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 . Jag följer lösningen och har inga problem fram till punkten "."
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 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.
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).
