“Reduced Dimension” (Easy). Provided chall.py and output n, e, and the first row of A^e (mod n) where A is a 4x4 quaternion matrix built from
a0 = m
a1 = m + 3p + 7q
a2 = m + 11p + 13q
a3 = m + 17p + 19q
with n = p*q, e = 65537.
We only see:
row = [b0, -b1, -b2, -b3] = first row of A^e (mod n)
The quaternion matrix A satisfies a quadratic relation:
A^2 = 2*a0*A - s*I
for some scalar s (the norm).
So every power of A lies in the span of {I, A}. In particular:
A^e = k*A + c*I (mod n)
for some scalars k, c.
Therefore the vector part scales by a single factor:
b1 = k*a1, b2 = k*a2, b3 = k*a3 (mod n)
(remember the row contains -b1, -b2, -b3).
Using the linear structure of a1, a2, a3:
2*a2 - a1 - a3 = 2p
3*a1 - 7*a2 + 4*a3 = 6q
Multiply by k and substitute b1, b2, b3:
2*b2 - b1 - b3 = 2*k*p
3*b1 - 7*b2 + 4*b3 = 6*k*q
Thus:
kp = (2*b2 - b1 - b3)/2
kq = (3*b1 - 7*b2 + 4*b3)/6
modulo n.
Then gcd(kp, n) = p and gcd(kq, n) = q, since p and q divide these values but are coprime.
p = gcd(kp, n) and q = n/p.k (mod n) using CRT from:
k ≡ kp * p^{-1} (mod q)k ≡ kq * q^{-1} (mod p)k modulo n to get a1, a2, a3:
a1 = b1 * k^{-1} (mod n)m = a1 - 3p - 7q (mod n)from math import gcd
from Crypto.Util.number import long_to_bytes
n = 24436555811992972366076806922530312273907496823566498825278523886197470905017391954938641972382127780163747562797956038193398654235644409459287830339446234525262072627164429789264587184451084484976035579016063031028571643546268940916664832350416704133070528632744931737357768415126788528052461206333395794164406084571633391115829776964808677724703621221154710591190375698378697896449037181113710774632252351521950724961537615755537875194862156989318761303971336544564950137455452434307027177388197740176937447577518701185717201408469263753367188476145954061480542913006467287367140336404472235624010067372903582272729
row = [
7645133316138320672920829866179304735182212690210047500676759675676422841305242219428671895825721777886336067123230090334404443239249744649348019800170870076772170648917374424307951430757942474104583441027037157499352780211088515553775367980514698077272400388982174956856115745318060191675644580097459087877103744768611124967141106979760409192285920050555016687019974731108717211479671838777445410222040882405240324940267527783747870861280181437508731620415299917485800707003438326195859384666421699977525718115984628571014356722832203980578905816041544254774832610446558646617081820383024594943509109272533930838708,
15115864622351599035162706206257324674672546729754571030515410021905207212154731966558659435218498028437041608389247596685777775075531974586762001822195044830215779677969600204017249097853619421972862952306880626946718048703037486579156521083427871219972900601347265611525515981798763462306348832427757653091251117371763790691703299928013908976268558111890052847761824740201601000159794443256033087429920731339521534477358144537370658535238347192547096515188805816620173560028595429243354057894242958704409904709847929320587768434722670465044376198153825572537650025403520767434960328371498100779394191999106392405505,
13745229990855433471733323096856618171809729836071048905352245517395661673128741357306382928377040374671176807926741135701004188571412113925163459038871795016583126047331363592533678987966281886904921753115792048974820789657695172533157583206166353580229326903802517936396022419823884208200013314323762420208768560108045572583904747823741147655693248507409489075089305887965790292485140729487526433929859183972759579430813209494595211145046105006826362941878536200003370316700559144884743367020754865964581608047339157411175462078984500914717760473129611002520677145892778242279106724152108492680282436100305414987989,
13075867308307993713881388617739767319783540136821062304673039023416514479073968404704931053707431722417113432221377192698845939724954608884902350188774482318948356490572584570493016148272003096623369096838093349374805909370089074902960407209272664510740999775809485842810426515913298045223326669961556520541238694804400787951685561362702557941491071370737013429166029262325140106903158536926574942320103807698268441557280143112008091660020312242173901777414105294912109492658141997518018221759802285312329937197750464541705293605084821535959702107937728040393887374381496534531147546227981215469580847563998832887560
]
# row is [b0, -b1, -b2, -b3]
b0 = row[0] % n
b1 = (-row[1]) % n
b2 = (-row[2]) % n
b3 = (-row[3]) % n
inv2 = pow(2, -1, n)
inv6 = pow(6, -1, n)
kp = (2*b2 - b1 - b3) * inv2 % n
kq = (3*b1 - 7*b2 + 4*b3) * inv6 % n
p = gcd(kp, n)
q = n // p
# recover k with CRT
k_mod_q = kp * pow(p, -1, q) % q
k_mod_p = kq * pow(q, -1, p) % p
t = ((k_mod_q - k_mod_p) * pow(p, -1, q)) % q
k = (k_mod_p + p * t) % n
k_inv = pow(k, -1, n)
a1 = (k_inv * b1) % n
m = (a1 - 3*p - 7*q) % n
print(long_to_bytes(m))
0xL4ugh{M4t_Qu4t3rn1on_By_Zwique}