参考Kicky_Mu佬的学习ing
[ISG 2023]FakeRSA
考点:费马小定理
题面:
1 | from Crypto.Util.number import * |
分析:
$$
g_1≡g^{r_1(p-1)}\ mod\ p\
g_2≡g^{r_2(p-1)}\ mod\ p\
$$
一眼丁真,用费马小定理,可以得到:
$$
g_1≡g^{r_1(p-1)}\ mod\ p≡1 \ mod\ p \
g_2≡g^{r_2(q-1)}\ mod\ q≡1 \ mod\ q\
$$
所以我们可以知道
gcd(g1-1,n)=p
gcd(g2-1,n)=q
再看密文的形式:
$$
c_1≡m^eg_1^s\ mod\ n\
c_2≡m^eg_2^s\ mod\ n\
$$
再次利用费马小定理可以得到
$$
c_1≡m^eg_1^s\ mod\ n≡m^e \ mod\ p\
c_2≡m^eg_2^s\ mod\ n≡m^e \ mod\ q\
$$
那么解密即为:
$$
m = c^{dp}\ mod\ p
$$
题解:
1 | from Crypto.Util.number import * |
[GKCTF 2021]RRRRsa
考点:费马小定理,二项式定理
题面:
1 | from Crypto.Util.number import * |
分析:
$$
hint1=(2020p_1+q_1)^{202020}\ mod\ n_1\
hint2=(2021p_1+212121)^{q_1}\ mod\ n_1\
$$
一般看到指数上是这种p,q之类的,先想到了费马小定理:
$$
hint2≡(2021p_1+212121)^{q_1}\ mod\ q_1 ≡2021p_1+212121\ mod\ q_1
$$
$$
hint2-212121≡(2021p_1)\ mod\ q_1
$$
对于hint1这样的直接二项式展开
$$
hint1≡(2020p_1)^{202020}+q_1^{202020}\ mod\ n_1 ≡(2020p_1)^{202020}\ mod\ q_1
$$
凑项:
$$
2021^{202020}hint1-2020(hint2-212121)^{202020} ≡ 0\ mod\ q_1\ =kq_1
$$
然后与n1求最大公因数即可
$$
hint3=(2020p_2+2021q_2)^{202020}\ mod\ n_2\
hint4=(2021p_2+2020q_2)^{212112}\ mod\ n_2
$$
$$
hint3≡(2020p_2)^{202020}\ mod\ q_2\
hint4≡(2021p_2)^{212121}\ mod\ q_2
$$
凑项:
$$
(2021^{202020}hint3)^{212121}-(2021^{212121}hint4)^{202020} = kq_2
$$
然后与n2求最大公因数即可
以上在进行大指数运算的时候可以模对应的n,这样更准确迅速
题解:
1 | from Crypto.Util.number import * |