. 17
( 29)


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

ci = mie mod n

To decrypt a message, take each encrypted block ci and compute

mi = cid mod n


cid = (mie)d = mied = mik(p - 1)(q- 1)+ 1 = mi mik(p- 1)(q- 1) = mi*1 = mi; all (mod n)

the formula recovers the message. This is summarized in Table 19.2.

The message could just as easily have been encrypted with d and decrypted with e; the choice is
arbitrary. I will spare you the number theory that proves why this works; most current texts on
cryptography cover it in detail.

A short example will probably go a long way to making this clearer. If p = 47 and q = 71, then

Table 19.2
RSA Encryption
Public Key:
n product of two primes, p and q (p and q must remain secret)
e relatively prime to (p - 1)(q - 1)
Private Key:
d e-1 mod ((p - 1)(q - 1))
c = me mod n
m = cd mod n

n = pq = 3337

The encryption key, e, must have no factors in common with

(p - 1)(q - 1) = 46 * 70 = 3220

Choose e (at random) to be 79. In that case

d = 79-1 mod 3220 = 1019

This number was calculated using the extended Euclidean algorithm (see Section 11.3). Publish e and
n, and keep d secret. Discard p and q.

To encrypt the message

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

m = 6882326879666683

first break it into small blocks. Three-digit blocks work nicely in this case. The message is split into six
blocks, mi, in which

m1 = 688
m2 = 232
m3 = 687
m4 = 966
m5 = 668
m6 = 003

The first block is encrypted as

68879 mod 3337 = 1570 = c1

Performing the same operation on the subsequent blocks generates an encrypted message:

c = 1570 2756 2091 2276 2423 158

Decrypting the message requires performing the same exponentiation using the decryption key of
1019, so

15701019 mod 3337 = 688 = m1

The rest of the message can be recovered in this manner.

RSA in Hardware

Much has been written on the subject of hardware implementations of RSA [1314, 1474, 1456, 1316,
1485, 874, 1222, 87, 1410, 1409, 1343, 998, 367, 1429, 523, 772]. Good survey articles are [258, 872].
Many different chips perform RSA encryption [1310, 252, 1101, 1317, 874, 69, 737, 594, 1275, 1563,
509, 1223]. A partial list of currently available RSA chips, from [150, 258], is listed in Table 19.3. Not
all are available on the open market.

Speed of RSA

In hardware, RSA is about 1000 times slower than DES. The fastest VLSI hardware implementation
for RSA with a 512-bit modulus has a throughput of 64 kilobits per second [258]. There are also chips
that perform 1024-bit RSA encryption. Currently chips are being planned that will approach 1
megabit per second using a 512-bit modulus; they will probably be available in 1995. Manufacturers
have also implemented RSA in smart cards; these implementations are slower.

In software, DES is about 100 times faster than RSA. These numbers may change slightly as
technology changes, but RSA will never approach the speed of symmetric algorithms. Table 19.4 gives
sample software speeds of RSA [918].

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

Software Speedups

RSA encryption goes much faster if you™re smart about choosing a value of e. The three most common
choices are 3, 17, and 65537 (216 + 1). (The binary representation of 65537 has only two ones, so it
takes only 17 multiplications to exponentiate.) X.509 recommends 65537 [304], PEM recommends 3
[76], and PKCS #1 (see Section 24.14) recommends 3 or 65537 [1345]. There are no security problems
with using any of these three values for e (assuming you pad messages with random values”see later
section), even if a whole group of users uses the same value for e.

Table 19.3
Existing RSA Chips
Clock Cycles
Baud Rate Per 512 Bit Number of
Company Clock Speed Per 512 Bits Encryption Technology Bits per Chip Transistors
Alpha Techn. 25 MHz 13 K .98 M 2 micron 1024 180,000
AT&T 15 MHz 19 K .4 M 1.5 micron 298 100,000
Telecom 10 MHz 5.1 K 1M 2.5 micron 256 ””
Business Sim.
Ltd. 5 MHz 3.8 K .67 M Gate Array 32 ””
Calmos Syst.
Inc. 20 MHz 28 K .36 M 2 micron 593 95,000
CNET 25 MHz 5.3 K 2.3 M 1 micron 1024 100,000
Cryptech 14 MHz 17 K .4 M Gate Array 120 33,000
Cylink 30 MHz 6.8 K 1.2 M 1.5 micron 1024 150,000
GEC Marconi 25 MHz 10.2 K .67 M 1.4 micron 512 160,000
Pijnenburg 25 MHz 50 K .256 M 1 micron 1024 400,000
Sandia 8 MHz 10 K .4 M 2 micron 272 86,000
Siemens 5 MHz 8.5 K .3 M 1 micron 512 60,000

Table 19.4
RSA Speeds for Different Modulus Lengths
with an 8-bit Public Key (on a SPARC II)
512 bits 768 bits 1, 024 bits
Encrypt 0.03 sec 0.05 sec 0.08 sec
Decrypt 0.16 sec 0.48 sec 0.93 sec
Sign 0.16 sec 0.52 sec 0.97 sec
Verify 0.02 sec 0.07 sec 0.08 sec

Private key operations can be speeded up with the Chinese remainder theorem if you save the values
of p and q, and additional values such as d mod (p - 1), d mod (q - 1), and q-1 mod p [1283, 1276]. These
additional numbers can easily be calculated from the private and public keys.

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

Security of RSA

The security of RSA depends wholly on the problem of factoring large numbers. Technically, that™s a
lie. It is conjectured that the security of RSA depends on the problem of factoring large numbers. It
has never been mathematically proven that you need to factor n to calculate m from c and e. It is
conceivable that an entirely different way to cryptanalyze RSA might be discovered. However, if this
new way allows the cryptanalyst to deduce d, it could also be used as a new way to factor large
numbers. I wouldn™t worry about it too much.

It is also possible to attack RSA by guessing the value of (p - 1)(q - 1). This attack is no easier than
factoring n [1616].

For the ultraskeptical, some RSA variants have been proved to be as difficult as factoring (see Section
19.5). Also look at [36], which shows that recovering even certain bits of information from an RSA-
encrypted ciphertext is as hard as decrypting the entire message.

Factoring n is the most obvious means of attack. Any adversary will have the public key, e, and the
modulus, n. To find the decryption key, d, he has to factor n. Section 11.4 discusses the current state of
factoring technology. Currently, a 129-decimal-digit modulus is at the edge of factoring technology.
So, n must be larger than that. Read Section 7.2 on public key length.

It is certainly possible for a cryptanalyst to try every possible d until he stumbles on the correct one.
This brute-force attack is even less efficient than trying to factor n.

From time to time, people claim to have found easy ways to break RSA, but to date no such claim has
held up. For example, in 1993 a draft paper by William Payne proposed a method based on Fermat™s
little theorem [1234]. Unfortunately, this method is also slower than factoring the modulus.

There™s another worry. Most common algorithms for computing primes p and q are probabilistic;
what happens if p or q is composite? Well, first you can make the odds of that happening as small as
you want. And if it does happen, the odds are that encryption and decryption won™t work properly”
you™ll notice right away. There are a few numbers, called Carmichael numbers, which certain
probabilistic primality algorithms will fail to detect. These are exceedingly rare, but they are insecure
[746]. Honestly, I wouldn™t worry about it.

Chosen Ciphertext Attack against RSA

Some attacks work against the implementation of RSA. These are not attacks against the basic
algorithm, but against the protocol. It™s important to realize that it™s not enough to use RSA. Details

Scenario 1: Eve, listening in on Alice™s communications, manages to collect a ciphertext message, c,
encrypted with RSA in her public key. Eve wants to be able to read the message. Mathematically, she
wants m, in which

m = cd

To recover m, she first chooses a random number, r, such that r is less than n. She gets Alice™s public
key, e. Then she computes

x = re mod n

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

y = xc mod n
t = r-1 mod n

If x = re mod n, then r = xd mod n.

Now, Eve gets Alice to sign y with her private key, thereby decrypting y. (Alice has to sign the
message, not the hash of the message.) Remember, Alice has never seen y before. Alice sends Eve

u = yd mod n

Now, Eve computes

tu mod n = r-1yd mod n = r-1xdcd mod n = cd mod n = m

Eve now has m.

Scenario 2: Trent is a computer notary public. If Alice wants a document notarized, she sends it to
Trent. Trent signs it with an RSA digital signature and sends it back. (No one-way hash functions are
used here; Trent encrypts the entire message with his private key.)

Mallory wants Trent to sign a message he otherwise wouldn™t. Maybe it has a phony timestamp;
maybe it purports to be from another person. Whatever the reason, Trent would never sign it if he
had a choice. Let™s call this message m™.

First, Mallory chooses an arbitrary value x and computes y = xe mod n. He can easily get e; it™s
Trent™s public key and must be public to verify his signatures. Then he computes m = ym™ mod n, and
sends m to Trent to sign. Trent returns m™d mod n. Now Mallory calculates (md mod n)x-1 mod n,
which equals n™d mod n and is the signature of m™.

Actually, Mallory can use several methods to accomplish these same things [423, 458, 486]. The
weakness they all exploit is that exponentiation preserves the multiplicative structure of the input.
That is:

(xm)d mod n = xdmd mod n

Scenario 3: Eve wants Alice to sign m3 . She generates two messages, m1 and m2, such that

G 1m2 (mod n)

If Eve can get Alice to sign m1 and m2, she can calculate m3:

m3d = (m1d mod n)(m2d mod n )

Moral: Never use RSA to sign a random document presented to you by a stranger. Always use a one-
way hash function first. The ISO 9796 block format prevents this attack.

Common Modulus Attack on RSA

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

A possible RSA implementation gives everyone the same n, but different values for the exponents e
and d. Unfortunately, this doesn™t work. The most obvious problem is that if the same message is ever
encrypted with two different exponents (both having the same modulus), and those two exponents are
relatively prime (which they generally would be), then the plaintext can be recovered without either of
the decryption exponents [1457].

Let m be the plaintext message. The two encryption keys are e1 and e2. The common modulus is n.
The two ciphertext messages are:

c1 = me1 mod n
c2 = me2 mod n

The cryptanalyst knows n, e1, e2, c1, and c2. Here™s how he recovers m.

Since e1 and e2 are relatively prime, the extended Euclidean algorithm can find r and s, such that

re1 + se2 = 1

Assuming r is negative (either r or s has to be, so just call the negative one r), then the extended
Euclidean algorithm can be used again to calculate c1-1. Then

(c1-1)-r * C2s = m mod n

There are two other, more subtle, attacks against this type of system. One attack uses a probabilistic
method for factoring n. The other uses a deterministic algorithm for calculating someone™s secret key
without factoring the modulus. Both attacks are described in detail in [449].

Moral: Don™t share a common n among a group of users.

Low Encryption Exponent Attack against RSA

RSA encryption and signature verification are faster if you use a low value for e, but that can also be
insecure [704]. If you encrypt e(e + 1)/2 linearly dependent messages with different public keys having
the same value of e, there is an attack against the system. If there are fewer than that many messages,
or if the messages are unrelated, there is no problem. If the messages are identical, then e messages
are enough. The easiest solution is to pad messages with independent random values. This also
ensures that me mod n G e. Most real-world RSA implementations”PEM and PGP (see Sections
24.10 and 24.12), for example”do this.

Moral: Pad messages with random values before encrypting them; make sure m is about the same size
as n.

Low Decryption Exponent Attack against RSA

Another attack, this one by Michael Wiener, will recover d, when d is up to one quarter the size of n
and e is less than n [1596]. This rarely occurs if e and d are chosen at random, and cannot occur if e
has a small value.

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

Moral: Choose a large value for d.

Lessons Learned

Judith Moore lists several restrictions on the use of RSA, based on the success of these attacks [1114,

” Knowledge of one encryption/decryption pair of exponents for a given modulus enables
an attacker to factor the modulus.
” Knowledge of one encryption/decryption pair of exponents for a given modulus enables
an attacker to calculate other encryption/decryption pairs without having to factor n.
” A common modulus should not be used in a protocol using RSA in a communications
network. (This should be obvious from the previous two points.)
” Messages should be padded with random values to prevent attacks on low encryption
” The decryption exponent should be large.

Remember, it is not enough to have a secure cryptographic algorithm. The entire cryptosystem must
be secure, and the cryptographic protocol must be secure. A failure in any of those three areas makes
the overall system insecure.

Attack on Encrypting and Signing with RSA

It makes sense to sign a message before encrypting it (see Section 2.7), but not everyone follows this
practice. With RSA, there is an attack against protocols that encrypt before signing [48].

Alice wants to send a message to Bob. First she encrypts it with Bob™s public key; then she signs it
with her private key. Her encrypted and signed message looks like:

(meB mod nB)dA mod nA

Here™s how Bob can claim that Alice sent him m™ and not m. Realize that since Bob knows the
factorization of nB (it™s his modulus), he can calculate discrete logarithms with respect to nB.
Therefore, all he has to do is to find an x such that

m™x = m mod nB

Then, if he can publish xeB as his new public exponent and keep nB as his modulus, he can claim that
Alice sent him message m™ encrypted in this new exponent.

This is a particularly nasty attack in some circumstances. Note that hash functions don™t solve the
problem. However, forcing a fixed encryption exponent for every user does.


RSA is a de facto standard in much of the world. The ISO almost, but not quite, created an RSA
digital-signature standard; RSA is in an information annex to ISO 9796 [762]. The French banking
community standardized on RSA [525], as have the Australians [1498]. The United States currently
has no standard for public-key encryption, because of pressure from the NSA and patent issues.

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

Many U.S. companies use PKCS (see Section 24.14), written by RSA Data Security, Inc. A draft ANSI
banking standard specifies RSA [61].


The RSA algorithm is patented in the United States [1330], but not in any other country. PKP licenses
the patent, along with other public-key cryptography patents (see Section 25.5). The U.S. patent will
expire on September 20, 2000.

19.4 Pohlig-Hellman

The Pohlig-Hellman encryption scheme [1253] is similar to RSA. It is not a symmetric algorithm,
because different keys are used for encryption and decryption. It is not a public-key scheme, because
the keys are easily derivable from each other; both the encryption and decryption keys must be kept

Like RSA,

C = Pe mod n
P = Cd mod n


G (mod some complicated number)

Unlike RSA, n is not defined in terms of two large primes, it must remain part of the secret key. If
someone had e and n, they could calculate d. Without knowledge of e or d, an adversary would be
forced to calculate

e = logPC mod n

We have already seen that this is a hard problem.


The Pohlig-Hellman algorithm is patented in the United States [722] and also in Canada. PKP licenses
the patent, along with other public-key cryptography patents (see Section 25.5).

19.5 Rabin

Rabin™s scheme [1283,1601] gets its security from the difficulty of finding square roots modulo a
composite number. This problem is equivalent to factoring. Here is one implementation of this

First choose two primes, p and q, both congruent to 3 mod 4. These primes are the private key; the
product n = pq is the public key.

To encrypt a message, M (M must be less than n), simply compute

C = M2 mod n

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

Decrypting the message is just as easy, but slightly more annoying. Since the receiver knows p and q,
he can solve the two congruences using the Chinese remainder theorem. Compute

m1 = C(p + 1)/4 mod p
m2 = (p - C(p+ 1)/4) mod p
m3 = C(q + 1)/4 mod q
m4 = (q - C(q + 1)/4) mod q

Then choose an integer a = q(q-1 mod p) and a integer b = p(p-1 mod q). The four possible solutions

M1 = (am1 + bm3) mod n
M2 = (am1 + bm4) mod n
M3 = (am2 + bm3) mod n
M4 = (am2 + bm4) mod n

One of those four results, M1, M2, M3, or M4, equals M. If the message is English text, it should be
easy to choose the correct Mi. On the other hand, if the message is a random-bit stream (say, for key
generation or a digital signature), there is no way to determine which Mi is correct. One way to solve
this problem is to add a known header to the message before encrypting.


Hugh Williams redefined Rabin™s schemes to eliminate these shortcomings [1601]. In his scheme, p
and q are selected such that

G3 mod 8
G mod 8


N = pq

Also, there is a small integer, S, such that J(S,N) = -1. (J is the Jacobi symbol”see Section 11.3). N
and S are public. The secret key is k, such that

k = 1/2 * (1/4 * (p - 1) * (q - 1) + 1)

To encrypt a message M, compute c1 such that J(M,N) = (-1)c1. Then, compute M™ = (Sc1 * M) mod N.
Like Rabin™s scheme, C = M™2 mod N. And c2 = M™ mod 2. The final ciphertext message is the triple:

(C, c1, c2)

To decrypt C, the receiver computes M" using

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

Ck G·M" (mod N)

The proper sign of M" is given by c2. Finally,

M = (Sc1 * (-1)c1 * M") mod N

Williams refined this scheme further in [1603, 1604, 1605]. Instead of squaring the plaintext message,
cube it. The large primes must be congruent to 1 mod 3; otherwise the public and private keys are the
same. Even better, there is only one unique decryption for each encryption.

Both Rabin and Williams have an advantage over RSA in that they are provably as secure as
factoring. However, they are completely insecure against a chosen-ciphertext attack. If you are going
to use these schemes in instances where an attacker can mount this attack (for example, as a digital
signature algorithm where an attacker can choose messages to be signed), be sure to use a one-way
hash function before signing. Rabin suggested another way of defeating this attack: Append a
different random string to each message before hashing and signing. Unfortunately, once you add a
one-way hash function to the system it is no longer provably as secure as factoring [628], although
adding hashing cannot weaken the system in any practical sense.

Other Rabin variants are [972, 909, 696, 697, 1439, 989]. A two-dimensional variant is in [866, 889].

19.6 ElGamal

The ElGamal scheme [518,519] can be used for both digital signatures and encryption; it gets its
security from the difficulty of calculating discrete logarithms in a finite field.

To generate a key pair, first choose a prime, p, and two random numbers, g and x, such that both g
and x are less than p. Then calculate

y = gx mod p

The public key is y, g, and p. Both g and p can be shared among a group of users. The private key is x.

ElGamal Signatures

To sign a message, M, first choose a random number, k, such that k is relatively prime to p - 1. Then

a = gk mod p

and use the extended Euclidean algorithm to solve for b in the following equation:

M = (xa + kb) mod (p - 1)

The signature is the pair: a and b. The random value, k, must be kept secret.

To verify a signature, confirm that

yaab mod p = gM mod p

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

Each ElGamal signature or encryption requires a new value of k, and that value must be chosen
randomly. If Eve ever recovers a k that Alice used, she can recover Alice™s private key, x. If Eve ever
gets two messages signed or encrypted using the same k, even if she doesn™t know what it is, she can
recover x.

This is summarized in Table 19.5.

For example, choose p = 11 and g = 2. Choose private key x = 8. Calculate

y = gx mod p = 28 mod 11 = 3

The public key is y = 3, g = 2, and p = 11.

To authenticate M = 5, first choose a random number k = 9. Confirm that gcd(9, 10) = 1. Compute

a = gk mod p = 29 mod 11 = 6

and use the extended Euclidean algorithm to solve for b:

M = (ax + kb) mod (p - 1)
5 = (8 * 6 + 9 * b) mod 10

The solution is b = 3, and the signature is the pair: a = 6 and b = 3.

Table 19.5
ElGamal Signatures
Public Key:
p prime (can be shared among a group of users)
g <p (can be shared among a group of users)
y = gx mod p
Private Key:
x <p
k choose at random, relatively prime to p - 1
a (signature) = gk mod p
b (signature) such that M = (xa + kb) mod (p - 1)
Accept as valid if yaab mod p = gM mod p

To verify a signature, confirm that

yaab mod p = gM mod p
36 63 mod 11 = 25 mod 11

A variant of ElGamal for signatures is in [1377]. Thomas Beth invented a variant of the ElGamal

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

scheme suitable for proofs of identity [146]. There are variants for password authentication [312], and
for key exchange [773]. And there are thousands more (see Section 20.4).

ElGamal Encryption

A modification of ElGamal can encrypt messages. To encrypt message M, first choose a random k,
such that k is relatively prime to p - 1. Then compute

a = gk mod p
b = ykM mod p

The pair, a and b, is the ciphertext. Note that the ciphertext is twice the size of the plaintext.

To decrypt a and b, compute

M = b/ax mod p

Since ax G kx (mod p), and b/ax G kM/ax G xkM/gxk G (mod p), this all works (see Table 19.6).
Gg Gy Gg GM
This is really the same as Diffie-Hellman key exchange (see Section 22.1), except that y is part of the
key, and the encryption is multiplied by yk.


Table 19.7 gives sample software speeds of ElGamal [918].

Table 19.6
ElGamal Encryption
Public Key:
p prime (can be shared among a group of users)
g < p (can be shared among a group of users)
y = gx mod p
Private Key:
x <p
k choose at random, relatively prime to p - 1.
a (ciphertext) = gk mod p
b (ciphertext) = ykM mod p
M (plaintext) = b/ax mod p


ElGamal is unpatented. But, before you go ahead and implement the algorithm, realize that PKP feels
that this algorithm is covered under the Diffie-Hellman patent [718]. However, the Diffie-Hellman
patent will expire on April 29, 1997, making ElGamal the first public-key cryptography algorithm
suitable for encryption and digital signatures unencumbered by patents in the United States. I can

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

hardly wait.

19.7 McEliece

In 1978 Robert McEliece developed a public-key cryptosystem based on algebraic coding theory
[1041]. The algorithm makes use of the existence of a class of error-correcting codes, known as Goppa
codes. His idea was to construct a Goppa code and disguise it as a general linear code. There is a fast
algorithm for decoding Goppa codes, but the general problem of finding a code word of a given
weight in a linear binary code is NP-complete. A good description of this algorithm can be found in
[1233]; see also [1562]. Following is just a quick summary.

Let dH(x,y) denote the Hamming distance between x and y. The numbers n, k, and t are system

The private key has three parts: G™ is a k * n generator matrix for a Goppa code that can correct t
errors. P is an n * n permutation matrix. S is a k * k nonsingular matrix.

The public key is a k * n matrix G: G = SG™P.

Plaintext messages are strings of k bits, in the form of k-element vectors over GF(2).

To encrypt a message, choose a random n-element vector over GF(2), z, with Hamming distance less
than or equal to t.

c = mG + z

To decrypt the ciphertext, first compute c™ = cP-1. Then, using the decoding algorithm for the Goppa
code, find m™ such that dH(m™ G, c™) is less than or equal to t. Finally, compute m = m™S-1.

In his original paper, McEliece suggested that n = 1024, t = 50, and k = 524. These are the minimum
values required for security.

Table 19.7
ElGamal Speeds for Different
Modulus Lengths with a 160-bit
Exponent (on a SPARC II)
512 bits 768 bits 1024 bits
Encrypt 0.33 sec 0.80 sec 1.09 sec
Decrypt 0.24 sec 0.58 sec 0.77 sec
Sign 0.25 sec 0.47 sec 0.63 sec
Verify 1.37 sec 5.12 sec 9.30 sec

Although the algorithm was one of the first public-key algorithms, and there were no successful
cryptanalytic results against the algorithm, it has never gained wide acceptance in the cryptographic
community. The scheme is two to three orders of magnitude faster than RSA, but has some problems.
The public key is enormous: 219 bits long. The data expansion is large: The ciphertext is twice as long
as the plaintext.

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

Some attempts at cryptanalysis of this system can be found in [8, 943, 1559, 306]. None of these were
successful in the general case, although the similarity between the McEliece algorithm and knapsacks
worried some.

In 1991, two Russian cryptographers claimed to have broken the McEliece system with some
parameters [882]. Their paper contained no evidence to substantiate their claim, and most
cryptographers discount the result. Another Russian attack, one that cannot be used directly against
the McEliece system, is in [1447, 1448]. Extensions to McEliece can be found in [424, 1227, 976].

Other Algorithms Based on Linear Error-Correcting Codes

The Niederreiter algorithm [1167] is closely related to the McEliece algorithm, and assumes that the
public key is a random parity-check matrix of an error-correcting code. The private key is an efficient
decoding algorithm for this matrix.

Another algorithm, used for identification and digital signatures, is based on syndrome decoding
[1501]; see [306] for comments. An algorithm based on error-correcting codes [1621] is insecure [698,
33, 31, 1560, 32].

19.8 Elliptic Curve Cryptosystems

Elliptic curves have been studied for many years and there is an enormous amount of literature on the
subject. In 1985, Neal Koblitz and V. S. Miller independently proposed using them for public-key
cryptosystems [867, 1095]. They did not invent a new cryptographic algorithm with elliptic curves
over finite fields, but they implemented existing public-key algorithms, like Diffie-Hellman, using
elliptic curves.

Elliptic curves are interesting because they provide a way of constructing “elements” and “rules of
combining” that produce groups. These groups have enough familiar properties to build
cryptographic algorithms, but they don™t have certain properties that may facilitate cryptanalysis.
For example, there is no good notion of “smooth” with elliptic curves. That is, there is no set of small
elements in terms of which a random element has a good chance of being expressed by a simple
algorithm. Hence, index calculus discrete logarithm algorithms do not work. See [1095] for more

Elliptic curves over the finite field GF(2n ) are particularly interesting. The arithmetic processors for
the underlying field are easy to construct and are relatively simple to implement for n in the range of
130 to 200. They have the potential to provide faster public-key cryptosystems with smaller key sizes.
Many public-key algorithms, like Diffie-Hellman, ElGamal, and Schnorr, can be implemented in
elliptic curves over finite fields.

The mathematics here are complex and beyond the scope of this book. Those interested in this topic
are invited to read the two references previously mentioned, and the excellent book by Alfred
Menezes [1059]. Two analogues of RSA work in elliptic curves [890, 454]. Other papers are [23, 119,
1062, 869, 152, 871, 892, 25, 895, 353, 1061, 26, 913, 914, 915]. Elliptic curve cryptosystems with small
key lengths are discussed in [701]. Next Computer Inc.™s Fast Elliptic Encryption (FEE) algorithm
also uses elliptic curves [388]. FEE has the nice feature that the private key can be any easy-to-
remember string. There are proposed public-key cryptosystems using hyperelliptic curves [868, 870,
1441, 1214].

19.9 LUC

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

Some cryptographers have developed generalizations of RSA that use various permutation
polynomials instead of exponentiation. A variation called Kravitz-Reed, using irreducible binary
polynomials [898], is insecure [451, 589]. Winfried MŸller and Wilfried Nöbauer use Dickson
polynomials [1127, 1128, 965]. Rudolph Lidl and MŸller generalized this approach in [966, 1126] (a
variant is called the R©idi scheme), and Nöbauer looked at its security in [1172, 1173]. (Comments on
prime generation with Lucas functions are in [969, 967, 968, 598].) Despite all of this prior art, a
group of researchers from New Zealand managed to patent this scheme in 1993, calling it LUC [1486,

The nth Lucas number, Vn(P,1), is defined as

Vn(P, 1) = PVn-1 (P, 1) - Vn- 2 (P,1)

There™s a lot more theory to Lucas numbers; I™m ignoring all of it. A good theoretical treatment of
Lucas sequences is in [1307, 1308]. A particularly nice description of the mathematics of LUC is in
[1494, 708].

In any case, to generate a public-key/private-key key pair, first choose two large primes, p and q.
Calculate n, the product of p and q. The encryption key, e, is a random number that is relatively
prime to p - 1, q - 1, p + 1, and q + 1.

There are four possible decryption keys,

d = e-1 mod (lcm((p + 1), (q + 1)))
d = e-1 mod (lcm((p + 1), (q - 1)))
d = e-1 mod (lcm((p - 1), (q + 1)))
d = e-1 mod (lcm((p - 1), (q - 1)))

where lcm is the least common multiple.

The public key is d and n; the private key is e and n. Discard p and q.

To encrypt a message, P (P must be less than n), calculate

C = Ve(P, 1) (mod n )

And to decrypt:

P = Vd P, 1) (mod n), with the proper d

At best, LUC is no more secure than RSA. And recent, still-unpublished results show how to break
LUC in at least some implementations. I just don™t trust it.

19.10 Finite Automaton Public-Key Cryptosystems

Chinese cryptographer Tao Renji has developed a public-key algorithm based on finite automata
[1301, 1302, 1303, 1300, 1304, 666]. Just as it is hard to factor the product of two large primes, it is
also hard to factor the composition of two finite automata. This is especially so if one or both of them
is nonlinear.

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

Much of this research took place in China in the 1980s and was published in Chinese. Renji is starting
to write in English. His main result was that certain nonlinear automata (the quasilinear automata)
possess weak inverses if, and only if, they have a certain echelon matrix structure. This property
disappears if they are composed with another automaton (even a linear one). In the public-key
algorithm, the secret key is an invertible quasilinear automaton and a linear automaton, and the
corresponding public key can be derived by multiplying them out term by term. Data is encrypted by
passing it through the public automaton, and decrypted by passing it through the inverses of its
components (in some cases provided they have been set to a suitable initial state). This scheme works
for both encryption and digital signatures.

The performance of such systems can be summed up by saying that like McEliece™s system, they run
much faster than RSA, but require longer keys. The keylength thought to give similar security to 512-
bit RSA is 2792 bits, and to 1024-bit RSA is 4152 bits. For the former case, the system encrypts data at
20, 869 bytes/sec and decrypts data at 17, 117 bytes/sec, running on a 33 Mhz 80486.

Renji has published three algorithms. The first is FAPKC0. This is a weak system which uses linear
components, and is primarily illustrative. Two serious systems, FAPKC1 and FAPKC2, use one linear
and one nonlinear component each. The latter is more complex, and was developed in order to
support identity-based operation.

As for their strength, quite a lot of work has been done on them in China (where there are now over
30 institutes publishing cryptography and security papers). One can see from the considerable
Chinese language literature that the problem has been studied.

One possible attraction of FAPKC1 and FAPKC2 is that they are not encumbered by any U.S.
patents. Thus, once the Diffie-Hellman patent expires in 1997, they will unquestionably be in the
public domain.

Chapter 20
Public-Key Digital Signature Algorithms
20.1 Digital Signature Algorithm (DSA)

In August 1991, The National Institute of Standards and Technology (NIST) proposed the Digital
Signature Algorithm (DSA) for use in their Digital Signature Standard (DSS). According to the
Federal Register [538]:

A Federal Information Processing Standard (FIPS) for Digital Signature Standard (DSS)
is being proposed. This proposed standard specifies a public-key digital signature
algorithm (DSA) appropriate for Federal digital signature applications. The proposed
DSS uses a public key to verify to a recipient the integrity of data and identity of the
sender of the data. The DSS can also be used by a third party to ascertain the authenticity
of a signature and the data associated with it.

This proposed standard adopts a public-key signature scheme that uses a pair of
transformations to generate and verify a digital value called a signature.


This proposed FIPS is the result of evaluating a number of alternative digital signature

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

techniques. In making the selection NIST has followed the mandate contained in section 2
of the Computer Security Act of 1987 that NIST develop standards to “...assure the cost-
effective security and privacy of Federal information and, among technologies offering
comparable protection, on selecting the option with the most desirable operating and use

Among the factors that were considered during this process were the level of security
provided, the ease of implementation in both hardware and software, the ease of export
from the U.S., the applicability of patents, impact on national security and law
enforcement and the level of efficiency in both the signing and verification functions. A
number of techniques were deemed to provide appropriate protection for Federal systems.
The technique selected has the following desirable characteristics:

NIST expects it to be available on a royalty-free basis. Broader use of this technique
resulting from public availability should be an economic benefit to the government and
the public.

The technique selected provides for efficient implementation of the signature operations in
smart card applications. In these applications the signing operations are performed in the
computationally modest environment of the smart card while the verification process is
implemented in a more computationally rich environment such as a personal computer, a
hardware cryptographic module, or a mainframe computer.

Before it gets too confusing, let me review the nomenclature: DSA is the algorithm; the DSS is the
standard. The standard employs the algorithm. The algorithm is part of the standard.

Reaction to the Announcement

NIST™s announcement created a maelstrom of criticisms and accusations. Unfortunately, it was more
political than academic. RSA Data Security, Inc., purveyors of the RSA algorithm, led the criticism
against DSS. They wanted RSA, and not another algorithm, used as the standard. RSADSI makes a
lot of money licensing the RSA algorithm, and a royalty-free digital signature standard would directly
affect their bottom line. (Note: DSA is not necessarily free of patent infringements; I™ll discuss that

Before the algorithm was announced, RSADSI campaigned against a “common modulus,” which
might have given the government the ability to forge signatures. When the algorithm was announced
without this common modulus, they attacked it on other grounds [154], both in letters to NIST and
statements to the press. (Four letters to NIST appeared in [1326]. When reading them, keep in mind
that at least two of the authors, Rivest and Hellman, had a financial interest in DSS™s not being

Many large software companies that already licensed the RSA algorithm came out against the DSS. In
1982, the government had solicited public-key algorithms for a standard [537]. After that, there
wasn™t a peep out of NIST for nine years. Companies such as IBM, Apple, Novell, Lotus, Northern
Telecom, Microsoft, DEC, and Sun had already spent large amounts of money implementing the RSA
algorithm. They were not interested in losing their investment.

In all, NIST received 109 comments by the end of the first comment period on February 28, 1992.

Let™s look at the criticisms against DSA, one by one.

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

1. DSA cannot be used for encryption or key distribution.
True, but not the point of the standard. This is a signature standard. NIST should have a
standard for public-key encryption. NIST is committing a grave injustice to the American
people by not implementing a public-key encryption standard. It is suspicious that this proposed
digital signature standard cannot be used for encryption. (As it turns out, though, it can”see
Section 23.3.) That does not mean that a signature standard is useless.
2. DSA was developed by the NSA, and there may be a trapdoor in the algorithm.
Much of the initial comments were just paranoia: “NIST™s denial of information with no
apparent justification does not inspire confidence in DSS, but intensifies concern that there is a
hidden agenda, such as laying the groundwork for a national public-key cryptosystem that is in
fact vulnerable to being broken by NIST and/or NSA” [154]. One serious question about the
security of DSA was raised by Arjen Lenstra and Stuart Haber at Bellcore. This will be
discussed later.
3. DSA is slower than RSA [800].
True, more or less. Signature generation speeds are the same, but signature verification can be
10 to 40 times slower with DSA. Key generation, however, is faster. But key generation is
irrelevant; a user rarely does it. On the other hand, signature verification is the most common
The problem with this criticism is that there are many ways to play with the test parameters,
depending on the results you want. Precomputations can speed up DSA signature generation,
but don™t always apply. Proponents of RSA use numbers optimized to make their calculations
easier; proponents of DSA use their own optimizations. In any case, computers are getting faster
all the time. While there is a speed difference, it will not be noticeable in most applications.
4. RSA is a de facto standard.
Here are two examples of this complaint. From Robert Follett, the program director of
standards at IBM [570]:

IBM is concerned that NIST has proposed a standard with a different digital
signature scheme rather than adopting the international standard. We have been
convinced by users and user organizations that the international standards using
RSA will be a prerequisite to the sales of security products in the very near future.

From Les Shroyer, vice president and director, corporate MIS and telecommunications, at
Motorola [1444]:

We must have a single, robust, politically-accepted digital signature standard that is
usable throughout the world, between both U.S. and non-U.S., and Motorola and
non-Motorola entities. The lack of other viable digital signature technology for the
last eight years has made RSA a de facto standard.... Motorola and many other
companies... have committed millions of dollars to RSA. We have concern over the
interoperability and support of two different standards, as that situation will lead to
added costs, delays in deployment, and complication....

Many companies wanted NIST to adopt the ISO 9796, the international digital signature
standard that uses RSA [762]. While this is a valid complaint, it is not a sufficient justification to
make it a standard. A royalty-free standard would better serve the U.S. public interest.
5. The DSA selection process was not public; sufficient time for analysis has not been

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

First NIST claimed that they designed the DSA; then they admitted that NSA helped them.
Finally, they confirmed that NSA designed the algorithm. This worries many people; the NSA
doesn™t inspire trust. Even so, the algorithm is public and available for analysis; and NIST
extended the time for analysis and comment.
6. DSA may infringe on other patents.
It may. This will be discussed in the section on patent issues.
7. The key size is too small.
This was the only valid criticism of DSS. The original implementation set the modulus at 512
bits [1149]. Since the algorithm gets its security from the difficulty of computing discrete logs in
that modulus, this worried most cryptographers. There have since been advances in the
problem of calculating discrete logarithms in a finite field, and 512 bits is too short for long-
term security (see Section 7.2). According to Brian LaMacchia and Andrew Odlyzko, “...even
512-bit primes appear to offer only marginal security...” [934]. In response to this criticism,
NIST made the key size variable, from 512 bits to 1024 bits. Not great, but better.

On May 19, 1994, the standard was finally issued [1154]. The issuing statement said [542]:

This standard is applicable to all Federal departments and agencies for the protection of
unclassified information.... This standard shall be used in designing and implementing
public-key based signature schemes which Federal departments and agencies operate or
which are operated for them under contract. Adoption and use of this standard is
available to private and commercial organizations.

Before you run out and implement this standard in your next product, read the section on patent
issues below.

Description of DSA

DSA is a variant of the Schnorr and ElGamal signature algorithms, and is fully described in [1154].
The algorithm uses the following parameters:

p = a prime number L bits long, when L ranges from 512 to 1024 and is a multiple of 64.
(In the original standard, the size of p was fixed at 512 bits [1149]. This was the source of
much criticism and was changed by NIST [1154].)

q = a 160-bit prime factor of p “ 1.

g = h(p-1)/q mod p, where h is any number less than p “ 1 such that h(p - 1)/q mod p is
greater than 1.

x = a number less than q.

y = gx mod p.

The algorithm also makes use of a one-way hash function: H(m). The standard specifies the Secure
Hash Algorithm, discussed in Section 18.7.

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

To sign a message, m:

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

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

The parameters r and s are her signature; she sends these to Bob.
(3) Bob verifies the signature by computing
w = s-1 mod q
u1 = (H(m) * w) mod q
u2 = (rw) mod q
v = ((gu1 * yu2) mod p) mod q

If v = r, then the signature is verified.

Proofs for the mathematical relationships are found in [1154]. Table 20.1 provides a summary.

Speed Precomputations

Table 20.2 gives sample software speeds of DSA [918].

Real-world implementations of DSA can often be speeded up through precomputations. Notice that
the value r does not depend on the message. You can create a string of random k values, and then
precompute r values for each of them. You can also precompute k-1 for each of those k values. Then,
when a message comes along, you can compute s for a given r and k-1.

This precomputation speeds up DSA considerably. Table 20.3 is a comparison of DSA and RSA
computation times for a particular smart card implementation [1479].

Table 20.1
DSA Signatures
Public Key:
p 512-bit to 1024-bit prime (can be shared among a group of users)
q 160-bit prime factor of p “ 1 (can be shared among a group of users)
g = h(p - 1)/q mod p, where h is less than p “ 1 and h(p - 1)/q mod p > 1 (can be shared among a group of
y = gx mod p (a p-bit number)
Private Key:
x < q (a 160-bit number)
k choose at random, less than q
r (signature) = (gk mod p) mod q
s (signature) = (k-1 (H(m) + xr)) mod q
w = s-1 mod q

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

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

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

DSA Prime Generation

Lenstra and Haber pointed out that certain moduli are much easier to crack than others [950]. If
someone forced a network to use one of these “cooked” moduli, then their signatures would be easier
to forge. This isn™t a problem for two reasons: These moduli are easy to detect and they are so rare
that the chances of using one when choosing a modulus randomly are almost negligible”smaller, in
fact, than the chances of accidentally generating a composite number using a probabilistic prime
generation routine.

In [1154] NIST recommended a specific method for generating the two primes, p and q, where q
divides p “ 1. The prime p is L bits long, between 512 and 1024 bits long, in some multiple of 64 bits.
The prime q is 160 bits long. Let L “ 1 = 160n + b, where L is the length of p, and n and b are two
numbers and b is less than 160.

Table 20.2
DSA Speeds for Different Modulus Lengths with a 160-bit
Exponent (on a SPARC II)
512 bits 768 bits 1024 bits
Sign 0.20 sec 0.43 sec 0.57 sec
Verify 0.35 sec 0.80 sec 1.27 sec

Table 20.3
Comparison of RSA and DSA Computation Times
DSA with
DSA RSA Common p, q, g
Global Computations Off-card (P) N/A Off-card (P)
Key Generation 14 sec Off-card (S) 4 sec
Precomputation 14 sec N/A 4 sec
Signature .03 sec 15 sec .03 sec
Verification 16 sec 1.5 sec 10 sec
1“5 sec off-card (P) 1“3 sec off-card (P)
Off-card computations were performed on an 80386 33 mHz, personal computer. (P) indicates public parameters off-card
and (S) indicates secret parameters off-card. Both algorithms use a 512-bit modulus.

(1) Choose an arbitrary sequence of at least 160 bits and call it S. Let g be the length of S
in bits.
(2) Compute U = SHA(S) SHA ((S + 1) mod 2g), where SHA is the Secure Hash
Algorithm (see Section 18.7).

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

(3) Form q by setting the most significant bit and the least significant bit of U to 1.
(4) Check whether q is prime.
(5) If q is not prime, go back to step (1).
(6) Let C = 0 and N = 2.
For k = 0, 1,..., n, let Vk = SHA ((S + N + k) mod 2g)
(8) Let W be the integer
W = V0 + 2160V1 +...+ 2160(n - 1)Vn - 1 + 2160n(Vn mod 2b)

and let
X = W + 2L - 1

Note that X is an L-bit number.
(9) Let p = X “ ((X mod 2q) “ 1). Note that p is congruent to 1 mod 2q.
If p < 2L - 1, then go to step (13).
(11) Check whether p is prime.
(12) If p is prime, go to step (15).
(13) Let C = C + 1 and N = N + n + 1.
(14) If C = 4096, then go to step (1). Otherwise, go to step (7).
(15) Save the value of S and the value of C used to generate p and q.

In [1154], the variable S is called the “seed,” C is called the “counter,” and N the “offset.”

The point of this exercise is that there is a public means of generating p and q. For all practical
purposes, this method prevents cooked values of p and q. If someone hands you a p and a q, you might
wonder where that person got them. However, if someone hands you a value for S and C that
generated the random p and q, you can go through this routine yourself. Using a one-way hash
function, SHA in the standard, prevents someone from working backwards from a p and q to generate
an S and C.

This security is better than what you get with RSA. In RSA, the prime numbers are kept secret.
Someone could generate a fake prime or one of a special form that makes factoring easier. Unless you
know the private key, you won™t know that. Here, even if you don™t know a person™s private key, you
can confirm that p and q have been generated randomly.

ElGamal Encryption with DSA

There have been allegations that the government likes the DSA because it is only a digital signature
algorithm and can™t be used for encryption. It is, however, possible to use the DSA function call to do
ElGamal encryption.

Assume that the DSA algorithm is implemented with a single function call:

DSAsign (p,q,g,k,x,h,r,s)

You supply the numbers p, q, g, k, x, and h, and the function returns the signature parameters: r and

To do ElGamal encryption of message m with public key y, choose a random number, k, and call

DSAsign (p,p,g,k,0,0,r,s)

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

The value of r returned is a in the ElGamal scheme. Throw s away. Then, call

DSAsign (p,p,y,k,0,0,r,s)

Rename the value of r to be u; throw s away. Call

DSAsign (p,p,m,1,u,0,r,s)

Throw r away. The value of s returned is b in the ElGamal scheme. You now have the ciphertext, a
and b.

Decryption is just as easy. Using secret key x, and ciphertext messages a and b, call

DSAsign (p,p,a,x,0,0,r,s)

The value r is ax mod p. Call that e. Then call

DSAsign (p,p,1,e,b,0,r,s)

The value s is the plaintext message, m.

This method will not work with all implementations of DSA. Some may fix the values of p and q, or
the lengths of some of the other parameters. Still, if the implementation is general enough, this is a
way to encrypt using nothing more than digital signature function.

RSA Encryption with DSA

RSA encryption is even easier. With a modulus n, message m, and public key e, call

DSAsign (n,n,m,e,0,0,r,s)

The value of r returned is the ciphertext.

RSA decryption is the same thing. If d is the private key, then

DSAsign (n,n,m,d,0,0,r,s)

returns the plaintext as the value of r.

Security of DSA

At 512-bits, DSA wasn™t strong enough for long-term security. At 1024 bits, it is.

The NSA, in its first public interview on the subject, commented to Joe Abernathy of The Houston
Chronicle on allegations about a trapdoor in DSS [363]:

Regarding the alleged trapdoor in the DSS. We find the term trapdoor somewhat
misleading since it implies that the messages sent by the DSS are encrypted and with
access via a trapdoor one could somehow decrypt (read) the message without the sender™s

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

The DSS does not encrypt any data. The real issue is whether the DSS is susceptible to
someone forging a signature and therefore discrediting the entire system. We state
categorically that the chances of anyone”including NSA”forging a signature with the
DSS when it is properly used and implemented is infinitesimally small.

Furthermore, the alleged trapdoor vulnerability is true for any public key-based
authentication system, including RSA. To imply somehow that this only affects the DSS (a
popular argument in the press) is totally misleading. The issue is one of implementation
and how one goes about selecting prime numbers. We call your attention to a recent
EUROCRYPT conference which had a panel discussion on the issue of trapdoors in the
DSS. Included on the panel was one of the Bellcore researchers who initially raised the
trapdoor allegation, and our understanding is that the panel”including the person from
Bellcore”concluded that the alleged trapdoor was not an issue for the DSS. Furthermore,
the general consensus appeared to be that the trapdoor issue was trivial and had been
overblown in the press. However, to try to respond to the trapdoor allegation, at NIST™s
request, we have designed a prime generation process which will ensure that one can
avoid selection of the relatively few weak primes which could lead to weakness in using
the DSS. Additionally, NIST intends to allow for larger modulus sizes up to 1024 which
effectively negates the need to even use the prime generation process to avoid weak
primes. An additional very important point that is often overlooked is that with the DSS
the primes are public and therefore can be subject to public examination. Not all public
key systems provide for this same type of examination.

The integrity of any information security system requires attention to proper
implementation. With the myriad of vulnerabilities possible given the differences among
users, NSA has traditionally insisted on centralized trusted centers as a way to minimize
risk to the system. While we have designed technical modifications to the DSS to meet
NIST™s requests for a more decentralized approach, we still would emphasize that portion
of the Federal Register notice for the DSS which states:

“While it is the intent of this standard to specify general security requirements
for generating digital signatures, conformance to this standard does not assure
that a particular implementation is secure. The responsible authority in each
agency or department shall assure that an overall implementation provides an
acceptable level of security. NIST will be working with government users to
ensure appropriate implementations.”

Finally, we have read all the arguments purporting insecurities with the DSS, and we
remain unconvinced of their validity. The DSS has been subjected to intense evaluation
within NSA which led to its being endorsed by our Director of Information Systems
Security for use in signing unclassified data processed in certain intelligence systems and
even for signing classified data in selected systems. We believe that this approval speaks to


. 17
( 29)