CTF中关于RSA算法的攻击方式
RSA算法本身是安全的.
但是他的不正确用法使得RSA算法的攻击成功率提高了.
RSA算法在之前的文章中详细的介绍了.其攻击的核心就是获取两个大素数p和q.
RSA算法也是针对c, m, e, d, n, p, q这几个参数展开的.
但是题目不会直接给出, 而是以其他方式间接给出,或者要求我们获取.
一种最常见的就是给出pem文件, 我们可以通过openssl(kali自带)提取.
openssl的用法:
密钥生成参数:
rsa指定密钥生成(对密钥的操作)
-inkey 指定私钥文件
-out 指定解密后的文件
-pubin 表示输入文件为公钥.
-pubout 输出公钥
-text 以明文形式输出各种参数
-modulus 输出模数值
从私钥中提取公钥:
openssl rsa -pubout -in <pr.pem> -out <pu.pem>
密钥加解密参数:
rsautl 对明文和密文的操作.
-in 输入文件
-inkey 输入的密钥
-encrypt 使用公钥加密
-decrypt 使用私钥解密
使用密钥解密文件.
openssl rsautl -decrypt -in <input.file> -inkey <pr.pem> -out <output.file>
使用密钥文件加密文件.
openssl rsautl -encrypt -in <input.file> -inkey <pr.pem> -out <output.file>
另一种则是有交互的,给一个IP,一个端口号,然后nc连接, 多轮交互,在交互中给出参数.
然后参数有了, 就开始各种各样的攻击.
一.模数分解
RSA算法题目中, 最简单的就是分解模n.
分解之后获得大素数p和q, 进而求得d.
在之前的文章中只写了RSA的理论部分,现在把代码补上.
以下写几个python脚本:
1. 已知e,p,q,求d:
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('逆元不存在')
else:
return x % m
e =
p =
q =
d = modinv(e, (p-1)*(q-1))2. 已知大数n, 求p,q.
给出一个大数n, 直接分解.
利用工具:
RSATool
利用在线网站:
分解完成之后, 就回到了上面1中的问题.
3.利用公约数
在一次加密中, 使用了两个大数n,
并且两个n都拥有相同的素因子,那么就可以直接通过欧几里得算法直接分解.
原理:
n1 = p * p1
n2 = p * p2
这种题目,一般会给出很多n, 而e可能是全部相同的.
直接上代码:
def gcd(a, b): if a < b: a, b = b, a while b != 0: temp = a % b a = b b = temp return a
通过脚本可以得到相同的素因子, 从而得到另一个素因子.
4.yafu
针对大整数的分解有很多种算法，性能上各有优异
有Fermat方法，Pollard rho方法，试除法，以及椭圆曲线法，连分数法，二次筛选法，数域分析法等等。
其中一些方法应用在RSA的攻击上也有奇效。
在p，q的取值差异过大，或者p，q的取值过于相近的时候，
Format方法与Pollard rho方法都可以很快将n分解成功
有个工具, 叫yafu, 下面的下载地址是基于window的.
当p和q的值相差较大或相差较小时, 可以使用这个工具.
下载地址:
用法:
解压到一个目录.为了方便使用, 将yafu-x64.exe改名成yafu.exe,
然后给这个目录添加path环境.
当有一个大数:
够大吧.
新建一个记事本, 把大数放里面, 在末位记得加一个换行.
然后执行:
yafu "factor(@)" -batchfile 1.txt
得到:
但是,原先的1.txt就没了.
二.第加密指数攻击
参数e, 也叫做加密指数. 在之前的文章中说到过, e是可以随意选取的
等待更新...
