Bitcoin ba kamo?
Kabanata 3: Cryptography

Kabanata 3: Cryptography

(Mambabasa: Intermediya – advanced, medyo maalam hanggang sa maalam sa mga paksang teknikal)

Tayo ay lumihis pa uli, bago pag-usapan ang bitcoin. Tignan natin ang cryptography (kriptograpiya), na isang mahalagang pag-aaral sa panahon ng impormasyon.

Ang bitcoin ay gumagamit ng konsepto ng public-key cryptography, elliptic curve cryptography, cryptographic hash functions at digital signatures. Teka, ano? Bumalik muna tayo sa basic – mahaba-haba ito!

Kung may alam ka na sa larangang ito, maaari mong laktawan ang mga elementaryang diskusyon at tignan nalang ang public-key cryptography, cryptographic hash functions, at elliptic curve digital signature algorithm sa II-B, II-C, at II-E na syang ginagamit sa operasyon ng bitcoin.

Ang cryptography ay ang agham at sining ng pagtatago ng mensahe para sa seguridad ng impormasyon. Maaaring sintagal na nito ang sining ng pagsusulat.

Ang konsepto ng cryptography ay:

Simpleng konsepto ng cryptography

Plain text ang mensahe, habang ang ciphertext naman ay hindi maintindihang anyo ng sulat. Sa encryption tinatago ang mensahe, kung saan naiiba ang anyo ng plaintext papuntang ciphertext. Sa decryption naman naibubunyag ang mensahe; ito ay kabaliktaran ng encryption. Cipher ang tawag sa algorithm o pamamaraan ng pagtatago o pagbubunyag ng mensahe.

Pangangailangan ng Cryptography

Maihahalintulad natin ang mga kondisyon kung san nabuo ang cryptography sa pangangailangan ng pera. Habang lumalaki ang populasyon, dumadami ang hindi mo kakilala. May mga mensahe ka na hindi kelangan malaman ng iba. Sumibol din ang politika, kapangyarihan, digmaan, atbp. na nakadagdag sa pangangailangan at pagsulong ng cryptography dahil sa sitwasyon na marami kang hindi kasundo. Isipin mo ang mga magkakalaban sa digmaan: paano magbibigay ang heneral sa kanyang mga kapitan na nasa ibang lugar, ng mahalagang mensahe na hindi nalalaman ng katunggali?

I. Simple o Tradisyonal na Cryptography

Tayo’y maglibang saglit sa pagtingin ng ilang halimbawa ng simple o tradisyonal na cryptography. Makakatulong din ito upang mailatag ang konsepto ng cryptography at kung bakit dapat pinapaigting ito.

Umpisahan natin sa halimbawang mensahe na ito:

UMATAKE NG MADALING ARAW

Caesar Cipher

Ito ay isa sa pinakasimpleng anyo ng encryption, na tinatawag ding shift cipher. Ito ay ipinangalan kay Julius Caesar dahil ginamit nya ito sa mga pribadong pag-susulatan.

Ang bawat letra ay binibigyan ng katumbas na ibang letra sa pamamagitan ng pag-usog (shift) ng ilang posisyon base sa pagkakasunud-sunod ng alpabeto. Halimbawa, bigyan natin ng katumbas ang normal na alpabeto sa pamamagitan ng pag-usog ng 3 posisyon pakaliwa.

PlainABCDEFGHIJKLMNOPQRSTUVWXYZ
CipherDEFGHIJKLMNOPQRSTUVWXYZABC

Iikot lamang ang helera, kaya para sa mga huling letra (XYZ), ibabalik lang ang umpisang mga letra ng alpabeto (ABC).

Gamit ito, ang pagbabago ng orihinal na mensahe ay:

Plaintext: UMATAKE NG MADALING ARAW
Ciphertext: XPDWDNH QJ PDGDOLQJ DUDZ

Para maibalik sa orihinal na mensahe, babaliktarin lamang ng nakatanggap ang pag-usog ng mga letra (3 posisyon pakanan).

Sa halimbawang ito, ang nagpadala at tumanggap lamang ang dapat nakakaalam ng cipher. Kapag nalaman ito ng kalaban, mabibisto ang mensahe.

Kung di marunong magbasa ang kalaban, na karaniwan nung mga unang panahon, maaaring epektibo ang Caesar Cipher. Pero malamang naiisip mo na madali lang ito mahulaan. Tama ka dyan. Iilang posibilidad lang ang meron sa encryption na ito sa alpabetong may 26 na titik: 25 (sa ika-26 na ikot kasi, balik ka na sa orihinal na alpabeto).

Kung hindi mo alam na Caesar Cipher ang gamit, maari mo pa rin itong hulaan sa pag-inspeksyon ng frequency o dalas ng paggamit ng mga letra. Sa wikang Ingles halimbawa, ang letrang E ang pinakamadalas gamitin. Sa wikang Filipino naman, letrang A. Kung mahaba ang mensahe mas magiging malinaw kung anong mga letra ang madalas lumabas kumpara sa iba. Sa halimbawa natin, maraming A ang orihinal na mensahe. Sa paghula ng kalaban, una nyang ipagpapalagay na ang letrang D malamang ay letrang A, atbp.

Magagamitan ng frequency analysis ang klaseng ito dahil ang cipher natin ay monoalphabetic – ibig sabihin, ang bawat tamang letra ay may katumbas na isang letra lamang. Halimbawa, ang letrang E ay laging letrang H ang katumbas.

Simple Substitution Cipher

Ang susunod na uri ng encryption na titignan natin ay ang tinatawag na simple substitution cipher. Sa pamamaraang ito, ang tagapadala at ang tagatanggap ay may pinagkakasunduang permutasyon ng mga letra. Ibig sabihin nito, pipili ng isa sa mga posibleng pagkakahelera ng letra na itutumbas sa normal na pagkakasunud-sunod ng alpabeto. Mas maigi na random ang cipher. Pero pwede rin gumamit ng susing salita sa unahan, saka ihahanay ang mga natitirang letra na wala doon. Halimbawa sa baba, may susing salita na ZIGURAT.

PlainABCDEFGHIJKLMNOPQRSTUVWXYZ
CipherZIGURATBCDEFHJKLMNOPQSVWXY

Gamit ito, ang pagbabago ng orihinal na mensahe ay:

Plaintext: UMATAKE NG MADALING ARAW
Ciphertext: QHZPZER JT HZUZFCJT ZNZV

Para maibalik sa orihinal na mensahe, titignan lang uli ng nakatanggap ang alpabetong cipher, at babaliktarin ang proseso.

Mas mahirap hulaan ang cipher dahil ang dami ng posibilidad ay 26! (26 factorial = 26 x 25 x 24…x 2 x 1). Subalit dahil monoalphabetic din ang cipher na ito, pwede rin itong gamitan ng frequency analysis. Mapapansin agad, aba, ang daming letrang Z sa ciphertext!

Vigenère Cipher

Ang klase ng cipher na ito ay polyalphabetic. Ibig sabihin, nag-iiba iba ang katumbas ng isang letra sa plaintext, papuntang ciphertext.

Ang Vigenère Cipher ay parang kombinasyon ng maraming Caesar Cipher, na mapapakita natin sa halimbawang ito:

  • Gumamit tayo ng isang susing salita: BITAG
  • Kunin ang katumbas na bilang ng mga letra: 2, 9, 20, 1, 7
  • Tatapatan natin ang mga bilang na ito paulit-ulit sa kabuuan ng mensahe, na syang magsasabi kung ilang shift ang gagamitin para mahanap ang katumbas na cipher.
PlaintextUMATAKENGMADALINGARAW
Susing salitaBITAGBITAGBITAGBITAGB
Shift2920172920172920172920172
CiphertextWVUUHMNHHTCMUMPPPUSHY

Babaliktarin lang din ng nakatanggap ng mensahe ang proseso para maibalik mula ciphertext papuntang plaintext.

Kung mapapansin mo, naiiba-iba ang katumbas ng isang letra. Kaya mas mahirap ito hulaan gamit ang frequency analysis. Pero posible pa rin itong mahulaan. Si Friedrich Kasiski at si Charles Babbage ay mga kilalang nakagawa ng solusyon upang mahulaan ang mensaheng gumamit ng Vigenère Cipher.

Kung mapapansin mo rin, habang humihirap hulaan ang mensahe, tumataas ang seguridad ng cipher. Ang epektibong cryptography ay nangangailangan ng sobrang habang panahon para mahulaan, na tila hindi na praktikal itong paghirapan.

One-time Pad

Sa tradisyonal na cryptography, ang One-time pad ang imposibleng mahulaan basta nasusunod ng tama. Ito ay substitution cipher kung saan:

  • Singhaba ng susing salita o cipher ang plaintext
  • Ang susing salita ay random talaga ang pagkakakuha
  • Ang susing salita ay gamit isang beses lamang. Bawat bagong mensahe ay may ibang susing salita na kukunin.

Makikita mong mahirap gamitin ang One-time pad base sa mga dapat sundin. Lalo na kung mahaba ang mensahe. Malamang hindi mo na kayang tandaan ang random na susing salita. Hindi na ito salita, sa totoo lang.

Marami pang mga tradisyonal na cipher, na hindi na natin pag-uusapan. Makikita na sa paglalaro ng alpabeto umiikot ang mga tradisyonal na cipher. Epektibo sila sa panahon ng manu-mano. Sa panahon ng elektrical at mekanical na mga gamit, madali nalang mahulaan ng masamang loob ang mga cipher, maliban sa One-time pad. Lalo naman sa panahon ng mga computer. Kaso, napakahirap, kung hindi imposible, tandaan ang susing salita o cipher para sa One-time pad. Kailangan isulat o gumamit ng mga storage device. Pero problema mo naman ang maingat na pag-aabot nito.

At paano naman ang matipid na pagpapasahan ng mensahe ng mga taong magkalayo? Kailangan natin ng solusyon na hindi mabigat para sa mga tao ang trabaho ng pagpapasahan ng sikreto, at akma sa panahon ng mga computer at Internet.

II. Makabago, o Modern Cryptography

Tumalon na tayo sa makabago o modern cryptography. Upang maging epektibo ang cryptography sa panahon ng mga computer – mabibilis na computer – kailangan natin ng kapangyarihan ng matematika. Sa katunayan, nahuhulaan ang mga nabanggit na tradisyonal na cipher gamit ang matematika. Pero kailangan natin ng mas akmang solusyong matematika para sa panahon ngayon.

Maaaring hatiin sa dalawang (2) klase ang cryptography: symmetric at asymmetric.

  • Symmetric – Sa klaseng ito, ang susi gamit para itago ang mensahe ay sya ring susi para mabunyag ito. Kaya ang 2 partido ay dapat alam ang sikreto. Ang mga tradisyonal na cryptography ay symmetric.
  • Asymmetric – ito ay gumagamit ng pares ng susi: pampubliko (public key) na maaring malaman ng iba, kahit ng mga tsismoso o masamang loob; at pribado (private key) kung saan ang may-ari lang ang dapat makaalam nito. Natatandaan mo yung pinag-usapan natin ukol sa bitcoin wallet at mga transakyon? Ito ang klase ng kriptograpiyang ginagamit sa operasyon nun.

II-A. Symmetric Cryptography

Sa symmetric cryptography, ang susi ay alam dapat ng 2 partido. Kaya ang pagpasa ng kaalaman nito ay dapat sa sikretong paraan. Ang ciphertext ang pinapasa sa walang seguridad o pampublikong daan.

Paglalarawan ng Symmetric Cryptography (Ang e at d ay parehas lang)

Dalawang dibisyon ang meron sa symmetric cryptography: Block Cipher at Stream Cipher. Ang mga block cipher ay nagbabago ng impormasyon sa kada “bloke” or “block” ng plaintext. Ang stream cipher naman ay nagbabago ng impormasyon sa kada isang digit ng plaintext. Unahin nating pag-usapan ang stream cipher.

Stream Cipher

Ang stream cipher ay paraan upang gayahin ang one-time pad sa digital na anyo. Sa halip na gumawa ng isang malaking set, may pamamaraan na ginagamit para ito ay nababago-bago depende sa laki ng impormasyon. Kaya masasabi na ang stream cipher ay nagbabago-bago rin sa oras (time-varying).

Ang pag-encrypt ng mensahe ay ginagawa sa bawat bit. Kumbaga bawat patak ng mensahe ay dumadaan sa encryption.

Halimbawa ng pinaggamitan nito ay video streaming at data sa mga mobile phones.

Exclusive-or

Pag-usapan muna natin ang konsepto ng Exclusive-or, na madalas gamitin sa stream cipher.

Sa lohika (logic), merong tinatawag na connective. Ito ay function kung saan may input na isa o maraming truth values – bale True at False lang naman pwede – at nagbibigay ng isang truth value bilang output.

Isang uri ng connective ay ang OR. Sa OR, kapag ang kahit isa sa mga input ay True, ang output ay True. Kapag lahat ay False, saka lamang magiging False ang output. Tignan natin sa anyo ng talaan kung paano ginagamit ang OR.

ABA OR B
TTT
TFT
FTT
FFF

Ang mga simbolo ng OR ay: | (A | B), (A B), (A B)

Mas madalas gamitin o matagpuan ang OR, kaya natin ito binanggit muna. Pag-usapan naman natin ang Exclusive-or na may daglat na XOR.

Sa XOR, ang output ay True kapag isa lamang sa dalawang kondisyon o input ang True. Kapag parehas na False, o parehas na True ang input, ang output ng XOR ay False. Tignan natin sa talaan na ito:

ABA XOR B
TTF
TFT
FTT
FFF

Ang simbolo ng XOR ay: ⊕

Bago tayo umusad, ipakita natin ang XOR sa anyo ng binary: 0 at 1, na syang gamit sa computer science. Sa binary, ang 1 ay True, at ang 0 ay False.

ABA ⨁ B
110
101
011
000

Simpleng Stream Cipher

Ipakita natin gamit ang maiksing mensahe:

BABA!

Mula sa plaintext, ito ay papalitan natin ng binary:

01000010 01000001 01000010 01000001 00100001

Maari mong tignan dito kung paano nagawa yan: https://www.binaryhexconverter.com/ascii-text-to-binary-converter

Halimbawa, ang keystream na random nakuha ay:

Tama?

Kapag ginawang binary:

01010100 01100001 01101101 01100001 00111111

Pansinin mo ang katumbas na binary ng A at a. Ang MALAKI at maliit na letra ay magkaiba ang katumbas na binary. Magkaiba rin kasi sila ng katumbas na ASCII number.

Ngayon, gamit ang plaintext, keystream at ang konsepto ng exclusive-or, makukuha na natin ang ciphertext:

Plaintext01000010 01000001 01000010 01000001 00100001
XOR⨁ (bawat bit)
Keystream01010100 01100001 01101101 01100001 00111111
Ciphertext00010110 00100000 00101111 00100000 00011110

Ang binary ciphertext na nabuo, kapag naging ASCII ay garalgal lamang. Walang ibig sabihin. Subukan mo ilagay yan sa nabanggit na text converter site kanina, at makikita mong walang kahulugan. Kaya dapat magkaroon ng kopya ng susi ang tagatanggap ng mensahe, para maibalik ang ciphertext sa plaintext. Mula sa anyo na binary maibabalik sa ASCII ito. Sa tagatanggap, baliktad lamang ang posisyon ng Ciphertext at Plaintext sa talaan:

Ciphertext00010110 00100000 00101111 00100000 00011110
XOR⨁ (bawat bit)
Keystream01010100 01100001 01101101 01100001 00111111
Plaintext01000010 01000001 01000010 01000001 00100001

Ito ay simpleng pagpapakita lamang kung paano ginagamit ang Stream Cipher. Mayroon pang mga komplikasyong idinaragdag upang mas mahirap para sa hackers na mahulaan ang mensahe.

Keystream generator

Gamit ang matematika, makakatipid rin tayo sa memorya ng computer. Sa halip na mag-imbak ng pagkarami-raming impormasyon, gagamitan lang ng formula upang makagawa ng susi pag kailangan. Halimbawa nito ang algorithm na gamit para sa keystream generator.

Depende sa haba ng mensahe, ganun din kahaba ang keystream. Ang keystream generator ay gumagamit ng mas maiksing susi sa umpisa, na syang ginagamit para makabuo ng mahabang susi pang encrypt ng plaintext. Ito ay mainam na paraan para makatipid sa memorya. Ang inisyal na susi ay tinatawag na seed (parang buto na pinagsisibulan).

Block Cipher

Sa block cipher ginugrupo ang plaintext sa kada bloke, kaya ang susi ay sinlaki lamang ng bloke. Dahil dito, ang susi ay mas maiksi at mas maliit ang memoryang kinakain.

Pwedeng iba ang haba ng bloke ng plaintext sa susi. Pero dadaan pa rin ito sa operasyon kung saan magtutugma ang haba ng susi at blokeng minamanipula. Kumbaga mayroon lamang inisyal na susi.

Kapag ang huling bloke naman ay kapos sa takdang haba, magdadagdag ng bits sa dulo para sumakto. Ang bits na idadagdag ay base sa operasyon ng block cipher; pwedeng puro 0 lang ang pampuno halimbawa. Ang tawag sa operasyong ito ay padding.

Maraming klase ng implementasyon ng block cipher. Para sa pag-aaral ng konsepto nito, gumamit tayo ng simpleng algorithm lamang.

Simplified Data Encryption Standard (S-DES)

Gamitin natin bilang halimbawa and Simplified Data Encryption Standard (S-DES). Ganito ang S-DES algorithm:

S-DES

Sa paraang ito, ang mensahe ay ginugrupo sa tig 8 bits. Meron namang inisyal na susi na may 10 bits na panggagalingan ng mga bagong susi.

Ang bawat 8 bits ng mensahe ay kukuhanan ng initial permutation (IP). Ang bagong anyong ito ay idadaan sa isang komplikadong function na fK kung saan gamit ang unang subkey K1. Tapos idadaan sa switch function (SW), bago dumaan uli sa isang komplikadong function fK na ikalawang subkey K2 naman ang gamit. At sa huli, gagamit ng inverse permutation IP-1 para mailabas ang 8-bit ciphertext. Bakit subkey ang tawag sa K1 at K2? Dahil may panggagalingan ang mga ito na susi – ang 10-bit key sa umpisa ng ilustrasyon.

Sa matematika, ganito ang equation para gumawa ng ciphertext:

Ciphertext = IP-1(fK2(SW(fK1(IP(plaintext)))))

Kung saan:
K1 = P8(Rotate(P10(key)))
K2 = P8(Rotate(Rotate(P10(key))))

Circular shift vs Logical shift

Sa algorithm ng susi, ang gamit na rotate ay circular shift. Ibang notasyon ang gamit sa pinagbasehan nating materyal ng S-DES na binago ko na dito. Marapat na matandaan ang pagkakaiba ng circular shift sa logical shift para sa ibang bahagi ng pag-aaral natin:

  • Circular shift – usog ang bits, at ang mga nasa dulo ay ipapalit lang sa kabilang dulo
    • Circular left shift (rotate left, ROTL) – usog ang bits pakaliwa, at ang mga natanggal sa kaliwang dulo ay ibabalik sa kanang dulo. Halimbawa: Circular left shift ng 10111010, 3 pwesto pakaliwa, o ROTL3, ay: 11010101
    • Circular right shift (rotate right, ROTR) – usog ang bits pakanan, at ang mga natanggal sa kanang dulo ay ibabalik sa kaliwang dulo. Halimbawa: Circular right shift ng 10111010, o ROTR3, 3 pwesto pakanan ay: 01010111
  • Logical shift – usog ang bits, at ang mga nabakante sa kabilang dulo ay papalitan ng 0.
    • Left shift (<<) – tanggalin ang kaliwang bits at ang nabakanteng pwesto sa kanan ay papalitan ng 0. Halimbawa: Left shift ng 10111010, 3 pwesto pakaliwa, o 10111010 << 3, ay: 11010000
    • Right shift (>>) – tanggalin ang kanang bits at ang nabakanteng pwesto sa kaliwa ay papalitan ng 0. Halimbawa: Right shift ng 10111010, 3 pwesto pakanan, o 10111010 >> 3, ay: 00010111

Ok, game! Sa parehas na mensahe:

BABA!
01000010 01000001 01000010 01000001 00100001

Gamit ang katumbas na bits ng unang letra lamang: 01000010, i encrypt natin ito.

Halimbawa naman ang Susi ay: 1010000010 (10 bits)

Sisimulan natin sa initial permutation (IP), na ang function ay babaguhin ang pagkakasunud-sunod ng bit sa orihinal na bloke ng plaintext. Ito ang inisyal na permutation:

IP (m1,m2,m3,m4,m5,m6,m7,m8) = (m2,m6,m3,m1,m4,m8,m5,m7)

Na mas madaling makita sa pamamagitan ng talaang:

IP

26314857

Kaya ang unang bloke na 01000010 ay magkakaroon ng bagong anyo sunod sa IP: 10000001, na ipinapakita sa talaan sa baba:

1 bloke plaintext01000010
Pagkakasunud-sunod12345678
Pagkakasunud-sunod sa IP26314857
IP ng plaintext10000001

Bago tayo pumunta sa fK, ay intindihin natin ang algorithm ng pagkuha ng susi:

Pagkuha ng susi (Key generation)

Dito naman, may 10-bit key na pag-uumpisahan ng mga subkeys (K1 & K2). Bibigyan ito ng permutasyon na P10 (halintulad sa IP). Hahatiin sa dalawa, gagamit ng rotate left ROTL1, tapos may dadaan sa permutasyon para makuha ang unang 8-bit na susi, K1. Sa kabila naman, gagamit uli ng rotate left ROTR2 at dadaan sa isa nanamang permutasyon para makuha ang ikalawang 8-bit na susi, K2.

Ang function na P10 ay pinapakita sa talaang ito:

P10

35274101986

Mula sa halimbawa nating susi 1010000010, ang P10 (1010000010) = 1000001100. Ito na ang hahatiin sa 2 na tig-5 bits, tapos pagkahati ay gagamitan ng isang rotate left (ROTR1). Kaya ang unang 5 bits ay 10000 —> 00001 at ang makalawa ay 01100 —> 11000. Isusulat natin ang bagong 10 bits na 00001 11000 para sa susunod na hakbang na P8. Bale pipili ng 8 bits na iba nanaman ang permutation, alinsunod sa:

P8

637485109

Ang resulta ay ang unang susi na K1: 10100100.

Kahalintulad ang gagawin para makuha ang K2. Gamit ang resulta ng ROTR1, ay dadaan naman sa ROTR2 ang 5 bits, ibig sabihin, dalawang rotate left ang gagawin. Ang unang 5 bits ay 00001 —> 00100 at ang makalawa ay 11000 —> 00011. Kaya ang bagong 10 bits ay 00100 00011.

Gamit ang parehas na P8, makukuha nating K2: 01000011

Ngayong may mga subkeys na, balikan na natin ang IP ng plaintext na: 10000001. Ito ay idadaan na sa komplikadong function fK na pinapakita sa baba:

Detalye ng fK sa S-DES encryption

Dito naman, hahatiin sa dalawa ang IP ng plaintext. Ang kaliwang 4 bits na 1000 ay irereserba muna. Ang kanang 4 bits na 0001 ay dadaan sa mga prosesong napapaloob sa F. Mag-uumpisa ito sa Expansion/Permutation (E/P) kung saan dapat 8 bits naman ang kalalabasan.

E/P

41232341

Ayusin natin sa ganitong anyo ang E/P para mas madali maintindihan ang mga komplikasyong kasunod:

n4|n1n2|n3
n2|n3n4|n1
1|00|0
0|01|0

Mula dyan gagamitin na ang K1 (10100100) na ka-XOR ng E/P.

1⨁1|0⨁00⨁1|0⨁0
0⨁0|0⨁11⨁0|0⨁0
0|01|0
0|11|0

Ang resultang iyan ay bibigyan natin ng notasyon para sa susunod na hakbang:

p0,0|p0,1p0,2|p0,3
p1,0|p1,1p1,2|p1,3

Ang unang helera ng 4 na bits ay dadaan sa S0 box, na maglalabas ng 2 bits. Ang susunod naman ay dadaan sa S1 box, na maglalabas rin ng 2 bits. Pansin mo, magbabawas nanaman tayo?

S0

0123
01032
13210
20213
33132

S1

0123
00123
12013
23010
32103

Paano naman gagamitin ang S-box? Ang una (p0,0) at ikaapat (p0,3) na bits ay pagduduktungin at babasahin para maging bilang ng row. Ang pinagdugtong na ikalawa (p0,1) at ikatlo (p0,2) naman ang magsisilbing bilang ng column. Kaya sa S0, ang row ay 00 na pag binasa sa decimal ay 0. Ang column naman ay 01 na pag binasa sa decimal ay 1. Kaya ang lalabas sa S0 ay ang row 0, column 1, na 0. Isusulat natin itong binary na may 2 digits: 00.

Sa S1 naman, ang row (p1,0,p1,3) ay 00 kaya 0. Ang column (p1,1,p1,2) ay 11 kaya ito ay 3. Sa row 0, column 3 ng S1, makukuha ang 3. Sa binary na may 2 digits: 11. Kaya ang pinagduktong ng S0 at S1 ay 0011. Ito naman ay dadaan sa P4 na nagsasaad:

P4

2431

Kaya ang lalabas sa P4 ay 0110. Itong P4 gagamitin sa pag XOR ng niriserba natin kaninang 4 na bits sa kaliwa: 1000.

Kaliwang 4 bits ng plaintext IP1000
XOR
Produkto ng P40110
Kaliwang produkto ng fK1110

Iduktong natin sa kaliwang produkto ng fK ang parehas na kanang bits na sinimulan kanina para makuhang ang produkto ng unang fK: 1110 0001. Dadaan ito sa simpleng switch function (SW) na pagpapalitin lamang ang 4 bits sa kaliwa at kanan: 0001 1110

Sa ikalawang fK na operasyon, ang 0001 naman ay irereserba, at ang 1110 ang idadaan muli sa mga operasyon sa F: E/P, XOR gamit ang K2, mga S-box, at P4. Saka nanaman sya ipang XOR sa niriserbang 0001. Makikita sa baba ang mga pangyayari:

Pagdaan sa E/P:

0|11|1
1|10|1

XOR gamit ang K2(01000011):

0⨁0|1⨁11⨁0|1⨁0
1⨁0|1⨁00⨁1|1⨁1
0|01|1
1|11|0

Produkto ng S0: Row 1, Column 1: 2 —> 10
Produkto ng S1: Row 2, Column 3: 0 —> 00
Duktong ng S0 at S1: 1000
Pagdaan sa P4: 0001
0001 XOR 0001: 0000 <— ito ang kaliwang 4 bits na ilalabas ng ikalawang fK.

Ang kanang 4 bits ay ang kaliwang produkto kanina ng unang fK: 1110. Kaya ang lalabas na 8 bits sa ikalawanag fK ay: 0000 1110.

At ang pinakahuling hakbang ay ang inverse permutation o IP-1. Ang ibig sabihin ng inverse permutation ay bawat numero at ang bilang ng posisyon nito ay pinagpalit. Kung saan babalik sa normal na ayos kapag ginamitan ng IP-1(IP(X)) = X. Pakita natin uli ang IP sa simula ng S-DES:

IP26314857
Posisyon12345678
IP-141357286

Gamit ang IP-1 sa 00001110, ang ciphertext na makukuha ay: 00011001. Pag sinubukan mo uli ito gawing ASCII, garalgal lamang ang makukuha.

Ang haba ano? Subukan natin ibalik sa plaintext ito.

Ciphertext: 00011001
IP: 00001110
fK gamit ang K2:
Reserba ang 0000, gamitin ang 1110
E/P:

0|11|1
1|10|1

XOR gamit ang K2 (01000011):

0|01|1
1|11|0

Produkto ng S0: Row 1, Column 1: 2 -> 10
Produkto ng S1: Row 2, Column 3: 0 -> 00
Duktong ng S0 at S1: 1000
Pagdaan sa P4: 0001
0000 XOR 0001: 0001
Labas ng fK: 0001 1110
Switch: 1110 0001
fK gamit ang K1:
Reserba ang 1110, gamitin ang 0001
E/P:

1|00|0
0|01|0

XOR gamit ang K1 (10100100):

0|01|0
0|11|0

Produkto ng S0: Row 0, Column 1: 0 -> 00
Produkto ng S1: Row 0, Column 3: 3 -> 11
Duktong ng S0 at S1: 0011
Pagdaan sa P4: 0110
1110 XOR 0110: 1000
Labas ng fK: 1000 0001
IP-1: 01000010
ASCII ng plaintext: B

Isang letra palang yan, komplikado na. At mula sa halimbawang iyan, isipin mo nalang gaano ka komplikado kapag mas mahaba ang susi at bloke. Sa DES, gumagamit ng 64 bits na laki ng bloke, at 56 bits na susi, kung saan 48 bits naman ang sub-key. Ipapaubaya na talaga yan sa kompyuter.

Ganun pa man, ang DES ay hindi na tinuturing na sapat ang seguridad sa panahon ngayon. Kaya naman napalitan na ito ng Advanced Encryption Standard (AES). Dito, ang laki ng bloke ay 128 bits. Ang susi naman ay pwedeng 128, 192 o 256 bits ang laki!

At dito natin ititigil ang Symmetric Cryptography. Hingang malalim.

II-B. Asymmetric Cryptography

Ngayon naman ay ipapakilala ang isang simple at eleganteng konsepto na makikita sa asymmetric cryptography, na tinatawag ring public-key cryptography. Nabanggit nang bahagya sa ikalawang kabanata ang konsepto nito nung pinag-uusapan ang digital na pitaka.

Ang public-key cryptography ay gumagamit ng 2 susi: pribado (private) at pampubliko (public). Ang public key ay maaaring ipadala sa hindi sikretong daan, tulad ng ciphertext. At ang private key ay nananatili sa isang user lamang.

Paglalarawan ng Asymmetric Cryptography (Ang e at d ay magkaiba)

Gagamitin ng magbibigay (A) ng mensahe ang public key (e) ng pagbibigyan (B) nya, upang mag-encrypt. Ang ciphertext na ipapadala nya ay made-decrypt ng tagatanggap gamit ang private key (d) nito. Ganun din kung kabaliktaran (B—>A) ang mangyayari.

Ang kalamangan ng pamamaraang ito, ay ang isang user ay merong naitatagong susi na kanya lamang. Para maging epektibo, dapat ang relasyon ng public at private key ay: madaling kunin ang public key mula sa private key. Pero, mahirap makuha ang private key mula sa public key. Nasa may-ari ng private key nakasalalay ang pag-iingat nito. Dahil pag ito nawala, sya mismo ay hindi made-decrypt ang ciphertext.

Maihahalintulad ito sa isang baul at lock. Gamit ang baul at nakabukas na lock ni B, ilalagay ni A ang mensahe sa loob, at isasarado, pati ang lock. Kumbaga ang public key ay ang kombinasyon ng bukas na baul at lock. Ang ciphertext ay ang box na nakakandado. At ang susi ni B ang private key. Pagkasara, hindi na mabubuksan ni A ang lock dahil nakay B lamang ang susi.

At magagawa ang konsepto na ito syempre, gamit ang kapangyarihan ng matematika. Marami sa mga public-key cryptography ay base sa konsepto ng integer factorization problem. Ito ang paghahanap ng prime factors ng isang integer. Halimbawa, ang numerong 65 ay may prime factors na 5 x 13. Sa 98: 2 x 72. Walang shortcut sa pagkuha nito. Kailangan mo lang subukan talaga ang mga posibilidad. Habang lumalaki ang numero, mas humihirap, lalo na kung malalaking prime numbers din ang factors ng isang integer.

Isang popular na public-key cipher ay ang RSA. Madalas itong gamit sa mga internet browser at websites sa kombinasyon ng iba pang cryptography. Dahil na rin nagagamit sa digital signatures ang RSA.

Ang RSA ay ipinangalan kina R. Rivest, A. Shamir at L. Adleman. Para matutukan natin ito, maging pamilyar muna sa mga susunod na konsepto ng matematika:

Konting Number Theory

Konti ba yan?

Integer – Alam mo naman na siguro ito. Basta whole number na pwedeng positive o negative, at 0. Ang set ng integers {…, -3, -2, -1, 0, 1, 2, 3, … } ay ℤ.

Division – maghain tayo ng mga notasyon ukol dito.

  • Kapag ang b ay nahahati ng sakto ang a, masasabing “b divides a,” na pwedeng isulat na b|a. Isang paraan lang ito ng pagsasabi na ang b ay divisor ng a, o kaya b ay factor ng a.
  • Division algorithm for integers: kapag ang a ay hahatiin ng b, may makukuha tayong quotient q, at kapag di sakto, may remainder r. Kung saan ang relasyong ng a, b, q & r ay maipapakita na: a = qb + r ;
  • Ang remainder na r ay maaring irepresenta na a mod b
  • Ang quotient q naman ay a div b
  • Halimbawa: a = 83, b = 19; ang q = 4 = 83 div 19, at r = 7 = 83 mod 19
  • Greatest common divisor (gcd): ito ang pinakamalaking divisor na pareho sa dalawang integer. Halimbawa, dalawang integer, 16 at 24, may mga factors o divisors sila na parehas: {±1, ±2, ±4, ±8}; makikita na ang gcd(16,24) = 8

Relatively prime – Ang dalawang integers a at b ay sinasabing relatively prime (o coprime) kung gcd (a,b) = 1, o wala silang common divisor maliban sa 1. Tandaan na iba ang prime number sa relatively prime. Halimbawa, ang 7 at 8 ay relatively prime dahil ang gcd(7,8) = 1. Pero alam natin na ang 7 ay prime, samantalang ang 8 ay composite na may prime factorization na 23.

Euler phi function o Euler totient function – ni rerepresenta ng ɸ. Para sa isang integer n, ang ɸ(n) ay ang dami ng integers mula 1 pataas, bago mag n, na relatively prime sa n. Halimbawa, ang mga relatively prime sa 9 ay: {1, 2, 4, 5, 7, 8}. Kaya ɸ(9) = 6. May mga katangian (properties) ang Euler phi function:

  • Kung ang p ay prime, ang ɸ(p) = p – 1. Halimbawa, ang 7: dahil prime number ito, lahat ng integers bago sya ay relatively prime sa kanya: {1,2,3,4,5,6}. Ito ay mahalagang katangian na nagagamit sa public key cryptography. Makikita mo mamaya (o bukas, bala ka).
  • Ang Euler phi function ay multiplicative. Sa dalawang relatively prime m at n, gcd(m,n) = 1, ang ɸ(mn) = ɸ(m) * ɸ(n). Mula sa kaninang nabanggit, gcd(7,8) = 1. Ang ɸ(7) = 6; samantalang ang ɸ(8) = 4: {1,3,5,7}. Mula dito ang ɸ(56) = ɸ(7) * ɸ(8) = 6 * 4 = 24. Kumpirmahin natin. Ang mga relatively prime sa 56 ay: {1, 3, 5, 9, 11, 13, 15, 17, 19, 23, 25, 27, 29, 31, 33, 37, 39, 41, 43, 45, 47, 51, 53, 55} – 24 na integers.
  • Kung ang n = p1e1p2e2pkek ay ang prime factorization ng n, susunod na:

Integers modulo n

  • Ang n ay isang integer.
  • Kung ang a at b ay integers, masasabing “a is congruent to b modulo n”, na nasusulat na ab (mod n), kung nadi-divide ng n ang (a – b). Ang integer na n ay tinatawag na modulus ng congruence.
  • Halimbawa, 83 ≡ 7 (mod 19), dahil 83 – 7 = 4 * 19; pansinin ang pagkakaiba ng representasyon ng congruence mula sa nabanggit kanina na representasyon ng remainder na 7 = 83 mod 19. Magkabaliktad ng pwesto ang 83 at 7, at napapaloob sa parentheses ang (mod 19) kapag congruence. Pagtutuunan ng pansin maya-maya ang congruence na napapaloob ang remainder sa equation. Pero wag ka malilito kapag hindi iyon tumugma sa ibang congruences na makikita mo. Halimbawa, pag pinagbaliktad natin ang pwesto ng 83 at 7: 7 ≡ 83 (mod 19), tama pa rin ito dahil 7 – 83 = -4 * 19. O kaya naman 249 ≡ 21 (mod 19), iisipin mo ang remainder kapag hinati ng 19 ang 249 ay 2. Pero ang congruence na ito ay tama pa rin dahil 249 – 21 = 12 * 19. Maiintindihan mo pa dahil sa susunod.
  • Ang congruence ay may mga katangian na:
  • ab (mod n) if and only if ang a at b ay may parehas na remainder kapag hinati ng n.
  • (Reflexivity) aa (mod n)
  • (Symmetry) If ab (mod n) then ba (mod n)
  • (Transitivity) If ab (mod n) and bc (mod n), then ac (mod n)
  • If aa1 (mod n) and bb1 (mod n), then a + ba1 + b1 (mod n) and aba1b1 (mod n)
  • May tinatawag na equivalence class na syang set ng integers na pare-parehas ng least residue sa isang modulus n. Gamit ang division algorithm: a = qn + r . Sa iba-ibang value ng a, mayroon remainder mula 0 – (n-1). Ang remainder r ay ang least residue ng a modulo n. Kaya ang r ay magagamit na representasyon ng equivalence class.
  • Ang integers modulo n, na may simbolong ℤn, ay ang set ng equivalence class ng integers {0, 1, 2, …, n – 1}. Ang mga operasyong addition, subtraction at multiplication ay ginagawa modulo n.
  • Halimbawa, ang ℤ19 = {0, 1, 2, …, 18}. Sa ℤ19, 11 + 12 = 4, kasi 23 ≡ 4 (mod 19). Masasabing ang 23 ay nasa equivalence class ng 4. Sa parehas na konsepto, ang 11 * 12 = 18 sa ℤ19, dahil 132 ≡ 18 (mod 19), o ang 132 ay nasa equivalence class ng 18.
  • Kapag sa loob ng ℤn ay may integers a at x kung saan ax ≡ 1 (mod n), masasabing ang multiplicative inverse ng a modulo n ay x. Halimbawa, ang 4 at 5 sa ℤ19 ay invertible dahil 45 ≡ 1 (mod 19).
  • Mayrong group sa loob ng ℤn na tinatawag na multiplicative group na may notasyong ℤ*n. Ang laman nito ay ang mga elements na relatively prime/coprime sa n.
  • Ang order ng ℤn ay |ℤn| o ang bilang ng elements nito. Kaya kung ano ang value ng Euler phi function ɸ(n), iyon ang order ng ℤ*n.

Euler’s theorem:

  • Kapag ang integer a sa ℤn ay relatively prime sa n o parte ng ℤ*n, susunod na: aɸ(n) ≡ 1 (mod n)
  • Kapag ang n ay produkto ng 2 magkaibang (distinct) primes, at kapag rs (mod ɸ(n)), susunod na aras (mod n) para sa lahat ng integers a.

Fermat’s theorem: Sa isang prime p

  • Kung gcd(a,p) = 1, susunod na ap-1 ≡ 1 (mod p)
  • Kung rs (mod p-1), susunod na aras (mod p) para sa lahat ng integers a.
  • Saka, apa (mod p) para sa lahat ng integers a.

Okay, yan na muna. Konti ba yan? Oo konti pa yan. Mula sa mga konseptong nalatag, pag-usapan na natin ang RSA.

RSA

Ang RSA Problem ay ganito:

  • Nabibigay ang mga sumusunod:
    • May isang integer n, na produkto ng 2 distinct primes p at q
    • Isang positive integer e, kung saan ang gcd(e, (p-1)(q-1)) = 1 (base sa Euler phi function ito: gcd(e, ɸ(n)), at
    • Integer c
  • Humanap ng integer m, kung saan mec (mod n)

Ang mga kondisyon sa kung ano dapat ang n at e, ay mahalaga para masiguro na ang bawat integer c ∈ {0, 1, 2, …, n-1} ay may katumbas lamang na isang m ∈ {0, 1, 2, …, n-1}, na magpapatotoo sa mec (mod n). Sa kontexto ng cryptography, importante ito dahil ang ciphertext na may katumbas na numerong c, ay dapat mayroon lamang isang numerong katumbas na m, na syang representasyon ng plaintext/mensahe.

Dalawang algorithm ang pagdadaanan sa paggamit ng RSA: (1) key generation at (2) encryption.

Key generation (paggawa ng susi):
Bawat myembro ng komunikasyon ay gagawa ng kanilang RSA public key at private key. Para magawa ito:

  1. Kumuha (random generation) ng 2 malaking distinct primes p at q.
  2. Kunin ang n = pq at ɸ = (p-1)(q-1)
  3. Pumili ng random na integer e, 1 < e < ɸ, kung saan gcd(e,ɸ) = 1.
  4. Kalkulahin ang unique integer na d, 1 < d < ɸ, kung saan ed ≡ 1 (mod ɸ). (Bale ang d ay multiplicative inverse ng e modulo ɸ)
  5. Ang public key ay (n, e); at ang private key ay d.

RSA Public-key encryption

  1. Encryption:
    • Kunin ang public key (n, e) ng pagbibigyan ng mensahe.
    • Irepresenta ang mensahe sa anyong integer m na napapaloob sa pagitan ng [0, n-1].
    • Kalkulahin ang c = me mod n.
    • Ipadala ang ciphertext c.
  2. Decryption: Para makuha ng tagatanggap ang m mula sa c, gagamitin nya ang kanyang private key d sa komputasyong: m = cd mod n.

Gumagana ito dahil sa Euler at Fermat’s theorem.

  • Dahil ang ed ≡ 1 (mod ɸ), merong integer k na kung saan ed = 1 + .
  • Mula sa Fermat’s theorem: mp-1 ≡ 1 (mod p)
  • I-raise ang magkabilang panig ng congruence sa k(q-1) at i-multiply ng m ang parehas na panig: m1+k(p-1)(q-1)m (mod p)
  • Makikita sa exponent ng m sa kaliwa na ito ay katumbas ng 1 + = ed. Kaya, medm (mod p)
  • Gayun din ang kalalabasan para sa modulus q, medm (mod q)
  • At dahil ang p at q ay distinct primes, mula sa Euler’s theorem, sumusunod na medm (mod n)
  • At sa wakas, cd ≡ (me)dm (mod n)

Ang galing noh? Para sa impormasyon ng kompyuter, may paraan dapat na irepresenta ang mensahe sa isang ingeter m. Hindi na natin palalawakin dito kung pano yun gagawin.

Ngayon at nakuha mo na ang konsepto, babanggitin lang saglit ang isang paraan ng assymetric cryptography na gamit sa bitcoin. Sa pagkuha ng public key mula sa private key, gumagamit ng Elliptic Curve Digital Signature Algorithm. Digital signature nanaman – may pag-uusapan muna tayong konsepto bago natin ito balikan.

II-C. Cryptographic Hash Functions

Ang susunod naman na maigi nating intindihin ay ang Cryptographic Hash Functions.

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.

II-D Digital Signatures (Digital na Lagda)

Gamit ang kaalaman natin sa public key cryptography at hash functions, maiging pag-usapan na ang digital signatures.

Ang digital signature ay isang numero na nakuha mula sa private key at sa laman ng mensaheng pinipirmahan. Kumbaga, ginamit ang mga katumbas na numero ng private key at mensahe sa kalkulasyon para makuha ang digital signature. Dahil sangkap ang mensahe, ang digital signature ay iba-iba ang halaga sa bawat mensahe. At sa paggamit ng private key, markado ang mensahe ng orihinal na may-ari.

Ang RSA ay maaaring gamitin direkta kung saan ang mensahe ay nakapaloob na rin sa digital signature. Pero lalaktawan natin iyon para mailarawan ang gamit ng hash function sa kombinasyon ng RSA.

Makikita sa ilutsrasyon sa baba ang prosesong sumusunod sa PKCS#1. Ang PKCS ay Public-key Cryptography Standards at ang #1 ay ang seksyon nito na naglalatag ng RSA Encryption Standard.

Proseso ng paggawa at pagberipika ng signature alinsunod sa PKCS #1

Ang mensahe ay dumaraan sa message hashing, halimbawa, ang SHA-256. Sa message digest encoding at data block formatting, may susunding ayos ng data na magreresulta sa anyong octet string. Ang octet string ay representasyon ng data na nagpapakitang tig-8 bits ang hati. Laktawan na natin ang detalye nito. Tapos, dadaan sa Octet string-to-integer conversion. Ito ay dahil ang susunod na hakbang ay ang RSA, na alam na nating operasyong matematika. Kaya integer ang kailangang input.

Halimbawa, ang integer na ito ay m. Para makuha ang signature s, gagamitin ang: s = md mod n

At ang makukuhang integer na s ay dadaan sa integer-to-octet string conversion, at iyon ang digital signature na ipapadala.

Sa verification, syempre kabaliktaran lang ang mangyayari. Tutukan lang natin ang RSA computation. Para makuha ang m, kakalkulahin ang: m = se mod n

Makikita mo sa ilustrasyon na may iba-ibang beripikasyong magaganap sa mga hakbang. Laktawan na muna natin ang mga kaugnay sa anyo ng data/formatting. Basta sa bandang huli, dapat ay makikilala ng tagatanggap ang bahagi ng octet string na syang hash ng orihinal na mensahe. Ang huling verification ay kapag ang hash na nahiwalay mo sa signature ay parehas ng hash ng mensahe na natanggap mo.

Tandaan na sa ilustrasyong ito, parehas na pinadala ang signature at message. Hindi naka-encrypt o naka ciphertext ang mensahe. Hindi na natin pag-uusapan ang scheme kung saan may digital signature na, may encryption pa sa mensahe.

Matatandaan na sa nauna nating usapan tungkol sa RSA, ang mensahe ay ini-encrypt gamit ang public key (n,e) ng pagbibigyan. Gagamitin ng tagatanggap ang kanyang private key (d) para makuha ang mensahe.

Pagbigay ng encrypted message ni A kay B, at pag decrypt ni B:
c = me mod n (e ni B ang gamit)
m = cd mod n (d ni B ang gamit)

Kabaliktaran sa digital signature: ang private key (d) ng pinanggalingan ang gagamitin para gumawa ng lagda, at ang public key (n,e) ng pinanggalingan ang gagamitin ng tagatanggap para makuha kung tama ang mensahe.

Pagbigay ng signature ni A kay B, at pag verify ni B:
s = md mod n (d ni A ang gamit)
m = se mod n (e ni A ang gamit)

Sa kontexto ng Bitcoin, ang blockchain ay bukas para makita ng network. Kaya, ang mga “mensahe” ay hindi sikreto. Ang mensahe ay ang transaksyon na nagsasaad kung magkano ang ibinigay na Bitcoin mula sa isang address papunta sa iba. Kaya ang signature algorithm lang ang kailangan gamitin, hindi encryption ng mensahe. At sa paksang ito, ang susunod na seksyon ang tutunton sa talagang digital signature algorithm na gamit sa Bitcoin.

II-E Discrete Logarithm, Elliptic Curve at ang Elliptic Curve Digital Signature Algorithm

Ang elliptic curve digital signature algorithm (ECDSA) ay hango sa elliptic curve cryptography, na syempre galing sa elliptic curve mathematics. Subalit wala ito halos kinalaman sa ellipse. Ha? Maglatag muna tayo uli ng mga konsepto ng matematika.

Discrete Logarithm Problem

Nabanggit sa umpisa ng usapan sa public-key cryptography na base sa integer factorization problem ang mga gamit na iskema. May isa pang problema na pwedeng gawan ng mahirap na halimbawa, na syang sinasamantala sa kriptograpiya: Discrete logarithm problem (DLP).

Sa logarithm na ipinapakitang ganito: logPQ = k (logarithm of Q to the base P is equal to k), ang Q ay ang numero na resulta kapag ang P ay ini-multiply sa sarili nya ng k na beses. Q = PxPxP…xP (k na beses). Kaya ang logarithm ay kabaliktaran ng exponential equation: Pk = Q (P to the power of k is equal to Q). Naaalala mo pa ba ito?

Ang DLP ay ang paghahanap ng k, kapag ang alam na impormasyon ay ang Q at P. Mahirap itong gawin sa malalaking numero dahil trial-and-error ang paraan.

Ngayon, sa discrete logarithm, ang multiplication ay maaring ibang operasyon, gaya ng addition ng integers sa isang cyclic group. Kaya ang k, sa halip na exponent o power, ay magiging numero na kung ilang beses ginawa ang addition ng P sa sarili nito.

Q = P+P+P+…+P (k na beses)
Q = [k]P

Teka, mas madali ang addition sa multiplication, hindi ba? Sa nakagawiang arithmetic, tama ka dyan. Pero ang konsepto ay makahanap ng operasyon na mahirap gawin. Sa grupong pinili sa elliptic curve cryptography, ang tinatawag na ‘addition’ ay komplikado ang pamamaraan.

Cyclic Group
Ano nga ba ang cyclic group? Mainam na intindihin natin ang mga konsepto patungo rito.

Kapag sinabing group (G, *), tumutukoy ito sa isang set G na may operasyong * na sumusunod sa mga axioms na ito:

  • Ang operasyon ng group ay associative: a * (b * c) = (a * b) * c sa lahat ng a,b,cG.
  • May isang identity element, 1 ∈ G, kung saan a * 1 = 1 * a = a sa lahat ng a ∈ G.
  • Sa bawat aG, mayroong a-1 ∈ G, tinatawag na inverse of a, kung saan a * a-1 = a-1 * a = 1.

At karagdagang katangian: ang G ay abelian o commutative, kapag:

  • a * b = b * a sa lahat ng a, bG.

Ang inilarawang group ay multiplicative ang ginamit na operasayon. Maaring addition ang operasyon nito, (G, +), bale additive group. Sa lagay na yun, ang identity element ay 0, at ang inverse ng a ay -a.

Ang group ay finite kapag ang bilang ng elements sa G ay may hangganan. Ang bilang ng elements sa isang group, |G| ay tinatawag na order nito.

Naaalala mo ang integers modulo nn na pinag-usapan sa bandang umpisa ng asymmetric cryptography? Ang operasyon nito na addition modulo n ay nakakabuo ng group. Ang identity element ay ang 0, at ang inverse ng a ay kung anong x na kapag dinagdag sa a ay magiging congruent sa 0 (modulo n): a + x ≡ 0 (mod n). Pero ang multiplication modulo n naman nito ay hindi group. Dahil hindi lahat ng element ay may multiplicative inverse (paalala: ax ≡ 1 (mod n)).

Pero, pero, ang multiplicative group na may notasyong ito: ℤ*n (na matatandaan eh, naglalaman ng mga elements na relatively prime/coprime sa n), ay group, dahil lahat ng elements nito ay may multiplicative inverse at naglalaman ng identity element na 1 (mod n). At gaya ng nabanggit na sa bandang taas, ang ℤ*n ay may order na |ℤ*n| = ɸ(n) (Euler phi function).

Ngayon, ano na ang cyclic group? Ito ay kapag ang G ay may element ∈ G, kung saan bawat b ∈ G may katumbas na integer i na magpapatotoo sa: b = i. Ang ay tinatawag na generator ng G.

Gamitin uli nating halimbawa ang multiplicative group na ℤ*n. Ang ℤ*13 ay may order na 12. Isa sa mga generators nito ay = 2. Nakuha ito dahil sa multiplicative group, malalamang may generator ito kapag may element syang ɸ(n) ≡ 1 (mod n). Sa halimbawa, 212 ≡ 1 (mod 13). At tunay ngang cyclic ang group na ℤ*13 dahil ang operasyong 2i mod 13 ay magreresulta sa b na napapaloob din sa group. Ito ang talaan:

i123456789101112
2i mod 13248361211951071

Mula 1-12 na i, nagkaroon ng unique na b, na isa sa mga elements ng ℤ*13. Para mas maimahe mo ang cyclic, ituring na kapag lumagpas ka na sa i = 12, mula 13-24, ang halaga ng 2i mod 13 ay uulit base sa pagkakasunud-sunod ng nasa talaan.

Ihalintulad natin ang operasyon sa Q = [k]P. Nabanggit sa taas na ang ℤn (walang asterisk) sa operasyong addition ay group, at sa + ay mapapakita mo na cyclic nga ang ℤn. Ang operasyon ay: b = [i] mod n. Na sa ℤ13 ay b = [i]2 mod 13. Ang [i] ay kung Ilang beses nag +2. (Maliban sa 0, lahat ng element sa ℤ13 ay generator, kaya pwede mo subukan sa iba.)

[i]0123456789101112
[i]2 mod 130246810121357911

Kaya sa Q = [k]P? Ang P ay ang generator ng cyclic group kung saan pinagmulan ang ibang elemento. Ilang beses, yun ang susi. Mapa multiplication o addition, basta ang pagdetermina ng ilang beses ito ginawa ang importante. At gusto nating makahanap ng mga cyclic group na mahirap atakihin ng kalaban, dahil nga komplikado ang operasyon, lalo na kung pabaliktad. Napakadali ng halimbawang pinakita. Paano tayo makakagawa ng ‘addition’ na mahirap?

Elliptic Curve

Ano ba ang itsura ng P kapag gumamit tayo ng elliptic curve? Ito ay hindi lang numero, kundi point sa elliptic curve. Ang operasyon para makuha ang susunod na point ay hindi lang basta-bastang addition ng numero. Kailangan, matunton pa ang posisyon ng susunod na point sa curve. Sa kontexto ng Elliptic Curves, and multiplication ay addition, ang squaring ay doubling, at ang division ay subtraction.

Weierstrass Curve

Ang napiling elliptic curve sa paggawa ng pares ng private at public key sa mga wallet ng bitcoin ay isang Weierstrass (mula sa apelyido ng mathematician na si Karl Weierstraß). Upang maging tiyak, isang Short Weierstrass curve ang gamit.

Ang general form ng Weierstrass Curve ay:
E: y2 + a1xy + a3y = x3 + a2x2 + a4x + a6

Sa mga tamang kondisyon, ito ay magagawang Short Weierstrass form sa anyong:
E: y2 = x3 + c4x + c6

Hindi na natin idedetalye kung paano ito nagawa. Basta sa matematika, may konsepto ng isomorphism. Kung saan, may pagmamapa mula sa isang function, object, set, atbp. papunta sa isa pa. At isomorphic sila kapag napapanatili ang istraktura, o ang relasyon ng mga elements. Mula Weierstrass papuntang Short Weierstrass, ang hugis ng curve ay nananatili.

Gamitin natin sa halip ang a at b bilang notasyon ng coefficients:
E: y2 = x3 + ax + b

Ang ilustrasyong susunod ay isang halimbawa ng itsura ng elliptic curve na naka Short Weierstrass form.

Kapiraso ng elliptic curve na Short Weierstrass

Operasyon sa Elliptic Curve

Sa elliptic curve, E, may relasyon ang mga points kung saan: Kapag ang P, Q, R ay nasa linya, ang P + Q + R = ∞

Ang ∞ ay ang point at infinity, na syang identity o neutral element ng group. Isipin mo itong point na syang matutunton sa dulung-dulo pataas o pababa kapag dumeretso ka sa isang linyang x = c (anumang constant), parallel sa y-axis.

Tumatayo rin syang 0 sa operasyon ng addition kaya sya ang neutral/identity element. Espesyal na kaso ito na ginawa para sa Weierstrass curve.

Halimbawa, ang kabaliktaran ng P ay -P, kung saan ang negative ng point na (x,y), ay -(x,y) = (x,-y). Bale kabaliktaran sa kabila ng x-axis.

Pagtunton ng negative ng point sa Weierstrass curve

Kaya kapag kinonekta ang P sa -P, ang linya ay parallel sa y-axis at tumuturo sa kataas-taasan at kailalim-ilaliman. Ito ay addition na ang sum ay equal sa neutral element.

P + -P = ∞

Ang inversion ng point na may coordinates (x,y) ay kung saan -(x,y) = (x,-y)

Punta naman tayo sa addition ng 2 points kung saan P Q. Para makuha ang ikatlong point na R, ikonekta ang P at Q, at ang susunod na point na tatamaan sa curve ang R. Kunin ang kabaliktaran nito sa kabila ng x-axis para matunton ang -R. Kaya,

P + Q + R = -R + R = (P + Q) + -(P + Q) = ∞ ; na inilalarawan sa susunod na graph:

Addition ng 2 points sa Weierstrass curve

Kaya ang R ay -(P + Q) o ang kabalitaran ng sum ng 2 points. Kaya kailangan kunin ang -R na syang sagot sa operasyon.

Para makuha ito gamit ang komputasyon, babalikan natin ang kaalaman sa algebra. Ang slope ng linya ay may formula na:

ƛ = (yP – yQ)/(xP – xQ)

Makukuha natin ang susunod na coordinates kasi kapag hinabaan lang ang linya, ang slope ƛ gamit ang coordinates ng R ay dapat parehas lang. Ang xR ay:

xR = ƛ2xP – xQ

At sa halip na yR ang kunin natin, baliktarin na agad ang sign para –yR na ang halaga:

yR = ƛ(xP – xR) – xP

Paano naman ang doubling o ang pag-add ng P sa sarili nito?

Doubling ng point sa Weierstrass curve

Ang P ay ituturing na tangent ng linyang iguguhit, at ang susunod na point na tatamaan sa E ay ang R. Kaya 2P + R = -R + R = 2P + -2P = ∞

Sa formulas, gagamitin natin ang slope ƛ ng isang tangent line. At ang pagpapanatili ng slope kapag hinabaan ang linya hanggang R.

ƛ = (3xP2 + a)/(2yP)
xR = (ƛ2 – 2xP)
yR = ƛ(xP – xR) – xP

Naimahe mo na, na hindi basta-basta ang operasyon sa elliptic curve? Kaya kapag malaki na ang mga numerong pinag-uusapan, magastos ang komputasyon lalo na sa pagbabaliktad ng operasyon. Iyan naman ang kailangan para sa cyptography.

Balikan natin ito:
Q = [k]P

Nalalaman ang P na syang generator, alam din kung ano ang iskemang gamit, halimbawa nga ang ECDSA. Ang Q ang tumatayong public key, at ang [k] ang sikreto – private key. Dahil iyan ang mahirap kalkulahin pabalik.

Maging mas tiyak pa tayo sa kondisyon.

Fields at Finite Fields
Mabilisang depinisyon lang. Ang Field ay isang set F na may 2 operasyon, addition at multiplication: (F, +, *). May mga axiom kaparehas ng nabanggit sa Group ito: Associativity, Commutativity, Additive at Mutliplicative na Identity elements at Inverses. At karagdagang Distributivity ng multiplication sa addition: a * (b + c) = (a * b) + (a * c)

Ang Finite Field F ay isang field na may hangganan ang bilang ng elements. At gaya sa group, order ang tawag sa bilang ng elements ng finite field. Isa sa mahalagang katangian ng finite field, ay meron itong pm elements. Ang p ay isang prime at ang m ≥ 1.

Nakita natin makailang beses na ang espesyal na papel ng prime numbers sa cryptography.

Sa epektibong gamit ng elliptic curve cryptography, pipili lang tayo ng subset ng curve na limitado ng finite field. Ang group G na pipiliin ay subset ng elliptic curve E na nasa finite field F, na may prime order p (Fp). At ang operasyon ay addition (+).

GE(Fp, +)

At magagawa natin ang limitasyon sa finite field kapag ang elliptic curve equation ay nakapares sa modulo arithmetic ng isang prime number.

E: y2 ≡ x3 + ax + b (mod p)

Ngayon, tandaan na sa elliptic curve, gumagamit tayo ng point bilang generator. Kaya ang order (dami ng points) na matutunton ng generator ay hindi nangangahulugang parehas ng prime order ng finite field.

|E(Fp)| ≠ p
(May mga anomalous curves na pwede magparehas ito, pero iniiwasan ang mga ganun.)

Punta na tayo sa gamit sa Bitcoin.

secp256k1

Mula sa NIST, may mga nirekomendang elliptic curves na pwedeng gamitin sa ECDSA. Lahat sila ay naka Short Weierstrass form. Isa sa mga yun ay ang gamit sa bitcoin: secp256k1. Ang palayaw na ito ay hango sa:
Standards for Efficient Cryptography – sec
Parameters over Fpp
256 bits na haba ng p – 256
Koblitz curve – k
Sequence number – 1

Pasensya na pero gagamit tayo ng notasyon mula sa NIST, na baka ikalito mo dahil iba ang representasyon sa mga naunang diskusyon.

May 6 na parameters na konsiderasyon sa secp256k1.

T = (p, a, b, G, n, h)

p = prime number na bilang ng elements sa Fp
a, b = coefficients ng short Weierstrass curve, kung saan a, bFp
G = base point (xG, yG) sa elliptic curve E(Fp) – na syang generator ng subgroup
n = order ng G, o dami ng elements sa subgroup na generated by G (dami ng points sa curve na generated ng G)
h = cofactor kung saan h = #E(Fp)/n

Tala: (#E(Fp) ay parehas sa |E(Fp)|)

Ilagay din natin ang mga napiling halaga ng mga parameters para maimahe mo na mahirap itong maimahe dahil sa laki! Ang mga numero ay naka hexadecimal.

pFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F
= 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1
a00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
b00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000007
GCompressed (x-coordinate lang ang nakalagay)
02 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Uncompressed
04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8
nFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
h01

Ganito ang elliptic curve equation:
E: y2 ≡ x3 + 7 (mod (2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1))

Sa haba ng dinaanan natin, ang konsepto ay babalik rin lang sa:

Q = [k]P

Ang [k] ang sikreto o private key, na syang katumbas ng dami ng point additions ng P. Ang P ay alam ng lahat (ito ang G sa kalalatag lang na deskripsyon ng secp256k1). At ang Q ang public key. Ganun lang din, pero malakihang halaga ang usapan.

Elliptic Curve Digital Signature Algorithm (ECDSA)

Ahay! So paano na ba ang Elliptic Curve Digital Signature Algorithm (ECDSA)?!

Ang ECDSA ay hango sa mekanismo ng Diffie-Hellman Key exchange. Ito ang nag-umpisa ng konsepto ng public-key cryptography, nauna pa sa RSA.

Balik tayo sa paggamit ng variables na mas karaniwan sa literatura ha, hindi yung sa notasyon ng NIST. Makikita sa susunod na talaan ang mga parameters bago pa magkatransaksyon ang 2 partido: Alicia at Bob.

AliciaParametersBob
nFinite Field order (alam ng lahat)n
PGenerator (alam ng lahat)P
aPrivate keyb
QA = aPPublic key (malalaman ng nakikipagtransaksyon)QB = bP

Nabanggit nung nakaraan, sa seksyon ng Digital Signatures, na ang mensahe sa Bitcoin ay ang detalye ng transaksyon. Hindi na kelangan itong i-encrypt para maging sikreto. Kaya sa mekanismo ng paggawa ng signature at verification nito tayo dumiretso.

Ang mensahe mula kay Alicia papunta kay Bob, ay kailangan mayroon din pirma o signature na kalakip bilang patunay na kay Bob nga nakalaan ang transaksyon. At may mekanismo naman para malaman ni Bob na kay Alicia nga galing ang signature.

AliciaParameters/ExchangeBob
r <— R{0, 1, …, n-1}Nonce, pansamantalang private key na pipiliin ng random / sikreto <—
R <— rPPoint generated na syang commitment sa transaksyon (parang pansamantalang public key) / —
R’ <— x(R)x-coordinate ng point R, parte ng signature / —
mMessage / ipapasa —>m
H(m)Hash ng message, gagamitin sa signature / —
s <— r-1(H(m) + R’a) mod nParte ng signature na may marka ng private key a ni Alicia at ng message m / —
(R’, s)Signature / ipapasa —>(R’, s)
Coefficient 1, multiplicative inverse ng s times H(m) / —w1 <— s-1H(m) mod n
Coefficient 2, multiplicative inverse ng s times R’ / —w2 <— s-1R’ mod n
Verification equation (pagkumpara sa x-coordinates) / —x(w1P + w2Q) ≡ R’ (mod n)

Kapag ang nakuhang x-coordinate ni Bob ay parehas sa R’, valid ang signature.

Ipakita natin na ang signature ay valid:
w1P + w2Q = (s-1H(m))P + (s-1R’)Q
Dahil ang public key ni Alicia ay Q = aP (tanggalin na muna natin ang subscript A), mapapakita natin ang P na naka-factor out sa equation:
w1P + w2Q = (s-1(H(m) + R’a))P
Dahil ang s ay multiplicative inverse ng r,
w1P + w2Q = rP
Kaya ang x-coordinate ay dapat magparehas
R’ x(rP) (mod n)

Kaya nakita mo, na hindi nalalaman ni Bob ang private key ni Alicia, pero mabeberika na valid ang signature.

“Anong pakialam ko dito?!”

Nakakalula ba? Yun ay kasama sa punto. Nasa iyo na kung gusto mo pang intindihin base sa antas ng paglahok mo sa Bitcoin.

Anong pakialam ko dito?! Pasensya na kung masyado tayong nagpaka teknikal. Pero magandang maintindihan ang konsepto ng kriptograpiya dahil ito ay bahagi na ng Internet, at ng buhay ngayon. Malaki ang saklaw nito sa operasyon ng Bitcoin. At nakakabilib na isang aspeto lamang ang kriptograpiya. May iba pang malalaking konsepto na nakalahok para mabuo ang Bitcoin.