Non-deterministic public key encrypton system

• US 5,799,088 A
• Filed: 09/23/1996
• Issued: 08/25/1998
• Est. Priority Date: 12/01/1993
• Status: Expired due to Fees

• Current Assignee: RPK New Zealand Limited
• Original Assignee: RPK New Zealand Limited
• Inventors: Raike, William Michael
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/656,185
• Time in Patent Office: 701 Days
• Field of Search: 380/28, 380/30, 380/46
• US Class Current: 380/30
• CPC Class Codes: H04L 2209/043 of tables, e.g. lookup, substitution or mapping
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme
• CPC Class Codes: H04L 9/3226 using a predetermined code, e.g. password, passphrase or PIN network architectures or network communication protocols for supporting authentication of entities using passwords in a packet data network H04L63/083
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A non-deterministic public key encryption system whereby a public key is generated from a private key using mathematical operations equivalent to exponentiation in finite fields. Thus an attacker is required to compute logarithms over finite fields. Encryption involves generating a random initialization key (R) which is used to (1) exponentiate the message receiver'"'"'s public key (E) to produce initial values (K) for a pseudorandom binary mixture generator, and to (2) compute an open key (Q) by exponentiating an initial known generator state (a₀). A ciphertext (C) is produced from plaintext (P) by clocking the mixture generator from the initial value (K) and combining the output keystream with the plaintext (P). The open key (Q) is attached to the ciphertext prior to transmission. Decryption involves extracting the open key (Q) and exponentiating this by the message receiver'"'"'s private key (D) to compute (K) which is then used to set the initial value of a mixture generator. The mixture generator is clocked and its output keystream combined with the ciphertext (C) to produce plaintext (P). The invention may be implemented in special purpose hardware or in software for a general purpose processor.

Claims

1. A public-key encryption system wherein a message sender encrypts a plaintext message P using a publicly known key unique to a message receiver and the message receiver decrypts the encrypted message using a secret private key from which the public key has been derived, characterised in that:

(1) a private key (D) is selected which comprises a plurality of binary numbers D₁ to n ;

(2) a public key (E) is computed by exponentiation (as hereinbefore defined) using the private key by, for each of the said numbers D₁ to n, calculating the state of a pseudo-random binary number generator from a given and known initial state after a number of clock pulses or state transitions equal to the corresponding number given by the private key D₁ to n and providing each of the calculated binary states E₁ to n as a component of the public key E;

(3) the message sender

(a) generates a random initialisation key (R) comprising a set of binary numbers R₁ to n and computes by exponentiation an open key Q by, for each of the numbers R₁ to n, calculating the state of a pseudo-random binary number generator from a given and known initial state after a number of clock pulses or state transitions equal to the corresponding number given by the random initialisation key R₁ to n and providing each of the calculated binary states O₁ to n as a component of the open key Q,

(b) exponentiates the components of the public key E by the components of the random initialisation key R to produce generator initialisation states K₁ to n by, for each of the said numbers E₁ to n and R₁ to n, calculating the state of a pseudo-random binary number generator that would result from applying the process defined in step (2) a number of times equal to the corresponding binary number R₁ to n,

(c) loads a set (n) of pseudo-random binary number generators, the outputs of which are combined to form a first mixture generator, with initial values K₁ to n,

(d) clocks the first mixture generator to obtain a keystream serial output,

(e) combines said keystream output with the binary plaintext message P to produce an encrypted bit stream ciphertext C,

(f) adds the ciphertext C to the open key Q to produce a message stream,

(g) transmits the message to the message receiver;

(4) the message receiver

(a) extracts the open key Q from the message stream,

(b) exponentiates the open key Q by the private key D to derive generator initialisation states K₁ to n by, for each of the said numbers Q₁ to n and D₁ to n, calculating the state of a pseudo-random binary number generator that would result from applying the process defined in step (3)(a) a number of times equal to the corresponding binary number D₁ to n,

(c) loads a second set (n) of pseudo-random binary number generators, the outputs of which are combined to form a mixture generator, with the generator initialisation states K₁ to n,

(d) clocks the mixture generator to obtain a keystream serial output and combines this output with the received encrypted bit stream to produce the sender'"'"'s plaintext message.

2. A public key encryption system according to claim 1 wherein said mixture generator comprises a set (n) of maximal period linear shift registers, with one generator in the set arranged to pseudo-randomly select the output of one of the remaining (n-1) members of the set each time it is clocked to provide said keystream serial output.

3. A public key encryption system according to claim 1 wherein generating said random initialisation key R comprises the steps:

(1) manipulating an electronic pointer device whose state at any time t can be described as a point X_t represented by a plurality of coordinates (X_t1, X_t2, . . . X_tn);

(2) measuring the points X_t describing the states of said input device at a plurality of time instants t=1, 2, . . . , n;

(3) selecting a subset of the points thus measured corresponding to a subset of said time instants;

(4) computing a numerical function of the coordinates of all the points thus selected;

(5) producing the desired random numbers as the plurality of binary digits which represent the value of the numerical function thus computed.

4. A public key encryption system according to claim 1 wherein combining said keystream with the binary plaintext P to produce said ciphertext C, comprises the steps of, for each component of P, P_i :

(1) generating a pseudorandom permutation T of the bytes 1, . . . , n_i using a plurality of bytes of the serial keystream output;

(2) permuting the relative positions of the bytes n_i within the part P_i according to the permutation T to form an intermediate part I_i ;

(3) forming the i-th part C_i of the encrypted bit stream by for each byte B of the intermediate part I_i ;

(a) generating one or more bytes of the serial keystream output; and

(b) replacing the byte B with a quantity that depends upon the byte B and the said generated byte or bytes of the serial keystream output.

5. A public key encryption system according to claim 4 including the steps of for each successive part P_i computing a cumulative current message digest value D_i for all parts of the binary information P from its beginning up to and including P_i ;

and

obtaining and discarding a number of additional bytes of the serial keystream output, said number depending upon the current message digest value D_i.

17. A public key encryption system according to claim 1 wherein said mixture generator comprises a set (n) of multiplicative congruential generators, with one generator in the set arranged to pseudo-randomly select the output of one of the remaining (n-1) members of the set each time it is clocked to provide said keystream output.

6. Encryption apparatus for a public key encryption system in which a private key (D) is selected which comprises a plurality of binary numbers D₁ to n and a public key (E) is exponentiated using the private key by, for each of the said numbers D₁ to n, calculating the state of a pseudo-random binary number generator from a given initial state after a number of clock pulses or state transitions equal to the corresponding number given by the private key D₁ to n, and providing each of the calculated binary states E₁ to n as a component of the public key E, said apparatus comprising:

means for generating a random initialisation key (R) comprising a set of binary numbers R₁ to n ;

means for calculating by exponentiation an open key Q by, for each of the said numbers R₁ to n, calculating the state of a pseudo-random binary number generator from a given and known initial state after a number of clock pulses or state transitions equal to the corresponding number given by the random initialisation key R₁ to n and providing each of the calculated binary states Q₁ to n as a component of the open key Q;

means for exponentiating the components of the public key E by the components of the random initialisation key R to produce generator initialisation states K₁ to n by, for each of the said numbers E₁ to n and R₁ to n, calculating the state of a pseudo-random binary number generator that would result from applying the process used to exponentiate public key (E) a number of times equal to the corresponding binary number R₁ to n ;

a mixture generator comprising a set (n) of pseudo-random binary number generators, the outputs of which are combined to form the output of the mixture generator;

means which load said set (n) of pseudo-random binary number generators with initial values equal to K₁ to n ;

means which clock the mixture generator to obtain a keystream serial output;

means which receive a plaintext message and combine the output of the mixture generator with the binary plaintext message to produce an encrypted bit stream;

means for adding the ciphertext C to the open key Q to produce a message stream, and

means for transmitting the message stream to the message receiver.

7. Decryption apparatus for a public-key encryption system in which a private key (D) is selected which comprises a plurality of binary numbers D₁ to n and a public key (E) is exponentiated using the private key by, for each of the said numbers D₁ to n, calculating the state of a pseudo-random binary number generator from a given initial state after a number of clock pulses or state transitions equal to the corresponding number given by the private key D₁ to n, and providing each of the calculated binary states E₁ to n as a component of the public key E, and wherein a plaintext message is encrypted according to a process whereby the message sender

(1) generates a random initialisation key (R) comprising a set of binary numbers R₁ to n and computes by exponentiation an open key Q by for each of the said numbers R₁ to n, calculating the state of a pseudo-random binary number generator from a given and known initial state after a number of clock pulses or state transitions equal to the corresponding number given by the random initialisation key R₁ to n and providing each of the calculated binary states Q₁ to n as a component of the open key Q;

(2) exponentiates the components of the public key E by the components of the random initialisation key R to produce generator initialisation states K₁ to n by, for each of the said numbers E₁ to n and R₁ to n, calculating the state of a pseudo-random binary number generator that would result from applying the process previously defined, wherein a private key is used to exponentiate a public key, a number of times equal to the corresponding binary number R₁ to n ;

(3) loads a set (n) of pseudo-random binary number generators, the outputs of which are combined to form a mixture generator, with initial values K₁ to n ;

(4) clocks the mixture generator to obtain a keystream serial output and combines this output with the binary plaintext message to produce an encrypted bit stream ciphertext C, and

(5) transmits the encrypted bit stream together with the open key Q to the message receiver,

said decryption apparatus comprising;

means for extracting the open key Q from the encrypted bit stream;

means for exponentiating the components of the open key Q by the components of the private key D to derive generator initialisation states K₁ to n by, for each of the said numbers Q₁ to n and D₁ to n, calculating the state of a pseudo-random binary number generator that would result from applying the process defined above for deriving the open key Q a number of times equal to the corresponding binary number D₁ to n ;

a set (n) of pseudo-random binary number generators, the outputs of which are combined to form a mixture generator;

means which load said set (n) of pseudo-random binary number generators with initial values equal to K₁ to n ;

means for clocking the mixture generator to obtain a keystream serial output;

and means for combining this output with the received ciphertext C to produce the plaintext message P.

8. A public-key authentication system wherein a message sender appends signature information to a message and registers corresponding authentication information together with his name in a signature archive that is open to public inspection and wherein a message verifier obtains the message and its signature information, and the authentication information from the public signature archive and uses these to confirm whether or not the message has been sent by the sender identified by said signature information, characterised in that:

(1) the message sender

(a) selects a random digital signature (S) consisting of a plurality of binary numbers S₁ to n ;

(b) exponentiates a verification key V by, for each of said numbers S₁ to n, by calculating the state of a pseudo-random binary number generator from a given initial state after a number of clock pulses or state transitions equal to the corresponding number given by the random digital signature S₁ to n and providing each of the calculated binary states V₁ to n as a component of the verification key V;

(c) checks said signature archive to ensure that the verification key V computed in (b) has not yet been registered and if V has previously been registered repeats steps (a) and (b);

(d) computes a generalised cyclic redundancy check (CRC) value C by, for each one of a set (n) of pseudo-random binary number generators, computing the remainder resulting from dividing the sequence of bits comprising the message being sent by a modulus corresponding to said pseudo-random binary number generator and providing each such remainder C₁ to n as a component of the generalised CRC value C;

(e) computes the sum C+S (modulo

     2) and registers this sum and the verification key V under his name in the public signature archive;

(f) appends S to the message being sent, and

(2) the message verifier

(a) extracts the digital signature (S) consisting of a plurality of binary numbers S₁ to n from the message;

(b) computes a generalised cyclic redundancy check (CRC) value C by, for each of the said numbers S₁ to n, computing the remainder resulting from dividing the sequence of bits comprising the received message by a modulus corresponding to a pseudo-random binary number generator and providing each such remainder C₁ to n as a component of the generalised CRC value C;

(c) computes a verification key V by, for each of said numbers S₁ to n, exponentiating a given initial state of the corresponding pseudo-random binary number generator using each said number S₁ to n by means of the process defined in step (1)(b);

(d) computes the sum C+S (modulo

     2);

(e) searches the public signature archive under the name of the sender identified by said signature information of the message for authentication information matching the values C+S (modulo

     2) and V computed in (c) and (d);

(f) validates the message as authentic if the search in (e) is successful, or rejects it as spurious if the search in (e) is unsuccessful.

9. A public-key authentication system wherein a message authenticator selects a private key D which comprises a plurality of binary numbers D₁ to n and exponentiates a public key E using the private key by, for each of the said numbers D₁ to n, calculating the state of a pseudo-random binary number generator from a given initial state after a number of clock pulses or state transitions equal to the corresponding number given by the private key D₁ to n and providing each of the calculated binary states E₁ to n as a component of the public key E, and makes E available for public inspection, and wherein a message sender registers unique authentication information with said message authenticator and appends signature information to a message, and wherein a message verifier obtains the message, calculates a generalised CRC value for the message, submits the message signature information, the generalised CRC value and the sender'"'"'s name or other identifying information to the message authenticator, and wherein said message authenticator uses said generalised CRC value, said message signature information and said registered authentication information to confirm whether or not the message has been sent by the sender identified by said authentication information, characterised in that:

(1) the message sender

(a) selects an authentication password (P) consisting of a plurality of binary numbers;

(b) requests said signature authenticator to register the authentication password P to correspond to his name or other identifying information and to confirm that P has not yet been registered by anyone and if informed that P has previously been registered repeats step (a);

(c) computes a generalised cyclic redundancy check (CRC) value C_M by, for each one of a set (n) of pseudo-random binary number generators, computing the remainder resulting from dividing the sequence of bits comprising the message being sent by a modulus corresponding to said pseudo-random binary number generator and providing each such remainder C₁ to n to as a component of the generalised CRC value C_M ;

(d) computes intermediate signature information by appending the generalised CRC value C_M to the authentication password P;

(e) computes message signature information S_P,M by encrypting the intermediate signature information computed in step (d) using the signature authenticator'"'"'s public key E by

(i) selecting a random initialisation key (R) comprising a set of binary numbers R₁ to n and exponentiating the initial state using each number by, for each of the said numbers R₁ to n, calculating the state of pseudo-random binary number generator from a given initial state after a number of clock pulses or state transitions given by the random initialisation key R₁ to n and providing each of the calculated binary states Q₁ to n to produce an open key Q,

(ii) exponentiating the components of the signature authenticator'"'"'s public key E by the components of the random initialisation key R to produce generator initialisation states K₁ to n by, for each of the said numbers E₁ to n and R₁ to n, calculating the state of a pseudo-random binary number generator that would result from applying the process previously defined, wherein a private key is used to exponentiate a public key, a number of times equal to the corresponding binary number R₁ to n,

(iii) loading a set (n) of pseudo-random binary number generators, the outputs of which are combined to form a mixture generator, with initial values K₁ to n,

(iv) clocking the mixture generator to obtain a keystream serial output and combining this output with said intermediate signature information to produce encrypted intermediate signature information,

(v) appending said encrypted intermediate signature information to said open key Q to produce message signature information S_P,M,

(f) appending the said message signature information S_P,M to the message and also appending his name or other identifying information to the message,

(2) the message verifier

(a) extracts the message signature information (S_P,M) and the sender'"'"'s name or other identifying information from the message;

(b) computes a generalised CRC value C'"'"'_M for the message by means of the process defined in step (1)(c);

(c) submits the said message signature information and the sender'"'"'s name or other identifying information and the said generalised CRC value C'"'"'_M to the signature authenticator and requests said signature authenticator to compare the authentication password P and generalised CRC value C_M encrypted within the message signature information S_P,M with C'"'"'_M and the sender'"'"'s name or other identifying information, and

(3) the message authenticator

(a) decrypts the message signature information S_P,M using its private key D by

(i) extracting the open key Q from the message signature information,

(ii) exponentiating the open key Q by the private key D to derive generator initialisation states K₁ to n by, for each of the said numbers Q₁ to n and D₁ to n, calculating the state of a pseudo-random binary number generator that would result from applying the process defined in step (1)(e)(i) a number of times equal to the corresponding binary number D₁ to n,

(iii) loading a second set (n) of pseudo-random binary number generators, the outputs of which are combined to form a mixture generator, with the generator initialisation states K₁ to n,

(iv) clocking the mixture generator to obtain a keystream serial output and combining this output with the message signature information to thereby recover the intermediate signature information P and C computed in step (1)(d);

(b) compares the value of P contained in said intermediate signature information with the authentication password registered as corresponding to the name or other identifying information submitted in step (2)(c);

(c) compares the value of C_M contained in said intermediate signature information with the value of C'"'"'_M submitted in step (2)(c);

(d) confirms to the message verifier that the message is authentic if both of the comparisons in steps (c) and (d) are successful, or rejects it as spurious if either comparison fails.

10. A method for generating random numbers comprising the steps of:

(1) manipulating an electronic pointer device whose state at any time t can be described as a point X_t represented by a plurality of coordinates (X_t1, X_t2, . . . X_tn);

(2) measuring the points X_t describing the states of said input device at a plurality of time instants t=1, 2, . . . , n;

(3) selecting a subset of the points thus measured corresponding to a subset of said time instants;

(4) computing a numerical function of the coordinates of all the points thus selected;

(5) producing the desired random numbers as the plurality of binary digits which represent the value of the numerical function thus computed.

11. A method of combining a serial keystream output with binary information P, comprising a succession of parts P₁, . . . , P_N in which each part P_i represents a number of bytes n_i, to produce an encrypted bit stream C comprising a succession of parts C_i, said method comprising the steps of, for each successive part P_i :

(1) generating a pseudorandom permutation T of the bytes 1, . . . , n_i using a plurality of bytes of the serial keystream output;

(2) permuting the relative positions of the bytes n_i within the part P_i according to the permutation T to form an intermediate part I_i ;

(3) forming the i-th part C_i of the encrypted bit stream by for each byte B of the intermediate part I_i ;

(a) generating one or more bytes of the serial keystream output; and

(b) replacing the byte B with a quantity that depends upon the byte B and the said generated byte or bytes of the serial keystream output.

12. A method of combining a serial keystream with binary information according to claim 11 including the steps of for each successive part P_i computing a cumulative current message digest value D_i for all parts of the binary information P from its beginning up to and including P_i ;

and

obtaining and discarding a number of additional bytes of the serial keystream output, said number depending upon the current message digest value D_i.

13. A method of combining a serial keystream output with an encrypted bit stream C comprising a succession of parts C₁, . . . , C_N, in which each part C_i consists of a number of bytes n_i, to recover binary information P containing by a succession of parts P_i, said method comprising the steps of for each successive part C_i :

(1) generating a pseudorandom permutation T of the numbers 1, . . . n_i using a plurality of bytes of the serial keystream output;

(2) forming an intermediate part I_i by for each byte B of the part C_i

(a) generating one or more bytes of the serial keystream output; and

(b) replacing the byte B with a quantity that depends upon the byte B and the said generated byte or bytes of the serial keystream output; and

(3) permuting the relative positions of the bytes within the intermediate part I_i according to the permutation T to form the i-th part P_i of said binary information.

14. A method of combining a serial keystream with an encrypted bit stream according to claim 13 including the steps of for each successive part P_i computing a current message digest value D_i for all parts of the binary information P from its beginning up to and including P_i ;

and

obtaining and discarding a number of additional bytes of the serial keystream output, said number depending upon the current message digest value D_i.

15. A mixture generator suitable for use in a public key encryption system comprising:

a set (n) of maximal period linear shift registers,

means for selecting the output from one of n-1 of said generators to provide the output of the mixture generator,

decoding means for decoding the outputs of a plurality m of the last stages of the nth generator,

said decoder output controlling said selecting means to determine its selection of the particular generator output to use.

16. A mixture generator according to claim 15 wherein n=3 and m=1.

18. A mixture generator suitable for use in a public key encryption system comprising:

a set (n) of multiplicative congruential generators,

means for selecting the output from one of n-1 of said generators to provide the output of the mixture generator,

decoding means for decoding the outputs of a plurality m of the last stages of the nth generator,

said decoder output controlling said selecting means to determine its selection of the particular generator output to use.

19. A mixture generator according to claim 18 wherein n=3 and m=1.