Re: crypto technique

[Matthew J Ghio <mg5n+@andrew.cmu.edu>]

Timothy C. May <tcmay@netcom.com> wrote: 

> But what you need for crypto is a _trapdoor_ one-way function, one for
> which a very fast (but secret, of course) inverse does exist. In RSA,
> the knowledge of the originally chosen primes p and q allows the
> "owner" of the public and private keys to quickly decrypt a message.

Ah...  but I do have exactly such a "trapdoor".  Consider the output
produced by y = 0.5x^2 + 0.5x:  (p=2^3)

      y mod 8
x y  in binary
- -- ---------
0  0    000
1  1    001
2  3    011
3  6    110
4 10    010
5 15    111
6 21    101
7 28    100

Note that the last digit of the binary number repeats every four
numbers. From only the last number, I know that x mod 4 must be only one
of two values.  By looking at the second to last binary digit of y, I
can narrow my list further, by deducing that x mod 8 could only be one
of two values. I can then test those two values and determine x.
For example: Suppose I am given the value 1101 and p=16.  I first try
x=0.  That gives me zero, so that must be wrong.  I try x=1, and I get a
1 for the last digit.  That macthes what I have.  So next I try x=1 and
x=2.  x=1 goves me 01, so that's right. Next I try x=1 and x=6. (6
because 2^3-1=7, 7-x=6)  x=1 gives me 001, that's not it.  6 gives me
101, which is what I'm looking for.  Finally I try 6 and 9.  (because
2^4-1=15 and 15-6=9)  6 gives me 0101, which isn't it, so I try 9, which
gives me 1101.  So the answer is x=9.  (and in fact, .5(9)^2 + .5(9) =
.5(81) + .5(9) = 45, which in binary is 101101; mod 16 = 1101 , which is
what we started with.)  So the inverse does exist and can be solved with
relativly few calculations.  I suppose this is what L. Detweiler was
referring to, am I correct? 


Now, the public key part of the system:


Previously, I posted the following sample polynomial:

         4      3         2
y = .125x + .25x + 63.875x + 63.75x + 8159


Karl Lui Barrus quickly pointed out how easily he could solve it.  (I
really only intended it as an example, so I didn't try to make it too
difficult.)  But since we now have the values, I'll go ahead and use
this example again to show how to actually solve it, and point out ways
it could not be solved.

Since we have C=127, D=31, we can solve for any x, given y and p.  I
didn't give a value for p earlier, so let's use p=256 (one byte
encryption.  Of course this could be brute-force attacked, but let's
keep the math simple for this demonstration.)

Suppose we have y=61.  To solve for x, we first subtract D, conevert to
binary and solve with the above method.  To save space, I won't go into
the calculation here, but go ahead and try it yourself if you want.  You
should come up with 172.  This can be checked easily: (172^2)/2 + 172/2
+ 31 = 29584/2 + 172/2 + 31 = 14792 + 86 + 31 = 14909   Taking 14909 mod
256, we get 61, so it checks out.

Next we do the same step again, starting with y=172.  I fairly quickly
solved this to get x=9.  Nine is, in fact, what was put in originally. 
This can be shown by:

          4      3         2
y = (.125x + .25x + 63.875x + 63.75x + 8159) mod 256

            4        3           2
y = (.125(9) + .25(9) + 63.875(9) + 63.75(9) + 8159) mod 256

y = (.125(6561) + .25(729) + 63.875(81) + 63.75(9) + 8159) mod 256

y = (820.125 + 182.25 + 5173.875 + 573.75 + 8159) mod 256

y = 14909 mod 256

y = 61


Note that none of the preceeding could have been done without knowing
the values of C and D.  So if Karl Barrus can find C and D using his
clever factoring technique, does that defeat the system?  Actually,
Karl's trick is easy to avoid.  Since the entire polynomial is mod 256,
we can mod each term by 256.  Which gives:

          4      3         2
y = (.125x + .25x + 63.875x + 63.75x + 223) mod 256

which still produces the same values for y, but the factoring technique fails.

One other question which could be asked is, does the technique for
calculating roots of moduli work for the entire polynomial?  A view of a
sample of numbers reveals that it does not:

x  y  binary y
- --- --------
0 223 11011111
1  95 01011111
2  98 01100010
3 238 11101110
4  12 00001100
5 200 11001000
6  49 00110001
7  89 01011001

which reveals no repeating patterns in the last digits (or any digits).


In summary, I see no method which would yeild the original input without
knowing the values added to the nested polynomials (the private key),
and there is no way to determine the private key if the modulus is
applied to the resulting function.

P.S. I could beat the RSA system too, if the modulus was left out. :)