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\)
There's Always More to Learn