Basic concepts of Chinese Remainder Theorem with respect of RSA/AES

 

Chinese Remainder Theorem
=========================

Suppose n_{1},n_{2}, ... , n_{k} are positive integers and coprime in pair. For any sequence of integers a_{1}, a_{2}, ... , a_{n}, there exists an integer x solving the following system of congruence equations:

\begin{cases} x \equiv a_1 \pmod{n_1} \\ \quad \cdots \\ x \equiv a_k \pmod{n_k} \end{cases}
There exists an unique modulo solution of the system of simultaneous congruences above:

x = a_1 M_1 y_1+ \cdots +a_k M_k y_k \pmod{M }in which:
\begin{aligned}<br />
M &= m_1 \cdots m_k \\<br />
M_1 &= \frac{M}m_1 , \cdots, M_k = \frac{M}m_k \\<br />
y_1 &\equiv (M_1)^{-1} \pmod{m_1}, \cdots , y_k\equiv (M_k)^{-1}\pmod{m_k}<br />
\end{aligned}

**Example**:
\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 5 \pmod{7} \end{cases}
Solve: \begin{aligned}<br />
M &=& 3.5.7 \\<br />
M_1 &=& 5.7 = 35 , M_2 = 3.7 = 21 , M_3 = 3.5 = 15 \\<br />
y_1 &=& (M_1)^{-1} = (35)^{-1} = 2^{-1} \mod{3}=2 \\<br />
y_2 &=& (M_2)^{-1} = (21)^{-1} = 1^{-1} \mod{5}=1 \\<br />
y_3 &=& (M_3)^{-1} = (15)^{-1} = 1^{-1} \mod{7}=1 \\\end{aligned}
Therefore, \begin{aligned}<br />
x &=& 3.35.2 + 5.21.1 + 7.15.1 \mod{3.5.7}\\<br />
x &=& 68 \mod{105}\end{aligned}

Hence, the solution of this simultaneous congruences is x=68+105k for all k are integers.

RSA using the Chinese remainder theorem
=======================================

In RSA scheme using the Chinese remainder theorem, the following values are precomputed and stored as a public key:
\begin{aligned}<br />
p,q&\text{ are primes from key generation}\\<br />
d_{p} =& d \pmod{p-1}\\<br />
d_{q} =& d \pmod{q-1}\\<br />
d_{inv} =& d^{-1} \pmod{p}\\\end{aligned}

Therefore, we can compute the message from given ciphertext more effienctly as follow:
\begin{aligned}<br />
m_1&=&c^{d_p}\mod{p}\\<br />
m_2&=&c^{d_q}\mod{q}\\<br />
h&=&q_inv\left(m_1-m_2\right)\mod{p} \\<br />
m&=&m_2+hq\\\end{aligned}

This scheme is more efficient than computing m=c^{d}\mod{pq} because these two modular exponentiations both use a smaller exponent and a smaller modulus.

**Proof:**

We know that: \begin{aligned}<br />
m_1&=&c^{d_p}=c^{d\pmod{p-1}}\mod{p} \\<br />
m_2&=&c^{d_q}=c^{d\pmod{q-1}}\mod{q} \\\end{aligned}

Note that the exponents are reduced module p-1 and q-1. This can be done using Fermat’s little theorem because p and q.Then, we recombine the; that is, we find a number m such that:
m = (M^d \bmod N) \mod p\\<br />
m = (M^d \bmod N) \mod q\\

Because of the Chinese Remainder Theorem (and because p and q are relatively prime), we can immediately deduce that: m = (M^d \bmod N) \mod pq\\ which is exactly what we were trying to compute.

Now, the questions in your comments appear to be asking about the details of this recombination step. It is actually fairly easy to see the correctness of the algorithm. To make the last step work, we need to show that we have come up with a value m such that: \begin{aligned}<br />
0 &\le m < pq\\<br />
m &\equiv m_1 \mod p\\<br />
m &\equiv m_2 \mod q\end{aligned}

As for the the first criteria 0 \le m < pq, well, that’s straight-forward; we know that 0 \le m_2 \le q-1, and 0 \le h \le p-1, and so the smallest that m can be is 0+(0.q)=0, and the largest it can be is q-1+((p-1)q)=pq-1

As for the third criteria, that’s also straight-forward;
(m_2 + (hq)) \bmod q = m_2 \bmod q + (hq) \bmod q = m_2 \bmod q

(m_2 + (hq)) \bmod p = (m_2 + qq_{inv}( m_1 - m_2) \bmod p) \bmod p = (m_2 + qq_{inv}(m_1 - m_2)) \bmod p

Now, q_{inv} is defined to be the number that, when multiplied by q modulo p, results in 1, or qq_{inv}=1 \bmod p. Now, because the above equation is, in fact, computed modulo p, we can replace qqinv with 1, which gives us:

m \bmod p = (m_2 + (m_1 - m_2)) \bmod p = m_1 \bmod p (QED)

Program for secure communication
================================

My following program was written using Python language. It includes 4 main parts:

- Take user text input from the console and encrypt it using AES-128 using built-in library Crypto.Cipher

aes_encrypt

- Encrypt the AES key using RSA where prime p,q were generated
randomly with the length of 1024 bits

rsa_encrypt

- Decrypt the key

- Using the normal RSA function

def decrypt(self, c,d,n):
return pow(c,d,n)

 

- Using the CRT approach

 {frame="single"}
def decryptCRT(self,c,p,q,d,dp,dq,qi):
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
h = (qi*(m1-m2))%p
m = m2+ h*q
return m

rsa_decrypt

- Decrypt the message using AES128 decryption and print it on
the screen.

aes_decrypt

Report of execution time
========================

Each execution of the encryption and decryption functions is too short. Therefore, I measure the average time of total 1000 executions to compare between each method. To ensure that the time measurement does not affect the process execution, this program used an external call based on Python’s ’timer’ library to calculate the difference between start and end of each run in milliseconds.

 

self.end = time.time()
self.secs = self.end - self.start
self.msecs = self.secs * 1000 # millisecs
if self.verbose:
print 'Elapsed time: %f ms' % self.msecs

**Functions** **1000 times (second)** **Average (second)**
-------------------- ------------------------- ----------------------
AES128 encryption                 0.015999794                 0.000016
AES128 decryption                 0.014999866                 0.000015
RSA encryption                       0.254999876                 0.000255
RSA decryption                       39.37100005                 0.039371
RSA CRT decryption                 12.02799988                 0.012028
Total                                          51.68499947                 0.051685

Table time shows the execution time of RSA scheme is much larger than AES128 scheme. This result explains why RSA should being used in key exchange while parties encrypt their information using AES cryptosystem. Another significant result is that the RSA-CRT decryption method is approximately 3 times faster than normal RSA decryption.

Hope this article can bring cryptography motivation to some Math/IT students and players who were exhausted in enjoying CTF challenges, or at least it can be a good reference for somebody.

-chuymichxinhdep

Ref:

1<https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29>

2 <http://crypto.stackexchange.com/questions/2575/chinese-remainder-theorem-and-rsa>

**APPENDIX**

from Crypto.Cipher import AES
import math,random
from fractions import gcd
from random import randrange
from collections import namedtuple
from math import log
from binascii import hexlify, unhexlify
from timer import Timer

class RSA():
def __init__(self):
self.KeyPair = namedtuple('KeyPair', 'public private CRT')
self.Key = namedtuple('Key', 'exponent modulus')
self.KeyCRT = namedtuple('KeyCRT', 'p q')
def is_prime(self,n, k=30):
# Miller-Rabin Test
if n <= 3:
return n == 2 or n == 3
neg_one = n - 1

# write n-1 as 2^s*d where d is odd
s, d = 0, neg_one
while not d & 1:
s, d = s+1, d>>1
assert 2 ** s * d == neg_one and d & 1

for i in xrange(k):
a = randrange(2, neg_one)
x = pow(a, d, n)
if x in (1, neg_one):
continue
for r in xrange(1, s):
x = x ** 2 % n
if x == 1:
return False
if x == neg_one:
break
else:
return False
return True

def randprime(self,N=10**8):
p = 1
while not self.is_prime(p):
p = randrange(N)
return p

def multinv(self,modulus, value):
'''Multiplicative inverse in a given modulus
'''
# http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
x, lastx = 0, 1
a, b = modulus, value
while b:
a, q, b = b, a // b, a % b
x, lastx = lastx - q * x, x
result = (1 - lastx * modulus) // value
if result < 0:
result += modulus
assert 0 <= result < modulus and value * result % modulus == 1
return result

def keygen(self,N, public=None):
''' Generate public and private keys from primes up to N.
Optionally, specify the public key exponent (65537 is popular choice).
'''

# http://en.wikipedia.org/wiki/RSA
p = self.randprime(N)
q = self.randprime(N)
composite = p * q
totient = (p - 1) * (q - 1)
if public is None:
while True:
private = randrange(totient)
if gcd(private, totient) == 1:
break
public = self.multinv(totient, private)
else:
private = self.multinv(totient, public)
assert public * private % totient == gcd(public, totient) == gcd(private, totient) == 1
return self.KeyPair(self.Key(public, composite), self.Key(private, composite), self.KeyCRT(p, q))
def encrypt(self, m,e,n):
return pow(m,e,n)
def decrypt(self, c,d,n):
return pow(c,d,n)
def decryptCRT(self, c,p,q,d,dp,dq,qi):
m1 = pow(c,dp,p)
m2 = pow(c,dq,q)
h = (qi*(m1-m2))%p
m = m2+ h*q
return m
class PKCS7Encoder():
"""
Technique for padding a string as defined in RFC 2315, section 10.3,
note #2
"""
class InvalidBlockSizeError(Exception):
"""Raised for invalid block sizes"""
pass

def __init__(self, block_size=16):
if block_size < 2 or block_size > 255:
raise PKCS7Encoder.InvalidBlockSizeError('The block size must be ' \
'between 2 and 255, inclusive')
self.block_size = block_size

def encode(self, text):
text_length = len(text)
amount_to_pad = self.block_size - (text_length % self.block_size)
if amount_to_pad == 0:
amount_to_pad = self.block_size
pad = chr(amount_to_pad)
return text + pad * amount_to_pad

def decode(self, text):
pad = ord(text[-1])
return text[:-pad]
iv = "this is iv123456"
key = "this mus be a 16"

def AES_encrypt(iv,key,message):
obj = AES.new(key, AES.MODE_CBC, iv)
pkcs7 = PKCS7Encoder()
return obj.encrypt(pkcs7.encode(message)).encode("hex")

def AES_decrypt(iv,key,cipherText):
obj = AES.new(key, AES.MODE_CBC, iv)
pkcs7 = PKCS7Encoder()
return pkcs7.decode(obj.decrypt(cipherText.decode('hex')))

message = raw_input("Input message:")
with Timer() as t:
cipherText = AES_encrypt(iv,key,message)

print cipherText
print "AES encrypt: %s s" % t.secs

rsa = RSA()
pk,sk,primes = rsa.keygen(2**1024, 65537)

message = int(cipherText.encode("hex"),16)

with Timer() as t:

rsacipher = rsa.encrypt(message,pk.exponent, pk.modulus)

print rsacipher

print "RSA Encrypt: %s s" % t.secs
with Timer() as t:

messagersa = hex(rsa.decrypt(rsacipher, sk.exponent,sk.modulus)).replace("0x","").replace("L","").decode('hex')
print "RSA Decrypt: %s s" % t.secs
print messagersa
#Pre compute RSA CRT
p = primes.p
q = primes.q
dp = sk.exponent % (p-1)
dq = sk.exponent % (q-1)
qi = rsa.multinv(p,q)
#RSA-CRT Decryption

with Timer() as t:
for i in xrange(1):
messagersacrt = hex(rsa.decryptCRT(rsacipher,p,q,sk.exponent,dp,dq,qi)).replace("0x","").replace("L","").decode('hex')
print "RSA Decrypt CRT : %s s" % t.secs
print messagersacrt

with Timer() as t:
plainText = AES_decrypt(iv,key,messagersa)
print "Decrypted message:", plainText
print "AES decrypt: %s s" % t.secs
```

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *