TL;DR

  • $N=p^8qr$という形のMulti-Prime RSA
  • $ed \equiv 1\mod \phi(N)$となる$d$を用いて$c^d \bmod N$をくれる
  • 一見それを文字列に直して終わりに見えるが、パディングのせいでフラグが$p$の倍数になり、通常の復号が出来ない
  • $p$は求まるので$qr$を求めてこれで法をとったりしながらフラグを導出する

Prerequisite

  • RSA周りの細々とした数学
    • 法を取らずに表したり、別の法とすり替えたりするのがメイン

Writeup

#!/usr/bin/env python3
#
# Polymero
#

# Imports
from Crypto.Util.number import getPrime
import os

# Local imports
with open('flag.txt','rb') as f:
    FLAG = f.read()
    f.close()

# Key gen
P = getPrime(512//8)
Q = getPrime(256)
R = getPrime(256)
N = P**8 * Q * R
E = 0x10001

def pad_easy(m):
    m <<= (512//8)
    m += (-(m % (P**2)) % P)
    return m

# Pad FLAG
M = pad_easy(int.from_bytes(FLAG,'big'))
print('M < N    :',M < N)
print('M < P**8 :',M < (P**8))
print('M < Q*R  :',M < (Q*R))

# Encrypt FLAG
C = pow(M,E,N)
print('\nn =',N)
print('e =',E)
print('c =',C)

# Hint
F = P**7 * (P-1) * (Q-1) * (R-1)
D = inverse(E,F)
print('\nD(C) =',pow(C,D,N))

#----------------------------------------------------
#                       Output
#----------------------------------------------------
# M < N    : True
# M < P**8 : True
# M < Q*R  : True
#
# n = 68410735253478047532669195609897926895002715632943461448660159313126496660033080937734557748701577020593482441014012783126085444004682764336220752851098517881202476417639649807333810261708210761333918442034275018088771547499619393557995773550772279857842207065696251926349053195423917250334982174308578108707
# e = 65537
# c = 4776006201999857533937746330553026200220638488579394063956998522022062232921285860886801454955588545654394710104334517021340109545003304904641820637316671869512340501549190724859489875329025743780939742424765825407663239591228764211985406490810832049380427145964590612241379808722737688823830921988891019862
#
# D(C) = 58324527381741086207181449678831242444903897671571344216578285287377618832939516678686212825798172668450906644065483369735063383237979049248667084304630968896854046853486000780081390375682767386163384705607552367796490630893227401487357088304270489873369870382871693215188248166759293149916320915248800905458
#

(※普段Writeupを書く時の慣習のせいで、ソースコード上で大文字になっている値の多くを小文字にして書きます)

Multi-PrimeなRSAで$N = p^8qr$となっている。加えて$F = p^7(p-1)(q-1)(r-1) = \phi(N)$という$F$に対して$ed \equiv 1 \mod F$となる$d$が定義され、$D(C) \equiv c^d \mod N$が与えられる。

よく考えなくても、$D(C)$が暗号文の復号結果のように思えるが実は罠がある。暗号化する際に、フラグにパディングが加わるがこのせいでフラグは$p$の倍数となってしまい、$N$と互いに素で無いことから通常の復号が出来ない(フラグを何乗しても$p$の倍数となってしまい、1になるような指数が存在しない)。このパディングは次のようになっている。

  1. $m_0$をフラグを64bit左シフトした結果とする(23行目の <<= (512//8)に対応)
  2. $m_1 \equiv m_0 \mod p^2$を計算する
  3. $m_2 \equiv -m_1 \mod p$を計算する
  4. $m_0+m_2$を返す

2より、$m_1 = m_0 + k_1p^2$、3より、$m_1 + m_2 = k_2p$となるような整数$k_1, k_2$が存在する。よって、前者を後者に代入して移項すると、$m_0+m_2 = k_2p - k_1p^2$となって、右辺が$p$の倍数であることは自明だから、パディング後のフラグである$m_0+m_2$も$p$の倍数となる。

というわけで以後は$m = kp$とおく。したがって$c \equiv m^e \equiv k^ep^e \mod N$が成り立つ。これより、$c = k^ep^e + m_c(p^8qr) = (k^ep^{e-8} + m_cqr)p^8$となるので、$c$は$p^8$の倍数となる。よって、$\gcd(N,c) = p^8$となるから、これの8乗根を計算して$p$を求めることが出来る。また、ついでに$qr$を求めることが出来、今後この値を法として使う事があるから計算しておく。

さて、与えられた値は$D(C) \equiv c^d \equiv m^{ed} \mod N$だった。これを$m = kp$を用いて計算してみると、$k$に関しては$ed$乗で元に戻ることから、次のようになる。

$$ c^d \equiv k^{ed}p^{ed} \equiv kp^{ed} \mod N $$

よってある整数$l$が存在して$c^d = kp^{ed} + p^8qrl = (kp^{ed-8} + qrl)p^8$となるから両辺$p^8$で割ると次のようになる。

$$ \frac{c^d}{p^8} = kp^{ed-8} + lqr $$

これを両辺$qr$で法を取ることで次のようになる。

$$ \frac{c^d}{p^8} \equiv kp^{ed-8} \mod qr $$

これを変形すると$ed\equiv 1 \mod (p-1)(q-1)$であるから、次が成り立ち、$k$を求めることが出来る。

$$ \frac{c^d}{p^8\cdot p^{ed-8}} \equiv \frac{c^d}{p} \equiv k \mod qr $$

$k$が求まったので$kp$を計算するとフラグが求められる。

Code

from math import gcd
from Crypto.Util.number import isPrime, long_to_bytes
from xcrypto.num_util import int_nth_root

n = 68410735253478047532669195609897926895002715632943461448660159313126496660033080937734557748701577020593482441014012783126085444004682764336220752851098517881202476417639649807333810261708210761333918442034275018088771547499619393557995773550772279857842207065696251926349053195423917250334982174308578108707
e = 65537
c = 4776006201999857533937746330553026200220638488579394063956998522022062232921285860886801454955588545654394710104334517021340109545003304904641820637316671869512340501549190724859489875329025743780939742424765825407663239591228764211985406490810832049380427145964590612241379808722737688823830921988891019862
dc = 58324527381741086207181449678831242444903897671571344216578285287377618832939516678686212825798172668450906644065483369735063383237979049248667084304630968896854046853486000780081390375682767386163384705607552367796490630893227401487357088304270489873369870382871693215188248166759293149916320915248800905458

p8 = gcd(n,c)
p = int_nth_root(p8, 8)
print(p)
assert isPrime(p) and n % (p**8) == 0
qr = n // (p**8)

k = dc * pow(p, -1, qr) % qr

flag = k*p
print(long_to_bytes(flag))

Flag

flag{y34_th1s_1s_n0t_h0w_mult1pr1m3_RS4_w0rks_buddy}

Resources