# US 8,280,039 B2 · Signature generating device, signature generating method and signature generating program

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,280,039 B2
- Document ID: US8280039B2
- Status: Granted
- Kind: B2
- Application number: 12/158,033
- Filed: 2006-12-26
- Published: 2009-04-09
- Granted: 2012-10-02
- Earliest claimed: 2005-12-28
- Assignees: Panasonic Corporation
- Inventors: Yuichi Futa; Motoji Ohmori; Masahiro Mambo
- Web page: https://patentgrep.com/patent/US8280039B2

## CPC

- H04L 9/002: {Countermeasures against attacks on cryptographic mechanisms (network architectures or network communication protocols for protection against malicious traffic H04L63/1441)}
- H04L 9/3013: {involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems}
- H04L 9/3073: {involving pairings, e.g. identity based encryption [IBE], bilinear mappings or bilinear pairings, e.g. Weil or Tate pairing}
- H04L 9/3252: {using DSA or related signature schemes, e.g. elliptic based signatures, ElGamal or Schnorr schemes}
- H04L 2209/08: Randomization, e.g. dummy operations or using noise
- H04L 2209/127: Trusted platform modules [TPM]
- H04L 2209/16: Obfuscation or hiding, e.g. involving white box
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A signature generation apparatus is capable of making a value used in signature generation processing difficult to analyze. In the signature generation apparatus, a random number generation module generates a len-bit random number u, a selection module converts the generated random number u into a bit expression, and acquires element pairs corresponding to the bit values from a table memory unit. A random element generation module applies a basic operation of a first group G and a second group to all acquired element pairs, and calculates an element Pk on the first group G and an element Pak on the second group Ga. The signature generation apparatus generates a digital signature S for a message m with use of a transformation module, a main operation module, an inverse transformation module, a multiplication module, a division module, and a signature data generation module.

## Claims

### Claim 1

A signature generation apparatus for generating a digital signature for a message by applying a power operation, the power operation being a basic operation performed a plurality of times with respect to a basic element P in a group G and a basic element Pa in a group Ga, and security of the digital signature being based on a discrete logarithm problem of the group G and the group Ga, the signature generation apparatus comprising:
a split value storage unit storing a plurality of split groups, the plurality of split groups corresponding to a plurality of numbers, such that (i) each split group, of the plurality of split groups, includes a plurality of split pairs, (ii) each split pair, of the plurality of split pairs of each respective split group of the plurality of split groups, includes a first split value and a second split value, (iii) each first split value of the plurality of split groups is an element that belongs to the group G and is calculated by applying, to the basic element P, a power operation in which a power is an arbitrary positive integer, and (iv) each second split value of the plurality of split groups is an element that belongs to the group Ga, wherein each respective second split value is calculated by applying, to the basic element Pa, a power operation in which a power is the arbitrary positive integer used to calculate the first split value of the split pair including the respective second split value;
a selection unit selecting a number u randomly from among the plurality of numbers, and selecting a split group, of the plurality of split groups, corresponding to the selected number u;
a generation unit (i) applying a basic operation of the group G to two or more of the first split values in the selected split group, so as to generate a first exponential element, and (ii) applying a basic operation of the group Ga to the second split values in the selected split group that correspond to the two or more first split values in the selected split group, so as to generate a second exponential element; and
a signature unit (i) transforming each of (a) the generated first exponential element and (b) the message into an element in the group Ga, (ii) applying an operation of the group Ga to the transformed first exponential element, the transformed message and the second exponential element, so as to calculate a first discrete logarithm and a second discrete logarithm, and (iii) generating the digital signature for the message with use of the calculated first and second discrete logarithms.

### Claim 2 (depends on 1)

The signature generation apparatus of claim 1, wherein
each number of the plurality of numbers is a number expressed as a bit string having a predetermined length, the predetermined length being two bits or longer,
a value of each bit of the bit string of each number corresponds to a split pair of the plurality of split pairs of the plurality of split groups, and
the selection unit transforms the selected number u into a bit string having the predetermined length, and selects, as the selected split group, a split group composed of split pairs corresponding to the value of each bit in the bit string transformed from the selected number u.

### Claim 3 (depends on 2)

The signature generation apparatus of claim 2, wherein
the generation unit applies the basic operation of the group G to the two or more first split values in the selected split group composed of the split pairs corresponding to the value of each bit, so as to generate the first exponential element, and
the generation unit applies the basic operation of the group Ga to the second split values in the selected split group composed of the split pairs (i) corresponding to the value of each bit and (ii) corresponding to each of the two or more first split values, so as to generate the second exponential element.

### Claim 4 (depends on 1)

The signature generation apparatus of claim 1, wherein
the first exponential element includes two or more values, and
the signature unit includes:
a transformation sub-unit applying the power operation of the group Ga to the basic element Pa with use of a hash value of the message as a power of the power operation, so as to transform the hash value into a transformed hash value belonging to the group Ga;
a first operation sub-unit calculating first data with use of one value of the two or more values in the first exponential element;
a second operation sub-unit applying the basic operation of the group Ga to the transformed hash value, so as to calculate a third exponential element belonging to the group Ga;
an inverse transformation sub-unit applying an inverse operation to each of the second exponential element and the third exponential element in one of the group Ga and a subgroup Sa included the group Ga, so as to find the first and second discrete logarithms, the inverse operation being an inverse of the transformation performed in the transformation sub-unit;
a third operation sub-unit calculating second data with use of the first and second discrete logarithms; and
a data generation sub-unit generating the digital signature composed of the first data and the second data.

### Claim 5 (depends on 4)

The signature generation apparatus of claim 4, further comprising:
a transformed private key storage unit storing a transformed private key belonging to the group Ga, the transformed private key being generated by applying the basic operation of the group Ga to the basic element Pa using a private key as a power,
wherein the second operation sub-unit applies the basic operation of the group Ga to (i) an operation result that is an element of the group Ga and is obtained by applying, to the transformed private key, a power operation of the group Ga in which the first data is a power and (ii) the transformed hash value, so as to calculate the third exponential element.

### Claim 6 (depends on 5)

The signature generation apparatus of claim 5, wherein
each of the group G and the group Ga is a multiplicative group of a residue integer ring,
each of the basic operation of the group G and the basic operation of the group Ga is a multiplicative operation that subjects each element in a respective one of the group G and the group Ga to multiplication, and
each of the power operation of the group G and the power operation of the group Ga is an exponentiation having a power value that is a positive integer.

### Claim 7 (depends on 6)

The signature generation apparatus of claim 6, wherein the group Ga is a multiplicative group of Z/nZ with respect to n=p^m×q, where p and q are primes, m is a positive integer, “^” is an operator representing exponentiation, “×” is an operator expressing multiplication, Z is an integer ring, and Z/nZ is a residue integer ring.

### Claim 8 (depends on 7)

The signature generation apparatus of claim 7, wherein the subgroup Sa is a multiplicative group of Z/p^mZ.

### Claim 9 (depends on 8)

The signature generation apparatus of claim 8, wherein m is 2.

### Claim 10 (depends on 4)

The signature generation apparatus of claim 4, wherein
the group G is a group of an elliptic curve,
the subgroup Sa is a group of an anomalous elliptic curve,
each of the basic operation of the group G and the basic operation of the group Ga is an operation that applies addition on an elliptic curve to each element in a respective one of the group G and the group Ga, and
each of the power operation of the group G and the power operation of the group Ga is an operation that applies multiplication on an elliptic curve to a positive integer.

### Claim 11 (depends on 4)

The signature generation apparatus of claim 4, wherein
the group G is a group of an elliptic curve,
the group Ga is a direct product of two anomalous elliptic curves,
each of the basic operation of the group G and the basic operation of the group Ga is an operation that applies addition on an elliptic curve to each element in a respective one of the group G and the group Ga, and
each of the power operation of the group G and the power operation of the group Ga is an operation that applies multiplication on an elliptic curve to a positive integer.

### Claim 12 (depends on 4)

The signature generation apparatus of claim 4, wherein
the inverse transformation sub-unit includes a reduction part reducing an element belonging to the group Ga to an element belonging to the subgroup Sa, and
the inverse transformation sub-unit, with use of the reduction part, reduces each of the second exponential element and the third exponential element to an element belonging to the subgroup Sa, and applies the inverse operation to each of the reduced element belonging to the group Ga, the reduced second exponential element and the reduced third exponential element to find the first discrete logarithm and the second discrete logarithm.

### Claim 13

A signature generation apparatus for generating a digital signature for a message by applying a power operation, the power operation being a basic operation performed a plurality of times with respect to a basic element P in a group G and a basic element Pa in a group Ga, and security of the digital signature being based on a discrete logarithm problem of the group G and the group Ga, the signature generation apparatus comprising:
a split value storage unit storing a plurality of split groups, the plurality of split groups corresponding to a plurality of numbers, such that (i) each split group, of the plurality of split groups, includes a plurality of split pairs, (ii) each split pair, of the plurality of split pairs of each respective split group of the plurality of split groups, includes a first split value and a second split value, (iii) each first split value of the plurality of split groups is an element that belongs to the group G and is calculated by applying, to the basic element P, a power operation in which a power is an arbitrary positive integer, and (iv) each second split value of the plurality of split groups is an element that belongs to the group Ga, wherein each respective second split value is calculated by applying, to the basic element Pa, a power operation in which a power is the arbitrary positive integer used to calculate the first split value of the split pair including the respective second split value;
a selection unit selecting a number u randomly from among the plurality of numbers, and selecting a split pair, of the plurality of split pairs of the plurality of split groups, corresponding to the selected number u; and
a signature unit (i) transforming each of (a) the message and (b) the first split value in the selected split pair into an element in the group G, (b) applying an operation of the group Ga to the transformed first split value, the transformed message and the second split value in the selected split pair, so as to solve the discrete logarithm problem and calculate first and second discrete logarithms, and (iii) generating the digital signature for the message with use of the calculated first and second discrete logarithms.

### Claim 14

An integrated circuit of a signature generation apparatus for generating a digital signature for a message by applying a power operation, the power operation being a basic operation performed a plurality of times with respect to a basic element P in a group G and a basic element Pa in a group Ga, and security of the digital signature being based on a discrete logarithm problem of the group G and the group Ga, the integrated circuit comprising:
a split value storage unit storing a plurality of split groups, the plurality of split groups corresponding to a plurality of numbers, such that (i) each split group, of the plurality of split groups, includes a plurality of split pairs, (ii) each split pair, of the plurality of split pairs of each respective split group of the plurality of split groups, includes a first split value and a second split value, (iii) each first split value of the plurality of split groups is an element that belongs to the group G and is calculated by applying, to the basic element P, a power operation in which a power is an arbitrary positive integer, and (iv) each second split value of the plurality of split groups is an element that belongs to the group Ga, wherein each respective second split value is calculated by applying, to the basic element Pa, a power operation in which a power is the arbitrary positive integer used to calculate the first split value of the split pair including the respective second split value;
a selection unit selecting a number u randomly from among the plurality of numbers, and selecting a split group, of the plurality of split groups, corresponding to the selected number u;
a generation unit (i) applying a basic operation of the group G to two or more of the first split values in the selected split group, so as to generate a first exponential element, and (ii) applying a basic operation of the group Ga to the second split values in the selected split group that correspond to the two or more first split values in the selected split group, so as to generate a second exponential element; and
a signature unit (i) transforming each of (a) the generated first exponential element and (b) the message into an element in the group Ga, (ii) applying an operation of the group Ga to the transformed first exponential element, the transformed message and the second exponential element, so as to calculate a first discrete logarithm and a second discrete logarithm, and (iii) generating the digital signature for the message with use of the calculated first and second discrete logarithms.
