Continuation of Lecture 2 -27072009-

A digital signature is an electronic signature that can be used to authenticate the identity of the sender of a message or the signer of a document, and possibly to ensure that the original content of the message or document that has been sent is unchanged. Digital signatures are easily transportable, cannot be imitated by someone else, and can be automatically time-stamped. The ability to ensure that the original signed message arrived means that the sender cannot easily repudiate it later. A digital signature can be used with any kind of message, whether it is encrypted or not, simply so that the receiver can be sure of the sender's identity and that the message arrived intact. A digital certificate contains the digital signature of the certificate-issuing authority so that anyone can verify that the certificate is real.

Example of how digital signature work. (http://searchsecurity.techtarget.com/sDefinition/0,,sid14_gci211953,00.html)

Assume you were going to send the draft of a contract to your lawyer in another town. You want to give your lawyer the assurance that it was unchanged from what you sent and that it is really from you. 
1. You copy-and-paste the contract (it's a short one!) into an e-mail note. 
2. Using special software, you obtain a message hash (mathematical summary) of the contract.
3. You then use a private key that you have previously obtained from a public-private key authority to encrypt the hash.

4. The encrypted hash becomes your digital signature of the message. (Note that it will be different each time you send a message.)

At the other end, your lawyer receives the message. 
1. To make sure it's intact and from you, your lawyer makes a hash of the received message.
2. Your lawyer then uses your public key to decrypt the message hash or summary.
3. If the hashes match, the received message is valid.

Another example of how digital signature work can be seen in http://www.youdzone.com/signature.html

What is RSA? RSA is named after its inventors Rivest, Shamir and Adelman. It is the best known and most frequently used reversible asymmetric algorithm. Its key length is variable, 512 bits being considered as a minimum today and 2048 bits as to remain very secure in the near future. The block size is also variable, but must be smaller than the key's. The cipher text will be the length of the key. The public key consists of a product n of two large primes p and q and a fixed number e. The private key is a number d. 

Each participant will need to generate a public and corresponding private key: 

First choose a small constant e. Taking always the same small e does not make RSA less secure but greatly increases its performance. Two popular values for e are 3 and 65537. 

For a key size of k bits, choose two large primes p and q of size bits with relatively prime to e. To find this kind of large primes when e=3 for instance, use Miller and Rabin's probabilistic primarily test on odd random numbers multiplied by 6 with 5 added. Such (probable) primes p will obey relatively prime to 3. Let n=pq. 

The public key is the pair, the private key is, where, i.e. d is e's multiplicative inverse mod, found with Euclid's algorithm. 

The encryption and decryption functions e, d are identical in RSA: 

To encrypt a message to Alice, one computes, where Alice’s public key is. Only Alice will be able to decrypt c, using her private key to compute. Also, only Alice can sign a message with the signature. Anyone can verify the signature by checking that. 

RSA is secure because no one knows how to factor large numbers quickly. Indeed, to find d from e and n, one needs to know, i.e. the factors p and q of n. No other way to break RSA is known, and factoring a 512 bit number with the best techniques known requires about 500'000 MIPS years. 

RSA is much slower to compute than popular symmetric algorithms such as DES and IDEA. Therefore it will not be used to encrypt long messages, but rather to encrypt a random DES or IDEA key which is then used to actually encrypt a message. 

Other than RSA, there are other encryption algorithm such as DES, Triple DES and AES.

The Data Encryption Standard (DES) is a block cipher (a form of shared secret encryption) that was selected by the National Bureau of Standards as an official Federal Information Processing Standard (FIPS) for the United States in 1976. DES encrypts and decrypts data in 64-bit blocks, using a 64-bit key. It takes a 64-bit block of plaintext as input and outputs a 64-bit block of cipher text. Since it always operates on blocks of equal size and it uses both permutations and substitutions in the algorithm, DES is both a block cipher and a product cipher.

DES has 16 rounds, meaning the main algorithm is repeated 16 times to produce the ciphertext. It has been found that the number of rounds is exponentially proportional to the amount of time required to find a key using a brute-force attack. So as the number of rounds increases, the security of the algorithm increases exponentially.

Triple DES is the common name for the Triple Data Encryption Algorithm (TDEA) block cipher. It is so named because it applies the Data Encryption Standard (DES) cipher algorithm three times to each data block. Triple DES provides a relatively simple method of increasing the key size of DES to protect against brute force attacks, without requiring a completely new block cipher algorithm.

Advanced Encryption Standard (AES) is an encryption standard adopted by the U.S. government. The standard comprises three block ciphers, AES-128, AES-192 and AES-256, adopted from a larger collection originally published as Rijndael. Each AES cipher has a 128-bit block size, with key sizes of 128, 192 and 256 bits, respectively. The AES ciphers have been analyzed extensively and are now used worldwide, as was the case with its predecessor,[3] the Data Encryption Standard (DES). AES is based on a design principle known as a Substitution permutation network. It is fast in both software and hardware,[5] is relatively easy to implement, and requires little memory. Unlike its predecessor DES, AES does not use a Feistel network.