DOC PREVIEW
MASON ECE 646 - RSA Implementation: Efficient encryption, decryption & key generation

This preview shows page 1-2-3-4 out of 12 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 12 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 12 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 12 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 12 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 12 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

MASON ECE 646 - RSA Implementation: Efficient encryption, decryption & key generation

Documents in this Course
Load more
Download RSA Implementation: Efficient encryption, decryption & key generation
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 RSA Implementation: Efficient encryption, decryption & key generation 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 RSA Implementation: Efficient encryption, decryption & key generation 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?