home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / sci / crypt / 7091 < prev    next >
Encoding:
Text File  |  1993-01-22  |  3.7 KB  |  101 lines
  1. Newsgroups: sci.crypt
  2. Path: sparky!uunet!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!cs.yale.edu!news-mail-gateway!daemon
  3. From: Markowitz@DOCKMASTER.NCSC.MIL
  4. Subject: RE: Public Key Ciphers
  5. Message-ID: <930122063829.282514@DOCKMASTER.NCSC.MIL>
  6. Sender: Markowitz.Catwalk2@DOCKMASTER.NCSC.MIL
  7. Organization: Yale CS Mail/News Gateway
  8. Date: Fri, 22 Jan 1993 06:38:00 GMT
  9. Lines: 90
  10.  
  11. rcain@netcom.com (Robert Cain) asks:
  12.  
  13. >>Is there a good description of ElGamal available by ftp from anywhere?
  14.  
  15. Don't know an FTP source, but it's not all that difficult:
  16.  
  17. Let p be a large prime (say 512 to 1024 bits), and g a generator of the
  18. multiplicative group of units in the finite field Zp (the integers mod
  19. p).  In other words g is an element of order p-1:  g^(p-1) = 1 mod p,
  20. but no smaller exponent satisfies this congruence.
  21.  
  22. (Actually, we could choose any element g of sufficiently large order,
  23. rather than a generator; this is useful in improving the efficiency of
  24. signature schemes without significantly comproming security.  See the
  25. NIST DSA explained below, for example.  But lets stick with a true
  26. generator of the full group for the moment; they're no harder to find.
  27. BTW, all this can just as easily be done over any finite field, but I'll
  28. stick to the prime ones for simplicity.)
  29.  
  30. Now Alice chooses a private key a in the range 1 < a < p, computes her
  31. public key g^a, and sends it to Bob.  If Bob has a message M in the
  32. range 1 < M < p, he can encrypt it for Alice by choosing a (secret)
  33. random k and computing:
  34.  
  35.     c = g^k mod p
  36.     d = (g^(ak) * M) mod p
  37.  
  38. He discards k and sends the pair [c,d] to Alice as the ciphertext.
  39. (Note the doubling of message size!)  Now Alice, knowing a may compute:
  40.  
  41.     c^(-a) * d = M mod p
  42.  
  43. There's actually more than one way to do this, but the point is that no
  44. one can strip the g^(ak) factor from d to recover M without knowing
  45. either Alice's secret key a or Bob's random number k.
  46.  
  47. Several digital signature schemes have been based on this variation of
  48. the Diffie-Hellman key exchange protocol.  ElGamal's original suggestion
  49. was to sign M, 1 < M < p, as folows:
  50.  
  51.     1. choose a secret random k relatively prime to p-1
  52.     2. compute r = g^k mod p
  53.     3. compute s = (M - ar) * k^-1 mod p-1
  54.  
  55. Alice sends [M,r,s] to Bob.  Bob takes Alice's public key y = g^a and
  56. checks that
  57.  
  58.     y^r * r^s = g^M mod p
  59.  
  60. If this equation holds, [r,s] is indeed Alice's signature on M (since
  61. step 3 required knowledge of the secret key a, only Alice could have
  62. sent it).
  63.  
  64. See:  A public key cryptosystem and a signature scheme based on discrete
  65. logarithms, IEEE Trans.  Info.  Theory, July 1985.
  66.  
  67. In 1989, Schnorr proposed a more efficient scheme based on taking g to
  68. be an element of large, but not maximal, order in Zp.  The Digital
  69. Signature Standard proposed by NIST (Federal Register, Aug.  30, 1991)
  70. is a variation on this idea:
  71.  
  72. Let p be a large prime with 2^511 < p < 2^512, q a large prime factor of
  73. p-1 with 2^159 < q < 2^160, and g and element of Zp* of order q.  Then,
  74. to sign M with the private key a:
  75.  
  76.     1. choose a secret random k relatively prime to q-1
  77.     2. compute r = g^k mod p mod q
  78.     3. compute s = (M + ar) * k^-1 mod q
  79.  
  80. Alice sends [M,r,s] to Bob who uses her public key y = g^a to check
  81. whether
  82.  
  83.     r = ( g^(M*s^-1) * y^(r*s^-1) mod p ) mod q
  84.  
  85. I'll leave it to you to check that this can only happen if it was really
  86. Alice.  :-)
  87.  
  88. All of these "proofs" are really just simple applications of Fermat's
  89. little theorem--computing mod q-1 in the exponent in this case; very
  90. similar to the proof that RSA decryption inverts encryption.
  91.  
  92. Michael
  93.  
  94. ----------
  95.   Michael J. Markowitz, VP R&D      markowitz@dockmaster.ncsc.mil
  96.   Information Security Corp.        708 405-0500, fax: 708 405-0506
  97.   1141 Lake Cook Rd., Suite D       MCI:  363-1959
  98.   Deerfield, IL  60302              CIS: 76206,2617
  99.  
  100.  
  101.