Jeg viser her hvordan man kan bruge matematik-programmet Maple til at kryptere og derefter dekryptere en meddelelse vha. RSA kryptering.
Trin 1: Først skal vi bruge to primtal p og q.
Man kan naturligvis tage de to primtal 11 og 13, eller andre små primtal man kender.
Man bør dog, hvis vi snakker sikkerhed, bruge meget store primtal, men princippet vises lettest ved at anvende små primtal.
Metoden jeg viser her kan bruges til vilkårligt store tal. Det skyldes at Maple ikke er begrænset af at skulle regne med tal med f.eks. 10 cifre.
Med Maple kan vi let finde lidt større primtal. Funktionen nextprime(tal) i Maple giver nemlig det første primtal der er større end tallet tal.
Eksempel: Vi vil bestemme det første primtal efter tallet 10:
\(nextprime(10)=11\)
Hvis vi derfor vil finde et primtal med f.eks. 3 cifre, så kan vi skrive nextprime(1000). Maple fortæller, at det første primtal, større end 1000, er tallet 1009. Dette kunne så være tallet p.
På samme måde kan vi finde det andet primtal q. Her tager vi f.eks. det første primtal større end 2000:
\(p:=nextprime(1000)=1009\)
\(q:=nextprime(2000)=2003\)
Vi skal nu beregne tallet n = pq. Det er bare at gange p og q sammen, og kalde resultatet for n:
\(n:=p \cdot q = 2021027\)
Trin 2: Nu skal vi beregne \(\varphi(n)\). Denne funktion \(\varphi(n)\) er Eulers \(\varphi\) -funktion.
Da n er et produkt af to primtal p og q, kan \(\varphi(n)\) beregnes således:
\(\varphi(n) = (p-1) \cdot (q-1) = 2018016\)
Trin 3: Vi skal nu finde et tal e, mellem 0 og \(\varphi(n)\), således at \(\gcd(e,\varphi(n)) = 1 \).
\(\gcd\) betyder ‘greatest common divisor’, eller på dansk; ‘største fælles divisor’.
At \(\gcd(e,\varphi(n)) = 1 \) betyder derfor, at det største tal, der både går op i e og \(\varphi(n)\), skal være tallet 1.
Vælger vi e som et primtal større end \(\varphi(n)/2\), så er vi hjemme: Da \(\varphi(n)\) er et primtal, går kun tallene 1 og \(\varphi(n)\) op i \(\varphi(n)\). Da e er valgt større end \(\varphi(n)/2\), så kan \(\varphi(n)\) ikke gå op i n. Den største fælles diviser for \(\varphi(n)\) og n er dermed 1.
Vi bruger igen nextprime for at finde e:
\(e:=nextprime(\frac{\varphi(n)}{2})=1009037\)
Nu skal vi finde endnu et tal d, således at \(e \cdot d \equiv 1 \mod \varphi(n)\). Det er en ligning Maple kan løse:
\( msolve(e \cdot d = 1,\varphi(n))=730661\)
Nu har vi altså tallene \(p, q, n = p \cdot q\), og de to tal \(e\) og \(d\).
Den offentlige nøgle er talparret \(n,e\).
\(n = 2021027 \) og \( e = 1009037\)
Den private nøgle er talparret \(n,d\).
\(n = 2021027 \) og \( d = 730661\)
Trin 4: Kryptering og dekryptering.
En tekst omsættes let til en række tal, f.eks. kan man bruge at bogstavet ‘A’ svarer til tallet 1, bogstavet ‘B’ svarer til tallet 2, o.s.v.
Vi forestiller os at vi har oversat en vigtig tekst til tallet \(m = 342391\).
Dette tal skal vi nu kryptere med vores RSA krypterings metode. Vi beregner
\(c = m^e \mod n = 169931\)
Den vigtige meddelelse 342391 krypteres altså til tallet 169931. Dette tal sendes til modtageren, og modtageren skal så dekryptere tallet 169931 til den vigtige besked 342391.
Modtageren beregner så
\(c^d \mod n = 342391\)
Den krypterede meddelelse 169931 dekrypteres altså til den oprindelige meddelelse 342391.
Alt i alt med Maple:
Bestemmer p, q og n:
\(p:=nextprime(1000)=1009\)
\(q:=nextprime(2000)=2003\)
\(n:=p \cdot q = 2021027\)
Bestemmer \(\varphi(n)\)
\(\varphi:= (p-1) \cdot (q-1) = 2018016\)
Bestemmer e :
\(e:=nextprime(\frac{\varphi}{2})=1009037\)
Bestemmer d:
\(msolve(e \cdot d = 1,\varphi)=730661\)
\(d:=730661\)
Meddelsen skrevet som et tal:
\(m:=342391\)
Den krypterede meddelelse:
\(c := m^e \mod n = 169931\)
Den dekrypterede meddelelse:
\(c^d \mod n = 342391\)