Giáo trình Mật mã và ứng dụng: Chương 4

Giáo trình Mật mã và ứng dụng - Chương 4: Hệ mật Rsa và vấn đề phân tích thừa số, trình bày các nội dung: giới thiệu về hệ mật khóa công khai, một số vấn đề sâu hơn về lý thuyết số, hệ mật Rsa, thực hiện hệ mật Rsa, kiểm tra tính nguyên tố xác suất, các phương pháp tấn công hệ mật Rsa,... Đây là tài liệu tham khảo dành cho sinh viên Công nghệ thông tin.
Nội dung trích xuất từ tài liệu:
Giáo trình Mật mã và ứng dụng: Chương 4 Ch−¬ng 4 HÖ mËt RSA v vÊn ®Ò ph©n tÝch thõa sè 4.1. Giíi thiÖu vÒ hÖ mËt kho¸ c«ng khai Trong m« h×nh mËt m cæ ®iÓn tr−íc ®©y m hiÖn nay ®ang ®−îc nghiªn cøu Alice (ng−êi göi) v Bob (ng−êi nhËn) chän mét c¸ch bÝ mËt kho¸ K. Sau ®ã dïng K ®Ó t¹o luËt m ho¸ ekv luËt gi¶i m dk. Trong hÖ mËt n y dk hoÆc gièng nh− ek hoÆc dÔ d ng nhËn ®−îc tõ nã (vÝ dô trong hÖ DES qu¸ tr×nh gi¶i m ho n to n t−¬ng tù nh− qu¸ tr×nh m nh−ng thñ tôc kho¸ ng−îc l¹i). C¸c hÖ mËt thuéc lo¹i n y ®−îc gäi l hÖ mËt kho¸ bÝ mËt, nÕu ®Ó lé ek th× l m cho hÖ thèng mÊt an to n. Nh−îc ®iÓm cña hÖ mËt n y l nã yªu cÇu ph¶i cã th«ng tin tr−íc vÒ kho¸ K gi÷a Alice v Bob qua mét kªnh an to n tr−íc khi göi mét b¶n m bÊt kú. Trªn thùc tÕ ®iÒu n y rÊt khã ®¶m b¶o. Ch¼ng h¹n khi Alice v Bob ë c¸ch xa nhau v hä chØ cã thÓ liªn l¹c víi nhau b»ng th− tÝn ®iÖn tö (Email). Trong t×nh huèng ®ã Alice v Bob kh«ng thÓ t¹o mét kªnh b¶o mËt víi gi¸ ph¶i ch¨ng. ý t−ëng x©y dùng mét hÖ mËt kho¸ c«ng khai (hay kho¸ dïng chung) l t×m mét hÖ mËt kh«ng cã kh¶ n¨ng tÝnh to¸n ®Ó x¸c ®Þnh dkkhi biÕt ek. NÕu thùc hiÖn ®−îc nh− vËy th× quy t¾c m ek cã thÓ ®−îc c«ng khai b»ng c¸ch c«ng bè nã trong mét danh b¹ (bëi vËy nªn cã thuËt ng÷ hÖ mËt kho¸ c«ng khai). ¦u ®iÓm cña hÖ mËt kho¸ c«ng khai l ë chç Alice (hoÆc bÊt k× mét ai) cã thÓ göi mét b¶n tin ® m cho Bob (m kh«ng cÇn th«ng tin tr−íc vÒ kho¸ mËt) b»ng c¸ch dïng luËt m c«ng khai ek. Ng−êi nhËn A sÏ l ng−êi duy nhÊt cã thÓ gi¶i ®−îc b¶n m n y b»ng c¸ch sö dông luËt gi¶i m bÝ mËt dk cña m×nh. Cã thÓ h×nh dung hÖ mËt n y t−¬ng tù nh− sau. Alice ®Æt mét vËt v o mét hép kim lo¹i v råi kho¸ nã l¹i b»ng mét kho¸ sè do Bob ®Ó l¹i. ChØ cã Bob l ng−êi duy nhÊt cã thÓ më ®−îc hép v× chØ cã anh ta míi biÕt tæ hîp m cña kho¸ sè cña m×nh. ý t−ëng vÒ mét hÖ mËt kho¸ c«ng khai ® ®ùoc Diffie v Hellman ®−a ra v o n¨m 1976. Cßn viÖc hiÖn thùc ho¸ nã th× do Rivesrt, Shamir v Adleman ®−a ra ®Çu tiªn v o n¨m 1977, hä ® t¹o nªn hÖ mËt næi tiÕng RSA (sÏ ®−îc nghiªn cøu trong ch−¬ng n y). KÓ tõ ®ã mét sè hÖ ®−îc c«ng bè, ®é mËt cña chóng dùa trªn c¸c b i to¸n tÝnh to¸n kh¸c nhau. Sau ®©y l c¸c hÖ mËt kho¸ c«ng khai quan träng : + HÖ mËt RSA: §é b¶o mËt cña hÖ RSA dùa trªn ®é khã cña viÖc ph©n tÝch ra thõa sè nguyªn tè c¸c sè nguyªn lín. HÖ n y sÏ ®−îc m« t¶ trong phÇn 4.3. + HÖ mËt xÕp ba l« Merkle - Hellman: HÖ n y v c¸c hÖ liªn quan dùa trªn tÝnh khã gi¶i cña b i to¸n tæng c¸c tËp con (b i to¸n n y l b i to¸n NP ®Çy ®ñ – l mét líp kh¸ lín c¸c b i to¸n kh«ng cã thuËt gi¶i ®−îc biÕt trong thêi gian ®a thøc). Tuy nhiªn tÊt c¶ c¸c hÖ mËt xÕp ba l« kh¸c nhau ®Òu ® bÞ chøng tá l kh«ng mËt (ngo¹i trõ hÖ mËt Chor – Rivest sÏ ®−îc nªu d−íi ®©y). HÖ mËt n y ®−îc xÐt ë ch−¬ng 5. + HÖ mËt McEliece: HÖ n y dùa trªn lý thuyÕt m ®¹i sè v vÉn cßn ®−îc coi l an to n. HÖ mËt McEliece dùa trªn b i to¸n gi¶i m cho c¸c m tuyÕn tÝnh (còng l mét b i to¸n NP ®Çy ®ñ). HÖ mËt McEliece ®−îc tr×nh b y ë ch−¬ng 5. + HÖ mËt Elgamal: HÖ mËt Elgamal dùa trªn tÝnh khã gi¶i cña b i to¸n logarithm rêi r¹c trªn c¸c tr−êng h÷u h¹n (xem trong ch−¬ng 5). + HÖ mËt Chor - Rivest: HÖ mËt Chor - Rivest còng ®−îc xem nh− mét lo¹i hÖ mËt xÕp ba l«. Tuy nhiªn nã vÉn ®−îc coi l an to n. + HÖ mËt trªn c¸c ®−êng cong Elliptic C¸c hÖ mËt n y l biÕn t−íng c¶u c¸c hÖ mËt kh¸c (ch¼ng h¹n nh− hÖ mËt Elgamal) , chóng l m viÖc trªn c¸c ®−êng cong Elliptic chø kh«ng ph¶i l trªn c¸c tr−êng h÷u h¹n. HÖ mËt n y ®¶m b¶o ®é mËt víi kho¸ sè nhá h¬n c¸c hÖ mËt kho¸ c«ng khai kh¸c (xem ch−¬ng 5). Mét chó ý quan träng l mét hÖ mËt kho¸ c«ng khai kh«ng bao giê cã thÓ ®¶m b¶o ®−îc ®é mËt tuyÖt ®èi (an to n v« ®iÒu kiÖn). Së dÜ nh− vËy v× ®èi ph−¬ng khi nghiªn cøu mét b¶n m y cã thÓ m lÇn l−ît c¸c b¶n râ b»ng luËt m c«ng khai ek cho tíi khi anh ta t×m ®−îc b¶n râ duy nhÊt x ®¶m b¶o y = ek (x). B¶n râ n y chÝnh l kÕt qu¶ gi¶i m cña y. Bëi vËy ta chØ nghiªn cøu ®é mËt vÒ mÆt tÝnh to¸n cña c¸c hÖ mËt n y. Mét kh¸i niÖm cã Ých khi nghiªn cøu hÖ mËt kho¸ c«ng khai l kh¸i niÖm vÒ h m cöa sËp mét chiÒu. Ta ®Þnh nghÜa kh¸i niÖm n y mét c¸ch kh«ng h×nh thøc. H m m kho¸ c«ng khai ek cña Bob ph¶i l mét h m dÔ tÝnh to¸n. Song viÖc t×m h m ng−îc (h m gi¶i m ) ph¶i rÊt khã kh¨n (®èi víi bÊt kú ai kh«ng ph¶i l Bob). §Æc tÝnh dÔ tÝnh to¸n nh−ng khã tÝnh to¸n h m ng−îc th−êng ®−îc gäi l ®Æc tÝnh mét chiÒu. Bëi vËy ®iÒu kiÖn c©n thiÕt l ek ph¶i l h m mét chiÒu. C¸c h m mét chiÒu ®ãng vai trß quan träng trong mËt m häc: chóng rÊt quan trong c¸c hÖ mËt kho¸ c«ng khai v trong nhiÒu lÜnh vùc kh¸c. §¸ng tiÕc l mÆc dï cã rts nhiÒu h m ®−îc coi l h m mét chiÒu nh−ng cho tíi nay vÉn kh«ng tån t¹i mét h m n o cã thÓ chøng minh ®−îc l h m mét chiÒu. Sau ®©y l mét vÝ dô vÒ mét h m ®−îc coi l h m mét chiÒu. Gi¶ sö n l tÝch cña hai sè nguyªn tè lín p v q, gi¶ sö b l mét sè nguyªn d−¬ng. Khi ®ã ta x¸c ®Þnh ¸nh x¹ f : Zn Zn l f(x) = xb mod n (víi b v n ® ®−îc chän thÝch hîp th× ®©y chÝnh l h m m RSA, sau n y sÏ cßn nãi nhiÒu vÒ nã). §Ó x©y dùng mét hÖ mËt kho¸ c«ng khai th× viÖc t×m ®−îc mét h m mét chiÒu vÉn ch−a ®ñ. Ta kh«ng muèn ek l h m mét chiÒu ®èi víi Bob v× anh ta ph¶i cã kh¶ n¨ng gi¶i m c¸c b¶n tin nhËn ®−îc mét c¸ch hiÖu qu¶. §iÒu cÇn thiÕt l Bob ph¶i cã mét cöa sËp chøa th«ng tin bÝ mËt cho phÐp dÔ d ng t×m h m ng−îc cña ek. Nh− vËy Bob cã thÓ gi¶i m mét c¸ch h÷u hiÖu v× anh ta cã mét hiÓu biÕt tuyÖt mËt n o ®ã vÒ K. Bëi vËy mét h m ®−îc gäi l cöa sËp mét chiÒu nÕu nã l h m mét chiÒu v nã trë nªn dÔ tÝnh ng−îc nÕu biÕt mét cöa sËp mhÊt ®Þnh. Ta sÏ xÐt c¸ch t×m mét cöa sËp ®èi víi h m f nªu ë trªn trong phÇn 4.3. C¸c t×m n y sÏ dÉn ®Õn hÖ mËt RSA. 4.2. mét sè vÊn ®Ò s©u h¬n vÒ lý thuyÕt sè Tr−íc khi m« t¶ hÖ mËt RSA l m viÖc ra sao cÇn ph¶i xem xÐt mét sè yÕu tè liªn quan ®Õn lý thuyÕt sè v sè häc modulo. Hai ...