RSA公钥加密算法

阅读数:28 评论数:0

跳转到新版页面

分类

hacker

正文

一、概述

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