--- title: "RSA Matteproblem med Euklides Utökade Algoritm" type: "forum-thread" url: "https://www.webforum.nu/amne/matematik/151865-rsa-matteproblem-med-euklides-utökade-algoritm" topic: "Matematik" topic_url: "https://www.webforum.nu/amne/matematik" author: "lilja" published: "2006-09-29T04:56:55.000Z" updated: "2006-09-29T16:12:36.000Z" replies: 5 views: 909 page: 1 pages: 1 language: "sv-SE" site: "webForum — webforum.nu" rights: "Upphovsrätten till varje inlägg tillhör dess författare." attribution: "Citera som: webForum, https://www.webforum.nu/amne/matematik/151865-rsa-matteproblem-med-euklides-utökade-algoritm" --- # RSA Matteproblem med Euklides Utökade Algoritm ## #1 — lilja, 2006-09-29T04:56Z OBS, detta är för dem som vet vad RSA är och hur man räknar med den algoritmen... Första gången jag stötte på detta läste jag diskret mattematik och hade bra exempel så jag lärde mig de. Nu befinner jag mig i USA och läser bl.a. datorsäkerhet. I en läxa vi hade tills igår skulle vi räkna ut nycklarna och kryptera/dekryptera ett värde. Jag kommer dock inte ihåg hur man gör euklides utökade algorithm för att hitta dne privata nyckeln. Oroa er inte för att hjälpa mig för mycket då läxan redan är inlämnad :) Jag testade alla värde från upp till p-1 för att hitta privata och det funkar men så kan man inte göra om man bara har en simpel räknare... Läraren har inte nämmnt euklides utökade algorithm men jag vet att man gör så. Lägger med ett exempel på så långt jag kommer och en länk till för mer information, men som jag inte tycker förklarar det jag vill :) på svenska och inte utökad... Vore underbart om någon har lite tips på hur man fortsätter. Bilagor: - [RSA Algorithm.pdf](https://www.webforum.nu/a/12331.pdf) Permalänk: https://www.webforum.nu/p/151865 ## #2 — Muzzafarath, 2006-09-29T06:06Z Euklides heter Euclid på engelska ;) Om vi fortsätter från det du har gjort i a) i pdf:en, så ska vi helt enkelt plocka bort parantesen och sen slå ihop termerna: 1 = 3 - (20 - 3\*6) = 3 - 20 + 3\*6 = (3 + 3\*6) - 20 = 3\*7 - 20 Alltså är 3\*7 = 1 (mod 20), så d = 3. Permalänk: https://www.webforum.nu/p/1875581 ## #3 — lilja, 2006-09-29T12:53Z 1=3\*7 då -20 är detsamma som 0 när man tar mod 20 :) Hmm, om vi testar en annan... Säg c) i min PDF... p=7, q=11, e=17, M=18 n=p\*q=7\*11=77 ф(n)=(p-1)(q-1)=(6)(10)=60 gcd(ф(n),e)=gcd(60,17) 60=17\*3+9 17=9\*1+8 9=8\*1+1 // gcd(60,17)=1 1=9-8\*1 1=9-(17-9) 1=9-(17-(60-17\*3)) 1=9-(17-60+17\*3) 1=9-17+60-17\*3 Äsh, nu är jag lost igen :( Hur gör jag här? Räknar antalrt 17?? Känner på mig att nyckeln blir negativt så att jag ska ändra den till ett positivt värde men jag ser inte riktigt hur? Permalänk: https://www.webforum.nu/p/1875662 ## #4 — Muzzafarath, 2006-09-29T15:17Z Försök istället att öppna upp paranteserna och förenkla vid varje steg. För att inte vela bort dig vill du bara ha två termer innan du "sätter in" nåt som du fick från Euklides "vanliga" algoritm. 1 = 9 - 8\*1 = (sätter in nåt från Euklides algoritm) 9 - (17 - 9) = (förenklar) 9 + 9 - 17 = 9\*2 - 17 = (åter redo att sätta in nåt från Euklides algortim) (60 - 17\*3)\*2 - 17 = (förenklar igen) 60\*2 - 17\*6 - 17 = 60\*2 - 17\*7. Permalänk: https://www.webforum.nu/p/1875704 ## #5 — lilja, 2006-09-29T15:58Z > **Muzzafarath skrev:** > > 1 = > 9 - 8\*1 = (sätter in nåt från Euklides algoritm) > 9 - (17 - 9) = (förenklar) > 9 + 9 - 17 = > 9\*2 - 17 = (åter redo att sätta in nåt från Euklides algortim) > (60 - 17\*3)\*2 - 17 = (förenklar igen) > 60\*2 - 17\*6 - 17 = > 60\*2 - 17\*7. Ok, men vad blir den privata nyckeln här? Enligt vad jag kom fram till i mitt "brutefoce" program ska det vara 68? Permalänk: https://www.webforum.nu/p/1875717 ## #6 — lilja, 2006-09-29T16:12Z Jag vet förresten vet inte om mitt svar är rätt, verkar fel :( I mitt senare exempel, vad blir den privata nyckeln där och hur får man fram den?? Permalänk: https://www.webforum.nu/p/1875721 --- Tråden på webben: https://www.webforum.nu/amne/matematik/151865-rsa-matteproblem-med-euklides-utökade-algoritm