デジタルペンテスト部の中嶋です。私事ですが、9月13日から9月15日にかけて関西（主に大阪）へ旅行に行ってきました。ただ、何か他に予定があったような気がするなと思ってずっとモヤモヤしていたのですが、その正体はこれでした。

旅行中にCTFに参加することが確定してしまいました*1。

AlpacaHackの概要を説明すると、短期間で個人参加のCTFが定期的に開催されるプラットフォームです。今回はその第3回目の「AlpacaHack Round 3 (Crypto)」でCryptoのジャンルの問題が4問出題されました。私はparabola0149として今回のCTFに参加しました。

この記事では前半で旅行をしながらCTFに参加した記録を紹介し、後半では各問題の解説をします。

CTFに参加した時に使用した環境
旅行をしながらCTFに参加したときの記録
writeup

CTFに参加した時に使用した環境

今回は旅行中にCTFに参加したので基本的にPCは使えず*2、スマートフォンで問題を解いていました。 CTFの問題を解くにあたり、以下のアプリやサービスを利用しました。

Pydroid 3
Android用のPython実行環境ですが、今回は問題で配布されたPythonファイルなどの閲覧に使用しました。

Gist
GitHubが提供しているコード共有サービスですが、今回はプログラムの作成に使用しました。スマートフォン上でプログラムを書くときに、Gistで書くのが個人的に一番書きやすかったような気がします。

SageMathCell
Cryptoの問題を解くときの必需品であるSageMathをブラウザ上で実行できるサービスです。これが無かったら旅行中にCryptoの問題を解こうという気持ちにはならなかったと思います。

旅行をしながらCTFに参加したときの記録

11:20頃
- 新世界の串かつ屋で昼食
- AlpacaHackの開始時間が近づいているのでサイトをチェック

12:00頃
- 昼食を終えて日本橋へ移動開始
12:00
- AlpacaHackが開始
- 日本橋に到着後、最初の問題「qrime」の内容を確認
12:20
- 「qrime」を解きフラグを提出
- 2問目「Rainbow Sweet Alchemist」に取り掛かる
13:00頃
- 日本橋からあべのハルカスへ移動
13:15頃
- あべのハルカスに到着

13:38
- あべのハルカスで大阪の街を眺めながらポラードのp-1法を思い出し、「Rainbow Sweet Alchemist」を解いてフラグを提出
- 3問目「A Dance of Add and Mul」に着手
14:30頃
- あべのハルカスを後にして伊丹空港へ移動開始
15:34
- 電車に揺られながらSageMathの実装を確認し、楕円曲線の点の整数倍の判定法が分かったので、「A Dance of Add and Mul」が解けてフラグを取得
- 最後の問題「Hat Trick」の攻略を開始

16:00頃
- 伊丹空港に到着
- SageMathCellから外部に接続できないことを思い出す
- 先にプログラムを書き上げてPCが使えるタイミングが来たらプログラムを実行する作戦としたが、なかなかPCを使える時間が確保できない*3
17:00頃
- 飛行機が離陸
- 人生で初めて使用した機内Wi-Fiへの接続に苦戦しながらもPCから問題サーバへ接続
- しかし書いておいたプログラムにバグがあり*4、競技時間内に修正が間に合わなかったのでフラグ取得ならず

18:00
- AlpacaHack終了
- 結果は4問中3問解いて28位でした。
18:15頃
- 羽田空港に到着
19:40頃
- 帰宅
- 家に着いたら荷物の片付けは後回しにしてプログラムの修正を行い、「Hat Trick」も解いてフラグを取得

競技終了後に解いたものも含めると全てのフラグを取得しました。競技中には全ての問題を解くことができませんでしたが、旅行中であったことを考慮すれば4問中3問という成績は健闘したと言えるのではないでしょうか。 AlpacaHackで次にCryptoの問題が出題されるのは10/12(土)の「AlpacaHack Round 5 (Crypto)」なので、今度は競技中に全ての問題を解けるようCTF以外のことに気を取られない環境で取り組もうと思います。

writeup

qrime (91 solves)

not crime and prime

問題の概要

この問題では以下のファイルが配布されています。

暗号化に使用したPythonファイル (chall.py)
鍵と暗号文が記載された出力結果 (chall.txt)

この問題では、まず256ビットの整数 $q, r$ を生成します。 $q$ より大きい次の素数を $\mathrm{nextprime} \! \left( q \right)$ として表すと、 $p$ は

$\begin{equation} p = q \cdot \mathrm{nextprime} \! \left( r \right) + \mathrm{nextprime} \! \left( q \right) \cdot r \end{equation}$

というように計算されています。 $p, q$ が素数となるまでこの計算を繰り返します。後は以下のように平文 $m$ を通常のRSA暗号のアルゴリズムで暗号化して、暗号文 $c$ を計算しています。

$\begin{gather} n = p q \\ e = \mathrm{0x10001} \\ c = m^ e \bmod n \end{gather}$

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$ より大きい次の素数は $q$ に近い値になると考えられるので、 $q \simeq \mathrm{nextprime} \! \left( q \right)$ が成り立ちます。この関係から、

$\begin{align} n &= p q \\ &= \left( q \cdot \mathrm{nextprime} \! \left( r \right) + \mathrm{nextprime} \! \left( q \right) \cdot r \right) q \\ &\simeq \left( q r + q r \right) q \\ &= 2 q^ 2 r \\ \end{align}$

$\begin{align} 2 q^ 2 r &\simeq n \\ q^ 2 &\simeq \frac{n}{2 r} \\ q &\simeq \sqrt{\frac{n}{2 r}} \end{align}$

が成り立つので、 $q$ のおおよその値が分かります。実際の $q$ の値は $\sqrt{\frac{n}{2 r}}$ より少し小さいので、 $\sqrt{\frac{n}{2 r}}$ 以下で $n$ を割り切るものを見つければ $q$ の値を求めることができます。

$p = \frac{n}{q}$ とすれば、後は通常のRSA暗号の復号の手順に従って、

$\begin{gather} \phi \! \left( n \right) = \left( p - 1 \right) \left( q - 1 \right) \\ d \equiv e^ {-1} \pmod {\phi \! \left( n \right)} \\ m = c^ d \bmod n \end{gather}$

とすれば平文 $m$ が求まります。

solve.sage

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


long_to_bytes = lambda n: n.to_bytes(ceil(log(n, 2) / 8), 'big')

q = floor(sqrt(n / (2 * r)))
while n % q != 0:
    q -= 1
p = n // q
assert p.is_prime()
assert q.is_prime()
assert p * q == n

phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))

Alpaca{q_and_r_have_nothing_to_do_with_QR_code}

Rainbow Sweet Alchemist (42 solves)

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

問題の概要

この問題では以下のファイルが配布されています。

暗号化に使用したPythonファイル (chall.py)
鍵と暗号文が記載された出力結果 (chall.txt)

この問題では、最初に乱数生成器のシード値を固定して、その乱数生成器で生成した64ビットの素数が再現可能になるようにしています。 64ビットの素数を16個生成して、それらの積に $2$ をかけて $1$ を足した値を $p$ としています。そして $p$ が素数になるまで64ビットの素数のうちの1つを新たに生成したものに置き換えて計算し直しています。 $q$ についても同様に計算しています。後は平文 $m$ を通常のRSA暗号のアルゴリズムで暗号化して、暗号文 $c$ を計算しています。

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 - 1$ は比較的小さな64ビット以下の素因数のみの積で表すことができます。このような性質を持つ $p$ を素因数として含む整数 $n$ を素因数分解する方法としてポラードのp-1法があります。 $a$ を $p$ と互いに素な数、 $M$ を $p - 1$ の倍数とすると、フェルマーの小定理 $a^ {p - 1} \equiv 1 \pmod p$ より、

$\begin{align} a^ M &\equiv a^ {k \left( p - 1 \right)} \\ &\equiv \left( a^ {p - 1} \right)^ k \\ &\equiv 1^ k \\ &\equiv 1 \pmod p \end{align}$

が成り立つので $a^ M - 1$ は $p$ の倍数となります。 $\gcd \! \left( a^ M - 1, n \right)$ を計算した結果も $p$ の倍数となり、さらに言うと $p$ 自体が得られる場合が多いです。 $p$ は未知の値なので条件を満たす $M$ の値も不明ですが、通常は $p - 1$ の倍数になる可能性が高くなるように素因数を多く含む数が使用されます。

この問題では、 $p - 1$ は生成した64ビットの素数の積に $2$ をかけた値なので、それに合わせて $M$ を用意すると $n$ を素因数分解することができます。競技中にこの問題を解いた時は、 $p - 1$ の素因数に $2$ が存在することを忘れており $M$ に $2$ を含めていませんでしたが、適当に $a = 2$ と設定したときに $a \equiv b^ 2 \pmod p$ として表せる値であったので問題は発生しませんでした*5。後は通常のRSA暗号の復号手順に従えば平文 $m$ が求まります。

solve.sage

n=2350478429681099659482802009772446082018100644248516135321613920512468478639125995627622723613436514363575959981129347545346377683616601997652559989194209421585293503204692287227768734043407645110784759572198774750930099526115866644410725881688186477790001107094553659510391748347376557636648685171853839010603373478663706118665850493342775539671166315233110564897483927720435690486237018231160348429442602322737086330061842505643074752650924036094256703773247700173034557490511259257339056944624783261440335003074769966389878838392473674878449536592166047002406250295311924149998650337286245273761909
e=65537
c=945455686374900611982512983855180418093086799652768743864445887891673833536194784436479986018226808021869459762652060495495939514186099959619150594580806928854502608487090614914226527710432592362185466014910082946747720345943963459584430804168801787831721882743415735573097846726969566369857274720210999142004037914646773788750511310948953348263288281876918925575402242949315439533982980005949680451780931608479641161670505447003036276496409290185385863265908516453044673078999800497412772426465138742141279302235558029258772175141248590241406152365769987248447302410223052788101550323890531305166459


import random

isPrime = lambda n: Integer(n).is_prime()
long_to_bytes = lambda n: n.to_bytes(ceil(log(n, 2) / 8), 'big')

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."


a = 2
a = power_mod(a, 2, n)
while True:
    y = deterministicGetPrime()
    a = power_mod(a, y, n)
    g = gcd(a - 1, n)
    if g != 1:
        p = g
        break
q = n // p
assert p.is_prime()
assert q.is_prime()
assert p * q == n

phi = (p - 1) * (q - 1)
d = inverse_mod(e, phi)
m = pow(c, d, n)
print(long_to_bytes(int(m)))

Alpaca{n0t_s0_sm00th_y3t_n0t_s0_s4f3}

A Dance of Add and Mul (30 solves)

So just dance, dance, dance...

問題の概要

この問題では以下のファイルが配布されています。

暗号化に使用したSageMathファイル (chall.sage)
暗号文が記載された出力結果 (chall.txt)

まずBLS12-381という楕円曲線とその2つの生成元 $G _ 1, G _ 2$ が用意されます。ランダムな整数 $x _ i$ を生成して、平文のビット $m _ i$ に対して、

$m _ i = 0$ の場合、 $C _ i = x _ i G _ 1 + x _ {i + 1} G _ 2$
$m _ i = 1$ の場合、 $C _ i = x _ {i + 1} G _ 1 + x _ i G _ 2$

というように暗号文 $C _ i$ を計算しています。

chall.sage

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)]

解法

平文の隣り合うビットが異なる場合、例えば $m _ i = 0, m _ {i + 1} = 1$ の場合は暗号文の差を取ると、

$\begin{align} C _ i - C _ {i + 1} &= \left( x _ i G _ 1 + x _ {i + 1} G _ 2 \right) - \left( x _ {i + 2} G _ 1 + x _ {i + 1} G _ 2 \right) \\ &= \left( x _ i - x _ {i + 2} \right) G _ 1 \end{align}$

というように生成元 $G _ 1$ の整数倍になっています。 $m _ i = 1, m _ {i + 1} = 0$ の場合も同様に $C _ i - C _ {i + 1} = \left( x _ i - x _ {i + 2} \right) G _ 2$ が成り立つので生成元 $G _ 2$ の整数倍になりますが、隣り合うビットが同じ場合は暗号文の差をこのように表すことはできないです。つまり楕円曲線のある点が他の点の整数倍であるかどうかを判定できれば平文の隣り合うビットの関係が得られることになります。

少し話が変わりますが、楕円曲線のある点が他の点の何倍であるかを求めるのは離散対数問題であり、一般の場合には現実的な時間で解くのが困難です。しかしSageMathで楕円曲線の点に対する離散対数を求める際に、解が存在しない場合（楕円曲線のある点が他の点の整数倍でない場合）はすぐにエラーになったような気がすると思い、以下のプログラムで検証しました。

dlp _no_solution.sage

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

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

G1.discrete_log(G2)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In [1], line 9
      6 G1, G2 = E.gens()
      7 o1, o2 = G1.order(), G2.order()
----> 9 G1.discrete_log(G2)

File /home/sc_serv/sage/src/sage/schemes/elliptic_curves/ell_point.py:3798, in EllipticCurvePoint_finite_field.discrete_log(self, Q)
   3796     pass    # cyclic rational n-torsion -> okay
   3797 elif self.weil_pairing(Q, n) != 1:
-> 3798     raise ValueError('ECDLog problem has no solution (non-trivial Weil pairing)')
   3800 return ZZ(pari.elllog(self.curve(), Q, self, n))

ValueError: ECDLog problem has no solution (non-trivial Weil pairing)

このSagaMathの実装を参考にすれば楕円曲線の点の整数倍の判定ができそうです。 GitHubでもSageMathのソースコードを見ることができ、バージョンの差異のため行番号が異なりますが楕円曲線の点の整数倍の判定についても確認できます。

競技終了後に他の方のWriteupを見て知ったのですが、上記のSageMathの実装で楕円曲線の点の整数倍の判定ができるのはWeilペアリング $e _ n \! \left( P, Q \right)$ の性質によるものです。 Weilペアリングは常に $e _ n \! \left( P, P \right) = 1$ が成り立つので、楕円曲線のある点とその整数倍の点のWeilペアリングは以下のように $1$ になります。

$\begin{align} e _ n \! \left( P, k P \right) &= e _ n \! \left( P, P \right)^ k \\ &= 1^ k \\ &= 1 \\ \end{align}$

楕円曲線の点の整数倍の判定ができれば平文の隣り合うビットの関係が分かり、平文の最初のビットはAlpaca{...}の最初の文字の最上位ビットなので $0$ であることが分かるので、これらの情報からフラグを得ることができます。

solve.sage

cs = ... # chall.txtの内容


long_to_bytes = lambda n: n.to_bytes(ceil(log(n, 2) / 8), 'big')


def is_multiple_of(P, base):
    # https://github.com/sagemath/sage/blob/develop/src/sage/schemes/elliptic_curves/ell_point.py#L4134
    n = base.order()
    return base.weil_pairing(P, n) == 1


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

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

bit = 0
m = bit
for C1, C2 in zip(cs[:-1], cs[1:]):
    C1, C2 = E(C1), E(C2)
    C = C1 - C2
    f1 = is_multiple_of(C, G1)
    f2 = is_multiple_of(C, G2)
    bit ^^= 1 if f1 or f2 else 0
    m = (m << 1) | bit

print(long_to_bytes(int(m)))

Alpaca{this_title_is_inpired_by_a_rhythm_game}

Hat Trick (26 solves)

strike not two, but three bird with one stone!

nc 34.170.146.252 53764

問題の概要

この問題では以下のファイルが配布されています。

問題サーバーで動かしているPythonプログラム (server.py)

問題サーバーに接続すると最初に3つのローリングハッシュの法 $p _ i$ と底 $b _ i$ が表示されます。アルファベット小文字のみからなる $m = 54$ 以下の長さの文字列を入力すると、文字列の $j$ 番目の文字を $c _ j$ としたときに以下のようにローリングハッシュ $h _ i$ が計算されます。

$\begin{align} h _ i = \left( \sum _ {j = 0}^ {m - 1} c _ j b _ i^ j \right) \bmod p _ i \end{align}$

ローリングハッシュ $h _ i$ が指定された値になるような文字列を入力するということを3回繰り返すとフラグが取得できます。

server.py

import json
import os
import random
import signal
import string
from Crypto.Util.number import getPrime, getRandomInteger

class RollingHash:
  def __init__(self, p=None, base=None) -> None:
    self.p = getPrime(64) if p is None else p
    self.base = (getRandomInteger(64) if base is None else base) % self.p
  def hash(self, s: str):
    res = 0
    for i, c in enumerate(s):
      res += ord(c) * (self.base ** i)
      res %= self.p
    return res

def check_str(s: str, max_len: int):
  assert len(s) <= max_len, "too long!"
  for i, c in enumerate(s):
    assert c in string.ascii_lowercase, f"found invalid char {c} at {i}"

signal.alarm(3 * 60)

flag = os.environ.get("FLAG", "fakeflag")
MAX_LEN = 54

rhs = [RollingHash() for _ in range(3)]
print("params:",json.dumps([{ "base": rh.base, "p": rh.p } for rh in rhs]))

for _ in range(3):
  target_hash = [random.randrange(0, rh.p) for rh in rhs]
  print('target:', target_hash)
  s = input("> ")
  check_str(s, MAX_LEN)

  actual_hash = [rh.hash(s) for rh in rhs]
  if target_hash != actual_hash:
    print("Oops! You missed the target hash. Better luck next time!")
    exit(1)

print("Congratulations! Here is your flag:", flag)

解法

この問題は $h _ i = \left( \sum _ {j = 0}^ {m - 1} c _ j b _ i^ j \right) \bmod p _ i$ という条件と入力する文字列がアルファベット小文字のみ（ $\mathrm{0x61} \le c _ j \le \mathrm{0x7a}$ ）という条件をClosest Vector Problem(CVP)の形式に変換して解きました。 CVPはBabai's nearest plane algorithmを用いると近似的に解くことができます。ローリングハッシュ $h _ i$ の式を変形すると以下のようになります。

$\begin{align} h _ i &= \left( \sum _ {j = 0}^ {m - 1} c _ j b _ i^ j \right) \bmod p _ i \\ &= \left( \sum _ {j = 0}^ {m - 1} c _ j \left( b _ i^ j \bmod p _ i \right) \right) \bmod p _ i \\ &= \sum _ {j = 0}^ {m - 1} c _ j \left( b _ i^ j \bmod p _ i \right) - k _ i p _ i \end{align}$

ここで、 $C$ を適当な定数として格子 $B$ を以下のように定義します。

$\begin{equation} B = \left[ \begin{array}{ccc|cccc} C \left( b _ 0^ 0 \bmod p _ 0 \right) & C \left( b _ 1^ 0 \bmod p _ 1 \right) & C \left( b _ 2^ 0 \bmod p _ 2 \right) & 1 & 0 & \cdots & 0 \\ C \left( b _ 0^ 1 \bmod p _ 0 \right) & C \left( b _ 1^ 1 \bmod p _ 1 \right) & C \left( b _ 2^ 1 \bmod p _ 2 \right) & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ C \left( b _ 0^ {m - 1} \bmod p _ 0 \right) & C \left( b _ 1^ {m - 1} \bmod p _ 1 \right) & C \left( b _ 2^ {m - 1} \bmod p _ 2 \right) & 0 & 0 & \cdots & 1 \\ \hline C p _ 0 & 0 & 0 & 0 & 0 & \cdots & 0 \\ 0 & C p _ 1 & 0 & 0 & 0 & \cdots & 0 \\ 0 & 0 & C p _ 2 & 0 & 0 & \cdots & 0 \\ \end{array} \right] \end{equation}$

以下に示すベクトル $t$ を $B$ に掛けた格子ベクトル $t B$ について考えます。

$\begin{equation} t = \bigl[ \begin{array}{cccc|ccc} c _ 0 & c _ 1 & \cdots & c _ {m - 1} & -k _ 0 & -k _ 1 & -k _ 2 \end{array} \bigr] \end{equation}$

$\begin{equation} t B = \bigl[ \begin{array}{ccc|cccc} C h _ 0 & C h _ 1 & C h _ 2 & c _ 0 & c _ 1 & \cdots & c _ {m - 1} \end{array} \bigr] \end{equation}$

ベクトル $x$ を以下のように定めると、 $x$ に最も近い格子ベクトルが $t B$ になると考えられます。

$\begin{equation} x = \left[ \begin{array}{ccc|cccc} C h _ 0 & C h _ 1 & C h _ 2 & \frac{\mathrm{0x61} + \mathrm{0x7a}}{2} & \frac{\mathrm{0x61} + \mathrm{0x7a}}{2} & \cdots & \frac{\mathrm{0x61} + \mathrm{0x7a}}{2} \end{array} \right] \end{equation}$

CVPを解いたときに得られる $t$ から $c _ j$ の値が分かるので、それを文字列に直して入力すると問題が解けます。時々アルファベット小文字以外の文字を含む文字列が得られることがあるので、その場合は最初からやり直しています。

solve.sage

#!/usr/bin/env sage


from pwn import remote
import json
import numpy as np
import string


# host = '34.170.146.252'
host = 'localhost'
port = 53764


def solve_CVP(B, x):
    # https://cims.nyu.edu/~regev/teaching/lattices_fall_2004/ln/cvp.pdf
    B, T = B.LLL(transformation=True)
    G, _ = B.gram_schmidt()
    v = x
    t = vector(ZZ, [0] * B.nrows())
    for i in reversed(range(G.nrows())):
        i -= G.nrows()
        cj = round((v * G[i]) / (G[i] * G[i]))
        v -= cj * B[i]
        t[i] = cj
    return x - v, t * T


def make_string(rhs, target_hash):
    MAX_LEN = 54
    n1, n2 = MAX_LEN, 3
    B1 = np.array([[pow(rh['base'], i, rh['p']) for rh in rhs] for i in range(n1)], dtype=object)
    B2 = np.diag(np.array([rh['p'] for rh in rhs], dtype=object))
    C = 2 ^ 64
    B = np.block([
        [C * B1, np.eye(n1, dtype=object)        ],
        [C * B2, np.zeros((n2, n1), dtype=object)],
    ])
    x = np.hstack([C * np.array(target_hash, dtype=object), np.array([(ord('a') + ord('z')) // 2] * n1, dtype=object)])
    B = Matrix(ZZ, B)
    x = vector(ZZ, x)
    v, t = solve_CVP(B, x)
    return bytes(t[:n1])


while True:
    with remote(host, port) as conn:
        data = conn.recvuntil(b'\n')
        rhs = json.loads(data.removeprefix(b'params: '))
        
        for _ in range(3):
            data = conn.recvuntil(b'\n')
            target_hash = json.loads(data.removeprefix(b'target: '))
            
            conn.recvuntil(b'> ')
            b = make_string(rhs, target_hash)
            print(b)
            if not all(i in string.ascii_lowercase.encode() for i in b):
                break
            conn.sendline(b)
        else:
            data = conn.recvall()
            print(data)
            break

$ ./solve.sage 
[+] Opening connection to 34.170.146.252 on port 53764: Done
b'uorjkoqmmsoojlphpqpnfmnqeekoonrllerpjosppjojomtepgrjkj'
b'tndrunoegmfplqmpkunqpkplmelnmorftkqgmqonoqktnopnpjgpmg'
b'ihegjsrqkjjjlntjqrghpjhpkpjpjlxhmroniknkgnuqmktnsisjll'
[+] Receiving all data: Done (97B)
[*] Closed connection to 34.170.146.252 port 53764
b'Congratulations! Here is your flag: Alpaca{i_st1ll_h4v3_n0_id3a_why_r0ll1ng_h4sh_is_c4ll3d_th4t}\n'

Alpaca{i_st1ll_h4v3_n0_id3a_why_r0ll1ng_h4sh_is_c4ll3d_th4t}

*1:通常であればCTFへの参加を諦めるという選択肢もあったのですが、今回は私が興味を持っているCryptoのジャンルのCTFだったので、何としても参加したいという気持ちがありました。

*2:一応持ってきてはいましたが、さすがにPCを開きながら旅先を移動する気にはなりませんでした。

*3:お土産を買っていた時間やラーメンを食べていた時間については考慮しないものとします。

*4:格子の中で3行必要な箇所を1行しか用意していなかったり、整数であるはずの値が何故か浮動小数点数になっていたりしていました...

*5:Mに2を含めない条件でaを他の値に変更すると素因数分解が終了しない場合もあります。

ラック・セキュリティごった煮ブログ

セキュリティエンジニアがエンジニアの方に向けて、セキュリティやIT技術に関する情報を発信していくアカウントです。

AlpacaHack in 大阪

CTFに参加した時に使用した環境

旅行をしながらCTFに参加したときの記録

writeup

qrime (91 solves)

問題の概要

解法

Rainbow Sweet Alchemist (42 solves)

問題の概要

解法

A Dance of Add and Mul (30 solves)

問題の概要

解法

Hat Trick (26 solves)

問題の概要

解法