Asymmetric Cryptography in Perl
by Vipul Ved Prakash, Benjamin Trott
|
Pages: 1, 2, 3
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.
