(57)【要約】【課題】アクセスパターンの保護に適した記憶装置を提供する。【解決手段】アクセス領域に格納されている暗号化データＥ（ｘ）に対してアクセスを行う場合に、任意のアクセスパターンの保護方法を用いて、暗号化データを安全なキャッシュに移動させるデータ移動手段と、暗号化データを安全なキャッシュに移動させた後に、データを復号する復号手段と、復号したデータｘとデータｘに対して何度アクセスを行ったかを記録したシーケンス番号とを保管する保管手段と、データｘを用いた処理が完了し、データをメインメモリに移動させる際に、データｘにシーケンス番号を付加した情報に対して、暗号化データＥ（ｘ）を生成した際に用いた鍵と同一の鍵を用いて暗号化した情報Ｅ（ｘ）´を生成する暗号化手段と、暗号化手段により暗号化された情報Ｅ（ｘ）´を元のアクセス領域に格納する格納手段と、を備える。【選択図】図３
2015011452.tif 000002
【特許請求の範囲】
【請求項１】
メモリをデータのアクセス領域と非アクセス領域とに分割し、履歴データを記憶する記憶領域を備えた記憶装置であって、
前記アクセス領域に格納されている暗号化データＥ（ｘ）に対してアクセスを行う場合に、任意のアクセスパターンの保護方法を用いて、前記暗号化データを安全なキャッシュに移動させるデータ移動手段と、
前記暗号化データを安全なキャッシュに移動させた後に、データを復号する復号手段と、
該復号したデータｘと前記データｘに対して何度アクセスを行ったかを記録したシーケンス番号とを保管する保管手段と、
前記データｘを用いた処理が完了し、データをメインメモリに移動させる際に、前記データｘに前記シーケンス番号を付加した情報に対して、暗号化した情報Ｅ（ｘ）´を生成する暗号化手段と、
該暗号化手段により暗号化された情報Ｅ（ｘ）´を元の前記アクセス領域に格納する格納手段と、
を備えたことを特徴とする記憶装置。
【請求項２】
メモリをデータのアクセス領域と非アクセス領域とに分割し、履歴データを記憶する記憶領域を備えた記憶装置であって、
前記アクセス領域に格納されている暗号化データＥ（ｘ）に対してアクセスを行う場合に、任意のアクセスパターンの保護方法を用いて、前記暗号化データを安全なキャッシュに移動させるデータ移動手段と、
前記暗号化データを安全なキャッシュに移動させた後に、データを復号する復号手段と、
該復号したデータｘと前記データｘに対して何度アクセスを行ったかを記録したシーケンス番号とを保管する保管手段と、
前記データｘを用いた処理が完了し、データをメインメモリに移動させる際に、前記データｘと前記シーケンス番号との演算を行った情報に対して、暗号化した情報Ｅ（ｘ）´を生成する暗号化手段と、
該暗号化手段により暗号化された情報Ｅ（ｘ）´を元の前記アクセス領域に格納する格納手段と、
を備えたことを特徴とする記憶装置。
【請求項３】
前記暗号化手段が、前記暗号化データＥ（ｘ）を生成した際に用いた鍵と同一の鍵を用いて暗号化した情報Ｅ（ｘ）´を生成することを特徴とする請求項１または請求項２に記載の記憶装置。
【請求項４】
前記暗号化手段が、少なくとも、
ＣＰＵのワードサイズに相当する暗号化する情報と前記暗号化データＥ（ｘ）を生成した際に用いた鍵と同一の鍵とを入力する入力手段と、
複数の非線形関数器と、
前記暗号化する情報を攪拌する攪拌手段と、
を備えたことを特徴とする請求項１から請求項３のいずれかに記載の記憶装置。
【請求項５】
暗号化情報を出力する出力手段を備え、
前記攪拌手段が、偏りなく攪拌されるように、前記入力手段の出力部および前記出力手段の入力部に設けられた排他的論理和演算器であり、前記出力手段が該攪拌された情報と前記暗号化データＥ（ｘ）を生成した際に用いた鍵と同一の鍵とを入力して暗号化情報を出力することを特徴とする請求項４に記載の記憶装置。
【請求項６】
前記攪拌手段が、ＳｈｉｆｔＲｏｗであって、攪拌後の情報をＭｉｘＣｏｌｕｍｎで処理して、暗号化情報を出力することを特徴とする請求項４に記載の記憶装置。
【請求項７】
前記アクセスパターンの保護方法が、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第１のステップと、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第２のステップと、
１つのデータにアクセスが生じたときに、２つのデータを選択し、前記アクセス領域と非アクセス領域との間でデータ交換を行う際に、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが前記アクセス領域および履歴領域に存在せず、前記非アクセス領域に存在し、前記履歴領域に保存されたデータがある場合に、前記アクセスを行うデータと前記履歴領域に保存された任意のデータとを前記２つのデータとして選択して、前記アクセス領域に移動して、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動して保存する第３のステップと、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第４のステップと、
を備えたことを特徴とする請求項１から請求項６のいずれかに記載の記憶装置。
【請求項８】
前記アクセスパターンの保護方法が、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第１のステップと、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第２のステップと、
１つのデータにアクセスが生じたときに、２つのデータを選択し、前記アクセス領域と非アクセス領域との間でデータ交換を行う際に、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが履歴領域に保存されている場合に、前記履歴領域に保存されていないデータをランダムに選択し、前記アクセスを行うデータと前記ランダムに選択したデータとを前記２つのデータとし、前記アクセス領域に移動して、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動して保存する第３のステップと、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第４のステップと、
を備えたことを特徴とする請求項１から請求項６のいずれかに記載の記憶装置。
【請求項９】
前記アクセスパターンの保護方法が、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第１のステップと、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第２のステップと、
１つのデータにアクセスが生じたときに、２つのデータを選択し、前記アクセス領域と非アクセス領域との間でデータ交換を行う際に、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが前記アクセス領域に保存されている場合に、前記非アクセス領域と履歴領域とからランダムに選択したデータを前記２つのデータとし、前記アクセス領域に移動して、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記非アクセス領域に移動し、これらのデータを前記履歴領域に保存する第３のステップと、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第４のステップと、
を備えたことを特徴とする請求項１から請求項６のいずれかに記載の記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アクセスパターンの保護に適した記憶装置に関する。
【背景技術】
【０００２】
近年、暗号に対するサイドチャネル攻撃と呼ばれる攻撃が大きな問題となっている。ソフトウェアに対するサイドチャネル攻撃としては、メモリアクセスを解析し秘密情報を復元する攻撃がある。こうした攻撃に対応して、メモリアクセスを攻撃者から保護するためにＯｂｌｉｖｉｏｕｓ ＲＡＭが注目を集めている（例えば、非特許文献１および非特許文献２参照。）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｏｄｅｄ  Ｇｏｌｄｒｅｉｃｈ  ａｎｄ  Ｒａｆａｉｌ  Ｏｓｔｒｏｖｓｋｙ,  “Ｓｏｆｔｗａｒｅ  ｐｒｏｔｅｃｔｉｏｎ  ａｎｄ  ｓｉｍｕｌａｔｉｏｎ  ｏｎ  ｏｂｌｉｖｉｏｕｓ  ＲＡＭＳ,”  Ｊ.ＡＣＭ,４３（３）：４３１−４７３, １９９６.
【非特許文献２】Ｊｏａｎ  Ｄａｅｍｅｎ, Ｖｉｎｃｅｎｔ  Ｒｉｊｍｅｎ，“Ｔｈｅ  ｄｅｓｉｇｎ  ｏｆ  Ｒｉｊｎｄａｅｌ  ＡＥＳ  Ａｄｖａｎｃｅｄ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ“，  Ｓｐｒｉｎｇｅｒ，  ２００２．
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ところが、非特許文献１などで検討されているＯｂｌｉｖｉｏｕｓ  ＲＡＭによるメモリの保護は、安全な暗号方式によってデータは保護されているとの前提のもとに、アクセスのパターンを保護することでメモリへのアクセスを保護している。ＯＲＡＭによってデータにアクセスを行う場合、それがデータの変化を伴わない読み出し処理であっても、読み出し処理であったという事実を保護するためにデータをメモリに戻す際にデータが別の値に変化している必要がある。これを実現する最もシンプルな方法は、データごとに異なる鍵を用意し、アクセスのたびに鍵の更新と新しい鍵での再暗号化を行う方式である。しかし、この方式では、データの分だけ鍵を用意し、それを安全に保管しておく必要があるため、現実的ではない。
【０００５】
そこで、本発明は、上述の課題に鑑みてなされたものであり、アクセスパターンの保護に適した記憶装置を提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、上記の課題を解決するために、以下の事項を提案している。
【０００７】
（１）本発明は、メモリをデータのアクセス領域と非アクセス領域とに分割し、履歴データを記憶する記憶領域を備えた記憶装置であって、前記アクセス領域に格納されている暗号化データＥ（ｘ）に対してアクセスを行う場合に、任意のアクセスパターンの保護方法を用いて、前記暗号化データを安全なキャッシュに移動させるデータ移動手段と、前記暗号化データを安全なキャッシュに移動させた後に、データを復号する復号手段と、該復号したデータｘと前記データｘに対して何度アクセスを行ったかを記録したシーケンス番号とを保管する保管手段と、前記データｘを用いた処理が完了し、データをメインメモリに移動させる際に、前記データｘに前記シーケンス番号を付加した情報に対して、暗号化した情報Ｅ（ｘ）´を生成する暗号化手段と、該暗号化手段により暗号化された情報Ｅ（ｘ）´を元の前記アクセス領域に格納する格納手段と、を備えたことを特徴とする記憶装置を提案している。
【０００８】
（２）本発明は、メモリをデータのアクセス領域と非アクセス領域とに分割し、履歴データを記憶する記憶領域を備えた記憶装置であって、前記アクセス領域に格納されている暗号化データＥ（ｘ）に対してアクセスを行う場合に、任意のアクセスパターンの保護方法を用いて、前記暗号化データを安全なキャッシュに移動させるデータ移動手段と、前記暗号化データを安全なキャッシュに移動させた後に、データを復号する復号手段と、該復号したデータｘと前記データｘに対して何度アクセスを行ったかを記録したシーケンス番号とを保管する保管手段と、前記データｘを用いた処理が完了し、データをメインメモリに移動させる際に、前記データｘと前記シーケンス番号との演算を行った情報に対して、暗号化した情報Ｅ（ｘ）´を生成する暗号化手段と、該暗号化手段により暗号化された情報Ｅ（ｘ）´を元の前記アクセス領域に格納する格納手段と、を備えたことを特徴とする記憶装置を提案している。
【０００９】
（３）本発明は、（１）または（２）の記憶装置について、前記暗号化手段が、前記暗号化データＥ（ｘ）を生成した際に用いた鍵と同一の鍵を用いて暗号化した情報Ｅ（ｘ）´を生成することを特徴とする記憶装置を提案している。
【００１０】
（４）本発明は、（１）から（３）のいずれかの記憶装置について、前記暗号化手段が、少なくとも、ＣＰＵのワードサイズに相当する暗号化する情報と前記暗号化データＥ（ｘ）を生成した際に用いた鍵と同一の鍵とを入力する入力手段と、複数の非線形関数器と、前記暗号化する情報を攪拌する攪拌手段と、を備えたことを特徴とする記憶装置を提案している。  
【００１１】
（５）本発明は、（４）の記憶装置について、暗号化情報を出力する出力手段を備え、前記攪拌手段が、偏りなく攪拌されるように、前記入力手段の出力部および前記出力手段の入力部に設けられた排他的論理和演算器であり、前記出力手段が該攪拌された情報と前記暗号化データＥ（ｘ）を生成した際に用いた鍵と同一の鍵とを入力して暗号化情報を出力することを特徴とする記憶装置を提案している。
【００１２】
（６）本発明は、（４）の記憶装置について、前記攪拌手段が、ＳｈｉｆｔＲｏｗであって、攪拌後の情報をＭｉｘＣｏｌｕｍｎで処理して、暗号化情報を出力することを特徴とする記憶装置を提案している。
【００１３】
（７）本発明は、（１）から（６）のいずれかの記憶装置について、前記アクセスパターンの保護方法が、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第１のステップと、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第２のステップと、１つのデータにアクセスが生じたときに、２つのデータを選択し、前記アクセス領域と非アクセス領域との間でデータ交換を行う際に、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが前記アクセス領域および履歴領域に存在せず、前記非アクセス領域に存在し、前記履歴領域に保存されたデータがある場合に、前記アクセスを行うデータと前記履歴領域に保存された任意のデータとを前記２つのデータとして選択して、前記アクセス領域に移動して、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動して保存する第３のステップと、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第４のステップと、を備えたことを特徴とする記憶装置を提案している。
【００１４】
（８）本発明は、（１）から（６）のいずれかの記憶装置について、前記アクセスパターンの保護方法が、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第１のステップと、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第２のステップと、１つのデータにアクセスが生じたときに、２つのデータを選択し、前記アクセス領域と非アクセス領域との間でデータ交換を行う際に、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが履歴領域に保存されている場合に、前記履歴領域に保存されていないデータをランダムに選択し、前記アクセスを行うデータと前記ランダムに選択したデータとを前記２つのデータとし、前記アクセス領域に移動して、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記履歴領域に移動して保存する第３のステップと、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第４のステップと、を備えたことを特徴とする記憶装置を提案している。
【００１５】
（９）本発明は、（１）から（６）のいずれかの記憶装置について、前記アクセスパターンの保護方法が、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える第１のステップと、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる第２のステップと、１つのデータにアクセスが生じたときに、２つのデータを選択し、前記アクセス領域と非アクセス領域との間でデータ交換を行う際に、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが前記アクセス領域に保存されている場合に、前記非アクセス領域と履歴領域とからランダムに選択したデータを前記２つのデータとし、前記アクセス領域に移動して、移動したデータサイズに応じて、前記アクセス領域にあった任意のデータを前記非アクセス領域に移動し、これらのデータを前記履歴領域に保存する第３のステップと、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す第４のステップと、を備えたことを特徴とする記憶装置を提案している。
【発明の効果】
【００１６】
本発明によれば、アクセスをするデータを安全な領域で復号し、メモリに移動させる際に、データとシーケンス番号を結合したもの、もしくは、データとシーケンス番号とを演算したものを暗号化して格納する。したがって、シーケンス番号はアクセスの度に変化するため、データが変化しない場合でも暗号化されたデータは変化し、アクセスの種類を秘匿することができるという効果がある。
【００１７】
また、本発明によれば、上記暗号化の際に、常に、同じ鍵を用いるため、使用メモリ量の増加を抑制することができるという効果がある。特に、本発明は、アクセスパターンの保護を目的とする手法において用いるとより効果がある。
【図面の簡単な説明】
【００１８】
【図１】本発明に係る記憶装置の構成を示す図である。
【図２】本発明に係る記憶装置の処理の概略を示す図である。
【図３】本発明に係る記憶装置における暗号化の概略を示す図である。
【図４】本発明に係る記憶装置における暗号化部の構成を示す図である。
【図５】本発明に係る記憶装置における暗号化部の構成を示す図である。
【図６】本発明に係る記憶装置における暗号化部による入力データと攪拌後のデータとの関係を示す図である。
【図７】本発明の第１の実施形態に係るアクセスパターン保護部の構成を示す図である。
【図８】本発明の第１の実施形態に係るアクセスパターン保護部の処理を示す図である。
【図９】本発明の第２の実施形態に係る記憶装置におけるアクセスパターン保護部の構成を示す図である。
【図１０】本発明の第２の実施形態に係る記憶装置におけるアクセスパターン保護部の処理を示す図である。
【図１１】本発明の第３の実施形態に係る記憶装置におけるアクセスパターン保護部の構成を示す図である。
【図１２】本発明の第３の実施形態に係る記憶装置におけるアクセスパターン保護部の処理を示す図である。
【図１３】本発明の実施例に係るアクセス時の記憶領域内のデータの遷移を示す図である。
【図１４】本発明の実施例に係るアクセスパターン保護部の処理を示す図である。
【図１５】本発明の実施例に係るアクセスパターン保護部の処理を示す図である。
【発明を実施するための形態】
【００１９】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００２０】
＜記憶装置の構成＞
図１から図６を用いて、本発明の記憶装置の構成について説明する。
本発明の記憶装置は、図１に示すように、アクセスパターン保護部１００と、記憶領域２００と、データ移動部１０と、キャッシュ部２０と、復号化部３０と、保管部４０と、暗号化部５０とから構成されている。なお、アクセスパターン保護部１００の詳細については、後述する。
【００２１】
記憶領域２００は、メモリをデータのアクセス領域と非アクセス領域と履歴領域とに分割されている。なお、アクセス領域、非アクセス領域、履歴領域は、ＤＲＡＭ、ＳＲＡＭ等の書き換え可能なメモリで構成される。また、アクセス領域を耐タンパ性を備えたＤＲＡＭ、ＳＲＡＭ等の書き換え可能なメモリで構成してもよい。なお、本発明の記憶装置は、例えば、ＲＡＭ等の一般的な記憶装置ばかりでなく、ＳＩＭやＩＣカード等の記憶媒体も含むものである。
【００２２】
データ移動部１０は、記憶領域２００内のアクセス領域に格納されている暗号化データＥ（ｘ）に対してアクセスを行う場合に、任意のアクセスパターンの保護方法を用いて、暗号化データを安全なキャッシュ部２０（例えば、レジスタ）に移動させる。なお、アクセスパターンの保護方法については、その例を後述する。
【００２３】
復号化部３０は、暗号化データを安全なキャッシュ部２０に移動させた後に、データを復号する。保管部４０は、復号したデータｘとデータｘに対して何度アクセスを行ったかを記録したシーケンス番号とを保管する。なお、暗号化処理を行う前には、すべてのシーケンス番号を保管するが、暗号化処理後は、後述する暗号化方法のうち、データｘとシーケンス番号とを演算した情報に対して、暗号化した場合にのみ、シーケンス番号を保管する。
【００２４】
暗号化部５０は、データｘを用いた処理が完了し、データをメインメモリに移動させる際に、データｘにシーケンス番号を付加した情報あるいはデータｘとシーケンス番号とを演算した情報に対して、暗号化した情報Ｅ（ｘ）´を生成する。なお、暗号化に用いる鍵は、暗号化データＥ（ｘ）を生成した際に用いた鍵と同一の鍵を用いることが好ましい。
【００２５】
つまり、図２に示すように、データＥ（ｘ）に対して、アクセスする場合には、このデータをまず、安全な領域であるキャッシュ部２０に移動し、ここで、復号化してデータｘを取り出す。データｘに対して処理が終了すると、暗号化部５０において、図３に例示するように、データｘにシーケンス番号ｃを付加した情報あるいはデータｘとシーケンス番号ｃとを演算した情報に対して、暗号化データＥ（ｘ）を生成した際に用いた鍵と同一の鍵を用いて暗号化した情報Ｅ（ｘ）´を生成し、これをメモリに戻す。なお、データＥ（ｘ）の暗号化も上述の情報Ｅ（ｘ）´の暗号化と同様の手法で行われる。したがって、アクセスデータに対する処理の前後において、異なった情報がメモリに戻されるため、例えば、不正な攻撃者にアクセスパターンが漏洩することを防止することができる。なお、暗号化部５０については、その詳細を後述する。
【００２６】
＜暗号化部の構成＞
図４および図５は、本発明の暗号化部５０内部の構成の一例を示している。なお、図４および図５は、１ラウンド（ラウンド関数）を示した図であり、実際には、ラウンド関数を繰り返し適用してデータを暗号化を行う。ここで、各ラウンドで入力される鍵はラウンド鍵と呼ばれ、ラウンドごとに異なる鍵が使用され、元となる鍵に対して演算を行なってラウンド鍵を生成する。
本発明の暗号方式では、プログラムの実行中のみデータを保護出来れば良いため、従来よりも低い安全性の暗号方式でも十分であり、オーバーヘッドを小さく抑えるために各種パラメータをより高速化に適した設定にすることが望ましい。また、現在主流のブロック暗号は１２８ビットであり、１２８ビットを最小の処理単位としている。しかし、ＣＰＵのワードサイズは６４ビットが主流であり、これに合わせたほうがより効率的である。
【００２７】
図４に示す暗号化部５０は、入力部５１と、排他的論理和演算器（ＸＯＲ）５２ａ、５２ｂと、非線形関数（Ｓ−Ｂｏｘ）５３ａ〜５３ｈと、Ｍｉｘ  Ｃｏｌｕｍｎ５４ａ、５４ｂと、出力部５５とから構成されている。ここで、入力データは、前述のデータｘにシーケンス番号ｃを付加した情報あるいはデータｘとシーケンス番号ｃとを演算した情報であり、これらが６４ｂｉｔ単位のデータになっている。また、各ラウンドで用いられる鍵は、入力データ長と同様の６４ｂｉｔのラウンド鍵であり、これは、ラウンドごとに、異なる鍵が用いられる。
【００２８】
図４のうち、２つの排他的論理和演算器（ＸＯＲ）５２ａ、５２ｂは、データ攪拌を行っている。図４の例では、２つの排他的論理和演算器（ＸＯＲ）５２ａ、５２ｂを用いることにより、偏りのないデータ攪拌を実現している。
【００２９】
図５に示す暗号化部５０は、入力部５６と、非線形関数群（Ｓ−Ｂｏｘ）５７と、Ｓｈｉｆｔ  Ｒｏｗ５８と、Ｍｉｘ  Ｃｏｌｕｍｎ５９とから構成されている。ここで、入力データは、前述のデータｘにシーケンス番号ｃを付加した情報あるいはデータｘとシーケンス番号ｃとを演算した情報であり、これらが６４ｂｉｔ単位のデータになっている。また、各ラウンドで用いられる鍵は、入力データ長と同様の６４ｂｉｔのラウンド鍵であり、これは、ラウンドごとに、異なる鍵が用いられる。
【００３０】
図５のうち、Ｓｈｉｆｔ  Ｒｏｗ５８は、データ攪拌を行っている。図５の例では、Ｓｈｉｆｔ  Ｒｏｗ５８を用いることにより、図６に示すようなデータの攪拌を実現している。
【００３１】
＜第１の実施形態＞
図７から図８を用いて、本発明の実施形態について説明する。
【００３２】
＜アクセスパターン保護部の構成＞
本実施形態に係るアクセスパターン保護部１００は、図７に示すように、並べ替え部１１０と、移動部１２０と、制御部１３０と、書き出し部１４０と、保存部１５０と、記憶領域２００とから構成されている。
【００３３】
並べ替え部１１０は、初期状態において、１度だけ、非アクセス領域内のデータをランダムに並び替える。移動部１２０は、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる。
【００３４】
制御部１３０は、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行う。
【００３５】
例えば、アクセスを行うデータがアクセス領域および履歴領域に存在せず、非アクセス領域に存在し、履歴領域に保存されたデータがある場合に、アクセスを行うデータと履歴領域に保存された任意のデータとを２つのデータとして選択して、アクセス領域に移動して、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存する。
【００３６】
なお、制御部１３０は、他のプロセス、あるいは、他の時刻で使用されるデータを対象としてランダムにデータを選択する。これにより、有効に、アクセスパターンを保護することができる。
【００３７】
書き出し部１４０は、アクセスすべきデータへのアクセス処理が終了したときに、アクセス領域内の必要なデータを書き出す。保存部１５０は、アクセス領域から非アクセス領域に移動したデータを履歴領域に履歴データとして保存する。
【００３８】
＜アクセスパターン保護部の処理＞
図８を用いて、本実施形態に係るアクセスパターン保護部の処理について説明する。
【００３９】
まず、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替え（ステップＳ１００）、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる（ステップＳ２００）。
【００４０】
次に、１つのデータにアクセスが生じたときに、２つのデータを選択し、アクセス領域と非アクセス領域との間でデータ交換を行う際に、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータがアクセス領域および履歴領域に存在せず、非アクセス領域に存在し、履歴領域に保存されたデータがある場合に、アクセスを行うデータと履歴領域に保存された任意のデータとを２つのデータとして選択して、アクセス領域に移動して、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存する（ステップＳ３００）。  
【００４１】
そして、アクセスすべきデータへのアクセス処理が終了したときに、アクセス領域内の必要なデータを書き出す（ステップＳ４００）。
【００４２】
以上、説明したように、本実施形態によれば、非アクセス領域内のデータの並べ替えを１度しか行わないため、所定のタイミングで、何度もデータの並べ替えを行うＯｂｌｉｖｉｏｕｓ  ＲＡＭのように、オーバーヘッドが大きくなることを防止することができる。また、アクセスを行うデータがアクセス領域および履歴領域に存在せず、非アクセス領域に存在し、履歴領域に保存されたデータがある場合に、アクセスを行うデータと履歴領域に保存された任意のデータとを２つのデータとして選択して、アクセス領域に移動して、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存することから、有効に、アクセスパターンを保護することができる。
【００４３】
＜第２の実施形態＞
図９から図１０を用いて、本発明の実施形態について説明する。
【００４４】
＜アクセスパターン保護部の構成＞
本実施形態に係るアクセスパターン保護部は、図９に示すように、並べ替え部１１０と、移動部１２０と、制御部１３１と、書き出し部１４０と、保存部１５０と、記憶領域２００とから構成されている。なお、第１の実施形態と同一の符号を付す構成要素については、同様の機能を有することから、その詳細な説明は省略する。
【００４５】
制御部１３１は、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行う。
【００４６】
例えば、アクセスを行うデータが履歴領域に保存されている場合に、履歴領域に保存されていないデータをランダムに選択し、アクセスを行うデータとランダムに選択したデータとを２つのデータとし、アクセス領域に移動して、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存する。
【００４７】
なお、制御部１３１は、他のプロセス、あるいは、他の時刻で使用されるデータを対象としてランダムにデータを選択する。これにより、ランダムなデータの付加を不要とすることができる。
【００４８】
＜記憶装置の処理＞
図１０を用いて、本実施形態に係るアクセスパターン保護部の処理について説明する。
【００４９】
まず、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替え（ステップＳ１１０）、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる（ステップＳ２１０）。
【００５０】
次に、１つのデータにアクセスが生じたときに、２つのデータを選択し、アクセス領域と非アクセス領域との間でデータ交換を行う際に、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータが履歴領域に保存されている場合に、履歴領域に保存されていないデータをランダムに選択し、アクセスを行うデータとランダムに選択したデータとを２つのデータとし、アクセス領域に移動して、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存する（ステップＳ３１０）。
【００５１】
そして、アクセスすべきデータへのアクセス処理が終了したときに、アクセス領域内の必要なデータを書き出す（ステップＳ４１０）。
【００５２】
以上、説明したように、本実施形態によれば、非アクセス領域内のデータの並べ替えを１度しか行わないため、所定のタイミングで、何度もデータの並べ替えを行うＯｂｌｉｖｉｏｕｓ  ＲＡＭのように、オーバーヘッドが大きくなることを防止することができる。また、アクセスを行うデータが履歴領域に保存されている場合に、履歴領域に保存されていないデータをランダムに選択し、アクセスを行うデータとランダムに選択したデータとを２つのデータとし、アクセス領域に移動して、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存することから、有効に、アクセスパターンを保護することができる。
【００５３】
＜第３の実施形態＞
図１１から図１２を用いて、本発明の実施形態について説明する。
【００５４】
＜アクセスパターン保護部の構成＞
本実施形態に係るアクセスパターン保護部は、図１１に示すように、並べ替え部１１０と、移動部１２０と、制御部１３２と、書き出し部１４０と、保存部１５０と、記憶領域２００とから構成されている。なお、第１の実施形態と同一の符号を付す構成要素については、同様の機能を有することから、その詳細な説明は省略する。
【００５５】
制御部１３２は、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行う。
【００５６】
例えば、アクセスを行うデータがアクセス領域に保存されている場合に、非アクセス領域と履歴領域とからランダムに選択したデータを２つのデータとし、アクセス領域に移動して、移動したデータサイズに応じて、アクセス領域にあった任意のデータを非アクセス領域に移動し、これらのデータを履歴領域に保存する。
【００５７】
なお、制御部１３２は、他のプロセス、あるいは、他の時刻で使用されるデータを対象としてランダムにデータを選択する。これにより、ランダムなデータの付加を不要とすることができる。
【００５８】
＜アクセスパターン保護部の処理＞
図１２を用いて、本実施形態に係る記憶装置の処理について説明する。
【００５９】
まず、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替え（ステップＳ１２０）、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる（ステップＳ２２０）。
【００６０】
次に、１つのデータにアクセスが生じたときに、２つのデータを選択し、アクセス領域と非アクセス領域との間でデータ交換を行う際に、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセスを行うデータがアクセス領域に保存されている場合に、非アクセス領域と履歴領域とからランダムに選択したデータを２つのデータとし、アクセス領域に移動して、移動したデータサイズに応じて、アクセス領域にあった任意のデータを非アクセス領域に移動し、これらのデータを履歴領域に保存する（ステップＳ３２０）。  
【００６１】
そして、アクセスすべきデータへのアクセス処理が終了したときに、アクセス領域内の必要なデータを書き出す（ステップＳ４２０）。
【００６２】
以上、説明したように、本実施形態によれば、非アクセス領域内のデータの並べ替えを１度しか行わないため、所定のタイミングで、何度もデータの並べ替えを行うＯｂｌｉｖｉｏｕｓ  ＲＡＭのように、オーバーヘッドが大きくなることを防止することができる。また、アクセスを行うデータがアクセス領域に保存されている場合に、非アクセス領域と履歴領域からランダムに選択したデータを２つのデータとし、アクセス領域に移動して、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存することから、有効に、アクセスパターンを保護することができる。
【００６３】
＜実施例＞
図１３から図１５を用いて、本発明の実施例について説明する。
【００６４】
図１３は、１、２、・・・、９、Ａ、Ｂ、・・・、Ｆをメモリに保存されているデータとしたときに、プログラムが、５→Ｄ→８→５→Ａの順にデータにアクセスする場合のメモリの遷移を示したものである。以下、図１４、図１５を用いて、この処理を例示とし、説明する。なお、図１３の例にかかわらず、非アクセス領域をさらに複数に分割してもよい。
【００６５】
まず、初期状態において、１度だけ、非アクセス領域内のデータをランダムに並び替え（ステップＳ１１００）、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる（ステップＳ１２００）。
【００６６】
そして、まず、５にアクセスする場合には、５はアクセス領域に含まれないため、５ともう一つランダムに選択されたデータ(図１３では、２)をアクセス領域に移動し、例えば、これにより、アクセス領域から移動する４とＢとを履歴領域に保存して、５にアクセスする。このとき、アクセス領域内の他のデータ（図１３では、２、３、８）に対してもアクセスを行う（ステップＳ１３００）。
【００６７】
次に、Ｄにアクセスする場合には、Ｄはアクセス領域に含まれないため、Ｄをアクセス領域に移動し、もう一つのデータは、履歴領域から選択する（例えば、図１３では、Ｂ)。これにより、アクセス領域から移動する５と８とを履歴領域に保存して、Ｄにアクセスする。このとき、アクセス領域内の他のデータ（図１３では、３、Ｂ、２）に対してもアクセスを行う（ステップＳ１４００）。
【００６８】
さらに、８にアクセスする場合には、８は履歴領域に含まれているため、もう一つのデータは履歴領域に含まれないデータをランダムに選択し(図１３では、Ａ)、アクセス領域に移動する。これにより、アクセス領域から移動する３とＢとを履歴領域に保存して、８にアクセスする。このとき、アクセス領域内の他のデータ（図１３では、Ａ、Ｄ、２）に対してもアクセスを行う（ステップＳ１５００）。
【００６９】
さらに、５にアクセスする場合、５は履歴領域に含まれているため、もう一つのデータは履歴領域に含まれないデータをランダムに選択し(図１３では、６)、アクセス領域に移動する。これにより、アクセス領域から移動する２と８とを履歴領域に保存して、５にアクセスする。また、アクセス領域内の他のデータ（図１３では、Ａ、Ｄ、６）に対してもアクセスを行う（ステップＳ１６００）。
【００７０】
最後に、Ａにアクセスする場合、Ａはアクセス領域に含まれているため、アクセス領域に含まれないランダムに選択したデータと履歴領域に保存されているデータとを(図１３では、３、Ｆ)、アクセス領域に移動する。これにより、アクセス領域から移動する６とＤとが非アクセス領域に書き出され、Ａにアクセスする。また、アクセス領域内の他のデータ（図１３では、５、Ｆ、３）に対してもアクセスを行う（ステップＳ１７００）。
【００７１】
そして、すべての処理が完了するとアクセス領域内の必要なデータを書き出して、終了する（ステップＳ１８００）。
【００７２】
したがって、本実施例によれば、非アクセス領域内のデータの並べ替えを１度しか行わないため、所定のタイミングで、何度もデータの並べ替えを行うＯｂｌｉｖｉｏｕｓ  ＲＡＭのように、オーバーヘッドが大きくなることを防止することができるという効果がある。また、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うことから、データのアクセスパターンを保護することができるという効果がある。さらに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行うため、さらに、データのアクセスパターンを保護することができる。また、プログラムによってアクセスされるデータに対して、ランダムに選択したデータを取り込むことによって、安全性を保ちつつ、アクセスパターンの保護において、必要な保存領域を削減することができる。
【００７３】
なお、記憶装置の処理をコンピュータシステムが読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを記憶装置に読み込ませ、実行することによって本発明の記憶装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００７４】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００７５】
また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【００７６】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００７７】
１０；データ移動部
２０；キャッシュ部
３０；復号化部
４０；保管部
５０；暗号化部
１００；アクセスパターン保護部
１１０；並べ替え部
１２０；移動部
１３０；制御部
１３１；制御部
１３２；制御部
１４０；書き出し部
１５０；保存部
２００；記憶領域
【図１】
2015011452.tif 000003
【図２】
2015011452.tif 000004
【図３】
2015011452.tif 000005
【図４】
2015011452.tif 000006
【図５】
2015011452.tif 000007
【図６】
2015011452.tif 000008
【図７】
2015011452.tif 000009
【図８】
2015011452.tif 000010
【図９】
2015011452.tif 000011
【図１０】
2015011452.tif 000012
【図１１】
2015011452.tif 000013
【図１２】
2015011452.tif 000014
【図１３】
2015011452.tif 000015
【図１４】
2015011452.tif 000016
【図１５】
2015011452.tif 000017