今年出た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は二項定理からの1次以上の項をまとめると整数を用いて次のようになる。

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

ではこれをで割る事を考える。で割って、とおく、但しである。この両辺にをかけて移項すると次のようになる。

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

したがってが成立することからに関して次が成り立つ事になる。

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

したがってで割った結果はの倍数になる。

これでと合わせての倍数が2つ揃ったことになるのでこれの最大公約数をとるとが吸い出される事が期待できる。その結果からの素因数分解が出来るので後はこの結果を用いて普通に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が実装されているが、公開鍵での代わりに秘密鍵であるをくれる。ついでにCRT-RSAで使われるパラメータであるもくれる。

Writeup §

の導出 §

ひとまず使える数字を増やしたい。現状の手持ちはしか無いのでを利用してを導出する。この合同式から次が成り立つような整数が存在する。

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

ここでである事からが成り立つ。これは十分探索可能な範囲なのでの約数となってかつが2048bitになるものを探す。

片方の素数の導出 §

これでが手に入ったのでこれを利用して片方の素数を求めたい。これにをかけてで法を取ると次のようになる。

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

この結果からの倍数となる。そこでのようにおく。

ところで任意整数に対して、である事からの倍数でありすなわちの倍数にもなる。そこでとおく。

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

前問同様にで割るととなる2つの整数が存在することがわかる。これの両辺にをかけるととなる事から

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

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

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

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

これでが手に入ったので後はからもう1つの素因数であるを計算でき、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つになる上の多項式を2つ用意すればそれの公約式をとることでが現れてくれそうである。よってこれを楕円曲線上の2倍算の結果とRSA暗号化の結果から構成する。

RSAの方は簡単である。なので次の式の根の1つがになる。

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

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

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

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

ここでにおける傾きを表しており、である(符号が正負どちらになるかはがわからないためこの地点では不明)。

y座標まで見ると結構複雑だがx座標だけ見るとそうでも無い。おまけにが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 $$

と定義した多項式の根はになる。

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

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}

感想 §

法を変えたり多項式に応用したりするのが思い付かずに解けなかった問題が多くて結構悔しかったです。

2021年はGCDに勝てるよう頑張ります。

関連リンク §

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

Modulus Amittendus §

urara §