The python script first generate parameters for El Gamal: p, g, x, y = generate(2048) and print p, g and y.
The goal of this challenge is to craft a signed message.
However, we don’t know $x$ so in theory we can only verify signature and not sign new message.
We are looking for a signature forgery.
With the search “el gamal signature forgery”, the first result is the wikipedia page of El Gamal signature scheme. It explains that this scheme is vulnerable to forgery with one-parameter forgery and two-parameters forgery.
- The one-parameter forgery. Select an $e$ such that $1 < e < p − 1$. Set $r := g^e y \mod{p}$ and $s := − r \mod {p − 1}$. Then the tuple $( r , s )$ is a valid signature for the message $m = e s \mod { p − 1}$.
Basically we do not need $x$ to forge a signature for an arbitrary message. You can take a piece of paper and run the verification algorithm with this parameters to check. However this doesn’t mean that this signature is useless. If you first hash the message before signing/verifying it, then an attacker would have to reverse the hash function to provide the message corresponding to the forged signature (good luck). But enough thinking, let’s just get the flag with a short python script:
# First copy the parameters printed by the server here
p = 27094078649165424778110868593130985287939239757223958417044102841842688286681622765146165344165655622085957925270861215595657116634345488902954006699421910709200533181586170386199373619134670345709901381947091890565764817539958931189859536708252462939237857212732963943828209350348533272269409218484923935442162474916296485301068025769723690725382596142771427142859823381207743732746792946153675389549421843801976219368303658367392233517149729601081146828362360512070557192400018774929830953231655895852887560349322837002690980815984577661996010481980784838083431828866258166757336432949782152938015035580405957012709
g = 1232733929115551278265381953732068014462078898168372699429392347353890203505865506898939683991221854895574525252118109202417362798709653929839323741206112381519588930667900247225173924674027253741753364519667085716927971588306126946939872757649953721577124807080201343871408858934161564542857892019957503535721823746451361190271055831633221624125235707874805670731685975508445316192613416279096548123271060639246757619693988607491110966231578594372789557162676990069197351136683609945955433654475391926769735281047256594280161947411609293922613880944987519409713010603412941088828889649287428410989923066505951384593
y = 21400515358484608734788781463849889210712169169493125592164554863859840914333091797729339779053447262498484779175633523848041101033374780666959437287609331631868387998656304218717858028108524543046475698483202089997127106917046687224157779459560322134496402274534162867508656092249453641072536296872868509850632973199300608289701421865333582271254174301648102474324432149802730031741166493874136624239465148932314653667027079875646279195302460614540418786054563265105697563249668144723622160674937244665643472706666782813912388054600418787400351624022140177448684166562768670910740106868319327188950644247062723305255
e = (p - 15) % p
r = (pow(g, e, p) * y) % p
s = (-r) % (p - 1)
m = (e * s) % (p - 1)
print("m", m)
print("r", r)
print("s", s)
#And then speedrun to send this to the server before the connection is closed
#FCSC{9494c...
As you can use any $e$ between $1$ and $p-1$, I choosed $p-15$ arbitrarily. Feel free to choose your preferred number. If it is bigger than p, well… you are definitely weird.
Anyway, it was a nice little crypto challenge!