JP2006078751A

JP2006078751A - Preliminary computing method for requested computing of public key code

Info

Publication number: JP2006078751A
Application number: JP2004262415A
Authority: JP
Inventors: Natsuki Ishida; 夏樹石田
Original assignee: Hitachi Software Engineering Co Ltd
Current assignee: Hitachi Software Engineering Co Ltd
Priority date: 2004-09-09
Filing date: 2004-09-09
Publication date: 2006-03-23

Abstract

<P>PROBLEM TO BE SOLVED: To provide a preliminary computing method for requested computing of a public key code such as an RSA requiring no power calculation, and to make many client devices practical as PKI tokens. <P>SOLUTION: A client device 1 which implements the preliminary computing method for requested computing of the RSA code comprises a central processing unit and main storage device 2 and a storage device 3. The storage device 3 is stored with pieces of FP[1] to PF[γ] and SP[1] to SP[γ] of power information by the present invention together with the same information with conventional arts. The client device 1 only perform multiplication processing of the power information without performing power operations by repeating processes of steps 104 and 105 to calculate pieces fp and sp of preliminary computing information. The requested computing performed thereafter is only performed by a server device as well as the conventional arts. <P>COPYRIGHT: (C)2006,JPO&NCIPI

Description

本発明は、公開鍵暗号の依頼計算の事前計算方法に係り、暗号技術のうち公開鍵暗号の復号時や署名時に実行される冪乗計算の依頼計算の事前計算方法に関する。 The present invention relates to a pre-calculation method for request calculation of public key cryptography, and more particularly to a pre-calculation method for request calculation of power calculation executed at the time of decryption or signature of public key cryptography among cryptographic techniques.

公開鍵暗号の依頼計算方法は、秘密鍵を記憶しているクライアント装置が、秘密鍵を記憶していないサーバ装置に対して、秘密鍵の保護を図りながら冪乗計算の処理を依頼する処理時間短縮を目的として実行する分散計算方法である。すなわち、依頼計算は、クライアント装置からサーバ装置に秘密鍵が漏洩することなく、クライアント装置で実行すべき冪乗計算の処理の一部をサーバ装置に実行させるものである。公開鍵暗号の依頼計算の事前計算方法は、復号したい暗号文または署名したいメッセージが入力される前、すなわち、公開鍵暗号の依頼計算を実行する前に、クライアント装置で実行する計算方法である。 The public key encryption request calculation method is a processing time in which a client device that stores a secret key requests a server device that does not store a secret key to perform a power calculation process while protecting the secret key. This is a distributed calculation method executed for the purpose of shortening. That is, the request calculation causes the server apparatus to execute a part of the power calculation process to be executed by the client apparatus without leaking the secret key from the client apparatus to the server apparatus. The public key encryption request calculation pre-calculation method is a calculation method executed on the client device before the ciphertext to be decrypted or the message to be signed is input, that is, before the public key encryption request calculation is executed.

公開鍵暗号の依頼計算方法に関する従来技術として、例えば、非特許文献１に記載された技術が知られている。この従来技術は、ＲＳＡ暗号の依頼計算方法に関するもので、ＲＳＡ暗号のＲＳＡ鍵情報と剰余群とを、楕円曲線暗号等の群を利用する公開鍵暗号の鍵情報と群とに変更することにより、公開鍵暗号の依頼計算方法に応用することができる。 As a conventional technique related to a public key encryption request calculation method, for example, a technique described in Non-Patent Document 1 is known. This prior art relates to a request calculation method for RSA encryption, and by changing RSA key information and residue group of RSA encryption into key information and group of public key encryption using a group such as elliptic curve encryption. It can be applied to a request calculation method for public key cryptography.

図３は従来技術によるＲＳＡ暗号の依頼計算の事前計算方法について説明する図であり、図３を参照して、従来技術による依頼計算の事前計算方法を説明する。図３において、１はクライアント装置、２は中央演算処理装置兼主記憶装置、３は記憶装置である。 FIG. 3 is a diagram for explaining a prior calculation method for request calculation of RSA encryption according to the prior art, and a prior calculation method for request calculation according to the prior art will be described with reference to FIG. In FIG. 3, 1 is a client device, 2 is a central processing unit and main storage device, and 3 is a storage device.

ＲＳＡ暗号の依頼計算の事前計算方法を実行するクライアント装置１は、中央演算処理装置兼主記憶装置２と、記憶装置と３から構成される。 A client apparatus 1 that executes a pre-calculation method for RSA cipher request calculation includes a central processing unit / main storage unit 2 and a storage unit 3.

記憶装置３には、ＲＳＡ公開鍵情報ｅ，ｎと、ＲＳＡ秘密鍵情報ｄと、ＲＳＡ秘密鍵二分割情報ｆｄ，ｓｄと、ＲＳＡ秘密鍵多分割情報Ｄ［１］〜Ｄ［α］と、第一指数情報ＦＥ［１］〜ＦＥ［α］と、第二指数情報ＳＥ［１］〜ＳＥ［α］と、セキュリティパラメータα，βとが記憶されている。 The storage device 3 includes RSA public key information e, n, RSA private key information d, RSA private key bisection information fd, sd, RSA private key multi-partition information D [1] to D [α], First exponent information FE [1] to FE [α], second exponent information SE [1] to SE [α], and security parameters α and β are stored.

但し、φ（ｎ）はＲＳＡ公開鍵情報ｎのオイラー関数値，Ｄ［１］〜Ｄ［α］は１以上φ（ｎ）−１以下の整数値，ＦＥ［１］〜ＦＥ［α］及びＳＥ［１］〜ＳＥ［α］は０以上β−１以下の整数値であり、ｄ＝ｆｄ×ｓｄｍｏｄφ（ｎ），ｆｄ＝Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＦＥ［ｉ］）ｍｏｄφ（ｎ），ｓｄ＝Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＳＥ［ｉ］）ｍｏｄφ（ｎ）が成り立つものとする。 Where φ (n) is the Euler function value of the RSA public key information n, D [1] to D [α] are integer values from 1 to φ (n) −1, FE [1] to FE [α], and SE [1] to SE [α] are integer values of 0 or more and β−1 or less, and d = fd × sd mod φ (n), fd = Σ (1 ≦ i ≦ α) (D [i] × FE [ i]) mod φ (n), sd = Σ (1 ≦ i ≦ α) (D [i] × SE [i]) mod φ (n).

次に、従来技術によるＲＳＡ暗号の依頼計算の事前計算方法の動作について、図３の中央演算処理装置兼主記憶装置２の内部に示したフローを参照して説明する。この処理は、ＲＳＡ暗号の依頼計算方法を実行する前に、毎回実行する必要のある処理である。 Next, the operation of the prior calculation method for RSA encryption request calculation according to the prior art will be described with reference to the flow shown in the central processing unit / main storage unit 2 in FIG. This process is a process that needs to be executed every time before executing the RSA encryption request calculation method.

（１）クライアント装置１の処理装置は、まず、記憶装置３からＲＳＡ公開鍵情報ｎと、ＲＳＡ秘密鍵二分割情報ｓｄを読み込む（ステップ３０１）。 (1) The processing device of the client device 1 first reads the RSA public key information n and the RSA secret key bisection information sd from the storage device 3 (step 301).

（２）次に、事前計算情報ｆｐに１以上ｎ−１以下のランダムな整数値を代入する（ステップ３０２）。 (2) Next, a random integer value of 1 or more and n-1 or less is substituted for the pre-calculation information fp (step 302).

（３）次に、事前計算情報ｓｐにｆｐ＾（−ｓｄ）ｍｏｄｎを代入する。但し、ｆｐ＾（−ｓｄ）は、ｆｐの（−ｓｄ）乗の値である（ステップ３０３）。 (3) Next, fp ^ (-sd) mod n is substituted for the pre-calculation information sp. However, fp ^ (-sd) is a value of fp raised to the power of (-sd) (step 303).

（４）記憶装置３に、ステップ３０２、３０３の処理で得られた事前計算情報ｆｐ，ｓｐを書き込む（ステップ３０４）。 (4) The pre-calculation information fp and sp obtained by the processing of steps 302 and 303 are written in the storage device 3 (step 304).

以上がクライアント装置１で実行される事前計算であり、クライアント装置１は、この事前計算を行った後に、サーバ装置に対して計算の依頼を行う。 The above is the pre-computation executed by the client device 1, and the client device 1 requests the server device for computation after performing this pre-calculation.

図４は従来技術によるＲＳＡ暗号の依頼計算方法について説明する図であり、次に、図４を参照して、従来技術による依頼計算方法を説明する。図４において、２’は中央演算処理装置兼主記憶装置、４はサーバ装置であり、他の符号は、図３の場合と同一である。 FIG. 4 is a diagram for explaining a request calculation method for RSA encryption according to the prior art. Next, a request calculation method according to the prior art will be described with reference to FIG. In FIG. 4, 2 'is a central processing unit and main storage device, 4 is a server device, and other reference numerals are the same as those in FIG.

従来技術による依頼計算は、クライアント装置１とサーバ装置４とが接続されて実行され、ＲＳＡ暗号の依頼計算方法を実行するクライアント装置１は、中央演算処理装置兼主記憶装置２と記憶装置３から構成され、サーバ装置４は、中央演算処理装置兼主記憶装置２’から構成される。記憶装置３には、図３で説明したＲＳＡ暗号の依頼計算の事前計算方法を実行した後の情報が記憶されている。 The request calculation according to the prior art is executed by connecting the client apparatus 1 and the server apparatus 4, and the client apparatus 1 that executes the RSA encryption request calculation method includes a central processing unit and main storage device 2 and a storage device 3. The server device 4 is configured by a central processing unit and main storage device 2 ′. The storage device 3 stores information after execution of the RSA encryption request calculation pre-calculation method described in FIG.

なお、後述において、ｘは復号したい暗号文情報または署名したいメッセージ情報であり、ｚは復号結果情報または署名結果情報である。 In the following description, x is ciphertext information to be decrypted or message information to be signed, and z is decryption result information or signature result information.

（１）クライアント装置１の処理装置は、まず、記憶装置３からＲＳＡ公開鍵情報ｎと、ＲＳＡ秘密鍵多分割情報Ｄ［１］〜Ｄ［α］と、第一指数情報ＦＥ［１］〜ＦＥ［α］と、第二指数情報ＳＥ［１］〜ＳＥ［α］と、セキュリティパラメータαと、事前計算情報ｆｐ，ｓｐとを読み込む（ステップ４０１）。 (1) First, the processing device of the client device 1 starts from the storage device 3 with the RSA public key information n, the RSA private key multi-partition information D [1] to D [α], and the first exponent information FE [1] to FE [α], second exponent information SE [1] to SE [α], security parameter α, and pre-calculation information fp, sp are read (step 401).

（２）次に、クライアント装置１は、サーバ装置４に、ｘ，ｎ，Ｄ［１］〜Ｄ［α］を送信する（ステップ４０２）。 (2) Next, the client device 1 transmits x, n, D [1] to D [α] to the server device 4 (step 402).

（３）サーバ装置４は、１≦ｉ≦αについて、第一基底情報ＦＢ［ｉ］にｘ＾Ｄ［ｉ］ｍｏｄｎを代入して、第一基底情報ＦＢ［１］〜ＦＢ［α］を算出する（ステップ４０３）。 (3) For 1 ≦ i ≦ α, the server device 4 substitutes x ^ D [i] mod n for the first basis information FB [i], and sets the first basis information FB [1] to FB [α]. Is calculated (step 403).

（４）その後、サーバ装置４は、クライアント装置１にステップ４０３で算出した第一基底情報ＦＢ［１］〜ＦＢ［α］を送信する（ステップ４０４）。 (4) Thereafter, the server device 4 transmits the first base information FB [1] to FB [α] calculated in Step 403 to the client device 1 (Step 404).

（５）クライアント装置１は、第一基底情報ＦＢ［１］〜ＦＢ［α］を受け取ると、中間結果情報ｙにｆｐ×Π（１≦ｉ≦α）（ＦＢ［ｉ］＾ＦＥ［ｉ］）ｍｏｄｎを代入して、中間結果情報ｙを算出する（ステップ４０５）。 (5) Upon receiving the first basis information FB [1] to FB [α], the client device 1 adds fp × Π (1 ≦ i ≦ α) (FB [i] ^ FE [i] to the intermediate result information y. ) Mod n is substituted to calculate intermediate result information y (step 405).

（６）クライアント装置１は、サーバ装置４にステップ４０５で算出した中間結果情報ｙを送信する（ステップ４０６）。 (6) The client device 1 transmits the intermediate result information y calculated in step 405 to the server device 4 (step 406).

（７）サーバ装置４は、１≦ｉ≦αについて、第二基底情報ＳＢ［ｉ］にｙ＾Ｄ［ｉ］ｍｏｄｎを代入して、第二基底情報ＳＢ［１］〜ＳＢ［α］を算出する（ステップ４０７）。 (7) For 1 ≦ i ≦ α, the server device 4 substitutes y ^ D [i] mod n for the second base information SB [i], and sets the second base information SB [1] to SB [α]. Is calculated (step 407).

（８）サーバ装置４は、クライアント装置１にステップ４０７で算出した第二基底情報ＳＢ［１］〜ＳＢ［α］を送信する（ステップ４０８）。 (8) The server device 4 transmits the second base information SB [1] to SB [α] calculated in Step 407 to the client device 1 (Step 408).

（９）クライアント装置１は、サーバ装置４から第二基底情報ＳＢ［１］〜ＳＢ［α］を受け取ると、ｚにｓｐ×Π（１≦ｉ≦α）（ＳＢ［ｉ］＾ＳＥ［ｉ］）ｍｏｄｎを代入する（ステップ４０９）。 (9) When the client apparatus 1 receives the second basis information SB [1] to SB [α] from the server apparatus 4, sp × Π (1 ≦ i ≦ α) (SB [i] ^ SE [i ] Mod n is substituted (step 409).

前述したような従来技術によるＲＳＡ暗号の依頼計算方法により、ＲＳＡ暗号の復号時や署名時に実行される冪乗計算を正しく実行することができ、このことは、次のように確認することができる。 According to the RSA encryption request calculation method according to the prior art as described above, the power calculation executed at the time of decryption or signature of the RSA encryption can be correctly executed, and this can be confirmed as follows. .

ｚ＝ｓｐ×Π（１≦ｉ≦α）（ＳＢ［ｉ］＾ＳＥ［ｉ］）ｍｏｄｎ
＝ｓｐ×Π（１≦ｉ≦α）（ｙ＾Ｄ［ｉ］＾ＳＥ［ｉ］）ｍｏｄｎ
＝ｓｐ×ｙ＾｛Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＳＥ［ｉ］）｝ｍｏｄｎ
＝ｓｐ×ｙ＾ｓｄｍｏｄｎ
＝ｓｐ×｛ｆｐ×Π（１≦ｉ≦α）（ＦＢ［ｉ］＾ＦＥ［ｉ］）｝＾ｓｄｍｏｄｎ
＝ｓｐ×ｆｐ＾ｓｄ×｛Π（１≦ｉ≦α）（ＦＢ［ｉ］＾ＦＥ［ｉ］）｝＾ｓｄｍｏｄｎ
＝｛Π（１≦ｉ≦α）（ＦＢ［ｉ］＾ＦＥ［ｉ］）｝＾ｓｄｍｏｄｎ
＝｛Π（１≦ｉ≦α）（ｘ＾Ｄ［ｉ］＾ＦＥ［ｉ］）｝＾ｓｄｍｏｄｎ
＝ｘ＾｛Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＦＥ［ｉ］）｝＾ｓｄｍｏｄｎ
＝ｘ＾ｆｄ＾ｓｄｍｏｄｎ
＝ｘ＾（ｆｄ×ｓｄ）ｍｏｄｎ
＝ｘ＾ｄｍｏｄｎ
前述したような従来技術により、ＲＳＡ暗号の依頼計算を行った場合にも、クライアント装置からサーバ装置にＲＳＡ秘密鍵情報ｄが漏洩することはない。なぜなら、セキュリティパラメータα，βの値を大きくすれば、第一指数情報ＦＥ［１］〜ＦＥ［α］と第二指数情報ＳＥ［１］〜ＳＥ［α］との組み合わせの数は膨大になり、サーバ装置が第一指数情報ＦＥ［１］〜ＦＥ［α］と第二指数情報ＳＥ［１］〜ＳＥ［α］とを取得できないからである。例えば、セキュリティパラメータαの値を１６，βの値を１６とすると、第一指数情報ＦＥ［１］〜ＦＥ［α］と第二指数情報ＳＥ［１］〜ＳＥ［α］との組み合わせの数は２＾１２８となる。 z = sp × Π (1 ≦ i ≦ α) (SB [i] ^ SE [i]) mod n
= Sp × Π (1 ≦ i ≦ α) (y ^ D [i] ^ SE [i]) mod n
= Sp × y ^ {Σ (1 ≦ i ≦ α) (D [i] × SE [i])} mod n
= Sp * y ^ sd mod n
= Sp × {fp × Π (1 ≦ i ≦ α) (FB [i] ^ FE [i])} ^ sd mod n
= Sp × fp ^ sd × {Π (1 ≦ i ≦ α) (FB [i] ^ FE [i])} ^ sd m od n
= {Π (1 ≦ i ≦ α) (FB [i] ^ FE [i])} ^ sd mod n
= {Π (1 ≦ i ≦ α) (x ^ D [i] ^ FE [i])} ^ sd mod n
= X ^ {Σ (1 ≦ i ≦ α) (D [i] × FE [i])} ^ sd mod n
= X ^ fd ^ sd mod n
= X ^ (fd × sd) mod n
= X ^ d mod n
Even when the RSA encryption request calculation is performed by the conventional technology as described above, the RSA private key information d is not leaked from the client device to the server device. This is because if the security parameters α and β are increased, the number of combinations of the first exponent information FE [1] to FE [α] and the second exponent information SE [1] to SE [α] becomes enormous. This is because the server device cannot acquire the first exponent information FE [1] to FE [α] and the second exponent information SE [1] to SE [α]. For example, if the value of the security parameter α is 16 and the value of β is 16, the number of combinations of the first exponent information FE [1] to FE [α] and the second exponent information SE [1] to SE [α]. Becomes 2 ^ 128.

そして、依頼計算を行わない場合のクライアント装置の処理量は、指数部ビット長がＲＳＡ秘密鍵情報ｄのビット長の冪乗計算１回である。一方、依頼計算方を行う場合のクライアント装置の処理量は、指数部ビット長がセキュリティパラメータβのビット長の冪乗計算２α回である。指数部のビット長がＬの冪乗計算１回の処理量は、乗算１．５Ｌ回の処理量とほぼ等しい。例えば、ＲＳＡ秘密鍵情報ｄのビット長を１０２４、セキュリティパラメータβのビット長を４、セキュリティパラメータαのビット長を１６とすると、依頼計算を行わない場合のクライアント装置の処理量は、乗算１５３６回の処理量となり、依頼計算を行う場合のクライアント装置の処理量は、乗算１９２回の処理量となる。従って、前述した従来技術によるＲＳＡ暗号の依頼計算方法により、クライアント装置の処理量を大幅に削減することができる。
「情報理論とその応用シリーズ４暗号と認証」、株式会社培風館、１９９６年、ｐ．１１４−１１５ When the request calculation is not performed, the processing amount of the client device is one exponentiation calculation of the exponent part bit length of the bit length of the RSA private key information d. On the other hand, the processing amount of the client device when performing the request calculation method is exponentiation calculation 2α times of the exponent part bit length of the security parameter β. The processing amount of one power calculation with the bit length of the exponent part being L is almost equal to the processing amount of 1.5L multiplications. For example, if the bit length of the RSA private key information d is 1024, the bit length of the security parameter β is 4, and the bit length of the security parameter α is 16, the processing amount of the client device when the request calculation is not performed is 1536 times multiplication. The processing amount of the client apparatus when performing the request calculation is the processing amount of 192 multiplications. Therefore, the processing amount of the client apparatus can be greatly reduced by the above-described RSA encryption request calculation method according to the prior art.
“Information Theory and Its Application Series 4 Cryptography and Authentication”, Baifukan Co., Ltd., 1996, p. 114-115

前述した従来技術によるＲＳＡ暗号の依頼計算の事前計算方法は、図３により説明したステップ３０３の処理で、指数部ビット長がＲＳＡ秘密鍵二分割情報ｓｄのビット長の冪乗計算を１回を実行する必要がある。ＲＳＡ秘密鍵二分割情報ｓｄのビット長は、ＲＳＡ秘密鍵情報ｄのビット長と等しいため、従来技術によるＲＳＡ暗号の依頼計算の事前計算の処理量は、依頼計算方法なしの場合のクライアント装置の処理量と等しくなる。また、この事前計算の結果は、サーバ装置に送信して依頼計算のために使用されるが、サーバ装置に毎回同一のデータを送信すると安全性を損なう可能性があるので、事前計算は、ＲＳＡ暗号の依頼計算を実行する前に、毎回実行する必要がある。 The prior calculation method of the RSA encryption request calculation according to the prior art described above is the process of step 303 described with reference to FIG. 3, in which the exponent part bit length is one power cycle calculation of the bit length of the RSA private key bisection information sd. Need to run. Since the bit length of the RSA private key bisection information sd is equal to the bit length of the RSA private key information d, the amount of pre-calculation of the request calculation of the RSA cipher request according to the prior art is that of the client apparatus in the case of no request calculation method It becomes equal to the processing amount. In addition, the result of this pre-calculation is transmitted to the server device and used for request calculation. However, if the same data is transmitted to the server device every time, the safety may be impaired. Before executing cryptographic request calculation, it is necessary to execute it every time.

そのため、前述した従来技術によるＲＳＡ暗号の依頼計算の事前計算方法は、その処理量を削減しないと、クライアント装置によってはＰＫＩトークンとして実用に耐えられないという問題点を生じさせてしまう。このことは、クライアント装置が携帯電話機等の携帯可能な機器のような処理能力の小さい機器である場合に特に大きな問題となる。 For this reason, the prior calculation method for RSA encryption request calculation according to the above-described prior art may cause a problem that some client devices cannot be used as a PKI token unless the processing amount is reduced. This is a particularly serious problem when the client device is a device with a small processing capability such as a portable device such as a mobile phone.

本発明の目的は、前述したような従来技術の問題点を解決し、冪乗計算を実行する必要のないＲＳＡ暗号、楕円曲線暗号等の公開鍵暗号の依頼計算の事前計算方法を提供することにある。 An object of the present invention is to solve the problems of the prior art as described above, and to provide a pre-calculation method for request calculation of public key cryptography such as RSA cryptography and elliptic curve cryptography that does not require execution of power calculation. It is in.

本発明によれば前記目的は、サーバ装置に公開鍵暗号の依頼計算を行わせるためにクライアント装置が事前計算を行う公開鍵暗号の依頼計算の事前計算方法において、前記クライアント装置内の記憶装置に事前計算情報の組と同様な関係が成立する冪乗情報を記憶しておき、前記クライアント装置がランダムに選んだ冪乗情報を乗算することにより事前計算情報を計算することにより達成される。 According to the present invention, the object is to provide a public key encryption request calculation pre-calculation method in which a client device performs pre-calculation in order to cause a server device to perform public key encryption request calculation. This is achieved by storing the power information that holds the same relationship as the set of pre-calculated information, and calculating the pre-calculated information by multiplying the power information randomly selected by the client device.

公開鍵暗号がＲＳＡ暗号である場合について具体的にいえば、前記目的は、サーバ装置が、底部分が復号したい暗号文情報または署名したいメッセージ情報であり指数部分がＲＳＡ秘密鍵多分割情報である冪乗計算を実行することにより第一基底情報を計算し、クライアント装置が、底部分が第一基底情報であり指数部分が第一指数情報である冪乗計算を実行し、さらに、事前計算情報を掛け合わせることにより中間結果情報を計算し、サーバ装置が、底部分が中間結果情報であり指数部分がＲＳＡ秘密鍵多分割情報である冪乗計算を実行することにより第二基底情報を計算し、クライアント装置が、底部分が第二基底情報であり指数部分が第二指数情報である冪乗計算を実行し、さらに、事前計算情報を掛けあわせることにより復号結果情報または署名結果情報を計算するＲＳＡ暗号の依頼計算方法に対して、クライアント装置内の記憶装置に、冪乗情報の組が事前計算情報の組と同様な関係が成立する冪乗情報を記憶し、クライアント装置が、ランダムに選んだ冪乗情報を乗算することで事前計算情報を計算することにより達成される。 More specifically, when the public key encryption is RSA encryption, the object is that the server apparatus is ciphertext information to be decrypted or message information to be signed, and the exponent part is RSA private key multi-partition information. The first base information is calculated by executing the power calculation, and the client device executes the power calculation in which the base portion is the first base information and the exponent portion is the first exponent information, and the pre-calculation information is further calculated. And the server device calculates the second base information by performing a power calculation with the base part being the intermediate result information and the exponent part being the RSA private key multi-partition information. The client device executes the power calculation with the bottom part being the second base information and the exponent part being the second exponent information, and further multiplying the precalculation information to obtain the decryption result information. Alternatively, for the RSA encryption request calculation method for calculating the signature result information, the storage information in the client device is stored in the storage device with the power information that satisfies the same relationship as the pre-calculation information set, This is achieved by the client device calculating pre-calculation information by multiplying randomly selected power information.

本発明によれば、公開鍵暗号の依頼計算の事前計算において、冪乗計算を実行する必要がなくなるので、依頼計算の事前計算を行うクライアント装置の処理量を削減することができると共に、安全性を維持することができる。これにより、携帯電話のような処理能力の小さい機器を含め、より多くのクライアント装置をＰＫＩトークンとして実用に耐えられるようにすることができる。 According to the present invention, since it is not necessary to perform a power calculation in the pre-calculation of the public key encryption request calculation, it is possible to reduce the processing amount of the client device that performs the pre-calculation of the request calculation, and to ensure safety. Can be maintained. As a result, a larger number of client devices including a device having a small processing capability such as a mobile phone can be put into practical use as a PKI token.

以下、本発明による公開鍵暗号の依頼計算の事前計算方法の実施形態を図面により詳細に説明する。 Embodiments of a pre-calculation method for public key encryption request calculation according to the present invention will be described below in detail with reference to the drawings.

図１は本発明の一実施形態によるＲＳＡ暗号の依頼計算の事前計算方法について説明する図であり、図１を参照して、本発明の実施形態による依頼計算の事前計算方法を説明する。図１における符号は、図３の場合と同様である。 FIG. 1 is a diagram for explaining a pre-calculation method for request calculation of RSA encryption according to an embodiment of the present invention. With reference to FIG. 1, a pre-calculation method for request calculation according to an embodiment of the present invention will be described. The reference numerals in FIG. 1 are the same as those in FIG.

ＲＳＡ暗号の依頼計算の事前計算方法を実行するクライアント装置１は、従来技術の場合と同様に、中央演算処理装置兼主記憶装置２と、記憶装置３とから構成される。図３には、本発明の説明に必要な構成だけを示しているが、クライアント装置１は、よく知られているように、ＣＰＵ、ハードディスク装置、主記憶装置、ディスプレイ、キーボード、マウス、通信制御部等を備えて構成される携帯電話機、ＰＤＡ、ＰＣ、ワークステーション等の情報処理装置であってよい。 The client device 1 that executes the pre-calculation method for the request calculation of the RSA encryption is composed of a central processing unit / main storage device 2 and a storage device 3 as in the case of the prior art. FIG. 3 shows only the configuration necessary for the description of the present invention. As is well known, the client device 1 has a CPU, a hard disk device, a main storage device, a display, a keyboard, a mouse, and communication control. An information processing apparatus such as a mobile phone, a PDA, a PC, or a workstation configured with a unit or the like may be used.

そして、記憶装置３には、ＲＳＡ公開鍵情報ｅ，ｎと、ＲＳＡ秘密鍵情報ｄと、ＲＳＡ秘密鍵二分割情報ｆｄ，ｓｄと、ＲＳＡ秘密鍵多分割情報Ｄ［１］〜Ｄ［α］と、第一指数情報ＦＥ［１］〜ＦＥ［α］と、第二指数情報ＳＥ［１］〜ＳＥ［α］と、セキュリティパラメータα，β，γ，δと、冪乗情報ＦＰ［１］〜ＦＰ［γ］，ＳＰ［１］〜ＳＰ［γ］が記憶されている。なお、冪乗情報ＦＰ［１］〜ＦＰ［γ］，ＳＰ［１］〜ＳＰ［γ］は、本発明のために予め算出されている情報である。 The storage device 3 stores RSA public key information e, n, RSA private key information d, RSA private key bisection information fd, sd, and RSA private key multi-partition information D [1] to D [α]. First exponent information FE [1] to FE [α], second exponent information SE [1] to SE [α], security parameters α, β, γ, δ, and power information FP [1]. ~ FP [γ], SP [1] to SP [γ] are stored. The power information FP [1] to FP [γ] and SP [1] to SP [γ] are information calculated in advance for the present invention.

但し、φ（ｎ）はＲＳＡ公開鍵情報ｎのオイラー関数値，Ｄ［１］〜Ｄ［α］は１以上φ（ｎ）−１以下の整数値，ＦＥ［１］〜ＦＥ［α］及びＳＥ［１］〜ＳＥ［α］は０以上β−１以下の整数値であり、ｄ＝ｆｄ×ｓｄｍｏｄφ（ｎ），ｆｄ＝Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＦＥ［ｉ］）ｍｏｄφ（ｎ），ｓｄ＝Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＳＥ［ｉ］）ｍｏｄφ（ｎ），１≦ｉ≦γについてＳＰ［ｉ］＝ＦＰ［ｉ］＾（−ｓｄ）ｍｏｄｎが成り立つものとする。 Where φ (n) is the Euler function value of the RSA public key information n, D [1] to D [α] are integer values from 1 to φ (n) −1, FE [1] to FE [α], and SE [1] to SE [α] are integer values from 0 to β−1, and d = fd × sd mod φ (n), fd = Σ (1 ≦ i ≦ α) (D [i] × FE [ i]) mod φ (n), sd = Σ (1 ≦ i ≦ α) (D [i] × SE [i]) SP [i] = FP [i] ^ for mod φ (n), 1 ≦ i ≦ γ (−sd) mod n is assumed to hold.

次に、本発明の実施形態によるＲＳＡ暗号の依頼計算の事前計算方法の動作について、図１の中央演算処理装置兼主記憶装置２の内部に示したフローを参照して説明する。 Next, the operation of the RSA encryption request calculation pre-calculation method according to the embodiment of the present invention will be described with reference to the flow shown in the central processing unit / main storage device 2 of FIG.

（１）クライアント装置１の処理装置は、まず、記憶装置３からＲＳＡ公開鍵情報ｎと、セキュリティパラメータγ，δと、冪乗情報ＦＰ［１］〜ＦＰ［γ］，ＳＰ［１］〜ＳＰ［γ］とを読み込む（ステップ１０１）。 (1) First, the processing device of the client device 1 stores the RSA public key information n, the security parameters γ and δ, and the power information FP [1] to FP [γ] and SP [1] to SP from the storage device 3. [Γ] is read (step 101).

（２）次に、事前計算情報ｆｐに１を代入すると共に、事前計算情報ｓｐにも１を代入する（ステップ１０２）。 (2) Next, 1 is substituted into the pre-calculation information fp and 1 is also substituted into the pre-calculation information sp (step 102).

（３）ｉに１を代入して、ステップ１０４、１０５の処理を繰り返すことを設定する（ステップ１０３）。 (3) Assign 1 to i and set to repeat the processing of steps 104 and 105 (step 103).

（４）次に、Ｒ［ｉ］に１以上γ以下のランダムな整数を代入する（ステップ１０４）。 (4) Next, a random integer between 1 and γ is substituted for R [i] (step 104).

（５）事前計算情報ｆｐにｆｐ×ＦＰ［Ｒ［ｉ］］ｍｏｄｎを代入し、事前計算情報ｓｐにｓｐ×ＳＰ［Ｒ［ｉ］］ｍｏｄｎを代入する（ステップ１０５）。 (5) Substitute fp × FP [R [i]] mod n for the pre-calculation information fp, and substitute sp × SP [R [i]] mod n for the pre-calculation information sp (step 105).

（６）ｉにｉ＋１を代入して、ｉ≦δであるか否かを判定し、ｉ≦δである間、ステップ１０４からの処理に戻って処理を繰り返す（ステップ１０６）。 (6) By substituting i + 1 for i, it is determined whether i ≦ δ or not, and while i ≦ δ, the processing returns to step 104 and is repeated (step 106).

（７）前述までの処理で算出された事前計算情報ｆｐ，ｓｐを記憶装置３に書き込んで、ここでの処理を終了する（ステップ１０７）。 (7) The pre-calculation information fp, sp calculated in the above processing is written in the storage device 3, and the processing here ends (step 107).

前述した事前計算の後の依頼計算は、図４により説明した従来技術の場合と同様に、サーバ装置に計算させることができる。 The request calculation after the above-described pre-calculation can be calculated by the server device as in the case of the prior art described with reference to FIG.

次に、前述した本発明の実施形態によるＲＳＡ暗号の依頼計算の事前計算方法により計算される事前計算情報ｆｐ，ｓｐが、従来技術によるＲＳＡ暗号の依頼計算の事前計算方法により計算される事前計算情報ｆｐ，ｓｐと同様なものとなることについて説明する。ｓｐ＝Π（１≦ｉ≦δ）（ＳＰ［Ｒ［ｉ］］）ｍｏｄｎ
＝Π（１≦ｉ≦δ）（ＦＰ［Ｒ［ｉ］］＾（−ｓｄ））ｍｏｄｎ
＝｛Π（１≦ｉ≦δ）ＦＰ［Ｒ［ｉ］］｝＾（−ｓｄ）ｍｏｄｎ
＝ｆｐ＾（−ｓｄ）ｍｏｄｎ
前述した本発明の実施形態によるＲＳＡ暗号の依頼計算の事前計算の処理量は、乗算２δ回である。従来技術によるＲＳＡ暗号の依頼計算の事前計算の処理量は、指数部ビット長がＲＳＡ秘密鍵二分割情報ｓｄのビット長の冪乗計算１回である。例えば、セキュリティパラメータδを２０、ＲＳＡ秘密鍵二分割情報ｓｄのビット長を１０２４とすると、本発明の実施形態でのＲＳＡ暗号の依頼計算の事前計算の処理量は、乗算４０回の処理量であり、従来技術でのＲＳＡ暗号の依頼計算の事前計算の処理量は、乗算１５３６回の処理量である。このように、本発明の実施形態によるＲＳＡ暗号の依頼計算の事前計算方法は、クライアント装置の処理量を削減することができる。 Next, the pre-calculation information fp, sp calculated by the RSA encryption request calculation pre-calculation method according to the embodiment of the present invention described above is calculated by the RSA encryption request calculation pre-calculation method according to the prior art. The fact that the information is similar to the information fp, sp will be described. sp = Π (1 ≦ i ≦ δ) (SP [R [i]]) mod n
= Π (1 ≦ i ≦ δ) (FP [R [i]] ^ (− sd)) mod n
= {Π (1 ≦ i ≦ δ) FP [R [i]]} ^ (− sd) mod n
= Fp ^ (-sd) mod n
The amount of pre-calculation of RSA cipher request calculation according to the above-described embodiment of the present invention is 2δ multiplications. The processing amount of the prior calculation of the request calculation of the RSA encryption according to the prior art is that the exponent part bit length is one power calculation of the bit length of the RSA private key bisection information sd. For example, assuming that the security parameter δ is 20 and the bit length of the RSA secret key bisection information sd is 1024, the processing amount of the pre-calculation of the RSA encryption request calculation in the embodiment of the present invention is the processing amount of 40 multiplications. Yes, the processing amount of the pre-calculation of RSA encryption request calculation in the prior art is the processing amount of 1536 multiplications. Thus, the RSA encryption request calculation pre-calculation method according to the embodiment of the present invention can reduce the processing amount of the client device.

また、本発明の実施形態によるＲＳＡ暗号の依頼計算の事前計算方法を用いても、クライアント装置からサーバ装置にＲＳＡ秘密鍵情報ｄが漏洩することはない。なぜなら、セキュリティパラメータγ，δを大きくすれば、事前計算情報ｆｐ，ｓｐの組み合わせの数は膨大になり、サーバ装置が事前計算情報ｆｐ，ｓｐを取得することができないからである。例えば、セキュリティパラメータγを３２，δを２０とすると、事前計算情報ｆｐ，ｓｐの組み合わせの数は２＾１００という大きなものとなる。 Further, even when the RSA encryption request calculation pre-calculation method according to the embodiment of the present invention is used, the RSA private key information d does not leak from the client device to the server device. This is because if the security parameters γ and δ are increased, the number of combinations of the pre-calculation information fp and sp becomes enormous and the server device cannot acquire the pre-calculation information fp and sp. For example, when the security parameter γ is 32 and δ is 20, the number of combinations of the pre-calculation information fp and sp is as large as 2 ^ 100.

前述したように、本発明の実施形態により、安全性を維持しつつ公開鍵暗号の依頼計算の事前計算の処理量を削減することができ、より多くのクライアント装置をＰＫＩトークンとして実用に耐えられるようにすることができる。 As described above, according to the embodiment of the present invention, it is possible to reduce the amount of pre-calculation processing for request calculation of public key encryption while maintaining security, and more client devices can be practically used as PKI tokens. Can be.

前述した本発明の実施形態は、ＲＳＡ暗号のＲＳＡ鍵情報と剰余群とを、楕円曲線暗号等の群を利用する公開鍵暗号の鍵情報と群とに変更することにより、公開鍵暗号の依頼計算の事前計算方法に応用することができ、次に、これについて説明する。 In the embodiment of the present invention described above, the RSA key information and the remainder group of the RSA cipher are changed to the key information and group of the public key cipher that uses a group such as an elliptic curve cipher. This can be applied to a calculation pre-calculation method, which will be described next.

図２は本発明の他の実施形態による楕円曲線暗号の依頼計算の事前計算方法について説明する図であり、図２を参照して、本発明の他の実施形態による依頼計算の事前計算方法を説明する。図２における符号は、図３の場合と同様であり、また、楕円曲線暗号の依頼計算の事前計算方法を実行するクライアント装置１は、図１の場合と同様に、中央演算処理装置兼主記憶装置２と、記憶装置３とから構成される。 FIG. 2 is a diagram for explaining a pre-calculation method for request calculation of elliptic curve cryptography according to another embodiment of the present invention. Referring to FIG. 2, a pre-calculation method for request calculation according to another embodiment of the present invention is described. explain. The reference numerals in FIG. 2 are the same as those in FIG. 3, and the client apparatus 1 that executes the pre-calculation method for the request calculation of elliptic curve cryptography is the central processing unit and main memory as in FIG. It comprises a device 2 and a storage device 3.

記憶装置３には、楕円曲線公開鍵情報Ｅ，Ｇ［１］〜Ｇ［２］と、楕円曲線秘密鍵情報ｄと、楕円曲線秘密鍵二分割情報ｆｄ，ｓｄと、楕円曲線秘密鍵多分割情報Ｄ［１］〜Ｄ［α］と、第一指数情報ＦＥ［１］〜ＦＥ［α］と、第二指数情報ＳＥ［１］〜ＳＥ［α］と、セキュリティパラメータα，β，γ，δと、スカラー倍情報ＦＰ［１］〜ＦＰ［γ］，ＳＰ［１］〜ＳＰ［γ］とが記憶されている。 The storage device 3 includes elliptic curve public key information E, G [1] to G [2], elliptic curve secret key information d, elliptic curve secret key bisection information fd, sd, and elliptic curve secret key multi-partition. Information D [1] to D [α], first index information FE [1] to FE [α], second index information SE [1] to SE [α], security parameters α, β, γ, δ and scalar multiplication information FP [1] to FP [γ], SP [1] to SP [γ] are stored.

但し、Ｅは楕円曲線，Ｈは楕円曲線上の巡回群，｜Ｈ｜は楕円曲線上の巡回群の位数，Ｇ［１］〜Ｇ［２］及びＦＰ［１］〜ＦＰ［γ］及びＳＰ［１］〜ＳＰ［γ］は楕円曲線上の点，ｄ及びｆｄ及びｓｄ及びＤ［１］〜Ｄ［α］は１以上｜Ｈ｜−１以下の整数値，ＦＥ［１］〜ＦＥ［α］及びＳＥ［１］〜ＳＥ［α］は０以上β−１以下の整数値であり、楕円曲線Ｅ上の演算でＧ［２］＝ｄ×Ｇ［１］，ｄ＝ｆｄ×ｓｄｍｏｄ｜Ｈ｜，ｆｄ＝Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＦＥ［ｉ］）ｍｏｄ｜Ｈ｜，ｓｄ＝Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＳＥ［ｉ］）ｍｏｄ｜Ｈ｜，１≦ｉ≦γについて楕円曲線Ｅ上の演算でＳＰ［ｉ］＝ＦＰ［ｉ］×（−ｓｄ）が成り立つものとする。 Where E is an elliptic curve, H is a cyclic group on the elliptic curve, | H | is the order of the cyclic group on the elliptic curve, G [1] to G [2] and FP [1] to FP [γ] and SP [1] to SP [γ] are points on the elliptic curve, d and fd and sd and D [1] to D [α] are integer values of 1 to | H | −1, and FE [1] to FE. [Α] and SE [1] to SE [α] are integer values of 0 or more and β−1 or less, and G [2] = d × G [1] and d = fd × sd in the calculation on the elliptic curve E. mod | H |, fd = Σ (1 ≦ i ≦ α) (D [i] × FE [i]) mod | H |, sd = Σ (1 ≦ i ≦ α) (D [i] × SE [i ]) It is assumed that SP [i] = FP [i] × (−sd) holds in the calculation on the elliptic curve E for mod | H |, 1 ≦ i ≦ γ.

次に、本発明の他の実施形態による楕円曲線暗号の依頼計算の事前計算方法の動作について、図２の中央演算処理装置兼主記憶装置２の内部に示したフローを参照して説明する。 Next, the operation of the pre-calculation method for request calculation of elliptic curve cryptography according to another embodiment of the present invention will be described with reference to the flow shown inside the central processing unit / main storage unit 2 in FIG.

（１）クライアント装置１の処理装置は、まず、記憶装置３から楕円曲線公開鍵情報Ｅと、セキュリティパラメータγ，δと、スカラー倍情報ＦＰ［１］〜ＦＰ［γ］，ＳＰ［１］〜ＳＰ［γ］とを読み込む（ステップ２０１）。 (1) The processing device of the client device 1 first stores the elliptic curve public key information E, the security parameters γ and δ, and the scalar multiplication information FP [1] to FP [γ] and SP [1] to SP from the storage device 3. SP [γ] is read (step 201).

（２）次に、事前計算情報ｆｐに無限遠点を代入すると共に、事前計算情報ｓｐにも無限遠点を代入する（ステップ２０２）。 (2) Next, the infinity point is substituted for the precalculation information fp, and the infinity point is substituted for the precalculation information sp (step 202).

（３）ｉに１を代入して、ステップ２０４、２０５の処理を繰り返すことを設定する（ステップ２０３）。 (3) Assign 1 to i and set to repeat the processing of steps 204 and 205 (step 203).

（４）次に、Ｒ［ｉ］に１以上γ以下のランダムな整数を代入する（ステップ２０４）。 (4) Next, a random integer between 1 and γ is substituted for R [i] (step 204).

（５）事前計算情報ｆｐに楕円曲線Ｅ上の演算でｆｐ＋ＦＰ［Ｒ［ｉ］］を代入し、事前計算情報ｓｐに楕円曲線Ｅ上の演算でｓｐ＋ＳＰ［Ｒ［ｉ］］を代入する（ステップ２０５）。 (5) Substituting fp + FP [R [i]] by the calculation on the elliptic curve E into the precalculation information fp, and substituting sp + SP [R [i]] by the calculation on the elliptic curve E into the precalculation information sp (step) 205).

（６）ｉにｉ＋１を代入して、ｉ≦δであるか否かを判定し、ｉ≦δである間、ステップ２０４からの処理に戻って処理を繰り返す（ステップ２０６）。 (6) i + 1 is substituted into i to determine whether i ≦ δ or not, and while i ≦ δ, the processing returns to step 204 and repeats the processing (step 206).

（７）前述までの処理で算出された事前計算情報ｆｐ，ｓｐを記憶装置３に書き込んで、ここでの処理を終了する（ステップ２０７）。 (7) The pre-calculation information fp, sp calculated in the above processing is written in the storage device 3, and the processing here is terminated (step 207).

本発明の一実施形態によるＲＳＡ暗号の依頼計算の事前計算方法について説明する図である。It is a figure explaining the prior calculation method of the request calculation of RSA encryption by one Embodiment of this invention. 本発明の他の実施形態による楕円曲線暗号の依頼計算の事前計算方法について説明する図である。It is a figure explaining the prior calculation method of the request calculation of elliptic curve encryption by other embodiment of this invention. 従来技術によるＲＳＡ暗号の依頼計算の事前計算方法について説明する図である。It is a figure explaining the prior calculation method of the request calculation of RSA encryption by a prior art. 従来技術によるＲＳＡ暗号の依頼計算方法について説明する図である。It is a figure explaining the request calculation method of RSA encryption by a prior art.

Explanation of symbols

１クライアント装置
２、２’ 中央演算処理装置兼主記憶装置
３記憶装置
４サーバ装置 DESCRIPTION OF SYMBOLS 1 Client device 2, 2 'Central processing unit and main storage device 3 Storage device 4 Server device

Claims

In a public key encryption request calculation pre-calculation method in which a client device performs pre-calculation in order to cause a server device to perform public key encryption request calculation, a relationship similar to a set of pre-calculation information in a storage device in the client device A pre-calculation method for request calculation of public key cryptography, wherein the pre-calculation information is calculated by storing the power information satisfying the above and multiplying the power information randomly selected by the client device.

The public key encryption request calculation pre-calculation method according to claim 1, wherein the public key encryption is an RSA encryption.

2. The public key encryption request calculation pre-calculation method according to claim 1, wherein the public key encryption is elliptic curve encryption.