今年出たCTFではCrypto問題に結構チャレンジしたのですが、最大公約数を上手く使う問題に苦戦したので反省と復習の意味を込めて数問Writeupを書きます。今回扱うのはASIS CTF 2020からBaby RSAとTSG CTF 2020からModulus Amittendus, そしてSECCON 2020 Online CTFからuraraです。

ASIS CTF 2020 - Baby RSA §

Babyと書かれている癖にCTF本番で解けなかったという恥ずかしい思い出がある問題。

暗号化スクリプトは次の通り。

#!/usr/bin/python

from Crypto.Util.number import *
import random
from flag import flag

nbit = 512
while True:
    p = getPrime(nbit)
    q = getPrime(nbit)
    e, n = 65537, p*q
    phi = (p-1)*(q-1)
    d = inverse(e, phi)
    r = random.randint(12, 19)
    if (d-1) % (1 << r) == 0:
        break

s, t = random.randint(1, min(p, q)), random.randint(1, min(p, q))
t_p = pow(s*p + 1, (d-1)/(1 << r), n)
t_q = pow(t*q + 4, (d-1)/(1 << r), n)

print 'n =', n
print 't_p =', t_p
print 't_q =', t_q
print 'enc =', pow(bytes_to_long(flag), e, n)

問題名にもある通り通常のRSA問題だが、公開鍵と暗号文に加えて謎のパラメータt_p, t_qが渡される。

Writeup §

注目するのはt_p = pow(s*p + 1, (d-1)/(1 << r), n)で定義されているパラメータである。ここで法を取らないt_pは二項定理から$p$の1次以上の項をまとめると整数$k$を用いて次のようになる。

$$ t_p = (s_p + 1)^{d'} = kp + 1 $$

ではこれを$N = pq$で割る事を考える。$k$を$q$で割って、$k = rq + \alpha$とおく、但し$r \in \mathbb{Z}, \ 0 \leq \alpha \lt q$である。この両辺に$p$をかけて移項すると次のようになる。

$$ kp - \alpha p = rpq = rN $$

したがって$kp \equiv \alpha p \bmod N$が成立することから$t_p$に関して次が成り立つ事になる。

$$ t_p - 1 \equiv \alpha p \bmod N $$

したがって$t_p - 1$を$N$で割った結果は$p$の倍数になる。

これで$N = pq$と合わせて$p$の倍数が2つ揃ったことになるのでこれの最大公約数をとると$p$が吸い出される事が期待できる。その結果から$N$の素因数分解が出来るので後はこの結果を用いて普通にRSAの復号をするだけである。

Code §

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


if __name__ == "__main__":
    n = 10594734342063566757448883321293669290587889620265586736339477212834603215495912433611144868846006156969270740855007264519632640641698642134252272607634933572167074297087706060885814882562940246513589425206930711731882822983635474686630558630207534121750609979878270286275038737837128131581881266426871686835017263726047271960106044197708707310947840827099436585066447299264829120559315794262731576114771746189786467883424574016648249716997628251427198814515283524719060137118861718653529700994985114658591731819116128152893001811343820147174516271545881541496467750752863683867477159692651266291345654483269128390649
    t_p = 4519048305944870673996667250268978888991017018344606790335970757895844518537213438462551754870798014432500599516098452334333141083371363892434537397146761661356351987492551545141544282333284496356154689853566589087098714992334239545021777497521910627396112225599188792518283722610007089616240235553136331948312118820778466109157166814076918897321333302212037091468294236737664634236652872694643742513694231865411343972158511561161110552791654692064067926570244885476257516034078495033460959374008589773105321047878659565315394819180209475120634087455397672140885519817817257776910144945634993354823069305663576529148
    t_q = 4223555135826151977468024279774194480800715262404098289320039500346723919877497179817129350823600662852132753483649104908356177392498638581546631861434234853762982271617144142856310134474982641587194459504721444158968027785611189945247212188754878851655525470022211101581388965272172510931958506487803857506055606348311364630088719304677522811373637015860200879231944374131649311811899458517619132770984593620802230131001429508873143491237281184088018483168411150471501405713386021109286000921074215502701541654045498583231623256365217713761284163181132635382837375055449383413664576886036963978338681516186909796419
    enc = 5548605244436176056181226780712792626658031554693210613227037883659685322461405771085980865371756818537836556724405699867834352918413810459894692455739712787293493925926704951363016528075548052788176859617001319579989667391737106534619373230550539705242471496840327096240228287029720859133747702679648464160040864448646353875953946451194177148020357408296263967558099653116183721335233575474288724063742809047676165474538954797346185329962114447585306058828989433687341976816521575673147671067412234404782485540629504019524293885245673723057009189296634321892220944915880530683285446919795527111871615036653620565630

    p = gcd(n, t_p - 1)
    assert p != 1
    q = n // p

    d = inverse(0x10001, (p-1)*(q-1))
    m = pow(enc, d, n)

    print(long_to_bytes(m))

Flag §

ASIS{baby___RSA___f0r_W4rM_uP}

なお、怪しい作り方をしていたdは大して関係なかった。

TSG CTF 2020 - Modulus Amittendus §

この問題も前問同様法のすり替えが必要な問題である。暗号化スクリプトは次の通り。

require 'openssl'
require 'json'

def modinv(a, m)
  m0, inv, x0 = m, 1, 0
  while a > 1
    inv -= (a / m) * x0
    a, m = m, a % m
    inv, x0 = x0, inv
  end
  inv += m0 if inv < 0
  inv
end

class RSA
  def initialize
    @p = OpenSSL::BN::generate_prime(1024, true).to_i
    @q = OpenSSL::BN::generate_prime(1024, true).to_i
    @n = @p * @q
    @e = 65537
    @d = modinv(@e, (@p - 1) * (@q - 1))
    @exp1 = @d % (@p - 1)
    @exp2 = @d % (@q - 1)
    @cf = modinv(@q, @p)
  end

  def encrypt(m)
    m.pow(@e, @n)
  end

  def decrypt(c)
    m1 = c.pow(@exp1, @p)
    m2 = c.pow(@exp2, @q)
    (m2 + @cf * (m1 - m2) % @p * @q) % @n
  end

  def pubkey
    privkey.to_a[..2].to_h
  end

  def privkey
    {
      e: @e,
      n: @d,
      cf: @cf,
      p: @p,
      q: @q,
      exp1: @exp1,
      exp2: @exp2,
    }
  end
end

flag = File.read('flag.txt').unpack("H*")[0].hex
rsa = RSA.new
p rsa.encrypt(flag)

File.write('pubkey.json', JSON.dump(rsa.pubkey))

CRT-RSAが実装されているが、公開鍵で$N$の代わりに秘密鍵である$d$をくれる。ついでにCRT-RSAで使われるパラメータである$cf := q^{-1} \bmod p$もくれる。

Writeup §

$\phi(N)$の導出 §

ひとまず使える数字を増やしたい。現状の手持ちは$e, d, cf$しか無いので$ed \equiv 1 \bmod \phi(N)$を利用して$\phi(N)$を導出する。この合同式から次が成り立つような整数$k$が存在する。

$$ ed - 1 = k\phi(N) $$

ここで$d \lt \phi(N)$である事から$1 \leq k \leq e = 65537$が成り立つ。これは十分探索可能な範囲なので$k$が$ed-1$の約数となってかつ$\phi(N)$が2048bitになるものを探す。

片方の素数の導出 §

これで$\phi(N) = (p-1)(q-1)$が手に入ったのでこれを利用して片方の素数を求めたい。これに$cf \equiv q^{-1} \bmod p$をかけて$p$で法を取ると次のようになる。

$$ cf \cdot \phi(N) \equiv cf\cdot p(q-1) - cf (q-1) \equiv cf(1 - q) \equiv cf - 1 \bmod p $$

この結果から$cf \cdot \phi(N) - cf + 1$は$p$の倍数となる。そこで$k'p := cf \cdot \phi(N) - cf + 1$のようにおく。

ところで任意整数$a$に対して、$a^\phi(N) = a^{(p-1)(q-1)} \equiv 1 \mod pq$である事から$a^{\phi(N)} - 1$は$pq$の倍数でありすなわち$p$の倍数にもなる。そこで$mp := a^{\phi(N)} - 1$とおく。

このような$mp$に対して$lp$である別の$p$の倍数$lp$で法をとる事を考える。

前問同様に$m$を$l$で割ると$m = rl + \alpha$となる2つの整数$r, \ 0 \leq \alpha \lt l$が存在することがわかる。これの両辺に$p$をかけると$mp = r(lp) + \alpha p$となる事から

$$ mp \equiv \alpha p \bmod lp $$

が成立する。よって$mp$を別の$p$の倍数である$lp$で割った結果も$p$の倍数となる。

というわけで$mp$には適当な$a$を利用した値を、$lp$には先程計算した$k'p$を適用すると$\alpha p$に相当する新しい$p$の倍数が手に入る事が期待できる。

このようにして$a$を変えて$p$の倍数を複数用意してから最大公約数を取れば高い確率で$p$が抽出出来る。

これで$p$が手に入ったので後は$\phi(N)$からもう1つの素因数である$q$を計算でき、RSA暗号の復号手順を経るとフラグが手に入る。

Code §

※自作ライブラリの関数を使っていますが、書き直すのが面倒なので機能は字面で察してください

from Crypto.Util.number import long_to_bytes
from xlog import XLog
from xcrypto import dec, is_prime, list_gcd


logger = XLog("CRYPTO")


def exploit(e, d, cf, c):
    k_phi = e * d - 1

    phi = -1
    for k in range(e, 0, -1):
        if k_phi % k == 0:
            phi = k_phi // k
            if phi.bit_length() == 2048:
                logger.info(f"found!!")
                logger.info(f"phi = {phi}")
                break

    if phi == -1:
        logger.error("not found...")
        return None

    kp = cf * phi - cf + 1

    gcd_p_list = [kp]
    for a in range(2, 10):
        gcd_p_list.append(pow(a, phi, kp) - 1)

    p = list_gcd(gcd_p_list)

    assert is_prime(p)
    assert phi % (p-1) == 0
    q = phi // (p-1) + 1

    flag = dec(c, d, p*q)

    return flag


if __name__ == '__main__':
    nums = {"e":65537,"n":27451162557471435115589774083548548295656504741540442329428952622804866596982747294930359990602468139076296433114830591568558281638895221175730257057177963017177029796952153436494826699802526267315286199047856818119832831065330607262567182123834935483241720327760312585050990828017966534872294866865933062292893033455722786996125448961180665396831710915882697366767203858387536850040283296013681157070419459208544201363726008380145444214578735817521392863391376821427153094146080055636026442795625833039248405951946367504865008639190248509000950429593990524808051779361516918410348680313371657111798761410501793645137,"cf":113350138578125471637271827037682321496361317426731366252238155037440385105997423113671392038498349668206564266165641194668802966439465128197299073392773586475372002967691512324151673246253769186679521811837698540632534357656221715752733588763108463093085549826122278822507051740839450621887847679420115044512}

    e = nums["e"]
    d = nums["n"]
    cf = nums["cf"]

    c = 17320751473362084127402636657144071375427833219607663443601124449781249403644322557541872089652267070211212915903557690040206709235417332498271540915493529128300376560226137139676145984352993170584208658625255938806836396696141456961179529532070976247738546045494839964768476955634323305122778089058798906645471526156569091101098698045293624474978286797899191202843389249922173166570341752053592397746313995966365207638042347023262633148306194888008613632757146845037310325643855138147271259215908333877374609302786041209284422691820450450982123612630485471082506484250009427242444806889873164459216407213750735305784

    flag = exploit(e, d, cf, c)

    if flag is not None:
        logger.info(long_to_bytes(flag).decode())

Flag §

見切れるぐらい長い(このパターン結構あるのでCSS書いて折り返すようにしようかな)

TSGCTF{Okay_this_flag_will_be_quite_long_so_listen_carefully_Happiness_is_our_bodys_default_setting_Please_dont_feel_SAd_in_all_sense_Be_happy!_Anyway_this_challenge_is_simple_rewrite_of_HITCON_CTF_2019_Lost_Modulus_Again_so_Im_very_thankful_to_the_author}

フラグ曰く、HITCON 2019に似たような問題が出ていたらしいので気が向いたら取り組んでみます。

SECCON 2020 Online CTF - urara §

ここまで扱ったのは整数の最大公約数を上手く使う問題だったが実は多項式でも同じ事が出来る。このアイデアはFranklin Reiter's Attack等にも見られ、この問題では楕円曲線とRSAの2つからから同じ解を持つ2つの式を構成するという形に帰着させている。

暗号化スクリプトは次の通り(SageMathによるもの)

from flag import flag

p = random_prime(1 << 1024)
q = random_prime(1 << 1024)
n = p * q

print("n =", n)

# ---

x = int.from_bytes(flag, "big")
y = randint(0, n-1)

a = randint(0, n-1)
b = (y^2 - (x^3 + a*x)) % n

EC = EllipticCurve(Zmod(n), [a, b])

P = EC((x, y))
Q = 2 * P

print("a, b =", [a, b])
print("Q =", Q.xy())

# ---

m = int.from_bytes(flag, "big")
t = randint(0, n-1)

c = power_mod(m + t, 65537, n)
print("t =", t)
print("c =", c)

フラグをx座標としたある楕円曲線上の点Pに対し、それを2倍したQとフラグに定数tを付けてRSAで暗号化された暗号文cが渡される。

Writeup §

前者の楕円曲線上の点に関してはRSAで使われているnを法として楕円曲線を定義しており、こいつは合成数である事から位数を求める事が難しい。よってQに2の逆数をかけてPを導出する、というのは無理そうである。

また、後者のRSAによる暗号化も特に目立った欠点は見当たらない。よってこの2つの表現から別々にフラグを導出するのは諦めて組み合わせる事を考える。

公約式の構成 §

フラグが根の1つになる$\mathbb{Z}_n$上の多項式を2つ用意すればそれの公約式をとることで$x - flag$が現れてくれそうである。よってこれを楕円曲線上の2倍算の結果とRSA暗号化の結果から構成する。

RSAの方は簡単である。$(flag + t)^e \equiv c \bmod n$なので次の式の根の1つが$x=flag$になる。

$$ f_1(x) := (x + t)^e - c \bmod n $$

続いて楕円曲線上の演算について考える。Pを$P := (x_p, y_p)$とする(よって$x_p = flag$である)。また、これを2倍した点であるQを$Q := (x_q, y_q)$とおく。

楕円曲線上の点の2倍算より次が成り立つ。

$$ Q = 2P = (s^2 - 2x_p, s(x_p - (s^2 - 2x_p)) - y_p) $$

ここで$s$は$P$における傾きを表しており、$s = \frac{3x_p^2 + a}{2y_p} = \pm \frac{3x_p^2+a}{2\sqrt{x_p^3 + ax_p + b}}$である(符号が正負どちらになるかは$P$がわからないためこの地点では不明)。

y座標まで見ると結構複雑だがx座標だけ見るとそうでも無い。おまけに$s$が2乗されていることから正負を考えなくて良さそうである。よってこちらだけを考えると次が成り立つ。

$$ s^2 - 2x_p \equiv \frac{9x_p^4 + 6ax_p^2 + a^2}{4(x_p^3 + ax_p + b)} - 2x_p \equiv \frac{x_p^4 - 2ax_p^2 + a^2 - 8bx_p}{4(x_p^3 + ax_p + b)} \equiv \frac{(x_p^2 - a)^2 - 8bx_p}{4(x_p^3 + ax_p + b)} \equiv x_q \bmod n $$

右辺2つの分母を消去して移項すると

$$ (x_p^2 - a)^2 - 8bx_p - 4x_q(x_p^3 + ax_p + b) \equiv 0 \bmod n $$

が得られることから

$$ f_2(x) := (x^2 - a)^2 - 8bx - 4x_q(x^3 + ax + b) \bmod n $$

と定義した多項式$f_2(x)$の根は$x = x_p = flag$になる。

これで根が共に$x = flag$である多項式$f_1, f_2$が得られたので、後はこの2式の最大公約式を取ると$x - flag$である事が期待出来、その切片の絶対値を取ればフラグになる。

Code §

SageMathです

from Crypto.Util.number import long_to_bytes

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a.monic()
    
n = 2495486283720196414658156567206136253284019243567958059321851922493511599099119079680539265897209530360296446936208426800428584598438104476991265428916133300767614183255586657557318228860960807727808759584720952822528262134841932977582943502095440882371004412919346559104839698667880585368725210776035801955698546309524104974030342228550787050046049567579065187788994920743809520302849445149655730482323230359606160072691147584028808470430189686361894038637340270209743137983546710783035439259335812370392005195583920997311705713592323771863115626855381027900474814101769171537793566286513448923754562724664313084249
a, b = [972698759004177594974248512452291945375078088533797369007356091167161417126661888563796734970930291849416186353401136601333663184182496443559710260512865444011720544123349975347739686656458945047235004231083887412945922041617098821848109846466185381123572906286526866381831235952511603159063112700803240801865531290422765608302160438343367509056504904308915457764244188011067916227743467457188390983251694692503189881215955070503001896424929414573915023552143884558308649592326241873353092050570518609492131325132956538067260949200100411641491893433056989039052880009034587425997261355587991692486739450094236514758, 1008573312161911000752400660247274100068850370101842340234132233694416751783423219213618251410638912974573281248522724039762013929414424219508458136249643022502332214316678524707691239057071086157162469422064755831275222236081328847657177640054036054045406160824940362440246044883298682522453311877923136432805003451856768017606479097933453907524689590456734108278484158414310289226885363416716427913861763258366781222560451163637643863000635404382308239958732271399310367790172837289160588101927655476531792837448724884102324974548266581640538857040307464673210901987003942198966596512095342443290488073222934653919]
Q = (867873247748174812072354447691943457644353996950272562674084117171032057450250434260859133245258701778341990173401264117064176603158749478700828272476995001485212129112894717807517326303812223951203313709014636942885555951223369106229497656316475383382128690099423171335569734684044941751080119216645566879454705354381241993772833561805053182217457917853140417414526348110486320351897963479122149636934280817200288672007854340543650563779551397976130991102876798375410531876063549460135790157054904126255613039452837589835705186004228042174285947129036321556613553671390037190356528190615214682864974887455909937619, 92156177218703573237225387608427402840283864799028130419669842561042657427033824263488342006248150114770090783060742870361337890590575949279141298574463897596258155388694505972290467228718686940706114514588166273676766526477678084721956511277781446249434968683955693367295727100489236602819441636378541120672736441095144636166942675405988795394557885388103901609694713050343823947711145939998064604641585844723037739727543720657955244689568060357318664843191704220939056774964806734882132924887657592200535178476768157269833478823542760608627255145238265363439669379993951234531206810550094244882515659269421133342)
t = 1777168232191821289919361506719035105250381465284676268198289506955330183480124536544599410896048478441274216496360402574201869585399683211082212730215235958242478585658417025279266624856606193964114464891213954565004165135702759126347979656143036294768812017453240638705726695168190715353794422332588623776474921669253740204759173522894816230138329334719993075279033623376817492761735171138485911978022373863743336360226609344072307935615642938848948516305275434543979476810981458780983782786892497139062392102615609343631554433368313342218231607432462736876822618694937755989879907893923918048177205572935961542238
c = 2495229390232434790849433815327288468942817979063945643796061305651846860246802186265725586015982098870449933396313764591953669092562225099204762704457578001689923221436404745009925073617272135602713059363827274464818599027905362654459980006227162213728037809437236173304627762460414746305401818555455721634808613093466198536909678291636025089911028651869899954385806560064211623734732747231127694454204886697599833768585606205744494003870149200884542308351359803929906608329439509726117597736110772616668829705345022404944932702135376373114568136049373919012494457087384217492589157659130773882703580148119446812556
e = 65537

P.<x> = PolynomialRing(Zmod(n))

f1 = (x + t)^e - c
f2 = (x^2 - a)^2 - 8*b*x - Q[0] * 4 * (x^3 + a * x + b)

res = -gcd(f1, f2).coefficients()[0]

print(long_to_bytes(res))

Flag §

SECCON{0n3_tw0_thr33_f0ur_fiv3_six_chachan}

関連リンク §

後者2つの問題は公式から問題のリポジトリとWriteupが提供されています。復習が非常にしやすくて嬉しいです。

Modulus Amittendus §

urara §