(57)【要約】【課題】安全性が数学的に保証された擬似乱数を、高速に生成できるようにする。【解決手段】自然数ｃ，ｏ，ａ及びｐビットのビット列ｗ１，ｗ２を入力し、ｗ１、ｗ２をそれぞれ内部状態保存部と生成元保存部に格納し、内部状態保存部に格納されたｐビットの値ｇを生成元とする。そして、内部状態保存部に格納されているｐビットの上位ｃビットの値をｓとして，ｐビット表現のｇｓを計算し、これを内部状態保存部に格納し，この格納されたｐビットの上位ｏビットを出力するという一連の処理をａ回繰り返し、ａ個の擬似乱数を生成する。【選択図】　　　図２
2004038020.tif 000002
【特許請求の範囲】
【請求項１】
ワード長がｗビットである計算装置であって、
自然数ｃ，ｏ，ａ（ｃ＋ｏ≦ｐ：ｐは素数で２ｐ−１も素数となる数）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在するビット列）を少なくとも２個入力する入力手段と、
前記入力手段が入力したビット長ｐの第１のビット列を格納する内部状態保存手段と、
前記入力手段が入力したビット長ｐの第２のビット列を格納する生成元保存手段と、
ｐ次の｛０，１｝係数の既約多項式ｆ（ｔ）（＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０）を、そのｐビットの｛０，１｝係数ｂｐ−１ｂｐ−２・・・ｂ１ｂ０のビット列により保存する既約多項式保存手段と、
演算手段とを備え、
該演算手段により、前記生成元保存手段に格納されているｐビットの値ｇ、前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓ及び前記既約多項式保存手段に格納されているｐビットのビット列とを用いてｇｓ（ｍｏｄｆ（ｔ））を計算し、該演算手段のｐビットの演算結果を内部状態保存手段に格納すると共に、該ｐビットの演算結果の下位ｏビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【請求項２】
ワード長がｗビットである計算装置であって、
自然数ｃ，ｏ，ａ（ｃ＋ｏ≦ｐ：ｐは素数で２ｐ−１も素数となる数）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を少なくとも３個入力する入力手段と、
前記入力手段が入力したビット長ｐの第１のビット列を格納する内部状態保存手段と、
前記入力手段が入力したビット長ｐの第２のビット列を格納する生成元保存手段と、
ｐ次の｛０，１｝係数の既約多項式ｆ（ｔ）（＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０）を、そのｐビットの｛０，１｝係数ｂｐ−１ｂｐ−２・・・ｂ１ｂ０のビット列により保存する既約多項式保存手段と、
前記入力手段が入力したビット長ｐの第３のビット列を保存するベースポイント保存手段と、
演算手段とを備え、
演算手段により、前記生成元保存手段に格納されているｐビットの値ｇ、前記ベースポイント保存手段に格納されているｐビットの値ｘ及び前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓとを用いて，ｘｇｓ（ｍｏｄｆ（ｔ））を計算し、そのｐビットの計算結果を内部状態保存手段に格納すると共に、そのｐビットの下位ｏビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【請求項３】
ワード長がｗビットである計算装置であって、
自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ（ｕ＋ｖ≦ｐ（ｐ：ｐは素数で２ｐ−１も素数となる数）かつ全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ，かつｃｉ≠ｏｊ）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を入力する入力手段と、
前記入力手段が入力したビット長ｐのビット列を格納する内部状態保存手段と、
該内部状態保存手段に格納されているビット長ｐのビット列に対して論理演算とシフト演算からなる演算ｆを施す演算手段を備え、
該演算手段により、前記内部状態保存手段に格納されているビット長ｐのビット列の値ｘに対して、前記演算ｆを前記内部状態保存手段に格納されているビット長ｐのビット列のｃ１，ｃ２，・・・，ｃｕビットで規定されるビット列の値ｓの数だけ施してｆｓ（ｘ）を計算し、ｐビットで表現されたその計算結果を前記内部状態保存手段に格納すると共にそのｐビットのビット列の計算結果のｏ１，ｏ２，・・・，ｏｖビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【請求項４】
ワード長がｗビットである計算装置であって、
自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ，ｄ（ｕ＋ｖ≦ｐ（ｐ：ｐは素数で２ｐ−１も素数となる数）かつ全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ，かつｃｉ≠ｏｊ）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を入力する入力手段と、
前記入力手段が入力したビット長ｐのビット列を格納する内部状態保存手段と、
該内部状態保存手段に格納されているビット長ｐのビット列に対して論理演算とシフト演算からなる演算ｆを施す演算手段と、
多倍長加算器を備え、
該演算手段により、前記内部状態保存手段に格納されているビット長ｐのビット列の値ｘに対して、前記演算ｆを前記内部状態保存手段に格納されているビット長ｐのビット列のｃ１，ｃ２，・・・，ｃｕビットで規定されるビット列の値ｓの数だけ繰り返してｆｓ（ｘ）を計算して、ｐビットで表現されたその計算結果を前記内部状態保存手段に格納すると共にそのｐビットのビット列の計算結果のｏ１，ｏ２，・・・，ｏｖビットを出力し、前記多倍長加算器により、前記内部状態保存手段に格納されたｐビットのビット列の値ｘ’とｄ（ｍｏｄ２ｐ−１）の加算を行い、その加算結果を前記内部状態保存手段に格納するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【請求項５】
ワード長がｗビットであるコンピュータで実行されるプログラムであって、
自然数ｃ，ｏ，ａ（ｃ＋ｏ≦ｐ：ｐは素数で２ｐ−１も素数となる数）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在するビット列）を少なくとも２個入力する機能と、
前記入力したビット長ｐの第１のビット列を内部状態記憶保存手段に格納する機能と、
前記入力したビット長ｐの第２のビット列を生成元保存手段に格納する機能と、
ｐ次の｛０，１｝係数の既約多項式ｆ（ｔ）（＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０）を、そのｐビットの｛０，１｝係数ｂｐ−１ｂｐ−２・・・ｂ１ｂ０のビット列により既約多項式保存手段に保存する機能と、
前記生成元保存手段に格納されているｐビットの値ｇ、前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓ及び前記既約多項式保存手段に格納されているｐビットのビット列とを用いてｇｓ（ｍｏｄｆ（ｔ））を計算し、該演算手段のｐビットの演算結果を内部状態保存手段に格納すると共に、該ｐビットの演算結果の下位ｏビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する機能を、
前記コンピュータに実行させるプログラム。
【請求項６】
ワード長がｗビットであるコンピュータにより実行されるプログラムであって、
自然数ｃ，ｏ，ａ（ｃ＋ｏ≦ｐ：ｐは素数で２ｐ−１も素数となる数）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を少なくとも３個入力する機能と、
前記入力したビット長ｐの第１のビット列を内部状態保存手段に格納する機能と、
前記入力したビット長ｐの第２のビット列を生成元保存手段に格納する機能と、
ｐ次の｛０，１｝係数の既約多項式ｆ（ｔ）（＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０）を、そのｐビットの｛０，１｝係数ｂｐ−１ｂｐ−２・・・ｂ１ｂ０のビット列により既約多項式保存手段に保存する機能と、
前記入力したビット長ｐの第３のビット列をベースポイント保存手段に保存する機能と、
前記生成元保存手段に格納されているｐビットの値ｇ、前記ベースポイント保存手段に格納されているｐビットの値ｘ及び前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓとを用いて，ｘｇｓ（ｍｏｄｆ（ｔ））を計算し、そのｐビットの計算結果を内部状態保存手段に格納すると共に、そのｐビットの下位ｏビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する機能を、
前記コンピュータに実行させるプログラム。
【請求項７】
ワード長がｗビットであるコンピュータにより実行されるプログラムであって、
自然数ｃ，ｏ，ａ，ｄ（ｃ＋ｏ≦ｐ：ｐは素数で２ｐ−１も素数となる数）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を３個入力する機能と、
前記入力したビット長ｐの第１のビット列を内部状態保存手段に保存する機能と、
前記入力したビット長ｐの第２のビット列を生成元保存手段に保存する機能と、、
ｐ次の｛０，１｝係数の既約多項式ｆ（ｔ）（＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０）を、そのｐビットの｛０，１｝係数ｂｐ−１ｂｐ−２・・・ｂ１ｂ０のビット列により既約多項式保存手段に保存する機能と、
前記入力したビット長ｐの第３のビット列をベースポイント保存手段に保存する機能と、
前記生成元保存手段に格納されているｐビットの値ｇ、前記ベースポイント保存手段に格納されているｐビットの値ｘ及び前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓとを用いて，ｘｇｓ（ｍｏｄｆ（ｔ））を計算し、該ｐビットの計算結果を前記内部状態保存手段に格納すると共に、そのｐビットの計算結果の下位ｏビットを出力し、さらに、前記多倍長加算手段により前記ベースポイント保存手段に格納されているｐビットの値ｘを多倍長とみなして、その値ｘにｄを加算し、その加算結果を前記ベースポイント保存手段に格納するという一連の処理をａ回繰り返すことにより擬似乱数を生成する機能を、
前記コンピュータに実行させるプログラム。
【請求項８】
ワード長がｗビットであるコンピュータにより実行されるプログラムであって、
自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ（ｕ＋ｖ≦ｐ（ｐ：ｐは素数で２ｐ−１も素数となる数）かつ全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ，かつｃｉ≠ｏｊ）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を入力する機能と、
前記入力したビット長ｐのビット列を内部状態保存手段に格納する機能と、
前記内部状態保存手段に格納されているビット長ｐのビット列の値ｘに対して論理演算とシフト演算からなる演算ｆを前記内部状態保存手段に格納されているビット長ｐのビット列のｃ１，ｃ２，・・・，ｃｕビットで規定されるビット列の値ｓの数だけ施してｆｓ（ｘ）を計算し、ｐビットで表現されたその計算結果を前記内部状態保存手段に格納すると共にそのｐビットのビット列の計算結果のｏ１，ｏ２，・・・，ｏｖビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する機能を、
前記コンピュータに実行させるプログラム。
【請求項９】
ワード長がｗビットであるコンピュータにより実行されるプログラムであって、
自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ，ｄ（ｕ＋ｖ≦ｐ（ｐ：ｐは素数で２ｐ−１も素数となる数）かつ全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ，かつｃｉ≠ｏｊ）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を入力する機能と、
前記入力手段が入力したビット長ｐのビット列を内部状態保存手段に格納する機能と、、
該内部状態保存手段に格納されているビット長ｐのビット列に対して論理演算とシフト演算からなる演算ｆを施す演算手段と、
多倍長加算器を備え、
前記内部状態保存手段に格納されているビット長ｐのビット列の値ｘに対して、論理演算とシフト演算からなる演算ｆを前記内部状態保存手段に格納されているビット長ｐのビット列のｃ１，ｃ２，・・・，ｃｕビットで規定されるビット列の値ｓの数だけ繰り返してｆｓ（ｘ）を計算して、ｐビットで表現されたその計算結果を前記内部状態保存手段に格納すると共にそのｐビットのビット列の計算結果のｏ１，ｏ２，・・・，ｏｖビットを出力し、前記多倍長加算器により、前記内部状態保存手段に格納されたｐビットのビット列の値ｘ’とｄ（ｍｏｄ２ｐ−１）の加算を行い、その加算結果を前記内部状態保存手段に格納するという一連の処理をａ回繰り返すことにより擬似乱数を生成する機能を、
前記コンピュータに実行させるプログラム。
【請求項１０】
ワード長がｗビットであるコンピュータにより実行されるプログラムであって、
自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ（ｕ＋ｖ≦ｐ（ｐ：ｐは素数で２ｐ−１も素数となる数）かつ全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ，かつｃｉ≠ｏｊ）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を入力する機能と、
前記入力したビット長ｐのビット列を内部状態保存手段に格納する機能と、
論理演算とシフト演算からなる演算ｆ１を施す第１の演算手段と、
論理演算とシフト演算からなる演算ｆ２を施す第２の演算手段と、
前記内部状態保存手段に格納されているビット長ｐのビット列の値ｘに対して、論理演算とシフト演算からなる第１の演算ｆ１を前記内部状態保存手段に格納されているビット長ｐのビット列のｃ１，ｃ２，・・・，ｃｕビットで規定されるビット列の値ｓの数だけ施してｆ１ｓ（ｘ）を計算し、ｐビットで表現されたその計算結果を前記内部状態保存手段に格納すると共にそのｐビットのビット列の計算結果のｏ１，ｏ２，・・・，ｏｖビットを出力し、続いて、論理演算とシフト演算からなる前記内部状態保存手段に格納された前記ｐビットのビット列の値ｘ’に対して論理演算とシフト演算からなる第２の演算ｆ２を施してｆ２（ｘ’）を計算し、そのｐビットの計算結果を内部状態保存手段に格納するという一連の処理をａ回繰り返すことにより擬似乱数を生成する機能を、
前記コンピュータに実行させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号システムに必要とされる擬似乱数を発生する装置及びプログラムに関する。
【０００２】
【従来の技術】
２００１年に施行された「電子署名法」や「ＩＴ書面一括法」などによる法整備、「電子政府構想」、さらには、電子メールやインターネットによるオンライン・ショッピングなど、情報技術基盤の進展に伴い電子社会が実現ようとしている。
【０００３】
このような電子社会のキーテクノロジーの一つとして暗号技術がある。電子社会においてはネットワークを介して電子文書など重要なコンテンツがやりとりされるため、それらのコンテンツの盗聴や改竄を防止するためのセキュリティ技術が重要となる。このセキュリティ技術に不可欠なのが暗号技術であり、暗号では乱数を生成することが重要である。。
【０００４】
乱数は全く無秩序かある一定のルールに従って発生する数値であり、このような数値を生成することが乱数生成である。この乱数生成は近年のセキュリティ技術に不可欠な要素となっており、ＰＫＩ（Ｐｕｂｌｉｃ　Ｋｅｙ　Ｉｎｆｒａｓｔｒｕｃｔｕｒｅ）を支える重要な要素技術の一つとなっている。乱数には、真性乱数と擬似乱数がある。
【０００５】
真性乱数とは、全く無秩序で周期を持たない乱数列のことである。暗号として応用できる真性乱数を生成することは非常に難しく、また長い乱数列を保存・転送することは効率面でも問題が大きい。擬似乱数は一定の算術式などを用いて生成される真性乱数とほとんど区別ができないような系列であり、真性乱数の代わりに擬似乱数を利用することは実用上非常に有益である。
【０００６】
このような擬似乱数を暗号の各種応用分野に利用するシステムにおいては、擬似乱数の安全性がそのシステムの安全性に影響し、擬似乱数の生成効率はそのシステム全体の速度性能に影響する。このため、擬似乱数には、より高い安全性と生成効率が求められる。
【０００７】
一般に、従来の擬似乱数生成方式は「安全そうな」方式であり、その安全性を明確に求めて議論されているものではなかったし、少なくとも、いくつかの統計テストにパスしているかどうかを検証しているにすぎないものが大半であった。
【０００８】
これに対して、「暗号学的擬似乱数」とは、いかなる多項式時間統計テストに対してもパスすると定義されるものである。つまり、「暗号学的擬似乱数生成方法」は安全性が数学的に証明されている擬似乱数生成方法を意味することになる。しかしながら、現在までに無条件で「暗号学的擬似乱数生成方法」となるものは知られておらず、ある種の計算量理論的な（妥当だと広く思われている）仮定が置かれている。
【０００９】
ところで、代表的な安全性証明可能擬似乱数生成法として以下のものが知られている。以下において、ｋはｑあるいはＮのビット数を表すもので、通常はセキュリティパラメータと呼ばれるものである。
【００１０】
ＢＢＳ：ｉ番目の内部状態がｓｉ　＝（ｓｉ−１）２　ｍｏｄＮ（但しＮはｂｌｕｍ数）と表現され、ｉ番目の出力をｓｉの下位ビットＯ（ｌｏｇｋ）とする方式。安全性はｂｌｕｍ数Ｎの素因数分解問題の困難性。
【００１１】
ＢＭ：ｉ番目の内部状態がｓｉ＝ｇｓｉ−１ｍｏｄｑ（但し、ｑは素数）と表現され、ｉ番目の出力をｓｉの上位ビットＯ（ｌｏｇｋ）とする方式。ｇは生成元。安全性は離散対数問題の困難性。
【００１２】
【発明が解決しようとする課題】
従来の擬似乱数発生方式は、一般に演算は高速ではあるがで安全性について数学的な根拠がなくセキュリティの面で不安であった。一方、従来の暗号学的擬似乱数生成方式（ＢＢＳ方式、ＢＭ方式）は安全性については数学的な保証があるが、演算速度の面で問題があった。
【００１３】
ＢＢＳ方式では、１回当たりの乗算により約ｌｏｇｋビット出力できる。ＢＭ方式では、１回の冪計算に約ｋ回の乗算が必要でｋ−ω（ｌｏｇｋ）ビット出力できる（尚、ωはｌｏｇｋよりも真に大きな関数のオーダーでありｋよりも小さい）。現実的なセキュリティパラメータとして、ｋ＝１０００程度が選ばれていることを考えると、ＢＢＳ方式では１回の乗算あたり約１０ビット出力でき、ＢＭ方式では１回の乗算あたり約１ビット出力できる。
【００１４】
本発明の目的は、安全性に対して数学的な保証があり、かつ従来の暗号学的擬似乱数方式よりも高速に暗号学的擬似乱数を生成できる装置及びプログラムを実現することである。
【００１５】
【課題を解決するための手段】
本発明の第１の態様の暗号学的擬似乱数生成装及びプログラムは、ワード長がｗビットでの計算を前提とする。そして、自然数ｃ，ｏ，ａ（ｃ＋ｏ≦ｐ：ｐは素数で２ｐ−１も素数となる数）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在するビット列）を少なくとも２個入力し、前記入力したビット長ｐの第１のビット列を内部状態記憶保存手段に格納し、前記入力したビット長ｐの第２のビット列を生成元保存手段に格納し、｛０，１｝係数の既約多項式ｆ（ｔ）（＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０）を、そのｐビットの｛０，１｝係数ｂｐ−１ｂｐ−２・・・ｂ１ｂ０のビット列により既約多項式保存手段に保存し、前記生成元保存手段に格納されているｐビットの値ｇ、前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓ及び前記既約多項式保存手段に格納されているｐビットのビット列とを用いてｇｓ（ｍｏｄｆ（ｔ））を計算し、該演算手段のｐビットの演算結果を内部状態保存手段に格納すると共に、該ｐビットの演算結果の下位ｏビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成することを特徴としている。
【００１６】
また、本発明の第２の態様の暗号学的擬似乱数生成装置及びプログラムは、
ワード長がｗビットでの計算を前提とする。そして、自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ（ｕ＋ｖ≦ｐ（ｐ：ｐは素数で２ｐ−１も素数となる数）かつ全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ，かつｃｉ≠ｏｊ）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を入力し、前記入力したビット長ｐのビット列を内部状態保存手段に格納し、前記内部状態保存手段に格納されているビット長ｐのビット列の値ｘに対して論理演算とシフト演算からなる演算ｆを前記内部状態保存手段に格納されているビット長ｐのビット列のｃ１，ｃ２，・・・，ｃｕビットで規定されるビット列の値ｓの数だけ施してｆｓ（ｘ）を計算し、ｐビットで表現されたその計算結果を前記内部状態保存手段に格納すると共にそのｐビットのビット列の計算結果のｏ１，ｏ２，・・・，ｏｖビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成することを特徴としている。
【００１７】
上記本発明においては、１回あたりの乗算で従来方式よりも多ビット出力できるので、擬似乱数を従来方式よりも高速に生成できる。また、生成される擬似乱数は数学的に安全性が保証された極めてセキュリティ強度の高い暗号学的擬似乱数である。
【００１８】
【発明の実施の形態】
以下、図面を参照しながら、本発明の実施形態について説明する。
｛第１実施形態｝
本発明の第１実施形態は、内部状態Ｓｉの更新が、
ｓｉ＝ｇｓ　（ｍｏｄｆ（ｔ））　　　　　　　　　　（１）
ｐ：素数で２ｐ−１が素数となる数
ｇ：ｐビットの値の生成元
ｃ：自然数
ｓ：ｐビットの内部状態ｓｉ−１の下位ｃビットの値
ｆ（ｔ）：｛０，１｝係数の既約多項式
で表現され、ｉ番目の出力は、
ｏｕｔｉ＝ｍｓｂｏ（ｓｉ）　　　　　　（２）
ｍｓｂｏ（ｓｉ）：ｐビットの内部状態ｓｉの上位ｏビット
ｏ＝ｋ−ｃ
ｃ＋ｏ≦ｐ
ｃ＝ω（ｌｏｇｋ）
ω（ｌｏｇｋ）：ωは関数のクラスを規定する記法であり、ｌｏｇｋの底は２　で表現される擬似乱数生成方式を実現する装置である。
【００１９】
ところで、上記（１）式はアルゴリズム表現を明確にしたものであり、数学的表現においては　ｓｉ＝ｇｓ　は体の抽象的な操作として規定されているので、上記（１）式を数学的に表現するならばｍｏｄｆ（ｔ）は不要となる。
【００２０】
すなわち、上記（１）式は、数学的には、
ｓｉ＝ｇｓ　　　　　　　　　　　　　　　　　（１）’
と表現することができる。
【００２１】
上記（１）、（２）式をより詳しく説明する。
ωは上述したように関数を規定する記法であり、以下のような集合である。今ｆ（ｋ）を関数とすると、ω（ｆ（ｋ））は、全ての正の実数ｒに対して、無限に多くのｋでｇ（ｋ）＞ｒ・ｆ（ｋ）を満たす集合ｇ（ｋ）の集合として定められる。
【００２２】
（１）式においてはｆ（ｋ）＝ｌｏｇｋであり、ω（ｌｏｇｋ）は、全ての正の実数ｒに対して、無限に多くのｋでｇ（ｋ）＞ｒ・ｌｏｇｋを満たす集合ｇ（ｋ）の集合となる。
また、ｃはｋによる関数であることを意味している。ω（ｌｏｇｋ）に属する関数のうち、ｋに自然数を代入したとき、自然数を取る関数を選ぶこともできる。例えば、（ｌｏｇｋ）２の小数点以下を切り上げする関数はω（ｌｏｇｋ）に属する。このようにすることにより、ｃが自然数であるとき、ω（ｌｏｇｋ）が自然数とならないという問題を回避できる。
【００２３】
また、ｃやｏが先に決まるのではなくｋが先に決まる。また、ｋの関数としてｃが決まる。また、ｏの最大値がｋ−ｃとして決まる。ｃは入力から得るようにしているが、これは想定しているｋの元でｃの関数値を入力させていることになる。
【００２４】
このとき、このようにして生成される擬似乱数列に対して、仮に、（多項式時間）統計テストで真性乱数と区別できるものが存在したとすると、そのテストを利用して離散対数問題が効率的に（多項式時間で）解けることが数学的に証明できる。しかしながら、離散対数問題は多項式時間で解けないと考えられているので、本発明の第１実施形態で生成される擬似乱数列と真性乱数が統計テストで区別されるという前提そのものが否定されることになる。したがって、本発明の第１実施形態で生成される擬似乱数列は真性乱数と区別することができず、統計テストで解くことはできないことが、背理法により数学的に証明される。
【００２５】
図１は、第１実施形態の暗号学的擬似乱数生成装置のシステム構成を示すブロック図である。
同図に示す暗号学的擬似乱数生成装置１０は、中央処理部１１、入力部１２、内部状態保存部１３、生成元保存部１４、既約多項式保存部１５、多項式乗算器１６、剰余演算器１７及び出力部１８から構成される。この装置１０の計算部で処理する数値データのワード長はｗビットである。
【００２６】
中央処理部１１は他の構成要素とインターフェイスを介して接続されており、必要に応じて作業を各構成要素に割り当てたり、構成要素間で授受される情報を管理する。
【００２７】
入力部１２は、３個の自然数ｃ，ｏ，ａ及びビット長ｐのビット列を２個入力する。但し、ｐは素数であり、２ｐ　−１も素数となる数である。
内部状態保存部１３は、ｎワードを保存する書き換え可能な記憶装置であり、ビット長ｐのビット列を格納する。但し、ｒ＜ｗでｐ＝ｎｗ−ｒとする。
【００２８】
生成元保存部１４は、ｎワードを保存する書き換え可能な記憶装置であり、ビット長ｐのビット列を格納する。但し、ｒ＜ｗでｐ＝ｎｗ−ｒとする。
既約多項式保存部１５はｐビットの記憶装置である。この既約多項式保存部１５に記憶されているｐビットのデータのビット列表現がｂｐ−１ｂｐ−２・・・ｂ１ｂ０であるとすると、これは、既約多項式
ｆ（ｔ）＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０　　　（３）
に対応する。なお、既約多項式とは因数分解ができない多項式のことである。
【００２９】
多項式乗算器１６は、ｐビットのビット列が２つ与えられたとき、ビット列に対応する多項式の積を計算し、多項式で表現される積をビット表現の値で返す。ｐビットのビット列をｂｐ−１ｂｐ−２・・・ｂ１ｂ０であるとすると、これは多項式
ｔｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０　　　　　　　　　　（４）
に対応する。尚、この多項式（４）の積は高々２ｐビットで表現される。
【００３０】
剰余演算器１７は、前記２ｐビットで表現される多項式（４）について、既約多項式（３）で割った余りの多項式をビット表現で返す。既約多項式（３）はｐ次なので、余りは常にｐ−１次以下で、ｐビットで表現される。
【００３１】
出力部１８は、多項式乗算器１６のｐビットで表現される演算結果のうち、上位ｏビットを出力する。
次に、上記構成の暗号学的擬似乱数生成装置１０の動作（暗号生成のアルゴリズム）を図２のフロチャートを参照しながら説明する。
【００３２】
まず、入力部１２を介して自然数ｃ，ｏ，ａ及びｐビットのビット列ｗ１、ｗ２を入力する（ステップＳ１１）。次に、ｃ＋ｏ＞ｐ（条件１）またはビット列ｗ１，ｗ２の少なくとも一方の全ビットが“０”もしくは“１”である（条件２）か判断する（ステップＳ１２）。そして、少なくとも、上記条件１，２のいずれか一方が成立すればステップＳ１１に戻る。条件１が満足されないと生成される暗号の安全性が保証できないからである。また、条件２を満足するビット列は初期データとして不適切だからである。
【００３３】
一方、上記条件１，２のいずれも成立しなければ、ｐビットのビット列ｗ１、ｗ２を、それそれ、内部状態保存部１３と生成元保存部１４に格納し（ステップＳ１３）、カウンター変数ｉを０にセットする（ステップＳ１４）。
【００３４】
次に、生成元保存部１４に格納されているｐビットで表現される数値をｇとする（ステップＳ１５）。続いて、内部状態保存部１３に格納されているｐビットの下位ｃビットで表現される数値をｓとする（ステップＳ１６）。
【００３５】
多項式乗算器１６及び剰余演算器１７により、ｇのｓ乗（＝ｇｓ）を計算し、その計算結果を内部状態保存部１３に格納する（ステップＳ１７）。
ステップＳ１７の計算においては、ｓ（＝ｂｃ−１ｂｃ−２・・・ｂ０）のビット列を基に、
【００３６】
【数１】
2004038020.tif 000003
【００３７】
を演算する。この演算は、高々ｃ回の積で実現される。このｇｓの演算においては、ｂｊ＝１（ｊ＝ｃ−１，ｃ−２，・・・、ｂ１、ｂ０）となっている項ｇ２ｊについてのみ計算すればよいので、ｇから次々２乗していくとｃ−１回の乗算で実現される　外１　。式（５）における各乗算は多項式乗算器１６により行う。
【００３８】
【外１】
2004038020.tif 000004
【００３９】
また、各乗算直後には剰余演算器１７を実行してｇｓ（ｍｏｄｆ（ｔ））を計算し、その計算結果を利用してｇｓの表現がｐビットとなるようにする。そして、ｐビットで表現されたｇｓの計算結果を内部状態保存部１３に格納する。
【００４０】
ステップＳ１７に続いて、出力部１８が内部状態保存部１３に格納されているｐビットのｇｓの演算結果のうち、その上位ｏビットを乱数として出力する（ステップＳ１８）。
【００４１】
次に、変数ｉを１インクリメントし（ステップＳ１９）、ｉ＜ａであるか判断する（ステップＳ２０）。そして、ｉ＜ａあればステップＳ１６に戻る。
このようにして、ｉ＝ａとなるまで、ステップＳ１６〜Ｓ２０の処理を繰り返してａ個の乱数を生成する。そして、乱数をａ個出力すると処理を終了する。
【００４２】
このように、第１実施形態では、ｇｓ（ｍｏｄ（ｆ（ｔ））を計算し、このｐビットの計算結果の上位ｏビットを乱数としてを内部状態保存部１３に格納すると共に、その内部状態保存部１３に格納されたｏビットの値を乱数として出力するという一連の処理をａ回繰り返しながら暗号学的擬似乱数をａ個生成していく。
｛第２実施形態｝
本発明の第２実施形態は、内部状態Ｓｉの更新が、
ｓｉ＝ｘｇｓ（ｍｏｄｆ（ｔ））　　　　　　　　　　（６）
ｐ：素数で２ｐ−１も素数となる数
ｇ：第１のｐビットの値の生成元
ｘ：第２のｐビットの値
ｓ：ｐビットの内部状態ｓｉ−１の下位ｃビットの値
で表現され、ｉ番目の出力は、
ｏｕｔｉ＝ｍｓｂｏ（ｓｉ）　　　　　　　　（７）
ｍｓｂｏ（ｓｉ）：ｐビットの内部状態ｓｉの上位ｏビット
ｏ＝ｋ−ｃ
ｃ＋ｏ≦ｐ
ｃ＝ω（ｌｏｇｋ）
で表現される擬似乱数生成方式を実現する装置である。
【００４３】
図３は、本発明の第２実施形態の暗号学的擬似乱数生成装置のシステム構成を示すブロック図である。
同図において、図１の構成要素と同一構成要素には同じ符号を付与している。同図に示す暗号学的擬似乱数生成装置２０は、図１の第１実施形態の暗号学的擬似乱数生成装置１０にベースポイント保存部２１を付加した構成となっており、その他の構成要素は暗号学的擬似乱数生成装置１０と同様である。したがって、以下の暗号学的擬似乱数生成装置２０の構成の説明においては、暗号学的擬似乱数生成装置１０と相違する構成要素のみについて説明する。なお、本装置２０の計算装置のワード長は第１実施形態の暗号学的擬似乱数生成装置１０と同様にｗビットである。
【００４４】
入力部１２ａは、入力部１２と同様に３個の自然数ｃ，ｏ，ａを入力するが、入力部１２とは異なりビット長ｐのビット列を２個ではなく３個入力する。
ベースポイント保存部２１は、ｎワード（１ワードはｗビット）を保存する書き換え可能な記憶装置である。ただし、ｒ＜ｗでｐ＝ｎｗ−ｒである。
【００４５】
上記構成の暗号学的擬似乱数生成装置２０の動作（暗号生成アルゴリズム）を図４のフロチャートを参照しながら説明する。
まず、入力部１２を介して自然数ｃ，ｏ，ａ及びｐビットのビット列ｗ１、ｗ２、ｗ３を入力する（ステップＳ３１）。次に、ｃ＋ｏ＞ｐ（条件１）またはビット列ｗ１，ｗ２の少なくとも一方の全ビットが゛“０”もしくは“１”である（条件２）か判断する（ステップＳ３２）。そして、少なくとも、上記条件１，２のいずれか一方が成立すればステップＳ３１に戻る。上述したように、条件１が満足されないと生成される暗号の安全性が保証できないからである。また、条件２を満足するビット列は初期データとして不適切だからである。
【００４６】
一方、上記条件１，２のいずれも成立しなければ、ｐビットのビット列ｗ１、ｗ２、ｗ３を、それそれ、内部状態保存部１３，生成元保存部１４及びベースポイント保存部２１に格納し（ステップＳ３３）、カウンター変数ｉを０にセットする（ステップＳ３４）。
【００４７】
次に、生成元保存部１４に格納されているｐビットで表現される数値をｇとし、ベースポイント保存部２１に格納されているｐビットの下位ｃビットで表現される数値をｘとする（ステップＳ３５）。続いて、内部状態保存部１３に格納されているｐビットの下位ｃビットで表現される数値をｓとする（ステップＳ３６）。
【００４８】
多項式乗算器１６及び剰余演算器１７により、ｇのｓ乗（＝ｇｓ）とｘの積を計算し、その計算結果を内部状態保存部１３に格納する（ステップＳ３７）。
ステップＳ３７の計算においては、ｓ（＝ｂｃ−１ｂｃ−２・・・ｂ０）のビット列を基に、
【００４９】
【数２】
2004038020.tif 000005
【００５０】
を演算する。この演算は、前述した第２実施形態と同様にして多項式乗算器１６と剰余演算器１７により行い、常に、ｇｓの表現がｐビットとなるようにする。そして、更に、ｘとｇｓの積ｘｇｓを計算する。そして、剰余演算器１７を実行して得たｐビットで表現されたｘｇｓの計算結果を内部状態保存部１３に格納する。
【００５１】
ステップＳ３７に続いて、出力部１８が内部状態保存部１３に格納されているｐビットのｘｇｓの演算結果のうち、その上位ｏビットを乱数として出力する（ステップＳ３８）。
【００５２】
次に、変数ｉを１インクリメントし（ステップＳ３９）、ｉ＜ａであるか判断する（ステップＳ４０）。そして、ｉ＜ａあればステップＳ３６に戻る。
このようにして、ｉ＝ａとなるまで、ステップＳ３６〜Ｓ４０の処理を繰り返してａ個の乱数を生成する。そして、乱数をａ個出力すると処理を終了する。
【００５３】
このように、第２実施形態では、ｘｇｓ（ｍｏｄ（ｆ（ｔ））を計算し、このｐビットの計算結果の上位ｏビットを乱数としてを内部状態保存部１３に格納すると共に、その内部状態保存部１３に格納されたｏビットの値を乱数として出力するという一連の作業をａ回繰り返しながら暗号学的擬似乱数をａ個生成していく。第２実施形態によれば、第１実施形態よりも内部状態保存部１３に格納される内部状態の数が多くなるため、第１実施形態よりも安全性が高い暗号学的擬似乱数を生成できる。
｛第３実施形態｝
本発明の第３実施形態は、内部状態Ｓｉの更新が、
ｓｉ＝（ｘ＋ｄｍｏｄ２ｐ−１）ｇｓ　　　　　　　（９）
ｐ：素数で２ｐ−１も素数となる数
ｇ：第１のｐビットの値の生成元
ｘ：第２のｐビットの値
ｄ：自然数
ｓ：ｐビットの内部状態ｓｉ−１の下位ｃビットの値
で表現され、ｉ番目の出力は、
ｏｕｔｉ＝ｍｓｂｏ（ｓｉ）　　　　　　　　　　　　　　　　（１０）
ｍｓｂｏ（ｓｉ）：ｐビットの内部状態ｓｉの上位ｏビット
ｏ＝ｋ−ｃ
ｃ＋ｏ≦ｐ
ｃ＝ω（ｌｏｇｋ）
で表現される擬似乱数生成方式を実現する装置である。
【００５４】
図５は、本発明の第３実施形態の暗号学的擬似乱数生成装置のシステム構成を示すブロック図である。
同図において、図３の構成要素と同一構成要素には同じ符号を付与している。同図に示す暗号学的擬似乱数生成装置３０は、図３の第２実施形態の暗号学的擬似乱数生成装置２０に多倍長加算器３１を付加した構成となっており、その他の構成要素は暗号学的擬似乱数生成装置２０と同様である。したがって、以下の暗号学的擬似乱数生成装置３０の構成の説明においては、暗号学的擬似乱数生成装置２０と相違する構成要素のみについて説明する。なお、本装置３０の計算装置のワード長は第２実施形態の暗号学的擬似乱数生成装置２０と同様にｗビットである。
【００５５】
入力部１２ｂは、入力部１２ａとは異なり４個の自然数ｃ，ｏ，ａ，ｄを入力し、入力部１２ａと同様にビット長ｐのビット列を３個入力する。
多倍長加算器３１は、高々ｐビット（高々ｎワード）で表現される２つの自然数の和を計算し、その計算結果が２ｐビット以上になった場合は、最上位ビットを０にし、その後１を加える（この操作は、上記和の計算結果を２ｐ−１で割った余りを求める演算に相当する）。
【００５６】
上記構成の暗号学的擬似乱数生成装置３０の動作（暗号生成アルゴリズム）を図６のフロチャートを参照しながら説明する。
まず、入力部１２を介して４個の自然数ｃ，ｏ，ａ，ｄ及びｐビットのビット列ｗ１、ｗ２、ｗ３を入力する（ステップＳ５１）。次に、ｃ＋ｏ＞ｐ（条件１）またはビット列ｗ１，ｗ２の少なくとも一方の全ビットが゛“０”もしくは“１”である（条件２）か判断する（ステップＳ５２）。そして、少なくとも、上記条件１，２のいずれか一方が満足されていればステップＳ５１に戻る。条件１が満足されないと生成される暗号の安全性が保証できないからである。また、条件２を満足するビット列は初期データとして不適切だからである。
【００５７】
一方、上記条件１，２のいずれも成立しなければ、ｐビットのビット列ｗ１、ｗ２、ｗ３を、それそれ、内部状態保存部１３，生成元保存部１４及びベースポイント保存部２１に格納し（ステップＳ５３）、カウンター変数ｉを０にセットする（ステップＳ５４）。
【００５８】
次に、生成元保存部１４に格納されているｐビットで表現される数値をｇとし、ベースポイント保存部２１に格納されているｐビットの下位ｃビットで表現される数値をｘとする（ステップＳ５５）。続いて、内部状態保存部１３に格納されているｐビットの下位ｃビットで表現される数値をｓとする（ステップＳ５６）。
【００５９】
多項式乗算器１６及び剰余演算器１７により、ｇのｓ乗（＝ｇｓ）とｘの積を計算し、その計算結果を内部状態保存部１３に格納する（ステップＳ５７）。
ステップＳ５７の計算においては、ｓ（＝ｂｃ−１ｂｃ−２・・・ｂ０）のビット列を基に、
【００６０】
【数３】
2004038020.tif 000006
【００６１】
を演算する。この式（１１）の演算は、第１実施形態と同様に多項式乗算器１６と剰余演算器１７により行う。そして、更に、ｘとｇｓの積ｘｇｓを計算する。そして、剰余演算器１７を実行して得たｐビットで表現されたｘｇｓの計算結果を内部状態保存部１３に格納する。
【００６２】
ステップＳ５７に続いて、出力部１８が内部状態保存部１３に格納されているｐビットのｘｇｓの演算結果のうち、その上位ｏビットを乱数として出力する（ステップＳ５８）。
【００６３】
次に、変数ｉを１インクリメントし、多倍長加算器３１によりｘ＋ｄ（ｍｏｄ２ｐ−１）を計算する。この計算結果はｐビットで表現される。この計算結果をベースポイント保存部２１に格納する（ステップＳ５９）。続いて、ｉ＜ａであるか判断する（ステップＳ６０）。そして、ｉ＜ａあればステップＳ５６に戻る。
【００６４】
このようにして、ｉ＝ａとなるまで、ステップＳ５６〜Ｓ６０の処理を繰り返してａ個の乱数を生成する。そして、乱数をａ個出力すると処理を終了する。
このように、第３実施形態では、ｘｇｓ（ｍｏｄ（ｆ（ｔ））を計算し、このｐビットの計算結果を内部状態保存部１３に格納すると共に、その内部状態保存部１３に格納されたｐビットの上位ｏビットを乱数として出力し、更にベースポイント保存部２１に格納されている値ｘを多倍長数値とみなして、それに自然数ｄを２ｐ−１で割った余りを加算し、その加算結果をベースポイント保存部２１に格納するという一連の処理をａ回繰り返しながら暗号学的擬似乱数をａ個生成していく。
【００６５】
第３実施形態によれば、ベースポイント保存部２１に格納されるｐビットの値ｘもランダムに変化するため、第２実施形態よりも内部状態保存部１３に格納される内部状態の数が多くなり、第２実施形態よりも安全性が高い暗号学的擬似乱数を生成できる。
｛実施例｝
本発明の理解を容易なものとするために、最も構成が簡素な第１実施形態の暗号学的擬似乱数生成装置１０の実施例について説明する。なお、以下の実例では説明を簡略化するためにＫ＝５としているが、現実の利用では、例えばｋ＝１０００などが使用される。
【００６６】
本装置１０では、２ｐ−１はメルセンヌ素数でないといけないので、ｐ＝５とする。このとき、２ｐ−１も素数３１となる。入力部１２に自然数ｃ＝５，ｏ＝２，ａ＝４が入力されるものとする。ここで、５次の既約多項式ｆ（ｔ）のひとつとして、ｆ（ｔ）＝ｔ５＋ｔ２＋１を考える。また、生成元ｇとして、ｇ＝ｔ２を考える。このとき、既約多項式ｆ（ｔ）は“００１０１”の５ビットのビット列｛ｂ４ｂ３ｂ２ｂ１ｂ０｝で表現され、生成元ｇは“００１００”の５ビットのビット列で表現される。また、入力される初期内部状態を“０１１１１”とする。
【００６７】
この場合、図２のフロチャートの動作は以下のようになる。
［ｉ＝０のとき］
内部状態が０１１１１なので、下位３ビット（ｃ＝３）は１１１であり、その値は７（ｓ＝７）なので（ｔ２）７（ｍｏｄｆ（ｔ））を計算すると、ｔ４＋ｔ３＋ｔ２＋１となる。これは１１１０１のビット表現となるので、その上位２ビットの１１（ｏ＝２）を出力する。
［ｉ＝１のとき］
内部状態が１１１０１なので、下位３ビット（ｃ＝３）は１０１であり、その値は５（ｓ＝５）なので（ｔ２）５（ｍｏｄｆ（ｔ））を計算すると、ｔ４＋１となる。これは１０００１のビット表現となるので、その上位２ビットの１０（ｏ＝２）を出力する。
［ｉ＝２のとき］
内部状態が１０００１なので、下位３ビット（ｃ＝３）は００１であり、その値は１（ｓ＝１）なので（ｔ２）１（ｍｏｄｆ（ｔ））を計算するとｔ２となる。これは００１００のビット表現となるので、その上位２ビットの００（ｏ＝２）を出力する。
［ｉ＝３のとき］
内部状態が００１００なので、下位３ビット（ｃ＝３）は１００であり、その値は４（ｓ＝４）なので（ｔ２）４（ｍｏｄｆ（ｔ））を計算するとｔ３＋ｔ２＋１となる。これは０１１０１のビット表現となるので、その上位２ビットの０１（ｏ＝２）を出力する。
［ｉ＝４のとき］
ｉ＝ａ＝４となり処理を停止する。
｛第４実施形態｝
本発明の第４実施形態は、内部状態ｓｉの更新が
ｓｉ＝ｆｓ（ｓｉ−１）　　　　　　　　　　　　（１２）
ｐ：素数で２ｐ−１も素数となる数
ｓ：ｐビットのｓｉ−１の特定のｃビットの値
で表現され、ｉ番目の出力は
ｏｕｔｉ＝ｓｉのｓを求めるために使用されたビッ以外の特定ビットで表現される擬似乱数生成方式を実現する装置である。
【００６８】
但し、ｆは線形変換であり、これは論理演算器とシフト演算器で実現することができる。ｆｓはｆ演算をｓ回繰り返す演算である。
本実施形態では、ｆを論理演算器とシフト演算器により実行するため、ｆ演算を乗算器を使用するよりも高速に行うことができる。また、ｓはｓｉ−１の特定のｃビットを取り出してそのｃビットを数値化したもので、ｏｕｔｉを定める特定のビットはｓを定めるビット以外のビットから選ばれるものとする。
【００６９】
このように構成することにより、非常に簡単に計算できるｆに対してもｓの効果により、高い安全性を確保できる乱数を生成できるようになる。特に、後述する実施例で示すようなｆの選び方及びｓを定めるビットの規定の仕方によっては生成される擬似乱数列に対して、仮に（多項式）統計テストで真性乱数と区別できるものが存在したとすると、その統計テストを利用して離散対策問題が効率的に（多項式時間で）解けることが数学的に証明できるようにすることができる。　しかしながら、離散対策問題は多項式時間では解けないと考えられているので、本発明の第４実施形態で生成される擬似乱数列と真性乱数が統計テストで区別されるという前提が否定されることになる。したがって、背理法により、本発明の第４実施形態で生成される擬似乱数列は統計テストにより（多項式時間で）真性乱数と区別することができないことになる。
【００７０】
図７は、本発明の第４実施形態の暗号学的擬似乱数生成装置のシステム構成を示すブロック図である。
同図に示す暗号学的擬似乱数生成装置４０は、中央処理部４１、入力部４２、内部状態保存部４３、演算部４４及び出力部４５から構成される。
【００７１】
中央処理部４１は、システム内の他の各構成要素とインターフェイスを介して説則されており、必要に応じて作業を各構成要素に割り当てたり、各構成要素間で授受される情報を管理する。
【００７２】
入力部４２は、自然数ｃ１，・・・，ｃｕ，ｏ１，，・・・，ｏｖ，ａ及びビット長ｐを入力する。ただし、（ｕ＋ｖ≦ｐ）かつ（全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ）かつ（ｃｉ≠ｏｊ）である。但し、ｐは素数で２ｐ−１も素数となるような数とする。また、本装置４０の計算装置のワード長はｗビットである。
【００７３】
内部状態保存部４３は、ｎワードを保存する書き換え可能な記憶装置であり、ビット長ｐのビット列を格納する。ただし、ｒ＜ｗでｐ＝ｎｗ−ｒとする。
演算部４４は、ワード単位の論理演算器４４とシフト演算器４４ｂからなり、内部状態保存部４３に保存されているｐビットをワード単位で状態更新する計算ｆｓ（ｘ）を実行する。
【００７４】
出力部４５は、上記計算ｆｓ（ｘ）の結果を出力する。
上記構成の第４実施形態の暗号学的擬似乱数生成装置４０の動作（アルゴリズム）を図８のフロチャートを参照しながら説明する。
【００７５】
まず、入力部４２は上記自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ及びビット長ｐのビット列ｗを入力する（ステップＳ６１）。
次に、｛ｕ＋ｖ＞ｐである｝（条件１）または｛ｃｉ＞ｐもしくはｏｉ＞ｐとなるｉが存在する｝（条件２）または｛ｃｉ＝ｏｊとなるｉ，ｊが存在する｝（条件３）または｛ビット列ｗの全てのビットが０または１である｝（条件４）か判断する（ステップＳ６２）。そして、条件１，２，３または４のいすれかが成立すれば、ステップＳ６１に戻り、入力部４２が新たな自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ及びビット長ｐのビット列ｗを入力する。
【００７６】
一方、ステップＳ６２で条件１，２，３，４のいずれも成立しないと判断すると、ｐビットのビット列ｗを内部状態保存部４３に格納し（ステップＳ６３）、内部状態保存部４３に格納されているｐビットの値をｘとする（ステップＳ６４）。　次に、カウンター変数ｉを０にセットし（ステップＳ６５）、内部状態更新の演算部４４の論理演算器４４ａとシフト演算器４４ｂにより、ｘに対してｆの計算をｓ回施し（ｆｓを演算し）、その計算結果（ｐビットで表現されたｆｓの値）を内部状態保存部４３に格納する（ステップＳ６７）。
【００７７】
出力部４５は、内部状態保存部４３に格納されているｐビットのうち、ｏ１，ｏ２，・・・，ｏｖで規定される全ビットを出力する（ステップＳ６８）。そして、変数ｉを１インクリメントして（ステップＳ６９）、ｉ＜ａであるか判断し（ステップＳ７０）、ｉ＜ａであればステップＳ６６に戻る。
【００７８】
このようにして、ｉ＝ａとなるまで、ステップＳ６６〜Ｓ７０の処理を繰り返しながらａ個の乱数を出力部４５から出力していく。そして、ステップＳ７０でｉ＝ａであると判断すると処理を終了する。
｛第５実施形態｝
本発明の第５実施形態は、内部状態ｓｉの更新が
ｓｉ＝ｆｓ（ｓｉ−１））　　　　　　　　　　　　（１３）
ｐ：素数で２ｐ−１も素数となる数
ｓ：ｐビットのｓｉ−１の特定のｃビットの値
で表現され、ｉ番目の出力は
ｏｕｔｉ＝ｓｉのｓを求めるために使用されたビット以外の特定ビットで表現される擬似乱数生成方式を実現する装置である。
【００７９】
但し、ｆは線形変換であり、これは論理演算器とシフト演算器で実現することができる。ｆｓはｆ演算をｓ回繰り返す演算である。
図９は、本発明の第５実施形態のシステム構成を示すブロック図である。
同図に示す暗号学的擬似乱数生成装置５０おいて、図７の第４実施形態の暗号学的擬似乱数生成装置４０の構成要素と同じ構成要素には同じ符号を付記している。暗号学的擬似乱数生成装置５０と暗号学的擬似乱数生成装置４０との構成の相違は、暗号学的擬似乱数生成装置５０が更に多倍長加算器５１を備えていることである。また、入力部４２ａが自然数ｃ１，ｃ２，・・・，ｃｕ−１，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａに加えて自然数ｄを入力することである。したがって、暗号学的擬似乱数生成装置５０の構成の説明は、多倍長加算器５１についてのみ行い、他の構成要素の説明は省略する。
【００８０】
多倍長加算器５１は、高々ｐビット（高々ｎワード）で表現される２つの自然数に対して和を計算し、その計算結果が２ｐビット以上となった場合はその最上位ビットを０にし、その後１を加算する（この操作は、和の結果を２ｐ−１で割った余りを求める演算に相当する）。
【００８１】
上記構成の第５実施形態の暗号学的擬似乱数生成装置５０の動作（アルゴリズム）を図１０のフロチャートを参照しながら説明する。
まず、入力部４２ａは自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ，ｄ及びビット長ｐのビット列ｗを入力する（ステップＳ８１）。
【００８２】
次に、｛ｕ＋ｖ＞ｐである｝（条件１）または｛ｃｉ＞ｐもしくはｏｉ＞ｐとなるｉが存在する｝（条件２）または｛ｃｉ＝ｏｊとなるｉ，ｊが存在する｝（条件３）または｛ビット列ｗの全てのビットが０または１である｝（条件４）か判断する（ステップＳ８２）。そして、条件１，２，３または４のいすれかが成立すれば、ステップＳ８１に戻り、入力部４２ａが新たな自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ，ｄ及びビット長ｐのビット列ｗを入力する。
【００８３】
一方、ステップＳ８２で条件１〜４のいずれも成立しないと判断すると、ｐビットのビット列ｗを内部状態保存部４３に格納し（ステップＳ８３）、内部状態保存部４３に格納されているｐビットの値をｘとする（ステップＳ８４）。
【００８４】
次に、カウンター変数ｉを０にセットし（ステップＳ８５）、内部状態更新の演算部４４の論理演算器４４ａとシフト演算器４４ｂにより、ｘに対してｆの計算をｓ回施し（ｆｓを演算し）、その計算結果（ｐビットで表現されたｆｓの値）を内部状態保存部４３に格納する（ステップＳ８７）。
【００８５】
出力部４５は、内部状態保存部４３に格納されているｐビットのうち、ｏ１，ｏ２，・・・，ｏｖで規定される全ビットを出力する（ステップＳ８８）。そして、変数ｉを１インクリメントし、多倍長加算器５１によりｘ＋ｄ（ｍｏｄ２ｐ−１）を計算する。ここで、計算結果はｐビットで表現される。この計算結果を内部状態保存部４３に格納する（ステップＳ６９）。次に、ｉ＜ａであるか判断し（ステップＳ９０）、ｉ＜ａであればステップＳ８６に戻る。
【００８６】
このようにして、ｉ＝ａとなるまで、ステップＳ８６〜Ｓ９０の処理を繰り返しながらａ個の乱数を出力部４５から出力していく。そして、ステップＳ９０でｉ＝ａであると判断すると処理を終了する。
｛第６実施形態｝
本発明の第６実施形態は、内部状態ｓｉの更新が
ｓｉ＝ｆｓ（ｆ’（ｓｉ−１））　　　　　　　　　　　　（１４）
ｐ：素数で２ｐ−１も素数となる数
ｓ：ｐビットのｓｉ−１の特定のｃビットの値
で表現され、ｉ番目の出力は
ｏｕｔｉ＝ｓｉのｓを求めるために使用されたビット以外の特定ビットで表現される擬似乱数生成方式を実現する装置である。
【００８７】
但し、ｆ及びｆ’は線形変換であり、これは論理演算器とシフト演算器で実現することができる。ｆｓはｆ演算をｓ回繰り返す演算である。
図１１は、本発明の第６実施形態のシステム構成を示すブロック図である。
同図に示す暗号学的擬似乱数生成装置６０おいて、図７の第４実施形態の暗号学的擬似乱数生成装置４０の構成要素と同じ構成要素には同じ符号を付けている。
【００８８】
暗号学的擬似乱数生成装６０と暗号学的擬似乱数生成装置４０との構成の相違は、暗号学的擬似乱数生成装置６０が二系統の演算部４４（第１の演算部４４ー１と第２の演算部４４ー２）を備えていることである。第１及び第２の演算部４４ー１，４４−２は、演算部４４と同様な構成となっており、論理演算器４４ａとシフト演算器４４ｂを備えている。
【００８９】
上記構成の第６実施形態の暗号学的擬似乱数生成装置６０の動作（アルゴリズム）を図１２のフロチャートを参照しながら説明する。
まず、入力部４２は自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ及びビット長ｐのビット列ｗを入力する（ステップＳ１０１）。
【００９０】
次に、｛ｕ＋ｖ＞ｐである｝（条件１）または｛ｃｉ＞ｐもしくはｏｉ＞ｐとなるｉが存在する｝（条件２）または｛ｃｉ＝ｏｊとなるｉ，ｊが存在する｝（条件３）または｛ビット列ｗの全てのビットが０または１である｝（条件４）か判断する（ステップＳ１０２）。そして、条件１，２，３または４のいすれかが成立すれば、ステップＳ１０１に戻り、入力部４２が新たな自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ及びビット長ｐのビット列ｗを入力する。
【００９１】
一方、ステップＳ１０２で条件１〜４のいずれも成立しないと判断すると、ｐビットのビット列ｗを内部状態保存部４３に格納し（ステップＳ１０３）、内部状態保存部４３に格納されているｐビットの値をｘとする（ステップＳ１０４）。
【００９２】
次に、カウンター変数ｉを０にセットし（ステップＳ１０５）、内部状態保存部４３に格納されているｐビットのビット列のｃ１，ｃ２，・・・，ｃｕビットで表現される数値をｓとする（ステップＳ１０６）。
【００９３】
次に、第１の演算部４４の論理演算器４４ａとシフト演算器４４ｂによりｘに対してｆ（ｆ１）の計算をｓ回施し、その計算結果ｆｓ（ｘ）を内部状態保存部４３に格納する（ステップＳ１０７）。そして、出力部４５により内部状態保存部４３に格納されているｐビットのうち、ｏ１，ｏ２，・・・，ｏｖで規定される全ビットを出力する（ステップＳ１０８）。そして、変数ｉを１インクリメントし、第２の演算部４４の論理演算器４４ａとシフト演算器４４ｂによりｘに対して，ｆ’（ｆ２）の計算を施し、そのｐビットの計算結果ｆ’（ｘ）を内部状態保存部４３に格納する（ステップＳ１０９）。次に、ｉ＜ａであるか判断し（ステップＳ１１０）、ｉ＜ａであればステップＳ１０６に戻る。
【００９４】
このようにして、ｉ＝ａとなるまで、ステップＳ１０６〜Ｓ１１０の処理を繰り返しながらａ個の乱数を出力部４５から出力していく。そして、ステップＳ１１０でｉ＝ａであると判断すると処理を終了する。
｛第４実施形態の実施例｝
第４実施形態では、２ｐ−１はメルセンヌ素数でないといけないので、ｐ＝１１２１３とする。このとき、１１２１３は素数であり、２１１２１３−１も素数である。また、中央処理部４１は３２ｂｉｔＣＰＵであることを想定して、ｗ＝３２とおくと、内部状態はｎ＝３５１ワードで表現される。但し、３５１ワードのうち、１ワードは１３ビットを内部状態の表現として用いる（ｒ＝１３）。今、内部状態ｘをｘ＝（ｘ３５０，・・・，ｘ１，ｘ０）で表現される。内部状態ｘの更新操作を表現するｆは下記のように表現される。
【００９５】
ｆ（ｘ）＝（ｘ３５０，・・・，ｘ２，（ｘ１の上位１３ビット））
ｘ１の上位１３ビットはマスク操作つまり論理演算器４４ａ内の論理積演算器により計算される。また、ｘ３５１は下記の論理演算により計算される。
【００９６】
ｘ３５１＝（ｘ１７５）　ＥＯＲ　（Ａ）
排他的論理和ＥＯＲは、論理演算器４４ａ内の排他的論理和演算器により計算される。また、は下記の式により計算される。
【００９７】
Ａ＝ｓｈｉｆｔｒｉｇｈｔ（ｙ）　ＥＯＲ　ｂ
ただし、ｙはｘ０とｘ１の下位１６ビットを繋げた３２ビットであり、シフト演算器４４ｂによりｘ０とｘ１に対して右シフト演算ｓｈｉｆｔｒｉｇｈｔを施すことにより得られる。ｂはｙの最下位ビットが０ならば“０”で、ｙの最下位ビットが１ならば１６進数表記で“Ｅ４ＢＤ７５Ｆ５”なる値である。よって、Ａは論理積、論理和、シフト演算、排他的論理和のみで実現され、ｆの計算は論理演算及びシフト演算のみで実現されている。また、内部状態ｘはこのような値をとることによりｆを複数回施して何回か後に元に戻るが、この周期が２１１２１３−１であることが数学的に証明される。
【００９８】
さらに、ｘとｆが与えられているとき、ｆｓ（ｘ）の値からｓを求める問題は離散対策問題の一種であり、非常に計算が困難な問題の一つである。一般に、
ｃ＝ω（ｌｏｇｐ）ととり、特に、ｃ１，ｃ２，・・・，ｃｕとして内部状態の下位ｃビット、ｏ１，ｏ２，・・・，ｏｖとして内部状態の上位１１２１３−ｃビットとすると、擬似乱数列のビット予測問題は困難になることが数学的に証明される。もし仮に上記擬似乱数列のビット予測問題を解くことが可能だとすると、上記離散問題が解けることが示されることになる。
【００９９】
本発明の第１〜第６実施形態は、ＢＢＳ方式、ＢＭ方式に対して速度の面で以下に述べるような優位性を有する。
ＢＢＳ方式では、１回当たりの乗算あたり約ｌｏｇｋビット出力できる。ＢＭ方式では１回の冪計算に約ｋ回の乗算が必要で約ｋビット出力できる。これに対して本発明の第４〜第６実施形態では１回の冪計算にω（ｌｏｇｋ）の乗算が必要で、ｋ−ω（ｌｏｇｋ）ビット出力できる。現実的なセキュリティパラメータとして、
ｋ＝１０００程度が選ばれていることを考えると、ＢＢＳ方式では１回の乗算あたり約１０ビット出力できる。ＢＭ方式では１回の乗算あたり約１ビット出力できる。これに対して、本発明の第１〜第６実施形態では、１回の冪計算が１０回くらいの乗算でできると考えると、１回の乗算あたり約９９ビット出力でき、ＢＢＳ方式の約１０倍の高速化が可能になっている。
【０１００】
また、本発明の第４〜第６実施形態においては、線形変換行列Ｍの選び方を工夫することにより、多倍長演算を不要とすることができ、さらなる高速化が可能である。
【０１０１】
｛本発明の暗号学的擬似乱数生成装置の応用例｝
図１３は、本発明の暗号学的擬似乱数生成装置の応用例であるディジタル署名系のシステム構成を示す図である。
【０１０２】
同図に示すディジタル署名系１００は、署名作成部１０１、鍵生成部１０２及び検証部１０３から構成されている。本発明の暗号学的擬似乱数生成装置２００（例えば、第１実施形態〜第６実施形態の暗号学的擬似乱数生成装置１０，２０，３０，４０，５０，６０）は、ディジタル署名系１００に対して擬似乱数を供給する。この擬似乱数は署名作成部１０１と鍵生成部１０２に入力される。
【０１０３】
鍵生成部１０２は、暗号学的擬似乱数生成装置２００から入力される擬似乱数を基に署名鍵と検証鍵を生成し、署名鍵と検証鍵を、それぞれ、署名作成部１０と検証部１０３に送る。署名作成部１０１は、平文を入力し、この平文を擬似乱数生成装置２００から供給される擬似乱数と鍵生成部から供給される秘密鍵を用いて書名を作成する。
【０１０４】
検証部１０３は、鍵生成部１０２から受信する検証鍵を用いて署名作成部１０１から受け取る書名の検証を行う。この検証において平文と前記署名を使用する。そして、その検証結果を出力する。
【０１０５】
ヂィジタル書名系１００は、例えば、ＤＳＡ（Ｄｉｇｉｔａｌ　Ｓｉｇｎａｔｕｒｅ　Ａｌｇｏｒｉｔｈｍ）により、署名の作成と検証を行う。
（付記１）　ワード長がｗビットである計算装置であって、
自然数ｃ，ｏ，ａ（ｃ＋ｏ≦ｐ：ｐは素数で２ｐ−１も素数となる数）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在するビット列）を２個入力する入力手段と、
前記入力手段が入力したビット長ｐの第１のビット列を格納する内部状態保存手段と、
前記入力手段が入力したビット長ｐの第２のビット列を格納する生成元保存手段と、
ｐ次の｛０，１｝係数の既約多項式ｆ（ｔ）（＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０）を、そのｐビットの｛０，１｝係数ｂｐ−１ｂｐ−２・・・ｂ１ｂ０のビット列により保存する既約多項式保存手段と、
演算手段とを備え、
該演算手段により、前記生成元保存手段に格納されているｐビットの値ｇ、前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓ及び前記既約多項式保存手段に格納されているｐビットのビット列とを用いてｇｓ（ｍｏｄｆ（ｔ））を計算し、該演算手段のｐビットの演算結果を内部状態保存手段に格納すると共に、該ｐビットの演算結果の下位ｏビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【０１０６】
（付記２）　ワード長がｗビットである計算装置であって、
自然数ｃ，ｏ，ａ（ｃ＋ｏ≦ｐ：ｐは素数で２ｐ−１も素数となる数）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を３個入力する入力手段と、
前記入力手段が入力したビット長ｐの第１のビット列を格納する内部状態保存手段と、
前記入力手段が入力したビット長ｐの第２のビット列を格納する生成元保存手段と、
ｐ次の｛０，１｝係数の既約多項式ｆ（ｔ）（＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０）を、そのｐビットの｛０，１｝係数ｂｐ−１ｂｐ−２・・・ｂ１ｂ０のビット列により保存する既約多項式保存手段と、
前記入力手段が入力したビット長ｐの第３のビット列を保存するベースポイント保存手段と、
演算手段とを備え、
演算手段により、前記生成元保存手段に格納されているｐビットの値ｇ、前記ベースポイント保存手段に格納されているｐビットの値ｘ及び前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓとを用いて，ｘｇｓ（ｍｏｄｆ（ｔ））を計算し、そのｐビットの計算結果を内部状態保存手段に格納すると共に、そのｐビットの下位ｏビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【０１０７】
（付記３）　ワード長がｗビットである計算装置であって、
自然数ｃ，ｏ，ａ，ｄ（ｃ＋ｏ≦ｐ：ｐは素数で２ｐ−１も素数となる数）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を３個入力する入力手段と、
前記入力手段が入力したビット長ｐの第１のビット列を格納する内部状態保存手段と、
前記入力手段が入力したビット長ｐの第２のビット列を格納する生成元保存手段と、
ｐ次の｛０，１｝係数の既約多項式ｆ（ｔ）（＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０）を、そのｐビットの｛０，１｝係数ｂｐ−１ｂｐ−２・・・ｂ１ｂ０のビット列により保存する既約多項式保存手段と、
前記入力手段が入力したビット長ｐの第３のビット列を保存するベースポイント保存手段と、
多倍長加算手段と、
演算手段とを備え、
該演算手段により、前記生成元保存手段に格納されているｐビットの値ｇ、前記ベースポイント保存手段に格納されているｐビットの値ｘ及び前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓとを用いて，ｘｇｓ（ｍｏｄｆ（ｔ））を計算し、該ｐビットの計算結果を前記内部状態保存手段に格納すると共に、そのｐビットの計算結果の下位ｏビットを出力し、さらに、前記多倍長加算手段により前記ベースポイント保存手段に格納されているｐビットの値ｘを多倍長とみなして、その値ｘにｄを加算し、その加算結果を前記ベースポイント保存手段に格納するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【０１０８】
（付記４）　ワード長がｗビットである計算装置であって、
自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ（ｕ＋ｖ≦ｐ（ｐ：ｐは素数で２ｐ−１も素数となる数）かつ全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ，かつｃｉ≠ｏｊ）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を入力する入力手段と、
前記入力手段が入力したビット長ｐのビット列を格納する内部状態保存手段と、
該内部状態保存手段に格納されているビット長ｐのビット列に対して論理演算とシフト演算からなる演算ｆを施す演算手段を備え、
該演算手段により、前記内部状態保存手段に格納されているビット長ｐのビット列の値ｘに対して、前記演算ｆを前記内部状態保存手段に格納されているビット長ｐのビット列のｃ１，ｃ２，・・・，ｃｕビットで規定されるビット列の値ｓの数だけ施してｆｓ（ｘ）を計算し、ｐビットで表現されたその計算結果を前記内部状態保存手段に格納すると共にそのｐビットのビット列の計算結果のｏ１，ｏ２，・・・，ｏｖビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【０１０９】
（付記５）　ワード長がｗビットである計算装置であって、
自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ，ｄ（ｕ＋ｖ≦ｐ（ｐ：ｐは素数で２ｐ−１も素数となる数）かつ全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ，かつｃｉ≠ｏｊ）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を入力する入力手段と、
前記入力手段が入力したビット長ｐのビット列を格納する内部状態保存手段と、
該内部状態保存手段に格納されているビット長ｐのビット列に対して論理演算とシフト演算からなる演算ｆを施す演算手段と、
多倍長加算器を備え、
該演算手段により、前記内部状態保存手段に格納されているビット長ｐのビット列の値ｘに対して、前記演算ｆを前記内部状態保存手段に格納されているビット長ｐのビット列のｃ１，ｃ２，・・・，ｃｕビットで規定されるビット列の値ｓの数だけ繰り返してｆｓ（ｘ）を計算して、ｐビットで表現されたその計算結果を前記内部状態保存手段に格納すると共にそのｐビットのビット列の計算結果のｏ１，ｏ２，・・・，ｏｖビットを出力し、前記多倍長加算器により、前記内部状態保存手段に格納されたｐビットのビット列の値ｘ’とｄ（ｍｏｄ２ｐ−１）の加算を行い、その加算結果を前記内部状態保存手段に格納するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【０１１０】
（付記６）　ワード長がｗビットである計算装置であって、
自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ（ｕ＋ｖ≦ｐ（ｐ：ｐは素数で２ｐ−１も素数となる数）かつ全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ，かつｃｉ≠ｏｊ）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を入力する入力手段と、
前記入力手段が入力したビット長ｐのビット列を格納する内部状態保存手段と、
論理演算とシフト演算からなる演算ｆ１を施す第１の演算手段と、
論理演算とシフト演算からなる演算ｆ２を施す第２の演算手段と、
前記第１の演算手段により、前記内部状態保存手段に格納されているビット長ｐのビット列の値ｘに対して、前記演算ｆ１を前記内部状態保存手段に格納されているビット長ｐのビット列のｃ１，ｃ２，・・・，ｃｕビットで規定されるビット列の値ｓの数だけ施してｆ１ｓ（ｘ）を計算し、ｐビットで表現されたその計算結果を前記内部状態保存手段に格納すると共にそのｐビットのビット列の計算結果のｏ１，ｏ２，・・・，ｏｖビットを出力し、続いて、前記第２の演算手段により前記内部状態保存手段に格納された前記ｐビットのビット列の値ｘ’に対して前記演算ｆ２を施してｆ２（ｘ’）を計算し、そのｐビットの計算結果を内部状態保存手段に格納するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【０１１１】
（付記７）　ワード長がｗビットであるコンピュータで実行されるプログラムであって、
自然数ｃ，ｏ，ａ（ｃ＋ｏ≦ｐ：ｐは素数で２ｐ−１も素数となる数）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在するビット列）を２個入力する機能と、
前記入力したビット長ｐの第１のビット列を内部状態記憶保存手段に格納する機能と、
前記入力したビット長ｐの第２のビット列を生成元保存手段に格納する機能と、
ｐ次の｛０，１｝係数の既約多項式ｆ（ｔ）（＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０）を、そのｐビットの｛０，１｝係数ｂｐ−１ｂｐ−２・・・ｂ１ｂ０のビット列により既約多項式保存手段に保存する機能と、
前記生成元保存手段に格納されているｐビットの値ｇ、前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓ及び前記既約多項式保存手段に格納されているｐビットのビット列とを用いてｇｓ（ｍｏｄｆ（ｔ））を計算し、該演算手段のｐビットの演算結果を内部状態保存手段に格納すると共に、該ｐビットの演算結果の下位ｏビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する機能を、
前記コンピュータに実行させるプログラム。
【０１１２】
（付記８）　ワード長がｗビットであるコンピュータにより実行されるプログラムであって、
自然数ｃ，ｏ，ａ（ｃ＋ｏ≦ｐ：ｐは素数で２ｐ−１も素数となる数）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を３個入力する機能と、
前記入力したビット長ｐの第１のビット列を内部状態保存手段に格納する機能と、
前記入力したビット長ｐの第２のビット列を生成元保存手段に格納する機能と、
ｐ次の｛０，１｝係数の既約多項式ｆ（ｔ）（＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０）を、そのｐビットの｛０，１｝係数ｂｐ−１ｂｐ−２・・・ｂ１ｂ０のビット列により既約多項式保存手段に保存する機能と、
前記入力したビット長ｐの第３のビット列をベースポイント保存手段に保存する機能と、
前記生成元保存手段に格納されているｐビットの値ｇ、前記ベースポイント保存手段に格納されているｐビットの値ｘ及び前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓとを用いて，ｘｇｓ（ｍｏｄｆ（ｔ））を計算し、そのｐビットの計算結果を内部状態保存手段に格納すると共に、そのｐビットの下位ｏビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する機能を、
前記コンピュータに実行させるプログラム。
【０１１３】
（付記９）　ワード長がｗビットであるコンピュータにより実行されるプログラムであって、
自然数ｃ，ｏ，ａ，ｄ（ｃ＋ｏ≦ｐ：ｐは素数で２ｐ−１も素数となる数）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を３個入力する機能と、
前記入力したビット長ｐの第１のビット列を内部状態保存手段に保存する機能と、
前記入力したビット長ｐの第２のビット列を生成元保存手段に保存する機能と、、
ｐ次の｛０，１｝係数の既約多項式ｆ（ｔ）（＝ｔｐ＋ｂｐ−１ｔｐ−１＋ｂｐ−２ｔｐ−２＋・・・＋ｂ１ｔ＋ｂ０）を、そのｐビットの｛０，１｝係数ｂｐ−１ｂｐ−２・・・ｂ１ｂ０のビット列により既約多項式保存手段に保存する機能と、
前記入力したビット長ｐの第３のビット列をベースポイント保存手段に保存する機能と、
前記生成元保存手段に格納されているｐビットの値ｇ、前記ベースポイント保存手段に格納されているｐビットの値ｘ及び前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓとを用いて，ｘｇｓ（ｍｏｄｆ（ｔ））を計算し、該ｐビットの計算結果を前記内部状態保存手段に格納すると共に、そのｐビットの計算結果の下位ｏビットを出力し、さらに、前記多倍長加算手段により前記ベースポイント保存手段に格納されているｐビットの値ｘを多倍長とみなして、その値ｘにｄを加算し、その加算結果を前記ベースポイント保存手段に格納するという一連の処理をａ回繰り返すことにより擬似乱数を生成する機能を、
前記コンピュータに実行させるプログラム。
【０１１４】
（付記１０）　ワード長がｗビットであるコンピュータにより実行されるプログラムであって、
自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ（ｕ＋ｖ≦ｐ（ｐ：ｐは素数で２ｐ−１も素数となる数）かつ全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ，かつｃｉ≠ｏｊ）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を入力する機能と、
前記入力したビット長ｐのビット列を内部状態保存手段に格納する機能と、
前記内部状態保存手段に格納されているビット長ｐのビット列の値ｘに対して論理演算とシフト演算からなる演算ｆを前記内部状態保存手段に格納されているビット長ｐのビット列のｃ１，ｃ２，・・・，ｃｕビットで規定されるビット列の値ｓの数だけ施してｆｓ（ｘ）を計算し、ｐビットで表現されたその計算結果を前記内部状態保存手段に格納すると共にそのｐビットのビット列の計算結果のｏ１，ｏ２，・・・，ｏｖビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する機能を、
前記コンピュータに実行させるプログラム。
【０１１５】
（付記１１）　ワード長がｗビットであるコンピュータにより実行されるプログラムであって、
自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ，ｄ（ｕ＋ｖ≦ｐ（ｐ：ｐは素数で２ｐ−１も素数となる数）かつ全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ，かつｃｉ≠ｏｊ）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を入力する機能と、
前記入力手段が入力したビット長ｐのビット列を内部状態保存手段に格納する機能と、、
該内部状態保存手段に格納されているビット長ｐのビット列に対して論理演算とシフト演算からなる演算ｆを施す演算手段と、
多倍長加算器を備え、
前記内部状態保存手段に格納されているビット長ｐのビット列の値ｘに対して、論理演算とシフト演算からなる演算ｆを前記内部状態保存手段に格納されているビット長ｐのビット列のｃ１，ｃ２，・・・，ｃｕビットで規定されるビット列の値ｓの数だけ繰り返してｆｓ（ｘ）を計算して、ｐビットで表現されたその計算結果を前記内部状態保存手段に格納すると共にそのｐビットのビット列の計算結果のｏ１，ｏ２，・・・，ｏｖビットを出力し、前記多倍長加算器により、前記内部状態保存手段に格納されたｐビットのビット列の値ｘ’とｄ（ｍｏｄ２ｐ−１）の加算を行い、その加算結果を前記内部状態保存手段に格納するという一連の処理をａ回繰り返すことにより擬似乱数を生成する機能ｍを、
前記コンピュータに実行させるプログラム。
【０１１６】
（付記１２）　ワード長がｗビットであるコンピュータにより実行されるプログラムであって、
自然数ｃ１，ｃ２，・・・，ｃｕ，ｏ１，ｏ２，・・・，ｏｖ，ａ（ｕ＋ｖ≦ｐ（ｐ：ｐは素数で２ｐ−１も素数となる数）かつ全てのｉでｃｉ≦ｐ，ｏｉ≦ｐ，かつｃｉ≠ｏｊ）とビット長ｐのビット列（但し、０となるビットと１となるビットが存在する文字列）を入力する機能と、
前記入力したビット長ｐのビット列を内部状態保存手段に格納する機能と、
論理演算とシフト演算からなる演算ｆ１を施す第１の演算手段と、
論理演算とシフト演算からなる演算ｆ２を施す第２の演算手段と、
前記内部状態保存手段に格納されているビット長ｐのビット列の値ｘに対して、論理演算とシフト演算からなる第１の演算ｆ１を前記内部状態保存手段に格納されているビット長ｐのビット列のｃ１，ｃ２，・・・，ｃｕビットで規定されるビット列の値ｓの数だけ施してｆ１ｓ（ｘ）を計算し、ｐビットで表現されたその計算結果を前記内部状態保存手段に格納すると共にそのｐビットのビット列の計算結果のｏ１，ｏ２，・・・，ｏｖビットを出力し、続いて、論理演算とシフト演算からなる前記内部状態保存手段に格納された前記ｐビットのビット列の値ｘ’に対して論理演算とシフト演算からなる第２の演算ｆ２を施してｆ２（ｘ’）を計算し、そのｐビットの計算結果を内部状態保存手段に格納するという一連の処理をａ回繰り返すことにより擬似乱数を生成する機能を、
前記コンピュータに実行させるプログラム。
【０１１７】
（付記１３）ワードサイズがｗである計算装置に関し、
自然数ｃ，ｏ，ａを入力する手段（ただしｃ＋ｏ≦ｐ）と、
メルセンヌ素数（２ｐ−１）に対してｐ＝ｎｗ−ｒ（ただしｒ＜ｗ）となるように定められるｎとｒにおいて、ｐビットの文字列（ただし、０となるビットと１となるビットが存在すること）を複数入力する入力手段と、
該ｐビットの複数の入力文字列の内の一つを格納する内部状態保存手段と、
前記ｐビットの複数の入力文字列のもう一つを保存する生成元保存手段と、
ｐ次の｛０，１｝係数の既約多項式ｆ（ｔ）を保持する既約多項式保存手段と、
連続するｐビットｂｐ−１　ｂｐ−２　・・・ｂ１　ｂ０　を多項式ｂｐ−１　ｔｐ−１　＋ｂｐ−２　ｔｐ−２　＋・・・＋ｂ１　ｔ　＋ｂ０　と見なしたとき、多項式乗算器および前記既約多項式保存手段に格納された既約多項式ｆ（ｔ）で除算した剰余を演算する剰余演算器からなる演算手段と、
上記演算結果を出力する出力結果手段とを備え、
前記生成元保存手段に保存されているｐビットの値ｇと前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓとを用いて、前記演算手段によりｇｓ　（ｍｏｄ　ｆ（ｔ））を計算し、その計算結果を前記内部状態保存手段に格納すると共に前記内部状態保存手段に格納されたｐビットの上位ｏビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【０１１８】
（付記１４）付記１３の暗号学的擬似乱数生成装置であって、前記ｐビットの複数の入力文字列の別の一つを保存するベースポイント保存手段を更に備え、
前記生成元保存手段に保存されているｐビットの値ｇと前記ベースポイント保存手段に格納されている値ｘと前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓとを用いて、前記演算手段によりｘｇｓ　（ｍｏｄ　ｆ（ｔ））を計算し、その計算結果を前記内部状態保存手段に格納すると共に前記内部状態保存手段に格納されたｐビットの上位ｏビットを出力するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【０１１９】
（付記１５）付記１３の暗号学的擬似乱数生成装置であって、前記ｐビットの複数の入力文字列の別の一つを保存するベースポイント保存手段、別の自然数ｄを入力する手段および多倍長加算演算装置を更に備え、
前記生成元保存手段に保存されているｐビットの値ｇ、前記ベースポイント保存手段に格納されている値ｘ及び前記内部状態保存手段に格納されているｐビットの下位ｃビットの値ｓとを用いて、前記演算手段によりｘｇｓ　（ｍｏｄ　ｆ（ｔ））を計算し、その計算結果を前記内部状態保存手段に格納すると共に前記内部状態保存手段に格納されたｐビットの上位ｏビットを出力し、更に前記ベースポイント保存手段に格納されている値ｘ　を多倍長数値とみなしてその値ｘに前記自然数ｄを加算し、その加算結果を前記ベースポイント保存手段へ格納するという一連の処理をａ回繰り返すことにより擬似乱数を生成する暗号学的擬似乱数生成装置。
【０１２０】
【発明の効果】
以上説明したように、本発明によれば、次ビットの予測が計算量的に困難であることを数学的に保証した安全性の高い擬似乱数を、従来方式よりも高速に生成することができる。
【図面の簡単な説明】
【図１】本発明の第１実施形態の暗号学的擬似乱数生成装置のシステム構成を示すブロック図である。
【図２】第１実施形態の暗号学的擬似乱数生成装置の動作（アルゴリズム）を説明するフロチャートである。
【図３】本発明の第２実施形態の暗号学的擬似乱数生成装置のシステム構成を示すブロック図である。
【図４】第２実施形態の暗号学的擬似乱数生成装置の動作（アルゴリズム）を説明するフロチャートである。
【図５】本発明の第３実施形態の暗号学的擬似乱数生成装置のシステム構成を示すブロック図である。
【図６】第３実施形態の暗号学的擬似乱数生成装置の動作（アルゴリズム）を説明するフロチャートである。
【図７】本発明の第４実施形態の暗号学的擬似乱数生成装置のシステム構成を示すブロック図である。
【図８】第４実施形態の暗号学的擬似乱数生成装置の動作（アルゴリズム）を説明するフロチャートである。
【図９】本発明の第５実施形態の暗号学的擬似乱数生成装置のシステム構成を示すブロック図である。
【図１０】第５実施形態の暗号学的擬似乱数生成装置の動作（アルゴリズム）を説明するフロチャートである。
【図１１】本発明の第６実施形態の暗号学的擬似乱数生成装置のシステム構成を示すブロック図である。
【図１２】第６実施形態の暗号学的擬似乱数生成装置の動作（アルゴリズム）を説明するフロチャートである。
【図１３】本発明を適用したヂィジタル書名系のシステム構成を示すブロック図である。
【符号の説明】
１１，４１　　　中央処理部
１２、１２ａ，１２ｂ、４２、４２ａ　　　入力部
１３、４３　　　内部状態保存部
１４　　　　　　生成元保存部
１５　　　　　　既約多項式保存部
１６　　　　　　多項式乗算器
１７　　　　　　剰余演算器
１８、４５　　　出力部
２１　　　　　　ベースポイント保存部
４４　　　　　　演算部
４４−１　　　　第１の演算部
４４−２　　　　第２の演算部
４４ａ　　　　　論理演算器
４４ｂ　　　　　シフト演算器
４５　　　　　　出力部
５１　　　　　　多倍長加算器
１００　　　　　ディジタル署名系
１０１　　署名作成部
１０２　　鍵生成部
１０３　　　検証部
２００　　　　　擬似乱数生成装置
【図１】
2004038020.tif 000007
【図２】
2004038020.tif 000008
【図３】
2004038020.tif 000009
【図４】
2004038020.tif 000010
【図５】
2004038020.tif 000011
【図６】
2004038020.tif 000012
【図７】
2004038020.tif 000013
【図８】
2004038020.tif 000014
【図９】
2004038020.tif 000015
【図１０】
2004038020.tif 000016
【図１１】
2004038020.tif 000017
【図１２】
2004038020.tif 000018
【図１３】
2004038020.tif 000019