Lamport-handtekening

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een Lamport-handtekening is een methode in de cryptografie om een digitale handtekening te construeren, ontwikkeld door en genoemd naar Leslie Lamport. Hiermee kan de echtheid van een binnengekomen bestand gecontroleerd worden. Lamport handtekeningen zijn zeer moeilijk om te kraken, want elke Lamport Sleutel kan maar voor één bericht gebruikt worden. In combinatie met een hash-boom wordt deze methode veel efficiënter, omdat alleen de top van de hash-boom een sleutel nodig heeft. Dit maakt het mogelijk om meerdere berichten te sturen.

wiskundige beschrijving[bewerken]

Hier volgt een wiskundige beschrijving van hoe de handtekening werkt. Persoon A wil een gesigneerd bericht naar persoon B sturen. Persoon A maakt hiervoor twee sleutels aan, een privé sleutel en een publieke sleutel. Met deze twee sleutels kan ze een handtekening ontwikkelen die ze mee kan sturen met haar bericht. Het bericht dat A verstuurt wordt \ M genoemd.

De sleutels[bewerken]

Laat \ Y bitcodes zijn met een willekeurige lengte en \ Z bitcodes zijn van \ k-bit lang.

Laat f:\,Y\rightarrow Z een cryptografische hashfunctie (bijvoorbeeld MD5 of één van de SHA-familie) zijn waar een bitcode uit komt van \ k-bit lang.

Voor 1\leq i\leq k en j\in \{0,1\} kiest persoon A \ y_{i,j}\in Y willekeurig en berekent \ z_{i,j}=f(y_{i,j}).

De privé sleutel \ K bestaat uit \ 2k elementen \ y_{i,j}. De publieke sleutel bestaat ook uit \ 2k elementen \ z_{i,j}.

Het bericht signeren[bewerken]

A berekent \ f(M)= m en dat geeft haar m = m_1\ldots m_k \in\{0,1\}^k.

De handtekening van het bericht wordt sig(m_1\ldots m_k)=(y_{1,m_1},\ldots, y_{k,m_k})=(s_1,\ldots,s_k).

De handtekening controleren[bewerken]

Persoon B heeft dus (s_1,\ldots,s_k), \ M en alle \ z_{i,j}.

Hij kan de handtekening controleren door eerst \ f(M) = m te berekenen en daarna te checken of f(s_i) = z_{i,m_i} geldt voor alle 1\leq i\leq k.

voorbeeld[bewerken]

Persoon A wil dus een bericht sturen naar persoon B. In dit voorbeeld gebruikt ze een 8-bit cryptografische hashfunctie. Deze hashfunctie zet dus een bit-string van onbekende lengte om in een hashwaarde van 8 bits. Dit is enkel ter illustratie want in het echt worden er veel langere hashwaarden gebruikt. Beide personen kennen deze hashfunctie. Daarnaast heeft persoon A een random getallen generator.

De sleutels[bewerken]

Om de privé sleutel te maken gebruikt A eerst de nummergenerator om 8 paren van random getallen te maken. Deze moeten minstens 8-bit lang zijn. Dit maakt een totaal van 2 x 8 x 8 bits = 128-bit. Dit is dus A's privé sleutel en die slaat ze op om deze later te gebruiken.

De privé sleutel:

13 134

128 67

25 90

78 156

89 37

234 29

199 74

12 3

Voor de publieke sleutel berekent ze van al deze random getallen hun hashwaarde met behulp van de hashfunctie. Ze heeft nu dus 16 hashwaardes die alle 8-bit lang zijn. Dus weer een totaal van 128-bit. Dit is dus haar Publieke sleutel die ze gewoon kan opsturen.

De publieke sleutel:

00101010 10010101

01100111 11010101

00101110 11110111

00100101 11011101

11100001 00011000

11000110 11001110

11001101 11001001

11100011 11111101

Het bericht signeren[bewerken]

Persoon A wil nu de handtekening maken voor haar bericht. Het bericht dat A wil sturen is "Lamport". Eerst zet ze het bericht om in een hashwaarde van 8-bit. Dan gaat ze voor elke bit in de hashwaarde een nummer uit haar privé sleutel nemen. Als bijvoorbeeld de eerste bit een 0 is neemt ze het eerste getal uit het eerste paar uit haar sleutel. Is het eerste getal een 1 neemt ze het tweede getal van het eerste paar. Zo gaat ze door en dat geeft haar dus 8 getallen die in totaal 64-bit groot zijn. Deze 8 getallen zijn haar handtekening en stuurt ze mee met het bericht. De andere 8 getallen worden niet gebruikt.

De hashwaarde van "Lamport" is : 01011010.

De handtekening is: 13 67 25 156 37 234 74 12

De handtekening controleren[bewerken]

Persoon B krijgt dus een bericht binnen van persoon A maar wil eerste controleren of het echt van persoon A is. Hij heeft dus de publieke sleutel, de handtekening en het bericht binnengekregen. Hij zet ook het bericht om in een 8-bit hash waarde. Dan gebruikt hij de bits van de hashwaarde om 8 hashwaarden te pikken uit de publieke sleutel zoals persoon A dat heeft gedaan. Dus als de eerste bit een 0 is neemt hij de eerste hashwaarde van het eerste paar. Is de eerste bit een 1 dan pakt hij de tweede hashwaarde van het eerste paar.

Dit geeft hem dus 8 hashwaarden:

00101010

11010101

00101110

11011101

00011000

11000110

11001001

11100011

Daarna zet hij alle 8 getallen die als handtekening zijn gestuurd om in hashwaardes. Ook dit geeft het 8 hashwaardes en deze moeten gelijk zijn aan de 8 hashwaardes die hij uit Persoon A's publieke sleutel heeft gehaald. Is dit niet het geval is er dus iets mis.

De handtekening is: 13 67 25 156 37 234 74 12

De hashwaarden van de handtekening zijn:

00101010

11010101

00101110

11011101

00011000

11000110

11001001

11100011

Veiligheid[bewerken]

Niemand anders dan de verzender kan de juiste lijst met de random getallen voor de handtekening opstellen. Ze komen uit de privé sleutel die aan niemand bekend is en die pas is aangemaakt. Ook al is het bericht opgestuurd weet niemand anders de andere getallen. Ze staan als hashcodes in de publieke sleutel maar een van de eisen aan een hashfunctie is dat de originele waarden niet te achterhalen zijn.

In het voorbeeld is een 8-bit hashfunctie gebruikt. Als een hacker het bericht onderschept kan hij alle 2^8 mogelijke paren in de privé sleutel in 2^8 operaties doorlopen tot hij een match vindt met de publieke sleutel en hij dus over de privé sleutel beschikt. Daarom wordt in het echte leven een veel langere hashfuncties gebruikt zoals een 128-bit, 256-bit of zelfs een 512-bit.

De privésleutel mag maar één keer gebruikt worden en moet daarna vernietigd worden. Dit om de veiligheid van de handtekening hoog te houden. Stel dat iemand de zelfde privésleutel gebruikt om twee berichten te versturen. De hashwaarden van de twee berichten zullen naar waarschijnlijkheid 50% overeenkomen. Als beide berichten worden onderschept weet de hacker 75% van de privésleutel.

Referenties[bewerken]