Giáo trình tin học : Tìm hiểu một sơ đồ chữ kí số phần 1

Tham khảo tài liệu giáo trình tin học : tìm hiểu một sơ đồ chữ kí số phần 1, công nghệ thông tin, an ninh - bảo mật phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Giáo trình tin học : Tìm hiểu một sơ đồ chữ kí số phần 1Vietebooks Nguyễn Hoàng Cương Ch−¬ng 6Giáo trình tin học : Tìm hiểu một sơ đồ chữ kí số C¸c s¬ ®å ch÷ kÝ sè6.1 giíi thiÖu. Trong ch−¬ng nµy, chóng ta xem xÐt c¸c s¬ ®å ch÷ kÝ sè (cßn ®−îc gäilµ ch÷ kÝ sè ). Ch÷ kÝ viÕt tay th«ng th−êng trªn tµI liÖu th−êng ®−îc dïng ®Óx¸c ng−êi kÝ nã. Ch÷ kÝ ®−îc dïng hµng ngµy ch¼ng h¹n nh− trªn mét bøc th−nhËn tiÒn tõ nhµ b¨ng, kÝ hîp ®ång... S¬ ®å ch÷ kÝ lµ ph−¬ng ph¸p kÝ mét bøc ®iÖn l−u d−íi dang ®iÖn tõ.Ch¼ng h¹n mét bøc ®iÖn cã ký hiÖu ®−îc truyÒn trªn m¹ng m¸y tinh. Ch−¬ngtr×nh nµy nghiªn cøu vµi s¬ ®å ch÷ kÝ. Ta sÏ th¶o luËn trªn mét vµI kh¸c biÖtc¬ b¶n giöa c¸c ch÷ kÝ th«ng th−êng vµ ch÷ kÝ sè. §Çu tiªn lµ mét vÊn ®Ò kÝ mét tµi liÖu. Víi ch÷ kÝ th«ng th−êng, nã lµmét phÇn vËt lý cña tµi liÖu. Tuy nhiªn, mét ch÷ kÝ sè kh«ng g¾n theo kiÓuvËt lý vµo bøc ®iÖn nªn thuËt to¸n ®−îc dïng ph¶i ”kh«ng nh×n thÊy” theoc¸ch nµo ®ã trªn bøc ®iÖn. Thø hai lµ vÊn ®Ò vÒ kiÓm tra. Ch÷ kÝ th«ng th−êng ®−îc kiÓm tra b»ngc¸ch so s¸nh nã víi c¸c ch÷ kÝ x¸c thùc kh¸c. vÝ dô, ai ®ã kÝ mét tÊm sÐc ®Ómua hµng, ng−êi b¸n ph¶i so s¸nh ch÷ kÝ trªn m¶nh giÊy víi ch÷ kÝ n»m ë mÆtsau cña thÎ tÝn dông ®Ó kiÓm tra. DÜ nhiªn, ®©y kh«ng ph¶i lµ ph−¬g ph¸p antoµn v× nã dÓ dµng gi¶ m¹o. M¾t kh¸c, c¸c ch÷ kÝ sè cã thÓ ®−îc kiÓm tra nhêdïng mét thuËt to¸n kiÓm tra c«ng khai. Nh− vËy, bÊt kú ai còng cã thÓ kiÓmtra d−îc ch÷ kÝ sè. ViÖc dïng mét s¬ ®å ch÷ kÝ an toµn cã thÓ sÏ ng¨n chÆnd−îc kh¶ n¨ng gi¶ m¹o. Sù kh¸c biÖt c¬ b¶n kh¸c gi÷a ch÷ kÝ sè vµ ch÷ kÝ th«ng th−êng b¶ncopy tµi liÖu ®−îc kÝ b¨ng ch÷ kÝ sè ®ång nhÊt víi b¶n gèc, cßn copy tµi liÖucã ch÷ kÝ trªn giÊy th−êng cã thÓ kh¸c víi b¶n gèc. §iÒu nµy cã nghÜa lµ ph¶icÈn thËn ng¨n ch¨n mét bøc kÝ sè khái bÞ dung l¹I. VÝ dô, Bob kÝ mét bøc ®iÖnx¸c nhËn Alice cã kh¶ n¨ng lµm ®iÒu ®ã mét lÇn. V× thÕ, b¶n th©n bøc ®iÖncÇn chøa th«ng tin (ch¼ng h¹n nh− ngµy th¸ng) ®Ó ng¨n nã khái bÞ dung l¹i. Mét s¬ ®å ch÷ kÝ sè th−êng chøa hai thµnh phÇn: thuËt to¸n kÝ vµ thuËtto¸n x¸c minh. Bob cã thÓ kÝ ®iÖn x dïng thuËt to¸n kÝ an toµn. Ch÷ kÝ sig(x)nhËn ®−îc cã thÓ kiÓm tra b»ng thuËt to¸n x¸c minh c«ng khai ver. Khi chotr−íc cÆp (x,y), thuËt to¸n x¸c minh cã gi¸ trÞ TRUE hay FALSE tuú thuécvµo ch÷ kÝ ®−îc thùc nh− thÕ nµo. D−íi ®©y lµ ®Þnh nghÜa h×nh thøc cña ch÷kÝ:§Þnh nghÜa 6.1 Trang 1Vietebooks Nguyễn Hoàng Cương Mét s¬ ®å ch÷ kÝ sè lµ bé 5( P,A, K,S,V) tho¶ m·n c¸c ®iÒu kiÖn d−íi®©y: 1. P lµ tËp h÷u h¹n c¸c bøc ®iÖn cã thÓ. 2. A lµ tËp h÷u h¹n c¸c ch÷ kÝ cã thÓ. 3. K kh«ng gian kho¸ lµ tËp h÷u h¹n c¸c kho¸ cã thÓ. 4. Víi mçi K thuéc K tån t¹I mét thuËt to¸n kÝ sigk ∈ S vµ lµ mét thuËtto¸n x¸c minh verk∈ V. Mçi sigk : P → A vµ verk: P×a →{true,false} lµnh÷ng hµm sao cho mçi bøc ®iÖn x∈ P vµ mèi ch÷ kÝ y∈ a tho¶ m·n ph−¬ngtr×nh d−íi ®©y. True nÕu y=sig(x) verk False nÕu y# sig(x) Víi mçi k thuéc K hµm sigk vµ verk lµ c¸c hµm th¬× than ®a thøc.Verk sÏ lµ hµm c«ng khai sigk lµ mËt. Kh«ng thÓ dÓ dµng tÝnh to¸n ®Ó gi¶ m¹och÷ kÝ cña Bob trªn bøc ®iÖn x. NghÜa lµ x cho tr−íc, chØ cã Bob míi cã thÓtÝnh ®−îc y ®Ó verk = True. Mét s¬ ®å ch÷ kÝ kh«ng thÓ an toµn v« ®iÒu kiÖn v×Oscar cã thÓ kiÓm tra tÊt c¶ c¸c ch÷ sè y cã thÓ cã trªn bøc ®iÖn x nhê dïngthu©t to¸n ver c«ng khai cho ®Õn khi anh ta t×m thÊy mét ch÷ kÝ ®óng. Vi thÕ,nÕu cã ®ñ thêi gian. Oscar lu«n lu«n cã thÓ gi¶ m¹o ch÷ kÝ cña Bob. Nh− vËy,gièng nh− tr−êng hîp hÖ thèng m· kho¸ c«ng khai, môc ®Ých cña chóng ta lµt×m c¸c s¬ ®å ch÷ kÝ sè an toan vÒ mÆt tÝnh to¸n. Xem thÊy r»ng, hÖ thèng m· kho¸ c«ng khai RSA cã thÓ dïng lµm s¬®å ch÷ kÝ sè, Xem h×nh 6.1. Nh− vËy, Bob kÝ bøc ®iÖn x dïng qui t¾c gi¶i m· RSA lµ dk,. Bob lµng−êi t¹o ra ch÷ kÝ v× dk = sigk lµ mËt. ThuËt to¸n x¸c minh dïng qui t¾c m·RSA ek. BÊt k× ai cñng cã x¸c minh ch÷ kÝ vi ek ®−îc c«ng khai. Chó ý r»ng, ai ®ã cã thÓ gi¶ m¹o ch÷ kÝ cña Bob trªn mét bøc ®iÖn “ngÈu nhiªn” x b»ng c¸ch t×m x=ek(y) víi y nµo ®ã; khi ®ã y= sigk(x). Métph¸p xung quanh vÊn ®Ò khã kh¨n nµy lµ yªu cÇu bøc ®iÖn ch−a ®ñ phÇn d− ®Óch÷ kÝ gi¶ m¹o kiÓu nµy kh«ng t−¬ng øng víi bøc ®iÖn ®©y nghÜa lµ x trõ métx¸c suÊt rÊt bÐ. Cã thÓ dïng c¸c hµm hash trong viÖc kÕt nèi víi c¸c s¬ ®å ch÷kÝ sè sÏ lo¹i trõ ®−îc ph−¬ng ph¸p gi¶ m¹o nµy (c¸c hµm hash ®−îc xÐt trongch−¬ng 7). H×nh 6.1 s¬ ®å ch÷ kÝ RSA Trang 2Vietebooks Nguyễn Hoàng Cương Cho n= pq, p vµ q lµ c¸c sè nguyªn tè. Cho p =a= Zn vµ ®Þnh nghÜa p= {(n,p,q,a,b):=n=pq,p vµ q lµ nguyªn tè, ab ≡ 1(mod( φ (n))) }. C¸c gi¸ trÞ ...