Ch ng 6 ươ
T NG QUAN V MÃ HÓA
Ổ
Ề
Trong các ch ng 1, ươ 2, 3, 4, 5 chúng ta đã đi tìm hi u v toán trong m t mã, chúng ta ể ề ậ
đã có đ c tiên chúng ta đi tìm ượ ề ả ủ c n n t n c a m t mã. Đ đi tìm hi u v m t mã, tr ể ể ề ậ ậ ướ
hi u th nào là m t mã, nh ng yêu c u c a h m t, nguyên t c và phân lo i các h ủ ệ ậ ữ ể ế ầ ắ ạ ậ ệ
m t.Hay nói cách khác ch ng này cho chúng ta cách nhìn nh n ban s khai v m t mã. ậ ươ ề ậ ậ ơ
1.
Khái ni mệ c b n v m t mã ơ ả ề ậ
K thu t m t mã (cryptology) là môn khoa h c ọ nghiên c u v hai lĩnh v c: m t mã ứ ự ề ậ ậ ậ ỹ
(crytography) và thám mã(cryptoanalysis).
M t mã (cryptography) là ngành khoa h c nghiên c u các ph ứ ậ ọ ươ ổ ng pháp bi n đ i ế
thông tin nh m m c đích b o v thông tin kh i s truy c p c a nh ng ng i không có ậ ủ ỏ ự ụ ữ ệ ằ ả ườ
th m quy n. ề ẩ
ế Thám mã (cryptoanalysis) là lĩnh v c khoa h c chuyên nghiên c u, tìm ki m y u ự ứ ế ọ
đi m c a các h m t đ t ng pháp t n công các h m t đó. M t mã và ệ ậ ể ừ ủ ể đó đ a ra ph ư ươ ệ ậ ấ ậ
mã thám là hai lĩnh v c đ i l p nhau nh ng gán bó m t thi t v i nhau. Không th xây ự ố ậ ư ậ ế ớ ể
t n u không hi u bi d ng m t h m t t ự ộ ệ ậ ố ế ể ế ể t sâu v mã thám. Mã thám ch ra y u đi m ề ế ỉ
c s d ng đ t n công h m t này nh ng cũng c a h m t. Y u đi m này có th đ ủ ệ ậ ể ượ ử ụ ệ ậ ể ấ ư ế ể
có th đ c s d ng đ cái ti n h m t cho t t h n. N u ng ể ượ ử ụ ệ ậ ể ế ố ơ ế ườ ệ ậ i xây d ng h m t ự
không có hi u bi t r ng v mã thám, không ki m tra đ an toàn c a h m t tr c các ể ế ộ ủ ệ ậ ướ ề ể ộ
ph ng pháp t n công thì h m t c a anh ta có th t ra kém an toàn tr ươ ệ ậ ủ ể ỏ ấ ướ c m t ph ộ ươ ng
pháp t n công nào đó mà anh ta ch a bi t. Tuy nhiên, không ai có th kh ng đ nh là có ư ấ ế ể ẳ ị
nh ng ph ng pháp thám mã nào đã đ c bi t đ n. Đ c nhi m c a các n c luôn gi ữ ươ ượ ế ế ủ ệ ặ ướ ữ
bí m t nh ng k t qu thu đ c trong lĩnh v c mã thám: k c ph ng pháp thám mã và ữ ế ậ ả ượ ể ả ươ ự
k t q a c a vi c thám mã. ế ủ ủ ệ
Máy mã hóa- Mã hóa h ng đ n vi c th c hi n d i d ng thi ướ ệ ướ ạ ự ế ệ t b đi n t . ế ị ệ ử
S đ m t mã là t p h p các thu t toán mã hóa, gi ơ ồ ậ ậ ậ ợ ả i mã, ki m tra s toàn v n và các ự ể ẹ
ch c năng khác c a m t h m t. ủ ộ ệ ậ ứ
Giao th c m t mã là t p h p các quy t c, th t c quy đ nh cách th c s d ng s đ ứ ử ụ ủ ụ ơ ồ ứ ắ ậ ậ ợ ị
m t mã trong m t h m . Có th th y r ng "giao th c m t mã" và "s đ m t mã" ể ấ ằ ộ ệ ậ ơ ồ ậ ứ ậ ậ
không đi li n v i nhau. Có th có nhi u giao th c khác m t mã khác nhau quy đ nh các ứ ề ể ề ậ ớ ị
cách th c s d ng khác nhau c a cùng m t s đ m t mã nào đó. ộ ơ ồ ậ ứ ử ụ ủ
Khóa (key) là đ i l ng bí m t, bi n thiên trong m t h m t. Khóa nh t đ nh ph i là ạ ượ ộ ệ ậ ấ ị ế ậ ả
ng bi n thiên. bí m t. Khóa nh t đ nh ph i là đ i l ấ ị ạ ượ ậ ả ế
ủ H m t (cryptosystem, h th ng m t mã)- là m t h th ng đ m b o an toàn c a ộ ệ ố ệ ậ ệ ố ậ ả ả
ợ ơ ồ ậ m ng b o v v i vi c s d ng các công c mã hóa. Nó bao g m t p h p s đ m t ụ ệ ử ụ ệ ớ ậ ạ ả ồ
mã, giao th c m t mã và các quy t c v ch t o, phân ph i khóa. ắ ề ế ạ ứ ậ ố
Mã hóa là quá trình s d ng nh ng quy t c đ ử ụ ắ ượ ữ ể ế c quy đ nh trong m t h mã đ bi n ộ ệ ị
đ i thông tin ban đ u (thông tin c n b o v ; b n rõ) thành b n mã. ổ ầ ả ệ ả ả ầ
Gi c l c quy iả mã là quá trình ng ượ ạ ớ i v i mã hóa, t c là s d ng nh ng quy t c đ ử ụ ắ ượ ứ ữ
đ nh trong h mã đ bi n đ i n i dung b n mã v thông tin ban đ u. ị ể ể ổ ộ ệ ề ả ầ
Thám mã cũng là quá trình nh n đ b n mã mà không có s tham gia ậ ượ c b n rõ t ả ừ ả ự
c a khóa ho c là quá trình tính toán khóa m t theo b n mã và b n rõ. ủ ậ ả ả ặ
c đ c tr ng b i s l ng phép tính (N) c n th c hi n đ mã hóa T c đ mã đ ộ ố ượ ở ố ượ ư ặ ự ệ ể ầ
(gi i mã) m t đ n v thông tin. C n hi u r ng t c đ mã ch ph thu c vào b n thân h ả ộ ơ ị ố ộ ể ằ ỉ ụ ầ ả ộ ệ
t b tri n tri n khai nó (t c đ máy tính, mã ch không ph thu c vào đ c tính c a thi ộ ứ ụ ủ ặ ế ị ể ể ố ộ
máy mã...).
Đ an toàn c a h mã đ c tr ng cho kh năng c a h mã ch ng l i s thám mã; nó ủ ệ ủ ệ ư ả ặ ộ ố ạ ự
đ ượ c đo b ng s l ằ ố ượ ề ng phép tính đ n gi n c n th c hi n đ thám h mã đó trong đi u ả ầ ự ệ ể ệ ơ
ki n s d ng thu t toán (ph ng pháp) thám mã t t nh t. C n ph i nói thêm r ng có ệ ử ụ ậ ươ ố ấ ầ ả ằ
th xây d ng nh ng h m t v i đ an tòan b ng ệ ậ ớ ộ ự ữ ể ằ tuy tệ đ iố (t c là không th thám đ ứ ể ượ c
v m t lý thuy t). Tuy nhiên các h m t này không thu n ti n cho vi c s d ng, đòi ề ặ ệ ử ụ ệ ậ ế ệ ậ
, ng h i chi phí cao. Vì th , trên th c t ỏ ự ế ế ườ i ta s d ng nh ng h m t có gi ữ ệ ậ ử ụ ớ ạ ố i h n đ i
v i đ an tòan. Do đó b t kỳ h m t nào cũng có th b thám trong th i gian nào đó. ớ ộ ệ ậ ể ị ấ ờ
Kh năng ch ng nhi u c a mã là kh năng ch ng l i s phát tán l i trong b n tin ễ ủ ả ả ố ố ạ ự ỗ ả
sau khi gi i mã, n u tr i v i b n mã trong quá trình b n mã đ ả ế ướ c đó x y ra l ả ỗ ớ ả ả ượ ề c truy n
i g i đ n ng ng i nh n. Có 3 lo i l i là: t ừ ườ ử ế ườ ạ ỗ ậ thay thế, thêm vào và xóa bit.
Hi uệ ngứ thác lũ – tính ch tấ phân bố nhả hư ngở c aủ m tộ bit đ uầ vào trên t pậ bit
đ uầ ra. Khi thi tế kế m tộ hệ m tậ chúng ta r tấ chú tr ngọ đ nế tính ch tấ này.
Hệ m tậ an toàn tuy tệ đ iố (trên lý thuy tế là không thể thám đư cợ ) là hệ m tậ mà trong
đó vi cệ ch nặ b tắ (thu th pậ ) m tộ số lư ngợ b tấ kỳ các b nả mã không khi nế cho vi cệ
thám mã trở nên dễ dàng hơn. Ta sẽ gi iả thích đ nhị nghĩa này trên ngôn ngữ toán xác
su tấ . Giả sử A và B đ iố đ chị nhau và B mu nố thám hệ m tậ c aủ A. Đ iố v iớ B, t iạ m tộ
th iờ đi mể nào đó, xác su tấ A g iử đi b nả tin Xi là P(Xi). N uế B ch nặ b tắ đư cợ m tộ b nả
mã Yj c aủ A (không bi tế có ph iả là b nả mã từ b nả tin Xi hay không) thì đ iố v iớ B, xác
su tấ A g iử b nả tin Xi là P(Xi/Yj) - xác su tấ có đi uề ki nệ c aủ b nả tin Xi khi bi tế b nả mã
Yj. Hệ m tậ đư cợ coi là an tòan tuy tệ đ iố n uế P(Xi/Yj)=P(Xi).
ệ H m t an toàn th c s là nh ng h m t có th b thám. Tuy nhiên, đ th c hi n ự ự ể ự ệ ậ ệ ậ ể ị ữ
ng th i gian vô cùng l n (hàng ch c ho c hàng nghìn vi c đó c n ph i tiêu t n m t l ả ộ ượ ệ ầ ố ụ ặ ờ ớ
ng b nh vô cùng l n. năm ch ng h n) ho c m t l ạ ộ ượ ẳ ặ ộ ớ ớ
H m t an toàn t m th i-Đó là nh ng h m t có th thám đ c khá d dàng - có th ệ ậ ệ ậ ữ ể ạ ờ ượ ễ ể
ch trong vòng vài gi c mã hóa đã tr nên ỉ ờ . Tuy nhiên, trong th i gian đó, thông tin đ ờ ượ ở
i th i, không còn giá tr n a. l ỗ ị ữ ờ
2. Các yêu c u c a m t h m t ộ ệ ậ ầ ủ
Quá trình m t mã che d u d li u có th th c hi n b ng ch ng trình trên máy tính ấ ữ ệ ể ự ệ ằ ậ ươ
ho c máy m t mã. Th c hi n trên máy thì t n kém chi phí cho vi c xây d ng máy, th ự ự ệ ệ ặ ậ ố ế
nh ng nó có u đi m là năng su t cao, đ n gi n, b o m t…. Vi c th c hi n trên ơ ư ư ự ể ệ ệ ấ ả ả ậ
ch ng trình thì th c t ươ ự ế ơ h n, và cho phép m m d o trong s d ng. ề ử ụ ẻ
Không ph thu c vào cách th c hi n đ i v i m t h m t hi n đ i b o m t thông ố ớ ộ ệ ậ ạ ả ụ ự ệ ệ ậ ộ
tin c n đ m b o các yêu c u sau: ầ ả ả ầ
1. Đ an toàn c a h m t ch ng l i thám mã c n ph i th a mãn đi u ki n: S ủ ệ ậ ộ ố ạ ề ệ ầ ả ỏ ự
phá mã ch th c hi n b ng cách gi i bài toán véc c n khóa, ho c s phá mà đòi ỉ ự ệ ằ ả ặ ự ạ
t quá gi h i nh ng tham s v ỏ ố ượ ữ ớ ạ ặ ầ i h n cho phép c a máy tính hi n đ i ho c c n ủ ệ ạ
t b tính toán đ c ti n. t o ra thi ạ ế ị ắ ề
2. Đ an toàn c a h m t c n đ ủ ệ ậ ầ ộ ượ ậ c đ m b o không ph i là bí m t v thu t ả ậ ề ả ả
toán mà là bí m t v khóa. ậ ề
3. B n mã ch đ c đ c khi có khóa m t. ỉ ọ ượ ả ậ
4. H m t ph i v ng ch c ngay c khi t c s l t đ ả ữ ệ ậ ắ ả ộ i ph m bi ạ ế ượ ố ượ ủ ớ ng đ l n
ng ng. b n rõ và b n mã t ả ả ươ ứ
5. Khi thay đ i l ổ ượ ng nh thông tin khóa ho c b n rõ thì c n ph i d n đ n s ả ả ẫ ế ự ặ ầ ỏ
thay đ i b n mã. ổ ả
6. C u trúc thành ph n thu t toán m t mã c n ph i không đ i ổ ậ ậ ầ ả ấ ầ
7. Kích th c b n mã không đ t so v i kích th c b n rõ; Các bit thêm ướ ả c v ượ ượ ớ ướ ả
vào b n tin trong quá trình mã hóa c n ph i hoàn toàn và ch c ch n d u kín trong ắ ấ ầ ắ ả ả
b n mã. ả
8. L i xu t hi n khi mã hóa không đ c d n đ n thay đ i và đánh m t thông ệ ấ ỗ ượ ế ẫ ấ ổ
tin.
9. S ph thu c gi a các khóa con đ c dùng tu n t trong quá trình mã hóa ự ụ ữ ộ ượ ầ ự
không đ c thi t l p d dàng và đ n gi n. ượ ế ậ ễ ả ơ
10. Đ m b o tính tuy n tính c a không gian khóa. ủ ế ả ả
11. Th i gian mã không đ
c l n. ờ ượ ớ
12. Chi phí khi mã c n ph i phù h p v i giá tr c a thông tin c n b o v . ả ệ
ị ủ ả ầ ầ ợ ớ
3.
Quy t c ắ Kerckhoffs
Trong tác ph m "M t mã quân s " (xu t b n năm 1833), Kerckhoffs đ ra các yêu ấ ả ự ề ẩ ậ
c u b t bu c cho m t h m t. Sau đây là 6 yêu c u chính trong s đó: ầ ộ ệ ậ ầ ắ ộ ố
1. N u h m t không ph i "tuy t đ i an tòan" thì ph i là "th c s an toàn.
ế ệ ậ ự ự ệ ố ả ả
2. Không c n thi bí m t b n thân h m t. Vi c đ i ph ng có đ ầ ế t ph i gi ả ữ ệ ố ệ ậ ậ ả ươ ượ c
ng đ n ho t đ ng c a h th ng. h m t không nh h ệ ậ ả ưở ủ ệ ố ạ ộ ế
ố 3. Khóa có th d dàng truy n đi, ghi nh mà không c n ph i ghi chép. Các đ i ể ễ ề ả ầ ớ
tác có th thay đ i khóa theo nguy n v ng c a h . ủ ọ ệ ọ ể ổ
4. Có th áp d ng h m t cho đi n tín. ệ ậ ụ ể ệ
5. H m t ph i có tính l u đ ng. Đ đ m b o ho t đ ng c a nó ch c n 1 ể ả ạ ộ ệ ậ ỉ ầ ư ủ ả ả ộ
ng ườ i là đ . ủ
6. H m t ph i đ n gi n v m t v n hành: vi c v n hành h m t không đòi ề ặ ậ ả ơ ệ ậ ề ậ ệ ả ậ
h i s tuân th s l ỏ ự ủ ố ượ ầ ng l n các quy t c, không gây ra căng th ng cho đ u ắ ẳ ớ
óc.
Trong 6 yêu c u trên đây, yêu c u th 2 đ c bi t đ n d ứ ầ ầ ượ ế ế ướ ắ i cái tên "quy t c
Kerckhoffs" (Kerckhoffs' principle). Nói cách khác thì quy t c Kerckhoffs là "Đ an toàn ắ ộ
c phép ph thu c vào s bí m t c a khóa". c a m t h m t ch đ ộ ệ ậ ủ ỉ ượ ậ ủ ụ ự ộ
4. Phân lo i h m t ạ ệ ậ
H m t mã
ệ ậ
Mã không dùng khóa
Mã dùng m t ộ khóa
Mã dùng hai khóa
Hàm hash
Mã đ i x ng
ố ứ
ấ ố
ữ
ệ
Mã b t đ i x ngứ
Ch ký đi n tử
Mã dòng
Mã kh iố
S đ phân lo i h m t ạ ệ ậ ơ ồ
Hàm hash – là hàm m t mã(thu t toán), mà đ i s c a nó là m t b n tin có đ dài ố ố ủ ộ ả ậ ậ ộ
b t kỳ bi u di n d ể ấ ễ ướ ạ i d ng dãy bit, giá tr c a hàm hash có kích th ị ủ ướ c không đ i. Vì có ổ
t ki m tra tính toàn v n c a thông đ c tính nh th , nên hash là m t l p mã hõa đ c bi ặ ư ế ộ ớ ặ ệ ẹ ủ ể
tin. Th ng thì hàm hash không có s tham gia c a khóa m t và nó ph i đ m b o đ ườ ả ả ả ượ c ự ủ ậ
đ ph c t p ph thu c c a giá tr đ u ra c a hàm vào t ng bit c a b n tin. ộ ứ ạ ủ ả ộ ủ ị ầ ủ ụ ừ
M t mã đ i x ng- đây là thu t toán m t mã mà quá trình mã hóa và gi ố ứ ậ ậ ậ ả i mã ch dùng ỉ
m t khóa. Th c t thì hai khóa(mã hóa, gi i mã) có th khác nhau, trong tr ự ế ộ ả ể ườ ng h p này ợ
thì m t khóa nh n đ c t khóa kia b ng phép tính toán đ n gi n. ậ ượ ừ ộ ằ ả ơ
M t mã đ i x ng thì đ ố ứ ậ ượ c chia ra thành hai lo i: mã dòng và mã kh i. ạ ố
Mã kh i- là mã, th c hi n bi n đ i kh i d li u v i m t kích th c không đ i. ố ữ ệ ớ ự ệ ế ố ộ ổ ướ ổ
Mã dòng- là mã, th c hi n bi n đ i tu n t t ng bit ho c ký t ầ ự ừ ự ệ ế ặ ổ ự riêng r . ẻ
M t mã b t đ i x ng- đây là ph ng pháp m t mã dùng hai khóa: Khóa công khai ấ ố ứ ậ ươ ậ
dùng cho quá trình mã, khóa m t dùng cho quá trình gi ậ ả ậ i mã. Khóa công khai và khóa m t
có quan h v i nhau b ng bi u th c ph c t p, khóa công khai tính d dàng t ứ ạ ệ ớ ứ ể ễ ằ ừ ậ khóa m t,
còn tính khóa m t t khóa công khai là bài toán khó và h u nh không gi c. ậ ừ ư ầ i đ ả ượ
Ch ký đi n t - ph ng pháp ký m t b c đi n d i d ng đi n t , đ đ m b o tính ệ ử ữ ươ ộ ứ ệ ướ ạ ệ ử ể ả ả
nguyên v n và xác th c quy n tác gi . Nh trong m t mã b t đ i x ng, ch ký đi n t ự ẹ ề ả ấ ố ứ ệ ử ư ữ ậ
cũng dùng thu t toán m t mã v i hai khóa, khóa công khai tính d dàng t ễ ậ ậ ớ ừ khóa m t, còn ậ
khóa công khai. Nh ng khác khóa m t thì r t khó và h u nh là không th tính đ ầ ư ể ấ ậ c t ượ ừ ư
v i m t mã b t đ i x ng là quá trình ký b c đi n dùng khóa m t, còn quá trình ki m tra ớ ấ ố ứ ứ ệ ể ậ ậ
b u đi n dùng khóa công khai. Và khóa m t ngoài ch c a b c đi n thì không ai bi ậ ứ ủ ủ ứ ệ ệ ế t
đ c, nh tính ch t này mà ch ng t ch i b c đi n. ượ ấ ờ ố ừ ố ứ ệ
