RSA wetenschapsweek

3489 days ago by J.Demeyer

Getallen factoriseren

Getallen factoriseren gebeurt met het commando "factor()"
factor(122) 
       
factor(1245672) 
       
factor(124588456845645672) 
       
factor(124588456845455654564457568475989945446489456564486645672) 
       

Voor erg grote getallen zie je dat Sage niet direct een oplossing vindt. Je kan de berekening onderbreken door in het menuutje Action "interrupt" aan te klikken of op de ESC-toets te duwen.
factor(10^1000+1) 
       

Priemgetallen genereren

Zij $n\in \mathbb{N}.$ Het commando next_prime($n$) geeft het eerste priemgetal groter dan $n$. Het commando random_prime($n$) geeft een willekeurig priemgetal tussen $2$ en $n$.
next_prime(100) 
       
next_prime(1000) 
       
next_prime(10^100) 
       
random_prime(10^100) 
       

Modulorekenen

$a \bmod n$ laat je Sage berekenen met het commando mod(a,n). Bijvoorbeeld 14 Mod 12=2, inderdaad
Mod(14,12) 
       
Mod(2^1000+1,101) 
       

Inversen modulo n berekenen

Het inverse van een getal $\bmod   n$ berekenen gaat als volgt. Stel dat ggd$(a,n)=1,$ dan berekenen we het inverse met het commando mod(a,n)^(-1). We gaan met enkele voorbeeldjes na dat als b=mod(a,n)^(-1), dan $(ab \bmod n)=1.$

$a=3,$ $n=7$:
Mod(3,7)^(-1) 
       
5*3 
       
Mod(5*3,7) 
       

$a=13,$ $n=20:$
Mod(13,20)^(-1) 
       
13*17 
       
Mod(13*17,20) 
       

Als we het inverse proberen berekenen van $a \text{ mod }n$ met ggd($a,n)\neq 1,$ geeft Sage een foutmelding weer:
Mod(6,12)^(-1) 
       

Machten modulo n berekenen

Machten berekenen van een getal $\bmod  n$ doe je door $\bmod(a,n)^c$ te berekenen en niet $\bmod(a^c,n)$!!!! Dit tweede commando werkt ook, maar zal voor grote getallen veel langer duren.
%time Mod(9,100)^10000000 
       
%time Mod(9^10000000,100) 
       

Tekst omzetten naar getallen

Hier staan enkele stukken code waarmee je tekst naar een groot getal kan omzetten en omgekeerd. De tekst die je ingeeft moet steeds tussen aanhalingstekens staan!!! De code in het volgende vakje moet je niet lezen.
%hide n = 10^1000 def tekst_naar_getal(woord): list=[] for i in range(len(woord)): list.append(ord(woord[i])-32) getal=sum(list[i]*100^i for i in range(len(list))) if getal >= n: raise ValueError('Je zin is te lang') return getal def getal_naar_tekst(number): number=Integer(number) str="" while number != 0: str += chr((number % 100) + 32) number //= 100 return str 
       

Op de volgende manier zet je de boodschap "De landing in Normandie vond plaats op 6 juni!" om in een groot getal en dan weer naar tekst.
tekst_naar_getal("De landing in Normandie vindt plaats op 6 juni!") 
       
getal_naar_tekst(173788574002200807900838465657680008468787386006973687865778279460078730071787368786576006936) 
       

Kies zelf een zin, laat deze naar een getal omzetten en omgekeerd.
 
       

Voorbeeld van het RSA systeem

We passen de commando's die we net geleerd hebben toe op het RSA cryptografisch systeem.

Romeo wilt een geheim bericht naar Julia sturen. Julia kiest twee priemgetallen $p_1,p_2,$ en zij berekent het product $n=p_1p_2$.
p1 = random_prime(10^60) p2 = random_prime(10^60) n = p1*p2 n 
       

Merk op dat Sage het getal $n$ niet onmiddellijk kan factoriseren:
factor(n) 
       

Nu berekent Julia $m=(p_1-1)(p_2-1)$ en kiest zij een getal $e < m$ waarvoor ggd$(e,m)=1.$ In de praktijk wordt heel vaak $e=65537=2^{16}+1$ gekozen, dus dat doen we hier ook. Natuurlijk moeten $p_1$ en $p_2$ dan zodanig zijn dat $65537<m$.
m = (p1-1)*(p2-1) e = 65537 e < m 
       
gcd(e,m) 
       

Julia stuurt de getallen $n$ en $e$ door naar Romeo.

Romeo maakt van het bericht dat hij wil sturen een getal $x$. Hij encrypteert $x$ gebruikmakend van de getallen $n$ en $e$ die Julia hem gegeven heeft. Hij berekent dus $(x \bmod{n})^e$.
x = tekst_naar_getal("I love you") x 
       
y = Mod(x,n)^e y 
       

Romeo stuurt $y$ naar Julia. Zij wil deze boodschap ontcijferen, ze bepaalt eerst $d=(e \bmod{m})^{-1}.$
d = Mod(e,m)^(-1) d 
       

We controleren dat $(e d\bmod{m})=1$.
Mod(e*d,m) 
       

Nu kan Julia de boodschap van Romeo ontcijferen, ze kan immers $(y \bmod n)^d$ bepalen.
ontcijferd = Mod(y,n)^d 
       
getal_naar_tekst(ontcijferd) 
       

Opdracht

Iemand heeft een slechte keuze gemaakt voor zijn $n$! Sage kan deze $n$ namelijk direct factoriseren. Je onderschepte de getallen $n$, $e$ en een vercijferde boodschap $y$. Ontcijfer het bericht $y,$ zet dit om in tekst en voer de opdracht om het eerst uit.
n = 7000376966006201716470139287964883138783459303 e = 451133587 y = 64011891091084385385982713194591836266284687 
       

Extra opdracht

Je kan ook eens proberen uit te zoeken hoe lang het duurt om getallen te factoriseren. Gebruik hiervoor %time. Is het belangrijk dat beide priemgetallen even groot zijn of mogen we ook een klein en een groot priemgetal nemen?
p1 = next_prime(10^20) p2 = next_prime(10^21) n = p1 * p2 
       
%time factor(n)