Challenge Points: 50(+100)
Challenge Description:

Hey there fellow lizard how nice of you to drop by! Did you know those filthy humans really think that some numbers have special meanings? Seven, 13 and for some strange reason even 9000. Go and show them that a good prime does not make a secure cryptosystem!

Given encryption script:

g = 5
d = key
m = int(flag.encode('hex'), 16) % p

B = pow(g, d, p)  # Equation-1
k = pow(A, d, p)  # Equation-2
c = k * m % p     # Equation-3

Values p, A, g, B, c are known. Prerequisites:

  1. Cyclic Groups
  2. Discrete Logarithm Problem
  3. Basic Number Theory

In case you are interested in understanding the exploit, but don’t have much knowledge about Cyclic Groups and DLP, you can read about it here in Crypton: Cyclic Groups and Disrete Logarithm Problem

There are three steps involved in solving this challenge:

  1. Compute the value of d by solving equation-1
  2. Calculate k using the value of d obtained in step-1, in order to solve equation-2
  3. Get the flag

Finding secret key d

We know from the property of Cyclic Groups that:
\(g^{|G|}\equiv 1\mod p\), where |G| is the cardinality of the Cyclic Group G.

Cardinality i.e. the number of elements in the Cyclic Group, in this case, is p-1.
Therefore we can write: \(g^{p-1}\equiv 1\mod p\) which is also known as Fermat’s Little Theorem.

Note that \(B = p-1\), which makes solving DLP a lot easier. We can now write:
\(p-1\equiv g^d\mod p\) which can also be written as \(g^d\equiv -1\mod p\)
Upon squaring, we have: \(g^{2d}\equiv 1\mod p\) –> (1)

Comparing (1) with \(g^{p-1}\equiv 1\mod p\), we can write:
\(d = (p-1)/2\)

Computing k and getting the flag

\(k = A^d\mod p\)
\(m \equiv c * (k^{-1}\mod p) \mod p\)

Solution script:

from Crypto.Util.number import *
import gmpy2

B = 1044388881413152506679602719846529545831269060992135009022588756444338172022322690710444046669809783930111585737890362691860127079270495454517218673016928427459146001866885779762982229321192368303346235204368051010309155674155697460347176946394076535157284994895284821633700921811716738972451834979455897010306333468590751358365138782250372269117968985194322444535687415522007151638638141456178420621277822674995027990278673458629544391736919766299005511505446177668154446234882665961680796576903199116089347634947187778906528008004756692571666922964122566174582776707332452371001272163776841229318324903125740713574141005124561965913888899753461735347970011693256316751660678950830027510255804846105583465055446615090444309583050775808509297040039680057435342253926566240898195863631588888936364129920059308455669454034010391478238784189888594672336242763795138176353222845524644040094258962433613354036104643881925238489224010194193088911666165584229424668165441688927790460608264864204237717002054744337988941974661214699689706521543006262604535890998125752275942608772174376107314217749233048217904944409836238235772306749874396760463376480215133461333478395682746608242585133953883882226786118030184028136755970045385534758453246
c = 626538023179183383530326775878874061243537575637678230775990839517480703838547661223043351239918394865532739593994849154430591305198322288328417436892902443505917379006443598061697092201021536603987285163299838045075649512028921956548205676208712226470308113290505059049053554206416767772651512039632936795232724801922443388952796545084060280910673215063573749033668717290815841834685051547255093401042248880082370281195663905731764841136214458769095907569163184276786105979509363239839613385785232307550226120692268670717158539363476974302593377514937470953649913863219081380729197866499068054753726732556988368232198510160183731571741889761632557457157261911256679728707526809880224074940827825962124087677609578885077944156589121586951372962667391498824853627326311588259929756093569512874696625507873168095797130866697040006079191565592914811736694534863664544646201900855732710994613768016495896341014229622129847800138058041138449691835652916517559125407914079964177419733079221280850917496784527992741048638603428068452948455069671414667008770873913118369984179054902139270844669700487715140145038503768704763641223894377872853332484296603268546135216483844722413025955229649646292980986542646384960063297213437076185709400450
p = 1044388881413152506679602719846529545831269060992135009022588756444338172022322690710444046669809783930111585737890362691860127079270495454517218673016928427459146001866885779762982229321192368303346235204368051010309155674155697460347176946394076535157284994895284821633700921811716738972451834979455897010306333468590751358365138782250372269117968985194322444535687415522007151638638141456178420621277822674995027990278673458629544391736919766299005511505446177668154446234882665961680796576903199116089347634947187778906528008004756692571666922964122566174582776707332452371001272163776841229318324903125740713574141005124561965913888899753461735347970011693256316751660678950830027510255804846105583465055446615090444309583050775808509297040039680057435342253926566240898195863631588888936364129920059308455669454034010391478238784189888594672336242763795138176353222845524644040094258962433613354036104643881925238489224010194193088911666165584229424668165441688927790460608264864204237717002054744337988941974661214699689706521543006262604535890998125752275942608772174376107314217749233048217904944409836238235772306749874396760463376480215133461333478395682746608242585133953883882226786118030184028136755970045385534758453247
g = 5
A = 1026312539297800437474663698165859314949881437729617621666434357798219198741950468733395500361477359726152747087790103309627020498122003777642051150130697457594304849673838709900017711265818285080832347734747895550397950729716624922572654209637755195129162139245110756558638081495998280747642920484467428206475906559638681536868548289456924005274209311355030582255692087426910634838198143851507435754029135363794578075936092774722678311786272841489629294721103591751528609388061794369341067986401129462942050916582521451289187645626081017578576190303952351748434876686541368607656026867091583868645619423975306245327421218767449273192101105293424028461698783545171866070124432565063559495566733441286372612161876492134408160732339966921175762866198980795890946054558528891296203285979664329713156129091098226212735763844909789916934266711879564086741733061623347281499025678164709559814150194881622611023214199434022258730549350019749882889143749385314934896284396513061241138504029046053964944026179039768718830854958634216721133676746317913559932277050177463811150719675119168868527853864167729206220819613297736800799391257602899169041109002518019207734013899840092155297682096290489330476118066934735827328128343402508975429994312

d = (p-1)/2
k = pow(A, d, p)
k_inv = inverse(k, p)
m = (k_inv*c) % p
print long_to_bytes(m)

flag: flag{If you whistle while you’re pissing, you have two minds, where one is quite sufficient. If you have two minds, you are at war with yourself. If you are at war with yourself, it is easy for an external force to defeat you. This is why Mong-tse wrote. ‘A man must destroy himself before others can destroy him.’ | Lorem ipsum dolor sit amet, consectetur adipisici elit, sed eiusmod tempor incidunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamaco laboris nisi …}