8

私は楕円曲線暗号の小さなプロジェクトを書いています。このプログラムは、アフィン座標系を使用するとうまく機能します。つまり、各点は2つの座標（x'、y'）で表されます。

ここで、アフィン座標系を、各点が3つの座標（x、y、z）、x'= x /z²、y' =y/z³で表されるジャコビアン座標系に置き換えようとしています。

アフィン座標をジャコビアン座標に変換する方法を知りたい**。一部のチュートリアルでは、次の式を使用します。（x、y）=（x、y、1）これは、z座標が常に1に設定されることを意味します。しかし、それが正しいかどうかはわかりません。

次に、楕円曲線上の点の追加について、P（x1、y1、z1）+ Q（x2、y2、z2）= R（x3、y3、z3）を計算します。プログラムでは次の式を使用しました。

u1 = x1.z2²
u2 = x2.z1²
s1 = y1.z2³
s2 = y2.z1³
h = u2 - u1
r = s2 - s1
x3 = r² - h³ - 2.u1.h²
Y3 = r. (U1.h² - x3) - s1.h³
z3 = z1.z2.h

しかし、プログラムをテストすると、たとえば（-2854978200、-5344897546224,578）などの負の座標が得られます。そして、結果を式（x'= x /z²、y' = y /z³）を使用してアフィン座標系に変換しようとすると、（-8545、-27679）が得られ、実際にはx座標は-8545.689です。 ...ジャコビアンのx座標はz²で割り切れません。

座標が整数でない場合はどうすればよいですか？そして、彼らが否定的であるならば？曲線のフィールドサイズでMODを試みましたが、結果も正しくありません。

したがって、ジャコビアン座標を使用するポイント(x,y,1)は正しいですが、一意ではありません。満足するすべてのポイント(a^2.x,a^3.y,a)は同等です。そして私のプログラムでは、曲線は素体で定義されているので、計算するときにu1, u2, s1, s2 ...各変数にMOD pを適用する必要がありますか？

そして、最終結果をアフィン座標に戻すために、たとえばx座標、実際には除算ではなく、モジュラ逆数ですか？たとえば、私の曲線は有限の素体で定義されてp=11おり、ジャコビアン座標を使用してポイントがあり、(15,3,2)ジャコビアンx座標をアフィンx座標に変換するには、を計算する必要があります。したがって、アフィネx2^2 = 4 => x = 4^-1 mod p => x = 3座標15.3 mod p = 1は1です。 ？

ジャコビアン座標の目的は、加算中の分割を回避することです。しかし、Thomas Porninが言ったように、私たちが計算するとき、P1 + P2 = P3処理するいくつかの特別なケースがあります。

  1. P1とP2は両方とも無限です：P3=infinite。
  2. P1は無限です：P3=P2。
  3. P2は無限です：P3=P1。
  4. P1とP2のx座標は同じですが、y座標が異なるか、両方のy座標が0に等しくなりますP3=infinite。
  5. P1とP2のx座標は異なりますAddition formula。
  6. P1とP2の座標は同じです：Doubling formula。

そして、これが私のC関数のプロトタイプです。

jac_addition(jacobian *, point *, jacobian *);
jac_doubling(jacobian *, jacobian *);

pointjacobianアフィン座標系およびジャコビアン系で定義された点を表す構造体です。

問題は、これらの特殊なケース、特に4番目のケースを処理するときに、両方のポイントをアフィン座標に変換し直しているか、それらの座標を比較できないため、除算を計算する必要があることです。

4

3 に答える 3

10

射影座標のジャコビアン形式（他の形式と同様）は一意ではありません- Z（0以外の）すべての値に対して、実際の点を変更せずにX他の値を取得します。Y

したがって、アフィン座標に点がある場合(X', Y')、ペアはこの点の射影表現であり、、など(X', Y', 1)も同様です。1の点が最も簡単に作成できるため、通常はこれを使用します。(4·X', 8·Y', 2)(9·X', 27·Y', 3)

あらゆる体で楕円曲線を定義（および研究）でき、多くの数学者は複素数で定義された曲線を研究しますが、暗号化の用途では、座標は有限体の要素です。最も単純なケースでは、素体（つまり、素数を法とする整数）があり、このフィールドで加算、減算、乗算、除算（およびおそらくべき乗）を実行する必要があります。

ゼロでない限り、Z除算できるはずです。Z²これは、Z²の逆数を掛けることと同等であり、そのような要素が存在し、拡張ユークリッドアルゴリズムを使用して効率的に計算できます。

これは、プログラミング言語に、 JavaのBigIntegerクラス（およびメソッドを含む）のように、必要な操作が事前定義された多数のライブラリが付属している場合に最も簡単です。modmodPowmodInverse

問題のフィールド（つまり、モジュラス）は楕円曲線の定義の一部であり、あるフィールドでの操作は、別のフィールドでの操作とはまったく異なる結果をもたらします。したがって、正しいフィールドを使用していることを確認してください。

于 2011-12-05T21:27:33.123 に答える
4

楕円曲線を扱う場合、座標はフィールドにあります。暗号化の場合、これは有限体です。あなたの場合、「素数pを法とする整数」。すべての演算はそのフィールドを対象としています。つまり、 pを法として、すべての加算、乗算、または反転を実行する必要があります。

ポイントの加算を行う場合、特別に処理しなければならないいくつかの特殊なケースがあります。

  • 座標xとyを持たない特別な「無限遠点」があります。これは、曲線加算の「ゼロ」です。一般的なポイント追加ルーチンでは、「無限遠点」をエンコードして特別にチェックする方法が必要です。

  • （x、y）を（x'、y'）に追加すると、 x=x'になる場合があります。その場合、y = y'のいずれかであり、特定の式を持つポイントダブリングです（一般式を適用すると、ゼロ除算になり、機能しなくなります）。または、y = -y'。この場合、合計は「無限遠点」になります。

したがって、一般式は、特殊なケースを処理した後でのみ適用されます。すべての一般性において、曲線y 2 = x 3 + a・x + bでは、 （x 1、y 1）と（x 2、y 2）の合計は（x 3、y 3）であり、x 3 = f 2 -x 1 - x2およびy3= f・（x1 -x 3 ） -y 1 、ここでf = （y 2 -y 1）/（x 2 -x 1）。これは、1つの除算と2つの乗算、およびいくつかの減算を計算することを意味します（上記で説明したように、すべての演算はpを法とする整数で実行されます）。

pを法とする除算と反転は比較的高価であるため（モジュラー除算は通常、約80の乗算と同じコストです）、状況によっては、射影座標系またはJacobian座標系を使用します。ジャコビアン座標は、 x = X /Z2およびy =Y / Z 3のように、点を3つの値（X、Y、Z） （すべて有限体、つまりpを法とする整数）として表すことを目的としています。

各点（x、y）には、 （X、Y、Z）として多くの可能な表現があります。X = x、Y = y、Z = 1に設定すると、Jacobian座標への変換が簡単になります。（x 、y、1）は（x、y）点の完全に有効なJacobian表現です。ジャコビアン座標からの変換は計算が難しくなります。モジュラー反転といくつかの乗算を実行する必要があります（U = 1 / Zを計算し、次にx = X・U2およびy = Y・U 3を計算します）。

Jacobian座標では、2つのポイントの加算は、1ダースのフィールド乗算で行われ、除算はまったく行われません。結果のJacobian表現しか得られないため、ある時点でモジュラー反転または除算を実行する必要があります。ただし（そのため、Jacobian座標を使用する必要があります）、その除算は相互に関連付けることができます。100程度の連続したポイントの追加を行う必要がある場合（暗号化のコンテキストで一般的であるように、ポイントを整数で「乗算」する場合）、全体でJacobian表現を使用し、デカルト座標に1回変換して戻すことができます（ x、y）最後に。したがって、200回の乗算と100回の除算を行う代わりに、1000回の乗算と1回の反転を行います。反転には80回の乗算と同じコストがかかるため、ゲインはかなり高くなります。

この本を利用してみてください; どんな良い大学図書館にもそれが必要です。それはそのすべてを非常に明確に説明しています。

于 2011-12-06T12:21:01.693 に答える
1

これがPythonのサンプルです：

def to_jacobian((Xp, Yp)):
    """
    Convert point to Jacobian coordinates

    :param (Xp,Yp,Zp): First Point you want to add
    :return: Point in Jacobian coordinates
    """
    return (Xp, Yp, 1)

def from_jacobian((Xp, Yp, Zp), P):
    """
    Convert point back from Jacobian coordinates

    :param (Xp,Yp,Zp): First Point you want to add
    :param P: Prime number in the module of the equation Y^2 = X^3 + A*X + B (mod p)
    :return: Point in default coordinates
    """
    z = inv(Zp, P)
    return ((Xp * z**2) % P, (Yp * z**3) % P)

def jacobian_add((Xp, Yp, Zp), (Xq, Yq, Zq), A, P):
    """
    Add two points in elliptic curves

    :param (Xp,Yp,Zp): First Point you want to add
    :param (Xq,Yq,Zq): Second Point you want to add
    :param P: Prime number in the module of the equation Y^2 = X^3 + A*X + B (mod p)
    :param A: Coefficient of the first-order term of the equation Y^2 = X^3 + A*X + B (mod p)
    :return: Point that represents the sum of First and Second Point
    """
    if not Yp:
        return (Xq, Yq, Zq)
    if not Yq:
        return (Xp, Yp, Zp)
    U1 = (Xp * Zq ** 2) % P
    U2 = (Xq * Zp ** 2) % P
    S1 = (Yp * Zq ** 3) % P
    S2 = (Yq * Zp ** 3) % P
    if U1 == U2:
        if S1 != S2:
            return (0, 0, 1)
        return jacobian_double((Xp, Yp, Zp), A, P)
    H = U2 - U1
    R = S2 - S1
    H2 = (H * H) % P
    H3 = (H * H2) % P
    U1H2 = (U1 * H2) % P
    nx = (R ** 2 - H3 - 2 * U1H2) % P
    ny = (R * (U1H2 - nx) - S1 * H3) % P
    nz = (H * Zp * Zq) % P
    return (nx, ny, nz)

したがって、次のように合計できます。

def fast_add(a, b, A, P):
    return from_jacobian(jacobian_add(to_jacobian(a), to_jacobian(b), A, P), P)
于 2018-08-27T03:37:13.043 に答える