(57)【要約】本発明は、第２のエンティティ(B)が公開鍵を使って第１のエンティティ(A)により提供されるプルーフを検証するための、第１エンティティ(A)が第１のエンティティ(A)によって秘密にされている秘密鍵に含まれる第１の整数sよりも、かなり大きい第１の乱数rを生成する暗号法に関するものである。第１のエンティティ(A)は、指数を第１の乱数rとする前記公開鍵に含まれるあるいは含まれない第１の整数Gの、nを法とする累乗計算から得られるプルーフの第１の要素を生成する。第１のエンティティ(A)は、第１の乱数rと少なくとも第１の秘密鍵整数sの一次結合により前記秘密鍵のイメージyを生成する。第２のエンティティ(B)は、プルーフの第１の要素がプルーフYの第２の要素の、指数が第３の整数eである累乗と前記公開鍵に含まれる第４の整数vの、指数が前記共通数cである累乗の、nを法とする積に一致するかどうかを検証する。
2005513564.tif 000002
【特許請求の範囲】
【請求項１】
第１のエンティティ(A)は、第１のエンティティ(A)により秘密にされている秘密鍵を使って、前記秘密鍵に関連付けられている公開鍵を使って第２のエンティティ(B)により検証可能なプルーフを生成する暗号法であって、プルーフの少なくとも１つの要素が前記秘密鍵を復元することができないデータ項目のオープンデジタル処理により少なくとも一部生成されるステップ(5,15)を含むことを特徴とする暗号法。
【請求項２】
暗号法であって、
−  第１のエンティティ(A)が、第１のエンティティ(A)により秘密にされている第１の乱数を使って、プルーフの第１の要素を生成する第１のステップ(1、9、20)と、
−  １つまたは複数の共通数と呼ばれるものがプルーフの第１の要素と関連して生成され、したがって第１のエンティティ(A)および第２のエンティティ(B)が前記１つまたは複数の共通数を認識していなければならない第２のステップ(11,23)と、
−  第１の乱数を伴う少なくとも第１の秘密鍵整数と少なくとも１つの前記共通数とを組み合わせることにより、第１のエンティティ(A)は前記秘密鍵のイメージを生成する第３のステップ(13、24)と、
−  前記公開鍵の第１の部分をプルーフの第２の要素に適用し、かつ前記公開鍵の少なくとも第２の部分を前記共通数の少なくとも１つに適用することによって、第２のエンティティ(B)がプルーフの第１の要素とプルーフの第２の要素との一致を検証できるようにするために、プルーフの第２の要素が、前記秘密鍵のイメージに対して、エンティティ(C)により実行可能なオープンデジタル処理オペレーションを適用することにより生成される第４のステップ(5、15)と
を含むことを特徴とする請求項１に記載の暗号法。
【請求項３】
暗号法であって、
−  第１のステップ(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を法とする累乗となるような整数であることを特徴とする請求項２に記載の暗号法。
【請求項４】
第４のステップにおいて、プルーフYの第２の要素は、第２のエンティティ(B)に送信されることを特徴とし、また、プルーフの第１の要素が、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積に一致することを、第２のエンティティ(B)が検証する第５のステップ(8、17、22)を含むことを特徴とする請求項３に記載の暗号法。
【請求項５】
第４のステップ(5、15)は、第１のエンティティ(A)以外の、第１のエンティティ(A)から秘密鍵イメージyを受信するエンティティ(C)により実行されることを特徴とする請求項２から４までのいずれか一項に記載の暗号法。
【請求項６】
第４のステップ(15)は、第１のエンティティ(A)により実行されることを特徴とする請求項２から４のいずれか一項に記載の暗号法。
【請求項７】
第４のステップは、
−  第１のエンティティ(A)は、イメージyを、イメージyを表すデータワードのu個の下位ビットにより表される第１の部分イメージy'と、前記データワードの残りの上位ビットにより表される第２の部分イメージy"とに分解し、また第１のエンティティ(A)は、第１のコンポーネントY'とプルーフの第２の要素の第２のコンポーネントg'を生成し、前記コンポーネントでは以下が成り立ち、
【数１】
2005513564.tif 000006
また第１のエンティティ(A)は、第１のコンポーネントY'、第２のコンポーネントg'、および第２の部分イメージy"を中間エンティティ(C)に送信する、第１のサブステップ(18)と、
−  中間エンティティ(C)は、第２の部分イメージy"を指数とする第２のコンポーネントg'の累乗を第１のコンポーネントY'に掛けることによりプルーフYの第２の要素を生成し、中間エンティティ(C)は、プルーフYの第２の要素を第１のエンティティ(B)に送信する第２のサブステップ(25)と
を含むことを特徴とする請求項２から４のいずれか一項に記載の暗号法。
【請求項８】
第２のステップ(11)は、第１のエンティティ(A)から受信したプルーフの第１の要素について、セキュリティ間隔の範囲内の少なくとも１つの共通数を選択し、前記共通数を第１のエンティティ(A)に送信する第２のエンティティ(B)により実行されることを特徴とする請求項２から７のいずれか一項に記載の暗号法。
【請求項９】
第２のステップ(23)は、プルーフの第１の要素と、前記共通数が添付されるデジタルメッセージMとに基づいて、少なくとも１つの共通数を生成する第１のエンティティ(A)により実行されることを特徴とする請求項２から７のいずれか一項に記載の暗号法。
【請求項１０】
第５のステップ(17)において、プルーフxの第１の要素が、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積に等しいときに、一致が検証されることを特徴とする請求項４に記載の暗号法。
【請求項１１】
第５のステップ(22)において、プルーフの第１の要素が、プルーフの第１の要素が添付されるデジタルメッセージMおよび指数が第３の整数eであるプルーフYの第２の要素の累乗と指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗のnを法とする積の関数に等しいときに一致が検証されることを特徴とする請求項４に記載の暗号法。
【請求項１２】
第５のステップ(8)において、共通数が、デジタルメッセージMと、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しい場合に、一致が検証されることを特徴とする請求項４に記載の暗号法。
【請求項１３】
プルーフの第１の要素は、前記公開鍵に含まれる場合もあれば含まれない場合もあり、その指数が第１の乱数rである第１の整数Gの、nを法とする累乗に等しいことを特徴とする請求項３に記載の暗号法。
【請求項１４】
第１の整数Gおよび第４の公開鍵整数vは、公式
G=ge modulo n
v=G-s modulo n
で与えられ、この等式は、公式
x=Yevc modulo n
によって検証されることを特徴とする請求項１３に記載の暗号法。
【請求項１５】
第４の公開鍵整数vは、公式
G=ge modulo n
v=Gs(modulo n)
で与えられ、この等式は、公式
Ye=vcx modulo n
によって検証されることを特徴とする請求項１３に記載の暗号法。
【請求項１６】
第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ、公式
G=g-e modulo n
v=G-s modulo n
で与えられ、この等式は、公式Yex=ve modulo nによって検証されることを特徴とする請求項１３に記載の暗号法。
【請求項１７】
暗号法であって、
−  第２のステップにおいて、２つの共通数aおよびbはプルーフxの第１の要素に関して生成され、
−  第３のステップにおいて、一次結合は、公式
y=ar+bs
によって与えられ、
−  第５のステップにおいて、一致は、等式
Yevb=xa modulo n
によって検証されることを特徴とする請求項１３に記載の暗号法。
【請求項１８】
秘密鍵が複数の秘密数s1、s2、...を含む場合、
−  第２のステップにおいて、同じ数の共通数c1、c2、...が、プルーフxの第１の要素に関して生成され、
−  第３のステップにおいて、一次結合は、公式
y=r+c1s1+c2s2+...
によって与えられ、
−  第５のステップにおいて、一致は、同じ数の第４の公開鍵整数v1、v2、...により、等式
Yev1c1v2c2...=x modulo n
を使って検証されることを特徴とする請求項１３に記載の暗号法。
【請求項１９】
公開鍵が特に、第１のエンティティ(A)からその素数が知られている法nを含む場合、第１のステップは中国の剰余定理と呼ばれる手法を使用することにより高速化されることを特徴とする請求項３に記載の暗号法。
【請求項２０】
公開鍵は、第２のステップでこの方法を開始するために、プルーフxの第１の要素のあらかじめ計算された少なくとも１つの値を含むことを特徴とする請求項２に記載の暗号法。
【請求項２１】
公開鍵は、プルーフxの第１の要素のk個のあらかじめ計算された値を含み、第２のステップから第５のステップまでの実行を、繰り返し毎にプルーフの第１の要素の異なる値を使ってk回繰り返すことを特徴とする請求項２０に記載の暗号法。
【請求項２２】
プルーフの第１の要素は、前記公開鍵に含まれる場合も含まれない場合もあり、その指数は第１の乱数rである、第１の整数Gの、nを法とする累乗の関数fに等しく、第５のステップの検証をこの関数の結果に基づいて行うことを特徴とする請求項２に記載の暗号法。
【請求項２３】
プルーフを生成するための、秘密にされ侵入者に対する保護処置が講じられている秘密鍵を与えられた証明者デバイスであって、前記秘密鍵に関連付けられている公開鍵を使用してその検証を行うことで、デバイス(30)が前記プルーフの発信元であることを保証することが可能であり、
−  デバイス(30)内に秘密にされている第１の乱数に基づいて、プルーフの第１の要素を生成し、第１の乱数を持った少なくとも第１の秘密鍵整数と、プルーフの第１の要素に関連付けられている複数の共通数のうち少なくとも１つとを組み合わせることにより、前記秘密鍵のイメージを生成し、かつ、
前記公開鍵の第１の部分をプルーフの第２の要素に適用し、前記公開鍵の少なくとも第２の部分を前記共通数の少なくとも１つに適用することにより、オープンデジタル処理オペレーションを、プルーフの第１の要素とプルーフの第２の要素との一致を検証することを可能にする前記秘密鍵イメージに適用することによって、プルーフの第２の要素を生成することが可能であるように設計されている計算手段(37)と、
−  プルーフの少なくとも前記第１の要素を伝送するように設計されている通信手段(34)を備えることを特徴とする証明者デバイス。
【請求項２４】
証明者デバイス(30)であって、
−  一方で、計算手段(37)は、秘密にされている秘密鍵に含まれる第１の整数sよりもかなり大きい第１の乱数rを生成し、第１の乱数rを指数として前記公開鍵に含まれている場合もいない場合もある第１の整数Gの、nを法とする累乗を計算することによりプルーフの第１の要素を生成するように設計され、
−  他方で、計算手段(37)は、第１の乱数rと少なくとも第１の秘密鍵整数sの一次結合により前記秘密鍵のイメージyを生成し、前記一次結合の少なくとも１つの乗法的係数は前記共通数または前記共通数のうちの１つであるように設計されることを特徴とする請求項２３に記載の証明者デバイス。
【請求項２５】
通信手段(34)は、プルーフの第１の要素を伝送した後に前記共通数を受信するように設計されていることを特徴とする請求項２３または２４のいずれか一項に記載の証明者デバイス(30)。
【請求項２６】
通信手段(34)は、秘密鍵イメージを伝送するように設計されていることを特徴とする請求項２３から２５のいずれか一項に記載の証明者デバイス(30)。
【請求項２７】
通信手段(37)は、プルーフの第２の要素を生成するように設計されていることを特徴とする請求項２３から２５のいずれか一項に記載の証明者デバイス(30)。
【請求項２８】
証明者デバイス(30)であって、
計算手段(37)は、イメージyを、イメージyを表すデータワードの下位ビットにより表される第１の部分イメージy'と、データワードの残りの上位ビットにより表される第２の部分イメージy"とに分解し、また第１のコンポーネントY'とプルーフの第２の要素の第２のコンポーネントg'を生成し、前記コンポーネントでは以下が成り立ち、
【数２】
2005513564.tif 000007
ただし、gは、第１の公開鍵整数Gが前記公開鍵に含まれる第３の整数eを指数とする第２の整数gのnを法とする累乗となるような第２の整数であり、
通信手段(34)は、第１のコンポーネントY'、第２のコンポーネントg'、および第２の部分イメージy"を伝送するように設計されることを特徴とする請求項２４から２５のいずれか一項に記載の証明者デバイス(30)。
【請求項２９】
計算手段(37)は、プルーフの第１の要素と前記共通数が添付されるデジタルメッセージMとに基づいて、少なくとも１つの共通数を生成するように設計されていることを特徴とする請求項２３および２４のいずれか一項に記載の証明者デバイス(30)。
【請求項３０】
計算手段(37)は、前記公開鍵に含まれる場合も含まれない場合もあり、指数は第１の乱数rである、第１の整数Gの、nを法とする累乗を計算することによりプルーフの第１の要素を生成するように設計されていることを特徴とする請求項２３に記載の証明者デバイス(30)。
【請求項３１】
第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ、公式
G=ge modulo n
v=G-s modulo n
によって与えられることを特徴とする請求項３０に記載の証明者デバイス(30)。
【請求項３２】
第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ、公式
G=ge modulo n
v=Gs modulo n
によって与えられることを特徴とする請求項３０に記載の証明者デバイス(30)。
【請求項３３】
第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ、公式
G=g-e modulo n
v=G-s modulo n
によって与えられることを特徴とする請求項３０に記載の証明者デバイス(30)。
【請求項３４】
計算手段は、公式
y=ar+bs
により、２つの共通数aおよびbの一次結合により秘密鍵イメージyを生成するように設計されていることを特徴とする請求項３０に記載の証明者デバイス(30)。
【請求項３５】
秘密鍵が複数の秘密数s1、s2、...を含む場合、
計算手段(37)は、プルーフxの第１の要素に関連付けられている同じ数の共通数c1、c2を生成するように設計され、
計算手段(37)は、公式
y=r+c1s1+c2s2+...
による一次結合により秘密鍵イメージを生成するように設計されていることを特徴とする請求項３０に記載の証明者デバイス(30)。
【請求項３６】
公開鍵が、特に証明者デバイス内で素数が秘密にされる法nを含む場合、計算手段(37)は、中国の剰余定理と呼ばれる手法を使用して指数計算をするように設計されていることを特徴とする請求項２４に記載の証明者デバイス(30)。
【請求項３７】
公開鍵が、プルーフxの第１の要素のk個のあらかじめ計算された値を含む場合、計算手段(37)は、繰り返し毎にプルーフの第１の要素の異なる値で各実行をk回繰り返すように設計されていることを特徴とする請求項２３に記載の証明者デバイス(30)。
【請求項３８】
プルーフの第１の要素は、前記公開鍵に含まれる場合も含まれない場合もあり、その指数が第１の乱数rである、第１の整数Gの、nを法とする累乗の関数fに等しいことを特徴とする請求項２３に記載のプルーフ証デバイス(30)。
【請求項３９】
前記秘密鍵に関連付けられている公開鍵を使用して、証明者デバイスにより秘密にされている秘密鍵が与えられた証明者デバイスによりプルーフが発行されたことを検証するための検証者デバイス(31)であって、
プルーフの第１の要素とプルーフの第２の要素とを受け取るように設計されている通信手段(35)と、
前記公開鍵の第１の部分を、プルーフの第２の要素に適用し、また前記公開鍵の少なくとも第２の部分を、プルーフの第１の要素に関連して生成された複数の共通数のうち少なくとも１つに適用することにより、プルーフの第１の要素とプルーフの第２の要素との一致を検証するように設計されている計算手段(38)と
を備えることを特徴とする検証者デバイス(31)。
【請求項４０】
計算手段(38)は、プルーフの第１の要素が、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである第４の整数vの累乗との、nを法とする積と一致することを検証し、第３の整数および第４の整数は前記公開鍵に含まれるように設計されていることを特徴とする請求項３９に記載の検証者デバイス(31)。
【請求項４１】
計算手段(38)は、プルーフの第１の要素を受信した後に、セキュリティ間隔の範囲内の少なくとも１つの共通数を選択するように設計され、また通信手段(35)は、前記共通数を伝送するように設計されていることを特徴とする請求項３９または４０に記載の検証者デバイス(31)。
【請求項４２】
計算手段(38)は、プルーフxの第１の要素が、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積に等しいときに、一致が検証されたと宣言するように設計されていることを特徴とする請求項４０に記載の検証者デバイス(31)。
【請求項４３】
計算手段(38)は、プルーフの第１の要素が、プルーフの第１の要素が添付されるデジタルメッセージM、および、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しいときに、一致が検証されたと宣言するように設計されていることを特徴とする請求項４０に記載の検証者デバイス(31)。
【請求項４４】
計算手段(38)は、共通数がデジタルメッセージM、および、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しい場合に、一致が検証されたと宣言するように設計されていることを特徴とする請求項４０に記載の検証者デバイス(31)。
【請求項４５】
等式は、公式
x=Yevc modulo n
によって検証されることを特徴とする請求項４２に記載の検証者デバイス(31)。
【請求項４６】
等式は、公式
Ye=vcx modulo n
によって検証されることを特徴とする請求項４２に記載の検証者デバイス(31)。
【請求項４７】
等式は、公式
Yex=vc modulo n
によって検証されることを特徴とする請求項４２に記載の検証者デバイス(31)。
【請求項４８】
一致は、等式
Yevb=xa modulo n
によって検証されることを特徴とする請求項４２に記載の検証者デバイス(31)。
【請求項４９】
秘密鍵が複数の秘密数s1、s2、...を含む場合、
計算手段(38)は、プルーフxの第１の要素に対する、同じ数の共通数c1、c2、...を選択するように設計され、
計算手段(38)は、等式
Yev1c2V2c2...=x modulo n
を使って、同じ数の第４の公開鍵整数v1、v2、...により一致を検証するように設計されていることを特徴とする請求項４１に記載の検証者デバイス(31)。
【請求項５０】
計算手段(38)は、メモリ内に、公開鍵の一部としてみなされるプルーフxの第１の要素の少なくとも１つのあらかじめ計算された値を備えることを特徴とする請求項３９に記載の検証者デバイス(31)。
【請求項５１】
計算手段(38)は、メモリ内に、プルーフxの第１の要素のk個のあらかじめ計算された値を備え、通信手段は、プルーフのk個の第２の要素を受信するように設計されており、計算手段(38)は、受信されたプルーフのそれぞれの第２の要素と、プルーフの第１の要素の異なる値との一致を検証するように設計されていることを特徴とする請求項５０に記載の検証者デバイス(31)。
【請求項５２】
プルーフの第１の要素が、前記公開鍵に含まれる場合も含まれない場合もある、その指数が第１の乱数rである、第１の整数Gの、nを法とする累乗の関数fに等しい場合に、計算手段(38)は、この関数の結果に基づいて検証を実行するように設計されていることを特徴とする請求項４０に記載の検証者デバイス(31)。
【請求項５３】
証明者デバイスにより秘密にされている秘密鍵に基づきプルーフを生成する目的のため証明者デバイスの下流に導入される媒介デバイス(32)であって、前記プルーフは、前記秘密鍵に関連付けられている公開鍵により検証可能であり、前記秘密鍵のイメージのオープンデジタル処理によりプルーフの少なくとも１つの要素を生成するための計算手段(39)を含み、前記秘密鍵イメージでは前記秘密鍵を元に戻すことができないことを特徴とする媒介デバイス(32)。
【請求項５４】
前記秘密鍵イメージyを受信するように設計されている通信手段(36)を備えることを特徴とする請求項５３に記載の媒介デバイス(32)。
【請求項５５】
計算手段(39)は、その指数が秘密鍵イメージyである前記公開鍵に含まれる第２の整数gの、nを法とする累乗を計算することによりプルーフYの第２の要素を生成するように設計されていることを特徴とする請求項５４に記載の媒介デバイス(32)。
【請求項５６】
秘密鍵の第１の部分イメージy'、第１のコンポーネントY'、およびプルーフの第２の要素の第２のコンポーネントg'を受信するように設計されている通信手段(36)を備え、計算手段(39)は、第２の部分イメージy"を指数とする第２のコンポーネントg'の累乗を第１のコンポーネントY'に掛けることにより、プルーフYの第２の要素を生成するように設計されていることを特徴とする請求項５３に記載の媒介デバイス(32)。
【請求項５７】
通信手段(36)は、プルーフYの第２の要素を検証者デバイスに伝送するように設計されていることを特徴とする請求項５５または５６のいずれか一項に記載の媒介デバイス(32)。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号の技術分野に関するものであり、より正確には、公開鍵暗号法と呼ばれるものに関する。この種の暗号法では、ユーザは所定の用途に関して一対の鍵を所有する。前記一対の鍵は、このユーザが公表しないで隠しておく秘密鍵と、このユーザが他のユーザに伝達することができる関連する公開鍵とからなる。例えば、一対の鍵が機密にすることのみを目的とする場合、公開鍵を使用して、データを暗号化し、秘密の鍵を使用してそれを暗号解読する、つまりこのデータを平文で再確立する。
【背景技術】
【０００２】
公開鍵暗号法は、秘密鍵暗号法とは異なり、これまで非常に広く使用されてきており、セキュリティ保護された通信を確立するために相手と同じ秘密を共有する必要はない。しかし、セキュリティに関するこのような利点はパフォーマンスに関する欠点と裏腹であるが、それは「公開鍵スキーム」とも呼ばれる公開鍵暗号法は、「秘密鍵スキーム」とも呼ばれる秘密鍵暗号法と比べて数百倍から数千倍程度遅いことが多いためである。したがって、接触型であろうと非接触型であろうと標準マイクロプロセッサカードなど資源が制限されている環境において使用できるような、実行速度の速い公開鍵暗号法を見つけることは大変な難題である。
【０００３】
現時点で存在するほとんどの公開鍵スキームは、算術演算(つまり「数輪」)の分野の数学的問題の難しさに依存している。したがって、RSA(Rivest,Shamir,Adleman)数値署名および暗号化スキームのセキュリティは、因数分解の難しさ、つまり、比較可能なサイズの２つまたはそれ以上の素数を掛け合わせて秘密のうちに得られた非常に大きな整数(500ビットを超えるもの)が与えられた場合に、現時点では元の素数を求める実効的方法が存在しないということに基づいている。
【０００４】
ElGamalデジタル署名または暗号化スキームなどの他の公開鍵スキームは、そのセキュリティに関して、「離散対数問題」と呼ばれる問題の難しさに依存している。この問題は、その最も一般的なケースにおいて、Eを演算(つまり、２つの元aとbが与えられた場合に、「a.b」または「ab」と表され、「aとbの積」と呼ばれる元を関連付ける関数)の与えられている集合とし、gをEの１つの元とし、rを大きな整数とし、yをy=gr(つまり、gがr回出現する積g・g・...・g)により定義された整数とすると、gとyから元のrを求めることは可能でない、というように表現できる。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、より具体的には、「識別」とも呼ばれるエンティティ認証の技術分野に関するものであり、また公開鍵暗号手法を使ったメッセージの認証およびデジタル署名の認証の技術分野に関するものである。このような方法では、「証明者（prover）」と呼ばれる認証されたエンティティは、秘密鍵および関連する公開鍵を所有する。証明者は、その秘密鍵を使用して認証値を出力する。「検証者」と呼ばれる認証側エンティティでは、認証値を検証するのに証明者の公開鍵のみがあればよい。
【０００６】
本発明は、より具体的には、さらに「ゼロ知識開示」と呼ばれる認証方法に関するものである。これは、認証は、実証済みの方法では、何回使用したとしても、認証済みエンティティの秘密鍵に関して何ら明らかにしないプロトコルを使用して実行されることを意味している。この種のスキームからは、標準の手法を使用して、メッセージおよびこのメッセージのデジタル署名を認証するスキームを推論する方法が知られている。
【０００７】
本発明は、さらに具体的には、セキュリティが整数の因数分解の問題および離散対数問題の難しさに両方とも基づく方法に関するものである。
【０００８】
本発明は、公開鍵暗号法を使用してその要素および/または取引のセキュリティを保護する多くのシステムにおいて、またより具体的には、さまざまなパーティによって実行される計算の数が、計算を高速化するため「暗号プロセッサ」と呼ばれることの多い暗号計算専用のコプロセッサが利用可能になっていないという理由から、あるいは例えば中央サーバの場合に多数の計算を同時に実行することができるという理由から、または他の何らかの理由により、少なくともそれらのうちの１つについて、クリティカルなパラメータであるシステムにおいて適用することが可能である。
【０００９】
通常のアプリケーションは、銀行カードまたは電子サイフによる、電子決済である。近接通信決済の場合、決済端末は公開の場所にあり、公開鍵暗号法を使用し、マスター鍵を格納しないよう指示される。そのようなシステムの総コストを減らすため、カードを標準マイクロプロセッサカード、つまり、暗号プロセッサを搭載しないカードとするか、または端末自体に内蔵されるセキュリティ保護マイクロプロセッサを標準タイプとするか、またはそれら両方とすることが望ましいと思われる。場合によっては、また採用されている暗号方法によっては、現時点で知られている従来技術はこれらの目標の一方または他方を達成しているが、両方を同時に達成しながら、システムの制約に適合することは容易でない。このような制約の例として、1秒以内に、さらには非接触型取引の場合には150ミリ秒以内に、さらには高速道路料金所の場合には数ミリ秒以内に決済する事例がある。
【００１０】
知られているすべての暗号方式の制限の１つに、パーティそれぞれが実行しなければならない計算の回数が方法自体により固定されており、変更できないという問題がある。特に、そのようなものまたはそのような環境に適合するように、証明者と必ずしも機密でない第三者との間の計算の分散を変更することは可能でない。このため、制約が異なるさまざまな環境において同じ方法を利用することができなくなっている。
【課題を解決するための手段】
【００１１】
本発明の目的は、かなりの量の計算を、関わっている複数のエンティティのうち少なくとも２つの間に分散し、しかもこの分散で前記方法により実現されるセキュリティのレベルが変わらないようにすることが可能な公開鍵暗号法を指定することである。公開鍵デジタル署名または認証方法の場合、本発明は、実行される計算の回数を減らすことにより証明者の負担を軽減するのに特に役立つ。本発明では、計算の一部を他のエンティティに任せることが可能であり、しかも、この他のエンティティを機密にする必要がない。より一般的には、本発明では、計算の全部または一部を注目する複数のエンティティの間に何らかの方法で分散させ、所定のアプリケーションに関連する制約条件を満たすようにできる。
【００１２】
第１のエンティティが、第１のエンティティにより秘密にされている秘密鍵を使って、前記秘密鍵に関連付けられている公開鍵を使って第２のエンティティにより検証可能なプルーフ（proof）を生成する暗号法を考察すると、本発明による方法は、プルーフの少なくとも１つの要素が元の前記秘密鍵を取り出すことを許さないデータ項目のオープンデジタル処理により少なくとも一部は生成されるステップを含むという点で注目に値する。
【００１３】
「オープンデジタル処理」という表現は、考えられる侵入に対する特定の保護の恩恵を受けないデジタル処理オペレーションを意味すると理解される。このオープンデジタル処理オペレーションは、エンティティにより実行可能である。上述のデータ項目は、例えば、前記秘密鍵のイメージである。
【００１４】
負荷を分散させることが可能であるため、全く同一の暗号方法を非常に多様な数多くの制約条件を持つ多数のアプリケーションおよび環境で使用することができる。特に、限られた計算能力を持つチップを使用して比較的短い時間で取引を遂行することができると思われる。
【００１５】
例えば、n個の整数を含み、乗算などの内部算法が与えられている有限群の特性を利用する暗号法が知られている。特に、nが少なくとも２つの非常に大きな素数の積である数の場合に、累乗の元の指数を復元することは実際上不可能である。
【００１６】
特に本発明による方法は、
-第１のエンティティが第１のエンティティにより秘密にされている第１の乱数を使ってプルーフの第１の要素を生成する第１のステップと、
-  １つまたは複数の共通数と呼ばれるものがプルーフの第１の要素と関連して生成され、したがって第１のエンティティおよび第２のエンティティが前記１つまたは複数の共通数を認識していなければならない第２のステップと、
-  少なくとも第１の秘密鍵整数と第１の乱数および前記共通数の少なくとも１つとを組み合わせることにより第１のエンティティは前記秘密鍵のイメージを生成する第３のステップと、
-  プルーフの第２の要素は、前記秘密鍵のイメージに対して、エンティティにより実行可能なオープンデジタル処理オペレーションを適用することにより生成され、前記公開鍵の第１の部分をプルーフの第２の要素に適用し、前記公開鍵の少なくとも第２の部分を前記共通数の少なくとも１つに適用することにより第２のエンティティがプルーフの第１の要素とプルーフの第２の要素との一致を検証できるようにする第４のステップを含む。
【００１７】
「プルーフの第１の要素と関連する共通数の生成」という表現は、プルーフの第１の要素が予め知られていなければならない共通数の生成を意味するものと理解される。この生成は、純粋にランダムで、プルーフの第１の要素とは無関係であってよく、あるいはプルーフの第１の要素に依存していてもよい。この関連付けにより、共通数が生成されたときにプルーフの第１の要素に戻ることが不可能になる。
【００１８】
より具体的には、
-  第１のステップで、第１のエンティティは、第１のエンティティにより秘密にされる秘密鍵に含まれる第１の整数sよりも非常に大きい第１の乱数rを生成し、第１のエンティティは、前記公開鍵に含まれている場合も含まれていない場合もある、指数が第１の乱数rである第１の整数Gの、nを法とする累乗を計算した後に得られるプルーフの第１の要素を生成し、
-  第３のステップでは、第１のエンティティは、第１の乱数rと少なくとも第１の秘密鍵整数sの一次結合により前記秘密鍵のイメージyを生成し、前記一次結合の少なくとも１つの乗法的係数は前記共通数または前記共通数のうちの１つであり、
-  第４のステップで、生成されたプルーフYの第２の要素は、前記公開鍵に含まれる場合も含まれない場合もあり、その指数が秘密鍵のイメージyである、第２の整数gの、nを法とする累乗に等しく、第２の整数gは、第１の公開鍵整数Gが、前記公開鍵に含まれる場合も含まれない場合もある第３の整数を指数とする第２の整数gの、nを法とする累乗となるような整数である。
【００１９】
第１に、第３のステップで生成された秘密鍵イメージを知っても、秘密鍵に関する情報は得られず、後者は第１の乱数との一次結合によりマスクされており、そのプルーフの第１の要素からは何も明らかにならない。第２に、プルーフの第１の要素および公開鍵を知っていても、秘密鍵のイメージがわかっていないとプルーフの第２の要素を生成できず、第２のステップにおけるその生成は単独で秘密鍵および乱数を知っている第２のエンティティでしか実行されない。第１のエンティティは、プルーフの第１の要素との一致の信頼できる検証には第３の整数と共通数の比較的小さな値で十分なので、第５のステップを実行するのに限られたコンピューティング資源を持つ場合がある。
【００２０】
第４のステップは、第１のエンティティにより実行することができる。しかし、第４のステップで累乗を計算するコストは、指数が大きな値を取るためかなり大きなものになる。
【００２１】
第４のステップは、第１のエンティティから秘密鍵のイメージyを受け取るエンティティにより実行されると都合がよい。上で説明したように、秘密鍵のイメージがどのようなエンティティに知られていようと、この方法のセキュリティは損なわれない。第１のエンティティ以外のエンティティによる第４のステップの実行により、第１のエンティティの負担が軽減される。エンティティはどれも、オプションにより、第２のエンティティまたは中間エンティティである。
【００２２】
また第４のステップは、
-  第１のエンティティは、イメージyをイメージyを表すデータワードのu個の下位ビットにより表される第１の部分イメージy'と、前記データワードの残りの上位ビットにより表される第２の部分イメージy"とに分解し、第１のエンティティは第１のコンポーネントY'とプルーフの第２の要素の第２のコンポーネントg'を生成し、前記コンポーネントでは以下が成り立ち、
【００２３】
【数１】
2005513564.tif 000003
【００２４】
第１のエンティティは、第１のコンポーネントY'、第２のコンポーネントg'、および第２の部分イメージy"を中間エンティティに送信する、第１のサブステップと、
-  任意のエンティティが第２の部分イメージy"を指数とする第２のコンポーネントg'の累乗を第１のコンポーネントY'に掛けることによりプルーフYの第２の要素を生成し、任意のエンティティがプルーフYの第２の要素を第２のエンティティに送る第２のサブステップを含むと都合がよい。
【００２５】
y'の値は、したがってyの値よりも小さいが、第１のコンポーネントY'と第２のコンポーネントg'を生成するのに第２のエンティティにおいて限られたコンピューティング資源のみ必要とする。第２の部分イメージおよび２つのコンポーネントY'およびg'は任意が秘密鍵のイメージを完全に知らなくてもプルーフの第２の要素を生成するのに十分であるため、この方法のセキュリティは向上する。
【００２６】
特に、暗号法を使用して第１のエンティティと第２のエンティティとの間の対話を認証する場合、第２のステップは、第２のエンティティから受け取ったプルーフの第１の要素に関して、セキュリティ間隔における少なくとも１つの共通数を選択し前記共通数を第１のエンティティに送る第２のエンティティにより実行される。
【００２７】
これにより、第２のエンティティは、第１のエンティティが対話内のプルーフの第１の要素との一致としてプルーフの第２の要素を生成することに関して共通数を受け取ったことを確認することが可能になる。
【００２８】
より具体的には第５のステップで、プルーフxの第１の要素が、指数が第３の整数eであるプルーフYの第２の要素の累乗と、指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積に等しいときに一致が検証される。
【００２９】
より具体的にはさらに、また異なる形で、対話が第１のエンティティによるメッセージMの送信を含む場合、第５のステップにおいて、プルーフの第１の要素がプルーフの第１の要素が添付されているデジタルメッセージM、及び、指数が第３の整数eであるプルーフYの第２の要素の累乗と、指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しい場合に一致が検証される。
【００３０】
より具体的に、かつ異なる形で、メッセージ署名Mに暗号法を使用する場合、第２のステップは、プルーフの第１の要素およびデジタルメッセージMに基づいて少なくとも１つの共通数を生成し、前記デジタルメッセージMに前記共通数が添付される、第１のエンティティにより実行される。
【００３１】
より具体的には第５のステップにおいて、共通数が、デジタルメッセージM、及び、指数が第３の整数eであるプルーフYの第２の要素の累乗と、指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しい場合に、一致が検証される。
【００３２】
本発明の対象は、暗号法を実装するように設計されている証明者デバイス、検証者デバイス、および媒介デバイスでもある。
【００３３】
証明者デバイスを考察すると、秘密にされ侵入者に対する保護処置が講じられている秘密鍵を与えられており、プルーフを生成することに関して、その検証では前記秘密鍵に関連付けられている公開鍵を使用することにより証明者デバイスが前記プルーフの発信者であることを保証することが可能であるが、証明者デバイスは、
-  証明者デバイス内に秘密にされている第１の乱数に基づいて、プルーフの第１の要素を生成し、少なくとも第１の秘密鍵整数と第１の乱数およびプルーフの第１の要素に関連付けられている複数の共通数のうち少なくとも１つを組み合わせることにより前記秘密鍵のイメージを生成し、前記公開鍵の第１の部分をプルーフの第２の要素に適用し、前記公開鍵の少なくとも第２の部分を前記共通数の少なくとも１つに適用することによりオープンデジタル処理オペレーションをプルーフの第１の要素とプルーフの第２の要素との一致を検証することを可能にする前記秘密鍵イメージに適用することによりプルーフの第２の要素を生成することが可能であるように設計されている計算手段と、
-  プルーフの少なくとも前記第１の要素を伝送するように設計されている通信手段を備えるという点で注目に値する。
【００３４】
証明者デバイスでは、
-  一方で、計算手段は、秘密にされている秘密鍵に含まれる第１の整数sよりもかなり大きい第１の乱数rを生成し、第１の乱数rを指数とする前記公開鍵に含まれている場合もいない場合もある第１の整数Gの、nを法とする累乗を計算することによりプルーフの第１の要素を生成するように設計され、
-  他方で、計算手段は、第１の乱数rと少なくとも第１の秘密鍵整数sの一次結合により前記秘密鍵のイメージyを生成し、前記一次結合の少なくとも１つの乗法的係数は前記共通数または前記共通数のうちの１つであるように設計されると都合がよい。
【００３５】
証明者デバイスのさまざまな修正は、実装すべき方法のバージョンに応じて好ましい。
【００３６】
例えば、通信手段は、さらに、プルーフの第１の要素を伝送した後に前記共通数を受信するように設計されている。
【００３７】
通信手段は、秘密鍵イメージを伝送するように設計されているのが好ましい。
【００３８】
任意選択により、計算手段は、プルーフの第２の要素を生成するように設計される。
【００３９】
計算手段は、イメージyを、イメージyを表すデータワードのu個の下位ビットにより表される第１の部分イメージy'と、前記データワードの残りの上位ビットにより表される第２の部分イメージy"とに分解し、第１のコンポーネントY'とプルーフの第２の要素の第２のコンポーネントg'を生成し、前記コンポーネントでは以下が成り立ち、
【００４０】
【数２】
2005513564.tif 000004
【００４１】
ただし、gは、第１の公開鍵整数Gが前記公開鍵に含まれる第３の整数eを指数とする第２の整数gの、nを法とする累乗となるような第２の整数であり、通信手段は、第１のコンポーネントY'、第２のコンポーネントg'、および第２の部分イメージy"を伝送するように設計されると都合がよい。
【００４２】
メッセージ署名の特定の場合、計算手段は、プルーフの第１の要素と、デジタルメッセージMとに基づいて、少なくとも１つの共通数を生成し、前記デジタルメッセージMには前記共通数が添付されるように設計される。
【００４３】
さまざまな他の実施形態によれば、計算手段は、前記公開鍵に含まれる場合も含まれない場合もある、指数は第１の乱数rである、第１の整数Gの、nを法とする累乗を計算することによりプルーフの第１の要素を生成するように設計される。
【００４４】
第１の他の実施形態によれば、第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ以下の式で与えられる。
G=ge modulo n
v=G-s modulo n
【００４５】
第２の他の実施形態によれば、第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ以下の式で与えられる。
G=ge modulo n
v=Gs modulo n
【００４６】
第３の他の実施形態によれば、第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ以下の式で与えられる。
G=g-e modulo n
v=G-s modulo n
【００４７】
第４の他の実施形態によれば、計算手段は、以下の式により、２つの共通数aおよびbの一次結合により秘密鍵イメージyを生成するように設計される。
y=ar+bs
【００４８】
第５の他の実施形態によれば、秘密鍵が複数の秘密数s1、s2などを含む場合、
-  計算手段は、プルーフxの第１の要素に関連付けられている、同じ数の共通数c1、c2を生成するように設計され、
-  計算手段は、以下の式による一次結合により秘密鍵イメージを生成するように設計される。
y=r+c1s1+c2s2+...
【００４９】
第６の他の実施形態によれば、公開鍵が特に証明者デバイス内で素数が秘密にされる法nを含む場合、計算手段(37)は、中国の剰余定理と呼ばれる手法を使用することにより累乗を計算するように設計される。証明者デバイスは、公開鍵がプルーフxの第１の要素のk個のあらかじめ計算された値を含む場合に改善され、計算手段は、繰り返し毎にプルーフの第１の要素の異なる値で各実行をk回繰り返すように設計される。
【００５０】
任意選択により、プルーフの第１の要素は、前記公開鍵に含まれる場合もあれば含まれない場合もある、指数は第１の乱数rである、第１の整数Gの、nを法とする累乗の関数fに等しい。前記秘密鍵に関連付けられている公開鍵を使用して、証明者デバイスにより秘密にされている秘密鍵が与えられる証明者デバイスによりプルーフが発行されたことを検証する検証者デバイスを考察すると、検証者デバイスは、
-  プルーフの第１の要素とプルーフの第２の要素を受け取るように設計されている通信手段と、
-  前記公開鍵の第１の部分をプルーフの第２の要素に、前記公開鍵の少なくとも第２の部分をプルーフの第１の要素に関連して生成された複数の共通数のうち少なくとも１つに適用することによりプルーフの第１の要素とプルーフの第２の要素との一致を検証するように設計されている計算手段を備えるという点で注目に値する。
【００５１】
検証者デバイスでは、計算手段は、プルーフの第１の要素が、指数が第３の整数eであるプルーフYの第２の要素の累乗と指数が前記共通数cである第４の整数vの累乗の、nを法とする積と一致することを検証し、第３の整数および第４の整数は前記公開鍵に含まれるように設計されると都合がよい。
【００５２】
また、計算手段は、プルーフの第１の要素を受信した後セキュリティ間隔の範囲内の少なくとも１つの共通数を選択するように設計されると都合がよく、また通信手段は前記共通数を伝送するように設計されるという点で都合がよい。
【００５３】
特に、計算手段は、プルーフxの第１の要素が、指数が第３の整数eであるプルーフYの第２の要素の累乗と指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗の、nを法とする積に等しいときに一致が検証されたと宣言するように設計される。
【００５４】
より具体的には、計算手段は、プルーフの第１の要素が、プルーフの第１の要素が添付されるデジタルメッセージM、および、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しいときに一致が検証されたと宣言するように設計される。
【００５５】
別の方法で、計算手段は、共通数がデジタルメッセージM、及び、指数が第３の整数eであるプルーフYの第２の要素の累乗と、指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しい場合に、一致が検証されたと宣言するように設計される。
【００５６】
検証者デバイス内でこの等式の検証に使用する公式は、
x=Yevc modulo n
または、
Ye=vcx modulo n
または、
Yex=vc modulo n
であるか、またはそうでなければ、一致は、以下の等式により検証される。
Yevb=xa modulo n
【００５７】
秘密鍵が複数の秘密数s1、s2などを含む場合、計算手段(38)は、プルーフxの第１の要素について、同じ数の共通数c1、c2などを選択するように設計されており、計算手段(38)は、以下の等式を使って、同じ数の第４の公開鍵整数v1、v2などによる一致を検証するように設計されている。
Yev1c2V2c2...=x modulo n
【００５８】
検証者デバイスの他の実施形態では、計算手段は、メモリ内に、公開鍵の一部としてみなされるプルーフxの第１の要素の少なくとも１つのあらかじめ計算された値を備える。
【００５９】
特に、計算手段は、メモリ内に、プルーフxの第１の要素のk個のあらかじめ計算された値を備え、通信手段は、プルーフのk個の第２の要素を受信するように設計されており、計算手段は、受信されたプルーフのそれぞれの第２の要素とプルーフの第１の要素の異なる値との一致を検証するように設計されている。
【００６０】
検証者デバイスの他の実施形態では、プルーフの第１の要素が、前記公開鍵に含まれる場合もあれば含まれない場合もある、指数は第１の乱数rである、第１の整数Gの、nを法とする累乗の関数fに等しい場合、計算手段は、この関数の結果に関する検証を実行するように設計される。
【００６１】
証明者デバイスにより秘密にされている秘密鍵に基づきプルーフを生成する目的のため証明者デバイスの下流に導入することに関して媒介デバイスを考察するが、前記プルーフは前記秘密鍵に関連付けられている公開鍵により検証可能であり、媒介デバイスは、前記秘密鍵のイメージのオープンデジタル処理によりプルーフの少なくとも１つの要素を生成する計算手段を含み、前記秘密鍵イメージでは前記秘密鍵を元に戻すことができないという点で注目に値する。
【００６２】
特に、デバイスは前記秘密鍵イメージyを作成するように設計されている通信手段を備える。
【００６３】
考えられる一実施形態によれば、計算手段は、指数が秘密鍵イメージyである前記公開鍵に含まれる第２の整数gの、nを法とする累乗を計算することによりプルーフYの第２の要素を生成するように設計される。
【００６４】
考えられる他の実施形態によれば、媒介デバイスは、秘密鍵の第１の部分イメージy'、第１のコンポーネントY'、およびプルーフの第２の要素の第２のコンポーネントg'を受信するように設計された通信手段を備え、計算手段は、第２の部分イメージy"を指数とする第２のコンポーネントg'の累乗を第１のコンポーネントY'に掛けることによりプルーフYの第２の要素を生成するように設計される。
【００６５】
媒介デバイスの通信手段は、プルーフYの第２の要素を検証者デバイスに伝送するように設計されているのが好ましい。
【発明を実施するための最良の形態】
【００６６】
本発明は、付属の図面を参照して後述する説明例を見るとさらによく理解されるであろう。
【００６７】
後述の実装方法は、エンティティ認証また識別方法である。これにより、証明者Aは、本物であることを検証者Bに納得させることができる。この方法は、メッセージまたはメッセージデジタル署名を認証する方法に変換することができる。そのセキュリティは、大きな整数を因数分解するという複合した難しさに依存する。
目的と上で説明した結果に従って、この方法では、計算を複数のエンティティ間に分散させる方法に応じた２つのオプションを含む。nを大きな合成数とし、５つの正の整数e、g、G、s、およびvを正かつnよりも小さく数とし、以下の式が成り立つとする。
G=ge (mod n) and v=G-S (mod n)
【００６８】
したがって、プルーフ書の公開鍵は、全部または一部、選択されたオプションに応じて、５つ組(n,e,g,G,v)から形成されるが、秘密鍵は、証明者により秘密にされている少なくとも整数sから形成される。公開鍵自体は、複数の証明者に共通であるという意味で一般的部分と、証明者ごとに異なるという意味で固有の部分に分解することができる。
【００６９】
セキュリティパラメータと呼ばれる２つの正整数kおよびtも定義される。すべてのオプションにおいて、第１のエンティティ-検証者B-はすでに、第２のエンティティ-証明者A-によりプルーフが与えられていることを検証するために必要なすべての公開パラメータ、つまり、そのアイデンティティ、公開鍵、公開鍵プルーフ書などを知っている。
【００７０】
第１のオプションにより、公開鍵は、３つ組(n,e,v)であり、エンティティBによるエンティティAの認証は、図１を参照して現在説明されているプロトコルをk回繰り返すことにより実行される。
【００７１】
第１のステップ9で、エンティティAは、sよりもかなり大きな第１の乱数rを生成し、x=Gr(mod n)を計算し、xをエンティティBに送信する。周知のように、エンティティAおよびBは、コンピュータタイプ、またはチップカードタイプのものである。「(mod n)」という表現は、、nを法とするということを表す、つまり、周知のように、計算の結果は、一般的に法と呼ばれる整数nによる注目している演算の結果の整数除算の剰余である。ここで、整数xは、乱数rを生成するエンティティのみが数値xを生成することができるためプルーフの第１の要素となる。乱数rは、それを生成するエンティティによって伝達されることはない。知られている数論から、数rは、第１の整数Gおよび法nを知っても数rを数xから復元できないような十分に大きな数値として選択される。プルーフのこの第１の要素は、第１の整数Gが公開鍵に含まれている場合、任意のエンティティがそのような要素を任意の乱数から生成できるため十分ではない。図１を参照して説明した方法では、整数Gは必ずしも公開鍵に含まれないことに注意されたい。
【００７２】
プルーフxの第１の要素をエンティティBが受け取ると、遷移10の有効性が確認され、その後、第２のステップ11がアクティブ化される。
【００７３】
ステップ11で、エンティティBは、セキュリティ間隔と呼ばれる間隔[0,t-1]の範囲内の整数cをランダムに選択し、その数cをエンティティAに送信する。したがって、数cは、エンティティBによるプルーフの第１の要素に関連して生成され、エンティティAおよびBに共通であり、また、エンティティAとBとの間の対話にこっそり入り込む他のエンティティにも共通である。
【００７４】
共通数cをエンティティAが受け取ると、遷移12の有効性が確認され、その後、第３のステップ13がアクティブ化される。
【００７５】
ステップ13で、エンティティAはy=r+scを計算する。そこで、エンティティAは秘密鍵のイメージyを数rと数sの一次結合の形で生成し、その乗法的係数は共通数cである。乱数rは非常に大きく、伝達されないため、イメージyを知っても、積scを復元することはできず、したがって、秘密鍵の元の数sを得ることはできず、したがって、エンティティAにより秘密にされたままである。エンティティAだけが数sを知っているので、エンティティAのみが共通数cを組み込むイメージを生成することができる。
【００７６】
ここで、第４のステップ15は、ステップ13の直後にアクティブ化される。ステップ15で、エンティティAはY=gy(mod n)を計算して、YをBに送信する。したがって、エンティティAは、プルーフYの第２の要素をここで生成する。第２の整数gは必ずしも、公開鍵の中に含まれないことに注意されたい。エンティティBがプルーフYの第２の要素を受け取ると、遷移16の有効性が確認され、その後、第５のステップ17がアクティブ化される。
【００７７】
ステップ17で、エンティティBは、Yevc=x(mod n)であることを検証する。上で見たように、プルーフの第２の要素は、秘密鍵に関する情報を伝達しないが、プルーフYの第２の要素は、以下のようになる。
Y=gr+sc(mod n)
【００７８】
したがって、プルーフYの第２の要素の指数が公開鍵の第３の整数eである累乗の計算を行うと、以下の式が得られる。
Ye=g(r+sc)e=Gr+sc(mod n)
【００７９】
さらに、数論によれば第４の整数vは秘密鍵に関する情報を一切伝達しないが、前記整数は実際には、以下のようになる。
vc=G-sc(mod n)
【００８０】
したがって、いつでもrが伝達されなければ、等式
Yevc=Gr=x(mod n)
により、エンティティAは、これだけがsを知っているが、cも知っていることがプルーフされる。
【００８１】
インポスターを秘密sを知らずにAであるとしてごまかそうとするエンティティであると考えると、このインポスターを検出しない確率は1/ktに等しい。多くのアプリケーションでは、積ktは、216のオーダーの例として、比較的小さい値となるように選択することができる。
【００８２】
k=1およびt=eとするのが好ましく、この場合、上で定義されている確率は、1/eに等しく、適用される検証式は１つだけである。eが例えば216に等しいとすると、指数eおよびcは比較的小さいため検証は比較的短時間のうちに終わる。この検証は、あらかじめステップ11の終わり、または前もって計算することによりさらに高速化することができる。
z=vc(mod n)
【００８３】
こうして、第４のステップでは、BはYez=x(mod n)を検証するだけでよい。kおよびtの他の値も可能である。
【００８４】
この基本プロトコルを最適化するさまざまな方法が考えられる。例えば、v=G-s(mod n)は、v=Gs(mod n)で置き換えることができ、その場合、検証の式は、Ye=xvc(mod n)となる。
【００８５】
再び、例えば、G=ge(mod n)は、G=g-e(mod n)で置き換えることが可能であり、その場合、検証の式は、xYe=vc(mod n)となる。
【００８６】
再び、例えば、cを正または負の整数の対(a,b)で置き換え、y=r+scをy=ar+bsで置き換えることが可能であり、その場合、検証の式はYevb=xa(mod n)となる。
【００８７】
再び、例えば、複数の秘密の数s1、s2など、複数の公開鍵v1、v2など、および複数の整数c1、c2などを選択して、y=r+scをy=r+s1c1+s2c2+...で置き換えることが可能であり、その場合、検証の式はYev1c1v2c2=x'mod n)となる。
【００８８】
nが公開鍵の特定の部分に含まれる場合、かつnの素因数がAによって知られている場合、第１のステップを高速化するには、「中国の剰余定理」と呼ばれる手法を使用する。
【００８９】
第１のステップは、前もって実行しておくことができる。さらに、xのk個の値はAの公開鍵の一部をなし、その場合、プロトコルは直接第２のステップから始まる。
【００９０】
数xは、fを例えば暗号ハッシュ関数に等しい(または含む)関数とすると値f(x)で置き換えることができ、その場合、検証の式はf(Yevc(mod n))=xとなる。上述の修正の全部または一部を結合することが可能である。
【００９１】
Yの計算もまた、A以外の任意のエンティティにより実行することができ、これはセキュリティを失わずに実行できる。この場合、Aはyのみを計算し、このエンティティをyとともに与える。まず、yを知っていても、sに関する情報は得られないが、それは、乱数rによって積scが「マスク」されているためである。第２に、詐欺行為者が断片すべてを集めてYをでっち上げることは実際上不可能であるが、それは、n、e、v、x、およびcが与えられても、因数分解が困難な問題であれば第４のステップの検証の式を満たすYの値を見つけることはできないためである。
【００９２】
図２を参照して説明されている第２のオプションによれば、公開鍵は、４つ組(n,e,g,v)であり、エンティティBによるエンティティAの認証は、CがA以外のエンティティを表す場合に以下のプロトコルをk回繰り返すことにより実行される。
【００９３】
この方法は、ステップ13まで図１を参照して説明されているのと同じ方法で実行される。図２を参照すると、ステップ13は、エンティティAが秘密鍵イメージyを中間エンティティCに送信するという理由で修正される。すでに見たように、イメージyは秘密鍵に関する情報をいっさい与えない。
【００９４】
イメージyをエンティティCが受け取ると、遷移14の有効性が確認され、その後、第４のステップ15がアクティブ化される。
【００９５】
ステップ15で、この場合、プルーフY=gy(mod n)の第２の要素を計算して、YをBに送信するのは中間エンティティCである。
【００９６】
次にこの方法は、遷移16およびステップ17を介して図１を参照して説明されているのと同じ方法で続行する。
【００９７】
物理的に、中間エンティティCは、例えば、チップカードなどの証明者のセキュリティデバイス、決済端末などの検証者のセキュリティデバイス、またはさもなければコンピュータなどの他のデバイスに収められているチップ内に実現されるが、これは、必ずしもセキュリティで保護されない。セキュリティは、エンティティCはそれ自体では適当な、つまり検証の式が満たされるような値Yを見つけられないという事実に基づいている。
【００９８】
図３を参照して説明されている第３のオプションでは、Yの計算はエンティティAとCとに分割される。この計算を分ける方法としてはさまざまなものがある。ここでもやはり、ステップ13まで図１を参照して説明されているのと同じ方法でこの方法を実行する。ステップ13では、都合のよいことに、イメージyは以下の式に従って分解される。
y=y'+2uy"
【００９９】
この公式では、uは正の整数であり、y'は2uよりも小さい整数である。分解は実行しやすい。イメージyを表すデータワードでは、第１の部分イメージy'はこのワードのu個の下位ビットによって表される。第２の部分イメージは、このデータワードの残りの上位ビットにより表される。
【０１００】
第４のステップは、プルーフの第２の要素を計算するために、この場合、２つのサブステップ18および25に分解される。
【０１０１】
第１のサブステップ18は、ステップ13の直後にエンティティAにより実行される。サブステップ18で、エンティティAは以下の公式に従ってプルーフの第２の要素の第１のコンポーネントY'を計算する。
Y'=gy'(mod n)
【０１０２】
例えば8または16のオーダーのuの比較的低い値を選択することにより、第１の部分イメージy'の値はイメージyの値よりもかなり小さいため、第１のコンポーネントY'の計算では、プルーフの第２の要素の完全な計算に必要な資源はかなり少ない。
【０１０３】
サブステップ18で、エンティティAは以下の公式に従ってプルーフの第２の要素の第２のコンポーネントg'を計算する。
【０１０４】
【数３】
2005513564.tif 000005
【０１０５】
第１のコンポーネントg'の計算では、計算資源はごくわずかでよいが、それは、uの平方を実行するだけでよいためであり、第１の平方は第２の整数gで実行され、その後続く平方は、nを法とする次の平方の結果に対し実行される。
【０１０６】
サブステップ18の終わりに、エンティティAは２つのコンポーネントg'およびY'、および第２の部分イメージy"を中間エンティティCに送信する。セキュリティは、秘密鍵のイメージは丸ごと伝達されることはないという事実により高められている。エンティティAの計算負荷は、プルーフの第２の要素はエンティティAにより全部は計算されないという事実により低減される。
【０１０７】
したがって、エンティティCが２つのコンポーネントg'、Y'および第２の部分イメージy"を受信すると、遷移14の有効性が確認され、中間エンティティCで第２のサブステップ25がアクティブ化される。
【０１０８】
サブステップ25で、エンティティCはY=Y'g'y"(mod n)を計算し、こうして生成されたプルーフYの第２の要素をエンティティBに送信する。
【０１０９】
次にこのプロシージャは、遷移16およびステップ17を介して図１を参照して説明されているのと同じ方法で続行する。
【０１１０】
遷移16の有効性確認の前に、エンティティBはステップ19を実行し、このときに、ステップ17のVの計算を容易にするため、数zが以下の式により計算される。
z=vc(mod n)
【０１１１】
図１、2、および4の例への遷移16の前にさらにステップ19を導入できる。
【０１１２】
ここでもやはり、Yの計算をエンティティCと検証者Bに分けることも可能であることを指摘しておく。
【０１１３】
上述のプロトコルは、メッセージ認証プロトコルまたはデジタルプルーフスキームに変換することができる。
【０１１４】
図４は、第１のエンティティBにより受信されたメッセージMが第２のエンティティAによって送信されたことを認証することを可能にする方法のステップを示している。第１のステップ20で、エンティティAは、sよりもかなり大きな第１の乱数rを生成し、ステップ9のようにx=Gr(mod n)を計算する。xをエンティティBに送信する代わりに、エンティティAはメッセージMに対し数xとともに、例えば、以下のような暗号ハッシュ関数に等しいまたは暗号ハッシュ関数を含む関数hを適用することによりプルーフx'の第１の要素を与える。
x'=h(x,M)
【０１１５】
次に、エンティティAは、メッセージMおよびプルーフx'の第１の要素をエンティティBに送信する。
【０１１６】
プルーフxの第１の要素をエンティティBが受け取ると、遷移21の有効性が確認され、その後、第２のステップ11がアクティブ化される。次にこのプロシージャは、図１から3のうちの１つを参照して説明されているのと同じ方法で続行する。
【０１１７】
ステップ11で、エンティティBは、セキュリティ間隔[0,t-1]の範囲内の整数cをランダムに選択し、その数cをエンティティAに送信する。したがって、数cは、エンティティBによるプルーフの第１の要素に関連して生成され、エンティティAおよびBに共通であり、また、エンティティAとBとの間の対話にこっそり入り込む他のエンティティにも共通である。
【０１１８】
共通数cをエンティティAが受け取ると、遷移12の有効性が確認され、その後、第３のステップ13がアクティブ化される。
【０１１９】
ステップ13で、エンティティAはy=r+scを計算する。そこで、エンティティAは秘密鍵のイメージyを数rと数sの一次結合の形で生成し、その乗法的係数は共通数cである。乱数rは非常に大きく、伝達されないため、イメージyを知っても、積scを復元することはできず、したがって、秘密鍵の元の数sを得ることはできず、したがって、エンティティAにより秘密にされたままである。エンティティAだけが数sを知っているので、エンティティAのみが共通数cを組み込むイメージを生成することができる。図４に示された例では、エンティティAは、秘密鍵イメージyを中間エンティティCに送信する。すでに見たように、イメージyは秘密鍵に関する情報をいっさい与えない。
【０１２０】
イメージyをエンティティCが受け取ると、遷移14の有効性が確認され、その後、第４のステップ15がアクティブ化される。
【０１２１】
ステップ15で、この場合、プルーフY=gy(mod n)の第２の要素を計算して、YをBに送信するのは中間エンティティCである。
【０１２２】
エンティティBがプルーフYの第２の要素を受け取ると、遷移16の有効性が確認され、その後、第５のステップ22がアクティブ化される。
【０１２３】
ステップ22で、エンティティBは、ステップ17と同様にして、以下の公式を使って検証の値Vを計算し、
V=Yevc (mod n)
その後、以下の検証の式を使ってプルーフの第２の要素とプルーフの第１の要素との一致を検証する。
h(V,M)=x'
【０１２４】
関数fを使用する実装の他の方法では、検証の式はh(f(Yevc(mod n)),M)=x'となる。
【０１２５】
メッセージ認証とは異なり、メッセージ署名は送信者と無関係である。エンティティAによって送信されるメッセージMの署名は、エンティティBが他のエンティティからメッセージMを受信した場合には有効なままである。
【０１２６】
図５を参照すると、第１のステップ1で、エンティティAは、sよりもかなり大きな第１の乱数rを生成し、ステップ9のようにx=Gr(mod n)を計算する。こうして生成されたプルーフxの第１の要素は、プルーフを検証するためユニットAとBとの間の対話を認証することは不要なので、エンティティBに送信する必要はない。
【０１２７】
ステップ1の直後の第２のステップ23では、エンティティAはメッセージMに対し数xとともに、例えば、以下のような暗号ハッシュ関数に等しいまたは暗号ハッシュ関数を含む関数hを適用することにより共通数c'を生成する。
c'=h(x,M)
【０１２８】
ステップ23の直後の第３のステップ24で、エンティティAはy=r+scを計算する。そこで、エンティティAは秘密鍵のイメージyを数rと数sの一次結合の形で生成し、その乗法的係数は共通数cである。乱数rは非常に大きく、伝達されないため、イメージyを知っても、積scを復元することはできず、したがって、秘密鍵の元の数sを得ることはできず、したがって、エンティティAにより秘密にされたままである。エンティティAだけが数sを知っているので、エンティティAのみが共通数c'を組み込むイメージを生成することができる。上で見たように、イメージyは秘密鍵に関する情報をいっさい与えない。対(c',y)は、メッセージMの署名となるが、それは、この対がメッセージMと、エンティティAがこの署名の署名元であることを保証する秘密鍵要素の両方を組み込むからである。
【０１２９】
次に、エンティティAは、メッセージMおよび署名(c',y)をエンティティBまたは他のエンティティに送信する。
【０１３０】
エンティティBがエンティティAから他のエンティティへ向かうメッセージMをその署名(c',y)とともに受信すると、遷移2の有効性が確認される。
【０１３１】
イメージyをエンティティCが受け取ると、遷移4の有効性が確認され、その後、第４のステップ5がアクティブ化される。
【０１３２】
ステップ5で、この場合、プルーフY=gy(mod n)の第２の要素を計算して、YをBに送信するのは中間エンティティCである。
【０１３３】
エンティティBがプルーフYの第２の要素を受け取ると、遷移7の有効性が確認され、その後、第５のステップ8がアクティブ化される。
【０１３４】
ステップ8で、エンティティBは、ステップ17と同様にして、以下の公式を使って検証の値Vを計算し、
V=Yevc' (mod n)
その後、以下の検証の式を使ってプルーフの第２の要素とプルーフの第１の要素との一致を検証する。
h(V,M)=c'
【０１３５】
この場合、ステップ23で生成された共通数c'はそれ自身プルーフの第１の要素と一致するという事実により、プルーフの第１の要素との一致は、この等式により検証される。
【０１３６】
関数fを使用する実装の他の方法では、検証の式はh(f(Yevc(mod n)),M)=x'となる。
【０１３７】
エンティティCがイメージyを受信すると、遷移4の有効性が確認され、またこれは、エンティティAまたは他の変ティティから来るメッセージMとその署名(c',y)の受信の結果であるといえる。図５を参照すると、エンティティCがイメージyを受信するのは、遷移2によりアクティブ化されたステップ3の結果である。ステップ3で、エンティティBは署名からイメージyを抽出し、それをエンティティCに送信する。
【０１３８】
遷移7の有効性を確認する前に実行されるステップ6で、エンティティBは署名から共通数c'を抽出し、vc'に等しい数zを取得するため、ステップ8でVを計算するのが簡単になる。
【０１３９】
図6を参照すると、上述のエンティティA、B、およびCはそれぞれ、物理的に証明者デバイス30、検証者デバイス31、および媒介デバイス32である。証明者デバイス30は、例えば、クレジットカードなどのマイクロプロセッサカード、または携帯電話加入者識別カードである。検証者デバイス31は、例えば、銀行端末または電子商取引サーバ、または移動体通信事業者のハードウェアである。媒介デバイス32は、例えば、マイクロプロセッサカード拡張、クレジットカード読み取り端末、または電子携帯電話カードである。
【０１４０】
証明者デバイス30は、通信手段34および計算手段37を備える。プルーフしたデバイス30は、侵入に対して保護されている。通信手段34は、図１から3を参照して説明したステップ9のようにプルーフxの第１の要素を、図２および4を参照して説明したステップ13のように秘密鍵イメージyを、図１を参照して説明したステップ15のようにプルーフYの第２の要素を、図３を参照して説明したステップ18のように２つの秘密鍵イメージコンポーネントg'およびy"とともに第１の部分イメージY'を、図４および5を参照して説明したステップ20または24のようにメッセージMを、または実装する方法のバージョンにおいて図５を参照して説明したステップ24のように共通数cを送信するように設計されている。通信手段34は、さらに、実装する方法のバージョンが認証に対応している場合に遷移12で図１から4を参照して説明したように、共通数cを受信するように設計されている。実装する方法のバージョンが署名に対応している場合、通信手段34は、共通数cを受信するように設計されている必要はない。
【０１４１】
計算手段37は、実装する方法のバージョンに応じて、図１を参照して説明されているステップ9、13、および15、図２を参照して説明されているステップ9および13、図３を参照して説明されているステップ9、13、および18、図４を参照して説明されているステップ20および13、または図５を参照して説明されているステップ1、23、および24を実行するように設計されている。周知のように、計算手段37は、上述の計算に専用のマイクロプロセッサおよびマイクロプログラムまたは上述の計算に専用の組み合わせ回路を備える。
【０１４２】
検証者デバイス31は、通信手段35および計算手段38を含む。通信手段35は、認証に対応する方法のバージョンが実装される場合に図１から4を参照して説明されているステップ11のように１つまたは複数の数cを送信するように設計されている。実装する方法のバージョンが署名に対応している場合、通信手段35は、共通数cを送信するように設計されている必要はない。通信手段35は、さらに、図１から3を参照して説明されている遷移10および16でのようにプルーフxおよびYの２つの要素を、図４を参照して説明されている遷移21および16でのようにプルーフx'およびプルーフYの第２の要素とともにメッセージMを、または図５を参照して説明されている遷移2および8でのようにプルーフの第２の要素および１つまたは複数の共通数c'および秘密鍵イメージyを含むメッセージMを、受信するように設計されている。任意選択により、実装する方法のバージョンが署名に対応している場合、通信手段35は図５を参照して説明されているステップ3のように秘密鍵イメージyを再送するように設計されている。
【０１４３】
計算手段38は、実装する方法のバージョンに応じて、図１から図３を参照して説明されているステップ11、17、および19を、図４を参照して説明されているステップ11および22を、図５を参照して説明されているステップ6および8を実行するように設計されている。周知のように、計算手段38は、上述の計算に専用のマイクロプロセッサおよびマイクロプログラムまたは上述の計算に専用の組み合わせ回路を備える。
【０１４４】
媒介デバイス32は、通信手段36および計算手段39を備える。通信手段36は、図２および4を参照して説明されているステップ15でのように、図３を参照して説明されているステップ25でのように、または図５を参照して説明されているステップ5でのように、プルーフYの第２の要素を送信するように設計されている。通信手段36は、さらに、図２および4を参照して説明されている遷移14でのように秘密鍵イメージyを、図５を参照して説明されている遷移4でのように秘密鍵イメージyを、または図３を参照して説明されているよ遷移14でのように秘密鍵部分イメージy"およびプルーフの第２の要素の２つのコンポーネントg'およびY'を受信するように設計されている。
【０１４５】
計算手段39は、実装する方法のバージョンに応じて、図２または図４を参照して説明されているステップ15を、図３を参照して説明されているステップ25を、図５を参照して説明されているステップ5を実行するように設計されている。周知のように、計算手段39は、上述の計算に専用のマイクロプロセッサおよびマイクロプログラムまたは上述の計算に専用の組み合わせ回路を備える。
【０１４６】
プロシージャの改善として、上で説明した計算手段および通信手段の両方は、プルーフの第１の要素およびそれと異なるプルーフの第２の要素について毎回、上述のステップの実行をk回繰り返すように設計されている。
【図面の簡単な説明】
【０１４７】
【図１】本発明による第１のエンティティにより第２のエンティティの認証を行う認証方法のステップを説明する図である。
【図２】中間エンティティを伴う認証方法の第１の他の実施形態を示す図である。
【図３】中間エンティティを伴う認証方法の第２の他の実施形態を示す図である。
【図４】本発明によるメッセージ認証方法のステップを説明する図である。
【図５】本発明によるメッセージ署名に使用される方法のステップを説明する図である。
【図６】本発明による方法を実現するシステムを示す図である。
【符号の説明】
【０１４８】
Ａ…第１のエンティティ
Ｂ…第２のエンティティ
Ｃ…エンティティ
２，４，１０，１４，１６…遷移
３０…証明者デバイス
３１…検証者デバイス
３２…媒介デバイス
３４，３５，３６…通信手段
３７，３８，３９…計算手段
【図１】
2005513564.tif 000008
【図２】
2005513564.tif 000009
【図３】
2005513564.tif 000010
【図４】
2005513564.tif 000011
【図５】
2005513564.tif 000012
【図６】
2005513564.tif 000013
【手続補正書】
【提出日】平成16年8月27日(2004.8.27)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
第１のエンティティ(A)は、第１のエンティティ(A)により秘密にされている秘密鍵を使って、前記秘密鍵に関連付けられている公開鍵を使って第２のエンティティ(B)により検証可能なプルーフを生成する暗号法であって、プルーフの少なくとも１つの要素が前記秘密鍵を復元することができないデータ項目のオープンデジタル処理により少なくとも一部生成されるステップ(5,15)を含むことを特徴とする暗号法。
【請求項２】
暗号法であって、
−  第１のエンティティ(A)が、第１のエンティティ(A)により秘密にされている第１の乱数を使って、プルーフの第１の要素を生成する第１のステップ(1、9、20)と、
−  １つまたは複数の共通数と呼ばれるものがプルーフの第１の要素と関連して生成され、したがって第１のエンティティ(A)および第２のエンティティ(B)が前記１つまたは複数の共通数を認識していなければならない第２のステップ(11,23)と、
−  第１の乱数を伴う少なくとも第１の秘密鍵整数と少なくとも１つの前記共通数とを組み合わせることにより、第１のエンティティ(A)は前記秘密鍵のイメージを生成する第３のステップ(13、24)と、
−  前記公開鍵の第１の部分をプルーフの第２の要素に適用し、かつ前記公開鍵の少なくとも第２の部分を前記共通数の少なくとも１つに適用することによって、第２のエンティティ(B)がプルーフの第１の要素とプルーフの第２の要素との一致を検証できるようにするために、プルーフの第２の要素が、前記秘密鍵のイメージに対して、エンティティ(C)により実行可能なオープンデジタル処理オペレーションを適用することにより生成される第４のステップ(5、15)と
を含むことを特徴とする請求項１に記載の暗号法。
【請求項３】
暗号法であって、
−  第１のステップ(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を法とする累乗となるような整数であることを特徴とする請求項２に記載の暗号法。
【請求項４】
第４のステップにおいて、プルーフYの第２の要素は、第２のエンティティ(B)に送信されることを特徴とし、また、プルーフの第１の要素が、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積に一致することを、第２のエンティティ(B)が検証する第５のステップ(8、17、22)を含むことを特徴とする請求項３に記載の暗号法。
【請求項５】
第４のステップ(5、15)は、第１のエンティティ(A)以外の、第１のエンティティ(A)から秘密鍵イメージyを受信するエンティティ(C)により実行されることを特徴とする請求項２から４までのいずれか一項に記載の暗号法。
【請求項６】
第４のステップ(15)は、第１のエンティティ(A)により実行されることを特徴とする請求項２から４のいずれか一項に記載の暗号法。
【請求項７】
第４のステップは、
−  第１のエンティティ(A)は、イメージyを、イメージyを表すデータワードのu個の下位ビットにより表される第１の部分イメージy'と、前記データワードの残りの上位ビットにより表される第２の部分イメージy"とに分解し、また第１のエンティティ(A)は、第１のコンポーネントY'とプルーフの第２の要素の第２のコンポーネントg'を生成し、前記コンポーネントでは以下が成り立ち、
【数１】
2005513564.tif 000014
また第１のエンティティ(A)は、第１のコンポーネントY'、第２のコンポーネントg'、および第２の部分イメージy"を中間エンティティ(C)に送信する、第１のサブステップ(18)と、
−  中間エンティティ(C)は、第２の部分イメージy"を指数とする第２のコンポーネントg'の累乗を第１のコンポーネントY'に掛けることによりプルーフYの第２の要素を生成し、中間エンティティ(C)は、プルーフYの第２の要素を第２のエンティティ(B)に送信する第２のサブステップ(25)と
を含むことを特徴とする請求項２から４のいずれか一項に記載の暗号法。
【請求項８】
第２のステップ(11)は、第１のエンティティ(A)から受信したプルーフの第１の要素について、セキュリティ間隔の範囲内の少なくとも１つの共通数を選択し、前記共通数を第１のエンティティ(A)に送信する第２のエンティティ(B)により実行されることを特徴とする請求項２から７のいずれか一項に記載の暗号法。
【請求項９】
第２のステップ(23)は、プルーフの第１の要素と、前記共通数が添付されるデジタルメッセージMとに基づいて、少なくとも１つの共通数を生成する第１のエンティティ(A)により実行されることを特徴とする請求項２から７のいずれか一項に記載の暗号法。
【請求項１０】
第５のステップ(17)において、プルーフxの第１の要素が、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積に等しいときに、一致が検証されることを特徴とする請求項４に記載の暗号法。
【請求項１１】
第５のステップ(22)において、プルーフの第１の要素が、プルーフの第１の要素が添付されるデジタルメッセージMおよび指数が第３の整数eであるプルーフYの第２の要素の累乗と指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗のnを法とする積の関数に等しいときに一致が検証されることを特徴とする請求項４に記載の暗号法。
【請求項１２】
第５のステップ(8)において、共通数が、デジタルメッセージMと、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しい場合に、一致が検証されることを特徴とする請求項４に記載の暗号法。
【請求項１３】
プルーフの第１の要素は、前記公開鍵に含まれる場合もあれば含まれない場合もあり、その指数が第１の乱数rである第１の整数Gの、nを法とする累乗に等しいことを特徴とする請求項３に記載の暗号法。
【請求項１４】
第１の整数Gおよび第４の公開鍵整数vは、公式
G=ge modulo n
v=G-s modulo n
で与えられ、この等式は、公式
x=Yevc modulo n
によって検証されることを特徴とする請求項１３に記載の暗号法。
【請求項１５】
第４の公開鍵整数vは、公式
G=ge modulo n
v=Gs(modulo n)
で与えられ、この等式は、公式
Ye=vcx modulo n
によって検証されることを特徴とする請求項１３に記載の暗号法。
【請求項１６】
第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ、公式
G=g-e modulo n
v=G-s modulo n
で与えられ、この等式は、公式Yex=ve modulo nによって検証されることを特徴とする請求項１３に記載の暗号法。
【請求項１７】
暗号法であって、
−  第２のステップにおいて、２つの共通数aおよびbはプルーフxの第１の要素に関して生成され、
−  第３のステップにおいて、一次結合は、公式
y=ar+bs
によって与えられ、
−  第５のステップにおいて、一致は、等式
Yevb=xa modulo n
によって検証されることを特徴とする請求項１３に記載の暗号法。
【請求項１８】
秘密鍵が複数の秘密数s1、s2、...を含む場合、
−  第２のステップにおいて、同じ数の共通数c1、c2、...が、プルーフxの第１の要素に関して生成され、
−  第３のステップにおいて、一次結合は、公式
y=r+c1s1+c2s2+...
によって与えられ、
−  第５のステップにおいて、一致は、同じ数の第４の公開鍵整数v1、v2、...により、等式
Yev1c1v2c2...=x modulo n
を使って検証されることを特徴とする請求項１３に記載の暗号法。
【請求項１９】
公開鍵が特に、第１のエンティティ(A)からその素数が知られている法nを含む場合、第１のステップは中国の剰余定理と呼ばれる手法を使用することにより高速化されることを特徴とする請求項３に記載の暗号法。
【請求項２０】
公開鍵は、第２のステップでこの方法を開始するために、プルーフxの第１の要素のあらかじめ計算された少なくとも１つの値を含むことを特徴とする請求項２に記載の暗号法。
【請求項２１】
公開鍵は、プルーフxの第１の要素のk個のあらかじめ計算された値を含み、第２のステップから第５のステップまでの実行を、繰り返し毎にプルーフの第１の要素の異なる値を使ってk回繰り返すことを特徴とする請求項２０に記載の暗号法。
【請求項２２】
プルーフの第１の要素は、前記公開鍵に含まれる場合も含まれない場合もあり、その指数は第１の乱数rである、第１の整数Gの、nを法とする累乗の関数fに等しく、第５のステップの検証をこの関数の結果に基づいて行うことを特徴とする請求項２に記載の暗号法。
【請求項２３】
プルーフを生成するための、秘密にされ侵入者に対する保護処置が講じられている秘密鍵を与えられた証明者デバイスであって、前記秘密鍵に関連付けられている公開鍵を使用してその検証を行うことで、デバイス(30)が前記プルーフの発信元であることを保証することが可能であり、
−  デバイス(30)内に秘密にされている第１の乱数に基づいて、プルーフの第１の要素を生成し、第１の乱数を持った少なくとも第１の秘密鍵整数と、プルーフの第１の要素に関連付けられている複数の共通数のうち少なくとも１つとを組み合わせることにより、前記秘密鍵のイメージを生成し、かつ、
前記公開鍵の第１の部分をプルーフの第２の要素に適用し、前記公開鍵の少なくとも第２の部分を前記共通数の少なくとも１つに適用することにより、オープンデジタル処理オペレーションを、プルーフの第１の要素とプルーフの第２の要素との一致を検証することを可能にする前記秘密鍵イメージに適用することによって、プルーフの第２の要素を生成することが可能であるように設計されている計算手段(37)と、
−  プルーフの少なくとも前記第１の要素を伝送するように設計されている通信手段(34)を備えることを特徴とする証明者デバイス。
【請求項２４】
証明者デバイス(30)であって、
−  一方で、計算手段(37)は、秘密にされている秘密鍵に含まれる第１の整数sよりもかなり大きい第１の乱数rを生成し、第１の乱数rを指数として前記公開鍵に含まれている場合もいない場合もある第１の整数Gの、nを法とする累乗を計算することによりプルーフの第１の要素を生成するように設計され、
−  他方で、計算手段(37)は、第１の乱数rと少なくとも第１の秘密鍵整数sの一次結合により前記秘密鍵のイメージyを生成し、前記一次結合の少なくとも１つの乗法的係数は前記共通数または前記共通数のうちの１つであるように設計されることを特徴とする請求項２３に記載の証明者デバイス。
【請求項２５】
通信手段(34)は、プルーフの第１の要素を伝送した後に前記共通数を受信するように設計されていることを特徴とする請求項２３または２４のいずれか一項に記載の証明者デバイス(30)。
【請求項２６】
通信手段(34)は、秘密鍵イメージを伝送するように設計されていることを特徴とする請求項２３から２５のいずれか一項に記載の証明者デバイス(30)。
【請求項２７】
通信手段(37)は、プルーフの第２の要素を生成するように設計されていることを特徴とする請求項２３から２５のいずれか一項に記載の証明者デバイス(30)。
【請求項２８】
証明者デバイス(30)であって、
計算手段(37)は、イメージyを、イメージyを表すデータワードの下位ビットにより表される第１の部分イメージy'と、データワードの残りの上位ビットにより表される第２の部分イメージy"とに分解し、また第１のコンポーネントY'とプルーフの第２の要素の第２のコンポーネントg'を生成し、前記コンポーネントでは以下が成り立ち、
【数２】
2005513564.tif 000015
ただし、gは、第１の公開鍵整数Gが前記公開鍵に含まれる第３の整数eを指数とする第２の整数gのnを法とする累乗となるような第２の整数であり、
通信手段(34)は、第１のコンポーネントY'、第２のコンポーネントg'、および第２の部分イメージy"を伝送するように設計されることを特徴とする請求項２４から２５のいずれか一項に記載の証明者デバイス(30)。
【請求項２９】
計算手段(37)は、プルーフの第１の要素と前記共通数が添付されるデジタルメッセージMとに基づいて、少なくとも１つの共通数を生成するように設計されていることを特徴とする請求項２３および２４のいずれか一項に記載の証明者デバイス(30)。
【請求項３０】
計算手段(37)は、前記公開鍵に含まれる場合も含まれない場合もあり、指数は第１の乱数rである、第１の整数Gの、nを法とする累乗を計算することによりプルーフの第１の要素を生成するように設計されていることを特徴とする請求項２３に記載の証明者デバイス(30)。
【請求項３１】
第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ、公式
G=ge modulo n
v=G-s modulo n
によって与えられることを特徴とする請求項３０に記載の証明者デバイス(30)。
【請求項３２】
第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ、公式
G=ge modulo n
v=Gs modulo n
によって与えられることを特徴とする請求項３０に記載の証明者デバイス(30)。
【請求項３３】
第１の公開鍵整数Gおよび第４の公開鍵整数vは、それぞれ、公式
G=g-e modulo n
v=G-s modulo n
によって与えられることを特徴とする請求項３０に記載の証明者デバイス(30)。
【請求項３４】
計算手段は、公式
y=ar+bs
により、２つの共通数aおよびbの一次結合により秘密鍵イメージyを生成するように設計されていることを特徴とする請求項３０に記載の証明者デバイス(30)。
【請求項３５】
秘密鍵が複数の秘密数s1、s2、...を含む場合、
計算手段(37)は、プルーフxの第１の要素に関連付けられている同じ数の共通数c1、c2を生成するように設計され、
計算手段(37)は、公式
y=r+c1s1+c2s2+...
による一次結合により秘密鍵イメージを生成するように設計されていることを特徴とする請求項３０に記載の証明者デバイス(30)。
【請求項３６】
公開鍵が、特に証明者デバイス内で素数が秘密にされる法nを含む場合、計算手段(37)は、中国の剰余定理と呼ばれる手法を使用して指数計算をするように設計されていることを特徴とする請求項２４に記載の証明者デバイス(30)。
【請求項３７】
公開鍵が、プルーフxの第１の要素のk個のあらかじめ計算された値を含む場合、計算手段(37)は、繰り返し毎にプルーフの第１の要素の異なる値で各実行をk回繰り返すように設計されていることを特徴とする請求項２３に記載の証明者デバイス(30)。
【請求項３８】
プルーフの第１の要素は、前記公開鍵に含まれる場合も含まれない場合もあり、その指数が第１の乱数rである、第１の整数Gの、nを法とする累乗の関数fに等しいことを特徴とする請求項２３に記載のプルーフ証デバイス(30)。
【請求項３９】
前記秘密鍵に関連付けられている公開鍵を使用して、証明者デバイスにより秘密にされている秘密鍵が与えられた証明者デバイスによりプルーフが発行されたことを検証するための検証者デバイス(31)であって、
プルーフの第１の要素とプルーフの第２の要素とを受け取るように設計されている通信手段(35)と、
前記公開鍵の第１の部分を、プルーフの第２の要素に適用し、また前記公開鍵の少なくとも第２の部分を、プルーフの第１の要素に関連して生成された複数の共通数のうち少なくとも１つに適用することにより、プルーフの第１の要素とプルーフの第２の要素との一致を検証するように設計されている計算手段(38)と
を備えることを特徴とする検証者デバイス(31)。
【請求項４０】
計算手段(38)は、プルーフの第１の要素が、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである第４の整数vの累乗との、nを法とする積と一致することを検証し、第３の整数および第４の整数は前記公開鍵に含まれるように設計されていることを特徴とする請求項３９に記載の検証者デバイス(31)。
【請求項４１】
計算手段(38)は、プルーフの第１の要素を受信した後に、セキュリティ間隔の範囲内の少なくとも１つの共通数を選択するように設計され、また通信手段(35)は、前記共通数を伝送するように設計されていることを特徴とする請求項３９または４０に記載の検証者デバイス(31)。
【請求項４２】
計算手段(38)は、プルーフxの第１の要素が、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積に等しいときに、一致が検証されたと宣言するように設計されていることを特徴とする請求項４０に記載の検証者デバイス(31)。
【請求項４３】
計算手段(38)は、プルーフの第１の要素が、プルーフの第１の要素が添付されるデジタルメッセージM、および、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しいときに、一致が検証されたと宣言するように設計されていることを特徴とする請求項４０に記載の検証者デバイス(31)。
【請求項４４】
計算手段(38)は、共通数がデジタルメッセージM、および、その指数が第３の整数eであるプルーフYの第２の要素の累乗と、その指数が前記共通数cである前記公開鍵に含まれる第４の整数vの累乗との、nを法とする積の関数に等しい場合に、一致が検証されたと宣言するように設計されていることを特徴とする請求項４０に記載の検証者デバイス(31)。
【請求項４５】
等式は、公式
x=Yevc modulo n
によって検証されることを特徴とする請求項４２に記載の検証者デバイス(31)。
【請求項４６】
等式は、公式
Ye=vcx modulo n
によって検証されることを特徴とする請求項４２に記載の検証者デバイス(31)。
【請求項４７】
等式は、公式
Yex=vc modulo n
によって検証されることを特徴とする請求項４２に記載の検証者デバイス(31)。
【請求項４８】
一致は、等式
Yevb=xa modulo n
によって検証されることを特徴とする請求項４２に記載の検証者デバイス(31)。
【請求項４９】
秘密鍵が複数の秘密数s1、s2、...を含む場合、
計算手段(38)は、プルーフxの第１の要素に対する、同じ数の共通数c1、c2、...を選択するように設計され、
計算手段(38)は、等式
Yev1c2V2c2...=x modulo n
を使って、同じ数の第４の公開鍵整数v1、v2、...により一致を検証するように設計されていることを特徴とする請求項４１に記載の検証者デバイス(31)。
【請求項５０】
計算手段(38)は、メモリ内に、公開鍵の一部としてみなされるプルーフxの第１の要素の少なくとも１つのあらかじめ計算された値を備えることを特徴とする請求項３９に記載の検証者デバイス(31)。
【請求項５１】
計算手段(38)は、メモリ内に、プルーフxの第１の要素のk個のあらかじめ計算された値を備え、通信手段は、プルーフのk個の第２の要素を受信するように設計されており、計算手段(38)は、受信されたプルーフのそれぞれの第２の要素と、プルーフの第１の要素の異なる値との一致を検証するように設計されていることを特徴とする請求項５０に記載の検証者デバイス(31)。
【請求項５２】
プルーフの第１の要素が、前記公開鍵に含まれる場合も含まれない場合もある、その指数が第１の乱数rである、第１の整数Gの、nを法とする累乗の関数fに等しい場合に、計算手段(38)は、この関数の結果に基づいて検証を実行するように設計されていることを特徴とする請求項４０に記載の検証者デバイス(31)。
【請求項５３】
証明者デバイスにより秘密にされている秘密鍵に基づきプルーフを生成する目的のため証明者デバイスの下流に導入される媒介デバイス(32)であって、前記プルーフは、前記秘密鍵に関連付けられている公開鍵により検証可能であり、前記秘密鍵のイメージのオープンデジタル処理によりプルーフの少なくとも１つの要素を生成するための計算手段(39)を含み、前記秘密鍵イメージでは前記秘密鍵を元に戻すことができないことを特徴とする媒介デバイス(32)。
【請求項５４】
前記秘密鍵イメージyを受信するように設計されている通信手段(36)を備えることを特徴とする請求項５３に記載の媒介デバイス(32)。
【請求項５５】
計算手段(39)は、その指数が秘密鍵イメージyである前記公開鍵に含まれる第２の整数gの、nを法とする累乗を計算することによりプルーフYの第２の要素を生成するように設計されていることを特徴とする請求項５４に記載の媒介デバイス(32)。
【請求項５６】
秘密鍵の第１の部分イメージy'、第１のコンポーネントY'、およびプルーフの第２の要素の第２のコンポーネントg'を受信するように設計されている通信手段(36)を備え、計算手段(39)は、第２の部分イメージy"を指数とする第２のコンポーネントg'の累乗を第１のコンポーネントY'に掛けることにより、プルーフYの第２の要素を生成するように設計されていることを特徴とする請求項５３に記載の媒介デバイス(32)。
【請求項５７】
通信手段(36)は、プルーフYの第２の要素を検証者デバイスに伝送するように設計されていることを特徴とする請求項５５または５６のいずれか一項に記載の媒介デバイス(32)。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
特に、暗号法を使用して第１のエンティティと第２のエンティティとの間の対話を認証する場合、第２のステップは、第１のエンティティから受け取ったプルーフの第１の要素に関して、セキュリティ間隔における少なくとも１つの共通数を選択し前記共通数を第１のエンティティに送る第２のエンティティにより実行される。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００４９
【補正方法】変更
【補正の内容】
【００４９】
第６の他の実施形態によれば、公開鍵が特に証明者デバイス内で素数が秘密にされる法nを含む場合、計算手段は、中国の剰余定理と呼ばれる手法を使用することにより累乗を計算するように設計される。証明者デバイスは、公開鍵がプルーフxの第１の要素のk個のあらかじめ計算された値を含む場合に改善され、計算手段は、繰り返し毎にプルーフの第１の要素の異なる値で各実行をk回繰り返すように設計される。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００５７
【補正方法】変更
【補正の内容】
【００５７】
秘密鍵が複数の秘密数s1、s2などを含む場合、計算手段は、プルーフxの第１の要素について、同じ数の共通数c1、c2などを選択するように設計されており、計算手段は、以下の等式を使って、同じ数の第４の公開鍵整数v1、v2などによる一致を検証するように設計されている。
Yev1c2V2c2...=x modulo n
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０１２６
【補正方法】変更
【補正の内容】
【０１２６】
図５を参照すると、第１のステップ1で、エンティティAは、sよりもかなり大きな第１の乱数rを生成し、ステップ9のようにx=Gr(mod n)を計算する。こうして生成されたプルーフxの第１の要素は、プルーフを検証するためエンティティAとBとの間の対話を認証することは不要なので、エンティティBに送信する必要はない。
【国際調査報告】
2005513564.tif 000016
2005513564.tif 000017
2005513564.tif 000018
2005513564.tif 000019