【手続補正書】
【提出日】平成19年3月2日(2007.3.2)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】   
【請求項１】
ｋをｎビットのべき乗数、Ａを被べき乗数とする、Ａk のべき乗演算を行う前にべき数値処理部で前記ｋを前処理し、処理後のべき乗数をＡと共に演算部に加えてＡk演算を行うべき乗演算装置における前記べき数値処理部であって、
正負を表す符号ビットと前記整数ｋとを含むビット列を格納するビット列格納手段と、
ビット列格納手段に格納されているビット列から符号ビットを含むｎ未満の所定ビット数の演算用ビット列データを読み出し、読み出した演算用ビット列データを基にして被べき乗数Ａの演算方法を指定し、読み出した演算用ビット列データが特定のものである場合に、読み出した演算用ビット列データを基にして変換用ビット列データを生成し、指定した演算方法で演算するよう演算部へ指示する判定手段と、
変換用ビット列データが生成された場合に、当該変換用ビット列データにより前記ビット列格納手段内の対応するビット列を更新する更新手段と、
ビット列格納手段から次に読み出すビット位置を、符号ビットを除き上位から下位ビット側にシフトする読み出し位置シフト手段と、
上記各手段を（ｎ＋１）回繰り返し動作させる繰り返し制御手段と、
を備え、
前記読み出し位置シフト手段は、符号ビットを除き、ビット列格納手段中でビット列を桁上げする桁上げ手段であり、
前記判定手段は、前記演算用ビット列データとして、符号ビットと前記符号ビットを除いた上位３ビットのデータを前記ビット列格納手段から読み出す
ことを特徴とするべき乗演算装置のべき数値処理部。
【請求項２】
前記べき乗演算装置は、Ａk のべき乗演算を用いて、暗号通信、署名通信又はメッセージ認証を行う
ことを特徴とする請求項１に記載のべき乗演算装置のべき数値処理部。
【請求項３】
前記判定手段は、読み出した演算用ビット列データの前記符号ビットが正を示し前記上位３ビットが「０１１」である場合、又は読み出した演算用ビット列データの前記符号ビットが負を示し前記上位３ビットのうち上位２ビットが「１０」である場合に、それぞれ、変換用ビット列データとして、負を示す符号ビットと「００１」又は正を示す符号ビットと「１０」を生成し、
前記更新手段は、「１００１」又は「０１０」により、前記ビット列格納手段内の対応するビット列を更新する
ことを特徴とする請求項２に記載のべき乗演算装置のべき数値処理部。
【請求項４】
前記判定手段は、読み出した演算用ビット列データの前記符号ビットが正を示し前記上位３ビットが「０１１」である場合、又は読み出した演算用ビット列データの前記符号ビットが正を示し前記上位３ビットのうち上位１ビットが「１」である場合に、それぞれ、演算方法として、被べき乗数Ａの乗算を指定し、読み出した演算用ビット列データの前記符号ビットが負を示し前記上位３ビットのうち上位２ビットが「１０」である場合、演算方法として、被べき乗算Ａの逆数の乗算を指定し、読み出した演算用ビット列データがその他の場合、乗算しない指示を行なう
ことを特徴とする請求項３に記載のべき乗演算装置のべき数値処理部。
【請求項５】
前記判定手段は、
第１欄に第１群のビットパターンが、第２欄に第２群のビットパターンが対応記述されたテーブルを含み、
読み出し手段が読み出した演算用ビット列データのビットパターンの少なくとも一部を共通にするビットパターンを第１群のビットパターンから検索し、検索したビットパターンに対応して記述されたビットパターンを第２群のビットパターンから読み出し、これを変換用ビット列データとして生成すること、
を特徴とする請求項４に記載のべき乗演算装置のべき数値処理部。
【請求項６】
前記テーブルは更に第３欄を備え、第３欄に演算方法が記述されており、
前記判定手段は、テーブルの第３欄に記述された演算方法を指定する
ことを特徴とする請求項５に記載のべき乗演算装置のべき数値処理部。
【請求項７】
前記ビット列格納手段が、最上位ビットを符号ビットとするｎ＋２ビットのレジスタであり、読み出し位置シフト手段が、レジスタに格納されたビット列を、最上位ビットを除き１ビットづつ左シフトするシフタであること、
を特徴とする請求項４に記載のべき乗演算装置のべき数値処理部。
【請求項８】
前記符号ビットは１ビットの値「０」により正を、１ビットの値「１」により負を示し、
前記判定手段は、所定の論理式を格納した演算手段であり、ビット列格納手段から読み出した演算用ビット列データの各ビットの値を前記論理式に代入して変換用ビット列データを生成し、
前記判定手段の格納する論理式は、ビット列格納手段から読み出した演算用ビット列データの前記符号ビットをＢ0とし、前記上位３ビットを上位ビットから、Ｂ1Ｂ2Ｂ3とし、生成すべき変換用ビット列データの符号ビットをＤ0とし、前記上位３ビットを上位ビットから、Ｄ1Ｄ2Ｄ3とした場合、以下の式で与えられること、
を特徴とする請求項２に記載のべき乗演算装置のべき数値処理部。
【数１】
2000330470.tif 000001
【請求項９】
前記判定手段は、所定の論理式を格納しており、ビット列格納手段から読み出した演算用ビット列データの各ビットの値を当該論理式に代入して演算方法を求めること、
を特徴とする請求項８に記載のべき乗演算装置のべき数値処理部。
【請求項１０】
前記判定手段は、ビット列格納手段から読み出した演算用ビット列データの前記符号ビットをＢ0とし、前記上位３ビットを上位ビットから、Ｂ1Ｂ2Ｂ3とし、Ａの乗算を行なうか否かの指定信号をＳA、Ａ-1の乗算を行なうか否かの指定信号をＳA-1とした場合、指定信号は以下の式で与えられること、
を特徴とする請求項８に記載のべき乗演算装置のべき数値処理部。
【数２】
2000330470.tif 000002
【請求項１１】
ｎビットの定数ｐによる剰余体上の楕円曲線をＥ（Ｆｐ）、ｐ以下の正の整数をｋ、楕円曲線Ｅ（Ｆｐ）上の点をＡとした場合、べき倍点ｋＡの演算を行なう前に前処理部で前記ｋを前処理し、処理後のべき値をＡとともに演算部に加えてｋＡ演算を行なう楕円べき倍演算装置における前記前処理部であって、
正負を表す符号ビットと前記整数ｋとを含むビット列を格納するビット列格納手段と、
ビット列格納手段に格納されているビット列から符号ビットを含むｎ未満の所定ビット数の演算用ビット列データを読み出す読み出し、読み出した演算用ビット列データを基にして楕円曲線上の点Ａの演算方法を指定し、読み出した演算用ビット列データを基にして変換用ビット列データを生成し、指定した演算方法で演算するよう演算部へ指示する判定手段と、
変換用ビット列データが生成された場合に、当該変換用ビット列データにより前記ビット列格納手段内の対応するビット列を更新する更新手段と、
ビット列格納手段から次に読み出すビット位置を、符号ビットを除いて下位ビット側にシフトする読み出し位置シフト手段と、
上記各手段を（ｎ＋１）回繰り返し動作させる繰り返し制御手段とを備え、
前記読み出し位置シフト手段は、符号ビットを除き、ビット列格納手段中でビット列を桁上げする桁上げ手段であり、
前記判定手段は、前記演算用ビット列データとして、符号ビットと前記符号ビットを除いた上位３ビットのデータを前記ビット列格納手段から読み出す
ことを特徴とする楕円べき倍点演算装置の前処理部。
【請求項１２】
前記べき乗演算装置は、べき倍点ｋＡの演算を用いて、暗号通信、署名通信又はメッセージ認証を行う
ことを特徴とする請求項１１に記載の楕円べき倍点演算装置の前処理部。
【請求項１３】
前記判定手段は、読み出した演算用ビット列データの前記符号ビットが正を示し前記上位３ビットが「０１１」である場合、又は読み出した演算用ビット列データの前記符号ビットが負を示し前記上位３ビットのうち上位２ビットが「１０」である場合に、それぞれ、変換用ビット列データとして、負を示す符号ビットと「００１」又は正を示す符号ビットと「１０」を生成し、
前記更新手段は、「１００１」又は「０１０」により、前記ビット列格納手段内の対応するビット列を更新する
を特徴とする請求項１２に記載の楕円べき倍点演算装置の前処理部。
【請求項１４】
前記判定手段は、読み出した演算用ビット列データの前記符号ビットが正を示し前記上位３ビットが「０１１」である場合、又は読み出した演算用ビット列データの前記符号ビットが正を示し前記上位３ビットのうち上位１ビットが「１」である場合に、それぞれ、演算方法として、楕円加算を指定し、読み出した演算用ビット列データの前記符号ビットが負を示し前記上位３ビットのうち上位２ビットが「１０」である場合、演算方法として、楕円減算を指定し、読み出した演算用ビット列データがその他の場合、加算も減算もしない指示を行なう
を特徴とする請求項１３に記載の楕円べき倍点演算装置の前処理部。
【請求項１５】
前記符号ビットは１ビットの値「０」により正を、１ビットの値「１」により負を示し、
前記判定手段は、所定の論理式を格納した演算手段であり、ビット列格納手段から読み出した演算用ビット列データの各ビットの値を前記論理式に代入して変換用ビット列を生成し、
前記判定手段の格納する論理式は、ビット列格納手段から読み出した演算用ビット列データの前記符号ビットをＢ0とし、前記上位３ビットを上位ビットから、Ｂ1Ｂ2Ｂ3とし、生成すべき変換用ビット列データの符号ビットをＤ0とし、上位３ビットをＤ1Ｄ2Ｄ33とした場合、以下の式で与えられること、
を特徴とする請求項１４に記載の楕円べき倍点演算装置の前処理部。
【数３】
2000330470.tif 000003
【請求項１６】
前記判定手段は、ビット列格納手段から読み出した演算用ビット列データの前記符号ビットをＢ0とし、前記上位３ビットを上位ビットから、Ｂ1Ｂ2Ｂ3とし、楕円加算を行なうか否かの指定信号をＳA、楕円減算を行なうか否かの指定信号をＳA-1とした場合、指定信号は以下の式で与えられること、
を特徴とする請求項１５に記載の楕円べき倍点演算装置の前処理部。
【数４】
2000330470.tif 000004
【請求項１７】
ｋをｎビットのべき乗数、Ａを被べき乗数とする、Ａk のべき乗演算を行う前にべき数値処理部で前記ｋを前処理し、処理後のべき乗数をＡと共に演算部に加えてＡk演算を行うべき乗演算装置における前記べき数値処理部において用いられるべき数値処理方法であって、
正負を表す符号ビットと前記整数ｋとを含むビット列を格納するビット列格納手段に格納されているビット列から符号ビットを含むｎ未満の所定ビット数の演算用ビット列データを読み出し、読み出した演算用ビット列データを基にして被べき乗数Ａの演算方法を指定し、読み出した演算用ビット列データが特定のものである場合に、読み出した演算用ビット列データを基にして変換用ビット列データを生成し、指定した演算方法で演算するよう演算部へ指示する判定ステップと、
変換用ビット列データが生成された場合に、当該変換用ビット列データにより前記ビット列格納手段内の対応するビット列を更新する更新ステップと、
ビット列格納手段から次に読み出すビット位置を、符号ビットを除き上位から下位ビット側にシフトする読み出し位置シフトステップと、
上記各ステップを（ｎ＋１）回繰り返し動作させる繰り返し制御ステップと、
を含み、
前記読み出し位置シフトステップは、符号ビットを除き、ビット列格納手段中でビット列を桁上げし、
前記判定ステップは、前記演算用ビット列データとして、符号ビットと前記符号ビットを除いた上位３ビットのデータを前記ビット列格納手段から読み出す
ことを特徴とするべき乗演算装置のべき数値処理方法。
【請求項１８】
ｋをｎビットのべき乗数、Ａを被べき乗数とする、Ａk のべき乗演算を行う前にべき数値処理部で前記ｋを前処理し、処理後のべき乗数をＡと共に演算部に加えてＡk演算を行うべき乗演算装置における前記べき数値処理部において用いられるべき数値処理プログラムを記録しているコンピュータ読み取り可能な記録媒体であって、
前記べき数値処理プログラムは、コンピュータに、
正負を表す符号ビットと前記整数ｋとを含むビット列を格納するビット列格納手段に格納されているビット列から符号ビットを含むｎ未満の所定ビット数の演算用ビット列データを読み出し、読み出した演算用ビット列データを基にして被べき乗数Ａの演算方法を指定し、読み出した演算用ビット列データが特定のものである場合に、読み出した演算用ビット列データを基にして変換用ビット列データを生成し、指定した演算方法で演算するよう演算部へ指示する判定ステップと、
変換用ビット列データが生成された場合に、当該変換用ビット列データにより前記ビット列格納手段内の対応するビット列を更新する更新ステップと、
ビット列格納手段から次に読み出すビット位置を、符号ビットを除き上位から下位ビット側にシフトする読み出し位置シフトステップと、
上記各ステップを（ｎ＋１）回繰り返し動作させる繰り返し制御ステップと、
を実行させ、
前記読み出し位置シフトステップは、符号ビットを除き、ビット列格納手段中でビット列を桁上げし、
前記判定ステップは、前記演算用ビット列データとして、符号ビットと前記符号ビットを除いた上位３ビットのデータを前記ビット列格納手段から読み出す
ことを特徴とする記録媒体。
【請求項１９】
ｎビットの定数ｐによる剰余体上の楕円曲線をＥ（Ｆｐ）、ｐ以下の正の整数をｋ、楕円曲線Ｅ（Ｆｐ）上の点をＡとした場合、べき倍点ｋＡの演算を行なう前に前処理部で前記ｋを前処理し、処理後のべき値をＡとともに演算部に加えてｋＡ演算を行なう楕円べき倍演算装置における前記前処理部で用いられる前処理方法であって、
正負を表す符号ビットと前記整数ｋとを含むビット列を格納するビット列格納手段に格納されているビット列から符号ビットを含むｎ未満の所定ビット数の演算用ビット列データを読み出す読み出し、読み出した演算用ビット列データを基にして楕円曲線上の点Ａの演算方法を指定し、読み出した演算用ビット列データを基にして変換用ビット列データを生成し、指定した演算方法で演算するよう演算部へ指示する判定ステップと、
変換用ビット列データが生成された場合に、当該変換用ビット列データにより前記ビット列格納手段内の対応するビット列を更新する更新ステップと、
ビット列格納手段から次に読み出すビット位置を、符号ビットを除いて下位ビット側にシフトする読み出し位置シフトステップと、
上記各ステップを（ｎ＋１）回繰り返し動作させる繰り返し制御ステップとを含み、
前記読み出し位置シフトステップは、符号ビットを除き、ビット列格納手段中でビット列を桁上げし、
前記判定ステップは、前記演算用ビット列データとして、符号ビットと前記符号ビットを除いた上位３ビットのデータを前記ビット列格納手段から読み出す
ことを特徴とする楕円べき倍点演算装置の前処理方法。
【請求項２０】
ｎビットの定数ｐによる剰余体上の楕円曲線をＥ（Ｆｐ）、ｐ以下の正の整数をｋ、楕円曲線Ｅ（Ｆｐ）上の点をＡとした場合、べき倍点ｋＡの演算を行なう前に前処理部で前記ｋを前処理し、処理後のべき値をＡとともに演算部に加えてｋＡ演算を行なう楕円べき倍演算装置における前記前処理部で用いられる前処理プログラムを記録しているコンピュータ読み取り可能な記録媒体であって、
前記前処理プログラムは、コンピュータに、
正負を表す符号ビットと前記整数ｋとを含むビット列を格納するビット列格納手段に格納されているビット列から符号ビットを含むｎ未満の所定ビット数の演算用ビット列データを読み出す読み出し、読み出した演算用ビット列データを基にして楕円曲線上の点Ａの演算方法を指定し、読み出した演算用ビット列データを基にして変換用ビット列データを生成し、指定した演算方法で演算するよう演算部へ指示する判定ステップと、
変換用ビット列データが生成された場合に、当該変換用ビット列データにより前記ビット列格納手段内の対応するビット列を更新する更新ステップと、
ビット列格納手段から次に読み出すビット位置を、符号ビットを除いて下位ビット側にシフトする読み出し位置シフトステップと、
上記各ステップを（ｎ＋１）回繰り返し動作させる繰り返し制御ステップとを実行させ、
前記読み出し位置シフトステップは、符号ビットを除き、ビット列格納手段中でビット列を桁上げし、
前記判定ステップは、前記演算用ビット列データとして、符号ビットと前記符号ビットを除いた上位３ビットのデータを前記ビット列格納手段から読み出す
ことを特徴とする記録媒体。
【手続補正２】
【補正対象書類名】図面
【補正対象項目名】図３
【補正方法】変更
【補正の内容】
【図３】
2000330470.tif 000005