ńňđ. 17 |

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

Since

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))

Encrypting:

c = me mod n

Decrypting:

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

British

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

matter.

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

Gm

G 1m2 (mod n)

m3

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

Gm

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,

1115]:

â€” 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

exponents.

â€” 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.

Standards

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

Patents

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

secret.

Like RSA,

C = Pe mod n

P = Cd mod n

where

G1

G (mod some complicated number)

ed

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.

Patents

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

scheme.

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

are:

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.

Williams

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

p

G7

G mod 8

q

and

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)

GÂ·

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

compute

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

Signing:

k choose at random, relatively prime to p - 1

a (signature) = gk mod p

b (signature) such that M = (xa + kb) mod (p - 1)

Verifying:

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.

Speed

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

Encrypting:

k choose at random, relatively prime to p - 1.

a (ciphertext) = gk mod p

b (ciphertext) = ykM mod p

Decrypting:

M (plaintext) = b/ax mod p

Patents

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

parameters.

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

details.

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,

521,1487].

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.

And:

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

characteristics.â€ť

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

later.)

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

approved.)

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

operation.

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

provided.

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

users)

y = gx mod p (a p-bit number)

Private Key:

x < q (a 160-bit number)

Signing:

k choose at random, less than q

r (signature) = (gk mod p) mod q

s (signature) = (k-1 (H(m) + xr)) mod q

Verifying:

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)

(7)

(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).

(10)

(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

s.

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

knowledge.

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 |