(57)【要約】  データの通信や蓄積の際にデータを秘匿するための安全性の高い暗号装置を提供する。秘密鍵に基づき擬似乱数列を生成し、前記擬似乱数列を平文に作用させることにより暗号文を生成する暗号装置であって、前記擬似乱数列の生成に用いる内部状態として、有限個の数値の列の並び替えを基礎とする状態に基づく内部状態を用い、前記擬似乱数列の生成に用いる一時変数の少なくとも一つが、前記内部状態のうちの一つ、又は、複数個の数値を使用した、線形、又は、非線形、線形及び非線形の組み合わせの結果に基づき、内部状態の数より小さい数に依存し、あらかじめ定められた、左又は右ローテイトシフトを実行した結果を値とする一時変数であり、前記生成される擬似乱数を、前記内部状態のうちの１つ又は複数個の数値と、前記一時変数との演算によって生成する。
2008010441.tif 000002
【特許請求の範囲】
【請求項１】
秘密鍵に基づき擬似乱数列を生成し、前記擬似乱数列を平文に作用させることにより暗号文を生成する暗号装置であって、
前記擬似乱数列の生成に用いる内部状態として、有限個の数値の列の並び替えを基礎とする状態に基づく内部状態を用い、
前記擬似乱数列の生成に用いる一時変数の少なくとも一つを、
前記内部状態のうちの一つ、又は、複数個の数値を用いた、線形、又は、非線形、線形及び非線形の組み合わせの結果に基づき、内部状態の数より小さい数に依存し、あらかじめ定められた、左又は右ローテイトシフトを実行した結果を値とする一時変数とし、
前記擬似乱数を、前記内部状態のうちの１つ又は複数個の数値と、前記一時変数との予め定められた所定の演算によって生成する手段を備えている、
ことを特徴とする暗号装置。
【請求項２】
前記有限個の数値の列の並び替えを基礎とする状態に基づく内部状態に関して、
前記内部状態の更新を、並び替え以外の、線形演算、および、非線形演算を用いて行う、ことを特徴とする請求項１に記載の暗号装置。
【請求項３】
前記有限個の数値の列の並び替えを基礎とする状態に基づく内部状態に関して、
前記内部状態の更新を、並び替え以外の、線形演算及び非線形演算を用いて行い、前記内部状態の状態数を、単調増加と単調減少のうちの一方にしたがって変化させる、ことを特徴とする請求項１に記載の暗号装置。
【請求項４】
前記有限個の数値の列の並び替えを基礎とする状態に基づく内部状態に関して、
前記内部状態の更新を、並び替え以外の、線形演算及び非線形演算を用いて行い、前記内部状態の状態数を振動させる、ことを特徴とする請求項１に記載の暗号装置。
【請求項５】
前記内部状態の更新を、
前記擬似乱数列の出力ごとに行う、
前記擬似乱数列の出力よりも多く行う、
前記擬似乱数列の出力よりも少なく行う、
のうち選択されたいずれか一つで行う、ことを特徴とする、請求項１乃至４のいずれか一項に記載の暗号装置。
【請求項６】
前記ローテイトシフトの方向及び／又はシフト数を、前記内部状態の数値に依存して動的に変更する、ことを特徴とする、請求項１乃至５のいずれか一項に記載の暗号装置。
【請求項７】
前記ローテイトシフトの方向及びシフト数を、あらかじめ定められたテーブルの値に従って変更する、ことを特徴とする、請求項１乃至５のいずれか一項に記載の暗号装置。
【請求項８】
前記擬似乱数列の生成に用いる内部状態として、配列Ｓの要素の並び替えと算術加算を繰り返すことで配列Ｓの要素を攪拌し配列Ｓの初期状態を作成し、その際、前記一時変数をなす内部変数ｋの初期値を配列Ｓの要素から求める第１の処理部と、
前記擬似乱数（以下、「鍵ストリーム」と称する）を生成するにあたり、第１、第２のインデックス変数ｉとｊに関して配列Ｓの要素Ｓ［ｊ］と内部変数ｋの加算結果をローテイトシフトした値で内部変数ｋの値を更新し、
Ｓ［ｉ］＋Ｓ［ｊ］による配設Ｓの参照結果Ｓ［（Ｓ［ｉ］＋Ｓ［ｊ］）］と内部変数ｋとの加算結果に基づき、鍵ストリームを出力し、
前記鍵ストリームを生成するために参照した配列Ｓの要素Ｓ［（Ｓ［ｉ］＋Ｓ［ｊ］）］を、鍵ストリーム出力の直後に内部変数ｋと配列要素Ｓ［ｉ］を用いて更新する第２の処理部と、
を備えている、ことを特徴とする請求項１記載の暗号装置。
【請求項９】
配列Ｓの要素数Ｎとローテイトシフトのシフト数ｎとがＮ＝２ｎの関係とされる、ことを特徴とする請求項８記載の暗号装置。
【請求項１０】
前記擬似乱数列の生成に用いる内部状態として、配列Ｓの要素の並び替えと算術加算を繰り返すことで配列Ｓの要素を攪拌し配列Ｓの初期状態を作成し、その際、前記一時変数をなす内部変数ｋの初期値を配列Ｓの要素から求める第１の処理部と、
前記擬似乱数（以下、「鍵ストリーム」と称する）を生成するにあたり、
第１のインデックス変数ｉの配列要素Ｓ［ｉ］を第１のシフト数ローテイトシフトした値と、第２のインデックス変数ｊとを算術加算した結果に基づき、第２のインデックス変数ｊの値を更新し、
第２のインデックス変数ｊの配列要素Ｓ［ｊ］を第２のシフト数ローテイトシフトした値と内部変数ｋとの算術加算結果に基づき内部変数ｋの値を更新し、
Ｓ［ｉ］＋Ｓ［ｊ］による配設要素Ｓ［（Ｓ［ｉ］＋Ｓ［ｊ］）］を第３のシフト数ローテイトシフトした値と内部変数ｋとの算術加算結果に基づき、鍵ストリームを出力し、
前記鍵ストリームを生成するために参照した配列要素Ｓ［（Ｓ［ｉ］＋Ｓ［ｊ］）］を、鍵ストリーム出力の直後に内部変数ｋと配列要素Ｓ［ｉ］を用いて更新する第２の処理部と、
を備えている、ことを特徴とする請求項１記載の暗号装置。
【請求項１１】
初期設定配列ａを用い、配列ａの並べ替えを行って攪拌し、前記一時変数をなす内部変数ｋを、対応する配列要素ａをローテイトシフトしたものと算術加算して求め、前記擬似乱数列の生成に用いる内部状態として配列Ｓを、配列ａの要素をローテイトシフトしたものと配列Ｓの要素との所定の演算によって求める第１の処理部と、
前記擬似乱数（以下、「鍵ストリーム」と称する）を生成するにあたり、第１、第２のインデックス変数ｉ、ｊに関して配列Ｓの参照結果Ｓ［ｊ］と内部変数ｋとを算術加算し、Ｓ［ｉ］＋Ｓ［ｊ］による配設Ｓの参照結果と内部変数ｋに基づき、鍵ストリームを出力し、
鍵ストリームを生成するために参照したＳのエントリを、鍵ストリーム出力直後に内部変数ｋを用いて更新する第２の処理部と、
を備えている、ことを特徴とする請求項１記載の暗号装置。
【請求項１２】
秘密鍵に基づき擬似乱数列を生成し、前記擬似乱数列を平文に作用させることにより暗号文を生成する暗号装置を構成するコンピュータに、
前記擬似乱数列の生成に用いる内部状態として、有限個の数値の列の並び替えを基礎とする状態に基づく内部状態を用い、
前記擬似乱数列の生成に用いる一時変数の少なくとも一つを、
前記内部状態のうちの一つ、又は、複数個の数値を使用した、線形、又は、非線形、線形及び非線形の組み合わせの結果に基づき、内部状態の数より小さい数に依存し、あらかじめ定められた、左又は右ローテイトシフトを実行した結果を値とする一時変数とし、
前記擬似乱数を、前記内部状態のうちの１つ又は複数個の数値と、前記一時変数との予め定められた所定の演算によって生成する、処理
を実行させるプログラム。
【請求項１３】
請求項１２記載のプログラムにおいて、
前記有限個の数値の列の並び替えを基礎とする状態に基づく内部状態に関して、
前記内部状態の更新を、並び替え以外の、線形演算、および、非線形演算を用いて行う、ことを特徴とするプログラム。
【請求項１４】
請求項１２記載のプログラムにおいて、
前記有限個の数値の列の並び替えを基礎とする状態に基づく内部状態に関して、
前記内部状態の更新として、並び替え以外の、線形演算及び非線形演算を用いて行い、前記内部状態の状態数を、単調増加と単調減少のうちの一方にしたがって変化させる、ことを特徴とするプログラム。
【請求項１５】
請求項１２記載のプログラムにおいて、
前記有限個の数値の列の並び替えを基礎とする状態に基づく内部状態に関して、
前記内部状態の更新として、並び替え以外の線形演算及び非線形演算を用いて行い、内部状態の状態数を振動させる、ことを特徴とするプログラム。
【請求項１６】
請求項１２記載のプログラムにおいて、
前記内部状態の更新を、
前記擬似乱数列の出力ごとに行う、
前記擬似乱数列の出力よりも多く行う、
前記擬似乱数列の出力よりも少なく行う、
のうちの選択されたいずれか一つで行う、ことを特徴とする、プログラム。
【請求項１７】
請求項１２記載のプログラムにおいて、
前記ローテイトシフトの方向及び／又はシフト数を、前記内部状態の数値に依存して動的に変更する、ことを特徴とする、プログラム。
【請求項１８】
請求項１２記載のプログラムにおいて、
前記ローテイトシフトの方向及びシフト数を、あらかじめ定められたテーブルの値に従って変更する、ことを特徴とする、プログラム。
【請求項１９】
前記擬似乱数列の生成に用いる内部状態として、配列Ｓの要素の並び替えと算術加算を繰り返すことで配列Ｓの要素を攪拌し配列Ｓの初期状態を作成し、その際、前記一時変数をなす内部変数ｋの初期値を配列Ｓの要素から求める第１の処理と、
前記擬似乱数（以下、「鍵ストリーム」と称する）を生成する処理として、
第１、第２のインデックス変数ｉとｊに関して配列Ｓの要素Ｓ［ｊ］と内部変数ｋの算術加算結果をローテイトシフトした値で内部変数ｋの値を更新し、
Ｓ［ｉ］＋Ｓ［ｊ］による配設Ｓの参照結果Ｓ［（Ｓ［ｉ］＋Ｓ［ｊ］）］と内部変数ｋとの算術加算結果に基づき、鍵ストリームを出力し、
前記鍵ストリームを生成するために参照した配列Ｓの要素Ｓ［（Ｓ［ｉ］＋Ｓ［ｊ］）］を、鍵ストリーム出力の直後に内部変数ｋと配列要素Ｓ［ｉ］を用いて更新する第２の処理と、
を前記コンピュータに実行させる請求項１２記載のプログラム。
【請求項２０】
前記擬似乱数列の生成に用いる内部状態として、配列Ｓの要素の並び替えと算術加算を繰り返すことで配列Ｓの要素を攪拌し配列Ｓの初期状態を作成し、その際、前記一時変数をなす内部変数ｋの初期値を配列Ｓの要素から求める第１の処理と、
前記擬似乱数（以下、「鍵ストリーム」と称する）を生成する処理として、
第１のインデックス変数ｉの配列要素Ｓ［ｉ］を第１のシフト数ローテイトシフトした値と、第２のインデックス変数ｊとを算術加算した結果に基づき、第２のインデックス変数ｊの値を更新し、
第２のインデックス変数ｊの配列要素Ｓ［ｊ］を第２のシフト数ローテイトシフトした値と内部変数ｋとの算術加算結果に基づき内部変数ｋの値を更新し、
Ｓ［ｉ］＋Ｓ［ｊ］による配設要素Ｓ［（Ｓ［ｉ］＋Ｓ［ｊ］）］を第３のシフト数ローテイトシフトした値と内部変数ｋとの算術加算結果に基づき、鍵ストリームを出力し、
前記鍵ストリームを生成するために参照した配列要素Ｓ［（Ｓ［ｉ］＋Ｓ［ｊ］）］を、鍵ストリーム出力の直後に内部変数ｋと配列要素Ｓ［ｉ］を用いて更新する第２の処理と、
を前記コンピュータに実行させる請求項１２記載のプログラム。
【請求項２１】
初期設定配列ａを用い、配列ａの並べ替えを行って攪拌し、前記一時変数をなす内部変数ｋを、対応する配列要素ａをローテイトシフトしたものと算術加算して求め、前記擬似乱数列の生成に用いる内部状態として配列Ｓを、配列ａの要素をローテイトシフトしたものと配列Ｓの要素との所定の演算によって求める第１の処理と、
前記擬似乱数（以下、「鍵ストリーム」と称する）を生成する処理として、
第１、第２のインデックス変数ｉ、ｊに関して配列Ｓの参照結果Ｓ［ｊ］と内部変数ｋとを算術加算し、
Ｓ［ｉ］＋Ｓ［ｊ］による配設Ｓの参照結果と内部変数ｋに基づき、鍵ストリームを出力し、
鍵ストリームを生成するために参照したＳのエントリを、鍵ストリーム出力直後に内部変数ｋを用いて更新する第２の処理と、
を前記コンピュータに実行させる請求項１２記載のプログラム。
【請求項２２】
コンピュータを用いて擬似乱数列を生成する方法であって、
擬似乱数列の生成に用いる内部状態として、有限個の数値の列の並び替えを基礎とする状態に基づく内部状態を用い、
前記擬似乱数列の生成に用いる一時変数の少なくとも一つを、
前記内部状態のうちの一つ、又は、複数個の数値を用いた、線形、又は、非線形、線形及び非線形の組み合わせの結果に基づき、内部状態の数より小さい数に依存し、あらかじめ定められた、左又は右ローテイトシフトを実行した結果を値とする一時変数とし、
前記擬似乱数を、前記内部状態のうちの１つ又は複数個の数値と、前記一時変数との予め定められた所定の演算によって生成する、
ことを特徴とする擬似乱数列の生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願の記載］
本発明は、日本国特許出願：特願２００６−１９９６８１号（平成１８年７月２１日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、データの通信や蓄積の際にデータを秘匿するための暗号装置及びコンピュータ・プログラムと方法に関する。
【背景技術】
【０００２】
＜ストリーム暗号概説＞
データを秘匿するための手法に暗号がある。暗号の中で、高速な暗号化及び復号を行うために、平文をビット単位あるいはバイト単位などで逐次、暗号化するストリーム暗号がある。典型的なストリーム暗号は、鍵ストリームを生成する鍵ストリーム生成部と、鍵ストリームと平文を結合する結合部と、からなる。例えば、暗号処理では、秘密鍵をシードとして擬似乱数を生成し(鍵ストリーム生成部)、その擬似乱数と平文をXORし(結合部)、暗号文を生成する。ここで、XORはビット毎の排他的論理和を意味する。【０００３】
平文をP、擬似乱数をR、暗号文をCとすると、
P XOR R = C
の関係となる。【０００４】
復号処理では、同じシードから擬似乱数を生成して暗号文とXORすることで、平文を得ることができる。【０００５】
C XOR R = (P XOR R) XOR R 
= P XOR (R XOR R) 
= P XOR 0 
= P 
の関係となり、
C XOR R = P 
が得られる。【０００６】
＜ストリーム暗号の安全性＞
ストリーム暗号は、結合部がXORなど簡単な処理で実現されることが多い。そのためストリーム暗号の安全性は、鍵ストリーム生成部が生成する擬似乱数の安全性に依存する。【０００７】
ここでいう、擬似乱数の安全性は、観測済みの擬似乱数列から、今後発生する擬似乱数列が予測できないことに依存している。【０００８】
例えば、鍵ストリーム生成部が、a, b, c, a, b, c, ... のように繰り返す鍵ストリームを生成したならば、観測済みの擬似乱数から、今後発生する擬似乱数の予測がつくために、暗号文が解読されてしまう。それは、結合部の逆演算を実行できるからである。【０００９】
すなわち、擬似乱数Rの予測がつけば、暗号文Cを観測して、
C XOR R = P 
により、平文Pを得ることができる。【００１０】
前述のように考えると、鍵ストリーム生成部が生成する擬似乱数が予測不可能な乱数（真の乱数）を生成するならば、そのストリーム暗号は安全であるといえる。逆にいえば、鍵ストリーム生成部が生成する擬似乱数が真の乱数と区別できるような情報を見つけることができれば、そのストリーム暗号は何がしかの安全性が低下していると考えることが出来る。【００１１】
＜ストリーム暗号の安全性評価手法の一例＞
前述ような考え方に基づいて、ストリーム暗号の安全性を評価する手法がある。出力された暗号文や擬似乱数列が、真の乱数列と区別がつくことを示す暗号の攻撃手法を、「Distinguishing Attack」とよぶ。【００１２】
真の乱数との区別は、出力された暗号文や擬似乱数列が、何がしかの偏りや、特徴を持っていることが示せれば、区別できたと判断する。【００１３】
Distinguishing Attackでは、このような偏りや特徴を示す手段を、「Distinguisher 」と呼び、このような偏りや特徴を示す手段を発見したり作成したりすることを、「Distinguisherを構成する」と言う。Distinguisher が構成できるならば、Distinguishing Attackが適用できることになる。【００１４】
ある暗号に対して、Distinguishing Attackが適用できるならば、その暗号は平文または鍵の情報を漏らしている可能性があるので、安全な暗号であると保証することが出来ない。【００１５】
従って、Distinguishing Attackが適用できる暗号に修正を加え、Distinguishing Attackが適用出来なくなれば、暗号の安全性が向上したと考えることが出来る。【００１６】
＜ストリーム暗号の具体例＞
RC4は、Ron Rivest氏によって開発された暗号方式であり、RFC2246(TLS), WEP, WPA など暗号標準としてよく利用されるストリーム暗号である。RC4の仕様は、RFC2246(TLS)などで公開されていると言ってよい。【００１７】
RC4は、処理単位nビットが可変という特徴を持ちながらも、処理単位nを大きくするとメモリが2n必要となり、鍵スケジュールも極端に低速になる。【００１８】
そのため、現実的に、ｎは8ビットを越える実装は少なく、32ビットを越える実装は不可能であった。【００１９】
よって、RC4は、32bit/64bitプロセッサといった最近のプロセッサ・サイズに適した実装が出来なかった。【００２０】
32ビットRC4ではこれらの制限が生じないよう、32bit/64bitプロセッサで高速かつ小メモリで実装可能なアルゴリズムに改良された。2005年にG. Gongらが発表した論文（非特許文献１）である。【００２１】
非特許文献１の論文では、処理単位が32bitの場合、速度は、RC4の約3.1倍高速、メモリはRC4の約2^{-22}倍に抑えることに成功している。【００２２】
また、内部変数kを追加することにより、過去に報告されたRC4の脆弱性（統計的な偏り）が生じないアルゴリズムに改良されている。【００２３】
＜発明が対象とする攻撃手法の要点＞
G. Gongらのアルゴリズムの場合、連続する出力の最下位ビットが必ず一致するというdistinguisherの構成が可能となる。【００２４】
このdistinguisherにより、約2^{30}のデータ量で真の乱数系列と区別可能となる。【００２５】
＜攻撃手法の例示のための、G. Gongら提案した改良アルゴリズムの説明＞
図２は、非特許文献１において、G. Gongらによって提案されたRC4の改良アルゴリズム（32bit RC4）を示す図である。G. Gongらによって提案されたRC4型ストリーム暗号は、配列Sのエントリ数が2^{n}個、配列Sのエントリサイズがmビットである。【００２６】
また、非特許文献１の提案では、n=8, m=32のモデルについてのみKSAの初期定数aiを定義しているので、本明細書における解析でも、n=8, m=32のモデルについて、詳しく解析を行う。以下では、基本処理単位n, mを元に便宜上GGHN(n,m)と記述する。【００２７】
図２に示されるように、G. Gongらによって提案されたRC4型ストリーム暗号GGHN(n,m)は、KSA(K,S)とPRGA(S)の二つの処理から構成される。【００２８】
KSA(K,S)は、いわゆる初期設定であり、４０ビットから２５６ビットの鍵Kを基にして、３２ビット２５６個の配列を並べ替え、初期状態Sを作り出す処理を行う。【００２９】
PRGA(S)は、鍵ストーリームを生成する処理であり、状態Sに基づいて毎時刻、擬似乱数を生成する。【００３０】
ここで、 + はmod N上またはmod M上の算術加算を表し、N=2^{8}、M=2^{32}である。
また L は秘密鍵のバイト数を表している。【００３１】
まず、KSA(K,S)の動作を説明する。【００３２】
KSAでは、配列Sの初期値として、初期変数aiを代入し（S[i]=ai）、Sエントリどうしのswap（Swap［S［i］,S[j]］）と算術加算(S[ｉ]＝S[ｉ]＋S[ｊ]  mod M)を繰り返すことで、Sエントリを攪拌している。【００３３】
KSAにおいて、内部変数kもSエントリ（ｋ＝ｋ＋S[ｉ]  mod M）を使って初期化されるため、PRGAにおけるkの初期値は未知である。【００３４】
Sエントリの攪拌において、ループ回数rが可変であるが、Sエントリの出現確率がランダムになるように、m=32のときr=20を選択するよう定められている。G. Gongらによる提案では、m=64のときは、r=40を設定するよう定められている。【００３５】
KSA(K,S)が終了した直後でPRGA(S)が開始されていない状態を時刻ｔ＝０とする。時刻ｔ＝０のとき、KSA(K,S)の動作が終了し、秘密鍵Kによって配列Sの状態が十分攪拌されていることが期待されている。【００３６】
次に、PRGA(S)の動作を説明する。【００３７】
PRGAでは、インデックスi、jに基づく配列Sの参照結果（S[(S[i]+S[j])mod N]）と、変数kの算術加算を行って、1ワード（1ワード=32ビット）を鍵ストリーム(out=S[(S[i]+S[j]) mod N]+k) mod M)として出力する。また鍵ストリームを生成するために参照したSエントリ(S[(S[i]+S[j])mod N])を、鍵ストリーム出力直後にkを用いて更新している(S[(S[i]+S[j])mod N]=k+S[i] mod M)。図２における  out(=S[(S[i]+S[j])mod N]=k+S[i] mod M )が出力となる鍵ストリームである。【００３８】
図３では、時刻t＝１における動作（PRGAの状態遷移）を示している。配列Sにおいて、アドレス１の値S[1]がA、アドレスAの値S[A]がBの時に、アドレスA+Bの値S[A＋B]は、k0+A+Bになる。【００３９】
図４では、時刻t＝２における動作（PRGAの状態遷移）を示している。配列Sにおいて、アドレス１の値S[1]がA、アドレスAの値S[A]がB、アドレス２の値S[２]がC、アドレスA+Cの値S[A+C]がD、アドレスA+Bの値S[A+B]がk0+A+B、の時に、アドレスC+Dの値S[C+D]が、k0+B+C+Dになる。【００４０】
G. Gongらによって提案されたRC4型ストリーム暗号の安全性は、彼らの提案論文（非特許文献１）のなかでで報告されている。【００４１】
それによれば、鍵ストリームはSエントリに変数kを算術加算することでマスクされるため、KSAによってkが一様分布に従うとするならば出力系列に偏りが生じないことを示している。【００４２】
また内部メモリのサイズはRC4の4倍となり、Sエントリが算術加算によって更新されるため、内部メモリを求める攻撃に対しても安全性が向上していると報告されている。【００４３】
ただし、全てのS-boxエントリ(配列Sの要素)と変数kが同時に偶数になると、以降常に偶数が続くという「weak state」が存在する。しかし、内部メモリのサイズからみて、weak stateの存在確率は起こりえないくらいに十分小さいので、安全性に問題がないとされている。【００４４】
【非特許文献１】G. Gong, K.C. Gupta, M. Hell, and Y. Nawaz,“Towards a General RC4-Like Keystream Generator,”SKLOIS Conference on Information Security and Cryptology, CISC 2005,LNCS 3822, pp.162-174, Springer Verlag, 2005.
【非特許文献２】I. Mantin, and A. Shamir: "A Practical Attack on Broadcast RC4,"Fast Software Encryption, FSE 2001, LNCS 2355, pp.152-164,Springer-Verlag, 2001
【非特許文献３】S. Paul, B. Preneel, and G. Sekar: "Distinguishing Attacks on the StreamCipher Py," eSTREAM, the ECRYPT Stream Cipher Project, Report 2005/081,2005.
【発明の開示】
【発明が解決しようとする課題】
【００４５】
非特許文献１〜３の開示事項は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明によって与えられたものである。【００４６】
＜発明が対象とするGGHN(n,m)攻撃手法 Distinguishing Attackの説明＞
GGHN(8,32)を解析するにあたり、変数の表記や定義について説明する。【００４７】
・は、算術乗算を表す。
‖は、データの連結（concatenation）を表す。
X <<< nは、データXの左nビットローテイトを表す。
またlsb(X)はデータXの最下位ビット、LSB(X)はデータXの最下位バイトとし、
lsb(X) = X mod 2
LSB(X) = X mod 2^{8}
となる。
時刻tにおける変数i, j, kをit, jt, ktと表記する。
また時刻tにおけるx番目のS-boxエントリをSt[x]と表記する。
時刻tで出力される鍵ストリームをOtとし、最初の鍵ストリームを出力する時刻をt=1とする。【００４８】
ここで、PRGAの初期値をi0 = 0, j0 = 0と定義し、k0は未知となる。【００４９】
また解析を行う上で、攻撃者は鍵ストリームを自由に入手可能であるものとする。【００５０】
＜1番目の出力ワードと2番目の出力ワード間の偏り＞
まずGGHN(8,32)の1番目の出力ワードと2番目の出力ワード間に偏りが生じることを説明するため、以下の＜ケース１＞の条件が成り立つ場合について考察する。【００５１】
＜ケース１＞
1. LSB(S1[i1] + S1[j1]) = LSB(S1[i1])、ただし、LSB(S1[i1]) ≠ 1
2. LSB(S2[i2] + S2[j2]) = i2【００５２】
ケース１の時、t=1、2における配列Sの最下位バイトの状態遷移について図５及び図６に示す。図５には、配列Ｓにおいて、アドレス１の値S[1]がAであり、アドレスAの値S[A]がk0+Aであるべきところが０となり、矛盾することが示されている。図６には、配列Ｓにおいて、アドレス１の値S[1]がA、アドレスAの値S[A]がk0+A、アドレスA＋Cの値S[A+C]が2-C、アドレス２の値S[2]がk0+2であるべきところが、Cとなり、矛盾することが示されている。【００５３】
図２より、t=1のとき、i1=1であり、LSB(S1[i1]) = Aとおくと、j1 = Aとなる。【００５４】
ここで、ケース１の条件1を満たす時、
LSB(S1[1] + S1[A]) = LSB(S1[1])
LSB(S1[A]) = 0 ・・・  (1)
となるため、
LSB(k1) = LSB(k0 + S1[j1]) = LSB(k0)
となる。【００５５】
ただし、A = 1のとき、
LSB(S1[1] + S1[1]) = LSB(S1[1])
LSB(S1[1]) = 0 ≠ 1
となり、式(1)と矛盾するため、
LSB(S1[i1]) ≠ 1の条件が導かれる。【００５６】
t=1で出力される鍵ストリームにおいて以下の関係が成り立つ。
LSB(O1) = LSB(k0) ・・・  (2)【００５７】
同様にt=2のとき、i2=2であり、LSB(S2[i2]) = Cとおくと、j2 = A + Cとなる。【００５８】
ここで、ケース１の条件2を満たす時、
LSB(S2[2] + S2[A+C]) = 2
LSB(S2[A+C]) = 2 - C
となる。【００５９】
t=2で出力される鍵ストリームにおいて、以下の関係が成り立つ。
LSB(O2) = LSB(k0 + 2) ・・・  (3)【００６０】
よって、式(2)、(3)より、１番目と２番目の出力ワードO1、O2について以下の関係式が必ず成り立つ。【００６１】
lsb(O1) = lsb(O2) ・・・ (4)【００６２】
また、ケース２についても同様に考える。【００６３】
＜ケース２＞
1. LSB(S1[i1] + S1[j1]) = LSB(S1[i1])、ただし、LSB(S1[i1]) ≠ 1
2. LSB(S2[i2] + S2[j2]) = j2【００６４】
ケース２の場合、t=1、2における配列Sの最下位バイトの状態遷移について、図５及び図７に示す。図７には、アドレス１の値S[1]がA、アドレス２の値S[2]がC、アドレスAの値S[A]がk0+A、アドレスA＋Cの値S[A+C]がk0+A＋CであるべきところがAとなり、矛盾することが示されている。【００６５】
t=1における内部変数ｋはケース１と同じため、配列Sの状態遷移や鍵ストリームにおける関係式(2)も同じとなる。【００６６】
t=2のときケース２の条件2を満たす時、
LSB(S2[2] + S2[A+C]) = A + C
LSB(S2[A+C]) = A
となる。【００６７】
t=2で出力される鍵ストリームにおいて以下の関係が成り立つ。【００６８】
LSB(O2) = LSB(k0 + 2・S1[1]) ・・・  (5)【００６９】
よって、ケース２の条件1、2を満たす時も式(2)、(5)より、式(4)が必ず成り立つ。【００７０】
このように、ケース１、２ともに、１番目の出力ワードO1と２番目の出力ワードO2間で同じ関係式(4)が成り立つ。【００７１】
次に、この式がdistinguisherとして利用できることを説明する。【００７２】
＜Distinguisherが成り立つ確率と必要なデータ量＞
ここでは、distinguisherとして利用する式(4)の成立確率について説明する。【００７３】
もしGGHN(8,32)の出力する系列が真の乱数系列であれば、distinguisherである式(1)が成り立つ確率は2^{-1}となる。【００７４】
式(4)の成立確率は、PRGAの構造に依存したものであり、KSAの構造には依存しない。【００７５】
よって、以下の検討では、KSA終了後の変数kと配列Sがそれぞれ独立で一様分布に従うものとする。【００７６】
まず、ケース１、２の条件1、2が成り立つ確率p1、p2は以下のとおりである。ここで条件2が成り立つ確率p2はケース１、２を考慮した確率である。【００７７】
p1 = 1/256・255/256
p2 = 1/256・1/256 + 255/256・2/256【００７８】
ここで条件1、2のいずれかの条件を満たさない時、式(1)が成り立つ確率を、理想的に1/2と仮定すると、GGHN(8,32)の出力系列において、式(4)が成り立つ確率Pdは、以下で与えられる。【００７９】
pd = 1・p1・p2+1/2・(1-p1・p2)
≒  1/2・(1+2^{-15.01})【００８０】
よって、真の乱数系列における確率1/2と比べて大きくなる。【００８１】
次に、式(4)をdistinguisherとしたとき、GGHN(8,32)の出力系列と真の乱数系列を区別するために必要なデータ量を検討する。【００８２】
非特許文献２によると、2つの分布を区別するのに必要なデータ量は、以下のようになることが示されている。【００８３】
確率pで発生する事象分布Xと、確率p(q+1)で発生する事象分布Yにおいてあるイベントeが生じる時、無視できない成功確率でXとYを区別するには、O(1/pq^{2})のサンプルが必要である。【００８４】
ただし、上記定理は、p<<1のときに成り立つ。【００８５】
非特許文献３には、p=1/2のとき、2つの分布を区別するのに必要なデータ量は以下のようになることが示されている。【００８６】
確率p = 1/2で発生する事象分布Xと確率1/2(q+1)で発生する事象分布Yにおいてあるイベントeが生じる時、無視できない成功確率でXとYを区別するにはO(1/q^{2})のサンプルが必要である。【００８７】
本解読におけるイベントeは、式(4)が成り立つ事象であり、乱数におけるイベントeの分布をX、GGHN(8,32)の出力系列におけるイベントeの分布をYとみなすことができる。【００８８】
よって、p = 2^{-1}、q = 2^{-15.01}と考えることができるため、解読に必要なデータ量はO(2^{30.02)となる。【００８９】
ここで求まるデータ量は、GGHN(8,32)のKSAが完全にランダムなpermutationという仮定の元での値であり、PRGAの構造的な偏りから求まる理論的なデータ量である。【００９０】
よって、GGHN(8,32)は、理論的に約2^{30}の秘密鍵における鍵ストリームの先頭2ワードを利用することで、真の乱数列との区別が可能である。【００９１】
＜1番目の出力ワードと2番目の出力ワード間の偏り＞の説明（段落００５０から００７０）では、鍵ストリームの先頭2ワードについてdistinguisherの構成方法を説明したが、ケース１については任意の時刻tにおいて連続する鍵ストリーム2ワードについて同様の関係が成り立つ。【００９２】
よって、鍵ストリームの先頭数ワードを捨てるという対策は効果が無い。【００９３】
前述した＜発明が対象とするGGHN(n,m)攻撃手法 Distinguishing Attackの説明＞は、図５乃至図９に、まとめることができる。【００９４】
図９は、解読に必要なデータ量（理論値）をあらわしており、初期処理によってS-boxエントリが一様にランダムで出力均等と仮定した場合の、解読に必要なデータ量の理論値を求める流れを説明する図である。【００９５】
図９では、初期処理によってS-boxエントリが一様にランダムで出力均等と仮定している。これは、攻撃する時刻において、Sの値２５６通りがすべて出現する可能性があるということである。図９における、確率p1(=1/256)、確率p2(=255/256)は、図５における、条件１が発生する確率、と、条件２が発生する確率にそれぞれ対応する。また、図９における、確率p3 (=(1/256)・(1/256)+(255/256)(2/256)=512/2562)は、図７における条件３、または、図６における条件４が発生する確率に対応する。解読に必要なデータ量（理論値）は、O(q-2)=O(230.02)となる。【００９６】
図８に示すように、G. Gongら提案した改良アルゴリズムの  distinguisher を構成することが出来る。図８は、
lsb(O1) = lsb(O2)
の式を、distinguisherとすることを説明する図である。【００９７】
連続する出力の下位８bitは以下のようになる。
O1=k0
O2=k0＋2A   （条件３）、
O2＝k0+2    （条件４）【００９８】
よって、式(4)をdistinguisherとすれば、GGHN(8,32)の出力系列と真の乱数系列との区別が可能となる。【００９９】
本発明者等は、このことを、確めるための実験を行ったので、以下に説明する。図１０と図１１は、実験の結果をまとめたものである。図１０には、計算機実験によって得られた確率と解読に必要なデータ量が示されている。図１１には、計算機実験によって、与えるデータ量Nを変化させながら、図８のdistinguisherが機能するか確かめた結果が示されている。【０１００】
すなわち、図１１では、与えるデータ量Nを変化させながら、図８のdistinguisherについて成立回数Xを求めた。１００通りの秘密鍵について実験を行い棄却率を求めた。
X - 2^{N-1} > (1/2)・√( 2^{N-1} - 2^{N-2} )
を満たすとき、乱数でないと棄却する（乱数であれば30.5%となる）。以下に、該実験の説明をする。【０１０１】
＜実験結果の説明＞
式(4)をdistinguisherとしたとき、図９のように、GGHN(8,32)の出力系列と真の乱数系列が区別可能であるかどうか確認した。実験の手順は以下のとおりである。【０１０２】
1.   秘密鍵を2^{w}回ランダムに変更し、GGHN(8,32)の鍵ストリームをそれぞれ2ワード生成する。【０１０３】
2.   1. で生成した2^{w}個の鍵ストリームについて式(1)の成立回数をカウントする。【０１０４】
3.   2. でカウントされた回数xが以下の関係式を満たした時、出力系列が乱数でないと棄却する。ここでμは平均値、σは標準偏差を表す。【０１０５】
μ-x > σ/2【０１０６】
よって本実験においては、
2^{w-1}-x > 1/2・(2^{w-1}-2^{w-2})^{-1/2}
の関係式を満たした時、出力系列が乱数でないとして棄却する。【０１０７】
4.   1. で与えた2^{w}個の秘密鍵グループを独立に100通り与え、1〜3を繰り返し、棄却率を求める。【０１０８】
実験結果を表として示した図１１によると、2^{28}のデータを与えたとき、棄却率が85％となり、乱数における棄却率と比べて、50%以上のアドバンテージが得られた。【０１０９】
よって、式(4)を、distinguisherとしたときの攻撃手法によって、GGHN(8,32)の出力系列は、約2^{30}ワードの鍵ストリームを用いることによって、極めて高い確率で真の乱数列との区別が可能である事が実験的にも確認できた。【０１１０】
このように、従来のGGHN(8,32)の出力系列は、式(4)
{lsb(O1) = lsb(O2)}
を、distinguisherとしたときの攻撃手法によって、鍵ストリームが高い確率で真の乱数列との区別が可能であり、安全性が低いという課題がある。【０１１１】
本発明は、本発明者等による上記課題の認識に基づき創案されたものであって、その目的は、データを秘匿するための安全性の高い暗号装置、プログラム、方法を提供することにある。
【課題を解決するための手段】
【０１１２】
本願で開示される発明は、前記課題を解決するため、概略以下の構成とされる。【０１１３】
本発明は、上記課題となった解析手法に、耐性を持つ対策を提供する。また、対策の実装において、暗号の設計者らの主張する安全性と実装性を損なうことのないよう考慮している。【０１１４】
本発明の１つのアスペクト（側面）に係る暗号装置は、秘密鍵に基づき擬似乱数列を生成し、前記擬似乱数列を平文に作用させることにより暗号文を生成する暗号装置であって、前記擬似乱数列の生成に用いる内部状態として、有限個の数値の列の並び替えを基礎とする状態に基づく内部状態を用い、前記擬似乱数列の生成に用いる一時変数の少なくとも一つが、前記内部状態のうちの一つ、又は、複数個の数値を使用した、線形、又は、非線形、線形及び非線形の組み合わせの結果に基づき、内部状態の数より小さい数に依存し、あらかじめ定められた、左又は右ローテイトシフトを実行した結果を値とする一時変数であり、前記生成される擬似乱数を、前記内部状態のうちの１つ又は複数個の数値と、前記一時変数との演算によって生成する。【０１１５】
本発明において、前記有限個の数値の列の並び替えを基礎とする状態に基づく内部状態であって、前記内部状態の更新を、並び替え以外の、線形演算、及び、非線形演算を用いて行うようにしてもよい。【０１１６】
本発明において、前記有限個の数値の列の並び替えを基礎とする状態に基づく内部状態であって、前記内部状態の更新として、並び替え以外の、線形演算及び非線形演算を用いることにより、前記内部状態の状態数が、単調増加する、ようにしてもよい。あるいは、前記内部状態の状態数が、単調減少する、ようにしてもよい。【０１１７】
本発明において、前記有限個の数値の列の並び替えを基礎とする状態に基づく内部状態であって、前記内部状態の更新として、並び替え以外の線形演算及び非線形演算を用いることにより、内部状態の状態数を振動させる、ようにしてもよい。【０１１８】
本発明においては、前記内部状態の更新を、前記擬似乱数列の出力ごとに行うようにしてもよい。あるいは、前記擬似乱数列の出力よりも多く行うようにしてもよい。あるいは、前記擬似乱数列の出力よりも少なく行うようにしてもよい。【０１１９】
本発明においては、前記ローテイトシフトの方向及び／又は数値（シフト数）を、前記内部状態の数値に依存して動的に変更するようにしてもよい。【０１２０】
本発明においては、前記ローテイトシフトの方向及び数値（シフト数）を、あらかじめ定められたテーブルの値に従って変更するようにしてもよい。【０１２１】
本発明の別のアスペクトに係る装置は、配列Ｓの要素の並び替えと算術加算を繰り返すことで配列Ｓの要素を攪拌し配列Ｓの初期状態を作成し、その際、内部変数ｋの初期値を配列Ｓの要素から求める第１の処理部（KSA）と、第１、第２のインデックス変数ｉとｊに関して配列Ｓの要素Ｓ［ｊ］と内部変数ｋの加算結果をローテイトシフトした値で内部変数ｋの値を更新し、Ｓ［ｉ］＋Ｓ［ｊ］による配設Ｓの参照結果Ｓ［（Ｓ［ｉ］＋Ｓ［ｊ］）］と内部変数ｋとの加算結果に基づき、鍵ストリームを出力し、前記鍵ストリームを生成するために参照した配列Ｓの要素Ｓ［（Ｓ［ｉ］＋Ｓ［ｊ］）］を、鍵ストリーム出力の直後に内部変数ｋと配列要素Ｓ［ｉ］を用いて更新する第２の処理部（PRGA）と、を備えている。【０１２２】
本発明の別のアスペクトに係る装置は、配列Ｓの要素の並び替えと算術加算を繰り返すことで配列Ｓの要素を攪拌し配列Ｓの初期状態を作成し、その際、内部変数ｋの初期値を配列Ｓの要素から求める第１の処理部（KSA）と、第１のインデックス変数ｉの配列要素Ｓ［ｉ］を第１のシフト数ローテイトシフトした値と、第２のインデックス変数ｊとを算術加算した結果に基づき、第２のインデックス変数ｊの値を更新し、第２のインデックス変数ｊの配列要素Ｓ［ｊ］を第２のシフト数ローテイトシフトした値と内部変数ｋとの算術加算結果に基づき内部変数ｋの値を更新し、Ｓ［ｉ］＋Ｓ［ｊ］による配設要素Ｓ［（Ｓ［ｉ］＋Ｓ［ｊ］）］を第３のシフト数ローテイトシフトした値と内部変数ｋとの算術加算結果に基づき、鍵ストリームを出力し、前記鍵ストリームを生成するために参照した配列要素Ｓ［（Ｓ［ｉ］＋Ｓ［ｊ］）］を、鍵ストリーム出力の直後に内部変数ｋと配列要素Ｓ［ｉ］を用いて更新する第２の処理部（PRGA）と、を備えている。【０１２３】
本発明においては、初期設定配列ａを用い、配列ａの並べ替えを行って攪拌し、内部変数ｋを対応する配列要素ａをローテイトシフトしたものと算術加算して求め、配列Ｓを、配列ａの要素をローテイトシフトしたものと配列Ｓの要素との所定の演算によって求める第１の処理部（KSA）と、第１、第２のインデックス変数ｉ、ｊに関して配列Ｓの参照結果Ｓ［ｊ］と内部変数ｋとを算術加算し、Ｓ［ｉ］＋Ｓ［ｊ］による配設Ｓの参照結果と内部変数ｋに基づき、鍵ストリームを出力し、鍵ストリームを生成するために参照したＳのエントリを、鍵ストリーム出力直後に内部変数ｋを用いて更新する第２の処理部（PRGA）と、を備えた構成としてもよい。上記第１の処理部（KSA）と第２の処理部（PRGA）は、コンピュータ・プログラム（ソフトウェア）として実装してもよい。【０１２４】
また、本発明に係る方法においては、擬似乱数列の生成に用いる内部状態として、有限個の数値の列の並び替えを基礎とする状態に基づく内部状態を用い、前記擬似乱数列の生成に用いる一時変数の少なくとも一つを、前記内部状態のうちの一つ、又は、複数個の数値を用いた、線形、又は、非線形、線形及び非線形の組み合わせの結果に基づき、内部状態の数より小さい数に依存し、あらかじめ定められた、左又は右ローテイトシフトを実行した結果を値とする一時変数とし、前記擬似乱数を、前記内部状態のうちの１つ又は複数個の数値と、前記一時変数との予め定められた所定の演算によって生成する。本発明によれば、上記第１の処理部（KSA）と第２の処理部（PRGA）の各手順を含む方法が提供される。
【発明の効果】
【０１２５】
本発明によれば、GGHN(n,m)におけるdistinguisherの構成を困難とし、GGHN(n,m)がもつ、速度性能の低下を回避することができる。このため、本発明は、データの通信や蓄積の際にデータを秘匿するための安全性の高い暗号装置を提供することができる。
【図面の簡単な説明】
【０１２６】
【図１】本発明の一実施形態を示すブロック図である。
【図２】32bit RC4 (CISC 2005)で提案されたRC4の改良アルゴリズムを示す図である。
【図３】PRGAの状態遷移 (1)を示す図である。
【図４】PRGAの状態遷移 (2)を示す図である。
【図５】PRGAの解析 (1)を示す図である。
【図６】PRGAの解析 (3)を示す図である。
【図７】PRGAの解析 (2)を示す図である。
【図８】PRGAの解析 (4)を示す図である。
【図９】解読に必要なデータ量（理論値）を示す図である。
【図１０】解読に必要なデータ量（実験値）を示す図である。
【図１１】実験結果 (distinguisher)を示す図である。
【図１２】G. Gong  らによってしめされたストリーム暗号のアルゴリズムを示す図である。
【図１３】本発明の変更アルゴリズムを示す図である。
【図１４】解決しようとする課題の具体例１を示す図である。
【図１５】解決しようとする課題の具体例２を示す図である。
【図１６】対策案 (1)を示す図である。
【図１７】対策案 (2)を示す図である。
【発明を実施するための最良の形態】
【０１２７】
上記した本発明についてさらに詳細に説明する。図１３は、本発明の変更アルゴリズムを説明するための図である。図１３には、本発明において、元のアルゴリズムの変更すべき箇所が示されている。【０１２８】
上記課題となった解析手法は、PRGAの構造的な脆弱性を利用したものである。【０１２９】
しかも、解析手法では、KSAによって全ての内部記憶が一様分布に従うとみなしていた。【０１３０】
よって、本発明の１つの側面においては、KSAに変更は施さず、PRGAのみ改良をおこなった。【０１３１】
図１３に示す対策手段におけるアルゴリズムの変更（図２のPRGAのアルゴリズムからの変更）は、変数kの更新の際に、左ローテイト処理  k=((k+S[j])<<<n) mod M
を行っている点である（ただし、N＝2^{n}、M＝2^{m}）。【０１３２】
ローテイト数は、GGHN(n,m)としたとき、nビットとする。【０１３３】
本発明によれば、擬似乱数列の生成に用いる一時変数の少なくとも一つである内部変数ｋを、前記内部状態のうちの一つ又は、複数個の数値を使用した、線形、又は、非線形、線形及び非線形の組み合わせの結果に基づき、ｎビットローテイトシフト（（ｋ＋S[j]）<<<ｎ）を実行した結果とし、前記生成される擬似乱数を、前記内部状態のうちの１つ又は複数個の数値と、前記一時変数との演算によって生成する（out＝(S[(S(i)+S[j]) mod N] +k ) mod M）。【０１３４】
ここで、本発明による対策手段の効果を説明するため、ケース１における内部変数k0とS1[A]、S2[A+C]をバイト単位の変数を用いて以下のように表現する。【０１３５】
ここで、右側が下位ビットであり、LSB(k0) = k00である。
ただし、式(1)より、LSB(S1[A]) = B0 = 0である。【０１３６】
k0 = k03‖k02‖k01‖k00
S1[A] = B3‖B2‖B1‖B0
S2[A+C] = A3‖A2‖A1‖A0【０１３７】
このとき、算術加算で生じるバイトを跨ぐ桁あがりの影響を無視すると、図１３に示したPRGAは、最下位バイトにおいて、一様分布に従う独立な変数が必ず２個以上挿入されるため、式(1)に、偏りが生じなくなる。【０１３８】
同様に、どのバイト間で比較しても、一様な分布に従う独立な変数が必ず２個以上挿入されることから、偏りは生じないと考えられる。【０１３９】
実際には、桁上がりがバイトを超えて影響するが、基本的な考え方に影響は無い。【０１４０】
また、図１３の対策手段における実装性を考慮すると、処理の増加は、ローテイト処理1回分である。【０１４１】
図１３の比較例として、元のアルゴリズムを図１２に示す。変数kの更新は、
k=(k+S[j]) mod M
にて行っている。【０１４２】
また、本発明において、実装ターゲットとして、32ビット／64ビットプロセッサ上でのソフトウェアの実装を想定した場合、nビットの左ローテイト処理は速度の劣化が小さいものと思料される。【０１４３】
また、本発明によれば、新たな内部メモリを用いることなく、改良が可能であるため、メモリの増加も無い。【０１４４】
よって、本発明による、図１３の対策手段は、
・設計者らの設計方針を崩すことなく、
・実装性の利点を損なうこともない、
暗号モデルを実現できるものと期待される。【０１４５】
次に、図１６に、本発明による、KSA(K, S)の変更による対策手段の例を示す。a[i]を左8xrビットローテイトしたものと変数kとを算術加算した値で、変数kを更新している。S[i]と、a[i]を左8x(3-r)ビットローテイトしたものとの演算結果（排他的論理和演算）にて、S[i]を更新している。【０１４６】
図１６の、KSA(K, S)の変更による対策手段でも、S-boxはある程度、ランダムになることが実験により確認できており、かつ、各バイトで見たとき出力均等となる。【０１４７】
そして、KSAの速度は、約2.5倍高速（RC4のKSAと比べて約8倍低速）となり、初期値テーブルを使用しないので、例えば1Kbyteのメモリを削減することができる。【０１４８】
なお、図１６の対策手段は、ローテイトシフトの方向及び／又はシフト数を、前記内部状態の数値に依存して動的に変更することに対応する。ローテイトシフトの方向及びシフト数を、あらかじめ定められたテーブルの値に従って変更するようにしてもよい。【０１４９】
図１７に、PRGA(S)の変更による対策手段の別の例を示した。S[i]を右24ビットローテイトシフトしたもの（S[i]>>>24）とｊとの算術加算結果でｊの値を更新し、S[j]を右16ビットローテイトシフトしたもの（S[j]>>>16）とｋとの算術加算結果でｋの値を更新し、S[(S[i]+S[j]) mod N]を右８ビットローテイトしたものとｋとの算術加算結果をoutとしている。【０１５０】
この対策手段の場合、鍵ストリーム間の関係（１番目と２番目の出力バイトＯ１とＯ２）が、
O1 = k0 + XO2 = k0 + Y
となり、Xの値に応じて、Yの値が決定する関係となる。【０１５１】
よって、インデックスの仮定で参照されるS-boxエントリを選択できたとしても。仮定で用いたインデックス情報を、上記の関係式に持ち込めない（X, Yの情報によらない恒等式に持ち込めない）ため、Distinguishing Attackの適用が困難になる。【０１５２】
なお、本発明において、前記有限個の数値の列の並び替えを基礎とする状態に基づく内部状態であって、前記内部状態の更新を、並び替え以外の、線形演算、及び、非線形演算を用いて行うようにしてもよい。【０１５３】
本発明において、前記有限個の数値の列の並び替えを基礎とする状態に基づく内部状態であって、前記内部状態の更新として、列の並び替え以外の、線形演算及び非線形演算を用いることにより、前記内部状態の状態数を、単調増加させるようにしてもよい。あるいは、前記内部状態の更新として、列の並び替え以外の、線形演算及び非線形演算を用いることにより、前記内部状態の状態数を、単調減少させるようにしてもよい。【０１５４】
本発明において、前記有限個の数値の列の並び替えを基礎とする状態に基づく内部状態であって、前記内部状態の更新として、並び替え以外の線形演算及び非線形演算を用いることにより、内部状態の状態数を振動させる、ようにしてもよい。【０１５５】
本発明においては、前記内部状態の更新を、前記擬似乱数列の出力ごとに行うようにしてもよい。あるいは、前記擬似乱数列の出力よりも多く行うようにしてもよい。あるいは、前記擬似乱数列の出力よりも少なく行うようにしてもよい。以下実施例に即して説明する。
【実施例】
【０１５６】
図１は、本発明の一実施例を説明するための図である。図１４、図１５は、比較例として、本発明が解決しようとする課題の具体例１、２を示すブロック図である。以下、本発明の一実施例を説明する。図１に示すように、<<<nの処理では、ｋ（0）に対して、左ローテイト処理（k+S[j]）<<<nを行ってｋ(1)としている。（S[(S[i]+S[j]） mod N]+k(1)）mod Mをout(1)としている。【０１５７】
図１４は、本発明が解決しようとする課題の具体例１として、図５から図７（ケース２の条件でのt=1、2における配列Sの最下位バイトの状態遷移）への処理の過程を示した図である。状態変化は、Sの箱で示されており、図には表れていない。はじめに、図１４の比較例を参照して説明する（アルゴリズムは図１２に示される)。【０１５８】
時刻１において、インデックスｉが１となる（j(0)の矢印の先の箱から出力される１参照）。インデックスｉ(0)と１を入力する十字ボックスは、算術加算を表しており、ｉ＝（ｉ＋１）  mod N＝１を出力する。【０１５９】
アドレスｉの値S［1］（下位８ビット）がＡであり、インデックスｊがＡとなる。なお、図１、図１４、図１５において、Sを四角で囲むボックスはS−boxであり、例えばインデックス（例えば１）を入力し、S[１]がAの場合、ボックスからは、Aが出力される図式とされる。j(0)とAを入力とするボックス（算術加算器）は、j(0)=（j(0)+A） mod N＝Aを出力している。【０１６０】
アドレスｊの値S[ｊ]（下位８ビット）が０であり、
変数ｋの値（下位８ビット）は
０＋ｋ０＝ｋ０
となる。【０１６１】
アドレスｉの値S[ｉ]（下位８ビット）がＡであり、アドレスｊの値S[ｊ]（下位８ビット）が０であるため、出力Ｏ１を生成するために必要なアドレスは、
Ｓ［ｉ］＋Ｓ［ｊ］＝Ａ＋０＝Ａ
となる。【０１６２】
アドレスＡの値S[A]（下位８ビット）が０であり、変数ｋの値（下位８ビット）がｋ０であるため、出力Ｏ１の値（下位８ビット）は、
０＋ｋ０＝ｋ０
となる。【０１６３】
出力Ｏ１を生成した後、アドレスＡの値S[A]（下位８ビット）は、
ｋ０＋Ａ
に更新される。【０１６４】
時刻２において、インデックスｉは２となる。【０１６５】
アドレスｉの値S[i]（下位８ビット）がＣであり、インデックスｊは、Ａ＋Ｃとなる。【０１６６】
アドレスｊの値S[ｊ]（下位８ビット）がＡであり、変数ｋの値（下位８ビット）は、
ｋ０＋Ａ
となる。【０１６７】
アドレスｉの値S[i]（下位８ビット）がＣであり、アドレスｊの値S[ｊ]（下位８ビット）がＡであるため、出力Ｏ２を生成するために必要なアドレスは、
Ｓ［ｉ］＋Ｓ［ｊ］＝Ａ＋Ｃ
となる。【０１６８】
アドレスＡ＋Ｃの値S[A+C]（下位８ビット）がＡであり、変数ｋの値（下位８ビット）がｋ０＋Ａであるため、出力Ｏ２の値（下位８ビット）は、
Ａ＋ｋ０＋Ａ＝ｋ０＋２Ａ
となる。【０１６９】
出力Ｏ２を生成した後、アドレスＡ＋Ｃの値S[A+C]（下位８ビット）は、
ｋ０＋Ａ＋Ｃ
に更新される。【０１７０】
図１５は、図１の比較例として、本発明が解決しようとする課題の具体例２を示す図であり、図５から図６（ケース１の条件でのt=1、2における配列Sの最下位バイトの状態遷移）への処理の過程を示した図である。状態変化はSの箱で示されており、図には表れていない。【０１７１】
図１５を参照すると、時刻１において、インデックスｉが１となる。【０１７２】
アドレスｉの値S[i]（下位８ビット）がＡであり、インデックスｊがＡとなる。【０１７３】
アドレスｊの値S[ｊ]（下位８ビット）が０であり、変数ｋの値（下位８ビット）は、    ０＋ｋ０＝ｋ０
となる。【０１７４】
アドレスｉの値S[i]（下位８ビット）がＡであり、アドレスｊの値S[ｊ]（下位８ビット）が０であるため、出力Ｏ１を生成するために必要なアドレスは、
Ｓ［ｉ］＋Ｓ［ｊ］＝Ａ＋０＝Ａとなる。【０１７５】
アドレスＡの値S[A]（下位８ビット）が０であり、変数ｋの値（下位８ビット）がｋ０であるため、出力Ｏ１の値（下位８ビット）は、
０＋ｋ０＝ｋ０
となる。【０１７６】
出力Ｏ１を生成した後、アドレスＡの値S[A]（下位８ビット）は、
ｋ０＋Ａ
に更新される。【０１７７】
時刻２において、インデックスｉは２となる。【０１７８】
アドレスｉの値S[i]（下位８ビット）がＣであり、インデックスｊはＡ＋Ｃとなる。【０１７９】
アドレスｊの値S[ｊ]（下位８ビット）が２−Ｃであり、変数ｋの値（下位８ビット）は、
ｋ０＋２−Ｃ
となる。【０１８０】
アドレスｉの値S[i]（下位８ビット）がＣであり、アドレスｊの値S[ｊ]（下位８ビット）が２−Ｃであるため、出力Ｏ２を生成するために必要なアドレスは、
Ｓ［ｉ］＋Ｓ［ｊ］＝Ｃ＋２−Ｃ＝２
となる。【０１８１】
アドレス２の値S[２]（下位８ビット）がＣであり、変数ｋの値（下位８ビット）がｋ０＋２−Ｃであるため、出力Ｏ２の値（下位８ビット）は、
Ｃ＋ｋ０＋２−Ｃ＝ｋ０＋２
となる。【０１８２】
出力Ｏ２を生成した後、アドレス２の値S[２]（下位８ビット）は、
ｋ０＋２−Ｃ＋Ｃ＝ｋ０＋２
に更新される。【０１８３】
図１４、図１５の比較例と相違して、本発明の一の実施例では、図１に示すように、処理の過程にローテイトシフト（<<<n）が追加されている。k(0)=ローテイトシフト（<<<n）は、((k+S[j])<<<n) mod M【０１８４】
本実施例においても、図１４と同様、時刻１において、インデックスｉが１となる。アドレスｉの値S[i]（下位８ビット）がＡであり、インデックスｊがＡの下位８ビットとなる。【０１８５】
アドレスｊの値S[j]（下位８ビット）がＢ（下位８ビットが０）であり、変数ｋの値はＲｏｌｎ（ｋ０＋Ｂ）となる。なお、Ｒｏｌｎは、Rotate-Left-Shift by n-bitを表している。すなわち、Ｒｏｌｎ（ｋ０＋Ｂ）は、図１３のｋ＝（（ｋ＋S[j]<<<n） mod Mに対応し、ｋ０＝（（ｋ０＋Ｂ）<<<n）mod Mが実行される。【０１８６】
アドレスｉの値S[i]（下位８ビット）がＡであり、アドレスｊの値S[j]がＢ（下位８ビットが０）であるため、出力Ｏ１を生成するために必要なアドレスは、
Ｓ［ｉ］＋Ｓ［ｊ］＝Ａ＋０＝Ａ
となる。【０１８７】
アドレスＡの値S[A]がＢ（下位８ビットが０）であり、変数ｋの値がＲｏｌｎ（ｋ０＋Ｂ）であるため、出力Ｏ１の値（下位８ビット）は、
０＋Ｒｏｌｎ（ｋ０＋Ｂ）＝Ｒｏｌｎ（ｋ０＋Ｂ）
となる。【０１８８】
出力Ｏ１を生成した後、アドレスＡの値S[A]（下位８ビット）は、
Ｒｏｌｎ（ｋ０＋Ｂ）＋Ａ
に更新される。【０１８９】
時刻２において、インデックスｉは２となる。【０１９０】
アドレスｉの値S[ｉ]（下位８ビット）がＣであり、インデックスｊはＡ＋Ｃの下位８ビットとなる。【０１９１】
アドレスｊの値S[ｊ]（下位８ビット）がＡであり、変数ｋの値は、
Ｒｏｌｎ（Ｒｏｌｎ（ｋ０＋Ｂ）＋Ａ）
となる。【０１９２】
アドレスｉの値S[ｉ]（下位８ビット）がＣであり、アドレスｊの値S[ｊ]（下位８ビット）がＡであるため、出力Ｏ２を生成するために必要なアドレスは、
Ｓ［ｉ］＋Ｓ［ｊ］＝Ａ＋Ｃ
となる。【０１９３】
アドレスＡ＋Ｃの値S[A+C]（下位８ビット）がＡであり、変数ｋの値がＲｏｌｎ（Ｒｏｌｎ（ｋ０＋Ｂ）＋Ａ）であるため、出力Ｏ２の値（下位８ビット）は、
Ａ＋Ｒｏｌｎ（Ｒｏｌｎ（ｋ０＋Ｂ）＋Ａ）
となる。【０１９４】
出力Ｏ２を生成した後、アドレスＡ＋Ｃの値S[A+C]（下位８ビット）は、
Ｒｏｌｎ（Ｒｏｌｎ（ｋ０＋Ｂ）＋Ａ）＋Ｃ
に更新される。【０１９５】
次に、図１の本実施例において、図１５に基づくと、時刻１において、インデックスｉが１となる。【０１９６】
アドレスｉの値S[ｉ]（下位８ビット）はＡであり、インデックスｊはＡの下位８ビットとなる。【０１９７】
アドレスｊの値S[ｊ]（下位８ビット）はＢ（下位８ビットが０）であり、変数ｋの値は、
Ｒｏｌｎ（ｋ０＋Ｂ）
となる。【０１９８】
アドレスｉの値S[ｉ]がＡであり、アドレスｊの値S[ｊ]がＢ（下位８ビットが０）であるため、出力Ｏ１を生成するために必要なアドレスは、
Ｓ［ｉ］＋Ｓ［ｊ］＝Ａ＋０＝Ａ
となる。【０１９９】
アドレスＡの値S[A]（下位８ビット）がＢ（下位８ビットが０）であり、変数ｋの値がＲｏｌｎ（ｋ０＋Ｂ）であるため、出力Ｏ１の値（下位８ビット）は、
０＋Ｒｏｌｎ（ｋ０＋Ｂ）＝Ｒｏｌｎ（ｋ０＋Ｂ）
となる。【０２００】
出力Ｏ１を生成した後、アドレスＡの値S[A]（下位８ビット）は、
Ｒｏｌｎ（ｋ０＋Ｂ）＋Ａ
に更新される。【０２０１】
時刻２において、インデックスｉは２となる。【０２０２】
アドレスｉの値S[ｉ]（下位８ビット）がＣであり、インデックスｊは、Ａ＋Ｃの下位８ビットとなる。【０２０３】
アドレスｊの値S[ｊ]（下位８ビット）が２−Ｃであり、変数ｋの値は、
Ｒｏｌｎ（Ｒｏｌｎ（ｋ０＋Ｂ）＋２−Ｃ）
となる。【０２０４】
アドレスｉの値S[ｉ]がＣであり、アドレスｊの値S[ｊ]が２−Ｃであるため、出力Ｏ２を生成するために必要なアドレスは、
Ｓ［ｉ］＋Ｓ［ｊ］＝Ｃ＋２−Ｃ＝２
となる。【０２０５】
アドレス２の値S[2]（下位８ビット）がＣであり、変数ｋの値が、
Ｒｏｌｎ（Ｒｏｌｎ（ｋ０＋Ｂ）＋２−Ｃ）
であるため、出力Ｏ２の値（下位８ビット）は、
Ｃ＋Ｒｏｌｎ（Ｒｏｌｎ（ｋ０＋Ｂ）＋２−Ｃ）
となる。【０２０６】
出力Ｏ２を生成した後、アドレス２の値S[2]（下位８ビット）は、
Ｒｏｌｎ（Ｒｏｌｎ（ｋ０＋Ｂ）＋２−Ｃ）＋Ｃ
に更新される。【０２０７】
本発明によれば、データの通信や蓄積の際にデータを秘匿するための安全性の高い暗号装置を得ることができる。【０２０８】
なお、図１３、図１６、図１７を参照して説明した本発明に係るプログラムは、鍵ストリームを生成する任意のアプリケーションに適用いることができる。本発明に係る暗号装置は、例えばサーバ装置のCPU、記憶装置、ネットワーク等を含む構成とされる。秘密鍵情報は、サーバ装置の記憶装置に記憶される。図１に示した構成において、ローテイトシフト演算は、CPUのALU（演算装置）で行われる。【０２０９】
以上、本発明を上記実施例に即して説明したが、本発明は上記実施例の構成にのみ制限されるものでなく、本発明の範囲内で当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【図１】
2008010441.tif 000003
【図２】
2008010441.tif 000004
【図３】
2008010441.tif 000005
【図４】
2008010441.tif 000006
【図５】
2008010441.tif 000007
【図６】
2008010441.tif 000008
【図７】
2008010441.tif 000009
【図８】
2008010441.tif 000010
【図９】
2008010441.tif 000011
【図１０】
2008010441.tif 000012
【図１１】
2008010441.tif 000013
【図１２】
2008010441.tif 000014
【図１３】
2008010441.tif 000015
【図１４】
2008010441.tif 000016
【図１５】
2008010441.tif 000017
【図１６】
2008010441.tif 000018
【図１７】
2008010441.tif 000019
【国際調査報告】
2008010441.tif 000020
2008010441.tif 000021
2008010441.tif 000022
2008010441.tif 000023