(57)【特許請求の範囲】
【請求項１】
非機密通信チャネルを介して情報を交換する２つのエンティティによって採用される暗号化方法であって、各エンティティが、機械によって読取り可能であり該方法を機能させるための実行可能なプログラムを包含するメモリを具備し、該方法が、交換されるべき情報アイテムから導出される整数を所定の非超単一楕円曲線の奇数次点に乗算する段階を含む、暗号化方法において、
上記段階が上記楕円曲線の点を加算および二等分する段階からなり、点の加算は当業界で公知の演算であり、且つ、奇数次点 P の上記二等分は、
[2]D ＝ P
で、
【数１】
0004704640.tif 000091
が二等分演算を表現し、且つ
【数２】
0004704640.tif 000092
が点 D を表現する、一意的奇数次点 D として定義されることを特徴とする暗号化方法。
【請求項２】
【数３】
0004704640.tif 000093
は2n個の要素の有限体であり、
【数４】
0004704640.tif 000094
は
【数５】
0004704640.tif 000095
により定義された楕円曲線Eの部分集合であり、且つ、E[2k]はkが1以上の整数であるときにPをP自体に対して2k回加算すると単位元
【数６】
0004704640.tif 000096
が与えられる如き上記楕円曲線の各点Pの集合である請求項１記載の方法において、
上記楕円曲線の点P＝(x,y)は、前記二等分により、下記の各演算を行って求められる上記楕円曲線の点
【数７】
0004704640.tif 000097
を与えることを特徴とする方法：
・λO2＋λO＝α＋xである如き第1値λOを探す；
・uO2＝x(λO＋1)＋yである如き第2値uO2を計算する；
・もしkが値1を有すれば、式：λ2＋λ＝α2＋u2OがF2n内に解を有するか否かをチェックする；
・もしそうであれば、上記二等分を次の如く計算する：
【数８】
0004704640.tif 000098
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する；
・もしkが1より大きければ、次の反復的計算を行う：
u2k-1が求まるまでi＝1からiをインクリメントすることにより、
λi2＋λi＝α＋ui-1である如き値λiを探し、
次に、u2i＝ui-1(λi＋λi-1＋ui-1＋1)である如き値u2iを計算する；
・上記式λ2＋λ＝α2＋u2k-1がF2nに解を有するか否かをチェックする；
・もしそうであれば、次の如く上記二等分を計算する：
【数９】
0004704640.tif 000099
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する。
【請求項３】
F2nは2n個の要素の有限体であり、E(F2n)は
【数１０】
0004704640.tif 000100
により定義された楕円曲線Eの部分集合であり、且つ、E[2k]はkが1以上の整数であるときにPをP自体に対して2k回加算すると単位元
【数１１】
0004704640.tif 000101
が与えられる如き上記楕円曲線の各点Pの集合である請求項１記載の方法において、
上記楕円曲線の点P＝(x,y)は、前記二等分により、λO＝uO＋vO/uOとして下記の各演算を行って求められる上記楕円曲線の点
【数１２】
0004704640.tif 000102
を与えることを特徴とする方法：
・λO2＋λO＝α＋xである如き第1値λOを探す；
・uO2＝x(λO＋1)＋yである如き第2値uO2を計算する；
・もしkが値1を有すれば、式：λ2＋λ＝α2＋uO2が
【数１３】
0004704640.tif 000103
内に解を有するか否かをチェックする；
・もしそうであれば、上記二等分を次の如く計算する：
【数１４】
0004704640.tif 000104
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する；
・もしkが1より大きければ、次の反復的計算を行う：
u2k-1が求まるまでi＝1からiをインクリメントすることにより、
λi2＋λi＝α＋ui-1である如き値λiを探し、
次に、ui2＝ui-1(λi＋λi-1＋ui-1＋1)である如き値ui2を計算する；
・上記式λ2＋λ＝α2＋u2k-1が
【数１５】
0004704640.tif 000105
に解を有するか否かをチェックする；
・もしそうであれば、次の如く上記二等分を計算する：
【数１６】
0004704640.tif 000106
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する。
【請求項４】
F2nは2n個の要素の有限体であり、E(F2n)は
【数１７】
0004704640.tif 000107
により定義された楕円曲線Eの部分集合であり、且つ、E[2k]はkが1以上の整数であるときにPをP自体に対して2k回加算すると単位元
【数１８】
0004704640.tif 000108
が与えられる如き上記楕円曲線の各点Pの集合である請求項１記載の方法において、
λP＝x＋y/xとして(x,λP)により表される上記楕円曲線の点P＝(x,y)は、前記二等分により、下記の各演算を行って求められる上記楕円曲線の点
【数１９】
0004704640.tif 000109
を与えることを特徴とする方法：
・λO2＋λO＝α＋xである如き第1値λOを探す；
・uO2＝x(λO＋λP＋x＋1)である如き第2値uO2を計算する；
・もしkが値1を有すれば、式：λ2＋λ＝α2＋uO2がF2n内に解を有するか否かをチェックする；
・もしそうであれば、上記二等分を次の如く計算する：
【数２０】
0004704640.tif 000110
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する；
・もしkが1より大きければ、次の反復的計算を行う：
u2k-1が求まるまでi＝1からiをインクリメントすることにより、
λi2＋λi＝α＋ui-1である如き値λiを探し、
次に、ui2＝ui-1(λi＋λi-1＋ui-1＋1)である如き値ui2を計算する；
・上記式λ2＋λ＝α2＋u2k-1がF2nに解を有するか否かをチェックする；
・もしそうであれば、次の如く上記二等分を計算する：
【数２１】
0004704640.tif 000111
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する。
【請求項５】
F2nは2n個の要素の有限体であり、E(F2n)は
【数２２】
0004704640.tif 000112
により定義された楕円曲線Eの部分集合であり、且つ、E[2k]はkが1以上の整数であるときにPをP自体に対して2k回加算すると単位元
【数２３】
0004704640.tif 000113
が与えられる如き上記楕円曲線の各点Pの集合である請求項１記載の方法において、
λP＝x＋y/xとして(x,λP)により表される上記楕円曲線の点P＝(x,y)は、前記二等分により、下記の各演算を行って求められてλO＝uO＋vO/uOとして(uO,λO)により表される上記楕円曲線の点
【数２４】
0004704640.tif 000114
を与えることを特徴とする方法：
・λO2＋λO＝α＋xである如き第1値λOを探す；
・uO2＝x(λO＋λP＋x＋1)である如き第2値uO2を計算する；
・もしkが値1を有すれば、式：λ2＋λ＝α2＋uO2がF2n内に解を有するか否かをチェックする；
・もしそうであれば、上記二等分を次の如く計算する：
【数２５】
0004704640.tif 000115
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する；
・もしkが1より大きければ、次の反復的計算を行う：
u2k-1が求まるまでi＝1からiをインクリメントすることにより、
λi2＋λi＝α＋ui-1である如き値λiを探し、
次に、ui2＝ui-1(λi＋λi-1＋ui-1＋1)である如き値ui2を計算する；
・上記式λ2＋λ＝α2＋u2k-1が
【数２６】
0004704640.tif 000116
に解を有するか否かをチェックする；
・もしそうであれば、次の如く上記二等分を計算する：
【数２７】
0004704640.tif 000117
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する。
【請求項６】
当該方法は、
前記２つのエンティティ内で夫々実現される２個の秘密鍵と、
該所定の非超単一楕円曲線 E の奇数次の前記点 P から成り、これらの両エンティティで実現される公開鍵と、
から共通鍵を構築するプロトコルであり、各エンティティは前記乗算段階を実行し、各エンティティによって該段階で使用される該整数は当該夫々の秘密鍵であり、該共通鍵は各エンティティにおける該段階から生じる点から導出されることを特徴とする、請求項１から請求項５までのいずれか一項に記載の方法。
【請求項７】
第１および第２エンティティの該夫々の秘密鍵は、 a および b と夫々表記され、且つ、
−上記第１エンティティは、該奇数点 P に該整数 a を乗じる乗算からなる、[a]P と表記されるスカラ乗算を計算し、該スカラ乗算の結果を第１結果点として、該第１結果点の識別情報を上記第２エンティティへ送信し、
−上記第２エンティティは、該奇数点 P に該整数 b を乗じる乗算からなる、[b]P と表記されるスカラ乗算を計算し、該スカラ乗算の結果を第２結果点として、該第２結果点の識別情報を上記第１エンティティへ送信し、
−該２つのエンティティは、上記楕円曲線 (E) の共通点 (C)=(x,y) を夫々計算すべく、該第２結果点 [b]P に該整数 a を乗じる乗算および該第１結果点 [a]P に該整数 b を乗じる乗算から夫々なる、 [a]([b]P) および [b]([a]P) と表記されるスカラ乗算であって、これらのスカラ乗算の結果点が両方ともに等しく [a.b]P と表記されて該共通点を決定するスカラ乗算を行い、
−該２つのエンティティは、それらの共通鍵として、上記スカラ乗算 [a.b]P により求められた上記共通点 (C) の座標 (x) を選択するが、該スカラ乗算の少なくともひとつ、好適にはそれらの全ては、点の加算および点の二等分により行われる、
ことを特徴とする、請求項６に記載の方法。
【請求項８】
当該方法は、前記２つのエンティティの一方に属する一対の永続的鍵に基づく上記２つのエンティティ間の署名プロトコルであり、
上記一対の永続的鍵は、
一方の秘密鍵(a)、および、
該秘密鍵(a)に対して、選択された非超単一楕円曲線(E)の奇数次rの点(P)から成るもうひとつの公開鍵を乗算した結果である、他方の公開鍵(Q)、
であることを特徴とする、請求項１乃至５のいずれかに記載の方法。
【請求項９】
以下の各演算により特徴付けられる、請求項８記載の方法：
−前記永続的鍵の対を保持する前記第1エンティティ(A)は単用対の鍵を構築し、一方の鍵(g)は任意に選択され、且つ、他方の鍵[g]Pは上記任意選択鍵(g)と前記楕円曲線の公開点Pとのスカラ乗算から帰着したものであり、上記鍵([g]P)の座標は(x,y)により表現され、但し、2≦g≦r-2であり、
−上記第1エンティティ(A)は、上記単用鍵[g]P＝(x,y)の多項式xを、当該整数iの２進値が上記多項式xの２進係数の数列により表される整数iへと変換し、
−上記第1エンティティ(A)は上記メッセージ(M)の署名(c,d)を次の様に計算し：
c=i  modulo  r
d=g-1(M+ac)  modulo  r
−上記第1エンティティは上記メッセージ(M)および上記署名(c,d)を上記第2エンティティへと送信し；その受信時に；
−上記第2エンティティ(B)は、上記署名(c,d)の各要素が範囲[1,r-1]に属するか否かをチェックし、
−もしそうでなければ、それは署名無効を宣言して停止し、
−もしそうであれば、第2エンティティ(B)は３個のパラメータを計算する：
h=d-1  modulo  r
h1=Mh  modulo  r
h2=ch  modulo  r
−上記第2エンティティは、引用された最後の２個のパラメータにより上記点PおよびQのスカラ乗算を合計することにより、上記楕円曲線の点Tを計算する：
T=[h1]P＋[h2]Q
もし演算結果点Tが単位元であれば、上記第2エンティティは署名無効を宣言して停止し；
もしそれが単位元でなければ、座標x'およびy'：T=(x',y')により点Tを考える：
−上記第2エンティティは、その点の多項式x'を、当該整数i'の２進値が上記多項式x'の２進係数の数列により表される整数i'へと変換し、
−上記第2エンティティ(B)はc'＝i'  modulo  rを計算し、且つ、
−c'=cか否かをチェックし：もしそうであれば、第2エンティティは上記署名を有効化し、且つ、もしそうでなければ、第2エンティティは署名を無効化し、上記各スカラ乗算演算の少なくともひとつ、好適にはそれらの全ては事前定義された二等分により行われる。
【請求項１０】
二等分を使用するスカラ乗算は次の各演算により求められることを特徴とする、請求項７もしくは９に記載の方法：
−もし上記乗算のスカラがSと表現されるなら、
m＋1個の値、S0....Sm∈｛0,1｝を選択し、Sを次の如く定義し：
【数２８】
0004704640.tif 000118
rは上記奇数次であり、mはlog2(r)-1とlog2(r)との間の単一整数であり、
以下の如く上記楕円曲線(E)の一連の点(Qm+1, Qm..., Qi..., QO)を決定する段階から成るアルゴリズムを適用することにより、スカラSにより上記楕円曲線の点Pのスカラ乗算[S]Pを計算し；
【数２９】
0004704640.tif 000119
−上記系列の最終点QOを計算し、上記スカラ乗算の演算結果[S]Pを与える。
【請求項１１】
一対のエンティティにおいて実現される暗号化方法であって、該一対のエンティティの一方が非機密通信チャネルを介して該一対のエンティティの他方と情報を機密の態様で交換するための暗号化方法において、
該一対のエンティティの各々は、機械によって読取り可能であり該方法を機能させるための実行可能なプログラムを包含するメモリを具備し、
該方法は、該一方のエンティティによって該他方のエンティティに送信されるべき情報アイテムから導出される整数を、非超単一楕円曲線の奇数次点に乗算するステップ、を含み、
該乗算ステップは、該楕円曲線の奇数次点の加算および二倍化の組み合わせとして定義可能であり、
該方法は、該乗算ステップが、点の該二倍化を該点の二等分で置き換えることによって演算されることを特徴とする、方法。
【請求項１２】
該乗算ステップが該一対のエンティティの各々によって実行され、該一対のエンティティの各々によって実行される該乗算ステップにおいて使用される該整数は該一対のエンティティの当該エンティティにおいて実現される夫々の秘密鍵であり、該乗算ステップの少なくとも一つは該一対のエンティティの各々において実現される該非超単一楕円曲線（Ｅ）の奇数次点（Ｐ）からなる公開鍵に適用され、該方法は該一対のエンティティに共通する鍵を該乗算ステップの結果から構築するステップを更に具備する、請求項１１に記載の方法。
【請求項１３】
第１エンティティおよび第２エンティティの該夫々の秘密鍵は、 a および b と夫々表記され、且つ、
−該第１エンティティは、該奇数点 P に該整数 a を乗じる乗算からなる、[a]P と表記されるスカラ乗算を計算し、該スカラ乗算の結果を第１結果点として、該第１結果点の識別情報を該第２エンティティへ送信し、
−該第２エンティティは、該奇数点 P に該整数 b を乗じる乗算からなる、[b]P と表記されるスカラ乗算を計算し、該スカラ乗算の結果を第２結果点として、該第２結果点の識別情報を該第１エンティティへ送信し、
−該第１エンティティは該第２結果点 [b]P に整数 a を乗じるスカラ乗算を計算する一方、該第２エンティティは該第１結果点 [a]P に整数 b を乗じるスカラ乗算を計算し、各エンティティは [a.b]P と表記される同一の結果点に到達し、該点 P または該第１もしくは第２結果点のいずれかのスカラ乗算の少なくとも一つ、好適にはそれらの全て、が点の加算および点の二等分からなり、
−該２つのエンティティは、それらの共通鍵として、前記スカラ乗算 [a.b]P により求められた前記同一の結果点の座標 (x) を選択する、
ことを特徴とする、請求項１２に記載の方法。
【発明の詳細な説明】
【０００１】
本発明は、例えばケーブルもしくは無線網などの非機密通信チャネル上で情報を交換する２つのエンティティ間で採用され、両エンティティ間における情報伝達の機密性および完全性を確かなものとする暗号化方法に関する。より詳細には本発明は、楕円曲線上の計算を採用する暗号体系の改良に関する。改良点は主に、計算時間の短縮である。
【０００２】
２つのエンティティ間で安全に鍵を交換する為に、Diffie-Hellmann鍵交換暗号化プロトコルが使用される。該プロトコルを使用する上では、数学的な意味での“群(group)”を用いる必要がある。使用され得る群は、次の形式の楕円曲線により構成される：
y2＋xy＝x3＋αx2＋β
【０００３】
もしP=(x,y)が楕円曲線E上に在れば、整数mによるEの点Pの“積”もしくは“スカラ乗算(scalar multiplication)”を定義し得ることは公知である。この演算は次の様に定義される：
[m]P＝P+P+P...＋P  (m回)。
【０００４】
当業界においては、Diffie-Hellmann鍵交換アルゴリズムにおいてこの種の楕円曲線上に被選択点Pを２倍化(doubling)することは公知である。この演算は“点の２倍化”として公知であり、反復的な２倍化／加算プロセス(double-and-add-process)の一部である。斯かる２倍化はいずれも、時間が掛かるものである。
【０００５】
上記Diffie-Hellmann鍵交換プロトコルの最も遅い部分は、上記曲線上の未知点に任意スカラを乗算することである。此処では標数２(characteristic-two)の体(body)上で定義された楕円曲線のみが考慮されるが；これは広く採用される実施方法の選択である、と言うのも、この種の体内への加算は“排他的論理和”演算に対応するからである。
【０００６】
当業界においては、低濃度(low cardinality)の体上に定義された各曲線に対するスカラの乗算は、Frobenius射を使用すれば促進され得ることは公知である。各曲線は、既知の攻撃を受けない様に選択され得る。但し少なくとも原理上は、可及的に一般的な曲線の範疇から曲線を選択して使用できれば好適であることは明らかである。本発明に係る方法の最高速変更例は、楕円曲線群の半分(half)に適用される。更に暗号化の観点からは、この半分は最適な半分である。本方法の理論を記述する前に、基本概念を検討する。
【０００７】
簡素化の為に、幾何学的に表現され得ると共に実数の集合Rに対して図１に示された式y2＋y＝x3-x2により定義された楕円曲線(E)を考慮するが、同図において水平線は整数mを表し、垂直線は整数nを表し、水平線と垂直線との各交点は整数座標対(m,n)を表している。
【０００８】
(E)は整数座標を有する有限個の点を通ると共に、任意の斯かる点から発する(E)における任意の割線(secant)は２点で(E)と交差するが、(この割線が上記曲線の接線である場合に)上記２点は一点になり得る。
【０００９】
これらの任意の２個の点AおよびBに対して適用される加算演算は次の様に定義される：直線セグメント(AB)が(E)と交差する点をB1とすれば、B1を通る垂線はC=A+Bにて(E)と交差する。
【００１０】
(AB')が(E)に対する接線であるという特殊な場合、C'が必要とされる和である。
【００１１】
“全ての垂線の交差”点Oは(E)の無限遠における点と称されると共に、この様にして定義された加算の単位元である、と言うのも、加算を定義する幾何学的構造を適用すると、
A+O=O+A=A
だからである。
【００１２】
故に、[2]Aと表現されると共にA+Aと定義されるAの２倍化は点B'であり、直線(Ax)がAにおける(E)への接線である。
【００１３】
Aの加算による作図を点B'に適用することにより、点[3]Aなどが求められ：これは整数と点との積[n]Aの定義である。
【００１４】
本発明は事実、幾何学的には表現され得ないが次の様に定義される楕円曲線の集合に関している：
nは所定整数、
【数３０】
0004704640.tif 000002
は2n個の要素の体、
【数３１】
0004704640.tif 000003
はその代数学的閉包とする。Oは無限遠における点とする。
【数３２】
0004704640.tif 000004
にて定義された非超単一楕円曲線(non-supersingular elliptic curve)Eは：
【数３３】
0004704640.tif 000005
である。
【００１５】
Eの各要素は通常は“点”と称される。当業界では、点を単位元として無限遠に取ることによりEは可換(abelian)群構造が与えられ得ることが公知である。以下においては、Eの各有理点の有限部分集合が考察されると共に、
【数３４】
0004704640.tif 000006
として定義され、式中、Nは自然整数の集合であり；全てのm∈Nに対し、Eにおける“mの乗算”の写像(application)は
【数３５】
0004704640.tif 000007
である。
【００１６】
E[m]はこの写像の核(kernel)である。群E[m]の各点はEのm-捩点(m-torsion point)と称される。各m-捩点の群構造は、当業界では公知である。
【００１７】
mが2の累乗である場合：
【数３６】
0004704640.tif 000008
であり、式中、Zは相対整数(relative integer)の集合である。
【００１８】
【数３７】
0004704640.tif 000009
はEの有限部分集合であることから、k≦k'であるときに且つその場合にのみE[2k]が
【数３８】
0004704640.tif 000010
内に包含される如きk'≧1が存在する。k'＝1である楕円曲線(E)に対し、
【数３９】
0004704640.tif 000011
は：
【数４０】
0004704640.tif 000012
であり、式中、Gは奇数次群であり、T2はEの固有二次点(unique second order point)を表す。この種の曲線は、最小２捩(minimal two-torsion)を有すると言われる。
【００１９】
今や、本発明の目的を説明することが可能である。２倍化はそれがEもしくは
【数４１】
0004704640.tif 000013
上で定義されたときに単射的(injective)でない、と言うのも、その核は：
【数４２】
0004704640.tif 000014
だからである。
【００２０】
更に、もし２倍化を定義する領域が奇数次部分集合
【数４３】
0004704640.tif 000015
へと減少されれば、２倍化は双射的となる。
【００２１】
結果として、２倍化による部分集合への逆写像(inverse application)が可能とされるが、これは以下においては、[2]Q＝Pである如く、
二等分：
[1/2]:  G→G
[2]Q＝Pである如き  P→Q
を行うものと称される。
【００２２】
[1/2]Pは、２倍化写像により点Pが対応せしめられるGの点である。全てのk≧1に対し、
【数４４】
0004704640.tif 000016
はそれ自体による二等分写像のk合成(k compositions)を表す。
【００２３】
故に概略的に述べると、本発明は、非超単一楕円曲線の奇数次点に整数を乗算する段階を含む暗号化方法であって非機密通信チャネルを介して情報を交換する２つのエンティティ間で採用される暗号化方法において、上記非機密通信チャネルを介して情報を交換する為に、上記段階は上記楕円曲線の点を加算および二等分する段階を含み、点の加算は当業界で公知の演算であり、且つ、点Pの上記二等分は、
【数４５】
0004704640.tif 000017
が二等分演算を表現し且つ
【数４６】
0004704640.tif 000018
が点Dを表現するものとして、[2]D＝Pである如き一意的奇数次点として定義されることを特徴とする、暗号化方法を提供する。
【００２４】
楕円曲線上の点のスカラ乗算に対する二等分写像(halving application)は次の理由により有用である：もしアファイン座標が使用されるならば、スカラ乗算による点の全ての２倍化を点の二等分で置き換えることが可能である。
【００２５】
点の二等分は、その２倍化を計算するよりも相当に高速である。暗号化の観点からは、最大限可能的個数の曲線から選択し得ることは好適であり、通常、
【数４７】
0004704640.tif 000019
の２捩がZ/4Zに対して最小もしくは同型的(isomorphic)である曲線がその為に使用される。与えられた曲線
【数４８】
0004704640.tif 000020
に対し、最小２捩楕円曲線は厳密に、
【数４９】
0004704640.tif 000021
上に定義された楕円曲線の集合の半分を構成する。これは何故かと言えば、全体としては一般的でないが、記述された方法の最高速変更例は暗号作成法において問題となる曲線の相当の割合に対して適用されるからである。それはまた、体の各要素が正規基(normal basis)で表されたときにも適用され得る。多項基(polynomial basis)の場合、必要なメモリ空間はO(n2)ビットのオーダーである。
【００２６】
以下においては添付図面を参照して幾つかの例が与えられる。
【００２７】
先ず、P∈Gから[1/2]P∈Gを計算する方法を示す。次に、各点の２倍化を二等分により置換してスカラによる乗算を実行する方法を示す。
【００２８】
また、点の通常のアファイン表現(affine representation)が使用される：P＝(x,y)および表現(x,λP)であり、λP＝x＋y/xである。
【００２９】
而して、y＝x(x＋λP)が導かれるが、これは第2表現(second representation)から１回の乗算のみを使用する。
【００３０】
この様に続行することにより、点にスカラを乗算する為に、表現(x,λP)を使用して中間結果を計算することにより乗算に関する時間節約が行われ、且つ、アファイン表現の座標は計算の終了時においてのみ決定される。
【００３１】
点Pは次の様にして二等分される：Pから[1/2]Pを計算する。この為に、[2]Q=Pである如きEの２個の点を考察する：
P=(x,y)=(x,x(x+λP))、および、
Q=(u,v)=(u,u(u+λQ))
当業界にて公知の２倍化の為の式は以下を与える：
λQ=u＋v/u    (1)
x＝λQ2＋λQ＋α    (2)
y＝(x+u)λQ＋x＋v    (3)。
【００３２】
(1)にuを乗算し、この様にして(3)で求められたvの値を代入すると、上記系は次の様になる：
v=u(u＋λQ)
λQ2＋λQ＝α＋x
y＝(x＋u)λQ＋x＋u2＋uλQ＝u2＋x(λQ＋1)、
又は、y＝x(x＋λP)なので、
λQ2＋λQ＝α＋x    (i)
u2＝(x(λQ＋1)＋y=(λQ＋λP＋x＋1)    (ii)
v＝u(u＋λQ)    (iii)
である。
【００３３】
アファイン座標におけるもしくは(x,λP)表現における点P=(x,y)=(x,x(x+λP))から開始すると、各式の上記系は次の２つの形式を決定する：
【数５０】
0004704640.tif 000022
これは、２倍化によりPを与えるものである。以下の特性によれば、それが区別され得る。
【００３４】
Eが最小２捩楕円曲線であり、且つ、
【数５１】
0004704640.tif 000023
はその奇数次要素のひとつであるとする。また、Q∈｛[1/2]P，[1/2]P＋T2｝であり、Q1は[2]Q1＝Qである如きEの２個の点の一方であるとする。
【００３５】
必要十分条件は：
【数５２】
0004704640.tif 000024
である。
【００３６】
この式からは、上記式(i)、(ii)および(iii)をQに適用し且つ求められた各点のひとつが
【数５３】
0004704640.tif 000025
に属するか否かを検証することにより、Q＝[1/2]Pであるか否かをチェックし得ることが導かれる。
【００３７】
これは、上記式(i)、(ii)および(iii)をk回適用することで、任意の楕円曲線
【数５４】
0004704640.tif 000026
に拡張され得る：Qに対する第1回目は[2]Q1＝Qである如き点Q1を求め；Qi-1に対する第i回目は[2]Qi＝Qi-1である如き点Qiを求める。結果的な点QkはQ＝[1/2]P＋T2であれば且つその場合にのみ、
【数５５】
0004704640.tif 000027
の形態であり、Q＝[1/2]Pであれば且つその場合にのみ、0≦i≦kとして
【数５６】
0004704640.tif 000028
の形態である。故に必要十分条件は：
【数５７】
0004704640.tif 000029
である。
【００３８】
もしkが大きければ、上記プロセスは明らかに冗長である。
【００３９】
上記式(a)は、Q1の座標が
【数５８】
0004704640.tif 000030
に属しまたは
【数５９】
0004704640.tif 000031
の超体(super-body)に属するか否かを検証することにより、Q＝[1/2]PであるかQ＝[1/2]P＋T2であるかを決定し得ることを示している。Q1は上記式(i)、(ii)および(iii)により決定されることから、これらの式を解く上で使用される各演算を考察せねばならないが、それらは上記体の内部では無く、
【数６０】
0004704640.tif 000032
の超体上に演算結果を有している。唯一の可能的な事例は、２次式(second degree equation)(i)を解くことである：また、Q1の第1座標を計算すべく平方根も計算せねばならないが、標数２において平方根を求めることは上記体内の演算である。故に、
【数６１】
0004704640.tif 000033
である。
【００４０】
平方根を求めることは上記体の内部であることから、この必要十分条件は次の様にも書かれ得る：
【数６２】
0004704640.tif 000034
【００４１】
上記の関係は、平方根の計算時間が無視し得ない場合に、以下で言及されるアルゴリズムを最適化すべく使用される。
【００４２】
P∈Gに対し、(i)の２つの解はλ[1/2]Pおよびλ[1/2]P＋1であり、(ii)からは、関連する各点の各第1座標がuおよび
【数６３】
0004704640.tif 000035
であることが導かれる。故に、次の如くに[1/2]Pを計算するアルゴリズムが導かれる：
【００４３】
もし
【数６４】
0004704640.tif 000036
が2n個の要素の有限体であり、
【数６５】
0004704640.tif 000037
は次式により定義される楕円曲線(E)の部分集合であり：
【数６６】
0004704640.tif 000038
且つ、kが1以上の整数であるときにPをP自体に対して2k回加算すると単位元
【数６７】
0004704640.tif 000039
が与えられる如くE[2k]が上記楕円曲線の各点Pの集合であれば、上記楕円曲線の点P＝(x,y)は、上記二等分により、図３のフローチャートにより示された下記の各演算を行って求められた上記楕円曲線の点
【数６８】
0004704640.tif 000040
を与える：
・λO2＋λO＝α＋xである如き第1値λOを探す；
・uO2＝x(λO＋1)＋yである如き第2値uO2を計算する；
・もしkが値1を有すれば、式：λ2＋λ＝α2＋uO2が
【数６９】
0004704640.tif 000041
内に解を有するか否かをチェックする；
・もしそうであれば、上記二等分を次の如く計算する：
【数７０】
0004704640.tif 000042
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する；
・もしkが1より大きければ、次の反復的計算を行う：
uk-12が求まるまでi＝1からiをインクリメントすることにより、
λi2＋λi＝α＋ui-1である如き値λiを探し、
次に、u2i＝ui-1(λi＋λi-1＋ui-1＋1)である如き値u2iを計算する；
・上記式λ2＋λ＝α2＋u2k-1が
【数７１】
0004704640.tif 000043
に解を有するか否かをチェックする；
・もしそうであれば、次の如く上記二等分を計算する：
【数７２】
0004704640.tif 000044
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する。
【００４４】
もし、上記楕円曲線の点
【数７３】
0004704640.tif 000045
を、λO＝uO＋vO/uOとして(uO,λO)により表すことを選択したなら、上記アルゴリズムは図４のフローチャートに従う：
・λO2＋λO＝α＋xである如き第1値λOを探す；
・uO2＝x(λO＋1)＋yである如き第2値uO2を計算する；
・もしkが値1を有すれば、式：λ2＋λO＝α2＋uO2が
【数７４】
0004704640.tif 000046
内に解を有するか否かをチェックする；
・もしそうであれば、上記二等分を次の如く計算する：
【数７５】
0004704640.tif 000047
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する；
・もしkが1より大きければ、次の反復的計算を行う：
uk-12が求まるまでi＝1からiをインクリメントすることにより、
λi2＋λi＝α＋ui-1である如き値λiを探し、
次に、ui2＝ui-1(λi＋λi-1＋ui-1＋1)である如き値u2iを計算する；
・上記式λ2＋λ＝α2＋u2k-1が
【数７６】
0004704640.tif 000048
に解を有するか否かをチェックする；
・もしそうであれば、次の如く上記二等分を計算する：
【数７７】
0004704640.tif 000049
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する。
【００４５】
もし、上記楕円曲線の点
【数７８】
0004704640.tif 000050
を上記二等分により与えるλP＝x＋y/xを設定する(x,λP)により点P＝(x,y)を表すことを選択したなら、上記アルゴリズムは図５のフローチャートに従う：
・λO2＋λO＝α＋xである如き第1値λOを探す；
・uO2＝x(λO＋λP＋x＋1)である如き第2値uO2を計算する；
・もしkが値1を有すれば、式：λ2＋λ＝α2＋uO2が
【数７９】
0004704640.tif 000051
内に解を有するか否かをチェックする；
・もしそうであれば、上記二等分を次の如く計算する：
【数８０】
0004704640.tif 000052
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する；
・もしkが1より大きければ、次の反復的計算を行う：
u2k-1が求まるまでi＝1からiをインクリメントすることにより、
λi2＋λi＝α＋ui-1である如き値λiを探し、
次に、u2i＝ui-1(λi＋λi-1＋ui-1＋1)である如き値u2iを計算する；
・上記式λ2＋λ＝α2＋u2k-1が
【数８１】
0004704640.tif 000053
に解を有するか否かをチェックする；
・もしそうであれば、次の如く上記二等分を計算する：
【数８２】
0004704640.tif 000054
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する。
【００４６】
最後に、λO＝uO＋vO/uOとして(uO,λO)により表された上記楕円曲線の点
【数８３】
0004704640.tif 000055
を上記二等分により与えるλP＝x＋y/xを以て(x,λP)により点P＝(x,y)を表すことを選択したなら、上記アルゴリズムは図６のフローチャートに従う：
・λO2＋λO＝α＋xである如き第1値λOを探す；
・uO2＝x(λO＋λP＋x＋1)である如き第2値uO2を計算する；
・もしkが値1を有すれば、式：λ2＋λ＝α2＋uO2が
【数８４】
0004704640.tif 000056
内に解を有するか否かをチェックする；
・もしそうであれば、上記二等分を次の如く計算する：
【数８５】
0004704640.tif 000057
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する；
・もしkが1より大きければ、次の反復的計算を行う：
u2k-1が求まるまでi＝1からiをインクリメントすることにより、
λi2＋λi＝α＋ui-1である如き値λiを探し、
次に、ui2＝ui-1(λi＋λi-1＋ui-1＋1)である如き値u2iを計算する；
・上記式λ2＋λ＝α2＋u2k-1が
【数８６】
0004704640.tif 000058
に解を有するか否かをチェックする；
・もしそうであれば、次の如く上記二等分を計算する：
【数８７】
0004704640.tif 000059
・もしそうでなければ、上記第2値uO2にxを加算し且つ上記第1値λOに1を加算して、先行演算における如く上記二等分を計算する。
【００４７】
次に、点を高速に二等分する上記アルゴリズムにおいて、チェックを行い、２次式を解き、且つ、平方根を計算する方法を記述する。正規基の場合および多項基の場合を考察する。
【００４８】
正規基の場合の演算結果は当業界にて公知である。此処では、
【数８８】
0004704640.tif 000060
をF2上のn次元ベクトル空間として考察し得る。正規基において、上記体の要素は次式により表される：
【数８９】
0004704640.tif 000061
正規基において、平方根は左回転シフト(left circular shift)により計算され、且つ、二乗は右回転シフトにより行われる。故に、対応する計算時間は無視され得る。
【００４９】
もし２次式λ2＋λ＝xがその解を
【数９０】
0004704640.tif 000062
内に有すれば、そのときの解は次式により与えられる：
【数９１】
0004704640.tif 000063
【００５０】
λを計算する時間は、上記体内で反転(inversion)の乗算を計算する時間に比べて無視され得るものである。上記２次式の解を計算する時間が無視され得ることから、上記チェックは次の様に行われ得る：xから候補λを計算し、λ2＋λ＝xであるか否かをチェックする。もしそうでなければ、その式は
【数９２】
0004704640.tif 000064
内に解を有さない。
【００５１】
多項基においては次の表現が使用される：
【数９３】
0004704640.tif 000065
、但し、xi＝∈(0,1)である。もし、
−標数２の体において、平方根が上記体の射(morphism)
【数９４】
0004704640.tif 000066
であることに留意すれば、xの平方根は要素
【数９５】
0004704640.tif 000067
を記憶(store)することにより計算され得る。
【００５２】
xにおいてTの偶数累乗および奇数累乗を分類し、且つ、その平方根を取ると、次の様になる：
【数９６】
0004704640.tif 000068
従って、平方根を計算する為には、２つのベクトルを半分に“減少”し、故に、既に計算された値に対する長さn/2の要素の乗算を実行するだけで十分である。このことが、多項基において平方根を計算する時間が、上記体において乗算を計算する時間の半分に等しい理由である。
【００５３】
上記２次式をチェックして解く為に、
【数９７】
0004704640.tif 000069
をF2上のn次元ベクトル空間として考える。その場合、
【数９８】
0004704640.tif 000070
として定義された写像(application)Fは線形核(linear kernel)演算子(0,1)である。
【００５４】
与えられたxに対し、式λ2＋λ＝xは、ベクトルxがFの像(image)内であるときに且つその場合にのみ
【数９９】
0004704640.tif 000071
内に解を有する。Im(F)は
【数１００】
0004704640.tif 000072
の(n-1)次元部分空間である。与えられた
【数１０１】
0004704640.tif 000073
の基(basis)および対応スカラ積に対し、Im(F)の全てのベクトルに対して直交する単一の非自明ベクトルが存在する。そのベクトルをwとする。その場合、
【数１０２】
0004704640.tif 000074
である。
【００５５】
故に上記チェックは、1に等しいwの各成分が対応するものに対してxの成分を加算することにより実施され得る。このチェックを実施する時間は無視され得る。
【００５６】
多項基において２次式F(λ)＝λ2＋λ＝xを解くべく、n×n行列の記憶を課す簡素で直接的な方法が提案される。この為に、
∀x∈Im(F)：F(G(x))=(G(x))2＋G(x)=x
である如き線形演算子Gを探ことにする。
【数１０３】
0004704640.tif 000075
である如きベクトルを
【数１０４】
0004704640.tif 000076
とし、Gを次の様に定義する：
【数１０５】
0004704640.tif 000077
【００５７】
【数１０６】
0004704640.tif 000078
とすれば、G(x)は上記２次式の解である。ひとつの実施方法は、上記基(1, T, .....,Tn-1)においてGを表す行列を事前計算する段階から成る。標数２においては、行列に対するベクトルの乗算は、1に等しい上記ベクトルの成分が対応するものに対する上記行列の各列の加算へと減少される。結果として、２次式を解く該方法は体
【数１０７】
0004704640.tif 000079
において平均でn/2回の加算を消費する。
【００５８】
以下においては、上記で説明した原理をスカラ乗算に適用する手法を記述する。
【００５９】
【数１０８】
0004704640.tif 000080
が奇数次rの点であり、cは任意整数であり、mはlog2(r)の整数部分とする。点とスカラとの積[c]Pは、点を二等分する写像(application)を使用して計算する。
【００６０】
而して、任意の整数cに対し、
【数１０９】
0004704640.tif 000081
の形態の有理数が在ることを示すものとする。<P>をPにより生成される循環群(cyclic group)とする。
【数１１０】
0004704640.tif 000082
という環同型写像(ring isomorphism)の故に、
[k]P→k
である。上記スカラ乗算は二等分および加算を使用して次の様に計算され得る：
【数１１１】
0004704640.tif 000083
これらの計算に対しては、当業界で公知の２倍化／加算アルゴリズムを使用し得る。その為には、２倍化を二等分で置換するだけで十分である。log2(r)回の二等分と、平均して1/2 log2(r)回の加算を実行することが必要である。平均して1/3 log2(r)回の加算のみを必要とする２倍化／加算アルゴリズムの改良変更例が在る。
【００６１】
故に、上記で定義された二等分を使用したスカラ乗算は、次の演算により求められる：
−もし上記乗算のスカラがSと表現されるなら、
m＋1個の値、S0....Sm∈｛0,1｝を選択し、Sを次の如く定義し：
【数１１２】
0004704640.tif 000084
−rは上記奇数次であり、mはlog2(r)-1とlog2(r)との間の単一整数であり、
−以下の如く上記楕円曲線(E)の一連の点(Qm+1, Qm..., Qi..., QO)を決定する段階から成るアルゴリズムを適用することにより、スカラSにより上記楕円曲線の点Pのスカラ乗算[S]Pを計算し；
【数１１３】
0004704640.tif 000085
−上記系列の最終点QOを計算し、上記スカラ乗算の演算結果[S]Pを与える。
【００６２】
初期点Pを中間結果
【数１１４】
0004704640.tif 000086
に加算すべく次のアルゴリズムを使用するが、これは標準的アルゴリズムの僅かな改変例である：
入力：アファイン座標におけるP＝(x,y)、および、(u,λQ)により表されるQ＝(u,u(u+λQ))
出力：アファイン座標におけるP＋Q＝(s,t)
アルゴリズム
1.計算：
【数１１５】
0004704640.tif 000087
2.計算：s＝λ2＋λ＋a＋x＋u
3.計算：t＝(s＋x)λ＋s＋y
4.演算結果：(s,t)
【００６３】
このアルゴリズムは、１回の反転(inversion)、３回の乗算および１回の平方根を使用する。
【００６４】
２倍化を二等分に置換えることにより、相当の時間が節約される。アファイン座標において、２倍化および加算はいずれも次のものを要する：１回の反転、２回の乗算、および、１回の平方根。もしスカラによる乗算のスカラが長さmおよびk個の非ゼロ成分のビット・ベクトルにより表されるなら、スカラ乗算は次のものを要する：
【表１】
0004704640.tif 000088
【００６５】
故に、二等分を使用すると、m回の２次解(second degree solution)、m回の平方根およびm回のチェックを負担して、m回の反転、m-k回の乗算およびm回の二乗が節約される。
【００６６】
多項基においては、約50％の実行時間改善が獲得され得る。
【００６７】
正規基においては、乗算もしくは反転を計算する時間と比較して、平方根を計算し、チェックを行い且つ２次式を解く時間は無視されると評価される。更に、反転を計算する時間が３回の乗算を計算する時間に等しいと仮定すれば、55％の実行時間改善に到達する。
【００６８】
図２は、非機密通信チャネル上で情報を交換する２つのエンティティAおよびBの間における上記アルゴリズムのひとつの可能的適用を示す図である。上記通信チャネルは、トランザクションの時間に対して２つのエンティティ間で確立された簡素な電気接続から成り得る。それはまた、無線および／または光による遠隔通信ネットワークも含み得る。この場合にエンティティAはマイクロ回路カードでありエンティティBはサーバである。上記通信チャネルを介して相互に接続されたなら、２つのエンティティは共通鍵構築プロトコルを適用する。この目的の為に、
−エンティティAは秘密鍵aを有し、
−エンティティBは秘密鍵bを有する。
【００６９】
各エンティティは、選択された非超単一楕円曲線Eの奇数次rの点Pから成る公開鍵から、各エンティティ自体のみが知る秘密鍵xを生成しなければならない。
【００７０】
採用されたプロトコルはDiffie-Hellmannプロトコルであり、これは、２倍化と称される通常の“２による乗算(multiplication-by-two)”の代わりに、上述されると共に“二等分(halving)”と称される本発明の演算を使用する。
【００７１】
この為のアルゴリズムは次の如くである：
−第1のエンティティ(例えばA)はスカラ乗算[a]Pを計算し、結果的な点を第2エンティティへと送信し、
−第2エンティティ(B)はスカラ乗算[b]Pを計算し、結果的な点を第1エンティティへ送信し、
−２つのエンティティは夫々、両方ともに[a.b]Pに等しいスカラ乗算[a]([b]P)および[b]([a]P)を行うことにより、上記楕円曲線(E)の共通点(C)=(x,y)を計算し、
−２つのエンティティはそれらの共通鍵として、上記スカラ乗算[a.b]Pにより求められた上記共通点(C)の座標xを選択するが、先行する各スカラ乗算の少なくともひとつ、好適にはそれらの全ては事前定義された二等分により行われる。
【００７２】
これの更に正確な例を与えるべく図７は、例えばモデム・インタフェースなどの通信インタフェース2を介して通信ネットワーク1に接続されたサーバBを示している。同様に、上記通信ネットワーク1に対しては通信インタフェース4を介して計算ステーション3が接続される。該ステーション3は、マイクロ回路カードAが挿入されるマイクロ回路カードリーダ5を備えている。
【００７３】
サーバBのランダム・アクセス・メモリ6は、各楕円曲線上の暗号化計算、特に、点とスカラとの積と、点の二等分とを実行し得るプログラム7を含んでいる。
【００７４】
カードAは、中央処理ユニット11、ランダム・アクセス・メモリ(RAM)8、読出専用メモリ(ROM)9および電気的消去／書込可能読出専用メモリ(EEPROM)10を含んでいる。メモリ9もしくは10の一方は、各楕円曲線上の暗号化計算、特に、点とスカラとの積と、点の二等分とを実行し得るプログラム12を含んでいる。
【００７５】
２つのプログラム7および12は、同一の楕円曲線(E)と該(E)の同一点P＝(x0,y0)から成る共通基準(common reference)を有している。
【００７６】
Bとの対話を安全にすべく共通秘密鍵をBと並行して構築せんとAが意図したとき、Aはスカラaを選択してBに対して積Q＝[a]P(x1,y1)を送信する。これに応じ、bはスカラbを選択して積R＝[b]P=(x2,y2)をAに戻し送信する。
【００７７】
次にaは積[a]R＝[ab]P=(x,y)を計算し、Bは[b]Q＝[ab]P=(x,y)を計算し、且つ、AおよびBはxを共通秘密鍵として採用する。
【００７８】
これらの演算は、以下の表中に表される。サーバBで行われる演算は右側列内に示され、カードAで行われる演算は左側列内に示される。水平な矢印はネットワーク1を介した情報の伝達を記号化している。
【数１１６】
0004704640.tif 000089
【００７９】
本発明の別の適用例は、図７における２つのエンティティAおよびBの間に適用される。それは、非機密チャネルすなわちネットワーク1を介してAおよびB間で伝送されるメッセージMに署名(sign)するプロトコルから成る。当業界においてその広範囲な概要は公知であるが、該プロトコルの目的は、ひとつのエンティティにより受信されたメッセージが他のエンティティにより送信されたことを確実にすることである。
【００８０】
この目的の為に、送信エンティティ(例えばA)は２個の永続的鍵すなわち秘密鍵aおよび公開鍵Q＝[a]Pを有し、Pは楕円曲線(E)上の点であり、且つ、Pおよび(E)はAおよびBが既知であり且つAおよびBにより同意されている。もうひとつの公開鍵は、選択された非超単一楕円曲線Eの奇数次rの点Pである。行われる各演算は、上記で定義された意味での二等分を伴う。
【００８１】
ひとつの例において：
−上記永続的鍵の対を保持する第1エンティティ(A)は単用対(single-use pair)の鍵を構築し、一方の鍵(g)は任意に選択され、且つ、他方の鍵[g]Pは上記任意選択鍵(g)と上記楕円曲線の公開点Pとのスカラ乗算から帰着したものであり、上記鍵([g]P)の座標は(x,y)により表現され、但し、2≦g≦r-2であり、
−第1エンティティ(A)は、上記単用鍵[g]P＝(x,y)の多項式(polynomial)xを、当該整数iの２進値が上記多項式xの２進係数の数列により表される整数iへと変換し、
−上記第1エンティティ(A)は上記メッセージ(M)の署名(c,d)を次の様に計算し：
c=i  modulo  r
d=g-1(M+ac)  modulo  r
−上記第1エンティティは上記メッセージ(M)および上記署名(c,d)を上記第2エンティティへと送信し；その受信時に；
−上記第2エンティティ(B)は、上記署名(c,d)の各要素が範囲[1,r-1]に属するか否かをチェックし、
−もしそうでなければ、それは署名無効を宣言して停止し、
−もしそうであれば、第2エンティティ(B)は３個のパラメータを計算する：
h=d-1  modulo  r
h1=Mh  modulo  r
h2=ch  modulo  r
−上記第2エンティティは、引用された最後の２個のパラメータにより上記点PおよびQのスカラ乗算を合計することにより、上記楕円曲線の点Tを計算する：
T=[h1]P＋[h2]Q
【００８２】
もし演算結果点Tが単位元であれば、上記第2エンティティは署名無効を宣言して停止する。
【００８３】
もしそれが単位元でなければ、座標x'およびy'：T=(x',y')により点Tを考える：
−上記第2エンティティは、その点の多項式x'を、当該整数i'の２進値が上記多項式x'の２進係数の数列により表される整数i'へと変換し、
−上記第2エンティティ(B)はc'＝i'  modulo  rを計算し、且つ、
−c'=cか否かをチェックし：もしそうであれば、第2エンティティは上記署名を有効化し、且つ、もしそうでなければ、第2エンティティは署名を無効化し、上記各スカラ乗算演算の少なくともひとつ、好適にはそれらの全ては事前定義された二等分により行われる。
【００８４】
これらの演算は以下の表により表されるが、下記表においてサーバBで行われる演算は右側列内に示され、カードAで行われる演算は左側列内に示され、２つの列の間の水平な矢印はネットワーク1を介した情報の伝達を記号化している。
【００８５】
【数１１７】
0004704640.tif 000090
【図面の簡単な説明】
【図１】  図１は、幾何学的に表現され得る極めて特異な楕円曲線であって、以下においては本発明に関して使用される基本的な演算を説明すべく使用される楕円曲線を示すグラフである。
【図２】  図２は、２つのエンティティ間における本発明に依る情報の交換を示す図である。
【図３】  図３は、本発明に従う幾つかの応用例を説明するフローチャートである。
【図４】  図４は、本発明に従う幾つかの応用例を説明するフローチャートである。
【図５】  図５は、本発明に従う幾つかの応用例を説明するフローチャートである。
【図６】  図６は、本発明に従う幾つかの応用例を説明するフローチャートである。
【図７】  図７は、本発明に係る暗号化方法を採用し得る２つのエンティティAおよびBの間において情報を交換し得る別のシステムのブロック図である。
【図１】
0004704640.tif 000120
【図２】
0004704640.tif 000121
【図３】
0004704640.tif 000122
【図４】
0004704640.tif 000123
【図５】
0004704640.tif 000124
【図６】
0004704640.tif 000125
【図７】
0004704640.tif 000126