I'm taking a hardware cryptography class and working on a problem that focuses on Montgomery Reduction.

So by definition: Computing $a * b \text{ mod } N$

  • Pick $R$, s.t. $R > N$, $gcd(R,N) = 1$
  • Compute $N^{-1} \text{ mod }R$
  • $a’ = a * R \text{ mod } N$
  • $b’ = b * R \text{ mod } N$
  • $c’ = (a’ * b’) * R^{-1} \text{ mod } N$
  • $c = c’* R^{-1} \text{ mod } N$

Claim: $c ≡ a * b \text{ mod } N$

Proof: $c’R^{-1} ≡ (a’b’)R^{-1} R^{-1} ≡ (a’ * R^{-1}) * (b’ * R^{-1}) ≡ a * b \text{ mod } N$

If $R=2^k, x * R, ÷ R, \text{ mod } R$ are trivial an option to implement modular exponentiation.

Now I am ask to solve for this given the following 25 modulo 109 w.r.t. 128. The question I have is since I only have $a= 25$, does this mean there is no $b$ value? And if that is the case, I can ignore calculating the $b’ = b * R \text{ mod } N$ expression and also remove it from calculating the $c$ equation?

  • 1
    $\begingroup$ You only need to do the Montgomery reduction after you do a multiplication of two values in Montgomery form. If you simply want to convert 25 to Montgomery form, then do 25 * R mod N. $\endgroup$
    – user13741
    Apr 24 '15 at 21:40
  • $\begingroup$ Thank you for the explanation. I actually tried this approach, but wasn't successful. Maybe the question has a hidden point that I'm missing. Here is the question: Montgomery reduction of 25 modulo 109 with respect to 128 is $\endgroup$
    – linos
    Apr 24 '15 at 22:22
  • $\begingroup$ 25 * 128 mod 109 = 39. I really don't see what else they could be asking for. $\endgroup$
    – user13741
    Apr 24 '15 at 23:17
  • $\begingroup$ I agree with you. I calculated the same result, but only doing it the long way. I will ask the prof. for an explanation. Thank You for your help. $\endgroup$
    – linos
    Apr 25 '15 at 0:19
  • $\begingroup$ So I received a bit more information on this problem. The problem is asking for the Montgomery Reduction, not computing axb(modN), so somehow I need to check the Montgomery reduction formulas. Also, another tip I received is that -N^-1=27. $\endgroup$
    – linos
    Apr 25 '15 at 22:00

Consult the transcript from the class, there is an example he works through which is very similar to this problem. Fundamentally you're trying to solve the problem c = (T + T(-N^-1) (mod R)N)/R (mod N). I suggest creating an equation in Excel (or other tool of your choice). Test your equation using the inputs from the example problem (EXAMPLE INPUTS: T=69, N=109, R=128, -N^-1 = 27). When you're confident your equation is working for that (EXAMPLE PROBLEM SOLUTION = 61), then plug in the values for this problem. Hint: T = 25 for this problem.


Answer is 30: $$T=25, N=109, -(N)^{-1} = 27, R=128$$ $$\Rightarrow T(R^{-1}) \bmod N$$ $$\Rightarrow m=T*(-N)^{-1} \bmod R \Rightarrow m= 25*27 \bmod 128 \Rightarrow m=35$$ $$\Rightarrow t= (T+m \cdot N)/R \Rightarrow (25+(35*109))/128 \Rightarrow t=30$$

  • 3
    $\begingroup$ Even if this answer is correct (which I'm not going to spend any time checking), it doesn't really help the OP (or anyone else) understand how to solve problems like this. $\endgroup$ Mar 30 '18 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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