This challenge is a diffie hellman protocol with matrix

To do this, we need to unpickle all the messages. That means we get the order, the base matrix G, and G^A,G^B.

Then, we inspect the jordan form of G.

The char poly has factors of degree 2, so we work over GF(p\*\*2)

We cannot do dlog with matrix in sage.

Since is is a diagonal matrix, we can just diagonalize both G and G^A and then it becomes dlog in GF(p\*\*2).

Then, since the order is small, a BSGS algorithm solves the Dlog problem.

With one of the private keys, we compute the shared key and then can decrypt the ciphertext.

```py
from base64 import b64decode

#val=bytes.fromhex("6741535677774541414141414141434b43586b76713079793733665141497757626e567463486b7558324e76636d55756258567364476c68636e4a68655a534d444639795a574e76626e4e30636e566a644a53546c497746626e567463486d556a4164755a474679636d46356c4a4f55537743466c454d42597053486c464b554b4573425377524c4249615561414f4d425752306558426c6c4a4f556a414a504f4a534a694965555570516f53774f4d41587955546b354f53762f2f2f2f394b2f2f2f2f2f30732f644a5269695632554b49775363336c7463486b75593239795a533575645731695a584a7a6c497748535735305a57646c637053546c496f49466d487751774d7a66334b466c4947556142574b43475a576b594f7557667070685a53426c47675669676d4d58776a3665704131764143466c4947556142574b434251436142757569517878685a53426c47675669676a6268794b4d344b494b52495755675a526f46596f4a523873786a4c586931616f41685a53426c4767566967695254534446724b7835576f5755675a526f46596f494c4b4d5145373543655175466c4947556142574b434f64474d694477704e4d66685a53426c47675669676a4933672f354e4173344d345755675a526f46596f4a775032476747523275707341685a53426c47675669676734676e785555314c6c56595755675a526f46596f4963616151323379597a7a36466c4947556142574b434f784e7a576e4a75423169685a53426c476756696768344c7244772b37422b4a6f5755675a526f46596f49766962587067476646794f466c4947555a585355596f6f476f78434e66697373683551750a")

# print(b64decode(val))

import pickle
import sympy

from sage.all import *
print(pickle.loads(b'\x80\x04\x95\xc3\x01\x00\x00\x00\x00\x00\x00\x8a\ty/\xabL\xb2\xefw\xd0\x00\x8c\x16numpy._core.multiarray\x94\x8c\x0c_reconstruct\x94\x93\x94\x8c\x05numpy\x94\x8c\x07ndarray\x94\x93\x94K\x00\x85\x94C\x01b\x94\x87\x94R\x94(K\x01K\x04K\x04\x86\x94h\x03\x8c\x05dtype\x94\x93\x94\x8c\x02O8\x94\x89\x88\x87\x94R\x94(K\x03\x8c\x01|\x94NNNJ\xff\xff\xff\xffJ\xff\xff\xff\xffK?t\x94b\x89]\x94(\x8c\x12sympy.core.numbers\x94\x8c\x07Integer\x94\x93\x94\x8a\x08\x16a\xf0C\x033\x7fr\x85\x94\x81\x94h\x15\x8a\x08fV\x91\x83\xaeY\xfai\x85\x94\x81\x94h\x15\x8a\t\x8c_\x08\xfaz\x905\xbc\x00\x85\x94\x81\x94h\x15\x8a\x08\x14\x02h\x1b\xae\x89\x0cq\x85\x94\x81\x94h\x15\x8a\x08\xdb\x87"\x8c\xe0\xa2\nD\x85\x94\x81\x94h\x15\x8a\tG\xcb1\x8c\xb5\xe2\xd5\xaa\x00\x85\x94\x81\x94h\x15\x8a\x08\x91M \xc5\xac\xacyZ\x85\x94\x81\x94h\x15\x8a\x08,\xa3\x10\x13\xbeBy\x0b\x85\x94\x81\x94h\x15\x8a\x08\xe7F2 \xf0\xa4\xd3\x1f\x85\x94\x81\x94h\x15\x8a\x08\xc8\xde\x0f\xf94\x0b83\x85\x94\x81\x94h\x15\x8a\t\xc0\xfd\x86\x80dv\xba\x9b\x00\x85\x94\x81\x94h\x15\x8a\x088\x82|TSR\xe5U\x85\x94\x81\x94h\x15\x8a\x08q\xa6\x90\xdb|\x98\xcf>\x85\x94\x81\x94h\x15\x8a\x08\xecM\xcdi\xc9\xb8\x1db\x85\x94\x81\x94h\x15\x8a\x08x.\xb0\xf0\xfb\xb0~&\x85\x94\x81\x94h\x15\x8a\x08\xbe&\xd7\xa6\x01\x9f\x17#\x85\x94\x81\x94et\x94b\x8a\x06\xa3\x10\x8d~+,\x87\x94.'))
p=15021738631187083129
gorder=48565318389923
Mat=[[8250369131483783446, 7636514724226618982, 13561904710751379340,
8146037206883500564],
[4902910229653653467, 12309994425856150343, 6519431793637084561,
826765390730273580],
[2293357986500986599, 3690712216774893256, 11221411595572149696,
6189443780743823928],
[4526003812557694577, 7070010165244546540, 2773849016628162168,
2528664545234724542]]
Mat=Matrix(GF(p**2),Mat)

print(Mat.charpoly().factor())

A,B=Mat.jordan_form(transformation=True)
print(B)
B=B**-1
Mat=B*Mat*(B**-1)
print(gcd(p**2-1,gorder))

sec=bytes.fromhex("6741535673514541414141414141434d466d3531625842354c6c396a62334a6c4c6d31316248527059584a7959586d556a417866636d566a6232357a64484a31593353556b35534d42573531625842356c497748626d5268636e4a68655a53546c457341685a524441574b55683552536c43684c41557345537753476c4767446a41566b64486c775a5a53546c497743547a6955695969486c464b554b4573446a4146386c45354f546b722f2f2f2f2f53762f2f2f2f394c50335355596f6c646c43694d456e4e35625842354c6d4e76636d5575626e5674596d56796335534d42306c756447566e5a584b556b35534b434754676e752f596b2b4269685a53426c476756696767357248547a50725743596f5755675a526f46596f496d4837556d52694d6e5557466c4947556142574b43466c54787761676c723875685a53426c47675669676b4a3337486c38553471735143466c4947556142574b4341754b59445a71784f734f685a53426c47675669676b6a315667794f3178577a7743466c4947556142574b43634c64395743667432693741495755675a526f46596f4a49326a4c7333436975356741685a53426c47675669676a2b4a306a5a62624d6a57495755675a526f46596f4a786b4e4751563733785a4541685a53426c476756696769705347656274796166436f5755675a526f46596f49656736532f786d67317a65466c4947556142574b43492b6d502b4a38352f5132685a53426c47675669676d7973642b2b5647786f7a7743466c4947556142574b43484b5654496b6b6e49396c685a53426c4756306c474975")
Mat2=pickle.loads(b64decode(sec))
Mat2=list(Mat2)
for i in range(4):
for j in range(4):
Mat2[i][j]=int(Mat2[i][j])
Mat2=Matrix(GF(p),Mat2)

Mat2=B*Mat2*(B**-1)

val=Mat[0][0]
val2=Mat2[0][0]
# DL=discrete_log(val2,val,ZZ(gorder))
DL=14694400667272
print(pow(Mat,DL))
print(Mat2)
print(DL)

third="674153562b774541414141414141434d466d3531625842354c6c396a62334a6c4c6d31316248527059584a7959586d556a417866636d566a6232357a64484a31593353556b35534d42573531625842356c497748626d5268636e4a68655a53546c457341685a524441574b55683552536c43684c41557345537753476c4767446a41566b64486c775a5a53546c497743547a6955695969486c464b554b4573446a4146386c45354f546b722f2f2f2f2f53762f2f2f2f394c50335355596f6c646c43694d456e4e35625842354c6d4e76636d5575626e5674596d56796335534d42306c756447566e5a584b556b35534b434e54533962432b774d6f52685a53426c47675669676b34597077734c79494e714143466c4947556142574b4361457878666f6f69586d6141495755675a526f46596f49784f75634b65346c313347466c4947556142574b4353775345584762494f484141495755675a526f46596f4978714e43717841504a4379466c4947556142574b435049305a6773436f726f35685a53426c47675669676b314f56676b34673957725143466c4947556142574b435a414c62346e597648584e41495755675a526f46596f4a556d364f783744744b4d3441685a53426c4767566967696f6538672b323941694b6f5755675a526f46596f49426c4332356b646d4a782b466c4947556142574b4362376b5a6550574636616741495755675a526f46596f4a322b744469714448544c5141685a53426c4767566967694c6e394d514d497a6665595755675a526f46596f49755744466a564878535379466c4947555a585355596b4d517551594678773346344e54537130574d6b386f2b4c4a52444d4e647957473465482f694c583733436f76644331736a385558724d4858624f4f41557473616f6d6146444e4a6b497974396b4e4b446f64493370766c395a566a3553486c43343d0a"
third=bytes.fromhex(third)
A,iv, cipher=pickle.loads(b64decode(third))
# A=list(A)
# for i in range(4):
# for j in range(4):
# A[i][j]=int(A[i][j])

# A=Matrix(GF(p),A)

# print(A)

import sys
import hashlib
import random
import numpy as np
from numpy._typing import NDArray
from gmpy2 import mpz
from typing import Any
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes
from cryptography.hazmat.primitives import padding
from cryptography.hazmat.backends import default_backend

def mpow(a: NDArray[Any], e: int, p: mpz):
n = a.shape[0]
c: NDArray[Any] = np.identity(n, dtype=object) // mpz(1)
for i in range(e.bit_length(), -1, -1):
c = (c @ c) % p
if e & (1 << i):
c = (c @ a) % p
return c

def dec(key: bytes, iv: bytes, ciphertext: bytes) -> str:
cipher = Cipher(algorithms.AES(key), modes.CBC(iv), backend=default_backend())
decryptor = cipher.decryptor()
padded_data = decryptor.update(ciphertext) + decryptor.finalize()
unpadder = padding.PKCS7(algorithms.AES.block_size).unpadder()
plaintext = unpadder.update(padded_data) + unpadder.finalize()
return plaintext.decode()

K=mpow(A,int(DL),p)
h = hashlib.sha256()
h.update(str(K).encode())
digest = h.digest()

print(dec(digest, iv, cipher))
```