From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
Date: Tue, 19 Oct 93 21:17:39 PDT
To: klbarrus@owlnet.rice.edu>
Subject: Unfactorable Polynomial Modulus PKC
In-Reply-To: <9310181535.AA27722@great-gray.owlnet.rice.edu>
Message-ID: <ggl=ebm00VpQAcdWo0@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain


Karl Lui Barrus wrote:

> I beleive the equation leaks information.  When you expand the
> equation symbolically, it is easy to solve for the constants by
> matching the coefficients of the highest powers and working backwards.
> If the constants can be negative as well as positive, the signs of
> some of the terms will reflect this.

You're right.  You know that the x^2 term is (c/2 + 3/8)x^2 so you can
just solve for c from there.  Once you have c, you can solve for c2. 
So, if I could prevent you from finding c, then you couldn't solve it. 
How can I do this?  By adding another constant.

So far, I have just added a constant after each term.  This leaves open
the possibility that I could also add one at the beginning.  (I'll call
the constants A, B and C for simplicity).  Therefore I'd have something
like the following:

F(G(H(x))) where:

F(x) = (1/2)x^2 + (1/2)x + C
G(x) = (1/2)x^2 + (1/2)x + B
H(x) = x + A

Expanding this, we have something which begins:

(1/8)x^4 + ((A+1/2)/2)x^3 + ((3/2)a^2+(3/2)a+b+3/4) + ...

So you can still solve for A, which lets you solve for B, which lets you
break my cipher and find my private key.  But consider the following:

Up to now, I have simply added a constant before and after each nested
term.  I (or you) can easily reverse this process by subtracting the
constant, and then inverting the functions.  I can add an additional
layer of security by multiplying the result of the function by an odd
number and taking the modulus.  As long as I multiply by an odd number
and take the modulus of a power of 2, the process can be reversed.  Now
if I do this at the beginning and after each of the functions I get:
F(G(H(x))) where:

F(x) = (F/2)x^2 + (F/2)x + C
G(x) = (E/2)x^2 + (E/2)x + B
H(x) = Dx + A

Expanding this, I get:

(1/8)fe^2d^4x^4 + ((a+1/2)/2)fe^2d^3x^3 +
(1/2)((3/2)ea^2+(3/2)ae+b+e/4+1/2)fed^2x^2 +
(1/2)(ea^3+(3/2)ea^2+ea/2+2ab+b+a+1/2)fedx +
fe^2a^4/8+fe^2a^3/4+fea^2b/2+fe^2a^2/8+feab/2+fb^2/2+fea^2/4+fea/4+fb/2+c

Picking some random values for A, B, and C, and picking some random odd
numbers for D, E, and F, plugging them into the equation, and then
taking mod 256, I came up with the following:

136.375x^4 + 139.25x^3 + 33.625x^2 + 110.75x + 179

So what values for A,B,C,D,E,& F did I use?  Have fun factoring!  :)