Montgomery Multiplication with Chinese Remainder Theorem

I am attempting to understand how to use montgomery multiplication in an RSA private key operation: a^e mod (n) where a is the message, e is the exponent, n is the modulus.

Using the algorithm from Montgomery Multiplication (with r=2^k, where k is the bit length of modulus n):

ModExp(a; e; n) { n is an odd number } Step 1. Compute n' using the extended Euclid algorithm. Step 2. a_hat := a*r (mod n) Step 3. x_hat := 1*r (mod n) Step 4. for i = k-1 down to 0 do Step 5. x_hat := MonPro(x_hat; x_hat) Step 6. if e(i) = 1 then x_hat := MonPro(a_hat; x_hat) Step 7. x := MonPro(x_hat; 1) Step 8. return x MonPro(a_hat;b_hat) Step 1. t := a_hat*b_hat Step 2. m := t*n' (mod r) Step 3. u := (t + m*n)/r Step 4. if u >= n then return u-n else return u 

Now, the modulus n will always be odd in RSA since it is generated from primes, which satisfies the first requirement. Also, from what I understand, in order for montgomery form to be possible, the size of the base a must be: a < n. Fortunately, in RSA, this also holds true as the message/signature can't be longer than the modulus.

However, here's where I'm getting stuck. I am adding in hardware acceleration to a preexisting RSA library (mbedTLS) by replacing the modular exponentiations with an accelerated version. It's working great, so long as it's not using the Chinese Remainder Theorem. I don't entirely grasp CRT yet, but I understand that it allows us to perform faster decryption by splitting the message up into two operations, and shrinking the modulus size:

m_1 = (M^d mod N) (mod p) = ((M mod p)^(d mod p-1)) (mod p)

m_2 = (M^d mod N) (mod q) = ((M mod q)^( d mod q-1)) (mod q)

Taken from: Chinese Remainder Theorem and RSA

The issue is, the message length is now longer than the modulus p and q. So now, it would violate the requirement for montgomery form that in (aR)*mod(N), a must be a < N.

I've searched all over for a method of doing montgomery modular exponentiation in the case that the a > N, but they all state that the input a is smaller than N. I can't seem to wrap my head around how you would perform a modexp using montgomery form with a larger input size than the modulus.

I was thinking maybe you could chunk a into binary groups of bitlen(N) with some sort of carry into the next group, but I can't figure out how you would mix in the inner loop that does the squaring. Would it be possible to modify it so that it becomes:

modexp(a[0:len(n)], e, n) ... modexp(a[len(n):len(a)], e, n)

And somehow combine those into an output that would be of len(n)? I'm really lost in understanding the mathematics behind it.

submitted by /u/polyic
[link] [comments]

from math https://ift.tt/386aSFl https://ift.tt/eA8V8J