Alice.

EK(RA)

(5) Alice decrypts the message to maintain RA. Assuming the RA she received from Bob is

the same as the one she sent to Bob in step (3), the protocol is complete. Both parties now

communicate using K as the session key.

Strengthening EKE

Bellovin and Merritt suggest an enhancement of the challenge-and-response portion of the protocol”

to prevent a possible attack if a cryptanalyst recovers an old K value.

Look at the basic EKE protocol. In step (3), Alice generates another random number, SA, and sends

Bob

EK(RA, SA)

In step (4), Bob generates another random number, SB, and sends Alice

EK(RA, RB, SB)

Alice and Bob now can both calculate the true session key, SA SB. This key is used for all future

messages between Alice and Bob; K is just used as a key-exchange key.

Look at the levels of protection EKE provides. A recovered value of S gives Eve no information about

P, because P is never used to encrypt anything that leads directly to S. A cryptanalytic attack on K is

also not feasible; K is used only to encrypt random data, and S is never encrypted alone.

Augmented EKE

Page 434 of 666

Applied Cryptography: Second Edition - Bruce Schneier

The EKE protocol suffers from one serious disadvantage: It requires that both parties possess the P.

Most password-based authentication systems store a one-way hash of the user™s password, not the

password itself (see Section 3.2). The Augmented EKE (A-EKE) protocol uses a one-way hash of the

user™s password as the superencryption key in the Diffie-Hellman variant of EKE. The user then

sends an extra message based on the original password; this message authenticates the newly chosen

session key.

Here™s how it works. As usual, Alice and Bob want to authenticate each other and generate a common

key. They agree on some digital signature scheme where any number can serve as the private key, and

where the public key is derived from the private key, rather than being generated along with it. The

ElGamal and DSA algorithms work well for this. Alice™s password P (or perhaps some simple hash of

it) will serve as the private key and as P´.

(1) Alice picks her random exponent Ra and transmits

EP´(gRA mod n)

(2) Bob, who knows only P´ and cannot derive P from it, chooses Rb and sends

EP´(gRA mod n)

(3) Both Alice and Bob calculate the shared session key K = grA*rB mod n. Finally, Alice

proves that she knows P itself, and not just P´, by sending

EK(SP(K))

Bob, who knows both K and P´, can decrypt and validate the signature. Only Alice could have sent

this message, since only she knows P; an intruder who obtains a copy of Bob™s password file can try

guessing at P, but cannot otherwise sign the session key.

The A-EKE scheme does not work with the public-key variant of EKE, since in it one party chooses

the session key and imposes it on the other. This permits a man-in-the-middle attack by an attacker

who has captured P´.

Applications of EKE

Bellovin and Merritt suggest using this protocol for secure public telephones [109]:

Let us assume that encrypting public telephones are deployed. If someone wishes to use

one of these phones, some sort of keying information must be provided. Conventional

solutions...require that the caller possess a physical key. This is undesirable in many

situations. EKE permits use of a short, keypad-entered password, but uses a much longer

session key for the call.

EKE would also be useful with cellular phones. Fraud has been a problem in the cellular

industry; EKE can defend against it (and ensure the privacy of the call) by rendering a

phone useless if a PIN has not been entered. Since the PIN is not stored within the phone,

it is not possible to retrieve one from a stolen unit.

EKE™s primary strength is that both symmetric and public-key cryptography work together in a

manner that strengthens them both:

From a general perspective, EKE functions as a privacy amplifier. That is, it can be used to

strengthen comparatively weak symmetric and asymmetric systems when used together.

Page 435 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Consider, for example, the key size needed to maintain security when using exponential

key exchange. As LaMacchia and Odlyzko have shown [934], even modulus sizes once

believed to be safe (to wit, 192 bits) are vulnerable to an attack requiring only a few

minutes of computer time. But their attack is not feasible if one must first guess a

password before applying it.

Conversely, the difficulty of cracking exponential key exchange can be used to frustrate

attempts at password-guessing. Password-guessing attacks are feasible because of how

rapidly each guess may be verified. If performing such verification requires solving an

exponential key exchange, the total time, if not the conceptual difficulty, increases

dramatically.

EKE is patented [111].

22.6 Fortified Key Negotiation

This scheme also protects key-negotiation schemes from poorly chosen passwords and man-in-the-

middle attacks [47,983]. It uses a hash function of two variables that has a very special property: It

has many collisions on the first variable while having effectively no collisions on the second variable.

H´(x, y) = H(H(k, x) mod 2m, x),

where H(k, x) is an ordinary hash function on k and x

Here™s the protocol. Alice and Bob share a secret password, P, and have just exchanged a secret key,

K, using Diffie-Hellman key exchange. They use P to check that their two session keys are the same

(and that Eve is not attempting a man-in-the-middle attack), without giving P away to Eve.

(1) Alice sends Bob

H´ (P, K)

(2) Bob computes H´ (P, K) and compares his result with what he received from Alice. If

they match he sends Alice

H´(H(P, K))

(3) Alice computes H´ (H(P, K)) and compares her result with what she received from

Bob.

If Eve is trying a man-in-the-middle attack, she shares one key, K1, with Alice, and another key, K2,

with Bob. To fool Bob in step (2), she has to figure out the shared password and then send Bob H´ *

(P, K2). With a normal hash function she can try common passwords until she guesses the correct one,

and then successfully infiltrate the protocol. But with this hash function, many passwords are likely to

produce the same value when hashed with K1. So when she finds a match, she will probably have the

wrong password, and hence Bob will not be fooled.

22.7 Conference Key Distribution and Secret Broadcasting

Alice wants to broadcast a message, M, from a single transmitter. However, she doesn™t want it to be

intelligible by every listener. In fact, she only wants a select subset of listeners to be able to recover M.

Everyone else should get nonsense.

Alice can share a different key (secret or public) with each listener. She encrypts the message in some

random key, K. Then she encrypts a copy of K with each of the keys of her intended recipients.

Finally, she broadcasts the encrypted message and then all of the encrypted Ks. Bob, who is listening,

Page 436 of 666

Applied Cryptography: Second Edition - Bruce Schneier

either tries to decrypt all the Ks with his secret key, looking for one that is correct, or, if Alice doesn™t

mind everyone knowing who her message is for, he looks for his name followed by an encrypted key.

Multiple-key cryptography, previously discussed, also works.

Another method is suggested in [352]. First, each listener shares a secret key with Alice, one that is

larger than any possible encrypted message. All of those keys should be pairwise prime. She encrypts

the message in a random key, K. Then, she computes a single integer, R, such that R modulo a secret

key is congruent to K when that secret key is supposed to decrypt the message, and R modulo a secret

key is otherwise congruent to zero.

For example, if Alice wants the secret to be received by Bob, Carol, and Ellen, but not by Dave and

Frank, she encrypts the message with K and then computes R such that

GK(mod KB)

RG

R GK(mod KC)

G

G0

R G (mod KD)

GK(mod KE)

RG

G0

R G (mod KF)

This is a straightforward algebra problem, one that Alice can solve easily. When listeners receive the

broadcast, they compute the received key modulo their secret key. If they were intended to receive the

message, they recover the key. Otherwise, they recover nothing.

Yet a third way, using a threshold scheme (see Section 3.7), is suggested in [141]. Like the others,

every potential receiver gets a secret key. This key is a shadow in a yet-uncreated threshold scheme.

Alice saves some secret keys for herself, adding some randomness to the system. Let™s say there are k

people out there.

Then, to broadcast M, Alice encrypts M with key K and does the following.

(1) Alice chooses a random number, j. This number serves to hide the number of

recipients of the message. It doesn™t have to be very large; it can be as small as 0.

(2) Alice creates a (k + j + 1, 2k + j + 1) threshold scheme, with:

K as the secret.

The secret keys of the intended recipients as shadows.

The secret keys of nonrecipients not as shadows.

j randomly chosen shadows, not the same as any of the secret keys.

(3) Alice broadcasts k + j randomly chosen shadows, none of which is any of the shadows

listed in step (2).

(4) All listeners who receive the broadcast add their shadow to the k + j shadows they

received. If adding their shadow allows them to calculate the secret, then they have recovered

the key. If it does not, then they haven™t.

Another approach can be found in [885,886,1194]. For yet another approach, see [1000].

Conference Key Distribution

This protocol allows a group of n users to agree on a secret key using only insecure channels. The

group shares two large primes, p and q, and a generator g the same size as q.

Page 437 of 666

Applied Cryptography: Second Edition - Bruce Schneier

(1) User i, where i goes from 1 to n, chooses a random ri less than q, and broadcasts

zi = gri mod p

(2) Every user verifies that zjq G (mod p), for all i from 1 to n.

G1

(3) User i broadcasts

xi = (zi+1/zi-1)ri mod p

(4) User i computes

K = (zi-1)nri * xin-1 * xi+1n-2 *...* xi-2 mod p

All index computations in the above protocol”i - 1, i - 2, and i + 1”should be computed mod n. At

the end of the protocol, all honest users have the same K. No one else gets anything. However, this

protocol falls to a man-in-the-middle attack. Another protocol, not quite as pretty, is in [757].

Tatebayashi-Matsuzaki-Newman

This key distribution protocol is suitable for networks [1521]. Alice wants to generate a session key

with Bob using Trent, the KDC. All parties know Trent™s public key, n. Trent knows the two large

primes that n factors to, and hence can easily take cube roots modulo n. A lot of the details are left out

of the following protocol, but you get the idea.

(1) Alice chooses a random number, rA, and sends Trent

rA3 mod n

(2) Trent tells Bob that someone wants to exchange a key with him.

(3) Bob chooses a random number, rB, and sends Trent

rB3 mod n

(4) Trent uses his private key to recover rA and rB. He sends Alice

rA rB

(5) Alice calculates

(rA rB) rA = rB

She uses this rB to communicate securely with Bob.

This protocol looks good, but it has a horrible flaw. Carol can listen in on step (3) and use that

information, with the help of an unsuspecting Trent and another malicious user (Dave), to recover rB

[1472].

(1) Carol chooses a random number, rC, and sends Trent

rB3rC3 mod n

(2) Trent tells Dave that someone wants to exchange a key with him.

(3) Dave chooses a random number, rD, and sends Trent

rD3 mod n

(4) Trent uses his private key to recover rC and rD. He sends Carol

(rBrC) mod n rD

(5) Dave sends rD to Carol.

Page 438 of 666

Applied Cryptography: Second Edition - Bruce Schneier

(6) Carol uses rC and rD to recover rB. She uses rB to eavesdrop on Alice and Bob.

This is not good.

Chapter 23

Special Algorithms for Protocols

23.1 Multiple-Key Public-Key Cryptography

This is a generalization of RSA (see Section 19.3) [217,212]. The modulus, n, is the product of two

G1

primes, p and q. However, instead of choosing e and d such that ed G mod ((p - 1)(q - 1)), choose t

keys, Ki, such that

G1

G mod ((p - 1)(q - 1))

K1 * K2 *...* Kt

Since

MK1*K2*...*Kt = M

this is a multiple-key scheme as described in Section 3.5.

If, for example, there are five keys, a message encrypted with K3 and K5 can be decrypted with K1 ,

K2 , and K4:

C = MK3*K5 mod n

M = CK1*K2*K4 mod n

One use for this is multisignatures. Imagine a situation where both Alice and Bob have to sign a

document for it to be valid. Use three keys: K1, K2 , and K3. The first two are issued one each to Alice

and Bob,and the third is made public.

(1) First Alice signs M and sends it to Bob.

M' = MK1 mod n

(2) Bob can recover M from M'.

M = M'K2*K3 mod n

(3) He can also add his signature.

M" = M'K2 mod n

(4) Anyone can verify the signature with K3 , the public key.

M = M"K3 mod n

Note that a trusted party is needed to set this system up and distribute the keys to Alice and Bob.

Another scheme with the same problem is [484]. Yet a third scheme is [695,830,700], but the effort in

verification is proportional to the number of signers. Newer schemes [220,1200] based on zero-

knowledge identification schemes solve both shortcomings of the previous systems.

23.2 Secret-Sharing Algorithms

Page 439 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Back in Section 3.7 I discussed the idea behind secret-sharing schemes. The four different algorithms

that follow are all particular cases of a general theoretical framework [883].

LaGrange Interpolating Polynomial Scheme

Adi Shamir uses polynomial equations in a finite field to construct a threshold scheme [1414]. Choose

a prime, p, which is both larger than the number of possible shadows and larger than the largest

possible secret. To share a secret, generate an arbitrary polynomial of degree m -1. For example, if

you want to create a (3,n)-threshold scheme (three shadows are necessary to reconstruct M),generate a

quadratic polynomial

(ax2 + bx + M) mod p

where p is a random prime larger than any of the coefficients. The coefficients a and b are chosen

randomly; they are kept secret and discarded after the shadows are handed out. M is the message.

The prime must be made public.

The shadows are obtained by evaluating the polynomial at n different points:

ki = F(xi)

In other words, the first shadow could be the polynomial evaluated at x = 1, the second shadow could

be the polynomial evaluated at x = 2, and so forth.

Since the quadratic polynomial has three unknown coefficients, a, b, and M, any three shadows can be

used to create three equations. Two shadows cannot. One shadow cannot. Four or five shadows are

redundant.

For example, let M be 11. To construct a (3, 5)-threshold scheme, where any three of five people can

reconstruct M, first generate a quadratic equation (7 and 8 were chosen randomly):

F(x) = (7x2 + 8x + 11) mod 13

The five shadows are:

G0

G (mod 13)

k1 = F(1) = 7 + 8 + 11

G3

k2 = F(2) = 28 + 16 + 11 G (mod 13)

G7

k3 = F(3) = 63 + 24 + 11 G (mod 13)

G12

k4 = F(4) = 112 + 32 + 11 G (mod 13)

G5

k5 = F(5) = 175 + 40 + 11 G (mod 13)

To reconstruct M from three of the shadows, for example k2 , k3 , and k5 , solve the set of linear

equations:

a * 22 + b * 2 + M G3

G (mod 13)

a * 32 + b * 3 + M G7

G (mod 13)

a * 52 + b * 5 + M G5

G (mod 13)

Page 440 of 666

Applied Cryptography: Second Edition - Bruce Schneier

The solution will be a =7, b =8, and M =11. So M is recovered.

This sharing scheme can be easily implemented for larger numbers. If you want to divide the message

into 30 equal parts such that any six can get together and reproduce the message, give each of the 30

people the evaluation of a polynomial of degree 6.

F(x) = (ax6 + bx5 + cx4 + dx3 + ex2 + fx + M) mod p

Six people can solve for the six unknowns (including M); five people cannot learn anything about M.

The most mind-boggling aspect of secret sharing is that if the coefficients are picked randomly, five

people with infinite computing power can™t learn anything more than the length of the message

(which each of them knows anyway). This is as secure as a one-time pad; an attempt at exhaustive

search (that is, trying all possible sixth shadows) will reveal that any conceivable message could be the

secret. This is true for all the secret-sharing schemes presented here.

Vector Scheme

George Blakley invented a scheme using points in space [182]. The message is defined as a point in m-

dimensional space. Each shadow is the equation of an (m -1)-dimensional hyperplane that includes the

point. The intersection of any m of the hyperplanes exactly determines the point.

For example, if three shadows are required to reconstruct the message, then it is a point in three-

dimensional space. Each shadow is a different plane. With one shadow, you know the point is

somewhere on the plane. With two shadows, you know the point is somewhere on the line formed

where the two planes intersect. With three shadows, you can determine the point exactly: the

intersection of the three planes.

Asmuth-Bloom

This scheme uses prime numbers [65]. For an (m, n)-threshold scheme, choose a large prime, p,

greater than M. Then choose n numbers less than p, d1 , d2 , ..., dn, such that:

1. The d values are in increasing order; di < di+1

2. Each di is relatively prime to every other di

3. d1 * d2 * ... * dm > p * dn-m+2 * dn-m+3 * ... * dn

To distribute the shadows, first choose a random value r and compute

M' = M + rp

The shadows, ki, are

ki = M' mod di

Any m shadows can get together and reconstruct M using the Chinese remainder theorem, but any m -

1 cannot. See [65] for details.

Page 441 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Karnin-Greene-Hellman

This scheme uses matrix multiplication [818]. Choose n +1 m-dimensional vectors, V0 , V1 , ..., Vn,

such that any possible m * m matrix formed out of those vectors has rank m. The vector U is a row

vector of dimension m +1.

M is the matrix product U·V0. The shadows are the products U·Vi, where i is a number from 1 to n.

Any m shadows can be used to solve the m * m system of linear equations, where the unknowns are

the coefficients of U. UV0 can be computed from U. Any m -1 shadows cannot solve the system of

linear equations and therefore cannot recover the secret.

Advanced Threshold Schemes

The previous examples illustrate only the simplest threshold schemes: Divide a secret into n shadows

such that any m can be used to recover the secret. These algorithms can be used to create far more

complicated schemes. The following examples will use Shamir™s algorithm, although any of the others

will work.

To create a scheme in which one person is more important than another, give that person more

shadows. If it takes five shadows to recreate a secret and one person has three shadows while

everyone else has only one, then that person and two other people can recreate the secret. Without

that person, it takes five to recreate the secret.

Two or more people could get multiple shadows. Each person could have a different number of

shadows. No matter how the shadows are distributed, any m of them can be used to reconstruct the

secret. Someone with m -1 shadows, be it one person or a roomful of people, cannot do it.

In other types of schemes, imagine a scenario with two hostile delegations. You can share the secret so

that two people from the 7 in Delegation A and 3 people from the 12 in Delegation B are required to

reconstruct the secret. Make a polynomial of degree 3 that is the product of a linear expression and a

quadratic expression. Give everyone from Delegation A a shadow that is the result of an evaluation of

the linear equation; give everyone from Delegation B a shadow that is the evaluation of the quadratic

equation.

Any two shadows from Delegation A can be used to reconstruct the linear equation, but no matter

how many other shadows the group has, they cannot get any information about the secret. The same

is true for Delegation B: They can get three shadows together to reconstruct the quadratic equation,

but they cannot get any more information necessary to reconstruct the secret. Only when the two

delegations share their equations can they be multiplied to reconstruct the secret.

In general, any type of sharing scheme that can be imagined can be implemented. All you have to do is

to envision a system of equations that corresponds to the particular scheme. Some excellent papers on

generalized secret-sharing schemes are [1462,1463,1464].

Sharing a Secret with Cheaters

This algorithm modifies the standard (m, n)-threshold scheme to detect cheaters [1529]. I demonstrate

this using the Lagrange scheme, although it works with the others as well.

Page 442 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Choose a prime, p, that is both larger than n and larger than

(s - 1) (m - 1)/e + m

where s is the largest possible secret and e is the probability of successful cheating. You can make e as

small as you want; it just makes the computation more complex. Construct your shadows as before,

except instead of using 1, 2, 3,..., n for xi, choose random numbers between 1 and p - 1 for xi.

Now, when Mallory sneaks into the secret reconstruction meeting with his false share, his share has a

high probability of not being possible. An impossible secret is, of course, a fake secret. See [1529] for

the math.

Unfortunately, while Mallory is exposed as a cheater, he still learns the secret (assuming that there are

m other valid shares). Another protocol, from [1529,975], prevents that. The basic idea is to have a

series of k secrets, such that none of the participants knows beforehand which is correct. Each secret

is larger than the one before, except for the real secret. The participants combine their shadows to

generate one secret after the other, until they create a secret that is less than the previous secret.

That™s the correct one.

This scheme will expose cheaters early, before the secret is generated. There are complications when

the participants deliver their shadows one at a time; refer to the papers for details. Other papers on

the detection and prevention of cheaters in threshold schemes are [355,114,270].

23.3 Subliminal Channel

Ong-Schnorr-Shamir

This subliminal channel (see Section 4.2), designed by Gustavus Simmons [1458,1459,1460], uses the

Ong-Schnorr-Shamir identification scheme (see Section 20.5). As in the original scheme, the sender

(Alice) chooses a public modulus, n, and a private key, k, such that n and k are relatively prime.

Unlike the original scheme, k is shared between Alice and Bob, the recipient of the subliminal

message.

The public key is calculated:

h = -k2 mod n

If Alice wants to send the subliminal message M by means of the innocuous message M', she first

confirms that M' and n are relatively prime, and that M and n are relatively prime.

Alice calculates

S1 = 1/2 * ((M' /M + M)) mod n

S2 = k/2 * ((M' /M - M)) mod n

Together, the pair, S1 and S2, is the signature under the traditional Ong-Schnorr-Shamir scheme and

the carrier of the subliminal message.

Walter the warden (remember him?) can authenticate the message as described by the Ong-Schnorr-

Shamir signature scheme, but Bob can do better. He can authenticate the message (it is always

Page 443 of 666

Applied Cryptography: Second Edition - Bruce Schneier

possible that Walter can make his own messages). He confirms that

S12 - S2 2/k2 GM'

G (mod n)

If the message is authentic, the receiver can recover the subliminal message using this formula:

M = M'/(S1 + S2 k-1) mod n

This works, but remember that the basic Ong-Schnorr-Shamir has been broken.

ElGamal

Simmons™s second subliminal channel [1459], described in [1407,1473], is based on the ElGamal

signature scheme (see Section 19.6).

Key generation is the same as the basic ElGamal signature scheme. First choose a prime, p, and two

random numbers, g and r, such that both g and r are less than p. Then calculate

K = gr mod p

The public key is K, g, and p. The private key is r. Besides Alice, Bob also knows r; it is the key that is

used to send and read the subliminal message in addition to being the key used to sign the innocuous

message.

To send a subliminal message M using the innocuous message M', M and p must be all relatively

prime to each other, and M and p -1 must be relatively prime. Alice calculates

X = gM mod p

and solves the following equation for Y (using the extended Euclidean algorithm):

M' = rX + MY mod (p - 1)

As in the basic ElGamal scheme, the signature is the pair: X and Y.

Walter can verify the ElGamal signature. He confirms that

KXXY GgM' (mod p)

G

Bob can recover the subliminal message. First he confirms that

(gr)X XY G M' (mod p)

Gg

If it does, he accepts the message as genuine (not from Walter).

Then, to recover M, he computes

M = (Y“1 (M' - rX)) mod (p - 1)

Page 444 of 666

Applied Cryptography: Second Edition - Bruce Schneier

For example, let p =11 and g =2. The private key, r, is chosen to be 8. This means the public key,

which Walter can use to verify the signature, is gr mod p =28 mod 11 =3.

To send the subliminal message M =9, using innocuous message M'= 5, Alice confirms that 9 and 11

are relatively prime and that 5 and 11 are relatively prime. She also confirms that 9 and 11 -1 =10 are

relatively prime. They are, so she calculates

X = gM mod p = 29 mod 11 = 6

Then, she solves the following equation for Y:

5 = 8 * 6 + 9 * Y mod 10

Y = 3, so the signature is the pair, X and Y: 6 and 3.

Bob confirms that

(gr)X XY G M' (mod p)

Gg

(28)663 G 5 (mod 11)

G2

It does (do the math yourself if you don™t trust me), so he then recovers the subliminal message by

calculating

M = (Y“1 (M' - rX)) mod (p - 1) = 3-1(5 - 8 * 6) mod 10 = 7(7) mod 10 = 49 mod 10 = 9

ESIGN

A subliminal channel can be added to ESIGN [1460] (see Section 20.6).

In ESIGN, the secret key is a pair of large prime numbers, p and q, and the public key is n =p2q . With

a subliminal channel, the private key is three primes, p, q, and r, and the public key is n, such that

n = p2qr

The variable, r, is the extra piece of information that Bob needs to read the subliminal message.

To sign a normal message, Alice first picks a random number, x, such that x is less than pqr and

computes:

w, the least integer that is larger than (H(m) - xk mod n)/pqr)

s = x + ((w/kxk-1) mod p)pqr

H(m) is the hash of the message; k is a security parameter. The value s is the signature.

To verify the signature, Bob computes sk mod n. He also computes a, which is the least integer larger

than 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.

To send a subliminal message, M, using the innocuous message, M', Alice calculates s using M in place

Page 445 of 666

Applied Cryptography: Second Edition - Bruce Schneier

of H(m). This means that the message must be smaller than p2qr. She then chooses a random value, u,

and calculates

x' = M' + ur

Then, use this x' value as the “random number” x to sign M'. This second s value is sent as a

signature.

Walter can verify that s (the second s) is a valid signature of M'.

Bob can also authenticate the message in the same way. But, since he also knows r, he can calculate

GM

G (mod r)

s = x' + ypqr = M + ur + ypqr

This implementation of a subliminal channel is far better than the previous two. In the Ong-Schnorr-

Shamir and ElGamal implementations, Bob has Alice™s private key. Besides being able to read

subliminal messages from Alice, Bob can impersonate Alice and sign normal documents. Alice can do

nothing about this; she must trust Bob to set up this subliminal channel.

The ESIGN scheme doesn™t suffer from this problem. Alice™s private key is the set of three primes: p,

q, and r. Bob™s secret key is just r. He knows n =p2qr, but to recover p and q he has to factor that

number. If the primes are large enough, Bob has just as much trouble impersonating Alice as would

Walter or anyone else.

DSA

There is also a subliminal channel in DSA (see Section 20.1) [1468,1469,1473]. In fact, there are

several. The simplest subliminal channel involves the choice of k. It is supposed to be a 160-bit

random number. However, if Alice chooses a particular k, then Bob, who also knows Alice™s private

key, can recover it. Alice can send Bob a 160-bit subliminal message in each DSA signature; everyone

else simply verifies Alice™s signature. Another complication: Since k should be random, Alice and Bob

need to share a one-time pad and encrypt the subliminal message with the one-time pad to generate a

k.

DSA has subliminal channels that do not require Bob to know Alice™s private key. These also involve

choosing particular values of k, but cannot be used to send 160 bits of information. This scheme,

presented in [1468,1469], allows Alice and Bob to exchange one bit of subliminal information per

signed message.

(1) Alice and Bob agree on a random prime, P (different from the parameter p in the

signature scheme). This is their secret key for the subliminal channel.

(2) Alice signs an innocuous message, M. If she wants to send Bob the subliminal bit, 1,

she makes sure the r parameter of the signature is a quadratic residue modulo P. If she wants to

send him a 0, she makes sure the r parameter is a quadratic nonresidue modulo P. She does this

by signing the message with random k values until she gets a signature with an r with the

requisite property. Since quadratic residues and quadratic nonresidues are equally likely, this

shouldn™t be too difficult.

(3) Alice sends the signed message to Bob.

(4) Bob verifies the signature to make sure the message is authentic. Then he checks

whether r is a quadratic residue or a quadratic nonresidue modulo P and recovers the

subliminal bit.

Page 446 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Sending multiple bits via this method involves making r either a quadratic residue or a quadratic

nonresidue modulo a variety of parameters. See [1468,1469] for details.

This scheme can be easily extended to send multiple subliminal bits per signature. If Alice and Bob

agree on two random primes, P and Q, Alice can send two bits by choosing a random k such that r is

either a quadratic residue mod P or a quadratic nonresidue mod P, and either a quadratic residue

mod Q or a quadratic nonresidue mod Q. A random value of k has a 25 percent chance of producing

an r of the correct form.

Here™s how Mallory, an unscrupulous implementer of DSA,can have the algorithm leak 10 bits of

Alice™s private key every time she signs a document.

(1) Mallory puts his implementation of DSA in a tamperproof VLSI chip, so that no one

can examine its inner workings. He creates a 14-bit subliminal channel in his implementation of

DSA. That is, he chooses 14 random primes, and has the chip choose a value of k such that r is

either a quadratic residue or a quadratic nonresidue modulo each of those 14 primes, depending

on the subliminal message.

(2) Mallory distributes the chips to Alice, Bob, and everyone else who wants them.

(3) Alice signs a message normally, using her 160-bit private key, x.

(4) The chip randomly chooses a 10-bit block of x: the first 10 bits, the second 10 bits, and

so on. Since there are 16 possible 10-bit blocks, a 4-bit number can identify which block it is.

This 4-bit identifier, plus the 10 bits of the key, is the 14-bit subliminal message.

(5) The chip tries random values of k until it finds one that has the correct quadratic

residue properties to send the subliminal message. The odds of a random k being of the correct

form are 1 in 16,384. Assuming the chip can test 10,000 values of k per second, it will find one in

less than two seconds. This computation does not involve the message and can be performed off-

line, before Alice wants to sign a message.

(6) The chip signs the message normally, using the value of k chosen in step (5).

(7) Alice sends the digital signature to Bob, or publishes it on the network, or whatever.

(8) Mallory recovers r and, because he knows the 14 primes, decrypts the subliminal

message.

It™s scary that even if Alice knows what is happening, she cannot prove it. As long as those 14 secret

primes stay secret, Mallory is safe.

Foiling the DSA Subliminal Channel

The subliminal channel relies on the fact that Alice can choose k to transmit subliminal information.

To foil the subliminal channel, Alice cannot be allowed to choose k. However, neither can anyone else;

if someone else were allowed to choose k, it would allow that person to forge Alice™s signature. The

only solution is for Alice to jointly generate k with another party, call him Bob, in such a way that

Alice cannot control a single bit of k and Bob cannot know a single bit of k. At the end of the protocol,

Bob should be able to verify that Alice used the k that they jointly generated.

Here™s the protocol [1470,1472,1473]:

(1) Alice chooses k' and sends Bob

u = gk' mod p

Page 447 of 666

Applied Cryptography: Second Edition - Bruce Schneier

(2) Bob chooses k" and sends it to Alice.

(3) Alice calculates k = k'k" mod (p - 1). She uses k to sign her message, M, with the DSA

and sends Bob the signature: r and s.

(4) Bob verifies that

((uk" mod p) mod q) = r

If it does, he knows that k was used to sign M.

After step (4), Bob knows that no subliminal information can be embedded in r. If he is a trusted

party, he can certify that Alice™s signature is subliminal-free. Others will have to trust his

certification; Bob cannot prove this fact to a third party with a transcript of the protocol.

A surprising result is that if Bob wants to, he can use this protocol to create his own subliminal

channel. Bob can embed a subliminal message in one of Alice™s signatures by choosing k" with certain

characteristics. When Simmons discovered this, he dubbed it the “Cuckoo™s Channel.” Details on how

the Cuckoo™s Channel works, and a three-pass protocol for generating k that prevents it, are

discussed in [1471,1473].

Other Schemes

Any signature scheme can be converted into a subliminal channel [1458,1460,1406]. A protocol for

embedding a subliminal channel in the Fiat-Shamir and Feige-Fiat-Shamir protocols, as well as

possible abuses of the subliminal channel, can be found in [485].

23.4 Undeniable Digital Signatures

This undeniable signature algorithm (see Section 4.3) is by David Chaum [343,327]. First, a large

prime, p, and a primitive element, g, are made public, and used by a group of signers. Alice has a

private key, x, and a public key, gx mod p.

To sign a message, Alice computes z =mx mod p.That™s all she has to do.

Verification is a little more complicated.

(1) Bob chooses two random numbers, a and b, both less than p, and sends Alice:

c = za(gx)b mod p

(2) Alice computes t=x“1 mod (p - 1), and sends Bob:

d = ct mod p

(3) Bob confirms that

d G agb (mod p)

Gm

If it is, he accepts the signature as genuine.

Imagine that Alice and Bob went through this protocol, and Bob is now convinced that Alice signed

the message. Bob wants to convince Carol, so he shows her a transcript of the protocol. Dave,

however, wants to convince Carol that some other person signed the document. He creates a fake

transcript of the protocol. First he generates the message in step (1). Then in step (3) he generates d

and the fake transmission from this other person in step (2). Finally, he creates the message in step (2).

To Carol, both Bob™s and Dave™s transcripts are identical. She cannot be convinced of the signature™s

Page 448 of 666

Applied Cryptography: Second Edition - Bruce Schneier

validity unless she goes through the protocol herself.

Of course, if she were watching over Bob™s shoulder as he completed the protocol, she would be

convinced. Carol has to see the steps done in order, just as Bob does.

There may be a problem with this signature scheme, but I know of no details. Please pay attention to

the literature before you use it.

Another protocol not only has a confirmation protocol”Alice can convince Bob that her signature is

valid”but it also has a disavowal protocol; Alice can use a zero-knowledge interactive protocol to

convince him that the signature is not valid, if it is not [329].

Like the previous protocol, a group of signers use a shared public large prime, p, and a primitive

element, g. Alice has a unique private key, x, and a public key, gx mod p. To sign a message, Alice

computes z =mx mod p.

To verify a signature:

(1) Bob chooses two random numbers, a and b, both less than p, and sends Alice:

c = magb mod p

(2) Alice chooses a random number, q, less than p, and computes and sends to Bob:

s1 = cgq mod p, s2 = (cgq)x mod p

(3) Bob sends Alice a and b, so that Alice can confirm that Bob did not cheat in step (1).

(4) Alice sends Bob q, so that Bob can use mx and reconstruct s1 and s2. If then the

signature is valid.

s1 G q (mod p)

Gcg

G x)b +qza (mod p)

G(g

s2

Alice can also disavow a signature, z, for a message, m. See [329] for details.

Additional protocols for undeniable signatures can be found in [584,344]. Lein Harn and Shoubao

Yang proposed a group undeniable signature scheme [700].

Convertible Undeniable Signatures

An algorithm for a convertible undeniable signature, which can be verified, disavowed, and also

converted to a conventional digital signature is given in [213]. It™s based on the ElGamal digital

signature algorithm.

Like ElGamal, first choose two primes, p and q, such that q divides p -1. Now you have to create a

number, g, less than q. First choose a random number, h, between 2 and p -1. Calculate

g = h( p-1)/q mod p

If g equals the 1, choose another random h. If it doesn™t, stick with the g you have.

The private keys are two different random numbers, x and z, both less than q. The public keys are p,

q, g, y, and u, where

Page 449 of 666

Applied Cryptography: Second Edition - Bruce Schneier

y = gx mod p

u = gz mod p

To compute the convertible undeniable signature of message m (which is actually the hash of a

message), first choose a random number, t, between 1 and q -1. Then compute

T = gt mod p

and

m' = Ttzm mod q.

Now, compute the standard ElGamal signature on m'. Choose a random number, R, such that R is less

than and relatively prime to p -1. Then compute r =gR mod p, and use the extended Euclidean

algorithm to compute s, such that

Grx

G + Rs (mod q)

m'

The signature is the ElGamal signature (r, s), and T.

Here™s how Alice verifies her signature to Bob:

(1) Bob generates two random numbers, a and b. He computes c = TTmagb mod p and

sends that to Alice.

(2) Alice generates a random number, k, and computes h1 = cgk mod p, and h2 = h1 z mod

p, and sends both of those numbers to Bob.

(3) Bob sends Alice a and b.

(4) Alice verifies that c = TTmagb mod p. She sends k to Bob.

(5) Bob verifies that h1 = TTmagb+k mod p, and that h2 = yrarsaub+k mod p.

Alice can convert all of her undeniable signatures to normal signatures by publishing z. Now, anyone

can verify her signature without her help.

Undeniable signature schemes can be combined with secret-sharing schemes to create distributed

convertible undeniable signatures [1235]. Someone can sign a message, then distribute the ability to

confirm that the signature is valid. He might, for example, require three out of five people to

participate in the protocol in order to convince Bob that the signature is valid. Improvements on this

notion deleted the requirement for a trusted dealer [700,1369].

23.5 Designated Confirmer Signatures

Here™s how Alice can sign a message and Bob can verify it, such that Carol can verify Alice™s

signature at some later time to Dave (see Section 4.4) [333].

First, a large prime, p, and a primitive element, g, are made public and used by a group of users. The

product of two primes, n, is also public. Carol has a private key, z, and a public key is h =gx mod p.

In this protocol Alice can sign m such that Bob is convinced that the signature is valid,but cannot

convince a third party.

Page 450 of 666

Applied Cryptography: Second Edition - Bruce Schneier

(1) Alice chooses a random x and computes

a = gx mod p

b = hx mod p

She computes the hash of m, H(m), and the hash of a and b concatenated, H(a,b). She then

computes

j = (H(m) H(a, b))1/3 mod n

and sends a, b, and j to Bob.

(2) Bob chooses two random numbers, s and t, both less than p, and sends Alice

c = gsht mod p

(3) Alice chooses a random q less than p, and sends Bob

d = gq mod p

e = (cd)x mod p

(4) Bob sends Alice s and t.

(5) Alice confirms that

gsht G (mod p)

Gc

Then she sends Bob q.

(6) Bob confirms

d G q (mod p)

Gg

e/aq Gasbt (mod p)

G

H(m) H(a, b) Gj1/3 mod n

G

If they all check out, he accepts the signature as genuine.

Bob cannot use a transcript of this proof to convince Dave that the signature is genuine, but Dave can

conduct a protocol with Alice™s designated confirmer, Carol. Here™s how Carol convinces Dave that a

and bconstitute a valid signature.

(1) Dave chooses a random u and v, both less than p, and sends Carol

k = guav mod p

(2) Carol chooses a random w, less than p, and sends Dave

l = gw mod p

y = (kl)z mod p

(3) Dave sends Carol u and v.

(4) Carol confirms that

guav Gk (mod p)

G

Then she sends Dave w.

(5) Dave confirms that

gw G (mod p)

Gl

y/hw G ubv (mod p)

Gh

If they both check out, he accepts the signature as genuine.

In another protocol Carol can convert the designated-confirmer protocol into a conventional digital

signature. See [333] for details.

Page 451 of 666

Applied Cryptography: Second Edition - Bruce Schneier

23.6 Computing with Encrypted Data

The Discrete Logarithm Problem

There is a large prime, p, and a generator, g. Alice has a particular value for x, and wants to know e,

such that

ge Gx

G (mod p)

This is a hard problem, and Alice lacks the computational power to compute the result. Bob has the

power to solve the problem”he represents the government, or a large computing organization, or

whatever. Here™s how Bob can do it without Alice revealing x [547,4]:

(1) Alice chooses a random number, r, less than p.

(2) Alice computes

x' = xgr mod p

(3) Alice asks Bob to solve

ge' G (mod p)

Gx'

(5) Bob computes e' and sends it to Alice.

(6) Alice recovers e by computing

e = (e' - r) mod (p - 1)

Similar protocols for the quadratic residuosity problem and for the primitive root problem are in

[3,4]. (See also Section 4.8.)

23.7 Fair Coin Flips

The following protocols allow Alice and Bob to flip a fair coin over a data network (see Section 4.9)

[194]. This is an example of flipping a coin into a well (see Section 4.10). At first, only Bob knows the

result of the coin toss and tells it to Alice. Later, Alice may check to make sure that Bob told her the

correct outcome of the toss.

Coin Flipping Using Square Roots

Coin-flip subprotocol:

(1) Alice chooses two large primes, p and q, and sends their product, n to Bob.

(2) Bob chooses a random positive integer, r, such that r is less than n/2. Bob computes

z = r2 mod n

and sends z to Alice.

(3) Alice computes the four square roots of z (mod n). She can do this because she knows

the factorization of n. Let™s call them +x, -x, +y, and -y. Call x' the smaller of these two

numbers:

x mod n

-x mod n

Similarly, call y' the smaller of these two numbers:

Page 452 of 666

Applied Cryptography: Second Edition - Bruce Schneier

y mod n

-y mod n

Note that r is equal either to x' or y'.

(4) Alice guesses whether r = x' or r = y', and sends her guess to Bob.

(5) If Alice™s guess is correct, the result of the coin flip is heads. If Alice™s guess is

incorrect, the result of the coin flip is tails. Bob announces the result of the coin flip.

Verification subprotocol:

(6) Alice sends p and q to Bob.

(7) Bob computes x' and y' and sends them to Alice.

(8) Alice calculates r.

Alice has no way of knowing r, so her guess is real. She only tells Bob one bit of her guess in step (4) to

prevent Bob from getting both x' and y'. If Bob has both of those numbers, he can change r after step

(4).

Coin Flipping Using Exponentiation Modulo p

Exponentiation modulo a prime number, p, is used as a one-way function in this protocol [1306]:

Coin-flip subprotocol:

(1) Alice chooses a prime number, p, in such a way that the factorization of p - 1 is known

and contains at least one large prime.

(2) Bob selects two primitive elements, h and t, in GF(p). He sends them to Alice.

(3) Alice checks that h and t are primitive and then chooses a random integer x, relatively

prime to p - 1. She then computes one of the two values:

y = hx mod p, or y = tx mod p

She sends y to Bob.

(4) Bob guesses whether Alice calculated y as afunction of h or t, and sends his guess to

Alice.

(5) If Bob™s guess is correct, the result of the coin flip is heads. If Bob™s guess is incorrect,

the result of the coin flip is tails. Alice announces the result of the coin flip.

Verification subprotocol:

(6) Alice reveals x to Bob. Bob computes hx mod p and tx mod p, to confirm that Alice has

played fairly and to verify the result of the toss. He also checks that x and p - 1 are relatively

prime.

For Alice to cheat, she has to know two integers, x and x', such that hx tx' (mod p). If she knew those

values,she would be able to calculate:

logt h = x'x-1 mod p - 1 and logth = x-1x' mod p - 1

These are hard problems.

Alice would be able to do this if she knew logt h, but Bob chooses h and t in step (2). Alice has no other

Page 453 of 666

Applied Cryptography: Second Edition - Bruce Schneier

recourse except to try to compute the discrete logarithm. Alice could also attempt to cheat by choosing

an x that is not relatively prime to p -1, but Bob will detect that in step (6).

Bob can cheat if h and t are not primitive in GF(p), but Alice can easily check that after step (2)

because she knows the prime factorization of p -1.

One nice thing about this protocol is that if Alice and Bob want to flip multiple coins, they can use the

same values for p, h, and t. Alice just generates a new x, and the protocol continues from step (3).

Coin Flipping Using Blum Integers

Blum integers can be used in a coin-flipping protocol.

(1) Alice generates a Blum integer, n, a random x relatively prime to n, x0 = x2 mod n, and

x1 = x02 mod n. She sends n and x1 to Bob.

(2) Bob guesses whether x0 is even or odd.

(3) Alice sends x to Bob.

(4) Bob checks that n is a Blum integer (Alice would have to give Bob the factors of n and

proofs of their primality, or execute some zero-knowledge protocol to convince him that n is a

Blum integer), and he verifies that x0 = x2 mod n and x1 = x02 mod n. If all this checks out, Bob

wins the flip if he guessed correctly.

It is crucial that n be a Blum integer. Otherwise, Alice may be able to find an x'0 such that x'02 mod n

=x0 2 mod n =x1 , where x'0 is also a quadratic residue. If x0 were even and x'0 were odd (or vice

versa), Alice could freely cheat.

23.8 One-Way Accumulators

There is a simple one-way accumulator function [116] (see Section 4.12):

A(xi, y) = xi-1y mod n

The numbers n (n is the product of two primes) and x0 must be agreed upon in advance. Then, the

accumulation of y1 , y2 , and y3 would be

((x0 y1 mod n)y2 mod n)y3 mod n

This computation is independent of the order of y1, y2 , and y3.

23.9 All-or-Nothing Disclosure of Secrets

This protocol allows multiple parties (at least two are required for the protocol to work) to buy

individual secrets from a single seller (see Section 4.13) [1374,1175]. First, here™s a definition. Take

two bit strings, x and y. The fixed bit index (FBI) of x and y are the bits where the ith bit of x equals

the ith bit of y.

Page 454 of 666

Applied Cryptography: Second Edition - Bruce Schneier

For example:

x = 110101001011

y = 101010000110

FBI(x, y) = {1, 4, 5, 11}

(We™re reading the bits from right to left, with the right-most bit as zero.)

Now, here™s the protocol. Alice is the seller. Bob and Carol are buyers. Alice has k n-bit secrets: S1,

S2 , ..., Sk. Bob wants to buy secret Sb; Carol wants to buy secret Sc.

(1) Alice generates a public-key/private-key key pair and tells Bob (but not Carol) the

public key. She generates another public-key/private-key key pair and tells Carol (but not Bob)

the public key.

(2) Bob generates k n-bit random numbers, B1 , B2 , ..., Bk, and tells them to Carol. Carol

generates k n-bit random numbers, C1 , C2 , ..., Ck, and tells them to Bob.

(3) Bob encrypts Cb (remember, Sb is the secret he wants to buy) with the public key from

Alice. He computes the FBI of Cb and the result he just encrypted. He sends this FBI to Carol.

Carol encrypts Bc (remember, Sc is the secret she wants to buy) with the public key from Alice.

She computes the FBI of Bc and the result she just encrypted. She sends this FBI to Bob.

(4) Bob takes each of the n-bit numbers B1, B2 , ..., Bk, and replaces every bit whose index

is not in the FBI he received from Carol with its complement. He sends this new list of n-bit

numbers, B'1, B'2, ..., B'k, to Alice.

Carol takes each of the n-bit numbers C1 , C2 , ..., Ck, and replaces every bit whose index is not

in the FBI she received from Bob with its complement. She sends this new list of n-bit numbers,

C'1, C'2, ..., C'k, to Alice.

(5) Alice decrypts all C'i with Bob™s private key, giving her k n-bit numbers: C"1, C"2, ...,

C"k. She computes Si C"i, for i = 1 to k, and sends the results to Bob.

Alice decrypts all B'i with Carol™s private key, giving her k n-bit numbers: B"1, B"2, ..., B"k.

She computes Si B"i, for i = 1 to k, and sends the results to Carol.

(6) Bob computes Sb by XORing Cb and the bth number he received from Alice.

Carol computes Sc by XORing Bc and the cth number she received from Alice.

This is complicated. An example will go a long way to help.

Alice has the following eight 12-bit secrets for sale: S1 =1990, S2 =471, S3 =3860, S4 =1487, S5 =2235,

S6 =3751, S7 =2546, and S8 =4043. Bob wants to buy S7. Carol wants to buy S2.

(1) Alice uses the RSA algorithm. The key pair she will use with Bob is: n = 7387, e =

5145, and d = 777. The key pair she will use with Carol is: n = 2747, e = 1421, and d = 2261. She

tells Bob and Carol each their public key.

(2) Bob generates eight 12-bit random numbers, B1 = 743, B2 = 1988, B3 = 4001, B4 =

2942, B5 = 3421, B6 = 2210, B7 = 2306, and B8 = 222, and tells them to Carol. Carol generates

eight 12-bit random numbers, C1 = 1708, C2 = 711, C3 = 1969, C4 = 3112, C5 = 4014, C6 = 2308,

C7 = 2212, and C8 = 222, and tells them to Bob.

Page 455 of 666

Applied Cryptography: Second Edition - Bruce Schneier

(3) Bob wants to buy S7 , so he encrypts C7 with the public key that Alice gave him.

22125145 mod 7387 = 5928

Now:

2212 = 0100010100100

5928 = 1011100101000

So, the FBI of those two numbers is {0, 1, 4, 5, 6}. He sends this to Carol.

Carol wants to buy S2 , so she encrypts B2 with the public key that Alice gave her and computes the

FBI of B2 with the result of her encryption. She sends {0, 1, 2, 6, 9, 10} to Bob.

(4) Bob takes B1 , B2 , ..., B8 , and replaces every bit whose index is not in the set {0, 1, 2,

6, 9, 10} with its complement. For example:

B2 = 111111000100 = 1988

B'2 = 011001111100 = 1660

He sends B'1, B'2, ..., B'8, to Alice.

Carol takes C1 , C2 , ..., C8 , and replaces every bit whose index is not in the set {0, 1, 4, 5, 6}

with its complement. For example:

C7 = 0100010100100 = 2212

C'7 = 1011100101000 = 5928

She sends C'1, C'2, ..., C'8, to Alice.

(5) Alice decrypts all C'i with Bob™s private key and XORs the results with Si. For

example, for i = 7:

5928777 mod 7387 = 2212; 2546 2212 = 342

She sends the results to Bob.

Alice decrypts all B'i with Carol™s private key and XORs the results with Si. For example, for i =

2:

16602261 (mod 2747) = 1988; 471 1988 = 1555

She sends the results to Carol.

(6) Bob computes S7 by XORing C7 and the seventh number he received from Alice:

2212 342 = 2546

Carol computes S2 by XORing B2 and the second number she received from Alice.

1988 1555 = 471

The protocol works for any number of buyers. If Bob, Carol, and Dave want to buy secrets, Alice

gives each buyer two public keys, one for each of the others. Each buyer gets a set of numbers from

each other buyer. Then, they complete the protocol with Alice for each of their sets of numbers and

XOR all of their final results from Alice to get their secret. More details are in [1374,1175].

Page 456 of 666

Applied Cryptography: Second Edition - Bruce Schneier

Unfortunately, a pair of dishonest parties can cheat. Alice and Carol, working together, can easily

find out what secret Bob is getting: If they know the FBI of Cb and Bob™s encryption algorithm, they

can find b such that Cb has the right FBI. And Bob and Carol, working together, can easily get all the

secrets from Alice.

If you assume honest parties,there™s an easier protocol [389].

(1) Alice encrypts all of the secrets with RSA and sends them to Bob: Ci = Sie mod n

(2) Bob chooses his secret Cb, picks a random r, and sends C', to Alice.

C' = Cbre mod n

(3) Alice sends Bob P'.

P' = C'd mod n

(4) Bob calculates Sb.

Sb = P'r-1 mod n

If the parties may be dishonest, Bob can prove in zero-knowledge that he knows some r such that

C'=Cbre mod n and keep b secret until Alice gives him P' in step (3) [246].

23.10 Fair and Failsafe Cryptosystems

Fair Diffie-Hellman

Fair cryptosystems are a way to do key escrowing in software (see Section 4.14). This example is from

Silvio Micali [1084,1085]. It is patented [1086,1087].

In the basic Diffie-Hellman scheme, a group of users share a prime, p, and a generator, g. Alice™s

private key is s, and her public key is t =gs mod p.

Here™s how to make Diffie-Hellman fair (this example uses five trustees).

(1) Alice chooses five integers, s1 , s2, s3, s4, and s5, each less than p - 1. Alice™s private key

is

s = (s1 + s2 + s3 + s4 + s5) mod p - 1

and her public key is

t = gs mod p

Alice also computes

ti = gsi mod p, for i = 1 to 5

Alice™s public shares are ti, and her private shares are si.

(2) Alice sends a private piece and corresponding public piece to each trustee. For

example, she sends s1 and t1 to trustee 1. She sends t to the KDC.

(3) Each trustee verifies that

ti = gsi mod p

Page 457 of 666

Applied Cryptography: Second Edition - Bruce Schneier

If it does, the trustee signs ti and sends it to the KDC. The trustee stores si in a secure place.