全般
問題数が多くて雑になりました。ごめ
わからない場合は直接私に訊いてください。DiscordやTwitterでDMを送ってください。
約束
- 配布ファイルにある大きな数字や配列などは省略して示しています。
>>>で始まっている行はPythonのインタラクティブモードでの入力を表しています。- 特に断りがない場合、全ての解答コードはPython3で書かれています。
- RSAの問題で出てくる、$m,e,c$はそれぞれ平文、公開鍵、暗号文を表します。
ライブラリ
次のPythonライブラリを使います。
これらのライブラリは、pip install pycryptodome gmpy2でインストールできます。
便利ツール
Beginner
序盤の簡単な問題
welcome
README.mdに書いてあります。sctf{welcome_to_shiba_ctf}
radix starter 1
こういうちょっとした計算はPythonのインタラクティブモードが便利です。
sctf{10010}
radix starter 2
sctf{11010100001011}
radix starter 3
1
2
| >>> int("10111",2)
23
|
sctf{23}
radix starter 4
sctf{52394}
radix starter 5
sctf{59}
radix starter 6
sctf{61}
radix starter 7
1
2
| >>> int("8128",9)
5939
|
sctf{5939}
radix starter 8
$1$の後ろに$0$が$a$個続く$2$進数は、$10$進数で$2^a$です。よって、$2^64$が答えです。sctf{18446744073709551616}
radix starter 9
Classic Cipher
だいたいの古典暗号は、ネットにソルバが転がっています。
古典暗号は、現代から見れば脆弱で、アソビのようにも感じますが、歴史的背景はかなり興味深いです。計算機を使わないからこその、アルゴリズムの創意工夫も見られて面白いです。
Romantic
シーザー暗号です。$14$文字後ろにずらします。sctf{kimagur3_r0m4ntic}
SOS
シンプルなモールス符号です。sctf{LICENSE}
No meaning
換字式暗号です。
1
| classic ciphers are encryption methods that have been used for centuries to secure secret messages. these ciphers are based on mathematical algorithms, transforming plaintext into unreadable ciphertext, readable only by those with the decryption key. examples of classic ciphers include the caesar cipher, which replaces each letter in the plaintext with a fixed number of positions down the alphabet; the vigenere cipher, which uses multiple caesar ciphers based on a keyword; the playfair cipher, which encrypts pairs of letters using a 5x5 grid; the rail fence cipher, which rearranges plaintext letters; and the enigma machine, which was famously cracked by allied codebreakers during world war ii. by the way, here is flag: sctf{plaintext_letters_substituted_with_different_ciphertext_letters}
|
Zigzag
レールフェンス暗号(Rail Fence Cipher)です。
`sctf{r@1l_f3nc3_c1ph3r_15_@_53cur3_4nd_345y_70_und3r574nd}
以下のようにジグザグに文字を配置して1行ずつ読む、という暗号化です。
1
2
3
4
5
| s l c
c 1 _ _
t @ f 3
f r 3 c
{ n
|
Cylinder
スキュタレー暗号です。$n$文字飛ばしで読むと文が出てきます。
改行して縦読みすると簡単に解けます。
1
2
3
4
| s{__05p
cy440t3
t0r_d3r
fu3g_p}
|
sctf{y0u_4r3_4_g00d_5t3pp3r}
Square
画像の出典でバレていますがヴィジュネル暗号(Vigenère cipher)です。シーザー暗号の改良版で、文字ごとにずらす数を変えます。この問題はKEYが分かっているので、デコードするだけです。
sctf{supercalifragilisticexpialidocious}
AtCipher
アトバシュ暗号(Atbash cipher)です。aをz、bをy、cをx、というようにアルファベットを変換します。この暗号はエンコードとデコードで行う操作が同じです。
sctf{just_like_affine_cipher}
Digital Crypto
現代暗号に分類するまでもない、エンコード形式などに関する問題です。
Numbers
文字コード(ASCII)です。sctf{Numbers_are_a_common_language}
long_to_bytes
問題文の通りです。
sctf{pycryptodome_is_one_of_the_most_important_library}
Compression
base64です。sctf{base64_enc0ded_s7ring_15_being_one}
Compression 2
base32です。sctf{B@s3_33_15_@v3ry_5ecure_3nc0d1ng_f0r_m@nypurp053s_bu7_1t_m@y_n07_b3_7h3_f@s73s7_0n3_f0r@ll_54tu@710n5}
Kanji
めっちゃ大規模なシーザー暗号です。1文字目をsと仮定したときにずらす数が決定するので、それを使ってデコードします。
1
2
3
4
5
6
| S = "籼籬籽籯粄籛簹籽籉籽簺簹籷籨簺簾籨簾簺籶籹籵簼籨簯簼籯籯簼籬籀簺籿簼粆"
k = ord(S[0])-ord('s')
for c in S:
print(chr(ord(c)-k),end = "")
print("")
|
sctf{R0t@t10n_15_51mpl3_&3ff3c71v3}
Numbers 2
8進数で表された文字コードです。数字に$8$以上が出現しないところに注目です。sctf{0c74l_numb3r5_@r3_7h3_b3s7_w@y_70_3nc0d3_d@73}
Emoji cipher
「Kanji」と全く同じ解き方ができます。sctf{3m0j1_com3_fr0m_j4pan}
http
URLエンコードです。sctf{日本語でもok}
Sanity Check
日本人には読めないフォントElectroharmonixで書かれた文章です。注意深く見るとアルファベットが見えてきます。どうしても読めなければこのフォントのアルファベット表と比較しましょう。SCTF{YOU_ARE_NOT_JAPANESE_LOL}
Numbers 3
15進数です。fが存在しないところに注目です。
1
2
3
| >>> x = int("495c11db788574a62d038c125c688b9976c81c75370b9de35d1ac9da9a95b39591ea51cc3acd660b1804a44a743a443490826847dc9947d0c7067ed9dd7",15)
>>> from Crypto.Util.number import long_to_bytes
>>> long_to_bytes(x)
|
sctf{7h3_r4d1x_15_1mp0rtant_and_1m_5orry_ab0u7_7h15_pr0blem}
酷い問題ですね(私は好きです)
Glitch
文字コードをうまい感じに扱うと解読できます
1
2
3
4
5
6
7
8
9
| S = open("glitch.txt","r").read().encode("unicode_escape")
T = S.decode("utf-8")
i = 0
while i < len(T):
if T[i] == "\\":
i += 6
else:
print(T[i],end="")
i += 1
|
Unicode can be used to represent a wide variety of characters. One of them is the combining character system. Here is an example of a long flag: sctf{V0yag1ng_Thr0ugh_Th3_Unchart3d_Gl1tch3s_0f_Th3_C0sm0s_1n_Pursu1t_0f_H1dd3n_R3v3lat10ns_and_Unv34l1ng_th3_Myst3r13s_of_Th3_Unkn0wn_Un1v3rs3}
zzzzzzzzzzzzzz
手抜き問題。暗号化スプリクトは以下の通りです。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| from random import shuffle
S = "sctf{h1d3_4nd_533k_j0yfu1_3xpl0r4t10n}"
T = "567f[HiDe-4nD-sEeK-JoyFUl-eXP1oRa7ioN]"
C = ""
for i in range(len(S)):
F = []
for j in range(18):
F.append(S[i])
for j in range(17):
F.append(T[i])
shuffle(F)
C += "".join(F)
print(C)
|
Ultimate Caesar
線形変換を複数合成したその結果も線形変換です。例えば、$f(x) = 2x+5$と$g(x) = 3x+7$を合成すると、$g(f(x)) = g(2x+5) = 3(2x+5)+7 = 6x+22$となり、線形変換のままです。
さらに、この問題は$\pmod 65537$で計算しているので、線形変換$ax+b$の$a,b$はどちらも$0$以上$65536$以下の整数です。$a$を全探索し、1文字目がsとなるような$b$を計算すれば、全通りの線形変換を試せます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| c = [47799, 18389, 14535, 725, 21466, 1781, 25216, 25632, 37871, 52855, 39626, 43890, 63798, 13679, 28100, 62877, 55237, 3163, 35047, 42930, 18652, 36817, 49095, 15836, 31228, 36576, 11850, 37110, 38663, 19959, 38874, 51360, 15748, 12843, 57056, 9250, 32197, 37439]
l = 65537
for a in range(0,l):
d = 0
b = (c[0] - ord("s"))%l
m = ""
for p in c:
d = (a*d + b)%l
m += chr((p-d)%l)
if m.startswith("sctf{") and m.endswith("}"):
print(m)
print(a,b)
break
|
この問題を解くのにparamsは必要ありません。
sctf{c0mp13x1ty_4nd_5urf1ng_7h3_w4v3s}
Basic Math
数学(主に数論)に関する基本的な問題です。
Equation 1
割り算するだけです。
1
2
| >>> 162030664//3158
51308
|
Equation 2
二分探索で求めます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| # x^2
x2 = 3386439659231533906596
# xを2分探索で探す
l = 0
r = x2
while r - l > 1:
m = (l + r) // 2
if m * m > x2:
r = m
else:
l = m
print(l)
|
Pythonの標準である関数は誤差が出ることがあるため使わない方が良いです。
Equation 3
同じく二分探索で求めます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| from Crypto.Util.number import *
x16 = #
# xを2分探索で探す
l = 0
r = x16
while r - l > 1:
m = (l + r) // 2
if m**16 > x16:
r = m
else:
l = m
print(long_to_bytes(l)) # sctf{r00t_of_unity}
|
Equation 4
関数が単調増加であれば二分探索が使えます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| from Crypto.Util.number import *
def f(x):
return x**8 + x**4 + x**2
fx = #
# xを2分探索で探す
l = 0
r = fx
while r - l > 1:
m = (l + r) // 2
if f(m) > fx:
r = m
else:
l = m
print(long_to_bytes(l)) # sctf{1ncr34s3_y0ur_5k1ll5}
|
Math Class 1
愚直に計算します。
1
2
| >>> sum([a for a in range(1,2023+1)])
2047276
|
Math Class 2
等差数列の和の公式を使います。
$10^{12}\times (10^{12}+1)/2 = 500000000000500000000000$
Math Class 3
下$10$桁は$10^{10}$で割った余りを求めれば良いです。
1
2
| >>> pow(8128,123456789,10**10)
328442060
|
Math Class 4
$x$の最大でも$157$未満なので、全探索できます。
1
2
3
4
5
6
7
| a = 29
b = 1
m = 157
for x in range(1,m):
if (a*x)%m == b:
print(x)
break
|
sctf{65}
Math Class 5
ユークリッドの互除法を使います。
1
2
3
4
5
6
7
8
| def GCD(a, b):
if a == 0:
return b
return GCD(b % a, a)
a = 14930888045225624011
b = 8204203643581470607
print(GCD(a, b))
|
sctf{3806516863}
Math Class 6
拡張ユークリッドの互助法で逆元を求めます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| def inverse(a, m):
m0 = m
y = 0
x = 1
if m == 1:
return 0
while a > 1:
q = a // m
t = m
m = a % m
a = t
t = y
y = x - q * y
x = t
if x < 0:
x = x + m0
return x
a = 12345678
m = 998244353
print(inverse(a, m))
|
あるいは、今回はmodが素数なのでフェルマーの小定理を使っても解けます。
1
2
3
| a = 12345678
m = 998244353
print(pow(a,m-2,m))
|
sctf{749734780}
Math Class 7
中国剰余定理を使います。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| from Crypto.Util.number import long_to_bytes, bytes_to_long, inverse, getPrime
def crt(a, m, b, n):
# nx = 1 (mod m)
# my = 1 (mod n)
# anx + bmy は mでmで割ったあまりがa, nで割ったあまりがbになる
x = inverse(n, m)
#x = pow(n,-1,m)
y = inverse(m, n)
return (a * n * x + b * m * y) % (m * n)
m = 591233
n = 950753
a = 23
b = 19
g = crt(a,m,b,n)
print(g)
|
sctf{549251909625}
Block Cipher
ブロック暗号に関する問題です。
AES starter
問題文の通りにやります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| # AES
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Random import get_random_bytes
from Crypto.Util.strxor import strxor
iv = 0xffffffffffffffffffffffffffffffff
iv = long_to_bytes(iv)
key = 0x01230123012301230123012301230123
key = long_to_bytes(key)
enc = 0xf47fda4253994089ee89c8f0b76d3991d36c9085cb0ffaa06781fb56dd7fe9a4
enc = long_to_bytes(enc)
dec = AES.new(key, AES.MODE_CBC, iv).decrypt
print(unpad(dec(enc), 16))
|
sctf{iv_m34n5_f0ur}
ECB starter
ECBモードは、16バイトごとに暗号化が独立しています。今回の暗号文は32バイトあるので、2ブロックに分けてそれぞれ復元すれば良いです。
b6506e08641d53366fdbfa35e8549e24をdecryptすると736374667b4543425f69735f7430305fd7666bdf3cbad130ddeb8eb1d0c7b58aをdecryptすると7765616b7d0b0b0b0b0b0b0b0b0b0b0b- これらを繋げて16進数デコードすると
sctf{ECB_is_t00_weak}
他にも、暗号文を余分に伸ばして回避する方法もあります。
OFB starter
OFBモードは暗号化と復号がブロックごとで同じ操作です。
よって、次のようにして復号できます。
- 適当な
ivを用意(例えば00000000000000000000000000000000)してdecryptして0e1e6412ca1533f9681c64b68dc8817e85c7508d4a3d6ee0570cf4b53adf723102 0e1e6412ca1533f9681c64b68dc8817e85c7508d4a3d6ee0570cf4b53adf723102をもう一度decryptすると736374667b57307264355f756e6c33347368316e675f637233347431763174797d7a3cd23dca7751c2491347e7e264fd76747220244d2c8b26d2373a583913096fcb- デコードすると
sctf{W0rd5_unl34sh1ng_cr34t1v1ty}
CBC starter
まず、暗号文を16バイトごとに分割します。
1
2
3
| 958fd2d255b337bb0c3d8c95fbcbc56a
6793aad6cb36a4c9bbc6bfc1791ac3f0
dc5b1476371e1333927ebdbc9d2ab27f
|
- はじめの16バイトを与えられた
ivを使ってdecryptするとsctf{d1sc0v3r1ngが得られます。 - 次の16バイトは、
ivを958fd2d255b337bb0c3d8c95fbcbc56aにすれば_CBC_m0d3_1n_cr1が得られます。 - 最後の16バイトは、
ivを6793aad6cb36a4c9bbc6bfc1791ac3f0にすればpt0}が得られます。
よって、フラグはsctf{d1sc0v3r1ng_CBC_m0d3_1n_cr1pt0}です。
Padding Escapade
コードは次のように暗号化しています
- フラグの長さを$L$として、$i=1,2,\dots,L$に対して、次を行う
i文字目までを16バイトの倍数になるようにパディングし、enc配列に追加- フラグの先頭
i文字目にランダムな8bitをxor
encの順序をシャッフルして出力
そもそも、paddingという操作は「データを16の倍数バイトの長さに延長する」という操作ですが、unpaddingという操作によって、「16の倍数バイトのデータを元の状態に戻す」ことができます(paddingという操作によって、元の長さの情報は失われていないのです)。
ですから、unpaddingをすればその文字列の長さから何文字目の情報であるかがわかります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| from Crypto.Util.Padding import unpad
from Crypto.Util.number import long_to_bytes, bytes_to_long
from random import getrandbits, sample
enc = # 省略
ct = []
for e in enc:
ct.append(long_to_bytes(e))
# unpad
m = [0] * len(ct)
for c in ct:
x = unpad(c, 16)
m[len(x)-1] = chr(x[-1])
print("".join(m))
|
sctf{Unpadd1ng_1s_un1que1y_def1n3d}
CBCモードのdecryptの手順を見ると、最初の16バイトは最後にivをxorしていることがわかります。最後のxorをこちら側でやってしまえばよいです。次の手順で解きます。
- 暗号文を
ivを00000000000000000000000000000000としてdecryptするとeafafcee0c030e554e6316135d5174335f316e5f7468335f736b377d04040404が得られる。- 後半16バイトをデコードするとフラグの一部
_1n_th3_sk7}が得られる。
- 前半16バイトを
ivの99998888777766661111222233334444とxorを取ることで、736374667b7468335f7234316e623077になり、デコードするとsctf{th3_r41nb0wが得られる。
よって、フラグはsctf{th3_r41nb0w_1n_th3_sk7}です。
Modern Crypto
現代暗号に関連する問題です。CTFのCrypto問題の多くは、このカテゴリに属します。
XOR starter
keyが暗号化スクリプトに直書きされています(多分普通にミス)ので、それを使って復号します。
1
2
3
4
5
6
7
8
9
| c = [66, 82, 69, 87, 74, 105, 126, 99, 110, 89, 80, 66, 110, 88, 95, 69, 2, 67, 2, 66, 69, 88, 95, 86, 110, 65, 67, 1, 65, 84, 67, 69, 88, 84, 66, 76]
for key in range(256):
flag = ""
for i in c:
flag += chr(i ^ key)
if "sctf" in flag:
print(flag)
break
|
sctf{XOR_has_int3r3sting_pr0perties}
XOR Maze
式の上から順に$a,b,c,d$とすると、
- $c \oplus d = C$
- $b \oplus (c \oplus d) = b \oplus C = A\oplus B \oplus C \oplus D$
- $a \oplus (b \oplus (c \oplus d)) = a \oplus A\oplus B \oplus C \oplus D = x$
よって、$a\oplus b\oplus c\oplus d$を計算すれば良いです。sctf{XOR-XOR-XOR}
XOR XOR XOR
暗号化した結果をそのまま16進数デコードするとsctf{Par17y_15_an_imp0rt4n7_prop3rty}が得られます。つまり暗号化しているように見えて、何も変化していません。
これは、$0$から$2^32-1$を$2$進数にしたときに、各ビットで必ず偶数回1が出現していることによります。
Foresight? 1～4
Foresight? 4は他の問題を包含しているめ、それを解くコードだけ載せます。理論の説明は線形合同法のパラメータ推測を参照してください。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| from Crypto.Util.number import *
def linear_random_crack(rands):
t = [rands[i+1]-rands[i] for i in range(len(rands)-1) ]
s = [(t[i+2]*t[i]-t[i+1]*t[i+1]) for i in range(len(t)-2) ]
m = 0
for a in s:
m = GCD(m,a)
a = ((t[2]-t[1]) * inverse(t[1]-t[0],m))%m
b = (rands[1] - a*rands[0])%m
return a,b,m
x = [747295850, 164867235, 2576857841, 3363332730, 1094604011, 2843336746, 1656975446, 397591104, 3296405267, 3516873680]
cipher = [44926602, 2937937393, 174436646, 2491180612, 315256230, 3211193071, 568689060, 93639370, 1909387862, 3075542788, 1540942839, 198180033, 727016228, 2502033293, 1802750036, 569086897, 375047049, 1629464891, 1407370985, 477707872, 774404513, 2716137718, 1840779688, 1191662382, 3504379912, 748125320, 1658575995, 928538355, 3070989414, 2468916650, 2782012797, 610961179, 3682269712, 2770385176, 2785363482, 1486741234, 2524249046, 1721210836, 3665494948, 2796298560, 431561753, 2330491191, 2141216717, 3524354070, 1129782399, 3057714851, 2038862641]
a,b,m = linear_random_crack(x)
print(a,b,m)
flag = ""
for c in cipher:
flag += chr(c ^ (a*x[-1]+b)%m)
x.append((a*x[-1]+b)%m)
print(x)
print(flag)
|
これを使うと、各問題のフラグは
- 1:
sctf{1_0f_th3_w0r$t_rand0m_numb3r_g3n3r@tor5} - 2:
sctf{d0_n0t_u5e_l1near_c0n9ruent1al_gener@t0r5} - 3:
sctf{l1near_c0n9ruent1al_gener@t0r_is_n0t_5@fe} - 4:
sctf{b3_c4r3ful_w1th_l1n34r_c0ngru3nti4l_g3n3r4t0r}
Foresight? Final
一つ飛ばしの場合、漸化式が$x_{n+2} = ax_{n+1} + b = a^2 x_n + ab + b$となります。新たに$A=a,B=ab+b$とおけば、$x_{n+2} = Ax_n + B$となり、これはForesight? 4と同じ問題になります。
$A,B$、そしてmodの$m$が求まれば、あとは$A=a^2,B=ab+b$を解けば良いですが、ここで注意なのはこの方程式は$\mod m$で解く必要があることです。$a$を$A$からもとめるには、modの世界で平方根を取る必要があります。
今回は、$m=3 \pmod 4$であるため、$A^{\frac{m-3}{4}}$の逆元が$A$の平方根になります。
(そうでない場合はこの手順では求められませんが、別のアルゴリズムを用いることで求めることはできます。Cipolla’s algorithmや、Tonelli-Shanks algorithmなどがあります。)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| from Crypto.Util.number import *
from gmpy2 import iroot
def mod_root(a,p):
# x^2 = a mod pとなるようなxを返す
assert p%4 == 3
k = (p-3)//4
x = inverse(pow(a, k, p),p)
assert (x**2 % p) == a
return x
def linear_random_crack(rands):
t = [rands[i+1]-rands[i] for i in range(len(rands)-1) ]
s = [(t[i+2]*t[i]-t[i+1]*t[i+1]) for i in range(len(t)-2) ]
m = 0
for a in s:
m = GCD(m,a)
a = ((t[2]-t[1]) * inverse(t[1]-t[0],m))%m
b = (rands[1] - a*rands[0])%m
return a,b,m
x = [
cipher = [
A,B,m = linear_random_crack(x)
a = mod_root(A,m)
b = B*inverse(a+1,m)%m
print(a,b,m)
flag = ""
for c in cipher:
flag += chr(c ^ (a*x[-1]+b)%m)
x.append((a*x[-1]+b)%m)
print(flag)
|
sctf{th3_s33r_0f_b3y0nd_c4n_p3rceiv3_th3_1nvis1bl3}
Modular Puzzle
modはとりあえず無視します。この問題の趣旨は次のとおりです。
- $v=g(a^2+b^2+c^2)$を次の値から求める
次のように求めることができます。
- $ga^2 = st^{-1}u$
- $gb^2 = stu^{-1}$
- $gc^2 = s^{-1}tu$
- よって、$v = g(s^{-1}tu + st^{-1}u + stu^{-1}) = stu(s^{-2}+t^{-2}+u^{-2})$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
from random import getrandbits
def GCD(a, b):
while b:
a, b = b, a % b
return a
p =
s =
t =
u =
ct =
A = s * t * u % p
gc2 = A * pow(s, -2, p)
ga2 = A * pow(t, -2, p)
gb2 = A * pow(u, -2, p)
v = (ga2 + gb2 + gc2) % p
m = pow(ct, pow(v, -1, p - 1), p)
print(long_to_bytes(m))
# sctf{unv34lin9_th3_p0w3r_0f_m0dul4r_1nv3rs3s_1n_crypt0}
|
ExpHash
長さ$1000$の配列が$4$つ与えられているので、全パターン試すと$10^{12}$通りになります。これは計算に時間がかかるので
高速な次のようなアルゴリズムを使います。求めたいパスワードのハッシュ値を$h$とします。
list1とlist2の全組み合わせのハッシュを計算してdict1に保存list3とlist4の全組み合わせのハッシュを計算してdict2に保存
ここで、重要な次の性質を使います。
- 長さ$N$の文字列$s$と文字列$t$のハッシュ値がそれぞれ$h_s,h_t$であるとすると、連結した文字列$s+t$のハッシュ値は$h_s + h_t \times base^{N} $となる
これにより、dict2の全ての要素$h_2$について次の問題を解きます。
- $h_1+base^N \times h_2 = h$が成り立つ$h_1$を求める。
- $h_1 = h - base^N \times h_2$
- $h_1$が
dict1に存在するかを調べる
適切なデータ構造(プログラム上ではdictを使用)を使うことで上記の操作は$O(\log 10^6)$で行うことができます。
よって、この問題は、$X=10^3$とすると、$O(X^2 \log X^2)$で解くことができました。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
base = 48337
mod = 11135515903660432429
list1 = ['NveEp', # 省略
list2 = ['6nBxk', # 省略
list3 = ['fls3N', # 省略
list4 = ['TLpkV', # 省略
h = 10560284356650745449
def hash(s, base, mod):
ret = 0
for i, c in enumerate(s):
ret = (ret + ord(c) * pow(base, i, mod)) % mod
return ret
dict34 = {}
for s3 in list3:
for s4 in list4:
a = (hash(s3 + s4, base, mod) * pow(base, 10, mod)) % mod
dict34[a] = s3 + s4
for s1 in list1:
for s2 in list2:
l = (h - hash(s1 + s2, base, mod)) % mod
if l in dict34:
print(s1 + s2 + dict34[l])
print(hash(s1 + s2 + dict34[l], base, mod))
# sctf{xYDpuEYEeO8m5ZQxkmO5}
|
Staircase
問題ファイルのverify関数を使おうとすると、実行に非常に時間がかかってしまうので、別の方法を考えます。
問題ファイルのverify(a)関数では、a-1の階乗がaで割り切れるかどうかを判定しています。
この判定は、aが素数であるかどうかと同値です。なぜなら、
- $a$が素数ではない場合を考える
- $a=p_1^{e_1}p_2^{e_2}\dots p_k^{e_k}$と素因数分解できるとする
- $s = \lbrace p_1^{e_1}, p_2^{e_2}, \dots, p_k^{e_k} \rbrace $とすると、$s$の全要素の積は$a$である。
- 一方、$(a-1)!$は、$a$以下の全ての数の積であり、$s$の各要素は全て$a-1$以下であるため、$(a-1)!$は$s$の全要素の積で割り切れる。
という理由によります(簡単に言うと、$a$が合成数だったら$a$の約数が$1$から$a-1$の間に存在するよね、ということです)。
より詳しく知りたい場合はウィルソンの定理を御覧ください。
よってこの問題は、素数判定を$O(N)$から$O(\sqrt N)$に高速化することで解くことができます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| from gmpy2 import iroot
from Crypto.Util.number import isPrime
b =
c =
def verify(a):
return isPrime(a)
for i,a in enumerate(b):
if verify(a):
print(c[i], end="")
# sctf{unl0cking_th3_myst3r13s_0f_f4ct0ri4ls_4nd_th3ir_3xtr4ordinary_pr0p3rt13s}
|
Smidgen
$2^x$の上位$7$桁のみが与えられて、$x$を求める問題です。$x$が大きくなると桁数が大きくなり計算に非常に時間がかかるため、$\log$をうまく使って、上位7桁のみ求められないかを考えます。
以下、$\log$の底は$10$とします。
例えば、$1.234567 \times 10^{100}$という数は、上位$7$桁が$1234567$となります。これを対数で表すと、
$$
\begin{align}
\log(1.234567 \times 10^{100}) &= \log(1.234567) + \log(10^{100}) \\
&= \log(1.234567) + 100\log(10) \\
&= 100 + \log(1.234567)
\end{align}
$$
となります。$\log(1.234567)<1$ですので、対数を取った値の小数部分に各桁の情報が入っています。よって、
$$
10^{\log(1.234567)} = 1.234567
$$
と累乗を行うと、数字の復元ができます。
このように、$2^x = a \times 10^b$と考えれば、$\log(2^x) = \log(a) + b\log(10)$となり、$10^{\log(a)}$の小数点以下6桁までが、$2^x$の上位$7$桁と一致します。
pythonのlog10関数の精度が気になりますが、今回は小数点以下6桁まで求めれば十分ですので、問題ありません。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| from math import log10
from Crypto.Util.number import long_to_bytes
s = "1873119"
# 2^x の 上から7桁
def top7(x):
a = x * log10(2)
# aの小数部分を取り出す
b = a - int(a)
# 10^b を求める
c = 10 ** b
# 10^b の上から7桁を求める
d = int(c * 10 ** 6)
return d
x = 1
y = 1
while True:
if str(top7(x)) == s:
print(x)
print(long_to_bytes(x))
# break
x += 1
# PIN
|
RSA starter
やるだけです。RSAの説明はネットに山ほどあるので省略します。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| from Crypto.Util.number import long_to_bytes
p = #
q = #
n = #
e = 65537
c = #
phi = (p-1)*(q-1)
d = pow(e,-1,phi)
m = pow(c,d,n)
print(long_to_bytes(m))
# sctf{A_good_start}
|
Each RSA
$1$文字ずつ暗号化されているということは、各平文$m_i$は高々$128$以下の数であることがわかります。$x^e = c_i \pmod n$となるような$x$を全探索すれば良いです。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
n = #
e = 65537
cs = [ #
m = ""
for c in cs:
for i in range(256):
if c==pow(i,e,n):
m += chr(i)
break
print(m)
# sctf{it_is_sunday}
|
Small RSA
$e$が小さく$m^e < n $となっていると予想できます。実際に$3$乗根を取ると、平文が得られます。
1
2
3
4
5
6
7
8
9
10
11
| from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot
n = #
e = 3
c = #
m = iroot(c,e)[0]
print(long_to_bytes(m))
# sctf{this_looks_#short}
|
RUSH E
$100$回暗号化しているだけなので$100$回復号すれば良いです。ちなみに$(a^x)^y=(a^y)^x$なので$e$の順番はなんでも良いです。
1
2
3
4
5
6
7
8
9
10
11
12
| from Crypto.Util.number import long_to_bytes
p = #
E = [ #
c = #
phi = p-1
for e in E:
c = pow(c, pow(e, -1, phi), p)
print(long_to_bytes(c)) # sctf{Enigma_0f_Ethereal_Expl0ration}
|
2D Lagrange
$a,b,c$のうち、2つの値が求まれば残りの一つは定まります。次のソースコードでは$b,c$を全探索しています。
$a,b,c$が決定すれば、2次方程式になるので、解の公式や二分探索で解けます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
def function(a,b,c,x):
return a*x*x + b*x + c
x = 2911
y = 8337062002
ct = #
for b in range(3000):
for c in range(3000):
a = (y - b*x - c)//(x*x)
if function(a,b,c,x) != y:
continue
print(a,b,c)
# 二分探索で，f(x) = ctとなるxを求める
l = 0
r = ct
while r - l > 1:
m = (l + r) // 2
if function(a,b,c,m) >= ct:
r = m
else:
l = m
assert function(a,b,c,r) == ct
assert function(a,b,c,x) == y
print(long_to_bytes(r)) # sctf{brute_force_is_not_so_bad}
|
Common N RSA
$e_1, e_2$が互いに素であることから、$e_1x + e_2y = 1$となるような$x,y$が存在します。
そのような$x,y$を求め、$c_1^x \times c_2^y = m^{e_1x+e_2y} = m$となるので、$m$が求まります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| from Crypto.Util.number import bytes_to_long, long_to_bytes, inverse
n = #
e1 = 135879330917823239005274526173902941241
e2 = 110581307957357787004164255007822749852
c1 = #
c2 = #
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
g, a,b = egcd(e1,e2)
m = pow(c1,a,n)*pow(c2,b,n)%n
print(long_to_bytes(m)) # sctf{C0mm0n_N_15_0n3_0f_7h3_m057_345y_7o_f@c70r1z3_pr1m3_f@c70r5}
|
Many RSA
素数が$9$個しか用意されていないのに、$5$回の暗号化、すなわち$10$個の素数を使っているということは、
必ずある$n_i$と$n_j$が同じ素数を使っていることになります。よって、$n_i$と$n_j$の最大公約数を求めることで、ある素数$p$が求まります。
$i,j$は全探索すればよいです。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
e = 65537
n = [ #
c = [ #
def GCD(a, b):
if b == 0:
return a
return GCD(b, a % b)
for i in range(1, len(n)):
for j in range(i+1,len(n)):
if GCD(n[i], n[j]) != 1:
p = GCD(n[i], n[j])
q = n[i] // p
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
m = pow(c[i], d, n[i])
print(long_to_bytes(m)) # sctf{GCD_15_50_useful_in_m4th_4nd_cryp70_!}
|
Unbalance RSA
$n=p_1,p_2,\dots,p_k$のうち、$p_1,p_2,\dots,p_x ( x<k ) $だけが求まったとき、
$n^\prime = p_1p_2\dots p_x>m$であれば$n^\prime$を使って復号できます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
n = #
c = #
e = 65537
def factor(n):
p = []
for i in range(1<<24, 1<<26):
if n % i == 0:
p.append(i)
n //= i
return p
ps = factor(n)
phi = 1
n = 1
for p in ps:
phi *= p - 1
n *= p
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m)) # sctf{sti11_we4k_rs@}
|
CutRSA
$p,q$それぞれ$1024$うち、$p$は上位$512$bit、$q$は下位$512$bitだけわかっています。
- $n$の下位$1$bitは、$p$と$q$の下位$1$bitの積です。よって、$q$の下位$1$ビットがわかっているため、$p$の下位$1$bitが求まります。
- $n$の下位$2$bitは、$p$と$q$の下位$2$bitの積です。よって、$q$の下位$2$ビットと$p$の下位$1$bitがわかっているため、$p$の下位$2$bitが求まります。
- 以下同様に、$p$の下位$512$bitが求まります。
$p$が分かれば、$q$は$n/p$で求まります。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime
n = #
c = #
e = 65537
s = #
# sはpの上位$512$bitとqの下位$512$bitを結合したもの
mask = (1<<512) - 1
q = s & mask
p = (s >> 512) << 512
# pの下位ビットから決定していく
for i in range(512):
if (p*q) % (1<<(i+1)) == n % (1<<(i+1)):
pass
else:
p += 1<<i
q = n // p
assert p*q == n
phi = (p-1)*(q-1)
d = pow(e, -1, phi)
m = pow(c, d, n)
print(long_to_bytes(m)) # sctf{CUT_i5_@_U53FUL_L1NUX_C0MM@ND}
|
Insufficient RSA
求まるフラグがダミーのもの(flag{????????????????}みたいな文字列)になってしまうという問題の不備があります(要修正)
$m^{e_1e_2}$に$m^{e_1}$の逆元を掛け算していくと、
$$
\begin{align}
m^{e_1e_2} \times m^{-e_1} &= m^{e_1e_2 - e_1} \\
&= m^{e_1(e_2 - 1)} \\
m^{e_1e_2}\times m^{-2e_1} &= m^{e_1(e_2 - 2)} \\
\dots \\
m^{e_1e_2} \times m^{-ke_1} &= m^{e_1(e_2 - k)} \\
\end{align}
$$
$k$が$e_2-1$になったときに、$m^{e_1e_2} \times m^{-ke_1} = m^{e_1}$が成り立ちます。今回$e_2$はそこまで大きくないため、$k$を順に試していけば、$m^{e_2}$が求まります。
同じ手順を使えば、$m^{e_1}$も求まります。$e_1,e_2$が求まれば、あとはCommon N RSAと同じです。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime, inverse
n = #
c1 = #
c2 = #
c3 = #
# c1:m^e1 mod n
# c2:m^e2 mod n
# c3:m^(e1*e2) mod n
c1i = inverse(c1, n)
i = 0
c4 = c3
while c4 != c1:
c4 = (c1i * c4) % n
i += 1
e2 = i+1
c2i = inverse(c2, n)
i = 0
c4 = c3
while c4 != c2:
c4 = (c2i * c4) % n
i += 1
e1 = i+1
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
g, a,b = egcd(e1,e2)
m = (pow(c1,a,n)*pow(c2,b,n)) %n
print(long_to_bytes(m)) #
|
@Everyone
共通の$m,e$と異なる$n$に対するデータを複数得られる場合に使えるHastad Broadcast Attackをします。
$k$個の$c_i = m^e \pmod {n_i}$を満たす値の組$(n_i,c_i)$と$e$が与えられたとします。
これは、$m^e$に対して、中国剰余定理(Math Class 7を参照)の問題と一致しますので、次の条件を満たす$x$を求めることができます(簡単のため、全ての$n_i$が互いに素であるとします)。
$$
x = m^e \pmod {n_1n_2\dots n_k}
$$
このとき、$e\leq k$である場合、全ての$i$について$m<n_i$ですから、$m^e < n_1n_2\dots n_k$となり、単純に$x$の$e$乗根を取ることで、$m$が求まります。
今回の問題では、$e=11$の場合の$n$が$11$個以上得られるので、$e=11$のものだけを使って、Hasatd Broadcast Attackを行います。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| pub = [(#
from Crypto.Util.number import inverse, bytes_to_long, long_to_bytes, getPrime
from gmpy2 import iroot
"""
x = dict()
x[7] = 0
x[11] = 0
x[13] = 0
for n,e,c in pub:
# eを数える
x[e] += 1
"""
# e = 11のときのみ使う
def crt(a, m, b, n):
# nx = 1 (mod m)
# my = 1 (mod n)
# anx + bmy は mでmで割ったあまりがa, nで割ったあまりがbになる
x = inverse(n, m)
#x = pow(n,-1,m)
y = inverse(m, n)
return (a * n * x + b * m * y) % (m * n)
def multi_crt(A, M):
if len(A) == 1:
return A[0], M[0]
else:
a = A.pop()
m = M.pop()
b = A.pop()
n = M.pop()
A.append(crt(a, m, b, n))
M.append(m * n)
return multi_crt(A, M)
N = []
C = []
for n,e,c in pub:
if e == 11:
C.append(c)
N.append(n)
e11, M = multi_crt(C, N)
m = int(iroot(e11, 11)[0])
print(long_to_bytes(m))
# sctf{th3_unbr34k4bl3_v01c3_0f_h4st4d_br0adc4st_4tt4ck_unv34l1ng_th3_h1dd3n_s3cr3ts_0f_cr1pt0syst3ms}
|
Hyperdefensiveness
$k,b$がランダムな数で、各文字$m_i$について$(2^km_i+b)$が暗号化されています。$k$は$512$未満なので全探索可能ですが、$b$は$n$以下と非常に範囲が広いです。
フラグの初めの二文字はscであるとわかっているため、この情報が利用できないかを考えます。つまり、既知の$m_1,m_2,c_1,c_2,e,k,n$について($k$は全探索するので便宜上既知であるとする)、次の式を満たすような$b$を求めたいです。
$$
\begin{align}
(2^km_1+b)^e &= c_1 \pmod n \\
(2^km_2+b)^e &= c_2 \pmod n
\end{align}
$$
変形すると、
$$
\begin{align}
f(b) &= (2^km_1+b)^e - c_1 \pmod n \\
g(b) &= (2^km_2+b)^e - c_2 \pmod n
\end{align}
$$
という$2$つの多項式が$0$となるような$b$、すなわち根を求める問題になります。このような問題は、多項式の最大公約数を求めることで解くことができます(Franklin-Reiter’s Related Message Attackと呼ぶ)。
多項式の計算はsagemathに任せると便利です。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| n = 111514100148774326367705704736979222700401163624613214832624545719172770237899669582747006984030817853537084997757295711771232132521914358653635342045379037331503674931338739346404124271446163845765651229207102076432601166326800350688722515916583372070523688695222758956481368503534557433446349136015628686357
e = 7
cs = [36267140803452927179495057268448637938138995328162738572087076174220240409292283541262772017889475150655158065847142060266322895790122174113706941494516841596254131235045666942402107201191704864689684087893142094789041848673700495337259457092014502960338636410206960779545493988287354582365176480889241401397, 84177014604944804713431824977078430985039214840423548727302549935407939656001979736935056882466843836602458913229420653818014792087210619568737881610552000458150387886315505969718562202068244042324330912044030393635010283562361328009574502508818702705813189169328775333079963347257257925439630420220127175829, 26334588403552340607768398401306649416040755108588686852906416781666048381323771223923748405041710715559064788598428283647378768153915565669694911025250778622002628864868653682135547573138160585696497105672184318572016275402944765554398056054008792299636594593784891344328744192547814256637485325927317001395, 39008748355038168689186112775415171775080453538840696392929415443773790351994722271571121500900391631955057916363561421994355312684103960195488880752606720853798798281056868691805850650791447036298961423811854772591007911280152475310164832965003512721252819160190892144211679158575822375393777439609931384228, 82304474098043608661060028321681382334401394934904222339395319421383234876718900465268919670376069360510194518855949296211410738852781393673645359310632298617613158767343280562908595925412679114315777637952825196478714760929249924083956743233566407955764435141409334579687138596172519820900979765467753196573, 88915284105550368348816008646608742292143489029127610126933206845483111178644891122256082598282559325036353326973664929069944575618690996757635254147026094139437865194750539450473269922090279864309652543519451590611102139707332820460670115266911755768845241843718195465579759746419873378517868651352058841458, 98160368638847675399572398674748989820793124316223139981985855809205341298949801328255193676763501201274664892968977440665912753652643866920809757293719818430444255015639083848225580011638253333896713028293846055458529120270575215996484868800961863545736109208008592247509627201121713291801184428552756145377, 70279666367663945104159396963722599443271538912699448265711060345564659125916030957426375309362421105107348749935824650731170999396565032726246601380355258321403300241834231445800732010706990358094627163499472364138529856992133783183420053350913338600465093680827074012324157966344442294730635343631713549906, 26334588403552340607768398401306649416040755108588686852906416781666048381323771223923748405041710715559064788598428283647378768153915565669694911025250778622002628864868653682135547573138160585696497105672184318572016275402944765554398056054008792299636594593784891344328744192547814256637485325927317001395, 64763064376414100725233177531707850921895901489998530541566600837891901271286259632472966731652975882525518714861117936078937742875177256830813148392298636780335110743485184829629555885194866581373993856809276049684559851915531706344971288160366305524324492953122496357054696292196646886565479381358322089901, 53117194717106647885894381448563589551431710951341823296134446602613706746061511004659195024758322208851050987552805791982437418655652792469412944720472972658226563166131320978600741791483309755403405454978613141796416330723219433461776878939616583985714124778821795628729912025022287270480633445555264913828, 39008748355038168689186112775415171775080453538840696392929415443773790351994722271571121500900391631955057916363561421994355312684103960195488880752606720853798798281056868691805850650791447036298961423811854772591007911280152475310164832965003512721252819160190892144211679158575822375393777439609931384228, 86894782492316823641474027353348280639827350140509498202323454802239795365765754893346836370629432362724021133533998222327533787772350966000212845689517598594730975441295282822776716711598532555271750263494233082883744371824351426984036331161881322183261364331109781030043400120020631277862928075639272480540, 98160368638847675399572398674748989820793124316223139981985855809205341298949801328255193676763501201274664892968977440665912753652643866920809757293719818430444255015639083848225580011638253333896713028293846055458529120270575215996484868800961863545736109208008592247509627201121713291801184428552756145377, 84177014604944804713431824977078430985039214840423548727302549935407939656001979736935056882466843836602458913229420653818014792087210619568737881610552000458150387886315505969718562202068244042324330912044030393635010283562361328009574502508818702705813189169328775333079963347257257925439630420220127175829, 64763064376414100725233177531707850921895901489998530541566600837891901271286259632472966731652975882525518714861117936078937742875177256830813148392298636780335110743485184829629555885194866581373993856809276049684559851915531706344971288160366305524324492953122496357054696292196646886565479381358322089901, 53117194717106647885894381448563589551431710951341823296134446602613706746061511004659195024758322208851050987552805791982437418655652792469412944720472972658226563166131320978600741791483309755403405454978613141796416330723219433461776878939616583985714124778821795628729912025022287270480633445555264913828, 55246916646286914625187113796720048819441939566665506017385493092856767339656526237362346906721544511645358309134070927853338504353951702813761072243997031326763934289184435155017089001073820925041450839537239147841610796100383324289859233339039655637333071097315278349550850982664574507930331009748462710911, 106648375177462244814956519863142484434517967715967260171155727468274165192829479031138664506248057814216598696573245004451813985881502107038970656193031218207987149410860333008967386597854794100347199877481501059868628561247838289796884990343108454123533819113308605079660529262282363403293782905105286943413, 64763064376414100725233177531707850921895901489998530541566600837891901271286259632472966731652975882525518714861117936078937742875177256830813148392298636780335110743485184829629555885194866581373993856809276049684559851915531706344971288160366305524324492953122496357054696292196646886565479381358322089901, 53117194717106647885894381448563589551431710951341823296134446602613706746061511004659195024758322208851050987552805791982437418655652792469412944720472972658226563166131320978600741791483309755403405454978613141796416330723219433461776878939616583985714124778821795628729912025022287270480633445555264913828, 31650942089375642510054326764892516358156398346137044526825293211184610770488763216089112327665960486732029154795363125415308882529637371792323952011503181694383542249053937049705363331841430627186294230178074563022408165996381257431458584741639584809242782643138124672566959509661990281446947609872835868259, 57445856580199047555821927276408547257287234119338383547680295248191332034583683110165244464867776524537766857873926746540178335971787038248326614035471638752532669724573592659987617219775753496418743022777874643326596350807062794404419710292631420242689457262146875057234137466703977429352051675954990924180, 52733271064742986069580185401136225085723910924586198924963032082504789759300764373422629882605818076528578345298891993301672368391137050104915904160017718192142731169500900964695475818325453992891982593375220239226277506904476711254127320329801845264516893252806655032312577411519336691811621335647129023361, 53117194717106647885894381448563589551431710951341823296134446602613706746061511004659195024758322208851050987552805791982437418655652792469412944720472972658226563166131320978600741791483309755403405454978613141796416330723219433461776878939616583985714124778821795628729912025022287270480633445555264913828, 26334588403552340607768398401306649416040755108588686852906416781666048381323771223923748405041710715559064788598428283647378768153915565669694911025250778622002628864868653682135547573138160585696497105672184318572016275402944765554398056054008792299636594593784891344328744192547814256637485325927317001395, 86894782492316823641474027353348280639827350140509498202323454802239795365765754893346836370629432362724021133533998222327533787772350966000212845689517598594730975441295282822776716711598532555271750263494233082883744371824351426984036331161881322183261364331109781030043400120020631277862928075639272480540, 53117194717106647885894381448563589551431710951341823296134446602613706746061511004659195024758322208851050987552805791982437418655652792469412944720472972658226563166131320978600741791483309755403405454978613141796416330723219433461776878939616583985714124778821795628729912025022287270480633445555264913828, 98420054751348658774654768769711772575456856329670343536374214734125293362008191863353279362661406706630812620085457858523242832046777520147019565432158787727926701046522801552223950521984840410467512317098698121156619169844565429672876258879490904439880561021274307016589721198271903007801901439744506436516, 8103856376845753749810636625954342348018992185519844669722934214750220704461506083125434201240659143412545192044085752110862173338746105220687527651499789257412505481727824115069835196124083503200171598235085429192694286297720468885721800993830272620709634783849094028115111736986619372457889210633015446035, 84177014604944804713431824977078430985039214840423548727302549935407939656001979736935056882466843836602458913229420653818014792087210619568737881610552000458150387886315505969718562202068244042324330912044030393635010283562361328009574502508818702705813189169328775333079963347257257925439630420220127175829, 26334588403552340607768398401306649416040755108588686852906416781666048381323771223923748405041710715559064788598428283647378768153915565669694911025250778622002628864868653682135547573138160585696497105672184318572016275402944765554398056054008792299636594593784891344328744192547814256637485325927317001395, 86894782492316823641474027353348280639827350140509498202323454802239795365765754893346836370629432362724021133533998222327533787772350966000212845689517598594730975441295282822776716711598532555271750263494233082883744371824351426984036331161881322183261364331109781030043400120020631277862928075639272480540, 98160368638847675399572398674748989820793124316223139981985855809205341298949801328255193676763501201274664892968977440665912753652643866920809757293719818430444255015639083848225580011638253333896713028293846055458529120270575215996484868800961863545736109208008592247509627201121713291801184428552756145377, 52733271064742986069580185401136225085723910924586198924963032082504789759300764373422629882605818076528578345298891993301672368391137050104915904160017718192142731169500900964695475818325453992891982593375220239226277506904476711254127320329801845264516893252806655032312577411519336691811621335647129023361, 73198532513569656825655932815116028623768108369022850693529471046786059562748754190203684724306442952754102776745207511288787858904129031621886376980579480123167701603828307388858285877348902045940914696081392483634390312790021307265070190586697015612393856134764738032761300682449532714249075851386488278344]
def my_gcd(a, b):
return a.monic() if b == 0 else my_gcd(b, a % b)
m1 = ord("s")
m2 = ord("c")
e = 7
a = 0
b = 0
for k in range(512):
R.<X> = Zmod(n)[]
a = 1<<k
f1 = (a*m1+X)^e - cs[0]
f2 = (a*m2+X)^e - cs[1]
try:
b = int(- my_gcd(f1, f2).coefficients()[0])
print(f"k = {k}")
for c in cs:
for x in range(256):
if ((a*x+b)^e) % n == c:
print(chr(x), end="")
break
print()
except:
continue
# k = 366 sctf{brut3_f0rc3_7h3_w4y_t0_v1ct0ry}
|
Inverse Reversal
なんか別解があるかもしれない
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| from Crypto.Util.number import getPrime,inverse
n = 115212497901906646076814945650309895223065016560945864089583972246705800990408483001623222186324281257478104684257852308787917125013403838511481248490878740277179793165166692920877439191759389913333342083969182732100040787346793325220621228831728421953145471976655292176384523616588290831652574119800536966597
d = 19342653619736321095019406739262858513292763553015427066205052775548921803712884940275240366691800221581311317505876509706704872192509791241353606371262312134419486455811905110699389036576438861749023222249924933100895188124818488844030692986386829677836303137950484789561971041735662663305221446673307607903
cs = [10242353083978425331223562567797514269135215185677532560179294927783959853514576981778894630349657921370334867951932593410475405995555736289847906042154384112685837678725023193827132344629725212164816493692848875410307544085203226440101540274011526700374931385518493417831316368488321727325515184568151426455, 10614892818365802934451081378888295041081933298314928457901366555968758473121378170911908812818997986081798069596185564224503943996567858768096095178074783142157529299486123996800432099683337523921701427572226532224929782596836875496174442947880382545797686865815099891604486286261919787127731895584214253785, 72453657083310089257132068668974440912111801910670468142317456734350746471656367901264395778244635699977087097440995706702553124375734909696651750134682685709474688342738091903309538593951219266496664218122721154957824947660952033076392157464628668943992581665800520466971397710440867328436725612844277185616, 98647759533143513480808149613887823568238300609882691602096508004696657959802528537131254224850762306677259319833460144958287042247188426802367363927273056606211932763782568610947132004917354050553817497737126062407543531223388475777919791247670350517819379638325075367384138491381057683847737466150749906086, 5024106669088093463562003718960109330705313562374543452438528313602617855905357532401880976240908091589698502023900906193469696286523508656527954451217307246424367688322103788009065126131508639251724653910735464299488376026339973561512095039160255996331127424626346940134555201647184801777652970005802921143, 57173566276152839839326205894969370339758769921399891434875201283350731025118233760406235071539545354369673595264536860334831405072362487356080042621379546106920371432129691982972436507749869786965986222104013143255093818747178117303575600939508848006078594085804147598648950372495589242867378340844539661829, 72453657083310089257132068668974440912111801910670468142317456734350746471656367901264395778244635699977087097440995706702553124375734909696651750134682685709474688342738091903309538593951219266496664218122721154957824947660952033076392157464628668943992581665800520466971397710440867328436725612844277185616, 30435994844696312458494966250848321779446940788476109430292339003759154360078941628171673055563466722255430556678813632559392927613683797507011461879353648054072770458773867982674111453591882581233508653698601274594552675881288898660885862998206884728148995407501713146968533321243438589523371623699094795941, 101327808423581541592927587047949532461793587521748592441894490558592733574958025837374249565965539028382209688316495047271591406329064827819425085902480209825849591040817009596108200881620618935625503689726361288586186992320497576451483131062751737536741217186325586722811410637968567618389787684331857560466, 87327169844523983024186122383572724936154831354783181878608891256805223750743051844195949497070499407051410981035689713887898481337279219925556788783414737155282223548872037661604716321394914122415178667868475649231602861435439948258055912755300227699665009680374017179552306049067806593638989478265257595623, 83389481040888030497790856848973402030638198599319104116648084674236455938345675099368791841144352956046785402693005865670852470990434078462372280366029119995664273357425145926363303962778643242574305196497209905020602604439770139514055798012244591463708875277734005171406049852868517184826790127424279602263, 26792604381377646077098396402793260738684852310097622835968043750488106684330389237457168995202432614926580714465344748955074731719122502856866853487774583986285615961561621872145383441414834424713492508633213590761466745269943443807603367636717881288504235179294189373487936760761540576883070654916009409489, 35426564731555513889237851465082545080255618916833078895301715072525216421320154889997120839511818209471077625066596255091975363510085882249655811276653233946009549269824606063686727755715259122186269630597735752989834148511877377230724853255333533300337152431524296263063305208567628038219756987849457785148, 72453657083310089257132068668974440912111801910670468142317456734350746471656367901264395778244635699977087097440995706702553124375734909696651750134682685709474688342738091903309538593951219266496664218122721154957824947660952033076392157464628668943992581665800520466971397710440867328436725612844277185616, 46694861756002366916735706731645345372121033836980649100683722948357911912209141799920512867115893415002115075227691875589099809025019151369694200136210026519207841609285202410859349378827669505134459181680564235975074207427460022602304708994084086149876123334646641467468267011532759183033751055001391252393, 30281694323753863441458350867904624817874667313481502785042126500756321120109405758999655235727302061889490451635511689922900929396338872303053038123411867687502338609514654580525716898320102869066117558818006714170127735357538143274531326933123213412752430796055539684175708243042908698142872283111107911608, 35426564731555513889237851465082545080255618916833078895301715072525216421320154889997120839511818209471077625066596255091975363510085882249655811276653233946009549269824606063686727755715259122186269630597735752989834148511877377230724853255333533300337152431524296263063305208567628038219756987849457785148, 55947104004191368365525210908485429681715011104626243979740505073406415385317433313938927531181223866386726543803621434029056235995279269101857548719257175008980354239448996290266943546288142431829714013341868359231844108948117002182179094761193999997792925591224764364942764312381437578659564620658162873394, 10242353083978425331223562567797514269135215185677532560179294927783959853514576981778894630349657921370334867951932593410475405995555736289847906042154384112685837678725023193827132344629725212164816493692848875410307544085203226440101540274011526700374931385518493417831316368488321727325515184568151426455, 85267805011078363506697155175062140207445636998652678963847567597112933065517043730217680585462732863070856582374109392402549375548014962953949834827583055566900127699689740704152509523751459328749013852559215003223022025558104675431581960531031400080057668288019225200618673162281176331058730009345028638060, 43047625107074961743170004020658620084375081659174244597272835102164875655042305084803789362225520075857994590638259054752253410693500437272595903397968434067504193320473056550732678581801885531679906689781871720252899783313666739622387198014024957715716687506601726301004202794916941972004298741372447690057, 101327808423581541592927587047949532461793587521748592441894490558592733574958025837374249565965539028382209688316495047271591406329064827819425085902480209825849591040817009596108200881620618935625503689726361288586186992320497576451483131062751737536741217186325586722811410637968567618389787684331857560466, 10242353083978425331223562567797514269135215185677532560179294927783959853514576981778894630349657921370334867951932593410475405995555736289847906042154384112685837678725023193827132344629725212164816493692848875410307544085203226440101540274011526700374931385518493417831316368488321727325515184568151426455, 46694861756002366916735706731645345372121033836980649100683722948357911912209141799920512867115893415002115075227691875589099809025019151369694200136210026519207841609285202410859349378827669505134459181680564235975074207427460022602304708994084086149876123334646641467468267011532759183033751055001391252393, 55947104004191368365525210908485429681715011104626243979740505073406415385317433313938927531181223866386726543803621434029056235995279269101857548719257175008980354239448996290266943546288142431829714013341868359231844108948117002182179094761193999997792925591224764364942764312381437578659564620658162873394, 48701029335169050508642116151835089481818697324049380991235220805438674667171014369618826489746401294080141491827209900960986109207050654566836044829486033474924457434225003427052894914134076164371360065924409850345014725627321986139065590438897603233947896392172107313010455120719211550140742035249226008482, 46694861756002366916735706731645345372121033836980649100683722948357911912209141799920512867115893415002115075227691875589099809025019151369694200136210026519207841609285202410859349378827669505134459181680564235975074207427460022602304708994084086149876123334646641467468267011532759183033751055001391252393, 72453657083310089257132068668974440912111801910670468142317456734350746471656367901264395778244635699977087097440995706702553124375734909696651750134682685709474688342738091903309538593951219266496664218122721154957824947660952033076392157464628668943992581665800520466971397710440867328436725612844277185616, 35426564731555513889237851465082545080255618916833078895301715072525216421320154889997120839511818209471077625066596255091975363510085882249655811276653233946009549269824606063686727755715259122186269630597735752989834148511877377230724853255333533300337152431524296263063305208567628038219756987849457785148, 43047625107074961743170004020658620084375081659174244597272835102164875655042305084803789362225520075857994590638259054752253410693500437272595903397968434067504193320473056550732678581801885531679906689781871720252899783313666739622387198014024957715716687506601726301004202794916941972004298741372447690057, 46694861756002366916735706731645345372121033836980649100683722948357911912209141799920512867115893415002115075227691875589099809025019151369694200136210026519207841609285202410859349378827669505134459181680564235975074207427460022602304708994084086149876123334646641467468267011532759183033751055001391252393, 95986447367326045426093398035717128745163168231027353313760049410714829280428132832024046121355336674565326660817719248178163295994324691661441849140970460223065048107525352432555086007197658274507458708928265358450858922214849451622695839976809845404589461849583560990174570270949221589643971236255473759502, 48701029335169050508642116151835089481818697324049380991235220805438674667171014369618826489746401294080141491827209900960986109207050654566836044829486033474924457434225003427052894914134076164371360065924409850345014725627321986139065590438897603233947896392172107313010455120719211550140742035249226008482, 55947104004191368365525210908485429681715011104626243979740505073406415385317433313938927531181223866386726543803621434029056235995279269101857548719257175008980354239448996290266943546288142431829714013341868359231844108948117002182179094761193999997792925591224764364942764312381437578659564620658162873394, 102196388132599661465127193498136214712734194555655476808934335897150648235342527038264806315430610409951157462783049809187879614657038847599689303851674413518624572369961782451485453027424159211981889371367117652871850755510134374933378219884631142150177303670825264449000800735646906719228306418991923032954, 43047625107074961743170004020658620084375081659174244597272835102164875655042305084803789362225520075857994590638259054752253410693500437272595903397968434067504193320473056550732678581801885531679906689781871720252899783313666739622387198014024957715716687506601726301004202794916941972004298741372447690057, 101327808423581541592927587047949532461793587521748592441894490558592733574958025837374249565965539028382209688316495047271591406329064827819425085902480209825849591040817009596108200881620618935625503689726361288586186992320497576451483131062751737536741217186325586722811410637968567618389787684331857560466, 10242353083978425331223562567797514269135215185677532560179294927783959853514576981778894630349657921370334867951932593410475405995555736289847906042154384112685837678725023193827132344629725212164816493692848875410307544085203226440101540274011526700374931385518493417831316368488321727325515184568151426455, 43047625107074961743170004020658620084375081659174244597272835102164875655042305084803789362225520075857994590638259054752253410693500437272595903397968434067504193320473056550732678581801885531679906689781871720252899783313666739622387198014024957715716687506601726301004202794916941972004298741372447690057, 5723729500504613988911012649235488314230597739998519880019057473508281675665686082911553905048649088376231234736824807660779859279904139231528796753965476265375603355980972192840798014180095210645960735022184908387410405125923950581976641525552168832330666924058878897788723720324546796860220974929285264525, 10242353083978425331223562567797514269135215185677532560179294927783959853514576981778894630349657921370334867951932593410475405995555736289847906042154384112685837678725023193827132344629725212164816493692848875410307544085203226440101540274011526700374931385518493417831316368488321727325515184568151426455, 46694861756002366916735706731645345372121033836980649100683722948357911912209141799920512867115893415002115075227691875589099809025019151369694200136210026519207841609285202410859349378827669505134459181680564235975074207427460022602304708994084086149876123334646641467468267011532759183033751055001391252393, 87307118345310119702653258381222073997804918741479869849232042749266878907749898467232887168663477815484043456727924324857395490287647603394842113311356233210988146555085321731058015777591227193439937161999647013197843369064629243657749023009638738937385179227360016071066981347721566597740037811800028211483, 19267198945211754297861142477484287320095370091394051943504033284349930360528342837033482462198025535111342423655963398315577109419041936760730669884411765478038017214819407760529579393734167528794080178740275931809218061260127483809186886377334175072486121939122414822581819234903557620052078724578274336979, 10242353083978425331223562567797514269135215185677532560179294927783959853514576981778894630349657921370334867951932593410475405995555736289847906042154384112685837678725023193827132344629725212164816493692848875410307544085203226440101540274011526700374931385518493417831316368488321727325515184568151426455, 72453657083310089257132068668974440912111801910670468142317456734350746471656367901264395778244635699977087097440995706702553124375734909696651750134682685709474688342738091903309538593951219266496664218122721154957824947660952033076392157464628668943992581665800520466971397710440867328436725612844277185616, 43047625107074961743170004020658620084375081659174244597272835102164875655042305084803789362225520075857994590638259054752253410693500437272595903397968434067504193320473056550732678581801885531679906689781871720252899783313666739622387198014024957715716687506601726301004202794916941972004298741372447690057, 101327808423581541592927587047949532461793587521748592441894490558592733574958025837374249565965539028382209688316495047271591406329064827819425085902480209825849591040817009596108200881620618935625503689726361288586186992320497576451483131062751737536741217186325586722811410637968567618389787684331857560466, 55947104004191368365525210908485429681715011104626243979740505073406415385317433313938927531181223866386726543803621434029056235995279269101857548719257175008980354239448996290266943546288142431829714013341868359231844108948117002182179094761193999997792925591224764364942764312381437578659564620658162873394, 34127146941936481372477524347174117649543594283221953160342239294107648519617758930779009979264231794082412213309938596375010903970416283286233605009292396324305464727125961014269918486135625551623103604605601774775786507536802097511555024071288539917105378126303073132004204929338960101156320517452626686652, 52036255893604477341934715473810269030247970205817055291498072878207547013204193378727013580540645618246526209850184390851220916461481967751863907859616924688860684737369522252726376036744053616828413005343792610099733100451851438439525606136549372385352089579210361004619804029816700946031427054199386628434, 10242353083978425331223562567797514269135215185677532560179294927783959853514576981778894630349657921370334867951932593410475405995555736289847906042154384112685837678725023193827132344629725212164816493692848875410307544085203226440101540274011526700374931385518493417831316368488321727325515184568151426455, 46694861756002366916735706731645345372121033836980649100683722948357911912209141799920512867115893415002115075227691875589099809025019151369694200136210026519207841609285202410859349378827669505134459181680564235975074207427460022602304708994084086149876123334646641467468267011532759183033751055001391252393, 87307118345310119702653258381222073997804918741479869849232042749266878907749898467232887168663477815484043456727924324857395490287647603394842113311356233210988146555085321731058015777591227193439937161999647013197843369064629243657749023009638738937385179227360016071066981347721566597740037811800028211483, 43047625107074961743170004020658620084375081659174244597272835102164875655042305084803789362225520075857994590638259054752253410693500437272595903397968434067504193320473056550732678581801885531679906689781871720252899783313666739622387198014024957715716687506601726301004202794916941972004298741372447690057, 87327169844523983024186122383572724936154831354783181878608891256805223750743051844195949497070499407051410981035689713887898481337279219925556788783414737155282223548872037661604716321394914122415178667868475649231602861435439948258055912755300227699665009680374017179552306049067806593638989478265257595623, 34127146941936481372477524347174117649543594283221953160342239294107648519617758930779009979264231794082412213309938596375010903970416283286233605009292396324305464727125961014269918486135625551623103604605601774775786507536802097511555024071288539917105378126303073132004204929338960101156320517452626686652, 69401495296315236368718189446344847520286894008520044766291962539023820618489257611028622222220014116454719109759418409883461463688088367181672431220134841451073808647367929163997951756171813410992531555853898652264760449505145105799573640215730814597454224932899513190043479574222894026750074303259912745643, 19267198945211754297861142477484287320095370091394051943504033284349930360528342837033482462198025535111342423655963398315577109419041936760730669884411765478038017214819407760529579393734167528794080178740275931809218061260127483809186886377334175072486121939122414822581819234903557620052078724578274336979, 24346144695681590205349279067665806307892343388448165134580850348646482294775320169625483132724950488697263847722957438768547341498183051173837126838765595397122139533539637543298860767155484880312594916234756288467120142402936525777313927872039953924465047920575821880648588810646217010641449050348837280578]
def mat_mul(a, b) :
I, J, K = len(a), len(b[0]), len(b)
c = [[0] * J for _ in range(I)]
for i in range(I) :
for j in range(J) :
for k in range(K) :
c[i][j] += a[i][k] * b[k][j]
c[i][j] %= n
return c
def mat_pow(x, n):
y = [[0] * len(x) for _ in range(len(x))]
for i in range(len(x)):
y[i][i] = 1
while n > 0:
if n & 1:
y = mat_mul(x, y)
x = mat_mul(x, x)
n >>= 1
return y
m = ""
for c in cs:
ret = [[c], [2]]
mat = [[c, -1], [1, 0]]
ret = mat_mul(mat_pow(mat, d-1), ret)
for i in range(256):
x = (i+inverse(i,n))%n
if x == ret[0][0]:
m += chr(i)
break
print(m) # sctf{St4rlight_Wh1sp3rs_1n_th3_Un1v3rs3's_Myst3r10us_M3l0dy}
|
DSA starter
DSAのアルゴリズムをそのまま適用します。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| # DSA
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
from Crypto.Random.random import randint
from hashlib import sha256
from random import shuffle
p, q, g, y = (178152782381825178803219174463700910343887635796771256691167008807374935805608810619510355568394750688608183393843518297273118359566453071394197733833035896858630558725699316955042421744365078468534495190922167403912399698372676556069049828057115488315878767055028995972138905736540492834987058578356095483777, 886462388902383667466763577880397720831607417567, 63028074410235712650856818704197230709567749692836951562649290014316138139312359167371415041184383722629991416556492666859022007320300058824552605629526632600490856764473931862464430933236982859019405547828622063621971180492882956812095615397762837988938242853452722411843661219861190400890315806421801546353, 38647414566356138569980136086529833930398825658110621806133281938642505973525550931612864354218115649244247745143865068040333379732358277345437679898306683569802690274384584277131839415050015738332670477850796862979487857316281608801669816739648374889909541749203238997633769097943033727833275138527729141082)
r = 853709161711035525874302893962481214917053133801
s = 257021930968164571494098920024334244863049558820
candidates = [ #
# 署名の検証
for msg in candidates:
w = inverse(s, q)
u1 = (bytes_to_long(sha256(msg).digest()) * w) % q
u2 = (r * w) % q
v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
if v == r:
print(f"Found! {msg}")
break
# sctf{this_is_passcode_14987914387428957283749837987938471847812313}
|
DH Starter
Diffie-Hellman鍵共有のアルゴリズムは離散対数問題が解くことが難しいことを利用しています。が、今回は$p$が小さいので、Baby-step Giant-step法で解くことができてしまいます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| # DSA
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, getStrongPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from random import randint
from os import urandom
p = 3449512277
g = 2
A = 1853660196
B = 1844600045
iv = 0x20bd91cc19f353375134ed6ac8ab9cd8
ciphertext = 0xc4f8d8b06d616d10ec48c15c1f313c584ee4c11768ec69582cd5a254ba010400679cee579d674c84bb560c38eef5b53e2e668f11fa0044ab79f9c5bd97a94ab6
iv = long_to_bytes(iv)
ciphertext = long_to_bytes(ciphertext)
# X^K ≡ Y (mod M) となるような K を求める
def bsgs(X, Y, M):
D = {1: 0}
sq = int(M**.5)+1
# Baby-step
Z = 1
for i in range(sq):
Z = Z * X % M
D[Z] = i+1
if Y in D:
return D[Y]
# Giant-step
R = pow(Z, M-2, M) # R = X^(-sq)
for i in range(1, sq+1):
Y = Y * R % M
if Y in D:
return D[Y] + i*sq
return -1
a = bsgs(g, A, p)
s = pow(B, a, p)
key = sha256(long_to_bytes(s)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
print(cipher.decrypt(ciphertext))
# sctf{Ro0t_Expr3ssi0n_Unveiling_Discrete_Logarithms}
|
DHMO Backdoor
DHアルゴリズムですが、素数$q$が用意されて、
という不思議なパラメータ設定になっています。
この条件下で$A, B$を計算すると、
$$
A = (1+q)^a \equiv 1 + aq \pmod{q^2} \\
B = (1+q)^b \equiv 1 + bq \pmod{q^2}
$$
というように、離散対数問題のように見えてただの線形方程式になってしまっています。よって、簡単に解けてしまいます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| # DSA
from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes, getStrongPrime
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from hashlib import sha256
from random import randint
from os import urandom
from gmpy2 import iroot
p = 95415937817579451380560331137505725674156858513926822163980264696859536466150605410084190929378877860698117457381837054218767245648636289250124372497832405773309953882151215182666896790688601517274746987312158949180001859580605523093541735579880492742320916914652237329506667385776239702594761823614432307209
g = 9768108200546278315194231322082114002915357430681820414703248793717480653233394063038860570648067384600535879456361644343100108834155177088164778679532548
A = 92453853458870576229518823501929360581552725741189278049516561961478833097172834801288760072546654951598477738730124366332805108801506092437910200235296192165845124855345940151854202354847168551454392462737787664299300742218459667689807033294098287219340833990501929320726865292649944555957036455424727547115
B = 56612820070987073806615211708626056370390413126863293367701116303948485194819573186994266503189322508232997547860696305447417646426321081076895093762235273029112042023440682941122763197970972104018354007661120535881288476220273010083950515697901659556323027333128910934151081165951565331390808856583772052696
iv = 0x242277a2562e41e7a2c84f07802a2113
ciphertext = 0x672233ffe1d4d793373950d4c1c177cc5caeb5b7a468e51cf86b29d4feb5bfde7847a038d3bab1050021301a0139f9ac
iv = long_to_bytes(iv)
ciphertext = long_to_bytes(ciphertext)
# (1+q)^a = 1 + aq mod q^2
q = iroot(p, 2)[0]
print(A-1)
a = (A-1)//q
s = pow(B, a, p)
key = sha256(long_to_bytes(s)).digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
print(cipher.decrypt(ciphertext))
# sctf{DHMO_Weakness_Revealed_Compromise_Eminent}
|
ECC Starter 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
p = 17
a = 0
b = 2
# y^2 = x^3 + ax + b mod p
Gx = 12
Gy = 9
def double(p1):
if p1 == None:
return None
x0 = p1[0]
y0 = p1[1]
if y0 == 0: # 無限遠O
return None
phi = (3 * x0 * x0 + a) * inverse(2 * y0, p)
psi = (-3 * x0 * x0 * x0 - a*x0 + 2*y0*y0) * inverse(2*y0, p)
x4 = (phi * phi - 2 * x0) % p
y4 = (-phi * x4 - psi) % p
return (x4, y4)
def add(p1, p2):
if p1 == None:
return p2
if p2 == None:
return p1
x1 = p1[0]
y1 = p1[1]
x2 = p2[0]
y2 = p2[1]
if x1 == x2 and y1%p == (-y2)%p:
return None
if x1 == x2 and y1 == y2:
return double(p1)
phi = (y2 - y1) * inverse(x2 - x1, p)
psi = (y1 * x2 - y2 * x1) * inverse(x2 - x1, p)
x3 = (phi * phi - x1 - x2) % p
y3 = (-phi * x3 - psi) % p
return (x3, y3)
P = (12,9)
Q = (8,2)
R = add(P,Q)
print(R)
|
1
2
3
4
5
6
7
8
9
10
11
| a = 0
b = 2
p = 17
K = GF(p)
E = EllipticCurve(K,[a,b])
G = E(12, 9)
P = E(8,4)
print(G+P)
|
sctf{16}
ECC Starter 2
$x$軸に対称な点を加算すると無限遠になります。
sctf{4}
ECC Starter 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
def double(p1):
if p1 == None:
return None
x0 = p1[0]
y0 = p1[1]
if y0 == 0: # 無限遠O
return None
phi = (3 * x0 * x0 + a) * inverse(2 * y0, p)
psi = (-3 * x0 * x0 * x0 - a*x0 + 2*y0*y0) * inverse(2*y0, p)
x4 = (phi * phi - 2 * x0) % p
y4 = (-phi * x4 - psi) % p
return (x4, y4)
def add(p1, p2):
if p1 == None:
return p2
if p2 == None:
return p1
x1 = p1[0]
y1 = p1[1]
x2 = p2[0]
y2 = p2[1]
if x1 == x2 and y1%p == (-y2)%p:
return None
if x1 == x2 and y1 == y2:
return double(p1)
phi = (y2 - y1) * inverse(x2 - x1, p)
psi = (y1 * x2 - y2 * x1) * inverse(x2 - x1, p)
x3 = (phi * phi - x1 - x2) % p
y3 = (-phi * x3 - psi) % p
return (x3, y3)
def mul(p1, n):
if n == 0:
return None
if n == 1:
return p1
if n % 2 == 0:
return double(mul(p1, n//2))
if n % 2 == 1:
return add(p1, double(mul(p1, n//2)))
p = 58831
a = 5
b = 13
# y^2 = x^3 + ax + b mod p
Gx = 28603
Gy = 46279
P = (Gx, Gy)
Q = mul(P, 10)
print(Q)
|
sctf{15400}
ECC Starter 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| from Crypto.Util.number import getPrime, inverse, bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
def double(p1):
if p1 == None:
return None
x0 = p1[0]
y0 = p1[1]
if y0 == 0: # 無限遠O
return None
phi = (3 * x0 * x0 + a) * inverse(2 * y0, p)
psi = (-3 * x0 * x0 * x0 - a*x0 + 2*y0*y0) * inverse(2*y0, p)
x4 = (phi * phi - 2 * x0) % p
y4 = (-phi * x4 - psi) % p
return (x4, y4)
def add(p1, p2):
if p1 == None:
return p2
if p2 == None:
return p1
x1 = p1[0]
y1 = p1[1]
x2 = p2[0]
y2 = p2[1]
if x1 == x2 and y1%p == (-y2)%p:
return None
if x1 == x2 and y1 == y2:
return double(p1)
phi = (y2 - y1) * inverse(x2 - x1, p)
psi = (y1 * x2 - y2 * x1) * inverse(x2 - x1, p)
x3 = (phi * phi - x1 - x2) % p
y3 = (-phi * x3 - psi) % p
return (x3, y3)
def mul(p1, n):
if n == 0:
return None
if n == 1:
return p1
if n % 2 == 0:
return double(mul(p1, n//2))
if n % 2 == 1:
return add(p1, double(mul(p1, n//2)))
p = 3173581703
a = 5
b = 13
# y^2 = x^3 + ax + b mod p
Gx = 2922555662
Gy = 1379601526
P = (Gx, Gy)
Q = mul(P, p)
print(Q)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
from Crypto.Util.number import getPrime
a = 5
b = 13
p = 3173581703
K = GF(p)
E = EllipticCurve(K,[a,b])
G = E(2922555662, 1379601526 )
print(G)
print((p)*G)
|
sctf{1012290686}
ECC Starter 5
sctf{41712}
ECC vs. RSA
楕円曲線上で、$e$倍した点を復元する問題です。$e$の逆元(楕円曲線の位数上で)を計算すればよいです。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| import os
from random import getrandbits
import hashlib
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import long_to_bytes, inverse
# secp256k1
bitsize = 256
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
a = 0
b = 7
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
# exponent
e2 = 65537
E = EllipticCurve(GF(p),[a,b])
Q = E(93433963105152978020305311287114858750860633144092310644734267100070909728359,49607652788439856681244209356178787315854579032619206302851865258501732308348)
c = 0x5ccc961542dab655f1fd94073b8d1becd031b371a2c849465a0b91dce3549d352daa3859e533ce27c343eed24a9f1808
iv = 0xacc9a0d6dba3ebd3d8eb3655baaaae8a
G = E(Gx,Gy)
n = Q.order()
c = long_to_bytes(c)
iv = long_to_bytes(iv)
d = inverse(e2,n)
P = (d)*Q
print(P)
key = hashlib.sha256(long_to_bytes(int(P[0]))).digest()
cipher = AES.new(key, AES.MODE_CBC, iv)
m = cipher.decrypt(c)
print(unpad(m,16)) # sctf{Crypt0_Unveiled_Thr0ugh_ECC_RSA_Enigmas}
|
Knapsack Starter
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| from Crypto.Util.number import *
q = 19476848988204872060832823259129600051004287455211043516206652751259893783183944942428856467
r = 29311266273294587273200436915502354865358876784826842913113098289713485249949916371307504229
c = 945990657049790727811563555213826037534670582134726526157349843403732326518548975197241258807
w = [263228976889951266540541834687364181713, 457935464639243892337831056783295578478, 1058195876074085625891598742796685364429, 1934211975170539017039476473246851471980, 3813329232257528690875093473358573391068, 7548351188526979796201239878428904609165, 15342376214376299641734234847361388410502, 30676111579055058805152748403012090457953, 61314165415482354434033552561206591940507, 122457509135354125562625114523776211913998, 245045468370028825796324167156568593108193, 490132911968585330062812415035249827516095, 980336727631959359084042995890560952266031, 1960712218890410427185218236979660909762713, 3921165295359268585867075266058558190047491, 7842448389418084606567626834395565528136167, 15684854680112704228353230728336753483365450, 31369856681810663918836565124030252512150917, 62739514158667052998477170704377763994464875, 125479138474588541117450796477672911548395031, 250958183125832955449049108788435947510860683, 501916497265011968966166509486889068874362376, 1003833059492784419306001709963036828597523022, 2007665977862164000887774833362203778917130761, 4015331819318235561394427804904380224700572183, 8030663847599794966775791679517475340506474867, 16061327666741485196225754142518721068080943118, 32122655345323353998576534454136019803643540679, 64245310729616839356083520012998574603423950304, 128490621341110194559129167379408144239346618394, 256981242546615628019276807071248658031631670062, 513962485288126713902190842333844183528809648761, 1027924970600288450786489616484085599828091152701, 2055849940990482356003425008869926100483221671690, 4111699882034627857142016435195095613774416853442, 8223399764305165028674983621512397264248203767081, 16446799528556974948616834997022842102628346949905, 32893599057155661341614967294809786188099159169000, 65787198114289863299284895203500669221171935691836, 131574396228310085788505514630103708420408554186039, 263148792456705125867287379096890451580988570193459, 526297584913529438181012879437140704409720583631137, 1052595169826954745965463773116138739756314031103225, 2105190339654059980131128392303874984820051581883518, 4210380679308075385776419970405407011648148027267268, 8420761358616068204682608730984585935797023148735240, 16841522717232249663297795069152658737760298312512891, 33683045434464430867773797571752143270644886204883278, 67366090868928845127882400245536153537986749318215467, 134732181737857628263363749789729833943267541695128439, 269464363475715229776799440963157258797709780239020914, 538928726951430501414854528372286612741407042677372934, 1077857453902860973085094919440328725332384482706712426, 2155714907805722202837631837419704718414663552265559180, 4311429815611444242553606338400042927549486188375483412, 8622859631222888393731412712717380322153162722607002277, 17245719262445776934016465912139643732064795350553784834, 34491438524891553747147568874352654535400550049840450634, 68982877049783107438718799754373184986004472676167594261, 137965754099566215102192084895283887966788005118662563572, 275931508199132430030634007293021764123584504939475470385, 551863016398264859986523382523585129022471394554055009435, 1103726032796529720155003462265105606483256466111108698616, 2207452065593059440240384970300352371199272846808008235379, 4414904131186118880368717968671301367907045659783220840939, 8829808262372237760948511909701827407796814078799892455848, 17659616524744475521701487905508934342721167847585411763221, 35319233049488951043417845329985524424774757313815096694704, 70638466098977902086887899164405215395786894649535300442723, 141276932197955804173745880247287180957442722334964370966546, 282553864395911608347748022365954348935775529435297210695625, 565107728791823216695400500048797452026936615561498504495800, 1130215457583646433390684998047707208069791052942278824204418, 2260430915167292866781340631462439052033775806549042273627757, 4520861830334585733562622652226068575770631209817472344431374, 9041723660669171467125263454374722081820235557791494551987159, 18083447321338342934250524265736708001496740499019055190094538, 36166894642676685868501113338137592286332612302544482485057756, 72333789285353371737002141672613582208906219392570439901703721, 144667578570706743474004416859793180811316017009618604250081956, 289335157141413486948009002951513754094921145079351292435147195, 578670314282826973896017865424292766255735419976456877004028357, 1157340628565653947792035726945634328313560050099335903802848245, 2314681257131307895584071484916560363546573736102282928362726573, 4629362514262615791168142936189402163593833141975026198871598830, 9258725028525231582336285931712985131658354715212582574367146995, 18517450057050463164672571753794287902392074875599395173445001321, 37034900114100926329345143433025043698658494079021716869810363729, 74069800228201852658690286945201185424116608368809782136879911153, 148139600456403705317380573848376468768454936157017896526821436751, 296279200912807410634761147836417492562880077408464415839925812836, 592558401825614821269522295541413003283623417844614775602991844926, 1185116803651229642539044591270817571719591114346031119224088519762, 2370233607302459285078089182311797790423709027951884197767219627489, 4740467214604918570156178364606021453368837362296775448471763559944, 9480934429209837140312356729250069790145748311960267934480838087905, 18961868858419674280624713458751382088628232003250304088543309769230, 37923737716839348561249426917310834526882249877135880939563199524561, 75847475433678697122498853834661002608365834191029460986523516653115, 151694950867357394244997707669233984078243395832393601212193574769823, 303389901734714788489995415338484802549497462764751593085610926721251, 606779803469429576979990830677134428924180420604088449473776489960306, 1213559606938859153959981661354245194413895941475040359205842686583473, 2427119213877718307919963322708252614754809336878944200561730368191557, 4854238427755436615839926645416710779751561776235946421137139708078928, 9708476855510873231679853290833317577704121721159966375281875830564338, 19416953711021746463359706581666732514173999893774109133822452371497323, 38833907422043492926719413163333385657156715009012938122750440578262832, 77667814844086985853438826326666897878038082310410763610504701470130183, 155335629688173971706877652653333586682032746273505115591234037181868344, 310671259376347943413755305306667131736767942225328981428811870395643998, 621342518752695886827510610613334390180071117312961860832391406841819242, 1242685037505391773655021221226668763320733426469906257502944537706725839, 2485370075010783547310042442453337627736279726847249205695542477157255942, 4970740150021567094620084884906675211827314506471042035293373265626939830, 9941480300043134189240169769813350276670008651025396844479521796298847105, 19882960600086268378480339539626700605915482613788268719820910533965573007, 39765921200172536756960679079253401436720214961803864078851996311157935833, 79531842400345073513921358158506802706672865389846451345114874503205005213, 159063684800690147027842716317013605468371993692078184096538877564792444780, 318127369601380294055685432634027210881752581399639207186287992365392777467, 636254739202760588111370865268054421884250687817733779499977175887424514055, 1272509478405521176222741730536108843689152570208250597214250682306871063453, 2545018956811042352445483461072217687200958170585479765867661071453005313204, 5090037913622084704890966922144435374727224095711352896489635140639284558709, 10180075827244169409781933844288870749150803604132946792902861730960130519101, 20360151654488338819563867688577741498440231818050984814414131779001893954002, 40720303308976677639127735377155482996907736287635668656167583298448205710726, 81440606617953355278255470754310965993749845305293880609616965926254291966065, 162881213235906710556510941508621931987383518233854591584928195206484523084469, 325762426471813421113021883017243863975031551177758729440470449095297505125034, 651524852943626842226043766034487727950001553814845214384370479452678770364486, 1303049705887253684452087532068975455899963985904839518584012121113144472278629, 2606099411774507368904175064137950911800064973447132296429922340194207206283403, 5212198823549014737808350128275901823600031933516369803366230858975355751742222, 10424397647098029475616700256551803647199952513646467290746525005642958338658131, 20848795294196058951233400513103607294399865165820761853103287568442192655904557, 41697590588392117902466801026207214588799775496407528083559167958620980948129123, 83395181176784235804933602052414429177599478133657109937098904135479294173925163, 166790362353568471609867204104828858355199142821865559664818176369748440091865937, 333580724707136943219734408209657716710398084055335450415180886098089029002838155, 667161449414273886439468816419315433420796288526206915881212684246336427399630981, 1334322898828547772878937632838630866841592652133597315692233339916367877136281186, 2668645797657095545757875265677261733683185227803667762780671479934012015987584583, 5337291595314191091515750531354523467366370314564538407749812829898633825373399680, 10674583190628382183031501062709046934732740774556387387862300273499571252048865079, 21349166381256764366063002125418093869465481720805671426454128431134329516135095761, 42698332762513528732126004250836187738930963282482100862796467954829168376044456878, 85396665525027057464252008501672375477861926499746255378365668800226613007580617247, 170793331050054114928504017003344750955723853028399583392630736846908044182196193007, 341586662100108229857008034006689501911447706242980595606170845145627101786522415403, 683173324200216459714016068013379003822895412498690191005975508101333950029720159355, 1366346648400432919428032136026758007645790825004255814047917130079813940756486579954, 2732693296800865838856064272053516015291581649768642168926936527369393080354781167740, 5465386593601731677712128544107032030583163299770499928222287223443786634370668059852, 10930773187203463355424257088214064061166326599293081832651132958631628113141503796974, 21861546374406926710848514176428128122332653198798219733689320505230168037031634772693, 43723092748813853421697028352856256244665306397312102686768877285823463474179918401903, 87446185497627706843394056705712512489330612794900982032101851797136904153336456238020, 174892370995255413686788113411425024978661225589557302145435604480844789031725418075992, 349784741990510827373576226822850049957322451179335479358445853411807130258467327702021, 699569483981021654747152453645700099914644902358741940569264175414201762057057799022129, 1399138967962043309494304907291400199829289804717165770650446407070302606046582025974620, 2798277935924086618988609814582800399658579609434558489360516727584419391721419833736445, 5596555871848173237977219629165600799317159218868899160948298515143384316463999067586636, 11193111743696346475954439258331201598634318437737879857707609916687973601545341951410159, 22386223487392692951908878516662403197268636875475806289175077655992859464525002451610176, 44772446974785385903817757033324806394537273750951700014946615606735494776383693258655688, 89544893949570771807635514066649612789074547501903184095022764183600184336070525246028640, 179089787899141543615271028133299225578149095003806543606123912894383587333125968090708987, 358179575798283087230542056266598451156298190007613060740055284132334732369346512327144844, 716359151596566174461084112533196902312596380015226109582319932656020963488351038028739646, 1432718303193132348922168225066393804625192760030452163868958382266333790500844020941445604, 2865436606386264697844336450132787609250385520060904416604457827324560131134874955795659071, 5730873212772529395688672900265575218500771040121808724814913279500673400050155498850067943]
n = len(w)
c = (c * inverse(r, q))%q
m = 0
for i in range(n-1, -1, -1):
if c >= w[i]:
m += 1 << i
c -= w[i]
print(long_to_bytes(m)) # sctf{NP-Hard_Knapsack}
|
What’s in the bag?
$w,q$の値がわかりませんが、配布ファイルをよく見ると乱数は使っておらず、毎回同じ値が求まるようにできているので、これを利用して$w,q$を求めます。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| from Crypto.Util.number import *
b = [460512672224238860814315137993310742357595503044391945632042049419054327951919468685681985, 1381538016672716582442945413979932227072786509133175836896126148257162983855758406057045955, 4144614050018149747328836241939796681218359527399527510688378444771488951567275218171137865, 5686547812913902340122430027557447584953827435183531575031782650803505850248688861484284418, 3565054764460613216639132686148457837458980011520492811028642585388595541839792998394594900, 3947869956241292748053319360183431053675688887546427476052575072654825621066242202154655523, 5096315531583331342295879382288350702325815515624231471124372534453515858745589813434837392, 1794357920468900223159480750341167189574944252842592499306412236338625567330495854246253822, 5383073761406700669478442251023501568724832758527777497919236709015876701991487562738761466, 2654632609939008204707169356546619788771995981553230579691004760025708097068189102158026044, 1216603492676477712257429371377916907614736797644640782039661596566163286751430513444948955, 3649810478029433136772288114133750722844210392933922346118984789698489860254291540334846865, 4202137096947752508452785644139309709831380031786716081323601685584508576309737827975411418, 5859116953702710623494278234155986670792888948345097286937452373242564724476076690897105077, 4082762186827038066754677305944075094976164551005189946745651752705772164521956486633056877, 5500992223340567298399953219570282826227242506000518883203602574606355489112732666870041454, 3008387995740608091471702262186963561279225223971454735544102356797144458431924414551866008, 2277869650081277372551028088298948225136424524899313249598954386880472370842636450626468847, 86314613103285215789005566634902216708022427682888791763510477130456108074772558850277364, 258943839309855647367016699904706650124067283048666375290531431391368324224317676550832092, 776831517929566942101050099714119950372201849145999125871594294174104972672953029652496276, 2330494553788700826303150299142359851116605547437997377614782882522314918018859088957488828, 244189324225555577045372199165137094648565495298941175810995964055983749603440473843337307, 732567972676666731136116597495411283945696485896823527432987892167951248810321421530011921, 2197703918030000193408349792486233851837089457690470582298963676503853746430964264590035763, 6593111754090000580225049377458701555511268373071411746896891029511561239292892793770107289, 6284746587988907936946990735852219749131302825184133326623967721512761708972404795252063513, 5359651089685630007112814811032774329991406181522298065805197797516363118010940799697932185, 2584364594775796217610287036574438072571716250536792283348888025527167345126548813035538201, 1005799447186841750966782411461371759013897604595325893013311393070541030926509646077485426, 3017398341560525252900347234384115277041692813785977679039934179211623092779528938232456278, 2304900687541028856836963004890403372423827294342882080086449854123908273885450021668239657, 167407725482539668646810316409267658570230736013595283225996878860763817203213271975589794, 502223176447619005940430949227802975710692208040785849677990636582291451609639815926769382, 1506669529342857017821292847683408927132076624122357549033971909746874354828919447780308146, 4520008588028571053463878543050226781396229872367072647101915729240623064486758343340924438, 65437089804619356663478232626795426786187323071116027239041820699947184554001443964514960, 196311269413858069990434697880386280358561969213348081717125462099841553662004331893544880, 588933808241574209971304093641158841075685907640044245151376386299524660986012995680634640, 1766801424724722629913912280923476523227057722920132735454129158898573982958038987041903920, 5300404274174167889741736842770429569681173168760398206362387476695721948874116961125711760, 2406624148241409865497053131787403791641017212251092705020457063065243837716077297318876926, 472578107583682694627080697100268916221800489738227158028018505684770508695095098927501601, 1417734322751048083881242091300806748665401469214681474084055517054311526085285296782504803, 4253202968253144251643726273902420245996204407644044422252166551162934578255855890347514409, 6012314567618885853067100123445318279287362075917082309723146969977842730314430878013414050, 4542355028575563755473142973812069920459583933721145015102735542911606182037019047981983796, 132476411445597462691271524912324843976249507133333131241501261712896537204783557887693034, 397429234336792388073814574736974531928748521399999393724503785138689611614350673663079102, 1192287703010377164221443724210923595786245564199998181173511355416068834843052020989237306, 3576863109031131492664331172632770787358736692599994543520534066248206504529156062967711918, 3983294989952847576128914819636369903374958930784932673528249515233658509134331395874006577, 5202590632717995826522665760647167251423625645339747063551395862190014522949857394592890554, 2113183223872893675839839885417616836868374641989139276587482219548121559943298597720413308, 6339549671618681027519519656252850510605123925967417829762446658644364679829895793161239924, 5524060340574949278830401572234666614412869483872151575220634608911172030583413793425461418, 3077592347443754032763047320180114925836106157586352811595198459711594082843967794218125900, 2485482705190715196425063262278402318807067325744007477752242695623821244078766589625248523, 709153778431598687411111088573264497719950830216971476223375403360502727783162975846616392, 2127461335294796062233333265719793493159852490650914428670126210081508183349488927539849176, 6382384005884388186699999797159380479479557471952743286010378630244524550048466782619547528, 5652563343372070756371841994954256521036170121828127943964430523711651641239126761800384230, 3463101355835118465387368588338884645706008071454281917826586204113032914811106699342894336, 3642009730364808494298027066754711478416773067347794796446405928828137739980183304999553831, 4178734853953878581030002502002191976549068055028333432305865102973452215487413121969532316, 5788910224721088841225928807744633470945953018069949339884242625409395642009102572879467771, 3872141999882172719949629026710015495435356760179746105586022509206264917121034132580144959, 4869131662505971257984808381868104027604819133524187359724714844107833746909965604711305700, 1112806313236819970226267749080427165411955106542460165107439165301579231823623228075658746, 3338418939710459910678803247241281496235865319627380495322317495904737695470869684226976238, 3267962481990832830172331043461902030006344811867090528933599804203252081959472259651799537, 3056593108831951588652914432123763631317783288586220629767446729098795241425279985926269434, 2422484989355307864094664598109348435252098718743610932268987503785424719822703164749679125, 520160630925376690419915096066102847055045009215781839773609827845313155014972701219908198, 1560481892776130071259745288198308541165135027647345519320829483535939465044918103659724594, 4681445678328390213779235864594925623495405082942036557962488450607818395134754310979173782, 549748360704076837609550197260891953083712954796007759820759984801533176497989346879262992, 1649245082112230512828650591782675859251138864388023279462279954404599529493968040637788976, 4947735246336691538485951775348027577753416593164069838386839863213798588481904121913366928, 1348617064728980811729697929520197815857747485462107601093814222619473756539438779681842430, 4045851194186942435189093788560593447573242456386322803281442667858421269618316339045527290, 5390259245420280403703202667419837884018476222143917452810975320064302804401812224107452693, 2676189061979747407381450605735628734652926372401650444366220593170986404299163086264099725, 1281272848798695320280273118944943745257527970189900376065309096001998208444352465763169998, 3843818546396085960840819356834831235772583910569701128195927288005994625333057397289509994, 4784161302047710980658379372242551248616500584694052427554429180507022871546035398839400805, 857895231862039138246980720203768828446999460052055368596582174499146605731832610459944061, 2573685695586117414740942160611306485340998380156166105789746523497439817195497831379832183, 973762749617805342358747783571976997321743993453447360335886886981358447133356701110367372, 2921288248853416027076243350715930991965231980360342081007660660944075341400070103331102116, 2016570409419701179364651353885850517194444794065975285989629299321265019747073516964177171, 6049711228259103538093954061657551551583334382197925857968887897963795059241220550892531513, 4654545010496216810553704788448769737347500852563675659839958326869463168817388066619336185, 469046357207556627932956968822424294640000263660925065453169613586467497545890613799750201, 1407139071622669883798870906467272883920000790982775196359508840759402492637671841399250603, 4221417214868009651396612719401818651760002372948325589078526522278207477913015524197751809, 5916957307463482052325759459943513496578755971829925810202226883323661429285909779564126250, 4256283248109352353249120983306655572333765621459675516539975282949062278951455752634120396, 6021555407187510157883284251658024258300045717363975592586573165336225832401230464873232011, 4570077547281436669921695358450187857497634858061824863693014128986755488297417808561437679, 215643967563216206036928678826678655090402280155372677012337019938344455985979839626054683, 646931902689648618110786036480035965271206840466118031037011059815033367957939518878164049, 1940795708068945854332358109440107895813620521398354093111033179445100103873818556634492147, 5822387124206837562997074328320323687440861564195062279333099538335300311621455669903476441, 3972572698339418885263065588437086144920082398555084923932593247983978925958093423652170969, 5170423757877709753925118067049315976058996048650203814764427060440975773421143477927383730, 2016682599352035458047196804624063010774485851920509530226575814301005311357156847723892836, 6050047798056106374141590413872189032323457555761528590679727442903015934071470543171678508, 4655554719887225318696613845092682179567870373254483857972476961687125793308138043456777170, 472075485380582152361684138754161621301108825733349659850725518039455371018140544312073156, 1416226456141746457085052416262484863903326477200048979552176554118366113054421632936219468, 4248679368425239371255157248787454591709979431600146938656529662355098339163264898808658404, 5998743768135171211901393048100421316428687147785389858936236303554334013036657903396846035, 4501642630124419831976021747777379031883559149326067662742003543641080030203700124132279751, 10339216092165692199907846808252178248175153948101074159305263901318081704826786338580899, 31017648276497076599723540424756534744525461844303222477915791703954245114480359015742697, 93052944829491229799170621274269604233576385532909667433747375111862735343441077047228091, 279158834488473689397511863822808812700729156598729002301242125335588206030323231141684273, 837476503465421068192535591468426438102187469796187006903726376006764618090969693425052819, 2512429510396263204577606774405279314306562409388561020711179128020293854272909080275158457, 789994194048242711868741624953895484218436081150632105100184700549920558365590447796346194, 2369982582144728135606224874861686452655308243451896315300554101649761675096771343389038582, 362653409293637504954595926323116899264673583340637988868309621438324020837177237137986569, 1087960227880912514863787778969350697794020750021913966604928864314972062511531711413959707, 3263880683642737544591363336908052093382062250065741899814786592944916187534595134241879121, 3044347713787665731910011312462213821444935603182174742411007095323787558150648609696508186, 2385748804222450293865955239124699005633555662531473270199668602460401669998809036060395381, 409952075526803979733787019112154558199415840579368853565653123870244005543290315152056966, 1229856226580411939201361057336463674598247521738106560696959371610732016629870945456170898, 3689568679741235817604083172009391023794742565214319682090878114832196049889612836368512694, 4321411702083160550948170817766230612682976548627908089239281660985627145215701716076408905, 6216940769108934750980433755036749379347678498868673310684492299445920431193968355200097538, 5156233633045710449213143868586363220640533202575918017986771531315839284675631479542034260, 1974112224856037543911274209235204744519097313697652139893609226925595845120620852567844426, 5922336674568112631733822627705614233557291941092956419680827680776787535361862557703533278, 4272421349423244091473310486592957783269373529248767344975777675308440597179314087052341480, 6069969711129185372555852761516930891106869440731251077893980342414360787084805468127895263, 4715320459106462313939400888026907755918106028163651319615235660221160352348142818325427435, 651372703038293138090045267556838350351815790460852044779001613641559048138154868918023951, 1954118109114879414270135802670515051055447371382556134337004840924677144414464606754071853, 5862354327344638242810407408011545153166342114147668403011014522774031433243393820262215559, 4092474307752820924703064827510750542096524048412903294966338201300172290823907874728388323, 5530128586117915872245115784270309167588320998223658927865661920389555868018586831156035792, 3095797084072653813007189956287042585362460700640874869530280394146745595149486907409849022, 2540096915077414537157491170599185297386130954907573651557488498929275780995323929200417889, 872996408091696709608394813535613433457141717707669997639112813276866338532834994572124490, 2618989224275090128825184440606840300371425153123009992917338439830599015598504983716373470, 1109673335684723484611474623558578442413024312353979021718662635980836042342378158119991233, 3329020007054170453834423870675735327239072937061937065155987907942508127027134474359973699, 3239765684021964459639192913765263523015967664170760238434611040316563376628266630050791920, 2972002714925346477053500043033848110346651845497229758270480437438729125431663097123246583, 2168713807635492529296421430839601872338704389476638317778088628805226371841852498340610572, 6506141422906477587889264292518805617016113168429914953334265886415679115525557495021831716, 6023835594438338959939635481032531933645837211259642945936092292225115337670398899007236794, 4576918109033923076090749046573710883535009339748826923741571509653424004104923110963452028, 236165652820675424544089743197247733202525725216378857158009161938350003408495746832097730, 708496958462026273632269229591743199607577175649136571474027485815050010225487240496293190, 2125490875386078820896807688775229598822731526947409714422082457445150030676461721488879570, 6376472626158236462690423066325688796468194580842229143266247372335450092029385164466638710, 5634829204193615584343111802453181472002081448496585515732036749984428267181881907341657776, 3409898938299752949301178010835659498603742051459654633129404882931362792639372135966714974, 3482402477758711946039455334245036037109975007363912942354861965283127373464979614871015745, 3699913096135588936254287304473165652628673875076687870031233212338421115941802051583918058, 4352444951266219906898783215157554499184770478215012653060346953504302343372269361722624997, 6310040516658112818832270947210721038853060287629987002147688177001946025663671292138745814, 5435532875693244652768655445108278199156678568859859092376359163983916068084740290357979088, 2812009952798640154577808938800949680067533412549475363062372124929826195347947285015678910, 1688735521255373561869348118140906581501349090633375132153763691278517581590705062017907553, 5066206563766120685608044354422719744504047271900125396461291073835552744772115186053722659, 1704031017017268253095975666744274316109639521670274275317167854484736225410071972102909623, 5112093051051804759287927000232822948328918565010822825951503563454208676230215916308728869, 1841690478874320474135623604174583927584253401002366563787805323340704019784374162867928253, 5525071436622961422406870812523751782752760203007099691363415970022112059353122488603784759, 3080625635587790463492455041047370430855778314991197160023542543044414169153093879753095923, 2494582569622824488613286424880168833866083797958540523037274945622281503006144846230158592, 736453371727926563975780576378564042897000246860570612078472153355883504565297745661346599, 2209360115183779691927341729135692128691000740581711836235416460067650513695893236984039797, 6628080345551339075782025187407076386073002221745135508706249380202951541087679710952119391, 6389652362372923423617918165697344240816504371205304612052042773586932614356765546798099819, 5674368412837676467125597100568147805047010819585811922089422953738875834164023054336041103, 3528516564231935597648633905180558497738530164727333852201563494194705493585795576949864955, 3838255355555259891081823017279733034514339347166950599571337799073155476304249937820465688, 4767471729525232771381390353577256644841766894485800841680660713708505424459613020432267887, 807826514294604510416013664207885017122798389427300610975276774103594264472565475238545307, 2423479542883813531248040992623655051368395168281901832925830322310782793417696425715635921, 523144291510893691880044279609022695403934357830654541744138283421387375799952484117778586, 1569432874532681075640132838827068086211803073491963625232414850264162127399857452353335758, 4708298623598043226920398516481204258635409220475890875697244550792486382199572357060007274, 630307196513035877033038152919727858503725367397570713025028285355537137692443485121763468, 1890921589539107631099114458759183575511176102192712139075084856066611413077330455365290404, 5672764768617322893297343376277550726533528306578136417225254568199834239231991366095871212]
c = 312842359600262511112435880530064569250589001035021284923827012948353613267507190924348823432
n = len(b)
w = []
sum = 0
for i in range(n):
w.append(2*sum + 1)
sum += w[-1]
q = sum
while True:
if isPrime(q):
break
q += 1
r = ( b[0] * inverse(w[0], q) )% q
c = (c * inverse(r, q))%q
m = 0
for i in range(n-1, -1, -1):
if c >= w[i]:
m += 1 << i
c -= w[i]
print(long_to_bytes(m)) # sctf{kn4p5ack_Adventur3}
|