Public Key Cryptography

Author: Kevin Sornberger
Last Modified: April 5, 2007

Public Key Cryptography is a form of cryptorgraphy where two keys are used to encrypt and decrypt a message: a public key and a private key. Unlike standard encryption which uses a secret key for encryption and decryption, the public key can be publically distributed to anyone that you wish to communicate with, or who might want to communicate with you, only the private key must be kept secret. Although the keys are related, it is impossible to derive the private key even if you have the public key.

Contents 1 History 2 Applications 2.1 Public Key Encryption 2.2 Digital Signatures 3 How It Works 4 Examples 5 See Also 6 External links 7 References

History

There is some controversy over who originally came up with the idea of public key cryptography, there is some evidence that the British Secret Service was first, but kept it a secret and didn't do much with it. The first published concept of it was by Whitfield Diffie and Martin Hellman in 1975 which became known as the Diffie-Hellman key exchange.

Applications

Public Key Encryption

About Public Key Encryption is usually used for confidentiality. The sender encrypts the message with the receiver's public key and the only the receiver can decrypt the message with their corresponding private key. This ensures that only the intended receiver is able to read the message.

Digital Signatures

Digital signatures are one of the main uses of public key cryptography today. They allow the receiver to verify that the message's sender as well as that the information was not modified in any way turing delivery. This provides a great method for authentication and data integrety. This also provides evidence that the message actually did come from the sender if they try to deny it at a later time.

With a digital signature, the sender signs the message with their private key, and then anyone with the sender's public key can use it to verify both the sender's identity and the integrity of the message.

How It Works

There are 6 major parts for the public encryption scheme:

• Plaintext - This is the message that will be encrypted
• Encryption Algorithm - There are many different ways to implement public key encryption, the algorithm used is how the plaintext is modified.
• Public Key - This is made publically available and is used for encryption of the plaintext.
• Private Key - This key is kept secret to the user and is used to decrypt cyphertext
• Ciphertext - This is the encrypted message which is created by applying the encryption algorithm to the plaintext
• Decryption Algorithm - This explains how to use the corresponding key with the cyphertext to discover the plaintext

To obtain the keys:

1. Choose two large prime numbers p and q and get n = pq
2. Choose an integer e which is greater than 1 so that the greatest common divisor between (e, (p-1)(q-1)) = 1.
3. Choose an integer d, such that (de - 1) is evenly divisible by (p-1)(p-1) or de = 1 (mod (P-1)(Q-1))
4. The public encryption key is (e, n).
5. The private encryption key is (d, n).

Encryption:

1. Obtain the receipient's public key (e, n).
2. Convert the message to an integer M between 0 and n-1. (You can break a long message into a series of blocks where each block is represented by an integer). This is not for the encryption, but to get it into the required form for encryption.
3. The cyphertext C, is the remainder when M to the power of e is divided by n. (C=M^e (mod n))

Decryption:

1. Using the private key (d, n), compute C to the power of d modulo n to obtain M. (M=C^d (mod n))

Examples

• SSH
• SSL
• PGP

See Also

• Cryptographic Hashing
• Random Number Generation for Cryptography
• Block Cyphers
• The RSA Algorithm

External links

• Cryptography FAQ

References

• http://en.wikipedia.org/wiki/Public-key_cryptography
• http://www.mycrypto.net/encryption/public_key_encryption.html
• http://www.pgpi.org/doc/pgpintro/