CSC 440, Notes from synchronous Zoom session, January 7th
Introduction
This presentation was meant to introduce some of the mathematics used to analyze and understand cryptosystems. This connection is a consistent theme throughout the course.
We begin with integer groups, a concept from the field of abstract algebra. We tie these objects to each of three ciphersystems:
– Shift ciphers
– Decimation ciphers
– Affine ciphers
Additive groups and shift ciphers
The additive group on 𝑛 elements, denoted Z+, is defined by: 𝑛
– The set of non-negative integers: {0, 1, 2, 3, … , 𝑛 − 1}
– The group operation (addition): +𝑛
The group operation is defined as follows. Given two elements in the set 𝑎, 𝑏 define:
𝑎+𝑛𝑏 = (𝑎 + 𝑏) 𝑚𝑜𝑑 𝑛
The plus on the right is the usual arithmetic addition. The additive identity element is 0:
𝑎+𝑛0 = 𝑎
The additive inverse of 𝑎, written −𝑎, is the element 𝑏 such that:
𝑎+𝑛𝑏 = 0
This provides a mathematical way of presenting the shift cipher, which encrypts plaintexts written in the 26-letter Roman alphabet, where each letter is assigned a code between 0 and 25 (a = 0, b = 1, and so
forth). We can characterize how it works based on the group Z+ . 26
CSC 440, Notes from synchronous Zoom session, January 7th
Encryption of the plaintext value 𝑥 with the key 𝑘 is defined by the equation:
𝑥 +26 𝑘 = 𝑦
Decryption of the ciphertext value 𝑦 with the key 𝑘 is defined by: 𝑦 +26 (−𝑘) = 𝑥
Multiplicative groups and decimation ciphers
The multiplicative group on 𝑛 elements, denoted Z⋅ , is defined by: 𝑛
– The set of non-negative integers: {0, 1, 2, 3, … , 𝑛 − 1}
– The group operation (multiplication): ⋅𝑛
The group operation is defined as follows. Given two elements in the set 𝑎, 𝑏 define:
𝑎 ⋅𝑛 𝑏 = (𝑎 ⋅ 𝑏) 𝑚𝑜𝑑 𝑛
The multiplication on the right is the usual multiplication. The multiplicative identity element is 1:
𝑎 ⋅𝑛 1 = 𝑎
The multiplicative inverse of 𝑎, written 𝑎−1, is the element 𝑏 such that:
𝑎 ⋅𝑛 𝑏 = 1
As above, this provides a mathematical way of understanding the
decimation cipher on the Roman alphabet as based on the group Z⋅ . 26
Encryption of the plaintext value 𝑥 with the key 𝑘 is: 𝑥⋅26 𝑘=𝑦
CSC 440, Notes from synchronous Zoom session, January 7th
Decryption of the ciphertext value 𝑦 with the key 𝑘 𝑖𝑠:
𝑦⋅26 𝑘−1=𝑥
Multiplicative inverses
How does one find the multiplicative inverse of a value 𝑎 in a group Z⋅ ? 𝑛
First, we need to see that it might be that not every element has a multiplicative inverse. Which ones do depend on 𝑛.
Theorem. An element 𝑎 in Z⋅ has a multiplicative inverse 𝑛
iff gcd(𝑛, 𝑎) = 1.
We won’t prove the theorem here.
When 𝑔𝑐𝑑(𝑛, 𝑎) = 1, we sometimes say that “𝑛 and 𝑎 are relatively prime or coprime”.
The greatest common divisor (gcd) is the largest value 𝑔 that divides both 𝑎 and 𝑛. For example,
– gcd(25,5) = 5
– gcd(25,10) = 5
– gcd(25,4) = 1
– gcd(20,12) = 4
– gcd(20,15) = 5
– gcd(20,6) = 2
– gcd(20,9) = 1
We calculate the gcd using the Euclidean algorithm (Java version):
public int gcd(int a, int b) {
if (b == 0) return a;
else return gcd(b, a % b);
}
CSC 440, Notes from synchronous Zoom session, January 7th
Considering the group Z⋅ 26
multiplicative inverses.
𝑎 𝑎−1
11 39 5 21 7 15
9
11 19
15 7
17 23
19 11
21 5
23 17
25 26
, the table below lists its elements that have
3
You can check that the entries are correct by multiplying each 𝑎 by its inverse, taking it mod 26, and seeing that the result is 1. The values not in the table each have a gcd with 26 that is greater than 1.
Both groups and affine ciphers
The affine cipher is based on both the additive and the multiplicative group operations. As above, fixing Z+ , Z⋅ as the groups of interest,
we define encryption in an affine cipher with a key having two elements from the groups 𝛼, 𝛽:
𝑦=𝛼⋅26 𝑥+26𝛽
As expected, the multiplication is performed first and then the addition.
26 26
CSC 440, Notes from synchronous Zoom session, January 7th
Decryption requires the reverse of encryption in that the inverse of the addition is performed first followed by the inverse of the multiplication:
𝑥=(𝑦+26(−𝛽))⋅26 𝛼−1