Rsa
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Rsa as PDF for free.
More details
- Words: 979
- Pages: 11
+
+
RSA Security
• RSA was invented by Rivest, Shamir and Aldleman in 1978 (the 2003 winners of Turning award).
• RSA is the best known public-key cryptosystem.
• RSA is the first practical realisation of the revolutionary notion of public-key cryptography invented by Diffie and Hellman in 1976.
+
1
+
+
RSA Cryptosystem • Problems Used: Factorisation. The modulus N = p × q is public, the primes p, q are secret. • Message Space: M = ZN . • Cryptogram Space: C = ZN . • Public Key: A random integer e ∈ ZN ; gcd (e, ϕ(N )) = 1. • Secret Key: An integer d ∈ ZN such that d · e ≡ 1 (mod (p − 1)(q − 1)).
+
• Encryption: c = Ee(m) ≡ me
(mod N ).
• Decryption: m = Dd(c) ≡ cd
(mod N ). 2
+
+
Factorisation “=⇒” breaking RSA • If you can factor N , how can you break RSA? • Attack: – Find p and q such that N = pq – Compute ϕ(N ) = (p − 1)(q − 1) – Compute the secret key d from the public key e and ϕ(N ). That is, the attacker computes d = e−1 (mod ϕ(N )) using the Euclidean algorithm. • It has been conjectured that breaking RSA is polynomially equivalent to factoring N , but this remains unproved (note: two problems are said to be polynomially equivalent if the existence of a polynomial-time algorithm for either problem implies the existence of a polynomial-time algorithm for the other problem). +
3
+
+
Knowing ϕ(N ) ‘=⇒” breaking RSA • Question: Assume that Euler’s totient function ϕ(N ) has been made public. Is it possible to compute factors of N from it ?
• Attack – ϕ(N ) = (p−1)(q−1) = N −p−q+1 = N −p−
N +1 p
– This equation can be rewritten as p2 + p(ϕ(N ) − N − 1) + N = 0 – Clearly, the equation has two solutions: the factors p and q. The conclusion is that revealing ϕ(N ) allows to factor N .
+
4
+
+
Iteration Attack on the RSA • Simmons and Norris in1977 showed that RSA is breakable if the multiplicative group contains short cycles. • Let the opponent know the public elements (N, e) and a cryptogram c ∈ ZN . • the opponent can generate the following sequence ei
ci ≡ c
(mod N )
for i = 1, 2, . . .. • If there is an element cj such that c = cj , then the message used to generate c is cj−1. • To avoid the iteration attack is enough to select the primes p and q so p − 1 = 2 × p and q−1 = 2×q where p and q are primes. +
5
+
+
Common Modulus Attack on the RSA
• Question: Can the modulus N be shared amongst several RSA schemes?
• Answer: No. There are at least 3 known attacks against this scenarios.
+
6
+
+
Attack I • Attack: Any user can find the secret key of other users. • Assume there are two pairs key (e1, d1) and (e2, d2) given to user 1 and user 2, respectively. • Lemma: If one knows the RSA secret key d corresponding to the public key (N, e) then one can efficiently factor N (the tutorial question). • Assume user 1 is the bad guy, he knows d1 and (N, e1) he then computes p and q by Lemma. He further computes ϕ(N ). Now since he knows e2, he can then computes d2 = e−1 (mod ϕ(N )) using the 2 Euclidean algorithm. +
7
+
+
Attack II If the same message is encrypted with the two different keys, the message can be recovered. • Attack: If a message is encrypted with two different keys, the attacker can recover the message. • Assume there are two pairs key (e1, d1 ) and (e2 , d2). Assume also e1 and e2 are relatively prime (they generally would be). Let m be the plaintext and the two ciphertexts are c1 = me1 c2 = me2
(mod N ) (mod N )
• The opponent knows N, e1, e2 , c1 and c2 . We show that he can recover m. • Since e1 and e2 are relatively prime, find r and s using the Euclidean algorithm such that r × e1 + s × e2 = 1 • Assuming r is negative (either r or s has to be), then the Euclidean algorithm can be used again to calculate c−1 1 . Then −r × cs2 = m (c−1 1 )
+
(mod N ) 8
+
+
Attack III If two pairs of keys have been compromised and made public. It is possible to find factors of N or equivalently ϕ(N ) ? (see the textbook)
+
9
+
+
Low Exponent Attack Against the RSA
• Question: If we use the low values for e, the public key, it makes encryption fast and easy to perform. Can we choose small e for RSA? • Answer:
+
No.
10
+
+
Attack on e = 3 • Suppose we have 3 users with different moduli N1, N2 and N3 , respectively. • Assume someone sends them the same message m. The attacker sees c1 = m3 c2 = m3 c3 = m3
(mod N1) (mod N2) (mod N3)
• The attacker, using the Chinese Remainder Theorem, computes X
= ci
(mod Ni), i = 1, 2, 3,
to obtain X = m3
(mod N1 N2N3 ).
• Since m3 < N1 N2 N3, X = m3 identically over the integers. The attacker recover m by taking the real cube root of X
+
11
+
RSA Security
• RSA was invented by Rivest, Shamir and Aldleman in 1978 (the 2003 winners of Turning award).
• RSA is the best known public-key cryptosystem.
• RSA is the first practical realisation of the revolutionary notion of public-key cryptography invented by Diffie and Hellman in 1976.
+
1
+
+
RSA Cryptosystem • Problems Used: Factorisation. The modulus N = p × q is public, the primes p, q are secret. • Message Space: M = ZN . • Cryptogram Space: C = ZN . • Public Key: A random integer e ∈ ZN ; gcd (e, ϕ(N )) = 1. • Secret Key: An integer d ∈ ZN such that d · e ≡ 1 (mod (p − 1)(q − 1)).
+
• Encryption: c = Ee(m) ≡ me
(mod N ).
• Decryption: m = Dd(c) ≡ cd
(mod N ). 2
+
+
Factorisation “=⇒” breaking RSA • If you can factor N , how can you break RSA? • Attack: – Find p and q such that N = pq – Compute ϕ(N ) = (p − 1)(q − 1) – Compute the secret key d from the public key e and ϕ(N ). That is, the attacker computes d = e−1 (mod ϕ(N )) using the Euclidean algorithm. • It has been conjectured that breaking RSA is polynomially equivalent to factoring N , but this remains unproved (note: two problems are said to be polynomially equivalent if the existence of a polynomial-time algorithm for either problem implies the existence of a polynomial-time algorithm for the other problem). +
3
+
+
Knowing ϕ(N ) ‘=⇒” breaking RSA • Question: Assume that Euler’s totient function ϕ(N ) has been made public. Is it possible to compute factors of N from it ?
• Attack – ϕ(N ) = (p−1)(q−1) = N −p−q+1 = N −p−
N +1 p
– This equation can be rewritten as p2 + p(ϕ(N ) − N − 1) + N = 0 – Clearly, the equation has two solutions: the factors p and q. The conclusion is that revealing ϕ(N ) allows to factor N .
+
4
+
+
Iteration Attack on the RSA • Simmons and Norris in1977 showed that RSA is breakable if the multiplicative group contains short cycles. • Let the opponent know the public elements (N, e) and a cryptogram c ∈ ZN . • the opponent can generate the following sequence ei
ci ≡ c
(mod N )
for i = 1, 2, . . .. • If there is an element cj such that c = cj , then the message used to generate c is cj−1. • To avoid the iteration attack is enough to select the primes p and q so p − 1 = 2 × p and q−1 = 2×q where p and q are primes. +
5
+
+
Common Modulus Attack on the RSA
• Question: Can the modulus N be shared amongst several RSA schemes?
• Answer: No. There are at least 3 known attacks against this scenarios.
+
6
+
+
Attack I • Attack: Any user can find the secret key of other users. • Assume there are two pairs key (e1, d1) and (e2, d2) given to user 1 and user 2, respectively. • Lemma: If one knows the RSA secret key d corresponding to the public key (N, e) then one can efficiently factor N (the tutorial question). • Assume user 1 is the bad guy, he knows d1 and (N, e1) he then computes p and q by Lemma. He further computes ϕ(N ). Now since he knows e2, he can then computes d2 = e−1 (mod ϕ(N )) using the 2 Euclidean algorithm. +
7
+
+
Attack II If the same message is encrypted with the two different keys, the message can be recovered. • Attack: If a message is encrypted with two different keys, the attacker can recover the message. • Assume there are two pairs key (e1, d1 ) and (e2 , d2). Assume also e1 and e2 are relatively prime (they generally would be). Let m be the plaintext and the two ciphertexts are c1 = me1 c2 = me2
(mod N ) (mod N )
• The opponent knows N, e1, e2 , c1 and c2 . We show that he can recover m. • Since e1 and e2 are relatively prime, find r and s using the Euclidean algorithm such that r × e1 + s × e2 = 1 • Assuming r is negative (either r or s has to be), then the Euclidean algorithm can be used again to calculate c−1 1 . Then −r × cs2 = m (c−1 1 )
+
(mod N ) 8
+
+
Attack III If two pairs of keys have been compromised and made public. It is possible to find factors of N or equivalently ϕ(N ) ? (see the textbook)
+
9
+
+
Low Exponent Attack Against the RSA
• Question: If we use the low values for e, the public key, it makes encryption fast and easy to perform. Can we choose small e for RSA? • Answer:
+
No.
10
+
+
Attack on e = 3 • Suppose we have 3 users with different moduli N1, N2 and N3 , respectively. • Assume someone sends them the same message m. The attacker sees c1 = m3 c2 = m3 c3 = m3
(mod N1) (mod N2) (mod N3)
• The attacker, using the Chinese Remainder Theorem, computes X
= ci
(mod Ni), i = 1, 2, 3,
to obtain X = m3
(mod N1 N2N3 ).
• Since m3 < N1 N2 N3, X = m3 identically over the integers. The attacker recover m by taking the real cube root of X
+
11
