Transcription
IntroductionTextbook RSAAttacks on RSAPadded RSATextbook RSAAnd its insecuritiesFoundations of CryptographyComputer Science DepartmentWellesley CollegeFall 2016IntroductionTextbook RSAAttacks on RSATable of contentsIntroductionTextbook RSAAttacks on RSAPadded RSAPadded RSA
IntroductionTextbook RSAAttacks on RSAPadded RSARSA encryption So far, lots of talk, but noaction. We haven’t seen asingle example of a real, livepublic-key encryptionscheme. That is about to change.Today we introduce a verywell-known scheme based onthe RSA assumptiondiscussed several weeks ago. We start with a keygeneration algorithm thatshould look familiar.IntroductionTextbook RSAAttacks on RSAGenRSAAlgorithm 11.25.RSA key generation GenRSAInput: Length n; parameter tOutput: N, e, d as described below(N, p, q)GenModulus(1n )*(N) : (p 1)(q 1)choose e such that gcd(e, (N)) 1compute d : [e 1 mod (N)]**return N, e, d*N pq with p, q n-bit primes.**Such an integer d exists since e is invertible modulo (N).Padded RSA
IntroductionTextbook RSAAttacks on RSAPadded RSATextbook RSAConstruction 11.26.Define a public-key encryption scheme using GenRSA as follows: Gen: On input 1n run GenRSA(1n ) to obtain N, e, and d.The public key is hN, ei and the private key is hN, di. Enc: On input a public key pk hN, ei and a messagem 2 Z N , compute the ciphertextc : [memod N]. Dec: On input a private key sk hN, di and a ciphertextc 2 Z N , compute the messagem : [c dIntroductionTextbook RSAmod N].Attacks on RSAPadded RSATextbook RSA in actionExample 11.27.Say that GenRSA outputs (N, e, d) (391, 3, 235).*To encrypt the message m 158 2 Z 391 using the public key(391, 3), we computec : [1583mod 391] 295.To decrypt, the receiver computes[295235mod 391] 158.Ta-da!*Note that 391 17 · 23 so (391) 16 · 22 352. Moreover, 3 · 235 1mod 352.
IntroductionTextbook RSAAttacks on RSAPadded RSAOne thing’s for sure Computing the private key isat least as hard as factoringmoduli output by GenRSA. Unfortunately, this saysnothing about whether themessage can be recoveredfrom the ciphertext usingother means. Worst still, ”textbook RSA”is not secure with respect toany of the definitions ofsecurity proposed so far.**Why?IntroductionTextbook RSAAttacks on RSAPadded RSAEncoding binary strings as elements of Z N .Remark. Let kNk. Binary strings of length 1 may be viewas elements of ZN . Strings of varying length may be padded* tobring them up to correct length.Concern. Not all encoded messages m lie in Z N since it may bethe case that gcd(m, N) 6 1. What then?*In some unambiguous fashion. More on this in your homework.
IntroductionTextbook RSAAttacks on RSAPadded RSAThe choice of eRemark. For the most part, there does not appear to be anydi erence in the hardness of the RSA problem for di erent choicesof the exponent e, as long as it isn’t too small.Concern. One popular choice is to set e 3, since then computingeth powers modulo N requires only two multiplications. However,this choice does leave textbook RSA vulnerable to certain attacks*(more soon).*More evidence that Construction 10.15 leaves much to be desired.IntroductionTextbook RSAAttacks on RSAPadded RSAAttacks on “textbook” RSARemark. When e is small, for example e 3 and the message m issuch that m N 1/3 , then the encryption c [m3 mod N] m3doesn’t involve any modular reduction. We can recover themessage m by computing the cube root of c.Remark. It gets worse, there is a more general attack for any sizemessage when e is small and the message is sent to multiplereceivers. To see how, we will first need . . .
IntroductionTextbook RSAAttacks on RSAPadded RSAThe Chinese remainder theoremTheorem 8.24. Let N pq where p and q are relatively prime.ThenZN ' Zp Zq and Z N ' Z p Z q .Moreover, let f be the function mapping elementsx 2 {0, . . . , N 1} to pairs (xp , xq ) with xp 2 {1, . . . , pxq 2 {1, . . . , q 1} defined bydeff (x) ([xmod p], [x1} andmod q]).Then f is an isomorphism from ZN to Zp Zq as well as anisomorphism from Z N to Z p Z q .For example. Take N 15 5 · 3 and considerZ 15 {1, 2, 4, 7, 8, 11, 13, 14}.IntroductionTextbook RSAAttacks on RSAPadded RSAAttacking textbook RSA using the Chinese remaindertheoremExample. Let e 3, and say m was sent to three di erent partiesholding public keys pk1 hN1 , 3i, pk2 hN2 , 3i, andpk3 hN3 , 3i. The eavesdropper seesc1 [m3mod N1 ] and c2 [m3mod N2 ] and c3 [m3mod N3 ].Assume gcd(Ni , Nj ) 6 1 for all i, j.* Let N N1 N2 N3 . Anextended version of the Chinese remainder theorem says thereexists a unique ĉ N such that:ĉ c1ĉ c2ĉ c3*If not we’re done. Why?mod N1mod N2mod N3
ii. Rotor machines (Enigma and Magic)c. The third stage is the age of mathematics and computers.i. Primes in PIntroductionTextbook RSAAttacks on RSAPadded RSAii. Probabilisticencryption and proof-drivendesign. That’s us. Wewill view cryptography as an engine for turning “good” atomicprimitives into secure protocols.6. Assignment for next time:a. Read information.doc and please come see me if you have any questionsSinceortextbookRSAis backgrounddeterministic,if therequirements.message m is chosenconcerns aboutyouror the aphyby MihirtoBellarefrom a small list of possible values, then it is possibledetermineand Phillip Rogaway. As you areereading, make a list of questions,m fromthe ciphertext would[m likemodN] by tryingin eachvalue of m,comments,and concernsc youto ask/discussionclass. Beprepared1 m L. to discuss this chapter in class on Thursday.Brute againc. Take a deep breath and have fun! They are only shadows after all.When L is large, as for example in the case of hybrid encryptionwhere L 2 , one might hope Brute would not be a threat.Unfortunately, . . .IntroductionTextbook RSAAttacks on RSAPadded RSAA quadratic improvement in recovering mWe assume that m 2 and that the attacker knows . The value is a constant with 12 1.Algorithm 11.28.An attack on textbook RSA encryptionInput: Public key hN, ei; ciphertext c; parameter Output: m 2 set T : 2 for r 1 to T :xi : [c/r e mod N]sort the pairs {(r , xr )}Tr 1 by their second componentfor s 1 to T :?if [s e mod N] xr for some rreturn [r · s mod N]
IntroductionTextbook RSAAttacks on RSAPadded RSACommon modulus attackThe boss wants to use the same modulus N for each of itsemployees. Since it is not desirable for messages encrypted to oneemployee to be read by another other, the company issues di erent(ei , di ) to each employee.That is, the public key of the ith employee is pki hN, ei i and theprivate key is sk hN, di i What’s wrong with this picture?IntroductionTextbook RSAAttacks on RSAPadded RSACommon modulus attack: The sequelRemark. So, suppose the employees all trust each other, andsecurity only needs to be maintained against outsiders.Suppose the same message m is encrypted and sent to twodi erent employees with the public keys (N, e1 ) and (N, e2 ) wheregcd(e1 , e2 ) 1. Then an eavesdropper seesc 1 m e1mod N and c2 me2What’s the harm in that?mod N.
IntroductionTextbook RSAAttacks on RSAPadded RSAPadded RSA RSA does not possiblysatisfy any of our definitionsof security* and indeed isvulnerable to a number ofrealistic attacks. A simple “fix” might be toadd some form of randompadding to the messagebefore encryption.*It is deterministic.IntroductionTextbook RSAAttacks on RSAPadded RSAPadded RSA: The constructionConstruction 11.30.Let be a function with (n) 2nencryption scheme as follows:4 for all n. Define a public-key Gen: On input 1n , run GenRSA(1n ) to obtain (N, e, d). Outputpublic key pk hN, ei, and the private key sk hN, di. Enc: On input a public key pk hN, ei and a messagem 2 {0, 1}kNk (n) 2 , choose a random string r{0, 1} (n) andinterpret m̂ : r km as an element of ZN . Output the ciphertextc : [m̂emod N]. Dec: On input a private key sk hN, di and a ciphertext c 2 Z N ,computem̂ : [c d mod N],and output the k N k (n)2 low-order bits of m̂.
IntroductionTextbook RSAAttacks on RSAPadded RSAHow’d we do?Warning. When is too small, so that (n) O(log n), then abrute-force search through all possible values of padding r can becarried out in 2O(log n) time.Remark. When the padding is as large as possible and m is just asingle bit, then it is possible to prove security based on the RSAassumption.Remark. In between the situation is not so clear. For certainranges of we cannot prove security based on the RSAassumption. But no polynomial-time attacks are known either.
Introduction Textbook RSA Attacks on RSA Padded RSA A quadratic improvement in recovering m We assume that m 2 and that the attacker knows .Thevalue is a constant with 1 2 1. Algorithm 11.28. An attack on textbook RSA encryption Input: Public key hN,ei;ciphertextc;parameter O
