New public key scheme, maybe
Philip Zimmermann
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
Jamie Mason
>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
Peter Wayner
>> 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:way...@cs.cornell.edu Office: 607-255-9202 or 255-1008
Home: 116 Oak Ave, Ithaca, NY 14850 Phone: 607-277-6678
Arthur Rubin
>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
>
(Detailed description ommited)
> 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
>
Sorry, polygonal sequences are functionally identical to square sequences.
However, they might not be subject to the RSA patent, even if the RSA patent is
valid. (I think they are, though.)
Let k be the number of sides (3,4,...)
ps(M,k) = (M /2) x ( (k-2) M + (4 - k))
2 ps(M,k) / (k-2) = M x M + (4-k)/(k-2) M
2 ps(M,k) / (k-2) + ((4-k)/(2 x (k-2))^2 = (M + (4-k)/(2 x (k-2))^2
--
216...@mcimail.com 7070...@compuserve.com art...@pnet01.cts.com (personal)
a_r...@dsg4.dse.beckman.com (work)
My opinions are my own, and do not represent those of my employer.
W.A.Simon
>> 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
> 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.
ditto for number theory, but two points:
- all systems that rely on the difficulty of resolving
a hard mathematical problem are sitting ducks waiting
to be shot by a smarter brain with a bigger computer.
- NSA won't do much about anything of that kind anymore.
The horse has fled the barn a few years back and NSA
just heard about it. |8-) de rigueur.
> [ ... ]
>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. :-)
Le ridicule tue. I think NSA is getting familiar with
this idea... and it's about time, because there are far
more dangerous threats to NatSec out there.
> 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.
I guess we can consider it published since at least two
Canadians have read it... |8-)
> 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
|8-), and it's only the beginning, I hear they have just
cranked Dan Bernstein up again.
>[ ... ]
>Jamie ... Lurker in the Process Table
--
William "Alain" Simon al...@elevia.UUCP
Frank Zappa for President of the United States of North America!
Robert Turner
>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
>
> We are considering
>patenting the idea.
Does making this method public knowledge prior to starting the patenting
process hurt you chances to receive a patent?
Robert
--
Robert Turner (602) 897-5441 Semiconductor Systems Design Technology, Motorola
tur...@ssdt-tempe.sps.mot.com OR ...!uunet!dover!turner
"Most Americans do not know or appreciate the fact that citizenship is the
primary political office under a constitutional government." Mortimer Adler
Steven Bellovin
> Does making this method public knowledge prior to starting the patenting
> process hurt you chances to receive a patent?
In the U.S., you may file for a patent within one year of first publication.
Elsewhere, you must file first.
Philip Zimmermann
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.
Dan Bernstein
> |8-), and it's only the beginning, I hear they have just
> cranked Dan Bernstein up again.
You called?
I recommend that the latest inventors of this public-key scheme
immediately apply for a United States patent. Having such a patent will
be an invaluable asset in the fight against RSA's control over patents
covering exactly the same thing.
(:-/ for the intelligence-impaired)
---Dan
W.A.Simon
>In article <1991Jul8.2...@elevia.UUCP> al...@elevia.UUCP (W.A.Simon) writes:
>> |8-), and it's only the beginning, I hear they have just
>> cranked Dan Bernstein up again.
>You called?
I have a feeling I am going to regret it. Let's not
invoke names in vain |8-)
>I recommend that the latest inventors of this public-key scheme
>immediately apply for a United States patent. Having such a patent will
>be an invaluable asset in the fight against RSA's control over patents
>covering exactly the same thing.
Yes.
>(:-/ for the intelligence-impaired)
|8-0
>---Dan