TL;DR

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

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=p8qrN = p^8qrとなっている。加えてF=p7(p−1)(q−1)(r−1)=ϕ(N)F = p^7(p-1)(q-1)(r-1) = \phi(N)というFFに対してed≡1mod  Fed \equiv 1 \mod Fとなるddが定義され、D(C)≡cdmod  ND(C) \equiv c^d \mod Nが与えられる。

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

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

2より、m1=m0+k1p2m_1 = m_0 + k_1p^2、3より、m1+m2=k2pm_1 + m_2 = k_2pとなるような整数k1,k2k_1, k_2が存在する。よって、前者を後者に代入して移項すると、m0+m2=k2p−k1p2m_0+m_2 = k_2p - k_1p^2となって、右辺がppの倍数であることは自明だから、パディング後のフラグであるm0+m2m_0+m_2もppの倍数となる。

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

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

cd≡kedped≡kpedmod  N c^d \equiv k^{ed}p^{ed} \equiv kp^{ed} \mod N

よってある整数llが存在してcd=kped+p8qrl=(kped−8+qrl)p8c^d = kp^{ed} + p^8qrl = (kp^{ed-8} + qrl)p^8となるから両辺p8p^8で割ると次のようになる。

cdp8=kped−8+lqr \frac{c^d}{p^8} = kp^{ed-8} + lqr

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

cdp8≡kped−8mod  qr \frac{c^d}{p^8} \equiv kp^{ed-8} \mod qr

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

cdp8⋅ped−8≡cdp≡kmod  qr \frac{c^d}{p^8\cdot p^{ed-8}} \equiv \frac{c^d}{p} \equiv k \mod qr

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

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