Cryptography Fundamentals 6: Chinese Remainder Theory (CTR)

And so a large army met. The general asks the collected troops to arrange themselves into groups of 50. He counts that there are four…

Cryptography Fundamentals 6: Chinese Remainder Theory (CTR)

Apple: [here] Spotify: [here]

And so a large army met. The general asks the collected troops to arrange themselves into groups of 50. He counts that there are four troops left without a group. He then asks for groups of 60, and there are 14 left, and finally, he asks for groups of 70, and there are 24 left. The general stands up and tells the army that they are 187,000 strong. So how did the general do it?

>>> army%50
4
>>> army%60
14
>>> army%70
24
>>> print (army)
 187000

Solution: https://asecuritysite.com/principles_pub/crt02?val1=4,14,24&val2=50,60,70

The Chinese remainder theorem was first published by Chinese mathematician Sun Tzu. It determines a number x so that, when divided by some given divisors, leaves given remainders. As public key encryption typically involves this type of operation, CRT is well set up to help to crack encrypted messages. So what value will x equal in the following [Soln]:

x mod 3 = 2
x mod 5 = 3
x mod 7 = 2

The answer is 23, as 23 divided by 3 gives 21 remainder 2, 23 divided by 5 gives 4 remainder 3, and 23 divided by 7 gives 3 remainder 2.

CRT and RSA

If we capture enough RSA encrypted messages with the same e value and different modulus values (N), we can crack the message using Chinese Remainder Theorem (CRT). For example, if we have an e value of 3 we just need to capture three cipher messages to be able to recover the message.

In this case, we will use the following (where p1 and q1 generate N1, p2 and q2 generate N2 and p3 and q3 generate N3):

e=3, 
message=123456789123456, 
p1=1131701, q1=1131721, 
p2=1131727, q2=1131737, 
p3=1131749, q3=1131751

The run then gives:

eGCD of N values: 1
N1= 1280769787421 
N2= 1280817319799 
N3= 1280858062499
Message= 1234567891234 
e= 3
Cipher1= 184224238921 
Cipher2= 173356604414 
Cipher3= 369941826218

The equations we have to solve are then:

M^e mod 1280769787421=184224238921
M^e mod 1280817319799=173356604414
M^e mod 1280858062499=369941826218

If we now use Chinese Remainder Theorem we get a result of:

Result (M^e) is: 188,1676,377,431,587,319,857,436,861,793,600,904

And then we just use: 10^(log10(M^e)/e)

and recover the message of 1234567891234

Try here.

A more detailed example is [here]:

N1= 20439437 N2= 20684303 N3= 20830087
Message= 1500000 e= 3
Cipher1= 6509102 Cipher2= 9683741 Cipher3= 3214286

=======Equations to solve=======
M^e mod 20439437=6509102
M^e mod 20684303=9683741
M^e mod 20830087=3214286

======Chinese Remainder Theorm Calc========
Result (M^e) is:  3375000000000000000

Calculated value of m is  1500000  Using 10^(log10(M^e)/e)

We can also use:


M=res**(1.0/3.0)
M=libnum.nroot(res,3)

CRT is good, sometimes?

Well, in RSA, we can use Chinese Remainder Theory to simplify the decryption process. We will cover this in more detail when we look at RSA encryption. For now, all we can say that for RSA keys we also generate values of dQ, dP and InvQ to use CRT to speed up decryption.

Other attacks

CRT is a wide used cracking technique in cryptoanalysis. Werner Schindler [here] defined a timing attack on RSA which involves a factorization on the RSA-modulus if CRT has been used. The work goes back to 1996, when Arjen Lenstra defined an attack against an optimization (called the CRT). If a fault was generated in calculating a signature (using RSA-CRT optimization), the attacker could recover the associated private key from a signature. This is known as the “RSA-CRT key leak”.

Many systems have been immune from this attack as TLS did not use an RSA signature. Unfortunately, the forward security option in TLS is now being recommended, and this has re-introduced the problem.

Researchers at Red Hat [here] also now found many Web sites which were not hardened against this type of attack and found quite a few with RSA-CRT key leaks (none of which were code repositories). They found that the private key of a Web site can be leaked to the intruder, who can then decode all of the encrypted communications with the site and also impersonate it.

Forward secrecy is used with a key-exchange method and uses a session key which derives itself from a given set of long-term keys and which will not reveal the session key even in the long-term keys are breached.

How do we protect against this?

There are two ways to defend against this attack. The first is to make sure that e always exceeds the copies of messages that can be copied, and the other is to pad messages with random bits. In most applications, now e is 65,537.