# 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) thatonce 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 * Palpha = J[3][3] * I[3][4] / I[4][4]
print flag_gen(alpha)```
```> ./matrices.sageSharifCTF{e61ac2503f2cc2e8385db92afb59aac2}```