(57)【特許請求の範囲】
【請求項１】
整数ｄと非負整数ｂの集合が格納された記憶部と、
ｋが入力されて、
ｋ＝Σｉ＝０  ｎ’−１Σｊ＝０  ｍ’−１ｃｉ，ｊ  ｄｊ  φｉ
ただしｃｉ，ｊ  ∈｛−１，０，１｝、φはＺ加群Ｍ上の自己準同型写像
を満す｛ｃｉ，ｊ  ｝を求めて出力するφ進展開部と、
上記複数のｂとＰが入力され、複数のＱｂ  ＝（ｖｂ  ・Φｂ  ）（Ｐ）を演算して出力するＱｂ  演算部と、
ただしΦｂ  ＝｛φｈ  ｝ｈ＝０Ｂ＋１＝（φ０  ，φ１  ，…，φＢ＋１  ）
Ｂ＝［ｌｏｇ３  ｂ］（［ａ］はａの小数切捨を意味する）
ｖｂ  ＝｛ｖｂ，ｈ  ｝ｈ＝０Ｂ＋１＝（ｖｂ，０  ，ｖｂ，１  ，…，ｖｂ，Ｂ＋１）
ｈ＝０でｖｂ，ｈ  ＝１、ｈ≠０で［ｂ／３（ｈ−１）  ］ｍｏｄ３
ｌｏｇ３  ０＝−１，ｍｏｄ３＝２の場合−１とし、
ｖｂ  ・Φｂ  ＝Σｈ＝０Ｂ＋１ｖｂ，ｈ  φｈ  
ｗＨ  （ｖｂ  ）＝Σｈ＝０Ｂ＋１｜ｖｂ，ｈ｜
Ｒが入力され、Ｚ加群Ｍ上でＲをｄ倍して出力するｄ倍演算部と、
ｉとＱｂ  が入力され、Ｚ加群Ｍ上で、φｉＱｂ を演算して出力するφｉ  倍演算部と、
二つの値が入力され、Ｚ加群Ｍ上でこれら入力値を加減算して出力する加減算部と、
外部よりの入力Ｐ，ｋを記憶部に格納し、記憶部から所要のものを読み出して、各部へ入力し、各部の出力を記憶部に格納し、上記加減算部及び上記φｉ  倍演算部を用いて上記Ｑｂ  を演算させ、｛ｃｉ，ｊ  ｝ｉ＝０  ｍ’−１に±１が含まれている間、ｖｂ，ｈ  ≠０となる全てのｈ（０≦ｈ≦Ｂ＋１）に対し、ｃｉ，ｊ  ＝（−１）ｅ  ｖｂ，ｈ  となるｂ，ｅ，ｉを探し、ｃｉ＋ｈ，ｊ  −（−１）ｅ  ｖｂ，ｈ  によりｃｉ＋ｈ，ｊ  を更新し、φｉ  倍演算部と加減算部を用いてＲ＋（−１）ｅ  φｉ  （Ｑｂ  ）を演算させてＲを更新することをｊ＝ｎ′−１，ｎ′−２，…，０について行わせ、そのｊの更新ごとにＲをｄ倍演算部でｄ倍してＲを更新し、ｊ＝０のＲをｋＰの演算結果として出力する制御部と
を具備する循環窓加算装置。
【請求項２】
φｍ（Ｐ）＝Ｐの関係があり、
上記Ｑｂ  演算部は上記複数のｂ中でＱｂ１＝φｉ  （Ｑｂ２）となるものを予測計算する手段と、
その予測計算されたものについてはＱｂ１とＱｂ２の一方のみを演算する手段とを備えることを特徴とする請求項１記載の循環窓加算装置。
【請求項３】
上記Ｑｂ  演算部は、既に求まっているＱｂ５とＰが入力されて
Ｑｂ６＝Ｑｂ５＋（−１）ｅ  φｉ  （Ｐ）
を演算する手段を含む（ｂ６＞ｂ５）ことを特徴とする請求項１又は２記載の循環窓加算装置。
【請求項４】
上記φ進展開部は、各ｊについてｃｉ，ｊ  が同一符号のものを求める手段であり、
上記Ｑｂ  演算部はｖｂ，ｈ  が１又は０であるｖｂ  に対しＱｂ  を演算する手段であることを特徴とする請求項１乃至３の何れかに記載の循環窓加算装置。
【請求項５】
φｍ  （Ｐ）＝Ｐの関係があり、
上記Ｑｂ  演算部は、
0003604126.tif 000006
のφｉ倍したもののいずれかを演算する手段であることを特徴とする請求項１記載の循環窓加算装置。
【請求項６】
ｄ倍演算及びφ倍演算を有するＺ加群Ｍ上の元Ｐとスカラーｋ∈Ｚを入力してスカラー倍ｋＰを出力する方法において、
Ｐとｋが入力されると記憶部に記憶する過程と、
記憶部からｋを取出して、
ｋ＝Σｉ＝０  ｎ’−１Σｊ＝０  ｍ’−１ｃｉ，ｊ  ｄｊ  φｉ
ただしｃｉ，ｊ  ∈｛−１，０，１｝、Ｚ加群Ｍ上の自己準同型写像
を満す｛ｃｉ，ｊ  ｝を求めて記憶部に格納するφ進展開過程と、
複数の非負整数ｂについてそれぞれＱｂ  ＝（ｖｈ  ・Φｂ  ）（Ｐ）を演算し、かつ各ｖｂ  を記憶部に格納するＱｂ  過程と、
ただしΦｂ  ＝｛φｈ  ｝ｈ＝０Ｂ＋１＝（φ０  ，φ１  ，…，φＢ＋１  ）
Ｂ＝［ｌｏｇ３  ｂ］（［ａ］はａの小数切捨を意味する）
ｖｂ  ＝｛ｖｂ，ｈ  ｝ｈ＝０Ｂ＋１＝（ｖｂ，０  ，ｖｂ，１  ，…，ｖｂ，Ｂ＋１）
ｈ＝０でｖｂ，ｈ  ＝１、ｈ≠０で［ｂ／３（ｈ−１）  ］ｍｏｄ３
ｌｏｇ３  ０＝−１，ｍｏｄ３＝２の場合−１とし、
ｖｂ  ・Φｂ  ＝Σｈ＝０Ｂ＋１ｖｂ，ｈ  φｈ  
ｗＨ  （ｖｂ  ）＝Σｈ＝０Ｂ＋１｜ｖｂ，ｈ｜
有限体ＧＦ（ｑ）上で定義される楕円曲線Ｅ／ＧＦ（ｑ）のＧＦ（ｑｍ  ）有理点からなる群Ｅ（ＧＦ（ｑｍ  ））の単位元ＯにＲを、ｎ′−１にｊをそれぞれ初期化する過程と、
記憶部から｛ｃｉ，ｊ  ｝ｉ＝０    ｍ’−１（＝（ｃ０，ｊ  ，ｃ１，ｊ，…，ｃｍ’−１，ｊ））、ｖｂ  を取出し、｛ｃｉ，ｊ  ｝ｉ＝０    ｍ’−１に±１が含まれている間、
ｖｂ，ｈ≠０となる全てのｈ（０≦ｈ≦Ｂ＋１）に対し、
ｃｉ＋ｈ，ｊ  ＝（−１）ｅ  ｖｂ，ｈ
となるｂ，ｅ，ｉを探し、
ｂが見つかると０≦ｈ≦Ｂ＋１となる全てのｈに対しｃｉ＋ｈ，ｊ  をｃｉ＋ｈ，ｊ  −（−１）ｅ  ｖｂ，ｈ  と更新し、
記憶部からＲ，Ｑｂ  を取出し、
Ｒ＋（−１）ｅ  φｉ  （Ｑｂ  ）を演算してＲを更新して記憶部に格納することを繰返す繰返し過程と、
ｊ＝０であるか否かを調べるチェック過程と、
ｊ＝０でなければ記憶部からＲを取出してｄＲを演算してＲを更新して記憶部に格納し、かつ記憶部のｊを−１して、更新して上記繰返し処理に戻る過程と、上記チェック処理でｊ＝０と判定されると、上記記憶部からＲを取出してｋＰの演算結果として出力する過程と、
を有することを特徴とする循環窓加算方法。
【請求項７】
φｍ  （Ｐ）＝Ｐを満し、
上記Ｑｂ  過程の前に、上記複数のｂ中でＱｂ１＝φｉ  （Ｑｂ２）となるものを予測計算する過程を有し、
上記Ｑｂ  過程は上記予測されたｂ１  とｂ２  についてはＱｂ１およびＱｂ２のいずれか一方を求める過程であることを特徴とする請求項６記載の循環窓加算方法。
【請求項８】
上記Ｑｂ  過程は既に求まっているＱｂ５を用いてＱｂ６＝Ｑｂ５＋（−１）ｅ  φｉ  （Ｐ）を演算してＱｂ６を求める過程を少くとも１つ含むことを特徴とする請求項６又は７記載の循環窓加算方法。
【請求項９】
上記Ｑｂ  過程は、既に求まったＱｂ３のｂ３  を用いてｗＨ  （ｖｂ３−ｖｂ４）を演算する過程と、
ｗＨ  （ｖｂ３−ｖｂ４）が１であるか否か判定する過程と、
この判定が１であればＱｂ４＝Ｑｂ３＋（−１）ｅ  φｉ  （Ｐ）を演算してＱｂ４を求める過程とを有することを特徴とする請求項８記載の循環窓加算方法。
【請求項１０】
上記Ｑｂ  過程は、ｖｂ  のハミング重みと、ｖｂ  の要素数とを重み付け加算する過程と、
その加算結果が小さい順にｂを選んでＱｂ  を求める過程を行わせる過程とを有することを特徴とする請求項６乃至９の何れかに記載の循環窓加算方法。
【請求項１１】
上記φ進展開過程はそれぞれのｊに対して∀ｉ ［ｃｉ，ｊ  ≧０］又は∀ｉ ［ｃｉ，ｊ  ≦０］とし、
上記Ｑｂ  過程は∀ｈ ［ｖｂ，ｈ  ≧０］のものについてのみ行うことを特徴とする請求項６乃至１０の何れかに記載の循環窓加算方法。
【請求項１２】
φｍ  （Ｐ）＝Ｐを満たし、
上記φ進展開過程はそれぞれのｊに対して
∀ｉ［ｃｉ，ｊ  ≧０］又は∀ｉ［ｃｉ，ｊ  ≦０］とし、
それぞれのｊについて、０の数が半分より大であり、
上記Ｑｂ過程は、
0003604126.tif 000007
又は各場合の何れか１つあるいは複数に対しφ倍したものを求める過程であることを特徴とする請求項６記載の循環窓加算方法。
【請求項１３】
上記φ進展開過程で得られた｛ｃｉ，ｊ  ｝中の各ｊ方向における配列で１，−１からなる部分配列が同一のものが２つ以上あるものを探す過程を有し、
上記Ｑｂ  過程は上記２つ以上ある部分配列と対応するＱｂを求める過程であることを特徴とする請求項６乃至９の何れかに記載の循環窓加算方法。
【請求項１４】
上記繰返し過程中の上記ｂ，ｅ，ｉを探す過程は、ｗＨ  （ｖｂ  ）の大きい順に並べた集合を｛ｂ１  ，ｂ２  ，…，ｂｓ  ｝として、
ｒを０に初期化するｒ初期化過程と、
ｉを０に初期化するｉ初期化過程と、
ｅを０に初期化するｅ初期化過程と、
ｖｂ，ｈ  ≠０となる全てのｈ（０≦ｈ≦［ｌｏｇ３  ｂｒ  ］＋１）に対し、ｃｉ＋ｈ，ｊ  ＝（−１）ｅ  ｖｂｒ，ｈを探し、見つかればｂ＝ｂｒ  ，ｉ，ｅを出力して終了する探索過程と、
この探索過程で見つからない場合は、ｅを＋１して更新し、更新したｅが２より小さければ探索過程に戻るｅ更新過程と、
ｅ更新過程において更新したｅが２より小さくなければｉを＋１して更新し、その更新したｉがｍ′より小さければｅ初期化過程に戻る過程と、
更新したｉがｍ′より小さくなければｒを＋１して更新し、その更新したｒがｓ以下であればｉ初期化過程に戻る過程とよりなる
ことを特徴とする請求項６乃至１３の何れかに記載の循環窓加算方法。
【請求項１５】
請求項６乃至１４の何れかに記載の方法をコンピュータに実行させるためのプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、例えば情報セキュリティ技術で用いられる楕円暗号に適用され、Ｚ加群Ｍ上の元Ｐをスカラーｋ（∈Ｚ）倍する循環窓加算装置、その方法及びそのプログラム記録媒体に関する。
【０００２】
【従来の技術】
近年、インターネットなどの発達により様々な情報を公衆回線を用い、やり取りすることが増えた。公衆回線は誰でも利用できることから中継情報の盗聴・改竄（かいざん）などを容易に行なうことができる。盗聴のような悪意ある行動に対抗するためには情報セキュリティ（安全性）技術が有効である。
従来、情報セキュリティ技術の実現に冪乗剰余演算がよく用いられてきたが、近年、鍵と呼ばれる秘密に保持すべき情報を少なくできることや、高速性などから有限体上の楕円曲線のなす群を用いた方式、すなわち楕円暗号が注目されている。
【０００３】
暗号に用いる楕円曲線は定義体と呼ばれる有限体ＧＦ（ｑ）上で定義される楕円曲線Ｅ／ＧＦ（ｑ）の、ＧＦ（ｑｍ  ）有理点からなる群Ｅ（ＧＦ（ｑｍ  ））を用いることが殆んどである。
楕円暗号の殆んどは、群Ｅ（ＧＦ（ｑｍ  ））をＺ加群とみなし、このＺ加群上のスカラー倍演算、つまり楕円曲線上の点Ｐ∈Ｅ（ＧＦ（ｑｍ  ））とスカラーｋ∈Ｚに対してｋＰを求めること、を多用することにより実現している。そのため、スカラー倍演算を高速に実現する研究が数多く行なわれてきた。
【０００４】
ソフトウェアでスカラー倍を高速に実現する方法として文献「Ｎｅａｌ  Ｋｏｂｌｉｔｚ：“ＣＭ−ＣＵＲＶＥＳ  ＷＩＴＨ  ＧＯＯＤ  ＣＲＹＰＴＯＧＲＡＰＨＩＣ  ＰＲＯＰＥＲＴＩＥＳ，”Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＣＲＹＰＴＯ’９１，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ５７６，ｐｐ．２７９−２８７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，１９９２」（以下「文献Ｃ」と略す）で提案されたφ進展開法が有力である。φ進展開法は、楕円曲線Ｅ／ＧＦ（ｑ）上のＦｒｏｂｅｎｉｕｓ写像と呼ばれる自己準同型写像
φ：Ｅ（ＧＦ（ｑｍ  ））→Ｅ（ＧＦ（ｑｍ  ））
∀Ｐ，Ｑ∈Ｅ（ＧＦ（ｑｍ  ））［φ（Ｐ＋Ｑ）＝φ（Ｐ）＋φ（Ｑ）］
（なお∀ｘ  Ｆ（ｘ）はすべてのｘに対してＦ（ｘ）を意味する）
を利用する。楕円２倍算より高速な楕円φ倍算を、２倍算の代わりに使うことによりスカラー倍を高速化する。
【０００５】
文献Ｃの方法では利用できる定義体としてＧＦ（２）が用いられたが、文献「Ｖｏｌｋｅｒ  Ｍｕｅｌｌｅｒ：“Ｆａｓｔ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ｏｎ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅｓ  ｏｖｅｒ  Ｓｍａｌｌ  Ｆｉｅｌｄｓ  ｏｆ  Ｃｈａｒａｃｔｅｒｉｓｔｉｃ  Ｔｗｏ，”ｐｐ．２１９−２３４，  Ｊｏｕｒｎａｌ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｏｙ，ｎｏ．４，ｖｏｌ．１１，  Ｓｐｒｉｎｇｅｒ，１９９８」で、ｑ＝２ｅ  （ｅは小）に拡張され、さらに文献「Ｔｅｔｓｕｔａｒｏｕ  Ｋｏｂａｙａｓｈｉ，  ｅｔ  ａｌ．：“Ｆａｓｔ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ａｌｇｏｒｉｔｈｍ  Ｃｏｍｂｉｎｉｎｇ  Ｆｒｏｂｅｎｉｕｓ  Ｍａｐ  ａｎｄ  Ｔａｂｌｅ  Ｒｅｆｅｒｅｎｃｅ  ｔｏ  Ａｄａｐｔ  ｔｏ  Ｈｉｇｈｅｒ  Ｃｈａｒａｃｔｅｒｉｓｔｉｃ，”Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＥＵＲＯＣＲＹＰＴ  ’９９，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  １５９２，ｐｐ．１７６−１８９，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，１９９９」（以下「文献Ｅ」と略す）で、ｑが一般の場合に拡張された。
【０００６】
上記φ進展開法の概要は以下の通りである。
Ｓｔｅｐ１：ｋをφ進展開する。つまり、
ｋ＝Σｉ＝０ｍ’−１Σｊ＝０ｎ’−１ｃｉ，ｊ  ２ｊ  φｉ  （ｃｉ，ｊ  ∈｛−１，０，１｝）    （１）
を満たす｛ｃｉ，ｊ  ｝を求める。
Ｓｔｅｐ２：式（１）を利用し
0003604126.tif 000002
を求める。
【０００７】
式（１）は、「ｋ倍演算」という意味でのＥ（ＧＦ（ｑｍ  ））上の自己準同型写像としての等号である。また、ｍ′≧２、ｎ′≧１である。この発明ではφ進展開しか扱わないので、φ進展開となっていないｍ′＝１の場合は扱わない。
Ｓｔｅｐ２の具体的な計算については、｛ｃｉ，ｊ  ｝の構造により様々な最適化手法がある。文献Ｅの方法は次の通りである。式（２）は有限和であることからΣの順序を換えても結果は変わらない。従って、
ｋＰ＝Σｊ＝０ｎ’−１２ｊ  Σｉ＝０ｍ’−１ｃｉ，ｊ  φｉ  （Ｐ）
となる。この式から、以下の処理が導かれる。
【０００８】
Ｓｔｅｐ１：Ｒ←Ο，ｊ←ｎ′−１に初期化。
Ｓｔｅｐ２：ｉ＝０，１，…，ｍ′−１に対して、
Ｒ←Ｒ＋φｉ  （Ｐ）ｃｉ，ｊ  ＝１の場合
Ｒ←Ｒ−φｉ  （Ｐ）ｃｉ，ｊ  ＝−１の場合
何もしない        ｃｉ，ｊ  ＝０の場合
とする。
【０００９】
Ｓｔｅｐ３：ｊ＝０ならＲ（＝ｋＰ）を出力して終了。ｊ＞０なら
Ｒ←２Ｒ，        ｊ←ｊ−１
とし、Ｓｔｅｐ２に戻る。
ここでΟはＥ（ＧＦ（ｑｍ  ））の単位元を表す。
この文献Ｅの方法は、式（１）で、一様にランダムなｋに対しｃｉ，ｊ  ≠０となるｃｉ，ｊ  を平均的には全体の約１／３にできることがわかっているのでこの場合の平均計算量は以下の通りである。
【００１０】
楕円加減算  ｍ′ｎ′／３回
楕円２倍算  ｎ′−１回
なお、φｉ  倍は高速に計算可能であるから上記計算量に含めていない。
【００１１】
【発明が解決しようとする課題】
文献Ｅの方法のＳｔｅｐ２では、異なるｊに対して、全く同じ加算、例えば、
Ｒ←Ｒ＋（φ１  （Ｐ）＋φ２  （Ｐ））
を複数回行なうことがある。冗長な同じ加算を行なわないようにするためには、上記例の場合一旦φ１  （Ｐ）＋φ２  （Ｐ）を計算し記録しておき、φ１  （Ｐ）＋φ２  （Ｐ）が必要になったときにこの記録された値を読みだしてＲに加算することにより冗長な加算を行なわないようにすることができる。
【００１２】
一般的に冗長な加算を行なわないためにはＳｔｅｐ２より前に、あり得る全ての
【００１３】
【数１】
0003604126.tif 000003
【００１４】
を計算しておくことが考えられるが、この計算自体に時間がかかってしまい、結果として全体の計算が遅くなってしまう。
この発明の目的は、φ進展開法を用いてＰをｋ倍演算する際に冗長な加算を効率的に減らすことができる循環窓加算装置、その方法及びそのプログラム記録媒体を提供することにある。
【００１５】
【課題を解決するための手段】
【００１６】
【数２】
0003604126.tif 000004
【００１７】
【発明の実施の形態】
以下ではこの発明の実施例を示す。
第１の実施例［一般］
図１にこの発明による循環窓加算装置であるスカラー倍装置１０の実施例を示す。この装置１０は、φ倍及びｄ倍演算を有するＺ加群Ｍ上の元Ｐとスカラーｋ∈Ｚを入力し、スカラー倍ｋＰを出力する。二つの値例えばＰとＱが入力されてＰ＋Ｑ又はＰ−Ｑを出力する加減算部１１、Ｐが入力されてそのｄ倍値ｄＰを出力するｄ倍演算部１２、ｉとＰが入力されてφｉ（Ｐ）を出力するφｉ倍演算部１３、記憶部１４、ｋが入力されて｛ｃｉ，ｊ  ｝を出力するφ進展開部１５が制御部１６に接続され、制御部１６はこの装置１０に入力されたｋ，Ｐを記憶部１４に格納し、記憶部１４から所要のデータを取出して、各部へ入力させて、所望の処理を行わせ、その結果（出力）を記憶部に格納して、各部を制御してｋＰ値を得て出力する。
【００１８】
図１中の各部はＭに合わせて設定されているものとする。このスカラー倍装置１０を機能的に表わすと図２に示すようになる。つまりｄ倍演算部１２、記憶部１４、φ進展開部１５、制御部１６を同様に備えるが、Ｑｂ演算部２１、探索部２２、ｃｉ，ｊ更新部２３、Ｒ更新部２４が設けられる。
この発明では、ＱｂをＱｂ演算部２１で演算し、このＱｂを利用して、演算を簡単にしている。従って、まずＱｂはどのようなものであるかを以下に示す。
【００１９】
Ｌｏｇ３０＝−１とし、以下のベクトルを定義する。
Φｂ  ＝｛φｈ  ｝ｈ＝０Ｂ＋１＝（φ０  ，φ１  ，…，φＢ＋１  ）
ｖｂ  ＝｛ｖｂ，ｈ  ｝ｈ＝０Ｂ＋１＝（ｖｂ，０  ，ｖｂ，１  ，…，ｖｂ，Ｂ＋１  ）
但し、Ｂ＝［ｌｏｇ３  ｂ］、つまりＢはｌｏｇ３  ｂの小数以下を切捨てたものである。
ｈ＝０の場合    ｖｂ，ｈ  ＝１
ｈ≠０の場合    ｖｂ，ｈ  ＝［ｂ／（３ｈ−１  ）］ｍｏｄ３
とする。ここで剰余ｍｏｄは０，１，−１を取るものとする。つまり２の代りに−１とおいた。
【００２０】
また、ｖｂとΦｂ  の形式的内積ｖｂ・Φｂ  を以下の通り定義する。
ｖｂ・Φｂ  ＝Σｈ＝０Ｂ＋１ｖｂ，ｈ  φｈ  
さらに、
Ｑｂ  ＝（ｖｂ・Φｂ  ）（Ｐ）
ｗＨ  （ｖｂ  ）＝Σｈ＝０Ｂ＋１｜ｖｂ，ｈ  ｜
とおく。
【００２１】
図１及び図２に示したスカラー倍装置は、以下の通り動作する。また、この動作の流れを図３に示す。
Ｓｔｅｐ１：Ｚ加群Ｍ上の元Ｐとスカラーｋが入力されると記憶部１４に格納する。
Ｓｔｅｐ２：φ進展開部１５はｋを入力し
ｋ＝Σｉ＝０ｍ’−１Σｊ＝０ｎ’−１ｃｉ，ｊ  ｄｊ  φｉ  （ｃｉ，ｊ  ∈｛−１，０，１｝）
を満たす｛ｃｉ，ｊ  ｝を求めて出力し、｛ｃｉ，ｊ  ｝は記憶部１４に格納される。
【００２２】
Ｓｔｅｐ３：いくつかのｂに対して、加減算部１１、φｉ  倍演算部１３を用いてＱｂ  演算部２１でそれぞれのＱｂ  を計算し、これらＱｂ  とその計算に用いたｖｂ  を記憶部１４に記憶する。但し、Ｑ０  は必ず準備する。このＱ０  はＱｂ  の定義からＰに等しい。
Ｓｔｅｐ４：Ｒ←Ο，ｊ←ｎ′−１に初期化し、記憶部１４に記憶する。
Ｓｔｅｐ５：｛ｃｉ，ｊ  ｝ｉ＝０ｍ’−１（＝（ｃ０，ｊ  ，ｃ１，ｊ，…，ｃｍ’−１，ｊ））に±１が含まれている間、以下を繰り返す。
【００２３】
Ｓｔｅｐ５−１：まず｛ｃｉ，ｊ  ｝ｉ＝０ｍ’−１に±１が含まれているかを調べ、含まれていればＳｔｅｐ５−２に移り、含まれていなければＳｔｅｐ６に移る。
Ｓｔｅｐ５−２：記憶部１４に記憶されているＱｂ  に対しｗＨ  （ｖｂ  ）の大きな順に、各ｖｂ  についてｖｂ，ｈ  ≠０の全てのｈ（０≦ｈ≦Ｂ＋１）に対して、
ｃｉ＋ｈ，ｊ＝（−１）ｅ  ｖｂ，ｈ
となるｂ，ｅ，ｉを探す。ｅは０又は１である。
【００２４】
つまり、まずｊ＝ｎ′−１であるから、係数ｃｉ，ｊは図４に示すように、ｍ′×ｎ′個あり、そのｊ＝ｎ′−１のベクトル｛ｃｉ，ｎ’−１  ｝ｉ＝０  ｍ’−１＝（ｃ０，  ｎ’−１，ｃ１，ｎ’−１  ，ｃ２，ｎ’−１  ，…，ｃｍ’−１，  ｎ’−１  ）を記憶部１４から取出し、また、ｗＨ（ｖｂ）の大きい順、つまり１と−１の数が多い順にｖｂを取出し、ｖｂ，０，ｖｂ，１，ｖｂ，２，…，ｖｂ，Ｂ−１その１又は−１、つまり０以外のもの（ｅ＝０）又はその符号を反転したもの（ｅ＝１）についてその配列位置を保持した状態で、｛ｃｉ，ｎ’−１  ｝ｉ＝０    ｍ’−１の配列中に同一のものが存在するかを、ｉ＝０から始まる配列から、順次ｉを＋１した配列と比較して探し、存在すればその時のｉの値と、ｅの値と、ｖｂのｂを出力する。例えばｃｉ，ｎ’−１  が図５Ａに示す列であり、ｖｂが図５Ｂに示すようにｖ１２＝（１，０，０，−１）である場合に、このｖ１２の始めをｃｉ，ｎ’−１  のｉ＝０に合せて（図５Ｂ）、ｖｂ，ｈ≠０が全て一致しているかを調べ、一致していないので図５Ｃに示すようにｃｉ，ｎ’−１  のｉ＝１にｖｂの始めを合せて比較し、一致していないので図５Ｄに示すようにｃｉ，ｎ’−１  のｉ＝２にｖｂの始めを合わせてる。この時ｖｂ中のｖｂ，０＝１とｖｂ，３＝−１とが｛ｃｉ，ｎ’−１  ｝中のｃ２，ｎ’−１  ＝１、ｃ５，ｎ’−１  ＝−１とそれぞれ一致する。これによりそのｂとｅ＝０とｉ＝２で一致が見い出されたことになる。
【００２５】
このように一致するか否かをｉの値を順次ずらして行う。一致するものが存在しなければ、Ｓｔｅｐ５−２に戻り、次にｗＨ（ｖｂ）の大きいｖｂについて同様に、一致するものを探す。このｂ，ｅ，ｉの探索は図２中の探索部２２で行う。なおｖｂの取出しは、ｗＨ（ｖｂ）の大きい順から行わなくてもよいが、ｗＨ（ｖｂ）の大きな順から行った方が効率がよいことが多い。
Ｓｔｅｐ５−３：Ｓｔｅｐ５−２でｂ，ｅ，ｉが見つかった場合、
・ｃｉ＋ｈ，ｊ←ｃｉ＋ｈ，ｊ−（−１）ｅ  ｖｂ，ｈ          ０≦ｈ≦［ｌｏｇ３  ｂ］＋１となる全てのｈ
例えば、図５Ｂに示すようなｖｂ＝（１，０，０，−１）について、図５Ａに示すようなあるｊに対する｛ｃｉ，ｊ  ｝ｉ＝０  ｍ’−１のｉ＝２、ｅ＝０でｖｂのｖｂ，ｈ≠０の要素が一致した場合に、その｛ｃｉ，ｊ  ｝ｉ＝０  ｍ’−１から一致した部分のｖｂ，ｈ≠０を引いて０として図５Ｅに示すように｛ｃｉ，ｊ  ｝ｉ＝０  ｍ−１を更新する。この更新は図２中のｃｉ，ｊ更新部２３で行う。
・Ｒ←Ｒ＋（−１）ｅ  φｉ  （Ｑｂ  ）
をφｉ  倍演算部１３、加減算部１１を用いて、つまり図２中のＲ更新部２４で計算して記憶部１４中のＲを更新する。図５に示した例ではｉ＝２でｖｂ  と一致が得られたのであるからＱｂ  にφ２をほどこしたものを記憶部１４中のＲに加算すればよい。Ｓｔｅｐ５−３が終了すると、Ｓｔｅｐ５−１に戻り同様のことを行う。取出したｊ＝ｎ′−１の係数列｛ｃｉ，ｊ  ｝ｉ＝０ｍ’−１に±１がなくなれば、その列に対するΣｉ＝０ｍ’−１ｃｉ，ｊ  φｉ  （Ｐ）の計算がなされたことになる。
【００２６】
Ｓｔｅｐ６−１：ｊ＝０であるかを調べ、
Ｓｔｅｐ６−２：ｊ＝０ならＲ（＝ｋＰ）を出力して終了。
Ｓｔｅｐ６−３：ｊ＞０ならｄ倍演算部１２を用いてＲをｄ倍してＲ←ｄＲと更新し、またｊも−１して、つまりｊ←ｊ−１と更新してＳｔｅｐ５に戻る。即ちｊ＝ｎ′−２について、Ｓｔｅｐ５の処理を行い、これが終了した時は（Σｉ＝０ｍ’−１ｃｉ，    ｎ’−１  ｄｎ’−１φｉ  （Ｐ））＋（Σｉ＝０ｍ’−１ｃｉ，ｎ’−２ｄｎ’−２φｉ（Ｐ））が求まり、以下同様のことを繰り返してｋＰ＝Σｊ＝０ｎ’−１  Σｉ＝０ｍ’−１ｃｉ，ｊｄｉφｉ（Ｐ）が求まる。
【００２７】
以上のようにして予め求めたＱｂ  を何回も利用すればする程、文献Ｅの方法よりも計算量が少なくて済む。
上記Ｓｔｅｐ５−２について、ｂ，ｅ，ｉはこのＳｔｅｐに書いてある条件の範囲内でどのように探してもよいが、より具体的には例えば以下のように探すこともできる（図６参照）。
記憶部１４に記憶されているＱｂ  のｖｂ  について、ｗＨ  （ｖｂ  ）の大きな順に並べた集合を｛ｂ１  ，ｂ２  ，…，ｂｓ  ｝とする。
【００２８】
Ｓ−１．ｒ←０に初期化する。
Ｓ−２．ｉ←０に初期化する。
Ｓ−３．ｅ←０に初期化する。
Ｓ−４．ｖｂｒ，ｈ≠０となる全てのｈ（０≦ｈ≦［ｌｏｇ３  ｂｒ  ］＋１）に対し、ｃｉ＋ｈ，ｊ  
＝（−１）ｅ  ｖｂｒ，ｈとなればその時のｂ＝ｂｒ  ，ｉ，ｅを出力して終了。
【００２９】
Ｓ−５．Ｓ−４で一致が得られなければｅ←ｅ＋１とし、ｅ＜２であれば、Ｓ−４に戻る。
Ｓ−６．Ｓ−５でｅ＜２でなければｉ←ｉ＋１とし、ｉ＜ｍ′であれば、Ｓ−３に戻る。
Ｓ−７．Ｓ−６でｉ＜ｍ′でなければｒ←ｒ＋１とし、ｒ≦ｓであれば、Ｓ−２に戻る。
第２の実施例［ｗｉｎｄｏｗ  ｓｉｚｅ小］
第１の実施例のＳｔｅｐ３のいくつかのｂとして、小さい順に選ぶ。
【００３０】
この実施例は、ｍ′が有限であり、かつ非ゼロのｃｉ，ｊ  が少ない場合に、ｂが大きいものはＳｔｅｐ５−２でマッチする確率が低いので、ｂとして小さい順、例えば１，２，３，…に選ぶことが有効である。
さらに、それぞれのｂに対するＱｂ  を計算する際に、既に計算したＱｂ’に対し
∃ｂ’＜ｂ［ｗＨ  （ｖｂ’−ｖｂ  ）＝１］
であるので、つまりｖｂ’とｖｂ  との差のハミング重みが１となるものが必ず存在するので、Ｑｂ’に（−１）ｅφｉ（Ｐ）を加算することによりＱｂ  を計算できる。よってＱｂの計算量を削減できる。
【００３１】
このＱｂの計算手順は例えば図７に示すように、まずｂを小さい順に並べ（Ｓ１）、次にその並べた順に小さい方から１つｂを選択し（Ｓ２）、その選択したｂのｖｂと、既に計算したＱｂ’のｖｂ’とのベクトル差のハミング重みが１となるかを確め（Ｓ３）、前記ハミング重みが１となれば、そのｖｂ’について既に計算したＱｂ’に（−１）ｅφｉ（Ｐ）を加算してＱｂを求める（Ｓ４）。Ｑｂの計算後、全てのｂを選択したかを調べ、また選択していないｂがあればステップＳ２に戻り、全て選択し、全てのＱｂを求めたならば終了する（Ｓ５）。
【００３２】
なお一般にＱｂを求める際に、既に求まっているＱｂ’に対し（−１）ｅφｉ（Ｐ）を加算することにより計算量を削減できる。例えば図７中のステップＳ３で∃Ｑｂ’，ｅ，ｉ［Ｑｂ＝Ｑｂ’＋（−１）ｅφｉ（Ｐ）］（ｂ′＜ｂ）となるＱｂ’があるかを調べ、Ｑｂ’があればＱｂ＝Ｑｂ’＋（−１）ｅφｉ（Ｐ）によりＱｂ  を求める。例えばＱ１  ＝Ｐ＋φＰであり、Ｑ７ ＝Ｐ＋φＰ−φ２  Ｐであるが、Ｑ７  の計算をＱ７ ＝Ｑ１＋（−１）１φ２  Ｐの計算により求める。
第３の実施例［ｗＨ（ｂ）  ＋  ｗｉｎｄｏｗ  ｓｉｚｅ小］
第１の実施例のＳｔｅｐ３のいくつかのｂとして、ｗＨ（ｖｂ）＋ｌｏｇ２（ｂ）の小さい順に選ぶ。この場合ｌｏｇの値として２に限らず、３、５などでもよく、要はｖｂのハミング重みと、ｖｂの要素数とを重み付けて加算し、その小さい順にｂを選べばよい。つまりｖｂの要素数［ｌｏｇ３  ｂ］＋１が大でもその要素ｖｂ，ｈ中に０のものを多く含む場合はＱｂを求めておき、これを利用してもｋＰの計算の量の削減に大きく寄与しない。その点でｗＨ（ｖｂ）が大きくかつｌｏｇ２（ｂ）が小さい方がよい。この場合はｗＨ（ｖｂ）＋ｌｏｇ２（ｂ）の小さい順に並べ図７に示したと同様の手順でＱｂを求めることができる。
第４の実施例［φｍ＝１（楕円曲線）］
計算対象のＺ加群ＭとＰ（∈Ｍ）によっては、φｍ（Ｐ）＝Ｐを満たす場合がある。この場合は、ｍ′＝ｍととることができる。一般にはｂ≠ｂ′に対して、
∀ｉ≠０［Ｑｂ≠φｉ（Ｑｂ’）］
である。つまり全てのｉ≠０に対し、Ｑｂ＝φｉ（Ｑｂ’）となるものはない。しかしφｍ（Ｐ）＝Ｐのときは、
∃ｉ≠０［Ｑｂ＝φｉ（Ｑｂ’）］
となることがある。即ちＱｂ＝φｉ（Ｑｂ’）となるｉが存在する。
【００３３】
従って、第１の実施例のＳｔｅｐ３で、Ｑｂを求める際に、
Ｑｂ＝φｉ（Ｑｂ’）
なる、ＱｂおよびＱｂ’については、そのいずれか一方を計算すれば十分であるので、片方だけ計算する。但し、Ｓｔｅｐ５で用いられるｃｉ，ｊの最初の添字ｉはｍｏｄ  ｍ′で考える。
所でＱｂ，Ｑｂ’の一方の計算で済ませるためには、各ｖｂについて次のような計算をする。ｖｂ＝（ｖ０，ｖ１，…，ｖＢ＋１）に対し、φ（ｖｂ）は（ｖＢ＋１，ｖ０，ｖ１，…，ｖＢ）＝ｖｂ’となる。従ってｖｂ’＝φｉ（ｖｂ）なる関係があるｖｂとｖｂ’を予め調べ、この関係があるものについてはＱｂ又はＱｂ’を計算すればよい。このような関係ｖｂ’＝φｉ（ｖｂ）＝φｉ’（ｖｂ’’）になるように、２つ以上のｖｂ  が、φｉ倍の関係にある場合があり、これらの関係のある複数のｖｂ中の１つのｂについてＱｂ  を求めればよい。なおＱｂを計算と比較して、前記ｖｂ’＝φｉ（ｖｂ）の関係があるか否かを調べる計算は頗る簡単で、高速に行うことができる。
第５の実施例［ｎｏｎ−ｓｉｇｎｅｄ（楕円曲線）］
第１の実施例ではｃｉ，ｊの符号に制限を設けなかったが、Ｚ加群によっては、Ｓｔｅｐ２で、それぞれのｊに対し、
∀ｉ［ｃｉ，ｊ  ≧０］
つまり１つのｊについてみるとｃｉ，ｊは１又は０，または
∀ｉ［ｃｉ，ｊ  ≦０］
つまりそのｉについてはｃｉ，ｊは−１又は０と取れることが全てのｊについて云える。即ち各ｊについてみるとｃｉ，ｊは同一符号に取れる。この場合は、Ｓｔｅｐ３のＱｂ（＝ｖｂ・Φｂ）として
∀ｈ［ｖｂ，ｈ≧０］
つまりｖｂ，ｈが１又は０からのみなるものを選べば十分である。
【００３４】
即ちｖｂ，ｈ＝−１を含むｖｂは用いない。
このようにすることによりｃｉ，ｊが−１，０，１の何れをも取れる場合と比較して計算量を著しく少くすることができる。
第６の実施例［ｍが小］
第４及び第５の実施例が共に適用できるような場合、つまりφｍ（Ｐ）＝Ｐ、かつそれぞれのｊについてみるとｃｉ，ｊは同一符号である場合で、更に
ｗＨ（｛ｃｉ，ｊ  ｝ｉ＝０ ｍ−１）＝ｗＨ（（ｃ０，ｊ，ｃ１，ｊ，…，ｃｍ−１，ｊ））≦ｍ／２
と｛ｃｉ，ｊ  ｝が取れて、つまり各ｊに対し｛ｃｉ，ｊ  ｝中の０の数が半分より多く、かつｍが、例えば３２以下、ｄ＝１の場合はｍが２５６以下のように小さい場合は、第１の実施例のＳｔｅｐ３で、以下のようにあり得る全てのＱｂを計算しておくと有利である。例えば、楕円曲線上の多くの点Ｐでは、
（１＋φ＋…＋φｍ−１  ）（Ｐ）＝０
を満たすので、ｗＨ（｛ｃｉ，ｊ  ｝ｉ＝０ ｍ−１）＝ｗＨ（（ｃ０，ｊ，ｃ１，ｊ，…，ｃｍ−１，ｊ））≦ｍ／２とでき、この発明の有効性が増す。
【００３５】
ｍ＝２，３の場合
Ｑ０＝Ｐ
ｍ＝４，５の場合
Ｑ０  ＝Ｐ
Ｑ１  ＝（１＋φ）（Ｐ）
Ｑ３  ＝（１＋φ２  ）（Ｐ）
ｍ＝６，７の場合
Ｑ０  ＝Ｐ
Ｑ１  ＝（１＋φ）Ｐ
Ｑ３  ＝（１＋φ２  ）（Ｐ）
Ｑ４  ＝（１＋φ＋φ２  ）（Ｐ）
Ｑ９  ＝（１＋φ３  ）（Ｐ）
Ｑ１０＝（１＋φ＋φ３  ）（Ｐ）
Ｑ２８＝（１＋φ＋φ４  ）（Ｐ）
Ｑ３０＝（１＋φ２  ＋φ４  ）（Ｐ）
以上の各Ｑの１つ乃至複数をφ倍したものでもよい。
第７の実施例［適応的］
第１の実施例のＳｔｅｐ３で、どのｂに対応するＱｂを計算するかについて、Ｓｔｅｐ２によって定められたｃｉ，ｊを調べＳｔｅｐ５で２回以上利用されるＱｂについて計算する。
第８の実施例［Ｐ固定］
第１の実施例で、予め入力されるＰが既知の場合、Ｓｔｅｐ３を実行せず、予め記憶装置が許す限りのＱｂ  について事前に計算しておく。
【００３６】
以上の実施例は部分体ＧＦ（ｑ）上定義される楕円曲線のＧＦ（ｑｍ  ）有理点のなす群Ｅ（ＧＦ（ｑｍ  ））／ＧＦ（ｑ）について、ｍ′＝ｍ，ｎ′＝［ｌｏｇ２  ｑ］＋１，ｄ＝２とでき、非常に効果を発揮する。この［ｌｏｇ２  ｑ］はｌｏｇ２  ｑの小数を切上げた整数である。
上述したこの発明のスカラー倍装置はコンピュータにより機能させることもできる。その場合は例えば図８に示すように、Ｐ，ｋなどが入力され、ｋＰが出力される入出力部３１、楕円パラメータｍ，ｑ，ｄとｂの集合などが記憶された記憶部３２、φ進展開展プログラムが格納されたメモリ３３、Ｑｂを演算するプログラムが格納されたメモリ３４、φｉ倍演算を行うプログラムが格納されたメモリ３５、ｄ倍演算を行うプログラムが格納されたメモリ３６、加減算を行うプログラムが格納されたメモリ３７、これらプログラムを用いてｋＰ演算を行うプログラムが格納されたメモリ３８、プロセッサ３９がバス４１に接続され、プロセッサ３９により、これらのプログラムを実行してスカラー倍演算を行う。なおこの発明は楕円曲線上の演算に限らず、一般にＺ加群Ｍ上の元Ｐをスカラーｋ（∈Ｚ）倍する方法に適用できる。
【００３７】
【発明の効果】
この発明により、楕円曲線Ｅ（ＧＦ（ｐｍ  ））／ＧＦ（ｐ）上の点のスカラー倍の計算は、例えば第６の実施例のｍ＝７，ｐ＝２２９−３の場合、文献Ｅの方法に比べて下記に示すように、楕円加減算を約半分に削減できる。
0003604126.tif 000005
例えば、楕円加減算と楕円２倍算の速度が等しい場合には、全体として約１．７倍の高速化が計られたことになる。
【００３８】
なお、この様な楕円曲線は実際に楕円曲線暗号として使われている。
【図面の簡単な説明】
【図１】この発明装置の実施例を示すブロック図。
【図２】この発明装置を機能的に示すブロック図。
【図３】この発明装置の動作手順の例を示す流れ図。
【図４】φ進展開係数の例を示す図。
【図５】係数ｃｉ，ｊの更新を説明するための図。
【図６】ｖｂ中のｖｂ，ｈ≠０の全てがｃｉ，ｊの列の一部と一致している部分を探す手順の例を示す流れ図。
【図７】第２の実施例を説明するための流れ図。
【図８】この発明装置をコンピュータにより構成する場合の例を示す図。
【図１】
0003604126.tif 000008
【図２】
0003604126.tif 000009
【図３】
0003604126.tif 000010
【図４】
0003604126.tif 000011
【図５】
0003604126.tif 000012
【図６】
0003604126.tif 000013
【図７】
0003604126.tif 000014
【図８】
0003604126.tif 000015