非对称加密算法与数字签名

发表于 2019-03-31 更新于 2021-11-17 分类于密码学本文字数： 8.9k 阅读时长 ≈ 8 分钟

RSA算法

背景

RSA是一种非对称加密算法，该算法在1977年由Ron Rivest、Adi Shamir和Leonard Adleman三人提出，算法一起三人姓氏开头字母命名。

对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之，对一极大整数做因数分解愈困难，RSA算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用RSA加密的信息的可靠性就肯定会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA钥匙才可能被强力方式解破。到当前为止，世界上还没有任何可靠的攻击RSA算法的方式。只要其钥匙的长度足够长，用RSA加密的信息实际上是不能被解破的。

算法流程

RSA算法本身比较简单，基本流程如下：

选择两个大素数p和q，p不等于q
计算N = p*q
令r=(p-1)(q-1)
寻找一个小于r的的整数e，使e与r互质
寻找一个整数d，使 (d*e) mod r = 1
(N,e)是公钥，(N,d)是私钥
加密时，若明文为P，则密文C = P^e mod N
解密时，P = C^d mod N

举例

取 p = 7，Q = 17
n = p*q = 119
r = 6 * 16 = 96
取e = 5
取d = 77
假设明文为10，密文c = 10^e mod n = 40
解密： 40^d mod n = 10

RSA安全性分析

回顾整个算法。我们公开的是公钥e和n，保密的是私钥d，私钥是由e和r构成的。由于e是公开的，所以攻击者需要求得r。一个途径就是根据公开的n求得p和q就得到了r。但是p和q是很大的素数，导致n也很大，所以因数分解异常困难，有数学分析证明，如果n能达到100位数，那么正确求得q和p需要数十年的时间。

速度

毫无疑问，由于涉及大量大数运算，RSA加密速度很慢。一种有效的方法是加密的一方使用一种可靠的对称加密算法加密明文，然后用RSA加密较短的秘钥，最后连同RSA加密的密文和对称加密算法加密的密文一同传输。

数字签名

RSA加密算法分公钥秘钥和私钥密码。用RSA进行数字签名的步骤如下

发送方A对消息M进行摘要得到M1
A用自己的私钥对摘要进行加密，得到数字签名DS
A将消息M和数字签名DS一同发送给B
B对消息M进行摘要得到M2
B用A的公钥对数字签名解密得到M1
对比M2和M1是否相等来判断消息是否完整或被篡改

使用

加解密

这里用go语言进行演示（其后所有实例完整代码见这里），先看加解密，基本思想就是公钥加密私钥解密

func main() {
	read:=rand.Reader
	privKey,err:=rsa.GenerateKey(read,1024)
	if err != nil{
		log.Fatalln(err.Error())
	}
	pubKey := privKey.PublicKey
	fmt.Println("N:",privKey.N)
	fmt.Println("公钥E:",privKey.E)
	fmt.Println("私钥D",privKey.D)

	plainText := "helloworld5645你好"

	ciphertext,err:=rsa.EncryptPKCS1v15(read,&pubKey,[]byte(plainText))
	if err != nil{
		log.Fatalln(err.Error())
	}
	fmt.Println(hexToString(ciphertext))

	result,err:=rsa.DecryptPKCS1v15(read,privKey,ciphertext)
	if err != nil{
		log.Fatalln(err.Error())
	}
	fmt.Println(string(result))
}

上面代码中GenerateKey是随机生成一对秘钥，公钥是和私钥相对应的，通过查看源码可以知道公钥的结构体就是包含一个大整数N和一个整数E，私钥除了记录了公钥信息，还记录了一个大整数D就是私钥。代码中使用的加密方法是EncryptPKCS1v15，PKCS是公钥加密标准(Public-Key Cryptography Standards ),PKCS1就是一系列标准的第一个，常记做PKCS#1，也即是RSA加密标准。v15表示1.5版本，详见文档

除了EncryptPKCS1v15的一套加解密方法外，还有一套OAEP方法，是另外一种填充方式，详见文档,用法如下：

ciphertext,err:=rsa.EncryptOAEP(sha256.New(),read,&pubKey,[]byte(plainText),[]byte("hi"))
result,err:=rsa.DecryptOAEP(sha256.New(),read,privKey,ciphertext,[]byte("hi"))

值得一提的是在加密时可以指定一个标签，解密时不但要秘钥正确，标签也要对应，否则无法解密，标签可以为空

数字签名

数字签名的签名与验证基本思路就是私钥签名，公钥验证

func main() {
	read:=rand.Reader
	privKey,err:=rsa.GenerateKey(read,1024)
	if err != nil{
		log.Fatalln(err.Error())
	}
	pubKey := privKey.PublicKey

	text := "helloworld5645你好"


	signature1,err:=rsa.SignPKCS1v15(read,privKey,crypto.Hash(0),[]byte(text))
	if err != nil{
		log.Fatalln(err.Error())
	}
	fmt.Println("signature1:",hex.EncodeToString(signature1))
	hashed := sha256.Sum256([]byte(text))
	signature2,err:=rsa.SignPKCS1v15(read,privKey,crypto.SHA256,hashed[:])
	if err != nil{
		log.Fatalln(err.Error())
	}
	fmt.Println("signature2:",hex.EncodeToString(signature2))

	err=rsa.VerifyPKCS1v15(&pubKey,crypto.Hash(0),[]byte(text),signature1)
	if err != nil {
		fmt.Println("签名验证失败")
	}else {
		fmt.Println("签名验证成功")
	}
	err=rsa.VerifyPKCS1v15(&pubKey,crypto.SHA256,hashed[:],signature2)
	if err != nil {
		fmt.Println("签名验证失败")
	}else {
		fmt.Println("签名验证成功")
	}
}

首先还是用GenerateKey生成一对秘钥，然后使用SignPKCS1v15进行签名，由于非对称加密的效率问题，官方强烈建议对原文进行摘要后在进行签名，这是需要在第三个参数中指定所用的hash函数，如果不摘要，则用0表示。验证也是一样道理，使用VerifyPKCS1v15函数，传入要验证的内容即可。注意使用的签名和验证函数以一对PKCS1v15后缀的，和加解密一样这是用PKCS1v15标准的。还有一对使用PSS规范的方法，用法基本一样这里不再举例。

DSA算法

先介绍一下DSA的一些基本变量

p ：长度为L的素数，L是64的倍数
q ：(p-1)的N位素数因子
g ：h^((p-1)/q) mod p ,h是小于p-1的数，g需要大于1
x ：小于q的数
y ：g^x mod p
H ：摘要算法

在以上变量中(p,q,g,y)是公开的，即公钥，x是私钥，签名过程如下（m是消息）

发送方A随机选择一个小于q的随机数k，作为临时秘钥
r=(g^k mod p) mod q
s=((1/k)*(H(m)+xr)) mod q
r与s作为数字签名连同信息m发送给接收方B
B进行如下计算
w = (1/s) mod q
u1 = (H(m) * w) mod q
u2 = (rw) mod q
v = ((g^u1 * y^u2) mod p) mod q
最后比较v与r是否相等验证数字签名

相比RSA可以用作加密，DSA只能用作签名，而且安全程度类似。

使用

func main() {
	read:=rand.Reader
	privKey:=new(dsa.PrivateKey)
	err:=dsa.GenerateParameters(&privKey.Parameters,read,dsa.L1024N160)
	if err!=nil {
		log.Fatalln(err.Error())
	}
	err=dsa.GenerateKey(privKey,read)
	if err!=nil {
		log.Fatalln(err.Error())
	}
	fmt.Println("私钥：X =",privKey.X)
	fmt.Println("公钥：Y =",privKey.PublicKey.Y)
	fmt.Println("公共参数：")
	fmt.Println("p = ",privKey.PublicKey.P)
	fmt.Println("q = ",privKey.PublicKey.Q)
	fmt.Println("g = ",privKey.PublicKey.G)
	r,s,err:=dsa.Sign(read,privKey,[]byte("helloworld"))
	if err!=nil {
		log.Fatalln(err.Error())
	}
	fmt.Println("签名结果：\nr=",r)
	fmt.Println("s=",s)

	b:=dsa.Verify(&privKey.PublicKey,[]byte("helloworld"),r,s)
	if b {
		fmt.Println("签名验证成功")
	}else {
		fmt.Println("签名验证失败")
	}
}

首先是生成秘钥对，和rsa需要指定秘钥长度一样，这里要指定密钥对的参数长度，这里选用dsa.L1024N160，L表示p的长度，N表示q的长度。先用GenerateParameters生成参数，再用GenerateKey生成秘钥，然后用Sign签名得到r,s。最后用Verify验证。同样由于效率问题，签名时除非明文较短，否则不要直接对明文签名。注意Go语言中是按照FIPS 186-3标准实现的，详见文档

ElGamal算法

和RSA类似，ElGamal是一种非对称加密算法，先介绍它的加密

秘钥生成

选取一个足够大的素数p
选取Zp的生成元E1
随机选取整数d，d小于p-2，计算E2 = E1^d mod p
私钥为d，公钥为(E1,E2,p)

加密

选取随机数r属于Zp-1
C1 = E1^r mod p
C2 = M*E2^r mod p (M位明文)
C1,C2就是密文

解密

计算 (C2 * (C1^d)^-1) mod p = M

数字签名

公钥为(E1,E2,p),私钥为d

发送方选择一个随机数r
S1 = E1^r mod p
S2 = ((M - d*S1) * r^-1) mod (p-1)
S1,S2就是数字签名，M是原始消息，将三种发送给接收方
接收方进行如下计算
V1 = E1 ^ M mod p
V2 = (E2^S1 * S1^S2) mod p
比较v1与v2是否相等来进行验证

ECC算法

ECC即EllipseCurve Cryptography，全称椭圆曲线加密。是一种基于椭圆曲线数学的公钥密码。与传统的基于大质数因子分解困难性的加密方法不同，ECC 依赖于解决椭圆曲线离散对数问题的困难性。关于椭圆曲线的知识见这里：ECC椭圆曲线详解

加解密过程

发送方A选择一条曲线E，同时选择曲线上一点G作为基点，基点G的阶数为n
A选择一个私钥d，d<n。生成公钥K = dG
A将E、K和G传给接收方B
B收到信息后，将明文编码到一点M（编码方式可自由协商），并产生随机数r，r<n
B进行如下计算
C1 = M+rK
C2 = rG
C1与C2就是密文
A收到密文后进行如下解密：M = C1 - dC2

数字签名

使用ECC进行的数字签名被称为ECDSA。基本过程如下，

依旧选择一条曲线E，同时选择曲线上一点G作为基点，基点G的阶数为n
选择一个私钥d，d<n,计算公钥Q = dG
首先计算信息的摘要e
随机选择一个数k，k<n
计算点(x1,y1) = kG
计算r = x1 mod n，如果r=0，回到第4步
计算s = k^-1(e + rd) mod n，如果s = 0，回到第4步
r和s就是签名值

验证如下：

收到消息m和签名值r，s后进行如下计算
先计算摘要e
计算w = s^-1 mod n
计算u1 = ew mod n
计算u2 = rw mod n
计算点(x1,y1) = u1G+u2Q
判断r是否等于x1

密钥协商

之前我们讲过Diffie-Hellman密钥协商算法，基于的是大数分解难题，而基于ECC也有一种密钥协商算法，称为ECDH，思想是和Diffie-Hellman类似的，基本流程如下：

A,B双方协商一条椭圆曲线及基点G，这些数据是可以明文传播的
A计算自己的公钥和私钥，即da与Da，其中Da=da*G
B计算自己的公钥和私钥，即db与Db，其中Db=db*G
双方交换公钥
A计算密钥Sa=da*Db
B计算密钥Sb=db*Da
可以证明Sa=Sb：Sa=da*Db=da*db*G，Sb=db*Da=db*da*G

使用

下面例子是ecdsa

func main() {
	read:=rand.Reader
	priv,err:=ecdsa.GenerateKey(elliptic.P256(),read)
	if err != nil {
		log.Fatalln(err.Error())
	}
	r,s,err:=ecdsa.Sign(read,priv,[]byte("hello"))
	if err != nil {
		log.Fatalln(err.Error())
	}
	fmt.Println("签名结果")
	fmt.Println("r = ",r)
	fmt.Println("s = ",s)
	b := ecdsa.Verify(&priv.PublicKey,[]byte("hello"),r,s)
	if b {
		fmt.Println("签名验证成功")
	}else {
		fmt.Println("签名验证失败")
	}
}

虽然标准包中没有提供ecc的实现，但是有elliptic包，提供了椭圆曲线的一些基本运算，再参考ecdsa可以自行设计加解密算法。对于ecdh在以太坊的ecies有实现

func (prv *PrivateKey) GenerateShared(pub *PublicKey, skLen, macLen int) (sk []byte, err error) {
	if prv.PublicKey.Curve != pub.Curve {
		return nil, ErrInvalidCurve
	}
	if skLen+macLen > MaxSharedKeyLength(pub) {
		return nil, ErrSharedKeyTooBig
	}

	x, _ := pub.Curve.ScalarMult(pub.X, pub.Y, prv.D.Bytes())
	if x == nil {
		return nil, ErrSharedKeyIsPointAtInfinity
	}

	sk = make([]byte, skLen+macLen)
	skBytes := x.Bytes()
	copy(sk[len(sk)-len(skBytes):], skBytes)
	return sk, nil
}

秘钥格式

一些规范对RSA秘钥的格式也有一些要求，具体格式语法就不介绍了，go语言提供方便的转换接口

密钥编码

func main() {
	read:=rand.Reader
	privKey,err:=rsa.GenerateKey(read,1024)
	if err != nil{
		log.Fatalln(err.Error())
	}
	pubKey := privKey.PublicKey

	encodePrivKey := x509.MarshalPKCS1PrivateKey(privKey)
	block1:=pem.Block{
		Type:  "RSA PRIVATE KEY",
		Bytes: encodePrivKey,
	}
	pem.Encode(os.Stdout,&block1)

	encodePubvKey := x509.MarshalPKCS1PublicKey(&pubKey)
	block2:=pem.Block{
		Type:  "RSA PUBLIC KEY",
		Bytes: encodePubvKey,
	}
	pem.Encode(os.Stdout,&block2)
}

首先利用x509包中的MarshalPKCS1PrivateKey方法对秘钥进行序列化，然后利用pem包进行编码，编码前首先要用Block对秘钥进行包装，主要是指定Type，最后生成数据如下

秘钥解码

给出一段上文表示秘钥可以用下面方法解码

func main() {
	read:=rand.Reader
	privKey,err:=rsa.GenerateKey(read,1024)
	if err != nil{
		log.Fatalln(err.Error())
	}

	encodePrivKey := x509.MarshalPKCS1PrivateKey(privKey)
	block1:=pem.Block{
		Type:  "RSA PRIVATE KEY",
		Bytes: encodePrivKey,
	}
	file, err := os.Create("priv.pem")
	pem.Encode(file,&block1)

	key,err:=ioutil.ReadFile("priv.pem")
	block,_:=pem.Decode(key)
	if block ==nil {
		log.Fatalln("nil")
	}
	privkey2,err:=x509.ParsePKCS1PrivateKey(block.Bytes)
	fmt.Println(privKey.D.Cmp(privkey2.D)==0)
	fmt.Println(privKey.N.Cmp(privkey2.N)==0)
}

基本就是编码的逆过程，先decode再Parse。

其他

除了可以编解码PKCS1规范的秘钥，还提供了MarshalPKCS8PrivateKey、MarshalECPrivateKey与 MarshalPKIXPublicKey等，用于支持不同的密钥或规范

题图来自unsplash：https://unsplash.com/photos/KidY3t8O4PE