阅读数:91 评论数:0

一、概述

1、基本步骤

（1）选择两个大素数p和q（大于$10^{100}$）

（2）令$n=p\times q$和$z=(p-1)\times (q-1)$ （n的长度就是密钥的长度，z为n的欧拉函数，RSA密钥一般是1024，重要的场合则为2048）

（3）选择d与z互质

（4）选择e，使$e \times  d = 1(mod \quad z) $

这样公钥为（e，n），私钥为（d，n）

这是一种非对称加密码算法

二、原理的理解

1、欧拉函数

任意给定正整数n，小于等于n的正整数之中，与n构成互质关系的个数，定义为$\varphi(n)$。

（1）对于素数p，$\varphi(p)=p-1$，对于两个素数p、q，$\varphi(pq)=pq-1$

（2）如果n可以分解成两个互质的整数之积，$n=p1\times p2$，则$\varphi(n)=\varphi(p1p2)=\varphi(p1)(p2)$。=$(p1-1)(p2-1)$

2、RSA的可靠性

那么有无可能在已知n和e的情况下，推导出d？

如果n可以被因数分解，d就可以被算出，也就意味着私钥被破解。可是，大整数的因数分解，是一件非常困难的事情。目前，除了暴力破解，还没有有效的方法。

三、加密和解密

1、加密要用公钥（e,n）

这里需要注意，加密信息m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。

所谓加密，就是算出下式的c：

$m^e\equiv c(mod\quad n)$

2、解密要用私钥（d，n）

$c^d\equiv m (mod\quad n)$

3、私钥解密的证明

为什么用私钥解密，一定可以正确地得到m。

$m^e\equiv c(mod\quad n)$于是c可以写成下面的形式

$c=m^e-kn$，将c代入要我们要证明的那个解密规则：

$(m^e-kn)^d\equiv m (mod\quad n)$ 它等同于求证

$m^{ed}\equiv m (mod\quad n)$

由于 $ed\equiv 1 (mod \varphi(n))$ ，所以

$ed = h \varphi(n)+1$，即

$m^{h \varphi(n)+1}\equiv m (mod\quad n)$

根据欧拉定理，$m^{\varphi(n) \equiv 1 (mod\quad n)}$

得到 $(m^{\varphi(n)})^h \times m \equiv m (mod\quad n)$

四、使用openssl生成RSA密钥对

1、安装openssl

2、生成私钥

openssl genrsa -out rsa_private_key.pem 1024

3、生成公钥

openssl rsa -in rsa_private_key.pem -out rsa_public_key.pem -pubout

4、修改私钥格式

openssl pkcs8 -topk8 -in rsa_private_key.pem -out rsa_private_key_pkcs8.pem -nocrypt