Probabilistic Encryption Key Exchange

Copy of

Moreau, Thierry, Probabilistic Encryption Key Exchange, Electronics Letters, Vol. 31, number 25 (7 December 1995), pp. 2166-2168

© 1995: The Institution of Electrical Engineers
Reproduced by the author with authorisation from the publisher, the Institution of Electrical Engineers. The author is affiliated with CONNOTECH Experts-conseils Inc. The Electronics Letters journal home page is

T. Moreau

Indexing terms: Cryptography, Information theory, Public key cryptography

A novel secret key exchange algorithm is proposed. It is based on the properties of the Blum Blum and Shub pseudo-random number generator (the 'x² mod N' generator), and on partial disclosure of the secret seed for this generator. The security and other features of the proposed cryptosystem are discussed.

Arithmetic Notation introduced for copying to the www format:


The need for secret key exchange algorithms has been addressed by early public key cryptosystems [1] as well as recent ones [2]. A secret key exchange is defined as a protocol interaction between unrelated parties that gives them a shared secret bit string from the uniform distribution [3]. As in [1], we limit the protocol to two messages, one initiating message and one response message, from the initiator party and the responder party, respectively. Unrelatedness is defined as the absence of both an alternate secret key distribution channel and on-line access to a third party. It is also necessary to provide assurance to both parties that the bit string is unique to a particular key exchange session. This is achieved if the bit string is jointly determined from random numbers.

We propose a novel secret key exchange algorithm in which security is partially based on the Blum-Goldwasser probabilistic encryption cryptosystem [4] and the mathematical properties of the BBS pseudo-random number generator [5-7]. For a tutorial presentation, see [8]. Our proposal exhibits interesting properties for actual use in cryptographic applications: (i) a low processing load for the responder, (ii) optional authentication of the initiator for the benefit of the responder, and (iii) possibly some resilience to (and a means of remote detection for) the responder's random source failure. Under the client-server computing paradigm, the initiator is a server and the responder is a client.

Theoretical results concerning BBS generator

For our purpose, the BBS generator is a one-way trap-door function having public key N equal to the product of two prime numbers P and Q. A seed of the BBS generator is a number x which is relatively prime to N (in practice, testing this condition may be avoided given the infinitesimal probability (P+Q)/N of a failure). The BBS generator computes a sequence x0, x1, x2, ..., xt-1, xt where x0 = x² mod N, and xi = xi-1² mod N. The BBS keystream w is defined as w=B0|B1|B2|...|Bt-1, where Bi = xi mod 2k and | represents concatenation of k-bit integers. The numbers t and k are system parameters.

The one-way trap-door function is represented as gN,t,k:X->W×X where X is the set of possible seeds, and W is the set of bit strings of length t×k. This function is gN,t,k(x)=(w,xt). Finding w from xt is also computationally infeasible [5,6]. The trap-door information is the private key (P,Q) which allows efficient computation of the inverse function inv(gN,t,k) (see appendix). Formally, gN,t,k is not precisely a one-way trap-door function since its inverse inv(gN,t,k) does not give x exactly but four possible values e, f, g, h, for x. The efficient computation of inv(gN,t,k) does not require knowledge of w.

The original Blum-Goldwasser probabilistic cryptosystem [4] encrypts a binary message M of length t×k as (M XOR w,xt) from a random x (hence 'probabilistic') and a public N. Then, knowledge of (P,Q) is required to fully recover the keystream w, hence M.

Definition of the probabilistic encryption key exchange

The probabilistic encryption key exchange (PEKE) cryptosystem is an adaptation of the Blum-Goldwasser cryptosystem for the task of secret key exchange. In PEKE, the BBS keystream w is simply the shared secret bit string output. The initiator selects P and Q as its private key and may distribute N as its public key. The initiator randomly selects a verifiable constraint on x and conveys it to the responder within the initiating message. If the PEKE optional authentication feature is not needed, the number N can conveniently be part of the initiating message as well. The constraint may restrict the set of say N  about 10200 possible values for x by a factor of say C about 107. The responder selects a random x meeting the verifiable constraint and easily computes w and xt. The response message of the PEKE cryptosystem consists of xt from which the initiator recovers the four possible values e, f, g, h for x. The initiator checks that at least one of them meets the verifiable constraint, and then computes w from any one of them.

The proposed verifiable constraint on x is based on two positive integers S and C used to shuffle the bits of two random numbers xA->B and x, where 0<C×S<N, 0<=xA->B<C, and 0<=x<=N/C. The number xA->B is selected by the initiator. The verifiable constraint is expressed as the triplet (S,C,xA->B) which is carried within the initiating message. The number x is selected by the responder and kept secret. Together, xA->B and x jointly determine the BBS seed x computed as x=(|_x/S_|×S×C)+(xA->B×S)+(x mod S), where |_a/b_| represents the integer division of a by b. This form of constraint is easily verifiable by the initiator having recovered e, f, g, and h from xt.

To illustrate, let C=256 and S=16. Then xA->B represents the two before last digits in the hexadecimal representation of x, and x determines all other digits of x. Intuitively, the number x is a 'mostly secret' number. The number of 'disclosed bits' is log2(C). Also, log2(S) 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 xA->B bits in x is more cryptic. It is certainly wise to vary S and C occasionally.

Security of the proposal

The eavesdropper sees only the constraint and the value xt and thus cannot compute w, as long as P, Q and x are concealed. A failure of the constraint verification process indicates that the received xt value was selected without due consideration of the initiating message, and thus detects replay attacks. By constraining the BBS seed x (and indirectly xt) we prevent the chosen cyphertext attack that otherwise threatens the Blum-Goldwasser cryptosystem. Elaborate cryptanalysis should be complicated by (i) the indeterminate quadratic residuacy of x and (ii) the randomness in the transformation of the partial information xA->B into xt (or even x0).

Some precautions are recommended in using the PEKE cryptosystem output, w. The theory on the BBS generator focuses on the information that can be inferred from the least significant bit of xt-1. All bits of w should be hidden from an eavesdropper to prevent elaborate statistical attacks. This can be achieved by using portions of w as encipherment keys, or as secret initial values of message authentication codes; and by encrypting digital signatures of portions of w.

The proposal has other properties which should be noted.

Processing load for responder

A single run of the PEKE requires t+1 squaring operations modulo N from the part of the responder, and a few operations on S and C. Altogether, this is a light load for a public key cryptosystem. We expect that careful examination of [6] could lead to PEKE implementations with k large enough to get t=4.

Optional authentication of initiator

According to the principles of public key cryptography, given appropriate integrity protection for the distribution and storage of the public key N, the successful completion of cryptographic processes based on w confirms the identity of the initiator from the responder's perspective.

Reaction to failure of responder's random source

In the case of an unexpected condition where the random number x becomes a constant on successive runs of the PEKE, the number xt becomes restricted to a set of C possible values. The randomness in the transformation of xA->B into xt makes the failure not trivial to detect by an eavesdropper. Nonetheless, the initiator can recover x as part of the constraint verification process (with a high probability, a single one of the four possible values for x will meet the constraint). Occurrence of a constant value of x in successive runs of the PEKE for a given responder is an indication of the responder's random source failure.

Appendix - implementation considerations

Selection of N. To guarantee the maximum period for the BBS generator (the smallest pi such that xpi=x0), theorem 8 of [5] requires the prime factors of N to be of the form 4p+3 where 2p+1 and p are also prime. The Rabin probabilistic primality test [9] can be run in parallel for these three numbers and aborted as soon as any of them is known to be composite. Another simple algorithmic improvement comes from the observation that for a base B where p=p1×B+p0 and p1>0, the least significant digit p0 is limited to a small set of values. In [10] the sequence M1406 for p is given with B=10 and p0 either 1 or 9. Preliminary results (using B=2310) show workable processing times for 512 and 640 bits N.

Computation of inv(gN,t,k) (theorem 10b of [5]). The initiator can recover four possible values for the BBS seed x from xt and its knowledge of P and Q. To make computations more efficient, the initiator 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)
beta = ((Q+1)/4)(t+1) mod (Q-1)

Given an xt, recovery starts with the following computations:

µ = (xt mod P)alpha mod P
nu = (xt mod Q)beta mod Q

The initiator may then compute the four possible values for x:

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

where x0 = e² mod N = f² mod N = g² mod N = h² mod N.

4 September 1995

© IEE 1995
Electronics Letters Online No. 19951499

T. Moreau (CONNOTECH Experts-conseils Inc., 9130 Place de Montgolfier, Montréal, Qc, H2M 2A1 Canada)

Patent application filed in Canada on August 23, 1995; application number 2,156,780


[1] DIFFIE, W., and HELLMAN, M.E.: New directions in cryptography, IEEE Trans., 1976, IT-22, pp. 644-654

[2] HARN, L.: Modified key agreement protocol based on the digital signature standard, Electron. Lett., 1995, 31, (6), pp. 448-449

[3] WALDVOGEL, C.P., and MASSEY, J.L.: The probability distribution of the Diffie-Hellman key, Advances in cryptology, AUSCRYPT'92, 1992, Lect. Notes Comput. Sci. (718), (Springer Verlag), pp. 492-504

[4] BLUM, M., and GOLDWASSER, S.: An efficient probabilistic public-key encryption scheme which hides all partial information, Advances in Cryptology: Proc. of Crypto'84, 1985, (Springer-Verlag), pp. 289-299

[5] BLUM, L., BLUM, M., and SHUB, M.: A simple unpredictable pseudo-random number generator, SIAM J. Comput., 1986, 15, (2), pp. 364-383

[6] VAZIRANI, U.V., and VAZIRANI, V.V.: Efficient and secure pseudo-random number generation, Proc. 25th IEEE Symp. on the Foundations of Comput. Sci., 1984, pp. 458-463

[7] L'ÉCUYER, P., and PROULX, R.: About polynomial-time 'upredictable' generators, Proc. 1989 Winter Simulation Conf., 1989, pp. 467-476

[8] BRASSARD, G.: Modern cryptology, a tutorial, Lect. Notes Comput. Sci., (325), (Springer-Verlag), 1988

[9] RABIN, M.O.: Probabilistic algorithm for testing primality, J. Number Theory, 1980, 12, pp. 128-138

[10] SLOANE, N.J.A., and PLOUFFE, S.: The encyclopedia of integer sequences, (Academic Press, San Diego, CA, 1995)

security scheme designalternative to PKIpatent publicationsSAKEMscholarly web contentsconsulting services ]
[ CONNOTECH home page: us | e-mail to: ]

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