(57)【特許請求の範囲】
【請求項１】
ＲＳＡ暗号における暗号文を復号する復号装置であって、
乱数を発生させる乱数生成部と、
秘密鍵を用いて前記暗号文を復号する復号演算部と、を備え、
前記復号演算部は、
複数の異なる前記乱数と前記秘密鍵とを含んだ排他的論理和の演算を混在させた演算により前記秘密鍵の各ビットを導出するビット導出部と、
前記ビット導出部によって前記秘密鍵の最上位ビット又は最下位ビットから順に導出された前記各ビットの値を判定し、判定結果に応じた２乗算と乗算とを繰り返すことにより復号のためのべき剰余算を代替する、べき剰余算部と、を備える、
復号装置。
【請求項２】
データに対するアクセスのパターンを保護するアクセスパターン保護部を有する保護記憶部をさらに備え、
前記復号演算部は、前記保護記憶部に記憶された前記秘密鍵を用いる、
請求項１に記載の復号装置。
【請求項３】
前記べき剰余算部は、前記秘密鍵の各ビットの値の判定に、前記各ビットの値と前記乱数との排他的論理和を用いる、請求項１又は２に記載の復号装置。
【請求項４】
前記べき剰余算部は、前記ビット導出部によって導出されたビットを複数のビットにまとめた値で場合分けし、各場合に固有の２乗算と乗算との組み合わせを繰り返すことにより前記べき剰余算を代替する、請求項１から３のいずれか一項に記載の復号装置。
【請求項５】
前記べき剰余算部は、ダミーの演算を混在させた演算をする、請求項１から４のいずれか一項に記載の復号装置。
【請求項６】
請求項１に記載の復号装置が実行する方法であって、
前記乱数生成部が、乱数を発生させる乱数ステップと、
前記復号演算部が、秘密鍵を用いて前記暗号文を復号する復号演算ステップと、を備え、
前記復号演算ステップは、
前記ビット導出部が、複数の異なる前記乱数と前記秘密鍵とを含んだ排他的論理和の演算を混在させた演算により前記秘密鍵の各ビットを導出するビット導出ステップと、
前記べき剰余算部が、前記ビット導出ステップによって前記秘密鍵の最上位ビット又は最下位ビットから順に導出された前記各ビットの値を判定し、判定結果に応じた２乗算と乗算とを繰り返すことにより復号のためのべき剰余算を代替する、べき剰余算ステップと、を備える、
方法。
【請求項７】
コンピュータに、請求項６に記載の方法の各ステップを実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置、方法及びプログラムに関する。
【背景技術】
【０００２】
従来より、公開鍵暗号の一つであるＲＳＡ暗号（非特許文献１）の復号処理ａ＝ｂｄ（ｍｏｄ  ｎ）の実装では、次のような実装が用いられている。ただし、ａは平文、ｂは暗号文、ｄは秘密鍵を表し、ｐ、ｑをそれぞれ素数とし、ｎ＝ｐｑが成り立つ。
（１）ｄｐ，ｄｑ，ｉｑの計算
ｄｐ＝ｄ（ｍｏｄ  ｐ−１）
ｄｑ＝ｄ（ｍｏｄ  ｑ−１）
ｉｑ＝ｑ−１（ｍｏｄ  ｐ）
（２）ｂｐ，ｂｑの計算
ｂｐ＝ｂｄｐ（ｍｏｄ  ｐ）
ｂｑ＝ｑｄｑ（ｍｏｄ  ｑ）
（３）ａの計算
ｔｍｐ＝（ｂｐ−ｂｑ）×ｉｑ（ｍｏｄ  ｐ）
ａ＝ｔｍｐ×ｑ＋ｂｑ
【０００３】
このような復号処理中の演算過程では、秘密鍵がメモリやＣＰＵレジスタに展開されるため、これらを狙った攻撃によって秘密鍵が漏えいするという危険性がある。これに対して、メモリ保護・レジスタ保護技術を適用することによってメモリやレジスタから鍵を抜き取る攻撃を防止することが可能である。例えば、特許文献１には、鍵などを秘匿するためのメモリ保護技術が開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１３−２４６６７８号公報
【非特許文献】
【０００５】
【非特許文献１】Ｒ．Ｌ．Ｒｉｖｅｓｔ，Ａ．Ｓｈａｍｉｒ，ａｎｄ  Ｌ．Ａｄｅｌｍａｎ：  Ａ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｏｂｔａｉｎｉｎｇ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  ａｎｄ  Ｐｕｂｌｉｃ−ｋｅｙ  Ｃｒｙｐｔｓｙｓｔｅｍｓ，  Ｔｅｃｈｎｉｃａｌ  Ｍｅｍｏ  ＬＣＳ／ＴＭ８２；  Ａｐｒｉｌ  ４，１９７７（Ｒｅｖｉｓｅｄ  Ｄｅｃｅｍｂｅｒ  １２，１９７７）
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述の実装において、鍵に関連する値であるｐ、ｑを保護しようとした場合、復号処理中のほぼすべての演算にｐ、ｑが現れるため、保護技術の適用によるオーバーヘッドが非常に大きくなり、パフォーマンス低下が著しいという問題がある。
【０００７】
そこで、保護技術を適用した場合でも、復号処理が高速に動作するＲＳＡ実装が、望まれている。
【０００８】
本発明は、ＲＳＡ暗号における復号処理が、安全、かつ、高速な復号装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
具体的には、以下のような解決手段を提供する。
（１）  ＲＳＡ暗号における暗号文を復号する復号装置であって、乱数を発生させる乱数生成部と、秘密鍵を用いて前記暗号文を復号する復号演算部と、を備え、前記復号演算部は、複数の異なる前記乱数と前記秘密鍵とを含んだ排他的論理和の演算を混在させた演算により前記秘密鍵の各ビットを導出するビット導出部と、前記ビット導出部によって前記秘密鍵の最上位ビット又は最下位ビットから順に導出された前記各ビットの値を判定し、判定結果に応じた２乗算と乗算とを繰り返すことにより復号のためのべき剰余算を代替する、べき剰余算部と、を備える、復号装置。
【００１０】
（１）に係る復号装置の復号処理は、秘密鍵から直接的に各ビットを導出しないで間接的に導出するので、秘密鍵の各ビットを導出する過程がメモリやＣＰＵレジスタに展開されても、秘密鍵の各ビットの値について推測されることが困難である。さらに、復号処理において、２乗算と乗算とを繰り返す、べき剰余算は高速であり、各ビットの導出についての間接的な演算は、秘密鍵だけに限られているので、オーバーヘッドが抑制されている。
したがって、（１）に係る復号装置は、ＲＳＡ暗号における復号処理が、安全、かつ、高速である。
【００１１】
（２）  データに対するアクセスのパターンを保護するアクセスパターン保護部を有する保護記憶部をさらに備え、前記復号演算部は、前記保護記憶部に記憶された前記秘密鍵を用いる、（１）に記載の復号装置。
【００１２】
（２）に係る復号装置は、復号処理中に保護技術を適用する対象が秘密鍵だけでよい。
したがって、（２）に係る復号装置は、ＲＳＡ暗号における復号処理に、保護技術を適用した場合でもオーバーヘッドが抑制され、高速である。
【００１３】
（３）  前記べき剰余算部は、前記秘密鍵の各ビットの値の判定に、前記各ビットの値と前記乱数との排他的論理和を用いる、（１）又は（２）に記載の復号装置。
【００１４】
（３）に係る復号装置は、秘密鍵の導出された各ビットの値も間接的に判定するので、秘密鍵の各ビットの値を判定する過程がメモリやＣＰＵレジスタに展開されても、秘密鍵の各ビットの値について推測されることが困難である。したがって、（３）に係る復号装置は、各ビットの導出の安全性に判定の安全性を加えて、さらに安全である。
【００１５】
（４）  前記べき剰余算部は、前記ビット導出部によって導出されたビットを複数のビットにまとめた値で場合分けし、各場合に固有の２乗算と乗算との組み合わせを繰り返すことにより前記べき剰余算を代替する、（１）から（３）のいずれか一に記載の復号装置。
【００１６】
（４）に係る復号装置は、秘密鍵の各ビットの値をさらに間接的に判定するので、秘密鍵の各ビットの値について推測されることがさらに困難である。したがって、（４）に係る復号装置は、さらに安全である。
【００１７】
（５）  前記べき剰余算部は、ダミーの演算を混在させた演算をする、（１）から（４）のいずれか一に記載の復号装置。
【００１８】
（５）に係る復号装置は、復号処理における秘密鍵に関するアルゴリズムの解読について困難化されているので、さらに安全である。
【００１９】
（６）  （１）に記載の復号装置が実行する方法であって、前記乱数生成部が、乱数を発生させる乱数ステップと、前記復号演算部が、秘密鍵を用いて前記暗号文を復号する復号演算ステップと、を備え、前記復号演算ステップは、前記ビット導出部が、複数の異なる前記乱数と前記秘密鍵とを含んだ排他的論理和の演算を混在させた演算により前記秘密鍵の各ビットを導出するビット導出ステップと、前記べき剰余算部が、前記ビット導出ステップによって前記秘密鍵の最上位ビット又は最下位ビットから順に導出された前記各ビットの値を判定し、判定結果に応じた２乗算と乗算とを繰り返すことにより復号のためのべき剰余算を代替する、べき剰余算ステップと、を備える、方法。
【００２０】
したがって、（６）に係る方法は、（１）と同様に、ＲＳＡ暗号における復号処理が、安全、かつ、高速である。
【００２１】
（７）  コンピュータに、（６）に記載の方法の各ステップを実行させるためのプログラム。
【００２２】
したがって、（７）に係るプログラムは、ＲＳＡ暗号における復号処理が、安全、かつ、高速であるように、コンピュータに機能させる。
【発明の効果】
【００２３】
本発明によれば、ＲＳＡ暗号における復号処理が、保護技術を適用した場合でも、安全、かつ、高速である。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施形態１に係る復号装置の構成を示すブロック図である。
【図２】本発明の実施形態２に係る復号装置の構成を示すブロック図である。
【発明を実施するための形態】
【００２５】
［実施形態１］
以下、本発明の実施形態について、図を参照しながら説明する。図１は、本発明の実施形態１に係る復号装置１０の構成を示すブロック図である。
復号装置１０は、乱数生成部１１と、復号演算部１２とを備える。各部を詳述する。
【００２６】
乱数生成部１１は、乱数を発生させる。生成される乱数は、暗号学的に安全な乱数であることが望ましい。
【００２７】
復号演算部１２は、秘密鍵を用いて暗号文を復号する。復号演算部１２は、ビット導出部１２１と、べき剰余算部１２２とを備える。具体的には、復号演算部１２は、ＲＳＡの復号処理として、ａ＝ｂｄ（ｍｏｄ  ｎ）のべき剰余算をする。ここで、ａは平文を表し、ｂは暗号文を表し、ｄは秘密鍵を表し、ｎは公開鍵をそれぞれ表す。復号演算部１２は、べき剰余算を、ビット導出部１２１によって導出された各ビットに基づいて、べき剰余算部１２２による演算をする。
【００２８】
ビット導出部１２１は、複数の異なる乱数と秘密鍵ｄとを含んだ排他的論理和の演算を混在させた演算により秘密鍵ｄの各ビットを導出する。具体的には、ビット導出部１２１は、秘密鍵ｄを直接的に演算（例えば、シフト演算など）をするのではなく、間接的にｉ番目のビットを導出する（後述する＜安全のための間接的なビット導出＞参照）。
【００２９】
べき剰余算部１２２は、ビット導出部１２１によって秘密鍵ｄの最上位ビット又は最下位ビットから順に導出された各ビットの値に基づいて、２乗算と乗算とを繰り返すことにより復号のためのべき剰余算を代替する。例えば、後述するアルゴリズム１は、秘密鍵ｄの最上位ビットから順に導出された各ビットの値に基づいて、２乗算と乗算とを繰り返す例である。同様に、後述するアルゴリズム２は、秘密鍵ｄの最下位ビットから順に導出された各ビットの値に基づいて、２乗算と乗算とを繰り返す例である。
このようなべき剰余算に、秘密鍵ｄの値を直接的に利用することのない演算（後述する＜安全のための間接的なビット導出＞）を組み込むと、組み込まれたべき剰余算は、演算の過程がメモリやＣＰＵレジスタに展開されても、安全に実行可能である。
【００３０】
＜高速のためのべき剰余算＞
ここで、べき剰余算部１２２が実行する演算について、さらに説明する。
秘密鍵ｄの２進数は、数式１のように表される。
【００３１】
【数１】
0006360440.tif 000002
【００３２】
べき剰余算部１２２は、べき剰余を数式１１のように計算する。
【００３３】
【数２】
0006360440.tif 000003
【００３４】
このべき剰余算（アルゴリズム１）は、次のように実装されることが可能である。
ｔ［０］＝１；
ｆｏｒ（ｉ＝ｋ−１；ｉ＞＝０；ｉ−−）
｛
ｔ［０］＝ｔ［０］＊ｔ［０］  ｍｏｄ  ｎ；
ｔ［１］＝ｔ［０］＊ｂ  ｍｏｄ  ｎ；
ｔ［０］＝ｔ［ｄ［ｉ］］；
｝
【００３５】
べき剰余算部１２２は、べき剰余を数式１２のように計算することもできる。
【００３６】
【数３】
0006360440.tif 000004
【００３７】
この、べき剰余算（アルゴリズム２）は、次のように実装されることが可能である。
ｔ［０］＝１；
ｘ＝ｂ；
ｆｏｒ（ｉ＝０；ｉ＜ｋ；ｉ＋＋）
｛
ｔ［１］＝ｔ［０］＊ｘ  ｍｏｄ  ｎ；
ｔ［０］＝ｔ［ｄ［ｉ］］；
ｘ＝ｘ＊ｘ  ｍｏｄ  ｎ；
｝
【００３８】
復号装置１０は、アルゴリズム１及びアルゴリズム２のどちらの場合も、保護対象は秘密鍵ｄのみであり、秘密鍵ｄの各ビットの値を判定し、判定結果に応じた２乗算と乗算とを繰り返し、高速な処理が可能である。
【００３９】
＜安全のための間接的な右シフト演算＞
例えば、ビット導出部１２１は、数式２の演算により、間接的に秘密鍵ｄのｉビット右シフトを行う。
（（（（ｄ  ｘｏｒ  ｒｄ）  ｘｏｒ  ｒ０  ｘｏｒ  ｒｄ）＞＞ｉ）ｘｏｒ  ｒ）  ｘｏｒ  （（ｒ０＞＞ｉ）  ｘｏｒ  ｒ）・・・数式２
【００４０】
ここで、数式２が、秘密鍵ｄのｉビット右シフトに相当することについて説明する。
ｒ、ｒｚ、ｒｄ、ｒ０は、それぞれ異なる乱数であるとし、次の演算式があるとする。
Ｚ  ｘｏｒ  ｒｚ＝（（（ｄ  ｘｏｒ  ｒｄ）  ｘｏｒ  ｒ０  ｘｏｒ  ｒｄ）＞＞ｉ）ｘｏｒ  ｒ  
この演算式と、ｒｚ＝（ｒ０＞＞ｉ）  ｘｏｒ  ｒとの排他的論理和を行うと、
左辺は、Ｚとなり、右辺は、乱数が消去され、（ｄ＞＞ｉ）となる。
すなわち、秘密鍵ｄのｉビット右シフトは、数式２の演算を行うことにより、実現される。
【００４１】
＜安全のための間接的な論理積演算＞
秘密鍵ｄと１との論理積演算は、例えば、数式３により行われ、間接的に秘密鍵ｄ＆１の値が求められる。
（（ｄ  ｘｏｒ  ｒｄ）＆（１  ｘｏｒ  ｒ１））  ｘｏｒ  （（（ｄ  ｘｏｒ  ｒｄ）＆ｒ１）  ｘｏｒ  （ｒｄ＆（１  ｘｏｒ  ｒ１））  ｘｏｒ  （ｒｄ＆ｒ１））・・・数式３
【００４２】
ここで、数式３が、秘密鍵ｄ＆１の値の導出に相当することについて説明する。
ｒｚ、ｒｄ、ｒ１は、それぞれ異なる乱数であるとし、次の演算式があるとする。
Ｚ  ｘｏｒ  ｒｚ＝（ｄ  ｘｏｒ  ｒｄ）＆（１  ｘｏｒ  ｒ１）
この演算式と、ｒｚ＝（（ｄ  ｘｏｒ  ｒｄ）＆ｒ１）  ｘｏｒ  （ｒｄ＆（１  ｘｏｒ  ｒ１））  ｘｏｒ  （ｒｄ＆ｒ１）との排他的論理和を行うと、
左辺は、Ｚとなり、右辺は、乱数が消去され、（ｄ＆１）となる。
すなわち、秘密鍵ｄ＆１の値は、秘密鍵ｄ＆１の演算の代わりに、数式３の演算を行うことにより、求められる。
したがって、秘密鍵ｄのｉビット目の値は、（ｄ＞＞ｉ）＆１の演算の代わりに、数式２の演算と数式３の演算とを行うことにより、求められる。
このような、秘密鍵ｄの値を直接的に利用することのない演算は、演算の過程がメモリやＣＰＵレジスタに展開されても、安全に実行可能である。
【００４３】
＜安全のための間接的なビット判定＞
べき剰余算部１２２は、秘密鍵ｄの各ビットの値の判定に、各ビットの値と乱数との排他的論理和を用いる。
具体的には、ビットの判定は、（（ｄｉ  ｘｏｒ  ｒ）＝＝（１  ｘｏｒ  ｒ））の判断によって行われる。ここで、ｄｉのビットの値は、数式２で求められた値＆１（すなわち、ｄ＞＞ｉ＆１の値）である。
すなわち、（（ｄｉ  ｘｏｒ  ｒ）＝＝（１  ｘｏｒ  ｒ））の判断が真の場合、ｄｉのビットの値は１であり、偽の場合、ｄｉのビットの値は０である。
べき剰余算部１２２は、このようなビットの判定によって、秘密鍵ｄのｉビット目が０であるか１であるかを判定することで、秘密鍵ｄの値を直接的に利用せずに判定することが可能である。
このような、秘密鍵ｄの値を直接的に利用することのない判定は、演算の過程がメモリやＣＰＵレジスタに展開されても、安全に実行可能である。
【００４４】
＜安全のための複数ビットの判定＞
さらに、べき剰余算部１２２は、ビット導出部１２１によって導出されたビットを複数のビットにまとめた値で場合分けして２乗算と乗算とを組み合わせ、べき剰余算を代替する。べき剰余算部１２２は、複数のビットをまとめて判定することで秘密鍵ｄのｉビット目の推測をさらに困難にすることが可能である。
【００４５】
例えば、べき剰余算部１２２は、秘密鍵ｄのｉビット目とｉ＋１ビット目を一度に判定し、００、０１、１０、１１の４とおりに場合分けする。
【００４６】
例えば、後述するアルゴリズム４において、判定した値が００の場合は、秘密鍵ｄのｉビット目が０の処理と、ｉ＋１ビット目が０の処理とを、次のように行う。
ｔ＝ｔ＊１  ｍｏｄ  ｎ；
ｘ＝ｘ＊ｘ  ｍｏｄ  ｎ；
ｔ＝ｔ＊１  ｍｏｄ  ｎ；
ｘ＝ｘ＊ｘ  ｍｏｄ  ｎ；
【００４７】
例えば、判定した値が１０の場合は、秘密鍵ｄのｉビット目が１の処理と、ｉ＋１ビット目が０の処理とを、次のように行う。
ｔ＝ｔ＊ｘ  ｍｏｄ  ｎ；
ｘ＝ｘ＊ｘ  ｍｏｄ  ｎ；
ｔ＝ｔ＊１  ｍｏｄ  ｎ；
ｘ＝ｘ＊ｘ  ｍｏｄ  ｎ；
【００４８】
＜安全のためのダミー演算の混在＞
べき剰余算部１２２は、ダミーの演算を混在させた演算をする。
【００４９】
上述のアルゴリズム１に、以下のようにダミーの演算を追加することで、べき剰余算部１２２は、ダミーの演算が混在するアルゴリズム３を実行する。ここで、ｂは暗号文である。この処理によって最終的に得られるｔの値が平文ａと等しくなる。
【００５０】
＜アルゴリズム３＞
ｔ＝１；
ｆｏｒ（ｉ＝ｋ−１；ｉ＞＝０；ｉ−−）
｛
ｔ＝ｔ＊ｔ  （ｍｏｄ  ｎ）；
ｉｆ（ｄ［ｉ］＝＝１）
ｔ＝ｔ＊ｂ  ｍｏｄ  ｎ；
ｅｌｓｅ（）
ｔ＝ｔ＊１  ｍｏｄ  ｎ；
｝
【００５１】
同様に、アルゴリズム２に、以下のようにダミーの演算を追加することで、べき剰余算部１２２は、ダミーの演算が混在するアルゴリズム４を実行する。
【００５２】
＜アルゴリズム４＞
ｔ＝１；
ｘ＝ｂ；
ｆｏｒ（ｉ＝０；ｉ＜ｋ；ｉ＋＋）
｛
ｉｆ（ｄ［ｉ］＝＝１）
ｔ＝ｔ＊ｘ（ｍｏｄ  ｎ）；
ｅｌｓｅ（）
ｔ＝ｔ＊１  ｍｏｄ  ｎ；
ｘ＝ｘ＊ｘ  （ｍｏｄ  ｎ）；
｝
【００５３】
上述のように、保護対象が秘密鍵ｄのみなので、オーバーヘッドを抑制することができ、復号装置１０は、復号処理を、安全のための特別の演算であって、秘密鍵ｄを直接的に利用せずに間接的に利用するような特別の演算に代替することが可能である。また、復号装置１０は、復号処理を、安全のためのアルゴリズムであって、秘密鍵ｄに関する処理にダミーの演算を追加し、アルゴリズムの難読化により秘密鍵ｄの推測を困難にするためのアルゴリズムに代替することが可能である。
【００５４】
［実施形態２］
実施形態２は、安全のために保護記憶部を適用した実施形態である。
復号装置１０は、実施形態１の構成に加えて、保護記憶部３０をさらに備える。乱数生成部１１と、復号演算部１２とについては、実施形態１と同様である。
【００５５】
保護記憶部３０（例えば、メインメモリ）は、データに対するアクセスのパターンを保護するアクセスパターン保護部３１を有し、データを秘匿して記憶する。
アクセスパターン保護部３１は、例えば、書き出し処理（例えば、データをキャッシュメモリから保護記憶部３０に戻すとき）において、保護記憶部３０へデータを書き出すときのアドレスを、保護記憶部３０からデータを読み出したときのアドレスとは異なるアドレスに変更する。その結果、アクセスパターン保護部３１は、データを読み出す保護記憶部３０のアドレスを都度変化させる。このように、アクセスパターン保護部３１は、読み出し処理及び書き出し処理におけるアドレスが同一のアドレスとなって、同じパターンのアクセスが発生することを防止する。アクセスパターン保護部３１は、例えば、ＯＲＡＭ（Ｏｂｌｉｖｉｏｕｓ  ＲＡＭ）において実現されている。
【００５６】
復号演算部１２は、保護記憶部３０に記憶された秘密鍵ｄを用い、ビット導出部１２１及びべき剰余算部１２２により、実施形態１において説明した演算をする。
【００５７】
保護が必要となるのは秘密鍵ｄだけであるため、オーバーヘッドが抑制され、復号装置１０は、演算中に秘密鍵ｄを保護記憶部３０に安全に保護しながら、パフォーマンスの著しい低下を招くことなく、高速に復号する。
さらに、復号装置１０は、保護記憶部３０による秘密鍵ｄの安全な保護と、安全のための特別な演算などとを組み合わせて保護技術を適用しても、オーバーヘッドが抑制され、パフォーマンスの著しい低下を招くことなく、高速に復号する。
【００５８】
本実施形態によれば、復号装置１０の復号処理は、秘密鍵ｄから直接的に各ビットを導出しないで間接的に導出するので、秘密鍵ｄの各ビットを導出する過程がメモリやＣＰＵレジスタに展開されても、秘密鍵ｄの各ビットの値について推測されることが困難であり、安全である。復号装置１０の復号処理は、２乗算と乗算とを繰り返す、べき剰余算によって処理され高速であり、各ビットの導出についての間接的な演算が秘密鍵ｄだけに限られているので、オーバーヘッドが抑制され、高速である。
さらに、復号装置１０の復号処理は、アクセスパターン保護部３１を有する保護記憶部３０を適用した場合でも、適用される範囲が秘密鍵ｄ及び秘密鍵ｄに関する演算に限られているので、オーバーヘッドが抑制され、高速である。
復号装置１０の復号処理は、秘密鍵ｄの各ビットの値の判定において、秘密鍵ｄを間接的に利用するので、演算の過程がメモリやＣＰＵレジスタに展開されても、秘密鍵ｄの各ビットの値について推測されることが困難であり、安全である。
復号装置１０の復号処理は、秘密鍵ｄに関するアルゴリズムが、秘密鍵ｄの各ビットを複数のビットにまとめた値での場合分けや、ダミーの演算の挿入により、難読化され、演算の過程がメモリやＣＰＵレジスタに展開されても、秘密鍵ｄの各ビットの値について推測されることが困難であり、安全である。
したがって、復号装置１０は、保護技術を適用した場合でも、オーバーヘッドが抑制され、従来の実装ではできなかった、安全、かつ、高速な復号を行う。
【００５９】
以上、本発明の実施形態について説明したが、本発明は上述した実施形態に限るものではない。また、本発明の実施形態に記載された効果は、本発明から生じる最も好適な効果を列挙したに過ぎず、本発明による効果は、本発明の実施形態に記載されたものに限定されるものではない。
【００６０】
復号装置１０による一連の処理は、ソフトウェアにより行うこともできる。一連の処理をソフトウェアによって行う場合には、そのソフトウェアを構成するプログラムが、汎用のコンピュータなどにインストールされる。また、当該プログラムは、コンピュータ読み取り可能な記録媒体（例えば、ＣＤ−ＲＯＭのようなリムーバブルメディアなど）に記録されてユーザに配布されてもよいし、ネットワークを介してユーザのコンピュータにダウンロードされることにより配布されてもよい。
【符号の説明】
【００６１】
１０    復号装置
１１    乱数生成部
１２    復号演算部
１２１  ビット導出部
１２２  べき剰余算部
３０    保護記憶部
３１    アクセスパターン保護部
【図１】
0006360440.tif 000005
【図２】
0006360440.tif 000006