Fast Montgomery Reduction with special modulus
Publication Date: 2005-Jun-16
The IP.com Prior Art Database
Philips Semiconductors Crypto Competence Center
ref: CCC-031110-1.GH 231350 date:
All rights strictly reserved. Reproduction or issue to third parties in any form whatever is not permitted without written authority from P hilips.
1 Special Modulus
This type of reduction is a Montgomery Reduction with a special modulus N that makes the reduction very fast. When an operand has to be reduced by m words, the reduction takes also m multiplications, while the standard Montgomery Reduction takes m(m+1) multiplications.
All operands have to be in Montgomery Space.
Assume, that the operands consist of m words of 64-bit (other word sizes are also possible). Then n has the following special characteristic ( n is only one word of 64-bit):
· N = nBm-1- 1 for GF(p) with B=264
· N = nBm-1 Å 1 for GF(2n) with B=a64
Let R = rmBm + rm-1Bm-1 + ... + r0
If R has to be reduced by 1 word, then we calculate: R = (R + r0N)/B
= [rmBm + rm-1Bm-1 + ... + r0 + r0(nm-1Bm-1-1)]/B =
= rmBm-1 + rm-1Bm-2+ r0nm-1Bm-2 + rm-2Bm-3+...r1
We calculate the product r0nm-1 and add the lower part to term rm-1 and the upper part to term rm. All other terms of R are unaffected, but we omit term r0, i.e. we divide R by B.
If R has to be reduced by more terms, we repeat the same procedure using the next LSW as multiplication factor. This is depicted in Figure 1 for the reduction of a complete 192-bit ECC- multiplication (m=3).
Philips Semiconductors Company Confidential CCC-031110-1.GH Crypto Competence Center page 2
r4 r2 r3 r1
r2 r1 r0
Figure 1 192-bit ECC reduction (m=3)
Because we need a special modulus, the reduction is in general not applicable for RSA, but for ECC. As with the normal Montgomery Reduction, the reduction might give 1 overflow bit, so we need to do additional reduction. For ECC, it is favourable when we can combine the multiplication with addition or subtraction of a 3rd term Z. This gives also overflow or underflow bits, for which we also need additional reduction. The invention describes a way to combine the additional reduction with the Montgomery Reduction.
All rights strictly reserved. Reproduction or issue to third parties in any form whatever is not permitted without written authority from Philips.
Philips Semiconductors Company Confidential CCC-031110-1.GH
Crypto Competence Center page 3
2 Reduction of X.Y± Z
2.1 Additional Reduction
Because of the Montgomery Reduction, we have to calculate X.Y ± Bm Z.
or issue to third
r4 r2 r3 r1
All rights strictly reserved. Reproduction
r2 r1 r0
Figure 2 With additional reduction
Without additional reduction R" will be too large or even negat...