(57)【要約】【課題】メモリダンプなどのメモリに対する直接攻撃に対しても、一定の耐性を有する秘密鍵の隠蔽方法を実現する。【解決手段】データを記憶する記憶装置１００内に設けられ、内部状態を一時的に保存するバッファ１１と、秘密鍵のインデックス値を格納するインデックス値格納部１２と、格納されていたインデックス値と内部状態に応じて、秘密鍵を導出する不可逆かつ非線形な変換を行う第１の関数器１３と、格納されていたインデックス値に応じて、内部状態を更新する可逆な変換を行う第２の関数器１４と、を備える。【選択図】図８
2014053714.tif 000002
【特許請求の範囲】
【請求項１】
データを記憶する記憶装置内に設けられ、
内部状態を一時的に保存するバッファと、
秘密鍵のインデックス値を格納する格納手段と、
該格納されていたインデックス値と前記内部状態に応じて、秘密鍵を導出する不可逆かつ非線形な変換を行う第１の関数器と、
前記格納されていたインデックス値に応じて、前記内部状態を更新する可逆な変換を行う第２の関数器と、
を備えたことを特徴とする秘密鍵生成装置。
【請求項２】
前記記憶装置に新たなデータを記憶する度に、前記新たな秘密鍵のインデックス値により、前記第２の関数器が前記内部状態を変更し、前記第１の関数器が新たな秘密鍵を導出することを特徴とする請求項１に記載の秘密鍵生成装置。
【請求項３】
前記データと該データを記憶するときに導出した前記秘密鍵とを対で前記記憶装置に記憶することを特徴とする請求項２に記載の秘密鍵生成装置。
【請求項４】
前記第２の関数器が、前記新たな秘密鍵のインデックス値に応じて、非線形関数の使用の順番を変更することにより、前記内部状態を変更することを特徴とする請求項２に記載の秘密鍵生成装置。
【請求項５】
前記第２の関数器が、前記新たな秘密鍵のインデックス値に応じて、入力する内部データをビット単位で巡回シフトすることにより、前記内部状態を変更することを特徴とする請求項２に記載の秘密鍵生成装置。
【請求項６】
前記第２の関数器が、前記内部状態と前記新たな秘密鍵のインデックス値との排他的論理和演算を行うことにより、前記内部状態を変更することを特徴とする請求項２に記載の秘密鍵生成装置。
【請求項７】
前記記憶装置が、
メモリをデータのアクセス領域と非アクセス領域とに分割された記憶装置であって、
初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える並び替え手段と、
前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる移動手段と、
１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行う制御手段と、
アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す書き出し手段と、
を備えたことを特徴とする請求項１または請求項２に記載の秘密鍵生成装置。
【請求項８】
前記記憶装置の記憶容量が、前記秘密鍵の鍵長以上であることを特徴とする請求項１から請求項７に記載の秘密鍵生成装置。
【請求項９】
生成する秘密鍵に対応した秘密鍵のインデックス値を入力する第１のステップと、
入力された秘密鍵のインデックス値に基づいて、必要な回数分、インデックス値に応じて、内部状態を更新する可逆な変換を行う第２の関数を動作させ、内部状態の値を更新する第２のステップと、
該更新した内部状態と秘密鍵のインデックス値とを入力し、インデックス値と前記内部状態に応じて、秘密鍵を導出する不可逆かつ非線形な変換を行う第１の関数を動作させ、前記秘密鍵を生成する第３のステップと、
を備えたことを特徴とする秘密鍵生成方法。
【請求項１０】
前記第１および第２のステップにおいて、
新たに生成する秘密鍵に対応した新たな秘密鍵のインデックス値を入力する第４のステップと、
入力された秘密鍵のインデックス値に基づいて、必要な回数分、前記第２の関数を動作させ、内部状態の値を更新する第５のステップと、
を備えたことを特徴とする請求項９に記載の秘密鍵生成方法。
【請求項１１】
コンピュータに、
生成する秘密鍵に対応した秘密鍵のインデックス値を入力する第１のステップと、
入力された秘密鍵のインデックス値に基づいて、必要な回数分、インデックス値に応じて、内部状態を更新する可逆な変換を行う第２の関数を動作させ、内部状態の値を更新する第２のステップと、
該更新した内部状態と秘密鍵のインデックス値とを入力し、インデックス値と前記内部状態に応じて、秘密鍵を導出する不可逆かつ非線形な変換を行う第１の関数を動作させ、前記秘密鍵を生成する第３のステップと、
を実行させるためのプログラム。
【請求項１２】
前記第１および第２のステップにおいて、
新たに生成する秘密鍵に対応した新たな秘密鍵のインデックス値を入力する第４のステップと、
入力された秘密鍵のインデックス値に基づいて、必要な回数分、第２の関数を動作させ、内部状態の値を更新する第５のステップと、
を備えたことを特徴とする請求項１１に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号化に使用する秘密鍵を生成し、メモリ上で適切に保護する秘密鍵生成装置、秘密鍵生成方法およびプログラムに関する。
【背景技術】
【０００２】
近年、コンピュータを利用した様々なサービスが提供されている。これらのサービスのうち、多くのサービスにおいては、通信内容の秘匿を実現するため、暗号化技術が利用される。ここで、暗号化技術を利用するためには、秘密鍵が必要であり、秘密鍵は攻撃者に漏洩しないように適切に保護される必要がある。そのため、秘密鍵を保護する方法として、実行プログラムに埋め込み難読化等の手段により隠蔽する方法が知られている（例えば、非特許文献１参照。）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Ｗａｔｅｒｍａｒｋｉｎｇ，Ｔａｍｐｅｒ−Ｐｒｏｏｆｉｎｇ，ａｎｄ  Ｏｂｆｕｓｃａｔｉｏｎ  Ｔｏｏｌｓ  ｆｏｒ  Ｓｏｆｔｗａｒｅ  Ｐｒｏｔｅｃｔｉｏｎ，  Ｃｈｒｉｓｔｉａｎ  Ｓ．Ｃｏｌｌｂｅｒｇ，ＩＥＥＥ  ＴＲＡＮＳＡＣＴＩＯＮＳ  ＯＮ  ＳＯＦＴＷＡＲＥ  ＥＮＧＩＮＥＥＲＩＮＧ，ｖｏｌ．２８，ＮＯ．８，ＡＵＧＵＳＴ  ２００２
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１に記載の方法では、動的解析と呼ばれるメモリを直接盗み見るような攻撃に対しては脆弱であることが知られている。
【０００５】
そこで、本発明は、上述の課題に鑑みてなされたものであり、メモリダンプなどのメモリに対する直接攻撃に対しても、一定の耐性を有する秘密鍵の隠蔽方法を実現する秘密鍵生成装置、秘密鍵生成方法およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明は、上記の課題を解決するために、以下の事項を提案している。なお、理解を容易にするために、本発明の実施形態に対応する符号を付して説明するが、これに限定されるものではない。
【０００７】
（１）本発明は、データを記憶する記憶装置（例えば、図１の記憶装置１００に相当）内に設けられ、内部状態を一時的に保存するバッファ（例えば、図２のバッファ１１に相当）と、秘密鍵のインデックス値を格納する格納手段（例えば、図２のインデックス値格納部１２に相当）と、該格納されていたインデックス値と前記内部状態に応じて、秘密鍵を導出する不可逆かつ非線形な変換を行う第１の関数器（例えば、図２の第１の関数器１３に相当）と、前記格納されていたインデックス値に応じて、前記内部状態を更新する可逆な変換を行う第２の関数器（例えば、図２の第２の関数器１４に相当）と、を備えたことを特徴とする秘密鍵生成装置を提案している。
【０００８】
この発明によれば、バッファは、内部状態を一時的に保存する。格納手段は、秘密鍵のインデックス値を格納する。第１の関数器は、格納されていたインデックス値と内部状態に応じて、秘密鍵を導出する不可逆かつ非線形な変換を行う。第２の関数器は、格納されていたインデックス値に応じて、内部状態を更新する可逆な変換を行う。つまり、秘密鍵のインデックス値により内部状態を更新し、インデックス値と内部状態に応じて、秘密鍵を導出することから、メモリダンプなどのメモリに対する直接攻撃に対しても、一定の耐性を有する秘密鍵の隠蔽方法を実現できる。
【０００９】
（２）本発明は、（１）の秘密鍵生成装置について、前記記憶装置に新たなデータを記憶する度に、前記新たな秘密鍵のインデックス値により、前記第２の関数器が前記内部状態を変更し、前記第１の関数器が新たな秘密鍵を導出することを特徴とする秘密鍵生成装置を提案している。
【００１０】
この発明によれば、記憶装置に新たなデータを記憶する度に、新たな秘密鍵のインデックス値により、第２の関数器が内部状態を変更し、第１の関数器が新たな秘密鍵を導出する。したがって、攻撃者から秘密鍵を有効に隠蔽することができる。
【００１１】
（３）本発明は、（２）の秘密鍵生成装置について、前記データと該データを記憶するときに導出した前記秘密鍵とを対で前記記憶装置に記憶することを特徴とする秘密鍵生成装置を提案している。
【００１２】
この発明によれば、さらに、データとそのデータを記憶するときに導出した秘密鍵とを対で記憶装置に記憶することから、攻撃者に対して秘密鍵を有効に隠蔽することができる。
【００１３】
（４）本発明は、（２）の秘密鍵生成装置について、前記第２の関数器が、前記新たな秘密鍵のインデックス値に応じて、非線形関数の使用の順番を変更することにより、前記内部状態を変更することを特徴とする秘密鍵生成装置を提案している。
【００１４】
この発明によれば、第２の関数器が、新たな秘密鍵のインデックス値に応じて、非線形関数の使用の順番を変更することにより、内部状態を変更することから、簡易な処理で秘密鍵を更新できるため、攻撃者に対して秘密鍵を有効に隠蔽することができる。
【００１５】
（５）本発明は、（２）の秘密鍵生成装置について、前記第２の関数器が、前記新たな秘密鍵のインデックス値に応じて、入力する内部データをビット単位で巡回シフトすることにより、前記内部状態を変更することを特徴とする秘密鍵生成装置を提案している。
【００１６】
この発明によれば、第２の関数器が、新たな秘密鍵のインデックス値に応じて、入力する内部データをビット単位で巡回シフトすることにより、内部状態を変更することから、簡易な処理で秘密鍵を更新できるため、攻撃者に対して秘密鍵を有効に隠蔽することができる。
【００１７】
（６）本発明は、（２）の秘密鍵生成装置について、前記第２の関数器が、前記内部状態と前記新たな秘密鍵のインデックス値との排他的論理和演算を行うことにより、前記内部状態を変更することを特徴とする請求項２に記載の秘密鍵生成装置を提案している。
【００１８】
この発明によれば、第２の関数器が、内部状態と新たな秘密鍵のインデックス値との排他的論理和演算を行うことにより、内部状態を変更することから、簡易な処理で秘密鍵を更新できるため、攻撃者に対して秘密鍵を有効に隠蔽することができる。
【００１９】
（７）本発明は、（１）または（２）の秘密鍵生成装置について、前記記憶装置が、メモリをデータのアクセス領域と非アクセス領域とに分割された記憶装置であって、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替える並び替え手段（例えば、図３の並べ替え部１１０に相当）と、前記非アクセス領域内のデータを前記アクセス領域のメモリサイズに応じて選択して、前記アクセス領域に移動させる移動手段（例えば、図３の移動部１２０に相当）と、１つのデータにアクセスが生じたときに、前記アクセス領域と非アクセス領域との間でデータ交換を行うとともに、前記アクセス領域内の他のデータについてもアクセスを行って、前記アクセス領域と非アクセス領域との間でデータ交換を行う制御手段（例えば、図３の制御部１３０に相当）と、アクセスすべきデータへのアクセス処理が終了したときに、前記アクセス領域内の必要なデータを書き出す書き出し手段（例えば、図３の書き出し部１４０に相当）と、を備えたことを特徴とする秘密鍵生成装置を提案している。
【００２０】
この発明によれば、記憶装置の並び替え手段は、初期状態において、１度だけ、非アクセス領域内のデータをランダムに並び替える。移動手段は、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる。制御手段は、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行う。書き出し手段は、アクセスすべきデータへのアクセス処理が終了したときに、アクセス領域内の必要なデータを書き出す。したがって、非アクセス領域内のデータの並べ替えを１度しか行わないため、所定のタイミングで、何度も非アクセス領域内のデータの並べ替えを行うＯｂｌｉｖｉｏｕｓ  ＲＡＭのように、オーバーヘッドが大きくなることを防止することができる。１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うことから、データのアクセスパターンを秘匿することができる。さらに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行うため、さらに、データのアクセスパターンを秘匿することができる。
【００２１】
（８）本発明は、（１）から（７）の秘密鍵生成装置について、前記記憶装置の記憶容量が、前記秘密鍵の鍵長以上であることを特徴とする秘密鍵生成装置を提案している。
【００２２】
この発明によれば、記憶装置の記憶容量が、秘密鍵の鍵長以上である。すなわち、記憶装置内のすべてのデータを得ることができなければ、秘密鍵を取得することができない。
【００２３】
（９）本発明は、生成する秘密鍵に対応した秘密鍵のインデックス値を入力する第１のステップ（例えば、図８のステップＳ１１００に相当）と、入力された秘密鍵のインデックス値に基づいて、必要な回数分、インデックス値に応じて、内部状態を更新する可逆な変換を行う第２の関数を動作させ、内部状態の値を更新する第２のステップ（例えば、図８のステップＳ１２００に相当）と、該更新した内部状態と秘密鍵のインデックス値とを入力し、インデックス値と前記内部状態に応じて、秘密鍵を導出する不可逆かつ非線形な変換を行う第１の関数を動作させ、前記秘密鍵を生成する第３のステップ（例えば、図８のステップＳ１３００に相当）と、を備えたことを特徴とする秘密鍵生成方法を提案している。
【００２４】
この発明によれば、生成する秘密鍵に対応した秘密鍵のインデックス値を入力し、入力された秘密鍵のインデックス値に基づいて、必要な回数分、インデックス値に応じて、内部状態を更新する可逆な変換を行う第２の関数を動作させ、内部状態の値を更新し、更新した内部状態と秘密鍵のインデックス値とを入力し、インデックス値と内部状態に応じて、秘密鍵を導出する不可逆かつ非線形な変換を行う第１の関数を動作させ、秘密鍵を生成する。したがって、メモリダンプなどのメモリに対する直接攻撃に対しても、一定の耐性を有する秘密鍵の隠蔽方法を実現できる。
【００２５】
（１０）本発明は、（９）の秘密鍵生成方法について、前記第１および第２のステップにおいて、新たに生成する秘密鍵に対応した新たな秘密鍵のインデックス値を入力する第４のステップと、入力された秘密鍵のインデックス値に基づいて、必要な回数分、前記第２の関数を動作させ、内部状態の値を更新する第５のステップと、を備えたことを特徴とする秘密鍵生成方法を提案している。
【００２６】
この発明によれば、第１および第２のステップにおいて、新たに生成する秘密鍵に対応した新たな秘密鍵のインデックス値を入力し、入力された秘密鍵のインデックス値に基づいて、必要な回数分、第２の関数を動作させ、内部状態の値を更新する。したがって、攻撃者から秘密鍵を有効に隠蔽することができる。
【００２７】
（１１）本発明は、コンピュータに、生成する秘密鍵に対応した秘密鍵のインデックス値を入力する第１のステップ（例えば、図８のステップＳ１１００に相当）と、入力された秘密鍵のインデックス値に基づいて、必要な回数分、インデックス値に応じて、内部状態を更新する可逆な変換を行う第２の関数を動作させ、内部状態の値を更新する第２のステップ（例えば、図８のステップＳ１２００に相当）と、該更新した内部状態と秘密鍵のインデックス値とを入力し、インデックス値と前記内部状態に応じて、秘密鍵を導出する不可逆かつ非線形な変換を行う第１の関数を動作させ、前記秘密鍵を生成する第３のステップ（例えば、図８のステップＳ１３００に相当）と、を実行させるためのプログラムを提案している。
【００２８】
この発明によれば、生成する秘密鍵に対応した秘密鍵のインデックス値を入力し、入力された秘密鍵のインデックス値に基づいて、必要な回数分、インデックス値に応じて、内部状態を更新する可逆な変換を行う第２の関数を動作させ、内部状態の値を更新し、更新した内部状態と秘密鍵のインデックス値とを入力し、インデックス値と内部状態に応じて、秘密鍵を導出する不可逆かつ非線形な変換を行う第１の関数を動作させ、秘密鍵を生成する。したがって、メモリダンプなどのメモリに対する直接攻撃に対しても、一定の耐性を有する秘密鍵の隠蔽方法を実現できる。
【００２９】
（１２）本発明は、（１１）のプログラムについて、前記第１および第２のステップにおいて、新たに生成する秘密鍵に対応した新たな秘密鍵のインデックス値を入力する第４のステップと、入力された秘密鍵のインデックス値に基づいて、必要な回数分、第２の関数を動作させ、内部状態の値を更新する第５のステップと、を備えたことを特徴とするプログラムを提案している。
【００３０】
この発明によれば、第１および第２のステップにおいて、新たに生成する秘密鍵に対応した新たな秘密鍵のインデックス値を入力し、入力された秘密鍵のインデックス値に基づいて、必要な回数分、第２の関数を動作させ、内部状態の値を更新する。したがって、攻撃者から秘密鍵を有効に隠蔽することができる。
【発明の効果】
【００３１】
本発明によれば、メモリに対して直接アクセスできるような攻撃者に対しても安全性を有する秘密鍵の隠蔽方法が実現できるという効果がある。
【図面の簡単な説明】
【００３２】
【図１】本発明の実施形態に係る秘密鍵生成装置を備えた記憶装置の構成を示す図である。
【図２】本発明の実施形態に係る秘密鍵生成装置の構成を示す図である。
【図３】本発明の実施形態に係る記憶装置の構成を示す図である。
【図４】本発明の実施形態に係る記憶装置の処理を示す図である。
【図５】本発明の実施形態に係る記憶装置の処理のうち、ステップ３００の処理を詳細に示した図である。
【図６】本発明の実施形態に係る記憶装置の処理のうち、ステップ３００の処理を詳細に示した図である。
【図７】本発明の実施形態に係る記憶装置の処理のうち、ステップ３００の処理を詳細に示した図である。
【図８】本発明の実施形態に係る秘密鍵生成装置の処理を示す図である。
【発明を実施するための形態】
【００３３】
以下、本発明の実施形態について、図面を用いて、詳細に説明する。
なお、本実施形態における構成要素は適宜、既存の構成要素等との置き換えが可能であり、また、他の既存の構成要素との組合せを含む様々なバリエーションが可能である。したがって、本実施形態の記載をもって、特許請求の範囲に記載された発明の内容を限定するものではない。
【００３４】
以下、図１から図８を用いて、本発明の実施形態について説明する。
【００３５】
＜秘密鍵生成装置を備えた記憶装置の構成＞
図１に示すように、本発明の秘密鍵生成装置１０は、記憶装置１００内に設けられている。そして、データが記憶装置１００に入力されると、秘密鍵生成装置１０が秘密鍵を生成して、入力されたデータと対に秘密鍵を記憶装置１００内の所定のメモリエリアに格納する。
【００３６】
＜秘密鍵生成装置の構成＞
本実施形態に係る秘密鍵生成装置１０は、図２に示すように、バッファ１１と、インデックス値格納部１２と、第１の関数器１３と、第２の関数器１４とから構成されている。なお、本実施形態に係る秘密鍵生成装置１０は、ローカルな環境においてメモリ上に保存されるデータの暗号化を行うための秘密鍵を生成するものである。
【００３７】
バッファ１１は、内部状態を一時的に保存する。インデックス値格納部１２は、秘密鍵のインデックス値を格納する。なお、本実施形態に係る秘密鍵生成装置１０は、記憶装置１００に新たなデータを記憶する度に、新たな秘密鍵のインデックス値により、第２の関数器１４が内部状態を変更し、第１の関数器１３が新たな秘密鍵を導出する。
【００３８】
第１の関数器１３は、インデックス値格納部１２に格納されていたインデックス値（以下、Ｋｅｙ  Ｐｏｉｎｔｅｒと同義）と内部状態に応じて、秘密鍵を導出する不可逆かつ非線形な変換を行う。具体的には、内部状態（Ｉｎｔｅｒｎａｌ  Ｓｔａｔｅ）の全ての値を使って秘密鍵のｋビットを計算する関数であり、非線形関数で、常に不可逆な変換を行う関数である。すなわちＦ：｛０、１｝＾ｎ、Ｋｅｙ  Ｐｏｉｎｔｅｒ＞｛０、１｝＾ｍ、｜ｎ＞ｍである。
【００３９】
ここで、第１の関数器１３については、Ｂｏｏｌｅａｎ  Ｆｕｎｃｔｉｏｎの組合せで構成できる。すなわち、複数のビットに対して１ビットを出力するような非線形関数を鍵長の分だけ用意し、秘密鍵を導出する。Ｂｏｏｌｅ多項式表現の例を数１に示す。
【００４０】
［数１］
｛（ｘ５＋１）（ｘ４＋１）（ｘ３＋１）（ｘ２＋０）（ｘ１＋１）（ｘ０＋１）｝
｛（ｙ０＋１）＋１｝＝０
【００４１】
ここで、最初の鍵かっこ部分の式を式Ａ、次の鍵かっこ部分の式を式Ｂとする。そうすると、この式は、式Ａを「ｘ５＝０かつｘ４＝０かつｘ３＝０かつｘ２＝１かつｘ１＝０かつｘ０＝０」という事象、式Ｂを「ｙ０＝０」という事象とし、事象が真であることを１、偽であることを０で表したときに「ＡかつＢは偽である」ということを式で表したものである。なお、上記ブール多項式表現で積は、ＡＮＤ（論理積）、＋はＸＯＲ（論理和）を表す。そして、この式は、入力ｘ０−ｘ５に対して、１ビット出力ｙ０が得られるＢｏｏｌｅａｎ  Ｆｕｎｃｔｉｏｎを表現している。
【００４２】
また、同方式は、Ｋｅｙ  ｐｏｉｎｔｅｒによって、鍵を一意に導出する。Ｋｅｙ  Ｐｏｉｎｔｅｒは、鍵の導出処理ごとに変更する。Ｋｅｙ  ｐｏｉｎｔｅｒ値による第１の関数器１３の変更については、例えば、Ｋｅｙ  Ｐｏｉｎｔ値に従ってＢｏｏｌｅａｎ  Ｆｕｎｃｔｉｏｎの使用順を変更する、Ｋｅｙ  Ｐｏｉｎｔ値に従って、入力する内部データをビット単位で巡回シフトさせる、内部状態とＫｅｙ  Ｐｏｉｎｔ値との排他的論理和演算結果を出力とする等の方法が考えられる。
【００４３】
第２の関数器１４は、インデックス値格納部１２に格納されていたインデックス値に応じて、内部状態を更新する可逆な変換を行う。具体的には、内部状態の全てもしくは一部の値を使って、内部状態の全てもしくは一部の値を更新する関数であり、可逆な変換を行うものとする。そして、Ｋｅｙ  Ｐｏｉｎｔｅｒの入力に対して対応する内部状態を返す関数である。
【００４４】
第２の関数器１４は、可逆な関数としているため、Ｋｅｙ  Ｐｏｉｎｔｅｒに従って、順方向、あるいは逆方向に必要な回数分演算を行なうことにより、Ｋｅｙ  Ｐｏｉｎｔｅｒに対応する内部状態を復元できる。このとき、現在保有しているＫｅｙ  Ｐｏｉｎｔｅｒ値と新たに入力されたｋｅｙ  Ｐｏｉｎｔｅｒ値との差分を計算し、順方向、あるいは逆方向に必要な回数分演算を行なう。内部状態が復元できれば、関数Ｆを使用することにより、Ｋｅｙ  Ｐｏｉｎｔｅｒに対応する秘密鍵を導出することができる。
【００４５】
本実施形態における第２の関数器１４は、出力として計算された秘密鍵とそのＫｅｙ  Ｐｏｉｎｔｅｒ値を返す。第２の関数器１４の代表例は、線形フィードバックシフトレジスタに用いられるフィードバック関数である。構成法の具体例を以下に示す。
【００４６】
フィードバック関数は、フィードバックの際には、既約多項式の根を掛けるという方針に従って構成する。
【００４７】
いま、例えば、ＧＦ（２＾８）を考える。ｘ＾８＋ｘ＾４＋ｘ＾３＋ｘ＾２＋１の根をα、入力するワードをｗとすると、ｗαとなる。処理としては、１ｂｉｔ左シフトして、ｗの最上位ビットが１であれば、ｘ＾４＋ｘ＾３＋ｘ＾２＋１を足し、０であれば何も足さない。
【００４８】
また、拡大体を逐次拡大によって構成する場合、以下のような方法をとる。これは、ストリーム暗号で一般的に用いられている方法である。例えば、ＧＦ（２＾８）とＧＦ（２＾３２）とを併用する。すなわち、αは、数２の、βは、数３の根であるとき、αやα＾−１を掛ける。
【００４９】
［数２］
ｘ＾４＋β＾２３＊ｘ＾３＋β＾２４５＊ｘ＾２＋β＾４８＊ｘ＋β＾２３９∈
ＧＦ（２＾８）
【００５０】
［数３］
ｘ＾８＋ｘ＾７＋ｘ＾５＋ｘ＾３＋１∈  ＧＦ（２）
【００５１】
なお、上の式のβのべき乗数は、互いに素でかつ適当に大きい数を選ぶ。そして、βを使って、８ｂｉｔ内の攪拌を行い、αで、４ｗｏｒｄ内の攪拌を行う。後は、前者のケースと同様である。
【００５２】
また、テーブルを作成しておくことで、高速化は可能である。さらに、第２の関数器１４のより安全な構成法として、巨大な全単写関数を使用する方式、小さな全単写関数を組み合わせる方式、線形行列を使う方式などが考えられる。
【００５３】
＜記憶装置の構成＞
本実施形態に係る記憶装置は、図３に示すように、並べ替え部１１０と、移動部１２０と、制御部１３０と、書き出し部１４０と、保存部１５０と、記憶領域２００とから構成されている。なお、本発明の記憶装置は、例えば、ＲＡＭ等の一般的な記憶装置ばかりでなく、ＳＩＭやＩＣカード等の記憶媒体も含むものである。
【００５４】
記憶領域２００は、メモリをデータのアクセス領域と非アクセス領域と履歴領域とに分割されている。なお、アクセス領域、非アクセス領域、履歴領域は、ＤＲＡＭ、ＳＲＡＭ等の書き換え可能なメモリで構成される。また、アクセス領域を耐タンパ性を備えたＤＲＡＭ、ＳＲＡＭ等の書き換え可能なメモリで構成してもよい。並べ替え部１１０は、初期状態において、１度だけ、非アクセス領域内のデータをランダムに並び替える。移動部１２０は、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる。
【００５５】
制御部１３０は、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行う。
【００５６】
例えば、アクセスを行うデータがアクセス領域に存在せず、非アクセス領域に存在し、履歴領域に保存されたデータがある場合に、アクセスを行うデータと履歴領域に保存された任意のデータとをアクセス領域に移動し、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存する。
【００５７】
また、アクセスを行うデータが履歴領域に保存されている場合に、履歴領域に保存されていないデータを選択し、アクセスを行うデータと選択したデータとをアクセス領域に移動し、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存する。
【００５８】
また、アクセスを行うデータがアクセス領域に保存されている場合に、非アクセス領域からランダムに選択したデータとアクセスするデータとをアクセス領域に移動し、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存する。
【００５９】
書き出し部１４０は、アクセスすべきデータへのアクセス処理が終了したときに、アクセス領域内の必要なデータを書き出す。保存部１５０は、アクセス領域から非アクセス領域に移動したデータを履歴領域に履歴データとして保存する。
【００６０】
＜記憶装置の処理＞
図４から図７を用いて、本実施形態に係る記憶装置の処理について説明する。
【００６１】
まず、初期状態において、１度だけ、前記非アクセス領域内のデータをランダムに並び替え（ステップＳ１００）、非アクセス領域内のデータをアクセス領域のメモリサイズに応じて選択して、アクセス領域に移動させる（ステップＳ２００）。
【００６２】
次に、１つのデータにアクセスが生じたときに、アクセス領域と非アクセス領域との間でデータ交換を行うとともに、アクセス領域内の他のデータについてもアクセスを行って、アクセス領域と非アクセス領域との間でデータ交換を行う（ステップＳ３００）。
【００６３】
例えば、アクセスを行うデータがアクセス領域に存在せず、非アクセス領域に存在し、履歴領域に保存されたデータがある場合には、アクセスを行うデータと履歴領域に保存された任意のデータとをアクセス領域に移動し（ステップＳ３１１）、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存する（ステップＳ３１２）。
【００６４】
また、アクセスを行うデータが履歴領域に保存されている場合には、履歴領域に保存されていないデータを選択し（ステップＳ３２１）、アクセスを行うデータと選択したデータとをアクセス領域に移動し、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存する（ステップＳ３２２）。
【００６５】
また、アクセスを行うデータがアクセス領域に保存されている場合には、非アクセス領域からランダムに選択したデータとアクセスするデータとをアクセス領域に移動し（ステップＳ３３１）、移動したデータサイズに応じて、アクセス領域にあった任意のデータを履歴領域に移動して保存する（ステップＳ３３２）。
【００６６】
そして、アクセスすべきデータへのアクセス処理が終了したときに、アクセス領域内の必要なデータを書き出す（ステップＳ４００）。
【００６７】
＜秘密鍵生成装置の処理＞
図８を用いて、本実施形態に係る秘密鍵生成装置の処理について説明する。
【００６８】
まず、生成する秘密鍵に対応した秘密鍵のインデックス値を入力し（ステップＳ１１００）、入力された秘密鍵のインデックス値に基づいて、必要な回数分、インデックス値に応じて、内部状態を更新する可逆な変換を行う第２の関数器１４を動作させ、内部状態の値を更新する（ステップＳ１２００）。
【００６９】
そして、その更新した内部状態と秘密鍵のインデックス値とを入力し、インデックス値と内部状態に応じて、秘密鍵を導出する不可逆かつ非線形な変換を行う第１の関数器１３を動作させ、秘密鍵を生成する（ステップＳ１３００）。
【００７０】
なお、新たなデータが入力される度に、新たに生成する秘密鍵に対応した新たな秘密鍵のインデックス値を入力し、入力された秘密鍵のインデックス値に基づいて、必要な回数分、第２の関数器１４を動作させ、内部状態の値を更新して、新たな秘密鍵が生成され、記憶装置内の所定のエリアに、新たなデータと新たな秘密鍵とが対になって格納される。
【００７１】
以上、説明したように、本実施形態によれば、秘密鍵のインデックス値により内部状態を更新し、インデックス値と内部状態に応じて、秘密鍵を導出することから、メモリダンプなどのメモリに対する直接攻撃に対しても、一定の耐性を有する秘密鍵の隠蔽方法を実現できる。
【００７２】
なお、秘密鍵生成装置の処理をコンピュータシステムが読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムを秘密鍵生成装置に読み込ませ、実行することによって本発明の秘密鍵生成装置を実現することができる。ここでいうコンピュータシステムとは、ＯＳや周辺装置等のハードウェアを含む。
【００７３】
また、「コンピュータシステム」は、ＷＷＷ（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）システムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
【００７４】
また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組合せで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
【００７５】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００７６】
１０；秘密鍵生成装置
１１；バッファ
１２；インデックス値格納部
１３；第１の関数
１４；第２の関数
１１０；並べ替え部
１２０；移動部
１３０；制御部
１４０；書き出し部
１５０；保存部
２００；記憶領域
【図１】
2014053714.tif 000003
【図２】
2014053714.tif 000004
【図３】
2014053714.tif 000005
【図４】
2014053714.tif 000006
【図５】
2014053714.tif 000007
【図６】
2014053714.tif 000008
【図７】
2014053714.tif 000009
【図８】
2014053714.tif 000010