import hashlib

def hash(message):
    return int(hashlib.sha384(message).hexdigest(), 16)

SAFEPRIME = 27327395392065156535295708986786204851079528837723780510136102615658941290873291366333982291142196119880072569148310240613294525601423086385684539987530041685746722802143397156977196536022078345249162977312837555444840885304704497622243160036344118163834102383664729922544598824748665205987742128842266020644318535398158529231670365533130718559364239513376190580331938323739895791648429804489417000105677817248741446184689828512402512984453866089594767267742663452532505964888865617589849683809416805726974349474427978691740833753326962760114744967093652541808999389773346317294473742439510326811300031080582618145727L


PUBKEY = (15897134744603412407236340130903515843905595787916104657385519422986426345115823686810853107481694865775913467114024913677335733894667792798395737569953849256882861414952399033485502243404713926200118812354039741107644139745006955253583455274886964967225553722035103514031122271234784040261201020226057012096511938211174167656870379685617680291810128637980892370691572490691519829076783461109306590095484179440862495482835514470915461945970795413256156820437342587014038955991776434408677693566169588551847744742286874738315251398924077333252631511215605564897611397211382716723267549879729623306978333824259701644870)

GENERATOR = 5

p = (27327395392065156535295708986786204851079528837723780510136102615658941290873291366333982291142196119880072569148310240613294525601423086385684539987530041685746722802143397156977196536022078345249162977312837555444840885304704497622243160036344118163834102383664729922544598824748665205987742128842266020644318535398158529231670365533130718559364239513376190580331938323739895791648429804489417000105677817248741446184689828512402512984453866089594767267742663452532505964888865617589849683809416805726974349474427978691740833753326962760114744967093652541808999389773346317294473742439510326811300031080582618145727L)

g = 5

S1 = (20950544720225190240516588643124156640166137751307772794120839122642879744566309989204234525193060193095734419581892490241084064977398989989423034374978973475972879096343609617333859217032402467474794063367359126064209414247112196692749986283927599483857635906461630946699655333336064650658571060838418022831773012112148484373450539087980144060939705883970226872558602362137321434221468807558634789744082687788692428002582578979320390623784385653753663765668912704533244714593744067390408848738952250051111603136134591670549919971405683223154547996667007410471545395238084694224087888217638321220704877088996234667758L)

S2 = (20193160426525825914749944534502183854793246273057225225204130786954179606391520252397561856344584750457489718289118609515303464507510251417077403315954173676057341891301159286752647600395198190644724307893515345893595410667424425312908674343690968733843740920409803587443515922925501638028491932183400780974410265039483539351372898810463837406346416273301833999371981123383744331959625540606861187311099827640470542835373136973637049034852358457864170556183428016586548277807973991611705101720973851865311156212618466002189499709957796272187041939722207610584175170433726950035007314375587759506260786928657084551208L)

R = (15596574224423604337174975776788465266479462558269645435687330615427783442319450174310669167504694165949734195772140468403401519160093357880254143018633950179114008556651092403391366077557363361555123124177670387232880718011385652224689886844787549431939261644192798219757366042713163922831165605478332687249430607990154018556718572496906645239311390495141354282987806832079357224945158666328969818853986069540836255016227603632402476397515152119360294922495895244235309968400537736534622122663697025389872185310053285819453794953849878570802282548259719716065417998189738453640724390984216257023730024188208988434794L)

x = 25068846673504649115013073204159551504077335388550230633916403745750246234700116848856658545794004828756011545491278286109627909119064932824318045632019480569837416672875776541337368023231944590490411760253202092483808095200967796197977981916982617237783161334496865286858293982227033097181473033945645887826660578179968969606115788410184864335869939046680461540228612601790548156930331249872426448165169562147455277630515803154329189762403617436554089752405120434751512261207786540113077887070082618511120708688069372803543422623986996708285225792456858415217112853089594868585882736142092012577812600140885857456632

def elgamal_verify(r, s, m):
    if r <= 0 or r >= SAFEPRIME:
        return False
    if s <= 0 or s >= SAFEPRIME-1:
        return False
    h = int(hashlib.sha384(m).hexdigest(), 16)
    left = pow(GENERATOR, h, SAFEPRIME)
    print left
    right = (pow(PUBKEY, r, SAFEPRIME) * pow(r, s, SAFEPRIME)) % SAFEPRIME
    print right
    return left == right

def gen_sign(message, k):
    m = hash(message)
    r = pow(g, k, p)
    s = ((m - x * r) * inverse_mod(k, SAFEPRIME - 1)) % (SAFEPRIME - 1)
    return int(r), int(s)

D1 = hash(u'\'"o%^W?GuXkB$4[>kW">FK|9+K.];P6/fWW8TVbiJD2CYtpcnM')
D2 = hash(u'O2,EmP|,!K5F?m]eI;;:V')

v = PUBKEY

p_1 = (p - 1)

A = mod(R * (S2 - S1), p_1)
B = mod(S2 * D1 - S1 * D2, p_1)

m = GCD(p_1, A)
pp = p_1 / int(m)
A_bar = mod(ZZ(int(A)), pp)
B_bar = mod(ZZ(int(B)), pp)
s = mod(B_bar * A_bar ** (-1), pp)
print pow(g, int(s), p) == v
print pow(g, int(s) + int(pp), p) == v
print pow(g, int(s) + int(pp * 2), p) == v

m = "There is no need to be upset"
r, s = gen_sign(m, 5)
print elgamal_verify(r, s, m)