RSA-learing

最近比赛的pwn题经常会穿插这些,让我有些摸不着头脑,所以学习一波。

基础知识

互质关系: 我觉得这个大家应该都知道,就是两个互质的数

欧拉函数: 这个函数的作用就是在小于等于n的数当中有多少个与n构成互质关系的数。

欧拉定理: 如果两个正整数a,n互质则n的欧拉函数可以使得 a^Φ(n) = 1(mod n) ps:这里的等于是三横线等于。

模反元素: 就是一个公式和上面一样如果正整数a,n互质,那么一定可以找到整数b,使得ab-1能被n整除。

如上感觉就是为了保证是质数,菜鸡如是理解。。

那么有了上面的数学基础可以继续往下看了

密钥

这里我们需要生成私钥和公钥

first step

随机选取两个不相等的质数 pq

second step

有了pq 那么久可以求出n

n = p * q

所求出来的就是密钥的长度,按照二进制位来计算总共几位。

third step

计算出欧拉函数Φ(n)

Φ(n) = (p-1)*(q-1)

four step

随机选择一个整数e
条件:

1 < e < Φ(n)

e与Φ(n)互质

five step

计算e 对于 Φ(n)的模反元素d

ed -1 = k*Φ(n)

期可以转化为对二元一次方程的求解

ex - 1 - y*Φ(n) =0

同理已知eΦ(n)即求得x,y的值

封装

公钥封装为(n,e)

私钥封装为(n,d)

安全性

这里不是密码大课堂。。我也只是个密码小白,大概看了资料期主要的问题在于n有可能被因数分解,但是这种情况是在n并不复杂的情况下。其他不说了,做不来密码题,做不来密码题哈哈哈,不过还是挺有趣的。

加密解密

这是最激动人心的时候了,这时候才知道原来整个过程并不难。。emmmm。。不知道当时自己为什么这么惧怕这东西哈哈哈。

加密->公钥运用

m^e mod n = c

解密

c^d mod n = m

好了不知道大家看到这里会不会觉得rsa其实整个过程对于我们需要运用的人来说并不难。当然研究它的大佬们的高度和我这种菜鸡是不一样嘻嘻。

这里还有一些为什么私钥能够推出公钥,也就是为什么解密公式能够成立。给出参考链接
http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

参考

阮一峰大佬的博客,深入浅出的解释了。

http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html