Introduction to Public-Key Cryptography

Jed Baer

IANBS – I Am Not Bruce Schneier

Topics

Cryptography

Symmetric-Key

Public-Key

GNU Privacy Guard

E-Mail

Cryptography

Terminology

Code: A system of hiding the meaning of a message by replacing words or phrases with other words or phrases

Cipher: Any general system for hiding the meaining of a message by replacing each letter in the original message with another letter.

Encipher: To turn the original message into a message by applying a cipher

Decipher: The reverse of encipher

Encrypt: To encipher or encode (a message)

Decrypt: The reverse of encrypt

Symmetric-key cryptography: A form of cryptography in which the key required for encrypting is the same as the key required for decrypting

Public-key cryptography: A system of cryptography which overcomes the problems of key distribution by using a pair of keys, one of which is public and freely distributed, the other being kept secret.

Plaintext: the message before encryption, or after decryption, plainly readable

Ciphertext: the message after encryption, unreadable

Symmetric Key — 1 key; A Single Key Encrypts and Decrypts

Enigma, DES, DES3, AES (Rijndael), Blowfish, Serpent

Public Key — 1 key pair, consisting of a Private Key and a Public Key

Either Key Will Encrypt

Whichever Key is Used to Encrypt, the Other Member of the Pair will Decrypt

Public Key is Freely distributed

Private Key Must Remain Private and Secured

Public Key Cryptography

Invented as a Means to Securely Exchange a Secret — The Key to a Symmetric Cipher

1st Invented in England, But Kept Secret

Invented in the U.S.A. by Whittfield Diffie and Martin Hellman (May 1975)

One-way function with a trap-door

Discrete exponentiation / Discrete Logarithm (May 1976)

New Directions in Cryptography; IEEE, November 1976

Included the concept, but not the means, for digital signatures

Implemented by Ron Rivest, Adi Shamir, and Len Adelman (RSA) in a Patented Algorithm

Rivest reads New Directions in Cryptography

Rivest invents new algorithm (April 3, 1977)

continued

Public Key Cryptography

Released “in the wild” by Phil Zimmerman, founder of Pretty Good Privacy (PGP)

Other Algorithms Exist (e.g. ElGamal, DSA)

Example: SSL

Essentially, Rivest's idea was to strip the factoring problem down to almost naked essentials. A public key is generated by multiplying two large (over 100 digits), randomly chosen prime numbers. Easy. Then another simple step (if you have a computer): randomly choose yet another alrge number, one that had certain easy-to-calculate specified properties. This would be known as the encryption key. The complete public key consists of both that encryption key and the product of those two primes.

Rivest then provided a simple formula by which someone who wanted to scramble a message could use that public key to do so. The plaintext would now be ciphertext, profoundly transformed by an equation that included that large product. Finally, using an algorithm drawn from the work of the great Euclid, Rivest provided for a decryption key -- one that could only be calculated by using the two original prime numbers. Using the decryption key, one could easily revert the ciphertext to the plaintext message.

[...]

Some of the mathematics of the decryption key -- which works as the private key in this system -- was derived from the work of another legendary mathematician, Leonhard Euler [...]

(crypto: How the Code Rebels Beat the Government -- Saving Privacy in the Digital Age; Steven Levy)

SSL

Secure Sockets Layer

Site Certificate is a Public Key

Public key is used to encrypt a “session key” which will be sent back to the server, and used to encrypt further communication using a symmetric cipher.

Symmetric encrypt / decrypt ciphers are much faster than assymetric ciphers

Gnu Privacy Guard

Free Software Implementation of OpenPGP

http://www.gnupg.org/

Supports several PK and Symmetric Algorithms, but not IDEA (Patent Issues)

Set of libraries, command-line tool, and GUI front-end

Provides command-line options for multi-version backward compatibility with PGP

Generating a Key Pair

gpg --gen-key

Listing Keys

gpg --list-keys

Generating a Revocation Certificate

gpg --gen-revoke key-id where key-id is

e-mail address

real name

comment

Revokes entire key (we're not getting into sub-keys)

Exporting your Public Key

gpg --export --armor key_id > filename

you can export to a keyserver too

Generating a Key Pair

more

Listing Keys

(you can list your private keys too)

Generating a Revocation Certificate

Distributing Your Public Key

Using a keyserver — RTFM

Importing Keys

Signing Keys

gpg “self signs” keys you generate

A tautology?

You vouch for the authenticity of your own key

Signing others keys

You vouch for the authenticity of someone else's key

Establishes level of trust

Trust refers primarily to identity, but identity can be used to infer other trust

Never sign keys without physical verification

instructions for key-signing party in links slide

Why Secure E-Mail?

Privacy

Dissident Communications

Whistleblowers

Confidential Data

Message Integrity

Sender Identification

Digital Signature Verifies Identity

Detect Tampering

Encrypted Message Hash Verifies the Message

Non-Repudiation

Example: Contracts via E-Mail

Tools For Securing E-Mail

Mail User Agents (MUA)

pine

mutt

elm

KMail

Mozilla Thunderbird

Sylpheed

Cryptography

Pretty Good Privacy (PGP) — Phillip Zimmerman; Now a Standard — RFC-2440)

GNU Privacy Guard (GnuPG); implements RFC-2440

Internals of Signed / Encrypted e-mail

Signing a Message

Hash the message text

Encrypt the hash using your private key

Signature can be either inline or attached

Encrypting a Message

Encrypt the message using recipient's public key

Sign first, then encrypt

Otherwise ciphertext from both the public and private keys of the key-pair are visible

Sylpheed

Free Software MUA

GTK+

http://sylpheed.good-day.net/

Some distributions do not include Sylpheed with gpg support (Fedora, for example)

examples

A Signed Message

A Signed Message — Detached Signature

A Signed Message — No Key

A Signed Message With Tampering

Inline Signature

Note: Sylpheed does not support inline signed messages

Receiving a Signed and Encrypted e-mail — decryption

Receiving a Signed and Encrypted e-mail — Verifying Signature

Signing an Outbound e-mail

Menu

Message

Sign

Encrypt

Encryption occurs when message is sent or queued

Encrypting an Outbound e-mail

Raw Encrypted e-mail

GNU Privacy Assistant

Further Reading

http://www.gnupg.org/docs.html

What is Diffie-Hellman?

http://www.rsasecurity.com/rsalabs/faq/3-6-1.html

Cryptography FAQ

http://www.faqs.org/faqs/cryptography-faq/

The OpenPGP Alliance

http://www.openpgp.org/

Simon Singh's Crypto Corner

http://www.simonsingh.net/Crypto_Corner.html

http://www.openssl.org

http://www.cryptnet.net/fdp/crypto/gpg-party.html

http://www.schneier.com/essays-comp.html

http://www.linuxjournal.com/article/7863

Books

Bruce Schneier

http://www.schneier.com/books.html

Applied Cryptography

Practical Crypography

and several others

Simon Singh

http://www.simonsingh.net/The_Code_Book.html

Stephen Levy

http://mosaic.echonyc.com/~steven/crypto.html

David Kahn

http://david-kahn.com/david-kahn-books-literature.htm

The Codebreakers

Kahn on Codes

Jed Baer

2004-09-21T16:06:44

Jed Baer