<<

. 18
( 29)



>>

the lack of any credible attack on the integrity provided by the DSS given proper use and
implementation. Based on the technical and security requirements of the U.S. government
for digital signatures, we believe the DSS is the best choice. In fact, the DSS is being used
in a pilot project for the Defense Message System to assure the authenticity of electronic
messages of vital command and control information. This initial demonstration includes
participation from the Joint Chiefs of Staff, the military services, and Defense Agencies
and is being done in cooperation with NIST.

I™m not going to comment on the trustworthiness of the NSA. Take their comments for what you think
they™re worth.



Page 410 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Attacks against k

Each signature requires a new value of k, and that value must be chosen randomly. If Eve ever
recovers a k that Alice used to sign a message, perhaps by exploiting some properties of the random-
number generator that generated k, she can recover Alice™s private key, x. If Eve ever gets two
messages signed using the same k, even if she doesn™t know what it is, she can recover x. And with x,
Eve can generate undetectable forgeries of Alice™s signature. In any implementation of the DSA, a
good random-number generator is essential to the system™s security [1468].

Dangers of a Common Modulus

Even though the DSS does not specify a common modulus to be shared by everyone, different
implementations may. For example, the Internal Revenue Service is considering using the DSS for the
electronic submission of tax returns. What if they require every taxpayer in the country to use a
common p and q? Even though the standard doesn™t require a common modulus, such an
implementation accomplishes the same thing. A common modulus too easily becomes a tempting
target for cryptanalysis. It is still too early to tell much about different DSS implementations, but
there is some cause for concern.

Subliminal Channel in DSA

Gus Simmons discovered a subliminal channel in DSA [1468,1469] (see Section 23.3). This subliminal
channel allows someone to embed a secret message in his signature that can only be read by another
person who knows the key. According to Simmons, it is a “remarkable coincidence” that the
“apparently inherent shortcomings of subliminal channels using the ElGamal scheme can all be
overcome” in the DSS, and that the DSS “provides the most hospitable setting for subliminal
communications discovered to date.” NIST and NSA have not commented on this subliminal channel;
no one knows if they even knew about it. Since this subliminal channel allows an unscrupulous
implementer of DSS to leak a piece of the private key with each signature, it is important to never use
an implementation of DSS if you don™t trust the implementer.


Patents

David Kravitz, formerly of the NSA, holds a patent on DSA [897]. According to NIST [538]:

NIST intends to make this DSS technique available world-wide on a royalty-free basis to
the public interest. We believe this technique is patentable and that no other patents
would apply to the DSS, but we cannot give firm assurances to such effect in advance of
issuance of the patent.

Even so, three patent holders claim that the DSA infringes on their patents: Diffie-Hellman (see
Section 22.1) [718], Merkle-Hellman (see Section 19.2) [720], and Schnorr (see Section 21.3) [1398].
The Schnorr patent is the most troublesome. The other two patents expire in 1997; the Schnorr patent
is valid until 2008. The Schnorr algorithm was not developed with government money; unlike the
PKP patents, the U.S. government has no rights to the Schnorr patent; and Schnorr patented his
algorithm worldwide. Even if the U.S. courts rule in favor of DSA, it is unclear what other courts
around the world would do. Is an international company going to adopt a standard that may be legal
in some countries but infringes on a patent in others? This issue will take time to resolve; at the time
of this writing it isn™t even resolved in the United States.




Page 411 of 666
Applied Cryptography: Second Edition - Bruce Schneier




In June 1993 NIST proposed to give PKP an exclusive patent license to DSA [541]. The agreement fell
through after public outcry and the standard was issued without any deal. NIST said [542]:

...NIST has addressed the possible patent infringement claims, and has concluded that
there are no valid claims.

So the standard is official, lawsuits are threatened, and no one knows what to do. NIST has said that
it would help defend people sued for patent infringement, if they were using DSA to satisfy a
government contract. Everyone else, it seems, is on their own. ANSI has a draft banking standard that
uses DSA [60]. NIST is working to standardize DSA within the government. Shell Oil has made DSA
their international standard. I know of no other proposed DSA standards.

20.2 DSA Variants

This variant makes computation easier on the signer by not forcing him to compute k-1 [1135]. All the
parameters are as in DSA. To sign a message, m, Alice generates two random numbers, k and d, both
less than q. The signature is

r = (gk mod p) mod q
s = (H(m) + xr) * d mod q
t = kd mod q

Bob verifies the signature by computing

w = t/s mod q
u1 = (H(m) * w) mod q
u2 = (rw) mod q

If r = ((gu1 * yu2) mod p) mod q, then the signature is verified.

This next variant makes computation easier on the verifier [1040,1629]. All the parameters are as in
DSA. To sign a message, m, Alice generates a random number, k, less than q. The signature is

r = (gk mod p) mod q
s = k * (H(m) + xr)-1 mod q

Bob verifies the signature by computing

u1 = (H(m) * s) mod q
u2 = (sr) mod q

If r = ((gu1 * yu2) mod p) mod q, then the signature is verified.

Another DSA variant allows for batch verification; Bob can verify signatures in batches [1135]. If
they are all valid, he is done. If one isn™t valid, then he still has to find it. Unfortunately, it is not
secure; either the signer or the verifier can easily create a set of bogus signatures that satisfy the batch
criteria [974].

There is also a variant for DSA prime generation, one that embeds q and the parameters used to



Page 412 of 666
Applied Cryptography: Second Edition - Bruce Schneier



generate the primes within p. Whether this scheme reduces the security of DSA is still unknown.

(1) Choose an arbitrary sequence of at least 160 bits and call it S. Let g be the length of S
in bits.
(2) Compute U = SHA(S) SHA ((S + 1) mod 2g), where SHA is the Secure Hash
Algorithm (see Section 18.7).
(3) Form q by setting the most significant bit and the least significant bit of U to 1.
(4) Check whether q is prime.
(5) Let p be the concatenation of q, S, C, and SHA(S). C is set to 32 zero bits.
(6) p = p “ (p mod q) + 1.
(7) p = p + q.
(8) If the C in p is 0x7fffffff, go to step (1).
(9) Check whether p is prime.
(10) If p is composite, go to step (7).

The neat thing about this variant is that you don™t have to store the values of C and S used to generate
p and q; they are embedded within p. For applications without a whole lot of memory, like smart
cards, this can be a big deal.

20.3 GOST Digital Signature Algorithm

This is a Russian digital signature standard, officially called GOST R 34.10-94 [656]. The algorithm is
very similar to DSA, and uses the following parameters

p = a prime number, either between 509 and 512 bits long, or between 1020 and 1024 bits
long.
q = a 254- to 256-bit prime factor of p “ 1.
a = any number less than p “ 1 such that aq mod p = 1.
x = a number less than q.
y = ax mod p.

The algorithm also makes use of a one-way hash function: H(x). The standard specifies GOST R
34.11-94 (see Section 18.11), a function based on the GOST symmetric algorithm (see Section 14.1)
[657].

The first three parameters, p, q, and a, are public and can be common across a network of users. The
private key is x; the public key is y.

To sign a message, m

(1) Alice generates a random number, k, less than q
(2) Alice generates
r = (ak mod p) mod q
s = (xr + k(H(m))) mod q

If H(m) mod q = 0, then set it equal to 1. If r = 0, then choose another k and start again. The
signature is two numbers: r mod 2256 and s mod 2256. She sends these to Bob.
(3) Bob verifies the signature by computing
v = H(m)q-2 mod q
z1 = (sv) mod q
z2 = ((q “ r) * v) mod q



Page 413 of 666
Applied Cryptography: Second Edition - Bruce Schneier



u = ((az1 * yz2) mod p) mod q

If u = r, then the signature is verified.


The difference between this scheme and DSA is that with DSA s = (xr + k-1(H(m))) mod q, which leads
to a different verification equation. Curious, though, is that q is 256 bits. Most Western
cryptographers seem satisfied with a q of around 160 bits. Perhaps this is just a reflection of the
Russian tendency to play it ultrasafe.

The standard has been in use since the beginning of 1995, and is not classified “for special use””
whatever that means.

20.4 Discrete Logarithm Signature Schemes

ElGamal, Schnorr (see Section 21.3), and DSA signature schemes are very similar. In fact, they are
just three examples of a general digital signature scheme based on the Discrete Logarithm Problem.
Along with thousands of other signature schemes, they are part of the same family [740,741,699,1184].

Choose p, a large prime number, and q, either p “ 1 or a large prime factor of p “ 1. Then choose g, a
number between 1 and p such that gq G (mod p). All these numbers are public, and can be common
G1
to a group of users. The private key is x, less than q. The public key is y = gx mod p.

To sign a message, m, first choose a random k less than and relatively prime to q. If q is also prime,
any k less than q works. First compute

r = gk mod p

The generalized signature equation now becomes

ak = b + cx mod q

The coefficients a, b, and c can be any of a variety of things. Each line in Table 20.4 gives six
possibilities.

To verify the signature, the receiver must confirm that

ra = gbyc mod p

This is called the verification equation.

Table 20.5 lists the signature and verifications possible from just the first line of potential values for a,
b, and c, ignoring the effects of the ±

Table 20.4
Possible Permutations of a, b, and c (r™
= r mod q)
±r™ ±s m
±r™m ±s 1
±r™m ±ms 1



Page 414 of 666
Applied Cryptography: Second Edition - Bruce Schneier



±mr™ ±r™s 1
±ms ±r™s 1


That™s six different signature schemes. Adding the negative signs brings the total to 24. Using the
other possible values listed for a, b, and c brings the total to 120.

ElGamal [518,519] and DSA [1154] are essentially based on equation (4). Other schemes are based on
equation (2) [24,1629]. Schnorr [1396,1397] is closely related to equation (5), as is another scheme
[1183]. And equation (1) can be modified to yield the scheme proposed in [1630]. The rest of the
equations are new.

There™s more. You can make any of these schemes more DSA-like by defining r as

r = (gk mod p) mod q

Keep the same signature equation and make the verification equation

u1 = a-1b mod q
u2 = a-1c mod q
r = (gu1yu2 mod p) mod q

There are two other possibilities along these lines [740,741]; you can do this with each of the 120
schemes, bringing the total to 480 discrete-logarithm-based digital signature schemes.

But wait”there™s more. Additional generalizations and variations can generate more than 13,000
variants (not all of them terribly efficient) [740,741].

One of the nice things about using RSA for digital signatures is a feature called message recovery.
When you verify an RSA signature you compute m. Then you compare the computed m with the
message and see if the signature is valid for that message. With the previous schemes, you can™t
recover m when you compute the signature; you need a candidate m that you use in a verification
equation. Well, as it turns out it is possible to construct a message recovery variant for all the above
signature schemes.

Table 20.5
Discrete Logarithm Signature Schemes
Signature Equation Verification Equation

rr™ = gsym mod p
(1) r™k = s + mx mod q
rr™ = gmys mod p
(2) r™k = m + sx mod q
rs = gr™ym mod p
(3) sk = r™ + mx mod q
rs = gmyr™ mod p
(4) sk = m + r™x mod q
rm = gsyr™ mod p
(5) mk = s + r™x mod q
rm = gr™ys mod p
(6) mk = r™ + sx mod q


To sign, first compute




Page 415 of 666
Applied Cryptography: Second Edition - Bruce Schneier




r = mgk mod p

and replace m by 1 in the signature equation. Then you can reconstruct the verification equation such
that m can be computed directly.

You can do the same with the DSA-like schemes:

r = (mgk mod p) mod q


All the variants are equally secure, so it makes sense to choose a scheme that is easy to compute with.
The requirement to compute inverses slows most of these schemes. As it turns out, a scheme in this
pile allows computing both the signature equation and the verification equation without inverses and
also gives message recovery. It is called the p-NEW scheme [1184].

r = mg-k mod p
s = k “ r™x mod q

And m is recovered (and the signature verified) by

m = gsyr™r mod p

Some variants sign two and three message blocks at the same time [740]; other variants can be used
for blind signatures [741].

This is a remarkable piece of research. All of the various discrete-logarithm-based digital signature
schemes have been put in one coherent framework. In my opinion this finally puts to rest any patent
dispute between Schnorr [1398] and DSA [897]: DSA is not a derivative of Schnorr, nor even of
ElGamal. All three are examples of this general construction, and this general construction is
unpatented.

20.5 Ong-Schnorr-Shamir

This signature scheme uses polynomials modulo n [1219,1220]. Choose a large integer n (you need not
know the factorization of n). Then choose a random integer, k, such that k and n are relatively prime.
Calculate h such that

h = “k-2 mod n = -(k-1)2 mod n

The public key is h and n; k is the private key.

To sign a message, M, first generate a random number, r, such that r and n are relatively prime. Then
calculate:

S1 = 1/2 * (M/r + r) mod n
S2 = k/2 * (M/r “ r) mod n

The pair, S1 and S2, is the signature.




Page 416 of 666
Applied Cryptography: Second Edition - Bruce Schneier




To verify a signature, confirm that

S12 + h * S22 GM
G (mod n)

The version of the scheme described here is based on quadratic polynomials. When it was first
proposed in [1217], a $100 reward was offered for successful cryptanalysis. It was proved insecure
[1255,18], but its authors were not deterred. They proposed a modification of the algorithm based on
cubic polynomials, which is also insecure [1255]. The authors then proposed a quartic version, which
was also broken [524,1255]. A variant which fixes these problems is in [1134].

20.6 ESIGN

ESIGN is a digital signature scheme from NTT Japan [1205,583]. It is touted as being at least as
secure and considerably faster than either RSA or DSA, with similar key and signature lengths.

The private key is a pair of large prime numbers, p and q. The public key is n, when

n = p2q

H is a hash function that operates on a message, m, such that H(m) is between 0 and n “ 1. There is
also a security parameter, k, which will be discussed shortly.

(1) Alice picks a random number x, where x is less than pq.
(2) Alice computes:
w, the least integer that is larger than or equal to
(H(m) “ xk mod n)/pq
s = x + ((w/kxk - 1) mod p)pq
(3) Alice sends s to Bob.
(4) To verify the signature, Bob computes sk mod n. He also computes a, which is the least
integer larger than or equal to two times the number of bits of n divided by 3. If H(m) is less
than or equal to sk mod n, and if sk mod n is less than H(m) + 2a, then the signature is
considered valid.

This algorithm works faster with precomputation. This precomputation can be done at any time and
has nothing to do with the message being signed. After picking x, Alice could break step (2) into two
partial steps. The first can be precomputed.

(2a) Alice computes:
u = xk mod n
v = 1/(kxk - 1) mod p
(2b) Alice computes:
w = the least integer that is larger than or equal to
(H(m) “ u)/pq)
s = x + (wv mod p)pq

For the size of numbers generally used, this precomputation speeds up the signature process by a
factor of 10. Almost all the hard work is done in the precomputation stage. A discussion of modular
arithmetic operations to speed ESIGN can be found in [1625,1624]. This algorithm can also be
extended to work with elliptic curves [1206].




Page 417 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Security of ESIGN

When this algorithm was originally proposed, k was set to 2 [1215]. This was quickly broken by Ernie
Brickell and John DeLaurentis [261], who then extended their attack to k = 3. A modified version of
this algorithm [1203] was broken by Shamir [1204]. The variant proposed in [1204] was broken in
[1553]. ESIGN is the current incarnation of this family of algorithms. Another new attack [963] does
not work against ESIGN.

The authors currently recommend these values for k: 8, 16, 32, 64, 128, 256, 512, and 1024. They also
recommend that p and q each be of at least 192 bits, making n at least 576 bits long. (I think n should
be twice that length.) With these parameters, the authors conjecture that ESIGN is as secure as RSA
or Rabin. And their analysis shows favorable speed comparison to RSA, ElGamal, and DSA [582].

Patents

ESIGN is patented in the United States [1208], Canada, England, France, Germany, and Italy.
Anyone who wishes to license the algorithm should contact Intellectual Property Department, NTT,
1“6 Uchisaiwai-cho, 1-chome, Chiyada-ku, 100 Japan.


20.7 Cellular Automata

A new and novel idea, studied by Papua Guam [665], is the use of cellular automata in public-key
cryptosystems. This system is still far too new and has not been studied extensively, but a preliminary
examination suggests that it may have a cryptographic weakness similar to one seen in other cases
[562]. Still, this is a promising area of research. Cellular automata have the property that, even if they
are invertible, it is impossible to calculate the predecessor of an arbitrary state by reversing the rule
for finding the successor. This sounds a whole lot like a trapdoor one-way function.

20.8 Other Public-Key Algorithms

Many other public-key algorithms have been proposed and broken over the years. The Matsumoto-
Imai algorithm [1021] was broken in [450]. The Cade algorithm was first proposed in 1985, broken in
1986 [774], and then strengthened in the same year [286]. In addition to these attacks, there are
general attacks for decomposing polynomials over finite fields [605]. Any algorithm that gets its
security from the composition of polynomials over a finite field should be looked upon with
skepticism, if not outright suspicion.

The Yagisawa algorithm combines exponentiation mod p with arithmetic mod p “ 1 [1623]; it was
broken in [256]. Another public-key algorithm, Tsujii-Kurosawa-Itoh-Fujioka-Matsumoto [1548] is
insecure [948]. A third system, Luccio-Mazzone [993], is insecure [717]. A signature scheme based on
birational permutations [1425] was broken the day after it was presented [381]. Tatsuaki Okamoto
has several signature schemes: one is provably as secure as the Discrete Logarithm Problem, and
another is provably as secure as the Discrete Logarithm Problem and the Factoring Problem [1206].
Similar schemes are in [709].

Gustavus Simmons suggested J-algebras as a basis for public-key algorithms [1455,145]. This idea
was abandoned after efficient methods for factoring polynomials were invented [951]. Special
polynomial semigroups have also been studied [1619,962], but so far nothing has come of it. Harald
Niederreiter proposed a public-key algorithm based on shift-register sequences [1166]. Another is
based on Lyndon words [1476] and another on propositional calculus [817]. And a recent public-key




Page 418 of 666
Applied Cryptography: Second Edition - Bruce Schneier



algorithm gets its security from the matrix cover problem [82]. Tatsuaki Okamoto and Kazuo Ohta
compare a number of digital signature schemes in [1212].

Prospects for creating radically new and different public-key cryptography algorithms seem dim. In
1988 Whitfield Diffie noted that most public-key algorithms are based on one of three hard problems
[492, 494]:

1. Knapsack: Given a set of unique numbers, find a subset whose sum is N.
2. Discrete logarithm: If p is a prime and g and m are integers, find x such that gx GMG
(mod p).
3. Factoring: If N is the product of two primes, either
a) factor N,
b) given integers M and C, find d such that Md G (mod N),
GC
c) given integers e and C, find M such that Me G (mod N), or
GC
d) given an integer x, decide whether there exists an integer y such that x G 2 (mod
Gy
N).

According to Diffie [492,494], the Discrete Logarithm Problem was suggested by J. Gill, the Factoring
Problem by Knuth, and the knapsack problem by Diffie himself.

This narrowness in the mathematical foundations of public-key cryptography is worrisome. A
breakthrough in either the problem of factoring or of calculating discrete logarithms could render
whole classes of public-key algorithms insecure. Diffie points out [492,494] that this risk is mitigated
by two factors:

1. The operations on which public key cryptography currently depends”
multiplying, exponentiating, and factoring”are all fundamental arithmetic
phenomena. They have been the subject of intense mathematical scrutiny for
centuries and the increased attention that has resulted from their use in public key
cryptosystems has on balance enhanced rather than diminished our confidence.
2. Our ability to carry out large arithmetic computations has grown steadily
and now permits us to implement our systems with numbers sufficient in size to be
vulnerable only to a dramatic breakthrough in factoring, logarithms, or root
extraction.

As we have seen, not all public-key algorithms based on these problems are secure. The strength of
any public-key algorithm depends on more than the computational complexity of the problem upon
which it is based; a hard problem does not necessarily imply a strong algorithm. Adi Shamir listed
three reasons why this is so [1415]:

1. Complexity theory usually deals with single isolated instances of a problem.
A cryptanalyst often has a large collection of statistically related problems to solve”
several ciphertexts encrypted with the same key.
2. The computational complexity of a problem is typically measured by its
worst-case or average-case behavior. To be useful as a cipher, the problem must be
hard to solve in almost all cases.
3. An arbitrarily difficult problem cannot necessarily be transformed into a
cryptosystem, and it must be possible to insert trapdoor information into the
problem so that a shortcut solution is possible with this information and only with
this information.




Page 419 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Chapter 21
Identification Schemes
21.1 Feige-Fiat-Shamir

Amos Fiat™s and Adi Shamir™s authentication and digital signature scheme is discussed in [566,567].
Uriel Feige, Fiat, and Shamir modified the algorithm to a zero-knowledge proof of identity [544,545].
This is the best-known zero-knowledge proof of identity.

On July 9, 1986 the three authors submitted a U.S. patent application [1427]. Because of its potential
military applications, the application was reviewed by the military. Occasionally the Patent Office
responds not with a patent, but with something called a secrecy order. On January 6, 1987, three days
before the end of their six-month period, the Patent Office imposed that order at the request of the
Army. They stated that “...the disclosure or publication of the subject matter...would be detrimental
to the national security....” The authors were ordered to notify all Americans to whom the research
had been disclosed that unauthorized disclosure could lead to two years™ imprisonment, a $10,000
fine, or both. Furthermore, the authors had to inform the Commissioner of Patents and Trademarks
of all foreign citizens to whom the information had been disclosed.

This was ludicrous. All through the second half of 1986, the authors had presented the work at
conferences throughout Israel, Europe, and the United States. The authors weren™t even American
citizens, and all the work had been done at the Weizmann Institute in Israel.

Word spread through the academic community and the press. Within two days the secrecy order was
rescinded; Shamir and others believe that the NSA pulled strings to rescind the order, although they
officially had no comment. Further details of this bizarre story are in [936].

Simplified Feige-Fiat-Shamir Identification Scheme

Before issuing any private keys, the arbitrator chooses a random modulus, n, which is the product of
two large primes. In real life, n should be at least 512 bits long and probably closer to 1024 bits. This n
can be shared among a group of provers. (Choosing a Blum integer makes computation easier, but it
is not required for security.)

To generate Peggy™s public and private keys, a trusted arbitrator chooses a number, v, where v is a
quadratic residue mod n. In other words, choose v such that x2 G (mod n) has a solution and v-1
Gv
Gsqrt (v-1) (mod
mod n exists. This v is Peggy™s public key. Then calculate the smallest s for which s G
n). This is Peggy™s private key.

The identification protocol can now proceed.

(1) Peggy picks a random r, where r is less then n. She then computes x = r2 mod n, and
sends x to Victor.
(2) Victor sends Peggy a random bit, b.
(3) If b = 0, then Peggy sends Victor r. If b = 1, then Peggy sends Victor y = r * s mod n.
(4) If b = 0, Victor verifies that x = r2 mod n, proving that Peggy knows sqrt (x). If b = 1,
Victor verifies that x = y2 * v mod n, proving that Peggy knows sqrt (v-1).

This is a single round”called an accreditation”of the protocol. Peggy and Victor repeat this protocol
t times, until Victor is convinced that Peggy knows s. It™s a cut-and-choose protocol. If Peggy doesn™t




Page 420 of 666
Applied Cryptography: Second Edition - Bruce Schneier



know s, she can pick r such that she can fool Victor if he sends her a 0, or she can pick r such that she
can fool Victor if he sends her a 1. She can™t do both. The odds of her fooling Victor once are 50
percent. The odds of her fooling him t times are 1 in 2t.

Another way for Victor to attack the protocol would be trying to impersonate Peggy. He could initiate
the protocol with another verifier, Valerie. In step (1), instead of choosing a random r, he would just
reuse an old r that he saw Peggy use. However, the odds of Valerie choosing the same value for b in
step (2) that Victor did in the protocol with Peggy are 1 in 2. So, the odds of his fooling Valerie are 50
percent. The odds of his fooling her t times are 1 in 2t.

For this to work, Peggy must not reuse an r, ever. If she did, and Victor sent Peggy the other random
bit in step (2), then he would have both of Peggy™s responses. Then, from even one of these, he can
calculate s and it™s all over for Peggy.

Feige-Fiat-Shamir Identification Scheme

In their papers [544,545], Feige, Fiat and Shamir show how parallel construction can increase the
number of accreditations per round and reduce Peggy and Victor™s interactions.

First generate n as in the previous example, the product of two large primes. To generate Peggy™s
public and private keys, first choose k different numbers: v1, v2,..., vk, where each vi is a quadratic
residue mod n. In other words, choose vi such that x2 = vi mod n has a solution and vi-1 mod n exists.
This string, v1, v2,..., vk, is the public key. Then calculate the smallest si such that si = sqrt (vi-1) mod n.
This string, s1, s2,..., sk, is the private key.

And the protocol is:

(1) Peggy picks a random r, when r is less than n. She then computes x = r2 mod n, and
sends x to Victor.
(2) Victor sends Peggy a random binary string k-bits long: b1, b2,..., bk.
(3) Peggy computes y = r * (s1b1 * s2b2 *...* skbk) mod n. (She multiplies together
whichever values of si that correspond to bi = 1. If Victor™s first bit is a 1, then s1 is part of the
product; if Victor™s first bit is a 0, then s1 is not part of the product, and so on.) She sends y to
Victor.
(4) Victor verifies that x = y2 * (v1b1 * v2b2 *...* vkbk) mod n. (He multiplies together the
values of vi based on the random binary string. If his first bit is a 1, then v1 is part of the
product; if his first bit is a 0, then v1 is not part of the product, and so on.)

Peggy and Victor repeat this protocol t times, until Victor is convinced that Peggy knows s1, s2,..., sk.

The chance that Peggy can fool Victor is 1 in 2kt. The authors recommend a 1 in 220 chance of a
cheater fooling Victor and suggest that k = 5 and t = 4. If you are more paranoid, increase these
numbers.


An Example




Page 421 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Let™s look at this protocol in action with small numbers.

If n = 35 (the two primes are 5 and 7), then the possible quadratic residues are:

1: x2 G1
G (mod 35) has the solutions: x = 1, 6, 29, or 34.
4: x2 G4 (mod 35) has the solutions: x = 2, 12, 23, or 33.
G
9: x2 G9
G (mod 35) has the solutions: x = 3, 17, 18, or 32.
11: x2 G11
G (mod 35) has the solutions: x = 9, 16, 19, or 26.
14: x2 G14
G (mod 35) has the solutions: x = 7 or 28.
15: x2 G15
G (mod 35) has the solutions: x = 15 or 20.
16: x2 G16
G (mod 35) has the solutions: x = 4, 11, 24, or 31.
21: x2 G21
G (mod 35) has the solutions: x = 14 or 21.
25: x2 G25
G (mod 35) has the solutions: x = 5 or 30.
29: x2 G29
G (mod 35) has the solutions: x = 8, 13, 22 or 27.
30: x2 G30
G (mod 35) has the solutions: x = 10 or 25.

The inverses (mod 35) and their square roots are:

v-1 s = sqrt (v-1)
v
1 1 1
4 9 3
9 4 2
11 16 4
16 11 9
29 29 8

Note that 14, 15, 21, 25, and 30 do not have inverses mod 35, because they are not relatively prime to
35. This makes sense, because there should be (5 - 1) * (7 - 1)/4 quadratic residues mod 35 relatively
prime to 35: That is gcd(x,35) = 1 (see Section 11.3).

So, Peggy gets the public key consisting of k = 4 values: {4,11,16,29}. The corresponding private key is
{3,4,9,8}. Here™s one round of the protocol.

Peggy chooses a random r = 16, computes 162 mod 35 = 11, and sends it to Victor.
(1)
(2) Victor sends Peggy a random binary string {1,1,0,1}.
Peggy computes 16 * ((31) * (41) * (90) * (81)) mod 35 = 31 and sends it to Victor.
(3)
Victor verifies that 312 * ((41) * (111) * (160) * (291)) mod 35 = 11.
(4)

Peggy and Victor repeat the protocol t times, each time with a different random r, until Victor is
satisfied.

With small values like these, there™s no real security. But when n is 512 bits long or more, Victor
cannot learn anything about Peggy™s secret key except the fact that she knows it.

Enhancements




Page 422 of 666
Applied Cryptography: Second Edition - Bruce Schneier




It is possible to embed identification information into the protocol. Assume that I is a binary string
representing Peggy™s identification: her name, address, social security number, hat size, preferred
brand of soft drink, and other personal information. Use a one-way hash function H(x) to compute H
(I,j), where j is a small number concatenated onto I. Find a set of js where H(I,j) is a quadratic residue
mod n. These H(I,j)s become v1, v2,..., vk (the js need not be quadratic residues). Peggy™s public key is
now I and the list of js. She sends I and the list of js to Victor before step (1) of the protocol (or
perhaps Victor downloads them from a public bulletin board someplace), and Victor generates v1,
v2,..., vk from H(I,j).

Now, after Victor successfully completes the protocol with Peggy, he is assured that Trent, who knows
the factorization of the modulus, has certified the association between I and Peggy by giving her the
square roots of the vi derived from I. (See Section 5.2 for background information.)

Feige, Fiat, and Shamir include the following implementation remarks [544,545]:

For nonperfect hash functions, it may be advisable to randomize I by concatenating it
with a long random string, R. This string is chosen by the arbitrator and is revealed to
Victor along with I.

In typical implementations, k should be between 1 and 18. Larger values of k can reduce
the time and communication complexity by reducing the number of rounds.

The value n should be at least 512 bits long. (Of course, there has been considerable
progress in factoring since then.)

If each user chooses his own n and publishes it in a public key file, they can dispense with
the arbitrator. However, this RSA-like variant makes the scheme considerably less
convenient.

Fiat-Shamir Signature Scheme

Turning this identification scheme into a signature scheme is basically a matter of turning Victor into
a hash function. The primary benefit of the Fiat-Shamir digital signature scheme over RSA is speed:
Fiat-Shamir requires only 1 percent to 4 percent of the modular multiplications of RSA. For this
protocol, we™ll bring back Alice and Bob.


The setup is the same as the identification scheme. Choose n to be the product of two large primes.
Generate the public key, v1, v2,..., vk, and the private key, s1, s2,..., sk, such that si = sqrt (vi-1) mod n.

(1) Alice picks t random integers between 1 and n: r1, r2,..., rt, and computes x1, x2,..., xt
such that xi = ri2 mod n.
(2) Alice hashes the concatenation of the message and the string of xis to generate a bit
stream: H(m, x1, x2,..., xt). She uses the first k * t bits of this string as values of bij, where i goes
from 1 to t, and j goes from 1 to k.
(3) Alice computes y1, y2,..., yt, where
yi = ri * (s1bi1 * s2bi2 *...* skbik) mod n




Page 423 of 666
Applied Cryptography: Second Edition - Bruce Schneier



(For each i, she multiplies together the values of the sj based on the random bi,j values. If bi,1 is a
1, then s1 is multiplied; if bi,1 is a 0, then s1 is not multiplied.)
(4) Alice sends Bob m, all the bit values of bi,j, and all the values of yi. He already has
Alice™s public key: v1, v2,..., vk.
(5) Bob computes z1, z2,..., zt, where
zi = yi2 * (v1bi1 * v2bi2 *...* vkbik) mod n
(Again, Bob multiplies based on the bi, j values.) Also note that zi should be equal to xi.
(6) Bob verifies that the first k * t bits of H(m, z1, z2,..., zt) are the bi, j values that Alice sent
him.

As with the identification scheme, the security of this signature scheme is proportional to 1/2kt. It also
depends on the difficulty of factoring n. Fiat and Shamir pointed out that forging a signature is easier
when the complexity of factoring n is considerably lower than 2kt. And, because of birthday-type
attacks (see Section 18.1), they recommend that k * t be increased from 20 to at least 72. They suggest
k = 9 and t = 8.

Improved Fiat-Shamir Signature Scheme

Silvio Micali and Adi Shamir improved the Fiat-Shamir protocol in [1088]. They chose v1, v2,..., vk to
be the first k prime numbers. So

v1 = 2, v2 = 3, v3 = 5, and so on.

This is the public key.

The private key, s1, s2,..., sk is a random square root, determined by

si = sqrt (vi-1) mod n

In this version, every person must have a different n. The modification makes it easier to verify
signatures. The time required to generate signatures, and the security of those signatures, is
unaffected.

Other Enhancements

There is also an N-party identification scheme, based on the Fiat-Shamir algorithm [264]. Two other
improvements to the Fiat-Shamir scheme are proposed in [1218]. Another variant is [1368].

Ohta-Okamoto Identification Scheme

This protocol is a modification of the Feige-Fiat-Shamir identification scheme and gets its security
from the difficulty of factoring [1198,1199]. The same authors also wrote a multisignature scheme (see
Section 23.1), by which a number of different people can sequentially sign a message [1200]. This
scheme has been proposed for smart-card implementation [850].

Patents




Page 424 of 666
Applied Cryptography: Second Edition - Bruce Schneier




Fiat-Shamir is patented [1427]. Anyone interested in licensing the algorithm should contact Yeda
Research and Development, The Weizmann Institute of Science, Rehovot 76100, Israel.

21.2 Guillou-Quisquater

Feige-Fiat-Shamir was the first practical identity-based protocol. It minimized computation by
increasing the number of iterations and accreditations per iteration. For some implementations, like
smart cards, this is less than ideal. Exchanges with the outside world are time-consuming, and the
storage required for each accreditation can strain the limited resources of the card.

Louis Guillou and Jean-Jacques Quisquater developed a zero-knowledge identification algorithm
more suited to applications like these [670,1280]. The exchanges between Peggy and Victor and the
parallel accreditations in each exchange are both kept to an absolute minimum: There is only one
exchange of one accreditation for each proof. For the same level of security, the computation required
by Guillou-Quisquater is greater than by Feige-Fiat-Shamir by a factor of three. And like Feige-Fiat-
Shamir, this identification algorithm can be converted to a digital signature algorithm.

Guillou-Quisquater Identification Scheme

Peggy is a smart card who wants to prove her identity to Victor. Peggy™s identity consists of a set of
credentials: a data string consisting of the card™s name, validity period, a bank account number, and
whatever else the application warrants. This bit string is called J. (Actually, the credentials can be a
longer string and hashed to a J value. This complexity does not modify the protocol in any way.) This
is analogous to the public key. Other public information, shared by all “Peggys” who could use this
application, is an exponent v and a modulus n, where n is the product of two secret primes. The
private key is B, calculated such that JBv G (mod n).
G1

Peggy sends Victor her credentials, J. Now, she wants to prove to Victor that those credentials are
hers. To do this, she has to convince Victor that she knows B. Here™s the protocol:

(1) Peggy picks a random integer r, such that r is between 1 and n - 1. She computes T = rv
mod n and sends it to Victor.
(2) Victor picks a random integer, d, such that d is between zero and v - 1. He sends d to
Peggy.
(3) Peggy computes D = rBd mod n, and sends it to Victor.
(4) Victor computes T´ = DvJd mod n. If T G ´ (mod n), then the authentication succeeds.
GT

The math isn™t that complex:

T´ = DvJd = (rBd)vJd = rvBdvJd = rv(JBv)d = rv GT
G (mod n)

since B was constructed to satisfy

JBv G1
G (mod n)


Guillou-Quisquater Signature Scheme

This identification can be converted to a signature scheme, also suited for smart-card implementation
[671,672].



Page 425 of 666
Applied Cryptography: Second Edition - Bruce Schneier




The public and private key setup is the same as before. Here™s the protocol:

(1) Alice picks a random integer r, such that r is between 1 and n - 1. She computes T = rv
mod n.
(2) Alice computes d = H(M,T), where M is the message being signed and H(x) is a one-
way hash function. The d produced by the hash function must be between 0 and v - 1 [1280]. If
the output of the hash function is not within this range, it must be reduced modulo v.
(3) Alice computes D = rBd mod n. The signature consists of the message, M, the two
calculated values, d and D, and her credentials, J. She sends this signature to Bob.
(4) Bob computes T´ = DvJd mod n. He then computes d´ = H(M,T´). If d = d´, then Alice
must know B and the signature is valid.

Multiple Signatures

What if many people want to sign the same document? The easy solution has each of them signing
separately, but this signature scheme can do better than that. Here Alice and Bob sign the same
document and Carol verifies the signatures, but any number of people can be involved in the
signature process. As before, Alice and Bob have their own unique J and B values: (JA, BA) and (JB,
BB). The values n and v are common to the system.

(1) Alice picks a random integer, rA, such that rA is between 1 and n - 1. She computes TA
= rAv mod n and sends TA to Bob.
(2) Bob picks a random integer, rB, such that rB is between 1 and n - 1. He computes TB =
rBv mod n and sends TB to Alice.
(3) Alice and Bob each compute T = (TATB) mod n.
(4) Alice and Bob each compute d = H(M,T), where M is the message being signed and H
(x) is a one-way hash function. The d produced by the hash function must be between 0 and v - 1
[1280]. If the output of the hash function is not within this range, it must be reduced modulo v.
(5) Alice computes DA = rABAd mod n and sends DA to Bob.
(6) Bob computes DB = rBBBd mod n and sends DB to Alice.
(7) Alice and Bob each compute D = DADB mod n. The signature consists of the message,
M, the two calculated values, d and D, and both of their credentials: JA and JB.
(8) Carol computes J = JAJB mod n.
(9) Carol computes T´ = DvJd mod n. She then computes d´ = H(M,T´). If d Gd´,
G then the
multiple signature is valid.

This protocol can be extended to any number of people. For multiple people to sign, they all multiply
their individual Ti values together in step (3), and their individual Di values together in step (7). To
verify a multiple signature, multiply all the signers Ji values together in step (8). Either all the
signatures are valid or there is at least one invalid signature.

21.3 Schnorr

Claus Schnorr™s authentication and signature scheme [1396,1397] gets its security from the difficulty
of calculating discrete logarithms. To generate a key pair, first choose two primes, p and q, such that q




Page 426 of 666
Applied Cryptography: Second Edition - Bruce Schneier



is a prime factor of p - 1. Then, choose an a not equal to 1, such that aq G (mod p). All these
G1
numbers can be common to a group of users and can be freely published.

To generate a particular public-key/private-key key pair, choose a random number less than q. This is
the private key, s. Then calculate v = a-s mod p. This is the public key.

Authentication Protocol

(1) Peggy picks a random number, r, less than q, and computes x = ar mod p. This is the
preprocessing stage and can be done long before Victor is present.
(2) Peggy sends x to Victor.
(3) Victor sends Peggy a random number, e, between 0 and 2t - 1. (I™ll discuss t in a
moment.)
(4) Peggy computes y = (r + se) mod q and sends y to Victor.
(5) Victor verifies that x = ayve mod p.

The security is based on the parameter t. The difficulty of breaking the algorithm is about 2 t. Schnorr
recommended that p be about 512 bits, q be about 140 bits, and t be 72.

Digital Signature Protocol

Schnorr can also be used as a digital signature protocol on a message, M. The public-key/private-key
key pair is the same, but we™re now adding a one-way hash function, H(M).

(1) Alice picks a random number, r, less than q, and computes x = ar mod p. This
computation is the preprocessing stage.
(2) Alice concatenates M and x, and hashes the result:
e = H(M,x)
(3) Alice computes y = (r + se) mod q. The signature is e and y; she sends these to Bob.
(4) Bob computes x´ = ayve mod p. He then confirms that the concatenation of M and x´
hashes to e.
e = H(M,x´)
If it does, he accepts the signature as valid.

In his paper, Schnorr cites these novel features of his algorithm:

Most of the computation for signature generation can be completed in a preprocessing
stage, independent of the message being signed. Hence, it can be done during idle time and
not affect the signature speed. An attack against this preprocessing stage is discussed in
[475], but I don™t think it™s practical.

For the same level of security, the length of signatures is less for Schnorr than for RSA.
For example, with a 140-bit q, signatures are only 212-bits long, less than half the length of
RSA signatures. Schnorr™s signatures are also much shorter than ElGamal signatures.

Of course, practical considerations may make even fewer bits suitable for a given scheme: For
example, an identification scheme where the cheater must perform an on-line attack in only a few
seconds, versus a signature scheme where the cheater can calculate for years off-line to come up with
a forgery.




Page 427 of 666
Applied Cryptography: Second Edition - Bruce Schneier




A modification of this algorithm, by Ernie Brickell and Kevin McCurley, enhances its security [265].

Patents

Schnorr is patented in the United States [1398] and in many other countries. In 1993, PKP acquired
the worldwide rights to the patent (see Section 25.5). The U.S. patent expires on February 19, 2008.

21.4 Converting Identification Schemes to Signature Schemes

There is a standard method of converting an identification scheme into a signature scheme: Replace
Victor with a one-way hash function. The message is not hashed before it is signed; instead the
hashing is incorporated into the signing algorithm. In principle, this can be done with any
identification scheme.


Chapter 22
Key-Exchange Algorithms
22.1 Diffie-Hellman

Diffie-Hellman was the first public-key algorithm ever invented, way back in 1976 [496]. It gets its
security from the difficulty of calculating discrete logarithms in a finite field, as compared with the
ease of calculating exponentiation in the same field. Diffie-Hellman can be used for key distribution”
Alice and Bob can use this algorithm to generate a secret key”but it cannot be used to encrypt and
decrypt messages.

The math is simple. First, Alice and Bob agree on a large prime, n and g, such that g is primitive mod
n. These two integers don™t have to be secret; Alice and Bob can agree to them over some insecure
channel. They can even be common among a group of users. It doesn™t matter.

Then, the protocol goes as follows:

(1) Alice chooses a random large integer x and sends Bob
X = gx mod n
(2) Bob chooses a random large integer y and sends Alice
Y = gy mod n
(3) Alice computes
k = Yx mod n
(4) Bob computes
k´ = Xy mod n

Both k and k´ are equal to gxy mod n. No one listening on the channel can compute that value; they
only know n, g, X, and Y. Unless they can compute the discrete logarithm and recover x or y, they do
not solve the problem. So, k is the secret key that both Alice and Bob computed independently.

The choice of g and n can have a substantial impact on the security of this system. The number (n -
1)/2 should also be a prime [1253]. And most important, n should be large: The security of the system
is based on the difficulty of factoring numbers the same size as n. You can choose any g, such that g is
primitive mod n; there™s no reason not to choose the smallest g you can”generally a one-digit




Page 428 of 666
Applied Cryptography: Second Edition - Bruce Schneier



number. (And actually, g does not have to be primitive; it just has to generate a large subgroup of the
multiplicitive group mod n.)

Diffie-Hellman with Three or More Parties

The Diffie-Hellman key-exchange protocol can easily be extended to work with three or more people.
In this example, Alice, Bob, and Carol together generate a secret key.

(1) Alice chooses a random large integer x and sends Bob
X = gx mod n
(2) Bob chooses a random large integer y and sends Carol
Y = gy mod n
(3) Carol chooses a random large integer z and sends Alice
Z = gz mod n
(4) Alice sends Bob
Z´ = Zx mod n
(5) Bob sends Carol
X´ = Xy mod n
(6) Carol sends Alice
Y´ = Yz mod n
(7) Alice computes
k = Y´x mod n
(8) Bob computes
k = Z´y mod n
(9) Carol computes
k = X´z mod n

The secret key, k, is equal to gxyz mod n, and no one else listening in on the communications can
compute that value. The protocol can be easily extended to four or more people; just add more people
and more rounds of computation.

Extended Diffie-Hellman

Diffie-Hellman also works in commutitive rings [1253]. Z. Shmuley and Kevin McCurley studied a
variant of the algorithm where the modulus is a composite number [1442,1038]. V. S. Miller and Neal
Koblitz extended this algorithm to elliptic curves [1095,867]. Taher ElGamal used the basic idea to
develop an encryption and digital signature algorithm (see Section 19.6).

This algorithm also works in the Galois field GF(2k) [1442,1038]. Some implementations take this
approach [884,1631,1632], because the computation is much quicker. Similarly, cryptanalytic
computation is equally fast, so it is important to carefully choose a field large enough to ensure
security.

Hughes

This variant of Diffie-Hellman allows Alice to generate a key and send it to Bob [745].

(1) Alice chooses a random large integer x and generates
k = gx mod n
(2) Bob chooses a random large integer y and sends Alice



Page 429 of 666
Applied Cryptography: Second Edition - Bruce Schneier



Y = gy mod n
(3) Alice sends Bob
X = Yx mod n
(4) Bob computes
z = y-1
k´ = Xz mod n

If everything goes correctly, k = k´.

The advantage of this protocol over Diffie-Hellman is that k can be computed before any interaction,
and Alice can encrypt a message using k prior to contacting Bob. She can send it to a variety of people
and interact with them to exchange the key individually later.

Key Exchange without Exchanging Keys

If you have a community of users, each could publish a public key, X = gx mod n, in a common
database. If Alice wants to communicate with Bob, she just has to retrieve Bob™s public key and
generate their shared secret key. She could then encrypt a message with that key and send it to Bob.
Bob would retrieve Alice™s public key to generate the shared secret key.

Each pair of users would have a unique secret key, and no prior communication between users is
required. The public keys have to be certified to prevent spoofing attacks and should be changed
regularly, but otherwise this is a pretty clever idea.

Patents

The Diffie-Hellman key-exchange algorithm is patented in the United States [718] and Canada [719].
A group called Public Key Partners (PKP) licenses the patent, along with other public-key
cryptography patents (see Section 25.5). The U.S. patent will expire on April 29, 1997.


22.2 Station-to-Station Protocol

Diffie-Hellman key exchange is vulnerable to a man-in-the-middle attack. One way to prevent this
problem is to have Alice and Bob sign their messages to each other [500].

This protocol assumes that Alice has a certificate with Bob™s public key and that Bob has a certificate
with Alice™s public key. These certificates have been signed by some trusted authority outside this
protocol. Here™s how Alice and Bob generate a secret key, k.

(1) Alice generates a random number, x, and sends it to Bob.
(2) Bob generates a random number, y. Using the Diffie-Hellman protocol he computes
their shared key based on x and y: k. He signs x and y, and encrypts the signature using k. He
then sends that, along with y, to Alice.
y,Ek(SB(x,y))
(3) Alice also computes k. She decrypts the rest of Bob™s message and verifies his
signature. Then she sends Bob a signed message consisting of x and y, encrypted in their shared
key.
Ek(SA(x,y))
(4) Bob decrypts the message and verifies Alice™s signature.




Page 430 of 666
Applied Cryptography: Second Edition - Bruce Schneier




22.3 Shamir™s Three-Pass Protocol

This protocol, invented by Adi Shamir but never published, enables Alice and Bob to communicate
securely without any advance exchange of either secret keys or public keys [1008].

This assumes the existence of a symmetric cipher that is commutative, that is:

EA(EB(P)) = EB(EA(P))

Alice™s secret key is A; Bob™s secret key is B. Alice wants to send a message, M, to Bob. Here™s the
protocol.

(1) Alice encrypts M with her key and sends Bob
C1 = EA(M)
(2) Bob encrypts C1 with his key and sends Alice
C2 = EB(EA(M))
(3) Alice decrypts C2 with her key and sends Bob
C3 = DA(EB(EA(M))) =DA(EA(EB(M))) = EB(M)
(4) Bob decrypts C3 with his key to recover M.

One-time pads are commutative and have perfect secrecy, but they will not work with this protocol.
With a one-time pad, the three ciphertext messages would be:

C1 = P A
C2 = P A B
C3 = P B

Eve, who can record the three messages as they pass between Alice and Bob, simply XORs them
together to retrieve the message:

C1 C2 C3 = (P A) (P A B) (P B) = P

This clearly won™t work.

Shamir (and independently, Jim Omura) described an encryption algorithm that will work with this
protocol, one similar to RSA. Let p be a large prime for which p - 1 has a large prime factor. Choose
G1
an encryption key, e, such that e is relatively prime to p - 1. Calculate d such that de G (mod p - 1).

To encrypt a message, calculate

C = Me mod p

To decrypt a message, calculate

M = Cd mod p

There seems to be no way for Eve to recover M without solving the discrete logarithm problem, but




Page 431 of 666
Applied Cryptography: Second Edition - Bruce Schneier



this has never been proved.

Like Diffie-Hellman, this protocol allows Alice to initiate secure communication with Bob without
knowing any of his keys. For Alice to use a public-key algorithm, she has to know his public key. With
Shamir™s three-pass protocol, she just sends him a ciphertext message. The same thing with a public-
key algorithm looks like:

(1) Alice asks Bob (or a KDC) for his public key.
(2) Bob (or the KDC) sends Alice his public key.
(3) Alice encrypts M with Bob™s public key and sends it to Bob.

Shamir™s three-pass protocol will fall to a man-in-the-middle attack.

22.4 COMSET

COMSET (COMmunications SETup) is a mutual identification and key exchange protocol developed
for the RIPE project [1305] (see Section 25.7). Using public-key cryptography, it allows Alice and Bob
to identify themselves to each other and also to exchange a secret key.

The mathematical principle behind COMSET is Rabin™s scheme [1283] (see Section 19.5). The scheme
itself was originally proposed in [224]. See [1305] for details.

22.5 Encrypted Key Exchange

The Encrypted Key Exchange (EKE) protocol was designed by Steve Bellovin and Michael Merritt
[109]. It provides security and authentication on computer networks, using both symmetric and
public-key cryptography in a novel way: A shared secret key is used to encrypt a randomly generated
public key.

The Basic EKE Protocol

Alice and Bob (two users, a user and the host, or whoever) share a common password, P. Using this
protocol, they can authenticate each other and generate a common session key, K.

(1) Alice generates a random public-key/private-key key pair. She encrypts the public
key, K´, using a symmetric algorithm and P as the key: Ep(K´). She sends Bob
A, EP(K´)
(2) Bob knows P. He decrypts the message to obtain K´. Then, he generates a random
session key, K, and encrypts it with the public key he received from Alice and P as the key. He
sends Alice
EP(EK´(K))
(3) Alice decrypts the message to obtain K. She generates a random string, RA, encrypts it
with K, and sends Bob
EK(RA)
(4) Bob decrypts the message to obtain RA. He generates another random string, RB,
encrypts both strings with K, and sends Alice the result.
EK(RA, RB)
(5) Alice decrypts the message to obtain RA and RB. Assuming the RA she received from
Bob is the same as the one she sent to Bob in step (3), she encrypts RB with K and sends it to
Bob.



Page 432 of 666
Applied Cryptography: Second Edition - Bruce Schneier



EK(RB)
(6) Bob decrypts the message to obtain RB. Assuming the RB he received from Alice is the
same one he sent to Alice in step (4), the protocol is complete. Both parties now communicate
using K as the session key.


At step (3), both Alice and Bob know K´ and K. K is the session key and can be used to encrypt all
other messages between Alice and Bob. Eve, sitting between Alice and Bob, only knows EP(K´), EP
(EK´(K)), and some messages encrypted with K. In other protocols, Eve could make guesses at P
(people choose bad passwords all the time, and if Eve is clever she can make some good guesses) and
then test her guesses. In this protocol, Eve cannot test her guess without cracking the public-key
algorithm as well. And if both K´ and K are chosen randomly, this can be an insurmountable problem.

The challenge-response portion of the protocol, steps (3) through (6), provides validation. Steps (3)
through (5) prove to Alice that Bob knows K; steps (4) through (6) prove to Bob that Alice knows K.
The Kerberos protocol timestamp exchange accomplishes the same thing.

EKE can be implemented with a variety of public-key algorithms: RSA, ElGamal, Diffie-Hellman.
There are security problems with implementing EKE with a knapsack algorithm (aside from the
inherent insecurity of knapsack algorithms): The normal distribution of the ciphertext messages
negates the benefits of EKE.

Implementing EKE with RSA

The RSA algorithm seems perfect for this application, but there are some subtle problems. The
authors recommend encrypting only the encryption exponent in step (1) and sending the modulus in
the clear. An explanation of the reasoning behind this recommendation, as well as other subtleties
involved in using RSA, is in [109].

Implementing EKE with ElGamal

Implementing EKE with the ElGamal algorithm is straightforward, and there is even a simplification
of the basic protocol. Using the notation from Section 19.6, g and p are parts of the public key and are
common to all users. The private key is a random number r. The public key is gr mod p. The message
Alice sends to Bob in step (1) becomes

Alice, gr mod p

Note that this public key does not have to be encrypted with P. This is not true in general, but it is
true for the ElGamal algorithm. Details are in [109].

Bob chooses a random number, R (for the ElGamal algorithm and independent of any random
numbers chosen for EKE), and the message he sends to Alice in step (2) becomes

EP(gR mod p, KgRr mod p)

Refer back to Section 19.6 for restrictions on choosing the variables for ElGamal.

Implementing EKE with Diffie-Hellman




Page 433 of 666
Applied Cryptography: Second Edition - Bruce Schneier




With the Diffie-Hellman protocol, K is generated automatically. The final protocol is even simpler. A
value for g and n is set for all users on the network.

(1) Alice picks a random number, rA, and sends Bob
A, grA mod n

With Diffie-Hellman, Alice does not have to encrypt her first message with P.
(2) Bob picks a random number, rB, and calculates
K = grA*rB mod n

He generates a random string RB, then calculates and sends Alice:
EP(grB mod n), EK(RB)
(3) Alice decrypts the first half of Bob™s message to obtain grB mod n. Then she calculates
K and uses K to decrypt RB. She generates another random string, RA, encrypts both strings
with K, and sends Bob the result.
EK(RA, RB)
(4) Bob decrypts the message to obtain RA and RB. Assuming the RB he received from

<<

. 18
( 29)



>>