crypto technique

I was recently doing a calculation involving polynomials when I noticed
the following: 

The function:


      1  2   1
y = ( - x  + - x + C ) mod P
      2      2

where C is any integar constant, and P is any integral exponent of 2,
given any positive integer less than P as input in x, will produce a
unique positive integer output in the same range, [0,P).  Hence we have
an encryption technique which works well for binary data.  Decrypting
this is a bit trickier.  It is possible to find the inverse equation for
this, (without the modulus) which is: x = SQR(2(y-c) + 1/4) - 1/2
(SQR=Square root)  Finding the square root of the modulus is the tricky
part, but it is possible, since for every number it is possible to add
some multiple of P and find a rational square root (There is a fairly
systematic way to do this; I don't want to bore you with the math right
now, I'll go into it later if anyone wants.  Just trust me for now; it's
possible to do without too much computation.)  Now, there are some ways
to beat this if you were encrypting one byte at a time, such as looking
for recurring spaces in ASCII text, but if you were to group 8 bytes
together and set p=2^64, it would be fairly difficult to crack.

Anyway, in case you're getting bored, here comes the fun part:

What happens when we double-encrypt with this technique?  Well,
obviously you need to use both keys (both values of C) in order to
unencrypt it.  For encrypting tho, we have a nested function of x:

    1   1  2   1        2   1   1  2   1
y = - ( - x  + - x + C )  + - ( - x  + - x + C ) + D
    2   2      2            2   2      2

where D is a second constant.  This multiplies out to a fourth degree
polynomial which can not be easily factored to find it's orininal
components.  Adding a third layer of encryption creates an eighth degree
polynomial which is hopelessly beyond factoring in any reasonable amount
of time.  Hence, it is impossible to determine the decryption key if one
has the encryption key.  Therefore, the multiplied polynomial can be
distributed as a public key, and the inverse functions needed to decrypt
are kept secret (private key).

Has this ever been tried before?  Has it been broken?  I don't see any
way to break this, but I could be overlooking something.  If this works
it seems like it might be simpler to generate keys for than RSA.

I wrote out an example of this on paper here, picking some values for C,
and got:

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

and I was able to find values of x for values of y.  Go ahead, post a
number, I can decode it (can you?).  Oh, don't forget to say what P is.
:)

P.S.  In case you're wondering where that function came from, and why it
always produces integars, it's a representation of the series
1+2+3+4+5...

Matthew J Ghio wrote:

>
>    1   1  2   1        2   1   1  2   1
>y = - ( - x  + - x + C )  + - ( - x  + - x + C ) + D
>    2   2      2            2   2      2
>
>         4      3         2
>y = .125x + .25x + 63.875x + 63.75x + 8159
>

By expanding the equation above (the top one), I got this:

y = 1/8*x^4 + 1/4*x^3 + (3/8 + c/2)*x^2 + (1/4 + c/2)*x + (1/2*c + 1/2*c^2 + d)

and by matching powers, got the following equations:

c/2 + 3/8 = 63.875

1/2*c^2 + 1/2*c + d = 8159

These equations are easily solved for c = 127, d = 31.  From there, I
can compute the required inverse equations, and so on.

I'm not too sure about the security of this method; it seems it
boils down to solving simultaneous equations, which yield the constant
terms.  And you even know how many nested equations there are from the
power of the leading term.

But, as a test, post a harder one (maybe four or more nestings) and
see if I can get it!

-- 
Karl L. Barrus: klbarrus@owlnet.rice.edu         
keyID: 5AD633 hash: D1 59 9D 48 72 E9 19 D5  3D F3 93 7E 81 B5 CC 32 

"One man's mnemonic is another man's cryptography" 
  - my compilers prof discussing file naming in public directories

Matthew,

From what I can tell from your description, you (may) have created a
"one-way function." Nest enough terms and you indeed have a function
that is difficult to invert.

Cellular automata do the same thing...crunch for several generations,
and the inverse is very hard to find. (BTW, Steven Wolfram was once
touting cellular automata as an ideal encryption scheme. Indeed,
running a linear CA on a string can scramble it quite a bit. The
problem is that inverses cannot be easily found, and if they can, so
can the opponent. Also, someone later showed that CAs are essentially
equivalent to linear feedback shift register (LFSR) schemes, which
have been analyzed and are not P-K systems. I'm not saying your scheme
is the same, though.)

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.

Anyone who does not know the p and q values cannot compute the inverse
in the ring (p -1)(q - 1), and so must try to factor n to find p and q.

In your scheme, a message may be easily turned into a jumble (as with
a cellular automata, an LFSR, etc.), but how will it be unjumbled
easily? If you can compute the inverse, so can anyone else.

The RSA scheme allows the owner to compute an inverse in a very clever
way, using number theory. I don't see how your systems allows this.

I could be missing something basic about your idea.

(And, in any case, I really like that you are trying to come up with
new schemes.)

-Tim May

-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power: 2^756839 | Public Key: PGP and MailSafe available.
Note: I put time and money into writing this posting. I hope you enjoy it.

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. :)

Matthew J Ghio wrote:

>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.

I've been thinking about this (well, not too much since I'm in the
midst of midterms week :-).

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.

We know the magnitude of the constants must be less than P, which is
public.  But can they be negative - will the decoding process still
work?  Or, will you obtain the correct decoding for the correct choice
and an incorrect decoding for the incorrect choice?  If it turns out
that either choice will decode a number to the same value, or if the
decoding won't work with negative numbers, then this method is too
easy to invert.

If the constants can't be negative, or if they can be but it doesn't
make a difference in the decoding, then taking the modulus doesn't
obscure anything at all.

For example, suppose c = 127 and d = -225.  Then

y1 = 7903. + 63.75 x + 63.875 x  + 0.25 x  + 0.125 x

which becomes (after mod 256)

y1 = 223. + 63.75 x + 63.875 x  + 0.25 x  + 0.125 x

However, if c = 127, d = 31, then

y2 = 8159. + 63.75 x + 63.875 x  + 0.25 x  + 0.125 x

which becomes (after mod 256)

y2 = 223. + 63.75 x + 63.875 x  + 0.25 x  + 0.125 x

So y1 = y2.  Here, d = -225 and d = 31 yeild the same equation (after
mod operation).  

Now I need to try the decoding process to see if d = -225 or d = 31
yeild the same or different answers.

-- 
Karl L. Barrus: klbarrus@owlnet.rice.edu         
keyID: 5AD633 hash: D1 59 9D 48 72 E9 19 D5  3D F3 93 7E 81 B5 CC 32 

"One man's mnemonic is another man's cryptography" 
  - my compilers prof discussing file naming in public directories

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!  :)

Karl Lui Barrus wrote:

> We know the magnitude of the constants must be less than P, which is
> public.  But can they be negative - will the decoding process still
> work?  Or, will you obtain the correct decoding for the correct choice
> and an incorrect decoding for the incorrect choice?  If it turns out
> that either choice will decode a number to the same value, or if the
> decoding won't work with negative numbers, then this method is too
> easy to invert.
>
> If the constants can't be negative, or if they can be but it doesn't
> make a difference in the decoding, then taking the modulus doesn't
> obscure anything at all.

Moduli are always positive.

It is interesting to note that since x^2 mod y = (-x)^2 mod y, then
x^2 mod y = (y-x)^2 mod y.  So whenever you have a square root modulus,
you have at least two numbers in the domain which will produce the same
outcome.

Matthew J Ghio wrote:

>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.

I still don't know about that - I think all it does is remove the
problem one step from immediately solvable.

Is that P term public knowledge (here P = 256)?  If so, the revised
equations are:

c1/2 + 1/4 = 63.75   ===> c1 = 127

c1/2 + 1/4 x1^2 + c2 = 223 + 256k  ===> c2 = -7905 + 256k

And this will yeild either c2 = -225 or c2 = 31.  The computational
expense of trying both is small.

If it does turn out that the magnitude of the constants must be less
than P, I don't think taking the mod of each coefficient obscures the
problem very much at all.  It still boils down to solving systems
of simultaneous equations, which isn't the same complexity as solving
discrete logarithms or factoring.

-- 
Karl L. Barrus: klbarrus@owlnet.rice.edu         
keyID: 5AD633 hash: D1 59 9D 48 72 E9 19 D5  3D F3 93 7E 81 B5 CC 32 

"One man's mnemonic is another man's cryptography" 
  - my compilers prof discussing file naming in public directories