1. A generalization of the Caesar cipher, known as the Affine cipher, has the fo

Question

1. A generalization of the Caesar cipher, known as the Affine cipher, has the following form: Assume that the alphabet is {a, b, …, z} and that a = 0, b = 1, …, z = 25. The key is a pair, K = {a, b} where 0 a 25 and 0 b 25, the plaintext P = p1p2 … pn is encrypted one character at a time to get the ciphertext C = c1c2 … cn. For each plaintext letter p, substitute the ciphertext c where c = E(p) = (ap + b) mod 26. To encrypt p just multiply p by a then add b and mod this by 26. A basic requirement of any encryption algorithm is that it be a one-to-one function. So the encryption of two different plaintext messages will not result in the same ciphertext. Otherwise decryption would be impossible.

a. Prove that, for all key values of K = {a, b}, the affine cipher is not a one-to-one function. Find a key and two plaintexts that give a collision.

b. I claim that if (a mod 26) has an inverse, that means that there is a value a-1 so that (aa-1) mod 26 = 1, then encryption will be 1-1. Find a “good” value for a and show that it gives a 1-1 mapping.

Explanation / Answer

SOLUTION

A : Proof by contradictory example

Let the key be {2,3} where a = 2, b = 3 then cipher text for plain text a (i.e. 0) and n (i.e. 13) is both d (i.e. 3).

c = E({a,b},p) = E({2,3},0) = ( 2 x 0 + 3 ) mod 26 = 3

= E({2,3},13) = ( 2 x 13 + 3 ) mod 26 = 3

So, a collision between plain text a,n can be seen when using key {a,b} = {2,3}.

B : The good values of 'a' for which the function is one to one are such that the values of a and 26 have no common integer factor other than 1 i.e. similar to saying they are relatively prime or their greatest common divisor is 1.

Case 1 : If they are Relatively prime

E(a, p) = E(a, q) such that (0<p<q<26) if and only if a(p - q) is divisible by 26.

Then, a(p - q) is not divisible by 26, because there is no way to reduce the fraction a/26 and (p - q) is less than 26.

Case 2 : If they have a common factor k >1

Then E(a, p) = E(a, q), if q = p + m/ k such that (k not equal to p).

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.