Previous | Table of Contents | Next |
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 | = g^{x} mod p |
Private Key: | |
x | <p |
Signing: | |
k | choose at random, relatively prime to p - 1 |
a | (signature) = g^{k} mod p |
b | (signature) such that M = (xa + kb) mod (p - 1) |
Verifying: | |
Accept as valid if y^{a}a^{b} mod p = g^{M} mod p | |
To verify a signature, confirm that
A variant of ElGamal for signatures is in [1377]. Thomas Beth invented a variant of the ElGamal 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
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
Since a^{x} ≡ g^{kx} (mod p), and b/a^{x} ≡ y^{k}M/a^{x} ≡ g^{xk}M/g^{xk} ≡ M (mod p), this all works (see Table 19.6). 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 y^{k}.
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 | = g^{x} mod p |
Private Key: | |
x | < p |
Encrypting: | |
k | choose at random, relatively prime to p - 1. |
a | (ciphertext) = g^{k} mod p |
b | (ciphertext) = y^{k}M mod p |
Decrypting: | |
M (plaintext) = b/a^{x} 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 hardly wait.
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 d_{H}(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.
To decrypt the ciphertext, first compute c’ = cP^{-1}. Then, using the decoding algorithm for the Goppa code, find m’ such that d_{H}(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 |
Previous | Table of Contents | Next |