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
Attachments
Solution
This problem appears to be similar to the discrete logarithm problem (see 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\times5\) 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)
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\times2\) matrix, if we have a repeated eigenvalues:
$$ A = \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix} $$ for \(B = A^x\): $$ B = \begin{pmatrix} \lambda^x & x\lambda^{x-1} \\ 0 & \lambda^x \end{pmatrix} $$
$$x = {-b \pm \sqrt{b^2-4ac} \over 2a}.$$
therefore in this case: $$ B_{12} = xB_{11}A_{11}^{-1} \iff x = A_{11}B_{12}B_{11}^{-1} $$
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 \(Z/Z_p\)
this is my code in sage (ElGamat.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)
