BCACTF 2.0 | Rsatrix 5

#bcactf2

import binascii

# future server implementer (todo ed delete this): all of these should be regenerated on every server connection
# also todo, you probably want to put a POW on this problem

print("Starting...")
e = 65537
p = 65538
while (p-1) % e == 0:
    p = random_prime(2^401, false, 2^400)
q = 65538
while (q-1) % e == 0:
    q = random_prime(2^401, false, 2^400)
n =  p * q
d = int(Zmod((p-1)*(q-1))(e)^-1)
N = 64

R = Zmod(n)
MS = MatrixSpace(R, N, N)
S = SymmetricGroup(N)
running = True
while running:
    try:
        s = 0
        while s.order() < 2000:
            s = S.random_element()
        P = MS(s.matrix())
        running = false
    except:
        continue
C = MS([randrange(n) for i in range(N*N)])
print("Calculating G...") 
G = C * P * C^-1

def encrypt(m):
    M = m * G
    return (M^e).list()

with open("flag.txt", "r") as f:
    flag = f.read().strip().encode("ascii")
m = int(binascii.hexlify(flag), 16)

print("Encrypting...")
mats = {"G" : G, "E" : MS(encrypt(m))}
vals = {"e" : e, "d" : d, "n" : n}
done = {"A" : False, "M" : False, "X" : False, "D" : False, "U" : False, "N" : False, "T" : False}


print("""
Our calculator demo has gotten pretty expensive.
Given you're not a paying customer or anything, we decided it was fair to
only allow one of each type of operation per connection.
Try them all for the full experience!
Also, d is secret now. Oops! We've added integer operations to compensate.
""")
print(f"n = {n}")

while True:
    print("Would you like to print the traces of your stored matrices (P), list your stored integers (L), \nadd two matrices (A), multiply two matrices (M), take a matrix power (X), \nadd two integers (D), multiply two integers (U), exponentiate two integers mod n (N), \nsave the trace of a matrix (T), or quit (Q)?")
    try:
        l = input(">>> ").strip().upper()
        if len(l) > 1:
            print("You inputted more than one character...")
        elif l == "Q":
            print("We hope you enjoyed!")
            exit()
        elif l == "P":
            print("Here the traces of your matrices:")
            for k in mats:
                print(k + ": " + str(mats[k].trace()))
        elif l == "L":
            print("Here is your list of integers:")
            print(list(vals.keys()))
        elif l == "A" and not done["A"]:
            print("What is the name of the first matrix you would like to add?")
            A = input(">>> ").strip()
            print("What is the name of the second matrix you would like to add?")
            B = input(">>> ").strip()
            C = mats[A]+mats[B]
            done["A"] = True
            print("The trace of their sum is: " + str(C.trace()))
            print("Would you like to save this matrix? (Y/N)")
            I = input(">>> ").strip().upper()
            if I == "N":
                continue
            print("What would you like the name of the matrix to be?")
            N = input(">>> ").strip()
            mats[N] = C
            print("Matrix saved.")
        elif l == "M" and not done["M"]:
            print("What is the name of the first matrix you would like to multiply?")
            A = input(">>> ").strip()
            print("What is the name of the second matrix you would like to multiply?")
            B = input(">>> ").strip()
            C = mats[A]*mats[B]
            done["M"] = True
            print("The trace of their product is: " + str(C.trace()))
            print("Would you like to save this matrix? (Y/N)")
            I = input(">>> ").strip().upper()
            if I == "N":
                continue
            print("What would you like the name of the matrix to be?")
            N = input(">>> ").strip()
            mats[N] = C
            print("Matrix saved.")
        elif l == "X" and not done["X"]:
            print("What is the name of the matrix you would like to exponentiate?")
            A = input(">>> ").strip()
            print("What is the name or value of the exponent you would like to use?")
            B = input(">>> ").strip()
            if B in vals:
                B = vals[B]
            else:
                B = int(B)
            if B <= 0:
                print("Positive powers only.")
                continue
            C = mats[A]^B
            print("The trace of the matrix power is is: " + str(C.trace()))
            done["X"] = True
            print("Would you like to save this matrix? (Y/N)")
            I = input(">>> ").strip().upper()
            if I == "N":
                continue
            print("What would you like the name of the matrix to be?")
            N = input(">>> ").strip()
            mats[N] = C
            print("Matrix saved.")
        elif l == "D" and not done["D"]:
            print("What is the name or value of the first number you would like to add?")
            A = input(">>> ").strip()
            if A in vals:
                A = vals[A]
            else:
                A = int(A)
            print("What is the name or value of the second number you would like to add?")
            B = input(">>> ").strip()
            if B in vals:
                B = vals[B]
            else:
                B = int(B)
            C = A + B
            done["D"] = True
            print("Sum calculated. Do you want to save the result (S), or print and quit (Q)?")
            I = input(">>> ").strip().upper()
            if I == "Q":
                print(C)
                print("We hope you enjoyed!")
                exit()
            print("What would you like the name of the variable to be?")
            N = input(">>> ").strip()
            vals[N] = C
        elif l == "U" and not done["U"]:
            print("What is the name or value of the first number you would like to multiply?")
            A = input(">>> ").strip()
            if A in vals:
                A = vals[A]
            else:
                A = int(A)
            print("What is the name or value of the second number you would like to multiply?")
            B = input(">>> ").strip()
            if B in vals:
                B = vals[B]
            else:
                B = int(B)
            C = A * B
            done["U"] = True
            print("Product calculated. Do you want to save the result (S), or print and quit (Q)?")
            I = input(">>> ").strip().upper()
            if I == "Q":
                print(C)
                print("We hope you enjoyed!")
                exit()
            print("What would you like the name of the variable to be?")
            N = input(">>> ").strip()
            vals[N] = C
        elif l == "N" and not done["N"]:
            print("What is the name or value of the exponent base?")
            A = input(">>> ").strip()
            if A in vals:
                A = vals[A]
            else:
                A = int(A)
            print("What is the name or value of the exponent base?")
            B = input(">>> ").strip()
            if B in vals:
                B = vals[B]
            else:
                B = int(B)
            C = int(R(A) ^ B)
            done["N"] = True
            print("Power calculated. Do you want to save the result (S), or print and quit (Q)?")
            I = input(">>> ").strip().upper()
            if I == "Q":
                print(C)
                print("We hope you enjoyed!")
                exit()
            print("What would you like the name of the variable to be?")
            N = input(">>> ").strip()
            vals[N] = C
        elif l == "T" and not done["T"]:
            print("What is the name of the matrix whose trace you would like to save?")
            A = input(">>> ").strip()
            C = mats[A].trace()
            done["T"] = True
            print("Trace calculated. We will make the brash assumption you'd like to save the result.")
            print("What would you like the name of the variable to be?")
            N = input(">>> ").strip()
            vals[N] = C
        else:
            print("Either that wasn't an option, or you already used up your trial!")
    except:
        print("Your input caused an error.")

BCACTF 2.0 | Rsatrix 3 と同じ系列だが -1乗が禁止されている。は置換群なのでを群の位数として である。したがってで逆行列が手に入る。ただし位数がわからない。

置換群の位数は……ちょっとよくわからなかった引用

つまり、 N次の置換行列の全ての位数(今回は2000以上のみでよい)のLCMを求めればよいことになります。

まず、 N = 64 での全ての2000以上の位数を求めてみます。これは、 N = 64 の分割の仕方を全て列挙することで求められます。これは N次対称群が共役類で分割でき、共役類の数はN=64の分割数(N=64の場合は1741630)に一致することにより求められます。

計算すると、N=64での全ての2000以上の位数のLCMは3099044504245996706400になります。

import copy
from math import gcd

def lcm(a, b):
    return (a * b) // gcd(a, b)

ms = []
a = []

def dfs(n, ma): # 分割数全列挙
    if n == 0:
        ms.append(copy.deepcopy(a))
        return
    for i in reversed(range(1, min(n, ma)+1)):
        a.append(i)
        dfs(n-i, i)
        del a[-1]

n = int(input('input n : '))
dfs(n, n)
# print(ms)

se = set()
# 位数の種類すべて求める
for vals in ms:
    g = 1
    for val in vals:
        g = lcm(g, val)
    if g >= 2000: se.add(g)

res = list(se)
print(res)

V = 1
for i in range(0, len(res)):
    V = lcm(V, res[i])
print(V)

import binascii
from Crypto.Util.number import long_to_bytes
from pwn import *

e = 65537
N = 64

def main():
    # nc crypto.bcactf.com 49159
    r = remote("crypto.bcactf.com", 49159)
    print(r.recvline()) # Starting...
    print(r.recvline()) # Calculating G...
    print(r.recvline()) # Encrypting...
    for _ in range(7): print(r.recvline()) # Our calclator...

    n = int(r.recvline().decode('utf-8').strip().split()[-1])
    print(f'n = {n}')

    print(r.recvline()) # コマンド押す前の最初のメッセージ 

    # まずG^eの逆行列 "rGe"を登録する
    # これは(G^e)^order = G^(e*((orderのLCM)-1))を登録すればOK
    # コマンドXを使う
    r.sendlineafter('>>> ', 'X')
    print(r.recvline())
    r.sendlineafter('>>> ', 'G') # A
    print(r.recvline())
    r.sendlineafter('>>> ', str(e*(3099044504245996706400-1))) # B
    print(r.recvline())
    print(r.recvline())
    r.sendlineafter('>>> ', 'Y')
    print(r.recvline())
    r.sendlineafter('>>> ', 'rGe')
    print(r.recvline())

    print(r.recvline()) # コマンド押す前の最初のメッセージ

    # 次にE * rGeを計算する
    # コマンドMを使う
    r.sendlineafter('>>> ', 'M')
    print(r.recvline())
    r.sendlineafter('>>> ', 'E')
    print(r.recvline())
    r.sendlineafter('>>> ', 'rGe')
    trace = int(r.recvline().decode('utf-8').strip().split()[-1])
    print(r.recvline())
    r.sendlineafter('>>> ', 'Y')
    print(r.recvline())
    r.sendlineafter('>>> ', 'ans')
    print(r.recvline())

    cipher = trace * pow(N, -1, n) % n

    print(r.recvline()) # コマンド押す前の最初のメッセージ

    # dを受け取る
    # ciper^dを計算して、出力して終了
    r.sendlineafter('>>> ', 'N')
    print(r.recvline())
    r.sendlineafter('>>> ', str(cipher))
    print(r.recvline())
    r.sendlineafter('>>> ', 'd')
    print(r.recvline())
    r.sendlineafter('>>> ', 'Q')
    m = int(r.recvline().decode('utf-8').strip())
    print(r.recvline())

    m %= n

    ans = binascii.unhexlify(hex(m)[2:].encode())
    print(ans)

    #r.interactive()
    r.close()

if __name__ == '__main__':
    main()