Differences

This shows you the differences between two versions of the page.

--- dsa [2025/01/21 16:08] – created lss
+++ dsa [2025/12/01 11:40] (current) – external edit 127.0.0.1
@@ Line 1: / Line 1: @@
 __PRIMJER__ -**Zadatak s Hacknite platforme - DSA**
-U zadatku je implementirana specifikacija DSA ("Digital Signature Algorithm").
+<file>
-Kao unos se traži poruka te parametri "r" i "s". Kako bi se flag ispisao poruka mora biti postavljena
+Tomislav je napisao aplikaciju za verifikaciju digitalnih potpisa.
-na "flag" te funkcija verificiraj mora vratiti true.
+Ž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>
-    if verificiraj(r, s):
-	if "flag" in poruka:
-           print("Poruka verificirana")
-           print(os.environ["flag"])
+U zadatku je implementiran DSA ("Digital Signature Algorithm").
-Ranjivost programa nalazi se u provjerama nad parametrima "r" i "s".
+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):
@@ Line 18: / Line 25: @@
         return False
+    w = modinverz(s, q)
     m = int(sha256(M).hexdigest(), 16)
@@ Line 30: / Line 39: @@
-Po DSA specifikaciji "r" i "s" moraju biti 0 < "r" < "q" te 0 < "s" <"q".
+</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 euklidov_prosireni(a, b):
+def modinverz(a, m):
-	    if a == 0:
+    g, x, y = euklidov_prosireni(a, m)
-		return (b, 0, 1)
+    return x % m
-	    else:
+</code>
-		g, y, x = euklidov_prosireni(b % a, a)
-		return (g, x - (b // a) * y, y)
-	def modinverz(a, m):
+Funkcija modinverz računa multiplikativni modularni inverz pomoću proširenog euklidovog algoritma.
-	    g, x, y = euklidov_prosireni(a, m)
+Više o operaciji multiplikativnog modularnog inverza možete pročitati na [[https://materijali.xfer.hr/docs/matematika/multiplikativni-inverz/|poveznici]].
-	    return x % m
+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.
-Funkcija koja određuje vrijednost w jest modinverz. Ukratko, modinverz interno koristi Euklidov algoritam kako bi se pronašao modularni inverz broja "a" mod "m".
+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" .
-Modularni inverz "k" jest broj za koji vrijedni ("k"*"a") mod "m" == 1. Ako takav broj ne postoji vraćena je 0. Npr. ako je vrijednost "a" postavljena na 0, ne postoji
-broj "k" koji će zadovoljiti uvjet zbog čega će i sami "k" biti 0.
-Kako bi verifikacija bila uspješna potrebno je zadovoljiti uvjet "v" == "r".
-Vrijednost "v" određena je, među ostalom, umnoškom rezultata funkcija pow() čiji su eksponencijali "u1" i "u2". Kada bi parametri "u1" i "u2" bili jednaki 0, obije funkcije bi
-vratile 1 pa bi samim time vrijednost v bila 1 (što je unutar dozvoljene domene "r").
-Zbog toga je rješenje da se "w" postavi na vrijednost 0 jer će "u1" i "u2" će također biti 0 i time dobiti "v" == 1.
-Otprije, zaključili smo da je "w" nula kada "s" nema modularni inverz. Neke od vrijednosti koje nikad nemaju inverz su npr. 0, q, 2*q, 3*q itd... Zbog neispravnih provjera nad parametrima
-vrijednost veće od "q" su dozvoljene stoga je rješenje npr. "s" = 2*q.