Hashfuncties zijn alomtegenwoordig in de hedendaagse cryptografie. De Amerikaanse crytografiedeskundige Bruce Schneier1 noemt ze niet voor niets de "werkpaarden van de moderne cryptografie". Ze worden onder andere gebruikt in digitale handtekeningen, bij het versleutelen van berichten, als vingerafdrukken om dubbels te detecteren en als controlemechanisme om foutieve gegevens te detecteren.
Peter Pearson ontwikkelde een snelle en eenvoudige hashfunctie die werkt met een permutatietabel $$T$$ van de natuurlijke getallen tussen 0 (inbegrepen) en 256 (niet inbegrepen). We noteren het $$i$$-de getal in de tabel als $$T_i$$ ($$i = 0, 1, \ldots, 255$$). Bij Pearson hashing wordt de hashwaarde van een string $$s$$ als volgt berekend:
-
initiële hashwaarde: $$h \leftarrow 0$$
-
voor elk karakter $$s_i$$ van de string $$s$$ ($$i = 0, 1, \ldots, |s| - 1$$)
-
$$v \leftarrow \text{ord}(s_i)$$
-
$$h \leftarrow (h + v)\ \text{mod}\ 256$$
-
$$h \leftarrow T_h$$
In stap (2a) wordt de ingebouwde functie ord gebruikt om de integerwaarde van een karakter te bepalen. In sommige implementaties — waaronder de originele implementatie van Pearson zelf — worden de twee waarden in stap (2b) gecombineerd met XOR ($$h \leftarrow (h\ \text{XOR}\ v)\ \text{mod}\ 256$$) in plaats ze op te tellen. Het resultaat blijft altijd een hashwaarde tussen 0 (inbegrepen) en 256 (niet inbegrepen).
Pearson hashing is niet geschikt voor het versleutelen van berichten, maar wordt wel gebruikt voor niet-cryptografische doeleinden zoals het opbouwen van een blockchain — het algoritme achter Bitcoin2 en andere cryptovaluta3.
Een blockchain is een voor het publiek leesbare databank waarin gegevens in blokken opgeslagen worden in een onveranderlijke en controleerbare keten. Er kunnen slechts twee bewerkingen uitgevoerd worden op de databank:
-
toevoegen (adjoin): toevoegen van een nieuw datum (gegevensitem) aan de databank
-
valideren (validate): controleren of de databank volledig en ongeschonden is
Er is geen bewerking om gegevens te wissen. Van zodra een datum aan de databank wordt toegevoegd, kan deze nooit meer verwijderd worden. Er is geen bewerking om gegevens te wijzigen. Van zodra een datum aan de databank wordt toegevoegd, kan deze nooit meer gewijzigd worden. Er is geen bewerking om gegevens te sorteren. Van zodra een datum aan de databank wordt toegevoegd, kan deze nooit binnen de keten verplaatst worden.
Elk blok in de keten heeft vier eigenschappen:
-
index (int): start bij nul en wordt telkens met één verhoogd als er een nieuw blok aan de keten toegevoegd wordt
-
datum (str): willekeurige string met gegevens
-
hash (int): hashwaarde van het blok (zie verder)
-
vorige_hash (int): hashwaarde van het vorige blok in de keten
Het eerste blok van een blockchain wordt het genesisblok genoemd. Per definitie heeft dit blok index 0, datum Genesis Block en vorige hashwaarde 0. Het genesisblok bepaalt ook welke hashfunctie gebruikt wordt voor het opbouwen van de blockchain (bijvoorbeeld Pearson hashing). De hashwaarde van een blok wordt berekend als de hashwaarde van de string die bestaat uit de opeenvolging van de index, de datum en de hashwaarde van het vorige blok in de keten. Voor het genesisblok is dit dus de string 0Genesis Block0.
De blockchain zelf is een gelinkte lijst van blokken die kan uitgebreid worden door een nieuw blok met een gegeven datum toe te voegen (adjoin) aan een bestaand blok. Het valideren (validate) van een blok bestaat erin om de hashwaarde van het blok opnieuw te berekenen en te vergelijken met de ingestelde hashwaarde. Als dat het geval is, dan wordt de bewerking herhaald voor de voorgaande blokken in de keten, totdat het genesisblok bereikt wordt. De blockchain is corrupt van zodra een berekende hashwaarde verschilt van een ingestelde hashwaarde. Als het genesisblok bereikt wordt zonder een fout te vinden, dan is de blockchain geldig.
Opgave
Definieer een klasse Pearson waarmee de Pearson hashwaarde van strings kan berekend worden. Zorg ervoor dat de klasse minstens de volgende methoden ondersteunt:
-
Een initialisatiemethode met twee optionele parameters tabel en combineer. Aan de parameter tabel kan een permutatietabel $$T$$ (een lijst of een tuple) van de natuurlijke getallen tussen 0 (inbegrepen) en 256 (niet inbegrepen) doorgegeven worden. Als niet expliciet een waarde wordt doorgegeven aan de parameter tabel dan wordt als permutatietabel $$T$$ de reeks 0, 1, …, 255 gebruikt. Als de waarde die wordt doorgegeven aan de parameter tabel geen permutatie is van de natuurlijke getallen tussen 0 (inbegrepen) en 256 (niet inbegrepen) dan moet een AssertionError opgeworpen worden met de boodschap ongeldige tabel. Aan de parameter combineer kan een functie met twee parameters $$h$$ en $$v$$ doorgegeven worden. Deze functie wordt gebruikt om de twee waarden te combineren in stap (2b) van de procedure voor Pearson hashing. Als niet expliciet een waarde wordt doorgegeven aan de parameter combineer dan worden de twee waarden gecombineerd als $$(h + v)\ \text{mod}\ 256$$.
-
Een methode hash waaraan een string moet doorgegeven worden. De functie moet de Pearson hashwaarde voor de gegeven string teruggeven.
Definieer ook nog een klasse Blok waarmee blokken uit een blockchain kunnen voorgesteld worden. Aan de initialisatiemethode kan een hashfunctie doorgegeven worden. Deze hashfunctie wordt voorgesteld door een object met een methode hash waaraan een string $$s$$ kan doorgegeven worden en die de hashwaarde van de string $$s$$ teruggeeft. Als niet expliciet een hashfunctie wordt doorgegegeven aan de initialisatiemethode, dan moet de blockchain gebruikmaken van Pearson hashing met als permutatietabel $$T$$ de reeks 0, 1, …, 255.
Elk object van de klasse Blok moet vier eigenschappen hebben die bepaald worden zoals beschreven in de inleiding: index, datum, hash en vorig_hash. De eigenschappen index en vorige_hash zijn onveranderlijk. Als een poging wordt ondernomen om deze eigenschappen te wijzigen, dan moet een AttributeError opgeworpen worden met de boodschap can't set attribute. De eigenschappen datum en hash moeten wel gewijzigd kunnen worden, in een poging om de blockchain aan te passen.
Zorg ervoor dat de klasse Blok minstens de volgende methoden ondersteunt:
-
Een methode toevoegen waaraan een datum (str) moet doorgegeven worden. De methode moet een nieuw blok met gegeven datum aan de blockchain toevoegen en een verwijzing naar dit nieuw blok (een object van de klasse Blok) teruggeven.
-
Een methode is_geldig waaraan geen argumenten kunnen doorgegeven worden. De methode moet een Booleaanse waarde teruggeven die de geldigheid aangeeft van de keten die start bij het blok waarop de methode wordt aangeroepen.
Voorbeeld
>>> pearson = Pearson()
>>> pearson.hash('Hello')
244
>>> pearson.hash('Hello,')
32
>>> pearson.hash('Hell,o')
32
>>> pearson.hash('Hel,lo')
32
>>> pearson.hash('Hello, World!')
105
>>> pearson = Pearson(tabel=list(range(255, -1, -1)))
>>> pearson.hash('Hello')
173
>>> pearson.hash('Hello,')
38
>>> pearson.hash('Hell,o')
160
>>> pearson.hash('Hel,lo')
32
>>> pearson.hash('Hello, World!')
234
>>> pearson = Pearson(tabel=list(range(255, -1, -1)), combineer=lambda hash, char: (hash ^ char) % 256)
>>> pearson.hash('Hello')
189
>>> pearson.hash('Hello,')
110
>>> pearson.hash('Hell,o')
110
>>> pearson.hash('Hel,lo')
110
>>> pearson.hash('Hello, World!')
210
>>> Pearson([1, 2, 3, 4])
Traceback (most recent call last):
AssertionError: ongeldige tabel
>>> genesis = Blok()
>>> genesis.index, genesis.datum, genesis.hash, genesis.vorige_hash
(0, 'Genesis Block', 57, 0)
>>> genesis.is_geldig()
True
>>> blokA = genesis.toevoegen('A')
>>> blokA.index, blokA.datum, blokA.hash, blokA.vorige_hash
(1, 'A', 222, 57)
>>> blokA.is_geldig()
True
>>> blokB = blokA.toevoegen('B')
>>> blokB.index, blokB.datum, blokB.hash, blokB.vorige_hash
(2, 'B', 10, 222)
>>> blokB.is_geldig()
True
>>> blokC = blokB.toevoegen('C')
>>> blokC.index, blokC.datum, blokC.hash, blokC.vorige_hash
(3, 'C', 215, 10)
>>> blokC.is_geldig()
True
>>> blokD = blokB.toevoegen('D')
>>> blokD.index, blokD.datum, blokD.hash, blokD.vorige_hash
(3, 'D', 216, 10)
>>> blokD.is_geldig()
True
>>> blokD.index = 100
Traceback (most recent call last):
AttributeError: can't set attribute
>>> blokD.vorige_hash = 200
Traceback (most recent call last):
AttributeError: can't set attribute
>>> blokD.hash = 666
>>> blokA.is_geldig()
True
>>> blokB.is_geldig()
True
>>> blokC.is_geldig()
True
>>> blokD.is_geldig()
False
>>> blokD.hash = 216
>>> blokA.is_geldig()
True
>>> blokB.is_geldig()
True
>>> blokC.is_geldig()
True
>>> blokD.is_geldig()
True
>>> blokB.datum = 'XXX'
>>> blokA.is_geldig()
True
>>> blokB.is_geldig()
False
>>> blokC.is_geldig()
False
>>> blokD.is_geldig()
False
>>> blokB.datum = 'B'
>>> blokA.is_geldig()
True
>>> blokB.is_geldig()
True
>>> blokC.is_geldig()
True
>>> blokD.is_geldig()
True
>>> genesis = Blok(Pearson(tabel=list(range(255, -1, -1))))
>>> genesis.index, genesis.datum, genesis.hash, genesis.vorige_hash
(0, 'Genesis Block', 52, 0)
>>> genesis.is_geldig()
True
>>> blokA = genesis.toevoegen('A')
>>> blokA.index, blokA.datum, blokA.hash, blokA.vorige_hash
(1, 'A', 243, 52)
>>> blokA.is_geldig()
True