US 6,567,832 B1 · Device, method, and storage medium for exponentiation and elliptic curve exponentiation

An exponent preprocessing unit in an exponentiation device in which the exponent preprocessing unit preprocesses an n-bit exponent k and an operating unit exponentiates a base A by the preprocessed exponent k to compute Ak, the exponent preprocessing unit comprising:

bit string storing means for storing a bit string including a sign bit and the exponent k;
reading means for reading from the bit string storing means a bit pattern composed of the sign bit and a bit sequence made up of a predetermined number of bits, the predetermined number being smaller than n;
bit pattern generating means for generating a new bit pattern based on the bit pattern read by the reading means;
operation pattern specifying means for specifying an operation pattern to be applied to the base A, based on the read bit pattern;
instructing and changing means for instructing the operating unit to perform an operation according to the operation pattern specified by the operation pattern specifying means, and changing the read bit pattern to the new bit pattern and writing the new bit pattern back into the bit string storing means in bit positions from which the bit pattern was read;
read position setting means for having the reading means read a next bit sequence starting from a different bit in the bit string in the bit string storing means;
and
repeat controlling means for having the reading means, the bit pattern generating means, the operation pattern specifying means, the instructing and changing means, and the read position setting means sequentially repeat respective procedures thereof n+1 times.

5 more elements

A preprocessing unit in an elliptic curve exponentiation device in which, when given an elliptic curve E(Fp) modulo a constant p of n bits, a positive integer k no greater than the constant p, and a point A on the elliptic curve E(Fp), the processing unit preprocesses the integer k and an operating unit performs elliptic curve exponentiation on the point A by the preprocessed integer k to compute an exponentiation point kA, the preprocessing unit comprising:

bit string storing means for storing a bit string including a sign bit and the integer k;
reading means for reading from the bit string storing means a bit pattern composed of the sign bit and a bit sequence made up of a predetermined number of bits, the predetermined number being smaller than n;
bit pattern generating means for generating a new bit pattern based on the bit pattern read by the reading means;
operation pattern specifying means for specifying an operation pattern to be applied to the point A, based on the read bit pattern;
instructing and changing means for instructing the operating unit to perform an operation according to the operation pattern specified by the operation pattern specifying means, and changing the read bit pattern to the new bit pattern and writing the new bit pattern back into the bit string storing means in bit positions from which the bit pattern was read;
read position setting means for having the reading means read a next bit sequence starting from a different bit in the bit string in the bit string storing means;
and
repeat controlling means for having the reading means, the bit pattern generating means, the operation pattern specifying means the instructing and changing means, and the read position setting means sequentially repeat respective procedures thereof n+1 times.

5 more elements

An exponentiation device for computer Ak using an n-bit positive integer k and an integer A, comprising:

storing means having an exponent holding area of n+1 bits, a sign holding area for holding a sign, and an intermediate value holding area for holding an intermediate value generated during the computation of Ak;
initializing means for initializing the storing means by setting the integer k in lower order n bit positions in the exponent holding area, a value 0 in an MSB position in the exponent holding area, a positive sign + in the sign holding area, and a constant 1 in the intermediate value holding area;
squaring means for squaring the intermediate value in the intermediate value holding area to obtain a square and replacing the intermediate value in the intermediate value holding area with the square to renew the intermediate value;
judgement object selecting means for selecting the sign in the sign holding area and 3 most significant bits in the exponent holding area, as a judgement object;
judging means for judging whether the judgement object has
(a) a first pattern in which the sign in the sign holding area is the positive sign + and a bit pattern of the 3 most significant bits in the exponent holding area is 011,
(b) a second pattern in which the sign in the sign holding area is the positive sign + and a 1 most significant bit in the exponent holding area is 1,
(c) a third pattern in which the sign in the sign holding area is a negative sign and a bit pattern of 2 most significant bits in the exponent holding area is 10, or
(d) none of the first pattern, the second pattern, and the third pattern;
multiplying means for
(1) if the judgement object has any of the first pattern and the second pattern, multiplying the intermediate value in the intermediate value holding area by the integer A to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value,
(2) if the judgement object has the third pattern, multiplying the intermediate value in the intermediate value holding area by a multiplicative inverse of the integer A to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value, and
(3) if the judgement object has none of the first pattern, the second pattern, and the third pattern, maintaining the intermediate value in the intermediate value holding area intact without performing any operation;
first changing means for changing the sign in the sign holding area to the negative sign − and the bit pattern of the 3 most significant bits in the exponent holding area to 001, if the judgement object has the first pattern;
second changing means for changing the sign in the sign holding area to the positive sign +, if the judgement object has the third pattern;
shifting means for left shifting a bit string of n+1 bits held in the exponent holding area by 1 bit and abandoning any bit that overflows, after procedures required depending on a judgement result by the judging means are carried out;
outputting means for outputting the intermediate value in the intermediate value holding area as Ak;
and
controlling means for firstly having the initializing means initialize the storing means, secondly having the squaring means, the judgement object selecting means, the judging means, the multiplying means, the first changing means, the second changing means, and the shifting means sequentially repeat respective procedures thereof n+1 times, and lastly having the outputting means output the intermediate value in the intermediate value holding area as Ak.

16 more elements

A modular exponentiation device for computing Ak mod p using an n-bit positive integer k, an integer A, and a constant p, comprising:

storing means having an exponent holding area of n+1 bits, a sign holding area for holding a sign, and an intermediate value holding area for holding an intermediate value generated during the computation of Ak mod p;
initializing means for initializing the storing means by setting the integer k in lower order n bit positions in the exponent holding area, a value 0 in an MSB position in the exponent holding area, a positive sign + in the sign holding area, and a constant 1 in the intermediate value holding area;
modular squaring means for squaring the intermediate value in the intermediate value holding area modulo p to obtain a square and replacing the intermediate value in the intermediate value holding area with the square to renew the intermediate value;
judgement object selecting means for selecting the sign in the sign holding area and 3 most significant bits in the exponent holding area, as a judgement object;
judging means for judging whether the judgement object has
(a) a first pattern in which the sign in the sign holding area is the positive sign + and a bit pattern of the 3 most significant bits in the exponent holding area is 011,
(b) a second pattern in which the sign in the sign holding area is the positive sign + and a 1 most significant bit in the exponent holding area is 1,
(c) a third pattern in which the sign in the sign holding area is a negative sign − and a bit pattern of 2 most significant bits in the exponent holding area is 10, or
(d) none of the first pattern, the second pattern, and the third pattern;
modular multiplying means for
(1) if the judgement object has any of the first pattern and the second pattern, multiplying the intermediate value in the intermediate value holding area by the integer A modulo p to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value,
(2) if the judgement object has the third pattern, multiplying the intermediate value in the intermediate value holding area by a multiplicative inverse of the integer A modulo p to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value, and
(3) if the judgement object has none of the first pattern, the second pattern, and the third pattern, maintaining the intermediate value in the intermediate value holding area intact without performing any operation;
first changing means for changing the sign in the sign holding area to the negative sign − and the bit pattern of the 3 most significant bits in the exponent holding area to 001, if the judgement object has the first pattern;
second changing means for changing the sign in the sign holding area to the positive sign +, if the judgement object has the third pattern;
shifting means for left shifting a bit string of n+1 bits held in the exponent holding area by 1 bit and abandoning any bit that overflows, after procedures required depending on a judgement result by the judging means are carried out;
outputting means for outputting the intermediate value in the intermediate value holding area as Ak mod p;
and
controlling means for firstly having the initializing means initialize the storing means, secondly having the modular squaring means, the judgement object selecting means, the judging means, the modular multiplying means, the first changing means, the second changing means, and the shifting means sequentially repeat respective procedures thereof n+1 times, and lastly having the outputting means output the intermediate value in the intermediate value holding area as Ak mod p.

16 more elements

An elliptic curve exponentiation device for computing an exponentiation point kA using an elliptic curve E(Fp) modulo a constant p of n bits, a positive integer k no greater than the constant p, and a point A on the elliptic curve E(Fp), comprising:

storing means having a holding area of n+1 bits, a sign holding area for holding a sign, and an intermediate point holding area for holding an intermediate point generated during the computation of the exponentiation point kA;
initializing means for initializing the storing means by setting the integer k in lower order n bit positions in the holding area, a value 0 in an MSB position in the holding area, a positive sign + in the sign holding area, and a point at infinity O in the intermediate point holding area;
elliptic curve doubling means for doubling the intermediate point in the intermediate point holding area to obtain a double point on the elliptic curve E(Fp) and replacing the intermediate point in the intermediate point holding area with the double point to renew the intermediate point;
judgement object selecting means for selecting the sign in the sign holding area and 3 most significant bits in the holding area, as a judgement object;
judging means for judging whether the judgement object has
(a) a first pattern in which the sign in the sign holding area is the positive sign + and a bit pattern of the 3 most significant bits in the holding area is 011,
(b) a second pattern in which the sign in the sign holding area is the positive sign + and a 1 most significant bit in the holding area is 1,
(c) a third pattern in which the sign in the sign holding area is a negative sign − and a bit pattern of 2 most significant bits in the holding area is 10, or
(d) none of the first pattern, the second pattern, and the third pattern,
elliptic curve adding means for
(1) if the judgement object has any of the first pattern and the second pattern, adding the point A and the intermediate point in the intermediate point holding area to obtain a sum point on the elliptic curve E(Fp) and replacing the intermediate point in the intermediate point holding area with the sum point to renew the intermediate point,
(2) if the judgement object has the third pattern, adding an additive inverse of the point A and the intermediate point in the intermediate point holding area to obtain a sum point on the elliptic curve E(Fp) and replacing the intermediate point in the intermediate point holding area with the sum point to renew the intermediate point, and
(3) if the judgement object has none of the first pattern, the second pattern, and the third pattern, maintaining the intermediate point in the intermediate point holding area intact without performing any operation;
first changing means for changing the sign in the sign holding area to the negative sign − and the bit pattern of the 3 most significant bits in the holding area to 001, if the judgement object has the first pattern;
second changing means for changing the sign in the sign holding area to the positive sign +, if the judgement object has the third pattern;
shifting means for left shifting a bit string of n+1 bits held in the holding area by 1 bit and abandoning any bit that overflows, after procedures required depending on a judgement result by the judging means area carried out;
outputting means for outputting the intermediate point in the intermediate point holding area as the exponentiation point kA;
and
controlling means for firstly having the initializing means initialize the storing means, secondly having the elliptic curve doubling means, the judgement object selecting means, the judging means, the elliptic curve adding means, the first changing means, the second changing means, and the shifting means sequentially repeat respective procedures thereof n+1 times, and lastly having the outputting means output the intermediate point in the intermediate point holding area as the exponentiation point kA.

16 more elements

An exponent preprocessing method for use in an exponentiation device that preprocesses an exponent k of n bits and exponentiates a base A by the preprocessed exponent k in an operating unit to compute Ak, the exponent preprocessing method comprising:

a first step for reading, from bit string storing means which stores a bit string including a sign bit and the exponent k, a bit pattern composed of the sign bit and a bit sequence made up of a predetermined number of bits, the predetermined number being smaller than n;
a second step for generating a new bit pattern based on the read bit pattern;
a third step for specifying an operation pattern to be applied to the base A, based on the read bit pattern;
a fourth step for instructing the operating unit to perform an operation according to the operation pattern specified in the third step, and changing the read bit pattern to the new bit pattern and writing the new bit pattern back into the bit string storing means in bit positions from which the bit pattern was read;
a fifth step for setting a start of a bit sequence to be read next, at a different bit in the bit string in the bit string storing means;
and
a sixth step for sequentially repeating the first step, the second step, the third step, the fourth step, and the fifth step n+1 times.

4 more elements

An exponentiation method for computing Ak using an n-bit positive integer k and an integer A, comprising:

a first step for initializing storing means which has an exponent holding area of n+1 bits, a sign holding area for holding a sign, and an intermediate value holding area for holding an intermediate value generated during the computation of Ak, by setting the integer k in lower order n bit positions in the exponent holding area, a value 0 in an MSB position in the exponent holding area, a positive sign + in the sign holding area, and a constant 1 in the intermediate value holding area;
a second step for squaring the intermediate value in the intermediate value holding area to obtain a square and replacing the intermediate value in the intermediate value holding area with the square to renew the intermediate value;
a third step for selecting the sign in the sign holding area and 3 most significant bits in the exponent holding area, as a judgement object;
a fourth step for judging whether the judgement object has
(a) a first pattern in which the sign in the sign holding area is the positive sign + and a bit pattern of the 3 most significant bits in the exponent holding area is 011,
(b) a second pattern in which the sign in the sign holding area is the positive sign + and a 1 most significant bit in the exponent holding area is 1,
(c) a third pattern in which the sign in the sign holding area is a negative sign − and a bit pattern of 2 most significant bits in the exponent holding area is 10, or
(d) none of the first pattern, the second pattern, and the third pattern;
a fifth step for
(1) if the judgement object has any of the first pattern and the second pattern, multiplying the intermediate value in the intermediate value holding area by the integer A to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value,
(2) if the judgement object has the third pattern, multiplying the intermediate value in the intermediate value holding area by the multiplicative inverse of the integer A to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value, and
(3) if the judgement object has none of the first pattern, the second pattern, and the third pattern, maintaining the intermediate value in the intermediate value holding area intact without performing any operation;
a sixth step for changing the sign in the sign holding area to the negative sign − and the bit pattern of the 3 most significant bits in the exponent holding area to 001, if the judgement object has the first pattern;
a seventh step for changing the sign in the sign holding area to the positive sign +, if the judgement object has the third pattern;
an eighth step for left shifting a bit string of n+1 bits held in the exponent holding area by 1 bit and abandoning any bit that overflows, after procedures required depending on a judgement result in the fourth step are carried out;
and
a ninth step for sequentially repeating the second step, the third step, the fourth step, the fifth step, the sixth step, the seventh step, and the eighth step until a bit which was in an LSB (least significant bit) position in the exponent holding area in the first step overflows, and outputting the intermediate value in the intermediate value holding area as Ak.

14 more elements

A modular exponentiation method for computing Ak mod p using an n-bit positive integer k, an integer A, and a constant p, comprising:

a first step for initializing storing means which has an exponent holding area of n+1 bits, a sign holding area for holding a sign, and an intermediate value holding area for holding an intermediate value generated during the computation of Ak mod p, by setting the integer k in lower order n bit positions in the exponent holding area, a value 0 in an MSB position in the exponent holding area, a positive sign + in the sign holding area, and a constant 1 in the intermediate value holding area;
a second step for squaring the intermediate value in the intermediate value holding area modulo p to obtain a square and replacing the intermediate value in the intermediate value holding area with the square to renew the intermediate value;
a third step for selecting the sign in the sign holding area and 3 most significant bits in the exponent holding area, as a judgement object;
a fourth step for judging whether the judgement object has
(a) a first pattern in which the sign in the sign holding area is the positive sign + and a bit pattern of the 3 most significant bits in the exponent holding area is 011,
(b) a second pattern in which the sign in the sign holding area is the positive sign + and a 1 most significant bit in the exponent holding area is 1,
(c) a third pattern in which the sign in the sign holding area is a negative sign − and a bit pattern of 2 most significant bits in the exponent holding area is 10, or
(d) none of the first pattern, the second pattern, and the third pattern;
a fifth step for
(1) if the judgement object has any of the first pattern and the second pattern, multiplying the intermediate value in the intermediate value holding area by the integer A modulo p to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value,
(2) if the judgement object has the third pattern, multiplying the intermediate value in the intermediate value holding area by a multiplicative inverse of the integer A modulo p to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value, and
(3) if the judgement object has none of the first pattern, the second pattern, and the third pattern, maintaining the intermediate value in the intermediate value holding area intact without performing any operation;
a sixth step for changing the sign in the sign holding area to the negative sign − and the bit pattern of the 3 most significant bits in the exponent holding area to 001, if the judgement object has the first pattern;
a seventh step for changing the sign in the sign holding area to the positive sign +, if the judgement object has the third pattern;
an eighth step for left shifting a bit string of n+1 bits held in the exponent holding area by 1 bit and abandoning any bit that overflows, after procedures required depending on a judgement result in the fourth step are carried out;
and
a ninth step for sequentially repeating the second step, the third step, the fourth step, the fifth step, the sixth step, the seventh step, and the eighth step until a bit which was in an LSB position in the exponent holding area in the first step overflows, and outputting the intermediate value in the intermediate value holding area as Ak mod p.

14 more elements

An elliptic curve exponentiation method for computing an exponentiation point kA using an elliptic curve E(Fp) modulo a constant p of n bits, a positive integer k no greater than the constant p, and a point A on the elliptic curve E(Fp), comprising:

a first step for initializing storing means which has a holding area of n+1 bits, a sign holding area for holding a sign, and an intermediate point holding area for holding an intermediate point generated during the computation of the exponentiation point kA, by setting the integer k in lower order n bit positions in the holding area, a value 0 in an MSB position in the holding area, a positive sign + in the sign holding area, and a point at infinity O in the intermediate point holding area;
a second step for doubling the intermediate point in the intermediate point holding area to obtain a double point on the elliptic curve E(Fp) and replacing the intermediate point in the intermediate point holding area with the double point to renew the intermediate point;
a third step for selecting the sign in the sign holding area and 3 most significant bits in the holding area, as a judgement object;
a fourth step for judging whether the judgement object has
(a) a first pattern in which the sign in the sign holding area is the positive sign + and a bit pattern of the 3 most significant bits in the holding area is 011,
(b) a second pattern in which the sign in the sign holding area is the positive sign + and a 1 most significant bit in the holding area is 1,
(c) a third pattern in which the sign in the sign holding area is a negative sign − and a bit pattern of 2 most significant bits in the holding area is 10, or
(d) none of the first pattern, the second pattern, and the third pattern;
a fifth step for
(1) if the judgement object has any of the first pattern and the second pattern, adding the point A and the intermediate point in the intermediate point holding area to obtain a sum point on the elliptic curve E(Fp) and replacing the intermediate point in the intermediate point holding area with the sum point to renew the intermediate point,
(2) if the judgement object has the third pattern, adding an additive inverse of the point A and the intermediate point in the intermediate point holding area to obtain a sum point on the elliptic curve E(Fp) and replacing the intermediate point in the intermediate point holding area with the sum point to renew the intermediate point, and
(3) if the judgement object has none of the first pattern, the second pattern, and the third pattern, maintaining the intermediate point in the intermediate point holding area intact without performing any operation;
a sixth step for changing the sign in the sign holding area to the negative sign − and the bit pattern of the 3 most significant bits in the holding area to 001, if the judgement object has the first pattern;
a seventh step for changing the sign in the sign holding area to the positive sign +, if the judgement object has the third pattern;
an eighth step for left shifting a bit string of n+1 bits held in the holding area by 1 bit and abandoning any bit that overflows, after procedures required depending on a judgement result in the fourth step are carried out;
and
a ninth step for sequentially repeating the second step, the third step, the fourth step, the fifth step, the sixth step, the seventh step, and the eighth step until a bit which was in an LSB position in the holding area in the first step overflows, and outputting the intermediate point in the intermediate point holding area as the exponentiation point kA.

14 more elements

A computer-readable storage medium storing an exponentiation program for computing Ak using an n-bit positive integer k and an integer A, the exponentiation program comprising:

a first step for initializing storing means which has an exponent holding area of n+1 bits, a sign holding area for holding a sign, and an intermediate value holding area for holding an intermediate value generated during the computation of Ak, by setting the integer k in lower order n bit positions in the exponent holding area, a value 0 in an MSB position in the exponent holding area, a positive sign + in the sign holding area, and a constant 1 in the intermediate value holding area;
a second step for squaring the intermediate value in the intermediate value holding area to obtain a square and replacing the intermediate value in the intermediate value holding area with the square to renew the intermediate value;
a third step for selecting the sign in the sign holding area and 3 most significant bits in the exponent holding area, as a judgement object;
a fourth step for judging whether the judgement object has
(a) a first pattern in which the sign in the sign holding area is the positive sign + and a bit pattern of the 3 most significant bits in the exponent holding area is 011,
(b) a second pattern in which the sign in the sign holding area is the positive sign + and a 1 most significant bit in the exponent holding area is 1,
(c) a third pattern in which the sign in the sign holding area is a negative sign − and a bit pattern of 2 most significant bits in the exponent area is 10, or
(d) none of the first pattern, the second pattern, and the third pattern;
a fifth step for
(1) if the judgement object has any of the first pattern and the second pattern, multiplying the intermediate value in the intermediate value holding area by the integer A to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value,
(2) if the judgement object has the third pattern, multiplying the intermediate value in the intermediate value holding area by a multiplicative inverse of the integer A to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value, and
(3) if the judgement object has none of the first pattern, the second pattern, and the third pattern, maintaining the intermediate value in the intermediate value holding area intact without performing any operation;
a sixth step for changing the sign in the sign holding area to the negative sign − and the bit pattern of the 3 most significant bits in the exponent holding area to 001, if the judgement object has the first pattern;
a seventh step for changing the sign in the sign holding area to the positive sign +, if the judgement object has the third pattern;
an eighth step for left shifting a bit string of n+1 bits held in the exponent holding area by 1 bit and abandoning any bit that overflows, after procedures required depending on a judgement result in the fourth step are carried out;
and
a ninth step for sequentially repeating the second step, the third step, the fourth step, the fifth step, the sixth step, the seventh step, and the eighth step until a bit which was in an LSB position in the exponent holding area in the first step overflows, and outputting the intermediate value in the intermediate value holding area as Ak.

14 more elements

A computer-readable storage medium storing a modular exponentiation program for computing Ak mod p using an n-bit positive integer k, an integer A, and a constant p, the modular exponentiation program comprising:

a first step for initializing storing means which has an exponent holding area of n+1 bits, a sign holding area for holding a sign, and an intermediate value holding area for holding an intermediate value generated during the computation of Ak mod p, by setting the integer k in lower order n bit positions in the exponent holding area, a value 0 in an MSB position in the exponent holding area, a positive sign + in the sign holding area, and a constant 1 in the intermediate value holding area;
a second step for squaring the intermediate value in the intermediate value holding area modulo p to obtain a square and replacing the intermediate value in the intermediate value holding area with the square to renew the intermediate value;
a third step for selecting the sign in the sign holding area and 3 most significant bits in the exponent holding area, as a judgement object;
a fourth step for judging whether the judgement object has
(a) a first pattern in which the sign in the sign holding area is the positive sign + and a bit pattern of the most significant 3 bits in the exponent holding area is 011,
(b) a second pattern in which the sign in the sign holding area is the positive sign + and a 1 most significant bit in the exponent holding area is 1,
(c) a third pattern in which the sign in the sign holding area is a negative sign − and a bit pattern of 2 most significant bits in the exponent holding area is 10, or
(d) none of the first pattern, the second pattern, and the third pattern;
a fifth step for
(1) if the judgement object has any of the first pattern and the second pattern, multiplying the intermediate value in the intermediate value holding area by the integer A modulo p to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value,
(2) if the judgement object has the third pattern, multiplying the intermediate value in the intermediate value holding area by a multiplicative inverse of the integer A modulo p to obtain a product and replacing the intermediate value in the intermediate value holding area with the product to renew the intermediate value, and
(3) if the judgement object has none of the first pattern, the second pattern, and the third pattern, maintaining the intermediate value in the intermediate value holding area intact without performing any operation;
a sixth step for changing the sign in the sign holding area to the negative sign − and the bit pattern of the 3 most significant bits in the exponent holding area to 001, if the judgement object has the first pattern;
a seventh step for changing the sign in the sign holding area to the positive sign +, if the judgement object has the third pattern;
an eighth step for left shifting a bit string of n+1 bits held in the exponent holding area by 1 bit and abandoning any bit that overflows, after procedures required depending on a judgement result in the fourth step are carried out;
and
a ninth step for sequentially repeating the second step, the third step, the fourth step, the fifth step, the sixth step, the seventh step, and the eighth step until a bit which was in an LSB position in the exponent holding area in the first step overflows, and outputting the intermediate value in the intermediate value holding area as Ak mod p.

14 more elements

A computer-readable storage medium storing an elliptic curve exponentiation program for computing an exponentiation point kA using an elliptic curve E(Fp) modulo a constant p of n bits, a positive integer k no greater than the constant p, and a point A on the elliptic curve E(Fp), the elliptic curve exponentiation program comprising:

a first step for initializing storing means which has a holding area of n+1 bits, a sign holding area for holding a sign, and an intermediate point holding area for holding an intermediate point generated during the computation of the exponentiation point kA, by setting the integer k in lower order n bit positions in the holding area, a value 0 in an MSB position in the holding area, a positive sign + in the sign holding area, and a point at infinity O in the intermediate point holding area;
a second step for doubling the intermediate point in the intermediate point holding area to obtain a double point on the elliptic curve E(Fp) and replacing the intermediate point in the intermediate point holding area with the double point to renew the intermediate point;
a third step for selecting the sign in the sign holding area and 3 most significant bits in the holding area, as a judgement object;
a fourth step for judging whether the judgement object has
(a) a first pattern in which the sign in the sign holding area is the positive sign + and a bit pattern of the 3 most significant bits in the holding area is 011,
(b) a second pattern in which the sign in the sign holding area is the positive sign + and a 1 most significant bit in the holding area is 1,
(c) a third pattern in which the sign in the sign holding area is a negative sign − and a bit pattern of 2 most significant bits in the holding area is 10, or
(d) none of the first pattern, the second pattern, and the third pattern;
a fifth step for
(1) if the judgement has any of the first pattern and the second pattern, adding the point A and the intermediate point in the intermediate point holding area to obtain a sum point on the elliptic curve E(Fp) and replacing the intermediate point in the intermediate point holding area with the sum point to renew the intermediate point,
(2) if the judgement object has the third pattern, adding an additive inverse of the point A and the intermediate point in the intermediate point holding area to obtain a sum point on the elliptic curve E(Fp) and replacing the intermediate point in the intermediate point holding area with the sum point to renew the intermediate point, and
(3) if the judgement object has none of the first pattern, the second pattern, and the third pattern, maintaining the intermediate point in the intermediate point holding area intact without performing any operation;
a sixth step for changing the sign in the sign holding area to the negative sign − and the bit pattern of the 3 most significant bits in the holding area to 001, if the judgement object has the first pattern;
a seventh step for changing the sign in the sign holding area to the positive sign +, if the judgement object has the third pattern;
an eighth step for left shifting a bit string of n+1 bits held in the holding area by 1 bit and abandoning any bit that overflows, after procedures required depending on a judgement result in the fourth step are carried out;
and
a ninth step for sequentially repeating the second step, the third step, the fourth step, the fifth step, the sixth step, the seventh step, and the eighth step until a bit which was in an LSB position in the holding area in the first step overflows, and outputting the intermediate point in the intermediate point holding area as the exponentiation point kA.

14 more elements

Device, method, and storage medium for exponentiation and elliptic curve exponentiation

Life of this patent

Device, method, and storage medium for exponentiation and elliptic curve exponentiation

Life of this patent

Abstract

Claims38