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
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."
Denote "decryption of string s" by D(s).
1) Create our 'base ciphertext' b by picking k numbers from the public
key and summing them. We know that this is congruent to something
less than p/2 mod p. So we know if we ask for D(b), we get 0.
2) Now we are going to add powers of 2 to b and then ask for the
decryptions of each intermediate value u_i. The idea is that we
are looking for the point at which D(u_i) switches from 0 to 1.
Then we are going to subtract powers of 2 from b and then ask
for the decryptions of each intermediate value v_i. The idea
is that we are looking for the point at which D(v_i) switches
from 0 to 1.
We know that p and therefore p/2 are less than any number in k.
So we should only need to add powers of 2 for log (the least
number in k) times at most before seeing a switch.
3) When we see a switch in D(u_i) from 0 to 1, we know an upper bound
on (p/2 - b) mod p.
When we see a switch in D(v_i) from 0 to 1, this means we "wrapped
around below". So now we have an upper bound on the size of b mod p.
If you can figure out exactly what b mod p and (p/2 - b) mod p are,
you add them together and get p/2 . Once you have p/2, you have p and
that's the private key. That's the part I'm not sure about just yet.
I think once you see a switch bewteen D(u_k) and D(u_k+1), you should
do something like ask for the decryption of the average, and then
see whether you need to go higher or lower based on that. Since you
will be halving the distance to the "real" value of b or (p/2 - b)
each time, this seems like it will be efficient, but I haven't
worked it out.
Does this work?
Thanks,
-David Molnar
