Browse Prior Art Database

Fast Montgomery Reduction with special modulus

IP.com Disclosure Number: IPCOM000125754D
Publication Date: 2005-Jun-16
Document File: 7 page(s) / 42K

Publishing Venue

The IP.com Prior Art Database

Abstract

ID697181

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 31% of the total text.

Page 1 of 7

Report

Company Confidential

Philips Semiconductors Crypto Competence Center

ID697181 department:

           ref: CCC-031110-1.GH 231350 date:

2003-11-10

to:

subject:

Montgomery-Hubert Reduction

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

697181_E_031110(MontgHubert)

[This page contains 1 picture or other non-text object]

Page 2 of 7

Philips Semiconductors Company Confidential CCC-031110-1.GH Crypto Competence Center page 2

R'=X.Y

r5

r4 r2 r3 r1

r0

nr0+r2

nr1 +r3+c

nc2+ Br5+r4+c

c2

r2 r1 r0

R"

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.

[This page contains 1 picture or other non-text object]

Page 3 of 7

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.

Bk+nr0+r2

nr1 +r3+c

R'=X.Y

or issue to third

r5

r4 r2 r3 r1

r0

All rights strictly reserved. Reproduction

-Bkn+nc2+ Br5+r4+c

c2

r2 r1 r0

R"

Figure 2 With additional reduction

Without additional reduction R" will be too large or even negat...