(57)【要約】【課題】剰余演算装置のサイドチャネル攻撃に対する耐ダンパー性を向上することである。【解決手段】本発明にかかる剰余演算装置は、第１の被乗数と第２の被乗数のうちのいずれか一方の被乗数と、乗数と、除数と、に基づき、モンゴメリ乗算を実行する演算器と、モンゴメリ乗算の演算結果を第１の被乗数として格納する第１の被乗数レジスタと、モンゴメリ乗算の演算結果を除数で減算する減算器と、減算器での減算結果を第２の被乗数として格納する第２の被乗数レジスタとを有する。更に、モンゴメリ乗算の演算結果と除数との比較結果に基づき、第１の被乗数レジスタの値と第２の被乗数レジスタの値のうちのいずれか一方の値を演算器に出力するセレクタを有する。【選択図】図１
2010139544.tif 000002
【特許請求の範囲】
【請求項１】
第１の被乗数と第２の被乗数のうちのいずれか一方の被乗数と、乗数と、除数と、に基づき、モンゴメリ乗算を実行する演算器と、
前記モンゴメリ乗算の演算結果を前記第１の被乗数として格納する第１の被乗数レジスタと、
前記モンゴメリ乗算の演算結果を前記除数で減算する減算器と、
前記減算器での減算結果を前記第２の被乗数として格納する第２の被乗数レジスタと、
前記モンゴメリ乗算の演算結果と前記除数との比較結果に基づき、前記第１の被乗数レジスタの値と前記第２の被乗数レジスタの値のうちのいずれか一方の値を前記演算器に出力するセレクタと、
を有する剰余演算装置。
【請求項２】
前記減算器は、前記モンゴメリ乗算の演算結果と前記除数との比較結果に基づきボロー信号を生成し、前記セレクタに当該ボロー信号を出力し、
前記セレクタは、当該ボロー信号に基づき前記第１の被乗数レジスタの値および前記第２の被乗数レジスタの値のうちのいずれか一方の値を前記演算器に出力する請求項１に記載の剰余演算装置。
【請求項３】
前記セレクタは、前記モンゴメリ乗算の演算結果が前記除数よりも小さい場合に、前記第１の被乗数レジスタの値を前記演算器に出力する、請求項１または２に記載の剰余演算装置。
【請求項４】
前記第１の被乗数レジスタ、前記第２の被乗数レジスタ、前記乗数を格納する乗数レジスタ、前記除数を格納する除数レジスタは、データバスと接続されており、当該データバスを経由して、データの書き込み、及びデータの読み込みを行う請求項１乃至３のいずれか１項に記載の剰余演算装置。
【請求項５】
前記第１の被乗数をＡ、前記第２の被乗数をＳ＿ｔｍｐ、前記乗数をＢ、前記除数をＮとした場合、
前記モンゴメリ乗算を実行する演算器は、Ｓ＝Ｐ（ＡＢ）Ｎの演算を実行し、
前記第１の被乗数レジスタは、前記モンゴメリ乗算の演算結果であるＳを前記第１の被乗数として格納し、
前記減算器は、Ｓ−Ｎの演算を実行し、
前記第２の被乗算レジスタは、前記減算器の減算結果であるＳ−Ｎを格納し、
前記セレクタは、前記モンゴメリ乗算の演算結果であるＳと前記除数Ｎとの比較結果に基づき、前記モンゴメリ乗算の演算結果であるＳの値、または前記減算器の減算結果であるＳ−Ｎの値を前記演算器に出力する、請求項１乃至４のいずれか１項に記載の剰余演算装置。
【請求項６】
被乗数と、乗数と、除数と、に基づき、モンゴメリ乗算を実行し、
前記モンゴメリ乗算の演算結果を第１の被乗数として格納し、
前記モンゴメリ乗算の演算結果を前記除数で減算し、当該減算した結果を第２の被乗数として格納し、
前記モンゴメリ乗算の演算結果と前記除数との比較結果に基づき、前記第１の被乗数レジスタの値および前記第２の被乗数レジスタの値のうちのいずれか一方の値を選択し、
前記選択した被乗数と、乗数と、除数と、に基づき、モンゴメリ乗算を実行する、
剰余演算方法。
【請求項７】
前記モンゴメリ乗算の演算結果が前記除数よりも小さい場合に、前記第１の被乗数レジスタの値を選択する、請求項６に記載の剰余演算方法。
【請求項８】
前記被乗数をＡ、前記乗数をＢ、前記除数をＮとした場合、モンゴメリ乗算であるＳ＝Ｐ（ＡＢ）Ｎを実行し、
前記モンゴメリ乗算の演算結果であるＳを前記第１の被乗数として格納し、
前記モンゴメリ乗算の演算結果Ｓを前記除数Ｎで減算し、当該減算した結果Ｓ−Ｎを第２の被乗数として格納し、
前記モンゴメリ乗算の演算結果Ｓと前記除数Ｎの比較結果に基づき、前記第１の被乗数レジスタの値Ｓおよび前記第２の被乗数レジスタの値Ｓ−Ｎのうちのいずれか一方の値を選択し、
前記選択した被乗数と、乗数Ｂと、除数Ｎと、に基づき、モンゴメリ乗算を実行する、
請求項６または７に記載の剰余演算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、剰余演算機能を備えた剰余演算装置に関し、特にモンゴメリ乗算演算器を用いた符号化及び復号化に有効な技術に関する。
【背景技術】
【０００２】
誰もが、いつでも、どこでも情報にアクセスできるというユビキタスネットワーク社会におけるセキュリティ強化の必要性から、様々な情報機器で暗号アルゴリズムが利用されている。これに伴い、暗号アルゴリズムや効率の良い実装手法に関する研究、開発も行われている。しかしながら、暗号アルゴリズムが盛んに研究、開発される一方、暗号アルゴリズムや暗号アルゴリズムの実装に関する脆弱性を研究、開発する活動も盛んである。特に近年、サイドチャネル攻撃という実装攻撃手法の研究が学会等を賑やかせている。
【０００３】
サイドチャネル攻撃とは、本来の通信経路（チャネル）以外の、例えば処理中の消費電力や電磁波、処理時間などのサイドチャネル情報から内部の秘密情報を得ようとする攻撃である。サイドチャネル攻撃の一手法として、タイミング解析というものがある。この手法は、演算する値によって処理時間が異なることに着目して内部の秘密情報を導出する手法である。
【０００４】
べき乗剰余演算を用いるＲＳＡ（登録商標）（Ｒｉｖｅｓｔ・Ｓｈａｍｉｒ・Ａｄｌｅｍａｎ）暗号の様に安全なアルゴリズムであると一般的に認知されていたとしても、脆弱性のある実装を行ってしまうと、サイドチャネル攻撃（特にタイミング解析）により秘密鍵を容易に推測されてしまう恐れがある。つまり、安全な暗号アルゴリズムだけではなく、暗号アルゴリズムの安全な実装も必要となる。安全な実装を実現するためには、実装回路自身の耐タンパー性の向上が必須となる。
【０００５】
べき乗剰余演算は、以下に説明する公開鍵暗号方式の暗復号処理などの計算に用いられている。公開鍵暗号方式の中でも、現在、ＲＳＡ（登録商標）暗号が主として用いられている。ＲＳＡ（登録商標）暗号は、任意の２つの素数を乗算した値Ｎを素因数分解する際の困難性と、Ｎを法とする数の範囲を利用する暗号化方式であり、暗号化及び復号のためにべき乗剰余演算（Ｍｅ  ｍｏｄ  Ｎ ）を実行する。
【０００６】
べき乗剰余演算は、通常、以下に示す乗算剰余演算の繰り返し処理に置き換えて実行される。
例えば、ｅ＝１９とするとき、Ｃ＝Ｍｅ  ｍｏｄ  Ｎは、
ｅ＝１９＝１＋２×（１＋２×（０＋２×（０＋２×１）））により、
Ｃ＝Ｍ１９  ｍｏｄ  Ｎ
＝Ｍ（１＋２×（１＋２×（０＋２×（０＋２×１））））  ｍｏｄ  Ｎ
＝（（（（Ｍ１）２×Ｍ０）２×Ｍ０）２×Ｍ１）２×Ｍ１  ｍｏｄ  Ｎ
＝（（（Ｍ２）２）２×Ｍ）２×Ｍ  ｍｏｄ  Ｎ
となる。
【０００７】
上述のようにべき数ｅを分解すれば、Ｍを単純にｅ−１回掛けるよりも乗算回数を低減できるため、演算時間を短縮できる。尚、上記のべき数ｅの分解方法はバイナリー法と呼ばれており、一般的なｅの分解方法である。
しかしながら、上記のような乗算剰余演算も、乗算によって演算桁数が倍になり、さらに乗算結果をＮで除算するため、ハードウェアまたはソフトウェアのいずれを利用しても効率よく処理するのが困難な演算である。そこで、乗算剰余演算を効率化するための手法として、モンゴメリ（Ｍｏｎｔｇｏｍｅｒｙ）乗算と呼ばれるアルゴリズムを応用した演算方法が知られている。
【０００８】
図５に、モンゴメリ乗算アルゴリズム（Ｓ＝Ｐ（ＡＢ）Ｎ＝ＡＢ×２−ｎ  ｍｏｄ  Ｎ）を示す。また図６に、べき乗剰余演算アルゴリズム（Ｃ＝Ｍ１９  ｍｏｄ  Ｎの場合）を示す。図５のモンゴメリ乗算アルゴリズムを図６のべき乗剰余演算アルゴリズムに応用すると、実質的な除算を必要とすることなく上述した、
Ｃ＝Ｍ１９  ｍｏｄ  Ｎ＝（（（Ｍ２）２）２×Ｍ）２×Ｍ  ｍｏｄ  Ｎ
のべき乗剰余演算を処理できる。
【０００９】
上記Ｃの求め方は図６に示す通りである。以下に、図６のべき乗剰余演算アルゴリズムを図内の番号に沿って説明する。
まず、（１）の事前計算を行い、分解されたべき数ｅに従い（２）〜（７）のように、乗算、２乗算のモンゴメリ乗算を繰り返し行い、最後のモンゴメリ乗算である（８）で１を掛けて２ｎを除去し、Ｃを求める。
【００１０】
図６のべき乗剰余演算の計算例では、べき数がｅ＝１９であるため、８回のモンゴメリ乗算を行えば計算できる。しかし、現在、ＲＳＡ（登録商標）の中でも広く利用されているＲＳＡ１０２４（鍵長１０２４ビット）の場合、Ｃ／Ｍ／Ｎ／ｅが１０２４ビットであり、前述のべき数の分解方法によると平均で１５３６回のモンゴメリ乗算を繰り返し行うことになる。
前述の通り、べき乗剰余演算は、モンゴメリ乗算（Ａ×Ｂ×２−ｎ  ｍｏｄ  Ｎ、及び、Ａ２×２−ｎ  ｍｏｄ  Ｎ）を利用して繰り返し計算するのが一般的である。
【００１１】
モンゴメリ乗算は、除算を実質行わずに計算できるのが大きな特徴である。モンゴメリ乗算の演算結果Ｓは、図５のモンゴメリ乗算アルゴリズムの６）でわかるように、０≦Ｓ＜２Ｎとなり、Ａ／Ｂ／Ｎ の値によってはＮの値を超える場合があり得る。Ｎの値を超える場合、図５のモンゴメリ乗算アルゴリズムの６）にて、演算結果ＳがＮより大きければＳ−Ｎの減算を行い、演算結果の補正（リダクション）を行う必要がある。
【００１２】
図７は、背景技術におけるモンゴメリ乗算の剰余演算装置を示すブロック図である（特許文献１参照）。図７に示されている剰余演算装置は、モンゴメリ乗算の被乗数Ａ、乗数Ｂ、除数Ｎを保持するレジスタ１８〜２０、乗数が異なるモンゴメリ乗算を設定するコントロールレジスタ１７、コントロールレジスタ１７が設定するモンゴメリ乗算に対応するためのセレクタ１６、演算器１５、バス１２から構成されている。
【００１３】
背景技術では、図７に示す剰余演算装置でモンゴメリ乗算を処理しており、べき乗剰余演算を処理する際には、図６のべき乗剰余演算アルゴリズムに従い、モンゴメリ乗算を繰り返し演算してべき乗剰余演算を行う。つまり、図７にて示される剰余演算装置で、図６のべき乗剰余演算アルゴリズムの（１）でＭ´を求め、演算器１５の入力となるＡ、Ｂの初期値をＭ´とし、図６のべき乗剰余演算アルゴリズムの（２）〜（７）のように分解されたべき数ｅに従い、図８に示すモンゴメリ乗算処理フローを繰り返し行い、最後に図６のべき乗剰余演算アルゴリズムの（８）にて２ｎを除去してべき乗剰余演算を処理する。
【００１４】
次に、上述の図８のモンゴメリ乗算処理フローを説明する。図８は、背景技術におけるモンゴメリ乗算の処理フローを示す図である。まず、分解されたべき数に従い、Ｓ１１のモンゴメリ乗算の繰り返し演算をスタートする。但し、前述の通りＡ＝Ｂ＝Ｍ´の状態である。Ｓ１２でモンゴメリ乗算と、演算結果ＳとＮの大小比較の演算を行い、モンゴメリ乗算の結果を図７のレジスタ１８に、大小比較の結果を図７の演算器１５の内部に保持する。大小比較の演算は、図７の演算器１５の内部にて処理される。次に、Ｓ１３にて前述の演算結果ＳとＮの大小比較の結果に従い、リダクション（Ｓ＝Ｓ−Ｎ）を行うか、行わないか判定する。リダクションを行わない場合は、Ｓ１４にて図７のレジスタ１８に保持されたＳの値をそのままＳとする。リダクションを行う場合は、Ｓ１５にて図７の演算器１５の内部でＳ−Ｎの減算処理を行って結果Ｓを図７のレジスタ１８に上書きして再度保持する。
【００１５】
次に、分解されたべき数に従い、引き続きモンゴメリ乗算を繰り返し行うかどうかをＳ１６で判定する。分解されたべき数に従い、全ての繰り返しモンゴメリ乗算が完了していれば、Ｓ２０のモンゴメリ乗算の繰り返し演算完了に分岐する。引き続きモンゴメリ乗算を繰り返し行う場合は、Ｓ１７にて次のモンゴメリ乗算が乗算なのか２乗算なのか、分解されたべき数を参照し判定する。次のモンゴメリ乗算が２乗算の場合は、Ｓ１８にてＡ＝Ｂ＝Ｓとし、また乗算の場合は、Ｓ１９にてＡ＝Ｓとして、それぞれＳ１２のモンゴメリ乗算と、演算結果ＳとＮの大小比較の演算に分岐する。
【００１６】
図９は、背景技術におけるべき乗剰余演算の一部の処理動作のタイミングチャートを示す図である。前述の説明から背景技術では、図９に示す通り、繰り返し行われるモンゴメリ乗算にて、モンゴメリ乗算の被乗数Ａ、乗数Ｂ、除数Ｎの値に依存してモンゴメリ乗算結果ＳがＮよりも大きい場合や小さい場合があるため、リダクションがランダムに発生することになる。繰り返し行われるモンゴメリ乗算にて、ランダムに発生するリダクションを繰り返し行うことによってべき乗剰余演算全体の処理時間が増大することになる。従って、べき乗剰余演算全体の処理時間の増大を防ぐために、背景技術ではリダクションが発生する頻度を減少させる工夫を行っている。
【００１７】
また、特許文献２には、剰余算出をより小規模の回路でより高速に実行するために、符号付き２進数Ａ、Ｂにおいて、演算結果Ａ−Ｂ及びＡを符号なし２進数として大小比較を行い、小さい方を選択出力する技術が開示されている。
【特許文献１】特開平１０−２１０５７号公報
【特許文献２】特開２００７−３４０３８号公報
【発明の開示】
【発明が解決しようとする課題】
【００１８】
背景技術では、図９に示す通り、繰り返し行われるモンゴメリ乗算の演算結果に依存して、リダクションを行ったり、行わなかったりする。このリダクションは、正常なモンゴメリ乗算結果を得るためには必要な処理である。しかしながら、このリダクションの処理行為により、秘密情報である秘密鍵の漏洩につながるおそれがある。つまり、前述したサイドチャネル攻撃の一手法であるタイミング解析により、リダクションを行った、行っていないという判別を容易に推測することができ、また前述の判別が１つのヒントとなり結果的に秘密情報である秘密鍵を推測することができるという問題がある。
【００１９】
ＲＳＡ（登録商標）暗号で説明すると、復号時のべき数値（例えば前述のｅ）が秘密鍵であり、第三者に知られないよう秘密にしなければならないものであるが、前述したタイミング解析により秘密鍵が漏洩するおそれがある。このようなことが発生する原因は、モンゴメリ乗算を完了しないと、リダクションを必要とするか、必要としないかが判定できない点にある。故に、背景技術では図９に示す通り、モンゴメリ乗算終了後に図８のＳ１５のリダクションを行っている。モンゴメリ乗算終了後のリダクションの存在が、サイドチャネル攻撃に対する耐性を低下させている理由となる。
【課題を解決するための手段】
【００２０】
本発明にかかる剰余演算装置は、第１の被乗数と第２の被乗数のうちのいずれか一方の被乗数と、乗数と、除数と、に基づき、モンゴメリ乗算を実行する演算器と、前記モンゴメリ乗算の演算結果を前記第１の被乗数として格納する第１の被乗数レジスタと、前記モンゴメリ乗算の演算結果を前記除数で減算する減算器と、前記減算器での減算結果を前記第２の被乗数として格納する第２の被乗数レジスタと、前記モンゴメリ乗算の演算結果と前記除数との比較結果に基づき、前記第１の被乗数レジスタの値と前記第２の被乗数レジスタの値のうちのいずれか一方の値を前記演算器に出力するセレクタと、を有する。
【００２１】
このような構成により、モンゴメリ乗算の演算中に強制的にリダクションを行い、リダクション前の値とリダクション後の値の両方を保持し、これらの値のうちのいずれか一方を選択するという処理が可能となり、リダクション期間を見かけ上みえなくすることができる。リダクション期間を見かけ上みえなくなることで、サイドチャネル攻撃に対する耐ダンパー性が向上する。
【００２２】
また、本発明にかかる剰余演算方法は、被乗数と、乗数と、除数と、に基づき、モンゴメリ乗算を実行し、前記モンゴメリ乗算の演算結果を第１の被乗数として格納し、前記モンゴメリ乗算の演算結果を前記除数で減算し、当該減算した結果を第２の被乗数として格納し、前記モンゴメリ乗算の演算結果と前記除数との比較結果に基づき、前記第１の被乗数レジスタの値および前記第２の被乗数レジスタの値のうちのいずれか一方の値を選択し、前記選択した被乗数と、乗数と、除数と、に基づき、モンゴメリ乗算を実行する。
【００２３】
このような剰余演算方法により、モンゴメリ乗算の演算中に強制的にリダクションを行い、リダクション前の値とリダクション後の値の両方を保持し、これらの値のうちのいずれか一方を選択するという処理が可能となり、リダクション期間を見かけ上みえなくすることができる。リダクション期間を見かけ上みえなくなることで、サイドチャネル攻撃に対する耐ダンパー性が向上する。
【発明の効果】
【００２４】
本発明により、剰余演算装置のサイドチャネル攻撃に対する耐ダンパー性を向上することができる。
【発明を実施するための最良の形態】
【００２５】
以下、図面を参照して本発明の実施形態について説明する。
図１は本発明の実施形態にかかる剰余演算装置を示すブロック図である。
剰余演算装置１０は、第１の被乗数または第２の被乗数と、乗数と、除数と、に基づき、モンゴメリ乗算を実行する演算器１と、モンゴメリ乗算の演算結果を第１の被乗数として格納する第１の被乗数レジスタ２と、モンゴメリ乗算の演算結果を除数で減算する減算器６と、を有する。また、減算器６での減算結果を第２の被乗数として格納する第２の被乗数レジスタ３と、モンゴメリ乗算の演算結果と除数との比較結果に基づき、第１の被乗数レジスタの値および第２の被乗数レジスタの値のうちのいずれか一方の値を演算器１に出力するセレクタ８と、を有する。
【００２６】
更に詳細に説明すると、剰余演算装置１０は、リダクション前までのＳ＝Ｐ（ＡＢ）Ｎの演算を行い、演算結果Ｓを出力する演算器１と、被乗数Ａを格納する第１の被乗数レジスタ２（以下、被乗数Ａレジスタともいう）と、同じく被乗数Ｓ＿ｔｍｐを格納する第２の被乗数レジスタ３（以下、被乗数Ｓ＿ｔｍｐレジスタともいう）と、乗数Ｂを格納する乗数レジスタ４と、除数Ｎを格納する除数レジスタ５と、を有する。剰余演算装置１０は更に、リダクションであるＳ＿ｔｍｐ＝Ｓ−Ｎの減算を行い、減算結果Ｓ＿ｔｍｐを出力する組み合わせ回路構成の減算器６と、ボロー信号７が"１"の場合には被乗数Ａレジスタ２の出力を選択し、"０"の場合には被乗数Ｓ＿ｔｍｐレジスタ３の出力を選択するセレクタ８を有する。
【００２７】
演算器１のＡ入力には、セレクタ８の出力信号が接続され、演算器１のＢ入力には、乗数Ｂレジスタ４の出力信号が接続され、演算器１のＮ入力には、除数Ｎレジスタ５の出力信号が接続される。演算器１のＳ出力は、演算結果Ｓをあるビット長単位で時分割に下位ビット側から出力する。
減算器６のＳ入力には、演算器１のＳ出力が接続され、Ｎ入力には、除数Ｎレジスタ５の出力信号が接続される。減算器６はＳ−Ｎの減算結果から、Ｓ＜Ｎの場合には、ボロー信号７を"１"にし、それ以外の場合には、ボロー信号７を"０"にする。ボロー信号７はセレクタ８に出力される。また、減算器６のＳ＿ｔｍｐ出力は、減算結果Ｓ＿ｔｍｐをあるビット長単位で時分割に下位ビット側から出力する。
【００２８】
被乗数Ａレジスタ２は、データバス９を経由して、ＣＰＵからのデータの書き込み、読み出しを行う機能を有し、さらに演算器１の出力Ｓを書き込む機能を有する。また、被乗数Ａレジスタ２はセレクタ８を経由して演算器１に対し、あるビット長単位で時分割に下位ビット側から保持データを出力する。
被乗数Ｓ＿ｔｍｐレジスタ３は、データバス９を経由して、ＣＰＵからのデータの書き込み、読み出しを行う機能を有し、さらに減算器６の出力Ｓ＿ｔｍｐを書き込む機能を有する。また、被乗数Ｓ＿ｔｍｐレジスタ３はセレクタ８を経由して演算器１に対し、あるビット長単位で時分割に下位ビット側から保持データを出力する。
【００２９】
乗数Ｂレジスタ４、除数Ｎレジスタ５は、データバス９を経由して、ＣＰＵからのデータを書き込み、読み出しを行う機能を有する。
セレクタ８は、ボロー信号７を入力し、当該ボロー信号に基づき、被乗数Ａレジスタの値および被乗数Ｓ＿ｔｍｐレジスタの値のうちのいずれか一方の値を演算器１に出力する。
【００３０】
本実施形態にかかる発明は、図１に示す剰余演算装置１０でモンゴメリ乗算を処理しており、べき乗剰余演算を処理する際には、図６のべき乗剰余演算アルゴリズムに従い、モンゴメリ乗算を繰り返し演算してべき乗剰余演算を行う。つまり図１に示す剰余演算装置１０で、図６のべき乗剰余演算アルゴリズムの（１）にてＭ´を求め、演算器１の入力であるＡ、Ｂの初期値をＭ´とし、図６のべき乗剰余演算アルゴリズムの（２）〜（７）のように分解されたべき数ｅに従い、図２に示すモンゴメリ乗算処理フローを繰り返し行う。そして最後に図６のべき乗剰余演算アルゴリズムの（８）にて２ｎを除去してべき乗剰余演算を処理する。
【００３１】
次に、上述の図２のモンゴメリ乗算処理フローを説明する。図２は、本実施形態にかかるモンゴメリ乗算の処理フローを示す図である。
まず、分解されたべき数に従い、Ｓ１のモンゴメリ乗算の繰り返し演算をスタートする。但し、前述の通りＡ＝Ｂ＝Ｍ´の状態である。
次のＳ２では、モンゴメリ乗算を行い、また強制的にリダクションも行う。そして、モンゴメリ乗算の演算結果Ｓとリダクションした結果Ｓ＿ｔｍｐを同時にそれぞれ記憶しておく。
【００３２】
次にＳ３では、前述のリダクションした結果Ｓ＿ｔｍｐを求めた際に、ボローが発生したか（Ｂｏｒｒｏｗ＝１）、発生しなかったか（Ｂｏｒｒｏｗ＝０）を確認する。ボローが発生した場合（Ｂｏｒｒｏｗ＝１）、つまり、モンゴメリ乗算の演算結果Ｓが除数Ｎよりも小さい場合、Ｓ４に示す通り、モンゴメリ乗算の正常な結果Ｓ´ はＳ２で行ったモンゴメリ乗算の演算結果Ｓとなる。また、ボローが発生しなかった場合（Ｂｏｒｒｏｗ＝０）、Ｓ５に示す通り、モンゴメリ乗算の正常な結果Ｓ´はＳ２で行ったリダクションした結果Ｓ＿ｔｍｐとなる。
【００３３】
次に、分解されたべき数に従い、引き続きモンゴメリ乗算を繰り返し行うかどうかをＳ６で判定する。分解されたべき数に従い、全ての繰り返しモンゴメリ乗算が完了していれば、Ｓ１０のモンゴメリ乗算の繰り返し演算完了に分岐する。引き続きモンゴメリ乗算を繰り返し行う場合は、Ｓ７にて次のモンゴメリ乗算が乗算なのか２乗算なのか、分解されたべき数を参照し判定する。次のモンゴメリ乗算が２乗算の場合は、Ｓ８にてＡ＝Ｂ＝Ｓ´とし、また乗算の場合は、Ｓ９にてＡ＝Ｓ´とする。そして、再びＳ２においてモンゴメリ乗算とリダクションを行う。
【００３４】
すなわち、図２に示す本実施形態にかかる剰余演算方法は、まず、被乗数と乗数と除数とに基づきモンゴメリ乗算を実行する。
次に、モンゴメリ乗算の演算結果を第１の被乗数として格納する。
次に、モンゴメリ乗算の演算結果を除数で減算し、当該減算した結果を第２の被乗数として格納する。
次に、モンゴメリ乗算の演算結果と除数との比較結果に基づき、第１の被乗数レジスタの値および第２の被乗数レジスタの値のうちのいずれか一方の値を選択する。
そして選択した被乗数と乗数と除数とに基づき再度モンゴメリ乗算を実行する。
【００３５】
さて、上述した図２のモンゴメリ乗算処理フローの説明を踏まえて、以下に本実施形態にかかる剰余演算装置１０におけるモンゴメリ乗算の動作について図１を参照して説明する。また図３は、本実施形態にかかるモンゴメリ乗算における図１の各種信号のタイミングチャートを示す図である。Ｔ０は演算器１のモンゴメリ乗算開始タイミングであり、Ｔ１は演算器１のモンゴメリ乗算完了タイミングである。またＴ１は演算器１の次のモンゴメリ乗算開始タイミングであり、Ｔ２は演算器１のモンゴメリ乗算完了タイミングである。図１の説明と共に、本実施形態にかかるモンゴメリ乗算における各種信号のタイミングについても適宜説明する。
【００３６】
図１において、演算器１の入力Ａには、セレクタ８で選択された被乗数Ａレジスタ２の出力または被乗数Ｓ＿ｔｍｐレジスタ３の出力があるビット長単位で時分割に下位ビット側から入力される。また、入力Ｂには乗数Ｂレジスタ４の出力が入力され、入力Ｎには除数Ｎレジスタ５の出力が入力される。更に、演算器１はリダクション前までのＳ＝Ｐ（ＡＢ）Ｎの演算をあるビット長単位で時分割に下位ビット側から行い、演算結果Ｓを同様にあるビット長単位で時分割に下位ビット側から出力する。演算結果Ｓのタイミングを図３の演算器１のＳに示す。
【００３７】
組み合わせ回路で構成される減算器６では、演算器１より時分割に出力された演算結果 Ｓと入力されるＮとのリダクションＳ−Ｎを時分割に行い、減算結果Ｓ＿ｔｍｐをあるビット長単位で時分割に下位ビット側から出力する。減算結果Ｓ＿ｔｍｐのタイミングを図 ３の減算器６のＳ＿ｔｍｐに示す。
演算器１から時分割に出力される前記演算結果Ｓは、被乗数Ａレジスタ２に随時格納され、また同時に減算器６から時分割に出力される前記減算結果Ｓ＿ｔｍｐは、被乗数Ｓ＿ｔｍｐレジスタ３に随時格納される。被乗数Ａレジスタ２及び被乗数Ｓ＿ｔｍｐレジスタ３のタイミングを図３の被乗数Ａレジスタ２及び被乗数Ｓ＿ｔｍｐレジスタ３に示す。
【００３８】
時分割に演算結果を出力する演算器１及び減算器６で全ての時分割の演算が完了したとき、被乗数Ａレジスタ２には演算結果Ｓの全ビットが格納されている状態となり、同時に被乗数Ｓ＿ｔｍｐレジスタ３にもリダクションの結果Ｓ＿ｔｍｐの全ビットが格納されている状態となる。同時に減算器６では、最終的にＳ−Ｎの演算結果でボローが発生したか、発生しなかったかを示すボロー信号７を生成する。ボローが発生した場合はボロー信号７が"１"となり、ボローが発生しなかった場合はボロー信号７が"０"となる。
【００３９】
前述の被乗数Ａレジスタ２に演算結果Ｓの全ビットが格納されている状態を図３のＳ１２及びＳ２２に示す。また、前述の被乗数Ｓ＿ｔｍｐレジスタ３にリダクションの結果 の全ビットが格納されている状態を図３のＳ１３及びＳ２３に示す。また、前述のボロー信号の状態を図３のＳ１４及びＳ２４に示す。
ボロー信号７が"１"の場合、モンゴメリ乗算はリダクションを必要としなかったことになり、正常な演算結果は被乗数Ａレジスタ２に保持されていることになる。また、ボロー信号７が"０"の場合、モンゴメリ乗算はリダクションを必要としたことになり、正常な演算結果は被乗数Ｓ＿ｔｍｐレジスタ３に保持されていることになる。
さて、図６のべき乗剰余演算アルゴリズムに示す通り、べき乗剰余演算はモンゴメリ乗算を繰り返し演算して行う。従って、上述のモンゴメリ乗算期間中に強制的にリダクションを行わせる動作により、べき乗剰余演算期間中には、モンゴメリ乗算完了後のリダクションが存在しないことになる。図４は、本実施形態にかかるべき乗剰余演算の一部の処理動作のタイミングチャートを示す図であり、この図からモンゴメリ乗算完了後のリダクションが存在しないことがわかる。
【００４０】
本実施形態にかかる剰余演算装置１０において、モンゴメリ乗算の演算中に強制的にリダクションを行い、リダクション前の値とリダクション後の値の両方を保持しておくことにより、図９の背景技術では見えていたＳ−Ｎのリダクション期間が図４に示す通り、見かけ上、見えなくなる。そして、リダクション期間が見えなくなる事により、サイドチャネル攻撃の一手法であるタイミング解析を用いて、処理時間の違いからリダクションの有無を検出することが困難となる。従って、リダクションの有無の判別が出来ず、秘密鍵の推測は困難となる。つまり、サイドチャネル攻撃に対する耐タンパー性が向上する。
【００４１】
また、モンゴメリ乗算の結果がリダクションを不要とする場合においてもダミーでリダクションを行わせて、単純に毎度のモンゴメリ乗算終了後にリダクションを行わせると本実施形態にかかる発明と同じ効果が得られる。しかし、乗数、被乗数、除数のそれぞれが多倍長整数で、且つ１５００回、３０００回と繰り返しモンゴメリ乗算を行うＲＳＡ（登録商標）暗号にてダミーのリダクションを行うとなると、べき乗剰余演算全体の処理性能の低下は避けられない。
【００４２】
本実施形態にかかる発明では、前述のダミー処理を挿入することもなく、つまり処理性能を低下することなく耐タンパー性が向上し、また、モンゴメリ乗算後のリダクション期間の削減に付随して、処理データ量の削減が可能となり、べき乗剰余演算の処理性能が向上する。
【００４３】
以上、まとめると、本実施形態にかかる剰余演算装置ではモンゴメリ乗算の演算中に強制的にリダクションを行い、強制的にリダクションした結果とリダクション前の結果とをそれぞれの記憶装置に保持する。そして、リダクションの結果に基づき生成されるボロー信号の値により、どちらが正常な演算結果であるかを判定する。
モンゴメリ乗算の演算後ではなく、演算期間中に強制的にリダクションを行うことにより、リダクション期間が見かけ上、見えなくなり、タイミング解析にてリダクションを行った、行っていないという判別を容易に推測することができなくなる。
【００４４】
なお、本発明は上記実施形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
前述した実施形態では、ｅの分解方法にバイナリー法を適用した場合の説明を行ったが、その他のｅの分解方法でも、前述の本実施形態にかかる発明と同様の効果を得ることができる。
また、モンゴメリ乗算回数を低減させることが出来る効率の良いｅの分解方法を適用することにより、前述の実施形態にかかる発明の効果を保ちつつ、べき乗剰余演算の処理性能を向上させることができる。
また、前述した実施形態では、乗数、被乗数、除数、モンゴメリ乗算結果を保持する手段をレジスタで説明したが、これらを保持することができる回路、または装置であればレジスタに限定されることはない。
【００４５】
よって、本実施形態にかかる剰余演算装置により、サイドチャネル攻撃の一手法であるタイミング解析にて、処理時間の違いからリダクションの有無を検出することが出来ず、秘密鍵の推測は困難となり、サイドチャネル攻撃に対する耐タンパー性を向上することができる。
また、処理性能低下の起因となるリダクションのダミー処理を挿入することなく、耐タンパー性の向上が実現できる。
また、モンゴメリ乗算後のリダクション期間の削減に付随して、処理時間の削減が可能となり、べき乗剰余演算の処理性能の向上が実現できる。
また、べき乗剰余演算は、公開鍵暗号方式のベースとなる演算であるため、ＲＳＡ（登録商標）暗号に限らず、楕円曲線暗号、デジタル署名などべき乗剰余演算を必要とする全ての公開鍵暗号方式に適用可能である。
また、暗号に限らず、モンゴメリ乗算を必要とする情報処理系に適用することで、処理データ量削減となり、べき乗剰余演算の処理性能向上を実現できる。
【図面の簡単な説明】
【００４６】
【図１】実施形態にかかる剰余演算装置のブロック図である。
【図２】実施形態にかかるモンゴメリ乗算の処理フローを示す図である。
【図３】実施形態にかかるモンゴメリ乗算のタイミングチャートを示す図である。
【図４】実施形態にかかるべき乗剰余演算の一部の処理動作のタイミングチャートを示す図である。
【図５】モンゴメリ乗算アルゴリズムを示す図である。
【図６】べき乗剰余演算アルゴリズムを示す図である。
【図７】背景技術の剰余演算装置のブロック図である。
【図８】背景技術のモンゴメリ乗算の処理フローを示す図である。
【図９】背景技術のべき乗剰余演算の一部の処理動作のタイミングチャートを示す図である。
【符号の説明】
【００４７】
１  演算器
２  被乗数Ａレジスタ（第１の被乗数レジスタ）
３  被乗数Ｓ＿ｔｍｐレジスタ（第２の被乗数レジスタ）
４  乗数レジスタ
５  除数レジスタ
６  減算器
７  ボロー信号
８  セレクタ
９  データバス
１０  剰余演算装置
【図１】
2010139544.tif 000003
【図２】
2010139544.tif 000004
【図３】
2010139544.tif 000005
【図４】
2010139544.tif 000006
【図５】
2010139544.tif 000007
【図６】
2010139544.tif 000008
【図７】
2010139544.tif 000009
【図８】
2010139544.tif 000010
【図９】
2010139544.tif 000011