依然是很坐牢的一天

special_rsa

看了wp后发现原来这题在La佬的blog中有提到,后悔没有认真看La佬的文章了,还发现了模意义开根的问题(二次剩余)趁机狠狠恶补一下数论

题目源码:

from Crypto.Util.number import *
def getPrime1(bitLength, e):
    while True:
        i = getPrime(bitLength)
        if (i - 1) % e ** 2 == 0:
            return i
flag=b'DASCTF{????????????????????}'
m = bytes_to_long(flag)
lenth = ((len(bin(m)) - 2) // 2) + 9
e=113
p = getPrime1(lenth, e)
q = getPrime1(lenth, e)
n=p*q
print(f"n = {n}")
c1 = pow(m, e, n)
for i in range(26):
    lenth = ((len(bin(c)) - 2) // 2) + 9
    p = getPrime1(lenth, e)
    q = getPrime1(lenth, e)
    n=p*q
    print(f"n = {n}")
    c=pow(c,e,n)
print(f"e = {e}")
print(f"c = {c}")

思路

  • 根据n,利用分解网站依次写出对应p、q

  • 由p、q生成过程发现,$e|(q-1)$ 且 $e|(p-1)$,所以知道是简单的 e,phi不互素,且$gcd(e, phi) = e$的情况

  • 由$c=m^e\ (mod\ n)$,又$n=p*q$,可以得到

    $$\begin{cases}c\equiv m^e(mod\ p)\\c\equiv m^e(mod\ q)\end{cases}$$

    由于$e|(p-1), e|(q-1)$所以并不能求逆,而是要开根,那么如何开根呢

    引用一下La佬的文章:
    
    这种情况下,开平方根可以用Tonelli–Shanks algorithm,<a href="https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm">wiki</a>说这个算法可以扩展到开n次方根。
    
    在这篇paper里给出了具体的算法:Adleman-Manders-Miller rth Root Extraction Method。
    
    这个算法只能开出一个根,实际上开 e
    次方,最多会有 e
    
    个根(这题的情况下有0x1337个根)。
    
    如何找到其他根?
    
    StackOverflow – Cube root modulo P 给出了方法。
    
    如何找到所有的primitive 0x1337th root of 1?
    
    StackExchange – Finding the n-th root of unity in a finite field 给出了方法。

    不过可以用sagemath去解方程,构造这样的方程

    $$f=(m^e-c)\ mod\ p=0$$

    P.<a>=PolynomialRing(Zmod(p),implementation='NTL')
    f=a^e-c
    mps=f.roots()

    嗯?这里怎么没有$mod\ p$ ,因为已经定义了a的范围是$Zmod(n)$,

对于其中一次加密

def solve(p, q, c, pren=0, e=113):
    solutions = []

    P.<a> = PolynomialRing(Zmod(p),implementation='NTL')
    f = a**e - c
    mps = f.roots()

    P.<a> = PolynomialRing(Zmod(q),implementation='NTL')
    g = a**e - c
    mqs = g.roots()

    for mpp in mps:
        x = mpp[0]
        for mqq in mqs:
            y = mqq[0]
            solution = CRT_list([int(x), int(y)], [p, q])
            if solution < pren:
                solutions.append(solution)

    return solutions

可能有不止一个解,但RSA中m的值比n小,可以筛选出一些解,但还是会遇到无解的情况,这个时候就要回到上次多解的那一轮,把解换一下,自动筛选解没写出来,就用另一篇wp的结论吧

for i in range(27):
    '''
    中间略
    '''
    i =  26 - i
    
    if i == 21:
        c = solutions[0]
    elif i==9:
        c = solutions[-2]
    elif i==5:
        c = solutions[0]
    else:
        c = solutions[-1]

exp

还是看这个wp


pwnhub春季赛 rootRSA

刚才看了一下pwnhub春季赛的wp,没想到也有一道这样的题