Đề 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ử

ơ RSA t 1000 t i 10000 l n tùy thu c công c (implementation) s d ng (thôngừ ớ ầ ộ ụ ử ụ tin này đ c l y t ượ ấ ừ Kích th c c a khóa trong RSA:ướ ủ Hi u qu c a m t h th ng m t mã khóa b t đ i x ng ph thu c vào ệ ả ủ ộ ệ ố ậ ấ ố ứ ụ ộ đ khóộ (lý thuy t ho c tính toán) c a m t v n đ toán h c nào đó ch ng h n nh bàiế ặ ủ ộ ấ ề ọ ẳ ạ ư toán phân tích ra th a s nguyên t . Gi i các bài toán này th ng m t nhi uừ ố ố ả ườ ấ ề th i gian nh ng thông th ng v n nhanh h n là th l n l t t ng khóa theoờ ư ườ ẫ ơ ử ầ ượ ừ ki u duy t toàn b . Vì th , khóa dùng trong các h th ng này c n ph i dài h nể ệ ộ ế ệ ố ầ ả ơ trong các h th ng m t mã khóa đ i x ng. T i th i đi m năm 2002, đ dàiệ ố ậ ố ứ ạ ờ ể ộ 1024 bít đ c xem là giá tr t i thi u cho h th ng s d ng thu t toán RSA.ượ ị ố ể ệ ố ử ụ ậ Năm 2003, công ty RSA Security cho r ng khóa RSA 1024 bít có đ an toànằ ộ t ng đ ng v i khóa 80 bít, khóa RSA 2048 bít t ng đ ng v i khóa 112 bítươ ươ ớ ươ ươ ớ và khóa RSA 3072 bít t ng đ ng v i khóa 128 bít c a h th ng m t mã khóaươ ươ ớ ủ ệ ố ậ đ i x ng. H cũng đánh giá r ng, khóa 1024 bít có th b phá v trong kho ngố ứ ọ ằ ể ị ỡ ả t 2006 t i 2010 và khóa 2048 bít s an toàn t i 2030. Các khóa 3072 bít c nừ ớ ẽ ớ ầ đ c s d ng trong tr ng h p thông tin c n gi bí m t sau 2030. Các h ngượ ử ụ ườ ợ ầ ữ ậ ướ d n v qu n lý khóa c a NIST cũng g i ý r ng khóa RSA 15360 bít có đ anẫ ề ả ủ ợ ằ ộ toàn t ng đ ng v i khóa đ i x ng 256 bít.ươ ươ ớ ố ứ M t d ng khác c a thu t toán m t mã hóa khóa b t đ i x ng, m t mãộ ạ ủ ậ ậ ấ ố ứ ậ đ ng cong elliptic (ECC), t ra an toàn v i khóa ng n h n khá nhi u so v i cácườ ỏ ớ ắ ơ ề ớ thu t toán khác. H ng d n c a NIST cho r ng khóa c a ECC ch c n dài g pậ ướ ẫ ủ ằ ủ ỉ ầ ấ đôi khóa c a h th ng khóa đ i x ng. Gi đ nh này đúng trong tr ng h pủ ệ ố ố ứ ả ị ườ ợ không có nh ng đ t phá trong vi c gi i các bài toán mà ECC đang s d ng. M tữ ộ ệ ả ử ụ ộ văn b n mã hóa b ng ECC v i khóa 109 bít đã b phá v b ng cách t n côngả ằ ớ ị ỡ ằ ấ duy t toàn b .ệ ộ Tùy thu c vào kích th c b o m t c a m i ng i và th i gian s ng c a khóaộ ướ ả ậ ủ ỗ ườ ờ ố ủ mà khóa có chi u dài thích h pề ợ - lo i Export 512 bitạ - lo i Person 768 bitạ - lo i Commercial 1024 bitạ - lo i Militery 2048 bitạ Chu kỳ s ng c a khóa ph thu c vàoố ủ ụ ộ - vi c đăng ký và t o khóaệ ạ - vi c phân b khóaệ ố - vi c kích ho t và không kích ho t khóaệ ạ ạ - vi c thay th ho c c p nh t khóaệ ế ặ ậ ậ - vi c h y b khóaệ ủ ỏ - vi c k t thúc khóa bao g m s phá ho i ho c s l u trệ ế ồ ự ạ ặ ự ư ữ 4.2.4.Đ an toàn c a RSAộ ủ Đ an toàn c a h th ng RSA d a trên 2 v n đ c a toán h c: bài toánộ ủ ệ ố ự ấ ề ủ ọ phân tích ra th a s nguyên t các s nguyên l n và bài toán RSA. N u 2 bàiừ ố ố ố ớ ế toán trên là khó (không tìm đ c thu t toán hi u qu đ gi i chúng) thì khôngượ ậ ệ ả ể ả th th c hi n đ c vi c phá mã toàn b đ i v i RSA. Phá mã m t ph n ph iể ự ệ ượ ệ ộ ố ớ ộ ầ ả đ c ngăn ch n b ng các ph ng pháp chuy n đ i b n rõ an toàn.ượ ặ ằ ươ ể ổ ả Bài toán RSA là bài toán tính căn b c ậ e môđun n (v i ớ n là h p s ): tìm sợ ố ố m sao cho me=c mod n, trong đó (e, n) chính là khóa công khai và c là b n mã.ả Hi n nay ph ng pháp tri n v ng nh t gi i bài toán này là phân tích ệ ươ ể ọ ấ ả n ra th aừ s nguyên t . Khi th c hi n đ c đi u này, k t n công s tìm ra s mũ bí m tố ố ự ệ ượ ề ẻ ấ ẽ ố ậ d t khóa công khai và có th gi i mã theo đúng quy trình c a thu t toán. N uừ ể ả ủ ậ ế k t n công tìm đ c 2 s nguyên t ẻ ấ ượ ố ố p và q sao cho: n = pq thì có th d dàngể ễ tìm đ c giá tr (ượ ị p-1)(q-1) và qua đó xác đ nh ị d t ừ e. Ch a có m t ph ng phápư ộ ươ nào đ c tìm ra trên máy tính đ gi i bài toán này trong th i gian đa th cượ ể ả ờ ứ (polynomial-time). Tuy nhiên ng i ta cũng ch a ch ng minh đ c đi u ng cườ ư ứ ượ ề ượ l i (s không t n t i c a thu t toán). ạ ự ồ ạ ủ ậ T i th i đi m năm 2005, s l n nh t có th đ c phân tích ra th a s nguyênạ ờ ể ố ớ ấ ể ượ ừ ố t có đ dài 663 bít v i ph ng pháp phân tán trong khi khóa c a RSA có đ dàiố ộ ớ ươ ủ ộ t 1024 t i 2048 bít. M t s chuyên gia cho r ng khóa 1024 bít có th s m bừ ớ ộ ố ằ ể ớ ị phá v (cũng có nhi u ng i ph n đ i vi c này). V i khóa 4096 bít thì h u nhỡ ề ườ ả ố ệ ớ ầ ư không có kh năng b phá v trong t ng lai g n. Do đó, ng i ta th ng choả ị ỡ ươ ầ ườ ườ r ng RSA đ m b o an toàn v i đi u ki n ằ ả ả ớ ề ệ n đ c ch n đ l n. N u ượ ọ ủ ớ ế n có đ dàiộ 256 bít ho c ng n h n, nó có th b phân tích trong vài gi v i máy tính cá nhânặ ắ ơ ể ị ờ ớ dùng các ph n m m có s n. N u n có đ dài 512 bít, nó có th b phân tích b iầ ề ẵ ế ộ ể ị ở vài trăm máy tính t i th i đi m năm 1999. M t thi t b lý thuy t có tên làạ ờ ể ộ ế ị ế TWIRL do Shamir và Tromer mô t năm 2003 đã đ t ra câu h i v đ an toànả ặ ỏ ề ộ c a khóa 1024 bít. Vì v y hi n nay ng i ta khuy n cáo s d ng khóa có đ dàiủ ậ ệ ườ ế ử ụ ộ t i thi u 2048 bít.ố ể Năm 1993, Peter Shor công b thu t toán Shor ch ra r ng: máy tính l ng tố ậ ỉ ằ ượ ử (trên lý thuy t) có th gi i bài toán phân tích ra th a s trong th i gian đa th c.ế ể ả ừ ố ờ ứ Tuy nhiên, máy tính l ng t v n ch a th phát tri n đ c t i m c đ nàyượ ử ẫ ư ể ể ượ ớ ứ ộ trong nhi u năm n a.ề ữ Vì khóa là khóa công khai nên ng i gi i mã th ng d a vào c p khóaườ ả ườ ự ặ này đ tìm c p khóa bí m t. Đi u quan tr ng là d a vào n đ tính hai th a sể ặ ậ ề ọ ự ể ừ ố p,q c a n t đó tính đ c d. Có nhi u gi i thu t nh th , đàu tiên ta xét tr ngủ ừ ượ ề ả ậ ư ế ườ h p đ n gi n nh t là ng i gi i mã bi t đ c ợ ơ ả ấ ườ ả ế ượ φ(n). Khi đó tính p,q đ a v vi cư ề ệ gi i hai ph ng trình sau:ả ươ n = p. q φ(n) = (p - 1)(q -1) Thay q= n/p ta đ c ph ng trình b c hai:ượ ươ ậ p2 – (n- φ(n) +1 )p+n=0 Hai nghi m c a ph ng trình b c hai s là p,q. tuy nhiên v n đ có đ c ệ ủ ươ ậ ẽ ấ ề ượ φ(n) còn khó h n tính hai th a s nhi uơ ừ ố ề N u ta ch n các s p,q kho ng 100 ch s th p phân, thì n s có kho ngế ọ ố ả ữ ố ậ ẽ ả 200 ch s th p phân. Đ phân tích m t s nguyên c l n nh th , v i cácữ ố ậ ể ộ ố ỡ ớ ư ế ớ thu t toán nhanh nh t hi n nay và v i nh ng máy tính hi n đ i nh t, ta m tậ ấ ệ ớ ữ ệ ạ ấ ấ hàng t năm.ỷ Có m t vài đi u c n l u ý khi ch n các s p,q đ tránh r i vào tr ng h p tíchộ ề ầ ư ọ ố ể ơ ườ ợ h p c a pq b phân tích nhanh nh nh ng thu t toán đ c bi t: p và q c n ch nợ ủ ị ờ ữ ậ ặ ệ ầ ọ sao cho p-1 và q-1 không ch có toàn c nguyên t nh . Ngoài ra, UCLN(p-1,q-ỉ ướ ố ỏ 1) ph i là s nh , p và q ph i có ch s trong khai tri n th p phân khác nhauả ố ỏ ả ữ ố ể ậ không nhi u.ề M t nh n đ nh chung là t t c các cu c t n công gi i mã đ u mang m c đíchộ ậ ị ấ ả ộ ấ ả ề ụ không t t. Tính b o m t c a RSA ch y u d a vào vi c gi bí m t khóa gi iố ả ậ ủ ủ ế ự ệ ữ ậ ả mã hay gi bí m t các th a s p,q c a n. Ta th xét m t vài ph ng th c t nữ ậ ừ ố ủ ử ộ ươ ứ ấ công đi n hình c a k đ ch nh m gi i mã trong thu t toán này(nh m xâm ph mể ủ ẻ ị ằ ả ậ ằ ạ t i các y u t bí m t đó).ớ ế ố ậ • Tr ng h p 1: Chúng ta xét đ n tr ng h p khi k đ ch nào đó bi t đ cườ ợ ế ườ ợ ẻ ị ế ượ modulo n, khóa công khai KB và b n tin mã hóa C, khi đó k đ ch s tìm raả ẻ ị ẽ b n tin g c (plaintext) nh th nào. Đ làm đ c đi u đó k đ ch th ngả ố ư ế ể ượ ề ẻ ị ườ t n công vào h th ng m t mã b ng hai ph ng th c sau đây:ấ ệ ố ậ ằ ươ ứ - ph ng th c th nh t: Tr c tiên d a vào phân tích th a sôươ ứ ứ ấ ướ ự ừ modulo n. T p theo sau chúng s tìm cách tính otans ra hai th a sế ẽ ừ ố p,q và có kh năng thành công khi đó s tính đ c ả ẽ ượ φ(n)=(p-1)(q-1) và khóa bí m t Kậ B. Ta th y n c n ph i là tích c a hai s nguyên t ,ấ ầ ả ủ ố ố vì n u n là tích c a hai s nguyên t thì thu t toán phân tích th aế ủ ố ố ậ ừ s đ n gi n c n t i đa nố ơ ả ầ ố 1/2 b c, b i vì có m t s nguyên t nhướ ở ộ ố ố ỏ h n nơ 1/2. M t khác, nêu sn là tích c a n s nguyên t thì thu t phânặ ủ ố ố ậ tích th a sô đ n gi n c n nừ ơ ả ầ 1/n b c.ướ - Ph ng th c th hai: ph ng th c t n công th hai vào h mã hóaươ ứ ứ ươ ứ ấ ứ ệ RSA là có th kh i đ u b ng cách gi i quy t tr ng h p thích h pể ở ầ ằ ả ế ườ ợ ợ c a bàn toán logarit r i r c. Tr ng h p này k đ ch đã có trong tayủ ờ ạ ườ ợ ẻ ị b n mã C và khóa công khai Kả B t c là c p (Kứ ặ B,C) • Tr ng h p 2: Chúng ta xét tr ng h p khi k đ ch bi t đ c modul n vàườ ợ ườ ợ ẻ ị ế ượ φ(n), khi đó k đ ch s tìm ra b n g c (plaintext) b ng cách sau:ẻ ị ẽ ả ố ằ Bi t ế φ(n) thì có th tính p,q theo h ph ng trình:ể ệ ươ pq=n, (p-1)(q-1)= φ(n) do đó p,q là hai nghi m c a ph ng trình b c hai:ệ ủ ươ ậ p2 – (n- φ(n) +1 )p+n=0 Ví d n=84773093 và bi t ụ ế φ(n) =84754668. Gi i ph ng trình b c hai t ngả ươ ậ ươ ng ta s đ c hai nghi m p=9539, q=8887.ứ ẽ ượ ệ 4.2.5.S che d u thông tin trong h th ng RSAự ấ ệ ố H th ng RSA có m t đ c đi m đ c tr ng là thông tin không ph i luôn luônệ ố ộ ặ ể ặ ư ả đ c che d u. Gi s ng i g i có e= 17, n=35. N u anh ta mu n g i b t cượ ấ ả ử ườ ử ế ố ử ấ ứ data nào thu c t p sau:ộ ậ {1,6,7,8,13,14,15,20,21,22,27,28,29,34} Thì m i m t mã cũng chính là data ban đ u. Nghĩa là: M=Mọ ậ ầ e mod n. Còn khi p=109, q=97, e= 865 thì h th ng hoàn toàn không có s che d u thông tin b iệ ố ự ấ ở vì: M=Me mod (109*97) v i m i Mớ ọ V i m i modul n, không che d u đ c ít nh t 9 message:ớ ỗ ấ ượ ấ M=Me mod n(1) Hay M=Me mod p và M=Me mod q(2) V i m i e,(2) có ít nh t 3 gi i pháp thu c t p {-1,0,1}. Do đó t t c messageớ ỗ ấ ả ộ ậ ấ ả th a (1) là: {M=[M(mod p), M(mod q)] | M(mod p), M(mod q)ỏ ∈{-1,0,1}} Đ xác đ nh chính xác s message không đ c che d u (không b thay đ i sauể ị ố ượ ấ ị ổ khi mã hóa) ta s d ng đ nh lý sau: “N u các message đ c mã hóa trong hử ụ ị ế ượ ệ th ng RSA đ c xác đ nh b i s modul n=pq(p,q, là s nguyên t ) và khóa côngố ượ ị ở ố ố ố khai e thì có: m=[1+UCLN(e-1,p-1)][1+UCLN(e-1,q-1)] message không b cheị d u ”.ấ M t s l u ý khi s d ng h m t mã RSAộ ố ư ử ụ ệ ậ • M i ng i đ u bi t “đi m m nh ” c a h mã v i chìa khóa công khaiọ ườ ề ế ể ạ ủ ệ ớ RSA là d a trên “đi m y u” c a máy tính trong vi c phân tích m t sự ể ế ủ ệ ộ ố nguyên (đ l n) ra các th a s nguyên t . V i th i gian h n 20 năm t nủ ớ ừ ố ố ớ ờ ơ ồ t i trên via trò m t h mã công kahi thông d ng nh t, RSA dã đ ng đ uạ ộ ệ ụ ấ ươ ầ v i các ki u t n công đ lo i c a gi i thám mã chuyên nghi p. K t quớ ể ấ ủ ạ ủ ớ ệ ế ả h n 20 năm “công phá” h mã RSA c a các nhà thám mã đã đ c tómơ ệ ủ ượ l c trong bài báo c a Dan Boneh v i tiêu đ “Hai m i năm t n côngượ ủ ớ ề ươ ấ h mã RSA” (đăng trong t Notice ò the AMS, tháng 2-1999), trong đó choệ ờ th y rõ RSA có th b “b ” khi ng i ta không bi t dùng nó m t cáchấ ể ị ẻ ườ ế ộ “bài b n”. Khi chìa khóa l p mã ho c gi i mã là m t s nguyên t nh thìả ậ ặ ả ộ ố ố ỏ ng i ta có nh ng gi i pháp “b ” RSA m t cách không m y khó khăn.ườ ữ ả ẻ ộ ấ Thêm vào đó, không ph i m i h p s l n đ u khó phân tích(k c khi nóả ọ ợ ố ớ ề ể ả là tích c a 2 s nguyên t r t l n), cho nên vi c ch n các s nguyên tủ ố ố ấ ớ ệ ọ ố ố p,q ph i r t th n tr ng.ả ấ ậ ọ G n đây ng i ta có đ c p đ n kh năng phá h mã RSA b ng các máyầ ườ ề ậ ế ả ệ ằ tính đ c bi t v i các con chip đ c ch ng(chuyên d ng cho vi c phân tích s )ặ ệ ớ ặ ủ ụ ệ ố ho c dùng thu t toán song song. M c dù h a h n nh ng ti n b v t b cặ ậ ặ ứ ẹ ữ ế ộ ượ ậ nh ng kh năng này v n ch a tr thành hi n th c trong t ng lai g n, nh t làư ả ẫ ư ở ệ ự ươ ầ ấ chu n c a RSA đ c nâng cao thêm m t b cẩ ủ ượ ộ ậ • Trong các h mã RSA, m t b n tin có th đ c mã hóa trong th i gianệ ộ ả ể ượ ờ tuy n tính ế Đ i v i các b n tin dài, đ dài c a các s đ c dùng cho các khóa có thố ớ ả ộ ủ ố ượ ể đ c coi nh là h ng. T ng t nh v y, nâng m t s lên lũy th a đ c th cượ ư ằ ươ ự ư ậ ộ ố ừ ượ ự hi n trong th i gian h ng, các s không đ c phép dài h n m t đ dài h ng.ệ ờ ằ ố ượ ơ ộ ộ ằ Th c ra tham s này che d u nhi u chi ti t cài đ t có liên quan đ n vi c tínhự ố ấ ề ế ặ ế ệ toán v i các con s dài, chi phí c a các phép toán th c s là m t y u t ngănớ ố ủ ự ự ộ ế ố c n s ph bi n ng d ng c a ph ng pháp này. Ph n quan tr ng nh t c aả ự ổ ế ứ ụ ủ ươ ầ ọ ấ ủ vi c tính toán có liên quan đ n vi c mã hóa b n tin. Nh ng ch c ch n là sệ ế ệ ả ư ắ ắ ẽ không có h mã hóa nào h t n u không tính đ c các khóa c a chúng là các sệ ế ế ượ ủ ố l n.ớ • Các khóa cho h mã hóa RSA có th đ c t o ra mà không ph i tính toánệ ể ượ ạ ả quá nhi u.ề M t l n n a ta nói đ n các ph ng pháp ki m tra s nguyên t . M i s nguyênộ ầ ữ ế ươ ể ố ố ỗ ố t l n có th đ c phát sinh băng cách đ u tiên t o ra m t s ng u nhiên l n,ố ớ ể ượ ầ ạ ộ ố ẫ ớ sau đó ki m tra các s k ti p cho t i khi tìm đ c m t s nguyên t . M tể ố ế ế ớ ượ ộ ố ố ộ ph ng pháp đ n gi n th c hi n m t phép tính trên m t con s ng u nhiên, v iươ ơ ả ự ệ ộ ộ ố ẫ ớ xác su t ½ s ch ng minh r ng s đ c ki m tra không ph i nguyên t . B cấ ẽ ứ ằ ố ượ ể ả ố ướ cu i cùng tính p d a vào thu t toán Euclidố ự ậ Nh ph n trên đã trình bày trong h mã hóa công khai thì khóa gi i mã (privateư ầ ệ ả key) kB và các th a s p,q là đ c gi bí m t và s thành công c a ph ng phápừ ố ượ ữ ậ ự ủ ươ là tùy thu c vào k đ ch có kh năng tìm ra đ c giá tr c a kộ ẻ ị ả ượ ị ủ B hay không n uế cho tr c n và Kướ B .R t khó có th tìm ra đ c kấ ể ượ B t Kừ B, c n bi t v p, q.Nhầ ế ề ư v y c n phân tích n ra thành th a s đ tính p,q. Nh ng vi c tính phân tích raậ ầ ừ ố ể ư ệ th a s là m t vi c làm t n r t nhi u th i gian, v i k thu t hi n đ i ngày nayừ ố ộ ệ ố ấ ề ờ ớ ỹ ậ ệ ạ thì c n t i hang tri u năm đ phan tích m t s có 200 ch s ra th a s .ầ ớ ệ ể ộ ố ữ ố ừ ố Đ an toàn c a thu t toán RSA d a trên c s nh ng khó khăn c a vi c xácộ ủ ậ ự ơ ở ữ ủ ệ đ nh các th a s nguyên t c a m t s l n. B ng d i đây cho bi t các th iị ừ ố ố ủ ộ ố ớ ả ướ ế ờ gian d đoán, gi s r ng m i phép toán th c hi n trong m t micro giâyự ả ử ằ ỗ ự ệ ộ S các ch số ữ ố trong s đ c phânố ượ tích Th i gian phânờ tích 50 4 giờ 75 104 giờ 100 74 năm 200 4.000.000 năm 300 5x 1015 năm 500 4x 1025 năm 4.3.H m t Rabinệ ậ H th ng mã hoá Rabin: có th xem nh g n gũi v i RSA, m c dù nó cóệ ố ể ư ầ ớ ặ quá trình gi i mã khác. Đi u thú v là s phá mã C a Rabin t ng v i vi c phânả ề ị ự ủ ươ ớ ệ tích th a s . ừ ố Rabin s d ng lũa th a c a 2 (hay b t kì m t s t nhiên nào) thay thử ụ ừ ủ ấ ộ ố ự ế cho các s nguyên t nh trong RSA. Đi u này d n t i 2 k t qu sau: Tr cố ố ư ề ẫ ớ ế ả ướ tiên, h th ng mã hoá Rabin t ng đ ng v i vi c phân tích th a s , th 2 vi cệ ố ươ ươ ớ ệ ừ ố ứ ệ gi i mã tr nên khó khăn h n, ít ra là v c m giác. V n đ ti p theo là làm saoả ỏ ơ ề ả ấ ề ế đ bi t đ u ra c a ti n trình gi i mã là đúng.ể ế ầ ủ ế ả 4.3.1.Mô t gi i thu t Rabinả ả ậ a. T o khóaạ M i đ u t o m t khóa công khai và m t khóa bí m t t ng ng theo các b cỗ ầ ạ ộ ộ ậ ươ ứ ướ sau: (1) T o hai s nguyên l n, ng u nhiên và phân bi t p và q có kích th c x pạ ố ớ ẫ ệ ướ ấ x nhauỉ (2) Tính n=pq (3) Khóa công khai là n, khóa bí m t là c p s (p,q)ậ ặ ố b. Mã hóa A ph i th c hi n các b c sau:ả ự ệ ướ (1) Nh n khóa công khai c a B: nậ ủ (2) Bi u th b n tin d i d ng m t s nguyên m n m trong d i [0,n-1]ể ị ả ướ ạ ộ ố ằ ả (3) Tính c=m2 mod n (4) G i b n mã c cho Bử ả c. Gi i mãả Đ khôi ph c b n rõ m t c, B ph i th c hi n các b c sau: Tìm 4 cănể ụ ả ừ ả ự ệ ướ b c hai c a c mod n là mậ ủ 1, m2, m3 ho c mặ 4 Thông báo cho ng i g i là m t trong 4 giá tr mườ ử ộ ị 1, m2, m3 ho c mặ 4 , b ng m tằ ộ cách nào đó B s quy t đ nh m là giá tr nàoẽ ế ị ị Ví dụ • T o khóa:B ch n các s nguyên t p=277 và q=331. B tính n=277*331=ạ ọ ố ố 91687.Khóa công khai c a B là 91687. Khóa bí m t c a A là c p sủ ậ ủ ặ ố (p=277, q=331) • Mã hóa:Gi s 6 bit cu i cùng c a b n g c đ c l p l i tr c khi th cả ử ố ủ ả ố ượ ặ ạ ướ ự hi n mã hóa. Vi c thêm vào các bit th a này nh m giúp cho bên gi i mãệ ệ ừ ằ ả nh n bi t đ c b n mã đúngậ ế ượ ả Đ mã hóa ban tin 10 bit m=1001111001, A s l p l i 6 bit cu i cùng c a m để ẽ ặ ạ ố ủ ể có đ c b n tin 16 bit sau: m=1001111001111001, bi u di n th p phân t ngượ ả ể ễ ậ ươ ng là m=40569ứ Sau đó A tính c = m2 mod n = 405692 mod 91687 = 62111 r i g i c cho Bồ ử • Gi i mã:Đ gi i mã b n mã c, B tính b n giá tr căn b c hai c a c mod n:ả ể ả ả ố ị ậ ủ m1 = 69654, m2 = 220033, m3 = 40596, m4 = 51118 Bi u di n nh phân t ng ng c a các s trên là :ể ễ ị ươ ứ ủ ố m1 = 10001000000010110, m2 = 101011000010001, m3 = 1001111001111001, m4 = 1100011110101110 vì ch có mỉ 3 m i scos đ th a c n thi t nên B s gi i mã c b ng mơ ộ ừ ầ ế ẽ ả ằ 3 và khôi ph c b n tin g c là m = 1001111001ụ ả ố 4.3.2.Đánh giá hi u quệ ả Thu t gi i mã hóa Rabin là m t thu t toán c c kỳ nhanh vì nó ch c nậ ả ộ ậ ự ỉ ầ th c hi n m t phép bình ph ng modulo đ n gi n. Trong khi đó, ch ng h nự ệ ộ ươ ơ ả ẳ ạ v i thu t toán RSA có e = 3 ph i c n t i m t phép nhân modulo và m t phépớ ậ ả ầ ớ ộ ộ bình ph ng modulo. Thu t toán gi i mã Rabin có ch m h n thu t toán mã hóa,ươ ậ ả ậ ơ ậ tuy nhiên v m t t c đ nó cũng t ng đ ng v i thu t toán gi i mã RSAề ặ ố ộ ươ ươ ớ ậ ả 4.4.Ch ký đi n tữ ệ ử H ng ngày, chúng ta v n th ng hay dùng ch ký đ xác minh m t v nằ ẫ ườ ữ ể ộ ấ đ , hay xác nh n quy n c a mình đ i v i m t v t thông nh ng gi y t ho cề ậ ề ủ ố ớ ộ ậ ữ ấ ờ ặ h p đ ng nào đó. Ch ng h n nh tên m t b c đi n nh n ti n t ngân hàng, hayợ ồ ẳ ạ ư ộ ứ ệ ậ ề ừ nh ng h p đ ng ký k t mua bán, chuy n nh ng… Nh ng ch ký đó là ch kýữ ợ ồ ế ể ượ ữ ữ ữ vi t tay. Nh ng y u t nào đã làm nên “s c thuy t ph c” c a nó ?ế ữ ế ố ứ ế ụ ủ V m t lý t ng:ề ặ ưở - Ch ký là b ng ch ng th hi n ng i ký có ch đ nh ký văn b n ữ ằ ứ ể ệ ườ ủ ị ả - Ch ký th hi n “ch quy n ”, nó làm cho ng i nh n văn b n bi t r ngữ ể ệ ủ ề ườ ậ ả ế ằ ai đích th là ng i đã ký văn b nị ườ ả - Ch ký không th “tái s d ng đ c” , t c là nó là ph n c a văn b n màữ ể ử ụ ượ ứ ầ ủ ả không th sao chép sang văn b n khácể ả - Văn b n đã ký không th thay đ i đ cả ể ổ ượ - Ch ký không th gi i m o và cũng là th không th ch i bữ ể ả ạ ứ ể ố ỏ Trong cu c s ng, m i th không di n ra theo đúng “mô hình lý t ng” nêuộ ố ọ ứ ễ ưở trên, nh ng v i kh năng ki m đ nh sát sao thì vi c làm khác đi không ph i làư ớ ả ể ị ệ ả d . Chúng ta có lý do đ mang mô hình này vào th gi i máy tính, nh ng cóễ ể ế ớ ư nh ng khó khăn hi n nhiên: các dòng thông tin trên máy tính đ c sao chép m tữ ể ượ ộ cách quá d dàng, hình nh c a ch ký tay c a m t ng i nào đó dù khó b tễ ả ủ ữ ủ ộ ườ ắ ch c t i đâu cũng d dàng sao chép t văn b n này sang văn b n khác…ướ ớ ễ ừ ả ả Đ có các đ c tính nh đã mô t trên , giao th c ký trong th gi i đi n t c nể ặ ư ả ứ ế ớ ệ ử ầ t i s h tr c a công ngh mã hóa. Đó là ch ký đi n t (ớ ự ỗ ợ ủ ệ ữ ệ ử electronic signature) V căn b n, ch ký đi n t cũng gi ng nh ch vi t tay. Chúng ta dùngề ả ữ ệ ử ố ư ữ ế nó đ xác nh n l i h a hay cam k t c a mình và sau đó không th rút l i đ c.ể ậ ờ ứ ế ủ ể ạ ượ Ch ký đi n t không đòi h i ph i s d ng gi y m c, nó g n đ c đi m nh nữ ệ ử ỏ ả ử ụ ấ ự ắ ặ ể ậ d ng c a ng i ký vào m t b n cam k t nào đó.ạ ủ ườ ộ ả ế Có đ c m t b n ch ng nh n đi n t cũng gi ng nh dùng b ng lái xeượ ộ ả ứ ậ ệ ử ố ư ằ đ xác nh n nh n d ng c a mình. B n có th thi l y đ c b ng lái xe t i Hàể ậ ậ ạ ủ ạ ể ấ ượ ằ ạ N i nh ng nó l i cho phép b n đi u khi n ph ng ti n t i TP HCM. T ng tộ ữ ạ ạ ề ể ươ ệ ạ ươ ự nh v y, b n ch ng nh n đi n t là v t đ kh ng đ nh nhân d ng c a b n trênư ậ ả ứ ậ ệ ử ậ ể ẳ ị ạ ủ ạ Internet v i nh ng ng i ch p nh n nó.ớ ữ ườ ấ ậ Ch ký đi n tữ ệ ử (ti ng anh: ế electronic signature) là thông tin đi kèm theo d li u (văn b n, hình nh, video...) nh m m c đích xác đ nh ng i ch c a dữ ệ ả ả ằ ụ ị ườ ủ ủ ữ li u đó.ệ Ch ký đi n t đ c s d ng trong các giao d ch đi n t . Xu t phát tữ ệ ử ượ ử ụ ị ệ ử ấ ừ th c t , ch ký đi n t cũng c n đ m b o các ch c năng: xác đ nh đ c ng iự ế ữ ệ ử ầ ả ả ứ ị ượ ườ ch c a m t d li u nào đó: văn b n, nh, video, ... d li u đó có b thay đ iủ ủ ộ ữ ệ ả ả ữ ệ ị ổ hay không. Hai khái ni m ch ký s (ệ ữ ố digital signature) và ch ký đi n t (ữ ệ ử electronic signature) th ng đ c dùng thay th cho nhau m c dù chúng không hoàn toànườ ượ ế ặ có cùng nghĩa. Ch ký s ch là m t t p con c a ch ký đi n t (ch ký đi n tữ ố ỉ ộ ậ ủ ữ ệ ử ữ ệ ử bao hàm ch ký s )ữ ố Tuy nhiên các ch ký th a mãn hai đi u ki n c b n sau:ữ ỏ ề ệ ơ ả - Không th gi m o. N u P ký thông bao M băng ch ký S(P,M) thì khôngể ả ạ ế ữ m t ai có th t o đ c c p [M,S(M,P)]ộ ể ạ ượ ặ - Xác th c. N u R nh n đ c c p [M,S(M,P)] đ c coi là c a R thì R cóự ế ậ ượ ặ ượ ủ th ki m tra đ c r ng ch ký có th c s là c a P hay không? Ch có Pể ể ượ ằ ữ ự ự ủ ỉ m i có th t o ra đ c ch ký này và ch ký đ c “g n ch t” v i M.ớ ể ạ ượ ữ ữ ượ ắ ặ ớ Hai yêu c u đ u tiên này là nh ng tr ng i chính trong giao d ch qua máyầ ầ ữ ở ạ ị tính. Hai tính ch t b tr sau là nh ng tính ch t mong mu n đ i v i giaoấ ổ ợ ữ ấ ố ố ớ d ch đ c hoàn t t nh ch ký s :ị ượ ấ ờ ữ ố + không th thay đ i. Sau khi đ c phát M không th thay đ i b i S, R,ể ổ ượ ể ổ ở ho c b i m t k thu tr m nàoặ ở ộ ẻ ộ +không th s d ng l i. M t thông báo tr c đó đ c đ a ra s ngay l pể ử ụ ạ ộ ướ ượ ư ẽ ậ t c b R phát hi nứ ị ệ M t s đ ch ký s th ng ch a hai thành ph n: thu t toán ký và thu tộ ơ ồ ữ ố ườ ứ ầ ậ ậ toán xác minh. Ng i A có th ký b c đi n x dùng thu t toán an toàn. Ch kýườ ể ứ ệ ậ ữ Sig(x) nh n đ c có th ki m tra b ng thu t toán xác minh công khai Ver. Khiậ ượ ể ể ằ ậ cho tr c c p (x,y) thu t toán xác minh cho giá tr TRUE hay FALSE tùy thu cướ ặ ậ ị ộ vào vi c ch ký đ c xác minh nh th nàoệ ữ ượ ư ế 4.4.1.Đ nh nghĩaị M t s đ ch ký đi n t là b năm (ộ ơ ồ ữ ệ ử ộ P, A, K, S,V) th a mãn các đi u ki n sau:ỏ ề ệ 1. P:t p h p h u h n các b c đi n có thậ ợ ữ ạ ứ ệ ể 2. A: t p h p h u h n các ch ký có thậ ợ ữ ạ ữ ể 3. K: không gian các khóa là t p h u h n các khóa có thậ ữ ạ ể 4. V i m i k ớ ỗ ∈ K t n t i m t thu t toán ký Sigồ ạ ộ ậ k ∈ S và m t thu t toán xácộ ậ minh Verk ∈ V M i ỗ Sigk : P→A và Verk: P × A →{TRUE, FALSE} là nh ng hàm sao cho m i b cữ ỗ ứ đi n x ệ ∈P và m i ch ký yỗ ữ ∈A th a mãn ph ng trình sau đây:ỏ ươ TRUE n u y= Sig(x)ế Verk (x,y) = FALSE n u y ≠ Sig(x)ế V i m i k thu c K hàm Sigớ ỗ ộ k và Verk là các hàm có th i gian đa th c. Verờ ứ k sẽ là hàm công khai, Sigk là bí m t. Không th d dàng tính toán đ gi m o chậ ể ễ ể ả ạ ữ ký c a A trên thông đi p x. Nghĩa là x cho tr c, ch có A m i có th tính đ củ ệ ướ ỉ ớ ể ượ y đ Verể k = TRUE. M t s đ ch ký không th an toàn vô đi u ki n vì B cóộ ơ ồ ữ ể ề ệ th ki m tra t t c các ch s y có th có trên thông đi p x nh dùng thu t toánể ể ấ ả ữ ố ể ệ ờ ậ Verk công khai cho đ n khi anh ta tìm th y m t ch ký đúng. Vì th , n u có đế ấ ộ ữ ế ế ủ th i gian, B luôn luôn có th gi m o ch ký c a A. Nh v y gi ng nh tr ngờ ể ả ạ ữ ủ ư ậ ố ư ườ h p h th ng mã khóa công khai, m c đích c a chúng ta là tìm các s đ ch kýợ ệ ố ụ ủ ơ ồ ữ s an toàn v m t tính toánố ề ặ 4.4.2.Hàm băm Chúng ta có th th y r ng các s đ ch ký ch cho phép ký các b c đi nể ấ ằ ơ ồ ữ ỉ ứ ệ nh . Ví d khi dùng DSS, b c đi n 160 bit s đ c ký b ng ch ký dài 320 bit.ỏ ụ ứ ệ ẽ ượ ằ ữ Th c t ta c n các b c đi n dài h n nhi u. Ch ng h n m t tài li u v phápự ế ầ ứ ệ ơ ề ẳ ạ ộ ệ ề lu t có th dài nhi u Megabyte.ậ ể ề M t cách đ n gi i đ gi i bài toán này là ch t các b c đi n dài thành nhi uộ ơ ả ể ả ặ ứ ệ ề đo n 160 bit, sau đó ký lên các đo n đó đ c l p nhau. Đi u này cũng t ng tạ ạ ộ ậ ề ươ ự nh mã m t đo n chu i dài b n rõ b ng cách mã ký t rõ đ c l p b ng cùngư ộ ạ ỗ ả ằ ự ộ ậ ằ m t b n khóa (ví d : ch đ ECB trong DES).ộ ả ụ ế ộ Bi n pháp này có m t s v n đ trog vi c t o ra các ch ký s . Tr cệ ộ ố ấ ề ệ ạ ữ ố ướ h t v i m t b c đi n dài, ta k t thúc b ng m t ch ký r t l n (dài g p đôi b cế ớ ộ ứ ệ ế ằ ộ ữ ấ ớ ấ ứ đi n g c trong tr ng h p DSS). Nh c đi m khác là các s đ ch ký “anệ ố ườ ợ ượ ể ơ ồ ữ toàn” l i ch m vì chúng dùng các ký pháp s h c ph c t p nh sô mũ modulo.ạ ậ ố ọ ứ ạ ư Tuy nhiên , v n đ quan tr ng h n v i phép toán này là b c đi n đã ký có th bấ ề ọ ơ ớ ứ ệ ể ị s p x p l i các đo n khác nhau, ho c m t s đo n trong chúng có th b lo i bắ ế ạ ạ ặ ộ ố ạ ể ị ạ ị lo i b và b c đi n nh n đ c v n ph i xác minh đ c. Ta c n b o v sạ ỏ ứ ệ ậ ượ ẫ ả ượ ầ ả ệ ự nguyên v n c a toàn b b c đi n và đi u này không th th c hi n đ c b ngẹ ủ ộ ứ ệ ề ể ự ệ ượ ằ cách ký đ c l p t ng m u nh c a chúngộ ậ ừ ẩ ỏ ủ Gi i pháp cho t t c các v n đ này là dùng hàm Hash mã khóa công khaiả ấ ả ấ ề nhanh. Hàm này l y m t b c đi n có đ dài tùy ý và t o ra m t b n tóm l cấ ộ ứ ệ ộ ạ ộ ả ượ thông báo có kích th c quy đ nh(160 bit n u dùng DSS). Sau đó b n tóm l cướ ị ế ả ượ thông báo d đ c ký.ẽ ượ Trong ngành m t mã h c, m t ậ ọ ộ hàm băm m t mã h cậ ọ (ti ng Anh:ế Cryptographic hash function) là m t hàm băm v i m t s tính ch t b o m tộ ớ ộ ố ấ ả ậ nh t đ nh đ phù h p vi c s d ng trong nhi u ng d ng b o m t thông tin đaấ ị ể ợ ệ ử ụ ề ứ ụ ả ậ d ng, ch ng h n nh ch ng th c (authentication) và ki m tra tính nguyên v nạ ẳ ạ ư ứ ự ể ẹ c a thông đi p (ủ ệ message integrity). M t hàm băm nh n đ u vào là m t xâu kýộ ậ ầ ộ t dài (hay ự thông đi pệ ) có đ dài tùy ý và t o ra k t qu là m t xâu ký t có độ ạ ế ả ộ ự ộ dài c đ nh, đôi khi đ c g i là ố ị ượ ọ tóm t t thông đi pắ ệ (message digest) ho c ặ ch kýữ số (digital fingerprint). Trong nhi u chu n và ng d ng, hai hàm băm thông d ng nh t là MD5 và SHA-ề ẩ ứ ụ ụ ấ 1. Năm 2005, ng i ta đã tìm ra l i b o m t c a c hai thu t toán trên.ườ ỗ ả ậ ủ ả ậ Ho t đ ng c a m t hàm bămạ ộ ủ ộ Nói r ng, m t hàm băm m t mã h c ph i ho t đ ng càng gi ng v i m t hàmộ ộ ậ ọ ả ạ ộ ố ớ ộ ng u nhiên càng t t, trong khi v n có tính ch t đ n đ nh và tính toán có hi uẫ ố ẫ ấ ơ ị ệ qu .ả M t hàm băm m t mã h c đ c coi là không an toàn n u m t trong các vi cộ ậ ọ ượ ế ộ ệ sau là kh thi v m t tính toán:ả ề ặ • cho m t tóm t t (digest), tìm m t thông đi p (ch a bi t) kh p v i tóm t tộ ắ ộ ệ ư ế ớ ớ ắ đó • tìm các "xung đ t băm" (ộ hash collision), trong đó hai thông đi p khác nhauệ có tóm t t trùng nhau.ắ N u có th th c hi n m t trong hai vi c trên, m t ng i có th t n côngế ể ự ệ ộ ệ ộ ườ ể ấ b ng cách dùng các cách trên đ thay m t thông đi p không đ c xác nh nằ ể ộ ệ ượ ậ (unauthorisez message) vào ch c a m t thông đi p đ c xác nh n.ỗ ủ ộ ệ ượ ậ V lý t ng, vi c tìm hai thông đi p có tóm t t r t gi ng nhau cũng nênề ưở ệ ệ ắ ấ ố không kh thi; ng i ta không mu n m t k t n công có th tìm hi u đ cả ườ ố ộ ẻ ấ ể ể ượ đi u gì đó h u ích v m t thông đi p n u bi t tóm t t.ề ữ ề ộ ệ ế ế ắ Nguyên lý:Khi Bob mu n ký b c đi n x, tr c tiên anh ta xây d ng m t b n tómố ứ ệ ướ ự ộ ả l c thông báo z = h(x) và sau đó tính y = sigượ K (z ). Bob truy n c p (x,y) trênề ặ kênh. Xét th y có th th c hi n xác minh (b i ai đó) b ng cách tr c h t khôiấ ể ự ệ ở ằ ướ ế ph c b n tóm l c thông báo z =h (x) b ng hàm h công khai và sau đó ki m traụ ả ượ ằ ể xem verk (x,y) = true, hay không. B c đi n : x đ dài tùy ýứ ệ ộ ↓ B n tóm l c thông báo:z = h (x) 160 bitả ượ ↓ Ch ký y = sig ữ K(z) 320 bit Chúng ta c n chú ý r ng, vi c dùng hàm hash h không làm gi m s an toàn c aầ ằ ệ ả ự ủ s đ ch ký vì nó là b n tóm l c thông báo đ c ch ký không ph i là b cơ ồ ữ ả ượ ượ ữ ả ứ đi n. Đi u c n thi t đ i v i h là c n th a mãn m t s tính ch t nào đó đ tranhệ ề ầ ế ố ớ ầ ỏ ộ ố ấ ể s gi m oự ả ạ Ki u t n công thông th ng là Oscar b t đ u b ng m t b c đi n đ cể ấ ườ ắ ầ ằ ộ ứ ệ ượ ký h p l (x,y), y= sigợ ệ K(h (x)),(C p (x, y) là b c đi n b t kỳ đ c Bob ký tr cặ ứ ệ ấ ượ ướ đó). Sau đó anh ta tính z = h(x) và th tìm x ử ≠ x’ sao cho h(x’) = h(x). N u Oscarế làm đ c nh v y,(x’,y) s là b c đi n h p l , t c m t b c đi n gi m o. Đượ ư ậ ẽ ứ ệ ợ ệ ứ ộ ứ ệ ả ạ ể tránh ki u t n công này, h c n th a mãn tính không va ch m t c là b c đi n xể ấ ầ ỏ ạ ứ ứ ệ không th ti n hành v m t tính toán đ tìm m t b c đi n x ể ế ề ặ ể ộ ứ ệ ≠ x’ sao cho h(x’) = h(x) M t ki u t n công ki u khác nh sau: tr c h t Oscar tìm hai b c đi n x ộ ể ấ ể ư ướ ế ứ ệ ≠ x’ sao cho h(x) = h(x’). Sau đó Oscar đ a cho Bob thuy t ph c Bob ký b n tómư ế ụ ả l c thông báo h(x) đ nh n đ c y. Khi đó (x’,y) là thông báo gi m o h p lượ ể ậ ượ ả ạ ợ ệ Ki u t n công th 3: gi s Oscar tính ch ký trên b n tóm l c thông báo zể ấ ứ ả ử ữ ả ượ ng u nhiên. Sau đó anh ta tìm x sao cho z=h(x). N u làm đ c nh v y thì (x,y)ẫ ế ượ ư ậ là b c đi n gi m o h p l . Đ tránh đ c t n công này, h c n th a mã tínhứ ệ ả ạ ợ ệ ể ượ ấ ầ ỏ ch t m t chi u.ấ ộ ề B n tóm l c(giá tr c a hàm băm) còn đ c g i là đ i di n văn b n (messageả ượ ị ủ ượ ọ ạ ệ ả digest). M t message digest có chi u dài c đ nh v i các đ c đi m nh sau:ộ ề ố ị ớ ặ ể ư - giá tr tr l i c a các hàm băm duy nh t đ i v i m i giá tr đ u vào. B tị ả ạ ủ ấ ố ớ ỗ ị ầ ấ kỳ s thay đ i nào c a d li u vào cũng d n đ n m t k t qu saiự ổ ủ ữ ệ ẫ ế ộ ế ả - t đ i di n văn b n không th suy ra d li u g c là gì, chính vì đi u nàyừ ạ ệ ả ể ữ ệ ố ề ng i ta g i là one-way nh đã đ c p trong ph n mã hóa khóa công khai,ườ ọ ư ề ậ ầ nó có th s d ng khóa bí m t c a b n cho vi c mã hóa và khóa côngể ử ụ ậ ủ ạ ệ khai cho vi c gi i mã. Cách s d ng c p khóa nh v y không đ c dùngệ ả ử ụ ặ ư ậ ượ khi có s bí m t thông tin,mà ch y u nó dùng đ “ký” cho d li u. Thayự ậ ủ ế ể ữ ệ cho vi c đi mã hóa d li u, các ph n m m ký t o ra đ i di n văn b nệ ữ ệ ầ ề ạ ạ ệ ả (message digest) c a d li u và s d ng khóa bí m t đ mã hóa đ i di nủ ữ ệ ử ụ ậ ể ạ ệ đó. Hình d i đây là mô hình đ n gi n hóa vi c ch ký s đ c s d ngướ ơ ả ệ ữ ố ượ ử ụ nh th nào đ ki m tra tính toàn v n c a d li u đ c ký. ư ế ể ể ẹ ủ ữ ệ ượ Trong hình trên có hai ph n đ c g i cho ng i nh n: d li u g c và ch kýầ ượ ử ườ ậ ữ ệ ố ữ s . Đ ki m tra tính toàn v n c a d li u, ng i nh n tr c tiên s d ng khóaố ể ể ẹ ủ ữ ệ ườ ậ ướ ử ụ công khai c a ng i ký đ gi i mã đ i di n văn b n t d li u g c và m i.ủ ườ ể ả ạ ệ ả ừ ữ ệ ố ớ N u không gi ng nhau t c là d li u đã b gi m o, đi u này cũng có th x yế ố ứ ữ ệ ị ả ạ ề ể ả ra khi s d ng hai khóa khóa công khai và khóa bí m t không t ng ng.ử ụ ậ ươ ứ N u nh hai đ i di n văn b n gi ng nhau, ng i nh n có th ch c ch n r ngế ư ạ ệ ả ố ườ ậ ể ắ ắ ằ khóa khó công khai đ c s d ng đ gi i mã ch ký s là t ng ng v i khóaượ ử ụ ể ả ữ ố ươ ứ ớ bí m t đ c s d ng đ gi i mã ch ký s . Đ xác th c đ nh danh c a m t đ iậ ượ ử ụ ể ả ữ ố ể ự ị ủ ộ ố t ng cũng c n ph i xác th c khóa công khai c a đ i t ng đó.ượ ầ ả ự ủ ố ượ Trong m t vài tr ng h p, ch ký s đ c dánh giá là có th thay th ch kýộ ườ ợ ữ ố ượ ể ế ữ b ng tay. Ch ký s ch có th đ c đ m b o khi khóa bí m t không b l . Khiằ ữ ố ỉ ể ượ ả ả ậ ị ộ khóa bí m t b l thì ng i s h u ch ký không th ngăn ch n đ c vi c bậ ị ộ ườ ở ữ ữ ể ặ ượ ệ ị gi m o ch kýả ạ ữ 4.4.3.M t s s đ ch ký đi n tộ ố ơ ồ ữ ệ ử a. S đ ch ký RSA(đ xu t năm 1978)ơ ồ ữ ề ấ Có th coi bài toán xác th c là bài toán “đ i ng u” v i bài toán b o m t. Vìể ự ố ẫ ớ ả ậ v y, s d ng ng c thu t toán RSA ta có th có đ c m t s đ ch ký sậ ử ụ ượ ậ ể ượ ộ ơ ồ ữ ố RSA nh sau:ư • Sinh khóa: ch n p,q là s nguyên t l n. Tính n=pọ ố ố ớ × q, φ(n)=(p-1) × (q-1) Đ t ặ P = A = Zn, Ch n m t s t nhiên ọ ộ ố ự e sao cho 1 < e <Ф(N) và là s nguyên tố ố cùng nhau v i ớ Ф(N), K = {( e,d) / ed ≡ 1 (mod φ (n))}. (hay hay d= (1 + i * Phi_N) / E) v iớ i= n,1 ) V i K=(n,e,d) ta có D=d là khóa bí m t, E=(n,e) là khóa công khai, m là b n tinớ ậ ả c n kýầ • T o ch ký : v i m i b khóa K=(n,e,d) đ nh nghĩaạ ữ ớ ỗ ộ ị Ch ký trên mữ ∈P là S= SigD(m)= md mod n, S∈A • Ki m tra ch ký: Verể ữ E(m,S)= TRUE ⇔ m= Se mod n • Ho t đ ng c a s đ ch ký RSA có th mô t nh sau:ạ ộ ủ ơ ồ ữ ể ả ư a. Tr ng h p b n tin rõ m không c n bí m t(A ký b n tin m và g i cho B,ườ ợ ả ầ ậ ả ử B ki m tra ch ký c a A)ể ữ ủ Gi s mu n g i cho B b n tin rõ m có xác th c b ng ch ký s c aả ử ố ử ả ự ằ ữ ố ủ mình. Tr c tiên A tính ch ký sướ ữ ố SA = SigDA(m)= mdA mod nA Sau đó A g i cho B b đôi (m, Sử ộ A) và ki m tra xem đi u ki n m ể ề ệ ≡ SeAA mod nAcó th a mãn không. N u th a mãn, thi fkhi đó B kh ng đ nh r ngỏ ế ỏ ẳ ị ằ VerEA(m,SA) nh n giá tr TRUE và ch p nh n ch ký c a A trên mậ ị ấ ậ ữ ủ b. A ký b n tin rõ m đ đ c ch ký Sả ể ượ ữ A. Sau đó A dùng khóa mã công khai EB cu B đ l p b n mã M= Eả ể ậ ả B(m, SA) r i g i đ n B. Khi nh n đ c b nồ ử ế ậ ượ ả mã M, B dùng khóa bí m t Dậ B c a mình đ gi i mã cho M và thu đ c m,ủ ể ả ượ SA. Ti p đó dùng thu t toán ki m tra Verế ậ ể EA đ xác nh n ch ký c a Aể ậ ữ ủ c. Ví d sau đây s d ng s đ ch ký RSA v i thông đi p l nụ ử ụ ơ ồ ữ ớ ệ ớ d. Sinh khóa e. Th c th A ch n s nguyên p=7927 và q=6997 và tính n=pq= 5546521 vàự ể ọ ố φ= 7926× 6996=55450296. A ch n a=5 và gi i ab=5bọ ả ≡ 1 (mod 55450296) đ c b=44360237. Khóa công khai c a A là (n=55465219, a=5) và khóaượ ủ riêng c a A là b=44360237ủ f. Sinh ch kýữ g. Đ ký m t thông đi p m=31229978, A tính mể ộ ệ 1’= h(m)= 31229978 và tính toán ch ký s=mữ 1’b mod 312299784430237 mod 55465219 =30729435 h. Xác nh n ch kýậ ữ i. B tính m2’= sa mod n= 307294355 mod 55465219 = 31229978. Cu i cùng Bố ch p nh n ch ký vì mấ ậ ữ 2’= m1’ Chú ý So sánh gi a s đ ch ký RSAữ ơ ồ ữ và s đ m t mã RSA ta th y có s t ngơ ồ ậ ấ ự ươ ng. Vi c Alice ký vào m t ng ng v i vi c mã hóa văn b n m. Thu t toán ki mứ ệ ươ ứ ớ ệ ả ậ ể th chính là vi c s d ng hàm gi i mã nh RSA đ ki m tra xem sau khi gi i mã cóử ệ ử ụ ả ư ể ể ả đúng là văn b n tr c khi ký không. Thu t toán ki m th là công khai, b t kỳ ai cũngả ướ ậ ể ử ấ có th ki m th ch ký đ cể ể ử ữ ươ Nh v y vi c ký ch ng qua là mã hóa, vi c ki m th l i chính là vi c gi i mã.ư ậ ệ ẳ ệ ể ử ạ ệ ả Văn b n m mã hóa tr c khi g i. Nh ng gi a vi c ký và mã hóa có m i liên h gìả ướ ử ư ữ ệ ố ệ không? Nên ký tr c hay mã hóa tr cướ ướ v n đ gi i mãấ ề ả 1. gi s ng i g i Alice mu n g i văn b n m cũng ch ký S đ n Bob, có 2 cách xả ử ườ ử ố ử ả ữ ế ử lý: a. Ký tr c , mã hóa sauướ Alice ký tr c vào m b ng ch ký S=ướ ằ ữ SigA(m), sau đó mã hóa m và S nh n đ c zậ ượ =eA(m,S). Alice g i z cho Bobử Nh n đ c z Bob gi i mã z đ đ c m, S.Ti p theo ki m tra ch ký Verậ ượ ả ể ượ ế ể ữ B(m,S)=True không? b. Mã hóa tr c, ký sauướ Alice mã hóa tr c m b ng u=eướ ằ A(m), sau đó ký vào u b ng ch ký v=Sigằ ữ A(u). Alice g i (u,v) cho N. Nh n đ c (u,v) , Bob gi i mã đ c m.Ti p theo ki m tra ch kýử ậ ượ ả ượ ế ể ữ VerB(u,v)= true? 1. gi s Oscar l y tr m đ c thông tin trên đ ng truy n t Alice đ n Bobả ử ấ ộ ượ ườ ề ừ ế tr ng h p a, Oscar s l y đ c z. Trong tr ng h p b, Oscar l y đ c(u,v)ườ ợ ẽ ấ ượ ườ ợ ấ ượ +đ t n công văn b n m trong c hai tr ng h p, Oscar đ u ph i gi i mã thôngể ấ ả ả ườ ợ ề ả ả tin l y đ cấ ượ +n u mu n t n công vào ch ký, thay b ng ch ký gi m o thì x y ra đi u gì?ế ố ấ ữ ằ ữ ả ạ ả ề - tr ng h p a, đ có th t n công ch ký S Oscar ph i gi i mã z,ườ ợ ể ể ấ ữ ả ả m i nh n đ c Sớ ậ ượ - tr ng h p b, đ có th t n công ch ký v, Oscar đã s n có v, sau đóườ ợ ể ể ấ ữ ẵ g i (u,v’) đ n Bobử ế Oscar thay ch ký v c a Alice trên u , b ng ch ký c a Oscar là v’= Sigữ ủ ằ ữ ủ O(u), sau đó g i (u,v’) đ n Bob.Khi nh n đ c v’, Bob ki m th th y sai, g i pahnr h i l iử ế ậ ượ ể ử ấ ử ồ ạ Alice.Alice có th ch ng minh ch ký đó là gi m o. Alice đ a ch ký đúng cho Bobể ứ ữ ả ạ ư ữ nh ng quá trình truy n tin s b ch m l iư ề ẽ ị ậ ạ Nh v y trong tr ng h p b, Oscar có th gi m o ch ký mà không c n gi i mãư ậ ườ ợ ể ả ạ ữ ầ ả Vì th có l i khuyên: hãy ký tr c khi mã hóa c ch ký ể ờ ướ ả ữ b. S đ ch ký ElGamaơ ồ ữ S đ ch ký ElGama đ c thi t k v i m c đích dành riêng cho ch ký s ,ơ ồ ữ ượ ế ế ớ ụ ữ ố đi m m nh c a nó là cùng s nguyên t p trong cùng m t s đ thì v i R làể ạ ủ ố ố ộ ơ ồ ớ ng u nhiên nên ta có th có nhi u ch ký s . Đi u này có nghĩa là có nhi u chẫ ể ề ữ ố ề ề ữ ký h p l trên b c đi n cho tr c b t kỳ. Thu t toán xác minh ph i có khợ ệ ứ ệ ướ ấ ậ ả ả năng ch p nh n b t kỳ ch ký h p l nào khi xác th c ch ký đóấ ậ ấ ữ ợ ệ ự ữ  S đ ch ký ElGamaơ ồ ữ - ch n p là m t s nguyên t khi đó Zọ ộ ố ố p là m t tr ng và Zộ ườ p* s là m t nhómẽ ộ v i phép nhânớ - gi s g là ph n t sinh c a Zả ử ầ ử ủ p* - ch n ng u nhiên rọ ẫ ∈ Zp và tính K= gr mod p công khai K, p,g  Y u t xác th c hóaế ố ự - A g i m cho B v i mử ớ ∈ Zp - Ch n ng u nhiên Rọ ẫ ∈ Zp sao cho (R,p-1)=1 - Y u t xác th c hóa:X=gế ố ự R và Y đ c xác đ nh t ph ng trình:ượ ị ừ ươ m=r*X+R*Y(mod p-1) Khi g i A s g i b (m,X,Y) cho Bử ẽ ử ộ  Xác th c:ự B tính Z=KX * XY (mod p), n u Z=gế m là đúng, Z≠gm là sai. N u ch ký đ cế ữ ượ thi t l p đúng thì xác minh s thành công vì:ế ậ ẽ KX * XY ≡ grXgRY(mod p) ≡ gm(mod p) B tính ch ký b ng cách dùng c giái tr m t r l n s ng u nhiên m tữ ằ ả ị ậ ẫ ố ẫ ậ R(dùng đ ký lên b c đi n m). Vi c xác minh có th th c hi n duy nh t b ngể ứ ệ ệ ể ự ệ ấ ằ thông tin công khai Ví d :ụ V i m=5, p=11 ớ →g=2 Ch n r=8 ọ → K=28= 25 mod 11=3 Ch n R=9 ọ - y u t xác th c hóa: X=2ế ố ự 9= 3*2=6. T ph ng trình 5= 8*6+9*Y (modừ ươ 10) suy ra : Y=(5-8*6)*9-1(mod 10) =(55-48)*9(mod 10)=3 - th xác th cử ự Z=36 *63 mod 11=10 gm= 25 mod 11=10(đúng)  Xét đ m t c a s đ ch ký ElGamaộ ậ ủ ơ ồ ữ Gi s , Oscar th gi m o ch ký trên b c đi n m cho tr c mà không bi tả ử ử ả ạ ữ ứ ệ ướ ế r. N u Oscar ch n X và sau đó th tìm giá tr Y t ng ng. Anh ta ph i tínhế ọ ử ị ươ ứ ả Logarithm r i r c Logờ ạ XgmK-X. M t khác, n u đ u tieenanh ta ch n Y và sauặ ế ầ ọ đó th tìm X và th gi i ph ng trình:ử ử ả ươ KX * XY≡ gm(mod p) Đây là bài toán ch a có l i gi i nào. Tuy nhiên, d ng nh nó ch a đ cư ờ ả ườ ư ư ượ g n v i bài toán đã nghiên c u k nòa nên v n còn kh năng có cách nào đóắ ớ ứ ỹ ẫ ả đ tính X,Y đ ng th i đ (Y,X) là m t ch ký. Hi n th i không ai tìm đ cể ồ ờ ể ộ ữ ệ ờ ượ cách gi i song cũng không ai kh ng đ nh r ng nó không th gi i đ cả ẳ ị ằ ể ả ượ N u Oscar ch n X và Y và sau đó th gi i tìm m, anh ta s ph i đ i m t v iế ọ ử ả ẽ ả ố ặ ớ bài toán Logarithm r i r c. Vì th Oscar không th ký m t b c đi n ng uờ ạ ế ể ộ ứ ệ ẫ nhiên b ng bi n pháp này. Tuy nhiên, có m t s cách đ Oscar có th giằ ệ ộ ố ể ể ả m o ch ký lên b c đi n. ạ ữ ứ ệ Sau đây là ki u gi m o mà Oscar có th ký m t b c đi n ng u nhiên b ngể ả ạ ể ộ ứ ệ ẫ ằ vi c ch n X, Y và m đ ng th iệ ọ ồ ờ Gi thi t i và j là các s nguyên 0 ≤ i ≤ p -2 , 0≤j≤p-2 và UCLN(j,p-2)=1ả ế ố Khi đó th c hi n các tính toán sau:ự ệ X=giKj mod p Y=-Xj-1 mod(p-1) m=- Xij-1 mod(p-1) trong đó j-1 đ c tính theo modulo (p-1) (UCLN(j, p-1)=1)ượ ta nói r ng (X,Y) là ch ký h p l c a m. Đi u này đ c ch ng minh quaằ ữ ợ ệ ủ ề ượ ứ vi c ki m tra đi u ki n xác minhệ ể ề ệ KX * XY ≡ gm(mod p) Sau đây là ki u gi m o th hai trong đó Oscar b t đ u b c đi n đ c B kýể ả ạ ứ ắ ầ ứ ệ ượ tr c đây. Gi s (X,Y) là ch ký h p l trên m. Khi đó Oscar có kh năngướ ả ử ữ ợ ệ ả ký lên b c đi n khác nhau. Gi s i, j, h là các s nguyên 0 ≤ i, j,h ≤ p -2 vàứ ệ ả ử ố UCLN(hX-jY,p-1)=1. Ta th c hi n tính toán sauự ệ λ = Xh gi Kj mod p µ = Yλ (hX -jY)-1 mod (p-1) m, = λ(hm+iY ) -1(hX -jY)-1 mod (p-1), trong đó (hX -jY)-1 đ c tính theo modulo (p-1). Khi đó d dàng ki m tra đi uượ ễ ể ề ki n xác minhệ K λ λµ ≡ gm’ (mod p) Vì th (ế λ, µ) là ch ký h p l c a m’ữ ợ ệ ủ C hai tr ng h p trên đ u t o ra các ch ký gi m o h p l song khôngả ườ ợ ề ạ ữ ả ạ ợ ệ xu t hi n kh năng đ i ph ng gi m o ch ký trên b c đi n có s l a ch nấ ệ ả ố ươ ả ạ ữ ứ ệ ự ự ọ c a chính h mà không ph i gi i bài toán Logarithm r i r c. Vì th không có gìủ ọ ả ả ờ ạ ế nguy hi m v đ an toàn c a s đ ch ký Elgamalể ề ộ ủ ơ ồ ữ Cu i cùng ta s nêu cách có th phá đ c s đ này n u không áp d ngố ẽ ể ượ ơ ồ ế ụ nó m t cách c n th n. Tr c h t, giá tr R ng u nhiên đ c dùng đ tính chộ ẩ ậ ướ ế ị ẫ ượ ể ữ ký ph i đ c g bí m t không đ c đ l . Vì n u R b l , khá đ n gi n đả ượ ữ ậ ượ ể ộ ế ị ộ ơ ả ể tính: R=(m-RX)Y-1 mod(p-1) Dĩ nhiên, m t khi r b l thì h th ng b phá và Oscar có th d dàng giộ ị ộ ệ ố ị ể ễ ả m o ch kýạ ữ M t ki u dùng sai s đ n a là dùng cùng giá tr R đ ký hai b c đi n khácộ ể ơ ồ ữ ị ể ứ ệ nhau. Đi u này cũng t o thu n l i cho Oscar tính r và phá h th ng. Sau đây làề ạ ậ ợ ệ ố cách th c hi n. Gi s (X, Yự ệ ả ử 1) là ch ký trên mữ 1 và (X,Y2) là ch ký trên mữ 2. Khi đó KX X Y1 ≡ gm1(mod p) Và KX X Y2 ≡ gm2(mod p) Nh v yư ậ gm1 gm2 ≡ X Y1Y2 (mod p) t ng đ ng v i ph ng trìnhươ ươ ớ ươ m1 – m2 ≡ R(Y1- Y2) (mod p-1) bây gi ta gi s d= UCLN(Yờ ả ử 1- Y2, p-1). Vì d | (p-1) và d | (Y1- Y2) nên d | (m1 – m2 ). Ta đ nh nghĩaị m’= (m1 – m2) /d Y’=( Y1- Y2)/d p’ = (p-1)/d khi đó đ ng d th c tr thànhồ ư ứ ở m’≡ RY’(mod p’) vì UCLN (Y’,p’)=1 nên ta có th tínhể ε= (Y’)-1 mod p’ Khi đó giá tr R xác đ nh theo modulo p’ s làị ị ẽ R= m’ ε mod p’ Ph ng trình này cho d giá tr có th c a R: R=m’ươ ị ể ủ ε +ip’ (mod p) v i i nào đó, 0ớ ≤ i≤d-1. Trong đó giá tr d có th này có th xác đ nh đ c m t giá t đúng duyị ể ể ị ượ ộ ị nh t qua vi c ki m tra đi u ki n : X ấ ệ ể ề ệ ≡ gR (mod p) Ch ng 5. Xây d ng ph n m m ng d ngươ ự ầ ề ứ ụ 5.1.Đ nh nghĩa bài toánị Ch ký đi n t ngày càng đ c ng d ng trong nhi u ngành khác nhauữ ệ ử ượ ứ ụ ề nh Công ngh thông tin, ngành m t mã, ngành ngân hàng đ xác th c ng iư ệ ậ ể ự ườ g i và ng i nh n, B u chính vi n thông đ s d ng các th thông minh…Chử ườ ậ ư ễ ể ử ụ ẻ ữ ký đi n t có t m quan tr ng và ng d ng r ng rãi(nh nói trên).Bài nghiênệ ử ầ ọ ứ ụ ộ ư ở c u này đi xây d ng ch ng trình ch ng th c ch ký đi n t .ứ ự ươ ứ ự ữ ệ ử Ch ng th c ch ký đi n t là ph ng pháp d a trên các ph ng phápứ ự ữ ệ ử ươ ự ươ m t mã đ nh n th c ng i t o văn b n d a trên các quy t c và tham s saoậ ể ậ ự ườ ạ ả ự ắ ố cho có th ki m tra đ c nhân d ng c a ng i t o và tính toàn v n c a vănể ể ượ ạ ủ ườ ạ ẹ ủ b n.ả 5.2.Phân tích và thi t kế ế Digital Signature (ch ký đi n t ) đ c t o ra và ki m tra b ng m t mã,ữ ệ ử ượ ạ ể ằ ậ đó là m t ph ng pháp thu c lĩnh v c toán h c, nó chuy n toàn b messageộ ươ ộ ự ọ ể ộ thành m t d ng khó có th nh n d ng và có th đ c gi i mã. Digital signatureộ ạ ể ậ ạ ể ượ ả s d ng hai khóa thông d ng, m t khóa đ t o ra digital signature ho c chuy nử ụ ụ ộ ể ạ ặ ể message thành d ng khó nh n d ng, m t khóa dùng đ ki m tra digital signatureạ ậ ạ ộ ể ể ho c đ chuy n message đã mã hóa v d ng nguyên th y c a nó.ặ ể ể ề ạ ủ ủ Digital signature là cách c b n đ b o m t cho m t tài li u đi n t ơ ả ể ả ậ ộ ệ ệ ử (e- mail, spreaDigital Signatureheet_b ng tính, text file,..)ả đáng tin c y. Đáng tinậ nghĩa là b n bi t ai đã t o ra tài li u và b n bi t nó không b thay đ i trong b tạ ế ạ ệ ạ ế ị ổ ấ c cách nào t ng i t o ra nó.ứ ừ ườ ạ Digital signature d a vào thu t toán mã hoá đ b o đ m đ tin c y. Mãự ậ ể ả ả ộ ậ hoá là quá trình mang t t c d li u t m t máy tính g i sang máy tính khác vàấ ả ữ ệ ừ ộ ử mã hóa nó thành m t d ng mà ch có máy tính đ c g i m i có th gi i mã. Độ ạ ỉ ượ ử ớ ể ả ộ tin c y là quá trình ki m tra xác nh n đ c thông tin đ n t m t ngu n tin c y.ậ ể ậ ượ ế ừ ộ ồ ậ Hai quá trình này liên quan ch t ch đ n digital signature.ặ ẽ ế M t Digital Signature có th đ c xem nh m t giá tr s , đ c bi uộ ể ượ ư ộ ị ố ượ ể di n nh m t dãy các ký t , và đ c s d ng trong tin h c nh m t bi u th cễ ư ộ ự ượ ử ụ ọ ư ộ ể ứ toán h c. Bi u th c ph thu c vào hai đ u vào: dãy các ký t bi u di n dòngọ ể ứ ụ ộ ầ ự ể ễ d li u đi n t đ c ký và s b o m t đ c tham chi u đ n nh m t signatureữ ệ ệ ử ượ ố ả ậ ượ ế ế ư ộ public key, đi u này có nghĩa là v i m i ch ký thì ch duy nh t ng i đã kýề ớ ỗ ữ ỉ ấ ườ m i có th truy xu t đ n public key. Public key là khoá công khai cho t t cớ ể ấ ế ấ ả m i ng i, nó gi ng nh s đi n tho i trong danh b đi n tho i, cho phép vi cọ ườ ố ư ố ệ ạ ạ ệ ạ ệ ki m tra ch ký. K t qu cho th y vi c bi u di n ch ký s g n vào d li uể ữ ế ả ấ ệ ể ễ ữ ố ắ ữ ệ đi n t gi ng nh s d ng ch ký tay trên gi y trong tài li u văn b n.ệ ử ố ư ử ụ ữ ấ ệ ả Digital signature làm vi c d a trên hai khoá là public key và private key vàệ ự th c hi n qua hai giai đo n là vi c hình thành ch ký trên tài li u phía ng iự ệ ạ ệ ữ ệ ở ườ g i và vi c xác nh n tài li u nh n đ c chính xác và nguyên v n hay không ử ệ ậ ệ ậ ượ ẹ ở phía ng i nh n.ườ ậ V n đ b o m t digital signature không gi ng v i các ph ng pháp mãấ ề ả ậ ở ố ớ ươ hoá c đi n là ch dùng m t khoá cho c vi c mã hoá ng i g i và gi i mã ổ ể ỉ ộ ả ệ ở ườ ử ả ở ng i nh n mà s d ng hai khoá: private key đ mã hoá và public key đ gi iườ ậ ử ụ ể ể ả mã ki m tra. ể 5.2.1. Quá trình ký trong Message  B c m tướ ộ : “Băm” tài li u g i thành các hash-value hay còn đ c g i là Message Digest, cácệ ử ượ ọ Message Digest này s đ c tính toán đ đ a vào quá trình mã hoá ch ký.ẽ ượ ể ư ữ  B c hai: Tính Message Digestướ Trong b c hai c a ti n trình, m t ướ ủ ế ộ hash-value (giá tr băm)ị c a m tủ ộ message th ng đ c g i là ườ ượ ọ Message Digest đ c tính toán b ng cách áp d ngượ ằ ụ các thu t toán băm mã hoá ậ cryptographic hashing arthgorithm nh MD2,ư MD4, MD5, SHA1,…M t hash-value đã tính c a message là m t dãy bit liênộ ủ ộ t c, có đ dài c đ nh, đ c trích rút t message theo cách nào đó.ụ ộ ố ị ượ ừ T t c các thu t toán chính xác cho vi c tính toán ấ ả ậ ệ message digest đ cượ cung c p nh m t phép bi n đ i toán h c, trong đó c m t bit đ n t inputấ ư ộ ế ổ ọ ứ ộ ơ ừ message đ c bi n đ i thì m t digest khác đ c g i đ n. V i cách làm vi cượ ế ổ ộ ượ ử ế ớ ệ nh v y các thu t toán là r t b o đ m đ tin c y tr c các cu c t n công.ư ậ ậ ấ ả ả ộ ậ ướ ộ ấ  B c ba: Tính Digital Signatureướ Trong b c hai c a vi c ký message, thông tin nh n đ c trong b c bămướ ủ ệ ậ ượ ướ message (Message Digest) đã mã hoá v i khoá private key c a ng i ký vàoớ ủ ườ message, vì th m t giá tr băm gi i mã cũng đ c g i là Digital Signature đ cế ộ ị ả ượ ọ ượ g i đ n. Vì m c đích này, các thu t toán mã hoá cho vi c tính ch ký s tử ế ụ ậ ệ ữ ố ừ message digest đ c dùng. Thu t toán th ng đ c s d ng là RSA, DIGITALượ ậ ườ ượ ử ụ SIGNATUREA, ECDIGITAL SIGNATUREA. Thông th ng, ch ký s g nườ ữ ố ắ vào message trong đ nh d ng đ c bi t đ ki m tra khi c n thi t.ị ạ ặ ệ ể ể ầ ế Hình 1:Quá trình ký trong message 5.2.2. Quá trình ki m tra xác nh n ch ký trên tài li u.ể ậ ữ ệ K thu t Digital Signature cho phép ng i nh n message có kèm ch kýỹ ậ ườ ậ ữ ki m tra tính xác th c và tính toàn v n c a nó. Quá trình ki m tra ch ký s -ể ự ẹ ủ ể ữ ố digital signature verification nh m m c đích xác đ nh m t message g i đi đãằ ụ ị ộ ử đ c ký b ng khoá ượ ằ private key đúng v i khóa ớ public key g i đi hay không.ử Digital signature verification không th xác nh n có hay không m t message đãể ậ ộ đ c ký b i ng i g i. N u chúng ta mu n ki m tra có hay không vài ng i đãượ ở ườ ử ế ố ể ườ ký trong m t message g i đi, chúng ta c n nh n đ c ộ ử ầ ậ ượ public key theo cách nào đó. Đi u này th c hi n ho c b ng cách l y public key trong cách an toàn ề ự ệ ặ ằ ấ (ví dụ nh floppy disk ho c CD)ư ặ ho c v i s tr giúp c a ặ ớ ự ợ ủ Public Key Intrasfication theo m t gi y ch ng nh n s . N u không có m t cách an toàn đ nh n khoáộ ấ ứ ậ ố ế ộ ể ậ public key th c s t ng i g i, chúng ta không có kh năng ki m tra messageự ự ừ ườ ử ả ể đ c g i là có ph i xác th c c a ng i này hay không.ượ ử ả ự ủ ườ Nh v y, vi c ki m tra m t Digital Signature đ c th c hi n trong 3ư ậ ệ ể ộ ượ ự ệ b c:ướ  B c m tướ ộ : Tính Current Hash-Value Trong b c m t, m t hash-value c a message đã ký đ c tính. V i vi c tínhướ ộ ộ ủ ượ ớ ệ này thì v n s d ng thu t toán băm nh đã dùng trong su t quá trình ký. Hash-ẫ ử ụ ậ ư ố value nh n đ c đ c g i là ậ ượ ượ ọ current hash-value b i vì nó đ c tính t tr ngở ượ ừ ạ thái hi n th i c a message.ệ ờ ủ  B c haiướ : Tính Original Hash-Value Trong b c hai c a quá trình ki m tra digital signature, digital signature đ cướ ủ ể ượ gi i mã v i cũng v i thu t toán mã hoá đã đ c s d ng trong su t quá trình ký.ả ớ ớ ậ ượ ử ụ ố Vi c gi i mã đ c th c hi n b ng khoá public key t ng ng v i khoá privateệ ả ượ ự ệ ằ ươ ứ ớ key đ c dùng trong su t quá trình ký c a message. K t qu là, chúng ta nh nượ ố ủ ế ả ậ đ c ượ original hash-value mà đã đ c tính t message g c trong su t b c m tựơ ừ ố ố ướ ộ c a quá trình ký ủ (original message digest)  B c baướ : So sánh Current hash-value v i Original hash-ớ value Trong b c ba, chúng ta đ i chi u current hash-value nh n đ c trongướ ố ế ậ ượ b c m t v i original hash-value nh n đ c trong b c hai. N u hai giá tr nàyướ ộ ớ ậ ượ ướ ế ị gi ng h t nhau thì vi c ki m tra s thành công n u ch ng minh đ c messageố ệ ệ ể ẽ ế ứ ượ đã đ c ký v i khoá private key đúng v i khoá public key đã đ c dùng trongượ ớ ớ ượ quá trình ki m tra. N u hai giá tr này khác nhau thì nghĩa là digital signature làể ế ị sai và vi c ki m tra là th t b i.ệ ể ấ ạ Hình 2: Quá trình ki m tra xác nh n ch ký trên tài li uể ậ ữ ệ Nh v y quá trình ho t đ ng c a m t digital signature đ c minh ho nh hìnhư ậ ạ ộ ủ ộ ượ ạ ư sau: Hình 3: Quá trình làm vi c c a m t Digital Signatureệ ủ ộ Decrypt Private Key Encrypt Public Key Nguyên nhân c a vi c sai ch ký: có 3 lý do c a vi c nh n m t digitalủ ệ ữ ủ ệ ậ ộ signature sai: - N u digital signature là gi m o và đ c gi i mã v i khoá public key,ế ả ạ ượ ả ớ giá tr nguyên thu nh n đ c s không ph i là original hash-value c aị ỷ ậ ượ ẽ ả ủ message g c tuy m t vài giá tr khác có gi ng.ố ộ ị ố - N u message đã b đ i sau khi ký, current hash-value đ c tính tế ị ổ ượ ừ message gi m o này s khác v i original hash-value b i vì haiả ạ ẽ ớ ở message khác nhau thì hash-value khác nhau. - N u public key không t ng ng v i private key đ c dùng trong khiế ươ ứ ớ ượ ký, original hash-value nh n đ c b i s gi i mã ch ký v i m t khoáậ ượ ở ự ả ữ ớ ộ không đúng s không ph i là giá tr đúng.ẽ ả ị 5.3.Ch ng trình cài đ tươ ặ 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. ằ ữ ườ V i tính năng m nh m c a .NET g m h n 5000 class và tích h p 25ớ ạ ẽ ủ ồ ơ ợ ngôn ng , .NET h tr s n cho chúng ta th vi n ữ ỗ ợ ẳ ư ệ System.Security.Cryptography; đ mã hóa thông tin b ng các thu t toán nh : RSA, MD5, SHA1, SHA256,ể ằ ậ ư SHA384, SHA512… Ví d đo n code sau đây dùng đ mã hóa b ng thu t toánụ ạ ể ằ ậ MD5. Giao di n ch ng trìnhệ ươ Giao di n chính c a ch ng trìnhệ ủ ươ Giao di n ch ng trình v i ti n trình mã hóa m t văn b nệ ươ ớ ế ộ ả Giao di n ch ng trình v i ti n trình gi i mãệ ươ ớ ế ả