quantum computing?!? Or, I don't want anyone to read my eMails... never.

Stefan Fendt stefan at lionfish.ping.de
Mon Dec 30 14:10:10 CET 2002


just before anyone asks... well, I don't regard quantum computing to
be possible in the next few years/decades, but I belive it's a matter
of fact, that it will be possible in the nearer future...

As it seem's to be possible to break any "hard problem" on such a
machine (may it be prime-factoring, discrete logarithms or eliptic
curves) I asked myself what those machines can't break (and can be
created with a normal computer) and I wonder if anyone else does so, 
The only thing I can think of which can't be broken by such a machine
is a one-time-pad vegeniere with: 



 the key being totaly random

It's simple to implement but not to use as you need to transfer large
keys in a secure way from Alice to Bob... I thought a long time over
this and I belive I found a solution for the key-exchange-problem. As
Vegeniere can be implemented cumutative as

ciphertext[x] = cleartext[x] XOR randomkey[x]

Alice could do the following (which is not new, I guess...):
Alice generates a random key of exactly the size of the message and
ciphers the message with that key and sends it to Bob. Bob ciphers it
again with his own random key and sends the ciphertext back to Alice.
Now Alice deciphers the message using their key and sends it to Bob
again. At this stage the ciphertext is only locked by Bob's key, who
can regain the message by deciphering with his own key. This way Alice
doesn't know Bobs key and Bob doesn't know Alice's so can't Eve know
any of the keys...

This should be easy to implement and has several drawbacks...

1. We need to transfer 3 times the amount of data needed if we were  
using any public-key scheme and 

2. We, if things turn out to be bad, can't know that Alice really is
talking to Bob and not accidently to Eve...

I don't think that 1 should be a problem as emails tend to be short
but I would like to get rid of 2 without compromising the security...

What do you think about this? Bad idea, next try?


More information about the Gnupg-devel mailing list