Cryptographic apparatus and method

Patent metadata

Field	Value
Publication number	US-2016248585-A1
Application number	US-201414259307-A
Country	US
Kind code	A1
Filing date	Apr 23, 2014
Priority date	Oct 31, 2011
Publication date	Aug 25, 2016
Grant date	—

Abstract

A cryptographic apparatus and method is provided with which the circuit scale does not become large, even if a circuit that makes exposure of the secret key difficult by using Differential Power Analysis is equipped. First key data (dQ) representing a quotient obtained by exponentiating, with respect to respect prime data (pi), using respective random number setting data representing exponents (rpi) corresponding to respective prime data, and then obtaining multiplication data by multiplying the respective exponentiated data, and then dividing secret key data (d) by the multiplication data, and second key data (dR) representing a reminder obtained by dividing the secret key data by the multiplication data are stored in a storing unit in advance, and using the first key data and the second key data, a decryption process using RSA or ECC having a countermeasure against Differential Power Analysis (DPA) is performed.

First claim

What is claimed is:

1 . A cryptographic apparatus configured to obtain decrypted data by performing an modular exponentiation operation using encrypted data representing a base, secret key data representing an exponent and public key data representing a modulus, comprising:
a storing unit configured to store first key data and second key data in advance, the first key data representing a quotient obtained by exponentiating respective prime data, using respective random number setting data representing an exponent corresponding to the respective prime data, by obtaining multiplication data by multiplying the respective obtained exponentiated data, and then by dividing the secret key data by the multiplication data, the second key data representing a reminder obtained by dividing the secret key data by the multiplication data; a random number generating unit configured to obtain second random number data by exponentiating the respective prime data, using respective first random number data being positive integers equal to or smaller than the random number setting data representing exponents corresponding to the respective prime data and by multiplying the respective obtained exponentiated data, and configured to obtain tamper resistant data by exponentiating the respective prime data, using subtraction data obtained by subtracting the first random number data corresponding to the random number setting data from the random number setting data representing exponents corresponding to the respective prime data and by multiplying the respective obtained exponentiated data; and an modular exponentiation operating unit configured to obtain a first variable by performing a multiplication reminder operation using the first key data and the tamper resistant data as a base with data obtained by subtracting 1 from a maximum bit width length that may be handled in the multiplication reminder operation as a modulus or to obtain the first variable by multiplication of the first key data and the tamper resistant data, configured to obtain a second variable by performing a modular exponentiation operation with the encrypted data as a base, with the second random number data as an exponent and with the public key data as a modulus, and configured to obtain a third variable by performing a modular exponentiation operation with the second variable as a base, with the first variable as an exponent, and with the public key data as a modulus, configured to obtain a fourth variable by performing a modular exponentiation operation with the encrypted data as a base, with the second key data as an exponent, and with the public key data as a modulus, and configured to obtain the decrypted data by performing a multiplication reminder operation with the third variable and the fourth variable as a base and with the public key data as a modulus.

2 . The cryptographic apparatus according to claim 1 , wherein
the modular exponentiation operating unit obtains the first variable by performing a Montgomery multiplication reminder operation using the first key data and the tamper resistant data as a base with data obtained by subtracting 1 from 2 raised to the power of a maximum bit width length that may be handled in the Montgomery multiplication reminder operation as a modulus, and obtains a fifth variable by performing a Montgomery multiplication reminder operation using the third variable and the fourth variable as a base and with the public key data as a modulus; and obtains the encrypted data by performing a Montgomery multiplication reminder operation using the fifth variable and a square of a Montgomery parameter as a base with the public key data as a modulus.

3 . A cryptographic apparatus configured to obtain decrypted data by performing a point scalar multiplication operation using encrypted data, secret key data and public key data, comprising:
a storing unit configured to store first key data and second key data in advance, the first key data representing a quotient obtained by exponentiating respective prime data, using respective random number setting data representing an exponent corresponding to the respective prime data, by obtaining multiplication data by multiplying the respective obtained exponentiated data, and then by dividing the secret key data by the multiplication data, the second key data representing a reminder obtained by dividing the secret key data by the multiplication data; a random number generating unit configured to obtain second random number data by exponentiating the respective prime data, using respective first random number data being positive integers equal to or smaller than the random number setting data representing exponents corresponding to the respective prime data and by multiplying the respective obtained exponentiated data, and configured to obtain tamper resistant data by exponentiating the respective prime data, using subtraction data obtained by subtracting the first random number data corresponding to the random number setting data from the random number setting data representing exponents corresponding to the respective prime data and by multiplying the respective obtained exponentiated data; and a multiplication unit configured to obtain a first variable by performing a multiplication using the first key data and the tamper resistant data; and a point scalar multiplication operating unit configured to obtain a second variable by performing a point scalar multiplication operation using the encrypted data and the second random number data, configured to obtain a third variable by performing a point scalar multiplication using the second variable and the first variable, configured to obtain a fourth variable by performing a point scalar multiplication using the encrypted data and the second key data, and configured to obtain decrypted data by performing a point addition operation using the third variable and the fourth variable.

4 . A cryptographic processing method executed by a computer, comprising:
storing in a storing unit first key data and second key data in advance, the first key data representing a quotient obtained by exponentiating respective prime data, using respective random number setting data representing an exponent corresponding to the respective prime data, by obtaining multiplication data by multiplying the respective obtained exponentiated data, and then by dividing the secret key data by the multiplication data, the second key data representing a reminder obtained by dividing the secret key data by the multiplication data; obtaining second random number data by exponentiating the respective prime data, using respective first random number data being positive integers equal to or smaller than the random number setting data representing exponents corresponding to the respective prime data and by multiplying the respective obtained exponentiated data; obtaining tamper resistant data by exponentiating the respective prime data, using subtraction data obtained by subtracting the first random number data corresponding to the random number setting data from the random number setting data representing exponents corresponding to the respective prime data and by multiplying the respective obtained exponentiated data; obtaining a first variable by performing a multiplication reminder operation using the first key data and the tamper resistant data as a base with data obtained by subtracting 1 from a maximum bit width length that may be handled in the multiplication reminder operation as a modulus or to obtain the first variable by multiplication of the first key data and the tamper resistant data; obtaining a second variable by performing a modular exponentiation operation with the encrypted data as a base, with the second random number data as the exponent and with the public key data as a modulus; obtaining

Assignees

• Fujitsu Ltd

Inventors

• Yajima Jun
• Itoh Kouichi

Classifications

• G09C1/00

  Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00) · CPC title

• H04L9/3066 Primary

  involving algebraic varieties, e.g. elliptic or hyper-elliptic curves · CPC title

• H04L9/003

  for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA] · CPC title

• H04L9/302

  involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes · CPC title

• H04L2209/12

  Details relating to cryptographic hardware or logic circuitry · CPC title