Another public key algorithm was devised in 1984 by El Gamal [ELG85, ELG86]. While this algorithm is not widely used directly, it is of considerable importance in the U.S.

**The El
Gamal and Digital Signature Algorithms**

Another public key algorithm was devised in
1984 by El Gamal [__ELG85__, __ELG86__]. While this algorithm is not widely used
directly, it is of considerable importance in the U.S. Digital Signature
Standard (DSS) [__NIS92b__, __NIS94__] of the National Institute of Standards and
Technology (NIST). This algorithm relies on the difficulty of computing
discrete logarithms over finite fields. Because it is based on arithmetic in
finite fields, as is RSA, it bears some similarity to RSA.

We investigated digital signatures in __Chapter 2__. Recall that a digital signature is,
like a handwritten signature, a means of associating a mark unique to an
individual with a body of text. The mark should be unforgeable, meaning that
only the originator should be able to compute the signature value. But the mark
should be verifiable, meaning that others should be able to check that the
signature comes from the claimed originator. The general way of computing
digital signatures is with public key encryption; the signer computes a
signature value by using a private key, and others can use the public key to
verify that the signature came from the corresponding private key.

**El Gamal
Algorithm**

In the El Gamal algorithm, to generate a key
pair, first choose a prime p and two integers, a and x, such that a < p and
x < p and calculate y

= a^{x} mod p. The prime p should be
chosen so that (p - 1) has a large prime factor, q. The private key is x and
the public key is y, along with parameters p and a.

To sign a message m, choose a random integer k,
0 < k < p - 1, which has not been used before and which is relatively
prime to (p - 1), and compute

r = a^{k} mod p

and

s = ^{k-1} (m - xr) mod (p - 1)

where k^{-1} is the multiplicative
inverse of k mod (p - 1), so that k * k^{-1} = 1 mod (p - 1). The message
signature is then r and s. A recipient can use the public key y to compute y^{r}
r^{s} mod p and determine that it is equivalent to a^{m} mod p.
To defeat this encryption and infer the values of x and k given r, s, and m,
the intruder could find a means of computing a discrete logarithm to solve y =
a^{x} and r = a^{k}.

**Digital
Signature Algorithm**

The U.S. Digital Signature Algorithm (DSA)
(also called the Digital Signature Standard or DSS) __[NIS94]__
is the El Gamal algorithm with a few restrictions. First, the size of p is
specifically fixed at 2^{511} < p < 2^{512} (so that p is
roughly 170 decimal digits long). Second, q, the

large prime factor of (p - 1) is chosen so that
2^{159} < q < 2^{160} . The algorithm explicitly uses
H(m), a hash value, instead of the full message text m. Finally, the
computations of r and s are taken mod q. Largely, one can argue that these
changes make the algorithm easy to use for those who do not want or need to
understand the underlying mathematics. However, they also weaken the potential
strength of the encryption by reducing the uncertainty for the attacker.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Security in Computing : Cryptography Explained : The El Gamal and Digital Signature Algorithms |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.