2024-ImaginaryCTF-wp-crypto

依然有最喜欢的maple师傅的题，依然做不来几道，不过还是记录一下。打*的赛后才会做，打$的不会做。

base64

题目描述：

1	yet another base64 decoding challenge

题目：

from Crypto.Util.number import bytes_to_long

q = 64

flag = open("flag.txt", "rb").read()
flag_int = bytes_to_long(flag)

secret_key = []
while flag_int:
    secret_key.append(flag_int % q)
    flag_int //= q

print(f"{secret_key = }")

secret_key = [10, 52, 23, 14, 52, 16, 3, 14, 37, 37, 3, 25, 50, 32, 19, 14, 48, 32, 35, 13, 54, 12, 35, 12, 31, 29, 7, 29, 38, 61, 37, 27, 47, 5, 51, 28, 50, 13, 35, 29, 46, 1, 51, 24, 31, 21, 54, 28, 52, 8, 54, 30, 38, 17, 55, 24, 41, 1]

就是简单的把flag用64进制表示而已。

exp：

from Crypto.Util.number import *

secret_key = [10, 52, 23, 14, 52, 16, 3, 14, 37, 37, 3, 25, 50, 32, 19, 14, 48, 32, 35, 13, 54, 12, 35, 12, 31, 29, 7, 29, 38, 61, 37, 27, 47, 5, 51, 28, 50, 13, 35, 29, 46, 1, 51, 24, 31, 21, 54, 28, 52, 8, 54, 30, 38, 17, 55, 24, 41, 1]

flag = 0
for i in range(len(secret_key)):
    flag += 64**i*secret_key[i]
print(long_to_bytes(flag))

#ictf{b4se_c0nv3rs1on_ftw_236680982d9e8449}

integrity

题目描述：

1	I think this is how signing works

题目：

from Crypto.Util.number import *
from binascii import crc_hqx

p = getPrime(1024)
q = getPrime(1024)

n = p*q
e = 65537
tot = (p-1)*(q-1)
d = pow(e, -1, tot)

flag = bytes_to_long(open("flag.txt", "rb").read())
ct = pow(flag, e, n)

#signature = pow(flag, d, n) # no, im not gonna do that
signature = pow(flag, crc_hqx(long_to_bytes(d), 42), n)

print(f"{n = }")
print(f"{ct = }")
print(f"{signature = }")

n = 10564138776494961592014999649037456550575382342808603854749436027195501416732462075688995673939606183123561300630136824493064895936898026009104455605012656112227514866064565891419378050994219942479391748895230609700734689313646635542548646360048189895973084184133523557171393285803689091414097848899969143402526024074373298517865298596472709363144493360685098579242747286374667924925824418993057439374115204031395552316508548814416927671149296240291698782267318342722947218349127747750102113632548814928601458613079803549610741586798881477552743114563683288557678332273321812700473448697037721641398720563971130513427
ct = 5685838967285159794461558605064371935808577614537313517284872621759307511347345423871842021807700909863051421914284950799996213898176050217224786145143140975344971261417973880450295037249939267766501584938352751867637557804915469126317036843468486184370942095487311164578774645833237405496719950503828620690989386907444502047313980230616203027489995981547158652987398852111476068995568458186611338656551345081778531948372680570310816660042320141526741353831184185543912246698661338162113076490444675190068440073174561918199812094602565237320537343578057719268260605714741395310334777911253328561527664394607785811735
signature = 1275844821761484983821340844185575393419792337993640612766980471786977428905226540853335720384123385452029977656072418163973282187758615881752669563780394774633730989087558776171213164303749873793794423254467399925071664163215290516803252776553092090878851242467651143197066297392861056333834850421091466941338571527809879833005764896187139966615733057849199417410243212949781433565368562991243818187206912462908282367755241374542822443478131348101833178421826523712810049110209083887706516764828471192354631913614281317137232427617291828563280573927573115346417103439835614082100305586578385614623425362545483289428

题目给出了两组数据：

$ct = m^e \quad(mod\;n)$ $sig = m^{crchqx(d,42)} \quad(mod\;n)$

似乎比较复杂，但是搜索一下发现说这个crchqx其实就是计算从给定数值42开始的d的crc16的值，所以其实加密指数也只有16bit，因此爆破一下这个指数，然后共模就可以了。

exp：

from Crypto.Util.number import *
from gmpy2 import gcdext,powmod

n = 10564138776494961592014999649037456550575382342808603854749436027195501416732462075688995673939606183123561300630136824493064895936898026009104455605012656112227514866064565891419378050994219942479391748895230609700734689313646635542548646360048189895973084184133523557171393285803689091414097848899969143402526024074373298517865298596472709363144493360685098579242747286374667924925824418993057439374115204031395552316508548814416927671149296240291698782267318342722947218349127747750102113632548814928601458613079803549610741586798881477552743114563683288557678332273321812700473448697037721641398720563971130513427
ct = 5685838967285159794461558605064371935808577614537313517284872621759307511347345423871842021807700909863051421914284950799996213898176050217224786145143140975344971261417973880450295037249939267766501584938352751867637557804915469126317036843468486184370942095487311164578774645833237405496719950503828620690989386907444502047313980230616203027489995981547158652987398852111476068995568458186611338656551345081778531948372680570310816660042320141526741353831184185543912246698661338162113076490444675190068440073174561918199812094602565237320537343578057719268260605714741395310334777911253328561527664394607785811735
signature = 1275844821761484983821340844185575393419792337993640612766980471786977428905226540853335720384123385452029977656072418163973282187758615881752669563780394774633730989087558776171213164303749873793794423254467399925071664163215290516803252776553092090878851242467651143197066297392861056333834850421091466941338571527809879833005764896187139966615733057849199417410243212949781433565368562991243818187206912462908282367755241374542822443478131348101833178421826523712810049110209083887706516764828471192354631913614281317137232427617291828563280573927573115346417103439835614082100305586578385614623425362545483289428

e = 65537
for i in range(3,2**16):
    dd = i
    d,x,y = gcdext(e,dd)
    m = powmod(ct,x,n)*powmod(signature,y,n) % n
    flag = long_to_bytes(m)
    if(b"ictf" in flag):
        print(flag)

#ictf{oops_i_leaked_some_info}

tango

题目描述：

1	Let's dance!

题目：

from Crypto.Cipher import Salsa20
from Crypto.Util.number import bytes_to_long, long_to_bytes
import json
from secrets import token_bytes, token_hex
from zlib import crc32

from secret import FLAG

KEY = token_bytes(32)


def encrypt_command(command):
    if len(command) != 3:
        print('Nuh uh.')
        return
    cipher = Salsa20.new(key=KEY)
    nonce = cipher.nonce
    data = json.dumps({'user': 'user', 'command': command, 'nonce': token_hex(8)}).encode('ascii')
    checksum = long_to_bytes(crc32(data))
    ciphertext = cipher.encrypt(data)
    print('Your encrypted packet is:', (nonce + checksum + ciphertext).hex())


def run_command(packet):
    packet = bytes.fromhex(packet)
    nonce = packet[:8]
    checksum = bytes_to_long(packet[8:12])
    ciphertext = packet[12:]

    try:
        cipher = Salsa20.new(key=KEY, nonce=nonce)
        plaintext = cipher.decrypt(ciphertext)

        if crc32(plaintext) != checksum:
            print('Invalid checksum. Aborting!')
            return

        data = json.loads(plaintext.decode('ascii'))
        user = data.get('user', 'anon')
        command = data.get('command', 'nop')

        if command == 'nop':
            print('...')
        elif command == 'sts':
            if user not in ['user', 'root']:
                print('o_O')
                return
            print('The server is up and running.')
        elif command == 'flag':
            if user != 'root':
                print('You wish :p')
            else:
                print(FLAG)
        else:
            print('Unknown command.')
    except (json.JSONDecodeError, UnicodeDecodeError):
        print('Invalid data. Aborting!')


def menu():
    print('[E]ncrypt a command')
    print('[R]un a command')
    print('[Q]uit')


def main():
    print('Welcome to the Tango server! What would you like to do?')
    while True:
        menu()
        option = input('> ').upper()
        if option == 'E':
            command = input('Your command: ')
            encrypt_command(command)
        elif option == 'R':
            packet = input('Your encrypted packet (hex): ')
            run_command(packet)
        elif option == 'Q':
            exit(0)
        else:
            print('Unknown option:', option)


if __name__ == '__main__':
    main()

连上靶机后，靶机会随机生成32字节的KEY，之后有两个选项供选择：

输入E，可以输入一个command，靶机会对command进行加密
输入R，可以输入一段打包的密文，靶机会拆开这段密文，进行解密+检查

两种交互均可以无限次进行。

然后来看下加密的encrypt_command函数和解密的run_command函数分别在做什么。

对于encrypt，需要输入一个长度为3的字符串当作command，然后靶机会用KEY初始化一个Salsa20的加密器，并加密下面这段json：

1	{'user': 'user', 'command': command, 'nonce': token_hex(8)}

同时，靶机会计算这段json的crc32值checksum，之后返回如下值作为密文：

1	nonce + checksum + ciphertext

这里需要注意一下返回的密文中的nonce和json里的nonce是不一样的。返回的nonce是本次Salsa20加密所用的nonce，而json里的nonce就是保证每次的json数据都不同而已

而对于decrypt，其接受的数据格式就是encrypt的密文格式。在接收到输入后，会先按照格式拆分出nonce、checksum和ciphertext，然后会依次执行下面的步骤：

用nonce和KEY初始化Salsa20加密器
用Salsa20加密器对ciphertext进行解密，得到plaintext
检查plaintext的crc32值是否与checksum相等，不相等则返回
用json加载plaintext，从中取出user和command
如果user为root，且command为flag，则得到flag

步骤就到这里结束了。

首先就是Salsa20之前完全没了解过，搜索一下发现是一种流密码。也就是说给定KEY和nonce，Salsa20会以某种方式产生密钥流，然后与明文加密就得到最终密文。这也就是说，对于同样的KEY和nonce，产生的密钥流也是一样的。

而要利用run_command解密之前，肯定首先是要加密一次的，这样才能获取nonce从而得到完全一样的密钥流。然而对于加密，我们唯一能输入的是长为3的command，也就是不能输入flag，并且user也不能改为root，此外最后的json里的nonce每次加密都是随机产生的，也未知，就更没办法计算出crc32的值了。

但是处理方法也很简单，由于密钥流确定，所以我们可以随意篡改每次data的任意字节和长度，也就是说，我就输入fla作为command，那么我得到的ciphertext是对下面这段json的加密：

1	{'user': 'user', 'command': 'fla', 'nonce': xxxxxxxxxxxxxxxx}

那么直接用下面这段json作为target：

1	{"user": "root", "command": "flag"}

与上面密文的对应长度做异或就得到diff，然后把ciphertext异或上这段diff并送回去解密就可以了，checksum直接对这段target做crc32就行。

exp：

from Crypto.Util.number import *
from pwn import *
from zlib import crc32

sh = remote("tango.chal.imaginaryctf.org", 1337)

sh.sendline(b"E")
sh.recvuntil(b'Your command: ')
sh.sendline(b"fla")
sh.recvuntil(b"Your encrypted packet is: ")
packet = bytes.fromhex(sh.recvline().strip().decode())
nonce, checksum, ciphertext = packet[:8], bytes_to_long(packet[8:12]), packet[12:]
target = b'{"user": "root", "command": "flag"}'
now =    b'{"user": "user", "command": "fla", "nonce": "0000000000000000"}'
diff = xor(target,now[:len(target)])


sh.sendline(b"R")
sh.recvuntil(b'Your encrypted packet (hex): ')
my_checksum = long_to_bytes(crc32(target))
my_packet = nonce + my_checksum + xor(ciphertext[:len(target)],diff)
sh.sendline(my_packet.hex().encode())
print(sh.recvline())


#ictf{F0xtr0t_L1m4_4lph4_G0lf}

solitude

题目描述：

1	The best thinking has been done in solitude. The worst has been done in turmoil.

题目：

#!/usr/bin/env python3

import random

def xor(a: bytes, b: bytes):
  out = []
  for m,n in zip(a,b):
    out.append(m^n)
  return bytes(out)

class RNG():
  def __init__(self, size, state=None):
    self.size = size
    self.state = list(range(self.size+2))
    random.shuffle(self.state)
  def next(self):
    idx = self.state.index(self.size)
    self.state.pop(idx)
    self.state.insert((idx+1) % (len(self.state)+1), self.size)
    if self.state[0] == self.size:
      self.state.pop(0)
      self.state.insert(1, self.size)
    idx = self.state.index(self.size+1)
    self.state.pop(idx)
    self.state.insert((idx+1) % (len(self.state)+1), self.size+1)
    if self.state[0] == self.size+1:
      self.state.pop(0)
      self.state.insert(1, self.size+1)
    if self.state[1] == self.size+1:
      self.state.pop(1)
      self.state.insert(2, self.size+1)
    c1 = self.state.index(self.size)
    c2 = self.state.index(self.size+1)
    self.state = self.state[max(c1,c2)+1:] + [self.size if c1<c2 else self.size+1] + self.state[min(c1,c2)+1:max(c1,c2)] + [self.size if c1>c2 else self.size+1] + self.state[:min(c1,c2)]
    count = self.state[-1]
    if count in [self.size,self.size+1]:
      count = self.size
    self.state = self.state[count:-1] + self.state[:count] + self.state[-1:]
    idx = self.state[0]
    if idx in [self.size,self.size+1]:
      idx = self.size
    out = self.state[idx]
    if out in [self.size,self.size+1]:
      out = self.next()
    return out

if __name__ == "__main__":
  flag = open("flag.txt", "rb").read()
  while True:
    i = int(input("got flag? "))
    for _ in range(i):
      rng = RNG(128)
      stream = bytes([rng.next() for _ in range(len(flag))])
      print(xor(flag, stream).hex())

相当杂乱的一个RNG，大致来说是把0-129这些数字按某种方式每次选出一个，然后这些数字就组成了密钥流与flag异或。

其中，可以输入i来指定次数，每次会重新生成一个RNG并开始产生密钥流。次数多大都可以，目的是还原flag。

由于这个RNG感觉实在是太乱了，所以我先放弃理解直接上手试了试他的统计特性，结果发现一个结果：0这个数字几乎百分百在每个新RNG的前64个数字中最少出现一次。

直观一点用代码表示这个特征就是：

res = []
for i in range(1000):
    rng = RNG(128)
    res += [rng.next() for i in range(64)]
print(Counter(res).most_common(10))

得到结果：

1	[(0, 996), (93, 546), (106, 542), (112, 539), (32, 534), (44, 533), (99, 530), (91, 530), (61, 528), (49, 527)]

而剩下的之所以都是500次多一点，是因为除了0以外，所有数字出现概率较为随机，也就是有大约64/128的概率出现在密钥流的前64个之中。

虽然实际上flag长度是32，但是0“更容易出现在一个新RNG的前面”这个特点是不会改变的，所以光解题来说就很容易，由于所有flag字符都与0异或的最多，所以只需要发一个很大的i过去，统计出现次数最多的也就是flag字符。

exp：

from pwn import *
from collections import Counter

sh = remote("solitude.chal.imaginaryctf.org",1337)
sh.recvuntil(b"got flag? ")
sh.sendline(b"10000")

res = []
for i in range(10000):
    res.append(bytes.fromhex(sh.recvline().strip().decode()))

flag = b""
for j in range(32):
    temp = b""
    for i in range(10000):
        temp += chr(res[i][j]).encode()
    flag += chr(Counter(temp).most_common(1)[0][0]).encode()

print(flag)


#ictf{biased_rng_so_sad_6b065f93}

做完之后写wp的时候决定深究一下原因，具体流程用叙述的话有点长，可以自己看看。主要来说这个RNG有这么几个特点：

数字有0-129，共130个
RNG只会产生0-127这128个数字
128、129这两个数字可以类比于“指针”的作用，他们在调控state如何变换

但即使这样做，还是太难看出有啥地方导致这种统计特性了，所以决定用删的方式来逐个判断一下是哪一部份在作怪，最终发现即使删成这样：

def next(self):
    c1 = self.state.index(self.size)
    c2 = self.state.index(self.size+1)
    self.state = self.state[max(c1,c2)+1:] + [self.size if c1<c2 else self.size+1] + self.state[min(c1,c2)+1:max(c1,c2)] + [self.size if c1>c2 else self.size+1] + self.state[:min(c1,c2)]
    count = self.state[-1]    
    self.state = self.state[count:-1] + self.state[:count] + self.state[-1:]
    idx = self.state[0]
    out = self.state[idx]
    return out

统计特性依然存在，并且发现前面总结的规律并不正确，0并不是在前面的位置出现概率大，而是在所有位置出现概率都更大。

但是还是没看明白为啥就有这个规律了，先放着吧TT。

lf3r

题目描述：

1	LFSR's weakness comes from its linearity, so I come up with a new way to make it non-linear. Can you help me analyze it?

题目：

import secrets, os

n = 256
MASK = 0x560074275752B31E43E64E99D996BC7B5A8A3DAC8B472FE3B83E6C6DDB5A26E7


class LF3R:
    def __init__(self, n, key, mask):
        self.n = n
        self.state = key & ((1 << n) - 1)
        self.mask = mask

    def __call__(self):
        v = self.state % 3
        self.state = (self.state >> 1) | (
            ((self.state & self.mask).bit_count() & 1) << (self.n - 1)
        )
        return v


def int_to_base(n, b):
    digits = []
    while n:
        digits.append(n % b)
        n //= b
    return digits


if __name__ == "__main__":
    key = secrets.randbits(n)
    lf3r = LF3R(n, key, MASK)

    stream = [lf3r() for _ in range(2048)]

    flag = os.environ["FLAG"].encode()
    flag_digits = int_to_base(int.from_bytes(flag, "big"), 3)
    stream += [(x + lf3r()) % 3 for x in flag_digits]
    print(f"{stream = }")

output.txt：

stream = [2, 2, 0, 1, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 2, 2, 1, 1, 2, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2, 1, 0, 1, 0, 1, 0, 0, 0, 2, 2, 2, 0, 2, 1, 2, 0, 1, 1, 2, 1, 0, 0, 0, 0, 0, 2, 1, 2, 1, 2, 2, 1, 2, 2, 2, 2, 1, 0, 1, 0, 1, 0, 1, 2, 1, 2, 2, 1, 0, 0, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 1, 2, 0, 2, 2, 1, 2, 1, 1, 2, 1, 1, 0, 1, 1, 0, 2, 0, 2, 1, 2, 1, 2, 0, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 0, 0, 2, 0, 0, 1, 2, 0, 2, 0, 1, 0, 2, 2, 1, 1, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 1, 1, 0, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 0, 0, 2, 1, 1, 1, 1, 2, 0, 0, 1, 2, 1, 2, 2, 1, 1, 1, 2, 1, 0, 0, 1, 0, 0, 2, 0, 2, 2, 1, 1, 2, 1, 2, 0, 2, 0, 1, 1, 1, 2, 1, 1, 0, 0, 0, 2, 2, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 2, 2, 1, 2, 1, 2, 0, 0, 0, 2, 1, 1, 2, 1, 1, 2, 1, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 2, 1, 0, 2, 0, 2, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 0, 2, 1, 2, 0, 2, 1, 1, 0, 1, 2, 0, 1, 2, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 2, 0, 1, 1, 2, 0, 2, 1, 1, 2, 1, 2, 0, 0, 1, 2, 2, 1, 2, 1, 1, 2, 1, 0, 2, 2, 2, 1, 1, 2, 2, 2, 0, 0, 1, 2, 0, 0, 0, 1, 2, 2, 2, 2, 2, 0, 1, 2, 1, 0, 2, 0, 1, 0, 0, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 0, 1, 2, 1, 2, 0, 0, 2, 2, 1, 2, 1, 1, 0, 2, 1, 0, 1, 1, 1, 0, 0, 1, 1, 2, 0, 1, 0, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 0, 1, 2, 1, 2, 2, 2, 0, 0, 0, 0, 2, 1, 0, 1, 2, 2, 1, 0, 2, 1, 1, 2, 1, 2, 0, 0, 0, 0, 0, 1, 2, 1, 2, 0, 1, 2, 1, 1, 2, 1, 2, 1, 0, 2, 2, 2, 1, 2, 0, 2, 1, 1, 1, 0, 1, 1, 2, 2, 1, 2, 2, 2, 1, 0, 1, 2, 2, 1, 2, 0, 0, 0, 0, 0, 2, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 0, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 0, 0, 1, 0, 0, 2, 1, 2, 0, 0, 0, 1, 0, 1, 2, 1, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 1, 2, 1, 1, 0, 0, 2, 2, 0, 1, 2, 0, 0, 0, 0, 0, 2, 2, 0, 0, 1, 1, 2, 1, 1, 1, 0, 0, 2, 1, 2, 1, 0, 0, 0, 2, 2, 0, 1, 1, 1, 2, 1, 2, 0, 0, 1, 2, 1, 2, 1, 0, 2, 0, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 0, 2, 1, 0, 0, 1, 0, 1, 0, 1, 1, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 0, 2, 2, 1, 2, 0, 0, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 0, 0, 1, 0, 1, 2, 2, 1, 2, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 2, 0, 2, 0, 2, 1, 1, 2, 0, 0, 1, 2, 1, 0, 0, 0, 2, 2, 1, 2, 1, 0, 0, 2, 1, 1, 0, 1, 2, 0, 2, 0, 0, 2, 0, 2, 1, 0, 0, 0, 1, 0, 2, 0, 1, 2, 0, 2, 0, 0, 2, 1, 1, 1, 0, 0, 0, 1, 2, 1, 1, 0, 2, 1, 2, 1, 0, 1, 0, 0, 0, 1, 2, 0, 1, 2, 0, 0, 0, 1, 2, 1, 2, 0, 2, 1, 0, 0, 2, 2, 1, 1, 0, 0, 2, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 0, 1, 1, 0, 0, 2, 1, 1, 1, 2, 0, 0, 1, 1, 0, 2, 2, 1, 0, 2, 1, 2, 1, 2, 0, 2, 1, 1, 1, 0, 0, 1, 2, 2, 2, 1, 0, 0, 1, 2, 1, 1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 2, 1, 2, 1, 0, 2, 2, 0, 1, 1, 1, 1, 1, 2, 2, 0, 1, 2, 1, 0, 1, 1, 1, 2, 1, 0, 1, 1, 0, 0, 1, 2, 1, 1, 2, 0, 2, 0, 2, 1, 2, 2, 0, 0, 2, 1, 0, 1, 0, 2, 2, 1, 2, 2, 2, 0, 0, 0, 0, 2, 1, 0, 0, 1, 1, 0, 1, 1, 2, 2, 1, 0, 0, 0, 2, 2, 2, 1, 2, 1, 0, 2, 0, 0, 2, 2, 0, 2, 1, 1, 1, 0, 0, 1, 2, 0, 1, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 2, 0, 0, 1, 2, 1, 2, 2, 0, 1, 0, 0, 1, 1, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 1, 2, 1, 2, 1, 2, 0, 1, 2, 1, 0, 2, 0, 0, 2, 1, 2, 2, 1, 0, 1, 2, 2, 0, 0, 2, 0, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 1, 2, 2, 0, 1, 2, 0, 2, 1, 2, 2, 1, 0, 0, 0, 0, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 2, 2, 0, 0, 0, 2, 2, 0, 0, 2, 1, 1, 2, 1, 0, 0, 0, 0, 1, 0, 1, 0, 2, 2, 0, 2, 0, 2, 0, 2, 2, 1, 2, 2, 2, 1, 0, 0, 0, 0, 2, 1, 2, 1, 2, 2, 1, 2, 0, 1, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 2, 1, 2, 1, 1, 2, 1, 0, 0, 2, 0, 1, 1, 0, 0, 1, 0, 0, 2, 1, 0, 1, 0, 0, 1, 2, 1, 1, 2, 2, 0, 2, 1, 2, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 2, 2, 0, 2, 1, 2, 2, 2, 1, 1, 0, 1, 0, 2, 1, 2, 0, 0, 2, 2, 1, 0, 1, 2, 0, 0, 0, 0, 1, 2, 1, 2, 2, 0, 0, 0, 0, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 0, 0, 0, 0, 1, 2, 1, 1, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 1, 1, 2, 0, 2, 2, 0, 1, 0, 2, 1, 0, 0, 0, 1, 2, 2, 0, 2, 1, 2, 2, 1, 0, 2, 1, 2, 1, 0, 0, 0, 0, 0, 1, 2, 1, 0, 2, 1, 1, 0, 0, 2, 0, 0, 0, 1, 1, 2, 1, 0, 2, 1, 2, 1, 2, 2, 1, 0, 0, 1, 2, 1, 2, 0, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 0, 0, 0, 2, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 1, 2, 1, 0, 0, 0, 2, 2, 1, 1, 1, 1, 0, 0, 2, 1, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 1, 2, 0, 2, 1, 2, 2, 2, 2, 1, 1, 1, 2, 0, 0, 0, 1, 2, 0, 0, 1, 1, 0, 1, 2, 0, 1, 0, 0, 1, 0, 2, 1, 1, 2, 0, 0, 1, 2, 0, 0, 2, 1, 2, 1, 0, 0, 2, 1, 2, 0, 0, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 2, 0, 0, 0, 0, 1, 2, 2, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 1, 0, 2, 1, 2, 1, 2, 0, 2, 1, 0, 0, 1, 2, 1, 2, 0, 0, 0, 0, 2, 1, 2, 2, 2, 1, 2, 0, 0, 0, 2, 1, 2, 1, 0, 1, 2, 1, 0, 2, 1, 2, 0, 0, 0, 1, 0, 0, 0, 0, 2, 2, 0, 0, 1, 2, 1, 0, 1, 1, 2, 1, 2, 1, 0, 2, 1, 0, 0, 1, 2, 1, 2, 0, 0, 1, 2, 2, 0, 1, 2, 0, 1, 0, 0, 0, 0, 0, 1, 2, 1, 1, 2, 1, 0, 0, 1, 2, 1, 0, 0, 2, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 2, 1, 2, 0, 0, 1, 2, 1, 2, 0, 0, 1, 2, 1, 0, 2, 0, 0, 2, 1, 1, 2, 2, 1, 1, 0, 2, 1, 0, 1, 1, 2, 2, 1, 2, 0, 0, 0, 1, 1, 1, 1, 0, 0, 2, 2, 1, 2, 1, 1, 0, 0, 1, 1, 2, 1, 2, 0, 0, 1, 0, 2, 1, 2, 2, 0, 1, 0, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 0, 2, 1, 2, 1, 2, 1, 2, 0, 1, 0, 1, 0, 1, 0, 2, 1, 2, 1, 2, 1, 2, 1, 0, 1, 2, 1, 0, 0, 1, 2, 2, 1, 0, 0, 0, 0, 0, 2, 2, 1, 2, 0, 1, 0, 0, 1, 1, 2, 1, 2, 0, 0, 0, 2, 1, 0, 0, 1, 2, 2, 0, 0, 0, 1, 0, 2, 2, 1, 1, 2, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 2, 1, 2, 0, 0, 0, 1, 2, 1, 2, 1, 0, 0, 0, 2, 0, 2, 1, 0, 1, 1, 2, 1, 1, 2, 0, 2, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 1, 2, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 2, 2, 1, 1, 2, 1, 0, 1, 1, 2, 1, 2, 0, 1, 2, 1, 2, 1, 2, 0, 0, 2, 0, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 0, 2, 1, 0, 0, 2, 0, 2, 1, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 2, 1, 2, 0, 2, 1, 1, 0, 0, 2, 0, 1, 2, 0, 0, 1, 2, 0, 0, 0, 0, 1, 2, 1, 0, 1, 1, 0, 0, 0, 1, 2, 2, 1, 0, 2, 0, 2, 1, 2, 0, 2, 1, 2, 1, 1, 0, 2, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 1, 0, 0, 0, 1, 1, 2, 0, 1, 1, 2, 0, 0, 0, 2, 1, 1, 1, 2, 0, 1, 0, 0, 2, 1, 0, 0, 0, 0, 2, 2, 0, 2, 1, 0, 0, 0, 2, 1, 2, 1, 2, 1, 2, 0, 0, 2, 1, 1, 1, 2, 2, 0, 2, 1, 2, 0, 2, 0, 2, 1, 0, 0, 0, 0, 2, 1, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1, 2, 0, 2, 1, 1, 2, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 2, 0, 1, 1, 1, 2, 1, 0, 2, 1, 0, 0, 1, 1, 1, 1, 0, 1, 2, 0, 0, 2, 2, 0, 0, 1, 1, 0, 0, 2, 2, 2, 0, 0, 0, 2, 2, 0, 2, 0, 2, 2, 0, 2, 1, 2, 2, 2, 0, 2, 1, 1, 1, 0, 2, 0, 0, 0, 1, 0, 2, 2, 0, 1, 0, 2, 1, 2, 2, 1, 0, 0, 1, 0, 2, 0, 2, 1, 0, 2, 0, 2, 2, 1, 0, 0, 0, 0, 2, 2, 2, 0, 2, 2, 1, 0, 0, 0, 2, 1, 1, 1, 0, 2, 2, 0, 2, 0, 2, 1, 0, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 0, 2, 2, 2, 2, 2, 1, 2, 1, 0, 1, 0, 1, 0, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 2, 0, 1, 2, 1, 0, 2, 0, 0, 2, 0, 2, 0, 1, 0, 0, 1, 2, 2, 2, 0, 1, 2, 1, 0, 0, 1, 1, 2, 0, 1, 1, 0, 2, 1, 0, 2, 2, 2, 0, 1, 2, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 2, 0, 1, 2, 0, 0, 0, 2, 0, 0, 1, 1, 1, 0, 2, 1, 2, 2, 2, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 2, 1, 2, 0, 1, 2, 0, 1, 2, 1, 2, 2, 1, 2, 0]

这题自己做的时候路走偏了，感觉挺麻烦，但rec一来就给出了正解。

题目基于一个已知mask，未知初始state的LFSR递推。然而一个特殊的地方在于，每次递推之后给的并不是产生的二进制位，而是当前state模3的值。给出2048组数据，要求能够继续向后预测LFSR的递推过程，从而还原flag。

首先明确一个事情，就是LFSR依然完完全全在模2下递推，仅仅是给出的值是整个当前state在模3下的，这才使得整个系统显得不那么线性。那么不妨假设第一次递推前，也就是初始状态的256个bit为

$(s_0,s_1,s_2,...,s_{255})$

那么这个state对应的256bit的整数是：

$state_0 = 2^{255}s_0 + 2^{254}s_1 + ... + 2^{1}s_{254} + 2^0s_{255}$

而如果把2模3看作是等于-1的话，那么整个式子模3就变成了：

$state_0 = (-1)^{255}s_0 + (-1)^{254}s_1 + ... + (-1)^{1}s_{254} + (-1)^0s_{255}$

也就等价于：

$state_0 = -s_0 + s_1 + ... - s_{254} + s_{255}$

而下一个state也就是：

$state_1 = -s_1 + s_2 + ... - s_{255} + s_{256}$

然后把这两个相加就可以消去绝大部分项：

$state_0 + state_1 = s_{256} - s_0$

此时注意，由于s256和s0都是一个二进制位，所以相减的取值仅有-1，0，1三种情况(-1也就对应2)。可以看出，当相减取值为1或-1时，就可以确定下两个bit的值分别为1、0和0、1，所以搜集足够的比特位就可以解线性方程得到初始state了。

exp：

from Crypto.Util.number import *

n = 256
MASK = 0x560074275752B31E43E64E99D996BC7B5A8A3DAC8B472FE3B83E6C6DDB5A26E7
stream = [2, 2, 0, 1, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 2, 2, 1, 1, 2, 1, 0, 0, 1, 0, 0, 0, 0, 1, 2, 1, 0, 1, 0, 1, 0, 0, 0, 2, 2, 2, 0, 2, 1, 2, 0, 1, 1, 2, 1, 0, 0, 0, 0, 0, 2, 1, 2, 1, 2, 2, 1, 2, 2, 2, 2, 1, 0, 1, 0, 1, 0, 1, 2, 1, 2, 2, 1, 0, 0, 1, 2, 1, 2, 2, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 1, 2, 0, 2, 2, 1, 2, 1, 1, 2, 1, 1, 0, 1, 1, 0, 2, 0, 2, 1, 2, 1, 2, 0, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 0, 0, 2, 0, 0, 1, 2, 0, 2, 0, 1, 0, 2, 2, 1, 1, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 1, 1, 0, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 0, 0, 2, 1, 1, 1, 1, 2, 0, 0, 1, 2, 1, 2, 2, 1, 1, 1, 2, 1, 0, 0, 1, 0, 0, 2, 0, 2, 2, 1, 1, 2, 1, 2, 0, 2, 0, 1, 1, 1, 2, 1, 1, 0, 0, 0, 2, 2, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 2, 2, 1, 2, 1, 2, 0, 0, 0, 2, 1, 1, 2, 1, 1, 2, 1, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 2, 1, 0, 2, 0, 2, 1, 1, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 2, 0, 2, 1, 2, 0, 2, 1, 1, 0, 1, 2, 0, 1, 2, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 2, 2, 0, 0, 0, 0, 0, 2, 0, 1, 1, 2, 0, 2, 1, 1, 2, 1, 2, 0, 0, 1, 2, 2, 1, 2, 1, 1, 2, 1, 0, 2, 2, 2, 1, 1, 2, 2, 2, 0, 0, 1, 2, 0, 0, 0, 1, 2, 2, 2, 2, 2, 0, 1, 2, 1, 0, 2, 0, 1, 0, 0, 2, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 0, 1, 2, 1, 2, 0, 0, 2, 2, 1, 2, 1, 1, 0, 2, 1, 0, 1, 1, 1, 0, 0, 1, 1, 2, 0, 1, 0, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 0, 1, 2, 1, 2, 2, 2, 0, 0, 0, 0, 2, 1, 0, 1, 2, 2, 1, 0, 2, 1, 1, 2, 1, 2, 0, 0, 0, 0, 0, 1, 2, 1, 2, 0, 1, 2, 1, 1, 2, 1, 2, 1, 0, 2, 2, 2, 1, 2, 0, 2, 1, 1, 1, 0, 1, 1, 2, 2, 1, 2, 2, 2, 1, 0, 1, 2, 2, 1, 2, 0, 0, 0, 0, 0, 2, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 0, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 0, 0, 1, 0, 0, 2, 1, 2, 0, 0, 0, 1, 0, 1, 2, 1, 0, 0, 0, 0, 0, 1, 2, 1, 0, 0, 0, 0, 0, 1, 2, 1, 1, 0, 0, 2, 2, 0, 1, 2, 0, 0, 0, 0, 0, 2, 2, 0, 0, 1, 1, 2, 1, 1, 1, 0, 0, 2, 1, 2, 1, 0, 0, 0, 2, 2, 0, 1, 1, 1, 2, 1, 2, 0, 0, 1, 2, 1, 2, 1, 0, 2, 0, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 2, 0, 2, 1, 0, 0, 1, 0, 1, 0, 1, 1, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 0, 2, 2, 1, 2, 0, 0, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 0, 0, 1, 0, 1, 2, 2, 1, 2, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 2, 0, 2, 0, 2, 1, 1, 2, 0, 0, 1, 2, 1, 0, 0, 0, 2, 2, 1, 2, 1, 0, 0, 2, 1, 1, 0, 1, 2, 0, 2, 0, 0, 2, 0, 2, 1, 0, 0, 0, 1, 0, 2, 0, 1, 2, 0, 2, 0, 0, 2, 1, 1, 1, 0, 0, 0, 1, 2, 1, 1, 0, 2, 1, 2, 1, 0, 1, 0, 0, 0, 1, 2, 0, 1, 2, 0, 0, 0, 1, 2, 1, 2, 0, 2, 1, 0, 0, 2, 2, 1, 1, 0, 0, 2, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 0, 1, 1, 0, 0, 2, 1, 1, 1, 2, 0, 0, 1, 1, 0, 2, 2, 1, 0, 2, 1, 2, 1, 2, 0, 2, 1, 1, 1, 0, 0, 1, 2, 2, 2, 1, 0, 0, 1, 2, 1, 1, 0, 0, 2, 0, 0, 0, 0, 0, 0, 2, 1, 2, 1, 0, 2, 2, 0, 1, 1, 1, 1, 1, 2, 2, 0, 1, 2, 1, 0, 1, 1, 1, 2, 1, 0, 1, 1, 0, 0, 1, 2, 1, 1, 2, 0, 2, 0, 2, 1, 2, 2, 0, 0, 2, 1, 0, 1, 0, 2, 2, 1, 2, 2, 2, 0, 0, 0, 0, 2, 1, 0, 0, 1, 1, 0, 1, 1, 2, 2, 1, 0, 0, 0, 2, 2, 2, 1, 2, 1, 0, 2, 0, 0, 2, 2, 0, 2, 1, 1, 1, 0, 0, 1, 2, 0, 1, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 2, 0, 0, 1, 2, 1, 2, 2, 0, 1, 0, 0, 1, 1, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 2, 0, 0, 0, 1, 2, 1, 2, 1, 2, 0, 1, 2, 1, 0, 2, 0, 0, 2, 1, 2, 2, 1, 0, 1, 2, 2, 0, 0, 2, 0, 1, 1, 1, 2, 0, 0, 0, 0, 0, 0, 0, 1, 2, 1, 2, 1, 1, 2, 2, 0, 1, 2, 0, 2, 1, 2, 2, 1, 0, 0, 0, 0, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 2, 2, 0, 0, 0, 2, 2, 0, 0, 2, 1, 1, 2, 1, 0, 0, 0, 0, 1, 0, 1, 0, 2, 2, 0, 2, 0, 2, 0, 2, 2, 1, 2, 2, 2, 1, 0, 0, 0, 0, 2, 1, 2, 1, 2, 2, 1, 2, 0, 1, 1, 0, 2, 1, 0, 1, 0, 2, 1, 0, 2, 1, 2, 1, 1, 2, 1, 0, 0, 2, 0, 1, 1, 0, 0, 1, 0, 0, 2, 1, 0, 1, 0, 0, 1, 2, 1, 1, 2, 2, 0, 2, 1, 2, 0, 0, 0, 2, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 2, 1, 2, 2, 0, 2, 1, 2, 2, 2, 1, 1, 0, 1, 0, 2, 1, 2, 0, 0, 2, 2, 1, 0, 1, 2, 0, 0, 0, 0, 1, 2, 1, 2, 2, 0, 0, 0, 0, 1, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 0, 0, 0, 0, 1, 2, 1, 1, 2, 1, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 1, 0, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 1, 1, 2, 0, 2, 2, 0, 1, 0, 2, 1, 0, 0, 0, 1, 2, 2, 0, 2, 1, 2, 2, 1, 0, 2, 1, 2, 1, 0, 0, 0, 0, 0, 1, 2, 1, 0, 2, 1, 1, 0, 0, 2, 0, 0, 0, 1, 1, 2, 1, 0, 2, 1, 2, 1, 2, 2, 1, 0, 0, 1, 2, 1, 2, 0, 2, 1, 2, 1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 0, 0, 0, 2, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 1, 2, 1, 0, 0, 0, 2, 2, 1, 1, 1, 1, 0, 0, 2, 1, 0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 1, 2, 0, 2, 1, 2, 2, 2, 2, 1, 1, 1, 2, 0, 0, 0, 1, 2, 0, 0, 1, 1, 0, 1, 2, 0, 1, 0, 0, 1, 0, 2, 1, 1, 2, 0, 0, 1, 2, 0, 0, 2, 1, 2, 1, 0, 0, 2, 1, 2, 0, 0, 2, 1, 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 2, 0, 0, 0, 0, 1, 2, 2, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 1, 0, 2, 1, 2, 1, 2, 0, 2, 1, 0, 0, 1, 2, 1, 2, 0, 0, 0, 0, 2, 1, 2, 2, 2, 1, 2, 0, 0, 0, 2, 1, 2, 1, 0, 1, 2, 1, 0, 2, 1, 2, 0, 0, 0, 1, 0, 0, 0, 0, 2, 2, 0, 0, 1, 2, 1, 0, 1, 1, 2, 1, 2, 1, 0, 2, 1, 0, 0, 1, 2, 1, 2, 0, 0, 1, 2, 2, 0, 1, 2, 0, 1, 0, 0, 0, 0, 0, 1, 2, 1, 1, 2, 1, 0, 0, 1, 2, 1, 0, 0, 2, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 2, 1, 2, 0, 0, 1, 2, 1, 2, 0, 0, 1, 2, 1, 0, 2, 0, 0, 2, 1, 1, 2, 2, 1, 1, 0, 2, 1, 0, 1, 1, 2, 2, 1, 2, 0, 0, 0, 1, 1, 1, 1, 0, 0, 2, 2, 1, 2, 1, 1, 0, 0, 1, 1, 2, 1, 2, 0, 0, 1, 0, 2, 1, 2, 2, 0, 1, 0, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 0, 2, 1, 2, 1, 2, 1, 2, 0, 1, 0, 1, 0, 1, 0, 2, 1, 2, 1, 2, 1, 2, 1, 0, 1, 2, 1, 0, 0, 1, 2, 2, 1, 0, 0, 0, 0, 0, 2, 2, 1, 2, 0, 1, 0, 0, 1, 1, 2, 1, 2, 0, 0, 0, 2, 1, 0, 0, 1, 2, 2, 0, 0, 0, 1, 0, 2, 2, 1, 1, 2, 2, 1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 2, 1, 2, 0, 0, 0, 1, 2, 1, 2, 1, 0, 0, 0, 2, 0, 2, 1, 0, 1, 1, 2, 1, 1, 2, 0, 2, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 1, 2, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 2, 2, 1, 1, 2, 1, 0, 1, 1, 2, 1, 2, 0, 1, 2, 1, 2, 1, 2, 0, 0, 2, 0, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 0, 2, 1, 0, 0, 2, 0, 2, 1, 0, 0, 0, 0, 0, 2, 1, 0, 0, 0, 2, 1, 2, 0, 2, 1, 1, 0, 0, 2, 0, 1, 2, 0, 0, 1, 2, 0, 0, 0, 0, 1, 2, 1, 0, 1, 1, 0, 0, 0, 1, 2, 2, 1, 0, 2, 0, 2, 1, 2, 0, 2, 1, 2, 1, 1, 0, 2, 0, 0, 0, 0, 0, 1, 1, 2, 2, 2, 2, 1, 0, 0, 0, 1, 1, 2, 0, 1, 1, 2, 0, 0, 0, 2, 1, 1, 1, 2, 0, 1, 0, 0, 2, 1, 0, 0, 0, 0, 2, 2, 0, 2, 1, 0, 0, 0, 2, 1, 2, 1, 2, 1, 2, 0, 0, 2, 1, 1, 1, 2, 2, 0, 2, 1, 2, 0, 2, 0, 2, 1, 0, 0, 0, 0, 2, 1, 1, 0, 1, 1, 1, 2, 2, 0, 2, 1, 2, 0, 2, 1, 1, 2, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 2, 0, 1, 1, 1, 2, 1, 0, 2, 1, 0, 0, 1, 1, 1, 1, 0, 1, 2, 0, 0, 2, 2, 0, 0, 1, 1, 0, 0, 2, 2, 2, 0, 0, 0, 2, 2, 0, 2, 0, 2, 2, 0, 2, 1, 2, 2, 2, 0, 2, 1, 1, 1, 0, 2, 0, 0, 0, 1, 0, 2, 2, 0, 1, 0, 2, 1, 2, 2, 1, 0, 0, 1, 0, 2, 0, 2, 1, 0, 2, 0, 2, 2, 1, 0, 0, 0, 0, 2, 2, 2, 0, 2, 2, 1, 0, 0, 0, 2, 1, 1, 1, 0, 2, 2, 0, 2, 0, 2, 1, 0, 1, 2, 1, 1, 2, 1, 1, 1, 2, 1, 1, 0, 2, 2, 2, 2, 2, 1, 2, 1, 0, 1, 0, 1, 0, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 2, 0, 1, 2, 1, 0, 2, 0, 0, 2, 0, 2, 0, 1, 0, 0, 1, 2, 2, 2, 0, 1, 2, 1, 0, 0, 1, 1, 2, 0, 1, 1, 0, 2, 1, 0, 2, 2, 2, 0, 1, 2, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 2, 0, 1, 2, 0, 0, 0, 2, 0, 0, 1, 1, 1, 0, 2, 1, 2, 2, 2, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 2, 1, 2, 0, 1, 2, 0, 1, 2, 1, 2, 2, 1, 2, 0]


############################################### part1 get init_state
def construct_matrix(n, MASK):
    L = Matrix(GF(2),n,n)
    for i in range(n-1):
        L[i,i+1] = 1
    for i in range(n):
        L[-1,i] = (MASK >> i) & 1
    return L

L = construct_matrix(n, MASK)
idx = 0
T = Matrix(GF(2),identity_matrix(n))
A = []
b = []
while(1):
    if((stream[idx] + stream[idx+1]) % 3 == 2):
        A.append(T[0])
        b.append(0)
    elif((stream[idx] + stream[idx+1]) % 3 == 1):
        A.append(T[0])
        b.append(1)
    T *= L
    idx += 1
    if(len(b) == n or idx == 2048-1):
        A = Matrix(GF(2),A)
        b = vector(GF(2),b)
        break
init_state = A.solve_right(b)[::-1]


############################################### part2 get flag
class LF3R:
    def __init__(self, n, key, mask):
        self.n = n
        self.state = key & ((1 << n) - 1)
        self.mask = mask

    def __call__(self):
        v = self.state % 3
        self.state = (self.state >> 1) | (
            (bin(self.state & self.mask).count("1") & 1) << (self.n - 1)
        )
        return v

key = int("".join(map(str,init_state)),2)
lf3r = LF3R(n, key, MASK)
[lf3r() for i in range(2048)]
flag = ""
for i in range(len(stream)-2048):
    flag += str((stream[2048+i] - lf3r()) % 3)
print(long_to_bytes(int(flag[::-1],3)))


#ictf{mixing_modulus_is_really_annoying_right?}

coast

题目描述：

1	Isogeny cryptography seems so fun, so I build a new cryptosystem based on CSIDH.

题目：

from Crypto.Cipher import AES
from hashlib import sha256

proof.all(False)
# fmt: off
ls = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 929]
# fmt: on
p = 4 * product(ls) - 1
F = GF(p)
E0 = EllipticCurve(F, [1, 0])
G = E0.gen(0)
base = (E0, G)


def keygen():
    return [randint(-1, 1) for _ in range(len(ls))]


def exchange(pub, priv):
    E, G = pub
    es = priv[:]
    while any(es):
        s = +1 if randint(0, 1) else -1
        E.set_order(p + 1)
        P = E.random_point()
        k = prod(l for l, e in zip(ls, es) if sign(e) == s)
        P *= (p + 1) // k
        for i, (l, e) in enumerate(zip(ls, es)):
            if sign(e) != s:
                continue
            Q = k // l * P
            if not Q:
                continue
            Q.set_order(l)
            phi = E.isogeny(Q)
            E, P = phi.codomain(), phi(P)
            G = phi(G)
            es[i] -= s
            k //= l
    return E, G


def serialize_pub(pub):
    E, G = pub
    return (E.a4(), E.a6(), G[0], G[1])


with open("flag.txt", "rb") as f:
    flag = f.read().strip()

priv_alice = keygen()
priv_bob = keygen()
pub_alice = exchange(base, priv_alice)
pub_bob = exchange(base, priv_bob)
shared_1 = exchange(pub_alice, priv_bob)
shared_2 = exchange(pub_bob, priv_alice)
assert shared_1 == shared_2

shared_secret = int(shared_1[0].j_invariant() + shared_1[1][0])
key = sha256(str(shared_secret).encode()).digest()
cipher = AES.new(key, AES.MODE_CTR)
ct = cipher.encrypt(flag)
iv = cipher.nonce

base_ser = serialize_pub(base)
pub_alice_ser = serialize_pub(pub_alice)
pub_bob_ser = serialize_pub(pub_bob)

print(f"{base_ser = }")
print(f"{pub_alice_ser = }")
print(f"{pub_bob_ser = }")
print(f"{ct = }")
print(f"{iv = }")

output.txt：

base_ser = (1, 0, 6395576350626777292729821677181541606370191430555605995902296654660733787961884662675205008112728910627829097716240328518277343733654560980779031197383306195903192278996242667385893559502924064335660043910231897229406366701069814748813352528977494567341233293392314984276702732050363273792561347300313, 4989628161531004318153788074304291273577473031059606908412965124036974844963743869216684686020120111949770513589687750670438648526142795689802013040914101895565898055896213731473214310303864435287131739468789570598441615792162769805326802317670196010077382560220110366549259348962142078308153647899274)
pub_alice_ser = (16796745232047376431076025485853428113133878598097917003461887969217006498108008731966744769172838839455129087919415367459511356804735314320761042839383730282543236466692745670914654548112400401873112245614944913297758267192129423214055383555189748155309668519243823656843679941140887547541583677456851, 8963816826825107706757885015960152371166552220981896678339960705520861493163941960230523020894830135812851365288978634124277530779100695340287569755423459240568704426045331208533913128865584575359563263393253534547084448818884991750356771030230632199257310184446749944357247275509600739836829962695982, 5985363780131483127972578951676841809331634397976984954623788863861777364455401615121494127550821174942018761442458411590922907440513151315213076773138479058971335280960602464177689878904986723530962048747658113657305981717196234378352404797804042544442260172818264948952275310656449986193544911288998, 11649597127875537444034607923163754235537320890125543416303955671947999961428652169037025819875497760380019726767893160005005207635230495183159964997017269895171761165208635703481382384409333096255950930548560628238229917503014555866644994772105200770892341004064761100707021002853325553967825145390381)
pub_bob_ser = (11074315528506118650419974941868902144061087346415910875754699136651403897503986559271837685210876546003254210356095728661380015394250217544836232370667249236726866756134031525443480212922804350247920434230860777321021642812917870058468202706130234985660019235758626667794297106070003964360950607030598, 14788615576129160240974902210621158431820003187709942310686740894110660926275619991889339611525021308542253932884035960214935758630370400596713566372704518819883473808782054060292387578412174017604910767645236213465324157607253511970477802974564062325283523478550237024031582360283010701611159519365278, 14321992806289178321304756176419224025450932661291292547666237239861901427262601709081849960088644959294041693893090273529716185385414362311881174527793744440204632764863112487952716682577231240702585919349036909411205777137409147119242850872654694352308452421920098660171268727320418419754354531076628, 7538734401643277631776877448699813925331537292810845825274725479798688685992383653831671943669387620894416031681699814135234397288844079804264499920949132059399186790837118164550554056080958276489614279355615876249173470199144967698224721556194470026970595690830845832259388888940448493603599827181272)
ct = b'\x8a\x1cs\xa1\xb3\xa77\x81_:\x81\xf8\x83\xc3a\x17\xe1\xd9\xcb\x0c]\x9b\xebP\x06c\x85\x9de1\xeed\x91\x0f\x87_\xf9\x9bD\x7f\xf1\xbdD\x88P\x9eO\x04'
iv = b'\x94j;L,\xf3\xde\xc5'

这是一道基于CSIDH的密钥交换，先简要介绍一下CSIDH与SIDH主要有哪些不同：

CSIDH一般工作在由p-1光滑的素数的一次域上
Alice与Bob的私钥是一个指数列表，用来指示在每个p-1的奇素因子上进行同源移动的次数
由于是一次域，所有奇素数都只对应一个唯一的torsion，因此每个度数的同源均只有一个

也就是对于一个确定的曲线来说，经过一个度数确定的同源，一定会到达另一条确定的曲线，这个目的地有且仅有一个。且如果按相同的度数一直同源下去最后会走出一个循环。
一般是用最后到达的曲线的Montgomery form的系数A作为共享密钥，不过题目中是j不变量，应该也行

而经过测试可以发现这里的CSIDH本身密钥交换的实现就有问题，在指数为负数的时候根本没有利用quadratic twisted来倒着走，所以他的整个作为私钥的指数列表其实是完全没有负数这个概念的，完全等价于01列表(-1就等价于1)。此外，由于给了初始曲线E0的生成元G，且给出了经历双方私钥交换的$\phi_A(G)$和$\phi_B(G)$，注意到刚才说过同样的torsion只有一个，所以经历了一个度为k的同源后，生成元G的阶中因子k也会随之消失，就破坏了他作为生成元的特点。

一个简单但不太严谨的解释是，由于k-torsion作为同源的核，也就是说k-torsion中的所有点会映射到O，因此生成元的因子k自然就消失了

因此简单的遍历一下G的阶中因子是否还存在就可以求出双方的私钥了，之后进行错误的密钥交换即可。

exp：

from Crypto.Cipher import AES
from hashlib import sha256

# fmt: off
ls = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 929]
# fmt: on
p = 4 * product(ls) - 1
F = GF(p)
E0 = EllipticCurve(F, [1, 0])
G = E0.gen(0)
base = (E0, G)

def exchange(pub, priv):
    E, G = pub
    es = priv[:]
    while any(es):
        s = +1 if randint(0, 1) else -1
        E.set_order(p + 1)
        P = E.random_point()
        k = prod(l for l, e in zip(ls, es) if sign(e) == s)
        P *= (p + 1) // k
        for i, (l, e) in enumerate(zip(ls, es)):
            if sign(e) != s:
                continue
            Q = k // l * P
            if not Q:
                continue
            Q.set_order(l)
            phi = E.isogeny(Q)
            E, P = phi.codomain(), phi(P)
            G = phi(G)
            es[i] -= s
            k //= l
    return E, G

base_ser = (1, 0, 6395576350626777292729821677181541606370191430555605995902296654660733787961884662675205008112728910627829097716240328518277343733654560980779031197383306195903192278996242667385893559502924064335660043910231897229406366701069814748813352528977494567341233293392314984276702732050363273792561347300313, 4989628161531004318153788074304291273577473031059606908412965124036974844963743869216684686020120111949770513589687750670438648526142795689802013040914101895565898055896213731473214310303864435287131739468789570598441615792162769805326802317670196010077382560220110366549259348962142078308153647899274)
pub_alice_ser = (16796745232047376431076025485853428113133878598097917003461887969217006498108008731966744769172838839455129087919415367459511356804735314320761042839383730282543236466692745670914654548112400401873112245614944913297758267192129423214055383555189748155309668519243823656843679941140887547541583677456851, 8963816826825107706757885015960152371166552220981896678339960705520861493163941960230523020894830135812851365288978634124277530779100695340287569755423459240568704426045331208533913128865584575359563263393253534547084448818884991750356771030230632199257310184446749944357247275509600739836829962695982, 5985363780131483127972578951676841809331634397976984954623788863861777364455401615121494127550821174942018761442458411590922907440513151315213076773138479058971335280960602464177689878904986723530962048747658113657305981717196234378352404797804042544442260172818264948952275310656449986193544911288998, 11649597127875537444034607923163754235537320890125543416303955671947999961428652169037025819875497760380019726767893160005005207635230495183159964997017269895171761165208635703481382384409333096255950930548560628238229917503014555866644994772105200770892341004064761100707021002853325553967825145390381)
pub_bob_ser = (11074315528506118650419974941868902144061087346415910875754699136651403897503986559271837685210876546003254210356095728661380015394250217544836232370667249236726866756134031525443480212922804350247920434230860777321021642812917870058468202706130234985660019235758626667794297106070003964360950607030598, 14788615576129160240974902210621158431820003187709942310686740894110660926275619991889339611525021308542253932884035960214935758630370400596713566372704518819883473808782054060292387578412174017604910767645236213465324157607253511970477802974564062325283523478550237024031582360283010701611159519365278, 14321992806289178321304756176419224025450932661291292547666237239861901427262601709081849960088644959294041693893090273529716185385414362311881174527793744440204632764863112487952716682577231240702585919349036909411205777137409147119242850872654694352308452421920098660171268727320418419754354531076628, 7538734401643277631776877448699813925331537292810845825274725479798688685992383653831671943669387620894416031681699814135234397288844079804264499920949132059399186790837118164550554056080958276489614279355615876249173470199144967698224721556194470026970595690830845832259388888940448493603599827181272)
ct = b'\x8a\x1cs\xa1\xb3\xa77\x81_:\x81\xf8\x83\xc3a\x17\xe1\xd9\xcb\x0c]\x9b\xebP\x06c\x85\x9de1\xeed\x91\x0f\x87_\xf9\x9bD\x7f\xf1\xbdD\x88P\x9eO\x04'
iv = b'\x94j;L,\xf3\xde\xc5'


################################################################ solve
EA = EllipticCurve(F, [pub_alice_ser[0],pub_alice_ser[1]])
phiA_G = EA(pub_alice_ser[2],pub_alice_ser[3])
EB = EllipticCurve(F, [pub_bob_ser[0],pub_bob_ser[1]])
phiB_G = EB(pub_bob_ser[2],pub_bob_ser[3])


As = []
for i in ls:
    if(((p+1) // i)*phiA_G == EA(0)):
        As.append(1)
    else:
        As.append(0)

shared_1 = exchange((EB,phiB_G), As)
shared_secret = int(shared_1[0].j_invariant() + shared_1[1][0])
key = sha256(str(shared_secret).encode()).digest()
cipher = AES.new(key, AES.MODE_CTR, nonce=iv)
flag = cipher.decrypt(ct)
print(flag)


#ictf{just_a_very_broken_implementation_of_csidh}

lcasm$

二进制的，默认自己不会。

notitle*

题目描述：

1	The keys are obfuscated by a weird magic operation.

题目：

from sage.all import *
import os
from Crypto.Cipher import AES
from hashlib import sha512

proof.all(False)
p = 0x7AADA0BA1C05D63803BA6BCE66CB6BC091C7ADA62B5CB5BC9F924B528FC113971D4BC54C7FAF3C146ADEB0548BFB9258DFF316741266B802DD7A2F46F77593BAD983E6DF394C1519E8DB0130289FA5A9C628E3ABCE58C63B3379DB7088AAC7A40B63776959774B1B57B8FD316C650AE3C012A91EE653477443446050438A99E79B89B69745BD1918EECB08A0C9D45EF3C61639137F24D979FF380D65C7ABD08785F1AF99729A62F3690747AEC4CCBDA99BAE6E990A0FEFF6F1AB9ABEAFE7FB5BDDB8471C607DEC16198A2AE7776C56B5B6CA24B4C0A2441A047A18EB23302B46CC49ADFF6188FC97C886D5BF67B4B0EFF56762C4E48AAD3F02E7CFE8AA157FB1789B1
F = GF(p)


def magic_op(x, n):
    r0, r1 = 1, x
    for b in f"{n:b}":
        if b == "0":
            r1 = 2 * r0 * r1 - x
            r0 = 2 * r0**2 - 1
        else:
            r0 = 2 * r0 * r1 - x
            r1 = 2 * r1**2 - 1
    return r0


if __name__ == "__main__":
    with open("flag.txt", "rb") as f:
        flag = f.read().strip()
    h = int(sha512(flag).hexdigest(), 16)

    magic_pi = magic_op(F(314159), h)
    magic_e = magic_op(F(271828), h)

    key = os.urandom(16)
    k = F(int.from_bytes(key, "big"))
    fake_k = [F.random_element() for _ in range(63)]
    fake_k += [k - sum(fake_k)]
    obfuscated_keys = [magic_op(k, h) for k in fake_k]

    cipher = AES.new(key, AES.MODE_CTR)
    ct = cipher.encrypt(flag)
    iv = cipher.nonce

    print(f"{magic_pi = }")
    print(f"{magic_e = }")
    print(f"{obfuscated_keys = }")
    print(f"{ct = }")
    print(f"{iv = }")

output.txt：

magic_pi = 5148814821900119542741261450055292586113647535732067369080655482691554380052565459741879836667166985122205831918390644340336597281539053251470086499523221365132775020379803159725553942273967210168653981106714132657280843578263021148705351143778776029557496571051812809658662726067976153186472043930315453925013490294642486555939775792002395538684028065710983702501767061099948677637628170785784723184512036672606688238070423752236657778483603721097906556034261993570775222774608063476541749544916702299880398045617340589746748928485972604335018907462971390470546547369413439887745742610507865846805659916187409855769246066
magic_e = 8878447123397871032793353635483327299966719603604645637163456750260006046180515857865901833307682085912071015731199110455704373871473760113314701165784769078987667181963959211583330276422824395469710749484200091258769774857850449793872245975923747504359937479437427303903459396846176850418095454020049581060468731625620525480615177381749700411805412315918132064189892840156850179530864345864647263106024656636294433888042438876427957061597712325859489700850421088851945938854380725546034619592618176214387229401345980744871213452008057033238556317427000191355488935507225718920441262097316074944129216518797230562213963417
obfuscated_keys = [4326140824521956487976279790363299848688143578937727990023522238815491662350740671721514230013411757331597683368571625352388582695882636582128941646360484347134795459111236569160279150663909457407768124309279392312476336344636337502713652117848919644108537912289537322494307490254659660165575733974835847622467835578814965651031527438243253655951024082459516351436633862436384099126043526729739695974589408793403726945561938878282572240502275350253088156244371636214730224202958258359181350999902964201837940328230260016200721331892104987949025868469034207768217318927673717244644296580381717696704066699126629784882249232, 12443852187166196720263773487283365969361609467991060481955407164652241510433853083928163146416567316676178025363217117728278664255221809057719433687467466810275886907447175232228490675449517397426150486389494934608476560374723991695971918174805214710490057914531786288570435609287394946783260974440895393003319981553282456016796554678387442213355808029672092760088108657118016146417856066386654143854772884893910982387205388649305692130861026577511931693062669287514031657669618200317062312320313349947602797108676439966773727374368065488296578198977712288313471741297817131246080749281776495523725045728152013076716579287, 11783892783845819822870118117095038815104455351866333000589560749098466628752885114729156400211030676341184493016854273358000235184460998133226442870016165406925974147322395625126526284591834524316625582610271803528810859130264343844762295212699648111891630832643731292496671469062044728522576285172558908261266622769714284479597883494141193293192677562309270395117167944341612647620710597355169080040700649466338521642057317942930919487129785167269418353236763384167693221489620632450146502489746343324216092314796389520608070296144713060449325563373049259850316522648892100988388281194612063333448453461429502953505069573, 13894156638324199491589780325830647932652544899161564463071559483309546467286093405223520828169135501264802636698144156608516453216427423472361615961466613487013592996735628692789112084183006911770462544909904292646886178154723635982076885329756051981361999710089024689789416873999180519387091759639949808128828934335034206105630671166162493389440566346219873666954802229378089406087408880266698641655763151660357376758272844138884041995102251835611568833358273437505601811703195992793903089434782951182383020836633876990785303163382566116745854956335998834081239653710801745824302726034711674184913396042435545055571133792, 12678288448580042671186572469150275732822504483478141616732256941827239948358904046737688494183857567091488922251145171949955786859542694797167065162005340117661944911268231110365173088594730916095260828201812295288827844523549888068807701993173707879018614183865756424790518035581212078705997387207032364954604468540347928656995060619874359690897177473562379276785605496954007349277266990144216846433687645615455380199763058723951535981176833824218307933431198927899563580987508956169389119542592287655511500141123922463707224972886223356516031479459516982361186926716312866603420168263730649073879243570182239773829095085, 3007294520795497281042971612618310128844540139916958409280017009726485825242140286348730829573687277581285784645978145514923002927378011382555890942158454315298297591905311675413392708087984705879729621808091506645665118979702634105332675233169240984774154598329480151952278439600932572470639284867323341033534137891365118246922101858574197390664866438229887716525686547585157980145986494912912295787917764249358350330661650836463245385940512988395266502602200283381141770165120289620346213668626042898791413973369493560174862894317322568496707343437438692540388002805570813541847298532205661707949133935540996986490197477, 5150414151397048173102333802347899058497038712155283257579690234348639298884383272819016174034348114780339516279305495231131724756072480756216642522839955109208180547993963876310060836688786183828797203759791107954479064101319067743130419359786634495088015088493786197431686444905326641918372318519306288465236243786592906055846211726340837454969044165821652342742330946992403889900251785709671384558725336003250724388886409390053154050836598054959226233970754686197878915813683465988719736372179906009484488351295985183480786596004188150714175199309727969280951208386123046273613599881884323800194747636149997390176321906, 8822452485847643520056531376202657760622284461200511783685206377039813796522800232415414044464110636630309232224302892600444641934122119055647819332327533614937140614103432257826287539431363148634901301220582119950287451208090864057654810424554936975154842031917205172176217829936212424366780193081899826932340562262173489922623021011888700027727161681179146061578675674953774712387442828288434487112421184725603899915290848923075636826371960550156431176653732343229298639253640765030942086287099937580145176065193329233345632075574482989413898228726132603082154846923022856677416631598629159315889124923811272270816112735, 5530564345741667565286560935175431459904864931664757434615456196761126412190962500743165982324652394148165576198585786356807915341477218949522508476530779037517844295317564441013718727992899643842959246771073995705020705792438613183147422022822943490655629684949923020837284054212713341821314161023870400593265968850042379012837763781351761617351226946259593070029631072747837766000848785340917178837516178566179269374753220218105863917440840691005317767118783100733694368217259812166023342996922603420967961201491494881784504075759246277161159474600935372661828760637878000801501311176081503494232370265935972434405520645, 7050786732312699449019042060515010786769858607414797421582874796853275354694990669744329864630573503999226250486662967599507849745693933350481328409438454122855417386040729798833455681742061762649547726320348142063520857313221343169576590484210648746479267342322840074012017851181993087895151453981118025188771093875123268201991044281746804534260244159408849894067763479881138344976015120895300646428677400346532666225014576713571119035212998022785661234985825154866291499934926726495897257676539602704034498082339228273979951306506807247793996532403451666020129429241687379968747177124983264617320204852923682913234764987, 5039276900659266398047276548145800363446446135192214581000699675060748984346104329635667375864374083669634210849847418399402955979107949072879526290055742048319963262617321741342070063692686759985479585016894937813184093826899774787805239230982723417453911184162810655919905421268754500360609454992705830496127032285926105428672485457581172316502943305979906188456501864178709625419860050562423790107653334719999154288618946089692006847992353294712460587566251634295749564398614502158516435977797837971295255274676756336459773503001898760372828684943173035798590537886997931193573162596458101167538732250834146345969659402, 5758979144226805331210475341135327946794182699365039410088158661602138541980306673893490938905010737448041530716212543360799837605674386476048258400311741790612235657539127504614765749970084036923234722025542743703512663617133820923351137814232964714666962702878505756411219726379798159531641295570221073018042985371298809828748239340353138662907286081441293855801916674878274249926448224232275175009437867092552751245262672575806810591868632575749171767194711371225223372211564267601300128744626987017744296805117130178270938858378849326239396002268917135705050799878759162808707533012057361126013078728940721792329243108, 1702895159056171468823854947589757749228140952532080385767221090170681843555269830130551394169176690540877327837112589046144967382421591437316136148294182775816724844383034072754894526183914063087907480127483399963483948979682367931489901920500452695725151093453409410170499306787904328629621318142578909623702509467797750928863512942677686932651156236732110943353279609314490030773734639558099704027890802037569219394059333203706397847857186463593731003179309828197760781216778269268992723276653980577701472054566370211611480145528194475546669854954494087728968004515339040903714334173424117589940469697063029858293294963, 8118346686273198384298416566359739860453494777349905084314865188502216025263404196850082499071566905418671867183045095253865605532239496804112347373745439811316233249074655944105447871837733902201305216878086604539079113088078270005144382641828549894767427450020886657941741757778929216118221738333256855672918473863478310226765092064782539556466893117217230996820778216662238210243497144596968331573201579210318881796905724804697788221408330127669062281529824482501508975578102099915280088267191020727557864716435138436958250707577380361741140390514594512388292611226495585650776974775157748491808584012483243342824000654, 9859440924791794452856268296823119423269312136038813936175037949820316447248967428345383597176392641982989783210956358750539196959190343489376075059334431525446467443100739290888118438980165121928942078295181491070959121001316679784682153603078143960481506405191514941843945555738565342915055811309094729223228571036764543242632461378734882285850105027013899076391107921800039945347881723334009092620443056218859999777120746421606896661287093802181731089895032285072504061676559599152748585728992344369734651854875141083832024831749094638192094030867160130321447621984987651283940845177224428883974777987291775428361920170, 8827798874736088922209564411102702400436158486164907253829643715345394081838754458054076414210244038292929230844437285376812111434356350058445227863483114026053641737856793397482869702075779170413607658219387301243604060157441503154355673942290925864510030941412866143755338470735266159417444150836630211894840757839615014191694812501431705113376722561203958380285600633601957161971607073652999563544473273653131077459753334266791377137195124504451040521851116080049024730871437594896946591210681044717333528384921936917082029160018243978884921805335548907280756156218363196248520199505075700364198590208581088569467606556, 2461672925442236135088701785284090922635949358193800363966849184053285317198224183864003566531997883925488867215129530806281877848369895575310559797872529892257552837382755682043786800830508073424073512462946259164295558860527520996471517316770499020992271812945267958392786878593021817136104455717105142877716645527092679113274170546306023239118511199202413429216860908324460544151174993813913987719927736936215787066930172854884534723710066377097301484334733086107195420735492694188365084071809083394209016684596595876144458412488557189655051820026094495792445623034692387711532858244703246179167669945229204210165919806, 7927684068777927047740132565343313934218327980063205744067499101373535804602167911558491297487976302815973550130955003937231855705147054106923733299558971131683738592149601534200057150009587115324535226617830439373542270210081795360929288142278563650062450937624784716569252271301208677894121085666347156648836091482191960024526383996329943809068858391886961580124880252687267853680946205238627921731328436970073572807195385187535415903275787862865197435112541054010914753688827988399144627086688316830203803779420404811507179287436352918042647587165518488892577593188273226011710209211752317845566762096263794507156547601, 1895418630250936354700049120537197440921142322782583120614287082760222149208599779383034756701446917126100744778377653395641114501543663864578153693544038765210164184443335302573193473506184683882699484604377957345271970739054457104120427588151127994450621087632056347875233086546173688268326403894777960508379281098122541746793859976078451896549329593440857327501873637891358568304856773543789426468901626954957456921547353566703564246561129954591019813855581040558470546828305842915106405267670959794687781084239402560192202154097398176878233704836534672720679759015552005199034571530962787039718987994743486510622246177, 10870275403422134284519269232622625079217655376677798130539731249970465856112203546034627070508022238954476170777732851267492558214053161653266038430385864336164489148739641889875060928793452338176509966646408138982795882390667396549500309815547900098090096507214702514292582075215710057214749219460948603770980927555017177711508952233805813776113382673008485057746864898123267907885484266527942161137220879368598477962230571052951124571202585116590053922087563146365214483333022945920809104194344090881596851244838409670443748755286942003395671000841428356877343223561404760569270155106953179992551236279036420125797315289, 11280781231365477540798600759233238029156886254034890868565225673311967232542389114924202228673394526068413147995661368002203425631319518118449658992780949528628478413799232511054559315405296670137702267162866567115901045893440031359624835839127040721618639300810238564961739359334646042270004153510047896360496297914216492801552115697450869372356022668009429946053851453248923369349400551734723811676838753133200682437884707399070208360572619267032923604680665041691915972123226167010752366389314694868006078798860392326788933262529005364522594554646147938584251393289502903840847193094381950964734434006881381292005797982, 4221447318682475376308881967162474732871438961132762768648024517031763481780607649374121258982041823658360260019502139491298398021263666700224741640828215595422201630338255975119932331867061610638983983661094648673830890394165110459842258062006186378137250972691382698663972256583144152409557915124371489188961179128991338925020973643945490938298032659514857473893944070571760645842328248754874696621018371192969881144152768188597113627231277229564688690431022919874058465354656436806477431658557599885508819968388864585488234133901990903362550159714312965979464562244087209504902185697612213823736822988076530584322776391, 2156244625855235376084198594126842596133369805914182306486572593512719752786127665057483411072928078280700982867734160709072490610165336781131558314454433094095865159453347733383800244919077929585650189169099294538414474780892668258758128464394455088213236612880091745151953955453169027909954814504890678527025314500444070371792762317108423015545223996048192603163060851187479655485068758368270026325758596104871827233760616467779238231915869641537290506287345267722203100686095583953719681900660875768168744504008914557177639360303185280791739430943803207496936971332922982357096655724201524518123441185397619959559233166, 5445008535286493124251610892481360607167732253697300128821787613473169692373671603295529086410973281706696669791167963711864376876568789605285600732494571035877520112711311445682605010826689316280147942920511784355389013087033373603400560829706936165796276846228200285785903475465219340043856485198734518982669657829846917546608252330907063619622810462413964980778281402922919480224985326937973276307879865918926854256338026833942575209887008393263607831802962907685590012289672030335208987050162306242370688919966216388858226550898084556612675561161041024434768781868830273379095834392297097699708685627156532528299784300, 11673110022503574796753105367285794748766045867792965344854840864988259167464586181836183804704494682324970418049833745280922869045604409297947219356082118225162076196562309417078074275098411840664757684204271760747338408136440965618102339045720804034786078266186727660642202464582218183388185756587969749405272734127765225295531355011808890046202739946375523079562475860492673869319164694396064193617629680075393179941677177344552610686265816318550299560752434232685236264033539751265527759854782193437947896460731155437612271057513497707762609028985525402951238240544294457650966817203702274255235304349754536321572545886, 994224299033307039203579544081216591452126257653849389377462937853417730171804297192793614042170417240915527127917386254138387253255500370010575742999314488369770226303616213722163246863375092378461986226693676341847396455659597844175321334523084256392837085772314935974132587765935683295952029973141385579172104138994248199919224064905635653958958132588960963919308438170284085344099576116555202872191801831938006319726624540712516671721548363414020154699878326781397416119250104231021627228457590975320691609821968544650129513435299683989583837023371902849797405297537164049124558658894741724953959394431804415155824137, 3743333415055156113740907621766452452757020449083590505909382294540647763208563875686665901979123542074844930460731195718339336457235235513745510760006063943411852424103371004859637151870326158477897124365531595256741788380655304262850880109761161091360892726825618542511893536325147589233089592786371163814781613055872178862963583502701254673562978177540316493713309583025642416084530806253108020649729050076037100132219821401705295010081816071658391505601518232552091312774862841922389956774315822111361357559932190321057167827888953342591954026749883557045408723044550730747792185130129384495936794892342287936808245381, 1122419208737226187996760422754952233085910403589064925265208846178462945017472406817894365217799535106960004292100597927273933207475218143206999854300734494828861044783584659687514797139491599834156765844001971651488062690041276715358212796268159890967256203524030711043445458424731490880296342471374767277261484531463864680743374908039427756138795899923932711097527202111654655581745636485088400110815157973421609104203719896264493014335965141459751362899593850856011526631122252856460477038656022716355548276403603313635389513197024379390959716619019881373317721149675820760584930231783152598010011269931479845545350167, 4069460981696438366932031506383914356954574056071166342163539275094946042824287897576475057020755940427134978721333383300539038546588864186883093712076113992472867824647248566074732128638024030935724362496781576699515401608991489001070362758006159660134381818516900233906598545839788767804020896598386330753640884230767183378647201125139797732717099476777358119127238717561082767041172780150293825682416982693324276737090609511908168077939949473394302688992716758953290871096694129667582698579920743250250155454178545579144330620030884244930163917987852869423668165919363195097704513932540372185199555827766455631780776534, 5230208183283545046283645008176767761034902160068488354311577455379555121126298993992804137465435343631865669356019630374237365718722335431791030261296213202893345962102754012342909526636318369054284905662142323764817760733120044904722589671699780219194887568335470022000557496785952673227219644218700415900168214113418288616103443081828305227389845235462267739096241035880812700369543878638432684882997465230215550949011969914833258322570584474141435296504341548344946239659118167941942594876990115337651381791986890155366386074125851186000068453920985276877022708675676198500055311885371190758559852082216360723450000978, 8174418608263004643866343083873986717010771670382078016899299757533152405069048470357939921934161233349718530509121692721667574305483003837632483277099749902450515918744152620262334945946573278541840924010754947045740322843754239294805435968994984745667250066418746714270783351067914088154286695509522345397024352028075405532175066208038091122431536341862999248106505544750338720439303363548671611880913577064339068408489204541631968515028038073894257960755361266310318279928898540511252485394153721519122472151162821853539414755752761957510115378518947045559219164325572607680660625746550189153128119252488960269026454610, 10834483701877849531761631336274349018440447363766493762697858084341910484844153324554193074487395531211349670537313130004150925192162214812559123121855884378981119675021815379177401208718702366940190806340941440403052290492065094249648698449306999951583283960322033848490064621849818423485596472227257435062670972250475928793612498154136926018284310013678116922592502747779679680266470782171769056120372225319179864122903497853671995947302112737196743500002071605909227006804453100903911246104160590110018012969049199545002395249306592205324807767771665641659059904548726172084745378418309472207956068917123725415846490713, 5258947876247267513995590387792876100865627271869600154529372600702383853953366332368062842506261783895660653772300803386892925125664008632901382761018881582630010624653184887218529014677373122509582334820036352654586375463690243370770281487973633345705009768849204531860787354532025742672501370429634780186135353848756006553759500773838155166562545430140045306666249838975465471048688679058367196334385746173165107877220396726185504984027567997311740137453566090142826697527721347893525747260572150121187705977019469899119758601748778673332893243688483811140791217059720133478517748105787256249232554509573995853457101860, 3523032116764717414607030475776392998098960347196803707779079063113305449749937407313143958735754697126966379329000288671316255024363837775404126169216385155276842822358757560234953491227193673589518959792924981992554330747443615161235378105684725494877090122844794056754353014686945802606169908060991808403275526804146398734166171277536961829935139912546439444116108618274899331554507289851233891108999114132251618646727484152729231501329580825293390727581347970804154411830061991620685759381966321686945480437940639712504851567534618163316585950112757651836597793179545442335065785647080928105980218106618950706537339353, 11443323853518572421067745581802551775097758333341646869828920897084669356716973333924109287680707423017779409089474893493774884461375874707271323579758707961136715582819743725268273808215338810189522064082093018493707178567310330198522692785712741209919694155809004285276604433663614429421755607357405633281090577664155906381423271104275894921961584140413832148583362455418492578668194807400244733081829306875824119205535478739159828470320026601917948572545392651434226131244588159232027869146921466691500266934303323630114993334338006125707802472153651310203402349426857804627145817226176747336542872711346301429036985928, 12278473206784298876009438753138450410067255723072719460366652597802124929411652044565058901475729649103622769291118441322766135544907431391057600437801315993834496740172350085626766825470578242220676898913163917743816729100177040740117418635049210060820270177326178087133756560153244352005806786979474690349851359867323741400525591418115808709660950895791794714600785193945890438587907172137643423348727008511858348317369117752139942495315483389303406756977904747321558774374676018579852978213784341703444810006880029424910728950586271505751953975591371671666751185353199753059339659031347213932746215635892556308138407412, 8850147662817023428376653377578294001008164620283938693825435384405050603702979113070444608219054605269566571198055022761262416191653988327024221699644536421199702042394327458938145398146093120425356692090972327542252377415215537856966039603251598464257601238807829572343187079109847974330468726158634353373204880359702312962351652250694713966984985759084483631717197592936834135515614367541831891814612152271936175356685857393976227386596333249878428144032460389311965058075858428115058938898921885504529941153751611838405943492914677042451460442039871056181916757733805363136023544704531379589196654969186017012821317058, 5263915536049626415574018572481571891724237834997900077682506182179863059613036848473798417004192862527830753468142801671423608603426585944062303036876472773060244495752705067695967804561765294513575692055492870988986133589464383566016450709382498548359624305485586518429928352126786949273802669098348134655347878505025693553888537924962005837442713579591186167994462516339263270507301519637225498963439450311024522174256497905972433664757045042742368649337556664019789785379916689170658464621488378915226242378580609923342966087323938762192137470028475521540376716266584747999096839000960152318089193793127343090252997211, 14539911416897169251665133526113394842198117573754897963809622599862312034145384134702408320401722130555267448473608197291304658941263418172834212421318864848314188803498932269085471471761230897371377949868498260879264528324667450240186007296370203128120426850450428269258029300262112214413905534175483220922247461839724128701300334210908287323220578342800274202647731893276242289304791022996226860670401539811861944641972577530810433419056292169326782103577266522610985282450113172050824203575456855411253496190983900505782867902192995617153895114070349519410443037092338574324800019492218236752321360389075045044866776586, 14107619584295152877690535214351021030590539706390543727793077924976695179800889374619357101986129840023639954796589804819453996852445423000688464373019497895382816261582254305547609427355624939803422541037461289999382789548610286800094959676759627671757740616119249854463364458745015732267490849157422452268354861745334853138650203189976750966199832285488776557738570387826129027373449636005762160637553657599443534659491522886376431669373273884717571421784703174952248839354310274979206497660802114198911797036785028213657850341090987248144612762312703639941525394051517777388870076504595484646972592471195907832133444179, 2284233386839988947227002495964070274282558199022503985886988052458227829436605481695838534318505233405550037294418595997915518527426358020361672385001026996714988712809306021768358644872016678433188207385037791305116403549647964554925731868951015796662178749336393766161616116131811364680941411957836593501046164427066536058995679468921087219680757080953914013032960130829383138583461565927800134634374967789041206447368086566213549250227151877832572401928932697936078993641250085065824634720336182307694213174003195870301223762894211187005713840496053311443400428111639743808987990929600381204282118344738749746668956233, 12090080529983104994304367372675835679074119434268951253633189978942073242909452624910620892501805781968491373444873674435741694138272665955381586957690400868483894375228605333970810704975449396114428449280747482398174648179248684525406079277538586813381959839095027034121100887765077510388680122344054009677382688665202177763308607774332882160404400011682051420635026169154582484543358318335015478105844783238071147078827115413069983943828271257111987427608658008537091529471079884726017634360580265847859392180128862622973456900154034870334777640725451510242398867680729047582627881855171517352885916110789102063335214045, 8780410594242410454189123048923048128278636247735817978575148168489622305680160366213887932067736140460840815133747356729049647955898009648508564800043441754866109141468001744967167739859897649476767735345121905237443720915124857429127189325595735801145372444313726726536308497941169724398468229920196006075010798496227219153031870691670486105317108317532807399958445105044130157130349494558918951008657822342607930490145976005210270504662146935087065494800985678297142223374695422703802751733358176577615426268960089772682761691036839741790038242960468271102083217548915383242299421064774843685631003247040941593228767555, 12638532596286690536931793366027174524704520803329449580487191279815488768267957429530294962265166358110790727045268582010905398583737718923632418352855321816299569893548273253355886360912536787179555443675660626971767578053852932145368413925186775186130189034616600353605973889487478371018132444231428112459552495729029985844112822339751054120097879521401316189871038317733947080612839576942554900727309497216545611425178298041037192145491868916707298985731722657716924198526529317242874335474262264977345486046506312207009363930360413221163552704155627349181747911146069682199322481029869461996380115956283030128300646742, 14225693291135908811698481256861433804498034932741873120040292288731800711225001898773780895957051975452843038497064233160778994532883457153869851551779526684301330701780384146965897245766550605593704256474323407484601249890289826408468993061867651459097067836359352490280693500441683237739251760711968406953331646103425115971395938019983240456861118247563886738050381504046093561271969733387276846631761792397332823078606138333691834980274277899948370146839560961198618212477344071805085100489344286798011562967223308356031064641822482690629630439238535979705296303292099272303137067584575592241482073914160049339828743460, 1371670846041867260324589060779747235090520844266535521996198703027252534965066155432167957250347116898696089245834653043285897613533451342716539524134897244554432839433863280867709818564304583214122445966696514217618338208412200249320335077945902857539333897623931908357788289063897841985203344008004850311149383426025850199789717445826201731415077049801079165534704181238520325639719580742119306348369420916683290530533306355453512795294878930074341810793303241562580557691620348834633009439601498533767423479873465716693383171542209708107935387189837715680781850228484843541798561174770702316729791473055450285943188265, 14708623804859337495233293249705554627856957953621073620574738343860442527437860459714392963432307565548395191553067287274734757641150929665498184091033973576720183502674585730232215192920711432115081065232565013337995748491222320937509734212639300113206532377476575263455729130986937361555117756308715691421831641649823135341333402616684672914850677982415341526608702608573542769062092203386950581245889146839759080652674215267660170986778798088035444904448061916724833904274789061415486957713985215321172801596973918213065262786043657431578763182103447000231844339769996252181071717290376583199617702912965525367542660535, 2079525942186153669295901492783740853212676561024193444780638988637847835644756443586890166439134698718932408243774425537995619928125603250628129115417902964735855519616272717379878048344881168224345684347364945700147131969989821058820879460314431635876119848428938120985381125003300617209346969998813735787567448774119589168695501044320014748099471066312674185119281298743032855120434892720428182236503714739337394039640707118038361657304942328498599585592181382144837561952879360025526179800392653477378744457281856741910408517044085784236670891450567973147640935080531824447313097181533661742399531352379822738701176567, 14792590665641028843033432480061660678975535819902801605571661546859426944131644568533395689046584811184391064144364792722577364068548209812474918806539788935075918298444261756722804477814663215497569069435454115120970529083814165863023872402563758552891206856042823668630816466927169339616898566240975080602419989584571252545007212013771626517775440419830425518552096774200225677449669460551889774509420628915115620873014862248765180503211726719165513374467773188013372007320110305669595026735996749618153282645159688914676920961714313055226046583528196528706063553983176539656599868939612854821053695656456430891836046092, 5421429792702568956729448569045195983852090988415758953575732945204333711957283060401211013931083588517500706846881352630854446235353695717332891228089451477378334669684360562646633015073537524338852194521249427314890306475465753890159977531883008697154603946794774313081972383969295442439137905948514986021418741247625670140599363209300238798422485012201480741035076590484076842740075780444289079509316382144446939083621783753965961898295535663162366825928320927006075967490264774219761948688976913098380134041630258553195459377700387995095857287227516370666281688103676000985604139928039764842944488391533010282401307918, 16178649325955842402878726248274823977309882506287302051961519684678802473114984617129333886148676799264635697963162832407100014691313801065797257437738519413038009847443318468797712116507107655903883044657970891310434813181545857360877275166548832189441979343030869350342946775702769146866214177165615311698901131147756167307227871668925809119371545250957131383939530183858600239845959699502960614528416837991687740058988062457118493477726348647535783604491447947002705228049650535453941845139580036524797171208903103984021381203471446362051930563808412078372484826383291672504121158412234425121958956560049726681796458734, 12609070105293050032848354708018025837063434503582939534855910239145322982669910473099388994113585907117312785941621522138076245516915577287852137982922803644060389479313880830623331634893838694405730013003743693865572486882307987016754787497582569571661406019033781198714521464606337359283147168906981614965735718230451877685435341337703571146714065735073556120719072348605350825240780876718002822374738460929998616328204174997582615499347552490165673535936109614190286423405201342438329251427185192818400581782142365403936506839499607039824377039122860846979829061386657756765366423303110962894985948551557898044626520095, 9424965984496651484696657367909446260942288240190190698080921833233653936277820348366348390264424261125141209375609118804226748811202714702967509258633148036415861309844015290410849991983709975340404728355494662203464963072235301554629381315134034783443037192238889932533301386357067633343193806816389244330084958270436126743642138397636786107253658973748153321925404243737725838101876051556793957537338106495518601017626816023679179074471278491918165145736726928755193593981174950170246606456222849178073824126075666917676831714930509928718405241759798553287221291664744401366668653741945990878092081172185103150896602330, 15116293680355608338382791908385195283995972537295926894651657778746497438491427943524354548499488171820197683012030663683009969734274886185767682528288749245942824531167213740939529660288282528025448769877881201963613912521520383794047380940601728197607425184251757234478463578833143818325215615477550188629794292013102489486566656942696426311298741696919903494480394822253005781518237470439964919901355722461444434410078168995692467731258451461849270266711569207791040632693282795598661262568749935159035305150669987269220844848184218436833596127591160110003781920164166758213975872142293778849841543045307561185605113401, 1925238780806008102331032014237481353073397536634789799780429015027648664934529654073221644947817960511486112318301594817736082765502076327789930564296518837005007795961552049501019490821880634700284284306694114847827819156811008668558676520544849867590766448108687206550783084199492021214339226151215819239963158100824675703324701240211222614703150885619803722271810351872083128322252115758690757299997463743499088521978157395068004235755181332814982338144201686541896056301556512030112746666153349320356084364709773383265777676988901698155268493906326020459185891222641964911152490415118379628499580159035557298181418290, 6821849778594062649763965434134147407981452386318528626049695128123610596804507486709291218053525228591339504038628576822848502138629519482167041154933105202131743197025133753406343212154773378664369808778950824953150391692115439636038281207318564530422025116063083561199444521236903613135585947543910910387167551982579105450569703737345719081978256626998176599150666634267571212434728450900702104872971864246156985076624004994146096408054023255040510677521305488234666884264243967139738435724930192717598240505994041162031562208515957026565435496680211293045131394063363315639312247735761004084950672659526629560827232941, 11981658011637873125680072618645994877624974013490208181802570503366160145273496194862623908588507029909145260125047107768764622482979310794547412998167142447953991400201229952905629766207486104328013007982288279354665890858545171420935476023773195871424546693467474150593391025768275500016977515166160189274993869882233828204705286795205657154575481111744059893515156011082485636881326837499293773034052147746640263638446885444421593297652460492447419834930083193292556328827661748026267333937588974753235170684027180848719469966309281347273505332264604442713377431337824526264857750170389969931851540203502894039498691967, 11256187409460270898265956394919678546929858727894223405333146256596470748947568358990433496164501643161730637614822508248765153092768766403694929925847705408792551692872276134518982137483584503721024087826406608103314996701570229190632978246419763933567142024184547947234530444612320108228238688804560571233110645182028817928582954949635282409260517213694673281160430235903401583991245835254121494686959061154478141094037987083918064542081105776691719972726391443985512291367926752898233233685180826635774222221703327119039039619107375045711773427582069998788349194225275031270464603676060061131743763511360826998034100991, 3319411965977730047648576917115688681976487870497815679902781110387252550220069019764562095986350303663002203821987514988421271558817221111338171556585872726565037061707807664741784768360668802006071574833246269217766938363474498862500197198370431931173791572421237207825891865985215814966857698153030397761236161957563601153665960536567949074742904655863603013948776579645484745161923464067657660239853804008863759163376848796762923763270847767153196111649856562654450306169666851528000816678125042428968196740859821974508588002054755848189988129603586891365220858852353693110249092425685104763097043924139904088800060521, 12440733317606575382710352654318473546589355635168021140657311851351055049847357265508697455805212918041025852751144015875248385455958299170054295854074464215581465263695823276600100679497078078322749491562405691274733378272823429315886588020768610470548278605470535075891323522097959489061870147238336983777144580058079600244467447792703903044627942703163070641612348212379039433161926552680997068363633596337504852569005001761539244734999135715440517028678902856488108828144264464893776800718718769958123168739501612398053156833948455014893392750135833482573323635978924922526215270385957216940667132162533975033895346775, 5757567941375580530435243651475354104501304019243937132799740546112033707027787914785768694342613775393744981241875527473314336947343193046466811789827733032642693667836972992206328861262460815481283166148914250630615316898458133055858878316444987377662565209542565056651965583081675595077558270488418534841546646235033376395051972428946326063968947133466955959425308477840732694061795833483179676288375644160800443024134992004563418806064994731107175193062378828884502809042962669482278048331982443799467318391557500729421837035812255908651432139645293591708317718612904319634655922778481117799526048985085267704172550041, 9829609956686583539845069342696192764417537911788107771859991393028091055220219008364425207849530065035154708694451213195271189116553389726957933134001936390978467737576421151103158874895274463488487765290953286298411444402871366777853110162314320038942558116305509076778891448363467504402514360289853588404894996298931303558346072378994874744743151838536819125707671305088120463629820871750181161777604563619897177298201988691579822105396918784197227480834608483198525121412178838344219369353861507273954874828624243451208368171223558656148999897034543214094636582878880955458855203080241088957507238168846515021722590366, 903703112768796183752069095763743554139797329197818971787841058004305700873207795820933992676806887620939596382846897408637351844794124411428902053648778006381126009317839874111084800541365808374023555938251717267473357191672167482202178157424570290263028939328749310167594541509949940210031310343596411750505234867344384444828089529554118151805058227356571346033364555417594766601791035174426960534074575507876829870106496985014718717331094109927348344717736408835527237280542510019005294523453490783084257941123449565664192188834403616442808417208937363198937058818592325903996360057972740547659042534740843072009139249, 4563431876926279903130938771973599753940044870201518046127908129409343089167342982354018725080391717464418066015241113361936860070231381602919316276969174866674035834321486781239937851119742414306767123060674749136547608888260951563444903884008810600799956465626549802548489024365405139230435972233252715513445481429533830151912566960320815379604390194802689334888564099349600886696470080642472404932839931517971905017769157249769345864132437402613647889332517219347314966089012391356518890836394547508933891335220586269002333185336386567891310665204219719676264881128639830424174841904902298242722065731296746803365913815]
ct = b'\xb7\x91\xcd\x11\xdc\x8f\x89\xbe\x02x\xcd4U\xf6\xfaE\xee\xa6\x96a\xab\x08zw3\x1bo&\xc4\xc7\x00\x9b\xb7\x02_\xc0\xdd\xae\xa4\xf5\n\x15\x8e\xb5\x1fHUm\xe3Z\x92\x10Ys\xc9v\xf6\xee\x99'
iv = b'DO\xf4Kc\x1f?7'

题目给了一个很奇怪的运算magic_op，为了方便表示就把他记为$f$，然后给出了以下几个奇怪的值：

$f(314159,h)$ $f(271828,h)$

然后又给了很多组：

$f(k_i,h) , i \in \{0,1,2,...,63\}$

其中k都是未知的，要求解出k才能解AES，此外h是某个未知的SHA512值。

做这个题的时候真是一点头脑也摸不到，因为magic_op看上去是个矩阵之类的运算，但是想上手写发现完全不会写，最后也没有一点进展。

赛后看maple的wp，才知道这个神奇的运算其实是某种群的运算，由于经测试，对于任意x，下列条件有且仅有一个成立：

$f(x,p-1) = 1$ $f(x,p+1) = 1$

也就是说这一定同构于一个阶为p-1或阶为p+1的子群，并且所有元素x一定在其中一个里。而分解一下p-1和p+1可以发现，p-1有一部分是光滑的，而p+1甚至可以完全分解。并且经过测试得到：

$f(314159,p-1) = 1$ $f(271828,p+1) = 1$

所以由于p+1的因子全部知道，因此对第二组数据在p+1下求dlp，如果有个512bit的h，那就是h本身了。

因为如果的确在p+1这个子群下，实际上求出来的是h % (p+1)，也就是h本身

然而实操的时候发现，虽然p+1能完全分解掉，但是最后一个因子38738895416631107有接近60bit，不是很利于求dlp，所以maple的方法是分别对两组数据的光滑因子求pohlig-hellman，然后crt起来得到最终的h，以h的大小是否接近512bit来判定是不是正确。

这个部分是我这题最昏的地方，这群太神奇了，不知道为什么一定需要映射到二次扩域上才能dlp，我这里直接在一次的乘法群上去pohlig-hellman一直打不通。同时也不知道为啥还要分正负crt，先将就着用吧，之后再回头看

求出了h之后，那么我们现在等于拥有多个如下形式的值：

$hk_i , i \in \{0,1,2,...,63\}$

由群的知识可以知道，如果ki在阶为p-1的群中，那么hki当然也在，所以依然可以通过magic_op来判定某个元素在哪个群中，然后求h关于群阶的逆元就可以解密了。

但是有一个问题就是h求出来是个偶数，所以会有多解，难以确定到底哪个解才是真正的ki。但这个问题也很容易，由于我们知道每个ki中有且仅有一个是正确的，并且所有正确的ki的和是AES的key，仅仅只有128bit，所以其和很小，可以用noise_crt的类似做法来规约出这个很小的和以及真正的系数。

exp：

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import *
from tqdm import *

proof.all(False)
p = 0x7AADA0BA1C05D63803BA6BCE66CB6BC091C7ADA62B5CB5BC9F924B528FC113971D4BC54C7FAF3C146ADEB0548BFB9258DFF316741266B802DD7A2F46F77593BAD983E6DF394C1519E8DB0130289FA5A9C628E3ABCE58C63B3379DB7088AAC7A40B63776959774B1B57B8FD316C650AE3C012A91EE653477443446050438A99E79B89B69745BD1918EECB08A0C9D45EF3C61639137F24D979FF380D65C7ABD08785F1AF99729A62F3690747AEC4CCBDA99BAE6E990A0FEFF6F1AB9ABEAFE7FB5BDDB8471C607DEC16198A2AE7776C56B5B6CA24B4C0A2441A047A18EB23302B46CC49ADFF6188FC97C886D5BF67B4B0EFF56762C4E48AAD3F02E7CFE8AA157FB1789B1
F = GF(p)
K = GF(p**2, "a")
#p-1
r1 = 32090597631875496964875824460641091296628030027330309270573588881699593258049492214648292205225010111468663778228033045339445804490552722382348336318865847719914851913737484451240783616294102245396637177371574819217147012208300441560023891282015402732149110315530519720930056963731560649365139635779017776119600025753742823545028690464302214723068726007943829580947008199206705401817636950825543787766807185293761967238938853522371566190222852636237278457796298025574931849223290873819297382019894964502598331073287197009
#p+1
r2 = 38738895416631107^30

################################################## part1 get h
magic_pi = 5148814821900119542741261450055292586113647535732067369080655482691554380052565459741879836667166985122205831918390644340336597281539053251470086499523221365132775020379803159725553942273967210168653981106714132657280843578263021148705351143778776029557496571051812809658662726067976153186472043930315453925013490294642486555939775792002395538684028065710983702501767061099948677637628170785784723184512036672606688238070423752236657778483603721097906556034261993570775222774608063476541749544916702299880398045617340589746748928485972604335018907462971390470546547369413439887745742610507865846805659916187409855769246066
magic_e = 8878447123397871032793353635483327299966719603604645637163456750260006046180515857865901833307682085912071015731199110455704373871473760113314701165784769078987667181963959211583330276422824395469710749484200091258769774857850449793872245975923747504359937479437427303903459396846176850418095454020049581060468731625620525480615177381749700411805412315918132064189892840156850179530864345864647263106024656636294433888042438876427957061597712325859489700850421088851945938854380725546034619592618176214387229401345980744871213452008057033238556317427000191355488935507225718920441262097316074944129216518797230562213963417
obfuscated_keys = [4326140824521956487976279790363299848688143578937727990023522238815491662350740671721514230013411757331597683368571625352388582695882636582128941646360484347134795459111236569160279150663909457407768124309279392312476336344636337502713652117848919644108537912289537322494307490254659660165575733974835847622467835578814965651031527438243253655951024082459516351436633862436384099126043526729739695974589408793403726945561938878282572240502275350253088156244371636214730224202958258359181350999902964201837940328230260016200721331892104987949025868469034207768217318927673717244644296580381717696704066699126629784882249232, 12443852187166196720263773487283365969361609467991060481955407164652241510433853083928163146416567316676178025363217117728278664255221809057719433687467466810275886907447175232228490675449517397426150486389494934608476560374723991695971918174805214710490057914531786288570435609287394946783260974440895393003319981553282456016796554678387442213355808029672092760088108657118016146417856066386654143854772884893910982387205388649305692130861026577511931693062669287514031657669618200317062312320313349947602797108676439966773727374368065488296578198977712288313471741297817131246080749281776495523725045728152013076716579287, 11783892783845819822870118117095038815104455351866333000589560749098466628752885114729156400211030676341184493016854273358000235184460998133226442870016165406925974147322395625126526284591834524316625582610271803528810859130264343844762295212699648111891630832643731292496671469062044728522576285172558908261266622769714284479597883494141193293192677562309270395117167944341612647620710597355169080040700649466338521642057317942930919487129785167269418353236763384167693221489620632450146502489746343324216092314796389520608070296144713060449325563373049259850316522648892100988388281194612063333448453461429502953505069573, 13894156638324199491589780325830647932652544899161564463071559483309546467286093405223520828169135501264802636698144156608516453216427423472361615961466613487013592996735628692789112084183006911770462544909904292646886178154723635982076885329756051981361999710089024689789416873999180519387091759639949808128828934335034206105630671166162493389440566346219873666954802229378089406087408880266698641655763151660357376758272844138884041995102251835611568833358273437505601811703195992793903089434782951182383020836633876990785303163382566116745854956335998834081239653710801745824302726034711674184913396042435545055571133792, 12678288448580042671186572469150275732822504483478141616732256941827239948358904046737688494183857567091488922251145171949955786859542694797167065162005340117661944911268231110365173088594730916095260828201812295288827844523549888068807701993173707879018614183865756424790518035581212078705997387207032364954604468540347928656995060619874359690897177473562379276785605496954007349277266990144216846433687645615455380199763058723951535981176833824218307933431198927899563580987508956169389119542592287655511500141123922463707224972886223356516031479459516982361186926716312866603420168263730649073879243570182239773829095085, 3007294520795497281042971612618310128844540139916958409280017009726485825242140286348730829573687277581285784645978145514923002927378011382555890942158454315298297591905311675413392708087984705879729621808091506645665118979702634105332675233169240984774154598329480151952278439600932572470639284867323341033534137891365118246922101858574197390664866438229887716525686547585157980145986494912912295787917764249358350330661650836463245385940512988395266502602200283381141770165120289620346213668626042898791413973369493560174862894317322568496707343437438692540388002805570813541847298532205661707949133935540996986490197477, 5150414151397048173102333802347899058497038712155283257579690234348639298884383272819016174034348114780339516279305495231131724756072480756216642522839955109208180547993963876310060836688786183828797203759791107954479064101319067743130419359786634495088015088493786197431686444905326641918372318519306288465236243786592906055846211726340837454969044165821652342742330946992403889900251785709671384558725336003250724388886409390053154050836598054959226233970754686197878915813683465988719736372179906009484488351295985183480786596004188150714175199309727969280951208386123046273613599881884323800194747636149997390176321906, 8822452485847643520056531376202657760622284461200511783685206377039813796522800232415414044464110636630309232224302892600444641934122119055647819332327533614937140614103432257826287539431363148634901301220582119950287451208090864057654810424554936975154842031917205172176217829936212424366780193081899826932340562262173489922623021011888700027727161681179146061578675674953774712387442828288434487112421184725603899915290848923075636826371960550156431176653732343229298639253640765030942086287099937580145176065193329233345632075574482989413898228726132603082154846923022856677416631598629159315889124923811272270816112735, 5530564345741667565286560935175431459904864931664757434615456196761126412190962500743165982324652394148165576198585786356807915341477218949522508476530779037517844295317564441013718727992899643842959246771073995705020705792438613183147422022822943490655629684949923020837284054212713341821314161023870400593265968850042379012837763781351761617351226946259593070029631072747837766000848785340917178837516178566179269374753220218105863917440840691005317767118783100733694368217259812166023342996922603420967961201491494881784504075759246277161159474600935372661828760637878000801501311176081503494232370265935972434405520645, 7050786732312699449019042060515010786769858607414797421582874796853275354694990669744329864630573503999226250486662967599507849745693933350481328409438454122855417386040729798833455681742061762649547726320348142063520857313221343169576590484210648746479267342322840074012017851181993087895151453981118025188771093875123268201991044281746804534260244159408849894067763479881138344976015120895300646428677400346532666225014576713571119035212998022785661234985825154866291499934926726495897257676539602704034498082339228273979951306506807247793996532403451666020129429241687379968747177124983264617320204852923682913234764987, 5039276900659266398047276548145800363446446135192214581000699675060748984346104329635667375864374083669634210849847418399402955979107949072879526290055742048319963262617321741342070063692686759985479585016894937813184093826899774787805239230982723417453911184162810655919905421268754500360609454992705830496127032285926105428672485457581172316502943305979906188456501864178709625419860050562423790107653334719999154288618946089692006847992353294712460587566251634295749564398614502158516435977797837971295255274676756336459773503001898760372828684943173035798590537886997931193573162596458101167538732250834146345969659402, 5758979144226805331210475341135327946794182699365039410088158661602138541980306673893490938905010737448041530716212543360799837605674386476048258400311741790612235657539127504614765749970084036923234722025542743703512663617133820923351137814232964714666962702878505756411219726379798159531641295570221073018042985371298809828748239340353138662907286081441293855801916674878274249926448224232275175009437867092552751245262672575806810591868632575749171767194711371225223372211564267601300128744626987017744296805117130178270938858378849326239396002268917135705050799878759162808707533012057361126013078728940721792329243108, 1702895159056171468823854947589757749228140952532080385767221090170681843555269830130551394169176690540877327837112589046144967382421591437316136148294182775816724844383034072754894526183914063087907480127483399963483948979682367931489901920500452695725151093453409410170499306787904328629621318142578909623702509467797750928863512942677686932651156236732110943353279609314490030773734639558099704027890802037569219394059333203706397847857186463593731003179309828197760781216778269268992723276653980577701472054566370211611480145528194475546669854954494087728968004515339040903714334173424117589940469697063029858293294963, 8118346686273198384298416566359739860453494777349905084314865188502216025263404196850082499071566905418671867183045095253865605532239496804112347373745439811316233249074655944105447871837733902201305216878086604539079113088078270005144382641828549894767427450020886657941741757778929216118221738333256855672918473863478310226765092064782539556466893117217230996820778216662238210243497144596968331573201579210318881796905724804697788221408330127669062281529824482501508975578102099915280088267191020727557864716435138436958250707577380361741140390514594512388292611226495585650776974775157748491808584012483243342824000654, 9859440924791794452856268296823119423269312136038813936175037949820316447248967428345383597176392641982989783210956358750539196959190343489376075059334431525446467443100739290888118438980165121928942078295181491070959121001316679784682153603078143960481506405191514941843945555738565342915055811309094729223228571036764543242632461378734882285850105027013899076391107921800039945347881723334009092620443056218859999777120746421606896661287093802181731089895032285072504061676559599152748585728992344369734651854875141083832024831749094638192094030867160130321447621984987651283940845177224428883974777987291775428361920170, 8827798874736088922209564411102702400436158486164907253829643715345394081838754458054076414210244038292929230844437285376812111434356350058445227863483114026053641737856793397482869702075779170413607658219387301243604060157441503154355673942290925864510030941412866143755338470735266159417444150836630211894840757839615014191694812501431705113376722561203958380285600633601957161971607073652999563544473273653131077459753334266791377137195124504451040521851116080049024730871437594896946591210681044717333528384921936917082029160018243978884921805335548907280756156218363196248520199505075700364198590208581088569467606556, 2461672925442236135088701785284090922635949358193800363966849184053285317198224183864003566531997883925488867215129530806281877848369895575310559797872529892257552837382755682043786800830508073424073512462946259164295558860527520996471517316770499020992271812945267958392786878593021817136104455717105142877716645527092679113274170546306023239118511199202413429216860908324460544151174993813913987719927736936215787066930172854884534723710066377097301484334733086107195420735492694188365084071809083394209016684596595876144458412488557189655051820026094495792445623034692387711532858244703246179167669945229204210165919806, 7927684068777927047740132565343313934218327980063205744067499101373535804602167911558491297487976302815973550130955003937231855705147054106923733299558971131683738592149601534200057150009587115324535226617830439373542270210081795360929288142278563650062450937624784716569252271301208677894121085666347156648836091482191960024526383996329943809068858391886961580124880252687267853680946205238627921731328436970073572807195385187535415903275787862865197435112541054010914753688827988399144627086688316830203803779420404811507179287436352918042647587165518488892577593188273226011710209211752317845566762096263794507156547601, 1895418630250936354700049120537197440921142322782583120614287082760222149208599779383034756701446917126100744778377653395641114501543663864578153693544038765210164184443335302573193473506184683882699484604377957345271970739054457104120427588151127994450621087632056347875233086546173688268326403894777960508379281098122541746793859976078451896549329593440857327501873637891358568304856773543789426468901626954957456921547353566703564246561129954591019813855581040558470546828305842915106405267670959794687781084239402560192202154097398176878233704836534672720679759015552005199034571530962787039718987994743486510622246177, 10870275403422134284519269232622625079217655376677798130539731249970465856112203546034627070508022238954476170777732851267492558214053161653266038430385864336164489148739641889875060928793452338176509966646408138982795882390667396549500309815547900098090096507214702514292582075215710057214749219460948603770980927555017177711508952233805813776113382673008485057746864898123267907885484266527942161137220879368598477962230571052951124571202585116590053922087563146365214483333022945920809104194344090881596851244838409670443748755286942003395671000841428356877343223561404760569270155106953179992551236279036420125797315289, 11280781231365477540798600759233238029156886254034890868565225673311967232542389114924202228673394526068413147995661368002203425631319518118449658992780949528628478413799232511054559315405296670137702267162866567115901045893440031359624835839127040721618639300810238564961739359334646042270004153510047896360496297914216492801552115697450869372356022668009429946053851453248923369349400551734723811676838753133200682437884707399070208360572619267032923604680665041691915972123226167010752366389314694868006078798860392326788933262529005364522594554646147938584251393289502903840847193094381950964734434006881381292005797982, 4221447318682475376308881967162474732871438961132762768648024517031763481780607649374121258982041823658360260019502139491298398021263666700224741640828215595422201630338255975119932331867061610638983983661094648673830890394165110459842258062006186378137250972691382698663972256583144152409557915124371489188961179128991338925020973643945490938298032659514857473893944070571760645842328248754874696621018371192969881144152768188597113627231277229564688690431022919874058465354656436806477431658557599885508819968388864585488234133901990903362550159714312965979464562244087209504902185697612213823736822988076530584322776391, 2156244625855235376084198594126842596133369805914182306486572593512719752786127665057483411072928078280700982867734160709072490610165336781131558314454433094095865159453347733383800244919077929585650189169099294538414474780892668258758128464394455088213236612880091745151953955453169027909954814504890678527025314500444070371792762317108423015545223996048192603163060851187479655485068758368270026325758596104871827233760616467779238231915869641537290506287345267722203100686095583953719681900660875768168744504008914557177639360303185280791739430943803207496936971332922982357096655724201524518123441185397619959559233166, 5445008535286493124251610892481360607167732253697300128821787613473169692373671603295529086410973281706696669791167963711864376876568789605285600732494571035877520112711311445682605010826689316280147942920511784355389013087033373603400560829706936165796276846228200285785903475465219340043856485198734518982669657829846917546608252330907063619622810462413964980778281402922919480224985326937973276307879865918926854256338026833942575209887008393263607831802962907685590012289672030335208987050162306242370688919966216388858226550898084556612675561161041024434768781868830273379095834392297097699708685627156532528299784300, 11673110022503574796753105367285794748766045867792965344854840864988259167464586181836183804704494682324970418049833745280922869045604409297947219356082118225162076196562309417078074275098411840664757684204271760747338408136440965618102339045720804034786078266186727660642202464582218183388185756587969749405272734127765225295531355011808890046202739946375523079562475860492673869319164694396064193617629680075393179941677177344552610686265816318550299560752434232685236264033539751265527759854782193437947896460731155437612271057513497707762609028985525402951238240544294457650966817203702274255235304349754536321572545886, 994224299033307039203579544081216591452126257653849389377462937853417730171804297192793614042170417240915527127917386254138387253255500370010575742999314488369770226303616213722163246863375092378461986226693676341847396455659597844175321334523084256392837085772314935974132587765935683295952029973141385579172104138994248199919224064905635653958958132588960963919308438170284085344099576116555202872191801831938006319726624540712516671721548363414020154699878326781397416119250104231021627228457590975320691609821968544650129513435299683989583837023371902849797405297537164049124558658894741724953959394431804415155824137, 3743333415055156113740907621766452452757020449083590505909382294540647763208563875686665901979123542074844930460731195718339336457235235513745510760006063943411852424103371004859637151870326158477897124365531595256741788380655304262850880109761161091360892726825618542511893536325147589233089592786371163814781613055872178862963583502701254673562978177540316493713309583025642416084530806253108020649729050076037100132219821401705295010081816071658391505601518232552091312774862841922389956774315822111361357559932190321057167827888953342591954026749883557045408723044550730747792185130129384495936794892342287936808245381, 1122419208737226187996760422754952233085910403589064925265208846178462945017472406817894365217799535106960004292100597927273933207475218143206999854300734494828861044783584659687514797139491599834156765844001971651488062690041276715358212796268159890967256203524030711043445458424731490880296342471374767277261484531463864680743374908039427756138795899923932711097527202111654655581745636485088400110815157973421609104203719896264493014335965141459751362899593850856011526631122252856460477038656022716355548276403603313635389513197024379390959716619019881373317721149675820760584930231783152598010011269931479845545350167, 4069460981696438366932031506383914356954574056071166342163539275094946042824287897576475057020755940427134978721333383300539038546588864186883093712076113992472867824647248566074732128638024030935724362496781576699515401608991489001070362758006159660134381818516900233906598545839788767804020896598386330753640884230767183378647201125139797732717099476777358119127238717561082767041172780150293825682416982693324276737090609511908168077939949473394302688992716758953290871096694129667582698579920743250250155454178545579144330620030884244930163917987852869423668165919363195097704513932540372185199555827766455631780776534, 5230208183283545046283645008176767761034902160068488354311577455379555121126298993992804137465435343631865669356019630374237365718722335431791030261296213202893345962102754012342909526636318369054284905662142323764817760733120044904722589671699780219194887568335470022000557496785952673227219644218700415900168214113418288616103443081828305227389845235462267739096241035880812700369543878638432684882997465230215550949011969914833258322570584474141435296504341548344946239659118167941942594876990115337651381791986890155366386074125851186000068453920985276877022708675676198500055311885371190758559852082216360723450000978, 8174418608263004643866343083873986717010771670382078016899299757533152405069048470357939921934161233349718530509121692721667574305483003837632483277099749902450515918744152620262334945946573278541840924010754947045740322843754239294805435968994984745667250066418746714270783351067914088154286695509522345397024352028075405532175066208038091122431536341862999248106505544750338720439303363548671611880913577064339068408489204541631968515028038073894257960755361266310318279928898540511252485394153721519122472151162821853539414755752761957510115378518947045559219164325572607680660625746550189153128119252488960269026454610, 10834483701877849531761631336274349018440447363766493762697858084341910484844153324554193074487395531211349670537313130004150925192162214812559123121855884378981119675021815379177401208718702366940190806340941440403052290492065094249648698449306999951583283960322033848490064621849818423485596472227257435062670972250475928793612498154136926018284310013678116922592502747779679680266470782171769056120372225319179864122903497853671995947302112737196743500002071605909227006804453100903911246104160590110018012969049199545002395249306592205324807767771665641659059904548726172084745378418309472207956068917123725415846490713, 5258947876247267513995590387792876100865627271869600154529372600702383853953366332368062842506261783895660653772300803386892925125664008632901382761018881582630010624653184887218529014677373122509582334820036352654586375463690243370770281487973633345705009768849204531860787354532025742672501370429634780186135353848756006553759500773838155166562545430140045306666249838975465471048688679058367196334385746173165107877220396726185504984027567997311740137453566090142826697527721347893525747260572150121187705977019469899119758601748778673332893243688483811140791217059720133478517748105787256249232554509573995853457101860, 3523032116764717414607030475776392998098960347196803707779079063113305449749937407313143958735754697126966379329000288671316255024363837775404126169216385155276842822358757560234953491227193673589518959792924981992554330747443615161235378105684725494877090122844794056754353014686945802606169908060991808403275526804146398734166171277536961829935139912546439444116108618274899331554507289851233891108999114132251618646727484152729231501329580825293390727581347970804154411830061991620685759381966321686945480437940639712504851567534618163316585950112757651836597793179545442335065785647080928105980218106618950706537339353, 11443323853518572421067745581802551775097758333341646869828920897084669356716973333924109287680707423017779409089474893493774884461375874707271323579758707961136715582819743725268273808215338810189522064082093018493707178567310330198522692785712741209919694155809004285276604433663614429421755607357405633281090577664155906381423271104275894921961584140413832148583362455418492578668194807400244733081829306875824119205535478739159828470320026601917948572545392651434226131244588159232027869146921466691500266934303323630114993334338006125707802472153651310203402349426857804627145817226176747336542872711346301429036985928, 12278473206784298876009438753138450410067255723072719460366652597802124929411652044565058901475729649103622769291118441322766135544907431391057600437801315993834496740172350085626766825470578242220676898913163917743816729100177040740117418635049210060820270177326178087133756560153244352005806786979474690349851359867323741400525591418115808709660950895791794714600785193945890438587907172137643423348727008511858348317369117752139942495315483389303406756977904747321558774374676018579852978213784341703444810006880029424910728950586271505751953975591371671666751185353199753059339659031347213932746215635892556308138407412, 8850147662817023428376653377578294001008164620283938693825435384405050603702979113070444608219054605269566571198055022761262416191653988327024221699644536421199702042394327458938145398146093120425356692090972327542252377415215537856966039603251598464257601238807829572343187079109847974330468726158634353373204880359702312962351652250694713966984985759084483631717197592936834135515614367541831891814612152271936175356685857393976227386596333249878428144032460389311965058075858428115058938898921885504529941153751611838405943492914677042451460442039871056181916757733805363136023544704531379589196654969186017012821317058, 5263915536049626415574018572481571891724237834997900077682506182179863059613036848473798417004192862527830753468142801671423608603426585944062303036876472773060244495752705067695967804561765294513575692055492870988986133589464383566016450709382498548359624305485586518429928352126786949273802669098348134655347878505025693553888537924962005837442713579591186167994462516339263270507301519637225498963439450311024522174256497905972433664757045042742368649337556664019789785379916689170658464621488378915226242378580609923342966087323938762192137470028475521540376716266584747999096839000960152318089193793127343090252997211, 14539911416897169251665133526113394842198117573754897963809622599862312034145384134702408320401722130555267448473608197291304658941263418172834212421318864848314188803498932269085471471761230897371377949868498260879264528324667450240186007296370203128120426850450428269258029300262112214413905534175483220922247461839724128701300334210908287323220578342800274202647731893276242289304791022996226860670401539811861944641972577530810433419056292169326782103577266522610985282450113172050824203575456855411253496190983900505782867902192995617153895114070349519410443037092338574324800019492218236752321360389075045044866776586, 14107619584295152877690535214351021030590539706390543727793077924976695179800889374619357101986129840023639954796589804819453996852445423000688464373019497895382816261582254305547609427355624939803422541037461289999382789548610286800094959676759627671757740616119249854463364458745015732267490849157422452268354861745334853138650203189976750966199832285488776557738570387826129027373449636005762160637553657599443534659491522886376431669373273884717571421784703174952248839354310274979206497660802114198911797036785028213657850341090987248144612762312703639941525394051517777388870076504595484646972592471195907832133444179, 2284233386839988947227002495964070274282558199022503985886988052458227829436605481695838534318505233405550037294418595997915518527426358020361672385001026996714988712809306021768358644872016678433188207385037791305116403549647964554925731868951015796662178749336393766161616116131811364680941411957836593501046164427066536058995679468921087219680757080953914013032960130829383138583461565927800134634374967789041206447368086566213549250227151877832572401928932697936078993641250085065824634720336182307694213174003195870301223762894211187005713840496053311443400428111639743808987990929600381204282118344738749746668956233, 12090080529983104994304367372675835679074119434268951253633189978942073242909452624910620892501805781968491373444873674435741694138272665955381586957690400868483894375228605333970810704975449396114428449280747482398174648179248684525406079277538586813381959839095027034121100887765077510388680122344054009677382688665202177763308607774332882160404400011682051420635026169154582484543358318335015478105844783238071147078827115413069983943828271257111987427608658008537091529471079884726017634360580265847859392180128862622973456900154034870334777640725451510242398867680729047582627881855171517352885916110789102063335214045, 8780410594242410454189123048923048128278636247735817978575148168489622305680160366213887932067736140460840815133747356729049647955898009648508564800043441754866109141468001744967167739859897649476767735345121905237443720915124857429127189325595735801145372444313726726536308497941169724398468229920196006075010798496227219153031870691670486105317108317532807399958445105044130157130349494558918951008657822342607930490145976005210270504662146935087065494800985678297142223374695422703802751733358176577615426268960089772682761691036839741790038242960468271102083217548915383242299421064774843685631003247040941593228767555, 12638532596286690536931793366027174524704520803329449580487191279815488768267957429530294962265166358110790727045268582010905398583737718923632418352855321816299569893548273253355886360912536787179555443675660626971767578053852932145368413925186775186130189034616600353605973889487478371018132444231428112459552495729029985844112822339751054120097879521401316189871038317733947080612839576942554900727309497216545611425178298041037192145491868916707298985731722657716924198526529317242874335474262264977345486046506312207009363930360413221163552704155627349181747911146069682199322481029869461996380115956283030128300646742, 14225693291135908811698481256861433804498034932741873120040292288731800711225001898773780895957051975452843038497064233160778994532883457153869851551779526684301330701780384146965897245766550605593704256474323407484601249890289826408468993061867651459097067836359352490280693500441683237739251760711968406953331646103425115971395938019983240456861118247563886738050381504046093561271969733387276846631761792397332823078606138333691834980274277899948370146839560961198618212477344071805085100489344286798011562967223308356031064641822482690629630439238535979705296303292099272303137067584575592241482073914160049339828743460, 1371670846041867260324589060779747235090520844266535521996198703027252534965066155432167957250347116898696089245834653043285897613533451342716539524134897244554432839433863280867709818564304583214122445966696514217618338208412200249320335077945902857539333897623931908357788289063897841985203344008004850311149383426025850199789717445826201731415077049801079165534704181238520325639719580742119306348369420916683290530533306355453512795294878930074341810793303241562580557691620348834633009439601498533767423479873465716693383171542209708107935387189837715680781850228484843541798561174770702316729791473055450285943188265, 14708623804859337495233293249705554627856957953621073620574738343860442527437860459714392963432307565548395191553067287274734757641150929665498184091033973576720183502674585730232215192920711432115081065232565013337995748491222320937509734212639300113206532377476575263455729130986937361555117756308715691421831641649823135341333402616684672914850677982415341526608702608573542769062092203386950581245889146839759080652674215267660170986778798088035444904448061916724833904274789061415486957713985215321172801596973918213065262786043657431578763182103447000231844339769996252181071717290376583199617702912965525367542660535, 2079525942186153669295901492783740853212676561024193444780638988637847835644756443586890166439134698718932408243774425537995619928125603250628129115417902964735855519616272717379878048344881168224345684347364945700147131969989821058820879460314431635876119848428938120985381125003300617209346969998813735787567448774119589168695501044320014748099471066312674185119281298743032855120434892720428182236503714739337394039640707118038361657304942328498599585592181382144837561952879360025526179800392653477378744457281856741910408517044085784236670891450567973147640935080531824447313097181533661742399531352379822738701176567, 14792590665641028843033432480061660678975535819902801605571661546859426944131644568533395689046584811184391064144364792722577364068548209812474918806539788935075918298444261756722804477814663215497569069435454115120970529083814165863023872402563758552891206856042823668630816466927169339616898566240975080602419989584571252545007212013771626517775440419830425518552096774200225677449669460551889774509420628915115620873014862248765180503211726719165513374467773188013372007320110305669595026735996749618153282645159688914676920961714313055226046583528196528706063553983176539656599868939612854821053695656456430891836046092, 5421429792702568956729448569045195983852090988415758953575732945204333711957283060401211013931083588517500706846881352630854446235353695717332891228089451477378334669684360562646633015073537524338852194521249427314890306475465753890159977531883008697154603946794774313081972383969295442439137905948514986021418741247625670140599363209300238798422485012201480741035076590484076842740075780444289079509316382144446939083621783753965961898295535663162366825928320927006075967490264774219761948688976913098380134041630258553195459377700387995095857287227516370666281688103676000985604139928039764842944488391533010282401307918, 16178649325955842402878726248274823977309882506287302051961519684678802473114984617129333886148676799264635697963162832407100014691313801065797257437738519413038009847443318468797712116507107655903883044657970891310434813181545857360877275166548832189441979343030869350342946775702769146866214177165615311698901131147756167307227871668925809119371545250957131383939530183858600239845959699502960614528416837991687740058988062457118493477726348647535783604491447947002705228049650535453941845139580036524797171208903103984021381203471446362051930563808412078372484826383291672504121158412234425121958956560049726681796458734, 12609070105293050032848354708018025837063434503582939534855910239145322982669910473099388994113585907117312785941621522138076245516915577287852137982922803644060389479313880830623331634893838694405730013003743693865572486882307987016754787497582569571661406019033781198714521464606337359283147168906981614965735718230451877685435341337703571146714065735073556120719072348605350825240780876718002822374738460929998616328204174997582615499347552490165673535936109614190286423405201342438329251427185192818400581782142365403936506839499607039824377039122860846979829061386657756765366423303110962894985948551557898044626520095, 9424965984496651484696657367909446260942288240190190698080921833233653936277820348366348390264424261125141209375609118804226748811202714702967509258633148036415861309844015290410849991983709975340404728355494662203464963072235301554629381315134034783443037192238889932533301386357067633343193806816389244330084958270436126743642138397636786107253658973748153321925404243737725838101876051556793957537338106495518601017626816023679179074471278491918165145736726928755193593981174950170246606456222849178073824126075666917676831714930509928718405241759798553287221291664744401366668653741945990878092081172185103150896602330, 15116293680355608338382791908385195283995972537295926894651657778746497438491427943524354548499488171820197683012030663683009969734274886185767682528288749245942824531167213740939529660288282528025448769877881201963613912521520383794047380940601728197607425184251757234478463578833143818325215615477550188629794292013102489486566656942696426311298741696919903494480394822253005781518237470439964919901355722461444434410078168995692467731258451461849270266711569207791040632693282795598661262568749935159035305150669987269220844848184218436833596127591160110003781920164166758213975872142293778849841543045307561185605113401, 1925238780806008102331032014237481353073397536634789799780429015027648664934529654073221644947817960511486112318301594817736082765502076327789930564296518837005007795961552049501019490821880634700284284306694114847827819156811008668558676520544849867590766448108687206550783084199492021214339226151215819239963158100824675703324701240211222614703150885619803722271810351872083128322252115758690757299997463743499088521978157395068004235755181332814982338144201686541896056301556512030112746666153349320356084364709773383265777676988901698155268493906326020459185891222641964911152490415118379628499580159035557298181418290, 6821849778594062649763965434134147407981452386318528626049695128123610596804507486709291218053525228591339504038628576822848502138629519482167041154933105202131743197025133753406343212154773378664369808778950824953150391692115439636038281207318564530422025116063083561199444521236903613135585947543910910387167551982579105450569703737345719081978256626998176599150666634267571212434728450900702104872971864246156985076624004994146096408054023255040510677521305488234666884264243967139738435724930192717598240505994041162031562208515957026565435496680211293045131394063363315639312247735761004084950672659526629560827232941, 11981658011637873125680072618645994877624974013490208181802570503366160145273496194862623908588507029909145260125047107768764622482979310794547412998167142447953991400201229952905629766207486104328013007982288279354665890858545171420935476023773195871424546693467474150593391025768275500016977515166160189274993869882233828204705286795205657154575481111744059893515156011082485636881326837499293773034052147746640263638446885444421593297652460492447419834930083193292556328827661748026267333937588974753235170684027180848719469966309281347273505332264604442713377431337824526264857750170389969931851540203502894039498691967, 11256187409460270898265956394919678546929858727894223405333146256596470748947568358990433496164501643161730637614822508248765153092768766403694929925847705408792551692872276134518982137483584503721024087826406608103314996701570229190632978246419763933567142024184547947234530444612320108228238688804560571233110645182028817928582954949635282409260517213694673281160430235903401583991245835254121494686959061154478141094037987083918064542081105776691719972726391443985512291367926752898233233685180826635774222221703327119039039619107375045711773427582069998788349194225275031270464603676060061131743763511360826998034100991, 3319411965977730047648576917115688681976487870497815679902781110387252550220069019764562095986350303663002203821987514988421271558817221111338171556585872726565037061707807664741784768360668802006071574833246269217766938363474498862500197198370431931173791572421237207825891865985215814966857698153030397761236161957563601153665960536567949074742904655863603013948776579645484745161923464067657660239853804008863759163376848796762923763270847767153196111649856562654450306169666851528000816678125042428968196740859821974508588002054755848189988129603586891365220858852353693110249092425685104763097043924139904088800060521, 12440733317606575382710352654318473546589355635168021140657311851351055049847357265508697455805212918041025852751144015875248385455958299170054295854074464215581465263695823276600100679497078078322749491562405691274733378272823429315886588020768610470548278605470535075891323522097959489061870147238336983777144580058079600244467447792703903044627942703163070641612348212379039433161926552680997068363633596337504852569005001761539244734999135715440517028678902856488108828144264464893776800718718769958123168739501612398053156833948455014893392750135833482573323635978924922526215270385957216940667132162533975033895346775, 5757567941375580530435243651475354104501304019243937132799740546112033707027787914785768694342613775393744981241875527473314336947343193046466811789827733032642693667836972992206328861262460815481283166148914250630615316898458133055858878316444987377662565209542565056651965583081675595077558270488418534841546646235033376395051972428946326063968947133466955959425308477840732694061795833483179676288375644160800443024134992004563418806064994731107175193062378828884502809042962669482278048331982443799467318391557500729421837035812255908651432139645293591708317718612904319634655922778481117799526048985085267704172550041, 9829609956686583539845069342696192764417537911788107771859991393028091055220219008364425207849530065035154708694451213195271189116553389726957933134001936390978467737576421151103158874895274463488487765290953286298411444402871366777853110162314320038942558116305509076778891448363467504402514360289853588404894996298931303558346072378994874744743151838536819125707671305088120463629820871750181161777604563619897177298201988691579822105396918784197227480834608483198525121412178838344219369353861507273954874828624243451208368171223558656148999897034543214094636582878880955458855203080241088957507238168846515021722590366, 903703112768796183752069095763743554139797329197818971787841058004305700873207795820933992676806887620939596382846897408637351844794124411428902053648778006381126009317839874111084800541365808374023555938251717267473357191672167482202178157424570290263028939328749310167594541509949940210031310343596411750505234867344384444828089529554118151805058227356571346033364555417594766601791035174426960534074575507876829870106496985014718717331094109927348344717736408835527237280542510019005294523453490783084257941123449565664192188834403616442808417208937363198937058818592325903996360057972740547659042534740843072009139249, 4563431876926279903130938771973599753940044870201518046127908129409343089167342982354018725080391717464418066015241113361936860070231381602919316276969174866674035834321486781239937851119742414306767123060674749136547608888260951563444903884008810600799956465626549802548489024365405139230435972233252715513445481429533830151912566960320815379604390194802689334888564099349600886696470080642472404932839931517971905017769157249769345864132437402613647889332517219347314966089012391356518890836394547508933891335220586269002333185336386567891310665204219719676264881128639830424174841904902298242722065731296746803365913815]
ct = b'\xb7\x91\xcd\x11\xdc\x8f\x89\xbe\x02x\xcd4U\xf6\xfaE\xee\xa6\x96a\xab\x08zw3\x1bo&\xc4\xc7\x00\x9b\xb7\x02_\xc0\xdd\xae\xa4\xf5\n\x15\x8e\xb5\x1fHUm\xe3Z\x92\x10Ys\xc9v\xf6\xee\x99'
iv = b'DO\xf4Kc\x1f?7'

def phi(x):
    return x + sqrt(x**2 - 1)
ord1 = (p-1)//r1
ord2 = (p+1)//r2
h1 = discrete_log(phi(K(magic_pi))^r1, phi(K(314159))^r1, ord=ord1)
h2 = discrete_log(phi(K(magic_e))^r2, phi(K(271828))^r2, ord=ord2)
h = min(
    crt([h1, h2], [ord1, ord2]),
    crt([-h1, h2], [ord1, ord2]),
    crt([h1, -h2], [ord1, ord2]),
    crt([-h1, -h2], [ord1, ord2]),
)


################################################## part2 decrypt
def magic_op(x, n):
    r0, r1 = 1, x
    for b in f"{n:b}":
        if b == "0":
            r1 = 2 * r0 * r1 - x
            r0 = 2 * r0**2 - 1
        else:
            r0 = 2 * r0 * r1 - x
            r1 = 2 * r1**2 - 1
    return r0


PR.<x> = PolynomialRing(F)
r0, r1 = 1, x
#4 = "100"
r0 = 2 * r0 * r1 - x
r1 = 2 * r1**2 - 1
r1 = 2 * r0 * r1 - x
r0 = 2 * r0**2 - 1
r1 = 2 * r0 * r1 - x
r0 = 2 * r0**2 - 1
f = r0

m = []
for i in tqdm(obfuscated_keys):
    if(magic_op(F(i), p-1) == 1):
        temp = magic_op(F(i), inverse(h//4,p-1))
        m += (f-temp).roots(multiplicities=False)
    else:
        temp = magic_op(F(i), inverse(h//4,p+1))
        m += (f-temp).roots(multiplicities=False)


################################################## part3 LLL and get flag
L = block_matrix(ZZ,[
    [1,Matrix(ZZ,m).T],
    [0,p]
])

L[:,:-1] *= 2^128
res = L.LLL()
for i in res:
    if(i[-1] != 0):
        key = long_to_bytes(abs(i[-1]))
        cipher = AES.new(key, AES.MODE_CTR, nonce=iv)
        flag = cipher.decrypt(ct)
        print(flag)
        break


#ictf{the_weird_magic_operation_is_not_so_magic_after_all..}

后面看discord有看到maple提了这个群的名字：

然后还有个师傅提供了篇论文，以后再看看吧：

http://wayback.cecm.sfu.ca/CAG/papers/Cheb.pdf

pacap*

题目描述：

1
2
3

The "capac" challenge from Crypto CTF 2024 can be directly solved by factorizing the modulus, but is it still solvable if the modulus is much larger?

Original challenge is made by @factoreal.

题目：

#!/usr/bin/env sage

from Crypto.Util.number import *
from flag import flag


def iscube(n, p):
    return pow(n, (p - 1) // gcd(3, p - 1), p) == 1


def issquare(n, p):
    return Mod(n, p).is_square()


def gen_prime(nbit, t):
    P = []
    for _ in range(t):
        while True:
            p = getPrime(nbit)
            if p % 3 * p % 4 == 3:
                P.append(p)
                break
    return P


def add(P, Q, c, n):
    # Add two points P and Q on curve x^3 + c*y^3 + c^2*z^3 - 3*c*x*y*z = 1 in Zmod(n)
    (x1, y1, z1) = P
    (x2, y2, z2) = Q
    x3 = (x1 * x2 + c * (y2 * z1 + y1 * z2)) % n
    y3 = (x2 * y1 + x1 * y2 + c * z1 * z2) % n
    z3 = (y1 * y2 + x2 * z1 + x1 * z2) % n
    return (x3, y3, z3)


def mul(P, g, c, n):
    # Scalar multiplication on curve
    (x1, y1, z1) = P
    (x2, y2, z2) = (1, 0, 0)
    for b in bin(g)[2:]:
        (x2, y2, z2) = add((x2, y2, z2), (x2, y2, z2), c, n)
        if b == "1":
            (x2, y2, z2) = add((x2, y2, z2), (x1, y1, z1), c, n)
    return (x2, y2, z2)


def keygen(nbit, r, s):
    p, q = gen_prime(nbit, 2)
    n, o = (
        p ^ r * q ^ s,
        p * q * (p ^ 2 + p + 1) * (q ^ 2 + q + 1) * (p - 1) ^ 2 * (q - 1) ^ 2,
    )
    e = randint(1, n)
    while gcd(e, o) != 1:
        e = randint(1, n)
    E = [
        p ^ (2 * (r - 1)) * q ^ (2 * (s - 1)) * (p ^ 2 + p + 1) * (q ^ 2 + q + 1),
        p ^ (2 * (r - 1)) * q ^ (2 * (s - 1)) * (p - 1) ^ 2 * (q - 1) ^ 2,
        p ^ (2 * (r - 1)) * q ^ (2 * (s - 1)) * (p ^ 2 + p + 1) * (q - 1) ^ 2,
        p ^ (2 * (r - 1)) * q ^ (2 * (s - 1)) * (p - 1) ^ 2 * (q ^ 2 + q + 1),
    ]
    D = [inverse(e, _) for _ in E]
    return (n, e), (p, q, D)


def encrypt(m, pubkey):
    (n, e) = pubkey
    (x, y) = m
    c = ((1 - x ^ 3) * inverse(y ^ 3, n)) % n
    enc = mul((x, y, 0), e, c, n)
    return enc


nbit, r, s = 1024, 4, 6
pubkey, _ = keygen(nbit, r, s)

l = len(flag)
m = (bytes_to_long(flag[: l // 2]), bytes_to_long(flag[l // 2 :]))
assert m[0] < pubkey[0] and m[1] < pubkey[0]
enc = encrypt(m, pubkey)

print(f"pubkey = {pubkey}")
print(f"enc = {enc}")
print(f"l = {l}")

心酸，自己明明还改过这题，这次没做出来，因为明文实在是太大了。

改过的那个初级版在：Capac’s revenge | NSSCTF

总的来说就是由于明文较小，所以可以利用曲线方程和已知点去构建等式，等式有小根所以可以造格或二元copper。一些技巧是：

直接造等式的话度会比较大，所以代换变量可以得到度仅为2的等式，利于copper
由于(0,0)是平凡解，所以需要自己找规约出来的一些向量，转化为多项式后观察他的形式，从而确定接下来的求解办法，具体直接看maple的解释吧：pacap

赛中一直没想到怎么处理好这个平凡解，当时想的是利用明文前缀来确定根，但这样的代价是度会增高到4，不利于copper了，上界就不太够。密码挑战赛过了太久，把自己手提多项式这一招都给忘记了