What is the decryption function for an affine cipher if the encryption function is c = (15p + 13) mod 26?
The Correct Answer and Explanation is :
The Affine cipher encryption function is typically written as: c=(ap+b)mod mc = (ap + b) \mod m
where:
- cc is the ciphertext character,
- pp is the plaintext character,
- aa and bb are keys for the cipher (with aa being coprime to mm, which is the number of letters in the alphabet, usually 26 for the English alphabet),
- mm is the modulus (in this case, m=26m = 26 for the English alphabet).
Given that the encryption function is: c=(15p+13)mod 26c = (15p + 13) \mod 26
we can identify that:
- a=15a = 15,
- b=13b = 13,
- m=26m = 26.
To decrypt the message, we need to reverse the encryption process. The decryption function for the Affine cipher is: p=a−1(c−b)mod mp = a^{-1}(c – b) \mod m
where:
- pp is the plaintext character,
- a−1a^{-1} is the modular multiplicative inverse of aa modulo mm.
Step-by-Step Decryption Process
- Find the modular inverse of a=15a = 15 modulo 26: We need to find an integer a−1a^{-1} such that: 15a−1≡1mod 2615a^{-1} \equiv 1 \mod 26 To find the inverse, we can use the Extended Euclidean Algorithm.
- Solve for pp: Once we have a−1a^{-1}, we can substitute it, along with b=13b = 13 and the ciphertext cc, into the decryption formula.
Calculating the Modular Inverse of 15 Modulo 26
Using the Extended Euclidean Algorithm: 15⋅a−1≡1mod 2615 \cdot a^{-1} \equiv 1 \mod 26
The modular inverse of 15 modulo 26 is 7. (This is because 15×7=105≡1mod 2615 \times 7 = 105 \equiv 1 \mod 26).
Final Decryption Formula:
Now that we know the modular inverse of 15 is 7, we can substitute this value into the decryption formula: p=7(c−13)mod 26p = 7(c – 13) \mod 26
This function will decrypt any ciphertext generated using the encryption function c=(15p+13)mod 26c = (15p + 13) \mod 26.