RSA, een openbaar-sleutelsysteem (public key system)

Inleiding | Wiskunde | Versleutelen | Getaltheorie | Voorbeeld | RSA-130 | Anecdote | Naschrift  ][ DK & Maple

---

Een korte beschrijving van een methode voor codering (versleuteling) van informatie
met gebruikmaking van het computerprogramma Maple V, release 4
februari 1997

(Literatuur: Dr. Ir. J.C. A. van der Lubbe, Basismethoden Cryptografie, Delft, 1994, blz. 140-152)

1. Inleiding
In een openbaar-sleutelsysteem (public key system) is er steeds sprake van twee sleutels, een sleutel voor het vercijferen van van de informatie en een tweede sleutel voor het ontcijferen. De vercijfersleutel is in principe openbaar; dat wil zeggen, dat een ieder ervan kan kennisnemen en de sleutel kan gebruiken voor vercijfering van boodschappen. Het basisidee van openbare-sleutelsytemen bestaat nu hierin, dat weliswaar iedereen een boodschap kan vercijferen, maar dat niet iedereen de aldus verkregen cijfertekst kan ontcijferen. Er wordt namelijk voor gezorgd, dat het ondoenlijk is (of althans bijna ondoenlijk) de ontcijfersleutel af te leiden uit de vercijfersleutel.

Een van de bekendste en meest gebruikte openbare-sleutelsystemen is het RSA-systeem. Het ontleent zijn naam aan de eerste letters van de achternamen van degenen die het systeem ontworpen hebben: Ron L. Rivest, Adi Shamir en Len Adleman van het Massachusetts Institute of Technologie (MIT).
Zie RSA Laboratories: http://www.rsasecurity.com/rsalabs/node.asp?id=2092.

Om te beginnen hebben we natuurlijk een methode nodig waarmee we een boodschap in letters kunnen omzetten naar een getal (en omgekeerd).
We zullen in het onderstaande alleen kleine letters gebruiken en geen andere leestekens dan de spatie. De afbeelding van de letters naar getallen houden we eenvoudig: a > 1, b > 2, ..., z > 26 en spatie > 27.
De Maple-procedures to_number en from_number doen inderdaad wat we van ze mogen verwachten:

Met het volgende reultaat

> to_number(`hallo wie is daar`);

801121215272309052709192704010118

> from_number(");

hallo wie is daar

Klik hier voor de beide procedures.

2. Wat wiskunde
Dat RSA inderdaad goed werkt, is gelegen in het feit, dat het eenvoudig is een product van twee priemgetallen te berekenen (we zullen dat hieronder zien), maar dat het een stuk moeilijker is (en bijzonder tijdrovend, en daardoor soms zelfs onmogelijk) om uit dat product de oorspronkelijke priemgetallen weer te bepalen (ontbinden in factoren). Als we een groot geheel getal bekend maken dat slechts twee grote priemfactoren heeft, dan is de kans groot, dat een willekeurig iemand niet in staat zal zijn dat getal in factoren te ontbinden.

In de volgende voorbeelden zijn de priemgetallen bewust kleiner gehouden dan in werkelijkheid in de cryptografie gebruikelijk zou zijn (daar worden producten van priemgetallen gebruikt die liggen in de orde van 10¹⁰⁰; ze bestaan dus uit ongeveer 100 cijfers).
Een moderne PC met een 100 Mhz Pentium processor zou, met de laatst bekende methode op het terrein van ontbinden van grote getallen, zo'n 18 jaar nodig hebben voor het ontbinden van een dergelijk getal.

Willen we het RSA-systeem gebruiken voor het versleutelen van berichten, dan is het in de eerste plaats nodig twee priemgetallen te kiezen.
Maple heeft een functie (nextprime) die het eerste priemgetal geeft, dat volgt op een gegeven geheel getal.

> p:=nextprime(113);

p := 127

Deze functie gebruiken we om de twee te gebruiken (voor ons doen en doel grote) priemgetallen te genereren.

> p:=nextprime(7347124781320478301247);

p := 7347124781320478301377

We kiezen het volgende priemgetal 'ietsje' groter.

> q:=nextprime(478574839027542389055784235534782043);

q := 478574839027542389055784235534782067

Een van de getallen die nu als de public key (openbare sleutel) worden gepubliceerd, is het getal n dat ontstaat door vermenigvulding van de zojuist gekozen priemgetallen p en q.

Vervolgens wordt de Euler-waarde van n berekend.
Dit gebeurt via de zogenoemde Euler-functie j (de functie j wordt ook wel totient-functie genoemd). De waarde van j(n) is het aantal gehele getallen dat kleiner is dan n en dat tegelijk copriem is met n.
Twee getallen die copriem zijn, worden ook wel onderling ondeelbaar (of relatief priem) genoemd. Ze hebben dus geen gemeenschappelijke delers ongelijk aan 1. Hun grootste gemeenschappelijk deler is dus het getal 1.

Een voorbeeld van de functie j met kleine getallen.
We gaan uit van het getal n = 15.
Voordat we j(n) met Maple kunnen berekenen (in Maple zit de functie phi in een librarry -ook wel package genoemd), moeten we deze functie inlezen via de opdracht:

> with(numtheory):
Warning, new definition for order
> n := 15:
> phi_n := phi(n);

phi_n := 8

De gehele getallen die kleiner zijn dan 15 en relatief priem met 15, zijn: 1, 2, 4, 7, 8, 11, 13, 14. Hun aantal is inderdaad 8.
Dus j(15) = 8.

Hieronder staat nog een berekening van j(n) als n een priemgetal is.

> n := nextprime(127);
> phi_n := phi(n);

n := 131
phi_n := 130

Merk op, dat in dit geval j(n) = n - 1.

Voor de hierboven in eerdere instante gekozen grote priemgetallen (p en q) hebben we:

> n := p*q;

n := 3516149059535715479653013539650200318590903767034041006259

Het berekenen van j(n) met behulp van de ingebouwde Maple-functie phi is voor grote priemgetallen bijzonder tijdrovend, omdat n daarbij, ook door Maple, in factoren moet worden ontbonden.
Omdat we de ontbinding van n echter kennen, is j(n) eenvoudig uit te rekenen.
In dit geval geldt namelijk (we vermelden dit hier zonder bewijs, maar zie ook de berekening van j(131) = 130):
  j(n) = (p-1) * (q-1)
zodat

> phi_n:=(p-1)*(q-1);

phi_n := 3516149059535715479652534964811172768854723201478027922816

Vervolgens is het noodzakelijk een derde geheel getal, e, te kiezen. Dit getal moet tussen 3 en j(n) in liggen en copriem zijn met j(n).
Met behulp van dit getal e, wordt dan nog een vierde getal d berekend, dat een rol zal spelen bij de decodering.
We kiezen nu allereerst e als een priemgetal (het priem zijn van e is echter niet noodzakelijk).

> e:=nextprime(432429);

e := 432433

Om na te gaan of e relatief priem is met j(n), kunnen we een deling uitvoeren (met behulp van de Maple-opdracht evalf) om na te gaan of e geen factor is van j(n).
Het is ook mogelijk met de Maple-opdracht gcd (greatest common divisor, grootste gemeenschappelijk deler) na te gaan of er sprake is van relatief priem zijn van j(n) en e.
We doen het beide.

> evalf(phi_n/e);

.8131084028 10⁵²

> gcd(phi_n,e);

1

Zoals reeds opgemerkt, wordt het getal e gebruikt bij het berekenen van het getal d. Tussen e en d bestaat de volgende relatie:
  e ^. d = 1 ( mod (p-1)(q-1) )
Dit wil zeggen:
d is een zodanig getal, dat het product e ^. d bij deling door (p-1)(q-1) (dit getal is gelijk aan j(n) ) als rest 1 geeft.

Dit komt overeen met het berekenen van de getallen d en k (k is voor ons verder niet interessant) uit onderstaand lineaire (diophantische) vergelijking (deze vergelijking wordt ook wel de Euclidische algoritme voor de grootste gemeenschappelijke deler genoemd):
  e ^. d + j(n) ^. k = 1 ( mod j(n) )
Uit de algebra is bekend (hier ook weer zonder bewijs), dat deze vergelijking een oplossing heeft, omdat e en j(n) releatief priem zijn. De oplossing vinden we met de Maple-opdracht igcdex (extended greatest common divisor for integers).

> euclid:=igcdex(e, phi_n, 'd', 'k');

euclid := 1

De hierboven berekende waarden van d en k zijn nu:

> d;k;

-1330245347001831618935545437658800010601949240140797229103
163600

Omdat (in dit geval) d negatief is, kiezen we voor d een andere waarde uit de klasse van getallen die aan de vergelijking voldoen:

> d:=d mod phi_n;

d := 2185903712533883860716989527152372758252773961337230693713

Alle te gebruiken getallen voor het openbare-sleutelsysteem zijn nu bekend.

Het getallenpaar (n, e) vormt nu de openbare sleutel waarmee aan een bepaalde ontvanger een gecodeerde boodschap kan worden gezonden.
Alle andere grootheden worden geheim gehouden. De getallen p, q en j(n) kunnen zelfs worden vergeten, omdat deze bij het verdere proces niet meer behoeven te worden gebruikt.

3. Versleutelen
Nu kan worden begonnen aan het versleutelen van de boodschap op basis van de getallen n en e.
Het getal d en ook weer het getal n zijn nodig bij het ontsleutelen van de boodschap.
d dient dus gebruikt te worden door (en alleen bekend te zijn aan) de (rechtmatige) ontvanger van de versleutelde boodschap. Deze ontvanger is dus ook 'eigenaar' van de openbare sleutel (n, e).

De boodschap die bestaat uit letters, wordt nu omgezet in een getal M. Daarbij kan gebruik gemaakt worden van een procedure zoals die hierboven is weergegeven.
Het eerste voorbeeld houden we eenvoudig.

> M := to_number(`hi`);

M := 809

Het getal M kan bij een lange boodschap een fiks groot getal worden.
Daarom wordt een gecodeerde boodschap vaak in blokken geknipt bestaande uit elk bijvoorbeeld 4 cijfers.Elk blok wordt dan opgevat als een afzonderlijke cijferboodschap M (een voorbeeld hiervan wordt verderop gegeven).

> M_fiks_groot := to_number(`neem ten spoedigste contact op`);

M_fiks_groot := 140505132720051427191615050409071920052703151420010320271516

Deze laatste boodschap wordt nu vercijferd door steeds 4 cijfers op te vatten als een afzonderlijke boodschap en deze te vercijferen:
M₁ = 1405, M₂ = 0513, enzovoorts.

Elke boodschap (afzonderlijk) wordt nu omgezet in een vercijferd blok C. C wordt in twee stappen berekend.

• Stap 1: Bereken de waarde van M^e. Noem deze waarde ME.
• Stap 2: Bereken de rest bij deling van ME door n. Deze rest is het getal C.

Opmerking
Gezien de redelijk grote waarde van het getal e, is het toch al verstandig om een te lange boodschap in kleine stukjes (van vier cijfers elk) te hakken. Een programma als Maple is zelfs niet in staat dergelijke machten te berekenen:

> M_fiks_groot^e;
Error, object too large

[einde opmerking]

We gebruiken in hetgeen volgt de waarde van M, die we als een enkelvoudige boodschap kunnen opvatten. Splitsen in blokken hoeft nog niet, want M bestaat uit drie cijfers.

> M;

809

De Maple-functie mod (samen met de functie Power) is in staat bij ingewikkelde berekeningen tussentijds vereenvoudigingen te bewerkstelligen.
Daarom is het verstandig de berekening van C (de beide hierboven genoemde stappen) in één Maple-opdracht te plaatsen:

> C:=Power(M,e) mod n;

C := 445306247884178784227069275130014327352175968049363742217

En dit 'bericht' wordt nu naar de ontvanger gezonden!

Merk daarbij op, dat het korte bericht ( "hi" ) heel wat langer geworden is. Dit wil niet zeggen, dat wat langere berichten dan in dit voorbeeld ook zullen leiden tot langere gecodeerde getallen. Immers elke M wordt gecodeerd tot een C die nooit groter kan zijn dan n (immers de waarde van C vinden we na deling door (modulo) n ).

De ontvanger van C gebruikt nu het (alleen aan hem bekende) getal d om het bericht te decoderen.
Hij berekent C^d mod n. Daardoor krijgt hij een geheel getal tussen 1 en n, dat de boodschap vormt.

> Boodschap:=Power(C,d) mod n;

Boodschap := 809

> from_number(Boodschap);

hi

Als laatste voorbeeld met de gegeven openbare sleutel geven we een wat langere boodschap afkomstig van René Descartes.

> Send:=`cogito ergo sum`;

Send := cogito ergo sum

> M:=to_number(Send);

M := 31507092015270518071527192113

Ook al is M hier behoorlijk groot (voor onze begrippen), we splitsen M voor het gemak maar niet in een aantal deelboodschappen.

> C := Power(M, e) mod n;

C := 2850186645719694427305359029680162004660716473283715291765

> Received := Power(C,d) mod n;

Received := 31507092015270518071527192113

> Message:=from_number(Received);

Message := cogito ergo sum

Hieronder staat nog een voorbeeld met kleine waarden van p en q.

> p := 3:
> q := 17:
> n := p*q;
> phi_n := (p-1)*(q-1);

n := 51
phi_n := 32

> e := 7:
> euclid := igcdex(e,phi_n,'d','k');

euclid := 1

> d := d mod phi_n;

d := 23

> Msend := 2;

Msend := 2

> C := Power(Msend,e) mod n;

C := 26

> Mreceived := Power(C,d) mod n;

Mreceived := 2

Deze waarde van Mreceived is gelijk aan de oorspronkelijke waarde Msend. De boodschap is dus goed ontvangen.
Overigens leent dit laatste voorbeeld zich goed voor berekeningen met een zakrekenmachine, waarbij dan gebruik gemaakt wordt van enkele eigenschappen uit de modulo-rekening.

Bij het ontcijferen van de boodschap, het berekenen van de waarde van Mreceived dus, komen we de volgende uitdrukking tegen:

Mreceived := 26²³ mod 51

Bij het berekenen van deze waarde kan worden volstaan met de berekening van de samenstellende machten modulo 51, omdat geldt
(i) ab mod k = (a mod k) * (b mod k).
Verder kan gebruik gemaakt worden van de volgende modulo-eigenschap:
(ii) ALS a = b (mod k) DAN a² = b² (mod k)
We hebben nu
  26²³ = 26¹ * 26² * 26⁴ * 26¹⁶
Volgens eigenschap (i) behoeven we nu alleen maar te kijken naar de waarden van
   a = 26 mod 51
   b = 26² mod 51
   c = 26⁴ mod 51
   d = 26¹⁶ mod 51
Voor b vinden we

> b:=26^2 mod 51;

b := 13

En dus volgens eigenschap (ii):
   c = 26⁴ mod 51 = 13² mod 51

> c:=13^2 mod 51;

c := 16

En dus wederom volgens eigenschap (ii):
   d = 16⁴ mod 51

> d:=16^4 mod 51;

d := 1

Hierdoor wordt Mreceived gelijk aan

> 26*13*16*1 mod 51;

2

Door gebruik te maken van de eigenschappen (i) en (ii) wordt de rekencomplexiteit van het machtsverheffen modulo n aanzienlijk beperkt (en daardoor bij kleine getallen geschikt voor een zakrekenmachine).

4. Enkele stellingen uit de getaltheorie
De getallen d en e worden in het RSA-systeem dus zo bepaald dat ze altijd aanleiding geven tot vercijfer- en ontcijferoperaties, die elkaars inverse zijn. Om aan te tonen, dat dit altijd zo is, moet een beroep worden gedaan op stellingen uit de getaltheorie (theoretische algebra).

Stelling
j (phi) is de Euler-functie (ook wel totient-functie genoemd). p en q zijn twee priemgetallen met n = p ^. q.
Nu geldt:
  j(n) = j(p) ^. j(q) = (p-1)^.(q-1)

Bewijs: j(a) is gelijk het aantal getallen kleiner dan a, dat met a relatief priem is. Voor een priemgetal p geldt dus j(p) = p - 1.
Dus:
j(n) = (p - 1) ^. (q - 1).
[einde bewijs]

De stelling waarop het RSA-systeem gebaseerd is luidt als volgt:

Stelling ( stelling van Euler )
Voor alle a en n die relatief priem zijn ten opzichte van elkaar en waarbij n > 0 en 0 < a < n, geldt:
  a^j(n) = 1 mod n

Bewijs: Voor gegeven (vaste) n kiezen we a uit de verzameling Z_n = {r₁, r₂,...r_m} van alle getallen tussen 0 en n die relatief priem zijn met n. Duidelijk is nu, dat het aantal elementen van Z_n gelijk is aan j(n) = m.
We bekijken nu het product van a en r_i (één van de getallen uit Z_n): a ^. r_i.
Omdat beide getallen relatief priem zijn met n, is ook a ^. r_i relatief priem met n. En omdat Z_n de verzameling is van alle getallen die relatief priem zijn met n, geldt dus, dat a ^. r_i (mod n) een element is van Z_n. Dus er is voor iedere i een j zodat a ^. r_i = r_j (mod n).
Er volgt nu:
ar₁ ^. ar₂ ^. ar₃ ^{. . .} ar_m = (r₁.r₂.r3 ^{. . .} r_m) mod n
oftewel
(a^m)*(r₁.r₂.r₃ ^{. . .} r_m) = (r₁.r₂.r₃ ... r_m) mod n
en
(a^m - 1) (r₁.r₂.r₃ . . . r_m) = 0 (mod n)
Aangezien het product r₁.r₂.r₃ ^. . . r_m relatief priem is ten opzichte van n, moet gelden
a^m - 1 = 0 (mod n)
en dus
a^m = 1 (mod n)
Door hierin j(n) = m te subsitueren volgt de stelling.
[einde bewijs]

Voorbeeld
Stel

> n := 17:
> a := 2:
> phi_n := phi(n);

phi_n := 16

Volgens de stelling van Euler geldt nu 2¹⁶ =1 (mod 17). En ook Maple geeft dit correct weer:

> rest:=a^phi_n mod n;

rest := 1

Het integer quotient van de deling van 2¹⁶ door 17 kunnen we vinden met de Maple-functie iquo:

> quot:=iquo(a^phi_n,n);

quot := 3855

En nu zien we

> quot*n+rest;

65536

5. Een laatste voorbeeld
In deze paragraaf staat een voorbeeld waarin het bericht M in blokken van 4 cijfers wordt gecodeerd.

> Message := `neem zsm contact met ons op`:
> M := to_number(Message);

M := 140505132726191327031514200103202713052027151419271516

De volgende gegevens, het aantal cijfers van M en het aantal blokken in M, en definities van de beide array's zijn nodig voor de codering van het bericht M.

> aantal_cijfers:=trunc(evalf(log10(M)))+1;

aantal_cijfers := 54

> aantal_groepen:=ceil(aantal_cijfers/4);

aantal_groepen := 14

> M_blok:=array(1..aantal_groepen);
> C_blok:=array(1..aantal_groepen);

M_blok := array(1 .. 14, [])
C_blok := array(1 .. 14, [])

Onderstaande gegevens zijn ontleend aan het voorbeeld op bladzijde 146 in Basismethoden Cryptografie.

> p := 47:
> q := 59:
> e := 17:
> n := p*q;
> phi_n := (p-1)*(q-1);

n := 2773
phi_n := 2668

> igcdex(e, phi_n, 'd', 'k');

1

> d := d mod phi_n;

d := 157

We splitsen de boodschap M nu van links naar rechts in groepen bestaande uit elk 4 cijfers (eventueel met uitzondering van de eerste (meest linkse) groep).
Het aantal groepen is hierboven berekend.
Elk blok bestaande uit vier cijfers vormt nu een getal dat wordt opgeslagen in het array M_blok.
De variabele s wordt in het onderstaande gebruikt om de groepen te berekenen.
De berekening van de groepen uit het getal s vindt echter plaats van rechts naar links.

> deler := 10^4;
> s := M;

deler := 10000
s := 140505132726191327031514200103202713052027151419271516

> for t from aantal_groepen by -1 to 1 do:
>   r := irem(s,deler);      # rest bij deling van s door de deler
>   s := iquo(s,deler);      # quotient bij deling van s door de deler
>   M_blok[t]:=r;
> od:
> eval(M_blok);

[14, 505, 1327, 2619, 1327, 315, 1420, 103, 2027, 1305, 2027, 1514, 1927, 1516]

Nu wordt elk element uit het array M_blok gecodeerd. De gecodeerde waarde wordt opgeslagen in het array C_blok (nu wel van links naar rechts).

> for t from 1 to aantal_groepen do
>   r:=M_blok[t];
>   C_blok[t]:=Power(r, e) mod n; # codering!
> od:
> eval(C_blok);

[2049, 2390, 1913, 1050, 1913, 677, 381, 850, 166, 813, 166, 2214, 1034, 477]

6. RSA-130
Het Centrum voor Wiskunde en Informatica (CWI) te Amsterdam heeft in 1996 (zie ook Naschrift) een nieuw wereldrecord getallenkraken gevestigd.
RSA-130, een getal van 130 cijfers is ontbonden in factoren: twee priemgetallen van elk 65 cijfers. Daarbij is gebruik gemaakt van een nieuwe methode (de Number Field Sieve) en de inschakeling van Internet bij het verzamelen van de benodigde gegevens.
RSA-130 is daardoor het tot nu toe (op het moment van schrijven) grootste getal waarvan bekend is dat het kan worden ontbonden in twee getallen die priem zijn.

We kunnen met Maple het getal RSA-130 in ieder geval ook berekenen (zie hierna).

Opmerking
De Maple-functie isprime(n) geeft de waarde true als het getal n een priemgetal is.
[einde opmerking]

> p := 45534498646735972188403686897274408864356301263205069600999044599:
> isprime(p);

true

> q := 39685999459597454290161126162883786067576449112810064832555157243:
> isprime(q);

true

> RSA_130 := p*q;

RSA_130 := 1807082088687404805951656164405905566278102516769401349\
17012702145005666254024404838734112759081230337178188796656318\
2013214880557

> AantalCijfers := trunc(evalf(log10(RSA_130)))+1;

AantalCijfers := 130

Op grond van het bovenstaande is het onverstandig op het getal RSA-130 de in Maple ingebouwde procedure ifactor los te laten! Met ifactor kunnen getallen worden ontbonden in hun priemfactoren, zoals met een eenvoudig voorbeeld kan worden gedemonstreerd:

> ifactor(6);

(2) (3)

Dat Maple met die procedure redelijk goed (en binnen een aanvaardbare tijdspanne) getallen kan ontbinden laten we hieronder zien. De berekeningen zijn uitgevoerd op een Compaq LTE 5100 met 16 Mb geheugen en een 90 MHz Pentium processor.

> a := 100!;      # 100! = 100.99.98...2.1

a := 9332621544394415268169923885626670049071596826438162146859296\
38952175999932299156089414639761565182862536979208272237582511\
85210916864000000000000000000000000

> AantalCijfers := trunc(evalf(log10(a)))+1;

AantalCijfers := 158

> ifactor(a);

(2)⁹⁷ (3)⁴⁸ (5)²⁴ (7)¹⁶ (11)⁹ (13)⁷ (17)⁵ (19)⁵ (23)⁴ (29)³ (31)³ (37)² (41)² (43)² *
(47)² (53) (59) (61) (67) (71) (73) (79) (83) (89) (97)

Bovenstaande ontbinding in factoren werd gevonden binnen 0,7 sec.

Een voorbeeld nu met twee redelijk grote priemgetallen.

> pp := nextprime(1234567890123456789012345678901);

pp := 1234567890123456789012345679099

> qq := nextprime(pp);

qq := 1234567890123456789012345679109

> nn := pp*qq;

nn := 1524157875323883675049535156757323577920560889904538942242791

> AantalCijfers:=trunc(evalf(log10(nn)))+1;

AantalCijfers := 61

> ifactor(nn);

(1234567890123456789012345679109) (1234567890123456789012345679099)

Deze ontbinding werd door Maple gevonden na 86,2 sec rekentijd.

Belangstellenden in cryptografie en in het bijzonder het kraken van van RSA-getallen worden verwezen naar de Internet web-site:
http://www.npac.syr.edu/factoring

7. Tot slot, een anecdote
Getallen van de vorm 2ⁿ - 1 worden Mersenne-getallen genoemd (Marin Mersenne, 1568-1648). In 1644 schreef Mersenne in het voorwoord bij zijn boek Cogitata Physico Mathematica, dat de enige waarden van p kleiner dan of gelijk aan 257 waarvoor 2^p -1 een priemgetal is, de volgende zijn:
1, 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257.
Mersenne-getallen worden in hetgeen volgt aangegeven met Mn = M(n) = 2ⁿ -1.
Mersenne heeft zich echter met zijn uitspraak in een tweetal opzichten vergist.
Ten eerste heeft hij niet alle waarden van p in zijn overzicht opgenomen, waarvan (nu) bekend is dat M(p) priem is.
Bijvoorbeeld:

> M89 := 2^89-1;

M89 := 618970019642690137449562111

> isprime(M89);

true

En in de tweede plaats leveren niet alle door hem genoemde waarden van p een Mersenne-getal op dat priem is.

> M67 := 2^67-1;

M67 := 147573952589676412927

> isprime(M67);

false

Maple levert deze waarde (false, dus ontbindbaar) binnen een fractie van een seconde, maar het heeft tot 1903 geduurd voordat de uitspraak van Mersenne met betrekking tot M(67) werd tegengesproken.
F.N. Cole, spreker op de jaarlijkse bijeenkomst van de American Mathematical Society in oktober 1903 in New York, hield zijn voordracht "On factorization of large numbers" als volgt.
Na door de voorzitter te zijn uitgenodigd om zijn voordracht te houden liep Cole -hij stond bekend als een man van weinig woorden- naar het bord waarop hij zwijgend de berekening van 2 tot de macht 67 opschreef. Van het antwoord trok hij zorgvuldig 1 af. Nog steeds zonder een woord te zeggen wandelde hij naar een leeg stuk van het bord en daar voerde hij de volgende vermenigvuldiging uit.

> 761838257287*193707721;

147573952589676412927

En inderdaad...
"De beide antwoorden waren gelijk... Cole ging weer zitten zonder dat hij een woord had gesproken. Niemand van de aanwezigen had iets te vragen", stond er in het verslag van E.T. Bell.
Bell vroeg later aan Cole hoe lang hij ervoor nodig had gehad om deze ontbinding te vinden. Cole antwoordde: "Drie jaar lang, elke zondag".

Maple berekent een en ander in ongeveer 4 seconden:

> ifactor(M67);

(761838257287) (193707721)

Overigens geldt:

> isprime(761838257287);
> isprime(193707721);

true
true

8. Naschrift
Moge dit artikel een uitdaging voor de lezer zijn zich (o.a.?) met Mersenne- en RSA-getallen bezig te (gaan) houden!

Dat RSA-getallen inderdaad een uitdaging vormen, moge blijken uit een persbericht van het CWI (Centrum voor Wiskunde en Informatica) te Amsterdam van 26 augustus 1999.
Daaruit blijkt, dat RSA-155 kan worden ontbonden (het teken \ is een regel-afbreekteken):

RSA-155 =
109417386415705274218097073220403576120037329454492059909138421314763499842889\
34784717997257891267332497625752899781833797076537244027146743531593354333897
=
102639592829741105772054196573991675900716567808038066803341933521790711307779
*
106603488380168454820927220360012878679207958575989291522270608237193062808643

Op 4 november 2005 werd door Prof. Dr. Jens Franke het volgende e-mailbericht verstuurd.
==========
To: ssw@cerias.purdue.edu, Paul.Zimmermann@loria.fr,
paul@leyland.vispa.com, scott_contini@yahoo.com, maro@isl.ntt.co.jp,
Peter-Lawrence.Montgomery@cwi.nl, Herman.te.Riele@cwi.nl,
A.K.Lenstra@tue.nl, BKaliski@rsasecurity.com
Reply-To: franke@math.uni-bonn.de
From: Jens Franke <franke@math.uni-bonn.de>
Date: Fri, 04 Nov 2005 16:53:08 +0100 X-UIDL: )oj!!_ha"!8[;!!Ie,#!

We have factored RSA640 by GNFS (general number field sieve). The factors are

16347336458092538484431338838650908598417836700330\
92312181110852389333100104508151212118167511579
and
19008712816648221131268515739354139754718967899685\
15493666638539088027103802104498957191261465571

We did lattice sieving for most special q between 28e7 and 77e7 using factor base bounds of 28e7 on the algebraic side and 15e7 on the rational side. The bounds for large primes were 2^34. This produced 166e7 relations. After removing duplicates 143e7 relations remained. A filter job produced a matrix with 36e6 rows and columns, having 74e8 non-zero entries. This was solved by Block-Lanczos.

Sieving has been done on 80 2.2 GHz Opteron CPUs and took 3 months. The matrix step was performed on a cluster of 80 2.2 GHz Opterons connected via a Gigabit network and took about 1.5 months.

Calendar time for the factorization (without polynomial selection) was 5 months.

More details will be given later.

F. Bahr, M. Boehm, J. Franke, T. Kleinjung
==========

Naschrift (dk)

RSA640 =
310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440\
5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482\
2783525742 3864540146 9173660247 7652346609

en verder

"Bei ihrem Rekord kooperierten die Wissenschaftler mit dem Centrum voor Wiskunde en Informatica (CWI) in den Niederlanden sowie dem Bundesamt für Sicherheit in der Informationstechnik (BSI)."

---

[rsa.htm] laatste wijziging op: 11-11-2005