Tags: crypto
Rating:
# 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:
for B = A^x:
therefore in this case: 
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 .
this is my code in sage ([ElGamat.sage](ElGamat.sage)):
```sage
import 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_mat
print '[+] 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/b11
assert 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)
```
