Device and method for calculating conversion parameter of montgomery modular multiplication and program therefor

A method for computing a conversion parameter R2 (mod n) of Montgomery modular multiplication where the effective word length of the residue modulo n is taken as m, the bit length per 1 word is taken as k, and 2m×k=R, this method comprising:

• (A) a first step for calculating H′=R (mod n), H0=2v×R (mod n) (where v is an integer, v≧1, and (m×k)/v is an integer);
• and
• (B) a second step for calculating and outputting H′=R2 (mod n) by repeating the steps of:
• (B-1) calculating H′=REDC(H′, Hi)n if the i-th bit value of (m×k)/v is 1, and
• (B-2) calculating Hi=REDC(Hi-1, Hi-1)n
• with respect to i=0, 1, . . . , b−1
• (here, b is a constant representing the highest-order bit length of (m×k)/v and REDC represents the Mongtomery modular multiplication REDC(a, b)=a×b×R−1 (mod n)).

A program for a method for computing a conversion parameter R2 (mod n) of Montgomery modular multiplication where the effective word length of the residue modulo n is taken as m, the bit length per 1 word is taken as k, and 2m×k=R, this program serving to execute on a computer a method for computing a conversion parameter of Montgomery modular multiplication comprising:

• (A) a first step for calculating H0=2v×R (mod n) (where v is an integer, v≧1, and (m×k)/v is an integer), this step comprising the steps of:
• (A-1) a step for initializing two registers REG1, REG2 by REG1=n, REG2=2(m−1)×k (here, REG1 is a register composed of m words and REG2 is a register composed or m or more words), and
• (A-2) a step for obtaining 2v×R (mod n) by repeating k+v times the modular squaring computation employing the value of REG1 as a residue modulo with respect to REG2;
• (B) a second step for calculating Hp=2v×2p×R (mod n) from H0=2v×R (mod n) by repeating Hi=REDC(Hi-1, Hi-1)n with respect to i=1, 2, . . . , p (where p represents an integer satisfying the condition 2p≧(m×k)/v>2p−1, REDC represents the Mongtomery modular multiplication REDC(a, b)n=a×b×R−1 (mod n), and xˆi represents exponential computation xi);
• and
• (C) a third step for calculating Hp=R2 (mod n) (where g=2k×E(p,m,k), E(p, m, k)=2×m−(v×2p)/k) by calculating Hp=REDC(Hp, g)n with respect to Hp obtained in the second step when 2p>(m×k)/v and finally outputting Hp as R2 (mod n).

A program for a method for computing a conversion parameter R2 (mod n) of Montgomery modular multiplication where the effective word length of the residue modulo n is taken as m, the bit length per 1 word is taken as k, and 2m×k=R, this program serving to execute on a computer a method for computing a conversion parameter of Montgomery modular multiplication comprising:

• (A) a first step for calculating H′=R (mod n), H0=2v×R (mod n) (where v is an integer, v≧1, and (m×k)/v is an integer);
• and
• (B) a second step for calculating and outputting H′=R2 (mod n) by repeating the steps of:
• (B-1) calculating H′=REDC(H′, Hi)n if the i-th bit value of (m×k)/v is 1, and
• (B-2) calculating Hi=REDC(Hi-1, Hi-1)n with respect to
• i=0, 1, . . . , b−1
• (here, b is a constant representing the highest-order bit length of (m×k)/v and REDC represents the Mongtomery modular multiplication REDC(a, b)n=a×b×R−1 (mod n)).

A device for computing a conversion parameter R2 (mod n) of Montgomery modular multiplication where the effective word length of the residue squaring n is taken as m, the bit length per 1 word is taken as k, and 2m×k=R, this device comprising:

• a first register REG1 composed of m words;
• a second register REG2 composed of m or more words;
• an initialization processing unit for initializing the two registers REG1, REG2 by REG1=n, REG2=2(m−1)×k;
• an H0 computation unit for computing H0=2v×R (mod n) (where v is an integer, v≧1, and (m×k)/v is an integer) by repeating k+v times the modular squaring computation employing the value of the first register REG1 as a residue modulo with respect to the second register REG2;
• an Hp computation unit for calculating Hp=2v×2p×R (mod n) from H0=2v×R (mod n) by repeating Hi=REDC(Hi-1, Hi-1)n with respect to i=1, 2, . . . , p (where p represents integer satisfying the condition 2p≧(m×k)/v>2p−1, REDC represents the Mongtomery modular multiplication REDC(a, b)n=a×b×R−1 (mod n), and xˆi represents exponential computation xi);
• and
• a parameter output unit for calculating Hp=R2 (mod n) by calculating Hp=REDC(Hp, g)n with respect to Hp obtained with the Hp computation unit when 2p>(m×k)/v (where g=2k×E(p,m,k), E(p, m, k)=2×m−(v×2p)/k) and finally outputting the obtained Hp as R2 (mod n).