## On the Subject of the Chinese Remainder CM

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

If the Submit Button is white, follow the instructions under Encrypt Instructions. Otherwise follow the instructions under Decrypt Instructions.

Take note: Some parts of this cipher use A1Z26 (normal alphabetic position) while some use A1Y25Z0 (normal for A–Y, but Z is 0).

## Decrypt Instructions

Append any letters on screen 2 to the end of your existing encrypted word.

Start with a value v of 0 (zero). Then, for each letter in the encrypted word, multiply v by 26 and add the A1Y25Z0 value of the letter.

For each letter on screen 1:

• Convert the letter into a number using A1Z26 and add 26.
• Take v modulo that number.
• Convert the result back to a letter using A1Z26.

The letters obtained this way form the decrypted word.

### Example

Encrypted word: YJOXGAAK + S (from screen 2)
v = (((((((25×26+10)×26+15)×26+24)×26+7)×26+1)×26+1)×26+11)×26+19 = 5305916823213

Screen 1: MKXOQCUW

5305916823213 % (13 + 26) = 6 = F
5305916823213 % (11 + 26) = 5 = E
5305916823213 % (24 + 26) = 13 = M
5305916823213 % (15 + 26) = 9 = I
5305916823213 % (17 + 26) = 14 = N
5305916823213 % (3 + 26) = 9 = I
5305916823213 % (21 + 26) = 19 = S
5305916823213 % (23 + 26) = 13 = M

Decrypted word: FEMINISM

## Encrypt Instructions

Convert each letter on screen 1 into a number using A1Z26 and add 26. These numbers are called the moduli.

Convert each letter of the encrypted word using A1Z26 and add the A1Y25Z0 value of the corresponding letter on screen 2. Call these the remainders.

Find the only integer v in the range 0 ≤ v < p (p is the product of all the moduli) such that taking v modulo each of the moduli results in the corresponding remainders. (This number is unique per the Chinese Remainder Theorem.) The following section outlines one possible method for finding this integer.

### Finding v from two moduli and remainders

qrst
m110
m201

This algorithm (called the extended Euclidean algorithm) finds a value v from two moduli, m1 and m2, and two remainders, a1 and a2, such that v mod m1 = a1 and v mod m2 = a2.

Create a table with four columns, labeled q, r, s and t, and populate it with initial values as shown on the right.

• q = r−2 / r−1 (round down)
• r = r−2 − q × r−1
• s = s−2 − q × s−1
• t = t−2 − q × t−1

Add a new row to the table with new values calculated as shown on the right. In these equations, a subscript of −2 refers to the second-last and −1 to the last fully populated row.

Keep calculating new rows until you reach one where r is 0. Then, obtain s and t from the row above that one (the rest is no longer relevant).

Calculate v = (a2 × m1 × s + a1 × m2 × t) mod (m1 × m2) (positive modulo).

### Finding the overall v

• Pick any two moduli and their corresponding remainders and remove them.
• Perform the extended Euclidean algorithm on these values to obtain v.
• Add a new modulus/remainder pair where the modulus is the product of the original two moduli and the new remainder is v.
• Repeat until only one pair is left. Its remainder is the final v.

### Final step

Once v is found, reconstruct the decrypted word as follows:

• Take v modulo 26 and convert the result to a letter using A1Y25Z0.
• Prepend this letter to the front of previously decrypted letters.
• Divide v by 26, rounding down.
• Repeat this process until v is zero.

### Example

Encrypted word: UJDT
Screen 2: ZZZD → Remainders: 21, 10, 4, 24
Screen 1: YQZE → Moduli: 51, 43, 52, 31

 m = 51 a = 21
 m = 43 a = 10
 m = 52 a = 4
 m = 31 a = 24

↘             ↙

qrst
5110
4301
181−1
53−56
2211−13
11−1619
20

v = (a2×m1×s + a1×m2×t) mod (m1×m2)
= (10×51×−16 + 21×43×19) mod (51×43)
= 8997 mod 2193
= 225

↘             ↙

qrst
5210
3101
1211−1
110−12
213-5
100

v = (a2×m1×s + a1×m2×t) mod (m1×m2)
= (24×52×3 + 4×31×−5) mod (52×31)
= 3124 mod 1612
= 1512

↘             ↙

qrst
219310
161201
15811−1
2450−23
11313−4
357−1115
21725−34
36−86117
25197−268
11−283385
50

v = (a2×m1×s + a1×m2×t) mod (m1×m2)
= (1512×2193×−283 + 225×1612×385) mod (2193×1612)
= -798736428 mod 3535116
= 199788

199788 % 26 = 4 → D   |   199788 / 26 = 7684
7684 % 26 = 14 → N   |   7684 / 26 = 295
295 % 26 = 9 → I   |   295 / 26 = 11
11 % 26 = 11 → K   |   11 / 26 = 0

Decrypted word: KIND