Project SPI-2Classical Algorithm(pseudo code )Barrett’s Algorithm(pseudo code )Montgomery Algorithm(pseudo code )Modular Multiplication AlgorithmsSupport FunctionsImplementation NotesImplementation Notes Number of bits -vs- Number of decimal digitsImplementation Notes Sizes and NumbersLimitations and ProblemsTest ResultsGraphic RepresentationConclusionsBatch File (for 128 bit numbers)Barrett’s (2048 bits)Project SPI-2Modulo Reduction of Large Integers using the Classical, Barrett, MontgomeryTeam Members: Bich-Ha PhungMichael JohnsonThomas ShackelfordSukhonthip RueangvivatanakijSeptember 4, 2005 2Classical Algorithm(pseudo code )The pseudo code of the Classical Algorithm given mk-1≥ b/2 follows:if (x > mbl-k) thenx = x - mbl-kfor (i = l-1; i > k-1; I--) do {if (xi== mk-1) thenq = b-1;elseq = (xib+ xi-1) div mk-1;while (q(mk-1b + mk-2) > xib2+ xi-1b + xi-2) do q = q-1;x = x – qmbi-k;if (x < 0) thenx = x + mbi-k; }Classical Algorithmx2n-1x0. . .x1x2n-2x2n-3xn-1. . .m0mn-1mn-2. . .:x0. . .x1x2n-2x2n-3xn-1. . .q’n-1 mxm–q’n-1=x2n-1b+ x2n-2mn-1q’n-1 = qn-1+ εε = 0, 1, 2m0mn-1mn-2. . .–x0. . .x1x2n-3xn-1. . .:q’n-2=x2n-2b+ x2n-3mn-1q’n-2 = qn-2+ εε = 0, 1, 2. . . . . . .x0x1xn-1. . .http://mason.gmu.edu/~kgaj/ECE297/viewgraphs/lecture10_RSA_implement_2.pdfSeptember 4, 2005 4Barrett’s Algorithm(pseudo code )The pseudo code of Barrett’s algorithm given µ= b2kdiv m follows:q1 ← x div bk-1;q2 ← q1* µ;q3 ← q2 div bk+1;r1 ← x mod bk+1;r2 ← q3 * m mod bk+1;r ← r1 - r2;If r < 0 then r ← r + bk+1;While r >= m dor ← r – m;Return r;September 4, 2005 5Montgomery Algorithm(pseudo code )The pseudo code of Montgomery’s algorithm givenm’ = m-1mod n using Extended Euclidean Algorithmfor (i=0; i < k; i++) do {ti= (xi* m’0) mod b;x = x + timbi;}x = x div bk;if (x ≥ m) then x = x – m;September 4, 2005 6Modular Multiplication Algorithms Multiplication• Paper-and-pencil θ(k2)• Karatsuba θ(k3/2)• Schönhage-Strassen (FFT) θ(k ⋅ ln(k))Modular Reduction• classical θ(k2)• Barrett complexity same as multiplication used• Selby-Mitchell θ(k2)Multiplication combined with modular reduction• Montgomery algorithm θ(k2)http://mason.gmu.edu/~kgaj/ECE297/viewgraphs/lecture10_RSA_implement_2.pdfSeptember 4, 2005 7Support Functions Addition Subtraction Multiplication Division CheckSize PowerOf FillVector TwistProgram Logic for the addition, subtraction, multiplication, anddivision functions was borrowed from D. Knuth's book "The art of Computer Program Volume II (1998)Multiplication AlgorithmPaper-and-Pencil. . .A0A1An-1An-2. . .B0B1Bn-1Bn-2D0D1D2. . .C0C1Cn-1Cn-2. . .CnCn+1C2n-1C2n-2D2n-4D2n-3D2n-2. . . . .3 words3 wordsABC2 words2 wordsD0= A0B0D1= A0B1+ A1B0D2= A0B2+ A1B1+ A2B0D2n-4= An-3Bn-1+ An-2Bn-2+ An-1Bn-3D2n-3= An-2Bn-1+ An-1Bn-2D2n-2= An-1Bn-11 word = l bytes = λ bitsAssertion:lg2n ≤λx+++++http://mason.gmu.edu/~kgaj/ECE297/viewgraphs/lecture10_RSA_implement_2.pdfSeptember 4, 2005 9Implementation Notes PIII 500 MHZ with 256 MB RAM MS Visual C++ version 6 with SP5 Vectors (Dynamic Arrays) 16 bit word size Hexadecimal format Input numbers read through argv[ ] x = (x2n-1•••x1x0)b m = (mn-1•••m1m0)b Timing (Win32 API getTickCount())September 4, 2005 10Implementation NotesNumber of bits -vs-Number of decimal digits#Digits = (log102) * #bits = 0.30 * #bits38 digits = 128 bits77 digits = 256 bits116 digits = 384 bits154 digits = 512 bits231 digits = 768 bits308 digits = 1024 bits616 digits = 2048 bitsNumbers were first generated in decimal format from π and then converted into hexadecimal formathttp://mason.gmu.edu/~kgaj/ECE297/viewgraphs/lecture13_RSA_implement_2.pdfSeptember 4, 2005 11Implementation NotesSizes and Numbers 128 Bits 1383d25c23903d1d9951313a661044 256 Bits 5f75ada81d4234952d566490beaa890d1f1bd3d5ce124301b320a3fd7cc77f2 384 Bits 252346c4f0cbe2a08b9d2b7911a33a9c8ba5bb1f1d901f864b425245c455bc01bf8a9dc6a7bd47848b68203cf59c799f1 512 Bits 1e68ba8493c5b956f62421f441cf0fceea961bc638c797c09882371a1eb4d81e48127ae2ad9d906b85383578b962fb5767db882c7deeb3c3c080e346d8f8575d 768 Bits 14da0d121a16d1f467b1616701bfca4f8bc2af60c1bfc7316597a766dfaeb24fc5766195063df88c86d90ed003dd7819e0ed1140de0f6f2a02744bd2721dfd14987d0d485e23848ff17f5e08dd6df4de901a88da9000c7986b9e37cef9871b52 1024 Bits 120207e704722209f8c50524ac2293581e93b8bc6e75faf7c3ff85dda178abc2411e4ee3ae21d48306417ccca367a86ef7c3976ca9969e96d284119f167e19f70af43da60b31232c8cb44185525b7119f3e98debc2328db22a290952375ae9b1f0366dd74e3005ba6cc77d2ecbb8fddc09ab821ac53864301b320a3fd7cc77f2 2048 Bits A046C6B5DD22208C0FA194D22BA47252DA71B71E5096A684D042433039657C6CA60F5AA1D510195582B0F5493AF6EDD7179BA442B1C95F75C44BD74A42AD5B77B0796D3334F5BD53B9383B9FEB0C7060D4DE73B09F6E3B76E72F9A4489EEF234CCB6BC9A4D82D9ABC6D3D65B7C0018B8DAF938FEB55D1AFCF0B646C8CD7BB16D592168524392CD360D1501B694C750AF0AE99A5EB12E7876640F12175FA6946D2AB5AE40E23C9F7F37A374F6F300CCEB58EB83BABAAC8EC7B22F3DF89FC2D6BE6943DF1B4B231A2C3EA4839A7A4B05AAD0D1D7956BCB42A551AD7CF5B31E421BAF20AADEFAF50BCED9266DA294DE6F6EFA38BF02D7569618803BD0725C941C8September 4, 2005 12Limitations and Problems Library Prohibition Signed versus Unsigned numbers Differences between processors Intel vs Athon Pre-computation of input Decimal to Hexadecimal Barrett’s µ= b2k/m. Montgomery’s m’ = m-1mod nSeptember 4, 2005 13Test Results128 Bits 256 Bits 384 Bits 512 Bits 768 Bits 1024 Bits 2048 BitsBarrett's 2 6 12 17 31 51 175Classical 94546637899169Montgomery 78 78 78 75 75 76 81All times are in Milliseconds• Input key length is equal to 2n-1 where the moduli length is equal to n-1• Results tested against the CBigInt and NTL large integer librariesSeptember 4, 2005 14Graphic RepresentationModular Reduction0102030405060708090100110120130140150160170180190200128 Bits 256 Bits 384 Bits 512 Bits 768 Bits 1024 Bits 2048 BitsBarrett'sClassicalMontgomeryTime in MillisecondsMillisecond = 0.001September 4, 2005 15Conclusions Barrett’s is best for input < 1024 bits Montgomery’s is best for input > 1024 bits Classical is best for single modular reductions Results similar to results published in 1998 by Bosselaers, Govaerts, Vandewalle using C Room for improvementSeptember 4, 2005 16Batch File (for 128 bit numbers)HexVersion 0acaf5dc5aad6d4b769529f6b786b2 3fe2de38c5bf86b2HexVersion
View Full Document