(57)【要約】【課題】効率的な楕円曲線スカラ倍演算を行うことを目的とする。【解決手段】拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した素数位数の点である前記第１の点および任意の整数が入力されると、前記整数を２進数展開し、前記展開した２進数の係数ごとに、（ａ）前記第１の点を、Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した点に置換した上で、前記変換した第１の点の２倍算を行い、前記２倍算の結果を拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した素数位数の点である第３の点に変換し、（ｂ）前記係数が１である場合、前記第１の点と、前記第３の点の加算処理を行う。【選択図】図１
2010266765.tif 000002
【特許請求の範囲】
【請求項１】
Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を拡張した拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した素数位数の点である第１の点を整数倍して、Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した第２の点を算出する楕円曲線スカラ倍演算装置による楕円曲線スカラ倍演算方法であって、
入力部を介して、前記第１の点および任意の整数が入力されると、
楕円曲線スカラ倍演算装置が、
前記整数を２進数展開し、前記展開した２進数の係数ごとに、（ａ）および（ｂ）の処理を行うことを特徴とする楕円曲線スカラ倍演算方法。
（ａ）前記第１の点を、Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した点に置換した上で、前記変換した第１の点の２倍算を行い、前記２倍算の結果を拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した素数位数の点である第３の点に変換し、
（ｂ）前記係数が１である場合、前記第１の点と、前記第３の点の加算処理を行う。
【請求項２】
Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の任意の点Ｐのスカラ倍演算（Ｑ＝ＬＰ）を行なう楕円スカラ倍演算装置による楕円曲線スカラ倍演算方法であって、
前記楕円スカラ倍演算装置が、
入力部を介して、
標数が２と異なる有限体ｋを定義体とするＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線ａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）に関する情報、楕円曲線上の点（ｘ1，ｙ1）において、ｘ1＝Ｚ1／Ｘ1、ｙ1＝Ｚ1／Ｙ1、ｘ1ｙ1＝Ｚ1／Ｔ1、Ｘ1Ｙ1Ｔ1Ｚ1≠０を満たすＸ1，Ｙ1，Ｔ1，Ｚ1∈ｋを用いて表現する拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標における素数位数の点Ｐ＝（Ｘ1：Ｙ1：Ｔ1：Ｚ1）、整数Ｌ（Ｌ＞０）、および楕円曲線の２点の加算を行う際に係数ｄを用いるか否かの入力情報が入力されると、
（ａ１）前記整数Ｌを２進数展開して、Ｌ＝Ｌ0＋Ｌ1×２＋・・・＋Ｌt-1×２t-1（Ｌt-1＝１）とし、
（ａ２）ｄ1←２ｄ、ｉ←ｔ−２、Ｑ←Ｐとおき、
（ａ３）前記ｉ＝−１であるか否かを判定し、ｉ＝−１であれば（ａ９）の処理へ進み、ｉ＝−１でなければ（ａ４）の処理へ進み、
（ａ４）Ｑ←２Ｑを計算し、
（ａ５）前記Ｌｉ＝１であるか否かを判定し、Ｌi＝１であれば、（ａ６）の処理へ進み、Ｌi＝１でなければ、（ａ７）の処理へ進み、
（ａ６）Ｑ←Ｑ＋Ｐを計算し、
（ａ７）ｉ←ｉ−１を計算し、
（ａ８）ｉ≧０であるか否かを判定し、ｉ≧０であれば、前記（ａ４）の処理へ戻り、ｉ≧０でなければ（ａ９）の処理へ進み、
（ａ９）Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）を計算結果とする
ことを特徴とする楕円曲線スカラ倍演算方法。
【請求項３】
前記楕円曲線スカラ倍演算装置が、
前記（ａ４）の処理において、
（ｂ１）Ｑ＝（Ｘ2：Ｙ2：Ｔ2：Ｚ2）であれば、ＱをＱ←（Ｘ2：Ｙ2：Ｚ2）におき直し、
（ｂ２）Ａ←Ｘ22、Ｂ←Ｙ22、Ｕ←ａＢをそれぞれｋ上で計算し、
（ｂ３）Ｃ←Ａ＋Ｕ、Ｄ←Ａ−Ｕ、Ｅ←（Ｘ2＋Ｙ2）2−Ａ−Ｂ、Ｈ←（Ｃ−ｄ1Ｚ22）をそれぞれｋ上で計算し、
（ｂ４）Ｘ3←ＣＤをｋ上で計算し、
（ｂ５）Ｙ3←ＥＨをｋ上で計算し、
（ｂ６）Ｌi＝１であれば、Ｔ3←ＣＨをｋ上で計算し、
（ｂ７）Ｚ3←ＤＥをｋ上で計算し、
（ｂ８）前記（ｂ６）の処理において、Ｔ3←ＣＨを計算している場合、２倍算の演算結果を前記拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｔ3：Ｚ3）とおき、前記（ｂ６）の処理において、Ｔ3←ＣＨを計算していない場合、前記Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とおく
ことを特徴とする請求項２に記載の楕円曲線スカラ倍演算方法。
【請求項４】
前記楕円曲線の２点の加算を行う際に前記係数ｄを用いる旨の情報が、前記入力部を介して入力されると、
前記楕円曲線スカラ倍演算装置が、
前記（ａ６）の処理において、
（ｃ１）Ａ←Ｘ1Ｘ2、Ｂ←Ｙ1Ｙ2、Ｄ←Ｔ1Ｔ2をｋ上でそれぞれ計算し、
（ｃ２）Ｚ１＝１であるか否かを判定し、Ｚ1＝１であれば、（ｃ３）の処理へ進み、Ｚ1＝１でなければ、（ｃ４）の処理へ進み、
（ｃ３）Ｃ←ｄＺ2をｋ上で計算し、（ｃ５）の処理へ進み、
（ｃ４）Ｃ←ｄＺ1Ｚ2をｋ上で計算し、（ｃ５）の処理へ進み、
（ｃ５）Ｅ←（Ｘ1＋Ｙ1）（Ｘ2＋Ｙ2）−Ａ−Ｂをｋ上で計算し、
（ｃ６）Ｆ←Ｄ−Ｃ，Ｇ←Ｄ＋Ｃ，Ｈ←Ａ−ａＢをｋ上でそれぞれ計算し、
（ｃ７）Ｘ3←ＨＧをｋ上で計算し、
（ｃ８）Ｙ3←ＥＦをｋ上で計算し、
（ｃ９）Ｚ3←ＨＥをｋ上で計算し、
（ｃ１０）演算結果を前記Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とおく
ことを特徴とする請求項２に記載の楕円曲線スカラ倍演算方法。
【請求項５】
前記ａの値が−１かつ前記楕円曲線の２点の加算を行う際に前記係数ｄを用いる旨の情報が、前記入力部を介して入力されると、
前記楕円曲線スカラ倍演算装置が、
前記（ａ６）の処理において、
（ｄ１）Ａ←（Ｘ1＋Ｙ1）（Ｘ2＋Ｙ2）、Ｂ←（Ｘ1−Ｙ1）（Ｘ2−Ｙ2）、Ｄ＝２Ｔ1Ｔ2  をｋ上でそれぞれ計算し、
（ｄ２）Ｚ1＝１であるか否かを判定し、Ｚ1＝１であれば、（ｄ３）の処理へ進み、Ｚ1＝１でなければ、（ｄ４）の処理へ進み、
（ｄ３）Ｃ←ｄ1Ｚ2をｋ上で計算し、（ｄ５）の処理へ進み、
（ｄ４）Ｃ←ｄ1Ｚ1Ｚ2をｋ上で計算し、、（ｄ５）の処理へ進み、
（ｄ５）Ｅ＝Ａ−Ｂ、Ｆ＝Ｄ−Ｃ、Ｇ＝Ｄ＋Ｃ、Ｈ＝Ａ＋Ｂをそれぞれｋ上で計算し、
（ｄ６）Ｘ3＝ＨＧをｋ上で計算し、
（ｄ７）Ｙ3＝ＥＦをｋ上で計算し、
（ｄ８）Ｚ3＝ＨＥをｋ上で計算し、
（ｄ９）演算結果を前記Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とおく
ことを特徴とする請求項２に記載の楕円曲線スカラ倍演算方法。
【請求項６】
前記楕円曲線の２点の加算を行う際に前記係数ｄを用いない旨の情報が、前記入力部を介して入力されると、
前記楕円曲線スカラ倍演算装置が、
前記（ａ６）の処理において、
（ｅ１）Ａ←Ｘ1Ｘ2、Ｂ←Ｙ1Ｙ2、Ｄ←Ｔ1Ｚ2をｋ上でそれぞれ計算し、
（ｅ２）Ｚ1＝１であるか否かを判定し、Ｚ1＝１であれば、（ｅ３）の処理へ進み、Ｚ1＝１でなければ、（ｅ４）の処理へ進み、
（ｅ３）Ｃ←Ｔ2とおき、（ｅ５）の処理へ進み、
（ｅ４）Ｃ←Ｚ1Ｔ2をｋ上で計算し、（ｅ５）の処理へ進み、
（ｅ５）Ｅ←（Ｘ1＋Ｙ1）（Ｘ2−Ｙ2）＋Ｂ−Ａをｋ上で計算し、
（ｅ６）Ｆ←Ｃ＋Ｄ，Ｇ←Ｃ−Ｄ，Ｈ←Ａ＋ａＢをｋ上でそれぞれ計算し、
（ｅ７）Ｘ3←ＨＧをｋ上で計算し、
（ｅ８）Ｙ3←ＥＦをｋ上で計算し、
（ｅ９）Ｚ3←ＦＧをｋ上で計算し、
（ｅ１０）演算結果を前記Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とおく
ことを特徴とする請求項２に記載の楕円曲線スカラ倍演算方法。
【請求項７】
前記ａの値が−１かつ前記楕円曲線の２点の加算を行う際にｄを用いない旨の情報が、前記入力部を介して入力されると、
前記楕円曲線スカラ倍演算装置が、
前記（ａ６）の処理において、
（ｆ１）Ａ←（Ｘ1−Ｙ1）（Ｘ2＋Ｙ2）、Ｂ←（Ｘ1＋Ｙ1）（Ｘ2−Ｙ2）、Ｄ←２Ｔ1Ｚ2をｋ上でそれぞれ計算し、
（ｆ２）Ｚ1＝１であるか否かを判定し、Ｚ1＝１であれば、（ｆ３）の処理へ進み、Ｚ1＝１でなければ、（ｆ４）の処理へ進み、
（ｆ３）Ｃ←２Ｔ2とおき、（ｆ５）の処理へ進み、
（ｆ４）Ｃ←２Ｚ1Ｔ2をｋ上で計算し、（ｆ５）の処理へ進み、
（ｆ５）Ｅ←Ａ＋Ｂ、Ｆ←Ｃ＋Ｄ，Ｇ←Ｃ−Ｄ，Ｈ←Ｂ−Ａをｋ上でそれぞれ計算し、
（ｆ６）Ｘ3←ＥＧをｋ上で計算し、
（ｆ７）Ｙ3←ＨＦをｋ上で計算し、
（ｆ８）Ｚ3←ＦＧをｋ上で計算し、
（ｆ９）演算結果をＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とおく
ことを特徴とする請求項２に記載の楕円曲線スカラ倍演算方法。
【請求項８】
ＥＣＤＳＡ署名を利用したＥＣＤＳＡ鍵ペア生成装置によるＥＣＤＳＡ鍵ペア生成方法であって、
入力部を介して、楕円曲線のパラメータａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）、定義体ｋ、ベースポイントＧ＝（ＸG：ＹG：ＴG：１）およびその位数ｎ、楕円曲線の２点の加算を行う際に前記係数ｄを用いるか否かの入力情報が入力されると、
前記ＥＣＤＳＡ鍵ペア生成装置が、
（ｇ１）０＜ｃ＜ｎを満たす整数ｃをランダムに生成し秘密鍵とし、
（ｇ２）請求項１から請求項７のいずれか一項に記載の楕円曲線スカラ倍演算方法を行うことによって、Ｑ１＝ｃＧ＝（Ｘ：Ｙ：Ｚ）を計算し、
（ｇ３）Ｑ←（ＸQ：ＹQ：ＴQ：１）＝（Ｘ／Ｚ：Ｙ／Ｚ：ＸＹ／Ｚ2：１）をｋ上で計算することでＱ1を拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標への変換し計算結果Ｑを公開鍵とし、
（ｇ４）鍵ペアを（ｃ、Ｑ）とする
ことを特徴とするＥＣＤＳＡ鍵ペア生成方法。
【請求項９】
ＥＣＤＳＡ署名を利用したＥＣＤＳＡ署名生成装置によるＥＣＤＳＡ署名生成方法であって、
入力部を介して、楕円曲線のパラメータａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）、定義体ｋ、ベースポイントＧ＝（ＸG：ＹG：ＴG：１）およびその位数ｎ、楕円曲線の２点の加算を行う際に前記係数ｄを用いるか否かの情報、秘密鍵ｃ、署名対象の平文Ｍの入力情報が入力されると、
前記ＥＣＤＳＡ署名生成装置が、
（ｈ１）０＜ｂ＜ｎを満たす整数ｂをランダムに生成し、
（ｈ２）請求項１から請求項７のいずれか一項に記載の楕円曲線スカラ倍演算方法を行って、Ｒ←ｂＧ＝（Ｘ1：Ｙ1：Ｚ1）を計算し、
（ｈ３）ｘ1←Ｚ1／Ｘ1をｋ上で計算し、
（ｈ４）ｋ上の元ｘ1を正の整数に変換したものをｘ1としておき直し、
（ｈ５）ｒ←ｘ1  ｍｏｄ  ｎ  を計算し、
（ｈ６）ハッシュ関数ｈを用いて、ｅ←ｈ（Ｍ）を計算し、
（ｈ７）ｓ←ｂ-1（ｅ＋ｃｒ）  ｍｏｄ  ｎを計算し、
（ｈ８）（ｒ，ｓ）をＥＣＤＳＡ署名とする
ことを特徴とするＥＣＤＳＡ署名生成方法。
【請求項１０】
請求項９に記載のＥＣＤＳＡ署名生成方法によって生成されたＥＣＤＳＡ署名を利用したＥＣＤＳＡ署名検証装置によるＥＣＤＳＡ署名検証方法であって、
入力部を介して、楕円曲線のパラメータａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）、定義体ｋ、ベースポイントＧ＝（ＸG：ＹG：ＴG：１）およびその位数ｎ、楕円曲線の２点の加算を行う際に前記係数ｄを用いるか否かの情報、公開鍵Ｑ＝（ＸQ：ＹQ：ＴQ：１）、前記ＥＣＤＳＡ署名（ｒ，ｓ）、署名検証対象の平文Ｍが入力情報として入力されると、
前記ＥＣＤＳＡ署名検証装置が、
（ｉ１）署名生成時と同じハッシュ関数ｈを用いて、ｅ←ｈ（Ｍ）を計算し、
（ｉ２）ｅ1←  ｓ-1ｅ  ｍｏｄ  ｎを計算し、
（ｉ３）ｒ1←  ｓ-1ｒ  ｍｏｄ  ｎを計算し、
（ｉ４）請求項１から請求項７のいずれか一項に記載の楕円曲線スカラ倍演算方法を行って、Ｇ1←（ＸG1：ＹG1：ＺG1）＝ｅ1Ｇを計算し、
（ｉ５）請求項１から請求項７のいずれか一項に記載の楕円曲線スカラ倍演算方法を行って、Ｑ1←（ＸQ1：ＹQ1：ＺQ1）＝ｒ1Ｑを計算し、
（ｉ６）（Ｘ1：Ｙ1：Ｚ1）＝Ｇ1＋Ｑ1のうちＸ1、Ｚ1を計算し、
（ｉ７）ｘ1←Ｚ1／Ｘ1をｋ上で計算し、
（ｉ８）定義体ｋ上の元ｘ1を正の整数に変換したものをｘ1としておき直し、
（ｉ９）ｘ1  ｍｏｄ  ｎ  ＝  ｒが成立するか否かの検証を行い、成立すれば検証結果をＴｒｕｅ、しなければ検証結果をＦａｌｓｅとする
ことを特徴とするＥＣＤＳＡ署名検証方法。
【請求項１１】
前記ＥＣＤＳＡ署名検証装置が、
前記（ｉ６）の処理において、
（ｊ１）Ａ←ＺG1ＺQ1、Ｂ←ｄＡ2、Ｃ←ＸG1ＸQ1、Ｄ←ＹG1ＹQ1、Ｅ←ＣＤをｋ上でそれぞれ計算し、
（ｊ２）Ｈ←Ｃ−ａＤ、Ｉ←（ＸG1＋ＹG1）（ＸQ1＋ＹQ1）−Ｃ−Ｄをｋ上でそれぞれ計算し、
（ｊ３）Ｘ1←（Ｅ＋Ｂ）Ｈをｋ上で計算し、
（ｊ４）Ｚ1←ＡＨＩをｋ上で計算する
ことを特徴とする請求項１０に記載のＥＣＤＳＡ署名検証方法。
【請求項１２】
請求項１から請求項７のいずれか一項に記載の楕円曲線スカラ倍演算方法、請求項８に記載のＥＣＤＳＡ鍵ペア生成方法、請求項９に記載のＥＣＤＳＡ署名生成方法、請求項１０または請求項１１に記載のＥＣＤＳＡ署名検証方法のうちいずれか１つをコンピュータに実行させることを特徴とするプログラム。
【請求項１３】
Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を拡張した拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した素数位数の点である第１の点を整数倍して、Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した第２の点を算出する楕円曲線スカラ倍演算装置であって、
入力部を介して、前記第１の点および任意の整数が入力されると、
前記整数を２進数展開し、前記２進数の係数ごとに、（ａ）および（ｂ）の処理を行うことを特徴とする楕円曲線スカラ倍演算装置。
（ａ）前記第１の点を、Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した点に置換した上で、前記変換した第１の点の２倍算を行い、前記２倍算の結果を拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した素数位数の点である第３の点に変換し、
（ｂ）前記係数が１である場合、前記第１の点と、前記第３の点の加算処理を行う。
【請求項１４】
Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の任意の点Ｐのスカラ倍演算（Ｑ＝ＬＰ）を行なう楕円曲線スカラ倍演算装置であって、
２進数展開部と、楕円曲線加算演算部と、楕円曲線２倍算演算部と、基本演算部とを有し、
入力部を介して、
標数が２と異なる有限体ｋを定義体とするＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線ａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）に関する情報、楕円曲線上の点（ｘ1，ｙ1）において、ｘ1＝Ｚ1／Ｘ1、ｙ1＝Ｚ1／Ｙ1、ｘ1ｙ1＝Ｚ1／Ｔ1、Ｘ1Ｙ1Ｔ1Ｚ1≠０を満たすＸ1，Ｙ1，Ｔ1，Ｚ1∈ｋを用いて表現する拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標における素数位数の点Ｐ＝（Ｘ1：Ｙ1：Ｔ1：Ｚ1）、整数Ｌ（Ｌ＞０）、および楕円曲線の２点の加算を行う際に係数ｄを用いるか否かの入力情報が入力されると、
前記２進数展開部が、
前記整数Ｌを２進数展開して、Ｌ＝Ｌ0＋Ｌ1×２＋・・・＋Ｌt-1×２t-1（Ｌt-1＝１）とし、
前記基本演算部が、
（ａ２）ｄ1←２ｄ、ｉ←ｔ−２、Ｑ←Ｐとおき、
（ａ３）前記ｉ＝−１であるか否かを判定し、ｉ＝−１であれば（ａ９）の処理へ進み、ｉ＝−１でなければ（ａ４）の処理へ進み、
前記楕円曲線２倍算加算演算部が、
（ａ４）Ｑ←２Ｑを計算し、
前記基本演算部が、
（ａ５）前記Ｌｉ＝１であるか否かを判定し、Ｌi＝１であれば、（ａ６）の処理へ進み、Ｌi＝１でなければ、（ａ７）の処理へ進み、
前記楕円曲線加算演算部が、
（ａ６）Ｑ←Ｑ＋Ｐを計算し、
前記基本演算部が、
（ａ７）ｉ←ｉ−１を計算し、
（ａ８）ｉ≧０であるか否かを判定し、ｉ≧０であれば、前記（ａ４）の処理へ戻り、ｉ≧０でなければ（ａ９）の処理へ進み、
（ａ９）Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）を計算結果とする
ことを特徴とする楕円曲線スカラ倍演算装置。
【請求項１５】
前記楕円曲線２倍算加算演算部は、
（ｂ１）Ｑ＝（Ｘ2：Ｙ2：Ｔ2：Ｚ2）であれば、ＱをＱ←（Ｘ2：Ｙ2：Ｚ2）におき直し、
（ｂ２）Ａ←Ｘ22、Ｂ←Ｙ22、Ｕ←ａＢをそれぞれｋ上で計算し、
（ｂ３）Ｃ←Ａ＋Ｕ、Ｄ←Ａ−Ｕ、Ｅ←（Ｘ2＋Ｙ2）2−Ａ−Ｂ、Ｈ←（Ｃ−ｄ1Ｚ22）をそれぞれｋ上で計算し、
（ｂ４）Ｘ3←ＣＤをｋ上で計算し、
（ｂ５）Ｙ3←ＥＨをｋ上で計算し、
（ｂ６）Ｌi＝１であれば、Ｔ3←ＣＨをｋ上で計算し、
（ｂ７）Ｚ3←ＤＥをｋ上で計算し、
（ｂ８）前記（ｂ６）の処理において、Ｔ3←ＣＨを計算している場合、２倍算の演算結果を前記拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｔ3：Ｚ3）とおき、前記（ｂ６）の処理において、Ｔ3←ＣＨを計算していない場合、前記Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とおく
ことを特徴とする請求項１４に記載の楕円曲線スカラ倍演算装置。
【請求項１６】
前記楕円曲線の２点の加算を行う際に前記係数ｄを用いる旨の情報が、前記入力部を介して入力されると、
前記楕円曲線加算演算部は、
（ｃ１）Ａ←Ｘ1Ｘ2、Ｂ←Ｙ1Ｙ2、Ｄ←Ｔ1Ｔ2をｋ上でそれぞれ計算し、
（ｃ２）Ｚ１＝１であるか否かを判定し、Ｚ1＝１であれば、（ｃ３）の処理へ進み、Ｚ1＝１でなければ、（ｃ４）の処理へ進み、
（ｃ３）Ｃ←ｄＺ2をｋ上で計算し、（ｃ５）の処理へ進み、
（ｃ４）Ｃ←ｄＺ1Ｚ2をｋ上で計算し、（ｃ５）の処理へ進み、
（ｃ５）Ｅ←（Ｘ1＋Ｙ1）（Ｘ2＋Ｙ2）−Ａ−Ｂをｋ上で計算し、
（ｃ６）Ｆ←Ｄ−Ｃ，Ｇ←Ｄ＋Ｃ，Ｈ←Ａ−ａＢをｋ上でそれぞれ計算し、
（ｃ７）Ｘ3←ＨＧをｋ上で計算し、
（ｃ８）Ｙ3←ＥＦをｋ上で計算し、
（ｃ９）Ｚ3←ＨＥをｋ上で計算し、
（ｃ１０）演算結果を前記Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とおく
ことを特徴とする請求項１４に記載の楕円曲線スカラ倍演算装置。
【請求項１７】
前記ａの値が−１かつ前記楕円曲線の２点の加算を行う際に前記係数ｄを用いる旨の情報が、前記入力部を介して入力されると、
前記楕円曲線加算演算部は、
（ｄ１）Ａ←（Ｘ1＋Ｙ1）（Ｘ2＋Ｙ2）、Ｂ←（Ｘ1−Ｙ1）（Ｘ2−Ｙ2）、Ｄ＝２Ｔ1Ｔ2  をｋ上でそれぞれ計算し、
（ｄ２）Ｚ1＝１であるか否かを判定し、Ｚ1＝１であれば、（ｄ３）の処理へ進み、Ｚ1＝１でなければ、（ｄ４）の処理へ進み、
（ｄ３）Ｃ←ｄ1Ｚ2をｋ上で計算し、（ｄ５）の処理へ進み、
（ｄ４）Ｃ←ｄ1Ｚ1Ｚ2をｋ上で計算し、、（ｄ５）の処理へ進み、
（ｄ５）Ｅ＝Ａ−Ｂ、Ｆ＝Ｄ−Ｃ、Ｇ＝Ｄ＋Ｃ、Ｈ＝Ａ＋Ｂをそれぞれｋ上で計算し、
（ｄ６）Ｘ3＝ＨＧをｋ上で計算し、
（ｄ７）Ｙ3＝ＥＦをｋ上で計算し、
（ｄ８）Ｚ3＝ＨＥをｋ上で計算し、
（ｄ９）演算結果を前記Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とおく
ことを特徴とする請求項１４に記載の楕円曲線スカラ倍演算装置。
【請求項１８】
前記楕円曲線の２点の加算を行う際に前記係数ｄを用いない旨の情報が、前記入力部を介して入力されると、
前記楕円曲線加算演算部は、
（ｅ１）Ａ←Ｘ1Ｘ2、Ｂ←Ｙ1Ｙ2、Ｄ←Ｔ1Ｚ2をｋ上でそれぞれ計算し、
（ｅ２）Ｚ1＝１であるか否かを判定し、Ｚ1＝１であれば、（ｅ３）の処理へ進み、Ｚ1＝１でなければ、（ｅ４）の処理へ進み、
（ｅ３）Ｃ←Ｔ2とおき、（ｅ５）の処理へ進み、
（ｅ４）Ｃ←Ｚ1Ｔ2をｋ上で計算し、（ｅ５）の処理へ進み、
（ｅ５）Ｅ←（Ｘ1＋Ｙ1）（Ｘ2−Ｙ2）＋Ｂ−Ａをｋ上で計算し、
（ｅ６）Ｆ←Ｃ＋Ｄ，Ｇ←Ｃ−Ｄ，Ｈ←Ａ＋ａＢをｋ上でそれぞれ計算し、
（ｅ７）Ｘ3←ＨＧをｋ上で計算し、
（ｅ８）Ｙ3←ＥＦをｋ上で計算し、
（ｅ９）Ｚ3←ＦＧをｋ上で計算し、
（ｅ１０）演算結果を前記Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とおく
ことを特徴とする請求項１４に記載の楕円曲線スカラ倍演算装置。
【請求項１９】
前記ａの値が−１かつ前記楕円曲線の２点の加算を行う際に前記係数ｄを用いない旨の情報が、前記入力部を介して入力されると、
前記楕円曲線加算演算部は、
（ｆ１）Ａ←（Ｘ1−Ｙ1）（Ｘ2＋Ｙ2）、Ｂ←（Ｘ1＋Ｙ1）（Ｘ2−Ｙ2）、Ｄ←２Ｔ1Ｚ2をｋ上でそれぞれ計算し、
（ｆ２）Ｚ1＝１であるか否かを判定し、Ｚ1＝１であれば、（ｆ３）の処理へ進み、Ｚ1＝１でなければ、（ｆ４）の処理へ進み、
（ｆ３）Ｃ←２Ｔ2とおき、（ｆ５）の処理へ進み、
（ｆ４）Ｃ←２Ｚ1Ｔ2をｋ上で計算し、（ｆ５）の処理へ進み、
（ｆ５）Ｅ←Ａ＋Ｂ、Ｆ←Ｃ＋Ｄ，Ｇ←Ｃ−Ｄ，Ｈ←Ｂ−Ａをｋ上でそれぞれ計算し、
（ｆ６）Ｘ3←ＥＧをｋ上で計算し、
（ｆ７）Ｙ3←ＨＦをｋ上で計算し、
（ｆ８）Ｚ3←ＦＧをｋ上で計算し、
（ｆ９）演算結果をＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とおく
ことを特徴とする請求項１４に記載の楕円曲線スカラ倍演算装置。
【請求項２０】
ＥＣＤＳＡ署名を利用したＥＣＤＳＡ鍵ペア生成装置であって、
乱数生成部と、請求項１３から請求項１９のいずれか一項に記載の楕円曲線スカラ倍演算装置である楕円曲線スカラ倍演算部と、制御演算部と、を有し、
入力部を介して、楕円曲線のパラメータａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）、定義体ｋ、ベースポイントＧ＝（ＸG：ＹG：ＴG：１）およびその位数ｎ、楕円曲線の２点の加算を行う際に係数ｄを用いるか否かの入力情報が入力されると、
前記乱数生成部は、
（ｇ１）０＜ｃ＜ｎを満たす整数ｃをランダムに生成し秘密鍵とし、
前記楕円曲線スカラ倍演算部は、
（ｇ２）Ｑ１＝ｃＧ＝（Ｘ：Ｙ：Ｚ）を計算し、
（ｇ３）Ｑ←（ＸQ：ＹQ：ＴQ：１）＝（Ｘ／Ｚ：Ｙ／Ｚ：ＸＹ／Ｚ2：１）をｋ上で計算することでＱ1を前記拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標への変換し計算結果Ｑを公開鍵とし、
前記制御演算部が、
（ｇ４）鍵ペアを（ｃ、Ｑ）とする
ことを特徴とするＥＣＤＳＡ鍵ペア生成装置。
【請求項２１】
ＥＣＤＳＡ署名を利用したＥＣＤＳＡ署名生成装置であって、
乱数生成部と、ハッシュ関数演算部と、請求項１３から請求項１９のいずれか一項に記載の楕円曲線スカラ倍演算装置である楕円曲線スカラ倍演算部と、制御演算部と、を有し、
入力部を介して、楕円曲線のパラメータａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）、定義体ｋ、ベースポイントＧ＝（ＸG：ＹG：ＴG：１）およびその位数ｎ、楕円曲線の２点の加算を行う際に係数ｄを用いるか否か、秘密鍵ｃ、署名対象の平文Ｍの入力情報が入力されると、
前記乱数生成部は、
（ｈ１）０＜ｂ＜ｎを満たす整数ｂをランダムに生成し、
前記楕円曲線スカラ倍演算部は、
（ｈ２）Ｒ←ｂＧ＝（Ｘ1：Ｙ1：Ｚ1）を計算し、
（ｈ３）ｘ1←Ｚ1／Ｘ1をｋ上で計算し、
（ｈ４）ｋ上の元ｘ1を正の整数に変換したものをｘ1としておき直し、
（ｈ５）ｒ←ｘ1  ｍｏｄ  ｎ  を計算し、
ハッシュ関数演算部は、
（ｈ６）ハッシュ関数ｈを用いて、ｅ←ｈ（Ｍ）を計算し、
前記楕円曲線スカラ倍演算部は、
（ｈ７）ｓ←ｂ-1（ｅ＋ｃｒ）  ｍｏｄ  ｎを計算し、
前記制御演算部は、
（ｈ８）（ｒ，ｓ）をＥＣＤＳＡ署名とする
ことを特徴とするＥＣＤＳＡ署名生成装置。
【請求項２２】
請求項２１に記載のＥＣＤＳＡ署名生成装置によって生成されたＥＣＤＳＡ署名を利用するＥＣＤＳＡ署名検証装置であって、
ハッシュ関数演算部と、請求項１３から請求項１９のいずれか一項に記載の楕円曲線スカラ倍演算装置である楕円曲線スカラ倍演算部と、制御演算部と、を有し、
入力部を介して、楕円曲線のパラメータａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）、定義体ｋ、ベースポイントＧ＝（ＸG：ＹG：ＴG：１）およびその位数ｎ、楕円曲線の２点の加算を行う際に係数ｄを用いるか否か、公開鍵Ｑ＝（ＸQ：ＹQ：ＴQ：１）、前記ＥＣＤＳＡ署名（ｒ，ｓ）、署名検証対象の平文Ｍが入力情報として入力されると、
ハッシュ関数演算部は、
（ｉ１）書名生成時と同じハッシュ関数ｈを用いて、ｅ←ｈ（Ｍ）を計算し、
前記楕円曲線スカラ倍演算部は、
（ｉ２）ｅ1←  ｓ-1ｅ  ｍｏｄ  ｎを計算し、
（ｉ３）ｒ1←  ｓ-1ｒ  ｍｏｄ  ｎを計算し、
（ｉ４）Ｇ1←（ＸG1：ＹG1：ＺG1）＝ｅ1Ｇを計算し、
（ｉ５）Ｑ1←（ＸQ1：ＹQ1：ＺQ1）＝ｒ1Ｑを計算し、
（ｉ６）（Ｘ1：Ｙ1：Ｚ1）＝Ｇ1＋Ｑ1のうちＸ1、Ｚ1を計算し、
（ｉ７）ｘ1←Ｚ1／Ｘ1をｋ上で計算し、
（ｉ８）定義体ｋ上の元ｘ1を正の整数に変換したものをｘ1としておき直し、
前記制御演算部が、
（ｉ９）ｘ1  ｍｏｄ  ｎ  ＝  ｒが成立するか否かの検証を行い、成立すれば検証結果をＴｒｕｅ、しなければ検証結果をＦａｌｓｅとする
ことを特徴とするＥＣＤＳＡ署名検証装置。
【請求項２３】
前記楕円曲線スカラ倍演算部は、
（ｊ１）Ａ←ＺG1ＺQ1、Ｂ←ｄＡ2、Ｃ←ＸG1ＸQ1、Ｄ←ＹG1ＹQ1、Ｅ←ＣＤをｋ上でそれぞれ計算し、
（ｊ２）Ｈ←Ｃ−ａＤ、Ｉ←（ＸG1＋ＹG1）（ＸQ1＋ＹQ1）−Ｃ−Ｄをｋ上でそれぞれ計算し、
（ｊ３）Ｘ1←（Ｅ＋Ｂ）Ｈをｋ上で計算し、
（ｊ４）Ｚ1←ＡＨＩをｋ上で計算する
ことによって、前記Ｘ1、Ｚ1を計算する
ことを特徴とする請求項２２に記載のＥＣＤＳＡ署名検証装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線スカラ倍演算方法、ＥＣＤＳＡ鍵ペア生成方法、ＥＣＤＳＡ署名生成方法、ＥＣＤＳＡ署名検証方法、プログラム、楕円曲線スカラ倍演算装置、ＥＣＤＳＡ鍵ペア生成装置、ＥＣＤＳＡ署名生成装置およびＥＣＤＳＡ署名検証装置の技術に関する。
【背景技術】
【０００２】
楕円曲線上の離散対数問題を用いたデジタル署名方式としてＥＣＤＳＡ（Elliptic Curve Digital Signature Algorithm）署名が知られている。この署名方式は楕円曲線上の加算やスカラ倍算を用いて実現される（例えば、非特許文献１参照）。このため、特にスカラ倍算は署名の処理速度に大きく影響するため高速処理が重要な課題となる。
スカラ倍の高速処理に適した楕円曲線としてＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線が知られている（例えば、非特許文献２参照）。
【０００３】
まず、非特許文献２に基づきＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線について説明する。
Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線とは標数が２以外の有限体をｋとした場合、ａｘ2＋ｙ2＝１＋ｄｘ2ｙ2  （ａ，ｄはｋ上の定数）で表される曲線で曲線上の点は、曲線の方程式を満たすｘ，ｙ∈ｋの組（ｘ，ｙ）で表すことができる。
【０００４】
ｋ上で係数ａは２乗根を持ち係数ｄは持たない場合、Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の２点Ｐ，Ｑに対して加算Ｐ＋Ｑが、１点Ｐに対して２倍算２Ｐが定義でき具体的な計算方法が知られている。
Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の２点Ｐ＝（ｘ1，ｙ1）、Ｑ＝（ｘ2，ｙ2）に対して加算は以下の式（１）で計算することができる。
【０００５】
【数１】
2010266765.tif 000003
【０００６】
さらに点Ｐ＝（ｘ1，ｙ1）に対して２倍算は上記加算公式においてＰ＝Ｑとすることで計算できる。以下に示す式（２）は２倍算に特化した形で前記した加算公式（式（１））を記載したものである。
【０００７】
【数２】
2010266765.tif 000004
【０００８】
また、点Ｐ＝（ｘ1，ｙ1）に対して−Ｐを（−ｘ1，ｙ1）で定義する。
Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の点全体からなる集合は加算に対して（０，１）を単位元とする加法群の構造を持つ。またＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の点Ｐおよび、正整数Ｌに対してＰのＬ回加算ＬＰを求める演算をスカラ倍と呼ぶ。
また、Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の点Ｐに対してＰをｎ回加算するスカラ倍の演算結果ｎＰが単位元である（０，１）となる場合、正整数ｎを点Ｐの位数と呼ぶ。
【０００９】
非特許文献３において係数ｄを用いない加算方法が開示されている。以下、非特許文献３に基づき上記加算方法を説明する。
楕円曲線上の２点をＰ＝（ｘ1，ｙ1）、Ｑ＝（ｘ2，ｙ2）、Ｐ≠Ｑ、ＰおよびＱは素数位数とした場合、加算Ｐ＋Ｑは以下の式（３）で計算することができる。
【００１０】
【数３】
2010266765.tif 000005
【００１１】
非特許文献２に開示されている加算および２倍算では有限体ｋ上の乗算に比べて１０倍以上演算コストの大きい逆元計算が用いられる。この問題に対して逆元計算を用いないことでより高速な加算および２倍算の計算方法が非特許文献２に開示されている。
【００１２】
具体的には、点（ｘ，ｙ）をｘ＝Ｚ／Ｘ、ｙ＝Ｚ／Ｙ、ＸＹＺ≠０を満たすＸ，Ｙ，Ｚ∈ｋを用いて変換したＩｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ：Ｙ：Ｚ）を用いて逆元計算をより負荷の少ない数回の乗算に置き換えることにより高速化を行う。
【００１３】
次に、非特許文献２に基づき逆元計算の必要の無い加算アルゴリズムを示す。
入力情報：（Ｘ1：Ｙ1：Ｚ1），（Ｘ2：Ｙ2：Ｚ2）
出力情報：（Ｘ3：Ｙ3：Ｚ3）＝（Ｘ1：Ｙ1：Ｚ1）＋（Ｘ2：Ｙ2：Ｚ2）
処理手順：なお、各処理の最後のＭ，Ｓ，Ｄは、それぞれ定義体ｋ上の乗算、２乗算、定数倍算の演算コストである。
（１）計算機が、Ａ←Ｚ1Ｚ2、Ｂ←ｄＡ2、Ｃ←Ｘ1Ｘ2、Ｄ←Ｙ1Ｙ2、Ｅ←ＣＤをｋ上でそれぞれ計算する（４Ｍ，１Ｓ，１Ｄ）。
（２）計算機が、Ｈ←Ｃ−ａＤ、Ｉ←（Ｘ1＋Ｙ1）（Ｘ2＋Ｙ2）−Ｃ−Ｄをｋ上でそれぞれ計算する（１Ｍ，１Ｄ）。
（３）計算機が、Ｘ3←（Ｅ＋Ｂ）Ｈをｋ上で計算する（１Ｍ）。
（４）計算機が、Ｙ3←（Ｅ−Ｂ）Ｉをｋ上で計算する（１Ｍ）。
（５）計算機が、Ｚ3←ＡＨＩをｋ上で計算する（２Ｍ）。
（６）計算機が、（Ｘ3：Ｙ3：Ｚ3）を演算結果として出力する。
この加算アルゴリズムの総演算コストは９Ｍ＋１Ｓ＋２Ｄとなる。
【００１４】
次に、非特許文献２に基づき逆元計算の必要の無い２倍算アルゴリズムを示す。
入力情報：（Ｘ1：Ｙ1：Ｚ1）
出力情報：（Ｘ3：Ｙ3：Ｚ3）＝２（Ｘ1：Ｙ1：Ｚ1）
処理手順：
（１）計算機が、Ａ←Ｘ12、Ｂ←Ｙ12、Ｕ←ａＢをｋ上でそれぞれ計算する（２Ｓ，１Ｄ）。
（２）計算機が、Ｃ←Ａ＋Ｕ、Ｄ←Ａ−Ｕ、Ｅ←（Ｘ1＋Ｙ1）2−Ａ−Ｂをｋ上でそれぞれ計算する（１Ｓ）。
（３）計算機が、Ｘ3←ＣＤをｋ上で計算する（１Ｍ）。
（４）計算機が、Ｙ3←Ｅ（Ｃ−２ｄＺ12）をｋ上で計算する（１Ｍ，１Ｓ，１Ｄ）。
（５）計算機が、Ｚ3←ＤＥをｋ上で計算する（１Ｍ）。
（６）計算機が、（Ｘ3：Ｙ3：Ｚ3）を演算結果として出力する。
この２倍算アルゴリズムの総演算コストは３Ｍ＋４Ｓ＋２Ｄとなる。
【００１５】
次に、Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の加算および、２倍算を組み合わせることでスカラ倍を計算するアルゴリズムを示す。
入力：楕円曲線上の点Ｐ，整数Ｌ（Ｌ＞０）
出力：Ｑ＝ＬＰ
処理手順：
（１）計算機が、整数Ｌを２進数展開して、Ｌ＝Ｌ0＋Ｌ1×２＋・・・＋Ｌt-1×２t-1  （Ｌt-1＝１）とする。
（２）計算機が、Ｑ←Ｐとおく。
（３）計算機が、ｉ←ｔ−２とおく。
（４）ｉ≧０を満たす間、計算機は、以下の処理（４−１）〜（４−２）を繰返す。
（４−１）計算機が、Ｑ←２Ｑを計算する。
（４−２）計算機が、Ｌi＝１であればＱ←Ｑ＋Ｐを計算する。
（４−３）計算機が、ｉ←ｉ−１を計算する。
（５）計算機が、計算結果としてＱを出力する
【００１６】
次に、非特許文献１に開示されているＥＣＤＳＡ署名に基づき、Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線および、Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いたＥＣＤＳＡ署名について説明する。
以下、本明細書において楕円曲線とはＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線を示すこととする。
なお、楕円曲線ａｘ2＋ｙ2＝１＋ｄｘ2ｙ2の素数位数のベースポイントＧ＝（ｘ，ｙ）はＩｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＧ＝（ＸG：ＹG：１）＝（１／ｘ，１／ｙ，１）に変換し、以後Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて楕円曲線上の演算を行う。またＺ座標が１であることからＧのスカラ倍におけるＧの加算時に１回の乗算を削減することができる。
公開鍵Ｑについても同様の理由でＺ＝１となるように変形を行う。
【００１７】
ＥＣＤＳＡ署名は以下の３つの処理より構成される。
（１）鍵ペア生成：計算機が、ＥＣＤＳＡ署名の生成および検証に用いる鍵ペアの生成を行う。鍵ペアの内、署名生成に用いる秘密鍵は署名生成者が外部に漏れないよう厳重に保管し、署名検証に用いる公開鍵は外部に公開する。
（２）署名生成：計算機が、秘密鍵を用いて署名対象の平文に対するデジタル署名を生成する。
（３）署名検証：計算機が、公開鍵、署名対象の平文およびデジタル署名を用いて署名の検証を行う。
【００１８】
以下、上記（１）〜（３）の処理を詳細に説明する。
（１）鍵生成：
入力情報：楕円曲線ａｘ2＋ｙ2＝１＋ｄｘ2ｙ2  （ｋ上で係数ａは２乗根を持ち係数ｄは持たない）、定義体ｋ、楕円曲線のベースポイントＧ＝（ＸG：ＹG：１）、ベースポイントの位数ｎ（素数）
出力情報：秘密鍵ｃ、公開鍵Ｑ＝（ＸQ：ＹQ：１）
（１−１）計算機が、０＜ｃ＜ｎを満たす整数ｃをランダムに生成し秘密鍵とする。
（１−２）計算機が、楕円曲線上のスカラ倍Ｑ1←ｃＧ＝（Ｘ：Ｙ：Ｚ）を計算する。
（１−３）計算機が、Ｑ←（ＸQ：ＹQ：１）＝（Ｚ／Ｘ：Ｚ／Ｙ：１）をｋ上で計算し公開鍵とする。
（１−３）計算機が、鍵ペアｃ、Ｑを出力する。
【００１９】
（２）署名生成：
入力情報：楕円曲線ａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）  、定義体ｋ、楕円曲線のベースポイントＧ＝（ＸG：ＹG：１）、ベースポイントの位数ｎ（素数）、署名対象データＭ、秘密鍵ｃ
出力情報：署名（ｒ，ｓ）
（２−１）計算機が、０＜ｂ＜ｎを満たす整数ｂをランダムに生成する。
（２−２）計算機が、楕円曲線上のスカラ倍Ｒ←ｂＧ＝（Ｘ1：Ｙ1：Ｚ1）を計算する。
（２−３）計算機が、ｘ1←Ｚ1／Ｘ1をｋ上で計算する。
（２−４）計算機が、定義体ｋ上の元ｘ1を正の整数に変換したものをｘ1としておき直す。
（２−５）計算機が、ｒ←ｘ1  ｍｏｄ  ｎ  を計算する。
（２−６）計算機が、ハッシュ関数ｈを用いてｅ←ｈ（Ｍ）を計算する。
（２−７）計算機が、ｓ←ｂ-1（ｅ＋ｃｒ）  ｍｏｄ  ｎを計算する。
（２−８）計算機が、署名対象データＭの署名として（ｒ，ｓ）を出力する。
【００２０】
（３）署名検証：
入力情報：楕円曲線ａｘ2＋ｙ2＝１＋ｄｘ2ｙ2  （ｋ上で係数ａは２乗根を持ち係数ｄは持たない）、定義体ｋ、楕円曲線のベースポイントＧ＝（ＸG：ＹG：１）、公開鍵Ｑ＝（ＸQ：ＹQ：１）、ベースポイントおよび公開鍵の位数ｎ（素数）、  署名検証対象データＭ、署名（ｒ，ｓ）
出力情報：Ｔｒｕｅ（検証成功）またはＦａｌｓｅ（検証失敗）
（３−１）計算機が、署名生成時と同じハッシュ関数ｈを用いてｅ←ｈ（Ｍ）を計算する。
（３−２）計算機が、ｅ1←  ｓ-1ｅ  ｍｏｄ  ｎを計算する。
（３−３）計算機が、ｒ1←  ｓ-1ｒ  ｍｏｄ  ｎを計算する。
（３−４）計算機が、Ｇ1←ｅ1Ｇを計算する。
（３−５）計算機が、Ｑ1←ｒ1Ｑを計算する。
（３−６）計算機が、Ｒ1←（Ｘ1：Ｙ1：Ｚ1）＝Ｇ1＋Ｑ1を計算する。
（３−７）計算機が、ｘ1←Ｚ1／Ｘ1をｋ上で計算する。
（３−８）計算機が、署名生成時と同じ変換方法でｋ上の元ｘ1を正の整数に変換したものをｘ1としておき直す。
（３−９）計算機が、ｘ1  ｍｏｄ  ｎ  ＝  ｒが成立すればＴｒｕｅ、しなければＦａｌｓｅを出力。
【先行技術文献】
【非特許文献】
【００２１】
【非特許文献１】ANSI X9.62-1998,"Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)", American National Standard for Financial Services, 1998.
【非特許文献２】Daniel J. Bernstein, Peter Birkner, Marc Joye, Tanja Lange, and Christiane Peters,"Twisted Edwards curves." In AFRICACRYPT 2008, volume 5023 of LNCS,p389-p405. Springer, 2008.
【非特許文献３】Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson,"Twisted Edwards Curves Revisited." In ASIACRYPT 2008, volume 5350 of LNCS, p326-p343 Springer, 2008.
【発明の概要】
【発明が解決しようとする課題】
【００２２】
前記したＥＣＤＳＡ署名では、楕円曲線上のスカラ倍演算処理が必須である。しかし、スカラ倍演算は署名処理において負荷が重いため処理性能に大きな影響を及ぼすことが知られている。
また、スカラ倍の処理性能は楕円曲線の定義体上の乗算および、２乗算、定数倍算の回数に依存することが知られている。
【００２３】
また、係数ｄを用いない加算方法についてＩｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標の適用可能性は非特許文献３において開示されていない。
【００２４】
このような背景に鑑みて本発明がなされたのであり、本発明は、効率的な楕円曲線スカラ倍演算を行うことを目的とする。
【課題を解決するための手段】
【００２５】
前記課題を解決するため、本発明は、Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を拡張した拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した素数位数の点である第１の点を整数倍して、Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した第２の点を算出する楕円曲線スカラ倍演算装置による楕円曲線スカラ倍演算方法であって、入力部を介して、前記第１の点および任意の整数が入力されると、楕円曲線スカラ倍演算装置が、前記整数を２進数展開し、前記展開した２進数の係数ごとに、（ａ）および（ｂ）の処理を行うことを特徴とする楕円曲線スカラ倍演算方法。
（ａ）前記第１の点を、Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した点に置換した上で、前記変換した第１の点の２倍算を行い、前記２倍算の結果を拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した素数位数の点である第３の点に変換し、（ｂ）前記係数が１である場合、前記第１の点と、前記第３の点の加算処理を行う。
その他の解決手段については、実施形態中で適宜説明する。
【発明の効果】
【００２６】
本発明によれば、効率的な楕円曲線スカラ倍演算を行うことができる。
【図面の簡単な説明】
【００２７】
【図１】本実施形態に係る楕円曲線スカラ倍演算装置の構成例を示す図である。
【図２】本実施形態に係る楕円曲線スカラ倍演算部の構成例を示す図である。
【図３】本実施形態に係る楕円曲線スカラ倍演算処理の全体処理を説明するためのフローチャートである。
【図４】ステップＳ１０４における２倍算処理の手順を示すフローチャートである。
【図５】ステップＳ１０６において係数ｄを用いる加算処理の手順を示すフローチャートである。
【図６】ステップＳ１０６において係数ａが−１かつ係数ｄを用いる加算処理の手順を示すフローチャートである。
【図７】ステップＳ１０６において係数ｄを用いない加算処理の手順を示すフローチャートである。
【図８】ステップＳ１０６において係数ａが−１かつ係数ｄを用いない加算処理の手順を示すフローチャートである。
【図９】本実施形態に係るＥＣＤＳＡ鍵ペア生成装置の構成例を示す図である。
【図１０】本実施形態に係るＥＣＤＳＡ鍵ペア生成処理の手順を示すフローチャートである。
【図１１】本実施形態に係るＥＣＤＳＡ署名生成装置の構成例を示す図である。
【図１２】本実施形態に係るＥＣＤＳＡ署名生成処理の手順を示すフローチャートである。
【図１３】本実施形態に係るＥＣＤＳＡ署名検証装置の構成例を示す図である。
【図１４】本実施形態に係るＥＣＤＳＡ署名検証処理の手順を示すフローチャートである。
【図１５】ステップＳ９０６の詳細な処理手順を示すフローチャートである。
【図１６】情報処理装置のハードウェア構成例を示す図である。
【発明を実施するための形態】
【００２８】
次に、本発明を実施するための形態（「実施形態」という）について、適宜図面を参照しながら詳細に説明する。なお、本実施形態では、拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いることで、楕円曲線スカラ倍演算における演算コスとを低減することを目的とする。
【００２９】
《楕円曲線スカラ倍演算》
［楕円曲線スカラ倍演算装置］
図１は、本実施形態に係る楕円曲線スカラ倍演算装置の構成例を示す図である。
楕円曲線スカラ倍演算装置１は、制御演算部１１０と、記憶部１２０を有している。
制御演算部１１０は、入出力部１１１と、制御部１１２と、楕円曲線スカラ倍演算部１１３とを有する。入出力部１１１は、入力情報としての演算対象データおよび出力情報としての演算結果の入出力を行う機能を有する。制御部１１２は、楕円曲線スカラ倍演算装置１全体を制御する機能を有する。楕円曲線スカラ倍演算部１１３は、実際に楕円曲線上のスカラ倍演算を計算する機能を有する。
記憶部１２０には、中間データ１２１、データ１２２などが格納されている。中間データ１２１は、必要に応じて処理中に生成されるデータである。データ１２２は、楕円曲線のパラメータなどのデータである。
【００３０】
図２は、本実施形態に係る楕円曲線スカラ倍演算部の構成例を示す図である。
楕円曲線スカラ倍演算部１１３は、入出力部１１４と、２進数展開部１１５と、楕円曲線加算演算部１１６と、楕円曲線２倍算演算部１１７と、基本演算部１１８とを有する。
２進数展開部１１５は、整数の２進数展開を行う機能を有する。楕円曲線加算演算部１１６は、楕円曲線上の２点の加算を行う機能を有する。楕円曲線２倍算演算部１１７は、楕円曲線上の点の２倍算を行う機能を有する。基本演算部１１８は、楕円曲線加算演算部１１６および楕円曲線２倍算演算部１１７から必要に応じて呼び出され楕円曲線の定義体上の演算や剰余計算（ｍｏｄ）を用いた四則演算などを行う機能を有する。
【００３１】
なお、楕円曲線スカラ倍演算装置１は、図１６に示すような、バス５７で接続されたＣＰＵ（Central Processing Unit）５１と、ＲＡＭ（Random Access Memory）などのメモリ５２と、ＨＤ（Hard Disk）やその他の外部記憶装置５５と、キーボードなどの入力装置５３と、ディスプレイなどの出力装置５４と、外部記憶装置５５や、入力装置５３や、出力装置５４とのインタフェース５６とを備えた、一般的な構成を有する情報処理装置５上に構築することができる。
楕円曲線スカラ倍演算装置１の制御演算部１１０および各部１１１〜１１８は、ＣＰＵ５１が、メモリ５２にロードされたプログラム（コードモジュールともいう）を実行することで、情報処理装置５上に具現化される。また、メモリ５２や、外部記憶装置５５が記憶部１２０として使用される。
【００３２】
また、前記したプログラムは、予め外部記憶装置５５に記憶され、必要に応じてメモリ５２上にロードされ、ＣＰＵ５１により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばＣＤ−ＲＯＭ（Compact Disk-Read Only Memory）などを介して、必要に応じて、可搬性の記憶媒体からメモリ５２にロードされてもよい。また、プログラムは、一旦、ＣＤ−ＲＯＭなどの可搬性の記憶媒体からＨＤなどにインストールされた後、必要に応じて、このＨＤからメモリ５２にロードされてもよい。さらに、プログラムは、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置５が伝送信号により、一旦ＨＤにダウンロードされてからメモリ５２にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ５２にロードされてもよい。
【００３３】
［楕円曲線スカラ倍演算処理］
次に、図２を参照しつつ、図３〜図８に沿って楕円曲線スカラ倍演算処理の手順を説明する。
ここで、全体概要を説明すると、入出力部１１１により入力を受け付けた楕円曲線ａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）、定義体ｋ、加算時の係数ｄ使用の有無、拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した素数位数の点Ｐ＝（Ｘ1：Ｙ1：Ｔ1：Ｚ1）、整数Ｌ（Ｌ＞０）の各入力情報は、記憶部１２０に保持される。
そして、制御演算部１１０が、記憶部１２０で保持されている各入力情報を用いて、図３〜図８に示すスカラ倍演算処理を行い、Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した演算結果Ｑ＝ＬＰ＝（Ｘ3：Ｙ3：Ｚ3）を求め、出力する。
【００３４】
（全体処理）
図３は、本実施形態に係る楕円曲線スカラ倍演算処理の全体処理を説明するためのフローチャートである。
ステップＳ１０１において、２進数展開部１１５が、Ｌを２進数展開して、Ｌ＝Ｌ0＋Ｌ1×２＋・・・＋Ｌt-1×２t-1  （Ｌt-1＝１）とする。
ステップＳ１０２において、基本演算部１１８が、ｄ1←２ｄ、ｉ←ｔ−２、Ｑ←Ｐとおく。
ステップＳ１０３において、基本演算部１１８が、ｉ＝−１であるか否かを判定し、ｉ＝−１であれば（Ｓ１０３→Ｙｅｓ）、ステップＳ１０９の処理に進み、そうでなければ（Ｓ１０３→Ｎｏ）、ステップＳ１０４の処理に進む。
ステップＳ１０４において、楕円曲線２倍算演算部１１７が、Ｑ←２Ｑを計算する。ステップＳ１０４の計算方法は図４を参照して後記する。
ステップＳ１０５において、基本演算部１１８が、Ｌi＝１であるか否かを判定し、Ｌi＝１であれば（Ｓ１０５→Ｙｅｓ）、ステップＳ１０６の処理に進み、そうでなければ（Ｓ１０５→Ｎｏ）、ステップＳ１０７の処理に進む。
【００３５】
ステップＳ１０６において、楕円曲線加算演算部１１６が、Ｑ←Ｑ＋Ｐを計算する。ステップＳ１０６の計算方法は、係数ｄを用いる設定がされている場合は図５を参照して後記し、係数ａが−１かつ係数ｄを用いる設定がされている場合は図６を参照して後記し、入力時にｄを用いない設定がされている場合は図７を参照して後記し、係数ａが−１かつ入力時にｄを用いない設定がされている場合は図８を参照して後記する。
ステップＳ１０７において、基本演算部１１８が、ｉ←ｉ−１を計算する。
ステップＳ１０８において、基本演算部１１８が、ｉ≧０であるか否かを判定し、ｉ≧０であれば（Ｓ１０８→Ｙｅｓ）、ステップＳ１０４の処理に戻り、そうでなければ（Ｓ１０８→Ｎｏ）、ステップＳ１０９の処理に進む。
ステップＳ１０９において、楕円曲線スカラ倍演算部１１３が、Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）を演算結果として出力する。
【００３６】
（２倍算処理）
次に、図２を参照しつつ、図４に沿って図３のステップＳ１０４における２倍算処理について説明する。なお、これ以降、各処理の最後に記述してあるＭ，Ｓ，Ｄは、それぞれ定義体ｋ上の乗算、２乗算、定数倍算の演算コストを示す。
図４は、ステップＳ１０４における２倍算処理の手順を示すフローチャートである。
なお、入力時におけるＱの座標は（Ｘ2：Ｙ2：Ｔ2：Ｚ2）または（Ｘ2：Ｙ2：Ｚ2）であるとする。
ステップＳ２０１において、楕円曲線２倍算演算部１１７が、必要に応じてＱを置換する。具体的には、楕円曲線２倍算演算部１１７が、Ｑ＝（Ｘ2：Ｙ2：Ｔ2：Ｚ2）であればＴ2を無視しＱをＱ←（Ｘ2：Ｙ2：Ｚ2）に置換し、それ以外であれば置換を行わない。
ステップＳ２０２において、楕円曲線２倍算演算部１１７が、Ａ←Ｘ22、Ｂ←Ｙ22、Ｕ←ａＢをｋ上でそれぞれ計算する（２Ｓ，１Ｄ）。ここでａ＝−１である場合、Ｕ←ａＢはｋ上でＢの符号を反転することにより定数倍算を用いないで計算できるため、演算コストを１Ｄ削減することができる。
ステップＳ２０３において、楕円曲線２倍算演算部１１７が、Ｃ←Ａ＋Ｕ、Ｄ←Ａ−Ｕ、Ｅ←（Ｘ2＋Ｙ2）2−Ａ−Ｂ、Ｈ←（Ｃ−ｄ1Ｚ22）をｋ上でそれぞれ計算する（２Ｓ，１Ｄ）。
【００３７】
ステップＳ２０４において、楕円曲線２倍算演算部１１７が、Ｘ3←ＣＤをｋ上で計算する（１Ｍ）。
ステップＳ２０５において、楕円曲線２倍算演算部１１７が、Ｙ3←ＥＨをｋ上で計算する（１Ｍ）。
ステップＳ２０６において、楕円曲線２倍算演算部１１７が、Ｌi＝１であればＴ3←ＣＨをｋ上で計算する（１Ｍ）。Ｌi＝１でなければ、何も行わない。
ステップＳ２０７において、楕円曲線２倍算演算部１１７が、Ｚ3←ＤＥをｋ上で計算する（１Ｍ）。
ステップＳ２０８において、楕円曲線２倍算演算部１１７が、ステップＳ２０６でＴ3を計算している場合、２倍算の演算結果を拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｔ3：Ｚ3）とおき、そうでなければＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とおき、それぞれを演算結果として出力する。
この２倍算の総演算コストは、ステップＳ２０６においてＴ3を計算しない場合、３Ｍ＋４Ｓ＋２Ｄ、ステップＳ２０６においてＴ3を計算する場合、４Ｍ＋４Ｓ＋２Ｄとなる。
またａ＝−１である場合、ステップＳ２０６においてＴ3を計算しない場合、３Ｍ＋４Ｓ＋Ｄ、ステップＳ２０６においてＴ3を計算する場合、４Ｍ＋４Ｓ＋Ｄとなる。
【００３８】
ここで、図４の処理について詳細に説明する。
まず、非特許文献２に基づくＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ：Ｙ：Ｚ）を用いた（Ｘ3：Ｙ3：Ｚ3）＝２（Ｘ2：Ｙ2：Ｚ2）を計算する２倍算は以下の式（４）〜（６）で計算できる。
【００３９】
【数４】
2010266765.tif 000006
【００４０】
次に、この非特許文献２記載の２倍算計算方法を本実施形態による、すなわち拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いるスカラ倍演算手段に適するよう変形する。
つまり、２倍算に続いて拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ：Ｙ：Ｔ：Ｚ）を用いて加算を行う場合のみ、上記のＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ3：Ｙ3：Ｚ3）に加えて１／ｘ3ｙ3＝Ｚ3／Ｔ3を満たすＴ3座標を求める必要がある。
ここで、Ｔ3は以下の条件（式（７））を満たす。
【００４１】
【数５】
2010266765.tif 000007
【００４２】
さらに変形して、式（８）を得る。
【００４３】
【数６】
2010266765.tif 000008
【００４４】
以上より、Ｔ３は、式（９）とおける。
【００４５】
【数７】
2010266765.tif 000009
【００４６】
また、２倍算においてＴ座標は使用しないため、２倍算の後に２倍算が行われる場合、Ｔ座標を計算する必要がないため出力はＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標（Ｘ3：Ｙ3：Ｚ3）を用いる。
さらに、入力が拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ＝（Ｘ2：Ｙ2：Ｔ2：Ｚ2）であった場合、Ｔ2座標を無視することによりＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標Ｑ＝（Ｘ2：Ｙ2：Ｚ2）とみなして２倍算を行う。
以上をアルゴリズムの形でまとめると、図４で示す手順となる。
【００４７】
（加算処理）
次に、図２を参照しつつ、図５〜図８に沿って図３のステップＳ１０６における処理を説明する。
まず、図５は、ステップＳ１０６において係数ｄを用いる加算処理の手順を示すフローチャートである。
なお、入力時におけるＰの座標は（Ｘ1：Ｙ1：Ｔ1：Ｚ1）、Ｑの座標は（Ｘ2：Ｙ2：Ｔ2：Ｚ2）であるとする。
ステップＳ３０１において、楕円曲線加算演算部１１６が、Ａ←Ｘ1Ｘ2、Ｂ←Ｙ1Ｙ2、Ｄ←Ｔ1Ｔ2をｋ上でそれぞれ計算する（３Ｍ）。
ステップＳ３０２において、楕円曲線加算演算部１１６が、Ｚ1＝１であるか否かを判定し、Ｚ1＝１であれば（Ｓ３０２→Ｙｅｓ）、ステップＳ３０３の処理に進み、そうでなければ（Ｓ３０２→Ｎｏ）、ステップＳ３０４の処理に進む。
ステップＳ３０３において、楕円曲線加算演算部１１６が、Ｃ←ｄＺ2をｋ上で計算しステップＳ３０５に進む（１Ｄ）。
ステップＳ３０４において、楕円曲線加算演算部１１６が、Ｃ←ｄＺ1Ｚ2をｋ上で計算しステップＳ３０５に進む（１Ｄ，１Ｍ）。
ステップＳ３０５において、楕円曲線加算演算部１１６が、Ｅ←（Ｘ1＋Ｙ1）（Ｘ2＋Ｙ2）−Ａ−Ｂをｋ上で計算する（１Ｍ）。
ステップＳ３０６において、楕円曲線加算演算部１１６が、Ｆ←Ｄ−Ｃ、Ｇ←Ｄ＋Ｃ、Ｈ←Ａ−ａＢをｋ上でそれぞれ計算する（１Ｄ）。
ステップＳ３０７において、楕円曲線加算演算部１１６が、Ｘ3←ＨＧをｋ上で計算する（１Ｍ）。
ステップＳ３０８において、楕円曲線加算演算部１１６が、Ｙ3←ＥＦをｋ上で計算する（１Ｍ）。
ステップＳ３０９において、楕円曲線加算演算部１１６が、Ｚ3←ＨＥをｋ上で計算する（１Ｍ）。
ステップＳ３１０において、楕円曲線加算演算部１１６が、演算結果をＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）として、出力する。
図５の処理手順による加算アルゴリズムの総演算コストは８Ｍ＋２Ｄ（Ｚ1＝１以外，Ｓ３０２→Ｎｏ）、７Ｍ＋２Ｄ（Ｚ1＝１，Ｓ３０２→Ｙｅｓ）となる。
【００４８】
ここで、図５の処理について詳細に説明する。
非特許文献３に基づく加算公式によるとＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の２点Ｐ＝（ｘ1，ｙ1）、Ｑ＝（ｘ2，ｙ2）に対して係数ｄを用いる加算Ｐ＋Ｑ＝（ｘ3，ｙ3）は以下の式（１０）で計算することができる。
【００４９】
【数８】
2010266765.tif 000010
【００５０】
次に、式（１０）より図５の加算アルゴリズムを導く。
２点Ｐ＝（ｘ1，ｙ1）、Ｑ＝（ｘ2，ｙ2）と拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現したＰ＝（Ｘ1：Ｙ1：Ｔ1：Ｚ1）、Ｑ＝（Ｘ2：Ｙ2：Ｔ2：Ｚ2）は以下の関係を満たす。
ｘ1＝Ｚ1／Ｘ1，ｙ1＝Ｚ1／Ｙ1，ｘ1ｙ1＝Ｚ1／Ｔ1，ｘ2＝Ｚ2／Ｘ2，ｙ2＝Ｚ2／Ｙ2，ｘ2ｙ2＝Ｚ2／Ｔ2
これらの式を、式（１０）へ代入することによって加算公式（式（１０））を変形すると、以下の式（１１）を得る。
【００５１】
【数９】
2010266765.tif 000011
【００５２】
次に、式（１２）より式（１３）を得ることができる。
【００５３】
【数１０】
2010266765.tif 000012
【００５４】
【数１１】
2010266765.tif 000013
【００５５】
式（１３）を用いて、更に加算公式（式（１１））を変形すると、式（１４）を得る。
【００５６】
【数１２】
2010266765.tif 000014
【００５７】
式（１４）を、更に変形することにより、最終的にＰ＋Ｑは以下の式（１５）を計算することで求められる。
【００５８】
【数１３】
2010266765.tif 000015
【００５９】
この式（１５）よりｘ3＝Ｚ3／Ｘ3、ｙ3＝Ｚ3／Ｙ3、ｘ3ｙ3＝Ｚ3／Ｔ3を満たすＸ3、Ｙ3、Ｔ3、Ｚ3をそれぞれ求めると、以下の式（１６）〜（１９）となる。
【００６０】
【数１４】
2010266765.tif 000016
【００６１】
式（１６）〜（１９）を用いることにより、Ｐ＋Ｑ＝（Ｘ1：Ｙ1：Ｔ1：Ｚ1）＋（Ｘ2：Ｙ2：Ｔ2：Ｚ2）＝（Ｘ3：Ｙ3：Ｔ3：Ｚ3）を計算することができる。
実際に、ｘ3＝Ｚ3／Ｘ3、ｙ3＝Ｚ3／Ｙ3、ｘ3ｙ3＝Ｚ3／Ｔ3を満たしていることは以下の式（２０）〜（２２）で確認できる。
【００６２】
【数１５】
2010266765.tif 000017
【００６３】
ここでＴ3は加算演算のみで用い２倍算では必要が無いこと、スカラ倍において加算の次に行われる演算は必ずＴ座標の必要の無い２倍算であることからＴ3を計算する必要は生じない。
この内容をアルゴリズムの形でまとめると、図５に示す処理手順となる。
【００６４】
次に、図３のステップＳ１０６における係数ａが−１かつ係数ｄを用いる加算処理について説明する。
図６は、ステップＳ１０６において係数ａが−１かつ係数ｄを用いる加算処理の手順を示すフローチャートである。
なお、入力時におけるＰの座標は（Ｘ1：Ｙ1：Ｔ1：Ｚ1）、Ｑの座標は（Ｘ2：Ｙ2：Ｔ2：Ｚ2）であるとする。なお、図６では係数ｄをｄ1とする。
ステップＳ４０１において、楕円曲線加算演算部１１６が、Ａ←（Ｘ1＋Ｙ1）（Ｘ2＋Ｙ2）、Ｂ←（Ｘ1−Ｙ1）（Ｘ2−Ｙ2）、Ｄ＝２Ｔ1Ｔ2  をｋ上でそれぞれ計算する（３Ｍ）。なお、この処理において、定義体ｋ上の２倍算が含まれるが、より演算コストの小さい加算もしくは１ビットシフトなどの演算を用いることでコストの大きい乗算を用いないで計算できるため定数倍としては扱わない。
ステップＳ４０２において、楕円曲線加算演算部１１６が、Ｚ1＝１であるか否かを判定し、Ｚ1＝１であれば（Ｓ４０２→Ｙｅｓ）、ステップＳ４０３の処理に進み、そうでなければ（Ｓ４０２→Ｎｏ）、ステップＳ４０４の処理に進む。
ステップＳ４０３において、楕円曲線加算演算部１１６が、Ｃ←ｄ1Ｚ2をｋ上で計算しステップＳ４０５に進む（１Ｄ）
ステップＳ４０４において、楕円曲線加算演算部１１６が、Ｃ←ｄ1Ｚ1Ｚ2をｋ上で計算しステップＳ４０５に進む（１Ｍ，１Ｄ）。
ステップＳ４０５において、楕円曲線加算演算部１１６が、Ｅ＝Ａ−Ｂ、Ｆ＝Ｄ−Ｃ、Ｇ＝Ｄ＋Ｃ、Ｈ＝Ａ＋Ｂをそれぞれｋ上で計算する。
ステップＳ４０６において、楕円曲線加算演算部１１６が、Ｘ3＝ＨＧをｋ上で計算する（１Ｍ）
ステップＳ４０７において、楕円曲線加算演算部１１６が、Ｙ3＝ＥＦをｋ上で計算する（１Ｍ）。
ステップＳ４０８において、楕円曲線加算演算部１１６が、Ｚ3＝ＨＥをｋ上で計算する（１Ｍ）。
ステップＳ４０９において、楕円曲線加算演算部１１６が、演算結果をＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）として、出力する。
図６に示す加算アルゴリズムの総演算コストは７Ｍ＋Ｄ（Ｚ1＝１以外，Ｓ４０２→Ｎｏ）、６Ｍ＋Ｄ（Ｚ1＝１，Ｓ４０２→Ｙｅｓ）となる。
【００６５】
ここで、図６の処理について詳細に説明する。
図５における加算方法を変形することにより、図６の加算アルゴリズムを導く。
図５における加算方法（式（１６）〜（１９））に対して、に対してａ＝−１を代入することにより式（２３）〜（２６）が得られる。
【００６６】
【数１６】
2010266765.tif 000018
【００６７】
【数１７】
2010266765.tif 000019
【００６８】
式（２３）〜（２６）を用いることによりＰ＋Ｑ＝（Ｘ1：Ｙ1：Ｔ1：Ｚ1）＋（Ｘ2：Ｙ2：Ｔ2：Ｚ2）＝（Ｘ3：Ｙ3：Ｔ3：Ｚ3）を計算することができ、（Ｘ3：Ｙ3：Ｔ3：Ｚ3）の代わりに（Ｘ4：Ｙ4：Ｔ4：Ｚ4）＝（４Ｘ3：４Ｙ3：４Ｔ3：４Ｚ3）を用いてもｘ3＝Ｚ4／Ｘ4、ｙ3＝Ｚ4／Ｙ4、ｘ3ｙ3＝Ｚ4／Ｔ4を満たすことから、以下の式（２７）〜（３０）を用いることによりＰ＋Ｑ＝（Ｘ1：Ｙ1：Ｔ1：Ｚ1）＋（Ｘ2：Ｙ2：Ｔ2：Ｚ2）＝（Ｘ3：Ｙ3：Ｔ3：Ｚ3）を計算できることが分かる。
【００６９】
【数１８】
2010266765.tif 000020
【００７０】
また、Ｘ3、Ｙ3、Ｚ3座標を求める際に必要となる式は以下の条件（式（３１），（３２））を満たす。
【００７１】
【数１９】
2010266765.tif 000021
【００７２】
これらの関係式を用いて加算公式（式（１０））をアルゴリズムの形で記載すると、図６に示す処理手順となる。
【００７３】
図７は、ステップＳ１０６において係数ｄを用いない加算処理の手順を示すフローチャートである。
なお、図７において、入力時のＰの座標は（Ｘ1：Ｙ1：Ｔ1：Ｚ1）、Ｑの座標は（Ｘ2：Ｙ2：Ｔ2：Ｚ2）であるとする。
ステップＳ５０１において、楕円曲線加算演算部１１６が、Ａ←Ｘ1Ｘ2、Ｂ←Ｙ1Ｙ2、Ｄ←Ｔ1Ｚ2をｋ上でそれぞれ計算する（３Ｍ）。
ステップＳ５０２において、楕円曲線加算演算部１１６が、Ｚ1＝１であるか否かを判定し、Ｚ1＝１であれば（Ｓ５０２→Ｙｅｓ）、ステップＳ５０３の処理に進み、そうでなければ（Ｓ５０２→Ｎｏ）、ステップＳ５０４に進む。
ステップＳ５０３において、楕円曲線加算演算部１１６が、Ｃ←Ｔ2とおきステップＳ５０５に進む。
ステップＳ５０４において、楕円曲線加算演算部１１６が、Ｃ←Ｔ2Ｚ1をｋ上で計算しステップＳ５０５に進む（１Ｍ）。
ステップＳ５０５において、楕円曲線加算演算部１１６が、Ｅ←（Ｘ1＋Ｙ1）（Ｘ2−Ｙ2）＋Ｂ−Ａをｋ上で計算する（１Ｍ）。
ステップＳ５０６において、楕円曲線加算演算部１１６が、Ｆ←Ｃ＋Ｄ，Ｇ←Ｃ−Ｄ，Ｈ←Ａ＋ａＢをｋ上でそれぞれ計算する（１Ｄ）。
ステップＳ５０７において、楕円曲線加算演算部１１６が、Ｘ3←ＨＧをｋ上で計算する（１Ｍ）。
ステップＳ５０８において、楕円曲線加算演算部１１６が、Ｙ3←ＥＦをｋ上で計算する（１Ｍ）。
ステップＳ５０９において、楕円曲線加算演算部１１６が、Ｚ3←ＦＧをｋ上で計算する（１Ｍ）
ステップＳ５１０において、楕円曲線加算演算部１１６が、演算結果をＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とし、出力する。
図７に示す加算アルゴリズムの総演算コストは８Ｍ＋Ｄ（Ｚ1＝１以外，Ｓ５０２→Ｎｏ）、７Ｍ＋Ｄ（Ｚ1＝１，Ｓ５０２→Ｙｅｓ）となる。
【００７４】
ここで、図７の処理の詳細について説明する。
非特許文献３に基づく加算公式によるとＴｗｉｓｔｅｄ  Ｅｄｗａｒｄ型楕円曲線上の２点Ｐ＝（ｘ1，ｙ1）、Ｑ＝（ｘ2，ｙ2）に対して係数ｄを用いない加算Ｐ＋Ｑ＝（ｘ3，ｙ3）は以下の式（３３）で計算することができる。
【００７５】
【数２０】
2010266765.tif 000022
【００７６】
この式（３３）より、図５に示す加算アルゴリズムを導く。
２点Ｐ＝（ｘ1，ｙ1）、Ｑ＝（ｘ2，ｙ2）と拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現したＰ＝（Ｘ1：Ｙ1：Ｔ1：Ｚ1）、Ｑ＝（Ｘ2：Ｙ2：Ｔ2：Ｚ2）は以下の関係を満たす。
ｘ1＝  Ｚ1／Ｘ1、ｙ1＝Ｚ1／Ｙ1、ｘ1ｙ1＝  Ｚ1／Ｔ1、ｘ2＝  Ｚ2／Ｘ2、ｙ2＝Ｚ2／Ｙ2、ｘ2ｙ2＝  Ｚ2／Ｔ2 
これらの関係式を、式（３３）に代入することによって、加算公式（式（３３）を変形し、式（３４）を得る。
【００７７】
【数２１】
2010266765.tif 000023
【００７８】
次に、以下の式（３５）より式（３６）が導かれる。
【００７９】
【数２２】
2010266765.tif 000024
【００８０】
この式（３６）を式（３４）に代入して、変形すると、以下の式（３７）を得る。
【００８１】
【数２３】
2010266765.tif 000025
【００８２】
最終的にＰ＋Ｑは以下の式（３８）を計算することで求められる。
【００８３】
【数２４】
2010266765.tif 000026
【００８４】
式（３８）より、ｘ3＝Ｚ3／Ｘ3、ｙ3＝Ｚ3／Ｙ3、ｘ3ｙ3＝Ｚ3／Ｔ3 を満たすＸ3、Ｙ3、Ｔ3、Ｚ3をそれぞれ求めると、以下の式（３９）〜（４２）を得る。
【００８５】
【数２５】
2010266765.tif 000027
【００８６】
式（３９）〜（４２）を用いることでＰ＋Ｑ＝（Ｘ1：Ｙ1：Ｔ1：Ｚ1）＋（Ｘ2：Ｙ2：Ｔ2：Ｚ2）＝（Ｘ3：Ｙ3：Ｔ3：Ｚ3）を計算することができる。
実際にｘ3＝Ｚ3／Ｘ3、ｙ3＝Ｚ3／Ｙ3、ｘ3ｙ3＝Ｚ3／Ｔ3を満たしていることは以下の式（４３）〜（４５）で確認できる。
【００８７】
【数２６】
2010266765.tif 000028
【００８８】
ここでＴ3は加算演算のみで用い２倍算では必要が無いこと、スカラ倍において加算の次に行われる演算は必ずＴ座標の必要の無い２倍算であることからＴ3を計算する必要は生じない。
上記の内容をアルゴリズムの形でまとめると、図７に示す処理手順となる。
【００８９】
図８は、ステップＳ１０６において係数ａが−１かつ係数ｄを用いない加算処理の手順を示すフローチャートである。
なお、入力時におけるＰの座標は（Ｘ1：Ｙ1：Ｔ1：Ｚ1）、Ｑの座標は（Ｘ2：Ｙ2：Ｔ2：Ｚ2）であるとする。
ステップＳ６０１において、楕円曲線加算演算部１１６が、Ａ←（Ｘ1−Ｙ1）（Ｘ2＋Ｙ2）、Ｂ←（Ｘ1＋Ｙ1）（Ｘ2−Ｙ2）、Ｄ←２Ｔ1Ｚ2をｋ上でそれぞれ計算する（３Ｍ）。この処理において、定義体ｋ上の２倍算が含まれるが、より演算コストの小さい加算もしくは１ビットシフトなどの演算を用いることでコストの大きい乗算を用いないで計算できるため定数倍としては扱わない。
【００９０】
ステップＳ６０２において、楕円曲線加算演算部１１６が、Ｚ1＝１であるか否かを判定し、Ｚ1＝１であれば（Ｓ６０２→Ｙｅｓ）、ステップＳ６０３の処理に進み、そうでなければ（Ｓ６０２→Ｎｏ）、ステップＳ６０４に進む。
ステップＳ６０３において、楕円曲線加算演算部１１６が、Ｃ←２Ｔ2をｋ上で計算しステップＳ６０５に進む。
ステップＳ６０４において、楕円曲線加算演算部１１６が、Ｃ←２Ｔ2Ｚ1をｋ上で計算しステップＳ６０５に進む（１Ｍ）。
ステップＳ６０５において、楕円曲線加算演算部１１６が、Ｅ←Ａ＋Ｂ、Ｆ←Ｃ＋Ｄ，Ｇ←Ｃ−Ｄ，Ｈ←Ｂ−Ａをｋ上でそれぞれ計算する。
ステップＳ６０６において、楕円曲線加算演算部１１６が、Ｘ3←ＥＧをｋ上で計算する（１Ｍ）。
ステップＳ６０７において、楕円曲線加算演算部１１６が、Ｙ3←ＨＦをｋ上で計算する（１Ｍ）。
ステップＳ６０８において、楕円曲線加算演算部１１６が、Ｚ3←ＦＧをｋ上で計算する（１Ｍ）。
ステップＳ６０９において、楕円曲線加算演算部１１６が、演算結果をＩｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いてＱ←（Ｘ3：Ｙ3：Ｚ3）とし、出力する。
図８に示す加算アルゴリズムの演算コストは７Ｍ（Ｚ1＝１以外）、６Ｍ（Ｚ1＝１）となる。
【００９１】
ここで、図８に示す処理について詳細に説明する。
図７に示す加算方法を変形することにより、図８に示す加算アルゴリズムを導く。
図７における加算方法（式（３９）〜（４２）に対して、ａ＝−１を代入することにより以下の式（４６）〜（４９）が得られる。
【００９２】
【数２７】
2010266765.tif 000029
【００９３】
【数２８】
2010266765.tif 000030
【００９４】
式（４６）〜（４９）を用いることによりＰ＋Ｑ＝（Ｘ1：Ｙ1：Ｔ1：Ｚ1）＋（Ｘ2：Ｙ2：Ｔ2：Ｚ2）＝（Ｘ3：Ｙ3：Ｔ3：Ｚ3）を計算することができ、（Ｘ3：Ｙ3：Ｔ3：Ｚ3）の代わりに（Ｘ4：Ｙ4：Ｔ4：Ｚ4）＝（４Ｘ3：４Ｙ3：４Ｔ3：４Ｚ3）を用いてもｘ3＝Ｚ4／Ｘ4、ｙ3＝Ｚ4／Ｙ4、ｘ3ｙ3＝Ｚ4／Ｔ4を満たすことから、以下の式（５０）〜（５３）を用いることによりＰ＋Ｑ＝（Ｘ1：Ｙ1：Ｔ1：Ｚ1）＋（Ｘ2：Ｙ2：Ｔ2：Ｚ2）＝（Ｘ3：Ｙ3：Ｔ3：Ｚ3）を計算できる。
【００９５】
【数２９】
2010266765.tif 000031
【００９６】
ここで、Ｘ3、Ｙ3、Ｚ3座標を求める際に必要となる式は以下の条件（式（５４），（５５））を満たす。
【００９７】
【数３０】
2010266765.tif 000032
【００９８】
関係式（５０）〜（５３）を用いて加算公式（式（３３））をアルゴリズムの形で記載すると、図８に示す処理となる。
【００９９】
ここで、例として１６１ビットの整数Ｌを用いた楕円曲線スカラ倍演算方法を説明する。
整数Ｌを１６１ビットとしその２進数展開をＬ＝Ｌ0＋Ｌ1×２＋・・・＋Ｌ159×２159  ＋Ｌ160×２160  （Ｌ160＝１）であるとする。さらに、Ｌi（０≦ｉ≦１５９）のうち半分の８０個が１であるとする。Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した点Ｐ＝（Ｘ：Ｙ：Ｚ）（Ｚ≠１）のＬ倍のＱ＝ＬＰを非特許文献２に開示されているＩｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いる２倍算および加算を組み合わせて計算する場合の演算コストは楕円曲線の定義体上の乗算、２乗算および定数倍算の演算コストをＭ、ＳおよびＤとした場合、１６０×（３Ｍ＋４Ｓ＋２Ｄ）＋８０×（９Ｍ＋１Ｓ＋２Ｄ）＝１２００Ｍ＋７２０Ｓ＋４８０Ｄとなる。
【０１００】
ここで、本実施形態における楕円曲線の係数ｄを用いてＬ倍を行う方法（図５）を用いると、８０×（３Ｍ＋４Ｓ＋２Ｄ：図４）＋８０×（４Ｍ＋４Ｓ＋２Ｄ：図４）＋８０×（８Ｍ＋２Ｄ：図５）＝１２００Ｍ＋６４０Ｓ＋４８０Ｄとなり、非特許文献２に記載の技術に比べて８０Ｓの演算コストを削減できる。
【０１０１】
また、本実施形態における楕円曲線の係数ａが−１かつ係数ｄを用いてＬ倍を行う方法（図６）を用いると、８０×（３Ｍ＋４Ｓ＋Ｄ：図４）＋８０×（４Ｍ＋４Ｓ＋Ｄ：図４）＋８０×（７Ｍ＋Ｄ：図６）＝１１２０Ｍ＋６４０Ｓ＋２４０Ｄとなり、非特許文献２に記載の技術に比べて８０Ｍ＋８０Ｓ＋２４０Ｄの演算コストを削減できる。
【０１０２】
さらに、本実施形態における楕円曲線の係数ｄを用いないでＬ倍を行う方法（図７）を用いると、８０×（３Ｍ＋４Ｓ＋２Ｄ：図４）＋８０×（４Ｍ＋４Ｓ＋２Ｄ：図４）＋８０×（８Ｍ＋Ｄ：図７）＝１２００Ｍ＋６４０Ｓ＋４００Ｄとなり、非特許文献２に記載の技術に比べて８０Ｓ＋８０Ｄの演算コストを削減できる。
【０１０３】
また、本実施形態における楕円曲線の係数ａが−１かつ係数ｄを用いないでＬ倍を行う方法（図８）を用いると、８０×（３Ｍ＋４Ｓ＋Ｄ：図４）＋８０×（４Ｍ＋４Ｓ＋Ｄ：図４）＋８０×（７Ｍ：図８）＝１１２０Ｍ＋６４０Ｓ＋１６０Ｄとなり、非特許文献２に記載の技術に比べて８０Ｍ＋８０Ｓ＋３２０Ｄの演算コストを削減できる。
【０１０４】
すなわち、本実施形態によれば、非特許文献２に記載の技術に比べてスカラ倍演算時の演算コストを削減できるためスカラ倍演算コストをより高速化することができる。これにより高速なＥＣＤＳＡ署名など楕円曲線の性質を用いた署名方式や公開鍵暗号の実現が可能となる。
【０１０５】
《ＥＣＤＳＡ鍵ペア生成》
次に、本実施形態に係る楕円曲線スカラ倍演算方法を利用したＥＣＤＳＡ鍵ペア生成方法について図９および図１０を参照して説明する。
【０１０６】
［ＥＣＤＳＡ鍵ペア生成装置］
図９は、本実施形態に係るＥＣＤＳＡ鍵ペア生成装置の構成例を示す図である。
ＥＣＤＳＡ鍵ペア生成装置２は、制御演算部２１０および記憶部２２０を有している。
制御演算部２１０は、入出力部２１１、制御部２１２、楕円曲線スカラ倍演算部２１３、乱数生成部２１４を有している。入出力部２１１は、楕円曲線のパラメータ、定義体情報、スカラ倍における係数ｄの加算時使用の有無情報、ベースポイントＧおよびその位数の入力を入力情報として受け付けるとともに、生成された鍵ペア２２３を出力情報として出力する機能を有している。制御部２１２は、ＥＣＤＳＡ鍵ペア生成装置２を制御する機能を有している。楕円曲線スカラ倍演算部２１３は、ベースポイントの整数倍を計算する機能を有する。乱数生成部２１４は、乱数を生成する機能を有する。
【０１０７】
なお、楕円曲線スカラ倍演算部２１３は、図１に示す楕円曲線スカラ倍演算装置１を用いて構成することができる。この場合、定義体上の演算、剰余演算（ｍｏｄ）、比較などの基本演算は、図１に示す楕円曲線スカラ倍演算装置１内の入出力部１１１を通じて基本演算部１１８を呼び出すことにより行うことができる。
【０１０８】
記憶部２２０には、中間データ２２１、データ２２２、鍵ペア２２３などが格納されている。中間データ２２１は、制御演算部２１０における演算時の中間データである。データ２２２は、入出力部２１１により入力を受け付けた楕円曲線のパラメータ、ベースポイントおよびその位数、定義体情報、スカラ倍における係数ｄの加算時使用の有無情報などのデータである。鍵ペア２２３は、制御演算部２１０で生成された鍵ペアのデータである。
【０１０９】
なお、ＥＣＤＳＡ鍵ペア生成装置２は、図１６に示すような、バス５７で接続されたＣＰＵ５１と、ＲＡＭなどのメモリ５２と、ＨＤやその他の外部記憶装置５５と、キーボードなどの入力装置５３と、ディスプレイなどの出力装置５４と、外部記憶装置５５や、入力装置５３や、出力装置５４とのインタフェース５６とを備えた、一般的な構成を有する情報処理装置５上に構築することができる。
ＥＣＤＳＡ鍵ペア生成装置２の制御演算部２１０および各部２１１〜２１４は、ＣＰＵ５１が、メモリ５２にロードされたプログラム（コードモジュールともいう）を実行することで、情報処理装置５上に具現化されるプロセスとして実現される。また、メモリ５２や、外部記憶装置５５が記憶部２２０として使用される。
【０１１０】
また、前記したプログラムは、予め外部記憶装置５５に記憶され、必要に応じてメモリ５２上にロードされ、ＣＰＵ５１により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばＣＤ−ＲＯＭなどを介して、必要に応じて、可搬性の記憶媒体からメモリ５２にロードされてもよい。また、プログラムは、一旦、ＣＤ−ＲＯＭなどの可搬性の記憶媒体からＨＤなどにインストールされた後、必要に応じて、このＨＤからメモリ５２にロードされてもよい。さらに、プログラムは、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置５が伝送信号により、一旦ＨＤにダウンロードされてからメモリ５２にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ５２にロードされてもよい。
【０１１１】
［ＥＣＤＳＡ鍵ペア生成方法］
図１０は、本実施形態に係るＥＣＤＳＡ鍵ペア生成処理の手順を示すフローチャートである。
入出力部２１１により、ＥＣＤＳＡ鍵ペア生成装置２が、入力情報として楕円曲線ａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）、定義体ｋ、スカラ倍における係数ｄの加算時使用の有無情報、楕円曲線のベースポイントＧ＝（ＸG：ＹG：ＴG：１）、ベースポイントの位数ｎ（素数）などを受け付けると、これらの入力情報は記憶部２２０に格納される。なおベースポイントＧはＺ＝１とした拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標で表されているものとする。
そして、制御演算部２１０が、入力情報として保持されているデータ２２２を用い、図１０に示す鍵ペア生成処理を行って、鍵ペア２２３を生成する。
そして、制御演算部２１０で作成された鍵ペア２２３を、記憶部２２０に保持するとともに入出力部２１１より出力情報として出力し、動作を終了する。
【０１１２】
以下、図１０を参照して、鍵ペア生成処理を説明する。
ステップＳ７０１において、乱数生成部２１４が、０＜ｃ＜ｎを満たす整数ｃをランダムに生成し秘密鍵３２３（図１１）とする。
ステップＳ７０２において、楕円曲線スカラ倍演算部２１３が、スカラ倍Ｑ1←ｃＧ＝（Ｘ：Ｙ：Ｚ）を用いて計算する。この計算は、図３〜図８に示す各処理を用いて行われる。
ステップＳ７０３において、楕円曲線スカラ倍演算部２１３が、Ｑ←（ＸQ：ＹQ：ＴQ：１）＝（Ｘ／Ｚ：Ｙ／Ｚ：ＸＹ／Ｚ2：１）をｋ上で計算することでＱ1を拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標への変換し計算結果Ｑを公開鍵とする。
ステップＳ７０４において、制御演算部２１０が、鍵ペア２２３を（ｃ，Ｑ）とし、生成した鍵ペア２２３を出力するとともに、記憶部２２０に格納する。
【０１１３】
《ＥＣＤＳＡ署名生成》
次に、本実施形態に係る楕円曲線スカラ倍演算方法を利用したＥＣＤＳＡ署名生成方法について図１１および図１２を参照して説明する。
【０１１４】
［ＥＣＤＳＡ署名生成装置］
図１１は、本実施形態に係るＥＣＤＳＡ署名生成装置の構成例を示す図である。
ＥＣＤＳＡ署名生成装置３は、制御演算部３１０および記憶部３２０を有している。
制御演算部３１０は、入出力部３１１、制御部３１２、楕円曲線スカラ倍演算部３１３、乱数生成部３１４、ハッシュ関数演算部３１５を有している。入出力部３１１は、楕円曲線のパラメータ、定義体情報、スカラ倍における係数ｄの加算時使用の有無情報、ベースポイントＧおよびその位数、署名者の秘密鍵３２３、署名対象の平文などの入力情報を受け付けるとともに、生成されたＥＣＤＳＡ署名を出力情報として出力する機能を有する。制御部３１２は、ＥＣＤＳＡ署名生成装置３を制御する機能を有する。楕円曲線スカラ倍演算部３１３は、ベースポイントのスカラ倍を計算する機能を有する。乱数生成部３１４は、乱数を生成する機能を有する。ハッシュ関数演算部３１５は、ハッシュ値を生成する機能を有する。
【０１１５】
なお、楕円曲線スカラ倍演算部３１３は、図１の楕円曲線スカラ倍演算装置１を用いて構成することができる。この場合、定義体上の演算、剰余演算（ｍｏｄ）、比較などの基本演算機能は、図１の楕円曲線スカラ倍演算装置１内の入出力部１１１を通じて基本演算部１１８を呼び出すことにより行うことができる。
【０１１６】
記憶部３２０には、中間データ３２１、データ３２２、秘密鍵３２３などが格納されている。中間データ３２１は、制御演算部３１０における演算時の中間データである。データ３２２は、入出力部３１１により入力を受け付けた楕円曲線のパラメータ、定義体情報、スカラ倍における係数ｄの加算時使用の有無情報、ベースポイントおよびその位数、署名対象の平文、生成されたＥＣＤＳＡ署名などの各情報である。秘密鍵３２３は、入出力部３１１により入力を受け付けた署名者の秘密鍵である。
【０１１７】
なお、ＥＣＤＳＡ署名生成装置３は、図１６に示すような、バス５７で接続されたＣＰＵ５１と、ＲＡＭなどのメモリ５２と、ＨＤやその他の外部記憶装置５５と、キーボードなどの入力装置５３と、ディスプレイなどの出力装置５４と、外部記憶装置５５や、入力装置５３や、出力装置５４とのインタフェース５６とを備えた、一般的な構成を有する情報処理装置５上に構築することができる。
ＥＣＤＳＡ署名生成装置３の制御演算部３１０および各部３１１〜３１５は、ＣＰＵ５１が、メモリ５２にロードされたプログラム（コードモジュールともいう）を実行することで、情報処理装置５上に具現化されるプロセスとして実現される。また、メモリ５２や、外部記憶装置５５が記憶部３２０として使用される。
【０１１８】
また、前記したプログラムは、予め外部記憶装置５５に記憶され、必要に応じてメモリ５２上にロードされ、ＣＰＵ５１により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばＣＤ−ＲＯＭなどを介して、必要に応じて、可搬性の記憶媒体からメモリ５２にロードされてもよい。また、プログラムは、一旦、ＣＤ−ＲＯＭなどの可搬性の記憶媒体からＨＤなどにインストールされた後、必要に応じて、このＨＤからメモリ５２にロードされてもよい。さらに、プログラムは、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置５が読み取り可能な媒体の一種である伝送信号により、一旦ＨＤにダウンロードされてからメモリ５２にロードされてもよいし、あるいは、直接、ネットワーク経由でメモリ５２にロードされてもよい。
【０１１９】
［ＥＣＤＳＡ署名生成処理］
図１２は、本実施形態に係るＥＣＤＳＡ署名生成処理の手順を示すフローチャートである。
入出力部３１１により、ＥＣＤＳＡ署名生成装置３が、入力情報として楕円曲線ａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）、定義体ｋ、スカラ倍における係数ｄの加算時使用の有無情報、楕円曲線のベースポイントＧ＝（ＸG：ＹG：ＴG：１）、ベースポイントの位数ｎ（素数）、署名対象の平文Ｍなどを受け付けると、これらの入力情報は記憶部３２０に格納される。なおベースポイントＧはＺ＝１とした拡張Ｉｎｖｅｒｔｅｄ  ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標で表されているものとする。
また、入出力部３１１により、ＥＣＤＳＡ署名生成装置３が、入力情報として署名者の秘密鍵３２３を受け付けると、この秘密鍵３２３は記憶部３２０に格納される。
そして、制御演算部３１０が、入力された入力情報を用いて、図１２に示すＥＣＤＳＡ署名生成処理を行い、ＥＣＤＳＡ署名を生成する。
制御演算部３１０は、生成した署名データを記憶部３２０に保持するとともに入出力部３１１より出力情報として出力して、動作を終了する。
【０１２０】
以下、図１２を参照して、ＥＣＤＳＡ署名生成処理を説明する。
ステップＳ８０１において、乱数生成部３１４が、０＜ｂ＜ｎを満たす整数ｂをランダムに生成する。
ステップＳ８０２において、楕円曲線スカラ倍演算部３１３が、Ｒ←ｂＧ＝（Ｘ1：Ｙ1：Ｚ1）を計算する。この計算は、図３〜図８の処理を用いて行われる。
ステップＳ８０３において、楕円曲線スカラ倍演算部３１３が、ｘ1←Ｚ1／Ｘ1をｋ上で計算する。
ステップＳ８０４において、楕円曲線スカラ倍演算部３１３が、定義体ｋ上の元ｘ1を正の整数に変換したものをｘ1としておき直す。
ステップＳ８０５において、楕円曲線スカラ倍演算部３１３が、ｒ←ｘ1  ｍｏｄ  ｎ  を計算する。
ステップＳ８０６において、ハッシュ関数演算部３１５が、ハッシュ関数ｈを用いてｅ←ｈ（Ｍ）を計算する。
ステップＳ８０７において、楕円曲線スカラ倍演算部３１３が、ｓ←ｂ-1（ｅ＋ｃｒ）  ｍｏｄ  ｎを計算する。
ステップＳ８０８において、制御演算部３１０が、算出した（ｒ，ｓ）を署名データとし、生成した署名データを出力するとともに、記憶部３２０に格納する。
【０１２１】
《ＥＣＤＳＡ署名検証》
次に、本実施形態に係る楕円曲線スカラ倍演算方法を利用したＥＣＤＳＡ署名検証方法について図１３〜図１５を参照して説明する。
【０１２２】
［ＥＣＤＳＡ署名検証装置］
図１３は、本実施形態に係るＥＣＤＳＡ署名検証装置の構成例を示す図である。
ＥＣＤＳＡ署名検証装置４は、制御演算部４１０および記憶部４２０を有している。
制御演算部４１０は、入出力部４１１、制御部４１２、楕円曲線スカラ倍演算部４１３、ハッシュ関数演算部４１４を有している。入出力部４１１は、楕円曲線のパラメータ、定義体情報、スカラ倍における係数ｄの加算時使用の有無情報、ベースポイント、署名者の公開鍵、ベースポイントおよび公開鍵の位数、署名検証対象の平文、署名などを入力情報として受け付けるとともに、署名検証を出力情報として出力する機能を有する。制御部４１２は、ＥＣＤＳＡ署名検証装置４を制御する機能を有する。楕円曲線スカラ倍演算部４１３は、ベースポイントおよび公開鍵のスカラ倍を計算する機能を有する。ハッシュ関数演算部４１４は、ハッシュ値を生成する機能を有する。
【０１２３】
楕円曲線スカラ倍演算部４１３は、図１の楕円曲線スカラ倍演算装置１を用いて構成することができる。この場合、定義体上の演算、剰余演算（ｍｏｄ）、比較などの基本演算機能は、図１の楕円曲線スカラ倍演算装置１内の入出力部１１１を通じて基本演算部１１８を呼び出すことにより行うことができる。
【０１２４】
記憶部４２０には、中間データ４２１およびデータ４２２などが格納されている。中間データ４２１は、制御演算部４１０における演算時の中間データである。データ４２２は、入出力部４１１により受け付けた楕円曲線のパラメータ、定義体情報、スカラ倍における係数ｄの加算時使用の有無情報、ベースポイント、署名者の公開鍵、ベースポイントおよび公開鍵の位数、署名検証対象の平文、署名などの入力情報、および署名検証結果などの出力情報などである。
【０１２５】
なお、ＥＣＤＳＡ署名検証装置４は、図１６に示すような、バス５７で接続されたＣＰＵ５１と、ＲＡＭなどのメモリ５２と、ＨＤやその他の外部記憶装置５５と、キーボードなどの入力装置５３と、ディスプレイなどの出力装置５４と、外部記憶装置５５や、入力装置５３や、出力装置５４とのインタフェース５６とを備えた、一般的な構成を有する情報処理装置５上に構築することができる。
ＥＣＤＳＡ署名検証装置４の制御演算部４１０および各部４１１〜４１４は、ＣＰＵ５１が、メモリ５２にロードされたプログラム（コードモジュールともいう）を実行することで、情報処理装置５上に具現化される。また、メモリ５２や、外部記憶装置５５が記憶部４２０として使用される。
【０１２６】
また、前記したプログラムは、予め外部記憶装置５５に記憶され、必要に応じてメモリ５２上にロードされ、ＣＰＵ５１により実行される。なお、このプログラムは、可搬性の記憶媒体、例えばＣＤ−ＲＯＭなどを介して、必要に応じて、可搬性の記憶媒体からメモリ５２にロードされてもよい。また、一旦、ＣＤ−ＲＯＭなどの可搬性の記憶媒体からＨＤなどにインストールされた後、必要に応じて、このＨＤからメモリ５２にロードされてもよい。さらに、図示していないネットワーク接続装置を介して、ネットワーク上の情報処理装置５が伝送信号により、一旦ＨＤにダウンロードされてからメモリ５２にロードされてもよい。あるいは、直接、ネットワーク経由でメモリ５２にロードされてもよい。
【０１２７】
［ＥＣＤＳＡ署名検証処理］
図１４および図１５は、本実施形態に係るＥＣＤＳＡ署名検証処理の手順を示すフローチャートである。
処理の概略を記述すると、入出力部４１１により、ＥＣＤＳＡ署名検証装置４が、入力情報として、楕円曲線ａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）、定義体ｋ、スカラ倍における係数ｄの加算時使用の有無情報、楕円曲線のベースポイントＧ＝（ＸG：ＹG：ＴG：１）、公開鍵Ｑ＝（ＸQ：ＹQ：ＴQ：１）、ベースポイントおよび公開鍵の位数ｎ（素数）、平文Ｍとその署名（ｒ，ｓ）を入力情報として受け付けると、制御演算部４１０は受け付けた入力情報を記憶部４２０に格納する。
そして、制御演算部４１０が、記憶部４２０に保持されている入力情報を用いて、図１４および図１５の処理に従ってＥＣＤＳＡ署名検証処理を行う。
制御演算部４１０は、生成された署名検証結果を、記憶部４２０に保持するとともに、入出力部４１１より出力情報として出力し、動作を終了する。
【０１２８】
まず、図１４の処理から説明する。
ステップＳ９０１において、ハッシュ関数演算部４１４が、署名生成時と同じハッシュ関数ｈを用いてｅ←ｈ（Ｍ）を計算する。
ステップＳ９０２において、楕円曲線スカラ倍演算部４１３が、ｅ1←  ｓ-1ｅ  ｍｏｄ  ｎを計算する。
ステップＳ９０３において、楕円曲線スカラ倍演算部４１３が、ｒ1←  ｓ-1ｒ  ｍｏｄ  ｎを計算する。
ステップＳ９０４において、楕円曲線スカラ倍演算部４１３が、Ｇ1←（ＸG1：ＹG1：ＺG1）＝ｅ1Ｇを計算する。この計算は、図３〜図８に示す各処理を用いて行われる。
ステップＳ９０５において、楕円曲線スカラ倍演算部４１３が、Ｑ1←（ＸQ1：ＹQ1：ＺQ1）＝ｒ1Ｑを計算する。この計算は、図３〜図８に示す各処理を用いて行われる。
ステップＳ９０６において、楕円曲線スカラ倍演算部４１３が、（Ｘ1：Ｙ1：Ｚ1）＝Ｇ1＋Ｑ1のうちＸ1、Ｚ1を図１５で後記するフローチャートに従って計算する。
ステップＳ９０７において、楕円曲線スカラ倍演算部４１３が、ｘ1←Ｚ1／Ｘ1をｋ上で計算する。
ステップＳ９０８において、楕円曲線スカラ倍演算部４１３が、署名生成時の処理（図１２）と同じ変換方法でｋ上の元ｘ1を正の整数に変換したものをｘ1としておき直す。
ステップＳ９０９において、制御演算部４１０が、、ｘ1  ｍｏｄ  ｎ＝ｒが成立するか否か検証を行い、成立すれば検証結果をＴｒｕｅ、しなければ検証結果をＦａｌｓｅとして出力するとともに、この検証結果を記憶部４２０に格納する。
【０１２９】
図１５は、ステップＳ９０６の詳細な処理手順を示すフローチャートである。
ステップＳ１００１において、楕円曲線スカラ倍演算部４１３が、Ａ←ＺG1ＺQ1、Ｂ←ｄＡ2、Ｃ←ＸG1ＸQ1、Ｄ←ＹG1ＹQ1、Ｅ←ＣＤをｋ上でそれぞれ計算する。
ステップＳ１００２において、楕円曲線スカラ倍演算部４１３が、Ｈ←Ｃ−ａＤ、Ｉ←（ＸG1＋ＹG1）（ＸQ1＋ＹQ1）−Ｃ−Ｄをｋ上でそれぞれ計算する。
ステップＳ１００３において、楕円曲線スカラ倍演算部４１３が、Ｘ1←（Ｅ＋Ｂ）Ｈをｋ上で計算する。
ステップＳ１００４において、楕円曲線スカラ倍演算部４１３が、Ｚ1←ＡＨＩをｋ上で計算する。
【０１３０】
［ハードウェア構成］
図１６は、情報処理装置のハードウェア構成例を示す図である。
この情報処理装置５は、楕円曲線スカラ倍演算装置１、ＥＣＤＳＡ鍵ペア生成装置２、ＥＣＤＳＡ署名生成装置３、ＥＣＤＳＡ署名検証装置４に相当する装置である。
情報処理装置５では、ＣＰＵ５１およびメモリ５２がバス５７を介して互いに接続されている。また、キーボードや、マウスに相当する入力装置５３、ディスプレイに相当する出力装置５４、ＨＤや、ＣＤ−ＲＯＭなどに相当し、プログラムや、データが格納されている外部記憶装置５５がインタフェース５６を介してバス５７に接続している。
【０１３１】
《まとめ》
本実施形態では、楕円曲線ａｘ2＋ｙ2＝１＋ｄｘ2ｙ2（ｋ上で係数ａは２乗根を持ち係数ｄは持たない）上の点（ｘ，ｙ）に対してｘ＝Ｚ／Ｘ、ｙ＝Ｚ／Ｙ、ＸＹＺ≠０を満たすＸ、Ｙ、Ｚ∈ｋを用いて（Ｘ：Ｙ：Ｚ）と変換したＩｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標に加えて、ｘ＝Ｚ／Ｘ、ｙ＝Ｚ／Ｙ、ｘｙ＝Ｚ／Ｔ、ＸＹＴＺ≠０を満たすＸ、Ｙ、Ｔ、Ｚ∈ｋを用いて（Ｘ：Ｙ：Ｔ：Ｚ）と変換した拡張Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を導入する。
Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した点（Ｘ：Ｙ：Ｚ）から拡張Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した点への変換は（ＸＺ：ＹＺ：ＸＹ：Ｚ2）で変換でき、拡張Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した点（Ｘ：Ｙ：Ｔ：Ｚ）からＩｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いて表現した点への変換は（Ｘ：Ｙ：Ｚ）とＴを無視することで変換することができる。
【０１３２】
拡張Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を加算の際に用いることで定義体上の２乗算１回を削減できる。
スカラ倍における２倍算は出力結果に拡張Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いた場合、Ｔ座標を求める際に乗算が１回増えるため２倍算の後に加算を行う必要がある場合のみＴ座標の計算を行う。なお加算の後には必ずＴ座標を用いることの無い２倍算が計算されるため加算時においてＴ座標を計算するために必要な乗算１回の削減が行われるため２倍算時に増加した乗算は次に行われる加算時に乗算を１回削減できるため相殺される。
さらに非特許文献３において開示されている楕円曲線の係数ｄを用いない加算方法に対して拡張Ｉｎｖｅｒｔｅｄ  Ｔｗｉｓｔｅｄ  Ｅｄｗａｒｄ座標を用いることでさらに加算１回あたり定数倍を１回削減する。
また、それぞれの加算においてａ＝−１の場合、それに特化したアルゴリズムを用いることにより加算１回あたりさらに乗算と定数倍算それぞれ１回を削減する。
スカラ倍演算の際の加算時に係数ｄを用いるか否かはスカラ倍演算に必要な情報を設定する際に指定できるものとする。
【符号の説明】
【０１３３】
１      楕円曲線スカラ倍演算装置
２      ＥＣＤＳＡ鍵ペア生成装置
３      ＥＣＤＳＡ署名生成装置
４      ＥＣＤＳＡ署名検証装置
５      情報処理装置
１１０  制御演算部（楕円曲線スカラ倍演算装置）
１１３  楕円曲線スカラ倍演算部（楕円曲線スカラ倍演算装置）
１１５  ２進数展開部
１１６  楕円曲線加算演算部
１１７  楕円曲線２倍算演算部
１１８  基本演算部
１２０  記憶部（楕円曲線スカラ倍演算装置）
２１０  制御演算部（ＥＣＤＳＡ鍵ペア生成装置）
２１３  楕円曲線スカラ倍演算部（ＥＣＤＳＡ鍵ペア生成装置）
２１４  乱数生成部（ＥＣＤＳＡ鍵ペア生成装置）
２２０  記憶部（ＥＣＤＳＡ鍵ペア生成装置）
２２３  鍵ペア
３１０  制御演算部（ＥＣＤＳＡ署名生成装置）
３１３  楕円曲線スカラ倍演算部（ＥＣＤＳＡ署名生成装置）
３１４  乱数生成部（ＥＣＤＳＡ署名生成装置）
３１５  ハッシュ関数演算部（ＥＣＤＳＡ署名生成装置置）
３２０  記憶部（ＥＣＤＳＡ署名生成装置置）
３２３  秘密鍵
４１０  制御演算部（ＥＣＤＳＡ署名検証装置）
４１３  楕円曲線スカラ倍演算部（ＥＣＤＳＡ署名検証装置）
４１４  ハッシュ関数演算部（ＥＣＤＳＡ署名検証装置）
４２０  記憶部（ＥＣＤＳＡ署名検証装置）
【図１】
2010266765.tif 000033
【図２】
2010266765.tif 000034
【図３】
2010266765.tif 000035
【図４】
2010266765.tif 000036
【図５】
2010266765.tif 000037
【図６】
2010266765.tif 000038
【図７】
2010266765.tif 000039
【図８】
2010266765.tif 000040
【図９】
2010266765.tif 000041
【図１０】
2010266765.tif 000042
【図１１】
2010266765.tif 000043
【図１２】
2010266765.tif 000044
【図１３】
2010266765.tif 000045
【図１４】
2010266765.tif 000046
【図１５】
2010266765.tif 000047
【図１６】
2010266765.tif 000048