トビタテ留学プロジェクト、完遂。
はじめに
先日、トビタテの事後研修がありまして、トビタテから支援していただいたプロジェクトは無事全てやり通せました。と言ってもトビタテ生としての活動が終わってはなく、留学エヴァンジェリストやグローバルリーダーになるという大きな宿題が残ってます。この記事では、その事後研修内で改めて気付かされたことをつらつら書いていこうと思います。真面目な文面でつまらないかもですが、どうかお付き合いを！
自己紹介
- 某私立大学院1年生。留学のために1年半休学していたので修士1年生を2年半していて、この夏休み明けに晴れて最終学年に。
- 情報セキュリティを学んでおり、生粋の理系人間。
- スポーツが好きで、ボウリングを小3からやってました。最近はプロ野球を見るために合わせたスケジュールで生きてます
- 現在はCTF(Capture The Flag)という、セキュリティの脆弱性を突いて秘匿情報を掴む、情報系謎解きみたいなものによく参加してます。ちゃんと合法です。
生い立ち
3~5歳のどこかでボウリングデビュー。そこから誕生日は必ずボウリング場に行かせろとせがむ子供になります。地元のボウリング場では小学3年生から入れるスクールがあり、小学校卒業までの4年間参加してました。勉強は得意だったつもりでしたが、小4の頃に受けた全国模試で偏差値50を切り「井の中の蛙大海を知らず」状態だったと思い知ります。そこからいつの間にか中学受験することになり、塾に通いだし、都内でボウリング部がある中学(高校まで一貫)があると知ります。なんとか合格して、6年間部活を楽しく続けました。大学でもボウリングは続けていたのですが、学部4年の時に現在の研究室の教授から留学を勧められます。
その頃には修士に進む道は決めていました。しかし、今までボウリングだけが自分の軸で、学士までは学校の教えをインプットだけで何かした実績はなく、その状態で修士の2年間を過ごして自分が社会人として働いて活躍できる土台ができるほど成長できるのか漠然とした不安がずっとありました。ボウリングで飯を食っていく気はさらさらなかったので、今後どうしようとずっと思っていました。そこで留学を勧められて、なにか変われるんじゃないかと渡米を決意。留学直前に、TOEFLで80点取らないと受入許可証が出ないとなったものの何とか出国。帰ってきて、多くの知見を得てそれを論文としてアウトプットできたのがかなり自信になり、社会人でも働いていくため頑張ろうとなっている今現在です。
英語不得意学生のTOEFL iBT初心者が80点取った勉強法 ～TOEFLについて～ - Attack All Around
留学概要
現在の研究室の教授と仲の良い、ジョージタウン大学の教授のもとへ20年3月に渡米。4月に帰国し、その後21年3月までオンラインで活動。
暗号資産(bitcoin etc)の取引の基盤になっているブロックチェーン技術と、第三者機関の信頼を必要とせず暗号資産の契約を履行するスマートコントラクトを学ぶために留学しました。ジョージタウン大学の教授はこれらのエキスパート中のエキスパートで暗号資産界隈の第一線で活躍しており、多くの技術的なことを学ぶことができました。結果として、一部の人が不当に暗号資産を失う危険性のある契約を発見することができました。
アメリカ留学始まってバタバタした話 - Attack All Around
第一回チキチキ！強制帰国レース - Attack All Around
I'll be back. - Attack All Around
本題の気付き
専門家としてやるべきこと
元々情報セキュリティの道に進んだのは、人々の生活を安全にすることに貢献したいとふんわり思っていました。そのためにもっと情報セキュリティを広める活動をすべきだとも感じました。情報セキュリティの世界では、一般ユーザの力が必要なケースがたくさんあります。例えばパスワードの設定です。技術者がいくらより良いシステムを構築したところでパスワードがずさんだと個人情報が簡単に盗まれてしまいます。「他人が予測できる意味のある文字列にはしないこと」、「よく使われる"password","qwerty"は避けること」「違う認証システムに同じパスワードを使い回ししないこと」などなどやってはいけないことは様々です。専門家が一般ユーザにこれらを伝えて広めることでより安全になるので、そういった専門家になりたいと思っていました。
しかし、事後研修で自分の留学概要をお話しさせてもらった時、ほとんどの方が自分の説明に「？？？」となっていました。自分が専門的な話を誰にでも分かりやすく説明できるスキルが欠けていることを思い知ります。目標まで全然です。改善すべき部分を知れたことは良かったので、次はこの欠点をなくせるよう動いていきます。勉強会とか開いて練習したいなと思っているので、興味のある方は越えてかけてくれると嬉しいです！！
人脈と交流の大切さ
正直なところ、9時間×2日の事後研修はつらくて集中できないと思っていました。だけど始まってみるとそんなことはなく、他のトビタテ生と議論できてかなり面白かったです。コロナ禍で人と話す機会が減っていたこともあり、会話するのが本当に楽しかったです！ それと同時に自分にとって重要な要素なんだなとも思いました。
いろんな方の意見や想いを聞くことで、自分一人ではなかなか持てない視点を理解できます。この視点を増やすことで「一を聞いて十を知る」ようになれるし、一つの物事から多くの情報や知識を知ることができて、なりたい自分に近づいていき豊かになれると思っています。人とのつながりって本当に大事と実感しました。トビタテ生になっていなければ、ここまで色んな人と仲良くなれなかったと思います。
良いパパになりたい
先程書いたなりたい自分とはこのことです。いきなり毛色が変わる話になりますが、許してください(笑)
事後研修であった3つのキーワードを選ぶ課題では、「経済的な安定、家族、知的好奇心」を選びました。知的好奇心については今まで書いたことでお分かりかなと思います。前2つについては、家族の影響が強いです。事後研修時とあるグループで、「学生の勉強はその土地に依存するのでは？」という話が持ち上がりました。首都圏に住む学生は、都内にある多くの学校に進学でき、多くの選択肢を持てる状態にあります。対して地方の場合、移動するにも鉄道があまり多くない、上京するにも親の理解や援助がないとできない、そもそも首都圏と比べ学校が少ないなどがあります。今まで関東で暮らしてきた自分にとってあまり地方のことは考えたことがなかったので反省しています。また、そこから親の経歴も関係するのでは？という流れになりました。そのグループでは親が修士に行ったから自分も行くもんだと思っていた、と自分と似た背景を持つ方がいらっしゃいました。このグループで、かなり勉強について考えさせられました。
私は家族のおかげでボウリングを何不自由なくできて、且つ自分の勉強の面倒を見てくれて…と本当にありがたい環境で育ってきました。今度は自分がその環境を作りたいと思っています。そのために、子供の可能性を広げるよう消さないよう、自分ができることをやっていきたいなと思っています。まずは、高校までの勉強を教えられるくらいにはなりたいなと思っています。塾に行かずに家で勉強について聞けて、且つ塾の先生よりも聞きやすい親だとなお捗りました。どんなことにでも対応できるよう、多くの知識といろんな角度から見れる視点を、今後身に付けていきたいなと思っています。
おわりに
前にも書きましたが、色んな人に関われるトビタテに入って本当に良かったです。これからも色んなお話をしたいので、トビタテ生の方どんどん連絡してくれると嬉しいです！突然電話かけても大丈夫なので、気兼ねなくかけてください！！
wormcon 2021 writeup
cryptoしか解いてないけど上位でした
Result
Writeup
githubに掲載できないみたいなので、問題ファイルなど直書きします。
RoboXOR 50pt
Rick got a robot named "XORius" as a gift by his parents which activates with a key, in user manual it was written - "we suggest you to use your name is X factor for ROBO ^_^" so Rick followed the user manual, his bot was working fine and now started saying
"2506110631060d103c5a15582036045b3c075734640015580d10531e0d1c134a2f"
But now Rick has fear of his parents and he wants your help to understand his ROBO
xorでしょう。keyを使い回ししていると仮定して、flagのフォーマットである"wormcon{"で各バイトをxorしてみるとkeyの長さが4でグルグル回していました。
enc = "2506110631060d103c5a15582036045b3c075734640015580d10531e0d1c134a2f" key = [] k = "wormcon{" for i in range(0,4*2,2): key.append(int(enc[i:i+2],16)^ord(k[i//2])) print(key) # [82, 105, 99, 107] flag = "" for i in range(0,len(enc),2): flag += chr(int(enc[i:i+2],16)^key[(i//2)%4]) print(flag)
wormcon{n3v3r_g0nn4_6iv3_y0u_up!}
Exclusive 100pt
SO EXCLUSIVE. MUCH ELITE. SUCH WOW.
ファイル：chall.py, out.txt
#chall.py #!/usr/bin/env python3 import os def splitit(n): return (n >> 4), (n & 0xF) def encrypt(n, key1, key2): m, l = splitit(n) e = ((m ^ key1) << 4) | (l ^ key2) return e FLAG = open('flag.txt').read().lstrip('wormcon{').rstrip('}') alpha = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_' assert all(x in alpha for x in FLAG) otp = int(os.urandom(1).hex(), 16) otpm, otpl = splitit(otp) print(f"{otp = }") cipher = [] for i,ch in enumerate(FLAG): if i % 2 == 0: enc = encrypt(ord(ch), otpm, otpl) else: enc = encrypt(ord(ch), otpl, otpm) cipher.append(enc) cipher = bytes(cipher).hex() print(f'{cipher = }') open('out.txt','w').write(f'cipher = {cipher}') # ---out.txt--- # cipher = a1adabc2b7acbbffb5ae86fee8edb1aeabc2e8a886a986f5e9f0eac2bbefeaeaeaf986fee8edb1aeab
splitit関数は、8bit値を上位4bit下位4bitに分けて返してくれます。また、encrypt関数はnをsplititで4bitに分け、前半をkey1後半をkey2でxorし、前者を上位4bit後者を下位4bitとする8bit値が返り値となります。
key1, key2はotp変数に依存し、1byteなのでbrute forceします。逆関数を作り、復元した結果が変数alphaだけで構成されているかを判別すればOKです。
def splitit(n): return (n >> 4), (n & 0xF) cipher = "a1adabc2b7acbbffb5ae86fee8edb1aeabc2e8a886a986f5e9f0eac2bbefeaeaeaf986fee8edb1aeab" alpha = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_' for otp in range(256): flag = "" otpm, otpl = splitit(otp) for i in range(0,len(cipher),2): if (i//2)%2 == 0: m = int(cipher[i],16)^otpm l = int(cipher[i+1],16)^otpl else: m = int(cipher[i],16)^otpl l = int(cipher[i+1],16)^otpm flag += chr(m*16+l) if all(x in alpha for x in flag): print("wormcon{"+flag+"}")
wormcon{x0r_n1bbl3_c1ph3r_15_4_h0m3_br3w3d_c1ph3r}
Fake Encryption 331pt
Key sizes: 56 bits Block sizes: 64 bits Rounds: 16 Designers: IBM
And you dare to say it's weak???
ファイル：chall.py, flag.png.enc, ff_error.png, ff_error.png.enc
# chall.py #!/usr/bin/env python3 from Crypto.Cipher import DES import random def splitn(text, size): return [text[i:i+size] for i in range(0,len(text),size)] def encrypt(m, key): cipher = DES.new(key, DES.MODE_ECB) return cipher.encrypt(m) flag = open('flag.png','rb').read() ff = splitn(flag, 8) assert len(flag) % 8 == 0, len(flag) key = random.randbytes(8) enc_flag = encrypt(flag, key) random.seed(ff[0]) random.shuffle(ff) ff = b''.join(ff) enc_ff = encrypt(ff, key) open('flag.png.enc', 'wb').write(enc_flag) open('ff_error.png', 'wb').write(ff) open('ff_error.png.enc', 'wb').write(enc_ff)
まず、DESは使いません。変数ffをシャッフルする際のseedがff[0]としている点に注目します。変数ffはflag.pngのバイナリデータを8byteずつ分けた値が格納されています。シャッフル後のffが与えられていますが、8byte毎の並びは変わりません。なのでその8byte毎でseedとする総当たりをします。
次にseedを取った後ですが、ffの長さと同じ配列を用意します。値はindexと同じにします。これをシャッフルします。例えば、値0がindex14に移動していたらシャッフル後のffのindex14は元々index0にあったということになります。png画像なので、index0が正しいpngフォーマットになっているかを判別し、あとはシャッフルした配列結果を基に復元します。
画像を開いてみるとflagが書いてありました。
import random f = open("ff_error.png","rb").read() print(f) #tmp = [i for i in range(len(f)//8)] print(len(f)) for i in range(0,len(f),8): tmp = [i for i in range(len(f)//8)] random.seed(f[i:i+8]) assert tmp[5] == 5 random.shuffle(tmp) #print(tmp) #print(str(i)+" : ",end="") #for j in range(4): for k in range(len(tmp)): if tmp[k] == 0: if f[8*k:8*k+8] == b'\x89PNG\r\n\x1a\n': print("find") dat = b"" for idx in range(len(f)//8): for j in range(len(tmp)): if tmp[j] == idx: dat += f[8*j:8*j+8] open('flag.png', 'wb').write(dat)
wormcon{ECB_lacks_diffiusion}
Invisible Cipher 419pt
Note: The Language used as plaintext is English.
YOU CAN'T GET THE FLAG IF YOU CAN'T SEE THE CIPHER
ファイル：chall.py, flag.enc
#chall.py #!/usr/bin/env python3 def encrypt(pt, PTALPHA, CTALPHA): ct = '' for ch in pt: i = PTALPHA.index(ch) ct += CTALPHA[i] return ct PTALPHA = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ ' CTALPHA = open('CTALPHA.txt').read().strip() FLAG = open('flag.txt').read().strip() assert len(CTALPHA) == len(PTALPHA) assert all(x in PTALPHA for x in FLAG) enc_flag = encrypt(FLAG, PTALPHA, CTALPHA) with open('flag.enc','w') as f: f.write(enc_flag) print('DONE')
ぃ〷〴ぁ〴おう〰あお〾〽〲〴お〰お〺〸〽〶お〾〵おあ〲〾ぃ〻〰〽〳おう〷〾あ〴お〽〰〼〴おう〰あおぁ〾〱〴ぁぃお〱ぁい〲〴お〷〴お〷〰〳お〽〴〴〳おぃ〾お〱〴お〱〾ぃ〷お〱ぁ〰ぅ〴お〰〽〳おう〸あ〴お〵〾ぁおぃ〷〴おぃ〸〼〴あお〸〽おう〷〸〲〷お〷〴お〻〸ぅ〴〳おう〴ぁ〴おう〸〻〳お〰〽〳おぁい〳〴おぃ〷〴お〺〸〽〶お〾〵お〴〽〶〻〰〽〳おう〰あお〰ぃおう〰ぁおう〸ぃ〷お〷〸〼お〰〽〳お〷〰〳お〻〴〳お〰お〶ぁ〴〰ぃお〰ぁ〼えお〸〽ぃ〾おあ〲〾ぃ〻〰〽〳おぃ〾お〳ぁ〸ぅ〴お〷〸〼お〾いぃお〾〵おぃ〷〴お〻〰〽〳お〱〰ぃぃ〻〴お〰〵ぃ〴ぁお〱〰ぃぃ〻〴お〷〰〳お〱〴〴〽お〵〾い〶〷ぃおあ〸ぇおぃ〸〼〴あお〷〰〳お〱ぁい〲〴お〻〴〳お〷〸あお〱ぁ〰ぅ〴お〻〸ぃぃ〻〴お〰ぁ〼えお〰〶〰〸〽あぃお〷〸あお〵〾〴あお〰〽〳おあ〸ぇおぃ〸〼〴あお〷〰〳お〷〸あお〼〴〽お〱〴〴〽お〱〴〰ぃ〴〽お〰〽〳お〳ぁ〸ぅ〴〽お〸〽ぃ〾お〵〻〸〶〷ぃお〰ぃお〻〰あぃお〷〸あお〰ぁ〼えおう〰あおあ〲〰ぃぃ〴ぁ〴〳お〰〽〳お〷〴おう〰あお〵〾ぁ〲〴〳おぃ〾お〷〸〳〴お〷〸〼あ〴〻〵お〸〽おぃ〷〴おう〾〾〳あお〰〽〳お〸〽お〻〾〽〴〻えお〿〻〰〲〴あお〰〼〾〽〶おぃ〷〴お〼〾い〽ぃ〰〸〽あお〾〽 〴おぁ〰〸〽えお〳〰えお〱ぁい〲〴お〻〰えお〾〽おぃ〷〴お〶ぁ〾い〽〳おい〽〳〴ぁお〰おぁい〳〴おあ〷〴〳お〻〸あぃ〴〽〸〽〶おぃ〾おぃ〷〴お〿〰ぃぃ〴ぁお〾〵おぃ〷〴お〳ぁ〾〿あお〾〽おぃ〷〴おぁ〾〾〵お〰〱〾ぅ〴お〷〸〼お〷〴おう〰あおぃ〸ぁ〴〳お〰〽〳おあ〸〲〺お〰ぃお〷〴〰ぁぃお〰〽〳おぁ〴〰〳えおぃ〾お〶〸ぅ〴おい〿お〰〻〻お〷〾〿〴お〸ぃおあ〴〴〼〴〳おぃ〾お〷〸〼おぃ〷〰ぃおぃ〷〴ぁ〴おう〰あお〽〾おいあ〴お〵〾ぁお〷〸〼おぃ〾おぃぁえおぃ〾お〳〾お〰〽えぃ〷〸〽〶お〼〾ぁ〴お〰あお〷〴お〻〰えおぃ〷〸〽〺〸〽〶お〷〴おあ〰うお〰おあ〿〸〳〴ぁお〾ぅ〴ぁお〷〸あお〷〴〰〳お〼〰〺〸〽 〶おぁ〴〰〳えおぃ〾おう〴〰ぅ〴お〷〴ぁおう〴〱お〷〴おう〰ぃ〲〷〴〳お〷〴ぁお〰あおあ〷〴おぃ〾〸〻〴〳おあ〻〾う〻えお〰〽〳おう〸ぃ〷お〶ぁ〴〰ぃお〲〰ぁ〴おあ〸ぇおぃ〸〼〴あおあ〷〴おぃぁ〸〴〳おぃ〾おぃ〷ぁ〾うお〷〴ぁお〵ぁ〰〸〻おぃ〷ぁ〴〰〳お〵ぁ〾〼お〾〽〴お〱〴〰〼おぃ〾お〰〽〾ぃ〷〴ぁお〰〽〳おあ〸ぇおぃ〸〼〴あお〸ぃお〵〴〻〻おあ〷〾ぁぃお〿〾〾ぁおぃ〷〸〽〶おあ〰〸〳お〱ぁい〲〴おえ〾いおぃ〾〾お〺〽〾うおう〷〰ぃお〸ぃお〸あおぃ〾お〵〰〸〻お〱いぃおぃ〷 〴おあ〿〸〳〴ぁお〳〸〳お〽〾ぃお〻〾あ〴お〷〾〿〴おう〸ぃ〷おぃ〷〴おあ〸ぇぃ〷お〵〰〸〻いぁ〴おう〸ぃ〷おあぃ〸〻〻お〼〾ぁ〴お〲〰ぁ〴おあ〷〴お〼〰〳〴おぁ〴〰〳えおぃ〾おぃぁえお〵〾ぁおぃ〷〴おあ〴ぅ〴〽ぃ〷おぃ〸〼〴お〱ぁい〲〴お〰〻〼〾あぃお〵〾ぁ〶〾ぃお〷〸あお〾う〽おぃぁ〾い〱〻〴あお〰あお〷〴おう〰ぃ〲〷〴〳お〷〴ぁおあう〸〽〶お〷〴ぁあ〴〻〵お〾いぃおい〿〾〽おぃ〷〴おあ〻〴〽〳〴ぁお〻〸〽〴おう〾い〻〳おあ〷〴お〵〰〸〻お〰〶〰〸〽お〽〾おぃ〷〴おぃ〷ぁ〴 〰〳おう〰あお〲〰ぁぁ〸〴〳おあ〰〵〴〻えおぃ〾おぃ〷〴お〱〴〰〼お〰〽〳お〵〰あぃ〴〽〴〳おぃ〷〴ぁ〴お〸おぃ〾〾おう〸〻〻おぃぁえお〰おあ〴ぅ〴〽ぃ〷おぃ〸〼〴お〲ぁ〸〴〳お〱ぁい〲〴お〷〴お〰ぁ〾あ〴お〰〽〳お〲〰〻〻〴〳お〷〸あお〼〴〽おぃ〾〶〴ぃ〷〴ぁお〷〴おぃ〾〻〳おぃ〷〴〼お〾〵お〷〸あお〿〻〰〽あお〰〽〳おあ〴〽ぃおぃ〷〴〼お〾いぃおう〸ぃ〷 お〼〴ああ〰〶〴あお〾〵お〲〷〴〴ぁおぃ〾お〷〸あお〳〸あ〷〴〰ぁぃ〴〽〴〳お〿〴〾〿〻〴おあ〾〾〽おぃ〷〴ぁ〴おう〰あお〰〽お〰ぁ〼えお〾〵お〱ぁ〰ぅ〴おあ〲〾ぃ〲〷〼〴〽お〰ぁ〾い〽〳お〷〸〼お〰〽〾ぃ〷〴ぁお〱〰ぃぃ〻〴おう〰あお〵〾い〶〷ぃお〰〽〳おぃ〷〴お〺〸〽〶お〾〵お〴〽〶〻〰〽〳おう〰あお〶〻〰〳おぃ〾お〶〾お〱〰〲〺お〸〽ぃ〾お〷〸あお〾う〽お〲〾い〽ぃぁえお〸お〷〰ぅ〴お〷〴〰ぁ〳お〸ぃおあ〰〸〳おぃ〷〰ぃお〰〵ぃ〴ぁおぃ〷〰ぃお〳〰えお〽〾お〾〽〴お〱えおぃ〷〴お〽〰〼〴お〾〵お〱ぁい〲〴おう〾い〻〳お〴ぅ〴ぁお〷いぁぃお〰おあ〿〸〳〴ぁおぃ〷〴お〻〴ああ〾〽おう〷〸〲〷お ぃ〷〴お〻〸ぃぃ〻〴お〲ぁ〴〰ぃいぁ〴お〷〰〳おぃ〰い〶〷ぃおぃ〷〴お〺〸〽〶おう〰あお〽〴ぅ〴ぁお〵〾ぁ〶〾ぃぃ〴〽お〷〴おぃ〾〻〳おいあおぃ〷〴お〵〻〰〶おう〰あお〲〰ぁ〴〵い〻お〵ぁ〴い〴〽〲えお〰〽〰〻えあ〸あお〱ぁ〴〰〺あおあい 〱あぃ〸ぃいぃ〸〾〽お〲〸〿〷〴ぁお〷〴お〰〻あ〾おあい〶〶〴あぃあおぃ〷〴おいあ〴ぁおぃ〾お〹〾〸〽おぃ〷〴おう〾ぁ〳 あおう〸ぃ〷おい〽〳〴ぁあ〲〾ぁ〴お〰〽〳お〿いぃおぃ〷〴おぁ〴あい〻ぃお〸〽おぃ〷〴お〵〻〰〶おうぁ〰〿〿〴ぁお〱〴〵〾 ぁ〴おあい〱〼〸ああ〸〾〽
まず1文字ずつordして値を確認します。
[12355, 12343, 12340, 12353, 12340, 12362, 12358, 12336, 12354, 12362, 12350, 12349, 12338, 12340, 12362, 12336, 12362, 12346, 12344, 12349, 12342, 12362, 12350, 12341, 12362, 12354, 12338, 12350, 12355, 12347, 12336, 12349, 12339, 12362, 12358, 12343, 12350, 12354, 12340, 12362, 12349, 12336, 12348, 12340, 12362, 12358, 12336, 12354, 12362, 12353, 12350, 12337, 12340, 12353, 12355, 12362, 12337, 12353, 12356, 12338, 12340, 12362, 12343, 12340, 12362, 12343, 12336, 12339, 12362, 12349, 12340, 12340, 12339, 12362, 12355, 12350, 12362, 12337, 12340, 12362, 12337, 12350, 12355, 12343, 12362, 12337, 12353, 12336, 12357, 12340, 12362, 12336, 12349, 12339, 12362, 12358, 12344, 12354, 12340, 12362, 12341, 12350, 12353, 12362, 12355, 12343, 12340, 12362, 12355, 12344, 12348, 12340, 12354, 12362, 12344, 12349, 12362, 12358, 12343, 12344, 12338, 12343, 12362, 12343, 12340, 12362, 12347, 12344, 12357, 12340, 12339, 12362, 12358, 12340, 12353, 12340, 12362, 12358, 12344, 12347, 12339, 12362, 12336, 12349, 12339, 12362, 12353, 12356, 12339, 12340, 12362, 12355, 12343, 12340, 12362, 12346, 12344, 12349, 12342, 12362, 12350, 12341, 12362, 12340, 12349, 12342, 12347, 12336, 12349, 12339, 12362, 12358, 12336, 12354, 12362, 12336, 12355, 12362, 12358, 12336, 12353, 12362, 12358, 12344, 12355, 12343, 12362, 12343, 12344, 12348, 12362, 12336, 12349, 12339, 12362, 12343, 12336, 12339, 12362, 12347, 12340, 12339, 12362, 12336, 12362, 12342, 12353, 12340, 12336, 12355, 12362, 12336, 12353, 12348, 12360, 12362, 12344, 12349, 12355, 12350, 12362, 12354, 12338, 12350, 12355, 12347, 12336, 12349, 12339, 12362, 12355, 12350, 12362, 12339, 12353, 12344, 12357, 12340, 12362, 12343, 12344, 12348, 12362, 12350, 12356, 12355, 12362, 12350, 12341, 12362, 12355, 12343, 12340, 12362, 12347, 12336, 12349, 12339, 12362, 12337, 12336, 12355, 12355, 12347, 12340, 12362, 12336, 12341, 12355, 12340, 12353, 12362, 12337, 12336, 12355, 12355, 12347, 12340, 12362, 12343, 12336, 12339, 12362, 12337, 12340, 12340, 12349, 12362, 12341, 12350, 12356, 12342, 12343, 12355, 12362, 12354, 12344, 12359, 12362, 12355, 12344, 12348, 12340, 12354, 12362, 12343, 12336, 12339, 12362, 12337, 12353, 12356, 12338, 12340, 12362, 12347, 12340, 12339, 12362, 12343, 12344, 12354, 12362, 12337, 12353, 12336, 12357, 12340, 12362, 12347, 12344, 12355, 12355, 12347, 12340, 12362, 12336, 12353, 12348, 12360, 12362, 12336, 12342, 12336, 12344, 12349, 12354, 12355, 12362, 12343, 12344, 12354, 12362, 12341, 12350, 12340, 12354, 12362, 12336, 12349, 12339, 12362, 12354, 12344, 12359, 12362, 12355, 12344, 12348, 12340, 12354, 12362, 12343, 12336, 12339, 12362, 12343, 12344, 12354, 12362, 12348, 12340, 12349, 12362, 12337, 12340, 12340, 12349, 12362, 12337, 12340, 12336, 12355, 12340, 12349, 12362, 12336, 12349, 12339, 12362, 12339, 12353, 12344, 12357, 12340, 12349, 12362, 12344, 12349, 12355, 12350, 12362, 12341, 12347, 12344, 12342, 12343, 12355, 12362, 12336, 12355, 12362, 12347, 12336, 12354, 12355, 12362, 12343, 12344, 12354, 12362, 12336, 12353, 12348, 12360, 12362, 12358, 12336, 12354, 12362, 12354, 12338, 12336, 12355, 12355, 12340, 12353, 12340, 12339, 12362, 12336, 12349, 12339, 12362, 12343, 12340, 12362, 12358, 12336, 12354, 12362, 12341, 12350, 12353, 12338, 12340, 12339, 12362, 12355, 12350, 12362, 12343, 12344, 12339, 12340, 12362, 12343, 12344, 12348, 12354, 12340, 12347, 12341, 12362, 12344, 12349, 12362, 12355, 12343, 12340, 12362, 12358, 12350, 12350, 12339, 12354, 12362, 12336, 12349, 12339, 12362, 12344, 12349, 12362, 12347, 12350, 12349, 12340, 12347, 12360, 12362, 12351, 12347, 12336, 12338, 12340, 12354, 12362, 12336, 12348, 12350, 12349, 12342, 12362, 12355, 12343, 12340, 12362, 12348, 12350, 12356, 12349, 12355, 12336, 12344, 12349, 12354, 12362, 12350, 12349, 12340, 12362, 12353, 12336, 12344, 12349, 12360, 12362, 12339, 12336, 12360, 12362, 12337, 12353, 12356, 12338, 12340, 12362, 12347, 12336, 12360, 12362, 12350, 12349, 12362, 12355, 12343, 12340, 12362, 12342, 12353, 12350, 12356, 12349, 12339, 12362, 12356, 12349, 12339, 12340, 12353, 12362, 12336, 12362, 12353, 12356, 12339, 12340, 12362, 12354, 12343, 12340, 12339, 12362, 12347, 12344, 12354, 12355, 12340, 12349, 12344, 12349, 12342, 12362, 12355, 12350, 12362, 12355, 12343, 12340, 12362, 12351, 12336, 12355, 12355, 12340, 12353, 12362, 12350, 12341, 12362, 12355, 12343, 12340, 12362, 12339, 12353, 12350, 12351, 12354, 12362, 12350, 12349, 12362, 12355, 12343, 12340, 12362, 12353, 12350, 12350, 12341, 12362, 12336, 12337, 12350, 12357, 12340, 12362, 12343, 12344, 12348, 12362, 12343, 12340, 12362, 12358, 12336, 12354, 12362, 12355, 12344, 12353, 12340, 12339, 12362, 12336, 12349, 12339, 12362, 12354, 12344, 12338, 12346, 12362, 12336, 12355, 12362, 12343, 12340, 12336, 12353, 12355, 12362, 12336, 12349, 12339, 12362, 12353, 12340, 12336, 12339, 12360, 12362, 12355, 12350, 12362, 12342, 12344, 12357, 12340, 12362, 12356, 12351, 12362, 12336, 12347, 12347, 12362, 12343, 12350, 12351, 12340, 12362, 12344, 12355, 12362, 12354, 12340, 12340, 12348, 12340, 12339, 12362, 12355, 12350, 12362, 12343, 12344, 12348, 12362, 12355, 12343, 12336, 12355, 12362, 12355, 12343, 12340, 12353, 12340, 12362, 12358, 12336, 12354, 12362, 12349, 12350, 12362, 12356, 12354, 12340, 12362, 12341, 12350, 12353, 12362, 12343, 12344, 12348, 12362, 12355, 12350, 12362, 12355, 12353, 12360, 12362, 12355, 12350, 12362, 12339, 12350, 12362, 12336, 12349, 12360, 12355, 12343, 12344, 12349, 12342, 12362, 12348, 12350, 12353, 12340, 12362, 12336, 12354, 12362, 12343, 12340, 12362, 12347, 12336, 12360, 12362, 12355, 12343, 12344, 12349, 12346, 12344, 12349, 12342, 12362, 12343, 12340, 12362, 12354, 12336, 12358, 12362, 12336, 12362, 12354, 12351, 12344, 12339, 12340, 12353, 12362, 12350, 12357, 12340, 12353, 12362, 12343, 12344, 12354, 12362, 12343, 12340, 12336, 12339, 12362, 12348, 12336, 12346, 12344, 12349, 12342, 12362, 12353, 12340, 12336, 12339, 12360, 12362, 12355, 12350, 12362, 12358, 12340, 12336, 12357, 12340, 12362, 12343, 12340, 12353, 12362, 12358, 12340, 12337, 12362, 12343, 12340, 12362, 12358, 12336, 12355, 12338, 12343, 12340, 12339, 12362, 12343, 12340, 12353, 12362, 12336, 12354, 12362, 12354, 12343, 12340, 12362, 12355, 12350, 12344, 12347, 12340, 12339, 12362, 12354, 12347, 12350, 12358, 12347, 12360, 12362, 12336, 12349, 12339, 12362, 12358, 12344, 12355, 12343, 12362, 12342, 12353, 12340, 12336, 12355, 12362, 12338, 12336, 12353, 12340, 12362, 12354, 12344, 12359, 12362, 12355, 12344, 12348, 12340, 12354, 12362, 12354, 12343, 12340, 12362, 12355, 12353, 12344, 12340, 12339, 12362, 12355, 12350, 12362, 12355, 12343, 12353, 12350, 12358, 12362, 12343, 12340, 12353, 12362, 12341, 12353, 12336, 12344, 12347, 12362, 12355, 12343, 12353, 12340, 12336, 12339, 12362, 12341, 12353, 12350, 12348, 12362, 12350, 12349, 12340, 12362, 12337, 12340, 12336, 12348, 12362, 12355, 12350, 12362, 12336, 12349, 12350, 12355, 12343, 12340, 12353, 12362, 12336, 12349, 12339, 12362, 12354, 12344, 12359, 12362, 12355, 12344, 12348, 12340, 12354, 12362, 12344, 12355, 12362, 12341, 12340, 12347, 12347, 12362, 12354, 12343, 12350, 12353, 12355, 12362, 12351, 12350, 12350, 12353, 12362, 12355, 12343, 12344, 12349, 12342, 12362, 12354, 12336, 12344, 12339, 12362, 12337, 12353, 12356, 12338, 12340, 12362, 12360, 12350, 12356, 12362, 12355, 12350, 12350, 12362, 12346, 12349, 12350, 12358, 12362, 12358, 12343, 12336, 12355, 12362, 12344, 12355, 12362, 12344, 12354, 12362, 12355, 12350, 12362, 12341, 12336, 12344, 12347, 12362, 12337, 12356, 12355, 12362, 12355, 12343, 12340, 12362, 12354, 12351, 12344, 12339, 12340, 12353, 12362, 12339, 12344, 12339, 12362, 12349, 12350, 12355, 12362, 12347, 12350, 12354, 12340, 12362, 12343, 12350, 12351, 12340, 12362, 12358, 12344, 12355, 12343, 12362, 12355, 12343, 12340, 12362, 12354, 12344, 12359, 12355, 12343, 12362, 12341, 12336, 12344, 12347, 12356, 12353, 12340, 12362, 12358, 12344, 12355, 12343, 12362, 12354, 12355, 12344, 12347, 12347, 12362, 12348, 12350, 12353, 12340, 12362, 12338, 12336, 12353, 12340, 12362, 12354, 12343, 12340, 12362, 12348, 12336, 12339, 12340, 12362, 12353, 12340, 12336, 12339, 12360, 12362, 12355, 12350, 12362, 12355, 12353, 12360, 12362, 12341, 12350, 12353, 12362, 12355, 12343, 12340, 12362, 12354, 12340, 12357, 12340, 12349, 12355, 12343, 12362, 12355, 12344, 12348, 12340, 12362, 12337, 12353, 12356, 12338, 12340, 12362, 12336, 12347, 12348, 12350, 12354, 12355, 12362, 12341, 12350, 12353, 12342, 12350, 12355, 12362, 12343, 12344, 12354, 12362, 12350, 12358, 12349, 12362, 12355, 12353, 12350, 12356, 12337, 12347, 12340, 12354, 12362, 12336, 12354, 12362, 12343, 12340, 12362, 12358, 12336, 12355, 12338, 12343, 12340, 12339, 12362, 12343, 12340, 12353, 12362, 12354, 12358, 12344, 12349, 12342, 12362, 12343, 12340, 12353, 12354, 12340, 12347, 12341, 12362, 12350, 12356, 12355, 12362, 12356, 12351, 12350, 12349, 12362, 12355, 12343, 12340, 12362, 12354, 12347, 12340, 12349, 12339, 12340, 12353, 12362, 12347, 12344, 12349, 12340, 12362, 12358, 12350, 12356, 12347, 12339, 12362, 12354, 12343, 12340, 12362, 12341, 12336, 12344, 12347, 12362, 12336, 12342, 12336, 12344, 12349, 12362, 12349, 12350, 12362, 12355, 12343, 12340, 12362, 12355, 12343, 12353, 12340, 12336, 12339, 12362, 12358, 12336, 12354, 12362, 12338, 12336, 12353, 12353, 12344, 12340, 12339, 12362, 12354, 12336, 12341, 12340, 12347, 12360, 12362, 12355, 12350, 12362, 12355, 12343, 12340, 12362, 12337, 12340, 12336, 12348, 12362, 12336, 12349, 12339, 12362, 12341, 12336, 12354, 12355, 12340, 12349, 12340, 12339, 12362, 12355, 12343, 12340, 12353, 12340, 12362, 12344, 12362, 12355, 12350, 12350, 12362, 12358, 12344, 12347, 12347, 12362, 12355, 12353, 12360, 12362, 12336, 12362, 12354, 12340, 12357, 12340, 12349, 12355, 12343, 12362, 12355, 12344, 12348, 12340, 12362, 12338, 12353, 12344, 12340, 12339, 12362, 12337, 12353, 12356, 12338, 12340, 12362, 12343, 12340, 12362, 12336, 12353, 12350, 12354, 12340, 12362, 12336, 12349, 12339, 12362, 12338, 12336, 12347, 12347, 12340, 12339, 12362, 12343, 12344, 12354, 12362, 12348, 12340, 12349, 12362, 12355, 12350, 12342, 12340, 12355, 12343, 12340, 12353, 12362, 12343, 12340, 12362, 12355, 12350, 12347, 12339, 12362, 12355, 12343, 12340, 12348, 12362, 12350, 12341, 12362, 12343, 12344, 12354, 12362, 12351, 12347, 12336, 12349, 12354, 12362, 12336, 12349, 12339, 12362, 12354, 12340, 12349, 12355, 12362, 12355, 12343, 12340, 12348, 12362, 12350, 12356, 12355, 12362, 12358, 12344, 12355, 12343, 12362, 12348, 12340, 12354, 12354, 12336, 12342, 12340, 12354, 12362, 12350, 12341, 12362, 12338, 12343, 12340, 12340, 12353, 12362, 12355, 12350, 12362, 12343, 12344, 12354, 12362, 12339, 12344, 12354, 12343, 12340, 12336, 12353, 12355, 12340, 12349, 12340, 12339, 12362, 12351, 12340, 12350, 12351, 12347, 12340, 12362, 12354, 12350, 12350, 12349, 12362, 12355, 12343, 12340, 12353, 12340, 12362, 12358, 12336, 12354, 12362, 12336, 12349, 12362, 12336, 12353, 12348, 12360, 12362, 12350, 12341, 12362, 12337, 12353, 12336, 12357, 12340, 12362, 12354, 12338, 12350, 12355, 12338, 12343, 12348, 12340, 12349, 12362, 12336, 12353, 12350, 12356, 12349, 12339, 12362, 12343, 12344, 12348, 12362, 12336, 12349, 12350, 12355, 12343, 12340, 12353, 12362, 12337, 12336, 12355, 12355, 12347, 12340, 12362, 12358, 12336, 12354, 12362, 12341, 12350, 12356, 12342, 12343, 12355, 12362, 12336, 12349, 12339, 12362, 12355, 12343, 12340, 12362, 12346, 12344, 12349, 12342, 12362, 12350, 12341, 12362, 12340, 12349, 12342, 12347, 12336, 12349, 12339, 12362, 12358, 12336, 12354, 12362, 12342, 12347, 12336, 12339, 12362, 12355, 12350, 12362, 12342, 12350, 12362, 12337, 12336, 12338, 12346, 12362, 12344, 12349, 12355, 12350, 12362, 12343, 12344, 12354, 12362, 12350, 12358, 12349, 12362, 12338, 12350, 12356, 12349, 12355, 12353, 12360, 12362, 12344, 12362, 12343, 12336, 12357, 12340, 12362, 12343, 12340, 12336, 12353, 12339, 12362, 12344, 12355, 12362, 12354, 12336, 12344, 12339, 12362, 12355, 12343, 12336, 12355, 12362, 12336, 12341, 12355, 12340, 12353, 12362, 12355, 12343, 12336, 12355, 12362, 12339, 12336, 12360, 12362, 12349, 12350, 12362, 12350, 12349, 12340, 12362, 12337, 12360, 12362, 12355, 12343, 12340, 12362, 12349, 12336, 12348, 12340, 12362, 12350, 12341, 12362, 12337, 12353, 12356, 12338, 12340, 12362, 12358, 12350, 12356, 12347, 12339, 12362, 12340, 12357, 12340, 12353, 12362, 12343, 12356, 12353, 12355, 12362, 12336, 12362, 12354, 12351, 12344, 12339, 12340, 12353, 12362, 12355, 12343, 12340, 12362, 12347, 12340, 12354, 12354, 12350, 12349, 12362, 12358, 12343, 12344, 12338, 12343, 12362, 12355, 12343, 12340, 12362, 12347, 12344, 12355, 12355, 12347, 12340, 12362, 12338, 12353, 12340, 12336, 12355, 12356, 12353, 12340, 12362, 12343, 12336, 12339, 12362, 12355, 12336, 12356, 12342, 12343, 12355, 12362, 12355, 12343, 12340, 12362, 12346, 12344, 12349, 12342, 12362, 12358, 12336, 12354, 12362, 12349, 12340, 12357, 12340, 12353, 12362, 12341, 12350, 12353, 12342, 12350, 12355, 12355, 12340, 12349, 12362, 12343, 12340, 12362, 12355, 12350, 12347, 12339, 12362, 12356, 12354, 12362, 12355, 12343, 12340, 12362, 12341, 12347, 12336, 12342, 12362, 12358, 12336, 12354, 12362, 12338, 12336, 12353, 12340, 12341, 12356, 12347, 12362, 12341, 12353, 12340, 12352, 12356, 12340, 12349, 12338, 12360, 12362, 12336, 12349, 12336, 12347, 12360, 12354, 12344, 12354, 12362, 12337, 12353, 12340, 12336, 12346, 12354, 12362, 12354, 12356, 12337, 12354, 12355, 12344, 12355, 12356, 12355, 12344, 12350, 12349, 12362, 12338, 12344, 12351, 12343, 12340, 12353, 12362, 12343, 12340, 12362, 12336, 12347, 12354, 12350, 12362, 12354, 12356, 12342, 12342, 12340, 12354, 12355, 12354, 12362, 12355, 12343, 12340, 12362, 12356, 12354, 12340, 12353, 12362, 12355, 12350, 12362, 12345, 12350, 12344, 12349, 12362, 12355, 12343, 12340, 12362, 12358, 12350, 12353, 12339, 12354, 12362, 12358, 12344, 12355, 12343, 12362, 12356, 12349, 12339, 12340, 12353, 12354, 12338, 12350, 12353, 12340, 12362, 12336, 12349, 12339, 12362, 12351, 12356, 12355, 12362, 12355, 12343, 12340, 12362, 12353, 12340, 12354, 12356, 12347, 12355, 12362, 12344, 12349, 12362, 12355, 12343, 12340, 12362, 12341, 12347, 12336, 12342, 12362, 12358, 12353, 12336, 12351, 12351, 12340, 12353, 12362, 12337, 12340, 12341, 12350, 12353, 12340, 12362, 12354, 12356, 12337, 12348, 12344, 12354, 12354, 12344, 12350, 12349]
これは換字式暗号ですね。この数値のどれかが空白となり、それ以外はテキトーなアルファベットを当てはめます。数値が同じなら同じアルファベットになるようにします。
全ての数値に対して空白にしたとき、明らかに長すぎる単語が出てきたものは無視します。
ABCDC EFG HIJC F KLIM HN GJHAOFIP
最初が"THERE ARE"ぽいです(違うけど)。これをquipquipに投げて完了です。
THERE WAS ONCE A KING OF SCOTLAND WHOSE NAME WAS ROBERT BRUCE HE HAD NEED TO BE BOTH BRAVE AND WISE FOR THE TIMES IN WHICH HE LIVED WERE WILD AND RUDE THE KING OF ENGLAND WAS AT WAR WITH HIM AND HAD LED A GREAT ARMY INTO SCOTLAND TO DRIVE HIM OUT OF THE LAND BATTLE AFTER BATTLE HAD BEEN FOUGHT SIX TIMES HAD BRUCE LED HIS BRAVE LITTLE ARMY AGAINST HIS FOES AND SIX TIMES HAD HIS MEN BEEN BEATEN AND DRIVEN INTO FLIGHT AT LAST HIS ARMY WAS SCATTERED AND HE WAS FORCED TO HIDE HIMSELF IN THE WOODS AND IN LONELY PLACES AMONG THE MOUNTAINS ONE RAINY DAY BRUCE LAY ON THE GROUND UNDER A RUDE SHED LISTENING TO THE PATTER OF THE DROPS ON THE ROOF ABOVE HIM HE WAS TIRED AND SICK AT HEART AND READY TO GIVE UP ALL HOPE IT SEEMED TO HIM THAT THERE WAS NO USE FOR HIM TO TRY TO DO ANYTHING MORE AS HE LAY THINKING HE SAW A SPIDER OVER HIS HEAD MAKING READY TO WEAVE HER WEB HE WATCHED HER AS SHE TOILED SLOWLY AND WITH GREAT CARE SIX TIMES SHE TRIED TO THROW HER FRAIL THREAD FROM ONE BEAM TO ANOTHER AND SIX TIMES IT FELL SHORT POOR THING SAID BRUCE YOU TOO KNOW WHAT IT IS TO FAIL BUT THE SPIDER DID NOT LOSE HOPE WITH THE SIXTH FAILURE WITH STILL MORE CARE SHE MADE READY TO TRY FOR THE SEVENTH TIME BRUCE ALMOST FORGOT HIS OWN TROUBLES AS HE WATCHED HER SWING HERSELF OUT UPON THE SLENDER LINE WOULD SHE FAIL AGAIN NO THE THREAD WAS CARRIED SAFELY TO THE BEAM AND FASTENED THERE I TOO WILL TRY A SEVENTH TIME CRIED BRUCE HE AROSE AND CALLED HIS MEN TOGETHER HE TOLD THEM OF HIS PLANS AND SENT THEM OUT WITH MESSAGES OF CHEER TO HIS DISHEARTENED PEOPLE SOON THERE WAS AN ARMY OF BRAVE SCOTCHMEN AROUND HIM ANOTHER BATTLE WAS FOUGHT AND THE KING OF ENGLAND WAS GLAD TO GO BACK INTO HIS OWN COUNTRY I HAVE HEARD IT SAID THAT AFTER THAT DAY NO ONE BY THE NAME OF BRUCE WOULD EVER HURT A SPIDER THE LESSON WHICH THE LITTLE CREATURE HAD TAUGHT THE KING WAS NEVER FORGOTTEN HE TOLD US THE FLAG WAS CAREFUL FREQUENCY ANALYSIS BREAKS SUBSTITUTION CIPHER HE ALSO SUGGESTS THE USER TO JOIN THE WORDS WITH UNDERSCORE AND PUT THE RESULT IN THE FLAG WRAPPER BEFORE SUBMISSION
Heritage History | Fifty Famous Stories Retold by James Baldwin
これですね。
HE TOLD US THE FLAG WAS CAREFUL FREQUENCY ANALYSIS BREAKS SUBSTITUTION CIPHER HE ALSO SUGGESTS THE USER TO JOIN THE WORDS WITH UNDERSCORE AND PUT THE RESULT IN THE FLAG WRAPPER BEFORE SUBMISSION
とあるのですが、flagが分からない…。この文章のタイトルかと思ったら違いました。結局これでした。
wormcon{CAREFUL_FREQUENCY_ANALYSIS_BREAKS_SUBSTITUTION_CIPHER}
Rem, Shinobu, Asuna 475pt
I thought RSA means Rem, Shinobu and Asuna!!!
ファイル：chall.py, out.txt
#!/usr/bin/env python3 from Crypto.Util.number import * FLAG = open('flag.txt', 'rb').read() bits = 512 e = 65537 p = getPrime(bits) q = getPrime(bits) n = p*q phi = (p-1)*(q-1) d = inverse(e, phi) hint = 2*d*(p-1337) m = bytes_to_long(FLAG) c = pow(m, e, n) print(f"n = {hex(n)}") print(f"e = {hex(e)}") print(f"c = {hex(c)}") print(f"hint = {hex(hint)}") # ---out.txt --- # n = 0xced9347557a5d6f88e3a506517ad051aff9c1a2ee8a1ac27f3dd74c58ac1c5bc2e2ba7ae2aba617497c5204d3933d9a941cf9af61d8308d760cad984567fa725f35510f6944dce3306687b49138c1eda555cd1f1a0c5fbf10b47ca0aa2afca13083a02f59281a2087d8b277fa43ad187dbc84d37f276c997b9ed456c1601256d # e = 0x10001 # c = 0xd5d4bc7f461ab02dddb1c3d911bfeee35837a787b02f09d45f5c29e122d784bf5ee97e1ace3a320130fb8747c40292a8503613b674280ab7b64163e9a2ab8a39dfba55d2032d67f1d3fe6389881f8c4145c5b7eb8d83caaa6ebebad021f668a83434d7d48a249f5e8e23828b1aa9402c8b88eab9c48e035a9997bdcc4b48479 # hint = 0x7acdc2f1c0acd1fb471f7804a984b962206babbbc8aba1c6a06757b1a10ba3941e5d9d5a1f19b8d9ed9facb48f8f0beda5366ed62c77303a5749e96f1cb820fd0d4d4e7ac1fc15207ae36f9a5aa0fdd9240605277d5ba51dee5075186fbea7340a5b2d09d82e025485ecedd7c505265e81c57db7ce72e722c0179f71669413c54fced2b3663b2171e38554d00e876c67b5d221bea6b1c7345fe1ae024ffdd72afd12f79522ac96932f6505d9ce8e7abad89182bcb7911b6a1dc7054c7a42b304
紆余曲折ありましたが、結果としては以下のa, bを求めることです。
a = k(p-1) + b (k : 整数)
適当な整数xを持ってきます。ここで、xa - xb = 0 mod p となり、左辺はpの倍数となります。フェルマーの小定理 (xp-1 = 1 mod p) を使えばこのように変形できます。
xa = xk(p-1) + b = xk(p-1) × xb mod p
では、a,bを求めていきます。
hint = 2*d*(p-1337) e*hint = 2*e*d*(p-1337) e*d = k(p-1)(q-1)+1 (k : 整数)より e*hint = 2*(k(p-1)(q-1)+1)*(p-1337) )= 2k(p-1)(q-1)(p-1337)+2(p-1337) = 2k(p-1)(q-1)(p-1337)+2(p-1)-2672
ゆえに、a = e*hint, b = -2672 が分かりました。xe*hint - x-2672 はpの倍数となります。nとgcdとれば素因数分解できます。
from Crypto.Util.number import * import math,random n = (中略) e = (中略) c = (中略) hint = (中略) m = random.randrange(n) c1 = pow(m,e*hint,n) c2 = pow(m,1336*2,n) c2 = inverse(c2,n) print(c1) print(c2) p = math.gcd(c1-c2,n) q = n//p phi = (p-1)*(q-1) d = inverse(e,phi) m = pow(c,d,n) print(long_to_bytes(m))
wormcon{RSA_And_Fermat's_Little_Theorem!?}
Sir Oracle 484pt
"I am Sir Oracle,. And when I ope my lips, let no dog bark!"
nc 34.83.246.93 8000
ファイル：server.py
# server.py #!/usr/bin/env python3 from Crypto.Util.number import * from Crypto.Cipher import AES from Crypto.Util.Padding import pad from Crypto.Hash import SHA256 import os bits = 256 bs = AES.block_size FLAG = open('flag.txt').read() menu = """ +-------------------------+ | | | M E N U | | | | [1] DH Parameters | | [2] View PublicKeys | | [3] Encrypt Flag | | [4] Generate PublicKey | | | +-------------------------+ """ def encrypt(m, key): key = SHA256.new(str(key).encode()).digest()[:bs] iv = os.urandom(bs) cipher = AES.new(key, AES.MODE_CBC, iv) enc = cipher.encrypt(pad(m.encode(), 16)) return (enc.hex(), iv.hex()) def gen_pubkey(g, p, privkey): l = privkey.bit_length() m = int(input("Enter some random integer > ")) new_privkey = privkey ^ m new_pubkey = pow(g, new_privkey, p) return new_pubkey if __name__ == '__main__': g = 2 p = getPrime(bits) # Rick Astley a = getRandomRange(1, p-1) R = pow(g,a,p) # Kermit the Frog b = getRandomRange(1, p-1) K = pow(g,b,p) s = pow(R,b,p) enc_flag, iv = encrypt(FLAG, s) # test with open('priv.txt','w') as f: f.write('a='+str(a)+'\n') f.write('b='+str(b)) print(menu) l = p.bit_length() + 4 try: for _ in range(l): ch = input("Choice ? ").strip().lower() if ch == '1': print("[DH parameters]") print(f"{g = }") print(f"{p = }\n") elif ch == '2': print("[Rick's PublicKey]") print(f"{R = }\n") print("[Kermit's PublicKey]") print(f"{K = }\n") elif ch == '3': print("[ENC FLAG]") print(f"{enc_flag = }\n") print("[IV]") print(f"{iv = }\n") elif ch == '4': npk = gen_pubkey(g, p, b) print("[Kermit's New PublicKey]") print(f"{npk = }\n") else: print(f":( Invalid Choice !!!") break except Exception as e: print(e) exit()
R = pow(g,a,p), K = pow(g,b,p) が渡され、s = pow(R,b,p) を求めたいという状態です。また、任意の整数mについて npk = pow(g,bm,p)を教えてくれます。
mを2のべき乗とすることで、mのbit数番目のbのbitが分かります。例えばm = 1を送った時、bの最下位ビットが0ならbm=b+1となりnpk = K*2 mod p となります。反対にbの最下位ビットが1ならbm=b-1となりnpk = K/2 mod p となります。渡されたnpkとKを比較してbの最下位ビットを特定します。
同様に、m = 2を送った時を考えます。
bの下位2ビット目が0 → npk = K*4 mod p bの下位2ビット目が1 → npk = K/4 mod p
これを255回繰り返して、bが特定できました。
from Crypto.Util.number import * from functools import reduce from operator import mul from itertools import combinations import sys import socket, struct, telnetlib from Crypto.Cipher import AES from Crypto.Util.Padding import pad from Crypto.Hash import SHA256 # --- common funcs --- def sock(remoteip, remoteport): s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect((remoteip, remoteport)) return s, s.makefile('rw') def read_until(f, delim='\n'): data = '' while not data.endswith(delim): data += f.read(1) return data #HOSTはIPアドレスでも可 HOST, PORT = "34.83.246.93", 8000 s, f = sock(HOST, PORT) for _ in range(12): print(read_until(f)) #--DH parameter-- read_until(f,"? ") s.send(b"1\n") read_until(f) g = int(read_until(f).split()[-1]) p = int(read_until(f).split()[-1]) read_until(f) #--Pubkey-- read_until(f,"? ") s.send(b"2\n") read_until(f) R = int(read_until(f).split()[-1]) read_until(f) print(read_until(f)) K = int(read_until(f).split()[-1]) print("K =",K) read_until(f) #--enc flag-- read_until(f,"? ") s.send(b"3\n") read_until(f) enc = read_until(f).split()[-1][1:-1] read_until(f) read_until(f) iv = read_until(f).split()[-1][1:-1] read_until(f) #--calc b-- b = "" for i in range(255): read_until(f,"? ") s.send(b"4\n") read_until(f,"> ") s.send(str(int("1"+"0"*i,2)).encode()+b"\n") read_until(f) npk = int(read_until(f).split()[-1]) read_until(f) if npk == (K*pow(2,int("1"+"0"*i,2),p))%p: b = "0" + b elif npk == (K*pow(inverse(2,p),int("1"+"0"*i,2),p))%p: b = "1" + b else: print("Not Found") print(len(b),b) print("p =",p) print("b =",b) print("iv =",iv) print("enc =",enc) print("R =",R) b = int(b,2) s = pow(R,b,p) key = SHA256.new(str(s).encode()).digest()[:16] iv = long_to_bytes(int(iv,16)) cipher = AES.new(key, AES.MODE_CBC, iv) flag = cipher.decrypt(long_to_bytes(int(enc,16))) print(flag)
wormcon{00p5!_n0_m45k_n0_FL4G}
corCTF 2021 writeup
久しぶりにwriteupを書く気がします。
Result
Writeup
misc
yeetcode
Brush up on your coding skills and ace your next interview with YeetCode! Flag is at ./flag.txt
https://yeetcode.be.ax
ファイル：yeetcode.tar.xz
引数a, bが渡されるとその和を返り値とする関数fを作るとCongrat!とほめてくれますほめてくれます。
def f(a,b): return a+b
tar.xzを解凍してyeet.pyを見るとテストケース10個の内2個は固定値でした。固定値かどうかは実際関係なかったのです。
FLAGが./flag.txtにあるということで、このプログラムから開けないか試してみました。
def f(a,b): g = open("./flag.txt","rb").read() return a+b
このプログラムを提出したところ、エラーは吐かれませんでした。ということはファイルを開けたでしょう。あとは手作業ゲーです。
def f(a,b): #example g = open("./flag.txt","rb").read() if g[0] == ord("c"): return a+b else: return 0
これでg[0]が"c"かどうか分かります。if文が真ならCongrat!と褒められ、偽なら当たってないと言われます。if文をこんな限定的にせず、二分探索とかの方が効率的です。
corctf{1m4g1n3_cp_g0lf_6a318dfe}
crypto
fibonary
Warmup your crypto skills with the superior number system!
ファイル：enc.py, flag.enc
フィボナッチ数列のナップザック暗号ですね。超増加数列ではありませんが、復号可能です。
f = open("flag.enc") a = f.readlines() print(a) enc = a[0].split() print(enc) fib = [1, 1] for i in range(2, 11): fib.append(fib[i - 1] + fib[i - 2]) flag = "" for i in range(len(enc)): val = 0 for j in range(len(enc[i])): if enc[i][j] == "1": val += fib[len(fib)-1-j] flag += chr(val) print(flag)
corctf{b4s3d_4nd_f1bp!113d}
4096
I heard 4096 bit RSA is secure, so I encrypted the flag with it.
ファイル：4096.tar.xz
nが32bit素数128個の積であるmultiple prime RSAです。
factorDBでは素因数分解できないので、sageに投げます。
from Crypto.Util.number import * n = (中略) c = (中略) e = 65537 fac = "(中略)" #sagemathの結果を入れる primes = list(map(int,fac.split(" * "))) phi = 1 for p in primes: phi *= (p-1) d = inverse(e,phi) m = pow(c,d,n) print(long_to_bytes(m))
corctf{to0_m4ny_pr1m3s55_63aeea37a6b3b22f}
dividing_secrets
I won't give you the secret. But, I'll let you divide it.
nc crypto.be.ax 6000
ファイル：server.py
離散対数問題ですが、変数divに代入する値を適切にすれば簡単に解けます。
flagの最終文字を求めます。
x = 256k+l とすると、lが最終バイトです。div=256を投げると、gk を渡されます。それを256乗し、その値とg×lがencrypted flagになります。lは256通りしかないのでbrute forceで解けます。
flagの最終2文字目を求めます。
先ほどのkがxに該当します。なのでencrypted flag = gkとなります。
k = 256k'+l' となり、l'を先と同様に求めます。
これらを繰り返しflagの全ての文字を求めていきます。
HOST, PORT = "crypto.be.ax", 6000 s, f = sock(HOST, PORT) g = int(read_until(f).split()[-1]) p = int(read_until(f).split()[-1]) enc = int(read_until(f).split()[-1]) t = 1 bef = enc flag = "" for i in range(64): t *= 256 print(i,read_until(f,"number> ")) s.send(str(t).encode()+b"\n") tmp = int(read_until(f).strip()) print(tmp) for j in range(256): if (pow(tmp,256,p)*pow(g,j,p))%p == bef: flag += chr(j) break bef = tmp print("flag =",flag[::-1])
corctf{qu4drat1c_r3s1due_0r_n0t_1s_7h3_qu3st1on8852042051e57492}
supercomputer
I ran this code with a supercomputer from the future to encrypt the flag, just get your own and decryption should be simple!
ファイル：supercomputer.tar.xz
n = (pq) × r, a1 = randrange(n), t = (a1n) + ( (n-a1)n) とあります。flagがv(p, t) とxorされます。
関数vは、tが素数pの何乗で割り切れるかの最大値を返り値とします。
ではtはpで何回割れるのでしょうか？ tを展開します。
( (n-a1)^n) =n^n - C0×n^(n-1)×a1 + ... + Ck×n×a1^(n-1) - a1^n
となり、最終項が(a1n)と打ち消されます。
この時点でtがnの倍数であることが分かります。( (n-a1)n) を展開した際にnが掛けられない唯一の項が打ち消されました。
次に、( (n-a1)n) の最終2項目の係数Ckを求めます。パスカルの三角形を考えると、x乗するときの2項目と最終2項目の係数はxです。つまりCk = nです。
( (n-a1)^n) =n^n - C0×n^(n-1)×a1 + ... + Ck'×n^2×a1^(n-2)+ n×n×a1^(n-1) - a1^n
a1n 以外n2で括ることができる＝tがn2の倍数であることが分かりました。
n = (pq) × rより、tがn2の倍数であれば2q回pで割れます。ゆえにv(p, t)の返り値は2qです。
import pwn import binascii from Crypto.Util.number import * p,q,r = (中略) enc = b'(中略)' print(pwn.xor(binascii.unhexlify(enc),long_to_bytes(q*2)))
corctf{1_b3t_y0u_d1dnt_4ctu411y_d0_th3_m4th_d1d_y0u?}
babyrsa
discord is the best place to store secrets
ファイル：babyrsa.PNG, output.txt, script.py
script.pyやbabyrsa.PNGを見ると、10進数表記のn, p, qの一部の桁は見えています。Coppersmithを使うのにどう落とし込むか…。
pの不明な桁数がいくつか、nを参考すると41桁あることが分かりました。
p = int( str(pの上位84桁)+(不明な41桁)+str(pの下位30桁) ) です。下位41+30桁がすべて0の時と9の時とで、上位bitがどこまで一致するか確かめたところ275bit一致しました。つまり不明な41桁がなんであろうとpの上位275bitは一定となります。
SageMathを使ってCoppersmith's Attackをやってみる - ももいろテクノロジー
いつもの資料を使います。コード内のkbitsは未知のbit数を表し、pが512bitならkbits = 219となります。つまり512-219 = 293bitは既知でないといけません。
ここで、pの上位275bitは分かっていて、残り293-275=18bitをbrute forceします。218 ≒ 260000なので余裕です。
n = (中略) pbar = (中略) PR.<x> = PolynomialRing(Zmod(n)) for i in range(pow(2,18) ): pbar = pbar + (i<<219) f = x + pbar x0 = f.small_roots(X=2^kbits, beta=0.3) if len(x0) > 0: print(x0[0] + pbar) break
ちなみにSageMathCell使うとループが3000回程度で止まってしまいます。
頑張って止まったところからやり直すこと数時間…。flag出てよかった。
corctf{1_w4s_f0rc3d_t0_wr1t3_ch4ll5_4nd_1_h4d_n0_g00d_1d345_pl5_n0_bully_;-;}
Red Team Lounge CTF 2021 writeup
最近、m1z0r3では週末に開催されているCTF全てに参加する方法を取っています。目指せ国内順位1桁
Result
Writeup
Web
Basic 10pts
This is a really basic challenge made by gamerboy
http://139.59.252.147:10705/
アクセスするとusernameとpasswordを求められます。SQL injectionですね。初めて上手くいきました。
Username : admin
Password : ' OR 1 = 1 --
RTL{b@s1c_5ql}
Forensics
Expic 15pts
zipを解凍するとphotoというファイルがあります。fileコマンドで中身を確認します。
$ file photo photo: JPEG image data, JFIF standard 1.01, resolution (DPI), density 72x72, segment length 16, progressive, precision 8, 1000x667, frames 3
JPEGファイルであることが分かったので、
$ mv photo photo.jpeg
で拡張子を変えます。
steghideとかstegonlineなので見ましたがよく分からず。exiftoolで怪しげな数値を発見。
$ exiftool photo.jpeg ExifTool Version Number : 10.80 File Name : photo.jpeg (中略) Author : p4ul Number : 68747470733a2f2f706173746562696e2e636f6d2f514632557a6a56590a Profile CMM Type : Linotronic (中略)
とりあえずこの数値をlong_to_bytesしてみます。
>>> from Crypto.Util.number import * >>> x = 0x68747470733a2f2f706173746562696e2e636f6d2f514632557a6a56590a >>> long_to_bytes(x) b'https://pastebin.com/QF2UzjVY\n'
URLが出てきたので方向性は間違っていないと確信。アクセスしてみるとこのような文字列がありました。
T0tLIApSVEx7MTBiYmE5YTUyNDE3MDk1ZGU1MWRiOTQ1NjM2MWQ3NDR9Cg==
base64ですね。
RTL{10bba9a52417095de51db9456361d744}
OSINT
Where is this? 40pts
Thehackerscrew have sent this image. Can you find where this is?
Flag format: RTL{latitude_longitude} Round latitude and longitude to 3 decimal places. (Decimal degrees)
ファイル：where.png
中央の大きなタワーと、その左の旗のようなものが立っているのが鍵になりそうです。見た目がヨーロッパっぽいですね。
「世界 有名なタワー」でググると以下のサイトを発見
【2021最新】ヨーロッパの人気展望台・タワーランキングTOP30 | RETRIP[リトリップ]
パラパラと見ていると、Berliner Fernsehturmが似ているのでGoogle mapで検索。ベルリンのテレビ塔でした。近くを見てみると、赤の市庁舎が旗が立っている建物のよう。
あとは、テレビ塔と旗の角度から南に少し行った道路のところで調整して座標を確定。flagを出したら「既に解かれている」との表示。slack見たら数分先にチームメイトに解かれていました悔しい！
RTL{52.517_13.409}
Reversing
Bad Developers 10pts
A bad developer made this key verification algorithm in Python, he doesn't believe me that it can be cracked, can you show him the way?
https://pastebin.com/4qLbCkQn
a = "LTR" b = "0D" c = "S1" inp = input("> ") if len(inp) != 17: print("Wrong size.") exit() if (inp[0] == a[2] and inp[1] == a[1] and inp[2] == a[0]) and inp[3] == "{" and \ ((inp[4] + inp[5]) == b[::-1]) and (inp[6] == "N" and inp[7] == "T" and inp[8] == chr(95)) and \ (inp[9] + inp[10] == b[::-1]) and (inp[11] + inp[12] + inp[13] == "_TH") and (inp[14] + inp[15] == c[::-1]) and \ (inp[16] == "}"): print("Good job.") else: print("Flag is incorrect.")
if文に合致するように文字列を繋げるだけですね。
RTL{D0NT_D0_TH1S}
The gate of ultimate success 50pts
This binary will ask you for a key, which will open the ultimate gate of success. The key should be wrapped inside RTL{}.
Download link: we_start_with_basics.exe - Google ドライブ
exeファイルを入手したので、実行すると文字列を入力しろと言われます。ある文字列を入力するとflagが出るようです。Ghidraを使って分析してみます。
文字列"'/5:/)4+62/(46>):(82(:9'"を0x7bでxorした値が求められているflagのよう。'TNATROPMITSOMERASCISAB'と出て入力してみるも違うと言われる。
なんでだろうとチームメイトに聞いてみると、strrevを見落としていました。逆順にすればいいだけでした。出てきた文字列に"SOME"があるので、方法が間違っていないとなかなか抜け出せなかったです。逆順にした文字列を入力すると、この文字列がflagのようです。
RTL{BASICSAREMOSTIMPORTANT}
Crypto
Welcome 5pts
This is a really easy challenge. It's purpose is to get you familiar with the platform.
UlRMe0g0VkVfRlVOX1BMNFkxTkchfQ==
base64ですね。
RTL{H4VE_FUN_PL4Y1NG!}
Triangle 10pts
My friend encoded the flag with XOR but forgot the key! He remembers that its a 4 byte key. Can you recover the flag?
133f29027034094a33253126395b3704
4bytesのkeyでxorしたとあります。flagの先頭4bytesがb"RTL{"というのが分かっているので、b"RTL{"と暗号文の先頭4bytesをxorしてkeyを特定します。
keyを特定したら残りの暗号文とxorしてflag全てを出します。
enc = "133f29027034094a33253126395b3704" key = [] flag = "RTL{" for i in range(0,8,2): key.append(int(enc[i:i+2],16)^ord(flag[i//2])) print(key) for i in range(0,len(enc),2): x = int(enc[i:i+2],16)^key[(i//2)%4] print(chr(x),end="") print()
RTL{1_l3rNT_x0R}
Wait, what! 20pts
My mom stole my phone and encrypted it, she doesn't know much about cryptography.
NBY{9x175777156k5608n3x889n5nx9215n2}
Hint : The ................................ is a method of encrypting alphabetic text by using a series of interwoven Caesar ciphers, based on the letters of a keyword. It employs a form of polyalphabetic substitution.
ROT13でもないな、flag内は恐らく16進数だろうから現れているアルファベット3種類k,n,xがa~fになるんだろうという推測で止まってしまいました。
ヒントが5pts消費しないと見れないのですが、思い切って見ることに。
Vigenere暗号か！！！
CyberChefで先頭3文字がRTLになるようにkeyを調整したらflagの括弧内が16進数になりました。
問題文に騙されました。暗号をよく知らないお母さんが暗号化したとあるので超簡単な方法かと思ったら、Vigenere暗号ってめっちゃ詳しいやん！！
RTL{9b175777156c5608a3b889f5ab9215f2}
Ciphers Galores 40pts
The hackers from Thehackerscrew have been sending encrypted messages to each other. We have intercepted this code from them: hastebin
Looks like it’s up to you to solve this mystery. Can you find out what this message says?
$&Es6a@I+v5;|`h_$)q?2Kq75w=p|%tK+)8K)K}d!b_l
この文字列見ただけじゃあ、全然わからないです。base85かなと思いましたがdecodeしても意味のある文字列になりません。そういう時はdcodeで暗号方式を特定してもらいましょう。
Decrypt a Message - Cipher Identifier - Online Code Recognizer
一番最初にBase91がありますが、試しても違うよう。ではその次に出てくるROT47を試したら、次に繋がりそうです。
SUtDe2oxZGdjM190SXBnazBfdHlAMTEzZXgzXzN5P30=
これは明らかにbase64ですね。
IKC{j1dgc3_tIpgk0_ty@113ex3_3y?}
あとはROT[1~25]を試して"RTL{"から始まるものを探したところ、ROT9でした。
RTL{s1mpl3_cRypt0_ch@113ng3_3h?}
Last Words 50pts
My friend told me his father died and his father had a last message for me, but it was in this weird format. Can you help me out?
hastebin
n = p3 のRSA暗号です。factorDBなどで素因数分解可能です。
from Crypto.Util.number import * n=(中略) e=65537 ct=(中略) p = (中略) assert p**3 == n assert isPrime(p) phi = (p-1)*p*p d = inverse(e,phi) m = pow(ct,d,n) print(long_to_bytes(m))
RTL{1_c0uld_pr0b4bly_m4k3_th15_al0t_h4rd3r_next_t1m3!!!-e82fac7a780f72579c47b6ce0d5b7fd82eb6192ed65949ca485309b5}
Diffie Hellman 100pts
Alice and Bob are communicating through a encrypted channel. To be more secure they exchange keys first and then exchange messages. Can you crack the message to find out the flag.
IP: 139.59.252.147 PORT: 19012
ncするとこんな感じになります。
$ nc 139.59.252.147 19012 g:5 p:23 Send your public message to BOB.Intercepted Alice's message: 4 1 Send your public message to ALICE.Intercepted Bob's message: 10 1 The message is encrypted.Bob sends message:SUMz5b6e839g472687gcd1e4g0e185b259c4|
Diffie-Hellmanというので、ga mod pなのでしょう。BobとAliceにメッセージを送れるらしいのですが、最後に貰える暗号文はBobに送るメッセージの値に依存しているようです。そこで1をBobに送るとflagっぽい形のが送られます。
結果的に暗号文のASCIIコードが奇数は-1, 偶数は+1すればflagになります。
Diffie-Hellman要素が無かったけど、何を求められているんだろう。
RTL{4c7d928f563796fbe0d5f1d094c348b5}
Unsolved
Crypto
Prime Wars 100pts
There's a battle between Good and Evil and the Evil empires messaging system is not fully functioning. We've intercepted their message they had to send twice.
hastebin Hint : There's something you should combine!
n1, n2が互いに素でないので、gcdとれば簡単に素因数分解できます。しかし復号しても意味ある文字列になりません。
b';\xd7\x11\xf2@\x17J\xa2<\x11\xf7\x13\xefw\xd8\xdd\x82A\xf8o4\xa5h\x07x\xa4\x1e/z\xd0\xf8;Tf<\xdd\xb3N\xe58\xd8\x06r\x1d\xc3\xe9>\xa1\x10of{Z\x06\xb2\xf3'
b'`\xd0\xa3s(>\x16\x94\x11u?\xa7~\xa2\xc5\xba\xd3\x04\xf9\x1c\x9c\x0e\x9a\xc9y\x02\xe3\x8c\xab\x9f\xad\x95\x0e@\x92\x08@\x11[\xb2b05b3bdd39da3e5}'
ただ、長さがともに56で、暗号文の値が1でも違うと長さが512になることから復号自体は間違っておらず、平文を暗号化する際に何か違う値をRSAで暗号化しているのかなと予想しています。
2個目の復号文の下位16bytesがflagっぽいので、ここから何かわからないかと思いましたが、ヒントを見てもピンと来ずタイムアップ。
CTF-Write-UP/Crypto/RTLXHA2021 - Prime Wars at master · MOCSCTF/CTF-Write-UP · GitHub
復号値をm1, m2とすると
flag = int(str(m1)+str(m2)) print(long_to_bytes(flag)) #RTL{th3r3_pr1m35_4nd_0pt1m4l_pr1m35_wh1ch_do_y0u_u53??-a1b8f0d453def3be67ebf3a313550f73e76951672b05b3bdd39da3e5}
だそうです。combineはそういうことか。
うーーーーん、m1,m2まで簡単に求められて思いつかない方が悪いのか、問題がエスパー要素強すぎるのか…。
Problems&solver
CRYPTO CTF 2021 writeup
Crypto問題が無いCTFもある中で、こういった暗号特化のCTFがあるのは本当にありがたいです。
Result
Writeup
warm-up
Mic Check 440solves 19pts
Read the Rules, check the mic and enter the flag!
問題サイトにあるRuleを読むと一番下にflagがありました。
CCTF{W3lc0me_t0_The_0ne&0nly_Crypt0_CTF_Mad3ـw1th_L0ve_f0r_Crypt0!}
easy
Farm 149solves 41pts
Explore the Farm very carefully!
ファイル：enc.txt, farm.sage
え、これeasy？というくらい、最初の問題にしては難しかったです。
farm.sageをそのままsagemathなどで実行すると、keyが64種類の式があるのに対し、pkeyがその64種類の内一つであることが予想できます。
pkey = key**5 + key**3 + key**2 + 1
とありますが、この計算方法はよく分かっていません。
pkeyが64通りしかないのでこれをbrute forceします。
flagをbase64encodeしてから、文字列encに付け足しています。flagの先頭は"CCTF{"と分かっているため、"CCT"をencryptさせencの先頭4文字"805c"になるpkeyを探します。base64では平文3bytesが符号後4bytesになるのを利用します。
これでpkeyが求まりました。次に、変数ALPHABETの内どれをencryptすればencのi文字目になるかbrute forceします。ALPHABET内を1文字ずつencryptさせ、enc[i]に合致すればbase64encodeのi文字目が分かります。
最後に、得られた文字列をbase64decodeでflagとなります。
import string, base64, math ALPHABET = string.printable[:62] + '\\=' F = list(GF(64)) def keygen(l): key = [F[randint(1, 63)] for _ in range(l)] #key = math.prod(key) # Optimization the key length :D return key def maptofarm(c): assert c in ALPHABET return F[ALPHABET.index(c)] def decrypt(msg, key): #pkeyの特定 m64 = base64.b64encode(msg) for pkey in key: enct = '' for m in m64: enct += ALPHABET[F.index(pkey * maptofarm(chr(m)))] if enct[:4] == "805c": #暗号化に使われたpkeyならここが一致する print(pkey) return pkey key = keygen(14) #keyの候補全て出す pkey = decrypt(b"CCTF{", key) print("pkey=",pkey) enc = "805c9GMYuD5RefTmabUNfS9N9YrkwbAbdZE0df91uCEytcoy9FDSbZ8Ay8jj" base64_enc = b"" for i in range(len(enc)): for m in ALPHABET: #何をencryptすればenc[i]になるのかbrute force if enc[i] == ALPHABET[F.index(pkey * maptofarm(m))]: base64_enc += m.encode() break print(base64.b64decode(base64_enc))
CCTF{EnCrYp7I0n_4nD_5u8STitUtIn9_iN_Fi3Ld!}
KeyBase 118solves 48pts
Recovering secrets is hard, but there is always some easy parts!
nc 01.cr.yp.toc.tf 17010
ファイル：keybase.py
AESのCBCモードの問題です。
keyの一部と任意の平文32bytesの暗号文の一部が隠されています。加えてivも不明です。
以降は以下のように定義します。
pt1, pt2 : 任意の平文の前半16bytes, 後半16bytes ct1, ct2 : ptの暗号文の前半16bytes, 後半16bytes k1, k2 : ct1,ct2をkeyによってdecryptした値。下図の赤い部分 enc_flag : flagの暗号文
i ) keyをbruteforceする
keyの隠されている部分は2bytesのみです。2562通りなのでbrute forceできますね。以降はkeyをbrute forceしている状態で考えていきます。
ii ) k2を求める
"\x00"*16+ct2を復号します。この際ivは何でもいいです。得られた平文をpt'1, pt'2とすると、暗号文の先頭16bytesとpt'2をxorすればk2となります。
iii) ct1を求める
求めたk2とpt2をxorするとct1になります。はじめにct1の一部が分かっているので、それと合致しないものは排除しても良いですね。
iv) k1を求める
ct1を復号します。この際ivは何でもいいです。得られた平文をpt'1とすると、ivとpt'1をxorすればk1となります。
v) ivを求める
求めたk1とpt1をxorすればサーバ側が使ったivが求まります。
vi) flagを求める
enc_flagを求めたivとbrute forceしているkeyで復号し、"CCTF{"が含まれているものを出力して終了です。
keyを求めるAESの問題なんて結構珍しいですね。
from Crypto.Cipher import AES from Crypto.Util.number import * import binascii key_t = "a2824541d7b87474f6c9b43d68d0" enc_a = "2031e2b4219ea750ba6a27f8dbe76555" fk = "dca4" enc = "374fccd3d532f29967b5c7a83972b7279aaf3866fd22298df1e66990fe9a4b1b" tmp = "0123456789abcdef" tmp_iv = b"A"*16 pl = b"a"*16 for k1 in tmp: print("k1=",k1) for k2 in tmp: for k3 in tmp: for k4 in tmp: key = key_t+k1+k2+k3+k4 # i ) #print(key) key = binascii.unhexlify(key.encode()) #print(key) cipher = AES.new(key, AES.MODE_CBC, tmp_iv) tmp_e = "00"*16+enc_a assert len(tmp_e)%32 == 0 pt = cipher.decrypt(binascii.unhexlify(tmp_e)) assert len(pt) == 32 pt2 = pt[16:] bx = bytes_to_long(pt2) # ii ) ct1 = bx^bytes_to_long(pl) # iii ) cipher = AES.new(key, AES.MODE_CBC, tmp_iv) ct1 = long_to_bytes(ct1) while len(ct1)%16 != 0: ct1 = b"\x00"+ct1 pt1 = cipher.decrypt(ct1) ax = bytes_to_long(pt1)^bytes_to_long(tmp_iv) # iv ) iv = long_to_bytes(ax^bytes_to_long(pl)) # v ) while len(iv) < 16: iv = b"\x00"+iv fipher = AES.new(key, AES.MODE_CBC, iv) flag = fipher.decrypt(binascii.unhexlify(enc)) # vi) if b"CCTF" in flag: print(flag)
CCTF{h0W_R3cOVER_7He_5eCrET_1V?}
Symbols 70solves 70pts
Oh, my eyes, my eyes! People still can solve this kind of cryptography? Mathematicians should love this one!
ファイル： Symbols.png
各文字がflagの1文字と該当していそうです。こんなフォントがないか探していると、チームメイトから連絡が。
これ多分わかったかもです
latexコマンドの頭文字をとると多分答えです
なぬ!? その通りでした。
ちゃんと研究してLatexで論文書いている人には造作の無いことだったのかもしれません。一方私は…。
CCTF{Play_with_LaTeX}
medium-easy
Rima 93solves 56pts
Sequences are known to be good solutions, but are they good problems?
ファイル：rima.py, g.enc, h.enc
複雑なことをしていますね。読み解いていきましょう。
大きく分けて3つあります。
A) 配列fを作る
flagを2進数にして各桁を配列fの一つの要素とします。その後先頭に0を加えます。
次に、配列fのindexの小さい方から大きい方へ、indexが一つ大きいものの値を足します。なので、配列fの要素は0か1か2になります。
B) 配列g,hを作る
まず、a,bを決めます。aはlen(f)より大きい最小の素数、bはaの次の素数になります。
gは、f[0]がa個、f[1]がa個、、、f[len(f)-1]がa個の配列になります。長さはlen(f)×aですね。
hは 、f[0]がb個、f[1]がb個、、、f[len(f)-1]がb個の配列になります。長さはlen(f)×bです。
配列fの要素をコピーしているので、配列g,hともに要素は0,1,2のどれかです。
次に、g,h を編集していきます。
cを(len(f)>>2)より大きい最小の素数とします。
gもhも同様に以下の事を行います。
まず配列の先頭に要素0をc個挿入します。つまり、len(g) = len(f)×a+c, len(h) = len(f)×b+cとなります。
その後、配列のindexの小さい方から大きい方へ、indexがcだけ大きいものの値を足します。なので、配列g,hの要素は0から4までになります。
C) g.enc, h.encに書く
配列g,hを5進数に見立ててlong_to_bytes()したものをそれぞれ書いて保存します。
では、これを元に戻しましょう。
C') 配列g,hの復元
g.enc, h.encをbytes_to_longして5進数にして、各桁を配列g,hの要素にします。これに時間かかります。
B') a,b,cを求める
この式を利用します。
len(g) = len(f)×a+c, len(h) = len(f)×b+c
まずcをbrute forceします。len(f) = gcd(len(g)-c, len(h)-c) となり、そこからa, bも求めることが出来ます。
ここで、nextprime(len(f) ) == a かつ nextprime(a) == b かつ nextprime(len(f)>>2) == c となれば正しいa,b,cであることが分かります。
a = 257, b = 263, c = 67でした！
A') 配列fの復元
配列gをf[0]がa個、f[1]がa個、、、f[len(f)-1]がa個の配列となるように戻します。
作る時の逆工程をするので、indexの大きい方からc個先の要素を引きます。hについても同様です。
これで、gはa個飛ばし、hはb個飛ばししたものがfになります。
作る時の逆工程をするので、indexの大きい方から1個先の要素を引き、配列fの復元が終わりました。
仕上げに配列fを2進数に見立ててlong_to_bytesすればflagとなります。
from Crypto.Util.number import * def nextPrime(n): while True: n += (n % 2) + 1 if isPrime(n): return n # C' G = open("g.enc","rb") GG = G.readlines() g = b"" for gt in GG: g += gt H = open("h.enc","rb") HH = H.readlines() h = b"" for ht in HH: h += ht G = bytes_to_long(g[:-1]) H = bytes_to_long(h[:-1]) g = [] h = [] while G != 0: g = [G%5] + g G //= 5 while H != 0: h = [H%5] + h H //= 5 lg = len(g) lh = len(h) #lg = len(f)*a + c #lh = len(f)*b + c import math # B' for c in range(lg): if isPrime(c): lf = math.gcd(lg-c,lh-c) a = (lg-c)//lf b = (lh-c)//lf if lf > 50 and isPrime(a) and isPrime(b): print("len(f)=",lf) print("a=",a) print("b=",b) print("c=",c) if nextPrime(lf) == a and nextPrime(a) == b and nextPrime(lf>>2) == c: print("Perfect!!!") break #g,hを逆に for i in range(len(g)-c-1,-1,-1): g[i] -= g[i+c] assert g[i] >= 0 for i in range(len(h)-c-1,-1,-1): h[i] -= h[i+c] assert h[i] >= 0 g = g[c:] h = h[c:] f = [] # A' for i in range(0,len(g),a): f.append(g[i]) for i in range(len(f)-2,-1,-1): f[i] -= f[i+1] assert f[i] >= 0 flag = ''.join(str(v) for v in f) print(flag) print(long_to_bytes(int(flag,2)))
CCTF{_how_finD_7h1s_1z_s3cr3T?!}
Hyper Normal 69solves 71pts
Being normal is hard these days because of Corona virus pandemic!
ファイル：hyper-normal.py, output.txt
ちょっとこれなんで解けたか怪しい部分があります。
outputの2重配列から、以下のことが分かります。
output[i][j] = (i+1)×chr(flagの何文字目)×(乱数0~126) mod 8443
chr(flagの何文字目)を32~127でbrute forceし、全てのiで乱数の部分が0~126になればOKです。
間違っている部分、考察不足があれば是非ともコメントいただきたいのですが、jがflagのj文字目に該当しているようでした。
これに気付くまではflagが何通りもなり得て意味のある文になるよう必死に探していたのですが、該当する文字が何列目か出すと、flagの何文字目かと一致するものが全部ありました。
でも途中でshuffleしているのは何…？
自分でもなんで解けたか分からなかったので伝わりにくくて申し訳ないです。
from Crypto.Util.number import * l = 55 p=8443 flag = [[] for _ in range(l)] cont = [] x = 0 aprj = [0 for _ in range(l)] while x < 5: ind = [[] for _ in range(l)] for i in range(l): #r0 * a = s0 mod p #a = (i+1)*ord(flag[i]) を求める for m in range(32,128): a = m*(i+1) for j in range(l): r0 = (enc[0][j]*inverse(a,p))%p if r0 < 127: ch = True for k in range(l): if k in cont: #ch = False continue r = (enc[k][j]*inverse(a,p))%p if r >= 127: ch = False break if ch: aprj[j] += 1 if i < len(tip): if tip[i] == chr(m): if not j in cont: cont.append(j) #if not [chr(m),j] in flag[i]: flag[i].append([chr(m),j]) else: flag[i].append([chr(m),j]) ind[i].append(j) if len(ind[i]) == 1: cont.append(ind[i][0]) x += 1 for k in cont: for i in range(len(flag)): if len(flag[i]) == 1: continue try: if flag[i][1] == k: flag = flag[:i] + flag[i+1:] break except: print("Except") print(flag[i]) for i in range(len(flag)): for j in range(len(flag[i])): if flag[i][j][1] == i: print(flag[i][j][0],end="") break print()
CCTF{H0w_f1Nd_th3_4lL_3I9EnV4Lu35_iN_FiN173_Fi3lD5!???}
Hamul 56solves 83pts
RSA could be hard, or easy?
ファイル：hamul.py, output.txt
まずこれが満たされる素数があるんだと問題ファイルを見て思いました。p,qが64bitsなのでこれらの積が分かれば素因数分解が出来るだろうと推測します。
筆算で考えると、nの下位x桁はp×qの下位x桁と一致し、nの上位y桁はp×qの上位y桁と一致します。
試してみると分かると思うのですが、これでp×qのほとんど桁が分かります。
手元でやってみたところ、問題ファイルのようにP,Qを決めるとx = 23, y=18程度であることが分かります。これで分からない桁数は0か1と判断し、(nの上位y桁)+[0-9]{0, 1}+(nの下位x桁)をsageなどで素因数分解し64bits素数の積になっているものを見つけます。
ちょっと手間取りましたが、これでp,qが求まりました。
from Crypto.Util.number import * n = 98027132963374134222724984677805364225505454302688777506193468362969111927940238887522916586024601699661401871147674624868439577416387122924526713690754043 c = 42066148309824022259115963832631631482979698275547113127526245628391950322648581438233116362337008919903556068981108710136599590349195987128718867420453399 primes = ['2', '3', '5', '7', '11', '13', '17', '19', '23', '29', '31', '37', '41', '43', '47', '53', '59', '61', '67', '71'] ns = [] for i in range(15,20): for j in range(18,23): N = int(str(n)[:i]+str(n)[-j:]) ch = True for p in primes: if N%int(p) == 0: #小さい素数で割れるものを排除 ch = False break if ch: ns.append(N) print(N) for k in range(10): N = int(str(n)[:i]+str(k)+str(n)[-j:]) #nの桁だけではpqが分からない場合 ch = True for p in primes: if N%int(p) == 0:#小さい素数で割れるものを排除 ch = False break if ch: ns.append(N) print(N) tmp = [[391111220047,25063748606238954787416469],[465963927380741639,21037493935292470637],[2647727654901734723 , 3702311783536219524841],[9324884768249686093 , 10512422984265378151],[2511932571814542137 , 39024587707209981139]] #大きい桁数×大きい桁数と素因数分解できた候補たち for t in tmp: p = int(str(t[0])+str(t[1])+str(t[1])+str(t[0])) if n%p == 0: print("Find!!!") print(p) print(n//p) q = n//p phi = (p-1)*(q-1) e = 65537 d = inverse(e,phi) m = pow(c,d,n) print(long_to_bytes(m))
はじめ、p×q = (nの上位y桁)+(nの下位x桁)だと思っていたので上手くいきませんでした
CCTF{wH3Re_0Ur_Br41N_Iz_5uP3R_4CtIVe_bY_RSA!!}
medium
Tuti 71solves 69pts
Cryptography is coupled with all kinds of equations very much!
ファイル：tuti.py
まあ気になるのはこれですよね
assert((x**2 + 1)*(y**2 + 1) - 2*(x - y)*(x*y - 1) == 4*(int(k, 16) + x*y))
式変形すると、このようになります。
(x^2+1)(y^2+1)-2(x-y)(xy-1) = 4k+4xy (x^2)(y^2)+x^2+y^2+1 -2((x^2)y-x-x(y^2)+y) - 4xy = 4k (x^2)(y^2-2y+1) + 2x(y^2-2y+1) +y^2-2y+1 = 4k ((y-1)^2)(x^2+2x+1) = 4k ((x+1)^2)((y-1)^2) = 4k
と、A2×B2 = 4kという形になりました。4kをfactorDBに投げると素因数分解できました。
あとは、得られた素数たちの部分集合を取ってその積をA、残りをBとして上式が成り立つか確認してx,yを求めます。
そして最後long_to_bytes()で終了です。
import gmpy2 from Crypto.Util.number import * k = (省略) k2, ch = gmpy2.iroot(k,2) fac = [2,3,11,11,19,47,71,3449,11953,5485619,2035395403834744453,17258104558019725087,1357459302115148222329561139218955500171643099] tt = 1 for h in fac: tt *= h assert tt == int(k2) s = pow(2,len(fac)) for i in range(s): tmp = bin(i)[2:] while len(tmp) < len(fac): tmp = "0"+tmp X = 1 for j in range(len(tmp)): if tmp[j] == "1": X *= fac[j] x = X-1 m1 = long_to_bytes(x) if b"CCTF" in m1: Y = 2*int(k2)//X y = Y+1 m2 = long_to_bytes(y) print(m1+m2)
CCTF{S1mPL3_4Nd_N!cE_Diophantine_EqUa7I0nS!}
Salt and Pepper 69solves 71pts
Salt and Pepper, Salty and Spicy! Can we attack these unnormalized served foods?
nc 02.cr.yp.toc.tf 28010
ファイル：salt_pepper.py
sha1とmd5のハッシュ値が与えられているので、逆引きできるかなと検索するもダメ。
Length Extention Attackでは？と気付いたチームメイトに全部やってもらいました。
実装には300行もかかったとのことで、有難い限りです。
Onlude 48solves 95pts
Encryption and Decryption could be really easy, while we expected the decryption to be harder!
ファイル：onlude.sage, output.txt
まずは式をまとめましょう。
S = L × U X = A + R Y = S × X = L × U × X = S × (A + R) = L × U × (A + R) E = L^(-1) × Y = U × X = U × (A + R)
そして、与えられた値は以下の通りです。
E L × U × L L^(-1) × S^2 × L R^(-1) × S^8
目標はAを求めることですが、慌てず求められる行列から求めていきましょう。
i) U
L^(-1) × S^2 × L = L^(-1) × (L × U) × (L × U) × L = U × L × U × L (U × L × U × L) × (L × U × L)^(-1) = U
ii) X
U^(-1) × E = U^(-1) × U × X = X
iii) S2
(L × U × L) × E × X^(-1) = L × U × L × L^(-1) × Y × X^(-1) = L × U × (S × X) × X^(-1) = S × S = S^2
iv) R
((R^(-1) × S^8) × (S^2)^(-4))^(-1) = (R^(-1) × S^8 × S^(-8))^(-1) = (R^(-1))^(-1) = R
v) A
X = A + R -> A = X - R
ということで、Aが求まりました。出力してみるとこんな感じです。
[48 0 0 0 0 57 0 0 0 0 66] [ 0 0 0 0 66 0 0 0 0 40 0] [ 0 0 0 4 0 0 0 0 13 0 0] [ 0 0 1 0 0 0 0 23 0 0 0] [ 0 26 0 0 0 0 51 0 0 0 0] [ 6 0 0 0 0 2 0 0 0 0 8] [ 0 0 0 0 45 0 0 0 0 25 0] [ 0 0 0 24 0 0 0 0 66 0 0] [ 0 0 66 0 0 0 0 5 0 0 0] [ 0 48 0 0 0 0 10 0 0 0 0] [ 1 0 0 0 0 65 0 0 0 0 0]
あとは0でない要素について、配列alphabetのindexを出力すればOKです。
global p, alphabet p = 71 alphabet = '=0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ$!?_{}<>' def cross(m): return alphabet.index(m) def prepare(msg): A = zero_matrix(GF(p), 11, 11) for k in range(len(msg)): i, j = 5*k // 11, 5*k % 11 A[i, j] = cross(msg[k]) return A def keygen(): R = random_matrix(GF(p), 11, 11) while True: S = random_matrix(GF(p), 11, 11) if S.rank() == 11: _, L, U = S.LU() return R, L, U def encrypt(A, key): R, L, U = key S = L * U X = A + R Y = S * X E = L.inverse() * Y return E A = prepare(flag) key = keygen() R, L, U = key S = L * U E = encrypt(A, key) O = [[1,2],[3,4]] Et = [[25,55,61,28,11,46,19,50,37,5,21],[20,57,39,9,25,37,63,31,70,15,47],[56,31,1,1,50,67,38,14,42,46,14],[42,54,38,22,19,55,7,18,45,53,39],[55,26,42,15,48,6,24,4,17,60,64],[1,38,50,10,19,57,26,48,6,4,14],[13,4,38,54,23,34,54,42,15,56,29],[26,66,8,48,6,70,44,8,67,68,65],[56,67,49,61,18,34,53,21,7,48,32],[15,70,10,34,1,57,70,27,12,33,46],[25,29,20,21,30,55,63,49,11,36,7]] Kt = [[50,8,21,16,13,33,2,12,35,20,14],[36,55,36,34,27,28,23,21,62,17,8],[56,26,49,39,43,30,35,46,0,58,43],[11,25,25,35,29,0,22,38,53,51,58],[34,14,69,68,5,32,27,4,27,62,15],[46,49,36,42,26,12,28,60,54,66,23],[69,55,30,65,56,13,14,36,26,46,48],[25,48,16,20,34,57,64,62,61,25,62],[68,39,11,40,25,11,7,40,24,43,65],[54,20,40,59,52,60,37,14,32,44,4],[45,20,7,26,45,45,50,17,41,59,50]] Wt = [[34,12,70,21,36,2,2,43,7,14,2],[1,54,59,12,64,35,9,7,49,11,49],[69,14,10,19,16,27,11,9,26,10,45],[70,17,41,13,35,58,19,29,70,5,30],[68,69,67,37,63,69,15,64,66,28,26],[18,29,64,38,63,67,15,27,64,6,26],[0,12,40,41,48,30,46,52,39,48,58],[22,3,28,35,55,30,15,17,22,49,55],[50,55,55,61,45,23,24,32,10,59,69],[27,21,68,56,67,49,64,53,42,46,14],[42,66,16,29,42,42,23,49,43,3,23]] Qt = [[51,9,22,61,63,14,2,4,18,18,23],[33,53,31,31,62,21,66,7,66,68,7],[59,19,32,21,13,34,16,43,49,25,7],[44,37,4,29,70,50,46,39,55,4,65],[29,63,29,43,47,28,40,33,0,62,8],[45,62,36,68,10,66,26,48,10,6,61],[43,30,25,18,23,38,61,0,52,46,35],[3,40,6,45,20,55,35,67,25,14,63],[15,30,61,66,25,33,14,20,60,50,50],[29,15,53,22,55,64,69,56,44,40,8],[28,40,69,60,28,41,9,14,29,4,29]] E = zero_matrix(GF(p), 11, 11) for i in range(len(Et)): for j in range(len(Et[i])): E[i,j] = Et[i][j] K = zero_matrix(GF(p), 11, 11) #LUL for i in range(len(Kt)): for j in range(len(Kt[i])): K[i,j] = Kt[i][j] W = zero_matrix(GF(p), 11, 11) #L^-1SSL for i in range(len(Wt)): for j in range(len(Wt[i])): W[i,j] = Wt[i][j] Q = zero_matrix(GF(p), 11, 11) #R^-1S**8 for i in range(len(Qt)): for j in range(len(Qt[i])): Q[i,j] = Qt[i][j] U = W*(K.inverse()) X = U.inverse()*E S2 = K*E*(X.inverse()) Rinv = Q*((S2**4).inverse()) R = Rinv.inverse() A = X-R print("CCTF{",end="") for i in range(11): for j in range(11): if A[i, j] != 0: print(alphabet[A[i, j]],end="") print("}")
CCTF{LU__D3c0mpO517Ion__4L90?}
Unsolved
medium
Triplet 50solves 91pts
Fun with RSA, three times!
nc 07.cr.yp.toc.tf 18010
ファイル：Triplet.py
気になるところはこの部分
if 1 < e < min([phi_1, phi_2, phi_3]) and 1 < d < min([phi_1, phi_2, phi_3]): b = (e * d % phi_1 == 1) and (e * d % phi_2 == 1) and (e * d % phi_3 == 1)
phiが3つあって、それらを法とすると全て積が1になるedか…。素数を3つ生成して、2つの組み合わせが3組できるのでそれをphi_1~3にすればいいのでは？となりました。なので、
ed = 1 mod (p-1)(q-1)(r-1) ※p,q,rは生成する素数
ただ、e,dにもルールがあるので気を付けなければなりません。(p-1)(q-1)(r-1)+1を素因数分解して、ともに160bits以下になればいいのですが、何回試しても上手くいかずタイムアップ。
参考資料：
lior@wildboar:/2021-crypto-ctf/triplets# cd .. | lior5654’s CTF Writeups
これによると、p,q,r = kx+1の形にしていました。なるほど！
これで、lcm(phi_1~3) = lcm(k1,k2,k3) ≒ k1×k2×k3×xとなり、e,d ともに160bits以内に収まりました。
CCTF{7HrE3_b4Bie5_c4rRi3d_dUr1nG_0Ne_pr39naNcY_Ar3_triplets}
Ferman 31solves 134 pts
Modern cryptographic algorithms are the theoretical foundations and the core technologies of information security. Should we emphasize more?
nc 07.cr.yp.toc.tf 22010
(p-x)^2 + (q-y)^2 = k
の形をどう解いていいか分からず終了。結局sageに任せばいいなんて…。 kが7乗根持つのもヒントだったのかな？
Problems&solver
ImaginaryCTF 2021 Writeup
Crypto全完まであと一問…。悔しいですね。
来週のCrypto CTFがあるので精進します。
Result
Writeup
Chicken Caesar Salad 50pts
I remember the good old days when Caesar ciphers were easy…
ファイル：chicken-caesar-salad.txt
ROT18でした。
ictf{wHen_dID_cAEseR_cIphERs_gEt_sO_hARd}
Flip Flops 100pts
Yesterday, Roo bought some new flip flops. Let's see how good at flopping you are.
nc chal.imaginaryctf.org 42011
ファイル：flop.py
DawgCTF 2021 writeup - Attack All Around
こちらと同じ、byte flipping attackですね。
100点問題で難易度高くね！？とひたすらビビっていました。案の定、以降の問題のレベルも高かったです。
from Crypto.Util.number import * from functools import reduce from operator import mul from itertools import combinations import sys import socket, struct, telnetlib # --- common funcs --- def sock(remoteip, remoteport): s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect((remoteip, remoteport)) return s, s.makefile('rw') def read_until(f, delim='\n'): data = '' while not data.endswith(delim): data += f.read(1) return data #HOSTはIPアドレスでも可 HOST, PORT = "chal.imaginaryctf.org", 42011 s, f = sock(HOST, PORT) print(read_until(f)) print(read_until(f,"solution: ")) sol = input("> ") s.send(sol.encode()+b"\n") for _ in range(25-8+1): print(read_until(f)) print(read_until(f,"'gimmeflag'.")) for _ in range(2): print(read_until(f)) print(read_until(f,"> ")) s.send(b"1\n") pt = "31"*48 print(read_until(f,"(in hex): ")) s.send(pt.encode()+b"\n") enc = read_until(f).strip() print("got mes:",enc) print(read_until(f,"'gimmeflag'.")) for _ in range(2): print(read_until(f)) print(read_until(f,"> ")) s.send(b"2\n") val = bytes_to_long(b"gimmeflag"+b"\x07"*7) pt0 = int("31"*16,16) ct1 = int(enc[:32],16) key = pt0^ct1 ppt0 = val^key ans0 = hex(ppt0)[2:] while len(ans0) < 32: ans0 = "0"+ans0 ans0 += enc[32:64] print(read_until(f,"(in hex): ")) s.send(ans0.encode()+b"\n") while True: print(read_until(f))
ictf{fl1p_fl0p_b1ts_fl1pped_b6731f96}
Rock Solid Algorithm 100pts
Something was the wrong size here...
ファイル：secure.txt
nが素因数分解できませんが、e=5と小さいです。Low public exponent attackなのだろう。
c+k×nに5乗根が存在するかどうかbrute forceして、flagを出します。
import gmpy2 from Crypto.Util.number import * n = 18718668654839418101060350414897678724581774081742102287908765212690862231899547405582997157020093499506177632395430572542600019258424947803591395926472246347413986531437177801754324606200243710836609694453888894668656807471052095014376204102474311740080044776201105722801365112971807912406879483156845216746137339614577267869908065296042390812575960639865867729920434603853708907147465162697098688239587320232595412227310236678367 e = 5 c = 4061448515799106340420739691775850071489215699577921072934942485890519294380069123037340174441242842518682390853378784679825023237216051766738593812159344136064529711265570171627670665806072255545198689928996413238102114126558579154343844959868438278433954975590137693439216155482228025380904377837299357044104373966173149290333194304831238889245126840666444234215617022142380016275718234640045049962318290976661640301222078289152 tmpc = c while True: m,ch = gmpy2.iroot(tmpc,e) if ch: print(long_to_bytes(int(m))) break tmpc += n
ictf{3_isnt_th3_0nly_sm4ll_3xp0n3nt}
Lines 150pts
Try to crack my unbreakable™ encryption! I based it off of the Diffie-Helman key exchange!
ファイル：lines.py, out.txt
複雑なことをしているようですが、sを求めるだけです。a, bは求める必要ありません。
enc_msg = s × msg mod p s = enc_msg × msg^(-1) mod p
これでsが求まりました。
enc_flag = s × flag mod p flag = enc_flag × s^(-1) mod p
これでflagも求められました。
p = (省略) encrypt_flag = (省略) encrypt_msg = (省略) msg = bytes_to_long(b":roocursion:") s = (inverse(msg,p)*encrypt_msg)%p flag = (encrypt_flag*inverse(s,p))%p print(long_to_bytes(flag))
これを深夜にやり、翌朝残りをやろうとしていました。
ictf{m0d_4r1th_ftw_1c963241}
New Technology 300pts
If it's not Windows New Technology, what else could NT stand for?
ファイル：new_technology.py
朝起きて、オリンピック見ながらのんびりやるかと思ったらもう既に解かれていました。
まあ、とりあえずやってみるかとコード読んでみたけど分からない…。複雑すぎる。
一日考えて分からなかったので、先に解いた方の解法見てみるとびっくり。
実験してみたらkey = pub * pubであることがわかった
未証明
そんなんあり！？と確かめてみたら、本当でした。とりあえず手元で動かしてみて色々試してみるってのは必要ですね。証明できたら、追記します。
ictf{Would_number_theory_be_new_technology?}
Roll it back 300pts
Once you figure out what this is doing, it could be a straight line to the finish.
ファイル：roll_it_back.py
こちらも先に解かれていた問題です。
itertoolsのislice, cycle, gmpy2のpopcountを調べるのが面倒で放置。けど他の問題も分からんし、と渋々調べてみたらそんなに難しくない。
isliceはリストにするような感じのもの。cycleはリストを無限に長くして、中身はサイクルする感じのもの(a[0], a[1], ... a[n-1], a[0], ...)。popcountは、引数が整数値でいくつbitが立っているか個数を返すものです。
ということで、この部分の逆関数を頑張って考えます。
for _ in range(421337): flag = (flag >> 1) | ((popcount(flag & T) & 1) << (l - 1))
flagを1bit右シフトしたものとpopcountの結果を(l-1)bits左シフトのORが次のflagになります。flagは常にl (=420)bits以下です。
なので、flagの420bit目が立っていたら、popcount( (前のflag) & T) が1になります。ORの左側の演算では必ず419bits以下になるからですね。flagの420bit目が立っていない場合、popcount( (前のflag) & T) が0になります。
次に、前のflagを1bit右シフトしているので、前のflagの最下位ビットが分かりません。しかし、popcountの条件がある、且つTは奇数なのでpopcountの結果は前のflagの最下位ビットに依存します。つまり、前のflagの最下位ビットが一意的に決まります。
このfor文の逆関数はこのようになります。
binf = bin(flag)[2:] for i in range(421337): if binf[0] == "1": # (popcount(flag & T) & 1) == 1 tmp_flag = binf[1:] if (popcount(int(tmp_flag+"1",2) & T) & 1) == 1: binf = binf[1:]+"1" else: assert (popcount(int(tmp_flag+"0",2) & T) & 1) == 1 binf = binf[1:]+"0" else: #assert flag.bit_length() == l-1 # (popcount(flag & T) & 1) == 0 tmp_flag = binf[1:] if (popcount(int(tmp_flag+"1",2) & T) & 1) == 0: binf = binf[1:]+"1" else: assert (popcount(int(tmp_flag+"0",2) & T) & 1) == 0 binf = binf[1:]+"0" #assert flag.bit_length() == l-1 #print(i, flag.bit_length()) assert len(binf) == l
Tの値がコードに書いてあるものをそのまま実行していいのか、それともfake_flagのところもちゃんと本物のflagにしないといけないのか判断が出来ず、先に解いたチームメイトにヒントをもらいました。自力じゃないです(笑)
ictf{I_did_not_have_linear_relations_with_that_LFSR}
Primetime 300pts
Alice and Bob are meeting up to watch TV, but they've neglected to invite Elise and Gamal! Elise and Gamal intercepted the network traffic between the two, and managed to extract an encrypted message. Can you help them figure out what TV show Alice and Bob will be watching, and when?
Wrap the decrypted message in the flag format before submitting.
ファイル：primetime.py, output.txt
この問題難しかった分、解けて嬉しかったです！
まず、Elementクラスを見ていきましょう。
class Element: def __init__(self, n): self.n = Element.reduce(n) def __str__(self): return str(self.n) def __add__(self, other): return Element(self.n*other.n) def __eq__(self, other): return self.n == other.n def __mul__(self, n): if type(n) == int: ret = Element(1) for c in "{:0128b}".format(n): ret += ret if c == '1': ret += self return ret if type(n) == Element: ret = Element(1) primelist = list(islice(primes(), ELEMENT_LEN)) for i, num in enumerate(primelist[::-1]): cnt = 0 temp = n.n while gcd(temp, num) > 1: cnt += 1 temp //= num for c in "{:08b}".format(cnt): ret += ret if c == '1': ret += self return ret @staticmethod def encode(b): assert len(b) <= ELEMENT_LEN ret = 1 for i, num in enumerate(primes()): if i >= len(b): return Element(ret) ret *= num**b[i] @staticmethod def reduce(n): if n == 0: return 0 primelist = list(islice(primes(), ELEMENT_LEN)) for i, num in enumerate(primelist): while n % (num**256) == 0: n //= num**256 if num != primelist[-1]: n *= primelist[i+1] return n
まず、genを生成したencodeを見ていきます。numには素数が小さいものから入っていきます。[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53] の16個ですね。(素数)bytes列bでのb[i]の積が返されます。
素因数分解するとこうなりました。
gen 53 116 47 112 43 95 41 114 37 48 31 43 29 97 23 114 19 51 17 110 13 51 11 103 7 95 5 51 3 104 2 43
(左側)右側という感じですね。
これを、乱数akey, bkeyでgenとの積を取ります。その積がapub, bpubとなり公開された値となります。
apubをgenで割ったらakeyが出るだろう、とapub%genを見てみると0じゃない。なんで？？？
Elementクラスでのmulを見てみましょう。
def __mul__(self, n): if type(n) == int: ret = Element(1) for c in "{:0128b}".format(n): ret += ret if c == '1': ret += self return ret
retにどんどんretを足したり、掛けられる数に該当するselfを足しています。では、addを見てみましょう。
def __add__(self, other): return Element(self.n*other.n)
なんとかけ算しています。足し算がかけ算になるのであったら、かけ算はべき乗になるのでは？と手元でやってみます。Element(23)×11とすると、2311が返ってきました。予想的中！
じゃあなぜ、apub%genが0でないのでしょう。途中でmodとかされているのかなと思ったら、initに罠が。なんと返す時にreduceを通しています。
@staticmethod def reduce(n): if n == 0: return 0 primelist = list(islice(primes(), ELEMENT_LEN)) for i, num in enumerate(primelist): while n % (num**256) == 0: n //= num**256 if num != primelist[-1]: n *= primelist[i+1] return n
先程の素数の指数が256を越えると、その次の素数の指数が1増えるようです。元の素数の指数は256減るようです。これが原因でした。
つまり、apubはgenのakey乗で、素因数分解して256乗を越えるものはreduce関数でごちゃごちゃさせられます。
途中で繰り上がりのようなものがあって、それを離散対数問題なんて解けるわけ…。ん？繰り上がり？
解法の鍵は繰り上がりでした！
gen, apub, bpubを素因数分解して、その指数を256進数に見立てます。先程のgenで考えると、2の指数が最下桁となりその値は43です。これが256を越えると、その一つ上の位3の指数部分に繰り上がります。また、一番大きい素数53の指数が256を越えた場合は、ただ指数%256になるだけです。つまり、mod 25616 ということです。
このように考えると、genを2乗するとこの256進数を2倍するだけです。つまり、(genの256進数方式) × akey = (apubの256進数方式) mod 25616 となり、akeyを簡単に求められます。
akey = (apubの256進数方式) × (genの256進数方式)^(-1) mod 256^16
これと同様にして、bkeyを求めます。
akey, bkeyが求められたので、sを求めます。これはprimetime.pyにある通りに実行すればOKです。
最後に、mを求めます。
ct及びsを先程と同様に256進数方式で計算します。
ct = m × s m = (ctの256進数方式) × (sの256進数方式)^(-1) mod 256^16
これでmが求まり、flagが出ました。
from Crypto.Util.number import * from itertools import islice from math import gcd from random import randint ELEMENT_LEN = 16 def primes(): num = 2 while True: prime = 1 for i in range(2, num): if num%i == 0: prime = 0 if prime: yield num num += 1 class Element: def __init__(self, n): self.n = Element.reduce(n) def __str__(self): return str(self.n) def __add__(self, other): return Element(self.n*other.n) def __eq__(self, other): return self.n == other.n def __mul__(self, n): if type(n) == int: ret = Element(1) for c in "{:0128b}".format(n): ret += ret if c == '1': ret += self return ret if type(n) == Element: ret = Element(1) primelist = list(islice(primes(), ELEMENT_LEN)) for i, num in enumerate(primelist[::-1]): cnt = 0 temp = n.n while gcd(temp, num) > 1: cnt += 1 temp //= num for c in "{:08b}".format(cnt): ret += ret if c == '1': ret += self return ret @staticmethod def encode(b): assert len(b) <= ELEMENT_LEN ret = 1 for i, num in enumerate(primes()): if i >= len(b): return Element(ret) ret *= num**b[i] @staticmethod def reduce(n): if n == 0: return 0 primelist = list(islice(primes(), ELEMENT_LEN)) for i, num in enumerate(primelist): while n % (num**256) == 0: n //= num**256 if num != primelist[-1]: n *= primelist[i+1] return n gen = (省略) apub = (省略) bpub = (省略) ct = (省略) Primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53] assert len(Primes) == 16 def frame(x): ret = [] for pri in Primes[::-1]: cnt = 0 while True: if x%pri == 0: cnt += 1 x //= pri else: break print(pri,cnt) ret.append(cnt) assert x == 1 return ret #gen, apub, bpubを素因数分解 print("gen") gg = frame(gen) print() print("apub") aa = frame(apub) print() print("bpub") bb = frame(bpub) #256進数方式で値にする Gen = 0 for G in gg: Gen *= 256 Gen += G print(Gen) Apub = 0 for A in aa: Apub *= 256 Apub += A Bpub = 0 for B in bb: Bpub *= 256 Bpub += B Gen_inv = inverse(Gen,pow(256,16)) assert (Gen_inv*Gen)%pow(256,16) == 1 #akey, bkeyを求める akey = (Apub*Gen_inv)%pow(256,16) bkey = (Bpub*Gen_inv)%pow(256,16) print(akey) print(bkey) gEn = Element.encode(b"+h3_g3n3ra+0r_pt") s = gEn*akey*bkey print(s) # sの値 S = (省略) ss = frame(S) print(ss) CT = frame(ct) print(CT) Ss = 0 for tmps in ss: Ss *= 256 Ss += tmps Ct = 0 for tmpct in CT: Ct *= 256 Ct += tmpct s_inv = inverse(Ss,pow(256,16)) assert (s_inv*Ss)%pow(256,16) == 1 m = Ct*s_inv print(m%pow(256,16)) print(long_to_bytes(m%pow(256,16))[::-1])
ictf{M1st3rRob0t_2045}
Problems&solver
Lexington Informatics Tournament CTF 2021 writeup
久しぶりにwriteupを書きます。サボっていたわけではなく、一問も解けないCTFが続いたんです…。
Result
Writeup
7 More Caesar Salads
Here’s an easy Crypto problem, try to decipher mshn{Dlsjvtl_Av_Jyfwavnyhwof}
問題名からCaesar暗号のようですね。以下のサイトで試してみたらROT19で上手くいきました。
flag{Welcome_To_Cryptography}
Zzz
Oh no, somebody shuffled the alphabet, can you help us restore the message? Note that the flag is not wrapped with flag{}, so you will have to do that yourself.
ファイル：zzz.txt
アルファベットをシャッフルしたと問題文にあるので、換字式暗号です。quipquipの出番です。
ここに、zzz.txtの内容を入れてsolveをクリックすると最初の文章がflagになります。flag{}で囲ってsubmitします。
flag{HOW_DO_YOU_KNOW_YOU_ARE_NOT_SLEEPING}
RSA Improved
The standard RSA only uses 2 prime factors, way too insecure. Let’s improve it by using more factors! More is better, ...right?
ファイル：rsa_improved.py, output.txt
問題文から、multiple primes RSAであることが予測できます。トーシェント関数φ(n)は(nを構成する素数-1)の積になります。nをfactorDBなどに投げると簡単に素因数分解できました。予想通り、素数が3個以上でした。問題ファイルからも分かりますね。
from Crypto.Util.number import * n = (省略) e = 65537 ct = (省略) N = [2151055861, 2319991937, 2341310833, 2391906757, 2448497717, 2493514393, 2586983803, 2758321513, 2784469417, 2816940109, 2865965429, 3092165243, 3218701459, 3438516511, 3526137361, 3663803701, 3673658161, 3789550043, 3866428117, 3919632263, 4147385899] phi = 1 for nn in N: phi *= (nn-1) d = inverse(e,phi) m = pow(ct,d,n) print(long_to_bytes(m))
flag{rsa_1s_4_pr3tty_imp0rt4nt_crypt0_4lg0r1thm}
Geometry is Fun!
We all love GEOMETRY, let's reminisce of all the times our teacher told us to find how large a certain figure is! Remember, Geometry teachers are bad at encrypting messages so the encryption method is not hard :D
(Note that the graphs may not be precise - only use angles/lengths notated in the diagrams)
ファイル：GeoIsFun.png
何だこの問題は。
問題文を読むと、とりあえず面積を求めよとのこと。やってみましょう。
左上から右に、上から下に(A) ~ (H)と名付けます。
(A)
基本問題ですね。
3 × 6 ÷ 2 = 9
(B)
正三角形で一辺の長さが分かっています。その長さが2重根号になっています。
正三角形の高さは、(辺の長さ) × (√3/2) です。
√(16√3) × { (√(16√3) ) × (√3/2) } ÷ 2
= { √(16√3) × √(16√3) } × (√3/2) ÷ 2
= 16√3 × (√3/2) ÷ 2
= 16 × 3 ÷ 2 ÷ 2
= 12
なんと整数になりました。他の問題もそうなるのかなと予想。
(C)
(B)と考え方は同じですね。
√(10√3) × { (√(10√3) ) × √3 } ÷ 2
= { √(10√3) × √(10√3) } × √3 ÷ 2
= 10√3 × √3 ÷ 2
= 10 × 3 ÷ 2
= 15
(D)
(A) と同じですね。
22/3 × 6 ÷ 2 = 22
(E)
これもまた簡単ですね。
1 × 10 ÷ 2 = 5
(F)
三辺の長さだけが分かっている二等辺三角形ですね。
ヘロンの公式を使います。
ヘロンの公式 面積S = √(s×(s-a)×(s-b)×(s-c) ) ただし、s = (a+b+c)/2, a,b,c は辺の長さ
これを適用します。
s = ( 5√2 + 5√2 + 2)/2 = 5√2 + 1 S = √(s×(s-a)×(s-b)×(s-c) ) = √( (5√2 + 1) × (5√2 + 1 - 5√2) × (5√2 + 1 - 5√2) × (5√2 + 1 - 2) ) = √( (5√2 + 1) × (5√2 - 1) ) = √( (5√2)×(5√2) - 1×1 ) = √(50 - 1) = 7
(G)
三角形の面積を求めるのに、三角関数を使った方法あったなと思いググる。
1/2 × 4 × 5 × sin30 = 5
(H)
直角二等辺三角形で、斜辺の長さだけ分かっています。
(一辺の長さ) = 2√15 × √2/2 = √30 (面積) = √30 × √30 ÷ 2 = 30/2 = 15
復号
以下の値が出揃いました。
9, 12, 15, 22, 5, 7, 5, 15
幾何学の先生だから暗号化方式はそんなに難しくないよ、と問題文にあります。
最大値が22であるので、1~26がa~zに対応しているのでは？とエスパー。復号してみると意味のある文になったビンゴ。
flag{ilovegeo}
Scottish Flag
Was is it Scottish or British? Oh who remembers these days
ファイル：scottish_flag.py, output.txt
scottish_flag.pyを読み、何が出力されているか見ると以下の式が成り立ちます。
t0, t1, t2 : 出力 ct1, ct2 : 求めたいflag a0, a1 : プログラム内の値。a1は未知。 ct1^2 + (ct2-a0)^2 = t0 ・・・ (a) (ct1-a1)^2 + ct2^2 = t1 ・・・ (b) (ct1-a1)^2 + (ct2-a0)^2 = t2 ・・・ (c)
未知数がct1, ct2, a1の3つに対し3式あるので、これは式同士を足し引きすれば求められますね。
ct2を求める
(b) - (c) ct2^2 - (ct2-a0)^2 = t1 - t2 2×a0×ct2 - a0^2 = t1 - t2 ct2 = (t1-t2+a0^2) / 2×a0
ct2が求められました。これをlong_to_bytes()すると、
b'mak35_g00d_pro6I3m}'
となり、方向性は間違っていないようです。
ct1を求める
(a) ct1^2 + (ct2-a0)^2 = t0 ct1 = √(t0 - (ct2-a0)^2 )
右辺のルート内を計算し、平方数であることを確認。二乗根を取ってlong_to_bytes()するとflagの前半が出ました。
b'flag{6r1t15h_cr0s5_'
from Crypto.Util.number import * import gmpy2 t0 = 11167218166350596634324970518743041384610511755703179147618262518561344714067317278672955466 t1 = 11167218166350596634324970522379402989880404344356627706412007661522873314144716029510966061 t2 = 11167218166350596634324970517500867796567936885101366588743135261789294824144716029510966061 a0 = 1000000000000000000 c2 = (t1-t2+a0*a0) // (2*a0) print(long_to_bytes(c2)) cc1 = (t0-pow(c2-a0,2)) print(cc1) c1, ch = gmpy2.iroot(cc1,2) assert ch print(long_to_bytes(int(c1))) flag = long_to_bytes(int(c1)) flag += long_to_bytes(c2) print(flag)
flag{6r1t15h_cr0s5_mak35_g00d_pro6I3m}
Leftovers
Leftovers are bad, but I guess at least they help the environment by not wasting food.
ファイル：Leftovers.py, output.txt
Leftovers.pyが少し複雑ですが、読み解いて行きましょう。
変数gはPRNGクラスのインスタンスで、そのフィールドの一つであるseedにはflagを数値にしたものが入ります。
配列resには、1~4e10内で乱数を生成させ、その値未満の素数でseedを割った余りがどんどんappendされ、長さは12です。これはoutput.txtにあります。
はい、flagを特定するには中国剰余定理を用います。
生成する乱数ですが、最初にシードを1337として初期化しているので同じものを生成できます。中国剰余定理はsympyにあるので、それを使えば楽勝です。
from sympy.ntheory.modular import crt import random from Crypto.Util.number import * import sympy import math val = [16751036754, 7441743891, 13537409447, 12455208971, 16901669565, 15060041617, 15538665605, 192375025, 2176355740, 21877084789, 3184436468, 13214581420] random.seed(1337) mod = [] for i in range(len(val)): mod.append(sympy.prevprime(random.randint(1,4e10))) flag, MOD = crt(mod,val) flag = int(flag) print(long_to_bytes(flag))
なんとこれでは意味ある文字列になりませんでした…。思い違いがあるのかと思ったけど、それではなさそう。
Leftovers.pyに怪しげなassert文がありました。
assert(math.log10(ct) <= 128)
上のプログラムで求めているのは、mod[i]で割ると余りがval[i]になる最小値を求めています。何も最小値が答えとは限りません。求めた最小値に、Π mod[i] (= mod[0]×mod[1]×...×mod[n-1]) をどんどん足していって、long_to_bytes()してb"flag"が含まれていたらそれを出力してプログラムを終わらせます。
from sympy.ntheory.modular import crt import random from Crypto.Util.number import * import sympy import math val = [16751036754, 7441743891, 13537409447, 12455208971, 16901669565, 15060041617, 15538665605, 192375025, 2176355740, 21877084789, 3184436468, 13214581420] random.seed(1337) mod = [] for i in range(len(val)): mod.append(sympy.prevprime(random.randint(1,4e10))) flag, MOD = crt(mod,val) flag = int(flag) while math.log10(flag) <= 128: FLAG = long_to_bytes(flag) flag += MOD if b"flag" in FLAG: print(FLAG) break
flag{ch1nese_f00d_l3ft0v3r_th30r3m_1s_v3ry_d3l1c10u5}
Problems&Solver
おわりに
最近研究の方も忙しくなり、CTFに参加しても最初の一問がすぐ解けないとそっとPCを閉じていました。CTFとの両立頑張りますが、期待はしないでください(笑)
久しぶりにwriteup書いたので、いつもの形式が違うとかあったらすみません
