ECDSA署名検証原理及びC言語実現

27596 ワード
組み込み開発 C 暗号学 ECDSA ツール
この2,3日やっとECDSAを理解して、もともとECDSAホイールを作りたいと思っていましたが、最近少し忙しくて、ECDSAホイールはHASHのように簡単ではありませんので、直接既製のホイールを持ってECDSAの勉強の心得を記録しました.ここにはgithubの学習に適したECDSAコードが貼られています.もちろん、このバージョンのコードにはopensslなどのビジネスクラスのコード専門はありませんが、ECDSAの原理を学ぶのに十分簡単で、非常に適しています.easy-ecc
非対称暗号化アルゴリズムの署名/検証は3つのステップにほかならない:1.鍵生成keygen 2.署名sign 3.ベリファイverify
後述はECDSA 384を例に挙げます.
1キー生成
鍵の生成は実は主に楕円曲線ECCのいくつかの原理に関連して、この小記の中で、もう原理を述べないで、ネット上で原理を話す文章はとても多いです.私も当時、以下の文章を見てECCの原理を入門しました.とても良い文章で、皆さんに共有します.楕円曲線暗号学概要楕円曲線暗号学の簡単な紹介
楕円曲線の定義
以上から,楕円の一般式はy^2=x^3+a*x+b mod pと無限大の数0であることが分かったが,もちろん最も本格的な定義には有限領域にあり,a,b,qの間にも関係がある限定条件がある.
ECDSAの鍵の計算方式
  • は楕円曲線Eを用いる、ここで、係数pがa及びbの素数次nの循環群を生成する点G
    • である.
  • ランダム整数dが選択され、0
  • はB=dGを計算し、dはECSDAの秘密鍵であり、点B(x,y)はECDSAの公開鍵である.

    • P-384曲線
    ECDSA 384で選択したP-384曲線.WikipediaのP-384曲線は以下のように記述されています.
    P-384 is the elliptic curve currently specified in NSA Suite B Cryptography for the ECDSA and ECDH algorithms. It is a 384 bit curve with characteristic approximately. In binary, this mod is given by 111…1100…0011…11. That is, 288 1s followed by 64 0s followed by 32 1s. The curve is given by the equation y^2 = x^3 - 3x + b where b is given by a certain 384 bit number. 簡単に言えば、この曲線形式はy^2=x^3−3 x+b mod pであり、bおよびqおよび素数次nはECDSAで固定されている.
    したがって,ECDSA 384における鍵生成のいくつかの条件を見出し,上記式から係数a=−3を見ることができ,他のパラメータはコードから見ることができる.コードからB,P,Nはいずれも固定値であり,これはECDSA 384で規定された数であり,暗号学の専門家が制定したものであることがわかる.ここではECDSA 384のことを言っているので、演算に参加するすべての数は384 bitsです.しかし、コンピュータの現在最も長いタイプは64 bitsであるため、64 bitsの配列で記述され、関連する演算も少し面倒である.
    ecc.h 
    #define ECC_CURVE 48

#define Curve_P_48 {0x00000000FFFFFFFF, 0xFFFFFFFF00000000, 0xFFFFFFFFFFFFFFFE, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF}

#define Curve_B_48 {0x2A85C8EDD3EC2AEF, 0xC656398D8A2ED19D, 0x0314088F5013875A, 0x181D9C6EFE814112, 0x988E056BE3F82D19, 0xB3312FA7E23EE7E4}

#define Curve_G_48 { \
    {0x3A545E3872760AB7, 0x5502F25DBF55296C, 0x59F741E082542A38, 0x6E1D3B628BA79B98, 0x8EB1C71EF320AD74, 0xAA87CA22BE8B0537}, \
    {0x7A431D7C90EA0E5F, 0x0A60B1CE1D7E819D, 0xE9DA3113B5F0B8C0, 0xF8F41DBD289A147C, 0x5D9E98BF9292DC29, 0x3617DE4A96262C6F}}

#define Curve_N_48 {0xECEC196ACCC52973, 0x581A0DB248B0A77A, 0xC7634D81F4372DDF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF}

static uint64_t curve_p[NUM_ECC_DIGITS] = CONCAT(Curve_P_, ECC_CURVE);
static uint64_t curve_b[NUM_ECC_DIGITS] = CONCAT(Curve_B_, ECC_CURVE);
static EccPoint curve_G = CONCAT(Curve_G_, ECC_CURVE);
static uint64_t curve_n[NUM_ECC_DIGITS] = CONCAT(Curve_N_, ECC_CURVE);
  • curve_bは楕円曲線の係数b
    • である
  • curve_pは楕円曲線のモジュールp
    • である
  • curve_Gは楕円生成素数次curve_である.nの循環群の点G
    • コード実装
    次に、コード内で鍵ペアがどのように生成されるかを直接見ることができ、そのAPIは
    int ecc_make_key(uint8_t p_publicKey[ECC_BYTES+1], uint8_t p_privateKey[ECC_BYTES])

    p_privateKeyは生成された秘密鍵であり、p_publicKeyは生成された公開鍵である.公開鍵は点Bの座標ではないかと聞かれるが、その点Bにはxとyが必要ではないか、xとyはそれぞれ384ビットなのに、なぜここの公開鍵は384+8ビットなのか.これは主にこのコードの著者らが実現した小さなテクニックであり,実際に座標xによって座標yを算出できるので,ここでは点Bのx座標だけを保存すればよいが,それ以上の8ビットが検証計算の正確性として用いられる.もちろんこれを直接p_publicKeyをp_に設定publicKey[ECC_BYTES*2]は、タスクの圧縮もせず、直接xとy座標を公開鍵に保存します.それでは、x座標でy座標を計算する必要はありません.これは個人的な好みにすぎません.
    int ecc_make_key(uint8_t p_publicKey[ECC_BYTES+1], uint8_t p_privateKey[ECC_BYTES])
{
    uint64_t l_private[NUM_ECC_DIGITS];
    EccPoint l_public;
    unsigned l_tries = 0;

    do
    {
        /*1.      d，   */
        if(!getRandomNumber(l_private) || (l_tries++ >= MAX_TRIES))
        {
            return 0;
        }
        /*1.1         0*/
        if(vli_isZero(l_private))
        {
            continue;
        }

        /*1.2            0 < d < n*/
        /* Make sure the private key is in the range [1, n-1].
           For the supported curves, n is always large enough that we only need to subtract once at most. */
        if(vli_cmp(curve_n, l_private) != 1)
        {
            vli_sub(l_private, l_private, curve_n);
        }
        /*2.  p-384      B=dG*/
        EccPoint_mult(&l_public, &curve_G, l_private, NULL);
    } while(EccPoint_isZero(&l_public));
    /*                        */
    ecc_native2bytes(p_privateKey, l_private);
    /*      B x      p_publicKey[1]     ，p_publicKey[0]     y     */
    ecc_native2bytes(p_publicKey + 1, l_public.x);
    p_publicKey[0] = 2 + (l_public.y[0] & 0x01);
    return 1;
}

    上のコードが列挙されており、中国語の注釈に基づいて説明された生成手順が一つ一つ対応していることがわかります.その中のいくつかの大きい数の演算とEcc曲線の演算は展開しないで、この中はすべてプログラミングの体力が働いて、原理はとても簡単で、しかしコードの実現は比較的に煩雑です.
    2署名
    DSAと同様に、ECDSA署名は、各値のビット長がqと同じである一対の整数(r,s)からなり、非常に簡潔な署名の実現にも役立つ.公開鍵と秘密鍵を用いてメッセージxの署名を計算する方法は、以下の通りである.
  • ランダム一時鍵Keとして整数を選択し、0
  • 計算R=Ke*A
  • r=XR
    • を設定
  • s=(h(x)+d*r)/Kemod qを計算した.

    • ここで、h(x)は署名されるデータのハッシュ値であり、ECDSA 384のハッシュアルゴリズムはSHA 384である.ステップ3では、点Rのx座標が変数rに与えられる.これで署名整数対(r,s)が計算される.だから実は楕円曲線の原理を理解してから、ECDSAを理解するのは簡単で、コードを直接見て、このECDSA署名の流れを直感的に見ることができます.
    署名のインタフェースは以下の通りです.p_privateKeyは署名に使用される秘密鍵であり、p_hashは署名対象データのハッシュ値であり、p_Signatureは計算した署名整数対(r,s),p_を格納する.Signature[0:ECC_BYTES-1]保存r,p_Signature[ECC_BYTES,ECC_BYTES*2-1]sを格納します.
    int ecdsa_sign(const uint8_t p_privateKey[ECC_BYTES], const uint8_t p_hash[ECC_BYTES], uint8_t p_signature[ECC_BYTES*2])

    ランダム一時鍵Keとして整数を選択し、0コードから分かるecdsa_Signは最初から乱数kを生成し,0int ecdsa_sign(const uint8_t p_privateKey[ECC_BYTES], const uint8_t p_hash[ECC_BYTES], uint8_t p_signature[ECC_BYTES*2]) { uint64_t k[NUM_ECC_DIGITS]; uint64_t l_tmp[NUM_ECC_DIGITS]; uint64_t l_s[NUM_ECC_DIGITS]; EccPoint p; unsigned l_tries = 0; do { if(!getRandomNumber(k) || (l_tries++ >= MAX_TRIES)) { return 0; } if(vli_isZero(k)) { continue; } if(vli_cmp(curve_n, k) != 1) { vli_sub(k, k, curve_n); } ...... }
    計算R=Ke*A
    同様に算出した点Rのx座標もqより大きくはならない.
    int ecdsa_sign(const uint8_t p_privateKey[ECC_BYTES], const uint8_t p_hash[ECC_BYTES], uint8_t p_signature[ECC_BYTES*2])
{
        ......
     /* tmp = k * G */
        EccPoint_mult(&p, &curve_G, k, NULL);

        /* r = x1 (mod n) */
        if(vli_cmp(curve_n, p.x) != 1)
        {
            vli_sub(p.x, p.x, curve_n);
        }
        ......
}

    r=Xrの設定
    rを大端バイト配列として署名p_に格納するSignatureの前半
    int ecdsa_sign(const uint8_t p_privateKey[ECC_BYTES], const uint8_t p_hash[ECC_BYTES], uint8_t p_signature[ECC_BYTES*2])
{
        ......
        ecc_native2bytes(p_signature, p.x);
        ......
}

    計算s=(h(x)+d*r)/Kemod q
    原理は簡単だが、計算方法が少し複雑なので、この計算は三つのステップに分かれている.
  • s = (r*d) mod n
  • s = (h(x) + r*d) mod n
  • s = (h(x) + r*d)/k mod n 
    • int ecdsa_sign(const uint8_t p_privateKey[ECC_BYTES], const uint8_t p_hash[ECC_BYTES], uint8_t p_signature[ECC_BYTES*2])
{
    ......
    ecc_bytes2native(l_tmp, p_privateKey);
    vli_modMult(l_s, p.x, l_tmp, curve_n); /* s = (r*d) mod n */
    ecc_bytes2native(l_tmp, p_hash);
    vli_modAdd(l_s, l_tmp, l_s, curve_n); /* s = (h(x) + r*d) mod n */
    vli_modInv(k, k, curve_n); /* k = 1 / k */
    vli_modMult(l_s, l_s, k, curve_n); /* s = (h(x) + r*d) / k mod n */
    ecc_native2bytes(p_signature + ECC_BYTES, l_s);

    return 1;
}

    最終的に算出されたsを署名p_に格納するsignatureの後半.
    3署名検証
    署名検証プロセスは、−補助値W=1/s mod qの計算−補助値u 1=w*h(x)mod qの計算−補助値u 2=w*r mod q−計算P=u 1*A+u 2*B−検証verify(x,(r,s))であり、Pのx座標=r mod qであれば有効な署名であり、そうでなければ無効な署名である.
    検証に関する証明は『暗号学-常用暗号化技術原理及び応用』P 268の証明を参考にすることができる.
    検証されたインタフェースは次のとおりです.-p_publicKeyは、使用する公開鍵、すなわち点Bの座標を検証するものである.-p_hashは検証対象データのハッシュ値です.-p_signatureは署名データです.
    int ecdsa_verify(const uint8_t p_publicKey[ECC_BYTES+1], const uint8_t p_hash[ECC_BYTES], const uint8_t p_signature[ECC_BYTES*2])

    補助値W=1/s mod qの計算
    int ecdsa_verify(const uint8_t p_publicKey[ECC_BYTES+1], const uint8_t p_hash[ECC_BYTES], const uint8_t p_signature[ECC_BYTES*2])
{
    uint64_t u1[NUM_ECC_DIGITS], u2[NUM_ECC_DIGITS];
    uint64_t z[NUM_ECC_DIGITS];
    EccPoint l_public, l_sum;
    uint64_t rx[NUM_ECC_DIGITS];
    uint64_t ry[NUM_ECC_DIGITS];
    uint64_t tx[NUM_ECC_DIGITS];
    uint64_t ty[NUM_ECC_DIGITS];
    uint64_t tz[NUM_ECC_DIGITS];

    uint64_t l_r[NUM_ECC_DIGITS], l_s[NUM_ECC_DIGITS];
    /*     B x      y，         r s*/
    ecc_point_decompress(&l_public, p_publicKey);
    ecc_bytes2native(l_r, p_signature);
    ecc_bytes2native(l_s, p_signature + ECC_BYTES);
    ......
    /* 1.  w = s ^ -1 mod q */
    vli_modInv(z, l_s, curve_n); /* Z = s^-1 */
    .......
}

    補助値u 1=w*h(x)mod qとu 2=w*r mod qの計算
    int ecdsa_verify(const uint8_t p_publicKey[ECC_BYTES+1], const uint8_t p_hash[ECC_BYTES], const uint8_t p_signature[ECC_BYTES*2])
{
    ......
    ecc_bytes2native(u1, p_hash);
    vli_modMult(u1, u1, z, curve_n); /* u1 = w * h(x) mod q = h(x) / s mod q */
    vli_modMult(u2, l_r, z, curve_n); /* u2 = w * r mod q= r / s mod q */
    ......
}

    計算P=u 1*A+u 2*B
    この中の計算コードの上で実現するのは少し煩雑で、主に大数演算と楕円曲線の演算で、一つ一つ展開しないで、最終的に計算した点Pのx座標とy座標をrxとryのこの2つの変数の中に保存します.
    int ecdsa_verify(const uint8_t p_publicKey[ECC_BYTES+1], const uint8_t p_hash[ECC_BYTES], const uint8_t p_signature[ECC_BYTES*2])
{
    ......
        /* Calculate l_sum = G + Q. */
    vli_set(l_sum.x, l_public.x);
    vli_set(l_sum.y, l_public.y);
    vli_set(tx, curve_G.x);
    vli_set(ty, curve_G.y);
    vli_modSub(z, l_sum.x, tx, curve_p); /* Z = x2 - x1 */
    XYcZ_add(tx, ty, l_sum.x, l_sum.y);
    vli_modInv(z, z, curve_p); /* Z = 1/Z */
    apply_z(l_sum.x, l_sum.y, z);

    /* Use Shamir's trick to calculate u1*G + u2*Q */
    EccPoint *l_points[4] = {NULL, &curve_G, &l_public, &l_sum};
    uint l_numBits = umax(vli_numBits(u1), vli_numBits(u2));

    EccPoint *l_point = l_points[(!!vli_testBit(u1, l_numBits-1)) | ((!!vli_testBit(u2, l_numBits-1)) << 1)];
    vli_set(rx, l_point->x);
    vli_set(ry, l_point->y);
    vli_clear(z);
    z[0] = 1;

    int i;
    for(i = l_numBits - 2; i >= 0; --i)
    {
        EccPoint_double_jacobian(rx, ry, z);

        int l_index = (!!vli_testBit(u1, i)) | ((!!vli_testBit(u2, i)) << 1);
        EccPoint *l_point = l_points[l_index];
        if(l_point)
        {
            vli_set(tx, l_point->x);
            vli_set(ty, l_point->y);
            apply_z(tx, ty, z);
            vli_modSub(tz, rx, tx, curve_p); /* Z = x2 - x1 */
            XYcZ_add(tx, ty, rx, ry);
            vli_modMult_fast(z, z, tz);
        }
    }

    vli_modInv(z, z, curve_p); /* Z = 1/Z */
    apply_z(rx, ry, z);
    ......
}

    verify(x,(r,s))を検証し,Pのx座標=r mod qであれば有効な署名であり,そうでなければ無効な署名である.
    最終的に計算された点Pのx座標が署名中のrと同じか否かを比較して署名が成功したか否かを判断する.
    int ecdsa_verify(const uint8_t p_publicKey[ECC_BYTES+1], const uint8_t p_hash[ECC_BYTES], const uint8_t p_signature[ECC_BYTES
    ......
    /* Accept only if v == r. */
    return (vli_cmp(rx, l_r) == 0);
}

    適用
    hashシミュレーションのデータのハッシュ値を定義します.まず鍵ペアを作成し、それぞれ検証に署名します.main.c 
      1 #include "ecc.h"
  2 #include 
  3 #include 
  4 #include 
  5
  6 int main()
  7 {
  8     uint8_t public_key[ECC_BYTES + 1];
  9     uint8_t private_key[ECC_BYTES];
 10     uint8_t hash[ECC_BYTES] = {0x2};
 11     uint8_t signature[ECC_BYTES * 2];
 12     uint32_t i = 0;
 13     int ret = 0;
 14
 15     ret = ecc_make_key(public_key, private_key);
 16     if (ret == 0) {
 17         printf("ecc_make_key failure
    "    );
 18     }
 19
 20     printf("##############public key###############
    "    );
 21     for (i = 0;i < ECC_BYTES + 1;i++) {
 22         printf("%x ", public_key[i]);
 23     }
 24
 25     printf("

    "    );
 26     printf("##############private key###############
    "    );
 27     for (i = 0;i < ECC_BYTES;i++) {
 28         printf("%x ", private_key[i]);
 29     }
 30     printf("

    "    );
 31
 32     ret = ecdsa_sign(private_key, hash, signature);
 33     if (ret == 0) {
 34         printf("ecdsa_sign failure
    "    );
 35     }
 36
 37     ret = ecdsa_verify(public_key, hash, signature);
 38     if (ret == 1) {
 39         printf("verify passed
    "    );
 40     } else {
 41         printf("verify failed
    "    );
 42     }
 43
 44     return 0;
 45 }

    実行結果
    ############secret key#############
662eea0239ee28f 62693fced7eb10f1 3dd1e1815fe2e2b6 af68ec328b437369 737206cce4206de3 7650b5ce554851b6

##############public key###############
2 8a 5c c7 24 28 ae 49 da c1 8 e7 a8 80 8a fd 5f ef a 79 ca d9 57 bf cc f9 92 98 85 5f 68 c4 5a 77 e2 2 d1 56 e4 4f 1d c5 94 1c bb 62 8e 2b a2

##############private key###############
76 50 b5 ce 55 48 51 b6 73 72 6 cc e4 20 6d e3 af 68 ec 32 8b 43 73 69 3d d1 e1 81 5f e2 e2 b6 62 69 3f ce d7 eb 10 f1 6 62 ee a0 23 9e e2 8f

l_read:48, l_left:48
verify passed

    データを改ざんした場合、検証に失敗します.ここでは、ハッシュ値を変更することでデータ改ざんをシミュレートできます.データが変化すると、対応するハッシュ値が変化するはずです.main関数を変更すると、署名を検証する前にデータを改ざんします.
     37     hash[0] = 0x3;
 38     ret = ecdsa_verify(public_key, hash, signature);
 39     if (ret == 1) {
 40         printf("verify passed
    "    );
 41     } else {
 42         printf("verify failed
    "    );
 43     }
 44
 45     return 0;
 46 }

    さらに実行すると、認証署名に失敗したことがわかります.
    ############secret key#############
4f512226dd0a47e3 e7c9bc62fd8f37e6 f200140c350bb743 7fa11d17b04448fb aa4b146001ab1143 b132949e3715217c

##############public key###############
2 ea cb d1 46 84 60 89 2f cb c9 6 d8 da 9a 1d b4 21 7d 17 2 e4 b5 2b 6 58 d9 e8 75 e2 4b ae 30 84 7c 70 cf 41 7 fe 8c f4 d2 a8 37 50 e1 4 92

##############private key###############
b1 32 94 9e 37 15 21 7c aa 4b 14 60 1 ab 11 43 7f a1 1d 17 b0 44 48 fb f2 0 14 c 35 b b7 43 e7 c9 bc 62 fd 8f 37 e6 4f 51 22 26 dd a 47 e3

l_read:48, l_left:48
verify failed
    利用環境変数LD_PRELAADはphp disableを迂回するfunction実行システムコマンド
    自分用メモ