Je leest:

De elliptische kromme in je telefoon

De elliptische kromme in je telefoon

Auteur:

In de zomer van 2005 verkocht Nokia zijn miljardste mobiele telefoon. De eerste werd in 1982 verkocht en woog ongeveer 15 kilo. Dat de technologie een grote stap voorwaarts heeft gemaakt, blijkt wel uit het feit dat de huidige telefoons slechts een paar honderd gram wegen.

In dit artikel lichten we een aspect van deze technologie eruit: de beveiliging van persoonsgegevens.

In iedere telefoon is een unieke identificatiecode ingebouwd. Als je iemand belt, dan wordt deze code verstuurd naar de telefoonaanbieder, bijvoorbeeld KPN of Vodafone. Zo kan de aanbieder zien naar wie hij de rekening voor het gesprek moet sturen. Het is van groot belang dat het versturen van de identificatiecode ‘veilig’ gebeurt. Als iemand deze code onderschept, dan kan hij voortaan op jouw kosten bellen!

We willen de identificatiecode eerst versleutelen voordat de telefoon hem verzendt naar de aanbieder. Er zijn veel manieren om informatie te versleutelen. In telefoons wordt tegenwoordig gebruik gemaakt van elliptische krommen. Een elliptische kromme is een wiskundig object dat speciale eigenschappen heeft die ons in staat stellen om snel en makkelijk informatie te versleutelen.

Mobiele telefoons waren er al in de jaren tachtig van de twintigste eeuw. Toen waren ze echter nog niet zo compact en licht als tegenwoordig! De grafiekjes zijn elliptische krommen. In elke mobiele telefoon zit een elliptische kromme, maar wel eentje die veel ingewikkelder is dan de krommen in het plaatje. Dankzij die elliptische kromme kan niemand anders op jouw kosten bellen.

Elliptische krommen

Er zijn vele manieren om te zeggen wat een elliptische kromme precies ‘is’. Een ‘goede’ definitie zou een diepgaand wiskundecollege vereisen. Voor ons is een elliptische kromme echter niets meer dan een vergelijking van de vorm y2 = x3 + ax + b. In deze vergelijking zijn x en y onbekenden, en a en b zijn bijvoorbeeld reële getallen. Als we a = –1 en b = 0 nemen, dan krijgen we een kromme waarvan de grafiek eruit ziet als in het linker plaatje in onderstaande afbeelding.

Links: de grafiek van y2 = x3 – x. Rechts: de som van twee punten op een kromme

We zien dat de kromme uit twee delen bestaat: een soort ellips aan de linkerkant en een kromme lijn aan de rechterkant. Van een hoger standpunt bezien is die kromme lijn eigenlijk ook een soort ellips, maar een van zijn punten kunnen we niet zien in dit plaatje. Oneindig hoog op de y-as ligt nog een punt, meestal O genaamd.

Een van de wonderlijke eigenschappen van een elliptische kromme is dat je twee punten op de kromme kunt ‘optellen’. In figuur 2 zie je nogmaals de kromme van figuur 1, maar nu hebben we ook twee punten P en Q op de kromme geprikt. Als we een rechte lijn door P en Q tekenen, dan zien we dat deze lijn de kromme in een uniek derde punt snijdt. Dit snijpunt spiegelen we in de x-as en het resulterende punt noemen we de som P + Q.

Dit is natuurlijk slechts een definitie van ‘P + Q’, maar er blijkt dat deze definitie een aantal mooie eigenschappen heeft. Als we bijvoorbeeld vanuit P een lijn naar O tekenen, dan moeten we wel een verticale lijn door P tekenen. Deze verticale lijn snijdt de kromme in een uniek punt. Om de som P + O te krijgen, moeten we dit punt nog spiegelen in de x-as. We zien dat P + O = P, ofwel: O is een soort ‘nul-element’ voor de optelling. Ook hebben we P + Q = Q + P: onze optelwet is symmetrisch in P en Q.

Wie van bovenstaand plaatje een kunstwerk wil maken, kan proberen te bewijzen dat ook (P + Q) + R = P + (Q + R) geldt. De eigenschappen van deze optelwet op een elliptische kromme doen sterk denken aan de optelling van natuurlijke getallen. Wiskundigen zeggen nu dat de punten op een elliptische krommen een (abelse) groep vormen.

Elektronisch stemmen

Elliptische krommen worden niet alleen gebruikt bij mobiele telefoons. Ook bij bijvoorbeeld internetbetalingen worden elliptische krommen gebruikt. Hier willen we namelijk ook informatie uitwisselen via een ‘onveilig medium’. Onlangs is in Denemarken een proef begonnen met elektronisch stemmen. Hier wil je niet alleen maar informatie veilig versturen, maar je wilt ook graag de informatie ‘ondertekenen’. Met een digitale handtekening kun je een uitgebrachte stem koppelen aan een persoon. Zo dwing je af dat het onmogelijk wordt dat iemand zich als jou voordoet om persoon X meer stemmen te geven. Elliptische krommen blijken bij uitstek geschikt om deze digitale handtekeningen te maken. Iedere inwoner van (een deel van) Denemarken krijgt een punt op een kromme thuisgestuurd dat hij vervolgens moet gebruiken bij het stemmen. Wellicht dat het in de brief van de Deense overheid geen punt op een elliptische kromme heet (niet iedereen heeft immers voldoende wiskundecolleges gevolgd…), maar het idee is hetzelfde. De proef in Denemarken was uiterst geslaagd en men verwacht dat elektronisch stemmen op grotere schaal ingevoerd gaat worden. Een groot voordeel van elektronisch stemmen is natuurlijk dat er niets meer mis kan gaan bij het tellen van de stemmen. Ook is de einduitslag van de verkiezingen direct bekend. De soap van zes jaar geleden in Florida had hiermee voorkomen kunnen worden! Hadden ze in de VS meer kennis gehad van elliptische krommen, dan had de wereld er wellicht heel anders uitgezien.

Terug naar versleuteling

Iedere mobiele telefoon bevat tegenwoordig een elliptische kromme en een punt P op deze kromme. Concreet betekent dit dat er een paar getallen in een chip gebrand zijn. Deze kromme en het punt P zijn niet geheim: de hele wereld mag ze weten. De telefoon kiest nu een willekeurig geheel getal t en berekent het punt tP. Met tP bedoelen we het punt dat we krijgen als we t keer het punt P bij zichzelf optellen (optellen in de zin van de vorige paragraaf!). De telefoon verstuurt nu tP naar de telefoonaanbieder en houdt t strikt geheim.

KPN (of een andere aanbieder) weet ook welke kromme en welk punt er in de telefoon geprogrammeerd zijn. Ze kiezen een willekeurig geheel getal u. KPN berekent nu het punt uP en stuurt dat terug naar de telefoon. De telefoon weet nu zijn eigen geheime getal t, maar ook het punt uP. Ergo: hij kan het punt (tu)P berekenen. KPN weet zijn eigen geheime getal u, maar ook het punt tP. Ook zij kunnen dus (ut)P = (tu)P uitrekenen. Merk op dat de telefoon niet zijn geheime getal t aan KPN hoeft te sturen, evenmin als KPN zijn geheime getal u aan de telefoon stuurt.

Zowel de telefoon als KPN weet nu het punt (tu)P. Zo’n punt bestaat uit een x- en een y-coördinaat. Als we nu de x-coördinaat optellen (gewoon als getal) bij de identificatiecode, dan krijgen we iets dat er voor de buitenwereld als een random getal uitziet. Dit getal wordt door de telefoon verstuurd. KPN krijgt dit binnen en trekt de x-coördinaat van (tu)P er weer vanaf om de identificatiecode te krijgen. Zo weet KPN welke telefoon er gebeld heeft en dus naar wie de rekening verstuurd moet worden.

Is dit veilig?

Wanneer is bovenstaande algoritme ‘veilig’? Ofwel: wat gebeurt er als iemand het dataverkeer tussen telefoon en aanbieder onderschept? Kan hij dan de identificatiecode alsnog achterhalen? De enige situatie waarin hij dit zou kunnen doen, is als ook hij het punt (tu)P weet.

Degene die een bericht onderschept, weet een boel: hij weet de elliptische kromme, het punt P en de punten tP en uP. Om (tu)P uit te rekenen, zal hij echter ofwel het geheime getal t ofwel het geheime getal u moeten achterhalen. Het blijkt dat dit voor geschikte elliptische krommen erg moeilijk is. ‘Moeilijk’ betekent hier dat alle wiskundigen ter wereld de afgelopen twintig jaar nog geen snelle manier hebben gevonden om dit te doen. De tijd die een aanvaller nodig zou hebben, zou met gemak meer kunnen zijn dan de leeftijd van het heelal. Lichtelijk onpraktisch dus. Dit betekent echter niet dat het probleem om t of u te achterhalen volgende week ook nog ‘moeilijk’ is. Dat nog niemand iets slims bedacht heeft, betekent niet dat er niet iemand uit Zimbabwe op zou kunnen staan die uitlegt hoe het simpel kan. In zekere zin berust de veiligheid van dit systeem op de onkunde van wiskundigen!

De ene elliptische kromme is geschikter dan de andere. De kromme uit dit artikel zou ik niemand willen aanraden die zelf zijn eigen telefoon wil bouwen. Deze kromme is volstrekt niet veilig, dus je kunt hoge telefoonrekeningen verwachten. De truc is voor de coëfficiënten a en b in de vergelijking geen reële getallen, maar getallen ‘modulo p’ te nemen. Hier is p een priemgetal van ongeveer 200 cijfers. Een getal modulo p bekijken is niets anders dan de rest te nemen bij deling door p. Zo is 17 gelijk aan 2 modulo 5. Getallen modulo p kun je net als natuurlijke getallen optellen en vermenigvuldigen. Als je een elliptische kromme modulo p neemt, dan krijg je in het algemeen een veilig systeem om de identificatiecode te versturen.

Dit artikel is een publicatie van Pythagoras (KWG).
© Pythagoras (KWG), alle rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 08 november 2007

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

LEES EN DRAAG BIJ AAN DE DISCUSSIE