Radix – 4 Implementation of a Montgomery Multiplier for a RSA CryptosystemPresentation TopicsRSA Public-Key CryptosystemRSA EquationsBinary ExponentiationMontgomery MultiplicationMontgomery ConversionExponentiation in Montgomery DomainRadix – 2 Processing ElementData PathRadix – 4 MultiplicationRadix – 4 Multiplication Using Carry Save AddersRadix – 4 Multiplication Using Booth EncodingRadix – 4 Montgomery MultiplicationRadix – 4 Montgomery ImplementationResultsConclusionRadix Radix ––4 Implementation 4 Implementation of a Montgomery Multiplier of a Montgomery Multiplier for a RSA Cryptosystemfor a RSA CryptosystemSteven Hubbard Steven Hubbard ECE ECE ––646646Presentation TopicsPresentation TopicsRSA Cryptography AlgorithmRSA Cryptography AlgorithmMontgomery MultiplicationMontgomery MultiplicationRadix Radix ––4 Multiplication4 MultiplicationRadix Radix ––4 Implementation of Montgomery 4 Implementation of Montgomery MultiplicationMultiplicationPublished Results & ConclusionsPublished Results & ConclusionsRSA PublicRSA Public--Key CryptosystemKey CryptosystemDeveloped by Developed by RivestRivest, , ShamirShamir, and , and AdlemanAdlemanin in 19781978Private Key contains two large prime numbers, Private Key contains two large prime numbers, ppand and qq, as well as a secret exponent , as well as a secret exponent ddPublic Key consists of n = Public Key consists of n = pp* * qq, with exponent , with exponent eeRequires Modular ExponentiationRequires Modular ExponentiationDecryption involves larger exponentiationDecryption involves larger exponentiationRSA EquationsRSA EquationsPublic Exponent Public Exponent eeis a number such that:is a number such that:gcd(egcd(e, , φφ) = 1) = 1φφ= (p = (p ––1)(q 1)(q ––1)1)Private Exponent d is obtained by:Private Exponent d is obtained by:d = ed = e--11mod mod φφEncryption OperationEncryption OperationC = MC = Meemod nmod nDecryption OperationDecryption OperationM = M = CCddmod nmod nBinary ExponentiationBinary ExponentiationRight to LeftRight to LeftLeftLeftto Rightto RightY = 1;Y = 1;Y = 1Y = 1S = X;S = X;for i=Lfor i=L--1 1 downtodownto00for i=0 to Lfor i=0 to L--11{{{{Y = YY = Y22mod N;mod N;if (if (eeii== 1)== 1)if (if (eeii== 1) == 1) Y = Y*S mod N;Y = Y*S mod N;Y = Y*X mod N;Y = Y*X mod N;S = S2 mod N;S = S2 mod N;}}} }Montgomery MultiplicationMontgomery MultiplicationEfficient technique for computing modular Efficient technique for computing modular exponentiations exponentiations Does not require division in taking modulusDoes not require division in taking modulusReplaces with bit shifting, which is fast and easy Replaces with bit shifting, which is fast and easy in hardwarein hardwareSimple conversion to Montgomery Domain Simple conversion to Montgomery Domain done before and after Multiplicationdone before and after MultiplicationMontgomery ConversionMontgomery ConversionGiven an integer a < M, A is said to be its MGiven an integer a < M, A is said to be its M--residue with residue with respect to r if,respect to r if,A = a*2k (mod M)A = a*2k (mod M)Likewise, given an integer b < n, B is its nLikewise, given an integer b < n, B is its n--residue with respect residue with respect to r if,to r if,B = b*2k (mod M)B = b*2k (mod M)The Montgomery product of A and B can then be defined as,The Montgomery product of A and B can then be defined as,C = A*B*rC = A*B*r--1 (mod M)1 (mod M)Exponentiation in Montgomery Domain Right-to-left binary exponentiationY = 1;S = X;Y’ = MP(Y, 22kmod N, N)S’ = MP(S, 22kmod N, N) for i=0 to L-1{if (ei == 1)Y’ = MP(Y’, S’, N);S’ = MP(S’, S’, N);}S = MP(S’, 1, N);Radix Radix ––2 Processing Element2 Processing ElementMultiple elements connected in serial to compute the multiplicatMultiple elements connected in serial to compute the multiplication. ion. The data path receives inputs from the previous stage and computThe data path receives inputs from the previous stage and computes the es the next next S(jS(j) )Data PathData PathRadix Radix ––4 Multiplication4 MultiplicationMultiply 2 bits of Multiplier per cycleMultiply 2 bits of Multiplier per cycleReduces partial products by halfReduces partial products by halfRequires additional MultiplexerRequires additional MultiplexerRadix Radix ––4 Multiplication Using Carry 4 Multiplication Using Carry Save AddersSave AddersUsing Carry Save Adders (CSA) instead of MultiplexerUsing Carry Save Adders (CSA) instead of MultiplexerDoes not require calculating “3a”Does not require calculating “3a”Radix Radix ––4 Multiplication Using 4 Multiplication Using Booth EncodingBooth EncodingUses xUses xi+1i+1, x, and x, x, and xii--11and recodes to zand recodes to z1/21/2between [2, between [2, --2]2]Radix Radix ––4 Montgomery 4 Montgomery MultiplicationMultiplicationUses principles of radix Uses principles of radix ––4 multiplication in Montgomery Domain4 multiplication in Montgomery DomainStepStep1: 1: S S = 0= 0xx--1 = 01 = 02: 2: FOR FOR j j = 0 TO = 0 TO N N --1 STEP 21 STEP 23: 3: ZjZj= = RecodingRecoding1(1(xjxj++1..¡1..¡--1)1)4: 4: ((Ca, SCa, S(0)) = (0)) = SS(0) + ((0) + (ZjZj* Y * Y )(0))(0)5: 5: qMjqMj= = SS(0)1(0)1....0 0 * * (4 (4 --MM(0)(0)--1111....0 ) mod 40 ) mod 45a:5a:q’Mjq’Mj= = RecodingRecoding2(2(qMj qMj ))6: 6: ((CbCb, S, S(0)) = (0)) = SS(0) + ((0) + (q’Mjq’Mj* M* M)(0))(0)7: 7: FOR FOR i i = 1 TO = 1 TO e e ––118:8:((Ca, Ca, SS((ii)) = )) = Ca Ca + + SS((ii) + () + (ZjZj* Y * Y )()(ii))9:9:((CbCb, , SS((ii)) = )) = CbCb+ + SS((ii) + () + (q’Mjq’Mj* * MM)()(ii))10:10:SS((ii--1) = (1) = (SS((ii)1)1....00, S, S((ii--1)1)BPWBPW--11....2)2)END FOR;END FOR;11: 11: Ca Ca = = CaCaor or CbCb12: 12: SS((ee--1) = 1) = signextsignext((CaCa, S, S((ee--1)1)BPWBPW--11....2)2)END FOR;END FOR;Radix Radix ––4 Montgomery 4 Montgomery ImplementationImplementationUses parallel Processing Elements to calculate multiple Uses parallel Processing Elements to calculate multiple iterations of Montgomery Multiplication algorithm at iterations of Montgomery Multiplication algorithm at onceonceResultsResultsResults from paper by Results from paper by KocKoc, , TawalbehTawalbeh, and , and TencaTencaat at Oregon State UniversityOregon State
View Full Document
Unlocking...