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 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.

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ªn thùc tÕ, ngêi ta gäi mét hÖ mËt lµ "an toµn vÒ mÆt tÝnh to¸n"

nÕu cã 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íi viÖ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µi to¸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©n tÝch ra thõa sè mét sè nguyªn n cho 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 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Ønh

vÒ ä an toµn. ( T×nh h×nh nµy còng t¬ng tù nh viÖc chø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ét chø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é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¸n kh«ng h¹n chÕ.

p(x) p(y | x)

p(y)

p

P

(x) = ∑ p

K

(K)

{K:x= d

K

(y)}

∑ p

K

(K) p

P

(d

K

(y))

{k,U:y∈c(k)}

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Ê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Ên c«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¬ng ph¸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ñ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Ó ®îc

nghiªn cøu theo quan ®iÓm ®é phøc t¹p tÝnh to¸n v× thêi gian 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 ®Ó 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¸c

suÊ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ªn

X 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ñ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 ®î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).

p(x) p(y | x)

p(y)

p

P

(x) = ∑ p

K

(K)

{K:x= d

K

(y)}

∑ p

K

(K) p

P

(d

K

(y))

{k,U:y∈c(k)}