Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Wikipedia has a nice section regarding the speedup of the RSA decryption using the Chinese Remainder Theorem here. I need to understand the implementation of a similar speedup for the encryption algorithm of a more complex homomorphic encryption scheme (DGK) and, for some reason, I'm unable to get my head around the way the Chinese Remainder Theorem is used to achieve this. I don't have a lot of background on modular arithmetic and I would really appreciate it if someone could explain this in more detail.

Edit: Following @mikeazo's comment, I just want to understand the way CRT is applied to speed up the RSA encryption.

share|improve this question
    
When dealing with the cryptosystem you reference, don't forget to look at an update to the system which is necessary for security. –  mikeazo May 9 '12 at 11:17
1  
I would suggest adding the mathematical details of the cryptosystem and how the CRT is used in it to your question. That way people (myself included) don't have to read the paper in order to answer your question. You are bound to get better answers. –  mikeazo May 9 '12 at 11:21
    
@mikeazo: The security update is not relevant for this conversation at the moment. If I manage to understand the way the CRT is applied for RSA, then I should be able to figure the rest out by myself, because it is similar. Please ignore my reference to DGK for now. –  Mihai Todor May 9 '12 at 11:30
    
after reading the CRT link you provided and this, perhaps you could explain exactly what you are having difficulty understanding? –  mikeazo May 9 '12 at 11:33
    
It's not clear to me how the CRT is applied to derive this formula: m = m_2 + (h * q), where h = q_inv * (m_1 - m_2) (mod p). I would really appreciate it if you could detail this procedure. –  Mihai Todor May 9 '12 at 11:39
show 2 more comments

1 Answer 1

up vote 8 down vote accepted

Well, the idea behind the CRT optimization is that if we know the factorization of the modulus $N$ (which we may if we have the private key), then we can split up the message $M$ into two halves (one modulo $p$, and one modulo $q$), compute each modulo separately, and then recombine them. That is, we compute:

$M_1 = (M^d \bmod N) \bmod p = ((M \bmod p)^{d \mod p-1}) \bmod p$

$M_2 = (M^d \bmod N) \bmod q = ((M \bmod q)^{d \mod q-1}) \bmod q$

(Note that the exponents are reduced modulo $p-1$ and $q-1$; we can do this because $p$ and $q$ are prime (and Fermat's little theorem); this is the source of a good portion of the speedup).

Then, we recombine the; that is, we find a number $m$ such that:

$m = (M^d \bmod N) \mod p$

$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.

Now, 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:

$0 \le m < pq$

$m \equiv m_1 \mod p$

$m \equiv m_2 \mod q$

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 + (h * q)) \bmod q = m_2 \bmod q + (h*q) \bmod q = m_2 \bmod q$

The second one is a little tricker: $(m_2 + (h * q)) \bmod p = (m_2 + q * q_{inv} * ( m_1 - m_2) \bmod p) \bmod p = (m_2 + q * q_{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 (that is, $q * q_{inv} = 1 \mod p$). Now, because the above equation is, in fact, computed modulo $p$, we can replace $q * q_{inv}$ with 1, which gives us:

$m \bmod p = (m_2 + 1 * (m_1 - m_2)) \bmod p = m_1 \bmod p$

QED

share|improve this answer
    
That's a really nice and detailed proof, but I need more help to understand it: First, how did you end up with this formula: $M_1 = (M^d \bmod N) \bmod p = ((M \bmod p)^{d \mod p-1}) \bmod p$? Could you please detail it? I don't understand how you applied Fermat's "Little" Theorem to obtain it. It's clear how you've proven the formulae for the recombination step, but I'm not able to understand how does the CRT work in this case. How do you "immediately deduce that" $m = (M^d \bmod N) \mod pq$? –  Mihai Todor May 9 '12 at 18:04
    
@MihaiTodor: well, for the first question, the CRT optimization splits $M$ into two parts, $M \bmod p$ and $M \bmod q$. Then, it computes the RSA private operation on both halves, that is, for the p side, we compute $((M \bmod p)^d) \bmod p$. We also note that $M^d \equiv (M \bmod p)^d \mod p$, that is, each of the two sides is effectively independent. We further note that Fermat's Little Theorem implies that $a^b \equiv a^{b \mod p-1} \mod p$ if $p$ is prime, and so it is sufficient to compute $((M \bmod p)^{d \mod p-1}) \bmod p$. –  poncho May 9 '12 at 18:27
    
@MihaiTodor: as for your second question, well, the Chinese Remainder theorem states that if $p$ and $q$ are relatively prime, and if $A \equiv B \mod p$ and $A \equiv B \mod q$, then $A \equiv B \mod pq$. –  poncho May 9 '12 at 18:29
    
Thank you very much. I can see that your knowledge of this subject is really good, but I am looking in 2 distinct books at the formulation of the CRT and I am failing to see how this simple statement that you presented above derives from it. The CRT states that a solution for a system of r linear congruences exists and is unique modulo n, where $n = \prod_{i=0}^rn_i$, but how do you use this? The "General Case" on Wikipedia doesn't help: en.wikipedia.org/wiki/Chinese_remainder_theorem#General_case –  Mihai Todor May 9 '12 at 18:48
    
@MihaiTodor: set $r=2$, $n_0 = p$, $n_1 = q$. Now, CRT says that, given $B \bmod p$ and $B \bmod q$ (with $0 \le B < pq$), there is a unique $0 \le A < pq$ such that $A \equiv B \bmod p \mod p$ and $A \equiv B \bmod q \mod q$. Now, $A \equiv B$ is such a solution. Since the solution is unique, it must be the only solution (and hence we can conclude that $A \equiv B$) –  poncho May 9 '12 at 18:56
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.