## Dsa (Crypto, 333p)
###ENG[PL](#pl-version)
We are given following python code - it is supposed to sign messages:```python#!/usr/bin/python
from hashlib import *from Crypto.Util.number import *from gmpy import *import os
def param_gen():    q = getPrime(1024)    while True:        t = 2*getRandomRange(1, 2**256)        p = t*q + 1        if is_prime(p):            break    while True:        h = getRandomRange(1, p-1)        g = pow(h, (p-1)/q, p)        if g != 1:            break    return (p, q, g)
def key_gen(params):    p, q, g = params    x = getRandomRange(1, q)    y = pow(g, x, p)    pubkey, privkey = y, x    return pubkey, privkey
def sign(msg, privkey, params):    p, q, g = params    while True:        k = getRandomRange(1, 1024) * pow(pubkey, privkey, p) % q        r = pow(g, k, p) % q        s = invert(k, q) * ( int(sha512(msg).hexdigest(), 16) + privkey * r) % q        if r*s != 0 :            break    return (int(r), int(s))
def verify(msg, signature, pubkey, params):    p, q, g = params    r, s = signature    if (0 < r < q) and  (0 < s < q) :        w = invert(s, q)        u1 = (int(sha512(msg).hexdigest(), 16) * w) % q        u2 = (r * w) % q        v = ((pow(g, u1, p) * pow(pubkey, u2, p)) % p) % q        if v == r:            return True    return False
params = param_gen()p, q, g = paramsprint paramspubkey, privkey = key_gen(params)
for i in range(0, 40):    msg = 'ASIS{' + os.urandom(16).encode('hex') + '}'    signature = sign(msg, privkey, params)    r, s = signature    print str((msg, r, s))
```
This challenge asks us to recover private key (x) given only a handful (around 40) signatures, public key, and public parameters given (attached to this solution in github).
After a while, we find a vulnerability in this challenge - ```pythonk = getRandomRange(1, 1024) * pow(pubkey, privkey, p) % q```
This is obviously insecure, as only 1024 ks can possibly be generated. If only we could recover k, this challenge would be trivial - given k we can calculate privkey from linear equation:
```pythons = invert(k, q) * ( int(sha512(msg).hexdigest(), 16) + privkey * r) % q<=>s * k - int(sha512(msg).hexdigest(), 16) * invert(r, q) % q = privkey```
But we don't know k... yet.
After another while, we noticed that if we could find two messages encrypted with the same k, challenge would be easy again. We could solve system of linear equations:
```s = invert(k, q) * ( int(sha512(msg0).hexdigest(), 16) + privkey * r) % qs = invert(k, q) * ( int(sha512(msg1).hexdigest(), 16) + privkey * r) % q```
...where k and privkey are unknowns. But again, this wasn't the case in this challenge.
And finally, when we began to fall into the pit od despair, we noticed that we could create another system of linear equations. Because k = (1..1024) * MAGIC (where `MAGIC = pow(publickey, privkey)`, but it's not important), we can write above equations as:
```s = invert(k1 * MAGIC, q) * (int(sha512(msg0).hexdigest(), 16) + privkey * r) % qs = invert(k2 * MAGIC, q) * (int(sha512(msg1).hexdigest(), 16) + privkey * r) % q```
In more mathematical terms, we can solve this system of equations as follows:
```s1 = (c1 + priv*r1) / (k1*magic)s2 = (c2 + priv*r2) / (k2*magic)
1 = (c1 + priv*r1) / (k1*magic*s1)1 = (c2 + priv*r2) / (k2*magic*s2)
(c1 + priv*r1) / (k1*magic*s1) = (c2 + priv*r2) / (k2*magic*s2)(c1 + priv*r1) * (k2*magic*s2) = (c2 + priv*r2) * (k1*magic*s1)c1*k2*magic*s2 + priv*r1*k2*magic*s2 = c2*k1*magic*s1 + priv*r2*k1*magic*s1c1*k2*s2 + priv*r1*k2*s2 = c2*k1*s1 + priv*r2*k1*s1priv*r1*k2*s2 - priv*r2*k1*s1 = c2*k1*s1 - c1*k2*s2 priv*(r1*k2*s2 - r2*k1*s1) = c2*k1*s1 - c1*k2*s2 priv = (c2*k1*s1 - c1*k2*s2) / (r1*k2*s2 - r2*k1*s1)```
Great, we have private key! But we have to bruteforce 1024 possible values of k1 and k2. It's easy enough in python:
```pythonfrom hashlib import *from Crypto.Util.number import *from gmpy import *import os
def hash(msg):    return int(sha512(msg).hexdigest(), 16)
def solve_for(params, set1, set2):    p, q, g = params    msg1, r1, s1 = set1    msg2, r2, s2 = set2    c1, c2 = hash(msg1), hash(msg2)    for k1 in range(1, 1024):        print k1        for k2 in range(1, 1024):            priv = (c2*k1*s1 - c1*k2*s2) * invert(r1*k2*s2 - r2*k1*s1, q) % q            if pubkey == pow(g, priv, p):                print priv params = (19990043472646209601994864878783430356973105946195950979159251182377121897576105462833887676561348770957108482823143337701724893247634876231133001112659622843245186144815694000013210989382541478073551247763586093331215996260234193847013210807939190828438263706901950228866893621933887960930392778176297205331569773161563794018138992335091883899396920586572927792555042350138728812073331L, 91629484598379105033512409529628860433949558415030791938154302542936417405614272511539966765257644706180090102931421315331051281240103609205686784098900471134711603588304765157414857991689054932897002635007537146809343047302801243835776634361209432398032301656027511721047704054332653738042312201931970395721L, 13622145302845273763875935516952425125176393702394844695432724066597834898277677169908234619701079219174550050531086255052810547971127992364106395259623997686454799745423099095097056224348731737512112568608406081844751809559052204755863089238863185755017905098158596830866362329243334855589147537151782745634416243769180780246626300677625340613515232605024658651528787608437872606367959L)set1 = ('ASIS{f178fcdecf80695744078436c8443d21}', 90237121958952251064976624492762150213417521896687572941345633764310618911601030617031373795520024583293535375710106225552196376797438589929204291257545448726331743603280815369427093966770848920593554708454565838054224752549404158493278464435213107237527453340811242850765181020853492694252650516970176641788L, 45699965566033911695982803604354032305058506238185457115666900773211243249439993822400900118887663777494151014067272471514622506941212402877792085312967213090334714190020080393819021065260516916603206309212756987461405393121419856054170230373811099272880018713486783939408418428725471847346917597357388173871L)set2 = ('ASIS{13d82a52a86b3f60d1d5d0a9a8fbd38c}', 82549501691566010240713957921730895287132128726058380260123211081436703044836270709304732846086147549660502736557189123678902405383474467404416541210982435469292602012427497998459504126706153698217704534579606635614323510632001857553260216879546038347723055837869594047336385462982125121614977106061534077159L, 14100015776662279808055950447194278668824709578034279558537621662053558677298084425976090376958899238099311275299915689425374231782256233762239739696534102757257328540054634833325260578944419955606514868448883176935887227050496260234118031035188783965371809668020726016057511098782430965590465392354859239207L)pubkey = 5120206348411789470161536127663499609309512038887109068976130122757582186109731229884381538683899917243667766639035225751229538595906667027298668257572271684995053081914448593696545954848592131805237134557157103971058735552127997038702518466039596176245969237004179261427946425137677159565508198606851760199742107673019486271187331752618149416170682584515782866631954825392784384052948
solve_for(params, set1, set2)```
And we finally get our flag: ASIS{1e58445616cd5178632ae15bef51c4a3}
###PL version
to be done?