Chapter 2 : lý thuyết về 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.
Nội dung trích xuất từ tài liệu:
Chapter 2 : lý thuyết về shannonVietebooks Nguyễn Hoàng Cương 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ùc Trang 1Vietebooks Nguyễn Hoàng CươnghiÖ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 lµan 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) lµx¸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) Trang 2Vietebooks Nguyễn Hoàng CươngHÖ 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 ...