RSA 学习档案
基本原理
随机选择两个质数p，q
模数n=p*q
φ(n)=(p−1)(q−1)
选择加密指数e: 1 < e < φ(n)
计算机密指数d: e*d % φ(n) = 1
c = m ^ e % n
m = c ^ d % n
常见攻击方式
模数分解
1.直接分解
n小于256bit可以本地暴力分解。
去factordb查询是否有已经分解成功的结果。
2.给出多个n，可以尝试计算n之间的最大公约数。
from libnum import *
n1 = 9051013965404084482870087864821455535159008696042953021965631089095795348830954383127323853272528967729311045179605407693592665683311660581204886571146327720288455874927281128121117323579691204792399913106627543274457036172455814805715668293705603675386878220947722186914112990452722174363713630297685159669328951520891938403452797650685849523658191947411429068829734053745180460758604283051344339641429819373112365211739216160420494167071996438506850526168389386850499796102003625404245645796271690310748804327
n2 = 13225948396179603816062046418717214792668512413625091569997524364243995991961018894150059207824093837420451375240550310050209398964506318518991620142575926623780411532257230701985821629425722030608722035570690474171259238153947095310303522831971664666067542649034461621725656234869005501293423975184701929729170077280251436216167293058560030089006140224375425679571181787206982712477261432579537981278055755344573767076951793312062480275004564657590263719816033564139497109942073701755011873153205366238585665743
print gcd(n1, n2)
>>> 1564859779720039565508870182569324208117555667917997801104862601098933699462849007879184203051278194180664616470669559575370868384820368930104560074538872199213236203822337186927275879139590248731148622362880471439310489228147093224418374555428793546002109
从而找到n的因数。
3.pq相差过大时或过近，使用yafu
(没分解之前我怎么知道pq差的多不多？好像就是碰运气上吧。。。)
>pcat<
yafu直接把二进制文件复制到/usr/bin中即可直接终端使用。在nextrsa中level5，使用yafu尝试一下，很快就出来，分解成功意味着本层攻击通过。
pn@Dp:~$ yafu
// :: v1.34.5 @ Dp, System/Build Info:
Using GMP-ECM 6.4., Powered by GMP 5.1.
detected Intel(R) Core(TM) i7-6700HQ CPU @ .60GHz
detected L1 = bytes, L2 = bytes, CL = bytes
measured cpu frequency ~= 2592.050760
using random witnesses for Rabin-Miller PRP checks ===============================================================
======= Welcome to YAFU (Yet Another Factoring Utility) =======
======= [email protected] =======
======= Type help at any time, or quit to quit =======
===============================================================
cached primes. pmax =
>> factor(0x1daf9fab45ff83e751bf7dd1b625879b3a8c89d4a086e0806b31e2a2cc1c4c1bc8694db643acc4911f3d143c1951f006df9e0a7282b65839d84b36102b8f2307c4eaa561e65435350d9cb2b978ace582535ae00d948546520252d0f59d82dcfa59bac33812da5b12c18de35bfbabfa481aa9d59a7ba00bc74cc1b55077c1ff72aff50493)
fac: factoring
fac: using pretesting plan: normal
fac: no tune info: using qs/gnfs crossover of digits
div: primes less than
rho: x^ + , starting iterations on C317
rho: x^ + , starting iterations on C317
rho: x^ + , starting iterations on C317
pm1: starting B1 = 150K, B2 = gmp-ecm default on C317
Total factoring time = 5.0378 seconds ***factors found*** P9 =
P309 = ans =
>>
低指数攻击
低加密指数
1.e=3 时小明文攻击
e=3时，如果明文过小，导致m ^ 3 < n,(一般此时len(c) < len(n))失去加密作用，可以直接对c开三次方(或者尝试对(c+k*n)开三次方)
i=0
while 1:
if(gmpy2.root(c+i*N, 3)[1]==1):
print gmpy2.root(c+i*N, 3)
break
i=i+1
安恒7月月赛中rsa：
c的长度远小于n，所以直接开方获得。
Attention: 爆破(c + i*n)时，i并不总是很小，jarvis OJ 上ExtremelyhardRSA，为flag加了padding，直到i=118719488时才拿到结果。
2.广播攻击
加密指数较低，使用相同的加密指数加密相同的消息(m, e相同)
关于cx的计算和原理参见中国剩余定理和RSA算法,将算式迁移到此进行对比分析
# 2(c1) = x mod 3(n1)
# 3(c2) = x mod 5(n2)
# 2(c3) = x mod 7(n3)
# x 即相当于 m^e
n = [n1, n2, n3]
c = [c1, c2, c3]
N = n1 * n2 * n3 = 105
Ni = N / n[] = [35, 21, 15]
# 求逆元T[]
# Ni * T = 1 mod n1
T = []
for i in xrange(3):
T.append(long(invert(Ni[i], n[i])))
# T = [2, 1, 1]
cx = sum(Ni[i]*T[i]*c[i]) % N
m = cx ^ (-3)
nextrsa中level9给出了三组{n:c},并且声明m,e相同，且e=3
# c1=pow(m,e,n1),c2=pow(m,e,n2),c3=pow(m,e,n3)
# e=0x3
可以根据以上原理进行运算
from gmpy2 import invert
def broadcast(n1, n2 ,n3, c1, c2, c3):
n = [n1, n2, n3]
C = [c1, c2, c3]
N = 1
for i in n:
N *= i
Ni = []
for i in n:
Ni.append(N / i)
T = []
for i in xrange(3):
T.append(long(invert(Ni[i], n[i])))
X = 0
for i in xrange(3):
X += C[i] * Ni[i] * T[i]
m3 = X % N
m = iroot(m3, 3)
return m[0]
3.Coppersmith定理攻击
适用于e较小(==3 ?)且明文中有 2/3 的bit已知，可以求出明文中全部的bit.
日本大佬的博客看不懂。。。以后再对着翻译来吧，反正坑是这么挖下了，什么时候填，填不填的就是另一回事了
低解密指数
1.Wiener attack
d < (1/3) N^(1/4)时,（e很大），采用wiener
python实现的高效攻击方法，e很大的时候，执行脚本，输入e， n即可。
//采用相同的n，不同的公钥e加密五次和采用五个e相乘加密一次效果相同，因此同模多次加密有可能采用低解密指数攻击
共模攻击
多组加密中，使用相同的模数和互质的e对相同的明文进行加密(m, n相同)
可以在不分解n和求出d的情况下获得m
模运算中，负数次幂的运算方式：c2^s2 (s2<0)，计算c2的模反元素c2’，计算c2’ ^ (-s2)
nextrsa 中level8：
c1=pow(m,e1,n),c2=pow(m,e2,n)
使用同样的n，不同的加密指数加密m
from libnum import invmod
from libnum import xgcd
def commonN(n, e1, c1, e2, c2):
s1, s2, _ = xgcd(e1, e2)
if s1 < 0:
s1 = -s1
c1 = invmod(c1, n)
# invmod 求模反元素
if s2 < 0:
s2 = -s2
c2 = invmod(c2, n)
m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
return m
Ref
CTF中RSA常见攻击方法
Err0rzz
M4x的nextrsa
Freebuf-CTF中RSA思路技巧
阮一峰RSA算法原理
作者：辣鸡小谱尼
出处：http://www.cnblogs.com/ZHijack/
如有转载，荣幸之至！请随手标明出处；