The Garner method solves [1] the Chinese Remainder Theorem (CRT). For CRT, we have a value of \(x\), and which is \(0 \le x \le M\), and where we have the residues of \(v(x)=(v_1, v_2, ... v_t)\) and for \(x\) modulo of the moduli \(m_1, m_2, ... m_t\). Note that the modulus values cannot share a factor: \(gcd(m_i,m_j)=1\).
Garner methods for Chinese Remainder Theory |
Theory
For CRT, we have a value of \(x\), and which is \(0 \le x \le M\), and where we have the residues of \(v(x)=(v_1, v_2, ... v_t)\) and for \(x\) modulo of the moduli \(m_1, m_2, ... m_t\). The method is:
for \(i\) from 2 to \(t\) do:
\(\hspace{1cm}\) for \(j\) from 1 to \((i-1)\) do:
\(\hspace{2cm}\) \(u=m_j^{-1} \pmod {m_i}\)
\(\hspace{2cm}\) \(c_i=u \cdot c_i \pmod {m_i}\)
\(u=v_1\)
\(x=u\)
For \(i\) from 2 to \(t\) do:
\(\hspace{1cm} u=(v_i-x) c_i \pmod {m_i}\)
\(x=x+u \cdot \prod_{j=1}^{i-1} m_j\)
Coding
import libnum import sys m=[5,7,11,13] v=[2,1,3,8] if (len(sys.argv)>1): v=eval("["+sys.argv[1]+"]") if (len(sys.argv)>2): m=eval("["+sys.argv[2]+"]") print (f"v={v}") print (f"m={m}") t=len(m) for i in range(1,t-1): for j in range(i+1,t): if (libnum.gcd(m[i],m[j])!=1): print(f"Cannot determine as gcd({m[i]},{m[j]})!=1") sys.exit() c=[1] * t res=libnum.solve_crt(v,m) print (f"Using libnum x={res}") MM=1 for j in range(0,t): MM=MM*m[j] print (f"\nM={MM}") print ("We want to solve: ") for i in range(0,t): print (f"x mod {m[i]} = {v[i]} ") for i in range(1,t): c[i]=1 for j in range(0,i): u=libnum.invmod(m[j],m[i]) c[i]=(u*c[i]) % m[i] u=v[0] x=u print (f"\nc={c}") for i in range(1,t): u=( (v[i]-x)*(c[i]) ) % m[i] mr=1 for j in range(0,i): mr=mr*m[j] x=x+u*(mr) print (f"\nx={x}")
And a sample run:
v=[2, 1, 3, 8] m=[5, 7, 11, 13] Using libnum x=2192 M=5005 We want to solve: x mod 5 = 2 x mod 7 = 1 x mod 11 = 3 x mod 13 = 8 c=[1, 3, 6, 5] x=2192
Cracking RSA
With RSA we encrypt a message \(M\) with a public key exponent (\(e\)) and a public modulus (\(N\)):
\(C = M^e \pmod N\)
Let's say Bob ciphers the same message (\(M\)) for Alice, Carol, Dave and Trent. Alice's public modulus (\(N\)) is 77, Carol's is 221, Dave's is 437 and Trent's is 1147, and we use a public exponent of \(e=5\). Eve then captures the ciphers of 76 (Alice), 41 (Carol), 347 (Dave) and 894 (Trent). Eve now needs to find \(x\) for:
x mod 77=76 x mod 221=41 x mod 437=347 x mod 1147=894
This gives \(x=7,776\). Not we just take the inverse log of this:
>> val = 10**((math.log10(7776))/e) >>> print (val) 6.0
And we get a value of \(x=6\), and which is the message as:
\(6^5 \pmod {77} = 76\)
\(6^5 \pmod {221} = 41\)
\(6^5 \pmod {437} = 347\)
\(6^5 \pmod {1147} = 894\)
References
[1] Garner, H. L. (1959, March). The residue number system. In Papers presented at the March 3-5, 1959, western joint computer conference (pp. 146-153). [here].