1993-10-16 - crypto technique

Header Data

From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
To: cypherpunks@toad.com
Message Hash: 1acca439d5db8994a385ee7a235452453ee6e67c83559eccc419c44ea8b9fc04
Message ID: <Agk4mNS00awY5cHkQU@andrew.cmu.edu>
Reply To: N/A
UTC Datetime: 1993-10-16 19:37:18 UTC
Raw Date: Sat, 16 Oct 93 12:37:18 PDT

Raw message

From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
Date: Sat, 16 Oct 93 12:37:18 PDT
To: cypherpunks@toad.com
Subject: crypto technique
Message-ID: <Agk4mNS00awY5cHkQU@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain


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





Thread