CONNOTECH Experts-conseils Inc.

Public Key Cryptosystem Options for the SAKEM Procedure

Say "Open, Sesame" to Electronic Identification!

by Thierry Moreau

May 1997

A public key cryptosystem (PKC) is at the heart of the SAKEM procedure. There are at least three possible PKCs, namely

any Public Key Encryption (PK-Encr) schemes, for which the RSA cryptosystem is the foremost example,
the Probabilistic Encryption Key Exchange (PEKE), see the article by Thierry Moreau, Probabilistic Encryption Key Exchange (in Electronics Letters, Vol. 31, number 25, 7th December 1995, pp 2166-2168), and
the Diffie-Hellman scheme as improved by Lein Harn (DH-Harn), see the recent article by Lein Harn, Digital signature for Diffie-Hellman keys without using a one-way function (in Electronics Letters, 16th January 1997, Vol 33, No 2, pp125-126). In the SAKEM application of the DH-Harn cryptosystem, there is no signature generation from the part of the applicant; in other words the Lein Harn's improvement ot the Diffie-Hellman cryptosystem is applied only for the issuer.

The following "PKC specification table" compares the three PKCs. The mathematical notation for each PKC is independent from each other (e.g. the symbol "e" for PEKE bears no relation to the symbol number "e" for DH-Harn). As with most public key cryptosystems, all computations are made with integer arithmetic, and often with very large operands. The usual known art of algorithmic number theory is implied. The symbol "|" represents concatenation of k-bit strings, and tacitly specifies a conversion from integer to bit string. Any of the following symbols should be read as if it was a one-letter symbol: x_A->B, x_B¦, alpha, beta, mu, and nu.

Note 1:: Preferably perform the pre-computation of integers a and b such that a×P+b×Q=1, and
alpha=((P+1)/4)^(t+1) mod (P-1), and
beta=((Q+1)/4)^(t+1) mod (Q-1).
Note 2:: Compute
x=(x_B¦-(x_B¦ mod S))×S×C+x_A->B×S+(x_B¦ mod S),
x₀=x² mod N,
x_i+1=x_i² mod N, where i runs from 0 to t-1, and
B_i=x_i mod 2^k, where i runs from 0 to t-1.
Note 3:: Compute
mu=(x_t mod P)^alpha mod P,
nu=(x_t mod Q)^beta mod Q,
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,
h=(b×Q×(P-mu)+a×P×(Q-nu)) mod N,
and then verify that one of e, f, g, or h satisfies x_A->B×S=(? mod (S×C))-(? mod S).
Note 4:: Compute
x₀=e² mod N,
x_i+1=x_i² mod N, where i runs from 0 to t-1, and
B_i=x_i mod 2^k, where i runs from 0 to t-1.
Note 5:: Lein Harn proposes four possible equation pairs for signature generation/verification, as indicated below:

The RSA cryptosystem is an alternative available for the PEKE cryptosystem. There may be institutional arguments in favor of the RSA cryptosystem, but technical merits are favourable to the PEKE alternative, notably:

The original Probabilistic Encryption was vulnerable to the "adaptatively chosen ciphertext attack", which is explicitly prevented in the PEKE cryptosystem. Nobody proved that RSA is immune to the "adaptatively chosen ciphertext attack".
The "x² mod N", where "N" is a "Blum integer", mathematical foundation for PEKE is used by many specialized cryptographic schemes proposed by the academia.
If the PEKE cryptosystem is replaced by the RSA cryptosystem, there are more serious potential damages from fraudulent modification of the issuer's public key.

The DH-Harn alternative is based on the difficulty of the discrete logarithm problem rather than the difficulty of factoring large integers as in the PEKE and PK-encr alternatives. Assuming no flaw is found in the mathematics of the Lein Harn improvement to the Diffie-Hellman cryptosystem, a comparative study of the relative merits of the three alternatives when exposed to the diverse attack scenarios could fill a complete book.

[ CONNOTECH home page: http://www.connotech.com/ | SAKEM web page: http://www.connotech.com/sakem.htm | about us | web editorial policy | 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