TR NG Đ I H C S PH M HÀ N IƯỜ Ạ Ọ Ư Ạ Ộ
KHOA CÔNG NGH THÔNG TINỆ
------------------------
NGHIÊN C U KHOA H CỨ Ọ
Đ tài:ề
TÌM HI U M T MÃ H C VÀ NG D NG Ể Ậ Ọ Ứ Ụ
TRONG XÁC TH C CH KÝ ĐI N TỰ Ữ Ệ Ử
Giáo viên h ng d n:ướ ẫ PGS.TS.Vũ Đình Hòa
Sinh viên th c hi n:ự ệ Tr nh Mai H ngị ươ
Hà n i ,2008ộ
M c l cụ ụ
L i nói đ uờ ầ ............................................................................................................. 4
Ch ng 1.T ng quan v m t mã h cươ ổ ề ậ ọ ................................................................ 5
1.1.L ch s phát tri n c a m t mãị ử ể ủ ậ ..................................................................... 5
1.1.1.M t mã h c c đi nậ ọ ổ ể ..................................................................................................... 5
1.1.2.Th i trung cờ ổ ................................................................................................................. 6
1.1.4.M t mã h c trong Th chi n IIậ ọ ế ế .................................................................................... 8
1.1.5.M t mã h c hi n đ iậ ọ ệ ạ .................................................................................................. 11
1.2.M t s thu t ng s d ng trong h m t mãộ ố ậ ữ ử ụ ệ ậ .................................................................... 16
1.3.Đ nh nghĩa m t mã h cị ậ ọ ...................................................................................................... 20
1.4.Phân lo i h m t mã h cạ ệ ậ ọ .................................................................................................. 22
1.4.1.M t mã c đi n (cái này ngày nay v n hay dùng trong trò ch i tìm m t th ).ậ ổ ể ẫ ơ ậ ư
D a vào ki u c a phép bi n đ i trong h m t mã c đi n, ng i ta chia h m tự ể ủ ế ố ệ ậ ổ ể ườ ệ ậ
mã làm 2 nhóm: mã thay th (substitution cipher) và mã hoán v (permutation/ế ị
transposition cipher). ............................................................................................................ 22
1.4.2.M t mã hi n đ iậ ệ ạ ......................................................................................................... 24
Ch ng 2.H m t mã c đi nươ ệ ậ ổ ể .......................................................................... 28
2.1.H mã Caesarệ ..................................................................................................................... 28
2.2.H mã Affinneệ .................................................................................................................... 30
2.3.H mã Vigenèreệ ................................................................................................................. 32
2.4.H m t Hillệ ậ ........................................................................................................................ 33
2.5. H m t Playfairệ ậ ................................................................................................................. 35
Ch ng 3. M t s công c h tr cho thuy t m t mãươ ộ ố ụ ỗ ợ ế ậ ................................. 36
3.1.Lý thuy t sế ố ....................................................................................................................... 36
3.1.1.Ki n th c đ ng d th cế ứ ồ ư ứ ............................................................................................. 36
3.1.2.M t s đ nh lý s d ng trong thu t mã hóa công khaiộ ố ị ử ụ ậ .............................................. 38
3.2.Lý thuy t đ ph c t pế ộ ứ ạ ....................................................................................................... 44
Ch ng 4. H m t mã công khaiươ ệ ậ ...................................................................... 48
4.1.Gi i thi u m t mã v i khóa công khaiớ ệ ậ ớ .............................................................................. 48
4.1.1.L ch sị ử ......................................................................................................................... 48
4.1.2.Lý thuy t m t mã công khaiế ậ ....................................................................................... 50
4.1.3.Nh ng y u đi m, h n ch c a m t mã v i khóa công khaiữ ế ể ạ ế ủ ậ ớ .................................... 52
4.1.4. ng d ng c a m t mãỨ ụ ủ ậ ................................................................................................ 53
4.2.H m t RSAệ ậ ....................................................................................................................... 55
4.2.1.L ch sị ử ......................................................................................................................... 55
4.2.2.Mô t thu t toánả ậ .......................................................................................................... 56
b. Mã hóa .............................................................................................................................. 58
c. Gi i mãả ............................................................................................................................. 58
Ví dụ ..................................................................................................................................... 59
4.2.3.T c đ mã hóa RSAố ộ .................................................................................................... 60
4.2.4.Đ an toàn c a RSAộ ủ .................................................................................................... 62
4.2.5.S che d u thông tin trong h th ng RSAự ấ ệ ố ................................................................. 65
4.3.H m t Rabinệ ậ ..................................................................................................................... 68
4.3.1.Mô t gi i thu t Rabinả ả ậ ............................................................................................... 68
4.3.2.Đánh giá hi u quệ ả ....................................................................................................... 69
4.4.Ch ký đi n tữ ệ ử ................................................................................................................... 70
4.4.1.Đ nh nghĩaị ................................................................................................................... 72
4.4.2.Hàm băm ...................................................................................................................... 73
4.4.3.M t s s đ ch ký đi n tộ ố ơ ồ ữ ệ ử ..................................................................................... 76
Ch ng 5. Xây d ng ph n m m ng d ngươ ự ầ ề ứ ụ .................................................... 83
5.1.Đ nh nghĩa bài toánị ............................................................................................................. 83
5.2.Phân tích và thi t kế ế .......................................................................................................... 83
5.2.1. Quá trình ký trong Message ........................................................................................ 85
5.2.2. Quá trình ki m tra xác nh n ch ký trên tài li u.ể ậ ữ ệ ..................................................... 86
5.3.Ch ng trình cài đ tươ ặ .......................................................................................................... 89
Ch ng trình ch y trên h u h t các h đi u hành c a windows. Cài đ t b ng ngôn ng C#ươ ạ ầ ế ệ ề ủ ặ ằ ữ
trên môi tr ng Visual Studio 2005. ườ ....................................................................................... 89
L i nói đ uờ ầ
Hi n nay , công ngh thông tin, công ngh Internet, công ngh E-mail, E-ệ ệ ệ ệ
business phát tri n nh vũ bão.Vi t Nam đã, đang t ng b c áp d ng công nghể ư ệ ừ ướ ụ ệ
m i đ “tin h c hóa xã h i” t c là đ a tin h c vào các lĩnh v c c a xã h i đớ ể ọ ộ ứ ư ọ ự ủ ộ ể
c i thi n ho t đ ng th công tr c đây.Tin h c hóa đã gi i phóng s c lao đ ngả ệ ạ ộ ủ ướ ọ ả ứ ộ
c a con ng i b ng cách sáng ch máy hút b i, máy gi t , máy r a bát, các conủ ườ ằ ế ụ ặ ử
robot làm vi c trong h m m -n i r t nguy hi m và đ c h i cho s c kh e c aệ ầ ỏ ơ ấ ể ộ ạ ứ ỏ ủ
con ng i…ườ
Ngoài ra,Tin h c còn đ c đ a vào qu n lý hành chính Nhà n c.Trongọ ượ ư ả ướ
giai đo n 2001-2005, Th t ng Phan Văn Kh i phê duy t nhi u đ án tin h cạ ủ ướ ả ệ ề ề ọ
hóa qu n lý hành chính Nhà n c v i m c tiêu quy t tâm xây d ng m t Chínhả ướ ớ ụ ế ự ộ
ph đi n t Vi t Nam.N u đ án này thành công thì ng i dân có th tìmủ ệ ử ở ệ ế ề ườ ể
hi u thông tin c n thi t v n mang tính gi y t nh gi y khai sinh, khai t , đăngể ầ ế ố ấ ờ ư ấ ử
kí l p h c, xin thành l p doanh nghi p,xin c p h chi u, xin b o h tác quy nớ ọ ậ ệ ấ ộ ế ả ộ ề
hay quy n s h u công nghi p…thông qua đ a ch m ng mà không c n ph iề ở ữ ệ ị ỉ ạ ầ ả
đ n c quan hành chính.Nh v y chúng ta có th trao đ i m i thông tin quaế ơ ư ậ ể ổ ọ
m ng.Thông tin mà chúng ta g i đi có th là thông tin quân s , tài chính, kinhạ ử ể ự
doanh ho c đ n gi n là m t thông tin nào đó mang tính riêng tặ ơ ả ộ ư…Đi u này d nề ẫ
t i m t v n đ x y ra là Internet là môi tr ng không an toàn, đ y r i ro vàớ ộ ấ ề ả ườ ầ ủ
nguy hi m, không có gì đ m b o r ng thông tin mà chúng ta truy n đi không bể ả ả ằ ề ị
đ c tr m trên đ ng truy n. Do đó, m t bi n pháp đ c đ a ra nh m giúpọ ộ ườ ề ộ ệ ượ ư ằ
chúng ta t b o v chính mình cũng nh nh ng thông tin mà chúng ta g i đi làự ả ệ ư ữ ử
c n ph i mã hóa thông tin.Ngày nay bi n pháp này đ c nhi u n i s d ng nhầ ả ệ ượ ề ơ ử ụ ư
là công c đ b o v an toàn cho b n thân.M t ví d đi n hình các ngân hàngụ ể ả ệ ả ộ ụ ể
l i d ng tính năng c a mã hóa đã tích h p công nghê ch ký s vào các giaoợ ụ ủ ợ # ữ ố
d ch th ng mai điên t tr c tuyên, đ m b o tính toàn v n cua d liêu, tính biị ươ # # ư$ ư# % ả ả ẹ $ ư' # %
mât, tính ch ng chôi bo giao dich (băng ch ng) trong các giao d ch th ng mai# ố % $ # ( ư% ị ươ #
điên t online…# ư$
Vì l đó m c đích chính c a lu n văn là tìm hi u lý thuy t m t mã đ đ aẽ ụ ủ ậ ể ế ậ ể ư
lý thuy t ng d ng vào th c t .ế ứ ụ ự ế
Ch ng 1.T ng quan v m t mã h cươ ổ ề ậ ọ
1.1.L ch s phát tri n c a m t mãị ử ể ủ ậ
M t mã h cậ ọ là m t ngành có l ch s t hàng nghìn năm nay. Trong ph nộ ị ử ừ ầ
l n th i gian phát tri n c a mình (ngo i tr vài th p k tr l i đây), ớ ờ ể ủ ạ ừ ậ ỷ ở ạ l ch s m tị ử ậ
mã h cọ chính là l ch s c a nh ng ph ng pháp m t mã h c c đi n - cácị ử ủ ữ ươ ậ ọ ổ ể
ph ng pháp m t mã hóa v i bút và gi y, đôi khi có h tr t nh ng d ng cươ ậ ớ ấ ỗ ợ ừ ữ ụ ụ
c khí đ n gi n. Vào đ u th k XX, s xu t hi n c a các c c u c khí vàơ ơ ả ầ ế ỷ ự ấ ệ ủ ơ ấ ơ
đi n c , ch ng h n nh máy Enigma, đã cung c p nh ng c ch ph c t p vàệ ơ ẳ ạ ư ấ ữ ơ ế ứ ạ
hi u qu h n cho vi c m t mã hóa. S ra đ i và phát tri n m nh m c a ngànhệ ả ơ ệ ậ ự ờ ể ạ ẽ ủ
đi n t và máy tính trong nh ng th p k g n đây đã t o đi u ki n đ m t mãệ ử ữ ậ ỷ ầ ạ ề ệ ể ậ
h c phát tri n nh y v t lên m t t m cao m i.ọ ể ả ọ ộ ầ ớ
S phát tri n c a m t mã h c luôn luôn đi kèm v i s phát tri n c a cácự ể ủ ậ ọ ớ ự ể ủ
k thu t phá mã (hay thám mã). Các phát hi n và ng d ng c a các k thu tỹ ậ ệ ứ ụ ủ ỹ ậ
phá mã trong m t s tr ng h p đã có nh h ng đáng k đ n các s ki n l chộ ố ườ ợ ả ưở ể ế ự ệ ị
s . M t vài s ki n đáng ghi nh bao g m vi c phát hi n ra b c đi nử ộ ự ệ ớ ồ ệ ệ ứ ệ
Zimmermann khi n Hoa Kỳ tham gia Th chi n 1 và vi c phá mã thành công hế ế ế ệ ệ
th ng m t mã c a Đ c Qu c xã góp ph n làm đ y nhanh th i đi m k t thúcố ậ ủ ứ ố ầ ẩ ờ ể ế
th chi n II.ế ế
Cho t i đ u th p k 1970, các k thu t liên quan t i m t mã h c h u nhớ ầ ậ ỷ ỹ ậ ớ ậ ọ ầ ư
ch n m trong tay các chính ph . Hai s ki n đã khi n cho m t mã h c tr nênỉ ằ ủ ự ệ ế ậ ọ ở
thích h p cho m i ng i, đó là: s xu t hi n c a tiêu chu n m t mã hóa DESợ ọ ườ ự ấ ệ ủ ẩ ậ
và s ra đ i c a các k thu t m t mã hóa khóa công khai.ự ờ ủ ỹ ậ ậ
1.1.1.M t mã h c c đi nậ ọ ổ ể
Nh ng b ng ch ng s m nh t v s d ng m t mã h c là các ch t ngữ ằ ứ ớ ấ ề ử ụ ậ ọ ữ ượ
hình không tiêu chu n tìm th y trên các b c t ng Ai C p c đ i (cách đâyẩ ấ ứ ượ ậ ổ ạ
kho ng 4500). Nh ng ký hi u t ra không ph i đ ph c v m c đích truy nả ữ ệ ỏ ả ể ụ ụ ụ ề
thông tin bí m t mà có v nh là nh m m c đích g i nên nh ng đi u th n bí, tríậ ẻ ư ằ ụ ợ ữ ề ầ
tò mò ho c th m chí đ t o s thích thú cho ng i xem. Ngoài ra còn r t nhi uặ ậ ể ạ ự ườ ấ ề