For Cybersecurity, Chinese Remainder Theory (CRT) is a Blessing and aThorn In Our Side

For Cybersecurity, Chinese Remainder Theory (CRT) is a Blessing and aThorn In Our Side

A general asks the troops to arrange themselves in groups of 11 and there is one person without a group, and then into groups of 13, and there are 5 people left. And then into a group of 21 and 19 are left over, and finally groups of 23, and 4 are left over. The general annouces that they are 10,561 strong, and ready to go to battle.

The general used CRT, and here is how they did it:

https://asecuritysite.com/principles_pub/garner?aival=1,5,19,4&xival=11,13,21,23

Blessing and not

In Cybersecurity, CRT has been a blessing — as it allows us often to compute complex operations in a simplier way — and also a great problem — and where it can be used to crack ciphertext.

In 1959, Harvey L Garner method created a method to solve CRT [1]:

For CRT, we have a value of x, and which is 0≤x≤M, and where we have the residues of v(x)=(v1_,v_2,…v_t) and for x modulo of the moduli m_1,m_2,…m_t. The method Garner defined is:

and here is an implementation:

https://asecuritysite.com/principles_pub/garner

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 [Try]. 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. The coding for this is [here]:

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 using the example above [here]:

v=[1, 5, 19, 4]
m=[11, 13, 21, 23]

Using libnum x=10561

M=69069
We want to solve: 
x mod 11 = 1 
x mod 13 = 5 
x mod 21 = 19 
x mod 23 = 4 

c=[1, 6, 5, 16]

Cracks and good things

Here is cracks for RSA:

• CTF Generator: Cracking RSA with Chinese Remainder Theory — Håstad’s Broadcast Attack. CRT. In this example, an RSA cipher has used the same message and with three different moduli.
• CTF Solver: Cracking RSA with Chinese Remainder Theory — Håstad’s Broadcast Attack. CRT. In this example, an RSA cipher has used the same message and with three different moduli, and produce a solution.

For good, CRT can be used to improve the decryption process by simplying the decryption:

• RSA: dQ, dP and InvQ. Go.
• RSA Key Generation in Golang: dQ, dP and InvQ. Go.
• RSA Decryption using dP, dQ, qInv: CRT and Euler’s Theorem. Go. In order to perform the decrypt, we can apply CRT (Chinese Remainder Theory) to solve M=Ce(modN). For this we need dP=e−1(modp−1), dQ=e−1(modq−1) and qInv=q−1(modp).
• CBOR RSA: dQ, dP and InvQ. Go.
• RSA Keys (d, p, q, dQ, qP, invQ, e, N). RSA Keys.

Conclusion

And, so, CRT is both highly useful, and a major problem.

Reference

[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].