Chapter 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 Technical Journal". 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ủa Shannan.
Nội dung trích xuất từ tài liệu:
Chapter 2 - LÝ THUYẾT SHANNON 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 BellSystem Technical Journal. Bµi b¸o ®· cã ¶nh hëng lín ®Õn viÖcnghiª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ña Shannan.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ét hÖ 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ªnthùc tÕ, ngêi ta gäi mét hÖ mËt lµ an toµn vÒ mÆt tÝnh to¸n nÕucã mét ph¬ng ph¸p tèt nhÊt ph¸ hÖ nµy nhng yªu cÇu thêi gian lí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íiviÖc chø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µn cña mét hÖ mËt vÒ mét bµi to¸n ®· ®îc nghiªn cøu kü vµ bµito¸n nµy ®îc coi 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©ntÝch ra thõa sè mét sè nguyªn n cho tríc. C¸c hÖ mËt lo¹i nµy ®«i khigä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 minh vÒ ®é an toµn cã liªn quan®Õ mét bµi to¸n kh¸c chø kh«ng ph¶i lµ mét chøng minh hoµn chØnhvÒ ä an toµn. ( T×nh h×nh nµy còng t¬ng tù nh viÖc chøng minh métbµi to¸n lµ NP ®Çy ®ñ: Cã thÓ chøng tá bµi to¸n ®· cho chÝ Ýt còngkhã nh mét bµi to¸n NP ®Çy ®ñ kh¸c , song kh«ng ph¶i lµ mét chøngminh 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 khikh«ng cã mét h¹n chÕ nµo ®îc ®Æt ra vÒ khèi lîng tÝnh to¸n mµOscar ®îc phÐp thùc hiÖ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¸nkh«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Ø rakiÓu tÊn c«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 lµ an toµn vÒ mÆt tÝnh to¸n víi ph¬ng ph¸p tÊnc«ng chØ víi b¶n m· ( Víi khèi lî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¸c hÖ mËt cã ®é an toµn kh«ng ®iÒu kiÖn víi ph¬ngph¸p tÊn c«ng chØ víi b¶n m·. 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Òu kiÖn chØ khi mçi pkÇn tö cñab¶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«ngthÓ ®îc nghiªn cøu theo quan ®iÓm ®é phøc t¹p tÝnh to¸n v× thêigian tÝnh to¸n cho phÐ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Õn thø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 ®Ó XnhËn gi¸ trÞ x lµ p(x) vµ ®Ó Y nhËn gi¸ trÞ y lµ p(y). X¸c suÊt ®ångthêi p(x,y) lµ x¸c suÊt ®Ó X nhËn gi¸ trÞ x vµ Y nhËn gi¸ trÞ y. X¸csuÊt cã ®iÒu kiÖn p(x | y) lµ x¸c suÊt ®Ó X nhËn gi¸ trÞ víi ®iÒukiÖn Y nhËn gi¸ trÞ y. C¸c biÕn ngÉu nhiªn X vµ Y ®îc gäi lµ ®éc lËpnÕu p(x,y) = p(x) p(y) víi mäi gi¸ trÞ cã thÓ x cña X 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 ®îcbiÓ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 chomét b¶n m·. 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¸c suÊt tiªn nghiÖm ®Ó b¶n râ xuÊt hiÖn lµ pP(x). Còng gi¶sö r»ng, khãa K ®îc chän ( bëi Alice vµ Bob ) theo mét ph©n bè x¸csuÊt x¸c ®Þnh nµo ®ã. ( Th«ng thêng kho¸ ®îc chän ngÉu nhiªn, bëivËy tÊt c¶ c¸c kho¸ sÏ ®ång kh¶ 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Çnnhí r»ng khãa ®îc chän tríc khi Alice biÕ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Êttrª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¶nm· ®î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¸c b¶n m· cã thÓ K l ...