Đồ án bảo mật công nghệ thông tin
- 122 trang
- file .pdf
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
MUÏC LUÏC
I .1 Giôùi thieäu ....................................................................................................... 3
I.2 Caùc Heä Maõ Thoâng Duïng:................................................................................. 3
e. Phöông phaùp Affine........................................................................................... 4
f. Phöông phaùp Vigenere....................................................................................... 5
I.2 LAÄP MAÕ DES................................................................................................. 14
I. 3 THAÙM MAÕ DES............................................................................................ 17
I.3.1. Thaùm maõ heä DES - 3 voøng ................................................................. 20
II.3.2. Thaùm maõ heä DES 6-voøng ..................................................................... 24
II.3. 3 Caùc thaùm maõ vi sai khaùc ...................................................................... 28
III. CAØI ÑAËT THAÙM MAÕ DES 3 VOØNG...................................................... 28
III.1 Giao Dieän .................................................................................................... 28
III.2 XÖÛ LYÙ ............................................................................................................
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
LÔØI NOÙI ÑAÀU
Hieän nay, nöôùc ta ñang trong giai ñoaïn tieán haønh coâng nghieäp hoùa, hieän ñaïi hoùa ñaát
nöôùc. Tin hoïc ñöôïc xem laø moät trong nhöõng ngaønh muõi nhoïn. Tin hoïc ñaõ vaø ñang ñoùng goùp
raát nhieàu cho xaõ hoäi trong moïi khía caïnh cuûa cuoäc soáng.
Maõ hoùa thoâng tin laø moät ngaønh quan troïng vaø coù nhieàu öùng duïng trong ñôøi soáng xaõ hoäi.
Ngaøy nay, caùc öùng duïng maõ hoùa vaø baûo maät thoâng tin ñang ñöôïc söû duïng ngaøy caøng phoå
bieán hôn trong caùc lónh vöïc khaùc nhau treân Theá giôùi, töø caùc lónh vöïc an ninh, quaân söï, quoác
phoøng…, cho ñeán caùc lónh vöïc daân söï nhö thöông maïi ñieän töû, ngaân haøng…
ÖÙng duïng maõ hoùa vaø baûo maät thoâng tin trong caùc heä thoáng thöông maïi ñieän töû, giao dòch
chöùng khoaùn,… ñaõ trôû neân phoå bieán treân theá giôùi vaø seõ ngaøy caøng trôû neân quen thuoäc vôùi
ngöôøi daân Vieät Nam. Thaùng 7/2000, thò tröôøng chöùng khoaùn laàn ñaàu tieân ñöôïc hình thaønh taïi
Vieät Nam; caùc theû tín duïng baét ñaàu ñöôïc söû duïng, caùc öùng duïng heä thoáng thöông maïi ñieän
töû ñang ôû böôùc ñaàu ñöôïc quan taâm vaø xaây döïng. Do ñoù, nhu caàu veà caùc öùng duïng maõ hoùa vaø
baûo maät thoâng tin trôû neân raát caàn thieát.
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
I. MOÄT SOÁ PHÖÔNG PHAÙP MAÕ HOÙA
I .1 Giôùi thieäu
Ñònh nghóa 1.1: Moät heä maõ maät (cryptosystem) laø moät boä-naêm (P, C, K, E, D) thoûa maõn
caùc ñieàu kieän sau:
1. P laø khoâng gian baûn roõ. taäp hôïp höõu haïn taát caû caùc maåu tin nguoàn caàn maõ hoùa coù theå
coù
2. C laø khoâng gian baûn maõ. taäp hôïp höõu haïn taát caû caùc maåu tin coù theå coù sau khi maõ
hoùa
3. K laø khoâng gian khoaù. taäp hôïp höõu haïn caùc khoùa coù theå ñöôïc söû duïng
4. Vôùi moãi khoùa k∈K, toàn taïi luaät maõ hoùa ek∈E vaø luaät giaûi maõ dk∈D töông öùng. Luaät
maõ hoùa ek: P → C vaø luaät giaûi maõ ek: C → P laø hai aùnh xaï thoûa maõn
d k ( ek ( x ) ) = x, ∀ x ∈ P
Tính chaát 4. laø tính chaát chính vaø quan troïng cuûa moät heä thoáng maõ hoùa. Tính chaát naøy
baûo ñaûm vieäc maõ hoùa moät maåu tin x∈P baèng luaät maõ hoùa ek∈E coù theå ñöôïc giaûi maõ
chính xaùc baèng luaät dk∈D.
Ñònh nghóa 1.2: Zm ñöôïc ñònh nghóa laø taäp hôïp {0, 1, ..., m-1}, ñöôïc trang bò pheùp coäng
(kyù hieäu +) vaø pheùp nhaân (kyù hieäu laø ×). Pheùp coäng vaø pheùp nhaân trong Zm ñöôïc thöïc
hieän töông töï nhö trong Z, ngoaïi tröø keát quaû tính theo modulo m
Ví duï: Giaû söû ta caàn tính giaù trò 11 × 13 trong Z16. Trong Z, ta coù keát quaû cuûa pheùp nhaân
11×13=143. Do 143≡15 (mod 16) neân 11×13=15 trong Z16.
Moät soá tính chaát cuûa Zm
1. Pheùp coäng ñoùng trong Zm, i.e., ∀ a, b ∈ Zm, a+b ∈ Zm
2. Tính giao hoaùn cuûa pheùp coäng trong Zm, i.e., ∀ a, b ∈ Zm, a+b =b+a
3. Tính keát hôïp cuûa pheùp coäng trong Zm, i.e., ∀ a, b, c ∈ Zm, (a+b)+c =a+(b+c)
4. Zm coù phaàn töû trung hoøa laø 0, i.e., ∀ a ∈ Zm, a+0=0+a=a
5. Moïi phaàn töû a trong Zm ñeàu coù phaàn töû ñoái laø m – a
6. Pheùp nhaân ñoùng trong Zm, i.e., ∀ a, b ∈ Zm, a×b∈ Zm
7. Tính giao hoaùn cuûa pheùp coäng trong Zm, i.e., ∀ a, b ∈ Zm, a×b=b×a
8. Tính keát hôïp cuûa pheùp coäng trong Zm, i.e., ∀ a, b, c ∈ Zm, (a×b)×c =a×(b×c)
9. Zm coù phaàn töû ñôn vò laø 1, i.e., ∀ a ∈ Zm, a×1=1×a=a
10. Tính phaân phoái cuûa pheùp nhaân ñoái vôùi pheùp coäng, i.e., ∀ a, b, c ∈ Zm, (a+b)×c
=(a×c)+(b×c)
11. Zm coù caùc tính chaát 1, 3 – 5 neân taïo thaønh 1 nhoùm. Do Zm coù tính chaát 2 neân taïo thaønh
nhoùm Abel. Zm coù caùc tính chaát (1) – (10) neân taïo thaønh 1 vaønh
I.2 Caùc Heä Maõ Thoâng Duïng:
a. Heä Maõ Ñaày (Shift Cipher )
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
Shift Cipher laø moät trong nhöõng phöông phaùp laâu ñôøi nhaát ñöôïc söû duïng ñeå
maõ hoùa. Thoâng ñieäp ñöôïc maõ hoùa baèng caùch dòch chuyeån (xoay voøng) töøng kyù töï ñi k vò trí
trong baûng chöõ caùi.
Phöông phaùp Shift Cipher
Cho P = C = K = Z26. Vôùi 0 ≤ K ≤ 25, ta ñònh nghóa
eK = x + K mod 26
vaø
dK = y - K mod 26
(x,y ∈ Z26)
trong ñoù 26 laø soá kyù töï trong baûng chöõ caùi La tinh, moät caùch töông töï cuõng coù theå
ñònh nghóa cho moät baûng chöõ caùi baát kyø. Ñoàng thôøi ta deã daøng thaáy raèng maõ ñaåy laø moät heä
maät maõ vì dK(eK(x)) = x vôùi moïi x∈Z26.
b. Heä KEYWORD-CEASAR
Trong heä maõ naøy khoùa laø moät töø naøo ñoù ñöôïc choïn tröôùc, ví duï PLAIN. Töø naøy
xaùc ñònh daõy soá nguyeân trong Z26 (15,11,0,8,13) töông öùng vôùi vò trí caùc chöõ caùi cuûa caùc
chöõ ñöôïc choïn trong baûng chöõ caùi. Baây giôø baûn roõ seõ ñöôïc maõ hoùa baèng caùch duøng caùc
haøm laäp maõ theo thöù töï:
e15, e11, e0, e8, e13, e15, e11, e0, e8, e,...
vôùi eK laø haøm laäp maõ trong heä maõ chuyeån.
c. Heä Maõ Vuoâng (SQUARE)
Trong heä naøy caùc töø khoùa ñöôïc duøng theo moät caùch khaùc haún. Ta duøng baûng chöõ
caùi tieáng Anh (coù theå boû ñi chöõ Q, neáu muoán toång soá caùc chöõ soá laø moät soá chính phöông)
vaø ñoøi hoûi moïi chöõ trong töø khoùa phaûi khaùc nhau. Baây giôø moïi chöõ cuûa baûng chöõ caùi
ñöôïc vieát döôùi daïng moät hình vuoâng, baét ñaàu baèng töø khoùa vaø tieáp theo laø nhöõng chöõ caùi
coøn laïi theo thöù töï cuûa baûng chöõ.
d. Maõ theá vò
Moät heä maõ khaùc khaù noåi tieáng . Heä maõ naøy ñaõ ñöôïc söû duïng haøng traêm naêm nay.
Phöông phaùp :
Cho P = C = Z26. K goàm taát caû caùc hoaùn vò coù theå coù cuûa 26 kyù hieäu
0,...,25. Vôùi moãi hoaùn vò π∈K, ta ñònh nghóa:
eπ(x) = π(x)
vaø ñònh nghóa dπ(y) = π-1(y)
vôùi π -1 laø hoaùn vò ngöôïc cuûa hoaùn vò π.
Trong maõ theá vò ta coù theå laáy P vaø C laø caùc baûng chöõ caùi La tinh. Ta söû duïng Z26
trong maõ ñaåy vì laäp maõ vaø giaûi maõ ñeàu laø caùc pheùp toaùn ñaïi soá.
e. Phöông phaùp Affine
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
Cho P = C = Z26 vaø cho
K = {(a,b) ∈ Z26 × Z26 : gcd(a,26) = 1}
Vôùi K = (a,b) ∈ K, ta xaùc ñònh
eK(x) = ax+b mod 26
vaø
dK = a-1(y-b) mod 26
(x,y ∈ Z26)
Phöông phaùp Affine laïi laø moät tröôøng hôïp ñaëc bieät khaùc cuûa Substitution Cipher.
Ñeå coù theå giaûi maõ chính xaùc thoâng tin ñaõ ñöôïc maõ hoùa baèng haøm ek∈ E thì ek phaûi laø moät
song aùnh. Nhö vaäy, vôùi moãi giaù trò y∈Z26, phöông trình ax+b≡y (mod 26) phaûi coù nghieäm
duy nhaát x∈Z26.
Phöông trình ax+b≡y (mod 26) töông ñöông vôùi ax≡(y–b ) (mod 26). Vaäy, ta chæ caàn
khaûo saùt phöông trình ax≡(y–b ) (mod 26)
Ñònh lyù1.1: Phöông trình ax+b≡y (mod 26) coù nghieäm duy nhaát x∈Z26 vôùi moãi giaù trò b∈Z26
khi vaø chæ khi a vaø 26 nguyeân toá cuøng nhau.
Vaäy, ñieàu kieän a vaø 26 nguyeân toá cuøng nhau baûo ñaûm thoâng tin ñöôïc maõ hoùa baèng haøm ek
coù theå ñöôïc giaûi maõ vaø giaûi maõ moät caùch chính xaùc.
Goïi φ(26) laø soá löôïng phaàn töû thuoäc Z26 vaø nguyeân toá cuøng nhau vôùi 26.
m
Ñònh lyù 1.2: Neáu n = ∏ pi i vôùi pi laø caùc soá nguyeân toá khaùc nhau vaø ei ∈ Z+, 1 ≤ i ≤ m thì
e
i =1
φ (n ) = ∏ ( piei − piei −1 )
m
i =1
Trong phöông phaùp maõ hoùa Affine , ta coù 26 khaû naêng choïn giaù trò b, φ(26) khaû naêng choïn
giaù trò a. Vaäy, khoâng gian khoùa K coù taát caû nφ(26) phaàn töû.
Vaán ñeà ñaët ra cho phöông phaùp maõ hoùa Affine Cipher laø ñeå coù theå giaûi maõ ñöôïc thoâng tin
ñaõ ñöôïc maõ hoùa caàn phaûi tính giaù trò phaàn töû nghòch ñaûo a–1 ∈ Z26.
f. Phöông phaùp Vigenere
phöông phaùp maõ hoùa Vigenere söû duïng moät töø khoùa (keyword) coù ñoä daøi m. Coù theå xem
nhö phöông phaùp maõ hoùa Vigenere Cipher bao goàm m pheùp maõ hoùa Shift Cipher ñöôïc aùp
duïng luaân phieân nhau theo chu kyø.
Khoâng gian khoùa K cuûa phöông phaùp Vigenere coù soá phaàn töû laø 26, lôùn hôn haún phöông
phaùp soá löôïng phaàn töû cuûa khoâng gian khoùa K trong phöông phaùp Shift Cipher. Do ñoù, vieäc
tìm ra maõ khoùa k ñeå giaûi maõ thoâng ñieäp ñaõ ñöôïc maõ hoùa seõ khoù khaên hôn ñoái vôùi phöông
phaùp Shift Cipher.
Phöông phaùp maõ hoùa Vigenere Cipher
Choïn soá nguyeân döông m. Ñònh nghóa P = C = K = (Z26)m
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
K = { (k0, k1, ..., kr-1) ∈ (Z26)r}
Vôùi moãi khoùa k = (k0, k1, ..., kr-1) ∈ K, ñònh nghóa:
ek(x1, x2, ..., xm) = ((x1+k1) mod 26, (x2+k2) mod n, ..., (xm+km) mod 26)
dk(y1, y2, ..., ym) = ((y1–k1) mod n, (y2–k2) mod n, ..., (ym–km) mod 26)
vôùi x, y ∈ (Z26)m
g. Heä maõ Hill
Phöông phaùp Hill Cipher ñöôïc Lester S. Hill coâng boá naêm 1929: Cho soá nguyeân döông
m, ñònh nghóa P = C = (Z26)m. Moãi phaàn töû x∈P laø moät boä m thaønh phaàn, moãi thaønh phaàn
thuoäc Z26. YÙ töôûng chính cuûa phöông phaùp naøy laø söû duïng m toå hôïp tuyeán tính cuûa m thaønh
phaàn trong moãi phaàn töû x∈P ñeå phaùt sinh ra m thaønh phaàn taïo thaønh phaàn töû y∈C.
Phöông phaùp maõ hoùa Hill Cipher
Choïn soá nguyeân döông m. Ñònh nghóa:
P = C = (Z26)m vaø K laø taäp hôïp caùc ma traän m×m khaû nghòch
⎛ k1,1 k1, 2 L k1,m ⎞
⎜ ⎟
⎜ k 2,1 L L k 2,m ⎟
Vôùi moãi khoùa k = ⎜ ∈ K , ñònh nghóa:
M M M ⎟
⎜ ⎟
⎜k k m, 2 L k m ,m ⎟⎠
⎝ m,1
⎛ k1,1 k1, 2 L k1,m ⎞
⎜ ⎟
⎜ k 2,1 L L k 2,m ⎟
ek ( x ) = xk = ( x1 , x2 ,..., xm )⎜ vôùi x=(x1, x2, ..., xm) ∈ P
M M M ⎟
⎜ ⎟
⎜k k m, 2 L k m ,m ⎟⎠
⎝ m ,1
vaø dk(y) = yk–1 vôùi y∈ C
Moïi pheùp toaùn soá hoïc ñeàu ñöôïc thöïc hieän treân Zn
h. Maõ hoaùn vò
Nhöõng phöông phaùp maõ hoùa neâu treân ñeàu döïa treân yù töôûng chung: thay theá moãi kyù töï
trong thoâng ñieäp nguoàn baèng moät kyù töï khaùc ñeå taïo thaønh thoâng ñieäp ñaõ ñöôïc maõ hoùa. YÙ
töôûng chính cuûa phöông phaùp maõ hoaùn vò laø vaãn giöõ nguyeân caùc kyù töï trong thoâng ñieäp
nguoàn maø chæ thay ñoåi vò trí caùc kyù töï; noùi caùch khaùc thoâng ñieäp nguoàn ñöôïc maõ hoùa baèng
caùch saép xeáp laïi caùc kyù töï trong ñoù.
Phöông phaùp maõ hoùa maõ hoaùn vò
Choïn soá nguyeân döông m. Ñònh nghóa:
P = C = (Z26)m vaø K laø taäp hôïp caùc hoaùn vò cuûa m phaàn töû {1, 2, ..., m}
Vôùi moãi khoùa π ∈ K, ñònh nghóa:
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
eπ ( x1 , x2 ,..., xm ) = (xπ (1) , xπ (2 ) ,...xπ (m ) ) vaø
(
d π ( y1 , y 2 ,..., y m ) = yπ −1 (1) , yπ −1 (2 ) ,... yπ −1 (m ) )
vôùi π–1 hoaùn vò ngöôïc cuûa π
Phöông phaùp maõ hoaùn vò chính laø moät tröôøng hôïp ñaëc bieät cuûa phöông phaùp Hill. Vôùi
moãi hoaùn vò π cuûa taäp hôïp {1, 2, ..., m} , ta xaùc ñònh ma traän kπ = (ki, j ) theo coâng thöùc sau:
⎧1, neáu i = π ( j )
ki, j = ⎨
⎩0, trong tröôøng hôïp ngöôïc laïi
Ma traän kπ laø ma traän maø moãi doøng vaø moãi coät coù ñuùng moät phaàn töû mang giaù trò 1, caùc
phaàn töû coøn laïi trong ma traän ñeàu baèng 0. Ma traän naøy coù theå thu ñöôïc baèng caùch hoaùn vò
caùc haøng hay caùc coät cuûa ma traän ñôn vò Im neân kπ laø ma traän khaû nghòch. Roõ raøng, maõ hoùa
baèng phöông phaùp Hill vôùi ma traän kπ hoaøn toaøn töông ñöông vôùi maõ hoùa baèng phöông phaùp
maõ hoaùn vò vôùi hoaùn vò π.
d. Maõ voøng
Trong caùc heä tröôùc ñeàu cuøng moät caùch thöùc laø caùc phaàn töû keá tieáp nhau cuûa baûn roõ
ñeàu ñöôïc maõ hoùa vôùi cuøng moät khoùa K. Nhö vaäy xaâu maõ y seõ coù daïng sau:
y = y1y2... = eK(x1) eK(x2)...
Caùc heä maõ loaïi naøy thöôøng ñöôïc goïi laø maõ khoái (block cipher).
Coøn ñoái vôùi caùc heä maõ doøng. YÙ töôûng ôû ñaây laø sinh ra moät chuoãi khoùa z = z1z2...,
vaø söû duïng noù ñeå maõ hoùa xaâu baûn roõ x = x1x2...theo qui taéc sau:
y = y1 y 2 ... = e z1 ( x1 )e z2 ( x 2 )...
I.3 Quy trình thaùm maõ:
Cöù moãi phöông phaùp maõ hoaù ta laïi coù moät phöông phaùp thaùm maõ töông öùng nhöng
nguyeân taéc chung ñeå vieäc thaùm maõ ñöôïc thaønh coâng thì yeâu caàu ngöôøi thaùm maõ
phaûi bieát heä maõ naøo ñöôïc duøng hoaù. Ngoaøi ra ta coøn phaûi bieát ñöôïc baûn maõ vaø baûn
roõ öùng.
nhìn chung caùc heä maõ ñoái xöùng laø deã caøi ñaët vôùi toác ñoä thöïc thi nhanh.
Tính an toaøn cuûa noù phuï thuoäc vaøo caùc yeáu toá :
• Khoâng gian khoaù phaûi ñuû lôùn
• vôùi caùc pheùp troän thích hôïp caùc heä maõ ñoái xöùng coù theå taïo ra ñöôïc moät heä
maõ môùi coù tính an toaøn cao.
• baûo maät cho vieäc truyeàn khoùa cuõng caàn ñöôïc xöû lyù moät caùch nghieâm tuùc.
Vaø moät heä maõ hoaù döõ lieäu ra ñôøi (DES). DES ñöôïc xem nhö laø chuaån maõ hoùa döõ
lieäu cho caùc öùng duïng töø ngaøy 15 thaùng 1 naêm 1977 do UÛy ban Quoác gia veà Tieâu chuaån
cuûa Myõ xaùc nhaän vaø cöù 5 naêm moät laàn laïi coù chænh söûa, boå sung.
DES laø moät heä maõ ñöôïc troän bôûi caùc pheùp theá vaø hoaùn vò. vôùi pheùp troän thích hôïp
thì vieäc giaûi maõ noù laïi laø moät baøi toaùn khaù khoù. Ñoàng thôøi vieäc caøi ñaët heä maõ naøy cho
nhöõng öùng duïng thöïc teá laïi khaù thuaän lôïi. Chính nhöõng lyù do ñoù noù ñöôïc öùng duïng roäng
raõi cuûa DES trong suoát hôn 20 naêm qua, khoâng nhöõng taïi Myõ maø coøn laø haàu nhö treân khaép
theá giôùi. Maëc duø theo coâng boá môùi nhaát (naêm 1998) thì moïi heä DES, vôùi nhöõng khaû naêng
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
cuûa maùy tính hieän nay, ñeàu coù theå beû khoùa trong hôn 2 giôø. Tuy nhieân DES cho ñeán nay
vaãn laø moät moâ hình chuaån cho nhöõng öùng duïng baûo maät trong thöïc teá.
II. HEÄ MAÕ CHUAÅN DES (Data Encryption Standard)
II.1 Ñaëc taû DES
Phöông phaùp DES maõ hoùa töø x coù 64 bit vôùi khoùa k coù 56 bit thaønh moät töø coù y 64 bit.
Thuaät toaùn maõ hoùa bao goàm 3 giai ñoaïn:
1. Vôùi töø caàn maõ hoùa x coù ñoä daøi 64 bit, taïo ra töø x0 (cuõng coù ñoä daøi 64 bit) baèng caùch
hoaùn vò caùc bit trong töø x theo moät hoaùn vò cho tröôùc IP (Initial Permutation). Bieåu dieãn
x0 = IP(x) = L0R0, L0 goàm 32 bit beân traùi cuûa x0, R0 goàm 32 bit beân phaûi cuûa x0
L0 R0
x0
Hình.1 Bieåu dieãn daõy 64 bit x thaønh 2 thaønh phaàn L vaø R
2. Xaùc ñònh caùc caëp töø 32 bit Li, Ri vôùi 1≤ i ≤ 16theo quy taéc sau:
Li = Ri-1
Ri = Li-1⊕ f (Ri-1, Ki)
vôùi ⊕ bieåu dieãn pheùp toaùn XOR treân hai daõy bit, K1, K2, ..., K16 laø caùc daõy 48 bit phaùt
sinh töø khoùa K cho tröôùc (Treân thöïc teá, moãi khoùa Ki ñöôïc phaùt sinh baèng caùch hoaùn vò
caùc bit trong khoùa K cho tröôùc).
Li-1 Ri-1
f Ki
⊕
Li Ri
Hình.2 Quy trình phaùt sinh daõy 64 bit LiRi töø daõy 64 bit Li-1Ri-1vaø khoùa Ki
3. AÙp duïng hoaùn vò ngöôïc IP-1 ñoái vôùi daõy bit R16L16, thu ñöôïc töø y goàm 64 bit. Nhö
vaäy, y = IP-1 (R16L16)
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
Haøm f ñöôïc söû duïng ôû böôùc 2 laø
A J
E
E(A)
+
B1 B2 B3 B4 B5 B6 B7 B8
S1 S2 S3 S4 S5 S6 S7 S8
C1 C2 C3 C4 C5 C6 C7 C8
P
f(A,J)
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
Haøm f coù goàm 2 tham soá: Tham soá thöù nhaát A laø moät daõy 32 bit, tham soá thöù hai J laø
moät daõy 48 bit. Keát quaû cuûa haøm f laø moät daõy 32 bit. Caùc böôùc xöû lyù cuûa haøm f(A, J)nhö
sau:
• Tham soá thöù nhaát A (32 bit) ñöôïc môû roäng thaønh daõy 48 bit baèng haøm môû roäng E.
Keát quaû cuûa haøm E(A) laø moät daõy 48 bit ñöôïc phaùt sinh töø A baèng caùch hoaùn vò theo
moät thöù töï nhaát ñònh 32 bit cuûa A, trong ñoù coù 16 bit cuûa A ñöôïc laäp laïi 2 laàn trong
E(A).
• Thöïc hieän pheùp toaùn XOR cho 2 daõy 48 bit E(A) vaø J, ta thu ñöôïc moät daõy 48 bit B.
Bieåu dieãn B thaønh töøng nhoùm 6 bit nhö sau:B = B1B2B3B4B5B6B7B8
• Söû duïng 8 ma traän S1, S2,..., S8, moãi ma traän Si coù kích thöôùc 4×16 vaø moãi doøng cuûa
ma traän nhaän ñuû 16 giaù trò töø 0 ñeán 15. Xeùt daõy goàm 6 bit Bj = b1b2b3b4b5b6,
Sj(Bj) ñöôïc xaùc ñònh baèng giaù trò cuûa phaàn töû taïi doøng r coät c cuûa Sj, trong ñoù, chæ soá
doøng r coù bieåu dieãn nhò phaân laø b1b6, chæ soá coät c coù bieåu dieãn nhò phaân laø b2b3b4b5.
Baèng caùch naøy, ta xaùc ñònh ñöôïc caùc daõy 4 bit Cj = Sj(Bj), 1 ≤ j ≤ 8.
• Taäp hôïp caùc daõy 4 bit Cj laïi. ta coù ñöôïc daõy 32 bit C = C1C2C3C4C5C6C7C8. Daõy 32
bit thu ñöôïc baèng caùch hoaùn vò C theo moät quy luaät P nhaát ñònh chính laø keát quaû cuûa
haøm F(A, J)
caùc haøm ñöôïc söû duïng trong DES.
Hoaùn vò khôûi taïo IP seõ nhö sau:
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
Ñieàu naøy coù nghóa laø bit thöù 58 cuûa x laø bit ñaàu tieân cuûa IP(x); bit thöù 50 cuûa x laø
bit thöù hai cuûa IP(x) v.v.
Hoaùn vò ngöôïc IP-1 seõ laø:
IP-1
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
Haøm môû roäng E ñöôïc ñaëc taû theo baûng sau:
E – baûng choïn bit
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
Taùm S-hoäp vaø hoaùn vò P seõ ñöôïc bieåu dieãn nhö sau:
S1
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S2
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S3
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S4
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S5
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 0 14 2 13 6 15 0 9 10 4 5 3
S6
12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S7
4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S8
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
P
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
K laø xaâu coù ñoä daøi 64 bit, trong ñoù coù 56 bit duøng laøm khoùa vaø 8 bit duøng ñeå kieåm
tra söï baèng nhau (ñeå phaùt hieän loãi). Caùc bit ôû caùc vò trí 8, 16, ..., 64 ñöôïc xaùc ñònh, sao cho
moãi byte chöùa soá leû caùc soá 1. Vì vaäy, töøng loãi coù theå ñöôïc phaùt hieän trong moãi 8 bit. Caùc
bit kieåm tra söï baèng nhau laø ñöôïc boû qua khi tính lòch khoùa.
1. Cho khoùa 64 bit K, loaïi boû caùc bit kieåm tra vaø hoaùn vò caùc bit coøn laïi cuûa K
töông öùng vôùi hoaùn vò (coá ñònh) PC-1. Ta vieát PC-1(K) = C0D0, vôùi C0 bao goàm 28 bit ñaàu
tieân cuûa PC-1(K) vaø D0 laø 28 bit coøn laïi.
2. Vôùi i naèm trong khoaûng töø 1 ñeán 16, ta tính
Ci = LSi(Ci-1)
Di = LSi(Di-1)
vaø Ki = PC-2(CiDi), LSi bieåu dieãn pheùp chuyeån chu trình (cyclic shift) sang traùi hoaëc cuûa
moät hoaëc cuûa hai vò trí tuøy thuoäc vaøo trò cuûa i; ñaåy moät vò trí neáu i = 1, 2, 9 hoaëc 16 vaø
ñaåy 2 vò trí trong nhöõng tröôøng hôïp coøn laïi. PC-2 laø moät hoaùn vò coá ñònh khaùc.
Vieäc tính lòch khoùa ñöôïc minh hoïa nhö hình veõ sau:
K
PC-1
C0 D0
LS1 LS1
C1 D1 PC-2 K1
LS2 LS2
...
LS16 LS16
C16 D16 PC-2 K16
Caùc hoaùn vò PC-1 vaø PC-2 ñöôïc söû duïng trong vieäc tính lòch khoùa laø nhö sau:
PC-1
57 49 41 33 25 17 9
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 34 60 52 44 36
63 55 7 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
PC-2
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 50 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Baây giôø ta seõ hieån thò keát quaû vieäc tính lòch khoùa. Nhö ñaõ nhaän xeùt ôû treân, moãi
voøng söû duïng khoùa 48 bit töông öùng vôùi 48 bit trong K. Caùc thaønh phaàn trong caùc baûng sau
seõ chæ ra caùc bit trong K ñöôïc söû duïng trong caùc voøng khaùc nhau.
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
MUÏC LUÏC
I .1 Giôùi thieäu ....................................................................................................... 3
I.2 Caùc Heä Maõ Thoâng Duïng:................................................................................. 3
e. Phöông phaùp Affine........................................................................................... 4
f. Phöông phaùp Vigenere....................................................................................... 5
I.2 LAÄP MAÕ DES................................................................................................. 14
I. 3 THAÙM MAÕ DES............................................................................................ 17
I.3.1. Thaùm maõ heä DES - 3 voøng ................................................................. 20
II.3.2. Thaùm maõ heä DES 6-voøng ..................................................................... 24
II.3. 3 Caùc thaùm maõ vi sai khaùc ...................................................................... 28
III. CAØI ÑAËT THAÙM MAÕ DES 3 VOØNG...................................................... 28
III.1 Giao Dieän .................................................................................................... 28
III.2 XÖÛ LYÙ ............................................................................................................
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
LÔØI NOÙI ÑAÀU
Hieän nay, nöôùc ta ñang trong giai ñoaïn tieán haønh coâng nghieäp hoùa, hieän ñaïi hoùa ñaát
nöôùc. Tin hoïc ñöôïc xem laø moät trong nhöõng ngaønh muõi nhoïn. Tin hoïc ñaõ vaø ñang ñoùng goùp
raát nhieàu cho xaõ hoäi trong moïi khía caïnh cuûa cuoäc soáng.
Maõ hoùa thoâng tin laø moät ngaønh quan troïng vaø coù nhieàu öùng duïng trong ñôøi soáng xaõ hoäi.
Ngaøy nay, caùc öùng duïng maõ hoùa vaø baûo maät thoâng tin ñang ñöôïc söû duïng ngaøy caøng phoå
bieán hôn trong caùc lónh vöïc khaùc nhau treân Theá giôùi, töø caùc lónh vöïc an ninh, quaân söï, quoác
phoøng…, cho ñeán caùc lónh vöïc daân söï nhö thöông maïi ñieän töû, ngaân haøng…
ÖÙng duïng maõ hoùa vaø baûo maät thoâng tin trong caùc heä thoáng thöông maïi ñieän töû, giao dòch
chöùng khoaùn,… ñaõ trôû neân phoå bieán treân theá giôùi vaø seõ ngaøy caøng trôû neân quen thuoäc vôùi
ngöôøi daân Vieät Nam. Thaùng 7/2000, thò tröôøng chöùng khoaùn laàn ñaàu tieân ñöôïc hình thaønh taïi
Vieät Nam; caùc theû tín duïng baét ñaàu ñöôïc söû duïng, caùc öùng duïng heä thoáng thöông maïi ñieän
töû ñang ôû böôùc ñaàu ñöôïc quan taâm vaø xaây döïng. Do ñoù, nhu caàu veà caùc öùng duïng maõ hoùa vaø
baûo maät thoâng tin trôû neân raát caàn thieát.
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
I. MOÄT SOÁ PHÖÔNG PHAÙP MAÕ HOÙA
I .1 Giôùi thieäu
Ñònh nghóa 1.1: Moät heä maõ maät (cryptosystem) laø moät boä-naêm (P, C, K, E, D) thoûa maõn
caùc ñieàu kieän sau:
1. P laø khoâng gian baûn roõ. taäp hôïp höõu haïn taát caû caùc maåu tin nguoàn caàn maõ hoùa coù theå
coù
2. C laø khoâng gian baûn maõ. taäp hôïp höõu haïn taát caû caùc maåu tin coù theå coù sau khi maõ
hoùa
3. K laø khoâng gian khoaù. taäp hôïp höõu haïn caùc khoùa coù theå ñöôïc söû duïng
4. Vôùi moãi khoùa k∈K, toàn taïi luaät maõ hoùa ek∈E vaø luaät giaûi maõ dk∈D töông öùng. Luaät
maõ hoùa ek: P → C vaø luaät giaûi maõ ek: C → P laø hai aùnh xaï thoûa maõn
d k ( ek ( x ) ) = x, ∀ x ∈ P
Tính chaát 4. laø tính chaát chính vaø quan troïng cuûa moät heä thoáng maõ hoùa. Tính chaát naøy
baûo ñaûm vieäc maõ hoùa moät maåu tin x∈P baèng luaät maõ hoùa ek∈E coù theå ñöôïc giaûi maõ
chính xaùc baèng luaät dk∈D.
Ñònh nghóa 1.2: Zm ñöôïc ñònh nghóa laø taäp hôïp {0, 1, ..., m-1}, ñöôïc trang bò pheùp coäng
(kyù hieäu +) vaø pheùp nhaân (kyù hieäu laø ×). Pheùp coäng vaø pheùp nhaân trong Zm ñöôïc thöïc
hieän töông töï nhö trong Z, ngoaïi tröø keát quaû tính theo modulo m
Ví duï: Giaû söû ta caàn tính giaù trò 11 × 13 trong Z16. Trong Z, ta coù keát quaû cuûa pheùp nhaân
11×13=143. Do 143≡15 (mod 16) neân 11×13=15 trong Z16.
Moät soá tính chaát cuûa Zm
1. Pheùp coäng ñoùng trong Zm, i.e., ∀ a, b ∈ Zm, a+b ∈ Zm
2. Tính giao hoaùn cuûa pheùp coäng trong Zm, i.e., ∀ a, b ∈ Zm, a+b =b+a
3. Tính keát hôïp cuûa pheùp coäng trong Zm, i.e., ∀ a, b, c ∈ Zm, (a+b)+c =a+(b+c)
4. Zm coù phaàn töû trung hoøa laø 0, i.e., ∀ a ∈ Zm, a+0=0+a=a
5. Moïi phaàn töû a trong Zm ñeàu coù phaàn töû ñoái laø m – a
6. Pheùp nhaân ñoùng trong Zm, i.e., ∀ a, b ∈ Zm, a×b∈ Zm
7. Tính giao hoaùn cuûa pheùp coäng trong Zm, i.e., ∀ a, b ∈ Zm, a×b=b×a
8. Tính keát hôïp cuûa pheùp coäng trong Zm, i.e., ∀ a, b, c ∈ Zm, (a×b)×c =a×(b×c)
9. Zm coù phaàn töû ñôn vò laø 1, i.e., ∀ a ∈ Zm, a×1=1×a=a
10. Tính phaân phoái cuûa pheùp nhaân ñoái vôùi pheùp coäng, i.e., ∀ a, b, c ∈ Zm, (a+b)×c
=(a×c)+(b×c)
11. Zm coù caùc tính chaát 1, 3 – 5 neân taïo thaønh 1 nhoùm. Do Zm coù tính chaát 2 neân taïo thaønh
nhoùm Abel. Zm coù caùc tính chaát (1) – (10) neân taïo thaønh 1 vaønh
I.2 Caùc Heä Maõ Thoâng Duïng:
a. Heä Maõ Ñaày (Shift Cipher )
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
Shift Cipher laø moät trong nhöõng phöông phaùp laâu ñôøi nhaát ñöôïc söû duïng ñeå
maõ hoùa. Thoâng ñieäp ñöôïc maõ hoùa baèng caùch dòch chuyeån (xoay voøng) töøng kyù töï ñi k vò trí
trong baûng chöõ caùi.
Phöông phaùp Shift Cipher
Cho P = C = K = Z26. Vôùi 0 ≤ K ≤ 25, ta ñònh nghóa
eK = x + K mod 26
vaø
dK = y - K mod 26
(x,y ∈ Z26)
trong ñoù 26 laø soá kyù töï trong baûng chöõ caùi La tinh, moät caùch töông töï cuõng coù theå
ñònh nghóa cho moät baûng chöõ caùi baát kyø. Ñoàng thôøi ta deã daøng thaáy raèng maõ ñaåy laø moät heä
maät maõ vì dK(eK(x)) = x vôùi moïi x∈Z26.
b. Heä KEYWORD-CEASAR
Trong heä maõ naøy khoùa laø moät töø naøo ñoù ñöôïc choïn tröôùc, ví duï PLAIN. Töø naøy
xaùc ñònh daõy soá nguyeân trong Z26 (15,11,0,8,13) töông öùng vôùi vò trí caùc chöõ caùi cuûa caùc
chöõ ñöôïc choïn trong baûng chöõ caùi. Baây giôø baûn roõ seõ ñöôïc maõ hoùa baèng caùch duøng caùc
haøm laäp maõ theo thöù töï:
e15, e11, e0, e8, e13, e15, e11, e0, e8, e,...
vôùi eK laø haøm laäp maõ trong heä maõ chuyeån.
c. Heä Maõ Vuoâng (SQUARE)
Trong heä naøy caùc töø khoùa ñöôïc duøng theo moät caùch khaùc haún. Ta duøng baûng chöõ
caùi tieáng Anh (coù theå boû ñi chöõ Q, neáu muoán toång soá caùc chöõ soá laø moät soá chính phöông)
vaø ñoøi hoûi moïi chöõ trong töø khoùa phaûi khaùc nhau. Baây giôø moïi chöõ cuûa baûng chöõ caùi
ñöôïc vieát döôùi daïng moät hình vuoâng, baét ñaàu baèng töø khoùa vaø tieáp theo laø nhöõng chöõ caùi
coøn laïi theo thöù töï cuûa baûng chöõ.
d. Maõ theá vò
Moät heä maõ khaùc khaù noåi tieáng . Heä maõ naøy ñaõ ñöôïc söû duïng haøng traêm naêm nay.
Phöông phaùp :
Cho P = C = Z26. K goàm taát caû caùc hoaùn vò coù theå coù cuûa 26 kyù hieäu
0,...,25. Vôùi moãi hoaùn vò π∈K, ta ñònh nghóa:
eπ(x) = π(x)
vaø ñònh nghóa dπ(y) = π-1(y)
vôùi π -1 laø hoaùn vò ngöôïc cuûa hoaùn vò π.
Trong maõ theá vò ta coù theå laáy P vaø C laø caùc baûng chöõ caùi La tinh. Ta söû duïng Z26
trong maõ ñaåy vì laäp maõ vaø giaûi maõ ñeàu laø caùc pheùp toaùn ñaïi soá.
e. Phöông phaùp Affine
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
Cho P = C = Z26 vaø cho
K = {(a,b) ∈ Z26 × Z26 : gcd(a,26) = 1}
Vôùi K = (a,b) ∈ K, ta xaùc ñònh
eK(x) = ax+b mod 26
vaø
dK = a-1(y-b) mod 26
(x,y ∈ Z26)
Phöông phaùp Affine laïi laø moät tröôøng hôïp ñaëc bieät khaùc cuûa Substitution Cipher.
Ñeå coù theå giaûi maõ chính xaùc thoâng tin ñaõ ñöôïc maõ hoùa baèng haøm ek∈ E thì ek phaûi laø moät
song aùnh. Nhö vaäy, vôùi moãi giaù trò y∈Z26, phöông trình ax+b≡y (mod 26) phaûi coù nghieäm
duy nhaát x∈Z26.
Phöông trình ax+b≡y (mod 26) töông ñöông vôùi ax≡(y–b ) (mod 26). Vaäy, ta chæ caàn
khaûo saùt phöông trình ax≡(y–b ) (mod 26)
Ñònh lyù1.1: Phöông trình ax+b≡y (mod 26) coù nghieäm duy nhaát x∈Z26 vôùi moãi giaù trò b∈Z26
khi vaø chæ khi a vaø 26 nguyeân toá cuøng nhau.
Vaäy, ñieàu kieän a vaø 26 nguyeân toá cuøng nhau baûo ñaûm thoâng tin ñöôïc maõ hoùa baèng haøm ek
coù theå ñöôïc giaûi maõ vaø giaûi maõ moät caùch chính xaùc.
Goïi φ(26) laø soá löôïng phaàn töû thuoäc Z26 vaø nguyeân toá cuøng nhau vôùi 26.
m
Ñònh lyù 1.2: Neáu n = ∏ pi i vôùi pi laø caùc soá nguyeân toá khaùc nhau vaø ei ∈ Z+, 1 ≤ i ≤ m thì
e
i =1
φ (n ) = ∏ ( piei − piei −1 )
m
i =1
Trong phöông phaùp maõ hoùa Affine , ta coù 26 khaû naêng choïn giaù trò b, φ(26) khaû naêng choïn
giaù trò a. Vaäy, khoâng gian khoùa K coù taát caû nφ(26) phaàn töû.
Vaán ñeà ñaët ra cho phöông phaùp maõ hoùa Affine Cipher laø ñeå coù theå giaûi maõ ñöôïc thoâng tin
ñaõ ñöôïc maõ hoùa caàn phaûi tính giaù trò phaàn töû nghòch ñaûo a–1 ∈ Z26.
f. Phöông phaùp Vigenere
phöông phaùp maõ hoùa Vigenere söû duïng moät töø khoùa (keyword) coù ñoä daøi m. Coù theå xem
nhö phöông phaùp maõ hoùa Vigenere Cipher bao goàm m pheùp maõ hoùa Shift Cipher ñöôïc aùp
duïng luaân phieân nhau theo chu kyø.
Khoâng gian khoùa K cuûa phöông phaùp Vigenere coù soá phaàn töû laø 26, lôùn hôn haún phöông
phaùp soá löôïng phaàn töû cuûa khoâng gian khoùa K trong phöông phaùp Shift Cipher. Do ñoù, vieäc
tìm ra maõ khoùa k ñeå giaûi maõ thoâng ñieäp ñaõ ñöôïc maõ hoùa seõ khoù khaên hôn ñoái vôùi phöông
phaùp Shift Cipher.
Phöông phaùp maõ hoùa Vigenere Cipher
Choïn soá nguyeân döông m. Ñònh nghóa P = C = K = (Z26)m
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
K = { (k0, k1, ..., kr-1) ∈ (Z26)r}
Vôùi moãi khoùa k = (k0, k1, ..., kr-1) ∈ K, ñònh nghóa:
ek(x1, x2, ..., xm) = ((x1+k1) mod 26, (x2+k2) mod n, ..., (xm+km) mod 26)
dk(y1, y2, ..., ym) = ((y1–k1) mod n, (y2–k2) mod n, ..., (ym–km) mod 26)
vôùi x, y ∈ (Z26)m
g. Heä maõ Hill
Phöông phaùp Hill Cipher ñöôïc Lester S. Hill coâng boá naêm 1929: Cho soá nguyeân döông
m, ñònh nghóa P = C = (Z26)m. Moãi phaàn töû x∈P laø moät boä m thaønh phaàn, moãi thaønh phaàn
thuoäc Z26. YÙ töôûng chính cuûa phöông phaùp naøy laø söû duïng m toå hôïp tuyeán tính cuûa m thaønh
phaàn trong moãi phaàn töû x∈P ñeå phaùt sinh ra m thaønh phaàn taïo thaønh phaàn töû y∈C.
Phöông phaùp maõ hoùa Hill Cipher
Choïn soá nguyeân döông m. Ñònh nghóa:
P = C = (Z26)m vaø K laø taäp hôïp caùc ma traän m×m khaû nghòch
⎛ k1,1 k1, 2 L k1,m ⎞
⎜ ⎟
⎜ k 2,1 L L k 2,m ⎟
Vôùi moãi khoùa k = ⎜ ∈ K , ñònh nghóa:
M M M ⎟
⎜ ⎟
⎜k k m, 2 L k m ,m ⎟⎠
⎝ m,1
⎛ k1,1 k1, 2 L k1,m ⎞
⎜ ⎟
⎜ k 2,1 L L k 2,m ⎟
ek ( x ) = xk = ( x1 , x2 ,..., xm )⎜ vôùi x=(x1, x2, ..., xm) ∈ P
M M M ⎟
⎜ ⎟
⎜k k m, 2 L k m ,m ⎟⎠
⎝ m ,1
vaø dk(y) = yk–1 vôùi y∈ C
Moïi pheùp toaùn soá hoïc ñeàu ñöôïc thöïc hieän treân Zn
h. Maõ hoaùn vò
Nhöõng phöông phaùp maõ hoùa neâu treân ñeàu döïa treân yù töôûng chung: thay theá moãi kyù töï
trong thoâng ñieäp nguoàn baèng moät kyù töï khaùc ñeå taïo thaønh thoâng ñieäp ñaõ ñöôïc maõ hoùa. YÙ
töôûng chính cuûa phöông phaùp maõ hoaùn vò laø vaãn giöõ nguyeân caùc kyù töï trong thoâng ñieäp
nguoàn maø chæ thay ñoåi vò trí caùc kyù töï; noùi caùch khaùc thoâng ñieäp nguoàn ñöôïc maõ hoùa baèng
caùch saép xeáp laïi caùc kyù töï trong ñoù.
Phöông phaùp maõ hoùa maõ hoaùn vò
Choïn soá nguyeân döông m. Ñònh nghóa:
P = C = (Z26)m vaø K laø taäp hôïp caùc hoaùn vò cuûa m phaàn töû {1, 2, ..., m}
Vôùi moãi khoùa π ∈ K, ñònh nghóa:
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
eπ ( x1 , x2 ,..., xm ) = (xπ (1) , xπ (2 ) ,...xπ (m ) ) vaø
(
d π ( y1 , y 2 ,..., y m ) = yπ −1 (1) , yπ −1 (2 ) ,... yπ −1 (m ) )
vôùi π–1 hoaùn vò ngöôïc cuûa π
Phöông phaùp maõ hoaùn vò chính laø moät tröôøng hôïp ñaëc bieät cuûa phöông phaùp Hill. Vôùi
moãi hoaùn vò π cuûa taäp hôïp {1, 2, ..., m} , ta xaùc ñònh ma traän kπ = (ki, j ) theo coâng thöùc sau:
⎧1, neáu i = π ( j )
ki, j = ⎨
⎩0, trong tröôøng hôïp ngöôïc laïi
Ma traän kπ laø ma traän maø moãi doøng vaø moãi coät coù ñuùng moät phaàn töû mang giaù trò 1, caùc
phaàn töû coøn laïi trong ma traän ñeàu baèng 0. Ma traän naøy coù theå thu ñöôïc baèng caùch hoaùn vò
caùc haøng hay caùc coät cuûa ma traän ñôn vò Im neân kπ laø ma traän khaû nghòch. Roõ raøng, maõ hoùa
baèng phöông phaùp Hill vôùi ma traän kπ hoaøn toaøn töông ñöông vôùi maõ hoùa baèng phöông phaùp
maõ hoaùn vò vôùi hoaùn vò π.
d. Maõ voøng
Trong caùc heä tröôùc ñeàu cuøng moät caùch thöùc laø caùc phaàn töû keá tieáp nhau cuûa baûn roõ
ñeàu ñöôïc maõ hoùa vôùi cuøng moät khoùa K. Nhö vaäy xaâu maõ y seõ coù daïng sau:
y = y1y2... = eK(x1) eK(x2)...
Caùc heä maõ loaïi naøy thöôøng ñöôïc goïi laø maõ khoái (block cipher).
Coøn ñoái vôùi caùc heä maõ doøng. YÙ töôûng ôû ñaây laø sinh ra moät chuoãi khoùa z = z1z2...,
vaø söû duïng noù ñeå maõ hoùa xaâu baûn roõ x = x1x2...theo qui taéc sau:
y = y1 y 2 ... = e z1 ( x1 )e z2 ( x 2 )...
I.3 Quy trình thaùm maõ:
Cöù moãi phöông phaùp maõ hoaù ta laïi coù moät phöông phaùp thaùm maõ töông öùng nhöng
nguyeân taéc chung ñeå vieäc thaùm maõ ñöôïc thaønh coâng thì yeâu caàu ngöôøi thaùm maõ
phaûi bieát heä maõ naøo ñöôïc duøng hoaù. Ngoaøi ra ta coøn phaûi bieát ñöôïc baûn maõ vaø baûn
roõ öùng.
nhìn chung caùc heä maõ ñoái xöùng laø deã caøi ñaët vôùi toác ñoä thöïc thi nhanh.
Tính an toaøn cuûa noù phuï thuoäc vaøo caùc yeáu toá :
• Khoâng gian khoaù phaûi ñuû lôùn
• vôùi caùc pheùp troän thích hôïp caùc heä maõ ñoái xöùng coù theå taïo ra ñöôïc moät heä
maõ môùi coù tính an toaøn cao.
• baûo maät cho vieäc truyeàn khoùa cuõng caàn ñöôïc xöû lyù moät caùch nghieâm tuùc.
Vaø moät heä maõ hoaù döõ lieäu ra ñôøi (DES). DES ñöôïc xem nhö laø chuaån maõ hoùa döõ
lieäu cho caùc öùng duïng töø ngaøy 15 thaùng 1 naêm 1977 do UÛy ban Quoác gia veà Tieâu chuaån
cuûa Myõ xaùc nhaän vaø cöù 5 naêm moät laàn laïi coù chænh söûa, boå sung.
DES laø moät heä maõ ñöôïc troän bôûi caùc pheùp theá vaø hoaùn vò. vôùi pheùp troän thích hôïp
thì vieäc giaûi maõ noù laïi laø moät baøi toaùn khaù khoù. Ñoàng thôøi vieäc caøi ñaët heä maõ naøy cho
nhöõng öùng duïng thöïc teá laïi khaù thuaän lôïi. Chính nhöõng lyù do ñoù noù ñöôïc öùng duïng roäng
raõi cuûa DES trong suoát hôn 20 naêm qua, khoâng nhöõng taïi Myõ maø coøn laø haàu nhö treân khaép
theá giôùi. Maëc duø theo coâng boá môùi nhaát (naêm 1998) thì moïi heä DES, vôùi nhöõng khaû naêng
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
cuûa maùy tính hieän nay, ñeàu coù theå beû khoùa trong hôn 2 giôø. Tuy nhieân DES cho ñeán nay
vaãn laø moät moâ hình chuaån cho nhöõng öùng duïng baûo maät trong thöïc teá.
II. HEÄ MAÕ CHUAÅN DES (Data Encryption Standard)
II.1 Ñaëc taû DES
Phöông phaùp DES maõ hoùa töø x coù 64 bit vôùi khoùa k coù 56 bit thaønh moät töø coù y 64 bit.
Thuaät toaùn maõ hoùa bao goàm 3 giai ñoaïn:
1. Vôùi töø caàn maõ hoùa x coù ñoä daøi 64 bit, taïo ra töø x0 (cuõng coù ñoä daøi 64 bit) baèng caùch
hoaùn vò caùc bit trong töø x theo moät hoaùn vò cho tröôùc IP (Initial Permutation). Bieåu dieãn
x0 = IP(x) = L0R0, L0 goàm 32 bit beân traùi cuûa x0, R0 goàm 32 bit beân phaûi cuûa x0
L0 R0
x0
Hình.1 Bieåu dieãn daõy 64 bit x thaønh 2 thaønh phaàn L vaø R
2. Xaùc ñònh caùc caëp töø 32 bit Li, Ri vôùi 1≤ i ≤ 16theo quy taéc sau:
Li = Ri-1
Ri = Li-1⊕ f (Ri-1, Ki)
vôùi ⊕ bieåu dieãn pheùp toaùn XOR treân hai daõy bit, K1, K2, ..., K16 laø caùc daõy 48 bit phaùt
sinh töø khoùa K cho tröôùc (Treân thöïc teá, moãi khoùa Ki ñöôïc phaùt sinh baèng caùch hoaùn vò
caùc bit trong khoùa K cho tröôùc).
Li-1 Ri-1
f Ki
⊕
Li Ri
Hình.2 Quy trình phaùt sinh daõy 64 bit LiRi töø daõy 64 bit Li-1Ri-1vaø khoùa Ki
3. AÙp duïng hoaùn vò ngöôïc IP-1 ñoái vôùi daõy bit R16L16, thu ñöôïc töø y goàm 64 bit. Nhö
vaäy, y = IP-1 (R16L16)
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
Haøm f ñöôïc söû duïng ôû böôùc 2 laø
A J
E
E(A)
+
B1 B2 B3 B4 B5 B6 B7 B8
S1 S2 S3 S4 S5 S6 S7 S8
C1 C2 C3 C4 C5 C6 C7 C8
P
f(A,J)
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
Haøm f coù goàm 2 tham soá: Tham soá thöù nhaát A laø moät daõy 32 bit, tham soá thöù hai J laø
moät daõy 48 bit. Keát quaû cuûa haøm f laø moät daõy 32 bit. Caùc böôùc xöû lyù cuûa haøm f(A, J)nhö
sau:
• Tham soá thöù nhaát A (32 bit) ñöôïc môû roäng thaønh daõy 48 bit baèng haøm môû roäng E.
Keát quaû cuûa haøm E(A) laø moät daõy 48 bit ñöôïc phaùt sinh töø A baèng caùch hoaùn vò theo
moät thöù töï nhaát ñònh 32 bit cuûa A, trong ñoù coù 16 bit cuûa A ñöôïc laäp laïi 2 laàn trong
E(A).
• Thöïc hieän pheùp toaùn XOR cho 2 daõy 48 bit E(A) vaø J, ta thu ñöôïc moät daõy 48 bit B.
Bieåu dieãn B thaønh töøng nhoùm 6 bit nhö sau:B = B1B2B3B4B5B6B7B8
• Söû duïng 8 ma traän S1, S2,..., S8, moãi ma traän Si coù kích thöôùc 4×16 vaø moãi doøng cuûa
ma traän nhaän ñuû 16 giaù trò töø 0 ñeán 15. Xeùt daõy goàm 6 bit Bj = b1b2b3b4b5b6,
Sj(Bj) ñöôïc xaùc ñònh baèng giaù trò cuûa phaàn töû taïi doøng r coät c cuûa Sj, trong ñoù, chæ soá
doøng r coù bieåu dieãn nhò phaân laø b1b6, chæ soá coät c coù bieåu dieãn nhò phaân laø b2b3b4b5.
Baèng caùch naøy, ta xaùc ñònh ñöôïc caùc daõy 4 bit Cj = Sj(Bj), 1 ≤ j ≤ 8.
• Taäp hôïp caùc daõy 4 bit Cj laïi. ta coù ñöôïc daõy 32 bit C = C1C2C3C4C5C6C7C8. Daõy 32
bit thu ñöôïc baèng caùch hoaùn vò C theo moät quy luaät P nhaát ñònh chính laø keát quaû cuûa
haøm F(A, J)
caùc haøm ñöôïc söû duïng trong DES.
Hoaùn vò khôûi taïo IP seõ nhö sau:
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
Ñieàu naøy coù nghóa laø bit thöù 58 cuûa x laø bit ñaàu tieân cuûa IP(x); bit thöù 50 cuûa x laø
bit thöù hai cuûa IP(x) v.v.
Hoaùn vò ngöôïc IP-1 seõ laø:
IP-1
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
Haøm môû roäng E ñöôïc ñaëc taû theo baûng sau:
E – baûng choïn bit
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
Taùm S-hoäp vaø hoaùn vò P seõ ñöôïc bieåu dieãn nhö sau:
S1
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
S2
15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9
S3
10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12
S4
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14
S5
2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 0 14 2 13 6 15 0 9 10 4 5 3
S6
12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13
S7
4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12
S8
13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11
P
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
K laø xaâu coù ñoä daøi 64 bit, trong ñoù coù 56 bit duøng laøm khoùa vaø 8 bit duøng ñeå kieåm
tra söï baèng nhau (ñeå phaùt hieän loãi). Caùc bit ôû caùc vò trí 8, 16, ..., 64 ñöôïc xaùc ñònh, sao cho
moãi byte chöùa soá leû caùc soá 1. Vì vaäy, töøng loãi coù theå ñöôïc phaùt hieän trong moãi 8 bit. Caùc
bit kieåm tra söï baèng nhau laø ñöôïc boû qua khi tính lòch khoùa.
1. Cho khoùa 64 bit K, loaïi boû caùc bit kieåm tra vaø hoaùn vò caùc bit coøn laïi cuûa K
töông öùng vôùi hoaùn vò (coá ñònh) PC-1. Ta vieát PC-1(K) = C0D0, vôùi C0 bao goàm 28 bit ñaàu
tieân cuûa PC-1(K) vaø D0 laø 28 bit coøn laïi.
2. Vôùi i naèm trong khoaûng töø 1 ñeán 16, ta tính
Ci = LSi(Ci-1)
Di = LSi(Di-1)
vaø Ki = PC-2(CiDi), LSi bieåu dieãn pheùp chuyeån chu trình (cyclic shift) sang traùi hoaëc cuûa
moät hoaëc cuûa hai vò trí tuøy thuoäc vaøo trò cuûa i; ñaåy moät vò trí neáu i = 1, 2, 9 hoaëc 16 vaø
ñaåy 2 vò trí trong nhöõng tröôøng hôïp coøn laïi. PC-2 laø moät hoaùn vò coá ñònh khaùc.
Vieäc tính lòch khoùa ñöôïc minh hoïa nhö hình veõ sau:
K
PC-1
C0 D0
LS1 LS1
C1 D1 PC-2 K1
LS2 LS2
...
LS16 LS16
C16 D16 PC-2 K16
Caùc hoaùn vò PC-1 vaø PC-2 ñöôïc söû duïng trong vieäc tính lòch khoùa laø nhö sau:
PC-1
57 49 41 33 25 17 9
NGOÂ THÒ TUYEÁT HAØ – T012825
ÑOÀ AÙN BAÛO MAÄT THOÂNG TIN HEÄ MAÕ DES
1 58 50 42 34 26 18
10 2 59 51 43 35 27
19 11 34 60 52 44 36
63 55 7 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
21 13 5 28 20 12 4
PC-2
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 50 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Baây giôø ta seõ hieån thò keát quaû vieäc tính lòch khoùa. Nhö ñaõ nhaän xeùt ôû treân, moãi
voøng söû duïng khoùa 48 bit töông öùng vôùi 48 bit trong K. Caùc thaønh phaàn trong caùc baûng sau
seõ chæ ra caùc bit trong K ñöôïc söû duïng trong caùc voøng khaùc nhau.
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