JPH0643808A - Arithmetic unit in finite commutative group - Google Patents

Abstract

(57) [Summary] [Purpose] To reduce the amount of calculation when creating an element of a finite commutative group in which a different random number is applied to the specific element of the finite commutative group. [Configuration] Two or more base random numbers generated from the random number generation unit 1 in the selection diagram are divided into one or more partial random numbers, and each divided partial random number is divided into the public key of the system and the self or the receiver. A constituent element is generated by acting on a specific element of a finite commutative group that is a public key. The definition operation of the finite commutative group and / or the inverse element operation of the operation are performed on the generated two or more constituent elements to combine them to create an element of the finite commutative group. .

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a cryptosystem technique as an information security technique, and particularly in a finite commutative group for realizing a discrete logarithmic cryptosystem by using a computer having a poor computing ability such as an IC card. The present invention relates to an arithmetic unit.

[0002]

2. Description of the Related Art The reason why a plurality of different random numbers act on a specific element of a finite commutative group will be described first.

A large number of public key cryptosystems, ie, discrete logarithm cryptosystems, have been proposed on the grounds of security that the discrete logarithm problem, which is a problem of calculating logarithm on a finite field, is difficult in a large finite field. However, the discrete logarithm problem on the finite field, which is the basis for it, has been studied for a long time, and as a result, many attempts have been made to solve it, and the time taken for the solution has gradually become shorter. Therefore, in order to maintain sufficient security, the radix of the finite field in which the discrete logarithmic cryptosystem is defined needs to be a number of about 512 bits. In addition, not only on finite fields but also discrete logarithmic cryptosystems on elliptic curves have been proposed in recent years. The cryptosystem defined on the elliptic curve has no definitive solution to the discrete logarithm problem on the elliptic curve, which is the basis of its security, at the present time. Does not work structurally. Therefore, it is considered that if the security is the same, it can be realized faster than the encryption method defined in the finite field. In order to maintain the same level of security as a discrete logarithmic cryptosystem on a finite field whose radix is a 512-bit number, the radix of the finite field defining the elliptic curve may be a 96-bit number. In addition, in the Elgamal encryption and the Elgamal signature, which are typical examples of the discrete logarithmic cryptosystem, it is necessary to generate a ciphertext and a signature text by changing random numbers for each communication text. For the Ergamal cipher on finite fields and the Ergamal cipher on elliptic curves, see Nikol Blitz, “Acous in Namba Theory and
"Cryptgrahy" (Neal koblitz, "A Course in Nu
mber Theory and Cryptography ", Springer-Verlag, 198
7). The difficulty of Ergamal signatures on finite fields and discrete logarithm problems are described in detail in "Modern Cryptography" by Shinichi Ikeno and Kenji Koyama (IEICE).

The following describes the procedure of the Elgamal cipher on a finite field, the Elgamal cipher on an elliptic curve, and the Elgamal signature on a finite field, and then the reason why the random numbers to be used in the Elgamal cipher and the Elgamal signature must be changed for each message. I will describe. 1) Ergamal cipher on finite field (1) Key generation The system administrator chooses finite field GF (q). Where q
Is the r-th power p ^r of prime numbers p. Let g be a large element of the finite field GF (q). The system administrator discloses g and GF (q) to the system user as public information of this encryption method. An arbitrary user B of this system selects an arbitrary integer x _B , and on GF (q),

[0005]

[Equation 1]

Calculate Therefore, the user B holds x _B as a private key and y _B as a public key to notify all users.

(2) Encryption Let us consider a case where the plaintext m is secretly communicated from A to B. A secretly chooses a random number k, which is an integer, and uses the random number k and B's public key y _B known only to the following two ciphertexts C ₁ and C ₂
To create.

[0008]

[Equation 2]

[0009]

[Equation 3]

A sends C ₁ and C ₂ to B. At this time, C ₁ determined by (Equation 2) is the first ciphertext, and C ₂ determined by (Equation 3) is C _2.
Is called the second ciphertext.

(3) Decryption B obtains M by calculating the following equation using the secret key x _B known only to itself.

[0012]

[Equation 4]

Either of (Equation 1) (Equation 2) (Equation 3) (Equation 4)
Assuming that these calculations are also performed on GF (q), the plaintext M is GF
(q) It is assumed to be the element above. 2) Elgamal cipher with elliptic curve (1) Key generation
Select E. Here, q is the r-th power of the prime p^r Is.
Also, a group composed of elements of a finite field GF (q) of the elliptic curve E
Be denoted by E (GF (q)). G for E (GF (q))
The source of the upper order is large. System administrators are G and E
(GF (q)) as the public information of this encryption method
To the user. Optional user B of this system is optional
Integer x _BAnd select on E (GF (q))

[0014]

[Equation 5]

Calculate Therefore, user B holds x _B as a secret key and informs all users as Y _B as a public key.

(2) Encryption Consider the case where the plaintext M is secretly communicated from A to B. A secretly chooses a random number k which is an integer, and creates the following two ciphertexts C ₁ and C ₂ using this random number k and the public key Y _B of _B that only the user knows.

[0017]

[Equation 6]

[0018]

[Equation 7]

A sends C ₁ and C ₂ to B. At this time, C ₁ determined by (Equation 6) is the first ciphertext and C ₂ determined by (Equation 7)
Is called the second ciphertext.

(3) Decoding B obtains M by calculating the following equation using x _B which only B knows.

[0021]

[Equation 8]

All the operations of (Equation 5) (Equation 6) (Equation 7) (Equation 8) are performed on E (GF (q)), and the plaintext M,
Y _B and G are elements on the elliptic curve E (GF (q)). 3) Ergamal signature on finite field (1) Key generation The system administrator selects finite field GF (p). Where p is
It is a prime number. Let g be the primitive root on GF (p). The system administrator discloses g and GF (p) to the system user as public information of this encryption method. An arbitrary user A of this system selects an arbitrary integer 0 <x _A <p,
On (p),

[0023]

[Equation 9]

Calculate Therefore, the user A holds x _A as a private key and y _A as a public key to notify all users.

(2) Generation of Signature Consider a case where a signature of plaintext m is communicated from user A to user B. Here, the plaintext m is an integer. A secretly generates a random number k which is an integer, and uses the random number k known only to itself to calculate the next R.

[0026]

[Equation 10]

Next, A is a secret key x _A and R which only A knows.
Using the random number k and the random number k, s that satisfies the following equation is calculated.

[0028]

[Equation 11]

A sends B the plaintext m and the signatures R and s. (3) Verification of signature B uses the public key y _A of _A to check whether the following equation holds.

[0030]

[Equation 12]

If true, authenticate that m was sent from A. Here, (p-
1) is the order of the element g on the finite field, and is (Equation 9) (Equation 1
0) (Equation 12) is assumed to be performed on GF (p), and (Equation 11) assumes that integers with the same remainder divided by (p-1) are the same, and the operation is 0 or more and p-1 or less. The plaintext m is an integer. 4) Reasons why the random numbers acting on the Elgamal cipher and Elgamal signature must be changed for each message (i) In the case of the Elgamal cipher, the principle does not change whether on a finite field or on an elliptic curve. We will discuss the Elgamal cipher.

If the communication texts Ma and Mb are respectively encrypted with the same random number k, two sets of ciphertexts (C ₁ a, C ₂ a) and (C ₁ b, C
₂ b), the relationship of C ₁ a = C ₁ b, Ma / Mb = C ₂ a / C ₂ b is established, and if one set of M and C ₂ is known, all other M are C _{I understand} from ₂ .

(Ii) In the case of Ergamal signature If two sets of signature texts (Ra, sa) and (Rb, sb) are created by signing the communication texts ma and mb with the same random number k, sa * k ≡ (ma-x _A * Ra) (mod p-1) sb * k ≡ (mb-x _A * Rb) (mod p-1) holds, and two sets of R and s and m are public values. Therefore, k and x _A can be solved from these two equations. Knowing A's secret x _A allows forgery of signatures for all other m.

The above restriction on random numbers has a relationship that k ₂ = a * k ₁ + b (a, b: constant) between _two random numbers k ₁ and k ₂ even if they are not always the same random number k. Even in this case, the same method is used to decrypt the ciphertext and forge the signature.

For the above reasons, it is necessary to obtain a new element of the finite commutative group by applying many different random numbers to the specific element on the finite commutative group.

Further, in order to realize the above-mentioned encryption method and signature method in a practical time while keeping high security, dedicated hardware and a high-performance computer have been conventionally required. However, with the increasing need for information security in society, it has been desired to realize public key cryptography and digital signature on an IC card that has a lower calculation capacity than before.

However, as described above, the radix of the finite field that defines the discrete logarithmic cryptosystem needs to be large in order to maintain sufficient security, and further, in the Elgamal encryption and the Elgamal signature, each message or signature message is required. Since it is necessary to change the random numbers to be applied, I
It takes a great deal of time to process with a computer having a low calculation ability such as a C card. Therefore, in order to encrypt or sign many communication texts in a short time, y _B ^k in the communication document and the part not related to the signed document (for example, (Equation 2) or y _B ^k in (Equation 3)) The time to encrypt or generate a signature after the communication document and the document to be signed is actually input is shortened by pre-calculating the time when the data is not encrypted or signed, that is, the free time. The idea of doing is necessary. Donald Davies edited "Eurocrypt '91" (1991), pages 446 to 457, Fujioka Atsushi, Okamoto Tatsuaki, Miyaguchi Shoji, "Eas-I-G: An Efficient Digital Signature Implementation for Smart". Card ”(A.Fujioka, T.Okamoto, S.Miyagut
i, “ESIGN: An Efficient Digital Signature Implement
ation for Smart Cards ”, Advances in Cryptology-Eur
ocrypt'91, pp.446-pp.457, Springer-Verlag, 1991). Although there are many parts that can be precalculated in the Elgamal encryption and the Elgamal signature, the number of items that can be processed in the idle time is not so large because the precomputation processing time is long. If it is possible to perform as much preparatory processing as possible in a short time, if the number of encrypted or signed messages increases, some messages may not be pre-calculated, and It can be avoided that encryption and signature generation will start after the document to be signed is input and it will take a lot of time, and even if the number of communication texts to be encrypted or signed does not increase, the number of times of preprocessing is performed. Can be reduced.

For the above reasons, it is desired to develop a calculation method capable of performing as many preliminary calculation processes as possible in a short time even on a computer having a low calculation capacity such as an IC card.

In the following, a conventional technique of a calculation method capable of performing as many preliminary calculation processes as possible will be described.

The calculation processing method to be described below is as follows: 1) In the case of the Ergamal cipher on a finite field, the calculation of (Equation 2) and y _B ^k of (Equation 3), 2) In the case of the Elgamal cipher by an elliptic curve If so, the calculation of (Equation 6) and the calculation of k * Y _B of (Equation 7), 3) In the case of Ergamal signature on a finite field, the calculation of Equation (Equation 10) is a random number that changes for each message. The processing method for the calculation to be performed will be described.

In addition, each of the above-mentioned calculations means that g or y _B is raised to the power of k in the case of a finite field, and G or Y _B is multiplied by k in the case of an elliptic curve. Is essentially unchanged. Therefore, all the calculation methods described in the conventional example will be described only when G is multiplied by k on an elliptic curve. Note that in the calculation of (Equation 2), G is set to g and k times to the kth power, and in the calculation of y _B ^k of (Equation 3), G is set to y _B and k times to the kth power, and calculation of the expression (Equation 7) Then, G may be changed to Y. Also g on a finite field
, G on the elliptic curve can be considered as common to all users who use the encryption system and the signature system, respectively.

In the following (Detailed Description of the Invention),
Unless otherwise stated, the description will proceed assuming that “random number k is all n bits”.

[Prior Art 1] In this calculation processing method, a random number k is expanded into a binary number and processed, and the following processing is performed. Regarding the binary number expansion method, Donald E.Knuth, “The ArtComputer Progr” by Donald Knuth.
amming Vol.2 ”, Addison-Wesley).

The binary expansion of the random number k ₁ is (a _n-1 , ...,
a ₀ ). (A _i ε {0,1}) That is,

[0045]

[Equation 13]

Holds. At this time,

[0047]

[Equation 14]

Therefore, first, 2 ⁱ * G (i = 0,1, ...
, n−1) is calculated in advance, and thereafter, only i for a _i = 1 is subjected to an additive operation. The same applies to the random number k ₂ ,
Perform k ₃ ,.

Regarding the amount of calculation, 2 ⁱ * G (i = 0,1, ...
, n-1), it is necessary to perform (n-1) times of addition operations on the elliptic curve.

Since the probability that a _i = 1 is 1/2, it can be considered that _i when a _i = 1 is 1/2 * n. Therefore, the number of addition operations on the elliptic curve for _{i with} a _i = 1 is (n / 2−1) times. Therefore, in order to calculate k ₁ * G, (3/2 * n−2) times of addition operations on the elliptic curve are required.

The number of addition operations on the elliptic curve required to calculate k ₁ * G, k ₂ * G, ..., K _t * G is t (3/2 *
n-2) times.

In the case of an elliptic curve, n = 96 may be set, so that the calculation amount is

[0053]

[Equation 15]

It becomes [Conventional Example 2] This calculation processing method can be easily improved from the above-mentioned Conventional Example 1. k ₁ * G, k ₂ * G, ..., k _t
The calculation of * G is performed simultaneously, and the following processing is performed. Regarding the binary expansion method, Donald E.Knuth, “The Art Compute” by Donald Knuth.
r Programming Vol.2 ”, Addison-Wesley).

This method is as follows when calculating k ₁ * G:
Same as the above-mentioned conventional example 1, but 2 ⁱ * G produced in the calculation process of k ₁ * G when calculating k ₂ * G, ..., K _t * G
(i = 0,1, ..., N-1) is stored in a table and used.

Therefore, in the calculation of k ₂ * G, ..., K _t * G, only the addition operation on the elliptic curve for _i with a _i = 1 is necessary.

[0057] Therefore, the amount of _{calculation, k 1 * G: (3} /2 * n-2) k 2 * G, ..., k t * G: each (1/2 * n-2 )
Therefore, the number of addition operations on the elliptic curve required to calculate k ₁ * G, k ₂ * G, ..., K _t * G is (3/2 * n−2) + (t− 1) * (1/2 * n-2)
Times.

In the case of an elliptic curve, n = 96 may be set, so that the calculation amount is

[0059]

[Equation 16]

It becomes In comparison with the calculation amount formula (Equation 15) in (Conventional example 1), assuming that t = 28, the number of addition operations on the elliptic curve required in (Conventional example 1) is 3976, whereas (Conventional example 2). ), The number of addition operations on the elliptic curve required is 1411 and the calculation amount can be reduced to about 35.5%.

[Prior Art Example 3] This method uses k ₁ * G, k ₂ *
When G is made into one pair and both k ₁ and k ₂ are binary-expanded, i which becomes 1 is processed collectively. Perform the following processing. This method is described in "Crypt'89" (1990) by Gillies Brasard.
Year) 175 to 185 (A.Fiat, “Batch RSA”, Advanc
es in Cryptology-CRYPTO'89, pp.175-pp.185, Springer-V
erlag, 1990).

Binary expansions of the random numbers k ₁ and k ₂ are (a [1] _n-1 , ..., A [1] ₀ ) (a [2] _n-1 ,.
[2] ₀ ).

At this time, for k ₁ and k ₂ , Γ (1,2) ^[2] = {0≤i≤n-1 | (a [1] _i , a [2] _i ) = (1 , 1)} Γ (1) ^[2] = {0 ≤ i ≤ n-1 | (a [1] _i , a [2] _i ) = (1,0)} Γ (2) ^[2] = { 0 ≦ i ≦ n−1 | (a [1] _i , a [2] _i ) = (0,1)}.

Where Γ (1,2) ^[2] , Γ (1) ^[2] , Γ (2)
Against ^[2]

[0065]

[Equation 17]

[0066]

[Equation 18]

[0067]

[Formula 19]

Define At this time, k ₁ * G = U (1,2) ^[2] + U (1) ^[2] k ₂ * G = U (1,2) ^[2] + U (2) ^[2] holds.

In the following, processing is carried out in pairs with (k ₃ , k ₄ ), (k ₅ , k ₆ ), ... (K _t-1 , k _t ) <t≡0 (mod2)>.

Therefore, the calculation amount is 2 ⁱ * G (i =
Since 0,1, ..., n-1) is calculated and stored in the table, the addition operation on the elliptic curve necessary for this calculation is (n-1)
Times.

Next, # Γ (1,2) = # Γ (1) = # Γ
(2) = 1/4 * n (where #A = number of elements of set A), so U (1,2) ^[2] , U (1) ^[2] , U (2)
Each calculation of ^[2] requires (1/4 * n−1) times of addition operation on the elliptic curve. Also U (1,2) ^[2] , U (1)
^[2], U ⁽²⁾ from _{^{[2], k 1 * G}} , to generate the k ₂ * G, because it is necessary addition operation on an elliptic curve once each, first of 2 ⁱ * G The number of calculations except for creating the table of (i = 0,1, ..., n-1) is (1/4 * n-1) * 3 + 1 * 2 = (3/4 * n-1) Become.

The number of addition operations on the elliptic curve required to calculate k ₁ * G, k ₂ * G, ..., K _t * G is (n-1) + t / 2 * (3/4 * n-1).

In the case of an elliptic curve, n = 96 may be set, so that the calculation amount is

[0074]

[Equation 20]

It becomes In (conventional example 3), t ≧ 1, and the number of calculations is the smallest as compared with (conventional example 1) (conventional example 2).
In comparison with the calculation amount formula (Equation 16) in (Conventional example 2), assuming that t = 28, the number of addition operations on the elliptic curve required in (Conventional example 2) is 1411 times, whereas (Conventional example 3) ), The number of addition operations on the elliptic curve required is 1089, and the calculation amount can be reduced to about 77.1%.

[Conventional method 4] This method is a generalization of the above-mentioned conventional method 3, and is a method for processing k ₁ * G, ..., K _L * G as one set, and is the following processing. . This method is described in "Crypt 'by Gillies Brasard".
89 "(1990), pages 175 to 185 (A. Fiat," Batch R
SA ”, Advances in Cryptology-CRYPTO'89, pp.175-pp.18
5, Springer-Verlag, 1990).

The binary expansion of the random number k _l (l = 1,2, ..., L) is (a [l] _n-1 , ..., a [l] ₀ ) (l = 1,2, ..., L). And

Next, for a subset T (≠ φ (empty set)) of Z (L) = {0,1, ..., L}, Γ (T) ^[L] = {0≤i≤n- 1 | a [l] _i = 1 (l∈T), a [l]
_i = 0 (lεZ (L) −T)} is defined. Further, if T = {x ₁ , ..., x _t } is abbreviated as Γ (T) ^[L] = Γ (x ₁ , ..., x _t ) ^[L] , then the method is defined by the conventional method 3. Γ
(1,2) ^[2] , Γ (1) ^[2] , Γ (2) ^[2] is a symbol consistent with the definition.

Further, as in the case of the conventional method 3,

[0080]

[Equation 21]

Then, U (T) ^[L] is defined. At this time,

[0082]

[Equation 22]

The following holds. The amount of calculation is as follows.

First, 2 ⁱ * G (i = 0, 1, ..., N-1) is calculated and stored in a table, so the addition operation on the elliptic curve necessary for this calculation is (n- 1) times.

Also, # Γ (T) ^[L] = (1/2 ^L ) * n (T
Ε P (Z (L)) − φ). However, P (A) =
U (T) ^{[L] because} it is considered to be the entire subset of set A
To calculate (T ∈ P (Z (L)) − φ), ((1/2 ^L ) * n−1) times of addition operations on the elliptic curve are required, and U (T) ^{[L ]} Is 2 ^L −1.

The total number of T T ∋ k _l is 2 ^{L-1 because} there is only a combination of whether or not a random number (L-1) other than k _l falls within T.

Therefore, U (T) ^[L] (T ∈ P (Z (L))
-(Φ) is calculated as ((1/2 ^L ) * n-1) *
(2 ^L -1) times of addition operations on the elliptic curve are required.

U (T) ^[L] (T ∈ P (Z (L))-
k ₁ * G from _{φ), ..., k L *} G respectively to generate a so it is necessary to add operations on an elliptic curve (2 ^L-1 -1) times, the beginning of the 2 ⁱ * G ( i = 0,1, ..., n-1) The number of calculations except creating the table is ((1/2 ^L ) * n-1) * (2 ^L -1) + L * (2 ^{L- 1} -1).

The number of addition operations on the elliptic curve required to calculate k ₁ * G, k ₂ * G, ..., K _t * G is <t≡
0 (mod l)> (n-1) + t / L * {((1/2 ^L ) * n-1) * (2 ^L -1) +
L * (2 ^L-1 -1)}.

In the case of an elliptic curve, n = 96, so the calculation amount is

[0091]

[Equation 23]

It becomes Where f (L) = 1 / L * {((96/2 ^L ) -1) * (2 ^L -1) + L * (2 ^L-1-
1)}, it is obvious that the L having the smallest value of f (L) is the number L to be processed collectively that minimizes the number of calculations.

The values of f (L) for each L are shown in (Table 1). As can be seen from the above, when L = 4, f (L) is the smallest, that is, it is the least computational complexity to process four random numbers at once.

[0094]

[Table 1]

Further, since the story so far has been on the elliptic curve, n = 96 is set, but n on a finite field is n.
= 512. Also in this case, n = 9
If f (L) is defined by processing in the same way as in the case of 6, L
When = 6, f (L) is minimum, that is, 6 random numbers are collectively processed, which requires the least amount of calculation. n = 5
The value of f (L) in the case of 12 is shown in (Table 2).

[0096]

[Table 2]

Therefore, in the case of an elliptic curve, the method of collectively processing four random numbers requires the least amount of calculation, and k ₁ * G,
The number of addition operations on the elliptic curve required to calculate k ₂ * G, ..., K _t * G is <t≡0 (mod 4)>

[0098]

[Equation 24]

It becomes In the method of L = 4 in (Conventional example 4), t ≧ 1 and the number of calculations is the smallest as compared with (Conventional example 1) (Conventional example 2) (Conventional example 3). In comparison with the calculation amount formula (Equation 20) in (Conventional example 3), assuming that t = 28, the number of addition operations on the elliptic curve required in (Conventional example 3) is 1089, whereas ), The number of addition operations on the elliptic curve required by the method of L = 4 is 816,
The calculation amount can be reduced to about 74.9%.

In the case of a finite field, the method of processing 6 random numbers at a time requires the least amount of calculation, and k ₁ * G, k ₂ *
The number of addition operations on the elliptic curve required to calculate G, ..., K _t * G is <t≡0 (mod 6)>

[0101]

[Equation 25]

It becomes Also in this case, the amount of calculation can be reduced by the same amount as in the case of the elliptic curve.

[0103]

In any of the above-mentioned conventional examples,
This is a calculation method for the problem that it takes time to realize a discrete logarithmic cryptosystem with a computer having a low calculation ability such as an IC card, but it cannot be said to be realized in a sufficiently practical time. It is an object of the present invention to realize a discrete logarithmic cryptosystem in a sufficiently short time even with a computer having a low calculation ability such as an IC card.

[0104]

In order to achieve the above object, the present invention provides a random number division unit for dividing at least one random number of two or more random numbers into two or more partial random numbers, and the partial random number. And an integer acting part for outputting a constituent element that acts on a specific element of the finite commutative group, and a definition operation of the finite commutative group and an inverse element operation thereof with respect to the constituent element output from the integer acting part. And an action source generation device for performing and combining both or one of the operations.

[0105]

According to the present invention, by including the above means, the random number division unit divides at least one random number of the two or more base random numbers into two or more partial random numbers, and the partial random numbers are converted into integer action units. The integer acting device applies the partial random number to a specific element of the finite commutative group to create a constituent element and supplies the constituent element to the effector generation unit. A new finite commutative group element is created by performing both or one of the group definition operation and its inverse element operation.

Further, by making the number of elements of the new finite commutative group lower than the total number of the partial random numbers, it is possible to know how to combine constituent elements and constituent elements from the elements of the new finite commutative group. Can not.

[0107]

【Example】

(First Embodiment) -Arithmetic Unit in Elgamal Cryptography on Elliptic Curve FIG. 1 shows a configuration of an arithmetic unit in Elgamar cipher on elliptic curve according to the first embodiment of the present invention. In the figure, 1 is a random number generation unit, 2 is a random number division unit that divides at least one random number of two or more random numbers supplied from the random number generation unit into two or more partial random numbers, and 3 is a bit. The designating unit, 4 is an integer acting unit on the first elliptic curve that creates a constituent element by acting the partial random number output from the random number dividing unit of 2 on the specific element on the elliptic curve, and 5 is the integer acting unit of 4 A first ciphertext that creates an element on an elliptic curve by combining two or more constituent elements output from the integer acting unit on the first elliptic curve with an addition operation or a subtraction operation on the elliptic curve A generation unit, 6 is a combination designation unit, 7 is a storage unit, and 8 is a second elliptic curve that creates a constituent element in which the partial random number output from the random number division unit 2 is applied to a specific element on an elliptic curve. Is the above integer action part, 9 is the above integer action part on the second elliptic curve? The second ciphertext generating unit for generating the original on the elliptic curve by combining the addition operation or subtraction operation on the elliptic curve with respect to two or more of said configuration source output,
Reference numeral 10 is an addition calculation unit on the elliptic curve.

The procedure of the embodiment will be described below with reference to FIG. In this example, 4 random numbers are input first, then 7
This is an example of outputting a part of the first ciphertext or the second ciphertext of each Ergamal cipher. (1) Random number division _Four random numbers k ₁ , k ₂ , k ₃ , k ₄ are supplied from the random number generation unit 1 and input to the random number division unit 2. On the other hand, the bit division information T ₁ , T ₂ , T ₃ , T ₄ is input to the random number division unit 2 from the bit designation unit 3. Where Z ₀ (n-1) = {0,1, ..., n-1
}, The bit division information T ₁ , T ₂ , T ₃ , T ₄ is Z ₀ (n-
It is a subset of 1). The random number division unit 2 uses the random number k _i (i = 1,
Partial random numbers k _i ^[1] , k _i ^[2] (i = 1,2,3,2) based on bit division information T _i (i = 1,2,3,4) Divide into 4).
That is, the binary expansion of the random number k _i (i = 1,2,3,4) is (a
[i] _n-1 , ..., A [i] ₀ ) (i = 1,2,3,4), and the partial random number k _i
^The binary expansion of ^[1] , k _i ^[2] (i = 1,2,3,4) is (b
[i] _n-1 , ..., b [i] ₀ ), (c [i] _n-1 , ..., c [i] ₀ ), b [i] _j , c [i] _j (i = 1,2,3,4 j = 0,1, ...
n-1) is determined by the following rules of (Equation 26) and (Equation 27).

[0109]

[Equation 26]

[0110]

[Equation 27]

At this time, k _i = k _i ^[1] + k _i ^[2] (i = 1,2,3,4) holds. (2) Creation of a constituent element of the first ciphertext of the Ergamal cipher Partial random numbers k _i ^[1] , k _i ^[2] (i
= 1,2,3,4) is supplied to the integer action part 4 on the first elliptic curve. The integer acting part 4 on the first elliptic curve is
By operations like 8), points K _i ^[1] , K _i ^[2] (i
= 1,2,3,4).

If G is a point on the elliptic curve that is the public key of the system,

[0113]

[Equation 28]

[0114] Calculation of where k _i ^[j] * G may be calculated by processing the batch four k _i ^[j] * G in the manner described (fourth conventional example).

In this way, the constituent elements of the first ciphertext, which are the points on the elliptic curve, are created. (3) Creation of the first ciphertext of the Elgamal cipher The points K _i ^[1] and K _i ^{[ 2]} (i = 1,2 ⁾ on the elliptic curve output from the integer action unit 4 on the first elliptic curve , 3, 4) is input to the first ciphertext generation unit 5. Further, the combination designation information Q _j (j = 1,2,3,4,5,6,7) is input from the combination designation unit 6 to the first ciphertext generation unit 5.

Combination designation information Q _j (j = 1,2,3,4,5,6,
7) chooses two points from points K _i ^[1] and K _i ^[2] (i = 1,2,3,4) on the elliptic curve, and adds the two points by addition on the elliptic curve. This is information that determines whether to act or to act by subtraction. Therefore, the first ciphertext generation unit 5 uses the first ciphertext C [j] ₁ (j = 1, j = 1, j of the El Gamal cipher based on Q _j (j = 1,2,3,4,5,6,7). 2,
Create 3,4,5,6,7). For example, Q ₁ is
If it is the information that K ₂ ^{[1] is} to be added and K ₄ ^{[2] is} to be subtractive, then C [1] ₁ is determined by the following (Equation 29).

[0117]

[Equation 29]

In this way, the first ciphertext generator 5 uses the combination designating information Q _j (j = 1,2,3,4,5,6,7) to generate the first ciphertext C of the El Gamal cipher. [j] ₁ (j = 1,2,3,4,5,6,
7) is created and stored in the storage unit 7. (4) Creation of a constituent element of the second ciphertext of the Ergamal cipher Partial random number output from the random number division unit 2 Same as the above (2) k _i
^[1] , k _i ^[2] (i = 1,2,3,4) are supplied to the integer operating unit 8 on the second elliptic curve. The integer acting unit 8 on the second elliptic curve is operated by the following operation (Equation 30) to obtain a point X _i on the elliptic curve
^[1] , X _i ^[2] (i = 1,2,3,4) is calculated.

Let Y _{B be} the point on the elliptic curve that is the public key of a particular recipient B, then

[0120]

[Equation 30]

Here, the calculation of k _i ^[j] * Y _B is (conventional example 4).
It is also possible to collectively process and calculate the four k _i ^[j] * Y _B by the method described in ⁽¹⁾ .

In this way, the constituents of the second ciphertext, which are the points on the elliptic curve, are created. (5) Creation of a part of the second ciphertext of the Elgamal cipher The points X _i ^[1] and X _i ^[2] (i = 1,2 ⁾ on the elliptic curve output from the integer action part 8 on the elliptic curve , 3, 4) is input to the second ciphertext generation unit 9. Also, the same combination designation information Q _j (j = 1,2,3,4,5,6,7) as in (3) above is input from the combination designation unit 6 to the second ciphertext generation unit 9. The combination designation information Q _j (j = 1,2,3,4,5,6,7) is the points K _i ^[1] and K _i on the elliptic curve.
^{[2] This} is information that determines two points from (i = 1,2,3,4) and determines whether the two points act on the elliptic curve by addition or subtraction. The second ciphertext generator 9 uses Q _j (j = 1,
2,3,4,5,6,7), the part V [j] (j = 1,2,3,4,5,6,7) other than the plaintext M of the second ciphertext of the Elgamal cipher To create. For example, Q ₂ is created by subtracting X ₃ ^[2] from X ₄
^If it is the information that ^[1] acts on the addition, V
[2] is to be determined by the following (Equation 31).

[0123]

[Equation 31]

In this way, the second ciphertext generator 9 generates the second ciphertext of the El Gamal cipher based on the combination designation information Q _j (j = 1,2,3,4,5,6,7). Portion other than plaintext V [j]
(j = 1,2,3,4,5,6,7) is created and stored in the storage unit 7.
However, in the storage unit 7, C [j] ₁ and V [j] (j = 1,2,3,4,5,6,7)
Store as a set. (6) Creation of second ciphertext of Ergamal cipher When plaintext M [j] secretly communicated to a specific recipient B is input to the addition operation unit 10 on the elliptic curve, V stored in the storage unit 7 is stored. [j] is input to the addition operation unit 10 on the elliptic curve,
The addition calculation unit 10 on the elliptic curve creates the _second ciphertext C [j] ₂ of the Elgamal cipher as the following (Numerical Expression 32).

[0125]

[Equation 32]

Then, C [j] ₁ stored in the storage unit 7 as a set with V [j] and this C [j] ₂ are transmitted to B as a ciphertext.

The C [j] ₁ and V [j] used once need not be stored in the storage unit 7. (7) Computational complexity From the comparison with the conventional example, the first ciphertext C [j] ₁ (j = 1,2,3,4,5,6,7 of the Ergamal cipher in the above (2) and (3) ) Describes the amount of calculation required to create). A similar effect can be obtained with respect to the amount of calculation for creating a part of the second ciphertext.

Similar to (Conventional example 2), first, 2 ⁱ *
G (i = 0,1, ..., n-1) is calculated and then K _i
^[j] = k _i ^[j] * G (i = 1,2,3,4 j = 1,2) is calculated.

To calculate all 2 ⁱ * G (i = 0, 1, ..., N-1), it is necessary to perform (n-1) times of addition operations on the elliptic curve.

Next, & k _i ^[j] = average (1/4) * n, where & r = the number of bits in which 1 is set when r is binary-expanded. Each calculation of K _i ^[j] = k _i ^[j] * G requires (1/4) * n−1 addition operations on the elliptic curve.

From K _i ^[j] (i = 1,2,3,4 j = 1,2) to C
[s] ₁ (s = 1,2,3,4,5,6,7) requires one addition operation or subtraction operation on the elliptic curve to create each. However, since the addition operation and the subtraction operation on the elliptic curve can be processed in the same time, the number of calculations is counted without being distinguished from the addition operation even in the subtraction operation. Therefore, a total of 7 addition operations on the elliptic curve are required.

Therefore, the addition operation on the elliptic curve required to create C [1] ₁ , C [2] ₁ , ..., C [t] ₁ is (n−1) + t / 7 * {((1 / 4) * n-1) * 8 + 7}.

In the case of an elliptic curve, n = 96, so the calculation amount is

[0134]

[Expression 33]

It becomes: Among the (conventional example), the method with the smallest calculation amount is the method of collectively processing the four random numbers of (conventional example 4), and the calculation amount is C [1] ₁ , C [2] ₁ , ..., C When [t] ₁ was prepared, H ₄ (t) = (103/4) t + 95 was obtained from (Equation 24).

Since 103/4 = 25 3/4 <191/7 = 27 2/7, it can be seen that the calculation amount of the present invention is slightly larger.

However, as described above, K _i ^[j] (i = 1,2,3,4
When j = 1, 2) is calculated by the method of collectively processing the four random numbers (conventional example 4), the calculation amount is as follows.

When collectively processing K ₁ ^[1] , K ₂ ^[1] , K ₃ ^[1] , and K ₄ ^[1] , # Γ (T) ^[4] = (1/32) * n T ∈ P (Z (4)) − φ, so each U (T) ^[4] (T ∈ P (Z (4))
Each of (1/32) * n-1 times of addition operation on the elliptic curve is required to calculate −φ).

U (T) ^[4] (T ∈ P (Z (4))-
φ), K ₁ ^[1] , K ₂ ^[1] , K ₃ ^[1] , and K ₄ ^[1] require 7 times of addition operations on the elliptic curve.

Since # (P (Z (4)) − φ) = 15, K ₁ ^[1] , K ₂ ^[1] , K ₃ ^[1] , and K ₄ ^[1] are collectively processed. When calculating, the necessary addition operation on the elliptic curve is ((1/32) * n-1) * 15 + 7 * 4 = (15/32) * n + 1
3

Similarly, in order to calculate K ₁ ^[2] , K ₂ ^[2] , K ₃ ^[2] , and K ₄ ^[2] , (15/32) * n + 13 addition operations on the elliptic curve are required. Therefore, a total of (15/16) * n + 26 addition operations on the elliptic curve are required to calculate K _i ^[j] = k _i ^[j] * G.

Therefore, the addition operation on the elliptic curve required to create C [1] ₁ , C [2] ₁ , ..., C [7] ₁ is ((15/16) * n + 26) + 7 = (15 / 16) * n + 33.

Therefore, the addition operation on the elliptic curve required to create C [1] ₁ , C [2] ₁ , ..., C [t] ₁ is (n−1) + t / 7 * ((15 / 16) * n + 33).

In the case of an elliptic curve, n = 96, so the calculation amount is

[0145]

[Equation 34]

[0146] Since 123/7 = 17 4/7 <103/4 = 25 3/4, the calculation amount is t = 28, and the method of collectively processing the four random numbers, which is the minimum calculation method of the conventional example, is ,
Whereas 816 times of addition operations on the elliptic curve are required, the method of combining the present invention and the method of collectively processing four random numbers requires only 587 times of addition operations on the elliptic curve, which is about 71.9%. You can reduce the calculation amount up to.

Further, in the above description, the calculation amount by the combination with the conventional example 4 is described, but the same effect can be obtained by combining with the conventional example 3.

In the first embodiment, four random numbers are exclusively divided into two to create seven first and second ciphertexts of the Elgamal cipher. But,
This embodiment can be generalized. Generally, L random numbers k _l (l =
1,2, ..., L) are each divided into m ( _kl ) pieces, and if M or less pieces of the first ciphertext and a part of the second ciphertext of the Elgamal cipher are created, the same is true. Can be obtained. However, M is given by the following (Equation 34).

[0149]

[Equation 35]

Further, in the first embodiment, the random number is exclusively divided, but the same effect can be obtained by dividing the random number into a sum of positive integers smaller than the random number or a division method in which a negative integer is entered. To be

(Second Embodiment) Arithmetic Unit in Ergamal Cryptography on Finite Field Further, FIG. 2 shows a configuration of an arithmetic unit in Ergamal cipher on a finite field in the second embodiment of the present invention.
In the figure, 11 is a random number generation unit, 12 is a random number division unit that divides at least one random number of the two or more random numbers supplied from the 11 random number generation unit into two or more partial random numbers, and 13 is a bit. A designation unit, 14 is a power calculation unit on a first finite field that creates a constituent element in which the partial random number output from the 12 random number division unit is applied to a specific element on a finite field, and 15 is A first ciphertext generation unit that creates an element on a finite field by combining a multiplication operation on the finite field with two or more constituent elements output from a power calculation unit on a first finite field; Reference numeral 16 is a combination designation unit, 17 is a storage unit, and 18 is a power on a second finite field that creates a constituent element in which the partial random number output from the random number division unit 12 is applied to a specific element on the finite field. Calculation unit, 19 is a power exponentiation on the second finite field of 18 The second ciphertext generating unit for generating the original on the finite field in combination multiplication operations on the finite field with respect to two or more of said configuration source output from the section 20
Is a multiplicative calculation part over a finite field.

Hereinafter, the procedure of the embodiment will be described with reference to FIG.
Reveal In this example, 6 random numbers are input first, then 1
One random number is the system public key or the recipient's public key
This is an example of outputting the value that is applied to. (8) Random number division Random number generation unit 11 generates a random number k₁, k₂, k₃, k_Four, k_Five, k₆ Is 6
Individually supplied and input to the random number division unit 12. One more
On the other hand, from the bit designation unit 13 to the bit division information T₁, T ₂, T₃,
T_Four, T_Five, T₆ Is input to the random number division unit 12. Where Z
₀If (n-1) = {0,1, ..., n-1}, the bit division information is
News T₁, T₂, T₃, T_FourIs Z₀It is a subset of (n-1). random number
The division unit 12 uses the random number k_i(i = 1,2,3,4,5,6) is the bit division information
News T_iBy (i = 1,2,3,4,5,6), the partial random number k is as follows._i
^[1], k_i ^[2]Divide into (i = 1,2,3,4,5,6). I.e. disorder
A few k_iThe binary expansion of (i = 1,2,3,4,5,6) is (a [i]_n-1、…
 , a [i]₀) (I = 1,2,3,4,5,6), and the partial random number k_i ^[1], k
_i ^[2]The binary expansion of (i = 1,2,3,4,5,6) is (b [i]
_n-1,…, B [i]₀), (C [i]_n-1,…, C [i]₀) And
When b [i]_j, C [i]_j (i = 1,2,3,4,5,6 j = 0,1, ...
 , n-1) is defined by the following (Equation 36) and (Equation 37).

[0153]

[Equation 36]

[0154]

[Equation 37]

At this time, k _i = k _i ^[1] + k _i ^[2] (i = 1,2,3,4,5,6) holds. (9) Creation of constituent element of first ciphertext of Ergamal cipher Partial random number k _i ^[1] , k output from the random number division unit 12
_i ^[2] (i = 1,2,3,4,5,6) is supplied to the power calculation unit 14 on the first finite field. The first power calculation unit 14 on the finite field is operated by the following operation (Equation 38) and the values K _i ^[1] , K _i ^[2] (i = 1,2,3,4,5) of the finite field are calculated. , 6).

Let g be the value of the finite field that is the public key of the system,

[0157]

[Equation 38]

Here, g ^ k _i ^[j] can be calculated by collectively processing six g ^ k _i ^[j] by the method described in (Conventional example 4).

In this way, the constituent elements of the first ciphertext, which are the values of 12 finite fields, are created.

(10) Creation of the first ciphertext of the Ergamal cipher The values K _i ^[1] , K _i ^[2] (i = 1 ^{) of} the finite field output from the power calculation unit 14 on the first finite field , 2, 3, 4, 5, 6) is input to the first ciphertext generating unit 15. Further, the combination designation information Q _j (j = 1, 2, ..., 11) is input from the combination designation unit 16 to the ciphertext generation unit 15.

Combination designation information Q_j(j = 1,2, ..., 11)
Is the value K of a finite field_i ^[1], K_i ^[2](i = 1,2,3,4,5,6)
It is information that determines which two values to choose from
It The first ciphertext generation unit 15 uses Q_j(j = 1,2, ..., 11)
Based on the first ciphertext C [j] of the Ergamal cipher₁(j = 1,
Create 2, ..., 11). How to create it, for example, Q₁But,
K ₂ ^[1]And K_Four ^[2]If it was the information to choose two of
For example, C [1]₁Is determined by the following (Equation 39)
It

[0162]

[Formula 39]

In this way, the first ciphertext generation unit 15
Creates the first ciphertext C [j] ₁ (j = 1,2, ..., 11) of the Elgamal cipher from the combination designation information Q _j (j = 1,2, ..., 11), and stores it in the storage unit 17. store. (11) Creation of constituent element of second ciphertext of Ergamal cipher Partial random number output from random number division unit 12 k _i ^[1] , k _i ^[2] (i = 1, 2, 3,4,5,6) is supplied to the power calculation unit 18 on the second finite field. Here, the following (Equation 4)
0) such as X _i ^[1] , X _i ^[2] (i = 1,
2,3,4,5,6) is required.

Let y _{B be} a point on the elliptic curve that is the public key of a particular recipient B, then

[0165]

[Formula 40]

Here, the calculation of y _B ^ k _i ^[j] is (conventional example 4).
It is also possible to collectively process and calculate the six y _B ^ k _i ^[j] by the method described in ⁽¹⁾ .

In this way, the constituent elements of the second ciphertext, which are the values on the 12 finite fields, are created. (12) Creation of a part of the second ciphertext of the Ergamal cipher The values of the finite field X _i ^[1] , X _i ^[2] (i = 1 ⁾ output from the power calculation unit 18 on the second finite field , 2, 3, 4, 5, 6) is input to the second ciphertext generating unit 19. Further, the same combination designation information Q _j (j = 1, 2, ...
, 11) is input to the second ciphertext generation unit 19. The combination designation information Q _j (j = 1,2, ..., 11) is selected from the values K _i ^[1] and K _i ^[2] (i = 1,2,3,4,5,6) of the finite field. This is information about which two values to select. Second ciphertext generator 19
Is based on Q _j (j = 1,2, ..., 11), and is a portion V [j] (j = 1,2, ..., 11) of the second ciphertext of the Elgamal ciphertext other than the plaintext M.
To create. The creation method is, for example, Q ₃ is X ₃ ^[2] and X ₄
If the information was to select ^[1] , then V [3] would be determined by the following (Equation 41).

[0168]

[Formula 41]

In this way, the second ciphertext generation unit 19
Combination specifying information _{Q j (j = 1,2, ...} , 11) portions other than the plaintext M from the ElGamal second ciphertext of the encryption V [j] (j =
1, 2, ..., 11) are created and stored in the storage unit 17. However, in the storage unit 17, C [j] ₁ and V [j] (j = 1, 2, ..., 11) are stored as a set. (13) Creation of second ciphertext of Ergamal cipher When plaintext M [j] secretly communicated to a specific recipient B is input to the multiplication calculation unit 20 on a finite field, V stored in the storage unit 17 is stored. [j] is input, and the multiplicative calculation unit 20 on the finite field creates the _second ciphertext C [j] ₂ as in the following (Equation 42).

[0170]

[Equation 42]

Then, C [j] _{1 and} this C [j] ₂ stored in the storage unit 17 as a set with V [j] and this C [j] ₂ are transmitted to B as a ciphertext.

The C [j] ₁ and V [j] used once need not be stored in the storage unit 17. (14) Computational complexity From the comparison with the conventional example, in (9) and (10), the first ciphertext C [j] ₁ (j = 1, 2, ... The amount of calculation required is described. A similar effect can be obtained with respect to the amount of calculation for creating a part of the second ciphertext.

Similarly to (Conventional example 2), first, g ^ 2
ⁱ (i = 0,1, ..., n-1) is calculated and then K _i ^[j]
= G ^ k _i ^[j] (i = 1,2, ..., 11 j = 1,2) is calculated.

To calculate g ^ 2 ⁱ (i = 0,1, ..., N-1), it is necessary to perform (n-1) times of multiplication operation on the finite field.

Next, & k _i ^[j] = average (1/4) * n, where & r = the number of bits in which 1 is set when r is expanded into a binary number. Each calculation of K _i ^[j] = g ^ k _i ^[j] requires (1/4) * n−1 multiplication operations on the finite field.

Further, C [s] ₁ (s = 1,2, ..., 11) is created from K _i ^[j] (i = 1,2,3,4,5,6 j = 1,2). 1 for each
It requires multiplication operations over a finite field. Therefore, a total of 7 multiplication operations on the finite field are required.

Therefore, the multiplication operation on the finite field required to create C [1] ₁ , C [2] ₁ , ..., C [t] ₁ is (n−1) + t / 7 * {((1 / 4) * n-1) * 8 + 7}.

In the case of a finite field, n = 512, so the calculation amount is

[0179]

[Equation 43]

It becomes: Among the (conventional example), the method with the smallest calculation amount is the method of collectively processing the six random numbers of (conventional example 4), and the calculation amount is C [1] ₁ , C [2] ₁ , ..., C When [t] ₁ was created, h ₆ (t) = (209/2) t + 511 was obtained from (Equation 25).

Since 209/2 = 104 1/2 <139 6/11 = 1535/11, it can be seen that the calculation amount of the present invention is slightly larger.

However, as described above, K _i ^[j] (i = 1,2,3,4,
When 5,6 j = 1,2) is calculated by the method of collectively processing the six random numbers (conventional example 4), the calculation amount is as follows.

K ₁ ^[1] , K ₂ ^[1] , K ₃ ^[1] , K ₄ ^[1] ,
When processing K ₅ ^[1] and K ₆ ^[1] together, it is considered that # Γ (T) ^[6] = (1/128) * n T ∈ P (Z (6)) − φ Each U (T) ^[6] (T ∈ P (Z (6))
To calculate −φ), (1/128) * n−1 multiplication operations on the finite field are required.

U (T) ^[6] (T ∈ P (Z (4))-
φ) to K ₁ ^[1] , K ₂ ^[1] , K ₃ ^[1] , K ₄ ^[1] , K ₅ ^[1] , K
₆ Each [31 ^] requires 31 multiplication operations on a finite field.

Since # (P (Z (6)) − φ) = 63, K ₁ ^[1] , K ₂ ^[1] , K ₃ ^[1] , K ₄ ^[1] , K ₅ ^[1] , K ₆
^When processing ^[1] in a batch, the multiplication operation on the finite field required is ((1/128) * n-1) * 63 + 31 * 6 = (63/128) * n + 123.

Similarly, K ₁ ^[2] , K ₂ ^[2] , K ₃ ^[2] , K ₄ ^[2] ,
To calculate K ₅ ^[2] and K ₆ ^[2] , (63/128) * n + 123 multiplication operations on a finite field are necessary, so K _i ^[j] = g
In total, (63/64) * n + 246 multiplication operations on the finite field are required to calculate ^ k _i ^[j] .

Therefore, C [1] ₁ , C [2] ₁ , ..., C [11] ₁
The multiplication operation on the finite field required to create is ((63/64) * n + 246) +11 = (63/64) * n + 257.

Therefore, the multiplication operation on the finite field required to create C [1] ₁ , C [2] ₁ , ..., C [t] ₁ is (n−1) + t / 11 * ((63 / 64) * n + 257).

In the case of a finite field, n = 512, so the calculation amount is

[0190]

[Equation 44]

It becomes Since 761/11 = 69 2/11 <209/2 = 104 1/2, the calculation amount is t = 22, and the method of collectively processing 6 random numbers, which is the minimum calculation method of the conventional example, is ,
Whereas 2810 multiplication operations on a finite field are required, the method of combining the present invention and the method of collectively processing 6 random numbers requires only 2033 multiplication operations on a finite field, which is about 72.3%. You can reduce the calculation amount up to.

In the above description, the calculation amount in combination with the conventional example 4 has been described, but the same effect can be obtained by combining with the conventional example 3.

In the second embodiment, six random numbers are exclusively divided into two to create eleven Elgamal cipher first ciphertexts and a part of the second ciphertexts. However, it can be generalized. Generally, L random numbers k _l (l = 1,2, ...
, L) are each divided into m ( _kl ) pieces, and the same effect can be obtained by creating M or less pieces of the first ciphertext and the second ciphertext of the Ergamal cipher. . However, M is given by (Equation 45).

[0194]

[Equation 45]

Further, in the second embodiment, the random number is exclusively divided, but the same effect can be obtained by dividing the random number into the sum of positive integers smaller than the random number.

(Third Embodiment) -Operator in Ergamal Signature on Finite Field FIG. 3 shows the configuration of the operator in Ergamal signature on finite field in the third embodiment of the present invention. In the figure, reference numeral 21 denotes a random number generation unit, 22 denotes a random number division unit for dividing at least one random number of two or more random numbers supplied from the random number generation unit of 21 into two or more partial random numbers, 2
3 is a bit designating unit, 24 is a power calculation unit on a finite field that creates a constituent element in which the partial random number output from the random number dividing unit of 22 is applied to a specific element on the finite field, and 25 is a unit of the 24 A first signature statement generation unit that creates an element on a finite field by combining multiplication operations on the finite field with two or more constituent elements output from a power calculation unit on a finite field, 2
6 is a combination designation unit, 27 is a storage unit, 28 is a multiplication calculation unit on a finite field, and 29 is a second signature text generation unit.

The procedure of the embodiment will be described below with reference to FIG.
Reveal In this example, 6 random numbers are input first, then 1
Outputs the value obtained by applying one random number to the system public key.
Is an example. (15) Random number division From the random number generation unit 21, the random number k₁, k₂, k₃, k_Four, k_Five, k₆ Is 6
Individually supplied and input to the random number division unit 22. One more
From the bit designation section 23, the bit division information T₁, T ₂, T₃,
T_Four, T_Five, T₆ Is input to the random number division unit 22. Where Z
₀If (n-1) = {0,1, ..., n-1}, the bit division information is
News T₁, T₂, T₃, T_FourIs Z₀It is a subset of (n-1). random number
The division unit 22 uses the random number k_iBit division of (i = 1,2,3,4,5,6)
Information T_iBy (i = 1,2,3,4,5,6), the partial random number k is as follows.
_i ^[1], k_i ^[2]Divide into (i = 1,2,3,4,5,6). That is,
Random number k_iThe binary expansion of (i = 1,2,3,4,5,6) is (a [i]_n-1，
…, A [i]₀) (I = 1,2,3,4,5,6), and the partial random number k_i ^[1],
k_i ^[2]The binary expansion of (i = 1,2,3,4,5,6) is (b
[i]_n-1,…, B [i]₀), (C [i]_n-1,…, C [i]₀)
B [i]_j, C [i]_j (i = 1,2,3,4,5,6 j = 0,1,
..., n-1) is determined by the following rules of (Equation 46) (Equation 47).
Meru.

[0198]

[Equation 46]

[0199]

[Equation 47]

At this time, k _i = k _i ^[1] + k _i ^[2] (i = 1,2,3,4,5,6) holds. (16) Creation of constituent element of first signature sentence of El Gamal signature Partial random number k _i ^[1] , k output from random number division unit 22
_i ^[2] (i = 1,2,3,4,5,6) is a power calculation unit 2 on a finite field.
4 is supplied. The exponentiation calculation unit 24 on the finite field calculates the values K _i ^[1] and K _i ^[2] (i
= 1,2,3,4,5,6).

Let g be the value of the finite field that is the public key of the system,

[0202]

[Equation 48]

Here, g ^ k _i ^[j] can be calculated by collectively processing six g ^ k _i ^[j] by the method described in (Conventional example 4).

In this way, the constituent elements of the first signature sentence, which are the values of 12 finite fields, are created. (17) Creation of first signature sentence of Ergamal signature The values K _i ^[1] and K _i ^[2] (i = 1,2,3,4 ^{) of} the finite field output from the power calculation unit 24 on the finite field , 5, 6) is a random number division unit 22
Partial random numbers k _i ^[1] , k _i ^[2] (i = 1,2,3,4,5,
It is input to the first signature text generation unit 25 together with 6). The specified combination from the combination specifying unit 26 information Q _{j (j} = 1,2,
, 11) is input to the first signature text generation unit 25.

Combination designation information Q _j (j = 1, 2, ..., 11)
Is information that determines which two values are selected from the values K _i ^[1] and K _i ^[2] (i = 1,2,3,4,5,6) of the finite field. The first signature text generation unit 25, based on Q _j (j = 1, 2, ..., 11), pseudo random number r [j] (j = 1, j) that combines partial random numbers.
2, ..., 11), the first signature sentence R [j] (j =
Create 1, 2,…, 11). How to create it, for example, Q
_{If 1} is the information to select two K ₂ ^[1] and K ₄ ^[2] , r [1] and R [1] are given by the following (Equation 49) and (Equation 5).
It is decided by 0).

[0206]

[Equation 49]

[0207]

[Equation 50]

In this way, the first signature text generator 25
Is based on the combination designation information Q _j (j = 1, 2, ..., 11),
Pseudo random number r [j] (j = 1,2, ..., 1) combining partial random numbers
1), the first signature sentence R [j] (j = 1,2, ...) of the Ergamal signature
, 11) is created and stored in the storage unit 27. (18) Creation of a constituent element of the second signature text of the El Gamal signature The first signature text R [j] (j = 1,2, ..., 11) of the El Gamal signature output from the first signature text generation unit 25. ) Is supplied to the multiplicative calculation unit 28 on the finite field. Multiplicative calculation part 2 on finite field
8 is the value X [j] (j
= 1,2, ..., 11) is calculated.

Letting x _{A be} a value on the finite field which is the public key of itself,

[0210]

[Equation 51]

In this way, the multiplicative calculation unit 28 on the finite field
Is the element X [j] (j = 1,2, ..., 11) of the second signature sentence of the Ergamal signature which is a value on 12 finite fields, and r
[j], R [j] (j = 1, 2, ..., 11) are paired and stored in the storage unit 27. (19) Creation of second signature text of Ergamal signature The message m [j] to be signed is the second signature text generator 29.
Then, r [j], R [j], and X [j] stored as a set from the storage unit 27 are input to the second signature text generation unit 29. The second signature text generation unit 29 calculates s [j] that satisfies the following (Equation 52).

[0212]

[Equation 52]

The s [j] and m [j] and R [j] thus obtained are transmitted to the receiver. And once used r
It is not necessary to store [j], R [j], and X [j] in the storage unit 27. (20) Calculation amount Since the calculation amount is almost the same as that of the second conventional example, the content is exactly the same as the above (14). When combined with the method of simultaneously performing the processing for 6 random numbers described in (Conventional example 4), the amount of calculation can be reduced to about 72.3% compared to the minimum calculation method of the conventional example.

In the above description, the calculation amount in combination with Conventional Example 4 has been described, but the same effect can be obtained by combining with Conventional Example 3.

In the third embodiment, six random numbers are exclusively divided into two, and eleven Elgamal signature first and second signature sentences are partially created. However, it can be generalized. Generally, L random numbers k _l (l = 1,2, ...
, L) are each divided into m ( _kl ) pieces, and the same effect can be obtained by creating M or less pieces of the first signature text and the second signature text of the ElGamal cipher. . However, M is given by (Equation 53).

[0216]

[Equation 53]

In the third embodiment, the random number is exclusively divided, but the same effect can be obtained by dividing the random number into the sum of positive integers smaller than the random number.

[0218]

As described above, according to the present invention, it is possible to create an element of a finite commutative group by applying a random number to a specific element on the finite commutative group at a speed higher than that of the conventional technique. When combined with the conventional example, the amount of calculation is about 72% compared to the method with the smallest amount of calculation in the conventional technique, that is, the amount of preliminary processing that can be processed in the same time is 1.39 times that of the conventional technique. . Therefore, the number of preliminary calculations is reduced, and its practical value is great.

[Brief description of drawings]

FIG. 1 is a configuration diagram of an arithmetic unit in an Elgamal encryption using an elliptic curve according to the first embodiment.

FIG. 2 is a configuration diagram of an arithmetic unit in the Ergamal cipher on a finite field according to the second embodiment.

FIG. 3 is a configuration diagram of an arithmetic unit in an Ergamal signature on a finite field according to the third embodiment.

[Explanation of symbols]

 1,11,21 Random number generation unit 2,12,22 Random number division unit 3,13,23 Bit designation unit 4,8 Integer action unit on elliptic curve 5,9,15,19 Ciphertext generation unit 6,16,26 Combination designation section 7, 17, 27 Storage section 10 Addition calculation section on elliptic curve on elliptic curve 14, 18, 24 Power calculation section on finite field 20, 28 Multiplication calculation section on finite field 25, 29 Signature sentence generation Department

Claims (4)

[Claims] 1. An arithmetic unit for generating another element of the finite commutative group by applying a different random number to a specific element of the finite commutative group by an operation defining the finite commutative group, and comprising two or more elements. A random number division unit that divides at least one random number of the above random numbers into two or more partial random numbers, and a configuration in which the partial random number output from the random number division unit is applied to the specific element of the finite commutative group An integer acting part that creates an element, and a combination of the definition operation of the finite commutative group and the inverse element operation, or one of the operations, with respect to the two or more constituent elements output from the integer acting part. An arithmetic unit in the finite commutative group, comprising: an operator generator that creates an element of the finite commutative group. 2. When a finite commutative group composed of elements on an elliptic curve E defined on a finite field is defined as E (G), an operation for defining E (G) is used to calculate E (G) A random number division for dividing at least one random number of two or more random numbers into two or more partial random numbers, which is an arithmetic unit for generating another element of E (G) by applying different random numbers to a specific element A unit, an integer acting unit that creates a constituent element that causes the partial random number output from the random number dividing unit to act on the specific element of the finite commutative group, and two or more output units from the integer acting unit. The finite commutative element according to claim 1, further comprising: an operator generator that creates an element of the E (G) by combining an additive operation or a subtractive operation on the elliptic curve E with the constituent element. An arithmetic unit in a group. 3. An arithmetic unit for generating another element of the finite field by applying a different random number to a specific element of the finite field by an operation defining a finite field, and at least one of two or more random numbers. A random number division unit that divides at least one random number into two or more partial random numbers, and an integer operation unit that creates a constituent element in which the partial random number output from the random number division unit acts on the specific element of the finite field And an operator generator that creates an element of the finite field by combining a multiplication operation on the finite field with two or more constituent elements output from the integer acting unit. An arithmetic unit in the finite commutative group according to claim 1. 4. A combination designating unit for reducing the number of elements of the finite commutative group to be generated to be smaller than the total number of partial random numbers, according to claim 1, 2, or 3. An arithmetic unit in the described finite commutative group.