1RSA Implementation:Efficient encryption, decryption & key generationECE646 Lecture 11Efficient encryption and decryptionHow 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”2Right-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;}Basic 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(1) ≈ ⋅ L32tMULMOD(k) - time of a single modular multiplication of two k-bit numbers modulo a k-bit numberHARDWAREtMULMOD(k) = csm· k2tMULMOD(k) = chm· ke, L3Encryption/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 securityDecryption 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 N4Time 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)14k2k2Concealment of messages in the RSA cryptosystemBlakley, Borosh, 1979There exist messages that are not changed by the RSA encryption!For example:M=1 C = 1emod N = 1M=0 C = 0emod N = 0M=N-1≡-1 mod N C = (-1)emod N = -1Every M such thatMP= M mod P ∈ {1, 0, -1} MQ= M mod Q ∈ {1, 0, -1} CP= C mod P = (Memod N) mod P = Memod P = MPemod P = MPCQ= C mod Q = (Memod N) mod Q = Memod Q = MQemod Q = MQConcealment of messages in the RSA cryptosystemBlakley, Borosh, 1979At least 9 messages not concealed by RSA!Number of messages not concealed by RSA:σ = (1 + gcd(e-1, P-1)) · (1 + gcd(e-1, Q-1)) A.e=3 σ = 9B.gcd(e-1, P-1) = 2 and gcd(e-1, Q-1) = 2 σ = 9C.gcd(e-1, P-1) = P-1 and gcd(e-1, Q-1) = Q-1 σ = P·Q=NIt is possible that all messages remain unconcealed by RSA!5Efficient key generationGeneration of the RSA keyseTypically e = 3 ore = 216+ 1P, Qprime numbergenerationgcd(e, P-1) = 1gcd(e, Q-1) = 1N = P · QExtended Euclid’s algorithmd = e-1mod (P-1) ·(Q-1)gcd(e-1, P-1) = 2gcd(e-1, Q-1) = 2Random searchIncremental searchprimesnumbers tested for primalityRandom vs. Incremental Searchstarting point chosen at random6Is there a sufficent amount of prime numbersto choose from?π(x) - the amount of prime numbers smaller than x x0π(x) prime numbersπ(x) = xln(x)xπ(x)10100101504.3 ⋅10972.9 ⋅10147Is there a sufficent amount of prime numbersof the given bit length to choose from?πk- the amount of prime numbers of the size of k-bits 2k0πkprime numbers2k-1πk = π(2k) - π(2k-1) ≈≈ 0.5 ⋅ π(2k) ≈≈ π(2k-1) kπk38451210247 ⋅ 101124 ⋅ 101512.5 ⋅ 10305Average distance between primesof the given bit length (1)Average distance betweentwo consecutive primesprimesAverage distance (k) ≈2k-12k2k - 2k-1πk≈2k-1π(2k-1)≈ln 2k-1≈≈ 0.69 ⋅ (k-1)7Average distance between primesof the given bit length (2)Number of bitskAverage distancebetween primes2563845121024177265354709Average amountof odd numbers to test88132177355Euler’s TheoremLeonard Euler, 1707-1783∀∀∀∀a: gcd(a, N) = 1aϕϕϕϕ(N)≡≡≡≡ 1 (mod N)Fermat’s Theorem∀∀∀∀1 ≤≤≤≤ a ≤≤≤≤ p-1ap-1≡≡≡≡ 1 (mod p)If p is prime8{1..n-1}W(n)L(n)Witnesses to the compositnessof nLiars to the compositnessof nFermat’s primality testn compositea ∈∈∈∈ W(n) iff an-1≡≡≡≡ 1 mod n{1..n-1}W(n)L(n)Witnesses to the compositnessof nLiars to the compositnessof nFermat’s testn composite Carmichael numberW(n) = {a: 1 ≤≤≤≤ a ≤≤≤≤ n, gcd(a, n)>1} | L(n) | = ϕϕϕϕ(n)| W(n) | = n−ϕ−ϕ−ϕ−ϕ(n)Carmichael numbersA composite integer is a Carmichael number iffn= p1· p2· p3· … · pkk ≥ 3piare distinct primes, pi≠pjfor i ≠j∀pi(pi -1) | (n-1)Among all numbers smaller or equal to 1015There are about 3 ·1013prime numbers105 Carmichael numbersSmallest Carmichael numbern = 561 = 3 · 11 · 179{1..n-1}W(n)L(n)Witnesses to the compositnessof nLiars to the compositnessof nGood probabilistic primality testn composite∀ n composite | W(n) | ≥ | L(n) | If a ∈∈∈∈ W(n) test returns “n composite”else test returns “n probably prime”or “n pseudoprime to the base a”{1..n-1}W(n)L(n)Strong witnesses to the compositnessof nStrong liars to the compositnessof nMiller-Rabin testn composite∀ n composite | L(n) | ≤ ϕ(n)/4 < (n-1)/4 {1..n-1}W(n)L(n)Strong witnesses to the compositnessof nStrong liars to the compositnessof nMiller-Rabin testn composite1, n-1For certain composite numbers, such asn = 3 · 5 · 7 · . . . · (2k+1)there are only two strong liars: 1 and n-110Miller-Rabin testMathematical BasisIf n is prime then1 has only two square roots modulo ni.e., there are only two numbers, y1and y2, such thaty12mod n = 1 and y22mod n = 1y1=1 and y2=n-1≡-1 mod nIf n is composite then1 has at least four square roots modulo ni.e., there exist numbers, y1, y2, y3, y4, such thaty12mod n = 1, y22mod n = 1, y32mod n = 1, y42mod n = 1, y1=1, y2=n-1≡-1 mod n, y3≡ ± 1 mod n, y4≡ ± 1 mod nMiller-Rabin
View Full Document