Method and apparatus for maintaining the privacy of digital messages conveyed by public transmission

• US 4,567,600 A
• Filed: 09/14/1982
• Issued: 01/28/1986
• Est. Priority Date: 02/02/1982
• Status: Expired due to Term

• Current Assignee: Omnet Associates
• Original Assignee: Omnet Associates
• Inventors: Massey, James L., Omura, Jimmy K.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US06/418,038
• Time in Patent Office: 1,232 Days
• Field of Search: 178/22.09, 178/22.1, 178/22.11, 178/22.14, 178/22.15, 178/22.16, 375/2.1
• US Class Current: 713/174
• CPC Class Codes: H04L 9/3026 details relating to polynomials generation, e.g. generation of irreducible polynomials
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

A private message of m bits is conveyed from its sender to its receiver by transmission of a public message of m bits, transmission of a public reply of m bits, and another transmission of a public message of m bits such that only the intended receiver can easily recover the private message from the three public messages. This private message now available to both the sender and intended receiver also allows all subsequent private messages between these two points to require only one public message for each private message while maintaining the property that only the intended receiver of each message can easily recover the private message for each public message.

Claims

1. An apparatus for maintaining the privacy of a digital message M conveyed by public transmission between a sender and a receiver, and adapted to serve as either a sending station or a receiving station when said sending station and said receiving station are interconnected by two-way public transmission means whose transmissions are subject to unauthorized reception, comprising:

(a) means for generating a random integer of m binary digits;

(b) means for computing two integers E and D each between 1 and 2^m -2 inclusive related such that their product ED equals 1 modulo 2^m -1, having as an input said random integer; and

(c) means for exponentiating, having as inputs, an integer N representing E or D, and a non-zero element B of the finite field GF(2^m) containing 2^m elements, having m binary digits in normal basis representation, for exponentiating said element B so as to form the element B^N of GF(2^m) having m binary digits in normal basis representation.

2. The apparatus recited in claim 1, wherein said means for exponentiating comprises:

(a) first means for storing the m binary digits of the element B to be exponentiated in normal basis representation;

(b) a first means for obtaining in sequence, the m-1 successive squares of B in normal basis representation;

(c) a second means for storing the m binary digits of the integer N representing the exponent in radix-two form;

(d) a second means for obtaining, in sequence, from lowest to highest order, the m binary digits of the integer N;

(e) an accumulator for accumulating successive products, whose initial contents are the m binary digits of the element 1 of GF(2^m) in normal basis representation, and which is successively updated with new contents, and whose final contents are the element B^N, in normal basis representation;

(f) a multiplier for GF(2^m) for determining the product vector of m binary digits of two elements of GF(2^m), each represented by a vector of m binary digits in normal basis representation, having as inputs the successive contents of said first means for storing and said accumulator, whereby after at most m successive multiplications, the element B^N of GF(2^m) will be determined;

(g) means for successively updating the contents of said accumulator with said product;

(h) means for feeding the contents of said accumulator to said multiplier; and

(i) means for controlling said multiplier whereby said multiplier will be enabled if the low order binary digit of said second means for storing is a logical 1, and disabled if said low order binary digit is a logical 0.

3. The apparatus recited in claim 2 wherein:

(a) said first means for storing comprises an m-bit circulating shift register whose initial contents are the m binary digits of the element B;

(b) said first means for obtaining comprises clocking circuitry for repetitively shifting the m binary digits of the element B in said circulating shift register such that after m shifts, the m-1 successive squares of B will have been formed in normal basis representation;

(c) said second means for storing comprises an m-bit shift register having as the output, the low order binary digit;

(d) said second means for obtaining comprises said clocking circuitry for repetitively shifting the m binary digits of the integer N in said shift register;

(e) said accumulator comprises an m-bit accumulation register;

(f) said means for successively updating comprises a first m-bit latch which transfers said product of said multiplier into said accumulator and further comprises said clocking circuitry which causes said transfer;

(g) said means for feeding comprises a second m-bit latch which transfers the contents of said accumulator to one input of said multiplier and further comprises said clocking circuitry which causes said transfer; and

(h) said means for controlling comprises means for coupling the output of said second means for storing to an enable input of said multiplier.

4. The apparatus recited in claim 2 or 3 wherein said multiplier comprises:

(a) means for developing, for each of the two vectors representing an element of GF(2^m), m successive rotated vectors; and

(b) logic means including at least one O-M circuit having the m rotated vectors for both elements as inputs, said logic means computing each binary digit of the vector representing the product of said two elements from respective pairs of said vectors using the same O-M logic function.

5. The apparatus recited in claim 4 wherein each of the 2^m elements of GF(2^m) is represented by a vector of m binary digits according to a normal basis representation of the form B=b_m-1 A².spsp.m-1 +b_m-2 A².spsp.m-2 + . . . b₂ A² +b₁ A² +b₀ A, where B is an element of GF(2^m), b_m-1, b_m-2, . . . b₂,b₁,b₀ are the binary digits of B, and A is an element of GF(2^m) satisfying the equation P(X)=0 for X=A, where P(X) is a polynomial of degree m which is irreducible over the field GF(2) and has linearly independent roots.

6. The apparatus recited in claim 5 wherein:

(a) said means for developing m rotated vectors comprises means to sequentially rotate the binary digits of each vector representing an element to be multiplied in one position increments; and

(b) said logic means comprise a single O-M circuit having as inputs the outputs of said means for developing whereby m rotated vectors will be supplied in sequence for each element to said logic means, and said logic means will thereby compute each binary digit of said product vector.

7. The apparatus recited in claim 5 wherein:

(a) said logic means comprise m identical O-M circuits for computing the respective binary digits of said vector representing the product of said two elements; and

(b) said means for developing m rotated vectors comprise a plurality of connections to said m identical O-M circuits such that the binary digits of said vectors are coupled as m rotated vectors at the inputs to respective ones of said m identical O-M circuits successively shifted by one position at each successive identical logic circuit.

8. The apparatus recited in claim 1, 2 or 3 wherein said means for exponentiating comprises at least one multiplier for GF(2^m) for determining the element B^N of GF(2^m).

9. The apparatus recited in claim 1,2 or 3 wherein said means for generating produces a random integer R between 1 and 2^m -1 inclusive, and wherein said means for computing computes said integers E and D according to the equations E=H^R modulo 2^m -1 and D=H^-R modulo 2^m -1 for a specified integer H, said means for computing comprising:

(a) a first means for storing 2 m m-bit words in 2 m storage locations j=0, 1, 2, 3, . . . 2 m-1, storage location j of which contains the integer H².spsp.j modulo 2^m -1 in radix-two form for j=0, 1, 2 . . . m-1 and H^-2.spsp.j-m modulo 2^m -1 in radix-two form for j=m, m+1 . . . 2 m-1, where H is an integer between 2 and 2^m -2 inclusive;

(b) a first means for obtaining, in sequence, each of said 2 m m-bit words;

(c) a second means for storing said random integer R having m binary digits;

(d) a second means for obtaining, in two identical sequences, from lowest to highest order, the m binary digits of said integer R;

(e) an accumulator for accumulating successive products, whose initial contents are the m binary digits of the integer 1 in radix-two form and whose contents after the m binary digits of the integer R have once been obtained are the binary digits of said integer E, and after the m binary digits of the integer R have twice been obtained are the m binary digits of said integer D;

(f) a 1'"'"'s complement multiplier which successively determines the 1'"'"'s complement product of two integers of m binary digits having as a first input, the successive contents of said first means for storing, and as a second input, the successive contents of said accumulator, whereby after at most m multiplications, said integer E will have been determined, and after at most 2 m multiplications, said integer D will have been determined;

(g) means for successively updating the contents of said accumulator with said 1'"'"'s complement product;

(h) means for feeding the contents of said accumulator to said 1'"'"'s complement multiplier; and

(i) means for controlling said 1'"'"'s complement multiplier whereby said 1'"'"'s complement multiplier will be enabled if the low order binary digit of said second memory is a logical 1, and disabled if said low order binary digit is a logical 0.

10. The apparatus recited in claim 9 wherein:

(a) said first means for storing comprises a read-only memory (ROM);

(b) said first means for obtaining comprises;

(i) clocking circuitry which operates at rate X Hz; and

(ii) a 2 m state counter which selects, in sequence, for each cycle of said clocking circuitry, one of said 2 m storage locations;

(c) said second means for storing comprises an m-bit circulating shift register having as the output, the low order binary digit;

(d) said second means for obtaining comprises said clocking circuitry for repetitively shifting the m binary digits of the integer R in said circulating shift register;

(e) said accumulator comprises an m-bit accumulation register;

(f) said means for successively updating comprises a first m-bit latch which transfers the 1'"'"'s complement product of said 1'"'"'s complement multiplier into said accumulator and further comprises said clocking circuitry which causes said transfer;

(g) said means for feeding comprises a second m-bit latch which transfers the contents of said accumulator to said 1'"'"'s complement multiplier and further comprises said clocking circuitry which causes said transfer; and

(h) said means for controlling comprises means for coupling the output of said second means for storing to an enable input of said 1'"'"'s complement multiplier.

11. The apparatus recited in claim 1,2 or 3 wherein m is an integer such that 2^m -1 is a prime number.

12. The apparatus recited in claim 9 wherein m is an integer such that p=2^m -1 is a prime number and the integer H is a primitive element of

13. GF(p). 13. The apparatus recited in claim 1, 2 or 3 when m is an integer such that 2^m -1 is a prime number wherein said means for generating produces said m-bit integer E as a randomly selected integer between 1 and 2^m -2 inclusive, and said computer produces the integer D from the randomly selected integer E, where DE=1 modulo 2^m -1, said means for computing comprising:

(a) an m-bit 1'"'"'s complement multiplier which performs 2 m-3 successive multiplications, having a first and second m-bit input an m-bit output, resulting in 2 m-3 successive m-bit products;

(b) a first accumulator whose initial contents are the m-bits of the random integer E in radix-two form, and which is successively updated, and the output of which connects to said first input of said m-bit 1'"'"'s complement multiplier;

(c) a second accumulator whose initial contents are the m-bits of the random integer E, and which is successively updated, and whose final contents are the m bits of the integer D;

(d) means for successively updating the contents of said first and second accumulators, whereby after the first multiplication said first product will be fed into said first accumulator, and thereafter, each successive product will be fed alternately into the first and second accumulator respectively; and

(e) means for coupling said first and second accumulators to said second m-bit input of said m-bit 1'"'"'s complement multiplier whereby after the first multiplication, said first accumulator is coupled to said second m-bit input, and thereafter, said first and second accumulators

14. respectively will be alternately coupled to said second m-bit input. 14. The apparatus recited in claim 13 wherein:

(a) said first accumulator comprises an m-bit accumulation register;

(b) said second accumulator comprises an m-bit accumulation register;

(c) said means for successively updating comprises;

(i) an m-bit switch having m switches with m ciommon inputs, one per switch, and first and second outputs for each of said m switches, and m common inputs respectively connecting to the m-bit output of said m-bit 1'"'"'s complement multiplier, said first outputs connecting to said first accumulator, and said second outputs connecting to said second accumulator;

(ii) clocking circuitry whereby said m-bit switch selects the first outputs during the first cycle of said clocking circuitry, and thereafter, alternately the first and second outputs respectively;

(iii) a disable input to said m-bit switch whereby said switch will not select alternate outputs between the first and second cycles of said clocking circuitry, but will after the second cycle and thereafter;

(d) said means for coupling comprises;

(i) an m-bit switch having m switches with first and second inputs and m common outputs, one per switch, said m first inputs connecting to said first accumulator, and said m second inputs connecting to said second accumulator, said m common outputs connecting to said second input of said m-bit 1'"'"'s complement multiplier;

(ii) clocking circuitry whereby said m-bit switch selects the first inputs during the first cycle of said clocking circuitry, and thereafter alternately, the first and second inputs respectively;

(iii) a disable input to said m-bit switch whereby said switch will not select alternate inputs between the first and second cycles of said

15. clocking circuitry, but will after the second cycle and thereafter. 15. The apparatus recited in claim 1, 2 or 3 wherein said means for exponentiating further comprises clocking circuitry operating at the rate of X Hz, and wherein said means for generating comprises an m-stage maximal-length linear feedback shift register with arbitrary non-zero initial contents and further comprises clocking circuitry operating at a rate >

X Hz, which shifts said contents of said maximal-length linear

16. feedback shift register. 16. An exponentiator which produces the element B^N of the finite field GF(2^m) containing 2^m elements in normal basis representation when presented with a non zero element B of GF(2^m) of m binary digits, and with an integer N between 1 and 2^m -2 inclusive of m binary digits to serve as the exponent, comprising:

(a) a first means for storing the m binary digits of said element B to be exponentiated in normal basis representation;

(b) a first means for obtaining in sequence, the m-1 successive squares of B in normal basis representation;

(c) a second means for storing the m binary digits of the integer N representing the exponent in radix-two form;

(d) a second means for obtaining, in sequence, from lowest to highest order, the m binary digits of the integer N;

(e) an accumulator for accumulating successive products whose initial contents are the element 1 of GF(2^m) in normal basis representation and which is successively updated with new contents, and whose final contents are the element B^N in normal basis representation;

(f) a multiplier for GF(2^m) for determining the product vector of m binary digits of two elements of GF(2^m), each represented by a vector of m binary digits in normal basis representation, having as inputs the successive contents of said first means for storing and said accumulator, whereby after at most m successive multiplications, the element B^N of GF(2^m) will be determined;

(g) means for successively updating the contents of said accumulator with said product;

(h) means for feeding the contents of said accumulator to said multiplier; and

(i) means for controlling said multiplier whereby said multiplier will be enabled if the low order binary digit of said second memory is a logical

17. 1, and disabled if said low order binary digit is a logical 0. 17. The exponentiator recited in claim 16 wherein:

(a) said first means for storing comprises an m-bit circulating shift register whose intital contents are the m binary digits of the element B;

(b) said first means for obtaining comprises clocking circuitry which operate at rate X Hz, for repetitively shifting the m binary digits of the element B in said circulating shift register such that after m shifts, the m-1 successive squares of B will have been formed in normal basis representation;

(c) said second means for storing comprises an m-bit shift register having as the output, the low order binary digit;

(d) said second means for obtaining comprises said clocking circuitry for repetitively shifting the m binary digits of the integer N in said shift register;

(e) said accumulator comprises an m-bit accumulation register;

(f) said means for successively updating comprises a first m-bit latch which transfers said product of said multiplier into said accumulator and further comprises said clocking circuitry which causes said transfer;

(g) said means for feeding comprises a second m-bit latch which transfers the contents of said accumulator to one input of said multiplier and further comprises said clocking circuitry which causes said transfer; and

(h) said means for controlling comprises means for coupling the output of

18. said second means for storing to an enable input of said multiplier. 18. The exponentiator recited in claim 16 or 17 wherein each of the 2^m elements of GF(2^m) is represented by a vector of m binary digits according to a normal basis representation of the form B=b_m-1 A².spsp.m-1 +b_m-2 A².spsp.m-2 + . . . b₂ A⁴ +b₁ A² +b₀ A, where B is an element of GF(2^m), b_m-1, b_m-2, . . . b₂, b₁, b₀ are the binary digits of B, and A is an element of GF(2^m) satisfying the equation P(X)=0 for X=A, where P(X) is a polynomial of degree m which is

19. irreducible over the field GF(2) and has linearly independent roots. 19. An apparatus for computing a pair of integers E and D each having m binary digits and each between 1 and 2^m -2 inclusive according to the equations E=H^R modulo 2^m -1 for a specified integer H and ED=1 modulo 2^m -1, when presented with a random integer R of m binary digits between 1 and 2^m -1 inclusive, comprising:

(a) a first means for storing 2 m m-bit words in 2 m storage locations j=0, 1, 2, 3 . . . 2 m-1, storage location j of which contains the integer H².spsp.j modulo 2^m -1 in radix-two form for j=0, 1, 2 . . . m-1, and H^-2.spsp.j-m modulo 2^m -1 in radix-two form for j=m, m+1 . . . 2 m-1, where H is an integer between 2 and 2^m -2 inclusive;

(b) a first means for obtaining, in sequence, each of said 2 m m-bit words;

(c) a second means for storing said random integer R having m binary digits;

(d) a second means for obtaining, in two identical sequences, from lowest to highest order, the m binary digits of said integer R;

(e) an accumulator for accumulating successive products, whose initial contents are the m binary digits of the integer 1 in radix-two form and whose contents after the m binary digits of the integer R have once been obtained are the m binary digits of said integer E, and after the m binary digits of the integer R have twice been obtained are the m binary digits of said integer D;

(f) a 1'"'"'s complment multiplier for determining the 1'"'"'s complement product of two integers of m binary digits having as a first input, the successive contents of said first means for storing, and as a second input, the successive contents of said accumulator, whereby after at most m multiplications, said integer E will have been determined, and after at most 2 m multiplications, said integer D will have been determined;

(g) means for successively updating the contents of said accumulator with said 1'"'"'s complement product;

(h) means for feeding the contents of said accumulator to said 1'"'"'s complement multiplier;

(i) means for controlling said 1'"'"'s complement multiplier whereby said 1'"'"'s complement multiplier will be enabled if the low order binary digit of said second means for storing is a logical 1, and disabled if said low

20. order binary digit is a logical 0. 20. The apparatus recited in claim 19 wherein:

(a) said first means for storing comprises a read-only memory (ROM);

(b) said first means for obtaining comprises;

(i) clocking circuitry which operates at rate X Hz; and

(ii) a 2 m state counter which selects, in sequence, for each cycle of said clocking circuitry, one of said 2 m storage locations;

(c) said second means for storing comprises an m-bit circulating shift register having as the output, the low order binary digit;

(d) said second means for obtaining comprises said clocking circuitry for repetitively shifting the m binary digits of the integer R in said circulating shift register;

(e) said accumulator comprises an m-bit accumulation register;

(f) said means for successively updating comprises a first m-bit latch which transfers the 1'"'"'s complement product of said 1'"'"'s complement multiplier into said accumulator and further comprises said clocking circuitry which causes said transfer;

(g) said means for feeding comprises a second m-bit latch which transfers the contents of said accumulator to said 1'"'"'s complement multiplier and further comprises said clocking circuitry which causes said transfer; and

(h) said means for controlling comprises means for coupling the output of said second means for storing to an enable input of said 1'"'"'s complement

21. multiplier. 21. An apparatus for computing an m-bit integer D from a randomly selected m-bit integer E, where both E and D are between 1 and 2^m -2 inclusive, and are related such that ED equals 1 modulo 2^m -1, comprising:

(a) an m-bit 1'"'"'s complement multiplier which performs 2 m-3 successive multiplications, having a first and second m-bit input and an m-bit output, resulting in 2 m-3 successive m-bit products;

(b) a first accumulator whose initial contents are the m-bits of the random integer E in radix-two form and which is successively updated and the output of which connects to said first input of said m-bit 1'"'"'s complement multiplier;

(c) a second accumulator whose initial contents are the m-bits of the random integer E, and which is successively updated, and whose final contents are the m bits of the integer D;

(d) means for successively updating the contents of said first and second accumulators, whereby after the first multiplication said first product will be fed into said first accumulator, and thereafter, each successive product will be fed alternately into the first and second accumulators respectively; and

(e) means for coupling said first and second accumulators to said second m-bit input of said m-bit 1'"'"'s complement multiplier whereby after the first multiplication, said first accumulator is coupled to said second m-bit input, and thereafer, said first and second accumulators

22. respectively will be alternately coupled to said second m-bit input. 22. The apparatus recited in claim 21 wherein:

(a) said first accumulator comprises an m-bit accumulation register;

(b) said second accumulator comprises an m-bit accumulation register;

(c) said means for successively updating comprises;

(i) an m-bit switch having m switches with m common inputs, one per switch, and first and second outputs for each of said m switches, said m common inputs respectively connecting to the m-bit output of said first accumulator, and said second outputs connecting to said second accumulator;

(ii) clocking circuitry whereby said m-bit switch selects the first outputs during the first cycle of said clocking circuitry, and thereafter, alternately the first and second outputs respectively;

(iii) a disable input to said m-bit switch whereby said switch will not select alternate outputs between the first and second cycles of said clocking circuitry, but will after the second cycle and thereafter;

(d) said means for coupling comprises;

(i) an m-bit switch having m switches with first and second inputs and m common outputs, one per switch, said m first inputs connecting to said first accumulator, and said m second inputs connecting to said second accumulator, said m common outputs connecting to said second input of said m-bit 1'"'"'s complement multiplier;

(ii) clocking circuitry whereby said m-bit switch selects the first inputs during the first cycle of said clocking circuitry, and thereafter alternately, the first and second inputs respectively;

(iii) a disable input to said m-bit switch whereby said switching means will not select alternate inputs between the first and second cycles of said clocking circuitry, but will after the second cycle and thereafter.

23. The method for maintaining the privacy of a digital message M conveyed by public transmission between a sender and a receiver wherein private transmission of said digital message M requires the actual transmission of a first public digital message Y₁, a second public digital message Y₂ and a third public digital message Y₃ for each private digital message M over public transmission means, said private digital message M and said three public digital messages Y₁, Y₂ and Y₃ each represented by a vector of m binary digits where m is an integer equal to or greater than 2, and each normal basis representations of an element of the finite field GF(2^m) containing 2^m elements other than the elements 0 and 1 of said finite field, said three public messages Y₁, Y₂ and Y₃ being the elements of GF(2^m) determined by the equations

View Dependent Claims (24, 25, 26)

24. private message M. 24. The method recited in claim 23 for the effective sending and receiving of further private messages M_i '"'"' and M_i " by the transmission of further public messages Y_i '"'"' and Y_i ", for i=0 to ∞

, after said private message M is transmitted by the exchange of said three public messages, where said private message M is the m-bit radix-two form of an integer D₁ between 1 and 2^m -2 inclusive, and E₁ is a second m-bit integer in radix two form between 1 and 2^m -2 inclusive such that E₁ D₁ =1 modulo 2^m -1, where E₁ and D₁ are computed in said means for computing at said sending station, said further private and public messages each containing m binary digits in normal basis representation and representing elements of the finite field GF(2^m) other than the elements 0 and 1, wherein any of said further private messages M_i '"'"' are transmitted by the actual transmission of the public message Y_i '"'"' for each private message M_i '"'"', where Y_i '"'"'=(M_i '"'"')^E.sbsp.1, said message Y_i '"'"' being computed in said means for exponentiating at said sending station, and said message M_i '"'"' being obtained by said means for exponentiating at said receiving station according to the equation M_i '"'"'=(Y_i '"'"')^D.sbsp.1, and wherein any of said further private messages M_i " are transmitted from said receiving station to said sending station by the actual transmission of one public message Y_i " for each private message M_i ", where Y_i "=(M_i ")^D.sbsp.1, said message Y_i " being computed in said means for exponentiating at said receiving station, and said message M_i " being obtained by said means for exponentiating at said sending station

25. according to the equation M_i "=(Y_i ")^E.sbsp.1. 25. The method recited in claim 24 where there is at least one receiving station, wherein said private message M is the m-bit radix two form of a randomly selected integer R between 1 and 2^m -2 inclusive generated in said random integer generating means at said sending station, and said means for computing at said receiving station computes said integer D₁ from said integer R according to the equation D₁ =H^-R for a specified integer H, whereby said message M_i '"'"'=(Y_i '"'"')^D.sbsp.1 may be obtained at said receiving station, and said message Y_i "=(M_i ")^D.sbsp.1 may be transmitted to said sending station from said

26. receiving station. 26. The method recited in claim 23, where there is at least one receiving station, for the effective sending of further private messages M_i '"'"', for i=0 to ∞

between any of said stations by the sending of one public message Y_i '"'"' for i=0 to ∞

, for each further private message M_i '"'"' after the exchange of said three public messages, wherein said private message M is the m-bit radix two form of said integer E₁ between 1 and 2^m -2 inclusive, said integer E₁ having been generated in said random integer generating means at said sending station, whereby said means for computing at said sending station and at said receiving station compute said integer D₁ between 1 and 2^m -2 inclusive such that E₁ D₁ =1 modulo 2^m -1, said further private and public messages each containing m binary digits in normal basis representation and representing an element of the finite field GF(2^m) other than the elements 0 and 1, and wherein said further private message M_i '"'"' is sent from one of said stations to the others of said stations by the actual transmission of said public message Y_i '"'"', where Y_i '"'"'=(M_i '"'"')^E.sbsp.1 is computed in said means for exponentiating at said sending station, and said message M_i '"'"' is obtained by said means for exponentiating at said receiving station according to the equation M_i '"'"'=(Y_i '"'"')_D.sbsp.1.