Apparatus and Method for Cryptographic System Users to Obtain a Jointly Determined, Secret, Shared, and Unique Bit String

(text of the Canadian Patent Application no. 2,156,780)

CONNOTECH Experts-conseils Inc.

Table of contents

Editor's note: This document contains the integral text of the patent application, with editorial modifications required to accomodate the HTML 2 format, and also to enhance the readability of the patent application:

1. descriptive titles are interspersed in the text,
2. the references are moved to the end of the document
3. the mathematical symbols S' and S'' are replaced by S and C respectively,
4. the figure was given a title and a number.
5. ^ is the exponent operator, e.g. x^2=x²,
6. [ ] denotes subscripting, e.g. x[0], x[1], x[2], ...,
7. -> is an arrow to the right,
8. <= is less than or equal,
9. >= is greater than or equal,
10. != is not equal,
11. alpha, beta, mu, nu, and pi are the corresponding greek symbols,
12. xor is the bitwise exclusive-or operator.

Patent Classification Data

(21) (A1) Patent File No: 2,156,780

(22) Filed: 1995/08/23

(43) Laid-Open Date: 1995/09/23

(51) Intl. Cl. G09C 1/00; H04L 9/00

(54) Invention: Apparatus and Method for Cryptographic System Users to Obtain a Jointly Determined, Secret, Shared, and Unique Bit String

(72) Inventor(s): Moreau, Thierry - Canada ;

(71) Assignee of the Invention: CONNOTECH Experts-Conseils Inc. - Canada ;

(57) 16 claims

Abstract

Two users of a cryptographic system use the present invention when their respective processors need to get a jointly determined, secret, shared, and unique bit string. The present invention is effective and most useful when used over an insecure means of data transmission. After completion of the secret key exchange according to the present invention, the users proceed with further cryptographic exchanges which may use the jointly determined, secret, shared, and unique bit string produced by the present invention. The shared bit string produced by the present invention is a simple transformation of a sequence x[0], x[1], x[2], ..., x[t-1] produced by the "x² mod N" pseudo-random number generator. Secrecy is achieved by disclosing selected information about this sequence, in such a way that the sequence can be computed by both participants in the secret key exchange but by no one else. It is a distinctive characteristic of the present invention to provide a means of cryptographic authentication of user A to the benefit of user B with no more processing and little more precautions than what is required for the secret key exchange only.

Figure 1) Logical representation of the present invention

Field of the Invention

The present invention relates to a method for cryptographic system users to obtain a jointly determined, secret, shared, and unique encryption key, and apparatus for obtaining such a key.

Description of the Prior Art

Distinction between public key and secret key cryptosystems

Each cryptosystem is easily classified as either a secret key cryptosystem or a public key cryptosystem. The Data Encryption Standard (DES) is a well known secret key cryptosystem and offers significantly better performance than all known public key cryptosystems. On the other hand, public key cryptosystems offer distinctive advantages. They provide confidentiality protection without preliminary exchange of secret keys before a digital conversation. They offer the undeniable digital signature capability, a function that renders cryptographic authentication data significant not only to participants in the digital conversation but to third parties as well.

In the field of cryptography, a subtle but important distinction is made between "secret" information and "private" information. Secret information is shared between two or more users of a cryptosystem and the security is based on none of them disclosing the information to a user not part of the group. Private information is known by a single user of a cryptosystem, and is associated with some public information. Usually, private information is the private key and the corresponding public information is the public key of a private/public key pair. In public key cryptography, security is based on not disclosing the private key and making sure that the public key is indeed the one of the intended user.

Efficiency of public key cryptosystems

Many improvements to public key cryptography are aimed at benefiting from its distinctive advantages while avoiding its typical deceptive performance. Most practical public key cryptosystems are hybrid in the sense that a public key cryptographic method is used to establish secret keys of a DES or equivalent cryptosystem, a technique referred to as secret key exchange. The Diffie-Hellman cryptosystem described in USA patent document 4,200,770 [4], is the foremost example of a secret key exchange cryptosystem. Practical digital signatures are also hybrid in the sense that a cryptographic hash function is first applied to a message to reduce the input data size for the digital signature algorithm, without noticeably reducing the difficulty of forging the digital signature affixed to a message. In these two cases, for a given general purpose numerical processor, the non-public key method (DES or the hash function) is typically over 100 times faster than the public key method.

The significance of the 100-fold performance disadvantage for public key cryptosystems can be illustrated by a very crude estimate of typical processor performance requirements. The public key method is usually applied to input data of a fixed size between 512 to 1024 bits long, so we will use 768 bits of input per use of cryptographic method. Let's assume a typical application where a first cryptographic method (e.g. [4]) is used once for secret key exchange and a second cryptographic method (e.g. USA patent document 4,405,829 [7]) is used once for a digital signature, each with input size of 768 bits. Let's assume a message size of 30 K-bytes. Finally, let's assume that the processor power was designed so that the two non-public key methods (DES and the hash function) could be performed with 20% processor utilization at the nominal transmission data rate (a conservative yet realistic design factor given the declining prices of digital electronic components). Then what is the implication of the deceptive public key performance? For the first 768 bit times of the digital conversation, the system would be missing a 100x20%=2000% more powerful processor (for the initial secret key exchange). The same thing would happen for the 768 bit times at the end of the digital conversation (for the digital signature). Assuming the processor is not upgraded to a 20 times more powerful one, an initial delay and a final delay each of 15,360 bit times will be incurred. The public key cryptography overhead doubles the transmission time.

This situation is most critical for the smart card application of cryptography. The smart card application is meant to be a low-cost, mass production "electronic currency" device. In this case, one participant in the digital conversation is a smart card with very limited computing power while the other one is a service provider system with reasonable computing power. In this context, the relative performance load of cryptographic algorithms may significantly affect the usefulness of a cryptosystem. For instance, if the service provider must digitally sign a message sent to the smart card, good use can be made of a digital signature algorithm where signature verification is fast compared with signature generation.

The Schnorr cryptosystem for efficient signatures

The Schnorr cryptosystem described in USA patent document 4,995,082, [8], is an attempt to resolve the performance issue for digital signatures in the context of smart card applications. It is based on a different mathematical foundation (the discrete logarithm problem) than the present invention which is based on the "x² mod N" cryptographically strong pseudo-random number generator. The security of the "x² mod N" generator is based on the difficulty of finding square roots modulo N where N is the product of two large prime numbers.

While the Schnorr cryptosystem addresses the performance issue of digital signatures for smart cards, it is not suitable for secret key exchange. The present invention is aimed at solving the performance issue of public key cryptosystems for secret key exchange. In this sense, it can be viewed as a replacement for either the Diffie-Hellman cryptosystem [4] or the RSA cryptosystems [7] for the purpose of secret key exchange. Neither [4] nor [7] use the "x² mod N" generator.

The Diffie-Hellman cryptosystem for secret key exchange

The Diffie-Hellman cryptosystem has been disclosed at the inception of the public key cryptography, and is well known to the specialists in the trade. Practice of the Diffie-Hellman cryptosystem is illustrated in annexes C and H of ISO/IEC 11577:1994, [5]. This public disclosure of a Diffie-Hellman cryptosystem application is not easily accessible as the cryptographically significant facts are dispersed in extensive and detailed protocol specifications. Before the improvements made by [5], the Diffie-Hellman cryptosystem is well explained by the following excerpt from Brassard, [3] (pages 23-25):

"We have seen that one of the major difficulties with large scale multi-user secret-key cryptosystems is that each pair of users must share a secret key. Assume to the contrary that two given users initially share no secret information, and that they suddenly wish to establish secure communications between them. The conventional solution would be for them to meet physically in order to exchange a secret key, or to make use of some sort of trusted courier. Both these solutions are slow and expensive, and they may not be all that safe. The purpose of a public-key distribution system is to allow two such users to come up with a secret key as a result of a discussion over an insecure channel, in a way that an eventual eavesdropper cannot figure out the key after listening to the entire discussion.

"More precisely, we wish a protocol in which A and B exchange messages m[1] (from A to B), m[2] (from B to A), ..., until eventually A and B agree on some key k, in a way that it is infeasible to infer k from knowledge of m[1], m[2], ... alone. Let us stress again that this must be achieved even though A and B share no information beforehand that is unknown to the eavesdropper.

"The first protocol to achieve this seemingly impossible goal was proposed by Diffie and Hellman [4] in 1976. It is based on the discrete logarithm problem introduced in section 4.1, Let p be some large integer and let a be another integer strictly between 1 and p-1. As a first step of the protocol, A and B agree on p and a over the insecure channel (alternatively, p and a could be standard parameters used by all users of the system). Then, A chooses some large integer x and computes X=a^x mod p. Similarly, B chooses y and computes Y=a^y mod p. At this point, A and B exchange X and Y over the insecure channel but they keep x and y secret (only A knows x and only B knows y). Finally, A computes Y^x mod p; similarly, B computes X^y mod p. Both these values are equal since it amounts to a^(xy) mod p either way. This is the key k they wished to establish in common.

"The eavesdropper is faced with the task of figuring out k from the information sent over the insecure channel: a, p, X, and Y. The obvious approach for the eavesdropper would be to figure out y from a, p, and Y (or at least some ÿ such that a^ÿ mod p=Y as any such ÿ would yield X^ÿ mod p=k). However, this is precisely the discrete logarithm problem, which is believed to be infeasible. No one has yet figured out a way of computing k efficiently from a, p, X, and Y, but no one has either been able to prove that this is not possible or even that there is no better way to do so than to first compute a discrete logarithm. It is hence conceivable that the computation of k could be carried out efficiently even if the discrete logarithm problem should be genuinely infeasible."

The impersonation attack and the Diffie-Hellman cryptosystem

The above explanation ignores the impersonation attack. The impersonation attack is the case where an adversary C intercepts X from A and replaces it with V=a^v mod p which is sent to B (the adversary C selects v). The unsuspicious B uses V^y mod p as if it was X^y mod p. In the reverse direction, the adversary intercepts Y and replaces it with W=a^w mod p which is sent to A. The unsuspicious A uses W^x mod p as if it was Y^x mod p. From then on, the digital conversation from A to B passes through C which is then an active eavesdropper.

To counter the impersonation attack, [5] annexes C and H specify an optional security association protocol. The security association protocol starts with a data exchange according to [4] and is followed by the transmission of a digital signature in each direction of communication. The digital signature is affixed to a challenge message implicitly dependent on the jointly determined value k=X^y mod p=Y^x mod p. In verifying the signature received from the other participant in the digital conversation, A authenticates B as the genuine other participant. The adversary C can not replace a digital signature of V^y mod p by a signature of X^y mod p since C can not sign on behalf of B. For a more academic treatment of the impersonation attack in the context of the Diffie-Hellman cryptosystem, see [6].

Diffie-Hellman and the present invention

In summary, the Diffie-Hellman cryptosystem produces a secret value k=X^y mod p=Y^x mod p which is jointly determined by the participants in a digital conversation, and secret from a passive eavesdropper. If the application of the Diffie-Hellman cryptosystem uses a random selection process for the choice of values x and y, the secret value k is unique to a given instance of a digital conversation. When the Diffie-Hellman process is followed by authentication based on the unique value k, impersonation attacks by an active eavesdropper can be detected. By itself, the Diffie-Hellman cryptosystem does not provide authentication. Anyone can select an exponent x and compute a^x mod p.

The Diffie-Hellman cryptosystem is compute intensive. The processing load is the same for either participant. Even when the value a^x mod p is pre-computed by a participant, the computation of Y^x mod p must be done during the digital conversation and may thus create a protocol delay or latency. Although the length of a single secret value k may accommodate the key size of the DES cryptosystem, it is conceivable for an application to require more than one secret value k because a single one does not contain enough secret bits. In this case, the Diffie-Hellman cryptosystem computations are made more than once and the performance deteriorates.

The present invention is aimed at alleviating some of the difficulties with the Diffie-Hellman cryptosystem for secret key exchange. By contrast to the latter, the present invention is not symmetric: the computations and procedures are different for the initiator of the secret key exchange than for the responder. This asymmetry in computation requirements reduces the processing load for the responder of the secret key exchange. Moreover, the present invention has the capability to authenticate the initiator of the secret key exchange to the benefit of the responder, further reducing the processing load when the overall cryptographic application is considered. When the present invention is used for authentication, the prior art reported in [9], is relevant to the present invention.

Introducing the "x² mod N" pseudo-random number generator

The present invention makes use of the "x² mod N" pseudo-random number generator which is described in [1]. Mathematical properties of the "x² mod N" generator were further studied in [10]. The "x² mod N" generator generates a sequence of numbers with an interesting property for public key cryptosystems: computing the sequence in the forward direction is easy for any user from the knowledge of the parameter N while the computations are infeasible in the reverse direction, unless some private information about N is known. The "x² mod N" generator is used for the Blum-Goldwasser cryptosystem reported in [2], which is important prior art to the present invention. The Blum-Goldwasser cryptosystem is well explained in [3], pages 32-39.

Summary of the Invention

Descriptive overview

Two users of a cryptographic system use the present invention when their respective processors need to get a jointly determined, secret, shared, and unique bit string. The overall process is called the secret key exchange. A secret key exchange typically occurs at the beginning of a digital conversation. In the following description, when a user is said to do something, this user's processor is implicitly involved. The user A is the initiator of the secret key exchange. The user B is the responder of the secret key exchange. In one instance of the secret key exchange, one message is sent from the user A to the user B and then one message is sent from user B to user A. The present invention is effective and most useful when these messages are sent using an insecure means of data transmission. After completion of the secret key exchange according to the present invention, the users A and B proceed with further cryptographic exchanges in the same digital conversation, or a subsequent one. These subsequent cryptographic exchanges may use the jointly determined, secret, shared, and unique bit string produced by the present invention. In doing so, the subsequent cryptographic exchanges enforce the information security provided by the present invention. For instance, the successful decipherment of a message using a secret key extracted from the resulting bit string is a confirmation that no breach of security occurred. More examples of subsequent cryptographic exchanges are given in the prior art, notably [5].

The shared bit string produced by the present invention is a simple transformation of a sequence x[0], x[1], x[2], ..., x[t-1] produced by the "x² mod N" generator. Secrecy is achieved by disclosing selected information about this sequence, in such a way that the sequence can be computed by both participants in the secret key exchange but by no one else. The value x[t]=x[t-1]² mod N is a first piece of information that can be disclosed without breach of confidentiality as long as the private information about N is known only by the user A, the initiator of the secret key exchange. The other piece of information disclosed is partial information about x which determines the sequence by equation x[0]=x² mod N. This partial disclosure should be inconsequential to the security of the system. It is reasonable to expect the present invention to be practiced by disclosing from 2 to 15 digits of x while complete knowledge of x requires between 150 and 200 digits. The present invention incorporates means to ensure that the disclosed part of x is diffused in x itself.

It is a distinctive characteristic of the present invention to provide a means of cryptographic authentication of user A to the benefit of user B with no more processing and little more precautions than what is required for the secret key exchange only. This comes from the fact that user A is the only one to have the private knowledge about N.

Formal invention summary

According to the invention, there is provided a method for cryptographic communication between a first data processor in communication with a second data processor using a jointly determined, secret, shared, and unique encryption key, comprising the steps of:
a) providing some first arbitrary information at both the first processor and the second processor, the first arbitrary information being determined by the first processor to be sufficiently unique;
b) determining at the second processor a first value using in part the first arbitrary information and in part second arbitrary information known only to the second processor, in such a manner that a use of the first arbitrary information in determining the first value can be confirmed by analysis without knowing the second arbitrary information;
c) generating at the second processor a sequence of values starting with the first value using a pseudo-random, unpredictable-to-the-left, trap-door one-way function for which the first processor knows a private key for determining preceding values of the sequence;
d) sending from the second processor to the first processor a message including a second value from the sequence;
e) determining at the first processor at least one value for the first value using the private key and the second value;
f) confirming at the first processor that the at least one first value was determined using in part the first arbitrary information;
g) generating the encryption key using at least a part of the sequence other than the second value at the second processor and generating a same the encryption key at the first processor; and
h) communicating data between the first processor and the second processor using the encryption key if the confirming in the step (f) is positive.

Preferably, the first arbitrary information is selected by the first processor and communicated to the second. Also, the first value is determined in step (b) using bit shuffling. The bit shuffling may be carried out using shuffling parameters also sent by the first processor to the second.

The one-way function is preferably the x² mod N function, in which N is a large number having factors P and Q, with P and Q being the private key. P and Q are preferably prime numbers respecting P mod 4 = 3 and Q mod 4 = 3. The encryption key is preferably a bit string calculated by transforming the sequence values using the mod 2^k function, where k is a number of least significant bits to be retained from each value of the sequence.

According to the invention, there is also provided an apparatus for cryptographic communication with a first data processor using a jointly determined, secret, shared, and unique encryption key. The apparatus comprises a second data processor including:

means for communicating with the first processor;

means for calculating a sequence of values starting with a first value using a pseudo-random, unpredictable-to-the-left, trap-door one-way function for which the first processor knows a private key for determining preceding values of the sequence;

means for generating second arbitrary information and determining the first value using in part some first arbitrary information and in part the second arbitrary information known only to the second processor, in such a manner that a use of the first arbitrary information in determining the first value can be confirmed by analysis without knowing the second arbitrary information, the first arbitrary information being at least one of generated by the second processor, transmitted to the first processor and then confirmed as being acceptable by the first processor, and being generated by the first processor and then sent to the second processor;

means for transmitting a second value from the sequence to the first processor;

means for generating the encryption key using at least a part of the sequence other than the second value; and

means for encrypting and decrypting data using the encryption key. In this way, creation of the sequence and the encryption key in the second processor is relatively easy to compute, while confirmation of the first value containing the first arbitrary information starting with the second value is relatively compute intensive, thus allowing the encryption key to be mutually and secretly determined using a first value which is in part arbitrarily determined by the second processor alone and without requiring the apparatus to possess significant computing power.

Brief Description of the Drawing

The drawing is a schematic block diagram providing a logical representation of a preferred embodiment of the present invention.

Detailed Description of the Preferred Embodiment

There are a number of numerical parameters associated with the present invention.

Usual parameters of the "x² mod N" generator

A first parameter is the number L of bits in the required shared bit string. The context where the present invention is used will normally dictate an appropriate value for the parameter L and users A and B will normally have a priori knowledge of this value.

Another parameter is a large number N equal to the product of two distinct prime numbers, each of them giving 3 as a remainder when divided by 4 (N=P×Q where P and Q are prime, P!=Q, P mod 4=3, Q mod 4=3). The prior art about the "x² mod N" generator should be taken into account when selecting the prime numbers P and Q. Notably, it was suggested that (P-1)/2, (P-3)/4, (Q-1)/2, and (Q-3)/4 should all be prime numbers.

The parameter N is selected by the user A and the prime numbers P and Q are never disclosed. The prime numbers P and Q are the private key of user A for the present invention. If the present invention is not used to authenticate user A to the benefit of user B, it is sufficient for the prime numbers P and Q to be kept private and the parameter value N to be carried to user B by any means (e.g. as part of the first message 301 from user A to user B). If the present invention is used to authenticate user A to the benefit of user B, then the parameter N is the public key of user A for the present invention and the data integrity protection should be applied to the distribution of the parameter N value as with any public key used for authentication (e.g. with the use of a security certificate). With the known factorization algorithms, the parameter N may need to exceed 150 digits for the present invention to be provide effective security.

Another parameter is a small number k which represents the number of least significant bits to be retained at each iteration of the "x² mod N" computation. The parameter k is at least 1 and much smaller than the number of bits required to represent N. The parameter k may be selected according to the number theoretical analysis of the "x² mod N" generator found in the prior art, notably [1]. The present invention is insensitive to the means of distributing the value of the parameter k to the users A and B.

Parameters required to restrict the random seed of the generator

The last two parameters are numbers S and C used to shuffle the bits of two numbers, and such that 4/C is an acceptable upper limit to the probability that a replay or impersonation attack targeting user A would remain undetected by the present invention. The parameter S and C can be as small as 1 but if C is very small, some protection is lost. The parameters S and C must be selected such that C×S<N.

The bit shuffling 202 proceeds as follows. In the secret key exchange, x[A->B] is a random integer selected by user A and transmitted in the clear to user B. The valid range for x[A->B] is 0<=x[A->B]<C. The integer x[B¦] is also random, but selected by user B and never disclosed. The valid range for x[B¦] is 0<=x[B¦]<=N/C. Together, x[A->B] and x[B¦] jointly determine a number x computed as x=(|_x[B¦]/S_|×C×S)+(x[A->B]×S)+(x[B¦] mod S), where |_a/b_| is the integer division of a by b. As a simple example, let C=16 and S=16. Then x[A->B] represents the before last digit in the hexadecimal representation of x, and x[B¦] determines all other digits of x. Intuitively, the number x is a "mostly secret" number. The number of "disclosed bits" is the size of (C-1) in bits. The size of (S-1) in bits represents the "left shift" of the disclosed bits from the least significant bit positions. This explanation holds when S and C are exact powers of 2. With unrestricted values of S and C, the shuffling of x[A->B] bits in x is more cryptic.

The parameters S and C can be changed from time to time to increase the secret key exchange security. The magnitude of the parameter C indicates the size of the partial information disclosed about x. Even a small change in the parameter values alters the bit shuffling 202. It is thus possible to practice the present invention by selecting new values for parameters S and C at each occurrence of a secret key exchange when the number x[A->B] is randomly selected 101 and sending them along with x[A->B] in the first message 301 of the secret key exchange.

Sequence of operations in an execution of the secret key exchange

The secret key exchange begins with the user A selecting 101 the random number x[A->B]. The user A sends x[A->B] to user B as the first message 301 in the secret key exchange. Depending on the application details, any or all of the parameters L, N, k, S and C may accompany the value x[A->B] in this first message 301. The user B then selects 201 a random number x[B¦], computes x from x[A->B] and x[B¦] using the bit shuffling 202, and checks that 1<x<N-1 (otherwise a new x[B¦] is selected). The number x[B¦] is never disclosed. Let t be |_(L+k-1)/k_| (thus, t>=1). Then, user B computes the sequence 203, x[0], x[1], x[2], ..., x[i], ..., x[t-1], and x[t] with the following equations:

x[0] = x² mod N
x[1] = x[0]² mod N
x[2] = x[1]² mod N
...
x[i] = x[i-1]² mod N
...
x[t-1] = x[t-2]² mod N
x[t] = x[t-1]² mod N

All x[i] values in the sequence 203 are kept secret. The user B sends x[t] to the user A as the second message 302 in the secret key exchange.

Upon receipt of the second message 302, the user A performs the inverse x^(2^(t-1)) mod N computation 102 based on the private knowledge of the prime factors P and Q (^ stands for the exponentiation operation).

To make the inverse x^(2^(t-1)) mod N computation 102 more efficient, the user A may pre-compute integers a and b such that a×P+b×Q=1 (using the generalized Euclid algorithm), and integers alpha and beta:

alpha = ((P+1)/4)^(t+1) mod (P-1), and
beta = ((Q+1)/4)^(t+1) mod (Q-1).

In the inverse x^(2^(t-1)) mod N computation 102, the user A recovers the four possible values for x and the exact value for x[0]. This recovery starts with the following computations:

mu = (x[t] mod P)^alpha mod P, and
nu = (x[t] mod Q)^beta mod Q.

The user A may then compute the four possible values for x:

e = (b×Q×mu + a×P×nu) mod N,
f = (b×Q×(P-mu) + a×P×nu) mod N,
g = (b×Q×mu + a×P×(Q-nu)) mod N, and
h = (b×Q×(P-mu) + a×P×(Q-nu)) mod N,

and the exact value of x[0]:

x[0] = e² mod N.

In the bit shuffling test 103, the user A verifies that at least one of the following equality is true

x[A->B] = |_e/S_| mod C,
x[A->B] = |_f/S_| mod C,
x[A->B] = |_g/S_| mod C, or
x[A->B] = |_h/S_| mod C.

If none of the above equality holds, the received x[t] value was selected without due consideration of the x[A->B] sent by the user A (possibly with a method or a device which is not practicing the present invention). Consequently, an error is detected and a later check of timeliness or detection of replay or impersonation attack will be unreliable (if based on the shared bit string).

From the recovered x[0], the user A can recover the other secret x[i] values using the same computations as the user B. This is done in step 104.

The jointly determined, secret, shared, and unique bit string is the concatenation w of B[i] values for i=0,1,2 ..., t-1 where each B[i] = x[i] mod 2^k (notation w=B[0]|B[1]|B[2]|...|B[t-1]). This computation is made independently by user A and user B, respectively in steps 105 and 204 which may be performed concomitantly with steps 104 and 203 respectively. Depending on the application details, the users A and B may subsequently use subsets of the bit string as encipherment keys, secret initial values for hash functions, and data to be digitally signed as part of cryptographic authentication procedures.

Sample C source code

An example of source code in the C programming language for carrying out the above described calculations and steps is given in example 'A' hereinbelow.

Properties and variations of the invention

It should be obvious to someone knowledgeable of the field of cryptology and applied cryptography that the processing load for user B is small compared to other methods for secret key exchange.

In reference to the prior art of public key cryptography theory, the present invention is based on the trap-door one-way function f[N](x)=x² mod N where N is a product of two distinct primes numbers congruent to 3 modulo 4. The private trap-door information (the private key) is the factorization of N (the two distinct prime numbers) which allow efficient computation of "square roots" modulo N. With the present invention, an unpredictable-to-the-left pseudo-random number generating function is constructed from a trap-door one-way function. Mathematically, this is represented as a function g:SxZ+->SxW where S is the set of possible seeds for the specific generator, Z+ is the set of integers greater than zero, and W is the set of bit strings. In the case of the "x² mod N" generator, the function g is g(x,L)=(x[t],w) where x, L, x[t], and w are as described above.

Without departing from the spirit and intent of the present invention, many variations are possible as should be obvious to someone knowledgeable of the field of cryptology and applied cryptography. Observing that inputs S, C, and x[A->B] to the bit shuffling 202 are effectively restricting the possible choices for x by a factor of C, any formulation of a restriction on x that can be conveyed in the first message 301 and verified by the bit shuffling test 103 falls within the spirit of the present invention. Yet another obvious variation to the present invention is to redefine x[0]=x^(2^t') mod N for some additional parameter t'>=1 (the preceding disclosure of the present invention implicitly uses t'=1). This variation introduces more "x² mod N" pseudo-randomness into x[0].

When the value x is output by the bit shuffling 202, a verification that x and N are relatively prime can be done. This would make the present invention more conforming to the mathematical foundation of the "x² mod N" generator. But the usefulness of this verification should be weighted against the infinitesimal probability (P+Q)/N of a failure and the processing requirement for this verification. In case x and N are not relatively prime, a new x[B¦] is selected.

Invention security, general principles

In order to fully disclose the present invention, a detailed analysis of its security follows. The cryptographic security of the present invention is described in terms other than a formal mathematical development. It is a characteristic of the present invention that the bit shuffling from x[A->B] into x is more of an heuristic nature than a result of formal mathematical deductions.

An eavesdropper can not recover any of the secret x[i] from the knowledge of N, S, C, x[A->B], x[t], k, L, and t. With a large enough N, neither the user B nor an eavesdropper can find the prime numbers P and Q. Without knowledge of the prime factors of N, finding an x[i-1] value given x[i] = x[i-1]² mod N is known to be computationally infeasible. The sequence x, x[0], x[1], x[2], ..., x[t-1], x[t] is easy to compute from left to right, but computationally infeasible from right to left (the "x² mod N" generator is said to be unpredictable to the left).

The knowledge of x[A->B] should give the eavesdropper insufficient information for the computation of the secret x[i] values. In selecting the order of magnitude for the parameter C, a trade-off must be made between the quantity of information offered to the eavesdropper through x[A->B] and the probability 4/C that a replay or impersonation attack targeting user A would remain undetected by the present invention. If S and C were respectively 1 and N, the disclosed x[A->B] value would completely determine x and the sequence x[0], x[1], x[2], ..., x[t-1]. At the other extreme, if C=1, x[A->B] is a constant, the secret x[B¦] completely determines the sequence x[0], x[1], x[2], ..., x[t-1], but the same sequence can be used more than once (e.g. by an impostor attempting a replay attack). A practical trade-off is possible considering 1) the magnitude of N, which accounts for the known factorization algorithms, 2) the plausibility of a replay or impersonation attack given that it is detected by the present invention with a probability 1-4/C, and 3) the ease with which the C magnitude can be increased after the detection of a first replay or impersonation attack.

Invention security, Blum-Goldwasser probabilistic encryption

Some principles of the Blum-Goldwasser probabilistic cryptosystem [2] are applied by the present invention. In order to disclose the security built in the present invention, it is useful to relate the two cryptosystems. The Blum-Goldwasser cryptosystem is related to the present invention in the following way:
1) In the Blum-Goldwasser cryptosystem, the bit sequence w=B[0]|B[1]|B[2]|...|B[t-1] serves as a one-time-pad to encipher a message m with the bitwise exclusive-or operation, xor. The resulting ciphertext m xor w is transmitted and thus available to the eavesdropper. With the intended usage of the present invention, it is unlikely that any portion of the bit sequence w is going to be available to the eavesdropper (since a portion of the bit sequence w is precisely intended as a secret key for the encipherment algorithm which protects the remaining of the digital conversation from the eavesdropper).
2) Both in the Blum-Goldwasser cryptosystem and in the present invention, x[t] is transmitted in the clear and readily available to the eavesdropper.
3) In the Blum-Goldwasser cryptosystem, x[t] is unrestricted, but for the fact that some value v exists where x[t]=v² mod N. In the present invention, x[t] is additionally restricted to a fraction 4/C of all possible values, as determined by x[A->B] which is transmitted in the clear and readily available to the eavesdropper.
4) Public knowledge is assumed for N, k and t. In the case of the present invention, S and C are assumed public as well.

The Blum-Goldwasser cryptosystem is known to be secure against a cyphertext-only attack. Under this form of attack, the adversary is given the ciphertext m xor w and the value x[t] for a number of messages. Under a cyphertext-only attack, the present invention gives x[A->B] and x[t] to the adversary for a number of digital conversations. The security of the present invention under the ciphertext-only attack is based on the shuffling of bits from x[A->B] into x, and the pseudo-randomness of the sequence x, x[0], x[1], x[2], ..., x[t-1], x[t]. The theoretical foundation of the "x² mod N" generator indicates that the pseudo-randomness is as effective for t=1 (leading to a short sequence x, x[0], x[1]) as for any other value of t.

The Blum-Goldwasser cryptosystem is known to be weak against a chosen cyphertext attack. Under this form of attack, the adversary has temporary access to the deciphering equipment, is free to submit any cyphertext he wants and to observe the corresponding cleartext. With the chosen cyphertext attack, the adversary can decipher a previously observed ciphertext but this trivial case is not so relevant to the overall security of the Blum-Goldwasser cryptosystem. The prior art reports that under the chosen cyphertext attack, the adversary has the capability to find the prime factors P and Q of the parameter N, and thus he may decipher any message m xor w from x[t] at any later time.

For the understanding of the security offered by the present invention, it is not necessary to understand exactly how the adversary can factor N from the information gathered by the chosen cyphertext attack of the Blum-Goldwasser cryptosystem. It is sufficient to understand what information is gathered and to understand that the present invention does not provide the equivalent information. Under the chosen cyphertext attack, the adversary submits any cyphertext c with x[t]=v² mod N for some selected value v. An intelligent selection process for the value v is an essential component of the successful factorization of N with the chosen cyphertext attack. The adversary then gets a deciphered meaningless message m[c] such that c=m[c] xor w and thus gets the bit sequence w=B[0]|B[1]|B[2]|...|B[t-1] for this x[t]. The theory shows that there are exactly four possible values for v, and only one of them, namely x[t-1], is itself a quadratic residue of the form u² mod N for some value u. Thus, with the Blum-Goldwasser cryptosystem, the ability to choose v without restriction and then get some information about the corresponding x[t-1], namely the k least significant bits of x[t-1], opens the door to the factorization of N.

With the present invention, x[t] is partially determined by x[A->B]. Thus, if the adversary submits an arbitrary x[t] value, the present invention will detect something going wrong with a probability of 1-4/C. The shuffling of bits from x[A->B] into x and the pseudo-randomness of the sequence x, x[0], x[1], x[2], ..., x[t-1], x[t] makes it impossible to find a value v satisfying both the said intelligent selection process and being correctly determined by x[A->B] (unless the factors of N are already known). A skilled mathematician may see as an example of a selection process for v that the adversary may at some point look for a value v having a Jacoby symbol with respect to N equal to -1 and such that v² mod N=x[t] for some x[t] partially determined by x[A->B] and compute gcd(v+x[t-1],N)=P or Q (see [1] on page 373).

Even if an appropriate value v could be found, the present invention does not disclose B[0]|B[1]|B[2]|...|B[t-1] as the Blum-Goldwasser cryptosystem does. An adversary could hope to select the value x satisfying the said intelligent selection process (after all, the adversary has N/C choices for x). But then, the wanted information would be B[-1] which is not even considered by the present invention.

With the preceding discussion of the chosen cyphertext attack, let's assume that the subsequent digital conversation does indeed reveal a portion of the sequence B[0]|B[1]|B[2]|...|B[t-1]. For instance, say a digital signature of a portion of this sequence inadvertently discloses the least significant bit of B[t-1] (a case where the theory on the "x² mod N" generator is very useful to the adversary). Then a chosen cyphertext attack could repeatedly submit an arbitrary x[t] without regard to x[A->B], and make use of the rare occasions (with a probability 4/C) where the present invention would not detect the attack and disclose the least significant bit of B[t-1]. In this case, increasing the magnitude of C may not be effective. Then, changing the parameter N may be the proper thing to do.

This last observation on the security of the present invention explains why it is more useful for secret key exchange than for public key encryption. The shuffling of bits from x[A->B] into x could be applied to the Blum-Goldwasser cryptosystems for messages sent from user B to user A (to detect chosen ciphertext attacks). But a combination of two objections may be raised. First, with public key encryption, the chosen cyphertext attack is a more than an academic threat. Second, with public key encryption, each user A must publish its parameter N. With the publication requirement, changing the parameter N can be a relatively costly operation. At the same time, changing the parameter N would be the appropriate countermeasure upon detection of repeated chosen cyphertext attack. On the contrary, for the secret key exchange, the chosen cyphertext attack is a very remote possibility. With a properly secured digital conversation following the secret key exchange using the present invention, no portion of the sequence B[0]|B[1]|B[2]|...|B[t-1] is ever disclosed and the chosen ciphertext attack threat disappear.

Invention security, authentication

Subsequent to the successful secret key exchange according to the present invention, the user B will notice that user A indeed knows the sequence B[0]|B[1]|B[2]|...|B[t-1]. Then, the user B gets a cryptographic assurance that his correspondent in the digital conversation knows the factors P and Q. Hence user A is authenticated by the present invention to the benefit of user B. In other words, if the user B has assurance that the specific parameter N used in a given secret key exchange is the public key of user A, impersonation attacks targeted at user B must be based on knowledge of the factors P and Q of this parameter N. This type of attack is typical of public key cryptography and relates to privacy of P and Q and to the integrity protection for the parameter N during its transmission to user B and storage in the user B's cryptographic device. If user B has doubts about the authenticity of the parameter N as the user A's public key, the security of the present invention for an impersonation attack targeted at user B is not different from the prior art of the Diffie-Hellman cryptosystem.

Example 'A': Source Code in C

This program is in a separate document.

Test results using the above program
with the x**2 mod 16873 generator

Sample 1, secret bit string: 44719864F65C4DF0B0F1CEEC972BC709
Sample 2, secret bit string: D23D79EDAC8C987389237097AEEF8C46
Sample 3, secret bit string: BC9CBF019C9E1BA4EA1F81721EBD5B77
Sample 4, secret bit string: CEB4A81173C0956818EB28A31E581D35
Duplicate secret bit string: 68F4CF8BBA09C8B4A617E5416D1CBBE1
Found 1 duplicates in 100 samples
Eavesdropping was successful 3 times out of 104 opportunities
Out of 100 attacks, 78 were detected (0 special)
Out of 100 dumb responses, 94 were detected (9 special)

Test results using the above program
with the x**2 mod 16537 generator

Sample 1, secret bit string: 71A7A3465BC111070BC0BD5F99D8063E
Sample 2, secret bit string: 5CEA600083195E0A373007722CA73282
Sample 3, secret bit string: 51C42FEA973C351BD58B1179C503BBF5
Sample 4, secret bit string: 7F32E95F3D7AD10047729566697AB3BB
Duplicate secret bit string: DEBAAC69FCE3F200DDDC7798FDF4A236
Duplicate secret bit string: F32E8EAB5D34F070CE6395BB8642F555
Found 2 duplicates in 100 samples
Eavesdropping was successful 8 times out of 104 opportunities
Out of 100 attacks, 81 were detected (0 special)
Out of 100 dumb responses, 95 were detected (12 special)

Claims

The embodiments of the invention in which an exclusive property or privilege is claimed are defined as follows:

1. A method for cryptographic communication between a first data processor in communication with a second data processor using a jointly determined, secret, shared, and unique encryption key, the method comprising the steps of:
a) providing some first arbitrary information at both said first processor and said second processor, said first arbitrary information being determined by said first processor to be sufficiently unique;
b) determining at said second processor a first value using in part said first arbitrary information and in part second arbitrary information known only to said second processor, in such a manner that a use of said first arbitrary information in determining said first value can be confirmed by analysis without knowing said second arbitrary information;
c) generating at said second processor a sequence of values starting with said first value using a pseudo-random, unpredictable-to-the-left, trap-door one-way function for which said first processor knows a private key for determining preceding values of said sequence;
d) sending from said second processor to said first processor a message including a second value from said sequence;
e) determining at said first processor at least one value for said first value using said private key and said second value;
f) confirming at said first processor that said at least one first value was determined using in part said first arbitrary information;
g) generating said encryption key using at least a part of said sequence other than said second value at said second processor and generating a same said encryption key at said first processor; and
h) communicating data between said first processor and said second processor using said encryption key if said confirming in said step (f) is positive.

2. The method as claimed in claim 1, wherein said step (a) comprises selecting said first arbitrary information at said first processor and sending said first arbitrary information to said second processor.

3. The method as claimed in claim 1 or 2, wherein said step (b) comprises bit shuffling said first and said second arbitrary information.

4. The method as claimed in claim 3, wherein said step (a) further comprises sending at least one shuffling parameter in addition to said first arbitrary information, and said bit shuffling is carried out using said at least one shuffling parameter.

5. The method as claimed in claim 1,2 or 4, wherein said function used in said step (c) is an x² mod N function, wherein N is a large number having factors P and Q, said factors P and Q being known to said first processor and constituting said private key.

6. The method as claimed in claim 5, wherein P and Q are two distinct prime numbers, each of said prime numbers giving 3 as a remainder when divided by 4.

7. The method as claimed in claim 3, wherein said function used in said step (c) is an x² mod N function, wherein N is a large number having factors P and Q, said factors P and Q being known to said first processor and constituting said private key.

8. The method as claimed in claim 7, wherein P and Q are two distinct prime numbers, each of said prime numbers giving 3 as a remainder when divided by 4.

9. The method as claimed in claim 1, wherein said second value is a final value of said sequence, said encryption key being generated using all values of said sequence except said final value.

10. The method as claimed in claim 1 or 9, wherein said encryption key comprises a bit string composed of a key function of at least some of said sequence of values, said key function being mod 2^k, where k is a number of least significant bits to be retained from each value of said sequence of values.

11. An apparatus for cryptographic communication with a first data processor using a jointly determined, secret, shared, and unique encryption key, comprising a second data processor including:

means for communicating with said first processor;

means for calculating a sequence of values starting with a first value using a pseudo-random, unpredictable-to-the-left, trap-door one-way function for which said first processor knows a private key for determining preceding values of said sequence;

means for generating second arbitrary information and determining said first value using in part some first arbitrary information and in part said second arbitrary information known only to said second processor, in such a manner that a use of said first arbitrary information in determining said first value can be confirmed by analysis without knowing said second arbitrary information, said first arbitrary information being at least one of generated by said second processor, transmitted to said first processor and then confirmed as being acceptable by said first processor, and being generated by said first processor and then sent to said second processor;

means for transmitting a second value from said sequence to said first processor;

means for generating said encryption key using at least a part of said sequence other than said second value; and

means for encrypting and decrypting data using said encryption key, whereby creation of said sequence and said encryption key in said second processor is relatively easy to compute, while confirmation of said first value containing said first arbitrary information starting with said second value is relatively compute intensive, thus allowing said encryption key to be mutually and secretly determined using a first value which is in part arbitrarily determined by said second processor alone and without requiring said apparatus to possess significant computing power.

12. The apparatus as claimed in claim 11, wherein said means for generating and determining carry out bit shuffling of said first and said second arbitrary information.

13. The apparatus as claimed in claim 11, wherein said function used in said calculating means is an x² mod N function, wherein N is a large number having factors P and Q, said factors P and Q being known to said first processor and constituting said private key.

14. The apparatus as claimed in claim 13, wherein P and Q are two distinct prime numbers, each of said prime numbers giving 3 as a remainder when divided by 4.

15. The apparatus as claimed in claim 11, wherein said second value is a final value of said sequence, said encryption key being generated using all values of said sequence except said final value.

16. The apparatus as claimed in claim 11,12,13,14 or 15, wherein said apparatus is provided in a smart card.

References

[1] Blum, Leonore, Blum, Manuel, and Shub, M., A Simple Unpredictable Pseudo-random Number Generator, SIAM Journal of Computing, vol. 15, no. 2, May 1986, pp 364-383

[2] Blum, Manuel, and Goldwasser, Shafi, An Efficient Probabilistic Public-key Encryption Scheme which Hides All Partial Information, In Advances in Cryptology: Proceedings of Crypto'84, Springer-Verlag, 1985, pp 289-299

[3] Brassard, Gilles, Modern Cryptology, a Tutorial, Lecture Notes in Computer Science, no. 325, Springer-Verlag, 1988

[4] USA patent document 4,200,770 Hellman, Martin E., Diffie, Bailey Whitfield, Merkle, Ralph C., Cryptographic Apparatus and Method, April 29, 1980 (the Canadian equivalent to this patent is patent number 1,121,480)

[5] ISO/IEC 11577:1994, Information Technology - Telecommunication and Information Exchange Between Systems - Open Systems Interconnection - Network Layer Security Protocol, also published as ITU-T Recommendation X.273(1994)

[6] Lim, Chae Hoon, and Lee, Pil Joong, Several Protocols for Authentication and Key Exchange, in Information Processing Letters 53 (1995) 91-96

[7] USA patent document 4,405,829 Rivest, Ronald L., Shamir, Adi, Adleman, Leonard M., Cryptographic Communications System and Method, September 20, 1983

[8] USA patent document 4,995,082, Schnorr, Claus P., Method for Identifying Subscribers and for Generating and Verifying Electronic Signatures in a Data Exchange System, February 19, 1991

[9] Tardo, J.J., and Alagappan, K., SPX: Global Authentication Using Public Key Certificates, in Proceedings of the 1991 IEEE Computer Society Symposium on Research in Security and Privacy, 1991, pp 232-244

[10] Vazirani, Umesh V., and Vazirani, Vijay V., Efficient and Secure Pseudo-random Number Generation, Proceedings of the 25th IEEE Symposium on the Foundations of Computer Science, 1984, pp 458-463

CONNOTECH Experts-conseils Inc.
9130 Place de Montgolfier
Montréal, Québec, Canada, H2M 2A1
Tél.: +1-514-385-5691 Fax: +1-514-385-5900