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.

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

q	r	s	t
	m1	1	0
	m2	0	1

This algorithm (called the extended Euclidean algorithm) finds a value v from two moduli, m₁ and m₂, and two remainders, a₁ and a₂, such that v mod m₁ = a₁ and v mod m₂ = a₂.

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₋₂ / r₋₁ (round down)
• r = r₋₂ − q × r₋₁
• s = s₋₂ − q × s₋₁
• t = t₋₂ − q × t₋₁

Add a new row to the table with new values calculated as shown on the right. In these equations, a subscript of ₋₂ refers to the second-last and ₋₁ 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 = (a₂ × m₁ × s + a₁ × m₂ × t) mod (m₁ × m₂) (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
↘             ↙ q r s t 51 1 0 43 0 1 1 8 1 −1 5 3 −5 6 2 2 11 −13 1 1 −16 19 2 0 v = (a2×m1×s + a1×m2×t) mod (m1×m2) = (10×51×−16 + 21×43×19) mod (51×43) = 8997 mod 2193 = 225		↘             ↙ q r s t 52 1 0 31 0 1 1 21 1 −1 1 10 −1 2 2 1 3 -5 10 0 v = (a2×m1×s + a1×m2×t) mod (m1×m2) = (24×52×3 + 4×31×−5) mod (52×31) = 3124 mod 1612 = 1512