picoCTF 2022 に参加しました (cryptoのwriteup)

これはなに

picoCTF2022にチームSUSHi-ST0RMで参加しました．crypto問題(300点以上)のwriteupです．

writeup

Very Smooth(300pt)

概要

RSA暗号で，$e,n,c$が与えられる．

問題プログラムと各数$e,n,c$の値

gen.py

#!/usr/bin/python

from binascii import hexlify
from gmpy2 import *
import math
import os
import sys

if sys.version_info < (3, 9):
    math.gcd = gcd
    math.lcm = lcm

_DEBUG = False

FLAG  = open('flag.txt').read().strip()
FLAG  = mpz(hexlify(FLAG.encode()), 16)
SEED  = mpz(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)

def get_prime(state, bits):
    return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1)))

def get_smooth_prime(state, bits, smoothness=16):
    p = mpz(2)
    p_factors = [p]
    while p.bit_length() < bits - 2 * smoothness:
        factor = get_prime(state, smoothness)
        p_factors.append(factor)
        p *= factor

    bitcnt = (bits - p.bit_length()) // 2

    while True:
        prime1 = get_prime(state, bitcnt)
        prime2 = get_prime(state, bitcnt)
        tmpp = p * prime1 * prime2
        if tmpp.bit_length() < bits:
            bitcnt += 1
            continue
        if tmpp.bit_length() > bits:
            bitcnt -= 1
            continue
        if is_prime(tmpp + 1):
            p_factors.append(prime1)
            p_factors.append(prime2)
            p = tmpp + 1
            break

    p_factors.sort()

    return (p, p_factors)

e = 0x10001

while True:
    p, p_factors = get_smooth_prime(STATE, 1024, 16)
    if len(p_factors) != len(set(p_factors)):
        continue
    # Smoothness should be different or some might encounter issues.
    q, q_factors = get_smooth_prime(STATE, 1024, 17)
    if len(q_factors) != len(set(q_factors)):
        continue
    factors = p_factors + q_factors
    if e not in factors:
        break

if _DEBUG:
    import sys
    sys.stderr.write(f'p = {p.digits(16)}\n\n')
    sys.stderr.write(f'p_factors = [\n')
    for factor in p_factors:
        sys.stderr.write(f'    {factor.digits(16)},\n')
    sys.stderr.write(f']\n\n')

    sys.stderr.write(f'q = {q.digits(16)}\n\n')
    sys.stderr.write(f'q_factors = [\n')
    for factor in q_factors:
        sys.stderr.write(f'    {factor.digits(16)},\n')
    sys.stderr.write(f']\n\n')

n = p * q

m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)

c = pow(FLAG, e, n)

print(f'n = {n.digits(16)}')
print(f'c = {c.digits(16)}')

output.txt

e = 0x10001
n = 809fbd8b667d664f01fe1b0387e0b424efe2035e2dec4d249ace30563d0e1a50050020880c2f01bad63b22e21125d780d887cffdb1165268e6be788cd49ad8a9a1d27482f1a8ccbb37adc0deee65d09f312ebaab854782e2411d917181fef63d478b7e25391ac10d0330cafcb5c8d859ee1e403be029ce5dd75f864deabe5a65645b099afb7af4ed84dd75d1e4b966e2a0662ece5409feeacb2a277ddf05b72153ff6f36524f7693cc432269b56bd8ab3d601844aef6a6130eaaec08f92f9816ed0e7781a23a043570364807bef579c1e9175e3fe2b1d8f52356230feea244ce1b88b2342c9e40b25583a1fe558bdfb3a7115a4c71a6f06b706419ce8e21a3e1
c = 74ce97c4712bc3827a9f6021089c093a7540a6280330a9ec7c6f446a88093c33a6b9a0a1fdf2cad96e32344970adbf26601d9baf2c4e9892dde435dc994bde4754fddbac47a475b3907a455c6f671484b473b5481080224406b1d48d48da5ba0d9fccdc5732cb64c0f02c32ddc1413f66bd95b8e5a929e5b1f14843bd8f5d4747a4aabcc64217a187db6913facce48f2019b5524633153ee40a4376960b7f669f331da29227fa9a8c09a58a6f3db7453dd89a6093c062ff95502cc7cca5ee497c8ec6265413f5d05d1b720b4eb620875b6f6d2a7958e2391835497a106f4c280cd1ca8b9605bbef5952b54dffc028c160c1495e5cd2957f6f2bbb2e868823b6a

解法

$p$と$q$の作り方が鍵になってきそうです． gen.pyには親切にもDEGUB機能がついているため，これを使って$p$と$q$の生成過程を観察します．

p_factors = [
    2,
    9277,
    16057,
    33223,
    33961,
(中略)
    61837,
    61961,
    62743,
    63577,
    65407,
]

q_factors = [
    2,
    33161,
    48751,
    67391,
    67399,
(中略)
    126227,
    127163,
    127607,
    128047,
]

プログラムも合わせて見ると，$p$と$q$は小さな素数の積に$1$を足して作られていることがわかります(もし$1$を足しても素数にならなければ作り直している)．また，$p$と$q$で使われている素数の範囲も異なっています．この状況に対して，$p-1$法という素因数分解の手法が使えます．

$p-1$法は，互いに素な$a,p$で，フェルマーの小定理$a^{p-1} = 1 \pmod p$が成り立つことを使います．

$p-1$の倍数である適当な数$ M $を持ってきて， $ a^{M} $を計算すれば，$ a^{M} = 1 \pmod p $ が成り立ち，$ a^{M}-1 $ が $ p $ の倍数となります．

つまり，$ a^{M}-1 $と$ n $の最大公約数が$ p $となります．

今回は，$p-1$が$10^{5}$未満の素数の積であることから，$ M $を$10^{5}$以下の素数の積¹として，$a$は$2$を選びます．

この問題を解くにあたって下記の記事を参考にさせていただきました． wacchoz.hatenablog.com

プログラム

from Crypto.Util.number import *


n = #省略
c = #
e = 0x10001

a = 2
b = 1
for i in range(2,100000):
    if isPrime(i):
        b*=i
ab =pow(a,b,n)

p = GCD(ab-1,n)
q=n//p

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

Sum-O-Primes(400pt)

概要

RSA暗号で，$e,n,c$加えて$x=p+q$が与えられる．

各パラメータ

e = 65537
x = 1603fc8d929cb31edf62bcce2d06794f3efd095accb163e6f2b78941bd8c646d746369636a582aaac77c16a9486881a9e3db26d742e48c4adcc417ef98f310a0c5433ab077dd872530c3c3c77fe0c080d84154bfdb4c920df9617e986999104d9284516c7babc80dc53718d59032aefdf41b9be53957dea3f00a386b2666d446e
n = 75302ba292dc4bf47ffd690b8edc70ef1fcca5e148b2b9c1b60227788afcfe77a0097929ed3789fe51ac66f678c558244890a09ae4af3e7d098fd366a1c859edabbff1c9e164d5354968798107ae8518fcaab3743de58a141ffd26c1e16cb09fed1f6b0d68536ec7fba744ed120fea8c3a7ac1ebfa55d664d2f321fb44e814650147a9031f3bfa8f69d87393c7d88976d28d147398a355020bcb8e5613f0b29028b77db710e163ca1019fd3c3a065465ea457adec45243c385d12d3a1de3178f6ca05964be92e8b5bc24d420956de96ccc9ce39e70705660eb6b2f4e675aac7d6d7ba45c84223fc5819b37aa85beff1382f1c2c3b97603150f30c17f7e674441
c = 562888c70ce9a5c5ed9a0be1b6196f854ba2efcdb6dd0f79319ee9e1142659f90a6bae67481eb0f635f445d3c9889da84639beb84ff7159dcf4d3a389873dc90163270d80dbb9503cbc32992cb592069ba5b3eb2bbe410a3121d658f18e100f7bd878a25c27ab8c6c15b690fce1ca43288163c544bfce344bcd089a5f4733acc7dc4b6160718e3c627e81a58f650281413bb5bf7bad5c15b00c5a2ef7dbe7a44cce85ed5b1becd5273a26453cb84d327aa04ad8783f46d22d61b96c501515913ca88937475603437067ce9dc10d68efc3da282cd64acaf8f1368c1c09800cb51f70f784bd0f94e067af541ae8d20ab7bfc5569e1213ccdf69d8a81c4746e90

解法

連立方程式と見て，$p$と$q$を求めることもできますが，直接$ \phi = (p-1)(q-1)$を求めるほうが早いです． $$ \phi = (p-1)(q-1) = pq - p - q + 1 = n - x + 1$$

from Crypto.Util.number import *

phi = n-x+1
d=pow(e,-1,phi)
m=pow(c,d,n)
print(long_to_bytes(m))

Sequences(400pt)

概要

下の関数で，m_func(20000000)の値の下10000桁を求める問題．

def m_func(i):
    if i == 0: return 1
    if i == 1: return 2
    if i == 2: return 3
    if i == 3: return 4

    return 55692*m_func(i-4) - 9549*m_func(i-3) + 301*m_func(i-2) + 21*m_func(i-1)

つまり，

$$ a_0 = 1, a_1 = 2, a_2 = 3, a_3 = 4 $$

$$ a_i = 21a_{i-1} + 301a_{i-2} - 9549_{i-3} + 55692 a_{i-4} \quad (i>4) $$

のとき，$a_{20000000}$を$10^{10000}$で割った余りを求める．

解法

線形漸化式であるため，行列を使うテクニックを使って第n項を$O(\log n)$で計算することができます．

任意の項は次の行列を使った式によって表されます．

この行列を累乗をナイーブに計算すると結局$O(n)$かかってしまいますが， 繰り返し2乗法(ダブリングと呼ぶこともある)，という手法を使うことで$O(\log n)$で計算することが可能です．

この問題を解くにあたって下記の記事を参考にさせていただきました．

qiita.com

プログラム

import math
import hashlib
import sys
from tqdm import tqdm
import functools

ITERS = int(2e7)
VERIF_KEY = "96cc5f3b460732b442814fd33cf8537c"
ENCRYPTED_FLAG = bytes.fromhex("42cbbce1487b443de1acf4834baed794f4bbd0dfe08b5f3b248ef7c32b")

def mat_mul(a, b) :
    I, J, K = len(a), len(b[0]), len(b)
    c = [[0] * J for _ in range(I)]
    for i in range(I) :
        for j in range(J) :
            for k in range(K) :
                c[i][j] += a[i][k] * b[k][j]
            c[i][j] %= 10**10000
    return c


def mat_pow(x, n):
    y = [[0] * len(x) for _ in range(len(x))]

    for i in range(len(x)):
        y[i][i] = 1

    while n > 0:
        if n & 1:
            y = mat_mul(x, y)
        x = mat_mul(x, x)
        n >>= 1

    return y


d0 = 0
ret = [[4], [3], [2],[1]]
mat = [[21,301,-9549,55692], [1, 0, 0, 0], [0, 1, 0, 0],[0,0,1,0]]
#ret = mat_mul(mat_pow(mat, ITERS), ret)
#ret = [[1],[1]]
#mat = [[1,1], [1,0]]
ret = mat_mul(mat_pow(mat, ITRES), ret)
print(ret)


# Decrypt the flag
def decrypt_flag(sol):
    sol = sol % (10**10000)
    sol = str(sol)
    sol_md5 = hashlib.md5(sol.encode()).hexdigest()

    if sol_md5 != VERIF_KEY:
        print("Incorrect solution")
        sys.exit(1)

    key = hashlib.sha256(sol.encode()).digest()
    flag = bytearray([char ^ key[i] for i, char in enumerate(ENCRYPTED_FLAG)]).decode()

    print(flag)

if __name__ == "__main__":
    sol = A
    decrypt_flag(sol)

NSA-backdoor(500pt)

概要

離散対数問題

問題プログラム

#!/usr/bin/python

from binascii import hexlify
from gmpy2 import *
import math
import os
import sys

if sys.version_info < (3, 9):
    math.gcd = gcd
    math.lcm = lcm

_DEBUG = False

FLAG  = open('flag.txt').read().strip()
FLAG  = mpz(hexlify(FLAG.encode()), 16)
SEED  = mpz(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)

def get_prime(state, bits):
    return next_prime(mpz_urandomb(state, bits) | (1 << (bits - 1)))

def get_smooth_prime(state, bits, smoothness=16):
    p = mpz(2)
    p_factors = [p]
    while p.bit_length() < bits - 2 * smoothness:
        factor = get_prime(state, smoothness)
        p_factors.append(factor)
        p *= factor

    bitcnt = (bits - p.bit_length()) // 2

    while True:
        prime1 = get_prime(state, bitcnt)
        prime2 = get_prime(state, bitcnt)
        tmpp = p * prime1 * prime2
        if tmpp.bit_length() < bits:
            bitcnt += 1
            continue
        if tmpp.bit_length() > bits:
            bitcnt -= 1
            continue
        if is_prime(tmpp + 1):
            p_factors.append(prime1)
            p_factors.append(prime2)
            p = tmpp + 1
            break

    p_factors.sort()

    return (p, p_factors)

while True:
    p, p_factors = get_smooth_prime(STATE, 1024, 16)
    if len(p_factors) != len(set(p_factors)):
        continue
    # Smoothness should be different or some might encounter issues.
    q, q_factors = get_smooth_prime(STATE, 1024, 17)
    if len(q_factors) == len(set(q_factors)):
        factors = p_factors + q_factors
        break

if _DEBUG:
    import sys
    sys.stderr.write(f'p = {p.digits(16)}\n\n')
    sys.stderr.write(f'p_factors = [\n')
    for factor in p_factors:
        sys.stderr.write(f'    {factor.digits(16)},\n')
    sys.stderr.write(f']\n\n')

    sys.stderr.write(f'q = {q.digits(16)}\n\n')
    sys.stderr.write(f'q_factors = [\n')
    for factor in q_factors:
        sys.stderr.write(f'    {factor.digits(16)},\n')
    sys.stderr.write(f']\n\n')

n = p * q
c = pow(3, FLAG, n)

print(f'n = {n.digits(16)}')
print(f'c = {c.digits(16)}')

解法

と はどちらも小さな素数の積であるため， も小さな素数の積に分解できます． つまり，Pohlig–Hellman algorithm が使えます． Pohlig–Hellman algorithm は，現実的な時間で解くことのできる小さな離散対数問題に分割し，中国剰余定理で結果をもとの問題の答えとして復元する，という手法です．

この問題を解くにあたって下記の記事を参考にさせていただきました．

sonickun.hatenablog.com

プログラム

from Crypto.Util.number import *

n = 0x71c27455f38b75f08868b5965d7afba3d81bff38f3b63271ad9250b9d7dc8c909d3555593c2eff9c27a3c259f8e95da41d55544a362494476141c8ccb93fc7d9019d965a20e16d55daf57b5663ede8d5ad97b7be239ecacb2636621ef997854f18f6da1394101dfb8229a2253dbc3ffc995cc6197bd85455f6178c14dbb9a611b3b42530fcdc5c36c5f63fd3796efdfc440a76cf966ff8c56e7e55872a57aa3a335c2b10a82421bcd1cd0d238496f2830d6524f6ba8e9890e30c4e6ad11df8948f4b428d8089a5d9455baca34cee61cb238042bcf8293aab13595aeb90fedabf23b1d0e82c6882824aa0f78c2208de641d9592a170ed839728f6c7e6b6bdf831
y = 0x2560971fdf742d398ae3e677082ab950e99edde5577abcc4d704d65577ec287169d209f2033c82e7574f7e6c27540bb07416cd12b5fca1bb5c7ae23e80bb00b81a5c49116fa3cca6ab72f4a56b2bf0d51c58eedb918faa1e88d6fddb7dd358c1cdaa6e61964284014919662f75adaad5065a3633067b2297cd4657d39c8e2cdb02fd80ba33447abb8bfcd4dd68166f487094108afe5b4378f5f6eb9209f503b718dec9c841089551db648f5b5a84357b2319eb1b27935c3bc47c645f732d36cfffcb0e7f1c8ec5859413e6d62f7ed9af27f4712ca91bbdb9526ea19414c82090a52a78e6bbc2a756b5756017ee08326cd7b1d5dd9fff6afb12bcb93fb541a542

print(f'n = {n}')
print(f'c = {y}')

# get p and q with using p-1 method
p=133120514134071565184901374403906104857402594315193452979400334844456988039351029748429497538981454221984106135005043996378098395846705709422658663585864970394230279241392567216599860405945469882804839379543093459226432299183847151658790842646530907008354991523758458009950957111989465047584759069188272154703
q=107878320716069936845347261730222923402619282584236808136469656719645067255143372538361375857163594280233925663413568686520703251291382637679919197208920902793419007945364505474185442005931731898039583502138819092649272834779913753377381462765827012568092442233669634217190652686190269458879367972776287369087
assert p*q==n
# factors of phi = (p-1)(q-1)
phi=[2, 2, 10369, 11437, 11969, 12491, 33343, 34369, 34687, 34939, 35969, 36467, 36709, 36919, 36973, 36997, 37361, 37379, 37561, 38867, 40897, 41203, 41593, 41801, 42221, 43189, 43481, 43951, 44029, 44953, 45161, 45751, 46649, 46703, 47017, 47221, 49409, 49499, 49783, 50321, 50539, 52081, 53077, 53299, 54367, 54601, 54829, 55147, 55399, 55457, 55661, 56039, 56237, 56267, 56299, 57089, 57373, 57637, 57731, 58897, 59753, 60223, 60733, 61673, 61781, 62459, 62969, 63781, 63901, 64399, 65551, 67651, 68207, 68947, 72287, 74653, 74857, 75011, 77081, 77153, 77239, 78467, 78691, 78877, 81343, 83701, 85009, 88037, 88117, 88397, 89269, 89363, 89477, 90403, 90901, 91009, 94057, 95701, 98387, 100853, 104161, 105097, 106657, 107021, 109121, 109807, 110681, 111599, 112901, 113797, 114883, 115163, 115727, 116009, 117037, 117413, 118799, 120413, 123229, 123973, 124067, 124427, 
125863, 125887, 126631, 127481, 128311, 129671, 129793, 130589]
m=1
for i in phi:
    m*=i

assert m==(p-1)*(q-1)

g=3

def extgcd(a, b):
    if b:
        d, y, x = extgcd(b, a % b)
        y -= (a // b) * x
        return d, x, y
    return a, 1, 0

# V = [(X_i, Y_i), ...]: X_i (mod Y_i)
def remainder(V,W):
    x = 0; d = 1
    for i in range(len(V)):
        X=V[i]
        Y=W[i]
        g, a, b = extgcd(d, Y)
        x, d = (Y*b*x + d*a*X) // g, d*(Y // g)
        x %= d
    return x, d


# Baby-step giant-step
def baby_step_giant_step(g, y, p, q):
    m = int(q**0.5 + 1)
    
    # Baby-step
    baby = {}
    b = 1
    for j in range(m):
        baby[b] = j
        b = (b * g) % p

    # Giant-step
    gm = pow(inverse(g, p), m, p)
    giant = y
    for i in range(m):
        if giant in baby:
            x = i*m + baby[giant]
            print("Found:", x)
            return x
        else:
            giant = (giant * gm) % p
    print ("not found")
    return -1


# Pohlig-Hellman algorithm
def pohlig_hellman(p1,p2, g, y, Q):
    print ("[+] Q:", Q)
    X = []
    for q in Q:
        x = baby_step_giant_step(pow(g,((p1-1)*(p2-1))//q,p1*p2), pow(y,((p1-1)*(p2-1))//q,p1*p2), p1*p2, q)
        X.append(x)
    print ("[+] X:", X)
    x ,d= remainder(X,Q)
    return x,d


x,d = pohlig_hellman(p,q, g, y, phi)
print(long_to_bytes(x))
print(long_to_bytes(d))

感想

400点のSum-O-Primesよりも300点のVery-Smoothの方が難しいと感じました．あと，全完できたので嬉しいです．

---

1. $ M $の値は小さな素数の積であれば何でもいいわけではなく，もし$ M $を$1.5\times 10^{5}$程度までの素数の積にしてしまうと，$ M $が$(p-1)(q-1)$の倍数になってしまい，$ a^{(p-1)(q-1)} =a^{M} = 1 \pmod n$が成り立つため，$n$と$a^{M}-1$の最大公約数が$n$になってしまいます．また，この問題は素数生成の際に同じ素数が2度以上使われていないことがわかっているので，ソルバでは各素数を1度しか掛け算していませんが，わかっていない場合は$p-1$が$2^{4}$や$3^{2}$のような約数を持っている可能性があるので，同じ素数も何度か掛けておくべきです．↩

今年解いたCrypto問題を振り返る(2021年)

これはなに

こっそりいくつかのctfに参加したりあとから問題を覗いたりして，Crypto問題だけ解いてました．
今後似た問題と遭遇したときのために備忘録として書きます．

そして公開日が12/26のくせになんとアドベントカレンダー24日目の記事です．
qiita.com

全部で4問あります．

K3RN3LCTF - Pascal RSA

問題概要

triangle =[[1]]
flag = open('flag.txt','rb').read()

from Crypto.Util.number import getPrime,bytes_to_long
from math import gcd
p = getPrime(20)
while len(triangle[-1]) <= p:
    r = [1]
    for i in range(len(triangle[-1]) - 1):
        r.append(triangle[-1][i] + triangle[-1][i+1])
    r.append(1)
    triangle.append(r)
code = ''
for x in triangle[-1]:
    code+=str(x%2)
d = int(code,2)
while True:
    P = getPrime(512)
    Q = getPrime(512)
    if gcd(d, (P-1)*(Q-1)) == 1:
        N = P*Q
        e = pow(d,-1,(P-1)*(Q-1))
        break
enc = pow(bytes_to_long(flag), e, N)
file = open('challenge.txt','w')
file.write(f'p = {p}\nenc = {enc}\nN = {N}')

p = 751921
enc = 9820620269072860401665805101881284961421302475382405373888746780467409082575009633494008131637326951607592072546997831382261451919226781535697132306297667495663005072695351430953630099751335020192098397722937812151774786232707555386479774460529133941848677746581256792960571286418291329780280128419358700449
N = 84317137476812805534382776304205215410373527909056058618583365618383741423290821410270929574317899945862949829480082811084554009265439540307568537940249227388935154641779863441301292378975855625325375299980291629608995049742243591901547177853086110999523167557589597375590016312480342995048934488540440868447 

考えたこと

プログラムは，

1. 素数$p$を元にtriangle二次元配列を作る
2. それを使って$d$を作成
3. 素数$P,Q$が生成され$N=PQ$，$e=d^{-1} \bmod N$として$enc = (flag)^{e} \bmod N$が計算される
4. $p,enc,N$が出力

を行っていて，$(enc)^d= (flag)^ed =(flag)^1 \bmod N$を計算すれば$flag$が求まるので$d$が欲しい．

$d$は$triangle$配列の各数にパリティによって決定され，$triangle$はパスカルの三角形．
詳しくは，パスカルの三角形を$p+1$段作り，最下段の数のうち奇数を1,偶数を0として横に並べたものを左から2進数とみて，それを$d$としている．

ここで，$p=751921$がわかっているので，実際にパスカルの三角形を作って$d$が求められるが，$O(p^2)$かかるため非常に時間がかかる．
どうにかして$p+1$段目のみを直接計算する必要がありそう．
パスカルの三角形の意味を考えると，各数は二項係数になっているため，最下段は$_pC_i$を表している．
二項係数の偶奇，すなわち$2$で割ったあまりはルーカスの定理を使用すれば高速に求められる！

プログラム

ルーカスの定理の$\bmod 2$の場合はビット演算で$O(1)$で求められます．

p = 751921
enc = 9820620269072860401665805101881284961421302475382405373888746780467409082575009633494008131637326951607592072546997831382261451919226781535697132306297667495663005072695351430953630099751335020192098397722937812151774786232707555386479774460529133941848677746581256792960571286418291329780280128419358700449
N = 84317137476812805534382776304205215410373527909056058618583365618383741423290821410270929574317899945862949829480082811084554009265439540307568537940249227388935154641779863441301292378975855625325375299980291629608995049742243591901547177853086110999523167557589597375590016312480342995048934488540440868447


def is_nCk_odd( n,k):
    return n&k == k

code=''
for i in range(0,p+1):
    ch=is_nCk_odd(p,i)
    if ch:
        code+='1'
    else:
        code+='0'

d=int(code,2)

print(hex(pow(enc,d,N)))

idek - Destroyed RSA

問題概要

RSA暗号で，各パラメータがわかります．

n=1107089530865291005792928480548189885479977703442107533313356742591951667125087535826010797157037462511849114045516095117408586807231706532861043400760247491545435256670371588020835746662537074526723641129179212527096161455117334264697975671817050553066298766943783138197527420889207777538892682506714149210612017224796083819420558023833783052917520724666512823601961316820680461331809092698744718706733677296285030329390980535993866209005527261307419128592439300515586162373258781346476786339580690681056167085317745381659204404735103663112312693895151699459534695810700103198736323229849182269856798173444808702578924983265251814786149856862410628895786620259450924651662102926294106305830166586486290823127164862167085238586221495862582249250498351063486438791642573599997108715545357001141390463446119948917429169048381714872075664706511363903028841832059662969788526342879432038294204060254076089346916015904423832151508649589004393115281760187305175538986217342069866841444503926477979016789070563231454129660241269241703644048193901022392096029852555194381071481792694321652042639278577632914177886450520371875549477493674646527815335341293227066407822982856815277497965140254717599437693337147736442753971955722420621907486011
p=36984002748507170891753731406126456416455992571790181677355704906806965226019238824877042494690893998579858694111411376511253440817505962720769835375650471685769471414118510774533150115499644554157393860475762756716310600646166773019267339855093152750395193553746652677602677776044436793635218677785744671419934810989547208990895631879209745428788589809123973606636033943819211438418326058364282178941980077621277854916308671126967906285068857212366779324466914715729553717164382649849824461928856952183975506817514230213608208371112629129318318247510911612301933407885682758975715426046251265646994864308390350130597
q=29934281002344392584917041715572452186213480993633769076547996710425134248100828277592343431170595254088836916660834689235026786084921641309257834412549082271979733777849147751813839475093849198230955115891279535391278974673199880605616268135363608516171875844412554370669853436778763238712799066154529158577804567624075485413272553162482452019391457208428519791195318467405021196329420684098999738549035239634242441609101096054948406319959608539620961927531536528883122477541022179797553950933620777436215821991811508533829734240459263426901285492628622233303498344386289944426215246507874026244979669057103099687263
e = 6551
c=1058973149865164549817155137780815812623456388672543624635614085499244505987561039674767711743995552767627702752408380616883846211075499731545623651849875151404363710832001498313789374024771997636035858261588415813326816005995068929381352608925142940988357078368871961040798086164564448858106053108740194519944625550651430368864502736439474454098320996590422347650921528404245531928248700516748854749201075928521539792773428322450795957658901093109369813686410937987553062385702498313602204488073904351501964183374202465473380985602391885101503608627656341003137115517005592591746184951205036757837506166599417314523057848473058411480339477693062957272869601856015496182168433136199994935250109784152100245527161736252507193119985157036229139371883973535111593404077185046749750799222687057579590699112612517984739574870394435873979331373499970168615775526148858445852147161884965435806142797327740412603655959161046424598064190354357612721920648035385092037901968197029138094288551013982417040611621259974923351358663093743109476722870043782424356300204605852351738436494837101112320000689343206094235482366575795725469918145189121430260345459865260920783660140849521053205162497433393126952425091234633490186637000777737106192645410

考えたこと

$\phi = (p-1)(q-1)$として$e^{-1} \bmod \phi$を求めようとするが，$\phi$と$e$が互いに素でないので$e$の逆元が存在しない．
けれども，いつものRSA暗号よりも$p$と$q$が大きく感じる．これより，$p,q$よりも平文が小さいと推測し，$\bmod p$の世界で考える．

プログラム

オイラーの$\phi$関数より$\phi=p(p-1)$です．

import binascii

phi =(p-1)*p
d=pow(e,-1,phi)
m=pow(c,d,p)
print(binascii.a2b_hex(hex(m)[2:]))
# idek{A_mashup_of_2_interesting_papers?_4p-1_and_coprime_e-phi}

idekCTF - Polyphenol

問題概要

import random
from secret import flag

assert flag[: 5] == b"idek{"
assert flag[-1:] == b"}"

L = len(flag[5: -1])
print(f"L = {L}")
coeff = list(flag[5: -1])
points = random.sample(range(L), L // 2)
evaluations = []

for p in points:
	evaluations += [sum(c * p ** i for i, c in enumerate(coeff))]

print(f"points = {points}")
print(f"evaluations = {evaluations}")

L = 34
points = [4, 26, 22, 30, 1, 0, 2, 28, 23, 6, 25, 15, 5, 17, 14, 3, 13]
evaluations = [6218619148819094267912, 3239660278168289094170378865781537878483145039862, 13167423991006904868698304825721530103488567362, 362300164581366743933077318596814390341728710066538, 2912, 68, 1115908868222, 37269531510352347514290324712333731253807861642016, 56973337294691266392513915302684316231304471586, 3613524058959314538010460402, 889396341293302641051808753025749133146757798168, 43685960244566626421146033917835089685178, 9183044381254551882537188, 2694648608589552169772471076958756166751152, 4505915953382938147124977926390455694362, 529597204775372366, 392892826701163426612412172019222254476]

考えたこと

プログラムが次のことをしている．

1. フラグの長さ$L=34$
2. 長さ$L/2$の配列$p$がランダムに生成される
3. 各$p$について$\sum_i c_i\cdot p^i$が計算され，それがevaluations配列(以下要素を$e_j$とする)として出力される．$c_i$はflagの$i$文字目(0-indexed)

$i=0$のことを考えると，$c_i\cdot p^0$すなわち$c_i$がそのまま出力されている．
もし，$c_0$が確定したのなら，各$j$について，$e_j-c_0$は$p$で割り切れるはず．
よって$c_0$を全探索して，$e_j-c_0\bmod p=0$となる$c_0$を探せばいい．

これで$c_0$が判明すると，$e_j-c_0$は，
$$\cdots c_4\cdot p^4+c_3\cdot p^3+c_2\cdot p^2+c_1\cdot p^1$$
であるから，これを$p$で割って
$$\cdots c_4\cdot p^3+c_3\cdot p^2+c_2\cdot p^1+c_1\cdot p^0$$
となる．さっきと同じく$c_1$を引き算した値は$p$で割り切れればいいので，同じく$c_1$を全探索すればよい．
これを繰り返していけば全ての$c_i$が判明する．

プログラム

L = 34
points = [4, 26, 22, 30, 1, 0, 2, 28, 23, 6, 25, 15, 5, 17, 14, 3, 13]
evaluations = [6218619148819094267912, 3239660278168289094170378865781537878483145039862, 13167423991006904868698304825721530103488567362, 362300164581366743933077318596814390341728710066538, 2912, 68, 1115908868222, 37269531510352347514290324712333731253807861642016, 56973337294691266392513915302684316231304471586, 3613524058959314538010460402, 889396341293302641051808753025749133146757798168, 43685960244566626421146033917835089685178, 9183044381254551882537188, 2694648608589552169772471076958756166751152, 4505915953382938147124977926390455694362, 529597204775372366, 392892826701163426612412172019222254476]

flag=b''

for i in range(L):
    print(i)
    
    for c in range(128):
        ok = True
        for j,p in enumerate(points):
            if p==0:
                continue
            if (evaluations[j]-c)%p!=0:
                ok=False
        if ok:
            flag=flag+bytes([c])
            break
    
    print(flag)
    if len(flag)<=i:
        break
    
    for j,p in enumerate(points):
        if p==0:
            continue
        evaluations[j]=(evaluations[j]-flag[i]) // p

print(flag)

ASIS CTF Finals - stair

問題概要

インタラクティブ問題で，整数$ m $を与えると，
$(m+f)^5 + m+f \bmod N$の値が得られる．ただし，$N$は与えられていて，$f$が$flag$をエンコードした整数．

考えたこと

$m=0$をツッコめば$f^5+f \bmod N$がもらえるが，これだけでは$f$がわからない．
いろんな$ m $に対する値を求めて，差分を使えば$f$が求められそうに見える．
せいぜい5乗だから5個くらい連立すれば求められそう．
sagemathに連立合同方程式の解を求める機能があると嬉しいが，検索しても情報が見つからないので自力でやることにした(知っている方がいれば教えていただきたいです)．
$m=0,1,2,3,4$のときの値を使うと$120f +240 \bmod N$の値がわかるので，$240$を引いて$120$の逆元を掛け算すれば$f$が得られる．

プログラム

配列fは$m=0,1,2,3,4$にしたときの値です．

#R, t = QQ['t'].objgen()
#f=[]
#
#for i in range(5):
#    f.append( (t+i)**5 + t+i )
N=26988480498549621160245719900903773232840133632092297127594267334625529876976567682696748909369604307829651367885173095648610898772155393424116881932377221727862169668643423945930632234830754314591119837812803280535627188168965771909142681188203416675060421505442173186401565213575135378512462997278191411587241912090506266759586550889109151809874920511159366347810063459052745819442622154442058802011002148677617743211040695825214353014636602312764287004302711193427903045229183477950620693238823860006014265413878884235271462570833448784828338773641090407644755768854808432704391895324251672027902608709822270571071

f=[7678362696224158956701891820260394322994444797134797509334898256237146486825801472927211891948373682506250939990802637395815706180623415855149741953776176055751156241260147038974404936634988564631047217184263400661620152919050573840562356351476554657104647343763809819409861741939562400931934650138514735572988980993806819120866951461870234494460541725144896871734651790217891303509247078749652558277274167508705770696323811414745227700584203806687715766468950519359927358705878416874611802144155422995089769048614986692238802133901914397516042752676004147573266403361112062581792833558029226248737403199527438101506,
14788325360699107531306883919556661064144694519471445922375722388450018317715071448645425976259873338645456550465992743602233105598367448123297061726949072210596288375462294436390394768943351588656958020779127908522908375145662787356823775692477212852561741562973843495730657757120104974270301648537189578177935723642798567001071035939064945165499393719867511733557712586650030399158140495127084644514974254698883657787832456262952225317851149173187482987991183508960271215005204373037324993641153123036288642461886338701109931921696160086233560207701523685353360356073766738874059155880544426943413197189649763340469,
21898288025174056105911876018852927805294944241808094335416546520662890148604341424363640120308705001328139799218998060015220942233233701538823483287890909370769140314557114171968074199480696460085493743859515498285671834353430141248665625350519376847518062995201731923444520473050821056431972562163140276496932676822592113294620726369076656350511158871574580444106607129983841062022948596916098177172143748496868607261996723630121751958059224066318699169970404234748180746499874149125182858370225434592223825067602214818918707522969362030582810133458711106275622375979468758972194206769242862002115016442569191670002,
2019770191099383520271148217245421313605060332052445620863103318250232102517043717385105414725264362724649318364645490986168317313066782677612124704224465808407542389901182299776810993416268864325534548612622889414283342373386863606945224137399629966913190135005314360201431489751672235765133723328700215283026889601838380167605348282189309021862550825208429644683376091750387313918390873545491852150335373967558575026248766078766442683294484810240993392208645810520091041566321843792752435210298734407372786599215959432578668401548719075249453389171411072742265840059681198511185651880203553468467815910403957235784,
9129732855574332094876140316541688054755310054389094033903927450463103933406313693103319678248760038494287843673281227812297028382177478387896749840704184979235833938781346711677869620411577430559320110664056642979997275543464498249947934429524805560867965993268949622856068047968026236155360456180777014050991147320707090064873879876014299581545044759189485020020250520638970634987053277770240771384108302208704746621142823647041991599554522837644776555616935109506734178564089606937235925590812881349191169371998982998804490076888309687538840639371530995031780991087826941206924626040375611741008453199170472273187
]

f2=[]

for i in range(4):
    f2.append(f[i+1]-f[i])

f3=[]
for i in range(3):
    f3.append(f2[i+1]-f2[i])

f4=[]
for i in range(2):
    f4.append(f3[i+1]-f3[i])

f5=[]
for i in range(1):
    f5.append(f4[i+1]-f4[i])

# f5[0] = 120f +240

m=((f5[0] -240)*pow(120,-1,N))%N
print(hex(m))

あとがき

RSA暗号系はちょっとだけ慣れてきましたが，楕円曲線暗号やブロック暗号の問題はさっぱりです．来年はここらへんも理解できるようになりたい......

真理値表の情報から簡略化(クワイン－マクラスキー法+α)

これはなに

4変数の真理値表からできるだけ簡単化した式を出力するプログラムを作りました．

発端は学校で課せられた実験レポートを書く際面倒な作業が多かったため自動化したいと思ったからです．
https://shibaken28.github.io/KarnaughMap/

簡略化の表示に成功！！！https://t.co/EYLrRtRp6V pic.twitter.com/c0zaA257m6

— しばけん💧 (@Shibaken_8128) 2021年11月19日

また，この記事は長野高専 Advent Calendar 2021の4日目の記事です．
qiita.com
3日目と5日目の記事はこちら
3日目↓
qiita.com

5日目↓
https://qiita.com/advent-calendar/2021/nnct
5日目は誰も入っていませんでしたorz

実装

JavaScriptで実装します．

準備

真理値表と配列

$bitState$という名前の配列に真理値表での出力値を格納しています．
入力の変数の数が$N$個のとき，$N$個の入力それぞれについて$0$か$1$の2通りあるので，配列$bitState$の大きさは$2^N$になります．
下の表のように入力$p$を横に並べて2進数と見た数字に出力を格納することにします．

例えば，次のような入力が2つの真理値表があったとすると，

$p_1$	$p_0$	出力$Z$	対応する添え字
$0$	$0$	$1$	$00_{(2)}=0_{(10)}$
$0$	$1$	$1$	$01_{(2)}=1_{(10)}$
$1$	$0$	$0$	$10_{(2)}=2_{(10)}$
$1$	$1$	$1$	$11_{(2)}=3_{(10)}$

$bitState$配列の中身は$bitState=\{1,1,0,1\}$になります．

厳密に表現すると，入力の変数を$p_0,p_1,p_2,...,p_{N-1}$とおくと，添字が$\displaystyle \sum_{\substack{i}} 2^{i} p_i$のところに出力を格納します．

ビット列

前節のように添字は$10$進数の整数として扱っているので，入力の組み合わせを得るには$2$進数に変換をする必要があるます．
$2$で割ったあまりを出して2で割る，を繰り返して2進数に変換する方法がありますが，ここでは任意の桁(bit)の情報を得られるbit演算を使います．
$i$桁目(右から0-indexed)は$2^i$の位を表していますので，$AND$演算によりそのbitが立っているかがわかります．

N & 1<<i //Nのi桁目が立っているか

これにより，for文を回せば次のような関数が作れます．

function toBin(n,k){//10進数整数nをk桁0埋め2進数表示へ
  s=""
  for(var i=0;i<k;i++){
    s=(1<<i&n?"1":"0")+s;  
  }
  return s;
}

クワイン－マクラスキー法(QM法)

QM法(の一部)によって，主項を求めます．カルノー図では長方形で$1$を囲むことで簡略化しますが，この長方形にあたるのが主項です．ただし，カルノー図で囲む長方形は，その長方形自身を完全に含む別の長方形がないことが条件です．私はWikipediaを見ながら実装しました．

次のような真理値表で説明します．

$p_2$	$p_1$	$p_0$	出力
$0$	$0$	$0$	$1$
$0$	$0$	$1$	$1$
$0$	$1$	$0$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$1$
$1$	$0$	$1$	$1$
$1$	$1$	$0$	$0$
$1$	$1$	$1$	$1$

まず，出力が$1$である入力のbit列を書き出します．この場合，$\{000,001,010,011,100,101,111\}$の$7$つです．これらを項と呼ぶことにし，今からこの項たちをまとめていきます．
これらの項のうち，ある$1$ビットのみ異なっている$2$つの項の組み合わせを見つけます．
例えば$010$と$000$は$1$ビット目のみが異なっているので$0\_0$としてまとめられます(記号$\_$は$0$か$1$を表します)．
ここで，全ての組み合わせに関して比較しても良いですが，立っているビット数の数によってグループ分けをし，
$i$個ビットが立っているグループの要素と$i+1$個ビットが立っているグループの要素同士のみを比較しても問題はありません．
なぜなら，まとめられるbit列はどれも立っているビットの数が必ず$1$つ違うからです．これにより少し高速化が可能です．

グループ分けすると次のようになります．

$0$個	$000$
$1$個	$001,010,100$
$2$個	$011,101$
$3$個	$111$

これで必要な比較回数が${}_7 \mathrm{C}_2 =42$回から$1\cdot 3+3\cdot 2+2\cdot 1=11$回に減りました．
各要素を比較し，$00\_,0\_0,\_00,0\_1,\_01,01\_,10\_,\_11,1\_1$の9項が得られます．
今回は出ませんでしたが，ペアが一つも見つからない項は，これ以上まとめられないという意味なので主項として取っておきます．

そして，再び立っているビット数でグループ分けをし，

$0$個	$00\_,0\_0,\_00$
$1$個	$0\_1,\_01,01\_,10\_$
$2$個	$\_11,1\_1$

同様に，$i$個ビットが立っているグループの要素と$i+1$個ビットが立っているグループの要素同士を比較します．
これらをまとめると，$0\_\_ , \_0\_ , \_\_1 $(このとき$\_$は一つの文字として認識します．)になります．

これを繰り返し，

$0$個	$0\_\_ , \_0\_$
$1$個	$\_\_1$

ここでどの項もペアが見つからなかったので全て主項になります．
このグループ分け→ペア探しの作業は高々(変数の数+1)回で終わります．なぜなら，1回の作業につき，ビット列の$1$が$\_$がに変化して立っているbitの数が一つ減るからです．

擬似コードを示します．ここで使われている集合は重複が許されません(集合$\{1,2,3,4\}$に，既に要素である$4$が追加されても集合は$\{1,2,3,4\}$のままです)．

// 入力の変数の数はn
// S[i]:=i個ビットが立っているビット列のリスト，T[i]も同様
// M:=主項の集合
// used:=ペアが見つかった項の集合

for t = 0~n
    usedを空にする
    Tを空にする
    for i = 0~n-1
        for j = 0~(S[i]の長さ-1)
            for k = 0~(S[i+1]の長さ-1)
                if S[i][j]とS[i+1][k]で1ビットだけ異なる
                    T[i] に S[i][j]とS[i+1][k]の異なる部分を"_"に変えたものを追加
                    used に S[i][j]とS[i+1][k]を追加
            if used に S[i][j]が含まれない
                M に S[i][j]を追加
    S に T をコピー

次に実際のコードを示します．
少し違いがあり，

• 擬似コードでは$S,T$と2つ配列を用意していますが，実際のコードは一つの配列を使いまわしている
• 擬似コードではペアが見つかったかどうかを$used$のみで判断しているが，実際のコードはペアが見つかったかの別のフラグfindを用意している

などの点があります．

擬似コードの方がコンパクトです(擬似コードを後に書いたので)．

function simplification(){
  var bitNum = new Array(vars+1);//bitNum[i]:=ビットがi個立ってる数の配列
  var uniquBits = new Set();//主項の集合
  //countBits
  var i,j,k,l;
  for(i=0;i<=vars;i++){
    bitNum[i]=new Array(0);
  }
  for(i=0;i<bitState.length;i++){
    if(bitState[i]==1)bitNum[countBits(i,vars)].push(toBin(i,vars));//ビットの数を数えてその場所に入力を表す2進数をpushする．
  }
  for(var t=0;t<=vars;t++){//高々(変数の数+1)回繰り返せばよい．
    var used = new Set();
    for(i=0;i<bitNum.length;i++){
      var len=bitNum[i].length;
      var csd=i+1;
      for(j=0;j<len;j++){
        var find=false;
        if(i==bitNum.length-1){
          if(!used.has(bitNum[i][0]))uniquBits.add(bitNum[i][0]);
          bitNum[i].shift();
          continue;
        }
        for(k=0;k<bitNum[csd].length;k++){
          //i,0とi+1,xを比較
          var a=bitNum[i][0];
          var b=bitNum[csd][k];
          var dif=0;//違いの数
          var out="";
          for(l=0;l<min(a.length,b.length);l++){
            if(a.charAt(l)!=b.charAt(l)){
              dif++;
              out+="\\d{1}"; //正規表現．0と1どちらでも良い
            }else{
              out+=a.charAt(l);
            }
          }
          if(dif==1){
            find=true;
            used.add(b);
            bitNum[i].push(out);//ビットがi個立っている，再び配列にpushする
          }
        }
        if(!find&&!used.has(bitNum[i][0])){
          uniquBits.add(bitNum[i][0]);
        }
        bitNum[i].shift();//配列の先頭を削除
      }
    }
  }

bit全探索で候補を列挙

Wikipediaには主項が求まった後には必須項を求める，とありますがその方法が試行錯誤またはぺトリック法と書いてあります．
が，ペトリック法を実装するのが面倒なので，全探索で殴りました．
前節の手順で$N$個の主項が求まっていれば，これらの項の組み合わせは$2^N$通りあります．これらを全列挙して，真理値表を満たしているかを確認すれば良いです．
$2^N$通りの全探索はbit全探索でできます．

任意の一文字記号$\_$を正規表現にしておくとちょっと楽ができます．

//(前のコードの続き)
  uniquArr = [...uniquBits];
  
  result = new Array(0);
  var num = uniquArr.length;
  for(i=0;i<(1<<num);i++){
    var ok=true;
    for(j=0;j<bitState.length;j++){
      if(bitState[j]==0)continue;//そもそも関係ない
      var match=false;
      for(k=0;k<num;k++){
        if(i&(1<<k)){
          var re = new RegExp(uniquArr[k]);
          if(toBin(j,vars).match(re)!=null){
            match=true;
          }
        }
      }
      if(!match)ok=false;
    }
    if(ok){
      result.push([]);
      for(k=0;k<num;k++){
        if(i&(1<<k)){
          result[result.length-1].push(uniquArr[k].replace(/\\d\{1\}/g, '*'));
        }
      }
    }
  }
}

こうして，簡略化を表す$result$配列に文字列が出力されます．

遊んでみた

4変数の場合はhttps://shibaken28.github.io/KarnaughMap/で遊ぶことができますし，実際4変数ならカルノー図書けば人力でも全然いけます．
せっかくなのでクワインーマクラスキー法の本領発揮ができる5変数以上でやってみます．
5変数になるとカルノー図が3次元に拡張しないと書くことができず人力だとなかなか苦労するでしょう．

まずは6変数で試してみました．真理値表は$2^6=64$行もあるので一部省略します．

これの出力が

これです．良さそうですね．

8変数にしてみました


良さそうです．

10変数...入力は$2^{10}=1024$通りです．表示がカクカクになったのでp5jsのフレームレートを落としました．


合っているかどうかすぐにはわかりませんが，たぶん合っているでしょう．

速度の問題で，一番のボトルネックは明らかに最後のbit全探索$\mathrm{O}(2^N)$ですね．
ここで必須項をペトリック法で事前に求めて，必須項以外の項のみをbit全探索をすることで高速化ができそうです．

が，そもそも10変数に関する簡単化を実際に必要とする機会があるのかはわからないです．

あとがき

bit演算様様です．GithubPagesも便利です．p5jsも便利です．

p5jsのすすめ

JSもHTMLもよくわからないけどwebブラウザで動くヤツ作りたい！Processingなら書ける！という人(僕です)におすすめなのが，p5jsです．
p5jsは，ブラウザで動くProcessingです．言語はJavaライクなものからJSに変わりますが，変数宣言とfunctionとArrayが使えればほとんど変わりません．setup()とかfill()みたいな関数は全く同じです．便利なオンラインエディタもあります．
editor.p5js.org

index.htmlというファイル名に次のコードを突っ込んで，

<!DOCTYPE html>
<html lang="en">
  <head>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.3.1/p5.js"></script>
    <link rel="stylesheet" type="text/css" href="style.css">
    <meta charset="utf-8" />
  </head>
  <body>
    <script src="./script.js"></script>
  </body>
</html>

同じ場所にstyle.cssというファイルも用意しておきます．中身は書かなくて大丈夫です(後から書き足すとき用)．
また，同じ場所にscript.jsというファイルも用意して，そこにp5jsのコードを書いて，index.htmlをChromeとかで開くと動きます．
githubにアップして，Settings/GitHub PagesのCheck it out hereを押してSourceのbranchをmainとかに設定すれば，ユーザー名.github.io/なんちゃらで公開されます．

第32回全国高専プロコン競技部門参戦記と好きなお茶ランキング

これはなに

長野高専から競技部門に「高専の応用呪術IIB」 というチーム名で参加しました．それの参戦記です．

内容は，アルゴリズムの簡単な説明，当日の様子，感想，お茶の順番です．気になるところだけ読んでください．

結果や出題された問題は公式サイトから見ることができます． www.procon.gr.jp

結果

予選(2組目)1位

準決勝(2組目)1位

決勝4位でした．総合では特別賞を頂きました．ありがとうございます．コードが汚いことこの上ないので選ばれないと思っていた．

上位3校に圧倒的に差をつけられて完敗でした．3位入賞はかなり技術力を上げないとまず届きそうにないですね......．

ほぼ1人参戦については，そもそもチーム戦なのに人を集めなかったのが(実際は集まらなかったのですが，主張が足りなかったのかも)悪いのです．

アルゴリズムの説明

本番で使用したプログラムは全て私が作りました．第25回のプログラムを参考にしてあり明らかに独創性がありません．様々な解法のソルバを作ったら良かったのですが技量と時間とやる気が足りませんでした．要精進．

プログラム自体8月中旬から作りはじめ，9月の中旬頃にはほとんど完成し，あとはパラメータをチューニングするだけの状態でした．

画像復元

貪欲に，ある断片画像の周りに一番くっつきそうな断片画像を繋げていきます．

具体的には，

1. 適当な断片画像一つを「確定」させて配置し，その画像の4辺を集合$S$に追加する
2. $S$の各々について，最も親和度が高い断片画像の辺を「候補」として，親和度の値と一緒に集合$E$に追加する．
3. Eのうち最も親和度が高いものを「確定」した断片画像として配置して，追加した断片画像の辺を「候補として」$S$に追加する．2に戻る．

$E$はプライオリティキューで実装しているので追加，検索が高速$\mathrm{O}(\log N)$です．

親和度は辺の各ピクセルのRGB値を並べたベクトル同士のcos類似度で計算しました．cos類似度は，ベクトルの内積の等式に出てくる$\cos \theta$の値です(2つのベクトルのなす角)． また，事前に全ての辺同士の親和度を計算しておき，いい感じにソートしておくことで高速化します．

回転可能という条件が予想以上に厄介で，向きや辺の番号の管理がややこしかったです．結局，向きとか辺を{0,1,2,3}で表して，剰余演算でごにょごにょしました．

GUI上では，次の断片画像の確定，任意の確定断片画像の削除，上端下端などの設定，強制的に任意の断片画像を候補から削除する，といった操作が可能です． ちなみに，サイズの大きいppmファイルの中身を全てchar型の配列に突っ込んでいるので，読み込みが一番時間かかります．

スライドパズル

端がつながっているルールをうまく使う方法が，案外思いつかないんですこれが． だんだん小さな正方形の問題にしていく戦法と迷ったのですが，結局端っこから1列ずつ揃える→3×nのサイズになったら3×(n-1)にしていく戦法になりました．具体的な様子は 第32回高専プロコン「競技部門2日目」#procon32 - YouTube をご覧ください(再生開始場所が埋め込んであります)．

プログラムは至ってシンプルで，断片画像の揃える順番を決めて，一つの移動させる断片画像を決定したらあとはその断片画像を使って一つずつ断片画像を持って正しい場所へ持って行きます．ここで重要なのは移動経路です． 移動される断片画像の経路探索は，最短経路のうちのいくつかをランダムで選びました．選ばれた経路それぞれについて次に書いてある経路探索を行い，その中で評価が高いものを採用すしました． 移動させる断片画像の経路探索はダイクストラ法を使いました．具体的には，各断片画像をノード，交換可能な画像同士にエッジを張りとし，入れ替えたときに正しい位置に近づくか遠ざかるかでコストをつけます．ここのコストのチューニングが難しい．

盤面の評価は単純に正しい場所へのマンハッタン距離の総和になっています．本当は2乗した値のほうがいいことに割と最近気づいたんですが，なんかうまくできませんでした．

また，端っこの処理のプログラムが不十分で今でもたまに止まります．その場合は手動で揃えています．

結構効果的だったのは乱数要素を入れたことです．もちろんコストが上振れ(コストは低いほうがいい)することがありますが，下振れもします．1回回答を出力するまでに1分もかからないので，何度も探索することで，下振れスコアが出ることを願う作戦です．実は，この下振れがなければ負けてました．

この一連のプログラムはどれもSiv3dで作成しました．

余談ですがパンフレット見たときにGUIの画像が掲載されている高専が結構あって驚きました．以下GUIのスクショです．

内輪向けの話になるのですが，Siv3dで，配布されたppmファイルを読み込もうとするとエラーになってハマりました．自前で用意したppmファイルは正常に読み込むのになんでかなとバイナリを比較すると，0A(改行)の次の0D(復帰)の有無の違いがあり，0Dを削除したら読み込めるようになりました．0Dは改行として扱われることがあるらしくておそらくそれが原因な気がしますが，真相は不明．僕が使用したppmビュアーでは正常に表示できていたので原因を突き止めるのに1e9+7年はかかりました．

追記(10/11) 結構前にissueが出されていてv0.6で修正されたらしいです． PPM 画像、一部の形式で encode/decode に失敗 · Issue #591 · Siv3D/OpenSiv3D · GitHub

その他

課題部門のメンバー(@shun_shobon)が問題自動生成ツールを作ってくれました．公式で配布される問題が少ないのでめっちゃ役立ちました．ありがとう．

本番の様子

緊張で吐きそうでした．お腹痛い．緊張に弱いのどうにかならんの．

1日目朝

テストを回してたところ早速バグが発見されました．死にものぐるいで修正しますが一部は修正しきれず．

1日目1回戦

模擬試合で早速ビビりました． なんだこれは．

復元後の画像

画像の周囲の背景色同士でくっついてしまいました． しかも，ほぼ水色一色みたいな断片画像もあります． 用意していた修正機能を駆使してなんとか時間内に提出できましたが，16x16でやられたらまずいと思い，後で新機能を追加することになります．

本番の問題は全く問題なくすんなり揃いました．8x8の経路は20秒くらいで求まるので，何度も回すことで乱数ガチャをします．動画を観るとわかりますが1位通過でめちゃくちゃ喜んでます．gif画像にされそう．

1日目夜

新機能を追加します．バグ修正する元気がないのと疲れたので素直に寝ました．

2日目朝

#procon32のハッシュタグのついたツイートを見ると，「完徹ww」とか「50%削減」などのワードが飛び交っています．うっそだろwwwと思いながら自分のプログラムも改善しなきゃと思い，試行錯誤しますが全くスコアが伸びずちょっと絶望してました．一応準決勝の組の中で，1回戦の成績はトップですが，そんな情報はあてにならなくなります．またもやバグが見つかったので，アドホックな修正をしていきます．そういえば朝ごはん食べてねぇ．

2日目準決勝

問題がこちらです．

竿燈祭りだとはわかる

面食らいます．けれどすんなり揃いました．正しく揃っていても間違ってるように見える箇所があり疑心暗鬼になりながらもaccepted 0 0(完全一致)の表示を見て一安心．乱数ガチャをし，1回目のコスト5081から，4477まで下げることができました．1位通過です．

2日目決勝

決勝に来れて満足！4位取れたら嬉しい！の気持ちで臨みました．画像復元に急遽実装した新機能が役立ち，4位を取ることができました．

後で試したら決勝の花火と模擬試合の画像は人の手を加えずに揃いました．画像が復元できないとその先がどうしよもないシステム，本当に怖いです．

本音と感想

正直，もともと競技部門にあまり乗り気ではありませんでした． 理由としては，

• アルゴリコンではなくマラソン系であること
• 1つの問題だけで勝敗が決まってしまうのでたまたま相性が悪い問題が出ると悲しくなること
• 制約が緩いので難しいこと
• まだなんも決まっていないアルゴリズムを書いた予選資料を提出をしなければならないこと

が挙げられます．そんな中，夏休み中になんとなく画像復元プログラムを作りはじめたや否や，そのままコーディングにハマり，数日後に16x16のアジサイが揃ったときの脳汁をエンジンに熱が入り，入賞するぞー！の気持ちになりました．一度書き始めるとノリノリにカタカタするんだけど，書き始めるまでが長い．

マラソンコンテストは積極的に出て，ヒューリスティックなアプローチに慣れていきたいなと思います．たぶん．

最後に，プロコンの関係者の皆様，観戦に来てくださった先生，応援してくださった方々，本当にありがとうございました．

好きなお茶ランキング

ところで，お茶は好きですか．私は好きです．Japanese like tea. year.

注：価格はスーパーなどで売ってるペットボトルのお茶のことを指しています．

1位：烏龍茶

この世で一番うまいお茶です．酔ったとき，気持ち悪いときに飲むと非常にすっきりします．あとだいたい価格がお手頃です．

2位：緑茶の濃い茶系

体脂肪云々はよくわかりませんが，こちらも気分が悪いときに飲むとすっきりします．こちらは割高なことが多い気がします．

3位：ほうじ茶

烏龍茶と風味の傾向が似ていて(当社比)しばしば比較されますが、私は烏龍茶派です．

4位：抹茶入り玄米茶

刺身のお供にしたいお茶第1位．某回転寿司のお茶の味と非常に近いです．

総括

一般に，お茶は美味しいです．

まとめ

プロコンのお供は烏龍茶一択ですね．皆さんのおすすめのお茶はなんですか．

自分なりに楕円曲線暗号についてまとめてみた

はじめに

先日，高専セキュコンに出場したのですが楕円曲線暗号に関する問題が解けなかったので色々調べました．それをまとめたもとがこちらになります．

楕円曲線とは

楕円曲線とは，$y^2=x^3+ax+b$で表される式です．
$y^2=(なんちゃら)$という形をしているのでx軸に関して対称であることがわかります．
具体的にどんな形をしているのかを見ていきます．
GeoGebraという関数グラフをかける神アプリを使って書いてみました．

https://www.geogebra.org/graphing?lang=ja

$y^2=x^3+2x+3$

$y^2=x^3-5x+5$

$y^2=x^3-5x+3$

離れ小島ができることもであるようです．

楕円曲線暗号の概要

楕円曲線$y^2 \equiv x^3+ax+b \pmod {p}$で$a,b,p$の値は事前に決めておきます．また，楕円曲線上の点Gも決めておきます．これらは全て公開されています．
ここで，秘密鍵$n$を使って$nG$を計算します．この$nG$が公開鍵です．$nG$の結果だけを見て$n$を計算するのは離散対数問題と言われる，解くのに膨大な時間を要するものになります．
「膨大な時間」というのはあまりにも長いので解読不可能と言われます．

これだけ見ると$nG$って何やねん，$(nx,ny)$と等しいのか？，とか思いますがそうではありません．あと，modとかいう異物が入っています．順を追って説明していきます．

加法

異なる点の加法

楕円曲線の世界での加法は$3+5=8$のようなものとは全く別のものです．
楕円曲線上の2点$P$,$Q$の足し算の結果は，$P$と$Q$を通る直線と楕円曲線の交点を$x$軸に関して対称移動させた点$R$です．
想像がしづらいので具体的な例をみてみます．

$y^2=x^3-2x+4，P(-2,0)，Q(0,-2)$とすると，PQを通る直線は$y=-x-2$と表されます．直線と楕円曲線の交点$S$は$(3,-5)$になります．$S$を$x$軸に関して対称移動させると点$R(3,5)$が得られます．よって，$P(-2,0)+Q(0,-2)=R(3,5)$です．

楕円曲線，と聞いてなんだか小難しそうですが図で見ると案外とっつきやすい印象です．
この例はたまたま座標が整数になっているだけで，実際は有理数になります．

問題はこれをどうプログラムに落とすか，です．一般化しなければなりません．
$y^2=x^3+ax+b，P(x_p,y_p)，Q(x_q,y_q)$のときの$P+Q=R$である$R(x_r,-y_r)$を求めます．
方針としては，PとQと通る直線の式と楕円曲線の方程式を連立して解けば座標$R(x_r,y_r)$が求まりそうです．

まず，PとQと通る直線の方程式は，傾きを

$$
\phi = \frac{y_q- y _ p } { x _ q - x _ p }
$$
とおくと

$$
y=\phi (x-x_p) + y_p，
y=\phi x - \phi x_p + y_p
$$
と表されます．わかりやすく$y=ax+b$の形にするために，
$$
\psi = - \phi x_p + y_p
$$
$$
= - \frac{ ( y _ q - y _ p ) x _ p } { x _ q - x _ p } + \frac { ( x _ q - x _ p ) y _ p } { x _ q - x _ p } = \frac{ x _ p y _ p - x _ q y _ q} { x _ q - x _ p }
$$
として
$$
y=\phi x + \psi
$$
と表します．この式を$y^2=x^3+ax+b$に代入すると，
$$
(\phi x + \psi)^2 = x^3+ax+b
$$
整理して，
$$
x^3- \phi^2 x^2 +ax- 2 \phi \psi x - \psi ^2 +b = 0
$$
となります．この三次方程式の解は$x_p,x_q,x_r$の3つです．なぜなら，$y^2=x^3+ax+b$と$y=\phi x + \psi$の交点は3つあり，その点は$P,Q,R$の3つであるからです．三次方程式の$x^3$の係数は1であるので，
$$
(x-x _ p ) ( x - x _ q ) ( x - x _ r )=0
$$
という式を変形すると上の三次方程式になることがわかります．よって，展開をして係数を比較すると
$$
\phi^2 = x _ p + x _ q + x _ r
$$
が得られます．よって，
$$
x _ r = \phi^2 - x _ p - x _ q
$$
そして，これを$y=\phi x + \psi$に代入し，
$$
y _ r = \phi x _ r + \psi
$$
と求まります．加法の一般化終了です．お疲れ様でした．($R$の座標は$(x_r,-y_r)$であることに注意)

同一点の加法(2倍)

楕円曲線上の点$P$について$P+P$の計算の結果は，楕円曲線の接線のうち$P$を通る直線と楕円曲線の交点をx軸に関して対称移動させた点$R$です．
接線の傾きを求めるには微分を使います．
$y^2=x^3+ax+b$の両辺を$x$で微分すると，
$$
2y \frac{dy}{dx} = 3x^2 + a
$$
よって
$$
\frac{dy}{dx} = \frac{3x^2 + a}{2y}
$$
つまり，$(x_p,y_p)$の接線の傾きは$x$と$y$に代入して，
$$
\phi = \frac{3 x _ p ^2 + a}{2 y _ p }
$$
異なる二点の加法のときと同様に，
$$
\psi = - \phi x_p + y_p
$$
$$
= - \frac{(3 x _ p ^2 + a) x_p }{2 y _ p } + \frac{2 y _ p ^ 2 }{ 2 y _ p } = \frac{- 3 x _ p ^3 - a x_p + 2 y _ p ^ 2 }{2 y _ p }
$$
あとは異なる二点の加法のときと同様です．
$x _ r = \phi^2 - 2 x _ p $と$y _ r = \phi x _ r + \psi$と求まります．($R$の座標は$(x_r,-y_r)$であることに注意)
これは$P+P$の結果ですが，$P+P=2P$とも表されます．
スカラー倍は，$3P=2P+P，4P=3P+P$というように求めていくことができます．
$P$のスカラー倍を計算する方法は早い方法がありますが，これについては後述します．繰り返し二乗法と呼ばれる方法になります．

有限体$\mathbb{F}_p$上の楕円曲線

なんか難しそうな記号がでてきました．これは$ \bmod p$についての話です．
有限個の要素からなる体(たい)を有限体といいます．体というのは四則演算ができる数の集合のことです．
$\mathbb{F}$は有限体を表す記号で，足についてる$p$は位数です．位数というのは体の要素の数です．
つまり，有限体$\mathbb{F}_p$というのはp個の要素のある四則演算ができる集合のことです．
(厳密には違います)(ここの詳しい話は僕自身よくわかっていません)．

例えば有理数は無限にありますがそれらをコンピュータで表そうとすると，コンピュータのメモリは有限であるので無限通りの数の表し方を用意することは不可能です．
しかし，それらは$ \bmod p$の演算を通すことで$0$以上$p$未満の整数のいずれかになります．有限通りの数の表し方は用意できるのでそれらの数を扱うことができます．

$ \bmod p$とは

さっきから$ \bmod p$という表記が登場していますが，これについて説明します．
$ \bmod p$がついている式を合同式と呼びます．$p$は自然数です．合同式についての説明を詳しくすると長くなりすぎてしまうので，簡単な説明だけして，性質の証明などは省略します．

整数に関しては割ったあまりという認識で良いです．例えば，
$$
7 \equiv 1 \pmod 3
$$
という式は，$7$を$3$で割ったあまりが$1$であることを表しています．別に，右辺は$3$で割ったあまりが$1$になる数が入っていればなんでもいいです．今回は$0$以上$p$未満の整数にすることが目的であるので右辺はそれに則ります．
$$
(-4) \equiv 2 \pmod 3
$$
マイナスでも定義ができます．$-4$を$3$で割った余りは$4 = 3 \times ( - 2 )+2 $より$2$と求めることができます．
次は分数(有理数)の場合です．
$$
\frac{1}{2} \equiv ? \pmod 3
$$
$\frac{1}{2}$は，$2$をかけると$1$になる数であるので
$$
2 \times \frac{1}{2} \equiv 1 \pmod 3
$$
が成り立ちます．この式を成り立たせる$ \frac{1}{2} $の代わりになる数を探すと$2$が見つかります．
$$
2 \times 2 \equiv 1 \pmod 3
$$
よって
$$
\frac{1}{2} \equiv 2 \pmod 3
$$
です．ちなみに$ \frac{1}{2} $は$2$をかけると$1$になるという意味で，$2^{-1}$と表すことがあります．行列でいう逆行列のように，(たまたま等しくなっているが)$ \frac{1}{2} $という意味はなく$2$の逆元という意味があります．逆元は$p$の値によって変わります．

実際に計算をしてみる

では，実際に楕円曲線上で計算してみます．
$y^2 \equiv x^3+x+6 \pmod{11}$の例で考えます．
$P(2,7)$は楕円曲線上の点です．これを2倍することを考えます．
2倍は同一点の足し算になるので，
$$
\phi = \frac{3 \times 2 ^2 +1 }{2 \times 7 } = \frac{13 }{14 }
$$
$$
\psi = \frac{- 3 \times 2 ^3 -1 \times 2 + 2 \times 7 ^ 2 }{2 \times 7 } =\frac{36}{7}
$$
有限体$\mathbb{F}_{11}$上の点にするため(0以上11未満の整数にするため)に$ \pmod{ 11}$で処理します．
$$
\frac{13 }{14 } \equiv 13 \times 14^{-1} \equiv 13 \times 4 \equiv 8 \pmod {11}
$$
$$
\frac{36}{7 } \equiv 36 \times 7^{-1} \equiv 36 \times 8 \equiv 2 \pmod {11}
$$
よって，
$$
x \equiv 8^8 - 2\times 2 \equiv 5 \pmod {11}
$$
$$
y \equiv -8 \times 5 - 2 \equiv 2 \pmod {11}
$$
以上の計算より$2P=(5,2)$だと求めることができました．
途中にでてきた逆元の求め方ですが，プログラムだと拡張ユークリッドの互除法やフェルマーの小定理を用いると高速に求めることができます．また，Python3であれば，

pow(7,-1,11)

と書くだけで，$\pmod {11}$の$7^{-1}$の値を取得することができます．この関数が標準で存在するのは驚きです．

スカラー倍を高速に計算する

$nG$から$n$を求めるのを難しくするにはnは十分に大きな数でなければなりません．しかし，$2G=G+G,3G=G+2G$...というナイーブな方法で計算していくと$O(n)$の時間がかかってしまいます．これだと，$nG$から$n$を求めようとしたときに全探索が$O(n)$の時間で終わってしまうので暗号化としての意味がありません．そこで，高速に$nG$を計算する方法を示します．
繰り返し二乗法と呼ばれる方法です．

わかりやすいようにまずは整数で考えます．例えば$13^{16} \pmod {10007}$を計算したいとします．愚直に計算すると，
$13 \times 13\equiv 169，169 \times 13 \equiv 2197， 2197 \times 13 \equiv 8547$...という具合に掛け算を15回することになります．
しかし，$(13^2)^2=13^4$であることを利用すると，
$13^2 \equiv 169，13^4= (13^2)^2 \equiv 8547，13^8=(13^4)^2 \equiv 109$...という具合に掛け算を4回行うだけで$13^{16} \pmod {10007}$を求めることができます．
そんなのたまたま指数が2の冪数だったからじゃないの，と思われるかもしれませんが，2の冪数でなくても大丈夫です．
例えば，$13^{13} \pmod {10007}$であったら$13^{12}=13^1 \times 13^4 \times 13^8$と変形すれば，先ほどの計算過程に出てきた数だけの式になります．
これは指数の数字を二進数にしたときに各位が1か0かで掛け算をするかしないかを決めるとうまくいきます．

楕円曲線の場合も同様に，$4G=2G+2G$，$8G=4G+4G$と計算できるので，例えば46Gを計算したいときは，$46$を二進数に直すと$101110_{(2)}$であることより，
$32G+8G+4G+2G$を計算すれば良いです．これで計算量は$0(log(n))$になりました．

あとがき，余談

楕円曲線暗号のしくみを整頓することができてよかったです．これでタイトルがsimpleECCみたいなCTFの問題は解けるようになったはずです．正直理解するのにかなりの時間を要したので，攻撃方法を学ぶのはまた今度にします．RSA暗号に比べてネット上の資料が少ないのも苦労した原因の一つだと思います．特に楕円曲線の加法の計算を実装したソースコードは数個しか見つかりませんでした(しかも言語がバラバラ)．Pythonに慣れていないのでソースコードを書きませんでしたが，今後載っけられたらいいなと思ってます．
(2021/2/23追記)SageMathというものを使うと楕円曲線や整式のライブラリが使えるので，普通はこちらを使用するようです．

(2021/10/12追記)
一応SageMathで$y^2 \equiv x^3+x+6 \pmod{11}$で$P(2,7)$の$2P$を求める方法を載せておきます

E=EllipticCurve(GF(p),[a,b])

で$E$が$y^2 \equiv x^3+ax+b \pmod{p}$として定義されます．

P=E([x,y])

で$E$上の$(x,y)$が点$P$として定義されます．
よって

sage: E = EllipticCurve(GF(11),[1,6])
sage: P=E([2,7])
sage: 2*P

と実行することで

(5 : 2 : 1)

と$(5,2)$が求めることができました．

水色になりました【色変記事】

はじめに

初参加から13ヶ月，48回目に参加したARC109で水色コーダーになりました．

めちゃくちゃ嬉しいです．

この記事は自分語りと自己満足で成り立っています．お役立ち情報は......高確率で，ないです．

自己紹介

とある高専の情報科二年生です．

数学が好きで得意な方かと思っていましたが，AtCoderをやっていると，どうもそんなことは井の中の蛙でしかないことがよくわかります．

学校でアルゴリズムはまだ学んでいないので，情報科であることは実力にあまり関係がないです．

このくらい解いたよ

水色になるまで48回もコンテストに出たわけですが，他の方の色変記事をみるとだいぶ回数が多く感じます．

少し複雑な気持ちです．

いや，いくら時間がかかっても水色は水色だ，喜べ！！

思い出話

思い出とともにどんなことを学んだかを紹介します．

初めた

部活の先輩にAtCoderってのがあるよーって教えてもらったのがきっかけです．

自分のプログラミング能力がどのくらいあるのか純粋に知りたかったので参加してみたいなと思いました．

ある日突然AtCoderの存在を思い出し，ABC144に滑り込みをして1完しました．パフォーマンスは16でした．

終了直後にBは解けたので，C問題を解くのを目標に過去問を漁りはじめました．

この頃はよく愚直な実装をしてTLEを出して唸ってました．

atcoder.jp

この問題のように灰dif(52)でも計算量の見積もりを要求してくることがあります．

全探索するにも，累積和するにも，計算量はついてくるので早めに知っておくべきです．

計算量はC++入門 AtCoder Programming Guide for beginners (APG4b) - AtCoderや，けんちょんさんの記事で学ぶのがおすすめです．

茶色になるまで

その後，3完が安定する頃に茶色になりました．

始めてから3ヶ月半です．

shibaken496さんのAtCoder Beginner Contest 155での成績：3837位
パフォーマンス：559相当
レーティング：389→410 (+21) :)
Highestを更新し、8 級になりました！#AtCoder https://t.co/gZ7Es1FSep

念願の有彩色！やった！
Cはもっとはやく解きたかった

— shibak3333n (@Shibak33333333n) 2020年2月16日

このころやっていたのは過去問埋めとアルゴリズムを学ぶことです．

この頃，じっくり考えないとわからない，というのが普通だということを知りました．

というのも初めた頃は少し考えて「あーこんなん無理だろ」と思ったらすぐに撤退していたし，解ける人はちょっと考えればわかるんだろうなと思っていました．

初心者の頃はすぐ撤退しがちな気がします．

なんにもわからないけどとりあえず手元で実験する，という問題への取り組み方を知りました．

ここで，ABC-Cの傾向について説明します．

ABC-C問題は，

• 複雑な全探索の問題
• アルゴリズムそのまま使うタイプの典型問題
• 数学的，論理的思考力を要求する問題

の三種類が主です．

全探索

まず重要なのは全探索です．

「全探索」と一括りにされていますが，bit全探索や順列列挙などと様々なことが要求されています．

「全探索？for文いくつか使ってぐるぐる回せばいいんでしょ？」と言って全探索の勉強をスキップするのは危険です．僕がそれでした．

また，多くのアルゴリズムは，全探索では時間がかかるので無駄な計算を省くことができないか，という考えで使われているので

「全探索めっちゃ大事！」

です．

よくある全探索の例を挙げます．

• bit全探索
• 順列列挙，組み合わせ列挙
• A+B+C=Nを満たすA,B,Cを求める問題でAとBだけfor文で回してC=N-A-Bとする

全探索の問題の例です．

atcoder.jp

atcoder.jp

atcoder.jp

典型アルゴリズム

最近は典型問題なら有名なアルゴリズムを使うものであっても茶difになる傾向があります．

最近はさらに顕著になったことで茶色のレベルが上がってると思っています．

D - FriendsやD - Water Heaterは有名アルゴリズムほぼそのままなので茶色difとなっています．

よくみるアルゴリズムとしては，

• 貪欲法
• UnionFind
• 累積和
• いもす法

が挙げれらます．

ネットにはいい記事がありますので，そこでアルゴリズムを理解したり類題を解いてみれば身につくと思います．

学んだアルゴリズムがちょうどコンテストで出題されると嬉しいです．

数学的論理的思考力を要求する問題

一番厄介なのがこれです．僕もこれは今でも苦手です．

下に問題の例を挙げます．

atcoder.jp

この問題はただの数学です．これが茶色difとか恐ろしいです．持ち前の数学力で殴れる人が羨ましいです．

atcoder.jp

場合分けなどの$O(1)$問題もよく出ますね．

このような問題に対して，僕は過去問で訓練しまくることでどうしかしました．投げ遣りな説明でごめんなさい．

緑になるまで

緑になるまでも普通に長かったです．このときもガッツポーズをして叫んでました．

緑になりました！！！！
shibaken496さんのAtCoder Beginner Contest 161での成績：2215位
パフォーマンス：1147相当
レーティング：753→802 (+49) :)
Highestを更新し、6 級になりました！#AtCoder https://t.co/oPr9WLmHtR

— shibak3333n (@Shibak33333333n) 2020年4月4日

この頃にはだいたいの基本的なアルゴリズムが身についていました．

ここら辺のレートからを伸ばすのに必要なのは，いわゆる考察ガチャのガチャの中身を増やすことが大事だと感じます．

例えば，「余事象を考える」や「後ろから考える」といった発想です．僕は頭が硬くてもこの発想をいつでも引き出せるように，メモをしました．そして，詰まったらそのメモを見るようにしました．

レート1000停滞期

ABC175からABC180の間にレートは浮き沈みし，結局22しか上がりませんでした．レートがあがらねぇ．

何かを理解する

レートが上がらずに無になってきた頃，ARC106,107で突然二連続水パフォがでました．水パフォはたまに出るのでたまたま得意なセットが来たからかと思いましたが，その後も1367,1148,1452という良いパフォーマンスでレートが1198まで上がりました．

別に激精進したわけではなく，正直よくわからないです(は?)．コンテストに出まくったから説が有力です．

入水

ARC108に，入水間近のレート1198のときに参加しました．

しかしAtCoderと人々は無情で，B問題が解けず，1完400パフォを突き出され僕は撃沈しました．

レートが本質ではないのはわかっていますが，レートは50下がり入水圏内からも離れ絶望です．

このような寸止めを多く経験することでメンタルが鍛えられた気がします．

まあでもやっぱり，レートが下がると辛いです．

その後，3回コンテストにでてようやく水色になりました．

大切なこと

とにかくコンテストに出る

「精進をしていない」とか「レートを下げたくない」といった口実でコンテストに出ないのはもったいないです．

僕がよくいうのは「欲しいのはレートではなく経験」です．コンテストに出るとじっくり考える時間が与えられるので良いです．

じっくり考えれば考えるほど，解答がよく染みます．

AGCは色が灰〜緑の人は早解き勝負になり，とくに茶，緑の人の人には出るのにはリスクが高く，出るのに躊躇しがちでしたが最近はrated1200~になったので安心です．

レートを気にせず参加することができます．

Twitter

一緒に取り組む人がいるのはとても大事です．

他の人から刺激を受けることやモチベーションに繋がります．

AtCoderをやっていれば，AtCoderをやっている人は大抵フォロバしてくれるのでどんどんフォローします．

コンテスト後の余韻はTwitterがあるからこそ浸ることができます．

あと，色が変わっていいねがたくさんくると嬉しいですね(承認欲求の塊)．

周りを気にしすぎない

僕は色変記事にどんなこと書くかを調べるためにいくつかの記事を見ましたが，点が少なくてかくかくしているスカスカなレートのグラフをたくさん見て劣等感を感じました．気にしすぎないようにします．

人は競プロだけじゃないです．

競プロやって良かったこと(2021/2/23追記)

ある種の発想力が得られる，鍛えられる

一見実装が大変そうに見える問題(C - Digital Graffiti)でも，実はループを回すだけで簡単に解けます．自分で思いつかなくても，その発想を覚えていくことはできますので，どんどん発想をためていくことができます．

実装力が身につく

例えば，C - Kaprekar Numberこの問題は数字自体をソート(8128なら，各位の数を小さい順に並べ1288)しますが，この処理は決して簡単ではないです．「数字を文字列にして一文字ずつに分ける」ことや，「数字を小さい順にくっつける」ことは僕が競技プログラミングを始めたときもそうでしたが，それらは長い考察の末に思いつく方法だと思います．しかし，競プロに慣れてくるとこのような発想は自然で，実装もすぐにスラスラできるようになりました．難しいアルゴリズムを実装できることが注目されがちですが，ABCのAB問題あたりの実装が難なくできる点は大きいと思います．

感想

なんだかまとまりのない記事になってしまいました．文章力がないです．

趣味でやっていることですが，こうした努力が客観的に水色という形で評価されて嬉しいです．

AtCoderは楽しいので，続けます．次の目標は青です．今のところ青になれる見込みは全くないですが気長に頑張ります．

高専セキュコン2020に出た(ごく一部のWriteUp)

はじめに

2020年11月14日に開催された高専セキュリティコンテストに同級生自分を含めて3人でチームを組んで出ました．僕はwebやネットワーク方面の知識が皆無なのと競技プログラミングをやっているという理由でprogrammingとcrytpto担当でした．が，楕円曲線暗号の問題は解くことができませんでした(追記:勉強しました(自己顕示欲)自分なりに楕円曲線暗号についてまとめてみた - 競プロやってる高専生)．というか，パズルしかやってない気がするので暗号勉強したい...

writeUp

足し算しよう

1000から10000の整数の和を求める問題です．プログラムを書いて求めます．プログラムを書かなくても，$(1000+10000)\times (10000-1000+1)\div 2$という式で求めることができます．

熱血計算塾

指定されたポートに接続すると，13+58=のような計算問題が出されます．正しい答えを入力すると次の問題，間違えると追い返されます．頑張って計算をしていきますが，解いても解いても終わらないので自動化します．問題には対話型のプログラムのサンプル添付されているので，そのコードを書き換え，実行してたくさん問題を解くとFLAGが手に入ります．解くのに使ったPythonのコードは次の問題を解く際に上書きしてしまいまったのでありません．

15game

問題を見て，「お！これはわかるぞ！」と調子に乗っていたらめちゃくちゃ時間かかりました．

必勝法を考えます．相手に15を言わせたいので，自分の最後に言う数字を14にする必要があります．そのためには，その前のターンで自分が最後に言う数字を10にすれば良いです．なぜなら相手が11から1~3個の数字をいくつ言ったとしてもその次のターンで自分は必ず14を言うことができるからです(相手11→自分12,13,14 or 相手11,12→自分13,14 or 相手11,12,13→自分14)．同様に考察すると，それぞれのターンで最後に言う数字は14,10,6,2にする必要があることがわかり，それにしたがって数字を言うとFirstRoundを勝利することができます

SecondRoundは，言ったら負けになる数字が30になります．さらにFourthRoundでは一度に417個まで数字を言ってよく，1993を言うと負けのルールになります．先ほどの考察を一般化すると，一度に $N$ 個まで数字を言うことが可能で $ M $ を言うと負けのルールの場合，はじめに1から $ ( M - 1 ) を ( N + 1 ) で割った余り$ の数字を言い，その後は $ (N+1)-(相手の言った数字の数) $ の個数だけ数字を言えば良いことになります．これでFourthRoundまでは勝ち進むことができます．

FinalRoundは一度に5555個まで数字を言ってよく999999を言ったら負けのルールになります．少なくとも100ターン程度かかることがわかるので，人力は厳しいです．そこで，対話型のプログラムを作成します．実際に作成した下記のコードはFinalRound中(はじめの1回は人力)に-1を入力することでオートモードに切り替わります(FourthRoundまでは人力でやる必要があります)．

めちゃくちゃ汚いコードです．pythonに慣れたい．

import socket
import decimal
import re
import time

def netcat(hostname, port):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    at=0
    s.connect((hostname, port))
    nop = re.compile("ok",re.IGNORECASE)
    while 1:
        data = s.recv(1024)
        if data == "":
            continue

        if data.decode('utf-8').strip() == "Let's play with 15game :)":
            s.sendall(bytes("", "utf-8"))
        elif nop.search(data.decode('utf-8')):
            print (data.decode('utf-8'))
            pass
        else:
            #data 変数に、サーバから送られてくる問題文が含まれる
            print (data.decode('utf-8'))
            try:
                answer=0
                q=data.decode('utf-8')
                if at==0:
                    answer=input()#-1を入力するとオートモードになる
                    print(answer)
                    if answer=="-1":
                        print("auto")
                        at=1
                    else :
                        s.sendall(bytes(str(answer) + "","utf-8"))
                if at==1:
                    a=q.find(":",11)
                    b=q.find("\n")
                    l=int(q[11:a])
                    r=int(q[a+1:b-1])
                    nr=r+5556-(r-l+1)
                    answer=str(r+1)+":"+str(nr)
                    print(answer)
                    s.sendall(bytes(str(answer) + "","utf-8"))
            except:
                print ("flag?\n")
                break
    shutdown(s)

def shutdown(s):
    print ("Connection closed.")
    s.shutdown(socket.SHUT_WR)
    s.close()

if __name__ == '__main__':
    netcat("52.175.155.247", 10001)

全部自動化できたらかっこよかった

※もう一つのProgrammingの問題は解けませんでした(チームの人が解きました)

感想

netcatについてのサンプルが添付されていてとても助かりました，なかったらだいぶしんどかったと思います．純粋に6時間楽しかったので来年も参加したいです．