zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» An ninh - Bảo mật

Giáo trình tin học : Hệ mật mã và những khả năng tạo liên lạc tuyệt mật của nó phần 2

Chia sẻ: AFASFAF FSAFASF | Ngày: | Loại File: PDF | Số trang:5

Báo xấu

85
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trong ví dụ trên , ta đã dùng các chữ in hoa ch o bản mã, các chữ thường cho bản rõ đêr tiện phân biệt. Quy tắc này còn tiếp tục sử dụng sau này. Nếu một hệ mật có thể sử dụng được trong thực tế thì nó phảo thoả mãn một số tính chất nhất định.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Giáo trình tin học : Hệ mật mã và những khả năng tạo liên lạc tuyệt mật của nó phần 2

Vietebooks Nguyễn Hoàng Cương NhËn xÐt: Trong vÝ dô trªn , ta ®· dïng c¸c ch÷ in hoa ch o b¶n m·, c¸c ch÷ th−êng cho b¶n râ ®ªr tiÖn ph©n biÖt. Quy t¾c nµy cßn tiÕp tôc sö dông sau nµy. NÕu mét hÖ mËt cã thÓ sö dông ®−îc trong thùc tÕ th× nã ph¶o tho¶ m·n mét sè tÝnh chÊt nhÊt ®Þnh. Ngay sau ®©y sÐ nªu ra hai trong sè ®ã: 1. Mçi hµm m· ho¸ eK vµ mçi hµm gi¶i m· dK ph¶i cã kh¶ n¨ng tÝnh to¸n ®−îc mét c¸ch hiÖu qu¶. 2. §èi ph−¬ng dùa trªn x©u b¶n m· ph¶i kh«ng cã kh¶ n¨ng x¸c ®Þnh kho¸ K ®· dïng hoÆc kh«ng cã kh¶ n¨ng x¸c ®Þnh ®−îc x©u b¶n râ x. TÝnh chÊt thø hai x¸c ®Þnh (theo c¸ch kh¸ mËp mê) ý t−ëng ý t−ëng "b¶o mËt". Qu¸ tr×nh thö tÝnh kho¸ K (khi ®· biÕt b¶n m· y) ®−îc gäi lµ m· th¸m (sau nµy kh¸i niÖm nµy sÏ ®ùc lµm chÝnh x¸c h¬n). CÇn chó ý r»ng, nÕu Oscar cã thÓ x¸c ®Þnh ®−îc K th× anh ta cã thÓ gi¶i m· ®−îc y nh− Bob b»ng c¸ch dïng dK. Bëi vËy, viÖc x¸c ®Þnh K chÝ Ýt còng khã nh− viÖc x¸c ®Þnh b¶n râ x. NhËn xÐt r»ng, MDV (theo modulo 26) lµ kh«ng an toµn v× nã cã thÓ bÞ th¸m theo ph−¬ng ph¸p vÐt c¹n. Do chØ cã 26 kho¸ nªn dÔ dµng thö mäi kho¸ dK cã thÓ cho tíi khi nhËn ®−îc b¶n râ cã nghÜa. §iÒu nµy ®−îc minh ho¹ theo vÝ dô sau: VÝ du 1.2 Cho b¶n m· JBCRCLQRWCRVNBJENBWRWN ta sÏ thö liªn tiÕp c¸c kho¸ gi¶i m· d0 ,d1 .. . vµ y thu ®−îc: jbcrclqrwcrvnbjenbwrwn iabqbkpqvbqumaidmavqvm hzapajopuaptlzhclzupul gyzozinotzoskygbkytotk jxynyhmnsynrjexfajxsnsj ewxmxglmrxmqiweziwrmri dvwlwfklqwlphvodyhvqlqh cuvkvejkpvkogucxgupkpg btujudijoujnftbwfojof astitchintimesavesnine Tíi ®©y ta ®· x¸c ®Þnh ®−îc b¶n râ vµ dõng l¹i. Kho¸ t−¬ng øng K = 9. Trang 6
Vietebooks Nguyễn Hoàng Cương Trung b×nh cã thÓ tÝnh ®−îc b¶n râ sau khi thö 26/2 = 13 quy t¾c gi¶i m·. Nh− ®· chØ ra trong vÝ dô trªn , ®iÒu kiÖn ®Ó mét hÖ mËt an toµn lµ phÐp t×m kho¸ vÐt c¹n ph¶i kh«ng thÓ thùc hiÖn ®−îc; tøc kh«ng gian kho¸ ph¶i rÊt lín. Tuy nhiªn, mét kh«ng gian kho¸ lín vÉn ch−a ®ñ ®¶m b¶o ®é mËt. 1.1.2 M∙ thay thÕ Mét hÖ mËt næi tiÕng kh¸c lµ hÖ m· thay thÕ. HÖ mËt nµy ®· ®−îc sö dông hµng tr¨m n¨m. Trß ch¬i ®è ch÷ "cryptogram" trong c¸c bµi b¸o lµ nh÷ng vÝ dô vÒ MTT. HÖ mËt nµy ®−îc nÕu trªn h×nh 1.3. Trªn thùc tÕ MTT cã thÓ lÊy c¶ P vµ C ®Òu lµ bé ch÷ c¸i tiÕng anh, gåm 26 ch÷ c¸i. Ta dïng Z26 trong MDV v× c¸c phÐp m· vµ gi¶i m· ®Òu lµ c¸c phÐp to¸n ®¹i sè. Tuy nhiªn, trong MTT, thÝch hîp h¬n lµ xem phÐp m· vµ gi¶i m· nh− c¸c ho¸n vÞ cña c¸c kÝ tù. H×nh 1.3 M∙ thay thÕ Cho P =C = Z26 . K chøa mäi ho¸n vÞ cã thÓ cña 26 kÝ hiÖu 0,1, . . . ,25 Víi mçi phÐp ho¸n vÞ π ∈K , ta ®Þnh nghÜa: eπ(x) = π(x) vµ dπ(y) = π -1(y) trong ®ã π -1 lµ ho¸n vÞ ng−îc cña π. Sau ®©y lµ mét vÝ dô vÒ phÐp ho¸n vÞ ngÉu nhiªn π t¹o nªn mét hµm m· ho¸ (còng nh−b tr−íc, c¸c kÝ hiÖu cña b¶n râ ®−îc viÕt b»ng ch÷ th−êng cßn c¸c kÝ hiÖu cña b¶n m· lµ ch÷ in hoa). a b c d e f g h i j k l M X N Y A H P O G Z Q W B T n o p q r s t u v w x y Z S F L R C V M U E K J D I Trang 7
Vietebooks Nguyễn Hoàng Cương Nh− vËy, eπ (a) = X, eπ (b) = N,. . . . Hµm gi¶i m· lµ phÐp ho¸n vÞ ng−îc. §iÒu nµy ®−îc thùc hiÖn b»ng c¸ch viÕt hµng thø hai lªn tr−íc råi s¾p xÕp theo thø tù ch÷ c¸i. Ta nhËn ®−îc: A B C D E F G H I J K L M d l r y v o h e z x w p T N O P Q R S T U V W X Y Z b g f j q n m u s k a c I Bëi vËy dπ (A) = d, dπ(B) = 1, . . . §Ó lµm bµi tËp, b¹n ®äc cã gi¶i m· b¶n m· sau b»ng c¸ch dïng hµm gi¶i m· ®¬n gi¶n: M G Z V Y Z L G H C M H J M Y X S S E M N H A H Y C D L M H A. MçÜ kho¸ cña MTT lµ mét phÐp ho¸n vÞ cña 26 kÝ tù. Sè c¸c ho¸n vÞ nµy lµ 26!, lín h¬n 4 ×10 26 lµ mét sè rÊt lín. Bëi vËy, phÐp t×m kho¸ vÐt c¹n kh«ng thÓ thùc hiÖn ®−îc, thËm chÝ b»ng m¸y tÝnh. Tuy nhiªn, sau nµy sÏ thÊy r»ng MTT cã thÓ dÔ dµng bÞ th¸m b»ng c¸c ph−¬ng ph¸p kh¸c. 1.1.3 M∙ Affine MDV lµ mét tr−êng hîp ®Æc biÖt cña MTT chØ gåm 26 trong sè 26! c¸c ho¸n vÞ cã thÓ cña 26 phÇn tö. Mét tr−êng hîp ®Æc biÖt kh¸c cña MTT lµ m· Affine ®−îc m« t¶ d−íi ®©y. trong m· Affine, ta giíi h¹n chØ xÐt c¸c hµm m· cã d¹ng: e(x) = ax + b mod 26, a,b ∈ Z26 . C¸c hµm nµy ®−îc gäi lµ c¸c hµm Affine (chó ý r»ng khi a = 1, ta cã MDV). §Ó viÖc gi¶i m· cã thÓ thùc hiÖn ®−îc, yªu cÇu cÇn thiÕt lµ hµm Affine ph¶i lµ ®¬n ¸nh. Nãi c¸ch kh¸c, víi bÊt kú y ∈ Z26, ta muèn cã ®ång nhÊt thøc sau: ax + b ≡ y (mod 26) ph¶i cã nghiÖm x duy nhÊt. §ång d− thøc nµy t−¬ng ®−¬ng víi: ax ≡ y-b (mod 26) Trang 8
Vietebooks Nguyễn Hoàng Cương V× y thay ®æi trªn Z26 nªn y-b còng thay ®æi trªn Z26 . Bëi vËy, ta chØ cÇn nghiªn cøu ph−¬ng tr×nh ®ång d−: ax ≡ y (mod 26) (y∈ Z26 ). Ta biÕt r»ng, ph−¬ng tf×nh nµy cã mét nghiÖm duy nhÊt ®èi víi mçi y khi vµ chØ khi UCLN(a,26) = 1 (ë ®©y hµm UCLN lµ −íc chung lín nhÊt cña c¸c biÕn cña nã). Tr−íc tiªn ta gi¶ sö r»ng, UCLN(a,26) = d >1. Khi ®ã, ®ång d− thøc ax ≡ 0 (mod 26) sÏ cã Ýt nhÊt hai nghiÖm ph©n biÖt trong Z26 lµ x = 0 vµ x = 26/d. Trong tr−êng hîp nµy, e(x) = ax + b mod 26 kh«ng ph¶i lµ mét hµm ®¬n ¸nh vµ bëi vËy nã kh«ng thÓ lµ hµm m· ho¸ hîp lÖ. VÝ dô, do UCLN(4,26) = 2 nªn 4x +7 kh«ng lµ hµm m· ho¸ hîp lÖ: x vµ x+13 sÏ m· ho¸ thµnh cïng mét gi¸ trÞ ®èi víi bÊt k× x ∈ Z26 . Ta gi¶ thiÕt UCLN(a,26) = 1. Gi¶ sö víi x1 vµ x2 nµo ®ã th¶o m·n: ax1 ≡ ax2 (mod 26) Khi ®ã a(x1- x2) ≡ 0(mod 26) bëi vËy 26 | a(x1- x2) B©y giê ta sÏ sö dông mét tÝnh chÊt cña phÐp chia sau: NÕu USLN(a,b)=1 vµ a ⏐bc th× a ⏐c. V× 26 ⏐ a(x1- x2) vµ USLN(a,26) = 1 nªn ta cã: 26⏐(x1- x2) tøc lµ x1 ≡ x2 (mod 26) Tíi ®©y ta chøng tá r»ng, nÕu UCLN(a,26) = 1 th× mét ®ång d− thøc d¹ng ax ≡ y (mod 26) chØ cã (nhiÒu nhÊt) mét nghiÖm trong Z26 . Do ®ã , nÕu ta cho x thay ®æi trªn Z26 th× ax mod 26 sÏ nhËn ®−îc 26 gi¸ trÞ kh¸c nhau theo modulo 26 vµ ®ång d− thøc ax ≡ y (mod 26) chØ cã mét nghiÖm y duy nhÊt. Kh«ng cã g× ®Æc biÖt ®èi v¬Ý sè 26 trong kh¼ng ®Þnh nµy. Bëi vËy, b»ng c¸ch t−¬ng tù ta cã thÓ chøng minh ®−îc kÕt qu¶ sau: §Þnh lÝ 1.1 Trang 9
Vietebooks Nguyễn Hoàng Cương §ång d− thøc ax ≡ b mod m chØ cã mét nghiÖm duy nhÊt x ∈ Zm víi mäi b ∈ Zm khi vµ chØ khi UCLN(a,m) = 1. V× 26 = 2 ×13 nªn c¸c gi¸ trÞ a ∈ Z26 tho¶ m·n UCLN(a,26) = 1 lµ a = 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23 vµ 25. Tham sè b cã thÓ lµ mét phÇn tö bÊt kú trong Z26 . Nh− vËy, m· Affine cã 12 × 26 = 312 kho¸ cã thÓ ( dÜ nhiªn con sè nµy qu¸ nhØ ®Ó b¶o ®¶m an toµn). B©y giê ta sÏ xÐt bµi to¸n chung víi modulo m. Ta cÇn mét ®Þnh nghÜa kh¸c trong lý thuyÕt sè. §Þnh nghÜa 1.3 Gi¶ sö a ≥ 1 vµ m ≥ 2 lµ c¸c sè nguyªn. UCLN(a,m) = 1 th× ta nãi r»ng a vµ m lµ nguyªn tè cïng nhau. Sè c¸c sè nguyªn trong Zm nguyªn tè cïng nhau víi m th−êng ®−îc ký hiÖu lµ φ(m) ( hµm nµy ®−îc gäi lµ hµm Euler). Mét kÕt qu¶ quan träng trong lý thuyÕt sè cho ta gi¸ trÞ cña φ(m) theo c¸c thõa sè trong phÐp ph©n tÝch theo luü thõa c¸c sè nguyªn tè cña m. ( Mét sè nguyªn p >1 lµ sè nguyªn tè nÕu nã kh«ng cã −íc d−¬ng nµo kh¸c ngoµi 1 vµ p. Mäi sè nguyªn m >1 cã thÓ ph©n tÝch ®−îc thµnh tÝch cña c¸c luü thõa c¸c sè nguyªn tè theo c¸ch duy nhÊt. VÝ dô 60 = 2 3 × 3 × 5 vµ 98 = 2 × 7 2 ). Ta sÏ ghi l¹i c«ng thøc cho φ(m) trong ®Þnh lÝ sau: §Þnh lý 1.2. ( thiÕu ) m = ∏ pi Gi¶ sö Trong ®ã c¸c sè nguyªn tè pi kh¸c nhau vµ ei >0 ,1 §Þnh lý nµy cho thÊy r»ng, sè kho¸ trong m· Affine trªn Zm b»ng mφ(m), trong ®ã φ(m) ®−îc cho theo c«ng thøc trªn. ( Sè c¸c phÐp chän cña b lµ m vµ sè c¸c phÐp chän cña a lµ φ(m) víi hµm m· ho¸ lµ e(x) = ax + b). VÝ dô, khi m = 60, φ(60) = 2 × 2 × 4 = 16 vµ sè c¸c kho¸ trong m· Affine lµ 960. B©y giê ta sÏ xÐt xem c¸c phÐp to¸n gi¶i m· trong mËt m· Affine víi modulo m = 26. Gi¶ sö UCLN(a,26) = 1. §Ó gi¶i m· cÇn gi¶i ph−¬ng tr×nh ®ång d− y ≡ax+b (mod 26) theo x. Tõ th¶o luËn trªn thÊy r»ng, ph−¬ng tr×nh Trang 10

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.