On the Subject of the RSA Cipher

Hill Cipher 2.0

A 6 letter word has been encrypted in to 6 numbers in the middle of the screen. Submit this word to disarm the module.

Above these 6 numbers are 2 more numbers labeled N and E. Below that is a flashing cursor that will input anything you type with the keyboard up to 6 letters. The green circular button will submit your input while the red circular button will clear all input made.

Follow the instructions below to get your decrypted word.

Step 1: Get λ(N)

First thing to do is to figure out the 2 prime numbers that were multiplied together to get N. Below is the list of primes used in this module:

11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Once, you figure out the 2 primes, then calculate λ(N) using the equation below:

λ(N) = ((P1 - 1) * (P2 - 1)) / GCD(P1 - 1, P2 - 1)

The Greatest Common Denominator (GCD) between 2 numbers can be found using these set of instructions:

1. Take the greater of the 2 numbers and modulo it by the smaller number.
2. Then take the right number of the previous operation and modulo it by the result of the previous step.
3. Repeat step 2 until the result is 0.
4. The right number of the operation when the result is 0 is the GCD of the 2 numbers.

Example

N = 1643
P1 = 31
P2 = 53

Calculating GCD
52 % 30 = 22
30 % 22 = 8
22 % 8 = 6
8 % 6 = 2
6 % 2 = 0
GCD(52, 30) = 2

λ(N) = (52 * 30) / 2 = 780

Step 2: Get D

To calculate for D, you’ll be using an Extended Euclidean algorithm that is instructed below:

1. Set up 7 variables labeled A, B, Q, R, T1, T2, and T3
2. Set A equal to λ(N).
3. Set B equal to E.
4. Q is equal to A / B, rounded down.
5. R is equal to A % B.
6. Set T1 equal to 0.
7. Set T2 equal to 1.
8. T3 is equal to T1 - (T2 * Q).
9. Set A equal to B.
10. Set B equal to R.
11. Q is equal to A / B, rounded down.
12. R is equal to A % B.
13. Set T1 equal to T2.
14. Set T2 equal to T3.
15. T3 is equal to T1 - (T2 * Q).
16. Repeat steps 9 - 15 until R is equal to 0.
17. If you stopped at step 12, then D is equal to T3 % λ(N). Otherwise if you stopped at step 15, then D is equal to T2 % λ(N).

If everything was done correctly, then the product of D and E, modulo λ(N), should equal 1.

Example

λ(N) = 780
E = 347

A	B	Q	R	T1	T2	T3
780	347	2	86	0	1	-2
347	86	4	3	1	-2	9
86	3	28	2	-2	9	-254
3	2	1	1	9	-254	263
2	1	2	0	-254	263	-780

D = 263 % 780 = 263

Step 3: Decrypting the Numbers.

The 6 numbers are read in reading order. For each number (C), do the following operation:

(C^D % N) - 1 = P

Turn P into a letter, treating it as if it was a letter’s alphabetic position.

After decrypting and turning each number into a letter, you should have a decrypted word.

Example

Encrypted Numbers: 1622 1247 1012 283 2 1018
D = 263
N = 1643

(1622²⁶³ % 1643) - 1 = 13 -> M
(1247²⁶³ % 1643) - 1 = 9 -> I
(1012²⁶³ % 1643) - 1 = 18 -> R
(283²⁶³ % 1643) - 1 = 1 -> A
(2²⁶³ % 1643) - 1 = 7 -> G
(1018²⁶³ % 1643) - 1 = 5 -> E
Decrypted Word: MIRAGE