Encryption

Encryption
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Encryption Terminology

Plaintext/Cleartext:
- Message in its original form
Ciphertext:
- An encrypted message
Encryption Algorithm:
- An algorithm that transforms a message in order to hide its meaning

Symmetric Key Encryption

Symmetric Key Encryption (cont.)

Some Classic Algorithms:
- Caesar Cipher - substitute each letter in the plaintext with the letter shifted a given number of places to the left or right
- Book Cipher - Replace each letter in the plaintext with three numbers; the page number, line number and character number in a given book
- Polygraphic Substitution Cipher - divide the plaintext into parts and replace each part with something else (e.g., a word, character, or number)
Some Modern (Computer-Based) Algorithms:
- Data Encryption Standard (DES) - 128, 192, or 256 bit
- International Data Encryption Algorithm (IDEA)
- Blowfish

Public Key Encryption

Public Key Encryption (cont.)

Motivating the Rivest-Shamir-Adelman (RSA) Algorithm

Encryption/Decryption as a Mapping/Inverse Mapping:
- If the mapping used for encryption can't be inverted then I can make the mapping public
- I then need a different mapping for decryption (that I must keep private)
Encryption:
- Convert the plaintext into a number (or numbers) that is less than a predetermined maximum \(n\) (e.g., using the ASCII codes)
- Multiply the number by itself \(e\) times and use the remainder after dividing by \(n\) as the cyphertext
Decryption:
- Multiply the cyphertext by itself \(d\) times, find the remainder after dividing by \(n\), and convert back to text

Public Key Encryption (cont.)

Creating Keys with the RSA Algorithm

Select two (large) prime numbers, \(p\) and \(q\)
- \(p=7\)
- \(q=17\)
Calculate \(n = p \cdot q \)
- \(n = 7 \cdot 17 = 119 \)
Find a number, \(e\), that is relatively prime (i.e., has no common divisors with) \((p-1)(q-1)\)
- \(e = 5\)
Find a number, \(d\), such that \(d \cdot e = 1 \mod (p-1)\cdot(q-1)\) (e.g., using the extended Euclidean algorithm)
- \(d = 77\)
\(e\) and \(n\) are the public key and \(d\) is the private key

Public Key Encryption (cont.)

RSA Example

Encryption (\(C = P^e \mod n\)):
- Suppose \(P = 19\)
- Then \(C = 19^5 \mod 119 = 66\)
Decryption (\(P = C^d \mod n\)):
- Suppose \(C = 66\)
- Then \(M = 66^{77} \mod 119 = 19\)