Kategori: RSA kryptering

Følgende lille simple Python-program udfører RSA-kryptering.

For at lave det så simpelt som muligt, så viser jeg kun principperne i kryptering og dekryptering, ikke bestemmelse af de forskellige konstanter der bruges til krypteringen og dekrypteringen.

Jeg har altså ‘snydt’ ved at bruge faste værdier for følgende størrelser \(p, q, \varphi(n), e, d\). Disse værdier har jeg beregnet ved brug af Maple. Det er samme værdier som jeg bruger i dokumentet ‘RSA med Maple’.

Man kan narurligvis også få sit Python-program til selv at beregne disse værdier, men nu handler det bare om at se hvordan der krypteres og dekrypteres ved brug af Python.

Programmet er vist herunder:

#####################
# To primtal p og q #
#####################

p = 1009
q = 2003
n = p*q


##############################
# Eulers phi-funktion phi(n) #
##############################

phi=(p-1)*(q-1)


################################################################
# Tallet e primisk med phi, og tallet d så ed = 1 (mod phi(n)) #
################################################################

e = 1009037
d = 730661


#######################################################
# Indtast din klartekst i form af et tal med få cifre #
#######################################################

m = int( input('Indtast et tal med fire cifre: ') )


###########################
# Krtptering af klartekst #
###########################

enc=pow(m,e,n)


###############################
# Dekryptering af krypt-tekst #
###############################

dec=pow(enc,d,n)


#########################################################
# Udskriv klartekst, krypt-tekst og dekodet krypt-tekst #
#########################################################

print('Din meddelelse er',m,sep=' ')
print('Kryptoteksten er',enc,sep=' ')
print('Dekrypteret er',dec,sep=' ')

Hvis du nu tænker; det vil jeg da gerne prøve, så hent Python og Idle fra siden

https://www.python.org/downloads/

Du får både editoren Idle og programmeringssproget Python med i pakken, så når du har instaleret er du klar til at komme i gang.

Husk at du kun må hente programmer fra kilder du stoler på!

Når man krypterer en tekst med RSA-krypteringsmetoden, så krypterer man teksten ved brug af en nøgle. Den krypterede tekst sendes så til modtageren. Modtageren dekrypterer det vedkommende har modtaget, og står tilbage med den oprindelige tekst.

I RSA-kryptering har en person en privat nøgle og en offentlig nøgle. Den private nøgle holder personen for sig selv. Den offentlige nøgle kan offentliggøres.

Hvis man f.eks. skal sende en besked til banken, så henter man bankens offentlige nøgle. Man krypterer så beskeden ved brug af den offentlige nøgle. Så sender man den krypterede besked til banken. Når banken har modtaget den krypterede besked, så dekrypterer de den med deres private nøgle, og de kan så læse beskeden. Man så at sig ‘låser beskeden’ med den offentlige nøgle, og man ‘låser beskeden op’ med den private nøgle.

Principperne bag RSA-kryptering

Man finder først to store primtal \(p\) og \(q\).

Man ganger de to primtal med hinanden, resultatet kalder man \(n\) :

\( n = p \cdot q \)

Beregn så størrelsen \(\varphi(n)\)

\(\varphi(n) = (p-1) \cdot (q-1)\)

Find et tal \(e\) som er primisk med \(\varphi(n)\).

Da \(e\) og \(\varphi(n)\) er primiske, så vil man, med Euklids ‘omvendte algoritme’, kunne bestemme to tal \(d\) og \(k\), således at

\(e \cdot d + k \cdot \varphi(n) = 1 \)

Den private nøgle er så talparret \((d,n)\).
Den offentlige nøgle er talparret \((e,n)\).

Du tager nu din meddelelse \(m\). Beregn størrelsen

\(c = m^e \mod n\)

Dette er den krypterede meddelelse.

Du sender den krypterede meddelelse til modtageren. Modtageren beregner så værdien

\(c^d \mod n\)

Dette giver den oprindelige meddelelse \(m\).

For at gøre rede for hvorfor vi ender med den oprindelige meddelelse, så skal vi bruge Euler-Fermats sætning som siger, at er \(m\) og \(n\) indbyrdes primiske, så er

\(m^{\varphi(n)} = 1 \mod n\)

Dermed har vi at

\((m^e)^d = m^{ed} = m^{1-k \cdot \varphi(n)} = m \cdot m^{-k \cdot \varphi(n)} \newline \qquad \quad = m \cdot (m^{\varphi(n)})^{-k} = m \cdot 1^{-k} = m \mod n   \)

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\)