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