Diffie Hellman key agreement using RSA keys?

Question

I want to have 2 parties agree on the same secret key using their public and private keys. I do not want them to have any interaction. So I'm thinking method(A.privKey, B.pubKey) gives the same number as method(B.privKey, A.pubKey)

I was wondering if the Diffie-Hellman key agreement algorithm works in Java when you use KeyPairGenerator.getInstance("RSA")

If so, how can I do this? Or do I need to use the KeyPairGenerator.getInstance("DH")?

I have searched online and can't seem to find the answer.

Hetzel

Answer 1

The mathematics behind Diffie-Hellman and RSA are different enough so that an RSA key can't work for DH.

Diffie-Hellman

DH is a key-exchange, it produces a shared key given two key-pairs. It doesn't encrypt data directly. (But it's easy to build encryption by combining DH with symmetric encryption).

Both sides agree on a group, in the simplest case defined by g and p where p is a safe prime.

A private key is simply a number a, the corresponding public key A is g^a mod p. A shared key an be computed since exponentiation is commutative, so

A^b = (g^a)^b = g^(ab) = (g^b)^a = B^a

For this to work both keypairs need to use the same group. The easiest way to achieve this is picking one particular group and hardcoding it into your protocol / application.

RSA

RSA encrypts a message m with the public key, producing a ciphertext c. So it only uses one key-pair, the key-pair of the recipient.

The private key is a fixed exponent e (typically 65537) and a pair of primes p and q.

The corresponding public key is e and the product of the primes n = p * q.

Encryption happens by computing c = m^e mod n which can be revered only if you know p and q but not if you only know n.

Comparison

You can produce a shared key using RSA by generating a random key as sender and encrypting it using the recipient's public key. This works for encrypting a message to the recipient without interaction. But it does not authenticate the sender since they can control the shared key. So if you can't use RSA to achieve non interactive deniable authentication. But you can sign the message with RSA (but don't use the same keypair for signing and encryption), giving you non repudiable authentication.

Hardi

Answer 2

Due to the fact that RSA doesn't actually produce a public and private key pair, but a pair of inverse keys, you can do an exchange with RSA keys that produces a pair of keys that are inverses, yet each side only knows one part of it. It relies on the fact that not only do RSA keys from the same pair commute, but they can also commute with a different pair. I just wrote some code to demo it this morning.

alice -> bob: alice.pub
bob -> alice: bob.pub
alice: a = (alice.priv * bob.pub)
bob: b = (bob.priv * alice.pub)

Up and down are inverse keys. It's a negotiated asymmetric secret key. Alice can apply a, while Bob can apply b. When they are both applied, they cancel out. So this is asymmetric key agreement. If we tried to do this with RSA, alice or bob would know both keys. But with this, messages for Bob were definitely created by Alice and vice versa.

I discovered this in the context of requiring an application to encrypt a key for us - after it checked that we are authorized for it, and so that the application cannot decrypt the key later - only the grantee. And even though the grantee can get the plaintext key, he can't generate a key that will properly decode for a different grantee. In other words, if signing a key to somebody is authorization, it really isn't up to the grantee to make such grants - the program that knows who is authorized for what must write them.

This is a lot like a Diffie Hellman exchange in that we negotiate a shared secret. The difference is that when we encrypt to the other side, even we can't decrypt it later.

Acyl