MAT 331: Homework 4

Problem 4.1

Let n be a positive integer. Euler’s totient function ϕ(n) gives the number of positive integers less than or equal to n which are relatively prime to n.  In this exercise you will prove that ϕ is given by the 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. The following steps should be useful:

If p is a prime number, then ϕ(p)=p-1.

If p is a prime number and k is a positive integer, then ϕ((p^k))=(p^k)-(p^(k-1)).

If m and If n are relatively prime to each other, then ϕ(mn) = ϕ(m)ϕ(n).

Use the previous steps to prove the general formula for ϕ(n).

The plot below shows the first 150 values of the function ϕ. Can you use the graph (and the previous steps) to identify the numbers n where the function attains a “local maximum”? Use your observations to prove that  (Underscript[limsup, n→∞])((ϕ(n))/n)=1.

DiscretePlot[EulerPhi[k],{k,150}]

One should not understand from part 5 that (lim_(n→∞))((ϕ(n))/n)=1. In fact Schinzel and Sierpiński showed that the set S={((ϕ(n))/n),n=1,2,3,...} is dense in the interval [0,1]. In particular, (Underscript[liminf, n→∞])((ϕ(n))/n)=0. Give evidence of this density result by plotting the set S for the first 100,1000 and 10000 positive integer numbers. Choose the appropriate plotting functions!

Problem 4.2

Consider an affine cipher (Subscript[E, a,b])(x)=ax+b (mod 26), where a and b are integer numbers between 0 and 25, and a and 26 are relatively prime.

a) Encoding/Decoding

Assume that the key is {a,b}={3,7}. Encode the text “Summer is coming”. Decode the following text “MCFJCXRTVXGLFJMCTOHJMCXRTVXGLHJJFZURTUMXWMCTNXPGJTVTVFOOXUOBCHSTXUTRXGTAGXITNM”

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

What is the dimension of the key space of an Affine Cipher? The following text “APQPKHPMMFVYOSDQLDDQACYDVSKWZMZDMZKHZQKFYPJMRPMZSZKKZMLVQKWZDSOWDCZK” has been encoded using an Affine Cipher. Decode the text.

Hint: After you generate all possible decodings, the Wolfram function LanguageIdentify[...] might help you narrow down the search.

c) Cryptanalysis by the method of a known ciphertext:

Suppose that an affine cipher E(x) = ax+b (mod 26) enciphers “J” as “S” and “M” as “B” and “W” as “F”. Find the key. Do you need to use all three known ciphertexts to break the cipher? Use the key to decode the ciphertext  
“PGLHZXREQDRAWMPTPWBDRETWMRWLHZMRCDADXHADAWMDWDIW”, 
which has been encoded using the same cipher.

Hint: Solve a system of linear equations modulo 26.

d) Cryptanalysis by frequency analysis:

Suppose that you have intercepted the following ciphertext 
“ZVDFVQZLMWDQFVSSLIDZLMWDQFMDQTJUVULXIZLMWDQFFLTMEDTXIXVEMWVKDULZFJKFULUJULXIZLMWDQFVQDIXUFDZJQDJIELPDZVDFVQFZLMWDQVMDQTJUVULXIZLMWDQOXDFIXUWVYDUWDOQVNKVZPXSVFTVEEPDRFMVZDWVYLIHVEVQHDPDRFMVZDOXDFIXUTDVIUWVUUWDFRFUDTLFFDZJQDXIUWDZXIUQVQRKRFLTMERZXJIULIHUWDEDUUDQSQDBJDIZLDFLIUWDZLMWDQUDCUVIOZXTMVQLIHUWDFDNLUWUWDEDUUDQSQDBJDIZLDFXSUWDDIHELFWVEMWVKDUXIDYDQRBJLZPERSLIOFUWDLTVHDFJIODQUWDMDQTJUVULXIMXSUWDTXFUSQDBJDIUEDUUDQFLIUWDMEVLIUDCU”.
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.

Hint: The frequencies of the letters in the English alphabet are given below:

T={"A"-> 0.0804, "B"-> 0.0154, "C"->0.0306, "D"->0.0399, "E"->0.1251, "F"->0.0230, "G"->0.0196, "H"->0.0549, "I"->0.0726, "J"->0.0016, "K"->0.0067, "L"->0.0414, "M"->0.0253,"N"->0.0709,"O"->0.0760,"P"->0.0200, "Q"->0.0011,"R"->0.0612, "S"->0.0654, "T"->0.0925, "U"->0.0271, "V"->0.0099, "W"->0.0192, "X"->0.0019, "Y"->0.0173, "Z"->0.0009};
TA=Association[T];
Sort[TA]