Ang Malaking Tulong na Cryptographic Hash Functions
Ang Malaking Tulong na Cryptographic Hash Functions

Ang Malaking Tulong na Cryptographic Hash Functions

Ang susunod naman na maigi nating intindihin ay ang Cryptographic Hash Functions. Maghanda ka, medyo siksik ito.

Ang hash function ay ang pag mapa ng mga binary strings na kahit ano ang haba, papunta sa binary strings na may nakapirming haba. Halimbawa, isa sa gamit sa operasyon ng bitcoin ay ang (Secure Hash Algorithm) SHA-256. Ito ay may 256 bits na output, kaya kahit ang input ay blangko lang, isang letra, salita, pangungusap, o talata ang haba: 256 bits pa rin ang output. Makikita sa talaan sa baba ang output ng iba-ibang habang strings.

StringHash value (gamit ang SHA-256, anyong hexadecimal)
“”e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
“A”559aead08264d5795d3909718cdd05abd49572e84fe55590eef31a88a08fdffd
“Aba”770e56386d2f3e140ffba0032342511c1c3cd9fed9312f62ddedf3a4a8749b1f
“Aba nakakabasa na pala ako.”56d9d5cf7e7e2bd8b3047c3409cf9fc29aa44aa77fd79ae894490626b23f8b43
Hash value ng iba-ibang haba ng string, gamit ang SHA-256 (subukan mo rin sa website na ito: https://xorbin.com/tools/sha256-hash-calculator)

Atras muna tayo patungo sa simpleng hash function. Isang aplikasyon nito ay sa data storage and retrieval – kung paano magtago at kunin ang data sa memorya ng kompyuter. Tignan ang paglalarawang ito para sa basic na konsepto:

Ilustrasyong ng simpleng hash; makikitang may 2 input na nagkaparehas ng output – collision – na hindi kanais-nais.

Madalas may katumbas ang function na hash table. Sa simpleng ilustrasyon, ito yung talaan ng hashes sa kanan. Parang index kumbaga kapag nag-aayos ng data. Lalaktawan na natin ang pagdetalye ng halimbawa ng isang basic hash function, dahil nabigyan ka na ng ideya sa pagmamanipula ng input nung pinag-usapan ang naunang klase ng kriptograpiya.

Ang cryptographic hash function ay hango sa konsepto ng hash function pero may mas pinaigting na mga pangagailangan upang magamit bilang sandata sa proteksyon ng mga data.

Ang pagmamapa sa kontexto ng kriptograpiya ay ang komputasyon sa pagmamanipula ng input, gamit ang iba-ibang operasyon. Ang mga ito ay padding, permutasyon, pagpalit-palit ng posisyon ng bits, lohika, modular arithmetic atbp., depende sa nasasaad sa algorithm ng hash function. Maihahalintulad ito sa block cipher, na may iba-ibang operasyon na ginagamit sa input bits para maiba anyo ng output. Sa katunayan, may mga hash functions na base sa block cipher ang operasyon.

Naaalala mo ang diskusyon tungkol sa bitcoin wallets? Gumagamit iyon ng cryptographic hash function upang makagawa ng bitcoin address. Ginagamit din ang hashing para sa proof-of-work, sa paggawa ng header ng mga bloke ng transaksyon, at sa paggastos ng bitcoin.

Ang hash function na gamit ay kailangang may sapat na seguridad upang:

  • Mula sa isang hash/output, napakahirap at hindi na praktikal para mahulaan ang input. One-way hash function kumbaga – sa isang direksyon lang sya madaling kalkulahin (input —> output). Madali syempre para sa kompyuter, kasi matagal masyado pag manu-mano.
  • Maiwasan ang collision. Ito ay ang pagkakaroon ng parehas na output ng magkaibang input. Ang bitcoin address ng mga tao dapat ay magkakaiba. Ang mga block headers ng blockchain syempre dapat iba-iba. At ang paggastos ng bitcoin ay para lamang dapat sa nakasaad na may-ari.

Nasa baba ang pagdetalye ng sankgap at algorithm ng SHA-256 na gamit sa bitcoin, para magka-ideya ka gaano ka komplikado ang “pagmamapa”. Sa komplikasyong ito, hindi na magiging praktikal hulaan pa ang input:

Mga Sangkap at Algorithm ng SHA-256

INPUT: Plaintext sa anyong bits (kahit anong haba < 264)
OUTPUT: Hash na may 256 bits

Mga operasyon sa salita (bitwise):
∧ AND
∨ OR
⨁ XOR
¬ Bitwise complement
SHRn(x) right shift (x bits, n places)
ROTRn(x) rotate right (x bits, n places)

Mga functions:
Ch(x,y,z) = (x ∧ y) ⨁ (¬ x ∧ z)
Maj(x,y,z) = (x ∧ y) ⨁ (x ∧ z) ⨁ (y ∧ z)
0{256} (x) = ROTR2(x) ⨁ ROTR13(x) ⨁ ROTR22(x)
1{256} (x) = ROTR6(x) ⨁ ROTR11(x) ⨁ ROTR25(x)
σ0{256} (x) = ROTR7(x) ⨁ ROTR18(x) ⨁ SHR3(x)
σ1{256} (x) = ROTR17(x) ⨁ ROTR19(x) ⨁ SHR10(x)

Initialization
Mga constants, Kt{256} (64 lahat, tig 32 bits). Itong mga ito ay hango sa: “first 32 bits of the fractional parts of the cube roots of the first 64 prime numbers.”
K0, K1, K2, … K63:

428a2f98 71374491 b5c0fbcf e9b5dba5 3956c25b 59f111f1 923f82a4 ab1c5ed5 d807aa98 12835b01 243185be 550c7dc3 72be5d74 80deb1fe 9bdc06a7 c19bf174 e49b69c1 efbe4786 0fc19dc6 240ca1cc 2de92c6f 4a7484aa 5cb0a9dc 76f988da 983e5152 a831c66d b00327c8 bf597fc7 c6e00bf3 d5a79147 06ca6351 14292967 27b70a85 2e1b2138 4d2c6dfc 53380d13 650a7354 766a0abb 81c2c92e 92722c85 a2bfe8a1 a81a664b c24b8b70 c76c51a3 d192e819 d6990624 f40e3585 106aa070 19a4c116 1e376c08 2748774c 34b0bcb5 391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3 748f82ee 78a5636f 84c87814 8cc70208 90befffa a4506ceb bef9a3f7 c67178f2

Mga initial na Hash value (8, tig 32 bits):
H0(0) = 6a09e667
H1(0) = bb67ae85
H2(0) = 3c6ef372
H3(0) = a54ff53a
H4(0) = 510e527f
H5(0) = 9b05688c
H6(0) = 1f83d9ab
H7(0) = 5be0cd19w

Pre-processing

Padding – ito ay ang pagdagdag ng bits sa dulo ng mensahe upang maging tama ang laki ng block na ipoproseso. Sa SHA-256, tig 512 bits ang block na pinoproseso. Kaya pag maiksi sa 512 bits ang mensahe, ipa-padding ito. Kapag mas mahaba naman sa 512 bits ang mensahe, ipa-padding ang huling bloke matapos i-grupo ng tig-512-bit blocks ang mensahe.

Sa pag-padding, susundan ang equation na:
l + 1 + k ≡ 448 mod 512

Kung saan ang l ay haba ng mensahe o dami ng bits. Ang 1 ay dahil automatic na lalagyan ng binary digit 1 matapos ang huling bit ng mensahe. Ang k ay ang dami ng 0 bits na idadagdag hanggang maging 448 bits ang haba. Ang huling 64 bits ay representasyon ng haba ng mensahe sa anyong binary.

Halimbawang mensahe, “BABA!”, sumusunod na:

Message, M01000010 01000001 01000010 01000001 00100001
Length, l40 bits in decimal —> 101000 in binary
No. 0 bits, k448-(40+1) = 407
Last 64 bits000…101000
512-bit block01000010 01000001 01000010 01000001
00100001 10000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00101000

Parsing – ito ang pag-ayos ng istraktura ng mensahe at padding na nabuo. Ang istraktura sa SHA ay N m-bit blocks. Ang N ay kung anumang multiple ng block ang nabuo. At m ay laki ng block. Kada bloke ng mensahe ay M(1), M(2), …, M(N).

Sa SHA-256 ng halimbawa natin, N = 1, isang bloke lang o M(1). Ang m ay 512 bits. Tapos, hahatiin pa natin ang bloke sa 16 na tig 32 bits, M0(i), M1(i), …, M15(i). Makikita mo sa talaan sa taas na nakahati ang halimbawang 512-bit block nang ganun, bawat helera pababa ang katumbas ng: M0(1), M1(1), …, M15(1).

Processing

Mapapansin mo na ang constants at initial hash values ay may habang 32 bits. May 8 variables kasi tayong ipo-proseso na tig 32 bits. Para pag pinagsama-sama sa bandang huli, ay 32 x 8 = 256 bits, na syang haba ng output.

Sa i=1 hanggang N:
{

  1. Ihanda ang message schedule, {Wt}:
    Wt = Mt(i) kapag 0 ≤ t ≤ 15
    Wt = σ1{256}(Wt-2) + Wt-7 + σ0{256}(Wt-15) + Wt-16 kapag 16 ≤ t ≤ 63
  2. Itakda ang inisyal na halaga ng 8 variables
    a = H0(i-1)
    b = H1(i-1)
    c = H2(i-1)
    d = H3(i-1)
    e = H4(i-1)
    f = H5(i-1)
    g = H6(i-1)
    h = H7(i-1)
  3. Sa t=0 hanggang 63:
    {
    T1 = h + ∑1{256}(e) + Ch(e,f,g) + Kt{256} + Wt
    T2 = ∑0{256}(a) + Maj(a,b,c)
    h = g
    g = f
    f = e
    e = d + T1
    d = c
    c = b
    b = a
    a = T1 + T2
    }
  4. Kunin ang bagong hash value H(i):
    H0(i) = a + H0(i-1)
    H1(i) = b + H1(i-1)
    H2(i) = c + H2(i-1)
    H3(i) = d + H3(i-1)
    H4(i) = e + H4(i-1)
    H5(i) = f + H5(i-1)
    H6(i) = g + H6(i-1)
    H7(i) = h + H7(i-1)
    }

Matapos ulitin ang 4 na hakbang ng N na beses; ang resultang 256-bit hash ay ang pinagduktong na 8 hashes:
H0(N)||H1(N)||H2(N)||H3(N)||H4(N)||H5(N)||H6(N)||H7(N)

(Sa halimbawa natin, di na kailangan ulitin dahil N = 1.)

Idagdag lang natin na sa bitcoin, doble ang hashing kapag gumagawa ng address mula sa public key: SHA-256 at RIPEMD-160. At mayroon pang mekanismo na susunod, pero saka na natin pag-usapan.


Hoo! Musta ka? Kitakits sa ika-10

Mag-iwan ng Tugon

Ang iyong email address ay hindi ipa-publish. Ang mga kinakailangang mga field ay markado ng *