(57)【要約】  楕円曲線暗号における逆演算技術が、特定の不変性を備える４つの補助変数U、V、R、及びSのMSWに対する演算を利用する。
2007520728.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２つの補助変数を用いる暗号化計算における逆演算を行う方法であって、
変数をシフトし、
より大きな変数から前記変数を減算することにより低減を実行することを有する方法。
【請求項２】
これらの変数は、同じ次数である、請求項１に記載の方法。
【請求項３】
不変性が有効な状態を保つように、複数の追加的な変数を更新することを有する請求項１又は２に記載の方法。
【請求項４】
４つの補助変数UとVとRとSとを含み、不変性
|S.V - R.U| = N
S.Y = U mod N
R.Y = V mod N
が成立する、請求項１乃至３のいずれかに記載の方法。
【請求項５】
U及びVのサイズを、U = 1になるまでステップ毎に縮小することを有する請求項４に記載の方法。
【請求項６】
R.Y = 1 mod N又はR = Y-1 mod Nの演算を必要に応じて実行することを有する請求項５に記載の方法。
【請求項７】
前記変数の最上位ワードを用いて演算することを有する請求項１乃至６のいずれかに記載の方法。
【請求項８】
GF(p)における逆を提供することを有する請求項１乃至７のいずれかに記載の方法。
【請求項９】
GF(2n)における逆を提供することを有する請求項１乃至８のいずれかに記載の方法。
【請求項１０】
long型整数の割算演算に対する方法を提供することを有する請求項１乃至９のいずれかに記載の方法。
【請求項１１】
デジタルコンピュータの内部メモリに直接ロード可能なコンピュータプログラムプロダクトであって、
前記プロダクトがコンピュータ上で実行されるとき、請求項１乃至１０のいずれか１つ又は複数に記載された方法を実行するためのソフトウェアコード部分を有するプログラムプロダクト。
【請求項１２】
デジタルコンピュータの内部メモリに直接ロード可能なコンピュータプログラムであって、
前記プログラムがコンピュータ上で実行されるとき、請求項１乃至１０のいずれか１つに記載された方法を実行するためのソフトウェアコード部分を有するコンピュータプログラム。
【請求項１３】
電気信号を含む、請求項１２に記載のコンピュータプログラム用のキャリア。
【請求項１４】
請求項１１に記載のコンピュータプログラムプロダクト、請求項１２に記載のコンピュータプログラム、又は請求項１３に記載のキャリアの電子配布。
【請求項１５】
少なくとも２つの補助変数を用いる暗号化計算における逆演算を行う装置であって、
変数をシフトする手段と、
より大きな変数に対し前記変数を減算又は加算することにより低減を実行する手段とを有する装置。
【請求項１６】
これらの変数は、シフトしなければ同じ次数である、請求項１５に記載の装置。
【請求項１７】
不変性が有効な状態を保つように、複数の追加的な変数を更新する手段を有する請求項１５又は１６に記載の装置。
【請求項１８】
４つの補助変数UとVとRとSとを演算する手段を有し、不変性
|S.V - R.U| = N
S.Y = U mod N
R.Y = V mod N
が成立する、請求項１５乃至１７のいずれかに記載の装置。
【請求項１９】
U及びVのサイズを、U = 1になるまでステップ毎に縮小する手段を有する請求項１８に記載の装置。
【請求項２０】
R.Y = 1 mod N又はR = Y-1 mod Nの演算を必要に応じて実行する手段を有する請求項１９に記載の装置。
【請求項２１】
前記変数の最上位ワードを用いて演算する手段を有する請求項１５乃至２０のいずれかに記載の装置。
【請求項２２】
図１乃至図７のうちの１つ又は複数において示される対応図面を参照して説明される内容、及び／又は前記対応図面において説明される内容と実質的に同一の、暗号化計算における逆演算を行う装置。
【請求項２３】
図１乃至図７のうちの１つ又は複数において示される対応図面を参照して説明される内容、及び／又は前記対応図面において説明される内容と実質的に同一の、暗号化計算における逆演算を行う方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、逆演算を行う方法及び逆演算を行う装置に関する。
【背景技術】
【０００２】
楕円曲線暗号(ECC: Elliptic Curve Cryptography)は、GF(p)やGF(2n)における楕円曲線関係に基づく計算の使用を含み、例えば、暗号化プロセッサにおける公開鍵アルゴリズムの実装において、繰り返し実行されるlong型整数の乗算を必要とする。
【０００３】
一般に、暗号処理又は復号処理を完了するには、何百回となく乗算演算が行われなければならない。そして、これらの演算を行う暗号化デバイスは、高速の乗算器を用いてlong型の乗算を高速に実行する。
【０００４】
ECCの計算は、逆計算もまた必要とする。逆計算とは、即ち、積Z.Z-1 = 1 mod NとなるようなZ-1を計算することである。点追加(point addition)計算や点二重(point doubling)計算毎にもこのような計算を必要とする。現在のアルゴリズムは、計算が強烈である。
【０００５】
別の方法は、いわゆる射影空間で機能する。これは、逆計算を最後に回し、１度だけ行われるようにするが、そのトレードオフとして、乗算の回数が大変増加する。
【０００６】
次第に、このような暗号アルゴリズムは、例えばスマートカードのような、アプリケーション処理能力や消費電力に厳しい制限が課される電子デバイスにおいて使用されるようになっている。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
従来の計算法の１つとしては、補助変数の組と共に機能するバイナリGCDシステムがある。１つの組は、偶数の場合２で割ることにより、奇数の場合減算を行うことにより、サイズが低減される。
【０００８】
しかしながら、GCDシステムではしばしば、モジュラスの半分を追加して、他の組に関する演算を修正する必要がある。
【０００９】
別の従来の計算法としては、補助変数の２つの組をここでも用いるKaliskiシステムがある。１つの組は、偶数の場合２で割ることにより、奇数の場合減算を行うことにより、低減される。
【００１０】
しかしながら、このシステムでは、いかなる必要な修正も第２段へ遅延される。
【００１１】
そこで、本発明の目的は、より効率的な逆演算を提供することにある。
【００１２】
また、本発明の目的は、より少ない演算で逆を求めるプロセスを提供することにある。
【００１３】
また、本発明の目的は、従来のシステムよりも速く完了する逆演算を提供することにある。
【課題を解決するための手段】
【００１４】
１つの側面によれば、本発明は、少なくとも２つの補助変数を用いる暗号化計算における逆演算を行う方法であって、変数をシフトし、より大きな変数からその変数を減算することにより低減を実行する方法を提供する。
【００１５】
本発明の１つの利点は、ほとんどの演算が補助変数の最上位ワードに関してのみ行われることである。このような計算を複数回実行した後、多数の乗算が完全な補助変数に対して行われ、それはより単純である。
【００１６】
これらの利点は、従来の方法に比べ、必要な演算の数が低減されるという結果をもたらす。それにより、演算はより高速に実行される。
【００１７】
こうして、本発明により与えられる重要な利点は、全体の計算演算を完了するのにかかる時間が短縮されることである。
【００１８】
更に、本発明の方法により提供される安全度は、既存の暗号化法と比較しても、同程度が維持される。
【００１９】
好ましくは、その方法は４つの補助変数U、V、R、Sを含み、不変性として次が成立する。
|S.V - R.U| = N
S.Y = U mod N
R.Y = V mod N
【００２０】
好ましくは、その方法は、それらの変数の最上位ワードに関して演算する。
【００２１】
こうして、本発明の利点は、計算演算がより速く実行されることにある。
【００２２】
別の側面によれば、本発明は、デジタルコンピュータの内部メモリに直接ロード可能なコンピュータプログラムプロダクトであって、そのプロダクトがコンピュータ上で実行されるとき、本発明の方法を実行するためのソフトウェアコード部分を含むことを特徴とするプログラムプロダクトを提供する。
【００２３】
別の側面によれば、本発明は、デジタルコンピュータの内部メモリに直接ロード可能なコンピュータプログラムであって、そのプログラムがコンピュータ上で実行されるとき、本発明の方法を実行するためのソフトウェアコード部分を有することを特徴とするプログラムを提供する。
【００２４】
別の側面によれば、本発明は、電気信号を含む、本発明を具体化するコンピュータプログラムのキャリアを提供する。
【００２５】
別の側面によれば、本発明は、本発明のコンピュータプログラムプロダクト、又はコンピュータプログラム、又はキャリアの電子配布を提供する。
【００２６】
別の側面によれば、本発明は、少なくとも２つの補助変数を用いる暗号化計算における逆演算を行う装置であって、変数をシフトする手段と、より大きな変数に対しその変数を減算又は加算することにより低減を実行する手段とを含む装置を提供する。
【００２７】
本発明の方法及び装置は、GF(p)、GF(2n)における計算及びlong型整数の割算にも適用することができる。
【発明を実施するための最良の形態】
【００２８】
以下、本発明が容易に理解されるように、実施例に過ぎないものを介し、対応する図面を参照しながら、説明が与えられる。
【００２９】
図１は、スマートカード５０を搭載する本発明のハードウェアによる実装のブロック図を示す図であり、以下の要素を含む。
・一般的な制御のため、インタフェースを介して外部世界と通信を行うマイクロコントローラ５１。それは、RAM／ROMのデータへのポインタをセットし、コプロセッサを起動する。
・例えばISO-7816-3などに基づきスマートカードと通信するための、外部世界へのインタフェース。
・マイクロコントローラのプログラム用のリードオンリメモリ(ROM)５２。
・データ又はプログラム用の不揮発性ストレージであるプログラム可能リードオンリメモリ(フラッシュ又はEEPROM)５３。
・揮発データ、例えば、計算中の中間結果を格納するストレージであるRAM５４。
・ECCやRSAの計算用の特別な高速タスクを実行する専用のコプロセッサ５５。タスクが実行可能(ready)にされると、制御がマイクロコントローラに戻される。
【００３０】
変形例では、マイクロプロセッサと、制御論理を与えるコントローラのプログラミングに用いる、加算、減算、シフト演算を与えるALUと、シフトレジスタ２による次数検出とにより、本発明はソフトウェアで実装される。
【００３１】
以下、本発明における逆演算を説明する図eが示される。
【００３２】
GF(p)における本計算方法は、４つの補助変数U、V、R、Sを用い、演算
R = Y-1 mod N
を含む。ただし、
U = Y
V = N
S = 1
R = 0
であり、 UとVは常に正である。
【００３３】
補助変数の次数は、それを表現するために必要なビット数である。例えば、U = 111100である場合、
Uの次数 dUは６である。
【００３４】
そして、もしV = 001110なら、
Vの次数dVは４である。
【００３５】
演算は、
B = dU - dV（ステップS1）
とし、b < 0なら、次の演算（ステップS2、S3）を行う。即ち、
(swap U,V)
(swap R,S)
(swap dU,dV)
b = -b
それから、U = U - 2b.V
S = S - Sb.R
そして、もしU < 0なら、
（ステップS4）U = -U
S = -S、
もしR < 0なら、そのときはR = R + N
もしR > Nなら、そのときはR = R - N.
こうして、次の不変性が各ループ繰り返しの後でも保たれる。
gcd(U,V) = gcd(Y,N)
SY = U mod N
RY = V mod N
|SV - RU| = N.
【００３６】
各ステップにおいて、Uの次数は減少されるか、Vの次数に一致する。そこでUとVは徐々に小さくなり、最後のステップで
Uは0になる(U = 2bV)。
【００３７】
U = 0なので、不変性 gcd(U,V) = gcd(Y,N)は、YとNとは互いに素であることも考慮すれば、V = gcd(Y,N) = 1を意味する。
【００３８】
すると、RY = 1 mod NかR = Y-1 mod Nが成立する。
【００３９】
U = 0のとき、-N < R < 2Nであり、高々１つの修正ステップ、即ち、Nの加算又は減算を与える。
【００４０】
実際は、Rは常にNより小さいようであり、Nの減算は決して起こらない。
【００４１】
また、一時的に|SV| < 2Nと|RU| < 2Nが成立する。
【００４２】
それらはすべて整数なので、
|S| < 2N;
|V| < 2N;
|R| < 2N;
|U| < 2N.
【００４３】
これらの変数に対して、それらを表現するにはNより１ビット余分に必要である。SとRとに対しては、符号ビットもまた必要になる。
【００４４】
図２は、本発明の方法のハードウェアによる実装を示す。
【００４５】
レジスタ１０、１１、１２、１３は、変数U、V、S、Rを保持する。加算器１４、１５は、加算、減算、反転及びmod 2の加算を行う。VとRとは、bビット分シフトされることができる。制御論理１６は、プロセスを制御する。２つの次数検出器１７、１８があり、１つはU用、もう１つはV用である。d減算器１９は、差(b)を与える。
【００４６】
最初に、YがUに、NがVにロードされ、Sは１に、Rは０にセットされる。
【００４７】
そしてプロセスが開始される。
【００４８】
b < 0のとき、UとVとはその内容を交換する。SとRも同様に交換する。そしてbは反転される。
【００４９】
加算器は減算にセットされ、シフタはbビット分シフトするようセットされる。それから、減算が行われる。Uが負であるとき、加算器はUとSとを両方反転するようセットされる。
【００５０】
このプロセスは、U≠0である限り行われる。
【００５１】
U = 0かつR
< 0又はR > Nであるとき、SにはNがロードされる。そして、R + N又はR - Nのいずれかが計算される。
【００５２】
通常、オペランドは多数のワードからなる。しかし、変形例においては、不変性が有効に保たれるようにしながら、２つの変数の最上位ワードのみと、それぞれが１ワード分のサイズの４つの補助変数とを使用することにより計算が高速化される。それは、チップ面積も電力も節約する。その結果は、全体のオペランドに対するその後の計算の推定器として使用される。
【００５３】
図３は、より詳細なハードウェア実装を示す。レジスタ３０〜３５は、それぞれ１ワード分の容量を持ち、UH、VH、uu、uv、vu及びvvを保持する。
【００５４】
UHとVHには、最初にU及びVの最上位ワードがロードされる。
【００５５】
U = uu.U0 - uv.V0
V = vu.U0 - vv.V0
S = uu.S0 - uv.R0
R = vu.S0 - vv.R0
【００５６】
uu、uv、vu、vvは、都合のよい大きさのワードである。
【００５７】
演算は、uu = 1、vv = -1、uv = vu = 0で開始する。
U0 = Y;
V0 = N;
S0 = 1;
R0 = 0.
【００５８】
その等式が、数回ステップを経た後もまだ成立すると仮定する。次回の計算の後でも、その等式はまだ成立する。最初から等式が成立するので、それは正しいままである。
【００５９】
U’= U - 2bVとS’= S - 2bRを計算するとき、以下のように選択する。
uu’= uu - 2bvu
uv’= uv - 2bvv
vu’= vu
vv’= vv.
【００６０】
U’= U + 2bVとS’= S + 2bRを計算する必要があるとき、以下のように選択する。
uu’= uu + 2bvu
uv’= uv + 2bvv
vu’= vu
vv’- vv.
【００６１】
必要なときは、uuとvuとを、uvとvvとをそれぞれ入れ替える。
【００６２】
この入れ替えは、RとSとについてと同様に、UとVとについても行われる。
【００６３】
オペランドを更新するには、UHにUのMSWをロードし、VHにVのMSWをロードして開始する。すると、
uu = 1、vv = -1、uv = vu = 0.
【００６４】
そうして多数の計算が行われると、ワードのサイズに依存する量及び有効なビット数が残される。
【００６５】
VHはシフトされるので、（未知の）右側ビットの代わりに０が補充される。そして、UH及びVHは徐々に小さくなっていく。ほとんどビットが残されていないとき、その演算は停止される。符号の決定もまた正確ではなくなる。
【００６６】
それからuu…vvとU0…S0を用いて、U、V、S、Rを計算する。
【００６７】
これは、U及びVの新たな低減された値を与え、それはなお不変性に従う。
【００６８】
U0をUに、V0をVにセットする。S0とR0も同様にセットする。またuu = 1、vv = -1、uv = vu = 0にセットする。
【００６９】
そして、手続きを繰り返す。毎回、UH及びVHレジスタにUとVとがフィットするまで、それらが小さくなっていく。
【００７０】
すると、その計算はもはや推定ではなく、正確な計算となる。そして、正確な結果と共に終了する。最後にRだけはY-1を見つけるために再計算されなければならない。
【００７１】
図１から４の方法の変形例として、UとVとに対する負の値を許容し、Uが負であるとき修正ステップを省略する計算方法がある（図５参照）。
【００７２】
正数の次数は、先導するゼロをすべて取り除いた後のビット数であり、負数の次数は、先導する１をすべて取り除いた後のビット数である。
【００７３】
繰り返すが、U≠0であれば、補助変数は、
U = Y;
V = N;
S = 1;
R = 0;
であり、b < 0なら、
{swap(U,V); swap(R,S) swap(dU,dV); b = -b};
を実行し、Sign(U) = Sign(V)なら、
{ U = U - 2b.V; S = S -2b.R; }
又は
{ U = U + 2b.V; S = S +2b.R; }
dU = degree(U);
を実行し、R < 0なら、R = R + Nを実行し、
R > N なら、R = R - Nを実行する。
【００７４】
図６は、GF(2n)における計算法である第２の実施形態を示す。主な差異点は：
αがU、V、S、及びRの多項式の変数であること；
Nが既約多項式であること；
負の値が１つもなく、mod 2の加算だけなので、アルゴリズムがより単純化されていることである。
【００７５】
こうして、
U = Y;
V = N;
S = 1;
R = 0;
で開始し、U > 0であれば、
b = dU - dV
を求め、b < 0なら、
2007520728.tif 000003
を実行し、R > Nなら
2007520728.tif 000004
を実行する。
【００７６】
こうして、最初にYがUに、NがVにロードされ、Sが１に、Rが０にセットされる。
【００７７】
そして、プロセスが開始される（ステップS10〜S12）。
【００７８】
b < 0のとき、UとVはその内容を交換し、SとRも同様に交換する。そしてbは反転される。
【００７９】
加算器は両方ともmod 2の加算を処理するようセットされる。シフタは、bビット分のシフトを行うようセットされる。それから加算が行われる。
【００８０】
プロセスは、U≠0である限り行われる。
【００８１】
U = 0かつR
> Nなら、SにはNがロードされ、そして
2007520728.tif 000005
が計算される。
【００８２】
図７は、long型の整数の割算に対する計算法である第３の実施形態を示す。主な差異点は：
最初に、XがUに、YがVにロードされ、Sが０に、Rが１にセットされることである。
【００８３】
U > 0のとき、UV加算器は減算にセットされ、RS加算器は加算にセットされる。適切な場合には、その逆が行われてもよい。シフタは、bビット分のシフトを行うようセットされる。それから加算／減算の演算が行われる。
【００８４】
プロセスは、U≠0かつb≧0である限り行われる。
【００８５】
プロセスが実行可能であり、U < 0のとき、bは０にセットされる。それから１回の加算／減算が行われる(U = U + V; S = S - R)。
【００８６】
すると、0 ≦ R’＜ Yとし、X = Q.Y + R’と表現するときの、Uは残りR’であり、Sは商Qである。
【図面の簡単な説明】
【００８７】
【図１】スマートカードに対する本発明の適用を示すブロック図である。
【図２】本発明の実施形態における逆演算の概略図である。
【図３】本発明のハードウェアによる実装を示す図である。
【図４】本発明のハードウェアによる実装を更に詳細に示す図である。
【図５】本発明の別の逆演算を示す概略図である。
【図６】本発明の別の逆演算を示す概略図である。
【図７】本発明の更なる演算を示す概略図である。
【図１】
2007520728.tif 000006
【図２】
2007520728.tif 000007
【図３】
2007520728.tif 000008
【図４】
2007520728.tif 000009
【図５】
2007520728.tif 000010
【図６】
2007520728.tif 000011
【図７】
2007520728.tif 000012
【国際調査報告】
2007520728.tif 000013
2007520728.tif 000014
2007520728.tif 000015
2007520728.tif 000016
2007520728.tif 000017