(57)【要約】【課題】従来のダミー乗算を付加して、秘密鍵ｄのべき値のビットによる乗算有無の違いをなくすことにより、単純電力解析攻撃を防ぐ方法では、ダミー乗算とそうでない乗算の乗数を解析する攻撃（ＢｉｇＭａｃ攻撃）を防げない。【解決手段】入出力部と、秘密鍵格納部と、カウンタ格納部と、カウンタ初期化部と、カウンタ更新部と、第１のカウンタ判定部と、第２のカウンタ判定部と、ビット判定部と、乗算部と、２乗算部と、中間値格納部と、乗数格納部と、乱数格納部と、乗数初期化部と、乗数更新部と、乱数性除去部と、乱数更新部とを備え、乗数をべき乗途中に更新することで、ダミー乗算とそうでない乗算の区別をしにくくする。これにより、ＢｉｇＭａｃ攻撃を防止できる。【選択図】図１
2007316491.tif 000002
【特許請求の範囲】
【請求項１】
対象データを入力し、秘密の数である秘密情報をべき値とした前記対象データのべき乗演算結果を出力するべき乗演算装置であって、
前記対象データの入力を受け付け、前記対象データのべき乗演算結果を出力する入出力部と、
前記秘密情報を格納する秘密情報格納部と、
中間値を格納する中間値格納部と、
前記秘密情報に対し、判定する秘密情報判定部と、
複数個の乗数を格納する乗数格納部と、
前記中間値と前記乗数との乗算を実行する乗算部と、
前記中間値の２乗算を実行する２乗算部と、
前記乗数を更新する乗数更新部とを備え、
前記乗算部で使用する前記乗数は、前記秘密情報判定部の判定結果に基づき、前記乗数格納部に格納されている複数個の前記乗数から選択すること
を特徴とするべき乗演算装置。
【請求項２】
前記べき乗演算装置は、さらに、
カウンタを格納するカウンタ格納部と、
カウンタの値を更新するカウンタ更新部と、
カウンタの値を判定するカウンタ判定部とを備え、
前記秘密情報判定部は、前記カウンタの値に基づき判定し、
前記乗数更新部は、前記カウンタ判定部の判定結果に基づき、前記乗数を更新すること
を特徴とする請求項１記載のべき乗演算装置。
【請求項３】
前記べき乗演算装置は、さらに、
乱数を格納する乱数格納部と、
前記中間値から前記乱数の影響を取り去る乱数性除去部とを備え、
前記乗数は、少なくとも前記乱数に基づくこと
を特徴する請求項１または請求項２記載のべき乗演算装置。
【請求項４】
前記乱数は、予め計算し、前記乱数格納部に格納しており、
前記乱数性除去部は、前記中間値に予め計算した乱数性除去数を乗算すること
を特徴とする請求項３記載のべき乗演算装置。
【請求項５】
前記べき乗演算装置は、さらに、
前記乱数を更新する乱数更新部を備えること
を特徴とする請求項４記載のべき乗演算装置。
【請求項６】
前記乗数格納部は、２個の前記乗数Ｘ＿０、Ｘ＿１を格納し、
前記乗数更新部は、前記乗数Ｘ＿０、Ｘ＿１に対し、前記乗数Ｘ＿０を２乗した結果を前記乗数Ｘ＿０に対する更新乗数Ｘ＿０’とし、前記対象データと前記更新乗数Ｘ＿０を掛けた結果を前記乗数Ｘ＿１に対する更新乗数Ｘ＿１’とし、それぞれの前記更新乗数Ｘ＿０’、Ｘ＿１’を前記乗数格納部に格納すること
を特徴とする請求項１から請求項５のいずれか１項に記載のべき乗演算装置。
【請求項７】
暗号文を入力し、秘密の数である秘密情報をべき値とした前記暗号文のべき乗演算結果を復号文として出力する復号化装置であって、
前記暗号文の入力を受け付け、前記復号文を出力する入出力部と、
前記秘密情報を格納する秘密情報格納部と、
中間値を格納する中間値格納部と、
前記秘密情報に対し、判定する秘密情報判定部と、
複数個の乗数を格納する乗数格納部と、
前記中間値と前記乗数との乗算を実行する乗算部と、
前記中間値の２乗算を実行する２乗算部と、
前記乗数を更新する乗数更新部とを備え、
前記乗算部で使用する前記乗数は、前記秘密情報判定部の判定結果に基づき、前記乗数格部に格納されている複数個の前記乗数から選択すること
を特徴とする復号化装置。
【請求項８】
署名対象データを入力し、秘密の数である秘密情報をべき値とした前記署名対象データのべき乗演算結果を署名データとして出力する署名生成装置であって、
前記署名対象データの入力を受け付け、前記署名データを出力する入出力部と、
前記秘密情報を格納する秘密情報格納部と、
中間値を格納する中間値格納部と、
前記秘密情報に対し、判定する秘密情報判定部と、
複数個の乗数を格納する乗数格納部と、
前記中間値と前記乗数との乗算を実行する乗算部と、
前記中間値の２乗算を実行する２乗算部と、
前記乗数を更新する乗数更新部とを備え、
前記乗算部で使用する前記乗数は、前記秘密情報判定部の判定結果に基づき、前記乗数格納部に格納されている複数個の前記乗数から選択すること
を特徴とする署名生成装置。
【請求項９】
対象データを入力し、秘密の数である秘密情報をべき値とした前記対象データのべき乗演算結果を出力するべき乗演算方法であって、
前記対象データの入力を受け付け、前記対象データのべき乗演算結果を出力する入出力ステップと、
前記秘密情報を格納する秘密情報格納ステップと、
中間値を格納する中間値格納ステップと、
前記の秘密情報に対し、判定する秘密情報判定ステップと、
複数個の乗数を格納する乗数格納ステップと、
前記中間値と前記乗数との乗算を実行する乗算ステップと、
前記中間値の２乗算を実行する２乗算ステップと、
前記乗数を更新する乗数更新ステップとを含み、
前記乗算部で使用する前記乗数は、前記秘密情報判定ステップの判定結果に基づき、前記乗数格納ステップに格納されている複数個の前記乗数から選択すること
を特徴とするべき乗演算方法。
【請求項１０】
対象データを入力し、秘密の数である秘密情報をべき値とした前記対象データのべき乗演算結果を出力するべき乗演算装置に実行させるプログラムであって、
前記対象データの入力を受け付け、前記対象データのべき乗演算結果を出力する入出力ステップと、
前記秘密情報を格納する秘密情報格納ステップと、
中間値を格納する中間値格納ステップと、
前記秘密情報に対し、判定する秘密情報判定ステップと、
複数個の乗数を格納する乗数格納ステップと、
前記中間値と前記乗数との乗算を実行する乗算ステップと、
前記中間値の２乗算を実行する２乗算ステップと、
前記乗数を更新する乗数更新ステップとを含み、
前記乗算部で使用する前記乗数は、前記秘密情報判定ステップの判定結果に基づき、前記乗数格納ステップに格納されている複数個の前記乗数から選択すること
を特徴とするプログラム。
【請求項１１】
請求項１０に記載のプログラムを記録した媒体。
【請求項１２】
対象データを入力し、秘密の数である秘密情報をべき値とした前記対象データのべき乗演算結果を出力するべき乗演算装置の集積回路であって、
前記対象データの入力を受け付け、前記対象データのべき乗演算結果を出力する入出力部と、
前記秘密情報を格納する秘密情報格納部と、
中間値を格納する中間値格納部と、
前記秘密情報に対し、判定する秘密情報判定部と、
複数個の乗数を格納する乗数格納部と、
前記中間値と前記乗数との乗算を実行する乗算部と、
前記中間値の２乗算を実行する２乗算部と、
前記乗数を更新する乗数更新部とを備え、
前記乗算部で使用する前記乗数は、前記秘密情報判定部の判定結果に基づき、前記乗数格納部に格納されている複数個の前記乗数から選択すること
を特徴とする集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理を実行する際の電力消費量を計測することで、暗号モジュールに埋め込まれている暗号鍵を解析する攻撃方法に対して安全な暗号装置に関する。
【背景技術】
【０００２】
近年、ハードウェアあるいはソフトウェアで実装された暗号モジュールが、暗号処理を行う際の副情報を手がかりにして、暗号鍵の解析を行う解読法が各種考案されている。例えば、タイミング攻撃と呼ばれる解析方法では、暗号モジュールが暗号処理に要する時間が、暗号処理に用いている暗号鍵の値により、わずかではあるが異なることを利用して、暗号鍵の解析を行う。即ち、タイミング攻撃においては、暗号処理を行う際の処理時間という副情報を利用して、暗号鍵の解読を行っている。そのような解読法の中でも、暗号処理を行う際の電力消費量を副情報として、解読を行う解読方法は、Ｓｉｍｐｌｅ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ（単純電力解析攻撃）、やＤｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ（差分電力解析攻撃）といった各種の方法が考案されている。これらの解読法は、近年、高性能な計測機器が安価で手に入るようになった背景もあって、ＩＣカードのような暗号が実装された実際の製品に対しても解析が可能であることが報告されている。以下の記述では、上記のような暗号処理時における暗号モジュールの電力消費量の変化、すなわち、電力波形を手がかりにして、暗号鍵を解析する解読方法を総称して、「電力解析攻撃」と呼ぶ。タイミング攻撃については、非特許文献１、電力解析攻撃については、非特許文献２が詳しい。
【０００３】
以下で、ＲＳＡ暗号への単純電力解析攻撃について説明する。ＲＳＡ暗号については、非特許文献３が詳しい。
【０００４】
〔ＲＳＡ暗号の単純電力解析攻撃〕
ＲＳＡ暗号の復号化処理において、素数ｐ、ｑの積ｎ、ｎ未満の正整数である暗号文ｃと、正整数である秘密鍵ｄに対し、ｃ＾ｄ  ｍｏｄ  ｎの計算を行う。この計算方法として例えば、非特許文献４の９ページにおけるバイナリ法が知られている。以下では、バイナリ法について説明する。ｄ＝ｄ０＋ｄ１×２＋ｄ２×２＾２＋．．．＋ｄ＾（ｌｅｎ−１）×２＾（ｌｅｎ−１）、ｉ＝０、１、．．．、ｌｅｎ−１に対しｄｉ＝０または１とする。ここで、ｌｅｎはｄのビット数、“×”は整数の乗算、ｘ＾ｙはｘのｙ乗を示している。
【０００５】
（バイナリ法）
ステップＳ８０１：ｉ←ｌｅｎ−２，  ｚ←ｃ
ステップＳ８０２：ｚ←ｚ＾２  ｍｏｄ  ｎ
ステップＳ８０３：ｄｉが１であるかチェック。ｄｉ＝１である場合は、ｚ←ｚ×ｃ  ｍｏｄ  ｎ。
【０００６】
ステップＳ８０４：ｉ←ｉ−１。ｉが負であるかチェック。負である場合は、ｚを出力。それ以外は、ステップＳ８０２へ。
【０００７】
上記方法では、ステップＳ８０２、Ｓ８０３、Ｓ８０４をループとして繰り返し計算している。このループ内で、ｄｉ（ｉ＝１，２，．．．，ｌｅｎ−１）に対して、ｄｉ＝１の場合は、ｚの２乗算とｃによる乗算を行い、ｄｉ＝０の場合は、ｚの２乗算のみを実行する。ｎは大きな数、例えば、１０２４ビットの整数である。通常は、２乗算は乗算より、計算の処理の効率化が図ることが可能なため、高速に処理可能になる。その場合、２乗算と乗算は処理が異なるため、電力波形が異なる。
【０００８】
したがって、電力波形を計測することにより、２乗算、乗算の演算の順序を解析することが可能になる。さらに、ｄｉによりループ内の処理が異なることを利用して、その順序からｄｉの値を求められる。まとめると、以下のステップにより、単純電力解析攻撃が可能になる。
【０００９】
（バイナリ法の単純電力解析攻撃）
ステップＳ９０１：暗号文ｃを復号化し、その処理における電力波形を計測。
【００１０】
ステップＳ９０２：上記電力波形より、２乗算、乗算の演算の順序を求める。
【００１１】
ステップＳ９０３：上記順序より、ビットｄｉ（ｉ＝１，２，．．．，ｌｅｎ−１）を求める。
【００１２】
〔従来のＲＳＡ暗号の単純電力解析攻撃対策〕
上記の単純電力解析攻撃では、バイナリ法のステップＳ８０３で、ｄｉ＝１のときのみ乗算を行うことを利用している。そこで、ｄｉ＝０のときに、１をｚに乗じる乗算をすることで、結果は変化しないが、ｄｉ＝０のときにも乗算を行うことで、２乗算、乗算の演算順序がｄの値に依存しなくなる、単純電力解析攻撃の対策方法も考案されている（非特許文献１参照）。
【非特許文献１】Ｐａｕｌ  Ｋｏｃｈｅｒ．  Ｔｉｍｉｎｇ  ａｔｔａｃｋｓ  ｏｎ  ｉｍｐｌｅｍｅｎｔａｔｉｏｎｓ  ｏｆ  Ｄｉｆｆｉｅ−Ｈｅｌｌｍａｎ，  ＲＳＡ，  ＤＳＳ，  ａｎｄ  ｏｔｈｅｒ  ｓｙｓｔｅｍｓ．  Ｉｎ  Ｎｅａｌ  Ｋｏｂｌｉｔｚ，  ｅｄｉｔｏｒ，  ＣＲＹＰＴＯ’９６，    ＬＮＣＳ  １１０９，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９６，  ｐｐ．１０４−１１３．
【非特許文献２】Ｐ．  Ｋｏｃｈｅｒ，  Ｊ．  Ｊａ＿ｅ，  ａｎｄ  Ｂ．  Ｊｕｎ，  “Ｄｉ＿ｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ，”  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −ＣＲＹＰＴＯ  ’９９，  ＬＮＣＳ，  １６６６  ，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  １９９９，  ｐｐ．３８８−３９７．
【非特許文献３】岡本龍明、山本博資、「現代暗号」、産業図書（１９９７年）
【非特許文献４】Ｈ．Ｃｏｈｅｎ，”Ａ  Ｃｏｕｒｓｅ  ｉｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ａｌｇｅｂｒａｉｃ  Ｎｕｍｂｅｒ  Ｔｈｅｏｒｙ”，ＧＴＭ  １３８，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，１９９６，ｐ９
【非特許文献５】Ｃ．Ｄ．Ｗａｌｔｅｒ，”Ｓｌｉｄｉｎｇ  ｗｉｎｄｏｗｓ  ｓｕｃｃｕｍｂｓ  ｔｏ  Ｂｉｇ  Ｍａｃ  Ａｔｔａｃｋ”，  ＣＨＥＳ２００１，  ＬＮＣＳ２１６２，  Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，  ２００１，  ｐｐ．２８６−２９９．
【非特許文献６】神永，  渡邊，  遠藤，  大河内，  “ＲＳＡ暗号の電力解析法による攻撃とその対策”，  ＩＥＩＣＥ，  Ｖｏｌ．  Ｊ８８−Ａ，  Ｎｏ．５，  ｐｐ．６０６−６１５，  ２００５
【発明の開示】
【発明が解決しようとする課題】
【００１３】
上述したＲＳＡ暗号の単純電力解析攻撃対策では、ｄｉ＝１のときにｃ、ｄｉ＝０のときに１を乗じる乗算を行い、乗数が異なる。このことを利用してｄｉが０であるか１であるかを解析する攻撃（ＢｉｇＭａｃ攻撃と呼ばれる）が考案されている（非特許文献５参照）。この攻撃を使用すると、上述した単純電力解析攻撃対策をしても、ｄの値が解析されてしまうという課題がある。
【００１４】
本発明は、ＢｉｇＭａｃ攻撃により安全性を低下しないようＲＳＡ暗号の復号化を行う復号装置を提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記目的を達成するために、請求項１における発明は、対象データを入力し、秘密の数である秘密情報をべき値とした前記対象データのべき乗演算結果を出力するべき乗演算装置であって、前記対象データの入力を受け付け、前記対象データのべき乗演算結果を出力する入出力部と、前記秘密情報を格納する秘密情報格納部と、中間値を格納する中間値格納部と、前記秘密情報に対し、判定する秘密情報判定部と、複数個の乗数を格納する乗数格納部と、前記中間値と前記乗数との乗算を実行する乗算部と、前記中間値の２乗算を実行する２乗算部と、前記乗数を更新する乗数更新部とを備え、前記乗算部で使用する前記乗数は、前記秘密情報判定部の判定結果に基づき、前記乗数格納部に格納されている複数個の前記乗数から選択することを特徴とする。
【００１６】
請求項２における発明は、前記べき乗演算装置は、さらに、カウンタを格納するカウンタ格納部と、カウンタの値を更新するカウンタ更新部と、カウンタの値を判定するカウンタ判定部とを備え、前記秘密情報判定部は、前記カウンタの値に基づき判定し、前記乗数更新部は、前記カウンタ判定部の判定結果に基づき、前記乗数を更新することを特徴とする。
【００１７】
請求項３における発明は、前記べき乗演算装置は、さらに、乱数を格納する乱数格納部と、前記中間値から前記乱数の影響を取り去る乱数性除去部とを備え、前記乗数は、少なくとも前記乱数に基づくことを特徴する。
【００１８】
請求項４における発明は、前記乱数は、予め計算し、前記乱数格納部に格納しており、前記乱数性除去部は、前記中間値に予め計算した乱数性除去数を乗算することを特徴とする。
【００１９】
請求項５における発明は、前記べき乗演算装置は、さらに、前記乱数を更新する乱数更新部を備えることを特徴とする。
【００２０】
請求項６における発明は、前記乗数格納部は、２個の前記乗数Ｘ＿０、Ｘ＿１を格納し、前記乗数更新部は、前記乗数Ｘ＿０、Ｘ＿１に対し、前記乗数Ｘ＿０を２乗した結果を前記乗数Ｘ＿０に対する更新乗数Ｘ＿０’とし、前記対象データと前記更新乗数Ｘ＿０を掛けた結果を前記乗数Ｘ＿１に対する更新乗数Ｘ＿１’とし、それぞれの前記更新乗数Ｘ＿０’、Ｘ＿１’を前記乗数格納部に格納することを特徴とする。
【００２１】
請求項７における発明は、暗号文を入力し、秘密の数である秘密情報をべき値とした前記暗号文のべき乗演算結果を復号文として出力する復号化装置であって、前記暗号文の入力を受け付け、前記復号文を出力する入出力部と、前記秘密情報を格納する秘密情報格納部と、中間値を格納する中間値格納部と、前記秘密情報に対し、判定する秘密情報判定部と、複数個の乗数を格納する乗数格納部と、前記中間値と前記乗数との乗算を実行する乗算部と、前記中間値の２乗算を実行する２乗算部と、前記乗数を更新する乗数更新部とを備え、前記乗算部で使用する前記乗数は、前記秘密情報判定部の判定結果に基づき、前記乗数格納部に格納されている複数個の前記乗数から選択することを特徴とする。
【００２２】
請求項８における発明は、署名対象データを入力し、秘密の数である秘密情報をべき値とした前記署名対象データのべき乗演算結果を署名データとして出力する署名生成装置であって、前記署名対象データの入力を受け付け、前記署名データを出力する入出力部と、前記秘密情報を格納する秘密情報格納部と、中間値を格納する中間値格納部と、前記秘密情報に対し、判定する秘密情報判定部と、複数個の乗数を格納する乗数格納部と、前記中間値と前記乗数との乗算を実行する乗算部と、前記中間値の２乗算を実行する２乗算部と、前記乗数を更新する乗数更新部とを備え、前記乗算部で使用する前記乗数は、前記秘密情報判定部の判定結果に基づき、前記乗数格納部に格納されている複数個の前記乗数から選択することを特徴とする。
【００２３】
請求項９における発明は、対象データを入力し、秘密の数である秘密情報をべき値とした前記対象データのべき乗演算結果を出力するべき乗演算方法であって、前記対象データの入力を受け付け、前記対象データのべき乗演算結果を出力する入出力ステップと、前記秘密情報を格納する秘密情報格納ステップと、中間値を格納する中間値格納ステップと、前記秘密情報に対し、判定する秘密情報判定ステップと、複数個の乗数を格納する乗数格納ステップと、前記中間値と前記乗数との乗算を実行する乗算ステップと、前記中間値の２乗算を実行する２乗算ステップと、前記乗数を更新する乗数更新ステップとを含み、前記乗算部で使用する前記乗数は、前記秘密情報判定ステップの判定結果に基づき、前記乗数格納ステップに格納されている複数個の前記乗数から選択することを特徴とする。
【００２４】
請求項１０における発明は、対象データを入力し、秘密の数である秘密情報をべき値とした前記対象データのべき乗演算結果を出力するべき乗演算装置に実行させるプログラムであって、前記対象データの入力を受け付け、前記対象データのべき乗演算結果を出力する入出力ステップと、前記秘密情報を格納する秘密情報格納ステップと、中間値を格納する中間値格納ステップと、前記秘密情報に対し、判定する秘密情報判定ステップと、複数個の乗数を格納する乗数格納ステップと、前記中間値と前記乗数との乗算を実行する乗算ステップと、前記中間値の２乗算を実行する２乗算ステップと、前記乗数を更新する乗数更新ステップとを含み、前記乗算部で使用する前記乗数は、前記秘密情報判定ステップの判定結果に基づき、前記乗数格納ステップに格納されている複数個の前記乗数から選択することを特徴とする。
【００２５】
請求項１１における発明は、請求項１０に記載のプログラムを記録した媒体である。
【００２６】
請求項１２における発明は、対象データを入力し、秘密の数である秘密情報をべき値とした前記対象データのべき乗演算結果を出力するべき乗演算装置の集積回路であって、前記対象データの入力を受け付け、前記対象データのべき乗演算結果を出力する入出力部と、前記秘密情報を格納する秘密情報格納部と、中間値を格納する中間値格納部と、前記秘密情報に対し、判定する秘密情報判定部と、複数個の乗数を格納する乗数格納部と、前記中間値と前記乗数との乗算を実行する乗算部と、前記中間値の２乗算を実行する２乗算部と、前記乗数を更新する乗数更新部とを備え、前記乗算部で使用する前記乗数は、前記秘密情報判定部の判定結果に基づき、前記乗数格納部に格納されている複数個の前記乗数から選択することを特徴とする。
【発明の効果】
【００２７】
これらの構成によると、ＢｉｇＭａｃ攻撃により安全性を低下することを防ぐことができ、その価値は大きい。
【発明を実施するための最良の形態】
【００２８】
（実施の形態１）
図１は、本発明にかかる実施の形態１としてのべき乗演算装置１０００の構成を示す図である。本装置は、べき乗を行う対象データである対象データＸを入力し、対象データのべき乗結果を出力する入出力部１０１０と、秘密鍵ｄを格納する秘密鍵格納部１０２０と、カウンタｃｏｕｎｔを格納するカウンタ格納部１０３０と、カウンタｃｏｕｎｔを初期化するカウンタ初期化部１０４０と、カウンタｃｏｕｎｔの値を更新するカウンタ更新部１０５０と、カウンタｃｏｕｎｔの値を判定する第１のカウンタ判定部１０６０と、第１のカウンタ判定部１０６０と異なるカウンタｃｏｕｎｔの値の判定を行う第２のカウンタ判定部１０７０と、ｄのビット値を判定するビット判定部１０８０と、乗算を実行する乗算部１０９０と、２乗算を実行する２乗算部１１００と、乗算部１０９０や２乗算部１１００の結果を格納する中間値格納部１１１０と、乗算部１０９０で使用する乗数を格納した乗数格納部１１２０と、後述する乱数と乱数性除去数を格納する乱数格納部１１３０と、乗数格納部１１２０に格納している乗数を初期化する乗数初期化部１１４０と、乗数格納部１１２０に格納している乗数を更新する乗数更新部１１５０と、乱数格納部１１３０に格納されている乱数性除去数を用いて乱数の影響を取り去る乱数性除去部１１６０と、乱数と乱数性除去数を更新する乱数更新部１１７０とを備える。本べき乗演算装置１０００は、対象データとして入力し、対象データの秘密鍵ｄをべき値としたべき乗演算結果を出力する。
【００２９】
＜べき乗演算装置１０００の使用する場面について＞
本装置は、例えば、ＲＳＡ暗号方式の復号化やＲＳＡ署名方式の署名作成において、使用する。以下で、ＲＳＡ暗号方式及びＲＳＡ署名方式について説明する。
【００３０】
●ＲＳＡ暗号方式
（１）鍵の生成
次に示すようにして公開鍵及び秘密鍵を計算する。
【００３１】
・ランダムに大きい素数ｐ，ｑを選択し、その積ｎ＝ｐ×ｑを計算する。
【００３２】
・（ｐ−１）及び（ｑ−１）の最小公倍数Ｌ＝ＬＣＭ（ｐ−１，ｑ−１）を計算する。
【００３３】
・Ｌと互いに素でＬより小さい自然数ｅをランダムに選ぶ。
【００３４】
１≦ｅ≦Ｌ−１、ＧＣＤ（ｅ，Ｌ）＝１
ここで、ＧＣＤ（ｅ，Ｌ）は、ｅとＬの最大公約数を示している。
【００３５】
・ｅ×ｄ＝１    ｍｏｄ    Ｌを満たすｄを計算する。ＧＣＤ（ｅ，Ｌ）＝１より、このようなｄは必ず存在する。このようにして、得られた整数ｅ及び整数ｎが、公開鍵である。また、整数ｄが、秘密鍵である。ここで、ｘ  ｍｏｄ  ｙは、ｘをｙで割った余りを示す。
【００３６】
（２）暗号文の生成
公開鍵である整数ｅ及び整数ｎを用いて、平文ｍに暗号演算を施して暗号文ｃを計算する。
【００３７】
ｃ＝ｍ＾ｅ      ｍｏｄ    ｎ
なお、この明細書において、演算子＾は、べき乗を示す。例えば、Ａ＾ｘは、ｘ＞０のときはＡをｘ回乗じたものを示す。
【００３８】
（３）復号文の生成
秘密鍵である整数ｄを用いて、暗号文ｃに復号演算を施して復号文ｍ’を計算する。
【００３９】
ｍ’＝ｃ＾ｄ    ｍｏｄ  ｎ
なお、
ｍ’＝ｃ＾ｄ    ｍｏｄ  ｎ
＝（ｍ＾ｅ  ）＾ｄ    ｍｏｄ  ｎ
＝ｍ＾（ｅ×ｄ    ｍｏｄ  Ｌ）    ｍｏｄ  ｎ
＝ｍ＾１    ｍｏｄ  ｎ
＝ｍ    ｍｏｄ  ｎ
であるので、復号文ｍ’は、平文ｍと一致する。
【００４０】
べき乗演算装置１０００は、この復号文の生成における上記のｃからｍ’を計算する箇所で使用する。このとき、べき乗演算装置１０００において対象データをｃとして、秘密鍵ｄを使用して、ｍ’＝ｃ＾ｄ    ｍｏｄ  ｎを計算する。
【００４１】
なお、ＲＳＡ暗号については、非特許文献３の１１０〜１１３ページに詳しく説明されている。
【００４２】
●ＲＳＡ署名方式
（１）鍵の生成
鍵の生成方法については、ＲＳＡ暗号方式と同様である。
【００４３】
（２）署名生成
メッセージデータＤに対して、以下のように署名データＳを計算する。
【００４４】
まず、ハッシュ関数Ｈａｓｈを用いて、メッセージデータＤのハッシュ値ｈ＝Ｈａｓｈ（Ｄ）を計算する。
【００４５】
次に、秘密鍵である整数ｄを用いて、ハッシュ値ｈをｄ乗して、署名データＳを計算する。
【００４６】
Ｓ＝ｈ＾ｄ  ｍｏｄ  ｎ
（３）署名検証
署名データＳがメッセージデータＤの正しい署名であるかを、以下のように検証する。
【００４７】
Ｈａｓｈ（Ｄ）とＳ＾ｅ  ｍｏｄ  ｎが等しいか否かを確認する。等しい場合は、署名データＳが正しい署名であるとして、受理する。等しくない場合は、署名データＳが正しくない署名であるとして、拒否する。
【００４８】
べき乗演算装置１０００は、上記の署名生成におけるｈからＳを計算する箇所で使用する。このとき、べき乗演算装置１０００において対象データをｈとして、秘密鍵ｄを使用して、Ｓ＝ｈ＾ｄ    ｍｏｄ  ｎを計算する。
【００４９】
なお、ＲＳＡ署名については、非特許文献３の１７５〜１７６ページに詳しく説明されている。
【００５０】
＜べき乗演算装置１０００の各部について＞
入出力部１０１０は、対象データＸの入力を受付、対象データを中間値Ｚとして、中間値格納部１１１０へ格納する。入出力部１０１０はさらに、対象データＸのべき乗演算結果を出力する。
【００５１】
秘密鍵格納部１０２０は、秘密鍵であるｄを格納する。ｄは例えば、５１２ビットの整数である。
【００５２】
カウンタ格納部１０３０は、カウンタｃｏｕｎｔを格納する。
【００５３】
カウンタ初期化部１０４０は、カウンタｃｏｕｎｔをｌｅｎｄ−１に設定する。ここで、ｌｅｎｄは秘密鍵ｄのビットサイズである。例えば、ｌｅｎｄ＝５１２である。
【００５４】
カウンタ更新部１０５０は、カウンタ格納部１０３０に格納されているカウンタｃｏｕｎｔをデクリメント（１を減算）する。
【００５５】
第１のカウンタ判定部１０６０は、カウンタ格納部１０３０に格納されているカウンタｃｏｕｎｔの値が０であるかを判定する。
【００５６】
第２のカウンタ判定部１０７０は、カウンタ格納部１０３０に格納されているカウンタｃｏｕｎｔの値が８で割り切れるか否か、すなわち、８の倍数であるか否かを判定する。
【００５７】
ビット判定部１０８０は、カウンタ格納部１０３０に格納されているカウンタｃｏｕｎｔに対し、秘密鍵格納部１０２０に格納されている秘密鍵ｄのｃｏｕｎｔビット目の値が０か１のどちらであるかを判定する。ここで、秘密鍵ｄのｃｏｕｎｔビット目とは、下位のビットから順番に数えたときの順番を示している。ただし、最下位ビットを０ビット目としている。
【００５８】
乗算部１０９０は、中間値格納部１１１０に格納されている中間値Ｚと、乗数格納部１１２０に格納されている乗数値Ｘ＿０または、乗数値Ｘ＿１を乗算し、その乗算結果を中間値格納部１１１０に格納する。具体的には、中間値Ｚと乗数値Ｘ＿０を乗算する場合、Ｚ←Ｚ×Ｘ＿０  ｍｏｄ  ｎを実行する。ここで、ｎはＲＳＡ暗号における大きな素数ｐ、ｑの積であり、←は右の計算結果を左の変数へ代入することを意味する。
【００５９】
２乗算部１１００は、中間値格納部１１１０に格納されている中間値Ｚを２乗し、２乗した結果を中間値格納部１１１０に格納する。具体的には、Ｚ←Ｚ＾２  ｍｏｄ  ｎを実行する。
【００６０】
中間値格納部１１１０は、べき乗演算の中間値Ｚを格納する。
【００６１】
乗数格納部１１２０は、乗算部１０９０で使用する乗数Ｘ＿０及びＸ＿１を格納する。
【００６２】
乱数格納部１１３０は、乱数Ｒと乱数性除去数Ｕを格納する。乱数Ｒ及び乱数性除去数Ｕは、予め与えられているものとする。
【００６３】
乗数初期化部１１４０は、乗数格納部１１２０に格納されている乗数Ｘ＿０及びＸ＿１を初期化する。具体的には、対象データＸに対し、乱数格納部１１３０に格納されている乱数Ｒを用いて、Ｘ＿０←Ｒ  ｍｏｄ  ｎ、Ｘ＿１←Ｘ×Ｘ＿０  ｍｏｄ  ｎとする。ここで、←は右の結果を左の変数に代入することを意味する。
【００６４】
乗数更新部１１５０は、乗数格納部１１２０に格納されている乗数Ｘ＿０及びＸ＿１を更新する。具体的には、Ｘ＿０←Ｘ＿０＾２  ｍｏｄ  ｎ、Ｘ＿１←Ｘ×Ｘ＿０  ｍｏｄ  ｎとする。
【００６５】
乱数性除去部１１６０は、乗数Ｘ＿０及びＸ＿１に乗じた乱数Ｒの影響を取り除くために、乱数性除去数Ｕを中間値格納部１１１０に格納されている中間値Ｚに乗じて、その結果を中間値格納部１１１０へ格納する。すなわち、Ｚ←Ｚ×Ｕ  ｍｏｄ  ｎを実行する。ここで、Ｕ＝Ｒ＾ｕ  ｍｏｄ  ｎであり、ｕ＝（１＋２＋２＾２＋２＾３＋２＾４＋２＾５＋２＾６＋２＾７）×（２＾５０４＋２×２＾４９６＋２＾２×２＾４８８＋・・・＋２＾６３）である。ただし、このｕは秘密鍵ｄが５１２ビットの整数であり、８ビットごとに乗数を更新する場合の値であり、秘密鍵ｄの大きさが大きくなったり、乗数を更新するタイミングが変わったりすれば、ｕの値も変化する。
【００６６】
乱数更新部１１７０は、乱数格納部１１３０に格納されている乱数と乱数性除去数Ｕを更新する。具体的には、乱数格納部１１３０に格納されている乱数Ｒに対し、Ｒ←Ｒ＾２  ｍｏｄ  ｎ、Ｕ←Ｕ＾２  ｍｏｄ  ｎを実行する。
【００６７】
＜べき乗演算装置１０００の動作＞
べき乗演算装置１０００は、対象データＸとして入力し、対象データＸの秘密鍵ｄをべき値としたべき乗演算結果を出力する。図２は、べき乗演算装置１０００のフローチャートを示している。以下では、べき乗演算装置１０００の動作を示す。
【００６８】
ステップＳ１０１：入出力部１０１０は、対象データＸの入力を受け付け、中間値格納部１１１０に中間値Ｚとして格納する。
【００６９】
ステップＳ１０２：乗数初期化部１１４０は、対象データＸを用いて、乗数格納部１１２０に格納する乗数Ｘ＿０とＸ＿１を初期化する。
【００７０】
ステップＳ１０３：カウンタ初期化部１０４０は、カウンタｃｏｕｎｔを初期化する。具体的には、カウンタｃｏｕｎｔをｌｅｎｄ−１に設定する。
【００７１】
ステップＳ１０４：２乗算部１１００は、中間値格納部１１１０に格納されている中間値Ｚを２乗し、その結果を中間値格納部１１１０に格納する。
【００７２】
ステップＳ１０５：ビット判定部１０８０は、秘密鍵ｄのビットを判定する。そのビットが０である場合、次のステップＳ１０６へ、１である場合、ステップＳ１０７へ。
【００７３】
ステップＳ１０６：乗算部１０９０は、中間値格納部１１１０に格納されている中間値Ｚと、乗数格納部１１２０に格納されている乗数Ｘ＿０を乗算し、その結果を中間値格納部１１１０に格納する。ステップＳ１０８へ。
【００７４】
ステップＳ１０７：乗算部１０９０は、中間値格納部１１１０に格納されている中間値Ｚと、乗数格納部１１２０に格納されている乗数Ｘ＿１を乗算し、その結果を中間値格納部１１１０に格納する。
【００７５】
ステップＳ１０８：第１のカウンタ判定部１０６０は、カウンタ格納部１０３０に格納されているカウンタｃｏｕｎｔの判定をする。カウンタｃｏｕｎｔが０であれば、ステップＳ１１２へ。それ以外は、次のステップＳ１０９へ。
【００７６】
ステップＳ１０９：第２のカウンタ判定部１０７０は、カウンタ格納部１０３０に格納されているカウンタｃｏｕｎｔの判定をする。判定結果が肯定（カウンタｃｏｕｎｔが８で割り切れる）の場合は、次のステップＳ１１０へ。それ以外は、ステップＳ１１１へ。
【００７７】
ステップＳ１１０：乗数更新部１１５０は、乗数格納部１１２０に格納されている乗数Ｘ＿０とＸ＿１を更新する。
【００７８】
ステップＳ１１１：カウンタ更新部１０５０は、カウンタ格納部１０３０に格納されているカウンタｃｏｕｎｔを更新する。ステップＳ１０４へ。
【００７９】
ステップＳ１１２：乱数性除去部１１６０は、中間値格納部１１１０に格納されている中間値Ｚと乱数格納部１１３０に格納されている乱数性除去数Ｕを乗算し、その結果を中間値格納部１１１０に格納する。
【００８０】
ステップＳ１１３：入出力部１０１０は、中間値格納部１１１０に格納されている中間値Ｚを（べき乗演算結果として）出力する。
【００８１】
ステップＳ１１４：乱数更新部１１７０は、乱数格納部１１３０に格納されている乱数Ｒ及び乱数性除去数Ｕを更新する。終了。
【００８２】
＜実施の形態１の効果＞
実施の形態１では、ｄを８ビットのブロックごとに乗数更新部１１５０において、中間値Ｚに乗じる乗数Ｘ＿０、Ｘ＿１を更新している。こうすることによって、ブロックごとに乗数が異なるようになり、乗数が何であるかを解析することにより、秘密鍵ｄを求めるＢｉｇＭａｃ攻撃を防ぐことが可能となる。以下で、詳細に説明する。
【００８３】
図３は、実施の形態１のべき乗演算装置１０００の秘密鍵ｄに対する処理と、攻撃者による乗数の分類及びｄのビット推測について示している。ブロック１では、ｄのビットが０の場合はＸ＿０＝Ｘ＿０１を中間値Ｚに乗じ、１の場合はＸ＿１＝Ｘ＿１１を乗じる。ブロック２では、Ｘ＿０をＸ＿０１からＸ＿０２、Ｘ＿１をＸ＿１１からＸ＿１２に更新しているため、ｄのビットが０の場合はＸ＿０＝Ｘ＿０２、１の場合はＸ＿１＝Ｘ＿１２を乗じる。ここで、攻撃者は、消費電力波形より、ブロック１の中に乗数が互いに異なるグループａ１とｂ１、ブロック２の中に乗数が互いに異なるグループａ２とｂ２に波形を分類できる。しかし、攻撃者はグループａ１とｂ１のどちらがｄのビットが０、１に対応するか、グループａ２とｂ２のどちらがｄのビットが０、１に対応するかを知らないため、それぞれのブロック内でどちらかのグループをｄのビットが０（または１）に対応すると仮定して、正しいか否かを確認する必要がある。ａ１、ｂ１がｄのビット０、１に対応するパターンは２通りあり、ａ２、ｂ２がｄのビット０、１に対応するパターンは２通りあるため、それぞれの組合せは２×２＝４通りある。したがって、攻撃者は４通りを試す必要がある。ここで、ブロックの個数をＮＢとすると、攻撃者は２＾ＮＢ通りを試す必要がある。ＮＢを大きくすると、その分、攻撃者の試す時間がかかり、ＢｉｇＭａｃ攻撃に対する安全性が高まる。例えば、秘密鍵ｄを５１２ビットの整数とするとき、８ビットのブロックは５１２／８＝６４個存在するため、安全性（攻撃者の試す時間）は２＾６４であり高い。このように、ＢｉｇＭａｃ攻撃を防ぐことができる。
【００８４】
また、乱数更新部１１７０において、乱数Ｒを更新することにより、対象データＸにより同じ乱数Ｒを使うことにより電力波形に偏りが出ることを利用して解析する差分電力解析攻撃を防ぐことが可能となる。
【００８５】
（実施の形態２）
図４は、本発明にかかる実施の形態２としてのべき乗演算装置２０００の構成を示す図である。本装置は、実施の形態１と同様の入出力部１０１０と、秘密鍵格納部１０２０と、カウンタ格納部１０３０と、カウンタ更新部１０５０と、第１のカウンタ判定部１０６０と、第２のカウンタ判定部１０７０と、２乗算部１１００と、中間値格納部１１１０と、乱数更新部１１７０と、実施の形態１と異なるカウンタ初期化部２０４０と、乗数選択部２０８０と、乗算部２０９０と、乗数格納部２１２０と、乱数格納部２１３０と、乗数初期化部２１４０と、乗数更新部２１５０と、乱数性除去部２１６０とを備える。本装置は、対象データとして入力し、対象データの秘密鍵ｄをべき値としたべき乗演算結果を出力する。
【００８６】
本べき乗演算装置２０００は、実施の形態１のべき乗演算装置１０００と同様に、例えば、ＲＳＡ暗号方式の復号化やＲＳＡ署名方式の署名作成において、使用する。
【００８７】
＜べき乗演算装置２０００の各部について＞
カウンタ初期化部２０４０は、カウンタｃｏｕｎｔをｂに設定する。ここで、ｂは（ｌｅｎ／ｓｗ以上の最も小さい整数）−１、ｓｗは正整数、ｌｅｎは秘密鍵ｄのビットサイズである。例えば、ｌｅｎ＝５１２である。以下では簡単のため、ｓｗ＝４とする。なお、ｓｗは２、３や５以上であってもよい。
【００８８】
乗数選択部２０８０は、カウンタ格納部１０３０に格納されているカウンタｃｏｕｎｔに対する後述する分割秘密情報ｄ＿ｃｏｕｎｔの値をインデックスｉ（ｉ＝ｄ＿ｃｏｕｎｔ）として、乗数格納部２１２０に格納されている乗数Ｘ＿ｉを選択する。
【００８９】
乗算部２０９０は、中間値格納部１１１０に格納されている中間値Ｚと、乗数選択部２０８０で選択された乗数Ｘ＿ｉを乗算し、その乗算結果を中間値格納部１１１０に格納する。具体的には、Ｚ←Ｚ×Ｘ＿ｉ  ｍｏｄ  ｎを実行する。ここで、ｎはＲＳＡ暗号における大きな素数ｐ、ｑの積であり、←は右の計算結果を左の変数へ代入することを意味する。
【００９０】
乗数格納部２１２０は、乗算部２０９０で使用する乗数Ｘ＿０、Ｘ＿１、．．．、Ｘ＿１５を格納する。なお、Ｘ＿０からＸ＿１５を格納するのは、ｓｗ＝４であるためである。一般のｓｗに対しては、乗数格納部２１２０は、乗数Ｘ＿０、Ｘ＿１、．．．、Ｘ＿（２＾ｓｗ−１）を格納する。
【００９１】
乱数格納部２１３０は、乱数Ｒと乱数性除去数Ｕを格納する。乱数Ｒ及び乱数性除去数Ｕは、予め与えられているものとする。
【００９２】
乗数初期化部２１４０は、乗数格納部２１２０に格納されている乗数Ｘ＿０、Ｘ＿１、．．．、Ｘ＿１５を初期化する。具体的には、対象データＸに対し、乱数格納部２１３０に格納されている乱数Ｒを用いて、Ｘ＿０←Ｒ  ｍｏｄ  ｎ、Ｘ＿１←Ｘ×Ｘ＿０  ｍｏｄ  ｎ、Ｘ＿２←Ｘ×Ｘ＿１  ｍｏｄ  ｎ、．．．、Ｘ＿１５←Ｘ×Ｘ＿１４  ｍｏｄ  ｎ（＝Ｘ＾１５×Ｒ  ｍｏｄ  ｎ）とする。ここで、←は右の結果を左の変数に代入することを意味する。
【００９３】
乗数更新部２１５０は、乗数格納部２１２０に格納されている乗数Ｘ＿０、Ｘ＿１、．．．、Ｘ＿１５を更新する。具体的には、Ｘ＿０←Ｘ＿０＾２  ｍｏｄ  ｎ、Ｘ＿１←Ｘ×Ｘ＿０  ｍｏｄ  ｎ、Ｘ＿２←Ｘ×Ｘ＿１  ｍｏｄ  ｎ、．．．、Ｘ＿１５←Ｘ×Ｘ＿１４  ｍｏｄ  ｎとする。
【００９４】
乱数性除去部２１６０は、乗数Ｘ＿０、Ｘ＿１、．．．、Ｘ＿１５に乗じた乱数Ｒの影響を取り除くために、乱数性除去数Ｕを中間値格納部１１１０に格納されている中間値Ｚに乗じて、その結果を中間値格納部１１１０へ格納する。すなわち、Ｚ←Ｚ×Ｕ  ｍｏｄ  ｎを実行する。ここで、Ｕ＝Ｒ＾ｕ  ｍｏｄ  ｎであり、ｕ＝（１＋２＾４＋２＾８＋２＾１２＋２＾１６＋２＾２０＋２＾２４＋２＾２８）×（２＾４８０＋２×２＾４４８＋２＾２×２＾４１６＋・・・＋２＾１５）である。ただし、このｕは秘密鍵ｄが５１２ビットの整数であり、カウンタが８削減されるたびに乗数を更新する場合の値であり、秘密鍵ｄの大きさが大きくなったり、乗数を更新するタイミングが変わったりすれば、ｕの値も変化する。
【００９５】
＜べき乗演算装置２０００の動作＞
べき乗演算装置２０００は、対象データＸとして入力し、対象データＸの秘密鍵ｄをべき値としたべき乗演算結果を出力する。図５は、べき乗演算装置２０００のフローチャートを示している。以下では、べき乗演算装置２０００の動作を示す。
【００９６】
ステップＳ２０１：入出力部１０１０は、対象データＸの入力を受け付け、中間値格納部１１１０に中間値Ｚとして格納する。
【００９７】
ステップＳ２０２：乗数初期化部２１４０は、対象データＸを用いて、乗数格納部２１２０に格納する乗数Ｘ＿０、Ｘ＿１、．．．、Ｘ＿１５を初期化する。
【００９８】
ステップＳ２０３：カウンタ初期化部２０４０は、カウンタｃｏｕｎｔを初期化する。具体的には、カウンタｃｏｕｎｔをｂに設定する。
【００９９】
ステップＳ２０４：２乗算部１１００は、中間値格納部１１１０に格納されている中間値Ｚを２乗し、その結果を中間値格納部１１１０に格納する。これをさらに３回繰り返すことで、ステップ２０４以前の中間値Ｚを１６乗する。
【０１００】
ステップＳ２０５：乗数選択部２０８０は、乗数格納部２１２０に格納されている乗数Ｘ＿ｉを選択する。
【０１０１】
ステップＳ２０６：乗算部２０９０は、中間値格納部１１１０に格納されている中間値Ｚと、乗数選択部２０８０で選択した乗数Ｘ＿ｉを乗算し、その結果を中間値格納部１１１０に格納する。
【０１０２】
ステップＳ２０７：第１のカウンタ判定部１０６０は、カウンタ格納部１０３０に格納されているカウンタｃｏｕｎｔの判定をする。カウンタｃｏｕｎｔが０であれば、ステップＳ２１１へ。それ以外は、次のステップＳ２０８へ。
【０１０３】
ステップＳ２０８：第２のカウンタ判定部１０７０は、カウンタ格納部１０３０に格納されているカウンタｃｏｕｎｔの判定をする。判定結果が肯定（カウンタｃｏｕｎｔが８で割り切れる）の場合は、次のステップＳ２０９へ。それ以外は、ステップＳ２１０へ。
【０１０４】
ステップＳ２０９：乗数更新部２１５０は、乗数格納部２１２０に格納されている乗数Ｘ＿０、Ｘ＿１、．．．、Ｘ＿１５を更新する。
【０１０５】
ステップＳ２１０：カウンタ更新部１０５０は、カウンタ格納部１０３０に格納されているカウンタｃｏｕｎｔを更新する。ステップＳ２０４へ。
【０１０６】
ステップＳ２１１：乱数性除去部２１６０は、中間値格納部１１１０に格納されている中間値Ｚと乱数格納部２１３０に格納されている乱数性除去数Ｕを乗算し、その結果を中間値格納部１１１０に格納する。
【０１０７】
ステップＳ２１２：入出力部１０１０は、中間値格納部１１１０に格納されている中間値Ｚを（べき乗演算結果として）出力する。
【０１０８】
ステップＳ２１３：乱数更新部１１７０は、乱数格納部１１３０に格納されている乱数Ｒ及び乱数性除去数Ｕを更新する。終了。
【０１０９】
＜実施の形態２の効果＞
実施の形態２では、ｄを８×４＝３２ビットのブロックごとに乗数更新部２１５０において、中間値Ｚに乗じる乗数Ｘ＿０、Ｘ＿１、．．．、Ｘ＿１５を更新している。こうすることによって、実施の形態１と同様にブロックごとに乗数が異なるようになり、乗数が何であるかを解析することにより、秘密鍵ｄを求めるＢｉｇＭａｃ攻撃を防ぐことが可能となる。
【０１１０】
（変形例）
上記に説明した実施の形態は、本発明の実施の一例であり、本発明はこの実施の形態に何ら限定されるものではなく、その旨を逸脱しない範囲において種々なる態様で実施し得るものである。例えば、以下のような場合も本発明に含まれる。
【０１１１】
（１）実施の形態１及び２における秘密鍵ｄのビットサイズは、５１２に限らない。１０２４や２０４８であってもよい。また、べき乗演算装置１０００では、Ｘ＾ｄ  ｍｏｄ  ｎを計算するが、ｄｐ＝ｄ  ｍｏｄ  ｐ−１，ｄｑ＝ｄ  ｍｏｄ  ｑ−１とし、Ｘ＾ｄｐ  ｍｏｄ  ｐとＸ＾ｄｑ  ｍｏｄ  ｑを計算し、中国人の剰余定理を用いることでＸ＾ｄ  ｍｏｄ  ｎを計算するとしてもよい。ここで、Ｘ＾ｄｐ  ｍｏｄ  ｐ及びＸ＾ｄｑ  ｍｏｄ  ｑを計算する際にべき乗演算装置１０００を使用してもよい。この場合、例えば、Ｘ＾ｄｐ  ｍｏｄ  ｐを計算するときは、乗算部１０９０などで使用しているｍｏｄ  ｎをｍｏｄ  ｐとして、べき乗演算装置１０００を実施する。
【０１１２】
（２）本発明は、べき乗を演算するのではなく、楕円曲線の点のスカラ倍点を演算するとしてもよい。その場合、べき乗演算装置１０００で実施している乗算は楕円加算であり、２乗算は楕円２倍算となる。また、「べき」は「スカラ」に対応する。
【０１１３】
（３）実施の形態１及び２における第２のカウンタ判定部１０７０は、カウンタが８で割り切れるか否かを判定しているが、これに限らない。例えば、４で割り切れるか否かを判定してもよい。この場合、実施の形態１では、ｕ＝（１＋２＋２＾２＋２＾３）×（２＾５０８＋２×２＾５０４＋２＾２×２＾５００＋・・・＋２＾１２７）、実施の形態２では、ｕ＝（１＋２＾４＋２＾８＋２＾１２）×（２＾４９６＋２×２＾４８４＋２＾２×２＾４６８＋・・・＋２＾３１）となる。また、複数の正整数を含めたテーブルを保持し、このテーブルに格納されている正整数であるかを判定してもよい。なお、このテーブルに含める正整数は、８の倍数など、規則性のあるものだけでなく、規則性がないものであってもよい。また、これらの場合も、その正整数の値により、ｕは変化する。
【０１１４】
（４）実施の形態１における乗数更新部１１５０や実施の形態２における乗数更新部２１５０において、乗数Ｘ＿０を２乗しているが、これに限らない。例えば、３乗してもよい。この場合、実施の形態１では、ｕ＝（１＋２＋２＾２＋２＾３＋２＾４＋２＾５＋２＾６＋２＾７）×（２＾５０４＋３×２＾４９６＋３＾２×２＾４８８＋・・・＋３＾６３）、実施の形態１では、ｕ＝（１＋２＾４＋２＾８＋２＾１２＋２＾１６＋２＾２０＋２＾２４＋２＾２８）×（２＾４８０＋３×２＾４４８＋３＾２×２＾４１６＋・・・＋３＾１５）となる。ただし、この場合、第２のカウンタ判定部１０７０で、カウンタが８で割り切れるか否かを判定しているものとする。
【０１１５】
（５）実施の形態１及び２における乱数更新部１１７０において、乱数Ｒを２乗することで更新しているが、これに限らない。例えば、３乗してもよい。また、固定の値を予め保持しておき、これを乱数Ｒに乗じることで乱数Ｒを更新してもよい。また、乱数更新部１１７０は、差分電力解析攻撃を防ぐためにべき乗演算装置１０００に含めており、この他で差分電力解析攻撃対策を施す場合は、乱数更新部１１７０はなくてもよい。
【０１１６】
（６）本発明は、べき乗演算装置でなく、これを利用するＲＳＡ暗号の復号化装置やＲＳＡ署名の署名生成装置であってもよい。また、秘密情報をべき値としたべき乗演算を実行する情報セキュリティ装置であってもよい。例えば、ＥｌＧａｍａｌ暗号の復号化装置であったり、ＤＳＡ署名の署名生成装置であったりしてもよい。
【０１１７】
（７）上記の各装置は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、ディスプレイユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記ＲＡＭまたはハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムにしたがって動作することにより、各装置は、その機能を達成する。ここでコンピュータプログラムは、所定の機能を達成するために、コンピュータに対する指令を示す命令コードが複数個組み合わされて構成されたものである。
【０１１８】
（８）上記の各装置を構成する構成要素の一部または全部は、１個のシステムＬＳＩ（Ｌａｒｇｅ  Ｓｃａｌｅ  Ｉｎｔｅｇｒａｔｉｏｎ：大規模集積回路）から構成されているとしてもよい。システムＬＳＩは、複数の構成部を１個のチップ上に集積して製造された超多機能ＬＳＩであり、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどを含んで構成されるコンピュータシステムである。前記ＲＡＭには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムにしたがって動作することにより、システムＬＳＩは、その機能を達成する。
【０１１９】
（９）上記の各装置を構成する構成要素の一部または全部は、各装置に脱着可能なＩＣカードまたは単体のモジュールから構成されているとしてもよい。前記ＩＣカードまたは前記モジュールは、マイクロプロセッサ、ＲＯＭ、ＲＡＭなどから構成されるコンピュータシステムである。前記ＩＣカードまたは前記モジュールは、上記の超多機能ＬＳＩを含むとしてもよい。マイクロプロセッサが、コンピュータプログラムにしたがって動作することにより、前記ＩＣカードまたは前記モジュールは、その機能を達成する。このＩＣカードまたはこのモジュールは、耐タンパ性を有するとしてもよい。
【０１２０】
（１０）本発明は、上記に示す方法であるとしてもよい。また、これらの方法をコンピュータにより実現するコンピュータプログラムであるとしてもよいし、前記コンピュータプログラムからなるディジタル信号であるとしてもよい。
【０１２１】
（１１）また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号をコンピュータ読み取り可能な記録媒体、例えば、フレキシブルディスク、ハードディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、ＢＤ（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ）、半導体メモリなどに記録したものとしてもよい。また、これらの記録媒体に記録されている前記ディジタル信号であるとしてもよい。
【０１２２】
（１２）また、本発明は、前記コンピュータプログラムまたは前記ディジタル信号を、電気通信回線、無線または有線通信回線、インターネットを代表とするネットワーク、データ放送等を経由して伝送するものとしてもよい。
【０１２３】
（１３）また、本発明は、マイクロプロセッサとメモリを備えたコンピュータシステムであって、前記メモリは、上記コンピュータプログラムを記憶しており、前記マイクロプロセッサは、前記コンピュータプログラムにしたがって動作するとしてもよい。
【０１２４】
（１４）また、前記プログラムまたは前記ディジタル信号を前記記録媒体に記録して移送することにより、または前記プログラムまたは前記ディジタル信号を前記ネットワーク等を経由して移送することにより、独立した他のコンピュータシステムにより実施するとしてもよい。
【０１２５】
（１５）上記実施の形態及び上記変形例をそれぞれ組み合わせるとしてもよい。
【産業上の利用可能性】
【０１２６】
これらの構成によると、ＢｉｇＭａｃ攻撃により安全性を低下することを防ぐことができる。
【図面の簡単な説明】
【０１２７】
【図１】本発明に係る１個の実施の形態としてのべき乗演算装置１０００の構成を示すブロック図
【図２】べき乗演算装置１０００の処理を示すフローチャート
【図３】べき乗演算装置１０００の秘密鍵ｄに対する処理と、攻撃者による乗数の分類及びｄのビット推測を示す図
【図４】本発明に係る１個の実施の形態としてのべき乗演算装置２０００の構成を示すブロック図
【図５】べき乗演算装置２０００の処理を示すフローチャート
【符号の説明】
【０１２８】
１０００，２０００    べき乗演算装置
１０１０    入出力部
１０２０    秘密鍵格納部
１０３０    カウンタ格納部
１０４０，２０４０    カウンタ初期化部
１０５０    カウンタ更新部
１０６０    第１のカウンタ判定部
１０７０    第２のカウンタ判定部
１０８０    ビット判定部
１０９０，２０９０    乗算部
１１００    ２乗算部
１１１０    中間値格納部
１１２０，２１２０    乗数格納部
１１３０，２１３０    乱数格納部
１１４０，２１４０    乗数初期化部
１１５０，２１５０    乗数更新部
１１６０，２１６０    乱数性除去部
１１７０    乱数更新部
２０８０    乗数選択部
【図１】
2007316491.tif 000003
【図２】
2007316491.tif 000004
【図３】
2007316491.tif 000005
【図４】
2007316491.tif 000006
【図５】
2007316491.tif 000007