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:
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
| 2 | 6 | 3 | 1 | 4 | 8 | 5 | 7 |
Kaya ang unang bloke na 01000010 ay magkakaroon ng bagong anyo sunod sa IP: 10000001, na ipinapakita sa talaan sa baba:
| 1 bloke plaintext | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| Pagkakasunud-sunod | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| Pagkakasunud-sunod sa IP | 2 | 6 | 3 | 1 | 4 | 8 | 5 | 7 |
| IP ng plaintext | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
Bago tayo pumunta sa fK, ay intindihin natin ang algorithm ng pagkuha ng susi:
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
| 3 | 5 | 2 | 7 | 4 | 10 | 1 | 9 | 8 | 6 |
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
| 6 | 3 | 7 | 4 | 8 | 5 | 10 | 9 |
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:
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
| 4 | 1 | 2 | 3 | 2 | 3 | 4 | 1 |
Ayusin natin sa ganitong anyo ang E/P para mas madali maintindihan ang mga komplikasyong kasunod:
| n4 | | | n1 | n2 | | | n3 |
| n2 | | | n3 | n4 | | | n1 |
| 1 | | | 0 | 0 | | | 0 |
| 0 | | | 0 | 1 | | | 0 |
Mula dyan gagamitin na ang K1 (10100100) na ka-XOR ng E/P.
| 1⨁1 | | | 0⨁0 | 0⨁1 | | | 0⨁0 |
| 0⨁0 | | | 0⨁1 | 1⨁0 | | | 0⨁0 |
| 0 | | | 0 | 1 | | | 0 |
| 0 | | | 1 | 1 | | | 0 |
Ang resultang iyan ay bibigyan natin ng notasyon para sa susunod na hakbang:
| p0,0 | | | p0,1 | p0,2 | | | p0,3 |
| p1,0 | | | p1,1 | p1,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
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 1 | 0 | 3 | 2 |
| 1 | 3 | 2 | 1 | 0 |
| 2 | 0 | 2 | 1 | 3 |
| 3 | 3 | 1 | 3 | 2 |
S1
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 2 | 0 | 1 | 3 |
| 2 | 3 | 0 | 1 | 0 |
| 3 | 2 | 1 | 0 | 3 |
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
| 2 | 4 | 3 | 1 |
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 IP | 1000 |
| XOR | ⨁ |
| Produkto ng P4 | 0110 |
| Kaliwang produkto ng fK | 1110 |
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 | | | 1 | 1 | | | 1 |
| 1 | | | 1 | 0 | | | 1 |
XOR gamit ang K2(01000011):
| 0⨁0 | | | 1⨁1 | 1⨁0 | | | 1⨁0 |
| 1⨁0 | | | 1⨁0 | 0⨁1 | | | 1⨁1 |
| 0 | | | 0 | 1 | | | 1 |
| 1 | | | 1 | 1 | | | 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:
| IP | 2 | 6 | 3 | 1 | 4 | 8 | 5 | 7 |
| Posisyon | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| IP-1 | 4 | 1 | 3 | 5 | 7 | 2 | 8 | 6 |
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 | | | 1 | 1 | | | 1 |
| 1 | | | 1 | 0 | | | 1 |
XOR gamit ang K2 (01000011):
| 0 | | | 0 | 1 | | | 1 |
| 1 | | | 1 | 1 | | | 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 | | | 0 | 0 | | | 0 |
| 0 | | | 0 | 1 | | | 0 |
XOR gamit ang K1 (10100100):
| 0 | | | 0 | 1 | | | 0 |
| 0 | | | 1 | 1 | | | 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.
Kitakits sa ika-21!
Photo by Pixabay: https://www.pexels.com/photo/colorful-color-play-concentration-54101/ (na hinaluan ng isang DALL-E-generated image)