Path: gmdzi!unido!mcsun!uunet!cs.utexas.edu!asuvax!ncar!sage.cgd.ucar.edu!prz
From: p...@sage.cgd.ucar.edu (Philip Zimmermann)
Newsgroups: sci.crypt
Subject: New public key scheme, maybe
Message-ID: <12044@ncar.ucar.edu>
Date: 7 Jul 91 19:32:38 GMT
Sender: ne...@ncar.ucar.edu
Reply-To: p...@sage.cgd.ucar.edu ()
Organization: Climate and Global Dynamics Division/NCAR, Boulder, CO
Lines: 166
A friend of mine has what may be a new public key scheme. It seems to
work. Is it really new? His paper follows.
--Philip Zimmermann, p...@sage.cgd.ucar.edu
-------------------------------------------------------------------------
Page 1
THE CRYPTOGRAPHIC USES OF POLYGONAL SEQUENCES
By C. David Colston
INTRODUCTION
Polygonal sequences are a series of numbers that are generated by
offset addition to the previous members of the sequence. The lowest
order of these sequences (other than sequence zero or 1, 2, 3, 4 ,5...
etc.) is the triangular sequence. It is created by taking the starting
number 1 and offset of 1, constantly adding 1 to the offset, and
summing the result. 1 + 2 + 3 + 4... are added, resulting in the
numbers 1, 3, 6, 10...
The next sequence is the square sequence in which offset is
increase by two each time, 1 + 3 + 5 + 7... This results in the
numbers 1, 4, 9, 16... The third sequence (a pentagon) increases the
offset by three each time 1 + 4 + 7 + 10 ... and it results in the
numbers 1, 5, 12, 22... These sequences are called polygonal because
the resulting numbers can be ordered into rigid geometric shapes.
Examples:
1 1 4 9 16
2 3 (Triangle) 2 3 8 15 (Square)
4 5 6 5 6 7 14
7 8 9 10 10 11 12 13
CALCULATION OF POLYGONAL NUMBERS
Because offset counting and addition is a cumbersome process it
is helpful to note that any member (M) of a given polygonal sequence
(PS) may be calculated by the following formula:
(M X M + M)/2 + (PS-1) X ((M-1) X (M-1) + (M-1))/2
It is also helpful to note that (PS + 2) is the number of sides in the
resulting polygonal sequence.
The formula resolves as follows for the first four sequences:
Triangle: (M X M + M)/2
Square: M X M
Pentagon: (3 X M X M - M)/2
Hexagon: 2 X M X M - M
THE MODULAR RESIDUE OF POLYGONAL NUMBERS
Polygonal sequences have ordered properties modulo a prime
number. On the next page is a complete set of the modular residue of
the first 23 polygonal sequences modulo the prime 23. The horizontal
columns are, from left to right, the sequence members from 1 to 23.
The rows from top to bottom are the polygonal sequences from 1 to 23
and are numbered from 1 to 23 accordingly.
______________________________________________________________________
Page 2
PS#|
---+------------------------------------------------------------------
1 |1| 3| 6|10|15|21| 5|13|22| 9|20| 9|22|13| 5|21|15|10| 6| 3| 1| 0|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
2 |1| 4| 9|16| 2|13| 3|18|12| 8| 6| 6| 8|12|18| 3|13| 2|16| 9| 4| 1|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
3 |1| 5|12|22|12| 5| 1| 0| 2| 7|15| 3|17|11| 8| 8|11|17| 3|15| 7| 2|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
4 |1| 6|15| 5|22|20|22| 5|15| 6| 1| 0| 3|10|21|13| 9| 9|13|21|10| 3|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
5 |1| 7|18|11| 9|12|20|10| 5| 5|10|20|12| 9|11|18| 7| 1| 0| 4|13| 4|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
6 |1| 8|21|17|19| 4|18|15|18| 4|19|17|21| 8| 1| 0| 5|16|10|10|16| 5|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
7 |1| 9| 1| 0| 6|19|16|20| 8| 3| 5|14| 7| 7|14| 5| 3| 8|20|16|19| 6|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
8 |1|10| 4| 6|16|11|14| 2|21| 2|14|11|16| 6| 4|10| 1| 0| 7|22|22| 7|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
9 |1|11| 7|12| 3| 3|12| 7|11| 1| 0| 8| 2| 5|17|15|22|15|17| 5| 2| 8|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
10 |1|12|10|18|13|18|10|12| 1| 0| 9| 5|11| 4| 7|20|20| 7| 4|11| 5| 9|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
11 |1|13|13| 1| 0|10| 8|17|14|22|18| 2|20| 3|20| 2|18|22|14|17| 8|10|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
12 |1|14|16| 7|10| 2| 6|22| 4|21| 4|22| 6| 2|10| 7|16|14| 1| 0|11|11|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
13 |1|15|19|13|20|17| 4| 4|17|20|13|19|15| 1| 0|12|14| 6|11| 6|14|12|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
14 |1|16|22|19| 7| 9| 2| 9| 7|19|22|16| 1| 0|13|17|12|21|21|12|17|13|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
15 |1|17| 2| 2|17| 1| 0|14|20|18| 8|13|10|22| 3|22|10|13| 8|18|20|14|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
16 |1|18| 5| 8| 4|16|21|19|10|17|17|10|19|21|16| 4| 8| 5|18| 1| 0|15|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
17 |1|19| 8|14|14| 8|19| 1| 0|16| 3| 7| 5|20| 6| 9| 6|20| 5| 7| 3|16|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
18 |1|20|11|20| 1| 0|17| 6|13|15|12| 4|14|19|19|14| 4|12|15|13| 6|17|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
19 |1|21|14| 3|11|15|15|11| 3|14|21| 1| 0|18| 9|19| 2| 4| 2|19| 9|18|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
20 |1|22|17| 9|21| 7|13|16|16|13| 7|21| 9|17|22| 1| 0|19|12| 2|12|19|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
21 |1| 0|20|15| 8|22|11|21| 6|12|16|18|18|16|12| 6|21|11|22| 8|15|20|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
22 |1| 1| 0|21|18|14| 9| 3|19|11| 2|15| 4|15| 2|11|19| 3| 9|14|18|21|0
---+-+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+-
23 |1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|16|17|18|19|20|21|22|0
----------------------------------------------------------------------
USING MODULAR RESIDUE TO MAKE A PUBLIC KEY
The cryptographic implications can be easily seen. For example, any
member of the first polygonal sequence can be transform to be a member
the second sequence and used for a public key:
_____________________________________________________________________
Page 3
p = prime 1
q = prime 2
N= p X q
M= message
C = Cipher_text
Encrypt (using polygonal sequence 1): (Sender knows N by not p and q.)
(M X M + M)/2 modulo N == C (The resolution of the formula for
polygonal sequence 1.)
Decrypt: (Receiver knows p and q.)
(C X 8 + 1) modulo N == ((M X 2 + 1) X (M X 2 + 1)) modulo N
This converts the triangular encryption into a member of the square
sequence and allows for solution. Solve for (M X 2 + 1) modulo p and
(M X 2 + 1) modulo q. Using Chinese remainder theory the results may
be used to produce four possible solutions. 1 is subtracted from the
four possible results and the results are divided by 2. Many methods
can be used to avoid ambiguity, but presumably only one of the four
possible M's will make sense.
A similar possibility exists for the use of the fourth or hexagon
sequence, because it may also be changed into a member of the square
sequence by (C X 8 = 1), but decryption is more complicated. The
resulting squares require the subtraction of 1 and division by 2 AND
THEN the additional step of adding 1 and the dividing by 2.
For conventional key purposes it should also be noted that the
vertical columns in the example contain all numbers from 0 to (N-1)
(the exception are the 1 column and the N column which are all 1 or 0)
and can be readily determined by their additive quality modulo N,
as suggested by the general formula.
To the best my knowledge, O. Joel Benston and myself are the
originators of the idea of using polygonal sequences (other than the
square sequence) for cryptographic purposes. We are considering
patenting the idea. If you have knowledge of other persons, who have
suggested a similar approach, please advise us. (501) 484-5489
Path: gmdzi!unido!math.fu-berlin.de!ira.uka.de!sol.ctr.columbia.edu!
spool.mu.edu!think.com!rpi!news-server.csri.toronto.edu!utgpu!jmason2
From: jma...@gpu.utcs.utoronto.ca (Jamie Mason)
Newsgroups: sci.crypt
Subject: Re: New public key scheme, maybe
Message-ID: <1991Jul7.234851.29247@gpu.utcs.utoronto.ca>
Date: 7 Jul 91 23:48:51 GMT
References: <12044@ncar.ucar.edu>
Organization: University of Toronto Computer Services Advisor
Lines: 40
> To the best my knowledge, O. Joel Benston and myself are the
>originators of the idea of using polygonal sequences (other than the
>square sequence) for cryptographic purposes. We are considering
>patenting the idea. If you have knowledge of other persons, who have
>suggested a similar approach, please advise us. (501) 484-5489
I don't know enough number theory, and the like, to know how
cryptographically strong your method is. But if you try to pantent it,
and if the NSA sees your method as a threat to their paranoia, (that is
to say, if they think it is really strong), then they can issue a patent
secrecy order.
You could take such an order as a complement. Afterall, the
NSA *are* knowledgable, about cryptography; If they think your method is
strong enough to be a threat, that says good things about it.
However I would take such an order as an insult, not a
complement; and a blatent violation of civil rights. They can freeze the
patent, prevent you from using your method, and prevent you from
discussing it. On top of that, there are laws governing the exporting
of cryptographic programs from the US... Espicially to dangerous
communist countries like Canada. :-)
So if you want to patent it, be sure both that it is original,
and that you have published it in *lots* and *lots* of places, before you
brave then NSA. If it has been widely published, then they will be
powerless to stop it, and so will be less likely to give you trouble.
As for the strengh of the algorighm, it can't be *that* great,
or the NSA spooks watching the Internet would never have let it out of
the USA. ;-)
More seriously, you can count on this newsgroup for some reasoned u
opinions, and many, many flames, about the strength/weakness of your
algorithm. Just witness the "debate" over Braided Streams. But none of
these opinions will come from me. My opinions are about the NSA.
Jamie ... Lurker in the Process Table
Written On Sunday, July 7, 1991 at 07:44:47pm EDT
Path: gmdzi!unido!mcsun!uunet!zephyr.ens.tek.com!uw-beaver!cornell!wayner
From: way...@CS.Cornell.EDU (Peter Wayner)
Newsgroups: sci.crypt
Subject: Re: New public key scheme, maybe
Message-ID: <1991Jul8.154826.3745@cs.cornell.edu>
Date: 8 Jul 91 15:48:26 GMT
References: <12044@ncar.ucar.edu> <1991Jul7.234851.29247@gpu.utcs.utoronto.ca>
Sender: ne...@cs.cornell.edu (USENET news user)
Organization: Cornell Univ. CS Dept, Ithaca NY 14853
Lines: 31
Nntp-Posting-Host: horus.cs.cornell.edu
jma...@gpu.utcs.utoronto.ca (Jamie Mason) writes:
>> To the best my knowledge, O. Joel Benston and myself are the
>>originators of the idea of using polygonal sequences (other than the
>>square sequence) for cryptographic purposes. We are considering
>>patenting the idea. If you have knowledge of other persons, who have
>>suggested a similar approach, please advise us. (501) 484-5489
> More seriously, you can count on this newsgroup for some reasoned u
>opinions, and many, many flames, about the strength/weakness of your
>algorithm. Just witness the "debate" over Braided Streams. But none of
>these opinions will come from me. My opinions are about the NSA.
If you are going to patent the idea and potentially remove it from
free and public use, why should we donate our time to criticize
the strength of the system? This is just free consulting. I don't mind
doing it for academic purposes, but when patents are involved, it is
another story. Why don't you pay for a patent search by a patent
law firm? Why don't you hire a few cryptographers and pay them for their
opinion?
Money changes everything. If you want to approach it as a business, do
it that way.
>Jamie ... Lurker in the Process Table
>Written On Sunday, July 7, 1991 at 07:44:47pm EDT
--
Peter Wayner Department of Computer Science Cornell Univ. Ithaca, NY 14850
EMail:...@cs.cornell.edu Office: 607-255-9202 or 255-1008
Home: 116 Oak Ave, Ithaca, NY 14850 Phone: 607-277-6678
Path: gmdzi!unido!mcsun!uunet!cs.utexas.edu!asuvax!ncar!sage.cgd.ucar.edu!prz
From: p...@sage.cgd.ucar.edu (Philip Zimmermann)
Newsgroups: sci.crypt
Subject: Re: New public key scheme, maybe
Message-ID: <12061@ncar.ucar.edu>
Date: 9 Jul 91 01:41:19 GMT
References: <12044@ncar.ucar.edu> <1991Jul7.234851.29247@gpu.utcs.utoronto.ca>
<1991Jul8.154826.3745@cs.cornell.edu>
Sender: ne...@ncar.ucar.edu
Organization: Climate and Global Dynamics Division/NCAR, Boulder, CO
Lines: 24
As I understand it, if this public key scheme is new and is secure, then
David Colston was planning to let everyone use it for free, or for
nearly free. He even granted permission for everyone to use it for free
while the patent process was going on. It more closely resembles
academia than business. He says his intent is to make a public key scheme
available to everyone for free, but maybe charge a little money for
some wealthy companies to use it. In light of this public-spirited
attitude, a little public participation in evaluating it and criticizing
it seems appropriate and justified. People who help in this process
are helping the public good. Wouldn't it be nice to have someone
contribute something like this to the public good, if it really works,
and if it is really new? That's what Colston wants to do. He's not
looking to get rich. He wants to make a social contribution, and maybe
make a few thousand (not a few million) bucks for his time. That's
why he can't hire lawyers to do a patent search, or cryptographers to
eveluate it.
By the way, this scheme is only good for privacy encryption, not signatures.
Apparently, using it for signatures can expose the prime factors of the
public key N. Colston does not claim it can be used for signatures.
Disclosing it in writing before a patent application precludes foreign
patents, but not US patents. The public disclosure here was to prevent
secrecy orders from the NSA.