(57)【特許請求の範囲】
【請求項１】
複数バイトからなるワード単位で、擬似乱数を生成する擬似乱数生成装置において、
鍵情報を記憶する鍵メモリと、
複数のワードからなり、アドレスＩ（Ｉは、０以上の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１と、
第１メモリＳ１と同一数の複数のワードから構成されるメモリであって、アドレスＩを用いて、
ワードＳ２［Ｉ］をアクセスする第２メモリＳ２と、
第１メモリＳ１と第２メモリＳ２との各ワードにそれぞれワード値を設定するとともに、第１内部メモリと第２内部メモリとに初期値を設定する初期化部と、
鍵メモリが記憶する鍵情報を用いて、第１メモリＳ１と第２メモリＳ２とに設定されたワードの値に対して鍵スケジューリングをして第１メモリＳ１と第２メモリＳ２とに記憶する鍵スケジュール部と、
鍵スケジュール部により鍵スケジュールされた第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成するストリーム生成部と
を備えたことを特徴とする擬似乱数生成装置。
【請求項２】
前記ストリーム生成部は、
第１メモリＳ１のワードの値から、第１メモリＳ１のアドレスを生成し、生成されたアドレスの第１メモリＳ１のワードの値から擬似乱数を生成する第１乱数生成部と、
第２メモリＳ２のワードの値から、第２メモリＳ２のアドレスを生成し、生成されたアドレスの第２メモリＳ２のワードの値から擬似乱数を生成する第２乱数生成部と、
を備えたことを特徴とする請求項１記載の擬似乱数生成装置。
【請求項３】
数バイトからなるワード単位で、擬似乱数を生成する擬似乱数生成装置において、
鍵スケジュールされた値を記憶する複数のワードからなり、アドレスＩ（Ｉは、０以上の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１と、
第１メモリＳ１と同一数の複数のワードから構成されるメモリであって、鍵スケジュールされた値を記憶する複数のワードからなり、アドレスＩを用いて、ワードＳ２［Ｉ］をアクセスする第２メモリＳ２と、
第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成するストリーム生成部と
を備えたことを特徴とする擬似乱数生成装置。
【請求項４】
ｎ（１≦ｎ≦Ｎ、Ｎは１以上の整数）バイトからなるワード単位で、擬似乱数を生成する擬似乱数生成装置において、
生成すべき乱数のストリーム長Ｌを記憶するストリーム長メモリと、
固定値を記憶する固定値メモリと、
鍵情報を記憶する鍵メモリと、
初期値を入力して記憶する初期値メモリと、
２５６ワードから構成されるメモリであって、アドレスＩ（Ｉは、０〜２５５の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１と、
第１メモリＳ１と同一数の複数のワードから構成されるメモリであって、アドレスＩを用いて、ワードＳ２［Ｉ］をアクセスする第２メモリＳ２と、
アドレスＩとなる値を記憶する第１内部メモリと、
ワード単位の値を記憶する第２内部メモリと、
鍵メモリが記憶する鍵情報と初期値メモリが記憶する初期値とを用いて第１内部メモリの値Ｉを更新し、第１内部メモリの値をアドレスＩとして、第１メモリＳ１の先頭ワードから最後のワードまでの各ワードのｎ番目のバイトの値と第１メモリＳ１のアドレスＩのワードＳ１［Ｉ］のｎ番目のバイトの値とをスワップし、さらに、第１内部メモリの値をアドレスＩとして、第２メモリＳ２の先頭ワードから最後のワードまでの各ワードのｎ番目のバイトの値と第２メモリＳ２のアドレスＩのワードＳ２［Ｉ］のｎ番目のバイトの値とをスワップして、第１から第Ｎ番目のバイトまでスワップを繰り返し、第１メモリＳ１と第２メモリＳ２とに記憶されたワードに対して鍵スケジューリングをする鍵スケジュール部と、
鍵スケジュール部により鍵スケジュールされた第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成するストリーム生成部と
を備えたことを特徴とする擬似乱数生成装置。
【請求項５】
ｎ（１≦ｎ≦Ｎ、Ｎは１以上の整数）バイトからなるワード単位で、擬似乱数を生成する擬似乱数生成装置において、
生成すべき乱数のストリーム長Ｌを記憶するストリーム長メモリと、
固定値を記憶する固定値メモリと、
鍵情報を記憶する鍵メモリと、
初期値を入力して記憶する初期値メモリと、
２５６ワードから構成されるメモリであって、アドレスＩ（Ｉは、０〜２５５の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１と、
第１メモリＳ１と同一数の複数のワードから構成されるメモリであって、アドレスＩを用いて、ワードＳ２［Ｉ］をアクセスする第２メモリＳ２と、
アドレスＩとなる値を記憶する第１内部メモリと、
ワード単位の値を記憶する第２内部メモリと、
固定値メモリに記憶された固定値を用いて、第１メモリＳ１と第２メモリＳ２との各ワードにそれぞれワード値を設定するとともに、第１内部メモリと第２内部メモリとに初期値を設定する初期化部と、
鍵メモリが記憶する鍵情報と初期値メモリが記憶する初期値とを用いて第１内部メモリの値Ｉを更新し、第１内部メモリの値をアドレスＩとして、第１メモリＳ１の先頭ワードから最後のワードまでの各ワードのｎ番目のバイトの値と第１メモリＳ１のアドレスＩのワードＳ１［Ｉ］のｎ番目のバイトの値とをスワップし、さらに、第１内部メモリの値をアドレスＩとして、第２メモリＳ２の先頭ワードから最後のワードまでの各ワードのｎ番目のバイトの値と第２メモリＳ２のアドレスＩのワードＳ２［Ｉ］のｎ番目のバイトの値とをスワップして、第１から第Ｎ番目のバイトまでスワップを繰り返し、第１メモリＳ１と第２メモリＳ２とに記憶されたワードに対して鍵スケジューリングをする鍵スケジュール部と、
第２内部メモリに記憶されたワードの下位２バイトの値からアドレスＩ２、Ｉ３の値を生成し、
第１メモリＳ１の先頭ワードから最後のワードまでの各ワードＳ１［Ｉ１］の値と
第１メモリＳ１のアドレスＩ２のワードＳ１［Ｉ２］の値と
第２メモリＳ２のアドレスＩ３のワードＳ２［Ｉ３］の値と
を用いて擬似乱数Ｒ１を生成してバッファメモリに出力する第１乱数生成部と、
第１メモリＳ１のアドレスＩ２のワードＳ１［Ｉ２］の値と
第２メモリＳ２のアドレスＩ３のワードＳ２［Ｉ３］の値と
を演算してシフトし、シフトした値を用いて第１メモリＳ１のアドレスＩ１のワードＳ１［Ｉ１］の値を書き換える第１状態変更部と、
第２内部メモリに記憶されたワードの上位と下位の値を入れ替える第１入れ替え部と、
第２内部メモリに記憶されたワードの下位２バイトの値からアドレスＩ４、Ｉ５とする値を生成し、
第２メモリＳ２の先頭ワードから最後のワードまでの各ワードＳ２［Ｉ１］の値と
第２メモリＳ２のアドレスＩ４のワードＳ２［Ｉ４］の値と
第１メモリＳ１のアドレスＩ５のワードＳ１［Ｉ５］の値と
を用いて擬似乱数Ｒ２を生成して出力する第２乱数生成部と、
第２メモリＳ２のアドレスＩ４のワードＳ２［Ｉ４］の値と
第１メモリＳ１のアドレスＩ５のワードＳ１［Ｉ５］の値と
を演算してシフトし、シフトした値を用いて、第２メモリＳ２のアドレスＩ１のワードＳ２［Ｉ１］の値を書き換える第２状態変更部と、
第２内部メモリに記憶されたワードの上位と下位の値を入れ替える第２入れ替え部と、
ストリーム長メモリに記憶したストリーム長になるまで、第１乱数生成部と第１状態変更部と第１入れ替え部の動作と、第２乱数生成部と第２状態変更部と第２入れ替え部の動作とを繰り返すループ部と、
第１乱数生成部から出力される擬似乱数Ｒ１と第２乱数生成部から出力される擬似乱数Ｒ２とを入力して一時的に保持して擬似乱数ストリームとして出力するバッファメモリと、
バッファメモリに出力した擬似乱数のストリーム長が、所定の再スケジュール長になった場合に、鍵スケジュール部を動作させる再スケジュール部と
を備えたことを特徴とする擬似乱数生成装置。
【請求項６】
鍵情報を記憶する鍵メモリと、複数のワードからなり、アドレスＩ（Ｉは、０以上の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１と、第１メモリＳ１と同一数の複数のワードから構成されるメモリであって、アドレスＩを用いて、ワードＳ２［Ｉ］をアクセスする第２メモリＳ２とを備えるとともに複数バイトからなるワード単位で、擬似乱数を生成するコンピュータである擬似乱数生成装置が行う擬似乱数生成方法において、
初期化部が、第１メモリＳ１と第２メモリＳ２との各ワードにそれぞれワード値を設定するとともに、第１内部メモリと第２内部メモリとに初期値を設定し、
鍵スケジュール部が、鍵メモリが記憶する鍵情報を用いて、第１メモリＳ１と第２メモリＳ２とに設定されたワードの値に対して鍵スケジューリングをして第１メモリＳ１と第２メモリＳ２とに記憶し、
ストリーム生成部が、鍵スケジュールされた第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成する
ことを特徴とする擬似乱数生成方法。
【請求項７】
鍵情報を記憶する鍵メモリと、複数のワードからなり、アドレスＩ（Ｉは、０以上の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１と、第１メモリＳ１と同一数の複数のワードから構成されるメモリであって、アドレスＩを用いて、ワードＳ２［Ｉ］をアクセスする第２メモリＳ２とを備えるとともに複数バイトからなるワード単位で、擬似乱数を生成するコンピュータである擬似乱数生成装置に以下の処理を実行させる擬似乱数生成プログラム
（１）第１メモリＳ１と第２メモリＳ２との各ワードにそれぞれワード値を設定するとともに、第１内部メモリと第２内部メモリとに初期値を設定する処理
（２）鍵メモリが記憶する鍵情報を用いて、第１メモリＳ１と第２メモリＳ２とに設定されたワードの値に対して鍵スケジューリングをして第１メモリＳ１と第２メモリＳ２とに記憶する処理
（３）鍵スケジュールされた第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成する処理
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、擬似乱数を生成する擬似乱数生成装置及び擬似乱数生成方法及び擬似乱数生成プログラムに関する。
【背景技術】
【０００２】
ソフトウェア向きストリーム暗号の代表的な従来技術としてＲＣ４が挙げられる。このＲＣ４のアルゴリズムは公式には公開されていない。しかし、現在ではＲＣ４の解析を行なった文献が多数存在し、方式の詳細も公開されている（例えば、非特許文献１）。【０００３】
図２４は、ＲＣ４のアルゴリズムを示している。このアルゴリズムは、「Ａ．初期化」と、「Ｂ．鍵スケジュール」と、「Ｃ．ストリーム生成」とから成る。図２４の例えば鍵スケジュールにおける「％２５６」は、２５６で除した余りを示す。
また、
「ｓｗａｐ（Ｓ［Ｉ］，Ｓ［Ｂ］）」
は、Ｓ［Ｉ］とＳ［Ｂ］との入れ替えを意味する。
また、図２５は、図２４に示した「Ａ初期化」、「Ｂ鍵スケジュール」、「Ｃストリーム」のそれぞれを図式化したものである。
図２４、図２５に示す様に、このアルゴリズムは、
「Ａ．初期化」として内部テーブルを生成し、
「Ｂ．鍵スケジュール」として生成した内部テーブルのデータをｓｗａｐし、
「Ｃ．ストリーム生成」として内部テーブルを使用して擬似乱数を生成する。【０００４】
従来技術では、ストリーム生成を１バイト単位で行なっているため、処理速度が高速とはいい難く、高速化の要請がある。また、従来技術では一つの内部テーブルから擬似乱数を生成しており、解読攻撃に対する更なる安全性の要請もある。
【非特許文献１】出典：Ａｐｐｌｉｅｄ  Ｃｒｙｐｔｏｇｒａｐｈｙ，  Ｂｒｕｃｅ  Ｓｃｈｎｅｉｅｒ著，  Ｊｏｈｎ  Ｗｉｌｅｙ  ＆  Ｓｏｎｓ，  ＩＳＢＮ  ０−４７１−１１７０９−９
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明は、ストリーム暗号方式において動作の高速な擬似乱数生成装置及び擬似乱数生成方法及び擬似乱数生成プログラムの提供を目的とする。また、従来のストリーム暗号方式において、より安全性の高い擬似乱数生成装置及び擬似乱数生成方法及び擬似乱数生成プログラムの提供を目的とする。
【課題を解決するための手段】
【０００６】
本発明の擬似乱数生成装置は、
複数バイトからなるワード単位で、擬似乱数を生成する擬似乱数生成装置において、
鍵情報を記憶する鍵メモリと、
複数のワードからなり、アドレスＩ（Ｉは、０以上の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１と、
第１メモリＳ１と同一数の複数のワードから構成されるメモリであって、アドレスＩを用いて、
ワードＳ２［Ｉ］をアクセスする第２メモリＳ２と、
第１メモリＳ１と第２メモリＳ２との各ワードにそれぞれワード値を設定するとともに、第１内部メモリと第２内部メモリとに初期値を設定する初期化部と、
鍵メモリが記憶する鍵情報を用いて、第１メモリＳ１と第２メモリＳ２とに設定されたワードの値に対して鍵スケジューリングをして第１メモリＳ１と第２メモリＳ２とに記憶する鍵スケジュール部と、
鍵スケジュール部により鍵スケジュールされた第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成するストリーム生成部と
を備えたことを特徴とする。【０００７】
前記ストリーム生成部は、
第１メモリＳ１のワードの値から、第１メモリＳ１のアドレスを生成し、生成されたアドレスの第１メモリＳ１のワードの値から擬似乱数を生成する第１乱数生成部と、
第２メモリＳ２のワードの値から、第２メモリＳ２のアドレスを生成し、生成されたアドレスの第２メモリＳ２のワードの値から擬似乱数を生成する第２乱数生成部と、
を備えたことを特徴とする。【０００８】
本発明の擬似乱数生成装置は、
数バイトからなるワード単位で、擬似乱数を生成する擬似乱数生成装置において、
鍵スケジュールされた値を記憶する複数のワードからなり、アドレスＩ（Ｉは、０以上の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１と、
第１メモリＳ１と同一数の複数のワードから構成されるメモリであって、鍵スケジュールされた値を記憶する複数のワードからなり、アドレスＩを用いて、ワードＳ２［Ｉ］をアクセスする第２メモリＳ２と、
第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成するストリーム生成部と
を備えたことを特徴とする。【０００９】
本発明の擬似乱数生成装置は、
ｎ（１≦ｎ≦Ｎ、Ｎは１以上の整数）バイトからなるワード単位で、擬似乱数を生成する擬似乱数生成装置において、
生成すべき乱数のストリーム長Ｌを記憶するストリーム長メモリと、
固定値を記憶する固定値メモリと、
鍵情報を記憶する鍵メモリと、
初期値を入力して記憶する初期値メモリと、
２５６ワードから構成されるメモリであって、アドレスＩ（Ｉは、０〜２５５の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１と、
第１メモリＳ１と同一数の複数のワードから構成されるメモリであって、アドレスＩを用いて、ワードＳ２［Ｉ］をアクセスする第２メモリＳ２と、
アドレスＩとなる値を記憶する第１内部メモリと、
ワード単位の値を記憶する第２内部メモリと、
鍵メモリが記憶する鍵情報と初期値メモリが記憶する初期値とを用いて第１内部メモリの値Ｉを更新し、第１内部メモリの値をアドレスＩとして、第１メモリＳ１の先頭ワードから最後のワードまでの各ワードのｎ番目のバイトの値と第１メモリＳ１のアドレスＩのワードＳ１［Ｉ］のｎ番目のバイトの値とをスワップし、さらに、第１内部メモリの値をアドレスＩとして、第２メモリＳ２の先頭ワードから最後のワードまでの各ワードのｎ番目のバイトの値と第２メモリＳ２のアドレスＩのワードＳ２［Ｉ］のｎ番目のバイトの値とをスワップして、第１から第Ｎ番目のバイトまでスワップを繰り返し、第１メモリＳ１と第２メモリＳ２とに記憶されたワードに対して鍵スケジューリングをする鍵スケジュール部と、
鍵スケジュール部により鍵スケジュールされた第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成するストリーム生成部と
を備えたことを特徴とする。【００１０】
本発明の擬似乱数生成装置は、
ｎ（１≦ｎ≦Ｎ、Ｎは１以上の整数）バイトからなるワード単位で、擬似乱数を生成する擬似乱数生成装置において、
生成すべき乱数のストリーム長Ｌを記憶するストリーム長メモリと、
固定値を記憶する固定値メモリと、
鍵情報を記憶する鍵メモリと、
初期値を入力して記憶する初期値メモリと、
２５６ワードから構成されるメモリであって、アドレスＩ（Ｉは、０〜２５５の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１と、
第１メモリＳ１と同一数の複数のワードから構成されるメモリであって、アドレスＩを用いて、ワードＳ２［Ｉ］をアクセスする第２メモリＳ２と、
アドレスＩとなる値を記憶する第１内部メモリと、
ワード単位の値を記憶する第２内部メモリと、
固定値メモリに記憶された固定値を用いて、第１メモリＳ１と第２メモリＳ２との各ワードにそれぞれワード値を設定するとともに、第１内部メモリと第２内部メモリとに初期値を設定する初期化部と、
鍵メモリが記憶する鍵情報と初期値メモリが記憶する初期値とを用いて第１内部メモリの値Ｉを更新し、第１内部メモリの値をアドレスＩとして、第１メモリＳ１の先頭ワードから最後のワードまでの各ワードのｎ番目のバイトの値と第１メモリＳ１のアドレスＩのワードＳ１［Ｉ］のｎ番目のバイトの値とをスワップし、さらに、第１内部メモリの値をアドレスＩとして、第２メモリＳ２の先頭ワードから最後のワードまでの各ワードのｎ番目のバイトの値と第２メモリＳ２のアドレスＩのワードＳ２［Ｉ］のｎ番目のバイトの値とをスワップして、第１から第Ｎ番目のバイトまでスワップを繰り返し、第１メモリＳ１と第２メモリＳ２とに記憶されたワードに対して鍵スケジューリングをする鍵スケジュール部と、
第２内部メモリに記憶されたワードの下位２バイトの値からアドレスＩ２、Ｉ３の値を生成し、
第１メモリＳ１の先頭ワードから最後のワードまでの各ワードＳ１［Ｉ１］の値と
第１メモリＳ１のアドレスＩ２のワードＳ１［Ｉ２］の値と
第２メモリＳ２のアドレスＩ３のワードＳ２［Ｉ３］の値と
を用いて擬似乱数Ｒ１を生成してバッファメモリに出力する第１乱数生成部と、
第１メモリＳ１のアドレスＩ２のワードＳ１［Ｉ２］の値と
第２メモリＳ２のアドレスＩ３のワードＳ２［Ｉ３］の値と
を演算してシフトし、シフトした値を用いて第１メモリＳ１のアドレスＩ１のワードＳ１［Ｉ１］の値を書き換える第１状態変更部と、
第２内部メモリに記憶されたワードの上位と下位の値を入れ替える第１入れ替え部と、
第２内部メモリに記憶されたワードの下位２バイトの値からアドレスＩ４、Ｉ５とする値を生成し、
第２メモリＳ２の先頭ワードから最後のワードまでの各ワードＳ２［Ｉ１］の値と
第２メモリＳ２のアドレスＩ４のワードＳ２［Ｉ４］の値と
第１メモリＳ１のアドレスＩ５のワードＳ１［Ｉ５］の値と
を用いて擬似乱数Ｒ２を生成して出力する第２乱数生成部と、
第２メモリＳ２のアドレスＩ４のワードＳ２［Ｉ４］の値と
第１メモリＳ１のアドレスＩ５のワードＳ１［Ｉ５］の値と
を演算してシフトし、シフトした値を用いて、第２メモリＳ２のアドレスＩ１のワードＳ２［Ｉ１］の値を書き換える第２状態変更部と、
第２内部メモリに記憶されたワードの上位と下位の値を入れ替える第２入れ替え部と、
ストリーム長メモリに記憶したストリーム長になるまで、第１乱数生成部と第１状態変更部と第１入れ替え部の動作と、第２乱数生成部と第２状態変更部と第２入れ替え部の動作とを繰り返すループ部と、
第１乱数生成部から出力される擬似乱数Ｒ１と第２乱数生成部から出力される擬似乱数Ｒ２とを入力して一時的に保持して擬似乱数ストリームとして出力するバッファメモリと、
バッファメモリに出力した擬似乱数のストリーム長が、所定の再スケジュール長になった場合に、鍵スケジュール部を動作させる再スケジュール部と
を備えたことを特徴とする。【００１１】
本発明の擬似乱数生成方法は、
鍵情報を記憶する鍵メモリと、複数のワードからなり、アドレスＩ（Ｉは、０以上の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１と、第１メモリＳ１と同一数の複数のワードから構成されるメモリであって、アドレスＩを用いて、ワードＳ２［Ｉ］をアクセスする第２メモリＳ２とを備えるとともに複数バイトからなるワード単位で、擬似乱数を生成するコンピュータである擬似乱数生成装置が行う擬似乱数生成方法において、
初期化部が、第１メモリＳ１と第２メモリＳ２との各ワードにそれぞれワード値を設定するとともに、第１内部メモリと第２内部メモリとに初期値を設定し、
鍵スケジュール部が、鍵メモリが記憶する鍵情報を用いて、第１メモリＳ１と第２メモリＳ２とに設定されたワードの値に対して鍵スケジューリングをして第１メモリＳ１と第２メモリＳ２とに記憶し、
ストリーム生成部が、鍵スケジュールされた第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成する
ことを特徴とする。【００１２】
本発明の擬似乱数生成プログラムは、
鍵情報を記憶する鍵メモリと、複数のワードからなり、アドレスＩ（Ｉは、０以上の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１と、第１メモリＳ１と同一数の複数のワードから構成されるメモリであって、アドレスＩを用いて、ワードＳ２［Ｉ］をアクセスする第２メモリＳ２とを備えるとともに複数バイトからなるワード単位で、擬似乱数を生成するコンピュータである擬似乱数生成装置に以下の（１）〜（３）の処理を実行させることを特徴とする。
（１）第１メモリＳ１と第２メモリＳ２との各ワードにそれぞれワード値を設定するとともに、第１内部メモリと第２内部メモリとに初期値を設定する処理
（２）鍵メモリが記憶する鍵情報を用いて、第１メモリＳ１と第２メモリＳ２とに設定されたワードの値に対して鍵スケジューリングをして第１メモリＳ１と第２メモリＳ２とに記憶する処理
（３）鍵スケジュールされた第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成する処理
【発明の効果】
【００１３】
本発明により、ストリーム暗号方式に対して、動作が高速で、かつ安全性の高い擬似乱数を生成することができる。
【発明を実施するための最良の形態】
【００１４】
実施の形態１．
図１〜図２３を用いて実施の形態１を説明する。実施の形態１は、２つの内部テーブルを用いて擬似乱数を生成する擬似乱数生成装置及び擬似乱数生成方法及び擬似乱数生成プログラムに関する。【００１５】
図１は、実施の形態１における擬似乱数生成装置１００のブロック図である。擬似乱数生成装置１００は、各種メモリを備える記憶部１１０と、初期化部１２０と、鍵スケジュール部１３０と、ストリーム生成部１４０とを備える。【００１６】
記憶部１１０は、
（１）生成すべき乱数のストリーム長Ｌを記憶するストリーム長メモリ１１１、
（２）固定値（後述するＩＮＩ１［０］等）を記憶する固定値メモリ１１２、
（３）鍵情報（後述するＫ［０］等）を記憶する鍵メモリ１１３、
（４）初期値（後述する０ｘ０１、０ｘ１２３４５６７８）を入力して記憶する初期値メモリ１１４、
なお、ここで、初期値である０ｘ０１、０ｘ１２３４５６７８は一例にすぎず、これらの値に限定するものではない。０ｘ０１については、１バイトの値であればどのような値でもよく、また、０ｘ１２３４５６７８については、４バイトの値であればどのような値でもよい。
（５）２５６ワードから構成されるメモリであって、アドレスＩ（Ｉは、０〜２５５の整数）を用いて、ワードＳ１［Ｉ］をアクセスする第１メモリＳ１（１１５）、
（６）第１メモリＳ１（１１５）と同一数の複数のワードから構成されるメモリであって、アドレスＩを用いて、ワードＳ２［Ｉ］をアクセスする第２メモリＳ２（１１６）、
（７）アドレスＩとなる値を記憶する第１内部メモリ１１７（後述のＢ１）、
（８）ワード単位の値を記憶する第２内部メモリ１１８（後述の＜Ｂ４＞）
等のメモリを備える。これらのメモリは、キャッシュメモリや、フラッシュメモリや、ランダムアクセスメモリや、固定ディスクや、光ディスクにより実現することができる。【００１７】
初期化部１２０は、固定値メモリ１１２に記憶された固定値を用いて、第１メモリＳ１（１１５）と第２メモリＳ２（１１６）との各ワードにそれぞれワード値を設定するとともに、第１内部メモリ１１７と第２内部メモリ１１８とに初期値を設定する。初期化部１２０の動作の詳細は、図５〜図８の説明で後述する。【００１８】
鍵スケジュール部１３０は、鍵メモリ１１３が記憶する鍵情報を用いて、第１メモリＳ１（１１５）と第２メモリＳ２（１１６）とに設定されたワードの値に対して鍵スケジューリングをして第１メモリＳ１（１１５）と第２メモリＳ２（１１６）とに記憶する。鍵スケジュール部１３０の動作の詳細は、図９〜図１５の説明で後述する。【００１９】
ストリーム生成部１４０は、第１メモリＳ１（１１５）と第２メモリＳ２（１１６）とに記憶されたワードを用いて擬似乱数を生成する。ストリーム生成部１４０は、第１乱数生成部１４１、第１状態変更部１４２、第１入れ替え部１４３、第２乱数生成部１４４、第２状態変更部１４５、第２入れ替え部１４６、ループ部１４７、バッファメモリ１４８、再スケジュール部１４９とを備える。これら各構成要素の動作の詳細は、図１６〜図２１の説明で後述する。【００２０】
図２は、実施の形態１における擬似乱数生成装置１００の外観を示す図である。図２において、擬似乱数生成装置１００は、システムユニット８３０、液晶表示装置８１３、キーボード８１４、マウス８１５、コンパクトディスク装置（ＣＤＤ）８１８、プリンタ８１９を備え、これらはケーブルで接続されている。また擬似乱数生成装置１００は、インターネット８４０に接続されており、擬似乱数による暗号を用いてＷｅｂサーバ８５０と通信可能である。【００２１】
図３は、実施の形態１における擬似乱数生成装置１００のハードウェア構成図である。図３において、擬似乱数生成装置１００は、プログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）８１０を備えている。ＣＰＵ８１０は、バス８２５を介してＲＯＭ８１１、ＲＡＭ８１２、液晶表示装置８１３、キーボード８１４、マウス８１５、通信ボード８１６、ＦＤＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）８１７、ＣＤＤ８１８、プリンタ８１９、磁気ディスク装置８２０と接続されている。ＲＡＭ８１２は、揮発性メモリの一例である。ＲＡＭ８１２は、例えばバッファメモリ１４８の一例である。ＲＯＭ８１１、ＦＤＤ８１７、ＣＤＤ８１８、磁気ディスク装置８２０は不揮発性メモリの一例である。これらは、記憶部１１０の一例である。【００２２】
擬似乱数生成装置１００は、通信ボード８１６を介してインターネット８４０に接続されている。また、通信ボード８１６、キーボード８１４、ＦＤＤ８１７などは、データ入力部の一例である。また、例えば、通信ボード８１６、液晶表示装置８１３、磁気ディスク装置８２０などは、出力部の一例である。【００２３】
磁気ディスク装置８２０には、オペレーティングシステム（ＯＳ）８２１、ウィンドウシステム８２２、プログラム群８２３が記憶されている。また、磁気ディスク装置８２０のメモリ領域８２４には、図１で示した記憶部１１０の各種メモリが対応する。プログラム群８２３は、ＣＰＵ８１０、ＯＳ８２１、ウィンドウシステム８２２により実行される。【００２４】
上記プログラム群８２３には、図１で「〜部」として説明した機能を実行するプログラムが記憶されている。例えば、上記プログラム群８２３には、図１の初期化部１２０、鍵スケジュール部１３０及びストリーム生成部１４０の機能を実行するプログラムが記憶されている。プログラムは、ＣＰＵ８１０により読み出され実行される。【００２５】
また、図１で「〜部」として説明したものは、ＣＰＵ８１０により実行され、あるいは処理されるものであり、ＲＯＭ８１１に記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェアのみ、或いは、ハードウェアのみ、或いは、ソフトウェアとハードウェアとの組み合わせ、さらには、ファームウェアとの組み合わせで実施されても構わない。【００２６】
また、以下に述べる実施の形態を実施するプログラムは、また、磁気ディスク装置８２０、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）、光ディスク、ＣＤ（コンパクトディスク）、ＭＤ（ミニディスク）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のその他の記録媒体による記録装置を用いて記憶されても構わない。【００２７】
次に、図４〜図２３を用いて擬似乱数生成装置１００の擬似乱数生成方法の動作を説明する。擬似乱数生成装置１００の動作は、「Ａ．初期化」と、「Ｂ．鍵スケジュール」と、「Ｃ．ストリーム生成」とから成る。これら動作の説明の前に、まず、図４を用いて以下で使用する記号を説明する。【００２８】
（１）暗号化鍵Ｋ（鍵情報の一例）：
暗号化鍵Ｋは、鍵メモリ１１３が記憶する。暗号化鍵Ｋの長さを「Ｋｅｙｌｅｎ」（バイト）とする。１バイト単位で、Ｋ［０］〜Ｋ［Ｋｅｙｌｅｎ−１］と記載する。
（２）初期値ＩＶ（鍵情報の一例）：
初期値ＩＶは、鍵メモリ１１３が記憶する。初期値ＩＶの長さを「Ｉｖｌｅｎ」（バイト）とする。１バイト単位で、ＩＶ［０］〜ＩＶ［Ｉｖｌｅｎ−１］と記載する。
（３）内部テーブルＳ１（第１メモリＳ１（１１５））：
内部テーブルＳ１は第１メモリＳ１（１１５）が記憶するワードにより実現される。以下では、第１メモリＳ１（１１５）を内部テーブルＳ１と同じ意味で使用する場合がある。内部テーブルＳ１は、４バイト×２５６エントリ＝１０２４バイトである。４バイト単位で＜Ｓ１［０］＞〜＜Ｓ１［２５５］＞と記載できる。なお＜Ｓ１［０］＞の「＜＞」の記載は、Ｓ１［０］が１ワード（４バイト）であることを示すものとする。なお、１ワードは４バイトに限るものではなく、２バイト、６バイト、８バイトなどでもよい。
（４）内部テーブルＳ２（第２メモリＳ２（１１６））：
内部テーブルＳ２も内部テーブルＳ１同様に、４バイト×２５６エントリ＝１０２４バイトである。内部テーブルＳ２は、第２メモリＳ２（１１６）により実現される。以下では、内部テーブルＳ１と同様に、第２メモリＳ２（１１６）を内部テーブルＳ２と同じ意味で使用する場合がある。４バイト単位で＜Ｓ２［０］＞〜＜Ｓ２［２５５］＞と記載する。
（５）乱数のストリーム長：
生成すべき乱数のストリーム長を「４×Ｓｔｒｌｅｎ」と記載する。４バイト単位で＜Ｒ［０］＞〜＜Ｒ［Ｓｔｒｌｅｎ−１］＞と記載できる。このストリーム長はストリーム長メモリ１１１が記憶している。
（６）第２内部メモリ１１８：
第２内部メモリ１１８は、４バイトの値を記憶する。第２内部メモリ１１８を＜Ｂ４＞と示す場合がある。
（７）第１内部メモリ１１７：
第１内部メモリ１１７は、１バイトの値を記憶する。第１内部メモリ１１７を「Ｂ１」と示す場合がある。【００２９】
以下に示す計算式、代入式において、右辺の変数は、ＣＰＵ８０がメモリ（記憶部１１０）から値を読み出すことを意味しており、左辺の変数は、ＣＰＵ８０がメモリ（記憶部１１０）へ値を書き込むことを表している。また、「記憶する」、「更新する」、「生成する」、「〜となる。」、「設定する」、「入れ替える」という動作も、ＣＰＵ８０がメモリ（記憶部１１０）へ値を書き込むことを表している。【００３０】
（Ａ．初期化：（Ｓ１０１））
次に、図５〜図８を用いて初期化について説明する。「初期化」は、内部テーブルＳ１と内部テーブルＳ２とを生成する処理である。この「初期化」は、後述の図２２におけるＳ１０１に対応する。図５は、初期化を行なう場合のプログラムを示す。また、図６は、図５のＡ．１〜Ａ．４をフローチャート化した図である。なお、Ａ．５〜Ａ．８は、Ａ．１〜Ａ．４と同様であるので省略した。図７は、内部テーブルＳ１（第１メモリＳ１（１１５））、及び内部テーブルＳ２（第２メモリＳ２（１１６））を初期化する様子を示す図である。図８は、具体的な数値により図７の状態を説明するための図である。【００３１】
（１）初期化部１２０は、図６のＡ．１〜Ａ．４において、固定値メモリ１１２に記憶された固定値＜ＩＮＩ１［０］＞等を用いて、第１メモリＳ１（１１５）の各ワードにワード値を設定する。同様に初期化部１２０は、Ａ．５〜Ａ．８において、固定値メモリ１１２に記憶された固定値＜ＩＮＩ２［０］＞等を用いて、第２メモリＳ２（１１６）の各ワードにワード値を設定する。図７は、初期化部１２０がワード値を第１メモリＳ１（１１５）と第２メモリＳ２（１１６）とに設定した状態を示している。図７は、初期化部１２０が、固定値メモリ１１２が記憶する４バイトの固定値＜ＩＮＩ１［０］＞〜＜ＩＮＩ１［２５５］＞により第１メモリＳ１（１１５）にワード値を設定し、また、固定値メモリ１１２が記憶する４バイトの固定値＜ＩＮＩ２［０］＞〜＜ＩＮＩ２［２５５］＞により第２メモリＳ２（１１６）にワード値を設定した状態を示している。＜ＩＮＩ１［０］＞等は前記のように４バイトの固定値であり、より具体的には、一例として、図８に示すような値が設定される。
（２）また、初期化部１２０は、第１内部メモリ１１７である「Ｂ１」と、第２内部メモリ１１８である＜Ｂ４＞とに初期値を設定する。この初期値は、初期値メモリ１１４に記憶されているものである。図５のＡ．９、Ａ．１０では、一例として、初期化部１２０が初期値として「Ｂ１」に「０ｘ０１」を設定し、＜Ｂ４＞に「０ｘ１２３４５６７８」を設定した場合を示した。【００３２】
（Ｂ．鍵スケジュール：（Ｓ１０２））
次に、図９〜図１５を用いて、鍵スケジュール部１３０の実行する鍵スケジュールについて説明する。この「鍵スケジュール」は、後述の図２２におけるＳ１０２に対応する。「鍵スケジュール」とは、鍵情報を用いて内部テーブルの中身を混ぜる処理をいう。本実施の形態では、「鍵スケジュール」の一例として、暗号化鍵Ｋと初期値ＩＶとを鍵情報として用いることにより、初期化で生成した内部テーブルＳ１と内部テーブルＳ２との中身を混ぜる場合を説明する。
図９は、鍵スケジュール部１３０が実行するプログラムを示している。
図１０は、図９のうちＢ．１〜Ｂ．１０をフローチャート化した図である。
図１１は、図９のうちＢ．１１〜Ｂ．２０をフローチャート化した図である。【００３３】
また、図１２は鍵スケジュールの概要を説明する図である。図１２を説明する。図１２は内部テーブルＳ１を示している。一組の「丸、三角、四角、バツ」は、４バイトのワードを表している。また、「丸」、「三角」、「四角」、「バツ」は、それぞれ１バイトを表す。一組の「丸、三角、四角、バツ」のうち、例えば、
「丸」を０バイト目、
「三角」を１バイト目、
「四角」を２バイト目、
「バツ」を３バイト目
と呼ぶこととする。
本鍵スケジュールでは、鍵スケジュール部１３０が次の処理を実行する。
（１）まず０バイト目（Ｊ＝０）である「丸」の全部（０〜２５５）について、置換を行なう。０バイト目の「丸」を「丸０」とし、アドレスＢ１の０バイト目の「丸」を所定の「丸」とする。スワップ（ｓｗａｐ）の対象となる所定の「丸」は、Ｂ．３、Ｂ．５、Ｂ．６等による「Ｂ１」の値で決まる。
即ち、「丸０」と所定の「丸」とをｓｗａｐし（Ｂ．４）、
（２）次に、「丸１」と所定の「丸」とをｓｗａｐし（Ｂ．４）、
（３）次に、「丸２」と所定の「丸」とをｓｗａｐする（Ｂ．４）。
（４）以下、順次これを「丸２５５」まで実行する。ｓｗａｐの対象となる所定の「丸」は、Ｂ．３、Ｂ．５、Ｂ．６等による「Ｂ１」の値で決まる。
（５）そして、「丸」を示すＪ＝０について、「丸２５５」（Ｉ＝２５５）まで終了すると、次に、Ｊ＝１の場合、つまり、１バイト目である「三角」の全部について同様の処理を実行する。以下同様に、「四角」（Ｊ＝２）、「バツ」（Ｊ＝３）についても実行する。
（６）鍵スケジュール部１３０は、内部テーブルＳ２についても、内部テーブルＳ１と同様の処理を実行する（Ｂ．１１〜Ｂ．２０）。【００３４】
図１３は、図９のＢ．３〜Ｂ．６を図式化したものである。次に図１３について説明する。前記のように、鍵スケジュールは、鍵スケジュール部１３０が行なう処理である。
（１）Ｂ．３において、暗号化鍵Ｋ（鍵情報の一例）をもとに第１内部メモリ１１７である「Ｂ１」にアドレスを設定する。
（２）Ｂ．４において、設定されたアドレス「Ｂ１」からＳ１［Ｂ１］Ｊが決まる。ここで、Ｓ１［Ｂ１］Ｊは、前記で述べたように４バイトである＜Ｓ１［Ｂ１］＞のうちＪバイト目（Ｊ＝０，１，２，３のいずれか）を示す。Ｂ．４において、Ｓ１［Ｂ１］ＪとＳ１［Ｉ］Ｊとを入れ替える（ｓｗａｐする）。なおＩは０〜２５５の整数である。
（３）Ｂ．５において、初期値ＩＶ（鍵情報の一例）をもとに、「Ｂ１」（第１内部メモリ１１７）にアドレスを設定する。
（４）Ｂ．６において、Ｂ．５で設定された「Ｂ１」からＳ２［Ｂ１］Ｊが決まり、Ｓ２［Ｂ１］ＪとＳ２［Ｉ］Ｊとを元に、第１内部メモリ１１７である「Ｂ１」にアドレスを設定する。【００３５】
図１４、図１５は、具体的な数値を用いて図１２を説明する図である。図１４はＢ．１〜Ｂ．６の過程の具体的な状態を説明する図である。図１５はＢ．７→Ｂ．８→Ｂ．３→Ｂ．６の過程の具体的な状態を説明するための図である。以下では、図１４、図１５を用いてＢ鍵スケジュールを具体的に説明する。【００３６】
以下は、鍵スケジュール部１３０の動作である。
（１）Ｂ．１において、Ｊ＝０とする。すなわち、内部テーブルＳ１、内部テーブルＳ２の０バイト目についての処理である。
（２）Ｂ．２において、Ｉ＝０とする。
（３）Ｂ．３において、Ｂ１＝３となる。詳細は次の様である。
鍵スケジュール部１３０は、
Ｂ１＝（Ｂ１＋Ｋ［Ｉ％Ｋｅｙｌｅｎ］）％２５６
を設定する。この場合、図１４に示す様に
Ｂ１＝１（Ａ．９による）、
Ｉ＝０、
Ｋｅｙｌｅｎ＝１６（仮定した）、
Ｋ［０］＝２（仮定した）
とする。よって、
Ｂ１＝（Ｂ１＋Ｋ［Ｉ％Ｋｅｙｌｅｎ］）％２５６
＝（１＋Ｋ［０％１６］）％２５６
＝（１＋Ｋ［０］）％２５６
＝（１＋２）％２５６
＝３
となる。
よって、Ｂ１＝３となる。
（４）Ｂ．４において、鍵スケジュール部１３０は、Ｓ１［０］０とＳ１［３］０とを入れ替える（スワップする）。
詳細は次の様である。
鍵スケジュール部１３０は、Ｓｗａｐ（Ｓ１［Ｉ］Ｊ，Ｓ１［Ｂ１］Ｊ）を実行する。本設例では、
Ｉ＝０、Ｊ＝０、Ｂ１＝３（前記Ｂ．３による）より、
Ｓｗａｐ（Ｓ１［Ｉ］Ｊ，Ｓ１［Ｂ１］Ｊ）
＝Ｓｗａｐ（Ｓ１［０］０，Ｓ１［３］０）
である。
よって、鍵スケジュール部１３０は、Ｓ１［０］０とＳ１［３］０とを入れ替える。
（５）Ｂ．５において、鍵スケジュール部１３０は、Ｂ１＝４を設定する。
詳細は次の様である。
鍵スケジュール部１３０は、
Ｂ１＝（Ｂ１＋ＩＶ［Ｉ％Ｉｖｌｅｎ］）％２５６
によりＢ１を設定する。
この場合、
Ｂ１＝３、Ｉ＝０、Ｉｖｌｅｎ＝１６（仮定した）である。
また、ＩＶ［０］＝１（仮定した）とする。
よって、
Ｂ１＝（Ｂ１＋ＩＶ［Ｉ％Ｉｖｌｅｎ］）％２５６
＝（３＋ＩＶ［０％１６］）％２５６
＝（３＋ＩＶ［０］）％２５６
＝（３＋１）％２５６
＝４
となる。よって、Ｂ１＝４である。
（６）Ｂ．６において、鍵スケジュール部１３０は、Ｂ１＝１２を設定する。
詳細は次の様である。
鍵スケジュール部１３０は、
Ｂ１＝Ｂ１ｘｏｒ（（Ｓ２［Ｉ］Ｊ＋Ｓ２［Ｂ１］Ｊ）％２５６）
により、あらたにＢ１を設定する。
この場合、
Ｂ１＝４（前記Ｂ．４による）、Ｉ＝０、Ｊ＝０である。
また、
Ｓ２［０］０＝３、Ｓ２［４］０＝５
と仮定する。
よって
Ｂ１＝Ｂ１ｘｏｒ（（Ｓ２［Ｉ］Ｊ＋Ｓ２［Ｂ１］Ｊ）％２５６）
＝４ｘｏｒ（（Ｓ２［０］０＋Ｓ２［４］０）％２５６）
＝４ｘｏｒ（（３＋５）％２５６）
＝４ｘｏｒ（８）
＝１２
となる。よって、Ｂ１＝１２である。【００３７】
次に図１５を用いて、Ｂ．７→Ｂ．８→Ｂ．３→Ｂ．６の過程を具体的に説明する。
（１）Ｂ．７において、Ｉ＝Ｉ＋１となる。
よって、Ｉ＝０＋１＝１となる。
（２）また、Ｉ＝１であるので、Ｂ．８においてＢ．３へ進む。
（３）Ｂ．３において、鍵スケジュール部１３０は、Ｂ１＝１４を設定する。
詳細は次の様である。
鍵スケジュール部１３０は、
Ｂ１＝（Ｂ１＋Ｋ［Ｉ％Ｋｅｙｌｅｎ］）％２５６
により、あらたにＢ１を設定する。
この場合、
Ｂ１＝１２（前記Ｂ．６による）、Ｉ＝１、Ｋｅｙｌｅｎ＝１６である。
また、Ｋ［１］＝２と仮定する。
よって、
Ｂ１＝（Ｂ１＋Ｋ［Ｉ％Ｋｅｙｌｅｎ］）％２５６
＝（１２＋Ｋ［１％１６］）％２５６
＝（１２＋Ｋ［１］）％２５６
＝（１２＋２）％２５６
＝１４
となる。よって、Ｂ１＝１４となる。
（４）Ｂ．４において、鍵スケジュール部１３０は、Ｓ１［１］０とＳ１［１４］０とを入れ替える。
詳細は次の様である。
鍵スケジュール部１３０は、Ｓｗａｐ（Ｓ１［Ｉ］Ｊ，Ｓ１［Ｂ１］Ｊ）を実行する。本設例では、
Ｉ＝１、Ｊ＝０、Ｂ１＝１４（前記Ｂ．３による）より、
Ｓｗａｐ（Ｓ１［Ｉ］Ｊ，Ｓ１［Ｂ１］Ｊ）
＝Ｓｗａｐ（Ｓ１［１］０，Ｓ１［１４］０）
である。
よって、鍵スケジュール部１３０は、Ｓ１［１］０とＳ１［１４］０とを入れ替える。
（５）Ｂ．５において、鍵スケジュール部１３０は、Ｂ１＝１７を設定する。
詳細は次の様である。
鍵スケジュール部１３０は、
Ｂ１＝（Ｂ１＋ＩＶ［Ｉ％Ｉｖｌｅｎ］）％２５６
によりＢ１を設定する。
この場合、
Ｂ１＝１４（前記Ｂ．３による）、Ｉ＝１、Ｉｖｌｅｎ＝１６である。
また、ＩＶ［１］＝３と仮定する。
よって、
Ｂ１＝（Ｂ１＋ＩＶ［Ｉ％Ｉｖｌｅｎ］）％２５６
＝（１４＋ＩＶ［１％１６］）％２５６
＝（１４＋ＩＶ［１］）％２５６
＝（１４＋３）％２５６
＝１７
となる。よって、Ｂ１＝１７である。
（６）Ｂ．６において、鍵スケジュール部１３０は、Ｂ１＝２５を設定する。
詳細は次の様である。
鍵スケジュール部１３０は、
Ｂ１＝Ｂ１ｘｏｒ（（Ｓ２［Ｉ］Ｊ＋Ｓ２［Ｂ１］Ｊ）％２５６）
により、あらたにＢ１を設定する。
この場合、
Ｂ１＝１７（前記Ｂ．５による）、Ｉ＝１、Ｊ＝０である。
また、
Ｓ２［１］０＝７、Ｓ２［１７］０＝１
と仮定する。
よって、
Ｂ１＝Ｂ１ｘｏｒ（（Ｓ２［Ｉ］Ｊ＋Ｓ２［Ｂ１］Ｊ）％２５６）
＝１７ｘｏｒ（（Ｓ２［１］０＋Ｓ２［１７］０）％２５６）
＝１７ｘｏｒ（（７＋１）％２５６）
＝１７ｘｏｒ８
＝２５
となる。よって、Ｂ１＝２５である。
（７）このようにして、
内部テーブルＳ１において、Ｂ．１〜Ｂ．１０を実行することにより、
内部テーブルＳ１において、
Ｊ＝０（０バイト目）について、
Ｓ１［０］０と所定の相手とが入れ替えられ、
Ｓ１［１］０と所定の相手とが入れ替えられ、
・・・
Ｓ１［２５５］０と所定の相手とが入れ替えられる。
同様に
Ｊ＝１（１バイト目）について、
Ｓ１［０］１と所定の相手とが入れ替えられ、
Ｓ１［１］１と所定の相手とが入れ替えられ、
・・・
Ｓ１［２５５］１と所定の相手とが入れ替えられる。
Ｊ＝２（２バイト目）、Ｊ＝３（３バイト目）の場合についても同様である。
以上のように、鍵スケジュール部１３０により、鍵スケジュールが実行される。【００３８】
なお、図９に示す様に、内部テーブルＳ１に対する鍵スケジュールのアルゴリズム（Ｂ．１〜Ｂ．１０）と、内部テーブルＳ２に対する鍵スケジュールのアルゴリズム（Ｂ．１１〜Ｂ．２０）のアルゴリズムとは同じであるため兼用することができる。これによりプログラムサイズは、両者を作成する場合に比べて半分になる。【００３９】
（Ｃ．ストリーム生成（Ｓ１０３））
次に、図１６〜図２１を用いて、ストリーム生成部１４０の実行する擬似乱数の生成を説明する。ストリーム生成は、内部テーブルＳ１と内部テーブルＳ２との役割を交互に変えながら、乱数列を生成する処理である。
図１６は、ストリーム生成部１４０の各構成要素が実行するプログラムを示している。
図１７は、図１６をフローチャート化した図である。
図１８は、Ｃ．２〜Ｃ．４を図式化したものである。【００４０】
図１８を簡単に説明する。擬似乱数生成装置１００は、次の動作を実行する。
（１）Ｃ．２において、第２内部メモリ１１８に設定されたＢ４１から＜Ｓ１［Ｂ４１］＞を決定し、Ｂ４０から＜Ｓ２［Ｂ４０］＞を決定する。そして、＜Ｓ１［Ｉ］＞と＜Ｓ１［Ｂ４１］＞と＜Ｓ２［Ｂ４０］＞とから＜Ｒ［Ｊ］＞を生成する。ここで、Ｂ４０は、４バイトの値である＜Ｂ４＞の下位１バイト目の値を示す。Ｂ４１は、４バイトの値である＜Ｂ４＞の下位２バイト目の値を示す。後述する図１９の第２内部メモリ１１８を例に取れば、Ｂ４０＝７８（１６）であり、Ｂ４１＝５６（１６）である。なお以下の説明には、＜Ｂ４＞に１６進数で記憶されている数値を使用するため「７８（１６）」等と記載し、添え字（１６）により「７８」が１６進数であることを示す。添え字のない値は、１０進数であることを示す。
（２）Ｃ．３において、＜Ｓ１［Ｂ４１］＞と＜Ｓ２［Ｂ４０］＞とに基づいて、＜Ｓ１［Ｉ］＞を新たに生成する。
（３）Ｃ．４において、＜Ｓ２（Ｉ）＞から新たにＢ４を更新する。
（４）以上において、＜Ｒ［Ｊ］＞は、＜Ｓ１［Ｂ４１］＞，＜Ｓ１［Ｉ］＞，＜Ｓ２［Ｂ４０］＞から生成されるが、次の内部状態を決定するのは、この３つの値と＜Ｂ４＞の他に＜Ｓ２［Ｉ］＞がある（Ｃ．４）。この＜Ｓ２［Ｉ］＞の値は、＜Ｒ［Ｊ］＞には直接的には影響を与えない。すなわち＜Ｒ［Ｊ］＞から＜Ｓ２［Ｉ］＞の値を推測することは不可能であり安全性が高まる。このため、攻撃者は生成された＜Ｒ［Ｊ］＞から＜Ｓ２［Ｉ］＞を推測することが困難となり安全性が向上する。【００４１】
図１９、図２０は、具体的な数値を用いて図１８を説明するための図である。以下では、図１９、図２０を参照して具体的な数値を用いて擬似乱数の生成を説明する。【００４２】
まず、図１９を参照してＣ．１〜Ｃ．４の過程を説明する。【００４３】
（１）Ｃ．１において、Ｉ＝０、Ｊ＝０とする。
また、初期化部１２０が、第２内部メモリ１１８に
＜Ｂ４＞＝０ｘ１２３４５６７８
を設定しているものとする。【００４４】
（２）Ｃ．２において、第１乱数生成部１４１が、＜Ｒ［０］＞＝７を生成する。
詳細は次の様である。
第１乱数生成部１４１は、
＜Ｒ［Ｊ］＞＝＜Ｓ１［Ｉ］＞ｘｏｒ＜Ｓ１［Ｂ４１］＞ｘｏｒ＜Ｓ２［Ｂ４０］＞
を実行して、乱数＜Ｒ［Ｊ］＞を生成する。
この場合、
Ｊ＝０、Ｉ＝０、Ｂ４１＝５６（１６）、Ｂ４０＝７８（１６）である。
また、図１９に示す様に
＜Ｓ１［０］＞＝２、＜Ｓ１［５６（１６）］＞＝１、＜Ｓ２［７８（１６）］＞＝４
と仮定する。
この場合、
＜Ｒ［０］＞＝＜Ｓ１［０］＞ｘｏｒ＜Ｓ１［５６（１６）］＞ｘｏｒ＜Ｓ２［７８（１６）］＞
＝２ｘｏｒ１ｘｏｒ４
＝７
となる。よって、
＜Ｒ［０］＞＝７となる。
（３）Ｃ．３において、第１状態変更部１４２が、＜Ｓ１［Ｂ４１］＞と、＜Ｓ２［Ｂ４０］＞とを演算してシフトし、シフトした値を用いて＜Ｓ１［Ｉ］＞の値を書き換える。
すなわち、第１状態変更部１４２は、
＜Ｓ１［Ｉ］＞＝（＜Ｓ１［Ｉ］＞＋ＲＯＴＬ（（＜Ｓ１［Ｂ４１］＞ｘｏｒ＜Ｓ２［Ｂ４０］＞），１））％２３２
を実行する。
ここで、ＲＯＴＬ（ｘ，ｓ）は、３２ビットデータｘを左にｓビット回転シフトすることを示す。
例えば、ＲＯＴＬ（５，１）であれば、１０進数の「５」は、２進数表記で
「００・・・０１０１（２）」
である。
よって、
ＲＯＴＬ（５，１）＝「００・・・・１０１０（２）」
となり、１０進数表記で、１０である。
よって、
ＲＯＴＬ（５，１）＝１０
である。
今Ｉ＝０であるので、左辺は＜Ｓ１［０］＞である。また、右辺の＜Ｓ１［０］＞等は、Ｃ．２の＜Ｒ［０］＞の右辺の値と同じである。よって、右辺の各値は、
＜Ｓ１［０］＞＝２、＜Ｓ１［５６（１６）］＞＝１、＜Ｓ２［７８（１６）］＞＝４
である。
よって、
＜Ｓ１［０］＞＝（＜Ｓ１［０］＞＋ＲＯＴＬ（（＜Ｓ１［５６（１６）］＞ｘｏｒ＜Ｓ２［７８（１６）］＞），１））％２３２
＝（２＋ＲＯＴＬ（（１ｘｏｒ４），１））％２３２
＝（２＋ＲＯＴＬ（５，１））％２３２
＝（２＋１０）％２３２
＝１２
となる。
よって、＜Ｓ１［０］＞＝１２となる。
図１９に示す様に、＜Ｓ１［０］＞は、２→１２に書き換えられる。【００４５】
（４）Ｃ．４において、第１入れ替え部１４３が、第２内部メモリ１１８である＜Ｂ４＞に記憶されたワードの上位と下位の値を入れ替える。
すなわち、第１入れ替え部１４３は、
＜Ｂ４＞＝ＲＯＴＬ（（（＜Ｂ４＞＋＜Ｓ２［Ｉ］＞）％２３２），１６）
を実行する。
ここで、
右辺の＜Ｂ４＞＝０ｘ１２３４５６７８、
また、Ｉ＝０である。
また、
＜Ｓ２［０］＞＝１と仮定する。
よって、
＜Ｂ４＞＝ＲＯＴＬ（（（＜Ｂ４＞＋＜Ｓ２［Ｉ］＞）％２３２），１６）
＝ＲＯＴＬ（（（＜Ｂ４＞＋＜Ｓ２［０］＞）％２３２），１６）
＝ＲＯＴＬ（（（０ｘ１２３４５６７８＋１）％２３２），１６）
＝ＲＯＴＬ（（（０ｘ１２３４５６７９）％２３２），１６）
＝０ｘ５６７９１２３４
となる。
よって、
＜Ｂ４＞＝０ｘ５６７９１２３４
となる。【００４６】
次に図２０を用いて、Ｃ．５〜Ｃ．９の過程を説明する。
（５）Ｃ．５において、Ｊ＝Ｊ＋１となる。この場合、Ｊ＝１となる。
（６）Ｃ．６ではＪ≠Ｓｔｒｌｅｎとする。
（７）Ｃ．７において、第２乱数生成部１４４が、＜Ｒ［１］＞＝１９を生成する。
詳細は次の様である。
第２乱数生成部１４４は、
＜Ｒ［Ｊ］＞＝＜Ｓ２［Ｉ］＞ｘｏｒ＜Ｓ２［Ｂ４１］＞ｘｏｒ＜Ｓ１［Ｂ４０］＞
を実行して、乱数＜Ｒ［Ｊ］＞を生成する。
この場合、
Ｊ＝１、
Ｉ＝０、
Ｂ４１＝１２（１６）、
Ｂ４０＝３４（１６）、
＜Ｓ２［０］＞＝１
である。
また、
＜Ｓ２［１２（１６）］＞＝２、＜Ｓ１［３４（１６）］＞＝１６
と仮定する。
この場合、
＜Ｒ［０］＞＝＜Ｓ２［０］＞ｘｏｒ＜Ｓ２［１２（１６）］＞ｘｏｒ＜Ｓ１［３４（１６）］＞
＝１ｘｏｒ２ｘｏｒ１６
＝１９
となる。よって、
＜Ｒ［１］＞＝１９となる。
（８）Ｃ．８において、第２状態変更部１４５が、
＜Ｓ２［Ｂ４１］＞と、＜Ｓ１［Ｂ４０］＞とを演算してシフトし、シフトした値を用いて＜Ｓ２［Ｉ］＞の値を書き換える。
すなわち、第２状態変更部１４５は、
＜Ｓ２［Ｉ］＞＝（＜Ｓ２［Ｉ］＞＋ＲＯＴＬ（（＜Ｓ２［Ｂ４１］＞ｘｏｒ＜Ｓ１［Ｂ４０］＞），１））％２３２
を実行する。
ここで、
右辺の＜Ｓ２［Ｉ］＞等は、Ｃ．７の＜Ｒ［Ｊ］＞の右辺の値と同じである。よって、右辺の各値は、
＜Ｓ２［０］＞＝１
＜Ｓ２［１２（１６）］＞＝２、
＜Ｓ１［３４（１６）］＞＝１６
である。よって、
＜Ｓ２［０］＞＝（＜Ｓ２［０］＞＋ＲＯＴＬ（（＜Ｓ２［１２（１６）］＞ｘｏｒ＜Ｓ１［３４（１６）］＞），１））％２３２
＝（１＋ＲＯＴＬ（（２ｘｏｒ１６），１））％２３２
＝３７
となる。
よって、＜Ｓ２［０］＞＝３７となる。
図２０に示す様に、＜Ｓ２［０］＞は、１→３７に書き換えられる。
（９）Ｃ．９において、第２入れ替え部１４６が、第２内部メモリ１１８である＜Ｂ４＞に記憶されたワードの上位と下位の値を入れ替える。
すなわち、第２入れ替え部１４６は、
＜Ｂ４＞＝ＲＯＴＬ（（（＜Ｂ４＞＋＜Ｓ１［Ｉ］＞）％２３２），１６）
を実行する。
ここで、
＜Ｂ４＞＝０ｘ５６７９１２３４、
Ｉ＝０、
及び＜Ｓ１［０］＞＝１２（Ｃ．３で書き換えられている）である。
よって、
＜Ｂ４＞＝ＲＯＴＬ（（（＜Ｂ４＞＋＜Ｓ２［Ｉ］＞）％２３２），１６）
＝ＲＯＴＬ（（（＜Ｂ４＞＋＜Ｓ１［０］＞）％２３２），１６）
＝ＲＯＴＬ（（（０ｘ５６７９１２３４＋１２＞）％２３２），１６）
＝ＲＯＴＬ（（０ｘ５６７９１２４６），１６）
＝０ｘ１２４６５６７９
となる。
（１０）ループ部１４７は、ストリーム長メモリ１１１に記憶したストリーム長になるまで、第１乱数生成部１４１と第１状態変更部１４２と第１入れ替え部１４３の動作と、第２乱数生成部１４４と第２状態変更部１４５と第２入れ替え部１４６の動作とを繰り返す。
（１１）バッファメモリ１４８は、第１乱数生成部１４１から出力される擬似乱数Ｒ１と第２乱数生成部１４４から出力される擬似乱数Ｒ２とを入力して一時的に保持して擬似乱数ストリームとして出力する。
（１２）再スケジュール部１４９は、バッファメモリ１４８に出力した擬似乱数のストリーム長が、所定の再スケジュール長になった場合に、鍵スケジュール部１３０を動作させ、鍵スケジュールをやり直す（Ｃ．１１）。ここで、所定の「再スケジュール長」とは、例えば、
「内部テーブルのワード数×ワードのバイト数×メモリの数×第２内部メモリが一巡するシフト回数（３２回、Ｃ．４及びＣ．９による））」を用いる。
ここで、
（ａ）「内部テーブルのワード数」とは、内部テーブルＳ１あるいは内部テーブルＳ２のワード数をいい本実施の形態１の場合は、２５６である。
（ｂ）「ワードのバイト数」とは、内部テー部の１ワードのバイト数であり、４である。
（ｃ）「メモリの数」とは、第１メモリＳ１と第２メモリＳ２との２つである。
（ｄ）「第２内部メモリ１１８が一巡するシフト回数」とは、Ｃ．４あるいはＣ．９においてメモリ＜Ｂ４＞が一巡するシフト回数を意味し、３２回である。
（ａ）〜（ｄ）によれば、「再スケジュール長」は、一例として、
「再スケジュール長」＝２５６×４×２×３２
＝６５５３６バイト（１６３８４ワード）
＝６４ＫＢとなる。
図１７のフローチャートで説明すれば、Ｃ．１１において、再スケジュール部１４９は、擬似乱数列の長さ（Ｊの値）が所定の「再スケジュール長」であるＳｔｒｌｅｎになったかどうかを判断する。再スケジュール部１４９は、「再スケジュール長」になったと判断した場合には、図１０の（Ａ）に進み、鍵スケジュール部１３０を動作させ鍵スケジュールをやり直す。
（１３）擬似乱数生成装置１００は、ストリーム生成部１４０の生成した擬似乱数ストリームＲ［０］、Ｒ［１］・・・と平文とをＸＯＲ（排他的論理和）して、暗号文を作成する。【００４７】
以上のストリーム生成では、内部テーブルＳ１と内部テーブルＳ２とが、「乱数生成」と「アドレス生成」との役割を交代しながら、順次、擬似乱数Ｒを生成していく。これに対し、従来のＲＣ４は、一つのテーブルで行なっていた。【００４８】
なお、以上の擬似乱数生成装置１００による擬似乱数の生成方法では、内部テーブルＳ１と内部テーブルＳ２との２つを使用することにより、擬似乱数を生成した。しかし、これは一例であり、３つの内部テーブルに基づき擬似乱数を生成してもよいし、４つの内部テーブルに基づき擬似乱数を生成してもよい。いくつの内部テーブルを用いても構わない。【００４９】
擬似乱数生成装置１００の初期化部１２０、鍵スケジュール部１３０、ストリーム生成部１４０の一連の動作は互いに関連しており、これらの一連の動作を擬似乱数生成方法として把握することができる。【００５０】
図２２は、擬似乱数生成装置１００の初期化部１２０等の動作を擬似乱数生成方法として把握した場合のフローチャートを示す。
（１）Ｓ１０１は、初期化部が、第１メモリＳ１と第２メモリＳ２との各ワードにそれぞれワード値を設定するとともに、第１内部メモリと第２内部メモリとに初期値を設定するステップである。
（２）Ｓ１０２は、鍵スケジュール部が、鍵メモリが記憶する鍵情報を用いて、第１メモリＳ１と第２メモリＳ２とに設定されたワードの値に対して鍵スケジュールをして第１メモリＳ１と第２メモリＳ２とに記憶するステップである。
（３）Ｓ１０３は、ストリーム生成部が、鍵スケジュール部により鍵スケジュールされた第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成するステップである。【００５１】
また、擬似乱数生成装置１００における初期化部１２０、鍵スケジュール部１３０、ストリーム生成部１４０の一連の動作は、一連の処理に置き換えることにより、プログラムの実施形態として把握することができる。【００５２】
図２３は、擬似乱数生成装置１００の初期化部１２０等の動作を、コンピュータである擬似乱数生成装置１００に実行させるための一連の処理からなる擬似乱数生成プログラムとして把握した場合のフローチャートを示す。
（１）Ｓ２０１は、第１メモリＳ１と第２メモリＳ２との各ワードにそれぞれワード値を設定するとともに、第１内部メモリと第２内部メモリとに初期値を設定する処理である。
（２）Ｓ２０２は、鍵メモリが記憶する鍵情報を用いて、第１メモリＳ１と第２メモリＳ２とに設定されたワードの値に対して鍵スケジュールをして第１メモリＳ１と第２メモリＳ２とに記憶する処理である
（３）Ｓ２０３は、鍵スケジュールされた第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成する処理である。【００５３】
なお、図１６に示すＣ．２では、内部テーブルＳ１のワード値＜Ｓ１［Ｉ］＞、及び＜Ｓ１［Ｂ４１］＞の他、内部テーブルＳ２のワード値＜Ｓ２［Ｂ４０］＞を用いた。また、Ｃ．７では、内部テーブルＳ２のワード値＜Ｓ２［Ｉ］＞、及び＜Ｓ２［Ｂ４１］＞の他、内部テーブルＳ１のワード値＜Ｓ１［Ｂ４０］＞を用いた。これは一つの例である。擬似乱数生成装置１００のストリーム生成部１４０は、鍵スケジュール部１３０により鍵スケジュールされた内部テーブルＳ１（第１メモリＳ１（１１５））と内部テーブルＳ２（第２メモリＳ２（１１６））とに記憶されたワードを交互に用いて擬似乱数を生成しても構わない。
その場合、
Ｃ．２において
＜Ｒ［Ｊ］＞＝＜Ｓ１［Ｉ］＞ｘｏｒ＜Ｓ１［Ｂ４１］＞    （式１）
を実行し、
Ｃ．７において
＜Ｒ［Ｊ］＞＝＜Ｓ２［Ｉ］＞ｘｏｒ＜Ｓ２［Ｂ４１］＞    （式２）
を実行する。
この場合、図１８（上記（式１）に対応）において、＜Ｒ［Ｊ］＞と＜Ｓ２［Ｂ４０］＞との関係が遮断されるため、攻撃者は生成されたＲ［Ｊ］の値から内部状態を予想することが困難となるため安全性が向上する。【００５４】
図２１を用いて、上記（式１）、（式２）を用いた場合の、ストリーム生成部１４０の別の動作例を説明する。
（１）ストリーム生成部１４０の第１乱数生成部１４１は、第１メモリＳ１（１１５）の値から、第１メモリＳ１（１１５）のアドレスを生成し、生成されたアドレスの第１メモリＳ１（１１５）のワードの値から擬似乱数を生成する（Ｃ．９及び上記（式１）としたＣ．２）。すなわち、図２１に示す様に、第１乱数生成部１４１は、Ｃ．９において、第１メモリＳ１（１１５）の値Ｓ１［Ｉ］から、Ｃ．２で＜Ｓ１［Ｂ４１］＞のアドレスとなるべき＜Ｂ４＞を生成する（ＳＴ１）。
そして、Ｃ．９において第１乱数生成部１４１は、生成されたアドレスＢ４１の第１メモリＳ１（１１５）のワード値＜Ｓ１［Ｂ４１］＞を特定し（ＳＴ２）、上記の（式１）により、特定したワード値＜Ｓ１［Ｂ４１］＞と＜Ｓ１［Ｉ］＞とから擬似乱数＜Ｒ＞を生成する（ＳＴ３）。
（２）図２１に示す様に、次にＳＴ４において、役割が内部テーブルＳ１（第１メモリＳ１（１１５））から内部テーブルＳ２（第２メモリＳ２（１１６））に移る。ストリーム生成部１４０の第２乱数生成部１４４は、第２メモリＳ２（１１６）の値から、第２メモリＳ２（１１６）のアドレスを生成し、生成されたアドレスの第２メモリＳ２（１１６）のワードの値から擬似乱数を生成する（Ｃ．４及び上記（式２）としたＣ．７）。すなわち、第２乱数生成部１４４は、Ｃ．４において、第２メモリＳ２（１１６）の値Ｓ２［Ｉ］から、Ｃ．７で＜Ｓ２［Ｂ４１］＞のアドレスとなるべき＜Ｂ４＞を生成する（ＳＴ５）。そして、Ｃ．７において第１乱数生成部１４１は、生成されたアドレスＢ４１の第２メモリＳ２（１１６）のワード値＜Ｓ２［Ｂ４１］＞を特定し（ＳＴ６）、上記の（式２）により、特定したワード値＜Ｓ２［Ｂ４１］＞と＜Ｓ２［Ｉ］＞とから擬似乱数＜Ｒ’＞を生成する（ＳＴ７）。
（３）以上（１）、（２）のように第１乱数生成部１４１と第２乱数生成部１４４とは、第１メモリＳ１（１１５）と第２メモリＳ２（１１６）とに記憶されたワードを交互に用いて擬似乱数Ｒ、Ｒ’等を生成する。【００５５】
前述した擬似乱数生成装置及び擬似乱数生成方法及び擬似乱数生成プログラムは、ストリーム型の暗号の発生装置であるが、テキスト（平文）の暗号装置としても使えるし、暗号文の復号装置としても用いることができる。【００５６】
また、前述した擬似乱数生成装置及び擬似乱数生成方法は、図３あるいは図２３に示したように、コンピュータで動作させるプログラム（ソフトウェア）として実現できる。プログラムで実現した場合は、そのプログラムを内蔵した半導体チップやＩＣチップとしても実現することができ、どのような電子機器にも用いることができる。【００５７】
例えば、前述した擬似乱数生成装置及び擬似乱数生成方法及び擬似乱数生成プログラムの好適な適用例としては、ワープロ文章の暗号または復号、Ｅメールテキストの暗号または復号、インターネットやローカルエリアネットワークの通信データの暗号または復号、携帯電話と基地局との通信データの暗号または復号、ＩＣタグやＩＣカードのデータの暗号または復号などが考えられる。【００５８】
特に、メモリ容量に限りのある小型機器（携帯電話、ＩＣタグ、ＩＣカード）の通信データの暗号または復号に適している。【００５９】
本実施の形態１の擬似乱数生成装置は、第１メモリＳ１と第２メモリＳ２とに対して鍵スケジュールを行なう鍵スケジュール部と、鍵スケジュールされた第１メモリＳ１と第２メモリＳ２とに記憶されたワードを交互に用いて擬似乱数を生成するストリーム生成部とを備えたので、解読攻撃に対する安全性を向上することができる。また、ストリーム生成部は、ワード単位を対象として擬似乱数を生成するので、処理の高速化を実現することができる。【００６０】
本実施の形態１の擬似乱数生成装置は、第１乱数生成部が第１メモリＳ１を用いて擬似乱数を生成し、第２乱数生成部が第２メモリＳ２を用いて擬似乱数を生成するとともに、第１乱数生成部と第２乱数生成部とが交互に擬似乱数を生成する。よって、解読攻撃に対する安全性を向上することができる。【００６１】
本実施の形態１の擬似乱数生成装置は、鍵スケジュール部が、ワード単位で構成された複数の内部テーブル（第１メモリＳ１及び第２メモリＳ２）に対して鍵スケジュールを実施する。よって、非常に大きな空間での置換が可能となり、解読攻撃に対する安全性を向上することができる。【００６２】
本実施の形態１の擬似乱数生成装置は、ストリーム生成部が２つの内部テーブルに基づき乱数を生成するので、解読攻撃に対する安全性を向上することができる。【００６３】
従来技術ではバイト単位の処理であったのに対して、実施の形態１の擬似乱数生成装置１００は、ストリーム生成部１４０が、ワード単位（４バイト）で擬似乱数を生成するので、高速化を実現することができる。【００６４】
また、バイト単位の処理では、一つの内部テーブルに実現される要素は０〜２５５までの２５６通りであったのに対して、実施の形態１の擬似乱数生成装置１００は、鍵スケジュール部１３０が、ワードを対象として処理することで、０〜２３２−１までの２３２通りと、非常に大きな空間での置換を可能とし、安全性を向上することができる。【００６５】
従来技術では一つの内部テーブルで置換を繰り返すものであったのに対して、実施の形態１の擬似乱数生成装置１００は、鍵スケジュール部１３０が、内部テーブルＳ１と内部テーブルＳ２とを交互に作用させて置換を繰り返すので、非常に長いランダム性（周期性）を実現することができる。また、ストリーム生成部１４０が、内部テーブルＳ１と内部テーブルＳ２とを交互に作用させて置換を繰り返すので、非常に長いランダム性（周期性）を実現することができる。【００６６】
従来技術では１回の鍵スケジュールを実行した後に、次に鍵が変更されるまでは擬似乱数生成の処理を連続実行するため、一定以上の処理を実行すると同じ乱数列が生成されてしまう。これに対して実施の形態１の擬似乱数生成装置１００は、擬似乱数の生成処理を一通り最後まで実施した後に、再スケジュール部１４９が鍵スケジュール部１３０を動作させて、擬似乱数の生成に利用する内部テーブルＳ１、内部テーブルＳ２を更新することにより同じ乱数列の生成を防ぎ、安全性を向上する。【００６７】
従来例は本実施の形態１の擬似乱数生成装置１００の動作に比べて動作が簡単であるため、高速に動作するように一見見える。しかし、実際にプログラミングした場合、本実施の形態１は格段に高速である。これは、本実施の形態１ではＣ．１〜Ｃ．１１のストリーム生成が４バイト単位でおこなわれていることに起因している（従来例では１バイト単位）。【００６８】
一方、一般に、テーブル参照型の暗号の安全性（解読困難性）を高めるためには、得られたストリームＲ［Ｊ］からテーブルの内部状態をできるだけ推測しにくくする必要がある。高速性と安全性を両立させるため、本実施の形態１の擬似乱数生成装置１００では速度を大きく低下させない範囲で次のような新たな工夫を行なっている。
（１）従来例では内部テーブルが１つであるのに対して、本実施の形態１の擬似乱数生成装置１００では同じサイズの内部テーブルを２つ持つ。このため、その内部状態を推測するのは困難であると考えられる。具体的には、従来例では、２５６バイトのテーブルの１状態から１バイトを生成するのに対し、本実施の形態１の擬似乱数生成装置１００では、２０４８バイトのテーブルの１状態から４バイトの乱数Ｒ［Ｊ］を生成する。即ち擬似乱数生成装置１００では、ストリーム１バイトあたりのエントロピーが従来例の倍あることになる。
（２）従来例の「Ｃストリーム生成」では、Ｒ［Ｊ］はＳ［Ｂ］とＳ［Ｉ］から生成され、しかも、この２つの値とＢが次の内部状態を決定する。これに対して本実施の形態１の擬似乱数生成装置１００は、例えば図１８において、Ｒ［Ｊ］はＳ１［Ｂ４１］，Ｓ１［Ｉ］，Ｓ２［Ｂ４０］から生成されるが、次の内部状態を決定するのは、この３つの値とＢ４の他にＳ２［Ｉ］がある。このＳ２［Ｉ］の値はＲ［Ｊ］には直接的には影響を与えない。すなわちＲ［Ｊ］からＳ２［Ｉ］の値を推測することは不可能であり安全性が高まる。
（３）本実施の形態１の擬似乱数生成装置１００では、内部テーブルＳ１と内部テーブルＳ２とが、その役割を変えながら交互に内部状態を変えていく。内部テーブルＳ１と内部テーブルＳ２との役割を変えた部分は、例えば図１６の「Ｃ．２〜Ｃ．５」と、「Ｃ．７〜Ｃ．１０」とが対応する。この２つの部分は、内部テーブルＳ１と内部テーブルＳ２とが入れ替わっただけなので、これらの内部テーブルの先頭アドレスへのポインタを入れ替えてやりさえすればプログラムを共用することができ、プログラムサイズ削減に役立つ。
（４）従来例では鍵スケジュールは最初に一回だけ行い、その後は決して行われなかった。これに対して、本実施の形態１の擬似乱数生成装置１００では、６４ＫＢごとに鍵スケジュールをやり直す処理を行っている。鍵スケジュールは内部テーブルＳ１、Ｓ２の内部状態を完全に変えてしまうので、これによって解読者による内部状態の再現はほぼ不可能になってしまう。鍵スケジュールを頻繁に行うと処理速度の低下となるが、６４ＫＢ程度であれば、その処理速度低下は問題にならない。
（５）ちなみに、６４ＫＢの根拠は以下の通りである。内部テーブルＳ１と内部テーブルＳ２とがすべて書き換えられるためには、Ｉが０から２５５まで動く必要がある。それまでにストリームＲは、２５６×４バイト×２＝２ＫＢ生成される。さらに内部に１ビットの回転シフト命令が存在するが、この回転は３２回行うと元に戻る。したがって、２ＫＢ×３２回＝６４ＫＢでデータの変換が一巡するとみなすことができ、鍵スケジュールを行うにはよいタイミングである。
【図面の簡単な説明】
【００６９】
【図１】実施の形態１における擬似乱数生成装置１００の構成図である。
【図２】実施の形態１における擬似乱数生成装置１００の外観の一例を示す。
【図３】実施の形態１における擬似乱数生成装置１００のハードウェア構成を示す。
【図４】実施の形態１における擬似乱数生成装置１００の動作説明に使用する記号の説明である。
【図５】初期化部１２０が初期化を実行する場合のプログラムである。
【図６】図５のフローチャートである。
【図７】初期化部１２０が第１メモリＳ１（１１５）、第２メモリＳ２（１１６）にワード値を設定する様子を示す図である。
【図８】初期化部１２０が第１メモリＳ１（１１５）、第２メモリＳ２（１１６）にワード値を設定した場合の具体例を示す図である。
【図９】鍵スケジュール部１３０が鍵スケジュールを行う場合のプログラムである。
【図１０】図９のＢ．１〜Ｂ．１０のフローチャートである。
【図１１】図９のＢ．１１〜Ｂ．２０のフローチャートである。
【図１２】鍵スケジュールの概要を説明する図である。
【図１３】図１０のＢ．３〜Ｂ．６の図式化である。
【図１４】図１３を具体的な数値で説明する図である。
【図１５】図１３を具体的な数値で説明する図である。
【図１６】ストリーム生成部１４０がストリーム生成を行う場合のプログラムである。
【図１７】図１６のフローチャートである。
【図１８】図１６のＣ．２〜Ｃ．４を図式化したものである。
【図１９】図１８を具体的な数値で説明する図である。
【図２０】図１８を具体的な数値で説明する図である。
【図２１】ストリーム生成部１４０の別の動作例を示す図である。
【図２２】擬似乱数生成方法のステップを示す図である。
【図２３】擬似乱数生成プログラムの処理工程を示す図である。
【図２４】従来技術を説明する図である。
【図２５】従来技術を説明する図である。
【符号の説明】
【００７０】
１００  擬似乱数生成装置、１１０  記憶部、１１１  ストリーム長メモリ、１１２  固定値メモリ、１１３  鍵メモリ、１１４  初期値メモリ、１１５  第１メモリＳ１、１１６  第２メモリＳ２、１１７  第１内部メモリ、１１８  第２内部メモリ、１２０  初期化部、１３０  鍵スケジュール部、１４０  ストリーム生成部、１４１  第１乱数生成部、１４２  第１状態変更部、１４３  第１入れ替え部、１４４  第２乱数生成部、１４５  第２状態変更部、１４６  第２入れ替え部、１４７  ループ部、１４８  バッファメモリ、１４９  再スケジュール部、８１０  ＣＰＵ、８１１  ＲＯＭ、８１２  ＲＡＭ、８１３  液晶表示装置、８１４  キーボード、８１５  マウス、８１６  通信ボード、８１７  ＦＤＤ、８１８  ＣＤＤ、８１９  プリンタ、８２０  磁気ディスク装置、８２１  ＯＳ、８２２  ウィンドウシステム、８２３  プログラム群、８２４  メモリ領域、８２５  バス、８３０  システムユニット、８４０  インターネット、８５０  Ｗｅｂサーバ。
【図１】
0004718455.tif 000002
【図２】
0004718455.tif 000003
【図３】
0004718455.tif 000004
【図４】
0004718455.tif 000005
【図５】
0004718455.tif 000006
【図６】
0004718455.tif 000007
【図７】
0004718455.tif 000008
【図８】
0004718455.tif 000009
【図９】
0004718455.tif 000010
【図１０】
0004718455.tif 000011
【図１１】
0004718455.tif 000012
【図１２】
0004718455.tif 000013
【図１３】
0004718455.tif 000014
【図１４】
0004718455.tif 000015
【図１５】
0004718455.tif 000016
【図１６】
0004718455.tif 000017
【図１７】
0004718455.tif 000018
【図１８】
0004718455.tif 000019
【図１９】
0004718455.tif 000020
【図２０】
0004718455.tif 000021
【図２１】
0004718455.tif 000022
【図２２】
0004718455.tif 000023
【図２３】
0004718455.tif 000024
【図２４】
0004718455.tif 000025
【図２５】
0004718455.tif 000026