Buckeye CTF Defective RSA writeup

Challenge

I use whatever exponent I want
ファイル：chall.py

from Crypto.Util.number import getPrime, inverse, bytes_to_long

e = 1440

p = getPrime(1024)
q = getPrime(1024)
n = p * q

flag = b"buckeye{???????????????????????????????}"
c = pow(bytes_to_long(flag), e, n)

print(f"e = {e}")
print(f"p = {p}")
print(f"q = {q}")
print(f"c = {c}")

# e = 1440
# p = 108625855303776649594296217762606721187040584561417095690198042179830062402629658962879350820293908057921799564638749647771368411506723288839177992685299661714871016652680397728777113391224594324895682408827010145323030026082761062500181476560183634668138131801648343275565223565977246710777427583719180083291
# q = 124798714298572197477112002336936373035171283115049515725599555617056486296944840825233421484520319540831045007911288562132502591989600480131168074514155585416785836380683166987568696042676261271645077182221098718286132972014887153999243085898461063988679608552066508889401992413931814407841256822078696283307
# c = 4293606144359418817736495518573956045055950439046955515371898146152322502185230451389572608386931924257325505819171116011649046442643872945953560994241654388422410626170474919026755694736722826526735721078136605822710062385234124626978157043892554030381907741335072033672799019807449664770833149118405216955508166023135740085638364296590030244412603570120626455502803633568769117033633691251863952272305904666711949672819104143350385792786745943339525077987002410804383449669449479498326161988207955152893663022347871373738691699497135077946326510254675142300512375907387958624047470418647049735737979399600182827754

How to solve

---

まず e=1440ということで、p-1, q-1と互いに素ではないのでいつも通りの復号ができません。eを素因数分解すると、2⁵ × 3² × 5 となります。次の3ステップで復号していきます。

c = c1 ^ 32 (=2^5) mod n
c1 = c2 ^ 9 (=3^2) mod n
c2 = m^5 mod n

Step 1

---

c = c1 ^ 32 mod n となるc1を以下のアルゴリズムで求めます。

ct ← c
for 0,5,1 :
  [ct = c1'^2 mod n となるc1'を求める] : ①
  ct ← c1'
c1 ← ct

①の部分はRabin暗号で求められます。Rabin暗号ではp, qがともに4で割ると余りが3になるものが条件ですが、今回はこれに合致しています。

Rabin暗号　復号方式

出典：Rabin cryptosystem - Wikipedia

上図のように復号していきます。c = c1'^2 mod n となるc1'は4通り考えられます。その4通りのc1'において、c1' = c1''^2 mod n となるc1''を求めます。これを繰り返すと 4⁵ 通りのc1が出てきそうですが、重複しているものや上図のr1~r4を2乗しても元に戻らないものなどを削ると3通りにまでc1の候補を減らすことができます。

Step 2

---

Step1で求めたc1を使って、c1 = c2 ^ 9 mod n となるc2を求めます。

ここで、9はp-1, q-1ともに互いに素なのでいつものRSAのように復号可能です。

Step 3

---

Step2で求めたc2を使って、c2 = c3 ^ 5 mod n となるc3を求めます。このc3は求めたいmに該当します。

5はp-1の約数ですが、その二乗の25はp-1の約数ではありません。また、q-1は5で割り切れません。以上より、カーマイケルの定理が利用できます。

p - 1 ≡ 0 (mod e) のときの RSA 復号方法 | y011d4.log

このサイトをそのまま使います。e=5と置き換えれば復号可能です。c2の候補3つを全て復号してみたら、flagのような形の平文が出力されました。

from Crypto.Util.number import *
import math
import gmpy2


e = 1440
p = 108625855303776649594296217762606721187040584561417095690198042179830062402629658962879350820293908057921799564638749647771368411506723288839177992685299661714871016652680397728777113391224594324895682408827010145323030026082761062500181476560183634668138131801648343275565223565977246710777427583719180083291
q = 124798714298572197477112002336936373035171283115049515725599555617056486296944840825233421484520319540831045007911288562132502591989600480131168074514155585416785836380683166987568696042676261271645077182221098718286132972014887153999243085898461063988679608552066508889401992413931814407841256822078696283307
c = 4293606144359418817736495518573956045055950439046955515371898146152322502185230451389572608386931924257325505819171116011649046442643872945953560994241654388422410626170474919026755694736722826526735721078136605822710062385234124626978157043892554030381907741335072033672799019807449664770833149118405216955508166023135740085638364296590030244412603570120626455502803633568769117033633691251863952272305904666711949672819104143350385792786745943339525077987002410804383449669449479498326161988207955152893663022347871373738691699497135077946326510254675142300512375907387958624047470418647049735737979399600182827754
n = p*q

#step1
g,yp,yq = gmpy2.gcdext(p,q)
yp = int(yp)
yq = int(yq)
assert p*yp+q*yq == 1
c_list = [c]
for _ in range(5):
    next_c_list = []
    print("="*30)
    for ct in c_list:
        mp = pow(ct,(p+1)//4,p)
        mq = pow(ct,(q+1)//4,q)
        r1 = (yp*p*mq+yq*q*mp)%n
        r2 = n-r1
        r3 = (yp*p*mq-yq*q*mp)%n
        r4 = n-r2
        
        if (r1**2)%n == ct: next_c_list.append(r1)
        
        if (r2**2)%n == ct: next_c_list.append(r2)
        
        if (r3**2)%n == ct: next_c_list.append(r3)
        
        if (r4**2)%n == ct: next_c_list.append(r4)
        

    c_list = list(set(next_c_list))
print(c_list,len(c_list))

#step2
e1 = 9
phi = (p-1)*(q-1)
d1 = inverse(e1,phi)
next_c_list = []
for ct in c_list:
    m = pow(ct,d1,n)
    next_c_list.append(m)
c_list = list(set(next_c_list))

#step3
phi //= 10
d = inverse(5,phi)
for k in range(2,5):
    L = pow(k,phi,n)
    for i in range(5):
        for ct in c_list:
            m = (pow(ct,d,n)*pow(L,i,n))%n
            print()
            print(long_to_bytes(m))

buckeye{r0ots_0f_uN1Ty_w0rk_f0r_th1s???}