Method and apparatus for modular inversion for information security and recording medium with a program for implementing the method

Claim 3

The method of claim 1 , wherein said step (c) includes a step of determining whether k+t−m is positive or negative and calculating R=S2 −(k+t−m) mod N or R=S2 k+t−m mod N, depending on whether said k+t−m is positive or negative.

Claim 4

The method of claim 1 or 2 , wherein the value of said parameter t is in the range of 0.6n+20≦t≦0.54n−20.

Claim 5

The method of claim 3 , wherein the value of said parameter t is an integral multiple of the number of bits which a calculation apparatus used processes at a time.

Claim 6

The method of claim 1 , wherein: said information security service utilizes an elliptic curve E/GF(p) over GF(p); said modular inversion is a modular inversion in the calculation of λ in the following equations for calculating from two points (x 1 , y 1 ) and (x 2 , y 2 ) on said elliptic curve E/GF(p), a point (x 3 , y 3 ) of the sum of said two points λ=( y 2 −y 1 )/( x 2 −x 1 )mod p x 3 =λ 2 −x 1 −x 2 mod p y 3 =λ( x 1 −x 3 )− y 1 mod p, said λ being expressed by the following equation with y=y 2 −y 1 and X=x 2 −x 1 λ=(y 2 −y 1 )(x 2 −x 1 ) −1 mod p=yX −1 mod p; said step (a) is a step of calculating Y by the following equation Y=X2 −t mod p; said step (b) is a step of calculating S and k by the following equation using said Y and p S=bgcd ( Y, p )= Y −1 2 k mod p; and said step (c) is a step of calculating a modular inverse X′ by the following equation using said S and t X′=S 2 −(k+t−m) mod p, where m= 0 , n or 2 n and calculating λ by the following equation using said modular inverse X′ λ= yX′ mod p.

Claim 7

The method of claim 1 , wherein: said information security service utilizes a digital signature scheme ESIGN; and, letting the following equation, which is part of a digital signature generating process, y=w /( kx k−1 )mod p where: x, k, w are integers satisfying 0<x<pg, 0≦w<p, p and q being primes be represented by the following equation y=w/ ( kx k−1 )mod p=wX −1 mod p: said step (a) is a step of calculating X=kx k−1 and then calculating Y by the following calculation with X′=X −1 mod p Y=X 2 −t mod p; said step (b) is a step of calculating S and k by the following equation using said Y and p S=bgcd ( Y, p )= Y −1 2 k mod p; and said step (c) is a step of calculating a modular inverse X′ by the following equation using said S and t X′=S 2 −(k+t−m) mod p, where m= 0, n or 2 n and performing the following equation using said modular inverse X′ y=wX −1 mod p=wX′ mod p.

Claim 8

The method of claim 1 , wherein: said information security service utilizes a digital signature scheme RSA; and setting R=r −1 mod N in the following equation which is part of a blind signature generating process, s′= ( r e m ) d mod N s=s′/r mod N where r, m, d, e are integers satisfying 0<r, m<N and 0<e, d<ø (N): said step (a) is a step of calculating Y by the following calculation Y=r 2 −t mod N; said step (b) is a step of calculating S and k by the following equation using said Y and N S=bgcd ( Y, N )= Y −1 2 k mod N; and said step (c) is a step of calculating a modular inverse R by the following equation using S and t R=S 2 −(k+t−m) mod N, where m= 0, n, or 2 n and performing the following equation using said modular inverse R s=s′/r mod N=s′R mod N.

Claim 9

The method of claim 1 , wherein, setting k′=k+t−m, said step (c) comprises the steps of: (c-1) calculating w′=k′ mod w, where w is the number of bits which are processed at a time in said modular division by power of 2 and is less than k′; (c-2) calculating n′=−N −1 mod 2 w ; (c-3) calculating s′=Sn′ mod 2 w ; (c-4) calculating q=S+s′N; (c-5) calculating q/2 w ; (c-6) executing said steps (c-3), (c-4) and (c-5) K=[k′/w] times, further executing said steps (c-3), (c-4) and (c-5) once again after replacing said w with w′, and for each round of K+1 executions of said steps, updating said S with the calculation result by said step (c-5), the notation [a] representing a maximum integer not exceeding a given real number a; and (c-7) outputting, as said modular inverse R, the calculation result by said step (c-5) in the last round of said K+1 executions.

Claim 10

The method of claim 1 , wherein: a precalculated value n′=−N −1 mod 2 w is prestored in storage means; and, setting k′=k+t−m, said step (c) comprises the steps of: (c-1) calculating w′=k′ mod w, where w is the number of bits which are processed at a time in said modular division by power of 2 and is less than k′; (c-2) calculating s′=Sn′ mod 2 w : (c-3) calculating q=S+s′N; (c-4) calculating q/2 w ; (c-5) executing said steps (c-2), (c-3) and (c-4) K=[k′/w] times, further executing said steps (c-2), (c-3) and (c-4) once again after replacing said w with w′, and for each round of K+1 executions of said steps, updating said S with the calculation result by said step (c-4), the notation [a] representing a maximum integer not exceeding a given real number a; and (c-6) outputting, as said modular inverse R, the calculation result by said step (c-4) in the last round of said K+1 executions.

Claim 11

The method of claim 1 , wherein said step (a) comprises the steps of: (a-1) calculating w′=t mod w, where w is the number of bits which are processed at a time in said modular division by power of 2 and is less than t; (a-2) calculating n′=−N −1 mod 2 w ; (a-3) calculating s′=Xn′ mod 2 w ; (a-4) calculating q=X+s′N; (a-5) calculating q/2 w ; (a-6) executing said steps (a-3), (a-4) and (a-5) K=[k/w] times, further executing said steps (a-3), (a-4) and (a-5) once again after replacing said w with w′, and for each round of K+1 executions of said steps, updating said S with the calculation result by said step (a-5), the notation [a] representing a maximum integer not exceeding a given real number a; and (a-7) outputting, as said modular inverse R, the calculation result by said step (a-5) in the last round of said K+1 executions.

Claim 12

The method of claim 1 , wherein: a precalculated value n′=−N −1 mod 2 w is prestored in storage means; and said step (a) comprises the steps of: (a-1) calculating w′=t mod w, where w is the number of bits which are processed at a time in said modular division by power of 2 and is less than t; (a-2) calculating s′=Xn′ mod 2 w ; (a-3) calculating q=X+s′N; (a-4) calculating q/2 w ; (a-5) executing said steps (a-2), (a-3) and (a-4) K=[k/w] times, further executing said steps (c-2), (c-3) and (c-4) once again after replacing said w with w′, and for each round of K+1 executions of said steps, updating said S with the calculation result by said step (a-4), the notation [a] representing a maximum integer not exceeding a given real number a; and (a-6) outputting, as said modular inverse R, the calculation result by said step (a-4) in the last round of said K+1 executions.

Claim 13

The method of claim 1 , wherein, setting k′=−(k+t−m), said step (c) comprises the steps of: (c-1) calculating w′=k′ mod w, where w is the number of bits which are processed at a time in said modular multiplication by power of 2 and is less than or equal to M; (c-2) calculating n″=[2 n+M−1 /N], where M is the number of bits that a calculation apparatus used processes at a time; (c-3) obtaining the value s of upper M bits of said S and calculating t′=[sn″/2 2M−w−1 ], the notation [a] representing a maximum integer not exceeding a given real number a; (c-4) calculating S′=S2 w −t′N; (c-5) comparing said S′ and N and, if S′>N, repeating updating S′←S′−N to obtain S′ which satisfies 0≦S′<N; (c-6) executing said steps (c-3), (c-4) and (c-5) K=[k′/w] times, further executing said steps (c-3), (c-4) and (c-5) once again after replacing said w with w′, and for each round of K+1 executions of said steps, updating said S with S′−N obtained at that time; and (c-7) outputting, as said modular inverse R, the calculation result S′ by the last round of said K+1 executions.

Claim 14

The method of claim 1 , wherein: a precalculated value n″=[2 n+M−1 /N] is prestored in storage means; and, setting k′=−(k+t−m), said step (c) comprises the steps of: (c-1) calculating w′=k′ mod w, where w is the number of bits which are processed at a time in said modular division by power of 2 and is less than or equal to M, where M is the number of bits which a calculating apparatus used processes at a time; (c-2) obtaining the value s of upper M bits of said S and calculating t′=[sn″/2 2M−w−1 ], the notation [a] representing a maximum integer not exceeding a given real number a; (c-3) calculating S′=S2 w −t′N; (c-4) comparing said S′ and N and, if S′>N, repeating updating S′←S′−N to obtain S′ which satisfies 0≦S′<N; (c-5) executing said steps (c-2), (c-3) and (c-4) K=[k′/w] times, further executing said steps (c-2), (c-3) and (c-4) once again after replacing said w with w′, and for each round of said K+1 executions of said steps, updating said S with S′−N obtained at that time; and (c-6) outputting, as said modular inverse R, the calculation result S′ by the last round of said K+1 executions.

Claim 15

The method of claim 1 , wherein said t is equal to a predetermined number of w bits and said input values X and N are expressed in units of said predetermined number w of bits, said step (a) comprising the steps of: (a-1) calculating n′=−N mod 2 w ; (a-2) calculating s′=Xn′ mod 2 w from said n′ and X; (a-3) calculating q=X+s′N from said s′, X and N; (a-4) calculating division q/2 w from said q and w; (a-5) executing said steps (a-2), (a-3) and (a-4) K=the number of times using the calculation result of said step (a-4) as an updated value X; and (a-6) further executing said steps (a-2), (a-3) and (a-4) with k mod w as an updated w using said X obtained in said step (a-5), and outputting the resulting value as the result Y.

Claim 16

The method of claim 1 , where said t is equal to a predetermined number w of bits and said input values X and N are expressed in units of said predetermined number w of bits, a precalculated value n′=−N −1 mod 2 w being prestored in storage means, said step (a) comprising the steps of: (a-1) calculating s′=Xn′ mod 2 w from said n′ and X; (a-2) calculating q=X+s′N from said s′, X and N; (a-3) calculating division q/2 w from said q and w; (a-4) executing said steps (a-1), (a-2) and (a-3) K=the number of times using the calculation result of said step (a-3) as an updated value X; and (a-5) further executing said steps (a-2), (a-3) and (a-4 ) with k mod w as an updated w using said X obtained in said step (a-4), and outputting the resulting value as a result Y.

Claim 17

The method of claim 1 , where said t is equal to a negative integer equal to −w, said w being a predetermined number of bits, and said input values X and N are expressed in units of said predetermined number w of bits, letting the number of bits which are processed at a time by hardware for said modular inversion be represented by M, said step (a) comprising the steps of: (a-1) calculating n′=[2 n+M−1 /N], the notation [a] representing a maximum integer not exceeding a given real number a; (a-2) calculating t′=[sn′/2 M−w−1 ] using said n′ and the value s of upper M bits of said X; (a-3) calculating S′=X2 w −t′N from said X, N, t′ and w; (a-4) comparing said S′ and N, and if S′>N, repeating updating S′←S′−N to obtain S′ which satisfies 0≦S′<N as an updated value S′, and if S′≦N, obtaining said value S′ as an updated value S′; (a-5) executing said steps (a-2), (a-3) and (a-4) K=[k/w] times using said S′ obtained in said step (a-4); and (a-6) further executing said steps (a-2), (a-3) and (a-4) with k mod w as an updated value w using said value S′ obtained in said step (a-5), and outputting the resulting value S′ as the result Y.

Claim 18

The method of claim 1 , where said t is equal to a predetermined number of bits, said input values X and N are expressed in units of said predetermined number w of bits, in which, letting the number of bits which are processed at a time by hardware for said modular inversion, a precalculated value n′=[2 n+M−1 /N] is prestored in storage means, said step (a) comprising the steps of: (a-1) calculating t′=[sn′/2 2M−w−1 ] using said n′ and the value s of upper M bits of said X; (a-2) calculating S′=X2 w −t′N from said X, N, t′ and w; (a-3) comparing said S′ and N, and if S′>N, repeating updating S′←S′−N to obtain S′ which satisfies 0≦S′≦N as an updated value S′, and if S′>N, obtaining said value S′ as an updated value S′; (a-4) executing said steps (a-1), (a-2) and (a-3) K=[k/w] times using said S′ obtained in said step (a-3 ); and (a-5) further executing said steps (a-1), (a-2) and (a-3) with k mod w as an updated value w using said value S′ obtained in said step (a-4), and outputting the resulting value S′ as the result Y.

Claim 21

The apparatus of claim 18 , wherein said calculating means by power of 2 comprises: comparison means for determining whether m−k−t is positive or negative; and means which, if said determination result is negative, calculates R=S 2− (m−k−t) mod N and, if said determination result is positive, calculates R=S 2 m−k−t mod N.

Claim 22

The apparatus of claim 18 , wherein: said information security service utilizes an elliptic curve E/GF(p) over GF(p); said modular inversion is a modular inversion in the calculation of λ in the following equations for calculating, from two points (x 1 , y 1 ) and (x 2 , y 2 ) on said elliptic curve E/GF(p), a point (x 3 , y 3 ) of the sum of said two points λ=( y 2 −y 1 )/( x 2 −x 1 )mod p x 3 =λ 2 −x 1 −x 2 mod p y 3 =λ( x 1 −x 3 )− y 1 mod p and, letting said λ be represented by the following equation with y=y 2 −y 1 and X=x 2 −x 1 λ=(y 2 −y 1 )(x 2 −x 1 ) −1 mod p=yX −1 mod p: said input means inputs p as said N; said dividing means by power of 2 calculates Y for said X and p by the following calculation Y=X 2 −t mod p: said extended GCD calculating means calculates S and k by the following equation using said Y and p S=bgcd ( Y,p )= Y −1 2 k mod p; and said calculating means by power of 2 calculates a modular inverse X′ by the following equation using said S and t X′=S 2 −(k+t−m) mod p, where m= 0, n or 2 n and calculates λ by the following equation using said modular inverse X′ λ= yX ′ mod p.

Claim 23

The apparatus of claim 18 , wherein: said information security service utilizes a digital signature scheme ESIGN; and, letting the following equation, which is part of a digital signature generating process, y=w /( kx k−1 )mod p where x, k, w are integers satisfying 0<x<pq, 0≦w<p, p and q being primes be represented by the following equation y=w/ ( kx k−1 )mod p=wX −1 mod p: said input means includes means for calculating X=kx k−1 , and inputs p as said value N; said dividing means by power of 2 calculates Y by the following equation with X′=X −1 mod p, Y=X 2 −t mod p; said extended binary GCD calculating means calculates S and k by the following equation using said Y and p S=bgcd ( Y, p )= Y −1 2 k mod p; and said calculating means by power of 2 calculates a modular inverse X′ by the following equation using said S and t X′=S 2 −(k+t−m) mod p, where m= 0 , n or 2 n, and performing the following equation using said modular ø inverse X′ y=wX −1 mod p=wX ′ mod p.

Claim 24

The apparatus of claim 18 , wherein: said information security service utilizes a digital signature scheme RSA; and, setting R=r −1 mod N in the following equation which is part of a blind signature generating process s ′=( r e m ) d mod N s=s′/r mod N where r, m, e, d are integers satisfying 0<r, m<N and 0<e, d<ø(N) said input means inputs x as said value X and stores it in said storage means; said dividing means by power of 2 calculates Y by the following equation Y=r2 −(k+t−m) mod N where m=0, n or 2n; said extended binary GCD calculating means calculates S and k by the following equation using said Y and N S=bgcd ( Y, N )= Y −1 2 k mod N; and said calculating means by power of 2 calculates a modular inverse R by the following equation using said S and t R=S 2 −(k+t−m) mod N where m= 0, n or 2 n and performs the following equation using said modular inverse R s=s′/r mod N=s′R mod N.

Claim 25

The apparatus of claim 18 , where said t is equal to a predetermined number w of bits, said input values X and N are expressed in units of w bits, said dividing means by power of 2 comprising: X and N storage means for storing said input values X and N, respectively; modular inverse calculating means for performing the following equation, the number M of bits which said division apparatus processes on hardware at a time being set as M=w; n′=−N −1 mod 2 w ; modular multiplication means for performing the following equation using said n′, said X and said w s′=Xn ′ mod 2 w ; multiply/add means for performing the following equation for said N, said X and said s′ q=X+s′N; and dividing means for calculating q/2 −w for said q and said w, and for outputting the calculation result as the result Y of calculation of X2 −w mod N.

Claim 26

The apparatus of claim 18 , where said t is equal to predetermined number w of bits, said input values X and N are expressed in units of w bits, said division apparatus comprising: X and N storage means for storing said input values X and N, respectively; n′ storage means for storing a precalculated value n′=−N mod 2 w , the number M of bits which said division apparatus processes on hardware at a time being set as M=w; modular multiplication means for performing the following equation using said n′, said X and said w s′=Xn ′ mod 2 w ; multiply/add means for performing the following equation for said N, said X and said s′ q=X+s′N; and dividing means for calculating q/2 −w for said q and said w, and for outputting the calculation result as the result Y.

Claim 27

The apparatus of claim 23 , wherein said modular inverse calculating means comprises: means for calculating y=N mod 2 w for said N and said w; and means for calculating n′=−y −1 mod 2 w for said y and said w.

Claim 28

The apparatus of claim 23 , wherein said modular inverse calculating means comprises: n′ storage means for storing said calculated n′ for said input N; and output means for reading out said n′ for said input N from said n′ storage means, and for outputting said read-out value n′ as the output n′ from said modular inverse calculating means.

Claim 29

The apparatus of claim 18 , where said t is equal to a predetermined number w of bits, said input values X, N and input value k′ are expressed in units of w bits, k′ being an integer equal to or greater than 1, said division apparatus comprising: X, N and k′ storage means for storing said input values X, N and k′ respectively; modular inverse calculating means for calculating n′=−N −1 mod 2 w for said N and the number w of bits which are processed by said division apparatus at a time; modular multiplication means for calculating s′=Xn′ mod 2 w using said n′, said X and said w; multiply/add means for calculating q=X+s′N for said N, said X and said s′, dividing means for calculating q/2 −w for said q and said w; and control means for executing the calculations by said modular inverse calculating means, said modular multiplication means, said multiply/add means and said dividing means K=[k′/w] times and further executing said calculations once again after setting k mod w as w, for updating said X in said X storage means with the calculation result by said dividing means for each round of K+1 executions, and for outputting the calculation result by said dividing means in the last round of K+1 executions of said calculations as the result of calculation of X2 −w mod N, the notation [a] being a maximum integer not exceeding a given real number a.

Claim 30

The apparatus of claim 18 , where said t is equal to a predetermined number w of bits, said input values X, N and input k′ are expressed in units of w bits, k′ being an integer equal to or greater than 1, said dividing means by power of 2 comprising: X, N and k′ storage means for storing said input values X, N and k′ respectively; n′ storage means for storing a precalculated value n′=−N −1 mod 2 w ; modular multiplication means for calculating s′=Xn′ mod 2 w using said n′, said X and said w; multiply/add means for calculating q=X+s′N for said N, said X and said s′, dividing means for calculating q/2 −w for said q and said w; and control means for executing the calculations by said modular multiplication means, said multiply/add means and said dividing means K=[k′/w] times and further executing said calculations once again after setting k′ mod w as w, for updating said X in said X storage means with the calculation result by said divide means for each round of K+1 executions, and for outputting the calculation result by said divide means in the last round of K+1 executions of said calculations as the result Y of calculation of X2 −t mod N, the notation [a] being a maximum integer not exceeding a given real number a.

Claim 31

The apparatus of claim 18 , where said t is equal to predetermined number w of bits, said dividing means by power of comprising: X, N and k′ storage means for storing said input values X, N and k′, respectively, k′ being an integer equal to or greater than 1; splitting means for splitting said value k′ into p values w 1 , w 2 , . . . , w p which satisfy k′=w 1 +w 2 + . . . +w p , and for outputting them, w i being greater than 0, where i=1, 2, . . . , p; and p division parts, an i-th one of said p division parts being supplied with values N, X i−1 and w i as the inputs thereto, and comprising: modular inverse calculating means for calculating n′=−N −1 mod 2 w ; modular multiplication means for calculating s′=X i−1 n ′ mod 2 w using said values n′, said X i−1 and said w i ; multiply/add means for calculating q=X i−1 +s′N for said values N, X i−1 and s′; and dividing means by power of 2 for calculating q/2 w i for said values q and w i and for outputting the calculation result as X i ; wherein a first one of said division parts is supplied with said value X as a value X 0 and a p-th one of said p division parts outputs said calculation result X p as the result of calculation of X2 −t mod N.

Claim 32

A computer readable recording medium having recorded thereon a modular inversion program for information security service which inputs n-bit values N and X and a parameter t given as pieces of security information and outputs a modular inverse X −1 2 m of X over a residue class ring or finite field GF(p) Z/NZ where said N is a part of cryptographic key information employed in the security service the input value X is calculated from an encrypted message, a digital signature, a random number or a message to be encrypted and the bit size of each of said X and N is n and said X is equal to or greater than 0 and less than said N, n being an integer equal to or greater than 1, said program comprises: (a) a step of storing said input parameter t in t storage means; (b) a step of storing said input value N in N storage means; (c) a step of calculating Y by the following equation using said stored values t and N and said input value X Y=X 2 −t mod N; (d) a step of performing the following extended GCD algorism S=bgcd ( Y, N )= Y −1 2 k mod N; for said stored input value N and said calculation result Y to obtain S and k; (e) a step of performing the following calculation using said stored input value N and parameter t and said S and k R=S 2 −(k+t−m) mod N, where: m=0, n, or 2n; and (f) a step of outputting said calculation result R as the modular inverse of said X to be used for calculation of an encrypted message, a decrypted message or a digital signature in the information security service.

Claim 33

A computer readable recording medium having recorded thereon a modular inversion program for information security service which inputs n-bit values N and X and a parameter t given as pieces of security information and outputs a modular inverse X −1 2 m of X over a residue class ring or finite field GF(p) Z/NZ where said N is a part of cryptographic key information employed in the security service the input value X is calculated from an encrypted message, a digital signature, a random number or a message to be encrypted and the bit size of each of said X and N is n and said X is equal to or greater than 0 and less than said N, n being an integer equal to or greater than 1, said program comprises: (a) a step of storing said input parameter t in t storage means; (b) a step of storing said input value N in N storage means; (c) a step of calculating Y by the following equation using said stored values t and N and said input value X Y=X 2 −t mod N; (d) a step of performing the following extended GCD algorism S=bgcd ( Y, N )= Y −1 2 k mod N; for said stored input value N and said calculation result Y to obtain S and k; (e) a step of performing the following calculation using said stored input value N and parameter t and said S and k R=S 2 −(k+t−m) mod N, where: m=0, n, or 2n; and (f) a step of outputting said calculation result R as the modular inverse of said X to be used for calculation of an encrypted message, a decrypted message or a digital signature in the information security service.

Claim 34

The recording medium of claim 30 , wherein said program further comprising: (g) a step of storing said extended binary GCD calculation results S and k in S storage means and k storage means, respectively; and (h) a step of determining whether m−k−t is positive or negative using said stored k and said t and said m; and wherein said R calculating step (e) is a step of calculating R=S 2 −(k+t−m) mod N if said determination result is negative, and calculating R=S 2 m−k−t mod N if said determination result is positive.

Claim 35

The recording medium of claim 30 , wherein: said information security service utilizes an elliptic curve E/GF(p) over GF(p); said modular inversion in said program is a modular inversion in the calculation of λ in the following equations for calculating, from two points (x 1 , y 1 ) and (x 2 , y 2 ) on said elliptic curve E/GF(p), a point (x 3 , y 3 ) of the sum of said two points λ=( y 2 −y 1 )/( x 2 −x 1 )mod p x 3 =λ 2 −x 1 −x 2 mod p y 3 =λ( x 1 −x 3 )− y 1 mod p; and, letting said λ being represented by the following equation with y=y 2 −y 1 and X=x 2 −x 1 λ=(y 2 −y 1 )(x 2 −x 1 ) −1 mod p=yX −1 mod p: said N storing step (b) is a step of storing said p as said N, said Y calculating step (c) is a step of calculating Y by the following equation using said p as said N Y=X 2 −t mod p; said binary GCD calculating (d) is a step of calculating S and k by the following equation using said p as said N S=bgcd ( Y,p )= Y −1 2 k mod p; and said modular inverse R calculating step (e) is a step of calculating X′ as said modular inverse R by the following equation X′=S2 −(k+t−m) mod p where m=0, n or 2n, and calculating λ by the following equation using said modular inverse X′ λ=yX′ mod p.

Claim 36

The recording medium of claim 30 , wherein: said information security service utilizes a digital signature scheme ESIGN; and, letting the following equation, which is part of a digital signature generating process, y=w/ ( kx k−1 )mod p where x, k, w are integers satisfy 0<x<pq, 0≦w<p, p and q being primes be represented by the following equation y=w/ ( kx k−1 )mod p=wX −1 mod p X=kx k−1 : said N storing step (b) is a step of storing said p as said N; said Y calculating step (c) is a step of setting X′=X −1 mod p and calculating Y by the following calculation using said p as said N Y=X 2 −t mod p; said binary GCD calculating step (d) is a step of calculating S and k by the following equation using said p as said N S=bgcd ( Y, p )= Y −1 2 k mod p; and said modular inverse calculating step (e) is a step of calculating said X′ as said modular inverse R by the following equation X′=S 2 −(k+t−m) mod p where m= 0, n or 2 n and performing the following equation using said modular inverse X′ y=wX −1 mod p=wX ′ mod p.

Claim 37

The recording medium of claim 30 , wherein: said information security service utilizes a digital signature scheme RSA; and, setting R=r −1 mod N in the following equation which is part of a blind signature generating process; s′= ( r e m ) d mod N s=s′/r mod N where: r, m, e, d are integers satisfy 0<r, m<N and 0<e, d<ø (N): said Y calculating step (c) is a step of calculating Y by the following calculation using said r said input value X Y=r 2 −t mod N; and said modular inverse calculating step (e) is a step of calculating said modular inverse R by the following equation R=S 2 −t mod N and performing the following equation using said modular inverse R S=s′/r mod N=s′R mod N.

Claim 38

The recording medium of claim 30 , where said t is equal to a predetermined value w of bits and said step (c) comprising: (c-1) a step of storing said X and said N in X storage means and N storage means, respectively; (c-2) a modular inverse calculating step of calculating n′=−N −1 mod 2 w for said N stored in said N storage means and said w, and storing said n′ in n′ storage means; (c-3) a step of calculating s′=Xn′ mod 2 w with said n′ stored in said n′ storage means, said X stored in said X storage means and said w, and storing said s′ in s′ storage means; (c-4) a step of calculating q=X+s′N for said N stored in said N storage means, said X stored in said S storage means and said s′ stored in said s′ storage means, and storing said q in q storage means; and (c-5) a step of calculating q/2 w for said q stored in said q storage means and said w, and outputting the calculation result Y.

Claim 39

The recording medium of claim 30 , where said t is equal to a predetermined value w of bits which are processed by a calculating apparatus at a time and a precalculated value n′=−N −1 mod 2 w being prestored in n′ storage means, said step (c) comprising: (c-1) a step of storing said X and said N in X storage means and N storage means, respectively; (c-2) a step of calculating s′=Xn′ mod 2 w using said n′ stored in said n′ storage means, said X stored in said X storage means and said w, and storing said s′ in s′ storage means; (c-3) a step of calculating q=X+s′N for said N stored in said N storage means, said X stored in said X storage means and said s′ stored in said s′ storage means, and storing said q in q storage means; and (c-4) a step of calculating q/2 w for said q stored in said q storage means and said w, and outputting the calculation result Y.

Claim 40

The recording medium of claim 30 , where said t is equal to a predetermined number w of bits, said step (c) comprising: (c-1) a step of storing said X, said N and said k in X storage means, N storage means and k′ storage means, respectively, k′ being an integer equal to or greater than 1; (c-2) a modular inverse calculating step of calculating n′=−N −1 mod 2 w for said N stored in said N storage means and the number w of bits which are processed by a calculating apparatus at a time, and storing said n′ in n′ storage means; (c-3) a step of calculating s′=Xn′ mod 2 w using said n′ stored in said n′ storage means, said X stored in said X storage means and said w, and storing said s′ in s′ storage means; (c-4) a step of calculating q=X+s′N for said N stored in said N storage means, said X stored in said X storage means and said s′ stored in said s′ storage means, and storing said q in q storage means; (c-5) a step of calculating q/2 w for said q stored in said q storage means and said w, and storing the calculation result in storage means; (c-6) a step of calculating w′=k′ mod w for said k′ stored in said k′ storage means and said w, and storing said w′ in w′ storage means; (c-7) a step of executing said steps (c-3), (c-4) and (c-5) K=[k′/w] times, the notation [a] representing a maximum integer not exceeding a given real number a, further executing said steps (c-3 ), (c-4) and (c-5) once again with said w set as said w′ stored in said w′ storage means, and updating said X stored in said storage means with the result of calculation in said step (c-5) for each round of K+1 executions of said steps; and (c-8) a step of outputting, as the calculation result Y, the calculation result in said step (c-5) in the last round of said K+1 executions.

Claim 41

The recording medium of claim 30 , where said t is equal to a predetermined value w of bits, a precalculated value n′=−N −1 mod 2 w being prestored in n′ storage means, said step (c) comprising: (c-1) a step of storing said X, said N and said k′ in X storage means, N storage means and k′ storage means, respectively, k′ being an integer equal to or greater than 1; (c-2) a step of calculating s′=Xn′ mod 2 w using said n′ stored in said n′ storage means, said X stored in said X storage means and said w, and storing said s′ in s′ storage means; (c-3) a step of calculating q=X+s′N for said N stored in said N storage means, said X stored in said X storage means and said s′ stored in said s′ storage means, and storing said q in q storage means; (c-4) a step of calculating q/2 w for said q stored in said q storage means and said w, and storing the calculation result in storage means; (c-5) a step of calculating w′=k′ mod w for said k stored in said k′ storage means and said w, and storing said w′ in w′ storage means; (c-6) a step of executing said steps (c-2), (c-3) and (c-4) K=[k′/w] times, the notation [a] representing a maximum integer not exceeding a given real number a, further executing said steps (c-2), (c-3) and (c-4) once again with said w set as said w′ stored in said w′ storage means, and updating said X stored in said storage means with the result of calculation in said step (c-4) for each round of K+1 executions of said steps; and (c-7) a process of outputting, as the calculation result Y, the calculation result in said step (c-4) in the last round of said K+1 executions.