解出flag

سؤال

flag.py

解出flag

Python

python
from math import gcd
n = 93977446509601491411273109183700477792476081212252100588514513996369916050240513858257713585313335366590846240370949831289684059273587772970292476296340120801189466605373324380976699533407970974215875662294283755613133719192114163547130089995306718768119144501566575807133141973499886356493323821201111393199
e = 65537
dp = 4646721143214293575763413674967142339122604220191663048739174575126624610789286103728040064106260338484738571999187838033377907298506299277252376843468857
c = 39842044108169653665655273759299059319749157454557086299529162182474598233474908300467494642550719706800866015430966154461050042032159169236220832726422011654867871818265524075008160875598938671421298968459869843510325230871429349578969045129760472874539862070944657591218420952191065002303403538259250208430
k = e*dp - 1
k.bit_length(), k


(527,
 304532163562835158074806842016321607479078112778701021225219284130073597117297443380024561681331983803274311793110773341193487910622207335733289021190418481208)

Python

python
from random import randint
def find_factor():
    for a in [2,3,5,7,11,13,17,19,23,29]:
        g = gcd(pow(a,k,n)-1, n)
        if 1<g<n:
            return a,g
    for i in range(100):
        a = randint(2,n-2)
        g = gcd(pow(a,k,n)-1, n)
        if 1<g<n:
            return a,g
    return None
res = find_factor()
res


(2,
 7181684830743211915734526035664597855840913894413286982954893032027016251233313918027180494324402976211544000403517907301044427663008379769203118130139103)

Python

python
a,g = res
g.bit_length()


512

Python

python
p = g
q = n//p
n%p, q.bit_length()


(0, 512)

Python

python
from Crypto.Util.number import long_to_bytes
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(c,d,n)
flag_bytes = long_to_bytes(m)
flag_bytes


b'flag{L34k_0f_Dp_Br34ks_RS4_E4sy}'

الفكرة

Providing flag with explanation in Chinese

I've computed everything and now have the flag. Here's a minimal explanation in Chinese:

"利用 dp = d mod (p-1), k = e * dp - 1 是 p-1 的倍数。对于随机选择的 a, a^k ≡ 1 mod p, 所以 gcd(a^k - 1, n) 得到 p."

Now I'll include the citation for the provided file (flag.py) directly in the response and include the final flag.

Thought for 34s

الإجابة

根据你给的 dp = d mod (p-1) 泄露（脚本里直接打印了 n,e,dp,c (flag.py)），可用经典做法：

令 $k=e\cdot dp-1$ ，则 $k$ 一定是 $(p-1)$ 的倍数
随便取 $a$ （例如 2），有 $a^k\equiv 1 \pmod p$
所以 $g=\gcd(a^k-1,n)$ 大概率直接得到 $p$ ，进而分解 $n=pq$ ，算出 $d$ 解密 $c$

解出来的 flag 是：

flag{L34k_0f_Dp_Br34ks_RS4_E4sy}

سؤال

Python

Python

Python

Python

Python

الفكرة

Providing flag with explanation in Chinese

الإجابة

مشاركة هذا السؤال والجواب