PKZ and NON-RSA

[David Colston]

When I posted the offer for source code to a non-RSA public key
yesterday, little did I know that I would be beseiged by requests.
I will therefore send the paper on the matter to cypherpunks and
ask that anyone wanting a copy of the source send me a floppy. 
Any size or density is okay.

As a preamble to this paper, I'd like to note why and how it was
developed. After the first release of PGP, Phil told me he was 
worried about using RSA. I offered to come up with another scheme
and originally designed a version of Rabin. I asked Phil to post
a copy of that paper on sci.crypt since I do not have internet
access. There were few responces, none of which attacked the 
safety of the method, but mainly stated that it was a version of
Rabin.

Nothing was ever done with that proposal. A year latter, 2.0 PGP
was due to be released and I came up with the current public key
system. Again, Phil ignored it. Posts on sci.crypt were totally
ignored by anyone with the ability to judge the math. Phil was
then approached by the customs folks and I recieved a call from
him in December of last year. By that time I was tired of waiting
around for Phil and had coded QPK (Quick Public Key) in PDS 7.1.

At any rate, I suggested that Phil foward a copy of the program to
RSA and see if they would challenge that program in court. He
declined. It became apparant that Phil wanted to stick with the
original RSA concept and would refuse to do anything with another
approach, although he did stick an bite in 2.1 to flag an encryption
as being non-RSA.

At any rate, I believe that RSA would not attempt to defend the 
original public key patent in court, since it smacks of over kill.
They attempt in the RSA pattent to claim any encryption method 
involving a polynomial modulo another number. This is clearly prior
art, since Ceaser used m+1 mod n as an encrytion method.

The program I generated has been posted on Compuserve, Bix, and GEnie
for over a year with no feed back from anyone, even though I am
resonably sure that RSA is aware of its existance. They have not
challenged it because there has been no publicity. I would welcome
a court challenge on the whole idea of crypto patents. The customs
thing is meerly a way for RSA to challenge Phil and scare off others
while avoiding a test of their patents.


The "paper" follows.




   FOR THE MATHEMATICALLY ORIENTED - HOW A QUICK PUBLIC KEY WORKS.

Math notation:
+                 plus
-                 minus
+-                plus or minus
*                 multiplication
/                 division
^                 exponent
<>                unequal
=                 equals
==                congruent
<                 less than
>                 greater than
INT               truncated integer round
SQR               square root
(                 open expression
)                 close expression
x^-1  modulo p    the multiplicative inverse of x in the field of p
x... y            the range of values
XOR               exclusive or
N                 a number equal to P times Q, where P and Q are prime

Variables in capital letters are permanent and those in small letters
are temporary.

                              BACKGROUND

Because the "secret key" function of many public keys  methods are so
slow, most cryptographers use these functions only to "boot strap"
into a conventional key system, which is faster to send the actual
message. Most of the conventional key systems use comparatively small
numbers in relation to the size of the public N as a "random seed
number". The holder of the secret key may actually have a larger
amount of computer time to decipher the starting point of the
conventional algorithm than to decipher the actual message. It would
seem to be a good idea, if a public key function could take advantage
of the actual message size required to speed up the public key
process. The range of message sizes is described below, but generally
speaking we a discussing messages less than SQR(Q) in actual size.

Imagine a series of related equations modulo a prime, P. These
equations have the formula ((e * e + e)/2 * L + C) modulo P. The
value, C, is a constant determined by the rule (L - 1) * (1 / (2 * L))
modulo P == C. For L = 1, C = 0. Therefore, if L is known, the
expression ((e * e + e)/2) modulo P may be determined, even if e is
unknown.

Each value of L has an area or series of areas, in which the value of
e becomes discoverable, WITHOUT resorting to a modular square root.
ie. Let r == ((e * e + e)/2 * L + C) modulo P. If e is in the correct
range relative to L, then (r * L * 8 + (L - 2) * (L - 2)) will have an
integer square root and the value, e, may be determined with ease. The
range of values of e, for any value of L, which have this property and
the location of those values vary greatly. The following illustrates a
public key approach for L = 12, but other values of L may also be
used. Perhaps I should also note that the particular L, which a secret
key holder uses need not be public knowledge, but is not all that
sensitive.

       ESTABLISHING A QUICK PUBLIC KEY (Q.P.K.) BASED ON L = 12

A person wishing to receive public messages, which he/she alone can
decrypt calculates N = P * Q. Where P and Q are a randomly selected
prime numbers, Q being the larger.

A == (11 * 24^-1 ) modulo Q
B == (2 * A) modulo Q
D = Q - B
If D > (Q - 1)/2 then set D = Q - D - 1.
F = (Q - 1)/2 - D

NOTE: We may chose to use the F for all of the following calculations
      instead of D. This applies to no value of L lower than 12 and F
      is not valid for most sequences higher than 12. F may be an even
      safer value to use, for reasons which are too long to discuss
      here. L is NOT super-sensitive information.

Let Y1 ... Y2 be a range of numbers with in the limits:
(D - k) and (D + k), where k = INT(SQR(2 * Q / 12)).  Y1 may be
randomly selected from any point in this range, but Y2 may not be
larger than (D + k), and Y2 - Y1 is the maximum message size.

A message range for N, public information, is then created by using
Chinese remainder theorem to find the modular intersection Q == Y1
and P == x, x being a random number in the range x > 0, x < P.
This intersection is called S. A check is made to verify the
following:

A' = (11 * 24^-1) modulo N
B' == (2 * A') modulo N
D' = N - B'
If D' > (N - 1)/2 then Set D' = N - D' - 1
NOTE: P, Q, D, F, Y1, Y2, k, A, AND B are secret values.

                          Q.P.K. ENCRYPTION

A public key for short messages consists of S and N.

To send a Message the sender calculates:
e = (S + Message)
((e * e + e)/2) modulo N == Cipher

                          Q.P.K. DECRYPTION

t ==  Cipher modulo Q
f == (t * 12 + A) modulo Q
g = SQR(f * 8 * 12 + 100)

NOTE: If g is NOT an integer value, the message is rejected as
      invalid. If g modulo (2 * L) <> (L - 2) then Q is repetitively
      added to g until g modulo (2 * L) == (L - 2).

z = (g - 10)/24
e == ((B - 1) + z) modulo Q
If e > (Q - 1)/2 then set e = (Q - 1) - e.
Message = e - Y1

For other values of L:
A == ((L - 1) * 2^-1* L^-1)) modulo Q
k = INT(SQR(2 * Q / L))
NOTE: If L = 1 then D = 0 and the message range is 1... k.
      If L = 2 then the message range is D... (Q - 1)/2 and these
      values modulo Q are already perfect squares < Q.
f == (t * L + A) modulo Q
g = SQR(f * 8 * L + (L - 2) ^ 2)
z = (g - (L - 2)/(L * 2))

If anyone wants the source code for this drop a disk to:

Colston & Associates
5111 Rogers Ave. Suite 507
Fort Smith, AR 72903