> On Sat, 4 Mar 2000, bram wrote: > > > I've written up a public key encryption algorithm I came up with and > > some thoughts on it at > > > > http://www.gawth.com/bram/essays/simple_public_key.html > > If I just send you the final sum, how do you know it was generated > correctly by adding stuff in the public key? does that matter? I don't, and it doesn't matter, but see below. > Also kind of wondering about chosen-ciphertext attacks. > > Here's an idea I just had towards an attack on the system. I'm not > sure it goes all the way through. It depends on the assumption that > there is no way for the decryption routine to tell whether a ciphertext > was correctly formed or not (since that would require solving a knapsack > problem). > > It requires that we have access to an oracle which will decrypt any > ciphertext we like (not necessarily well-formed), but it does not > require that we have any sort of "target" ciphertext. Technically it's > "CCA_1" or a "lunch-time attack." > > [snip details] > > Does this work? I'm not sure, but a simplified version does. The attacker sends a 1 (that's the integer 1), which of course translates to a 0 bit. She then sends a 2, 4, 8, etc. until getting a 1, then proceeds to find p/2 via binary search between the last 0 and the first 1. The problem, as you point out, is that the decrypter can't tell if the input was correctly formed or not, which there is a nice clean way of fixing by modifying the encryption scheme. During encryption, the encrypter has to pick a bunch of random 0 or 1 bits to determine whether to include each of the public key integers in each sum. Rather than doing that randomly, she picks a seed for a standard cryptographically strong PRNG, and uses the PRNG's output to choose whether to include each number. She then includes the seed to the PRNG as the first bunch of bits sent to the decrypter. It is now possible for the decrypter to tell if the input is well formed by re-running the PRNG and seeing if it gives the same totals, so the attack is thwarted. -Bram Cohen
