説明

パラメータ生成装置、鍵共有システム、公開鍵暗号システム、電子署名システム、送付鍵生成装置、第1の鍵共有装置、第2の鍵共有装置、暗号化装置、復号化装置、署名装置、認証装置、パラメータ生成方法、送付鍵生成方法、鍵共有方法、暗号化方法、復号化方法、鍵対生成方法、署名方法、認証方法及びプログラム

【課題】2剰余環Z/NZ(但し、N=2、wは3以上の整数)上でd次のチェビシェフ多項式T(x)を考えることにより構成される次数決定問題(但し、当該次数決定問題とは、パラメータNとパラメータxと(但し、xとNは整数、0≦x<N)と整数y(但し、0≦y<N)とから、y=T(x)modNを満たす正の整数dを求める問題とする。)を解くことを困難にするパラメータxを生成する。
【解決手段】次数決定問題のパラメータNと適切に設定した所定値と用いて、q=x−1 modNで定義される整数qが因数4の個数を前記所定値以上有するという条件を満たすパラメータxを計算して生成する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、パラメータ生成装置、鍵共有システム、公開鍵暗号システム、電子署名システム、送付鍵生成装置、第1の鍵共有装置、第2の鍵共有装置、暗号化装置、復号化装置、署名装置、認証装置、パラメータ生成方法、送付鍵生成方法、鍵共有方法、暗号化方法、復号化方法、鍵対生成方法、署名方法、認証方法及びプログラムに関するものである。
【背景技術】
【0002】
公開鍵暗号は、今日の情報化社会において、認証、決済等に欠かせない基幹技術の1つになっている。但し、現在主流の公開鍵暗号方式であるRSA暗号方式やElGamal暗号方式をコンピュータ上で動作させる場合、そのメッセージの暗号化や復号化には、対称鍵暗号方式の100倍程度の時間を要し、長いメッセージを交換する事は実質的に不可能である。また、携帯電話等に用いられるような計算速度の低いCPUを用いた装置では、公開鍵暗号をソフトウェアとして使用することができない。
【0003】
そこで、楕円曲線の理論を利用してElGamal暗号方式を高速化した楕円曲線暗号方式の研究が進んでいる。この楕円曲線暗号方式を利用することにより、メッセージを暗号化したり、暗号化されたメッセージを復号化したりする処理速度は、上述したRSA暗号方式やElGamal暗号方式を用いた公開鍵暗号方式の10倍から数十倍程度の高速にすることができる。しかし、この楕円曲線暗号方式においては、楕円曲線の選択がデリケートであり、また、この楕円曲線暗号方式を実装するのが困難であるという問題がある。
【0004】
ここでElGamal暗号方式とは、剰余環Z/NZ上の離散対数問題、つまり或る適当な正の整数N(通常は大きな素数)を法として,与えられた正の整数x(0≦x<N)と正の整数y(0≦y<N)から、
y=xmod N
を満たすdを求める問題が効率的に解けないことを利用した公開鍵暗号方式である。正の整数xと正の整数dから正の整数yを計算する事は容易であるため、一方向性が存在する。
【0005】
ElGamal暗号方式においては、大きな(2進数で1000桁以上の)素数Nを法とした剰余環を考えるため、この剰余計算に多大な計算時間を要する。もしこの剰余計算を高速化することが可能であれば、対称鍵暗号方式のように長いメッセージを交換できたり、携帯電話等に用いられるような計算速度の低いCPUを用いた装置においても公開鍵暗号をソフトウェアとして使用することができることが期待される。
【0006】
大きな整数による剰余を高速化する一つの方法として、剰余環Z/NZの法Nを2の羃とするという方法が挙げられる。この剰余環を2冪剰余環という。即ち、正の整数wについて、N=2での剰余計算を行うことにすれば、2進数を利用する通常のコンピュータの特性を上手く利用した高速化が可能である。剰余計算を受ける数をwビットの2進数として与えておけば、計算過程におけるwビットの固定長処理,すなわちwビットを超えた桁溢れの無視が自動的にN=2に関する剰余計算となるためである。
【0007】
しかしながら、2羃剰余環上の離散対数問題は、Pohlig−Hellman法により多項式時間で解かれてしまう事が知られており、公開鍵暗号方式に適用することができない。
【0008】
他方、チェビシェフ多項式の性質を利用した公開鍵暗号方式が、特許文献1及び非特許文献1において開示されている。上記の離散対数問題の困難性を安全性の根拠とするのがElGamal暗号方式であるが、この離散対数問題の困難性を剰余環上のチェビシェフ多項式の次数決定問題の困難性に置き換えるのである。
【0009】
ここで、チェビシェフ多項式とは、0以上の整数dに対して定義される、xについてd次の整数係数の多項式T(x)であって次を満たすものである。
(cosθ)=cos(dθ).
例えば、T(x)=1、T(x)=x、T(x)=2x−1である。
【0010】
そして、このチェビシェフ多項式には、
(T(x))=Tab(x)
という性質がある。
【0011】
特許文献1には、ガロア有限体上のチェビシェフ多項式に関する次数決定問題の困難性を利用した公開鍵暗号システム、非特許文献1及び2には、剰余環上のチェビシェフ多項式に関する次数決定問題の困難性を利用した公開鍵暗号システムに関する記載がある。
【0012】
ここで、剰余環上のチェビシェフ多項式に関する次数決定問題を説明する。Nを適当な正の整数、xとyとを0以上でN未満の整数として、次の式を考える。
y=T(x) mod N.
【0013】
上記の式において、既知のx、d及びΝから未知のyを計算する事は容易、言い換えれば、多項式時間で計算可能であることが知られている。しかし、x、y、Nを既知で、dを未知として、このx、y、Nからdを効率的に解くアルゴリズムは、現在までのところ知られていない。即ち、既知のx、y及びΝからdを計算する事は困難であるという一方向性を有する。
【0014】
チェビシェフ多項式の次数決定問題とは、適当な正の整数Νと、整数x及び整数y(0≦x,y<N)に対し、y=T(x) mod Nを満たすdを求める問題である。上述のように、この問題を適当なNに対し解くことは困難である。
【0015】
即ち、これらの文献は、ElGamal暗号方式における離散対数問題を、剰余環上のチェビシェフ多項式の次数決定問題に置き換えた公開鍵暗号方式に関するものである。これらの公開鍵暗号システムをプログラム化してコンピュータ等の計算機に実装する場合、ElGamal暗号方式における冪乗多項式xの計算の代わりに、チェビシェフ多項式T(x)を計算することになる。
【0016】
チェビシェフ多項式T(x)を用いた暗号方式は、楕円曲線暗号方式に比べるとプログラムの作成についてははるかに容易であるが、しかし、ElGamal暗号方式に比べると、暗号化や復号化に一般に多くの時間がかかり、またプログラムの作成も若干面倒となる。
【0017】
実際、特許文献1の公開鍵暗号システムは、チェビシェフ多項式の計算に時間を要し、ElGamal暗号方式に比べ、10倍前後低速である。
【0018】
非特許文献1では、公開鍵暗号システムの1つである鍵交換システムが開示されている。これはDiffie−Hellman鍵交換法を基にしたものであり、2羃剰余環を利用して、特許文献1に記載の鍵交換システムの高速化を図ったものである。
【0019】
非特許文献1で説明された鍵交換法は、以下の通りである。この鍵交換法の説明では、この鍵交換法を用いて鍵を交換する者を甲及び乙とする。そして、N=2(但し、wは3以上の整数)とする。
(1)甲と乙は,正の整数x(1<x<N)をとり、xとNをシステムの共通パラメータとして公開する。
(2)甲は、正の奇数sを秘密鍵とする。そして、T=T(x) mod Nを求めて、Tを乙に配送する。
(3)乙は、正の奇数tを秘密鍵とする。そして、U=T(x) mod Nを求め、Uを甲に配送する。
(4)甲は、V = T(U) mod Nを共有鍵とする。乙は、V’=T(T) mod Nを共有鍵とする。
この鍵交換法では、(4)で示したVとV’はV=V’となるので、甲と乙は共通鍵を持つことができる。
【0020】
2羃剰余環以外の通常の剰余環では、計算の多くが剰余計算に占められているが、非特許文献1の鍵交換システムが利用している2羃剰余環では、2進数表現の装置上で或るビット以上の桁上がりを無視することがそのまま剰余計算となる上に、計算の際、一時的な桁数の倍加も発生しないので、コンピュータのハードウェア資源が著しく効率的に使用され、高速化が可能になる。
【0021】
しかしながら、非特許文献1の鍵交換システムにおいては、暗号鍵生成のパラメータが偶数である場合に、Pohlig−Hellman法の直接的な応用により、秘密鍵が多項式時間で容易に解読できてしまうという致命的な問題点が、つまり、xが偶数の場合には、Nとxを利用することで、Tからs、そしてUからtを多項式時間で計算する方法が、非特許文献2で開示されている。
【0022】
このように、暗号化・復号化の処理が高速で、暗号システム等をプログラム化してコンピュータ等の計算機に実装することが容易で、かつ、暗号解読が困難という3つの要件を満たす公開鍵暗号システムの研究は様々に進められているが、上述したように、問題を抱えている。
【特許文献1】特開2003−8564号公報
【非特許文献1】Ken Umeno、"Key Exchange byChebyshev Polynomials Modulo 2w、INA-CISC-2005、(インドネシア)、2005年3月、pp.95-97
【非特許文献2】石井雅治、吉本明宣、「2冪剰余環の既約剰余類群の構造とその応用」、椙山女学園大学現代マネジメント学部ディスカッションペーパー、2007年、No.12 Dec. pp.1-9
【発明の開示】
【発明が解決しようとする課題】
【0023】
現在、一般に公開鍵暗号システムや電子署名システムをコンピュータ上のプログラムとして動作させる際、2進数で1000桁以上の整数を法とする剰余計算が必要となる。
【0024】
この剰余計算は、加算や乗算に比べ少なくとも数倍の計算コストがかかり、これが公開鍵暗号システムや電子認証システムの律速過程となっている。もし、この剰余計算を高速に行うことが可能ならば、暗号システムや電子認証を大幅に高速化することができる。
【0025】
ところで、現代のコンピュータのほとんどが、2進数に基づく計算を行っている。従って、上で述べたように、正の整数wについて、N=2を法とする剰余計算を行う場合、高速化が可能である。即ち、剰余計算を受ける数をwビットの2進数として与えておけば、計算過程におけるwビットの固定長処理、即ちwビットを超えた桁溢れの無視が自動的にN=2に関する剰余計算となる。
【0026】
しかし、Nを上記のように2の冪乗とすると、問題が生じる場合がある。RSA暗号方式はその定義によりΝは大きな素数2つの積(N=pq,p及びqは2進数500桁程度以上の素数)でなければならないので、そもそもNを2の冪乗には出来ない。また、ElGamal暗号方式の場合、Pohlig−Hellman法により離散対数問題が多項式時間で解けてしまうため、暗号としての安全性に欠ける。
【0027】
また、チェビシェフ多項式の次数決定問題を利用する手法が考えられるが、この手法においても、剰余の法Νを2の冪乗とした場合には、上述したように、共通パラメータ(xとN)のひとつであるxが偶数である場合に多項式時間で解けてしまうことが、非特許文献2に示されている。
【0028】
そこで、本発明の目的は、上記の問題点、特に非特許文献2の問題点を鑑みたものであって、2羃剰余環上のチェビシェフ多項式に関する次数決定問題を解くことを困難とするようなパラメータを高速に生成するシステム、方法及びプログラムを提供することにある。
【0029】
また、本発明の目的は、このパラメータを利用した鍵共有システム、公開鍵暗号システム、電子署名システム、送付鍵生成装置、第1の鍵共有装置、第2の鍵共有装置、暗号化装置、復号化装置、署名装置、認証装置、パラメータ生成方法、送付鍵生成方法、鍵共有方法、暗号化方法、復号化方法、鍵対生成方法、署名方法、認証方法及びこれらのプログラムを提供することにある。
【課題を解決するための手段】
【0030】
本発明では、法Nを2(但し、wは3以上の整数)とした2冪剰余環Z/NZで考えられたd次のチェビシェフ多項式に関する次数決定問題のパラメータxとして適切な奇数を選ぶことによって、上記課題を解決するものである。ここで、パラメータxを奇数としたのは、上述したように、偶数の場合には2羃剰余環上のチェビシェフ多項式に関する次数決定問題を解けてしまうからである。
【0031】
即ち、本発明のパラメータ生成装置は、2冪剰余環上でd次のチェビシェフ多項式T(x)を考えることにより構成される次数決定問題を解くことを困難にするパラメータxを生成する生成装置である。
【0032】
但し、当該次数決定問題とは、パラメータNとパラメータxと(但し、xとNは整数、0≦x<N)と整数y(但し、0≦y<N)とから、y=T(x) mod Nを満たす正の整数dを求める問題である。
【0033】
ここで、剰余環Z/NZ上で考えるとは、整数及びその演算結果をすべてNで割った余りで同一視して考えるという意味である。本明細書では、整数PをQで割った正の余りを、2項演算子modにより、P
mod Qで表す。modの結合強度は四則演算や冪より弱いものとする。例えばN=256の場合、剰余環Z/NZは2冪剰余環であり、0以上255以下の整数のみからなり、256は0と、また、257は1と置き換えられる。これを数式では、
256 mod 256 = 0
257 mod 256 = 1
等と表現する。剰余環上では加算と乗算が定義される。例えば、
100 + 200 mod 256 = 300 mod 256 = 44
3 × 200 mod 256 = 600 mod 256 = 88
等となる。
【0034】
2冪剰余環上でのチェビシェフ多項式の計算も全く同様であり、チェビシェフ多項式
(x)=2x−1
について、N=256(=2)としたとき、例えばx=30に対し、
(30) mod 256 = 2×30−1 mod 256 = 2×900−1 mod 256 = 1800−1 mod 256 = 7
となる。
【0035】
なお上記の計算は、最後にmod 256としたが、計算途中においてmod 256を行っても計算結果は同じとなる。即ち、
2×30−1 mod 256 = 2×900−1 mod 256 = 2×132−1
mod 256 = 264−1 mod 256 = 7
である。ここで900 mod 256=132を用いた。
【0036】
2冪剰余環において、すべての数をwビットの固定長2進数として表現することが好ましい。何故なら、演算を行った結果がwビット以内で納まる場合はもちろん問題ないが、結果がwビットで納まらない場合、上位桁へ溢れる値を無視する事が2冪剰余環Z/NZ上で考える事と一致するからである。
【0037】
これをもう少し詳しく説明する。例えばw=8とし、すべての数は最大8ビットの2進数として表現するとする。このとき、上記の例と同じくN=256なる。また、(**…*)(ただし*は0か1)で2進数を表現する。100=(1100100)、200=(11001000)であり、
100+200=(1100100)+(11001000)=(100101100)
と9ビットの2進数となるが、この9ビット目を無視した2進数(00101100)は、100+200 mod 256の解である44と等しい。これは2進数(100000000)が256に等しく、mod 256という演算、即ち2冪剰余環Z/NZの性質が2進数のある桁数以上を無視することと同値である、という事実の帰結である。
【0038】
一般に、剰余環上における計算を行う場合、剰余を行う処理が最も計算時間がかかるが、本発明においては2羃剰余環に限定するので、wビットの2進数を用いることにより、剰余処理は実質的に何もしない事と等価となる。
【0039】
更に、一般の2羃でない剰余環を用いて乗算を行う場合、一時的に桁数が増加するため、必要なビット数(扱う最大数を格納するために必要なビット数)の倍のビット数を準備する必要があるが、2羃剰余環の場合、各2項演算又は単項演算ごとに溢れた桁を無視する事により剰余処理が行われるため、桁数の一時的増加も考える必要がない。
【0040】
このように2羃剰余環を用いる事は、コンピュータのハードウェア特性を活かし、かつ高速な剰余計算が実現される。このことは、通常の(2羃でない)剰余環上で行う計算に比べ、大幅な処理速度の向上が期待される。
【0041】
本発明に係るパラメータ生成装置は、2冪剰余環Z/NZ上でチェビシェフ多項式Tを考えるときに、その次数決定問題を解くことを困難にするパラメータxを生成する生成装置であって、パラメータN格納部と、第1の所定値格納部と、計算部と、出力部と、を有し、以下のように構成する。
【0042】
パラメータN格納部は、次数決定問題のパラメータNを格納する。ここでN=2であるから、必ずしもN自体の数値を格納するのではなく、代替的にwの数値を格納することができる。即ち、パラメータNは2で定義されるのであり、2進数で処理される計算システムでは、wが決まれば計算長がwビットに決まることになる。
【0043】
第1の所定値格納部は、予め設定した第1の所定値を格納する。
【0044】
計算部は、パラメータN格納部に格納されたパラメータNと第1所定値格納部に格納された第1の所定値とを読み出して、
q=x−1 mod N
で定義される整数qが因数4の個数を第1の所定値以上有するという第1の条件を満たすパラメータxを計算して生成する。
【0045】
このように計算されたパラメータxは、qが偶数であり、パラメータNも偶数であることから、必ず奇数となる。
【0046】
ここで第1の条件は、非特許文献2で開示されている、2羃剰余環上のチェビシェフ多項式の次数決定問題を、Pohlig−Hellman法により多項式時間で解く方法の適用を困難とする条件である。即ち、Pohlig−Hellman法の適用には、2羃剰余環上でx−1の平方根の計算が不可欠であるが、上記の整数q=x−1 mod Nが因数4を多数持つ事によりx−1の平方根に多数の分岐が生じ、現在のところ、計算に非常に長時間を必要とする。つまり、次数決定問題を解く事が困難となるのである。
【0047】
上記の分岐が多数になるほど次数決定問題を解く事は困難となるため、第1の所定値は、出来る限り大きく設定する事が望ましい。但し、余り大きくしすぎると、計算部の処理時間が長くなるという状況や、場合によっては第1の条件を満たすパラメータxが全く存在しないという状況も起こり得る。従って、パラメータNに応じて適切な値を設定すればよい。
【0048】
出力部は、計算部において生成されたパラメータxを少なくとも出力する。ここで、「少なくとも」としたのは、出力部はパラメータxを出力するが、それ以外の数値も出力するように構成することができるという趣旨である。
【0049】
従って、出力部は、必要に応じて、パラメータNも出力することができるように構成することができる。
【0050】
また本発明のパラメータ生成装置は、予め設定した第2の所定値を格納する第2の所定値格納部を更に有し、計算部が更に以下の条件を満たすようなパラメータxを生成する事が好ましい。
【0051】
即ち、計算部は、パラメータN格納部に格納されたパラメータNと第1所定値格納部に格納された第1の所定値と第2の所定値格納部に格納された第2の所定値とを読み出して、上記の第1の条件と、更に、次数が2−1であるチェビシェフ多項式T−1(x)について、x=T−1(x) mod Nを満たす2以上の最小の整数eが第2の所定値以上であるという第2の条件を満たすパラメータxを計算して生成する。
【0052】
ここで第2の所定値が大きいほど、2羃剰余環上のチェビシェフ多項式の次数決定問題は、総当たり法による攻撃に対する強度が上がる。総当たり法とは、既知のパラメータxとパラメータNから、
(x) mod N
(x) mod N
(x) mod N

を逐次計算し、初めてy=T(x) mod Nとなるdを次数決定問題の解として得る手法である。この解は、時間さえかければ必ず見付けることができる。次数dは、チェビシェフ多項式の周期性により、2−1以下にしかとれないので、eが小さい場合には、このような総当たり法により簡単に次数決定問題が解かれてしまうのである。
【0053】
よって、第2の所定値も、出来る限り大きく設定する事が望ましい。但し、余り大きくしすぎると、計算部の処理時間が長くなるという状況や、場合によっては第2の条件を満たすパラメータxが全く存在しないという状況も起こり得る。従って、パラメータNに応じて適切な値を設定すればよい。
【0054】
2羃剰余環上のチェビシェフ多項式において、3つの条件
(1)x=T−1(x) mod N
(2)1=T(x) mod N
(3)x=T+1(x) mod N
は互いに同値である。従って、上記の第2の条件「x=T−1(x) mod Nを満たす2以上の最小の整数eが第2の所定値以上である」は、「1=T(x) mod Nを満たす2以上の最小の整数eが第2の所定値以上である」及び「x=T+1(x) mod Nを満たす2以上の最小の整数eが第2の所定値以上である」と同値である。つまり、このように第2の条件が書き換えられても、本発明の技術的範囲に含まれる。
【0055】
本発明の他の観点に係るパラメータ生成方法は、コンピュータ又は専用計算装置で実行され、2冪剰余環Z/NZ(但し、N=2、wは3以上の整数)上でd次のチェビシェフ多項式T(x)を考えることにより構成される次数決定問題を解くことを困難にするパラメータxを生成する生成方法であって、読み出し工程と、計算工程と、出力工程と、を備え、以下のように構成する。
【0056】
なお、方法の発明に関し、対応する装置と同様な数学的根拠の詳細な説明については省略する。
【0057】
読み出し工程は、コンピュータ又は専用計算装置に格納されたパラメータNと第1の所定値とを読み出す。
【0058】
計算工程は、q=x−1 mod Nで定義される整数qが因数4の個数を前記第1の所定値以上有するという第1の条件を満たすパラメータxを計算して生成する。
【0059】
このように計算されたパラメータxは、上述したように、qが偶数であり、パラメータNも偶数であることから、必ず奇数となる。また、第1の所定値は、出来る限り大きく設定されている事が望ましい。但し、余り大きくしすぎると、計算工程の処理時間が長くなるという状況や、場合によっては第1の条件を満たすパラメータxが全く存在しないという状況も起こり得る。従って、パラメータNに応じて適切な値を設定すればよい。
【0060】
出力工程は、計算工程において生成された前記パラメータxを少なくとも出力する。ここで、「少なくとも」としたのは、出力部はパラメータxを出力するが、それ以外の数値も出力するように構成してもよいという趣旨である。
【0061】
ここで出力工程は、必要に応じて、パラメータNも出力することができるように構成することができる。
【0062】
また本発明のパラメータ生成方法は、読み出し工程はコンピュータ又は専用計算装置に格納された第2の所定値を更に読み出し、計算工程が更に以下の条件を満たすようなパラメータxを生成する事が好ましい。
【0063】
即ち、計算工程は、第1の条件と、更に、x=T−1(x) mod Nを満たす2以上の最小の整数eが前記第2の所定値以上であるという第2の条件を満たすパラメータxを計算して生成する。
【0064】
ここにおいても、第2の所定値は、出来る限り大きく設定されている事が望ましい。但し、余り大きくしすぎると、計算工程の処理時間が長くなるという状況や、場合によっては第2の条件を満たすパラメータxが全く存在しないという状況も起こり得る。従って、パラメータNに応じて適切な値を設定すればよい。
【0065】
上述のパラメータ生成装置、パラメータ生成方法において、生成されたパラメータxは、2冪剰余環上で考えられたチェビシェフ多項式の次数決定問題を解くことを困難にするパラメータである。従って、この生成されたパラメータxを、2冪剰余環を利用した鍵共有システムやその方法、公開鍵暗号システムやその方法、電子認証システムやその方法等に用いた場合には、システムや方法をプログラム化してコンピュータ等の計算機に実装することが容易にでき、かつ、解くことが困難なので外部からの攻撃に強く、システムや方法における演算の処理を高速にすることができる。
【0066】
本発明の他の観点に係る鍵共有システムは、上記のパラメータ生成装置のいずれか又はパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNを用いた鍵共有システムであって、送付鍵生成装置と、第1の鍵共有装置と、第2の鍵共有装置とを備え、以下のように構成する。
【0067】
なお、ここで「上記のパラメータ生成装置のいずれか又はパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNを用いた」としたのは、ここで用いられるパラメータxは、あくまでも、上記のパラメータ生成装置のいずれか又はパラメータ生成方法のいずれかによって生成されたパラメータxに限定する趣旨であり、パラメータNは、この生成されたパラメータxに対応するパラメータN、つまり、このパラメータxを生成する際に用いたパラメータNを意味する。以下の同様の記載においても、同様に解すべきである。
【0068】
以下では、整数を取得する整数取得部又は整数取得工程について記載されるが、これは乱数を発生させる、日付と時刻のハッシュ関数値を用いる、等、動作の度に異なる整数値を発生させる装置又は工程によって構成することができる。
【0069】
送付鍵生成装置は、整数取得部と、送付鍵計算部と、第1送付鍵出力部と、第2送付鍵出力部とを備え、以下のように構成する。
【0070】
整数取得部は正の整数sを取得する。
【0071】
送付鍵計算部は、パラメータxとパラメータNと取得した整数sとから
T=T(x) mod N
により送付鍵Tを計算する。
【0072】
第1送付鍵出力部は、計算された送付鍵Tを第1の鍵共有装置に出力する。
【0073】
第2送付鍵出力部は、整数sを送付鍵として第2の鍵共有装置に出力する。
【0074】
また、第1の鍵共有装置は、整数取得部と、送付鍵計算部と、送付鍵出力部と、送付鍵入力部と、共有鍵計算部とを備え、以下のように構成する。
【0075】
整数取得部は、正の整数tを取得する。
【0076】
送付鍵計算部は、整数tとパラメータxとパラメータNとから
U=T(x) mod N
により送付鍵Uを計算する。
【0077】
送付鍵出力部は、計算された送付鍵Uを第2の鍵共有装置に出力する。
【0078】
送付鍵入力部は、送付鍵生成装置が出力した送付鍵Tを入力する。
【0079】
共有鍵計算部は、入力された送付鍵Tから
V’=T(T) mod N
により共有鍵V’を計算する。
【0080】
さらに第2の鍵共有装置は、第1送付鍵入力部と、第2送付鍵入力部と、共有鍵計算部とを備え、以下のように構成する。
【0081】
第1送付鍵入力部は、第1の鍵共有装置が出力した送付鍵Uを入力する。
【0082】
第2送付鍵入力部は、送付鍵生成装置が送付鍵として出力した整数sを入力する。
【0083】
共有鍵計算部は、パラメータNと整数sと送付鍵Uとから
V=T(U) mod N
により共有鍵Vを計算する。
【0084】
ここで、チェビシェフ多項式の性質より、
V=T(T(x)) mod N=Tst(x)mod N
及び、
V’=T(T(x)) mod N=Tst(x) mod N
となることから、V=V’が成立する。即ち、V(=V’)が共有鍵として、第1の鍵共有装置及び第2の鍵共有装置に共有される。
【0085】
この鍵共有システムにおいて、送付鍵T、送付鍵U、パラメータx及びパラメータNのみから共有鍵Vを得る事は容易でない。なぜなら、T=T(x) mod N、U=T(x) mod Nに基づいて、整数sと整数tを求める次数決定問題は、パラメータxの性質によって容易に解く事が出来ず、また共有鍵Vは整数sと整数tなしには計算出来ないからである。
【0086】
またこの鍵共有システムは、2羃剰余環における演算を用いて構成されているため、2進数を用いた計算を行う装置を用いた場合、非常に高速に動作し、また作成も容易である。
【0087】
なお、送付鍵生成装置の整数取得部で取得される整数s、また、第1の鍵共有装置の整数取得部で取得される整数tは、奇数である事が望ましい。このとき、異なるパラメータxに対し異なる送付鍵U及びVが生成できる確率が高まる。
【0088】
本発明の鍵共有システムは、以下のように構成することにより、公開鍵暗号システムとすることができる。
【0089】
上記の通り、共有鍵Vと共有鍵V’は等しく、かつ、第三者は容易に得る事が出来ない。従って、この共有鍵V(=V’)を対称鍵暗号方式の対称鍵として用いる事が出来る。
【0090】
即ち、本第1の公開鍵暗号システムは、送付鍵生成装置と、第1の鍵共有装置と、第2の鍵共有装置を備え、以下のように構成する。
【0091】
第1の鍵共有装置は、更に、暗号化部と暗号化メッセージ送信部とを備える。
【0092】
暗号化部は、平文のメッセージを共有鍵V’により暗号化して暗号化メッセージを得る。
【0093】
暗号化メッセージ送信部は、第2の鍵共有装置に暗号化メッセージを送信する。
【0094】
第2の鍵共有装置は、更に、暗号化メッセージ受信部と復号化部とを備え、以下のように構成する。
【0095】
暗号化メッセージ受信部は、第1の鍵共有装置が送信した暗号化メッセージを受信する。
【0096】
復号化部は、受信された暗号化メッセージを共有鍵Vにより復号化して、平文のメッセージを得る。
【0097】
本発明の他の観点に係る第2の公開鍵暗号システムは、上記のパラメータ生成装置のいずれか又はパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた公開鍵暗号システムであって、鍵対生成装置と、暗号化装置と、復号化装置とを備え、以下のように構成する。
【0098】
鍵対生成装置は、整数取得部と、公開鍵計算部と、公開鍵公開部と、秘密鍵出力部と、を備え、以下のように構成する。
【0099】
整数取得部は、正の奇数である整数sを取得する。
【0100】
公開鍵計算部は、取得した整数sとパラメータxとパラメータNとから、
T=T(x) mod N
により公開鍵Tを計算する。
【0101】
公開鍵公開部は、計算された公開鍵Tを暗号化装置に公開する。
【0102】
秘密鍵出力部は、整数sを秘密鍵として復号化装置に出力する。
【0103】
また暗号化装置は、公開鍵受付部と、整数取得部と、暗号化部と、暗号化メッセージ送信部と、を備え、以下のように構成する。
【0104】
公開鍵受付部は、鍵対生成装置が公開した公開鍵Tを受け付ける。
【0105】
整数取得部は、正の奇数である整数rを取得する。
【0106】
暗号化部は、奇数であるメッセージm(0<m<N)と取得した整数rとパラメータxとパラメータNとから、
=T(x) mod N
=mT(T) mod N
により整数の組である暗号化メッセージ(c,c)を計算する。
【0107】
暗号化メッセージ送信部は、暗号化メッセージ(c,c)を復号化装置へ送信する。
【0108】
一方、復号化装置は、暗号化メッセージ受信部と、秘密鍵入力部と、中間整数計算部と、復号化部と、を備え、以下のように構成する。
【0109】
暗号化メッセージ受信部は、暗号化装置が送信した暗号化メッセージ(c,c)を受信する。
【0110】
秘密鍵入力部は、鍵対生成装置が秘密鍵として出力した整数sを入力する。
【0111】
中間整数計算部は、入力された整数sと受信された暗号化メッセージ(c,c)の第1成分cとパラメータNとから、
1=αT(c) mod N
を満たす中間整数αを求める。
【0112】
ここで、パラメータx、整数s、整数tがいずれも奇数であることから、
(c)=T(T(x))mod N
も奇数となり、この中間整数αは必ず存在し、拡張ユークリッドの互除法やフェルマーの小定理よる適当な冪乗を用いれば高速に計算することができる。
【0113】
復号化部は、受信された暗号化メッセージ(c,c)の第2成分cと中間整数αとパラメータNとから
m’=αc mod N
によりメッセージm’を得る。
【0114】
このメッセージm’は、暗号化装置が送信した元のメッセージmと等しい。
【0115】
本第2の公開鍵暗号システムにおいて、公開鍵T、パラメータx及びパラメータNのみを用いて暗号化メッセージ(c,c)から元のメッセージmを得る事は容易でない。なぜなら、復号化においてT(c)を計算する必要があり、この秘密鍵sは次数決定問題の困難性により容易に計算できないからである。
【0116】
また本第2の公開鍵暗号システムは、すべての計算を2羃剰余環上で行うため、2進数を用いた計算を行う装置を用いた場合、非常に高速に動作し、また作成も容易である。
【0117】
本発明の他の観点に係る第3の公開鍵暗号システムは、上記のパラメータ生成装置のいずれか又はパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた公開鍵暗号システムであって、鍵対生成装置と暗号化装置と復号化装置とを備え、以下のように構成する。
【0118】
鍵対生成装置は、整数取得部と、公開鍵計算部と、公開鍵公開部と、秘密鍵出力部と、を備え、以下のように構成する。
【0119】
整数取得部は、正の整数sを取得する。
【0120】
公開鍵計算部は、整数sとパラメータxとパラメータNとから、
T=T(x) mod N
により公開鍵Tを計算する。
【0121】
公開鍵公開部は、計算された公開鍵Tを暗号化装置に公開する。
【0122】
秘密鍵出力部は、整数sを秘密鍵として復号化装置に出力する。
【0123】
一方、暗号化装置は、公開鍵受付部と、整数取得部と、暗号化部と、暗号化メッセージ送信部と、を備え、以下のように構成する。
【0124】
公開鍵受付部は、鍵対生成装置が公開した公開鍵Tを受け付ける。
【0125】
整数取得部は、正の整数rを取得する。
【0126】
暗号化部は、整数であるメッセージm(0≦m<N)と整数rとパラメータxとパラメータNとから
=T(x) mod N
=(T(T) mod N) xor m
により整数の組である暗号化メッセージ(c,c)を計算する。
【0127】
但し、A xor Bは、2進数AとBのビット毎の排他的論理和演算を表わす。例えば、A=01100101,B=10110110である時、A xor B=11010011となる。
【0128】
暗号化メッセージ送信部は、暗号化メッセージ(c,c)を復号化装置へ送信する。
【0129】
更に復号化装置は、暗号化メッセージ受信部と、秘密鍵入力部と、復号化部と、を備え、以下のように構成する。
【0130】
暗号化メッセージ受信部は、暗号化装置が送信した暗号化メッセージ(c,c)を受信する。
【0131】
秘密鍵入力部は、鍵対生成装置が秘密鍵として出力した整数sを入力する。
【0132】
復号化部は、入力された整数sと受信された暗号化メッセージ(c,c)とパラメータNとから
m’=(T(c) mod N) xor c
によりメッセージm’を得る。
【0133】
このメッセージm’は、暗号化装置の送信したメッセージmに等しい。
【0134】
本第3の公開鍵暗号システムにおいて、公開鍵T、パラメータx及びパラメータNのみを用いて暗号化メッセージ(c,c)から元のメッセージmを得る事は容易でない。なぜなら、復号化においてT(c)を計算する必要があり、この秘密鍵sは次数決定問題の困難性により容易に計算できないからである。
【0135】
また本第3の公開鍵暗号システムは、すべての計算を2羃剰余環上で行うため、2進数を用いた計算を行う装置を用いた場合、非常に高速に動作し、また作成も容易である。
【0136】
鍵対生成装置の整数取得部で取得される整数s、また、暗号化装置の生成取得部で取得される整数rは奇数であることが望ましい。このとき、非特許文献1において初めて示されたように、2羃剰余環上でチェビシェフ多項式T及びTが全単射となるためである。ただし両者が奇数の場合、2羃剰余環上でT(T)=T(c)も奇数となるため、最下位ビットを解読されてしまう。これを避けるには、メッセージmの最下位ビットには情報を与えず定数(0でも1でもよい)とし、復号化されたメッセージm’の最下位ビットを無視すればよい。
【0137】
本発明の他の観点に係る電子署名システムは、上記のパラメータ生成装置のいずれか又はパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた電子署名システムであって、鍵対生成装置と、署名装置と、認証装置とを備え、以下のように構成する。
【0138】
鍵対生成装置は、整数取得部と、公開鍵計算部と、公開鍵公開部と、秘密鍵出力部と、を備え、以下のように構成する。
【0139】
整数取得部は、正の整数sを取得する。
【0140】
公開鍵計算部は、整数sとパラメータxとパラメータNとから、
T=T(x) mod N
により公開鍵Tを計算する。
【0141】
公開鍵公開部は、計算された公開鍵Tを認証装置に公開する。
【0142】
秘密鍵出力部は、整数sを秘密鍵として署名装置に出力する。
【0143】
一方、署名装置は、整数発生部と、秘密鍵入力部と、署名部と、署名付メッセージ送信部と、を備え、以下のように構成する。
【0144】
整数発生部は、整数Mを2の倍数であってN以下のものとし、Mと互いに素な正の整数kと、整数kから1
= k’k mod Mを満たす正の整数k’を発生させる。但し、eは、x=T−1(x) mod Nを満たす2以上の最小の整数とする。整数Mと整数kが互いに素であるため、この正の整数k’は必ず存在し、拡張ユークリッドの互除法等を用いる事により高速に計算できる。
【0145】
秘密鍵入力部は、鍵対生成装置が秘密鍵として出力した整数sを入力する。
【0146】
署名部は、パラメータxとパラメータNと整数sと整数であるメッセージm(0≦m<N)とから、
a=T(x) mod N
b=k’(sa+h(m)) mod M
により署名付メッセージ(a,b,m)を計算する。但し、h(m)は正の整数であって、メッセージm自身又はメッセージmのハッシュ関数値とする。
【0147】
メッセージmは、M以上の値となっても構わない。但し、0≦m<Mである方が異なるメッセージを同じであると認証する確率が減って望ましい。
【0148】
ここで関数hを恒等関数にとれば整数h(m)はメッセージm自身となる。そして、関数hをハッシュ関数にとれば、整数h(m)として、mのハッシュ値を用いることになる。存在的偽造不可能性に関する安全性を高めることができると期待されるため、hとしてはハッシュ関数を用いる事が望ましい。
【0149】
なお、ハッシュ関数hは、パラメータに依存するハッシュ関数を用いるのが更に望ましい。このことにより、存在的偽造不可能性に関する安全性を更に高めることができると期待される。このためには、署名装置の署名部で計算されたaを用い、ハッシュ関数hをパラメータ付きハッシュ関数hに置き換えればよい。
【0150】
署名付メッセージ送信部は、署名付メッセージ(a,b,m)を認証装置へ送信する。
【0151】
なお、この署名装置の整数発生部におけるMは、必ずしも2を使用して設定する必要はない。例えばM=N/4とすることができる(eは常にw−2以下となる)。但し、計算時間の短縮のために、Mは小さい方が望ましい。
【0152】
またMを2を利用して設定する場合で、かつ、パラメータ生成装置がeをx=T−1(x) mod Nを満たす2以上の最小の整数として発生させているとき又はパラメータ生成方法によりeがx=T−1(x) mod Nを満たす2以上の最小の整数として発生させられているときは、そのeを受け付け利用する事により、更に計算を高速化することができる。
【0153】
またMは、2の冪乗にとるのが望ましい。これは、署名装置として、2進数を用いた計算を行う装置を用いた場合、非常に高速に動作し、また作成も容易となるからである。
【0154】
更に、Mが2の冪乗である場合、整数kは単に正の奇数として選ぶことができる。
【0155】
上記整数k’は、拡張ユークリッドの互除法以外でも、フェルマーの小定理により、ある整数cを用いて、k’=k mod Mで高速に求めることができる。
【0156】
また認証装置は、公開鍵受付部と、署名付メッセージ受信部と、整数計算部と、認証部と、を備え、以下のように構成する。
【0157】
公開鍵受付部は、鍵対生成装置が公開した公開鍵Tを受け付ける。
【0158】
署名付メッセージ受信部は、署名装置が送信した署名付メッセージ(a,b,m)を受信する。
【0159】
整数計算部は、受け付けられた公開鍵Tと受信された署名付メッセージ(a,b,m)とパラメータxとパラメータNから、整数h(m)を設定し、整数Wを、
W=Th(m)(x)−2Th(m)(x)T(T)T(a)+T(T)+T(a)−1 mod Nにより計算する。
【0160】
認証部は、整数Wが0に等しい場合、署名付メッセージ(a,b,m)を認証する。
【0161】
本署名システムにおいて、公開鍵T、パラメータx及びパラメータNのみを用いて秘密鍵である整数sを計算することは困難である。このため署名付メッセージ(a,b,m)の第2成分bは秘密鍵である整数sを知っている署名装置によってしか作成できない。
【0162】
本発明の他の観点に係る送付鍵生成装置は、上記の鍵共有システムの送付鍵生成装置である。
【0163】
本発明の他の観点に係る第1の鍵共有装置は、上記の鍵共有システムの第1の鍵共有装置である。
【0164】
本発明の他の観点に係る第2の鍵共有装置は、上記の鍵共有システムの第2の鍵共有装置である。
【0165】
本発明の他の観点に係る第1の鍵共有装置は、上記の第1の公開鍵暗号システムの第1の鍵共有装置である。
【0166】
本発明の他の観点に係る第2の鍵共有装置は、上記の第1の公開鍵暗号システムの第2の鍵共有装置である。
【0167】
本発明の他の観点に係る暗号化装置は、上記の第2の公開鍵暗号システムの暗号化装置である。
【0168】
本発明の他の観点に係る復号化装置は、上記の第2の公開鍵暗号システムの復号化装置である。
【0169】
本発明の他の観点に係る署名装置は、上記の電子署名システムの署名装置である。
【0170】
本発明の他の観点に係る認証装置は、上記の電子署名システムの認証装置である。
【0171】
本発明の他の観点に係る送付鍵生成方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いて共有鍵を生成するのに必要な送付鍵Tを生成する方法であって、整数取得工程と、送付鍵計算工程と、を備え、以下のように構成する。
【0172】
整数取得工程は、正の整数sを取得する。
【0173】
送付鍵計算工程は、パラメータxとパラメータNと取得した整数sとから、
T=T(x) mod N
により送付鍵Tを計算する。
【0174】
本送付鍵生成方法は、2進数を用いて計算を行った場合、非常に高速に動作し、また、プログラム化も容易である。
【0175】
本発明の他の観点に係る第1の鍵共有方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた鍵共有方法であって、整数取得工程と、送付鍵計算工程と、送付鍵出力工程と、送付鍵入力工程と、共有鍵計算工程と、を備え、以下のように構成する。
【0176】
整数取得工程は、正の整数tを取得する。
【0177】
送付鍵計算工程は、整数tとパラメータxとパラメータNとから、
U=T(x) mod N
により送付鍵Uを計算する。
【0178】
送付鍵出力工程は、計算された送付鍵Uを他の鍵共有装置に出力する。
【0179】
送付鍵入力工程は、上記の送付鍵生成方法において生成され送付鍵Tを入力する。
【0180】
共有鍵計算工程は、入力された送付鍵Tから
V’=T(T) mod N
により共有鍵V’を計算する。
【0181】
本第1の鍵共有方法は、2進数を用いて計算を行った場合、非常に高速に動作し、プログラム化も容易である。
【0182】
本発明の他の観点に係る第2の鍵共有方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータxに対応したパラメータNを用いた鍵共有方法であって、第1送付鍵入力工程と、第2送付鍵入力工程と、共有鍵計算工程と、を備え、以下のように構成する。
【0183】
なお、ここでいう「パラメータxに対応したパラメータN」とは、生成されたパラメータxを対応するパラメータN、つまり、パラメータxを生成する際に用いたパラメータNをいう。以下においても同様である。
【0184】
第1送付鍵入力工程は、上記の第1の鍵共有方法において計算され送付鍵Uを入力する。
【0185】
第2送付鍵入力工程は、上記の送付鍵生成方法において取得され整数sを送付鍵として入力する。
【0186】
共有鍵計算工程は、パラメータNと整数sと送付鍵Uとから、
V=T(U) mod N
により共有鍵Vを計算する。
【0187】
ここで、チェビシェフ多項式の性質より、V=V’が成立する。即ち、V(=V’)が共有鍵として作成される。
【0188】
本第2の鍵共有方法は、2進数を用いて計算を行った場合、非常に高速に動作し、プログラム化も容易である。
【0189】
上記の第1の鍵共有方法と本第2の鍵共有方法を組み合わせて実施した場合において、送付鍵T、送付鍵U、パラメータx及びパラメータNのみから共有鍵V(=V’)を得る事は容易でない。
【0190】
なお、上記の送付鍵生成方法の整数取得工程で取得される整数s、また、第1の鍵共有方法の整数取得工程で取得される整数tは、奇数である事が望ましい。
【0191】
本発明の他の観点に係る第1の暗号化方法は、上記の第1の鍵共有方法を用いた暗号化方法であって、更に、平文のメッセージを共有鍵V’により暗号化して暗号化メッセージを得る暗号化工程を有することを特徴とする。
【0192】
本発明の他の観点に係る第1の復号化方法は、上記の第2の鍵共有方法を用いた復号化方法であって、更に、上記の第1の暗号化方法により暗号化された暗号化メッセージを共有鍵Vにより復号化して、上記の第1の暗号化方法で用いられた平文のメッセージを得る復号化工程を有することを特徴とする。
【0193】
本発明の他の観点に係る鍵対生成方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた鍵対生成方法であって、整数取得工程と、公開鍵計算工程と、公開鍵公開工程と、秘密鍵出力工程と、を備え、以下のように構成する。
【0194】
整数取得工程は、正の整数sを取得する。
【0195】
公開鍵計算工程は、取得した整数sとパラメータxとパラメータNとから、
T=T(x) mod N
により公開鍵Tを計算する。
【0196】
公開鍵公開工程は、計算された公開鍵Tを公開する。
【0197】
秘密鍵出力工程は、整数sを秘密鍵として出力する。
【0198】
本鍵対生成方法は、2進数を用いて計算を行った場合、非常に高速に動作し、またプログラム化も容易である。
【0199】
本発明の他の観点に係る第2の暗号化方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた暗号化方法であって、公開鍵受付工程と、整数取得工程と、暗号化工程と、を備え、以下のように構成する。
【0200】
公開鍵受付工程は、上記の鍵対生成方法で整数sを奇数としたものにおいて公開された公開鍵Tを受け付ける。
【0201】
整数取得工程は、正の奇数である整数rを取得する。
【0202】
暗号化工程は、奇数であるメッセージm(0<m<N)と取得した前記整数rと前記パラメータxと前記パラメータNとから、
=T(x) mod N
=mT(T) mod N
により整数の組である暗号化メッセージ(c,c)を計算する。
【0203】
本第2の暗号化方法は、2進数を用いて計算を行った場合、非常に高速に動作し、またプログラム化も容易である。
【0204】
本発明の他の観点に係る第2の復号化方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータxに対応したパラメータNを用いた復号化方法であって、暗号化メッセージ受信工程と、秘密鍵入力工程と、中間整数計算工程と、復号化工程と、を備え、以下のように構成する。
【0205】
暗号化メッセージ受信工程は、上記の第1の暗号化方法において計算された暗号化メッセージ(c,c)を受信する。
【0206】
秘密鍵入力工程は、上記の鍵対生成方法整数sを奇数としたものにおいて秘密鍵として出力された整数sを入力する。
【0207】
中間整数計算工程は、入力された整数sと受信された暗号化メッセージ(c,c)の第1成分cとパラメータNとから、
1=αT(c) mod N
を満たす中間整数αを求める。
【0208】
復号化工程は、受信された暗号化メッセージ(c,c)の第2成分cと中間整数αとパラメータNとから
m’=αc mod N
によりメッセージm’を得る。
【0209】
このメッセージm’は、上記の第2の暗号化装置の送信したメッセージmに等しい。
【0210】
上記の第2の暗号化方法と本第2の復号化方法を組み合わせて実施した場合において、公開鍵T、パラメータx及びパラメータNのみを用いて暗号化メッセージ(c,c)から元のメッセージmを得る事は容易でない。
【0211】
また、本第2の復号化方法は、2進数を用いて計算を行った場合、非常に高速に動作し、またプログラム化も容易である。
【0212】
本発明に係る第3の暗号化方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた暗号化方法であって、公開鍵受付工程と、整数取得工程と、暗号化工程と、を備え、以下のように構成する。
【0213】
公開鍵受付工程は、上記の鍵対生成方法において公開された公開鍵Tを受け付ける。
【0214】
整数取得工程は、正の整数rを取得する。
【0215】
暗号化工程は、整数であるメッセージm(0≦m<N)と整数rとパラメータxとパラメータNとから
=T(x) mod N
=(T(T) mod N) xor m
により整数の組である暗号化メッセージ(c,c)を計算する。
【0216】
本第3の暗号化方法は、2進数を用いて計算を行った場合、非常に高速に動作し、またプログラム化も容易である。
【0217】
本発明の他の観点に係る第3の復号化方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータxに対応したパラメータNとを用いた復号化方法であって、暗号化メッセージ受信工程と、秘密鍵入力工程と、復号化工程と、を備え、以下のように構成する。
【0218】
暗号化メッセージ受信工程は、上記の第3の暗号化方法において計算され暗号化メッセージ(c,c)を受信する。
【0219】
秘密鍵入力工程は、上記の鍵対生成方法において秘密鍵として出力され整数sを入力する。
【0220】
復号化工程は、入力された整数sと受信された暗号化メッセージ(c,c)とパラメータNとから、
m’=(T(c) mod N) xor c
によりメッセージm’を得る。
【0221】
このメッセージm’は、上記の第3の暗号化方法の送信したメッセージmに等しい。
【0222】
上記の第3の暗号化方法と本第3の復号化方法を組み合わせて実施した場合において、公開鍵T、パラメータx及びパラメータNのみを用いて暗号化メッセージ(c,c)から元のメッセージmを得る事は容易でない。
【0223】
また、本第3の復号化方法は、2進数を用いて計算を行った場合、非常に高速に動作し、またプログラム化も容易である。
【0224】
鍵対生成方法の整数取得工程で取得される整数s、また、暗号化方法の整数取得工程で取得される整数rは奇数であることが望ましい。このときは、メッセージmの最下位ビットには情報を与えず定数(0でも1でもよい)とし、復号化されたメッセージm’の最下位ビットを無視することが望ましい。
【0225】
本発明の他の観点に係る署名方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた署名方法であって、整数発生工程と、秘密鍵入力工程と、署名工程と、を備え、以下のように構成する。
【0226】
整数発生工程は、整数Mを2の倍数であってN以下のものとし、Mと互いに素な正の整数kと、前記整数kから1
= k’k mod Mを満たす正の整数k’を発生させる。但しeは、x=T−1(x) mod Nを満たす2以上の最小の整数である。整数Mと整数kが互いに素であるため、この正の整数k’は必ず存在し、拡張ユークリッドの互除法等を用いる事により高速に計算できる。
【0227】
秘密鍵入力工程は、上記の鍵対生成方法において秘密鍵として出力された整数sを入力する。
【0228】
署名工程は、パラメータxとパラメータNと整数sと整数であるメッセージm(0≦m<N)とから、
a=T(x) mod N
b=k’(sa+h(m)) mod M
により署名付メッセージ(a,b,m)を計算する。但し、h(m)は正の整数であって、m自身又はmのハッシュ関数値とする。
【0229】
メッセージmは、M以上の値となっても構わない。但し、0≦m<Mである方が異なるメッセージを同じであると認証する確率が減って望ましい。
【0230】
ここで関数hを恒等関数にとれば整数h(m)はメッセージm自身となる。そして、関数hをハッシュ関数にとれば、整数h(m)として、mのハッシュ値を用いることになる。存在的偽造不可能性に関する安全性を高めることができると期待されるため、hとしてはハッシュ関数を用いる事が望ましい。
【0231】
なお、ハッシュ関数hは、パラメータに依存するハッシュ関数を用いるのが更に望ましい。このことにより、存在的偽造不可能性に関する安全性を更に高めることができると期待される。このためには、上記の署名工程で計算されたaを用い、ハッシュ関数hをパラメータ付きハッシュ関数hに置き換えればよい。
【0232】
なお、整数発生工程におけるMは、必ずしも2を使用して設定する必要はない。例えばM=N/4とすることができる。ただし計算時間の短縮のために、Mは小さい方が望ましい。
【0233】
またMを2を利用して設定する場合で、かつ、パラメータ生成装置がeをx=T−1(x) mod Nを満たす2以上の最小の整数として発生させているとき又はパラメータ生成方法によりeがx=T−1(x) mod Nを満たす2以上の最小の整数として発生させられているときは、そのeを受け付け利用する事により、更に計算を高速化することができる。
【0234】
またMは、2の冪乗にとるのが望ましい。2進数を用いて計算を行った場合、非常に高速に動作し、またプログラム化も容易となるからである。
【0235】
更に、Mが2の冪乗である場合、整数kは単に正の奇数として選ぶことができる。
【0236】
上記整数k’は、拡張ユークリッドの互除法以外でも、フェルマーの小定理により、ある整数cを用いて、k’=k mod Mで高速に求めることができる。
【0237】
本発明の他の観点に係る認証方法は、コンピュータ又は専用計算装置で実行される、上記のパラメータ生成装置のいずれか又は上記のパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた認証方法であって、公開鍵受付工程と、署名付メッセージ受信工程と、整数計算工程と,認証工程と、を備え、以下のように構成する。
【0238】
公開鍵受付工程は、上記の鍵対生成方法において公開された公開鍵Tを受け付ける。
【0239】
署名付メッセージ受信工程は、上記の署名方法において計算された署名付メッセージ(a,b,m)を受信する。
【0240】
整数計算工程は、受け付けられた公開鍵Tと受信された署名付メッセージ(a,b,m)とパラメータxとパラメータNから、整数h(m)を設定し整数Wを
W=Th(m)(x)−2Th(m)(x)T(T)T(a)+T(T)+T(a)−1 mod N
により計算する。
【0241】
認証工程は、整数Wが0に等しい場合、前記署名付メッセージ(a,b,m)を認証する。
【0242】
上記署名方法と本認証方法を組み合わせて実施した場合において、署名付メッセージ(a,b,m)の第2成分bは秘密鍵である整数sを知っている署名方法によってしか作成できない。
【0243】
本発明の他の観点に係るプログラムは、コンピュータを、上記のパラメータ生成装置のいずれか、上記の鍵共有システムの送付鍵生成装置、上記の鍵共有システムの第1の鍵共有装置、上記の鍵共有システムの第2の鍵共有装置、上記の第1の公開鍵暗号システムの第1の鍵共有装置、上記の第1の公開鍵暗号システムの第2の鍵共有装置、上記の公開鍵暗号システムのいずれかの鍵対生成装置、上記の公開鍵暗号システムのいずれかの暗号化装置、上記の公開鍵暗号システムのいずれかの復号化装置、上記の電子署名システムの鍵対生成装置、上記の電子署名システムの署名装置、上記の電子署名システムの認証装置のいずれか少なくとも1つとして機能させ、又は、コンピュータに、上記のパラメータ生成方法、上記の送付鍵生成方法、上記いずれかの鍵共有方法、上記いずれかの暗号化方法、
上記いずれかの復号化方法、上記の鍵対生成方法、上記の署名方法、上記の認証方法のいずれか少なくとも1つを実行させるように構成する。
【0244】
なお、上記プログラムは、コンパクトディスク、フレキシブルディスク、ハードディスク、光磁気ディスク、ディジタルビデオディスク、磁気テープ、半導体メモリ等のコンピュータ読取可能な情報記憶媒体に記録することができる。また、上記プログラムは、プログラムが実行されるコンピュータやディジタル信号プロセッサとは独立して、コンピュータ通信網を介して配布・販売することができる。また、上記情報記憶媒体は、コンピュータやディジタル信号プロセッサとは独立して配布・販売することができる。
【発明を実施するための最良の形態】
【0245】
以下において、本発明の実施形態を説明する。なお、以下に説明する実施形態は、説明のためであって、本発明の範囲を限定するものと解されるべきではない。また、下記の実施形態の構成要素、要件を均等なものに置換することができるが、これらの形態も本発明に含まれるものとする。
【0246】
以下において、パラメータである剰余環の法Nを、2(但し、wは3以上の整数)に限定し、剰余環を2冪剰余環Z/NZに限定する。なお、Nとwは関係式N=2、w=logNによって相互に容易に変換できるので、等価であり、Nの代わりにwを用いた構成も、Nを用いた構成とみなす。例えば、格納部にNの代わりに、wが格納されていても構わない。
【0247】
更に、以下において、次数決定問題とは、この2冪のパラメータNとパラメータxと(但し、xは整数、0≦x<N)と整数y(但し、0≦y<N)とから、y=T(x) mod Nを満たす正の整数dを求める問題とする。
【0248】
更に、以下において、各部は2進数で表現された数を扱い、そのビット数はw以上である。2冪剰余環上では、平方根を除いた全ての計算は、加算、乗算と剰余の組み合わせとして実行されるが、前述のように、桁溢れを持たない又は無視したwビットの加算と乗算によって、結果的に剰余が実現される。以下における剰余を、この構成で実現し計算を高速化する。疑義のないよう数式上はmod Nと表記するが、実際にはこれを行わない。
【0249】
更に、以下において、頻繁にチェビシェフ多項式T(x)の値を計算するが、この計算部は、全て上述のwビットの加算と乗算を組み合わせたバイナリー指数法によって構成し、高速化する。例として、d=7としたT(x)をとって、このバイナリー指数法を詳しく述べる。
【0250】
まず、整数Dを
D=x−1 mod N
により計算し、一時メモリ内の適当な領域に格納する。更に、整数a及びbを、
=x,b=1
とし、中間結果として一時メモリ内の別の適当な領域に格納する。これらの整数D、a、b及びNを用い、整数a及びbを、
=a+bD mod N
=2a mod N
により計算し、別の中間結果として一時メモリ内の別の適当な領域に格納する。更に、整数a及びbを、
=a+bD mod N
=2a mod N
により計算し、別の中間結果として一時メモリ内の別の適当な領域に格納する。次に、整数a及びbを、
=a+bD mod N
=a+a mod N
により計算し、別の中間結果として一時メモリ内の別の適当な領域に格納する。最後に、
=a+bD mod N
により整数aを計算すれば、T(x)=aとなる。
【0251】
一般のdについても、このようにしてT(x)の値を高速に計算する。ここで利用する一時メモリは,その計算部に備わっている場合もあるし、汎用のものである場合もある。よって、T(x)の計算部において一時メモリとの関係に言及しないときがある。
【0252】
<第1の実施形態>
第1の実施形態として、本発明のパラメータ生成装置の実施形態を説明する。図1はパラメータ生成装置の概要構成を示すブロック図である。以下、本図を参照しつつ本実施形態のパラメータ生成装置100について説明する。なお、本実施形態のパラメータ生成装置を使用することで、本発明のパラメータ生成方法を実施することができる。
【0253】
(全体の構成)
本実施形態のパラメータ生成装置100は、2冪剰余環Z/NZ(但し、N=2、wは3以上の整数)上でd次のチェビシェフ多項式T(x)を考えることにより構成される次数決定問題を解くことを困難にするパラメータxを生成する生成装置であって、パラメータN格納部110と第1の所定値格納部120と計算部130と出力部140と第2の所定値格納部150を備えている。
【0254】
本実施形態のパラメータ生成装置100は、上記以外に、メモリ160、一時メモリ170、制御部180等を備えている。本実施形態では、パラメータN格納部110と第1の所定値格納部120と第2の所定値格納部150は、メモリ160内の領域として構成されている。
【0255】
なお、本実施形態のパラメータ生成装置100は、通常のコンピュータを用いて実現されている。但し、加算器・乗算器等を備えた専用計算装置としても実現できる。
【0256】
(パラメータN格納部の構成)
パラメータN格納部110は、パラメータNを予め記憶しており、上述したようにメモリ160内の領域として構成されている。
【0257】
また、パラメータN格納部110は、擬似乱数発生部131、q計算部132、z計算部136及び出力部140にNを出力することができるように構成されている。
【0258】
(第1の所定値格納部の構成)
第1の所定値格納部120は、予め第1の所定値nを記憶しており、メモリ160内の領域として構成されている。
【0259】
また、第1の所定値格納部120は、後述するn判定部134に第1の所定値nを出力することができるように構成されている。
【0260】
(第2の所定値格納部の構成)
第2の所定値格納部150は、予め第2の所定値nを記憶しており、メモリ160内の領域として構成されている。
【0261】
また、第2の所定値格納部150は、後述するn判定部138に第2の所定値nを出力することができるように構成されている。
【0262】
(計算部の構成)
【0263】
計算部130は、擬似乱数発生部131、q計算部132、n計数部133、n判定部134、初期値設定部135、z計算部136、等否判定部137、n判定部138及びe制御部139を備えることで、q=x−1 mod Nで定義される整数qが因数4の個数を第1の所定値以上有するという第1の条件とx=T−1(x) mod Nを満たす最小の正の整数eが第2の所定値以上であるという第2の条件とを満たすパラメータxを計算し生成することできるように構成されている。
【0264】
擬似乱数発生部131は、3以上N未満の奇数の乱数を生成できるようになっており、制御部180に要求される度に、パラメータN格納部110に格納されたパラメータNを読み出し、擬似乱数を発生し、整数xとしてメモリ160内の領域161に格納するように構成されている。
【0265】
q計算部132は、計算式q=x−1 mod Nを記憶しており、パラメータN格納部110に格納されたパラメータNと領域161に格納された整数xとから、q=x−1 mod Nを計算して、メモリ160内の領域162に格納するように構成されている。
【0266】
計数部133は、領域162に格納された整数qに関し、含まれる因数4の個数nを計数して、メモリ内の領域163に格納するように構成されている。
【0267】
このnの計数は、最下位ビットから順に並んでいる0の個数を計数し、その個数が偶数であった場合それを2で割った値をn、奇数であった場合はそこから1を引いた値を2で割った値をnとすることで実現することができる。例えばq=48のとき、2進数表現はq=(110000)であり、整数qの下位ビットから連続した0の個数=4となるため、n=2となる。実際、48=2×3=4×3であり、因数4の数は2個である。
【0268】
判定部134は、領域163に格納された因数4の個数nと第1の所定値格納部120に格納された第1の所定値nに関して、不等式n≧nが成り立つかどうかを判定し、その結果を制御部180に伝達することができるように構成されている。
【0269】
初期値設定部135は、メモリ160内の領域164に整数eとして2を格納できるように構成されている。
【0270】
z計算部136は、予め、数式z=T−1(x) mod Nを記憶しており、領域161に格納された整数xとパラメータN格納部110に格納されたパラメータNと領域164に格納された整数eとから、整数
z=T−1(x) mod N
を計算し、計算された整数zをメモリ160内の領域165に格納できるように構成されている。
【0271】
ここにおいて、補助的に整数2−1が必要となるが、この値は一時メモリ170に格納することができるように構成されている。
【0272】
なお、z計算部136では、チェビシェフ多項式の計算の際、中間結果を一時メモリ170に格納する。
【0273】
等否判定部137は、領域161に格納された整数xと領域165に格納された整数zが等しいかどうかを判定し、その結果を制御部180に伝達することができるように構成されている。
【0274】
判定部138は、第2の所定値格納部150に格納された第2の所定値nと領域164に格納された整数eに関して、不等式e≧nが成り立つかどうかを判定し、その結果を制御部180に伝達することができるように構成されている。
【0275】
e制御部139は、制御部180に要求される度に、領域164に格納された整数eの値を1だけ増やし、領域164に格納することができるように構成されている。
【0276】
(出力部の構成)
出力部140は、上述の計算部130において生成された整数xをパラメータxとして、本パラメータ生成装置100の外部に出力するように構成されている。また、出力部140は、必要に応じて、パラメータN格納部110に格納されているパラメータNや領域164に格納されている整数eも本パラメータ生成装置100の外部に出力するように構成されている。
【0277】
(その他の部材の構成)
制御部180は、後述する本パラメータ生成装置100の動作に基づき、本パラメータ生成装置100に含まれる各部の動作を制御するように構成されている。また、一時メモリ170は、制御部180の指示に応じて、計算部130の動作に必要となる中間結果を一時的に保存することができるように構成されている。
【0278】
(構成のまとめ)
このように、本実施形態のパラメータ生成装置は、コンピュータを用いて上述のように構成されており、必要な計算をしてパラメータxを生成することができる。また、加算器・乗算器等を備えた専用計算装置により同様に構成して、必要な計算をしてパラメータxを生成することもできる。
【0279】
なお、上述の構成では、パラメータN格納部110、第1の所定値格納部120及び第2の所定値格納部150は、いずれもメモリ160内の領域として構成されているが、少なくともwビットの2進数を格納できる記憶領域であれば、メモリ160内でなくとも、構成することができる。
【0280】
(動作)
以下、本パラメータ生成装置100の動作について説明する。図2は本パラメータ生成装置100の動作全体の流れを示すフローチャートである。また、図3は図2のステップS100の詳細を説明するためのフローチャートである。また、図4は図2のステップS200の詳細を説明するためのフローチャートである。以下、図2から図4を用い、本第1の実施形態の動作を説明する。
【0281】
(動作と構成の対応)
尚、ステップS100の動作は、上記の計算部130内の擬似乱数生成部131、q計算部132、n計数部133及びn判定部134で処理され、ステップS200の動作は、初期値設定部135、z計算部136、等否判定部137及びe制御部139で処理され、ステップS300の動作はn判定部138で処理される。又、以下に述べる各処理は、制御部180の制御の下で実行される。また特に明示しないが、各演算処理によって得られたデータは逐一一時メモリ170に格納され、格納された各データはその後の演算処理に利用される。
【0282】
(前処理)
まず前処理として、パラメータNがパラメータN格納部110に、第1の所定値nが第1の所定値格納部120に、第2の所定値nが第2の所定値格納部150に格納される。
【0283】
(ステップS100の詳細)
本パラメータ生成装置100の計算部130に備えられた擬似乱数生成部131は、パラメータN格納部110に格納されたパラメータNを読み出し、3以上N未満の奇数の乱数を生成して、整数xとしてメモリ160内の領域161に格納する(ステップS101)。
【0284】
次にq計算部132は、領域161に格納された整数xとパラメータN格納部110に格納されたパラメータNを読み出し、
q=x−1 mod N
を計算する。そして、計算した整数qをメモリ160内の領域162に格納する(ステップS103)。
【0285】
計数部133は、領域162に格納された整数qを読み出し、整数qに含まれる因数4の個数nを計数し、これをメモリ160内の領域163に格納する(ステップS103)。
【0286】
そしてn判定部134は、領域163に格納された整数nと第1の所定値格納部120に格納された第1の所定値nを読み出し、不等式
≧n
が成立するかどうか判定する(ステップS104)。
【0287】
判定の結果、n≧nが成立していた場合、次のステップS200へ進む。成立していなかった場合、ステップS101へ戻り、ステップS101からステップS104の動作を繰り返す。
【0288】
上記の判定を通過した場合、整数xは、q=x−1 mod Nによって定義される整数qが因数4を第1の所定値n以上有するという第1の条件を満たす。2羃剰余環上のチェビシェフ多項式の次数決定問題を解く事を困難にするため、第1の所定値は、出来る限り大きく設定する事が望ましい。但し、余り大きくしすぎると、上記の反復動作が多数繰り返され計算部130の処理時間が長くなるばかりでなく、場合によっては第1の条件を満たす整数xが全く存在しないという状況も起こり得る。従って、パラメータNに応じて適切な値を設定しておく。
【0289】
(ステップS200の詳細)
上記の処理が終わった状態において、即ち、第1の条件を満たす整数xが領域161に格納された後、以下の処理を行う。
【0290】
まず、初期値設定部135は、メモリ160内の領域164の値を2に設定する。これは整数eの値を2に設定するという動作である(ステップS201)。
【0291】
次に、z計算部136は、領域161に格納された整数xとパラメータN格納部110に格納されたパラメータNと領域164に格納された整数eを読み出し、
z=T−1(x) mod N
により整数zを計算し、メモリ160内の領域165に格納する(ステップS202)。
【0292】
等否判定部137は、領域161に格納されている整数xと領域165に格納されている整数zを読み出し、これら2つの整数の値が等しいかどうか判定する(ステップS203)。
【0293】
判定の結果、これら2つの整数が等しかった場合、次のステップS300へ進む。等しくなかった場合、ステップS204へ進む。
【0294】
上記の判定は、整数eが、x=T−1(x) mod Nを満たすかどうか判定する。
【0295】
上記の判定を通過しなかった場合、e制御部139は、領域164に格納された整数eを読み出し、その値を1だけ増加させた整数を領域164に格納する(ステップS204)。この動作は、eをインクリメントすることに対応する。そして整数zが整数xになるまでステップS202からステップS204の動作が繰り返されることになる。z=xが成立したとき、ステップS200が終了する。
【0296】
(ステップS300)
判定部138は、領域164に格納された整数eと第2の所定値格納部150に格納された第2の所定値nを読み出し、不等式
e≧n
が成立するかどうか判定する(ステップS300)。
【0297】
判定の結果、e≧nが成立していた場合、処理を終了し、出力部140を後述のように動作させる。
【0298】
e≧nが成立していなかった場合、ステップS100へ戻り、ステップS100からステップS300の動作を繰り返す。
【0299】
上記のステップS300の判定を通過した場合、eは第2の所定値n以上であるという第2の条件を満たす。eが大きいほど2羃剰余環上のチェビシェフ多項式y=T(x) mod Nの次数決定問題に対する総当たり法による攻撃に対する強度が上がるため、第2の所定値は、出来る限り大きく設定する事が望ましい。但し、余り大きくしすぎると、上記の反復動作が多数繰り返され計算部130の処理時間が長くなるばかりでなく、場合によっては第2の条件を満たす整数xが全く存在しないという状況も起こり得る。従って、パラメータNに応じて適切な値を設定しておく。
【0300】
また、第2の所定値nを0と設定しておけば、n判定部138は実質的になにも処理せず、無条件で通過する。この場合、本パラメータ生成装置100は、上記の第1の条件のみでパラメータxを生成する装置となる。
【0301】
(出力部の動作)
出力部140は、少なくともメモリ160内の領域161に格納された整数xをパラメータxとして本パラメータ生成装置100の外部へ出力する。また制御部180の指示により、パラメータN格納部110に格納されたパラメータNや領域164に格納された整数eも本パラメータ生成装置100の外部へ出力することができる。
【0302】
(動作のまとめ)
上記のように本パラメータ生成装置100を動作させる事により、第1及び第2の条件を満たすパラメータxを高速に生成し、出力することができる。
【0303】
<第2の実施形態>
第2の実施形態として、本発明のパラメータ生成装置の第1の実施形態とは異なる実施形態を説明する。図5は本パラメータ生成装置の概要構成を示すブロック図である。以下、本図を参照しつつ本実施形態のパラメータ生成装置200について説明する。なお、本実施形態の本パラメータ生成装置200を使用することで、本発明のパラメータ生成方法を実施することができる。
【0304】
(全体の構成)
本実施形態のパラメータ生成装置200は、上記のパラメータ生成装置100と同様、剰余環Z/NZ(但し、N=2、wは3以上の整数)上でd次のチェビシェフ多項式T(x)を考えることにより構成される次数決定問題を解くことを困難にするパラメータxを生成する生成装置であって、パラメータN格納部210と第1の所定値格納部220と計算部230と出力部240と第2の所定値格納部250を備えている。
【0305】
本実施形態のパラメータ生成装置200は、上記以外に、メモリ260、一時メモリ270、制御部280等を備えている。本実施形態では、パラメータN格納部210と第1の所定値格納部220と第2の所定値格納部250は、上記の第1の実施形態と同様、メモリ260内の領域として構成されている。
【0306】
なお、本実施形態のパラメータ生成装置200も上記の第1の実施形態と同様、通常のコンピュータを用いて実現されている。但し、加算器・乗算器等を備えた専用計算装置としても実現できる。
【0307】
(パラメータN格納部の構成)
パラメータN格納部210は、パラメータNを予め記憶しており、上述したようにメモリ260内の領域として構成されている。
【0308】
また、パラメータN格納部210は、擬似乱数発生部231、X計算部232、z’計算部236及び出力部240にNを出力することができるように構成されている。
【0309】
(第1の所定値格納部の構成)
第1の所定値格納部220は、予め第1の所定値nを記憶しており、メモリ260内の領域として構成されている。
【0310】
また、第1の所定値格納部220は、後述するk設定部234に第1の所定値nを出力することができるように構成されている。
【0311】
(第2の所定値格納部の構成)
第2の所定値格納部250は、予め第2の所定値nを記憶しており、メモリ260内の領域として構成されている。
【0312】
また、第2の所定値格納部250は、後述するn判定部238に第2の所定値nを出力することができるように構成されている。
【0313】
(計算部の構成)
【0314】
計算部230は、擬似乱数発生部231、X計算部232、平方根計算部233−1、平方剰余判定部233−2、k設定部234、d初期値設定部235、z’計算部236、等否判定部237、n判定部238及びd制御部239を備えることで、q=x−1 mod Nで定義される整数qが因数4の個数を第1の所定値以上有するという第1の条件とx=T−1(x) mod Nを満たす最小の正の整数eが第2の所定値以上であるという第2の条件とを満たすパラメータxを計算し生成することできるように構成されている。
【0315】
擬似乱数発生部231は、3以上N未満の奇数の乱数を生成できるようになっており、制御部280に要求される度に、パラメータN格納部210に格納されたパラメータNを読み出し、擬似乱数を発生し、整数yとしてメモリ260内の領域264に格納するように構成されている。
【0316】
X計算部232は、計算式X=4y+1 mod Nを記憶しており、パラメータN格納部210に格納されたパラメータNとメモリ260内の領域262に格納された整数kと領域264に格納された整数yとから、X=4y+1 mod Nを計算して、メモリ260内の領域266に整数Xを格納するように構成されている。
【0317】
平方根計算部233−1は、領域266に格納された整数Xに関し、パラメータN格納部210に格納されたパラメータNを読み出し、2冪剰余環Z/NZ上でXの平方根を計算し、平方根がこの2冪剰余環の要素にならない場合は0を、なる場合は整数値の平方根の1つ√X(0≦√X<N)をメモリ内の領域261に格納するように構成されている。2冪剰余環上で平方根を計算する方法としては、非特許文献2の第3章にPohling−Hellman法を利用したものが記載されており、平方根計算部233−1はこの方法による計算を実行するように構成されている。
【0318】
平方剰余判定部233−2は、領域261に格納された整数xを読み出し、その値が0に等しいかどうかを判定し、その結果を制御部280に伝達することができるように構成されている。
【0319】
このように計算された整数の平方根√Xから
q=(√X)−1 mod N
を計算したとき、整数qは因数4を第1の所定値nと同じ個数だけ持つ。これは、
q=X−1 mod N=4y mod N
より明らかである。
【0320】
k設定部234は、第1の所定値格納部220に格納された第1の所定値nに関して、その値を整数kとして設定し、領域262に格納するように構成されている。
【0321】
d初期値設定部235は、メモリ260内の領域263に整数dとして4を格納できるように構成されている。
【0322】
z’計算部236は、予め、数式z’=Td−1(x) mod Nを記憶しており、領域261に格納された整数xとパラメータN格納部210に格納されたパラメータNと領域263に格納された整数dとから、整数
z’=Td−1(x) mod N
を計算し、計算された整数z’をメモリ260内の領域265に格納できるように構成されている。
【0323】
ここにおいて、補助的に整数d−1が必要となるが、この値は一時メモリ170に格納することができるように構成されている。
【0324】
なお、本実施形態では、チェビシェフ多項式の計算の際、中間結果を一時メモリ270に格納する。
【0325】
等否判定部237は、領域261に格納された整数xと領域265に格納された整数z’が等しいかどうかを判定し、その結果を制御部280に伝達することができるように構成されている。
【0326】
判定部238は、第2の所定値格納部250に格納された第2の所定値nと領域263に格納された整数dに関して、不等式d≧2n2が成り立つかどうかを判定し、その結果を制御部280に伝達することができるように構成されている。但し、ここで、n2とはnのことである。
【0327】
d制御部239は、制御部280に要求される度に、領域263に格納された整数dの値を2倍し、領域263に格納することができるように構成されている。
【0328】
(出力部の構成)
出力部240は、上述の計算部230において生成された整数xをパラメータxとして、本パラメータ生成装置200の外部に出力するように構成されている。また、出力部240は、必要に応じて、パラメータN格納部210に格納されているパラメータNや、整数e(但し、eは領域263に格納されている整数dから計算される整数logd)を、本パラメータ生成装置200の外部に出力するように構成されている。
【0329】
(その他の部材の構成)
制御部280は、後述する本パラメータ生成装置200の動作に基づき、本パラメータ生成装置200に含まれる各部の動作を制御するように構成されている。また、一時メモリ270は、制御部280の指示に応じて、計算部230の動作に必要となる中間結果を一時的に保存することができるように構成されている。
【0330】
(構成のまとめ)
このように、本実施形態のパラメータ生成装置は、コンピュータを用いて上述のように構成されており、必要な計算をしてパラメータxを生成することができる。また、加算器・乗算器等を備えた専用計算装置により同様に構成して、必要な計算をしてパラメータxを生成することもできる。
【0331】
なお、上述の構成では、パラメータN格納部210、第1の所定値格納部220及び第2の所定値格納部250は、いずれもメモリ260内の領域として構成されているが、少なくともwビットの2進数を格納できる記憶領域であれば、メモリ260内でなくとも、構成することができる。
【0332】
(動作)
以下、本パラメータ生成装置200の動作について説明する。図6は本パラメータ生成装置200の動作全体の流れを示すフローチャートである。以下、図6を用い、本第2の実施形態の動作を説明する。
【0333】
(動作と構成の対応)
尚、ステップS401の動作は上記の計算部230内のk設定部234で、ステップS402の動作はd初期値設定部235で、ステップS403の動作は擬似乱数発生部231で、ステップS404の動作はX計算部232で、ステップS405−1の動作は平方根計算部233−1で、ステップS405−2の動作は平方剰余判定部233−2で、ステップS406の動作はz’計算部236で、ステップS407の動作は等否判定部237で、ステップS408の動作はd制御部239で、ステップS409の動作はn判定部238でそれぞれ処理される。また、以下に述べる各処理は、制御部280の制御の下で実行される。また特に明示しないが、各演算処理によって得られたデータは逐一一時メモリ270に格納され、格納された各データはその後の演算処理に利用される。
【0334】
(前処理)
まず前処理として、パラメータNがパラメータN格納部210に、第1の所定値nが第1の所定値格納部220に、第2の所定値nが第2の所定値格納部250に格納される。
【0335】
(各ステップの詳細)
本パラメータ生成装置200の計算部230に備えられたk設定部234は、第1の所定値格納部220に格納された第1の所定値nを読み出し、整数kの値をnとし、メモリ260内の領域262に格納する(ステップS401)。
【0336】
次にd初期値設定部235は、メモリ260内の領域263に値4を格納する。これはd=4という処理を行った事に対応する(ステップS402)。
【0337】
擬似乱数生成部231は、パラメータN格納部210に格納されたパラメータNを読み出し、3以上N未満の奇数の乱数を生成して、整数yとしてメモリ260内の領域264に格納する(ステップS403)。
【0338】
続いてX計算部232は、領域261に格納された整数xと領域262に格納された整数kとパラメータN格納部210に格納されたパラメータNを読み出し、
X=4y+1 mod N
を計算する。そして、計算した整数Xをメモリ260内の領域266に格納する(ステップS404)。
【0339】
そして平方根計算部233−1は、パラメータN格納部210に格納されたパラメータNと領域266に格納された整数Xを読み出し、2冪剰余環上で平方根を計算し、平方根がこの2冪剰余環の要素にならない場合は0を、なる場合は整数値の平方根の1つxを、メモリ260内の領域261に格納する(ステップS405−1)。
【0340】
平方剰余判定部233−2は、領域261から整数xを読み出し、整数xが0に等しいかどうか判定する(ステップS405−2)。
【0341】
判定の結果、整数xが0に等しい場合、ステップS403に戻る。整数xが0以外の値になるまで、即ち、xが上記の整数Xの2羃剰余環上での平方根になるまで、ステップS403からステップS405−2の動作が繰り返されることになる。x≠0が成立したとき、ステップS406へ進む。
【0342】
更に、z’計算部236は、領域261に格納された整数xとパラメータN格納部210に格納されたパラメータNと領域263に格納された整数dを読み出し、
z’=T−1(x) mod N
により整数z’を計算し、メモリ260内の領域265に格納する(ステップS406)。
【0343】
等否判定部237は、領域261に格納されている整数xと領域265に格納されている整数z’を読み出し、これら2つの整数の値が等しいかどうか判定する(ステップS407)。
【0344】
判定の結果、これら2つの整数が等しかった場合、次のステップS409へ進む。等しくなかった場合、ステップS408へ進む。
【0345】
上記の判定は、整数dが、x=Td−1(x) mod Nを満たすかどうか判定する。
【0346】
上記の判定を通過しなかった場合、d制御部239は、領域263に格納された整数dを読み出し、その値を2倍した整数を領域263に格納する(ステップS408)。整数z’が整数xになるまでステップS406からステップS408の動作が繰り返されることになる。z’=xが成立したとき、ステップS409へ進む。
【0347】
判定部238は、領域263に格納された整数dと第2の所定値格納部250に格納された第2の所定値nを読み出し、不等式
d≧2n2
が成立するかどうか判定する(ステップS409)。ここで、n2とは、第2の所定値nを意味する。
【0348】
判定の結果、d≧2n2が成立していた場合、処理を終了し、出力部240を後述のように動作させる。
【0349】
d≧2n2が成立していなかった場合、ステップS402へ戻り、ステップS402からステップS409の動作を繰り返す。
【0350】
上記のステップS409の判定を通過した場合、logd(=e)は、第2の所定値n以上であるという第2の条件を満たす。logdが大きいほど2羃剰余環上のチェビシェフ多項式y=T(x) mod Nの次数決定問題に対する総当たり法による攻撃に対する強度が上がるため、第2の所定値は、出来る限り大きく設定する事が望ましい。但し、余り大きくしすぎると、上記の反復動作が多数繰り返され計算部230の処理時間が長くなるばかりでなく、場合によっては第2の条件を満たす整数xが全く存在しないという状況も起こり得る。従って、パラメータNに応じて適切な値を設定しておく。
【0351】
また、第2の所定値nを0と設定しておけば、n判定部238は実質的になにも処理せず、無条件で通過する。この場合、本パラメータ生成装置200は、上記の第1の条件のみでパラメータxを生成する装置となる。
【0352】
(出力部の動作)
出力部240は、メモリ260内の領域261に格納された整数xをパラメータxとして本パラメータ生成装置200の外部へ出力する。また制御部280の指示により、パラメータN格納部210に格納されたパラメータNを出力し、領域263に格納された整数dを読み出し、整数e=logdを計算し出力することができる。
【0353】
(動作のまとめ)
上記のように本パラメータ生成装置200を動作させる事により、第1及び第2の条件を満たすパラメータxを高速に生成し、出力することができる。
【0354】
<第3の実施形態>
第3の実施形態として、本発明の第1の公開鍵暗号システムの実施形態を説明する。本発明の公開暗号鍵システムは、本発明のパラメータ生成装置又はパラメータ生成方法によって生成されたパラメータxと、パラメータNとを用いた公開鍵暗号システムである。図7は公開鍵暗号システムの概要構成を示す模式図である。以下、本図を参照しつつ本実施形態の公開鍵暗号システム300について説明する。なお、本実施形態の公開鍵暗号システム300は、本発明の鍵共有システムを用いたものである。
【0355】
(システム全体の構成)
本実施形態の公開鍵暗号システム300は、3台のコンピュータPC A310、PC B320及びPC C330がインターネット340を介して相互に接続されている。ここでは3台のコンピュータを考えているが、PC C330は、PC A310又はPC B320のどちらかに含むように構成することもできる。図8はPC Aの構成を示すブロック図、図9はPC Bの構成を示すブロック図である。以下、これらの図も参照しながら説明する。
【0356】
PC C330は、パラメータxとパラメータNとを出力するパラメータ生成装置である。PC A310は、本発明の鍵暗号システムに含まれる第1の鍵共有装置であって、PC B320は、本発明の鍵暗号システムに含まれる送付鍵生成装置と第2の鍵共有装置を兼ねている。なお、本実施形態では、本発明のパラメータ生成装置が生成し出力したパラメータxと、それに対応するパラメータNとを用いるために、パラメータ生成装置であるPC C330が、公開鍵暗号システムの一部を構成している。但し、本発明の公開鍵暗号システムとしては、パラメータ生成装置がシステムの一部を構成しなくても、パラメータ生成装置が生成し出力したパラメータxと、それに対応するパラメータNとを本システムが用いていればよい。
【0357】
また、本実施形態の公開鍵暗号システムは、3台のコンピュータを用いているが、それぞれについて、コンピュータに代えて、加算器・乗算器等を備えた専用計算装置としても実現できる。
【0358】
(パラメータ生成装置(PC C330)の構成)
PC C330は、上記の第1の実施形態又は第2の実施形態で示したパラメータ生成装置であって、パラメータxとパラメータNとを出力するように構成されている。
【0359】
(第1の鍵共有装置(PC A310)の構成)
PC A310は、本発明の公開鍵暗号システムを構成する第1の鍵共有装置であって、図8に示すように構成されている。即ち、メモリ311、整数取得部312、送付鍵計算部313、送付鍵出力部314、送付鍵入力部315、共有鍵計算部316、暗号化部317、暗号化メッセージ送信部318、一時メモリ311i、制御部319を備える。一時メモリ311iは、各部の計算過程を一時的に格納することができるように構成されている。また制御部319は全体の動作を制御できるように構成されている。
【0360】
尚、本発明の第1の鍵共有装置を構成することができる。また、本PC A310を使用することで、本発明の第1の鍵共有方法及び第1の暗号化方法を実施することができる。
【0361】
(第1の鍵共有装置(PC A310)の各部の構成)
メモリ311は、PC C330の出力したパラメータxとパラメータN、整数t、送付鍵U、送付鍵T、共有鍵V’、メッセージm及び暗号化メッセージcを格納できるよう構成されている。
【0362】
整数取得部312は、大きな奇数tを取得し、メモリ311の領域311bに格納できるように構成されている。
【0363】
送付鍵計算部313は、予め計算式U=T(x) mod Nを記憶しており、メモリ311内の領域311cに格納されたパラメータtと領域311aに格納されたパラメータxと領域311bに格納されたパラメータNとから、
U=T(x) mod N
により送付鍵Uを計算し、メモリ311内の領域311dに格納できるように構成されている。
【0364】
送付鍵出力部314は、領域311dに格納されている送付鍵UをPC A310の外部に出力できるよう構成されている。
【0365】
送付鍵入力部315は、PC A310の外部から入力された送付鍵Tを入力し、メモリ311内の領域311eに格納できるように構成されている。
【0366】
共有鍵計算部316は、予め計算式V’=T(T) mod Nを記憶しており、領域311cに格納された整数tと領域311eに格納された送付鍵Tと領域311bに格納されたパラメータNとから、
V’=T(T) mod N
により共有鍵V’を計算し、メモリ内の領域311fに格納できるように構成されている。
【0367】
暗号化部317は、予め記憶された対称鍵暗号方式の暗号化式と領域311fに格納された共有鍵V’を用いて、領域311gに格納されたメッセージmから暗号化メッセージcを計算し、メモリ311内の領域311hに格納できるように構成されている。
【0368】
暗号化メッセージ送信部318は、領域311hに格納された暗号化メッセージcをPC A310の外部に出力できるよう構成されている。
【0369】
(送付鍵生成装置兼第2の鍵共有装置(PC B320)の構成)
PC B320は、本発明の公開鍵暗号システムを構成する送付鍵生成装置と第2の鍵共有装置を兼ねており、図9に示すように構成されている。即ち、メモリ321、整数取得部322a、送付鍵計算部322b、第1送付鍵出力部322c、第2送付鍵出力部322d、第1送付鍵入力部323a、第2送付鍵入力部323b、共有鍵計算部323c、暗号化メッセージ受信部323d、復号化部323e、一時メモリ321i、制御部324を備えている。一時メモリ321iは、各部の計算過程を一時的に格納することができるように構成されている。また制御部324は全体の動作を制御できるように構成されている。
【0370】
なお、送付鍵生成装置に対応する部分としては、メモリ321内の領域321a、321b、321c及び321d、整数取得部322a、送付鍵計算部322b、第1送付鍵出力部322c、第2送付鍵出力部322d等であり、第2の鍵共有装置に対応する部分としては、メモリ321内の321e、321f、321g及び321h、第1送付鍵入力部323a、第2送付鍵入力部323b、共有鍵計算部323c、暗号化メッセージ受信部323d、復号化部323e等である。
【0371】
また、本PC A320を使用することで、本発明の送付鍵生成方法、第2の鍵共有方法及び第1の復号化方法を実施することができる。
【0372】
(送付鍵生成装置兼第2の鍵共有装置(PC B)の各部の構成)
メモリ321は、PC C330の出力したパラメータxとパラメータN、整数s、送付鍵T、送付鍵U、共有鍵V、暗号化メッセージc及びメッセージm’を格納できるよう構成されている。
【0373】
整数取得部322aは、大きな奇数sを取得し、メモリ321の領域321cに格納できるように構成されている。
【0374】
送付鍵計算部322bは、予め計算式T=T(x) mod Nを記憶しており、メモリ321内の領域321cに格納されたパラメータsと領域321aに格納されたパラメータxと領域321bに格納されたパラメータNとから、
T=T(x) mod N
により送付鍵Tを計算し、メモリ321内の領域321dに格納できるように構成されている。
【0375】
第1送付鍵出力部322cは、領域321dに格納されている送付鍵TをPC B320の外部に出力できるよう構成されている。
【0376】
第2送付鍵出力部322dは、領域321cに格納されている整数sを送付鍵として送付鍵生成装置322の外部に出力できるよう構成されている。
【0377】
第1送付鍵入力部323aは、PC B320の外部から入力された送付鍵Uを入力し、メモリ321内の領域321eに格納できるように構成されている。
【0378】
第2送付鍵入力部323bは、第2の鍵共有装置323の外部から入力された送付鍵sを入力し、メモリ321内の領域321cに格納できるように構成されている。
【0379】
共有鍵計算部323cは、予め計算式V=T(U) mod Nを記憶しており、領域321cに格納された送付鍵sと領域321eに格納された送付鍵Uと領域321bに格納されたパラメータNとから、
V=T(U) mod N
により共有鍵Vを計算し、メモリ内の領域321fに格納できるように構成されている。
【0380】
暗号化メッセージ受信部323dは、PC B320の外部から入力された暗号化メッセージcを領域321gに格納できるよう構成されている。
【0381】
復号化部323eは、予め記憶された対称鍵暗号方式の復号化式と領域321fに格納された共有鍵Vを用いて、領域321gに格納された暗号化メッセージcからメッセージm’を計算し、メモリ321内の領域321hに格納できるように構成されている。
【0382】
(構成のまとめ)
このように、本実施形態の公開鍵暗号システムは、3台のコンピュータを用いて上述のように構成されており、PC C330の生成したパラメータxとパラメータNを用い、PC A310が作成した暗号化メッセージをPC B320で復号化することができる。また、PC A310とPC B320でそれぞれ作成された共有鍵V’とVは等しい。
【0383】
(鍵共有システムとしての動作)
以下、本公開鍵暗号システム300の動作について説明する。図10は本公開鍵暗号システム300の鍵共有システムとしての動作の流れを示すフローチャートである。以下、図10を用い、本第3の実施形態の動作を説明する。
【0384】
(ステップS410)
PC C330の動作により、パラメータxとパラメータNが生成され、インターネット340を通じPC A310及びPC B320に配信される。
【0385】
PC A310は、配信されたパラメータxをメモリ311内の領域311aに、パラメータNを領域311bに格納する。
【0386】
PC B320は、配信されたパラメータxをメモリ321内の領域321aに、パラメータNを領域321bに格納する。
【0387】
(ステップS420)
PC A310の整数取得部312は、大きな奇数である整数tを生成してメモリ311内の領域311cに整数tとして格納する。
【0388】
送付鍵計算部313は、領域311aに格納されたパラメータxと領域311bに格納されたパラメータNと領域311cに格納された整数tを読み出し、
U=T(x) mod N
により送付鍵Uを計算し、領域311dに格納する。
【0389】
送付鍵出力部314は、領域311dに格納された送付鍵Uを読み出し、インターネット340を通じPC B320の第1送付鍵入力部323aに出力する。
【0390】
(ステップS430)
PC B320の整数取得部322aは、大きな奇数である整数sを生成してメモリ321内の領域321aに整数sとして格納する。
【0391】
送付鍵計算部322bは、領域321cに格納された整数sと領域321aに格納されたパラメータxと領域321bに格納されたパラメータNを読み出し、
T=T(x) mod N
により送付鍵Tを計算し、領域321dに格納する。
【0392】
第1送付鍵出力部322cは、領域321dに格納された送付鍵Tを読み出し、インターネット340を通じPC A310の送付鍵入力部315に出力する。
【0393】
第2送付鍵出力部322dは、領域321cに格納された整数sを読み出し、送付鍵として第2送付鍵入力部323bに出力する。
【0394】
第1送付鍵入力部323aは、PC A310の送付鍵出力部314が出力した送付鍵Uを入力し、領域321eに格納する。
【0395】
第2送付鍵入力部323bは、第2送付鍵出力部322dが送付鍵として出力した整数sを入力し、領域321cに格納する。
【0396】
共有鍵計算部323cは、領域321cに格納された整数sと領域321eに格納された送付鍵Uと領域321bに格納されたパラメータNとから、
V=T(U) mod N
により共有鍵Vを計算し、領域321fに格納する。
【0397】
(ステップS440)
PC A310の送付鍵入力部315は、PC B320の第1送付鍵出力部322cが出力した送付鍵Tを入力し、メモリ311の領域311eに格納する。
【0398】
共有鍵計算部316は、領域311eに格納された送付鍵Tから、
V’=T(T) mod N
により共有鍵V’を計算し、領域311fに格納する。
【0399】
(鍵共有システムとしての動作のまとめ)
ここで、チェビシェフ多項式の性質より、
V=T(T(x)) mod N=Tst(x)mod N
及び、
V’=T(T(x)) mod N=Tst(x) mod N
となることから、V=V’が成立する。即ち、V(=V’)が共有鍵として、PC A310及びPC B320に共有される。
【0400】
(公開鍵暗号システムとしての動作)
上記の鍵共有システムとしての動作の後に、次の動作を加えることによって、本第3の実施形態を、公開鍵暗号システムとして動作させることができる。
【0401】
PC A310のメモリ311には、領域311gに予め平文のメッセージmが格納されている。
【0402】
PC A310の暗号化部317は、メモリ311内の領域311gに格納された平文のメッセージmと領域311fに格納された共有鍵V’を読み出し、予め記憶されている対称鍵暗号方式の暗号化計算式により、メッセージmを共有鍵V’を用いて暗号化し、暗号化メッセージcを得、領域311hに格納する。
【0403】
暗号化メッセージ送信部318は、インターネット340を通し、PC B320の暗号化メッセージ受信部323dに領域311hに格納された暗号化メッセージcを送信する。
【0404】
PC B320の暗号化メッセージ受信部323dは、PC A310が送信した暗号化メッセージcを受信し、メモリ321内の領域321gに格納する。
【0405】
復号化部323eは、領域321gに格納された暗号化メッセージcと領域321fに格納された共有鍵Vを読み出し、予め記憶されている対称鍵暗号方式の復号化計算式により、暗号化メッセージcを共有鍵Vを用いて復号化し、平文のメッセージm’を得、領域321hに格納する。
【0406】
このように本第3の実施形態は、パラメータx、パラメータN及び送付鍵Tを公開鍵とみて、整数sを秘密鍵とみて、全体としての暗号化メッセージを(c,U)とみれば、公開鍵暗号システムとして用いる事ができる。
【0407】
(第3の実施形態の変形例)
本第3の実施形態では、PC B320が本発明の送付鍵生成装置と第2の鍵共有装置を兼ねた形態であるが、変形例は、送付鍵生成装置と第2の鍵共有装置とを別々の装置とする形態である。
【0408】
この変形例では、便宜上、図9を用いて説明すると、送付鍵生成装置は、領域321a、321b、321c及び321dを有するメモリ、整数取得部322a、送付鍵計算部322b、第1送付鍵出力部322c、第2送付鍵出力部322d等を備えた装置であり、第2の鍵共有装置に対応する部分としては、領域321e、321f、321g及び321hを有するメモリ、第1送付鍵入力部323a、第2送付鍵入力部323b、共有鍵計算部323c、暗号化メッセージ受信部323d、復号化部323e等を備えた装置である。
【0409】
送付鍵生成装置の動作、及び、第2の鍵共有装置の動作は、装置が分離したことに伴う違いを除けば、基本的には、第3の実施形態と同様である。
【0410】
<第4の実施形態>
第4の実施形態として、本発明の第2の公開鍵暗号システムの実施形態を説明する。本発明の公開暗号鍵システムは、本発明のパラメータ生成装置又はパラメータ生成方法によって生成されたパラメータxと、パラメータNとを用いた公開鍵暗号システムである。図11は公開鍵暗号システムの概要構成を示す模式図である。以下、本図を参照しつつ本実施形態の公開鍵暗号システム400について説明する。
【0411】
(システム全体の構成)
本実施形態の公開鍵暗号システム400は、3台のコンピュータPC A410、PC B420及びPC C430がインターネット440を介して相互に接続されている。ここでは3台のコンピュータを考えているが、PC C430は、PC A410又はPC B420のどちらかに含むように構成することもできる。図12はPC Aの構成を示すブロック図、図13はPC Bの構成を示すブロック図である。以下、これらの図も参照しながら説明する。
【0412】
PC C430は、パラメータxとパラメータNとを出力するパラメータ生成装置である。PC A410は、本発明の公開鍵暗号システムに含まれる暗号化装置であって、PC B420は、本発明の公開鍵暗号システムに含まれる鍵対生成装置と復号化装置を兼ねている。なお、本実施形態では、本発明のパラメータ生成装置が生成し出力したパラメータxと、それに対応するパラメータNとを用いるために、パラメータ生成装置であるPC C430が、公開鍵暗号システムの一部を構成している。但し、本発明の公開鍵暗号システムとしては、パラメータ生成装置がシステムの一部を構成しなくても、パラメータ生成装置が生成し出力したパラメータxと、それに対応するパラメータNとを本システムが用いていればよい。
【0413】
また、本実施形態の公開鍵暗号システムは、3台のコンピュータを用いているが、それぞれについて、コンピュータに代えて、加算器・乗算器等を備えた専用計算装置としても実現できる。
【0414】
(パラメータ生成装置(PC C430)の構成)
PC C430は、上記の第1の実施形態又は第2の実施形態で示したパラメータ生成装置であって、パラメータxとパラメータNとを出力するように構成されている。
【0415】
(暗号化装置(PC A410)の構成)
PC A410は、本発明の公開鍵暗号システムを構成する暗号化装置であって、図12に示すように構成されている。即ち、メモリ411、整数取得部413、公開鍵受付部412、暗号化部414、暗号化メッセージ送信部415、一時メモリ411h、制御部416を備える。一時メモリ411hは、各部の計算過程を一時的に格納することができるように構成されている。また制御部416は、全体の動作を制御できるように構成されている。
【0416】
尚、本PC A410を上述のように構成する事で、本発明の暗号化装置を実現することができる。また、本PC A410を使用することで、本発明の第2の暗号化方法を実施することができる。
【0417】
(暗号化装置(PC A410)の各部の構成)
メモリ411は、PC C430の出力したパラメータxとパラメータN、整数r、公開鍵T、メッセージm及び暗号化メッセージ(c,c)を格納できるよう構成されている。
【0418】
整数取得部413は、大きな奇数である整数rを取得し、メモリ411の領域411dに格納できるよう構成されている。
【0419】
公開鍵受付部412は、PC A410の外部に公開されている公開鍵Tを受け付け、領域411cに格納できるよう構成されている。
【0420】
暗号化部414は、予め計算式c=T(x) mod N及びc=mT(T) mod Nが記憶されており、領域411eに格納されている奇数であるメッセージm(0<m<N)と、領域411dに格納されている整数rと、領域411aに格納されているパラメータxと、領域411bに格納されているパラメータNと、領域411cに格納されている公開鍵Tとから、
=T(x) mod N
=mT(T) mod N
により整数の組である暗号化メッセージ(c,c)を計算し、cを領域411fに、cを領域411gに格納できるよう構成されている。
【0421】
暗号化メッセージ送信部415は、領域411f及び411gに格納されている暗号化メッセージ(c,c)を、PC A410の外部へ送信できるよう構成されている。
【0422】
(鍵対生成装置兼復号化装置(PC B420)の構成)
PC B420は、本発明の公開鍵暗号システムを構成する鍵対生成装置と復号化装置を兼ねており、図13に示すように構成されている。即ち、メモリ421、整数取得部422a、公開鍵計算部422b、公開鍵公開部422c、秘密鍵出力部422d、暗号化メッセージ受信部423a、秘密鍵入力部423b、中間整数計算部423c、復号化部423d、一時メモリ421i、制御部424を備える。一時メモリ421iは、各部の計算過程を一時的に格納することができるように構成されている。また制御部424は、全体の動作を制御できるように構成されている。
【0423】
なお、鍵対生成装置に対応する部分としては、メモリ421内の領域421a、421b及び421c、整数取得部422a、公開鍵計算部422b、公開鍵公開部422c、秘密鍵出力部422d等であり、復号化装置に対応する部分としては、メモリ421内の領域421d、421e、421f、421g及び421h、暗号化メッセージ受信部423a、秘密鍵入力部423b、中間整数計算部423c、復号化部423d等である。
【0424】
また、本PC B420を使用することで、本発明の鍵対生成方法、復号化方法を実施することができる。
【0425】
(鍵対生成装置兼復号化装置(PC B420)の各部の構成)
メモリ421は、PC C430の出力したパラメータxとパラメータN、整数s、暗号化メッセージc及びc、中間整数α、公開鍵T及びメッセージm’を格納できるよう構成されている。
【0426】
整数取得部422aは、大きな奇数である整数sを取得し、メモリ421の領域421cに格納できるように構成されている。
【0427】
公開鍵計算部422bは、予め計算式T=T(x) mod Nを記憶しており、メモリ421内の領域421cに格納されたパラメータsと領域421aに格納されたパラメータxと領域421bに格納されたパラメータNとから、
T=T(x) mod N
により公開鍵Tを計算し、メモリ421内の領域421hに格納できるように構成されている。
【0428】
公開鍵公開部422cは、領域421hに格納されている公開鍵TをPC B420の外部に公開できるよう構成されている。
【0429】
秘密鍵出力部422dは、領域421cに格納されている整数sを秘密鍵として秘密鍵入力部423bに出力できるよう構成されている。
【0430】
暗号化メッセージ受信部423aは、PC B420の外部から入力された暗号化メッセージ(c,c)を入力し、メモリ421内の領域421d及び421eに格納できるように構成されている。
【0431】
秘密鍵入力部423bは、秘密鍵出力部422dから入力された秘密鍵である整数sを入力し、メモリ421内の領域421cに格納できるように構成されている。
【0432】
中間整数計算部423cは、予め拡張ユークリッドの互除法が実現できるよう構成されており、領域421cに格納された秘密鍵である整数sと領域421dに格納された暗号化メッセージの第1成分cと領域421bに格納されたパラメータNとから、
1=αT(c) mod N
を満たす中間整数αを計算し、メモリ421内の領域421fに格納できるように構成されている。なお、拡張ユークリッドの互除法の代わりに、フェルマーの小定理を用いてT(c)の適当な冪乗を計算してもこれを満たすαが得られる。
【0433】
復号化部423eは、予め計算式m’=αc mod Nが記憶されており、領域421fに格納された中間整数αと領域421eに格納された暗号化メッセージの第2成分cと領域421bに格納されたパラメータNとから、
m’=αc mod N
を計算してメッセージm’を計算し、メモリ421内の領域421gに格納できるように構成されている。
【0434】
(構成のまとめ)
このように、本実施形態の公開鍵暗号システムは、3台のコンピュータを用いて上述のように構成されており、PC C430の生成したパラメータxとパラメータNを用い、PC A410が作成した暗号化メッセージをPC B420で復号化することができる。
【0435】
(動作)
以下、本公開鍵暗号システム400の動作について説明する。図14は本公開鍵暗号システム400の動作全体の流れを示すフローチャートである。以下、図14を用い、本第4の実施形態の動作を説明する。
【0436】
(事前処理)
PC A410に備えられているメモリ411の領域411eには、予め奇数であるメッセージm(0<m<N)が格納されている。
【0437】
(ステップS510)
PC C430の動作により、パラメータxとパラメータNが生成され、インターネット440を通じPC A410及びPC B420に配信される。
【0438】
(ステップS520)
PC B420は、インターネット440を通じPC C430から受け取ったパラメータxをメモリ421内の領域421aに、パラメータNを領域421bに格納する。
【0439】
PC B420内の整数取得部422aは、正の奇数である整数sを取得し、メモリ421内の領域421cに格納する。
【0440】
公開鍵計算部422bは、領域421cに格納されている整数sと領域421aに格納されているパラメータxと領域421bに格納されているパラメータNを読み出し、
T=T(x) mod N
により公開鍵Tを計算し、領域421hに格納する。
【0441】
公開鍵公開部422cは、領域421hに格納されている公開鍵Tを読み出し、インターネット440へ公開する。
【0442】
秘密鍵出力部422dは、領域421cに格納されている整数sを読み出し、秘密鍵として秘密鍵入力部423bに出力する。
【0443】
(ステップS530)
一方、PC A410は、インターネット440を通じPC C430から受け取ったパラメータxをメモリ411内の領域411aに、パラメータNを領域411bに格納する。
【0444】
公開鍵受付部412は、PC B420内の公開鍵公開部422cが公開した公開鍵Tを受け付け、メモリ411内の領域411cに格納する。
【0445】
整数取得部413は、正の奇数である整数rを取得し、メモリ411内の領域411dに格納する。
【0446】
暗号化部414は、領域411eに格納されているメッセージmと、領域411dに格納されている整数rと、領域411aに格納されているパラメータxと、領域411bに格納されているパラメータNと、領域411cに格納されている公開鍵Tとを読み出し、
=T(x) mod N
=mT(T) mod N
により整数の組である暗号化メッセージ(c,c)を計算し、第1成分cを領域411fに、第2成分cを領域411gに格納する。
【0447】
暗号化メッセージ送信部415は、領域411f及び411gに格納されている暗号化メッセージ(c,c)を読み出し、PC B420内の暗号化メッセージ受信部423aへ送信する。
【0448】
(ステップS540)
PC B420の暗号化メッセージ受信部423aは、PC A410の暗号化メッセージ送信部415が送信した暗号化メッセージ(c,c)を受信し、メモリ421内の領域421dに第1成分cを、領域421eに第2成分cを格納する。
【0449】
秘密鍵入力部423bは、秘密鍵出力部422dが秘密鍵として出力した整数sを入力し、メモリ421上の領域421cに格納する。
【0450】
中間整数計算部423cは、領域421cに格納されている整数sと領域421dに格納されている暗号化メッセージ(c,c)の第1成分cと領域421bに格納されているパラメータNとを読み出し、
1=αT(c) mod N
を満たす中間整数αを求め、メモリ421内の領域421fに格納する。
【0451】
復号化部423dは、領域421eに格納されている暗号化メッセージ(c,c)の第2成分cと領域421fに格納されている中間整数αと領域421bに格納されているパラメータNを読み出し、
m’=αc mod N
によりメッセージm’を得、領域421gに格納する。
【0452】
(動作のまとめ)
このメッセージm’は、暗号化装置が送信した元のメッセージmと等しく、本第4の実施形態は、公開鍵暗号システムとして用いる事ができる。
【0453】
(第4の実施形態の変形例)
本第4の実施形態では、PC B420が本発明の鍵対生成装置と復号化装置を兼ねた形態であるが、変形例は、鍵対生成装置と復号化装置とを別々の装置とする形態である。
【0454】
本変形例では、便宜上、図13を用いて説明すると、鍵対生成装置は、領域421a、421b及び421cを有するメモリ、整数取得部422a、公開鍵計算部422b、公開鍵公開部422c、秘密鍵出力部422d等を備えた装置であり、復号化装置に対応する部分としては、領域421d、421e、421f、421g及び421hを有するメモリ、暗号化メッセージ受信部423a、秘密鍵入力部423b、中間整数計算部423c、復号化部423d等を備えた装置である。
【0455】
鍵対生成装置の動作、及び、復号化装置の動作は、装置が分離したことに伴う違いを除けば、基本的には、第4の実施形態と同様である。
【0456】
(第4の実施形態の第2の変形例)
また本第4の実施形態の第2の変形例は、暗号化と復号化を第4の実施形態と異なる方式で行う公開鍵暗号システムとする形態である。即ち、本発明の第3の公開暗号鍵システムの実施形態である。
【0457】
この変形例は、全体を図10と同様な、又は、上記の変形例と同様な形態とし、暗号化部414及び復号化部423dの構成を変える事により実施する。これを便宜上、図12と図13を用いて説明する。
【0458】
暗号化部414は、予め計算式c=T(x) mod N及びc=(T(T) mod N) xor mを記憶しており、メモリ411内の領域411eに格納された整数であるメッセージm(0≦m<N)と、領域411dに格納された整数rと、領域411aに格納されたパラメータxと、領域411bに格納されたパラメータNと、領域411cに格納されている公開鍵Tとから、
=T(x) mod N
=(T(T) mod N) xor m
により整数の組である暗号化メッセージ(c,c)を計算し、第1成分cをメモリ411内の領域411fに、第2成分cを領域411gに格納できるように構成されている。
【0459】
また復号化部423dは、予め計算式m’=(T(c) mod N) xor cを記憶しており、メモリ421内の領域421cに格納された整数sと、領域421d及び421eに格納された暗号化メッセージ(c,c)と、領域421bに格納されたパラメータNとから、
m’=(T(c) mod N) xor c
によりメッセージm’を得、メモリ421内の領域421gに格納できるように構成されている。
【0460】
本変形例の動作は、上記のように構成された暗号化部414と復号化部423dが動作する事以外は第4の実施形態と同じであるため、説明は省略する。尚、本変形例において、中間整数計算部423cは抹消したものとする。
【0461】
復号化装置423dで計算されたメッセージm’は、暗号化装置の送信したメッセージmに等しい。このように本変形例は、暗号化装置の送信した暗号化メッセージを復号化装置で復号するという、公開鍵暗号システムとして用いることができる。
【0462】
<第5の実施形態>
第5の実施形態として、本発明の電子署名システムの実施形態を説明する。本発明の電子署名システムは、本発明のパラメータ生成装置又はパラメータ生成方法によって生成されたパラメータxと、パラメータNと、更に整数eを用いた電子署名システムである。図15は電子署名システムの概要構成を示す模式図である。以下、本図を参照しつつ本実施形態の電子署名システム500について説明する。
【0463】
(システム全体の構成)
本実施形態の電子署名システム500は、3台のコンピュータPC A510、PC B520及びPC C530がインターネット540を介して相互に接続されている。ここでは3台のコンピュータを考えているが、PC C530は、PC A510又はPC B520のどちらかに含むように構成することもできる。図16はPC Aの構成を示すブロック図、図17はPC Bの構成を示すブロック図である。以下、これらの図も参照しながら説明する。
【0464】
PC C530は、パラメータxとパラメータNと整数eを出力するパラメータ生成装置である。PC A510は、本発明の電子署名システムに含まれる認証装置であって、PC B520は、本発明の電子署名システムに含まれる鍵対生成装置と署名装置を兼ねている。なお、本実施形態では、本発明のパラメータ生成装置が生成し出力したパラメータxと、それに対応するパラメータNとを用いるために、パラメータ生成装置であるPC C530が、電子署名システムの一部を構成している。但し、本発明の電子署名システムとしては、パラメータ生成装置がシステムの一部を構成しなくても、パラメータ生成装置が生成し出力したパラメータxと、それに対応するパラメータNとを本システムが用いていればよい。
【0465】
また、本実施形態の電子署名システムは、3台のコンピュータを用いているが、それぞれについて、コンピュータに代えて、加算器・乗算器等を備えた専用計算装置としても実現できる。
【0466】
(パラメータ生成装置(PC C530)の構成)
PC C530は、上記の第1の実施形態又は第2の実施形態で示したパラメータ生成装置であって、パラメータxとパラメータNと整数eを出力するように構成されている。
【0467】
(認証装置(PC A510)の構成)
PC A510は、本発明の電子署名システムを構成する認証装置であって、図16に示すように構成されている。即ち、メモリ511、公開鍵受付部512、署名付メッセージ受信部513、整数計算部514、認証部515、一時メモリ511h、制御部516を備える。一時メモリ511hは、各部の計算過程を一時的に格納することができるように構成されている。また制御部516は、全体の動作を制御できるように構成されている。
【0468】
尚、本PC A510を上述のように構成する事で、本発明の認証装置を実現することができる。また、本PC A510を使用することで、本発明の認証方法を実施することができる。
【0469】
(認証装置(PC A510)の各部の構成)
メモリ511は、PC C530の出力したパラメータxとパラメータN、公開鍵T、メッセージm及び署名付メッセージ(a,b,m)を格納できるよう構成されている。
【0470】
公開鍵受付部512は、PC A510の外部に公開されている公開鍵Tを受け付け、領域511cに格納できるよう構成されている。
【0471】
署名付メッセージ受信部513は、PC B520内の署名付メッセージ送信部523dが送信した署名付メッセージ(a,b,m)を受信し、第1成分aを領域511dに、第2成分bを領域511eに、第3成分mを領域511fに格納できるように構成されている。
【0472】
整数計算部514は、予めハッシュ関数hと計算式W=Th(m)(x)−2Th(m)(x)T(T)T(a)+T(T)+T(a)−1 mod Nが記憶されており、領域511d、511e及び511fに格納されている署名付メッセージ(a,b,m)と、領域511aに格納されているパラメータxと、領域511cに格納されている公開鍵Tと、領域511bに格納されているパラメータNを読み出し、整数h(m)をハッシュ関数hを用いて計算し、更に、整数Wを前記計算式を用いて計算し、整数Wを領域511gに格納できるように構成されている。
【0473】
認証部515は、領域511gに格納された整数Wを読み出し、その値が0に等しい場合、署名付メッセージ(a,b,m)を認証することができるように構成されている。
【0474】
(鍵対生成装置兼署名装置(PC B520)の構成)
PC B520は、本発明の電子署名システムを構成する鍵対生成装置と署名装置を兼ねており、図17に示すように構成されている。即ち、メモリ521、整数取得部522a、公開鍵計算部522b、公開鍵公開部522c、秘密鍵出力部522d、整数発生部523a、秘密鍵入力部523b、署名部523c、署名付メッセージ送信部523d、一時メモリ521l、制御部524を備える。一時メモリ521lは、各部の計算過程を一時的に格納することができるように構成されている。また制御部524は、全体の動作を制御できるように構成されている。
【0475】
なお、鍵対生成装置に対応する部分としては、メモリ521内の領域521a、521b、521c及び521i、整数取得部522a、公開鍵計算部522b、公開鍵公開部522c、秘密鍵出力部522d等であり、署名装置に対応する部分としては、メモリ521内の領域521d、521e、521f、521g、521h、521j及び521k、整数発生部523a、秘密鍵入力部523b、署名部523c、署名付メッセージ送信部523d等である。
【0476】
また、本PC B520を使用することで、本発明の鍵対生成方法、署名方法を実施することができる。
【0477】
(鍵対生成装置兼署名装置(PC B520)の各部の構成)
メモリ521は、PC C530の出力したパラメータxとパラメータNと整数e、整数s、署名付メッセージ(a,b,m)、整数k、整数k’、公開鍵T及び整数Mを格納できるよう構成されている。
【0478】
整数発生部523aは、メモリ521内の領域521jから整数eを読み出し、整数Mを2に設定し、領域521kに格納することができるように構成されている。ここで、Mは、2倍数であってN以下のものであれば何でもよいが、高速化のために最小の2に設定する。また整数発生部523aは、設定した整数Mと互いに素な正の整数kを発生させ、領域521gに格納できるように構成されている。ここで、整数Mは2の冪乗なので、正の奇数kを発生すれば、Mと互いに素になっている。整数発生部523aは更に、計算式1
= k’k mod Mを予め記憶しており、上記の設定した整数Mと発生させた整数kとから拡張ユークリッドの互除法を用いて、
1 =
k’k mod M
を満たす正の整数k’を発生させ、領域521hに格納することができるように構成されている。なお、拡張ユークリッドの互除法の代わりに、フェルマーの小定理を用いてkの適当な冪乗を計算してもこれを満たすk’が得られる。
【0479】
秘密鍵入力部523bは、秘密鍵出力部522dが秘密鍵として出力した整数sを入力し、領域521cに格納することができるように構成されている。
【0480】
署名部523cは、予めハッシュ関数hと計算式a=T(x) mod N及びb=k’(sa+h(m)) mod Mが記憶されており、領域521gに格納されている整数kと、領域521hに格納されている整数k’と、領域521aに格納されているパラメータxと、領域521cに格納されている秘密鍵である整数sと、領域521fに格納されている整数であるメッセージm(0≦m<N)と、領域521kに格納されている整数Mと、領域521bに格納されているパラメータNとを読み出し、
a=T(x) mod N
b=k’(sa+h(m)) mod M
により署名付メッセージ(a,b,m)を計算し、整数a、整数b及び整数mをそれぞれ領域521d、521e及び521fに格納できるように構成されている。
【0481】
署名付メッセージ送信部523dは、領域521d、521e及び521fにそれぞれ格納されている整数a、b及びmを読み出し、署名付メッセージ(a,b,m)としてPC A510の署名付メッセージ受信部513へ送信することができるように構成されている。
【0482】
(構成のまとめ)
このように、本実施形態の電子署名システムは、3台のコンピュータを用いて上述のように構成されており、PC C530の生成したパラメータxとパラメータNを用い、PC B520が作成した署名付メッセージをPC A510で認証することができる。
【0483】
(動作)
以下、本電子署名システム500の動作について説明する。図18は本電子署名システム500の動作全体の流れを示すフローチャートである。以下、図18を用い、本第5の実施形態の動作を説明する。
【0484】
(事前処理)
PC B520内に備えられたメモリ521内の領域521fには予め正の整数であるメッセージmが格納されている。
【0485】
(ステップS610)
PC C530の動作により、パラメータxとパラメータNと整数eが生成され、インターネット540を通じ、PC A510にパラメータxとパラメータNが、PC B520にパラメータxとパラメータNと整数eが配信される。
【0486】
(ステップS620)
PC B520は、インターネット540を通じPC C530から受け取ったパラメータxをメモリ521内の領域521aに、パラメータNを領域521bに、整数eを領域521jに格納する。
【0487】
整数取得部522aは、大きい正の整数sを取得し、メモリ521内の領域521cに格納する。
【0488】
公開鍵計算部522bは、メモリ521内の領域521cに格納されている整数sと、領域521aに格納されているパラメータxと、領域521bに格納されているパラメータNを読み込み、
T=T(x) mod N
により公開鍵Tを計算し、領域521iに格納する。
【0489】
公開鍵公開部522cは、領域521iに格納されている公開鍵Tを読み出し、PC A510内の公開鍵受付部512に公開する。
【0490】
秘密鍵出力部522dは、領域521sに格納されている整数sを読み出し、秘密鍵として秘密鍵入力部523bに出力する。
【0491】
(ステップS620)
整数発生部523aは、メモリ521内の領域521jから整数eを読み出し、整数Mを2に設定し、領域521kに格納する。
【0492】
整数発生部523aは引き続き、上記の設定した整数Mと互いに素な正の整数kを発生させ、領域521gに格納する。
【0493】
整数発生部523aは更に、上記の設定した整数Mと、発生させた整数kとから、
1 =
k’k mod M
を満たす正の整数k’を発生させ、領域521hに格納する。
【0494】
秘密鍵入力部523bは、秘密鍵出力部522dが秘密鍵として出力した整数sを入力し、メモリ521内の領域521cに格納する。
【0495】
署名部523cは、領域521gに格納されている整数kと、領域521hに格納されている整数k’と、領域521aに格納されているパラメータxと、領域521cに格納されている秘密鍵である整数sと、領域521fに格納されているメッセージmと、領域521kに格納されている整数Mと、領域521bに格納されているパラメータNとを読み出し、
a=T(x) mod N
b=k’(sa+h(m)) mod M
により署名付メッセージ(a,b,m)を計算し、整数aを領域521dに、整数bを領域521eに、整数mを521fに格納する。
【0496】
署名付メッセージ送信部523dは、メモリ521内の領域521dに格納されている整数aと、領域521eに格納されている整数bと、領域521fに格納されている整数mを読み出し、署名付メッセージとして(a,b,m)をPC A510内の署名付メッセージ受信部513に送信する。
【0497】
(ステップS640)
PC A510の公開鍵受付部512は、PC B520の公開鍵公開部522cが公開した公開鍵Tを受け付け、メモリ511内の領域511cに格納する。
【0498】
署名付メッセージ受信部513は、PC B520の署名付メッセージ送信部523dが送信した署名付メッセージ(a,b,m)を受信し、整数aをメモリ511内の領域511dに、整数bを領域511eに、整数mを領域511fにそれぞれ格納する。
【0499】
整数計算部514は、メモリ511内の領域511dに格納されている整数aと、領域511eに格納されている整数bと、領域511fに格納されている整数mと、領域511aに格納されているパラメータxと、領域511cに格納されている公開鍵Tと、領域511bに格納されているパラメータNとを読み出し、ハッシュ関数hの計算により整数整数h(m)を計算し、更に整数Wを、記憶されている計算式により計算し、メモリ511内の領域511gに格納する。
【0500】
認証部515は、領域511gに格納された整数Wを読み出し、その値が0に等しい場合、署名付メッセージ(a,b,m)を認証する。
【0501】
(動作のまとめ)
本署名システム500において、PC B520が作成した署名付メッセージ(a,b,m)の第2成分bは、秘密鍵である整数sを知っている装置によってしか作成できない。このため、PC B520の作成した署名付メッセージをPC A510が認証するという本第5の実施形態は、電子署名システムとして用いることができる。
【0502】
(第5の実施形態の変形例)
本第5の実施形態では、PC B520が本発明の鍵対生成装置と署名装置を兼ねた形態であるが、変形例は、鍵対生成装置と署名装置とを別々の装置とする形態である。
【0503】
本変形例では、便宜上、図17を用いて説明すると、鍵対生成装置は、領域521a、521b、521c及び521iを有するメモリ、整数取得部522a、公開鍵計算部522b、公開鍵公開部522c、秘密鍵出力部522d等を備えた装置であり、署名装置に対応する部分としては、領域521d、521e、521f、521g、521h、521j及び521kを有するメモリ、整数発生部523a、秘密鍵入力部523b、署名部523c、署名付メッセージ送信部523d等を備えた装置である。
【0504】
鍵対生成装置の動作、及び、復号化装置の動作は、装置が分離したことに伴う違いを除けば、基本的には、第5の実施形態と同様である。
【図面の簡単な説明】
【0505】
【図1】図1は、本発明の第1の実施形態に係るパラメータ生成装置の構成を例示したブロック図である。
【図2】図2は、本発明の第1の実施形態に係るパラメータ生成装置の処理の全体を説明するためのフローチャートである。
【図3】図3は、図2のステップS100の詳細を説明するためのフローチャートである。
【図4】図4は、図2のステップS200の詳細を説明するためのフローチャートである。
【図5】図5は、本発明の第2の実施形態に係るパラメータ生成装置の構成を例示したブロック図である。
【図6】図6は、本発明の第2の実施形態に係るパラメータ生成装置の処理を説明するためのフローチャートである。
【図7】図7は、本発明の第3の実施形態に係る公開鍵暗号システムの構成を例示した模式図である。
【図8】図8は、本発明の第3の実施形態に係るコンピュータを用いて実現した第1の鍵共有装置の構成を例示したブロック図である。
【図9】図9は、本発明の第3の実施形態に係るコンピュータを用いて実現した送付鍵生成装置及び第2の鍵共有装置の構成を例示したブロック図である。
【図10】図10は、本発明の第3の実施形態に係る公開鍵暗号システムの処理の全体を説明するためのフローチャートである。
【図11】図11は、本発明の第4の実施形態に係る公開鍵暗号システムの構成を例示した模式図である。
【図12】図12は、本発明の第4の実施形態に係るコンピュータを用いて実現した暗号化装置の構成を例示したブロック図である。
【図13】図13は、本発明の第4の実施形態に係るコンピュータを用いて実現した鍵対生成装置及び復号化装置の構成を例示したブロック図である。
【図14】図14は、本発明の第4の実施形態に係る公開鍵暗号システムの処理の全体を説明するためのフローチャートである。
【図15】図15は、本発明の第5の実施形態に係る電子署名システムの構成を例示した模式図である。
【図16】図16は、本発明の第5の実施形態に係るコンピュータを用いて実現した認証装置の構成を例示したブロック図である。
【図17】図17は、本発明の第5の実施形態に係るコンピュータを用いて実現した鍵対生成装置及び署名装置の構成を例示したブロック図である。
【図18】図18は、本発明の第5の実施形態に係る電子署名システムの処理の全体を説明するためのフローチャートである。
【符号の説明】
【0506】
100 パラメータ生成装置
110 パラメータN格納部 120 第1の所定値格納部
130 計算部 140 出力部
150 第2の所定値格納部 160 メモリ
200 パラメータ生成装置
210 パラメータN格納部 220 第1の所定値格納部
230 計算部 240 出力部
250 第2の所定値格納部 260 メモリ
300 公開鍵暗号システム
310 PC A(第1の鍵共有装置)
311 メモリ 312 整数取得部
313 送付鍵計算部 314 送付鍵出力部
315 送付鍵入力部 316 共有鍵計算部
317 暗号化部 318 暗号化メッセージ送信部
320 PC B(送付鍵生成装置兼第2の鍵共有装置)
321 メモリ
322a 整数取得部 322b 送付鍵計算部
322c 第1送付鍵出力部 322d 第2送付鍵出力部
323a 第1送付鍵入力部 323b 第2送付鍵入力部
323c 共有鍵計算部 323d 暗号化メッセージ受信部
323e 復号化部
330 PC C(パラメータ生成装置)
340 インターネット
400 公開鍵暗号システム
410 PC A(暗号化装置)
411 メモリ 412 公開鍵受付部
413 整数取得部 414 暗号化部
415 暗号化メッセージ送信部
420 PC B(鍵対生成装置兼復号化装置)
421 メモリ
422a 整数取得部 422b 公開鍵計算部
422c 公開鍵公開部 422d 秘密鍵出力部
423a 暗号化メッセージ受信部 423b 秘密鍵入力部
423c 中間整数計算部 423d 復号化部
430 PC C(パラメータ生成装置)
440 インターネット
500 電子署名システム
510 PC A(認証装置)
511 メモリ 512 公開鍵受付部
513 署名付メッセージ受信部 514 整数計算部
515 認証部
520 PC B(鍵対生成装置兼署名装置)
521 メモリ
522a 整数取得部 522b 公開鍵計算部
522c 公開鍵公開部 522d 秘密鍵出力部
523a 整数発生部 523b 秘密鍵入力部
523c 署名部 523d 署名付メッセージ部
530 PC C(パラメータ生成装置)
540 インターネット




【特許請求の範囲】
【請求項1】
2冪剰余環Z/NZ(但し、N=2、wは3以上の整数)上でd次のチェビシェフ多項式T(x)を考えることにより構成される次数決定問題(但し、当該次数決定問題とは、パラメータNとパラメータxと(但し、xとNは整数、0≦x<N)と整数y(但し、0≦y<N)とから、y=T(x) mod Nを満たす正の整数dを求める問題とする。)を解くことを困難にするパラメータxを生成する生成装置であって、
前記パラメータNを格納するパラメータN格納部と、
第1の所定値を格納する第1の所定値格納部と、
前記パラメータN格納部に格納された前記パラメータNと前記第1の所定値格納部に格納された前記第1の所定値とを読み出して、
q=x−1 mod Nで定義される整数qが因数4の個数を前記第1の所定値以上有するという第1の条件を満たすパラメータxを計算して生成する計算部と、
前記計算部において生成された前記パラメータxを少なくとも出力する出力部と、
を有することを特徴とするパラメータ生成装置。
【請求項2】
請求項1に記載のパラメータ生成装置において、
更に、第2の所定値を格納する第2の所定値格納部を有し、
前記計算部は、前記パラメータN格納部に格納された前記パラメータNと前記第1の所定値格納部に格納された前記第1の所定値と第2の所定値格納部に格納された前記第2の所定値とを読み出して、前記第1の条件と、更に、x=T−1(x) mod Nを満たす2以上の最小の整数eが前記第2の所定値以上であるという第2の条件を満たすパラメータxを計算して生成するパラメータ生成装置。
【請求項3】
コンピュータ又は専用計算装置で実行される、2冪剰余環Z/NZ(但し、N=2、wは3以上の整数)上でd次のチェビシェフ多項式T(x)を考えることにより構成される次数決定問題(但し、当該次数決定問題とは、パラメータNとパラメータxと(但し、xとNは整数、0≦x<N)と整数y(但し、0≦y<N)とから、y=T(x) mod Nを満たす正の整数dを求める問題とする。)を解くことを困難にするパラメータxを生成する生成方法であって、
前記コンピュータ又は専用計算装置に格納された前記パラメータNと第1の所定値とを読み出す読み出し工程と、
q=x−1 mod Nで定義される整数qが因数4の個数を前記第1の所定値以上有するという第1の条件を満たすパラメータxを計算して生成する計算工程と、
前記計算工程において生成された前記パラメータxを少なくとも出力する出力工程と、
を有することを特徴とするパラメータ生成方法。
【請求項4】
請求項3に記載のパラメータ生成方法において、
前記読み出し工程は、更に、コンピュータ又は専用計算装置に格納された第2の所定値を読み出し、
前記計算工程は、前記第1の条件と、更に、x=T−1(x) mod Nを満たす2以上の最小の整数eが前記第2の所定値以上であるという第2の条件を満たすパラメータxを計算して生成するパラメータ生成方法。
【請求項5】
請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた鍵共有システムであって、
送付鍵生成装置と、第1の鍵共有装置と、第2の鍵共有装置とを有し、
前記送付鍵生成装置は、
正の整数sを取得する整数取得部と、
前記パラメータxと前記パラメータNと取得した前記整数sとから、
T=T(x) mod N
により送付鍵Tを計算する送付鍵計算部と、
計算された前記送付鍵Tを前記第1の鍵共有装置に出力する第1送付鍵出力部と、
前記整数sを送付鍵として前記第2の鍵共有装置に出力する第2送付鍵出力部と、
を有し、
前記第1の鍵共有装置は、
正の整数tを取得する整数取得部と、
前記整数tと前記パラメータxと前記パラメータNとから、
U=T(x) mod N
により送付鍵Uを計算する送付鍵計算部と、
計算された前記送付鍵Uを前記第2の鍵共有装置に出力する送付鍵出力部と、
前記送付鍵生成装置が出力した前記送付鍵Tを入力する送付鍵入力部と、
入力された前記送付鍵Tから、
V’=T(T) mod N
により共有鍵V’を計算する共有鍵計算部と、
を有し、
前記第2の鍵共有装置は、
前記第1の鍵共有装置が出力した前記送付鍵Uを入力する第1送付鍵入力部と、
前記送付鍵生成装置が送付鍵として出力した前記整数sを入力する第2送付鍵入力部と、
前記パラメータNと前記整数sと前記送付鍵Uとから、
V=T(U) mod N
により共有鍵Vを計算する共有鍵計算部と、
を有することを特徴とする鍵共有システム。
【請求項6】
請求項5に記載の鍵共有システムを用いた公開鍵暗号システムであって、
前記第1の鍵共有装置は、更に、
平文のメッセージを前記共有鍵V’により暗号化して暗号化メッセージを得る暗号化部と、
前記第2の鍵共有装置に前記暗号化メッセージを送信する暗号化メッセージ送信部と、
を有し、
前記第2の鍵共有装置は、更に、
前記第1の鍵共有装置が送信した前記暗号化メッセージを受信する暗号化メッセージ受信部と、
受信された前記暗号化メッセージを前記共有鍵Vにより復号化して、前記平文のメッセージを得る復号化部と、
を有することを特徴とする公開鍵暗号システム。
【請求項7】
請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた公開鍵暗号システムであって、
鍵対生成装置と、暗号化装置と、復号化装置とを有し、
前記鍵対生成装置は、
正の奇数である整数sを取得する整数取得部と、
取得した前記整数sと前記パラメータxと前記パラメータNとから、
T=T(x) mod N
により公開鍵Tを計算する公開鍵計算部と、
計算された前記公開鍵Tを前記暗号化装置に公開する公開鍵公開部と、
前記整数sを秘密鍵として前記復号化装置に出力する秘密鍵出力部と、
を有し、
前記暗号化装置は、
前記鍵対生成装置が公開した公開鍵Tを受け付ける公開鍵受付部と、
正の奇数である整数rを取得する整数取得部と、
奇数であるメッセージm(0<m<N)と取得した前記整数rと前記パラメータxと前記パラメータNとから、
=T(x) mod N
=mT(T) mod N
により整数の組である暗号化メッセージ(c,c)を計算する暗号化部と、
前記暗号化メッセージ(c,c)を前記復号化装置へ送信する暗号化メッセージ送信部と、
を有し、
前記復号化装置は、
前記暗号化装置が送信した前記暗号化メッセージ(c,c)を受信する暗号化メッセージ受信部と、
前記鍵対生成装置が秘密鍵として出力した前記整数sを入力する秘密鍵入力部と、
入力された前記整数sと受信された前記暗号化メッセージ(c,c)の第1成分cと前記パラメータNとから、
1=αT(c) mod N
を満たす中間整数αを求める中間整数計算部と、
受信された前記暗号化メッセージ(c,c)の第2成分cと前記中間整数αと前記パラメータNとから、
m’=αc mod N
によりメッセージm’を得る復号化部と、
を有することを特徴とする公開鍵暗号システム。
【請求項8】
請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた公開鍵暗号システムであって、
鍵対生成装置と暗号化装置と復号化装置を有し、
前記鍵対生成装置は、
正の整数sを取得する整数取得部と、
前記整数sと前記パラメータxと前記パラメータNとから、
T=T(x) mod N
により公開鍵Tを計算する公開鍵計算部と、
計算された前記公開鍵Tを前記暗号化装置に公開する公開鍵公開部と、
前記整数sを秘密鍵として前記復号化装置に出力する秘密鍵出力部と、
を有し、
前記暗号化装置は、
前記鍵対生成装置が公開した前記公開鍵Tを受け付ける公開鍵受付部と、
正の整数rを取得する整数取得部と、
整数であるメッセージm(0≦m<N)と前記整数rと前記パラメータxと前記パラメータNとから、
=T(x) mod N
=(T(T) mod N) xor m
により整数の組である暗号化メッセージ(c,c)を計算する暗号化部と、
前記暗号化メッセージ(c,c)を前記復号化装置へ送信する暗号化メッセージ送信部と、
を有し、
前記復号化装置は、
前記暗号化装置が送信した前記暗号化メッセージ(c,c)を受信する暗号化メッセージ受信部と、
前記鍵対生成装置が秘密鍵として出力した前記整数sを入力する秘密鍵入力部と、
入力された前記整数sと受信された前記暗号化メッセージ(c,c)と前記パラメータNとから、
m’=(T(c) mod N) xor c
によりメッセージm’を得る復号化部と、
を有することを特徴とする公開鍵暗号システム。
(但し、A xor Bは、2進数AとBのビット毎の排他的論理和演算を表わす。)
【請求項9】
請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた電子署名システムであって、
鍵対生成装置と、署名装置と、認証装置とを有し、
前記鍵対生成装置は、
正の整数sを取得する整数取得部と、
前記整数sと前記パラメータxと前記パラメータNとから、
T=T(x) mod N
により公開鍵Tを計算する公開鍵計算部と、
計算された前記公開鍵Tを前記認証装置に公開する公開鍵公開部と、
前記整数sを秘密鍵として前記署名装置に出力する秘密鍵出力部と、
を有し、
前記署名装置は、
整数Mを2の倍数であってN以下のものとし(eは、x=T−1(x) mod Nを満たす2以上の最小の整数)、Mと互いに素な正の整数kと、前記整数kから1
= k’k mod Mを満たす正の整数k’を発生させる整数発生部と、
前記鍵対生成装置が秘密鍵として出力した整数sを入力する秘密鍵入力部と、
前記パラメータxと前記パラメータNと整数sと整数であるメッセージm(0≦m<N)とから、
a=T(x) mod N
b=k’(sa+h(m)) mod M
(但し、h(m)は正の整数であって、m自身又はmのハッシュ関数値とする。)
により署名付メッセージ(a,b,m)を計算する署名部と、
前記署名付メッセージ(a,b,m)を前記認証装置へ送信する署名付メッセージ送信部と、
を有し、
前記認証装置は、
前記鍵対生成装置が公開した前記公開鍵Tを受け付ける公開鍵受付部と、
前記署名装置が送信した前記署名付メッセージ(a,b,m)を受信する署名付メッセージ受信部と、
受け付けられた前記公開鍵Tと前記受信された署名付メッセージ(a,b,m)と前記パラメータxと前記パラメータNから、前記整数h(m)を設定し整数Wを、
W=Th(m)(x)−2Th(m)(x)T(T)T(a)+T(T)+T(a)−1 mod N
により計算する整数計算部と、
前記整数Wが0に等しい場合、前記署名付メッセージ(a,b,m)を認証する認証部と、
を有することを特徴とする電子署名システム。
【請求項10】
請求項5に記載された鍵共有システムの送付鍵生成装置。
【請求項11】
請求項5に記載された鍵共有システムの第1の鍵共有装置。
【請求項12】
請求項5に記載された鍵共有システムの第2の鍵共有装置。
【請求項13】
請求項6に記載された公開鍵暗号システムの第1の鍵共有装置。
【請求項14】
請求項6に記載された公開鍵暗号システムの第2の鍵共有装置。
【請求項15】
請求項8に記載された公開鍵暗号システムの暗号化装置。
【請求項16】
請求項8に記載された公開鍵暗号システムの復号化装置。
【請求項17】
請求項9に記載された電子署名システムの署名装置。
【請求項18】
請求項9に記載された電子署名システムの認証装置。
【請求項19】
コンピュータ又は専用計算装置で実行される、請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いて共有鍵を生成するのに必要な送付鍵Tを生成する方法であって、
正の整数sを取得する整数取得工程と、
前記パラメータxと前記パラメータNと取得した前記整数sとから、
T=T(x) mod N
により送付鍵Tを計算する送付鍵計算工程と、
を有することを特徴とする送付鍵生成方法。
【請求項20】
コンピュータ又は専用計算装置で実行される、請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた鍵共有方法であって、
正の整数tを取得する整数取得工程と、
前記整数tと前記パラメータxと前記パラメータNとから、
U=T(x) mod N
により送付鍵Uを計算する送付鍵計算工程と、
計算された前記送付鍵Uを他の鍵共有装置に出力する送付鍵出力工程と、
請求項19に記載された送付鍵生成方法において生成された前記送付鍵Tを入力する送付鍵入力工程と、
入力された前記送付鍵Tから、
V’=T(T) mod N
により共有鍵V’を計算する共有鍵計算工程と、
を有することを特徴とする鍵共有方法。
【請求項21】
コンピュータ又は専用計算装置で実行される、請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxに対応するパラメータNを用いた鍵共有方法であって、
請求項20に記載の鍵共有方法において計算された前記送付鍵Uを入力する第1送付鍵入力工程と、
請求項19に記載された送付鍵生成方法において取得された前記整数sを送付鍵として入力する第2送付鍵入力工程と、
前記パラメータNと前記整数sと前記送付鍵Uとから、
V=T(U) mod N
により共有鍵Vを計算する共有鍵計算工程と、
を有することを特徴とする鍵共有方法。
【請求項22】
請求項20に記載された鍵共有方法を用いた暗号化方法であって、
更に、平文のメッセージを前記共有鍵V’により暗号化して暗号化メッセージを得る暗号化工程を有することを特徴とする暗号化方法。
【請求項23】
請求項21に記載された鍵共有方法を用いた復号化方法であって、
更に、請求項22に記載された暗号化された暗号化メッセージを前記共有鍵Vにより復号化して、前記平文のメッセージを得る復号化工程を有することを特徴とする復号化方法。
【請求項24】
コンピュータ又は専用計算装置で実行される、請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた鍵対生成方法であって、
正の整数sを取得する整数取得工程と、
取得した前記整数sと前記パラメータxと前記パラメータNとから、
T=T(x) mod N
により公開鍵Tを計算する公開鍵計算工程と、
計算された前記公開鍵Tを公開する公開鍵公開工程と、
前記整数sを秘密鍵として出力する秘密鍵出力工程と、
を有することを特徴とする鍵対生成方法。
【請求項25】
コンピュータ又は専用計算装置で実行される、請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた暗号化方法であって、
請求項24に記載された鍵対生成方法で前記整数sを奇数としたものにおいて公開され
た公開鍵Tを受け付ける公開鍵受付工程と、
正の奇数である整数rを取得する整数取得工程と、
奇数であるメッセージm(0<m<N)と取得した前記整数rと前記パラメータxと前記パラメータNとから、
=T(x) mod N
=mT(T) mod N
により整数の組である暗号化メッセージ(c,c)を計算する暗号化工程と、
を有することを特徴とする暗号化方法。
【請求項26】
コンピュータ又は専用計算装置で実行される、請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxに対応するパラメータNを用いた復号化方法であって、
請求項25に記載された暗号化方法において計算された前記暗号化メッセージ(c,c)を受信する暗号化メッセージ受信工程と、
請求項24に記載された鍵対生成方法で前記整数sを奇数としたものにおいて秘密鍵として出力された前記整数sを入力する秘密鍵入力工程と、
入力された前記整数sと受信された前記暗号化メッセージ(c,c)の第1成分cと前記パラメータNとから、
1=αT(c) mod N
を満たす中間整数αを求める中間整数計算工程と、
受信された前記暗号化メッセージ(c,c)の第2成分cと前記中間整数αと前記パラメータNとから、
m’=αc mod N
によりメッセージm’を得る復号化工程と、
を有することを特徴とする復号化方法。
【請求項27】
コンピュータ又は専用計算装置で実行される、請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた暗号化方法であって、
請求項24に記載された鍵対生成方法において公開された前記公開鍵Tを受け付ける公開鍵受付工程と、
正の整数rを取得する整数取得工程と、
整数であるメッセージm(0≦m<N)と前記整数rと前記パラメータxと前記パラメータNとから、
=T(x) mod N
=(T(T) mod N) xor m
により整数の組である暗号化メッセージ(c,c)を計算する暗号化工程と、
を有することを特徴とする暗号化方法。
【請求項28】
コンピュータ又は専用計算装置で実行される、請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxに対応するパラメータNを用いた復号化方法であって、
請求項27に記載された暗号化方法において計算された前記暗号化メッセージ(c,c)を受信する暗号化メッセージ受信工程と、
請求項24に記載された鍵対生成方法において秘密鍵として出力された前記整数sを入力する秘密鍵入力工程と、
入力された前記整数sと受信された前記暗号化メッセージ(c,c)と前記パラメータNとから、
m’=(T(c) mod N) xor c
によりメッセージm’を得る復号化工程と、
を有することを特徴とする復号化方法。
(但し、A xor Bは、2進数AとBのビット毎の排他的論理和演算を表わす。)
【請求項29】
コンピュータ又は専用計算装置で実行される、請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた署名方法であって、
整数Mを2の倍数であってN以下のものとし(eは、x=T−1(x) mod Nを満たす2以上の最小の整数)、Mと互いに素な正の整数kと、前記整数kから1
= k’k mod Mを満たす正の整数k’を発生させる整数発生工程と、
請求項24に記載された鍵対生成方法において秘密鍵として出力された整数sを入力する秘密鍵入力工程と、
前記パラメータxと前記パラメータNと整数sと整数であるメッセージm(0≦m<N)とから、
a=T(x) mod N
b=k’(sa+h(m)) mod M
(但し、h(m)は正の整数であって、m自身又はmのハッシュ関数値とする。)
により署名付メッセージ(a,b,m)を計算する署名工程と、
を有することを特徴とする署名方法。
【請求項30】
コンピュータ又は専用計算装置で実行される、請求項1に記載されたパラメータ生成装置、請求項2に記載されたパラメータ生成装置、請求項3に記載されたパラメータ生成方法及び請求項4に記載されたパラメータ生成方法のいずれかによって生成されたパラメータxと、パラメータNとを用いた認証方法であって、
請求項24に記載された鍵対生成方法において公開された前記公開鍵Tを受け付ける公開鍵受付工程と、
請求項29に記載された署名方法において計算された署名付メッセージ(a,b,m)を受信する署名付メッセージ受信工程と、
受け付けられた前記公開鍵Tと前記受信された署名付メッセージ(a,b,m)と前記パラメータxと前記パラメータNから、前記整数h(m)を設定し整数Wを、
W=Th(m)(x)−2Th(m)(x)T(T)T(a)+T(T)+T(a)−1 mod N
により計算する整数計算工程と、
前記整数Wが0に等しい場合、前記署名付メッセージ(a,b,m)を認証する認証工程と、
を有することを特徴とする認証方法。
【請求項31】
コンピュータを、
請求項1又は2に記載されたパラメータ生成装置、
請求項5に記載された鍵共有システムの送付鍵生成装置、
請求項5に記載された鍵共有システムの第1の鍵共有装置、
請求項5に記載された鍵共有システムの第2の鍵共有装置、
請求項6に記載された公開鍵暗号システムの第1の鍵共有装置、
請求項6に記載された公開鍵暗号システムの第2の鍵共有装置、
請求項7又は8に記載された公開鍵暗号システムの鍵対生成装置、
請求項6、7及び8のいずれか1項に記載された公開鍵暗号システムの暗号化装置、
請求項6、7及び8のいずれか1項に記載された公開鍵暗号システムの復号化装置、
請求項9に記載された電子署名システムの鍵対生成装置、
請求項9に記載された電子署名システムの署名装置、
若しくは請求項9に記載された電子署名システムの認証装置のいずれか1つとして機能させることを特徴とするプログラム。
【請求項32】
コンピュータに、
請求項3又は4に記載されたパラメータ生成方法、
請求項19に記載された送付鍵生成方法、
請求項20又は21に記載された鍵共有方法、
請求項22、25及び27のいずれか1項に記載された暗号化方法、
請求項23、26及び28のいずれか1項に記載された復号化方法、
請求項24に記載された鍵対生成方法、
請求項29に記載された署名方法、
若しくは請求項30に記載された認証方法のいずれか1つを実行させることを特徴とするプログラム。


【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate