Differences

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

--- dsa [2025/01/22 13:38] – lss
+++ dsa [2025/12/01 11:40] (current) – external edit 127.0.0.1
@@ Line 3: / Line 3: @@
 <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
+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:
-naredbom nc chal.platforma.hacknite.hr 13011 ako koristite Linux odnosno telnet chal.platforma.hacknite.hr 13011 ako koristite Windows
+telnet chal.platforma.hacknite.hr 13011 ako koristite Windows
 </file>
@@ Line 45: / Line 44: @@
 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):
+def euklidov_prosireni(a, b):
-	    g, x, y = euklidov_prosireni(a, m)
+    if a == 0:
-	    return x % m
+	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.
-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.