Ktl-icon-tai-lieu

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

Được đăng lên bởi motsach
Số trang: 26 trang   |   Lượt xem: 2463 lần   |   Lượt tải: 0 lần
KiÓm tra tÝnh nguyªn tè x¸c suÊt
§Ó thiÕt lËp hÖ mËt RSA, ta ph¶i t¹o ra c¸c sè nguyªn tè ngÉu
nhiªn lín (ch¼ng h¹n cã 80 ch÷ sè). Trong thùc tÕ, ph¬ng c¸ch thùc
hiÖn ®iÒu nµy lµ: tríc hÕt ph¶i t¹o ra c¸c sè ngÈu nhiªn lín, sau ®ã
kiÓm tra tÝnh nguyªn thuû cña chóng b»ng c¸ch dïng thuËt to¸n x¸c
suÊt Monte- Carlo thêi gian ®a thøc (ch¼ng h¹n nh thuËt to¸n MillerRabin hoÆc lµ thuËt to¸n Solovay- Strasen). C¶ hai thuËt to¸n trªn ®Òu
®îc tr×nh bµy trong phÇn nµy. Chóng lµ c¸c thuËt to¸n nhanh (tøc lµ
mét sè nguyªn n ®îc kiÓm tra trong thêi ®a thøc theo log2n, lµ sè c¸c
bÝt trong biÓu diÖn nhÞ ph©n cña n). Tuy nhiªn, vÉn cã kh¶ n¨ng lµ
thuËn to¸n cho r»ng n lµ sè nguyªn tè trong khi thùc tÕ n lµ hîp lÖ sè.
Bëi vËy, b»ng c¸ch thay ®æi thuËt to¸n nhiÒu lÇn, cã thÓ gi¶m x¸c
suÊt sai sè díi mét møc ngìng cho phÐp (sau nµy sÏ th¶o luËn kü h¬n
mét chót vÒ vÊn ®Ò nµy).
Mét vÊn ®Ò quan träng kh¸c: lµ cÇn ph¶i kiÓm tra bao nhiªu sè
nguyªn ngÉu nhiªn (víi kÝch th¬c x¸c ®Þnh)cho tíi khi t×m ®îc mét
sè nguyªn tè. Mét kÕt qu¶ nçi tiÕng trong lý thuyÕt sè (®îc gäi lµ
®Þnh lý sè nguyªn tè) ph¸t biÓu r»ng: sè c¸c sè nguyªn tè kh«ng lín
h¬n N xÊp xØ b»ng N/ln N. Bëi vËy, nÕu p ®îc chän ngÉu nhiªn th×
x¸c suÊt p lµ mét sè nguyªn tè sÏ vµo kho¶ng 1/ln p. Víi mét mo®un
512 bÝt, ta cã 1/ln p ≈ 1/77. §iÒu nµy cã nghÜa lµ tÝnh trung b×nh, c
177 sè nguyªn ngÉu nhiªn p víi kÝch thíc t¬ng øng sÏ cã mét sè lµ
sè nguyªn tè. DÜ nhiªn, nÕu chÜ h¹n chÕ xÐt c¸c sè nguyªn lÎ th× x¸c
suÊt sÏ t¨ng gÊp ®«i tíi kho¶ng 2/177). Bìi vËy trªn thùc tÕ, hoµn
toµn cã kh¶ n¨ng t¹o ®îc c¸c nguyªn tè ®ñ lín vµ do ®ã vÒ mÆt thùc
thÓ ta cã thÓ thiÕt lËp ®îc mét hÖ mËt RSA. Sau ®©y sÏ tiÕp tôc xem
xÐt ®iÒu nµy ®îc thùc hiªn nh thÕ nµo.
Mét bµi to¸n quyÕt ®Þnh lµ mét bµi to¸n to¸n trong ®ã mét c©u hái
cÇn ®îc tr¶ lêi “cã” hoÆc “kh«ng”. Mét thuËt to¸n x¸c suÊt lµ mét
thuËt to¸n bÊt kú cã sö dông c¸c sè ngÉu nhiªn (ngîc l¹i, thuËt to¸n
kh«ng sö dông c¸c sè ngÉu nhiªn sÏ ®îc gäi lµ mét thuËt to¸n tÊt
®Þnh). C¸c ®Þnh nghÜa sau cã liªn quan tíi c¸c thuËt to¸n x¸c suÊt cho
c¸c bµi to¸n quyÕt ®Þnh.
§Þnh nghÜa 4.1
ThuËt to¸n Monte Carlo ®Þnh híng “cã” lµ mét thuËt to¸n x¸c
suÊt cho mét bµi to¸n quyÕt ®Þnh, trong ®ã c©u tr¶ lêi “cã” lu«n lu«n
lµ ®óng cßn c©u tr¶ lêi “kh«ng” cã thÓ lµ sai. ThuËt to¸n Monte Carlo
®Þnh híng “kh«ng“ còng ®îc ®Þnh nghÜa theo c¸ch t¬ng tù. Chóng ta
nãi r»ng, mét thuËt to¸n Monte Carlo ®Þnh híng “cã” cã x¸c suÊt sai

b»ng ε nÕu víi bÊt kú mæt trêng hîp nµo mµ c©u tr¶ lêi lµ “cã” th×
thuËt to...
KiÓm tra tÝnh nguyªn tè x¸c suÊt
§Ó thiÕt lËp hÖ mËt RSA, ta ph¶i t¹o ra c¸c sè nguyªn tè ngÉu
nhiªn lín (ch¼ng h¹n cã 80 ch÷ sè). Trong thùc tÕ, ph¬ng c¸ch thùc
hiÖn ®iÒu nµy lµ: tríc hÕt ph¶i t¹o ra c¸c sè ngÈu nhiªn lín, sau ®ã
kiÓm tra tÝnh nguyªn thuû cña chóng b»ng c¸ch dïng thuËt to¸n x¸c
suÊt Monte- Carlo thêi gian ®a thøc (ch¼ng h¹n nh thuËt to¸n Miller-
Rabin hoÆc lµ thuËt to¸n Solovay- Strasen). C¶ hai thuËt to¸n trªn ®Òu
®îc tr×nh bµy trong phÇn nµy. Chóng lµ c¸c thuËt to¸n nhanh (tøc lµ
mét sè nguyªn n ®îc kiÓm tra trong thêi ®a thøc theo log
2
n, lµ sè c¸c
bÝt trong biÓu diÖn nhÞ ph©n cña n). Tuy nhiªn, vÉn cã kh¶ n¨ng lµ
thuËn to¸n cho r»ng n lµ sè nguyªn tè trong khi thùc tÕ n lµ hîp lÖ sè.
Bëi vËy, b»ng c¸ch thay ®æi thuËt to¸n nhiÒu lÇn, cã thÓ gi¶m x¸c
suÊt sai sè díi mét møc ngìng cho phÐp (sau nµy sÏ th¶o luËn kü h¬n
mét chót vÒ vÊn ®Ò nµy).
Mét vÊn ®Ò quan träng kh¸c: lµ cÇn ph¶i kiÓm tra bao nhiªu sè
nguyªn ngÉu nhiªn (víi kÝch th¬c x¸c ®Þnh)cho tíi khi t×m ®îc mét
sè nguyªn tè. Mét kÕt qu¶ nçi tiÕng trong lý thuyÕt sè (®îc gäi lµ
®Þnh lý sè nguyªn tè) ph¸t biÓu r»ng: sè c¸c sè nguyªn tè kh«ng lín
h¬n N xÊp xØ b»ng N/ln N. Bëi vËy, nÕu p ®îc chän ngÉu nhiªn th×
x¸c suÊt p lµ mét sè nguyªn tè sÏ vµo kho¶ng 1/ln p. Víi mét mo®un
512 bÝt, ta cã 1/ln p 1/77. §iÒu nµy cã nghÜa lµ tÝnh trung b×nh, c
177 sè nguyªn ngÉu nhiªn p víi kÝch thíc t¬ng øng sÏ cã mét sè lµ
sè nguyªn tè. DÜ nhiªn, nÕu chÜ h¹n chÕ xÐt c¸c sè nguyªn lÎ th× x¸c
suÊt sÏ t¨ng gÊp ®«i tíi kho¶ng 2/177). Bìi vËy trªn thùc tÕ, hoµn
toµn cã kh¶ n¨ng t¹o ®îc c¸c nguyªn tè ®ñ lín vµ do ®ã vÒ mÆt thùc
thÓ ta cã thÓ thiÕt lËp ®îc mét hÖ mËt RSA. Sau ®©y sÏ tiÕp tôc xem
xÐt ®iÒu nµy ®îc thùc hiªn nh thÕ nµo.
Mét bµi to¸n quyÕt ®Þnh lµ mét bµi to¸n to¸n trong ®ã mét c©u hái
cÇn ®îc tr¶ lêi “cã” hoÆc “kh«ng”. Mét thuËt to¸n x¸c suÊt lµ mét
thuËt to¸n bÊt kú cã sö dông c¸c sè ngÉu nhiªn (ngîc l¹i, thuËt to¸n
kh«ng sö dông c¸c sè ngÉu nhiªn sÏ ®îc gäi lµ mét thuËt to¸n tÊt
®Þnh). C¸c ®Þnh nghÜa sau cã liªn quan tíi c¸c thuËt to¸n x¸c suÊt cho
c¸c bµi to¸n quyÕt ®Þnh.
§Þnh nghÜa 4.1
ThuËt to¸n Monte Carlo ®Þnh híng “cã” lµ mét thuËt to¸n x¸c
suÊt cho mét bµi to¸n quyÕt ®Þnh, trong ®ã c©u tr¶ lêi “cã” lu«n lu«n
lµ ®óng cßn c©u tr¶ lêi “kh«ng” cã thÓ lµ sai. ThuËt to¸n Monte Carlo
®Þnh híng “kh«ng“ còng ®îc ®Þnh nghÜa theo c¸ch t¬ng tù. Chóng ta
nãi r»ng, mét thuËt to¸n Monte Carlo ®Þnh híng “cã” cã x¸c suÊt sai
Lý thuyết mật mã (chương 4.1) - Trang 2
Để xem tài liệu đầy đủ. Xin vui lòng
Lý thuyết mật mã (chương 4.1) - 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!
26 Vietnamese
Lý thuyết mật mã (chương 4.1) 9 10 681