数字签名算法之RSA

RSA算法是一种常用的非对称加密算法，常用于数字签名。

在公开密钥密码体制（PKI）中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK，反之亦然。

RSA公开密钥密码体制的原理是：根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥。

对称加密与非对称加密

对称加密：

加密和解密用的是同一密钥，也是最简单、最快速的加密方式，通常使用的密匙相对较小，容易被破解，如果密钥过大，安全性确实可以得到保证，但同样加密和解密的效率将会很低。
因为双方都需要密钥进行加密解密，如果有一方的密钥泄露出去，整个安全性将不复存在，所以这也是对称加密的缺点。

非对称加密：

相较于对称加密，非对称加密使用两个密匙，即公开密钥和私钥密钥。
非对称加密很有趣，公钥是任何人都可以请求得到的，但私钥只有一个人持有，而且用公钥加密的密文只能通过私钥来解开，解密者无需像对称加密一样接收加密者的密钥，而是自己保存一个密钥，这样就不在网上传送密匙，不会被拦截，会更加安全，但是相对于对称加密，非对称加密加密和解密的效率会低一些

下面就来学习属于非对称加密中的RSA算法

RSA算法涉及的数学知识

一、互质关系

两个正整数，除1以外，没有其他公因子，那么这两个数就是互质关系。

例如：30与7就是互质关系，但是30不是质数，这就是说明不是质数也能构成互质关系

由互质关系能得出以下结论：

任意两个质数构成互质关系，比如7和61。

一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。

如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。

1和任意一个自然数是都是互质关系，比如1和99。

p是大于1的整数，则p和p-1构成互质关系，比如57和56。

p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

二、欧拉函数

在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目，以φ(n)表示

其实欧拉函数就是用来计算这样一个问题

任意给定正整数n，在小于等于n的正整数之中，有多少个与n构成互质关系？

举个列子：

在1—10中，与10互质的有1、3、7、9，即φ(n)=4

通过欧拉函数又衍生出几种情况：

第一种情况：如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。
第二种情况：如果n是质数，则φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如7与1、2、3、4、5、6都构成互质关系。

其中对RSA最重要的一种情况就是：

如果n可以分解成两个互质的整数之积

1	n = p1 × p2

则

1	φ(n) = φ(p1p2) = φ(p1)φ(p2)

通过这个公式可以看出积的欧拉函数等于各个因子的欧拉函数之积

举个列子：

1
2
3

n=21
n=3*7
φ(n) = φ(p1p2) = φ(3)φ(7)=2*6=12

三、欧拉定理

欧拉定理表明，若n,a为正整数，且n,a互质，则以下公式成立：

换句话就是a的φ(n)次方被n除的余数为1或者是a的φ(n)次方减去1，可以被n整除。

举个列子：

1	例如：2和5互质，φ(5)=4，则2的4次方(16)减1,15恰好被n(5)整除

欧拉定理还有一个特殊情况：

如果正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成：

四、模反元素

如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。这时，b就叫做a的“模反元素”。

举个列子：

a=3,n=4
(3*b-1)%4=0
故b=7或b=3
显然模反元素不止一个，即如果b是a的模反元素，则 b+kn 都是a的模反元素（k为正整数）

可以看出，a的 φ(n)-1 次方，就是a对模数n的模反元素

五、模运算

让m去被n整除，只取所得的余数作为结果，就叫做模运算。

举个例子：

1	10 mod 4=2、8 mod 3=2

六、同余

给定一个正整数m，如果两个整数a和b满足a-b能被m整除，即(a-b) mod m=0，
那么就称整数a与b对模m同余，记作a≡b (mod m)，同时可成立a mod m=b

而且同余与模运算是不同的

1	a≡b (mod m)仅可推出b=a mod m

七、欧几里德算法

欧几里德算法是用来求两个正整数最大公约数的算法
计算公式gcd(a,b) = gcd(b,a mod b)

计算方法：

用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止 （辗转相除法）

八、扩展欧几里德算法

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式 ax + by = gcd(a,b)

int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int k=x;
    x=y;
    y=k-a/b*y;
    return d;
}

需要的数学知识已经了解完了，接下来就来学习RSA

RSA算法

（一）、生成密钥过程：

一、随机选择两个不相等的质数p和q

二、计算p和q的乘积n

三、计算n的欧拉函数φ(n)

四、随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质

五、计算e对于φ(n)的模反元素d

六、将n和e封装成公钥，n和d封装成私钥

下面就通过一个列子来执行一遍

一、选取两个不相等的质数p=11 q=13
二、n=p*q=143
三、φ(n)=(p-1)(q-1)=10*12=120
四、从1<e<60, 随机选取一个e,这里选取7
五、根据欧拉定理	e*d ≡ 1 (mod φ(n))，该公式又可转化为e*d - 1 = kφ(n)
所以7*d+120*k=1,这个方程可以由扩展欧几里得算法（辗转相除法）来得出结果：
六、120 = 7 * 17 + 1
	17 = 17 * 1
	//余数放前面
	1 = 120 * 1 + 7 * (-17)
	1 = 120 * 1 + 7 *(-17)
	故d = -17 k = 1
	在RSA中d必须是正整数，所以将它翻转
	d=120 + （-17）=103
	故公钥为（n,e）=(143,7)
    私钥为（n,d）=(143,103)

（二）、加密解密过程

求出公钥和私钥，就可以对信息进行加密和解密

一、通过公钥进行加密（n,e）

设明文为M，密文为C，则加密公式为：

假设明文为13，则

1 2	M^e mod n ≡ c 13^7 mod 143 = 117

二、通过私钥进行解密（n,d）

密文为C，明文为M，则解密公式为：

1 2	C^d mod n ≡ M 117^103 mod 143 = 13

换句通俗的话说C的d次方除以n的余数为M

同理可以 公钥加密、私钥解密、私钥签名、公钥验签。

(三)、RSA安全性

在已知n和e的情况下即（公钥），能否推导出d？

（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。

（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。

（3）n=pq。只有将n因数分解，才能算出p和q。

但现实生活中，不可能跟我们举例子一样那么小，而且大整数的因数分解，是一件非常困难的事情，例如：

12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413

没法对这个整数进行因数分解，过于大了，而且目前破解的只有暴力破解。

总结：RSA中涉及数学的知识点比较多，本文只做了初略的介绍，如:加密解密中 C = M^e % n 和 M = C^d % n 未做详细的证明。

（四）、代码实践

package main

import (
	"crypto/rand"
	"encoding/base64"
	"encoding/pem"
	"errors"
	"fmt"
	"crypto"
	"crypto/rsa"
	"crypto/x509"
	"io/ioutil"
	"testing"
)

func TestRSA(t *testing.T) {
	str := "will be best"
	base64Sig,_ := RSASign([]byte(str),"./files/private.pem")
	fmt.Println("签名后信息",base64Sig)

	err := RSAVerify([]byte(str),base64Sig,"./files/public.pem")
	if err == nil {
		fmt.Println("验证签名ok!")
	} else {
		fmt.Println("验证失败！")
	}
}

func RSASign(data []byte,filename string) (string,error) {
	//1.选择hash算法，对需要签名的数据进行hash运算
	myhash := crypto.SHA256
	hashInstance := myhash.New()
	hashInstance.Write(data)
	hashed := hashInstance.Sum(nil)
	//2.读取私钥文件，解析出私钥对象
	privateKey,err :=ReadParsePrivateKey(filename)
	if err != nil {
		return "",err
	}
	//3.RSA数字签名
	bytes,err := rsa.SignPKCS1v15(rand.Reader,privateKey,myhash,hashed)
	if err != nil {
		return "",err
	}
	return base64.StdEncoding.EncodeToString(bytes),nil
}

//公钥验证数据签名是否正确
func RSAVerify(data []byte,base64Sig,filename string) error {
	//- 对base64编码的签名内容进行解码，返回签名字节
	bytes,err := base64.StdEncoding.DecodeString((base64Sig))
	if err != nil {
		return err
	}
	//- 选择hash算法，对需要签名的数据进行hash运算
	myhash := crypto.SHA256
	hashInstance := myhash.New()
	hashInstance.Write(data)
	hashed := hashInstance.Sum(nil)
	//- 读取公钥文件，解析出公钥对象
	publicKey,err := ReadParsePublicKey(filename)
	if err != nil {
		return err
	}
	//- RSA验证数字签名
	return rsa.VerifyPKCS1v15(publicKey,myhash,hashed,bytes)
}

//读取公钥文件，解析出公钥对象
func ReadParsePublicKey(filename string) (*rsa.PublicKey,error) {
	//--1.读取公钥文件，获取公钥字节
	publicKeyBytes,err := ioutil.ReadFile(filename)
	if err != nil {
		return nil,err
	}
	//--2.解码公钥字节，生成加密对象
	block,_ := pem.Decode(publicKeyBytes)
	if block == nil {
		return  nil,errors.New("公钥信息错误")
	}
	//--3.解析DER编码的公钥,生成公钥接口
	publicKeyInterface,err :=x509.ParsePKIXPublicKey(block.Bytes)
	if err != nil {
		return nil,err
	}
	//--4.公钥接口转型成公钥对象
	publicKey := publicKeyInterface.(*rsa.PublicKey)
	return publicKey,nil
}
//读取私钥文件，解析出私钥对象
func ReadParsePrivateKey(filename string) (*rsa.PrivateKey,error) {
	//--1.读取私钥文件，获取私钥字节
	privateKeyBytes,_ := ioutil.ReadFile(filename)
	//--2.对私钥文件进行编码,生成加密对象
	block,_ := pem.Decode(privateKeyBytes)
	if block == nil {
		return nil,errors.New("私钥信息错误")
	}
	//3.解析DER编码的私钥,生成私钥对象
	privateKey,err := x509.ParsePKCS1PrivateKey(block.Bytes)
	if err != nil {
		return nil,err
	}
	return privateKey,err
}

参考：

密码学——RSA加密算法原理

阮一峰的RSA算法原理

wiki