Subject: Diffie-Hellman key agreement

From: Timo Schulz <[email-masked]>
Date: Mon, 9 Dec 2002 13:39:06 +0100

Hi,

I ask me if there are any plans to add the needed details for the
public key algorithm type 21 (Reserved for Diffie-Hellman). IMHO
this algorithm could be useful in some cases to reduce the complexity
of key exchange and public keys in general.

On the other hand it's a little annoying that you need more than one
step to exchange the final session key. But this could be easily solve
with a variation of the DH algorithm:

  w = secret key which is chosen randomly (w < p)
  p = prime ((prime-1)/2 should be also prime)
  g = primitive generator for p
  y = public key (g^w mod p)

  1. alice gets the public key of the recipient bob (p, g, y)
  2. alice chose a random x (x < p) and calculates X = g^x mod p
     the session key is: s = y^x mod p
  3. alice ciphers the message with the session key s und sends bob
     X and the ciphered message
  4. bob calculates s = X^w mod p and can decipher the message

Compared to the performance of RSA and ELG it should be faster because
the exponents are not very large (~160 bits) and no multiplicative inverse
is needed. IMHO this algorithm should have the same strength as ELG.

And the integration into the OpenPGP protocol should be also easy:

Tag 1: set pubkey algorithm 21 and wrap X into a PGP MPI.
Tag 6: set pubkey algorithm 21 and store p, g, y (same as for ELG keys).
Tag 5: set pukey algorithm 21 and store p, g, y, w (same as ELG keys).

        Timo

Date: Mon, 9 Dec 2002 13:39:06 +0100
From: Timo Schulz <[email-masked]>
To: [email-masked]
Subject: Diffie-Hellman key agreement
Reply-To: [email-masked]
Mail-Followup-To: [email-masked]
Sender: [email-masked]

Hi,

I ask me if there are any plans to add the needed details for the
public key algorithm type 21 (Reserved for Diffie-Hellman). IMHO
this algorithm could be useful in some cases to reduce the complexity
of key exchange and public keys in general.

On the other hand it's a little annoying that you need more than one
step to exchange the final session key. But this could be easily solve
with a variation of the DH algorithm:

  w = secret key which is chosen randomly (w < p)
  p = prime ((prime-1)/2 should be also prime)
  g = primitive generator for p
  y = public key (g^w mod p)

  1. alice gets the public key of the recipient bob (p, g, y)
  2. alice chose a random x (x < p) and calculates X = g^x mod p
     the session key is: s = y^x mod p
  3. alice ciphers the message with the session key s und sends bob
     X and the ciphered message
  4. bob calculates s = X^w mod p and can decipher the message

Compared to the performance of RSA and ELG it should be faster because
the exponents are not very large (~160 bits) and no multiplicative inverse
is needed. IMHO this algorithm should have the same strength as ELG.

And the integration into the OpenPGP protocol should be also easy:

Tag 1: set pubkey algorithm 21 and wrap X into a PGP MPI.
Tag 6: set pubkey algorithm 21 and store p, g, y (same as for ELG keys).
Tag 5: set pukey algorithm 21 and store p, g, y, w (same as ELG keys).

        Timo