Scheme for computing Montgomery division and Montgomery inverse realizing fast implementation

A Montgomery division device for computing a Montgomery division Y=B.multidot.A.sup.-1 .multidot.2.sup.n mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0.ltoreq.A<N, a positive integer B, and an integer n which is satisfying n.gtoreq.L where L is a bit length of N in binary expression, the device comprising:

• an inverse calculation unit for obtaining a first intermediate result C=A.sup.-1 .multidot.2.sup.k mod N and a parameter k satisfying L.ltoreq.k.ltoreq.2L from inputs A and N;
• a Montgomery multiplication unit for obtaining a second intermediate result D=B.multidot.C.multidot.2.sup.-n mod N from the first intermediate result C obtained by the inverse calculation unit and input B and N;
• and
• an inverse correction unit for obtaining the Montgomery division Y=D.multidot.2.sup.2n-k mod N from the second intermediate result D obtained by the Montgomery multiplication unit, the parameter k obtained by the inverse calculation unit and input N.

A method for computing a Montgomery division Y=B.multidot.A.sup.-1 .multidot.2.sup.n mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0.ltoreq.A.ltoreq.N, a positive integer B, and an integer n which is satisfying n.gtoreq.L where L is a bit length of N in binary expression, the method comprising the steps of:

• (a) obtaining a first intermediate result C=A.sup.-1 .multidot.2.sup.k mod N and a parameter k satisfying L.ltoreq.k.ltoreq.2L from inputs A and N;
• (b) obtaining a second intermediate result D=B.multidot.C.multidot.2.sup.-n mod N from the first intermediate result C obtained by the step (a) and input B and N;
• and
• (c) obtaining the Montgomery division Y=D.multidot.2.sup.2n-k mod N from the second intermediate result D obtained by the step (b), the parameter k obtained by the step (a) and input N.

An article of manufacture, comprising:

• a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for computing a Montgomery division Y=B.multidot.A.sup.-1 .multidot.2.sup.n mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0.ltoreq.A<N, a positive integer B, and an integer n which is satisfying n.gtoreq.L where L is a bit length of N in binary expression, the computer readable program code means includes:
• first computer readable program code means for causing said computer to obtain a Montgomery inverse X=A.sup.-1 .multidot.2.sup.2n mod N from inputs A and N;
• and
• second computer readable program code means for causing said computer to obtain the Montgomery division Y=B.multidot.X.multidot.2.sup.-n mod N from the Montgomery inverse X obtained by the first computer readable program code means and inputs B and N.

An article of manufacture, comprising:

• a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for computing a Montgomery division Y=B.multidot.A.sup.-1 .multidot.2.sup.n mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0.ltoreq.A<N, a positive integer B, and an integer n which is satisfying n.gtoreq.L where L is a bit length of N in binary expression, the computer readable program code means includes:
• first computer readable program code means for causing said computer to obtain a first intermediate result C=A.sup.-1 .multidot.2.sup.k mod N and a parameter k satisfying L.ltoreq.k.ltoreq.2L from inputs A and N;
• second computer readable program code means for causing said computer to obtain a second intermediate result D=B.multidot.C.multidot.2.sup.-n mod N from the first intermediate result C obtained by the first computer readable program code means and input B and N;
• and
• third computer readable program code means for causing said computer to obtain the Montgomery division Y=D.multidot.2.sup.2n-k mod N from the second intermediate result D obtained by the second computer readable program code means, the parameter k obtained by the first computer readable program code means and input N.

An article of manufacture, comprising:

• a computer usable medium having computer readable program code means embodied therein for causing a computer to function as a system for computing a Montgomery inverse X=A.sup.-1 .multidot.2.sup.2n mod N for a positive integer N, a positive integer A which is relatively prime with respect to N and satisfying 0.ltoreq.A<N, and an integer n which is satisfying n.gtoreq.L where L is a bit length of N in binary expression, the computer readable program code means includes:
• first computer readable program code means for causing said computer to obtain an intermediate result C=A.sup.-1 .multidot.2.sup.k mod N and a parameter k satisfying L.ltoreq.k.ltoreq.2L from inputs A and N;
• and
• second computer readable program code means for causing said computer to obtain the Montgomery inverse X=C.multidot.2.sup.2n-k mod N from the intermediate result C and the parameter k obtained by the first computer readable program code means and input N.

A method for implementing basic operations of an elliptic curve cryptosystem, comprising the steps of:

• converting parameters of the basic operations of the elliptic curve cryptosystem from Zp, integers modulo p, over which elliptic curves are defined, into a Montgomery space;
• executing the basic operations of the elliptic curve cryptosystem on input data of the elliptic curve cryptosystem in terms of Montgomery arithmetic system operations defined on the Montgomery space using the parameters converted by the converting step;
• and
• inversely converting operation results of the basic operations of the elliptic curve cryptosystem obtained by the executing step from the Montgomery space into Zp so as to obtain output data of the elliptic curve cryptosystem.