rsa的公钥加密私钥解密过程

发表于 2018-04-20 分类于密码学

Abstract

从一个初学者的角度,了解rsa的实现过程.在王里冲产出公钥和私钥.私钥自己保留,公钥传送给潘兴.潘兴把使用公钥加密后信息传给王里冲,王里冲可以使用私钥解开加密.获得信息.

前置知识

名词解析

王里冲：秘钥的生成方，生成公钥和私钥
潘兴：当然就是另一方喽
公钥,私钥 :公钥和私钥实际就分别是两个数对(n,e), (n,d), 其中(n,e)是公钥,(n,d)是私钥.n是两个质数的积.[1]
密钥长度: n用二进制表示的时候占用的位数,就是所说的密钥长度.[1]
素数: 就是质数.除了1和该数自身外，无法被其他自然数整除的数.(小时候学的数学课本忘记怎么说的.查了一下wiki.(orz))

正文

故事的背景,王里冲(男一)和潘兴(男二)想要做一个私密的py交易,事先需要沟通信息.这个信息不能别人知道.他们使用rsa.

潘兴向王里冲传递信息.(公钥加密, 私钥解密)

潘兴想要发送一段文字: I LOVE YOU!(此处不讨论中文字符).为了完成这个, 主要有三个步骤:

王里冲在自己本地生成公钥和私钥.
王里冲自己随机选择两个素数 p=23,q=47.可以得到$n=p*q=53*59=3127$

根据欧拉函数:
$$r=\phi(n)=(p-1)*(q-1)=52*58=3106$$
然后,选择一个数字e=3, e的选择标准是: e是1和r之间的一个质数,1< e< r.e和r当然也是相互是质数.这里的n和e也是将来分发的公钥.

接下来产生私钥,从数学上来讲,就是计算e相对的r的”模反元素”.使用这个公式:

$$ed ≡ 1 (mod (r))$$

这个公式的意思是r对ed取余数是1.
等价于:

$$ed+k*r=1$$

也等价于:

$$ed-1 = k*\phi(n)$$

带入数据就是:

$$3*d -1 = k * 3106$$

其中k是一个常数.这个方程可以用”扩展欧几里得算法(辗转相除法)“求解.

最后可以得到 d=2011.具体的计算过程放在附录1中.

所以公钥(n,e)就是(3127,3),私钥是(n,d)即(3127,2011);
王里冲公开发布公钥,所有人都可以得到公钥.当然潘兴也可以获得.这个地方rsa的特性保证了只用公钥不能或者说很难猜出私钥

潘兴用这个公钥,加密了自己的信息.通过公网传出给王里冲.

此处,潘兴获得的公钥(n,e),(3127,3)

由于rsa只能加密数字, 所以只能把要加密的信息按照一定的规则转化为数字.即将明文信息数字化.可以使用Unicode码的序号来表示这串数字.在英文范围内,Unicode与ASCII序号相同.把上面的”I LOVE YOU”转为数字就是
[ 73, 32, 76, 79, 86, 69, 32, 89, 79, 85 ]

js代码实现

//getCodePoint :: string -> [a]
function getCodePoint(str) {
    return str.split('').map((e) => e.charCodeAt(0))
    // console.log(codePoint);
}
out = getCodePoint('I LOVE YOU');
console.log(out);//[ 73, 32, 76, 79, 86, 69, 32, 89, 79, 85 ]

设待加密的信息m,加密后的信息是c, 然后加密的过程就是 m^e = c(mod n) (应该是一个三横线的等号), 等价于 m^e mod n = c.

在这里还会遇到一个问题就是如果m和e数字比较大的时候, 直接乘方会有数据溢出的风险.所以, 这里有一些专门的算法.可以参考附录2的算法.详细的信息可以搜索”高次幂函数取模算法”

let out = [ 73, 32, 76, 79, 86, 69, 32, 89, 79, 85 ];
const n = 3127;
const e = 3;
let c = out.map(ele => ele ** e % 3127);
console.log(c);//[ 1269, 1498, 1196, 2100, 1275, 174, 1498, 1394, 2100, 1233 ]

至此, 潘兴小哥把自己的信息加密好了, 然后通过公网传给王里冲

王里冲获得信息,用自己在私钥解密.同样,rsa的特性保证只有私钥才能解密出公钥加密的信息.

王总现在取得了潘兴的加密信息,只需要解密就可以看到了.

解密的过程和加密及其类似:c^d=m(mod n)((应该是一个三横线的等号))
,等价于 c^d mod n = m;
1
2
3
4
let m = c.map(ele => getMod(ele, d, n));
console.log(m);//[ 73, 32, 76, 79, 86, 69, 32, 89, 79, 85 ]
out = String.fromCodePoint(...m);
console.log(out);//I LOVE YOU
最后, 潘兴终于获得了王里冲发给自己信息.

总结

到目前为止，完成了从公钥加密，私钥解密的过程。接下来，还有一部分从私钥加密，公钥验证（挖坑），以及数字证书的签名问题(挖坑)。

参考资料

附录

17*d -1 = k * 3106的求解.d和k取整数

把等式右边移到左边, 可以得到 17*d + k*3106 = 1.

注意这里k的变成了原来-k,但是对于最终的结果没有影响,因为我们只是想找符合的参数

有两种方法:

方法一:辗转相除法

已知:3120y+17x = 1
- 3120 = 17*183+9
- 17 = 9*1 +8
- 9 = 8*1 + 1
  改写成余数的形式:
- 9 = 3120*1 + 17*(-183)
- 8 = 17*1 + 9*(-1)
- 1 = 9*1 + 8*(-1)
从最后一个式子开始, “倒回去” , 把上面式子的结果带入

1 = 9*1 + 8*(-1) = 9*1 + [17*1+9*9(-1)]
= 17*(-1)+9*2 = 17*(-1) + (3120*1+17*(-183))=
3120*2+17*(-367).

所以可以得到x=-367 , y=2;
计算出这个结果之后, 并没有结束,按照wiki的解释, 模逆元, 一般x取最小的正数, x = x+ kn = -367+k*3120 = 2753.所以y = 15;

方法二:

受wiki上一个矩阵解法的启发, 专门去搜了一下, 本质也是辗转相除法, 不过只是用矩阵表示出来.暂时先做记录, 以后可以优化(给自己挖坑)

求解过程的来自这里: http://www.mast.queensu.ca/~math418/m418oh/m418oh13.pdf

r_-1 = m = 3120, r_0 = n = 17

3120/17 =183…9, r_1 = 9, q_1= 183

17/9 = 1…8, r_2 = 8, q_2=1

9/8=1…1, r_3=1, q_3=1

8/1=8…0, r_4=0,q_4=8

构造如下的矩阵
每一次经过一个初等行变换

$$
\left(\begin{array}{cc}
1 & 0 & 3120\
0& 1 & 17
\end{array}\right)
$$

$$
\left(\begin{array}{cc}
0 & 1 & 17\
1& -183 & 9
\end{array}\right)
$$

$$
\left(\begin{array}{cc}
1& -183 & 9\
-1& 184 & 8
\end{array}\right)
$$

$$
\left(\begin{array}{cc}
-1& 184 & 8\
2& -367 & 1
\end{array}\right)
$$

$$
\left(\begin{array}{cc}
2& -367 & 1\
-17& 3120 & 0
\end{array}\right)
$$

2.暴力方法

数学原理:TODO

//a^b mod c
function getMod(a, b, c) {
    let result = 1;
    while (b--) {
        result = result * a % c;//这个算法的核心就是在迭代运算过程中进行取模运算
    }
    return result;
};

参考

mathjax中书写公式: https://www.zybuluo.com/Cesar/note/228458