从数盲到口算 ——带你玩转RSA加密算法(一)

RSA是一种非对称加密算法,它由 公钥(ne),私钥(nd),明文M和密文C组成。

首图.png

RSA是一种非对称加密算法,它由 公钥(n/e),私钥(n/d),明文M和密文C组成。我们做CTF题目时,一般题目中会给出公钥和密文让我们推出对应的私钥或者明文。RSA的相关公式都写在上面脑图中,在正式讲解RSA加密算法前我们先来普及一波数学的基本知识。

一、相关数学基础


1.1素数和互质数

素数也称质数,它的定义为除本身和 1 的乘积外,不能表示其他数的乘积。比如2,3,5,7,11,13,17……等都是素数。

互素数也称互质数,定义是公约数只有1的两个自然数,如:

 1和任何自然数 1 & 2

 任意 2个质数 2 & 3

 相邻2个自然数 4 & 5

 3 & 10 、7 & 10 、5 & 26等等

1.2模指数运算

模运算就是取余数,如5 mod 3 =2。而模指数就是,先做指数运算在做mod运算。

如:53 mod 7 = 125 mod 7 =6

我们可以使用python的pow()来求解模指数运算。

 1.2.png

1.3同余运算

两个整数a,b,它们除以整数M所得的余数相等:a ≡ b(mod m),比如说5除3余数为2,11除3余数也为2,于是可写成11 ≡ 5(mod 3)。

二、RSA加密算法


2.1 加解密算法

前面已经说过,RSA是一种非对称加密算法,这个算法的特点就是明文使用公钥进行加密得到密文,而密文解密使用私钥来解。

2.1.png

所需的密钥对为n,d,e。密钥对是如何生成的?

2.2 生成密钥对

密钥对的生成步骤如下:n → Led (L作为生成过程中的中间数)

2.2.png

 

三、CTF题目实战


3.1 First Blood 已知p、q、e求d

题目链接 : http://www.shiyanbar.com/ctf/1828

题目:

在一次RSA密钥对生成中,假设p=473398607161,q=4511491,e=17,求解出d

此题直接告诉我们p、q、e,让我们求解d

而d的计算公式为d*e ≡ 1 (mod L*i)  ,i=1,2,3…,

由于1和任何数做mod都为1,所有该公式又可转换为:

d*e mod (L*i )=1 , i=1,2,3…。

d*e除(L*i)的余数为1,即d*e = (L*I) + 1 。

直接使用脚本进行实现。

Clipboard Image.png

求d的脚本,也可以又rsatool.py这个脚本来实现,需要安装gmpy这个模块,链接如下:

链接:http://pan.baidu.com/s/1bCDyoQ 密码:09gj

3.2 Double Kill  已知p、q、e和密文 求明文

题目链接 : http://www.shiyanbar.com/ctf/1979

题目:

Use RSA to find the secret message

直接跑上题脚本获取d:

3.2 1.png

3.2 2.png

 3.2 3.png

5577446633554466577768879988

3.3 Triple Kill  已知n、e和密文 求明文

题目链接 : http://www.shiyanbar.com/ctf/1918 

3.3 1.png

 

n=920139713,e=19

因式分解 n 用yafu 或者在线因式分解

使用yafu:链接:http://pan.baidu.com/s/1croXpO 密码:w43p

分解.png

在线地址:

http://www.atool.org/quality_factor.php

 在线地址.png

p=18443,q=49891

求d:

 d.png

d=96849619

解密:

 jiemi 1.png

 jiemi 2.png

flag{13212je2ue28fy71w8u87y31r78eu1e2}

3.4 Quadra Kill  已知公钥和密文 求明文

题目链接 : http://www.shiyanbar.com/ctf/1772  

题目:

 3.4 1.png

此题只给了公钥,并没有做分解,我们可以对题目所给的公钥进行分解。

python实现:

 Clipboard Image.png

open.png

或则使用openssl:

ssl.png

使用yafu分解n 的值

 n.png

rsa-d.py计算d 的值

 d 1.png

 d2.png

明文 = 密文d mod n

 mingwen.png

3.5 Penta Kill  已知公钥和密文 求明文

题目链接 : http://www.shiyanbar.com/ctf/730 

题目:

 3.5 tui.png

3.5 tu 2.png

 

分解公钥得n、e的值,然后求解d,这边提供另外一种求解d的方案,就是利用github上的一个开源项目

github: https://github.com/pablocelayes/rsa-wiener-attack

 git.png

 脚本.png

python脚本下载:链接:http://pan.baidu.com/s/1qXVhKpI 密码:fuef

三、总结

限于篇幅,本篇先到这里告一个断落,下期会带来一些有一定难度RSA题目的解法,敬请期待,让斗哥带你走上RSA超神之路吧!

640.webp.jpg

更多精彩
发表评论

已有 7 条评论

取消
Loading...

填写个人信息

姓名
电话
邮箱
公司
行业
职位
css.php