[GreyCTF’23] crypto part

baby crypto

caesar sign

whuo{squi4h_s1fx3h_v0h_co_i4b4T}

grey{caes4r_c1ph3r_f0r_my_s4l4D}

The Vault

There is only one check_keys function here, the encryption cannot be broken, as long as the check_keys is passed.

from hashlib import sha256
from Crypto.Util.number import long_to_bytes
from Crypto.Cipher import AES
from Crypto.Random import get_random_bytes
from math import log10

FLAG = "grey{fake_flag}"

n = pow(10, 128)
def check_keys(a, b):
    if a % 10 == 0:
        return False

    # Check if pow(a, b) > n
    if b * log10(a) > 128:
        return True
    return False

def encryption(key, plaintext):
    iv = "Greyhats".encode()
    cipher = AES.new(key, AES.MODE_CTR, nonce = iv)
    return cipher.encrypt(plaintext)

print("Welcome back, NUS Dean. Please type in the authentication codes to open the vault! \\
")

a = int(input("Enter the first code: "))
b = int(input("Enter the second code: "))

if not check_keys(a, b):
    print("Nice try thief! The security are on the way.")
    exit(0)

print("Performing thief checks...\\
")
thief_check = get_random_bytes(16)

# Highly secure double encryption checking system. The thieves stand no chance!
x = pow(a, b, n)
first_key = sha256(long_to_bytes(x)).digest()
second_key = sha256(long_to_bytes(pow(x, 10, n))).digest()

if thief_check == encryption(first_key, encryption(second_key, thief_check)):
    print("Vault is opened.")
    print(FLAG)
else:
    print("Stealing attempts detected! Initializing lockdown")

As long as a=1, b is optional, but it is required that a cannot be 1, but it can be n + 1

a = n + 1
b = 2

#grey{th3_4n5w3R_T0_Th3_3x4M_4nD_3v3ry7H1N6_1s_42}

GreyCat Trial

two primality tests

from random import randint

FLAG = "grey{fake_flag}"

print("Lo and behold! The GreyCat Wizard, residing within the Green Tower of PrimeLand, is a wizard of unparalleled prowess")
print("The GreyCat wizard hath forged an oracle of equal potency")
print("The oracle hath the power to bestow upon thee any knowledge that exists in the world")
print("Gather the requisite elements to triumph over the three trials, noble wizard.")
print()

a = int(input("The first element: "))
b = int(input("The second element: "))
print()

all_seeing_number = 23456789

# FIRST TRIAL
if b <= 0:
    print("Verily, those who would cheat possess not the might of true wizards.")
    exit(0)

if pow(all_seeing_number, a - 1, a) != 1:
    print("Alas, thy weakness hath led to defeat in the very first trial.")
    exit(0)

# SECOND TRIAL
trial_numbers = [randint(0, 26) for i in range(26)]

for number in trial_numbers:
    c = a + b * number
    if pow(all_seeing_number, c - 1, c) != 1:
        print("Thou art not yet strong enough, and thus hast been vanquished in the second trial")
        exit(0)

#THIRDTRIAL
d = a + b * max(trial_numbers)
if (d. bit_length() < 55):
    print("Truly, thou art the paramount wizard. As a reward, we present thee with this boon:")
    print(FLAG)
else:
    print("Thou art night, but thy power falters still.")

This seems to be a simple question, but I haven’t found a solution, and then I read two works of WP

In Primes in Arithmetic Progression Records

There are a bunch of prime numbers made by others, just choose one that suits the size.

”’
According to this page tracking records for primes in arithmetic progression, the smallest known end for an AP-26 is:

3486107472997423 + 1666981·23#·n (12783396861134173)

We technically need an AP-27, but will have to work with this because the best known AP-27 is too big. We note that the success rate is approximately
, and can just keep retrying until it works.
”’
a = 3486107472997423
b = 371891575525470

Another method is a blasting method, which looks at the probability of success in a small range. Since these 26 numbers are randomly selected, sometimes some of them do not appear, so it is not necessary to pass all the tests. It can be successful after a few more attempts. .

from random import randint

def get_probability(a, b):
    all_seeing_number = 23456789
    trial_numbers = [i for i in range(26)]
    successes = 0
    for number in trial_numbers:
        c = a + b * number
        if pow(all_seeing_number, c - 1, c) == 1:
            successes += 1
    
    return successes / len(trial_numbers)

for i in range(1,50):
    p = get_probability(i, 2)
    print(i, p)

#a=3, b=2, the success rate is 84%, and it can be successful after multiple runs

EncryptService

The AES_CTR mode is to encrypt the counter and XOR it with the plaintext. Obviously, if the ctr is the same and then XOR it again, it will be returned, but the key is 256. Try one by one.

import os
from Crypto.Cipher import AES
from hashlib import sha256

FLAG = "grey{fake_flag_please_change_this}"
assert(len(FLAG) == 40)

secret_key = os.urandom(16)

def encrypt(plaintext, iv):
    hsh = sha256(iv).digest()[:8]
    cipher = AES.new(secret_key, AES.MODE_CTR, nonce=hsh)
    ciphertext = cipher.encrypt(plaintext)
    return ciphertext.hex()

print("AES is super safe. You have no way to guess my key anyways!!")
print("My encryption service is very generous. Indeed, so generous that we will encrypt any plaintext you desire many times")

try:
    plaintext = bytes.fromhex(input("Enter some plaintext (in hex format): "))
except ValueError:
    print("We are incredibly generous, yet you display such selfishness by failing to provide a proper hex string")
    exit(0)

for i in range(256):
    ciphertext = encrypt(plaintext, i.to_bytes(1, 'big'))
    print(f"Ciphertext {i}: {ciphertext}")

print()
print("We will reward a lot of money for the person that can decipher this encrypted message :)")
print("It's impossible to decipher anyways, but here you go: ")
print("Flag: ", encrypt(FLAG. encode("ascii"), os. urandom(1)))

from pwn import xor
enc = bytes.fromhex('90a9cb7f769ae85e8619188c3c1a2faa7817cd26472df0058358d7724cad5fe03b50bbe781061962')
for v in c:
    t = bytes.fromhex(v)
    print(xor(t,enc))

#grey{0h_m4n_57r34m_c1ph3r_n07_50_53cur3}

OT

This question needs to find the decomposition of two numbers n, n + 1, look at WP, or two,

import secrets
import hashlib
from Crypto.Util.number import isPrime, long_to_bytes

FLAG = b'grey{fake_flag}'

e = 0x10001

def checkN(N):
    if (N < 0):
        return "what?"
    if (N. bit_length() != 4096):
        return "N should be 4096 bits"
    if (isPrime(N) or isPrime(N + 23)):
        return "Hey no cheating"
    return None
    
def xor(a, b):
    return bytes([i ^ j for i,j in zip(a,b)])

def encrypt(key, msg):
    key = hashlib.shake_256(long_to_bytes(key)).digest(len(msg))
    return xor(key, msg)

print("This is my new Oblivious transfer protocol built on top of the crypto primitive (factorisation is hard)\\
")
print("You should first generate a number h which you know the factorisation,\\
")
print("If you wish to know the first part of the key, send me h")
print(f"If you wish to know the second part of the key, send me h - {23}\\
")

N = int(input(("Now what's your number: ")))

check = checkN(N)
if check != None:
    print(check)
    exit(0)

k1, k2 = secrets.randbelow(N), secrets.randbelow(N)
k = k1^k2

print("Now I send you these 2 numbers\\
")
print(f"pow(k1, e, N) = {pow(k1, e, N)}")
print(f"pow(k2, e, N + 23) = {pow(k2, e, N + 23)}\\
")

print("Since you only know how to factorise one of them, you can only get one part of the data :D\\
")
print("This protocol is secure so sending this should not have any problem")
print(f"flag = {encrypt(k, FLAG).hex()}")
print("Bye bye!")

The first is the website

n1_fact = [7, 462770317, 5694507743]
n2_fact = [2, 2, 2, 3, 41, 857, 1559, 339023, 23432090796364571547475280912492243278264760950356520438632049635287425126593349 660046776622291610199504830833665844854585481382804490933418620023789779541679334973682190075976037554031065044573425247313 781521410645070218793211395622196624729724747761222526319534097612382151606132099715581737418030269792542142107275281422165 538988760302911986261817842656075999959087260455094877187994621817717280900382380689620567776449929888929381240089924389505 494723450444268556388338775068767283127821611676477472908247847486967542461598921368144414883143254035627303671449179669907 364000330173529899253349855949452958876602601449689091914651527076993036076938542988651035494707402312427673444889749838442 088912661944784741707420484769736210368925305853458613146762229677003813394680700335809371585269441178687211560052902783613 212424990227807701096298878905699609683263949195971575919850915454022575942108216634015652362329816507109500407997625863853 353530998407997018386116312263159559703085780317278038055605492540489679322501616871733411346000166841837282905403258144988 558331846658513823404855075606117285192838379886744977036921426673728144419200581766794798756715543223758428688669160301603 61839169885024648792639108310409]

n1 = mult(n1_fact)**64
n2 = mult(n2_fact)

print(n1. bit_length())

assert n1 + 23 == n2

import itertools
import gmpy2

phi1 = itertools.product([(v-1)*v**63 for v in n1_fact])
phi2 = itertools. product([v-1 for v in n2_fact])
d1 = invert(e,phi1)
d2 = invert(e,phi2)

Second, it makes sense to generate a number of 23*k*2^m so that + 1 is a prime number, and both decompositions are available

for i in range(1, 1<<24, 2):
    order = 4096-(23).bit_length()-i.bit_length()
    p = i*2**order + 1
    if is_prime(p):
        print(i)
        break

#2013

PLCG

I watched WP for a long time, but I didn’t understand it

Combine 3, 80 and two random numbers, and after a bunch of calculations, %6 gets a number encrypted

import secrets
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad

FLAG = b'grey{fake_flag}'

while True:
    sample = [3, 80] + [secrets. randbelow(256) for _ in range(2)]
    if len(sample) == len(set(sample)) and 0 not in sample:
        break

def getBiasRandomByte():
    return secrets.choice(sample)

def getRandomByte():
    n = 0; g = 0
    for _ in range(20):
        n + = getBiasRandomByte() * getBiasRandomByte()
    for _ in range(20):
        g = (g + getBiasRandomByte()) % 256
    for _ in range(n):
        g = (getBiasRandomByte() * g + getBiasRandomByte()) % 256
    return g

def encrypt(msg):
    key = bytes([getRandomByte() for _ in range(6)])
    cipher = AES.new(pad(key, 16), AES.MODE_CTR, nonce=b'\xc1\xc7\xcc\xd1D\xfbI\x10')
    return cipher.encrypt(msg)

print("Hello there, this is our lucky numbers")
print(" ".join(map(str,sample)))

s = int(input("Send us your lucky number! "))

if not (0 <= s <= 10):
    print("I dont like your number :(")
    exit(0)

for i in range(s):
    print("Here's your lucky flag:", encrypt(FLAG).hex())

The first method is to blast two random numbers. When they are both multiples of 16, the person will get 16 and 64. These operations will have a high probability of 0, 128, 208, and then you can use these 6 numbers to Burst result (it’s not even 256 numbers)

#We find that the byte ends up being one of [3, 80, 16, 64] about 61% of the time, and one of [0, 128, 208] another 12% of the time. So to make this simple we hope that our key only contains bytes from these 7 possible values.
cts = '''
247692734a39dbf895bc7ce9a38871551c18d744810b1920e6170fa92ccc4b3e2fe6a95ae72292110b78c5065bec72440b317a5ddb296126
c1a183e98205ddefa55a35925570493198928a1bfccdae69846dd12dec76b05316796efa9c76096c5774ce32766c2421a7c4fe7aa73f191f
d287ef4d396311abe5403b887c6c5bc85f081cf132c84bf0fe5ae536d815db70c8b233f313a4398606b1b8f6e9e6888fee43d12f405c60d3
9e708b90c66feea44ee33cec21f0eb6e18d32bd39d0923fbbd72dc19b890f87582b70467c1b27ec88811db24f6029d93650078b67a9b050
66abaaef5630322ceaf9d64b1ec98843695446f9767e0bd632e661a7b2e9d1dbd0f303913695392084207d35032585ad3f3f59d1b505450a
9d6e07c4054e6244654cdb7d0a4b0d0f862d4501e93a2d2e63afe277438bab86a4865399be3be282463d03b344aadaab115706b164b166da
12af626ab1d20e221cb4950e5e76d994ec6f4e0645a7ccd414e70ea4740bdf0998d0783e5bc085acba776d7596442509077c971247c16100
cbef3197bd8b5fca426b6d3f5ad4d95a475d399a802eed6c270bba652df091d0b450ca8bf8ff1c13b3e5cbd85d6fd3ed2353b33eddf4cfa1
5b2111328b099a7b9857b886348a8c59b7a1a6004e6837e312507b0b338be1fb077cd7041284d3c817dd2961db5bf21e5a6605c92cd52067
ae20d773cf0fe43be929f52a359cf9e7afe11648f58230cf53fd691051188b66097c5eaba03e24b234b31eeffdf3e5144d1b18a6386b2b77
'''

dic = {x[:5]:x[5:] for x in map(bytes.fromhex, cts.split())}
candidate_bytes = [3, 80, 16, 64, 0, 128, 208]
for key in cartesian_product([candidate_bytes] * 6):
    cipher = AES.new(pad(bytes(key), 16), AES.MODE_CTR, nonce=b'\xc1\xc7\xcc\xd1D\xfbI\x10')
    if tail := dic.get(cipher.encrypt(b'grey{')):
        print(b'grey{' + cipher.encrypt(tail))
        break

Another method is complicated, but it is good to save a board. I really don’t understand it, although there are also blasting behaviors, but I feel that the success rate will be relatively high. And matrix operations are not time-consuming.

from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from sage.all import *
from pwn import *

def decrypt(msg, key):
    cipher = AES.new(pad(key, 16), AES.MODE_CTR, nonce=b'\xc1\xc7\xcc\xd1D\xfbI\x10')
    return cipher.decrypt(msg)

while True:
    r = remote("localhost", 9999)
    r.recvuntil("our lucky numbers\\
")
    sample = list(map(int, r. recvline(). decode(). strip(). split()))

    trans = [[0 for _ in range(2**8)] for _ in range(2**8)]

    for i in sample:
        for j in sample:
            for k in range(2**8):
                trans[k][(j * k + i) % 256] + = (1)/(len(sample)^2)

    for i in range(2**8):
        trans[i][i] -= 1
        trans[i].append(1)

    T = Matrix(QQ, trans)

    T = T.transpose()

    v = list(T.solve_right(vector([0 for _ in range(256)] + [1])))
    for i in range(len(v)):
        v[i] = (v[i], i)

    v. sort(key=lambda x : x[0])

    # for i in range(len(v)):
    # print(v[i][0].n(50), v[i][1])

    k = sum(map(lambda x : x[0], v[-12:])).n(50)

    print(sample)
    print(k)
    if (k < 0.4):
        r. close()
        continue

    arr = list(map(lambda x : x[1], v[-12:]))

    
    print(arr)

    r. sendline("10")

    for _ in range(10):
        r.recvuntil("lucky flag: ")
        c = bytes.fromhex(r.recvline().decode())

        for i in range(12**6):
            key = []
            for _ in range(6):
                key.append(int(arr[i % 12]))
                i = i // 12
            key = bytes(key)
            if b'grey{' in decrypt(c, key):
                print(decrypt(c, key))
                exit(0)
    r. close()

Encrypt

The program is short and the problem is two equations and three unknowns. But sage is very good at this. It’s just that I don’t know how to do it.

from Crypto.Util.number import bytes_to_long
from secrets import randbits

FLAG = b'fake_flag'

p = randbits(1024)
q = randbits(1024)

def encrypt(msg, key):
    m = bytes_to_long(msg)
    return p * m + q * m**2 + (m + p + q) * key

n = len(FLAG)
s = randbits(1024)

print(f'n = {n}')
print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {encrypt(FLAG[:n//2], s)}')
print(f'c2 = {encrypt(FLAG[n//2:], s)}')

The first is to directly construct the matrix and then reduce (save)

n = 60
p = 15408657859416945743559567566664389573481184108057255876537350723657802821659174753384992375146919159637766100402904687 790404246077891910362521025944892505140356865403517209455305968662093899515032367169061206750214975033421764043088183780339 8594614204799922967620005040202036583050736150941842152536365544084
q = 1250174636287087861120458987839895196865186410187872928923908778416683067461467023019811722637291022524535070062409739 113240331062440683766434356221581283098265495422040342578715455581858414584072547998848298203199497562207817176464507606425 11971882897039183232753628829418868493229485015468373205449789812260
c1 = 3111885028909815283216104993097456444079267351619958478448486452827948150061294860152670606262127626271121049773956298 749163366481428972525504648526279860451062694182718791203428740212855001879816533134386919853913769290345111899353897778876 894591202698084683225401055807380646446117252229565361463582951691262030390107489553670449755093380565351299341378443181403 497039935390831508373478364168884588733517575641545232005766629379422252219297024704577505306257313000215495922128557197964 5935259561842756575513382500001710093979669436220490166791279222321068474420333628707932126068199272570200432284026433343662 8467610
c2 = 3111885028909815283216104993097456444079267351619958478448486452827948150061294860152670606262127626271121049773956298 749163366481428972525504648526279860451062694181767266083212784704191701856690224146527038845821028929958795825682437531292 071679452183510872403400227733324566095102739754459125611737146294592506322787705254350516226033137762796185569840610290976 451895539878836643226812347193092287079005928952624183203241304693333803200516367758562981626466827341612650617500409148642 122590024776724731158706142243659360080685470384274033437993659043199188472198505736682545646798646293023698623927593565681 0387114


from Crypto.Util.number import long_to_bytes

var('a b k')
f = p * a + q * a**2 + (a + p + q) * k - c1
g = p * b + q * b**2 + (b + p + q) * k - c2

h = f.resultant(g, k).expand()

print(h)

arr = [
    abs(h. coefficient(a, 2). coefficient(b, 1)),
    abs(h. coefficient(a, 2). coefficient(b, 0)),
    abs(h. coefficient(a, 1). coefficient(b, 0)),
    abs(h. coefficient(a, 0). coefficient(b, 1)),
]

constT = h.coefficient(a, 0).coefficient(b, 0)

X = 2^200

M = [
    [1, 0, 0, 0, arr[0], 1, 0, 0, 0, 0],
    [0, 1, 0, 0, arr[1], 0, 2^(n//2 * 8), 0, 0, 0],
    [0, 0, 1, 0, arr[2], 0, 0, 2^(n//2 * 8 * 2), 0, 0],
    [0, 0, 0, 1, arr[3], 0, 0, 0, 2^(n//2 * 8 * 2), 0],
    [0, 0, 0, 0, constT, 0, 0, 0, 0, 2^(n//2 * 8 * 3)],
]

M = Matrix(ZZ, M)

for i in M:
    print(i)

print()

L = M. LLL()[0]

a = abs(L[2])
b = abs(L[3])

print(long_to_bytes(a) + long_to_bytes(b))

The second solution, this person may be a mathematician.

First find a way to make a model to remove the key, and then solve it directly with copperSmith

#c = p*m + q*m**2 + (m + p + q)key
#m + p + q divide c + (p + q)(p-p*q-q**2) with c + (p + q)(p-p*q-q**2) as the modulo, use CopperSmith to solve

def solve(c):
    x = Zmod(c + (p + q)*(p-p*q-q**2))['x'].gen()
    m = (x + p + q). small_roots(X=2**240, beta=1/3)[0]
    return long_to_bytes(int(m))
print(solve(c1) + solve(c2))

Fancy

a polynomial encryption

from Crypto.Util.number import getPrime
from secrets import randbits
from hashlib import shake_256

FLAG = b'?'

p = 2^29 - 33

F.<x,y> = GF(p)[]
G.<x,y> = F.quotient(F.ideal([x^3 - y^2 + 1, y^7 - 11]))

def xor(a, b):
    return bytes([i ^^ j for i, j in zip(a,b)])

def encrypt_flag(s):
    secret = b",".join(map(lambda x : str(x).encode(), s.lift().coefficients()))
    key = shake_256(secret).digest(len(FLAG))
    return xor(key, FLAG)

g = 1 + x + y

a = randbits(1024); A = g^a
b = randbits(1024); B = g^b
S = A^b

f = open("output.txt", 'w')

f.write(f"c = {encrypt_flag(S).hex()}\\
")
f.write(f"A = {A}\\
")
f.write(f"B = {B}\\
")

'''
c = cd519d06bf85ecafdb84111ab63d509e49ffb8cfc78fee4f4cbc3c007a96d2060613f5c0a208325569bf3476d4ea839c10d4667d3dfb5d0d650d79153b
A = -210623603*x^2*y^6 + 223917991*x^2*y^5 - 234939507*x*y^6 - 103510738*x^2*y^4 - 255193765*x*y^5 + 245323126 *y^6 - 41129482*x^2*y^3 + 3293396*x*y^4 + 265040169*y^5 - 175348566*x^2*y^2 - 8922481*x*y^3 - 76227659*y ^4 - 127516194*x^2*y - 97886874*x*y^2 - 207888821*y^3 - 123290485*x^2 + 93703664*x*y - 146824287*y^2 - 229640558*x - 5428142*y - 185137098
B = 155912203*x^2*y^6 - 50064221*x^2*y^5 + 107681922*x*y^6 - 249464027*x^2*y^4 - 13560651*x*y^5 - 178499062* y^6 + 75225430*x^2*y^3 + 241399622*x*y^4 + 8431316*y^5 - 15433512*x^2*y^2 - 80127041*x*y^3 - 199374666*y^ 4 + 203619258*x^2*y + 20681482*x*y^2 - 92775952*y^3 - 46663623*x^2 + 171776018*x*y - 164809964*y^2 - 186955302*x + 235677332*y - 173567532
'''

Let’s save this question first, and it may not be useful if I don’t understand it.

from hashlib import shake_256

def xor(a, b):
    return bytes([i ^^ j for i, j in zip(a,b)])

def decrypt(s, c):
    secret = b",".join(map(lambda x : str(x).encode(), s.coefficients()))
    key = shake_256(secret).digest(len(c))
    return xor(key, c)

p = 2^29 - 33

d1 = 3
d2 = 7

pari.allocatemem(42949672960)

F = PolynomialRing(GF(p), 'a', d1 * d2 + 2)

variables = F. gens()
x = variables[0]
y = variables[1]

G = F.quotient(F.ideal([x^d1 - y^2 + 1, y^d2 - 11]))

variables = G. gens()
x = variables[0]
y = variables[1]

g = 1 + x + y

c = bytes.fromhex("cd519d06bf85ecafdb84111ab63d509e49ffb8cfc78fee4f4cbc3c007a96d2060613f5c0a208325569bf3476d4ea839c10d4667d3dfb5d0d650d 79153b")
A = -210623603*x^2*y^6 + 223917991*x^2*y^5 - 234939507*x*y^6 - 103510738*x^2*y^4 - 255193765*x*y^5 + 245323126 *y^6 - 41129482*x^2*y^3 + 3293396*x*y^4 + 265040169*y^5 - 175348566*x^2*y^2 - 8922481*x*y^3 - 76227659*y ^4 - 127516194*x^2*y - 97886874*x*y^2 - 207888821*y^3 - 123290485*x^2 + 93703664*x*y - 146824287*y^2 - 229640558*x - 5428142*y - 185137098
B = 155912203*x^2*y^6 - 50064221*x^2*y^5 + 107681922*x*y^6 - 249464027*x^2*y^4 - 13560651*x*y^5 - 178499062* y^6 + 75225430*x^2*y^3 + 241399622*x*y^4 + 8431316*y^5 - 15433512*x^2*y^2 - 80127041*x*y^3 - 199374666*y^ 4 + 203619258*x^2*y + 20681482*x*y^2 - 92775952*y^3 - 46663623*x^2 + 171776018*x*y - 164809964*y^2 - 186955302*x + 235677332*y - 173567532

f = 0
for i in range(d1):
    for j in range(d2):
        f + = variables[2 + d2 * i + j] * x^i * y^j

def hom(k):
    M = [[0 for _ in range(d1 * d2)] for _ in range(d1 * d2)]
    t = (f * k).lift()
    for i in range(d1):
        for j in range(d2):
            for k in range(d1 * d2):
                M[k][d2 * i + j] = t.coefficient({x:i, y: j, variables[2 + k]: 1})
    return Matrix(GF(p), M)
            
G = hom(g)
AA = hom(A)
print(p)
print(G)
gg = G.charpoly()
n = len(G.rows())

factors = factor(gg)

val = []
mods = []

order = 1

for f in factors:
    print(f)
    FF = GF(p ^ f[0].degree())
    root = f[0].change_ring(FF).roots()[0][0]
    v = (G.change_ring(FF) - root * 1).right_kernel_matrix().rows()[0]
    P = [v] + [[1 if i == j else 0 for j in range(n)] for i in range(n - 1)]
    P = Matrix(FF, P).transpose()
    T1 = P^-1 * G.change_ring(FF) * P
    T2 = P^-1 * AA.change_ring(FF) * P
    o = T1[0][0].multiplicative_order()
    if (lcm(order, o) == order):
        continue
    order = lcm(order, o)
    val.append(T2[0][0].log(T1[0][0]))
    mods.append(T1[0][0].multiplicative_order())

a = crt(val, mods)

print(order)

s = (B^a).lift()
print(s)
print(decrypt(s, c))

QRSA

a custom operation

from Crypto.Util.number import bytes_to_long
from secret import qa, qb, pa, pb

FLAG = b'fake_flag'

class Q:
    d = 41
    def __init__(self, a, b):
        self.a = a
        self.b = b
    
    def __add__(self, other):
        return Q(self.a + other.a, self.b + other.b)
    
    def __sub__(self, other):
        return Q(self.a - other.a, self.b - other.b)
    
    def __mul__(self, other):
        a = self.a * other.a + Q.d * self.b * other.b
        b = self.b * other.a + self.a * other.b
        return Q(a, b)

    def __mod__(self, other):
        #Implementation Hidden
        #...
        return self
    
    def __str__(self) -> str:
        return f'({self.a}, {self.b})'
    
def power(a, b, m):
    res = Q(1, 0)
    while (b > 0):
        if (b & 1): res = (res * a) % m
        a = (a * a) % m
        b //= 2
    return res

p, q = Q(pa, pb), Q(qa, qb)
N = p * q
m = Q(bytes_to_long(FLAG[:len(FLAG)//2]), bytes_to_long(FLAG[len(FLAG)//2:]))
e = 0x10001
c = power(m, e, N)

print(f"N_a = {N.a}")
print(f"N_b = {N.b}")
print(f"C_a = {c.a}")
print(f"C_b = {c.b}")
print(f"e = {e}")
print(f"D = {Q.d}")

Follow the official WP of a paper

from decimal import Decimal, getcontext

getcontext().prec = int(10000)

class Q:
    d = 41
    def __init__(self, a, b):
        self.a = a
        self.b = b
    
    def __add__(self, other):
        return Q(self.a + other.a, self.b + other.b)
    
    def __sub__(self, other):
        return Q(self.a - other.a, self.b - other.b)
    
    def __mul__(self, other):
        a = self.a * other.a + Q.d * self.b * other.b
        b = self.b * other.a + self.a * other.b
        return Q(a, b)

    def __mod__(self, other):
        r = Decimal(int(other.a * other.a - Q.d * other.b * other.b))
        q = self * Q(other.a, -other.b)
        qa = int((Decimal(int(q.a))/r).to_integral_exact())
        qb = int((Decimal(int(q.b))/r).to_integral_exact())
        res = self - Q(qa, qb) * other
        return res
    
    def __str__(self) -> str:
        return f'({self.a}, {self.b})'
    
def power(a, b, m):
    res = Q(1, 0)
    while (b > 0):
        if (b & 1): res = (res * a) % m
        a = (a * a) % m
        b //= 2
    return res

N_a = 261324057144139219596408863098226134968282164561349739622674297185009286204968271412335502961244860925430379669090964 659494606965071932042155030708246030510378519877273227357102052900397432039723709669152280471270651203071575364015566865968 409306731918526515354523639247213449642838226660009038379761465394222193633292917555730339165624135111780883395991825340401 2245633586322491783496235954011173498460231177697737092488315432823871012224368640000000
N_b = 406631291381063062708368640624433195177629887128324992156536215422427085251271158548246052765619573442134462500652616 281986273622217404519958464200902599497611719198311591180368508835389781999428982410097278062504076636059232055783729252448 502542597951710294264137195997893054083787667027206495381119048279226753306334118272352371363733528942151156768581101905518 532465160584386180402709606771189313858666352673319676040954150310530906188677120000000
C_a = 254871119458390524283848290007829485919988248437522996471555046979076741670672541195336284572498300255882171067925849 998296045359879807463179675066377484541569265058935251376587089487817076943508768322033098657361497452969018779293131647587 998480926794160636549348127778518407632072048764456580890940382159315010156880344607580871500263246332984174917929582368636 1086890490703942659897558782785569910876849941888829825694107185482012864247559426111336
C_b = 400941158148299866665115436146084555297152646914223433988293961893848206718639579342053294961462797881591789534709492 717097892667288044693824228320005182068933966525404665323301134912609777110824069569544060608441451336249895977866445507357 131208911196230972379132737483251711155975474018188763433151191428844929401881703566513896999328525340678378000286116960582 957867857836600614501387296599091266404311307529322130111164410987643652390537358307965
e = 65537

N = Q(N_a, N_b)
c = Q(C_a, C_b)

f = factor(N.a * N.a - Q.d * N.b * N.b)
print(f)

ord1 = 1
ord2 = 1

for i in f:
    ord1 *= (i[0] - 1)**2 * (i[0]**2 - 1) * i[0]**i[1]
    ord2 *= (i[0] - 1) * i[0]**(i[1] - 1)

d1 = int(inverse(e, ord1))
d2 = int(inverse(e, ord2))

m1 = power(c, d1, N)
m2 = power(c, d2, N)

print(N)
print(c)
print(long_to_bytes(m1.a) + long_to_bytes(m1.b))
print(long_to_bytes(m2.a) + long_to_bytes(m2.b))

This kind of paper, if you don’t understand the paper during the competition time, you can’t write it, and you don’t know which paper it is.

It’s still another solution of that big cow, even better, in fact, it’s just a sentence of F.quo(F.gen()**2-D)((C_a,C_b))

e = 65537
D = 41

N = N_a**2 - D*N_b**2
F = Zmod(N)['x']
C = F.quo(F.gen()**2-D)((C_a,C_b))

phi = euler_phi(N)
g = gcd(list(C**phi-1) + [N_a,N_b])
d = int(pow(e,-1,phi))
print(b''.join(long_to_bytes(int(x%g)) for x in C**d))