Samenvatting deel 2

Met de komst van het ARPANET in 1969, uitmondend in het internet in 1982, werd het berichtenverkeer steeds drukker, nam de behoefte aan veilige communicatie steeds verder toe en werd het sleuteldistributieprobleem steeds groter.

Hellman was de eerste die een oplossing voor het probleem vond en werkte het samen met Diffie en Merkle uit. In juni 1976 presenteerden ze hun oplossing aan de buitenwereld, waarbij ze gebruik maakten van de modulo-functie en de exponentiële functie. Het berekenen van een macht modulo m met grote exponent is redelijk eenvoudig te berekenen voor Alice en Bob, terwijl het voor Eve ondoenlijk is de berekening terug te draaien. Daarmee is een zogenaamde eenwegfunctie gecreëerd, een functie die niet omkeerbaar is. Alice en Bob kunnen hiermee openlijk een geheim getal afspreken waarmee een symmetrische sleutel gemaakt kan worden voor verdere vercijfering zonder dat iemand het na kan rekenen. Hiernee is het sleuteldistributie systeem opgelost.

Het Man in the Middle probleem laat zien hoe Eve in de communicatie tussen Alice en Bob kan inbreken. Ze doet zich voor als Bob als ze tegen Alice praat en als Alice als ze tegen Bob praat, zonder dat Alice en Bob daar iets van merken.

In 1975 lanceerde Diffie het idee van een asymmetrische sleutel. Dat wil zeggen dat sleutel {a,n} gebruikt wordt voor encryptie en sleutel {b,n} voor decryptie. Sleutel {a,n} zou je op je visitekaartje kunnen zetten zodat iedereen jou een bericht kan sturen versleuteld met sleutel {a,n}. Alleen jij kunt de berichten ontsleutelen met de geheime sleutel {b,n}. Voorwaarde is, dat het niet mogelijk mag zijn om

  1. met alleen kennis van de publieke sleutel {a,n}, sleutel {b,n} af te leiden en
  2. om sleutel {a,n} te breken

Daarom is het nodig dat sleutel {a,n} zelf een eenwegfunctie is.

 

Les 11, 12 en 13 laten zien hoe je volgens het uitgebreide algoritme van Euclides een asymmetrische sleutel kunt maken.Volgens de stelling van Bachet-Bézout is er, als a en m onderling priemdelers zijn, een b zodat
a∙b = 1 (mod m). Voor iedere geldt dan dat a∙x mod m = y en dat b∙y mod m = b∙a∙x mod m = x. Hierbij is xde klare tekst en y de cijfertekst.

 

Om het algoritme van Euclides te kunnen hanteren moet je eerst weten wat priemdelers zijn en wat de Grootste Gemene Deler is. Verder moet je kunnen rekenen met
- de gehele deling a div m en 
- de modulusfunctie a mod m
In les 12 heb je geleerd hoe Excel daarbij een handige tool kan zijn.

In les 13 is het algoritme van Euclides uitgebreid om de inverse sleutel {b,m} te vinden, waarmee de vercijferde code kan worden ontsleuteld. Het algoritme stelt je in staat om voor twee getallen a en m met a < m eenvoudig het getal bte vinden, 
waarbij a∙b=1 mod m.

Het doel om een asymmetrisch systeem te maken is hiermee nog niet direct bereikt omdat iedereen in principe in staat is met a en m de inverse b te berekenen.

Het duurde tot april 1977 tot Rivest, Shamir en Adleman een asymmetrische sleutel vonden die wel aan voorwaarden 1. en 2. voldeed. Ze maakten daarbij gebruik van twee zeer grote priemgetallen p en q. Je moet hierbij denken aan priemgetallen van 150 cijfers of meer.Het product p∙q is de modulus n bij de vercijfering. Verder gebruiken ze de Eulerfunctie φ(x); deze berekent het aantal priemdelers van x.

Het RSA algoritme zegt nu:

Kies twee grote priemgetallen p en q.
Bereken  p∙q=n
Bereken φ(n)=(p-1)∙(q-1)
Kies een getal e relatief priem ten opzichte van φ(n).
Bereken de inverse van e mod φ(n) volgens het algoritme van Euclides.
Vercijfer de code x volgens xe mod n = y.
Ontcijfer de code y volgens yd mod n = x.
Blijkbaar geldt xed mod n = x 
{e,n} heet de publieke sleutel en wordt aan ieder die het weten wil bekendgemaakt.
{b,n} heet de privé sleutel en blijft een goed bewaard geheim.

 

De juistheid van de stelling wordt aangetoond voor 0<x<min{p,q} in de subpagina Euler en Fermat. De kracht van het algoritme is, dat Alice eenvoudig φ(n) kan berekenen volgens φ(n)=(p-1)(q-1). Voor Eve is het niet mogelijk om de inverse d te vinden zonder dat ze weet wat p en q zijn. De enige manier om daar toch achter te komen is door n te ontbinden in factoren. Hoe groter de priemgetallen, hoe moeilijker dat wordt en bij de genoemde waarden van p en q is dat zelfs onmogelijk. Het probleem waarvoor Eve zich gesteld ziet, heet het factorisatieprobleem.

Alice kan tonen dat het bericht echt van haar afkomstig is door het begin van het bericht te coderen met haar eigen Privé sleutel. Bob kan met de Publieke sleutel van Alice het berichtje ontcijferen en daaraan zien dat het bericht echt van Alice komt. Daarmee is het Man in the Middle probleem ook opgelost.