Lamport-handtekening

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 Lamportsleutel 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

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

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 een 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

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

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

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

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

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

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

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 het bericht onderschept wordt kunnen alle 2^8 mogelijke paren in de privésleutel in 2^8 operaties worden doorlopen tot een match wordt gevonden met de publieke sleutel en men dus over de privésleutel beschikt. Daarom wordt in werkelijkheid een veel langere hashfuncties gebruikt met lengtes als 128-bit, 256-bit of zelfs 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 dezelfde 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

• Dit artikel of een eerdere versie ervan is een (gedeeltelijke) vertaling van het artikel Lamport signature op de Engelstalige Wikipedia, dat onder de licentie Creative Commons Naamsvermelding/Gelijk delen valt. Zie de bewerkingsgeschiedenis aldaar.