[go: up one dir, main page]

JP2005513564A5 - - Google Patents

Download PDF

Info

Publication number
JP2005513564A5
JP2005513564A5 JP2003555732A JP2003555732A JP2005513564A5 JP 2005513564 A5 JP2005513564 A5 JP 2005513564A5 JP 2003555732 A JP2003555732 A JP 2003555732A JP 2003555732 A JP2003555732 A JP 2003555732A JP 2005513564 A5 JP2005513564 A5 JP 2005513564A5
Authority
JP
Japan
Prior art keywords
proof
integer
modulo
public key
designed
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
JP2003555732A
Other languages
Japanese (ja)
Other versions
JP2005513564A (en
Filing date
Publication date
Priority claimed from FR0116789A external-priority patent/FR2834153B1/en
Application filed filed Critical
Publication of JP2005513564A publication Critical patent/JP2005513564A/en
Publication of JP2005513564A5 publication Critical patent/JP2005513564A5/ja
Pending legal-status Critical Current

Links

Claims (57)

第１のエンティティ(A)は、第１のエンティティ(A)により秘密にされている秘密鍵を使って、前記秘密鍵に関連付けられている公開鍵を使って第２のエンティティ(B)により検証可能なプルーフを生成する暗号法であって、プルーフの少なくとも１つの要素が前記秘密鍵を復元することができないデータ項目のオープンデジタル処理により少なくとも一部生成されるステップ(5,15)を含むことを特徴とする暗号法。   The first entity (A) verifies with the second entity (B) using the public key associated with the secret key, using the secret key kept secret by the first entity (A). An encryption method for generating a possible proof, comprising at least one step (5, 15) wherein at least one element of the proof is generated at least in part by open digital processing of a data item for which the private key cannot be recovered Cryptography characterized by 暗号法であって、
− 第１のエンティティ(A)が、第１のエンティティ(A)により秘密にされている第１の乱数を使って、プルーフの第１の要素を生成する第１のステップ(1、9、20)と、
− １つまたは複数の共通数と呼ばれるものがプルーフの第１の要素と関連して生成され、したがって第１のエンティティ(A)および第２のエンティティ(B)が前記１つまたは複数の共通数を認識していなければならない第２のステップ(11,23)と、
− 第１の乱数を伴う少なくとも第１の秘密鍵整数と少なくとも１つの前記共通数とを組み合わせることにより、第１のエンティティ(A)は前記秘密鍵のイメージを生成する第３のステップ(13、24)と、
− 前記公開鍵の第１の部分をプルーフの第２の要素に適用し、かつ前記公開鍵の少なくとも第２の部分を前記共通数の少なくとも１つに適用することによって、第２のエンティティ(B)がプルーフの第１の要素とプルーフの第２の要素との一致を検証できるようにするために、プルーフの第２の要素が、前記秘密鍵のイメージに対して、エンティティ(C)により実行可能なオープンデジタル処理オペレーションを適用することにより生成される第４のステップ(5、15)と
を含むことを特徴とする請求項１に記載の暗号法。 Cryptography,
A first step (1, 9, 20) in which the first entity (A) generates a first element of the proof using a first random number kept secret by the first entity (A); )When,
-What is called one or more common numbers is generated in connection with the first element of the proof, so that the first entity (A) and the second entity (B) are said one or more common numbers A second step (11, 23) that must be recognized, and
A third step (13, 13) in which the first entity (A) generates an image of the secret key by combining at least a first secret key integer with a first random number and at least one of the common numbers; 24)
-Applying a first part of the public key to a second element of the proof and applying at least a second part of the public key to at least one of the common numbers; The second element of the proof is executed by the entity (C) on the image of the secret key in order to be able to verify the match between the first element of the proof and the second element of the proof A cryptography method according to claim 1, characterized in that it comprises a fourth step (5, 15) generated by applying possible open digital processing operations. 暗号法であって、
− 第１のステップ(1、9、20)において、第１のエンティティ(A)は、第１のエンティティ(A)により秘密にされている秘密鍵に含まれる第１の整数sよりも非常に大きい第１の乱数rを生成し、第１のエンティティ(A)は、前記公開鍵に含まれる場合も含まれない場合もあり、その指数が第１の乱数rであるところの第１の整数Gを、nを法とする累乗計算した後に得られるプルーフの第１の要素を生成し、
− 第３のステップ(13、24)において、第１のエンティティ(A)は、第１の乱数rと少なくとも第１の秘密鍵整数sの一次結合により前記秘密鍵のイメージyを生成し、前記一次結合の少なくとも１つの乗法的係数は、前記共通数または前記共通数のうちの１つであり、
− 第４のステップ(5、15)において、生成されたプルーフYの第２の要素は、前記公開鍵に含まれる場合も含まれない場合もあり、その指数が秘密鍵のイメージyであるところの第２の整数gの、nを法とする累乗に等しく、第２の整数gは、第１の整数Gが、前記公開鍵に含まれる場合も含まれない場合もあり、第３の整数ｅを指数とするところの第２の整数gの、nを法とする累乗となるような整数であることを特徴とする請求項２に記載の暗号法。 Cryptography,
-In the first step (1, 9, 20), the first entity (A) is much more than the first integer s contained in the secret key kept secret by the first entity (A). Generate a large first random number r, and the first entity (A) may or may not be included in the public key, and the first integer whose index is the first random number r Generate a first element of the proof obtained after computing G to a power modulo n;
-In a third step (13, 24), the first entity (A) generates the secret key image y by a linear combination of a first random number r and at least a first secret key integer s; At least one multiplicative factor of the linear combination is the common number or one of the common numbers;
-In the fourth step (5, 15), the second element of the generated proof Y may or may not be included in the public key, where the exponent is the image y of the private key Is equal to a power modulo n, and the second integer g may or may not be included in the public key, and the third integer g 3. The encryption method according to claim 2, wherein the second integer g, where e is an exponent, is an integer that is a power modulo n. 第４のステップにおいて、プルーフYの第２の要素は、第２のエンティティ(B)に送信されることを特徴とし、また、プルーフの第１の要素が、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積に一致することを、第２のエンティティ(B)が検証する第５のステップ(8、17、22)を含むことを特徴とする請求項３に記載の暗号法。   In the fourth step, the second element of the proof Y is transmitted to the second entity (B), and the first element of the proof has an exponent of the third integer e Match the power of the second element of a proof Y and the power of the fourth integer v contained in the public key whose exponent is the common number c, modulo n. Encryption method according to claim 3, characterized in that it comprises a fifth step (8, 17, 22) verified by two entities (B). 第４のステップ(5、15)は、第１のエンティティ(A)以外の、第１のエンティティ(A)から秘密鍵イメージyを受信するエンティティ(C)により実行されることを特徴とする請求項２から４までのいずれか一項に記載の暗号法。   The fourth step (5, 15) is performed by an entity (C) that receives the secret key image y from the first entity (A) other than the first entity (A). Item 5. The encryption method according to any one of Items 2 to 4. 第４のステップ(15)は、第１のエンティティ(A)により実行されることを特徴とする請求項２から４のいずれか一項に記載の暗号法。   Cryptography according to any one of claims 2 to 4, characterized in that the fourth step (15) is performed by the first entity (A). 第４のステップは、
− 第１のエンティティ(A)は、イメージyを、イメージyを表すデータワードのu個の下位ビットにより表される第１の部分イメージy'と、前記データワードの残りの上位ビットにより表される第２の部分イメージy"とに分解し、また第１のエンティティ(A)は、第１のコンポーネントY'とプルーフの第２の要素の第２のコンポーネントg'を生成し、前記コンポーネントでは以下が成り立ち、
Figure 2005513564
 また第１のエンティティ(A)は、第１のコンポーネントY'、第２のコンポーネントg'、および第２の部分イメージy"を中間エンティティ(C)に送信する、第１のサブステップ(18)と、
− 中間エンティティ(C)は、第２の部分イメージy"を指数とする第２のコンポーネントg'の累乗を第１のコンポーネントY'に掛けることによりプルーフYの第２の要素を生成し、中間エンティティ(C)は、プルーフYの第２の要素を第２のエンティティ(B)に送信する第２のサブステップ(25)と
を含むことを特徴とする請求項２から４のいずれか一項に記載の暗号法。 The fourth step is
The first entity (A) is represented by image y by a first partial image y ′ represented by u lower bits of the data word representing image y and the remaining upper bits of said data word And the first entity (A) generates a first component Y ′ and a second component g ′ of the second element of the proof, The following holds:
Figure 2005513564
 The first entity (A) also sends the first component Y ′, the second component g ′, and the second partial image y ″ to the intermediate entity (C), a first sub-step (18) When,
The intermediate entity (C) generates a second element of the proof Y by multiplying the first component Y ′ by the power of the second component g ′ with the second partial image y ″ as an index, The entity (C) comprises a second sub-step (25) for transmitting the second element of the proof Y to the second entity (B). The encryption method described in. 第２のステップ(11)は、第１のエンティティ(A)から受信したプルーフの第１の要素について、セキュリティ間隔の範囲内の少なくとも１つの共通数を選択し、前記共通数を第１のエンティティ(A)に送信する第２のエンティティ(B)により実行されることを特徴とする請求項２から７のいずれか一項に記載の暗号法。   The second step (11) selects at least one common number within the security interval for the first element of the proof received from the first entity (A), and sets the common number to the first entity. The encryption method according to any one of claims 2 to 7, wherein the encryption method is executed by a second entity (B) that transmits to (A). 第２のステップ(23)は、プルーフの第１の要素と、前記共通数が添付されるデジタルメッセージMとに基づいて、少なくとも１つの共通数を生成する第１のエンティティ(A)により実行されることを特徴とする請求項２から７のいずれか一項に記載の暗号法。   The second step (23) is performed by the first entity (A) generating at least one common number based on the first element of the proof and the digital message M to which the common number is attached. The cryptographic method according to any one of claims 2 to 7, characterized in that: 第５のステップ(17)において、プルーフxの第１の要素が、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積に等しいときに、一致が検証されることを特徴とする請求項４に記載の暗号法。   In the fifth step (17), the first element of the proof x is a power of the second element of the proof Y whose index is the third integer e, and the public whose index is the common number c 5. The encryption method according to claim 4, wherein a match is verified when equal to a product modulo n with a power of a fourth integer v included in the key. 第５のステップ(22)において、プルーフの第１の要素が、プルーフの第１の要素が添付されるデジタルメッセージMおよび指数が第３の整数eであるプルーフYの第２の要素の累乗と指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗のnを法とする積の関数に等しいときに一致が検証されることを特徴とする請求項４に記載の暗号法。   In a fifth step (22), the first element of the proof is a digital message M to which the first element of the proof is attached and the power of the second element of the proof Y having the third integer e. 5. The match is verified when an exponent is equal to a function of a product modulo n of a power of a fourth integer v included in the public key that is the common number c. Cryptography. 第５のステップ(8)において、共通数が、デジタルメッセージMと、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しい場合に、一致が検証されることを特徴とする請求項４に記載の暗号法。   In the fifth step (8), the public number is the digital message M, the power of the second element of the proof Y whose exponent is the third integer e, and the public number whose exponent is the common number c 5. A cryptography method according to claim 4, wherein the match is verified if it is equal to a function of a product modulo n with a power of a fourth integer v contained in the key. プルーフの第１の要素は、前記公開鍵に含まれる場合もあれば含まれない場合もあり、その指数が第１の乱数rである第１の整数Gの、nを法とする累乗に等しいことを特徴とする請求項３に記載の暗号法。   The first element of the proof may or may not be included in the public key and is equal to the power of the first integer G whose exponent is the first random number r modulo n. The encryption method according to claim 3, wherein: 第１の整数Gおよび第４の公開鍵整数vは、公式
G=ge modulo n
v=G-s modulo n
で与えられ、この等式は、公式
x=Yevc modulo n
によって検証されることを特徴とする請求項１３に記載の暗号法。 The first integer G and the fourth public key integer v are
G = g e modulo n
v = G -s modulo n
This equation is given by
x = Y e v c modulo n
The encryption method according to claim 13, wherein the encryption method is verified by: 第４の公開鍵整数vは、公式
G=ge modulo n
v=Gs(modulo n)
で与えられ、この等式は、公式
Ye=vcx modulo n
によって検証されることを特徴とする請求項１３に記載の暗号法。 The fourth public key integer v is the formula
G = g e modulo n
v = G s (modulo n)
This equation is given by
Y e = v c x modulo n
The encryption method according to claim 13, wherein the encryption method is verified by: 第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ、公式
G=g-e modulo n
v=G-s modulo n
で与えられ、この等式は、公式Yex=ve modulo nによって検証されることを特徴とする請求項１３に記載の暗号法。 The first public key integer G and the fourth public key integer v are respectively
G = g -e modulo n
v = G -s modulo n
14. The cryptography according to claim 13, characterized in that this equation is verified by the formula Y e x = v e modulon. 暗号法であって、
− 第２のステップにおいて、２つの共通数aおよびbはプルーフxの第１の要素に関して生成され、
− 第３のステップにおいて、一次結合は、公式
y=ar+bs
によって与えられ、
− 第５のステップにおいて、一致は、等式
Yevb=xa modulo n
によって検証されることを特徴とする請求項１３に記載の暗号法。 Cryptography,
-In the second step, two common numbers a and b are generated for the first element of proof x;
-In the third step, the linear combination is the formula
y = ar + bs
Given by
-In the fifth step, the match is equality
Y e v b = x a modulo n
The encryption method according to claim 13, wherein the encryption method is verified by: 秘密鍵が複数の秘密数s1、s2、...を含む場合、
− 第２のステップにおいて、同じ数の共通数c1、c2、...が、プルーフxの第１の要素に関して生成され、
− 第３のステップにおいて、一次結合は、公式
y=r+c1s1+c2s2+...
によって与えられ、
− 第５のステップにおいて、一致は、同じ数の第４の公開鍵整数v1、v2、...により、等式
Yev1c1v2c2...=x modulo n
を使って検証されることを特徴とする請求項１３に記載の暗号法。 If the secret key contains multiple secret numbers s1, s2, ...
-In the second step, the same number of common numbers c1, c2, ... is generated for the first element of proof x;
-In the third step, the linear combination is the formula
y = r + c1s1 + c2s2 + ...
Given by
-In the fifth step, the match is equalized by the same number of fourth public key integers v1, v2, ...
Y e v1 c1 v2 c2 ... = x modulo n
The encryption method according to claim 13, wherein the encryption method is verified using the encryption method. 公開鍵が特に、第１のエンティティ(A)からその素数が知られている法nを含む場合、第１のステップは中国の剰余定理と呼ばれる手法を使用することにより高速化されることを特徴とする請求項３に記載の暗号法。   The first step is speeded up by using a technique called the Chinese remainder theorem, especially if the public key contains a modulus n whose prime number is known from the first entity (A) The encryption method according to claim 3. 公開鍵は、第２のステップでこの方法を開始するために、プルーフxの第１の要素のあらかじめ計算された少なくとも１つの値を含むことを特徴とする請求項２に記載の暗号法。   3. A cryptography method according to claim 2, characterized in that the public key comprises at least one pre-calculated value of the first element of proof x to start the method in the second step. 公開鍵は、プルーフxの第１の要素のk個のあらかじめ計算された値を含み、第２のステップから第５のステップまでの実行を、繰り返し毎にプルーフの第１の要素の異なる値を使ってk回繰り返すことを特徴とする請求項２０に記載の暗号法。   The public key contains k pre-computed values of the first element of proof x, and the execution from the second step to the fifth step is repeated with different values of the first element of proof. 21. The encryption method according to claim 20, wherein the encryption method is repeated k times. プルーフの第１の要素は、前記公開鍵に含まれる場合も含まれない場合もあり、その指数は第１の乱数rである、第１の整数Gの、nを法とする累乗の関数fに等しく、第５のステップの検証をこの関数の結果に基づいて行うことを特徴とする請求項２に記載の暗号法。   The first element of the proof may or may not be included in the public key, the exponent of which is a first random number r, a first integer G, a power function modulo n, f The cryptographic method according to claim 2, wherein the verification of the fifth step is performed based on the result of the function. プルーフを生成するための、秘密にされ侵入者に対する保護処置が講じられている秘密鍵を与えられた証明者デバイスであって、前記秘密鍵に関連付けられている公開鍵を使用してその検証を行うことで、デバイス(30)が前記プルーフの発信元であることを保証することが可能であり、
− デバイス(30)内に秘密にされている第１の乱数に基づいて、プルーフの第１の要素を生成し、第１の乱数を持った少なくとも第１の秘密鍵整数と、プルーフの第１の要素に関連付けられている複数の共通数のうち少なくとも１つとを組み合わせることにより、前記秘密鍵のイメージを生成し、かつ、
前記公開鍵の第１の部分をプルーフの第２の要素に適用し、前記公開鍵の少なくとも第２の部分を前記共通数の少なくとも１つに適用することにより、オープンデジタル処理オペレーションを、プルーフの第１の要素とプルーフの第２の要素との一致を検証することを可能にする前記秘密鍵イメージに適用することによって、プルーフの第２の要素を生成することが可能であるように設計されている計算手段(37)と、
− プルーフの少なくとも前記第１の要素を伝送するように設計されている通信手段(34)を備えることを特徴とする証明者デバイス。 A certifier device that has been given a secret key that is secret and protected against intruders to generate a proof and validates it using the public key associated with the secret key. By doing so, it is possible to ensure that the device (30) is the source of the proof,
Generating a first element of the proof based on a first random number kept secret in the device (30), at least a first secret key integer with the first random number, and a proof first Generating an image of the secret key by combining with at least one of a plurality of common numbers associated with the elements of:
By applying a first part of the public key to a second element of the proof and applying at least a second part of the public key to at least one of the common numbers, an open digital processing operation is performed. Designed to be able to generate a second element of the proof by applying to the secret key image that allows verification of the match between the first element and the second element of the proof. Calculating means (37),
A prover device, characterized in that it comprises communication means (34) designed to transmit at least the first element of the proof. 証明者デバイス(30)であって、
− 一方で、計算手段(37)は、秘密にされている秘密鍵に含まれる第１の整数sよりもかなり大きい第１の乱数rを生成し、第１の乱数rを指数として前記公開鍵に含まれている場合もいない場合もある第１の整数Gの、nを法とする累乗を計算することによりプルーフの第１の要素を生成するように設計され、
− 他方で、計算手段(37)は、第１の乱数rと少なくとも第１の秘密鍵整数sの一次結合により前記秘密鍵のイメージyを生成し、前記一次結合の少なくとも１つの乗法的係数は前記共通数または前記共通数のうちの１つであるように設計されることを特徴とする請求項２３に記載の証明者デバイス。 A certifier device (30),
-On the other hand, the calculation means (37) generates a first random number r that is considerably larger than the first integer s included in the secret key that is kept secret, and uses the first random number r as an index to generate the public key. Is designed to generate the first element of the proof by computing the power of the first integer G, which may or may not be included, modulo n,
On the other hand, the calculation means (37) generates the image y of the secret key by a linear combination of the first random number r and at least the first secret key integer s, and the at least one multiplicative coefficient of the linear combination is 24. The prover device of claim 23, wherein the prover device is designed to be the common number or one of the common numbers. 通信手段(34)は、プルーフの第１の要素を伝送した後に前記共通数を受信するように設計されていることを特徴とする請求項２３または２４のいずれか一項に記載の証明者デバイス(30)。   25. A prover device according to any one of claims 23 or 24, characterized in that the communication means (34) are designed to receive the common number after transmitting the first element of the proof. (30). 通信手段(34)は、秘密鍵イメージを伝送するように設計されていることを特徴とする請求項２３から２５のいずれか一項に記載の証明者デバイス(30)。   26. The prover device (30) according to any one of claims 23 to 25, characterized in that the communication means (34) are designed to transmit a secret key image. 通信手段(37)は、プルーフの第２の要素を生成するように設計されていることを特徴とする請求項２３から２５のいずれか一項に記載の証明者デバイス(30)。   26. The prover device (30) according to any one of claims 23 to 25, characterized in that the communication means (37) are designed to generate a second element of the proof. 証明者デバイス(30)であって、
計算手段(37)は、イメージyを、イメージyを表すデータワードの下位ビットにより表される第１の部分イメージy'と、データワードの残りの上位ビットにより表される第２の部分イメージy"とに分解し、また第１のコンポーネントY'とプルーフの第２の要素の第２のコンポーネントg'を生成し、前記コンポーネントでは以下が成り立ち、
Figure 2005513564
 ただし、gは、第１の公開鍵整数Gが前記公開鍵に含まれる第３の整数eを指数とする第２の整数gのnを法とする累乗となるような第２の整数であり、
通信手段(34)は、第１のコンポーネントY'、第２のコンポーネントg'、および第２の部分イメージy"を伝送するように設計されることを特徴とする請求項２４から２５のいずれか一項に記載の証明者デバイス(30)。 A certifier device (30),
The calculating means (37) determines the image y from the first partial image y ′ represented by the lower bits of the data word representing the image y and the second partial image y represented by the remaining upper bits of the data word. And generate a first component Y ′ and a second component g ′ of the second element of the proof, in which the following holds:
Figure 2005513564
 Where g is a second integer such that the first public key integer G is a power modulo n of the second integer g with the third integer e included in the public key as an index. ,
The communication means (34) is designed to transmit a first component Y ', a second component g' and a second partial image y ". The prover device (30) according to one item. 計算手段(37)は、プルーフの第１の要素と前記共通数が添付されるデジタルメッセージMとに基づいて、少なくとも１つの共通数を生成するように設計されていることを特徴とする請求項２３および２４のいずれか一項に記載の証明者デバイス(30)。   The calculating means (37) is designed to generate at least one common number based on the first element of the proof and the digital message M to which the common number is attached. The prover device (30) according to any one of claims 23 and 24. 計算手段(37)は、前記公開鍵に含まれる場合も含まれない場合もあり、指数は第１の乱数rである、第１の整数Gの、nを法とする累乗を計算することによりプルーフの第１の要素を生成するように設計されていることを特徴とする請求項２３に記載の証明者デバイス(30)。   The calculating means (37) may or may not be included in the public key, and the exponent is the first random number r, by calculating the power of the first integer G modulo n. 24. The prover device (30) according to claim 23, characterized in that it is designed to generate a first element of the proof. 第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ、公式
G=ge modulo n
v=G-s modulo n
によって与えられることを特徴とする請求項３０に記載の証明者デバイス(30)。 The first public key integer G and the fourth public key integer v are respectively
G = g e modulo n
v = G -s modulo n
31. A prover device (30) according to claim 30, characterized by: 第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ、公式
G=ge modulo n
v=Gs modulo n
によって与えられることを特徴とする請求項３０に記載の証明者デバイス(30)。 The first public key integer G and the fourth public key integer v are respectively
G = g e modulo n
v = G s modulo n
31. A prover device (30) according to claim 30, characterized by: 第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ、公式
G=g-e modulo n
v=G-s modulo n
によって与えられることを特徴とする請求項３０に記載の証明者デバイス(30)。 The first public key integer G and the fourth public key integer v are respectively
G = g -e modulo n
v = G -s modulo n
31. A prover device (30) according to claim 30, characterized by: 計算手段は、公式
y=ar+bs
により、２つの共通数aおよびbの一次結合により秘密鍵イメージyを生成するように設計されていることを特徴とする請求項３０に記載の証明者デバイス(30)。 The calculation means is the official
y = ar + bs
31. The prover device (30) according to claim 30, characterized in that it is designed to generate a secret key image y by a linear combination of two common numbers a and b. 秘密鍵が複数の秘密数s1、s2、...を含む場合、
計算手段(37)は、プルーフxの第１の要素に関連付けられている同じ数の共通数c1、c2を生成するように設計され、
計算手段(37)は、公式
y=r+c1s1+c2s2+...
による一次結合により秘密鍵イメージを生成するように設計されていることを特徴とする請求項３０に記載の証明者デバイス(30)。 If the secret key contains multiple secret numbers s1, s2, ...
The calculating means (37) is designed to generate the same number of common numbers c1, c2 associated with the first element of proof x,
The calculation means (37) is the formula
y = r + c1s1 + c2s2 + ...
31. The prover device (30) according to claim 30, wherein the prover device (30) is designed to generate a secret key image by a linear combination according to. 公開鍵が、特に証明者デバイス内で素数が秘密にされる法nを含む場合、計算手段(37)は、中国の剰余定理と呼ばれる手法を使用して指数計算をするように設計されていることを特徴とする請求項２４に記載の証明者デバイス(30)。   The calculation means (37) is designed to perform exponential calculations using a technique called the Chinese remainder theorem, especially when the public key contains a modulus n where the prime number is kept secret in the prover device 25. A prover device (30) according to claim 24, characterized in that: 公開鍵が、プルーフxの第１の要素のk個のあらかじめ計算された値を含む場合、計算手段(37)は、繰り返し毎にプルーフの第１の要素の異なる値で各実行をk回繰り返すように設計されていることを特徴とする請求項２３に記載の証明者デバイス(30)。   If the public key contains k pre-computed values of the first element of proof x, the calculating means (37) repeats each execution k times with different values of the first element of proof for each iteration. 24. The prover device (30) according to claim 23, characterized in that it is designed as follows. プルーフの第１の要素は、前記公開鍵に含まれる場合も含まれない場合もあり、その指数が第１の乱数rである、第１の整数Gの、nを法とする累乗の関数fに等しいことを特徴とする請求項２３に記載のプルーフ証デバイス(30)。   The first element of the proof may or may not be included in the public key, and the exponent f of the first integer G, whose exponent is the first random number r, modulo n 24. A proof certificate device (30) according to claim 23, characterized in that 前記秘密鍵に関連付けられている公開鍵を使用して、証明者デバイスにより秘密にされている秘密鍵が与えられた証明者デバイスによりプルーフが発行されたことを検証するための検証者デバイス(31)であって、
プルーフの第１の要素とプルーフの第２の要素とを受け取るように設計されている通信手段(35)と、
前記公開鍵の第１の部分を、プルーフの第２の要素に適用し、また前記公開鍵の少なくとも第２の部分を、プルーフの第１の要素に関連して生成された複数の共通数のうち少なくとも１つに適用することにより、プルーフの第１の要素とプルーフの第２の要素との一致を検証するように設計されている計算手段(38)と
を備えることを特徴とする検証者デバイス(31)。 A verifier device (31 for verifying that a proof has been issued by a prover device given a secret key that has been kept secret by the prover device using a public key associated with the secret key. ) And
A communication means (35) designed to receive the first element of the proof and the second element of the proof;
Applying a first part of the public key to a second element of the proof and applying at least a second part of the public key to a plurality of common numbers generated in relation to the first element of the proof. A verifier comprising: a computing means (38) designed to verify a match between the first element of the proof and the second element of the proof by applying to at least one of them Device (31). 計算手段(38)は、プルーフの第１の要素が、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである第４の整数vの累乗との、nを法とする積と一致することを検証し、第３の整数および第４の整数は前記公開鍵に含まれるように設計されていることを特徴とする請求項３９に記載の検証者デバイス(31)。   The calculating means (38) is arranged such that the first element of the proof is a power of the second element of the proof Y whose exponent is the third integer e, and the fourth integer v whose index is the common number c. 40. The third integer and the fourth integer are designed to be included in the public key by verifying that they coincide with a product of n raised to the power modulo n. The verifier device (31) described. 計算手段(38)は、プルーフの第１の要素を受信した後に、セキュリティ間隔の範囲内の少なくとも１つの共通数を選択するように設計され、また通信手段(35)は、前記共通数を伝送するように設計されていることを特徴とする請求項３９または４０に記載の検証者デバイス(31)。   The calculation means (38) is designed to select at least one common number within the security interval after receiving the first element of the proof, and the communication means (35) transmits the common number. 41. Verifier device (31) according to claim 39 or 40, characterized in that it is designed to do so. 計算手段(38)は、プルーフxの第１の要素が、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積に等しいときに、一致が検証されたと宣言するように設計されていることを特徴とする請求項４０に記載の検証者デバイス(31)。   The calculation means (38) uses the first element of the proof x as the power of the second element of the proof Y whose exponent is the third integer e, and the public key whose exponent is the common number c. 41. The verifier device of claim 40, wherein the verifier device is designed to declare a match verified when it is equal to a product of the fourth integer v included and modulo n. (31). 計算手段(38)は、プルーフの第１の要素が、プルーフの第１の要素が添付されるデジタルメッセージM、および、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しいときに、一致が検証されたと宣言するように設計されていることを特徴とする請求項４０に記載の検証者デバイス(31)。   The calculation means 38 is a power of the second element of the proof Y whose first element of the proof is the digital message M to which the first element of the proof is attached and whose index is the third integer e. And the exponent is equal to the product of the product of the fourth integer v contained in the public key with the common number c and modulo n. 41. The verifier device (31) according to claim 40, characterized in that: 計算手段(38)は、共通数がデジタルメッセージM、および、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しい場合に、一致が検証されたと宣言するように設計されていることを特徴とする請求項４０に記載の検証者デバイス(31)。   The calculation means (38) uses the power of the second element of the proof Y whose common number is the digital message M and its exponent is the third integer e, and the public key whose exponent is the common number c. 41. Verification according to claim 40, designed to declare a match verified if it is equal to a function of a product modulo n with a power of a fourth integer v contained Device (31). 等式は、公式
x=Yevc modulo n
によって検証されることを特徴とする請求項４２に記載の検証者デバイス(31)。 The equation is official
x = Y e v c modulo n
43. Verifier device (31) according to claim 42, characterized in that it is verified by: 等式は、公式
Ye=vcx modulo n
によって検証されることを特徴とする請求項４２に記載の検証者デバイス(31)。 The equation is official
Y e = v c x modulo n
43. Verifier device (31) according to claim 42, characterized in that it is verified by: 等式は、公式
Yex=vc modulo n
によって検証されることを特徴とする請求項４２に記載の検証者デバイス(31)。 The equation is official
Y e x = v c modulo n
43. Verifier device (31) according to claim 42, characterized in that it is verified by: 一致は、等式
Yevb=xa modulo n
によって検証されることを特徴とする請求項４２に記載の検証者デバイス(31)。 Match is equality
Y e v b = x a modulo n
43. Verifier device (31) according to claim 42, characterized in that it is verified by: 秘密鍵が複数の秘密数s1、s2、...を含む場合、
計算手段(38)は、プルーフxの第１の要素に対する、同じ数の共通数c1、c2、...を選択するように設計され、
計算手段(38)は、等式
Yev1c2V2c2...=x modulo n
を使って、同じ数の第４の公開鍵整数v1、v2、...により一致を検証するように設計されていることを特徴とする請求項４１に記載の検証者デバイス(31)。 If the secret key contains multiple secret numbers s1, s2, ...
The calculation means (38) is designed to select the same number of common numbers c1, c2,... For the first element of proof x,
The calculation means (38) is the equation
Y e v1 c2 V2 c2 ... = x modulo n
42. Verifier device (31) according to claim 41, designed to verify a match with the same number of fourth public key integers v1, v2,. 計算手段(38)は、メモリ内に、公開鍵の一部としてみなされるプルーフxの第１の要素の少なくとも１つのあらかじめ計算された値を備えることを特徴とする請求項３９に記載の検証者デバイス(31)。   40. Verifier according to claim 39, wherein the calculating means (38) comprises in memory at least one pre-calculated value of the first element of the proof x considered as part of the public key Device (31). 計算手段(38)は、メモリ内に、プルーフxの第１の要素のk個のあらかじめ計算された値を備え、通信手段は、プルーフのk個の第２の要素を受信するように設計されており、計算手段(38)は、受信されたプルーフのそれぞれの第２の要素と、プルーフの第１の要素の異なる値との一致を検証するように設計されていることを特徴とする請求項５０に記載の検証者デバイス(31)。   The calculating means (38) comprises in memory the k pre-calculated values of the first element of the proof x, and the communication means is designed to receive the k second elements of the proof. And the calculating means (38) is designed to verify a match between each second element of the received proof and a different value of the first element of the proof. 50. The verifier device (31) according to item 50. プルーフの第１の要素が、前記公開鍵に含まれる場合も含まれない場合もある、その指数が第１の乱数rである、第１の整数Gの、nを法とする累乗の関数fに等しい場合に、計算手段(38)は、この関数の結果に基づいて検証を実行するように設計されていることを特徴とする請求項４０に記載の検証者デバイス(31)。   The first element of the proof may or may not be included in the public key, the exponent f of the first integer G whose exponent is the first random number r and modulo n 41. Verifier device (31) according to claim 40, characterized in that the computing means (38) is designed to perform verification based on the result of this function when equal to. 証明者デバイスにより秘密にされている秘密鍵に基づきプルーフを生成する目的のため証明者デバイスの下流に導入される媒介デバイス(32)であって、前記プルーフは、前記秘密鍵に関連付けられている公開鍵により検証可能であり、前記秘密鍵のイメージのオープンデジタル処理によりプルーフの少なくとも１つの要素を生成するための計算手段(39)を含み、前記秘密鍵イメージでは前記秘密鍵を元に戻すことができないことを特徴とする媒介デバイス(32)。   An intermediary device (32) introduced downstream of the prover device for the purpose of generating a proof based on a secret key kept secret by the prover device, wherein the proof is associated with the secret key Computation means (39) that is verifiable by a public key and generates at least one element of a proof by open digital processing of the image of the secret key, wherein the secret key is restored in the secret key image An intermediary device (32) characterized in that it cannot. 前記秘密鍵イメージyを受信するように設計されている通信手段(36)を備えることを特徴とする請求項５３に記載の媒介デバイス(32)。   54. The intermediary device (32) according to claim 53, comprising communication means (36) designed to receive the secret key image y. 計算手段(39)は、その指数が秘密鍵イメージyである前記公開鍵に含まれる第２の整数gの、nを法とする累乗を計算することによりプルーフYの第２の要素を生成するように設計されていることを特徴とする請求項５４に記載の媒介デバイス(32)。   The calculating means (39) generates the second element of the proof Y by calculating the power of the second integer g included in the public key whose exponent is the secret key image y, modulo n. 55. An intermediary device (32) according to claim 54, characterized in that it is designed as follows. 秘密鍵の第１の部分イメージy'、第１のコンポーネントY'、およびプルーフの第２の要素の第２のコンポーネントg'を受信するように設計されている通信手段(36)を備え、計算手段(39)は、第２の部分イメージy"を指数とする第２のコンポーネントg'の累乗を第１のコンポーネントY'に掛けることにより、プルーフYの第２の要素を生成するように設計されていることを特徴とする請求項５３に記載の媒介デバイス(32)。   Comprising a communication means (36) designed to receive a first partial image y 'of a secret key, a first component Y', and a second component g 'of a second element of the proof, comprising: The means (39) is designed to generate the second element of the proof Y by multiplying the first component Y ′ by the power of the second component g ′ indexed by the second partial image y ″. 54. An intermediary device (32) according to claim 53, characterized in that 通信手段(36)は、プルーフYの第２の要素を検証者デバイスに伝送するように設計されていることを特徴とする請求項５５または５６のいずれか一項に記載の媒介デバイス(32)。   57. The intermediary device (32) according to any one of claims 55 or 56, characterized in that the communication means (36) are designed to transmit the second element of the proof Y to the verifier device. .
JP2003555732A 2001-12-21 2002-12-16 Cryptography to distribute the load across multiple entities and their devices Pending JP2005513564A (en)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR0116789A FR2834153B1 (en) 2001-12-21 2001-12-21 CRYPTOGRAPHIC PROCESS ALLOWING TO DISTRIBUTE THE LOAD AMONG SEVERAL ENTITIES AND DEVICES FOR IMPLEMENTING THIS PROCESS
PCT/FR2002/004366 WO2003055134A1 (en) 2001-12-21 2002-12-16 Cryptographic method for distributing load among several entities and devices therefor

Publications (2)

Publication Number Publication Date
JP2005513564A JP2005513564A (en) 2005-05-12
JP2005513564A5 true JP2005513564A5 (en) 2005-12-22

Family

ID=8870936

Family Applications (1)

Application Number Title Priority Date Filing Date
JP2003555732A Pending JP2005513564A (en) 2001-12-21 2002-12-16 Cryptography to distribute the load across multiple entities and their devices

Country Status (8)

Country Link
US (1) US7382875B2 (en)
EP (1) EP1456998A1 (en)
JP (1) JP2005513564A (en)
KR (1) KR100971038B1 (en)
CN (1) CN1618200B (en)
AU (1) AU2002364321A1 (en)
FR (1) FR2834153B1 (en)
WO (1) WO2003055134A1 (en)

Families Citing this family (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7363492B2 (en) * 2005-02-25 2008-04-22 Motorola, Inc. Method for zero-knowledge authentication of a prover by a verifier providing a user-selectable confidence level and associated application devices
JP4988448B2 (en) * 2007-06-25 2012-08-01 株式会社日立製作所 Batch verification apparatus, program, and batch verification method
FR2923305B1 (en) * 2007-11-02 2011-04-29 Inside Contactless METHOD AND DEVICES FOR PROTECTING A MICROCIRCUIT AGAINST ATTACKS TO DISCOVER SECRET DATA
FR2925245B1 (en) * 2007-12-12 2010-06-11 Sagem Securite CONTROL OF AN ENTITY TO BE CONTROLLED BY A CONTROL ENTITY
FR2981531A1 (en) * 2011-10-14 2013-04-19 France Telecom METHOD OF TRANSFERRING THE CONTROL OF A SECURITY MODULE FROM A FIRST ENTITY TO A SECOND ENTITY
FR2992509B1 (en) * 2012-06-21 2017-05-26 Commissariat Energie Atomique DEVICE AND METHOD FOR GENERATING A SESSION KEY
EP3697019A1 (en) * 2019-02-12 2020-08-19 Siemens Aktiengesellschaft Method for providing proof of origin for a digital key pair
CN110517147B (en) * 2019-08-30 2023-04-14 深圳市迅雷网络技术有限公司 Transaction data processing method, device, system, and computer-readable storage medium

Family Cites Families (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6226383B1 (en) * 1996-04-17 2001-05-01 Integrity Sciences, Inc. Cryptographic methods for remote authentication
US6092202A (en) * 1998-05-22 2000-07-18 N*Able Technologies, Inc. Method and system for secure transactions in a computer system
US6779111B1 (en) * 1999-05-10 2004-08-17 Telefonaktiebolaget Lm Ericsson (Publ) Indirect public-key encryption
JP2001209308A (en) * 2000-01-24 2001-08-03 Advanced Mobile Telecommunications Security Technology Research Lab Co Ltd Bulk signature method
US7139917B2 (en) * 2000-06-05 2006-11-21 Phoenix Technologies Ltd. Systems, methods and software for remote password authentication using multiple servers

Similar Documents

Publication Publication Date Title
US11895231B2 (en) Adaptive attack resistant distributed symmetric encryption
EP2359523B1 (en) Acceleration of key agreement protocols
CN110545279A (en) block chain transaction method, device and system with privacy and supervision functions
Wang et al. Generalization of threshold signature and authenticated encryption for group communications
JPS5950068B2 (en) public key cryptographic device
US20150288527A1 (en) Verifiable Implicit Certificates
WO1995030292A1 (en) Private signature and proof systems
US12489620B2 (en) Threshold secret share generation for distributed symmetric cryptography
JP2012019559A (en) Custom static diffie-hellman groups
WO2013021360A1 (en) Encryption and decryption method
JP2007519044A (en) Zero knowledge proof encryption method and apparatus
JP2005513564A5 (en)
Akleylek et al. A novel 3-pass identification scheme and signature scheme based on multivariate quadratic polynomials
Alam et al. A comparison between RSA and ElGamal based untraceable blind signature schemes
Malina et al. Trade-off between signature aggregation and batch verification
JP2005513564A (en) Cryptography to distribute the load across multiple entities and their devices
Dong et al. Two extensions of the ring signature scheme of Rivest–Shamir–Taumann
Hafsa et al. Secure transmission of medical images using improved hybrid cryptosystem: authentication, confidentiality and integrity
US20060251248A1 (en) Public key cryptographic methods and systems with preprocessing
US7480380B2 (en) Method for efficient generation of modulo inverse for public key cryptosystems
Awad et al. A NEW APPROACH COMBINING RSA AND ELGAMAL ALGORITHMS: ADVANCEMENTS IN ENCRYPTION AND DIGITAL SIGNATURES USING GAUSSIAN INTEGERS.
CN114520728B (en) Distributed anonymous marking method and system
Ezziri et al. A blind signature based on the DLP and RSA cryptosystem
US12494922B2 (en) Threshold signature scheme
CN110401533A (en) A kind of private key encryption method and device