Path: msuinfo!sharkey!caen!zaphod.mps.ohio-state.edu!qt.cs.utexas.edu!cs.utexas.edu!asuvax!ncar!sage.cgd.ucar.edu!prz From: prz@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: news@ncar.ucar.edu Reply-To: prz@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, prz@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