Giáo trình Mật mã và ứng dụng: Chương 2

Giáo trình Mật mã và ứng dụng - Chương 2: Lý thuyết Shannon, trình bày các nội dung chính: độ mật hoàn thiện, entropi, các tính chất của entropi, các khóa giả và khoảng duy nhất, các hệ mật mã tích,... Đây là tài liệu tham khảo dành cho sinh viên ngành Công nghệ thông tin.
Nội dung trích xuất từ tài liệu:
Giáo trình Mật mã và ứng dụng: Chương 2 Ch−¬ng 2 Lý thuyÕt shannon N¨m 1949, Claude shannon ® c«ng bè mét b i b¸o cã nhan ®Ò LýthuyÕt th«ng tin trong c¸c hÖ mËt trªn t¹p chÝ The Bell System TechnicalJournal. B i b¸o ® cã ¶nh h−ëng lín ®Õn viÖc nghiªn cøu khoa häc mËt m .Trong ch−¬ng n y ta sÏ th¶o luËn mét v i ý t−ëng trong lý thuyÕt cñaShannan.2.1 ®é mËt ho n thiÖn. Cã hai quan ®iÓm c¬ b¶n vÒ ®é an to n cña mét hÖ mËt.§é an to n tÝnh to¸n: §o ®é n y liªn quan ®Õn nh÷ng nç lùc tÝnh to¸n cÇn thiÕt ®Ó ph¸ méthÖ mËt. Mét hÖ mËt l an to n vÒ mÆt tÝnh to¸n nÕu cã mét thuËt to¸n tèt nhÊt®Ó ph¸ nã cÇn Ýt nhÊt N phÐp to¸n, N l sè rÊt lín n o ®ã. VÊn ®Ò l ë chç,kh«ng cã mét hÖ mËt thùc tÕ ® biÕt n o cã thÓ ®−îc chøng tá l an to n theo®Þnh nghÜa n y. Trªn thùc tÕ, ng−êi ta gäi mét hÖ mËt l an to n vÒ mÆt tÝnhto¸n nÕu cã mét ph−¬ng ph¸p tèt nhÊt ph¸ hÖ n y nh−ng yªu cÇu thêi gianlín ®Õn møc kh«ng chÊp nhËn ®−îc.(§iÒu n y tÊt nhiªn l rÊt kh¸c víi viÖcchøng minh vÒ ®é an to n). Mét quan ®iÓm chøng minh vÒ ®é an to n tÝnh to¸n l quy ®é an to ncña mét hÖ mËt vÒ mét b i to¸n ® ®−îc nghiªn cøu kü v b i to¸n n y ®−îccoi l khã. VÝ dô, ta cã thÓ chøng minh mét kh¼ng ®Þnh cã d¹ng Mét hÖmËt ® cho l an to n nÕu kh«ng thÓ ph©n tÝch ra thõa sè mét sè nguyªn ncho tr−íc. C¸c hÖ mËt lo¹i n y ®«i khi gäi l an to n chøng minh ®−îc.Tuy nhiªn cÇn ph¶i hiÓu r»ng, quan ®iÓm n y chØ cung cÊp mét chøng minhvÒ ®é an to n cã liªn quan ®Õ mét b i to¸n kh¸c chø kh«ng ph¶i l métchøng minh ho n chØnh vÒ ä an to n. ( T×nh h×nh n y còng t−¬ng tù nh− viÖcchøng minh mét b i to¸n l NP ®Çy ®ñ: Cã thÓ chøng tá b i to¸n ® cho chÝÝt còng khã nh− mét b i to¸n NP ®Çy ®ñ kh¸c , song kh«ng ph¶i l métchøng minh ho n chØnh vÒ ®é khã tÝnh to¸n cña b i to¸n).§é an to n kh«ng ®iÒu kiÖn. §é ®o n y liÖn quan ®Õn ®é an to n cña c¸c hÖ mËt khi kh«ng cã méth¹n chÕ n o ®−îc ®Æt ra vÒ khèi l−îng tÝnh to¸n m Oscar ®−îc phÐp thùchiÖn. Mét hÖ mËt ®−îc gäi l an to n kh«ng ®iÒu kiÖn nÕu nã kh«ng thÓ bÞph¸ thËm chÝ víi kh¶ n¨ng tÝnh to¸n kh«ng h¹n chÕ. Khi th¶o luËn vÒ ®é an to n cña mét mËt, ta còng ph¶i chØ ra kiÓu tÊnc«ng ®ang ®−îc xem xÐt. Trong ch−¬ng 1 ® cho thÊy r»ng, kh«ng mét hÖmËt n o trong c¸c hÖ m dÞch vßng, m thay thÕ v m VigenÌre ®−îc coi lan to n vÒ mÆt tÝnh to¸n víi ph−¬ng ph¸p tÊn c«ng chØ víi b¶n m ( Víi khèil−îng b¶n m thÝch hîp). §iÒu n y m ta sÏ l m trong phÇn n y l ®Ó ph¸t triÓn lý thuyÕt vÒ c¸chÖ mËt cã ®é an to n kh«ng ®iÒu kiÖn víi ph−¬ng ph¸p tÊn c«ng chØ víi b¶nm . NhËn thÊy r»ng, c¶ ba hÖ mËt nªu trªn ®Òu l c¸c hÖ mËt an to n v« ®iÒukiÖn chØ khi mçi pkÇn tö cña b¶n râ ®−îc m ho¸ b»ng mét kho¸ cho tr−íc!. Râ r ng l ®é an to n kh«ng ®iÒu kiÖn cña mét hÖ mËt kh«ng thÓ ®−îcnghiªn cøu theo quan ®iÓm ®é phøc t¹p tÝnh to¸n v× thêi gian tÝnh to¸n chophÐp kh«ng h¹n chÕ. ë ®©y lý thuyÕt x¸c suÊt l nÒn t¶ng thÝch hîp ®Ónghiªn cøu vÒ ®é an to n kh«ng ®iÒu kiÖn. Tuy nhiªn ta chØ cÇn mét sè kiÕnthøc s¬ ®¼ng trong x¸c suÊt; c¸c ®Þnh nghÜa chÝnh sÏ ®−îc nªu d−íi ®©y.§Þnh nghÜa 2.1. Gi¶ sö X v Y l c¸c biÕn ngÉu nhiªn. KÝ hiÖu x¸c suÊt ®Ó X nhËn gi¸trÞ x l p(x) v ®Ó Y nhËn gi¸ trÞ y l p(y). X¸c suÊt ®ång thêi p(x,y) l x¸csuÊt ®Ó X nhËn gi¸ trÞ x v Y nhËn gi¸ trÞ y. X¸c suÊt cã ®iÒu kiÖn p(x | y) lx¸c suÊt ®Ó X nhËn gi¸ trÞ víi ®iÒu kiÖn Y nhËn gi¸ trÞ y. C¸c biÕn ngÉu nhiªnX v Y ®−îc gäi l ®éc lËp nÕu p(x,y) = p(x) p(y) víi mäi gi¸ trÞ cã thÓ x cñaX v y cña Y. Quan hÖ gi÷a x¸c suÊt ®ång thêi v x¸c suÊt cã ®iÒu kiÖn ®−îc biÓu thÞtheo c«ng thøc: p(x,y) = p(x | y) p(y)§æi chç x v y ta cã : p(x,y) = p(y | x) p(x)Tõ hai biÓu thøc trªn ta cã thÓ rót ra kÕt qu¶ sau:(®−îc gäi l ®Þnh lý Bayes)§Þnh lý 2.1: (§Þnh lý Bayes). NÕu p(y) > 0 th×: p(x) p(y | x) p(x | y) = p(y)HÖ qu¶ 2.2. X v Y l c¸c biÕn ®éc lËp khi v chØ khi: p(x | y) = p(x) víi mäi x,y. Trong phÇn n y ta gi¶ sö r»ng, mét kho¸ cô thÓ chØ dïng cho mét b¶nm . Gi¶ sö cã mét ph©n bè x¸c suÊt trªn kh«ng gian b¶n râ P. KÝ hiÖu x¸csuÊt tiªn nghiÖm ®Ó b¶n râ xuÊt hiÖn l pP (x). Còng gi¶ sö r»ng, khãa K ®−îcchän ( bëi Alice v Bob ) theo mét ph©n bè x¸c suÊt x¸c ®Þnh n o ®ã. (Th«ng th−êng kho¸ ®−îc chän ngÉu nhiªn, bëi vËy tÊt c¶ c¸c kho¸ sÏ ®ångkh¶ n¨ng, tuy nhiªn ®©y kh«ng ph¶i l ®iÒu b¾t buéc). KÝ hiÖu x¸c suÊt ®Ókhãa K ®−îc chän l pK(K). CÇn nhí r»ng khãa ®−îc chän tr−íc khi AlicebiÕt b¶n râ. Bëi vËy cã thÓ gi¶ ®Þnh r»ng kho¸ K v b¶n râ x l c¸c sù kiÖn®éclËp. Hai ph©n bè x¸c suÊt trªn P v K sÏ t¹o ra mét ph©n bè x¸c suÊt trªn C.ThËt vËy, cã thÓ dÔ d ng tÝnh ®−îc x¸c suÊt pP(y) víi y l b¶n m ®−îc göi®i. Víi mét kho¸ K ∈ K, ta x¸c ®Þnh: C(K) = { eK (x) : x ∈P }ë ®©y C(K) biÓu thÞ tËp c ...