基于仓颉语言BigInt库实现SM2国密算法

杨洋_866

985人浏览 · 2025-11-10 17:55:15

杨洋_866 · 2025-11-10 17:55:15 发布

在信息安全领域，密码技术扮演着至关重要的角色。中国的国密标准（SM系列）为保障国家安全提供了有力的技术支持。本文将介绍基于仓颉语言的SM2国密算法实现，包括椭圆曲线运算、密钥生成、签名与验签、加密与解密等功能。

在仓颉语言中有BigInt大数库，因此实现sm2算法变得简单了，这里介绍下实现原理及过程。

BigInt大数库在标准库的std.math.numeric.*包下面。

文档地址：https://developer.huawei.com/consumer/cn/doc/cangjie-guides-V5/bigint_basic_arithmetic-V5

BigInt 定义为任意精度（二进制）的有符号整数。仓颉的 struct BigInt 用于任意精度有符号整数的计算，类型转换等。

BigInt的使用示例：

import std.math.numeric.*

main() {
    let int1: BigInt = BigInt("123456789")
    let int2: BigInt = BigInt("987654321")

    println("${int1} + ${int2} = ${int1 + int2}")
    println("${int1} - ${int2} = ${int1 - int2}")
    println("${int1} * ${int2} = ${int1 * int2}")
    println("${int1} / ${int2} = ${int1 / int2}")
    let (quo, mod) = int1.divAndMod(int2)
    println("${int1} / ${int2} = ${quo} .. ${mod}")

    return 0
}

SM2国密算法简介

SM2是一种基于椭圆曲线公钥密码算法（Elliptic Curve Public Key Cryptography, ECC），它使用了中国自主定义的椭圆曲线参数，能够提供安全的加密和签名功能。SM2定义在GB/T 32918-2016标准中，该标准由中国国家标准化管理委员会发布。

SM2算法基于椭圆曲线密码学(ECC)，其核心参数包括：

椭圆曲线方程：y² = x³ + ax + b
有限域参数：大素数p
基点G：曲线上的生成点
阶n：基点G的阶

中国商用密码标准中SM2的推荐参数为256位素数域上的椭圆曲线，具体参数可在国家标准文档中找到。

仓颉BigInt的优势

仓颉的BigInt类型具有以下特点，使其非常适合实现SM2：

任意精度：支持超大整数运算
丰富的运算符：重载了+, -, *, /, %等运算符
模运算支持：内置高效的模逆元计算
类型安全：编译时检查确保运算安全

椭圆曲线运算

SM2算法的核心是椭圆曲线运算。实现椭圆曲线运算前，需要定义椭圆曲线的参数。本文中，我们使用的是SM2的曲线参数：

P = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF
A = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC
B = 28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E933
N = FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123
Gx = 32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7
Gy = BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0

// 定义无穷远点
let INFINITY = (x: BigInt(0), y: BigInt(0))

计算模逆元

在椭圆曲线运算中，计算模逆元是一个关键步骤。以下为计算模逆元的函数实现：

func inv_mod(a: BigInt, p: BigInt): BigInt {
    if (p <= 1) throw ArithmeticException("Modulus must be > 1")
    if (a == 0) throw ArithmeticException("Cannot invert 0")
    
    var (old_r, r) = (a, p)
    var (old_s, s) = (BigInt(1), BigInt(0))
    
    while (r != BigInt(0)) {
        let quotient = old_r / r
        (old_r, r) = (r, old_r - quotient * r)
        (old_s, s) = (s, old_s - quotient * s)
    }
    
    if (old_r != BigInt(1)) {
        throw ArithmeticException("No inverse")
    }
    
    let result = old_s % p
    return if (result < 0) result + p else result
}

椭圆曲线点加

椭圆曲线点加是椭圆曲线加密算法的基础。通过特定的公式可以实现两个椭圆曲线点的相加。

func point_add(P: (x: BigInt, y: BigInt), Q: (x: BigInt, y: BigInt)): (x: BigInt, y: BigInt) {
    if (P == INFINITY) return Q
    if (Q == INFINITY) return P
    if (P.x == Q.x && (P.y + Q.y) % p == 0) return INFINITY
    
    let lambda = 
        if (P == Q) {
            // 点倍运算
            let numerator = (P.x.pow(2) * 3 + a) % p
            let denominator = (P.y * 2) % p
            (numerator * inv_mod(denominator, p)) % p
        } else {
            // 点加运算
            let numerator = (Q.y - P.y) % p
            let denominator = (Q.x - P.x) % p
            (numerator * inv_mod(denominator, p)) % p
        }
    
    let x3 = (lambda.pow(2) - P.x - Q.x) % p
    let y3 = (lambda * (P.x - x3) - P.y) % p
    
    return (x: if (x3 < 0) x3 + p else x3, 
            y: if (y3 < 0) y3 + p else y3)
}

椭圆曲线点乘

椭圆曲线点乘是椭圆曲线加密算法中另一个重要的运算，它用于生成公钥和签名密钥。

func point_mul(k: BigInt, P: (x: BigInt, y: BigInt)): (x: BigInt, y: BigInt) {
    var result = INFINITY
    var current = P
    var remaining = k
    
    while (remaining > BigInt(0)) {
        if (remaining % BigInt(2) == BigInt(1)) {
            result = point_add(result, current)
        }
        current = point_add(current, current)
        remaining = remaining / BigInt(2)
    }
    
    return result
}

密钥生成

SM2算法的密钥对包括私钥和公钥。私钥是一个随机数，而公钥则是根据私钥和椭圆曲线的基点G计算得到的。

func generate_keypair(): (priv: BigInt, pub: (x: BigInt, y: BigInt)) {
    // 生成私钥d
    let rand = Random()  // 创建随机数生成器
    let d = BigInt(false, SM2_N.bitLen, rand: rand) % (SM2_N - BigInt(1)) + BigInt(1)  // 生成 [1, SM2_N-1] 范围内的随机 BigInt
    // 计算公钥P
    let P = ec_point_mul(d, (SM2_Gx, SM2_Gy))
    return (d, P)
}

签名/验签

签名和验签是公钥密码算法的重要应用。签名过程包括哈希计算、随机数生成、椭圆曲线运算等步骤。验签过程则是签名过程的逆操作，用于验证签名的真伪。

计算ZA

compute_za函数用于计算Za值，这是签名过程中的一个重要参数。

func compute_za(pub: (x: BigInt, y: BigInt), id!: Array<UInt8> = []): Array<UInt8> {
    // ...
    return sm3.finish()
}

签名生成

sm2_sign函数用于生成签名。

func sm2_sign(priv: BigInt, msg: Array<UInt8>, id!: Array<UInt8> = []): (r: BigInt, s: BigInt) {
    // ...
    return (r, s)
}

签名验证

sm2_verify函数用于验证签名。

func sm2_verify(pub: (x: BigInt, y: BigInt), msg: Array<UInt8>, 
               signature: (r: BigInt, s: BigInt), id!: Array<UInt8> = []): Bool {
    // ...
    return (e_int + x1) % SM2_N == r
}

加密/解密

SM2算法还可以用于加密和解密。加密过程包括随机数生成、椭圆曲线运算、密钥派生、异或加密等步骤。解密过程则是加密过程的逆操作，用于恢复原始数据。

密钥派生

kdf函数用于密钥派生。

func kdf(z: Array<UInt8>, keyLen: Int): Array<UInt8> {
    // ...
    return derived[0..keyLen-1]
}

加密实现

sm2_encrypt函数用于加密数据。

func sm2_encrypt(pub: (x: BigInt, y: BigInt), plaintext: Array<UInt8>): Array<UInt8> {
    // ...
    return C1[0].toBytes().concat(C1[1].toBytes()).concat(C3).concat(ciphertext)
}

解密实现

sm2_decrypt函数用于解密数据。

func sm2_decrypt(priv: BigInt, ciphertext: Array<UInt8>): Array<UInt8> {
    // ...
    return plaintext
}

示例用法

下面是一个完整的示例，展示了如何使用上述函数进行密钥生成、签名、验签、加密和解密操作。

main() {
    // 密钥生成
    let (priv, pub) = generate_keypair()
    println("私钥: ${toHexString(priv.toBytes())}")
    println("公钥: (${toHexString(pub[0].toBytes())}, ${toHexString(pub[1].toBytes())})")
    
    // 签名验签
    let msg = "仓颉SM2测试消息".toArray()
    let (r, s) = sm2_sign(priv, msg)
    println("签名: r=${toHexString(r.toBytes())}, s=${toHexString(s.toBytes())}")
    println("验签结果: ${sm2_verify(pub, msg, (r, s))}")
    
    // 加密解密
    let plaintext = "加密测试数据".toArray()
    let ciphertext = sm2_encrypt(pub, plaintext)
    println("密文: ${toHexString(ciphertext)}")
    println("解密: ${toHexString(sm2_decrypt(priv, ciphertext))}")
    
    // 错误测试
    try {
        sm2_decrypt(priv, ciphertext[0..95])
        println("错误：未检测到短密文")
    } catch (e: Exception) {
        println("成功捕获异常: ${e.message}")
    }
}

完整实现代码

package testcj
import std.random.*
import std.binary.*
import stdx.crypto.digest.*
import std.math.numeric.*
import stdx.encoding.hex.*
//import std.exception.*

// ==================== 国密SM2参数 ====================
let SM2_P = BigInt.parse("FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF", radix: 16)
let SM2_A = BigInt.parse("FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFC", radix: 16)
let SM2_B = BigInt.parse("28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93", radix: 16)
let SM2_N = BigInt.parse("FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123", radix: 16)
let SM2_Gx = BigInt.parse("32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7", radix: 16)
let SM2_Gy = BigInt.parse("BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0", radix: 16)

// ==================== 椭圆曲线运算 ====================
func inv_mod(a: BigInt, p: BigInt): BigInt {
    if (p <= BigInt(1)) {throw ArithmeticException("Modulus must be > 1")}
    if (a == BigInt(0)) {throw ArithmeticException("Cannot invert 0")}

    var (old_r, r) = (a, p)
    var (old_s, s) = (BigInt(1), BigInt(0))
    
    while (r != BigInt(0)) {
        let quotient = old_r / r
        (old_r, r) = (r, old_r - quotient * r)
        (old_s, s) = (s, old_s - quotient * s)
    }
    //println("old_r:${toHexString(old_r.toBytes())}" )
    if (old_r != BigInt(1)) { 
        throw ArithmeticException("No inverse") 
    } else { 
        return old_s%p 
    }
}

func ec_point_add(P: (x: BigInt, y: BigInt), Q: (x: BigInt, y: BigInt)): (x: BigInt, y: BigInt) {
    // 参数名本身不能作为变量使用或用于访问元组中元素
    if (P[0]== BigInt(0) && P[1]== BigInt(0)) { return Q }
    if (Q[0] == BigInt(0) && Q[1] == BigInt(0)) { return P }
    if (P[0] == Q[0] && (P[1] != Q[1] || P[1] == BigInt(0))) { return (BigInt(0), BigInt(0)) }
    
    let lambda = if (P == Q) {
        (BigInt(3) * P[0]**2 + SM2_A) * inv_mod(BigInt(2) * P[1], SM2_P) % SM2_P
    } else {
        (Q[1] - P[1]) * inv_mod(Q[0] - P[0], SM2_P) % SM2_P
    }
    
    let x3 = (lambda**2 - P[0] - Q[0]) % SM2_P
    let y3 = (lambda * (P[0] - x3) - P[1]) % SM2_P
    return (x3, y3)
}

func ec_point_mul(k: BigInt, P: (x: BigInt, y: BigInt)): (x: BigInt, y: BigInt) {
    var result = (BigInt(0), BigInt(0))
    var temp = P
    for (i in 0..k.bitLen) {
        if (k.testBit(i)) {
            result = ec_point_add(result, temp)
        }
        temp = ec_point_add(temp, temp)
    }
    return result
}

// ==================== 密钥生成 ====================
func generate_keypair(): (priv: BigInt, pub: (x: BigInt, y: BigInt)) {
    //let d = BigInt.random(SM2_N - 1) + 1
    let rand = Random()  // 创建随机数生成器
    let d = BigInt(false, SM2_N.bitLen, rand: rand) % (SM2_N - BigInt(1)) + BigInt(1)  // 生成 [1, SM2_N-1] 范围内的随机 BigInt
    let P = ec_point_mul(d, (SM2_Gx, SM2_Gy))
    return (d, P)
}

// ==================== 签名/验签 ====================
func compute_za(pub: (x: BigInt, y: BigInt), id!: Array<UInt8> = []): Array<UInt8> {
    let sm3 = SM3()
    //sm3.write(UInt16(id.size * 8).toBytes())
    let buffer = Array<Byte>(4, repeat: 0)
    UInt16(id.size * 8).writeBigEndian(buffer)
    sm3.write(buffer)
    sm3.write(id)
    sm3.write(SM2_A.toBytes())
    sm3.write(SM2_B.toBytes())
    sm3.write(SM2_Gx.toBytes())
    sm3.write(SM2_Gy.toBytes())
    sm3.write(pub[0].toBytes())
    sm3.write(pub[1].toBytes())
    return sm3.finish()
}

func sm2_sign(priv: BigInt, msg: Array<UInt8>, id!: Array<UInt8> = []): (r: BigInt, s: BigInt) {
    let pub = ec_point_mul(priv, (SM2_Gx, SM2_Gy))
    let za = compute_za(pub, id:id)
    
    let sm3 = SM3()
    sm3.write(za)
    sm3.write(msg)
    let hashBytes = sm3.finish()
    //let hexStr = hashBytes.map({b => b.toHexString()}).join("")
    let hexStrArray = hashBytes.map({ b: Byte => toHexString(b) })
    let hexStr = String.join(hexStrArray, delimiter: "")  
    let bigInt = BigInt.parse(hexStr, radix: 16)

    //let e_int = BigInt.fromBytes(sm3.finish())
    let e_int = bigInt
    
    var r = BigInt(0)
    var s = BigInt(0)
    var k = BigInt(0)
    
    while (true) {
        let rand = Random()  // 创建随机数生成器
        k = BigInt(false, SM2_N.bitLen, rand: rand) % (SM2_N - BigInt(1)) + BigInt(1)  // 生成 [1, SM2_N-1] 范围内的随机 BigInt
        let (x1, _) = ec_point_mul(k, (SM2_Gx, SM2_Gy))
        r = (e_int + x1) % SM2_N
        
        if (r == BigInt(0) || r + k == SM2_N) {
            continue
        }
        
        s = (inv_mod(BigInt(1) + priv, SM2_N) * (k - r * priv)) % SM2_N
        if (s != BigInt(0)) {
            break
        }
    }
    
    return (r, s)
}

func sm2_verify(pub: (x: BigInt, y: BigInt), msg: Array<UInt8>, 
               signature: (r: BigInt, s: BigInt), id!: Array<UInt8> = []): Bool {
    let (r, s) = signature
    if (r <= BigInt(0) || r >= SM2_N || s <= BigInt(0) || s >= SM2_N) {
        return false
    }
    
    let za = compute_za(pub, id:id)
    let sm3 = SM3()
    sm3.write(za)
    sm3.write(msg)
    //let e_int = BigInt.fromBytes(sm3.finish())
    let hashBytes = sm3.finish()
    //let hexStr = hashBytes.map({b => b.toHexString()}).join("")
    let hexStrArray = hashBytes.map({ b: Byte => toHexString(b) })
    let hexStr = String.join(hexStrArray, delimiter: "")  
    let bigInt = BigInt.parse(hexStr, radix: 16)
    let e_int = bigInt
    
    let t = (r + s) % SM2_N
    if (t == BigInt(0)) {
        return false
    }
    
    let sG = ec_point_mul(s, (SM2_Gx, SM2_Gy))
    let tP = ec_point_mul(t, pub)
    let (x1, _) = ec_point_add(sG, tP)
    
    return (e_int + x1) % SM2_N == r
}

// ==================== 加密/解密 ====================
func kdf(z: Array<UInt8>, keyLen: Int): Array<UInt8> {
    var derived: Array<UInt8> = []
    var counter: UInt32 = 1
    
    while (derived.size < keyLen) {
        let sm3 = SM3()
        sm3.write(z)
        //sm3.write(counter.toBytes())
        let buffer = Array<Byte>(4, repeat: 0)
        UInt32(counter).writeBigEndian(buffer)
        sm3.write(buffer)
        let hashBytes = sm3.finish()
        //derived = derived+hashBytes
        derived = derived.concat(hashBytes)
        counter += 1
    }
    return derived[0..keyLen-1]
}

func sm2_encrypt(pub: (x: BigInt, y: BigInt), plaintext: Array<UInt8>): Array<UInt8> {
    var k: BigInt
    var C1: (x: BigInt, y: BigInt) = (BigInt(0), BigInt(0))
    var S: (x: BigInt, y: BigInt) = (BigInt(0), BigInt(0))

    
    while (true) {
        //k = BigInt.random(SM2_N - 1) + 1
        let rand = Random()  // 创建随机数生成器
        k = BigInt(false, SM2_N.bitLen, rand: rand) % (SM2_N - BigInt(1)) + BigInt(1)  // 生成 [1, SM2_N-1] 范围内的随机 BigInt
        C1 = ec_point_mul(k, (SM2_Gx, SM2_Gy))
        S = ec_point_mul(k, pub)
        if (!(S[0] == BigInt(0) && S[1] == BigInt(0))) {
            break
        }
    }
    
    let x2 = S[0].toBytes()
    let y2 = S[1].toBytes()
    let con = x2.concat(y2) // 不支持 x2 + y2这种
    let kdfKey = kdf(con, plaintext.size)
    
    var ciphertext = plaintext.clone()
    for (i in 0..plaintext.size) {
        ciphertext[i] ^= kdfKey[i]
    }
    
    let sm3 = SM3()
    sm3.write(x2)
    sm3.write(plaintext)
    sm3.write(y2)
    let C3 = sm3.finish()
    
    //return C1[0].toBytes() + C1[1].toBytes() + C3 + ciphertext
    return C1[0].toBytes().concat(C1[1].toBytes()).concat(C3).concat(ciphertext)
}

func sm2_decrypt(priv: BigInt, ciphertext: Array<UInt8>): Array<UInt8> {
    if (ciphertext.size < 96) {
        throw IllegalArgumentException("Invalid ciphertext length")
    }

    let hexStr1 = toHexString(ciphertext[0..32])
    let hexStr2 = toHexString(ciphertext[32..64])
    let bigInt1 = BigInt.parse(hexStr1, radix: 16)
    let bigInt2 = BigInt.parse(hexStr2, radix: 16)
    
    let C1: (x: BigInt, y: BigInt) = (
        bigInt1,
        bigInt2
    )
    let C3 = ciphertext[64..96]
    let C2 = ciphertext[96..]
    
    // 验证曲线点
    let left = (C1[1]**2) % SM2_P
    let right = (C1[0]**3 + SM2_A * C1[0] + SM2_B) % SM2_P
    if (left != right) {
        throw IllegalArgumentException("Invalid curve point")
    }
    
    let S = ec_point_mul(priv, C1)
    if (S[0] ==  BigInt(0) && S[1] ==  BigInt(0)) {
        throw IllegalArgumentException("Invalid private key")
    }
    
    let x2 = S[0].toBytes()
    let y2 = S[1].toBytes()
    let con = x2.concat(y2) // 不支持 x2 + y2这种
    let kdfKey = kdf(con, C2.size)
    
    var plaintext = C2.clone()
    for (i in 0..C2.size) {
        plaintext[i] ^= kdfKey[i]
    }
    
    let sm3 = SM3()
    sm3.write(x2)
    sm3.write(plaintext)
    sm3.write(y2)
    let u = sm3.finish()
    if (u != C3) {
        throw IllegalArgumentException("MAC verification failed")
    }
    
    return plaintext
}

// ==================== 示例用法 ====================
main() {
    // 密钥生成
    let (priv, pub) = generate_keypair()
    println("私钥: ${toHexString(priv.toBytes())}")
    println("公钥: (${toHexString(pub[0].toBytes())}, ${toHexString(pub[1].toBytes())})")
    
    // 签名验签
    let msg = "仓颉SM2测试消息".toArray()
    let (r, s) = sm2_sign(priv, msg)
    println("签名: r=${toHexString(r.toBytes())}, s=${toHexString(s.toBytes())}")
    println("验签结果: ${sm2_verify(pub, msg, (r, s))}")
    
    // 加密解密
    let plaintext = "加密测试数据".toArray()
    let ciphertext = sm2_encrypt(pub, plaintext)
    println("密文: ${toHexString(ciphertext)}")
    println("解密: ${toHexString(sm2_decrypt(priv, ciphertext))}")
    
    // 错误测试
    try {
        sm2_decrypt(priv, ciphertext[0..95])
        println("错误：未检测到短密文")
    } catch (e: Exception) {
        println("成功捕获异常: ${e.message}")
    }
}