dsa.py

#!/usr/bin/env python
import hashlib
import utils
import gmpy2


L = 3072
N = 256

P = 4046261409545279481846657173088772896119142202231569809006694247791067886250869503259535636090814617968999878545891271312952579656792106079449572582661758625636275124484708830096892553142398087979421100268322750327693638134290007678579734971296441877030644268635040690956219501594626733630939963365599035277780863883018242559975436973267408737052957920522124751528328410616845731178795063825019447868372497865406616459743257043107507678778387107347082754073213376020124277102831162242424119740989379523503649331019082100082613740393322928933487573186514364343465815217181701973192167168944546816563793765445960393321908271707131751610497979083821175284545759072423865466355778235185724916204992659426380907377606244984835101464536900236928271366474923549402775631748959898771155726886578525431613744931289803940357249355874002855505630572881157768661565699234308864323444991740089424126644765901834893217850537561238381779701
Q = 97585403232599834391841697562831866882398283595752204839661452302849015191743
G = 3026428198448871560911273948775904894021223734849896518636879659245450255087355712137130232879729176234165431389765244977256536658615758785743263407214786275363905779612237581945081113239181301197997900356572774171981639514560272328546224595110774192385028733500291289317812371722629284149800688487727769955398624339682586054082268147456742133071634862396600773540952838200995800242129145326508422067038844286405227086881618482441314203987541190447654303054798087881329338176022929864962902790651768125012069902834734329015425085758237052534094752637772073086873173206308874929073310901306515908329314599650780064736400132061917290156891701745138710831081884276404041261553767736980946770436978446787920952817469972729006322915012620947171654193979308627061526920147871954065233795449196664099693485524346660482593903023551460943856523243310708574801533782667456482364699644745181729280493630242590751690154117219303141734740


def gen_pub(x, g, p, q):
    if 0 < x and x < q:
        return utils.powmod(g, x, p)

def gen_key(p, q, g):
    # 0 < x < q
    x = utils.randomnumber(q, inf=0)
    if 0 < x and x < q:
        y = utils.powmod(g, x, p)
        return x, y

def sign(m, p, q, g, x):
    k = utils.randomnumber(q-1, inf=2)
    while True:
        r = utils.powmod(g, k, p) % q
        if r == 0:
            k = utils.randomnumber(q, inf=2)
            continue
        break
    inv = utils.invert(k, q)
    h = m + x * r
    s = inv * h % q
    return r, s

def verify(m, sig, y, p=P, q=Q, g=G):
    r, s = sig
    w = utils.invert(s, q)
    u1 = m * w % q
    u2 = r * w % q
    r1 = gmpy2.powmod(g, u1, p)
    r2 = gmpy2.powmod(y, u2, p)
    r3 = r1 * r2 % p
    v = r3 % q
    return v == r

if __name__ == "__main__":
    priv, pub = gen_key(P, Q, G)
    message = "hello"
    h = hashlib.sha256()
    h.update(message.encode("utf-8"))
    m = long(h.hexdigest(), 16)
    
    r, s = sign(m, P, Q, G, priv)
    print(verify(m, (r, s), pub))

    h.update("an other message".encode("utf-8"))
    m = long(h.hexdigest(), 16)
    print(verify(m, (r, s), pub))