べき乗剰余演算装置、べき乗剰余演算方法およびプログラム
【課題】べき乗剰余演算において、電力解析および処理時間解析に基づくサイドチャネル攻撃への耐性を向上させること。
【解決手段】べき乗剰余演算装置は、べき乗指数ｋとべき乗剰余演算の法Ｎを保持する暗号鍵保持部と、べき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する乱数生成部と、処理ビット幅ｐおよびべき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成するべき乗指数制御部と、処理回数ｑ、演算用べき乗指数ｆ、およびべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する剰余演算部と、を備えている。
【解決手段】べき乗剰余演算装置は、べき乗指数ｋとべき乗剰余演算の法Ｎを保持する暗号鍵保持部と、べき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する乱数生成部と、処理ビット幅ｐおよびべき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成するべき乗指数制御部と、処理回数ｑ、演算用べき乗指数ｆ、およびべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する剰余演算部と、を備えている。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、べき乗剰余演算装置、べき乗剰余演算方法およびプログラムに関し、特に、耐タンパー性を有するべき乗剰余演算装置、べき乗剰余演算方法およびプログラムに関する。
【背景技術】
【０００２】
電子決済に用いられるＩＣカード、決裁可能な端末機器などの普及に伴い、重要な情報の秘匿性を向上させるために、暗号技術の重要性が増大している。
【０００３】
一方、暗号化された情報に対する攻撃方法も高度化されている。特に、暗号処理を実行するプロセッサの処理時間または消費電力を測定し、統計的手法を用いて、暗号プロセッサ内部の秘密情報を解析するサイドチャネル攻撃が現実的な脅威となってきている。そこで、非正規な手段による機密データの読み取りを防ぐ能力（耐タンパー性）をさらに向上させる必要がある。
【０００４】
一例として、特許文献１に、耐タンパー性べき乗演算方法が記載されている。図５は、特許文献１に記載された耐タンパーべき乗剰余演算装置の構成を示すブロック図である。
【０００５】
べき乗剰余演算装置１０１は、ＩＣカードなどの計算機のべき乗剰余演算演算部として構成されており、ハードウェアまたはソフトウェアによってべき乗剰余演算を行う。べき乗剰余演算装置１０１は、制御部１０２、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ、リードオンリーメモリ）１０３、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ、ランダムアクセスメモリ）１０４、事前計算テーブル１０５、剰余乗算ユニット１０６からなる。
【０００６】
ＲＯＭ１０３は、べき乗剰余演算を行う際に必要なパラメータを格納している。例えば、ｍ，Ｎ（後述）が固定値であるときには、ＲＯＭ１０３はｍ，Ｎを格納している。また、ソフトウェアで実現されるときには、Ｂｒｉｃｋｅｌｌらの方法でべき乗剰余演算を行うプログラムを格納している。
【０００７】
ＲＡＭ１０４は、べき乗剰余演算の途中結果などの一時的なデータを格納する。事前計算テーブル１０５は、ＴＢＬ［ｉ］＝ｍｗｉ ｍｏｄ ＮからなるＴＢＬ［ ］を格納している。事前計算テーブル１０５は、ＲＯＭ１０３に含まれていてもよい。
【０００８】
剰余乗算ユニット１０６は、ＲＯＭ１０３、ＲＡＭ１０４または事前計算テーブル１０５から制御部１０２の制御のもとに入力値ｘ，ｙを受け、剰余乗算ｚ＝ｘ×ｙ ｍｏｄ Ｎを行って結果ｚをＲＡＭ１０４に返す。
【０００９】
図６は、特許文献１に記載された耐タンパーべき乗剰余演算方法を実現するフローチャートである。
【００１０】
図６、図７では、今日のベき乗剰余算を利用した暗号方式の法は一般に１，０２４ビットが使われていることから、ｎを１，０２４ビット、ｗを８ビット、ｓをｓ＝ｎ／ｗ＝１２８とした場合を示しているが、もちろん一般化することも容易である。
【００１１】
図６を参照して、特許文献１に記載されたべき乗剰余演算装置１０１の動作について説明する。
【００１２】
まず、ｋは８ビットずつ１２８ブロックに分けられているものとし、それをＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）側からｋ１２７，ｋ１２６，・・・，ｋ１，ｋ０とする。これは、ステップ２０１よりも前またはステップ２０１で行われるステップである。また、ｎが１，０２４ビットの場合を考えているので、ＭＳＢを含むブロックに０をパディングする必要がないが、必要に応じてここでｋのＭＳＢ側に０をパディングしてブロックをｗビットにしておく。
【００１３】
ステップ２０１では、ｋ１２７，・・・，ｋ０を大きい順に並べ替え、それに対応する添え字を領域Ｆに格納する。ステップ２０１を詳細に記述したフローチャートが図７である。ここで、ステップ２０１に対応する図７について説明する。
【００１４】
ステップ３０１において、添え字を格納する領域Ｆを０に初期化する。ステップ３０２から３０９は、ｄを２５５（＝２ｗ−１）からｄ＝０まで１ずつ減じていくループ処理である。ステップ３０３から３０６は、ｉを１２７（＝ｓ−１）からｉ＝０まで１ずつ減じていくループ処理である。なお、ここはｉを０から１２７まで１ずつ増加させていってもよい。
【００１５】
ステップ３０４において、ｋｉ＝ｄであるかを検査する。成立するときは添え字を格納する領域Ｆに１バイトのデータとしてｉを連結する（ステップ３０５）。成立しないときは何もしない、すなわちステップ３０５を飛ばしてステップ３０６に進む。
【００１６】
ステップ３０６のｉループが終了したのちはステップ３０７に進み、ｉ＞０か検査する。成立するときは領域Ｆに、ｄの値が変化する印をつける。ここでは０ｘ８０（１０進数では１２８）という１バイトをその印としている（ステップ３０８）。成立しないときは何もしない、すなわちステップ３０８を飛ばしてステップ３０９に進む。ステップ３０９のｄループが終了したとき、このフローチャートは終了する。
【００１７】
そこで、図６のフローチャートに戻る。ステップ２０２、２０３で中間結果Ａ，Ｂをそれぞれ１と設定する。ステップ２０４から２０８はｉを０から３８２（＝（２ｗ−１）＋ｓ−１）まで１ずつ増加させていくループ処理である。
【００１８】
ステップ２０５においてＦのｉ番目の要素Ｆ［ｉ］が０ｘ８０であるか検査する。成立する場合はＢ×Ａ ｍｏｄ Ｎを実行してＡに格納し（ステップ２０６）、ステップ２０８に進む。成立しない場合はＢ×ＴＢＬ［Ｆ［ｉ］］ ｍｏｄ Ｎを実行してＢに格納する（ステップ２０７）。
【００１９】
ステップ２０８で終了したときに、Ａにｍｋ ｍｏｄ Ｎが格納されている。なぜならば、ここでは、Ｂｒｉｃｋｅｌｌらの方法において、ｋｉ＝ｄかの判定を処理の先頭で行っているのみで、剰余乗算の実行順序はＢｒｉｃｋｅｌｌらの方法と同じだからである。また、Ｂｒｉｃｋｅｌｌらの方法では、ｄのループはｄ＝０で行っていないが、ここでは（図７）、ｄ＝０の場合も行っている。しかし、ステップ３０７でｉ＝０の場合はＦに０ｘ８０を連結していないため、ｄ＝０に対応する図６での演算は、ステップ２０７が行われるのみで、ステップ２０６は行われない。したがって、ｄ＝０に対応する演算は、最終結果Ａに影響を与えないため、Ｂｒｉｃｋｅｌｌらの方法と同一の最終結果を得ることができる。
【００２０】
なお、特許文献２には、指数部を上位と下位に２分割して並列に処理する技術が記載されている。また、特許文献３には、べき乗剰余演算式ではないものの、乱数による分割処理手段が記載されている。
【先行技術文献】
【特許文献】
【００２１】
【特許文献１】特開２００８−２２４８３０号公報（第６、７頁、図２〜図４）
【特許文献２】特開２００３−１７７６６９号公報
【特許文献３】特開平０９−３１１６２７号公報
【発明の概要】
【発明が解決しようとする課題】
【００２２】
以下の分析は、本発明者によってなされたものである。
【００２３】
特許文献１に記載された耐タンパーべき乗剰余演算装置によると、攻撃手法の高度化に伴い、組込みシステムのように、あらかじめ格納された暗号鍵で処理が行われる場合、複数の異なる被べき乗数に対する処理の処理時間および消費電力波形を統計的に解析することにより、各ステップの処理内容、暗号鍵が解読されるおそれがある。すなわち、特許文献１に記載された耐タンパーべき乗剰余演算装置は、電力解析に基づくサイドチャネル攻撃への耐タンパー性が低い。
【００２４】
特許文献１に記載されたべき乗剰余演算では、全ての演算は、図６のフローチャートにおける、ステップ２０５からステップ２０６、または、ステップ２０５からステップ２０７の演算、すなわち、条件分岐の後のべき乗剰余演算の繰り返しとなる。
【００２５】
図６のフローチャートにおいて繰返されるステップ２０６、およびステップ２０７の演算の入力値として用いる中間結果Ａ、Ｂ、およびＴＢＬ［Ｆ［ｉ］］は、繰返し処理の度に異なる。したがって、各ステップにおける消費電力波形は、入力値に対応した波形となる。組込みシステムのように、あらかじめＲＯＭなどに格納された同一の暗号鍵を使用する場合には、特許文献１に記載されたべき乗剰余演算では、暗号鍵の０、１のパターンの依存した条件分岐、べき乗剰余演算が実行されることになる。このとき、複数の異なる被べき乗数に対する処理の処理時間および消費電力波形を統計的に解析することにより、各ステップの処理内容および暗号鍵を解析することができる。
【００２６】
すなわち、特許文献１に記載されたべき乗剰余演算方法は、暗号鍵、すなわち、べき乗指数ｋおよびべき乗剰余演算の法Ｎが同一の場合には、同一の処理フローで演算する方法である。したがって、同一の暗号鍵を用いた演算を複数回行うと、暗号鍵の０、１のパターンに依存する処理時間および消費電力波形を統計的に解析することで、暗号鍵を解析することができる。
【００２７】
そこで、べき乗剰余演算において、電力解析および処理時間解析に基づくサイドチャネル攻撃への耐性を向上させることが課題となる。本発明の目的は、かかる課題を解決するべき乗剰余演算装置、べき乗剰余演算方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００２８】
本発明の第１の視点に係るべき乗剰余演算装置は、
べき乗指数ｋとべき乗剰余演算の法Ｎを保持する暗号鍵保持部と、
べき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する乱数生成器と、
処理ビット幅ｐおよびべき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成するべき乗指数制御部と、
処理回数ｑ、演算用べき乗指数ｆ、およびべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する剰余演算部と、を備えている。
【００２９】
本発明の第２の視点に係るべき乗剰余演算方法は、
コンピュータが、記憶部に記録されたべき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する工程と、
処理ビット幅ｐおよびべき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成する工程と、
処理回数ｑ、演算用べき乗指数ｆ、および記憶部に記録されたべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する工程と、を含む。
【００３０】
本発明の第３の視点に係るプログラムは、
記憶部に記録されたべき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する処理と、
処理ビット幅ｐおよびべき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成する処理と、
処理回数ｑ、演算用べき乗指数ｆ、および記憶部に記録されたべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する処理と、をコンピュータに実行させる。
【発明の効果】
【００３１】
本発明に係るべき乗剰余演算装置、べき乗剰余演算方法およびプログラムによると、べき乗剰余演算において、電力解析および処理時間解析に基づくサイドチャネル攻撃への耐性を向上させることができる。
【図面の簡単な説明】
【００３２】
【図１】本発明の第１の実施形態に係るべき乗剰余演算装置の構成を示すブロック図である。
【図２】本発明の第２の実施形態に係るべき乗剰余演算装置の構成を示すブロック図である。
【図３】本発明の第２の実施形態に係るべき乗剰余演算装置の剰余演算部の構成を示すブロック図である。
【図４】本発明の第２の実施形態に係るべき乗剰余演算装置の動作を示すフローチャートである。
【図５】特許文献１に記載された耐タンパーべき乗剰余演算装置の構成を示すブロック図である。
【図６】特許文献１に記載された耐タンパーべき乗剰余演算方法を示すフローチャートである。
【図７】特許文献１に記載された耐タンパーべき乗剰余演算方法（図６のステップＳ２０１）の詳細を示すフローチャートである。
【発明を実施するための形態】
【００３３】
第１の展開形態によると、上記第１の視点に係るべき乗剰余演算装置が提供される。
【００３４】
第２の展開形態によると、べき乗指数制御部は、べき乗指数ｋを処理ビット幅ｐで割った商を処理回数ｑとし、べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出す、べき乗剰余演算装置が提供される。
【００３５】
第３の展開形態によると、乱数生成器は、べき乗剰余演算を行なう度に、処理ビット幅ｐを生成する、べき乗剰余演算装置が提供される。
【００３６】
第４の展開形態によると、べき乗剰余演算の途中結果を含む一時的なデータを格納する一時データ保持部をさらに備えている、べき乗剰余演算装置が提供される。
【００３７】
第５の展開形態によると、
剰余演算部は、処理ビット幅ｐの最大値をｒとして、２ｒ個のモンゴメリ演算器と、
２ｒ個のモンゴメリ演算器の演算結果から、べき乗指数制御部で生成する演算用べき乗指数ｆに対応する演算結果を選択する第１のセレクタと、
処理回数ｑを保持するレジスタと、
乗算器と、
剰余演算結果Ｕを出力する剰余演算器と、
剰余演算結果または固定値を選択する第２のセレクタと、を備えている、べき乗剰余演算装置が提供される。
【００３８】
第６の展開形態によると、２ｒ個のモンゴメリ演算器は、それぞれ、乱数生成器で生成する処理ビット幅ｐの最大値をｒとした場合、あらかじめ、０から（２ｒ−１）までの整数ｊに関して、ｍｊ ｍｏｄ Ｎを計算した結果を保持する、べき乗剰余演算装置が提供される。
【００３９】
第７の展開形態によると、第１のセレクタは、べき乗指数制御部で生成する演算用べき乗指数ｆに対し、モンゴメリ演算器の演算結果からｍｆ ｍｏｄ Ｎを選択し、当該選択結果を乗算器に出力する、べき乗剰余演算装置が提供される。
【００４０】
第８の展開形態によると、レジスタは、ｑ−１から０までの整数をループカウンタｈとして順次出力する、べき乗剰余演算装置が提供される。
【００４１】
第９の展開形態によると、乗算器は、乱数生成器から出力された処理ビット幅ｐ、およびべき乗指数制御部から出力された処理回数ｑを用いて、第１のセレクタの出力Ｘ（ｆ）の２乗を剰余演算器に出力し、剰余演算器の出力Ｕの２乗をｐ−１回計算して剰余演算器に出力し、第１のセレクタの出力Ｘ（ｆ）と剰余演算器の出力Ｕの積の２乗を剰余演算器に出力し、剰余演算器の出力Ｕの２乗をｐ−１回計算して剰余演算器に出力する処理をｑ−２回繰り返す、べき乗剰余演算装置が提供される。
【００４２】
第１０の展開形態によると、剰余演算器は、乗算器出力Ｔとべき乗剰余演算の法Ｎに対し、Ｔ ｍｏｄ Ｎを計算して乗算器に出力する、べき乗剰余演算装置が提供される。
【００４３】
第１１の展開形態によると、第２のセレクタは、ループカウンタｈの値により、剰余演算器出力Ｕまたは固定値いずれかを選択し、選択結果を外部に出力する、べき乗剰余演算装置が提供される。
【００４４】
第１２の展開形態によると、上記第２の視点に係るべき乗剰余演算方法が提供される。
【００４５】
第１３の展開形態によると、演算用べき乗指数生成工程において、べき乗指数ｋを処理ビット幅ｐで割った商を処理回数ｑとし、べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出す、べき乗剰余演算方法が提供される。
【００４６】
第１４の展開形態によると、上記第３の視点に係るプログラムが提供される。
【００４７】
第１５の展開形態によると、演算用べき乗指数生成処理において、べき乗指数ｋを処理ビット幅ｐで割った商を処理回数ｑとし、べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出す、プログラムが提供される。
【００４８】
特許文献１に記載されたべき乗演算方法では、同一の暗号鍵によるべき乗剰余演算を行う場合、暗号鍵の０、１のパターンに依存する同一の処理フローとなる。
【００４９】
一方、本発明においては、乱数生成器により、動的に生成した処理ビット幅ｐを用いて、べき乗指数ｋを処理するたびに、べき乗指数制御部で決定した処理回数ｑ回の演算に分割し、べき乗剰余演算をｑ回繰り返す。処理のたびに演算の分割数を可変とすることで、同一の暗号鍵、すなわち同一のべき乗指数ｋおよびべき乗剰余演算の法Ｎを用いた処理であっても、処理の都度、暗号鍵の０、１のパターンに依存しない処理フローとすることができる。
【００５０】
すなわち、本発明によると、同一の暗号鍵を用いたべき乗剰余演算であっても、処理のたびに異なる消費電力波形とすることができる。このとき、統計的手法を用いて、消費電力波形から暗号鍵の解析を行うことを困難とすることができる。したがって、本発明によると、電力解析に関する耐タンパー性が向上する。
【００５１】
また、本発明によると、処理の分割数を演算のたびに変更させるため、同一の暗号鍵を用いた演算を行っても、毎回異なる処理フロー、すなわち異なる処理時間とすることができ、統計的手法を用いて、処理時間から暗号鍵を解析することが困難となる。したがって、本発明によると、処理時間解析に関する耐タンパー性も向上する。
【００５２】
（実施形態１）
本発明の第１の実施形態に係るべき乗剰余演算装置について、図面を参照して説明する。
【００５３】
図１は、本実施形態に係るべき乗剰余演算装置１の構成を示すブロック図である。図１を参照すると、べき乗剰余演算装置１は、暗号鍵保持部１３、乱数生成器５、べき乗指数制御部６および剰余演算部４を備えている。
【００５４】
暗号鍵保持部１３は、べき乗指数ｋとべき乗剰余演算の法Ｎを保持する。暗号鍵保持部１３は、一例として、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）であってもよい。
【００５５】
乱数生成器５は、べき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する。乱数生成器５は、べき乗剰余演算を行う度に、処理ビット幅ｐを生成するようにしてもよい。
【００５６】
べき乗指数制御部６は、処理ビット幅ｐおよびべき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成する。べき乗指数制御部６は、べき乗指数ｋを処理ビット幅ｐで割った商を処理回数ｑとし、べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出し、処理回数ｑおよび演算用べき乗指数ｆを剰余演算部４に出力するようにしてもよい。
【００５７】
剰余演算部４は、処理回数ｑ、演算用べき乗指数ｆ、およびべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する。
【００５８】
べき乗剰余演算装置は、べき乗剰余演算の途中結果を含む一時的なデータを格納する一時データ保持部１４をさらに備えていてもよい。一時データ保持部１４は、一例として、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）であってもよい。
【００５９】
本実施形態では、乱数生成器５により、動的に生成した処理ビット幅ｐを用いて、べき乗指数ｋを処理するたびに、べき乗指数制御部６で決定した処理回数ｑ回の演算に分割し、べき乗剰余演算をｑ回繰り返す処理を行う。
【００６０】
処理のたびに演算の分割数を可変とすることで、同一の暗号鍵、すなわち同一のべき乗指数ｋおよびべき乗剰余演算の法Ｎを用いた処理であっても、処理の都度、暗号鍵の０、１のパターンに依存しない処理フローとすることができる。
【００６１】
すなわち、本発明によると、同一の暗号鍵を用いたべき乗剰余演算であっても、処理のたびに異なる消費電力波形とすることができる。このとき、統計的手法を用いて、消費電力波形から暗号鍵の解析を行うことを困難にすることができる。したがって、本実施形態によると、電力解析に関する耐タンパー性が向上する。
【００６２】
また、本実施形態によれば、処理の分割数を演算のたびに変更させるため、同一の暗号鍵を用いた演算を行っても、毎回異なる処理フロー、すなわち異なる処理時間とすることができ、統計的手法を用いて、処理時間から暗号鍵を解析することが困難となる。したがって、本実施形態によると、処理時間解析に関する耐タンパー性も向上する。
【００６３】
（実施形態２）
本発明の第２の実施形態に係るべき乗剰余演算装置について、図面を参照して説明する。
【００６４】
図２は、本実施形態に係るべき乗剰余演算装置１の構成を示すブロック図である。図２を参照すると、べき乗剰余演算装置１は、制御部１０２および演算部８を備えている。
【００６５】
演算部８は、ＲＯＭ１０３、ＲＡＭ１０４、乱数生成器５、べき乗指数制御部６および剰余演算部４を備えている。
【００６６】
制御部１０２は、演算部８の演算全体のコントロールを行う。
【００６７】
ＲＯＭ１０３は、べき乗剰余演算を行う際に必要なパラメータ格納している。ＲＯＭ１０３は、例えば、暗号鍵となるべき乗指数ｋ、べき乗剰余演算の法Ｎを固定値として格納している。ＲＯＭ１０３に格納されたべき乗指数ｋは、べき乗指数制御部６に出力される。
【００６８】
ＲＡＭ１０４と剰余演算部４は、一時データ７を相互に入出力する。
【００６９】
乱数生成器５で生成された処理ビット幅ｐは、べき乗指数制御部６および剰余演算部４に入力される。
【００７０】
剰余演算部４は、制御部１０２の制御のもとに、ＲＯＭ１０３からべき乗剰余演算の法Ｎを、べき乗指数制御部６から演算用べき乗指数ｆおよび処理回数ｑを、さらに、べき乗剰余演算装置１の外部から被べき乗数ｍ受け、べき乗剰余演算ｍｋ ｍｏｄ Ｎを行い、演算結果をべき乗剰余演算装置１の外部に出力する。なお、剰余演算部４による演算方法の詳細については後述する。
【００７１】
図３は、剰余演算部４の構成を示すブロック図である。図３を参照すると、剰余演算部４は、モンゴメリ演算器群２０、セレクタ１０、乗算器４０、剰余演算器２１、レジスタ３０およびセレクタ１１を備えている。
【００７２】
モンゴメリ演算器群２０は、Ｍ個のモンゴメリ演算器２０−（０），２０−（１），・・・，２０−（Ｍ−１）を含む。ここで、Ｍは、図２の乱数生成器５で生成される乱数、すなわち、処理ビット幅ｐの大きさに依存する。処理ビット幅ｐの最大値をｒとすると、Ｍ＝２ｒである。
【００７３】
モンゴメリ演算器群２０の各モンゴメリ演算器２０−（ｉ）（ｉ＝０〜Ｍ−１）は、被べき乗数ｍおよびべき乗剰余演算の法Ｎを受ける。モンゴメリ演算器２０−（０）はｍ０ ｍｏｄ Ｎを計算し、モンゴメリ演算器２０−（１）はｍ１ ｍｏｄ Ｎを計算し、・・・、モンゴメリ演算器２０−（Ｍ−１）はｍＭ−１ ｍｏｄ Ｎを計算する。ここで、モンゴメリ演算器２０−（０）で計算された値をＸ（０）とし、モンゴメリ演算器２０−（１）で計算された値をＸ（１）とし、・・・、モンゴメリ演算器２０−（Ｍ−１）で計算された値をＸ（Ｍ−１）とする。
【００７４】
セレクタ１０は、演算用べき乗指数ｆを受け、モンゴメリ演算器２０−（０），２０−（１），・・・，２０−（Ｍ−１）から出力された演算結果Ｘ（０），Ｘ（１），・・・、Ｘ（Ｍ−１）のうちのいずれかを選択するとともに、選択した演算結果Ｘ（ｆ）を乗算器４０に出力する。
【００７５】
レジスタ３０は、処理回数ｑを受ける。また、レジスタ３０は、ループカウンタ（ループカウント）ｈを乗算器４０およびセレクタ１１に出力する。レジスタ３０は、一例として、ｑ−１から０までの整数を順次ループカウンタｈとして出力するようにしてもよい。
【００７６】
乗算器４０は、処理ビット幅ｐ、剰余演算器２１の出力Ｕ、セレクタ１０の出力Ｘ（ｆ）、および、ループカウンタｈを受ける。乗算器４０は、演算中の一時的なデータを、一時データ７として、ＲＡＭ１０４との間でやりとりする。
【００７７】
剰余演算器２１は、乗算器４０の演算結果Ｔ、および、べき乗剰余演算の法Ｎを受け、剰余演算を行う。剰余演算器２１は、乗算器４０およびセレクタ１１に出力Ｕを出力する。また、剰余演算器２１は、演算中の一時的なデータを、一時データ７として、ＲＡＭ１０４との間でやりとりする。
【００７８】
ループカウンタｈ≠０の場合には、セレクタ１１は０を出力する。一方、ループカウンタｈ＝０の場合には、セレクタ１１は、最終結果としてｍｋ ｍｏｄ Ｎを出力する。なお、ループカウンタｈ≠０の場合における出力は固定値であればよく、０に限定されない。
【００７９】
本実施形態におけるモンゴメリ演算器は、以下の原理に基づく計算を行う。
【００８０】
整数Ｅ，Ｙとべき乗剰余演算の法Ｎが与えられたとき、モンゴメリ乗数Ｒ（＝２ｎ、ｎはべき乗剰余演算の法Ｎのビット数）を用いると、２つの整数Ｅ、Ｙは、整数ｅ，ｙを用いて、それぞれ式（１）および式（２）によって表すことができる。
【００８１】
【００８２】
【００８３】
このとき、整数Ｅ，Ｙの積の剰余演算は、式（３）で示される。
【００８４】
【００８５】
ここで、Ｅ、Ｙ、ｅ、ｙ、Ｒはいずれも整数であり、モンゴメリ乗数Ｒ≧２であることから、式（４）が成り立つ。
【００８６】
【００８７】
式（４）より、式（１）、（２）に示されたようなモンゴメリ乗数Ｒを用いた変換を行うことで、べき乗剰余演算を式（３）の右辺のように少ないビット数の演算に変換することができる。したがって、モンゴメリ乗数を使用した場合には、モンゴメリ乗数を使用しない場合と比較して、高速にべき乗剰余演算を実行することができる。
【００８８】
本実施形態では、べき乗剰余演算を高速化するために、一例として、モンゴメリ演算器を用いて剰余演算部４を構成した。なお、剰余演算部４は、モンゴメリ演算器を使用しないものであってもよい。
【００８９】
図４は、本実施形態に係るべき乗剰余演算装置１により、べき乗剰余演算ｍｋ ｍｏｄ Ｎを計算する方法を示すフローチャートである。ここで、ｍは被べき乗数、ｋはべき乗指数、Ｎは法である。また、Ｎを固定とすると、必然的にモンゴメリ乗数も一意に定まる。
【００９０】
まず、乱数生成器５（図２）は、乱数として処理ビット幅ｐを生成する（ステップＳ１）。処理ビット幅ｐは、２以上の任意の整数とする。
【００９１】
次に、モンゴメリ演算器群２０（図３）は、初期値として、０から（Ｍ−１）までの整数ｊに関して、ｍｊ ｍｏｄ Ｎを計算する（ステップＳ２）。本実施形態では、Ｍ個のモンゴメリ演算器２０−（０）〜２０−（Ｍ−１）を用いて並列処理を行う場合について説明するが、逐次処理を行うようにしてもよい。
【００９２】
モンゴメリ演算器２０−（０）はｍ０ ｍｏｄ Ｎを計算し、モンゴメリ演算器２０−（１）はｍ１ ｍｏｄ Ｎを計算し、・・・、モンゴメリ演算器２０−（Ｍ−１）はｍＭ−１ ｍｏｄ Ｎを計算する。モンゴメリ演算器２０−（０）で計算された値をＸ（０）とし、モンゴメリ演算器２０−（１）で計算された値をＸ（１）とし、・・・、モンゴメリ演算器２０−（Ｍ−１）で計算された値をＸ（Ｍ−１）とする。
【００９３】
べき乗指数ｋのビット数が処理ビット幅ｐで割り切れるように、べき乗指数制御部６（図２）は、べき乗指数ｋのＭＳＢ側に０をパディングする（ステップＳ３）。パディング後のべき乗指数をｋ１とする。
【００９４】
べき乗指数制御部６は、ステップＳ３で補正されたべき乗指数ｋ１のビット数を処理ビット幅ｐで割った商を処理回数ｑとする（ステップＳ４）。べき乗指数制御部６は、処理回数ｑを剰余演算部４に出力する。
【００９５】
ステップＳ５以降の演算は、次の原理に基づく。
【００９６】
べき乗指数ｋ１をｐビット単位でｑ個に分割して得られた各ビット列を、演算用べき乗指数ｆを用いて、ｆ（ｑ−１），ｆ（ｑ−２），・・・，ｆ（１），ｆ（０）とし、べき乗の演算を＾で表すと、ｍｋを式（５）によって表すことができる。
【００９７】
【００９８】
また、剰余演算においては以下の式が成り立つ。すなわち、整数Ｃ、Ｄ、Ｆ、べき乗剰余演算の法Ｎがあるとき、以下の式（６）、（７）が成立する。
【００９９】
【０１００】
【０１０１】
したがって、式（５）〜（７）より、ｍｋ ｍｏｄ Ｎの演算は、式（８）のように変更することができる。
【０１０２】
（８）
【０１０３】
べき乗指数制御部６は、べき乗指数ｋ１の上位からｐビットを、演算用べき乗指数ｆとして取り出し、剰余演算部４に出力する（ステップＳ５）。
【０１０４】
べき乗指数制御部６は、ステップＳ４で求めた処理回数ｑを剰余演算部４に出力する（ステップＳ６）。剰余演算部４は、初期値として、ｑ−１をレジスタ３０にセットする。
【０１０５】
セレクタ１０は、演算用べき乗指数ｆにより、モンゴメリ演算器群２０内のモンゴメリ演算器２０−（０），２０−（１），・・・，２０−（Ｍ−１）からのモンゴメリ演算器群出力Ｘ（ｆ）を選択し、乗算器４０に出力する（ステップＳ７）。このときのモンゴメリ演算器群出力Ｘ（ｆ）の値は、Ｘ（０）〜Ｘ（２ｐ−１）のいずれかとなる。
【０１０６】
乗算器４０は、モンゴメリ演算器群出力Ｘ（ｆ）を受けて、（Ｘ（ｆ））２を計算し、出力Ｔとして出力する。
【０１０７】
剰余演算器２１は、乗算器４０の出力Ｔ、および、べき乗剰余演算の法Ｎを受けて、初期値としてＴ ｍｏｄ Ｎを計算する（ステップＳ８ａ）。
【０１０８】
乗算器４０は、剰余演算器２１の出力Ｕを受けて、Ｕ２を計算し、計算結果を出力Ｔとして剰余演算器２１に出力する（ステップＳ８ｂ）。
【０１０９】
剰余演算器２１は、出力Ｔを受けて、Ｔ ｍｏｄ Ｎを計算する（ステップＳ８ｃ）。
【０１１０】
剰余演算器２１によるＴ ｍｏｄ Ｎの計算がｐ回繰り返されたか否かを判定する（ステップＳ８ｄ）。ｐ回繰り返されていない場合には（ステップＳ８ｄのＮｏ）、ステップＳ８ｂおよびＳ８ｃにおける処理を繰り返す。
【０１１１】
ステップＳ８ａ〜Ｓ８ｄの処理により、べき乗指数ｋ１の最初のｐビット分をべき乗指数とし、Ｎを法とする、被べき乗数ｍに対するべき乗剰余演算が完了する。
【０１１２】
べき乗指数制御部６は、べき乗指数ｋ１を、ｐビット分だけＭＳＢ側にシフトし、これを新たなべき乗指数ｋ１とする（ステップＳ９）。
【０１１３】
べき乗指数制御部６は、ステップＳ９で更新されたべき乗指数ｋ１のＭＳＢからｐビットを取り出し、演算用べき乗指数ｆとして剰余演算部４に出力する（ステップＳ１０）。
【０１１４】
次に、レジスタ３０に格納されたループカウンタｈを１だけ減ずる。ループカウンタｈは、最初（ｑ−１）であるが、以後１ずつ減算されていく。減算された新たなループカウンタｈに対して、演算器４０は、モンゴメリ演算器群２０のモンゴメリ演算器２０−（０），２０−（１），・・・，２０−（Ｍ−１）からセレクタ１１で選択した新たなＸ（ｆ）の値、すなわち、Ｘ（０）〜Ｘ（２ｐ−１）のいずれかと、ステップＳ８ｄ実行後の剰余演算器２１の出力Ｕとを受け、これらを乗じた結果として新たに得られた出力Ｔを剰余演算器２１に出力する。剰余演算器２１は、出力Ｔを受けて、べき乗剰余演算の法Ｎによる剰余演算を行う（ステップＳ１１）。
【０１１５】
ループカウンタｈの値により終了判定を行う（ステップＳ１２）。ループカウンタｈ≠０の場合、すなわち、べき乗指数ｋ１について分割した演算が完了していない場合には（ステップＳ１２のＮｏ）、ステップＳ８ａに戻り、ステップＳ８ａ〜Ｓ１１を繰返す。
【０１１６】
一方、ループカウンタｈ＝０の場合には（ステップＳ１２のＹｅｓ）、処理を終了する。このとき、セレクタ１１は、最終的な演算結果を出力する。
【０１１７】
以上の処理により、剰余演算部４の出力としてｍｋ ｍｏｄ Ｎが得られる。
【０１１８】
ステップＳ１で生成する分割数ｐを、乱数生成器５の出力値とすることにより、同一の暗号鍵およびメッセージを入力した演算であっても、毎回、分割数を変えることができ、演算内容および中間処置の値が異なるものになる。すなわち、毎回、消費電力波形を異なるものとすることができる。
【０１１９】
本実施形態では、モンゴメリ演算器群２０として、Ｍ個のモンゴメリ演算器２０−（０）〜２０−（Ｍ−１）を設ける構成について説明した。一方、モンゴメリ演算器群２０を設ける代わりに、モンゴメリ演算の結果を予めレジスタまたはメモリ領域に格納するようにした構成を採用することもできる。
【０１２０】
本実施形態にかかるべき乗剰余演算装置は、べき乗剰余演算において、まず、乱数生成器により、動的に処理ビット幅ｐ生成する。処理ビット幅ｐの最大値をｒとするとき、モンゴメリ演算器により、０から（２ｒ−１）までの整数ｊに関して、ｍｊ ｍｏｄ Ｎの演算結果を求めておき、べき乗指数ｋを処理するたびに、べき乗指数制御部により決定した処理回数ｑ回の演算に分割し、当該回数に分割された演算用べき乗指数ｆに応じた前記モンゴメリ演算器によるｍｆ ｍｏｄ Ｎの演算結果を選択し、選択した演算結果を基に乗算器および剰余演算器を用いてべき乗剰余演算を行わせる処理を、ｑ回繰り返す。
【０１２１】
処理のたびに演算の分割数を可変とすることで、同一の暗号鍵、すなわち同一のべき乗指数ｋおよびべき乗剰余演算の法Ｎを用いた処理であっても、毎回異なる処理フローとすることができ、結果として処理のたびに異なる消費電力波形とすることができる。
【０１２２】
本実施形態によると、電力解析に関する耐タンパー性が向上する。なぜなら、本実施形態によると、処理の分割数を演算のたびに変更させるため、同一の暗号鍵を用いた演算を行っても、毎回異なる処理フローとすることができ、統計的手法を用いて、消費電力波形から暗号鍵を解析することが困難となるからである。
【０１２３】
また、本実施形態によると、処理時間解析に関する耐タンパー性も向上する。なぜなら、本実施形態によると、処理の分割数を演算のたびに変更させるため、同一の暗号鍵を用いた演算を行っても、毎回異なる処理フロー、すなわち異なる処理時間とすることができ、統計的手法を用いて、処理時間から暗号鍵を解析することが困難となるからである。
【０１２４】
なお、上記の特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１２５】
１，１０１ べき乗剰余演算装置
４ 剰余演算部
５ 乱数生成器
６ べき乗指数制御部
７ 一時データ
８ 演算部
１０，１１ セレクタ
１３ 暗号鍵保持部
１４ 一時データ保持部
２０ モンゴメリ演算器群
２０−（０），２０−（１），・・・，２０−（Ｍ−１） モンゴメリ演算器
２１ 剰余演算器
３０ レジスタ
４０ 乗算器
１０２ 制御部
１０３ ＲＯＭ
１０４ ＲＡＭ
１０５ 事前計算テーブル
１０６ 剰余乗算ユニット
ｆ 演算用べき乗指数
ｈ ループカウンタ
ｋ べき乗指数
ｍ 被べき乗数
Ｎ べき乗剰余演算の法
ｐ 処理ビット幅
ｑ 処理回数
Ｔ 演算結果
Ｕ 剰余演算器２１の出力
Ｘ（ｆ） モンゴメリ演算器群出力
【技術分野】
【０００１】
本発明は、べき乗剰余演算装置、べき乗剰余演算方法およびプログラムに関し、特に、耐タンパー性を有するべき乗剰余演算装置、べき乗剰余演算方法およびプログラムに関する。
【背景技術】
【０００２】
電子決済に用いられるＩＣカード、決裁可能な端末機器などの普及に伴い、重要な情報の秘匿性を向上させるために、暗号技術の重要性が増大している。
【０００３】
一方、暗号化された情報に対する攻撃方法も高度化されている。特に、暗号処理を実行するプロセッサの処理時間または消費電力を測定し、統計的手法を用いて、暗号プロセッサ内部の秘密情報を解析するサイドチャネル攻撃が現実的な脅威となってきている。そこで、非正規な手段による機密データの読み取りを防ぐ能力（耐タンパー性）をさらに向上させる必要がある。
【０００４】
一例として、特許文献１に、耐タンパー性べき乗演算方法が記載されている。図５は、特許文献１に記載された耐タンパーべき乗剰余演算装置の構成を示すブロック図である。
【０００５】
べき乗剰余演算装置１０１は、ＩＣカードなどの計算機のべき乗剰余演算演算部として構成されており、ハードウェアまたはソフトウェアによってべき乗剰余演算を行う。べき乗剰余演算装置１０１は、制御部１０２、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ、リードオンリーメモリ）１０３、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ、ランダムアクセスメモリ）１０４、事前計算テーブル１０５、剰余乗算ユニット１０６からなる。
【０００６】
ＲＯＭ１０３は、べき乗剰余演算を行う際に必要なパラメータを格納している。例えば、ｍ，Ｎ（後述）が固定値であるときには、ＲＯＭ１０３はｍ，Ｎを格納している。また、ソフトウェアで実現されるときには、Ｂｒｉｃｋｅｌｌらの方法でべき乗剰余演算を行うプログラムを格納している。
【０００７】
ＲＡＭ１０４は、べき乗剰余演算の途中結果などの一時的なデータを格納する。事前計算テーブル１０５は、ＴＢＬ［ｉ］＝ｍｗｉ ｍｏｄ ＮからなるＴＢＬ［ ］を格納している。事前計算テーブル１０５は、ＲＯＭ１０３に含まれていてもよい。
【０００８】
剰余乗算ユニット１０６は、ＲＯＭ１０３、ＲＡＭ１０４または事前計算テーブル１０５から制御部１０２の制御のもとに入力値ｘ，ｙを受け、剰余乗算ｚ＝ｘ×ｙ ｍｏｄ Ｎを行って結果ｚをＲＡＭ１０４に返す。
【０００９】
図６は、特許文献１に記載された耐タンパーべき乗剰余演算方法を実現するフローチャートである。
【００１０】
図６、図７では、今日のベき乗剰余算を利用した暗号方式の法は一般に１，０２４ビットが使われていることから、ｎを１，０２４ビット、ｗを８ビット、ｓをｓ＝ｎ／ｗ＝１２８とした場合を示しているが、もちろん一般化することも容易である。
【００１１】
図６を参照して、特許文献１に記載されたべき乗剰余演算装置１０１の動作について説明する。
【００１２】
まず、ｋは８ビットずつ１２８ブロックに分けられているものとし、それをＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）側からｋ１２７，ｋ１２６，・・・，ｋ１，ｋ０とする。これは、ステップ２０１よりも前またはステップ２０１で行われるステップである。また、ｎが１，０２４ビットの場合を考えているので、ＭＳＢを含むブロックに０をパディングする必要がないが、必要に応じてここでｋのＭＳＢ側に０をパディングしてブロックをｗビットにしておく。
【００１３】
ステップ２０１では、ｋ１２７，・・・，ｋ０を大きい順に並べ替え、それに対応する添え字を領域Ｆに格納する。ステップ２０１を詳細に記述したフローチャートが図７である。ここで、ステップ２０１に対応する図７について説明する。
【００１４】
ステップ３０１において、添え字を格納する領域Ｆを０に初期化する。ステップ３０２から３０９は、ｄを２５５（＝２ｗ−１）からｄ＝０まで１ずつ減じていくループ処理である。ステップ３０３から３０６は、ｉを１２７（＝ｓ−１）からｉ＝０まで１ずつ減じていくループ処理である。なお、ここはｉを０から１２７まで１ずつ増加させていってもよい。
【００１５】
ステップ３０４において、ｋｉ＝ｄであるかを検査する。成立するときは添え字を格納する領域Ｆに１バイトのデータとしてｉを連結する（ステップ３０５）。成立しないときは何もしない、すなわちステップ３０５を飛ばしてステップ３０６に進む。
【００１６】
ステップ３０６のｉループが終了したのちはステップ３０７に進み、ｉ＞０か検査する。成立するときは領域Ｆに、ｄの値が変化する印をつける。ここでは０ｘ８０（１０進数では１２８）という１バイトをその印としている（ステップ３０８）。成立しないときは何もしない、すなわちステップ３０８を飛ばしてステップ３０９に進む。ステップ３０９のｄループが終了したとき、このフローチャートは終了する。
【００１７】
そこで、図６のフローチャートに戻る。ステップ２０２、２０３で中間結果Ａ，Ｂをそれぞれ１と設定する。ステップ２０４から２０８はｉを０から３８２（＝（２ｗ−１）＋ｓ−１）まで１ずつ増加させていくループ処理である。
【００１８】
ステップ２０５においてＦのｉ番目の要素Ｆ［ｉ］が０ｘ８０であるか検査する。成立する場合はＢ×Ａ ｍｏｄ Ｎを実行してＡに格納し（ステップ２０６）、ステップ２０８に進む。成立しない場合はＢ×ＴＢＬ［Ｆ［ｉ］］ ｍｏｄ Ｎを実行してＢに格納する（ステップ２０７）。
【００１９】
ステップ２０８で終了したときに、Ａにｍｋ ｍｏｄ Ｎが格納されている。なぜならば、ここでは、Ｂｒｉｃｋｅｌｌらの方法において、ｋｉ＝ｄかの判定を処理の先頭で行っているのみで、剰余乗算の実行順序はＢｒｉｃｋｅｌｌらの方法と同じだからである。また、Ｂｒｉｃｋｅｌｌらの方法では、ｄのループはｄ＝０で行っていないが、ここでは（図７）、ｄ＝０の場合も行っている。しかし、ステップ３０７でｉ＝０の場合はＦに０ｘ８０を連結していないため、ｄ＝０に対応する図６での演算は、ステップ２０７が行われるのみで、ステップ２０６は行われない。したがって、ｄ＝０に対応する演算は、最終結果Ａに影響を与えないため、Ｂｒｉｃｋｅｌｌらの方法と同一の最終結果を得ることができる。
【００２０】
なお、特許文献２には、指数部を上位と下位に２分割して並列に処理する技術が記載されている。また、特許文献３には、べき乗剰余演算式ではないものの、乱数による分割処理手段が記載されている。
【先行技術文献】
【特許文献】
【００２１】
【特許文献１】特開２００８−２２４８３０号公報（第６、７頁、図２〜図４）
【特許文献２】特開２００３−１７７６６９号公報
【特許文献３】特開平０９−３１１６２７号公報
【発明の概要】
【発明が解決しようとする課題】
【００２２】
以下の分析は、本発明者によってなされたものである。
【００２３】
特許文献１に記載された耐タンパーべき乗剰余演算装置によると、攻撃手法の高度化に伴い、組込みシステムのように、あらかじめ格納された暗号鍵で処理が行われる場合、複数の異なる被べき乗数に対する処理の処理時間および消費電力波形を統計的に解析することにより、各ステップの処理内容、暗号鍵が解読されるおそれがある。すなわち、特許文献１に記載された耐タンパーべき乗剰余演算装置は、電力解析に基づくサイドチャネル攻撃への耐タンパー性が低い。
【００２４】
特許文献１に記載されたべき乗剰余演算では、全ての演算は、図６のフローチャートにおける、ステップ２０５からステップ２０６、または、ステップ２０５からステップ２０７の演算、すなわち、条件分岐の後のべき乗剰余演算の繰り返しとなる。
【００２５】
図６のフローチャートにおいて繰返されるステップ２０６、およびステップ２０７の演算の入力値として用いる中間結果Ａ、Ｂ、およびＴＢＬ［Ｆ［ｉ］］は、繰返し処理の度に異なる。したがって、各ステップにおける消費電力波形は、入力値に対応した波形となる。組込みシステムのように、あらかじめＲＯＭなどに格納された同一の暗号鍵を使用する場合には、特許文献１に記載されたべき乗剰余演算では、暗号鍵の０、１のパターンの依存した条件分岐、べき乗剰余演算が実行されることになる。このとき、複数の異なる被べき乗数に対する処理の処理時間および消費電力波形を統計的に解析することにより、各ステップの処理内容および暗号鍵を解析することができる。
【００２６】
すなわち、特許文献１に記載されたべき乗剰余演算方法は、暗号鍵、すなわち、べき乗指数ｋおよびべき乗剰余演算の法Ｎが同一の場合には、同一の処理フローで演算する方法である。したがって、同一の暗号鍵を用いた演算を複数回行うと、暗号鍵の０、１のパターンに依存する処理時間および消費電力波形を統計的に解析することで、暗号鍵を解析することができる。
【００２７】
そこで、べき乗剰余演算において、電力解析および処理時間解析に基づくサイドチャネル攻撃への耐性を向上させることが課題となる。本発明の目的は、かかる課題を解決するべき乗剰余演算装置、べき乗剰余演算方法およびプログラムを提供することにある。
【課題を解決するための手段】
【００２８】
本発明の第１の視点に係るべき乗剰余演算装置は、
べき乗指数ｋとべき乗剰余演算の法Ｎを保持する暗号鍵保持部と、
べき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する乱数生成器と、
処理ビット幅ｐおよびべき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成するべき乗指数制御部と、
処理回数ｑ、演算用べき乗指数ｆ、およびべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する剰余演算部と、を備えている。
【００２９】
本発明の第２の視点に係るべき乗剰余演算方法は、
コンピュータが、記憶部に記録されたべき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する工程と、
処理ビット幅ｐおよびべき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成する工程と、
処理回数ｑ、演算用べき乗指数ｆ、および記憶部に記録されたべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する工程と、を含む。
【００３０】
本発明の第３の視点に係るプログラムは、
記憶部に記録されたべき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する処理と、
処理ビット幅ｐおよびべき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成する処理と、
処理回数ｑ、演算用べき乗指数ｆ、および記憶部に記録されたべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する処理と、をコンピュータに実行させる。
【発明の効果】
【００３１】
本発明に係るべき乗剰余演算装置、べき乗剰余演算方法およびプログラムによると、べき乗剰余演算において、電力解析および処理時間解析に基づくサイドチャネル攻撃への耐性を向上させることができる。
【図面の簡単な説明】
【００３２】
【図１】本発明の第１の実施形態に係るべき乗剰余演算装置の構成を示すブロック図である。
【図２】本発明の第２の実施形態に係るべき乗剰余演算装置の構成を示すブロック図である。
【図３】本発明の第２の実施形態に係るべき乗剰余演算装置の剰余演算部の構成を示すブロック図である。
【図４】本発明の第２の実施形態に係るべき乗剰余演算装置の動作を示すフローチャートである。
【図５】特許文献１に記載された耐タンパーべき乗剰余演算装置の構成を示すブロック図である。
【図６】特許文献１に記載された耐タンパーべき乗剰余演算方法を示すフローチャートである。
【図７】特許文献１に記載された耐タンパーべき乗剰余演算方法（図６のステップＳ２０１）の詳細を示すフローチャートである。
【発明を実施するための形態】
【００３３】
第１の展開形態によると、上記第１の視点に係るべき乗剰余演算装置が提供される。
【００３４】
第２の展開形態によると、べき乗指数制御部は、べき乗指数ｋを処理ビット幅ｐで割った商を処理回数ｑとし、べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出す、べき乗剰余演算装置が提供される。
【００３５】
第３の展開形態によると、乱数生成器は、べき乗剰余演算を行なう度に、処理ビット幅ｐを生成する、べき乗剰余演算装置が提供される。
【００３６】
第４の展開形態によると、べき乗剰余演算の途中結果を含む一時的なデータを格納する一時データ保持部をさらに備えている、べき乗剰余演算装置が提供される。
【００３７】
第５の展開形態によると、
剰余演算部は、処理ビット幅ｐの最大値をｒとして、２ｒ個のモンゴメリ演算器と、
２ｒ個のモンゴメリ演算器の演算結果から、べき乗指数制御部で生成する演算用べき乗指数ｆに対応する演算結果を選択する第１のセレクタと、
処理回数ｑを保持するレジスタと、
乗算器と、
剰余演算結果Ｕを出力する剰余演算器と、
剰余演算結果または固定値を選択する第２のセレクタと、を備えている、べき乗剰余演算装置が提供される。
【００３８】
第６の展開形態によると、２ｒ個のモンゴメリ演算器は、それぞれ、乱数生成器で生成する処理ビット幅ｐの最大値をｒとした場合、あらかじめ、０から（２ｒ−１）までの整数ｊに関して、ｍｊ ｍｏｄ Ｎを計算した結果を保持する、べき乗剰余演算装置が提供される。
【００３９】
第７の展開形態によると、第１のセレクタは、べき乗指数制御部で生成する演算用べき乗指数ｆに対し、モンゴメリ演算器の演算結果からｍｆ ｍｏｄ Ｎを選択し、当該選択結果を乗算器に出力する、べき乗剰余演算装置が提供される。
【００４０】
第８の展開形態によると、レジスタは、ｑ−１から０までの整数をループカウンタｈとして順次出力する、べき乗剰余演算装置が提供される。
【００４１】
第９の展開形態によると、乗算器は、乱数生成器から出力された処理ビット幅ｐ、およびべき乗指数制御部から出力された処理回数ｑを用いて、第１のセレクタの出力Ｘ（ｆ）の２乗を剰余演算器に出力し、剰余演算器の出力Ｕの２乗をｐ−１回計算して剰余演算器に出力し、第１のセレクタの出力Ｘ（ｆ）と剰余演算器の出力Ｕの積の２乗を剰余演算器に出力し、剰余演算器の出力Ｕの２乗をｐ−１回計算して剰余演算器に出力する処理をｑ−２回繰り返す、べき乗剰余演算装置が提供される。
【００４２】
第１０の展開形態によると、剰余演算器は、乗算器出力Ｔとべき乗剰余演算の法Ｎに対し、Ｔ ｍｏｄ Ｎを計算して乗算器に出力する、べき乗剰余演算装置が提供される。
【００４３】
第１１の展開形態によると、第２のセレクタは、ループカウンタｈの値により、剰余演算器出力Ｕまたは固定値いずれかを選択し、選択結果を外部に出力する、べき乗剰余演算装置が提供される。
【００４４】
第１２の展開形態によると、上記第２の視点に係るべき乗剰余演算方法が提供される。
【００４５】
第１３の展開形態によると、演算用べき乗指数生成工程において、べき乗指数ｋを処理ビット幅ｐで割った商を処理回数ｑとし、べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出す、べき乗剰余演算方法が提供される。
【００４６】
第１４の展開形態によると、上記第３の視点に係るプログラムが提供される。
【００４７】
第１５の展開形態によると、演算用べき乗指数生成処理において、べき乗指数ｋを処理ビット幅ｐで割った商を処理回数ｑとし、べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出す、プログラムが提供される。
【００４８】
特許文献１に記載されたべき乗演算方法では、同一の暗号鍵によるべき乗剰余演算を行う場合、暗号鍵の０、１のパターンに依存する同一の処理フローとなる。
【００４９】
一方、本発明においては、乱数生成器により、動的に生成した処理ビット幅ｐを用いて、べき乗指数ｋを処理するたびに、べき乗指数制御部で決定した処理回数ｑ回の演算に分割し、べき乗剰余演算をｑ回繰り返す。処理のたびに演算の分割数を可変とすることで、同一の暗号鍵、すなわち同一のべき乗指数ｋおよびべき乗剰余演算の法Ｎを用いた処理であっても、処理の都度、暗号鍵の０、１のパターンに依存しない処理フローとすることができる。
【００５０】
すなわち、本発明によると、同一の暗号鍵を用いたべき乗剰余演算であっても、処理のたびに異なる消費電力波形とすることができる。このとき、統計的手法を用いて、消費電力波形から暗号鍵の解析を行うことを困難とすることができる。したがって、本発明によると、電力解析に関する耐タンパー性が向上する。
【００５１】
また、本発明によると、処理の分割数を演算のたびに変更させるため、同一の暗号鍵を用いた演算を行っても、毎回異なる処理フロー、すなわち異なる処理時間とすることができ、統計的手法を用いて、処理時間から暗号鍵を解析することが困難となる。したがって、本発明によると、処理時間解析に関する耐タンパー性も向上する。
【００５２】
（実施形態１）
本発明の第１の実施形態に係るべき乗剰余演算装置について、図面を参照して説明する。
【００５３】
図１は、本実施形態に係るべき乗剰余演算装置１の構成を示すブロック図である。図１を参照すると、べき乗剰余演算装置１は、暗号鍵保持部１３、乱数生成器５、べき乗指数制御部６および剰余演算部４を備えている。
【００５４】
暗号鍵保持部１３は、べき乗指数ｋとべき乗剰余演算の法Ｎを保持する。暗号鍵保持部１３は、一例として、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）であってもよい。
【００５５】
乱数生成器５は、べき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する。乱数生成器５は、べき乗剰余演算を行う度に、処理ビット幅ｐを生成するようにしてもよい。
【００５６】
べき乗指数制御部６は、処理ビット幅ｐおよびべき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成する。べき乗指数制御部６は、べき乗指数ｋを処理ビット幅ｐで割った商を処理回数ｑとし、べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出し、処理回数ｑおよび演算用べき乗指数ｆを剰余演算部４に出力するようにしてもよい。
【００５７】
剰余演算部４は、処理回数ｑ、演算用べき乗指数ｆ、およびべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する。
【００５８】
べき乗剰余演算装置は、べき乗剰余演算の途中結果を含む一時的なデータを格納する一時データ保持部１４をさらに備えていてもよい。一時データ保持部１４は、一例として、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）であってもよい。
【００５９】
本実施形態では、乱数生成器５により、動的に生成した処理ビット幅ｐを用いて、べき乗指数ｋを処理するたびに、べき乗指数制御部６で決定した処理回数ｑ回の演算に分割し、べき乗剰余演算をｑ回繰り返す処理を行う。
【００６０】
処理のたびに演算の分割数を可変とすることで、同一の暗号鍵、すなわち同一のべき乗指数ｋおよびべき乗剰余演算の法Ｎを用いた処理であっても、処理の都度、暗号鍵の０、１のパターンに依存しない処理フローとすることができる。
【００６１】
すなわち、本発明によると、同一の暗号鍵を用いたべき乗剰余演算であっても、処理のたびに異なる消費電力波形とすることができる。このとき、統計的手法を用いて、消費電力波形から暗号鍵の解析を行うことを困難にすることができる。したがって、本実施形態によると、電力解析に関する耐タンパー性が向上する。
【００６２】
また、本実施形態によれば、処理の分割数を演算のたびに変更させるため、同一の暗号鍵を用いた演算を行っても、毎回異なる処理フロー、すなわち異なる処理時間とすることができ、統計的手法を用いて、処理時間から暗号鍵を解析することが困難となる。したがって、本実施形態によると、処理時間解析に関する耐タンパー性も向上する。
【００６３】
（実施形態２）
本発明の第２の実施形態に係るべき乗剰余演算装置について、図面を参照して説明する。
【００６４】
図２は、本実施形態に係るべき乗剰余演算装置１の構成を示すブロック図である。図２を参照すると、べき乗剰余演算装置１は、制御部１０２および演算部８を備えている。
【００６５】
演算部８は、ＲＯＭ１０３、ＲＡＭ１０４、乱数生成器５、べき乗指数制御部６および剰余演算部４を備えている。
【００６６】
制御部１０２は、演算部８の演算全体のコントロールを行う。
【００６７】
ＲＯＭ１０３は、べき乗剰余演算を行う際に必要なパラメータ格納している。ＲＯＭ１０３は、例えば、暗号鍵となるべき乗指数ｋ、べき乗剰余演算の法Ｎを固定値として格納している。ＲＯＭ１０３に格納されたべき乗指数ｋは、べき乗指数制御部６に出力される。
【００６８】
ＲＡＭ１０４と剰余演算部４は、一時データ７を相互に入出力する。
【００６９】
乱数生成器５で生成された処理ビット幅ｐは、べき乗指数制御部６および剰余演算部４に入力される。
【００７０】
剰余演算部４は、制御部１０２の制御のもとに、ＲＯＭ１０３からべき乗剰余演算の法Ｎを、べき乗指数制御部６から演算用べき乗指数ｆおよび処理回数ｑを、さらに、べき乗剰余演算装置１の外部から被べき乗数ｍ受け、べき乗剰余演算ｍｋ ｍｏｄ Ｎを行い、演算結果をべき乗剰余演算装置１の外部に出力する。なお、剰余演算部４による演算方法の詳細については後述する。
【００７１】
図３は、剰余演算部４の構成を示すブロック図である。図３を参照すると、剰余演算部４は、モンゴメリ演算器群２０、セレクタ１０、乗算器４０、剰余演算器２１、レジスタ３０およびセレクタ１１を備えている。
【００７２】
モンゴメリ演算器群２０は、Ｍ個のモンゴメリ演算器２０−（０），２０−（１），・・・，２０−（Ｍ−１）を含む。ここで、Ｍは、図２の乱数生成器５で生成される乱数、すなわち、処理ビット幅ｐの大きさに依存する。処理ビット幅ｐの最大値をｒとすると、Ｍ＝２ｒである。
【００７３】
モンゴメリ演算器群２０の各モンゴメリ演算器２０−（ｉ）（ｉ＝０〜Ｍ−１）は、被べき乗数ｍおよびべき乗剰余演算の法Ｎを受ける。モンゴメリ演算器２０−（０）はｍ０ ｍｏｄ Ｎを計算し、モンゴメリ演算器２０−（１）はｍ１ ｍｏｄ Ｎを計算し、・・・、モンゴメリ演算器２０−（Ｍ−１）はｍＭ−１ ｍｏｄ Ｎを計算する。ここで、モンゴメリ演算器２０−（０）で計算された値をＸ（０）とし、モンゴメリ演算器２０−（１）で計算された値をＸ（１）とし、・・・、モンゴメリ演算器２０−（Ｍ−１）で計算された値をＸ（Ｍ−１）とする。
【００７４】
セレクタ１０は、演算用べき乗指数ｆを受け、モンゴメリ演算器２０−（０），２０−（１），・・・，２０−（Ｍ−１）から出力された演算結果Ｘ（０），Ｘ（１），・・・、Ｘ（Ｍ−１）のうちのいずれかを選択するとともに、選択した演算結果Ｘ（ｆ）を乗算器４０に出力する。
【００７５】
レジスタ３０は、処理回数ｑを受ける。また、レジスタ３０は、ループカウンタ（ループカウント）ｈを乗算器４０およびセレクタ１１に出力する。レジスタ３０は、一例として、ｑ−１から０までの整数を順次ループカウンタｈとして出力するようにしてもよい。
【００７６】
乗算器４０は、処理ビット幅ｐ、剰余演算器２１の出力Ｕ、セレクタ１０の出力Ｘ（ｆ）、および、ループカウンタｈを受ける。乗算器４０は、演算中の一時的なデータを、一時データ７として、ＲＡＭ１０４との間でやりとりする。
【００７７】
剰余演算器２１は、乗算器４０の演算結果Ｔ、および、べき乗剰余演算の法Ｎを受け、剰余演算を行う。剰余演算器２１は、乗算器４０およびセレクタ１１に出力Ｕを出力する。また、剰余演算器２１は、演算中の一時的なデータを、一時データ７として、ＲＡＭ１０４との間でやりとりする。
【００７８】
ループカウンタｈ≠０の場合には、セレクタ１１は０を出力する。一方、ループカウンタｈ＝０の場合には、セレクタ１１は、最終結果としてｍｋ ｍｏｄ Ｎを出力する。なお、ループカウンタｈ≠０の場合における出力は固定値であればよく、０に限定されない。
【００７９】
本実施形態におけるモンゴメリ演算器は、以下の原理に基づく計算を行う。
【００８０】
整数Ｅ，Ｙとべき乗剰余演算の法Ｎが与えられたとき、モンゴメリ乗数Ｒ（＝２ｎ、ｎはべき乗剰余演算の法Ｎのビット数）を用いると、２つの整数Ｅ、Ｙは、整数ｅ，ｙを用いて、それぞれ式（１）および式（２）によって表すことができる。
【００８１】
【００８２】
【００８３】
このとき、整数Ｅ，Ｙの積の剰余演算は、式（３）で示される。
【００８４】
【００８５】
ここで、Ｅ、Ｙ、ｅ、ｙ、Ｒはいずれも整数であり、モンゴメリ乗数Ｒ≧２であることから、式（４）が成り立つ。
【００８６】
【００８７】
式（４）より、式（１）、（２）に示されたようなモンゴメリ乗数Ｒを用いた変換を行うことで、べき乗剰余演算を式（３）の右辺のように少ないビット数の演算に変換することができる。したがって、モンゴメリ乗数を使用した場合には、モンゴメリ乗数を使用しない場合と比較して、高速にべき乗剰余演算を実行することができる。
【００８８】
本実施形態では、べき乗剰余演算を高速化するために、一例として、モンゴメリ演算器を用いて剰余演算部４を構成した。なお、剰余演算部４は、モンゴメリ演算器を使用しないものであってもよい。
【００８９】
図４は、本実施形態に係るべき乗剰余演算装置１により、べき乗剰余演算ｍｋ ｍｏｄ Ｎを計算する方法を示すフローチャートである。ここで、ｍは被べき乗数、ｋはべき乗指数、Ｎは法である。また、Ｎを固定とすると、必然的にモンゴメリ乗数も一意に定まる。
【００９０】
まず、乱数生成器５（図２）は、乱数として処理ビット幅ｐを生成する（ステップＳ１）。処理ビット幅ｐは、２以上の任意の整数とする。
【００９１】
次に、モンゴメリ演算器群２０（図３）は、初期値として、０から（Ｍ−１）までの整数ｊに関して、ｍｊ ｍｏｄ Ｎを計算する（ステップＳ２）。本実施形態では、Ｍ個のモンゴメリ演算器２０−（０）〜２０−（Ｍ−１）を用いて並列処理を行う場合について説明するが、逐次処理を行うようにしてもよい。
【００９２】
モンゴメリ演算器２０−（０）はｍ０ ｍｏｄ Ｎを計算し、モンゴメリ演算器２０−（１）はｍ１ ｍｏｄ Ｎを計算し、・・・、モンゴメリ演算器２０−（Ｍ−１）はｍＭ−１ ｍｏｄ Ｎを計算する。モンゴメリ演算器２０−（０）で計算された値をＸ（０）とし、モンゴメリ演算器２０−（１）で計算された値をＸ（１）とし、・・・、モンゴメリ演算器２０−（Ｍ−１）で計算された値をＸ（Ｍ−１）とする。
【００９３】
べき乗指数ｋのビット数が処理ビット幅ｐで割り切れるように、べき乗指数制御部６（図２）は、べき乗指数ｋのＭＳＢ側に０をパディングする（ステップＳ３）。パディング後のべき乗指数をｋ１とする。
【００９４】
べき乗指数制御部６は、ステップＳ３で補正されたべき乗指数ｋ１のビット数を処理ビット幅ｐで割った商を処理回数ｑとする（ステップＳ４）。べき乗指数制御部６は、処理回数ｑを剰余演算部４に出力する。
【００９５】
ステップＳ５以降の演算は、次の原理に基づく。
【００９６】
べき乗指数ｋ１をｐビット単位でｑ個に分割して得られた各ビット列を、演算用べき乗指数ｆを用いて、ｆ（ｑ−１），ｆ（ｑ−２），・・・，ｆ（１），ｆ（０）とし、べき乗の演算を＾で表すと、ｍｋを式（５）によって表すことができる。
【００９７】
【００９８】
また、剰余演算においては以下の式が成り立つ。すなわち、整数Ｃ、Ｄ、Ｆ、べき乗剰余演算の法Ｎがあるとき、以下の式（６）、（７）が成立する。
【００９９】
【０１００】
【０１０１】
したがって、式（５）〜（７）より、ｍｋ ｍｏｄ Ｎの演算は、式（８）のように変更することができる。
【０１０２】
（８）
【０１０３】
べき乗指数制御部６は、べき乗指数ｋ１の上位からｐビットを、演算用べき乗指数ｆとして取り出し、剰余演算部４に出力する（ステップＳ５）。
【０１０４】
べき乗指数制御部６は、ステップＳ４で求めた処理回数ｑを剰余演算部４に出力する（ステップＳ６）。剰余演算部４は、初期値として、ｑ−１をレジスタ３０にセットする。
【０１０５】
セレクタ１０は、演算用べき乗指数ｆにより、モンゴメリ演算器群２０内のモンゴメリ演算器２０−（０），２０−（１），・・・，２０−（Ｍ−１）からのモンゴメリ演算器群出力Ｘ（ｆ）を選択し、乗算器４０に出力する（ステップＳ７）。このときのモンゴメリ演算器群出力Ｘ（ｆ）の値は、Ｘ（０）〜Ｘ（２ｐ−１）のいずれかとなる。
【０１０６】
乗算器４０は、モンゴメリ演算器群出力Ｘ（ｆ）を受けて、（Ｘ（ｆ））２を計算し、出力Ｔとして出力する。
【０１０７】
剰余演算器２１は、乗算器４０の出力Ｔ、および、べき乗剰余演算の法Ｎを受けて、初期値としてＴ ｍｏｄ Ｎを計算する（ステップＳ８ａ）。
【０１０８】
乗算器４０は、剰余演算器２１の出力Ｕを受けて、Ｕ２を計算し、計算結果を出力Ｔとして剰余演算器２１に出力する（ステップＳ８ｂ）。
【０１０９】
剰余演算器２１は、出力Ｔを受けて、Ｔ ｍｏｄ Ｎを計算する（ステップＳ８ｃ）。
【０１１０】
剰余演算器２１によるＴ ｍｏｄ Ｎの計算がｐ回繰り返されたか否かを判定する（ステップＳ８ｄ）。ｐ回繰り返されていない場合には（ステップＳ８ｄのＮｏ）、ステップＳ８ｂおよびＳ８ｃにおける処理を繰り返す。
【０１１１】
ステップＳ８ａ〜Ｓ８ｄの処理により、べき乗指数ｋ１の最初のｐビット分をべき乗指数とし、Ｎを法とする、被べき乗数ｍに対するべき乗剰余演算が完了する。
【０１１２】
べき乗指数制御部６は、べき乗指数ｋ１を、ｐビット分だけＭＳＢ側にシフトし、これを新たなべき乗指数ｋ１とする（ステップＳ９）。
【０１１３】
べき乗指数制御部６は、ステップＳ９で更新されたべき乗指数ｋ１のＭＳＢからｐビットを取り出し、演算用べき乗指数ｆとして剰余演算部４に出力する（ステップＳ１０）。
【０１１４】
次に、レジスタ３０に格納されたループカウンタｈを１だけ減ずる。ループカウンタｈは、最初（ｑ−１）であるが、以後１ずつ減算されていく。減算された新たなループカウンタｈに対して、演算器４０は、モンゴメリ演算器群２０のモンゴメリ演算器２０−（０），２０−（１），・・・，２０−（Ｍ−１）からセレクタ１１で選択した新たなＸ（ｆ）の値、すなわち、Ｘ（０）〜Ｘ（２ｐ−１）のいずれかと、ステップＳ８ｄ実行後の剰余演算器２１の出力Ｕとを受け、これらを乗じた結果として新たに得られた出力Ｔを剰余演算器２１に出力する。剰余演算器２１は、出力Ｔを受けて、べき乗剰余演算の法Ｎによる剰余演算を行う（ステップＳ１１）。
【０１１５】
ループカウンタｈの値により終了判定を行う（ステップＳ１２）。ループカウンタｈ≠０の場合、すなわち、べき乗指数ｋ１について分割した演算が完了していない場合には（ステップＳ１２のＮｏ）、ステップＳ８ａに戻り、ステップＳ８ａ〜Ｓ１１を繰返す。
【０１１６】
一方、ループカウンタｈ＝０の場合には（ステップＳ１２のＹｅｓ）、処理を終了する。このとき、セレクタ１１は、最終的な演算結果を出力する。
【０１１７】
以上の処理により、剰余演算部４の出力としてｍｋ ｍｏｄ Ｎが得られる。
【０１１８】
ステップＳ１で生成する分割数ｐを、乱数生成器５の出力値とすることにより、同一の暗号鍵およびメッセージを入力した演算であっても、毎回、分割数を変えることができ、演算内容および中間処置の値が異なるものになる。すなわち、毎回、消費電力波形を異なるものとすることができる。
【０１１９】
本実施形態では、モンゴメリ演算器群２０として、Ｍ個のモンゴメリ演算器２０−（０）〜２０−（Ｍ−１）を設ける構成について説明した。一方、モンゴメリ演算器群２０を設ける代わりに、モンゴメリ演算の結果を予めレジスタまたはメモリ領域に格納するようにした構成を採用することもできる。
【０１２０】
本実施形態にかかるべき乗剰余演算装置は、べき乗剰余演算において、まず、乱数生成器により、動的に処理ビット幅ｐ生成する。処理ビット幅ｐの最大値をｒとするとき、モンゴメリ演算器により、０から（２ｒ−１）までの整数ｊに関して、ｍｊ ｍｏｄ Ｎの演算結果を求めておき、べき乗指数ｋを処理するたびに、べき乗指数制御部により決定した処理回数ｑ回の演算に分割し、当該回数に分割された演算用べき乗指数ｆに応じた前記モンゴメリ演算器によるｍｆ ｍｏｄ Ｎの演算結果を選択し、選択した演算結果を基に乗算器および剰余演算器を用いてべき乗剰余演算を行わせる処理を、ｑ回繰り返す。
【０１２１】
処理のたびに演算の分割数を可変とすることで、同一の暗号鍵、すなわち同一のべき乗指数ｋおよびべき乗剰余演算の法Ｎを用いた処理であっても、毎回異なる処理フローとすることができ、結果として処理のたびに異なる消費電力波形とすることができる。
【０１２２】
本実施形態によると、電力解析に関する耐タンパー性が向上する。なぜなら、本実施形態によると、処理の分割数を演算のたびに変更させるため、同一の暗号鍵を用いた演算を行っても、毎回異なる処理フローとすることができ、統計的手法を用いて、消費電力波形から暗号鍵を解析することが困難となるからである。
【０１２３】
また、本実施形態によると、処理時間解析に関する耐タンパー性も向上する。なぜなら、本実施形態によると、処理の分割数を演算のたびに変更させるため、同一の暗号鍵を用いた演算を行っても、毎回異なる処理フロー、すなわち異なる処理時間とすることができ、統計的手法を用いて、処理時間から暗号鍵を解析することが困難となるからである。
【０１２４】
なお、上記の特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１２５】
１，１０１ べき乗剰余演算装置
４ 剰余演算部
５ 乱数生成器
６ べき乗指数制御部
７ 一時データ
８ 演算部
１０，１１ セレクタ
１３ 暗号鍵保持部
１４ 一時データ保持部
２０ モンゴメリ演算器群
２０−（０），２０−（１），・・・，２０−（Ｍ−１） モンゴメリ演算器
２１ 剰余演算器
３０ レジスタ
４０ 乗算器
１０２ 制御部
１０３ ＲＯＭ
１０４ ＲＡＭ
１０５ 事前計算テーブル
１０６ 剰余乗算ユニット
ｆ 演算用べき乗指数
ｈ ループカウンタ
ｋ べき乗指数
ｍ 被べき乗数
Ｎ べき乗剰余演算の法
ｐ 処理ビット幅
ｑ 処理回数
Ｔ 演算結果
Ｕ 剰余演算器２１の出力
Ｘ（ｆ） モンゴメリ演算器群出力
【特許請求の範囲】
【請求項１】
べき乗指数ｋとべき乗剰余演算の法Ｎを保持する暗号鍵保持部と、
前記べき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する乱数生成器と、
前記処理ビット幅ｐおよび前記べき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成するべき乗指数制御部と、
前記処理回数ｑ、前記演算用べき乗指数ｆ、および前記べき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する剰余演算部と、を備えていることを特徴とするべき乗剰余演算装置。
【請求項２】
前記べき乗指数制御部は、前記べき乗指数ｋを前記処理ビット幅ｐで割った商を処理回数ｑとし、前記べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出すことを特徴とする、請求項１に記載のべき乗剰余演算装置。
【請求項３】
前記乱数生成器は、べき乗剰余演算を行なう度に、前記処理ビット幅ｐを生成することを特徴とする、請求項１または２に記載のべき乗剰余演算装置。
【請求項４】
べき乗剰余算の途中結果を含む一時的なデータを格納する一時データ保持部をさらに備えていることを特徴とする、請求項１ないし３のいずれか１項に記載のべき乗剰余演算装置。
【請求項５】
前記剰余演算部は、処理ビット幅ｐの最大値をｒとして、２ｒ個のモンゴメリ演算器と、
前記２ｒ個のモンゴメリ演算器の演算結果から、前記べき乗指数制御部で生成する演算用べき乗指数ｆに対応する演算結果を選択する第１のセレクタと、
前記処理回数ｑを保持するレジスタと、
乗算器と、
剰余演算結果Ｕを出力する剰余演算器と、
剰余演算結果または固定値を選択する第２のセレクタと、を備えていることを特徴とする、請求項１ないし４のいずれか１項に記載のべき乗剰余演算装置。
【請求項６】
前記２ｒ個のモンゴメリ演算器は、それぞれ、前記乱数生成器で生成する処理ビット幅ｐの最大値をｒとした場合、あらかじめ、０から（２ｒ−１）までの整数ｊに関して、ｍｊ ｍｏｄ Ｎを計算した結果を保持することを特徴とする、請求項５に記載のべき乗剰余演算装置。
【請求項７】
前記第１のセレクタは、前記べき乗指数制御部で生成する演算用べき乗指数ｆに対し、前記モンゴメリ演算器の演算結果からｍｆ ｍｏｄ Ｎを選択し、当該選択結果を前記乗算器に出力することを特徴とする、請求項５または６に記載のべき乗剰余演算装置。
【請求項８】
前記レジスタは、ｑ−１から０までの整数をループカウンタｈとして順次出力することを特徴とする、請求項５ないし７のいずれか１項に記載のべき乗剰余演算装置。
【請求項９】
前記乗算器は、前記乱数生成器から出力された処理ビット幅ｐ、および前記べき乗指数制御部から出力された処理回数ｑを用いて、前記第１のセレクタの出力Ｘ（ｆ）の２乗を前記剰余演算器に出力し、前記剰余演算器の出力Ｕの２乗をｐ−１回計算して前記剰余演算器に出力し、前記第１のセレクタの出力Ｘ（ｆ）と前記剰余演算器の出力Ｕの積の２乗を前記剰余演算器に出力し、前記剰余演算器の出力Ｕの２乗をｐ−１回計算して前記剰余演算器に出力する処理をｑ−２回繰り返すことを特徴とする、請求項５ないし８のいずれか１項に記載のべき乗剰余演算装置。
【請求項１０】
前記剰余演算器は、前記乗算器出力Ｔとべき乗剰余演算の法Ｎに対し、Ｔ ｍｏｄ Ｎを計算して前記乗算器に出力することを特徴とする、請求項５ないし９のいずれか１項に記載のべき乗剰余演算装置。
【請求項１１】
前記第２のセレクタは、前記ループカウンタｈの値により、前記剰余演算器出力Ｕまたは固定値のいずれかを選択し、選択結果を外部に出力することを特徴とする、請求項５ないし１０のいずれか１項に記載のべき乗剰余演算装置。
【請求項１２】
コンピュータが、記憶部に記録されたべき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する工程と、
前記処理ビット幅ｐおよび前記べき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成する工程と、
前記処理回数ｑ、前記演算用べき乗指数ｆ、および前記記憶部に記録されたべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する工程と、を含むことを特徴とするべき乗剰余演算方法。
【請求項１３】
前記演算用べき乗指数生成工程において、前記べき乗指数ｋを前記処理ビット幅ｐで割った商を処理回数ｑとし、前記べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出すことを特徴とする、請求項１２に記載のべき乗剰余演算方法。
【請求項１４】
記憶部に記録されたべき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する処理と、
前記処理ビット幅ｐおよび前記べき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成する処理と、
前記処理回数ｑ、前記演算用べき乗指数ｆ、および前記記憶部に記録されたべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する処理と、をコンピュータに実行させることを特徴とするプログラム。
【請求項１５】
前記演算用べき乗指数生成処理において、前記べき乗指数ｋを前記処理ビット幅ｐで割った商を処理回数ｑとし、前記べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出すことを特徴とする、請求項１４に記載のプログラム。
【請求項１】
べき乗指数ｋとべき乗剰余演算の法Ｎを保持する暗号鍵保持部と、
前記べき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する乱数生成器と、
前記処理ビット幅ｐおよび前記べき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成するべき乗指数制御部と、
前記処理回数ｑ、前記演算用べき乗指数ｆ、および前記べき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する剰余演算部と、を備えていることを特徴とするべき乗剰余演算装置。
【請求項２】
前記べき乗指数制御部は、前記べき乗指数ｋを前記処理ビット幅ｐで割った商を処理回数ｑとし、前記べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出すことを特徴とする、請求項１に記載のべき乗剰余演算装置。
【請求項３】
前記乱数生成器は、べき乗剰余演算を行なう度に、前記処理ビット幅ｐを生成することを特徴とする、請求項１または２に記載のべき乗剰余演算装置。
【請求項４】
べき乗剰余算の途中結果を含む一時的なデータを格納する一時データ保持部をさらに備えていることを特徴とする、請求項１ないし３のいずれか１項に記載のべき乗剰余演算装置。
【請求項５】
前記剰余演算部は、処理ビット幅ｐの最大値をｒとして、２ｒ個のモンゴメリ演算器と、
前記２ｒ個のモンゴメリ演算器の演算結果から、前記べき乗指数制御部で生成する演算用べき乗指数ｆに対応する演算結果を選択する第１のセレクタと、
前記処理回数ｑを保持するレジスタと、
乗算器と、
剰余演算結果Ｕを出力する剰余演算器と、
剰余演算結果または固定値を選択する第２のセレクタと、を備えていることを特徴とする、請求項１ないし４のいずれか１項に記載のべき乗剰余演算装置。
【請求項６】
前記２ｒ個のモンゴメリ演算器は、それぞれ、前記乱数生成器で生成する処理ビット幅ｐの最大値をｒとした場合、あらかじめ、０から（２ｒ−１）までの整数ｊに関して、ｍｊ ｍｏｄ Ｎを計算した結果を保持することを特徴とする、請求項５に記載のべき乗剰余演算装置。
【請求項７】
前記第１のセレクタは、前記べき乗指数制御部で生成する演算用べき乗指数ｆに対し、前記モンゴメリ演算器の演算結果からｍｆ ｍｏｄ Ｎを選択し、当該選択結果を前記乗算器に出力することを特徴とする、請求項５または６に記載のべき乗剰余演算装置。
【請求項８】
前記レジスタは、ｑ−１から０までの整数をループカウンタｈとして順次出力することを特徴とする、請求項５ないし７のいずれか１項に記載のべき乗剰余演算装置。
【請求項９】
前記乗算器は、前記乱数生成器から出力された処理ビット幅ｐ、および前記べき乗指数制御部から出力された処理回数ｑを用いて、前記第１のセレクタの出力Ｘ（ｆ）の２乗を前記剰余演算器に出力し、前記剰余演算器の出力Ｕの２乗をｐ−１回計算して前記剰余演算器に出力し、前記第１のセレクタの出力Ｘ（ｆ）と前記剰余演算器の出力Ｕの積の２乗を前記剰余演算器に出力し、前記剰余演算器の出力Ｕの２乗をｐ−１回計算して前記剰余演算器に出力する処理をｑ−２回繰り返すことを特徴とする、請求項５ないし８のいずれか１項に記載のべき乗剰余演算装置。
【請求項１０】
前記剰余演算器は、前記乗算器出力Ｔとべき乗剰余演算の法Ｎに対し、Ｔ ｍｏｄ Ｎを計算して前記乗算器に出力することを特徴とする、請求項５ないし９のいずれか１項に記載のべき乗剰余演算装置。
【請求項１１】
前記第２のセレクタは、前記ループカウンタｈの値により、前記剰余演算器出力Ｕまたは固定値のいずれかを選択し、選択結果を外部に出力することを特徴とする、請求項５ないし１０のいずれか１項に記載のべき乗剰余演算装置。
【請求項１２】
コンピュータが、記憶部に記録されたべき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する工程と、
前記処理ビット幅ｐおよび前記べき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成する工程と、
前記処理回数ｑ、前記演算用べき乗指数ｆ、および前記記憶部に記録されたべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する工程と、を含むことを特徴とするべき乗剰余演算方法。
【請求項１３】
前記演算用べき乗指数生成工程において、前記べき乗指数ｋを前記処理ビット幅ｐで割った商を処理回数ｑとし、前記べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出すことを特徴とする、請求項１２に記載のべき乗剰余演算方法。
【請求項１４】
記憶部に記録されたべき乗指数ｋを分割する単位として、２以上の整数の乱数である処理ビット幅ｐを生成する処理と、
前記処理ビット幅ｐおよび前記べき乗指数ｋを用いて処理回数ｑを計算し、演算用べき乗指数ｆを生成する処理と、
前記処理回数ｑ、前記演算用べき乗指数ｆ、および前記記憶部に記録されたべき乗剰余演算の法Ｎを用いてｍｋ ｍｏｄ Ｎを算出する処理と、をコンピュータに実行させることを特徴とするプログラム。
【請求項１５】
前記演算用べき乗指数生成処理において、前記べき乗指数ｋを前記処理ビット幅ｐで割った商を処理回数ｑとし、前記べき乗指数ｋのＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からｐビット分を演算用べき乗指数ｆとして取り出すことを特徴とする、請求項１４に記載のプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１２−４７９４１（Ｐ２０１２−４７９４１Ａ）
【公開日】平成２４年３月８日（２０１２．３．８）
【国際特許分類】
【出願番号】特願２０１０−１８９４３８（Ｐ２０１０−１８９４３８）
【出願日】平成２２年８月２６日（２０１０．８．２６）
【出願人】（３０２０６２９３１）ルネサスエレクトロニクス株式会社 (8,021)
【Ｆターム（参考）】
【公開日】平成２４年３月８日（２０１２．３．８）
【国際特許分類】
【出願日】平成２２年８月２６日（２０１０．８．２６）
【出願人】（３０２０６２９３１）ルネサスエレクトロニクス株式会社 (8,021)
【Ｆターム（参考）】
[ Back to top ]