Topic of Contents:
- Introduction to the Affine Cipher
- Keys Generation for Affine Cipher
- Understanding the Greatest Common Divisor (GCD)
- Exploring Co-prime Numbers
- Affine Cipher First Key Cheat Sheet
- Mathematical Operations behind Affine Cipher
- Example of Affine Cipher Encryption Process
- Conclusion
Introduction to Affine Cipher
The Affine cipher belongs to a category of substitution ciphers where each letter is replaced with another letter based on a fixed mathematical rule. Unlike the more famous Caesar cipher, which shifts each letter in plaintext by a fixed three number of positions, Affine cipher employs three mathematical operations: multiplication, addition, and modulo operation (modular arithmetic). These operations help create a unique and customizable encryption scheme.
The formula for the Affine Cipher encryption is:
| E(x) = (a.x + b) mod m | |
|---|---|
| E(x) | Denotes an Encryption of the x alphabetical index |
| a | An index value of the “special” first key |
| x | An index value of the plain letter |
| b | An index value of the second key (additional shift value) |
| mod m | The modulo operations of the total amount of the alphabet which is 26 |
Keys Generation for Affine Cipher
Choosing the “a” and “b” keys requires special consideration. Generating the first key should follow one condition. “A” should be a co-prime integer with a value of the modulo operation that is required within the equation which is the alphabet size (26 for English letters). While “b” should be within the [0, 25] range. Now, you might ask what is the co-prime number. Before answering that, let’s learn the concept that underlies the term “co-prime”, namely the greatest common divisor (GCD).
The Greatest Common Divisor (GCD)
The Greatest Common Divisor (GCD) of multiple integers is the largest positive number that can divide all of them evenly, leaving no remainder. In simpler words, it’s the largest number that divides these integers without fractions or remainders. For example, what is the GCD of integers 8 and 6? The mathematical expression is denoted as GCD(8,6).
To answer the question, let’s break down the GCD term into three parts: greatest, common, and divisor. Let’s start from the last to the beginning.
Alt-image & caption: Dividend, Divisor, and Quotient
1. Divisor
To answer the question about GCD(8,6), let us first identify what are the positive integers that could be a divisor without leaving a remainder, starting from 1 to its dividend number. We have two dividend numbers which are 8 and 6.
Alt-image & caption: Divisor
Alt-image & caption: Divisor
Now, we eliminate the non-integer quotient. The result is as follows:
Alt-image & caption: Integer Quotient
Now, we have a whole number divisor that only produces an integer quotient. They are:
8 = 1, 2, 4, 8
6 = 1, 2, 3, 6
2. Common Divisor
Once we get the divisor numbers for each dividend, we identify which are the share common divisor numbers.
Alt-image & caption:The Common Divisors
Their common divisors are 1 and 2.
3. The Greatest Common Divisor
Finally, after we find the common divisors, we then identify which is the greatest common divisor among 1 and 2. Certainly, it is number 2.
Alt-image & caption: The Greatest Common Divisor
So, the GCD(8,6) is equal to 2. Easy, right?
Co-Prime Number
Co-prime numbers (relatively prime numbers) are a pair of two or more numbers that have only 1 as their greatest common divisor (GCD). In other words, when a pair number is co-prime, they have no other common factors (divisors) except for 1. In a mathematical equation, it is expressed as GCD(x,y) = 1.
In the generation of the first key that is used in the Affine cipher, “a” should be a co-prime integer with 26 which means that it shares no common factors other than 1 with 26. In a mathematical equation, it is expressed as GCD(a,m) = 1 where “a” is the first key and “m” represents the mod value (26).
For example, let’s analyze whether the number “5” could meet the criteria to be the first key or not. Now, calculate the result of GCD(5,26).
Alt-image & caption: Co-Prime Number
From the previous table, we can see that GCD(5,26) = 1. This means that “a” has no other shared common divisor with a mod value (26) other than “1”. So, the number “5” met the criteria to be the first key.
Affine Cipher First Key Cheat Sheet
Since the first key which is “a” should meet the criteria where GDC(a,m) = 1, there would be limited numbers. Here are the numbers that could be used for the first key:
Alt-image & caption: Affine Cipher First Keys List
Take a look for a moment. Can you catch the point from that list of numbers? It is the Affine cipher first key, “a”, that can only be an odd number from 1 to 26, excluding 13. Take note of that. Why is 13 excluded even if it is an odd number? Because GCD(13,26) is 13, not 1.
Mathematical Operations Behind Affine Cipher
Affine cipher relies on three primary mathematical operations: multiplication, shift addition, and modular arithmetic. The modulo operation in the formula ensures that the result remains within the bounds of the alphabet which has 26 letters. This step is crucial because it prevents the encryption from going out of the valid character range.
Alt-image & caption: Affine Cipher Equation
Let’s jump into an example. We want to encrypt the “LINUXHINT” plaintext with the keys 7 and 13. First, convert each plain letter into the corresponding index value. Here is the table:
Alt-image & caption: Index Numbering
The “LINUXHINT” plaintext is converted into an index value to “11 8 13 20 23 7 8 13 19”.
Alt-image & caption: Convert a Plaintext into an Index Numbering Value
Based on the equation, the generated value is:
| (a.x + b) mod m | |
|---|---|
| a | 7 |
| x | (11, 8, 13, 20, 23, 7, 8, 13, 19) |
| b | 13 |
| mod m | 26 |
Then, let’s apply the equation calculation. Remember these sequence steps: multiplication, addition, and modulo arithmetic. Here is the result:
Alt-image & caption: Affine Ciphering Calculation Steps
The last step is to produce the ciphertext by converting the equation result back into its corresponding alphabet using the previous index value table. The cipher index values of “12 17 0 23 18 10 17 0 16” are converted into cipher text to:
Alt-image & caption: Affine Ciphertext
So, the “LINUXHINT” plaintext is encrypted using Affine Cipher with keys 7 and 13, resulting in “MRAXSKRAQ”.
Conclusion
In conclusion, Affine cipher presents a robust encryption technique that goes beyond the simplistic approach of the Caesar cipher, employing a more complex mathematical model involving multiplication, addition, and modular arithmetic. The key generation process necessitates a careful consideration, ensuring that the first key (“a”) is a co-prime integer with the specified modulo value, while the second key (“b”) falls within the range of 0 to 25. The co-prime numbers play a vital role in this context as they only have 1 as their greatest common divisor, thereby emphasizing the importance of the GCD concept.
Affine cipher’s reliance on mathematical operations, particularly the modulo operation, safeguards the encryption process from exceeding the constraints of the 26-letter English alphabet. Furthermore, the cipher’s encryption process involves several steps including converting the plaintext into index values, applying the encryption equation, and eventually converting the resulting index values back into the corresponding ciphertext. By adhering to these principles, Affine cipher successfully encrypts the plaintext such as “LINUXHINT” into the “MRAXSKRAQ” ciphertext using the keys 7 and 13.
Frequently Asked Questions (FAQs)
Q1: What are the key considerations when generating keys for the Affine cipher?
A1: The key considerations for generating keys in Affine cipher involve selecting a co-prime integer “a” with the modulo value and ensuring that the additional shift value of “b” falls within the range of 0 to 25.
Q2: How is the Greatest Common Divisor (GCD) calculated in the context of the Affine cipher?
A2: The Greatest Common Divisor (GCD) is calculated as the largest positive integer that divides two or more numbers without leaving a remainder. In the context of the Affine cipher, it helps determine whether two numbers are co-prime
Q3: What role do co-prime numbers play in the Affine cipher encryption process?
A3: Co-prime numbers are crucial in the Affine cipher’s encryption process as they only have 1 as their greatest common divisor.
Q4: What are the primary mathematical operations involved in the Affine cipher?
A4: The primary mathematical operations involved in the Affine cipher include multiplication, shift addition, and modular arithmetic. These operations work together to ensure that the encryption process stays within the bounds of the 26-letter English alphabet, maintaining the security of the encryption.
