Ktl-icon-tai-lieu

Lý thuyết mật mã (chương 2)

Được đăng lên bởi motsach
Số trang: 24 trang   |   Lượt xem: 2271 lần   |   Lượt tải: 0 lần
Lý thuyÕt mËt m·

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Õ.
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).
Trang : 1

NguyÔn §¨ng Dòng

Lý thuyÕt mËt m·
§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...
Lý thuyÕt mËt m·
Ch¬ng 2
Lý thuyÕt shannon
N¨m 1949, Claude shannon ®· c«ng mét bµi b¸o nhan ®Ò " thuyÕt
th«ng tin trong c¸c 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 mËt an toµn mÆt tÝnh to¸n nÕu mét thuËt to¸n tèt nhÊt ®Ó ph¸
cÇn Ýt nhÊt N phÐp to¸n, N rÊt lín nµo ®ã. VÊn ®Ò ë chç, kh«ng mét
mËt thùc ®· biÕt nµo t ®îc chøng an toµn theo ®Þnh nghÜa nµy. Trªn
thùc tÕ, ngêi ta gäi mét mËt "an toµn vÒ mÆt tÝnh to¸n" nÕu cã mét ph¬ng
ph¸p tèt nhÊt p 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 quy ®é an toµn cña
mét mËt mét bµi to¸n ®· ®îc nghiªn cøu bµi to¸n nµy ®îc coi khã.
dô, ta thÓ chøng minh mét kh¼ng ®Þnh d¹ng " Mét 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 " 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 mét chøng minh hoµn chØnh ä an toµn. ( T×nh h×nh nµy
còng t¬ng nh viÖc chøng minh mét bµi to¸n NP ®Çy ®ñ: Cã thÓ chøng 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
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 mËt khi kh«ng mét h¹n
chÕ nµo ®îc ®Æt ra vÒ khèi lîng tÝnh to¸n Oscar ®îc phÐp thùc hiÖn. Mét
mËt ®îc gäi an toµn kh«ng ®iÒu kiÖn nÕu kh«ng thÓ pthËm chÝ víi kh¶
n¨ng tÝnh to¸n kh«ng h¹n chÕ.
Khi th¶o luËn ®é 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 mËt nµo trong
c¸c dÞch vßng, thay thÕ VigenÌre ®îc coi an toµn mÆ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).
Trang : 1
NguyÔn §¨ng Dòng
Lý thuyết mật mã (chương 2) - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Lý thuyết mật mã (chương 2) - Người đăng: motsach
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
24 Vietnamese
Lý thuyết mật mã (chương 2) 9 10 899