彩笔
2022-12-21

RSA解密技巧

保存一些推导好的结论

已知n 且p、q相邻

线索是在加密脚本中可以找到如下类似代码
1
2
3
p = getPrime(512)
q = int(gmpy2.next_prime(p))
n = p*q
如下代码解出p、q
1
2
3
4
# pq相邻 为n开方
n2 = int(gmpy2.iroot(n, 2)[0])
p = sympy.nextprime(n2)
q = n//p
加以验证
1
2
print(p*q)
print(n == p*q) #返回True
q = sympy.nextprime()，意味着 p 和 q 是相邻的素数，非常接近，于是可以将 N 开平方根，这个数的 nextprime 就为 q

$q$ 与 $phi(q^2)$ 关系

题目给出
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from Crypto.Util.number import *
import gmpy2
from flag import flag

p=getPrime(512)
q=getPrime(512)
r=getPrime(512)
n=p*q*r
e=65537
m=bytes_to_long(flag)

def Euler(x):
    res=0
    for i in range(1,x):
        if gmpy2.gcd(i,x)==1:
            res+=1
    return res

P=p**3
Q=q**2
c=pow(m,e,n)

print(P)
print(Euler(Q))
print(c)
print(n)
#P = 1686761823519516525084824311416810253107853832929411677237594989001281261421956188747941222367576127569696216513071075733130132251383529469095077597202999362675041210639065389821237728348981344440193122126487447235175127680730304754656661704596111547454161716607787386914764780833658069534913186485846587027674567133467341836048413431174183101579802349498153899249182793495245916757355079598668221097821452488627067390724198617676379698358212167618567704428433303
#EQ = 54800501457630149544580145188029519076092032026436445384163914536965196942938808746487258773679836358732387355329080483568564046906919385574994390974732491368590525875801103056613954297623835159311237599961507385582029709732950222118171961946571285930711702624160354541459438994349318149872111029043942485620
#c = 568846080701555049788706647255668980211679838950729382006912035332305772256748203239331545262283165739670330060735508231578298253855583985677482008855909565463834639005910652510802915373310537390293061001384655286359323437737989289787972131460392977341024828530868508329336263146882773903176326250063921456707975853839017504122823304303509269793133132036479219404842827556015566627129747816769486873563843578029479179692030808518925753268233301452280242586076493
#n = 1069981867450019752454430625015273180922733107799929958042241890002915414684562764186875387471850290817321430141222917656674447229697676236077201897275059270515637506529666384968535578683380559782336910645306992981172862940944536463561840412558764760962107958365575095435157363812028759723055357681895134974760386884254380189603418912937553755099672511307377054933171384741715642510754214768859689909974996095149155241791151425031489280537907842378844226410097051
解出q

Euler(q^2) = q * (q-1)，那么 q-1 < sqrt(Euler(q^2)) < q.(已翻译)

rain: Euler(q^2) = q * (q-1) 推导过程
$$\begin{aligned}\phi(q^2) &= q^2 - q \ &= q*(q - 1)\ &= q *\phi(q)\end{aligned}$$
此处待上传一份定理
设 $p$ 是素数， $a$ 是一个正整数，那么
$$\phi(p^a)=p^a-p^{a-1}$$
证明

不超过 $p^a$ 且和 $p$ 不互素的正整数就是那些不超过 $p^a$ 且能够被 $p$ 整除的整数，即 $kp$，其中 $1<=k<=p^{a-1}$. 因为恰有 $p^{a-1}$ 个这样的整数，所以存在 $p^a-p^{a-1}$ 个不超过 $p^a$ 且和 $p^a$ 互素的正整数. 所以 $\phi(p^a) = p^a - p^{a-1}$ .

LQX: 关键在于 Euler(q**2) = q * Euler(q)
lov3: Euler(q) = q - 1

1
2
Eq = gmpy2.iroot(EQ, 2)[0] # 求平方根
q = Eq + 1

Q: 为什么可以用gcd(rsa1,N)计算出 S，其背后的数学原理是什么？
已告知有 rsa1 = RA * S , N = R * S * A

A: 因为 rsa1 和 N 都有相同的因子 S。这只是一种初等算术。例如，令 p,q,r 为不同的素数。然后 gcd(pq, pr) = p。
代码验证如下

1
2
3
4
5
6
7
from Crypto.Util.number import *
import gmpy2
p=getPrime(14)
q=getPrime(14)
r=getPrime(14)
print(p, q, r)
print(gmpy2.gcd(p*q, p*r))

待更新。。。

彩笔

彩笔

熟练拼写:XCPC,Crypto