<<

. 19
( 29)



>>

Alice is the same as the one he sent to Alice in step (2), he encrypts RA with K and sends it to
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.

<<

. 19
( 29)



>>