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, maar elke Lamport Sleutel kan maar voor één bericht gebruikt worden. In combinatie met een hash-boom wordt deze methode veel efficienter want alleen de top van de hash-boom heeft een sleutel nodig. Zo is het toch mogelijk om meerdere berichten te sturen.

wiskundige beschrijving[bewerken | brontekst 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 prive 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 verstuurd wordt $\ M$ genoemd.

De sleutels[bewerken | brontekst 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 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 prive sleutel $\ K$ bestaat uit $\ 2k$ elementen $\ y_{i,j}$ . De publieke sleutel bestaat ook uit $\ 2k$ elementen $\ z_{i,j}$ .

Het bericht signeren[bewerken | brontekst 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 | brontekst 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}}$ geld voor alle $1\leq i\leq k$ .

voorbeeld[bewerken | brontekst bewerken]

Persoon A wil dus een bericht sturen naar persoon B. In dit voorbeeld gebruikt ze een 8-bit hashfunctie. 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. Het bericht wat A wil sturen is; "Lamport".

De sleutels[bewerken | brontekst bewerken]

Om de prive sleutel te maken gebruikt A eerst de nummer generator om 8 paren van random getallen te maken, die allemaal 8-bit lang zijn. Dit maakt een totaal van 2X8X8 bits = 128-bit. Dit is dus A's prive sleutel en die slaat ze op om deze later te gebruiken.

De prive 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 hash waarde 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 op kan sturen.

De publieke sleutel:

00101010 10010101

01100111 11010101

00101110 11110111

00100101 11011101

11100001 00011000

11000110 11001110

11001101 11001001

11100011 11111101

Het bericht signeren[bewerken | brontekst bewerken]

Persoon A wil nu de handtekening maken voor haar bericht. 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 prive 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 random getallen dat in totaal 64-bit groot is. Deze 8 random getallen is 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 | brontekst 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 binnen gekregen. 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 het 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 hashwaarde:

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 is:

00101010

11010101

00101110

11011101

00011000

11000110

11001001

11100011

Veiligheid[bewerken | brontekst bewerken]

Niemand anders dan de verzender kan de juiste lijst met de random getallen voor de handtekening opstellen. Ze komen uit de prive 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 origenele waarden niet te achterhalen zijn.

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

De prive 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 prive sleutel gebruikt om 2 berichten te versturen. De hashwaarden van de twee berichten zullen naar waarschijnlijkheid 50 % overeen komen. Als beide berichten worden onderschept weet de hacker 75 % van de prive sleutel.

Referenties[bewerken | brontekst bewerken]

World Lingo: De handtekening van Lamport

[[Categorie:Cryptografie]]

hash-tree[bewerken | brontekst bewerken]

Een hash-boom (Engels: hash tree) is een boom die kan worden gebruikt om data veilig tussen twee computers te sturen. Ze worden op het moment vooral gebruikt om te checken of alle data is aangekomen en of de data onbeschadigd is. De hash-boom is uitgevonden door Ralph Merkle in 1979 en daarom worden Hash bomen ook wel Merkle-bomen genoemd.

Opbouw[bewerken | brontekst bewerken]

Een hash-boom is vaak een binaire boom. Dit houdt in dat elke parent node twee child nodes heeft. Het is wel mogelijk om een hash tree te maken met meerdere child nodes. Om een hash tree te maken beginnen we onderaan, bij de bladeren van de boom. We hakken het bericht $\ M$ in stukken $\ {m_{1},m_{2},...,m_{n}}$ en elk stuk zetten we om in een hashwaarde met behulp van een Hashfunctie $\ H$ . Elk blaadje $\ v_{1,j}$ krijgt dus de hash waarde $\ H(m_{j})$ . De parent nodes $\ v_{i,j}$ kunnen we bepalen door de hashwaarde van de twee childs $\ v_{i-1,j*2-1}$ en $\ v_{i-1,j*2}$ om te zetten in een nieuwe hashwaarde $\ H(v_{i-1,j*2-1}||v_{i-1,j*2})$ . Zo wordt de hele boom opgebouwd tot de top $\ v_{d,1}$ . Deze top node is de belangrijkste node van de boom en wordt opgestuurd door een betrouwbare bron. De ontvanger kan beginnen met downloaden van de datablocks nadat hij deze top binnen heeft gekregen. Zodra de hele boom is gedownload kan er gecheckt worden of de data klopt. De ingekomen datablokken worden omgezet in hashwaarden en de hele boom wordt opgezet. Als een datablok niet klopt krijgt deze een andere hashwaarden dan de juiste datablock. Zo krijgen de parents van deze child ook andere hashwaarden en zal dus de top van de boom niet overeen komen met de top die opgestuurd is. De boom is dus onjuist en moet opnieuw gedownload worden.

Toepassingen[bewerken | brontekst bewerken]

Hash bomen zijn vooral toe te passen in peer-to-peer-netwerken. Een betrouwbare bron berekent de hele tree en stuurt de top op. De rest van de datablokken kan van elke bron vandaan komen. Met behulp van de hashfunctie kan er dan bepaald worden of alle data is aangekomen en of er geen fouten inzitten of dat er iemand veranderingen heeft aangebracht.

De originele doel van Hash trees was om het mogelijk te maken om efficiënt om te gaan met Lamport one-time signatures. Lamport Signiture zijn zeer moeilijk te kraken, maar elke Lamport Key kan maar voor één bericht gebruikt worden. In combinatie met hash trees kunnen ze ineens wel voor meerdere berichten gebruikt worden waardoor Lamport Signitures veel efficiënter worden. Alleen de top heeft namelijk een handtekening nodig.

Voorbeeld[bewerken | brontekst bewerken]

Gezien een voorbeeld vaak duidelijker is dan een lap tekst volgt hier een voorbeeld van de hash-boom. Persoon A wil graag het bericht "Dit is een hash boom" downloaden binnen een netwerk. Persoon B krijgt deze vraag binnen en begint de boom op te stellen. Hij begint met het in stukken hakken van het bericht. Dit levert hem 5 stukjes op. Hij gebruikt een 8-bit hashfunctie. Dit is enkel ter illustratie, want in het echt worden er veel langere hashfuncties gebruikt. Hij zet elk stukje van het bericht om een hashwaarden en heeft dus nu de bladeren van de boom gemaakt.

De volgende stap is de hashwaarden van elke parent node te berekenen door de twee hashwaarden de van childnodes samen te nemen en om te zetten in een nieuwe hashwaarde. Hiermee gaat hij door tot hij de top node heeft bereikt. Deze node stuurd hij op naar persoon A.

Persoon A krijgt dus de top node binnen van persoon B. Hij kun nu beginnen met downloaden van het bericht. Alle stukjes komen van verschillende personen vandaan. Zodra alles binnen is begint hij de boom op te bouwen zoals persoon B dat had gedaan. Dus eerste alle stukjes van het bericht omzetten in hashwaarden en daarmee de parentnodes te bepalen. De top node die hij zo krijgt vergelijkt hij met de hashwaarde van de top node dat hij van persoon B binnnen heeft gekregen. Als alles goed is binnen gekomen moeten deze hashwaarden dus gelijk aan elkaar zijn. Is dit niet het geval dan is er iets mis met de binnengekomen stukjes.

Referenties[bewerken | brontekst bewerken]

[[Categorie:Boom (datastructuur)]]