(57)【要約】  楕円曲線暗号における低減技術が、最上位ワード(Most Significant Word)が１である状態の第１セクションを含む素数を、N = nm-1 + N1B + n0と共に利用する。
2007520729.tif 000002
【特許請求の範囲】
【請求項１】
暗号化計算において低減演算を行う方法であって、
最上位ワードが「１」である状態を複数備える第１セクションと、「１」又は「０」の状態を複数備える第２セクションとを持つモジュラスを、該２つのセクションにより形成される数が、モジュラス又はモジュラスの倍数となるよう選択し、
前記モジュラス／倍数に対する低減演算を行うことを有する方法。
【請求項２】
複数の乗算演算を実行することを有する請求項１に記載の方法。
【請求項３】
複数の乗算演算を実行し、後に低減演算を実行することを有する請求項２に記載の方法。
【請求項４】
前記乗算演算と前記低減演算とを組み合わせたものを繰り返すことを有する請求項３に記載の方法。
【請求項５】
前記モジュラス／倍数の倍数を使用することを有する請求項１乃至４のいずれかに記載の方法。
【請求項６】
直近の乗算がオーバーフローを与えるとき、前記オーバーフローが前記選択された数の一部に加えられる、請求項１乃至５のいずれかに記載の方法。
【請求項７】
前記オーバーフロー追加ステップがオーバーフローを与えるとき、n0’が該オーバーフローに加えられる、請求項６に記載の方法。
【請求項８】
２つの隣接する乗算間でのキャリーが、次回の乗算において加数として与えられる、請求項１乃至７のいずれかに記載の方法。
【請求項９】
先導する「１」の個数が(k-2)未満であるかどうかを決定するため、該個数を監視することを有する請求項１乃至８のいずれかに記載の方法。
【請求項１０】
前記先導する「１」の個数が(k-2)未満であるとき、次回の計算を開始することを有する請求項６に記載の方法。
【請求項１１】
１９２ビットECCと６４ビットのワードサイズとを演算することを有し、前記モジュラスは、１３８ビットの第１セクションと５４ビットの第２セクションとを含む、請求項１乃至１０のいずれかに記載の方法。
【請求項１２】
１２８ビットECCと６４ビットのワードサイズとを演算することを有し、前記モジュラスは、７４ビットの第１セクションと５４ビットの第２セクションとを含む、請求項１乃至１０のいずれかに記載の方法。
【請求項１３】
２５６ビットECCと６４ビットのワードサイズとを演算することを有し、前記モジュラスは、２０２ビットの第１セクションと５４ビットの第２セクションとを含む、請求項１乃至１０のいずれかに記載の方法。
【請求項１４】
デジタルコンピュータの内部メモリに直接ロード可能なコンピュータプログラムプロダクトであって、
前記プロダクトがコンピュータ上で実行されるとき、請求項１乃至１３のいずれか１つ又は複数に記載された前記方法を実行するためのソフトウェアコード部分を有するプログラムプロダクト。
【請求項１５】
デジタルコンピュータの内部メモリに直接ロード可能なコンピュータプログラムであって、
前記プログラムがコンピュータ上で実行されるとき、請求項１乃至１３のいずれか１つ又は複数に記載された前記方法を実行するためのソフトウェアコード部分を有するプログラム。
【請求項１６】
電気信号を有する、請求項１５に記載のコンピュータプログラム用のキャリア。
【請求項１７】
請求項１４に記載のコンピュータプログラムプロダクト、又は請求項１５に記載のコンピュータプログラム、又は請求項１６に記載のキャリアの電子配布。
【請求項１８】
暗号化計算において低減演算を行う装置であって、
「１」である状態を複数備える第１セクションと、「１」又は「０」の状態を複数備える第２セクションとを持つモジュラスを、該２つのセクションにより形成される数が、モジュラス又はモジュラスの倍数となるよう選択する手段と、
前記モジュラス／倍数に対する低減演算を行う手段とを有する装置。
【請求項１９】
複数の乗算演算を実行する手段を有する請求項１８に記載の装置。
【請求項２０】
複数の乗算演算を実行し、後に低減演算を実行する手段を有する請求項１９に記載の装置。
【請求項２１】
前記乗算演算と前記低減演算とを組み合わせたものを繰り返す手段を有する請求項２０に記載の装置。
【請求項２２】
前記モジュラス／倍数の倍数を使用する手段を有する請求項１８乃至２１のいずれかに記載の装置。
【請求項２３】
直近の乗算がオーバーフローを与えるとき、前記オーバーフローを前記選択された数の一部に加える手段を有する請求項１８乃至２２のいずれかに記載の装置。
【請求項２４】
前記オーバーフロー追加ステップがオーバーフローを与えるとき、n0’を該オーバーフローに加える手段を有する請求項２３に記載の装置。
【請求項２５】
２つの隣接する乗算間でのキャリーを、次回の乗算において加数として与える手段を有する請求項１８乃至２４のいずれかに記載の装置。
【請求項２６】
先導する「１」の個数が(k-2)未満であるかどうかを決定するため、該個数を監視する手段を有する請求項１８乃至２５のいずれかに記載の装置。
【請求項２７】
前記先導する「１」の個数が(K-2)未満であるとき、次回の計算を開始する手段を有する請求項１８乃至２６のいずれかに記載の装置。
【請求項２８】
１９２ビットECCと６４ビットのワードサイズとに対する手段を有し、前記モジュラスは、７４ビットの第１セクションと５４ビットの第２セクションとを含む、請求項１８乃至２７のいずれかに記載の装置。
【請求項２９】
１２８ビットECCと６４ビットのワードサイズとに対する手段を有し、前記モジュラスは、７４ビットの第１セクションと５４ビットの第２セクションとを含む、請求項１８乃至２７のいずれかに記載の装置。
【請求項３０】
２５６ビットECCと６４ビットのワードサイズとに対する手段を有し、前記モジュラスは、２０２ビットの第１セクションと５４ビットの第２セクションとを含む、請求項１８乃至２７のいずれかに記載の装置。
【請求項３１】
図１乃至図５のうちの１つ又は複数において示される対応図面を参照して説明される内容、及び／又は前記対応図面において説明される内容と実質的に同一の低減演算を行う方法。
【請求項３２】
暗号化計算において低減演算を行う装置であって、図１乃至図５のうちの１つ又は複数において示される対応図面を参照して説明される内容、及び／又は前記対応図面において説明される内容と実質的に同一の低減演算を行う装置。
【請求項３３】
暗号化計算を行う低減演算を行う方法であって、図１乃至図５のうちの１つ又は複数において示される対応図面を参照して説明される内容、及び／又は前記対応図面において説明される内容と実質的に同一の低減演算を行う方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、低減演算を行う方法及び低減演算を行う装置に関する。
【背景技術】
【０００２】
楕円曲線暗号(ECC: Elliptic Curve Cryptography)は、GF(p)における楕円曲線関係に基づく計算の使用を含み、例えば、暗号化プロセッサにおける公開鍵アルゴリズムの実装において、繰り返し実行されるlong型整数の乗算を必要とする。
【０００３】
一般に、暗号処理又は復号処理を完了するには、何百回となく乗算演算が行われなければならない。そして、これらの演算を行う暗号化デバイスは、高速の乗算器を用いてlong型の乗算を高速に実行することが重要である。
【０００４】
次第に、このような暗号アルゴリズムは、例えばスマートカードのような、アプリケーション処理能力や消費電力に厳しい制限が課される電子デバイスにおいて使用されるようになっている。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
従来技術の計算法としては、次式を用いて最上位ワード(Most Significant Word)に対する演算を行うQuisquaterシステムがある。
【０００６】
R’= R + (-N’* MSW)
ここで、N’はNの特殊な倍数である。-N’は、２の補数表記で使用されている。
【０００７】
低減演算が不十分であり、結果がとても大きくなるやもしれず、-N’をR’に加算する必要が生じる。
【０００８】
別の従来技術の計算法としては、次式を用いて最下位ワード(Least Significant Word)に対する演算を行うMongomeryシステムがある。
【０００９】
R’= R + N * Q
ここで、Q = LSW * M mod 2n である。
【００１０】
ここでも低減演算は不十分であり、1ビット分余計に大きいために、Nの減算をもう一度行う必要があるかもしれない。
【００１１】
そこで、本発明の目的は、より効率的な低減演算を提供することにある。
【００１２】
また、本発明の目的は、より乗算演算回数の少ない低減演算を提供することにある。
【００１３】
また、本発明の目的は、計算演算においてよりオーバーフローが少ない低減演算を提供することにある。
【００１４】
また、本発明の目的は、低減演算の完了がより速い低減演算を提供することにある。
【課題を解決するための手段】
【００１５】
１つの側面によれば、本発明は、暗号化計算において低減演算を行う方法であって、最上位ワードが「１」である状態を複数備える第１セクションと、「１」又は「０」の状態を複数備える第２セクションとを持つモジュラスを、その２つのセクションにより形成される数が、モジュラス又はモジュラスの倍数となるよう選択し、前述のモジュラス／倍数に対する低減演算を行うことを有する方法を提供する。
【００１６】
計算に使用するモジュラス／倍数を特定の形式で選択するこの方法により、その低減演算は乗算演算がより少なくて済む。
【００１７】
こうして、本発明により提供される重要な利点は、全体の計算演算を完了するのにかかる時間が短縮されることである。
【００１８】
更に、本発明の方法により提供される安全度は、既存の暗号化法と比較しても、同程度が維持される。
【００１９】
好ましくは、上記方法は、先導する「１」の個数が(k-2)未満であるかどうかを決定するため、その個数を監視することを含む。有利には、先導する「１」の個数が(k-2)未満であるとき、次回の計算が開始される。
【００２０】
こうして、本発明の更なる利点は、多数の乗算演算が同時に処理されることであり、それにより計算演算を完了するのにかかる時間が短縮されることである。
【００２１】
本発明のある実施形態によれば、１９２ビットECCと６４ビットのワードサイズに対して、上記モジュラスが、１３８ビットの第１セクションと５４ビットの第２セクションとを含む。
【００２２】
本発明の別の実施形態によれば、１２８ビットECCと６４ビットのワードサイズに対して、上記モジュラスが、７４ビットの第１セクションと５４ビットの第２セクションとを含む。
【００２３】
本発明の別の実施形態によれば、２５６ビットECCと６４ビットのワードサイズに対して、上記モジュラスが、２０２ビットの第１セクションと５４ビットの第２セクションとを含む。
【００２４】
本発明はまた、ワードサイズの倍数分より少ない数のビットを持つ複数のモジュラスと共に機能することができる。その場合、そのシステムは、先導する「１」を必要な数含む倍数のモジュラスと共に機能する。
【００２５】
ある好ましい変形例によれば、本発明の方法は最下位ワード(LSW: Least Significant Word)以外のすべてのワードが「１」であるm個のワードからなるモジュラスを利用する。そのLSWは、例えば、１０個の先導する「１」を持ち、いくつでもよいが、大きくすればするほど、追加的な低減が要求される回数は少なくなることを覚えておくとよい。
【００２６】
別の側面によれば、本発明は、デジタルコンピュータの内部メモリに直接ロード可能なコンピュータプログラムプロダクトであって、そのプロダクトがコンピュータ上で実行されるとき、本発明の方法を実行するためのソフトウェアコード部分を含むプログラムプロダクトを提供する。
【００２７】
別の側面によれば、本発明は、デジタルコンピュータの内部メモリに直接ロード可能なコンピュータプログラムであって、そのプログラムがコンピュータ上で実行されるとき、本発明の方法を実行するためのソフトウェアコード部分を含むプログラムを提供する。
【００２８】
別の側面によれば、本発明は、電気信号を含む、本発明を具体化するコンピュータプログラム用のキャリアを提供する。
【００２９】
別の側面によれば、本発明は、本発明のコンピュータプログラムプロダクト、又はコンピュータプログラム、又はキャリアの電子配布を提供する。
【００３０】
別の側面によれば、本発明は、暗号化計算において低減演算を行う装置であって、「１」である状態を複数備える第１セクションと、「１」又は「０」の状態を複数備える第２セクションとを持つモジュラスを、その２つのセクションにより形成される数が、モジュラス又はモジュラスの倍数となるよう選択する手段を含む装置を提供する。
【発明を実施するための最良の形態】
【００３１】
以下、本発明が容易に理解されるように、実施例に過ぎないものを介し、対応する図面を参照しながら、詳細な説明が与えられる。
【００３２】
図１は、スマートカード５０を搭載する、本発明のハードウェアによる実装のブロック図を示し、以下の要素を含む。
・一般的な制御のため、インタフェースを介して外部世界と通信を行うマイクロコントローラ５１。それは、RAM／ROMのデータへのポインタをセットし、コプロセッサを起動する。
・例えばISO-7816-3などに基づきスマートカードと通信するための、外部世界へのインタフェース。
・マイクロコントローラのプログラム用のリードオンリメモリ(ROM)５２。
・データ又はプログラム用の不揮発性ストレージであるプログラム可能リードオンリメモリ(フラッシュ又はEEPROM)５３。
・揮発データ、例えば、計算中の中間結果を格納するストレージであるRAM５４。
・ECCやRSAの計算用の特別な高速タスクを実行する専用のコプロセッサ５５。タスクが実行可能(ready)にされると、制御がマイクロコントローラに戻される。
【００３３】
変形例では、マイクロプロセッサと、制御論理を与えるコントローラのプログラミングに用いる、加算、減算、シフト演算を提供するALUと、そしてシフトレジスタによる次数検出とにより、本発明はソフトウェアで実装される。
【００３４】
図２は、複数のワードを含み、全体で１９２ビットのモジュラスを用いて行われる本発明の低減演算を示す。モジュラスは、６４ビットワード２つ分に１０ビットを加えた部分がすべて「１」の状態である第１セクションを含む。モジュラスの第２セクションは、５４ビットであり、全体の数が素数であればいくつであってもよい。数が大きくなればなるほど、追加的な低減が必要とされる機会は少なくなる。
【００３５】
一般的に、Nは次式のように表現できる。
N = nm-1 Bm-1 + … n1B + n0 (B = 264)
【００３６】
Nの選択にあたり特別に要求されることは、以下の通り。
・n1…nm-1は、定数であり、「１」だけを含む (n1 = … nm-1 = B-1)。
・n0は最上位からkビットが１であることを除けば、残りの64-kビットは自由に選択でき、一般的である。
【００３７】
するとNは、次式のように書き直すことができる。
N = Bm - B + n0 = Bm - n0’ここで、n0’= B - n0
【００３８】
Rを１ワード分低減されるべき結果であるとする。
【００３９】
R = rm Bm + rm-1 Bn-1 + … r1B + r0
【００４０】
その結果Rから積rm Nを減算することにより、次のように低減する。
R’= R - rm N
= rm Bm + rm-1 Bm-1 + … r1B + r0 - rm(Bm - B + n0)
= rm-1 Bm-1 + … + r2B2 + r1B + r0 + rm(B - n0) =  (R - rm Bm) + rm.n0’
【００４１】
これは、低減のためには、ワードrmを省き、最下位ワードr0に積rmn0’を加算することを意味する。この低減では、通常m回の乗算を行う代わりに、乗算を１回だけ行えばよいことを意味する。
【００４２】
n0 < B より、n0’は常に正である。結果もまた常に正である。
【００４３】
n0の代わりに、n0’を格納して使用する。
【００４４】
場合によっては、結果が1ビット分余計に大きなものになる。その場合、再度Nを減算する必要がある。
【００４５】
R’= (Bm + rm-1 Bm-1 + … + r1B + r0) - (Bm - n0’) = rm-1 Bm-1 + … + r1B + (r0 + n0’) = (R - Bm) + n0’
【００４６】
すると、オーバーフロービットBm を捨て、n0’を加算しさえすればよいことになる。
【００４７】
すべての乗算に対して１ワードずつ、このような低減を行う。あるいは、最初にすべての乗算を行い、それから低減を行う。後者の方法をここで説明する。下記に示す例は、１９２ビットECCと６４ビットワードサイズ(m=3)の例である。
【００４８】
N = B3 - B + n0 = B3 - n0’ここで、29 ≦ n0 < B  (B = 264)
【００４９】
Rは、６４ビットワード３つ分と、同じく６４ビットワード３つ分との乗算の結果であり、結果６ワード(r0…r5)が生じる。
【００５０】
低減は次のように行われる。
・n0’とr4との積にr1を加える（ステップS1）。
・n0’とr5との積に、r2と、前の乗算でのキャリーcとを加える。更に、r3が乗算の上位部分に加えられる。その結果は、下位半分が再度r2となり、上位半分がqとなる（ステップS2）。
・n0’とqとの積にr0を加え、上位部分に新しいr1を加える（ステップS3）。
・直近の乗算でオーバーフローが生じたら、そのオーバーフローは、例えば、（０とするために）n0’と０との積がr2に加算される。r1の加算（下位半分としてr1を与える）とr2の上位部分（即ちオーバーフロービット）への加算を行う（ステップS4）。
・この演算でもオーバーフローが生じるなら（もっとも、r2がすべて１からなる場合（確率2-64）のみだが）、n0’が加算される（ステップS5）。
・これは、n0’に１を掛け、r0を下位半分に、r1を上位半分にそれぞれ加えることによりなされる。
【００５１】
２番目の乗算におけるキャリー(q)は、次回の乗算における被乗数として使用され、１ビット分拡張されることができる。
【００５２】
積n0’qへの入力r1が、先導する８つの１を持たないなら（その確率は、２５６分の１未満である）、オーバーフローは発生しない。というのも、n0’の存在によりn0’qは少なくとも８つの先導する０を持つからである。その場合、プログラムはオーバーフローが処理されるのを待つことはない。
【００５３】
オーバーフローの処理には時間を要するので、できるだけ最小にしなければならない。従って、n0はたくさんの先導する１を持ち（例えばその個数をk個とおく）、そして、n0’は少なくともk-1個の先導する０を持つ。
【００５４】
こうして、qは１ビット分拡張されてよいため、積n0’c2は少なくともk-2個の先導する０を持つ。
【００５５】
オーバーフローを発生させるためには、B.c0 + r0の加算が少なくともk-2個の先導する１と下位ビットからのキャリーcを持っていなければならない。
【００５６】
これが起きる確率は2-(k-2)未満である。そこでkを大きくすると、オーバフローが発生する確率はとても小さくなる。
【００５７】
r2は完全に１からなるため、２番目のオーバフローの確率は極度に小さい(2-64)。
【００５８】
実際、パイプライン化された乗算器は効率的な計算演算を提供するために用いられ、多数の乗算が同時に処理されている。その乗算器から結果を得るには数クロックサイクルしか消費しない。オーバーフローが生じるかを決定するために待つことが必要な場合、そのオーバーフローが計算されるまで次回の乗算は開始することができない。こうして、r1が監視され、先導する１がk-2個ない場合、今後数サイクルにわたりオーバーフローはないと判断され、次回の乗算が開始される。
【００５９】
図３は、１２８ビットECCと、６４ビットのワードサイズに対し、１２８ビットのモジュラスNを組み込む新たな実施形態を示す図である。
【００６０】
この実施形態では、
N = B2 - B + n0 = B2 - n0’; 29≦ n0 < B
【００６１】
オペランドは、正規空間内になければならない。
【００６２】
すると、低減は以下のように行われる。
・n0’とr3との積にr1を加える。また、乗算の上位部分にr2が加算される（ステップS10）。その結果は、下位半分が再びr1となり、上位半分がqとなる。
・n0’とqとの積にr0を加え、上位部分に新しいr1を加える（ステップS11）。
・直近の乗算でオーバーフローが生じたら、例えば、乗算／加算 n0’.1 + B.r1 + r0により、n0’を加算する（ステップS12）。
【００６３】
図４は、２５６ビットECCと、６４ビットのワードサイズに対し、２５６ビットの素数を組み込む新たな実施形態を示す図である。
【００６４】
この実施形態では、
N = B4 - B + n0 + B4 - n0’; 29 < n0 < B
【００６５】
オペランドは、正規空間内になければならない。
【００６６】
すると、低減は以下のように行われる。
・n0’とr5との積にr1を加える（ステップS20）。その新しい結果がr1となる。
・n0’とr6との積に、r2と、前の乗算でのキャリーcとを加える（ステップS21）。その新しい結果がr2となる。
・n0’とr7との積に、r3と、前の乗算でのキャリーcとを加える。
【００６７】
更に、その乗算の上位部分にr4が加算される（ステップS22）。その結果は、下位半分が再度r3となり、上位半分がqとなる。
・n0’とqとの積にr0を加え、上位部分に新しいr1を加える（ステップS23）。
・直近の乗算でオーバーフローが生じたら、そのオーバーフローがr2に加算される（ステップS24）。
・これが再度オーバーフローを生じさせるときは、それがr3に加算される（ステップS25）。
・それでもなおオーバーフローが生じるときは、n0’が加算される（ステップS26）。
【００６８】
３番目の乗算のキャリー(q)は、次回の乗算における被乗数として使用され、１ビット分拡張されることができる。
【００６９】
図５は、本発明のハードウェアによる実装を示し、以下の要素を含む。
・それぞれ、入力オペランドX、Y、U、Rを格納するX-、Y-、U-、そしてZ-レジスタ１０〜１３。
・出力C及びRを格納するC-及びR-レジスタ１４、１５。
・中間結果を格納するRAM１６。
・演算B.C + R = X*Y + B*U + Z + cを実行する乗算器１７。
・演算を制御し、RAMとレジスタとの間又はレジスタ同士の間の運搬を制御するステートマシン１８。
【００７０】
乗算器１７は、XとYの積を計算し、必要ならば、内部に格納された、過去のキャリーcを更に加算する。結果は２つの均等な部分に分割され、下位半分にはZが加算され、上位半分にはUが加算される。
【００７１】
C-レジスタ１４の出力はYへの入力として直接使用される（例えば、図２におけるqのように）。
【００７２】
本発明の異なる形態は、加算、減算そしてシフト演算を提供する適切なALUとシフトレジスタとを備えるマイクロプロセッサ上で稼動するソフトウェアにより実装される。
【図面の簡単な説明】
【００７３】
【図１】スマートカードにおける本発明の適用を示す図である。
【図２】１９２ビットECCと６４ビットワードの場合に対応する本発明の実施形態における低減演算の概略図である。
【図３】１２８ビットECCと６４ビットワードの場合に対応する本発明の新たな低減演算の概略図である。
【図４】２５６ビットECCと６４ビットワードの場合に対応する本発明の新たな低減演算の概略図である。
【図５】本発明のハードウェアによる実装を示す図である。
【図１】
2007520729.tif 000003
【図２】
2007520729.tif 000004
【図３】
2007520729.tif 000005
【図４】
2007520729.tif 000006
【図５】
2007520729.tif 000007
【国際調査報告】
2007520729.tif 000008
2007520729.tif 000009
2007520729.tif 000010