Jag leker lite med RSA-kryptering och programmering..
Nu är det ju så att formeln för kryptering är C = T^E mod N, där C är krypterad text, T är orig. text, E är den öppna nyckeln och N är modulus.(duh..)
N väljs ut med hjälp av två stora primtal, P och Q. Förslagsvis är ju P och Q slumpmässigt valda. Så säg att mitt program väljer två slumpmässiga primtal.
När man väljer E, så ska den vara relativt primt mot J(N).
J(N) är (P-1)*(Q-1).
För att (om jag har fattat matten rätt) välja ett E som är relativt primt mot J(N) måste jag veta båda talens primfaktorer, men eftersom J(N) är ett väldigt stort tal, är det ju en ganska komplicerad process att räkna ut dess primfaktorer. Och det är väl lite det, som hela RSA bygger på, men ändå. Jag måste ju faktiskt ha E.
Har jag missuppfattat det hela, eller måste man ha primfaktorerna? Isåfall, finns det nåt lättare sätt än att testa alla udda tal (+2) upp till roten?
Det är rätt uppfattat. Av någon konstig anledning brukar de flesta böcker som beskriver RSA hoppa över delen om hur den publika nyckeln beräknas, men i praktiken väljer man den genom att med Euklides algoritm beräkna för vilket e som gcd(e, j(n)) = 1.
I praktiken börjar man ofta med att välja ut ett Fermat-primtal (dvs ett primtal på formen 2^x + 1) och låter detta vara e. Först därefter genererar man p och q samtidigt som man testar att gcd(e, p-1) = 1 och gcd(e, q-1) = 1. Men det är mest ett trick för att snabba upp beräkningarna.
Men när jag sedan har E, hur får jag ut den privata nyckeln D?
T^ED mod N = T
är väl förmodligen vad som ska användas, men jag har inte förut använt mod så jag vet inte riktigt hur det funkar. D är ju den enda obekanta, men hur löser jag ut den?
Okej. Du vet att e*d = 1 mod (p-1)(q-1). Alltså är d = e^-1 mod (p-1)(q-1). För att beräkna den modulära inversen använder du Euklides utökade algoritm.
Av en händelse skrev jag en funktion för att beräkna just detta i en gammal tråd.
Ok, tack igen. Upptäckte precis att jag gjort något fel någon annanstans, så jag ska ta o börja om från början nu, men det blir lite lättare nu när jag har lärt mig lite om modulus och så.
Jag har ett litet problem med formeln d=e^-1 mod (p-1)(q-1)
I ett exempel hittade jag E=5 och D=77. (p-1)(q-1) = 96.
Detta stämmer bra då 5*77 mod 96 = 1
men säg då att man använder den först nämnda formeln.
d=5^-1 mod 96
ger d=0.2 (alltså 5^-1).. Det är ju iof inte så konstigt, men det tyder ju på att jag missuppfattat nånting i den första formeln.
När du räknar med en ändlig matematisk kropp (modulo 96 i ditt exempel) kan du inte räkna ut inverser på samma sätt som när man räknar med vanliga reella tal.
Säg att vi räknar modulo 5, för enkelhetens skull. Vi har två matematiska operationer, addition och multiplikation. Dessa kan vi definiera så här:
Alltså, 2+3 = 0 (mod 5) och 3*4 = 2 (mod 5). 24*2 = 3 (mod 5) eftersom 24 mod 5 = 4. Eftersom en invers till x är det talet som gånger x blir lika med 1, kan man se i multiplikationstabellen att inversen till 2 i det här fallet är 3: 2*3 = 1 (mod 5). Jag vet inte om det blev så mycket klarare, men det är så modulo-räkning och inverser fungerar.
Det är nu Euklides utökade algoritm kommer in i bilden, eftersom den låter dig räkna ut inversen utan att ägna flera år åt att skriva tabeller när du ska kryptera något.
Det blev säkert fel någonstans, men jag hoppas du förstår principen.
Nu har jag fixat och lärt mig Euclides utökade och det var inga större problem..
Om man tar det gamla exemplet så visar det sig att 5*77=1 (mod 96) som sagt..
Men jag har ändå ett problem.. RSA formeln är ju C=T^E mod N och T=C^D mod N.
om J(N) = 96 är N = 119. (I det här fallet.) Om vi för enkelhetens skull sätter T = 10 får man C=10^5 mod 119 = 40.
Om C = 40 får man T=40^77 mod 119 = 18.
Det stämmer alltså inte. Förmodligen är det väl bara jag som har missuppfattat formeln som jag missuppfattade det där med modulär invers förut... Men på vilket sätt är det jag har missuppfattat?
Det blir även fel med andra E, D och N, även om E och D är modulära inverser av varandra och relativt prima mot J(N).
Och en annan fråga, ungefär vilken storlek bör det vara på E, D och N? Eller istället för N, P och Q?
Flashback finansieras genom donationer från våra medlemmar och besökare. Det är med hjälp av dig vi kan fortsätta erbjuda en fri samhällsdebatt. Tack för ditt stöd!
