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()