Asymmetric Cryptography in Perl

Sep 26, 2001 by Benjamin Trott and Vipul Ved Prakash

Introduction

Symmetric cryptography allows Alice to exchange secret messages with Bob over the network, but only after they have shared a secret key. If Alice and Bob don’t live within commutable distance, or are unable to meet in person for any number of reasons, they have no option other than to share this key over the network. This, however, poses a problem. The network is insecure, and Eve, who systematically sniffs traffic between Alice & Bob, can get hold of any key they share over the network and read all subsequent communications encrypted with it without having to break the symmetric cipher.

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.

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.

Digital Signatures and Non-repudiation

Encryption provides only half of the solution to digital privacy. Identities in the online world are malleable and can be faked trivially; this necessitates the use of a signature mechanism to ensure that people are who they say they are. When you receive a message, how can you really know that the sender is who he or she purports to be? The message could have been written by someone else entirely; or it could have been intercepted in transit, modified and then passed on to you.

Digital signatures provide you with the tools to unequivocally determine whether a message is legitimate. You can use digital signatures to detect in-transit message tampering and to determine whether a message is truly from the advertised sender. Such signatures are unforgeable guarantees of both a message’s true author and of its validity. This concept, known as non-repudiation, also extends in the opposite direction: Since a digital signature provides absolute proof that the sender signed a piece of data, the sender cannot subsequently deny having signed that piece of data. Taken to its logical extension, once an author has signed his work, he can deny neither the validity of the signature nor the authorship of the work.

To digitally sign a message is to apply one’s private key to that message. Digital signatures use the same public and private keys that are used for encrypting and decrypting messages; in contrast to the sender using the recipient’s public key to encrypt a message, however, when signing the sender uses her private key to sign the message. This works because certain trapdoor functions also work as trapdoor permutations. Once the private key has scrambled the message, the resulting signature can only be unscrambled by the matching public key. If the recipient of the message holds a copy of this public key, he/she can then determine absolutely whether the sender signed it using the private key.

Here is an example:

Alice wishes to send a message to Bob, and wants Bob to be able to verify that she sent the message, and that it has not been modified in transit. After composing the message, Alice ``signs” that message using her private key, then sends the message and the signature to Bob. This signature is computed over the data in the message, such that it is unique to Alice’s private key and the message. In other words, this particular signature can only have been produced by Alice’s private key.

To verify the signature, Bob uses his copy of Alice’s public key to unscramble the signature; if he produces the original message, he knows that the message has not been tampered with. Meanwhile, if Eve is listening in on the network traffic and sniffs a copy of Alice’s message, she can easily modify it and send it on to Bob; but once she has modified the original message, the signature no longer matches the message. When Bob receives the modified message with its original signature, his attempts at verification will fail, and he will know that the message has been tampered with. Eve has no way of ``fixing” the signature such that it matches the modified message, because doing so requires possession of Alice’s private key – and only Alice has access to that key. Thus Alice’s identity and authorship can be guaranteed.

Here’s how Alice signs her message with Crypt::RSA:

    $private = new Crypt::RSA::Key::Private(
                  Filename => "keys/alice.private",
                  Password => 'alice's passphrase'
               );
    $rsa = new Crypt::RSA;
    $signature = $rsa->sign ( Message => $message, Key => $private );

Alice reads her private key from a disk file. Private keys are usually stored in encrypted form (using a symmetric cipher) for additional security, so they must be decrypted before use. Alice provides a password with which the key is decrypted, and reads the key in $private. She then signs her message with the sign() method of Crypt::RSA, and sends $signature and $message to Bob. Bob verifies the signature with the verify() method of Crypt:RSA using Alice’s public key:

    $public = new Crypt::RSA::Key::Public(
                  Filename => "keys/alice.public",
              );
    $rsa->verify( Message => $message, Signature => $signature,
                  Key => $public ) ||
                  die "Signature doesn't verify!\n";

It should be noted that sign() computes a digest of the message and signs that instead of the original message. This is typically how real-world applications generate digital signatures. Signing the entire message is expensive and doesn’t provide any benefit over signing a digest.

Diffie-Hellman Key Agreement

Key agreement is the process of two parties agreeing on a shared encryption key without exposing that key to potential intruders. Key agreement protocols are different from public-key encryption protocols in that they are not meant for encrypting communications; rather they are used to agree upon a secret that can be used for encrypting communications with symmetric ciphers. Shortly after Rivest, Shamir and Aldeman published their RSA paper, Diffie & Hellman published a key agreement protocol that has come to be known as Diffie-Hellman Key Agreement.

Here’s how it works:

To begin the key exchange, Alice and Bob choose a property p and a property g; the values for these properties are shared by both parties, and are often computed by a central authority, rather than be either one of the parties. Each party then computes a random private-key integer x, where the length of x is at most (number of bits in p) - 1. Each party then computes a public key y based on g, x, and p; the exact value is:

    y = g^x mod p

The parties exchange these public keys.

The shared secret key is generated from the exchanged public key, the private key, and p. If Bob’s public key is denoted y_Bob, then Alice computes the shared secret using the formula

    secret = y_Bob^x mod p

The mathematical principles involved ensure that both parties will generate the same shared secret key. Having computed the shared secret – again, without that secret ever passing over the insecure network – Alice and Bob can use the key to encrypt their communications; all future messages between the two (during this session) can be symmetrically encrypted using the shared secret.

More information can be found in PKCS #3 (Diffie-Hellman Key Agreement Standard).

A Perl implementation of Diffie-Hellman key agreement can be found in Crypt::DH. To use Crypt::DH, Alice must agree ahead of time with Bob as to the values for p and g. For example, the SSH-2 protocol, which uses Diffie-Hellman, uses a value of 2 for g, and a value of

      FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
      29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
      EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
      E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
      EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381
      FFFFFFFF FFFFFFFF

for p. We begin using Crypt::DH by initializing a Crypt::DH object with the chosen values for p and g:

    use Crypt::DH;
    my $dh = Crypt::DH->new;
    $dh->p($p);
    $dh->g($g);

Each party then generates a public and a private key:

    $dh->generate_keys;

After generating the keys, Alice must send her public key to Bob, and Bob must send his public key to Alice, over the network. Once Alice has received Bob’s public key, she can generate the shared secret using that public key, and her own private key:

    my $shared_secret = $dh->compute_key( $bob_public_key );

This shared secret is a big integer. Often this big integer is linearized into a string of octets to be used as a key for symmetric encryption between Alice and Bob. Since both parties have generated the same shared secret, Alice is able to decrypt messages that Bob has encrypted with the shared secret, and vice versa.

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.