纯C语言实现ECDSA签名验签：无依赖椭圆曲线密码学实战

简介本资源是一份轻量级ECDSA椭圆曲线数字签名算法的C语言实现面向嵌入式开发、物联网安全及密码学初学者解决资源受限环境下高效实现数字签名与验证的核心需求。压缩包共2个文件1个C源码文件 1个头文件总大小仅7KB结构精简.c文件封装了椭圆曲线参数初始化、私钥生成、签名计算r/s生成与验证逻辑等完整流程.h文件提供标准化接口如ecdsa_sign()和ecdsa_verify()便于快速集成到现有C项目中。目前已有943人学习下载适合需要在裸机或RTOS环境中部署基础密码功能的开发者。读者可直接编译调用掌握ECDSA在真实硬件上的工程落地要点包括随机数安全性处理、模运算优化及签名防重放等关键实践细节。 最近在整理手头的代码工程翻出一个用纯C语言写的ECDSA签名验签实现。说实话网上关于ECDSA的教程一搜一大把但大多数要么是OpenSSL命令行的简单调用要么是Python里几行代码跑通示例真正用C语言从零实现整个算法流程的完整资料并不算多。很多做嵌入式、做安全网关、做区块链底层开发的朋友恰恰最需要的就是这种能在没有第三方库的环境下跑起来的版本。所以今天我把整个工程的设计思路、模块拆解、关键算法实现以及开发和调试过程中踩过的坑完整梳理一遍希望能给同样在搞C语言密码学实现的朋友一些参考。这个工程实现的是标准ECDSA椭圆曲线数字签名算法支持密钥生成、签名、验签三件事曲线用的是secp256k1哈希部分自己实现了一个SHA-256整个包没有任何外部依赖拿到任何支持C99的编译器上都能编过。如果你正在学习密码学底层实现或者需要在嵌入式环境里做数字签名这篇内容应该能帮你省不少事。1. ECDSA在C语言里到底难在哪先理清原理再动手1.1 椭圆曲线签名算法的核心逻辑先说清楚ECDSA在做什么。数字签名要解决的问题很简单怎么让接收方确认一段数据确实来自声称的发送方并且没有被篡改过。ECDSA就是基于椭圆曲线的数学结构来完成这个认证过程的。它跟RSA最大的区别在于同样安全强度下ECDSA的密钥长度短得多256位椭圆曲线提供的安全性大致相当于3072位RSA这在嵌入式设备、物联网固件签名这种资源受限的场景里优势非常明显。ECDSA的数学基础是椭圆曲线离散对数问题ECDLP。对于一个定义在有限域上的椭圆曲线已知基点G和私钥d求公钥Q dG是容易的但从Q和G反推d在计算上不可行这就是整个算法安全性的支点。签名和验签的核心流程是这样的签名方持有私钥d对待签消息的哈希值z选择一个随机数k计算点R kG取R的x坐标作为r再计算s k⁻¹(z r·d) mod n签名结果就是(r, s)。验签方持有公钥Q计算w s⁻¹ mod nu1 z·w mod nu2 r·w mod n然后计算点P u1G u2Q最后检查P的x坐标模n是否等于r。这里面n是基点G的阶一个很大的素数。如果把验签公式做代数化简你会发现u1G u2Q (zw rwd)G w(z rd)G w·s·k·G kG而kG的x坐标就是r所以验签成立。这个数学上的闭环是整个算法能工作的根本原因。理解了这个逻辑你才能真正看懂C语言代码里的每一个步骤在干什么。我见过太多人拿着现成代码改改就用一旦遇到验签失败就完全不知道怎么排查根源就是没有把这条数学链路在脑子里打通。后续所有的实现都是围绕这条链路展开的。1.2 为什么我要写一个无依赖的C语言版本可能有人会问OpenSSL明明提供了完整且经过安全审计的ECDSA实现为什么还要自己用C语言写一遍这里要分场景看。我的情况是目标运行环境是一个裁剪过的嵌入式Linux系统整个系统里只有busybox和基础C库不可能装OpenSSL更不可能装GMP这种大数库。在这种场景下要么把OpenSSL交叉编译进去体积和依赖都是问题要么自己实现最小可用的密码学库。另一方面从学习角度讲把ECDSA完整捋一遍对理解椭圆曲线密码学、大数运算、安全编码这些问题帮助极大远比直接调API收获多。纯C语言实现ECDSA核心难点有三个。第一是大数运算。ECDSA用到的曲线参数都是256位的大整数C语言原生类型根本装不下必须自己实现大整数的加减乘除、模运算、模逆、模幂。这一层是地基地基不牢后面全是坑。第二是椭圆曲线点运算。包括点加、点倍、标量乘法还要处理无穷远点、坐标的模运算、不同坐标系之间的转换。这些运算看起来公式简单实际写出来要考虑大量边界情况。第三是安全细节。密码学代码跟普通业务代码不一样不光要能跑还要跑得安全。随机数质量、时序侧信道、错误处理时泄露的中间信息每一项都可能成为攻击入口。虽然初学者写的东西不会真的上生产环境对抗国家级攻击者但养成这个意识非常重要。我把工程拆成了几个相对独立的模块大数运算模块、有限域运算模块、椭圆曲线点运算模块、ECDSA签名验签模块、SHA-256哈希模块。每个模块只暴露少量接口模块之间通过结构体传递数据这样单测和排错都很方便。下面逐个拆开讲。2. 大数运算模块256位整数是绕不过去的第一道坎2.1 用四个uint64_t表示256位大数大数运算的第一步是确定数据表示方案。我采用的是最直白的方式用一个包含4个uint64_t元素的数组表示256位整数数组下标0对应最低64位下标3对应最高64位也就是小端序的limb表示。typedef struct { uint64_t limb[4]; } bignum256;为什么用64位做基本单元而不是32位因为在64位平台上两个uint64_t相乘可以得到128位的结果现代编译器在x86_64架构下会直接用mulq指令生成64x64-128的乘法效率很高。如果拆成32位单次乘法只能利用到64位结果同样的运算要多一倍的步骤。这里还有个实现细节值得说一下做乘法时a[i] * b[j]的结果可能溢出64位需要用__int128这个GCC扩展来承接中间结果。如果你的编译环境不支持__int128那就只能降级成32位limb或者用拆半法手动处理进位性能和代码复杂度都会明显上升。我用的是GCC/Clang工具链所以直接用__int128来简化实现。static void bignum_mul_limb(const bignum256 *a, uint64_t b, bignum256 *out) { unsigned __int128 t 0; for (int i 0; i 4; i) { t (unsigned __int128)a-limb[i] * b; out-limb[i] (uint64_t)t; t 64; } // 注意这里t可能还有值需要处理第5个limb的溢出 }这个函数是乘以单个limb的辅助操作大数乘法会反复调用它。我在开发初期犯过的一个典型错误是忽略了最后那个进位导致乘法结果偶尔少一小截单测数据量不够多的时候根本发现不了后来用随机数据做大规模对比测试才抓到。2.2 加减乘除与模逆运算的工程实现大数加法和减法比较直接就是逐limb运算加法要传递进位减法要传递借位。乘法用经典的竖式算法两层循环把a的每个limb和b的每个limb相乘累加到对应位置上。这个算法的时间复杂度是O(n²)n这里是4所以性能不是问题。麻烦的是取模和模逆。取模运算分两种情况。一种是模p椭圆曲线域参数因为secp256k1的p非常接近2的幂可以用专门的优化方法来快速归约这里先不展开。另一种是模n基点阶我直接用了大数除法求余数的方式虽然比专门优化的慢一些但胜在代码简单、正确性容易验证。模逆运算是ECDSA里最频繁也最容易出错的地方。求a模p的逆元意思就是找一个数x使得a·x mod p 1。我采用的是扩展欧几里得算法通过迭代计算最大公约数的同时把系数也求出来。// 返回 a 在模 p 下的逆元要求 gcd(a, p) 1 void bignum_inv(const bignum256 *a, const bignum256 *p, bignum256 *out) { bignum256 r0 *p, r1 *a; bignum256 t0 {0}, t1 {1}; while (!bignum_is_zero(r1)) { bignum256 q, r; bignum_div(r0, r1, q, r); // r0 q * r1 r // (r0, r1) (r1, r) bignum256 tmp r0; r0 r1; r1 r; // (t0, t1) (t1, t0 - q * t1) bignum256 t2; bignum_mul(q, t1, t2); bignum_sub(t0, t2, t2); t0 t1; t1 t2; } if (bignum_cmp(r0, one) ! 0) { // 逆元不存在 return; } while (bignum_is_negative(t0)) { bignum_add(t0, p, t0); } *out t0; }上面这个伪代码隐藏了大数比较、减法、除法等一堆细节真实实现里每个操作都要处理进位、借位、符号位加起来大概几百行。我特别提醒一点扩展欧几里得迭代过程中中间结果可能变成负数所以必须有一个清晰的符号处理方案。我的做法是让大数用一个额外的int字段记录符号位运算函数统一按有符号大数来处理等结果落到模运算时再确保转为非负。另一种取模逆元的方法是费马小定理因为p是素数所以a^(p-2) mod p等于a的逆元。这个方法的好处是代码逻辑简单只需要实现模幂函数但代价是运算量大得多要执行几百次平方乘速度大约是扩展欧几里得的几十倍。在实际签名验签这种高频场景下不划算我在工程里选择了扩展欧几里得。2.3 大数模块的交叉验证方法大数模块是整个ECDSA实现里最容易藏bug的地方而且这类bug往往很隐蔽可能在特定数值组合下才触发。我的做法是把大数模块单独拎出来做大规模随机测试。具体方法是写了一个测试程序循环生成随机的256位整数分别调用我实现的大数加减乘除、模逆函数然后把同样的计算交给Python的int类型来完成逐项对比结果。Python的int是任意精度的标准库也足够可靠拿它当参照物可以省掉很多人工验证的时间。# 这是测试脚本的思路不是完整代码 import random p 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F for _ in range(100000): a random.getrandbits(256) inv_a pow(a, p-2, p) # 用费马小定理求模逆作为参照 # 然后把a传给C程序的test_inv函数比较结果这个测试帮我抓到了两个非常隐蔽的问题。一个是模逆函数在特定输入下会多减一次模导致结果为负另一个是大数乘法在某些进位组合下中间结果的128位累加会溢出。这类问题靠手写测试用例几乎不可能覆盖到必须靠大规模随机数据来压测。所以我强烈建议任何一个C语言大数库第一步就是建立这样的自动化对比测试否则后续做椭圆曲线点运算时会让你排查到怀疑人生。3. 椭圆曲线点运算点加、点倍与标量乘法3.1 secp256k1域参数与坐标选择点运算模块建立在有限域的运算基础之上。我选的是secp256k1曲线就是比特币和以太坊用的那条。选它有几个原因参数形式简单a 0b 7这样点加和点倍的公式可以省掉不少乘法项生态成熟各种测试向量和参考数据好找而且网上资料多做交叉验证方便。参数值pFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2Fa0b7Gx79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798Gy483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8nFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141坐标表示上有两种常见选择仿射坐标和雅可比坐标。仿射坐标就是直接用(x, y)表示点公式直观但点加和点倍每次都要做模逆运算而模逆是最慢的大数运算。雅可比坐标用(X, Y, Z)三个元素表示点实际坐标是(X/Z², Y/Z³)这样点加和点倍可以完全避免模逆只在最后需要输出仿射坐标时才做一次模逆。性能差距非常可观。我工程里的做法是内部运算统一用雅可比坐标只有对外接口比如返回公钥坐标、签名时的r值计算才转换回仿射坐标。转换公式很简单x X·Z⁻² mod py Y·Z⁻³ mod p。3.2 仿射坐标下的点加/点倍公式虽然实际运算用雅可比坐标但理解算法的捷径是先看仿射坐标下的公式这样逻辑最清晰。给定两个不同的点P (x1, y1)和Q (x2, y2)且P ≠ -Q点加R P Q的结果是λ (y2 - y1) / (x2 - x1) mod px3 λ² - x1 - x2 mod py3 λ(x1 - x3) - y1 mod p如果P Q点倍公式变成λ (3x1² a) / (2y1) mod px3 λ² - 2x1 mod py3 λ(x1 - x3) - y1 mod p这里除法是模逆的意思。可以直观理解为椭圆曲线上的点构成了一个群点加就是群运算点倍就是自己加自己而标量乘法dG就是重复的点加过程。实现时最容易遗漏的是特殊情形处理。当P -Q时两个点互为y轴对称结果应该是无穷远点当P或Q是无穷远点时结果就是另一个点点倍时如果y1 0结果也是无穷远点。这些边界条件缺一个后面签名验签就会出现莫名其妙的失败而且因为不常见调试起来特别费劲。3.3 标量乘法的窗口优化标量乘法kG是ECDSA里最核心也最耗时的运算。最直白的做法是二进制展开从低位到高位扫描k的每一位每一轮对结果做点倍遇到位为1就额外做一次点加。这就是经典的Double-and-Add算法。// 伪代码计算 k * P point result INFINITY; while (k 0) { if (k 1) { result point_add(result, P); } P point_double(P); k 1; }这个算法平均需要约256次点倍和128次点加在雅可比坐标下已经很快了但还可以优化。我额外做了一层4-bit窗口预计算把P的1倍到15倍提前算好存起来然后标量k每4位查一次表直接把相应倍数加进去。这样点加次数从平均128次降到约64次整体性能提升明显。窗口法的代价是预计算需要额外的内存和启动时间但公钥通常是固定的预计算结果可以复用。我的工程里在验签前会对公钥做一次预计算后面多次验签性能就上来了。不过要注意如果签名和验签发生在随机性很强的嵌入式平台上内存受限窗口大小要缩减到2-bit甚至1-bit这是个取舍问题。4. 签名与验签全流程实现4.1 密钥生成与签名过程密钥生成很简单在[1, n-1]范围内选一个随机数作为私钥d然后计算公钥Q dG。随机数的质量是关键如果随机源可预测整个签名体系就废了。Linux环境下我用了/dev/urandom嵌入式环境如果有硬件随机数发生器优先用硬件源。签名过程的代码骨架大致是这样int ecdsa_sign(const uint8_t msg_hash[32], const bignum256 *privkey, bignum256 *r, bignum256 *s) { bignum256 z {0}, k, k_inv, tmp; bignum256_digest_to_bignum(msg_hash, z); // 哈希值转大数 // 选择一个安全的随机数 k bignum256_random_range(k, one, n_minus_1); // 计算 R kG point R; point_scalar_mul(G, k, R); // r R.x mod n *r R.x; bignum_mod(r, n, r); if (bignum_is_zero(r)) { return ECDSA_ERR_RETRY; // r0需要重新选k } // s k^{-1} * (z r*d) mod n bignum_inv(k, n, k_inv); bignum_mul(r, privkey, tmp); bignum_add(z, tmp, tmp); bignum_mod(tmp, n, tmp); bignum_mul(k_inv, tmp, s); bignum_mod(s, n, s); if (bignum_is_zero(s)) { return ECDSA_ERR_RETRY; } return ECDSA_OK; }随机数k有个著名的安全性原则同一个私钥下k值绝对不能重复使用。如果两次签名用了同一个k攻击者可以直接恢复出私钥。经典推导是两个签名消息分别是z1和z2都有 (r, s1) 和 (r, s2)因为r kG的x坐标k相同则r相同于是 (s1 - s2) k⁻¹(z1 - z2) mod n从而可以解出k再代入 s k⁻¹(z rd) 解出d。这个攻击只需要最基本的代数运算所以k的随机性跟私钥本身一样重要。为了避免随机数发生器出问题导致k重用现代实现普遍采用RFC 6979标准用HMAC-DRBG从私钥和消息哈希派生一个确定性的k。这样同样的消息用同样的私钥签名结果是一致的不依赖外部随机源彻底杜绝了k重用问题。我的工程里在主流程之外也实现了一个RFC 6979的可选模块生产环境建议开启。4.2 验签流程与边界检查验签是签名的逆过程核心代码框架如下int ecdsa_verify(const uint8_t msg_hash[32], const point *pubkey, const bignum256 *r, const bignum256 *s) { // 边界检查r 和 s 必须在 [1, n-1] 范围内 if (bignum_is_zero(r) || bignum_is_zero(s)) return ECDSA_ERR_INVALID; if (bignum_cmp(r, n) 0 || bignum_cmp(s, n) 0) return ECDSA_ERR_INVALID; // 检查公钥是否在曲线上 if (!point_is_on_curve(pubkey)) return ECDSA_ERR_INVALID; bignum256 w, u1, u2; bignum_inv(s, n, w); // w s^{-1} mod n bignum256 z; bignum256_digest_to_bignum(msg_hash, z); bignum_mul(z, w, u1); bignum_mod(u1, n, u1); // u1 z*w mod n bignum_mul(r, w, u2); bignum_mod(u2, n, u2); // u2 r*w mod n point P; point_scalar_mul(G, u1, P); point tmp; point_scalar_mul(pubkey, u2, tmp); point_add(P, tmp, P); // P u1G u2Q if (point_is_infinity(P)) return ECDSA_ERR_INVALID; bignum256 v P.x; bignum_mod(v, n, v); return bignum_cmp(v, r) 0 ? ECDSA_OK : ECDSA_ERR_SIGNATURE; }这里有一个很多初学者容易忽略的地方在验签之前必须先检查公钥是否在椭圆曲线上。如果一个恶意公钥不在曲线上验签过程可能会被用于发起无效曲线攻击诱导签名方泄露私钥信息。点是否在曲线上很好判断把x代入方程y² x³ ax b看得到的值是否是某个数的平方即可。我的工程里point_is_on_curve函数做了这件事。另外签名和验签过程中需要用到消息的哈希值。标准ECDSA没有规定具体哈希算法但通常搭配SHA-256。工程里我自己实现了SHA-256输入任意长度消息输出32字节摘要然后在签名前转成大数。这里要注意的是如果消息摘要的比特长度大于n的比特长度常见于SHA-384/SHA-512搭配256位曲线需要截断到n的比特长度我的实现里用了一个辅助函数来处理这个截断逻辑。4.3 DER编码输出与字节序处理签名完成后r和s是两个256位的大数对外输出时有两种常用格式一种是原始的r||s拼接各32字节一共64字节另一种是DER编码这是X.509证书和多数密码学库包括OpenSSL的标准格式。DER编码的签名是一个SEQUENCE结构里面包含两个INTEGER先写0x30表示SEQUENCE再写总长度然后写0x02表示INTEGER以及r的长度和数据最后写0x02表示INTEGER以及s的长度和数据。注意每个INTEGER如果最高位字节大于0x80需要前面补一个0x00字节避免被解析成负数。字节序是另一个坑。ECDSA的数学运算全部是模大整数的运算大整数在不同平台上有大端和小端的表示差异。我的内部大数limb用的是小端序但对外输出密钥、签名、公钥坐标统一用大端序。这个转换过程非常容易出错我的做法是在模块的边界上集中处理从外部读入的字节先转成内部limb表示输出时统一转回大端字节数组内部其他模块一律不碰字节序问题。// 大数转大端字节数组 void bignum_to_be_bytes(const bignum256 *a, uint8_t out[32]) { for (int i 0; i 4; i) { uint64_t limb a-limb[3 - i]; for (int j 0; j 8; j) { out[i * 8 j] (limb (56 - j * 8)) 0xFF; } } }5. 工程化踩坑实录这些问题你早晚会遇到5.1 常见编译与运行错误速查表开发过程中我整理了一份问题清单基本都是我自己踩过的按症状、原因、解决方案列在下面症状常见原因解决方案验签偶发失败大数模逆运算出错特定输入触发用Python参照做大规模随机测试定位边界输入生成签名两次结果相同随机k未正确更新或随机源退化改用RFC 6979确定性k签名验签结果恒失败公钥未做曲线上点校验验签前调用point_is_on_curve内存越界崩溃大数数组未清零或limb索引越界每次分配后memset开启AddressSanitizer编译报__int128未定义交叉编译工具链不支持降级为32位limb实现输出到网络端的签名无法被OpenSSL解析DER编码缺少前导0x00字节按DER规范补前导零性能极慢仿射坐标点运算频繁模逆改用雅可比坐标实现内部运算其中内存越界这个问题我印象最深。有一版代码在处理公钥预计算表的时候窗口大小设置成4预计算数组是15个点结果初始化循环里写成了for (i 0; i 15; i)多写了一个元素越界写入了16号位置。这个bug平时跑不崩但在某些内存布局下会悄悄覆盖别的变量表现成签名结果时对时不对排查了整整一个下午。后来用Valgrind和AddressSanitizer跑一遍才定位到。所以调试这类底层代码我的习惯是开国-fsanitizeaddress,undefined编译选项配合-Wall -Wextra -Wpedantic把编译警告也当成错误处理。这条建议对任何C语言项目都适用尤其是密码学代码一个小小未定义行为在安全场景下可能就是致命的。5.2 安全坑位k值重用与随机数质量前面提到过k重用攻击这里单独拿出来说因为这是ECDSA实现中最经典也最容易被忽视的安全问题。我见过不止一个开源项目的草稿版本直接用rand()生成k或者用time(NULL)做随机种子这在密码学上等于裸奔。k重用攻击的公式并不复杂。假如同一把私钥签了两个不同的消息哈希值分别是z1和z2而两次签名错误地用了同一个k那么两个签名共享同一个r因为r只依赖kG这时候攻击者手上有(r, s1)和(r, s2)可以这样恢复k因为 s1 - s2 ≡ k⁻¹(z1 - z2) mod n所以 k ≡ (z1 - z2) / (s1 - s2) mod n拿到k之后代入 s1 ≡ k⁻¹(z1 r·d) mod n直接解出 d ≡ (s1·k - z1) / r mod n整个攻击过程用Python写不到十行。而且这种攻击不是理论上的2010年索尼PS3的ECDSA签名就被研究人员用类似方式破解了原因是Sony在签名时使用了固定的k值。这个案例在密码学界几乎是必讲的教材。除了k重用随机数发生器本身也可能出问题。如果系统熵不足很多嵌入式设备刚上电时熵池几乎是空的生成的随机数可能集中在某个范围甚至出现大量重复。我的工程里有几个应对措施签名前强制读取足够长度的随机源并对生成的k做范围检查如果是0或者接近0就重新生成同时把RFC 6979作为默认方案因为确定性k不依赖系统熵池更稳。另一个安全细节是错误处理。签名验签失败时不要返回过于详细的错误码。举个例子如果验签失败返回坐标不在曲线上和签名不匹配两种不同错误攻击者就可以通过观察错误码来获取公钥的额外信息辅助实施无效曲线攻击。正确的做法是对外统一返回一个验签失败具体原因只记录在日志里供内部排查。5.3 我的几条实操心得整个工程从零到跑通再到通过自测和交叉验证前后花了大半个月。回头总结有几条心得特别想分享。第一一定要先搭好测试框架再写实现或者至少并行推进。我一开始图省事随便写了几个测试用例就开始写点运算结果后面出了问题根本分不清是大数运算错了、点运算错了还是主流程逻辑错了。后来老老实实把大数模块单独抽出来做随机对比测试点运算用已知测试向量验证主流程再跟Python的ecdsa库做双向验证问题定位效率提升了不止一个量级。第二调试密码学代码要从最小案例入手。我遇到一个点加结果不符的问题直接把secp256k1的参数换成一条小曲线比如p 23这样的小素数然后用纸笔算一遍点加再用代码跑一遍立刻就能暴露公式实现的问题。小参数调试完之后再切回真实曲线跑向量测试。第三版本管理要勤快。这类代码经常出现改了一个bug引入两个新bug的情况没有完善的git历史你会非常被动。我每个模块完成一个小目标就提交一次commit message写清楚改动内容回滚和定位都方便很多。最后再分享一个小技巧做ECDSA交叉验证时不要只依赖一个参考实现。我用Python的ecdsa库、OpenSSL命令行、以及官方测试向量三个来源互相印证三者结果一致才敢说实现是对的。这个习惯帮我在后续扩展SM2算法时也省了很多力气因为在同一套代码体系上做第二套算法时很多基础模块是可以复用的而只要基础模块够可靠扩展新算法就只是公式翻译成代码的工作量了。本文还有配套的精品资源点击获取