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 n n t n c a m t mã. Đ đi tìm hi u v m t mã, tr c tiên chúng ta đi tìmượ ề ả ủ ậ ể ể ề ậ ướ
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 đó đ a ra ph ng pháp t n công các h m t đó. M t mã vàể ủ ệ ậ ể ừ ư ươ ấ ệ ậ ậ
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ự ố ậ ư ậ ế ớ ể
d ng m t h m t t t n u không hi u bi t sâu v mã thám. Mã thám ch ra y u đi mự ộ ệ ậ ố ế ể ế ề ỉ ế ể
c a h m t. Y u đi m này có th đ c s d ng đ t n công h m t này nh ng cũngủ ệ ậ ế ể ể ượ ử ụ ể ấ ệ ậ ư
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àạ ượ ậ ế ộ ệ ậ ấ ị ả
bí m t. Khóa nh t đ nh ph i là đ i l ng bi n thiên. ậ ấ ị ả ạ ượ ế
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 iả mã là quá trình ng c l i v i mã hóa, t c là s d ng nh ng quy t c đ c quyượ ạ ớ ứ ử ụ ữ ắ ượ
đ 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 đ c b n rõ t b n mã mà không có s tham giaậ ượ ả ừ ả ự
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õ. ủ ặ ậ ả ả
T c đ mã đ c đ c tr ng b i s l ng phép tính (N) c n th c hi n đ mã hóaố ộ ượ ặ ư ở ố ượ ầ ự ệ ể
(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ầ ể ằ ố ộ ỉ ụ ộ ả ệ
mã ch không ph thu c vào đ c tính c a thi t b tri n tri n khai nó (t c đ máy tính,ứ ụ ộ ặ ủ ế ị ể ể ố ộ
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ề ặ ế ệ ậ ậ ệ ệ ử ụ
h i chi phí cao. Vì th , trên th c t , ng 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 c đó x y ra l i v i b n mã trong quá trình b n mã đ c truy nả ế ướ ả ỗ ớ ả ả ượ ề
t ng i g i đ n ng i nh n. Có 3 lo i l i là: ừ ườ ử ế ườ ậ ạ ỗ 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ệ ậ ự ự ữ ệ ậ ể ị ể ự ệ
vi c đó c n ph i tiêu t n m t l ng th i gian vô cùng l n (hàng ch c ho c hàng nghìnệ ầ ả ố ộ ượ ờ ớ ụ ặ
năm ch ng h n) ho c m t l ng b nh vô cùng l n. ẳ ạ ặ ộ ượ ộ ớ ớ
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 . Tuy nhiên, trong th i gian đó, thông tin đ c mã hóa đã tr nênỉ ờ ờ ượ ở
l i th i, không còn giá tr n a.ỗ ờ ị ữ
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ỉ ự ệ ằ ả ạ ặ ự
h i nh ng tham s v t quá gi i h n cho phép c a máy tính hi n đ i ho c c nỏ ữ ố ượ ớ ạ ủ ệ ạ ặ ầ
t o ra thi t b tính toán đ c ti n.ạ ế ị ắ ề
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 i ph m bi t đ c s l ng đ l nệ ậ ả ữ ắ ả ộ ạ ế ượ ố ượ ủ ớ
b n rõ và b n mã t ng ng.ả ả ươ ứ
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 đ c v t so v i kích th c b n rõ; Các bit thêmướ ả ượ ượ ớ ướ ả
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 t ph i gi bí m t b n thân h m t. Vi c đ i ph ng có đ cầ ế ả ữ ậ ả ệ ậ ệ ố ươ ượ
h m t không nh h ng đ n ho t đ ng c a h th ng. ệ ậ ả ưở ế ạ ộ ủ ệ ố
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 a m t h m t ch đ c phép ph thu c vào s bí m t c a khóa". ủ ộ ệ ậ ỉ ượ ụ ộ ự ậ ủ
4. Phân lo i h m tạ ệ ậ
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óấ ể ễ ướ ạ ị ủ ướ ổ
đ c tính nh th , nên hash là m t l p mã hõa đ c bi t ki m tra tính toàn v n c a thôngặ ư ế ộ ớ ặ ệ ể ẹ ủ
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 i đ c.ậ ừ ầ ư ả ượ
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 m t thì r t khó và h u nh là không th tính đ c t khóa công khai. Nh ng khácậ ấ ầ ư ể ượ ừ ư
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ố