On the Subject of the RSA CM

A machine that knows no bounds when it comes to ciphers.

Determining N & E

The numbers on screen A (N) and B (E) have been encrypted through a series of modular exponentiation. To decrypt it, take each letter of the encrypted word and convert it to a number using the table below:

A	B	C	D	E	F	G	H	I	J	K	L	M
7	11	13	17	19	23	29	31	37	41	43	47	49
N	O	P	Q	R	S	T	U	V	W	X	Y	Z
53	59	61	67	71	73	77	79	83	89	91	97	101

For each encrypted number (Z), use the following equation to get your final N value: N^Z mod 9797

Take E and take it to the power of the sum of the alphabetic positions (A1Z26) of the encrypted word, modulo 9797 to get your final E value.

Determining λ(N)

Determine what 2 prime numbers from the list below were multiplied to get N:

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

λ(N) is calculated by using this equation: ((P1 - 1) * (P2 - 1)) / GCD(P1 - 1, P2 - 1)

The 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.

Determining D

• 1. Set up 7 variables: A, B, Q, R, T1, T2, 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 mod 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 mod 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, stopping at step 12.
• 17. Your D is equal to T2 mod λ(N).
• 18. Use this to check if D is correct: (D * E) mod λ(N) = 1

Decrypting

Do the instructions below for each digit on screens 1–4:

• 1: Take the Nth digit on screen 1 and multiply it by 1000.
• 2: Take the Nth digit on screen 2 and multiply it by 100.
• 3: Take the Nth digit on screen 3 and multiply it by 10.
• 4: Take the sum of the 3 numbers you got from steps 1 - 3 and the Nth digit on screen 4.
• 5: Take the number you got from step 4 (C) and put it through this equation:
  (C^D mod N) - 1
• 6: Turn the resulting number back into a letter, treating as if the number is its alphabetic position to get your Nth decrypted letter.

Example

Encrypted Word: DEECB
Screen 1: 22122
Screen 2: 68792
Screen 3: 43822
Screen 4: 73255
Screen A: 2181
Screen B: 6299

D → 2181¹⁷ mod 9797 → 2569
E → 2569¹⁹ mod 9797 → 1779
E → 1779¹⁹ mod 9797 → 2569
C → 2569¹³ mod 9797 → 4706
B → 4706¹¹ mod 9797 → 3071
N: 3071

6299^{4 + 5 + 5 + 3 + 2} mod 9797 → 685
E: 685

2 prime numbers that make 3071: 37 83

Calculating GCD
82 mod 36 = 10
36 mod 10 = 6
10 mod 6 = 4
6 mod 4 = 2
4 mod 2 = 0
GCD(36, 82) = 2

λ(N) = (36 * 82) / 2 = 1476

A	B	Q	R	T1	T2	T3
1476	685	2	106	0	1	-2
685	106	6	49	1	-2	13
106	49	2	8	-2	13	-28
49	8	6	1	13	-28	181
8	1	8	0	-28	181	-1476

D = 181 mod 1476 = 181

(2647¹⁸¹ mod 3071) - 1 → 19 → S
(2833¹⁸¹ mod 3071) - 1 → 20 → T
(1782¹⁸¹ mod 3071) - 1 → 5 → E
(2925¹⁸¹ mod 3071) - 1 → 1 → A
(2225¹⁸¹ mod 3071) - 1 → 4 → D

Decrypted Word: STEAD

If you don’t have a powerful calculator, follow the steps below:

• 1: Convert the exponent into binary.
• 2: Label the Least Significant Bit with the base number.
• 3: Each bit onward is labeled with the previous bit’s number, multiplied by itself, modulo by the divisor.
• 4: Multiply each number that has a 1 for a bit, modulo by the divisor.
• 5: The resulting number is equal to this: base^exponent mod divisor

To convert a number to binary, follow the instructions below:

• 1: Write the result of the number modulo 2.
• 2: Take the number and divide it by 2, rounded down.
• 3: Repeats steps 1–2 until the number is 0.
• 4: Reverse the resulting binary string to get your binary number.

Example

181 → 1, 90
90 → 0, 45
45 → 1, 22
22 → 0, 11
11 → 1, 5
5 → 1, 2
2 → 0, 1
1 → 1, 0

181 → 10110101
Divisor: 3071

1	2647	2833	1782	2925	2225
0	1658	1366	0110	2890	0173
1	0419	1859	2887	2051	2290
0	0514	1006	0075	2402	1903
1	0090	1677	2554	2266	0700
1	1958	2364	0112	0044	1711
0	1156	2347	0260	1936	0858
1	0451	2106	0038	1476	2195

(2647 * 419 * 90 * 1958 * 451) mod 3071 → 20
(2833 * 1859 * 1677 * 2364 * 2106) mod 3071 → 21
(1782 * 2887 * 2554 * 112 * 38) mod 3071 → 6
(2925 * 2051 * 2266 * 44 * 1476) mod 3071 → 2
(2225 * 2290* 700 * 1711 * 2195) mod 3071 → 5