「SECCON13 電脳会議」参加記

1. はじめに

　CTFerにとって「SECCON = SECCON CTF」というお気持ちは強いのかもしれませんが、SECCON が主催する魅力的なイベントは CTF だけではありません。CTF の決勝戦を含むイベントとして、「SECCON 電脳会議」が開催されます。

www.seccon.jp

　今年（2025）年は、3月1日（土）・2日（日）の２日間、会場は「浅草橋ヒューリックホール＆カンファレンス*1」でした。

SECCON会場

　ここで開催されるワークショップ等は、基本的に参加無料でした。特に初参加の方は驚かれるかもしれませんが、それはスポンサーあってのことです。リスペクトを忘れてはいけません。

スポンサー様

2. 参加記

2.0 参加までの経緯

　筆者の電脳会議への参加は昨年からです。前回はパソコンを使った CTF 系ハンズオンを中心に応募して、当選した 3 つのワークショップに参加しました。

　今年は当初 3/1 の「SWS1 バッジ基板でチカチカLEDハンダ付けワークショップ」と 3/2 の「Car Hacking Village」に応募したのですが、3/2 の都合が悪くなってしまい、後者をキャンセルしました*2。半田付けの方が、抽選では幸いにも「当選」となり、その時点でイベントへのオフライン参加が確定しました。

　3/1 の午後については当初、オンラインもしくはオフラインで「AlpacaHack x SECCON CTF コラボイベント」に参加するつもりだったのですが、同日午後の「SWS2 バッジ基板でマイコンハンダ付け＆プログラミングワークショップ」に空き出来た旨を知り、「基盤コンプリートできるぞ！」ということで応募（参加）することとした次第です。

　当日は少し早めに会場に到着し、3 階で受付を済ませ、1 階のコンビニで栄養補給しながらワークショップの開始時刻を待ちました。

2.1 SWS1 バッジ基板でチカチカLEDハンダ付けワークショップ

　半田付けのワークショップは、CTF 決勝会場と同じフロアの 2 階（セミオープンスペースのようなところ）で開催され、外からも様子をうかがうことは出来るものでした。

　基盤は受付で参加者全員に付与されるものを使用、半田ごてなどの工具や部品は会場にて貸与・提供されました。

　このワークショップは、青と赤の LED が交互に点滅する「非安定マルチバイブレータ回路の組み立て」を実装するものでしたが、回路については知識皆無なため後日基礎からキャッチアップすることとし、当日は半田付けに集中するという戦術をとりました。

　半田付けの経験は少しだけありましたが、多くはリード線同士を結合するものでしたので基盤での経験が少なく、いわゆる「半田ブリッジ」を量産しないかと内心ヒヤヒヤしていました。

　しかし、事前に注意すべきポイントや半田付けのコツ（タイミング）などが記された資料が配布され、作業概要の説明なども分かりやすく、結果的には思ったよりいい感じの作業が出来たかと思います。

　また、作業フェイズではスタッフの方が巡回し、作業で困った場合にはフォローを受けられるよう、配慮されており、安心して作業に取り組めました。

半田付けワークショップ（LED編）

　「半田付け完全に理解した」ご褒美ということで、作業終了後秋葉原へ転進し、昼食を摂った後ミルクスタンドで牛乳をキメました。

牛乳！

2.2 SWS2 バッジ基板でマイコンハンダ付け＆プログラミングワークショップ

　午後の部では、午前中にウオームアップが済んでいることもあって、少しだけ楽な気持ちで参加できました。

　このワークショップでは、「マイコン回路の組み立てとプログラミング」という 2 つのフェイズがあり、最初に半田付けでマイコン回路を基盤に設置した後、マイコンにプログラムを入れて動作させるというものでした。

　半田付けは午前中の勢いもあってサクサク進む・・・かのように思えましたが、誤って部品挿入前の穴を半田でふさいでしまい、溶かしながら本来の部品を差し込むリカバリを行ったため、本来奥まで押し込まれている部品（上部オレンジ色のスイッチ「Sw.A」）がなぜか宙に浮いている、というやらかしが発生しました。

　しかしそれ以外は大きな問題はなく組み立てが進み、テスト稼働もＯＫ！

半田付けワークショップ（マイコン編）

　プログラミングについては、会場では時間的に自作は難しいため、あらかじめ用意されたものを入れて動作させたりそれらを改造したりといったところでしたが、そのあたりは後でじっくり楽しもうという算段で、ここではいくつかのゲームをテスト動作させた後、任意 ASCII 文字列を入れられたところでヨシとしました。

ジーク・ジオン！

　これまでほぼ「ソフトウェア畑」で生きてきた者としては、非常に有意義なワークショプだったと思っています。これをきっかけに電子工作に入門することで、QOL の向上が期待できます。

　自分の得意分野を伸ばすのも楽しいですが、未経験の分野に飛び込んでみるのもまた楽しいものですね。

2.3 AlpacaHack x SECCON CTF コラボイベント（決勝観戦CTF）

　Workshop の空き時間や移動時間を使って、「SECCON CTF 13 決勝観戦 CTF」に参加しました。帰宅後もオンラインで参加し、結果的には 12 問を解いて 19 位でした。

コラボCTF参加結果

　Cryptoは全完、「Customizable EC」はたまたま手許にいい感じの使えるデータがあったため 1st blood を取れました。総じて面白い問題が多く、楽しむことが出来ました。

　なお、この CTF はオンライン「でも」参加できるものでしたが、会場では正答数などに応じて景品をもらえる*3という趣向もありました。*4

3. おわりに

　運営スタッフのみなさま、スポンサーのみなさま、参加された皆様に感謝します。

　来年も楽しいイベントが開催されることを祈念します。

*1:昨年と同じ会場です。

*2:無料イベントでの（あらかじめ判明している）キャンセルはつい忘れがちですが、他の参加希望者の機会を理不尽に奪うことになってしまうので、無料イベントだからこそキャンセル手続きは可能な限り全力で行わなければならないと思っています。もちろん、突発的なアクシデントによる欠席の場合などはその限りではありませんが。

*3:数に限りがあるので先着順。

*4:これらのグッズはとても魅力的であり、オンラインで解いた場合でも会場に出向けば貰えた可能性はあったかもしれないのですが、前述の通り 3/2 の都合が付かないため、泣く泣く辞退する（会場へは向かわない）こととなりました。

AlpacaHack Round 9 (Crypto) Writeup

1. はじめに

　2025/1/26 12:00 JST ～18:00 に開催された「AlpacaHack Round9 (Crypto)」参加しました。数時間とはいえ、CTF にまとまった時間を投入できたのは久しぶりでした*1。2 完で 6 位。

　最初の 1 問で色々迷走し、時間を使い過ぎてしまった点は大いなる反省点でした。

2. Writeup

AlpacaHackの過去問は常設コンテンツとなるため、フラグの記載は省略します。

2.1. RSAMPC (16 solves)

設問

I calculated the RSA public key using multi-party computation.

以下の 2 ファイルが提供されます。

「chall.py」

import os
from Crypto.Util.number import getRandomRange, getPrime, bytes_to_long

FLAG = os.environ.get("FLAG", "fakeflag").encode()

def additive_share(a):
    t0, t1 = getRandomRange(-2**512, 2**512), getRandomRange(-2**512, 2**512)
    t2 = a-t0-t1
    return t0, t1, t2

def replicated_share(a):
    t = additive_share(a)
    return [(t[i], t[(i+1)%3]) for i in range(3)]

def multiply_shares(sa, sb):
    def mul(t, u):
        return t[0]*u[0]+t[0]*u[1]+t[1]*u[0]
    r = additive_share(0)
    z = [mul(sa[i], sb[i])+r[i] for i in range(3)]
    w = [(z[i], z[(i+1)%3]) for i in range(3)]
    return w

def reconstruct(s):
    return s[0][0] + s[0][1] + s[1][1]

p = getPrime(512)
q = getPrime(512)

sp = replicated_share(p)
sq = replicated_share(q)
print("your share of p:", sp[0])
print("your share of q:", sq[0])

spq = multiply_shares(sp, sq)
print("your share of pq:", spq[0])

n = reconstruct(spq)
assert n == p*q
print("n:", n)

e = 0x10001
c = pow(bytes_to_long(FLAG + os.urandom(127-len(FLAG))), e, n)
print("e:", e)
print("c:", c)

「output.txt」

your share of p: (-384164070196680113629973964276599320736606300184523772854135294036334447818682200607218877531386512793858125339877828582394197679795576991953411880314517, 178776721087372919385257940734429604253240493277094581482580652949038337321961407291832241379559936948198042043881180916670462219794291885959730598632423)
your share of q: (-10504102453855211730773548202462643334445368588122773952797120588540073173181223269420294976331168878842123082669069593895980908615299058089156709125348617, 3324659724832936014805633502878093035237335054058544453532695059432217891926271390882999445452501190449380595220556388508799059755133895886341486877191502)
your share of pq: (880194945859095512548778390949753106113259354062743403885130575509194611686622871911550689148439940097472063798899034574466553154127726867674397008987477001207806315461004286936941315001029394217039765579529660629019466179402060549350587729722354909331590051509695082365313846996923469825646557408789955494, 40388351148875096689764230410867470980240794826105168292967479483809364773078955483003274901375600951153408618729650715655666480989756454152565386666760509805904377793675351489295406907138019316039841793386393194481700178651652081449097569147179108704523020190287922457859082133424057955783092523665228634328)
n: 122269467950798077326822634108968850809243750508493781647505745002863843379348700424238562022365315227978807541070854658246091147872559714237246479088170538196473585543281713624525798244748333546435600544573727499127916535316599284592352755786055339638261774730837681190375466416924715653324305527245715836447
e: 65537
c: 100976267335628681910815317357700490412039872278731196009735781349258998302355802361980783540754919888894607253589239383351290237447746132667260747986281172840910605287343986031579879857474734142154881821962810929745626899955618676413832332521656625264015203959361696843594006345498340544121922011105950850715

検討

　リークされる sp[0] 、sq[0]、spq[0] が何なのかよくわからなかったので、SageMath の数式処理で把握することにしました。 「test.sage」

PR.<p,q,tp0,tp1,tq0,tq1,tr0,tr1> = PolynomialRing(ZZ)

tp2 = p - tp0 -tp1
sp = [(tp0,tp1), (tp1,tp2), (tp2,tp0)]
print(sp[0])
#(tp0,tp1)

tq2 = q - tq0 -tq1
sq = [(tq0,tq1), (tq1,tq2), (tq2,tq0)]
print(sq[0])
#(tq0,tq1)

def mul(t, u):
  return t[0]*u[0]+t[0]*u[1]+t[1]*u[0]

tr2 = -tr0-tr1
r = (tr0, tr1, tr2)

z = [mul(sp[i], sq[i])+r[i] for i in range(3)]
spq = [(z[i], z[(i+1)%3]) for i in range(3)]

print(spq[0])
#(tp0*tq0 + tp1*tq0 + tp0*tq1 + tr0, q*tp1 - tp1*tq0 + p*tq1 - tp0*tq1 - tp1*tq1 + tr1)

　spq[0][0]からは良い情報を得られそうにありませんので、spq[0][1]の方を見てみます。

　tp0、tp1、tq0、tq1 は既知ですから、spq[0][1] の未知数は p, q, r[1] の 3つでいずれも 512bit、ということになります。

　最初これを（愚かにも） LLL で処理しようとしたのですが、無理筋でした（未知数が大きすぎ！）。気を取り直して r[1] を "誤差" と見なし、 p （もしくは q）の近似値を求めて総当たりしてみたところ、うまくいきました。想定解法のようです。

解法（ソルバ）

「solve.sage」

from Crypto.Util.number import *
import gmpy2

sp = (-384164070196680113629973964276599320736606300184523772854135294036334447818682200607218877531386512793858125339877828582394197679795576991953411880314517, 178776721087372919385257940734429604253240493277094581482580652949038337321961407291832241379559936948198042043881180916670462219794291885959730598632423)
sq = (-10504102453855211730773548202462643334445368588122773952797120588540073173181223269420294976331168878842123082669069593895980908615299058089156709125348617, 3324659724832936014805633502878093035237335054058544453532695059432217891926271390882999445452501190449380595220556388508799059755133895886341486877191502)
spq = (880194945859095512548778390949753106113259354062743403885130575509194611686622871911550689148439940097472063798899034574466553154127726867674397008987477001207806315461004286936941315001029394217039765579529660629019466179402060549350587729722354909331590051509695082365313846996923469825646557408789955494, 40388351148875096689764230410867470980240794826105168292967479483809364773078955483003274901375600951153408618729650715655666480989756454152565386666760509805904377793675351489295406907138019316039841793386393194481700178651652081449097569147179108704523020190287922457859082133424057955783092523665228634328)
n = 122269467950798077326822634108968850809243750508493781647505745002863843379348700424238562022365315227978807541070854658246091147872559714237246479088170538196473585543281713624525798244748333546435600544573727499127916535316599284592352755786055339638261774730837681190375466416924715653324305527245715836447
e = 65537
c = 100976267335628681910815317357700490412039872278731196009735781349258998302355802361980783540754919888894607253589239383351290237447746132667260747986281172840910605287343986031579879857474734142154881821962810929745626899955618676413832332521656625264015203959361696843594006345498340544121922011105950850715

N = n * sp[1] * sq[1]
b = spq[1] + sp[1]*sq[0] + sp[0]*sq[1] +sp[1]*sq[1]
D = B**2 - 4*N

sqD = int(gmpy2.isqrt(D))
approx_p = ((b + sqD)//2) // sq[1]

for i in range(-100000,100000):
  p = approx_p+i
  if n % p == 0:
    print("found!")
    break

q = n // p
d = pow(e,-1,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))

2.2. addprimes (16solves)

設問

addprimes in PARI/GP is useful for implementing RSA decryption.

以下のファイルが提供されます。 「server.sage」

import os
import signal
from sage.misc.banner import require_version
from Crypto.Util.number import getPrime, bytes_to_long

assert require_version(10), "This challenge requires SageMath version 10 or above"

signal.alarm(30)
FLAG = os.environ.get("FLAG", "Alpaca{*** FAKEFLAG ***}").encode()
assert FLAG.startswith(b"Alpaca{")

p = getPrime(512)
q = getPrime(512)
n = p * q
e = 37

print("n:", n)
print("e:", e)

c = int(input("ciphertext: "))
assert 1 < c < n-1
pari.addprimes(p)
m = mod(c, n).nth_root(e)
print("plaintext:", m)

padded_flag = FLAG + os.urandom(127-len(FLAG))
print("encrypted flag:", pow(bytes_to_long(padded_flag), e, n))

検討

　「e=37だから37個集めてCRTすれば終わりっしょ」…なわけありませんでした。ちゃんと padding されていますのでダメです。

　そこで私はこう考えました。「Zmod(n) における 1 の e 乗根で 1 以外のもの（ここでは w と書くことにする）が判明して、たとえば w mod p ==1、w mod q !=1で1以外、なんていうことであれば、 GCD(w, n) == p となり幸せになれる！」*2

　最近クジ運はそう悪くない*3ので、実装してみることにしました。

　p, q が求められたら、mod.p、mod.q で e 乗根を計算して CRT すれば解候補を列挙できるので、そこから long_to_bytesして b"Alpaca{" を含むものを選べば OK です。

解法（ソルバ）

「solve.sage」

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from pwn import *
import random
import itertools

HOST = <redacted>
PORT = <redacted>

while(True):
  r = remote(HOST, int(PORT))
  try:
    n = int(r.readline().decode().replace("n: ",""))
    m0 = random.randint(2**1023,2**1024) % n
    c = pow(m0,e,n)
    r.readline()
    kw = b"ciphertext: "
    data = str(c).encode()
    r.sendlineafter(kw, data)
    m = int(r.readline().decode().replace("plaintext:",""))
    enc = int(r.readline().decode().replace("encrypted flag: ",""))
    r.close()
    if m != m0:
      print("hit")
      root = m * pow(m0,-1,n) % n
      if 1 < gcd(root - 1, n) < n:
        break
  except:
    try:
      r.close()
    except:
      pass

p = gcd(root - 1, n)
q = n // p
d = pow(e,-1,(p-1)*(q-1))

mps = GF(p)(enc).nth_root(e, all=True)
mqs = GF(q)(enc).nth_root(e, all=True)

for mp in mps:
  for mq in mqs:
    pt = long_to_bytes(crt([int(mp),int(mq)],[p,q]))
    if b"Alpaca" in pt:
      print(pt)
      exit()

3. おわりに

　久しぶりにまとまった時間を使って Crypto に取り組んで楽しめました。

　解けなかった問題*4については「Upsolve queue」に投入し、腰を据えて取り込もうと思います。

*1:ここ最近は主に Dream Hack を埋めていました。

*2:ちょっとまどろっこしい考え方でしたが、間違いではなかったようです。

*3:宝くじは全く当たりませんが。

*4:maple3142さんゴメンサナイ！

ASIS CTF Finals 2024 Writeup

はじめに

2024/12/28 23:00(JST)～2024/12/29 23:00(JST) に開催された「ASIS CTF Finals 2024」に参加しました。

ASIS CTFは毎年「Quals」と「Finals」が開催されますが、Qualsの成績（参加したかどうか）にかかわらず、誰でも「Finals」に参加できる点が特徴です*1。

また、毎年夏ごろに開催される「Crypto CTF」も ASIS が主催しているので、スコアサーバーの仕様や Crypto 問の "雰囲気" は「Crypto CTF」とあまり変わりません。

今年は Welcome 以外に 1 問だけ解いたので、その Writeup を記します。

Writeup（Crypto: Prequel）

設問

問題文

The Prequel challenge is an RSA-like cryptosystem that employs primes to encrypt messages; your task is to determine if you can crack it.

さらに、以下の 2 つのファイルが与えられます。

「prequel.py」

#!/usr/bin/env python3

import sys
from Crypto.Util.number import *
from gmpy2 import *
from flag import flag

sys.set_int_max_str_digits(31337)

def keygen(nbit):
    p, q = [getPrime(nbit) for _ in '01']
    r = getRandomRange(int(sqrt(nbit)) - 6, int(sqrt(nbit)) - 2)
    el, eu = gmpy2.mpfr(0.313370), gmpy2.mpfr(0.313371)
    n = p ** r * q
    LB, UB = gmpy2.mpfr(n ** el), gmpy2.mpfr(n ** eu)
    while True:
        d = getRandomRange(int(LB), int(UB))
        if gcd(d, (p - 1) * (q - 1)) == 1:
            e = inverse(d, (p - 1) * p ** (r - 1) * (q - 1))
            pkey = (e, n)
            return pkey, p

def encrypt(pkey, m):
    e, n = pkey
    return pow(m, e, n)

nbit = 313
pkey, p = keygen(nbit)
leak = p >> (nbit - 110)
m = bytes_to_long(flag)
c = encrypt(pkey, m)

print(f'{pkey = }')
print(f'{leak = }')
print(f'{c = }')

「output.txt」

pkey = (944984216927923510201632892590973850396661004462637332470998692449473596147493056311556894274204384772245077199058201622663388870165853321514938390441922867744498045849562497498717541042273278722002724114323618415091788186436761530554704088831215674666508754493615190498409786246565421296815821144500053753541478115299818356208214842787878705507370000629490294894557563667238897580058365172647256838412804911793977543619952840345076821273688643340277663983978371517448815463676125262666981270106439865969562915113205738001725642662329402186543918540592857393236245561690138398624201831557408611329098686349160818187747866456142256107766608245109705394760161152149884966951412665124929307008884695153382823979103652331606374772643625454383796914104674926070440737555826764320704518088196526949189103136022725502727356347447898565076722293345812309904036148668484228145114845351597999627809134413162233694983260023335297935279362831629133363771856519138323406358741822257599256158338525479586263478550717041462562899067010275174754407304718504645899837079557969502458086794913151167168163806285282506054300509388486093311006086376253301164343501616847937093772055957157712109369148744534731794371877307459946892056516053189982899621716318353614392781697596182727270501967480050137271802789989335424116814956605897659695039346323148687277751797419022692731447626006685767185840351540024069735331584364371296637613, 1452555162484423094204272395668825864425858167951825248522254177355034320176317627983704814521987979462679209217224587843692961038072625276289088263063916312454063508971916392662126004169054114695929017189872344842892286936562800914894059094440706797590766534678617438546477291372961430694316631786751565980790336823391361448938562707595799561199804974728837382446309392345427392542054776375430173541164190267637089826224768787716175908383185937154106806666015608403587363740954913044238268027159138149560830255978411373953231081028917316810626513701549109082809033588325835995430775638183746573860855462601730060058435120347307880501033629111555041368645212535321038333226713439706850084390944584620390198451729423255029670597830696884057707298103661063645422201650193037579513548455396626285411554616298390654808282591666199594231724518220087029144900495621196610981488923195891882255051846054094193874725925891053828767058887465063408516838857255119107357554078884804766097567862856413776107172468608979963097253583645713425121828451445286685286957216700892272273593552825477661634343198333035487251526061944732509355481657352585099800059225933115925254158102061140222371901021148054134169351467725305515042483726174527900632582656051498291251313807505045410710795838591329757837318548396644822622741706027733589221502317111724928858949861047058614733251866097738666866237225371884800573975895583145334862421)
leak = 796956384442719989903800382564170
c = 38398501009318127402251454303185975044505725081432350072003179352912844506182592025548382411693404106121650125175767577630724584066093007682602717574297661159152529877504145970929948707672120710795817463378725702604444195035278070611986583089799626615006836373315737045972847903057330030714586759298718441702548958143092870823872602673742151510958310995416858464859985704940541327985501673157460094765400202880602253036196854992870865603595310724904723727741990509603676046235020285031674682809676916037159019396902506966869530813777561280788374053428609565028663190600600535950026961420175130542385344783206955617983310086360350162520714760190173399389436035543115475004638417438717844186849132794755110633153868496290621115586696624573124643680384266290308848912781595288421278677349450179551070029795438557683318778608173202855450178371350722473362466795524615544800311313780571398816927500141728472343934416335116140693015632760715583394126989965973932978513042231875305448899469799582957407701353226639056497214505485283678525029670740954711966488522384712245051906041944357637627673748756561944440203114633578364268572508791426432809743171091893729296358440839133044203227653938038939077922999044579549773015685362963501036164991181347497597220000860418745044206521748941309042190678006569494374554817208628917020688605352826432899301626704307738692382180316582310579631651507508469713046192636747409508

問題の分析

問題文にも書かれていた通り、RSA の亜種を扱った問題です。この手の問題は「本来のRSAとの違い」の部分に脆弱性があることが多いので、そこを中心に分析します。

まず、modulus の作り方が特徴的で、p**r*q の形をしています。さらにexponent についても一般的な 0x10001（65537）ではなく、d を先に決めてその値に依存して e が定められています。

提示されたスクリプトに出てくる値の中で、r は明記されていませんが、out.txt に記載された値から計算可能です。具体的には、p, q の bit 数と n の bit 数から、 r=14 であることが判ります。

さらに、LB と UB の値は n から計算できるので、d の値の範囲も計算可能で、1468bit の値になることが確定しています。

また、p の上位 110bit がリークされています。

ここまで分析した結果を踏まえ、雰囲気としては、CopperSmith 法を p もしくは d に適用して、といった感じがします。

検討

d は n に比べそこそこ小さいですが、それでも d のサイズがやや大きいことと、そもそも n の作り方が特殊なため「普通の」Boneh-Durfee 法は適用外となります。

しかし、同じ着想が使えそうなので、もう一度 e, d, p, q の関係を見直すことにします。

n = p**r*q なので、totient（φ(n)）は (p - 1)*p**(r - 1)*(q - 1) です*2。そのため、ある整数 k に対して、e*d - 1 = k*p**13*(p-1)*(q-1)が成り立ちます。左右の bit 数を比較すると、k の bit 数は 概ね d と同じくらいであることが判ります。

Boneh-Durfee 法では、k と s:=(p+q) // 2 を未知数と考え、eを法として CopperSmith 法を適用しますが、右辺の形を見ると s に相当する部分が大きすぎてしまいどうも良くなさそうです*3。

しかし、CopperSmith 法では n の約数を法とした解が算出できることを思い出し、 d を未知数とし p^r-1 を法とすれば良さそうだと思って試みることにしました。*4

ソルバ

「solve.py」

from Crypto.Util.number import *

pkey = (944984216927923510201632892590973850396661004462637332470998692449473596147493056311556894274204384772245077199058201622663388870165853321514938390441922867744498045849562497498717541042273278722002724114323618415091788186436761530554704088831215674666508754493615190498409786246565421296815821144500053753541478115299818356208214842787878705507370000629490294894557563667238897580058365172647256838412804911793977543619952840345076821273688643340277663983978371517448815463676125262666981270106439865969562915113205738001725642662329402186543918540592857393236245561690138398624201831557408611329098686349160818187747866456142256107766608245109705394760161152149884966951412665124929307008884695153382823979103652331606374772643625454383796914104674926070440737555826764320704518088196526949189103136022725502727356347447898565076722293345812309904036148668484228145114845351597999627809134413162233694983260023335297935279362831629133363771856519138323406358741822257599256158338525479586263478550717041462562899067010275174754407304718504645899837079557969502458086794913151167168163806285282506054300509388486093311006086376253301164343501616847937093772055957157712109369148744534731794371877307459946892056516053189982899621716318353614392781697596182727270501967480050137271802789989335424116814956605897659695039346323148687277751797419022692731447626006685767185840351540024069735331584364371296637613, 1452555162484423094204272395668825864425858167951825248522254177355034320176317627983704814521987979462679209217224587843692961038072625276289088263063916312454063508971916392662126004169054114695929017189872344842892286936562800914894059094440706797590766534678617438546477291372961430694316631786751565980790336823391361448938562707595799561199804974728837382446309392345427392542054776375430173541164190267637089826224768787716175908383185937154106806666015608403587363740954913044238268027159138149560830255978411373953231081028917316810626513701549109082809033588325835995430775638183746573860855462601730060058435120347307880501033629111555041368645212535321038333226713439706850084390944584620390198451729423255029670597830696884057707298103661063645422201650193037579513548455396626285411554616298390654808282591666199594231724518220087029144900495621196610981488923195891882255051846054094193874725925891053828767058887465063408516838857255119107357554078884804766097567862856413776107172468608979963097253583645713425121828451445286685286957216700892272273593552825477661634343198333035487251526061944732509355481657352585099800059225933115925254158102061140222371901021148054134169351467725305515042483726174527900632582656051498291251313807505045410710795838591329757837318548396644822622741706027733589221502317111724928858949861047058614733251866097738666866237225371884800573975895583145334862421)
leak = 796956384442719989903800382564170
c = 38398501009318127402251454303185975044505725081432350072003179352912844506182592025548382411693404106121650125175767577630724584066093007682602717574297661159152529877504145970929948707672120710795817463378725702604444195035278070611986583089799626615006836373315737045972847903057330030714586759298718441702548958143092870823872602673742151510958310995416858464859985704940541327985501673157460094765400202880602253036196854992870865603595310724904723727741990509603676046235020285031674682809676916037159019396902506966869530813777561280788374053428609565028663190600600535950026961420175130542385344783206955617983310086360350162520714760190173399389436035543115475004638417438717844186849132794755110633153868496290621115586696624573124643680384266290308848912781595288421278677349450179551070029795438557683318778608173202855450178371350722473362466795524615544800311313780571398816927500141728472343934416335116140693015632760715583394126989965973932978513042231875305448899469799582957407701353226639056497214505485283678525029670740954711966488522384712245051906041944357637627673748756561944440203114633578364268572508791426432809743171091893729296358440839133044203227653938038939077922999044579549773015685362963501036164991181347497597220000860418745044206521748941309042190678006569494374554817208628917020688605352826432899301626704307738692382180316582310579631651507508469713046192636747409508

e = pkey[0]
n = pkey[1]

#e*d -1 = k * (p-1)*p^13*(q-1)
#d: about 1468 bit

PR.<x> = PolynomialRing(Zmod(n))
f = e*x-1 #mod n => mod p^13 の解を狙う
f = f.monic()
d = int(f.small_roots(X=2^1468, beta=0.5)[0]) #betaはテキトーにセットした

print(long_to_bytes(pow(c,d,n)))

フラグ

ASIS{F4ct0r!n9_N=p**r*q_F0r_L4rG3_r_BDH_m3Th0d!!!}

おわりに（＋今年の総括）

感想として、本問は「過去の遺産」のおかげで辛うじて解けたような感じでした。しかし裏を返せば、「過去の遺産」を増やせば解ける問題も増えるということになります。

今年は色々と低調で、CTFも「だいぶ伸びしろがある」にもかかわらず、伸びるどころか低迷していた感じがしています。・・・とそう考えるとネガティブな感じになるのですが、視点を変えると「やり方や着眼点を見直す好機」とみることもできます。実は「チャンス到来」だったのかも！

ということで、来年は「読み書き・算盤」（Writeupの読み書きやUpsolve）を中心に、活発な活動を推進したいと思っています。

*1:個人的には大好きです。

*2:度忘れしていても、提供されるスクリプトから窺うことができます。

*3:うまい方法があるもかもしれませんが、自分は分かりませんでした。

*4:理論的検証はしていませんが、後日他の Upsolve とともにやろうと思っています。

Writeup ＆ Upsolve 〜復習するは我にあり〜

1. はじめに

1.1. この記事について

この記事は、CTF Advent Calendar 2024（CTF Advent Calendar 2024 - Adventar）の 20 日目 の記事です。

前日の記事は、はまやんはまやんはまやんさんの「Cryptoにおける祈りについて」でした。個人的には思わずニヤっとしてしまうところがありました。超お勧めです。 blog.hamayanhamayan.com

1.2. 注意事項（必ずお読みください）

• この記事は、主に CTF 初心者*1もしくはこれから CTF を始めるかもしれない方*2をターゲットにしたものです。日常的に CTF をプレイしている方、あるいは過去に CTF を反復継続的にプレイしていた方が読まれた場合、「何をいまさら！」というイライラ感が湧き出すぎてしまう虞がありますので、くれぐれもご注意ください。

• この記事はあくまで筆者の私見であり、客観性のある評価とは全く関係ありません。したがってスポンサー以外の方のクレームは一切お断りします*3！

• この記事を読んで得られる「技術的知見」は、ほぼ皆無であると考えられます。裏を返せば、日ごろテクニカル三昧で食傷気味の方にとって丁度よい塩梅である、という可能性は（些か）期待できるかもしれません。

• 「Writeup」と「Upsolve」を題材にしておりますが、本稿中に「Writeup」と「Upsolve」そのものは出しません。後日の別稿とします*4。

2. "Writeup"とは

　すでにご存知の方もいらっしゃるかとは思いますが、 CTF 文化を特徴づける要素として、競技後に解法を blog 等で公開する「Writeup」*5と呼ばれるものがあります。

　もし、まだ「Writeup」の実物を目にしたことがないのであれば、何でもよいので、ぜひ「実物」を一度みてみましょう*6。オープンな CTF に参加されたことがある方は、[問題のタイトル] + [CTF大会名称] + "Writeup" でググると自分が取り組んだ問題の Writeup に辿りり着けるかもしれません*7。

　ところで、「Writeup」を直訳した場合「書き上げる」、意味合いとしては自分が競技の中でどう振舞ったのかなどをレポートする、といったところになるのかと思います。しかし実際には、そういった訳語以上の「何か」があるように感じています。もう少し踏み込んで考えた場合の 「Writeup の意義」として、筆者は個人的に以下のような思いを持っています。

• その問題を解けなかった人や、競技に参加しなかった人を「同じ場所に導く」ための道標。

• 作問者へのリスペクトを表すもの。

• その問題に取り組んだ、自分にとっての振り返りの場。

　そして筆者はそれらが、CTF 文化の素晴らしい点の一つであることを確信しています。

2.2. Writup 講読のススメ

　CTF に慣れていないうちは特にそうですが、設問から解法にたどり着くまでに必要な技術的知識（スキルセット）は持っていても、実際の答えにたどり着けない場合があります。

　次節の「Upsolve」とも関連しますが、自分のもつ知見を CTF 競技に生かせるよう昇華もしくはアレンジする方法として、「大会への参加」だけでなく「Writeupの講読」も併せて行うことを強く推奨します。

　たとえば数学の授業*8を考えてみると、「命題（定理）の証明をトレースしたり意味を理解したりすることは出来ている（つもりだ）が、実際に数値を当てはめる計算ができなかったり、類題を自力で証明できなかったりすること」が、ままあるように思えます*9。俗にいう「完全に理解した」というスラングも、概ねそんな状態に近いものだと思います。それはある意味、行き詰っている状態であると見ることもできます。

　この状況を打破するための方法としては、「まだ自力で頑張る」「誰かの力を借りる」があります。自力で頑張ろうとする精神は立派ですが、それに拘りすぎるのは「極めて勿体ない」気がします*10。「Writeupを活用してパワーアップすることは、Writeup執筆者へのリスペクトでもあり、とても立派な事」という考え方で、行き詰ったら悩まず Writeup を捜して読んでみてはどうでしょうか。

　さらに言えば、何かに詰まったかどうかは関係なく、また自分の取り組んでいる分野に拘ることもなく、カジュアルに多くの Writeup を読み、じわりじわりと糧にしてゆくと良いのではないかと思う次第です。

2.3. Writup 執筆のススメ

　CTF に参加し、何らかの問題を自力で解けるようになったら、躊躇なく Writeup を書いてみましょう！個人的に、「Solve 数も多いし、自分が書かなくても・・・」という思想は悪だと思っています*11。「表現の自由」は権利です。権利を行使しようではありませんか*12！

　書き方は人それぞれ、誰かを傷つけるような内容でない限りは、何がダメなどというのはないと思います。ただ、個人的には、「解いたときに、こういう道筋で正解にたどり着いた」という部分*13を一番大事にしたいと思っています。・・・思ってはいるのですが、なかなか文章で表現しきれず、どうしても「思考の飛躍」の部分が残ってしまっている感じがしているので、どうにかしたいと思うのですが。。。

　また、「鉄は熱いうちに打て」という言葉もあるように、（大会の規約や受賞条件などの制約がない限りは）競技後すぐ書いて公開するのがベストでしょう。公開できる形にならないまでも、記事にする準備稿はまとめておいた方がタイムパフォーマンス的に見ても得策です。筆者の失敗パターンとしては、[Writeup後回し] ⇒ [長期放置（書く書く詐欺）] ⇒ [解いた時の気持ちを忘れていて書けない] ⇒ [お蔵入り] というのがありますので、「悪・即・斬」ならぬ「解・即・書」くらいの気持ちでやった方が良いはずです*14。

　「自分は文章を書くのは苦手」という方でも、チャレンジをあきらめないで欲しいです*15。筆・・・ではなくキーボードが止まった場合、（前小節に戻りますが）何人かの Writeup を読んで、「いいな」と思う表現方法を参考にしてみると良いでしょう。「Writeupを書いたら優勝」くらいの気持ちで、どんどん書きましょう*16。

3. Upsolve

3.1. "Upsolve"とは

　「Upsolve」も CTF 文化の特徴のひとつ*17であり、競技後に（競技中解けなかった／解かなかった）問題を解く行為のことです。

　Upsolve は競技参加者が競技後に行うというのが普通である、と考えられますが、競技後に問題セットが公開される大会（SECCONなど）や常設化される大会（AlpacaHackやpico CTFなど）では、リアルタイムで競技に参加していない方でも Upsolve が可能な場合があります。

　問題セットの公開や常設化は運営にとっては負担であるはずで、それをしていただけることは「とてもありがたい」と思っています。リスペクトと感謝しかありません。

3.2. Upsolve という名の「供養」

　Upsolve はただの「復習」ではありません！解けなかった問題への「復讐」であり、次なる大会への「予習」でもあるのです！時間が許すなら、やらない手はありません。

　Writeup とは別なところで Upsolve はパワーを必要としますが、Upsolve にもさまざまな考え方（アプローチ）があります。

　一つは、競技と極力同じ条件でチャレンジする方法。競技日の都合が悪く、参加できなかった場合などで腕試しをしたい時、この方法を採用することになります。

　そのほかにも、

• 誰かの Writeup をそのままトレースする（写経）
• Writeup を参考にしながら自分の手で解いてみる
• 複数の Writeup から解法（設問）の本質を探る
• 別解を捜す

などがあって、どのやり方を選ぶかは、Upsolve で何を得たいかによって変わってくるはずです。個人的には、問題の理解度に合わせて段階的に「写経」「考え方を参考に自力で実装」をやって、特に興味があるものについては「設問の本質を探る」「別解を捜す」など深掘りを行うのが良いのではないかと思っています。

　ところで、Upsolve には技術的な知見を得るという教育的効果のほかに、競技の中で心に生じた「モヤモヤ」を解消するという大きな役目があります。先の記事で「Writeup の講読」を勧めておいてアレなのですが、「解けなかった」悔しさは、解けた人の Writeup を読んだとき無限大に増幅されることがあります。そういった気持ちは極論すれば怨霊そのものです。ですので、供養が必要になるのです。Upsolve が時として「供養」と呼ばれるのは、そういうことなのだと（勝手に）思っています。

　深掘りした場合は特に、Upsolve したものを Writeup するのも良いかと思います。但し、常設化されている場合は公表できる範囲に関する規約に注意し、規約に明記がなくてもフラグを記事に直接記載しないなどの配慮もしておくべきでしょう。

　そこそこ長くなりましたので、Upsolve については次の言を以てシメることとします：

「解けなかったことを気に病むことはない。ただ Upsolve して、次の糧にすればいい。それが、CTFer の特権だ。」

4. おわりに

　「色々言ってるけど、Writeup も Upsolve も、お前ロクにやってねーじゃん！」という天の声が聞こえてきます。

　ハイ、その通りです。サーセン。

　どちらも「やらなくてもいい」ものです。サボったからと、誰かに責められるものではありません。

　しかし、書いた方が、やった方が「楽しい」し「強くなれる」に決まっています。

　来年は、参加する競技数を絞り Writeup と Upsolve に軸をシフトしながら、 自身の能力向上に加え、CTF コミュニティの盛り上げに微力ながらも貢献できればと思っています。少しの間冬眠しますが、拙文に最後まで付き合っていただいた方とは、またいつか、どこかで会って感謝の気持ちを直接お伝えできることを祈念して、本稿を終えることとします。

　See you next CTF!!

*1:ここでいう「初心者」は、CTF という競技の経験が浅い方のことを意味します。コンピュータ関連の知識の多寡を問うてはいない点に注意してください。

*2:長らく離れていて記憶がかなり薄れているようなケースも含みます。

*3:金額にもよりますが、スポンサーになっていただけるのならクレームを歓迎する場合もあります。

*4:ネタとしては TSG CTF 2024 や SECCON 13 Quals があるのですが、準備が間に合わなかったため。

*5:正確には、「write up」もしくは「write-up」と書くべきなのかもしれませんが、本質的ではないのでこの記事では「Writeup」に統一します。Upsolveも同様。

*6:ちなみに、当ブログにも Crypto 分野のものを中心にいくつか掲載しています

*7:外国語が苦でなければ、CTFTimeのリンクから辿ることもできます。

*8:大学で数学専攻の方は、高校までではなく大学の授業の方を思い出していただいたほうがシックリ来るかと思います。

*9:優秀な人でそういう経験がない場合は、想像力を働かせてみてください。

*10:自戒。。。

*11:自分も時々やってしまうので、自戒・・・。

*12:余談ですが、「権利の主張は悪」という風潮がすごく嫌いです。「自己の権利の主張」は「他者の権利の尊重」と一体なのですけど。何が悪いんですかね。。。

*13:論文などでは決して表に出ない部分です。

*14:またまた自戒・・・自戒・・・。

*15:おこがましい言い方ですみません。

*16:予選突破条件として Writeup が求められる大会もあるので、ガチ勢になりたい方はある意味必須課題であるともいえます。

*17:発祥は「競技プログラミング」であると言われていますが。

AlpacaHack Round 4 (Rev) writup

1. はじめに

　2024/10/5 12:00(JST) - 18:00(JST) に開催された「AlpacaHack Round 4 (Rev)」に「edwowmath」として参加しました。

　1 問だけ解いた*1ので、その writeup を公開します。

2. writeup

Simple Flag Checker

設問

A simple flag checker :)

　「checker」という 17,048 バイトのファイル（ELF）が提示されます。

検討

・表層解析

　CTF の rev 1 問目は strings で出ることもあるので念のため確認しましたが、案の定フラグはありません*2。

　IDA free で開き中を見てみると、表面的にはフラグのチェックをして結果を表示するシンプルなもので、

angr でやれるか試したのですが不首尾でした*3。

・静的解析

　IDA free で疑似コードを表示してみると、チェックは1文字ごとに行われていて、「update」関数に入れた結果とテーブルにあるデータが一致するかどうかで判定しているようです。

　update 関数の中の処理は複雑で、移植はキツそうです*4。

　また、判定する文字数として、バイナリの 0x1A41 番地に「0x31」がハードコードされています。

　このバイナリを改変し、バイナリの 0x1A41 番地の値を [判明済み文字数+1] すれば、総当たりで次の 1 文字分を判明させることができそうです。

解法

　バイナリの改変と試行を手作業でやるのは辛いので、python でプログラムを作って実行させました。

　フラグは "Alpaca{" から始まるはずなので、その部分の処理は省略しています*5。また、総当たりする文字種は Ascii コードで 0x30～ 0x7e と guessしました。

「solve.py」

import subprocess
import time
source = "checker"
dest = "./_checker"

known_flag = "Alpaca{"
binary = open(source, "rb").read()

for i in range(8,50):
  with open(dest, "wb") as f:
     f.write(binary[:0x1A41] + i.to_bytes(1,"big") + binary[0x1A42:])
  time.sleep(0.5)
  for c in range(0x30, 0x7f):
    proc = subprocess.Popen(dest, stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=subprocess.PIPE)
    stdout, stderr = proc.communicate(input=(known_flag + chr(c)).encode()) 
    if b"Correct" in stdout:
      known_flag += chr(c)
      print(known_flag)
      break

フラグ

フラグの記載は、本問が常設化されるため省略します

　想定解法がこの方法なのか、もっとスマートなやり方があるのかは、他の方の writeup を読んで把握したいところです。

3. おわりに

　次回は 2 問以上解けるよう精進します。 　

*1:1 問しか解けませんでした。

*2:まぁ、そりゃそうですね。

*3:まぁ、そりゃそうですねと思い、深追いせず。

*4:やる人はやるのでしょうけど。

*5:もちろんフラグ未知からスタートしても可。

IERAE CTF 2024 writeup（兼 参加記）

※2024/9/26 一部加筆修正

1. はじめに

　2024/9/21 15:00(JST) - 9/22 15:00(JST) に開催された「IERAE CTF 2024」に、チーム「N30Z30N」の総帥「EdwowMath」*1として参加しました。いつもの通り crypto 全完を目指しましたが 3 問を残してしまい、結果は 15位（1891pts）でした*2。

2. 参戦状況

2.1. 準備について

　準備については、前日良く寝ることを最優先にしました。「いのちだいじに」というやつですね。

　なお、宿題*3はサボってしまい、8月31日の憂鬱な児童／生徒*4を追体験しました。

　また、競技直前の食事は「ゲン担ぎのカツ」が定番でしたが、あまり効き目がない*5ので、今回は代わりにウインナーソーセージ*6としました。

2.2. 競技ログ的なもの

　競技開始から終了までは以下のような流れでした（時刻は概算です）。

• 9/21 15:00 競技開始。BGM は森口博子のアニソン*7。
• 9/21 15:01 サーバがバグっていて（？）、問題のIPアドレス、ポート番号が見えなくて辛い。*8
• 9/21 15:10「assignment」のフラグゲット。
• 9/21 16:10「derangement」のフラグゲット。
• 9/21 17:45「splitting」のフラグゲット。この問題でかなり体力を使い果たす。
• 9/21 17:50「OMG」のフラグゲット。
• 9/21 18:00 ディナー休憩＆「名探偵コナン」視聴。
• 9/21 19:00 気力・体力が回復したので競技再開。
• 9/21 19:50「Weak PRNG」のフラグゲット。
• 9/21 20:05「Luz Da Lua」のフラグゲット。
• 9/22 01:20「Heady Heights」のフラグゲット。眠気MAXで就寝準備に入る。
• 9/22 01:40「Free Your Mind」の解法を思いつくが眠くて手が動かない。
• 9/22 02:20 寝落ち寸前、枕元で「Free Your Mind」のフラグゲット。
• 9/22 02:30 就寝。
• 9/22 07:30 起床。5時間寝たはずなのに、かなりグロッギー。
• 9/22 08:00 モーニング：頭がボンヤリしているので意図的に過剰摂取。
• 9/22 09:00 競技再開。「cluster」「enjoyable-lattice」に取り組むも、虚無を重ねる。
• 9/22 12:30 虚無を続けながらランチ。引き続き延々と虚無タイム*9。
• 9/22 15:00 競技終了*10。

2.3. 感想的なもの

　結果的に、最初の 12 時間でやれる問題が尽きた、といった感じでした。翌朝は「crypto の残りをやる」か「他分野の warmup～easy にチャレンジ」かの二択*11だったのですが、前者を選んだ末に、前のめりに倒れました。

　プレイ時間的には 24 時間の大会が自分に合っているような気がしています。24 時間フル稼働は体力的にキツくなってきましたが、実稼働12～15時間程度で成果を出せるよう腕力を鍛えておけば良いですし、何より 24 時間ならばバイオリズムに合わせてプレイ時間を選択できますので。

3. writeup（Crypto）

3.1 [warmup] derangement（149pts, 106solved）

設問

I've made a secret magic string, perfectly encrypted!

nc (redacted)

サーバ接続先と、ソースファイルが提供されます。

「challenge.py」

#!/usr/bin/env python

from os import getenv
import random
import string
import sys

FLAG = getenv("FLAG", "TEST{TEST_FLAG}")

LENGTH = 15
CHAR_SET = string.ascii_letters + string.digits + string.punctuation

def generate_magic_word(length=LENGTH, char_set=CHAR_SET):
    return ''.join(random.sample(char_set, length))

def is_derangement(perm, original):
    return all(p != o for p, o in zip(perm, original))

def output_derangement(magic_word):
    while True:
        deranged = ''.join(random.sample(magic_word, len(magic_word)))
        if is_derangement(deranged, magic_word):
            print('hint:', deranged)
            break

def guess_random(magic_word, flag):
    print('Oops, I spilled the beans! What is the magic word?')
    if input('> ') == magic_word:
        print('Congrats!\n', flag)
        return True
    print('Nope')
    return False

def main():
    magic_word = generate_magic_word()
    banner = """
/********************************************************\\
|                                                        |
|   Abracadabra, let's perfectly rearrange everything!   |
|                                                        |
\\********************************************************/
"""
    print(banner)
    connection_count = 0

    while connection_count < 300:
        print('type 1 to show hint')
        print('type 2 to submit the magic word')
        try:
            connection_count += 1
            user_input = int(input('> '))

            if user_input == 1:
                output_derangement(magic_word)
            elif user_input == 2:
                if guess_random(magic_word, FLAG):
                    break
                sys.exit()
            else:
                print('bye!')
                sys.exit()
        except:
            sys.exit(-1)
    
    print('Connection limit reached. Exiting...')

if __name__ == "__main__":
    main()

検討

　提供されたソースを解読すると、magic word について以下のことが分かります。

• 文字数は15文字。
• 文字種は文字コード 0x21～0x7e の Ascii 文字で、高々1回だけ使われる。
• ヒントは magic word を並べ替えたもので、なおかつどの1文字も元の magic word と同じ位置にはない。
• 1つのインスタンスで、ヒントの取得と照合を合わせて 300 回（つまり、ヒントの入手は最大 299 回）までサーバと対話可能である。

解法

　各文字位置において14種類の文字が出現している程度にヒントを多く集めれば、正解の magic word を決定できます。

　運悪く*12集まらなかった場合、消去法を重ねて正解を得ることができる場合もありますが、その処理を書くよりもうまく集まるまで再試行したほうが合理的と考えました。

　作成したソルバでは、ヒント収集と使われていない文字の判定機能だけを入れています。

「solve.py」

from Crypto.Util.number import *
from pwn import *

HOST = <redacted>
PORT = <redacted>

r = remote(HOST, PORT)

data_dict = {}
for i in range(15):
  data_dict[i] = []

def set_data(data):
  for i,c in enumerate(data):
    if not c in data_dict[i]:
      data_dict[i] += [c]

def check_data():
  for i in range(15):
    if len(data_dict[i]) != 14:
      return False
  return True

def get_magic_word():
  mw = ""
  for i in range(15):
    for c in charset:
      if not c in data_dict[i]:
        mw += c
        break
  return mw

charset = []

for i in range(299):
  r.readuntil(">")
  r.sendline(b"1")
  data = r.readline().strip().decode().replace("hint: ", "")
  assert len(data) == 15
  if charset == []:
    charset = list(data)
  set_data(data)
  if check_data():
    print("ok, now prepared!", i)
    break

magic_word = get_magic_word()
print(f"magic_word: {magic_word}")
r.readuntil(">")
r.sendline(b"2")
r.readuntil(">")
r.sendline(magic_word.encode())

print(r.readline())
print(r.readline())
r.close()

フラグ

IERAE{th3r35_n0_5uch_th!ng_45_p3rf3ct_3ncrypt!0n}

3.2 [easy] Weak PRNG（185pts, 54solved）

設問

Do you understand the traits of that famous PRNG?

nc (redacted)

サーバ接続先と、ソースファイルが提供されます。

「challenge.py」

#!/usr/bin/env python

from os import getenv
import random
import secrets

FLAG = getenv("FLAG", "TEST{TEST_FLAG}")


def main():
    # Python uses the Mersenne Twister (MT19937) as the core generator.
    # Setup Random Number Generator
    rng = random.Random()
    rng.seed(secrets.randbits(32))

    secret = rng.getrandbits(32)

    print("Welcome!")
    print("Recover the initial output and input them to get the flag.")

    while True:
        print("--------------------")
        print("Menu")
        print("1. Get next 16 random data")
        print("2. Submit your answer")
        print("3. Quit")
        print("Enter your choice (1-3)")
        choice = input("> ").strip()

        if choice == "1":
            print("Here are your random data:")
            for _ in range(16):
                print(rng.getrandbits(32))
        elif choice == "2":
            print("Enter the secret decimal number")
            try:
                num = int(input("> ").strip())

                if num == secret:
                    print("Correct! Here is your flag:")
                    print(FLAG)
                else:
                    print("Incorrect number. Bye!")
                break
            except (ValueError, EOFError):
                print("Invalid input. Exiting.")
                break
        elif choice == "3":
            print("Bye!")
            break
        else:
            print("Invalid choice. Please enter 1, 2 or 3.")
            continue


if __name__ == "__main__":
    main()

検討

　Mersenne Twister (MT19937) の過去ステートを復元できればフラグをゲットできそうです。ところで Mersenne Twister のステートは、32ビットの値624個を集めることで構成できることが知られてます。

　Mersenne Twister については SECCON Beginners CTF 2022 で出題されていたのですが、その時スクリプトキディしていたので今回もスクリプトキディすることにしました。進歩無くてゴメンナサイ。

　しかしながら、2022 年のものと今回の設問とは少し内容が異なるので、本問にそのまま利用できそうなスクリプトを改めて捜したところ、以下のものを見つけました。

zenn.dev

　簡潔にまとめられていて、とても分かりやすかったです。

解法

　くどいようですが、ほとんど「スクリプトキディ」です。スクリプトをそのまま使えるようなデータの取り方をしています。

「solve.py」

from Crypto.Util.number import *
from pwn import *

##########################################################################
#https://zenn.dev/hk_ilohas/articles/mersenne-twister-previous-state
##########################################################################
def untemper(x):
    x = unBitshiftRightXor(x, 18)
    x = unBitshiftLeftXor(x, 15, 0xefc60000)
    x = unBitshiftLeftXor(x, 7, 0x9d2c5680)
    x = unBitshiftRightXor(x, 11)
    return x


def unBitshiftRightXor(x, shift):
    i = 1
    y = x
    while i * shift < 32:
        z = y >> shift
        y = x ^ z
        i += 1
    return y


def unBitshiftLeftXor(x, shift, mask):
    i = 1
    y = x
    while i * shift < 32:
        z = y << shift
        y = x ^ (z & mask)
        i += 1
    return y


def get_prev_state(state):
    for i in range(623, -1, -1):
        result = 0
        tmp = state[i]
        tmp ^= state[(i + 397) % 624]
        if ((tmp & 0x80000000) == 0x80000000):
            tmp ^= 0x9908b0df
        result = (tmp << 1) & 0x80000000
        tmp = state[(i - 1 + 624) % 624]
        tmp ^= state[(i + 396) % 624]
        if ((tmp & 0x80000000) == 0x80000000):
            tmp ^= 0x9908b0df
            result |= 1
        result |= (tmp << 1) & 0x70000ccf
        state[i] = result
    return state
##########################################################################

HOST = <redacted>
PORT = <redacted>

r = remote(HOST, PORT)
data = []

for i in range((624//16)*2):
  r.readuntil(b"> ")
  r.sendline(b"1")
  r.readline()
  for _ in range(16):
    x = int(r.readline().strip().decode())
    data.append(x)

xs = data[623:1247]
mt_state = [untemper(x) for x in xs]
prev_mt_state = get_prev_state(mt_state)
random.setstate((3, tuple(prev_mt_state + [0]), None))
secret = random.getrandbits(32)

r.readuntil(b"> ")
r.sendline(b"2")
r.readuntil(b"> ")
r.sendline(str(secret).encode())
print(r.readline())
print(r.readline())

フラグ

IERAE{WhY_4r3_n'7_Y0u_u51n6_4_CSPRNG_3v3n_1n_2024}

3.3 [easy] splitting（255pts, 21solved）

設問

Do you need to solve many ECDLPs?

nc (redacted)

サーバ接続先と、ソースファイル（sage、requirements、Dockerfile）が提供されます。

「challenge.sage」

#!/usr/bin/env sage

from Crypto.Util.number import *
from os import getenv

FLAG = getenv("FLAG", "TEST{TEST_FLAG}").encode()
f = bytes_to_long(FLAG)

p = random_prime(2^128)
Fp = GF(p)
a, b = Fp.random_element(), Fp.random_element()
E = EllipticCurve(Fp, [a, b])

print(a)
print(b)
print(p)

gens = list(E.gens())
if len(gens) < 2:
    gens.append(ZZ(Fp.random_element()) * E.gens()[0])

res = []
while f > 0:
    r = Fp.random_element()
    res.append(ZZ(r) * gens[f & 1])
    f >>= 1

for R in res:
    print(R.xy())

検討

　楕円曲線問題です。p、a、b のパラメータは素直に与えられるので、そのあたりが「easy」の理由なのかと思いました。

　E.gens()は、「点のスカラー倍」により定義される群の生成元を求める関数ですが、生成元の個数は楕円曲線によって異なります。リスト gens には、生成元が 2 つ入る場合と、（唯1 つの）生成元とそのスカラー倍が入るケースが 生じます。

　得られるオラクルは、フラグのビット毎に gens[bit] のスカラー倍を計算した結果です。DLP を解けば gens のどちらが選ばれたかが判明しますが非現実的ですので、ほかの方法を考えることになります。

　一つの方法として、「もし E.gens() が 2 つの生成元を返している場合、E.gens() で与えられる 2点 について、オラクルで与えられた点との Weil-pairing を計算し、もし片方だけ 1 になればそちらがアタリ*13」という事実を利用するというのがあり、今回はそれを採用しました。

　ただし、 一般には未決箇所が生じ得るため、複数回繰り返して全ビットが決定できるまで実行することとしました。

解法

　処理の煩雑さを避けるため、採用する楕円曲線の条件として

• E.gens() で得られる元の個数が 2
• E.gens() で得られる元のorderはどちらも同じ

としたのですが、この条件は思ったよりシビアだったらしく、サーバに要らぬ負荷をかけてしまったのかもしれません。

　また、サーバ上での E.gens() と ローカルでの E.gens() で順序が異なる場合があるようで、それに気づかずハマってしまいました（途中、その判定を入れています）。

　※このように、この解き方はエレガントではない気がするので、本問を解いていない方につきましては他の方の writeup もお読みいただくことを強く推奨します。

「solve.sage」

from Crypto.Util.number import *
import json
from pwn import *

def merge_flag(new_flag, base_flag):
  if base_flag == "":
    return new_flag
  ret = ""
  for cn, cb in zip(new_flag,base_flag):
    if cb == "?":
      ret += cn
    else:
      ret += cb
  return ret

HOST = <redacted>
PORT = <redacted>

flag = ""

while(True):
  points = []
  while(True):
    r = remote(HOST, PORT)
    a = eval(r.readline().decode().strip())
    b = eval(r.readline().decode().strip())
    p = eval(r.readline().decode().strip())
    E = EllipticCurve(GF(p),[a,b])
    gens = list(E.gens())
    if len(gens) !=2:
      r.close()
    elif gens[0].order() != gens[1].order():
      r.close()
    else:
      for _ in range(567):
        points.append(eval(r.readline().decode().strip()))
      r.close()
      break
  G = list(E.gens())[0]
  H = list(E.gens())[1]
  n = G.order()
  P0 = E(points[0])
  if G.weil_pairing(P0, n)==1 and H.weil_pairing(P0,n) != 1:
    G, H = H, G
  elif G.weil_pairing(P0, n)==1 or H.weil_pairing(P0, n)!=1:
    continue
  _flag = ""
  for P in points:
    P = E(P)
    if G.weil_pairing(P, n)==1 and H.weil_pairing(P,n) != 1:
      _flag = "0" + _flag
    elif G.weil_pairing(P, n)!=1 and H.weil_pairing(P, n)==1:
      _flag = "1" + _flag
    else:
      _flag = "?" + _flag
  flag = merge_flag(_flag, flag)
  if "?" not in flag:
    print(long_to_bytes(int(flag,2)))
    break

フラグ

IERAE{7de6b745404269a0d7b40955047921c6860e4438c73eb095090e75c8fb00cb51}

3.4 [medium] Heady Heights（397pts, 5solved）

設問

It's Perfectly Safe!

ソースコードと出力データが与えられます。

「chall.sage」

from sage.all import *
import flag

BITS = 88
K = 8


def random(lower_bound=0, upper_bound=2 ^ BITS, bits=None):
    return ZZ.random_element(lower_bound, upper_bound)


def random_bits(bits):
    return random(2 ^ (bits - 1), 2 ^ bits)


p = next_prime(random_bits(BITS))
m = ZZ(flag.FLAG.encode().hex(), 16)

a, b, E = None, None, None
P = None
Q = None
R = None

while True:
    a = random_bits(BITS)
    b = random_bits(BITS)
    E = EllipticCurve(Zmod(p ^ K), [a, b])
    try:
        P = E.lift_x(1337)
        break
    except:
        continue

while True:
    secret_key = random(upper_bound=p ^ (K - 1))
    x0 = (secret_key * m) % (p ^ K)
    try:
        R = E.lift_x(x0)
        break
    except:
        continue

Q = secret_key * P


def xy(P):
    t = P.xy()
    return ZZ(t[0]), ZZ(t[1])


x1, y1 = xy(P)
x2, y2 = xy(Q)
x3, y3 = xy(R)

print((x1, x2, x3))
print((y1, y2, y3))

「transcript.txt」

(1337, 108758038897050520831860923441402897201224898270547825657705075428051130846061735614252293345445641285591980004736447964462956581141116321772403519125859758137648644808920743070411296325521866392898376475395494, 5438451076181919949694350690364579526012926958491719881284366792649670689294870931317007945903275017524668258922051576064401873439529896167369498669912618211164397682696947429627504905294350782410183543966679528)
(2356240417146305163212384832005924367753484871437731042165238964932920608988096746757585282365391701455222258919772283748442969489163122612874542328479985011793178437324509351503404273134948028573603448460822465, 5224211491008373131406603536527981755345757742567201307027247664784412223361972085071271594280642689356776497337283996518196426296230388008390390705691353643411319840725993589925599219787596133403802269715179842, 1255469150673352477643406441586559401886808227235272570913194477760462899397412967437903450228715079681927518702031385236882455686813595191144244687009073603134094899106009798791920033413388436982273752206346286)

検討

　同一曲線上の 3 つの点が与えられているので、p, a, b のパラメータを復元します。

　また、modulus は p 冪であるため、DLP は p進数体 Qp に写して計算する手法が使えそうです。

解法

　パラメータの復元を試みましたが、p^K を含む大きな数が出てきてしまい参りました。

xs=(1337, 108758038897050520831860923441402897201224898270547825657705075428051130846061735614252293345445641285591980004736447964462956581141116321772403519125859758137648644808920743070411296325521866392898376475395494, 5438451076181919949694350690364579526012926958491719881284366792649670689294870931317007945903275017524668258922051576064401873439529896167369498669912618211164397682696947429627504905294350782410183543966679528)
ys=(2356240417146305163212384832005924367753484871437731042165238964932920608988096746757585282365391701455222258919772283748442969489163122612874542328479985011793178437324509351503404273134948028573603448460822465, 5224211491008373131406603536527981755345757742567201307027247664784412223361972085071271594280642689356776497337283996518196426296230388008390390705691353643411319840725993589925599219787596133403802269715179842, 1255469150673352477643406441586559401886808227235272570913194477760462899397412967437903450228715079681927518702031385236882455686813595191144244687009073603134094899106009798791920033413388436982273752206346286)

BITS = 88
K = 8

PR.<a_,b_> = PolynomialRing(ZZ)
f1 = ys[0]**2 - xs[0]**3 - xs[0]*a_ - b_
f2 = ys[1]**2 - xs[1]**3 - xs[1]*a_ - b_
f3 = ys[2]**2 - xs[2]**3 - xs[2]*a_ - b_

I = ideal([f1,f2,f3])
B = I.groebner_basis()

a__ = -PR(B[0]).coefficients()[1]
b__ = -PR(B[1]).coefficients()[1]
modulus = int(B[2])

mod1 = int(f1(a_=a__,b_=b__))
mod2 = int(f2(a_=a__,b_=b__))
mod3 = int(f3(a_=a__,b_=b__))

G1 = GCD(mod1,mod2)
G2 = GCD(G1,mod3)
G = GCD(G1,modulus)
#30558817863616547841843215194014864539068601822214696308287137799717866291127202506493151238616054827947647196976316863155266996859496629123724363522444478764916846435304507606468278908320828802715927250941730536531110798374352712159696646923245204044379258915385591315211835465988858640230668256688566076289380353779292102988630405407369907253598873884384366060049339156771913629141234111513265795360764711403547653114352883407706891829153033706611402191495800954413720317602766998979308992285534585671642880057317532886292784472691679897391231094240818130992778968500768685820614713085268151999207572917295898805168213373284565248186998191684846575640741202096132127940943495912748353490333915451347709502280466322023578650893942333911655962330155913700470326378392862400970986881976562980886133403004733804192676038419

　「yafu」で素因数分解を試み、しばらくして中断したところ目的の p と思われる数「223490196137382483691737269」が出てきました。

　DLP パートは mitsu さん*14のスクリプトを微調整のうえ使わせていただきました。

hackmd.io

p = 223490196137382483691737269
R = Zmod(p^K)
a = R(a__)
b = R(b__)
E = EllipticCurve(R, [a, b])
E0 = EllipticCurve(GF(p), [a, b])
od = E0.order()

P = E((xs[0],ys[0]))
Q = E((xs[1],ys[1]))
R = E((xs[2],ys[2]))

#################################################
# https://hackmd.io/@mitsu/ByhK-tZX_
#################################################
prec = 8
Qp = pAdicField(p, prec)
Ep = EllipticCurve(Qp, [a, b])
Fp = GF(p)
Ef = EllipticCurve(Fp, [a, b])
N = Ef.order()

P_p = Ep(P)
Q_p = Ep(Q)
NP_p = N * P_p

a = Fp(-NP_p[0] / (p * NP_p[1]))
n = 0
l = 1
Sp = P_p
Tp = Q_p
ds = []
while Tp != 0:
    NTp = N*Tp
    w = -NTp[0] / NTp[1]
    b = w / p^l
    d = Fp(Integer(b)/a)
    ds.append(Integer(d))
    Tp = Tp - Integer(d)*Sp
    Sp = p*Sp
    n += 1
    l += 1
    if n > prec:
        break

secret_key = 0
for i in range(len(ds)):
    secret_key += ds[i] * p^i
#################################################
from Crypto.Util.number import *

assert secret_key * P == Q
m = xs[2] * pow(secret_key, -1, p^K) % (p^K)
print(long_to_bytes(int(m)))

フラグ

IERAE{44b508bb0782d3daf78d8afbb260fc75862a167414f2e99c4acda2e61960f4d6}

3.5 [hard] Free Your Mind（361pts, 7solved）

設問

We need a Purest Unobtainium

nc (redacted)

サーバ接続先と、ソースファイルが提供されます。

「chall.sage」

#!/usr/bin/env sage

from sage.all import *
import flag
import sys
import os

sys.stdout = os.fdopen(sys.stdout.fileno(), 'w', buffering=1)
sys.stderr = os.fdopen(sys.stderr.fileno(), 'w', buffering=1)
sys.stdin = os.fdopen(sys.stdin.fileno(), 'r', buffering=1)

# Initial configuration
UCF = UniversalCyclotomicField()
zeta = UCF.zeta(11).to_cyclotomic_field()

eta = zeta^2 + zeta^-2

# NF is a finite Galois extension of the rational field, hence NF is a simple extension of the rational field
NF.<omega> = NumberField(eta.minpoly())
deg = NF.degree()

CRITERIA = 2^16
BITS = 2048

def main():
    print("Welcome to *Number Theoretic* Encryption Oracle!")

    print("Enter your request key:")
    coeffs = []
    # you can enter any element of NF because omega's coefficient is controllable :)
    # ...but smaller value is prohibited to prevent cheating!
    for _ in range(deg):
        x = input().replace(" ", "")
        if "/" in x: 
            p, q = x.split("/")
            p = int(p)
            q = int(q)
            g = gcd(p, q)
            p /= g
            q /= g
            if abs(p) < CRITERIA or abs(q) < CRITERIA:
                print("You can't cheat!")
                return
            coeffs.append(QQ(p) / q)
        else:
            x = int(x)
            if abs(x) < CRITERIA:
                print("You can't cheat!")
                return
            coeffs.append(x)

    print("We got your request key")
    # your element is here
    alpha = sum(x * omega^i for i, x in enumerate(coeffs))

    # we use the norm of `alpha` for RSA's public key
    # class group order is not used here, because it is too complicated to compute :(
    e = alpha.norm()
    set_random_seed(int(str(alpha).encode().hex(), 16) * current_randstate().ZZ_seed()) # Add to the entropy pool
    p = random_prime(2^BITS)
    q = random_prime(2^BITS)

    N = p * q
    d = Mod(e, (p - 1) * (q - 1))^-1
    # print(f"{e = }") <- you don't need it because you can compute it, isn't it?
    print(f"{N = }")
    msg = ZZ(flag.FLAG.encode().hex(), 16)
    assert msg < N
    c = ZZ(Mod(msg, N)^e)
    assert Mod(c, N)^d == msg
    print(f"Enc(flag) = {c}") # Can you get the FLAG?

if __name__ == "__main__":
    try:
        main()
    except:
        print("Are you kidding me?")

検討

　RSA問ですが、プレイヤーはある制約のもとで、 exponent を決めることができます。

　NF は円の 11 分体の部分体で、有理数体上5次の巡回拡大体です。omega はその生成元です。プレイヤーは、NF の元 alpha を指定できますが、omega の 4 次式で表現したとき係数の絶対値が全て 2¹⁶=65536 以上である必要があります。e は alpha の NF/Q での ノルム（以下、単に「ノルム」といいます。）として決まります。

　もし、e を 1 に出来れば flag == enc(flag) ですし、-1 でも modN の逆数をとることで容易に復号できます。

　ここで、「単数はノルムの絶対値が 1」であることや「単数のべき乗は単数」であることなどを思い出せば、適当な単数を何乗かして係数の絶対値が大きな単数を用意できれば OK、という方針が立ちます*15。

解法

SageMath の units() で、NF の単数を列挙します。

UCF = UniversalCyclotomicField()
zeta = UCF.zeta(11).to_cyclotomic_field()

eta = zeta^2 + zeta^-2
NF.<omega> = NumberField(eta.minpoly())
NF.units()

(omega^4 + omega^3 - 3*omega^2 - 3*omega,
 -omega^3 + 3*omega,
 -omega^3 + 3*omega - 1,
 omega^2 - 2)

　一番最初のやつが良さげですので、これを何乗かしてゆき条件を満たすものを算出します。

u = omega^4 + omega^3 - 3*omega^2 - 3*omega
alpha = u
while(True):
  alpha *= u
  if all([abs(c)>2^16 for c in alpha.list()]):
    break
print(alpha)

180037*omega^4 + 329615*omega^3 - 446292*omega^2 - 910899*omega - 216694

　サーバに接続し、pow(ploof of work) を解くと係数入力を受け付けますので、そこで -216694, -910899, -446292, 329615, 180037 の順に入力します。

　サーバは以下の値を返してきました。

N = 672228754547333564050159768595843231928243017327963894062986465373907451434272917627617328454654197286927461692326312394468078179164499976278470684142359000264286018200152003430020389125971534032344068309799095519490777996214801831138731576771773843542589480334000065038155940444820535590908849002637357115468530321760011365632331392719771646640417862231137606425856177676435845682410108211068641269847031524661557429819182723628076861043453224374573315196879989798460979396633144477536385595200827605663858572618832354965320705544153230217747319146157362846931033191115405436359059164369837886047545786784269972638543358070538110289573835904005155690269896801808285722482531209154145575023812797780986255049727529641861584796117205935895183538098160170745098973684976756630890804100890067664824642639589092432914498898600120332970813163043157838253047471232626526780521581486639131459983425407847086254674037377756949248113825642432087864942531245034742209381745688731273006510527134001938247811070510995132023678846496996678177796483605667198767129200358475944856250446358744125712853772318008884032107371472320376580231615493704518092986087002921898258237508069533598512214713469385221963034901057530843804769093689283128565687431
Enc(flag) = 430499849081337663832081920302659618751659875427051018870197208017664953238487473697352845290325544558064899797877046545208347216414865382064980917304875592602446404287228402964383579305270095250734057603750747065366921659580644160152473380518670632941045017536731197059772871900986149981535038527031360103525319691941766128222314209311120251691166369664393920271849371046788352052155707160091755619094924755859793996988286006616247538158486359146970822170451500192576559845128261837579098250545624760450362977788583508716897058975264111924665106391329783978595651208527595611582119230360624111244548921513723226191731589212301229764695429479496204856592478811960728805890970175244763355423026191823803360395528834304960509188373885372696883907597362083966102533343273087325044123519704598407719702988894224878081932701140954856595078098758618752549476793719456758592831569352050676494359558243641089383213200444196033632442145314272495788695894145969680805976395707219351221345884444293803025691868351359591770938097219639258118437571302668758237868578993441887711408196331006385922293764488028486104415885810234337945236111227561847482107834722196762384666506658799478200494160789233470589732679953979834202530567057239680670006988

　以下の通り、フラグを復号します*16。

N = 672228754547333564050159768595843231928243017327963894062986465373907451434272917627617328454654197286927461692326312394468078179164499976278470684142359000264286018200152003430020389125971534032344068309799095519490777996214801831138731576771773843542589480334000065038155940444820535590908849002637357115468530321760011365632331392719771646640417862231137606425856177676435845682410108211068641269847031524661557429819182723628076861043453224374573315196879989798460979396633144477536385595200827605663858572618832354965320705544153230217747319146157362846931033191115405436359059164369837886047545786784269972638543358070538110289573835904005155690269896801808285722482531209154145575023812797780986255049727529641861584796117205935895183538098160170745098973684976756630890804100890067664824642639589092432914498898600120332970813163043157838253047471232626526780521581486639131459983425407847086254674037377756949248113825642432087864942531245034742209381745688731273006510527134001938247811070510995132023678846496996678177796483605667198767129200358475944856250446358744125712853772318008884032107371472320376580231615493704518092986087002921898258237508069533598512214713469385221963034901057530843804769093689283128565687431
Enc = 430499849081337663832081920302659618751659875427051018870197208017664953238487473697352845290325544558064899797877046545208347216414865382064980917304875592602446404287228402964383579305270095250734057603750747065366921659580644160152473380518670632941045017536731197059772871900986149981535038527031360103525319691941766128222314209311120251691166369664393920271849371046788352052155707160091755619094924755859793996988286006616247538158486359146970822170451500192576559845128261837579098250545624760450362977788583508716897058975264111924665106391329783978595651208527595611582119230360624111244548921513723226191731589212301229764695429479496204856592478811960728805890970175244763355423026191823803360395528834304960509188373885372696883907597362083966102533343273087325044123519704598407719702988894224878081932701140954856595078098758618752549476793719456758592831569352050676494359558243641089383213200444196033632442145314272495788695894145969680805976395707219351221345884444293803025691868351359591770938097219639258118437571302668758237868578993441887711408196331006385922293764488028486104415885810234337945236111227561847482107834722196762384666506658799478200494160789233470589732679953979834202530567057239680670006988
print(long_to_bytes(pow(enc,int(alpha.norm()),N)))

フラグ

IERAE{e70019b319bbac72653c3b3a357be327a115921419670277eaa88760268c3f9752d7bcd16ca8fb304feefe4db851dd962901381891cdd7b7147f03a07611d61c}

4. writeup（Crypto以外）

4.1 [misc][warmup] OMG（123pts, 191solved）

設問

Oh my God!!!My browser history has been hijacked!

オーマイガー！！！ブラウザの履歴が乗っ取られてしまった！

検討

　ソースを見ると エンコードされているっぽい文字列がありましたが、とりあえずまずは愚直に戻るボタンを33回押してみることにしました。

解法

　サイトにアクセスし、戻るボタンを33回押してフラグをゲットしました。

フラグ

IERAE{Tr3ndy_4ds.LOL}

4.2 [rev][warmup] Assignment（140pts, 127solved）

設問

Assignment is the root of everything in procedural programs.

　解析対象ファイル「chal」が提供されます。

検討

　とりあえず、IDA free版で開いてみて方針を決めることにしました。

解法

　IDA free版で開き疑似コードを作成したところ、モロにフラグが出てきてしまいました。マジか。

フラグ

IERAE{s0me_r4nd0m_str1ng_5a9354c}

4.3 [rev][easy][was_warmup] Luz Da Lua（159pts, 86solved）

設問

The luac file is compiled and tested on Lua 5.4.7

　解析対象ファイル「lua LuzDaLua.luac」が提供されます。

検討

　オンラインで Lua の decompiler 的なものがないか捜すことにしました。自力で頑張るのは勉強にがなりますが、どうしても時間コストがかかります。*17

　すぐに良さげなものが見つかったので、そこで可読化を試みることにしました。

luadec.metaworm.site

解法

　可読化の結果は以下の通りでした。 「reversed.txt」

https://luadec.metaworm.site/

-- filename: @/mnt/LuzDaLua.lua
-- version: lua54
-- line: [0, 0] id: 0
io.write("Input > ")
input = io.read("*l")
if string.len(input) ~= 28 then
  goto label_301
elseif string.byte(input, 1) ~ 232 ~= 161 then
  goto label_301
elseif string.byte(input, 2) ~ 110 ~= 43 then
  goto label_301
elseif string.byte(input, 3) ~ 178 ~= 224 then
  goto label_301
elseif string.byte(input, 4) ~ 172 ~= 237 then
  goto label_301
elseif string.byte(input, 5) ~ 212 ~= 145 then
  goto label_301
elseif string.byte(input, 6) ~ 25 ~= 98 then
  goto label_301
elseif string.byte(input, 7) ~ 53 ~= 121 then
  goto label_301
elseif string.byte(input, 8) ~ 63 ~= 74 then
  goto label_301
elseif string.byte(input, 9) ~ 135 ~= 230 then
  goto label_301
elseif string.byte(input, 10) ~ 92 ~= 3 then
  goto label_301
elseif string.byte(input, 11) ~ 38 ~= 23 then
  goto label_301
elseif string.byte(input, 12) ~ 250 ~= 137 then
  goto label_301
elseif string.byte(input, 13) ~ 216 ~= 135 then
  goto label_301
elseif string.byte(input, 14) ~ 5 ~= 86 then
  goto label_301
elseif string.byte(input, 15) ~ 69 ~= 117 then
  goto label_301
elseif string.byte(input, 16) ~ 226 ~= 189 then
  goto label_301
elseif string.byte(input, 17) ~ 137 ~= 186 then
  goto label_301
elseif string.byte(input, 18) ~ 148 ~= 240 then
  goto label_301
elseif string.byte(input, 19) ~ 64 ~= 53 then
  goto label_301
elseif string.byte(input, 20) ~ 130 ~= 225 then
  goto label_301
elseif string.byte(input, 21) ~ 241 ~= 197 then
  goto label_301
elseif string.byte(input, 22) ~ 151 ~= 227 then
  goto label_301
elseif string.byte(input, 23) ~ 203 ~= 250 then
  goto label_301
elseif string.byte(input, 24) ~ 179 ~= 220 then
  goto label_301
elseif string.byte(input, 25) ~ 216 ~= 182 then
  goto label_301
elseif string.byte(input, 26) ~ 101 ~= 4 then
  goto label_301
elseif string.byte(input, 27) ~ 238 ~= 130 then
  goto label_301
elseif string.byte(input, 28) ~ 61 ~= 64 then
  goto label_301
else
  print("Correct")
end
-- warn: not visited block [59]
-- block#59:
-- _ENV.print("Wrong")

　これをもとに python でソルバを作りました。

「solve.py」

flag = ""
flag += chr(232 ^ 161)
flag += chr(110 ^ 43)
flag += chr(178 ^ 224)
flag += chr(172 ^ 237)
flag += chr(212 ^ 145)
flag += chr(25 ^ 98)
flag += chr(53 ^ 121)
flag += chr(63 ^ 74)
flag += chr(135 ^ 230)
flag += chr(92 ^ 3)
flag += chr(38 ^ 23)
flag += chr(250 ^ 137)
flag += chr(216 ^ 135)
flag += chr(5 ^ 86)
flag += chr(69 ^ 117)
flag += chr(226 ^ 189)
flag += chr(137 ^ 186)
flag += chr(148 ^ 240)
flag += chr(64 ^ 53)
flag += chr(130 ^ 225)
flag += chr(241 ^ 197)
flag += chr(151 ^ 227)
flag += chr(203 ^ 250)
flag += chr(179 ^ 220)
flag += chr(216 ^ 182)
flag += chr(101 ^ 4)
flag += chr(238 ^ 130)
flag += chr(61 ^ 64)
print(flag)

フラグ

IERAE{Lua_1s_S0_3duc4t1onal}

5. 解けなかった問題（upsolved）

[crypto][medium] cluster（335pts, 9solved）

設問

I know there is a cluster of RSA lovers.

I know there is a cluster of unknown RSA challenges.

※2024/9/26 問題のソースを載せ忘れていたので追加。

「chall.py」

from secret import p, q, r, flag
from Crypto.Util.number import isPrime, bytes_to_long

N = p * q * r

assert isPrime(p) and p.bit_length() < 1024
assert isPrime(q) and q.bit_length() < 1024
assert isPrime(r) and r.bit_length() < 1024
assert p ** 2 + q ** 2 + r ** 2 + (p * q + q * r + r * p) == 6 * N



m = bytes_to_long(flag)
e = 65537
c = pow(m, e, N)

print(f'{c = }')

「output.txt」

c = 803065078252547393812982498895211019353977926969143481455672761264443519482121067346644328911375984166893647468186232810673857290127114177258405196432172412966170401425497369188710097376895361641046391686887615687734454887428130745946475159776034046370464137762008371294039825175819408224450178007611894599399705434991448459196552982074660952318580952594830076838718297573226980847848142642550316589863549823042663312178673956251841439218528410295177672591802052069297783

検討

　p,q,rの関係式は対称式で、素数性を無視すれば (p,q,r) = (1,1,1) は解の一つとなっています。

　競技中はここで思考停止してしまったのですが、X で @Yu_212_MC さん

clusterは小さい値で実験してOEISに投げるとそれっぽい数列が出てきて、もうちょっと調べると、(1,1,1)から初めて(p,q,r)->(p,r,?),(q,r,?)をたどっていくことですべての解を列挙できることがわかるhttps://t.co/mYoQs42li3https://t.co/410oRYWczU

— Yu (@Yu_212_MC) 2024年9月22日

が述べているような「既知の解(p,q,r)に対し、(p,r,x)や(q,r,y)を考え "解を先に膨らませていく"」ようなことを考察し思いつくべきでした。重解の問題や網羅性永続性その他数学的正しさの検証はさておき、"Math" を名乗る者として先進的態度で試行しながら進めていくべきであったと反省するしかありません。

　このような手法がとれる仮定のもと、(p,q,r) がすべて素数であるようなものが「現実的な時間内で十分少なく」列挙できれば、それら候補に対して総当たり試行し c を「まともに復号できた」ものをフラグと考えることが可能です。

解法

　先述した内容をプログラムに起こしてみます。無限に続く可能性があるのですが、p,q,r はどれも1024bit以下とあるのでそこで頭打ちにします。

　この手法の正当性ついては、（自分の理解が追い付いていないので）本問をもう少し一般化した形にして改めて*18述べたいと思います。

「solve.sage」

from Crypto.Util.number import *
import sys
import itertools
sys.setrecursionlimit(100000)

e = 65537
c = 803065078252547393812982498895211019353977926969143481455672761264443519482121067346644328911375984166893647468186232810673857290127114177258405196432172412966170401425497369188710097376895361641046391686887615687734454887428130745946475159776034046370464137762008371294039825175819408224450178007611894599399705434991448459196552982074660952318580952594830076838718297573226980847848142642550316589863549823042663312178673956251841439218528410295177672591802052069297783

PR.<X,Y,Z> = PolynomialRing(ZZ)

def check(x,y,z):
  f = X^2+Y^2+Z^2+X*Y+Y*Z+Z*X-6*X*Y*Z
  if f(X=x,Y=y,Z=z) == 0:
    return True
  return False

cands = []

#solve X^2 + (x+y-6*x*y)*X + x^2+xy+y^2
def next(x,y):
  ans = []
  b = x+y-6*x*y
  c = x^2+x*y+y^2
  D = b**2 - 4*c
  if D < 0:
    return ans
  sqrt_d = int(sqrt(D))
  if sqrt_d**2 == D:
    z = (-b + sqrt_d)//2
    if z > y and check(x,y,z):
      ans.append(z)
    z = (-b - sqrt_d)//2
    if z > y and check(x,y,z):
      ans.append(z)
  return ans

def solve(x,y):
  w = [x, y]
  w.sort()
  if w not in used:
    used.append(w)
    if x < 2**1024 and y < 2**1024:
      z_s = next(x,y)
      if z_s != []:
        for z in z_s:
          if isPrime(x) and isPrime(y) and isPrime(z) and x*y*z > c:
            cand=[x,y,z]
            cand.sort()
            if not cand in cands:
              cands.append(cand)
              print(f"added {cand}")
          solve(x,z)
          solve(y,z)

used = []
solve(1,1)

for cand in cands:
  p,q,r = cand
  phi = (p-1)*(q-1)*(r-1)
  if phi % e == 0:
    print("bad case:{p},{q},{r}")
    badcase.append((p,q,r))
    continue
  d = pow(e, -1, phi)
  m = long_to_bytes(int(pow(c,d,n)))
  if b"CTF{" in m:
    print(m)
    break

※b"IERAE{"を含むものを探索したがヒットせず。Discordを確認したところ、出てくるフラグはにフォーマットと異なる旨ちゃんとアナウンスされていました。

フラグ

CTF{9fceac6e79e1e23d718610c4de7b4844}

6. 振り返り

　このあたりで、今回の「振り返り」をしてみましょう。

• 嬉しい😄😄😄：hard 問やelliptic-shihoさん作の楕円曲線問が解けた。あと、とりあえず順位的には上位10%に入れた。
• 悔しい😣😣😣：crypto問を3問残した & warmup 全完できなかった。
• 反省点😞😞😞：Diophantine equation は得意分野だったはずなのに、いつの間にか後れを取っている。

　反省をしたところで行動に移さないと意味がないのですが・・・善処します😎。 　

7. おわりに

　手応えのある問題が多かっただけでなく、ビギナー・フレンドリーな解きやすいな問題も用意されていて、経験の多寡によらず多くの参加者が楽しめる良い大会だったと思います。

　来年の開催*19もぜひよろしくお願いします！

*1:ソロチームなのでポジションは総帥のみです。

*2:スクショを取った時点では1892ptsだったのですが、writeup執筆時には1891ptsとなっていました。不思議。

*3:IERAE CTFの特徴として、2023年の過去問が「Homework」として1ptで出題されていましたが、とても面白い試みだと思いました。

*4:実際、この日の自殺者が多いという話があります。大人になると「宿題くらいで」と思ってしまうのですが、「真面目な子ども」は思い詰めてしまうものです。そのことはこの先、年を重ねても忘れずにいたいです。

*5:徳が低いせいです（涙）。

*6:粘り強くという意味で「納豆」も候補だったのですが、未調達のため今回は見送りました。

*7:「鳥の詩」はオリジナルも素晴らしいのですが、森口ver.にはまた別な味わいがあります。

*8:後刻 Discord で回避策を確認。

*9:「届かない場所がまだ遠くにある　願いだけを秘めて（スコアサーバを）見つめてる」状態。

*10:悔しくて指を離しました。

*11:ソロチームでなければ、分担するという手があるのですが。しかしこれは「ソリストの運命」なので甘んじて受け入れました。

*12:日頃の行いが悪いと稀にあります。

*13:QがPのスカラー倍のとき、Weil-pairingは1となります。逆は一般には成り立ちません。

*14:ちなみに、本問ではありませんが IERAE CTF で作問をしています。

*15:実二次体の単数をべき乗計算したことがある方だと、すぐこの方法を思いつけるのかもしれません。

*16:このケースでは alpha のノルムは -1 でしたが、ノルム 1 のものを選んだ場合は勿論そのままlong_to_bytes してもOKです。

*17:場面によって他力を頼るという選択ができるというのも、有用な能力の一つではないかと思っています。

*18:他の問題のupsolveと合わせて実施予定です。

*19:もちろん、半年後やそれよりも短くてもよいです！

AplacaHack Round3(crypto) Writeup

※2024/9/16 加筆＆誤字修正

1. はじめに

2024/09/15 12:00-18:00 AlpacaHack Round3 (crypto) に参加しました。

AlpacaHack では現在のところ、隔週で特定分野の 6 時間競技が開催されており、競技中解けなかった場合でも終了後は常設コンテンツとして upsolve できます*1。

このところ不調気味であったにもかかわらず、最初はそこそこ快調*2に走っていたのですが、4問目で完敗。結果的には、3 完 26 位でした。

2. Writeup

2-1. qrime（104pts, 91solves）

設問

not crime and prime

以下の2ファイルが提供されます。

「chall.py」

import os
from Crypto.Util.number import bytes_to_long, getRandomNBitInteger, isPrime

def nextPrime(n):
    while not isPrime(n := n + 1):
        continue
    return n

def gen():
    while True:
        q = getRandomNBitInteger(256)
        r = getRandomNBitInteger(256)
        p = q * nextPrime(r) + nextPrime(q) * r
        if isPrime(p) and isPrime(q):
            return p, q, r

flag = os.environ.get("FLAG", "fakeflag").encode()
m = bytes_to_long(flag)

p, q, r = gen()
n = p * q

phi = (p - 1) * (q - 1)
e = 0x10001
d = pow(e, -1, phi)
c = pow(m, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c=}")
print(f"{r=}")

「chall.txt」

n=200697881793620389197751143658858424075492240536004468937396825699483210280999214674828938407830171522000573896259413231953182108686782019862906633259090814783111593304404356927145683840948437835426703183742322171552269964159917779
e=65537
c=77163248552037496974551155836778067107086838375316358094323022740486805320709021643760063197513767812819672431278113945221579920669369599456818771428377647053211504958874209832487794913919451387978942636428157218259130156026601708
r=30736331670163278077316573297195977299089049174626053101058657011068283335270

検討

気になる点としては、q が256bitと比較的小さめであることと、p の生成に使われた r という素数が leak される点です。

一般に、x と nextprime(x) との差はそう大きくない数*3と考えられるので、差分を総当たりします。具体的には、p を構成する式に q を乗じると n になることから、q を未知数とする 2 次方程式を作ります。

解法

q として適切な値が拾えたところでストップするのですが、煩雑なコードになるのを避けるため itertools を使い、適切な q が取れたところで break するようにしました*4。

))。

2 次方程式を解く場合、解の公式を使うのが堅実だと思いますが、試しに SageMath の factor を使ったらそのまま通ってしまいました。

「solve.sage」

from Crypto.Util.number import *
import itertools

n=200697881793620389197751143658858424075492240536004468937396825699483210280999214674828938407830171522000573896259413231953182108686782019862906633259090814783111593304404356927145683840948437835426703183742322171552269964159917779
e=65537
c=77163248552037496974551155836778067107086838375316358094323022740486805320709021643760063197513767812819672431278113945221579920669369599456818771428377647053211504958874209832487794913919451387978942636428157218259130156026601708
r=30736331670163278077316573297195977299089049174626053101058657011068283335270

PR.<x> = PolynomialRing(ZZ)

for diffs in itertools.product(range(400),repeat=2):
  a,b = diffs
  f = x*(x*(r+a) + (x+b)*r) - n
  g = factor(f)
  if len(g) > 1:
    q = -g[0][0].coefficients()[0]
    p = n // q
    if p*q == n:
      break

d = pow(e,-1,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)).decode())

※常設化されるのでフラグは記載しません。以下同じ。

2-2. Rainbow Sweet Alchemist（146pts, 42solves）

設問

I spent an hour thinking of a problem name but got nothing🌈🍰🧪

以下の2ファイルが提供されます。 「chall.py」

import os
import random
from math import prod
from Crypto.Util.number import isPrime, bytes_to_long

r = random.Random(0)
def deterministicGetPrime():
  while True:
    if isPrime(p := r.getrandbits(64)):
      return p

# This is not likely to fail
assert deterministicGetPrime() == 2710959347947821323, "Your Python's random module is not compatible with this challenge."

def getPrime(bit):
  factors = [deterministicGetPrime() for _ in range(bit // 64)]
  while True:
    p = 2 * prod(factors) + 1
    if isPrime(p):
      return p
    factors.remove(random.choice(factors))
    factors.append(deterministicGetPrime())

flag = os.environ.get("FLAG", "fakeflag").encode()
m = bytes_to_long(flag)

p, q = getPrime(1024), getPrime(1024)
n = p * q
e = 0x10001
c = pow(m, e, n)

print(f"{n=}")
print(f"{e=}")
print(f"{c=}")

「chall.txt」

n=2350478429681099659482802009772446082018100644248516135321613920512468478639125995627622723613436514363575959981129347545346377683616601997652559989194209421585293503204692287227768734043407645110784759572198774750930099526115866644410725881688186477790001107094553659510391748347376557636648685171853839010603373478663706118665850493342775539671166315233110564897483927720435690486237018231160348429442602322737086330061842505643074752650924036094256703773247700173034557490511259257339056944624783261440335003074769966389878838392473674878449536592166047002406250295311924149998650337286245273761909
e=65537
c=945455686374900611982512983855180418093086799652768743864445887891673833536194784436479986018226808021869459762652060495495939514186099959619150594580806928854502608487090614914226527710432592362185466014910082946747720345943963459584430804168801787831721882743415735573097846726969566369857274720210999142004037914646773788750511310948953348263288281876918925575402242949315439533982980005949680451780931608479641161670505447003036276496409290185385863265908516453044673078999800497412772426465138742141279302235558029258772175141248590241406152365769987248447302410223052788101550323890531305166459

検討

p, q はいずれも 264-smooth ですが、264 までの素数を列挙している時間はありません。

いわゆる p-1 法は、p-1 が B-smooth （B は現実的に計算処理が終わる程度の小さな数）である場合の手法として認識されていますが、本質は p-1 の素因数が現実的な時間で列挙可能であるという点なので、deterministicGetPrimeから順次呼んで当ててみれば現実的な時間内に処理がおわることが期待できます*5。

解法

「solve.py」

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

n=2350478429681099659482802009772446082018100644248516135321613920512468478639125995627622723613436514363575959981129347545346377683616601997652559989194209421585293503204692287227768734043407645110784759572198774750930099526115866644410725881688186477790001107094553659510391748347376557636648685171853839010603373478663706118665850493342775539671166315233110564897483927720435690486237018231160348429442602322737086330061842505643074752650924036094256703773247700173034557490511259257339056944624783261440335003074769966389878838392473674878449536592166047002406250295311924149998650337286245273761909
e=65537
c=945455686374900611982512983855180418093086799652768743864445887891673833536194784436479986018226808021869459762652060495495939514186099959619150594580806928854502608487090614914226527710432592362185466014910082946747720345943963459584430804168801787831721882743415735573097846726969566369857274720210999142004037914646773788750511310948953348263288281876918925575402242949315439533982980005949680451780931608479641161670505447003036276496409290185385863265908516453044673078999800497412772426465138742141279302235558029258772175141248590241406152365769987248447302410223052788101550323890531305166459

r = random.Random(0)
def deterministicGetPrime():
  while True:
    if isPrime(p := r.getrandbits(64)):
      return p

def _p_minus_1_method(n, a):
  while(True):
    prime = deterministicGetPrime()
    l = math.floor(math.log(n) / math.log(prime))
    a = pow(a, prime**l, n)
    d = math.gcd(a - 1, n)
    if 1 < d and d < n:
      return d

#ある程度時間が経って終わらなかったら強制終了してaを挿げ替える
p = _p_minus_1_method(n, 2)

q = n // p
d = pow(e, -1, (p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)).decode())

「ポラードの p-1 法」の本質を突いた良問だと思います。

2-3. A Dance of Add and Mul（170pts, 30solves）

設問

So just dance, dance, dance...

以下の2ファイルが提供されます。 「chall.py」

import os
import random
from Crypto.Util.number import bytes_to_long

flag = os.environ.get("FLAG", "fakeflag").encode()
bit_length = len(flag) * 8

# BLS12-381 curve
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))

G1, G2 = E.gens()
o1, o2 = G1.order(), G2.order()

xs = [random.randrange(0, o1) for _ in range(bit_length + 1)]
m = bytes_to_long(flag)

cs = []
for c, (x1, x2) in zip(bin(m)[2:].zfill(bit_length), zip(xs[:-1], xs[1:])):
  if c == "1":
    x1, x2 = x2, x1
  cs.append(x1 * G1 + x2 * G2)

print([P.xy() for P in cs])

「chall.txt」

[(1743174964898476231884492702526509409941910166755636264114719001134136311544164859608107001037008472785879054193988, 282507966368478109897913420013335901793877733656209659063912815751605947276771371685158803883038457671423792959840), (2604476425813600106045658392319587289251667405363075850511854900496916483360403086711960714647065926704529705816533, 1555857183284830438138185604088744760453460623795300707325224098164127005282478344794747935181654983396533387315430), (2316226643069567923605535237355685445875266547343403579490962756133173171433231067567591483595552100655458309566375, 2981428021753314510640923396169008185208755941539344157873670976071986622411215869689136199806661813962964122496611), (570291358935290536461621191412821158258680894876108780059636091310268926107670650894039439356071505254096233248479, 3881161413135409717601570271820950701084246386487308541497516454864205318916175942055323780387614517073043110384481), (3393991437700130919971682453197245082132251403135464589665716819160872349344288713855432761127777860855879468086926, 197115896770739332711898251459357715211735867935233481258486508852860774065543786601936171487329140359263904400350), (3903717415321585090050779276501605989003552460714494008769947620936330216481027485956935886164260976671037851254062, 2143957550792197190205052518873628958027488004690598022229297123812921151049954588061293964272099703220362264408422), (3155826236324608386073976989196518785073154281603042305195847816013535010158091322306144696469066967429132422929970, 1167283444539635080801595792809376297016756971780065392701544702066642369690357578759951147463248401751077749745850), (2373072752516833130514525114791856650043671866922901852071361743705870219847590283892925536987350441426150946837794, 3687243739237830810120912151997208733295811434624806106604541385169799516786062320604346544361858358973899334983602), (3677019777144161434386517418220606765190961918427826803412978558839925737890553573528568071504020109237111435434944, 3208204766308208999262695309378666842688419375297666733451273333654092349433781127601555485269100008136400232393043), (2338732364904510265382569094992609438359596184712951920253913737484376036254037401096815921130975866642664888637040, 1418863982859410473188417088065816977135888933971128170083567546329689005524281018568617308995002426600440734298587), (866445308037380610321719565934333556604345040761914372598447855159856486185883402209283249065749012915569843829022, 377712780643316061254987698843499116301164824971209207766064262625734671473946792176643588537200320564805975931800), (3224703326652723083323786488771255769727590096885540509630174364411484527761708021730558868998034346418670809673731, 1248045624805684627589164527340015464632612570045616783824650784617621741379667525500078290139524450856708641455329), (3092721273367908674435112776226787892838633055207323799767351566838352354607808168705551879176165600612554297049345, 2033741917676418752133253349401638484960495897601767290934236381178958680782863092355969907470195219406891216069324), (238345278643849133410795626296280878033717102196044376554086147973994521283274059924277421364530805345651805533413, 3545337167845706315764635864200687227399051719375681045301861126554171963539059473865304640809152201515615297825057), (2533410177430894928425916074902597241468177637191230606086254685584295568050221696629217515399237382465503058875508, 559857545718544627334416122554537985754457586789834344284855641708701323052701838016142405799716437297507854013517), (3918611372080264161965074253138359014479895566531446624617853228139496619207464861430938882208100002356039785782941, 1380063584996002882386293722224718970379940899130108919580918011297542268081375117145106033341885781365390853514842), (561694655291204404329300564527644358215741242156773098667597830191500874838538527753654710940429665843339956466790, 2167296469095477281197595959369369433440980014780990084964453932386247351503245346131300437256829185170107882116135), (1137975179613584348595121655647179511893096585131851688569522424473834147449472004970047036767728093116303006575009, 2291043016813094898947188515612475714529964540310451708267825174859174308964383491304789931050471002856565609761873), (3642979912316198073300004984327495725206879047379685730043201932481721546907558048592176445260699921430404648706482, 3366402292879089819640920497537575618422097060135345019113162092312698201305209261409680910018290840864588462791304), (2938719830590373770819508211750604773463683119383632758822316536113919355221329623031187189527122753389729010777979, 3163724306747370493931386973297687161789923727059029100814804013731254878501603429883988579726698756230083870415466), (730723453892839803824925319882842872691327695619003090010894485003543782249324101178827221435294539291224749239394, 3703430381418502342035734627829233670421783388508556953784365813674715384363129596615791911568715682158566567390132), (1151754316191221129383662031900821767072996354256400667126452278933741712907705560806973722064937875044123175984385, 2157748838436400553071272643953991105614982657588518724499480704310606539057538058273051467684475732214728264013344), (154271205642055889855207065726531724855279038507267548815863396345605893458340991172401593492194566414801648396939, 3401702097539235936805037274515822324387631393606719658945826399448700044027616136221240770934912222680073366326298), (945558960491952483439577368506521063211304855039729625446968291313872952766227452612172312609238017344876080429953, 2202898569661531423814597008482220802004967422843405778009297931372300778048691479725775182546333730532396185863702), (1338905209806747642144294260435817735072027077744614169244899221529001066364721373406246879679547533053232024628140, 3926007114897143746120209555937341641154567682621855382863248833117412734252941420515449124404708474814164160184506), (3217186734296508773352682762139686143961473163452814422038919438069415504106917664554804802440864867867000022454876, 609525049715089215576092142878351711679546003826712111131229628346856195462547503928839918174632287605033350006842), (1200189058730635654926661921705598716016730657003653587941093596791023815791516717661705902386995468599251122495400, 1434406040441416623472752461640086749124750735097702039543968523969655307846182092401596013056341706265120117336701), (2076862912930134237019162902658706409555817924197056632400525510811191420183813663435566440648326271218319033436293, 2771622557463217576747134589004557390244576553785795743405698645232729266332257770586228250132353311071336946722049), (2718957640578376436128228161369864023316241058654785003025477207541776891537252725308770832959322295786549771810593, 3919293911573464410618070047304934458414653603983418395788866354866643280430146769832691856448644530282220334087739), (825097584715571379491566295343643999925571672107924311157717894183065449714417005393189586561628417733967176102111, 3842415319951377284960098134366948343450809633081803945234328070443579228830440472078497850372902375187657310832697), (1878459351789424491155619956127871300509033860155313382183707549343918618383271320986958019904575673263860553968846, 1843063941800442255688437442825379605979272796305493360896445789046526334002925976720304836792897791890303796099026), (1385407762877042230403917879796293645850765166849346317380136838213659993679653777548695120314972287555857649398438, 2738405289832873176112572784551115918651954279331301203676435665838117929597053369181210053756597352097887411217365), (850137573743327965960337639900572615853955851041195615544996862063837167208879362778226437704581973931652007577566, 3443628108918467375733105601178257771047136347917713972150969283661474927543672260789670084149713591495510236820349), (2036387613845323378867919530347728930858106428579891823080364032261346884723220763633988792115482140407986043983114, 2636221878930104166296224251595823011021497309340295437196008077978401778444976212412496002085665886715743537405665), (3186054595259308165771563637975559268526573657759860955768092682281569022501303440275704388074605576431892681018792, 27280959976434548785368480052847977507640696922352208444728261145764367481997269297811229550884295997840865777355), (3650015116251940267917606599026361806110511105230406744137560588981095887202763178661784936871793778765551544484880, 1886067345525943549296455551056307544318878355881514438385609903664739214513568895071807760303350642522017228601873), (1740375129145105862312906866155656350079230769046683192937656871286407880818550771306421774637754302131084122910130, 2305105144635879373390361159918727305517628027941283012945602288791776322815491879693726380331639936626697485708511), (3809743670014203504547578875482548995752508151125220446303067068500206782173428247832675416287234120166889788907165, 3992898534122331469889238165126534275993347148527216424736410774369911365773416075754587934729253127103797430681824), (3276180655291559947349893782576681601171895346747002874364312529231028819588601924209243299155570310306799703345986, 2302815299648759062347545479881676338634634642279823357730782078455384189874332666310220597314468860240105274788631), (2591931536757146389811780700442907042212815479127760473386376543036429822695736195041408582477611861682037276979053, 387641249689125025764507164841658115136816589193648867288922344894357899159497110465255072353621934229892598855734), (913896177442848830826225293891797165845805595025186899741307598009002482110234682105570707815547827499632983586346, 3370324153591413452136375270698103128903473819685032024663874098815212194282718484312445988401586243964551896780805), (1558798620967779187508334028595220156231798185647149531046633383206611454191054742756308403141920849719062069885859, 1979135206662048942063579353658835651947958731902747440055206108592288748330929395356946884574509610543961900997015), (2536213617749816546164176086798548652009684535257233907683021696497883892160265075816637711783952278896548223781634, 1423332472832856150959000339885629273253028866715176585969761961783853398863927286479045864682090077634370933330344), (200350259724703141044507099742305657686299861371519686850505076424734222652586601498823667389271441895041790614223, 2596576515726482464314914799389357533010580343310288540387605092912810778464226512672696811949791036061251134920874), (3414785870020319044874831341675084149265665932144687078070807057011424628862129614342189707649776649382249875306880, 3078201391799646719606057716642312213957043371920098927080032542081033007528098105406058905997467369985054411341924), (1303029267947658306902578759439173537465146940068357509643612447736875224270055860574374651380892958838968541452478, 3018979257678715087161924100643872228380975900283124691201973759294402498266498272784316964148098421066689503641963), (1016867131835320084136779619205050864995799142541025273593855107386693826242137351146303887272446876472627874226485, 3797012649593436233953537292072475966806856028714097191892161449096269478213477985590591755330008470840101553733309), (3527842275038721000672637959688237800303688888648287446382583259001918454878491004597434849496627166239603592388531, 3422042828395917230643953692926265894113894593808551725765023892401648906209198620311798531791280951061970159672972), (3911488242604430964555625723697123624748324529696498418399342764085940754674800811162036750567232204769658509290037, 665162270921761910905724875702119391426149204451636034810934789751938932503110960969623334459785146583765609927110), (1460209240429048093647346647745801455445777501334507266597063708269819722706916700325467234848004113586315454431185, 2172396235679040300729583412375878037602521646893284863121509703263722013869943898375524016615672389353243581758422), (3956957306098977921818425917075313625243527646332112546981127219817832915904064984748171358268534362987947059057659, 2504187177482161631231341835823762329470639414743566436595885034994297498820216302889636595309488818202744811549916), (3719936787655343959707263002551823904626951867550892952682418268163308238732421549725507584372057704277812801960226, 2558356074158187453458749799241688829776266949443838140691682952939728055117267316926275697061496950402023860080119), (3662483949159992577100493759405926389118659337737440107435537896516440640755762254044319961356543575013099639983411, 3911909075742683547475623898673589691808558905569745044567950814585239909171828481869094401166887309213644284233681), (2881122265493374594109851575602045297948996541732104384234367002529684744355182191855247616034999054519550806707182, 3675710045640682700064672271422161711712131151424103454923891343313635501831239519626016634059222555549288686873267), (2930764973228541562905194945610369049562622542340955368358802109690076815088104475978982966925942353093680976935042, 388807248282663198131099265902481665763424142691466620797672742136306650851881824711239721232680526808159717453060), (1176006007023883208491190611182648626187078876723630738759603136521011002778800229501169810758290846173111080425599, 1918826724587296481334110267085588549808798483124976466692304846969094434682567778125331419372149284436004907430351), (1353558447774043607343663677629855221166053990929040420283659035536992602178367543174840274788429079204942829452947, 3988537876492759769864849629347193548404871309125194481226891159944780821442578047680829391773575398610661847516535), (2003727338880610817750500101645409189774081509332010114131469775573584709411155143488824665456219942161704653063601, 3965904518413226123462348534557739079101591383319657587888990405392449283791860685308921625528918448102207775758114), (1771744624749948561237547791980222915239384882484931571471388567985171567299380948254690326120946549646025128028137, 2956478725191814250144256893532389503923675547772322719594226600657169995385941482050356051031145751614554971687619), (2438342480321233229126941497993672537660084555841844109291224141894498110846483457011328094034067874043386229918118, 50839361672939290549843823916806635980242913738648339385596576962156959013054155827699189485207912012941377303119), (2497746546957773249873412568730891763133076298606237190416874498576910565401848201305697464279605312125088158353601, 3337664433920182611126811699941452176617530837143236567704476104329179451207834083612263441690765134921003269330396), (401563612144328911971154454988545648461956858868609210160753738607137889744790783594766508755031536616977690821585, 170448328121092740960921347952030719159771543702457470319639215941627331432791612391837042686597467640214390416499), (794415920599090784340064281677589748050170354321863123523038084545603488663273396548463929038233960999431571777711, 1844391040844006926840827273245620714058866350279789760378449183706754382033739549959355168291669745415046433672601), (1650933162020943303225095725392532860629368008348117031386380044629523385285751338823249938857191552007975582878749, 3885747029663341535640197907907694286583383498617909303735961181162786184596342970212927612940622966840942043795491), (619052506540122218158572365831419360404156996086739687080656733711821345695573156062186836136311942595576005237557, 2047888032845898489866564887114582378615235756870026447050403629047208875931449853464515394745408559750147328633455), (1379812108596149939142956689141193188738261810529941774311477755613567611452886983861188946779731880183628391539487, 2119675911476551496733465878627062945889349117019584060568048094102353704282855361505216925774725035652610811090074), (723374512695652686418463502338309300616996285026193105534625273679047933468386109287501438120175088565154698630515, 477888160222361553191635400498273811716669229272616553331139729532382733396107443008910702858051758673928226204240), (3563239089381627761195654319135194327011087587991349979642192772899531779038783868829593174748814715624467954793394, 980660381172162298624737390295636871466641878969677198104123629124313893286162186185479042069130852741969905266571), (3989369344544551450964300523597071598706946958925081206092101714864522624139344046779839485705960763474146585320839, 1836650806892262099336342627406009793651775835558557722354135106788556584443708367113413956523253984486123345335354), (875470011531297922439988447731270173443598624079492226772944204172706043037614291152649768641356425338251757415999, 3286455264880329325061878551649805661675674108728780388553924841040654949991845572075593344370173361541327188723361), (1924430144686857445109711676929794476884539252488231087361455972137600357205088538123305960994949687549027345072129, 530829322437476656462612331804546452763425557036221305473360394719059525619931596397108561655025766337049023970887), (230500009485283937143703909439567096954799060172900059805429785790721122576998385895528204662076541144845998150210, 2559278382322289375039273770088812610923822220679560015675558980977689012577684415058175551575174995646580497319537), (2740994433865954246067607986465408446553672444765785557268778237329849937413056933090745778865771497444830867222614, 2613582707151001926819205644635422116654843257337653493919965051049927004049873535922901307198167764456385392764680), (2681947609615826594967563241943549568076707355148704802083621337937978243066137107872941449945536725668620804731430, 1137985515674432323877748300389752843455952218651669385745487748545343728293445363627195120206686642774929526690914), (3412623342772299648422101567356015749751212680827280435238160174484738409273915269503084355637783542808021535337117, 1769678819363757382029193593326778398769431928851671586166075461076260980862582148472959719573961587111539660802282), (3019818370868402416812720483695438383325290501190816351789074632955626439666364777484542294231294276133537429942401, 2725638012304499679778686658541589768859479302562910127909208235501190985083666277692767540682559784485122550015646), (262624578862408316768031524129870945861352330303597127438991783630335721267861477583005117508558891414899569719378, 778395429168394590888519678752632360165458094941403437887880205902617587613679136716995373444004703421471305287188), (2300029436533709037733681770369535729217164784967585053321072849678436785527185541268532034569620564264430394807165, 3409546554518502488163598197056640212975425740434708203250024687997981872492280908415440069070758278595536521056416), (3233059809564733827088416772614337628537615053189875009544125965604019033407575713708146742969062915317572723025722, 2575021784264560509650840912195183300795594257676876052494838609911976118060395851655626409505535337847860593500202), (3100492826588183197636977973521220018027150771528585020416141837863233292845966547476935324854565961713595686352589, 388687412042984893044994743311771057130471032946705666961926791621312336351883120807490335546967376497535907408546), (2083928309848593796705558419554559485029195587317898033739040714327002556571881465655321384410677749449533537139964, 2578275896486999091363743523158637185080560273280809875601958237580408065121211052909793502376916151471373990735890), (275594143827016789295549763726246176884922839026157241945825820835054140841820302589454554943788287048471241504848, 3804120365507168156030506438752457563355825172024777619029759942684142787825742147447105204287546942459320665069836), (919027468554054129528587228745322974813615497149959511878624507407645763776596936669084789792892395236317465258090, 1361866816968646855690303270973827168240405164507293575568932992888744493258843658289322430557026066670112756374520), (3895152074834929444524271060833832691844526642719842680022944599143400090600610733429835239718283225450038721901236, 2491425709121414733876366468947368318187233664060156384023480986757356682713824485468669671731188506431324316523811), (1774288796965603308517837540980289450014063498019151705131510747596570813006310497754487529578484767435295845883628, 1017412206680229202885657745099547560102534341669201335111385935135117619729418678360904775509347503019497123987875), (1120582585099367747045261777942398059277860346102012516703506786508700111094316192810177836229567932367365498377684, 3969906450208468672811467034819372908829088778333390151140118017527759868870244082896061059079917187322587919310138), (868716539800150430417691819083674970888282892395058493810295644001937487461305388506656802972501232002507580377684, 156500768235474650862609315592154510270285430977990885492994223146761459736232269778289741683190840806450671268066), (179613647510807106731221862975326713676387190295070967371071166081350453651060552039462702007934044543206735240673, 2000118142411917408682012303012490607719794506815037972801367230825639503363774564625355901582489342686162806367184), (3428490873417579859131715149846283671555863597448416027035335214911224955675641800797619558911311934510047632383638, 1606121171891640799134966572948847580566011911983545932056741292866466206392083021352087667320272286528429778533535), (1209610068030543417560293357778036997143235103883597613217038185452369099143295935782444133885962012399943131114441, 2978591660654365900072208780932686729458705558541278399020421594908475014026227835197914114767518362351494320961501), (2355910520524201801048140621742199179931067013849090592106629960613626301205000100315043496270170534901029774964388, 1089701821109531846859512113520534969954692453480167825159467026108391937055982805480926337985953617016475166282438), (954271683444088790733947648865075637768540494687948010722653322844240290768994723341967308463188695331395406465770, 1966991926076932806913710286212912080495915847067601315965150914263263921592305218406827209420265458249801079477488), (53632339423085372109120363945988116410361141024917531619734505592277617941901142301336536937172636441681835373341, 1062955979364891812811357890882959736170200947219808079603365929074486232497091390149919360419491737231326896912720), (1115384226617271973399700299548856382164000456949043562407050350631684150397821762817974095026930098063716915623714, 3564302243800330877775802075209914896120471295297288724237703532814115883577760313520606588693954182857513168855540), (1042310445437054944015598112179188627194783193344730931172200256071349889916536675343195998773463407437335809141275, 470978663316257690916751069143158093208493407751431401034418814911251427639961558457537290308329928996876580715557), (1007597105656653136415775107072721262413309288774661538772434146344641161138442780487357777943197077655150109122169, 938184631717936890712414677205685990221471770185965577864117544883445860041274046817801292696483786247065237507119), (759994558132361118853257613563868239695308426577691229562161655433518507374511305523700453895154633358474900686822, 3580123009162302476114882976682218433947164864563059846783716473455557054710023332009125242237172376001467549096298), (3755367128520380532514022781716281382200607863001994392740930663337329099767499354331311424682591741031304120101472, 1354542040330426084086390664834894076027739831976575143487843354889810291988700733385350559479720102742202520168066), (3663670297818370461437407175474650571731647900079479080169113208122437752945438751557991599861782462924154585635132, 567126843093111581792849192800862378142640062121600526378604941111769515061206354144440332731788058914235328650766), (58517079090988561245791177440443554024099191947739165294927594162673192346744429279493144158977841640093611115938, 918981973620084194073486992290735475702852987374316462098597080402725407863025884555330720012242444289688785266153), (1967251684044444890246939075163034982685478166617082843425527659217643632478028058001352033150613574296427202341997, 3193572181082582755261662320913754175388077817153997110282620657159449071813323690161882990603452573355398201561075), (140776035384547589684143759521013666926341840618575312012393878196112412946046630762820736341883592453213069457297, 136320404560684738068004075237864257686417496423037230032023020482921214337339066447588478489424144350909547559124), (2225849486849269000378457237608487510978071498192397009291411435051663644451398257591823867744460393597596204694559, 3020922987835343158956158848422148601185332221756325247797384591587531370187217237719869548441088495850022904590394), (3735652555426159150678377470976476138226513364030250315909343132729519558371076453381913393181165078798911663988659, 485150239293774162383698694386773623187743388684814451550178809238081704848747313184684565412371701582935934277031), (3215157215913726671364594409629884424615706560672825158965900952848973991682501669882733175992607869781215533273780, 3948681173935039514249172090793324429602433248996500134406927749930230603575039107708117014369858634281105589965501), (185216238384583469695173295941352660520655936979442175382113756158301072579267893336150405954376330223226141027180, 949837255206902409258490047345959945037488158673555977855765854174185899755775575138933051338907107258824726461560), (2368128363660862970208997014910614295926111224543308237126700388401200171324983799866375294933188097472981887855759, 1761707426166802434782007705762997427297596784753175309215466454168469489855962187228889791678348144309121422334318), (3343724902583706984214020698831054712670271276017943554162039518330207747573571794482722887128625067276506172259190, 3468726385716393273871767657802545487489261534320431519583671426398227961901861892938744026873366446741757447770868), (1838748297978859153778791704926089796806413832589822846586735951442143462859643532874527275415525793911516013850050, 3782318930993965825619771267570684950539939513850688672736384679399579497237411341494612517023822945490062861156183), (2059587403239677412790011370774159494940409925303977652666993045211065301556930871416832316915510350137596287235971, 3166903650309401666616759706776802618786522011704527627395416418446901716933659078186403233597340977621463761522541), (1350143007735382852912561914030312580248410458229759015389438986831873985419021038612639294184848398149737873707780, 3970910327412005429773803044889020719028460899874073899933973227428585818005580504880287457413952379716069895713545), (3563632992743530892394997009861261766053671897314090423302820021085811327799650742054596029684606592442045851651909, 2225778389486861394140963491436757024170334406513592236576764498580361308485532193783296524010845662138202729950861), (3221298578530988643345907640516517131159249341152897653195819504828380559863969507289468817978578659543980163839061, 2093258496872284986767893284073622826642906619919813345462765066265584412199837792686782364703231236615486488244382), (3214512994055559362616909795699051979759367308252297306810792547430584326245280299434694489629129725345559860413035, 1162185165305871565040794260106952897756843632335930510601771504136925928326495911082520267217506184430445481435677), (3070019167790369421619833269777200398014606674262864652946141503994988578545070976172366716217484929698841424394467, 3139349635374539198347869817485233251989657515909455579986381522124983922982175728182382557595448381348560839488755), (1133777478490142102541436788331903688646254896786540118834530068976158250658045287149571436218595563198857068286235, 3248190040772092774424940746623214145373119521657226906996973337396339881553539054738436498199901310856954768176326), (650701601546426127698226035212569053427400368119099302618154988566040145117589078251112042148013913865987465325592, 3422274620924137599874299866190976175876264554057707557805679724942583400938598043492308710403488863754712118003972), (329115162217437319987855250907288535678003570910267742410365599788721805270664497960434944246083615324374687988772, 1937355764164056681713709286062528411906372010113118458217612958499350637396020753451869135003973593017647686229548), (177527835075795321155203268150358040256737208875489338689446485673205766361846516846112185235192877893399863048636, 940819894214883336848446652721431735154353557305622275444761101328949562298229359106747643438888193684399830850908), (2918875000182940520503038003286953436987040559041764494882014649648617490542960742576759951580018225437159877441864, 1902608634095511216958083327793878419335947906029776646356257146778609583046391805265229338144271983885416390902946), (2534523840210635107457741649037794676983059584911590322130533156815020304312610561358608645251417713586951058412830, 921788470579560227636766602777512249821853543367033270774723604077379707851618740431765053703288184610894191125621), (434519969848266665869002582905991821901013143743592945938744643533027596547471097530130079620018619900121050785417, 853873986943673439415443369912805075176435603833768706871996491366302198406752024615079441692385437626557400775004), (3079538375645182703572534217394509849459920658903395108110590760405458801219181646235817469467220906502461979583348, 1070676540611114536195908039286679350535760781015980067340734134718900747170039760588048211821413349967045108576072), (421413763147146424711602616132991461643882832549294951276895758798829765199653740962447512676448142273121941152492, 1709181007508970564663803832571204957559678349026203637113259625360031114884327221271898658846269664851279264556308), (2102953018583476608401548746351881723997299674146045365071662674574654854279471043735772812601811416888600741475011, 3226956460512939881075336989584690818272648028921498828407441422888059810368417311799009754505003982921391671140558), (1138659766378145746361789665662263448104709549639655364386705209216342521656210088987274753890939701420551424327920, 3264723092638646119113943647034839869793430599813738266994161300629366078043871345623955187903722450452771722421095), (1862488893361391865044571626217599420867430524270307642800076516806376695819040950246902402971462650524935150520626, 560120064299877766308983228015422060870591121658036826473788371837579687422923064013093208994883113578884030758519), (1353440069107074052411872230359367559551088597037545653093016344258709526365077317669200379122481776224208248477895, 1258951164443993858171923393249205937592566020254126538987537667854783159745456068773668802568782752154543029008689), (2617365104989227945108481567241568590745976809796244656328517510285545869074036432214468741124953901859781269065613, 103790193584135551768374771845075398314864190116394191928252156510211145940065804589701618564257632319205747672892), (2736023107275318649915298797894314721765227950180166877941648504198236465042033725907931766385939806843497990904208, 3471789018677855182597240573847203224529826346320978501394524658302290785904805607777443736448358991073141219316306), (2702190993824332677918548498597097429035523630496166814099463487883212167144561510899602407349494686628594707010081, 1389782189528822000754652934155584903810587367142057038421699963074365120598035016659791619244320888571484893406417), (1213921154555397190271398227872395530806433181706516886686082906042416464797902200940605334905535848866932843553917, 1331142952572951850228006257680109817102977381180272933575942308420550304486716550262427919727825629783529514504861), (264018181472773957603129915206238463514712141557867795315357405678736840336350236832733814037443828497768267209455, 3944215906714433268725879675676466991433829974999030902691262989038242782158935057407444135859598569383192468296971), (3491479775642710742546678530318842131955813114512654548030244240430197253690981890449212533997405231774654617668095, 3589102633669163727668378942783432197522019402576226597310803880921053959129385118741566979295451802713822129794393), (2423713825760225873607192024617253913582269483507464464815833057981406225141591989047480454748967383471926834985225, 913849591426844229989026995645101457154286429191698032290343868524594177670894947754767293538757123523826199253246), (349374525515488638036638686883458550793287932899475905959885716187787226148910086792721680718769514756613762741690, 24450374527246977694956259555557875292770356753728159233821521515113882324745640249037993319498128373422925390030), (873442910573017957670315317413729158456562760233072829331895910481366710154333722298813745731894037881962120586408, 3662370514955333616120814164134455085082118471646729860630217907949658119973306195015200852572962333204037060912174), (2083337244235916534893806331404384157423151998182043194533797263468648970010925545659227774800510209311883371528522, 2761408044422447221829156018252337342312240330795642327052782650127438757584359097883211777444572277090391755477405), (3384808928978181529603265055065753379893787871113335693822814142635319269202573247807240080973248940164647691512262, 2648485689548879562773990789383554789223527960770129792916252996470465166313050306664649487785922236403877264677069), (2716441170416082749653138946523306724631988994821725817030645027210151885249839248463166627261071784156370771339201, 3894949617187145742040258338273856803079727638023322689876802463582197427511049390759981390762009889713266031808901), (1882783515866019927811353488741829975758244357017154542600914559284120280119189397498514172081079566828166579999171, 2506293102153714943733073162152905252748523299015904776680156525754065969193626409386442057395876601536243128229306), (930794184188637124621374170008447306808289245816115273549980198392215714494066352938926264718119021046580136306699, 512329907020181698070454648991406622257250542940580895470930044300740737987605578092975766264432467794772958873626), (194332592501583791888166142243101711911823760963152157777085481192259067059644469691830848826223048510793939608516, 3218234700261368719715934723018945321018354749759873733972000790877076617052133895416424094478272987422167334072928), (1899661955449222918086121616966167941356994080952754571133096025505433297787844424947467801722586644366370215854974, 1357349405024699190023632281120059156834027260444373281630643852341852045252230173947070323179621745344521802407327), (2875801757659826315657817566091950014365369397824590786357312110651929560093045633289861044582344840566844845098053, 941698000325619255546794064346116583385702039832147840925221660655147769424680087394268404617529767297977976751397), (1044695594123945280125569736047733957018768847527051707718264380331640079998482144092058794475275514049153548070375, 2240708760512600818440894349177194335254193823933455416071707982087296463214403926634044490758498753107984414059881), (273997106240888164587618339096265010943540938434326171220771099130740683766778383974602179301465467047054278901273, 3995155896131257496072838767740731198642624168114428794913239688849122032792296221779378781447534968711453516050141), (1405215821813004501876633578743528267904936981121182388798022614718903537062417427776589303963541552785332024081190, 1701709524790730595236416197084715740895324196840029168913493162194787815649647987469876919820548152868233703066772), (519964082841119420834425637149502372612506441622299419365009034208677693156424432849179850777363454104364906143547, 3742545062576753433436325178619990481531253971328575157611357680001500040078112418962578686630379597474031730989278), (1911518514371787094615616303283744516228464132358511026878360496440207441877372649705478760259444074089904809246000, 226866287668255300389948471091159813859937297259973468609148939527612832945581337998199472576468801373082056104261), (1245566442814179259670062519757982775843519815784954930544036870063767229993604929965732391405204572283912811498377, 37940829143163870086741119052479135513840882906271490236044324261780185716476344884310384131711746047829391625737), (3939693754850284641003567356788104833140389103035647822486543106594264154302161401755915503983345110248924948629436, 2215515455011456207098562880777410866695274824605328467054459870487509456431277553301412969208208575986582111696803), (606406419161581329177197784128006749562823894938802421117692743760434347581710948489510066195297974124866874453743, 991217122335559879774570977801222034274147824755866788363901777427153138949307833675472020166538790353335189780244), (673740004662474334145787886834049754339039313043712200704217670709985431929183861898933485272033622488016851121807, 3970997838785813654851615673387883635995260266449439971888815106173335771100320416592392337527729141524893721857035), (3623799870837840901596096295809702617799177987677855864559806156893288574431053991875547642540683047602475609894148, 1824812069199220079693714273396713262438704828255808623057243986135307578476120174122280575873650411740552954339953), (2056768958394341003562194782878686264761319066520108792669792547697736746468896772323894380879443303198673535336510, 2156180506208608305216562788288966195075667198994575265872993763650442918979254021094015660923863779452243533860478), (1405296688731214013462210885829111962222136189667989645709167330746538540714194002147602062285959180989622285544285, 2781750426842391965436056640365859384340404584319925619559836869790840397482590305085544948893868193142901498451484), (122121289585860156703535908679172332489295942229052038442565443158271965504762054353382639683644444517507368601636, 975484937813743807363871386326880811652608303695845321468306314441408099002683554376654559624023765526857117707873), (1049814658834277540963967520783493913875762035770319498556701035174129027468972907653301165528860175032997896600304, 1575117755730233968226708403115270447223388679152401976725443572828809088231321216811233633822246407970633377501941), (1797885865972383696042804644007273042838741747674895297721572301151719381274125226701121861578084990879090727537180, 718078523890461475228764906270891372571984065724318883035045721598806536939958822071079390516720984981612726810547), (197022469350539012352535447318113619076672017834688720632371198902975156112457554282676308552529095495918080989129, 270563135026112739654616332573127060370861764226083753604379692414816690851586411623835452866647510461231628375494), (2330596877847545669461493408091481684786159303069061553610070916931849071925882463251583804840266136457257888889463, 3901762210026323895312300525626106789424226573768976940353112471547946301206765805312666500130031854836521276963533), (619811624964624719444476303116900496673008859085168741894201498817224619474505219160157937861641064975577376218579, 412406686658556352654298630920323156322183023493837276542214322272007510850137851549279378026037980257587350670284), (3189479638931708471945236305450253900824969398717336709545728987240829654987936105678348946987315567492779676870902, 3730793684785480643123087850009500915859492269546929026945833830446994797768431609028084516005952097962913813561109), (2745408674751436766141122572343830625335744175980451690432274950979719256807190553138757527471484916448513333342110, 1815115865484421861499715803463167291305067900592176576617651777130443638109144155385528071325492028186626009110182), (610774402241432755239555836969583114022562830698253027860072960210957459171559032171519942780862439801365074079135, 3464814376112464235148563373577681767925865121666197304018844344234651352899284572324781177761609500077249230267600), (1127909476159441231209689404276367995736138497178935103022576097575926633048448432210112327254881304032936131296541, 3932192988960829547240334027414204804509965886561708904997124717366471591291971276499880983412614650506545197889028), (562314946951099435574288701612309633406697109821334547335313927668843530739472928276324507229427869217178398163932, 1325146735063957886487372240557199426242632267303848459773183447837453615712817616699976679120154818314786550950548), (2884541717529354500108255616802868281704227150068898597234719417483747256792180524145632159378485923331470772854773, 1921906498050541282709360661545116278118757103095679586244231119428521275844144569001922482012015447518682655357567), (30402964508486876961425493958306546447060646617196673625356934655242022331048123839769363558098862368823702618673, 2144919081286218504204495834087752627271428131528970302666459859317146288629489239948059430329652499258781301796015), (1008182644804844996087586926834834596935615017957970207590337123742297255793818995200481674838616463994806641311064, 2111765533733432039179903411356635322778037811944836728663666835783424885566289826290383116934851945938305002265852), (228948255303850725154625206519241825197369655607838086514027078679359079684296145506392568239942827437250457721029, 789554235961038629072095821997899807185077973558115683162562251779319517505696734448479027124641811305361298010886), (3676237605550481267121753104305167265278467153071099060511582776285957435400455980065237384166212126868785235621293, 3810382305597926733593960723434151880259927181691405438953003564893973936078601761131809303883667710369147158186815), (2205342289151400430831622270831757696845843743300388288685369850921867453650865725456204785693394123319566760742640, 3587152035928808541331210664134728462335676286520870152599830781991531980005422627640548620473664484755246550943261), (1693284642815119297637994252510549187868372679028919717231269417278894881530437840900078895860307669983089165354626, 1303770902531212510014130071146595492659578723049896420681329716728643370790317631166897490888728825540758781090242), (2483938675649631069114179512766573389994478707916536838236322711314402303390244109868637691825304977756113339759638, 3663214914738438318032679874122257397578705995586950737328488551544491192028156334197103580653994049703342472854559), (3163812645044577968700124976133135885962166112740952960825886912849443604909194330214995813527722845047946516627654, 2352064023658787508472021551206379194587267380379759424577497245244941111471787047899782289348374773511438427864104), (1816833562260868061919658223207958049837766357553607513954190094516007437187934033459505698481761145116121611566540, 169030656534247079661822184833991682087574936401262043814985145347145282159403033999722320506775467409452431820167), (2579209729487471305775552288040640858912784825747956429255625728180358924800046051882897708429599491682145146625788, 2073860606031057970706627033068720875326788739268176986897392862862599459626533032759068194555994446806057894863898), (615839728333645089779067612061892514946252871514871004032847853448347020521432503860488234245373625838335252758786, 2141638076176537646435363211193035081373157605194221221292646010376286706818222384234550299888712222493778704703920), (1144086753792951217114861059010119066813936013633233858432474765306359248787636842933224994760930813747928603757098, 3492320366505983532712020902553346882096505300871123111728930775706188096682319646342856786031440239407515635402455), (2774651417693208959107369461624807591895503471304432674407835033928241530699917763319113638026066433581105523048059, 2739247945562194834680282864495712437412135428568780942569500242737439682978931282850113333880471036706459033085104), (530857049662143698801766944390639586727462572698325574729614661264949056735907435501149369093952928130360713739199, 1202590111462465680993715541192858223102876749351564273955560685950878500557565551645757186680355774856247287482977), (3436750833355634355633876769701891994062261968539215253994615244588344194569015181674870245920182981560154983762776, 332086231288803837076526335691344197077416301299776940407636901468512601697593271252601614203890351210907423520517), (473858669495942351931932517167277475211615943971874399561108959337918465172532242306050430547756813856804902797774, 3108613209090064729552522412619775213132379683782461561406388127455833251713525716972763026650641887581823523332127), (3309350761615850550817800492265829507037401915967385649209122640063618670500446353731199726237949582858116515223836, 1284526703859756516102986818066698017696322234281653369901495711865144420622573995336810797976403738993104823104931), (1952175677094271249635005364069722410157975860490928841538786431070240150598137447476565419059601011773401360269810, 2293018152712985353307935947024215658407804485894903823479702460779191309814318008644627641074552348527232069538009), (1173126051195021777776884733708767096361234082742171129393645379191362643910919950251728146616380243394174343050625, 3868794993817827337618894473750550389927849695611129487429149227607100484552097184048877461583501060792377386296548), (557457254985894819709561212466252295919606531877845755696957846826629061849102991822314204542070043163477645862114, 2406388154737392165467222665501056330441990829779421168714476810590708073975123934154095276416602990629027215027247), (923768932215425600699646266765836221267466284816923224088496730374253666801296553370339821369212936946133871761282, 1932298892743162702267167498792561307200317150998525608381026830252608050463270438777649161580672564949698107720926), (3362941654090784167281569999835660572325392181063580622453477197310559185299081882242314934530980441049703106889453, 3493566312170565184109934069165686781152414626515057142298720609747366449697164724654470627147280820748442599840161), (3751743002684734863544798384250036532450252362774460663478680938856305584556719948257382324078783326295545578107579, 3670985367844627692978720559739153183225401739501480092373989544177176591357146360663672268341950292974112244743822), (3668964858150930294966046017530901660785690740956791438729090124553738537163064225377250453226769148117224646804288, 370699193735299681829410534115317087686546978010125456561514447683247297399587109427282551895267815380599980092202), (2088468571029682513249804386469694692374721417893403373698915512387029369054873958601098365768133199076879719779318, 1208895825086548561404029178156063513193744593589144744220631776438108077406152143434443314994295209332248401941306), (521075474237421785008709533317400431209760420482818785131787887137335657700062447292661783026355705700896057083051, 3931495474483200092674543828906146350762948502972722415313406906785882905817078614960149811073696147113638235879599), (1776332823413344792648794426439807329760831472315577368177318877502731717222023460858308033362992495458995907907542, 3960105445325195682413148558017714321347370631359189401995838349954447931415673840604012337777895112200008160129565), (731339806924864134428123713162152211598710482697573323035904938555735487642230339289274166589709054381254049829493, 1557234871534313156172730262555521855248303569449196455420012721025949777045505096884803951593376550349817064824822), (2711217920283170515014355122931141950362352714735451758447595647071063772976770876131174050061755297794679990926300, 3781028446915251462128340643486607705849972802672821044500799122496546262229101111726674740157490864659125719986075), (3055075394538845211401781163955884693956104716139126552795805207124556042320001337461929114152138192414822881531571, 1971348200707004735984521754205109196359484886934027952579859224378545682521357738526078478838549113769470463017137), (3051079791851866333891024025601010362922551205067352106186901179252887554017285369808978833576307889856504798373830, 2977478008443993743294906839674948449881075765271326086496387153147294239380576354190057669937460561143721822911826), (1428116661789840906824001840207216648007727731895128664307755012791217090358780498043881695675516258623270624455669, 3669945477374908883464761660089773014294613118926603515618213628324938812870443007771926806703475851809119205182570), (2611554816849728446228723445957508607624879133012664941750446733124248312992300326142245313388417994377111370561220, 393806486630790018835963546659891380091787906116635269001985127712081897110671293783705592562697087873425909870776), (1166671097837244131869081969336627038009551814799295786223982203173757285162555052044150573386913318457479049765386, 3480848290976014346211904862062082495125406909154861913638694758460393249129799528114761717860893796930719333013009), (3222905804580821506947802173273981739391379355404520490076511578225438118391137067757230279780998336699511079768717, 1041644134069793425197555419587745028266803663094566801799277605498580968225792387348920776434718750628947246933744), (2718765531155274517158302617642182909828089700740190878635361720271018809681346451980693095217325722132837132737582, 3613036890911521359554503731753705326348634391854180997467195095797940719390151647932011346049258388184173087624884), (2910667178527028154888660442782979318296268644079381198490299645695217187017478530467138266726866302549363255702150, 2686569398864140950559593735911358773507373196075645514170863528394485267925921237698174410354938950018482158039051), (1485349803928632139615439675255706088051243962244154732704926091030465661662651617348992696277885593526653031591410, 2662238276729634232936070215320357627480919700948329734843677757602861086641573808654416255536204399286436593760286), (1784104481533561766032863365395363819969745287255227652683382226243445799614359682164819817988692034016237330822089, 159037805625181105094591552394529941416738000218004299995895669851314923808067591807274172421319337260643852726077), (728613343402516534764659104237790185622478261247495598974119313060555126406183781158241413427321517592439032333077, 2810649003424074079031136004984902980590863924836350599958140379156164733675117139068987192378983190720216580557101), (366496758243439270780404949049943441934414501827898694235551523215228181383854555333608124026894532783032173842045, 2573596682024380317857446687348112926596841923369560668021757177568061564077908781402123288123027257059762619523586), (480618610329917906726734628291692641758883920845461116746395588430827668557781071953642285100919139815990511276717, 3504834342870161770830925505970737296324960250775269651376871291966866408459407756312995506869148006429125683723055), (2131492650193023752908078246558753899857243001719596373591732518807355918025641967002873260029966516846891786694733, 1674797836236989545789813873463073997135998546166954231937839979660104521986883891872941499614210609421381260798679), (2731774738255874281029577224773161200048180342503886607853551229764542734360307566791717354172152500729398477855901, 2155263328671573598059423082548717412725456656043279370654511895493221410730418140416147671506439975812528381146067), (3470475038986417430553467149939773152562512155397085172924462446329464095235707932031719336748059711174653786192653, 2099414562739222517140186527480552746131803306668142531272614593515004542339792320679077557973601973773514033575662), (3657309914247496985769310165997865155892332508101849012126357536532235647730689335315736335090426459955495454773081, 458353655003782432425092131430902085252890158029140118404044537142625425812899809700017616409178290293355816608770), (555392092520304963280804204347645470085916303503828214872311599602857163373036238156522366324731786534372096147461, 698963881435153186910787502798044781189000602497881685605738670886712718329864760207447377746942326787012847361011), (3317146807202508142239656512977824179969472567946103716604041020715878280664520024787264193084413613895038580954881, 3290863928949340304119557460219840697857497464475748599258391277281157792375409378360975992388068645376483071468993), (3147369675384779158279828624882731084453594753464276643505757717949135299575574333450777230099379531793528885842924, 3285174616791638904709484434784686589002213085198096144102520188422903363626577359492502950105311779263908787190204), (3717733280001579681591400214183324046945384574053563472738337692038695058844419330891018016758052144099205382030678, 837212756302991038831938274272150768332745759126088882522579521876522244105177866441917571799253459024090529541342), (2550992204963081207802341803492246509186731327450841069523910207890212514507901580466289397293890663050014562323704, 2541730658563519504997970678165830808884942232735979510986363397866709760331543841264841230042309873647267677122682), (2680241449144675382321564797858727251669240276638927695831426872916148672191619787718495211987913061985887481483401, 3311102561791571503226610261938566070110210492198399868350641959211814139047134331639899452321954868945337124339243), (3193402522298004625528195524031274225175707159097775212199152453358243934226515017771305713415266870744528639380492, 187839957709023685465969315666572715466525987556890988770580406808650430989607755043130960560149840127684064951907), (1046664384145876982323458287128393278091026166089993519614893810572659728200299367176581662758474052849972745001390, 1648957695671235864690717404385665570641956921958097734796507071320212761430046319748449914662878023393989406610901), (1143473212875984740754640804322423521165198484205167777588925483669990826074437374661529864477941517931010583035759, 2530562785755984705004075804349996018041599494530671163646302985829820328851650591238888697499066452464913610440665), (2653340577527435494364446614670321998888701923593038065562006246969949417513511700522654224781979418087094428632431, 2881388201695127445041544254422620691736907363555973007373041640611502852769561631498370910424183687505101184494962), (3425519373996429955359519657932856552384592543298491797748570547121653444421423405168700641160415534918151479486343, 1102990572720800109350814196813342511125283913129705763855029183965638365404110095383481866053682379399478549024768), (3088367310942769946945235842351182245346140422292758404487283293355724578531518940468967298685724006880873134691778, 717022572220828225430369755097407068538424252837061627280995195901470864961944588869650847858632294366382320213586), (1251575174886111718743824038027447844662075520335350419069710979315067168783943342832680323151271888184203231375421, 3360476100824346812055447994066944493230820236144859415324663149116082618118033803938293100408424926652633051836889), (3870638976049678008595178636636461343311116316626387622992827128011004519783506493062840500413482484795959863682952, 1220147256726764229878770658837335682109852019962919423140552001308859401929193246354012355523689079838613828327837), (77524898003739826327402357618362404618113177219659471009677868051230792185471985974166650564875776418798778116374, 2198636856127568538045715540401005055696308987305707930096787498193413850483377256298925699498015973439665126721390), (2839886513447417851145742573110430538937073580785632618610667204999807284301827525158932775506602555039921600204347, 2056247312338860400700844640683486651151596593412203550822878970770636027108903226686752921995013253271857140913581), (256315761463117523364197164800697938124231243593670996964986361562360297262992126184219404623444923872073067927688, 1649695297218586107921389071728127966063751475087228745167220635982869176690580723729164544445702482439400086495989), (2854395142296165216324352333351087392059730465367478082193983211237714185287110900795318761063909515131684727954881, 2292499519410426681776816949491952454950363106114799793731003296229944957845667970750935816209661709857199597788533), (3963759497377525822480541981078993007980139547620545913421787868811518384745472523672762143951190710314636030084759, 3101589759889530887392024131194422205351660004406708099530104254933170256467017524527780513952769777431044716810338), (1310229630964647531637585190204980869514385860084512646437451797150949191215455481309749699467993825253946029217839, 1374925511668785868515791713839749106072998750581834509296366533030360012350381413201830020277244818815718811938198), (259407441842064579507839598772518615560743852141088566066264872213775665948135761063057278029129550375648369222166, 2031481694049927775005439943620067442711302420995124182315083161831185645790273804413676038871522455191437473805375), (617754710437170617376028357227596627183642653167152796603747796582352687280871792615278363607971090669548992293373, 1849487089930035541847423452712967769219257380320054278403453229189495349497689812864551999889465516741685760370313), (3811900059174008966038743309591400623540462361833941315320721646224688012570872486493001989790240800337697415008555, 133998677189871574156047238626698643596523728780270930487528953403880462476380803989924835025880645311493769339612), (597703383429223857751415928899083874311342159437403495360828734502810159157260731630005445744907340590923242155065, 987422897093099451191702097676705607572041408896440992199912817438218157392891891333918445800722428577084419654954), (552738880333941255646232933936488659709779799076463359646284271892150480449846124130228055660493256408747212330088, 3349426443198567601873646591922100108379839336436142412377304752725773657832417615817163525934938619783590564459692), (1675412861712224598966510401234558337078627479105911488051846675314602489541635382621022421315296280975089647899605, 1916360947231412881292684965087203804434052472634437600228207017695691134016361902650476209395535188197065563879006), (878921090785727522877567436956896640955804871840443183268700084026167594651158758724520352240586136138646044986212, 1967376074978152565979963982586745838476004526142673105535827654001118053688958237864507584029689666268206899450332), (559314964184269589520683245767814645425648871037619386442990083031604869673157390607737996848282781210034419922133, 2259730867940497973797163757458059927063802121933382018532336754904414490692112112762666383545277082512052970123227), (1634941478885455682442835710001195780699343347337500717448599690710954925402337071208542232658990726241560044464279, 1628545886273153590901899681074069312331095730719768325450445098988898455395429067493325628552221639379029855194276), (581960168339300952944662756008518402783371254801806266614426739118731127179034774935168050936435680662175146599982, 3963697506585200584619694394446345043708355711588439229271946611456205712872283863324389042999060497216075849763141), (1012950265529925883499365853699919898299505669973781141622088843061237169260932602980087330458659905342943654846724, 1333255258351244486434088660451536367653493901312764601083304275074933368698227972021301780688765308977307187232164), (2970771506071946776309913260230675256763982798049495691017368001481361877788191938088364067187228729586921432938474, 3066028185122782689025347794668232268412341677292919390038118471308510739501129046404056191065935741946628394642603), (2747500725800296120275971119688889409231148036449828300153132194818967996940379426113995929381245272849180529553566, 537672192837244676071667971544435462653326310792228569756133920569329568610521172171675361178221503767091779346623), (3609471631173909144851676649285228752113020982292882768817336512953651188240459139130371747510001769692142801709845, 1860111574282923028069897476524572994730790265730694650882705526482572139833535256411784196664237668957674727810716), (201049642828312287012100044739744204336119179357870596917191959120388181961121796184170901031509263561052713206926, 3191619924565646530395965974752958619497759761824758973181118588427014302496805882942927474307903187016442795833208), (1041362728148787180473759429170998288010808526007180291433864356249704260585616531023661831595814605467153329373631, 1120679038458342383699084655192018241739550034868688300427427526923863597347310696332831607122619359616994292949188), (2559657259550093612767883632326817223022251349105967525619513990160614768174278664781965434139440563121321821491278, 1652234296202254056908155162280029847122213430065084202045122913834486040262458144539143841410048981825785785346198), (252097335448698220331735702409749225921468117340989170228924142494621807610130398731223726457869053420924904656290, 1279528203861496350590067623286715290841952098853522825479527008158917196868184713071385434810606824362838850655590), (264376442884701552263055107881369804215426268488234218743992046853863207234666251199088321878548419699201651076124, 3335611595637113067977469879112560670788379208948742526687448640240273018866870301999790873293068406196735361235623), (1595022846572535973979426514037115017128644448870199043774861645769783985618623246079190004974726061290887154705897, 2942410536850865652398570400955064997573369565821790027767387421638674291933986637202967166228516027657565422692643), (1947482553475219150939740785314239566912912358054115634228718000680098092664410601162997991053254061054246422387638, 3605008730795980654452099245852686811943121116113957918190629250034023163848140226501387664102395792370572248827096), (1800327691233519119232855012814930003584924533520179357940716797076518268261679697013086167069130866070401402163071, 1202745053072643121932207152261574111259647193066497595148935651681028850702538825635729844087505290337364660301160), (1198937907909544237197018280769260572146934786428603421882427382840235921860136360912116120222181397911471330907983, 3714372226932539300846532996454916308502213150305364488719534159871269230116439500176579585726301805559983087932103), (2140116656724269954059630042266114304249438494758429441879511447820782180146826742519220868910192477591695412016386, 826621150743196846901089161295424839529008332981028178302652289094515368752078278253494763050557382185923961484539), (1357268277896169061262348926786977666669862242798598147685627469288813301100012934935119652206681222578885260663372, 2819355324573939387378273346333601735188341914810368853503202304013362104049489751441711058274266293650247686863577), (3465344091585270648691996463869368991339012813879938879916784381554292980951033438400743462487130698324672283806344, 1099119170069373310794878556272884566908771552967947618697756393015655033486192126019503871834862129356597946120475), (444071145141911123713309061579589219750532862766606887027443876551026298219696401441275490312557837905401686959080, 2281670713851351258805083595923034727654384153679396984184064181956969911623161535067084038233234633348797574495207), (2053144060463974164919895336473458768598942133858375170214000834493036137976992754467715693547201193647131058319424, 760544990928247142847702210476079954952846704184261663248127463697865215602107162282987362955473892345366575944100), (949588549302862780658093474767447428645342144198628441386239862415483239524648754809910222617832278344940134410825, 1388051545258071575138353639789954407574542142407328370616403476983971874793009289152977725671295702610366245219463), (1605421632343720897898917154945327814493114568689977573489161574625212469988812852297423313155091802360264867844546, 991047989905040233564275740201503354200477470565772611006926212140103351809777421730720236498593537146797278586529), (2954425071104119398667329639930827132261087666923966449398148579796018056557580834859551866266545204569521768669441, 1574852378582113923594070039805525748816143601506295942115486448222394115851163926996654054440435792630808457561775), (2296657979504721228444205815291647636042878059529378590545480976192386695715193344157528506729849142814555741011653, 1941915421394229328035657988237361609981413060243801266043190377681434983864454436356224949088094321283624779374885), (2447352800120728367196329415896667966941674615241384722019064289230267504411406541549923610825993549859817071759751, 3452414603258675326370816741279512788541861860470115422874616306326498510566038437586005763822910480915197720284299), (2620016762078232809729708488954985393205840236956466911954039237367855182506129730090543005002602956682576224932708, 936166772428171013598644783744997089746762680772097772480342765872090800755485123157533310730723311450388527018618), (36731656324233328512387688318460116564590544257354348757970752358331856869161025117255989564268920097211159859212, 2275786310406563429256304949123046249017571139337426476077651128029667032632749397608182192667029044142045614477497), (1574267373197498706983806706357067022341854941765136678096341606441460183847940631444766713713168778151782224289599, 31790861435301882453763150886903055730567389606301512838723805599292298141088984082307589460289360303144005354528), (177020197574577835379616860283687114454608357958394813123475941776282255947705617902520551278368115410466671448555, 1879387377104725329598652653546983964651122548990802927445828518527319425567649967100088485700542526212513074566574), (108665575254363983833161592745853112728537361774470031387225118786292781784676553339698842470065848139567830700066, 1937808738789017455013984576342445689404272389347736868322104828793041407531105010794421342548399862951771816751806), (3377392308910027628897055327644593562337558384923530603956672959249362401799687780782941276368348321337211755656990, 1549508424896581010301698314522557767704660145706580930332348981481158009165577663416970489858585494310977068179827), (1893775786691941267392379142060188576419261276134900904551881018670049306553168553518066615887671747015854006322122, 321783470040253297656828563252770583426037747793378349118774052027407214776871619578634448826731727208025385737184), (2789767491057295067946436193356251768592786309964693392452911075977771989101740798426858749187803010528179791598225, 1493484810631250209389656450892390143090565922882086392878440266805307906696643542515237502654181109793441149713250), (2817605657477576591826695056223780310259882242148589246694301435262899560771667885659655694194557887579539529349747, 798459908445666766455794053121783285016781711301269215935156780296966258500000851865798763835792723303768411696354), (3552219062553746583874116564088100073612976975039428229285485880081339474877313453184314597030970404129563626626862, 1630146389591436399619838675490366207571079297033685867177718074921481290864367099905127117123056792464344891664380), (2657851808837389586019865174871421058766620767333811430842811331452104351973030762101316147953453619184369634513994, 3107993220111529458288896694579127465709401306207510572908221622564041023573535459100844133162474639030089399012931), (733942269928205201985376139343174515320811667150371917907341943464714967845443318477512290526800307892352939696641, 3788174697023066164202932027536531266600361768293140955807128721601517347905614214495157834994801229043461469672820), (1897469598105423963296432387896551017982437767632908271145510755455650943723882009397535591085450571722430901649292, 2047340206178746876948791891735808856131278712722361656763711758228359998553074173743776254671611299056362732530264), (1737686196959352828116954381548637526667233356759906134358326924652011660704367665217071673652889332575364346051279, 3367258234821964027464802556193577665286847156550009114683578524534658837105702041293819251727184861893323024908932), (996721332067834988687531478738582405027893882879558057538647480649925020878570874579549467031218081697729059335420, 3092124472707313752273385192273944007396984693933534778713471846098154261604636416546993162345107910963130006430756), (689544011007908372552451748458424668920664119632617639862718764799859184708502803394834907089108655405394904232873, 3066524862354370144836878648501053349522660106298049014972063477806296008746286477692133697331291333327261206663924), (853322550870613683431169842255717492625149625487993406663524135805852337611975838882871807102282421600869873492614, 2160924051288462012744544648335590318798923157897852745131710356981082810101344704918093761072990376449059842747409), (2705153537947151857822670798106755847095382245837953790007056251645488528622410787880504765020572847468880639212907, 3466346719415369259457856273168443846501766935871664076014719646365675810120458184170794091334952971144082373314875), (2578560805110401538640731597928654323372341367111199630337362882538155140164433058411368663133668278488473628796001, 3572347234009313609944352763623900397796302306970310843260923466240639438004177617406558680739141286070110681654454), (2295112398782782178371709464681569880318824715661680298843611341710572146911506946988864798317261426655044451369258, 2485154214701759263892200438202797313681243962811465572613287608335547003634483836604383446726287627149037064200623), (1703552519045497057273974269270251536909068760000316861246678751341465743448951350212874624873556828726493691544810, 1625796243924797116012090317300152455144799169146864799390014501299505600436615187890065558907335123862963615566873), (3937667569784877363337226304513131694974000388773377881243914967834785464626305212117020572724478619398245619779707, 2527947610493141152331629381995377372916641244065254479297428900545483282882152325362044650112221265738601324567016), (2037347798031007792079776203549025539761304984478484162967264497447114271691941188564614768422576311390353962780275, 1523939205905971463308387207785568753001595501836439848564363981574742760525628557954879096469836208428963406061661), (21735003265696356163058625615431289322214231812807732160839918650341807436910753313176867459459146247108305494238, 2961986525876460795048745984987965698369031700585643319317634889730253957878003709495652934819870002239500393062160), (3952259655056453048522791388187502555012887520812203854148060720478121657833829970916590697233033496337725947713282, 3346296049886326599884279279766279938380640705932906943801214209232958934493618173018229091434861836469585092606016), (3273595988990864849224482037117939242971926668473831217993674386905611277686344048915852827022708850497504618247078, 2463240396158927503186649869230740800636324059651206463369654946987160129086660475804678962703011587329845686667088), (3650569383922268578661900351200337755242463182125693029742898449979195776923663646205661543597782099853951357607639, 641937416401486477272600476190590695691689596614715297839336354761225535635800212441389367891091326993948459056941), (3891370960585999978249840491219793468567922009033845747351109719503009854998819771055043033535338228307061352456816, 2850310972180163065103784779783536339615253291561947954222354832707966856807384483433533775957978897726223148228760), (408525172506934670370689911100317900128909754766520916745704740289711437778260337014191407964764269449308346907963, 1782127352162566084759014842918367217108637056553744781744809544813224790844346310138410299580699549294163398037443), (2067824896682860718213273370121442581920158914376045010550256196503191381955929685999350123476860970866902092258065, 1158331477691884581122892360378926744974715954443142329427710034213234912875638730043532354880739843845743249306787), (2690332378016571224242205770376370597023344796239741901098820507607502154045166454745890245618019315890310788464150, 1029991474393774939360191169557333473653252777058464212751051050587314849165991060745582308643713683832821451536597), (3244906457021028765338053321600664813474645471334248464040192952109387144850589171346296107669774815461300722800090, 2327912285779970382178548586259637339048853883449698236489784098465137426497508321958172304549590137961377344969797), (1674271041311767441316347910524652042897662503983175046873351415032211699534673431265545682532375189118311737262861, 2167413283040667536427214025134710645807826556895705443909866551494761696846982767308368613999039854732287849625991), (1105977548235994862896102745087926470801039856277766229529315567233068711725935328347196607084968530386357083556572, 2105824969928198062733302797511452854791549175152342870768045296106602653550682531289059974421680577377574533144213), (1862647512547821161007874707996482905523579899968539938344009219424548679160054023634481809813252439023124707786599, 1678434985607609653584913082957257479720622443389792022526745146490703911359561910166137288460002365571692226931008), (2908374002004157911965996202076621631313399081659652389815640990109997405660207338123016278070277162506295802949220, 487764105020939855531226502065298501346083552099482365043189416426455428791812519236279487890205333913236064596654), (3307378088381872688628627214870147658309670005711523592590863645995100605728335822353077409595433341447315078453085, 204002833028598386841739839756295995867127776286205493226927599020284111629168040663210442498862248368598303115308), (389589194625643714591024459400090739916345911225435394850558085143096825618734954322337286246412148159107685105719, 3326123682538624176831938133503325285516656493714854471519387911165326900921999853914212094491568925686898785850025), (1030107056637319253375236209383181214311200941688433855433876108409795610026772580535568282323008705559080877898315, 610310919143136896991577916438448379885879965568660672862431939648278124608487411528529688508239587691250376181508), (2715346578436320176817017058905546754210849719139666095257806032583647466649775874182368957252448168057084337771926, 800590197531251616032320463225460338753673801169558084498626378399325705450338703397629211187227184230939614168457), (2756590632615432223332604940442343551947394406681496252232178381556862948877659131173239083854521821972275588741222, 193364275025752728649277427078033196549395085219665832035772693033165045558357465130259724749787073425242148945925), (522008726080133629776538466861584555421036696237220728164410326623982474087423191010964135580106395488699309582211, 118189730233061917561717642724066761036590627707528366404799595508795257266834491966312162230324117956131173540744), (276662161676479260525709461777452612841361917600690671884092193254575548027770689095041653265932115205498506954226, 2410052484279387772100213753596432150554193877764347120700263622326671312449007887443913625313907967985304678951763), (1332454089599583341633597169747288875038711493935092673270342622563160233822024598288846238633088307502794541319866, 2039976435321267683927411583531717124413674944648694900366736834224399176008524382811192478095849089505178804250571), (153682475484367950553853945877510968336463935731841423089885424198761190233872323583409421142998348682203492507958, 3336715336600735602884110988286845869904025007847884986132717795057997315347349929859197483716565611984951527421048), (702049455800324405971993229935324595660950596878688401047491918535917166111668834949223987958353669806784108281443, 3160562408241018049025629382531923706088033927913476225556334333874174953464471415223982691775953761235820162635372), (2186956561288538494910456018821184880701154350098728327683141882813052379943892408746245235827957044015664919022985, 1731207276122356878841841362548727109496925705551805474400037348647841255354632552642272287343209221435406889992473), (1587144192146602712341664252305017377185632573015897328387796193586948569701236824805179189025332697889623910470251, 2029622640687732077081420834579085659288058779490306496406304369851409654110867210916147053070927485407878710792318), (1691153891221751497500139359985520152961687471524831314099972511206885788995251039325747977805558416294869979156338, 381283917668631236172219863599095938834777556641129052283719893982987107380653178383974740572803113758182592326759), (3746144374293226022504368489194114201911908046415596397012427755025034878823381038046103438403312540648258446869638, 2252609058677452189555488316252632444796470688951740469066998095820773512658548686599824227814052219315948257493449), (303876534315687347893191526000093858197646361397694439095906537511925648223092386959267586834508631530409641383354, 1992558066130653754247608815407403595072398249200774259624678937718796622899135194042868421646507941506103809604513), (3603567888654529132187528299389660058729360988968528005264257258027139208426834062915176591780333026597747649244988, 2266562889993353648757565939362065662230132580380430302902098654396994497780578511499216167400101494032051760153835), (2887854163212072424743871369679509269984457999705554464599103698271722303544839982327181538191409687572831102022118, 1052237779013339354741496714019625990929059602724492157240008379705653274539633527448291261451364971792379967096450), (2670340344975994983537472007203621793118039148156001446346266458192692989049008219030555328554565721212006336021360, 774861482720051060696429268398732112947505142282607687986570542047819198519365066954988724468888922847467017356652), (1922240840727991091885513609538551841865516045488268375814117027601994387090631046815216539844131069128408651258381, 2037212801692860818892390228200037261110687948070871055625747519113619396126308615559682719072140071181124670265312), (3196949475389595243378684471631576895235308160663659758937014910049542597868261186349895527646259894911288561963540, 3484550295987446440085114441550719795853641642680604046347805929187088643685773541391548734513989404919100635913015), (462137188382701171749089738177776634121545256430491652669871245154512805312417585930132095504610440463189635067929, 2870857861389828785208594676671091025871406111344772195566318819354762616189114956205278612748816773319927456036002), (1909979617219747996177157695681817988830410473880558844533564015063517233912648702598871696167755547955751621696729, 3179506901550424946994088186656015149036589354946655676616747284903248944212641001409920427615551129144422537256428), (1337581150093384054128554867367038141404542022194778226294314164403495414151490435007347087531384781284104301517365, 1946141449901565790871358056437032313736905193111452761446018081819669191341169193072926772509608492207348793324309), (3390646494729649692834187679395265676862767721747937314722916456942111116028702804557608312872387531482253218691806, 3925284734765288972453200565240681558787065140575948711826661981368480139961215077519201838159283505646699847596377), (3799916893711254040241782507325309173180330569815061201425151728781880079622892295714167496689510157699919831458749, 2596133219648071681166740082174002939957313800462272433677130197215719517408887054096916538639425181560069427531759), (978878565181125424962867194236844974629639523507661604462110919097830437631306317376641606373204239690951521345725, 2932094668034153997052856380517292128740012372305541386695278208826477254919209518299094346359270901752834240041682), (734015267443182931840629254260683750688630663141803815304913019076516120611303526970850212871852329539558227585464, 2135630418277376319155585600596384348531815563167086838687968263474526252381882129388876413264794338374690361217793), (3566255293485747445879984781311601873925975315414327971086741441546525140429018622870398319994650065931762266772644, 1953153808034941308052920360076402276699517696962940906145899074983238795789888792380860796191435111928194502757561), (1718548289061170809041199854428963421693390423327148841022530115851525367956280178024262548969674925338819796274395, 1149645365158779987154296050228758562991009282856537593607276809968283516885474063248541837009810869628964300273175), (2121483290603402953133398621522357134897778609947516273488414265753881910917212187326749101716229009749085639528290, 2165387819668377886632667580052938500086308766976070600248234339381166101919729818716385397330917040579578155982797), (3304435295218535805857882095719633446753233622128775699661504202797497869765426743857894383684366674580012516660776, 716865923297681074441395496293522828546294700899606727842506795012040306877276928267804637926421697177890675448777), (1240856513138495368455653700252377037538009543744066005484189503727586282046902244799389389700864420672188302850919, 2162828426555245574374637404792081779063251250479373710957467925626303679041054431937792909550162198877382353835828), (1329180757929382992502569190267606181548270144287071748892237107869586626504794057992490165906457309318679572763181, 1919134342801591948127332376377398080657438176177190004548225018568980836588489155914510158665611537344598498662343), (2586439047577030738886669269717410615234354186598169190333979311709449330203161920730331329812469086999542141804839, 3792771646685334099012689299094673372795037102345599114129159117087418568579258975682054610969809930709614129330045), (90607760429096534798924989799561728812192621365023371306892949501967774649365278863021305119309564176169581268262, 3626860450869997582158999001594395992512346642356922782530601583985010084646578242777054549702674236100146224219388), (2106345093870032471022465558531540222471718266868215903895218089293505436120750844232311394643224336868669761945166, 2214615884070653297112928071251106359154573910083538537657408507874398173363103366283316565103055208506436313936064), (2605552388309807266511135888348625826066817662935513382464996994696168833907096222549799403868586112683614906506391, 1144369231863089459614793604468381329600347250441508324165855433945221370158327055964460664391475731325830255715808), (461255754456207864973394033128253517443841633735780561840922368780913152568904582387054432009932776066948741485101, 729009725674910438149629811750636392012625360719868110576328057222378382906439978343377811440914796150774049715028), (1950527194347223583386503709776245870306117590038911374453506330917187060307587090493611484848451896614780983307201, 1654447408133772341999740041040022480112927809749980414723446421137185844509473258225344131477064436460666083697081), (2174148179792157512198158314754842965160063987252451940503849450464146672286385179082286668129916616952849666853485, 195367241805028860984605138022953214852470537352185654770016651873723233734709179027886350477873538058603964201871), (1169942158360040293391774665518587224378223394221401744820188183726786614388704119837934119585338130055673183903493, 2275641206952746667635988217674155151411782436907190609852853885585508142548853190093475684186561954371133624366048), (388822756447349489527834141513883684964051093664367562907917062441257861628901816749381535078771266911306674420440, 2375627193002512834514447262591827441280896101724344997523605373669648019998398454191827168332235497366356624012998), (2418875526934952899103714773437883015533785600428227152542860336425540671414770651361711565224140179877294061260020, 1951471427504725410762300862641380918220587949528196324111709795471829074594535188444417962715622070994129227984886), (1115990057538063395755389087515042310435207686577124874322302063901741875234709574830975029992159712643238579727890, 3155174883209680388522431700163467406210933863035636047981658140392903324858299257125012795428297395222472442201270), (1918826007531988826532588038365734749878825684573269528140484288412482365446545307542879984433482707178674063746492, 748137279899430543156450867614532364829750451730919547297011457874111388926397430316293334295314461406502743360487), (3690024622540110172741545209485418000745377193213338497476439442353248216355234434762849877999071201325253810141426, 1262113044483783968896441459000005577191584947846468983604656965957250751365691568038951051619110179696519338392925), (1266414164965357925481604584825669649620176611670652908832173181593519298416322971202472303130942537039406974863931, 587874208364341725658277129955434092561760045053303270079179495723823711301118492890176328903534335835040892430354), (463280522281805207447617981120767009770487473810348286035335830306547192774291252171262625715092473859915995375720, 2759057523033990554050795998270371724846506852026575254746159164487668718486768888176618230277451651186453698944991), (403940603018140410286243587783131783896724426261313030691900519634049047812732264277040552238770054971549344074471, 1315526822266435270735016255027761225444705991031110084207437427899040912055550490606968977110744166527925143152778), (1696677966172231744233138322399881550660645855491065636116783739345956464056234111211734505613239882945026839761955, 1946688840176886133509534781021944097802000239174060816810638174715575984901231536611855441505777376139102922136983), (617681937275492952408585258995399671910310726991425839667733047629086167972859427960638277739983710950077157197757, 1539355236860681460682825516146036282093842658452955581414239516224951420867412890491959775659394170858813184941484), (2651819669954654577882482042933512866999186040496706514079441659262161985160342600303405268527356881938603731631722, 3341328796703834345295131094878205269330465421309877640809534957064868993232493188222294365771728056321795989670941), (152803193221065776864809545177174916636814207334176885194595964201593271303026427128470158134248035074738097967600, 3639748576293854693841854922988779456821607113166549123874505873481490042779214207251775854255081023022030733643760), (3909583343743766050387247948567936765121215521060189901971326065024285612473848089377541401918215976476708520882749, 2332367317764759801573983936435466286109617662571051036501951410251388667066472650596102203808344475772533808528950), (2158481768733875689652875664887000341412391408111141023305451235727238774416515982906594212788891677344881888456393, 1698710116889161826635897093462172390678342162012906326383441390849565852586581887381899782356784997679028900370097), (3322155924417357261700064037669513644039754833143040743274502035890729312264662831334570967501116037136904918434147, 3585704031228317040458405188392794858887986900395574022326101195729542161368444057476312317474683071844462069739078), (1066058860222258808879786548571477887057585467941342072597175165156355160593041348176712910446475061369748318201589, 256034218301240407326233580068818797143225725561051748544824330590773098262979132150764800594029172810538890390488), (2549245916595691919023600786853895753607837663023188204268001961348159509872854660145104680267133721343886721849159, 3057397368395334631929598068157013915306096020422876199511256663846696118441328876115418734063175883826946445223362), (1979538735817695642443769690422541423665115379321895433641064182522384920874678864402489107436974256158308880697026, 1321737595489170317519370691973244623661103535472204681912671145998144354626763073340325466862563217254790981061295), (919846299858070082100293211549391067591062891005251177056539696910655548251245782286736269576181231129171245988999, 1014747318909771063730283566278276104131509470735583966494497484225823015718206789301000576295864729452539365730522), (3366387636787585314008676034945076972892631090612672780443355952239192315964321591353070636784122693875095992806579, 1817507562813614856767426624022402778256189855921034450258656369202622277284037412506218473672871487123659966171859), (1906118031393343309635917137142203610932111851643061311994992866336686072344617775658581975302845937745954774594829, 4343557681708134505715353883720584744618182851533272215293650955251741856635485528307179697829399829150137835247), (2358344410482271422097270467420677149384631189336948552477080782079311776471754826833651042503223061306543207566130, 1305515833990387731315537798215595797811569078245955543704201449505199434066634362598389188207836140355275005253226), (3128366213735873052682594619802830600357351413250802932922122459110272106617162279907031455733288372468955762562925, 3519031583472222679993174260378665330716844298192409123752024582400999743762906734483437302914795991345087057640435)]

検討

cs の作り方から、ある bit と次の bit が異なる場合、対応する2点の「差」を取ると G1 のスカラー倍もしくは G2 のスカラー倍のいずれかとなります。逆に、ある bit と次の bit が等しい場合は十分高い確率で G1 のスカラー倍・G2 のスカラー倍のいずれにもならないと考えられます。

そして、Weil Pairning が自明かどうか、という点に着目します。具体的には、Q が P のスカラー倍のとき、その Weil Pairning は必ず自明（1）になることを利用します*6。

解法

「solve.sage」

from Crypto.Util.number import *

# BLS12-381 curve
p = 0x1a0111ea397fe69a4b1ba7b6434bacd764774b84f38512bf6730d2a0f6b0f6241eabfffeb153ffffb9feffffffffaaab
K = GF(p)
E = EllipticCurve(K, (0, 4))

G1, G2 = E.gens()
o1, o2 = G1.order(), G2.order()
ct = eval(open("chall.txt","r").read())

flag = ""
current = 0
for i in range(len(ct)-1):
  P = E(ct[i]) - E(ct[i+1])
  if G1.weil_pairing(P,o1) == 1 or G2.weil_pairing(P,o2) == 1:
    current ^^= 1
  flag += str(current)

print(long_to_bytes(int(flag,2)).decode())

3. おわりに

1 問逃したのが悔しいです*7。

次回は全完を目指します。

*1:もちろん競技順位が変動するわけではありませんが upsolve するのとしないのとでは向上能力の差が激しくつきます。

*2:3問目の「A Dance of Add and Mul」は 2nd blood でした。

*3:雑に 400 くらいと見積もりました。足りなければ増やせばよいので。

*4:チョコラスクさんのWriteup https://chocorusk.hatenablog.com/entry/2024/09/16/001208を見るとrは既知なのでnextprime(r)も既知、とありました。まさにそのとおりですね。なので総当たりする変数は1個だけで済みますからitertoolsは不要でした。

*5:成否は底の選び方にもよるので、ある程度やってうまくいかなかったら中断して底を置き換えます。今回はたまたま 2 で成功しています。

*6:逆が成り立つかどうかは数学的検証が必要ですが、競技中は目を瞑りました

*7:LLL をちゃんと理解していなかったのが原因です。