Rating:
# ElGamat: ElGamal over Matrices (crypto 200)
We are provided with a [cryptosystem scheme spec](ElGamat.pdf),
which consists in getting the discrete logarithm of a matrix.
We are also provided with [a data file](Matrices.txt),
consisting in the modulo `p`, the generator matrix `G`
and the public key matrix `H`.
Finally we have a [flag generator](flag_gen.py) that
once we have the private key (the exponent `α`) gives us the flag.
To get the private key, we look for the jordan blocks of the matrix,
find one that is easily solvable and get alpha:
```sage
#!/usr/bin/sage
def flag_gen(alpha):
import hashlib
return 'SharifCTF{%s}' % hashlib.md5(str(alpha).encode()).hexdigest()
p = 1461501637330902918203684832716283019655932542983
G = matrix(GF(p), 5, 5, [
[1287397632974625907369332145667695136576732725719, 999149001044306271168727399637009399486427921379, 1046504160269652701583906344218556291030141088947, 724446625683754938181565321149725788430461092168, 1071845980147173642753960259602135592110139561915],
[947603660931904341080240982051313712707367037453, 312289846563741934103580532543082761760226637905, 494739786803547247505263837170488583876166831850, 680540462980071181450018491798299105995449257198, 2602258415762368797405060707505977243346704576],
[996213673531855992829525358578006610606634622631, 1025711294257038288640877971869685565227647136954, 1432432135773706484846126533752827108541355741973, 1238541870126055576875033883691918425137600727481, 1130938956963588695293783764965618873887596017827],
[1320933266015680090206505704792362493057963931979, 1151746112645644166669332171392580649376526147475, 117512451110908867093773368598681106589771485221, 78071463743800894350883457304401524272336187149, 350437511649326676405126284689545814008237687775],
[438339253001275654203062260777687750937184662400, 372483950165136927369598298270629892810999203086, 859008773869616460027135965589262417694174453098, 1174526536643808668299968641952541506024584582818, 13201859260259503932772826643483081858286638179]
])
H = matrix(GF(p), 5, 5, [
[903022231855038558383593109888227525558007552960, 565977275270298825053282757799743346899236483368, 989303675765663596792169321947495382568831693037, 601579288654704389384765634776493921679315260303, 913791750749394879333717884106841876340654737006],
[1159121456278955861257379214176694847802842944213, 55304385436577133507085707981392660143782780650, 559867756424853909301288957105188829240808301823, 1230859641388132364539374469026906952870988170695, 1423995124592695628047882256427827379994877406997],
[1125565199147204322161069021173152827232960621114, 1373772036013472137002755957284397215018630262515, 640623873603434273377865546046279663852895430999, 1056809237992218798189986002766547616222871640976, 1426649441470162608512662468308504390861950649943],
[303729376872199895471546635639837180361513146712, 1163767872227950278851006729914569662442255257700, 1320342731346163804219021270875175061467772367004, 433001013681018647747911760920686992297849343282, 1149024280460224794070159244078925721991430685838],
[23661702916810298505759145354543089608241235601, 1048655828654821525617176122368805879408325508567, 587846047820504813842423941849757078103027466928, 1338365929525105225695097114139069216753339875455, 1425543850003062038868121400064269552725872690214]
])
J, P = G.jordan_form(transformation=True)
I = ~P * H * P
alpha = J[3][3] * I[3][4] / I[4][4]
print flag_gen(alpha)
```
```
> ./matrices.sage
SharifCTF{e61ac2503f2cc2e8385db92afb59aac2}
```
