ふるつき

v(*'='*)v かに

2021年印象に残ったCTFと暗号問題

はじめに

この記事は 2021年の CTF Crypto 問を振り返る | y011d4.log のリスペクト記事です。こちらの記事に挙げられている問題のどれも確かにと思わせられる、記憶に残る問題ではあったのですが、私が0から選んでみると少し違ったものが挙げられるかな、ということで書いてみようと思います。

おことわりとして、私はzer0ptsというチームでできるだけ開催されるCTFには参加していたつもりでしたが、見返してみるとさまざまな要因から参加できていないCTFも多くありました。全ての問題を精査したものではないということはご承知おきください*1。

DiceCTF 2021

個人的には今年No. 1くらいのCTFです。あのDiceGang*2が開催するCTFで、本当に多くのことを学べる暗号問題が出題されました。このCTFが年初にあったことで2021年のCrypto業界は大きく様変わりしたのではないかと思います。

benaloh

問題ソースコード

from Crypto.Random.random import randrange
from Crypto.Util.number import getPrime, GCD

r = 17

def keygen():
    while True:
        p = getPrime(1024)
        a, b = divmod(p-1, r)
        if b == 0 and GCD(r, a) == 1:
            break
    while True:
        q = getPrime(1024)
        if GCD(r, q-1) == 1:
            break
    n = p*q
    phi = (p-1)*(q-1)//r
    y = 1
    while True:
        y = randrange(n)
        x = pow(y, phi, n)
        if x != 1:
            break
    log = {pow(x, i, n): i for i in range(r)}
    return (n, y), (n, phi, log)

def encrypt(data, pk):
    n, y = pk
    u = randrange(n)
    a = randrange(n)
    c = randrange(n)
    for m in data.hex():
        yield pow(y, int(m, 16), n) * pow(u, r, n) % n
        u = (a*u + c) % n

def decrypt(data, sk):
    n, phi, log = sk
    return bytes.fromhex(''.join(f'{log[pow(z, phi, n)]:x}' for z in data))

if __name__ == '__main__':
    from local import flag
    pk, sk = keygen()
    print(pk)
    for z in encrypt(flag, pk):
        print(z)

この問題について詳細な解説をすることは難しいのですが簡単に言うとbenaloh cryptosystemに手を加えた問題で、 c_i = y^{m_i}u_i^r \mod n という形式で暗号化されており、各 u_{i+1} = au_{i} + c \mod nと計算されています。今見れば「グレブナー基底とかで計算すれば一発では」と思うところではありますが、個人的には暗号問題におけるグレブナー基底の有用性を幅広く知らしめたのがこの問題という認識でいて、それゆえ非常に強く印象に残っています。

グレブナー基底はこれまでも一部のCryptoプレイヤーの間では常識のように用いられていたようですが、連立した多項式の解を求める操作は多くの場合グレブナー基底を使わずとも手で十分ということが多くあり必須ではなかったため、大衆に浸透するには至らないという状態であったのではないかと推測しています。一方この問題では線形合同法をベースとしてある程度複雑な式がネストしており、手で解くのはまず不可能ということでグレブナー基底が登場し、writeupなどからこのテクニックの存在が多くのプレイヤーに知れ渡りました。私もこの問題でグレブナー基底の有用性を認識し、BSides Ahmedabad CTF 2021のSSSS.RNGなどでグレブナー基底を用いる問題を出題しています。

plagiarism

問題ソースコード

Two agents, Blex and Kane, have simultaneously known very secret message and transmitted it to Center. You know following:
1) They used RSA with this public key
2) They sent exactly the same messages except the signatures (name appended, eg. "[message]Blex")
3) They did encryption this way:

m = int(message.encode("hex"), 16)
c = pow(m, e, N)

4) And here are cryptograms you have intercepted:

N = 25898966400928827905718377946331123070958718286581765316565582158865227877882475404853218079499084099440419144196215764927720893687968939899067275095801562867742359933997487928281899714724738097735994026225339488710478292473051567851786254924548138570069406420407124627567648479424564834446192417334669768477661434992797176428220265984651288944265998446714590797833756720922745187467388408600309665467669255896919554072379878017822219455974525233467767926938557154083882126002952139561283708342676308894318951822068027821029295524097544028901807902120777407151278396388621981625398417573347316888458337381776303199529

e = 1048577

ciphertext_Blex = 11140520553087800834883326476247582685177207584737264356946559762068509060522907835540767944557089926814767920501376431871780404000550271362410228709616559148950928004959648199391157781102695421411667843970881959939688515679415870087007797819271601359811630724878746762862603629420061133824605384527474682526549557804674160851967543475275374840169790764048711047622418045734436512050742433282306694490346907876574514077395835974083376649624559301087384766644865104383786285302561584731767419571603248493060257358632833957327996996960955767927114473513709882904104552609194519132931270741118197821776138632855021619178

ciphertext_Kane = 2922817623733019475805146570530296261205732600738503605503192845278422660686627490817081424885152809772315629265930072636690234953045955503581182067349322827011065359648958225896393305011175960879100475146203207801533980643261035226402857047007061320653920746872424363923515091038846823007819033456503365649022294092944985887626605207259444051959239244136999684366533551627508385114998024232490369665950339127904350803268889205463047713233591604324960184727360413931125906144631968128488876241314939855024305076160092193380013725939761970042406866169417457376487954247442308318888399299295082898238584625937490546472



Now tell me that secret message! (The answer for this task starts from 'dice{')

DiceCTFは「存在するが広く知られていない知識」をうまく問題に落とし込むのが本当にうまく、このplagiarismもbenalohに引き続いてHalf-GCDというテクニックをCrypto界に浸透させた立役者的な問題であろうと思います。

この問題はどう見てもFranklin-Reiter's Related Message Attackではあるのですがe = 1048577と大きいことが特徴で、多項式のGCDをユークリッドの互助法的に愚直に求めようとしても計算が間に合いません。そこで登場するのがHalf-GCDです。詳細は各自でお調べいただきたいところですが、Half-GCDではGCDより計算量が多少改善され、eが大きい場合にも現実的な時間で解けるようになります。

もっとも、愚直なGCDに比べて計算量的な改善は多少の範疇にとどまりますので、計算資源を費やせばHalf-GCDを用いずともこの問題を解くことはできます。そういった力任せの解法が現実的に多く用いられた問題の例としてもこの問題は印象に残っています。

この問題でHalf-GCDの存在が広まって以降、多少の計算を要する多項式の問題が出題されるようになりました。具体的にはBSides Ahmedabad CTF 2021のECC-RSA 2などですね。

Union CTF

Union CTFはCr0wnというチームが主催するCTFだったと思います。この時期は justCTF 2020→Dice CTF→Union CTFと強いチームの開催する（初？）CTFが連続していて怒涛でしたね。Union CTFでは2問ほど印象深い問題がありますが、1問はこの後の番外編で紹介して、こちらでは普通に面白かった1問をご紹介します

neo-classical key exchange

問題ソースコード

import os
from hashlib import sha1
from random import randint
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad

FLAG = b"union{XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX}"

def list_valid(l):
    x = l // 2
    checked = set([x])
    while x * x != l:
        x = (x + (l // x)) // 2
        if x in checked: return False
        checked.add(x)
    return True

def list_iter(n):
    x = n
    y = (x + 1) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def list_mul(l1,l2,p):
    X, Y = len(l1), len(l2)
    Z = list_iter(X)
    assert X == Y
    assert list_valid(X)
    l3 = []
    for i in range(Z):
        for j in range(Z):
            prod_list = [x*y for x,y in zip(l1[Z*i:Z*(i+1)], l2[j::Z])]
            sum_list = sum(prod_list) % p
            l3.append(sum_list)
    return l3

def list_exp(l0, e, p):
    exp = bin(e)[3::]
    l = l0
    for i in exp:
        l = list_mul(l,l,p)
        if i == '1':
            l = list_mul(l,l0,p)
    return l

def gen_public_key(G,p):
    k = randint(2,p-1)
    B = list_exp(G,k,p)
    return B,k

def gen_shared_secret(M,k,p):
    S = list_exp(M,k,p)
    return S[0]

def encrypt_flag(shared_secret: int):
    # Derive AES key from shared secret
    key = sha1(str(shared_secret).encode('ascii')).digest()[:16]
    # Encrypt flag
    iv = os.urandom(16)
    cipher = AES.new(key, AES.MODE_CBC, iv)
    ciphertext = cipher.encrypt(pad(FLAG, 16))
    # Prepare data to send
    data = {}
    data['iv'] = iv.hex()
    data['encrypted_flag'] = ciphertext.hex()
    return data

p = 64050696188665199345192377656931194086566536936726816377438460361325379667067
G = [37474442957545178764106324981526765864975539603703225974060597893616967420393,59548952493843765553320545295586414418025029050337357927081996502641013504519, 31100206652551216470993800087401304955064478829626836705672452903908942403749, 13860314824542875724070123811379531915581644656235299920466618156218632047734, 20708638990322428536520731257757756431087939910637434308755686013682215836263, 24952549146521449536973107355293130621158296115716203042289903292398131137622, 10218366819256412940642638446599581386178890340698004603581416301746386415327, 2703573504536926632262901165642757957865606616503182053867895322013282739647, 15879294441389987904495146729489455626323759671332021432053969162532650514737, 30587605323370564700860148975988622662724284710157566957213620913591119857266, 36611042243620159284891739300872570923754844379301712429812256285632664939438, 58718914241625123259194313738101735115927103160409788235233580788592491022607, 18794394402264910240234942692440221176187631522440611503354694959423849000390, 37895552711677819212080891019935360298287165077162751096430149138287175198792, 42606523043195439411148917099933299291240308126833074779715029926129592539269, 58823705349101783144068766123926443603026261539055007453105405205925131925190, 5161282521824450434107880210047438744043346780853067016037814677431009278694, 3196376473514329905892186470188661558538142801087733055324234265182313048345, 37727162280974181457962922331112777744780166735208107725039910555667476286294, 43375207256050745127045919163601367018956550763591458462169205918826786898398, 21316240287865348172884609677159994196623096993962103476517743037154705924312, 7032356850437797415676110660436413346535063433156355547532408592015995190002, 3916163687745653495848908537554668396996224820204992858702838114767399600995, 13665661150287720594400034444826365313288645670526357669076978338398633256587,23887025917289715287437926862183042001010845671403682948840305587666551788353]
A,a = gen_public_key(G,p)
B,b = gen_public_key(G,p)
assert gen_shared_secret(A,b,p) == gen_shared_secret(B,a,p)

shared_secret = gen_shared_secret(B,a,p)
encrypted_flag = encrypt_flag(shared_secret)

print(f"Alice's public key: {A}") 
print(f"Bob's public key: {B}")
print(f"Encrypted flag: {encrypted_flag}")

ソースコードが多少複雑ですが*3、これは一般線形群上の離散対数問題が解けますか、という問題です。当然通常は解くことができないんですが、この問題で用いられている行列は対角化できないもので、このとき離散対数問題が解けてしまいます*4。世の中にはいろんな群があるけど、いろんな問題をその群で実現したときに特定のケースで脆弱になるね、というのは面白かったので印象に残っているし、ptr-yudaiが鮮やかな式変形で解法を導いていてすげーとなったのも憶えています。

m0leCon 2021

m0lecon、去年からいい問題が出ると思って注目しているんですが*5、あんまり世間で楽しみにされている様子は見ませんね……。

Giant log

問題ソースコード

import random
from secret import flag, fast_exp
import signal

p = 0x83f39daf527c6cf6360999dc47c4f0944ca1a67858a11bd915ee337f8897f36eff98355d7c35c2accdf4555b03a9552b4bf400915320ccd0ba60b0cb7fcad723
g = 0x15a5f7dec38869e064dd933e23c64f785492854fbe8a6e919d991472ec68edf035eef8c15660d1f059ca1600ee99c7f91a760817d7a3619a3e93dd0162f7474bbf


def test():
    for _ in range(10):
        x = random.randint(1, p)
        n = random.randint(1, 20)
        m = p**n
        assert pow(g, x, m) == fast_exp(x, n)

def chall():
    n = 1000
    x = random.randint(1, p**(n-1))
    y = fast_exp(x, n)
    return x, y


def stop(signum, stack):
    print("Too slow")
    exit(1)


def main():
    x, y = chall()
    timeout = 60
    print(hex(y))
    print("Now gimme x")
    signal.alarm(timeout)
    x_inp = int(input(), 16)
    if x == x_inp:
        print("Wow, impressive!")
        print(flag)
    else:
        print("Nope, sorry")


if __name__ == "__main__":
    signal.signal(signal.SIGALRM, stop)
    #test()
    main()

この問題は全然解けなかったんですが、要するに y \equiv g^x \mod p^nという離散対数問題で、これ解けるんですかすげーということで印象に残っています。また、この問題はこの後紹介するOMH 2021 CTFのTower of Powerという問題と同時期に出題されたのですが、こちらは似て非なる問題で同じようなタイミングで、これらの難題が別々に出題されたことの偶然もよく憶えています。ところでこれはなんで解けてるんですか？

OMH 2021 CTF

CONFidence CTFが名前を変えたんですかね、なんで名前変えたんだろう

Tower of Power

問題ソースコード

from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
load('secret.sage')
M = x^127 + x^126 + x^125 + x^124 + x^122 + x^120 + x^118 + x^117 + x^115 + x^108 + x^107 + x^104 + x^103 + x^100 + x^99 + x^98 + x^96 + x^95 + x^94 + x^91 + x^88 + x^85 + x^83 + x^82 + x^81 + x^77 + x^74 + x^72 + x^70 + x^66 + x^65 + x^64 + x^57 + x^56 + x^55 + x^54 + x^50 + x^49 + x^48 + x^46 + x^44 + x^43 + x^37 + x^36 + x^34 + x^33 + x^28 + x^25 + x^22 + x^19 + x^18 + x^17 + x^16 + x^15 + x^14 + x^13 + x^11 + x^10 + x^8 + x^7 + x^4 + x^2 + 1

K.<x> = GF(2^127, 'x', M)
z = x + 1

# for _ in range(n):
#     z = z**69
z = z**ZZ(pow(69, n, z.multiplicative_order()))

print(z)

aes = AES.new(long_to_bytes(n), AES.MODE_ECB)
print(aes.encrypt(flag.encode()).hex())

こちらもわけわかんない群の上でのちょっと大きい離散対数問題ということで、giant logと一緒に記憶に残っています。writeupはあるんですが、「magma使ったら解けたわ」ということで全然意味わからないです。何が起こっているのかわかった方はこっそり教えてください

Google Capture The Flag 2021

Google CTF、評判よかったり良くなかったりするんですよね。あとソースコードにライセンス埋めこんでるのはさすがというからしいですね

tiramisu

問題ソースコード（一部）

// Copyright 2021 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//      http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

package server

import (
    "crypto-tiramisu/pb"
    "crypto/ecdsa"
    "fmt"
    "math/big"
)

const serverCurveId = pb.EcdhKey_SECP224R1

var flagCipherKdfInfo = []byte("Flag Cipher v1.0")
var flagMacKdfInfo = []byte("Flag MAC v1.0")
var flagFixedIV = []byte{0x73, 0x40, 0x76, 0xd5, 0x67, 0xe0, 0x9, 0x2a, 0xbc, 0xe1, 0x9, 0x15, 0x82, 0x55, 0x43, 0x7d}

var channelCipherKdfInfo = []byte("Channel Cipher v1.0")
var channelMacKdfInfo = []byte("Channel MAC v1.0")

type Server struct {
    flag          string
    encryptedFlag *pb.Ciphertext
    key           *ecdsa.PrivateKey
    channel       *AuthCipher
}

func buildFlagCipher(priv *ecdsa.PrivateKey) (*AuthCipher, error) {
    secret := make([]byte, priv.Params().BitSize/8)
    priv.D.FillBytes(secret)

    return newAuthCipher(secret, flagCipherKdfInfo, flagMacKdfInfo)
}

func NewServer(flag string, priv *pb.EcdhPrivateKey) (*Server, error) {
    // Load private key.
    if priv.Key.Curve != serverCurveId {
        return nil, fmt.Errorf("priv.Key.Curve != serverCurveId, want %d, got %d", serverCurveId, priv.Key.Curve)
    }
    key, err := proto2ecdsaPrivateKey(priv)
    if err != nil {
        return nil, fmt.Errorf("proto2ecdsaPrivateKey() = %v, want nil error", err)
    }

    // Private key sanity checks.
    x, y := key.ScalarBaseMult(key.D.Bytes())
    if x.Cmp(key.X) != 0 || y.Cmp(key.Y) != 0 {
        return nil, fmt.Errorf("input private key does not match public")
    }
    if !key.Curve.IsOnCurve(key.X, key.Y) {
        return nil, fmt.Errorf("input key not on curve X=%X, Y=%X", key.X, key.Y)
    }

    // Encrypt flag.
    flagCipher, err := buildFlagCipher(key)
    if err != nil {
        return nil, fmt.Errorf("deriveFlagKey()=%v, want nil error", err)
    }
    encryptedFlag, err := flagCipher.Encrypt(flagFixedIV, []byte(flag))
    if err != nil {
        return nil, fmt.Errorf("encryptFlag()=%v, want nil error", err)
    }

    return &Server{
        flag:          flag,
        encryptedFlag: encryptedFlag,
        key:           key,
    }, nil
}

func (server *Server) ServerHello() *pb.ServerHello {
    return &pb.ServerHello{
        Key: &pb.EcdhKey{
            Curve: serverCurveId,
            Public: &pb.Point{
                X: server.key.X.Bytes(),
                Y: server.key.Y.Bytes(),
            },
        },
        EncryptedFlag: server.encryptedFlag,
    }
}

func (server *Server) EstablishChannel(clientHello *pb.ClientHello) error {
    // Load peer key.ecnrypted
    peer, err := proto2ecdsaKey(clientHello.Key)
    if err != nil {
        return err
    }

    // Key sanity checks.
    if !peer.Curve.IsOnCurve(peer.X, peer.Y) {
        return fmt.Errorf("point (%X, %X) not on curve", peer.X, peer.Y)
    }

    // Compute shared secret.
    P := server.key.Params().P
    D := server.key.D.Bytes()
    sharedX, _ := server.key.ScalarMult(new(big.Int).Mod(peer.X, P), new(big.Int).Mod(peer.Y, P), D)

    masterSecret := make([]byte, server.key.Params().BitSize/8)
    sharedX.FillBytes(masterSecret)

    // Derive AES+MAC session keys.
    server.channel, err = newAuthCipher(masterSecret, channelCipherKdfInfo, channelMacKdfInfo)
    if err != nil {
        return fmt.Errorf("newAuthCipher()=%v, want nil error", err)
    }
    return nil
}

// Read and re-encrypt client's message.
func (server *Server) EchoSessionMessage(clientMsg *pb.SessionMessage) *pb.SessionMessage {
  data, err := server.channel.Decrypt(clientMsg.EncryptedData)
  if err != nil {
      return &pb.SessionMessage{}
  }

  iv := make([]byte, len(clientMsg.EncryptedData.Iv))
  copy(iv, clientMsg.EncryptedData.Iv)
  iv[0] ^= 1

  encryptedData, err := server.channel.Encrypt(iv, data)
  if err != nil {
      return &pb.SessionMessage{}
  }
  return &pb.SessionMessage{
      EncryptedData: encryptedData,
  }
}

これはCRTでsecp224r1ではInvalidCurveAttackになるようなsecp256r1上の点を生成してbruteforceでECDLPをとき、CRTでd復元する問題です。これをtiramisuするといいます。きれいな問題だなと思ったのでよく憶えています。あとprotobufが鬱陶しかったので憶えています……

DownUnderCTF 2021

josephがめちゃくちゃ頑張っていたCTFことDownUnderCTFです。joseph作のcryptoがひたすらよくできていました。

yadlp

問題ソースコード

def G_add(A, B):
    x1, y1 = A
    x2, y2 = B
    return ((x1*x2 + D*y1*y2) % p, (x1*y2 + x2*y1 + 2*y1*y2) % p)

def G_mul(A, k):
    out = (1, 0)
    while k > 0:
        if k & 1:
            out = G_add(out, A)
        A = G_add(A, A)
        k >>= 1
    return out

def rand_element():
    while True:
        x = randint(1, p-1)
        d = x^2 * (D + 1) - D
        if (x & 1 == d & 1) and kronecker(d, p) == 1:
            y = (x + sqrt(Zmod(p)(d))) * inverse_mod(D, p) % p
            return (x, y)

D = 13337
p = 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
assert p.nbits() >= 512
assert ((p-1)//2).is_prime() # safe prime

FLAG = open('flag.txt', 'rb').read().strip()
assert len(FLAG) % 8 == 0
M = [int.from_bytes(FLAG[i:i+8], 'big') for i in range(0, len(FLAG), 8)]

G = [rand_element() for _ in M]
c = (1, 0)
for m, gi in zip(M, G):
    c = G_add(c, G_mul(gi, m))

print(f'{D = }')
print(f'{p = }')
print(f'{G = }')
print(f'{c = }')

同じようなアイデアの問題を温めていたのでよく憶えています……

TSG CTF 2021

World No.1 CTFとの呼び声も高いTSG CTFです。keymoonさんが強かったのも憶えています。

This is DSA

問題ソースコード

# See also https://github.com/tsg-ut/pycryptodome
from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
from Crypto.Util.number import getPrime
from Crypto.Random.random import randrange
from base64 import b64decode
from signal import alarm
import os

alarm(15)

q = getPrime(256)
print(f'q = {q}')

p = int(input('p? '))
h = int(input('h? '))

g = pow(h, (p - 1) // q, p)
x = randrange(q)
y = pow(g, x, p)

print(f'g = {g}')
print(f'y = {y}')

dsa = DSA.construct((y, g, p, q, x))
dss = DSS.new(dsa, 'fips-186-3')

print('Thank you for helping me with DSA! Now give me the base64-encoded signature of sha256("flag")')
sign = b64decode(input('sign? '))

dss.verify(SHA256.new(b'flag'), sign)
print(f"Awesome! {os.environ.get('FLAG')}")

https://github.com/tsg-ut/pycryptodome/tree/22388c5fec4607e8e255926c3e95724a2f070e76

感動しました！！！　最高の作問だと思います。Best Crypto Challenge 2021どころかBest Crypto Challenge Everかも

番外編

手前味噌なので番外編です。何がNOTなのかは知りません

Mordell Primes - Union CTF / NOT Mordell Primes - zer0pts CTF 2021

問題ソースコード - Mordell Primes

from Crypto.Util.number import bytes_to_long
from secrets import k, FLAG

assert k < 2^128
assert FLAG.startswith(b'union{')

E = EllipticCurve(QQ,[0,1,0,78,-16])
P = E(1,8)
Q = k*P
R = (k+1)*P

p = Q[0].numerator()
q = R[0].numerator()

assert is_prime(p)
assert is_prime(q)

e = 0x10001
N = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,N)

print(f'N = {N}')
print(f'c = {c}')

問題ソースコード - NOT Mordell Primes

from Crypto.Util.number import bytes_to_long
from secrets import k, FLAG


p = 13046889097521646369087469608188552207167764240347195472002158820809408567610092324592843361428437763328630003678802379234688335664907752858268976392979073
a = 10043619664651911066883029686766120169131919507076163314397915307085965058341170072938120477911396027902856306859830431800181085603701181775623189478719241
b = 12964455266041997431902182249246681423017590093048617091076729201020090112909200442573801636087298080179764338147888667898243288442212586190171993932442177

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

P = E(11283606203023552880751516189906896934892241360923251780689387054183187410315259518723242477593131979010442607035913952477781391707487688691661703618439980, 12748862750577419812619234165922125135009793011470953429653398381275403229335519006908182956425430354120606424111151410237675942385465833703061487938776991)
Q = k*P
R = (k+1)*P

p = int(Q[0])
q = int(R[0])

assert is_prime(p)
assert is_prime(q)

e = 0x10001
N = p*q
m = bytes_to_long(FLAG)
c = pow(m,e,N)

print(f'N = {N}')
print(f'c = {c}')

Union CTF 2021で出題されたMordell Primesは単調性を使って探索するだけの問題だったのですが割と苦戦した結果、DiceCTFで憶えたばかりのグレブナー基底などを試していたところ、別の問題が作れそう！　となってできたのがNOT Mordell Primesです。

これはなかなかいい問題ができたぞと思いながら、Union CTF 2021のDiscordを見に行くとhellmanがこんな投稿をしておりました😰

f:id:Furutsuki:20211221000928p:plain

やべーーーと思いつつ、そのまま出したらhellmanが思いもよらない解き方をしていたので面白かったです

https://affine.group/writeup/2021-01-Zer0pts#not-mordell-primes

感想

ここで紹介できてない面白くて難しい問題も無限個あるんですよね。来年は一体どうなってしまうんだ

*1:参加しなかったCTFで後から見返して面白いと感じた問題もあったけど、こちらもリアルタイムな印象ではないので今回はパスとしてます

*2:defundしか認識していなかったけど、ちらっとみたらwillwamとかTuxとかも所属しているんですか？　デカすぎる

*3:よくないと思う……。問題のコンセプトがシンプルなのにソースコードが複雑になってしまうのは何故なんですかね

*4:ジョルダン標準形を考えるとλaとaλa-1が登場するので解けます

*5:後スコアボードで使われているCTFdのテーマが良い