(57)【要約】【課題】より少ないレイテンシでメモリシャッフルすることのできるメモリシャッフル装置を提供すること。【解決手段】メモリ１の各アドレスにつき、その保持データが初期値であるべき第１状態又はこれとは異なる第２状態を示すフラグ情報を保持するフラグレジスタファイル３を持つ。メモリシャッフル部４は、メモリ１の或るアドレスを入力し、該或るアドレスに保持されるべきデータの初期値を出力する演算機能を備える。メモリシャッフル部４のメモリ交換部４５によりメモリ交換を行う際、対象の両アドレスにつき、フラグ情報を参照し、第１の状態ならば演算機能により当該アドレスの保持データを求め、第２の状態ならばメモリアクセスする。第１の状態では１回分のメモリアクセスが省略できる。【選択図】      図１
2005149412.tif 000002
【特許請求の範囲】
【請求項１】
乱数生成のもととなるデータを保持するメモリを、初期値を設定した後にシャッフルした状態にするためのメモリシャッフル装置において、
前記メモリにおける第１のアドレスを保持するための第1のアドレスレジスタと、
前記メモリにおける第２のアドレスを保持するための第２のアドレスレジスタと、
前記メモリの各アドレスごとに、前記メモリの当該アドレスに保持されているべきデータが初期値であることを示す第１の状態又は第１の状態とは異なる第２の状態を示すフラグ情報を保持するためのフラグレジスタファイルと、
前記メモリのアドレスを入力とし、前記メモリの当該アドレスに保持されるべきデータの初期値を出力とする初期値演算手段と、
前記メモリの前記第１のアドレスに保持されている第１のデータと、前記メモリの前記第２のアドレスに保持されている第２のデータとを交換するための交換手段と、
前記第１及び第２のアドレスレジスタに初期値を設定するとともに、前記交換の後には前記第１及び第２のアドレスレジスタに更新値を設定するための設定手段とを備え、
前記交換手段は、前記交換を行うにあたって、前記第１及び第２のアドレスそれぞれにつき、前記フラグ情報を参照して、前記第１の状態か前記第２の状態かを調べ、当該アドレスに対応する前記フラグ情報が前記第１の状態である場合には、前記メモリをアクセスせずに、前記初期値演算手段によって、前記メモリの当該アドレスに保持されるデータを求め、当該アドレスに対応する前記フラグ情報が前記第２の状態である場合には、前記メモリをアクセスして、前記メモリの当該アドレスに保持されるデータを求めることを特徴とするメモリシャッフル装置。
【請求項２】
前記メモリの各アドレスに対応する前記フラグ情報が示す前記第２の状態は、前記メモリの当該アドレスに保持されているべきデータが初期値でない可能性があることを示すものであり、
前記交換手段は、前記交換を行うにあたって、前記メモリの或るアドレスに対応する前記フラグ情報が前記第１の状態であったために、前記メモリをアクセスせずに、前記初期値演算手段によって、前記メモリの当該アドレスに保持されるデータを求めた場合には、当該アドレスに対応する前記フラグ情報を前記第２の状態に設定することを特徴とする請求項１に記載のメモリシャッフル装置。
【請求項３】
前記メモリの各アドレスに対応する前記フラグ情報が示す前記第２の状態は、前記メモリの当該アドレスに保持されているべきデータが初期値でないことを示すものであり、
前記交換手段は、前記交換を行うにあたって、前記メモリの或るアドレスに、前記メモリの他のアドレスに保持されていたデータを書き込む場合に、該データが、該或るアドレスに保持されるべき初期値に等しいときは、当該アドレスに対応する前記フラグ情報を前記第１の情報に設定し、等しくないときは、前記第２の情報に設定することを特徴とする請求項１に記載のメモリシャッフル装置。
【請求項４】
前記フラグレジスタファイルは、初期設定として、全てのアドレスに対応するフラグ情報を、前記第１の状態に設定することを特徴とする請求項１ないし３のいずれか１項に記載のメモリシャッフル装置。
【請求項５】
前記交換を予め定められた繰り返し回数だけ繰り返し実行させるための手段を更に備えたことを特徴とする請求項１ないし４のいずれか１項に記載のメモリシャッフル装置。
【請求項６】
前記設定手段は、前記第１又は第２のアドレスレジスタの少なくとも一方につき、前記繰り返し回数の交換の間に、前記メモリの全てのアドレスがそれぞれ少なくとも１回は保持されるように前記設定を行うことを特徴とする請求項５に記載のメモリシャッフル装置。
【請求項７】
前記繰り返し回数の交換が完了した後に、前記フラグ情報を参照して、前記メモリのアドレスのうちで、当該アドレスに対応する前記フラグ情報が前記第１の状態であるものを求め、対応する前記フラグ情報が前記第１の状態であるアドレスについては、それぞれ、前記初期値演算手段によって、前記メモリの当該アドレスに保持されるデータを求め、これを前記メモリの当該アドレスに書き込む手段を更に備えたことを特徴とする請求項５に記載のメモリシャッフル装置。
【請求項８】
前記交換に先立って、前記メモリの全てのアドレスに前記初期値を書き込む手段を更に備えたことを特徴とする請求項５に記載のメモリシャッフル装置。
【請求項９】
鍵情報を入力する手段と、
入力した鍵情報を記憶する手段とを更に備え、
前記設定手段は、前記第１又は第２のアドレスレジスタの少なくとも一方につき、前記更新値を求める方法として、前記鍵情報に依存した方法を用いることを特徴とする請求項１に記載のメモリシャッフル装置。
【請求項１０】
前記設定手段は、前記第１のアドレスレジスタにつき、前記更新値を求める方法として、前記第２のアドレスに依存した方法を用い、及び又は前記第２のアドレスレジスタにつき、前記更新値を求める方法として、前記第１のアドレスに依存した方法を用いることを特徴とする請求項１に記載のメモリシャッフル装置。
【請求項１１】
前記交換手段は、
前記メモリにアクセスして又は前記初期値演算手段によって求めた前記第１のデータを保持する第１のデータレジスタと、前記メモリにアクセスして又は前記初期値演算手段によって求めた前記第２のデータを保持する第２のデータレジスタとを含み、
前記交換にあたっては、前記第１及び第２のアドレスそれぞれにつき、前記フラグ情報を参照して、前記第１の状態か前記第２の状態かを調べ、前記第１のアドレスに対応する前記フラグ情報と前記第２のアドレスに対応する前記フラグ情報との両方が前記第１の状態である場合以外の場合には、前記第１のデータレジスタに一旦保持した第１のデータを、前記メモリの前記第２のアドレスに書き込み、前記第２のデータレジスタに一旦保持した第２のデータを、前記メモリの前記第１のアドレスに書き込むことを特徴とする請求項１に記載のメモリシャッフル装置。
【請求項１２】
前記交換手段は、前記交換にあたって、前記第１及び第２のアドレスそれぞれにつき、前記フラグ情報を参照して、前記第１の状態か前記第２の状態かを調べ、前記第１のアドレスに対応する前記フラグ情報と前記第２のアドレスに対応する前記フラグ情報との両方が前記第１の状態である場合には、前記初期値演算手段によって求めた第１のデータを一旦前記第１のデータレジスタに保持することと、前記初期値演算手段によって求めた第２のデータを前記メモリの前記第１のアドレスに書き込むこととを、第１のクロックで行い、前記第１のデータレジスタに一旦保持した第１のデータを、前記メモリの前記第２のアドレスに書き込むことを、第２のクロックで行うことを特徴とする請求項１１に記載のメモリシャッフル装置。
【請求項１３】
乱数生成のもととなるデータを保持するメモリを、初期値を設定した後にシャッフルした状態にするためのメモリシャッフル装置のメモリシャッフル方法において、
第1のアドレスレジスタにより指定される前記メモリの前記第１のアドレスに保持されている第１のデータと、第２のアドレスレジスタにより指定される前記メモリの前記第２のアドレスに保持されている第２のデータとを交換するための交換ステップと、
前記第１及び第２のアドレスレジスタに更新値を設定するためのステップと、
前記第１及び第２のステップを予め定められた繰り返し回数だけ繰り返し実行させるためのステップとを有し、
前記交換では、前記第１及び第２のアドレスそれぞれにつき、前記メモリの各アドレスごとに前記メモリの当該アドレスに保持されているべきデータが初期値であることを示す第１の状態又は第１の状態とは異なる第２の状態を示すフラグ情報を保持するためのフラグレジスタファイルを参照して、前記第１の状態か前記第２の状態かを調べ、当該アドレスに対応する前記フラグ情報が前記第１の状態である場合には、前記メモリをアクセスせずに、前記メモリのアドレスを入力とし前記メモリの当該アドレスに保持されるべきデータの初期値を出力とする初期値演算手段によって、前記メモリの当該アドレスに保持されるデータを求め、当該アドレスに対応する前記フラグ情報が前記第２の状態である場合には、前記メモリをアクセスして、前記メモリの当該アドレスに保持されるデータを求めることを特徴とするメモリシャッフル方法。
【請求項１４】
乱数生成のもととなるデータを保持するメモリを、初期値を設定した後にシャッフルした状態にするためのメモリシャッフル装置としてコンピュータを機能させるためのプログラムにおいて、
前記プログラムは、
第1のアドレス保持手段により指定される前記メモリの前記第１のアドレスに保持されている第１のデータと、第２のアドレス保持手段により指定される前記メモリの前記第２のアドレスに保持されている第２のデータとを交換するための交換ステップと、
前記第１及び第２のアドレス保持手段に更新値を設定するためのステップと、
前記第１及び第２のステップを予め定められた繰り返し回数だけ繰り返し実行させるためのステップとをコンピュータに実行させるとともに、
前記交換ステップでは、前記第１及び第２のアドレスそれぞれにつき、前記メモリの各アドレスごとに前記メモリの当該アドレスに保持されているべきデータが初期値であることを示す第１の状態又は第１の状態とは異なる第２の状態を示すフラグ情報を保持するためのフラグ情報保持手段を参照して、前記第１の状態か前記第２の状態かを調べ、当該アドレスに対応する前記フラグ情報が前記第１の状態である場合には、前記メモリをアクセスせずに、前記メモリのアドレスを入力とし前記メモリの当該アドレスに保持されるべきデータの初期値を出力とする初期値演算手段によって、前記メモリの当該アドレスに保持されるデータを求め、当該アドレスに対応する前記フラグ情報が前記第２の状態である場合には、前記メモリをアクセスして、前記メモリの当該アドレスに保持されるデータを求めさせるものであることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリの内容をシャッフルするメモリシャッフル装置、メモリシャッフル方法及びプログラムに関する。
【背景技術】
【０００２】
通信内容を秘密にするために暗号化技術が使われている。暗号化には、乱数発生器を用いるものがある。乱数発生器は、次のような原理に基づいて構成されている。乱数発生器は、内部状態を記憶する記憶装置と、記憶装置の内部状態を更新する手段と、記憶装置の内部状態に基づいて乱数を出力する手段をもっている。記憶装置の内部状態の初期値が鍵となる。
【０００３】
回路規模を小さくすることができることから、ＬＦＳＲによる擬似乱数発生を利用したストリーム暗号がよく使用されている。ＬＦＳＲに基づく乱数発生器では、シフトレジスタが上記の内部状態記憶装置になる。しかし、ＬＦＳＲに基づくストリーム暗号は安全性が低い問題がある。特に、回路の設計情報が分かると解読できてしまう問題がある。また、ソフトウェアでは速度が遅いという問題もある。
【０００４】
そこで、最近は、メモリ交換に基づくストリーム暗号が使われている。回路規模は小さくならないが、ソフトウェアでも高速にできるという特徴がある。アルゴリズムが知られることが、即、解読できることを意味しているわけではないという特徴もある。
【０００５】
メモリ交換に基づくストリーム暗号の乱数発生器は、内部状態記憶手段（メモリ上の配列）と、二つのアドレスレジスタとをもつ。１回の乱数生成では、二つのアドレスレジスタの内容を更新し、二つのアドレスレジスタから求められる第三のアドレス（例えば、二つのアドレスレジスタの和）のメモリの内容を乱数として出力し、二つのアドレスレジスタの指す番地の内容を交換する。
【０００６】
バリエーションとして考えられるのは、アドレスレジスタの更新方法と、第三のアドレスを求める方法である。
【０００７】
上述した乱数生成自体は、鍵に依存した操作ではない。セキュリティを確保するために、鍵に依存して乱数系列が変わるように、乱数生成の前に、メモリの内容を鍵に依存してシャッフルしておく。かりにメモリをシャッフルしないでアドレスレジスタの更新を鍵に依存して行ったとすると、出力される乱数系列は鍵との相関が高いものになってしまう。
【０００８】
メモリは、次のようにシャッフルする。上記の乱数生成と同じく二つのアドレスレジスタを用意する。まず、メモリをアドレスに依存した所定の値で初期化する（例えば、０番地には０を、１番地には１を、…、ｉ番地にはｉを書き込む）。そして、鍵に依存して二つのアドレスレジスタを更新し、二つのアドレスレジスタの指す番地の内容を交換する、という操作を、適当な回数繰り返す。このようにアドレスレジスタの更新を鍵に依存して行うことにより、メモリは鍵に依存してシャッフルされることになる。
【０００９】
なお、従来のシャッフルアルゴリズムは例えば非特許文献１に開示されている。
【非特許文献１】仙波一郎著、「組み合わせ数学」、コロナ社、１９９９年
【発明の開示】
【発明が解決しようとする課題】
【００１０】
メモリ交換に基づくストリーム暗号は、最近広く世の中で使われるようになってきている。無線ＬＡＮの標準であるＩＥＥＥ８０２．１１や、インターネットで安全にｗｅｂサイトにアクセスするためのＳＳＬ／ＴＬＳなどにも使用されている。高速な処理を要求するアプリケーションも増えてきており、従来のようにソフトウェアで処理するだけでなく、ハードウェアで処理されることも多くなってきている。
【００１１】
メモリ交換に基づくストリーム暗号をハードウェアで実現しようとしたとき、処理時間は必要とされるクロック数つまりレイテンシで測られることになる。メモリへのアクセスは少なくとも１クロックを必要とする操作であり、メモリ交換に基づくストリーム暗号の処理速度はメモリアクセス回数に支配されているといってよい。
【００１２】
一回の乱数生成は高々数クロック程度で完了するため、高速に行うことができる。鍵を異なる値に交換したときは、メモリシャッフルを最初からやりなおす必要があり、これには１０００クロック以上かかり、非常に時間がかかる。
【００１３】
このように、メモリ交換に基づくストリーム暗号は、乱数生成そのものは高速に行うことができるが、安全性を高めるために頻繁に鍵を交換しようとすると、毎回メモリシャッフルを行わなければならないのでレイテンシが増大し低速になってしまうという問題がある。
【００１４】
本発明は、上記事情を考慮してなされたものであり、より少ないレイテンシでメモリシャッフルすることのできるメモリシャッフル装置、メモリシャッフル方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明は、乱数生成のもととなるデータを保持するメモリを、初期値を設定した後にシャッフルした状態にするためのメモリシャッフル装置において、前記メモリにおける第１のアドレスを保持するための第1のアドレスレジスタと、前記メモリにおける第２のアドレスを保持するための第２のアドレスレジスタと、前記メモリの各アドレスごとに、前記メモリの当該アドレスに保持されているべきデータが初期値であることを示す第１の状態又は第１の状態とは異なる第２の状態を示すフラグ情報を保持するためのフラグレジスタファイルと、前記メモリのアドレスを入力とし、前記メモリの当該アドレスに保持されるべきデータの初期値を出力とする初期値演算手段と、前記メモリの前記第１のアドレスに保持されている第１のデータと、前記メモリの前記第２のアドレスに保持されている第２のデータとを交換するための交換手段と、前記第１及び第２のアドレスレジスタに初期値を設定するとともに、前記交換の後には前記第１及び第２のアドレスレジスタに更新値を設定するための設定手段とを備え、前記交換手段は、前記交換を行うにあたって、前記第１及び第２のアドレスそれぞれにつき、前記フラグ情報を参照して、前記第１の状態か前記第２の状態かを調べ、当該アドレスに対応する前記フラグ情報が前記第１の状態である場合には、前記メモリをアクセスせずに、前記初期値演算手段によって、前記メモリの当該アドレスに保持されるデータを求め、当該アドレスに対応する前記フラグ情報が前記第２の状態である場合には、前記メモリをアクセスして、前記メモリの当該アドレスに保持されるデータを求めることを特徴とする。
【００１６】
本発明によれば、メモリ交換に基づく乱数発生器（ストリーム暗号）の前処理として必要となるメモリシャッフルにおいて、メモリアクセスの回数を削減することができるので、メモリシャッフルに要するレイテンシを低減することができる。また、ハードウェアで実現する際に、なるべく少ない回路規模でレイテンシを節約してメモリシャッフルするメモリシャッフル装置が実現可能になる。セキュリティを高めるために鍵の変更を頻繁に行う応用に対しては高い効果が得られる。
【００１７】
なお、装置に係る本発明は方法に係る発明としても成立し、方法に係る本発明は装置に係る発明としても成立する。  
また、装置または方法に係る本発明は、コンピュータに当該発明に相当する手段を実行させるための（あるいはコンピュータを当該発明に相当する手段として機能させるための、あるいはコンピュータに当該発明に相当する機能を実現させるための）プログラムとしても成立し、該プログラムを記録したコンピュータ読み取り可能な記録媒体としても成立する。
【発明の効果】
【００１８】
本発明によれば、より少ないレイテンシでメモリシャッフルすることができる。
【発明を実施するための最良の形態】
【００１９】
以下、図面を参照しながら本発明の実施形態について説明する。
【００２０】
図１に、本発明の一実施形態に係る乱数生成装置の構成例を示す。
【００２１】
本乱数生成装置は、乱数生成のもととなる各データを保持するためのメモリ１、メモリ１に保持する各データの初期値を生成するための初期値生成部２、メモリ１に記憶された各データの内容が未だ更新されていない初期値の状態にあるか否かを示す情報を記憶するためのフラグレジスタファイル３、メモリ１に保持されているデータをシャッフルするためのメモリシャッフル部４、メモリ１に保持されているデータに基づいて乱数を発生するための乱数発生部５、装置全体の制御を司る制御回路（図示せず）、鍵情報等を入力したり、生成した乱数等を出力したりするための入出力部（図示せず）を備えている。なお、初期値生成部２は省いても構わない。
【００２２】
本実施形態のメモリシャッフル部４は、図１に示されるように、外部から与えられる鍵のデータ（鍵情報）を記憶するための鍵情報記憶部４１、第１のアドレスレジスタ４２、第２のアドレスレジスタ４３、アドレスレジスタ更新部４４、メモリ交換部４５を含む。なお、鍵情報を用いない場合には、鍵情報記憶部４１は省いて構わない。
【００２３】
なお、乱数発生部５は、公知の乱数生成装置の乱数発生部と同じもので構わない。図１には、乱数生成部５の一例を示してあり、この例では、乱数発生部５は、第１のアドレスレジスタ５１、第２のアドレスレジスタ５２、アドレスレジスタ更新部５３、選択部５４、メモリ交換部５５を含む。
【００２４】
また、初期値生成部２も、公知の初期値生成部の乱数発生部と同じもので構わない。
【００２５】
本実施形態では、ｎはメモリ１とフラグレジスタファイル３におけるアドレス空間の最大値を示すものとする。すなわち、メモリ１とフラグレジスタファイル３は、アドレスとして０番地からｎ番地までを指定でき、ｎ＋１個の内容を保持できることになる。
【００２６】
図１の乱数生成装置では、手順は、大きく次の３つのフェイズに分けられる。（１）まず、初期値生成部２が、制御回路の指示に従って、メモリ１の０番地からｎ番地までの各アドレスに設定する初期値を生成する。生成された各初期値は、各アドレスに設定される。（２）次に、メモリシャッフル部４が、制御回路の指示に従って、フラグレジスタファイル３とメモリ１を参照かつ書き込みながら、メモリ１のシャッフルを行う。（３）最後に、乱数発生部５が、制御回路の指示に従って、メモリ１を用いて乱数を生成する。なお、初期値生成部２を省く構成の場合には、もちろん、（１）の手順は省かれる。
【００２７】
以下、上記の（２）のメモリシャッフルについて詳しく説明する。（１）と（３）は、従来の手順と同様で構わない。
【００２８】
図２に、本実施形態におけるメモリシャッフルの手順の一例を示す。なお、図２では、各々のボックスが、処理単位であると同時に同クロック内で行う操作になっている。
【００２９】
前述のように、ｎはアドレス空間の最大値を示している。
【００３０】
Ｍ［ｉ］は、メモリ１のｉ番地の内容である。メモリ１は、ｉ番地を指定して内容を読み書きできる。フラグレジスタファイル３と異なり、メモリ１は、内容を読むのにも書くのにも、少なくとも１クロック以上のクロックが必要である。
【００３１】
Ｆ［ｉ］は、フラグレジスタファイル３のｉ番地の内容である。フラグレジスタファイル３は、アドレスを指定すると、対応する１ビットの内容を読み書きできる。フラグレジスタファイル３は、レジスタなので、クロックなしで読み出しを行える。ただし、書き込みには１クロックが必要である。
【００３２】
Ａ１は、第１のアドレスレジスタ４２の保持している内容である。Ａ２は、第１のアドレスレジスタ４３の保持している内容である。いずれも、少なくとも０からｎの値を保持できる。
【００３３】
ａ１は、第１のアドレスレジスタ４２の初期値である。ａ２は、第２のアドレスレジスタ４３の初期値である。なお、ａ１とａ２は、鍵に依存した値であってもよいし、依存しない値（例えば、ａ１＝０、ａ２＝１）であってもよい。
【００３４】
Ｄ１は、Ａ１が指すメモリ１の内容を読み出して保持するレジスタの内容である。Ｄ２は、Ａ２が指すメモリ１の内容を読み出して保持するレジスタの内容である。なお、これらレジスタは、図１では、省略している。
【００３５】
以下、関数について説明する。
【００３６】
なお、関数は、ハードウェアで実現する場合には、組み合わせ回路により構成される。この場合、１クロック内に関数の評価が終わることが望ましいが、複数クロックかかる順序回路であってもよい。
【００３７】
ｆ（ｘ）は、入力としてアドレスｘをとり、メモリ１のｘ番地に対応する初期値を出力する関数である。例えば、ｆ（ｘ）＝ｘでもよい。
【００３８】
ｇ１（ｘ）は、入力としてアドレスレジスタＡ１をとり、Ａ１の更新された値を出力する関数である。
【００３９】
ｇ２（ｘ）は、入力としてアドレスレジスタＡ２をとり、Ａ２の更新された値を出力する関数である。
【００４０】
なお、ｇ１は、鍵とＡ２とＤ２の全部又は一部に依存した関数であってもよいし、依存しない関数でもよい。また、ｇ１は、鍵とＡ１とＤ１の全部又は一部に依存した関数であってもよいし、依存しない関数でもよい。
【００４１】
以下、動作について説明する。
【００４２】
（ステップＳ１）
最初に、初期化を行う。初期化の内容は、以下の３つである。
【００４３】
・フラグレジスタの内容Ｆ［０］〜Ｆ［ｎ］をすべて０にする。ここでは、ｘ番地の内容Ｍ［ｘ］は、Ｆ［ｘ］＝０の場合にｆ（ｘ）と同じ状態（初期値の状態）であり、Ｆ［ｘ］＝１の場合にｆ（ｘ）と同じとは限らない状態（少なくとも一度は更新がなされた状態）であることを示すものとする。
【００４４】
・アドレスレジスタＡ１の内容を初期値ａ１にする。  
・アドレスレジスタＡ２の内容を初期値ａ２にする。
【００４５】
なお、ａ１とａ２は、例えば、鍵情報記憶部４１に記憶された鍵に基づいて生成される。
【００４６】
以下の処理は、１回の繰り返しで、１回のメモリ交換を行うことができ、これを所定の回数（ｍ回）繰り返す（ステップＳ１０）ことによって、メモリ１をシャッフルすることができる。なお、ｍは、任意の定数でかまわないが、鍵に依存したものであってもよい。
【００４７】
（ステップＳ２）
まず、フラグレジスタＦ［Ａ１］とＦ［Ａ２］を調べる。
【００４８】
ここで、フラグレジスタＦ［Ａ１］とＦ［Ａ２］の内容により、処理の流れが４通りになる。
【００４９】
（第１のケース）Ｆ［Ａ１］＝０かつＦ［Ａ２］＝０である場合
この場合、まず、１クロック目にステップＳ３の３つの独立した操作を行い、次いで、２クロック目にステップＳ９の４つの独立した操作を行う。
【００５０】
（ステップＳ３）
・Ｆ［Ａ１］＝０であることから、メモリ１におけるＡ１で示す番地の内容は実際にメモリ１を読まなくてもＭ［Ａ１］はｆ（Ａ１）に等しいことが分かるので、Ｄ１にはｆ（Ａ１）を書き込む。  
・Ａ１の指す番地のメモリＭ［Ａ１］には、本来、メモリ１におけるＡ２の指す番地の内容Ｍ［Ａ２］を書き込むのであるが、Ｆ［Ａ２］＝０であることから、実際にＭ［Ａ２］は読み出さなくても、ｆ（Ａ２）であることが分かっているので、Ｍ［Ａ１］にｆ（Ａ２）を書き込む。  
・上記のようにＡ１の指す番地のメモリＭ［Ａ１］を書き換えるので、以降、Ｍ［Ａ１］とｆ（Ａ１）が同じであるとは限らなくなる。このことを示すために、Ｆ［Ａ１］に１を書き込む。
【００５１】
これら３つの操作は独立しており、依存関係がないので、同一クロック内に行うことができる。
【００５２】
（ステップＳ９）
・Ａ２の指す番地のメモリＭ［Ａ２］にＤ１を書き込む。  
・上でＡ２の指す番地のメモリＭ［Ａ２］を書き換えるので、以降Ｍ［Ａ２］とｆ（Ａ２）が同じであるとは限らなくなる。このことを示すために、Ｆ［Ａ２］に１を書き込む。  
・アドレスレジスタＡ１の内容をｇ１（Ａ１）に更新する。  
・アドレスレジスタＡ２の内容をｇ２（Ａ２）に更新する。
【００５３】
なお、ｇ１とｇ２は、例えば、鍵情報記憶部４１に記憶された鍵に基づいて求められる。
【００５４】
これら４つの操作は独立しており、依存関係がないので、同一クロック内に行うことができる。
【００５５】
なお、このステップＳ９は、全てのケースにおいて行われる操作である。
【００５６】
この第１のケースでは、メモリ読み込み２回に必要なクロック（２クロック）を節約でき、計２クロックでメモリの交換を行うことができる。
【００５７】
（第２のケース）Ｆ［Ａ１］＝１かつＦ［Ａ２］＝０である場合
この場合、まず、１クロック目にステップＳ４の２つの独立した操作を行い、次いで、２クロック目のステップＳ８の２つの独立した操作を行い、最後に、３クロック目にステップＳ９の４つの独立した操作を行う。
【００５８】
（ステップＳ４）
・Ｆ［Ａ１］＝１であることから、Ｍ［Ａ１］がｆ（Ａ１）に等しいとは限らないので、実際にメモリ１を読まなければならない。すなわち、Ｍ［Ａ１］を読み出して、これをＤ１に保持する。  
・Ｆ［Ａ２］＝０であることから、メモリ１におけるＡ２で示す番地の内容Ｍ［Ａ２］は、実際にメモリ１を読まなくてもｆ（Ａ２）に等しいことが分かるので、Ｄ２にはｆ（Ａ２）を書き込む。
【００５９】
これら２つの操作は独立しており、依存関係がないので、同一クロック内に行うことができる。
【００６０】
（ステップＳ８）
・Ａ１の指す番地のメモリＭ［Ａ１］にＤ２を書き込む。  
・上記のようにＡ１の指す番地のメモリＭ［Ａ１］を書き換えるので、以降、Ｍ［Ａ１］とｆ（Ａ１）が同じであるとは限らなくなる。このことを示すために、Ｆ［Ａ１］に１を書き込む。
【００６１】
これら２つの操作は独立しており、依存関係がないので同一クロック内に行うことができる。
【００６２】
なお、このステップＳ８は、第２のケース〜第４のケースにおいて行われる操作である。
【００６３】
（ステップＳ９）
前述したように４つの独立した処理を行う。
【００６４】
この第２のケースでは、メモリ読み込み１回に必要なクロック（１クロック）を節約でき、計３クロックでメモリの交換を行うことができる。
【００６５】
（第３のケース）Ｆ［Ａ１］＝０かつＦ［Ａ２］＝１である場合
この場合、まず、１クロック目にステップＳ５の２つの独立した操作を行い、次いで、２クロック目のステップＳ８の２つの独立した操作を行い、最後に、３クロック目にステップＳ９の４つの独立した操作を行う。
【００６６】
（ステップＳ５）
・Ｆ［Ａ１］＝０であることから、メモリ１におけるＡ１で示す番地の内容Ｍ［Ａ１］は、実際にメモリ１を読まなくてもｆ（Ａ１）に等しいことが分かるので、Ｄ１にはｆ（Ａ１）を書き込む。  
・Ｆ［Ａ２］＝１であることから、Ｍ［Ａ２］がｆ（Ａ２）に等しいとは限らないので、実際にメモリ１を読まなければならない。すなわち、Ｍ［Ａ２］を読み出して、これをＤ２に保持する。
【００６７】
これらの２つの操作は独立しており、依存関係がないので、同一クロック内に行うことができる。
【００６８】
（ステップＳ８）
第２のケースと同様に２つの独立した処理を行う。
【００６９】
（ステップＳ９）
前述したように４つの独立した処理を行う。
【００７０】
この第３のケースでは、メモリ読み込み１回に必要なクロック（１クロック）を節約でき、計３クロックでメモリの交換を行うことができる。
【００７１】
（第４のケース）Ｆ［Ａ１］＝１かつＦ［Ａ２］＝１である場合
この場合、まず、１クロック目にステップＳ６の操作を行い、２クロック目にステップＳ７の操作を行い、次いで、３クロック目のステップＳ８の２つの独立した操作を行い、最後に、４クロック目にステップＳ９の４つの独立した操作を行う。
【００７２】
なお、ステップＳ６とステップＳ７とを逆の順番で行っても構わない。
【００７３】
（ステップＳ６）
Ｆ［Ａ１］＝１であることから、Ｍ［Ａ１］とｆ（Ａ１）が同じであるとは限らないので、実際にメモリ１を読まなければならない。すなわち、Ｍ［Ａ１］を読み出して、これをＤ１に保持する。
【００７４】
（ステップＳ７）
Ｆ［Ａ２］＝１であることから、Ｍ［Ａ２］とｆ（Ａ２）が同じであるとは限らないので、実際にメモリ１を読まなければならない。すなわち、Ｍ［Ａ２］を読み出して、これをＤ２に保持する。
【００７５】
（ステップＳ８）
第２，３のケースと同様に２つの独立した処理を行う。
【００７６】
（ステップＳ９）
前述したように４つの独立した処理を行う。
【００７７】
この第４のケースでは、計４クロックでメモリの交換を行うことができる。
【００７８】
なお、ステップＳ６の操作とステップＳ７の操作とは、独立していて、依存関係はないが、メモリ１に通常のメモリ装置に対しては、異なるアドレスに対する読み出しを同クロック内に行うことはできないので、２つのクロックが必要となる。ただし、メモリ１にデュアルポートメモリを使用する場合には、同クロック内で２つの異なるアドレスに対する読み出しを行うことができ、この場合には、必要となるクロック数を節約することができる。
【００７９】
前述したように、１回の繰り返しで、第１のケース〜第４のケースのいずれかの処理が実行され、１回のメモリ交換を行うことができ、これをｍ回繰り返す（ステップＳ１０）ことによって、メモリ１がシャッフルされる。
【００８０】
なお、初期値ａ１，初期値ａ２，関数ｇ１，関数ｇ２，繰り返し回数ｍの少なくとも一つは、鍵に依存した関数にすると、好ましい。
【００８１】
ところで、初期値ａ１，初期値ａ２，関数ｇ１，関数ｇ２，繰り返し回数ｍによっては、メモリの全ての番地（０〜ｎ）が交換の対象とはならず、結果として、ある番地ｘに対してはメモリシャッフルの処理が完了してもＦ［ｘ］＝０のままである場合があり得る。
【００８２】
初期値生成部２を省く構成においては、このように場合には、ｘ番地のメモリＭ［ｘ］の内容は一度も書き込みが行われていないので、何が書き込まれているかは不定である。従って、Ｆ［ｘ］＝０であるようなｘが存在する場合には、Ｍ［ｘ］にはｆ（ｘ）を書き込んでやる必要がある。
【００８３】
このような状況を避けるためには、Ａ１とＡ２の一方又は両方がメモリの全ての番地を値としてとるようにすればよい。例えば、ａ１＝０とし、ｇ１（ｘ）＝ｘ＋１とし、繰り返し回数をｎ＋１回とすることでＡ１は０〜ｎの値をとることが保証される。
【００８４】
また、上記の例では、ある番地ｘについて、Ｆ［ｘ］＝０は、Ｍ［ｘ］とｆ（ｘ）が一致していることを意味し、Ｆ［ｘ］＝１は、Ｍ［ｘ］とｆ（ｘ）が一致しているとは限らないことを意味するものとした。しかし、場合によっては、初期状態以外であっても、Ｍ［ｘ］にｆ（ｘ）が書き込まれることもあり得る。そこで、Ｍ［ｘ］とｆ（ｘ）とを比較して、Ｍ［ｘ］＝ｆ（ｘ）であればＦ［ｘ］に０を、そうでなければ１を書き込むようにしてもよい（この場合、ある番地ｘについて、Ｆ［ｘ］＝０は、Ｍ［ｘ］とｆ（ｘ）が一致していることを意味し、Ｆ［ｘ］＝１は、Ｍ［ｘ］とｆ（ｘ）が一致していないことを意味することになる）。これによって、レイテンシをより少なくすることができる。
【００８５】
図３に、図２の動作を行うシャッフル部４をハードウェアで実現した場合の構成例を示す。
【００８６】
２つのアドレスレジスタＡ１とＡ２は、それぞれ、関数ｇ１とｇ２によって更新される。
【００８７】
データレジスタＤ１には、ｆ（Ａ１）またはメモリからの入力Ｍｏｕｔをセレクタｓ１で切り替えた入力が書き込まれる。データレジスタＤ２には、ｆ（Ａ２）またはメモリからの入力Ｍｏｕｔをセレクタｓ２で切り替えた入力が書き込まれる。
【００８８】
メモリへの書き込みＭｉｎへは、Ｄ１またはＤ２をセレクタｓ４で切り替えた内容が出力される。
【００８９】
メモリのアドレス入力Ａｉｎへは、Ａ１またはＡ２をセレクタｓ３で切り替えた内容が出力される。
【００９０】
アドレスレジスタＡ１とＡ２の内容は、それぞれ、フラグレジスタファイルｆへ出力される。
【００９１】
各セレクタは、制御部（図示せず）によって、切り替えられる。
【００９２】
次に、乱数発生部５について簡単に説明する。
【００９３】
乱数発生部５は、メモリシャッフルされたメモリ１の内容をランダムに読み出して、これを乱数として出力するものである。乱数発生部５は、公知のもので構わない。
【００９４】
図１に例示した構成の場合には、例えば、まず、第１のアドレスレジスタ５１と第２のアドレスレジスタ５２の内容ｉとｊに初期値を設定し、選択部５４は、それらを加算した値ｉ＋ｊを番地とするメモリの内容を読み出して、これを乱数値とする。メモリ交換部５５は、メモリのうち、ｉ番地とｊ番地の内容を入れ替える。そして、アドレスレジスタ更新部５３は、第１のアドレスレジスタ５１と第２のアドレスレジスタ５２の内容を更新する。選択部５４は、それらを加算した値ｉ＋ｊを番地とするメモリの内容を読み出して、これを次の乱数値とする。メモリ交換部５５は、メモリのうち、ｉ番地とｊ番地の内容を入れ替える。これを必要なだけ繰り返し行う。
【００９５】
次に、図４に、本実施形態におけるメモリシャッフルの手順の他の例を示す。
【００９６】
本例は、関数ｇ２が、（Ａ１が指すメモリ１の内容を読み出して保持する）レジスタＤ１の保持している内容に依存する場合の例を示している。
【００９７】
本例は、例えば、無線ＬＡＮの標準ＩＥＥＥ８０２．１１で使用されているストリーム暗号に適用可能である。ここでは、メモリの各番地には８ビット（０〜２５５）の数値を格納でき、アドレスの最大値ｎは２５５である場合を例にとって説明する。
【００９８】
本例では、アドレスレジスタＡ２の内容は、レジスタＤ１の内容が決まるまでは決定できないため、Ａ２の内容をｇ２によって更新する操作の部分が図２の処理手順とは異なっている。
【００９９】
ここで、各定数と各関数の一例を以下に示す。
【０１００】
ｎ＝２５５  
ａ１＝０  
ａ２＝１  
ｆ（ｘ）＝ｘ  
ｇ１（Ａ１）＝Ａ１＋１  
ｇ２（Ａ２，Ｄ１，ｋ）＝（Ａ２＋Ｄ１＋ｋ）  ｍｏｄ  ２５６
ただし、ｋは、（鍵情報記憶部４１に記憶されている）鍵系列の入力であり、Ａ１に依存している。ｋｅｙを鍵のバイト配列（key[0],key[1],key[2],key[3],…）、ｋｅｙｌｅｎを鍵のバイト長とすると、ｋは次のように定義される。ｋ＝ｋｅｙ［Ａ１  ｍｏｄ  ｋｅｙｌｅｎ］
従来技術では、Ｍ［０］〜Ｍ［２５５］に０〜２５５を書き込むための２５６回のメモリアクセスと、２５６回のメモリ交換（１回のメモリ交換につき４回のメモリアクセス）を行うための１０２４回のメモリアクセスとの計１２８０回のメモリアクセスが必要であるが、本例によれば、初期値生成部２を省く構成の場合にはＭ［０］〜Ｍ［２５５］にはあらかじめ何も書き込まないので、初期値を書き込む２５６回のメモリアクセスを節約でき、２５６回のメモリ交換のうち２５６回のメモリ参照を節約できるので、１０２４−２５６＝７６８回のメモリアクセスの計７６８回に低減されている。
【０１０１】
なお、以上では、メモリがシングルポートの場合について説明したが、デュアルポートである場合も同様の構成をとることができ、レイテンシを削減することができる。
【０１０２】
また、アドレスの更新関数は、一般的に鍵に依存した関数であるが、ここでは陽には示さなかった。これは、鍵に依存する関数であれば、任意の関数にすることが可能なためである。
【０１０３】
なお、以上の各機能は、ソフトウェアとして記述し適当な機構をもったコンピュータに処理させても実現可能である。  
また、本実施形態は、コンピュータに所定の手段を実行させるための、あるいはコンピュータを所定の手段として機能させるための、あるいはコンピュータに所定の機能を実現させるためのプログラムとして実施することもできる。加えて該プログラムを記録したコンピュータ読取り可能な記録媒体として実施することもできる。
【０１０４】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１０５】
【図１】本発明の一実施形態に係る乱数生成装置の構成例を示す図
【図２】同本実施形態におけるメモリシャッフルの動作手順の一例を示す図
【図３】図２の動作を行うシャッフル部をハードウェアで実現した場合の構成例を示す図
【図４】同本実施形態におけるメモリシャッフルの動作手順の一例（ＩＥＥＥ８０２．１１標準に適用した例）を示す図
【符号の説明】
【０１０６】
１…メモリ、２…初期値生成部、３…フラグレジスタファイル、４…メモリシャッフル部、５…乱数発生部、４１…鍵情報記憶部、４２，４３，５１，５２…アドレスレジスタ、４４，５３…アドレスレジスタ更新部、４５，５５…メモリ交換部、５４…選択部
【図１】
2005149412.tif 000003
【図２】
2005149412.tif 000004
【図３】
2005149412.tif 000005
【図４】
2005149412.tif 000006