Tags: crypto 

Rating:

Sharif CTF 8 - ElGamat WriteUp

Challenge details

EventChallengeCategoryPoints
Sharif CTF 8ElGamatCrypto200

Description

ElGamal over Matrices: algebra-focused crypto challenge

you can find full description in ElGamat.pdf

Attachments

Matrices.txt

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 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)

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

for B = A^x:

alt text

therefore in this case: alt text

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.

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)
Original writeup (https://github.com/philomath213/CTF_WriteUps/tree/master/SharifCTF8/ElGamat).