2023年7月27日发(作者：)

ECDSA签名验证原理及C语⾔实现这两天总算把ECDSA搞明⽩了，本来想造个ECDSA轮⼦，但最近有点忙，⽽ECDSA轮⼦⼜不像HASH那样简单，所以就直接拿现成的轮⼦来记录⼀些ECDSA学习⼼得。这⾥贴上github上⼀个⽐较适合学习的ECDSA代码，当然这个版本的代码没有openssl等商业级的代码专业，但是它⾜够简单，⽤来学习ECDSA原理⾮常合适。⾮对称加密算法签名/验证⽆⾮包括三步：1. 密钥⽣成keygen2. 签名sign3. 验证verify后⽂都以ECDSA384为例。#1 密钥⽣成密钥⽣成其实主要涉及椭圆曲线ECC的⼀些原理，在这篇⼩记⾥，就不再赘述原理，⽹上讲原理的⽂章⾮常多。我当时也是看了以下这篇⽂章算是⼊门ECC原理。⾮常好的⼀篇⽂章，分享给各位朋友。椭圆曲线定义从上⽂中我们就可以知道椭圆的通式为y^2 = x^3 + a*x + b mod p 以及⼀个⽆穷⼤的数0，当然最正宗的定义还有限定条件，该曲线是在有限域上的，并且a，b和q之间也存在关系。ECDSA的密钥的计算⽅式1. 使⽤椭圆曲线E， 其中模数为p系数为a和b⽣成素数阶n的循环群的点G2. 选择⼀个随机整数d，且0 < d < q。3. 计算B=dG其中d就是ECSDA的私钥，⽽点B(x，y)就是ECDSA的公钥。P-384曲线ECDSA384选⽤的P-384曲线。维基百科对P-384曲线描述如下：P-384 is the elliptic curve currently specified in NSA Suite B Cryptography for the ECDSA and ECDH algorithms. It is a 384bit curve with characteristic approximately. In binary, this mod is given by 111…1100…0011…11. That is, 288 1s followedby 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 bitnumber.简⽽⾔之，这条曲线形式就是y^2 = x^3 - 3x + b mod p，⽽b和q以及素数阶n在ECDSA中都是固定的。所以ECDSA384中密钥⽣成的⼀些条件我们都找到了，从上述式⼦中可以看到系数a=-3， 其他的参数我们从代码中看。从代码中可以看到B，P和N都是⼀些固定值，这个是ECDSA384所规定的数，都是密码学专家制定的。因为这⾥讲的是ECDSA384，所以所有参与运算的数都是384 bits。但由于计算机现在最长的类型就是64bits，所以⼀个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就是椭圆曲线的系数bcurve_p就是椭圆曲线的模数pcurve_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签名由⼀对整数(r, s)组成，其中每个值的位长度都与q相同，这也有助于实现⼗分简洁的签名。使⽤公钥和私钥计算消息x的签名的⽅式如下选择⼀个整数作为随机临时密钥Ke， 且0 < Ke < n。计算R = Ke * A设置r = Xr计算s = (h(x) + d * r)/Ke mod q。其中h(x)是待签名的数据的哈希值，ECDSA384的哈希算法是SHA384。在步骤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 < Ke < n。从代码中可以看到， ecdsa_sign⼀开始就⽣成⼀个随机数k，并且必须满⾜0 < k < 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]){ 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)/Ke mod q原理很简单，但由于计算⽅法稍微复杂⼀点这个计算分成三步⾛s = (r*d) mod ns = (h(x) + r*d) mod ns = (h(x) + r*d) / k mod nint 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计算辅助值u1 = w * h(x) mod q计算辅助值u2 = w * r mod q计算P = u1 * A + u2 * B验证verify(x, (r, s)), 如果P的x坐标 = r mod q，那么就是有效的签名，否则就是⽆效的签名。关于验证的证明可以参考《深⼊浅出密码学-常⽤加密技术原理及应⽤》P268的证明。验证的接⼝如下: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 qint 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 */ .......}计算辅助值u1 = w * h(x) mod q 和 u2 = w * r mod qint 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 = u1 * A + u2 * B这⾥⾯的计算代码上实现有点繁琐，主要是⼤数运算和椭圆曲线的运算，就不⼀⼀展开了，最终就是将计算出来的点P的x坐标和y坐标存放到rx和ry这两个变量中。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 failuren"); 18 } 19 20 printf("##############public key###############n"); 21 for (i = 0;i < ECC_BYTES + 1;i++) { 22 printf("%x ", public_key[i]); 23 } 24 25 printf("nn"); 26 printf("##############private key###############n"); 27 for (i = 0;i < ECC_BYTES;i++) { 28 printf("%x ", private_key[i]); 29 } 30 printf("nn"); 31 32 ret = ecdsa_sign(private_key, hash, signature); 33 if (ret == 0) { 34 printf("ecdsa_sign failuren"); 35 } 36 37 ret = ecdsa_verify(public_key, hash, signature); 38 if (ret == 1) { 39 printf("verify passedn"); 40 } else { 41 printf("verify failedn"); 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 8fl_read:48, l_left:48verify passed假如我们篡改了数据，那么验证就会失败，这⾥可以通过修改哈希值来模拟数据篡改，应该当数据⼀旦发⽣变化，其相应的哈希值就会发⽣变化。修改main函数如下，在验证签名之前篡改数据。 37 hash[0] = 0x3; 38 ret = ecdsa_verify(public_key, hash, signature); 39 if (ret == 1) { 40 printf("verify passedn"); 41 } else { 42 printf("verify failedn"); 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 e3l_read:48, l_left:48verify failed