(57)【特許請求の範囲】
【請求項１】
反復的モジュラー乗法ステップを有し、第１の法Ｎと秘密指数ｄと基数ｘとを入力とする、モジュラー累乗を実行する、好適なサイドチャンネルを見ることによりモジュラー二乗とモジュラー乗法とを区別できるプロセッサで実行される方法であって、
２つの値ａ、ｂと前記第１の法Ｎとからｃ＝ａ・ｂ  ｍｏｄＮとなるように結果ｃを計算することを目的とした前記反復的モジュラー乗法ステップの少なくとも１つのステップにおいて、
前記２つの値ａ、ｂと前記第１の法Ｎとを入力として取るステップと、
前記２つの値ａ、ｂと前記第１の法Ｎとから、２つのオペランドａ′、ｂ′と第２の法Ｎ′とを求めるステップであって、前記２つのオペランドａ′、ｂ′のうち少なくとも一方は前記２つの値ａ、ｂとは異なり、ａがｂと等しいとき、前記２つのオペランドａ′、ｂ′は異なるようにして、ａ′がｂ′と等しいときを除いてモジュラー乗法ｃ′＝ａ′・ｂ′  ｍｏｄＮ′がサイドチャンネルの観点から見て、モジュラー二乗と区別されるモジュラー乗法のように振る舞うようにし、最大でも線形の複雑性である演算を用いて、前記オペランドａ′は前記値ａから求め、前記オペランドｂ′は前記値ｂから求め、前記第２の法Ｎ′は前記第１の法Ｎから求める、ステップと、
中間結果ｃ′＝ａ′・ｂ′  ｍｏｄＮ′を計算するステップと、
前記中間結果ｃ′から前記結果ｃを求めるステップであって、ｃは最大でも線形の複雑性である演算を用いてｃ′から求めるステップと、
前記モジュラー累乗において前記結果ｃを用いるステップとを有する方法。
【請求項２】
ａ′＝２ａ、ｂ′＝ｂ＋Ｎ、及びＮ′＝２Ｎであり、ｃ′＝ｃ／２である、請求項１に記載の方法。
【請求項３】
ａ′＝Ｎ−ａ、ｂ′＝ｂ、及びＮ′＝Ｎであり、ｃ′＝Ｎ−ｃである、請求項１に記載の方法。
【請求項４】
前記第１の法Ｎは奇数である、請求項３に記載の方法。
【請求項５】
反復的モジュラー乗法ステップを有し、第１の法Ｎと秘密指数ｄと基数ｘとを入力とする、モジュラー累乗を実行するプロセッサであって、好適なサイドチャンネルを見ることによりモジュラー二乗とモジュラー乗法とを区別できるようにし、２つの値ａ、ｂと前記第１の法Ｎとからｃ＝ａ・ｂ  ｍｏｄＮとなるように結果ｃを計算する前記反復的モジュラー乗法ステップの少なくとも１つのステップにおいて、
前記２つの値ａ、ｂと前記第１の法Ｎとを入力として取る手段と、
前記２つの値ａ、ｂと前記第１の法Ｎとから、２つのオペランドａ′、ｂ′と第２の法Ｎ′とを求める手段であって、前記２つのオペランドａ′、ｂ′のうち少なくとも一方は前記２つの値ａ、ｂとは異なり、ａがｂと等しいとき、前記２つのオペランドａ′、ｂ′は異なるようにして、ａ′がｂ′と等しいときを除いてモジュラー乗法ｃ′＝ａ′・ｂ′  ｍｏｄＮ′がサイドチャンネルの観点から見て、モジュラー二乗と区別されるモジュラー乗法のように振る舞うようにし、最大でも線形の複雑性である演算を用いて、前記オペランドａ′は前記値ａから求め、前記オペランドｂ′は前記値ｂから求め、前記第２の法Ｎ′は前記第１の法Ｎから求める、手段と、
中間結果ｃ′＝ａ′・ｂ′  ｍｏｄＮ′を計算する手段と、
前記中間結果ｃ′から前記結果ｃを求めるステップであって、ｃは最大でも線形の複雑性である演算を用いてｃ′から求める手段とを有し、
前記プロセッサは、さらに、前記モジュラー累乗において前記結果ｃを用いる手段を有するプロセッサ。
【請求項６】
ａ′＝２ａ、ｂ′＝ｂ＋Ｎ、及びＮ′＝２Ｎであり、ｃ′＝ｃ／２である、請求項５に記載のプロセッサ。
【請求項７】
ａ′＝Ｎ−ａ、ｂ′＝ｂ、及びＮ′＝Ｎであり、ｃ′＝Ｎ−ｃである、請求項５に記載のプロセッサ。
【請求項８】
前記第１の法Ｎは奇数である、請求項７に記載のプロセッサ。
【請求項９】
プロセッサにより実行されたとき、前記プロセッサに、請求項１ないし４いずれか一項に記載の方法を実行させるコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して暗号化に関し、特に、一定のサイドチャンネル攻撃に抵抗力のあるべき乗累乗アルゴリズムに関する。
【背景技術】
【０００２】
このセクションは、以下に説明して特許を請求する本発明の様々な態様に関連する様々な態様の技術を読者に紹介することを意図するものである。この説明は、本発明の様々な態様の理解を容易にする背景情報を読者に提供する役に立つと思われる。従って、言うまでもなくこれらの記載は上記を考慮して読むべきであり、先行技術として認める（admissions of prior art）ものではない。
【０００３】
公開鍵暗号の基本演算はべき乗剰余である。入力Ｎ、ｘ、及びｄに対してｙ＝ｘｄ  ｍｏｄＮを計算する。もちろん、多数の先行技術のべき乗剰余アルゴリズムがあり、ここに２つの例を挙げる。
【０００４】
アルゴリズム１−左から右のバイナリ法
【０００５】
【数１】
0005977996.tif 000002
アルゴリズム２−右から左のバイナリ法
【０００６】
【数２】
0005977996.tif 000003
上記方法は両方とも効率的であるが、当業者には言うまでもなく、サイドチャンネル攻撃、特に単純パワー分析（ＳＰＡ）攻撃にさらされることがある。非特許文献１と非特許文献２を参照されたい。
【０００７】
主な問題は、条件分岐、すなわち「ｉｆ」文がある点にある。
【０００８】
この問題を解消する一方法は、繰り返しの各ループで乗算を実行すること、言い換えればｄｊ＝０となるたびにニセの乗算を実行することである。非特許文献３を参照されたい。しかし、その結果の実装は遅くなり、１ビットあたり約１．５回の乗算から１ビットあたり約２回の乗算にコストが増加する。欠点として、この実装はセーフエラー攻撃に弱くなる。非特許文献４と非特許文献５を参照されたい。
【０００９】
ＳＰＡタイプの攻撃を防ぐよりよい方法は、いわゆるサイドチャンネル原始性を用いることである。非特許文献６を参照されたい。対応するアルゴリズムは次の通りである：
アルゴリズム３−左から右のバイナリ法（原子的）
【００１０】
【数３】
0005977996.tif 000004
アルゴリズム４−右から左のバイナリ法（原子的）
【００１１】
【数４】
0005977996.tif 000005
アルゴリズム３、４では、
＜外１＞
0005977996.tif 000006
はＸＯＲ（排他的論理和）演算子を示し、
＜外２＞
0005977996.tif 000007
は否定演算子を示す（すなわち
＜外３＞
0005977996.tif 000008
）。
【００１２】
言うまでもなく、コストは上がらないが、１ビットあたり約１．５回の乗算のままである。また、言うまでもなく、サイドチャンネル原子性はバイナリ剰余法に限られたものではない。さらに別のアルゴリズムは、Chevallier-Mames、Ciet、Joyeたちによる上記の論文に記載されている。
【００１３】
サイドチャンネル原子性によりアルゴリズムは非常によくなるが、乗算演算が原子的（atomic）であることを仮定していることを強調しなければならない。より明示的には、好適なサイドチャンネルを見ることにより、二乗剰余（modular squaring）と乗算剰余（modular multiplication）を区別することはできない。この仮定は常に満たされるわけではない。具体的な攻撃が非特許文献７で報告されている。
【００１４】
言うまでもなく、サイドチャンネルの観点から、モジュラー乗算がモジュラー二乗のように振る舞う解が必要である。本発明はかかる解を提供するものである。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】「Paul Kocher, Joshua Jaffe, and Benjamin Jun; Differential PowerAnalysis; In M. Wiener, editor, Advances in Cryptology − CRYPTO’99, volume 1666 ofLecture Notes in Computer Science, pages 388−397; Springer-Verlag, 1999」
【非特許文献２】「Paul C. Kocher; Timing Attacks on Implementations of Diffie-Hellman,RSA, DSS, and Other Systems; In N. Koblitz, editor, Advances in Cryptology − CRYPTO’96, volume 1109 ofLecture Notes in Computer Science, pages 104−113. Springer-Verlag, 1996」
【非特許文献３】「Jean-Sebastien Coron; Resistance Against Differential Power Analysisfor Elliptic Curve Cryptosystems; In C.K. Koc and C. Paar, editors,Cryptographic Hardware and Embedded Systems −CHES’99, volume 1717 of Lecture Notes inComputer Science, pages 292−302. Springer-Verlag, 1999」
【非特許文献４】Sung-Ming Yen and Marc Joye; Checking before output may not beenough against fault-based cryptanalysis; IEEE Transactions on Computers,49(9):967−970,2000」
【非特許文献５】「Sung-Ming Yen, Seung-Joo Kim, Seon-Gan Lim, and Sang-Jae Moon; ACountermeasure Against One Physical Cryptanalysis May Benefit Another Attack;In K. Kim, editor, Information Security and Cryptology − ICISC 2001, volume 2288of Lecture Notes in Computer Science, pages 417−427. Springer-Verlag, 2002」
【非特許文献６】「Benoit Chevallier-Mames, Mathieu Ciet, and Marc Joye; Low-CostSolutions for Preventing Simple Side-channel Analysis: Side-Channel Atomicity;IEEE Transactions on Computers, 53(6):760−768, 2004」
【非特許文献７】「Frederic Amiel, Benoit Feix, Michael Tunstall, Claire Whelan, andWilliam P. Marnane; Distinguishing Multiplications from Squaring Operations; InR. Avanzi, L. Keliher, and F. Sica, editors, Selected Areas in Cryptography − SAC 2008, volume 5394 ofLecture Notes in Computer Science, pages 346−360. Springer-Verlag, 2009」
【発明の概要】
【課題を解決するための手段】
【００１６】
第１の態様では、本発明は、反復的モジュラー乗法ステップを有し、第１の法Ｎと秘密指数ｄと基数ｘとを入力として取るモジュラー累乗を実行する方法に関する。２つの値ａ、ｂと第１の法Ｎとからｃ＝ａ・ｂ  ｍｏｄＮとなるように結果ｃを計算する少なくとも１つのモジュラー乗法ステップにおいて、プロセッサは、前記２つの値ａ、ｂと前記第１の法Ｎとを入力として取り、前記２つの値ａ、ｂと前記第１の法Ｎとから、２つのオペランドａ′、ｂ′と第２の法Ｎ′とを求め、前記２つのオペランドａ′、ｂ′のうち少なくとも一方は前記２つの値ａ、ｂとは異なり、ａがｂと等しいとき、前記２つのオペランドａ′、ｂ′は異なるようにして、ａ′がｂ′と等しいときを除いて前記モジュラー乗法ｃ＝ａ・ｂ  ｍｏｄＮがサイドチャンネルの観点から見て、モジュラー二乗のように振る舞うようにし、最大でも線形の複雑性である演算を用いて、前記オペランドａ′は前記値ａから求め、前記オペランドｂ′は前記値ｂから求め、前記第２の法Ｎ′は前記第１の法Ｎから求め、中間結果ｃ′＝ａ′・ｂ′  ｍｏｄＮ′を計算し、前記中間結果ｃ′から前記結果ｃを求め、ｃは最大でも線形の複雑性である演算を用いてｃ′から求め、前記モジュラー累乗において前記結果ｃを用いる。
【００１７】
第１の好ましい実施形態において、ａ′＝２ａ、ｂ′＝ｂ＋Ｎ、及びＮ′＝２Ｎであり、ｃ′＝ｃ／２である。
【００１８】
第２の好ましい実施形態において、ａ′＝Ｎ−ａ、ｂ′＝ｂ、及びＮ′＝Ｎであり、ｃ′＝Ｎ−ｃである。前記第１の法Ｎは奇数であると有利である。
【００１９】
第２の態様では、本発明は、反復的モジュラー乗法ステップを有し、第１の法Ｎと秘密指数ｄと基数ｘとを入力とする、モジュラー累乗を実行するプロセッサに関する。前記プロセッサは、２つの値ａ、ｂと前記第１の法Ｎとからｃ＝ａ・ｂ  ｍｏｄＮとなる結果ｃを計算する少なくとも１つのモジュラー乗法において、前記２つの値ａ、ｂと前記第１の法Ｎとを入力として取る手段と、前記２つの値ａ、ｂと前記第１の法Ｎとから、２つのオペランドａ′、ｂ′と第２の法Ｎ′とを求める手段であって、前記２つのオペランドａ′、ｂ′のうち少なくとも一方は前記２つの値ａ、ｂとは異なり、ａがｂと等しいとき、前記２つのオペランドａ′、ｂ′は異なるようにして、ａ′がｂ′と等しいときを除いて前記モジュラー乗法ｃ＝ａ・ｂ  ｍｏｄＮがサイドチャンネルの観点から見て、モジュラー二乗のように振る舞うようにし、最大でも線形の複雑性である演算を用いて、前記オペランドａ′は前記値ａから求め、前記オペランドｂ′は前記値ｂから求め、前記第２の法Ｎ′は前記第１の法Ｎから求める、手段と、中間結果ｃ′＝ａ′・ｂ′  ｍｏｄＮ′を計算する手段と、前記中間結果ｃ′から前記結果ｃを求めるステップであって、ｃは最大でも線形の複雑性である演算を用いてｃ′から求める手段とを有し、前記プロセッサは、さらに、前記モジュラー累乗において前記結果ｃを用いる手段を有する。
【００２０】
第１の好ましい実施形態において、ａ′＝２ａ、ｂ′＝ｂ＋Ｎ、及びＮ′＝２Ｎであり、ｃ′＝ｃ／２である。
【００２１】
第２の好ましい実施形態において、ａ′＝Ｎ−ａ、ｂ′＝ｂ、及びＮ′＝Ｎであり、ｃ′＝Ｎ−ｃである。前記第１の法Ｎは奇数であると有利である。
【００２２】
第３の態様では、本発明は、プロセッサにより実行されると、第１の態様の方法を実行する命令を記憶したコンピュータプログラム製品に関する。
【図面の簡単な説明】
【００２３】
添付した図面を参照して、本発明の好ましい特徴を非限定的な例により説明する。
【図１】本発明の好ましい一実施形態による、あるサイドチャンネル攻撃に対する抵抗力のべき乗を求める装置を示す。
【発明を実施するための形態】
【００２４】
本発明の主要な発明的アイデアは、既述の通り、サイドチャンネルの観点から、あるサイドチャンネル攻撃に耐えうるべき乗剰余を与えるために用いることができる、モジュラー二乗のように振る舞うモジュラー乗算を求めることである。
【００２５】
これは、ａとｂのＮを法とするモジュラー乗算を評価することにより実現でき、ａ＝ｂのとき、モジュラー乗算に現れる２つのオペランドの値は異なる。
【００２６】
第１の好ましい実施形態は、任意の要素
＜外４＞
0005977996.tif 000009
について、
＜外５＞
0005977996.tif 000010
であるとの観察に基づく。
【００２７】
証明：整数Ｔ＝（ａ＋ａ）・（ｂ＋Ｎ）とＳ＝Ｔ／２を定義する。
【００２８】
＜外６＞
0005977996.tif 000011
となる。よって、
＜外７＞
0005977996.tif 000012
が得られる。（Ｔ  ｍｏｄ２Ｎ）／２は｛０，．．．，Ｎ−１｝の中にあるので、結果は次の通りである。（証明終わり）
ａ＝ｂのとき、（ａ＋ａ）・・・（ｂ＋Ｎ）＝（２ａ）・・・（ａ＋Ｎ）及び２ａ≠ａ＋Ｎとなる。そうでないとａ＝Ｎとなるが、これはａが
＜外８＞
0005977996.tif 000013
に含まれる（すなわち、集合｛０，１，．．．，Ｎ−１｝に含まれる）ので、あり得ないからである。言い換えると、ａ＝ｂのとき、モジュラー乗算（ａ＋ａ）・・・（ｂ＋Ｎ）  ｍｏｄ２Ｎに現れる２つのオペランドの値は異なる。
【００２９】
第２の好ましい実施形態は次の等式によるものである：
＜外９＞
0005977996.tif 000014
。
【００３０】
証明：整数
＜外１０＞
0005977996.tif 000015
を定義する。（−１）２＝１なので、明らかにＳ≡ａ・ｂ（ｍｏｄＮ）である。さらに、Ｓ∈｛０，．．．，Ｎ−１｝である。（証明終わり）
再び、Ｎが奇数とすると、ａ＝ｂのとき、モジュラー乗算（Ｎ−ａ）・ｂ  ｍｏｄＮに現れる２つのオペランドの値は異なる。確かに、ａ＝ｂであれば、（Ｎ−ａ）・ｂ＝（Ｎ−ａ）・ａと（Ｎ−ａ）≠ａは、Ｎが奇数であれば常に満たされる。
【００３１】
ａ′とｂ′がオペランドで、Ｎ′が修正したモジュラー乗算の法であり、ｃ′が修正したモジュラー乗算の結果であり、正しい出力ｃを求めるために調整する必要があるものだとすると、言うまでもなく、オペランドａ′とｂ′と法Ｎ′は最大でも線形の複雑性の演算を用いて求められる。当業者には、ｃ′からｃを求めるために用いる演算の場合と同様に、Ｎ′＝２Ｎは通常加法又はビットシフトとして実施され、「割り算」はビットシフトとして実施される。
【００３２】
いずれかの実施形態を背景技術欄で説明したアルゴリズム３と４で用いて、次のアルゴリズムが得られる。
【００３３】
アルゴリズム３′−第１の実施形態を実装する左から右へのバイナリ法（原子的）
【００３４】
【数５】
0005977996.tif 000016
アルゴリズム４′−第２の実施形態を実装する右から左へのバイナリ法（原子的）
【００３５】
【数６】
0005977996.tif 000017
留意点として、書き換えた式がモジュラー二乗となる場合がある。これの一例は、第１の実施形態の式を用いる、Ｎ＝１２０である７０と２０のモジュラー乗法である。
（（７０＋７０）・（２０＋１２０）  ｍｏｄ２４０）／２＝（１４０・１４０  ｍｏｄ２４０）／２＝（１９６００  ｍｏｄ２４０）／２＝１６０／２＝８０。これの第２の実施形態の式を用いる一例は、Ｎ＝１２１である７０と５１のモジュラー乗法であり：
１２１−（（１２１−７０）・５１  ｍｏｄ１２１）＝１２１−（５１・５１  ｍｏｄ１２１）＝１２１−（２６０１  ｍｏｄ１２１）＝６１。
【００３６】
しかし、言うまでもなく、この場合が起こるのは、しばしば起こる元の原子的スキームの二乗よりまれである。さらに、一定のランダム化方法と組み合わせると、かかる衝突値を生成することは難しいだろう。これは、例えば、べき乗剰余ｙ＝ｘｄ  ｍｏｄＮをｙ＝［（ｘ＋ｒ・Ｎ）ｄ  ｍｏｄｔ・Ｎ］  ｍｏｄＮとして計算した時に起こる。ここで、ｔはセキュリティパラメータｋのためのランダムなｋビット整数であり、ｒは｛０，．．．，ｔ−１｝のランダム整数である。
【００３７】
図１は、本発明の好ましい実施形態による装置を示す。装置１００は、他の装置（図示せず）と通信するように構成された少なくとも１つのインタフェースユニット１１０と、少なくとも１つのプロセッサ１２０と、データを記憶するように構成された、アキュムレータや中間計算結果などの少なくとも１つのメモリ１３０とを有する。プロセッサ１２０は、本発明の方法のいずれかの実施形態によるモジュラー乗算を計算し、前述の通り、かかる乗算を実施するべき乗剰余アルゴリズムも実行するように構成されている。ＣＤ−ＲＯＭやＤＶＤなどのコンピュータプログラム製品１４０は、プロセッサ１２０により実行されたとき、本発明のいずれかの実施形態による方法を実行する命令を記憶している。
【００３８】
言うまでもなく、本乗算方法により、サイドチャンネル攻撃に対する防禦が強化されたべき乗剰余（modular exponentiation）を提供することができる。
【００３９】
明細書、特許請求の範囲、及び図面に開示した各特徴は、独立に設けることもできるし、適切に組み合わせて設けることもできる。ハードウェアで実施されると説明した機能はソフトウェアでも実施できるし、その逆の場合もある。特許請求の範囲に示す参照符号は例示であり、請求項の範囲を限定するものではない。
【図１】
0005977996.tif 000018