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
http://www.iee.org.uk/publish/journals/profjrnl/eleclett.html

T. Moreau

Indexing terms: Cryptography, Information theory, Public key cryptographyA 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:

`->`

is an arrow to the right,`<=`

is less than or equal,`alpha`

,`beta`

,`µ`

,`nu`

, and`pi`

are the corresponding greek symbols,`XOR`

is the bitwise exclusive-or operator,`inv( )`

is the inverse of a function.

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.

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
`x`

where
_{0}, x_{1}, x_{2}, ..., x_{t-1}, x_{t}`x`

, and
_{0} = x² mod
N`x`

. The BBS keystream
_{i} = x_{i-1}² mod
N`w`

is defined as
`w=B`

, where
_{0}|B_{1}|B_{2}|...|B_{t-1}`B`

and
_{i} = x_{i} mod 2^{k}`|`

represents concatenation of
`k`

-bit integers. The numbers
`t`

and
`k`

are system parameters.

The one-way trap-door function is represented as
`g`

where
_{N,t,k}:X->W×X`X`

is the set of possible seeds, and
`W`

is the set of bit strings of length
`t×k`

. This function is
`g`

. Finding
_{N,t,k}(x)=(w,x_{t})`w`

from
`x`

is also computationally infeasible
[5,6]. The trap-door information is the private key
_{t}`(P,Q)`

which allows efficient computation of the inverse function
`inv(g`

(see appendix). Formally,
_{N,t,k})`g`

is not precisely a one-way trap-door function since its inverse
_{N,t,k}`inv(g`

does not give
_{N,t,k})`x`

exactly but four possible values
`e`

,
`f`

,
`g`

,
`h`

, for
`x`

. The efficient computation of
`inv(g`

does not require knowledge of
_{N,t,k})`w`

.

`M`

of length
`t×k`

as
`(M XOR w,x`_{t})

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`

.
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
`10`

possible values for
^{200}`x`

by a factor of say
`C`

about
`10`

. The responder selects a random
^{7}`x`

meeting the verifiable constraint and easily computes
`w`

and
`x`

. The response message of the PEKE cryptosystem consists of
_{t}`x`

from which the initiator recovers the four possible values
_{t}`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
`x`

and
_{A->B}`x`

, where
_{B¦}`0<C×S<N`

,
`0<=x`

, and
_{A->B}<C`0<=x`

. The number
_{B¦}<=N/C`x`

is selected by the initiator. The verifiable constraint is expressed
as the triplet
_{A->B}`(S,C,x`

which is carried within the initiating message. The number
_{A->B})`x`

is selected by the responder and kept secret. Together,
_{B¦}`x`

and
_{A->B}`x`

jointly determine the BBS seed
_{B¦}`x`

computed as
`x=(|_x`

, where
_{B¦}/S_|×S×C)+(x_{A->B}×S)+(x_{B¦} mod S)`|_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
`x`

.
_{t}

To illustrate, let
`C=256`

and
`S=16`

. Then
`x`

represents the two before last digits in the hexadecimal
representation of
_{A->B}`x`

, and
`x`

determines all other digits of
_{B¦}`x`

. Intuitively, the number
`x`

is a 'mostly secret' number. The number of 'disclosed bits' is
`log`

. Also,
_{2}(C)`log`

represents the 'left shift' of the disclosed bits from the least
significant bit positions. This explanation holds when
_{2}(S)`S`

and
`C`

are exact powers of
`2`

. With unrestricted values of
`S`

and
`C`

, the shuffling of
`x`

bits in
_{A->B}`x`

is more cryptic. It is certainly wise to vary
`S`

and
`C`

occasionally.

The eavesdropper sees only the constraint and the value
`x`

and thus cannot compute
_{t}`w`

, as long as
`P`

,
`Q`

and
`x`

are concealed. A failure of the constraint verification process
indicates that the received
_{B¦}`x`

value was selected without due consideration of the initiating
message, and thus detects replay attacks. By constraining the BBS seed
_{t}`x`

(and indirectly
`x`

) 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
_{t}`x`

and (ii) the randomness in the transformation of the partial
information
`x`

into
_{A->B}`x`

(or even
_{t}`x`

).
_{0}

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
`x`

. All bits of
_{t-1}`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.

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`

.

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.

In the case of an unexpected condition where the random number
`x`

becomes a constant on successive runs of the PEKE, the number
_{B¦}`x`

becomes restricted to a set of
_{t}`C`

possible values. The randomness in the transformation of
`x`

into
_{A->B}`x`

makes the failure not trivial to detect by an eavesdropper.
Nonetheless, the initiator can recover
_{t}`x`

as part of the constraint verification process (with a high
probability, a single one of the four possible values for
_{B¦}`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.
_{B¦}

Selection of
`N`

. To guarantee the maximum period for the BBS generator (the smallest
`pi`

such that
`x`

), theorem 8 of
[5] requires the prime factors of
_{pi}=x_{0}`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=p`

and
_{1}×B+p_{0}`p`

, the least significant digit
_{1}>0`p`

is limited to a small set of values. In
[10] the sequence M1406 for
_{0}`p`

is given with
`B=10`

and
`p`

either
_{0}`1`

or
`9`

. Preliminary results (using
`B=2310`

) show workable processing times for
`512`

and
`640`

bits
`N`

.

Computation of
`inv(g`

(theorem
10_{N,t,k})*b* of
[5]). The initiator can recover four possible values for the BBS seed
`x`

from
`x`

and its knowledge of
_{t}`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
`x`

, recovery starts with the following computations:
_{t}

```
µ =
(x
```_{t} mod
P)^{alpha} mod
P

```
nu =
(x
```_{t} 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
`x`

.
_{0} = 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)

[ CONNOTECH home page: http://www.connotech.com/ | about us | e-mail to: info@connotech.com ]

*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*