1
[ichunqiu-crypto]writeup【loading】
source link: https://scorpionre.github.io/2022/01/24/ichunqiu-crypto-writeup/#IceCTF-Round-Rabins%E3%80%90Cipolla%E3%80%91
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[ichunqiu-crypto]writeup【loading】
[ichunqiu-crypto]writeup
[phrackCTF]BrokenPic
题面：这里有个图片，可是好像打不开？
给出一个 bmp 图片
[IceCTF]Round Rabins【Cipolla】
发现 n 能开平方，提示 rabin，e 应为 2，所以转化为下式求 m 的值
c=m2(modp2)c = m^2 (mod\ p^2)
c=m2(mod p2)
先利用 Cipolla 算法求得 r，使得（本题中 k 为 2）
a=r2(modp) 所以 (r2−a)k=0(modpk) 二项式分解 (r2−a)k=t2−u2a=0(modpk)t2u−2=a=x2(modpk) 所以 x=t∗u−1(modpk) 即最后所求 ma = r^2 (mod\ p)
\\ 所以 (r^2-a)^k = 0 (mod\ p^k)
\\ 二项式分解 (r^2-a)^k=t^2-u^2a=0 (mod\ p^k)
\\t^2u^{-2} = a = x^2 (mod\ p^k)
\\ 所以 x = t*u^{-1} (mod p^k)
\\ 即最后所求 m
a=r2(mod p) 所以 (r2−a)k=0(mod pk) 二项式分解 (r2−a)k=t2−u2a=0(mod pk)t2u−2=a=x2(mod pk) 所以 x=t∗u−1(modpk) 即最后所求 m
利用平方差公式得到方程组，求解得 t、u
（r−a2)k=t−ua2(r+a2)k=t+ua2（r-\sqrt[2]{a})^k = t-u\sqrt[2]{a}
\\(r+\sqrt[2]{a})^k = t + u\sqrt[2]{a}
（r−2a)k=t−u2a(r+2a)k=t+u2a
Cipolla 算法求 r
首先找到一个 a 使得
(a2−n)(p−1)/2=−1(modp) 令 i2=a2−n(a^2-n)^{(p-1)/2} = -1 (mod\ p)
\\ 令 i^2 = a^2 - n
(a2−n)(p−1)/2=−1(mod p) 令 i2=a2−n
def find_a(n,p):
更一般的情况：先对 n 进行质因数分解，再使用中国剩余定理
n=p1k1∗p2k2∗p3k3n=p1^{k1} * p2^{k2} * p3^{k3}
n=p1k1∗p2k2∗p3k3
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK