# Sharif CTF 8 - ElGamat WriteUp## Challenge details|       Event        | Challenge | Category | Points  ||:-------------------|:----------|:---------|:-------:|| Sharif CTF 8       |ElGamat    |Crypto   |200      |
### Description> ElGamal over Matrices: algebra-focused crypto challenge>> you can find full description in [ElGamat.pdf](ElGamat.pdf)### Attachments> [Matrices.txt](Matrices.txt)## Solution
This problem appears to be similar to the discrete logarithm problem (see [Discrete logarithm](https://en.wikipedia.org/wiki/Discrete_logarithm)), but instead of the generator g we a have a matrix G, So we need to find x such that G^x = H (both G and H are 5 square Matrices).
Matrices => Linear Algebra: this challenge requires some fundamentals in linear algebra.
At the beginning I tried to diagonalize the matrix G and H in order to transform the problem to a discrete logarithm problem, but it will stay hard to solve since p-1 is not a product of small primes which in this case Pohlig–Hellman algorithm is not an efficient method for computing the discrete logarithms.
After doing some googling I figure out that in order to make this problem easy to solve we need to put both Matrices G and H in Jordan normal form (see [Jordan normal form](https://en.wikipedia.org/wiki/Jordan_normal_form))
A Jordan matrix has each non-zero off-diagonal entry equal to 1, immediately above the main diagonal.
for A a Jordan block as 2*2 matrix, if we have a repeated eigenvalues:
![alt text](img/A.gif "Matrix A")
for B = A^x:
![alt text](img/B.gif "Matrix B")
therefore in this case: ![alt text](img/x.gif "Solution x")
Now we need to apply this solution to ElGamat problem
In our case G[3][3] to G[4][4] is a Jordan block with repeated eigenvalues, and all arithmetic operations are in Quotient Ring ![alt text](img/ring.gif "Ring Z/Zp").
this is my code in sage ([ElGamat.sage](ElGamat.sage)):
```sageimport hashlib
p = 1461501637330902918203684832716283019655932542983
G = [     [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 = [     [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]    ]
R = IntegerModRing(p)M = MatrixSpace(R, 5, 5)g = M(G)h = M(H)
g, p_mat = g.jordan_form(transformation=True)
print '[+] jordan normal for G:'for i in g:    print i
h = p_mat.inverse()*h*p_matprint '[+] jordan normal for H:'for i in h:    print i
a11 = g[3][3]b11 = h[3][3]b12 = h[3][4]
x = a11*b12/b11assert b12 == x*a11^(x-1)
print '[+] solution:', x
def flag_gen(alpha):	return 'SharifCTF{%s}' % hashlib.md5(str(alpha).encode()).hexdigest()
print '[+] FLAG:', flag_gen(x)```