1RSA Implementation:Efficient encryption, decryption & key generationECE646 Lecture 10Efficient encryption and decryption2Number of bits vs. number of decimal digits10#digits = 2#bits#digits = (log102) · #bits ≈≈≈≈ 0.30 · #bits256 bits = 77 D384 bits = 116 D512 bits = 154 D768 bits = 231 D1024 bits = 308 D2048 bits = 616 DHow to perform exponentiation efficiently?Problems:Y = XEmod N = X ⋅ X ⋅ X ⋅ X ⋅ X … ⋅ X ⋅ X mod NE-timesE may be in the range of 21024 ≈ 103081. huge storage necessary to store XE before reduction2. amount of computations infeasible to performSolutions:1. modulo reduction after each multiplication2. clever algorithms200 BC, India, “Chandah-Sûtra”3Right-to-left binary exponentiationS: X X2mod N X4mod N X8mod N … X2 mod NL-1E: e0e1e2e3… eL-1Y = X ⋅ (X2mod N) ⋅ (X4mod N) ⋅ (X8mod N) ⋅ … ⋅ (X2 mod N)E = (eL-1, eL-2, …, e1, e0)2e0e1e2e3eL-1Y = Xe0+ 2⋅e1+ 4⋅e2+ 8⋅e3+ … + 2L-1 ⋅eL-1mod N =Xa⋅ Xb= Xa+b(Xa)b= Xab= X = XEmod Ni=0L-1ei⋅ 2iL-1Y = XEmod NRight-to-left binary exponentiation: ExampleS: X X2mod N X4mod N X8mod N X16 mod NE: e0e1e2e3e41 1 0 0 1Y = X ⋅ X2mod N ⋅ 1 ⋅ 1 ⋅ X16 mod N =E = 19 = 16 + 2 + 1 = (10011)2= X 19mod NY = 319mod 113 32mod 11 =9 92mod 11 = 4 42mod 11 = 5 52mod 11 = 33 ⋅ 9 ⋅ 1 ⋅ 1 ⋅ 3 mod 11 (27 mod 11) ⋅ 3 mod 11 = 5 ⋅ 3 mod 11 = 44Left-to-right binary exponentiationE: eL-1eL-2eL-3… e1e0Y = ((...(((12⋅ X )2 ⋅ X )2 ⋅ X )2 …. )2 ⋅ X )2 ⋅ X mod NE = (eL-1, eL-2, …, e1, e0)2eL-1eL-2eL-3e1e0Y = X(eL-1⋅ 2 + eL-2) ⋅ 2 + eL-3) ⋅ 2 + …. + e1) ⋅ 2 + e0mod N =Xa⋅ Xb= Xa+b(Xa)b= Xab= XEmod Ni=0L-1ei⋅ 2iY = XEmod N= X2L-1 ⋅eL-1+ 2L-2 ⋅eL-2+ 2L-3 ⋅eL-3+…+2⋅e1+e0mod N = X =Left-to-right binary exponentiation: ExampleE: e4e3e2e1e0Y = ((...(((12⋅ X )2 ⋅ 1 )2 ⋅ 1 )2 ⋅ X)2 ⋅ X mod NY = (X8 ⋅ X)2 ⋅ X mod N = X19mod NE = 19 = 16 + 2 + 1 = (10011)2Y = 319mod 111 0 0 1 1= (((32mod 11) )2mod 11)2mod 11 ⋅ 3)2mod 11 ⋅ 3 mod 11 = (81 mod 11)2mod 11 ⋅ 3)2mod 11 ⋅ 3 mod 11 == (5 ⋅ 3)2mod 11 ⋅ 3 mod 11 == 42mod 11 ⋅ 3 mod 11 = = 5 ⋅ 3 mod 11 = 45Right-to-left binary exponentiationLeft-to-right binary exponentiationExponentiation: Y = XEmod NE = (eL-1, eL-2, …, e1, e0)2Y = 1;S = X;for i=0 to L-1{if (ei== 1)Y = Y ⋅ S mod N;S = S2mod N;}Y = 1;for i=L-1 downto 0{Y = Y2mod N;if (ei== 1)Y = Y ⋅ X mod N;}Exponentiation Example: Y = 712mod 11Right-to-left binary exponentiationLeft-to-right binary exponentiation12 = (1 1 0 0)2i 0 1 2 3ei0 0 1 1Sbefore7 5 3 9Yafter1 1 1 3 5Safter7 5 3 9 4i 3 2 1 0ei1 1 0 0Y 1 7 2 4 5Sbefore- S before round i is computedSafter- S after round i is computed6Right-to-Left Binary Exponentiation in HardwareMULSQRYSEoutputX1enableLeft-to-Right Binary Exponentiation in HardwareMULYEoutputX1ControlLogic7Basic Operations of RSAEncryptionDecryptionciphertext=modplaintextpublic key moduluspublic key exponentplaintext=modciphertextprivate key modulusprivate key exponentk-bitsk-bitsk-bitsk-bitsk-bits k-bitsL=kL < kCMeNMCdNTime of exponentiationtEXP(e, L, k) = #modular_multiplications(e, L) ⋅ tMULMOD(k)SOFTWARE#modular_multiplicationse=324e = F4= 2 + 1217large random L-bit eL + #ones(e) ≈ ⋅ L32tMULMOD(k) - time of a single modular multiplication of two k-bit numbers modulo a k-bit numberHARDWAREtMULMOD(k) = csm· k2tMULMOD(k) = chm· ke, L8Algorithms for Modular MultiplicationMultiplicationModular ReductionMultiplication combined withmodular reduction• Montgomery algorithm• Paper-and-pencil• Karatsuba• Schönhage-Strassen (FFT)• classical• Barrett• Selby-Mitchellθ(k2)θ(k3/2)θ(k ⋅ln(k))θ(k2)θ(k2)complexity same as multiplication usedθ(k2). . .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 = λ bitsPaper-and-Pencil Algorithm of MultiplicationAssertion:lg2n ≤ λx+++++9Classical Algorithm (1)x2n-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. . .ModularMultiplicationModular ExponentiationSOFTWAREHARDWAREcsm· k2chm· kTime of basic operations in software and hardwarecsme· k2· Lchme· k · L10Encryption/Signature verificationwith a small exponent eDecryption / Signature generationKey GenerationFactorization(breaking RSA)SOFTWAREHARDWAREcse· k2che· kTime of the RSA operations as a function of the key size kcsd· k3chd· k2csk· k4/log2kchk· k3/log2kexp(csf· k1/3· (ln k)2/3)Effect of the increase in the computer speedon the speed of encryption and decryption in RSAcomputer speedoperandsizeencryption/decryptionspeedto keep the same security11Decryption using Chinese Remainder Theorem=MPCPPdPmod=MQCQQdQmodCP= C mod PdP= d mod (P-1)CQ= C mod QdQ= d mod (Q-1)=modCMdNM = MP·RQ+ MQ·RP mod NwhereRP= (P-1mod Q) ·P = PQ-1mod NRQ= (Q-1mod P) ·Q= QP-1mod NTime of decryption without and with Chinese Remainder TheoremSOFTWAREHARDWAREWithout CRTWith CRTtDEC(k) = tEXP(random e, k, L=k) = cs ⋅ k3tDEC-CRT(k) ≈ 2 ⋅ tEXP(random e, k/2, L=k/2) = 2 ⋅ cs ⋅ ( )3 = tDEC(k)14Without CRTWith CRTtDEC(k) = tEXP(random e, k, L=k) = ch ⋅ k2tDEC-CRT(k) ≈ tEXP(random e, k/2, L=k/2) = ch⋅ ( )2 = tDEC(k)14k2k212Chinese Remainder TheoremLetN = n1⋅⋅⋅⋅ n2⋅⋅⋅⋅ n3. . . ⋅⋅⋅⋅ nMandfor any i, j gcd(ni, nj) = 1Then, any number 0 ≤ A ≤ N-1can be represented uniquely byA ↔↔↔↔ (a1= A mod n1, a2= A mod n2, …, aM= A mod nM)
View Full Document
Unlocking...