Exponent calculation apparatus and method, and program

An exponent calculation apparatus for encrypting or decrypting data by calculating xe(mod N) based on three integers x, e, and N, the apparatus comprising:

• an input unit for inputting the three integers x, e, and N;
• a candidate exponents storing unit for storing candidate exponents {l_i} (0≦i≦L−1), the number of the candidate exponents being L;
• a pre-calculation unit for pre-calculating x^{l_i} for each of the candidate exponents {l_i}, which are stored in the candidate exponents storing unit, based on the input integer x;
• a pre-calculated values storing unit for storing the values x^{l_i} obtained by the pre-calculation;
• a dividing unit for dividing the input integer e into a plurality of values {f_i} (0≦i≦F−1) so that each of the values {f_i} corresponds to one of the candidate exponents {l_i};
• a calculation result storing unit for storing a calculation result c;
• a sequential processing unit for sequentially updating the calculation result c for each of the divided values {f_i} (0≦i≦F−1) by using each of the pre-calculated values x^{l_i};
• and
• an output unit for outputting the calculation result c for encrypting or decrypting data afther the calculation result c is update for all the values {f_i} as xe(mod N).

A method for encrypting or decrypting data by calculating xe based on two integers x and e, the method comprising:

• an input step of inputting the two integers x and e;
• a pre-calculation step of pre-calculating x^{l_i} for each of candidate exponents {l_i} (0≦i≦L−1) stored in a candidate exponents storing unit, the number of the candidate exponents being L, based on the input integer x, and storing the values x^{l_i} obtained by the pre-calculation in a pre-calculated values storing unit;
• a dividing step of dividing the input integer e into a plurality of values {f_i} (0≦i≦F−1) so that each of the values {f_i} corresponds to one of the candidate exponents {l_i};
• a sequential processing step of sequentially updating a calculation result c, which is stored in a calculation result storing unit, for each of the divided values {f_i} (0≦i≦F−1) by using each of the pre-calculated values x^{l_i};
• and
• an output step of outputting the calculation result c for encrypting or decrypting data afther the calculation result c is update for all the values {f_i} as xe.

A method for encrypting or decrypting data by calculating xe(mod N) based on three integers x, e, and N, the method comprising:

• an input step of inputting the three integers x, e, and N;
• a pre-calculation step of pre-calculating x^{l_i} for each of candidate exponents {l_i} (0≦i≦L−1) stored in a candidate exponents storing unit, the number of the candidate exponents being L, based on the input integer x, and storing the values x^{l_i} obtained by the pre-calculation in a pre-calculated values storing unit;
• a dividing step of dividing the input integer e into a plurality of values {f_i} (0≦i≦F−1) so that each of the values {f_i} corresponds to one of the candidate exponents {l_i};
• a sequential processing step of sequentially updating a calculation result c, which is stored in a calculation result storing unit, for each of the divided values {f_i} (0≦i≦F−1) by using each of the pre-calculated values x^{l_i};
• and
• an output step of outputting the calculation result c for encrypting or decrypting data afther the calculation result c is update for all the values {f_i} as xe(mod N).

A computer-readable program stored in a computer-readable storage medium, for encrypting or decrypting data by allowing a computer to execute exponent calculation for calculating xe based on two integers x and e, said program comprising codes for causing the computer to perform:

• an input step of inputting the two integers x and e;
• a pre-calculation step of pre-calculating x^{l_i} for each of candidate exponents {l_i} (0≦i≦L−1) stored in a candidate exponents storing unit, the number of the candidate exponents being L, based on the input integer x, and storing the values x^{l_i} obtained by the pre-calculation in a pre-calculated values storing unit;
• a dividing step of dividing the input integer e into a plurality of values {f_i} (0≦i≦F−1) so that each of the values {f_i} corresponds to one of the candidate exponents {l_i};
• a sequential processing step of sequentially updating a calculation result c, which is stored in a calculation result storing unit, for each of the divided values {f_i} (0≦i≦F−1) by using each of the pre-calculated values x^{l_i};
• and
• an output step of outputting the calculation result c for encrypting or decrypting data afther the calculation result c is update for all the values {f_i} as xe.

A computer-readable program stored in a computer-readable storage medium, for encrypting or decrypting data by allowing a computer to execute exponent calculation for calculating Xe(mod N) based on three integers x, e, and N, said program comprising codes for causing the computer to perform:

• an input step of inputting the three integers x, e, and N;
• a pre-calculation step of pre-calculating x^{l_i} for each of candidate exponents {l_i} (0≦i≦L−1) stored in a candidate exponents storing unit, the number of the candidate exponents being L, based on the input integer x, and storing the values x^{l_i} obtained by the pre-calculation in a pre-calculated values storing unit;
• a dividing step of dividing the input integer e into a plurality of values {f_i} (0≦i≦F−1) so that each of the values {f_i} corresponds to one of the candidate exponents {l_i};
• a sequential processing step of sequentially updating a calculation result c, which is stored in a calculation result storing unit, for each of the divided values {f_i} (0≦i≦F−1) by using each of the pre-calculated values x^{l_i};
• and
• an output step of outputting the calculation result c for encrypting or decrypting data afther the calculation result c is update for all the values {f_i} as xe(mod N).