Cryptography with Mathematica

Modular Arithmetic

Definition: Let m be any positive integer. We say that two integers a and b are congruent modulo m if b-a is divisible by m. In other words, the division of a by m gives the same remainder as the division of b by m. We write a=b (mod m), or a ≡ b (mod m), or a-b ≡ 0 (mod m).

Equivalence Relation:

reflexive:         a ≡ a (mod m)

symmetric:     if a ≡ b (mod m) then b ≡ a (mod m)

transitive:       if a ≡ b (mod m) and b ≡ c (mod m) then a ≡ c (mod m)

Division Principle: Let m be any positive integer. Let b be any integer. Then there exist unique numbers q and r such that b=qm+r, and 0 ≤ r < m. 
Smallest representative:  b ≡ r (mod m)  and we think of r as the simplest representative of the equivalence class of b modulo m.

The set of smallest representatives modulo m is denoted by (Subscript[ℤ, m])={0,1,2,3....,m-1}.

On (Subscript[ℤ, m]) we have two operations + (addition) and * (multiplication), with the following properties:

If a, b and c are integers and  a ≡ b (mod m), then a + c ≡ b + c (mod m)

If a, b, c, d are integers and  a ≡ b (mod m) and c ≡ d (mod m) then ac ≡ bd (mod m)

Special case: If a and b are integers and n is a positive integer, then (a^(n ))≡ (b^n) (mod m).

Multiplicative inverse

Definition:  A multiplicative inverse of an integer a modulo m is an integer b such that ab ≡ 1 (mod m). 
                   We write (a^(-1))≡ b (mod m).

Examples :

2*3 ≡ 6 ≡ 1 (mod 5), so (2^(-1))≡ 3 (mod 5) and (3^(-1))≡ 2 (mod 5)

2 is not invertible modulo 6. Suppose, by contradiction, that there exists a number x such that 2x ≡ 1 (mod 6), then 2x-1 is divisible by 6, so in particular 2x-1 is divisible by 2, which is false, because 2x-1 is odd.

Theorem: If  p⩾2 is a prime number, then any number a in {1,2,...p-1} has a multiplicative inverse in (Subscript[ℤ, p])

Theorem: Let m⩾2 be any positive number, and a be a number in {1,2,...m-1}. Then a has a multiplicative inverse in (Subscript[ℤ, m]) if and only if a and m are relatively prime.

Suppose that a and b are relatively prime, and let us consider the set of remainders:

a*0 (mod m), a*1 (mod m), a*2 (mod m), ... ,  a* (m-1) (mod m)

Notice that remainders are all distinct. Otherwise, suppose that a*i ≡ a*j (mod m) for some i and j with 0<i<j<m. Then a(j-i) ≡ 0 (mod m), a(j-i) is divisible by m. But a and m are relatively prime, so j-i must be divisible by m. However this is not possible, because 0<j-i<m.

In conclusion {a*0 (mod m), a*1 (mod m), a*2 (mod m), ... ,  a* (m-1) (mod m)} ={0,1,2,..., m-1}, so there exists a number k such that a*k ≡ 1 (mod m).

Suppose now that a*b ≡ 1 (mod m) and let us show that a and m must be relatively prime.

Suppose by contradiction, that a and m are not relatively prime and let a= (Subscript[a, 1])*c and m=(Subscript[m, 1])*c, where 1<(Subscript[m, 1])<m.

a*b ≡ 1 (mod m)  ⟹ (Subscript[a, 1])*c*b ≡ 1 (mod m)  ⟹ (Subscript[a, 1])*c*b*(Subscript[m, 1]) ≡ (Subscript[m, 1]) (mod m)

⟹ ((Subscript[a, 1])*b)*(c*(Subscript[m, 1])) ≡ (Subscript[m, 1]) (mod m)  ⟹  0 ≡ (Subscript[m, 1]) (mod m), which is false because (Subscript[m, 1]) is not divisible by m.

Modular Arithmetic in Mathematica

PowerMod[a,b,m] - gives (a^b)mod m.
PowerMod[a,-1,m] - finds the inverse of a modulo m; returns an error message “a is not invertible modulo m” is the integer a is not invertible modulo m.
PowerMod[a,1/r,m] - finds a modular r root of a.

PowerMod[3,-1,7]

PowerMod[3,-1,6]

Mathematica is able to solve modular equations using 
Solve[{List of Equations}, {List of Variables}, Modulus->m]

Solve[{3x ==1}, {x}, Modulus->7 ]

Solve[{2x == 1},{x}, Modulus->26]

Solve[{2x == 2},{x}, Modulus->26]

Affine ciphers

An Affine cipher is an enchipherment scheme of the form (Subscript[E, a,b])(x)=ax+b (mod 26) and (Subscript[D, a,b])(x)=(a^(-1))(x-b) (mod 26), where a and b are integer numbers between 0 and 25, and a and 26 must be relatively prime.

These are the admissible values for the first key (key a):

Select[Table[i,{i,25}],(GCD[26,#]==1)&]

An example of a good key : a = 3

Table[Mod[3*i,26], {i,0,25}]

An example of a bad key: a = 2

Table[Mod[2*i,26], {i,0,25}]

Remark: Note that when a = 1, the Affine Cipher is just the Caesar Cipher discussed in the last lecture

Euler's totient function ϕ(n)

Definition: 
The function ϕ(n) gives the number of positive integers less than or equal to n which are relatively prime to n.

Formula:  ϕ(n)=n*(1-(1/(Subscript[p, 1])))(1-(1/(Subscript[p, 2])))...(1-(1/(Subscript[p, k])))
                  where (Subscript[p, 1]),...(Subscript[p, k]) are all the prime divisors of n.

Mathematica function: 
EulerPhi[n] - computes Euler’s totient function ϕ(n).

Applications: 
Euler’s totient function ϕ(n) is widely used in Number Theory and also useful for a number of cryptographic protocols. For example, in the case of an Affine Cipher, we can use it to count the number of admissible values for the first parameter “a” of the key.

EulerPhi[26]

Encoding and Decoding of Affine Ciphers

Notice that each function is defined twice, on Integers and on Strings. You can use ?AffineEncode to see that Mathematica takes in both definitions, and it decides which one to apply based on the type of the input.

Clear[AffineEncode, AffineDecode]

AffineEncode[x_ ?IntegerQ, a_, b_]:= Mod[a*x+b,26]
AffineEncode[x_ ?StringQ, a_, b_]:= 
Module[{n,numerictext},
numerictext=ToCharacterCode[ToUpperCase[x]]-65;
numerictext = Select[numerictext, (0<=#≤25)&];
n = Mod[a*numerictext+b,26];
FromCharacterCode[n+65]
]

AffineDecode[x_ ?IntegerQ, a_, b_]:= Mod[PowerMod[a,-1,26]*(x-b),26]
AffineDecode[x_ ?StringQ, a_, b_]:= 
Module[{n,numerictext},
numerictext = ToCharacterCode[x]-65;
n = Mod[PowerMod[a,-1,26]*(numerictext-b),26];
FromCharacterCode[n+65]
]

Listable is an attribute that can be assigned to a function to indicate that the function should automatically be applied to lists that appear as its arguments. For example, Sin is listable, so Sin[{1, 2, 3, 4}] evaluates to {Sin[1], Sin[2], Sin[3], Sin[4]}

SetAttributes[AffineEncode, Listable];
SetAttributes[AffineDecode, Listable];

AffineEncode[3,5,1]
AffineDecode[16,5,1]
AffineEncode[{0,1,2,3,4,5},5,1]
AffineEncode["What to encode today?", 7, 11]
AffineDecode["JILOOFNYZFGNOFGLX", 7, 11]

Simple substitution/Monoalphabetic substitutions

Description: With the method of a simple substitution one chooses a fixed permutation p of the alphabet letters {a, b, …, z} and applies that permutation to all letters in the plaintext.

Encoding and Decoding functions:
E(x)= p(x)
D(x)= (p^(-1))(x)

Example:

Cipher = {"A"->"K", "B"->"E","E"->"Z",  "N"->"A",  "Z"->"C", "C"->"B", "K"->"N"}

DecodeA =  ("A" /. Cipher)->"A"

We can generate the English alphabet in several ways: from the ASCII codes, or by using the Mathematica function Alphabet[..].

alphabet = Table[FromCharacterCode[i],{i,65,65+25}]
alphabet=ToUpperCase @ Alphabet["English"]

Now we can display the backwards correspondence between the permuted (encrypted) alphabet and the original one.

DecodeCipher =  Table[(alphabet[[i]]/. Cipher)->alphabet[[i]],{i,1,26}]

Encoding and Decoding for Simple Substitution Ciphers

StringReplace[“string”,s->sp] or StringReplace[“string”,{s1->sp1,s2->sp2,…}]
replaces the string expressions s by sp  whenever they appear as substrings of string.

Clear[EncodeP, DecodeP]
EncodeP[x_]:=StringReplace[ToUpperCase[x], Cipher]
DecodeP[x_]:=StringReplace[ToUpperCase[x], DecodeCipher]

EncodeP["ANOTHER CIPHER"]

DecodeP["KAOTHZR BIPHZR"]

Cryptanalysis of Affine Ciphers:

a) By the method of a known ciphertext:

Exercise: Suppose that an affine cipher E(x) = ax+b (mod 26) enciphers “H” as “X” and “Q” as “Y”. Find the key. Then use the key to decode the ciphertext “HXAEAEICJJOLCGPSQPVJCAPHOTHCHHCIG”, which has been encoded using the same cipher.

Hint: Solve a system of two linear equations mod 26.

b) By exhaustive key search, or brute-force approach (try all possible keys):

The following text "KJJTZKLTVFMMLSVNULAUVIZFIVAIVQQXVFZX" has been encoded using an Affine Cipher. Decode the text.

c) By frequency analysis:

Exercise: Suppose that you have intercepted the following ciphertext “QNRVKVITSTIJVLVFPUTHVONVPGNWZVTGWQTWWQVPFPWVZXPPVHDIVNGWQVHNGWITIFAFPXZUSFHNDGWXGJWQVSVWWVICIVBDVGHXVPXGWQVHXUQVIWVYWTGOHNZUTIXGJWQVPVRXWQWQVSVWWVICIVBDVGHXVPNCWQVVGJSXPQTSUQTAVWNGVKVIFBDXHLSFCXGOPWQVXZTJVPDGOVIWQVUVIZDWTWXNGUNCWQVZNPWCIVBDVGWSVWWVIPXGWQVUSTXGWVYW”. 
You know that it has been encoded using an affine cipher, but you don' t know the key. Use frequency analysis to break the cipher.