CSCE 313 Lecture 25

« previous | Tuesday, April 24, 2012 | next »

Hash Algorithms

• Message digests, one-way transformation.
• Length of hashed value of message (usually fixed) is much shorter than length of message
• Easy to compute hash value
• Given the hash value, it is very difficult to find the original message
• Computationally infeasible to find two messages with the same hash value (collision)

Password Hashing

• Don't need to know password to verify it
• Store $h(p+s)$ where $s$ is the "salt" and compare it with the user-entered password
• Salt makes dictionary attack less convenient.

Message Integrity

• Agree on password $p$
• Compute $h(p+m)$ for a message $m$

Symmetric Encryption

The same key can be used to encrypt and decrypt: $E(k)$ can be derived from $D(k)$ and vice versa

EX: DES, AES, shift (caesar) cipher

Caeser Cipher

Select an alphabet $A$, a number $n$, and for each letter $l\in M$, compute $l+n{\pmod {\left|A\right|}}$

DES

1. start with 64-bit plaintext
2. permute order of plaintext (IP) using known permutation scheme
3. Perform 16 rounds of XOR substitution
4. permute order again (FP) to produce ciphertext

Asymmetric Encryption

Two different keys used to encrypt and decrypt message

RSA

$E(k_{e},N)$ is public key $D(k_{d},N)$ is private key $N$ is product of two large, randomly chosen prime numbers $p$ and $q$.

Example

1. Choose $p=7,q=13$
2. $N=7\cdot 13=91$ and $\phi =(p-1)(q-1)=72$
3. Select $k_{e}$ that is relatively prime to (and less than) 72, such as 5
4. Finally, we calculate $k_{d}$ such that $k_{e}k_{d}{\pmod {\phi }}=5k_{d}{\pmod {72}}=1$, yielding 29
5. Public key = (5, 91), private key = (29, 91)
6. Encrypting the message 69 with public key is 62: $69^{5}{\pmod {91}}=62$
7. Ciphertext is decoded with private key $62^{29}{\pmod {91}}=69$

Public key is transmitted in plain text to the world.

If someone wants to encrypt a message (or verify signature of message), then they use the public key.

The owner can decrypt (and sign) messages with his or her private key.

Comparison

Symmetric

based on simple transformation

Asymmetric

based on complex, computation-intensive math problems