(57)【要約】【課題】処理が高速で安全性の高い擬似乱数発生システム【解決手段】本発明の擬似乱数発生システムは、あらかじめ用意した数列から生成した擬似乱数列のブロックを、当該擬似乱数列により選択される関数で変換して、安全な暗号乱数列を生成することを特徴とする。ここで、数列は、関数の選択及び関数のパラメータとして用いられる。  暗号化通信における共有鍵１２２を数列として用いることにより、生成した暗号乱数列３２５をストリームサイファによる文書の暗号化・復号化に用いることができる。【選択図】図３
2011128655.tif 000002
【特許請求の範囲】
【請求項１】
あらかじめ与えられた数列から暗号学的に安全な安全擬似乱数列を出力する擬似乱数発生システムであって、
あらかじめ定めたビット数のワード単位に、複数種類の関数を実行する関数実行手段と、
前記数列から擬似乱数列を生成する擬似乱数生成手段と、
前記関数実行手段の関数の種類を重複を許して選択する関数選択手段と
を備えており、
前記関数選択手段は、前記生成された擬似乱数列の前記ワードごとに前記擬似乱数列を用いて関数を選択し、
前記関数実行手段は、前記選択された関数で、前記擬似乱数列のワードを関数のパラメータとして用い、前記擬似乱数列を変換して、前記安全擬似乱数列を生成することを特徴とする擬似乱数発生システム。
【請求項２】
請求項１に記載の擬似乱数発生システムであって
前記擬似乱数生成手段は、線形次状態関数を用いて擬似乱数を生成すること
を特徴とする擬似乱数発生システム。
【請求項３】
請求項１又は２に記載の擬似乱数発生システムであって、
前記関数選択手段及び前記関数実行手段は、前記ワードごとに、あらかじめ定めた回数選択・変換を繰り返して、前記ワードを前記安全擬似乱数列に変換すること
を特徴とする擬似乱数発生システム。
【請求項４】
請求項１〜３のいずれかに記載の擬似乱数発生システムであって、
さらに、あらかじめ初期値を設定した、あらかじめ定めたビット数（ワード）の記憶手段を備えており、
前記擬似乱数生成手段は、前記数列から擬似乱数列を生成した後に、該生成した擬似乱数列をワードに切り出して最下位ビットを１にし、前記記憶手段の値と前記切り出したワードとを２のワード長乗を法として乗算した結果を前記記憶手段に格納し、繰り返し乗算した結果のビット列の一部または全体を前記擬似乱数列とすること
を特徴とする擬似乱数発生システム。
【請求項５】
請求項１〜４のいずれかに記載の擬似乱数発生システム機能をコンピュータ・システムに構築させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、共有鍵を用いたストリームサイファにおける擬似乱数発生システムである。
【背景技術】
【０００２】
第三者に見られては困る文書を電子データとして保存する時には、データは暗号化され、パスワードを知らなければ解読できないように変換される。ここで利用される暗号技術として、現在広く使用されているのは、データを固定サイズのブロックに区切り、それぞれのブロックを秘密鍵に依存した特定の関数で暗号化する、ブロックサイファと呼ばれる暗号化方式と、データの位置によって異なる関数で暗号化されるストリームサイファと呼ばれる暗号化方式である。ストリームサイファではデータと暗号乱数列の排他的論理和を求めることが多い。
また、インターネットを用いて電子商取引を行なう際にも、第三者に知られることなく、安全に２点Ａ，Ｂ間で通信を行なうために、データは暗号化して伝送されている。その時に利用される暗号技術として、現在広く利用されているのは、ＤＥＳやＴｒｉｐｌｅ  ＤＥＳ，ＡＥＳに代表される共有鍵暗号方式である。これは、通信を行なうＡ，Ｂ間でのみ共有している共有暗号鍵をもとに、送信するデータを第三者に分からないデータに変換する方法である。
【０００３】
ＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）は、これまでアメリカ合衆国政府の国立標準研究所（ＮＩＳＴ）が、データ暗号の標準として推奨してきた共有鍵暗号方式である。Ｔｒｉｐｌｅ  ＤＥＳはＤＥＳを３回繰り返すことで、その安全性を高めた暗号方式である。ＡＥＳ（Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）は、ＤＥＳに代わるデータ暗号の標準としてＮＩＳＴが公募し、数学者J.Daemen，V.Rijmenによって開発されたＲｉｊｉｎｄａｅｌと呼ばれる暗号化方式である。これらはすべて、共有鍵を利用して、固定サイズのブロックに区切られたデータを高速に暗号化する共有鍵暗号方式であり、ブロックサイファである。この変換に必要な計算量は大変小さく、実用性が高い。
ストリームサイファでは、平方剰余により擬似乱数を生成するＢｌｕｍ−Ｂｌｕｍ−Ｓｈｕｂ（ＢＢＳ）法により暗号乱数列を生成し、文書との排他的論理和を暗号文とする方法が知られている。ＢＢＳ法は、暗号鍵ｋを次々に二乗して、秘密の２つの素数の積Ｎでの剰余を作り、その最下位ビットを並べて作った列を暗号乱数列とする方針である。このNが十分大きければ、この列が暗号的に大変優れたもの、すなわち連続するいくつものデータを集めても、次のビットをランダムより良い確率で予測することが難しい、という性質をもつ擬似乱数列になっていることは、文献「L. Blum, M. Blum, M. Shub: “A Simple Unpredictable Psudo-Random Number Generator”, SIAM J. Comput. Vol15, No.2, May 1986」で示されている。よって、これを用いれば、たくさんの文字を推定しても、法則を見つけることは大変に難しく、他の部分列を推定するには、全数チェック相当の計算が必要となると考えられている。
【０００４】
しかしながら、従来の共有鍵暗号方式のブロックサイファでは、鍵情報から一つの複雑な暗号化関数を作り、これを用いて平文を変換するため、高速な暗号システムは作られる関数に偏りがあり、暗号解読のための情報を得られやすいという問題がある。たとえば暗号を解読しようとする際には、差分解読法や、線形解読法などの、既知の平文を暗号化させることによる攻撃がよく用いられている。すなわち攻撃する人物が、任意の文書を暗号化させられる状況では、解読に用いるデータを採取され、鍵の全数検索よりも簡単に暗号が破られるという問題があった。また、共有鍵暗号方式のストリームサイファでも、例えば上記のＢＢＳ法では大きな数の自乗と、その値の大きな数Nでの剰余を計算するため低速であるように、十分な安全性を持つ暗号乱数列を生成するための計算量は大きく低速になり、高速に生成できる擬似乱数は暗号的に安全でないという問題がある。
また、これまでに知られているストリームサイファ用暗号乱数列は周期が短く長く使い続けることができないという問題があった。
【０００５】
これらの問題に対処する方法として、例えば特許文献１〜特許文献５がある。特許文献１および特許文献２では、複数の暗号化関数を用意し、鍵情報や外部からのデータにより、どの暗号化関数で暗号化するかを選択することで、平文によって異なる暗号化関数で暗号化し、これにより情報の漏洩を防いだり、認証効果を得たりしている。また、特許文献３〜特許文献５では、性質の良い暗号乱数列の作り方を与えている。特に特許文献３では、平文列を有限状態オートマトンで書き換えて暗号乱数列を生成していて、本発明と関係が深い。線形フィードバックシフトレジスタ（ｌｉｎｅａｒ  ｆｅｅｄｂａｃｋ  ｓｈｉｆｔ  ｒｅｇｉｓｔｅｒ  （ＬＦＳＲ））にもとづいた擬似乱数生成装置であるが、ソフトウェア実装した場合の処理速度が充分ではないという問題がある。また、ＬＦＳＲにもとづいた擬似乱数生成装置についての従来技術としては、たとえば、文献「B. Schneier, "Applied Cryptography," John Wiley & Sons, Inc., 1996.pp. 369〜428」に開示されている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許公開平１１−１５９４０号公報
【特許文献２】特許公開平１１−２６５１４６号公報
【特許文献３】特許公開平１１−５００８４９号公報
【特許文献４】特許公開２００３−３７４８２号公報
【特許文献５】特許公開２００４−３８０２０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記の特許文献１および特許文献２の方法を用いて十分な効果を得るには、なるべく多くの暗号化関数を用意しなくてはならないが、複数の暗号化関数を保存するには、その個数倍のメモリや関数作成のための計算量が必要となるという問題がある。
また、特許文献３〜特許文献５の方法を用いて暗号乱数列を作っても、十分に長い周期を得ることはできず、速さまたは安全性に問題が生じる。
本発明の課題は、計算量を増やさずに安全性を高め、これらの問題を解決することである。
【課題を解決するための手段】
【０００８】
本発明は、あらかじめ与えられた数列から暗号学的に安全な安全擬似乱数列を出力する擬似乱数発生システムであって、あらかじめ定めたビット数のワード単位に、複数種類の関数を実行する関数実行手段と、前記数列から擬似乱数列を生成する擬似乱数生成手段と、前記関数実行手段の関数の種類を重複を許して選択する関数選択手段とを備えており、前記関数選択手段は、前記生成された擬似乱数列の前記ワードごとに前記擬似乱数列を用いて関数を選択し、前記関数実行手段は、前記選択された関数で、前記擬似乱数列のワードを関数のパラメータとして用い、前記擬似乱数列を変換して、前記安全擬似乱数列を生成することを特徴とする擬似乱数発生システムである。
前記擬似乱数発生システムにおいて、前記擬似乱数生成手段は、線形次状態関数を用いて擬似乱数を生成してもよい。
また、前記関数選択手段及び前記関数実行手段は、前記ワードごとに、あらかじめ定めた回数選択・変換を繰り返して、前記ワードを前記安全擬似乱数列に変換してもよい。
さらに、あらかじめ初期値を設定した、あらかじめ定めたビット数（ ワード） の記憶手段を備えており、前記擬似乱数生成手段は、前記数列から擬似乱数列を生成した後に、該生成した擬似乱数列をワードに切り出して最下位ビットを１にし、前記記憶手段の値と前記切り出したワードとを２のワード長乗を法として乗算した結果を前記記憶手段に格納し、繰り返し乗算した結果のビット列の一部または全体を前記擬似乱数列としてもよい。
上記のいずれかに記載の擬似乱数発生システムの機能をコンピュータ・システムに構築させるプログラムも、本発明である。
【発明の効果】
【０００９】
また、本発明の実施形態２の擬似乱数発生システムでは、鍵情報から一つの解読されにくい大きな暗号化関数を生成するのではなく、高速な異なるタイプの変換を複数個用意し、それらを鍵情報によって決まる組合せで複数回変換に用いることで暗号化する。それぞれの変換が基本的で高速なので、組み合わせた全体の変換も大変に高速である。また、関数の組み合わせ方も反復数も変えられるので、将来の仕様強化が容易である。関数属のうち、どれがどのような順番で施されたかわからないため安全性が高い。このため、従来の特許文献１および特許文献２のように複数の大掛かりな暗号化関数を用意するほどの負担をかけずに、鍵により使われる関数の種類が異なり解読の困難なシステムを実現できるようになった。
【図面の簡単な説明】
【００１０】
【図１】本実施形態の実施形態１の擬似乱数発生システムを用いて文書の暗号化及び復号化を行なう場合のシステム構成例を示す図である。
【図２】本実施形態の実施形態２，３，５の暗号化システム及び復号化システムのシステム構成例を示す図である。
【図３】本実施形態の実施形態４の擬似乱数発生システムを用いて文書の暗号化及び復号化を行なう場合のシステム構成例を示す図である。
【図４】（ａ）従来のストリームサイファの処理の流れを示す図である。（ｂ）従来のブロックサイファの処理の流れを示す図である。
【図５】実施形態１の擬似乱数発生システムの処理の流れを示す図である。
【図６】実施形態２，３の暗号化システム及び実施形態４の擬似乱数発生システムの処理の流れを示す図である。
【図７】実施形態５の暗号化システムの処理の流れを示す図である。
【発明を実施するための形態】
【００１１】
以降、本発明の擬似乱数発生システム、暗号化システム及び復号化システムの実施形態を、具体的な例を挙げて詳細に説明する。実施形態１及び４は擬似乱数発生システムを文書の暗号化・復号化に用いる場合を例とした実施形態である。また、実施形態２，３，５は暗号化システム及び復号化システムの実施形態である。
なお、以降で用いる用語を以下のように定義する。
ワード：  本実施形態では、１ワード＝３２ビットとする。
ブロック：  何ワードごとに暗号化を行なうかの単位ブロック。（例えば１ブロック＝４ワード）
【００１２】
（実施形態１）  あらかじめ用意した数列から生成した暗号的に安全でない擬似乱数列のワードと、1ワードのメモリに書かれたワードとの積を次々にとり、結果を該１ワードのメモリに格納し、その上位ビットから安全な暗号乱数列を生成することを特徴とする擬似乱数発生システム。数列に共有鍵を用いることにより、生成した暗号乱数列をストリームサイファによる文書の暗号化・復号化に用いることができる。
（実施形態２）  ブロックに分割した文書を、ブロックごとに共有鍵から生成した擬似乱数列（拡張鍵）により選択される関数で変換して暗号化文書を生成することを特徴とする暗号化システム及び復号化システムの基本的な例（ブロックサイファ）である。
（実施形態３）  ブロックに分割した文書を、ブロックごとに共有鍵から生成した擬似乱数列により選択される関数で変換して暗号化文書を生成することを特徴とする暗号化システム及び復号化システム（ストリームサイファ）である。
（実施形態４）  あらかじめ用意した数列から生成した擬似乱数列のブロックを、当該擬似乱数列により選択される関数で変換して、安全な暗号乱数列を生成することを特徴とする擬似乱数列発生システム。数列に共有鍵を用いることにより、生成した暗号乱数列をストリームサイファによる文書の暗号化・復号化に用いることができる。
（実施形態５）  実施形態３と同様の暗号化システム及び復号化システムに、後述する「ＪＵＭＰ処理」を加えることにより、より効率的な暗号化を行なう手法を提案する。なお、このＪＵＭＰ処理は実施形態２の暗号化システム及び復号化システム及び実施形態４の擬似乱数列発生システムにおいても使用することができる。
（実施形態６）  実施形態２〜５の各実施形態で用いる擬似乱数列を、実施形態１の方法で生成することにより、より複雑な暗号化を行なう手法を提案する。
以降、各実施形態を順に詳しく説明する。
【００１３】
＜１．実施形態１＞
実施形態１は、あらかじめ用意した数列（共有鍵）から生成した暗号的に安全でない擬似乱数列のワードと、1ワードのメモリに書かれたワードとの積を次々にとり、結果を該１ワードのメモリに格納し、その上位ビットから安全な暗号乱数列を生成することを特徴とする擬似乱数発生システムである。暗号化通信における共有鍵を数列として用いることにより、生成した暗号乱数列をストリームサイファによる文書の暗号化・復号化に用いることができる。
【００１４】
（１−１．従来のストリームサイファの概要と問題点）
文書のブロックｂの集合をＢＬとすると、ストリームサイファとは、暗号化側でＥ１，Ｅ２，…なる暗号化関数
Ｅｉ：  ＢＬ→ＢＬ’
の列を用意し、復号化側でＤ１，Ｄ２，…なる復号化関数
Ｄｉ：  ＢＬ’ →ＢＬ
の列を用意し、ＢＬの全てのブロックｂでＤｉ（Ｅｉ（ｂ））＝ｂとなるようにしておいて、メッセージ=ブロックの列ｂ１，ｂ２，…を暗号化してＥ１（ｂ１），Ｅ２（ｂ２），…として送信し、復号化側はそれぞれにＤ１，Ｄ２，…を施して復号化するものである。
典型的には、ＢＬの元からなる擬似乱数列ｒ１，ｒ２，…を生成して
Ｅｉ（ｂ）  ：= ｂ  ＥＸＯＲ  ｒｉ
Ｄｉ（ｂ）  ：= ｂ  ＥＸＯＲ  ｒｉ
とするものである。すなわち、送信側、受信側は擬似乱数列ｒｉの生成手段を持っていればよい。
【００１５】
上述の従来のストリームサイファの処理の流れを示したのが、図４（ａ）である。擬似乱数列ＰＮ（ｐｓｅｕｄｏｒａｎｄｏｍ  ｎｕｍｂｅｒｓ）を生成するのに、メモリ４２０（状態メモリ）を用い、それに次状態関数４６２を作用させ、メモリ４２０に書き込む。これを繰り返すことにより、メモリ４２０の内容は次々に変換される。このメモリ４２０の内容を、出力関数４６４を用いて変換し、擬似乱数列ＰＮとして用いる。
生成されたＰＮ（上述の例では列（ｒｉ）に該当）と、平文メッセージＭ（ブロックの列）に対し、暗号化関数４７０（上記の例ではＥ（ｒｉ，ｂｉ）に該当）を計算して、暗号化文Ｃ（ｃｒｙｐｔｏｇｒａｐｈｙ）を計算する。
図４（ａ）の暗号化関数４７０に示すように、関数に小さな丸がついているのは、逆関数がつくれる、すなわち計算機で容易に計算できることを示している。この小さな丸の意味は、以降の図においても同じである。ここでは、復号化関数Ｄ（ｒｉ，ｃｉ）があって、Ｄ（ｒｉ，Ｅ（ｒｉ，ｂ））＝ｂとなるということである。上述したストリームサイファの典型的な例では、ＥもＤもＥＸＯＲである。
ストリームサイファであって、Ｅ１＝Ｅ２＝…，従ってＤ１＝Ｄ２＝…となっているものをブロックサイファという。
【００１６】
図４（ａ）に示す従来のストリームサイファ（例えば、B. Schneier, "Applied Cryptography," John Wiley & Sons, Inc., 1996.pp. 369〜428）では、次状態関数４６２が複雑である（例えば、上述の従来技術ＢＢＳ（Ｂｌｕｍ−Ｂｌｕｍ−Ｓｈｕｂ）では、メモリは大きな桁数の整数を保持し、その自乗をｍｏｄｕｌｏ  Ｍで計算するのが次状態関数）か、出力関数４６４が複雑（例えば、ハッシュ関数）であるか、暗号化関数４７０が複雑である（例えば、ブロック暗号）か、のいずれかによって暗号強度を保持している。
しかしながら、次状態関数を複雑にすると、擬似乱数列ＰＮの生成速度が落ちる。また、ＰＮ周期や分布が計算できない。
次状態関数を線形にすればＰＮを高速生成でき、周期・分布も計算できる。例として、メルセンヌツイスター（ＭＴ）がある。（メルセンヌツイスターについては、http://www.math.keio.ac.jp/〜matsumoto/mt.html, M. Matsumoto and T. Nishimura, "Mersenne Twister: A 623-dimensionally equidistributed uniform pseudorandom number generator", ACM Trans. on Modeling and Computer Simulation Vol.8, No.1, January pp.3-30 (1998) を参照のこと。）この擬似乱数は高速に発生でき、周期が長い。しかし、出力関数が単純であれば、出力列から内部状態が推測されるので、暗号学的に安全であるとはいえない。
【００１７】
（１−２．本実施形態の擬似乱数発生システム）
これに対し、本実施形態の擬似乱数発生システム（ｃｒｙｐｔＭＴと呼ぶ）は、暗号学的には安全ではないかも知れない擬似乱数列ＰＮを、安全擬似乱数列ＳＰＮ（ｓｅｃｕｒｅ  ｐｓｅｕｄｏｒａｎｄｏｍ  ｎｕｍｂｅｒｓ）に変換する。
図５は、本実施形態の擬似乱数発生システムの処理の流れを示す図である。なお、図５に示されたＰＮ（安全ではないかも知れない擬似乱数列）の前には、図４（ａ）のＰＮの左側部分の処理を行なっている。なお、本実施形態において、この構成を何度も繰り返すようにしてもよい。つまり、図５のＳＰＮ生成までの処理を、図５の入力となるＰＮの位置にさらにつなげてもよい。
図５に示す本実施形態の構成において、次のような場合がスピード対安全性で最も効果がある。
・ＰＮ生成部分（図５につながる図４（ａ）のＰＮの左側部）には、高速高次元分布な線形生成法（図４（ａ）の次状態関数４６２が線形、例：上述のＭＴ）を用いる。
・ＰＮ→ＳＰＮ変換部分の次状態関数５６２は、線形ではないが高速に計算できるもの（例：３２ビット整数とみての乗算）を用いる。
・ＳＰＮ変換部分の出力関数５６４は、単純で高速なもの（例：３２ビットから、上位８ビットのみをとり、残りは捨てる）を用いる。
これらの効果のある方法を用いたのが、本実施形態のｃｒｙｐｔＭＴである。ただし、乗算を用いており、偶数の積はｍｏｄｕｌｏ  ２｛３２｝で可逆でないため、ＭＴの出力の最下位ビットを強制的に１にする必要がある。
【００１８】
以降、図４（ａ）及び図５を参照しながら、本実施形態の擬似乱数発生システムを用いて、ストリームサイファにより文書（平文）の暗号化及び復号化を行なう場合の処理を説明する。なお、ここでは上述したように図４（ａ）の次状態関数４６２にメルセンヌツイスターを使用する例で説明する。
（１）共有鍵（図４（ａ）の鍵４３０）を初期シード配列として、非線形初期化法（ｉｎｉｔ＿ｂｙ＿ａｒｒａｙ）により６２４ワードのデータを生成し、メルセンヌツイスター（以後ＭＴ）ｍｔ１９９３７ａｒ．ｃを初期化する。これは、図４（ａ）の鍵変換４３２の処理に該当し、これによりＭＴ（次状態関数４６２）の状態メモリ（メモリ４２０）を初期化する。出力関数４６４は、単にメモリ４２０の最初のワードを出力する。
（２）初期化後のＭＴの出力ワード列をＭ（０），Ｍ（１），Ｍ（２），…とする。これが図４（ａ）に示す擬似乱数列ＰＮ（安全ではないかも知れない擬似乱数列）であり、図５に送られる（図５の左上のＰＮに該当）。なお、上述したようにＭ（ｎ）はＭＴの出力の最下位ビットを強制的に１にしたものである。
（３）１ワード＝３２ビットのメモリ（変数）ａｃｃｕｍを用意する。これが図５のメモリ５２０に該当する。
（４）ａｃｃｕｍに初期値（例えば１）を代入する。なお、初期値は他の値（ただし、ゼロ以外）でもよい。
（５）以後、代入
ａｃｃｕｍ←ａｃｃｕｍ×Ｍ（ｎ）  （ｍｏｄ２｛３２｝）
を繰り返す（次状態関数５６２）。ここで、最初の６４回は空回しし、６５回目からあらかじめ定めた回数までａｃｃｕｍの上位８ビットを次々に出力する（出力関数５６４）。これにより、暗号学的に安全な８ビット整数擬似乱数列（ＳＰＮ）を出力することができる。
なお、上述の演算の繰返し回数は例であり、システムに応じて必要な回数とすればよい。また、上述のａｃｃｕｍの上位８ビットの代わりに、ａｃｃｕｍのビット列の全部又は一部（例えば１ビットおきに出力するなど）を、安全擬似乱数列として次々に出力するようにしてもよい。
（６）出力された安全なＳＰＮと、文書（平文Ｍ）とのＥＸＯＲをとることにより（暗号化関数５７０に該当）、暗号文Ｃを出力する。
【００１９】
また、上記（２）〜（５）の処理を、次のようにしてもよい。メルセンヌツイスターにより生成した擬似乱数のｎワード目のデータの最下位ビットを１にしたデータをＭ（ｎ）とし、３２ビットのメモリａｃｃｕｍに、共有鍵データからハッシュ関数を用いた数列をつくってａｃｃｕｍの初期値とする。ここで、この数列の最下位ビットを強制的に１にしてもよい。次に、ｎ＝１，２，３，…について、
ａｃｃｕｍ←ａｃｃｕｍ×Ｍ（ｎ）  （ｍｏｄ２｛３２｝）
を計算し、ａｃｃｕｍの上位８ビットを出力して、暗号学的に安全な８ビット整数擬似乱数として出力する。
【００２０】
（１−３．効果）
本実施形態では擬似乱数として、メルセンヌツイスター（ｍｔ１９９３７ａｒ．ｃ）を用いたことで、出力される暗号乱数列は周期が２１９９３７−１であることが数学的に証明できる。この周期は従来知られているどの暗号乱数列よりも長く、安心して長期間利用することができる。
また、ａｃｃｕｍに非線形な演算（乗算）を行うことと、線形性の残る最下位ビットを使わないことで、暗号乱数列として十分な安全性を持つ。
また、メルセンヌツイスターのように、暗号的に安全でないが高速な擬似乱数を、３２ビットの積という比較的速い関数で変換したことにより、このアルゴリズムを用いて生成する暗号乱数生成法は、現在アメリカのスタンダード暗号乱数生成法であるＡＥＳの最速オプティマイズ版の１．５倍以上と、非常に高速である。
また、ＭＴの内部空間の大きさにより、ｔｉｍｅ−ｍｅｍｏｒｙ−ｔｒａｄｅ−ｏｆｆ攻撃に対しても耐性が強い。
【００２１】
（１−４．本実施例を用いた暗号化システム及び復号化システムの構成例）
最後に、本実施形態の擬似乱数発生システムを用いて、ストリームサイファにより文書（平文）の暗号化及び復号化を行なう場合のシステム構成を、図１のシステム構成図を参照しながら説明する。
本実施形態のシステムは、例えば通常のパソコン等の端末に実装するものする。図１に示すように、文書を暗号化して送信する側の端末には暗号化システム１１０を、文書を受信して復号化する側の端末には復号化システム１５０を実装する。また、暗号化システム１１０及び復号化システム１５０の双方に、数列（共有鍵１２２）及び本実施形態の擬似乱数発生システム１３０を用意する。
暗号化システム１１０において、擬似乱数発生システム１３０の擬似乱数生成プログラム１３２により、共有鍵１２２から上述で説明した本実施形態の手法を用いて安全な擬似乱数列（安全擬似乱数列）１２５を生成する。次に、ストリームサイファの典型的な例として、暗号化プログラム１３６は、安全な擬似乱数列１２５と文書１２４のＥＸＯＲをとることにより文書１２４を暗号化して、暗号化文書１４０を生成する。
【００２２】
一方、復号化システム１５０においては、擬似乱数発生システム１３０の擬似乱数生成プログラム１３２により、共有鍵１２２から上述で説明した本実施形態の手法を用いて安全な擬似乱数列１２５を生成する。次に、復号化プログラム１６６は、安全な擬似乱数列１２５と復号化文書１２４のＥＸＯＲをとることにより暗号化文書１４０を復号し、元の文書１２４を得る。暗号化システム１１０と復号化システム１５０とでは、同じ共有鍵１２２から同じ擬似乱数生成プログラム１３２を用いて、同じ安全な擬似乱数列１２５を生成するため、対応する暗号化・復号化の処理を行なうことができる。
【００２３】
＜２．実施形態２＞
実施形態２は、ブロックに分割した文書を、ブロックごとに共有鍵から生成した擬似乱数列により選択される関数で変換して暗号化文書を生成することを特徴とする暗号化システム及び復号化システムの基本的な例であり、ブロックサイファである。関数の選択及び関数のパラメータには、共有鍵から生成した擬似乱数列が用いられる。ここで、後述の実施形態３では、文書が長いほど擬似乱数列を消費するが、本実施形態２は、一定の長さしか消費しない。このため、本実施例では、共有鍵から生成した一定の長さの擬似乱数列を「拡張鍵」とよぶ。
【００２４】
（２−１．従来のブロックサイファの概要と問題点）
ＡＥＳなどの従来のブロックサイファは、図４（ｂ）に示す構成である。すなわち、平文Ｍのブロックをメモリ４２０に取り込み、擬似乱数列ＰＮを使って変換（４６６に示すＥＸＯＲ）を行ない、メモリ４２０に書き込む。これを数回繰り返して暗号文Ｃを得る。ここで、右下の関数４６０は複雑な全単射である。なお、上述の図４（ａ）で説明したとおり、関数に小さな丸がついているのは、逆関数がつくれる、すなわち計算機で容易に計算できることを示している。
しかしながら、上述したように、従来のブロックサイファは、鍵情報から一つの複雑な暗号化関数を作り、これを用いて平文を変換するため、高速な暗号システムでは作られる関数に偏りがあり、暗号解読のための情報を得られやすいという問題がある。たとえば暗号を解読しようとする際には、差分解読法や、線形解読法などの、既知の平文を暗号化させることによる攻撃がよく用いられている。すなわち攻撃する人物が、任意の文書を暗号化させられる状況では、解読に用いるデータを採取され、鍵の全数検索よりも簡単に暗号が破られてしまう。
【００２５】
（２−２．処理の流れ）
これに対し、本実施形態では、次のような構成をとることにより、従来の問題点を解決する。
図６は、本実施形態の暗号化システムの処理の流れを示す図である。なお、後述の実施形態３の暗号化システムの処理も同図に示す通りである。
本実施形態（及び実施形態３）では、ブロックｂの集合ＢＬについて、
Ｆ：  ＰＡＲＡＭ×ＢＬ→ＢＬ
の形をした単純な関数と、逆操作に当たる
Ｆ’：  ＰＡＲＡＭ×ＢＬ→ＢＬ
の関数を複数個用意し（Ｆ’（Ｐ，Ｆ（Ｐ，ｂ））＝ｂとなるものである）、図６に示すように、擬似乱数列ＰＮ（図６の左上に示すＰＮ）をパラメータＰとして消費しながら、平文Ｍのブロックが取り込まれたメモリ６２０の内容を繰り返し変換して、暗号文Ｃを得る。変換の際、どの関数６６０（上記のＦに該当）を使うかは、ＰＮをセレクタ６４０に送って選択する。
【００２６】
上記の構成をとることにより、本実施形態（及び実施形態３）では関数の組み合わせの自由度が指数的に増大し、強固な暗号が実現できる。
また、擬似乱数列ＰＮからパラメータ（図６における関数６６０で、白丸のついていないところ）を取り込むため柔軟性があり、より強固な暗号が実現できる。
さらに、共有鍵を図４（ａ）に示す鍵４３０として、上述のメルセンヌツイスターなどを用いて擬似乱数列ＰＮを生成すれば、ＰＮはいくらでも生成することができる。そのため、関数６６０による平文の変換の繰り返し回数を増やすことができ、暗号化の強度を上げることができる。
また、図６において、平文が複数のブロックからなる場合には、各ブロックに対して異なる組み合わせの関数による暗号化を行なうことができる（つまり、ストリームサイファとして使える）。
【００２７】
（２−３．前提条件）
本実施形態では、１ブロック＝４ワード（８ワードまたは１６ワードでもよい）、１２８ビット以上の共有秘密鍵情報での暗号化方式を例に挙げて説明する。
前処理として、共有鍵を必要なサイズにハッシュ関数で拡張して擬似乱数列ＰＮ、すなわち拡張鍵（図６の左上のＰＮに該当）を生成する。本実施例では、文書はブロックサイズ（４ワード）に分割し、ブロックごとに変換するものとする。
【００２８】
（２−４．用意する関数）
ブロックの変換には以下の７種類の、ブロックサイズのデータを高速で変換することができる、性質の全く異なる関数（図６の関数６６０に該当）を用いる。以降、これらの関数族をＰＥＦ（ｐｒｉｍｉｔｉｖｅ  ｅｎｃｒｙｐｔｉｏｎ  ｆａｍｉｌｙ）とよぶ。本実施形態では、ワード内の計算を行なう関数（ワード内関数）４種類と、ブロック内の複数のワードを跨ぐ計算を行なう関数（ワード間関数）３種類を用意する。なお、復号化において、ワード内関数に対応する逆関数をワード内逆関数、ワード間関数に対応する逆関数をワード間逆関数という。
ｔ回目の演算（変換）には拡張鍵（擬似乱数列ＰＮ）のｔブロック目のデータを用いる。また、拡張鍵の最後の１ブロックは関数の選択に用いる。
【００２９】
（ａ）ワード内の計算（４種類）
（１）ＥＸＯＲ：  ブロックの各ワードに、拡張鍵のｔブロック目のデータをワードごとに排他的論理和で加える。
（２）＋：  ブロックの各ワードに、拡張鍵のｔブロック目のデータをワードごとにｍｏｄ２３２で加える。
（３）×：  ブロックの各ワードに、拡張鍵のｔブロック目の、対応するそれぞれのワードの最下位ビットを１に変えたものをｍｏｄ２３２で掛け算する。なお、この変換については、最下位ビットを１に変えた拡張鍵のワードの掛け算の逆関数をすべて計算して辞書引きできるよう保存しておく。
（４）横シフト：  ブロックの各ワードについて、拡張鍵のｔブロック目の対応するそれぞれのワードの下５ビットずつを数字として用いて、その大きさの分だけのビットを右にシフトする。ワードの右にはみ出た部分をビット反転させて、左に書く。
【００３０】
（ｂ）ワードを跨ぐ計算（３種類）
（５）縦回転：  1ブロックをワードの４個（１ブロック＝４ワードの場合。なお、１ブロック＝８ワードとする場合は８個、１ブロック＝１６ワードとする場合は１６個）の配列とみなし、４行３２列（１ブロック＝８ワードとする場合は８行３２列、１ブロック＝１６ワードとする場合は１６行３２列）の０，１からなる行列とみなす。拡張鍵のｔブロック目から１ワード取り出す。この１ワードでビットが１のところに対応する列をビット反転させて、さらに下方向に１行分シフトする。一番下の行のデータは一番上に書く（ローテート）。
（６）置換：  拡張鍵のｔブロック目から２ビット（１ブロック＝４ワードの場合。なお、１ブロック＝８ワードとする場合は３ビット、１ブロック＝１６ワードとする場合は４ビット）を４回取り出し、それぞれを数として見た値ｋについて配列されたブロックのｋ行目と（（ｋ＋５）ｍｏｄ４）行目（１ブロック＝４ワードの場合。なお、１ブロック＝８ワードとする場合は（（ｋ＋５）ｍｏｄ８）行目，１ブロック＝１６ワードとする場合は（（ｋ＋５）ｍｏｄ１６）行目）を入れ換えることを、４回行う。
（７）和置換：  拡張鍵のｔブロック目から２ビット（１ブロック＝４ワードの場合。なお、１ブロック＝８ワードとする場合は３ビット、１ブロック＝１６ワードとする場合は４ビット）を４回取り出し、それぞれを数として見た値ｋについて配列されたブロックのｋ行目に（（ｋ＋７）ｍｏｄ４）行目（１ブロック＝４ワードの場合。なお、１ブロック＝８ワードとする場合は（（ｋ＋７）ｍｏｄ８）行目，１ブロック＝１６ワードとする場合は（（ｋ＋７）ｍｏｄ１６）行目）を排他的論理和で加えることを４回行う。
【００３１】
（２−５．文書の暗号化）
文書の暗号化は、文書をブロックサイズに区切り、それぞれのブロックに上述の関数を以下のように拡張鍵（擬似乱数列ＰＮ）に依存して選択して変換する。上述したように、ｔ回目の演算（変換）には拡張鍵のｔブロック目のデータを関数（図６の関数６６０）のパラメータとして用いる。また、拡張鍵の最後の１ブロックは関数の選択に用いる。図６で説明すると、ＰＮの最後の１ブロックをセレクタ６４０に送り、セレクタ６４０により関数６６０を選択する。
本実施形態では、文書の各ブロック（図６ではメモリ６２０に取り込まれた平文Ｍのブロック）に対し、上述した７種類の関数を、例えば「横シフト・×・縦回転・（置換または和置換）・（＋またはＥＸＯＲ）」の順に施すことを１セットとし、これを８セット行なうことによりブロックを変換する。ただし、後ろ２つのそれぞれ２種類の関数を（）内に示している箇所においては、拡張鍵の最終ブロックから１ビットずつを２×８回次々に用いて、０なら前者を、１なら後者を選択するものとする。この場合、ｔ＝４０回の演算（変換）を行なうことになるため、拡張鍵は４１ブロックのサイズに生成し、最後の４１ブロック目を関数の選択に用いる。
なお、上記（１）〜（７）の関数は一例であり、高速に処理できる他の演算を用意してもよい。また、上記の関数の組み合わせや順序は一例であり、他の組み合わせや順序でもよい。また、繰り返し回数も上記の８セット以外の回数でもよい。また、最初の１セットと最後の１セットで全種類の変換を行ない、間のセットで全種類の関数の中から拡張鍵を用いてどれかを選択することを例えば５回以上繰り返すなどの方法を用いてもよい。１セットを複数回行なう理由は、本実施形態では全てのブロックに対して同じ変換を施すため、安全性を高める必要があるからである。
【００３２】
（２−６．文書の復号化）
復号化は、暗号化の逆の順番で、それぞれの変換の逆写像を施せばよく、本実施形態では暗号化と同じくらいの時間で計算できる。
【００３３】
（２−７．効果）
本実施形態の暗号化システム及び復号化システムによれば、それぞれの変換が高速であることから大量の文書を高速に暗号化でき、施された関数のタイプとその順番がわからないことから、従来のブロックサイファよりも解読が困難となる。
【００３４】
（２−８．本実施例を用いた暗号化システム及び復号化システムの構成例）
最後に、本実施形態の暗号化システム及び復号化システムを用いて、文書の暗号通信を行なう場合のシステム構成例を、図２を参照しながら説明する。なお、後述の実施形態３，実施形態５も同様のシステム構成とすることができる。
本実施形態の暗号化システム及び復号化システムは例えば通常のパソコン等の端末に実装するものとする。図２に示すように、文書を暗号化して送信する側の端末には暗号化システム１１０を、文書を受信して復号化する側の端末には復号化システム１５０を実装する。また、暗号化システム１１０には共有鍵１２２及び暗号化に用いる複数の関数１２６を用意し、復号化システム１５０には共有鍵１２２及び復号化に用いる複数の逆関数１２８（関数１２６の各関数に対応し、それぞれ逆の操作をする関数）を用意する。
【００３５】
上述したように、本実施形態の暗号化システム及び復号化システムは、共有鍵の情報（共有鍵から生成した擬似乱数列）を暗号化関数の選択及び選択された関数のパラメータとして用いていることが主要な特徴であり、これにより高速で安全性の高いシステムを実現している。暗号化システム１１０では、まず、擬似乱数生成プログラム２３２により、共有鍵１２２から擬似乱数列２２５（本実施形態においては拡張鍵）を生成する。次に、生成された擬似乱数列（拡張鍵）２２５を用いて、関数選択プログラム２３４は関数１２６から文書１２４の暗号化に用いる関数を選択する。また、暗号化プログラム２３６は、擬似乱数列（拡張鍵）２２５を関数選択プログラム２３４で選択された関数のパラメータとして用いて関数を実行して文書１２４を暗号化する。これにより暗号化文書１４０を生成する。
一方、復号化システム１５０では、まず、擬似乱数生成プログラム２３２により、共有鍵１２２から送信端末１１０と同じ擬似乱数列（拡張鍵）２２５を生成する。次に、生成された擬似乱数列（拡張鍵）２２５を用いて、逆関数選択プログラム２６４は逆関数１２８から受信した暗号化文書１４０の復号に用いる逆関数を選択する。ここでは、送信端末１１０で選択された関数に対応する逆関数が選択されることになる。復号化プログラム２６６は、擬似乱数列（拡張鍵）２２５を逆関数選択プログラム２６４で選択された逆関数のパラメータとして用いて逆関数を実行し、暗号化文書１４０を復号する。これにより元の文書１２４を得る。
【００３６】
＜３．実施形態３＞
実施形態３は、ブロックに分割した文書を、ブロックごとに共有鍵から生成した擬似乱数列により選択される関数で変換して暗号化文書を生成することを特徴とする暗号化システム及び復号化システムの例であり、ストリームサイファである。共有鍵の情報（共有鍵から生成した擬似乱数列）は、関数の選択及び関数のパラメータに用いられる。
本実施形態のシステム構成例は上述の実施形態２で図２を用いて説明した通りである。また、その処理の流れは実施形態２で図６を用いて説明した通りである。本実施形態と、上述の実施形態２との違いは、実施形態２（ブロックサイファ）では、一度複数の関数を選択してパラメータを決定したら、同じ関数及びパラメータですべてのブロックを変換するが、本実施形態（ストリームサイファ）では、文書のブロックごとに、関数とパラメータを決めて変換する。すなわち、全く同じブロックが２つあったときに、実施形態２ではこの２つのブロックは同じ暗号文に変換されるが、実施形態３では選択される関数もパラメータも違うため違う暗号文になる。また、上述したように、実施形態２は、一定の長さの擬似乱数列（拡張鍵）しか使わないが、実施形態３の方は、文書の長さに応じて擬似乱数を消費することになる。
【００３７】
（３−１．前処理）
共有鍵に基づき擬似乱数を発生させて、３２種類の乗算値（３２ビット符号なしの整定数で、どれも奇数なもの）を準備する。そして、それらのｍｏｄ２３２での乗法逆数値を計算して表にしておく。
【００３８】
（３−２．ユーザが決めるマクロ定数）
（１）１ブロックのワード数（Ｔｕｐｌｅ）を定義する。
＃ｄｅｆｉｎｅ  Ｌｏｇ＿Ｔｕｐｌｅ  ２
＃ｄｅｆｉｎｅ  Ｔｕｐｌｅ  （１ＵＬ＜＜Ｌｏｇ＿Ｔｕｐｌｅ）
本実施形態においては、１ブロックはＴｕｐｌｅ個のワードとする。
Ｔｕｐｌｅの値は２巾であり、４以上１６以下である必要がある。
Ｔｕｐｌｅの２を底としたログを、Ｌｏｇ＿Ｔｕｐｌｅとして指定する。
上記は、１ブロック＝４ワードとする場合の記述である。
（２）文書のブロックの暗号化関数による変換回数（Ｉｔｅｒａｔｉｏｎ）を定義する。
＃ｄｅｆｉｎｅ  Ｉｔｅｒａｔｉｏｎ  １０
上記は、変換回数を１０回とする場合の記述である。
【００３９】
（３−３．グローバル変数）
暗号化したい文書（平文）を入れておく配列は二重配列
ｍｓｇ［Ｍｓｇ＿Ｌｅｎｇｔｈ］［Ｔｕｐｌｅ］
である。本実施形態で用いるグローバル変数は次の通りである。
（１）暗号化したい文書（平文）を格納する。
ｕｎｓｉｇｎｅｄ ｌｏｎｇ ｍｓｇ［Ｍｓｇ＿Ｌｅｎｇｔｈ］［Ｔｕｐｌｅ］；
（２）配列ｍｓｇを直接書き換えて暗号化する。
ｈｍｎｅｎｃｏｄｅ（ｋｅｙ［］，ｉｎｉｔ＿ｖａｌｕｅ［］）
（３）配列ｍｓｇを直接書き換えて復号化する。
ｈｍｎｄｅｃｏｄｅ（ｋｅｙ［］，ｉｎｉｔ＿ｖａｌｕｅ［］）
【００４０】
（３−４．用意する関数）
Ｔｕｐｌｅ個のワードからなるブロックの変換に用いる関数（ＰＥＦ）（図６の関数６６０に該当）として、本実施形態では、あらかじめ、ワード内の計算を行なう関数５種類と、ブロック内の複数のワードを跨ぐ計算を行なう関数３種類の計８種類の関数を用意する。
これらの関数は全て、
ＰＥＦ：  ＢＬ×ＰＡＲＡＭ→ＢＬ
なる写像である。ここで、ＢＬは文書のブロックの集合であり、ＰＡＲＡＭは関数に与えるパラメータであり、ＰＡＲＡＭはＢＬと同じくＴｕｐｌｅ個のワードからなるデータの集合であり、擬似乱数列ＰＮから得る。
ここでは、Ｔｕｐｌｅ＝４の場合を例として
（ｗ１， ｗ２， ｗ３， ｗ４）←ＰＥＦ（ｗ１，ｗ２，ｗ３，ｗ４； ｐ１， ｐ２， ｐ３， ｐ４）
の形で記述することにする。
以降、ＰＥＦの８種類の関数とその逆関数（＿ｉｎｖ）をそれぞれ説明する。なお、これらの（１）〜（８）の関数は一例であり、高速に処理できる他の演算を用意してもよい。
【００４１】
（ａ）ワード内の計算（ワード内関数及びそれに対応するワード内逆関数）５種類 
（１）ｃｒｙｐｔ＿ｐｌｕｓ
ｃｒｙｐｔ＿ｐｌｕｓ
ｗｉ←ｗｉ＋ｐｉ  (ｉ＝１，２，３，４)．
ｃｒｙｐｔ＿ｐｌｕｓ＿ｉｎｖ
ｗｉ←ｗｉ−ｐｉ  (ｉ＝１，２，３，４)．
【００４２】
（２）ｃｒｙｐｔ＿ｅｘｏｒ
ｃｒｙｐｔ＿ｅｘｏｒ
ｗｉ←ｗｉ  ＥＯＲ  ｐｉ  (ｉ＝１，２，３，４)．
ｃｒｙｐｔ＿ｅｘｏｒ＿ｉｎｖ
ｗｉ←ｗｉ  ＥＯＲ  ｐｉ  (ｉ＝１，２，３，４)．
【００４３】
（３）ｃｒｙｐｔ＿ｍｕｌｔｉ
最近のＣＰＵは掛け算命令を持っているが、割り算は遅い。そのため、本実施形態では上述の（３−１．前処理）で述べたようにＭｕｌｔｉ＿Ｓｉｚｅ個（＝３２個）の掛け算用乱数定数を用意し、ｇｌｏｂａｌ変数の配列ｍｕｌｔｉ＿ｔａｂｌｅに格納する。
実際の処理としては、
１）ｐｒｅｐａｒｅ＿ｍｕｌｔｉ（）を呼び出すと、ｍｕｌｔｉ＿ｔａｂｌｅに乱数が格納される。
２）下位ビットを強制的に変換し、ｍｏｄ７で３のものと、ｍｏｄ１６で７のものをｍｕｌｔｉ＿ｔａｂｌｅ内に交互におく。これらは、ｍｏｄ２３２での乗法群を生成する。
３）ｐｒｅｐａｒｅ＿ｍｕｌｔｉ＿ｉｎｖ（）を呼び出すと、ｉｎｖ＿ｔａｂｌｅにｍｕｌｔｉ＿ｔａｂｌｅの乗法逆数が格納される。
ｃｒｙｐｔ＿ｍｕｌｔｉ
ｗｉ←ｗｉ×ｍｕｔｌｉ＿ｔａｂｌｅ［ｐｉの上位５ビット］
ｗｉ←ｗｉ−ｐｉ
をｉ＝１，２，３，４について行う。すなわち、パラメータｐｉの上位５ビットに対応する乗算用定数をｍｕｔｌｉ＿ｔａｂｌｅ［］から読み出し、それをｗｉに掛ける。ｐｉの下位２７ビットが捨てられるのはもったいないので、ｗｉからｐｉを引いておく。
ｃｒｙｐｔ＿ｍｕｌｔｉ＿ｉｎｖ
ｗｉ←ｗｉ＋ｐｉ
ｗｉ←ｗｉ×ｉｎｖ＿ｔａｂｌｅ［ｐｉの上位５ビット］
をｉ＝１，２，３，４について行う。
【００４４】
（４）ｃｒｙｐｔ＿ｈｏｒｉ＿ｒｏｔａｔｅ
ｃｒｙｐｔ＿ｈｏｒｉ＿ｒｏｔａｔｅ
ワードごとに、ビットを反転しながら横ローテートを行う。すなわち
ｓｉ←ｐｉの上位５ビット、ただし下から４ビット目は常に１にセット
ｗｉ←（ｗｉのビット反転の右３２−ｓｉシフト）と（ｗｉの左ｓｉシフト）のＯＲ
ｗｉ←ｗｉ−ｐｉ
をｉ＝１，２，３，４で行う。４ビット目を１にするのは、パラメータが０でもローテートをするため。
ｃｒｙｐｔ＿ｈｏｒｉ＿ｒｏｔａｔｅ＿ｉｎｖ
上述の逆変換
【００４５】
（５）ｃｒｙｐｔ＿ｈｏｒｉ＿ｒｉｇｈｔｓｈｉｆｔ
ｃｒｙｐｔ＿ｈｏｒｉ＿ｒｉｇｈｔｓｈｉｆｔ
ワードごとに、ビットを反転しながら横ローテートを行う。すなわち
ｓｉ←ｐｉの上位５ビット、ただし下から５ビット目は常に１にセット
ｗｉ←ｗｉ  ＥＯＲ  （ｗｉのビット反転の右ｓｉシフト）
ｗｉ←ｗｉ＋ｐｉ
をｉ＝１，２，３，４で行う。５ビット目を１にするのは、パラメータが０でもローテートをするためと、逆変換を易しくするため。
ｃｒｙｐｔ＿ｈｏｒｉ＿ｒｉｇｈｔｓｈｉｆｔ＿ｉｎｖ
上記の逆変換
【００４６】
（ｂ）ワードを跨ぐ計算（ワード間関数及びそれに対応するワード間逆関数）３種類
（６）ｃｒｙｐｔ＿ｖｅｒｔ＿ｒｏｔａｔｅ
ｃｒｙｐｔ＿ｖｅｒｔ＿ｒｏｔａｔｅ
ｋｅｙ←ｐ１＋ｐ４
ｋｅｙを３２ビットランダムパターンと思う。
ｗ１，ｗ２，ｗ３，ｗ４に関して、ｋｅｙにおいて１になっているビットについては縦方向にビット反転しながらローテートする。乱数がもったいないので
ｗｉ←ｗｉ＋ｐｉ
をｉ＝１，２，３，４について行う。
ｃｒｙｐｔ＿ｖｅｒｔ＿ｒｏｔａｔｅ＿ｉｎｖ
上記の逆変換
【００４７】
（７）ｃｒｙｐｔ＿ａｄｄ＿ｐｅｒｍｕｔｅ
ｃｒｙｐｔ＿ａｄｄ＿ｐｅｒｍｕｔｅ
ｉ＝１，２，３，４について、
ｗｉ←ｗｉ＋ｗｊ
という和を行う。ここでｊはｐｉの最下位Ｌｏｗ＿Ｍａｓｋ＝２ビットを用いて決められるが、たまたまそれがｉと同じであるときにはｊをｍｏｄ  Ｌｏｗ＿Ｍａｓｋでｉｎｃｒｅｍｅｎｔしておく。
ｐ１−ｐ４の有効活用のために
ｗｉ←ｗｉ  ＥＯＲ  ｐｉ
をｉ＝１，２，３，４でやっておく。
ｃｒｙｐｔ＿ａｄｄ＿ｐｅｒｍｕｔｅ＿ｉｎｖ
上記の逆変換
【００４８】
（８）ｃｒｙｐｔ＿ｅｘｏｒ＿ｐｅｒｍｕｔｅ
ｃｒｙｐｔ＿ｅｘｏｒ＿ｐｅｒｍｕｔｅ
ｉ＝１，２，３，４について、
ｗｉ←ｗｉ  ＥＸＯＲ  ｗｊ
という和を行う。ここでｊはｐｉの最下位Ｌｏｗ＿Ｍａｓｋ＝２ビットを用いて決められるが、たまたまそれがｉと同じであるときにはｊをｍｏｄ  Ｌｏｗ＿Ｍａｓｋでｉｎｃｒｅｍｅｎｔしておく。
ｐ１−ｐ４の有効活用のために
ｗｉ←ｗｉ−ｐｉ
をｉ＝１，２，３，４でやっておく。
ｃｒｙｐｔ＿ｅｘｏｒ＿ｐｅｒｍｕｔｅ＿ｉｎｖ
上記の逆変換
【００４９】
（３−５．擬似乱数列）
ここでは擬似乱数列ＰＮ（図６の左上のＰＮに該当）の生成方法として、上述のメルセンヌツイスター（ｍｔ１９９３７ａｒ．ｃ）を用いる。ｍｔ１９９３７ａｒ．ｃは、任意長の配列を初期値として受け取る機能を持つ。
擬似乱数列は４ワードずつ読み込むようにした。内部配列長の６２４が４でわりきれるため、６２４／４回読み込むごとに配列全体に擬似乱数列を生成しなおす。
ｇｅｎｒａｎｄ＿ｆｏｕｒｉｎｔ３２（ｐａｒａｍ）
により、ｐａｒａｍ［０］〜ｐａｒａｍ［３］に３２ビット長符号なし整数乱数が読み込まれる。
暗号化する際の
ｃｒｙｐｔ＿．．．（ｕｎｓｉｇｎｅｄ  ｌｏｎｇ  ｂｌｏｃｋ［Ｔｕｐｌｅ］）
では、どれも内部でｇｅｎｒａｎｄ＿ｆｏｕｒｉｎｔ３２（ｐａｒａｍ）を呼び出してｐ１，ｐ２，ｐ３，ｐ４を生成している。それに対し、復号化する際の
ｃｒｙｐｔ＿．．．＿ｉｎｖ（ｂｌｏｃｋ［］，ｐａｒａｍ［］）
では、ｐａｒａｍのところにｐ１〜ｐ４を指定する。この違いは、復号化する場合には擬似乱数列を逆向きに生成しなくてはならないことに起因する。復号化する場合には、擬似乱数列を配列ｔｅｍｐ＿ｒａｎｄにいったん記録しておき、逆向きに使う。
【００５０】
（３−６．文書の暗号化）
ｈｍｎｅｎｃｏｄｅ（ｋｅｙ［］，ｉｎｉｔ＿ｖａｌｕｅ［］）
を呼び出すと、文書（図６においては、メモリ６２０に取り込んだ平文Ｍのブロック）の暗号化を行なう。ｋｅｙ，ｉｎｉｔ＿ｖａｌｕｅは配列で、あわせてメルセンヌツイスターの初期化に使われる。
（１）ｍｕｌｔｉ＿ｔａｂｌｅに乗算定数をしまう。
（２）擬似乱数列ＰＮを４ワードｆｕｎｃ＿ｃｈｏｉｃｅ［０］−［３］の４つに格納し、積とＥＯＲを用いて新たな４ワードに書き換える。（あとでこの４ワードを３ビットずつに切り出し、上述の５＋３種のＰＥＦの選択を行う。）
（３）まずは平文に対して次の３つを施す。
ｃｒｙｐｔ＿ｍｕｌｔｉ（ｍｓｇ［ｉ］）；
ｃｒｙｐｔ＿ｖｅｒｔ＿ｒｏｔａｔｅ（ｍｓｇ［ｉ］）；
ｃｒｙｐｔ＿ｈｏｒｉ＿ｒｉｇｈｔｓｈｉｆｔ（ｍｓｇ［ｉ］）；
（４）その後はＩｔｅｒａｔｅ回、ｆｕｎｃ＿ｃｈｏｉｃｅを用いてＰＥＦ関数を選択し（図６のセレクタ６４０の処理に該当）、ＭＴで生成した擬似乱数列ＰＮをパラメータとして与えながら変換を繰り返す。
（５）最後に再び
ｃｒｙｐｔ＿ｍｕｌｔｉ（ｍｓｇ［ｉ］）；
ｃｒｙｐｔ＿ｖｅｒｔ＿ｒｏｔａｔｅ（ｍｓｇ［ｉ］）；
ｃｒｙｐｔ＿ｈｏｒｉ＿ｒｉｇｈｔｓｈｉｆｔ（ｍｓｇ［ｉ］）；
を作用させる。
【００５１】
（３−７．文書の復号化）
ｈｍｎｄｅｃｏｄｅ（ｋｅｙ［］， ｉｎｉｔ＿ｖａｌｕｅ［］）
を呼び出すと、復号化を行なう。ｋｅｙ，ｉｎｉｔ＿ｖａｌｕｅは配列で、あわせてメルセンヌツイスターの初期化に使われる。
（１）ｍｕｌｔｉ＿ｔａｂｌｅに乗算定数をしまう。
（２）ｉｎｖ＿ｔａｂｌｅにその乗算に関する逆元をしまう。
（３）擬似乱数を４ワードｆｕｎｃ＿ｃｈｏｉｃｅ［０］〜［３］の４つに格納し、積とＥＯＲを用いて新たな４ワードに書き換える。（あとでこの４ワードを３ビットずつに切り出し、上述の５＋３種のＰＥＦの選択を行う。）
（４）後で使われるべき乱数ブロックを、３＋Ｉｔｅｒａｔｉｏｎ＋３個作って配列ｔｅｍｐ＿ｒａｎｄにしまっておく。
（５）暗号文に対して、３つの逆変換を施す。
ｃｒｙｐｔ＿ｈｏｒｉ＿ｒｉｇｈｔｓｈｉｆｔ＿ｉｎｖ（ｍｓｇ［ｉ］，ｔｅｍｐ＿ｒａｎｄ［−−ｋ］）；
ｃｒｙｐｔ＿ｖｅｒｔ＿ｒｏｔａｔｅ＿ｉｎｖ（ｍｓｇ［ｉ］，ｔｅｍｐ＿ｒａｎｄ［−−ｋ］）；
ｃｒｙｐｔ＿ｍｕｌｔｉ＿ｉｎｖ（ｍｓｇ［ｉ］，ｔｅｍｐ＿ｒａｎｄ［−−ｋ］）；
（６）その後はＩｔｅｒａｔｅ回、ｆｕｎｃ＿ｃｈｏｉｃｅを用いてＰＥＦ関数を選択し、格納しておいたＭＴの出力を与えながら逆変換を繰り返す。
（７）最後に再び
ｃｒｙｐｔ＿ｈｏｒｉ＿ｒｉｇｈｔｓｈｉｆｔ＿ｉｎｖ（ｍｓｇ［ｉ］，ｔｅｍｐ＿ｒａｎｄ［−−ｋ］）；
ｃｒｙｐｔ＿ｖｅｒｔ＿ｒｏｔａｔｅ＿ｉｎｖ（ｍｓｇ［ｉ］，ｔｅｍｐ＿ｒａｎｄ［−−ｋ］）；
ｃｒｙｐｔ＿ｍｕｌｔｉ＿ｉｎｖ（ｍｓｇ［ｉ］，ｔｅｍｐ＿ｒａｎｄ［−−ｋ］）；
を作用させる。
【００５２】
＜４．実施形態４＞
実施形態４は、あらかじめ用意した数列（共有鍵）から生成した擬似乱数列のブロックを、当該擬似乱数列により選択される関数で変換して、安全な暗号乱数列を生成することを特徴とする擬似乱数列発生システムである。ここで、数列は、関数の選択及び関数のパラメータとして用いられる。暗号化通信における共有鍵を数列として用いることにより、生成した暗号乱数列をストリームサイファによる文書の暗号化・復号化に用いることができる。
【００５３】
（４−１．擬似乱数列の生成）
一般に実験などに利用されている擬似乱数列は、高速に生成されるが、いくつかのワードを見ると他のワードがわかってしまうため、暗号学的には安全でない。このため、従来、暗号乱数列の生成には、ＢＢＳ法に代表される計算量の大きな暗号化方式が用いられている。本実施形態は、本発明のポイントである、鍵情報を関数選択に用いることで、高速な擬似乱数列を少ない計算量で暗号乱数列に書き換えることを特徴とした擬似乱数発生システムであり、高速で安全なストリームサイファを構成することができる。
ここでは擬似乱数ＰＮの生成方法として実施形態１で説明したメルセンヌツイスター（ｍｔ１９９３７ａｒ．ｃ）を用いる。高速で周期が長い擬似乱数列を生成できるためである。なお、他の擬似乱数生成方法を用いてもよい。
前処理として、あらかじめ暗号化・復号化を行う双方で、共有鍵を用いて６２４ワードの秘密の擬似乱数列の初期値を求めておく。使い続ける共有秘密鍵の他に、一回の通信ごとにセッション鍵を受け取る場合には、ここで作成した初期値の一部をセッション鍵に変えたものを、その通信で用いる擬似乱数列の初期値とし、乱数は初期値の次の値から使うものとする。
【００５４】
擬似乱数列ＰＮは、必要になった分だけ次々に作ることとして、以下のように安全な擬似乱数列を出力する。擬似乱数列ＰＮの１２ｎワード目のデータを、１２ｎ＋１ワード目から１２ｎ＋１１ワード目のデータを用いて次のように書き換える。以下、擬似乱数のｍワード目のデータをＲ（ｍ）であらわす。
ｘ＝Ｒ（１２ｎ）とし、Ｒ（１２ｎ＋１）のデータを上から２ビットずつ１０回見て、この値により次の操作でｘを書き換えていく。
ｔ回目の２ビットが
（１）００ならば、ｘを、ｘ＋Ｒ（１２ｎ＋ｔ＋１）ｍｏｄ２３２に書き換える。
（２）０１ならば、ｘを、ｘ  ＥＸＯＲ  Ｒ（１２ｎ＋ｔ＋１）に書き換える。
（３）１０ならば、ｘを、ｘ×Ｒ（１２ｎ＋ｔ＋１）＊に書き換える。ただし、ｐ＊は、ｐの最下位ビットを１にした数とする。
（４）１１ならば、ｘを、ｘ  ｓｈｉｆｔ  Ｒ（１２ｎ＋ｔ＋１）に書き換える。ただし、ｓ  ｓｈｉｆｔ  tは、ｔの上５ビットの大きさの分だけのｓのビットを右にシフトし、ワードの右にはみ出た部分をビット反転させて、左に書いたものとする。
１０回書き換えたら、ｘを暗号乱数列のｎワード目として出力する。
【００５５】
なお、上記（１）〜（４）の関数は一例であり、高速に処理できる他の演算を用意してもよい。また、必要な強度に応じて変換の回数を増やし、また強制的に掛け算とシフトがあらわれるようにするなどの方法で、安全性を高めることができる。１つのワードを求めるのにｍ＋２ワード（ｍは６〜１６くらい）用いて変換の回数をｍ回とし、１回目とｍ−１回目の変換をシフト、２回目とｍ回目の変換を掛け算と決めるなど必要に応じて調整すると良い。
メルセンヌツイスターには、周期の完全な保障と、分布のある程度の保障がある。周期がとても長いことから、生成した安全擬似乱数列の周期も使い切ることができないくらい長くなり、共有鍵を取り替えずに長く使い続けることができる。
【００５６】
（４−２．本実施例を用いた暗号化システム及び復号化システムの構成例）
最後に、本実施形態の擬似乱数発生システムを用いて、ストリームサイファにより文書（平文）の暗号化及び復号化を行なう場合のシステム構成例を、図３のシステム構成図を参照しながら説明する。
本実施形態のシステムは、例えば通常のパソコン等の端末に実装するものする。図１に示すように、文書を暗号化して送信する側の端末には暗号化システム１１０を、文書を受信して復号化する側の端末には復号化システム１５０を実装する。また、暗号化システム１１０及び復号化システム１５０の双方に、数列（共有鍵１２２）、関数１２６、及び本実施形態の擬似乱数発生システム３３０を用意する。
暗号化システム１１０では、まず、共有鍵１２２から従来技術の手法により安全ではないかもしれない擬似乱数列ＰＮを生成する。次に、生成されたＰＮを用いて、関数選択プログラム３３４は関数１２６からＰＮの暗号化に用いる関数を選択する。また、擬似乱数生成プログラム３３２は、ＰＮを関数選択プログラム３３４で選択された関数のパラメータとして用いて関数を実行し、ＰＮを暗号化する。これにより、安全な擬似乱数列３２５を生成して、記憶領域に一時的に格納する。次に、ストリームサイファの典型的な例として、暗号化プログラム３３６は、擬似乱数列３２５と文書１２４のＥＸＯＲをとることにより文書１２４を暗号化して、暗号化文書１４０を生成する。
【００５７】
一方、復号化システム１５０でも、共有鍵１２２から従来技術の手法により安全ではないかもしれない擬似乱数列ＰＮを生成する。次に、生成されたＰＮを用いて、関数選択プログラム３３４は関数１２６からＰＮの暗号化に用いる関数を選択する。また、擬似乱数生成プログラム３３２は、ＰＮを関数選択プログラム３３４で選択された関数のパラメータとして用いて関数を実行し、ＰＮを暗号化する。これにより、安全な擬似乱数列３２５を生成して、記憶領域に一時的に格納する。次に、復号化プログラム３６６は、擬似乱数列３２５と暗号化文書１４０のＥＸＯＲをとることにより暗号化文書１４０を復号し、元の文書１２４を得る。
暗号化システム１１０と復号化システム１５０とでは、同じ共有鍵１２２及び関数１２６を用いて、同じ安全な擬似乱数列３２５を生成するため、暗号化に対応する復号化の処理を行なうことができる。
【００５８】
＜５．実施形態５＞
実施形態５は、上述の実施形態２〜４のシステムに、後述する「ＪＵＭＰ処理」を加えることにより、より効率の良い暗号化を行なう手法を提案する。なお、ここでは実施形態３と同様の暗号化システム及び復号化システムにＪＵＭＰ処理を追加する例で説明するが、使用する関数（ＰＥＦ）等については、実施形態３とは異なるものを用意して説明する。
本実施形態の暗号化システムの処理の流れを、図７に示す。
まず、共有鍵（数列）から上述の実施形態２〜４と同様の方法（例えばメルセンヌツイスター）により擬似乱数列を生成して、これを本実施形態で使用する擬似乱数列ＰＮとする（図７の左上部）。
次に、擬似乱数列ＰＮをセレクタ７４０に送り、どの関数７６０を選ぶかを決定する。図６で示した実施形態２〜４との違いは、ブロックの変換が何ステップ目であるかを記録する履歴メモリ７５０が追加されている点であり。これによりｊｕｍｐという値が計算される。
ｊｕｍｐは、「各ワードの情報を、どれだけ離れたワードに渡すか」を各関数に指定するものである。１つのブロックを変換するとき、ｊｕｍｐは１ステップ目の変換では１，２ステップ目は２，３ステップ目は４，…と二倍二倍に増えて行き、ｔ（１ブロック内のワード数）以上になったら１に戻す。このｊｕｍｐの処理は、履歴メモリ７５０がセレクタ７４０に指示を出すことにより行なう。
【００５９】
また、本実施形態では、関数の選択においても、第１ステップでは本実施形態で用いる９種類の関数（ＰＦ１〜ＰＦ９）のうちからワード内関数ＰＦ１〜ＰＦ４（ワード内の計算を行なう関数）の１つを選び、第２ステップではワード間関数ＰＦ５〜ＰＦ８（ブロック内の複数のワード間に跨る計算を行なう関数）の１つを選び、第３ステップではＰＦ９を選び、第４ステップではＰＦ１〜ＰＦ４の１つを選び、…という具合に、ステップごとに関数選択の範囲が変わる。この処理も履歴メモリ７５０がセレクタ７４０に指示を出すことにより行なう。なお、本実施形態で用いる９種類の関数（ＰＦ１〜ＰＦ９）については後で詳しく説明する。
また、選択された関数７６０は、ブロックサイズと同程度の大きさのパラメータを受け取る。関数のパラメータには、実施形態２〜４と同様、共有鍵（数列）から生成した擬似乱数列ＰＮを用いる。
【００６０】
上述のｊｕｍｐの効用は、次の通りである。1ブロック＝tワードとして、ワード間関数を用いてワード間に跨る変換を行なう場合、あるワードの情報を他の全てのワードに早く渡すためには、隣接する次のワードのみに情報を渡すのは、あるワードの情報が他の全てのワードに達するのにｔ回の繰り返しが必要なため、最も効率的な方法ではない。高速に変換するには２ワードなど少ないワード間の計算の方がよく、変換を行なうごとに、最初は１ワード隣り（間隔１）、次は２ワード隣り（間隔２）、次は４ワード隣り（間隔４）、…という具合にワードの間隔を倍倍にしていくのが最も効率的である。
ここで対象となる２ワードを●で表すと、上記のワードの間隔とは、
●●        間隔１の関係
●○●      間隔２の関係
●○○○●  間隔４の関係
である。
このように、全ての自然数ｔがｌｏｇ２（ｔ）桁の２進数によって表されることにより、ｌｏｇ２（ｔ）回の繰り返しによって、０，１，…，ｔ−１の全ての距離のワードに対して情報を渡すことができる。すなわち、ＪＵＭＰ処理はワード間関数が少ないワード間（本実施形態においては２ワード間）の計算であっても、少ない繰り返し回数で十分な撹拌がされるようにするための処理である。
【００６１】
（５−１．前提条件及び前処理）
（１）Ｗを３２ｂｉｔ＝１ワード符号なし整数の集合とする。
ここには、二項演算としてビットごとのＥＸＯＲ，ＡＮＤ，ＯＲ，足し算，掛け算（ｍｏｄｕｌｏ  ２{３２}）、単項演算として右シフト，左シフト，ビット反転が行える。これらは最近のＣＰＵの命令セットに通常入っている演算である。
（２）ブロックｂの集合ＢＬを、
ＢＬ＝Ｗｔ
で定義する。ただし、ｔは４，８，または１６とする。
（３）パラメータｐの集合ＰＡＲＡＭを、
ＰＡＲＡＭ＝Ｗｔ×｛０，１，２，…，ｔ／２｝
で定義し、飛ばし値ｊの集合ＪＵＭＰを
ＪＵＭＰ＝｛１，２，４，８，…，ｔ／２｝
で定義する。
（４）次の形の関数（ＰＥＦ）を９種類（ＰＦ１，．．．，ＰＦ９）用意する。これが図７でいうところの関数７６０に該当する。なお、９種類のＰＥＦの詳細は後で詳しく説明する。
ＰＦ：  ＪＵＭＰ×ＰＡＲＡＭ×ＢＬ→ＢＬ．
これらのＪＵＭＰ，ＰＡＲＡＭ，ＢＬが図７の関数７６０への入力線３本にそれぞれ対応している。
ここで、ＰＦの逆関数
ＰＦ’：  ＪＵＭＰ×ＰＡＲＡＭ×ＢＬ→ＢＬ．
も復号化のために構成しておく。ここで、
ＰＦ’（ｊ， Ｐ， ＰＦ（ｊ， Ｐ， ｂ））＝ｂ
である必要があり、また高速に計算できるものが望ましい。
（５）本実施形態では、鍵情報（共有鍵）は上述の他の実施形態と同様にメルセンヌツイスター（ＭＴ）の処理に送られる。ＭＴを用いて乗法定数テーブル、加法定数テーブルを作成する。乗法定数テーブル、加法定数テーブルについては後で詳しく説明する。
なお、上記以外の前提条件及び前処理は、上述の実施形態３の（３−１．前処理）〜（３−３．グローバル変数）で説明した通りであり、あらかじめＩｔｅｒａｔｉｏｎ（変換回数）とＬｏｇ＿Ｔｕｐｌｅ（ブロック内のワード数の対数）を決めておく。
【００６２】
（５−２．文書の暗号化）
次に、平文ブロックを暗号化する。ここでは、１ブロック＝４ワード、変換回数を４回として説明する。なお、本実施形態において、文書の暗号化は、ＪＵＭＰ処理以外の部分は実施形態３と同様である。
今、与えられた平文ブロックはワード長変数t個の配列
Ｂ：＝（ｂ０，ｂ１，．．．，ｂ｛ｔ−１｝）
に格納されているものとする。
本実施形態の一ラウンドは次のようになっている。
１）ラウンドの開始
２）ＰＦ１〜ＰＦ４から１つランダムに選んで、それを用いてＢを書き換える
３）ＰＦ５〜ＰＦ８から１つランダムに選んで、それを用いてＢを書き換える
４）ＰＦ９を用いてＢを書き換える
５）ラウンドの終了
上記を４ラウンド行い、１ブロック分の暗号化ブロックを得る。
【００６３】
具体的には、１ブロックの暗号化は、次のようにして行われる。
（０）ｊｕｍｐ←１
（１）ＭＴから４ワードの擬似乱数を取得
（２）この４ワードから２ビットの擬似乱数を８組生成し、ｃ１，ｃ２，ｃ３，．．．，ｃ８とする（生成方法については後で説明する）
（３）ｃ１＝０，１，２，３に従って、ＰＦ１，ＰＦ２，ＰＦ３，ＰＦ４のうちの１つＰＦ＊を選択する
（４）ＭＴから４ワードの擬似乱数を取得し、これをＰとする
（５）ＰＦ＊（ｊｕｍｐ，Ｐ，Ｂ）を用いてＢを書き換える。ｊｕｍｐを２倍し、ｔ以上になったら１にする
（６）ｃ２＝０，１，２，３に従って、ＰＦ５，ＰＦ６，ＰＦ７，ＰＦ８のうちの一つＰＦ＊を選択する
（７）ＭＴから４ワードの擬似乱数を取得、Ｐとする
（８）ＰＦ＊（ｊｕｍｐ，Ｐ，Ｂ）を用いてＢを書き換える。ｊｕｍｐを２倍し、ｔ以上になったら１にする
（９）ＭＴから４ワードの擬似乱数を取得、Ｐとする
（１０）ＰＦ９（ｊｕｍｐ，Ｐ，Ｂ）を用いてＢを書き換える。ｊｕｍｐを２倍し、ｔ以上になったら１にする
（３）〜（１０）を４回繰り返す。２回目ではｃ１，ｃ２の代わりにｃ３，ｃ４を使う。
3回目ではｃ５，ｃ６，４回目ではｃ７，ｃ８をそれぞれ使う。なお、図７でいうと、ｊｕｍｐが履歴メモリ７５０に格納されている。
【００６４】
次に、上述の（２）のｃ１〜ｃ８の生成方法を説明する。
上記（１）で取得した４ワードをｆｕｎｃ＿ｃｈｏｉｃｅ［０］，．．．，ｆｕｎｃ＿ｃｈｏｉｃｅ［３］として、次の変換を行う。
ｆｕｎｃ＿ｃｈｏｉｃｅ［２］＊＝（ｆｕｎｃ＿ｃｈｏｉｃｅ［０］｜１）；
ｆｕｎｃ＿ｃｈｏｉｃｅ［３］＊＝（ｆｕｎｃ＿ｃｈｏｉｃｅ［１］｜１）；
ｆｕｎｃ＿ｃｈｏｉｃｅ［０］＾＝（ｆｕｎｃ＿ｃｈｏｉｃｅ［３］＞＞５）；
ｆｕｎｃ＿ｃｈｏｉｃｅ［１］＾＝（ｆｕｎｃ＿ｃｈｏｉｃｅ［２］＞＞５）；
ここで、＊＝は左辺に右辺を掛けて左辺に代入する命令，＾＝は左辺に右辺とＥＸＯＲをとって、左辺に代入する命令，｜はビットごとのＯＲ，＞＞５は５ビット右シフトを表す。こうして、ｆｕｎｃ＿ｃｈｏｉｃｅ［０］の上位２ビットがｃ０，次の２ビットがｃ１，と順番にとっていく。ラウンドの回数が１６より多いときには、例えばｆｕｎｃ＿ｃｈｏｉｃｅ［１］の上位ビットから用いるようにする。
【００６５】
（５−３．文書の復号化）
本実施形態における文書の復号化は、ＪＵＭＰ処理以外の部分は実施形態３と同様である。
（１）復号に用いるＪＵＭＰの初期値を求める。
これは暗号化に用いる上述の２つの定数、Ｉｔｅｒａｔｉｏｎ（変換回数）とＬｏｇ＿Ｔｕｐｌｅ（ブロック内のワード数の対数）から、次の式で求める事が出来る。
ＪＵＭＰ＝１＜＜（（３＊Ｉｔｅｒａｔｉｏｎ−１）％Ｌｏｇ＿Ｔｕｐｌｅ）
ここで、％は剰余を求める演算であり、１  ＜＜  は、１を＜＜の右の回数だけ２倍するという意味である。
（２）ＪＵＭＰの変化は、暗号化の逆にする。
すなわち、１ブロック＝４ワードの場合は、繰り返し毎に４，２，１と半分にしていき、１の次は４に戻る。
（３）このようにＪＵＭＰが決定されれば、暗号化の時に使用した関数に対応する逆関数を選択し、このＪＵＭＰ値および暗号化時と同じパラメータを与えることができる。
【００６６】
（５−４．用意する関数）
本実施形態で用いる関数として、ブロック内のそれぞれのワードを主にワード内で変換する関数としてＰＦ１，ＰＦ２，ＰＦ３，ＰＦ４の４種類、ワード間の情報を混ぜるための変換を行なう関数としてＰＦ５，ＰＦ６，ＰＦ７，ＰＦ８の４種類、関数として１種類、計９種類の関数を用意する。以降、これら９種類の関数について順に説明する。なお、これらのＰＦ１〜ＰＦ９の関数は一例であり、高速に処理できる他の演算を用意してもよい。
【００６７】
（１）ＰＦ１〜ＰＦ４（ワード内関数）
ＰＦ１〜ＰＦ４は、ブロック内のそれぞれのワードを主にワード内で変換するワード内関数である。復号化にはそれぞれ関数の逆の処理を行なう逆関数（ワード内逆関数）を用いる。
ブロックをｂ０，ｂ１，…，ｂ｛ｔ−１｝なるｔワードとし、パラメータをｐ０，ｐ１，．．．，ｐ｛ｔ−１｝なるｔワードとする。まず、
ｂｊ←ｂｊ  ＥＸＯＲ  ｐｊ
なる代入を行う。（ｊ＝０，１，…，ｔ−１）。つぎに、奇数定数をかける：
ｂｊ←ｂｊ×ｃｊ（ｍｏｄ  ２{３２}，以下ｍｏｄはいつもついているが省略）（ｊ＝０，１，…，ｔ−１）。
ｃｊは、あらかじめＭＴにより生成された奇数乱数のテーブルｍ０，ｍ１，…，ｍ｛３１｝より次の方法で選ばれる。ｍ０，…，ｍ｛３１｝はすべて奇数であるよう、最下位ビットを1にしてある。また、ｃｊ：＝ｍ{ｋｊ}であり、ｋｊはｐ｛ｊ＋ｅｌｌ}の最上位５ビットを０〜３１の整数と見たものである。ここで、ｅｌｌの値はＰＦ１，ＰＦ２，ＰＦ３，ＰＦ４のときそれぞれ１，２，２，３である。なお、テーブルを用意したのは復号化の際にｃｊの逆数（ｍｏｄｕｌｏ  ２{３２}）を用いるからである。
本実施形態では、暗号化を行う前処理としてこの乗法定数テーブルｍ０，…，ｍ｛３１｝をＭＴにより作成し、そのｍｏｄｕｌｏ  ２{３２}での乗法逆数のテーブルを作成して保存する。さらに、ある加法定数テーブルａｄｄ０，…，ａｄｄ｛３１｝もＭＴにより作成して保存する。
【００６８】
次に、
ｂ｛（ｊ＋ｊｕｍｐ）ｍｏｄ ｔ｝←ｂ｛（ｊ＋ｊｕｍｐ）ｍｏｄ ｔ｝□ａｄｄ｛［ｂｊ＞＞（３２−５）］｝
なる代入を行なう。ｊ＝０，１，２，…，ｔ−１を、この順序で計算する。これは、まずｂｊの上位５ビットを見て、それに対応するａｄｄのテーブル（加法定数テーブル）の値と、ｂ｛ｊ＋ｊｕｍｐ｝（添え字はｍｏｄｕｌｏ  ｔで見る）の値とを二項演算□を取って、その結果をｂ｛ｊ＋ｊｕｍｐ｝に格納するということである。二項演算□は、ＰＦ１，ＰＦ２，ＰＦ３，ＰＦ４のときにそれぞれ＋，ＥＯＲ，＋，ＥＯＲである。
次に、以下のようにして１６〜２３に値をとる擬似乱数ｓｊを生成する。
ｓｊ←（（ｐｊ＞＞（３２−４））｜０ｘ１０）＆０ｘ１７
ここで、＆はビットごとのＡＮＤ演算である。
ｓｊを用いて、ｂｊに対して次の二つの変換のいずれかを行う。
ｂｊ←（（〜ｂｊ）＜＜（３２−ｓｊ））｜（ｂｊ＞＞ｓｊ）．
ｂｊ←ｂｊ  ＥＸＯＲ  （（〜ｓｉｍ  ｂｊ）＞＞ｓｊ）．
上はローテート（ただし、左からあふれた分はビット反転〜をとる）である。下は、ビット反転したものを右にｓｊシフトしたものをｂｊに足すものである（シフトと呼ぶ）。ＰＦ１，ＰＦ２，ＰＦ３，ＰＦ４で、それぞれローテート、ローテート、シフト、シフトを選ぶ。
【００６９】
（２）ＰＦ５〜ＰＦ８（ワード間関数）
ＰＦ５〜ＰＦ８は、は、主にワード間（本実施形態においては２ワード間）の情報を混ぜるための変換を行なうワード間関数である。復号化にはそれぞれの関数の処理の逆の操作を行なう逆関数（ワード間逆関数）を用いる。
１）ＰＦ５
まずｊ＝０とし、
ｂｊ←ｂｊ＋（ｂ｛ｊ−ｊｕｍｐ｝×ｐｊ）
を行なう。
ｓｊ←（（ｐｊ＞＞（３２−４））｜０ｘ１０）＆０ｘ１７
により１６〜２３に値をとる擬似乱数を生成し、
ｂｊ←ｂｊ  ＥＸＯＲ  （（〜ｓｉｍ  ｂｊ）＞＞ｓｊ）．
を行う。これをｊ＝０，１，２，…，ｔ−１とこの順に繰り返す。
【００７０】
２）ＰＦ６〜ＰＦ８
ｊ＝０とする。
ｓ←（ｐｊ＞＞（３２−ｌｏｇ２（ｔ）））
により、ｓにｐｊの上位ｌｏｇ２（ｔ）ビットを格納する。ｓ＝ｊとなったときは、ｓから１を引く（ｍｏｄｕｌｏ  ｔで計算する）。これにより、ｓとｊは異なる。ここで、
ＰＦ６では、
ｂｊ←（ｂｊ  ＥＸＯＲ  （ｂ｛ｊ−ｊｕｍｐ｝×ｂｓ））−ｐｊ
ｂｊ←ｂｊ  ＥＸＯＲ  （ｂｊ＞＞１６）
なる代入を行う。添え字はｍｏｄｕｌｏ  ｔで考える。
ＰＦ７，ＰＦ８では、
ｂｊ←（ｂｊ  ＥＸＯＲ  （ｂ｛ｊ−ｊｕｍｐ｝×（ｂｓ□−ｐｊ））；
ｂｊ←ｂｊ  ＥＸＯＲ  （ｂｊ＞＞ｃ）；
なる代入を行う。ここで、□は、ＰＦ７の時にはビットごとのＯＲ，ＰＦ８ではＥＸＯＲである。また、ｃは、ＰＦ７のときには１６、ＰＦ８のときには１７である。
【００７１】
（３）ＰＦ９
ｋ＝２（ｐ０＋ｐ｛ｔ−１｝)＋１  ｍｏｄ  ２{３２}
としておいて、ｊｕｍｐ＿ｏｄｄをｊｕｍｐ以下の最大の奇数とする。ブロックｂ０，ｂ１，…，ｂ｛ｔ−１｝において、ｋのビットパターンで１になっているところを、ｊｕｍｐ＿ｏｄｄとばしに巡回置換する。すなわち、以下の置換を行う。
１）ｋのビットパターンで１になっている部分に対応するｂ０のビットを抽出し、保存しておく。これは、ｂ０とｋのビットごとＡＮＤ演算の結果を保存することと等しい。
２）次に、ｂ０における上記のビットを、ｂ{−ｊｕｍｐ_ｏｄｄ}における対応するビットによって置換する。ここで、ｂの添え字はｍｏｄｕｌｏ  ｔで計算するものとする。
３）次に、ｂ{−ｊｕｍｐ_ｏｄｄ}における対応するビットを、ｂ{−２ｊｕｍｐ_ｏｄｄ}に対応するビットによって置換する。このように、玉突き的にｂ{−ｊ×ｊｕｍｐ_ｏｄｄ}における対応するビットを、
ｂ{−（ｊ＋１）×ｊｕｍｐ_ｏｄｄ}における対応するビットに置換する、という操作をｊ＝０，１，…ｔ−１について行う。
４）最後に、ｂ{−（ｔ＋１）×ｊｕｍｐ_ｏｄｄ}における対応するビットを、保存しておいたｂ０の対応するビットに置換する。
復号化には、上述の処理の逆の操作を行なう逆関数を用いる。
【００７２】
＜６．実施形態６＞
実施形態６は、実施形態２〜５の各実施形態において、あらかじめ用意した数列（共有鍵）から上述のｃｒｙｐｔＭＴ（実施形態１）の方法で生成した暗号学的に安全な擬似乱数列ＳＰＮを、これらの実施形態で用いる擬似乱数列ＰＮとする手法である。この手法では、暗号化に用いる関数の選択及び関数のパラメータに暗号学的に安全な擬似乱数列を用いるため、より解読が困難な暗号化を行なうことができる。
【図１】
2011128655.tif 000003
【図２】
2011128655.tif 000004
【図３】
2011128655.tif 000005
【図４】
2011128655.tif 000006
【図５】
2011128655.tif 000007
【図６】
2011128655.tif 000008
【図７】
2011128655.tif 000009