day1
写的笔记只用于提供自己学习复盘和督促自己学习，资料应该基本都是风二西师傅的，在bilibili看到，在此提供师傅的一些链接
【CTF-加密】RSA之leak=d+p+q
【CTF-加密】RSA之leak=d+p+q_哔哩哔哩_bilibili
[3.RSA_2022收集/P01 题目/P32 l=d+p+q · 风二西/rsa_f2x - 码云 - 开源中国](https://gitee.com/fengerxi/rsa_f2x/tree/master/3.RSA_2022收集/P01 题目/P32 l=d+p+q)
import libnum
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
m=libnum.s2n(flag)
p=libnum.generate_prime(512)
q=libnum.generate_prime(512)
e = 0x10001
n = p * q
c = pow(m, e, n)
d=libnum.invmod(e,(p-1)*(q-1))
leak = d+p+q
print(f'{e = }')
print(f'{c = }')
print(f'{n = }')
print(f'{leak = }')
l
e
a
k
=
d
+
p
+
q
leak = d+p+q
leak=d+p+q
p
h
i
=
(
p
−
1
)
∗
(
q
−
1
)
=
n
−
(
p
+
q
)
+
1
phi=(p-1)*(q-1)=n-(p+q)+1
phi=(p−1)∗(q−1)=n−(p+q)+1
d
=
l
e
a
k
−
(
p
+
q
)
d = leak-(p+q)
d=leak−(p+q)
c
d
m
o
d
n
=
m
c^dmodn=m
cdmodn=m
c
l
e
a
k
∗
c
−
(
p
+
q
)
m
o
d
n
=
m
c^{leak}*c^{-(p+q)}modn=m
cleak∗c−(p+q)modn=m
欧拉定理： a p h i ( n ) m o d n = 1 a^{phi(n)}modn=1 aphi(n)modn=1
问题：
c
(
p
+
q
)
m
o
d
n
=
?
c^{(p+q)}modn=?
c(p+q)modn=?
c
p
h
i
(
n
)
m
o
d
n
=
1
c^{phi(n)}modn=1
cphi(n)modn=1
c
n
−
(
p
+
q
)
+
1
m
o
d
n
=
1
c^{n-(p+q)+1}modn=1
cn−(p+q)+1modn=1
c
n
+
1
∗
c
−
(
p
+
q
)
m
o
d
n
=
1
c^{n+1}*c^{-(p+q)}modn=1
cn+1∗c−(p+q)modn=1
结论 c n + 1 m o d n = c ( p + q ) m o d n c^{n+1}modn = c^{(p+q)}modn cn+1modn=c(p+q)modn
回到式子 c l e a k ∗ c − ( p + q ) m o d n = m c^{leak}*c^{-(p+q)}modn=m cleak∗c−(p+q)modn=m
c l e a k ∗ c − ( n + 1 ) m o d n = m c^{leak}*c^{-(n+1)}modn=m cleak∗c−(n+1)modn=m
最终结果 c l e a k − ( n + 1 ) m o d n = m c^{leak-(n+1)}modn=m cleak−(n+1)modn=m
# exp:
e =
c =
n =
leak =
from Crypto.Util.number import *
# 原本的样子m = pow(c,d,n)
m=pow(c,leak-n-1,n)
flag = long_to_bytes(m)
print(flag)
【CTF-加密】RSA之 l e a k = p q m o d n + q p m o d n leak=p^qmodn+q^pmodn leak=pqmodn+qpmodn
【CTF-加密】RSA之leak=pq%n+qp%n_哔哩哔哩_bilibili
[3.RSA_2022收集/P01 题目/P33 pow(p, q, n) + pow(q, p, n) · 风二西/rsa_f2x - 码云 - 开源中国](https://gitee.com/fengerxi/rsa_f2x/tree/master/3.RSA_2022收集/P01 题目/P33 pow(p, q, n) + pow(q, p, n))
import libnum
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
m=libnum.s2n(flag)
p=libnum.generate_prime(512)
q=libnum.generate_prime(512)
e = 0x10001
n = p * q
c = pow(m, e, n)
leak = (pow(p, q, n) + pow(q, p, n)) % n
print(f'{e = }')
print(f'{c = }')
print(f'{n = }')
print(f'{leak = }')
费马小定理：
a p m o d p = a m o d p a^pmodp=amodp apmodp=amodp
a p − 1 m o d p = 1 a^{p-1}modp=1 ap−1modp=1
模拟方法：
自己试着按照题目给的算法运行，去看有没有什么相等的数值，或者找出一些突破点
比如这个题中的 l e a k = ( p o w ( p , q , n ) + p o w ( q , p , n ) ) leak = (pow(p, q, n) + pow(q, p, n)) % n leak=(pow(p,q,n)+pow(q,p,n))
l e a k = p + q leak=p+q leak=p+q
l e a k 1 = ( p o w ( p , q , n ) = p , l e a k 2 = ( p o w ( q , p , n ) = q leak1 = (pow(p, q, n) = p,leak2 = (pow(q, p, n) = q leak1=(pow(p,q,n)=p,leak2=(pow(q,p,n)=q
结论：
l e a k = ( p o w ( p , q , n ) + p o w ( q , p , n ) ) leak = (pow(p, q, n) + pow(q, p, n)) % n leak=(pow(p,q,n)+pow(q,p,n))
l e a k 1 = ( p o w ( p , q , n ) = p , l e a k 2 = ( p o w ( q , p , n ) = q leak1 = (pow(p, q, n) = p,leak2 = (pow(q, p, n) = q leak1=(pow(p,q,n)=p,leak2=(pow(q,p,n)=q
# exp:
e =
c =
n =
leak =
from Crypto.Util.number import *
# leak=p+q
phi=n-leak+1
d = inverse(e,phi)
m=pow(c,d,n)
flag = long_to_bytes(m)
print(flag)
【CTF-加密】rsa_dp泄露新解析—e较大的情况
【CTF-加密】rsa_dp泄露新解析_哔哩哔哩_bilibili
[3.RSA_2022收集/P01 题目/P08 dp泄露 · 风二西/rsa_f2x - 码云 - 开源中国](https://gitee.com/fengerxi/rsa_f2x/tree/master/3.RSA_2022收集/P01 题目/P08 dp泄露)
import gmpy2
import libnum
import uuid
flag = "flag{" + str(uuid.uuid4()) + "}"
m = libnum.s2n(flag)
p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
e = libnum.generate_prime(128)
n = p * q
phi = (p - 1) * (q - 1)
d = gmpy2.invert(e, phi)
dp = d % (p - 1)
c = pow(m, e, n)
print("n=", n)
print("e=", e)
print("c=", c)
print("dp=", dp)
常规版本的e相对小，为65537，k会在1-65537内，采用的方法是爆破k
# exp:
for k in range(1, 65537):
p = (dp * e - 1) // k + 1
if n % p == 0:
q = n // p
break
这道题的exp：
# exp:
n=
e=
c=
dp=
import libnum
from Crypto.Util.number import *
p=libnum.gcd(pow(2,dp*e,n)-2,n)
q=n//p
phi=(p-1)*(q-1)
d=inverse(e,phi)
m=pow(c,d,n)
flag = long_to_bytes(m)
print(flag)
2024-11-09
晚安！