(57)【特許請求の範囲】
【請求項１】
離散対数問題のパラメータを生成するパラメータ生成装置であって、
素数ｒのｆ（ｆ≧２）乗からなる素数冪ｑｊ（ｊ＝１，...，ｓ）の集合であって、当該素数冪ｑｊの組にそれぞれ対応するオイラー関数値の組の最大公約数が全て２となるものを生成し、生成した当該複数の素数冪ｑｊを出力する素数冪生成部と、
全てのｊについて、整数ｇの属する法ｑｊの剰余類の代表元が、上記素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の生成元となる当該整数ｇを生成し、生成した当該整数ｇを出力する生成元生成部と、
上記素数冪生成部で生成された全ての上記素数冪ｑｊの積である合成数Ｎを算出し、当該合成数Ｎを出力する合成数生成部と、
を有することを特徴とするパラメータ生成装置。
【請求項２】
請求項１に記載のパラメータ生成装置であって、
全てのｊについて上記素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の元である整数ｘを生成し、当該整数ｘを出力する真数生成部と、
上記素数冪ｑｊを法としてｇａｊ（ａｊはａｊを示す）と上記整数ｘとが合同となる整数ａｊの集合であって、その集合に属する全ての整数の組が２を法として合同となるものを生成し、当該整数ａｊを出力する補助対数生成部と、
全てのｊについて上記素数冪ｑｊのオイラー関数値を法として上記整数ａｊと合同な整数ａを生成し、当該整数ａを出力する対数生成部と、
を有することを特徴とするパラメータ生成装置。
【請求項３】
請求項１に記載のパラメータ生成装置であって、
上記生成元生成部は、
各ｊについて、整数ｇｊの属する法ｑｊの剰余類の代表元が、上記素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の生成元となる当該整数ｇｊを生成し、生成した当該整数ｇｊを出力する部分群生成元生成部と、
全てのｊについて上記素数冪ｑｊを法として上記整数ｇｊと合同な整数ｇを生成し、当該整数ｇを出力する群生成元生成部と、
を有することを特徴とするパラメータ生成装置。
【請求項４】
請求項２に記載のパラメータ生成装置であって、
上記真数生成部は、
全ての上記素数冪ｑｊと互いに素な整数ｙを生成し、当該整数ｙを出力する補助整数生成部と、
上記整数ｙを偶数冪乗した整数ｘを生成し、当該整数ｘを出力する冪乗部と、
を有することを特徴とするパラメータ生成装置。
【請求項５】
請求項１から４の何れかのパラメータ生成装置の出力値を用いて暗号鍵を生成する暗号鍵生成装置。
【請求項６】
離散対数問題のパラメータを生成するパラメータ生成方法であって、
素数冪生成部が、素数ｒのｆ（ｆ≧２）乗からなる素数冪ｑｊ（ｊ＝１，...，ｓ）の集合であって、当該素数冪ｑｊの組にそれぞれ対応するオイラー関数値の組の最大公約数が全て２となるものを生成し、生成した当該複数の素数冪ｑｊを出力するステップと、
生成元生成部が、全てのｊについて、整数ｇの属する法ｑｊの剰余類の代表元が、上記素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の生成元となる当該整数ｇを生成し、生成した当該整数ｇを出力するステップと、
合成数生成部が、上記素数冪生成部で生成された全ての上記素数冪ｑｊの積である合成数Ｎを算出し、当該合成数Ｎを出力するステップと、
を有することを特徴とするパラメータ生成方法。
【請求項７】
請求項６に記載のパラメータ生成方法において、
真数生成部が、全てのｊについて上記素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の元である整数ｘを生成し、当該整数ｘを出力するステップと、
補助対数生成部が、上記素数冪ｑｊを法としてｇａｊ（ａｊはａｊを示す）と上記整数ｘとが合同となる整数ａｊの集合であって、その集合に属する全ての整数の組が２を法として合同となるものを生成し、当該整数ａｊを出力するステップと、
対数生成部が、全てのｊについて上記素数冪ｑｊのオイラー関数値を法として上記整数ａｊと合同な整数ａを生成し、当該整数ａを出力するステップと、
を有することを特徴とするパラメータ生成方法。
【請求項８】
請求項１から４の何れかのパラメータ生成装置の出力値を用いて暗号鍵を生成する暗号鍵生成方法。
【請求項９】
請求項１から４の何れかに記載のパラメータ生成装置としてコンピュータを機能させるためのプログラム。
【請求項１０】
請求項５に記載の暗号鍵生成装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、離散対数の計算を利用したセキュリティ技術に関し、特に、合成数を法とした離散対数問題のパラメータを生成する技術に関する。
【背景技術】
【０００２】
ＲＳＡ暗号等の利用されている公開鍵暗号の多くは、量子計算機が実現化すると解読されてしまうことが知られている。一方、量子計算機が実現化されても解読が困難である公開鍵暗号として、２０００年に岡本、田中、内山らが提案した公開鍵暗号システム（以下では「ＯＴＵ暗号」と呼ぶ）がある（例えば、非特許文献１、特許文献１から３参照）。
ＯＴＵ暗号は、長期的に安全性を保証できることを期待できる公開鍵暗号方式であるが、鍵生成の過程において、素体上の離散対数問題を複数計算する必要がある。素体上の離散対数問題とは、素数ｐとｘ，g∈Zp×が与えられたときに、
x≡ga(mod p)  …(1)
を満たす整数ａを計算する問題である。なお、Ｚｐ×は、ｐと互いに素な０以上ｐ未満の整数の集合を意味する。ＯＴＵ暗号の場合、上記の式（１）におけるｇは固定となり、さらにｘはｐに比べて十分小さい整数になる。
【０００３】
しかし、現在利用されている計算機では、上記素数ｐのビット長が長い（例えば、１０２４ビット）離散対数問題を解くことは困難であることが知られている。つまり、ＯＴＵ暗号を現在の計算機で実現するのは容易ではない。そのため、ＯＴＵ暗号の鍵生成に必要な素体上の離散対数問題を、小さな素数のみで割り切れる合成数Ｎを法とした離散対数問題に置き換える方式（未公開）が考えられる。
【非特許文献１】T. Okamoto, K. Tanaka, S. Uchiyama "Quantum Public-Key Cryptosystem", LNCS 1880, pp 147-165, Springer-Verlag, 2000
【特許文献１】特許3615132号公報
【特許文献２】特許3615133号公報
【特許文献３】特許3615137号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、ＯＴＵ暗号の鍵生成に必要な素体上の離散対数問題を、小さな素数のみで割り切れる合成数Ｎを法とした離散対数問題に置き換えた場合、鍵生成処理を効率的に行うことが困難であるという問題点がある。以下にこの理由を述べる。
ＯＴＵ暗号の鍵生成方式では、g∈ZN×を１つ固定して、ｇを生成元とする巡回群＜ｇ＞に含まれる十分小さな整数ｘを用意する必要がある（なお、ＺＮ×は、０以上Ｎ未満であってＮと互いに素な整数の集合を意味する。）。ところが、どのようなg∈ZN×を選択しても、任意に選択した整数ｘがx∈<g>となる確率は低い。これは、ＺＮ×が巡回群でないことに起因する。例えば、N=Πj=1sqj（ｑｊは素数の冪乗である素数冪）とおいた場合、（ＺＮ×の位数）／（＜ｇ＞の位数）≧２ｓ−１であるため、任意に選択した整数ｘがx∈<g>となる確率は１／２ｓ−１以下となる。そして、選択した整数ｘが巡回群＜ｇ＞に含まれなかった場合、整数ｘを選択し直さなければならない。そのため、x∈<g>となる整数ｘを用意する場合、この整数ｘの選択し直しを平均２ｓ−１回以上行わなければならない。
【０００５】
また、x∈<g>であることの判定そのものに複数の離散対数の計算が必要である。以下に、この判定手順を例示する。
１．各ｊ（ｊ＝１，...，ｓ）に対して、
x≡gaj(mod qj)   …(2)
なる整数ａｊを求める。ただし、式（２）の上付き添え字のａｊは、ａｊを示す。
２．すべてのｖ，ｗ（１≦ｖ＜ｗ≦ｓを満たす自然数）について
av≡aw(mod gcd(φ(qv),φ(qw)))  …(3)
が成立しているか判定する。なお、ｇｃｄ（α，β）は、αとβとの最大公約数を示す。また、φ(α)は、１からαまでの正整数でαと互いに素となるものの個数を示すオイラー関数である。αが素数ｒをｆ乗した素数冪α=rfである場合、φ(α)=α(1-1/r)となる。
【０００６】
３．そして、式（３）が成立している場合、x∈<g>であると判断し、式（３）が成立していない場合、x∈<g>ではないと判断する。
以上のように、この判定手順を１回実行するためには、式（２）の離散対数の解を求めるための演算をｓ回行わなければならない。そのため、ＯＴＵ暗号の鍵生成に必要なx∈<g>となる整数ｘを１つ得るためには、平均２ｓ−１・ｓ回以上の離散対数計算が必要となる。よって、任意に合成数Ｎ及び整数ｇを選択したのでは、x∈<g>となる整数ｘを特定するために長い時間を要してしまう。
【０００７】
このような問題は、上述の鍵生成に限らず、合成数Ｎを法とした離散対数問題x≡ga(mod N)においてx∈<g>となる整数ｘを特定する処理が必要な用途に共通するものである。
本発明はこのような点に鑑みてなされたものであり、合成数Ｎを法とした離散対数x≡ga(mod N)においてx∈<g>となる整数ｘを効率的に特定することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
第１の本発明では上記課題を解決するために、素数冪生成部が、素数の冪乗からなる素数冪ｑｊ（ｊ＝１，...，ｓ）の集合であって、当該素数冪ｑｊの組にそれぞれ対応するオイラー関数値の組の最大公約数が全て２となるもの〔全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対してgcd(φ(qv),φ(qw))=2〕を生成し、生成した当該複数の素数冪ｑｊを出力する。また、生成元生成部が、全てのｊについて、整数ｇの属する法ｑｊの剰余類の代表元〔g mod qj〕が、素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合〔Ｚｑｊ×（下付添え字のｑｊはｑｊを示す）〕の生成元となる当該整数ｇを生成し、生成した当該整数ｇを出力する。そして、合成数生成部が、素数冪生成部で生成された全ての素数冪ｑｊの積である合成数Ｎ〔N=Πj=1sqj〕を算出し、当該合成数Ｎを出力する。
【０００９】
ここで、全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対してgcd(φ(qv),φ(qw))=2が成立している。そして、合成数生成部が生成する合成数Ｎは、N=Πj=1sqjである。この場合、ＺＮ×の巡回部分群の位数を最大値化することができる（詳細は後述）。また、g mod qjがＺqj×の生成元となっている。この場合、当該整数ｇは、ＺＮ×の巡回部分群のうち位数が最大のものの生成元となっている（詳細は後述）。すなわち、当該整数ｇを生成元とする巡回群＜ｇ＞の位数は最大となり、（ＺＮ×の位数）／（＜ｇ＞の位数）の比率を最小化することができる。よって、任意に整数x∈ZN×を選択した場合にx∈<g>となる確率を最大にすることができる。
【００１０】
また、第１の本発明において好ましくは、真数生成部が、全てのｊについて素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の元である整数ｘ〔x∈Zqj×〕を生成し、当該整数ｘを出力し、補助対数生成部が、素数冪ｑｊを法としてｇａｊ（ａｊはａｊを示す）と整数ｘとが合同〔x≡gaj(mod qj)〕となる整数ａｊの集合であって、その集合に属する全ての整数の組が２を法として合同〔全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対してav≡aw(mod 2)〕となるものを生成し、当該整数ａｊを出力する。そして、対数生成部が、全てのｊについて素数冪ｑｊのオイラー関数値を法として整数ａｊと合同な整数ａ〔a≡ajmod φ(qj)〕を生成し、当該整数ａを出力する。第１の本発明において、これらの処理を行うことにより、x∈<g>となる（詳細は後述）。
【００１１】
また、第１の本発明において好ましくは、生成元生成部は、各ｊについて、整数ｇｊの属する法ｑｊの剰余類の代表元〔gj mod qj〕が、素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合〔Ｚｑｊ×〕の生成元となる当該整数ｇｊを生成し、全てのｊについて素数冪ｑｊを法として当該整数ｇｊと合同な整数ｇ〔g≡gj(mod qj)〕を生成する。
このような手順で生成された整数ｇは、g mod qjがＺｑｊ×の生成元となるという条件を満たしている。よって、上述したのと同様、任意に整数x∈ZN×を選択した場合にx∈<g>となる確率を最大にすることができる。
【００１２】
また、第１の本発明において好ましくは、真数生成部は、全ての素数冪ｑｊと互いに素な整数ｙを生成し、整数ｙを偶数冪乗した値を整数ｘとする。この場合、x=y2=gaj mod qjを満たす整数ａｊが存在する。また、x=y2=gajmod qjを満たす各整数ａｊは必ず偶数となり、全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対してav≡aw(mod 2)を満たす。この場合、必ずx∈<g>となる（詳細は後述）。
また、第２の本発明では、上述の何れかのパラメータ生成装置の出力値を用いて暗号鍵を生成する。例えば、素数冪生成部が、素数の冪乗からなる素数冪ｑｊ（ｊ＝１，...，ｓ）の集合であって、当該素数冪ｑｊの組にそれぞれ対応するオイラー関数値の組の最大公約数が全て２となるものを生成し、生成元生成部が、全てのｊについて、整数ｇの属する法ｑｊの剰余類の代表元が、素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の生成元となる当該整数ｇを生成する。そして、真数生成部が、全てのｊについて素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の元である整数ｘｉの集合あって、その集合に属する全ての整数の組が互いに素となるものを生成し、補助対数生成部が、素数冪ｑｊを法としてｇａ（ｉ，ｊ）〔上付き添え字のａ（ｉ，ｊ）はａｉ，ｊを示す〕と整数ｘｉとが合同となる整数ａｉ，ｊの集合であって、その集合に属する全ての整数の組が２を法として合同となるものを生成し、当該整数ａｉ，ｊを出力する。また、対数生成部が、全てのｊについて素数冪ｑｊのオイラー関数値を法として整数ａｉ，ｊと合同な整数ａｉをｉ毎に生成し、当該整数ａｉを出力し、関数演算部が、整数ａｉを変数とした関数値ｂｉを生成し、当該関数値ｂｉを出力し、合成数生成部が、素数冪生成部で生成された全ての素数冪ｑｊの積である合成数Ｎを算出し、当該合成数Ｎを出力する。そして、少なくともｂ１，...，ｂｎを含む情報を公開鍵とし、少なくともＮ，ｘ1，...，ｘｎ，ｇを含む情報を秘密鍵とする。
【００１３】
これにより、xi∈<g>となる整数ｘｉを効率的に特定することができ、公開鍵と暗号鍵とを効率良く生成することができる。
【発明の効果】
【００１４】
以上のように、本発明では、合成数Ｎを法とした離散対数x≡ga(mod N)においてx∈<g>となる整数ｘを効率的に特定することが可能となる。
【発明を実施するための最良の形態】
【００１５】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
〔原理〕
まず、本発明を実施するための最良の形態の原理について説明する。
［与える条件］
本形態では、離散対数問題x≡ga(mod N)を構成する合成数Ｎ
【数１】
0004676873.tif 000002
に以下の条件を与える。
【００１６】
＜条件１＞
全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対して、gcd(φ(qv),φ(qw))=2が成立する。なお、ｖ，ｗ，ｓは自然数である。
また、離散対数問題x≡ga(mod N)を構成するｇに以下の条件を与える。
＜条件２＞  
各ｊ（ｊ＝１，....，ｓ）において、g mod qjがＺｑｊ×の生成元となっている。なお、Ｚｑｊ×の下付き添え字のｑｊはｑｊを示す。
また、離散対数問題x≡ga(mod N)を構成するｘに以下の条件を与える。
＜条件３＞
(a)各ｊ（ｊ＝１，....，ｓ）に対して、x≡gaj(mod qj)となる整数ａｊが存在する。なお、ｇａｊの上付き添え字ａｊはａｊを示す。
(b)全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対して、av≡aw(mod gcd(φ(qv),φ(qw)))が成立する。なお、φ（ｑｖ）及びφ（ｑｗ）は、それぞれ、g(mod qv)及びg(mod qw)を生成元とする巡回群の元の個数を示すことになる。
なお、＜条件１＞＜条件２＞＜条件３＞の全てが満たされている場合に限らず、＜条件１＞＜条件２＞及び＜条件３＞の一方を満たす構成であってもよい。
特に、＜条件１＞が満たされている場合、＜条件３＞は、以下のように換言できる。
【００１７】
＜条件３’＞
(a)各ｊ（ｊ＝１，....，ｓ）に対してx≡gaj(mod qj)となる整数ａｊが存在する。なお、ｇａｊの上付き添え字ａｊはａｊを示す。また、ｘ∈Ｚｑｊ×である。
(b)全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対して、av≡aw(mod 2)が成立する。
さらに、＜条件２＞が満たされている場合、＜条件３’＞の(a)が保証される。すなわち、各ｊにおいてg mod qjがＺｑｊ×の生成元である場合、当然、ｘ∈Ｚｑｊ×に対してx≡gaj(mod qj)となる整数ａｊが存在する。よって、この場合、＜条件３’＞は、以下のように換言できる。
＜条件３’’＞
全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対して、av≡aw(mod 2)が成立する。
【００１８】
［得られる効果］
次に、上記の条件を満たすことにより得られる効果について説明する。
＜条件１により得られる効果＞
一般に、合成数Ｎの素因数分解が上述の式（４）で表されるとき、g∈ZN×を生成元とする巡回群＜ｇ＞の位数は、lcm{φ(qj);1≦j≦s}以下であることが知られている（例えば、「岡本龍明、山本博資、”現代暗号”、Ｐ１７、産業図書、１９９７年」参照）。なお、lcm{α,β,γ....}は、α，β，γ....の最小公倍数を表す。
【００１９】
また、φ（ｑｊ）は、オイラー関数であり、ｑｊが素数ｒをｆ乗（ｆ≧２）した素数冪qj=rfである場合、
φ(qj)=qj(1-1/r) …(5)
が成立する。ここで、qj=rfを式(5)に代入して変形すると
φ(qj)=rf(1-1/r)=rf-1(r-1) …(6)
となる。ここでｒは素数であるからｒ≠２である場合には必ず奇数となり、r-1は必ず偶数となる。また、r=2の場合にはrf-1=2f-1となり、rf-1は必ず偶数となる。よって、式(5)は偶数となり、φ（ｑｊ）は必ず２の倍数となる。そして、φ（ｑｊ）は必ず２の倍数であるため、オイラー関数値φ（ｑｊ）は、
φ(qj)=2rj …(7)
と表すことができる。
【００２０】
以上より、g∈ZN×を生成元とする巡回群＜ｇ＞の位数は、
lcm{φ(qj) ; 1≦j≦s}=2lcm{rj; 1≦j≦s}  …(8)
以下となる。
ここで、上述の＜条件１＞が成立する場合、式(7)より、全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対して、gcd(rv, rw)=1が成立するといえる。よって、
【数２】
0004676873.tif 000003
が成立する。
一方、上述の＜条件１＞が成立しない場合、式(7)より、ある自然数ｈ（ｈ＞１）が存在し、
gcd(φ(qv),φ(qw))=2h   …(10)
が成立するといえる。このとき、gcd(rv, rw)=hとなり、
【数３】
0004676873.tif 000004
が成立する。この値は、上述の＜条件１＞が成立する場合の式(9)の値を下回る。
以上より、＜条件１＞が成立する場合、g∈ZN×を生成元とする巡回群＜ｇ＞の位数は最大値lcm{φ(qj);1≦j≦s}となり、ZN×の巡回部分群の位数を最大値化できることが分かる。
【００２１】
＜条件２により得られる効果＞
＜条件２＞を満たすように整数ｇを選択した場合、g mod qjを生成元とする巡回群の位数はＺｑｊ×の位数、すなわちφ（ｑｊ）となる。ここで、g mod Nを生成元としたＺＮ×における巡回部分群の位数は、g mod qjを生成元とする巡回群の位数φ（ｑｊ）の最小公倍数lcm{φ(qj);1≦j≦s}となる。これは、前述したg∈ZN×を生成元とする巡回群＜ｇ＞の位数の最大値lcm{φ(qj);1≦j≦s}と一致する。したがって、＜条件２＞を満たすように選択した整数ｇは、ZN×内の最大巡回部分群を生成することになる。
すなわち＜条件１＞及び＜条件２＞を満たすように合成数Ｎ及び整数ｇを選択した場合、任意に選択した整数ｘに対し、x∈<g>となる確率を最大値化することができる。
【００２２】
＜条件３により得られる効果＞
＜条件３＞の(b)が成立する場合、x≡ga(mod N)となる整数ａが存在することになる。これは、ｘ∈＜ｇ＞となることを意味する。すなわち、＜条件３＞や＜条件３’＞や＜条件３’’＞を満たすようにｘを選択した場合、必ずｘ∈＜ｇ＞となる。
〔第１の実施の形態〕
次に、本発明における第１の実施の形態について説明する。本形態は、上述の＜条件１＞＜条件２＞＜条件３’’＞を満たすように合成数Ｎ、整数ｇ，ａを生成していく形態である。
【００２３】
＜ハードウェア構成＞
図１は、本形態におけるパラメータ生成装置１００のードウェア構成を例示したブロック図である。
図１に例示するように、この例のパラメータ生成装置１００は、ＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６及びバス１７を有している。
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２は、データが入力される入力インタフェース、キーボード、マウス等であり、出力部１３は、データが出力される出力インタフェース、液晶ディスプレイ等である。補助記憶装置１４は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、パラメータ生成装置１００としてコンピュータを機能させるためのプログラムが格納されるプログラム領域１４ａ及び各種データが格納されるデータ領域１４ｂを有している。また、ＲＡＭ１６は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、上記のプログラムが格納されるプログラム領域１６ａ及び各種データが格納されるデータ領域１６ｂを有している。また、バス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５及びＲＡＭ１６を通信可能に接続する。なお、このようなハードウェアの具体例としては、パーソナルコンピュータ等を例示できる。
【００２４】
＜プログラム構成＞
パラメータ生成装置１００としてコンピュータを機能させるためのプログラムは、各処理を実現するための複数のプログラムから構成される。これらのプログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。また、各プログラム単体でそれぞれの機能を実現できるものでもよいし、各プログラムがさらに他のライブラリを読み出して各機能を実現するものであってもよい。
【００２５】
＜ハードウェアとプログラムとの協働＞
ＣＰＵ１１（図１）は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４のプログラム領域１４ａに格納されている上述のプログラムをＲＡＭ１６のプログラム領域１６ａに書き込む。同様にＣＰＵ１１は、補助記憶装置１４のデータ領域１４ｂに格納されている各種データを、ＲＡＭ１６のデータ領域１６ｂに書き込む。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ａに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。
【００２６】
図２は、このようにＣＰＵにプログラムが読み込まれることにより構成される第１の実施の形態のパラメータ生成装置１００の機能構成を説明するためのブロック図である。
図２に示すように、本形態のパラメータ生成装置１００は、離散対数問題x≡ga(mod N)を構成する合成数Ｎ及び整数ｇを生成する巡回群生成部１１０、整数ｘを生成する真数生成部１２０、整数ａを求める離散対数計算部１３０、メモリ１４０、制御部１５０、一時メモリ１６０及びカウント部１７０を有している。
ここで、巡回群生成部１１０は、素数冪生成部１１１、生成元生成部１１２及び合成数生成部１１３を有している。なお、素数冪生成部１１１は、擬似乱数生成部１１１ａ、素数判定部１１１ｂ、冪乗部１１１ｃ及び素数冪選択部１１１ｄを有している。また、生成元生成部１１２は、整数生成部１１２ａａと判定部１１２ａｂとを具備する部分群生成元生成部１１２ａ、及び群生成元生成部１１２ｂを有している。また、真数生成部１２０は、補助整数生成部１２１及び冪乗部１２２を有し、離散対数計算部１３０は、補助対数生成部１３１及び対数生成部１３２を有している。さらに、メモリ１４０は、各種情報を格納するための領域１４１から１４９を有している。
【００２７】
なお、メモリ１４０及び一時メモリ１６０は、補助記憶装置１４のデータ領域１４ｂ、ＲＡＭ１６のデータ領域１６ｂ、ＣＰＵ１１のレジスタ１１ｃ、その他のバッファメモリやキャッシュメモリ等の何れか、或いはこれらを併用した記憶領域に相当する。また、巡回群生成部１１０、真数生成部１２０、離散対数計算部１３０、制御部１５０及びカウント部１７０は、上述のようにＣＰＵ１１にプログラムが読み込まれることによって構成されるものである。また、図２における矢印はデータの流れを示しているが、制御部１５０、一時メモリ１６０及びカウント部１７０に入出力するデータの流れの記載は省略してある。
【００２８】
＜処理＞
次に、第１の実施の形態の処理を説明する。
図３は、第１の実施の形態の処理の全体を説明するためのフローチャートである。また、図４は、図３のステップＳ１の詳細を説明するためのフローチャートである。また、図５は、図３のステップＳ２の詳細を説明するためのフローチャートである。また、図６は、図３のステップＳ４の詳細を説明するためのフローチャートである。以下、図２から図６を用い、本形態の処理を説明する。なお、以下に述べる各処理は、制御部１５０の制御のもと実行される。また、特に明示しない限り、各演算処理によって得られたデータは逐一一時メモリ１６０に格納され、格納された各データはその後の演算処理に利用される。
【００２９】
＜前処理＞
まず、前処理として、３つの整数ｓ，ｂｌｅｎ１，ｂｌｅｎ２がメモリ１４０の領域１４１に格納される。なお、整数ｓ，ｂｌｅｎ１，ｂｌｅｎ２は、例えば、図１に例示した入力部１２から入力されたデータである。
＜巡回群生成部１１０の処理＞
上記のような前処理を前提とし巡回群生成部１１０による処理が実行される。
まず、素数冪生成部１１１が、メモリ１４０の領域１４１から整数ｓ，ｂｌｅｎ１を読み込み、素数の冪乗からなるビット長ｂｌｅｎ１の素数冪ｑｊ（ｊ＝１，...，ｓ）の集合であって、当該素数冪ｑｊの組にそれぞれ対応するオイラー関数値φ（ｑｊ）の組の最大公約数が全て２となるものを生成し、生成した当該複数の素数冪ｑｊを出力し、メモリ１４０の領域１４２に格納する（ステップＳ１）。以下、このステップＳ１の詳細について説明する。
【００３０】
［ステップS１の詳細］
まず、素数冪生成部１１１が、ビット長ｂｌｅｎ１の素数冪ｑ１を生成する（図４／ステップＳ１１）。
具体的には、例えばまず、擬似乱数生成部１１１ａが、ＳＨＡ-１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用い、擬似乱数を発生させる。そして、擬似乱数生成部１１１ａは、当該擬似乱数から、ビット長ｂｌｅｎ１の素数冪q1=rfを構成する整数ｒ及びｆ（ｆ≧２）を生成し、当該整数ｒ及びｆを一時メモリ１６０に格納する。次に、素数判定部１１１ｂが、一時メモリ１６０から当該整数ｒを読み込み、AKS素数判定法、フェルマーテスト、Miller-Rabinテスト等の公知の素数判定手順によって、当該整数ｒが素数である（又はその可能性が高い）か否かを判断する。そして、当該整数ｒが素数でないと判断された場合には、整数ｒが素数である（又はその可能性が高い）と判定されるまで、擬似乱数生成部１１１ａによって整数ｒ及びｆを生成し直す。そして、整数ｒが素数である（又はその可能性が高い）と判定された場合、冪乗部１１１ｃが一時メモリから最新の整数ｒ及びｆを読み込み、素数冪q1=rfを生成し、これをメモリ１４０の領域１４２に格納する。
【００３１】
次に、カウント部１７０が、変数ｊに２を代入し、これを一時メモリ１６０に格納する（ステップＳ１２）。そして、素数冪生成部１１１が、一時メモリ１６０から変数ｊを読み込み、メモリ１４０の領域１４２から全ての素数冪ｑｕ（１≦ｕ≦ｊ−１）を読み込み、全ての素数冪ｑｕに対してgcd(φ(qu),φ(qj))=2となり、ビット長がｂｌｅｎ１の素数冪ｑｊを生成し、これをメモリ１４０の領域１４２に格納する（ステップＳ１３）。具体的には、例えば、ステップＳ１１と同様に擬似乱数生成部１１１ａ、素数判定部１１１ｂ及び冪乗部１１１ｃによって素数冪ｑｊを生成し、素数冪選択部１１１ｄが、全ての素数冪ｑｕに対してgcd(φ(qu),φ(qj))=2であるか否かを判定する。そして、素数冪選択部１１１ｄが、全ての素数冪ｑｕに対してgcd(φ(qu),φ(qj))=2であると判定するまで、素数冪ｑｊの生成と当該判定とを繰り返し、全ての素数冪ｑｕに対してgcd(φ(qu),φ(qj))=2であると判定された素数冪ｑｊを出力し、メモリ１４０の領域１４２に格納する。なお、最大公約数を求める方法としては、例えば、ユークリッドの互助法（例えば、「A. J. Menezes, P. C. van Oorschot, S. A. Vanstone "Handbook of Applied Cryptography" pp 66., CRC Press,1997」等参照）等を用いる。
【００３２】
次に、制御部１５０が、メモリ１４０の領域１４１から整数ｓを読み込み、一時メモリ１６０から変数ｊを読み込み、ｊ＝ｓであるか否かを判定する（ステップＳ１４）。ここで、ｊ＝ｓでないと判断された場合、制御部１５０は、カウント部１７０に指示を与え、カウント部１７０は、変数ｊに１を加算した値を新たな変数ｊし、これを一時メモリ１６０に格納する（ステップＳ１５）。そして、制御部１５０は、処理をステップＳ１３に戻す。一方、ｊ＝ｓであると判断された場合、制御部１５０は、ステップＳ１の処理を終了させる（［ステップＳ１の詳細］の説明終わり）。
【００３３】
ステップＳ１の終了後、生成元生成部１１２が、メモリ１４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、全てのｊについて、整数ｇの属する法ｑｊの剰余類の代表元が、素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の生成元となる〔＜g mod qj＞=Zqj×〕当該整数ｇを生成し、生成した当該整数ｇを出力し、メモリ１４０の領域１４４に格納する（ステップＳ２）。以下、このステップＳ２の詳細について説明する。
【００３４】
［ステップＳ２の詳細］
まず、カウント部１７０が変数ｊに１を代入し、これを一時メモリ１６０に格納する（図５／ステップＳ２１）。次に、整数生成部１１２ａａが、擬似乱数等により任意の整数ｇｊを生成し、これを一時メモリ１６０に格納する（ステップＳ２２）。次に、判定部１１２ａｂが、メモリ１４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、さらに、一時メモリ１６０から整数ｇｊを読み込み、
<gj mod qj>=Zqj×  …(12)
を満たすか否か（整数ｇｊの属する法ｑｊの剰余類の代表元が、素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の生成元となるか否か）を判断する（ステップＳ２３）。この判定は、例えば、判定部１１２ａが<gj mod qj>の位数を計算し、その値とZqj×の位数であるφ（ｑｊ）とが一致するか否かによって行う。<gjmod qj>の位数を計算する方法としては、例えば、A. J. Menezes, P. C. van Oorschot, S. A. Vanstone "Handbook of Applied Cryptografhy"., CRC Press,1997の163ページに記載された方法等を用いる。ここで、式(12)を満たさないと判断された場合、制御部１５０は、処理をステップＳ２２に戻す。
【００３５】
一方、ステップＳ２３において、式(12)を満たすと判断された場合、部分群生成元生成部１１２ａは、一時メモリ１６０から整数ｇｊを読み込み、これを出力する（ステップＳ２４）。出力された整数ｇｊは、メモリ１４０の領域１４３に格納される。さらに制御部１５０は、一時メモリ１６０から変数ｊを読み込み、メモリ１４０の領域１４１から整数ｓを読み込み、ｊ＝ｓを満たすか否かを判断する（ステップＳ２５）。ここで、ｊ＝ｓを満たさないと判断した場合、制御部１５０は、カウント部１７０に指示を与え、カウント部１７０は、変数ｊに１を加えた値を新たな変数ｊの値とし、この変数ｊを一時メモリ１６０に格納する（ステップＳ２６）。そして、制御部１５０は、処理をステップＳ２２に戻す。
【００３６】
一方、制御部１５０は、ステップＳ２５において、ｊ＝ｓを満たすと判断した場合、群生成元生成部１１２ｂに指示を与え、これを受けた群生成元生成部１１２ｂは、メモリ１４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、さらに、領域１４３から整数ｇｊ（ｊ＝１，...，ｓ）を読み込む。そして、群生成元生成部１１２ｂは、全てのｊについて素数冪ｑｊを法として整数ｇｊと合同な整数ｇ〔g≡gj (mod qj)〕を生成し（ステップＳ２７）、当該整数ｇを出力する（ステップＳ２８）。具体的には、群生成元生成部１１２ｂは、例えば、GaussやGarnarのアルゴリズムとして知られている手順により、g≡gj(mod qj)を満たす整数ｇを生成する（例えば、「A. J. Menezes, P. C. van Oorschot, S. A. Vanstone "Handbook of Applied Cryptography" pp 612-613., CRC Press,1997」等参照）。また、得られた整数ｇは、メモリ１４０の領域１４４に格納される（［ステップＳ２の詳細］の説明終わり）。
【００３７】
次に、合成数生成部１１３が、メモリ１４０の領域１４２から全ての素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、それらの素数冪ｑｊの積である合成数Ｎを以下のように算出し、当該合成数Ｎを出力する（ステップＳ３）。なお、出力された合成数Ｎは、メモリ１４０の領域１４５に格納される。
【数４】
0004676873.tif 000005
以上のように生成された素数冪ｑｊ（ｊ＝１，...，ｓ）及び整数ｇは、前述の＜条件１＞＜条件２＞を満たす。よって、整数ｇを生成元とする巡回部分群＜ｇ＞は、ＺＮ×において位数が最大となる巡回部分群であり、（ＺＮ×の位数）／（＜ｇ＞の位数）＝２ｓ−１となる。
【００３８】
＜真数生成部１２０の処理＞
次に、真数生成部１２０の処理を説明する。
上記のような巡回群生成部１１０の処理の終了後、真数生成部１２０が、メモリ１４０の領域１４１からｂｌｅｎ２を読み込み、領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、これらを用い、全てのｊについて、素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の元である整数ｘを生成し、当該整数ｘを出力する（ステップＳ４）。なお、出力された整数ｘは、メモリ１４０の領域１４７に格納される。以下、このステップＳ４の詳細について説明する。
【００３９】
［ステップＳ４の詳細］
まず、補助整数生成部１２１が、メモリ１４０の領域１４１からｂｌｅｎ２を読み込み、領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込む。そして、補助整数生成部１２１は、全ての素数冪ｑｊと互いに素なビット長ｂｌｅｎ２／２ｅ（ｅは自然数／例えばｅ＝１）の整数ｙを生成し、当該整数ｙを出力する（図６／ステップＳ３１）。出力された整数ｙは、メモリ１４０の領域１４６に格納される。次に、冪乗部１２２が、メモリ１４０の領域１４６から整数ｙを読み込み、当該整数ｙを偶数冪乗した整数ｘ（ｘ＝ｙ２ｅ）を生成し、当該整数ｘを出力する（ステップＳ３２）。出力された整数ｘは、メモリ１４０の領域１４７に格納される。
【００４０】
このステップＳ３１，Ｓ３２のように整数ｘを生成することにより、前述の＜条件３’’＞を満たすことになり、x∈<g>を満たすことになる。すなわち、前述のように本形態は＜条件１＞を満たすため、各ｊ（ｊ＝１，....，ｓ）に対してx≡gaj(mod qj)となる整数ａｊが存在する。また、ステップＳ３２で生成された整数ｘは、ｘ＝ｙ２ｅを満たす。また、ｙは全ての素数冪ｑｊと互いに素であるから、y mod qj∈Ｚqj×を満たす。そして、g(mod qj)はＺqj×の生成元である（ステップＳ２３）からｙ≡gaj’(mod qj)を満たす整数ａｊ’は必ず存在する。よって、x≡gaj(mod qj)すなわちx≡y2e≡g2eaj’≡gaj(mod qj)を満たす整数ａｊ’は必ず偶数となる。そのため、全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対して、av≡aw(mod 2)が成立することになり＜条件３’’＞を満たす。さらに、本形態では＜条件２＞も満たしているのであるから、x∈<g>を満たすといえる（［ステップＳ４の詳細］の説明終わり）。
【００４１】
＜離散対数計算部１３０の処理＞
次に、離散対数計算部１３０の処理を説明する。
まず、補助対数生成部１３１が、メモリ１４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、領域１４４から整数ｇを読み込み、領域１４７から整数ｘを読み込む。そして、補助対数生成部１３１は、各ｊについて
x≡gaj (mod qj)  …(14)
を満たす整数ａｊを算出する（ステップＳ５）。なお、本形態では、上述のステップＳ３１，Ｓ３２のように整数ｘを選択しているため＜条件３’’＞を満たしており、算出された各整数ａｊの全ての組は、２を法として合同〔全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対して、av≡aw(mod 2)〕となっている。また、式(14)を満たす整数ａｊの算出は、例えば、数体ふるい法やＰollardのρ法等（例えば、「岡本龍明，山本博資著，“現代暗号”，第２刷，ISBN4-7828-5353-X- C3355，p21」等参照）を用いる。これによって、少ない演算量で整数ａｊを求めることが可能となる。算出された整数ａｊ（ｊ＝１，...，ｓ）は、補助対数生成部１３１から出力され、メモリ１４０の領域１４８に格納される。
【００４２】
次に、対数生成部１３２が、メモリ１４０の領域１４８から各整数ａｊ（ｊ＝１，...，ｓ）を読み込み、全てのｊについて
a≡aj(mod φ(qj))   …(15)
を満たす整数ａを算出し、当該整数ａを出力する（ステップＳ６）。そして、出力された整数ａは、メモリ１４０の領域１４９に格納される。なお、この整数ａの算出は、例えば、GaussやGarnarのアルゴリズムとして知られている手順によって行う（例えば、「A. J. Menezes, P. C. van Oorschot, S. A. Vanstone "Handbook of Applied Cryptography" pp 612-613., CRC Press,1997」等参照）。
【００４３】
＜本形態の特徴＞
以上により、素数冪ｑｊの積である合成数Ｎを法とした離散対数問題x≡ga(mod N)を構成する整数ｘ，ｇ、合成数Ｎ及び解である整数ａを生成することができた。そして、上述のように合成数Ｎは＜条件１＞を満たし、整数ｇは＜条件２＞を満たし、さらに解ａは＜条件３’’＞を満たすものとなった。そして、ｘ∈＜ｇ＞であるか否かの判定を行うことなく、簡単な計算によってｘ∈＜ｇ＞を満たすｘを生成することが可能となった。そして、このように生成された整数ｘ，ｇ、合成数Ｎ及び解である整数ａは、必要に応じてメモリ１４０から読み出され、例えば、ＯＴＵ暗号の暗号鍵生成等に利用することができる。
【００４４】
〔第２の実施の形態〕
次に、本発明の第２の実施の形態について説明する。本形態は、Ｚｑｊ×の生成元の偶数冪乗の整数ｇ’を生成する形態である。なお、以下では、Ｚｑｊ×の生成元の２乗となる整数ｇ’を生成する例について説明する。また、以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する部分については説明を省略する。
＜構成＞
図７は、第２の実施の形態のパラメータ生成装置２００の機能構成を例示したブロック図である。なお、本形態のパラメータ生成装置２００も第１の実施の形態と同様、所定のプログラムがコンピュータに読み込まれることによって構成されるものである。また、図７において、第１の実施の形態と共通する部分については図２と同じ符号を付した。
【００４５】
図７に示すように、本形態のパラメータ生成装置２００は、離散対数問題x≡g'a(mod N)を構成する合成数Ｎ及び整数ｇ’を生成する巡回群生成部２１０、整数ｘを生成する真数生成部２２０、整数ａを求める離散対数計算部２３０、メモリ２４０、制御部１５０、一時メモリ１６０及びカウント部１７０を有している。ここで、巡回群生成部２１０は、素数冪生成部１１１、生成元生成部２１２及び合成数生成部１１３を有している。なお、素数冪生成部１１１の構成は第１の実施の形態と同じである。また、生成元生成部２１２は、整数生成部１１２ａａと判定部１１２ａｂとを具備する部分群生成元生成部１１２ａ、群生成元生成部２１２ｂ及び冪乗部２１２ｄを有している。また、離散対数計算部２３０は、補助対数生成部２３１及び対数生成部１３２を有している。さらに、メモリ２４０は、各種情報を格納するための領域１４１，１４２，１４５，１４８，１４９，２４３，２４４，２４７を有している。また、図７における矢印はデータの流れを示しているが、制御部１５０、一時メモリ１６０及びカウント部１７０に入出力するデータの流れの記載は省略してある。
【００４６】
＜処理＞
次に、第２の実施の形態の処理について説明する。図８は、第２の実施の形態の処理を説明するためのフローチャートである。また、図９は、図８におけるステップＳ５２の処理の詳細を説明するためのフローチャートである。以下、図７から図９を用いて本形態の処理を説明する。
＜前処理＞
第１の実施の形態と同様、３つの整数ｓ，ｂｌｅｎ１，ｂｌｅｎ２をメモリ２４０の領域１４１に格納する。
【００４７】
＜巡回群生成部２１０の処理＞
上記のような前処理を前提とし巡回群生成部２１０による処理が実行される。
まず、素数冪生成部１１１が、メモリ２４０の領域１４１から整数ｓ，ｂｌｅｎ１を読み込み、素数の冪乗からなるビット長ｂｌｅｎ１の素数冪ｑｊ（ｊ＝１，...，ｓ）の集合であって、当該素数冪ｑｊの組にそれぞれ対応するオイラー関数値φ（ｑｊ）の組の最大公約数が全て２となるものを生成し、生成した当該複数の素数冪ｑｊを出力し、メモリ２４０の領域１４２に格納する（ステップＳ５１）。この処理の内容は、第１の実施の形態のステップＳ１と同じである。
【００４８】
次に、生成元生成部２１２が、メモリ２４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、全てのｊについて整数ｇ’の属する法ｑｊの剰余類の代表元が、素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の生成元の偶数冪乗（この例では２乗）となる整数ｇ’〔g'=g2，＜g mod qj＞=Zqj×〕を生成し、生成した当該整数ｇ’を出力し、メモリ２４０の領域２４４に格納する（ステップＳ５２）。以下、このステップＳ５２の詳細について説明する。
［ステップＳ５２の詳細］
まず、カウント部１７０が変数ｊに１を代入し、これを一時メモリ１６０に格納する（図９／ステップＳ６１）。次に、整数生成部１１２ａａが、擬似乱数等により任意の整数ｇｊを生成し、これを一時メモリ１６０に格納する（ステップＳ６２）。次に、判定部１１２ａｂが、メモリ２４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、さらに、一時メモリ１６０から整数ｇｊを読み込み、
<gj mod qj>=Zqj×  …(16)
を満たすか否か（整数ｇｊの属する法ｑｊの剰余類の代表元が、素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の生成元となるか否か）を判断する（ステップＳ６３）。この判定は、例えば、判定部１１２ａが<gj mod qj>の位数を計算し、その値とZqj×の位数であるφ（ｑｊ）とが一致するか否かによって行う。<gjmod qj>の位数を計算する方法としては、例えば、A. J. Menezes, P. C. van Oorschot, S. A. Vanstone "Handbook of Applied Cryptografhy"., CRC Press,1997の163ページに記載された方法等を用いる。ここで、式(16)を満たさないと判断された場合、制御部１５０は、処理をステップＳ６２に戻す。
【００４９】
一方、ステップＳ６３において、式(16)を満たすと判断された場合、冪乗部２１２ｄは、一時メモリ１６０から整数ｇｊを読み込み、これを偶数冪乗（この例では２乗）した整数ｇｊ’（gj’=gj2)を算出し（ステップＳ６４）、この整数ｇｊ’を出力する（ステップＳ６５）。出力された整数ｇｊ’は、メモリ２４０の領域２４３に格納される。さらに制御部１５０は、一時メモリ１６０から変数ｊを読み込み、メモリ２４０の領域１４１から整数ｓを読み込み、ｊ＝ｓを満たすか否かを判断する（ステップＳ６６）。ここで、ｊ＝ｓを満たさないと判断した場合、制御部１５０は、カウント部１７０に指示を与え、カウント部１７０は、変数ｊに１を加えた値を新たな変数ｊの値とし、この変数ｊを一時メモリ１６０に格納する（ステップＳ６７）。そして、制御部１５０は、処理をステップＳ６２に戻す。
【００５０】
一方、制御部１５０は、ステップＳ６６において、ｊ＝ｓを満たすと判断した場合、群生成元生成部２１２ｂに指示を与え、これを受けた群生成元生成部２１２ｂは、メモリ２４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、さらに、領域２４３から整数ｇｊ’（ｊ＝１，...，ｓ）を読み込む。そして、群生成元生成部２１２ｂは、全てのｊについて素数冪ｑｊを法として整数ｇｊ’と合同な整数ｇ’〔g’≡gj’(mod qj)〕を生成し（ステップＳ６８）、当該整数ｇ’を出力する（ステップＳ６９）。具体的には、群生成元生成部２１２ｂは、例えば、GaussやGarnarのアルゴリズムとして知られている手順により、g’≡gj’ (mod qj)を満たす整数ｇ’を生成する。また、得られた整数ｇ’は、メモリ２４０の領域２４４に格納される（［ステップＳ５２の詳細］の説明終わり）。
【００５１】
次に、合成数生成部１１３が、メモリ２４０の領域１４２から全ての素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、それらの素数冪ｑｊの積である合成数Ｎを算出し、当該合成数Ｎを出力する（ステップＳ５３）。なお、出力された合成数Ｎは、メモリ２４０の領域１４５に格納される。
＜真数生成部２２０の処理＞
次に、真数生成部２２０の処理を説明する。上記のような巡回群生成部２１０の処理の終了後、真数生成部２２０が、メモリ２４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、全てのｊについて素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の元である整数ｘ（x∈Zqj×）を生成し、当該整数ｘを出力する（ステップＳ５４）。具体的には、真数生成部２２０は、例えば、擬似乱数等を用いて０以上ｑｊ未満の整数ｘを生成し、それが全ての素数冪ｑｊと互いに素であるかを判定する処理を繰り返し、全ての素数冪ｑｊと互いに素であると判定された整数ｘを出力する。なお、出力された整数ｘは、メモリ２４０の領域２４７に格納される。  
＜離散対数計算部２３０の処理＞
次に、離散対数計算部２３０の処理を説明する。
【００５２】
まず、補助対数生成部２３１が、メモリ２４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、領域２４４から整数ｇ’を読み込み、領域２４７から整数ｘを読み込む。そして、補助対数生成部２３１は、各ｊについて
x≡g'aj (mod qj)  …(17)
を満たす整数ａｊ（ｊ＝１，...，ｓ）を算出し、これを出力する（ステップＳ５５）。なお、式(17)を満たす整数ａｊの算出は、例えば、数体ふるい法やＰollardのρ法等を用いる。算出された整数ａｊ（ｊ＝１，...，ｓ）は、補助対数生成部２３１から出力され、メモリ２４０の領域１４８に格納される。
【００５３】
次に、対数生成部１３２が、メモリ２４０の領域１４８から各整数ａｊ（ｊ＝１，...，ｓ）を読み込み、全てのｊについて
a≡aj(mod φ(qj))   …(18)
を満たす整数ａを算出し、当該整数ａを出力する（ステップＳ５６）。そして、出力された整数ａは、メモリ２４０の領域１４９に格納される。なお、この整数ａの算出は、例えば、GaussやGarnarのアルゴリズムとして知られている手順によって行う。
【００５４】
＜本形態の特徴＞
前述した＜条件３＞におけるオイラー関数値φ（ｑｖ），φ（ｑｗ）は、それぞれ、g(mod qv)及びg(mod qw)を生成元とした巡回群の位数を示す。しかし、g’=g2とした本形態のg’(mod qv)及びg’(mod qw) をそれぞれ生成元とした巡回群の位数は、それぞれφ(qv)/2，φ(qw)/2となる。よって、本形態の場合、ｘ∈＜ｇ’＞となるためには＜条件３＞の代わりに、以下の＜条件３’’’＞を満たす必要がある。なお、＜条件３＞の(b)は「(b)全てのｖ，ｗ（１≦ｖ＜ｗ≦ｓ）に対して、av≡aw(mod 1)が成立する。」に置き換わるが、av，awは整数であるため、この条件は不要となる。
【００５５】
＜条件３’’’＞
(a)各ｊ（ｊ＝１，....，ｓ）に対して、x≡g'aj(mod qj)となる整数ａｊが存在する。
ここで、ｘ∈Ｚqj×であるから、高い確率（この例では５０％程度）でx≡g'aj(mod qj)となる整数ａｊが存在し、上記の(a)の条件を満たす。また、上記の(b)は当然に満たされる。そのため、この例においてｊを固定した場合x∈<g’>となる確率は５０％程度となる。また、この場合、全てのｊでx∈<g’>となる確率は、１／２×１／２×…×１／２＝１／２ｓ程度となり、任意に選択した整数ｘに対し、x∈<g’>となる確率を最大値／２程度〔任意にｇ’を選択した場合（ＺＮ×の位数）／（＜ｇ’＞の位数）≧２ｓ−１であるため、ｘ，ｇ’を任意に選択した場合、x’∈<g’>となる確率は１／２ｓ−１以下となる〕にすることができる。
【００５６】
よって、最終的にx∈<g’>であるか否かを判定し、x∈<g’>でない場合にステップＳ５４以降の処理をやり直す構成としても比較的少ない演算量でx∈<g’>を満たす整数ｘを選択することができる。
なお、ステップＳ５１の代わりに、全てのｊについてgcd(φ(qu),φ(qj))=2e〔ｅは自然数，∀u(1≦u≦j-1）〕となる素数冪ｑｊを生成し、ステップＳ５２の代わりに、
全てのｊについて、整数ｇ’の属する法ｑｊの剰余類の代表元が、素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の生成元ｇの２ｅ（ｅは自然数）乗となる整数g ’＝ｇ２ｅを生成することとしてもよい。
【００５７】
〔第３の実施の形態〕
次に、本発明の第３の実施の形態について説明する。本形態は、前述の＜条件１＞＜条件２＞を満たすように合成数Ｎ、整数ｇを生成し、任意に選択された整数ｘがｘ∈＜ｇ＞となる確率を最大値化する形態である。以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する部分については説明を省略する。
＜構成＞
図１０は、第３の実施の形態のパラメータ生成装置３００の機能構成を例示したブロック図である。なお、本形態のパラメータ生成装置３００も第１の実施の形態と同様、所定のプログラムがコンピュータに読み込まれることによって構成されるものである。また、図９において、第１の実施の形態と共通する部分については図２と同じ符号を付した。
【００５８】
図１０に示すように、本形態のパラメータ生成装置３００は、離散対数問題x≡g'a(mod N)を構成する合成数Ｎ及び整数ｇ’を生成する巡回群生成部１１０、整数ｘを生成する真数生成部３２０、整数ａを求める離散対数計算部１３０、メモリ１４０、制御部１５０、一時メモリ１６０及びカウント部１７０を有している。
ここで、巡回群生成部１１０の構成は第１の実施の形態と同じである。また、離散対数計算部３３０は、補助対数生成部１３１、対数生成部１３２及び判定部３３３を有している。さらに、メモリ１４０は、各種情報を格納するための領域１４１〜１４５，１４８，１４９，３４７を有している。また、図９における矢印はデータの流れを示しているが、制御部１５０、一時メモリ１６０及びカウント部１７０に入出力するデータの流れの記載は省略してある。
【００５９】
＜処理＞
次に、第３の実施の形態の処理について説明する。図１１は、第３の実施の形態の処理を説明するためのフローチャートである。以下、図１０及び図１１を用いて本形態の処理を説明する。
＜前処理＞
第１の実施の形態と同様、３つの整数ｓ，ｂｌｅｎ１，ｂｌｅｎ２をメモリ３４０の領域１４１に格納する。
【００６０】
＜巡回群生成部１１０の処理＞
巡回群生成部１１０は、第１の実施の形態と同じ手順（図３／ステップＳ１〜Ｓ３）によってメモリ３４０の領域１４１に格納された整数ｓ，ｂｌｅｎ１を用い、素数冪ｑｊ、整数ｇｊ（ｊ＝１，...，ｓ）、整数ｇ、合成数Ｎを生成し、これらをメモリ３４０の領域１４２，１４３，１４４，１４５に格納する（ステップＳ８１〜Ｓ８３）。
＜真数生成部３２０の処理＞
上記のような巡回群生成部１１０の処理の終了後、真数生成部３２０が、メモリ２４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、全てのｊについて素数冪ｑｊと互いに素な０以上ｑｊ未満の整数集合の元である整数ｘ（x∈Zqj×）を生成し、当該整数ｘを出力する（ステップＳ８４）。なお、出力された整数ｘは、メモリ３４０の領域３４７に格納される。  
【００６１】
＜離散対数計算部３３０の処理＞
上記のような真数生成部３２０の処理の終了後、離散対数計算部３３０の処理が開始される。
まず、補助対数生成部１３１が、メモリ３４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、領域１４４から整数ｇを読み込み、領域３４７から整数ｘを読み込む。そして、補助対数生成部１３１は、各ｊについて
x≡gaj (mod qj)  …(19)
を満たす整数ａｊ（ｊ＝１，...，ｓ）を算出し、これを出力する（ステップＳ８５）。なお、式(19)を満たす整数ａｊの算出は、例えば、数体ふるい法やＰollardのρ法等を用いる。また、出力された整数ａｊは、メモリ３４０の領域１４８に格納される。
【００６２】
次に、判定部３３３が、メモリ３４０の領域１４２から素数冪ｑｊを、領域１４８から整数ａｊを、それぞれ読み込み、すべてのv,w(1≦v＜w≦s)について  
av≡aw (mod gcd(φ(qv),φ(qw))   …(20)
が成立するか否かを判断する（ステップＳ８６）。なお、ステップＳ８１でgcd(φ(qv),φ(qw))=2であることが保証されているため、式(20)の代わりに
av≡aw (mod 2)   …(20)'
が成立するか否かを判断することとしてもよい。この場合、gcd(φ(qv),φ(qw))を求めるために、メモリ３４０の領域１４２からの素数冪ｑｊの読み込み、オイラー関数の演算、及び最大公約数の算出処理を省略することができる。その結果、以下に示すステップＳ８４〜Ｓ８６の繰り返し演算処理を効率化できる。
【００６３】
ここで、すべてのv,w(1≦v＜w≦s)について式(20)又は(20)'が成立しないと判断された場合、制御部１５０は、処理をステップＳ８４に戻す（その結果、ステップＳ８４〜Ｓ８６の処理が繰り返される）。一方、すべてのv,w(1≦v＜w≦s)について式(20) 又は(20)'が成立すると判断された場合、制御部１５０は、対数生成部１３２に指示を与え、これを受けた対数生成部１３２は、メモリ３４０の領域１４８から各整数ａｊ（ｊ＝１，...，ｓ）を読み込み、全てのｊについて
a≡aj(mod φ(qj))   …(21)
を満たす整数ａを算出し、当該整数ａを出力する（ステップＳ８７）。そして、出力された整数ａは、メモリ３４０の領域１４９に格納される。なお、この整数ａの算出は、例えば、GaussやGarnarのアルゴリズムとして知られている手順によって行う。
【００６４】
＜本形態の特徴＞
本形態の構成の場合、前述の＜条件１＞及び＜条件２＞を満たす。そして、＜条件１＞及び＜条件２＞を満たすように合成数Ｎ及び整数ｇを選択した場合、任意に選択した整数ｘに対し、x∈<g>となる確率を最大値化することができる。よって、ステップＳ８４〜Ｓ８６の繰り返し回数を従来構成よりも少なくすることができる。
〔第４の実施の形態〕
次に、本発明の第４の実施の形態について説明する。本形態は、第１の実施の形態の応用例であり、第１の実施の形態の構成をＯＴＵ暗号の暗号鍵生成に適用した形態である。以下では、第１の実施の形態との相違点を中心に説明し、第１の実施の形態と共通する事項については説明を省略する。
【００６５】
まず、ＯＴＵ暗号の暗号鍵について説明する。
ＯＴＵ暗号の公開鍵ＰＫ＝（ｂ１，...，ｂｎ，ｋ）、秘密鍵ＳＫ＝（Ｎ，ｄ，ｘ１，...，ｘｎ，ｇ）には次の条件がある。
(a)各ｉ（ｉ＝１，...，ｎ）に対して、gbi-d≡xi(mod N)を満たす。なお、上付き添え字にあるｂｉはｂｉを示す。
(b)集合{１，２，...，ｎ}の部分集合であり、要素数がｋ個（ｋは整数）である任意の集合Ｓに対し、Πj∈S xj<N  が成立している。
【００６６】
(c)ｘ１，...，ｘｎは互いに素である。
上記の条件(b)は、各ｘｊのビット長はＮビットに比べて非常に短い必要があることを意味している。少なくとも、｜xj｜≦｜N｜/k（ただし｜＊｜は＊のビット長を示す。）でなくてはならない。
本形態では、４つの整数ｓ，ｂｌｅｎ１，ｋ，ｎを入力とし、第１の実施の形態の構成を利用し、ＯＴＵ暗号の公開鍵ＰＫ＝（ｂ１，...，ｂｎ，ｋ）及び秘密鍵ＳＫ＝（Ｎ，ｄ，ｘ１，...，ｘｎ，ｇ）を生成する。ただし、各パラメータは次の性質を満たしている。
【００６７】
・Ｎは整数であり、ビット長がｂｌｅｎ１である素数冪ｑｊ（ｊ＝１，...，ｓ）の積である。
・ｄはランダムに選ばれた整数である。
・ｇは、全てのｊ（ｊ＝１，...，ｓ）において、Ｚｑｊ×の生成元となる。
・各ｘｊは、ある整数の偶数冪乗であり、xj∈<g>を満たす。また、各ｘｊのビット長は
【００６８】
【数５】
0004676873.tif 000006
・各ａｊは、xj≡gaj(mod N)を満たす整数である。
＜構成＞
図１２は、第４の実施の形態の暗号鍵生成装置４００の機能構成を例示したブロック図である。なお、図１２において第１の実施の形態と共通する部分については図２と同じ符号を付した。また、本形態の暗号鍵生成装置４００は、第１の実施の形態と同様、公知のコンピュータに所定のプログラムが読み込まれることによって構成されるものである。
【００６９】
図１２に例示するように、本形態の暗号鍵生成装置４００は、巡回群生成部１１０、制御部１５０、一時メモリ１６０、カウント部１７０、乗算部４１１、乱数生成部４１２、除算部４１３、真数生成部４２０、離散対数計算部４３０、メモリ４４０、加算部４５０及び出力部４６０を有している。なお、乱数生成部４１２は、正の整数αを入力としてαビットの擬似乱数を生成し出力する。また、真数生成部４２０は、補助整数生成部４２１、冪乗部４２２及び判定部４２３を有している。また、離散対数計算部４３０は、補助対数生成部４３１及び対数生成部４３２を有している。また、図１２における矢印はデータの流れを示しているが、制御部１５０、一時メモリ１６０及びカウント部１７０に入出力するデータの流れの記載は省略してある。
【００７０】
＜処理＞
次に、第４の実施の形態の暗号鍵生成処理を説明する。
図１３は、第４の実施の形態の暗号鍵生成処理の全体を説明するためのフローチャートである。また、図１４は、図１３のステップＳ９７の詳細を説明するためのフローチャートである。以下、図１２から図１４を用いて、本形態の暗号鍵生成処理を説明する。
＜前処理＞
まず、前処理として、４つの整数ｓ，ｂｌｅｎ１，ｋ，ｎ（ｎ≧１）がメモリ４４０の領域４４１に格納される。なお、整数ｓ，ｂｌｅｎ１，ｋ，ｎは、例えば、図１に例示した入力部１２から入力されたデータである。
【００７１】
＜巡回群生成部１１０の処理＞
上記のような前処理を前提として、巡回群生成部１１０は、第１の実施の形態と同じ手順（図３／ステップＳ１〜Ｓ３）によってメモリ４４０の領域４４１に格納された整数ｓ，ｂｌｅｎ１を用い、素数冪ｑｊ、整数ｇｊ（ｊ＝１，...，ｓ）、整数ｇ、合成数Ｎを生成し、これらをメモリ４４０の領域１４２，１４３，１４４，１４５に格納する（ステップＳ９１〜Ｓ９３）。
＜乗算部４１１の処理＞
次に、乗算部４１１が、メモリ４４０の領域４４１から整数ｓ，ｂｌｅｎ１を読み込み、blen1・sを算出し、その演算結果blen1・sを出力する（ステップＳ９４）。出力された演算結果s・blen1は、メモリ４４０の領域４４２に格納される。
【００７２】
＜乱数生成部４１２の処理＞
次に、乱数生成部４１２が、メモリ４４０の領域４４２からblen1・sを読み込み、blen1・sビットの（擬似）乱数ｄを発生して出力し（ステップＳ９５）、これをメモリ４４０の領域４４３に格納する。なお、乱数ｄの生成には、例えば、前述の擬似乱数生成アルゴリズム等を用いる。
＜除算部４１３の処理＞
次に、除算部４１３が、メモリ４４０の領域４４２からblen1・sを読み込み、領域４４１から整数ｋを読み込む。そして、除算部４１３は、
【数６】
0004676873.tif 000007
の演算を行い、その演算結果blen2を出力する（ステップＳ９６）。出力された演算結果blen2は、メモリ４４０の領域４４４に格納される。
【００７３】
＜真数生成部４２０の処理＞
次に、真数生成部４２０が、メモリ４４０の領域１４１からｂｌｅｎ２を読み込み、領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、これらを用い、全ての素数冪ｑｊと互いに素でありビット長が（ｂｌｅｎ２）／２ｅ（ｅは自然数）以下である整数ｙｉ（ｉ＝１，...，ｎ）を２ｅ冪乗した整数ｘｉ（xi=yi2e）の集合であって、その集合に属する全ての整数の組が互いに素となるものを生成し、当該整数ｘｉを出力する（ステップＳ９７）。そして、出力された各整数ｘｉ（ｉ＝１，...，ｎ）は、メモリ４４０の領域４４６に格納される。以下、このステップＳ９７の詳細について説明する。
【００７４】
［ステップＳ９７の詳細］
まず、補助整数生成部４２１が、メモリ４４０の領域４４１からｂｌｅｎ２を読み込み、領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込む。そして、補助整数生成部４２１は、全ての素数冪ｑｊと互いに素なビット長ｂｌｅｎ２／２ｅ（ｅは自然数／例えばｅ＝１）の整数ｙ１を生成し、当該整数ｙ１を出力する（図１４／ステップＳ１１１）。出力された整数ｙ１はメモリ４４０の領域４４５に格納される。
次に、冪乗部４２２が、メモリ４４０の領域４４５から整数ｙ１を読み込み、整数ｙ１を偶数冪乗した整数ｘ１（ｘ１＝ｙ１２ｅ）を生成し、当該整数ｘ１を出力する（ステップＳ１１２）。出力された整数ｘ１はメモリ４４０の領域４４６に格納される。 
【００７５】
次に、制御部１５０が、メモリ４４０の領域４４１から整数ｎを読み込み、整数ｎが１であるか否かを判断する（ステップＳ１１３）。ここで、ｎ＝１と判断された場合、制御部１５０は、ステップＳ９７の処理を終了する。一方、ｎ＝１でないと判断された場合、制御部１５０は、カウント部１７０に指示を与え、これを受けたカウント部１７０は、変数ｉに２を代入し、この変数ｉを一時メモリ１６０に格納する（ステップＳ１１４）。
【００７６】
そして、補助整数生成部４２１が、メモリ４４０の領域４４１からｂｌｅｎ２を読み込み、領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、一時メモリ１６０から変数ｉを読み込み、全ての素数冪ｑｊと互いに素なビット長ｂｌｅｎ２／２ｅ（ｅは自然数／例えばｅ＝１）の整数ｙｉを生成し、当該整数ｙｉを出力する（図１４／ステップＳ１１５）。出力された整数ｙ１はメモリ４４０の領域４４５に格納される。さらに、冪乗部４２２が、メモリ４４０の領域４４５から整数ｙｉを読み込み、整数ｙｉを偶数冪乗した整数ｘｉ（ｘｉ＝ｙｉ２ｅ）を生成し、当該整数ｘｉを出力する（ステップＳ１１６）。出力された整数ｘｉはメモリ４４０の領域４４６に格納される。
【００７７】
次に、判定部４２３が、メモリ４４０の領域４４６から、整数ｘ１，...，ｘｉ−１，ｘｉを読み込み、整数ｘｉが、その他全ての整数ｘ１，...，ｘｉ−１と互いに素であるか否かを判断する（ステップＳ１１７）。ここで、整数ｘｉが、何れかの整数ｘ１，...，ｘｉ−１と互いに素でないと判断された場合、制御部１５０は、メモリ４４０の領域４４５，４４６の整数ｙｉ，ｘｉを削除し、処理をステップＳ１１５に戻す。一方、整数ｘｉが、その他全ての整数ｘ１，...，ｘｉ−１と互いに素であると判断された場合、制御部１５０は、一時メモリ１６０から変数ｉを読み込み、メモリ４４０の領域４４１から整数ｎを読み込み、ｉ＝ｎであるか否かを判断する（ステップＳ１１８）。
【００７８】
ここで、ｉ＝ｎでないと判断された場合、制御部１５０は、カウント部１７０に指示を与え、これを受けたカウント部１７０は、一時メモリ１６０に格納されている変数ｉの値をｉ＋１の値によって更新し、新たな変数ｉを一時メモリ１６０に格納する（ステップＳ１１９）。この場合、さらに制御部１５０は、処理をステップＳ１１５に戻す。
一方、ステップＳ１１８の判断で、ｉ＝ｎであると判断された場合、制御部１５０は、ステップＳ９７の処理を終了する（［ステップＳ９７の詳細］の説明終わり）。
【００７９】
＜離散対数計算部４３０の処理＞
次に、補助対数生成部４３１が、メモリ４４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、領域１４４から整数ｇを読み込み、領域１４７から整数ｘｉを読み込む。そして、補助対数生成部４３１は、各ｉ（ｉ＝１，...，ｎ），ｊ（ｊ＝１，...，ｓ）について、
xi≡ga(i,j)(mod qj)  …(23)
を満たす整数ａｉ，ｊを算出する（ステップＳ９８）。なお、式(23)の上付き添え字のａ（ｉ，ｊ）は、ａｉ，ｊを意味する。また、式(23)を満たす整数ａｉ，ｊの算出は、例えば、数体ふるい法やＰollardのρ法等を用いる。また、本形態では、上述のステップＳ９７のように整数ｘｉを選択しているため＜条件３’’＞を満たしており、算出された各整数ａｉ，ｊの全ての組は、２を法として合同となっている。算出された各整数ａｉ，ｊ（ｉ＝１，...，ｎ，ｊ＝１，...，ｓ）は、補助対数生成部４３１から出力され、メモリ４４０の領域４４７に格納される。
【００８０】
次に、対数生成部４３２が、メモリ４４０の領域４４７から各整数ａｉ，ｊ（ｉ＝１，...，ｎ，ｊ＝１，...，ｓ）を読み込み、全てのｊについて
ai≡ai,j(mod φ(qj))   …(24)
を満たす整数ａｉをｉ毎に算出し、当該整数ａｉ（ｉ＝１，...，ｎ）を出力する（ステップＳ９９）。そして、出力された整数ａｉは、メモリ４４０の領域４４９に格納される。なお、これらの整数ａｉの算出は、例えば、GaussやGarnarのアルゴリズムとして知られている手順によって行う。
【００８１】
＜加算部４５０の処理＞
次に、加算部４５０（「関数演算部」に相当）が、メモリ４４０の領域４４３から乱数ｄを読み込み、領域４４８から整数ａｉ（ｉ＝１，...，ｎ）を読み込み、整数ａｉと乱数ｄとを加算した加算値（「関数値」に相当）ｂｉ＝ａｉ＋ｄを生成し、当該加算値ｂｉ（ｉ＝１，...，ｎ）を出力する（ステップＳ１００）。出力された加算値ｂｉ（ｉ＝１，...，ｎ）は、メモリ４４０の領域４４９に格納される。
＜出力部４６０の処理＞
その後、出力部４６０が、メモリ４４０の領域４４９から加算値ｂ１，...，ｂｎを読み込み、領域４４１から整数ｋを読み込み、ＰＫ＝（ｂ１，...，ｂｎ，ｋ）を公開鍵として出力する。さらに、出力部４６０は、メモリ４４０の領域１４５から合成数Ｎを読み込み、領域４４３から乱数ｄを読み込み、領域４４６から整数ｘ1，...，ｘｎを読み込み、領域１４４から整数ｇを読み込み、ＳＫ＝（Ｎ，ｄ，ｘ1，...，ｘｎ，ｇ）を秘密鍵として出力する。
【００８２】
〔第５の実施の形態〕
次に、本発明における第５の実施の形態について説明する。本形態は、第２の実施の形態の応用例であり、第２の実施の形態の構成をＯＴＵ暗号の暗号鍵生成に適用した形態である。以下では、第１，２，４の実施の形態との相違点を中心に説明し、第１，２，４の実施の形態と共通する事項については説明を省略する。
＜構成＞
図１５は、第５の実施の形態の暗号鍵生成装置５００の機能構成を例示したブロック図である。なお、図１５において第１，４の実施の形態と共通する部分については図２，１２と同じ符号を付した。また、本形態の暗号鍵生成装置５００は、第１の実施の形態と同様、公知のコンピュータに所定のプログラムが読み込まれることによって構成されるものである。
【００８３】
図１５に例示するように、本形態の暗号鍵生成装置５００は、巡回群生成部２１０、制御部１５０、一時メモリ１６０、カウント部１７０、乗算部４１１、乱数生成部４１２、除算部４１３、真数生成部５２０、離散対数計算部４３０、メモリ４４０、加算部４５０及び出力部４６０を有している。なお、真数生成部５２０は、整数生成部５２１及び判定部４２３を有している。また、離散対数計算部４３０は、補助対数生成部４３１及び対数生成部４３２を有している。また、図１５における矢印はデータの流れを示しているが、制御部１５０、一時メモリ１６０及びカウント部１７０に入出力するデータの流れの記載は省略してある。
【００８４】
＜処理＞
次に、第５の実施の形態の暗号鍵生成処理を説明する。
図１６は、第５の実施の形態の暗号鍵生成処理の全体を説明するためのフローチャートである。以下、図１５及び図１６を用いて、本形態の暗号鍵生成処理を説明する。
＜前処理＞
まず、前処理として、４つの整数ｓ，ｂｌｅｎ１，ｋ，ｎ（ｎ≧１）がメモリ４４０の領域４４１に格納される。
【００８５】
＜巡回群生成部２１０の処理＞
上記のような前処理を前提として、巡回群生成部２１０は、第２の実施の形態と同じ手順（図８／ステップＳ５１〜Ｓ５３）によってメモリ４４０の領域４４１に格納された整数ｓ，ｂｌｅｎ１を用い、素数冪ｑｊ、整数ｇｊ’（ｊ＝１，...，ｓ）、整数ｇ’、合成数Ｎを生成し、これらをメモリ４４０の領域１４２，１４３，１４４，１４５に格納する（ステップＳ１２１〜Ｓ１２３）。
＜乗算部４１１・乱数生成部４１２・除算部４１３の処理＞
次に、乗算部４１１・乱数生成部４１２・除算部４１３が、第４の実施の形態と同じ手順（図１３／ステップＳ９４〜Ｓ９６）により、blen1・s，ｄ，blen2を生成し、これらをメモリ４４０の領域４４２，４４３，４４４にそれぞれ格納する（ステップＳ１２４〜Ｓ１２６）。
【００８６】
＜真数生成部５２０の処理＞
次に、真数生成部５２０が、メモリ４４０の領域１４１からｂｌｅｎ２を読み込み、ビット長がｂｌｅｎ２以下の整数ｘｉの集合であって、その集合に属する全ての整数の組が互いに素となるものを生成し、当該整数ｘｉを出力する（ステップＳ１２７）。
出力された各整数ｘｉ（ｉ＝１，...，ｎ）は、メモリ４４０の領域４４６に格納される。具体的には、例えば、整数生成部５２１が、メモリ４４０の領域１４１からｂｌｅｎ２を読み込み、ｂｌｅｎ２以下の整数ｘｉ（ｉ＝１，...，ｎ）を生成し、判定部４２３がそれらが互いに素であるかを判定し、互いに素な整数ｘｉ（ｉ＝１，...，ｎ）を生成するといった、前述のステップＳ９７に類似した手順によって各整数ｘｉを生成する。そして、ｘｉ∈＜ｇ’＞であるか否かの判定処理を追加し、ｘｉ∈＜ｇ’＞でない場合、各整数ｘｉを生成し直す構成とする。
【００８７】
＜離散対数計算部４３０・加算部４５０・出力部４６０の処理＞
その後、離散対数計算部４３０・加算部４５０・出力部４６０によって、第４の実施の形態と同じ処理（図１３／ステップＳ９８からＳ１０１）を実行し、最終的に、出力部４６０が、公開鍵ＰＫ＝（ｂ１，...，ｂｎ，ｋ）と秘密鍵ＳＫ＝（Ｎ，ｄ，ｘ1，...，ｘｎ，ｇ）を出力する。
〔第６の実施の形態〕
次に、本発明における第６の実施の形態について説明する。本形態は、第３の実施の形態の応用例であり、第３の実施の形態の構成をＯＴＵ暗号の暗号鍵生成に適用した形態である。以下では、第１，３，４の実施の形態との相違点を中心に説明し、第１，３，４の実施の形態と共通する事項については説明を省略する。
【００８８】
＜構成＞
図１７は、第６の実施の形態の暗号鍵生成装置６００の機能構成を例示したブロック図である。なお、図１７において第１，４の実施の形態と共通する部分については図２，図１２と同じ符号を付した。また、本形態の暗号鍵生成装置６００は、第１の実施の形態と同様、公知のコンピュータに所定のプログラムが読み込まれることによって構成されるものである。
図１７に例示するように、本形態の暗号鍵生成装置６００は、巡回群生成部１１０、制御部１５０、一時メモリ１６０、カウント部１７０、乗算部４１１、乱数生成部４１２、除算部４１３、真数生成部６２０、離散対数計算部６３０、メモリ４４０、加算部４５０及び出力部４６０を有している。なお、離散対数計算部６３０は、補助対数生成部４３１、対数生成部４３２及び判定部６３３を有している。また、図１７における矢印はデータの流れを示しているが、制御部１５０、一時メモリ１６０及びカウント部１７０に入出力するデータの流れの記載は省略してある。
【００８９】
＜処理＞
次に、第６の実施の形態の暗号鍵生成処理を説明する。
図１８は、第６の実施の形態の暗号鍵生成処理の全体を説明するためのフローチャートである。以下、図１７及び図１８を用いて、本形態の暗号鍵生成処理を説明する。
＜前処理＞
まず、前処理として、４つの整数ｓ，ｂｌｅｎ１，ｋ，ｎ（ｎ≧１）がメモリ４４０の領域４４１に格納される。
【００９０】
＜巡回群生成部１１０・乗算部４１１・乱数生成部４１２・除算部４１３の処理＞
上記のような前処理を前提として、第４の形態のステップＳ９１〜Ｓ９６（図１３）と同じ処理を実行し、素数冪ｑｊ、整数ｇｊ（ｊ＝１，...，ｓ）、整数ｇ、合成数Ｎ、blen1・s，乱数ｄ，blen2を生成し、これらをメモリ４４０の領域１４２，１４３，１４４，１４５，４４２，４４３，４４４に格納する（ステップＳ１４１〜Ｓ１４６）。
＜真数生成部６２０の処理＞
次に、真数生成部６２０が、メモリ４４０の領域１４１からｂｌｅｎ２を読み込み、ビット長がｂｌｅｎ２以下の整数ｘｉ〔ｉ＝（１，...，ｎ）〕の集合であって、その集合に属する全ての整数の組が互いに素となるものを生成し、当該整数ｘｉを出力する（ステップＳ１４７）。出力された各整数ｘｉ（ｉ＝１，...，ｎ）は、メモリ４４０の領域４４６に格納される。
【００９１】
＜離散対数計算部６３０の処理＞
その後、離散対数計算部６３０の処理が開始される。
まず、補助対数生成部４３１が、メモリ４４０の領域１４２から素数冪ｑｊ（ｊ＝１，...，ｓ）を読み込み、領域１４４から整数ｇを読み込み、領域４４７から整数ｘｉ（ｉ＝１，...，ｎ）を読み込む。そして、補助対数生成部４３１は、各ｊについて
xi≡ga(i,j)(mod qj)  …(25)
を満たす整数ａｉ，ｊ（ｉ＝１，...，ｎ／ｊ＝１，...，ｓ）を算出し、これを出力する（ステップＳ１４８）。なお、式(25)を満たす整数ａｉ，ｊの算出は、例えば、数体ふるい法やＰollardのρ法等を用いる。また、出力された整数ａｉ，ｊは、メモリ４４０の領域４４７に格納される。
【００９２】
次に、判定部６３３が、メモリ４４０の領域４４７から整数ａｉ，ｊを、それぞれ読み込み、すべてのv,w(1≦v＜w≦s)について  
av≡aw (mod 2)   …(26)
が成立するか否かを判断する（ステップＳ１４９）。
ここで、すべてのv,w(1≦v＜w≦s)について式(26)が成立しないと判断された場合、制御部１５０は、処理をステップＳ１４７に戻す。一方、すべての
v,w(1≦v＜w≦s)について式(26)が成立すると判断された場合、制御部１５０は、対数生成部４３２に指示を与え、これを受けた対数生成部４３２は、メモリ４４０の領域４４７から各整数ａｉ，ｊ（ｉ＝１，...，ｎ／ｊ＝１，...，ｓ）を読み込み、全てのｊについて
ai≡ai,j(mod φ(qj))   …(27)
を満たす整数ａｉを算出し、当該整数ａｉを出力する（ステップＳ１５０）。そして、出力された整数ａｉは、メモリ４４０の領域４４８に格納される。なお、この整数ａｉの算出は、例えば、GaussやGarnarのアルゴリズムとして知られている手順によって行う。
【００９３】
その後、加算部４５０・出力部４６０によって、第４の実施の形態と同じ処理（図１３／ステップＳ１００，Ｓ１０１）を実行し、最終的に、出力部４６０が、公開鍵ＰＫ＝（ｂ１，...，ｂｎ，ｋ）と秘密鍵ＳＫ＝（Ｎ，ｄ，ｘ1，...，ｘｎ，ｇ）を出力する。
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述では、加算部４５０が、bi=ai+dの演算を行ったが、bi=ai+d(mod N)やbi=ai+d(mod φ(N))等の演算を行うこととしてもよい。また、各実施の形態を適宜融合することも可能である。例えば、第１の実施の形態のように整数ｘを選択し、第２の実施の形態のようにｇ’を生成する構成であってもよい。さらに、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【００９４】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００９５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００９６】
また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００９７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００９８】
本発明の産業上の利用分野としては、合成数を法としたＯＴＵ暗号の暗号鍵生成装置等の分野を例示できる。
【図面の簡単な説明】
【００９９】
【図１】図１は、パラメータ生成装置のードウェア構成を例示したブロック図である。
【図２】図２は、第１の実施の形態のパラメータ生成装置の機能構成を説明するためのブロック図である。
【図３】図３は、第１の実施の形態の処理の全体を説明するためのフローチャートである。
【図４】図４は、図３のステップＳ１の詳細を説明するためのフローチャートである。
【図５】図５は、図３のステップＳ２の詳細を説明するためのフローチャートである。
【図６】図６は、図３のステップＳ４の詳細を説明するためのフローチャートである。
【図７】図７は、第２の実施の形態のパラメータ生成装置の機能構成を例示したブロック図である。
【図８】図８は、第２の実施の形態の処理を説明するためのフローチャートである。
【図９】図９は、図８におけるステップＳ５２の処理の詳細を説明するためのフローチャートである。
【図１０】図１０は、第３の実施の形態のパラメータ生成装置の機能構成を例示したブロック図である。
【図１１】図１１は、第３の実施の形態の処理を説明するためのフローチャートである
【図１２】図１２は、第４の実施の形態の暗号鍵生成装置の機能構成を例示したブロック図である。
【図１３】図１３は、第４の実施の形態の暗号鍵生成処理の全体を説明するためのフローチャートである。
【図１４】図１４は、図１３のステップＳ９７の詳細を説明するためのフローチャートである。
【図１５】図１５は、第５の実施の形態の暗号鍵生成装置の機能構成を例示したブロック図である。
【図１６】図１６は、第５の実施の形態の暗号鍵生成処理の全体を説明するためのフローチャートである。
【図１７】図１７は、第６の実施の形態の暗号鍵生成装置の機能構成を例示したブロック図である。
【図１８】図１８は、第６の実施の形態の暗号鍵生成処理の全体を説明するためのフローチャートである。
【符号の説明】
【０１００】
１００，２００，３００  パラメータ生成装置
４００，５００，６００  暗号鍵生成装置
【図１】
0004676873.tif 000008
【図２】
0004676873.tif 000009
【図３】
0004676873.tif 000010
【図４】
0004676873.tif 000011
【図５】
0004676873.tif 000012
【図６】
0004676873.tif 000013
【図７】
0004676873.tif 000014
【図８】
0004676873.tif 000015
【図９】
0004676873.tif 000016
【図１０】
0004676873.tif 000017
【図１１】
0004676873.tif 000018
【図１２】
0004676873.tif 000019
【図１３】
0004676873.tif 000020
【図１４】
0004676873.tif 000021
【図１５】
0004676873.tif 000022
【図１６】
0004676873.tif 000023
【図１７】
0004676873.tif 000024
【図１８】
0004676873.tif 000025