- In chapter 2 we discuss the basic elements of cryptography.

- You'll not only understand the
*what*but also the*why*?

- After this chapter we cover:
- Symmetric key cryptography.
- Public key cryptography.
- Hash functions.

- The basic terminology of crypto:
- Cryptology: The art and science of making and breaking
*secret codes*. - Cryptography: The making of
*secret codes*. - Cryptanalysis: The breaking of
*secret codes*. - Crypto: A synonym for all the above.

- A
*Cipher*or*Cryptosystem*is used to*encrypt*and*decrypt*data. - Unencrypted data is
*plaintext*. - One encrypts plaintext to produce
*ciphertext.* - One decrypts ciphertext to recover plaintext.
- A
*Key*is used to configure a cryptosystem.

- In a
*Symmetric Cipher,*the same key is used for encryption of plaintext and decryption of ciphertext.

*Public Key Cryptography*: a different key is used for encryption than is used for decryption.- With different keys, the encryption key can be made
public and is therefore called the
*Public Key*. - The decryption key must be kept secret/private and is
therefore called the
*Private Key*.

- In an ideal cipher, it's not feasible to recover the plaintext without the key.
- The algorithms used by a cipher should not be considered nor kept secret.
- It is [now] a fundamental tenet of crypto that the cryptosystem itself is not the secret.
**The only secret is the key**...Kerckhoff's Principle.- In early forms of crypto (and sometimes even today),
this principle was violated.

- Kerckhoff's Principle (KP):
- Secrets don't stay secret for long.
- Software Reverse Engineering (SRE) can be used to recover algorithms from software--including ciphers.
- Tamper-resistant hardware is not fool-proof and embedded cipher algorithms can still be recovered.
*Cryptographers*(experts in cryptology) will not deem a crypto-algorithm (e.g,. a cipher) worthy of use without extensive public analysis.- KP is often extended to apply to an entire security system.

- We'll examine 4 classic ciphers.
*Simple Substitution*- More than 2000 years old.

*Double Transposition*

- Concepts are still used in modern ciphers.
*Classic Codebooks*- Many modern ciphers can be viewed as "electronic" codebooks.
*One-Time Pad*- A practical cipher that is provably secure.

- A simple implementation:

- The plaintext (message) is encrypted by substituting
each letter with the letter of the alphabet that occurs
*n*places__ahead__of the current letter. - The ciphertext is decrypted by substituting each letter
with the letter of the alphabet that occurs
*n*places__before__the current letter. *Assumption: We're working with plaintext written using the English alphabet (26 letters).*- Encrypt example #1 with
*n*= 3: -
Plaintext

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

Ciphertext

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

A

B

C

- Encrypt example #2 with
*n*= 3: -
Plaintext

H

E

L

L

O

W

O

R

L

D

Ciphertext

K

H

O

O

R

Z

R

U

O

G

- Simple Substitution with
*n*= 3 is known as*Caesar's Cipher*as it was successfully used by Julius Caesar. - Given that we're working with the English alphabet, the
possible keys (values of
*n*) are {0,1,2,...,25}.

- 26 possible keys is a
*k**eyspace*...quite easy to try them all! - With 26 possible keys Trudy can expect to recover the plaintext by trying 13 keys on average.

- Brute force attacks are always something that Trudy can try.
- If Trudy has enough time/resources she may eventually
stumble upon the key. This is known as an
*Exhaustive Key Search*. - Exhaustive Key Search is the most elementary crypto attack.
- It's necessary, but from from sufficient, that the keyspace for a cipher be too large for Trudy to try all of them in a reasonable amount of time.

- How large of a keyspace is enough?
- If Trudy has a fast computer that can test 2^40
keys/second:

- A keyspace of size 2^56 can be exhausted in 2^16 seconds or 18.2 hours.
- A keyspace of size 2^64 can be exhausted in 2^24 seconds or 194 days.
- A keyspace of size 2^128 can be exhausted in 2^88
seconds or 9 quintillion years (!)

- Modern ciphers usually have a key of 128 bits or more, yielding a keyspace of 2^128 or more.

- Back to Caesar's Cipher (modern equiv is ROT13 which has
*n = 13*) - If we only allows shifts of the alphabet, then the keyspace (26 keys) is too small.
- There's no need to limit ourselves to shifts by
*n*. - We can use any permutation of the alphabet.
- There are 26! or about 2^88 possible permutations of the English alphabet, and therefore 2^88 possible keys.
- [26 choices for the first letter * 25 choices for the second letter * ... * 1 choice for the last letter]
- With Trudy's fast computer that can try 2^40 keys per second, it would take Trudy 2^44 seconds (8900 millennia) to try all the keys.
- On average Trudy would find the key in half the time, which is still 4450 millennia.
- This large keyspace does not make Simple Substitution secure (recall that a large keyspace is a necessary but not sufficient condition).

- Since it's too much work to try all 2^88 keys (permutations of the English alphabet), Trudy has to be more clever.
*Assumption: We're working with plaintext written using the English alphabet (26 letters).*- Trudy can make use of English letter frequency counts.
- For example, if "X" is the most common letter in the
ciphertext, and "E" is the most common letter is English
words, Trudy can try replacing "X" with "E" in the
ciphertext.

- Trudy can continue is this fashion with other letters until she recognizes words.
- With sensible use of frequency counts Trudy can cut down the 4450 millennia is would have normally taken to find the key.
- This attack on Simple Substitution shows that a large keyspace is not sufficient to ensure security.

- How do we protect against attacks when new attacks are developed all the time?
- Ciphers must be subjected to extensive analysis.
- The more cryptographers that fail to break a cipher, the more confidence we have in the cipher.
- This leads us to the an important definition...

- Provably secure ciphers are few and far between. Those that do exist are impractical for most uses.
- We say that a crypto-system is secure if the best-known attack requires as much work as an exhaustive key search.
- No shortcuts like we saw in the cryptanalysis of the Simple Substitution.
- Ciphertext must
*not*give clue about the plaintext.

- A cipher cannot offer more security than an exhaustive key search, therefore a cipher's key length (e.g., 128 bits) is its advertised security.
- We must select a cipher that is secure
__and__has a large enough keyspace.