Kryptografisk hash-funktion

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 11. maj 2019; checks kræver 58 redigeringer .

Kryptografiske hashfunktioner er en særskilt klasse af hashfunktioner, der har visse egenskaber, der gør dem egnede til brug i kryptografi .

Konstruktionsprincipper

Iterativt sekventielt kredsløb

I det generelle tilfælde er konstruktionen af en hashfunktion baseret på et iterativt sekventielt skema. Kernen i algoritmen er en komprimeringsfunktion, der konverterer k input til n outputbit, hvor n er hashfunktionens længde, og k er et vilkårligt tal større end n . I dette tilfælde skal komprimeringsfunktionen opfylde alle betingelserne for kryptografisk styrke .

Indgangsstrømmen er opdelt i blokke af ( k − n ) bit. Algoritmen bruger en midlertidig variabel af størrelse n bit, hvis startværdi er et velkendt tal. Hver næste blok af data kombineres med outputværdien af krympningsfunktionen ved den foregående iteration. Værdien af hash-funktionen er output n bits af den sidste iteration. Hver bit af outputværdien af en hashfunktion afhænger af hele inputdatastrømmen og startværdien. Dermed opnås en lavineeffekt .

Når man designer hash-funktioner baseret på et iterativt skema, er der et problem med størrelsen af inputdatastrømmen. Størrelsen af inputdatastrømmen skal være et multiplum af ( k−n ) . Som regel udvides dataene før starten af algoritmen på en eller anden måde, der er kendt på forhånd.

Ud over single-pass algoritmer findes der multi-pass algoritmer, hvor lavineeffekten forstærkes yderligere. I dette tilfælde gentages dataene først og udvides derefter til den ønskede størrelse.

Kontraktionsfunktion baseret på den symmetriske blokalgoritme

Den symmetriske blokchifferalgoritme kan bruges som en komprimeringsfunktion . For at sikre større sikkerhed kan du bruge den datablok, der er beregnet til hashing ved denne iteration, som en nøgle og resultatet af den tidligere komprimeringsfunktion som input. Så vil resultatet af den sidste iteration være outputtet af algoritmen. I et sådant tilfælde er hashfunktionens sikkerhed baseret på sikkerheden af den anvendte algoritme.

Normalt, når man bygger en hash-funktion, bruges et mere komplekst system. Det generaliserede skema for den symmetriske blokkrypteringsalgoritme er vist i fig. 2.

Således får vi 64 muligheder for at konstruere en kontraktionsfunktion. De fleste af dem er enten trivielle eller usikre. Nedenfor er de fire mest sikre ordninger til alle typer angreb.

Den største ulempe ved hash-funktioner designet på basis af blokalgoritmer er deres lave hastighed. Den nødvendige kryptografiske styrke kan også opnås ved et mindre antal operationer på inputdataene. Der er hurtigere hashing-algoritmer designet af dig selv, fra bunden, baseret på kravene til kryptografisk styrke. De mest almindelige af dem er MD5 , SHA-1 , SHA-2 .

Krav

Kravene til kryptografiske hashfunktioner er:

1. Første preimage-søgningsmodstand : Givet en hash , burde det være svært at finde nogen meddelelse, sådan at . Denne egenskab er relateret til begrebet en envejsfunktion . Funktioner, der mangler denne egenskab, er sårbare over for første preimage-angreb . $h$ $m$ $h=hash(m)$

2. Modstand mod at søge efter det andet præbillede : givet en besked , burde det være svært at finde en anden besked (ikke lig med ) sådan, at . Denne egenskab omtales nogle gange som svag kollisionsmodstand. Funktioner, der mangler denne egenskab, er sårbare over for andet preimage opslagsangreb. $m_1$ $m_2$ $m_1$ $hash(m_{1})=hash(m_{2})$

3. Modstand mod kollisioner

En hashfunktionskollision er et par værdier og ", " for hvilke . Da antallet af mulige klartekster er større end antallet af mulige værdier af foldningen, så er der for nogle foldninger mange forbilleder, og derfor er der nødvendigvis kollisioner for hash-funktioner. Lad for eksempel længden af hash-præbilledet være 6 bit, længden af foldningen være 4 bit. Så er antallet af forskellige fold , og antallet af hash-forbilleder er altså 4 gange flere, hvilket betyder, at mindst én af alle fold svarer til 4 forbilleder. $m$ $m$ $m\neq m$ $H(m)=H(m')$ $2^{4}=16$ $2^6=64$

En hashfunktions modstand mod kollisioner betyder, at der ikke er nogen effektiv polynomiel algoritme til at finde kollisioner.

Disse egenskaber er ikke uafhængige:

En inverterbar funktion er ustabil over for gendannelse af det andet forbillede og kollisioner.
En funktion, der ikke er modstandsdygtig over for gendannelse af det andet forbillede, er ikke modstandsdygtig over for kollisioner; det omvendte er ikke sandt.
Funktionen er kollisionsbestandig, anden preimage modstandsdygtig.
En kollisionssikker hash-funktion er ikke nødvendigvis envejs.

Det er vigtigt for kryptografi, at hashværdier ændrer sig meget med den mindste ændring i argumentet ( lavineeffekt ). Hashværdien bør ikke lække information, selv om individuelle bits af argumentet.

Ved udvikling af den moderne russiske standard GOST R 34.11-2012 (Stribog) blev følgende krav formuleret til kryptografiske hashfunktioner:

Vanskeligheder ved at beregne præbilledet: hvis værdien af funktionen er kendt, så burde det være svært at finde en sådan besked, hvis hashfunktion er lig med den kendte;
Sikkerhed for beregningen af det andet preimage: lad der være én værdi, og hashkoden for denne værdi er kendt. Så burde det være svært for en angriber at finde en anden sådan værdi, så dens hash-funktion falder sammen med hash-funktionen af den første værdi;
Svært ved at finde kollisioner: det burde være svært at finde to sådanne beskeder, der ikke er ens, men de har de samme hash-koder;
Modstand mod forlængelse af preimage: hvis en angriber ikke kender beskeden, men kender dens længde og hash-kode fra den, så burde det være svært for ham at opfange en besked, der, når den føjes til originalen, vil give en kendt hash-funktion . Med andre ord burde det ikke være muligt for en angriber at ændre noget ved at tilføje til meddelelsen, mens outputtet bliver kendt. Dette kan siges på en anden måde: hash-funktionen behøver ikke at være godt "polstret".

4. Pseudo -tilfældighed : Det burde være svært at skelne en hash-baseret pseudo-tilfældig talgenerator fra en tilfældig talgenerator, for eksempel består den de sædvanlige test for tilfældighed .

Sikkert sikre hash-funktioner

Sikkerheden af en hash-funktion kan sikres af kompleksiteten af et matematisk problem, forudsat at der er bevis for, at angreb, der sigter mod at overtræde kravene til det, er lige så vanskelige som løsningen af dette problem. [en]

En kryptografisk hashfunktion er beviseligt kollisionssikker, hvis problemet med at finde kollisioner kan medieres i polynomiel tid fra et problem , der anses for uløseligt i polynomisk tid . Med andre ord, hvis algoritmen ville tillade at løse problemet med at finde kollisioner i polynomiel tid, hvis der eksisterer en reducerende algoritme , der også virker i polynomiel tid, så ville sidstnævnte tillade algoritmen at løse problemet i polynomiel tid, hvilket modsiger dens kompleksitet , hvilket betyder, at problemet med at finde kollisioner ikke er nemmere end opgaven . $P$ $EN$ $R$ $EN$ $P$ $P$

Den beviselige sikkerhed mod søgningen efter det første og andet præbillede er defineret på samme måde.

Modstanden mod søgningen efter det andet forbillede følger af den påviste modstand mod kollisioner, derfor er det i praksis nogle gange kun modstanden mod at finde det første forbillede og modstanden mod kollisioner, der er teoretisk bevist. [2]

Nogle problemer, der formodes at være uløselige i polynomisk tid, som kan bruges til at konstruere sådanne funktioner:

Ulemper ved den evidensbaserede tilgang

I nærvær af teoretiske garantier for kompleksitet har den evidensbaserede tilgang også betydelige ulemper:

De nuværende beviseligt sikre hashing-algoritmer er for beregningsmæssigt komplekse til at blive brugt i praksis. Sammenlignet med almindelige hash-funktioner er de ret langsomme.
At skabe beviseligt sikre hash-funktioner er meget mere tidskrævende end klassiske tilgange.
Selve sikkerhedsbeviset er ofte baseret på et problem, der har den nødvendige gennemsnitlige eller worst case kompleksitet. Worst-case kompleksitet beskriver oftest patologiske situationer frem for typiske for opgaven. Selv reduktion til et problem med kompleksitet i gennemsnit giver begrænset sikkerhed, da der kan findes en algoritme, der nemt løser problemet for en bestemt delmængde af problemdata. Så det blev for eksempel vist, at for to af de tre parametre, der blev foreslået i den oprindelige artikel for den hurtige syndrom-baserede hash- funktion, er der mere optimale angreb end dem, der er foreslået af skaberne for at bevise sikkerheden. [3]

SWIFFT er et eksempel på en hash-funktion, der i nogen grad omgår det beskrevne sikkerhedsproblem. Det kan påvises, at for enhver algoritme, der bryder SWIFFT med sandsynlighed i tid, er der en algoritme, der løser et bestemt matematisk problem i værste fald i tid afhængig af og . [fire] $P$ $T$ $T'$ $P$ $T$

Eksempler på beviseligt sikre hash-funktioner

VSH - Very Smooth Hash-funktion - er en beviseligt sikker kollisionsbestandig funktion, der er afhængig af vanskeligheden ved at finde ikke-trivielle kvadratrødder modulo et sammensat tal n (hvilket er lige så svært som at faktorisere n ).
MuHASH
ECOH - Elliptisk kurve kun hash - hash-funktion baseret på ideen om elliptiske kurver , delmængde-sumproblem og polynomiel summation. Sikkerhedsbeviset var baseret på antagelsen om NP-fuldstændighed af det underliggende matematiske problem, men der blev fundet en sårbarhed for Wagners generaliserede "fødselsdage"-angreb relateret til søgningen efter det andet forbillede. [5]
FSB - Fast Syndrome-Based hash-funktion - Det kan påvises, at bryde FSB er mindst lige så svært som at løse det NP-komplette problem kendt som regulær syndromafkodning. [6]
SWIFFT - SWIFFT er baseret på FFT og er beviseligt sikker under en ret svag antagelse om den værste vanskelighed ved at finde korte vektorer i et cyklisk/ideelt gitter. [7]
Chaum, van Heijst, Pfitzmann hash-funktion - en funktion, hvor det er lige så besværligt at finde kollisioner, som når man finder en diskret logaritme i en endelig gruppe . $F_{2p+1}$
Rygsæk-baserede hash-funktioner er en familie af hash-funktioner baseret på rygsæk-problemet .
Der er en generel tilgang til at bygge sikkert sikre hashing-algoritmer baseret på enhver passende sigma-protokol . En hurtigere version af VSH (kaldet VSH*) kan opnås på denne måde.

Den ideelle kryptografiske hash-funktion

En ideel kryptografisk hashfunktion er en kryptografisk hashfunktion, der har fem grundlæggende egenskaber:

Determinisme . Med de samme inputdata vil resultatet af hashfunktionen være det samme (den samme besked fører altid til den samme hash);
Højhastighedsberegning af hashværdien for en given besked;
Manglende evne til at generere en besked ud fra dens hashværdi, med undtagelse af at forsøge at skabe alle mulige beskeder;
Lavineeffekt. En lille ændring i beskederne skulle ændre hashværdierne så vidt, at de nye hashværdier ikke matcher de gamle hashværdier;
Manglende evne til at finde to forskellige beskeder med samme hashværdi.

En ideel kryptografisk hashfunktion, som har længden n (det vil sige outputtet er n bits), skal således mindst kræve operationer for at beregne præbilledet. $2^{n}$

En angriber vil lede efter et forbillede for en ideel hash-funktion på følgende måde: han har et tal h, og han skal finde m, således at H(m) = h. Hvis dette er en ideel hash-funktion, så kan angriberen kun gå igennem alle mulige M og tjekke, hvad hash-funktionen fra denne besked er lig med. Resultatet af beregningen, hvis m gentages fuldstændigt, er i virkeligheden et tilfældigt tal. Hvis tallet h ligger i området fra 0 til , vil angriberen i gennemsnit bruge iterationer på at søge efter den ønskede h. Således vil beregningen af præbilledet tage halvt så mange iterationer som i det ideelle tilfælde. $2^{n}$ $2^{{n-1}}$

Beregningen af det andet forbillede forbliver . I søgen efter kollisioner vil scoren give , og dette er ikke et helt præcist resultat. Denne vurdering kommer fra en vurdering af det såkaldte " Fødselsdagsparadoks ". $2^{n}$ $2^{n}$

Hvis en angriber vil skrive et program til at finde kollisioner, ville det være optimalt for ham først at anskaffe sig en ordbog over kollisioner. Følgelig beregner den hash-funktionen fra den næste besked og kontrollerer, om denne hash-funktion hører til den næste besked eller ej. Hvis den gør det, så er kollisionen fundet, og så kan den originale besked med den givne hash-kode findes i ordbogen. Hvis ikke, så fylder det ordbogen op. I praksis er denne metode ikke implementeret, fordi der ikke ville være nok hukommelse til en sådan ordbog.

Fødselsdagsangreb

Fødselsdagsangrebet er det navn, der bruges i kryptoanalyse for en metode til registrering af hashfunktionskollisioner baseret på fødselsdagsparadokset. Essensen af paradokset er, at i en gruppe på 23 eller flere personer overstiger sandsynligheden for sammenfald af fødselsdage (dag og måned) for mindst to personer 50%. Hvis der for eksempel er 23 eller flere elever i en klasse, så er det mere sandsynligt, at en af klassekammeraternes fødselsdage falder på samme dag, end at alle har deres egen unikke fødselsdag.

Lavineeffekt

Lad os overveje denne effekt og dens rolle i eksemplet med blockchain-hash-processen. Denne egenskab betyder, at hvis vi laver små ændringer i inputstrengen, så vil hasherne (det vil sige outputtet af den kryptografiske funktion) være drastisk forskellige fra hinanden. Lad os tjekke denne egenskab på et simpelt eksempel. Overvej for eksempel resultatet af en hash-funktion fra MD-familien - MD5. Ved input vil vi levere værdier, der kun vil afvige i tilfælde af de første tegn - strengene er næsten identiske. Deres hashes (resultatet af hashfunktionen) er dog forskellige.

Et eksempel på, hvordan MD5-krypteringsalgoritmen fungerer
Input	Produktion
bitcoin	0xCD5B1E4947E304476C788CD474FB579A
bitcoin	0xD023EC040F79F1A9B2AC960B43785089

"Høj entropi"

Gode hash-funktioner har egenskaben "Høj entropi ". Det betyder, at hasherne af dataarrays skal være maksimalt fordelt i systemet under hashing-processen, det vil sige, at de skal have en høj entropi i betydningen information. Som du ved, er entropi i betydningen information et mål for usikkerheden i et bestemt system, især uforudsigeligheden af et symbols udseende.

Så overvej for eksempel ligningen , hvor er sammenkædningen af en streng og streng , og er en kryptografisk hashfunktion. Hvis værdien har et højt entropiindeks, så vil det være næsten umuligt at finde en værdi, der opfylder ligningen. $OUTPUT=H(K|INPUT)$ $K|INPUT$ $K$ $INPUT$ $H$ $K$ $INPUT$

Udtrykket "Høj entropi" i forbindelse med hashfunktioner betyder en tilstand, hvor en værdi er valgt fra en så bred vifte af mulige muligheder, at forsøg på at gætte ved tilfældig udvælgelse ikke har nogen chance for succes. For eksempel har et tal, der er mellem 1 og 10, en lav entropi, mens et tal, der er mellem 1 og , omvendt har en høj entropi. $2^{256}$

Familie af hash-funktioner MD og SHA

Til dato er det overvældende flertal af applikationer af hash-funktioner "overtaget" af algoritmerne MD5 , SHA-1 , SHA-256 , og i Rusland - også GOST R 34.11-2012 (Stribog) . Selvfølgelig er der mange andre algoritmer, der er mindre kendte eller almindelige kun i snævre samfund (for eksempel RIPEMD , TIGER , Panama osv.), men disse algoritmer er ikke så almindelige. Nedenfor er en analyse af MD4- hash-funktionerne , som var forløberen til MD5, samt SHA-hash-funktionen.

Type	Beskrivelse
MD4	Den hurtigste, optimeret til 32-bit maskiner blandt familien af MD-funktioner. En hashfunktion udviklet af University of Massachusetts professor Ronald Rivest i 1990 og først beskrevet i RFC 1186. Indeholder tre sløjfer med hver 16 trin. I 1993 blev MD4-cracking-algoritmen beskrevet, så i dag anbefales denne funktion ikke til brug med rigtige applikationer.
MD5	Den mest almindelige af familien af MD-funktioner. Svarende til MD4, men sikkerhedsforbedringer gør den 33 % langsommere end MD4. Indeholder fire cyklusser med hver 16 trin. Giver dataintegritetskontrol. De første vellykkede forsøg på at knække denne hash-funktion går tilbage til 1993: Forskerne Bert den Boer og Anton Bossilaris viste, at pseudo-kollisioner er mulige i algoritmen. I 1996 viste Hans Dobbertin muligheden for kollisioner og beskrev teoretisk hacking-algoritmen. Den 24. august 2004 opdagede fire uafhængige forskere - Wang Xiaoyun, Feng Dengguo, Lai Xuejia og Yu Hongbo - en algoritmesårbarhed, der gør det muligt at finde kollisioner ved hjælp af en analytisk metode på mere eller mindre acceptabel tid. I 2005 udgav Vlastimil Klima en algoritme til at opdage kollisioner på få timer. Den 18. marts 2006 offentliggjorde en forsker en algoritme, der finder kollisioner på et minut, som senere blev kaldt "tunneling". I dag anbefales MD5 ikke til brug i virkelige applikationer.
SHA-1 (Sikker Hash Algoritme 1)	I 1993 arbejdede NSA sammen med NIST om at udvikle Secure Hash Algorithm (nu kendt som SHA-0) (udgivet i FIPS PUB 180) til en sikker hashing-standard. NSA trak dog snart denne version tilbage med henvisning til en fejl, de opdagede, som aldrig blev afsløret. Og erstattede den med en revideret version udgivet i 1995 i FIPS PUB 180-1. Denne version anses for at være det, der kaldes SHA-1 . Senere, på CRYPTO-konferencen i 1998, præsenterede to franske forskere et angreb på SHA-0-algoritmen, der ikke fungerede på SHA-1-algoritmen. Dette kan have været en fejl opdaget af NSA. SHA-1 opretter en 160-bit værdi, også kaldet en beskedsammenfatning. Indeholder fire trin. Både MD5 og SHA-1 er væsentligt forbedrede udvidelser af MD4. Forskelle: I SHA-1 bruger den fjerde fase den samme funktion som den anden fase. I MD5 bruger hver handling en unik inkrementel konstant. I SHA-1 genbruges konstanter for hver af de fire grupper. En femte variabel er blevet tilføjet til SHA-1. SHA-1 bruger en cyklisk fejlkorrektionskode. MD5 har fire forskellige elementære booleske funktioner, mens SHA-1 har tre. I MD5 er digestlængden 128 bit, i SHA-1 er den 160 bit. SHA-1 indeholder flere runder (80 i stedet for 64) og kører på en 160-bit buffer sammenlignet med MD5 's 128-bit buffer . Så SHA-1 burde køre omkring 25 % langsommere end MD5 på den samme hardware.
SHA-2	En familie af kryptografiske algoritmer - hash-funktioner, herunder SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/256 og SHA-512/224 algoritmerne. I 2003 gennemførte Gilbert og Handschuh en undersøgelse af SHA-2 , men fandt ingen sårbarheder. Men i marts 2008 offentliggjorde de indiske forskere Somitra Kumar Sanadiya og Palash Sarkar de kollisioner, de fandt for 22 iterationer af SHA-256 og SHA-512. I september samme år præsenterede de en metode til at konstruere kollisioner for trunkerede versioner af SHA-2 (21 iterationer). Undersøgelser har vist [8] at SHA-2 algoritmer virker 2-3 gange langsommere end MD5 , SHA-1 hash algoritmer .
SHA-256	Separat skiller SHA-256-algoritmen sig ud, som bruges i hashing-algoritmer til bitcoin og andre kryptovalutaer. Som navnet på den kryptografiske hash-funktion antyder, er output-hashen 256 bit lang, den tilsvarende entropi kan defineres som et sæt værdier fra 1 til 2 til styrken af 256 - et stort antal værdier, hvilket gør cracking og dekryptering en ekstremt tidskrævende proces baseret på sekventiel opregning.
SHA-3 ( Keccak)	SHA-3 hash-funktionen (også kaldet Keccak) er en variabel bitfunktion udviklet af en gruppe forfattere ledet af Joan Dymen . Den 2. oktober 2012 blev Keccak vinderen af konkurrencen om kryptografiske algoritmer afholdt af US National Institute of Standards and Technology [9] . Den 5. august 2015 blev funktionsalgoritmen godkendt og offentliggjort som en FIPS 202 [10] [11] standard . SHA-3-funktionsalgoritmen er bygget på princippet om en kryptografisk svamp .

Ansøgninger

Elektronisk signatur

For at sikre, at beskeden er sendt af en bestemt afsender, sendes en såkaldt elektronisk signatur sammen med beskeden. Modtageren tjekker, om den elektroniske signatur faktisk hører til den givne besked.

På grund af det faktum, at brugen af kryptografi med offentlige nøgler (signering, verificering af signaturer osv.) er en meget langsom proces, vil desuden, hvis du underskriver hele meddelelsen, størrelsen af denne signatur være sammenlignelig med størrelsen af den. besked, underskriv ikke beskeden, og en hash-funktion fra beskeden. Og så modtager modtageren, når han dekrypterer signaturen, en hash-funktion. Dernæst sammenligner han hash-funktionen fra den besked, han modtog, og hash-funktionen, der blev opnået som et resultat af dekryptering. På grund af at hash-funktionen har en fast længde, er den mindre end selve beskeden. Dette giver dig mulighed for hurtigt at beregne den digitale signatur. Størrelsen af denne signatur vil være lille sammenlignet med størrelsen af meddelelsen.

Bekræftelse af adgangssætning

I de fleste tilfælde gemmes adgangssætninger ikke på mål, kun deres hashværdier gemmes. Det er ikke tilrådeligt at gemme adgangssætninger, for i tilfælde af uautoriseret adgang til en fil med sætninger, vil en angriber kende alle adgangssætningerne og vil være i stand til at bruge dem med det samme, og når han gemmer hashværdier, vil han kun lære hashværdier der ikke er reversible til de originale data, i dette tilfælde - til en adgangssætning. Under godkendelsesproceduren beregnes hashværdien af den indtastede adgangssætning og sammenlignes med den gemte.

Eksempler i dette tilfælde er GNU/Linux og Microsoft Windows XP . De gemmer kun hash-værdier af adgangssætninger fra brugerkonti .

Dette system indebærer transmission af en besked over en sikker kanal, det vil sige en kanal, hvorfra det er umuligt for en kryptoanalytiker at opsnappe beskeder eller sende sine egne. Ellers kan han opsnappe adgangssætningen og bruge den til yderligere ulovlig godkendelse. Du kan beskytte dig selv mod sådanne angreb ved hjælp af challenge-response- metoden .

Lad en klient ved navn navn autentificere med en adgangssætning, pass , til en server. Serveren gemmer hashværdien H ( pass , R 2 ) , hvor R 2 er et pseudo-tilfældigt, forudvalgt tal. Klienten sender en anmodning ( navn , R 1 ), hvor R 1 er en pseudo-tilfældig, hver gang et nyt nummer. Som svar sender serveren værdien R2 . Klienten beregner hashværdien H ( R 1 , H ( pass , R 2 )) og sender den til serveren. Serveren beregner også værdien H ( R 1 , H ( pass , R 2 )) og kontrollerer den mod den modtagne. Hvis værdierne stemmer overens, er godkendelsen korrekt.

I en sådan situation er adgangskoden ikke gemt åbent på serveren, og selv efter at have opsnappet alle meddelelser mellem klienten og serveren, kan kryptanalytikeren ikke gendanne adgangskoden, og den transmitterede hashværdi er forskellig hver gang.

Bitcoin hashing

Bitcoin betalingssystem transaktioner , der præsenteres som en bestemt række af data, kombineres i blokke (herefter vil helheden af alle blokke blive kaldt blockchain ) og går gennem en hashing-algoritme, det vil sige, at deres feltdata føres til inputtet af en kryptografisk hash-funktion. Hver transaktion angiver, hvor midlerne debiteres fra, og hvor de går hen. For at angive adressaten bruges hans offentlige nøgle (en unik identifikator i bitcoin-netværket). For at adressaten kan bruge de modtagne penge inden for bitcoin-protokollen (vi udelukker salg af sin egen tegnebog - Wallet), skal han oprette en ny transaktion, der vil tage valutaen fra den forrige og omdirigere den til en anden adresse ved hjælp af offentlig nøgle. Følgelig vil den nye transaktion, sammen med transaktionerne fra andre brugere af bitcoin-netværket, falde i en ny blok. Dermed vokser antallet af blokke i blockchainen. Hver transaktion skal dog godkendes – systemet skal nå til konsensus. Der er flere måder at gøre dette på, men Bitcoin bruger Proof-of-Work (PoW) princippet. Efter at transaktionen er accepteret, betragtes den som reel, og kryptovalutaen flytter sig fra en pung til en anden.

Bitcoin-systemet er et decentraliseret system uden dedikerede blokgenereringscentre. Hver deltager kan tage et sæt transaktioner, der venter på at blive logget, og danne en ny blok. Desuden vil en sådan deltager (miner) i systemer som BitCoin også modtage en bonus i form af et bestemt beløb eller kommission fra transaktioner, der accepteres i blokken.

Men du kan ikke bare tage og danne en blok i decentrale systemer. Systemet skal opnå konsensus, det vil sige få godkendelse. Der er flere måder at gøre dette på, men Bitcoin bruger Proof-of-Work (PoW) princippet. Pålideligheden af sådanne systemer er netop baseret på det faktum, at en ny blok ikke kan dannes hurtigere (i gennemsnit) end på en vis tid. For eksempel på 10 minutter (BitCoin).

Blockstrukturen af BitCoin Blockchain

Mark	Beskrivelse	størrelse
Magisk nr	værdi altid 0xD9B4BEF9	4 bytes
blokstørrelse	antal bytes, der følger op til slutningen af blok	4 bytes
blokhoved	bestående af 6 genstande	80 bytes
transaktionstæller	positivt heltal	1-4 bytes
transaktioner	listen <ikke tom> over transaktioner	<Transaktionstæller> - mange transaktioner

Blockheader-strukturen i BitCoin Blockchain-blokken

Mark	Formål	Opdater når...	størrelse
version	blokere versionsnummer	Du opgraderer softwaren, og den specificerede en ny version	fire
hashPrevBlock	256-bit hash af den forrige blokoverskrift	En ny blok kommer ind	32
hashMerkelRoot	256-bit hash baseret på alle transaktionerne i blokken	En transaktion accepteres	32
Tid	nuværende tidsstempel som sekunder siden 1970-01-01 T00:00 UTC	Med få sekunders mellemrum	fire
stykker	nuværende mål i kompakt format	Sværhedsgraden justeres _	fire
intet	32-bit tal (starter ved 0)	En hash er træt (stigninger)	fire

sværhedsgrad er antallet af nul bit, der vil være i begyndelsen af måltallet .

target er det tal, som blokhashen skal være mindre end for at blokken anses for at være gyldig. Mål eller mere præcist sværhedsgrad afhænger af netværkets aktuelle kraft, og du skal ændre sværhedsgraden for hver n (i BitCoin-netværket - 2016) blokke, så der genereres en blok hvert 10. minut. Lad os antage, at 2016-blokke genereres i netværket, og hver klient kontrollerer, hvor længe hver blok blev oprettet. Hvis denne tid er længere end beregnet, det vil sige mere end 10 minutter, falder kompleksiteten.

nonce er et tilfældigt tal, som minearbejdere skal samle op for at lave en blokering.

Strukturen af bitcoin-datastrukturen

Som nævnt ovenfor er et sæt Bitcoin-transaktioner repræsenteret som forbundne blokke af data - blockchain . Enhedsstrukturen af selve blockchainen præsenteres som en sammenkædet liste med pointere.

Hver blok har en pointer, der indeholder et link til den forrige datablok. For at gå til n + 1 blokke er det således nødvendigt at følge pointerne fra de foregående n blokke. Derfor tilføjer pointere først adressen på en ny blok, efter at den oprindelige datablok er gået gennem bitcoin-hash-algoritmen - dette giver dig mulighed for at gøre forbindelsen pålidelig og sikker.

Et sådant system er mindre tilbøjelige til at blive angrebet af ubudne gæster, der kan forsøge at ændre dataene i blockchain, for eksempel for at udføre deres egen transaktion på den valgte adresse. Som allerede nævnt afhænger hashen af hver blok i blockchain ikke kun af dets eget indhold, men også af indholdet af den forrige blok. Enhver ændring i dataene i den oprindelige blok medfører således en ændring i dataene i andre blokke. Dette garanterer blockchainens uforanderlighed og systemets sikkerhed, da det er ekstremt svært at "falske" blockchainen. Det skal dog bemærkes, at hver bloks hash skal være unik, ellers bliver det umuligt at spore angrebsforsøg.

Merkle træ

Alle transaktioner er repræsenteret som strenge i hexadecimalt format, som hashes for at opnå transaktions-id'er. Baseret på dem opbygges en blokhash, som tages i betragtning af den efterfølgende blok, hvilket sikrer uforanderlighed og sammenhæng. En enkelt blokhash-værdi indsamles ved hjælp af et Merkle-træ .

Et Merkle-træ er et komplet binært træ , hvis bladspidser indeholder hash fra transaktioner, og de indre hjørner indeholder hashes fra tilføjelse af værdier i underliggende knudepunkter, og træets rodknude (Top Hash) indeholder en hash fra hele datasættet.

Konstruktionen af Merkle-træet til bitcoin blockchain er som følger:

$H(L_{i})$ - resultatet af hashfunktionen fra transaktionen $L_{i}$

Hashen af transaktioner placeret i blokke beregnes: H(L1), H(L2), H(L3) og så videre.
Hashes beregnes ud fra summen af hashes af transaktioner, for eksempel H(H(L1) + H(L2)). Da Merkle-træet er binært, skal antallet af elementer ved hver iteration være lige. Derfor, hvis en blok indeholder et ulige antal transaktioner, så duplikeres sidstnævnte og tilføjes til sig selv: hash (H(L3) + H(L3)).
Yderligere beregnes hashes igen ud fra summen af hashes. Processen gentages, indtil der opnås en enkelt hash - roden af Merkle-træet. Det er et kryptografisk bevis på blokintegritet (det vil sige, at alle transaktioner er i den angivne rækkefølge). Værdien af roden er fastsat i blokoverskriften.

Samtidig, når for eksempel transaktion L1 er brugt, kan data om den fjernes fra blokken, og kun dens hash kan efterlades til blokverifikation. Når transaktioner L1 og L2 er brugt, så kan vi slette deres hashes (hash 0-0 og hash 0-1), og kun tilbagelade hash 0, igen til blokverifikationsformål. I det øjeblik, hvor alle transaktioner er brugt, så kan alle hashes slettes, undtagen Top Hash, fordi oplysninger om disse transaktioner ikke længere vil være nødvendige.

For at opnå en hash for en ny kædeblok er det således nødvendigt at tage højde for alle tidligere transaktions-hash. Ændring af hashen af mindst én af de foregående blokke vil føre til en ændring i hash for den næste blok, henholdsvis, en sådan transaktion kan umiddelbart identificeres som ugyldig.

Bitcoin minedrift

Minedrift er processen med at finde konsensus om princippet om Proof-Of-Work - at opnå godkendelse til at oprette en ny blok. Faktisk, i BitCoin-netværket, kommer dette ned på at tælle hashen fra blokken og sammenligne den med målnummeret : hvis hashen er mindre end målet, så genereres en ny blok, ellers er den ikke.

Minearbejdere sikrer den fortsatte vækst af blockchain. Til dette bruges enorm computerkraft – hver minearbejder bidrager til at øge den samlede bitcoin-hashrate (computerkraft). Andelen af bitcoin-hash-operationer af hver minearbejder afhænger af den samlede hashrate-indikator - jo højere netværkets samlede hashrate er, jo mere beregningsmæssigt arbejde på kortere tid skal minearbejderen udføre for at opretholde den gennemsnitlige størrelse af sin minedriftsbelønning.

Processen med at erstatte en nonce i en streng fortsætter, indtil den rigtige løsning er fundet. Nogle gange kan antallet af forsøg nå op til millioner af gange. Minearbejderen, der først finder den rigtige løsning, tilføjer blokken til blockchain og modtager en belønning for dette.

Nonce-udvælgelsesprocessen er baseret på brute force- metoden . Derfor genererer mineudstyret kontinuerligt tilfældige strenge, indtil den nødvendige nonce- værdi er fundet .

Eksempler på kryptovalutaer, der bruger SHA-256 hash-funktionen til kryptering

SHA-256 er en klassisk algoritme for kryptovalutaer: den vigtigste kryptovaluta, Bitcoin, er bygget på den. Derfor bruges denne algoritme også i Bitcoin gafler: i Bitcoin Cash, Bitcoin SV. Samtidig bruger minearbejdere i Bitcoin Gold en kryptofunktion - Equihash

Ud over dem bruges SHA-256 også i:

Steemit;
peercoin ;
NameCoin ;
Ocoin;
Zetacoin;
emercoin .

SHA-256-algoritmen bruges også som en underrutine i Litecoin-kryptovalutaen, og hovedalgoritmen til minedrift er Scrypt.

Se også

Noter

↑ Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. En hurtig beviseligt sikker kryptografisk hash-funktion . - 2003. - Nr. 230 . - S. 3-4 . Arkiveret fra originalen den 8. december 2019.
↑ Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. En hurtig beviseligt sikker kryptografisk hash-funktion . - 2003. - Nr. 230 . - S. 3 . Arkiveret fra originalen den 8. december 2019.
↑ Jean-Sebastien Coron, Antoine Joux. Krypteringsanalyse af en sikkert sikker kryptografisk hash-funktion . - 2004. - Nr. 013 . - S. 1.3 . Arkiveret fra originalen den 7. december 2019.
↑ Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: Et beskedent forslag til FFT-hashing // Hurtig softwarekryptering. — Springer, Berlin, Heidelberg, 2008-02-10. — S. 65 . — ISBN 9783540710387 , 9783540710394 . - doi : 10.1007/978-3-540-71039-4_4 . Arkiveret fra originalen den 8. april 2019.
↑ Michael A. Halcrow, Niels Ferguson. Et andet angreb før billedet mod kun elliptisk kurvehash (ECOH) . - 2009. - Nr. 168 . Arkiveret fra originalen den 24. december 2018.
↑ Daniel Augot, Matthieu Finiasz, Nicolas Sendrier. En hurtig beviseligt sikker kryptografisk hash-funktion . - 2003. - Nr. 230 . Arkiveret fra originalen den 8. december 2019.
↑ Alon Rosen, Chris Peikert, Daniele Micciancio, Vadim Lyubashevsky. SWIFFT: Et beskedent forslag til FFT-hashing // Hurtig softwarekryptering. — Springer, Berlin, Heidelberg, 2008-02-10. - S. 54-72 . — ISBN 9783540710387 , 9783540710394 . - doi : 10.1007/978-3-540-71039-4_4 . Arkiveret fra originalen den 8. april 2019.
↑ Hastighedssammenligning af populære kryptoalgoritmer . www.cryptopp.com. Hentet 22. december 2017. Arkiveret fra originalen 2. juli 2017.
↑ Swenson, Gayle . NIST udvælger vinder af Secure Hash Algorithm (SHA-3) Competition (eng.) , NIST (2. oktober 2012). Arkiveret fra originalen den 5. oktober 2012. Hentet 23. december 2017.
↑ Hernandez, Paul . NIST udgiver SHA-3 Cryptographic Hash Standard , NIST ( 5. august 2015). Arkiveret fra originalen den 24. januar 2018. Hentet 23. december 2017.
↑ Morris J. Dworkin. SHA-3 Standard: Permutationsbaseret Hash og Extendable Output-funktioner // Federal Inf. behandle. Stds. (NIST FIPS) - 202. - 2015-08-04. Arkiveret fra originalen den 17. september 2017.

Litteratur

Bruce Schneier. Anvendt kryptografi. Protokoller, algoritmer, kildetekster i C-sprog. - M . : Triumph, 2002. - ISBN 5-89392-055-4 .
Laponina O.R. Kryptografiske grundprincipper for sikkerhed . - M . : Internet University of Information Technologies - INTUIT.ru, 2004. - S. 320. - ISBN 5-9556-00020 -5.

Links

Oplysninger om elektronisk digital signatur . (ubestemt)
Keccak Hash-funktionen og svampekonstruktionen som en universel kryptoprimitiv, pgpru.com, 2010-2013 (oversat fra noekon.org)
Teksten til den officielle standard GOST R 34.11-2012 i Wikisource

Hash funktioner
generelle formål	Adler-32 CRC Fletcher kontrolsum FNV MurmurHash2 MurmurHash2A MurmurHash3 PJW-32 TTH - Hash Tree jenkins hash hash sum
Kryptografisk	Stribog GOST R 34,11-94 Bælte BLAKE bmw CubeHash EKKO edonkey2k FSB Fuge Grostl HAVAL Hamsi JH Kupyna LM hash Luffa MD2 MD4 MD5 MD6 N-hash RIPEMD-128 RIPEMD-160 RIPEMD-256 RIPEMD-320 SHA-1 SHA-2 Keccak (SHA-3) SHABAL SHAvite-3 SIMD SWIFFT Hud Snefru Tiger Whirlpool
Nøglegenereringsfunktioner	bcrypt PBKDF2 krypt Argon 2 Lyra2
Tjek nummer ( sammenligning )	Tjek sum Verhouffs algoritme Månen algoritme Damm algoritme Stregkode bankkonti bankkort ER I SNILS OKPO TIN OKATO ISBN OGRN og OGRNIP VIN
Hashes	Sammenligning af checknumre Autentificeringsprotokoller Stregkode sammenligning Kryptografi Magnet link Merkle signatur ed2k URNE