Hoe moeilijk is het om de waarde van d te berekenen?
In 1977 schreef Martin Gardner het artikel "A new kind of cipher that would take millions of years to break". Gardner gaf zijn lezers een opgave om een cijfertekst te ontcijferen en loofde een beloning uit van $100 voor degenen die er als eerste in zou slagen. De tekst was vercijferd met volgens RSA-129. Dat wil zeggen dat n een getal was van 129 cijfers. Het zou tot 26 april 1994 duren voordat een groep van 600 vrijwilligers bekend maakte dat ze de ontbinding gevonden hadden:
RSA-129 =
114.381.625.757.888.867.669.235.779.976.146.612.010.218.296.721.242.362.562
561.842.935.706.935.245.733.897.830.597.123.563.958.705.058.989.075.147.599
290.026.879.543.541
= 3.490.529.510.847.650.949.147.849.619.903.898.133.417.764.638.493.387.843.990.820.577 *
32.769.132.993.266.709.549.961.988.190.834.461.413.177.642.967.992.942.539.798.288.533.
Sindsdien zijn er steeds nieuwe Challenges uitgeschreven en op 9 mei 2005 werd RSA-200 gekraakt. De RSA-factory schreef steeds nieuwe challenges uit met steeds groter wordende beloningen, maar is daar inmiddels mee gestopt omdat er steeds meer challenges onopgelost bleven en de lol er blijkbaar afging.
Hieronder is een internet-pagina opgenomen die over dit onderwerp handelt. Als je geïnteresseerd bent bevat het ook veel links waarmee je verder op zoek kunt, maar het voert te ver om hier nu uitgebreid bij stil te blijven staan.
Klik hier om naar de site te gaan.
In het boek van Simon Singh lezen we dat in 1995 door Simson Garfinkel werd berekend, dat als neen waarde zou hebben van een getal van 130 cijfers, een 100Mhz Intel Pentium-computer met 8 MB ram, een moderne computer voor die tijd, er 50 jaar voor nodig zou hebben om n te ontbinden inp*q. Honderd miljoen computers in een netwerk, wat gelijk stond aan het totale aantal verkochte computers in 1995, zouden n echter in 15 seconden kunnen ontbinden. Met het sneller worden van de computers en het groeien van het netwerk is het dus nodig om steeds grotere priemgetallen te gebruiken. Tegenwoordig worden priemgetallen van enkele honderden cijfers gebruikt om bijvoorbeeld banktransacties te beveiligen. Als de techniek voortschreidt en computers steeds sneller worden, dan zal het steeds sneller gaan om grote waarden van n te ontbinden, maar het werken met grotere waarden van p en q wordt dan ook steeds makkelijker en we weten dat er al priemgetallen zijn met meer dan 10 miljoen cijfers! Dat maakt RSA tot een hele veilige encrypiemethode.
Een techniek die Blinding heet vercijfert de tekst x vóórdat het de eenwegfunctie van de RSA-encryptie ingaat. Op die manier kunnen Alice en Bob gebruik maken van een instantie die RSA-vercijfering voor hen uitvoert. Het is immers goed denkbaar dat Alice en Bob zelf niet over de techniek en apparatuur beschikken om de tekst te vercijferen en ontcijferen.