Newsgroups: sci.crypt
Path: sparky!uunet!cs.utexas.edu!asuvax!ncar!sage.cgd.ucar.edu!prz
From: p...@sage.cgd.ucar.edu (Philip Zimmermann)
Subject: Colston's Quick Public Key scheme
Message-ID: <1992Jun28.040947.7642@ncar.ucar.edu>
Summary: Fast public key algorithm
Sender: ne...@ncar.ucar.edu (USENET Maintenance)
Organization: none
Date: Sun, 28 Jun 1992 04:09:47 GMT
Lines: 387
I'm posting this document for a friend, David Colston, who does not
have access to Internet. If you have any comments, you can reply
directly to him via phone, or snail mail, or you can reply to me and
I can forward your comments to him (but not as fast).
His article refers to some software he developed, which can be obtained
directly from David Colston.
-Philip Zimmermann
Article follows...
--------------------------------------------------------------------
QUICK PUBLIC KEY (Q.P.K.) v. 1.0
Copyright 1992 By Colston & Associates, Inc.
If you hate math skip down to the useage section.
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
Variables in capital letters are permanent and those in small letters
are temporary.
BACKGROUND
Because the "secret key" function of RSA is so slow, most
cryptographers use the RSA function 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. Here is an idea on this
subject. 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. The range of message sizes is described below, but generally
speaking we a discussing messages less than SQR(Q) in actual size.
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 Q.P.K. KEY 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. Q.P.K. Uses L = 3.
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))
I have been told that this idea is based on Rabin and Williams. I will
leave that decision to the reader. The point is that it involves a
NON-MODULAR SQUARE ROOT and is therefore much faster than
exponentiation modulo N. If this algorithm is Rabin, it's in the
public domain. If it's not Rabin, but mine, I hereby place it in the
public domain.
The Q.P.K. program uses this approach to send 4 large "random number
seeds". The seeds are used by a conventional decryption algorithm.
This conventional key is like a huge "tear sheet" for entire N sized
blocks of code. New random are used for each send and receive
secession. This is fairly quick stuff, after initialization (although
I do admit there are faster algorithms). How does it work? Think of
two rows of numbers, with each row having (N - 1) numbers. Each row
has a random value for the first number of the row and each subsequent
number is determined by adding a random constant to the previous value
(a different constant for each row and modulo N, of course). Find your
message in the first row. Send the number at that has the same
location in the second row. The receiver finds out the position of the
number you sent in row two and "looks" up the corresponding value in
the first row. Even knowing one row is not enough to decrypt the
message. If N has 64 bytes, then each block of 64 characters which are
sent can have (N - 1) or about 2 ^ 512 possible values. A change in
only one bit of the block will change the entire output block.
To summarize, any value sent for a message can be 0 to (N-1) and each
has an equal chance of being the correct value. Just in case we're
sending the same block of characters over and over again, (ie. pages
of spaces) two characters in each block are dummies. The first
character in each send block tells the receiving program which other
character is null.
Mathematically it works this way:
R1 = Random Seed 1
R2 = Random Seed 2
R3 = Random Seed 3
R4 = Random Seed 4
IR2 = R2 ^ -1 modulo N
IR4 = R4 ^ -1 modulo N
ENCRYPT:
M = Message.
C = Cipher_text.
(IR2 * (M - R1)) modulo N = Message_Index
NOTE: Message_Index + 1 = the position at which M falls in the first
row.
C == (R3 + Message_Index * R4) modulo N
NOTE: C is the number which occupies the same position in the
second row that M occupies in the first column.
DECRYPT:
(IR4 * (C - R3)) modulo N = Message_Index
NOTE: Message_Index + 1 = the row on which the cipher text falls in
row 2. It was previously unknown to the receiver.
M == (R1 + Message_Index * R2) modulo N
PROGRAM USAGE
The Start File is labeled "QPK.EXE" amazingly enough. There are a
total of seven executable files. QPK.EXE, MAKEKEY.EXE, MAKEKEY2.EXE,
MAKEKEY3.EXE, PUBSEND.EXE, PUBGET.EXE, AND BRT71EFR.EXE. The Program
assumes that all of these files are in the same directory.
QPK is menu driven. It does not have all the features that I would
like, just yet. It is intended primarily as demonstration code, but it
works well as a public key system. If enough people are interested, I
will include an "electronic signature" in the next edition. That way
you can not only get messages that you alone can read, but you can
know for sure who sent it. If you don't understand what a public key
is, it's sort of an "eyes only" message. After you have generated your
own random key from the Q.P.K. menu. You can receive messages from
anyone who has your public key that only you can interpret (or decrypt
as a cryptographer would say)!
How, because each public key has a secret key, which is associated
with it and you are the only one with the secret key. Conversely, if
you have someone else's public key, your can send a message file,
which only they can decrypt, To make sure of this you must do only
three things:
1) PROTECT YOUR HARD DISK (AND BACKUPS) AND DON"T GIVE ANYONE YOUR
MYKEY.SEC OR MYKEY2.SEC FILES!
2) Make sure that anyone that you wish to receive messages from
has YOUR public key file and a copy of QPK. Use the main QPK
menu to place your key in another file, for example - JOHN.PUB.
COLSTON.PUB is include with this offering.
3) You public key is placed in KEYLIST.PUB as the first key when
your secret key is generated. (IF YOU HAVE AN OLD KEY IT WILL
BE OVER WRITTEN IN KEYLIST.PUB, MYKEY.SEC, AND MYKEY2.SEC. The
key will have your name, the date the key was generated, and a
number which is associated with that key. Be sure the person
who wishes to send you a message has the key number, key date,
and your name as entered for key generation, so that a
substitution cannot be made. This prevents someone else from
substituting a "fake key" that they generated, pretending to be
you, and getting confidential messages really intended for YOU.
You may use this program for free, as well as the all the source code
(Q.P.K. is written in Microsoft (R) Quick Basic V 7.1) for any
non-commercial purpose. If you wish to be on a mailing list for
updates, write to: Colston and Associates, Inc.
5111 Rogers Ave. Suite 507
Fort Smith, AR 72703
Day phone (501) 452-4948
Home (501) 785-2208
In addition to writing or calling the above address, you may reach me
by E-Mail for questions or to make comments: c/o Charles Merritt
7120...@compuserve.com Bix User I.D.- charliemerritt (for those of
you on BIX)
I am available for consultation for commercial applications (for a
fee). Fellow hackers can communicate with me for free. If you wish to
send me a public key message, my public key is included as
COLSTON.PUB. My name is listed as Colston, C. David 05-30-1992 Key#
3,667,255. Use the QPK Menu to add it to KEYLIST.PUB after you have
generated you own public key.
The author of this program makes no warranties about it's performance.
The program is not heavily error trapped, so you could make it "blow
up". Any blow up would not compromise any message that you wish to
send, however, at most it will merely not send the message or garble
it beyond all recognition. Of that I have made very sure, but you can
always tell the computer to do something impossible (such as request
files which are no where to be found). Yes, I error trapped for that,
but after 10 years of writing computer programs, I've learned that
people can always surprise a programmer and find a way to do something
he/she never conceived.
ABOUT THE SOURCE CODE
As I have already stated the source code is in QUICK BASIC 7.1. I
wrote it in basic to prove how fast the public key decryption is
compared to other methods. It also will hopefully end the joke about a
"math pack" written in basic. This code is not very neat, I have not
had time to go back and make every routine consistent from module to
module. It is also not heavily remarked. If you have questions please
feel free to get in touch with me.
Big numbers in Q.P.K. are treated as long integer arrays, but only
part of the bits in each member of the array are used. The routines
assume (in most cases) that an incoming array represents a large
number in base 4096 (2^12). In other words, if the number represented
is 4096 and the array is A&(), then A&(2) = 1 and A&(1) =0. 4097 would
be A&(2) = 1 and A&(1) = 1. If you think naturally in base 10 like
most people, then you could place the number in the array in groups of
three base 10 digits. (Think of each group of three digits as being
separated by a comma.) Thus 9,123,746 in base 10 can be placed in the
array as A&(3) = 9, A&(2) = 123, A&(1) = 746. You may then call the
convert base routine:
ABytes%=3
OldBase% = 1000
NewBase% = 4096
ConvertBase A&(), ABytes%, OldBase%, NewBase%
This will convert the array to base 4096. The array would return as:
A&(3) = 0, A&(2) = 2227, A&(1) = 1954. ABytes% would return as 2. You
may then use any other math routine in the source code.
I have included routines that add, subtract, multiply, divide, square
root, modulo, exponentiate modulo, increment (add one), decrement
(subtract one), find the multiplicative inverse of two big numbers, do
Chinese remainder, covert the base, display a number in base 10, and
find the square of x in a way that is 40% faster than multiplying X *
X (Thank you, Joel Benston!). QPK routines are set up to "crunch"
number up to 2 ^ 2070, but you may change the dimension statements to
A&(256) and it should handle 2 ^ 3072. To give you some idea how big
such numbers are, 2 ^ 1024 has about 309 decimal digits and 2 ^ 3072
would have about 927 decimal digits!
ABOUT PUBLIC KEY PATENTS
It is my firm belief that everything which is contained in the program
is in the public domain, was developed by me, or use of an idea by
conceived by someone else has been granted to me by appropriate
authority. It is clear that this is NOT the RSA public key. RSA uses
exponentiation modulo a number to achieve a public key decryption AND
Ron Rivest has decried Rabin's squares modulo N for years. As I've
said before, I think it's entirely mine, but, if it's not, it's much
closer to RABIN than RSA.
When Phil Zimmermann came out with P.G.P. last year, many people
refused to use it for fear of violation of patent law. This program is
not in violation of any law of which I am aware.
One final note. This program is not compatible with any other program
on the market or which is widely used, including P.G.P. by Phillip
Zimmerman. You must give a copy of Q.P.K. to anyone you wish to
communicate with.
ABOUT Q.P.K. SPEED
This program was compiled to be used even by a 8086 machine. You may
recompile far any higher chip, if you wish. If you do not recompile
all modules to stand alone files, you must use your own version of
BRT71EFR.EXE to assure that the program will perform adequately. The
program does FIVE secret key decryption for a 512 bit public key in
about 8 seconds on an 8086 machine. It is algorithmically twenty times
faster than R.S.A. decrypts from conventional key. I think that it can
be optimized to be even faster.
Even though Q.P.K. is fast. It is only as fast as your computer. The
conventional key routine will encrypt and decrypt at about 10 to 20
characters per second on an 8086 machine (AFTER THE SET UP AND
DEPENDING ON KEY SIZE). It will be six times faster on an 80286 and
faster still on higher level chips.
PUBLIC/SECRET KEY GENERATION TIMES
FOR AN 8086 THE FOLLOWING TIMES ARE AVERAGE BUT MAY VARY WILDLY:
512 bit key - 45 minutes.
768 bit key - 2 hours.
1024 bit key - 6 hours.
An 80286 will divide these times by a factor of 6. I have not tried
this on an 80386 or 80486 machine. If you have a copy of QUICK BASIC
7.1 and wish more speed, the recompile the source code accordingly. It
was compiled for the lowest common denominator, an 8086.
SPECIAL THANKS (I.O.U.)
O. Joel Benston, Charlie Merritt, and John Ewbank, the original public
key encoders for P.C. Many of their concepts are in Q.P.K., especially
Joel. Thanks to Phil Zimmermann for moral support! In addition, I wish
to thank Euclid, Fermat, Gauss, Wilson, Euler, Jacobi, Rabin, and
Williams for inspiration.
C. David Colston (Colston and Associates, Inc.)
05-31-92 O.K. to post!