__PRIMJER__ -**Zadatak s Hacknite platforme - DSA** 

<file>
Tomislav je napisao aplikaciju za verifikaciju digitalnih potpisa.
Želi da pregledaš izvorni kod i testiraš je li nekako moguće zaobići verifikaciju.

Dostupan ti je izvorni kod programa, a na njegov servis se možete spojiti naredbom:
nc chal.platforma.hacknite.hr 13011 ako koristite Linux, ili naredbom: 
telnet chal.platforma.hacknite.hr 13011 ako koristite Windows
</file>


U zadatku je implementiran DSA ("Digital Signature Algorithm").

Kao unos se traži poruka te parametri "r" i "s". Kako bi riješili zadatak, moramo programu dati digitalno potpisanu poruku koja sadrži string "flag" i koja prolazi validaciju digitalnog potpisa (digitalni potpis čine parametri "r" i "s"). Budući da nemamo privatni ključ, ne možemo jednostavno potpisati poruku nego moramo pronaći nekakvu ranjivost u programu.


Kod za verifikaciju je sljedeći:

<code python>
def verificiraj(r, s):


    if r==0 or s==0 or r==q or s==q:
        return False

    w = modinverz(s, q)
    
    m = int(sha256(M).hexdigest(), 16)
    
    u1 = (m * w) % q
    
    u2 = (r * w) % q

    v = (pow(g, u1, p) * pow(y, u2, p)) % p % q
    
    if v == r:
        return True


</code>

Po DSA specifikaciji (koju je moguće pronaći npr. na Wikipediji) "r" i "s" moraju zadovoljavati uvjete <code>0 < "r" < "q"</code> te <code> 0 < "s" <"q" </code>
Vidimo da je implementacija u zadatku malo drukčija, ne provjerava se jesu li "r" i "s" manji od vrijednosti q.

Također, vrijedi proučiti kako je implementirana funkcija modinverz.

<code python>


def euklidov_prosireni(a, b):
    if a == 0:
	return (b, 0, 1)
    else:
	g, y, x = euklidov_prosireni(b % a, a)
	return (g, x - (b // a) * y, y)

def modinverz(a, m):
    g, x, y = euklidov_prosireni(a, m)
    return x % m
</code>

Funkcija modinverz računa multiplikativni modularni inverz pomoću proširenog euklidovog algoritma.
Više o operaciji multiplikativnog modularnog inverza možete pročitati na [[https://materijali.xfer.hr/docs/matematika/multiplikativni-inverz/|poveznici]]. 

Ono što je bitno, jest da će funkcija vratiti 0 ako multiplikativni modularni inverz nije definiran. Funkcija će vratiti nulu za 0 i //q// (koji nisu dozvoljeni), ali također i za sve višekratnike //q// (npr. //2*q//) koji jesu dozvoljeni.

To znači da ako vrijednost parametra //s// postavimo na //2*q// tada će vrijednost varijable //w// biti 0, što pak znači da će i vrijednost varijabli //u1// i //u2// također biti 0, a vrijednost varijable v biti 1. Kako bi verifikacija prošla, //v// mora biti jednak //r// . Vrijednost //r// možemo postaviti na 1, tako da zadatak možemo riješiti postavljanjem vrijednosti //r// na 1, a vrijednosti //s// na //2*q// , a u poruci m napišemo "flag" .