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:

ABCDEFGHIJKLM
7111317192329313741434749
NOPQRSTUVWXYZ
535961677173777983899197101

For each encrypted number (Z), use the following equation to get your final N value: NZ 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:
    (CD 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 → 218117 mod 9797 → 2569
E → 256919 mod 9797 → 1779
E → 177919 mod 9797 → 2569
C → 256913 mod 9797 → 4706
B → 470611 mod 9797 → 3071
N: 3071

62994 + 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

ABQRT1T2T3
1476685210601-2
6851066491-213
1064928-213-28
4986113-28181
8180-28181-1476

D = 181 mod 1476 = 181

(2647181 mod 3071) - 1 → 19 → S
(2833181 mod 3071) - 1 → 20 → T
(1782181 mod 3071) - 1 → 5 → E
(2925181 mod 3071) - 1 → 1 → A
(2225181 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: baseexponent 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

126472833178229252225
016581366011028900173
104191859288720512290
005141006007524021903
100901677255422660700
119582364011200441711
011562347026019360858
104512106003814762195

(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