CPCTF 2026 作問者writeup (Nzt3編)

みなさまこんにちは。Nzt3です。

この記事では 2026-04-17 20:00(JST) から 2026-04-19 20:00(JST) まで行われたイベントである CPCTF 2026 の問題のうち、Nzt3が制作に関わった問題の解説・出題意図を記録します。

PPC(競技プログラミング)分野の問題はyukicoder上で公開されているのでこの記事を読む前に挑戦してみてください！

yukicoder: CPCTF 2026: PPC

私が関わった問題

Crypto

Lv.2 Very Exciting
Lv.3 Janken Master
LV.5 mod N Janken

PPC

Lv.3 Sum of Prod of Root (謝罪)
Lv.4 OR Mapping (強化)
Lv.5 RPS Eliminations

[Crypto] Lv.2 Very Exciting

問題概要

ワクワクする乱数をあなたにも使わせてあげます。

↑この問題文はただのフレーバーテキストなので無視してください。

ncコマンドでサーバーにTCP接続してサーバーで実行されるPythonプログラムとやり取りをする問題です。

配布ファイル

server.py


#!/usr/local/bin/python3
from os import getenv, urandom


class BoringRandom:
    C0 = 0x6A09E667F3BCC908
    C1 = 0xBB67AE8584CAA73B
    C2 = 0x3C6EF372FE94F82B

    SBOX = [
        0x63, 0x7c, 0x77, 0x7b, 0xf2, 0x6b, 0x6f, 0xc5, 0x30, 0x01, 0x67, 0x2b, 0xfe, 0xd7, 0xab, 0x76,
        0xca, 0x82, 0xc9, 0x7d, 0xfa, 0x59, 0x47, 0xf0, 0xad, 0xd4, 0xa2, 0xaf, 0x9c, 0xa4, 0x72, 0xc0,
        0xb7, 0xfd, 0x93, 0x26, 0x36, 0x3f, 0xf7, 0xcc, 0x34, 0xa5, 0xe5, 0xf1, 0x71, 0xd8, 0x31, 0x15,
        0x04, 0xc7, 0x23, 0xc3, 0x18, 0x96, 0x05, 0x9a, 0x07, 0x12, 0x80, 0xe2, 0xeb, 0x27, 0xb2, 0x75,
        0x09, 0x83, 0x2c, 0x1a, 0x1b, 0x6e, 0x5a, 0xa0, 0x52, 0x3b, 0xd6, 0xb3, 0x29, 0xe3, 0x2f, 0x84,
        0x53, 0xd1, 0x00, 0xed, 0x20, 0xfc, 0xb1, 0x5b, 0x6a, 0xcb, 0xbe, 0x39, 0x4a, 0x4c, 0x58, 0xcf,
        0xd0, 0xef, 0xaa, 0xfb, 0x43, 0x4d, 0x33, 0x85, 0x45, 0xf9, 0x02, 0x7f, 0x50, 0x3c, 0x9f, 0xa8,
        0x51, 0xa3, 0x40, 0x8f, 0x92, 0x9d, 0x38, 0xf5, 0xbc, 0xb6, 0xda, 0x21, 0x10, 0xff, 0xf3, 0xd2,
        0xcd, 0x0c, 0x13, 0xec, 0x5f, 0x97, 0x44, 0x17, 0xc4, 0xa7, 0x7e, 0x3d, 0x64, 0x5d, 0x19, 0x73,
        0x60, 0x81, 0x4f, 0xdc, 0x22, 0x2a, 0x90, 0x88, 0x46, 0xee, 0xb8, 0x14, 0xde, 0x5e, 0x0b, 0xdb,
        0xe0, 0x32, 0x3a, 0x0a, 0x49, 0x06, 0x24, 0x5c, 0xc2, 0xd3, 0xac, 0x62, 0x91, 0x95, 0xe4, 0x79,
        0xe7, 0xc8, 0x37, 0x6d, 0x8d, 0xd5, 0x4e, 0xa9, 0x6c, 0x56, 0xf4, 0xea, 0x65, 0x7a, 0xae, 0x08,
        0xba, 0x78, 0x25, 0x2e, 0x1c, 0xa6, 0xb4, 0xc6, 0xe8, 0xdd, 0x74, 0x1f, 0x4b, 0xbd, 0x8b, 0x8a,
        0x70, 0x3e, 0xb5, 0x66, 0x48, 0x03, 0xf6, 0x0e, 0x61, 0x35, 0x57, 0xb9, 0x86, 0xc1, 0x1d, 0x9e,
        0xe1, 0xf8, 0x98, 0x11, 0x69, 0xd9, 0x8e, 0x94, 0x9b, 0x1e, 0x87, 0xe9, 0xce, 0x55, 0x28, 0xdf,
        0x8c, 0xa1, 0x89, 0x0d, 0xbf, 0xe6, 0x42, 0x68, 0x41, 0x99, 0x2d, 0x0f, 0xb0, 0x54, 0xbb, 0x16
    ]

    def __init__(self, key: bytes, iv: bytes):
        assert len(key) == 16 and len(iv) == 16

        K0 = int.from_bytes(key[0:8], byteorder='big')
        K1 = int.from_bytes(key[8:16], byteorder='big')
        I0 = int.from_bytes(iv[0:8], byteorder='big')
        I1 = int.from_bytes(iv[8:16], byteorder='big')

        self.a = [0] * 3
        self.b = [0] * 16

        self.a[0] = K0
        self.a[1] = K1
        self.a[2] = self._rotl(K0, 7) ^ self._rotr(K1, 7) ^ self.C0

        for i in range(16):
            self._update_rho_only()
            self.b[15 - i] = self.a[0]

        self.a[0] ^= I0
        self.a[1] ^= I1
        self.a[2] ^= self._rotl(I0, 7) ^ self._rotr(I1, 7) ^ self.C0

        for i in range(16):
            self._update_rho_only()

        for i in range(16):
            self._update()

    def nextrand(self) -> bytes:
        out = self.a[2]
        self._update()
        return out.to_bytes(8)

    def _update(self):
        a_0_next = self.a[1]
        a_1_next = self.a[2] ^ self._F(self.a[1], self.b[4]) ^ self.C1
        a_2_next = self.a[0] ^ self._F(
            self.a[1], self._rotl(self.b[10], 17)) ^ self.C2

        b_next = [0] * 16
        for j in range(16):
            if j not in (0, 4, 10):
                b_next[j] = self.b[j - 1]
        b_next[0] = self.b[15] ^ self.a[0]
        b_next[4] = self.b[3] ^ self.b[7]
        b_next[10] = self.b[9] ^ self._rotl(self.b[13], 32)

        self.a = [a_0_next, a_1_next, a_2_next]
        self.b = b_next

    def _update_rho_only(self):
        a_0_next = self.a[1]
        a_1_next = self.a[2] ^ self._F(self.a[1], 0) ^ self.C1
        a_2_next = self.a[0] ^ self._F(self.a[1], 0) ^ self.C2
        self.a = [a_0_next, a_1_next, a_2_next]

    def _F(self, X: int, B: int) -> int:
        O = X ^ B

        O_bytes = [(O >> ((7 - i) * 8)) & 0xFF for i in range(8)]

        P = [self.SBOX[b] for b in O_bytes]

        Q = [0] * 8
        for j in (0, 4):
            Q[j+0] = self._mul2(P[j+0]) ^ self._mul3(P[j+1]) ^ P[j+2] ^ P[j+3]
            Q[j+1] = P[j+0] ^ self._mul2(P[j+1]) ^ self._mul3(P[j+2]) ^ P[j+3]
            Q[j+2] = P[j+0] ^ P[j+1] ^ self._mul2(P[j+2]) ^ self._mul3(P[j+3])
            Q[j+3] = self._mul3(P[j+0]) ^ P[j+1] ^ P[j+2] ^ self._mul2(P[j+3])

        Y_bytes = [Q[4], Q[5], Q[2], Q[3], Q[0], Q[1], Q[6], Q[7]]

        Y = 0
        for b in Y_bytes:
            Y = (Y << 8) | b
        return Y

    def _rotl(self, x: int, n: int) -> int:
        return ((x << n) | (x >> (64 - n))) & 0xFFFFFFFFFFFFFFFF

    def _rotr(self, x: int, n: int) -> int:
        return ((x >> n) | (x << (64 - n))) & 0xFFFFFFFFFFFFFFFF

    def _mul2(self, x: int) -> int:
        return (x << 1) ^ 0x11b if (x & 0x80) else (x << 1)

    def _mul3(self, x: int) -> int:
        return self._mul2(x) ^ x


# 平文の長さに合わせてキーストリームを自動生成するヘルパー関数
def stream_excite(pksg, data: bytes) -> bytes:
    keystream = b""

    while len(keystream) < len(data):
        keystream += pksg.nextrand()

    return bytes([a ^ b for a, b in zip(data, keystream)])


def main():
    secret_key = urandom(16)
    exciting_iv = urandom(16)
    secret_flag_plaintext = getenv("FLAG", "FLAG{DUMMY}").encode()

    myPKSG = BoringRandom(secret_key, exciting_iv)

    exciting_flag = stream_excite(myPKSG, secret_flag_plaintext)
    print(f"Here is the exciting_iv I used!: {exciting_iv.hex()}")
    print(
        f"And behold! My masterpiece, the incredibly cool exciting_flag!!\n => {exciting_flag.hex()}\n")

    print("Now it's your turn, folks at home! Let's make your 'favorite' thing EXCITING!")

    favorite_input = input("Enter your boring 'favorite' (Hex): ")
    your_favorite = bytes.fromhex(favorite_input)
    if your_favorite == exciting_flag:
        print("Whoa, whoa, whoa! That's MY exciting_flag! Bring your own boring stuff!")
        exit(0)

    very_exciting_input = input("Enter your own 'very_exciting' IV (Hex): ")
    very_exciting_iv = bytes.fromhex(very_exciting_input)
    if len(very_exciting_iv) != 16:
        print("That's not a very exciting IV...")
        exit(0)
    yourPKSG = BoringRandom(secret_key, very_exciting_iv)

    enc_your_favorite = stream_excite(yourPKSG, your_favorite)
    print(
        f"Your favorite just got completely EXCITED!!\n => {enc_your_favorite.hex()}")

    tea_list = ["Black tea", "Green tea",
                "Oolong tea", "White tea", "Matcha", "Tisane"]
    destiny_tea_index = int.from_bytes(yourPKSG.nextrand()) % 6
    print(
        f"Time to cool down. Today's Exciting Tea Omikuji says... [{tea_list[destiny_tea_index]}]! Enjoy!")


if __name__ == '__main__':
    try:
        main()
    except:
        print("\nOops, looks like we got too excited and short-circuited. Bye!")

BoringRandom という乱数生成器クラスを使用し、秘匿された16bytesのsecret_keyと公開された16bytesのexciting_ivを用いて作ったkeysteamとxorすることでflagを暗号化しています。

その後、secret_key(そのまま)とユーザーの入力したvery_exciting_ivを使ってユーザーが自由に入力できる very_exciting_input を同様に暗号化しています。

やり取りを利用して暗号化されたexciting_flagを頑張って復号してflagを入手したいですね。

解法

very_exciting_ivとしてexciting_ivと同じものを入力すると全く同じkeystreamが生成されます。
xorの性質より、暗号文であるenc_your_favoriteと暗号化前の平文であるyour_favoriteがわかるとkeystreamが特定できます。your_favoriteとして長めの列を選べばkeystreamもその長さだけ特定できます。
十分な長さのkeystreamを特定できたら、exciting_flagとxorすることでsecret_flag_plaintextを特定できます。

ivが選択できてしまうため、flagの暗号化に使ったkeystreamと同じものを生成でき、特定できます。

一般に、疑似乱数生成器は (内部状態, 内部状態を更新する関数, 内部状態を加工して乱数を生成する関数) の3つからなります。
全ての関数は決定的でありどこにもランダム要素はありません。内部状態さえわかればその先の内部状態の更新も乱数の生成も決定的であるため、同じ乱数が生成されます。

今回の乱数生成器では、内部状態として64bit整数19個を、内部状態を更新する関数として_updateを、内部状態から乱数を生成する関数として内部状態の64bit整数を持ってくるa[2]を使用しています。
疑似乱数では内部状態が特定できればその後に生成される乱数が全てわかります。暗号に用いられる乱数では乱数の出力から内部状態が特定できないように工夫がされていますが、今回のように内部状態を設定する部分を直に触れると色々と悪いことをできてしまいますね。

BoringRandomはCRYPTREC 推奨候補暗号^[1]である MUGI を用いています。現時点ではこの暗号自体に深刻な問題は見つかっていません。
退屈でワクワクしない地味なMUGI……？ Today's Exciting Tea Omikujiってなんだ？O,NI,CHA ……？

感想

擬似乱数生成器は初期情報であるseed、今回であれば鍵(key)と初期化ベクトル(IV)から数列を作る装置なので初期状態が同一なら生成される数列も同一になります。乱数といっても機械で作る疑似乱数には限界はあるし、乱数生成の操作も実装するだけなら意外に単純なんですよね。

Lv.2として攻撃に使うデータを自分で用意してもらう形式の問題にしたかったので、IVと平文を選択してもらう形にしました。暗号化後のflagをそのままもう一度暗号化して平文に戻せたら綺麗ですが、何かしら手元でxorをやって欲しいので弾きました。

こんな誤答がありました。教育的なflagを考えていてえらいですね。

CPCTF{x0r_5tr34m_c1ph3r_15_v3ry_3xc1t1ng!}
- XOR stream cipher is very exciting! わかる。わかります。逆元が自身であるおかげで暗号化/復号の処理が同じになって実装がシンプルになる実用性重視の演算に見えるのに、OTPみたいな最強の安全性にも出てくるの面白すぎる。二元体が嬉しすぎる。
CPCTF{D0_n0t_r3us3_th3_IV_in_str34m_c1ph3rs!!}
- 教育的だからflagこれにした方がよかったかも。leetでeが3になるの非自明。

[Crypto] Lv.3 Janken Master

問題概要

みんなでじゃんけん！

この問題文もフレーバーテキストなので無視して大丈夫です。
ncコマンドでサーバーにTCP接続してサーバーで実行されるPythonプログラムとやり取りをする問題です。
配布ファイル

server.py

#!/usr/local/bin/python3
import os


class Xoroshiro128Plus:
    MASK = 0xFFFFFFFFFFFFFFFF

    def __init__(self, seed):

        self.s = [seed >> 64 & self.MASK, seed & self.MASK]

    def rotl(self, x, k):
        return ((x << k) | (x >> (64 - k))) & self.MASK

    def next(self):
        s0 = self.s[0]
        s1 = self.s[1]

        result = (self.rotl((s0 + s1) & self.MASK, 17) + s0) & self.MASK
        s1 ^= s0
        self.s[0] = (self.rotl(s0, 49) ^ s1 ^ (
            (s1 << 21) & self.MASK)) & self.MASK
        self.s[1] = self.rotl(s1, 28)

        return result


def main():
    FLAG = os.environ.get("FLAG", "FLAG{DUMMY}")
    NPC_COUNT = 99

    print("=====================================================")
    print(f" Welcome to the {NPC_COUNT + 1}-Player Rock-Paper-Scissors! ")
    print(" Can you become the sole winner against all NPCs?")
    print("=====================================================\n")

    try:
        seed_input = input("Enter your lucky number (seed): ")
        seed = int(seed_input)
    except ValueError:
        print("Invalid input. Please enter an integer.")
        return

    seed ^= 0x1234567890abcdef1234567890abcdef
    rng = Xoroshiro128Plus(seed)

    print("\nSelect your hand:")
    print("0: Rock (グー)")
    print("1: Scissors (チョキ)")
    print("2: Paper (パー)")

    try:
        player_hand = int(input("Your hand (0-2): "))
        if player_hand not in [0, 1, 2]:
            print("Invalid hand.")
            return
    except ValueError:
        print("Invalid input.")
        return

    npc_hands = []
    for _ in range(NPC_COUNT):
        npc_hands.append(rng.next() % 3)

    rock_count = npc_hands.count(0)
    scissors_count = npc_hands.count(1)
    paper_count = npc_hands.count(2)

    print("\n--- Result ---")
    print(f"Your hand: {player_hand}")
    print(
        f"NPC hands: Rock={rock_count}, Scissors={scissors_count}, Paper={paper_count}")

    # 勝敗判定
    hands_in_field = set(npc_hands)
    hands_in_field.add(player_hand)

    if len(hands_in_field) == 3:
        print("\nDraw! All three hands appeared in the field.")
    elif len(hands_in_field) == 1:
        print("\nDraw! Everyone played the same hand.")
    else:
        if (player_hand == 0 and 1 in hands_in_field) or \
           (player_hand == 1 and 2 in hands_in_field) or \
           (player_hand == 2 and 0 in hands_in_field):
            winner_count = 1 + npc_hands.count(player_hand)
            if winner_count == 1:
                print("\nCongratulations! You are the SOLE winner!")
                print(f"Here is your reward: {FLAG}")
            else:
                print(
                    f"\nYou won! But there are {winner_count} winners in total.")
                print("You must be the *sole* winner to get the flag.")
        else:
            print("\nYou lost...")


if __name__ == "__main__":
    main()

xoroshiro128+という乱数生成アルゴリズムを用いたじゃんけんNPCが99体います。これにあなたも含めた100プレイヤーでじゃんけんをするので、一発で一人勝ちしてください。
xoroshiro128+という乱数生成アルゴリズムの使い方はhttps://prng.di.unimi.it/に公開されています。

あなたは乱数のseedを自由に設定できます。うまくseedを設定してうまい手を出せば勝てるかもね！

解法

https://prng.di.unimi.it/xoroshiro128plus.cにあるxoroshiro128+のC言語での実装を見ると、コメントでThe state must be seeded so that it is not everywhere zero.と書かれています。
xoroshiro128+では乱数のseedとして(0,0)を設定すると内部状態が全部0になり、その後も乱数として0しか生成されず、乱数の機能を果たしません。
今回は入力値に細工をしてからseedとしていますが、その細工が固定値0x1234567890abcdef1234567890abcdefとのxorなので入力値を0x1234567890abcdef1234567890abcdefとすればseedを0にできます。実際には十進法に直した24197857200151252728969465429440056815の入力が必要です。

これで乱数を固定できたので、NPCの出す手が固定されました。あとは勝つ手を出せば良いです。

感想

じゃんけん１つ目。一発ギャグ。

ゲームAIをバグらせて無双できたら楽しいよね〜ということを考えてこの問題を作りました。
軽量な乱数生成器は大体xorshiftの変種か線形合同法の変種だと思っています。適当にやると周期が非常に短くなりがち。

xoroshiro128+のようなビット演算と加算だけで作られる乱数は軽量なのでゲームやシミュレーションに使いやすいと思います。実際にポケモンとかで使われているらしいです。
いつでもmt19937ほどの高次元での均等分布が必要なわけではないので、用途に応じて使い分けたいですね。

[Crypto] Lv.5 mod N Janken

問題概要

みんなでじゃんけん！
引き分けは無駄なのでなくしました。

この問題文もフレーバーテキストなので無視して良いです。
ncコマンドでサーバーにTCP接続してサーバーで実行されるPythonプログラムとやり取りをする問題です。

配布ファイル server.pyの他に手元で動かせるようにdockerfile,compose.ymlを配布しています。

server.py

#!/usr/local/bin/python3 from random import randrange from os import getenv

def nextrand(n):
n ^= n << 13
n ^= n >> 7
n ^= n << 17
return n & ((1 << 64) - 1)

def main():
MAX_CHEAT_COUNT = 600
PARTICIPANTS = 101
STRATEGY_LEN = 120
MATCHES = 20

janken_powers = [[0 for _ in range(STRATEGY_LEN)]
                 for _ in range(PARTICIPANTS - 1)]

for i in range(PARTICIPANTS - 1):
    janken_powers[i][0] = randrange(1, 2**64)
    for j in range(1, STRATEGY_LEN):
        janken_powers[i][j] = nextrand(janken_powers[i][j - 1])

print("🌟====================================================🌟")
print("  ✊✌️✋ Welcome to the ULTRA JANKEN TOURNAMENT! ✋✌️✊")
print("🌟====================================================🌟")
print("\n[MC] First, tell me your \"Secret Janken Strategy\"! (Space-separated integers, please!)")

try:
    player_strategy = list(map(int, input("Your Strategy: ").split()))
except ValueError:
    print("[MC] Oops! Those don't look like numbers. Please try again!")
    exit(0)

assert len(player_strategy) == STRATEGY_LEN
for val in player_strategy:
    assert 0 <= val < 2**64

print(f"\n[MC] Entry complete! We've received your strategy loud and clear!")
janken_powers.append(player_strategy)

total_cheats = 0

print("\n[MC] Now, let the tournament of destiny BEGIN!!!\n")

for match_num in range(MATCHES):
    print(f"\n--- [ MATCH {match_num + 1}/{MATCHES} ] ---")
    player_no = randrange(0, PARTICIPANTS)
    luck_pattern = [randrange(0, 2) for _ in range(STRATEGY_LEN)]

    print(f"[MC] Your Number is No: {player_no}")
    lucky = "".join(map(str, luck_pattern))
    print(f"[info] Current Luck Pattern: {lucky}")

    while True:
        action = input(
            "\n[?] What will you do? [C]heat the luck / [G]o Janken!: ").strip().upper()

        if action == "C":
            try:
                idx = int(input("Which luck index to flip?: "))
                if 0 <= idx < STRATEGY_LEN:
                    luck_pattern[idx] = 1 - luck_pattern[idx]
                    total_cheats += 1
                    print("[Info] Luck value altered silently.")
                else:
                    print("[ERROR] Error: Index out of range.")
            except ValueError:
                print("[ERROR] Error: Invalid integer.")

        elif action == "G":
            break
        else:
            print("[ERROR] Unrecognized command.")
            exit(0)

    clash_power = 0
    for i in range(PARTICIPANTS):
        for j in range(STRATEGY_LEN):
            clash_power ^= janken_powers[i][j] * luck_pattern[j]

    winner = clash_power % PARTICIPANTS

    print(
        "\n[MC] Alright, everyone together... Rock, Paper, SCISSORS!!! ✊✌️✋")
    print(f"[MC] And the winner is... Participant No.{winner}!!!")

    if winner != player_no:
        print("\n[Info] You lost...")
        exit(0)

    if total_cheats > MAX_CHEAT_COUNT:
        print(
            "\n[MC] Wait a minute... the luck generators are fluctuating wildly! SECURITY!!")
        exit(0)

    print("[MC] What an incredible match! Let's move right to the next one!\n")

print("🎊======================================================🎊")
print("  🏆 TOURNAMENT COMPLETED! 🏆")
print("🎊======================================================🎊")
print("\n[MC] What a breathtaking tournament! I've never seen such consistent \"luck\" before!")
print("[MC] Please accept this grand prize on behalf of our amazing winner! \n")

flag = getenv("FLAG", "FLAG{DUMMY}")
print(flag)

if name == 'main':
try:
main()
except Exception as e:
print(f"\n[MC] Whoops! Looks like we have some technical difficulties!")

mod N じゃんけんを知っていますか？大人数でじゃんけんを行うと引き分けが連続して長引いて嫌ですよね。勝者を1人だけ決めたいなら、それぞれが整数を宣言してその総和mod Nで勝者を決めれば良いですね！では実際にやってみましょう！

NPC100人とあなたの合計101人でmod N じゃんけんを行います。

NPCは秘密の乱数列(janken_powers)を生成します。
あなたも同様に整数列を宣言します。

それぞれのNPCの宣言する整数は事前に用意した乱数列から添字列(luck_pattern)の通りに選んでxorしたものです。
あなたの宣言する整数も同じluck_patternで決まります。
じゃんけんで20連勝してください！

勝利条件は全員の宣言した整数の合計 mod 101 があなたのplayer_noになることです。player_noは毎回教えてもらえるのでうまく調整して勝利したいですね。

luck_patternを1箇所ずつ改変できます。改変しすぎると怒られるので、600回以下の改変でどうにかして勝利しましょう。

解法

NPCの生成する乱数列は xorshift64 を用いて作られています。
xorshift64はxorとshiftという軽量なbit演算だけで疑似乱数列を生成するアルゴリズムです。
内部状態に対してxorとshiftの操作を行い、新たな内部状態を作成してそれを乱数の出力としています。

内部状態、内部状態を更新する関数、内部状態から乱数を生成する関数を整理しましょう。

内部状態: 64bit整数1つ
内部状態を更新する関数: nextrandで定義されたxorとshiftからなる関数
内部状態から乱数を生成する関数: 内部状態の64bit整数をそのまま利用する

ここで大事なのが内部状態から乱数を生成する関数です。xorshift64の場合では内部状態をそのまま乱数として使用します。これにより、乱数の出力と内部状態を区別せずに同一視できます。

内部状態を更新する関数を $f$ とします。最初の内部状態を $x_{0}$ とすると、生成される内部状態は次のようになります。xorshiftでは生成される乱数列も全く同じです。

x_{0}, f (x_{0}), f^{(2)} (x_{0}), \dots, f^{(k)} (x_{0}), \dots

$f$ の性質を調べます。64bit整数のxorとshiftは64bit整数を $F_{2}^{64}$ の元として扱えば $f$ は $F_{2}$ 線型空間の線型写像となります。
$F_{2}^{64}$ には $\oplus$ としてxorを入れます。

線型写像であるため、ある行列 $A \in F_{2}^{64 \times 64}$ が存在し $f (x) = A x$ となります。

今回の問題では各NPCごとに乱数列の特定の要素の総xorをとって宣言する整数を決定しています。
具体的には、指定された非負整数の集合 $S$ について、 $⨁_{k \in S} A^{k} x$ を宣言する整数に設定しています。

ケイリー・ハミルトンの定理を用いると、 $A$ の固有多項式 $p_{A}$ について $p_{A} (A) = O$ がわかります。
固有多項式の係数のうち $1$ である次数のみからなる集合を $S$ に設定できれば $⨁_{k \in S} (A^{k} x) = (⨁_{k \in S} A^{k}) x = p_{A} (A) x = O x = 0$ となり、初期の内部状態に関係なく宣言する整数を0に設定できます。 $p_{A}$ の次数は64以下であるため、乱数列の最初の65要素を利用すれば総xorを0にできます。

今回の問題では $S$ (=luck_pattern)を自由に操作できるため、これでNPC全ての宣言する整数を $0$ に固定することができました。

実際には任意の $F_{2}$ 多項式 $g (x)$ について $(g \cdot p_{A}) (A) = O$ となるため、今回のluck_pattern全体( $F_{2}$ 上の次数120未満の多項式)のうちNPCの宣言する整数を $0$ に固定できるluck_patternは $2^{120 - 65}$ 通り存在します。

提示されたluck_patternを少し変更することでこのパターンのどれかを作り、さらに、自分の宣言する整数 mod 101 がplayer_noになるようにします。変更には回数制限があるのでできるだけ変更回数が少ないものを選びたいです。変更回数は最初のluck_patternと目標となるluck_patternのハミング距離になること、固有多項式の多項式倍は $x^{k} p_{A}$ の線型結合になることを考えると線型符号の復号に見えますが、距離最小のものをとらなくとも平均で距離30以下を取れば良いので愚直な探索でも間に合います。

感想

じゃんけん2つ目。
じゃんけんを2問出題してしまったせいで間違えて別のじゃんけんのflagを提出する人がいました。問題名を読んでください。

線形な乱数生成器はこれができるというのは知っていましたが、実際に構築してみると本当にできてしまってショックを受けました。

この人が作った問題全部乱数じゃん。なんで？

[PPC] Lv.3 Sum of Prod of Root

問題・解説はyukicoderにあります。
https://yukicoder.me/problems/no/3505

PPCジャンルの難易度順ソート、評価の確認を担当しました。
難易度評価に失敗しました。
ごめんなさい。

でも高校数学と言われたら2.5付けたくなりませんか？(言い訳)

[PPC] Lv.4 OR Mapping

問題・解説はyukicoderにあります。
https://yukicoder.me/problems/no/3508

@n3による原案提案時には無向グラフの設定でしたが、有向グラフでも解けることを主張しました。無向グラフでも有向グラフでも偶奇性だけの判定ですが、強連結成分をまたぐ移動により偶奇性の自由度が増えて難しくなります。

[PPC] Lv.5 RPS Eliminations

問題・解説はyukicoderにあります。
https://yukicoder.me/problems/no/3510

じゃんけん3つ目。じゃんけんとPPCのコンテストになってしまった……

フットブレーキを使いすぎてじゃんけんに弱くなってしまう現象ってなーんだ？

ペーパーロック現象

RPSを利用した最適化の問題を作ろうという会話があり、そこから作りました。
木構造になることはすぐにわかりその後どうしようか考えていたら解いてもらえました。

最終結果を決めると全体で何通りあるかは定まるので存在判定はできますね。対称性があるので議論も楽です。
部分木についても同様に数だけは定まるのでDFSでprefixを構築する際にsuffix部分が何通りあるかを考慮することができます。面白いですね。

終わりに

CPCTF2026へ参加していただいたみなさま、ご参加ありがとうございました！

去年に引き続き、PPCとCryptoの問題を作っていました。数学っぽい何かをプログラムっぽい何かに適用して何かを作る、壊すという体験を提供できていたら嬉しいです。

去年までだとLv.5相当の問題は10人程度にしか解かれなかったのですが、今年は50人近くの参加者に解いていただけました。多くの人に解いていただき大変嬉しいです。

デジタル庁、総務省、経済産業省が定める電子政府における調達のために参照すべき暗号です。通常は推奨暗号リストに載っているものを使うことになり、推奨候補暗号はあまり使われません。 ↩︎

CPCTF 2026 作問者writeup (Nzt3編)

私が関わった問題

Crypto

PPC

[Crypto] Lv.2 Very Exciting

問題概要

解法

感想

[Crypto] Lv.3 Janken Master

問題概要

解法

感想

[Crypto] Lv.5 mod N Janken

問題概要

解法

感想

[PPC] Lv.3 Sum of Prod of Root

[PPC] Lv.4 OR Mapping

[PPC] Lv.5 RPS Eliminations

終わりに

この記事をシェア

関連する記事