【手続補正書】
【提出日】平成18年3月24日(2006.3.24)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
体Ｆ2 m 上で定義される楕円曲線上における点Ｐの倍数を決定する倍数決定方法において、
（ａ）数値ｋを、２値数ｋi からなるベクトルとして表すステップと、
（ｂ）差がＰを越えない１対の点である点Ｐ1 および点Ｐ2 を作るステップと、
（ｃ）ｋi をそれぞれ順に選択し、さらに、それぞれのｋi について、ｋi が１のときには、上記点Ｐ1 および点Ｐ2 の対を加えて新しい点Ｐ1 を形成し、点Ｐを点Ｐ1 に加えて新しい点Ｐ2 を形成して、これらの新しい２点で点Ｐ1 および点Ｐ2 の対を置き換え、また、ｋi が０のときには、上記の点Ｐ1 を２倍して新しい点Ｐ1 を形成し、上記点Ｐを加えて新しい点Ｐ2 を形成して、これらの新しい２点で点Ｐ1 および点Ｐ2 の対を置き換え、Ｍ−１回（ただし、Ｍはｋの桁数）の繰り返しで上記点Ｐ1 から積ｋＰを求めるステップとを含む倍数決定方法。
【請求項２】
上記楕円曲線が式ｙ2 ＋ｘｙ＝ｘ3 ＋ａｘ2 ＋ｂで表現され、上記体は正規基底を成す元Ａv （ただし、ｖ＝２i ；０≦ｉ≦ｍ）を含むように選択されている請求項１に記載の倍数決定方法。
【請求項３】
上記曲線上における点の座標をベクトルの集合として表すステップを含み、
個々のベクトルがこの点の座標を表し、かつｍ個の２値数を有し、
２値数それぞれが該ベクトルの正規基底表現における複数個の係数Ａv （ただし、ｖ＝２i ）を表す請求項２に記載の倍数決定方法。
【請求項４】
点Ｐ1 と点Ｐ2 との上記の加算では、点Ｐ1 ，点Ｐ2 および点Ｐ1 −Ｐ2 のｘ座標だけを使う請求項３に記載の倍数決定方法。
【請求項５】
ｘ3 ＋ｘ4 ＝ｘ1 ｘ2 ／（ｘ1 ＋ｘ2 ）2 （ただし、ｘ1 とｘ2 とはそれぞれ点Ｐ1 と点Ｐ2 とのｘ座標、ｘ3 はＰ1 ＋Ｐ2 のｘ座標、ｘ4 はＰ1 −Ｐ2 のｘ座標）を計算することによって上記加える点のｘ座標を得る請求項４に記載の倍数決定方法。
【請求項６】
上記座標を射影座標に変換することを含む請求項５に記載の倍数決定方法。
【請求項７】
ｘ3 ＝ｘ14＋ｂｚ14を計算することによって上記座標ｘ3 を得る請求項６に記載の倍数決定方法。
【請求項８】
上記点（ｋ−１）Ｐおよび点ｋＰのｘ座標を使って、上記ｘ座標から上記点ｋＰのｙ座標を計算することを含む請求項４に記載の倍数決定方法。
【請求項９】
上記点ｋＰのｘ座標を上記の楕円曲線方程式に代入することによって、点ｋＰのｙ座標を計算することを含む請求項８に記載の倍数決定方法。
【請求項１０】
データ通信リンクで結ばれた２つの通信部間で代数曲線上の点の座標を伝送する座標伝送方法であり、
一方の通信部から他方の通信部に対して上記点の座標を送るステップと、
上記他方の通信部において、上記代数曲線のパラメタを得るステップと、
上記他方の通信部において、上記一方の座標と代数曲線とから該点の他方の座標を計算するステップとを含む座標伝送方法。
【請求項１１】
上記他方の座標を識別する情報を上記一方の座標とともに送るステップと、
この識別情報と認識関数とを使用して、上記他方の座標の適切な値を決定するステップとをさらに含む請求項１０に記載の座標伝送方法。
【請求項１２】
上記識別情報が、上記他方の座標の適切な値を示す、他方の座標のデジタルビットである請求項１１に記載の座標伝送方法。
【請求項１３】
上記代数曲線が、ｙ2 ＋ｘｙ＝ｘ3 ＋ａｘ2 ＋ｂで表さる楕円曲線であり、
二次方程式を解いて上記他方の座標が取り得る値を２つ求め、上記の識別情報によって、これら２つの値から適当な方を選択することによって、上記他方の座標を決定する請求項１２に記載の座標伝送方法。
【請求項１４】
上記識別情報が、上記他方の座標の適切な値を示す、他方の座標のデジタルビットである請求項１３に記載の座標伝送方法。
【請求項１５】
上記代数曲線は、有限体Ｆ2 m 上で定義されるｙ2 ＋ｘｙ＝ｘ3 ＋ａｘ＋ｂで表される楕円曲線である請求項１４に記載の座標伝送方法。
【請求項１６】
上記の他方の座標を識別する情報を上記の座標とともに送るステップと、
この識別情報と認識関数とを使用して、上記他方の座標の適切な値を決定するステップとをさらに含む請求項１５に記載の座標伝送方法。
【請求項１７】
上記の体ＧＦ２m が正規基底を成す元Ａv （ただし、ｖ＝２i ）を含む請求項１６に記載の座標伝送方法。
【請求項１８】
二次方程式を解いて上記他方の座標の取り得る値を２つ求め、上記の識別情報によって、これら２つの値から適当な方を選択することで、上記他方の座標を決定する請求項１７に記載の座標伝送方法。
【請求項１９】
ｃw （ただし、ｗ＝２g ，ｃ＝Ｘ0 ＋ａ＋ｂ／Ｘ02，Ｘ0 は上記一方の座標）の形式の項をｇ＝０からｇ＝ｍ−１まで加えることによって上記の二次方程式を解く請求項１８に記載の座標伝送方法。
【請求項２０】
正規基底表現したｃをｇ回循環シフトすることによってｃw （ただし、ｗ＝２g ）の形式の項を得る請求項１９に記載の方法。
【請求項２１】
上記の楕円曲線が体Ｚｐ上で定義され、
上記識別情報が適当な値のレジェンド（Legend）記号を示す請求項２０に記載の座標伝送方法。
【請求項２２】
上記の曲線が体ｚｐ上で定義され、
その元が、取り得る値の一方を含む部分集合（subsets ）と、他方の取り得る値を含む部分集合との対に分割されて、上記の識別情報が、これら２つの部分集合のうち、適当な値を含む部分集合を示す請求項２１に記載の座標伝送方法。
【請求項２３】
楕円曲線の上に存在し、座標（ｘ，ｙ）で表される点Ｐの倍数ｋを決定する倍数決定方法であり、
（ａ）差が既知である２つの点Ｐ1 とＰ2 との和のｘ座標を計算するステップと、
（ｂ）差がＰに等しい点Ｐ1 および点Ｐ2 と、点Ｐとのｘ座標から、点Ｐ1 と点Ｐ2 との和のｘ座標を計算するステップと、
（ｃ）この計算をｋ回反復して、点ｋＰと点（ｋ＋１）Ｐとの対のｘ座標を得るステップと、
（ｄ）この点ｋＰと点（ｋ＋１）Ｐとのｘ座標を使って点ｋＰのｙ座標を求めるステップとを含む倍数決定方法。
【請求項２４】
上記楕円曲線が、体Ｆ2 ｍで定義される請求項２３に記載の倍数決定方法。
【請求項２５】
上記楕円曲線が、体Ｆｐ上で定義される請求項２３に記載の倍数決定方法。
【請求項２６】
点ｋＰと点（ｋ＋１）Ｐとの擬似座標を使って上記ｙ座標を求める請求項２４に記載の倍数決定方法。
【請求項２７】
＝（ｘ1 ＋ｘ2 ）｛１／（ｘ1 Ｚ3 ）（Ｘ3 （ｘ1 ＋ｘ2 ）＋Ｚ3 ｙ1 ）＋ｘ2 ｝＋ｙ1 （ただし、ｘ3 は点（ｋ＋１）Ｐのｘ座標、ｘ2 はｋＰのｘ座標であり、ｘ2 ＝Ｘ2 ／Ｚ2 かつ、ｘ3 ＝Ｘ3 ／Ｚ3 ）を計算することによって上記ｙ座標を求める請求項２４に記載の倍数決定方法。
【請求項２８】
【数１】
2002508523.tif 000001
を計算することによって、上記ｙ座標を求める請求項２５に記載の倍数決定方法。
【請求項２９】
楕円曲線上の点であるとともに、楕円曲線暗号システムの所定パラメータであるＰ＝（ｘ1,ｙ1 ）と上記楕円曲線暗号システムとから公開鍵ｋＰを算出する方法であって、
ａ）ＰのＸおよびＺ座標の射影を算出するステップと、
ｂ）前記ＰのＸおよびＺ座標の射影を用いて、前記Ｐに連続する２倍加算演算を実行することによって、１）ｋＰのＸおよびＺ座標の射影であるＸ2,およびＺ2 と、２）（ｋ＋１）ＰのＸおよびＺ座標の射影であるＸ3 およびＺ3 とを得るステップと、
ｃ）Ｘ2 とＺ2 とを結合させて、ｋＰのアフィンｘ座標ｘ2 を導出するステップと、
ｄ）前記点Ｐの座標として導出された前記ｘ2 の値と（ｋ＋１）Ｐの射影座標Ｘ3 およびＺ3 とを結合させて、ｋＰのアフィンｙ座標ｙ2 を得るステップとを含むことを特徴とする算出方法。
【請求項３０】
上記楕円曲線暗号システムは、標数が２の体上で定義されていることを特徴とする請求項２９に記載の算出方法。
【請求項３１】
ｋＰの前記アフィンｙ座標の決定は、ｘ1 Ｚ3 の逆数を用いて行われることを特徴とする請求項３０に記載の算出方法。
【請求項３２】
【数１３】
2002508523.tif 000002
を計算することによって、ｋＰの前記アフィンｙ座標を決定することを特徴とする請求項３１に記載の算出方法。
【請求項３３】
上記楕円曲線暗号システムは、標数が奇数の体上で定義されていることを特徴とする請求項２９に記載の算出方法。
【請求項３４】
ｋＰの前記アフィンｙ座標の決定は、Ｚ3 の逆数を用いて行われることを特徴とする請求項３３に記載の算出方法。
【請求項３５】
前記楕円曲線は、一対のパラメータａ，ｂと関連づけられており、
【数１４】
2002508523.tif 000003
を計算することによって、ｋＰの前記アフィンｙ座標を決定することを特徴とする請求項３４に記載の算出方法。
【請求項３６】
ｋＰの前記アフィンｙ座標の決定は、ｙ1 Ｚ3 の逆数を用いて行われることを特徴とする請求項３３に記載の算出方法。
【請求項３７】
前記楕円曲線は、一対のパラメータａ，ｂと関連づけられており、
【数１５】
2002508523.tif 000004
を計算することによって、ｋＰの前記アフィンｙ座標を決定することを特徴とする請求項３６に記載の算出方法。