(57)【要約】【課題】楕円曲線のパラメータに制限を加えることなく、楕円加算のみを用いてサイドチャネル攻撃への対策が可能な、楕円曲線スカラー倍算装置を提供すること。【解決手段】楕円曲線上の点Ｐの座標と整数値ｅとを入力する入力手段と、入力された整数値ｅを第１の数値列Ａ＝（ａ1，ａ2，．．．，ａv）に変換する第１の変換手段と、変換された第１の数値列Ａを第２の数値列Ｃ＝（ｃ1，ｃ2，．．．，ｃm）に変換する第２の変換手段と、楕円曲線上の点Ｐから事前計算テーブル（Ｐ1，Ｐ2，．．．，Ｐn）を計算する第１の計算手段と、変換された第１の数値列Ａ、変換された第２の数値列Ｃ、および計算された事前計算テーブルから、スカラー倍点を計算する第２の計算手段と、計算されたスカラー倍点を出力する出力手段を備える。【選択図】図４
2011085750.tif 000002
【特許請求の範囲】
【請求項１】
定義体Ｆq上定義された楕円曲線を用いて、整数値ｅおよび前記楕円曲線上の点Ｐから、スカラー倍点Ｑ＝ｅＰを計算する楕円曲線スカラー倍算装置であって、
楕円曲線上の点Ｐの座標と整数値ｅとを入力する入力手段と、
前記入力手段によって入力された整数値ｅを第１の数値列Ａ＝（ａ1，ａ2，．．．，ａv）に変換する第１の変換手段と、
前記第１の変換手段によって変換された第１の数値列Ａを第２の数値列Ｃ＝（ｃ1，ｃ2，．．．，ｃm）に変換する第２の変換手段と、
前記楕円曲線上の点Ｐから事前計算テーブル（Ｐ1，Ｐ2，．．．，Ｐn）を計算する第１の計算手段と、
前記第１の変換手段によって変換された第１の数値列Ａ、前記第２の変換手段によって変換された第２の数値列Ｃ、および前記第１の計算手段によって計算された事前計算テーブルから、前記スカラー倍点Ｑを計算する第２の計算手段と、
前記第２の計算手段によって計算された前記スカラー倍点Ｑを出力する出力手段と、
を備えることを特徴とする楕円曲線スカラー倍算装置。
【請求項２】
前記第１の変換手段は、Ｇi+1＝Ｇi＋Ｇi-1をみたす一般化フィボナッチ数列Ｇiにより、Ｇi+1＞ｅ＞Ｇi-1をみたすｉを求め、ｎにｉ、ｖに１、およびａvにｉを代入し、ｅにｅ−Ｇnを計算して代入した後、ｅ＞０である間、Ｇi+1＞ｅ＞Ｇi−１をみたすｉを求め、ｖにｖ＋１を計算して代入し、ａvにｉを代入し、ｅにｅ−Ｇiを計算して代入する処理を繰り返すことにより、前記整数値ｅを前記第１の数値列Ａに変換する、ことを特徴とする請求項１に記載の楕円曲線スカラー倍算装置。
【請求項３】
前記第２の変換手段は、前記ｎについて、ｍに［（ｎ＋１）／２］（［ｘ］はｘを超えない最大の整数値をあらわす）を計算して代入し、ｋにｍ−ｖを計算して代入し、ｋ＞０である場合に、０＜ｒ＜ｖ＋１となる整数ｒをランダムに選択し、前記第１の数値列Ａ＝（ａ1，ａ2，．．．，ａv）について、ｉに１を代入し、ｂj(1)にａj（ｊ＜ｒ）を代入し、ｂr(1)にａr−１を代入し、ｂr+1(1)にａr−２を代入し、ｂj+1(1)にａj（ｊ＞ｒ）を代入し、第１の数値列Ａから第３の数値列Ｂ(1)＝（ｂ1(1)，ｂ2(1)，．．．，ｂv+1(1)）を構成し、ｉ＜ｋである間、０＜ｒ＜ｖ＋ｉ＋１となる整数ｒをランダムに選択し、前記第３の数値列Ｂ(i)＝（ｂ1(i)，ｂ2(i)，．．．，ｂv+i(i)）について、ｂj(i+1)にｂj(i)（ｊ＜ｒ）を代入し、ｂr(i+1)にｂr(i)−１を代入し、ｂr+1(i+1)にｂr(i)−２を代入し、ｂj+1(i+1)にｂj(i)（ｊ＞ｒ）を代入して、前記第３の数値列Ｂ(i)から数値列Ｂ(i+1)＝（ｂ1(i+1)，ｂ2(i+1)，．．．，ｂv+i+1(i+1)）に変換し、ｉ←ｉ＋１として変換を行うまでの処理を繰り返すことにより、数値列Ｂ(k)＝（ｂ1(k)，ｂ2(k)，．．．，ｂm(k)）を求めて、前記第２の数値列Ｃ＝（ｃ1，ｃ2，．．．，ｃm）について、ｃjにｂj(k)（０＜ｊ＜ｍ＋１）を代入する、ことを特徴とする請求項２に記載の楕円曲線スカラー倍算装置。
【請求項４】
前記第１の変換手段は、Ｇnに基づいてＰ1にＧ1Ｐを計算して代入し、Ｐ2にＧ2Ｐを計算して代入し、Ｐi（ｉ＞２）について、ＰiにＰi-1＋Ｐi-2を計算して代入して、逐次的に前記整数値ｅを前記第１の数値列Ａに変換する、ことを特徴とする請求項２に記載の楕円曲線スカラー倍算装置。
【請求項５】
前記第２の数値列Ｃおよび前記事前計算テーブルに基づいて、前記スカラー倍点ＱにＯ（Ｏは無限遠点をあらわす）を代入し、ｉに１を代入し、ｉ＜ｍ＋１である間、前記スカラー倍点ＱにＱ＋Ｐc_iを計算して代入し、ｉにｉ＋１を代入することを繰り返し、前記スカラー倍点Ｑ＝ｅＰを計算する第３の計算手段、
を備えることを特徴とする請求項１乃至３の何れか１項に記載の楕円曲線スカラー倍算
装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セキュリティ技術に関し、特に、楕円曲線上でのスカラー倍算演算に関する。
【背景技術】
【０００２】
従来、楕円曲線暗号は公開鍵暗号のカテゴリに属する暗号技術であり、楕円曲線離散対数問題を解くことの困難さにその理論的な安全性の根拠をおいている。
楕円曲線暗号の実現にあたっては、楕円曲線スカラー倍算と呼ばれる演算が用いられ、この楕円曲線スカラー倍算の処理性能が楕円曲線暗号全体の処理性能を左右するほど、楕円曲線暗号において主要な演算となっている。
【０００３】
楕円曲線スカラー倍算は、与えられた楕円曲線上の１点およびスカラー値（整数値）を入力として、楕円２倍算と呼ばれる楕円曲線上の１点に対する演算、楕円加算と呼ばれる楕円曲線上の異なる２点に対する演算、さらに、自己準同型写像であるフロベニウス写像φが定義される楕円曲線では、楕円曲線上の１点に対するフロベニウス写像、これらの演算（写像）を組み合わせて用いることにより計算され、計算結果として楕円曲線上の１点を出力する演算である。
【０００４】
これらの演算（写像）の組み合わせ方（アルゴリズム）によっては、楕円曲線スカラー倍算を効率良く計算でき、ひいては楕円曲線暗号全体の処理性能を向上させることができるため、これまでに様々なアルゴリズムが提案されてきた。
【０００５】
しかし一方では、こうした暗号技術を実際にソフトウェアで実装したり、回路としてハードウェアに組み込んだりする場合に、暗号処理時に観測される消費電力や漏洩電波などのサイドチャネル情報から秘密情報が漏洩する可能性が近年になって明らかになり、そうしたサイドチャネル情報から秘密鍵などの秘密情報を特定する攻撃、いわゆるサイドチャネル攻撃に関する研究報告がこれまでに多数なされている。
【０００６】
楕円曲線暗号においても、楕円曲線スカラー倍算の処理において、実現するためのアルゴリズムによっては、そうしたサイドチャネル攻撃に対して脆弱である研究報告がなされている。
【０００７】
具体的には、楕円曲線スカラー倍算の入力であるスカラー値において、前述の楕円２倍算や楕円加算（ならびにフロベニウス写像）の処理系列がスカラー値の内容によって変化するようなアルゴリズムであり、さらに消費電力などのサイドチャネル情報において波形パターン等からそれらの楕円２倍算や楕円加算（ならびにフロベニウス写像）の演算が識別可能であれば、逆に処理系列からスカラー値の特定が可能となるものである。
【０００８】
楕円曲線暗号においては、そうしたスカラー値に秘密鍵などの秘密情報を設定する暗号方式が多数あり、その場合サイドチャネル攻撃により秘密鍵を特定することが可能となる。
【０００９】
したがって、楕円曲線スカラー倍算の実現方式については、性能だけではなくそうしたサイドチャネル攻撃についての対策が必要とされている。
そうした対策としては、楕円２倍算と楕円加算が一定のパターンで出現するようにアルゴリズムを工夫した方式や、楕円曲線のパラメータを限定して楕円曲線の表現式を変形することにより、楕円２倍算と楕円加算の演算公式を同一化して、波形パターンの特定を防
ぐ方式などが提案されている。
【００１０】
例えば、楕円曲線スカラー倍算において、複数の基本演算の呼び出し順序に規則性を持たせてサイドチャネル攻撃への対策を実現した技術が開示されている（例えば、特許文献１参照。）。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００６−２４３６９０号公報
【発明の概要】
【発明が解決しようとする課題】
【００１２】
しかしながら、従来技術は、楕円曲線スカラー倍算の演算処理におけるサイドチャネル攻撃への対策として、これまで提案されていた楕円２倍算と楕円加算の演算の公式を同一化することにより処理系列の識別を困難化し、スカラー値の特定を防ぐ方式については、楕円曲線のパラメータについて制限を加える必要がある、という課題があった。
【００１３】
本発明は、上述のような実状に鑑みたものであり、上述のように楕円曲線のパラメータに制限を加えることなく、楕円加算のみを用いてサイドチャネル攻撃への対策が可能な、楕円曲線スカラー倍算装置を提供することを目的とする。
【課題を解決するための手段】
【００１４】
本発明は、上記課題を解決するため、下記のような構成を採用した。
すなわち、本発明の一態様によれば、本発明の楕円曲線スカラー倍算装置は、定義体Ｆq上定義された楕円曲線を用いて、整数値ｅおよび前記楕円曲線上の点Ｐから、スカラー倍点Ｑ＝ｅＰを計算する楕円曲線スカラー倍算装置であって、楕円曲線上の点Ｐの座標と整数値ｅとを入力する入力手段と、前記入力手段によって入力された整数値ｅを第１の数値列Ａ＝（ａ1，ａ2，．．．，ａv）に変換する第１の変換手段と、前記第１の変換手段によって変換された第１の数値列Ａを第２の数値列Ｃ＝（ｃ1，ｃ2，．．．，ｃm）に変換する第２の変換手段と、前記楕円曲線上の点Ｐから事前計算テーブル（Ｐ1，Ｐ2，．．．，Ｐn）を計算する第１の計算手段と、前記第１の変換手段によって変換された第１の数値列Ａ、前記第２の変換手段によって変換された第２の数値列Ｃ、および前記第１の計算手段によって計算された事前計算テーブルから、前記スカラー倍点Ｑを計算する第２の計算手段と、前記第２の計算手段によって計算された前記スカラー倍点Ｑを出力する出力手段とを備えることを特徴とする。
【００１５】
また、本発明の楕円曲線スカラー倍算装置は、前記第１の変換手段が、Ｇi+1＝Ｇi＋Ｇi-1をみたす一般化フィボナッチ数列Ｇiにより、Ｇi+1＞ｅ＞Ｇi-1をみたすｉを求め、ｎにｉ、ｖに１、およびａvにｉを代入し、ｅにｅ−Ｇnを計算して代入した後、ｅ＞０である間、Ｇi+1＞ｅ＞Ｇi−１をみたすｉを求め、ｖにｖ＋１を計算して代入し、ａvにｉを代入し、ｅにｅ−Ｇiを計算して代入する処理を繰り返すことにより、前記整数値ｅを前記第１の数値列Ａに変換することが望ましい。
【００１６】
また、本発明の楕円曲線スカラー倍算装置は、前記第２の変換手段が、前記ｎについて、ｍに［（ｎ＋１）／２］（［ｘ］はｘを超えない最大の整数値をあらわす）を計算して代入し、ｋにｍ−ｖを計算して代入し、ｋ＞０である場合に、０＜ｒ＜ｖ＋１となる整数ｒをランダムに選択し、前記第１の数値列Ａ＝（ａ1，ａ2，．．．，ａv）について、ｉに１を代入し、ｂj(1)にａj（ｊ＜ｒ）を代入し、ｂr(1)にａr−１を代入し、ｂr+1(1)にａr−２を代入し、ｂj+1(1)にａj（ｊ＞ｒ）を代入し、第１の数値列Ａから第３の数値列Ｂ(1)＝（ｂ1(1)，ｂ2(1)，．．．，ｂv+1(1)）を構成し、ｉ＜ｋである間、０＜ｒ＜ｖ
＋ｉ＋１となる整数ｒをランダムに選択し、前記第３の数値列Ｂ(i)＝（ｂ1(i)，ｂ2(i)，．．．，ｂv+i(i)）について、ｂj(i+1)にｂj(i)（ｊ＜ｒ）を代入し、ｂr(i+1)にｂr(i)−１を代入し、ｂr+1(i+1)にｂr(i)−２を代入し、ｂj+1(i+1)にｂj(i)（ｊ＞ｒ）を代入して、前記第３の数値列Ｂ(i)から数値列Ｂ(i+1)＝（ｂ1(i+1)，ｂ2(i+1)，．．．，ｂv+i+1(i+1)）に変換し、ｉ←ｉ＋１として変換を行うまでの処理を繰り返すことにより、数値列Ｂ(k)＝（ｂ1(k)，ｂ2(k)，．．．，ｂm(k)）を求めて、前記第２の数値列Ｃ＝（ｃ1，ｃ2，．．．，ｃm）について、ｃjにｂj(k)（０＜ｊ＜ｍ＋１）を代入することが望ましい。
【００１７】
また、本発明の楕円曲線スカラー倍算装置は、前記第１の変換手段が、Ｇnに基づいてＰ1にＧ1Ｐを計算して代入し、Ｐ2にＧ2Ｐを計算して代入し、Ｐi（ｉ＞２）について、ＰiにＰi-1＋Ｐi-2を計算して代入して、逐次的に前記整数値ｅを前記第１の数値列Ａに変換することが望ましい。
【００１８】
また、本発明の楕円曲線スカラー倍算装置は、前記第２の数値列Ｃおよび前記事前計算テーブルに基づいて、前記スカラー倍点ＱにＯ（Ｏは無限遠点をあらわす）を代入し、ｉに１を代入し、ｉ＜ｍ＋１である間、前記スカラー倍点ＱにＱ＋Ｐc_iを計算して代入し、ｉにｉ＋１を代入することを繰り返し、前記スカラー倍点Ｑ＝ｅＰを計算する第３の計算手段を備えることが望ましい。
【００１９】
すなわち、上記課題を解決するために、本発明においては、スカラー値を一般化フィボナッチ数列において現れる数の和で表現する。
一般化フィボナッチ数は、Ｇn+1＝Ｇn＋Ｇn-1で定義される数列のことであり、代表的なフィボナッチ（Fibonacci）数は初期値がＧ1＝１、Ｇ2＝１、リュカ（Lucas）数は初期値がＧ1＝１、Ｇ2＝３で定義される数列のことである。
【００２０】
一般的な事実として、Ｇ1およびＧ2に適切な初期値を選べば、任意の整数値ｅは、異なる一般化フィボナッチ数の和ｅ＝ΣiＧiとして表現される。この和表現においては、数列において隣り合う項が（すなわち、ＧiとＧi+1が同時に）現れることはないため、Ｇn+1＞ｅ＞Ｇn−１とした場合、整数値ｅのフィボナッチ数による和表現ｅ＝ΣiＧiにおいて現れるフィボナッチ数Ｇiの個数は高々[(ｎ＋１)／２]個である（[ｘ]はｘを超えない最大の整数値をあらわす）。
【００２１】
このとき、任意の項（一般化フィボナッチ数）Ｇkについて、Ｇk＝Ｇk-1＋Ｇk-2と展開することができるため、この展開を繰り返すことによって、和表現におけるフィボナッチ数の個数を増やして[(ｎ＋１)／２]個に固定することができる。
【００２２】
ここで、整数ｅについて、楕円曲線上の点Ｐに対する楕円曲線スカラー倍算演算ｅＰを行うことを考える。楕円曲線上の点Ｐiについて、Ｐi＝ＧiＰとして定める。すると、点Ｐiについては、Ｇiの性質より、Ｐi+1＝Ｐi＋Ｐi-1として楕円加算演算により求めることができるとともに、点Ｐiを用いてＱ＝ｅＰ＝ΣiＧiＰ＝ΣiＰiとして計算することができる。前述のとおり、項（フィボナッチ数）の個数は一定にできるため、ΣiＰiにおける楕円曲線加算演算の回数を一定にすることが可能となる。
【発明の効果】
【００２３】
本発明は、楕円曲線スカラー倍算において、楕円曲線のパラメータに制限を加えることなく、一般化フィボナッチ数列を用いて１つの基本演算を一定回数だけ呼び出すだけで、サイドチャネル攻撃対策を実現することが可能となる、という効果を奏する。
【図面の簡単な説明】
【００２４】
【図１】本発明を適用した実施の形態であるディジタル署名生成・署名検証システムを示す図である。
【図２】楕円曲線暗号処理部１１００における機能ブロック図である。
【図３】楕円曲線暗号処理部２１００における機能ブロック図である。
【図４】楕円曲線スカラー倍算装置１１１０における機能ブロック図である。
【図５】楕円曲線暗号処理部１１００におけるＥＣＤＳＡ署名生成処理の流れを示すフローチャートである。
【図６】楕円曲線暗号処理部２１００におけるＥＣＤＳＡ署名検証処理の流れを示すフローチャートである。
【図７】楕円曲線スカラー倍算装置１１１０における楕円曲線スカラー倍算演算処理の流れを示すフローチャート（その１）である。
【図８】楕円曲線スカラー倍算装置１１１０における楕円曲線スカラー倍算演算処理の流れを示すフローチャート（その２）である。
【図９】楕円曲線スカラー倍算装置１１１０における楕円曲線スカラー倍算演算処理の流れを示すフローチャート（その３）である。
【図１０】楕円曲線スカラー倍算装置１１１０における楕円曲線スカラー倍算演算処理の流れを示すフローチャート（その４）である。
【図１１】楕円曲線スカラー倍算装置１１１０における楕円曲線スカラー倍算演算処理の流れを示すフローチャート（その５）である。
【発明を実施するための形態】
【００２５】
以下、本発明の実施の形態について、図面を参照しながら詳細に説明する。
図１は、本発明を適用した実施の形態であるディジタル署名生成・署名検証システムを示す図である。
【００２６】
本ディジタル署名生成・署名検証システムは、対象となるメッセージデータに対して署名生成を行い、生成されたディジタル署名をネットワーク経由で外部に送信する機能を持った情報処理装置１０００と、ネットワーク経由で外部から受信したディジタル署名について署名検証を行う情報処理装置２０００から構成される。
【００２７】
情報処理装置１０００には、ディスプレイ７００、キーボード８００および記憶装置９００が接続され、情報処理装置２０００には、ディスプレイ１７００、キーボード１８００および記憶装置１９００が接続されている。
【００２８】
また、ディジタル署名方式については、ここではＥＣＤＳＡ（Elliptic Curve Digital
Signature Algorithm：楕円曲線ディジタル署名アルゴリズム）を使用する。ＥＣＤＳＡは、楕円曲線上の離散対数問題の困難さに基づくディジタル署名方式である。ＥＣＤＳＡの詳細については、URL http://www.cryptrec.go.jp/ を参照することができる。
【００２９】
図１において、情報処理装置１０００は、外部との入出力インターフェイス１２００、情報処理制御部１３００、ディジタル署名生成を行う機能を有した楕円曲線暗号処理部１１００を有し、さらに楕円曲線暗号処理部１１００は、本発明の楕円曲線スカラー倍算方式を具現化した楕円曲線スカラー倍算装置１１１０を有する。
【００３０】
また、情報処理装置２０００は、外部との入出力インターフェイス２２００、情報処理制御部２３００、ディジタル署名生成を行う機能を有した楕円曲線暗号処理部２１００を有し、さらに楕円曲線暗号処理部２１００は、本発明の楕円曲線スカラー倍算方式を具現化した楕円曲線スカラー倍算装置２１１０を有する。なお、楕円曲線スカラー倍算装置２１１０は、図４を用いて後述するような楕円曲線スカラー倍算装置１１１０と同様の構成を備える。
【００３１】
情報処理制御部１３００は、入出力インターフェイス１２００を通じて外部装置とデータの入出力制御を行い、また、楕円曲線暗号処理部１１００に対して署名生成の対象となるメッセージを入力し、楕円曲線暗号処理部１１００から出力されたＥＣＤＳＡ署名データを受け取る。
【００３２】
情報処理制御部２３００は、入出力インターフェイス２２００を通じて外部装置とデータの入出力制御を行い、また、楕円曲線暗号処理部２１００に対してＥＣＤＳＡ署名データを入力し、楕円曲線暗号処理部２１００から出力された署名検証結果を受け取る。
【００３３】
図２は、楕円曲線暗号処理部１１００における機能ブロック図である。
図２において、楕円曲線暗号処理部１１００は、楕円曲線スカラー倍算装置１１１０、ハッシュ値計算部１１２０、パラメータ保持部１１３０、秘密鍵保持部１１４０、乱数生成部１１５０、比較演算部１１６０、剰余演算部１１７０、剰余逆元演算部１１８０、剰余乗算演算部１１９０および剰余加算演算部１１９５を備える。
【００３４】
図３は、楕円曲線暗号処理部２１００における機能ブロック図である。
図３において、楕円曲線暗号処理部２１００は、楕円曲線スカラー倍算装置２１１０、ハッシュ値計算部２１２０、パラメータ保持部２１３０、公開鍵保持部２１４０、比較演算部２１６０、剰余演算部２１７０、剰余逆元演算部２１８０、剰余乗算演算部２１９０および剰余加算演算部２１９５を備える。
【００３５】
図４は、楕円曲線スカラー倍算装置１１１０における機能ブロック図である。
図４において、楕円曲線スカラー倍算装置１１１０は、楕円曲線スカラー倍算処理制御部１１１１、入出力インターフェイス１１１２、事前調整部１１１３、インデックス変換処理部１１１４、インデックス記憶部１１１５、事前計算部１１１６、総和計算処理部１１１７、事前計算結果記憶部１１１８、楕円曲線加算処理部１１１９および楕円曲線２倍算処理部１１２１を備える。
【００３６】
次に、情報処理装置１０００によって実行される、ＥＣＤＳＡによるディジタル署名が生成されるシーケンスについて、図面を用いて説明する。
まず、外部入力に起因して、情報処理制御部１３００にて、署名生成を行う対象となるメッセージを楕円曲線暗号処理部１１００に入力する。そして、楕円曲線暗号処理部１１００によって、ＥＣＤＳＡ署名生成処理が実行される。
【００３７】
図５は、楕円曲線暗号処理部１１００におけるＥＣＤＳＡ署名生成処理の流れを示すフローチャートである。
まず、ステップＳ０５０１において、パラメータ保持部１１３０から楕円曲線ドメインパラメータ（ｐ，ａ，ｂ，ｒ，Ｇ）および補助パラメータ（ｍ，ｎ，Ｇn，Ｇn+1）を読み込む。また、秘密鍵保持部１１４０から秘密鍵ｓを読み込む。
【００３８】
ここで、ｐは定義体（素体）の標数であり、ａおよびｂは楕円曲線ｙ2＝ｘ3＋ａｘ＋ｂ（ワイエルシュトラス表現）を定義するパラメータである。また、ｒは楕円曲線の最大素数位数、Ｇはその生成元をあらわす。ｎは一般化フィボナッチ数列Ｇn（初期値はＧ1＝１，Ｇ2＝２とする）について、Ｇn+1＋１＞ｒ＞Ｇnをみたすｎであり、またｍ＝[（ｎ＋1）／２]である。なお、［ｘ］はｘを超えない最大の整数値をあらわす。
【００３９】
次に、ステップＳ０５０２において、メッセージＭを読み込み、ステップＳ０５０３において、ハッシュ値ｆ＝Ｈ（Ｍ）をハッシュ値計算部１１２０によって計算する。
次に、ステップＳ０５０４において、［１，ｕ］の範囲で乱数ｕを乱数生成部１１５０
によって生成する。そして、ステップＳ０５０５において、Ｑ＝ｕＧを楕円曲線スカラー倍算装置１１１０により計算し、ステップＳ０５０６において、ｃ＝Ｑx mod ｒを剰余演算部１１７０によって計算する。
【００４０】
次に、ステップＳ０５０７において、ｃが０であるか（ｃ＝０）否かを判断する。
ｃ＝０であるならば（ステップＳ０５０７：ｙｅｓ）、ステップＳ０５０４へ戻り、ｃ＝０でなければ（ステップＳ０５０７：ｎｏ）、ステップＳ０５０８へ進む。
【００４１】
そして、ステップＳ０５０８において、以下の計算をする。まず、ｕ-1を剰余逆元演算部１１８０によって計算する。つづいて、ｓ×ｃを剰余乗算演算部１１９０において計算する。その後、ｆ＋ｓｃを剰余加算演算部１１９５によって計算し、最後に、ｕ-1（ｆ＋ｓｃ）を剰余乗算演算部１１９０において計算する。
【００４２】
次に、ステップＳ０５０９において、ｄが０であるか（ｄ＝０）否かを判断する。
ｄ＝０であるならば（ステップＳ０５０９：ｙｅｓ）、ステップＳ０５０４へ戻り、ｄ＝０でなければ（ステップＳ０５０９：ｎｏ）、ステップＳ０５１０へ進む。
【００４３】
そして、ステップＳ０５１０において、署名（ｃ，ｄ）を出力する。
以上のＥＣＤＳＡ署名生成処理によって生成された署名を、ネットワークを通じて情報処理装置２０００に送信する。
【００４４】
次に、情報処理装置２０００によって実行される、ＥＣＤＳＡによるディジタル署名が検証されるシーケンスについて、図面を用いて説明する。
まず、外部入力に起因して、情報処理制御部２３００にて、署名検証を行う対象となるメッセージならびに署名データを楕円曲線暗号処理部２１００に入力する。そして、楕円曲線暗号処理部２１００によって、ＥＣＤＳＡ署名検証処理が実行される。
【００４５】
図６は、楕円曲線暗号処理部２１００におけるＥＣＤＳＡ署名検証処理の流れを示すフローチャートである。
まず、ステップＳ０６０１において、パラメータ保持部１１３０から楕円曲線ドメインパラメータ（ｐ，ａ，ｂ，ｒ，Ｇ）および補助パラメータ（ｍ，ｎ，Ｇn，Ｇn+1）を読み込む。また、公開鍵保持部２１４０から公開鍵Ｗを読み込む。なお、パラメータｐ，ａ，ｂ，ｒ，Ｇ，ｍ，ｎ，Ｇn，Ｇn+1については、上述のＥＣＤＳＡ署名生成処理の説明と同様である。
【００４６】
次に、ステップＳ０６０２において、ネットワークを通じて情報処理装置１０００から送信されてきた署名（ｃ，ｄ）を読み込む。
そして、ステップＳ０６０３において、ｃ∈[１，ｒ−１]かつｄ∈[１，ｒ−１]であるか否かを比較演算部２１６０によって判断する。
【００４７】
ｃ∈[１，ｒ−１]かつｄ∈[１，ｒ−１]であるならば（ステップＳ０６０３：ｙｅｓ）、ステップＳ０６０４へ進み、ｃ∈[１，ｒ−１]かつｄ∈[１，ｒ−１]でないならば（ステップＳ０６０３：ｎｏ）、ステップＳ０６１１へ進む。
【００４８】
次に、ステップＳ０６０４において、メッセージＭを読み込み、ステップＳ０６０５において、ハッシュ値ｆ＝Ｈ（Ｍ）をハッシュ値計算部２１２０によって計算する。
そして、ステップＳ０６０６において、ｄ-1を剰余逆元演算部２１８０によって計算し、ｈ1＝ｆｄ-1 mod ｒおよびｈ2＝ｃｄ-1 mod ｒを剰余乗算演算部２１９０によって計算する。
【００４９】
次に、ステップＳ０６０７において、Ｑ＝ｈ1Ｇ＋ｈ2Ｗを楕円曲線スカラー倍算装置２１１０により計算する。
そして、ステップＳ０６０８において、Ｑが０であるか（Ｑ＝０）否かを判断する。
【００５０】
Ｑ＝０であるならば（ステップＳ０６０８：ｙｅｓ）、ステップＳ０６１１へ進み、Ｑ＝０でなければ（ステップＳ０６０８：ｎｏ）、ステップＳ０６０９へ進む。
次に、ステップＳ０６０９において、ｃ´＝Ｑx mod ｒを剰余演算部２１７０によって計算し、ｃがｃ´であるか（ｃ＝ｃ´）否かを判断する。
【００５１】
ｃ＝ｃ´であるならば（Ｓ０６０９：ｙｅｓ）、ステップＳ０６１０へ進み、ｃ＝ｃ´でなければ（Ｓ０６０９：ｎｏ）、ステップＳ０６１１へ進む。
そして、ステップＳ０６１０において、”署名は有効”を出力し、ステップＳ０６１１において、”署名は無効”を出力する。
【００５２】
以上のＥＣＤＳＡ署名検証処理によって署名検証結果を得る。
次に、楕円曲線スカラー倍算装置１１１０によって実行される、楕円曲線スカラー倍算シーケンスについて、図面を用いて説明する。
【００５３】
図７乃至図１１は、楕円曲線スカラー倍算装置１１１０における楕円曲線スカラー倍算演算処理の流れを示すフローチャートである。
まず、図７のステップＳ０７０１において、入出力インターフェイス１１１２を介して、楕円曲線ドメインパラメータｒ、補助パラメータ（ｍ，ｎ，Ｇn，Ｇn+1）、スカラー値ｅ、および楕円曲線上の点Ｐを読み込む。
【００５４】
そして、ステップＳ０７０２において、ｅが０より大きく［ｒ／２］より小さいか（０＜ｅ＜［ｒ／２］）否かを判断する。
０＜ｅ＜［ｒ／２］であるならば（ステップＳ０７０２：ｙｅｓ）、図８のステップＳ０８０１へ進み、０＜ｅ＜［ｒ／２］でなければ（ステップＳ０７０２：ｎｏ）、ステップＳ０７０３へ進む。
【００５５】
そして、ステップＳ０７０３において、ｒ−ｅをｅに変換し，−ＰをＰに変換する。
次に、図８のステップＳ０８０１において、変数ｖに０を設定し、変数ｉにｎを設定し、変数ｏｆｆｓに１を設定し、Ｔ［０］に０を設定し、Ｔ［１］にＧnを設定し、Ｔ［２］にＧn+1を設定する。
【００５６】
そして、ステップＳ０８０２において、ｉが０より大きいか（ｉ＞０）否かを判断する。
ｉが０より大きいならば（ステップＳ０８０２：ｙｅｓ）、ステップＳ０８０３へ進み、ｉが０より大きくないならば（ステップＳ０８０２：ｎｏ）、図９のステップＳ０９０１へ進む。ステップＳ０９０１以降については後述する。
【００５７】
ステップＳ０８０３において、ｅがＴ［ｏｆｆｓ］より小さいか（ｅ＜Ｔ［ｏｆｆｓ］）否かを判断する。
ｅがＴ［ｏｆｆｓ］より小さいならば（ステップＳ０８０３：ｙｅｓ）、ステップＳ０８０４へ進み、ステップＳ０８０４において、ｆｌｇに０を設定する。
【００５８】
ｅがＴ［ｏｆｆｓ］より小さくないならば（ステップＳ０８０３：ｎｏ）ステップＳ０８０５へ進み、ステップＳ０８０５において、ｆｌｇに１を設定する。
そして、ステップＳ０８０６において、ｅにｅ−Ｔ［ｆｌｇ×ｏｆｆｓ］の計算結果を設定し、ｔｍｐに３−ｏｆｆｓの計算結果を設定し、Ｔ［ｔｍｐ］にＴ［ｔｍｐ］−Ｔ［
ｏｆｆｓ］の計算結果を設定し、ｏｆｆｓにｔｍｐを設定する。
【００５９】
次に、ステップＳ０８０７において、ｉｎｄｅｘ［ｖ＋１］にｉを設定し、ｌｉｎｋ［ｖ＋１］にｖ＋２の計算結果を設定し、ｖにｖ＋ｆｌｇの計算結果を設定し、これらをインデックス記憶部１１１５に格納する。
【００６０】
そして、ステップＳ０８０８において、変数ｉを１インクリメントし、ステップＳ０８０２へ戻り、ステップＳ０８０２以降を繰り返す。
上述のステップＳ０８０２でｉが０より大きくないと判断された場合（ステップＳ０８０２：ｎｏ）は、図９のステップＳ０９０１において、変数ｊにｍを設定する。
【００６１】
そして、ステップＳ０９０２において、ｊが０より大きいか（ｊ＞０）否かを判断する。
ｊが０より大きいならば（ステップＳ０９０２：ｙｅｓ）、ステップＳ０９０３へ進み、ｊが０より大きくないならば（ステップＳ０９０２：ｎｏ）、図１０のステップＳ１００１へ進む。ステップＳ１００１以降については後述する。
【００６２】
ステップＳ０９０３において、ｖがｍと等しいか（ｖ＝ｍ）否かを判断する。
ｖがｍと等しいならば（ステップＳ０９０３：ｙｅｓ）、ステップＳ０９０４へ進み、ステップＳ０９０４において、ｆｌｇに０を設定する。
【００６３】
ｖがｍと等しくないならば（ステップＳ０９０３：ｎｏ）ステップＳ０９０５へ進み、ステップＳ０９０５において、ｆｌｇに１を設定する。
そして、ステップＳ０９０６において、［１，ｖ］の範囲で乱数ｋをランダムに選択する。
【００６４】
次に、ステップＳ０９０７において、ｉｎｄｅｘ［ｋ］にｉｎｄｅｘ［ｋ］−ｆｌｇの計算結果を設定し、ｉｎｄｅｘ［ｖ＋１］にｉｎｄｅｘ［ｋ］−ｆｌｇ×２の計算結果を設定し、ｌｉｎｋ［ｖ＋１］にｌｉｎｋ［ｋ］を設定し、ｌｉｎｋ［ｋ］にｆｌｇ×（ｖ＋１）＋（１−ｆｌｇ）×ｌｉｎｋ［ｋ］の計算結果を設定し、ｖにｖ＋ｆｌｇの計算結果を設定する。
【００６５】
そして、ステップＳ０９０８において、変数ｊを１インクリメントし、ステップＳ０９０２へ戻り、ステップＳ０９０２以降を繰り返す。
上述のステップＳ０９０２でｊが０より大きくないと判断された場合（ステップＳ０９０２：ｎｏ）は、図１０のステップＳ１００１において、ｐｒｅｃａｌｃ［１］にＰを設定して、事前計算結果記憶部１１１８に格納し、ｐｒｅｃａｌｃ［２］に２Ｐを設定して、楕円曲線２倍算処理部１１２１によって計算の後、事前計算結果記憶部１１１８に格納する。
【００６６】
次に、ステップＳ１００２において、変数ｉに２を設定する。
そして、ステップＳ１００３において、ｉがｎより小さいか（ｉ＜ｎ）否かを判断する。
【００６７】
ｉがｎより小さいならば（ステップＳ１００３：ｙｅｓ）、ステップＳ１００４へ進み、ｉがｎより小さくないならば（ステップＳ１００３：ｎｏ）、ステップＳ１１０１へ進む。
【００６８】
ステップＳ１００４において、楕円曲線加算処理部１１１９によってｐｒｅｃａｌｃ［ｉ］＋ｐｒｅｃａｌｃ［ｉ−１］を計算し、ｐｒｅｃａｌｃ［ｉ＋１］にその計算結果を
設定する。
【００６９】
そして、ステップＳ１００５において、変数ｉを１インクリメントし、ステップＳ１００３へ戻り、ステップＳ１００３以降を繰り返す。
上述のステップＳ１００３でｉがｎより大きくないと判断された場合（ステップＳ１００３：ｎｏ）は、図１１のステップＳ１１０１において、変数ＱにＯを設定し、ステップＳ１１０２において、ｊにｍを設定し、ｋに１を設定する。
【００７０】
次に、ステップＳ１１０３において、ｊが０より大きいか（ｊ＞０）否かを判断する。
ｊが０より大きいならば（ステップＳ１１０３：ｙｅｓ）、ステップＳ１１０４へ進み、ｊが０より大きくないならば（ステップＳ１１０３：ｎｏ）、ステップＳ１００６へ進む。
【００７１】
ステップＳ１１０４において、楕円曲線加算処理部１１１９によってＱ＋ｐｒｅｃａｌｃ［ｉｎｄｅｘ［ｋ］］を計算し、Ｑにその結果を設定し、ｋにはｌｉｎｋ［ｋ］を設定する。
【００７２】
そして、ステップＳ１１０５において、変数ｊを１インクリメントし、ステップＳ１１０３へ戻り、ステップＳ１１０３以降を繰り返す。
上述のステップＳ１１０３でｊが０より大きくないと判断された場合（ステップＳ１１０３：ｎｏ）は、ステップＳ１１０６において、Ｑを出力し、本楕円曲線スカラー倍算演算処理を終了する。
【００７３】
上述したように、楕円曲線スカラー倍算装置１１１０または楕円曲線スカラー倍算装置２１１０においては、楕円曲線２倍算の演算回数は１回であり、楕円曲線加算演算の回数は、ｎ＋［（ｎ＋１）／２］−３回である。ｎについては、楕円曲線の最大素数位数ｒに応じて固定されるため、楕円曲線加算演算の回数は一定である。また、楕円曲線２倍算は、事前計算テーブル作成時の一回だけ呼び出され、後は楕円曲線加算しか呼び出されない。よって、演算パターンは一定回数の楕円曲線加算演算の繰り返しであり、このことによりサイドチャネル攻撃対策となる。
【００７４】
以上、本発明の実施の形態を、図面を参照しながら説明してきたが、上述してきた本発明の実施の形態は、情報処理装置および楕円曲線スカラー倍算計算装置の一機能としてハードウェアまたはＤＳＰ（Digital Signal Processor）ボードやＣＰＵボードでのファームウェアもしくはソフトウェアにより実現することができる。
【００７５】
また、本発明が適用される情報処理装置および楕円曲線スカラー倍算計算装置は、その機能が実行されるのであれば、上述の実施の形態に限定されることなく、単体の装置であっても、複数の装置からなるシステムあるいは統合装置であっても、ＬＡＮ、ＷＡＮ等のネットワークを介して処理が行なわれるシステムであってもよいことは言うまでもない。
【００７６】
また、バスに接続されたＣＰＵ、ＲＯＭやＲＡＭのメモリ、入力装置、出力装置、外部記録装置、媒体駆動装置、ネットワーク接続装置で構成されるシステムでも実現できる。すなわち、前述してきた実施の形態のシステムを実現するソフトェアのプログラムを記録したＲＯＭやＲＡＭのメモリ、外部記録装置、可搬記録媒体を、情報処理装置および楕円曲線スカラー倍算計算装置に供給し、その情報処理装置および楕円曲線スカラー倍算計算装置のコンピュータがプログラムを読み出し実行することによっても、達成されることは言うまでもない。
【００７７】
この場合、可搬記録媒体等から読み出されたプログラム自体が本発明の新規な機能を実
現することになり、そのプログラムを記録した可搬記録媒体等は本発明を構成することになる。
【００７８】
プログラムを供給するための可搬記録媒体としては、例えば、フレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、ＤＶＤ−ＲＯＭ、ＤＶＤ−ＲＡＭ、磁気テープ、不揮発性のメモリーカード、ＲＯＭカード、電子メールやパソコン通信等のネットワーク接続装置（言い換えれば、通信回線）を介して記録した種々の記録媒体などを用いることができる。
【００７９】
また、コンピュータ（情報処理装置）がメモリ上に読み出したプログラムを実行することによって、前述した実施の形態の機能が実現される他、そのプログラムの指示に基づき、コンピュータ上で稼動しているＯＳなどが実際の処理の一部または全部を行ない、その処理によっても前述した実施の形態の機能が実現される。
【００８０】
さらに、可搬型記録媒体から読み出されたプログラムやプログラム（データ）提供者から提供されたプログラム（データ）が、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行ない、その処理によっても前述した実施の形態の機能が実現され得る。
【００８１】
すなわち、本発明は、以上に述べた実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲内で種々の構成または形状を取ることができる。
【符号の説明】
【００８２】
７００        ディスプレイ
８００        キーボード
９００        記憶装置
１０００      情報処理装置
１１００      楕円曲線暗号処理部
１１１０      楕円曲線スカラー倍算装置
１１１１      楕円曲線スカラー倍算処理制御部
１１１２      入出力インターフェイス
１１１３      事前調整部
１１１４      インデックス変換処理部
１１１５      インデックス記憶部
１１１６      事前計算部
１１１７      総和計算処理部
１１１８      事前計算結果記憶部
１１１９      楕円曲線加算処理部
１１２０      ハッシュ値計算部
１１２１      楕円曲線２倍算処理部
１１３０      パラメータ保持部
１１４０      秘密鍵保持部
１１５０      乱数生成部
１１６０      比較演算部
１１７０      剰余演算部
１１８０      剰余逆元演算部
１１９０      剰余乗算演算部
１１９５      剰余加算演算部
１２００      入出力インターフェイス
１３００      情報処理制御部
１７００      ディスプレイ
１８００      キーボード
１９００      記憶装置
２０００      情報処理装置
２１００      楕円曲線暗号処理部
２１１０      楕円曲線スカラー倍算装置
２１２０      ハッシュ値計算部
２１３０      パラメータ保持部
２１４０      秘密鍵保持部
２１６０      比較演算部
２１７０      剰余演算部
２１８０      剰余逆元演算部
２１９０      剰余乗算演算部
２１９５      剰余加算演算部
２２００      入出力インターフェイス
２３００      情報処理制御部
【図１】
2011085750.tif 000003
【図２】
2011085750.tif 000004
【図３】
2011085750.tif 000005
【図４】
2011085750.tif 000006
【図５】
2011085750.tif 000007
【図６】
2011085750.tif 000008
【図７】
2011085750.tif 000009
【図８】
2011085750.tif 000010
【図９】
2011085750.tif 000011
【図１０】
2011085750.tif 000012
【図１１】
2011085750.tif 000013