Exploit Notes

Chinese Remainder Theorem

Last modified: 2023-09-02

Cryptography Math

Basic

If moduli (n1, n2, etc.) are co-primes, the following rules hold:

x ≡ a1 mod n1 # means `x % n1 = a1`
x ≡ a2 mod n2 # means `x % n2 = a2`
...
x ≡ ak mod nk # means `x % nk = ak`

In addition, if the values of a1, a2, … ak and n1, n2, … nk are defined, we can calculate x by the following approach.

# Calculate N
N = n1 * n2 * n3 * ... * nk

# Calculate Ni (N1, N2, ..., Nk)
N1 = n2 * n3 * n4 ... * nk
N2 = n1 * n3 * n4 ... * nk
N3 = n1 * n2 * n4 ... * nk
...
Nk = n1 * n2 * n3 ... * n(k-1)

# Calculate xi (x1, x2, ..., xk)
N1*x1 ≡ 1 (mod n1) # means `N1*x1 % n1 = 1`
N2*x2 ≡ 1 (mod n2) # means `N2*x2 % n2 = 1`
N3*x3 ≡ 1 (mod n3) # means `N3*x3 % n3 = 1`
...
Nk*xk ≡ 1 (mod nk) # means `Nk*xk % nk = 1`

# x is sum of each ai*Ni*xi (mod N)
x = a1*N1*x1 + a2*N2*x2 + a3*N3*x3 + ... + ak*Nk*xk (mod N)

Using crt method in Sympy

from sympy.ntheory.modular import crt

m = [7, 15]
a = [5, 12]
(x, y) = crt(m, a)
# x = 68, y = 77

References