Asymmetric Cryptography in Perl
by Vipul Ved Prakash, Benjamin Trott
|
Pages: 1, 2, 3
Digital Signature Algorithm
|
|
DSA is the Digital Signature Algorithm, an algorithm developed by the U.S. government for use as the Digital Signature Standard. At the time of its creation, RSA was threatening to become a de facto standard: Microsoft and Lotus, for example, were already including it in their products. RSA provided both signatures and encryption, and this frightened the government: A future where regular citizens might secure their personal communications, preventing government agents from snooping on networks and phone lines, was terrifying to the NSA (National Security Agency). With this in mind, the government pushed for the standardization of the DSA, an algorithm that provided only digital signatures, and could not encrypt messages.
The government wanted cryptography back in the hands of the NSA rather
than in a private company, RSA Data Security, Inc. For this reason they
pushed DSA as a royalty-free standard, as an alternative to the
license-restricted RSA; DSA was not subject to RSA licensing restrictions
because it is based not on the RSA algorithm but on the digital signature
algorithm published by Tehar Elgamal. DSA is by many opinions an inferior
standard to RSA: It is difficult to implement, more complicated
mathematically and slower than RSA for signature verification (though
faster for signing). More importantly, DSA keys are restricted to a maximum
bitsize of 1024. Despite these concerns -- or, perhaps, because of
them -- DSA was chosen as the government standard.
Here's how DSA works:
To begin generating a new DSA key pair, Alice generates a large prime
q (generated either from a user-supplied seed or from a string of
random octets), where
2^159 < q < 2^160
The same seed is then used to construct a prime p such that q
divides p-1 and
2^(bits-1) < p < 2^(bits)
where bits is the number of bits in the key; the bitsize can range from
512 to 1024.
A number g is then chosen such that
g = h^((p-1)/q) mod p
where h is any integer greater than 1, less than p-1. A typical value
for h is 2.
Finally, two numbers x and y are generated that represent the
private and public portions of the key, respectively. x is a randomly
generated integer such that x is greater than 0 and less than q;
y is derived as follows:
y = g^x mod p
A DSA public key consists of the values of p, q, g and y; a
private key consists of those values, and the value of x. A DSA
signature consists of two values, r and s, generated by applying the
private DSA key to a SHA-1 hash of a message. To verify a message, the
verifier uses the original message and the sender's public key to
mathematically backtrack from the value of s to arrive at a final value
v; if v is equal to r, then the signature is valid. Otherwise, it
is invalid.
Perl and Crypt::DSA, a pure Perl implementation of DSA, make digital signatures with DSA very simple. Alice generates a new DSA key:
use Crypt::DSA;
my $dsa = Crypt::DSA->new;
my $key = $dsa->keygen( Size => 512 );
After sending the public portion of this key to Bob, she signs her message (a string stored in $message) with her private key:
my $sig = $dsa->sign( Message => $message, Key => $key );
She then sends the signature $sig and the message $message to Bob, who uses Alice's public key to verify the signature:
my $valid = $dsa->verify( Signature => $sig, Message => $message,
Key => $alice_pub_key );
If $valid is true, then the signature $sig is valid.
Meanwhile, if Eve has sniffed the network traffic to intercept the message and signature in transit to Bob, then she can modify the message $message; but in order to regenerate the signature $sig, Eve must have access to Alice's private key. Since Eve is not in possession of that key, the signature will not match the message and signature verification will fail.
Schnorr
Like DH and DSA, Schnorr is another signature algorithm based on the difficulty of the discrete logarithm problem. Schnorr was specifically designed in 1991 by Claus-Peter Schnorr for use in smart cards. Schnorr is both a signature scheme and an interactive identification scheme that makes extensive use of lookup tables for generating signatures, thereby minimizing the computational effort on part of the signature computing device. A Perl implementation of Schnorr is provided by the Crypt::Schnorr::AuthSign module. For usage information, we refer the readers to module's POD documentation.
Future Articles
This concludes part one in a series of three articles on Asymmetric Cryptography in Perl. Part two will discuss asymmetric crypto in the real world: systems and protocols such as SSH, PGP and SSL that are applications of asymmetric cryptography you use everyday. Along with a discussion of these applications, we will also look at the computational and security contraints that go in the design of real-world cryptography systems. Part three will discuss the building blocks of asymmetric cryptography, which will cover several interesting topics such as prime-number generation, bitfield/buffer manipulations, large number mathematics and number theory, all of which have comprehensive implementations in Perl.
