[1302] in cryptography@c2.net mail archive
Useful El Gamal Variant
daemon@ATHENA.MIT.EDU (John Kelsey)
Sun Aug 3 17:17:42 1997
To: "Perry's crypto list" <cryptography@c2.net>
From: John Kelsey <kelsey@plnet.net>
Date: Sun, 03 Aug 97 15:35:32 CDT
-----BEGIN PGP SIGNED MESSAGE-----
[ To: sci.crypt ## Date: 02-Aug-97 ##
Subject: Useful El Gamal Variant ]
I came up with this El Gamal variant a while back, and I'm
curious about whether anyone else has done something similar.
(It's not so novel that I would really expect to be the first
person to come up with it.) The idea is to use offline
Diffie-Hellman key exchange to encrypt to multiple recipients in
a way that's clearly no less secure than standard offline
Diffie-Hellman.
For review: El Gamal encryption is Diffie-Hellman done with the
receiver's public key instead of a one-use g^x mod p value. The
resulting key is then used to encrypt a short message, such as
the session key to be used. In the ``standard'' version of El
Gamal encryption, we use multiplication mod p as the encryption
technique. This is actually not a good idea. It makes more
sense to use the Diffie-Hellman derived key with a well-known
symmetric encryption algorithm, such as triple-DES.
As a simple example, suppose I want to send a message to Alice.
1. Alice's public key is Y = g^x mod p--I know Y but not x.
2. I generate r = g^z mod p, for some random z.
3. I form key K = hash(Y^z mod p).
4. I encrypt my actual message using triple-DES with key K.
5. I send r and the encrypted message to Alice.
Now, all of this is standard stuff. For some applications,
though, it would be nice to be able to minimize the effort and
space taken up by encrypting a message to many different people.
(One example of this comes up with PGP, which has an option to
encrypt a message to multiple recipients.)
Here's how to do this cheaply:
1. We have N recipients, with public keys Y[0] to Y[N-1].
Each public key is a Diffie-Hellman key, as with the above
example. I also have a private signing key, privKey.
2. We have a message key, K[*], which is used to encrypt the
actual message. This is 128 bits long.
3. I form r = g^z mod p, for some random z.
4. I form a check block, C = hash(r,K[*]).
5. For each intended recipient i, I do the following:
a. Form K[i] = hash(C,Y[i]^z mod p)
b. Form B[i] = encrypt(K[i],K[*])
6. Form ciphertext =
encrypt(K[*],(plaintext,SIGN(privKey, plaintext))
7. Form final message M =
r,C,B[0],B[1],...,B[N-1],ciphertext.
Assuming a 1024-bit modulus and a 160-bit hash, this adds
160+(N-1)*128 bits to encrypt to N recipients rather than to one
recipient. In most circumstances, this isn't a terribly big
gain, but it is really useful for some rare cases. For example,
in the rare cases where it makes sense to use key-recovery
mechanisms, this provides a really nice way to do this on the
cheap. Suppose I have a tape backup mechanism. To simplify my
life, I have the process set up to encrypt the backups under a
public key which I hold on a tamper-resistant token. In case
the token is destroyed, I also have five other public keys of
trustees. I use a 3/5 secret sharing scheme to share my key
among them, and then encrypt each share instead of the actual
key K[*] in my example, above. The nice thing about this is
that it makes it only moderately expensive to use more
trustees--adding a trustee costs only 128 bits per stored
message. The more often we do this, the bigger the savings.
Thus, it might be really useful for situations where we encrypt
lots of files or individual records under someone's public key,
and want backups, or where we really want to encrypt lots of
files or records individually under N different public keys.
Comments?
--John Kelsey, Counterpane Systems, kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBM+RgyEHx57Ag8goBAQG8LAP/W5GHdARGU1nojADiVOezYelQPihizMwv
k/PrjDrdUBHPcsqMh1Pc0lCSPJ3QYmFPFou4n2y0UGeCOjH2RVABRt9QTVl1VfoB
snWx1F7exDXM/XWAvjUbFwrM6u4toO9QLoXe4af+0dE/CknEhHOJdQyt8zZ2Y2oE
vxUCIq7HQJw=
=eEaq
-----END PGP SIGNATURE-----
--John Kelsey, Counterpane Systems, kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
