Förståelsefråga gällande RSA-kryptering och Euklides algoritm
Hej,
Jag har en uppgift som handlar om att knäcka kryptot för ett meddelande $m=12$ med givna publika nycklar {e,n}={5,247}. Jag följer lösningen och har inga problem fram till punkten "d·e≡ϕ1⇔d·5+216·k=1."
Därefter börjar det bli svårt för mig att förstå hur de använder Euklides algoritmen för att bestämma den hemliga nyckeln d och dekryptera meddelandet. Jag har svårt att se varför de använder koefficienterna -43 och 173 i Euklides algoritm också.
Kan någon hjälpa mig att förstå detta steg för steg? Varför är det -43 och 173 som används i Euklides algoritm, och vad innebär det för dekrypteringen?
Därefter börjar det bli svårt för mig att förstå hur de använder Euklides algoritmen för att bestämma den hemliga nyckeln d och dekryptera meddelandet.
d·e≡1 ⇒ d=e-1
För att hitta den multiplikativa inversen för e använder de den "Utökade euklidiska algoritmen". (Se paragrafen "Computing multiplicative inverses in modular structures")
Ett exempel på en konkret beräkning: https://math.stackexchange.com/questions/1612740/how-to-find-multiplicative-inverse-of-17-in-mathbbz-26#:~:text=So%20going%20back%20up%20and,3%E2%89%A123mod26.
Det innebär att de går "backlänges".
Resultatet: d = e-1 = -43 vilket är (mod 216) lika med 173, eftersom 216-43=173.
Alltså -43 (aka 173) inte används i utan är resultatet av den utökade euklidiska algoritmen.
Lösningen är md = 12173 (mod 247).
För att kunna beräkna det använder man kunskapen att
173=9*19+2
och 129 = 246 = -1 (mod 247).
