DOC PREVIEW
MASON ECE 646 - Project SPI-2

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

MASON ECE 646 - Project SPI-2

Documents in this Course
Load more
Download Project SPI-2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Project SPI-2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Project SPI-2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?