[原创]国密算法及其优化

闲鱼技术01 · 发表于 2022-1-8 15:39

一.项目背景

对于商业银行来说，国密算法的金融安全必不可少的一环，大多商业银行都有硬件加密机做加密处理，缺缺乏软加密方面的支持，因此，这篇大致详解国密算法软加密及其优化的思路，具体包括sm2非对称加密算法，sm3的hash算法和sm4的对称加密算法
二.国密算法概述

国密算法是椭圆曲线算法的一种，椭圆曲线加密法是一种基于离散对数问题的非对称（或公钥）加密法，可以用对椭圆曲线上的点进行加法或乘法运算来表达。

在椭圆曲线上，两个点的加法是如下定义的：

任意取椭圆曲线上两点P、Q（若P、Q两点重合，则作P点的切线），作直线交于椭圆曲线的另一点R&#39;，过R&#39;做y轴的平行线交于R，定义P+Q=R。这样，加法的和也在椭圆曲线上，并同样具备加法的交换律、结合律

椭圆曲线上公钥生成

以一个随机生成的私钥k为起点，我们将其与曲线上已定义的生成点G相乘以获得曲线上的另一点，也就是相应的公钥K。生成点的坐标是由不同椭圆曲线标准（如比特币用secp256k1）的，公钥的生成满足如下公式：
{K = k * G}
其中k是私钥，G是生成点，在该曲线上所得的点K是公钥。一个私钥k乘以G将得到相同的公钥K。k和K之间的关系是固定的，但只能单向运算，即从k得到K。这就是可以把公钥地址（K的衍生，比如对K再算一次hash）与任何人共享而不会泄露私钥（k）的原因
下图展示了在椭圆曲线上整数点的乘法的示意，目标是找到生成点G的倍数kG。也就是将G相加k次。例如得到 G、2G、4G 的几何操作，在椭圆曲线中，点的相加等同于从该点画切线找到与曲线相交的另一点，然后映射到x轴。

椭圆曲线加密算法原理如下：

　　设私钥、公钥分别为k、K，即K = kG，其中G为G点。

　　公钥加密：
　　选择随机数r，将消息M生成密文C，该密文是一个点对，即：
　　C = {rG, M+rK}，其中K为公钥

　　私钥解密：
　　M + rK - k(rG) = M + r(kG) - k(rG) = M
　　其中k、K分别为私钥、公钥。

椭圆曲线的加密和解密过程示例：

1. Alice选定一条椭圆曲线E，并取椭圆曲线上一点作为基点G 假设选定E29(4,20)，基点G(13,23) , 基点G的阶数n=37
2.Alice选择一个私有密钥k（k<n），并生成公开密钥K=kG 比如25, K= kG = 25G = (14,6）
3.Alice将E和点K、G传给Bob
4.Bob收到信息后，将待传输的明文编码到上的一点M（编码方法略），并产生一个随机整数r（r<n,n为G的阶数）假设r=6 要加密的信息为3,因为M也要在E29(4,20) 所以M=(3,28)
5.Bob计算点C1=M+rK和C2=rG C1= M+6K= M+6*25*G=M+2G=(3,28)+(27,27)=(6,12) C2=6G=(5,7)
6.Bob将C1、C2传给Alice
7.Alice收到信息后，计算C1-kC2，结果就应该是点M C1-kC2 =(6,12)-25C2 =(6,12)-25*6G =(6,12)-2G =(6,12)-(27,27) =(6,12)+(27,2) =(3,28)
数学原来上能解密是因为:C1-kC2=M+rK-krG=M+rkG-krG=M
解析:该例子中私钥k=25，公钥 K=kG=25G（公钥K也是拥有坐标x和坐标y的一个点）=点（14，6），要加密的明文M为3（需要编码到椭圆曲线上的一点，例子中就编码到椭圆曲线的点（4，20）），随机数r=6，可以计算出加密后的密文C = {M+rK和rG}，所以C1=M+rK=（6，12），C2=rG=（5，7），解密过程用C1-kC2即可反推出M
三. 国密算法在Fabric的压测测算数据

                           SM2（C语言） SM2（未优化GO） SM2(优化GO)    ECDSA_P256
生成密钥100次       93ms          600ms                   36ms                      30ms
签名100次                97ms             626ms                   8ms                      8ms
验签100次             未测试          1203ms                   20ms                      19ms
                                       sha256    sm3       sm3未优化
哈希1000字节1000次       9ms          10ms       49ms

四.目前使用的国密的软算法是基于以下go语言编写的未优化的国密算法，具体地址如下

五.  国密代码解析

1. 配置信息：主要包括国密开启开关，加密方式（软加密还是硬加密），如果是硬加密，还要配置硬加密地址和超时时间
   2.曲线初始化：主要看curve .go的initP256_sm2方法，这里面定义好了椭圆曲线，其中Gx和Gy是椭圆曲线中的G点坐标（不同的椭圆曲线G点坐标各不相同，国密算法的G点也是早就定死的）
func initP256_sm2() {
p256_sm2 = &elliptic.CurveParams{Name: &#34;SM2-P-256&#34;}
      //p是一个质数，也叫G点的阶
p256_sm2.P, _ = new(big.Int).SetString(&#34;FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF00000000FFFFFFFFFFFFFFFF&#34;, 16)
//如果存在最小正整数n，使得nG=O∞，则n为G点的阶
      p256_sm2.N, _ = new(big.Int).SetString(&#34;FFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFF7203DF6B21C6052B53BBF40939D54123&#34;, 16)
//椭圆曲线方程y= x-3x+b中常数b
      p256_sm2.B, _ = new(big.Int).SetString(&#34;28E9FA9E9D9F5E344D5A9E4BCF6509A7F39789F515AB8F92DDBCBD414D940E93&#34;, 16)
p256_sm2.Gx, _ = new(big.Int).SetString(&#34;32C4AE2C1F1981195F9904466A39C9948FE30BBFF2660BE1715A4589334C74C7&#34;, 16)
p256_sm2.Gy, _ = new(big.Int).SetString(&#34;BC3736A2F4F6779C59BDCEE36B692153D0A9877CC62A474002DF32E52139F0A0&#34;, 16)
p256_sm2.BitSize = 256
}

3.密钥生成主要看sm2sign.go中GenerateKey函数
// GenerateKey generates a public and private key pair.
//输入椭圆曲线c和随机数的reader，返回随机的私钥priv，注意priv包含公钥
func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
k, err := randFieldElement(c, rand)
if err != nil {
return nil, err
}

priv := new(PrivateKey)
priv.PublicKey.Curve = c
priv.D = k
      //G点坐标乘以私钥k，得到公钥K坐标x和y
priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
return priv, nil
}

// randFieldElement returns a random element of the field underlying the given
//输入椭圆曲线c和随机数的reader，返回随机的私钥k，注意1 <= k <= n-2
func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
params := c.Params()
b := make([]byte, params.BitSize/8+8)
_, err = io.ReadFull(rand, b)//随机读取40byte到b
if err != nil {
return
}

k = new(big.Int).SetBytes(b)
n := new(big.Int).Sub(params.N, one)
n = n.Sub(n, one) //n-2

// 1 <= k <= n-2
k.Mod(k, n)
k.Add(<span class="nx">k, one)

return
}

4.签名和验签生成主要看sm2sign.go中Sign()和Verify()函数，这里不做过多描述，不过值得一提的是，这里国密算法的签名和验签跟上述说的椭圆曲线的不太一样，
1、签名的过程
设G是椭圆曲线上的参考点，dA是私钥，PA是公钥，PA=dAG
对e进行数字签名得到签名结果(r,s)，计算过程是：
首先选取随机数k，当然，这个数的选择是有约束条件的，现在暂时不管
计算r=e+x1，其中(x1,y1)=kG
计算s=(1+dA)的-1次方(krdA)
可以看出前面是用私钥进行的。

2、签名验证的过程
验证签名就是利用得到的签名、公钥、椭圆曲线参数等对签名进行验证，验证主要步骤是：
首先计算t=r+s，如果t=0那么就表明没有通过。
然后通过t与s计算曲线上的点(x1,y1)=sG+tPA
再计算R=x1+e，然后验证R与r是不是相等，如果相等则表明验证通过。

3、验证的原理
为什么这样能完成验证，我们不妨推导一下：
(x1,y1)=sG+tPA
   =sG+(r+s)PA
   =sG+(r+s)dAG
   =(1+dA)sG+rdAG
   =(1+dA)(1+dA)的-1次方(krdA)G+rdAG
   =(krdA)G+rdAG
   =kG
可以看出依据公钥得到的椭圆曲线上的这个点和签名时的点是一致的。
然后再由这个x1和收到的信息相加，看是否与发送的签名r是否相符，相符就通过了。
// Sign signs a hash (which should be the result of hashing a larger message)
// using the private key, priv. If the hash is longer than the bit-length of the
// private key&#39;s curve order, the hash will be truncated to that length.  It
// returns the signature as a pair of integers. The security of the private key
// depends on the entropy of rand.
func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {
// Get min(log2(q) / 2, 256) bits of entropy from rand.
entropylen := (priv.Curve.Params().BitSize + 7) / 16
if entropylen > 32 {
entropylen = 32
}
entropy := make([]byte, entropylen)
_, err = io.ReadFull(rand, entropy)
if err != nil {
return
}

// Initialize an SHA-512 hash context; digest ...
md := sha512.New()
md.Write(priv.D.Bytes()) // the private key,
md.Write(entropy)       // the entropy,
md.Write(hash)          // and the input hash;
key := md.Sum(nil)[:32]  // and compute ChopMD-256(SHA-512),
// which is an indifferentiable MAC.

// Create an AES-CTR instance to use as a CSPRNG.
block, err := aes.NewCipher(key)
if err != nil {
return nil, nil, err
}

// Create a CSPRNG that xors a stream of zeros with
// the output of the AES-CTR instance.
csprng := cipher.StreamReader{
R: zeroReader,
S: cipher.NewCTR(block, []byte(aesIV)),
}

c := priv.PublicKey.Curve
N := c.Params().N
if N.Sign() == 0 {
return nil, nil, errZeroParam
}
var k *big.Int
e := new(big.Int).SetBytes(hash)
for {
for {
                     //这里的k为随机数
k, err = randFieldElement(c, csprng)
if err != nil {
r = nil
return
}
                     //r=明文e+（随机数k*G）的x坐标，最后再mod N
r, _ = priv.Curve.ScalarBaseMult(k.Bytes())
r.Add(r, e)
r.Mod(r, N)
if r.Sign() != 0 {
break
}
if t := new(big.Int).Add(r, k); t.Cmp(N) == 0 {
break
}
}
            //s=模逆运算（随机数k-r*私钥，1+私钥）
            //模逆运算需要三个整数。a的模逆元素（对n取模）为b，意味着a*b mod n=1
            //3*5 mod 7=1 , 3 关于 7 的模逆元素就是5，当然也可以是12等等。
            //3*3 mod 8=1,3 关于 8的模拟元素是3，也可以是11等等。。
rD := new(big.Int).Mul(priv.D, r)
s = new(big.Int).Sub(k, rD)
d1 := new(big.Int).Add(priv.D, one)

d1Inv := new(big.Int).ModInverse(d1, N)
s.Mul(s, d1Inv)
s.Mod(s, N)
if s.Sign() != 0 {
break
}
}

return
}

// Verify verifies the signature in r, s of hash using the public key, pub. Its
// return value records whether the signature is valid.
func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {
c := pub.Curve
N := c.Params().N

if r.Sign() <= 0 || s.Sign() <= 0 {
return false
}
if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {
return false
}

t := new(big.Int).Add(r, s)
t.Mod(t, N)
if N.Sign() == 0 {
return false
}

// Check if implements s*g + t*p
var x *big.Int
if opt, ok := c.(combinedMult); ok {
x, _ = opt.CombinedMult(pub.X, pub.Y, s.Bytes(), t.Bytes())
} else {
x1, y1 := c.ScalarBaseMult(s.Bytes())
x2, y2 := c.ScalarMult(pub.X, pub.Y, t.Bytes())
x, _ = c.Add(x1, y1, x2, y2)
}

e := new(big.Int).SetBytes(hash)
x.Add(x, e)
x.Mod(x, N)
return x.Cmp(r) == 0
}六国密算法的优化思路和方法

在go的源码go/src/crypto/eliptic/p256_amd64.go中，就有关于椭圆曲线的实现，具体修改地方如下几处：
1.在initP256（）处，P、N、B、Gx、Gy都要设置成国密算法的参数
2.在inverse（k  *http://big.Int）处，根据费马小定律，k^-1=k^(N-2) mod N,因此对整个函数都要进行改造
3.在scalarMult和 p256BaseMult 中转换成monegomert domain的时候，r.xyz[9],r.xyz[10],r.xyz[11]都要更改
  4.添加椭圆曲线上点(x1,y1)+(x2,y2)的计算函数
  另外在go的源码go/src/crypto/eliptic/p256_asm_amd64.s中，也需要具体修改地方如下几处：
用汇编语言如下使用到的国密函数都要实现
// Functions implemented in p256_asm_amd64.s
// Montgomery multiplication modulo P256
//
func p256Mul(res, in1, in2 []uint64) //蒙哥马利模乘需要修改

// Montgomery square modulo P256
func p256Sqr(res, in []uint64)  //蒙哥马利幂模 2次幂需要修改

// Montgomery multiplication by 1
func p256FromMont(res, in []uint64) //蒙哥马利模乘 in乘以1需要修改

// iff cond == 1  val <- -val
func p256NegCond(val []uint64, cond int) //若cond为1，则返回-val，即p-val

// if cond == 0 res <- b; else res <- a
func p256MovCond(res, a, b []uint64, cond int)//若cond为0，res=b否则res=a

// Endianness swap,主要是字节存储顺序需要转换
func p256BigToLittle(res []uint64, in []byte) //
func p256LittleToBig(res []byte, in []uint64) //

// Constant time table access
func p256Select(point, table []uint64, idx int) //从table返回16*12的数组，
//从table中返回table[12*(idx-1):12*(idx-1)+12)],结果保存在point中，
//如果idx=0或idx>16，则返回全为0的数组

func p256SelectBase(point, table []uint64, idx int) //该函数无需修改
//从table返回64*8的数组，
//从table中返回table[8*(idx-1):8*(idx-1)+8)],结果保存在point中，
//如果idx=0或idx>64，则返回全为0的数组

// Montgomery multiplication modulo Ord(G)
//蒙哥马利模乘 mod =N ,在费马小定律大数求逆时候用
func p256OrdMul(res, in1, in2 []uint64) //该函数无需修改

// Montgomery square modulo Ord(G), repeated n times
//蒙哥马利幂模 2^n次幂 mod =N ,在费马小定律大数求逆时候用
func p256OrdSqr(res, in []uint64, n int) //需修改

// Point add with in2 being affine point
// If sign == 1 -> in2 = -in2
// If sel == 0 -> res = in1
// if zero == 0 -> res = in2
// in1和in相加，其中in1、res处于jacobian坐标系，in2处于affine坐标系
func p256PointAddAffineAsm(res, in1, in2 []uint64, sign, sel, zero int)

// Point add
//点加，即in1和in2相加，in1，in2和res均处于jacobian坐标系
func p256PointAddAsm(res, in1, in2 []uint64)//该函数无需修改

// Point double
//点倍，即in乘以2，in和res均处于jacobian坐标系
func p256PointDoubleAsm(res, in []uint64)//该函数需小修改

XGundam05 · 发表于 2022-1-8 15:45

我想问一下，比如那个签名的公式推导没什么疑问，就是s和t的定义有些奇怪。s的定义式花里花哨的，其实重点在包含私钥dA和随机数k的信息。我们换一个最简单的：s=（k-dA）mod n，然后相应的把验签的 t 直接赋值 1，好像也没什么大问题。

mypro334 · 发表于 2022-1-8 15:46

签名和验签的方法有很多种，只是国密算法规定死了流程，如G点的选取或签名验签的算法，本质也是椭圆曲线的加密解密，只是G点选取的不同，签名验签的流程不同，破解的难度也就不同

		自动登录	找回密码
密码			立即注册

[原创]国密算法及其优化

本帖子中包含更多资源