Baây giôø ta seõ moâ taû vieäc môû roäng yù töôûng treân cho vieäc thaùm maõ treân heä DES 6-voøng. YÙ töoûng ôû ñaây laø löïa choïn moät caùch caån thaän caëp baûn roõ vôùi xaâu x-or ñaëc thuø vaø sau ñoù xaùc ñònh caùc xaùc suaát cuûa caùc daõy ñaëc thuø cuûa caùc xaâu x-or qua caùc voøng laäp maõ. Baây giôø ta caàn ñònh nghóa moät khaùi nieäm quan troïng sau.
Ñònh nghóa 3.5: Cho n ≥ 1 laø soá nguyeân. Ñaëc tröng cuûa voøng thöù n laø moät danh saùch caùc daïng
L0’, R0’, L1’, R1’, p1, ..., Ln’, Rn’, pn
thoûa maõn caùc ñieàu kieän sau:
1. Li’ = Ri-1’ vôùi 1 ≤ i ≤ n
2. Cho 1 ≤ i ≤ n vaø Li-1, Ri-1 vaø L*i-1, R*i-1 laø ñaõ ñöôïc choïn sao cho Li-1 ⊕ L*i-1 = L’i-1 vaø Ri-1 ⊕ R*i-1 = R’i-1. Giaû söû Li, Ri vaø Li* , Ri* laø tính ñöôïc nhôø vieäc aùp duïng moät voøng laäp maõ DES. Khi ñoù xaùc suaát ñeå Li ⊕ L*i = Li’ vaø Ri ⊕ R*i = Ri’ chính xaùc baèng pi.
(Chuù yù laø, xaùc suaát naøy ñöôïc tính treân taát caû caùc boä coù theå coù cuûa J = J1...J8) . Xaùc suaát ñaëc tröng ñöôïc ñònh nghóa baèng tích p = p1 × ...× pn.
Nhaän xeùt: Giaû söû ta choïn L0, R0 vaø L0*, R0* sao cho L0 ⊕ L0* = L0’ vaø R0 ⊕ R0*= R0’ vaø ta aùp duïng n voøng laäp maõ cuûa DES, nhaän ñöôïc L1. ..., Ln vaø R1, ..., Rn. Khi ñoù ta khoâng theå ñoøi hoûi xaùc suaát ñeå Li ⊕ Li* = Li’ vaø Ri ⊕ Ri* = Ri’ cho taát caû i ( 1 ≤ i ≤ n) laø p1 × ...× pn. Bôûi vì caùc boä -48 trong lòch khoùa K1, ..., Kn khoâng phaûi laø ñoäc laäp laãn nhau. (Neáu n boä-48 naøy ñuôïc choïn ñoäc laäp moät caùch ngaãu nhieân, thì ñieàu xaùc nhaän laø ñuùng). Nhöng ta seõ coi raèng p1 × ... × pn chính xaùc laø xaùc xuaát ñoù.
Ta coøn caàn xaùc nhaän laø, caùc xaùc suaát pi trong ñaëc tröng laø caùc caëp baûn roõ ñöôïc xaùc ñònh tuøy yù (nhöng coá ñònh) ñöôïc ñaëc taû baèng xaâu x-or, vôùi 48 bit khoùa cho moät voøng laäp maõ DES laø coù 248 khaû naêng. Do ñoù vieäc thaùm maõ seõ nhaèm vaøo vieäc xaùc ñònh khoùa coá ñònh (nhöng chöa bieát). Do ñoù caàn coá choïn caùc baûn maõ ngaãu nhieân (nhöng chuùng coù caùc xaâu x- or ñöôïc ñaëc taû), hy voïng raèng caùc xaùc suaát ñeå caùc xaâu x-or trong n voøng laäp maõ truøng hôïp vôùi caùc xaâu x-or, ñöôïc ñaëc taû trong ñaëc tröng, töøng ñoâi moät p1, ..., pn töông öùng.
Trong ví duï sau ñaây, ta seõ trình baøy ñaëc tröng voøng 1 ñeå laøm cô sôû cho vieäc thaùm maõ DES ba voøng trong hình sau (nhö ôû treân, ta seõ söû duïng caùch bieåu dieãn theo heä thaäp luïc phaân).
L’0 = baát kyø R’0 = 0000000016
L’1 = 0000000016 R’1 = L’0 p = 1
Ta cuõng seõ moâ taû moät ñaëc tröng voøng 1 khaùc nhö sau L’0 = 0000000016 R’0 = 6000000016
L’1 = 6000000016 R’1 = 0080820016 p = 14/64
Ta haõy xeùt ñaëc tröng sau moät caùch chi tieát hôn. Khi f(R0, K1) vaø f(R0, K1) ñöôïc tính, böôùc ñaàu tieân laø môû roäng R0 vaø R0*. Xaâu x-or keát quaû cuûa hai môû roäng laø:
001100...0
Töùc laø xaâu x-or nhaäp cho S1 laø 001100 vaø caùc xaâu x-or cho baûy S-hoäp khaùc ñeàu laø 000000.
Caùc xaâu xuaát x-or cho S2 ñeán S8 ñeàu laø 0000. Xaâu xuaát x-or cho S1 laø 1110 vôùi xaùc suaát 14/64 (do N1(001100, 1110) = 14). Neân ta nhaän ñöôïc:
C’ = 11100000000000000000000000000000 vôùi xaùc suaát 14/64. Aùp duïng P, ta nhaän ñöôïc:
P(C) ⊕ P(C*) = 00000000100000001000001000000000
trong daïng thaäp luïc phaân seõ laø 0080820016. Khi xaâu naøy coäng x-or vôùi L0’, ta nhaän ñöôïc R1’ vôùi xaùc suaát 14/64. Do ñoù L1’ = R0’.
Vieäc thaùm maõ DES saùu voøng döïa treân ñaëc tröng ba voøng ñöôïc cho trong hình sau.
Trong thaùm maõ 6-voøng, ta baét ñaàu vôùi L0R0. L0*R0*, L6R6 vaø L6*R6*, maø ta phaûi choïn baûn roõ sao cho L0’= 4008000016 vaø R.0’= 0400000016, ta coù theå bieåu dieãn R0 nhö sau:
L0’ L1’ L2’ L3’
=
=
=
=
4008000016
0400000016
0000000016
0400000016
R0’ R1’ R2’ R3’
=
=
=
=
0400000016
0000000016
0400000016
4008000016
p = 1/4 p = 1 p = 1/4 R6 = L5 ⊕ f(R5, K6)
= R4 ⊕ f(R5, K6)
= L3 ⊕ f(R3, K4) ⊕ f(R5, K6) R6* cuõng coù theå bieåu dieãn töông töï, ta coù
R0’ = L3’ ⊕ f(R3, K4) ⊕ f(R3*, K4) ⊕ f(R5, K6) ⊕ f(R5*, K6) (4) (Ñeå yù laø töông töï nhö thaùm maõ 3-voøng)
R6’ laø ñöôïc bieát. Töø ñaëc tröng ta tính L3’ = 0400000016 vaø R3’ = 4008000016 vôùi xaùc suaát 1/16. Neáu nhö vaäy, thì xaâu nhaäp x-or cho S-hoäp trong voøng 4 coù theå tính ñöôïc nhôø haøm môû roäng phaûi laø:
001000000000000001010000...0
Caùc xaâu x-or cho S2, S5, S6, S7 vaø S8 taát caû ñeàu baèng 000000, vaø vì theá xaâu xuaát x-or laø 0000 cho taát caû naêm S-hoäp ñoù trong voøng 4. Ñieàu naøy coù nghóa laø, ta coù theå tính ñöôïc caùc xaâu xuaát x-or cho naêm S-hoäp ñoù trong voøng 6 nhôø phöông trình (4). Do ñoù giaû söû ta tính:
C1’C2’C3’C4’C5’C6’C7’C8’ = P-1(R6’ ⊕ 04000000)
moãi Ci laø xaâu bit coù ñoä daøi 4. Khi ñoù vôùi xaùc suaát 1/16, thì seõ daãn ñeán laø C2’, C5’, C6’, C7’ vaø C8’ töông öùng laø caùc xaâu x-or xuaát cuûa S2, S5, S6, S7 vaø S8 trong voøng 6. Caùc xaâu nhaäp cho caùc S-hoäp ñoù trong voøng 6 coù theå tính ñöôïc laø E2, E5, E6, E7 vaø E8; vaø E2*, E5*, E6*, E7*
vaø E8*, vôùi
E1E2E3E4E5E6E7E8 = E(R5) = E(L6) vaø
E1*E2*E3*E4*E5*E6*E7*E8* = E(R5*) = E(L6*) coù theå tính ñöôïc töø caùc baûn roõ nhö sau:
Input: L0R0, L0*R0*, L6R6 vaø L6*R6*; vôùi L0’ = 4008000016 vaø R0’ = 0400000016.
1. Tính C’ = P-1(R6’ ⊕ 0400000016) 2. Tính E = E(L6) vaø E* = E(L6*) 3. for j ∈ {2,5,6,7,8} do
tính testj( Ej, Ej*, Cj’)
Ta cuõng seõ xaùc ñònh 30 bit khoùa trong J2, J5, J6, J7 vaø J8 nhö trong thaùm maõ 3-voøng.
Baøi toaùn, ñeå xaâu xuaát x-or giaû ñònh cho voøng 6 laø chính xaùc chæ vôùi xaùc suaát 1/16. Coøn 15/16 phaàn coøn laïi ta seõ thöôøng nhaän ñöôïc nhöõng xaâu voâ duïng ngaãu nhieân hôn laø caùc bit khoùa.
Ñònh nghóa 3.6: Giaû söû L0 ⊕ L0* = L0’ vaø R0 ⊕ R0*= R0’. Ta noùi raèng, caëp baûn roõ L0R0 vaø L0* R0* laø ñuùng (right) öùng vôùi ñaëc tröng neáu Li ⊕ Li* = Li’ vaø Ri ⊕ Ri*= Ri’ cho moïi i, 1 ≤ i
≤ n. Caëp traùi vôùi caëp ñöôïc ñònh nghóa goïi laø caëp sai (wrong).
Ta mong raèng, khoaûng 1/16 soá caëp cuûa ta laø ñuùng, coøn caùc caëp coøn laïi laø caëp sai öùng vôùi ñaëc tröng voøng ba cuûa ta.
Chieán löôïc cuûa ta laø tính Ej. Ej* vaø Cj’nhö ñaõ moâ taû ôû treân vaø sau ñoù xaùc ñònh testj(Ej, Ej*, Cj’) vôùi j = 2,5,6,7,8. Neáu ta baét ñaàu vôùi moät caëp ñuùng, thì thì caùc bit khoùa chính xaùc cho moãi Jj seõ naèm trong taäp testj. Neáu caëp laø sai, thì trò Cj’ seõ khoâng ñuùng, vaø ñoù laø nguyeân do ñeå giaû ñònh raèng, moãi taäp testj thöïc chaát laø ngaãu nhieân.
Ta coù theå nhaän ra caëp ñuùng theo phöông phaùp sau: Neáu ⎮testj⎮= 0, vôùi baát kyø j∈
{2,5,6,7,8}, khi ñoù ta taát yeáu coù ñöôïc caëp ñuùng. Baây giôø cho moät caëp sai, ta coù theå hy voïng raèng, xaùc suaát ñeå ⎪testj⎪= 0 cho moät j cuï theå laø xaáp xæ 1/5. Ñoù laø lyù do ñeå giaû ñònh laø, Nj(Ej’, Cj’) = ⎪testj⎪ vaø nhö ñaõ nhaän xeùt töø tröôùc, xaùc suaát ñeå Nj(Ej’, Cj’) = 0 laø xaáp xæ 1/5.
Xaùc suaát ñeå caû naêm testj ñeàu döông laø vaøo khoaûng 0.85 ≈ 0.33, quaû vaäy xaùc suaát ñeå ít nhaát moät testj baèng 0 laø vaøo khoaûng 0.67. Neân ta coù khoaûng 2/3 soá caëp laø sai, nhôø vaøo moät nhaän xeùt ñôn giaûn, ñöôïc goïi laø pheùp loïc (filtering operation). Tyû soá cuûa caùc caëp ñuùng treân caùc caëp coøn laïi sau pheùp loïc laø vaøo khoaûng:
6 3 1 1 16 15 16 1
16
1 =
× +
Ví duï 3.4: Giaû söû ta coù caëp baûn roõ - baûn maõ sau:
Baûn roõ Baûn maõ
86FA1C2B1F51D3BE
C6F21C2B1B51D3BE 1E23ED7F2F553971 296DE2B687AC6340
Chuù yù laø, L0’ = 4008000016 vaø R0’ = 0400000016. Xaâu nhaäp vaø xaâu xuaát cuûa S-hoäp cho voøng 6 ñöôïc tính nhö sau:
j Ej Ej* Cj’ 2
5 6 7 8
111100 111101 011010 101111 111110
010010 111100 000101 010110 101100
1101 0001 0010 1100 1101 Khi ñoù caùc taäp testj seõ laø nhö sau:
j testj
2 14, 15,26, 30, 32, 33, 48, 52
5 6 7, 24, 36, 41, 54, 59
7
8 34, 35, 48, 49
Ta thaáy raèng, hai taäp test5 vaø test7 laø roãng , neân caëp naøy laø caëp sai vaø noù bò loaïi boû baèng pheùp loïc.
Baây giôø giaû söû ta coù caëp sao cho ⎪testj⎪> 0 vôùi j = 2,5,6,7,8 laø nhöõng taäp coøn laïi sau pheùp loïc.(Bôûi vì ta khoâng bieát ñöôïc laø caëp naøo ñuùng, caëp naøo sai.) Ta noùi raèng, xaâu bit J2J5J6J7J8
ñoä daøi 30 laø ñöôïc ñeà xuaát bôûi caëp neáu Jj ∈ testj vôùi j = 2,5,6,7,8. Soá caùc caëp ñöôïc ñeà xuaát laø:
∈2∏,5,6,7,8 j
testj
Ñoù laø bình thöôøng vôùi soá xaâu bit ñöôïc ñeà xuaát laø khaù lôùn. (Chaúng haïn. lôùn hôn 80000)
Giaû söû, ta laäp baûng cho taát caû caùc xaâu ñöôïc ñeà xuaát nhaän ñöôïc töø N caëp, maø khoâng bò loaïi bôûi pheùp loïc. Vôùi moãi caëp ñuùng, thì xaâu bit ñuùng J2J5J6J7J8 seõ laø xaâu ñöôïc ñeà xuaát. Xaâu bit ñuùng seõ ñöôïc tính khoaûng 3N/16 laàn. Xaâu bit sai thöôøng xuaát hieän ít hôn, bôûi vì chuùng xuaát hieän ngaãu nhieân vaø coù khoaûng 230 khaû naêng. (Laø moät soá raát lôùn.)
Ta nhaän ñöôïc moät baûng cöïc lôùn taát caû caùc xaâu ñöôïc ñeà xuaát, neân ta söû duïng moät thuaät toaùn chæ ñoøi hoûi moät khoâng gian vaø thôøi gian ít nhaát. Ta coù theå maõ hoùa baát kyø moät taäp testj naøo thaønh moät veùc tô Tj coù ñoä daøi 64, vôùi toïa ñoä thöù i cuûa Tj ñöôïc ñaët baèng 1 (0≤
i≤63), neáu xaâu bit ñoä daøi 6 laø bieåu dieãn cuûa i ôû trong taäp testj; vaø toïa ñoä thöù i ñöôïc ñaët baèng 0 trong tröôøng hôïp ngöôïc laïi ( ñieàu naøy gioáng nhö maûng caùc boä ñeám maø ta ñaõ söû duïng trong thaùm maõ DES ba voøng).
Vôùi moãi caëp coøn laïi, ta xaây döïng caùc veùc tô nhö treân vaø goïi chuùng laø Tji,
j=2,5,6,7,8; 1 ≤ i≤ N. Vôùi I ⊆ {1, ..., N} ta noùi raèng I laø chaáp nhaän ñöôïc (allowable) neáu vôùi moãi j ∈ {2,5,6,7,8} coù ít nhaát moät toïa ñoä baèng ⎪I⎪ trong veùc tô
∑i∈I i
Tj
Neáu caëp thöù i laø caëp ñuùng cho moãi i∈I, thì taäp I laø chaáp nhaän ñöôïc. Do ñoù ta cho raèng taäp chaáp nhaän ñöôïc coù kích thöôùc (xaáp xæ) 3N/16, laø taäp ñeà xuaát vaø ta hy voïng laø chæ goàm caùc bit khoùa ñuùng chöù khoâng coù caùc xaâu khaùc. Ñieàu naøy laøm ñôn giaûn hoùa cho vieäc xaây döïng taát caû caùc taäp chaáp nhaän ñöôïc I baèng moät thuaät toaùn ñeä qui.