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

[Noel D. Torres Taño]

Stefan Fendt wrote:
> 
> Hi,
> 
> 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,
> too...
> The only thing I can think of which can't be broken by such a machine
> is a one-time-pad vegeniere with:
> 
>  sizeof(message)==sizeof(key)
> 
>  *and*
> 
>  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...
FALSE!
There is a problem in what you said. Alice KNOWS Bob's key and Bob KNOWS
Alice key. Look simply at this: Bob has the Alice-only ciphered message
and the cleartext, so he can find Alice key. This is not a problem if
the keys are used only once, but this basic error threatens your scheme
completely. A man-in-the-middle will get the three messages, Alice-only
ciphered, Bob-only ciphered and Alice-and-Bob ciphered messages. Using
the AB message and one of the A or B messages, the attacker can find one
of the keys, and using that key on the other one-key message, he'll find
the cleartext.
> 
> 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...
> Hmm...
> 
> What do you think about this? Bad idea, next try?
> 
> Stefan
> 
> _______________________________________________
> Gnupg-devel mailing list
> Gnupg-devel at gnupg.org
> http://lists.gnupg.org/mailman/listinfo/gnupg-devel