【手続補正書】
【提出日】平成17年5月16日(2005.5.16)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
楕円曲線暗号系において、暗号化／復号化ユニット（１６）を含むプロセッサにおいて実装されておりｘ座標及びｙ座標を有する点とシード点Ｐ（２８）とを用いて、秘密鍵ｋに対応する公開鍵ｋＰ（２６）を計算する方法であって、
ａ）Ｐだけ異なる１対の点に対して連続的な２倍及び加算演算を実行して、１対の点のｘ座標の値を取得する（５１）ステップであって、前記値の一方はｋＰに対応し、前記値の他方は前記シード点Ｐに対して２倍及び加算演算を実行することによってｋＰからＰだけ異なる（［ｋ−１］Ｐ又は［ｋ＋１］Ｐ）、ステップと、
ｂ）前記ｘ座標の一方を用いて前記曲線上の１点のｙ座標の可能な値を決定するステップと、
ｃ）前記１点にＰを加算する又は前記１点からＰを減算することによって、前記１点をＰの値だけ変化させるステップと、
ｄ）前記変化させた値から得られた点の座標を前記他方の座標と比較することによって、前記１点の可能な値のどれがＰの値だけ異なるのかを判断するステップと、
を含むことを特徴とする方法。
【請求項２】
請求項１記載の方法において、ｋＰのｘ座標及びｙ座標の値を用いてｋＰを表すステップを更に含むことを特徴とする方法。
【請求項３】
請求項１記載の方法において、ステップａ）は、ｋの１ビットと１対の点であるｄＰ及び（ｄ＋１）Ｐとを用いて、
ａ）前記ビットが０に等しいときには、１対の点である２ｄＰ及び（２ｄ＋１）Ｐを計算するステップを、
ｂ）前記ビットが１に等しいときには、１対の点である（２ｄ＋１）Ｐ及び（２ｄ＋２）Ｐを計算するステップを、
含むことを特徴とする方法。
【請求項４】
請求項３記載の方法において、
ａ）前記点２ｄＰはｄＰを２倍することによって計算され、前記点（２ｄ＋１）ＰはＰを前記点２ｄＰに加算することによって計算され、
ｂ）前記点（２ｄ＋１）ＰはｄＰと（ｄ＋１）Ｐとを加算することによって計算され、
前記点（２ｄ＋２）Ｐは（ｄ＋１）Ｐを２倍することによって計算されることを特徴とする方法。
【請求項５】
請求項１記載の方法において、前記シード点Ｐは射影座標を用いて表されることを特徴とする方法。
【請求項６】
請求項１記載の方法において、前記他方の点は（ｋ−１）Ｐに対応し、ｋＰのｙ座標は、
ａ）前記１対の点のそれぞれに対して第１の可能なｙ座標を計算するステップと、
ｂ）前記他方の点の前記第１の可能なｙ座標にＰを加算して、第１の結果的なｙ座標を取得するステップと、
ｃ）前記一方の点の前記第１の可能なｙ座標と前記第１の結果的なｙ座標とを比較するステップと、
ｄ）これら２つの第１の座標が等しいときには、前記第１の可能なｙ座標の値を、前記一方の点の前記ｙ座標の値と決定するステップと、
ｅ）これら２つの第１の座標が等しくないときには、
ｉ）前記一方の点に対して第２の可能なｙ座標を計算し、
ｉｉ）前記一方の点の前記第２の可能なｙ座標と前記第１の結果的なｙ座標とを比較し、
ｉｉｉ）前記一方の点の前記第２の可能なｙ座標が前記第１の結果的なｙ座標と等しいときには、前記一方の点の前記第２の可能なｙ座標の値を、前記一方の点の前記ｙ座標の値と決定し、
ｉｖ）前記一方の点の前記第２の可能なｙ座標が前記第１の結果的なｙ座標と等しくないときには、前記他方の点に対して第２の可能なｙ座標を計算し、前記他方の点の前記第２の可能なｙ座標にＰを加算して第２の結果的なｙ座標を取得し、前記一方の点に対する前記第２の結果的なｙ座標を、前記一方の点の前記ｙ座標の値と決定するステップと、
によって決定されることを特徴とする方法。
【請求項７】
請求項６記載の方法において、前記１対の点の前記可能なｙ座標は、前記１対の点の対応するｘの値を楕円曲線の定義方程式に代入することによって計算されることを特徴とする方法。
【請求項８】
請求項１記載の方法において、ｋＰの前記ｙ座標は、
ａ）前記１対の点のそれぞれに対して第１の可能なｙ座標を計算するステップと、
ｂ）前記一方の点の前記第１の可能なｙ座標からＰを減算して、第１の結果的なｙ座標を取得するステップと、
ｃ）前記他方の点の前記第１の可能なｙ座標と前記第１の結果的なｙ座標とを比較するステップと、
ｄ）これら２つの第１の座標が等しいときには、前記一方の点の前記第１の可能なｙ座標の値を、前記一方の点の前記ｙ座標の値と決定するステップと、
ｅ）これら２つの第１の座標が等しくないときには、
ｉ）前記他方の点に対して第２の可能なｙ座標を計算し、
ｉｉ）前記他方の点の前記第２の可能なｙ座標と前記第１の結果的なｙ座標とを比較し、
ｉｉｉ）前記他方の点の前記第２の可能なｙ座標が前記第１の結果的なｙ座標と等しいときには、前記一方の点の前記第１の可能なｙ座標の値を、前記一方の点の前記ｙ座標の値と決定し、
ｉｖ）前記他方の点の前記第２の可能なｙ座標が前記第１の結果的なｙ座標と等しくないときには、前記一方の点に対して第２の可能なｙ座標を計算し、前記一方の点に対する前記第２の可能なｙ座標を、前記一方の点の前記ｙ座標の値と決定するステップと、
によって決定されることを特徴とする方法。
【請求項９】
請求項１記載の方法において、前記他方の点は（ｋ＋１）Ｐに対応し、前記一方の点の前記ｙ座標は、
ａ）前記１対の点のそれぞれに対して第１の可能なｙ座標を計算するステップと、
ｂ）前記一方の点の前記第１の可能なｙ座標にＰを加算して、第１の結果的なｙ座標を取得するステップと、
ｃ）前記他方の点の前記第１の可能なｙ座標と前記第１の結果的なｙ座標とを比較するステップと、
ｄ）これら２つの第１の座標が等しいときには、前記一方の点の前記第１の可能なｙ座標の値を、前記一方の点の前記ｙ座標の値と決定するステップと、
ｅ）これら２つの第１の座標が等しくないときには、
ｉ）前記他方の点に対して第２の可能なｙ座標を計算し、
ｉｉ）前記他方の点の前記第２の可能なｙ座標と前記第１の結果的なｙ座標とを比較し、
ｉｉｉ）前記他方の点の前記第２の可能なｙ座標が前記第１の結果的なｙ座標と等しいときには、前記一方の結果的なｙ座標の値を、前記一方の点の前記ｙ座標の値と決定し、
ｉｖ）前記他方の点の前記第２の可能なｙ座標が前記第１の結果的なｙ座標と等しくないときには、前記一方の点に対して第２の可能なｙ座標を計算し、前記一方の点に対する前記第２の可能なｙ座標を、前記一方の点の前記ｙ座標の値と決定するステップと、
によって決定されることを特徴とする方法。
【請求項１０】
請求項１記載の方法において、
ａ）前記一方の点の前記ｙ座標から識別子を取得するステップと、
ｂ）前記識別子とｋＰのｘ座標とを用いてｋＰを表すステップと、
を更に含むことを特徴とする方法。
【請求項１１】
請求項１０記載の方法において、前記識別子は前記一方の点の前記ｙ座標の単一ビットであることを特徴とする方法。
【請求項１２】
ｓＰの値とｅＱの値とを計算するステップと、ｓＰ−ｅＱを計算するステップと、ｓＰ−ｅＱ＝ｒであるかどうかをチェックするステップとを含む、デジタル署名を確認する方法であって、
ａ）請求項１ないし請求項１１のいずれかの請求項に記載の方法を用いて、ｓＰ及びｅＱの少なくとも一方を計算するステップを含むことを特徴とする方法。
【請求項１３】
請求項１ないし請求項１１のいずれかの請求項に記載の方法を用いて楕円曲線デジタル署名を計算することを特徴とする方法。
【請求項１４】
楕円曲線において、ｘ座標及びｙ座標を有する点とシード点Ｐ（２８）とを用いて、公開鍵ｋＰ（２６）を計算する計算装置（１６）であって、
ａ）１対の点のｘ座標の値を取得する（５１）手段であって、前記値の一方はｋＰに対応し、前記値の他方は前記シード点Ｐに対して２倍及び加算演算を実行することによってｋＰからＰだけ異なる（［ｋ−１］Ｐ又は［ｋ＋１］Ｐ）、手段と、
ｂ）前記一方の点（ｋＰ）の可能な値の１つに対応する前記楕円曲線上の点を、前記一方の点のｘ座標から前記一方の点のｙ座標の可能な値を導くことにより、決定する手段と、
ｃ）前記他方の点（［ｋ−１］Ｐ又は［ｋ＋１］Ｐ）の可能な値の１つに対応する前記楕円曲線上の点を、前記他方の点のｘ座標から前記他方の点のｙ座標の可能な値を導くことにより、決定する手段と、
前記他方の点に対応する前記可能な点の１つとＰだけ異なる前記一方の点に対応する前記可能な点の前記１つとして、ｋＰの値を選択する手段と、
を備えていることを特徴とする計算装置。
【請求項１５】
請求項１４記載の計算装置（１６）において、ｋＰのｘ座標及びｙ座標の値を用いてｋＰを表す手段を更に含むことを特徴とする計算装置。
【請求項１６】
請求項１５記載の計算装置（１６）において、ｋＰのｘ座標及びｙ座標の値を用いてｋＰを表す前記手段は、ｋの１ビットと１対の点であるｄＰ及び（ｄ＋１）Ｐとを用いて、
ａ）前記ビットが０に等しいときには、１対の点である２ｄＰ及び（２ｄ＋１）Ｐを計算し、
ｂ）前記ビットが１に等しいときには、１対の点である（２ｄ＋１）Ｐ及び（２ｄ＋２）Ｐを計算するように動作することを特徴とする計算装置。
【請求項１７】
請求項１６記載の計算装置（１６）において、
ａ）前記点２ｄＰはｄＰを２倍することによって計算され、前記点（２ｄ＋１）ＰはＰを前記点２ｄＰに加算することによって計算され、
ｂ）前記点（２ｄ＋１）ＰはｄＰと（ｄ＋１）Ｐとを加算することによって計算され、前記点（２ｄ＋２）Ｐは（ｄ＋１）Ｐを２倍することによって計算されることを特徴とする計算装置。
【請求項１８】
請求項１４記載の計算装置（１６）において、前記シード点Ｐは射影座標を用いて表されることを特徴とする計算装置。
【請求項１９】
請求項１４記載の計算装置（１６）において、前記他方の点は（ｋ−１）Ｐに対応し、前記決定する手段は、
ａ）前記１対の点のそれぞれに対して第１の可能なｙ座標を計算するステップと、
ｂ）前記他方の点の前記第１の可能なｙ座標にＰを加算して、第１の結果的なｙ座標を取得するステップと、
ｃ）前記一方の点の前記第１の可能なｙ座標と前記第１の結果的なｙ座標とを比較するステップと、
ｄ）これら２つの第１の座標が等しいときには、前記第１の可能なｙ座標の値を、前記一方の点の前記ｙ座標の値と決定するステップと、
ｅ）これら２つの第１の座標が等しくないときには、
ｉ）前記一方の点に対して第２の可能なｙ座標を計算し、
ｉｉ）前記一方の点の前記第２の可能なｙ座標と前記第１の結果的なｙ座標とを比較し、
ｉｉｉ）前記一方の点の前記第２の可能なｙ座標が前記第１の結果的なｙ座標と等しいときには、ｋＰの前記第２の可能なｙ座標の値を、前記一方の点の前記ｙ座標の値と決定し、
ｉｖ）前記一方の点の前記第２の可能なｙ座標が前記第１の結果的なｙ座標と等しくないときには、前記他方の点に対して第２の可能なｙ座標を計算し、前記他方の点の前記第２の可能なｙ座標にＰを加算して第２の結果的なｙ座標を取得し、前記一方の点に対する前記第２の結果的なｙ座標を、ｋＰの前記ｙ座標の値と決定するステップと、
によって動作することを特徴とする計算装置。
【請求項２０】
請求項１９記載の計算装置（１６）において、前記１対の点の前記可能なｙ座標は、前記１対の点の対応するｘの値を楕円曲線の定義方程式に代入することによって計算されることを特徴とする計算装置。
【請求項２１】
請求項１４記載の計算装置（１６）において、前記他方の点は（ｋ−１）Ｐに対応し、前記決定する手段は、
ａ）前記１対の点のそれぞれに対して第１の可能なｙ座標を計算するステップと、
ｂ）前記一方の点の前記第１の可能なｙ座標からＰを減算して、第１の結果的なｙ座標を取得するステップと、
ｃ）前記他方の点の前記第１の可能なｙ座標と前記第１の結果的なｙ座標とを比較するステップと、
ｄ）これら２つの第１の座標が等しいときには、前記一方の点の前記第１の可能なｙ座標の値を、前記一方の点の前記ｙ座標の値と決定するステップと、
ｅ）これら２つの第１の座標が等しくないときには、
ｉ）前記他方の点に対して第２の可能なｙ座標を計算し、
ｉｉ）前記他方の点の前記第２の可能なｙ座標と前記第１の結果的なｙ座標とを比較し、
ｉｉｉ）前記他方の点の前記第２の可能なｙ座標が前記第１の結果的なｙ座標と等しいときには、前記一方の点の前記第１の可能なｙ座標の値を、前記一方の点の前記ｙ座標の値と決定し、
ｉｖ）前記他方の点の前記第２の可能なｙ座標が前記第１の結果的なｙ座標と等しくないときには、前記一方の点に対して第２の可能なｙ座標を計算し、前記一方の点に対する前記第２の可能なｙ座標を、前記一方の点の前記ｙ座標の値と決定するステップと、
によって動作することを特徴とする計算装置。
【請求項２２】
請求項１４記載の計算装置（１６）において、前記他方の点は（ｋ＋１）Ｐに対応し、前記決定する手段は、
ａ）前記１対の点のそれぞれに対して第１の可能なｙ座標を計算するステップと、
ｂ）前記一方の点の前記第１の可能なｙ座標にＰを加算して、第１の結果的なｙ座標を取得するステップと、
ｃ）前記他方の点の前記第１の可能なｙ座標と前記第１の結果的なｙ座標とを比較するステップと、
ｄ）これら２つの第１の座標が等しいときには、前記一方の点の前記第１の可能なｙ座標の値を、前記一方の点の前記ｙ座標の値と決定するステップと、
ｅ）これら２つの第１の座標が等しくないときには、
ｉ）前記他方の点に対して第２の可能なｙ座標を計算し、
ｉｉ）前記他方の点の前記第２の可能なｙ座標と前記第１の結果的なｙ座標とを比較し、
ｉｉｉ）前記他方の点の前記第２の可能なｙ座標が前記第１の結果的なｙ座標と等しいときには、前記一方の結果的なｙ座標の値を、前記一方の点の前記ｙ座標の値と決定し、
ｉｖ）前記他方の点の前記第２の可能なｙ座標が前記第１の結果的なｙ座標と等しくないときには、ｋＰに対して第２の可能なｙ座標を計算し、ｋＰに対する前記第２の可能なｙ座標を、ｋＰの前記ｙ座標の値と決定するステップと、
によって動作することを特徴とする計算装置。
【請求項２３】
請求項１４記載の計算装置（１６）であって、
ａ）ｋＰの前記ｙ座標から識別子を取得する手段と、
ｂ）前記識別子とｋＰのｘ座標とを用いてｋＰを表す手段と、
を更に備えていることを特徴とする計算装置。
【請求項２４】
請求項２５記載の計算装置（１６）であって、前記識別子はｋＰの前記ｙ座標の単一ビットであることを特徴とする計算装置。
【請求項２５】
請求項１ないし請求項１３のいずれかの請求項に記載の方法を実行させるプログラム命令を含むコンピュータ・プログラム。