Asymmetric Cryptography in Perl
An Introduction
by Vipul Ved Prakash, Benjamin TrottSeptember 26, 2001
Introduction
In the early days of public networks, Witfield Diffie & Martin Hellman, then researchers at Stanford's mathematics department, were battling against this fundamental problem - how to enable two complete strangers to bootstrap secure communications over an insecure network. Their work culminated in a seminal paper, titled ``New Directions In Cryptography,'' that laid down the foundations of what has come to be known as asymmetric cryptography. Asymmetric cryptography did not only provide an elegant solution to the aforementioned bootstrapping problem, it simultaneously solved several other problems of digital privacy, including unforgeable signatures and non-repudiation.
In this article we look at the various methods of asymmetric cryptography and Perl modules that provide ready-to-use implementations of these methods.
|
|
Trapdoor One-Way Functions
Central to asymmetric cryptography, is the notion of trapdoor one-way functions. One-way functions are easy to compute in one direction but impossibly hard in the reverse direction. Breaking an egg, for example, is a one-way function. Trapdoor one-way functions are much like one-way functions except they are easy to reverse if certain ``trap-door'' information is available.
In an asymmetric cryptosystem, each user has two keys: a public key that others use to encrypt messages to the user and a secret key for decrypting messages encrypted with the public key. (For this reason, asymmetric cryptography is also commonly referred to as public-key cryptography.) The secret key is zealously guarded by the user while its public counterpart is indiscriminately distributed to the world. Unlike symmetric keys, that are usually random numbers of a certain length, asymmetric keys are numbers with special mathematical properties that are computed using a key generation algorithm.
To send a private message to Bob using public-key cryptography, Alice first acquires his public key. Public key exchange can be carried out over an insecure network because the knowledge of Bob's public key does not enable Eve to decrypt messages encrypted with it. Alice then encrypts her message with this key. The encryption operation consists of computing the trapdoor one-way function on the message (in the easy direction), using the public key, to generate the ciphertext. Once generated, Alice sends the ciphertext over to Bob.
|
Table of Contents
• Trapdoor One-Way Functions |
To recover the plaintext, Bob and Eve (who's sniffed a copy of ciphertext off the wire) must reverse the trapdoor one-way function. Bob uses the trapdoor information, his private key, to easily decrypt and read the message. Eve, on the other hand, without the benefit of trapdoor information, is faced with a task much harder than putting a broken egg together.
RSA
When Diffie & Hellman proposed their theory of asymmetric cryptography and trapdoor one-way functions, they did not suggest a particular trapdoor one-way function. Rivest, Shamir and Aldeman, then-professors at MIT, were the first to devise such a function around the conjectured difficulty of factoring prime products. Their cryptosystem, RSA, has withstood several years of cryptanalysis and is the most widely used public-key cryptosystem today.
Here's how RSA works: To generate an RSA key pair, Bob chooses two large primes, p & q
(each 1024 bits/308 digits long) and computes their product,
n = pq
Then, he chooses a random number C<e> that is smaller than and relatively prime to C<(p-1)(q-1)>,
1 < e < (p-1)(q-1)
gcd(e, ((p-1)(q-1)) = 1
Finally, with the extended euclidean algorithm, he computes,
ed = 1 mod (p-1)(q-1)
(n,e) becomes his public key, and d the secret key.
Upon getting Bob's public key, Alice encrypts her message with it. To do
so, she converts her message into a number, m, between 1 and n,
and computes:
c = (m ^ e) mod n
c is the ciphertext; Alice sends it to Bob, who computes:
m = (c ^ d) mod n
thereby recovering the original m. He converts m back to text form
and reads the message.
Eve, who has been sniffing the traffic between Alice & Bob all this while,
has Bob's public key, (n,e), and the encrypted message from Alice,
c. To decrypt c, she must learn the value of d. Eve could compute
d and decrypt the message if she knew p and q. But to discover
p and q, she has to factorize n, which, given the known
algorithms for factoring and the current state of computational technology,
is considered intractable.
Crypt::RSA
If you are wondering where Perl comes into all this, then the answer is right here. Through extension modules on CPAN, Perl provides efficient, secure and DWIM implementations of several asymmetric cryptosystems. A comprehensive RSA implementation is provided by the Crypt::RSA package.
Here's how Alice sends an RSA encrypted message to Bob using Crypt::RSA:
Bob generates a 2048-bit key-pair:
$rsa = new Crypt::RSA;
($public, $private) = $rsa->keygen( Size => 2048 )
He sends $public to Alice, possible by e-mail, who encrypts her message (a string stored in $message) with it:
my $c = $rsa->encrypt( Message => $message, Key => $public );
Alice sends the ciphertext, $c, to Bob, who decrypts it with his
private key, $private, to recover the original message:
$message = $rsa->decrypt( Ciphertext => $c, Key => $private );
Usually, Alice & Bob don't need more four or so lines of code to carry out a secure exchange using Crypt::RSA. However, it's instructive to look at what Crypt::RSA does underneath these four lines and how it can be made to do things a little differently.
Crypt::RSA is structured as a bundle of modules that encapsulate different aspects of the RSA cryptosystem. Crypt::RSA itself is a convenient front-end to other modules in the bundle that sits between the user and other modules, and pre-processes data to meet expectations of both.
One of Crypt::RSA's responsibilities is to convert text to numbers and
back. Since the RSA algorithm works on numbers smaller than n,
plaintext is first converted into a list of numbers smaller than n,
that are converted back to text after encryption and concatenated to form
the final ciphertext. The same process is carried out at decryption.
The encryption modules of Crypt::RSA additionally carry out a process
called ``padding.'' It has been shown that textbook RSA, as described in the
previous section, is vulnerable to known plaintext attack. That is, if Eve
can force Alice to encrypt certain quantities of known text, then she can
recover p and q without having to factor n. To prevent this
attack, plaintext blocks must be padded with random data in a special way.
Over the years, a padding standard known as PKCS #1 has come into wide use. Crypt::RSA implements PKCS #1 as well as the newer standard, OAEP. OAEP provides the notion of plaintext-aware encryption, and is recommended for applications that don't need to interoperate with with older PKCS #1 applications. Crypt::RSA uses OAEP padding by default. However, it can be instructed to use PKCS #1 by passing a parameter to new(), like so:
$rsa = new Crypt::RSA ( ES => 'PKCS1v15 )
ES stands for ``Encryption Scheme'' and PKCS1v15 means the PKCS #1 standard version 1.5 as described in the RFC 2437.
