Help:Veelgestelde vragen: verschil tussen versies
Verwijderde inhoud Toegevoegde inhoud
Geen bewerkingssamenvatting |
|||
Regel 1:
{{Helpmenu}}
13. RSA
RSA is een encryptiesysteem gebaseerd op openbare sleutels, een publieke sleutel en een persoonlijke en geheime sleutel. Maar toch geven we je even een korte herhaling: De publieke sleutel is dus niet geheim en wordt gebruikt om berichten te coderen, iedereen kan dit doen, deze sleutel kun je alleen niet gebruiken om het bericht te ontcijferen, daarvoor is de geheime sleutel nodig, die alleen de ontvanger heef. Dit is dus de basis achter systemen met openbare sleutels.
De basis van RSA heeft twee persoonlijke en geheime priemgetallen, P en Q. We kiezen de getallen P=13 en Q=23. Nu vermenigvuldigen we dit en krijgen we een waarde N, in ons geval is dat 299.
En nu het moeilijke gedeelte. Straks we gaan een speciaal algoritme op deze N loslaten, dit algoritme is gebaseerd op de stelling van Euler. Deze stelling in functievorm , stelt dat (Spreek uit "fie") aanduid hoeveel getallen er zijn die geen enkele factor met X gemeen hebben. Hierbij worden alleen de getallen geteld die kleiner zijn dan X en de factor 1 wordt vanzelfsprekend niet meegeteld, anders zouden immers alle getallen een factor met X gemeen hebben. Dat is dus de definitie van de stelling van Euler. Ook dit kan net zoals de stelling van Fermat worden gebruikt om te kijken of een bepaald getal een priemgetal is, als X immers een priemgetal is dan zal geen enkel getal een factor gemeen hebben en zal het aantal getallen kleiner dan X die geen factor (boven de 1) met X gemeen hebben X - 1 bedragen. Anders gezegd, als X een priemgetal is dan heeft de waarde X - 1.
Wellicht een beetje vaag, laten we eens eens een voorbeeld nemen en van 10 nemen. Dit wil zeggen dat we gaan uitzoeken hoeveel getallen er zijn die geen enkele factor gemeen hebben met het getal 10 (dat geen priemgetal is). Anders gezegd, we tellen hoeveel getallen er zijn die niet te delen zijn door een getal waarmee 10 te delen is. Dit ziet er misschien een beetje moeilijk uit maar het volgende voorbeeld zal een hoop duidelijk maken: We willen de van 10, laten we alle getallen opschrijven die kleiner zijn dan 10:
1 2 3 4 5 6 7 8 9 10
Het getal 10 is deelbaar door 5, we gaan alle getallen weghalen die ook deelbaar zijn door 5, die dus de factor 5 gemeen hebben met 10. In dit geval is dit alleen het getal vijf zelf. Dit getal heeft een factor gemeen en verwijderen we uit onze lijst:
1 2 3 4 6 7 8 9
Het getal 10 is ook deelbaar door 2, we halen dus alle getallen weg die ook deelbaar zijn door 2. De getallen die verdwijnen hebben dus de factor 2 met 10 gemeen, Er blijft nu over:
1 3 7 9
Er zijn geen andere getallen waardoor 10 te delen is, we zijn dus klaar!
De overgebleven getallen hebben dus geen factor gemeen met 10. Er zijn dus 4 getallen die geen factor gemeen hebben met het getal 10, namelijk: 1, 3, 7 en 9. We kunnen dus zeggen dat de van 10 het getal 4 is. Het uitrekenen van de van een priemgetal is zoals al eerder vermeld veel makkelijk te berekenen, als X een priemgetal is dan geld altijd het volgende: = X - 1. En dit is dus ook een manier om te testen of een getal een priemgetal is of niet.
Voor het uitrekenen van de waarde van een niet-priemgetal X is het NIET mogelijk een formule op te stellen en is het gewoon een kwestie van tellen. Er is echter een uitzondering, als een getal het product is van twee priemgetallen dan is het weer wel mogelijk een formule op te stellen, er geldt dan namelijk = (P - 1)(Q - 1) waarin P en Q priemgetallen zijn.
LET OP! Deze formule geldt dus alleen voor een getal dat het product is van twee priemgetallen. Waarvoor we deze getallen nodig hebben leggen we straks uit.
Omdat het berekenen van de Eulerphi van niet priemgetallen veel werk is, hebben we een programma geschreven dat dit voor je doet.
Laten we weer eens terugkeren naar RSA, we hadden twee persoonlijke en geheime priemgetallen P en Q, waaraan we respectievelijk de waarden 13 en 23 hadden gegeven. Deze hadden we met elkaar vermenigvuldigd en dat leverde N op (299 in ons geval). N een getal dat niet geheim is en is deel van de openbare sleutel. Nu gaan we weer een stapje verder. We gaan de stelling van Euler loslaten op deze N. We bereken dus , en aangezien N een produkt is van twee priemgetallen, 13 en 23, kunnen we de volgende formule gebruiken: = (P - 1)(Q - 1) = (13 - 1)(23 - 1) = 12 x 22 = 264.
Vervolgens kiezen we een willekeurig getal E. Dit getal mag echter geen factor gemeen hebben met de van N. Het controleren of het getal E geen factor met gemeen heeft is bij grote getallen nogal een lastig karwei. Daarom hebben we een computerprogramma geschreven die ervoor zorgt dat de computer een getal E uitzoekt zonder dat het een factor gemeen heeft met de van N. Dit scheelt een hoop werk, gezien het feit dat de computer dit vele malen sneller kan dan wij.
Het uitrekenen van was niet zo heel moeilijk, omdat dit priemgetallen waren. Het volgende wat we moeten doen is echter een heel stuk moeilijker. We moeten nu nogmaals door de functie halen. We moeten dus uitzoeken hoeveel getallen er zijn die geen factor gemeen hebben met de van N. Omdat N geen priemgetal is, is dit nog vrij ingewikkeld. Gelukkig hebben we hiervoor dat programma geschreven, dus de computer kan dit mooi voor ons uitrekenen. We berekenen dus .
Met de gegevens die we nu hebben kunnen we de geheime sleutel uitrekenen die gebruikt wordt om boodschappen te decoderen. Dit gebeurd met de volgende formule:
geheimesleutel = E - 1mod
We hebben nu het getal dat nodig is om een tekst te ontcijferen. Dit is de geheime sleutel en dat maken we NIET openbaar bekend. Dat doen we alleen met de getallen N en E, die samen deel uitmaken van de openbare sleutel. We maken de priemgetallen P en Q ook niet bekend.
De persoon die de openbare sleutel heeft, de getallen N en E dus, kan ons een gecodeerd bericht sturen. Dat doet hij met de volgende formule:
Gecodeerdeboodschap = BoodschapE mod N
En met de volgende formule kunnen we de boodschap weer ontcijferen:
Boodschap = Gecodeerdeboodschapgeheimesleutel mod n
Met deze gegevens kunnen we dus een bericht coderen en ook weer decoderen. We zullen een voorbeeld geven van het hele proces. Eerst kiezen we twee priemgetallen P en Q. In ons voorbeeld gebruiken we hiervoor de getallen 13 en 23, maar in werkelijkheid gebruik je priemgetallen die vele malen groter zijn om het systeem veiliger te maken.
We vermenigvuldigen deze twee getallen en krijgen zo het getal N, dat deel is van de openbare sleutel. Dus 13 x 23 = 299. N is dus 299. Wat we nu moeten doen is de nemen. Dit kan met behulp van de formule = (P - 1)(Q - 1) omdat het een produkt is van twee priemgetallen.
Dus = (13 - 1)x(23 - 1) = 264.
We kiezen nu een willekeurig getal E dat geen factoren gemeen heeft met , dus met 264. Hiervoor kunnen we het computerprogramma gebruiken dat we hebben gemaakt, en dan vinden we zo bijvoorbeeld het getal 5 dat geen enkele factor gemeen heeft met 264. Nu moeten we berekenen hoeveel getallen er zijn die geen factor gemeen hebben met 264, dus met de . Dit is dus . Om dit uit te rekenen gebruiken we weer het computerprogramma. Hieruit vinden we dat het getal 80 is. Er zijn dus 80 getallen die geen factor gemeen hebben met , oftewel 264.
We kunnen nu de geheime sleutel uit gaan rekenen. We weten de formule hiervoor:
geheimesleutel = E - 1mod
We beschikken over alle benodigde variabelen dus we kunnen deze formule gaan invullen:
geheimesleutel = 580 - 1 mod 264 = 53.
Onze geheime sleutel is dus het getal 53.
Dan gaan we eens kijken naar de openbare sleutel, die bestaat uit de getallen N en E, dus 299 en 5. Een persoon die de deze getallen N en E heeft kan ons dus een bericht sturen. Dit met behulp van de volgende formule:
gecodeerdeboodschap = boodschape mod n
Laten we zeggen dat de boodschap al omgezet is in cijfers en het getal 150 vormt. We vinden nu 1505 mod 299. En dit is het getal 271, dit is dus de gecodeerde versie van 150, deze gecodeerde waarde 271 gaat naar persoon B, samen met de openbare sleutel, de variabelen N en E dus.
Willen we deze boodschap weer ontcijferen, dan gaat dit alleen maar als je de openbare sleutel hebt. Anders is deze opgave bijna niet te doen omdat dat eeuwen zou kosten. Laten we de gecodeerde boodschap 271 dus eens ontcijferen met behulp van de openbare sleutel bestaande uit N=299 en E=5. We weten de formule:
gecodeerdeboodschapgeheimesleutel mod n = boodschap
Als we dit invullen vinden we:
27153 mod 299 = 150
En wonder boven wonder komt hier weer het getal 150 uit. We hebben de boodschap dus weer ontcijferd!
We hebben in ons voorbeeld voor het gemak gebruik gemaakt van maar kleine getallen. In het echt worden dus vele grotere getallen gebruikt zoals we al verteld hebben. We hebben echter zo geprobeerd om het iets duidelijker te maken. Probeer het zelf ook eens, en het is natuurlijk het beste om het met z'n tweeen te proberen!
| |||