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