【零依赖实现国密算法C语言版】国密SM2之大数模加
约 799 字大约 3 分钟
2023-05-13
加法进位
先看0xFF + 0xFF应该等于多少，多少个字节能表示，0xFF为一字节，一字节能表示的最大数，两个这样的数相加的结果为0x1FE，进一位。
同理4字节能表示的最大数是0xFFFFFFFF，两个这样的数相加为0x1FFFFFFFE，uint64_t完全可以表示，并且心可以放进肚子，完全不会溢出。
也就是说8个uint64_t所表示的256-bit大数，执行一次加法，完全不用担心会溢出，不用考虑循环多次加法，因为素域的加法，无论加多少次，结果都不会超过该域。
大数加法
大数的加法实现比较简单，就是8个数循环相加，并且处理进位即可。从数组索引0开始，因为0存放的是大数的低位。
函数定义
// r = a + b
static void gm_i_bn_add(gm_bn_t r, const gm_bn_t a, const gm_bn_t b);先看第一轮：
r[0] = a[0] + b[0];有可能会产生进位，也有可能不会产生进位，那么下一轮相加时，应该要加上前一轮可能产生的进位，同时要将前一轮的进位清除掉。
r[1] = a[1] + b[1] + 进位;
清除进位进位应该怎么算呢，uint64_t，高32比特存放的就是进位值，清除进位就是把高32比特清零：
r[1] = a[1] + b[1] + (r[0] >> 32);
r[0] &= 0x0FFFFFFFFULL;转换为循环：
for(i = x; i < 8; i++) {
r[i] = a[i] + b[i] + (r[i-1] >> 32); // 会溢出吗？
r[i-1] &= 0x0FFFFFFFFULL;
}显然i应该从1开始，第1轮并不需要处理进位，所以最终实现为：
static void gm_i_bn_add(gm_bn_t r, const gm_bn_t a, const gm_bn_t b) {
int i;
r[0] = a[0] + b[0];
for(i = 1; i < 8; i++) {
r[i] = a[i] + b[i] + (r[i - 1] >> 32);
r[i - 1] &= 0x0FFFFFFFFULL;
}
}这里循环结果r[i]是不可能会溢出的，另外也注意到，最后一轮r[7]的进位是保存在高字节，未处理的，这个不影响模加、模减结果，因为取模过程中，最终不会产生进位的。
模加
定义及实现
// r = (a + b) mod m
void gm_bn_add(gm_bn_t r, const gm_bn_t a, const gm_bn_t b, const gm_bn_t m) {
gm_i_bn_add(r, a, b);
if(gm_bn_cmp(r, m) >= 0) {
gm_i_bn_sub(r, r, m);
}
}其中gm_i_bn_add为我们刚刚实现的大数加法，gm_i_bn_sub为下一章节需要实现的大数减法，先不用关注如何实现，先看看原理
a + b的结果存放在r当中，r是的值是有可能超过m的，所以执行完加法后，只要r >= m，都减掉一个m，就是模加的结果了，如果没有超过就不用减了。
因为a和b都是小于m的大数，所以他们相加肯定小于m+m的，所以只需要减一次即可。
有了这些，我们就可以先约定gm_i_bn_sub中的参数，a必须大于b，那么a-b就不用考虑借位问题，接下来的实现就简单多了。