There is a technique of using an electronic signature for verifying an author of electronic data.
The electronic signature is created by a specific signature generation algorithm by using electronic data, a secret key, and a random number. The electronic signature is communicated together with the electronic data.
A receiver of the electronic data verifies the electronic data by a specific signature verification algorithm by using the received electronic data, the received electronic signature, and a public key of a signer. That is, the receiver of the electronic data determines whether or not the received electronic signature was generated by using the secret key corresponding to the public key. Then, if the received electronic signature was generated by using the secret key corresponding to the public key, it is verified that the received electronic data was created by an owner of the secret key (the signer).
Thus, if the secret key is disclosed to another person, there is a risk that the electronic signature may be forged and electronic data may be communicated by another person posing as the owner of the secret key.
If the random number used in generating the electronic signature is disclosed to another person, the secret key may be identified based on the electronic signature and the random number.
Thus, as in the case of disclosure of the secret key, the electronic signature may be forged and electronic data may be communicated by another person posing as the owner of the secret key.
By performing timing analysis of processing time of an arithmetic process for generating an electronic signature, it may be possible to obtain a numerical value (for example, a secret key or a random number) used in the arithmetic process (see Non-Patent Literature 1).
For example, in a signature generation algorithm (and a signature verification algorithm) of elliptic curve cryptography, such as EC-Schnorr or ECDSA, an elliptic scalar multiplication kG is performed by which a point G on an elliptic curve is scalar-multiplied by a random number k. The signature generation algorithm (and the signature verification algorithm) is discussed in Non-Patent Literature 2.
A conventional elliptic scalar multiplication kG is performed as shown below.
[Formula 1]                Step 1. R=G;        Step 2. i=t−1, then repeat Steps 2-1 to 2-4 until i=0;                    Step 2-1. R[0]=2R;            Step 2-2. R[1]=R[0]+G;            Step 2-3. R=R[k[i]];            Step 2-4. i - - -;                        Step 3. Return R;        where        t: bit count of k        k[i]: bit value of the i-th bit from the least significant bit        R[k[i]]: R[0] if k[i]=0, or R[1] if k[i]=1.        
The above computation method will be called an Add-Double-Always method.
In the Add-Double-Always method, k[t] must be 1. Thus, a bit count t of the random number k varies depending on the value of the random number k. For example, assume that the random number k is represented by 32 bits. If the most significant bit of the random number k is 1, the bit count t is “32”. If the most significant 12 bits of the random number k are 0, the bit count t changes to “20(=32−12)”.
That is, computation time varies depending on the value of the random number k, and it may be possible to identify the random number k by timing analysis.
An elliptic scalar multiplication kG based on a modified Add-Double-Always method is shown below.
[Formula 2]                Step 1. R=0;        Step 2. i=t, then repeat Steps 2-1 to 2-4 until i=0;                    Step 2-1. R[0]=2R;            Step 2-2. R[1]=R[0]+G;            Step 2-3. R=R[k[i]];            Step 2-4. i - - -;                        Step 3. Return R;        
In the above computation method, k[t] does not have to be 1. Thus, the bit count t of the random number k is a fixed value, not varying with the value of the random number k.
However, in Step 2-1, if the most significant bit of the random number k is 1, doubling of a variable R that is an infinite point (R=0) is performed only once. If a plurality of most significant bits are 0, the doubling of the variable R that is the infinite point is performed a plurality of times. Further, computation time varies between the doubling of the variable R that is the infinite point and the doubling of the variable R that is not the infinite point.
Thus, the computation time varies depending on the value of the random number k, and it may be possible to identify the random number k by timing analysis.
In the signature generation algorithm (and the signature verification algorithm) of elliptic curve cryptography, it is necessary to perform a multiple-precision operation process.
A residue operation “a/2 mod p” performed in the multiple-precision operation process is shown below, where “a” represents a multiple-precision integer, “p” represents a prime number, and “mod” represents a residue operator.
[Formula 3]                Step 1. if a is even, then c=a>>1;        Step 2. else c=a+p;c=c>>1;        Step 3. Return c; [Formula 3]        where        x>>1: right-shift by 1 bit the bit sequence x.        
In the above residue operation, if “a” is even, a shift operation is performed once. If “a” is odd, a shift operation and an addition are each performed once.
That is, computation time varies depending on the value of “a”, and it may be possible to identify “a” by timing analysis and to identify the random number k based on “a”.
A zero determination operation performed in the multiple-precision operation process is shown below. The zero determination operation determines whether or not the value of a multiple-precision integer b is zero. The multiple-precision integer b is expressed as a value in which a plurality of words (integer values) are concatenated.
[Formula 4]
Process: Determine whether or not a word in “b” is zero sequentially from the most significant word.                Condition 1: If a word is non-zero, determine that “b” is non-zero, and end.        Condition 2: If all words are zero, determine that “b” is zero, and end.        
In the above zero determination operation, the nearer the position of a non-zero word is to the most significant word, the shorter computation time becomes.
That is, the computation time varies depending on the value of “b”, and it may be possible to identify the random number k by timing analysis.
USPTO Backgrounds
USPTO Backgrounds