EMC Defenders League - Round 3 - ElGamal Cryptosystem

A ruby script was given, looking at the code its easily identified as ElGamal cryptosystem

def encrypt(plaintext)
  begin
    p,g = File.read("public.key").split.map(&:to_i)   # prime p and generator g
    x = File.read("secret.key").downcase.unpack("H*").first.to_i
  rescue
    raise "Could not read the keys."
  end
  y = mod_pow(g,x,p)     
  msg = plaintext.unpack("H*").first.to_i(16)  
  enc = []
  while msg!=0 do
    k = rand(2**512)
    while k.gcd(p-1)!=1
      k = rand(2**512)     # ephimeral key
    end
    msg , m = msg.divmod(p)    # quotient , remainder
    a = mod_pow(g,k,p)     # cipher_one

    b = (m * mod_pow(y,k,p)) % p   # cipher_two
    enc.push([p,g,y,a,b])
  end
  return enc
end

Also a directory listing was given, which read

-rw------- 1 user1 user1    9 Sep 12 16:59 secret.key

So, it looks like the private key is a small number. From the code y = g^x mod p , where y,g and p are public. I wrote a GMP C code to brute the value of x. Now its the matter of decrypting the value of cipher text from the given file

#!/usr/bin/env sage -python

from sage.all import *

a = [10264935714840344555659480530391531504799751837786398398316078563294217410270167702155077526394934157060210816906645541211888193204711479484170362078382934, 6823073135499190154483378335285592356188617899094830851286814357379354454127003397049290347022567266459967665409741524356428389256663366725696511671610252, 6799828613544592377533880394625646977560051635952644078042208063362163512223938553938795141149658062454075205535854660371542763834499519406362703514503332, 672505970984355266693231966226618520516336889495074224541849620341452271159684475161636332714848734553160854293600007936085992661979551831016772987917068]
b = [10340609465224600321180300969872222181794348193568386018372923576739867282485924452563065089417849300140351755230325685204557146183945278941161645372102509, 5281134801218769020778720412885415834550804855232111764210295764635532757913976877308711845460529040416820894758873972605710392788924240448443272640451982, 457101717286387383800532326852190913868486287682428841339947697619176026876915473073415513803021227080851888197491621726415573291680046893149593865864624, 589149635285693973671288870900610302399060697179753365215668035230635162797171706009867229016045306799390816419364037357020145534760948533979498925094150]
mod = 11994453392181474037639262741550096843127850786293620241343626519409002514576698974663696483571708872339453054238999399420344927969237949604807335692536203

private = 77656
dec = []
for i in range(4):
    dec.append( (b[i] * inverse_mod(a[i]^private, mod)) % mod)

q = 0
for i in range(3, -1, -1):
    msg = (q * mod + dec[i])
    q = msg

dec = hex(q)[2:]
dec = dec[:len(dec)-1].decode('hex')
print dec

Yourt passwordh muste be ats leaste 18770c charactersr ande cannott repeat anyc ofo yourd previouse 30689 passwords.i Pleases type ag differenty password.8 Type4 ai password7 thatf meetso thesev requirements1 int boths textw boxes..
Collect the last character of each word to retrieve message.