Private-Key Encryption « PD4CS - Python programming, common student misconceptions, student projects

Private- or symmetric-key encryption schemes are intuitive ciphers your students may have heard about. These ciphers depend upon a shared secret key. For example, if Alice and Bob are using an encryption system to communicate, they both have to know the secret key. That way, Alice can encipher a message with the key, and Bob can decipher it with the same key. Then Bob can encipher a message with the key, and Alice can decipher it. And so on. But how do Alice and Bob share the key in the first place? What if Alice lives in California and Bob lives in New York? There must be a secure way in which they can share the secret key before being able to use it. Ask your students how they think Alice and Bob should share their secret key and discuss difficulties that might come up.

The following are some examples of symmetric-key encryption systems. Although most of them are considered insecure and are not used for security purposes today, the ideas behind them are fundamental to modern private-key encryption.

Caesar Ciphers

Substitution Ciphers

A substitution cipher is much like the cryptogram puzzle found in the Sunday newspaper. It might be a fun activity to have students try to solve a cryptogram and discuss strategies. In that puzzle, the user attempts to guess which one-to-one encoding exists between letters. There is no order, so it is all based on patterns that the code-breaker can find. General strategies for decoding a substitution cipher involve looking for common word-patterns like “the” and “and”. Another strategy to solve this problem involves attempting to match frequently used letters with the most common letters in the ciphertext. This is called frequency analysis, and a discussion can be found at https://en.wikipedia.org/wiki/Frequency_analysis. A sample encoding is shown below.Key: A=M, B=E, C=Q, D=P, E=Z, F=N, G=R, H=B, I=F, J=U, K=W, L=C, M=O, N=L, O=K, P=I, Q=A, R=S, S=J, T=H, U=Y, V=G, W=T, X=V, Y=D, Z=X

Encoding the plaintext “PROGRAMMING IS FUN” yields the ciphertext “ISKRSMOOFLR FJ NYL”.

Note that the key is a permutation of the alphabet, which means that there are 26! possibilities (assuming that a letter can be encoded as itself.) This is far too many to test with modern computing capabilities, so a brute-force attack is not reasonable. However, this kind of encryption is still not secure. Consider how many people solve cryptograms in newspapers every day! This is because there are other strategies used in solving them. In this system, patterns in the plaintext are preserved in the ciphertext. A simple substitution cipher can be broken by looking for common patterns in the ciphertext and by using frequency analysis.

This programming assignment could be attempted once the students have worked with lists. The common pattern for frequency of letters in the alphabet can be used to put the letters in order from most frequent to least frequent. Then the computer can make a first guess at decrypting the message by fitting letters based on frequency in the ciphertext. Then the student can create a mechanism for swapping two letters in the decrypted pattern.

If you are familiar with Java, the following programs may be useful as simulations the substitution cipher and frequency analysis:

Cryptogram.java: turns plaintext into ciphertext using a simple substitution cipher.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class Cryptogram {
//instance variables
static final Character[] alpha = {‘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’};
private ArrayList<Character> alphabet;
private ArrayList<Character> key;
private Random gen;

public Cryptogram() {
alphabet = new ArrayList<Character>(Arrays.asList(alpha));
key = new ArrayList<Character>();
gen = new Random();
while(alphabet.size() > 0) {
int i = gen.nextInt(alphabet.size());
int index = Arrays.binarySearch(alpha, alphabet.get(i));
while(index == key.size()) {
i = gen.nextInt(alphabet.size());
index = Arrays.binarySearch(alpha, alphabet.get(i));
}
key.add(alphabet.remove(i));
}
}

public void changeKey() {
alphabet = new ArrayList<Character>(Arrays.asList(alpha));
key = new ArrayList<Character>();
while(alphabet.size() > 0) {
int i = gen.nextInt(alphabet.size());
key.add(alphabet.remove(i));
}
}

public String encipher(String message) {
String newMsg = “”;
message = message.toUpperCase();
int index = -1;
for(int i = 0; i < message.length(); i++) {
index = Arrays.binarySearch(alpha, message.charAt(i));
if(index != -1)
newMsg += key.get(index);
else
newMsg += message.charAt(i);
}
return newMsg;
}

/* main method */
public static void main(String[] args) {
Cryptogram c = new Cryptogram();
Scanner in = new Scanner(System.in);
System.out.println(“Enter a message to encipher: “);
String msg = in.nextLine();
while(!in.nextLine().equals(“END”)) {
msg += in.nextLine();
}
System.out.println(msg.toUpperCase() + “\n”);
String ct = c.encipher(msg);
System.out.println(ct);
}
}

CryptogramSolver.java: helps turn ciphertext into plaintext using frequency analysis.

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Scanner;

public class CryptogramSolver {
static final char[] alpha = {‘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’};
//instance variables
private String ciphertext;
private char[] key = {‘Z’, ‘Q’, ‘X’, ‘J’, ‘K’, ‘V’, ‘B’, ‘P’, ‘Y’, ‘G’, ‘F’, ‘W’, ‘M’, ‘U’, ‘C’, ‘L’, ‘D’, ‘R’, ‘H’, ‘S’, ‘N’, ‘I’, ‘O’, ‘A’, ‘T’, ‘E’};
private CharCount[] counts;

//constructor
public CryptogramSolver(String s) {
this.ciphertext = s.toUpperCase();
counts = new CharCount[26];
for(int i = 0; i < counts.length; i++) {
counts[i] = new CharCount(alpha[i], 0, true);
}
//count frequencies of letters in message
for(int i = 0; i < ciphertext.length(); i++) {
int index = -1;
index = Arrays.binarySearch(alpha, ciphertext.charAt(i));
if(index != -1) {
counts[index].increase();
}
}
Arrays.sort(counts);//ascending order
//this.printKey();
}

public String solve() {
String result = “”;
int index = -1;
for(int i = 0; i < ciphertext.length(); i++) {
index = this.find(ciphertext.charAt(i));
if(index != -1) {
result += key[index];
}
else
result += ciphertext.charAt(i);
}
//this.printKey();
return result;
}

public void setKey(char cipher, char plain) {
int index1 = this.find(cipher); //index of char to be changed
char temp = key[index1]; //value of char to be changed
int index2 = this.find(key, plain); //index of new char
key[index1] = plain;
key[index2] = temp;
//this.printKey();
}

public String getCipherText() {
return ciphertext;
}

private int find(char[] array, char c) {
for(int i = 0; i < array.length; i++) {
if(array[i] == c)
return i;
}
return -1;
}

private int find(char c) {
for(int i = 0; i < counts.length; i++) {
if(counts[i].getLetter() == c)
return i;
}
return -1;
}

private void printKey() {
for(int i = 0; i < counts.length; i++) {
System.out.print(counts[i].getLetter() + “: ” + key[i] + “\t”);
}
System.out.println();
}

/* main method */
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println(“Enter a cryptogram to solve: “);
String ct = in.nextLine();
System.out.println(ct.toUpperCase() + “\n”);
CryptogramSolver cgs = new CryptogramSolver(ct);
System.out.println(cgs.solve());
System.out.println(“Enter a letter to re-map or \”done\”: “);
String input = in.nextLine();
while(!input.equals(“done”)) {
char one = input.toUpperCase().charAt(0);
System.out.println(“Enter the new key for the given letter: “);
input = in.nextLine();
char two = input.toUpperCase().charAt(0);
cgs.setKey(one, two);
System.out.println(ct + “\n”);
System.out.println(cgs.solve() + “\n”);
System.out.println(“Enter a letter to re-map or \”done\”: “);
input = in.nextLine();
}
}
}

CryptoTester.java: tests some functionalities of Cryptogram and CryptogramSolver.

Vigenère Cipher

Some cipher systems (e.g., Ceasar and Substitution ciphers) preserve the patterns from the plaintext in the ciphertext. This makes them vulnerable as a letter in the plaintext is ALWAYS ENCRYPTED THE SAME WAY (e.g., ‘A’ always equals ‘M’).Consider an encryption system in which the plaintext was encoded in much the same way as a rotation cipher, but the key isn’t always the same. The word “AND”, then, might be encoded as “BOE” in one instance and as “ZMC” in another instance, making it much more difficult to find patterns. This is the idea behind the Vigenére cipher, which is also known as a polyalphabetic rotation cipher. For example, consider the following cipher using the key SIMPLE. The letters of the plaintext are encrypted by adding each letter of the key in a cycle: PROGRAMMINGISFUN + SIMPLESIMPLESIMP = HZAVCEEUUCRMKNGC. Note that each individual letter is encrypted the same as the rotation cipher (e.g., P –> (15 + 18) % 26 = 33 % 26 = 7 –> H).

The method of using a key that changes helps to mask the patterns in the plaintext. For example, the “MM” becomes “EU”, the “AM” becomes “EE” and the “MI” becomes “UU”. Patterns that exist in the plaintext do not exist in the ciphertext and vice versa. A given letter is not always encrypted the same way. This makes it much more difficult to apply the strategies, such as frequency analysis, and for many years, the Vigenére cipher was considered unbreakable.

Then, a man named Kasiski figured out a method for breaking the cipher. First, he analysed the ciphertext to find repeated patterns. Then, he figured out how far apart those patterns were. Then, he found the greatest common factor of those distances, and treated that as the length of the key. Once the length of the key is known (or guessed), it is possible to apply frequency analysis multiple times. To read more about the Vigenére cipher, including methods for breaking it, see https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher

If you are familiar with Java, the following program may be helpful as a simulation to show how the Vigenére cipher works.

Vigenere.java

import java.util.Random;
import java.util.Arrays;
import java.util.ArrayList;

public class Vigenere {
/* global variables */
static final char[] alpha = {‘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’};

/* instance variables */
private String key;
private int[] keyNums;

/* constructors */
public Vigenere(String key) {
this.key = key.toUpperCase();
this.setKeyArray();
//for(int num: keyNums)
//System.out.println(num);
}

//creates new instance with random key of given length
public Vigenere(int length) {
Random gen = new Random();
this.key = “”;
int index;
for(int i = 0; i < length; i++) {
index = gen.nextInt(alpha.length);
this.key += alpha[index];
}
this.setKeyArray();
}

//creates a new instance with random key of random length given the min and max length
public Vigenere(int min, int max) {
Random gen = new Random();
int length = min – 1 + gen.nextInt(max – min);
this.key = “”;
int index;
for(int i = 0; i < length; i++) {
index = gen.nextInt(alpha.length);
this.key += alpha[index];
}
this.setKeyArray();
}

/* public methods */
public String encipher(String msg) {
msg = msg.toUpperCase();
String res = “”;
int j = 0; //System.out.println(msg.length());
for(int i = 0; i < msg.length(); i++) {
int index = Arrays.binarySearch(alpha, msg.charAt(i)); //System.out.println(index);
if(index >= 0) {
index = (index + keyNums[j]) % 26; //System.out.println(keyNums[j] + “\t” + index);
res += alpha[index];
j++;
if(j == keyNums.length)
j = 0;
}
else
res += msg.charAt(i);
}
return res;
}

public String decipher(String msg) {
msg = msg.toUpperCase();
String res = “”;
int j = 0;
for(int i = 0; i < msg.length(); i++) {
int index = Arrays.binarySearch(alpha, msg.charAt(i));
if(index >= 0) {
index = (index – keyNums[j]) % 26;
if(index < 0)
index = 26 + index;
res += alpha[index];
j++;
if(j == keyNums.length)
j = 0;
}
else
res += msg.charAt(i);
}
return res;
}

/* private method */
private void setKeyArray() {
char c = ‘-‘;
int[] temp = new int[key.length()];
int index = -1;
int count = 0;
for(int i = 0; i < key.length(); i++) {
c = key.charAt(i);
index = Arrays.binarySearch(alpha, c);
if(index != -1)
count++;
temp[i] = index;
}
keyNums = new int[count];
int j = 0;
for(int i = 0; i < temp.length; i++) {
if(temp[i] != -1) {
keyNums[j] = temp[i];
j++;
}
}
}
}

One-time Pads

The Enigma Machine

Current private-key encryption systems

Stream and Block Ciphers