0xGame2024:
week1:
Number-Theory-CRT
题面:
1 | from Crypto.Util.number import bytes_to_long, getPrime |
分析:
发现e,phi不互素,gcd(e,phi)=2
$$
gcd(e,\phi(n)) \neq 1\newline
m^e≡(m^{gcd(e,\phi(n))})^{\frac{e}{gcd(e,\phi(n))}}≡c\ (mod\ n)\newline
当gcd(e,\phi(n))较小时,可以直接对c开根,有两种情况:
$$
$$
\begin{cases}
m^e≡c<n,这种情况直接对c开e次方即可\
m^e≡c>n,这种情况需要在有限域下对c开方,一般先计算c_p = c\ mod\ p,c_q = c\ mod\ q,分别求出c_p,c_q在c下的e次方(可能有多个),然后使用CRT遍历所有组合,分别check得出明文
\end{cases}
$$
解释一下吧:
1 | R.<x> = Zmod(p)[] |
题解:
1 | from Crypto.Util.number import * |
week2:
RSA-IV
题面:
1 | from os import urandom |
1 | from Crypto.Util.number import getPrime, inverse, bytes_to_long |
分析:
很综合全面的一道题,考了sha256爆破,pwntools的使用和开方,dp泄露,wiener攻击和共模攻击
题解:
1 | from Crypto.Util.number import * |