11.5 Public-Key Cryptography
There was a revolution, the only true revolution in the field or cryptography according to many, in 1977 when the concept of public-private key cryptography was enunciated by Diffie and Hellman. They did not have an algorithm, but outlined in precise terms the properties it must have. Rivest, Shamir and Adelman came up with an algorithm almost immediately afterwards, an algorithm that has endured through the passage of time. This algorithm is called the RSA algorithm. Perl provides an implementation in terms of a module called Crypt::RSA. We do not discuss the RSA algorithm, but discuss its usage.
A public-private key algorithm uses two distinct keys instead of one. Thus, if A is the sender of information and B is its receiver, A possesses two keys: a private key and a public key . They are large keys, possibly 1024 bits or more in length. They are related by number theoretic properties. A bases the computation of and by starting with two hugely large prime numbers p and q. These two prime numbers must be kept secret by A. They should be thrown away as well after the keys have ben computed. A computes and . A safeguards , but makes public and gives it away to anyone who asks or even without asking.
When A needs to send a message m securely to B, the following steps are performed.
1. A encrypts m using his or her private key, . The encryption algorithm is known to everyone. The private key must be securely guarded. Let the encoded message or ciphertext be called c. c is sent by A to B. This communication, in the context of computer programs, is usually in the form of socket-based transmission. For example, Web based programs that use the RSA algorithm use socket-based communication.
2. B receives the encoded message c. B performs decryption using A’s public key . The decryption algorithm is known to everyone. is also known to everyone since A makes it public after computing it. The decryption computation produces the original message or cleartext m although the encryption and decryption keys are different.
Thus, the process of secure communication is simple. But, the numbers involved are very very big, and hence, every computation step is slow, even on the fastest computers. In practice, large amounts of data are not transmitted between a client and a server using public-private key algorithms such as the RSA. The RSA is usually used to transmit the single key needed for conventional cryptography.
Public-private key cryptography requires every potential participant p in communication to possess two keys: and . So, if there are n potential participants, 2n keys need to be computed. In contrast, if conventional cryptography is used, n parties need keys. For even a moderately small number, the difference between 2n and is huge. In public-private key cryptography, is kept secret by the potential participant p, and is known to the world. Thus, there is no need to transmit a key between two communicating parties securely, as in the case of conventional cryptography. This reduces the infra-structural burden for secure communication enormously. Both
conventional cryptographic techniques and public-private key cryptographic techniques are practically impossible to break, i.e., they provide the same level of security. Thus, public-private key cryptography should be preferable to conventional cryptography in practice. But, in reality, conventional cryptographic techniques are much faster to implement.
Perl has an implementation for the RSA algorithm. The implementation of Crypt::RSA uses a fast mathematical module called Math::Pari to perform number theoretic computation. The following program shows how Crypt::RSA can be used. It does not use any socket-based communication, but one can clearly foresee how Crypt::RSA can be used to send data securely across the Internet.
Program 11.11
#!/usr/bin/perl
#rsatest.pl
use Crypt::RSA;
use strict;
my ($rsa, $public, $private, $plaintext, $ciphertext);
my ($plaintext1);
$rsa = new Crypt::RSA;
#If keysize is small, it will not encrypt
($public, $private) = $rsa->keygen (
Size => 2048,
# Size => 512,
Identity => 'Jugal Kalita, kalita@pikespeak.uccs.edu',
Password => "University of Colorado at Colorado Springs",
Cipher => "DES",
Verbosity => 1
) or die "Cannot create key pair: " . $rsa->errstr();
#$public->write (Filename => "test.public");
print "_" x 50 . "\n";
print "public key is:\n$public\n";
foreach (keys %$public){
print "key = " . $_ . "value = " . $$public{$_} . "\n";
}
#$private->write (Filename => "test.private");
print "_" x 50 . "\n";
print "private key is:\n$private\n";
foreach (keys %$private){
print "key = " . $_ . "value = " . $$private{$_} . "\n";
}
print "_" x 50 . "\n";
$plaintext = q{Deposit $250,000.00, Account No 5295023273, Wells Fargo}.
q{Bank, ABA Routing No= 10200076};
print "plaintext before encryption is:\n$plaintext\n";
$ciphertext = $rsa->encrypt (
Message => $plaintext,
Key => $public,
Armour => 1
) or die "Cannot encrypt: " . $rsa->errstr();
print "ciphertext is:\n$ciphertext\n";
print "_" x 50 . "\n";
$plaintext1 = $rsa->decrypt (
Cyphertext => $ciphertext,
Key => $private,
Armour => 1
) or die "Cannot decrypt: " . $rsa->errstr();
print "_" x 50 . "\n";
print "The decrypted plaintext is:\n$plaintext1\n";
print "_" x 50 . "\n";
my ($signature, $verify);
#PKCS#1 v1.5 signature
$signature = $rsa->sign(
Message => $plaintext,
Key => $private) or die "Cannot sign: " . $rsa->errstr() . "\n";
$verify = $rsa->verify (
Message => $plaintext,
Signature => $signature,
Key => $public
) or die "Cannot verify: " . $rsa->errstr() . "\n";
print "PKCS#1 v1.5 verify = $verify\n";
#Probabilistic Signature Scheme
my ($pss);
$pss = new Crypt::RSA::SS::PSS;
$signature = $pss->sign(
Message => $plaintext,
Key => $private
) or die "Cannot sign: " . $rsa->errstr() . "\n";
$verify = $pss->verify (
Message => $plaintext,
Signature => $signature,
Key => $public
) or die "Cannot verify: " . $rsa->errstr() . "\n";
print "PSS verify = $verify\n";
We create a new object of type Crypt::RSA. It is called $rsa. It is used to compute two keys: $public and $private. The keys are generated by the following statement.
($public, $private) = $rsa->keygen (
Size => 2048,
# Size => 512,
Identity => 'Jugal Kalita, kalita@pikespeak.uccs.edu',
Password => "University of Colorado at Colorado Springs",
Cipher => "DES",
Verbosity => 1
) or die "Cannot create key pair: " . $rsa->errstr();
The generation process uses the keygen method of the Crypt::RSA object $rsa. keygen returns two keys. The size of the keys is 2048 bits. The Crypt::RSA module does not create the keys if the key size is small. The minimum size allowed is 48 according to the documentation. The size must be an even integer. Key generation is time consuming. 2048 bits or more can be used as key size, but the computation time will be quite slow, in terms of minutes, not seconds. The keygen method is be given an identity of the owner. This value is unused in the creation of the keys. A password needs to provided to keygen. This is the string with which the private key is encrypted so that it remains private. To securely keep the private key, the keygen method is given an algorithm to encipher the private key. A conventional cryptographic algorithm is needed. The DES conventional algorithm given as the value of the Cipher argument is used here for encrypting the private key. The default conventional encryption algorithm is one called Blowfish which is implemented in Perl as Crypt::Blowfish. If for some reason, the key pair cannot be produced, the program dies
and it prints an error using the errstr method. In this example, the public key is written into the file test.public and later printed for illustrative purposes. Each key is a hash, and the program prints the key-value pairs for the hash just to show what they are.
Next, a plaintext or cleartext message is created and stored in the scalar $plaintext. The message is shown below.
$plaintext = q{Deposit $250,000.00, Account No 5295023273, Wells Fargo}.
q{Bank, ABA Routing No= 10200076};
The program encrypts the message using the public key $public. In practice, the public key is known to everyone and someone sending a message encrypts the message with the public key of the recipient. The encoded message is called $ciphertext. The Armour argument, if true, causes encrypt to encode the ciphertext as an ASCII message so it can be printed and read easily. The program dies if it cannot encrypt. It prints the encrypted message as illustration.
In a realistic program, at this point the encrypted message is sent by the program, possibly using a socket as a means of communication. To keep the example simple, we do not use sockets, but simply perform the decryption in the same program. The program decrypts the ciphertext using the decrypt method of the Crypt::RSA object. For decryption, the private key $private is used. In practice, after the recipient has received the encoded message, the recipient decodes the ciphertext using the recipient’s closely safeguarded private key. The program then prints the decrypted plaintext which is the same as what we started with.
The Crypt::RSA algorithm allows us to produce digital signatures as well. Digital signatures are like message digests that are discussed in Section 11.1. The module follows a standard called the PKCS to generate signatures. PKCS stands for Public Key Cryptographic Standards. This is a standard application programming interface (API) to hold cryptographic information and perform cryptographic functions. Digital signatures are like message digests, but provide an adequate amount of security when the sender and the receiver do not trust each other completely. When there is complete trust, i.e., the receiver or the sender is not guaranteed to cheat the other, message digests can be used. Digital signatures are like hand-written signatures. A message digest provides authentication, but a digital signature is more stringent. A digital signature must have the
following properties [Sta99].
• It must be able to verify the author, the date and the time of the signature.
• It must be able to authenticate the contents at the time of the signature.
• The signature must be verifiable by third parties, to resolve disputes.
Thus, a digital signature includes the authentication function performed by a message digest. Stallings formulates the following requirements for a digital signature.
• The signature must depend on the message being signed.
• The signature must depend on some information unique to the sender.
• The signature must be easy to produce.
• The signature must be easy to recognize and verify.
• It must be computationally infeasible to forge a digital signature.
• It must be practical to keep a copy of the digital signature in storage.
The Crypt::RSA module provides a method called sign to produce digital signatures. It creates the signature based on the private key. In practice, an individual signing the message signs it with his or her private signature. Also, in practice, the signature is verified by not the party that produces the signature, but by someone else, possibly, the receiver or a third-party service. In this program, verification is performed immediately for illustration purposes. Verification is performed on the plaintext using the public key. Here, signing and verification are done on the plaintext without encrypting. In practice, it is possible that a message is encrypted first and the ciphertext is signed, and later verified by someone other than the producer of the signature. The verification status is printed by the
program.
There are many methods to produce digital signatures. The default signature scheme used by Crypt::RSA is called the Probabilistic Signature Scheme (PSS) that the Crypt::RSA::SS::PSS module implements. The module implements a sign and verify method. The first calls to sign and verify use the default, whereas the second pair of calls uses the same signing and verifying algorithm, but does so explicitly. As an aside, Perl also provides implementation for other digital signature algorithms such as the Digital Signature Algorithm (DSA) in terms of the module Crypt::DSA,
and Pretty Good Privacy (PGP) based signature in terms of the module PGP::Sign. These two signature algorithms are unrelated to the RSA algorithm.
The output of running the program is given below.
..+.......+(31).....+..+(54).+..+.........+...........+..+.....+.+...........+..
.......+.................................+.+.+(86)..............+.....+(161)...+
..........+......+.....+..+.+..........+(209).+......+..........+..+.....+...+..
..+..+....+................+...........+..+.....+.+.+.........+..........+......
....................+(374)....+...+...........+.......+(446).....+..............
......+..........+...+.+................+...+....+........+.+...+.+........+....
........................+..+....+.............+........+........+..+..+.........
+................+.......................+............+........+............+...
....+..+........+.......................+........+...+.+.+......................
...........+..........+.......+.............+......+...+.+(821).+.....+...+...+.
........................+...........................................+........+..
.....+(1024)
....+.....+(32)............+..+(52).........+........+.........+(78)............
.+(134).......+.........................+.......+....+........+.....+......+...+
............................+......+........+........................+.+....+...
..+........................+....+.......+...+.....................+.....+.......
.....+...+...+................+..+.......+...+(177)..........+........+..+......
+...........+.......+........+...+......+.+...............+.................+...
.+.......+.+........+...+....+..............+..............+............+..+...+
.......+.....+...........................+..+.+.+..............+........+.......
...........+............+...+...+...+.....+...+....+(214)...+...........+..+.+..
.....+....+....................+..............+...........+...........+...+....+
....+...........................+...+.....................+......+..............
............................+......+.............+..+......+...............+.+..
......+(396)....+..........+.......+.......+........+...........................
........................+.+..+.........+.....+..................................
.+..........+.......+.......+.+......+.........+...................+.......+.+..
......+...................+..+.....+..+....+............+.+........+............
.............................+....+..........+.+.....................+...+......
...................................+(611).............................+......+.+
....+...+...+...+..+(1024)
__________________________________________________
public key is:
Crypt::RSA::Key::Public=HASH(0x8102eb8)
key = evalue = 65537
key = nvalue = 17104917492586114818543054874204650554228503940656776060622052453
30800416136559412363482662140688954622468029644183264492210998161249501803468013
08235445803342311999114535491608842047053711781310960269142605835434470622175871
53114508048285334096229138284398603786837554362226927603490307776909158736109797
70001283266228266237719129585413901709140486460312918720026229304692181368535523
26626399290032270266921035610972928571560660397989083125691181041378117690023137
15408530197170481579489973172140442099179612631966720072872633860963195057014666
396855496258820244074390411624320832808298721272059391697921140703280619
key = Versionvalue = 1.8
key = Identityvalue = Jugal Kalita, kalita@pikespeak.uccs.edu
__________________________________________________
private key is:
Crypt::RSA::Key::Private=HASH(0x8102ef4)
key = privatevalue = Tie::EncryptedHash=HASH(0x828d8f8)
key = Versionvalue = 1.8
key = Identityvalue = Jugal Kalita, kalita@pikespeak.uccs.edu
__________________________________________________
plaintext before encryption is:
Deposit $250,000.00, Account No 5295023273, Wells FargoBank,
ABA Routing No= 10200076
blocksize: 214
ciphertext is:
-----BEGIN COMPRESSED RSA ENCRYPTED MESSAGE-----
Scheme: Crypt::RSA::ES::OAEP
Version: 1.21
eJwBEQHu/jEwADI1NgBDeXBoZXJ0ZXh0gqChBq8u6f3Lcsdy8zyGyD0skT1w6m3ZKVnZUSmcOFIt
GjNKCdgiJvClhDKkdV56SxIEBcTb6Etstf7jrYlhC4YhFKKYJ2QwitSAO04gPcC8i57x22ZmGV1Y
aVHWKekWtn1cAnBfjalfxXxiXQlptsjgHL8SOIam6MWwKhH5/whHxxGluRJi1vgGl6PESqyeURdI
8usomlcDm1Chrm7jbb/kAijws0BIuUibNQZBNILRl8pqCJdGmsMNo+lcLrD/EKk6tY2n3D35nNuu
Emvy9IuVeDrBpuSYCPaUhfMYuarQMOY4CtdPc8jp2x02k+pqVg3Wg7QiCQ2pd7DQiZkOHgBdgqU=
=86uLtp34INeMsaLgRaIjwg==
-----END COMPRESSED RSA ENCRYPTED MESSAGE-----
__________________________________________________
blocksize: 256
__________________________________________________
The decrypted plaintext is:
Deposit $250,000.00, Account No 5295023273, Wells FargoBank,
ABA Routing No= 10200076
__________________________________________________
PKCS#1 v1.5 verify = 1
PSS verify = 1
The dots show progress of computation on the screen.