jjwlisenchuk@rose.waterloo.edu (Jason Lisenchuk) (03/29/88)
Has anyone put forth any alleged weaknesses of the RSA (Rivest-Shamir-Adleman) Public Key Cryptosystem? Is it possible that RSA is unconditionally secure for keys longer than (the square of) the block length if these keys are chosen with certain number-theoretic considerations in mind? By unconditionally secure I mean that deducing the key is computationally tantamount to exploring every possible ciphertext for a given plaintext, i.e. the 'randomness' in the key equals or exceeds that in the plaintext. Is it worth abandoning analysis of DES? Since DES uses a key of fixed length, its primitive functions etc. would have to be redesigned to accommodate a larger key whenever its computational security proved suspect. Is this not a fatal drawback in comparison with RSA which accommodates keys of arbitrary size? Since RSA is mathematically-founded, is anyone working on integrating error correction into the scheme? Jason J. W. Lisenchuk 4B Computer Science, Combinatorics and Optimization Faculty of Mathematics University of Waterloo
billc@prism.TMC.COM (03/30/88)
-Has anyone put forth any alleged weaknesses of the RSA (Rivest-Shamir-Adleman)
-Public Key Cryptosystem? Is it possible that RSA is unconditionally secure
-for keys longer than (the square of) the block length if these keys are chosen
-with certain number-theoretic considerations in mind?
-
-By unconditionally secure I mean that deducing the key is computationally
-tantamount to exploring every possible ciphertext for a given plaintext,
-i.e. the 'randomness' in the key equals or exceeds that in the plaintext.
I believe that breaking RSA is equivalent to factoring the
products of large primes. Right now, that task is "hard," to
put it loosely, as far as we know. Now, if someone can find a
way to easily factor large composites, RSA is in trouble.
-Since RSA is mathematically-founded, is anyone working on integrating error
-correction into the scheme?
It wouldn't be difficult to do. Take the plaintext and generate
the cyphertext, then send (or record) the cyphertext using an
error correcting code, like a Hamming Code, for example. Then,
on the other side, decode the error correcting code to get the
cyphertext, then decode the cyphertext into plaintext.
Bill Callahan 617-661-0777
Mirror Systems 2067 Massachusetts Avenue Cambridge, MA, 02140
billc@mirror.TMC.COM
UUCP : {mit-eddie, pyramid, wjh12, cca, datacube}!mirror!billcgdelong@cvbnet2.UUCP (Gary Delong x5232) (04/01/88)
In article <6053@watdragon.waterloo.edu>, jjwlisenchuk@rose.waterloo.edu (Jason Lisenchuk) writes: >Has anyone put forth any alleged weaknesses of the RSA (Rivest-Shamir-Adleman) >Public Key Cryptosystem? Is it possible that RSA is unconditionally secure >for keys longer than (the square of) the block length if these keys are chosen >with certain number-theoretic considerations in mind? The following is my submission for dumb question of the month: Having heard much about the "Public Key Crytosystem" for many years, I have yet to see the algorithm. Could someone e-mail me the information, or perhaps even post it? -- _____ / \ / All spelling errors | Gary A. Delong, N1BIP | \ / intentional for testing | linus!raybed2!cvbnet!gdelong \____\/ rn spellcorrector v1.10A. | (617) 275-1800 x5232
rgsmeb@abcom.ATT.COM (Michel Behna) (04/03/88)
From article <114@cvbnet2.UUCP>, by gdelong@cvbnet2.UUCP (Gary Delong x5232): > In article <6053@watdragon.waterloo.edu>, jjwlisenchuk@rose.waterloo.edu (Jason Lisenchuk) writes: > The following is my submission for dumb question of the month: > yet to see the algorithm. > Could someone e-mail me the information, or perhaps even post it? It has been widely published in many of the latest books on cryptography and there is a really good article on it in one of '85 or '84, '86 Scientific American. Sorry but I no longer have the references -- Michel Behna Qui a eu l'idee folle "Unix is unique!" D'inventer un jour l'ecole rgsmeb@abcom.att.com C'est se sacre Charlemagne {ncsc5,codas}!abcom!rgsmeb
falk@sun.uucp (Ed Falk) (04/14/88)
In article <114@cvbnet2.UUCP>, gdelong@cvbnet2.UUCP (Gary Delong x5232) writes: > > The following is my submission for dumb question of the month: > > Having heard much about the "Public Key Crytosystem" for many years, I have > yet to see the algorithm. > > Could someone e-mail me the information, or perhaps even post it? Since nobody else has said anything, I guess I will. Here's a summary of the introduction to Rivest, Shamir & Adlemen's original paper: M := plaintext message C := encrypted message E := encryption function D := decryption function so, C=E(M) and M=D(C) It is (hopefully) impossible to derive D even if you know E. As an added bonus, it is impossible to derive E from D. The idea is that I invent functions E and D that are unique to me (call them Em and Dm). I now *publish* Em. In this way, anybody can send a message to me by using C=Em(M) and mailing C to me over any unsecure channel. I use M=Dm(C) to read the message. Since nobody can derive Dm from Em, my mail is safe even though Em and C were transmitted through unsafe channels. As an added bonus, the RSA algorithm is commutitive. In other words, not only does M = D(E(M)) but M = E(D(M)) This means you can "sign" messages to guarentee authenticity. For instance, if you have your own functions, Ey and Dy you can encrypt a message like this: C = Dy(Em(M)) I then use M = Dm(Ey(M)) If the message is legible, then I know that (a) nobody but me could have read it, and (b) nobody but you could have sent it. That's the idea behind public-key cryptosystems. Here is how RSA works: You come up with two very large primes, p and q. I take their product and call it n. I use some other cute math to derive e and d from p and q. Now: e E(M) = M mod n d D(C) = C mod n For instance, if you choose 100-digit numbers for p and q, then n will be about 200 digits. Take your message and break it into 200-digit chunks and raise it to the e power, mod n. This gives you another 200-digit encrypted number which you send to me. The rest of the paper is devoted to deriving e and d from p and q, effecient algorithms for raising large numbers to large powers modulo other large numbers, finding large primes and so on. You could probably still order a copy from MIT press or LCS Laborator for Computer Science 545 Technology Square Cambridge, Massachusetts 02139 "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems"; Ronald Rivest, Adi Shamir, Len Adleman; LCS/TM82; April 4, 1977 (revised Dec 12, 1977) -- -ed falk, sun microsystems sun!falk, falk@sun.com terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO.
smb@ulysses.homer.nj.att.com (Steven Bellovin) (04/15/88)
} You could probably still order a copy from MIT press or LCS } } Laborator for Computer Science } 545 Technology Square } Cambridge, Massachusetts } 02139 } } "A Method for Obtaining Digital Signatures and Public-Key } Cryptosystems"; Ronald Rivest, Adi Shamir, Len Adleman; } LCS/TM82; April 4, 1977 (revised Dec 12, 1977) The same paper was published in the February 1978 issue of Communications of the ACM, which any technical library should have. A year or two earlier, Martin Gardner published an excellent explanation in Scientific American. New editions of Knuth, Vol. 2., discuss it as well.
dennis@rlgvax.UUCP (Dennis.Bednar) (04/16/88)
> In article <114@cvbnet2.UUCP>, gdelong@cvbnet2.UUCP (Gary Delong x5232) writes: > > > > Having heard much about the "Public Key Crytosystem" for many years, I have > > yet to see the algorithm. Besides the original paper, and the ACM reprint, there was some discussion in Dr. Dobb's Journal a year or two back. The article had source code in C, I believe, to generate large prime numbers, and therefore might also be useful to you. -- FullName: Dennis Bednar UUCP: {uunet|sundc}!rlgvax!dennis USMail: CCI; 11490 Commerce Park Dr.; Reston VA 22091 Telephone: +1 703 648 3300
dennis@rlgvax.UUCP (Dennis.Bednar) (04/16/88)
In article <49480@sun.uucp>, falk@sun.uucp (Ed Falk) writes: > > Here is how RSA works: > > You come up with two very large primes, p and q. I take their product > and call it n. I use some other cute math to derive e and d from p and > q. Now: > > e > E(M) = M mod n > > d > D(C) = C mod n > > For instance, if you choose 100-digit numbers for p and q, then n will > be about 200 digits. Take your message and break it into 200-digit chunks > and raise it to the e power, mod n. This gives you another 200-digit > encrypted number which you send to me. Ed, thanks very much for the lucid explanations. But I have a simple question. In order to better understand what you were saying, I tried picking small prime numbers, say p=3, and q=7. Each is a 1-digit number, and the product, n, is 21, which is 2 digits. So take the message and break it into 2 digit chunks. Lets look at what happens to an arbitrary two-digit chunk. Well, a two digit number is a number between 00 and 99. The problem is that e C = E(M) = M mod n will always return a number between 0 and 21, and therefore so will the D() function, since both functions return a number mod 21. Therefore if you encrypt a clear message M whose value was bigger than 21, you will never be able to decode it back to the original clear text, because the D() function will never return more than 21. Please clear up my misconfusion, if you could. Thanks. By the way, your discussion did not mention what d and e were, or how they were related to the original chosen p and q. I assume that they were numbers chosen, such that the the functions D and E were inverses of one another, ie that M = D(E(M)) C = E(D(C)) for all clear text messages M and all encoded messages C. The fact that such numbers d and e exist, and can be found for all M and all C is incredible (to me)! -- FullName: Dennis Bednar UUCP: {uunet|sundc}!rlgvax!dennis USMail: CCI; 11490 Commerce Park Dr.; Reston VA 22091 Telephone: +1 703 648 3300
falk@sun.uucp (Ed Falk) (04/16/88)
In article <921@rlgvax.UUCP>, dennis@rlgvax.UUCP (Dennis.Bednar) writes: > In article <49480@sun.uucp>, falk@sun.uucp (Ed Falk) writes: > > > > Here is how RSA works: > > > > You come up with two very large primes, p and q. I take their product > > and call it n. I use some other cute math to derive e and d from p and > > q. Now: > > > > e > > E(M) = M mod n > > > > d > > D(C) = C mod n > > > > For instance, if you choose 100-digit numbers for p and q, then n will > > be about 200 digits. Take your message and break it into 200-digit chunks > > and raise it to the e power, mod n. This gives you another 200-digit > > encrypted number which you send to me. > > Ed, thanks very much for the lucid explanations. But I have > a simple question. In order to better understand what you > were saying, I tried picking small prime numbers, say p=3, and q=7. > Each is a 1-digit number, and the product, n, is 21, which is 2 digits. > So take the message and break it into 2 digit chunks. Lets look > at what happens to an arbitrary two-digit chunk. Well, a two > digit number is a number between 00 and 99. The problem is that > e > C = E(M) = M mod n > > will always return a number between 0 and 21, and therefore > so will the D() function, since both functions return a number > mod 21. Therefore if you encrypt a clear message M whose value > was bigger than 21, you will never be able to decode it back > to the original clear text, because the D() function will never > return more than 21. Good point. I went back to the original paper and it said that both the plaintext (M) and the cypertext (C) are integers between 0 and n-1. > > By the way, your discussion did not mention what d and e were, > or how they were related to the original chosen p and q. > I assume that they were numbers chosen, such that the the > functions D and E were inverses of one another, ie that > > M = D(E(M)) > C = E(D(C)) > > for all clear text messages M and all encoded messages C. > The fact that such numbers d and e exist, and can be found > for all M and all C is incredible (to me)! To be honest, I don't understand the math behind this part. Apparently, there are a large number of d and e for each (p,q). According to R,S,A, you choose any d such that d is relatively prime to (p-1)*(q-1). gcd( d, (p-1)*(q-1) ) = 1 Any prime greater than max(p,q) will do here. e is simply the "multiplicitive inverse" of e, mod (p-1)*(q-1). (e*d) mod (p-1)*(q-1) = 1 They give an iterative algorithm for computing e which I'm not going to bother repeating here. It's similar to Euclid's algorithm for computing the gcd of (p-1)*(q-1) and d. -- -ed falk, sun microsystems sun!falk, falk@sun.com terrorist, cryptography, DES, drugs, cipher, secret, decode, NSA, CIA, NRO.
cik@l.cc.purdue.edu (Herman Rubin) (04/18/88)
In article <49704@sun.uucp>, falk@sun.uucp (Ed Falk) writes: > In article <921@rlgvax.UUCP>, dennis@rlgvax.UUCP (Dennis.Bednar) writes: > > In article <49480@sun.uucp>, falk@sun.uucp (Ed Falk) writes: > Apparently, there are a large number of d and e for each (p,q). According > to R,S,A, you choose any d such that d is relatively prime to (p-1)*(q-1). > > gcd( d, (p-1)*(q-1) ) = 1 > e is simply the "multiplicitive inverse" of e, mod (p-1)*(q-1). > > (e*d) mod (p-1)*(q-1) = 1 What Ed says is correct but slightly misleading. Instead of using (p-1)*(q-1) the use of lcm( p-1, q-1) is more enlightening, as two values of d or e which differ by multiples of this number are equivalent. This is why the example given with p=3, q=7 is not very revealing. The only values for d and e in this case are 1 and 5. There is even a discussion in the literature of choosing p and q so that there are few factors in common between p-1 and q-1; taking p = 2r+1, r prime, is one way to do this. It is important that p and q are difficult to find. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (ARPA or UUCP) or hrubin@purccvm.bitnet