(57)【要約】    【課題】  コブリッツ曲線を用いたスカラー倍計算装置において、メモリ使用量、及び、高速性に優れた楕円曲線スカラー倍計算装置を提供することにある。  【解決手段】  スカラー値、及び、コブリッツ曲線上の点からスカラー倍点を計算するスカラー倍計算装置において、スカラー値を数値列にエンコードし、上記数値列から0でない数を一つ選択し、上記エンコードした数値列の各桁を見て、上記選択した数と一致する桁で楕円曲線上の加算を実行し、上記選択した数と一致しない桁で楕円曲線上の第二の演算を実行することによって、メモリ使用量、及び、高速演算可能なスカラー倍計算装置が利用可能である。    【選択図】図１
2006235416.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線上の加算とは異なる第二の演算を実行することができる楕円曲線を用いて、スカラー値と前記楕円曲線上の点とからスカラー倍点を計算する楕円曲線暗号におけるスカラー倍計算装置であって、
前記スカラー値を数値列にエンコードするステップと、
前記数値列から0でない数を一つ選択するステップと、
前記選択した数と同じ絶対値をもつ桁において，前記スカラー倍点を求める演算を行うステップと，
0でなく，かつ，前記数値列を構成する数について，前記選択するステップと前記演算を行うステップを繰り返すステップと、
を実行する
ことを特徴とするスカラー倍計算装置。
【請求項２】
請求項１に記載のスカラー倍計算装置であって、
前記エンコードするステップを実行するエンコード部と，
前記選択するステップと，前記計算するステップとを実行する実計算部と，からなる
ことを特徴とするスカラー倍計算装置。
【請求項３】
請求項１に記載のスカラー倍計算装置であって、
前記楕円曲線はコブリッツ曲線であるスカラー倍計算装置。
【請求項４】
請求項１に記載のスカラー倍計算方法であって、
前記第二の演算はτ倍算であるスカラー倍計算装置。
【請求項５】
請求項２に記載のスカラー倍計算装置であって、
実計算部は、さらに、基底変換するステップを実行する
ことを特徴とするスカラー倍計算装置。
【請求項６】
請求項１に記載のスカラー倍計算装置であって、
前記数値列から0でない数を一つ選択するステップは、
前記数値列の各桁を構成する0以外でかつ未選択の数から数を1つ選択し、前記選択した数に対応する前計算を実行することにより前計算点を求め、前記前計算点をあらかじめ定められた前計算テーブルに格納する第一のステップからなり、
前記スカラー倍点を求める演算を行うステップは、
前記数値列の、前記選択した数と同じ絶対値を持つ数を持つ桁がある場合に，当該桁になるまで，前記前計算テーブルに格納されている前記前計算点に対して前記楕円曲線上の第二の演算を実行し、その結果を前記前計算テーブルの前記前計算点に上書きする第二のステップと、
前記数値列の、前記選択した数と同じ絶対値を持つ桁において，前記前計算テーブルに格納されている前記前計算点を利用して前記楕円曲線上の加算を実行する第三のステップと、
第二、第三のステップを繰り返す第四のステップと，からなり、
前記選択するステップと前記計算ステップを繰り返すステップは、
前記数値列の各桁を構成する0以外の未選択の数がある場合に，
前記第一から前記第四のステップを繰り返す第五のステップからなる
ことを特徴とするスカラー倍計算装置。
【請求項７】
請求項１に記載のスカラー倍計算装置であって、
前記エンコードするステップは、さらに、前記スカラー値dに対するΦｗ 関数の値を
計算するステップを含み、
前記Φｗ 関数は、Φｗ (d) = (dR+dT*tw mods 2w)で与えられる
ことを特徴とするスカラー倍計算装置。
【請求項８】
データから署名データを生成する署名部と、前記署名データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する署名生成装置であって、
前記スカラー倍計算部は、請求項１に記載のスカラー倍計算装置を用いて，前記スカラー倍点を計算するステップを実行する
ことを特徴とする署名生成装置。
【請求項９】
データと署名データとから署名検証結果を出力する署名検証部と、前記署名検証結果を作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する署名検証装置であって、
前記スカラー倍計算部は、請求項１に記載のスカラー倍計算装置を用いて，前記スカラー倍点を計算するステップを実行する
ことを特徴とする署名検証装置。
【請求項１０】
データから暗号化データを生成する暗号部と、前記暗号化データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する暗号化装置であって、
前記スカラー倍計算部は、請求項１に記載のスカラー倍計算装置を用いて，前記スカラー倍点を計算するステップを実行する
ことを特徴とする暗号化装置。
【請求項１１】
暗号化データから復号化データを生成する復号部と、前記復号化データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する復号化装置であって、
前記スカラー倍計算部は、請求項１に記載のスカラー倍計算装置を用いて，前記スカラー倍点を計算するステップを実行する
ことを特徴とする復号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はセキュリティ技術に係り、特に楕円曲線演算を用いたメッセージ処理方法に関する。
【背景技術】
【０００２】
情報通信ネットワークの進展と共に電子情報に対する秘匿や認証の為に暗号技術は不可欠な要素となってきている。暗号技術に課せられる要件としては、安全性以外にも、処理速度や少ないメモリ使用量などがあるが、一般的に安全性、処理速度、メモリ使用量の間にはトレードオフの関係があり、全ての要件をみたすことは難しい。
【０００３】
暗号技術には，共通鍵暗号と公開鍵暗号があるが、公開鍵暗号の一種にN. Koblitz, V. S. Millerにより提案された、楕円曲線暗号がある。
【０００４】
楕円曲線暗号は、楕円曲線上の離散対数問題が非常に困難である為に、素因数分解の困難性を安全性の根拠にしている暗号と比べて、楕円曲線暗号は鍵長を比較的短くすることができる。
【０００５】
楕円曲線のなかで、標準化団体(例えば、NIST（National Institute of Standards and Technology）)が推奨する、暗号に適した楕円曲線は、ランダムな標数2の楕円曲線、コブリッツ曲線、及び、標数が大きな素体上の楕円曲線である。標準化団体の推奨する楕円曲線は、例えば、非特許文献１に記載されている。
【０００６】
公開鍵暗号には、公開鍵(Public Key)と呼ばれる一般に公開してよい情報と、秘密鍵(Private Key)と呼ばれる秘匿しなければならない秘密情報がある。平文メッセージの暗号化や署名の検証には公開鍵を用い、暗号文メッセージの復号化や署名の生成には秘密鍵を用いる。
【０００７】
楕円曲線暗号における秘密鍵は、後述するスカラー値が担っている。また、楕円曲線暗号の安全性は楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Pとそのスカラー倍の点d Pが与えられた時、スカラー値dを求める問題である。楕円曲線上の点とは、楕円曲線の定義方程式をみたす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法（または加算）が定義される。
【０００８】
ある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果をスカラー倍点、その回数のことをスカラー値という。そして、同じ点同士による楕円曲線上の加法のことを、特に楕円曲線上の2倍算という。楕円曲線上の2点の加法は次のようにして計算される。2点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とx軸に関して対称な点を、加法を行った結果の点とする。例えば、上記コブリッツ曲線の場合には、点(x1, y1)と点(x2 ,y2 )の加算(x3 ,y3 ) = (x1 ,y1 ) + (x2 ,y2 )は
x3 = λ2 + λ + x1 + x2 + a                              (式1)
y3 = (x1 + x3 ) λ +x3 + y1                                (式2)
λ = (y1 + y2 )/(x1 + x2 )                                （式3）
を計算することにより得られる。
【０００９】
ここで、コブリッツ曲線の定義方程式は
y2 + x y = x3 + a x2 + 1, (a = 0 or 1)                    (式4)
で与えられる。すなわち、式4のx, yに各々xi ,yi (i=1,2,3)を代入した場合に、式4の等式が成り立つ。
【００１０】
楕円曲線上の点の2倍算は次のようにして計算される。楕円曲線上の点における接線をひくと、その接線は楕円曲線上の他の一点において交わる。その交わった点とx座標に関して対称な点を、2倍算を行った結果の点とする。例えば、コブリッツ曲線の場合には、点(x1, y1)の2倍算を行った結果(x3 ,y3 ) = 2 (x1 ,y1 ) = (x1 ,y1) + (x1 ,y1 )は、式1, 式2及び
λ = (y1 /x1 ) + x1                                      （式5）
を計算することにより得られる。
【００１１】
また、コブリッツ曲線上の点に対して、τ倍算と呼ばれる処理の軽い演算を行うことが可能である。点(x1 ,y1 )に対するτ倍算とは、
(x3 ,y3 ) = τ (x1 ,y1 ) = (x1 2 ,y1 2)                    （式6）
を計算することである。また、
(x4 ,x4 ) + 2 (x, y) = μ (x2 ,y2 )                          （式7）
μ = (- 1)a                                              （式8）
が成り立つことが知られており、式7の性質によりτを、
τ2 + 2 = μ τ                                            （式9）
をみたす複素数と考えることができる。
【００１２】
コブリッツ曲線では、スカラー値dを、
d = dw [m+a-1]τm+a-1 + dw [m+a-2]τm+a-2 + … + dw [j]τj + … + dw [0]  (式10)
-2w-1 < dw [j] < 2w-1                            (式11)
と変換することができる。ここで、各iに対してdw [j]は奇数、mはスカラー値ｄを2進表記した際のビット長である。である。
【００１３】
コブリッツ曲線におけるスカラー値dを、式10、式11を満たすτ進数表現に変換することをτ進エンコード、または単にエンコードという。
【００１４】
従来，楕円曲線上の点をスカラー倍する場合は、スカラー値dを、
d = d [m]2m + d [m-1]2m - 1 + … + d [0]                            (式12)
d[i] = 0 または 1                            (式13)
の形に変換し、式12、式13を用いてスカラー倍計算を行っている。したがって、桁をずらす際に比較的処理の重い楕円曲線上の2倍算を用いる必要がある。
【００１５】
これに対し、コブリッツ曲線上の点のスカラー倍では、スカラー値dを、式10の形に変換し、式10を用いてスカラー倍計算を行う。したがって、桁をずらす際にτ倍算を用いることによって、コブリッツ曲線上の点を高速にスカラー倍できる高速演算方法TNAFw が知られている。
【００１６】
楕円曲線暗号においては、与えられたメッセージの暗号化、復号化、署名の生成またはその検証は、楕円曲線演算を用いて行う必要がある。特に楕円曲線上のスカラー倍の計算は、秘密情報であるスカラー値を用いた暗号処理において用いられる。
【００１７】
コブリッツ曲線におけるスカラー倍の高速計算手法TNAFw (式10、及び、式11)の詳細が、非特許文献２に記載されている。多項式基底、及び、正規基底については、例えば、非特許文献２に記載されている。また、τ倍算のような性質を持つフロベニウス写像を有する楕円曲線が非特許文献３に記載されている。
【００１８】
【非特許文献１】D. Johnson, A. Menezes, “The Elliptic Curve Digital Signature Algorithm (ECDSA)”, Technial Report CORR 99-34, Dept. of C&O, University of Waterloo, Canada.<URL>http://www.cacr.math.uwaterloo.ca/techreports/1999/corr99-34.pdf
【非特許文献２】J.A.Solinas, “Efficient Arithmetic on Koblitz Curves”, Designs, Codes and Cryptography, 19, Kluwer Academic Publishers (2000), pp.195-249.
【非特許文献３】R. P. Gallant, J. L. Lambert, and S. A. Vanstone “Faster Point Multiplication on Elliptic Curves with Efficient Endomorphisms”, In J. Kilian, editor, Advances in Cryptology  Proceedings of CRYPTO 2001, volume 2139 of Lecture Notes in Computer Science, 190-200. Springer, 2001.
【発明の開示】
【発明が解決しようとする課題】
【００１９】
上述のように楕円曲線暗号を用いれば、計算能力、メモリ容量などのリソースが比較的少なくても暗号処理を行うことが可能である。しかしながら、、一般の計算機に比べ、スマートカード(ICカードともいう)等において利用可能なリソースはさらに少なく、限られたリソース内で暗号処理を最適化する必要がある。
【００２０】
また、署名検証や鍵交換では、スカラー倍計算の直前に受け取った点のスカラー倍算を行う必要があり、例えば非特許文献２のスカラー倍計算高速化技術TNAFw を用いるとスカラー倍計算の前に前計算テーブルを作成する必要がある。
【００２１】
そのため、非特許文献２に記載のスカラー倍計算高速化技術TNAFw では、メモリ使用量が非常に大きくなるため、使用可能なメモリが制限された場合には適用することが難しい。ここで、事前計算テーブルは、式11を満たすjに対し、点j Pからなる。
【課題を解決するための手段】
【００２２】
本発明は、標準化団体(例えば、NIST)が推奨するコブリッツ曲線を用い、スカラー値を数値列にエンコードし、上記数値列から0でない数を一つ選択し、上記エンコードした数値列の各桁を見て上記選択した数と一致する桁で楕円曲線上の加算を実行し、上記選択した数と一致しない桁で楕円曲線上の第二の演算を実行することによって、メモリ使用量、及び、高速演算可能な楕円曲線演算装置を提供する。
【００２３】
本発明は更に、上記楕円曲線演算方法を用いた、暗号化処理装置、復号化処理装置、署名生成装置、署名検証装置、データ共有装置を提供する。
【００２４】
ここで、エンコードとはスカラー値として用いられるような大きな整数(2の160ビット程度)から小さな数の列に変換する操作であり、この小さな数の列を数値列という。
【００２５】
従来技術を用いたスカラー倍計算方法と本発明によるスカラー倍計算方法との違いを図15に記載する。
【００２６】
図１５(a)に記す従来技術を用いたスカラー倍計算方法では、
（１）スカラー値dをエンコードする。
（２）点Pの情報から点３Pを計算する。前計算テーブルは、R1 = P、R2 = ３Pからなる。
（３）点Qを格納するメモリを無限遠点と呼ぶ仮想的な点Oで初期化する。ただし，点Qに用いるメモリはワーク領域であり、前計算テーブルとして用いられるメモリとは異なる。エンコード結果の数値列の各桁を順に調べ，式11のdw [j] が0でない桁になるまで、桁をずらすために点Qに対するτ倍算を行う。このとき点Qの内容は上書きする。
（４）dw [j]が0でない桁において，その数値（図15（ａ）では，1または3）に応じて，楕円曲線上の加算を行う。加算を行う際に，事前に計算した結果を格納している前計算テーブルを用いる。その数値が1の場合は、R1に格納されているPを読み出し、点Qとの加算を行う。その結果を再び点Qに格納する。
【００２７】
同様に、その数値が3の場合は、R2に格納されている3Pを読み出し、点Pとの加算を行う。その結果を再び点Qに格納する。
【００２８】
一方、その数が-1の場合は、R1に格納されているPを読み出し、-Pを求め、点Qと-Pとの加算を行う。その結果を再び点Qに格納する。
【００２９】
同様に、その数値が-3の場合は、R2に格納されている3Pを読み出し、-3Pを求め、点Qと-3Pとの加算を行う。その結果を再び点Qに格納する。
【００３０】
尚、Pから-P、3Pから-3Pを求める計算は、楕円曲線の性質により高速に行うことが可能である。
（５）上記（３）（４）を数値列の全桁（式10の0 〜 m+a-1）を対象に繰り返す。
【００３１】
これに対し，図１５（b）に記す本発明によるスカラー倍計算方法では、
（１）数値列からdw [j]が0でない数(これをuとする)を選択し(図１５（ｂ）では、まず１を選択している)、前計算テーブルを点R = u Pで初期化する(図１５（ｂ）では、まずR = Pで初期化している)。ただし、点Qに用いるメモリはワーク領域であり、前計算テーブルとして用いられるメモリとは異なる。
（２）選択した数が現れる桁になるまで桁をずらすために点Rに対するτ倍算を行う。これより前計算テーブルに格納されている点Rは上書きされる。
（３）選択した数が現れたら，点Rと点Qの加算を行い、その結果を点Qに格納する。
（４）上記（２），（３）を数値列の全桁（式10の0 〜 m+a-1）を対象に繰り返し，
（５）上記（１）〜（４）を式11の-2w-1 < dw [j] < 2w-1を満たす奇数すべてについて繰り返す。
【００３２】
以上のとおり、本発明によれば、点Rに対する計算結果を更新しつつ格納するメモリがあればよく，前計算テーブルは楕円曲線上の１点分で済む。
【００３３】
図１５（ａ）（ｂ）の例では、簡単のためw = 3の場合として説明しているが、図１５(a)に示す従来技術を製品に実装する際は、通常、w = 5 もしくはw = 6を選択するため、前計算テーブルには楕円曲線上の１６個の点または３２個の点を格納する必要がある。
【００３４】
そのため，例えば点1個を格納するために必要なメモリ領域が50バイト程度の場合、従来技術における前計算テーブルのサイズが800バイト程度必要となるのに対し、本発明における前計算テーブルのサイズは50バイト程度で済むことになる。
【００３５】
以上の通りであるから，従来技術を用いてスカラー倍計算を行う場合、前計算テーブルに格納する点の情報は、通常１６個または３２個必要となるのに対し、本発明によれば、前計算テーブルにはコブリッツ曲線上の一点の情報を格納し、その内容を上書きしていくことによってスカラー倍計算を行うため、前計算テーブルのサイズは１／１６または１／３２となる。したがって、メモリ使用量に優れた高速計算可能なスカラー倍計算装置を提供可能になる。
【００３６】
より具体的な本発明の一態様は，楕円曲線上の加算とは異なる第二の演算を実行することができる楕円曲線を用いて、スカラー値と上記楕円曲線上の点とからスカラー倍点を計算する楕円曲線暗号におけるスカラー倍計算装置であって、上記スカラー値を数値列にエンコードするステップと、上記数値列から0でない数を一つ選択するステップと、上記選択した数と同じ絶対値をもつ桁において，上記スカラー倍点を求める演算を行うステップと，0でなく，かつ，上記数値列を構成する数について，上記選択するステップと上記演算を行うステップを繰り返すステップと、を実行することを特徴とする。
【００３７】
さらに，上記スカラー倍計算装置は，上記エンコードするステップを実行するエンコード部と，上記選択するステップと，上記計算するステップとを実行する実計算部と，からなるものであってもよい。
【００３８】
さらに，上記楕円曲線はコブリッツ曲線であってもよい。
【００３９】
さらに，上記第二の演算はτ倍算であってもよい。
【００４０】
さらに，上記実計算部は、さらに、基底変換するステップを実行するものであってもよい。
【００４１】
さらに，上記数値列から0でない数を一つ選択するステップは、上記数値列の各桁を構成する0以外でかつ未選択の数から数を1つ選択し、上記選択した数に対応する前計算を実行することにより前計算点を求め、上記前計算点をあらかじめ定められた前計算テーブルに格納する第一のステップからなり、上記スカラー倍点を求める演算を行うステップは、上記数値列の、上記選択した数と同じ絶対値を持つ数を持つ桁がある場合に，当該桁になるまで，上記前計算テーブルに格納されている上記前計算点に対して上記楕円曲線上の第二の演算を実行し、その結果を上記前計算テーブルの上記前計算点に上書きする第二のステップと、上記数値列の、上記選択した数と同じ絶対値を持つ桁において，上記前計算テーブルに格納されている上記前計算点を利用して上記楕円曲線上の加算を実行する第三のステップと、第二、第三のステップを繰り返す第四のステップと，からなり、上記数値列の各桁を構成する0以外の未選択の数がある場合に，上記第一から上記第四のステップを繰り返す第五のステップからなるものであってもよい。
【００４２】
さらに，上記エンコードするステップは、さらに、Φｗ (d) = (dR+dT*tw mods 2w)で与えられる，上記スカラー値dに対するΦｗ 関数の値を計算するステップを含むものであってもよい。なお、Φｗ 関数とは，大きな整数を小さな数の列にエンコードするステップにおいて、上記数列の各項を計算する際に用いられる関数であり，その詳細は非特許文献２に記載されている。
【００４３】
また，本発明の他の態様は，データから署名データを生成する署名部と、上記署名データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する署名生成装置であって、
上記スカラー倍計算部は、上記スカラー倍計算装置を用いて，上記スカラー倍点を計算するステップを実行することを特徴とする。
【００４４】
また，本発明の他の態様は，データと署名データとから署名検証結果を出力する署名検証部と、上記署名検証結果を作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する署名検証装置であって、上記スカラー倍計算部は、上記スカラー倍計算装置を用いて，上記スカラー倍点を計算するステップを実行することを特徴とする。
【００４５】
また，本発明の他の態様は，データから暗号化データを生成する暗号部と、上記暗号化データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する暗号化装置であって、上記スカラー倍計算部は、上記スカラー倍計算装置を用いて，上記スカラー倍点を計算するステップを実行することを特徴とする。
【００４６】
また，本発明の他の態様は，暗号化データから復号化データを生成する復号部と、上記復号化データを作成するために必要なスカラー倍点を計算するスカラー倍計算部と、を有する復号化装置であって、上記スカラー倍計算部は、上記スカラー倍計算装置を用いて，上記スカラー倍点を計算するステップを実行することを特徴とする。
【発明の効果】
【００４７】
本発明によれば、メモリ使用量が少なく，かつ，高速計算可能なスカラー倍演算装置を実現することができる。
【発明を実施するための最良の形態】
【００４８】
以下、本発明の実施例を図面により説明する。
【００４９】
図1はネットワーク142によって接続された本実施形態による楕円曲線演算方法を適用したコンピュータＡ101、コンピュータＢ121がネットワーク142により接続されたシステム構成を示すものである。図1の暗号通信システムにおけるコンピュータＡ101でメッセ―ジの暗号化を行うには、Pm + k (d Q)及びk Qを計算して出力し、コンピュータＢ121で暗号文の復号化を行うには、秘密鍵d及びk Qより-d (k Q)を計算し、
(Pm + k (d Q))-d (k Q)                    (式14)
を計算して出力すればよい。
【００５０】
ここでPm はメッセージ、kは乱数、dは秘密鍵を示す定数、Qは定点、d Qは公開鍵を示す点である。ネットワーク142には、Pm + k (d Q), kQのみ送信され、メッセージPm を復元するためには、k d Q、すなわちk Qのd倍を計算する必要がある。ところが、秘密鍵dはネットワーク142には送信されないため、秘密鍵dを保持しているものだけが、Pm を復元できることになる。
【００５１】
図1において、コンピュータＡ101は、ＣＰＵ113やコプロセッサ114などの演算装置、ＲＡＭ103、ＲＯＭ106や外部記憶装置107などの記憶装置、コンピュータ外部とのデータ入出力を行う入出力インタフェース110を装備しており、外部にはコンピュータＡ101をユーザが操作するためのディスプレイ108、キーボード109、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
【００５２】
更にコンピュータＡ101は、ＲＡＭ103、ＲＯＭ106や外部記憶装置107などの記憶装置によって、記憶部102を実現し、ＣＰＵ113やコプロセッサ114などの演算装置が、記憶部102に格納されたプログラムを実行することにより、データ処理部112、スカラー倍計算部115とそれらに含まれる各処理部を実現する。データ処理部112は、本実施形態においては、暗号化処理部112として機能し、入力されたメッセージの暗号化を行う。
【００５３】
スカラー倍計算部115は、暗号処理部112で暗号化を行うのに必要なパラメタを計算する。記憶部102は、定数104（例えば、楕円曲線の定義式や楕円曲線上の定点である）、秘密情報105（例えば、秘密鍵である）などを記憶している。コンピュータＢ121は、コンピュータＡ101と同様のハードウェア構成を備える。
【００５４】
更にコンピュータＢ121は、ＲＡＭ123、ＲＯＭ126や外部記憶装置127などの記憶装置によって、記憶部122を実現し、ＣＰＵ133やコプロセッサ134などの演算装置が、記憶部122に格納されたプログラムを実行することにより、データ処理部132、スカラー倍計算部135とそれらに含まれる各処理部を実現する。データ処理部132は、本実施形態においては、復号化処理部132として機能し、暗号化されたメッセージである暗号文141の復号化を行う。
【００５５】
スカラー倍計算部135は、復号化処理部132で復号化を行うのに必要なパラメタを計算する。記憶部122は、定数124（例えば、楕円曲線の定義式や楕円曲線上の定点である）、秘密情報125（例えば、秘密鍵である。）などを記憶している。なお、上記各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていても良いし、必要なときに、入出力インタフェース110もしくは130と上記コンピュータA101もしくはB121が利用可能な媒体を介して、他の装置から上記記憶部に導入されてもよい。媒体とは、たとえば、入出力インタフェース110もしくは130に着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波やディジタル信号）を指す。
【００５６】
図2は、コンピュータＡ101、コンピュータＢ121の各処理部が行う情報の受け渡しの様子を示したものである。
【００５７】
次に、図1のコンピュータＡ101が、入力されたメッセージを暗号化する場合の動作について説明する。なお、本明細書におけるメッセージとはディジタル化されたデータであれば良く、テキスト、画像、映像、音などの種類は問わない。暗号化処理部112は、入出力インタフェース110を介して、平文メッセージ(図2の入力メッセージ204)を受け取ると、入力された平文メッセージのビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるように平文メッセージを区切る。
【００５８】
以下、所定のビット長に区切られている部分メッセージ(単にメッセージともいう)について説明する。暗号化処理部112は、メッセージのビット列によって表される数値をx座標(x1 )にもつ楕円曲線上の点Pm のy座標の値(y1 )を計算する。コブリッツ曲線は式4で表わされるので、これよりy座標の値を求めることができる。
【００５９】
次に、暗号化処理部112は、乱数kを生成する。そして、記憶部102に格納されている定数104から読み出した(図2の205)公開鍵d QとQのx座標と、求めたy座標の値と乱数kとをスカラー倍計算部115へ送る(図2の206)。スカラー倍計算部115は、Qのx座標、y座標の値、乱数kによるスカラー倍点(xd1 ,yd1 ) = k Qと、公開鍵d Qのx座標、y座標の値、乱数によるスカラー倍点(xd2 ,yd2 ) = k (d Q)とを計算し、計算されたスカラー倍点を暗号化処理部112へ送る(図2の207)。
【００６０】
暗号化処理部112は、送られたスカラー倍点を用いて、暗号化処理を行う。例えば、コブリッツ曲線では、k QとPm + k (d Q)を計算する。すなわち、
xe1 = xd1                                            (式15)
xe2 = λ2 + λ + x1 + xd2 + a                    (式16)
λ = (y1 + yd2 )/(x1 + xd2 )                        （式17）
を計算し、暗号化されたメッセージxe1 ,xe2 を得る。
【００６１】
コンピュータＡ101は暗号化処理部112で暗号化された1つ以上の部分メッセージから暗号化された出力メッセージを組み立てる(図2の208)。
コンピュータＡ101は、暗号化された出力メッセージをデータ141として入出力インタフェース110より出力し、ネットワーク142を介してコンピュータＢ121へ転送する。
なお、図2の記憶部102からの情報読み出しは、スカラー計算部115へ当該情報を送る前で有れば、入力メッセージを受け付ける前であっても良い。
【００６２】
次に、コンピュータＢ121が、暗号化されたメッセージ141を復号化する場合の動作について、図2を参照しつつ説明する。
【００６３】
復号化処理部132(図2のデータ処理部112)は、入出力インタフェース130を介して、暗号化されたデータ141(図2の入力メッセージ204）が入力されると、入力された暗号化されたデータ141のビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるように暗号化されたデータを区切る。
【００６４】
以下、所定のビット長に区切られている部分データ（単にデータともいう）について説明する。データ141のビット列によって表される数値をx座標にもつ楕円曲線上のy座標の値を計算する。暗号化されたメッセージがxe1 ,xe2 のビット列であり、コブリッツ曲線ではy座標の値ye1 ,ye2 は
ye1 2 + xe1 ye1 = xe1 3 + a xe1 2 + 1,(a = 0 or 1)                    (式18)
ye2 2 + xe2 ye2 = xe2 3 + a xe2 2 + 1,(a = 0 or 1)                    (式19)
から得ることができる。
【００６５】
復号化処理部132は、記憶部122(図2の102)に格納されている秘密情報125から読み出した(図2の205)秘密鍵dと、x座標、y座標の値(xe1 ,ye1 )を、スカラー倍計算部135(図2の115)へ送る(図2の206)。スカラー倍計算部135は、x座標、y座標の値、秘密情報dからスカラー倍点(xd3 ,yd3 ) = d(xe1 ,ye1 )を計算する。スカラー倍計算部135は、計算されたスカラー倍点を復号化処理部132へ送る(図2の207)。
【００６６】
復号化処理部132は、送られたスカラー倍点を用いて、復号化処理を行う。例えば、暗号化されたメッセージが、xe1 ,xe2 のビット列であり、コブリッツ曲線では、(Pm + k (d Q))  d (k Q) = (xe2 ,ye2 ) - (xd3 ,yd3 )を計算することにより達成する。すなわち、
xf1 = λ2 + λ + xe2 + xd3 + a                    (式20)
λ = (ye2 + yd3 )/(xe2 + xd3 )                      （式21）
を計算し、暗号化される前の部分メッセージx1に相当するxf1 を得る。
【００６７】
コンピュータＢ121は、復号化処理部132で復号化された部分メッセージから平文メッセージを組み立て(図2の208)、入出力インタフェース130を介して、ディスプレイ128などから出力する。
【００６８】
以上のように、暗号化処理や復号化処理では、スカラー倍計算を行う必要がある。
【００６９】
次に、コンピュータA101が、暗号化処理を行う場合やコンピュータB121が、復号化処理を行う場合の、スカラー倍計算部115の処理を詳細に説明する。
【実施例１】
【００７０】
実施例1では、図3で示されるスカラー倍計算部115の機能ブロックを用いる。スカラー倍計算部115(図1の135)は、エンコード部302、実計算部303からなる。エンコード部302は、剰余取得部321、剰余変換部322、繰り返し判定部323、δ剰余変換部324、Φw 関数計算部325、格納部326からなる。実計算部303は、ビット値判定部331、加算部332、τ倍算部333、繰り返し判定部334からなる。
【００７１】
スカラー倍計算部115がスカラー値d、及び、楕円曲線上の点Pから、楕円曲線におけるスカラー倍点d Pを計算する第１の計算方法を説明する。第1の計算方法では、前計算テーブルを用いずにスカラー倍計算を行えるという特徴がある。そのため、スカラー倍計算の直前に受け取った点のスカラー倍計算では、前計算テーブルを用いることなく、直接、スカラー倍点が計算できる。したがって、前計算テーブルを格納するメモリを節約することができる。スカラー倍計算部115が復号化処理部132からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード部302は、入力されたスカラー値dを数値列dw [j]にエンコードする。
【００７２】
これは、
d P = d' P                                    (式22)
をみたす整数d'に対して、
d' = dw [m+a-1]τm+a-1 + dw [m+a-2]τm+a-2 + … + dw [j]τj + … + dw [0]        (式23)
-2w-1 < dw [j] < 2w-1                            (式24)
をみたすdw [j]に、スカラー値dを変換することに相当する。ただし、スカラー値dを数値列dw [j]にエンコードするには、スカラー値dをτw で割った余りをdw [j]とし、この操作を繰り返す。その詳細な計算方法については、非特許文献２に記載されている。
【００７３】
ここで、mはスカラー値d'を2進表記した場合のビット長であり、wはあらかじめ定めた小さな自然数で、ウィンドウ幅と呼ばれる。本実施例では、w = 4、点Pは正規基底で表わされているものとする。
【００７４】
実計算部303は、数値列dw [j]を用いてスカラー倍点d Pを計算する。
【００７５】
次にエンコード部302、実計算部303の行う各処理について詳細に説明する。
【００７６】
図4を用いて、エンコード部302がスカラー値dをエンコードする方法を説明する。
【００７７】
δ剰余変換部324は、変数d'にd modδを、β|u| にc0 を、γ|u| にc1 をそれぞれ代入する(401)。ただし、δとスカラー値dに対してd modδの計算方法については非特許文献２に記載されている。
【００７８】
ここで、δは
δ = (τm  1)/(τ - 1)                            (式25)
で表わされる数であり、
d modδは、
d' = d - kδ                                (式26)
d' = c0 + c1 τ                              (式27)
なる形で表される。ここで、k,c0 ,c1 はすべて整数である。
【００７９】
d modδをエンコードすると、その数値列の長さはスカラー値dをエンコードした数値列の長さより短くなることが知られている。すなわち、コブリッツ曲線のスカラー倍計算における加算、及び、τ倍算の回数を減らすことにより、スカラー倍計算の高速化が図ることが可能になる。
【００８０】
変数iを0で初期化し、j0 、j1 、…、j2 w-1 -1 にそれぞれ0を代入する(402)。
【００８１】
繰り返し判定部323は、c0 ≠ 0またはc1 ≠ 0であるかどうかを判定する。この2つの条件のうち、どちらか一方が成立すれば、ステップ411へ行く。2つの条件のいずれも成立しない場合、ステップ421へ行く(403)。
【００８２】
ステップ403でいずれかの条件が成立する場合、uにc0 + tw * c1 mods 2w を代入する(411)。
【００８３】
繰り返し判定部323は、uが奇数であるかどうかを判定する。条件が成立する場合、ステップ413へ行く。条件が成立しない場合、ステップ415へ行く(412)。
【００８４】
ステップ412で条件が成立する場合、dw [u][ju ]にsign(u) * iを、ju にju + 1をそれぞれ代入する(413)。
【００８５】
c0 にc0 - sign(u) * β|u| を、c1 にc1 - sign(u) * γ|u| をそれぞれ代入する(414)。
【００８６】
iにi + 1、tにc0 を、c0 にc1 + μc0 /2を、c1 に- t/2を、それぞれ代入し、ステップ403へ行く(415)。
【００８７】
dw [0][j0 ]、…、dw [2w-1 -1][ j2 w-1 -1 ]のそれぞれに， Ωをそれぞれ代入する(421)。ここで、Ωは終端を表わす記号である。  例えば、Ωとして、
Ω = 2L
とすることが可能である。ここで、Lは、2m < 2L を満たす整数である。
Ω = 2L とおくと、Ωのバイナリ表現は、最上位ビットのみが1であり、本実施例の実装が行いやすくなる。
【００８８】
エンコード部302は、dw [0]、…、dw [j2 w-1 -1]を実計算部303へ出力する(422)。
【００８９】
次に図5を用いて、実計算部303がエンコードされたスカラー値、楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。
【００９０】
w = 4の場合、各iに対してdw [i] は、± 1、±3、±5、± 7である。
【００９１】
Q、R、u、dw [u]を入力し、Rを(u mod τw )P、jを0、kを0でそれぞれ初期化する(501)。
【００９２】
iに| dw[u][j] |を、Rにτj-k Rを、kにiをそれぞれ代入する(511)。
ここで、数xに対して、| x |はxの絶対値を表わす数である。
【００９３】
繰り返し判定部334は、dw [u][j] > 0であるかどうかを判定する。条件が成立すれば、ステップ513へ行く。条件が成立しない場合、ステップ514へ行く(512)。
【００９４】
加算部332は、点Qと点Rを加算し、その結果をQに格納する(513)。
【００９５】
加算部332は、点Qと点- Rを加算し、その結果をQに格納する(514)。
【００９６】
ｊにj + 1を代入する(515)。
【００９７】
繰り返し判定部334は、dw [u][j] ≠Ωであるかどうかを判定する。条件が成立すれば、ステップ511へ行く。条件が成立しない場合、ステップ521へ行く(516)。
【００９８】
実計算部302は、点Qを出力する(521)。
【００９９】
ステップ501からステップ521までの計算をi=0からi=3まで繰り返す。
【０１００】
エンコード部302が行う処理により出力されるdw [j]は、式22、式23、式24をみたす。この理由は、以下のとおりである。  ステップ401で、d'にd modδを代入している。そのため、d' = d + kδと適当な数kを用いて表わすことができる。他方、コブリッツ曲線上では、点δPは無限遠点となることが知られており、そのため式22が成立する。
【０１０１】
式23が成立する理由は、スカラー値dをτ4 で割った余りをd4 [j]とし、この操作を繰り返すからである。
【０１０２】
また、τ4 で割った余りをd4 [j]とし、この操作を繰り返すと、d4 [j]は
- 8 = -24-1 < d4 [j] < 24-1 = 8
を満たすため、式24が成立する。
【０１０３】
実計算部303が出力する点Qはスカラー倍点d Pに等しい。この理由は次の通りである。d'は、
d' = Σi,j sign(dw [u[i]][j])τ| dw [u[i]] |                            (式28)
と変形できる。このとき、
d'P = (Σi,j sign(dw [u[i]][j])τ| dw [u[i]] | (P))                      (式29)
であり、各iに対して、Σj sign(dw [u[i]][j])τ| dw [u[i]] | (P)は、図5で計算されている。したがって、点QはQ = d Pを満たす。
【０１０４】
スカラー倍計算部115は前計算部を具備する必要がない。この理由は次の通りである。図5において、i回目の計算が終了した時点で、
Q = Σj sign(dw [u[0]][j])τ| dw [u[0]] | (P) + … + Σj sign(dw [u[i - 1]][j])τ| dw [u[i-1]] | (P)              (式30)
であり、(i + 1)回目の計算のステップ501において、Rに(u[i] mod τ4 ) Pを代入するときに、a = 0の場合、
(u[0] mod τ4 ) P = P                                    (式31)
(u[1] mod τ4 ) P = -τ P - 3 P                          (式32)
(u[2] mod τ4 ) P = -τ P - P                            (式33)
(u[3] mod τ4 ) P = -τ P + P                            (式34)
a = 1の場合、
(u[0] mod τ4 ) P = P                                    (式35)
(u[1] mod τ4 ) P =τ P - 3 P                          (式36)
(u[2] mod τ4 ) P =τ P - P                            (式37)
(u[3] mod τ4 ) P =τ P + P                            (式38)
を計算する。したがって、点Pだけ格納されていればよく、点(u[i + 1] mod τ4 ) Pは点(u[i] mod τ4 ) Pから計算し、値を上書きすればよいので、前計算テーブルを必要とせず，メモリを節約できる。
【０１０５】
また、本実施例におけるスカラー倍計算は高速性に優れる。これは、次の通りである。スカラー倍計算の直前に受け取った点に関するTNAF4 を用いたスカラー倍計算において、必要な計算コストは、
{(m + a)/5 + 3} * ECADD + {(m + a)/5 + 3} * ECFRB                    (式39)
となり、通常のTNAF4 を用いたスカラー倍計算において、必要な計算コストと同等である。ただし、ECADD、ECFRBはそれぞれ、楕円曲線上の加算、τ倍算を表わす。つまり、式35はスカラー計算において、各楕円演算の回数の総和を表わしている。
【０１０６】
非特許文献２に記載のスカラー倍計算における計算コストは、
{(m + a)/5 + 3} * ECADD + {(m + a)/5 + 2} * ECFRB                    (式40)
である。したがって、通常のTNAF4 を用いたスカラー倍計算と同等の高速性を持ち、かつ、メモリ使用量に優れている。
【０１０７】
また、本実施例におけるスカラー倍計算では、各iに対して、jをランダムな順に並べることができる。ただし、dw [u[i]][j]は、スカラー値dをエンコードしたときの桁がj番目にu[i]または- u[i]となる数である。各iに対して、jをランダムな順に並べたとき、この順でスカラー倍計算を行うと、スカラー倍計算のランダム化を図ることができる。
【０１０８】
また、本実施例におけるスカラー倍計算方法は、非特許文献３に記載の楕円曲線やフロベニウス写像をもつ楕円曲線に対しても適用することができる。
【０１０９】
以上の通り、上記計算方法は、楕円曲線上の加算とは異なる第二の演算を有する楕円曲線に対し、メモリ使用量、及び、高速性に優れるという特徴がある。
【実施例２】
【０１１０】
実施例2では、図3で示されるスカラー倍計算部115の機能ブロックを用いる。スカラー倍計算部115(図1の135)は、実施例1と同様である。
【０１１１】
スカラー倍計算部115がスカラー値d、及び、楕円曲線上の点Pから、楕円曲線におけるスカラー倍点d Pを計算する第2の計算方法を説明する。第2の計算方法では、任意のウィンドウ幅wに対してスカラー倍計算を行うことができるという特徴がある。ここでは、ウィンドウ幅wの値として、w = 5を用いて説明する。なお、実施例1と同様に、スカラー倍計算の直前に受け取った点のスカラー倍計算では、前計算テーブルを用いることなく、直接、スカラー倍点が計算できるので，メモリを節約できる。スカラー倍計算部115が復号化処理部132からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード部302は、入力されたスカラー値dを数値列dw [j]にエンコードする。
これは、式22を満たす整数d'に対して、式23、式24を満たすdw [j]に、スカラー値dを変換することに相当する。
【０１１２】
本実施例では、点Pは正規基底で表わされているものとする。
【０１１３】
実計算部303は、数値列dw [j]を用いてスカラー倍点d Pを計算する。
【０１１４】
次にエンコード部302、実計算部303の行う各処理について詳細に説明する。
【０１１５】
エンコード部302がスカラー値dをエンコードする方法は実施例1と同様である。
【０１１６】
次に図5、図6を用いて、エンコードされたスカラー値、楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。
【０１１７】
w = 5の場合、u[0] = 1、u[1] = 3、u[2] = 11、u[3] = 15、u[4] = 5、u[5] = 13、u[6] = 7、u[7] = 9とする。
【０１１８】
実計算部303は、点P、及び、スカラー値dを受け取ると、u[0] = 1、u[3] = 15、u[5] = 13、u[7] = 9の場合、図5を用いて、点Qを計算し、u[1] = 3、u[2] = 11、u[4] = 5、u[6] = 7の場合、図6を用いて、点Q、Rを計算する。図5の処理は実施例1と同様である。
【０１１９】
Q、R、u、dw [u]を入力し、Rを(u mod τw ) P、jを0、kを0でそれぞれ初期化する(601)。
【０１２０】
iに| dw [u][j] |を、Rにτj-k Rを、kにiをそれぞれ代入する(611)。
【０１２１】
繰り返し判定部334は、dw [u][j] > 0であるかどうかを判定する。条件が成立すれば、ステップ613へ行く。条件が成立しない場合、ステップ614へ行く(612)。
【０１２２】
加算部332は、点Qと点Rを加算し、その結果をQに格納する(613)。
【０１２３】
加算部332は、点Qと点- Rを加算し、その結果をQに格納する(614)。
【０１２４】
ｊにj + 1を代入する(615)。
【０１２５】
繰り返し判定部334は、 dw [u][j] ≠Ωであるかどうかを判定する。条件が成立すれば、ステップ611へ行く。条件が成立しない場合、ステップ621へ行く(616)。
【０１２６】
Rにτm-k Rを代入して、実計算部302は、点Q、Rを出力する(621)。
エンコード部302が行う処理により出力されるdw [j]は、式22、式23、式24をみたす。この理由は、次の通りである。
【０１２７】
式22が成立する理由は実施例1と同様である。
【０１２８】
式23が成立する理由は、スカラー値dをτ5 で割った余りをd5 [j]とし、この操作を繰り返すからである。
【０１２９】
また、τ5 で割った余りをd5 [j]とし、この操作を繰り返すと、d5 [j]は
- 16 = -25-1 < d5 [j] < 25-1 = 16
を満たすため、式24が成立する。
【０１３０】
実計算部303が出力する点Qはスカラー倍点d Pに等しい。この理由は次の通りである。d'は、
d' = Σi,j sign(dw [u[i]][j])τ| dw [u[i]] |                            (式41)
と変形できる。このとき、
d'P = (Σi,j sign(dw [u[i]][j])τ| dw [u[i]] | (P))                      (式42)
であり、各iに対して、Σj sign(dw [u[i]][j])τ| dw [u[i]] | (P)は、図5、または、図6で計算されている。したがって、点QはQ = d Pを満たす。
【０１３１】
スカラー倍計算部115は前計算部を具備する必要がない。この理由は次の通りである。図5、または、図6において、i回目の計算が終了した時点で、
Q = Σj sign(dw [u[0]][j])τ| dw [u[0]] | (P) + … + Σj sign(dw [u[i-1]][j])τ| dw [u[i-1]] | (P)  (式43)
であり、(i + 1)回目のステップ501、または、ステップ601において、
Rに(u[i] mod τ5 ) Pを代入するときに、a = 0の場合、
(u[0] mod τ5 ) P = P                                                  (式44)
(u[1] mod τ5 ) P = τ2 P - P                                          (式45)
(u[2] mod τ5 ) P = τ3 P + (u[1] mod τ5 ) P                          (式46)
(u[3] mod τ5 ) P = τ P - (u[2] mod τ5 ) P                            (式47)
(u[4] mod τ5 ) P = -τ P - P                                          (式48)
(u[5] mod τ5 ) P = -τ2 (u[4] mod τ5 ) P + P                          (式49)
(u[6] mod τ5 ) P = -τ P + P                                          (式50)
(u[7] mod τ5 ) P = -τ4 P - (u[6] mod τ5 ) P                          (式51)
a = 1の場合、
(u[0] mod τ5 ) P = P                                                  (式52)
(u[1] mod τ5 ) P = τ2 P - P                                          (式53)
(u[2] mod τ5 ) P = -τ3 P + (u[1] mod τ5 ) P                          (式54)
(u[3] mod τ5 ) P = -τ P - (u[2] mod τ5 ) P                          (式55)
(u[4] mod τ5 ) P = τ P - P                                            (式56)
(u[5] mod τ5 ) P = -τ2 (u[4] mod τ5 ) P + P                          (式57)
(u[6] mod τ5 ) P = τ P + P                                            (式58)
(u[7] mod τ5 ) P = -τ4 P - (u[6] mod τ5 ) P                          (式59)
を計算する。したがって、点Pだけ格納されていればよく、点(u[i + 1] mod τ5 ) Pは点(u[i] mod τ5 ) Pから計算し、値を上書きすればよいので、前計算テーブルを必要とせず，メモリを節約できる。
【０１３２】
実施例1では、図5、実施例2では、図5、図6を用いてスカラー倍計算を行う理由は次の通りである。
【０１３３】
実施例1は、(u[i] mod τ5 ) Pはすべて点Pを用いて計算を行っているのに対し、第2実施例では、(u[i] mod τ5 ) Pは、i = 0,1,4,6の場合は点Pを用いて計算を行い、i = 2,3,5,7の場合は、(u[i-1] mod τ5 ) Pを用いて計算を行う。これより、(u[i] mod τ5 ) Pの計算を行う際に、(u[i-1] mod τ5 )Pを用いるときは、ステップ621で
R = (u[i-1] mod τ5 ) P                                (式60)
としておかなければならない。したがって、実施例2では、図5、図6を用いてスカラー倍計算を行う。
【０１３４】
また、本実施例におけるスカラー倍計算は高速性に優れる。これは、次の通りである。スカラー倍計算の直前に受け取った点に関するTNAF5 を用いたスカラー倍計算において、必要な計算コストは、
{(m + a)/6 + 7} * ECADD + {(m + a)/6 + 7} * ECFRB                    (式61)
となる。非特許文献２に記載のスカラー倍計算における計算コストは、
{(m + a)/6 + 7} * ECADD + {(m + a)/6 + 4} * ECFRB                    (式62)
である。通常のTNAF5 を用いたスカラー倍計算において、必要な計算コストと同等である。したがって、通常のTNAF5 を用いたスカラー倍計算と同等の高速性を持ち、かつ、メモリ使用量に優れている。
【０１３５】
また、本実施例におけるスカラー倍計算では、各iに対して、jをランダムな順に並べることができる。ただし、dw [u[i]][j]は、スカラー値dをエンコードしたときの桁がj番目にu[i]または- u[i]となる数である。各iに対して、jをランダムな順に並べたとき、この順でスカラー倍計算を行うと、スカラー倍計算のランダム化を図ることができることは実施例1と同様である。
【０１３６】
また、実施例1と同様に、本実施例におけるスカラー倍計算方法は、非特許文献３に記載の楕円曲線やフロベニウス写像をもつ楕円曲線に対しても適用することができる。
【０１３７】
以上の通り、上記計算方法は、楕円曲線上の加算とは異なる第二の演算を有する楕円曲線に対し、メモリ使用量、及び、高速性に優れるという特徴がある。
【実施例３】
【０１３８】
実施例3では、図7で示されるスカラー倍計算部115の機能ブロックを用いる。スカラー倍計算部115(図1の135)は、エンコード部702、実計算部703からなる。エンコード部702は、剰余取得部721、剰余変換部722、繰り返し判定部723、δ剰余変換部724、Φw 関数計算部725、格納部726からなる。実計算部703は、ビット値判定部731、加算部732、τ倍算部733、繰り返し判定部734、基底変換部735からなる。
【０１３９】
スカラー倍計算部115がスカラー値d、及び、楕円曲線上の点Pから、楕円曲線におけるスカラー倍点d Pを計算する第3の計算方法を説明する。第3の計算方法では、任意の基底を用いて点Pを表現することができる。そのため、スカラー倍計算では、点Pの座標の表現に用いる基底を正規基底に限定する必要はない。ここでは、多項式基底を用いて説明する。
【０１４０】
なお、実施例1、及び、実施例2と同様に、スカラー倍計算の直前に受け取った点のスカラー倍計算では、前計算テーブルを用いることなく、直接、スカラー倍点が計算できる。スカラー倍計算部115が復号化処理部132からスカラー値dと楕円曲線上の点Pを受け取ると、エンコード部702は、入力されたスカラー値dを数値列dw [j]にエンコードする。
【０１４１】
スカラー値dを数値列dw [j]にエンコードする計算方法については、実施例と同様であり，その詳細は，非特許文献２に記載されている。
【０１４２】
本実施例では、w = 4、点Pは多項式基底で表わされているものとする。
【０１４３】
実計算部703は、数値列dw [j]を用いてスカラー倍点d Pを計算する。
【０１４４】
次にエンコード部702、実計算部703の行う各処理について説明する。
【０１４５】
エンコード部702がスカラー値dをエンコードする方法は、実施例1、及び、実施例2と同様である。
【０１４６】
次に、図8を用いて、実計算部703がエンコードされたスカラー値、及び、楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。
【０１４７】
Q、u、Rp 、dw [u]を入力し、Rp を(u[i] mod τw ) P、jを0、kを0でそれぞれ初期化し、基底変換部735は、点Rの多項式基底表現Rp を正規基底表現Rn に変換する(801)。
【０１４８】
iに| dw[u][j] |を、Rn にτj-k Rn を、kにiをそれぞれ代入し、点Rの正規基底表現Rn を多項式基底表現Rp に変換する(811)。
【０１４９】
繰り返し判定部734は、dw [u][j] > 0であるかどうかを判定する。条件が成立すれば、ステップ813へ行く。条件が成立しない場合、ステップ814へ行く(812)。
【０１５０】
加算部732は、点Qと点Rp を加算し、その結果をQに格納する(813)。
【０１５１】
加算部732は、点Qと点-Rp を加算し、その結果をQに格納する(814)。
【０１５２】
ｊにj + 1を代入する(815)。
【０１５３】
繰り返し判定部734は、dw [u][j] ≠Ωであるかどうかを判定する。条件が成立すれば、ステップ811へ行く。条件が成立しない場合、ステップ821へ行く(816)。
【０１５４】
実計算部703は、点Qを出力する(821)。
ステップ801からステップ821までの計算をi=0からi=3まで繰り返す。
【０１５５】
エンコード部702が行う処理により出力されるdw [j]は、式22、式23、式24をみたす。この理由は、実施例1と同様である。
【０１５６】
実計算部703が出力する点Qはスカラー倍点d Pに等しい。この理由は実施例1、及び、実施例2と同様である。
【０１５７】
スカラー倍計算部115は前計算部を具備する必要がない。この理由も実施例1、及び、実施例2と同様である。
【０１５８】
また、本実施例におけるスカラー倍計算は高速性に優れる。これは、次の通りである。スカラー倍計算の直前に受け取った点に関するTNAF4 を用いたスカラー倍計算において、必要な計算コストは、
{(m + a)/5 + 3} * ECADD + {(m + a)/5 + 7} * ECFRB + {(m + a)/5 + 4} COB    (式63)
となる。
非特許文献２に記載のスカラー倍計算における計算コストは、
{(m + a)/5 + 3} * ECADD + {(m + a) + 3} * ECFRB                    (式64)
である。
通常のTNAF4 を用いたスカラー倍計算において、必要な計算コストと同等である。ただし、COBは基底変換を表わす。したがって、通常のTNAF4 を用いたスカラー倍計算と同等の高速性を持ち、かつ、メモリ使用量に優れている。ここで、計算コストとは、スカラー倍計算に必要な演算(例えば、楕円曲線上の加算やτ倍算)の総数のことである。
【０１５９】
なお、実施例2、及び、実施例3を組み合わせることによって、スカラー倍計算の直前に受け取った点のスカラー倍計算では、任意のウィンドウ幅w、及び、任意の基底を用いて、前計算テーブルを用いることなく、直接、スカラー倍点を計算することが可能である。この場合、スカラー倍計算では、図8、及び、図9を用いる。この理由は、実施例2と同様である。
【０１６０】
また、本実施例におけるスカラー倍計算では、各iに対して、jをランダムな順に並べることができる。ただし、dw [u[i]][j]は、スカラー値dをエンコードしたときの桁がj番目にu[i]または- u[i]となる数である。各iに対して、jをランダムな順に並べたとき、この順でスカラー倍計算を行うと、スカラー倍計算のランダム化を図ることができることは、実施例1、及び、実施例2と同様である。
【０１６１】
また、非特許文献２に記載されているように、正規基底、及び、多項式基底は、列ベクトルを、基底変換は行列を，それぞれ用いて表わされる。
【０１６２】
ステップ811において、Rn にτj-k Rn を代入する処理は、上記列ベクトルのシフト演算、また点Rの正規基底表現Rn を多項式基底表現Rp に変換する処理は、上記列ベクトルと上記行列の積である。したがって、本実施例を実装の際、上記基底変換処理における列ベクトルと上記行列の積の計算では、列ベクトルの第一項から計算を開始するのではなく、上記シフト演算後に第一項となる項から計算を開始するように実装することによって、Rn にτj-k Rn を代入するシフト演算処理を省略することができる。これにより更なる高速化を図ってもよい。
【０１６３】
また、実施例1、及び、実施例2と同様に、本実施例におけるスカラー倍計算方法は、非特許文献３に記載の楕円曲線やフロベニウス写像をもつ楕円曲線に対しても適用することができる。
【０１６４】
以上の通り、上記計算方法は、楕円曲線上の加算とは異なる第二の演算を有する楕円曲線に対し、メモリ使用量、及び、高速性に優れるという特徴がある。
【実施例４】
【０１６５】
実施例では、図10で示されるスカラー倍計算部115の機能ブロックを用いる。スカラー倍計算部115(図1の135)は、実計算部1002からなる。実計算部1002は、剰余取得部1021、剰余変換部1022、繰り返し判定部1023、δ剰余変換部1024、Φw 関数計算部1025、ビット値判定部1031、加算部1032、τ倍算部1033からなる。
【０１６６】
スカラー倍計算部115がスカラー値d、及び、楕円曲線上の点Pから、楕円曲線におけるスカラー倍点dPを計算する第4の計算方法を説明する。第4の計算方法では、スカラー値をエンコードすることなく、直接スカラー倍計算を行えるという特徴を持つ。そのため、実計算部1002はエンコード部を具備する必要がない。なお、実施例1、実施例2、及び、実施例3と同様に、前計算テーブルを用いずにスカラー倍計算を行えるという特徴がある。そのため、スカラー倍計算の直前に受け取った点のスカラー倍計算では、前計算テーブルを用いることなく、直接、スカラー倍点が計算できる。したがって、前計算テーブルを格納するメモリを節約することができる。本実施例では、w = 4、点Pは正規基底で表わされているものとする。
【０１６７】
次に、実計算部1002の行う各処理について詳細に説明する。
【０１６８】
図11を用いて、実計算部1002がスカラー値、楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。
【０１６９】
点P,スカラー値dを入力する(1101)。
【０１７０】
dw [0]、…、dw [2w-1 - 1]にTNAFw (d modδ)を代入する(1102)。
【０１７１】
Qを無限遠点O、iを0で初期化する(1103)。
【０１７２】
繰り返し判定部1023は、i < 2w-1 であるかどうかを判定する。条件が成立すれば、ステップ1111へ行く。条件が成立しない場合、ステップ1121へ行く(1104)。
【０１７３】
vにu[i]を、Rに(v modτw ) Pを、QにQ + Σj sign(dw [v][j])*τ| dw[v][j] | Rをそれぞれ代入する(1111)。
【０１７４】
iにi + 1を代入し、ステップ1104へ行く(1112)。
【０１７５】
実計算部1002は、点Qを出力する(1121)。
【０１７６】
実施例2、及び、実施例4を組み合わせることによって、スカラー倍計算の直前に受け取った点のスカラー倍計算では、任意のウィンドウ幅wで、前計算テーブルを用いることなく、直接、スカラー倍点を計算することが可能である。この理由は、実施例1から実施例3と同様である。
【０１７７】
また、実施例3、及び、実施例4を組み合わせることによって、スカラー倍計算の直前に受け取った点のスカラー倍計算では、任意のウィンドウ幅w、任意の基底を用いて点Pを表現することによって、前計算テーブルを用いることなく、直接、スカラー倍点が計算できる。これは次の通りである。
【０１７８】
ここでは、図12で示されるスカラー倍計算部115の機能ブロックを用いる。スカラー倍計算部115(図1の135)は、実計算部1202からなる。実計算部1202は、剰余取得部1221、剰余変換部1222、繰り返し判定部1223、δ剰余変換部1224、Φw 関数計算部1225、ビット値判定部1231、加算部1232、τ倍算部1233、基底変換部1234からなる。
【０１７９】
図13を用いて、実計算部1202がスカラー値、楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。
【０１８０】
点P,スカラー値dを入力し、Qを無限遠点O、iを0で初期化する(1301)。
【０１８１】
繰り返し判定部1223は、i < 2w-1 であるかどうかを判定する。条件が成立すれば、ステップ1311へ行く。条件が成立しない場合、ステップ1351へ行く(1302)。
【０１８２】
Rに(u[i] modτw )Pを、c0 + c1 τにd modδを、jに0を、kに0をそれぞれ代入する(1311)。
【０１８３】
繰り返し判定部1223は、c0 ≠0またはc1 ≠0であるかどうかを判定する。この2つの条件のうち、どちらか一方が成立すれば、ステップ1313へ行く。2つの条件がいずれも成立しない場合、ステップ1341へ行く(1312)。
【０１８４】
ステップ1312でいずれかの条件が成立する場合、vにc0 + tw * c1 mods 2w を代入し、ステップ1314へ行く(1313)。
【０１８５】
繰り返し判定部1223は、|v| = u[i]であるかどうかを判定する。条件が成立する場合、ステップ1321へ行く。条件が成立しない場合、ステップ1325へ行く(1314)。
【０１８６】
Rにτj-k Rを、kにjをそれぞれ代入する(1321)。
【０１８７】
繰り返し判定部1223は、v > 0かどうかを判定する。条件が成立する場合、ステップ1323へ行く。条件が成立しない場合、ステップ1324へ行く(1322)。
【０１８８】
加算部1232は、点Qと点Rを加算し、その結果をQに格納する(1323)。
【０１８９】
加算部1232は、点Qと点-Rを加算し、その結果をQに格納する(1324)。
【０１９０】
繰り返し判定部1223は、vが奇数かどうかを判定する。条件が成立する場合、ステップ1331へ行く。条件が成立しない場合、ステップ1332へ行く(1325)。
【０１９１】
c0 にc0 - sign(v) * β|v| を、c1 にc1 - sign(v) * γ|v| をそれぞれ代入する(1331)。
【０１９２】
jにj + 1を、tにc0 、c0 にc1 + μc0 /2を、c1 に- t/2をそれぞれ代入する(1332)。
【０１９３】
iにi + 1を、Rにτm-k Rを、それぞれ代入し、ステップ1302へ行く(1341)。
【０１９４】
実計算部1202は、点Qを出力する(1351)。
【０１９５】
実計算部1202が出力する点Qはスカラー倍点d Pに等しい。この理由は、実施例1、実施例2、及び、実施例3と同様である。
【０１９６】
スカラー倍計算部115は前計算部を具備する必要がない。この理由も実施例1、実施例2、及び、実施例3と同様である。
また、本実施例におけるスカラー倍計算は高速性に優れる。この理由も実施例1、実施例2、及び、実施例3と同様である。
【０１９７】
また、本実施例の実装は、実施例3と同様の方法を用いてシフト演算処理を省略するにより、更なる高速化を図ってもよい。
【０１９８】
また、実施例1から実施例3と同様に、本実施例におけるスカラー倍計算方法は、非特許文献３に記載の楕円曲線やフロベニウス写像をもつ楕円曲線に対しても適用することができる。
【０１９９】
以上の通り、上記計算方法は、楕円曲線上の加算とは異なる第二の演算を有する楕円曲線に対し、メモリ使用量、及び、高速性に優れるという特徴がある。
【実施例５】
【０２００】
次に本発明を署名検証システムに適用する実施形態を、図14と図2を用いて説明する。
【０２０１】
図2の署名検証システムは、スマートカード1401と署名検証処理を行うコンピュータ1421とから成る。
【０２０２】
スマートカード1401は、図1のコンピュータＡ101と類似の構成を備え、ＣＰＵ113やコプロセッサ114などの演算装置とが記憶部102に格納されているプログラムを実行することにより、データ処理部112ではなく、署名生成処理部1412を実現する。
【０２０３】
ただし、図1に示す外部記憶装置107、ディスプレイ108、キーボード109を備えなくてもよい。コンピュータ1421は、コンピュータＡ101と同様の構成を備え、ＣＰＵ113がプログラムを実行することによりデータ処理部112ではなく、署名検証処理部1432を実現する。スカラー倍計算部1415と1435は、図1に示すスカラー倍計算部115または135と同様の機能を備える。
【０２０４】
なお、本実施例において、コンピュータ1421内の各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていても良いし、必要なときに、コンピュータ1421が利用可能な媒体を介して他の装置から上記記憶部に導入されてもよい。
【０２０５】
さらに、スマートカード1401内の各プログラムは、あらかじめ、上記スマートカード1401内の記憶部に格納されていても良いし、必要なときに、入出力インタフェースを介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して上記記憶部に導入されてもよい。媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【０２０６】
図14の署名検証システムにおける署名生成と署名検証動作を、図2を参照して説明する。離散対数問題に基づくディジタル署名方法を楕円曲線上の離散対数問題に基づく方法に対応させて構成する楕円曲線ディジタル署名アルゴリズム（ECDSA）という署名方法がある。ECDSA署名については、たとえば非特許文献１に記載されている。
【０２０７】
コンピュータ1421は、ランダムに選んだ数値をチャレンジコード1442として、インタフェースを介してスマートカード1401に転送する。
【０２０８】
署名生成処理部1412(図2の112)は、チャレンジコード1442を受け付け、チャレンジコード1442のハッシュ値をとり、所定のビット長の数値fに変換する。
【０２０９】
署名生成処理部1412は、乱数uを生成し、記憶部1402(図2の102)に格納されている定数1404から読み出した(図2の205)楕円曲線上の定点Qとともにスカラー倍計算部1415(図2の115)へ送る(図2の206)。
【０２１０】
スカラー倍計算部1415は、定点Q、乱数uによるスカラー倍点u Q=(xu ,yu )を計算し、計算されたスカラー倍点を署名生成処理部1412へ送る(図2の207)。
署名生成処理部1412は、送られたスカラー倍点を用いて署名の生成を行う。例えば、非特許文献１のECDSA署名であれば、
s = xu mod q                    (式65)
t = u-1 (f+ds) mod q            (式66)
を計算することによりチャレンジコード1442に対応する署名(s, t)を得る(図2の208)。
【０２１１】
ここで、qは定点Qの位数、すなわち定点Qのq倍点q Qが無限遠点になり、qより小さな数値mに対する定点Qのm倍点m Qは無限遠点にはならない、というような数値のことである。
【０２１２】
スマートカード1401は、署名生成処理部1412で生成した署名1441を入出力インタフェース1410より出力し、インタフェースを介してコンピュータ1421へ転送する。
コンピュータ1421の署名検証処理部1432(図2の112)は、署名1441が入力される(図2の204)と、署名1441の数値s,tが適切な範囲内すなわち1≦s,t<qであるかを調べる。
【０２１３】
数値s,tが上記範囲内になければチャレンジコード1442に対する署名の検証結果として「無効」を出力し、スマートカード1401を拒絶する。数値s,tが上記範囲内にあれば、署名検証処理部1432は、
h = t-1 mod q                    (式67)
h1 = fh mod q                    (式68)
h2 = sh mod q                  (式69)
を計算する。
【０２１４】
そして、記憶部1422(図2の102)に格納されている定数1424から読み出した(図2の205)公開鍵d Q及び定点Qと計算したh1 ,h2 をスカラー倍計算部1435(図2の115)へ送る(図2の206)。
【０２１５】
スカラー倍計算部1435は、定点Qとh1 によるスカラー倍点h1 Qと、公開鍵d Qとh2 によるスカラー倍点h2 d Qとを計算し、計算されたスカラー倍点を署名検証処理部1432へ送る(図2の207)。
【０２１６】
署名検証処理部1432は、送られたスカラー倍点を用いて、署名検証処理を行う。例えば、ECDSAの署名検証であれば、点R
R = h1 Q+h2 d Q                (式70)
を計算し、そのx座標をxR としたとき、
s' = xR mod q                (式71)
を計算し、s'=sであればチャレンジコード1442に対する署名の検証結果として「有効」を出力し、スマートカード1401を認証し、受け入れる(図2の208)。
s'=sでなければ「無効」を出力し、スマートカードを拒絶する(図2の208)。
署名の生成と検証では、スカラー倍点を計算する。したがって、署名生成、及び、署名検証を行う際に、実施例1から実施例4までの何れか一つに記載のスカラー倍計算方法を用いることが可能である。
【０２１７】
署名の検証では式70より、検証する直前に受け取った点Qと公開鍵d Qによる多重スカラー倍点h1 Q+h2 d Qを計算する。そのため、非特許文献2の方法を用いる場合、式66を計算する前に前計算テーブルを作成する必要がある。しかし、実施例1から実施例4までの何れか一つに記載のスカラー倍計算方法を用いると前計算テーブルを作成する必要がなく、使用可能なメモリが制限された場合にもスカラー倍計算を高速に行うことができる。
【実施例６】
【０２１８】
次に本発明を鍵交換システムに適用する実施形態を説明する。本実施形態においては、図1のシステム構成が応用できる。
【０２１９】
図1のデータ処理部112、132は、本実施形態においては、それぞれ鍵交換処理部112、132として機能する。鍵交換システムのコンピュータＡ101が、入力されたデータ143から共有情報の導出を行う場合の動作について図1、図2を参照して説明する。
【０２２０】
コンピュータＢ121のデータ処理部132(図2の112)は、記憶部122(図2の102)の秘密情報125から秘密鍵bを読み出しコンピュータＢ121の公開鍵bQを計算する。そして、ネットワーク142を介して、公開鍵bQをデータ143としてコンピュータＡ101に転送する。コンピュータＡ101の鍵交換処理部112(図2の112)はコンピュータＢ121の公開鍵bQの入力を受け付ける(図2の204)と、鍵交換処理部112は、記憶部102から読み出した(図2の205)秘密情報105であるコンピュータＡ101の秘密鍵aと、コンピュータＢ121の公開鍵bQとをスカラー倍計算部115へ送る(図2の206)。
【０２２１】
スカラー倍計算部115は、秘密鍵dと、公開鍵bQによるスカラー倍点dbQを計算し、計算されたスカラー倍点を鍵交換処理部112へ送る(図2の207)。
【０２２２】
鍵交換処理部112は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部102に秘密情報105として格納する。例えば、スカラー倍点dbQのx座標を、共有情報とする。
【０２２３】
次に、コンピュータ121が、入力されたデータ141から共有情報の導出を行う場合の動作について説明する。
【０２２４】
コンピュータＡ101のデータ処理部112は、記憶部102の秘密情報105から秘密鍵dを読み出しコンピュータＡ101の公開鍵dQを計算する。そして、ネットワーク142を介して、公開鍵dQをデータ141としてコンピュータＢ121に転送する。
【０２２５】
コンピュータＢ121の鍵交換処理部132(図2の112)はコンピュータＡ101の公開鍵dQの入力を受け付ける(図2の204)と、鍵交換処理部132は、記憶部122(図2の102)の定数125から読み出した(図2の205)秘密情報125であるコンピュータＢ121の秘密鍵bと、コンピュータＡ101の公開鍵dQとをスカラー倍計算部135(図2の115)へ送る(図2の206)。
【０２２６】
スカラー倍計算部135は、秘密鍵bと、公開鍵d Qによるスカラー倍点bd Qを計算し、計算されたスカラー倍点を鍵交換処理部132へ送る(図2の207)。
鍵交換処理部132は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部122に秘密情報125として格納する。例えば、スカラー倍点bd Qのx座標を、共有情報とする。ここで、数dbと数bdは数値として同じなので、点db Qと点bd Qは同じ点となり、同じ情報が導出されたことになる。
【０２２７】
鍵共有では、受け取った点のスカラー倍点を計算する。したがって、鍵交換を行う際に、実施例1から実施例4までの何れか一つに記載のスカラー倍計算方法を用いることが可能である。
【０２２８】
また、鍵共有では、鍵交換した際に受け取った点によるスカラー倍点を計算する。そのため、非特許文献2の方法を用いる場合、受け取った点のスカラー倍点を計算する前に前計算テーブルを作成する必要がある。しかし、実施例1から実施例4までの何れか一つに記載のスカラー倍計算方法を用いると前計算テーブルを作成する必要がない。
【０２２９】
ネットワーク142には、点d Qと点b Qが送信されるが、点db Q(もしくは点bd Q)を計算するには秘密鍵dもしくは秘密鍵bを用いなければならない。すなわち、秘密鍵dもしくは秘密鍵bを知らなければ、共有情報を得ることができない。このようにして得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。
【０２３０】
また、上記各実施形態における暗号化処理部、復号化処理部、署名生成処理部、署名検証処理部、鍵交換処理部は、専用のハードウェアを用いて行ってもよい。また、スカラー倍計算部をコプロセッサまたはそれ以外の専用ハードウェアで実現しても良い。また、データ処理部は、上記暗号化処理、復号化処理、署名生成処理、署名検証処理、鍵交換処理のうち、任意の一つ以上の処理を行えるように構成してもよい。
【図面の簡単な説明】
【０２３１】
【図１】各実施形態におけるシステム構成図である。
【図２】各実施形態における情報の受け渡しを示すシーケンス図である。
【図３】実施例1、及び、実施例2の実施形態におけるスカラー倍計算部の構成図である。
【図４】実施例1、実施例2、及び、実施例3におけるエンコード部の行うエンコード方法を示すフローチャート図である。
【図５】実施例1、及び、実施例2における実計算部のスカラー倍点の計算方法を示すフローチャート図である。
【図６】実施例2における実計算部のスカラー倍点の計算方法を示すフローチャート図である。
【図７】実施例3の実施形態におけるスカラー倍計算部の構成図である。
【図８】実施例3における実計算部のスカラー倍点の計算方法を示すフローチャート図である。
【図９】実施例3における実計算部のスカラー倍点の計算方法を示すフローチャート図である。
【図１０】実施例4の実施形態におけるスカラー倍計算部の構成図である。
【図１１】実施例4における実計算部のスカラー倍点の計算方法を示すフローチャート図である。
【図１２】実施例4の実施形態におけるスカラー倍計算部の構成図である。
【図１３】実施例4における実計算部のスカラー倍点の計算方法を示すフローチャート図である。
【図１４】署名検証システムを示す構成図である。
【図１５】従来技術と本発明によるスカラー倍計算方法の概念を説明する図である。
【符号の説明】
【０２３２】
101、121、1421：コンピュータ、1401：スマートカード、102、122、1402、1422：記憶部、111、131、1411、1431：処理部、115、135、1415、1435：スカラー倍計算部、112、132：データ処理部、1412：署名生成処理部、1432：署名検証処理部、104、124、1404、1424：定数、105、125、1405、1425：秘密情報、110、130、1410、1430：入出力インタフェース、108、128、1428：ディスプレイ、109、129、1429：キーボード、142：ネットワーク、1442：チャレンジコード、141、143：データ、302：エンコード部、303：実計算部、321：剰余取得部、322：剰余変換部、323：繰り返し判定部、324：δ剰余変換部、325：Φｗ 関数計算部、326：格納部、331：ビット値判定部、332：加算部、333：τ倍算部、334：繰り返し判定部、702：エンコード部、703：実計算部、721：剰余取得部、722：剰余変換部、723：繰り返し判定部、724：δ剰余変換部、725：Φｗ 関数計算部、726：格納部、731：ビット値判定部、732：加算部、733：τ倍算部、734：繰り返し判定部、735：基底変換部、1002：実計算部、1021：剰余取得部、1022：剰余変換部、1023：繰り返し判定部、1024：δ剰余変換部、1025：Φｗ 関数計算部、1031：ビット値判定部、1032：加算部、1033：τ倍算部、1202：実計算部、1221：剰余取得部、1222：剰余変換部、1223：繰り返し判定部、1224：δ剰余変換部、1225：Φｗ 関数計算部、1231：ビット値判定部、1232：加算部、1233：τ倍算部、1234：基底変換部。
【図１】
2006235416.tif 000003
【図２】
2006235416.tif 000004
【図３】
2006235416.tif 000005
【図４】
2006235416.tif 000006
【図５】
2006235416.tif 000007
【図６】
2006235416.tif 000008
【図７】
2006235416.tif 000009
【図８】
2006235416.tif 000010
【図９】
2006235416.tif 000011
【図１０】
2006235416.tif 000012
【図１１】
2006235416.tif 000013
【図１２】
2006235416.tif 000014
【図１３】
2006235416.tif 000015
【図１４】
2006235416.tif 000016
【図１５】
2006235416.tif 000017