Re: Name this key exchange

From: Kristian Gjøsteen (kristiag+news_at_math.ntnu.no)
Date: 09/16/03 

Date: Tue, 16 Sep 2003 09:31:05 +0000 (UTC)

In article <_Ol9b.12072$tE3.4082995345@twister2.starband.net>,
Roger Schlafly <rogersc@mindspring.com> wrote:
>A was directly inspired by the DH paper. A better question
>is to ask why RSA was invented when DH does everything you want.

RSA is faster than DH at encryption and slower at decryption.
I believe there are cases where that is desirable.

Here is a key transport algorithm that is faster than DH at
encryption and faster than RSA at decryption. Call it a compromise.

Let u, p=2au+1 and q=2bu+1 be primes. Set n=pq and let g be an
element Z_n^* of order u such that gcd(g-1,n)=1. Everything
happens in the group G=<g>.

Alice's public key is (n,g).

Bob generates a secret by choosing a random number r and setting
s=g^r. Then he encrypts the secret as c=s^3, and sends c to Alice.

Alice's private key is d = 3^{-1} (mod u). To decrypt the secret
she computes s=c^d.

This algorithm uses a somewhat special modulus which makes Z_n^*
non-cyclic. As far as I know, there is no way to distinguish such a
modulus from a more general modulus when u is not too large.

As for performance: The secret generation is one exponentiation,
the encryption is practically for free, and the decryption is one
exponentiation.

Compare this with DH in G, which has one exponentiation for the
secret (s=(g^a)^k), one for the clue (c=g^k) and one for the
recovery (s=c^a).

Comparing with DH in a subgroup of F_p^*, you will find that
encryption is rougly twice as fast, and because of the CRT,
decryption is (somewhat less than) twice as fast.

My naive implementations suggest that this is also competitive
with DH using elliptic curves for small security parameters.

This algorithm has obvious analogues in any group where computing
cube roots is difficult. You can also use 2 (or almost whatever)
instead of 3. This may or may not have implications for the
security argument, I haven't worked out all the details yet.

I have a paper on this in the pipeline, but I need to check that it
is new before I bother. 

-- 
Kristian Gjøsteen

Relevant Pages

  • Re: Securing data to a process principal
    ... encryption key first time for the user - and use it later). ... secret. ... I need the decryption to ... You MAY think that instead of a filter driver you can simply ...
    (microsoft.public.platformsdk.security)
  • Re: Symmetric encryption algorithm with group like properties
    ... >> Solutions that exist today are not as secure as they can be. ... I wouldn't expect more than PGP / GPG type encryption, ... > versions - with the key, protected by RSA encryption under a RSA public key ... > Alice needs a secure decryption mechanism to read her emails, ...
    (sci.crypt)
  • Re: Sharing Encrypted Data
    ... > where D stands for decryption and E stands for encryption. ... You can use RSA directly or any ... You could then give your public key ... decryption functions are identical, differing only by the key they use. ...
    (sci.crypt.research)
  • Re: Rabin vs. RSA/ElGamal
    ... the speed difference between RSA ... encryption and Rabin encryption probably is irrelevant. ... What DOES takes the time is decryption. ... This also doesn't change the fact that Rabin encryption is still a lot ...
    (sci.crypt)
  • Re: RSA vs DH
    ... DHencryption is very much slower than RSA encryption. ... DHdecryption is about twice as fast as RSA decryption. ... Unless you use canned primes for DH key generation, ...
    (sci.crypt)