Een mens moet wat doen hier bij Campuskrant

Een mens moet wat doen hier bij Campuskrant. Bijvoorbeeld: met een ernstig gezicht bij een burgerlijk ingenieur computerwetenschappen binnenschrijden en doodleuk beweren dat je een praatje komt maken over het wereldrecord puntentellen op een elliptische kromme, en of we meteen kunnen beginnen. Persoonlijk vinden wij een kromme al erg, maar als dat ook nog een elliptische moet zijn...

Frederik Vercauteren is het blijkbaar gewend over zijn discipline te praten met volstrekte beotiërs als yours truly. Hij is pas afgestudeerd in de computerwetenschappen, en werkt nu als FWO'er in ESAT, afdeling COSIC. Daarnaast studeert hij tweede licentie wiskunde. Hij vertelt geanimeerd over getallen met honderden cijfers, en wij hoorden beduusd toe.

"Wiskundigen houden van uitdagingen. Ik weet dat niet iedereen er van wakker ligt, maar wij houden ons onder andere bezig met het vinden van de punten die een elliptische kromme samenstellen. Een elliptische kromme is geen ellips, maar een verzameling oplossingen van een algebraïsche vergelijking met twee veranderlijken x en y, met x tot de derde macht en y in het kwadraat - bijvoorbeeld: y^2 + xy = x^3 + a."

Wereldrecord

"Het is behoorlijk moeilijk om het aantal punten op zo'n kromme te tellen. Die complexiteit neemt natuurlijk toe met de grootte van de parameters van je vergelijking. Met mijn eindwerk onder leiding van Prof. Marc Van Barel van het departement Computerwetenschappen heb ik me gewaagd aan een aanval op die complexiteit. Dat is verlopen in een schitterende sfeer: wiskunde en computerwetenschappen liggen trouwens heel dicht bij elkaar. Met het programma dat ik voor dat eindwerk onwikkeld heb, was ik in staat het aantal punten te bepalen op een kromme waarvan parameter a 1999 bits telt, zeg maar 1999 enen en nullen. Het aantal punten dat je dan krijgt, is tamelijk groot: het resultaat begint met 574063... en het eindigt met ...3770752. Het gaat om een getal van 602 cijfers. Dat betekent dat ik momenteel wereldrecordhouder ben. Het vorige was een curve van 1663 bits, op naam van een Franse wiskundige."

"Hoé complex zo'n berekening is? Wel, mijn programma heeft gedurende een week continu gedraaid op 10 snelle en onderling verbonden Pentiums, speciaal voor deze poging uitgebreid door het departement Computerwetenschappen. Als je de berekeningen door één computer zou willen laten doen, heeft die er ongeveer 65 dagen voor nodig."

"Ik begrijp dat je als buitenstaander bedenkingen hebt bij dergelijke bezigheden, maar er is méér dan alleen maar de kick van de indrukwekkende berekening. Maar elliptische krommen zijn eigenaardige dingen, die op heel onverwachte terreinen ingezet kunnen worden. Zo zijn ze essentieel gebleken om de stelling van Fermat eindelijk, na meer dan drie eeuwen, te kunnen bewijzen. Het bewijs zelf is een heel boek dik, maar zónder elliptische krommen was de stelling wellicht onbewezen gebleven. Verder, en dat is praktisch gezien heel belangrijk, kunnen elliptische krommen ingezet worden in de wereld van de cryptografie. Dat is de discipline die zich bezighoudt met het veiligheids- en betrouwbaarheidsaspect van informatie-overdracht. Als A informatie naar B stuurt, moet hij er zeker van zijn dat alleen B toegang heeft tot die informatie, en B moet er zeker van zijn dat de informatie alleen van A afkomstig kan zijn. Beiden moeten erop kunnen rekenen dat derden geen toegang hebben tot de informatie. Cryptografische methoden, concreet het encoderen en decoderen van informatie, zorgen ervoor dat dit kan."

"Cryptografie werkt met sleutels. Probleem is dat die sleutels niet alleen betrouwbaar moeten zijn, dus onkraakbaar, maar ook snel te verwerken. Als een derde toegang zou krijgen tot je vertrouwelijke computer-informatie, zou dat vervelend zijn. Maar als die veiligheid telkens pas na dagen rekenwerk verzekerd zou kunnen worden, zijn we evenmin waar we willen zijn."

"Een veel gebruikte methode is de RSA. Dat systeem werkt momenteel met sleutels van 1024 bits. Het probleem met RSA is dat de complexiteit van de sleutels moet toenemen naarmate de rekenkracht van computers vordert. De reden daarvoor is dat het algoritme dat aan RSA-versleuteling ten grondslag ligt, relatief eenvoudig is - wat niet wegneemt dat het nog altijd een hele portie hogere wiskunde vergt om RSA-gecodeerde informatie te kraken. De Wet van Moore zegt dat de rekenkracht van computers elke 18 maanden verdubbelt: dat betekent dat we in de relatief nabije toekomst met zodanig lange RSA-sleutels zullen zitten, dat de zaak onhanteerbaar wordt."

Krommen in de cryptografie

"Nu blijkt echter dat elliptische krommen schitterend gebruikt kunnen worden als basis voor een cryptografisch systeem. Hét voordeel is dat de betrouwbaarheid van een RSA-sleutel van 350 decimale cijfers ook gehaald wordt door een sleutel op basis van een elliptische kromme van maar 50 tot 60 cijfers. En dàt betekent dat je het cryptografisch proces sneller zou kunnen laten verlopen, met minder energie-verbruik. Dat laatste is relevant voor omgevingen met een beperkte verwerkingsruimte. Beveiliging op chipkaarten, bijvoorbeeld, verloopt nu al in hoofdzaak met systemen op basis van elliptische krommen."

"Ik zei 'zou kunnen', want een belangrijk nadeel van elliptische krommen is dat ze wiskundig zeer complex zijn. Het mooie van mijn programma is nu dat ik aangetoond heb dat het niet alleen mogelijk is heel vér te gaan - 1999 bits is niet niks - en tegelijk heel snel. Het vinden van een goede kromme op basis van parameters van 50 of 60 bits, zoals je die in de praktijk zou kunnen inzetten, duurde vroeger dagen tot weken. Met mijn programma duurt het enkele seconden. Dat brengt de inzetbaarheid van elliptische krommen in de cryptografische praktijk een heel eind dichterbij."

"Natuurlijk denken we aan een of andere vorm van commercialisering, maar we weten nog niet precies hoe. We zouden de executable van het programma kunnen verkopen, of we zouden door ons berekende krommen kunnen aanbieden, of we zouden zelfs, als stunt op het Internet, gratis curven kunnen aanbieden. De broncode van mijn programma verkopen? No way. Enfin, commercialisering is zeker niet mijn eerste zorg; trouwens de rechten behoren toe aan het departement Computerwetenschappen. Ik werk voor mijn doctoraat aan een nieuw algoritme, om systemen gebaseerd op elliptische krommen te breken. Zo'n algoritme groeit. Het is een kwestie van veel lezen, hard werken - en hopen op de vonk. Zonder die vonk kan je wel wat geleidelijke vooruitgang boeken, maar de échte doorbraak, toch de droom van elke wetenschapper, die dwing je niet af. Je zorgt alleen dat je er klaar voor bent..."

574065347637127262116416600588840992011158851044347600238821 368412883130696185156928329743158253134959222982319493731386 723559480431527665712965678083326592695649945726561400003443 895741200224357144634950317431223908077318231941819736585130 202331769854524982790811994044723148028116558247680821109851 648266130021482804215117281240652777636877032539303676212329 506225050275354360897048389816294790900159388810225730090007 882842743959402706162092986004358310842121244058298616451168 830123088478281383177609414270321938681141511810358750508596 91488342472463884539358839786434045186460955333873267133770752