Xem mẫu
- Luận văn
Đề Tài:
Bảo mật thông tin-Part 3
- ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
I.2 LAÄP MAÕ DES
Ñaây laø ví duï veà vieäc laäp maõ söû duïng DES. Giaû söû ta maõ hoùa baûn roõ sau trong daïng
thaäp luïc phaân (Hexadecimal)
0123456789ABCDEF
söû duïng khoùa thaäp luïc phaân
133457799BBCDFF1
Khoùa trong daïng nhò phaân khoâng coù caùc bit kieåm tra seõ laø:
00010010011010010101101111001001101101111011011111111000.
Aùp duïng IP, ta nhaän ñöôïc L0 vaø R0 (trong daïng nhò phaân) :
L0 = 11001100000000001100110011111111
L1 = R0 = 11110000101010101111000010101010
16 voøng laäp maõ ñöôïc theå hieän nhö sau:
E(R0) = 011110100001010101010101011110100001010101010101
K1 = 000110110000001011101111111111000111000001110010
E(R0) ⊕ K1 = 011000010001011110111010100001100110010100100111
Output S-hoäp = 01011100100000101011010110010111
f(R0,K1) = 00100011010010101010100110111011
L2 = R1 = 11101111010010100110010101000100
E(R1) = 011101011110101001010100001100001010101000001001
NGOÂ THÒ TUYEÁT HAØ – T012825
- ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
K2 = 011110011010111011011001110110111100100111100101
E(R1) ⊕ K2 = 000011000100010010001101111010110110001111101100
Output S-hoäp = 11111000110100000011101010101110
f(R1, K2) = 00111100101010111000011110100011
L3 = R2 = 11001100000000010111011100001001
E(R2) = 111001011000000000000010101110101110100001010011
K3 = 010101011111110010001010010000101100111110011001
E(R2) ⊕ K3 = 101100000111110010001000111110000010011111001010
S-box output = 00100111000100001110000101101111
f(R2, K3) = 01001101000101100110111010110000
L4 = R3 = 10100010010111000000101111110100
E(R3) = 010100000100001011111000000001010111111110101001
K4 = 011100101010110111010110110110110011010100011101
E(R3) ⊕ K4 = 001000101110111100101110110111100100101010110100
S-box output = 00100001111011011001111100111010
f(R3, K4) = 10111011001000110111011101001100
L5 = R4 = 011101110
E(R4) = 101110101110100100000100000000000000001000001010
K5 = 011111001110110000000111111010110101001110101000
E(R4) ⊕ K5 = 110001100000010100000011111010110101000110100010
Xuaát S-hoäp = 01010000110010000011000111101011
f(R4, K5) = 00101000000100111010110111000011
L6 = R5 = 10001010010011111010011000110111
E(R5) = 110001010100001001011111110100001100000110101111
K6 = 011000111010010100111110010100000111101100101111
E(R5) ⊕ K6 = 101001101110011101100001100000001011101010000000
S-box output = 01000001111100110100110000111101
f(R5, K6) = 10011110010001011100110100101100
L7 = R6 = 11101001011001111100110101101001
E(R6) = 111101010010101100001111111001011010101101010011
K7 = 111011001000010010110111111101100001100010111100
E(R6) ⊕ K7 = 000110011010111110111000000100111011001111101111
S-box output = 00010000011101010100000010101101
f(R6, K7) = 10001100000001010001110000100111
L8 = R7 = 00000110010010101011101000010000
E(R7) = 000000001100001001010101010111110100000010100000
NGOÂ THÒ TUYEÁT HAØ – T012825
- ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
K8 = 111101111000101000111010110000010011101111111011
E(R7) ⊕ K8 = 111101110100100001101111100111100111101101011011
S-box output = 01101100000110000111110010101110
f(R7, K8) = 00111100000011101000011011111001
L9 = R8 = 11010101011010010100101110010000
E(R8) = 011010101010101101010010101001010111110010100001
K9 = 111000001101101111101011111011011110011110000001
E(R8) ⊕ K9 = 100010100111000010111001010010001001101100100000
S-box output = 00010001000011000101011101110111
f(R8, K9) = 00100010001101100111110001101010
L10 = R9 = 00100100011111001100011001111010
E(R9) = 000100001000001111111001011000001100001111110100
K10 = 101100011111001101000111101110100100011001001111
E(R9) ⊕ K10 = 101000010111000010111110110110101000010110111011
S-box output = 11011010000001000101001001110101
f(R9, K10) = 01100010101111001001110000100010
L11 = R10 = 10110111110101011101011110110010
E(R10) = 010110101111111010101011111010101111110110100101
K11 = 001000010101111111010011110111101101001110000110
E(R10) ⊕ K11 = 011110111010000101111000001101000010111000100011
S-box output = 01110011000001011101000100000001
f(R10, K11) = 11100001000001001111101000000010
L12 = R11 = 11000101011110000011110001111000
E(R11) 011000001010101111110000000111111000001111110001
K12 011101010111000111110101100101000110011111101001
E(R11) ⊕ K12 000101011101101000000101100010111110010000011000
S-box output 01111011100010110010011000110101
f(R11, K12) 11000010011010001100111111101010
L13 = R12 01110101101111010001100001011000
E(R12) = 001110101011110111111010100011110000001011110000
K13 = 100101111100010111010001111110101011101001000001
E(R12)⊕ K13 = 101011010111100000101011011101011011100010110001
S-box output = 10011010110100011000101101001111
f(R12, K13) = 11011101101110110010100100100010
L14 = R13 = 00011000110000110001010101011010
E(R13) = 000011110001011000000110100010101010101011110100
K14 = 010111110100001110110111111100101110011100111010
E(R13)⊕ K14 = 010100000101010110110001011110000100110111001110
NGOÂ THÒ TUYEÁT HAØ – T012825
- ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
S-box output = 01100100011110011001101011110001
f(R13, K14) = 10110111001100011000111001010101
L15 = R14 = 11000010100011001001011000001101
E(R14) = 111000000101010001011001010010101100000001011011
K15 = 101111111001000110001101001111010011111100001010
E(R14)⊕ K15 = 010111111100010111010100011101111111111101010001
S-box output = 10110010111010001000110100111100
f(R14, K15) = 01011011100000010010011101101110
L16 = R15 = 01000011010000100011001000110100
E(R15) = 001000000110101000000100000110100100000110101000
K16 = 110010110011110110001011000011100001011111110101
E(R15)⊕ K16 = 111010110101011110001111000101000101011001011101
S-box output = 10100111100000110010010000101001
f(R15, K16) = 11001000110000000100111110011000
R16 = 00001010010011001101100110010101
Cuoái cuøng, aùp duïng IP-1 cho R16L16 ta nhaän ñöôïc baûn maõ trong daïng thaäp luïc phaân
nhö sau:
85E813540F0AB405
I. 3 THAÙM MAÕ DES
Moät phöông phaùp raát noåi tieáng trong thaùm maõ DES laø “thaùm maõ vi sai“
(differential cryptanalysic) do Biham vaø Shamir ñeà xuaát. Ñoù laø phöông phaùp thaùm vôùi baûn
roõ ñöôïc choïn. Noù khoâng ñöôïc söû duïng trong thöïc teá ñeå thaùm maõ DES 16 voøng, maø chæ
ñöôïc söû duïng ñeå thaùm caùc heä DES coù ít voøng hôn.
Baây giôø ta seõ moâ taû nhöõng yù töôûng cô baûn cuûa kyõ thuaät naøy. Ñeå ñaït muïc ñích thaùm
maõ, ta coù theå boû qua hoaùn vò khôûi taïo IP vaø hoaùn vò ñaûo cuûa noù (bôûi vì ñieàu ñoù khoâng caàn
thieát cho vieäc thaùm maõ). Nhö ñaõ nhaän xeùt ôû treân, ta xeùt caùc heä DES n voøng, vôùi n ≤ 16.
Trong caøi ñaët ta coù theå coi L0R0 laø baûn roõ vaø LnRn nhö laø baûn maõ.
Thaùm maõ vi sai ñoøi hoûi phaûi so saùnh x-or (exclusive-or) cuûa hai baûn roõ vôùi x-or cuûa
hai baûn maõ töông öùng. Noùi chung, ta seõ quan saùt hai baûn roõ L0R0 vaø L0*R0* vôùi trò x-or
ñöôïc ñaëc taû L0’R0’ = L0R0 ⊕ L0*R0*. Trong nhöõng thaûo luaän sau ta seõ söû duïng kyù hieäu (‘)
ñeå chæ x-or cuûa hai xaâu bit.
Ñònh nghóa 3.1: Cho Sj laø moät S-hoäp (1 ≤ j ≤ 8). Xeùt moät caëp xaâu 6-bit laø (Bj,Bj* ).
Ta noùi raèng, xaâu nhaäp x-or (cuûa Sj) laø Bj ⊕ Bj* vaø xaâu xuaát x-or (cuûa Sj) laø Sj(Bj) ⊕ Sj(Bj*).
Chuù yù laø xaâu nhaäp x-or laø xaâu bit coù ñoä daøi 6, coøn xaâu xuaát x-or coù ñoä daøi 4.
Ñònh nghóa 3.2: Vôùi baát kyø Bj ’ ∈ (Z2) 6, ta ñònh nghóa taäp Δ(Bj’) goàm caùc caëp
(Bj,Bj*) coù x-or nhaäp laø Bj’.
Deã daøng thaáy raèng, baát kyø taäp Δ(Bj’) naøo cuõng coù 26 = 64 caëp, vaø do ñoù
NGOÂ THÒ TUYEÁT HAØ – T012825
- ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
Δ(Bj’) = {(Bj, Bj ⊕ Bj’) : Bj ∈ (Z2) 6 }
Vôùi moãi caëp trong Δ(Bj’), ta coù theå tính xaâu x-or xuaát cuûa Sj vaø laäp ñöôïc phaân boá
keát quaû. Coù 64 xaâu xuaát x-or, ñöôïc phaân boá trong 24 = 16 giaù trò coù theå coù. Tính khoâng
ñoàng ñeàu cuûa caùc phaân boá ñoù laø cô sôû ñeå maõ thaùm.
Ví duï 3.1: Giaû söû ta xeùt S1 laø S-hoäp ñaàu tieân vaø xaâu nhaäp x-or laø 110100. Khi ñoù
Δ(110100) = {(000000, 110100), (000001, 110101), ..., (111111, 001011)}
Vôùi moãi caëp trong taäp Δ(110100), ta tính xaâu xuaát x-or cuûa S1. Chaúng haïn,
S1(000000) = E16 = 1110, S1(110100) = 1001,
nhö vaäy xaâu xuaát x-or cho caëp (000000,110100) laø 0111.
Neáu thöïc hieän ñieàu ñoù cho 64 caëp trong Δ(110100) thì ta nhaän ñöôïc phaân boá cuûa
caùc xaâu x-or xuaát sau:
000 000 001 001 010 010 011 011 100 100 101 101 110 110 111 111
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 8 16 6 2 0 0 12 6 0 0 0 0 8 0 6
Trong ví duï 3.1, chæ coù 8 trong soá 16 xaâu x-or xuaát coù theå coù xuaát hieän thaät söï. Ví
duï cuï theå naøy ñaõ chæ ra söï phaân boá raát khoâng ñeàu cuûa caùc xaâu x-or xuaát. Noùi chung, neáu ta
coá ñònh S-hoäp Sj vaø xaâu nhaäp x-or Bj’, thì trung bình coù khoaûng 75 - 80% caùc xaâu x-or
xuaát coù theå coù xuaát hieän thöïc söï.
Ñeå moâ taû caùc phaân boâ ñoù ta ñöa ra ñònh nghóa sau.
Ñònh nghóa 3.3: Vôùi 1 ≤ j ≤ 8 vaø vôùi caùc xaâu bit Bj’ ñoä daøi 6 vaø Cj’ ñoä daøi 4, ta
ñònh nghóa:
INj(Bj’,Cj’) = {Bj ∈ (Z2)6 : Sj(Bj) ⊕ Sj(Bj ⊕ Bj’) = Cj’}
vaø
Nj(Bj’, Cj’) = ⎮INj(Bj’, Cj’)⎮
Baûng sau seõ cho caùc xaâu nhaäp coù theå coù vôùi xaâu x-or nhaäp 110100
Xaâu xuaát x-or Caùc xaâu nhaäp coù theå coù
0000
0001 000011, 001111, 011110, 011111
101010, 101011, 110111, 111011
000100, 000101, 001110, 010001
0010 010010, 010100, 011010, 011011
100000, 100101, 010110, 101110
101111, 110000, 110001, 111010
0011 000001, 000010, 010101, 100001
110101, 110110
0100 010011, 100111
NGOÂ THÒ TUYEÁT HAØ – T012825
- ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
0101
0110
000000, 001000, 001101, 010111
0111 011000, 011101, 100011, 101001
101100, 110100, 111001, 111100
1000 001001, 001100, 011001, 101101
111000, 111101
1001
1010
1011
1100
1101 000110, 010000, 010110, 011100
110010, 100100, 101000, 110010
1110
1111 000111, 001010, 001011, 110011
111110, 111111
Nj(Bj’, Cj’) tính soá caùc caëp vôùi xaâu nhaäp x-or baèng Bj’ coù xaâu xuaát x-or baèng Cj’
vôùi S-hoäp Sj. Caùc caëp ñoù coù caùc xaâu nhaäp x-or ñöôïc ñaëc taû vaø ñöa ra caùch tính caùc xaâu
xuaát x-or coù theå nhaän ñöôïc töø taäp INj(Bj’, Cj’). Ñeå yù raèng, taäp naøy coù theå phaân thaønh
Nj(Bj’, Cj’) /2 caëp, moãi caëp coù xaâu x-or nhaäp baèng Bj’.
Phaân boá trong ví duï 3.1 chöùa caùc trò N1(110100, C1’), C1’∈ (Z2)4. Trong baûng treân
chöùa caùc taäp IN(110100, C1’).
Vôùi moãi taùm S-hoäp, coù 64 xaâu nhaäp x-or coù theå coù. Nhö vaäy, coù 512 phaân boá coù
theå tính ñöôïc. Nhaéc laïi laø, xaâu nhaäp cho S-hoäp ôû voøng thöù i laø B= E⊕ J, vôùi E = E(Ri-1) laø
môû roäng cuûa Ri-1 vaø J = Ki goàm caùc bit khoùa cuûa voøng i. Baây giôø xaâu nhaäp x-or (cho taát caû
taùm S-hoäp) coù theå tính ñöôïc nhö sau:
B ⊕ B* = (E ⊕ J) ⊕ (E* ⊕ J) = E ⊕ E*
Ñieàu naøy raát quan troïng ñeå thaáy raèng, xaâu nhaäp x-or khoâng phuï thuoäc vaøo caùc bit
khoùa J. (Do ñoù, xaâu xuaát x-or cuõng khoâng phuï thuoäc vaøo caùc bit khoùa.)
Ta seõ vieát moãi B, E vaø J nhö laø noái cuûa taùm xaâu 6-bit:
B = B1B2B3B4B5B6B7B8
E = E1E2E3E4E5E6E7E8
J = J1J2J3J4J5J6J7J8
vaø ta cuõng seõ vieát B vaø E* nhö vaäy. Baây giôø giaû söû laø ta ñaõ bieát caùc trò Ej vaø Ej* vôùi moät j
*
naøo ñoù, 1 ≤ j ≤ 8, vaø trò cuûa xaâu xuaát x-or cho Sj, Cj’ = Sj(Bj) ⊕ Sj(Bj* ). Khi ñoù seõ laø:
Ej ⊕ Jj ∈ INj(Ej’, Cj’),
*
vôùi Ej’ = Ej ⊕ Ej .
Ñònh nghóa 3.4: Giaû söû Ej vaø Ej* laø caùc xaâu bit ñoä daøi 6, vaø Cj’ laø xaâu bit ñoä daøi 4. Ta ñònh
nghóa:
testj(Ej, Ej*, Cj’) = { Bj ⊕ Ej : Bj ∈ INj(Ej’, Cj’) },
vôùi Ej’ = Ej ⊕ Ej*.
NGOÂ THÒ TUYEÁT HAØ – T012825
- ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
Ñònh lyù 3.1:
Giaû söû Ej vaø Ej* laø hai xaâu nhaäp cho S-hoäp Sj, vaø xaâu xuaát x-or cho Sj laø Cj’. Kyù hieäu
Ej’ = Ej ⊕ Ej* . Khi ñoù caùc bit khoùa Jj coù trong taäp testj(Ej, Ej*, Cj’).
Ñeå yù, ñoù chính laø caùc xaâu bit Nj(Ej’, Cj’) ñoä daøi 6 trong taäp testj(Ej, Ej*, Cj’); giaù trò
chính xaùc cuûa Jj phaûi laø moät trong soá ñoù.
Ví duï 3.2:
Giaû söû E1 = 000001, E1*= 110101 vaø C1’= 1101. Do ñoù N1(110101,1101) = 8, ñuùng baèng 8
xaâu bit trong taäp test1(000001, 110101, 1101). Töø baûng treân ta thaáy raèng
IN1(110100, 1101) = {000110, 010000, 010110, 011100, 100010, 100100, 101000,
110010}
Cho neân
test1(000001, 110101,1101) = {000111, 010001, 010111, 011101, 100011, 100101,
101001, 110011}
Neáu ta coù moät boä ba thöù hai nhö theá E1, E1*, C1’, khi ñoù ta seõ nhaän ñöôïc taäp thöù
hai test1 cuûa caùc trò cho caùc bit khoùa trong J1. Trò ñuùng cuûa J1 caàn phaûi naèm trong giao cuûa
caùc S-hoäp. Neáu ta coù moät vaøi boä ba nhö vaäy, khi ñoù ta coù theå mau choùng tìm ñöôïc caùc bit
khoùa trong J1. Moät caùch roõ raøng hôn ñeå thöïc hieän ñieàu ñoù laø laäp moät baûng cuûa 64 boä ñeám
bieåu dieãn cho 64 khaû naêng cuûa cuûa 6 khoùa bit trong J1. Boä ñeám seõ taêng moãi laàn, töông öùng
vôùi söï xuaát hieän cuûa caùc bit khoùa trong taäp test1 cho moät boä ba cuï theå. Cho t boä ba, ta hy
voïng tìm ñöôïc duy nhaát moät boä ñeám coù trò t; trò ñoù seõ töông öùng vôùi trò ñuùng cuûa caùc bit
khoùa trong J1.
I.3.1. Thaùm maõ heä DES - 3 voøng
Baây giôø ta seõ xeùt yù töôûng vöøa trình baøy cho vieäc thaùm maõ heä DES - ba voøng. Ta seõ
baét ñaàu vôùi caëp baûn roõ vaø caùc baûn maõ töông öùng: L0R0, L0*R0*, L3R3 vaø L3*R3*. Ta coù theå
bieåu dieãn R3 nhö sau:
R3 = L2 ⊕ f(R2, K3)
= R1 ⊕ f(R2, K3)
= L0 ⊕ f(R0, K1) ⊕ f(R2, K3)
R3* coù theå bieåu dieãn moät caùch töông töï , do vaäy:
R3’ = L0’ ⊕ f(R0, K1) ⊕ f(R0*, K1) ⊕ f(R2, K3) ⊕ f(R2*, K3)
Baây giôø, giaû söû ta ñaõ choïn ñöôïc caùc baûn roõ sao cho R0 = R0*, chaúng haïn:
R0’ = 00...0
Khi ñoù f(R0, K1) = f(R0*, K1), vaø do ñoù:
R3’ = L0’⊕ f(R2, K3) ⊕ f(R2*, K3)
ÔÛ ñieåm naøy R3’ laø ñöôïc bieát khi noù coù theå tính ñöôïc töø hai baûn maõ, vaø L0’ laø bieát
ñöôïc khi noù coù theå tính ñöôïc töø hai baûn roõ. Nghóa laø ta coù theå tính ñöôïc f(R2,K3)⊕f(R2*,K3)
töø phöông trình:
f(R2, K3) ⊕ f(R2*, K3) = R3’ ⊕ L0’
Baây giôø f(R2, K3) = P(C) vaø f(R2*, K3) = P(C*), vôùi C vaø C* töông öùng laø kyù hieäu
cuûa hai xaâu xuaát cuûa taùm S-hoäp (nhaéc laïi, P laø coá ñònh, laø hoaùn vò ñöôïc bieát coâng khai).
Neân:
NGOÂ THÒ TUYEÁT HAØ – T012825
- ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
P(C) ⊕ P(C*) = R3’ ⊕ L0’
vaø keát quaû laø:
C’ = C ⊕ C* = P-1(R3’ ⊕ L0’) (1)
Ñoù laø xaâu xuaát x-or cho taùm S-hoäp trong voøng ba.
Baây giôø, R2 = L3 vaø R2* = L3* laø ñaõ bieát (chuùng laø moät phaàn cuûa caùc baûn maõ). Töø
ñaây ta coù theå tính:
E = E(L3) (2)
vaø
E* = E(L3*) (3)
söû duïng haøm môû roäng E ñöôïc bieát coâng khai. Chuùng laø nhöõng xaâu nhaäp cho caùc S-hoäp cho
voøng ba. Nhö vaäy giôø ta ñaõ bieát E, E*, vaø C’ cho voøng ba vaø ta coù theå tieáp tuïc xaây döïng
caùc taäp test1, ..., test8 cuûa caùc trò coù theå coù cho caùc bit khoùa trong J1, ..., J8.
Giaûi thuaät vöøa xeùt coù theå bieåu dieãn bôûi caùc maõ sau:
Input: L0R0, L0*R0*, L3R3 vaø L3*R3*, vôùi R0 = R0*
1. Tính C’ = P-1(R3’ ⊕ L0’)
2. Tính E = E(L3) vaø E* = E(L*)
3. for j = 1 to 8 do
compute testj(Ej, Ej*, Cj’)
Vieäc maõ thaùm seõ söû duïng moät soá boä ba E, E*, C’ nhö vaäy. Ta seõ laäp taùm baûng caùc
boä ñeám vaø do ñoù xaùc ñònh ñöôïc 48 bit trong K3, laø khoùa cho voøng ba. 56 bit trong khoùa khi
ñoù coù theå tìm ñöôïc hoaøn toaøn töø 28 = 256 khaû naêng cho 8 bit khoùa.
Baây giôø ta seõ minh hoïa ñieàu ñoù qua ví duï sau.
Ví duï 3.3
Giaû söû ta coù ba caëp baûn roõ vaø baûn maõ, vôùi caùc baûn maõ cuøng coù caùc xaâu x-or ñöôïc
maõ hoùa bôûi cuøng moät khoùa. Ñeå ngaén goïn ta söû duïng heä thaäp luïc phaân:
Baûn roõ Baûn maõ
748502CD38451097 03C70306D8A09F10
3874756438451097 78560A0960E6D4CB
486911026ACDFF31 45FA285BE5ADC730
375BD31F6ACDFF31 134F7915AC253457
357418DA013FEC86 D8A31B2F28BBC5CF
12549847013FEC86 0F317AC2B23CB944
Töø caëp ñaàu tieân ta tính caùc xaâu nhaäp cuûa S-hoäp (cho voøng 3) töø caùc phöông trình
(2) vaø (3). Chuùng laø:
E = 000000000111111000001110100000000110100000001100
E* = 101111110000001010101100000001010100000001010010
Xaâu xuaát x-or cuûa S-hoäp ñöôïc tính baèng phöông trình (1) seõ laø:
C’ = 10010110010111010101101101100111
NGOÂ THÒ TUYEÁT HAØ – T012825
- ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
Töø caëp thöù hai, ta tính ñöôïc caùc xaâu nhaäp cho S-hoäp laø:
E = 101000001011111111110100000101010000001011110110
E* = 100010100110101001011110101111110010100010101001
vaø xaâu xuaát x-or cuûa S-hoäp laø:
C’ = 10011100100111000001111101010110
Töø caëp thöù ba, caùc xaâu nhaäp cho S-hoäp seõ laø:
E = 111011110001010100000110100011110110100101011111
E* = 000001011110100110100010101111110101011000000100
vaø xaâu xuaát x-or cuûa S-hoäp laø:
C’ = 11010101011101011101101100101011
Tieáp theo, ta laäp baûng caùc trò trong taùm maûng boä ñeám cho moãi caëp. Ta seõ minh hoïa
thuû tuïc vôùi caùc maûng ñeám cho J1 töø caëp ñaàu tieân. Trong caëp naøy, ta coù E1’= 101111 vaø C1’
= 1001. Taäp:
IN1(101111, 1001) = {000000, 000111, 101000, 101111}
Do E1 = 000000 ta coù:
J1 ∈ test1(000000, 101111, 1001) = {000000, 000111, 101000, 101111}
Do ñoù ta taêng caùc trò 0, 7, 40 vaø 47 trong caùc maûng ñeám cho J1.
Cuoái cuøng ta seõ trình baøy caùc baûng. Neáu ta xem caùc xaâu bit ñoä daøi 6 nhö laø bieåu
dieãn cuûa caùc soá nguyeân trong khoaûng 0-63, thì 64 trò seõ töông öùng vôùi 0, 1, ..., 63. Caùc
maûng ñeám seõ laø nhö sau:
J1
1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0
0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 3
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
J2
0 0 0 1 0 3 0 0 1 0 0 1 0 0 0 0
0 1 0 0 0 2 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 1 0 1 0 0 0 1 0
0 0 1 1 0 0 0 0 1 0 1 0 2 0 0 0
J3
0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0
0 0 0 3 0 0 0 0 0 0 0 0 0 0 1 1
0 2 0 0 0 0 0 0 0 0 0 0 1 1 0 0
0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0
J4
3 1 0 0 0 0 0 0 0 0 2 2 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 1
NGOÂ THÒ TUYEÁT HAØ – T012825
- ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 2 1
J5
0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0
0 0 0 0 2 0 0 0 3 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 2 0 0 0 0 0 0 1 0 0 0 0 2 0
J6
1 0 0 1 1 0 0 3 0 0 0 0 1 0 0 1
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0
1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0
J7
0 0 2 1 0 1 0 3 0 0 0 1 1 0 0 0
0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1
0 0 2 0 0 0 2 0 0 0 0 1 2 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
J8
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 1
0 3 0 0 0 0 1 0 0 0 0 0 0 0 0 0
Trong moãi taùm maûng ñeám, coù duy nhaát moät boä ñeám coù trò laø 3. Vò trí cuûa caùc boä
ñeám ñoù xaùc ñònh caùc bit khoùa trong J1, ..., J8. Caùc vò trí ñoù laø: 47, 5, 19, 0, 24, 7, 7, 49.
Chuyeån caùc soá nguyeân ñoù sang daïng nhò phaân, ta nhaän ñöôïc J1, ..., J8:
J1 = 101111
J2 = 000101
J3 = 010011
J4 = 000000
J5 = 011000
J6 = 000111
J7 = 000111
J8 = 110001
Baây giôø ta coù theå taïo ra 48 bit khoùa, baèng caùch quan saùt lòch khoùa cho voøng ba. Suy
ra laø K coù daïng:
0001101 0110001 01?01?0 1?00100
0101001 0000??0 111?11? ?100011
vôùi caùc bit kieåm tra ñaõ ñöôïc loaïi boû vaø “?” kyù hieäu bit khoùa chöa bieát. Khoùa ñaày ñuû (trong
daïng thaäp luïc phaân, goàm caû bit kieåm tra) seõ laø:
1A624C89520DEC46
NGOÂ THÒ TUYEÁT HAØ – T012825
nguon tai.lieu . vn