Tài liệu Chữ ký số người xác nhận không thể chối bỏ

Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá §Æt vÊn ®Ò Khi øng dông trªn m¹ng m¸y tÝnh ngµy cµng trë nªn phæ biÕn, thuËn lîi vµ quan träng th× yªu cÇu vÒ an toµn m¹ng, vÒ an ninh d÷ liÖu trªn m¹ng ngµy cµng trë nªn cÊp b¸ch vµ cÇn thiÕt. Nguån tµi nguyªn trªn m¹ng rÊt dÔ bÞ ®¸nh c¾p hoÆc ph¸ háng nÕu kh«ng cã mét c¬ chÕ b¶o mËt cho chóng hoÆc sö dông nh÷ng c¬ chÕ b¶o mËt qu¸ láng lÎo. Th«ng tin trªn m¹ng, dï ®ang truyÒn hay ®îc lu tr÷ ®Òu cÇn ®îc b¶o vÖ. HoÆc c¸c th«ng tin Êy ph¶i ®îc gi÷ bÝ mËt, hoÆc chóng ph¶i cho phÐp ngêi ta kiÓm tra ®Ó tin tëng r»ng chóng kh«ng bÞ söa ®æi so víi d¹ng nguyªn thuû cña m×nh vµ chóng ®óng lµ cña ngêi nhËn göi nã cho ta. M¹ng m¸y tÝnh cã ®Æc ®iÓm næi bËt lµ cã nhiÒu ngêi sö dông, nhiÒu ngêi cïng khai th¸c mét kho tµi nguyªn, ®Æc biÖt lµ tµi nguyªn th«ng tin vµ c¸c ®iÓm cã ngêi sö dông thêng ph©n t¸n vÒ mÆt ®Þa lý. C¸c ®iÓm nµy thÓ hiÖn lîi Ých to lín cña m¹ng th«ng tin m¸y tÝnh ®ång thêi nã còng lµ ®iÒu kiÖn thuËn lîi cho nh÷ng ngêi muèn ph¸ ho¹i an toµn th«ng tin trªn m¹ng m¸y tÝnh. Do ®ã c¸ch tèt nhÊt ®Ó b¶o mËt th«ng tin lµ m· ho¸ th«ng tin tríc khi göi ®i. Môc tiªu c¬ b¶n cña mËt m· lµ cho phÐp 2 ngêi, thêng ®îc ®Ò cËp ®Õn nh Alice vµ Bob, liªn l¹c trªn kªnh kh«ng an toµn theo c¸ch mµ ®èi thñ Orcar kh«ng thÓ hiÓu c¸i g× ®ang ®îc nãi. Kªnh nµy cã thÓ lµ ®êng ®iÖn tho¹i hoÆc m¹ng m¸y tÝnh. Th«ng tin mµ Alice muèn göi ®Õn Bob sÏ ®îc gäi lµ “b¶n râ” (plaintext), cã thÓ lµ bÊt kú tµi liÖu nµo cã cÊu tróc tuú ý. Alice m· b¶n râ b»ng c¸ch dïng kho¸ -1- Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá x¸c ®Þnh tríc, vµ göi b¶n râ thu ®îc trªn kªnh kh«ng an toµn. Orcar dï thu trém ®îc m· trªn kªnh song kh«ng thÓ hiÓu ®îc b¶n râ lµ g×, nhng Bob lµ ngêi biÕt kho¸ m· cã thÓ gi¶i m· vµ thiÕt lËp b¶n râ. Cã hai lo¹i mËt m· lµ mËt m· bÝ mËt vµ mËt m· kho¸ c«ng khai.Trong mËt m· bÝ mËt, 2 ngêi muèn trao ®æi th«ng tin cho nhau ph¶i tho¶ thuËn chän mét c¸ch bÝ mËt kho¸ k. Tõ k suy ra quy t¾c m· ho¸ ek vµ quy t¾c gi¶i m· dk. Trong c¸c hÖ mËt nµy, dk hoÆc trïng víi ek hoÆc dÔ dµng rót ra tõ ek vµ viÖc tiÕt lé ek sÏ lµm cho hÖ thèng kh«ng an toµn. §é an toµn hÖ mËt chÝnh lµ ®é an toµn tÝnh to¸n. Trong thùc tÕ, mét hÖ mËt lµ “an toµn tÝnh to¸n” nÕu ph¬ng ph¸p tèt nhÊt ®· biÕt ®Ó ph¸ nã yªu cÇu mét sè lín kh«ng hîp lý thêi gian tÝnh to¸n, nghÜa lµ qu¸ tr×nh thùc hiÖn tÝnh to¸n cùc kú phøc t¹p, phøc t¹p ®Õn møc ta coi lµ “kh«ng thÓ ®îc”. HÖ mËt kho¸ c«ng khai ®· ®¸p øng ®îc nh÷ng ®ßi hái ®ã. ý tëng n»m sau hÖ mËt kho¸ c«ng khai lµ ë chç nã cã thÓ t×m ra mét hÖ mËt trong ®ã kh«ng thÓ tÝnh to¸n ®Ó x¸c ®Þnh dk khi biÕt ek. Quy t¾c m· ek cã thÓ c«ng khai. Hµm m· ho¸ c«ng khai ek ph¶i dÔ dµng tÝnh to¸n nhng viÖc gi¶i m· ph¶i khã ®èi víi bÊt kú ngêi nµo ngoµi ngêi lËp m·. TÝnh chÊt dÔ tÝnh to¸n vµ khã ®¶o ngù¬c nµy thêng ®îc gäi lµ tÝnh chÊt mét chiÒu. Muèn gi¶i m· c¸c th«ng b¸o nhËn ®îc mét c¸ch hiÖu qu¶ ta cÇn cã mét cöa sËp 1 chiÒu. §iÒu nµy ®¶m b¶o ®é bÝ mËt cao. MÆt kh¸c, m· ho¸ cßn bao gåm c¶ x¸c thùc vµ ch÷ ký sè. X¸c thùc cã nhîc ®iÓm lµ ë ®©y 2 bªn cïng cã chung mét kho¸ nªn kh«ng thÓ ph©n xö ®îc khi 1 trong 2 ngêi chèi bá -2- Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá th«ng b¸o hä ®· göi cho ngêi kia. H¬n n÷a, trong m¹ng cã nhiÒu ngêi sö dông, nÕu mçi cÆp cã mét kho¸ tho¶ thuËn nh vËy th× mçi ngêi ph¶i lu gi÷ n-1 kho¸ bÝ mËt. Khi n ®ñ lín, ®ã lµ mét viÖc phiÒn phøc, phøc t¹p. ChÝnh v× vËy mµ ch÷ ký sè ®îc sö dông nhiÒu h¬n. Ch÷ ký sè cã nhiÖm vô gièng ch÷ ký tay nghÜa lµ nã dïng ®Ó thùc hiÖn c¸c chøc n¨ng x¸c nhËn cña mét ngêi göi trªn mét v¨n b¶n. Nã ph¶i võa mang dÊu vÕt kh«ng chèi c·i ®îc cña ngêi göi, võa g¾n víi tõng bit cña v¨n b¶n mµ nÕu thay ®æi dï chØ mét bit cña v¨n b¶n th× ch÷ ký còng kh«ng cßn ®îc chÊp nhËn. Nãi chung c¸c lîc ®å ch÷ ký th× kh«ng cÇn ®èi tho¹i. Nhng trong mét sè trêng hîp ®Ó t¨ng thªm tr¸ch nhiÖm trong viÖc x¸c nhËn, ngêi ta dïng c¸c giao thøc hái- ®¸p ®Ó x¸c ®Þnh ®é tin cËy cña ch÷ ký. Trong ®å ¸n nµy t«i ®i s©u t×m hiÓu vÒ lîc ®å ch÷ ký chèng chèi bá cã ngêi x¸c nhËn. ë ®©y ch÷ ký cã thÓ ®îc kiÓm tra mµ kh«ng cÇn ®Õn sù céng t¸c cña ngêi ký mµ lµ mét ngêi thø 3- ngêi x¸c nhËn. Ch¬ng I TæNG QUAN VÒ NG¤N NG÷ C I.1. LÞch sö h×nh thµnh vµ ph¸t triÓn Ng«n ng÷ C do Brian W.Kernighan vµ Dennis M.Ritchie ph¸t triÓn vµo ®Çu nh÷ng n¨m 70 t¹i phßng thÝ -3- Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá nghiÖm BELL ( Hoa Kú) víi môc ®Ých ban ®Çu lµ ®Ó ph¸t triÓn hÖ ®iÒu hµnh UNIX. Bèi c¶nh ra ®êi xuÊt ph¸t tõ nhu cÇu cÇn ph¶i cã mét ng«n ng÷ lËp tr×nh hÖ thèng thay thÕ cho hîp ng÷ (Assembly) vèn nÆng nÒ, ®é tin cËy thÊp vµ khã chuyÓn ®æi gi÷a c¸c hÖ m¸y tÝnh kh¸c nhau. Ngoµi viÖc C ®îc dïng ®Ó viÕt hÖ ®iÒu hµnh UNIX, ngêi ta nhanh chãng nhËn ra søc m¹nh cña C trong viÖc xö lý c¸c vÊn ®Ò hiÖn ®¹i cña tin häc: xö lý sè, v¨n b¶n, c¬ së d÷ liÖu, lËp tr×nh híng ®èi tîng. C ®· trë thµnh mét chuÈn mÆc nhiªn. Liªn quan ®Õn sù h×nh thµnh vµ ph¸t triÓn cña ng«n ng÷, cã thÓ kÓ ®Õn mét sè sù kiÖn sau: - N¨m 1978, cuèn gi¸o tr×nh d¹y lËp tr×nh b»ng ng«n ng÷ C “The C programming langguage” do chÝnh 2 t¸c gi¶ cña ng«n ng÷ Brian W.Kernighan vµ Dennis M.Ritchie biªn so¹n ®· ®îc xuÊt b¶n vµ ®îc phæ biÕn réng r·i. - N¨m 1983 mét tiÓu ban cña viÖn tiªu chuÈn quèc gia Mü (ANSI) ®îc thµnh lËp nh»m ®Ò xuÊt ra mét chuÈn cho ng«n ng÷ C. - N¨m 1988 chuÈn ANSI C chÝnh thøc ®îc ban hµnh. ChuÈn nµy bao gåm c¸c m« t¶ vÒ ng«n ng÷ theo Brian W.Kernighan vµ Dennis M.Ritchie vµ quy ®Þnh c¸c th viÖn chuÈn cña ng«n ng÷ C, nhê ®ã t¨ng tÝnh kh¶ chuyÓn cña ch¬ng tr×nh viÕt b»ng C. - Trong thÕ giíi m¸y vi tÝnh cã c¸c hÖ ch¬ng tr×nh dÞch C næi tiÕng nh: Turbo C, Borland C cña Borland Inc; MSC, VC cña Microsoft Corp; Lattice C cña Lattice. -4- Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá I. 2. C¸c tÝnh chÊt ®Æc trng cña ng«n ng÷ C lµ mét ng«n ng÷ lËp tr×nh v¹n n¨ng ®îc dïng ®Ó viÕt c¸c hÖ ®iÒu hµnh nh UNIX còng nh c¸c ch¬ng tr×nh øng dông nh qu¶n lý v¨n b¶n, c¬ së d÷ liÖu. C lµ mét ng«n ng÷ cã møc ®é thÝch nghi cao, gän vµ kh«ng nhÊt thiÕt ph¶i cÇn tíi hîp ng÷. C ®éc lËp víi bÊt kú kiÕn tróc m¸y ®Æc thï nµo vµ víi mét chót thËn träng vÉn dÔ dµng viÕt ®îc c¸c ch¬ng tr×nh “kh¶ chuyÓn” (portability) tøc lµ nh÷ng ch¬ng tr×nh cã thÓ ch¹y mµ kh«ng cÇn ph¶i thay ®æi g× khi cã sù thay ®æi vÒ phÇn cøng. C ®îc sö dông réng r·i trong c¸c lÜnh vùc chuyªn nghiÖp v× ®¸p øng ®îc c¸c yªu cÇu: hiÖu qu¶ cao trong so¹n th¶o ch¬ng tr×nh vµ dÞch ra m· m¸y; tiÕp cËn trùc tiÕp víi c¸c thiÕt bÞ phÇn cøng. C kh«ng ®a ra c¸c phÐp to¸n xö lý trùc tiÕp c¸c ®èi tîng hîp thµnh nh lµ ®èi tîng toµn vÑn; kh«ng x¸c ®Þnh bÊt kú mét ph¬ng tiÖn cÊp ph¸t bé nhí nµo kh¸c ngoµi cÊp ph¸t tÜnh, cÊp ph¸t ®éng theo nguyªn t¾c xÕp chång cho c¸c biÕn côc bé cña hµm; kh«ng cung cÊp c¬ chÕ I/O, kh«ng cã ph¬ng ph¸p truy nhËp tÖp. TÊt c¶ c¸c c¬ chÕ nµy ®îc thùc hiÖn b»ng nh÷ng lêi gäi hµm trong th viÖn. C ®a ra c¸c kÕt cÊu ®iÒu khiÓn c¬ b¶n cÇn cho c¸c ch¬ng tr×nh cã cÊu tróc nh: nhãm tuÇn tù c¸c c©u lÖnh, chän quyÕt ®Þnh (if); chu tr×nh víi phÐp kiÓm tra kÕt thóc ë -5- Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá ®Çu (for, while), hoÆc ë cuèi (do...while); vµ viÖc lùa chän mét trong c¸c trêng hîp cã thÓ (switch). C cung cÊp con trá vµ kh¶ n¨ng ®Þnh ®Þa chØ sè häc. C¸c ®èi cña hµm ®îc truyÒn b»ng c¸ch sao chÐp gi¸ trÞ ®èi vµ hµm ®îc gäi kh«ng thÓ thay ®æi ®îc gi¸ trÞ cña ®èi hiÖn t¹i. C cho phÐp hµm ®îc gäi ®Ö quy vµ c¸c biÕn côc bé cña hµm sÏ “tù ®éng” sinh ra hoÆc t¹o míi víi mçi lÇn gäi míi. C¸c ®Þnh nghÜa hµm kh«ng ®îc lång nhau nhng c¸c biÕn cã thÓ ®îc khai b¸o theo kiÓu cÊu tróc khèi. C¸c hµm cã thÓ dÞch t¸ch biÖt. C¸c biÕn cã thÓ trong hoÆc ngoµi hµm. Hµm chØ biÕt ®îc c¸c biÕn ngoµi trong cïng mét tÖp gèc, hoÆc biÕn tæng thÓ extern. C¸c biÕn tù ®éng cã thÓ ®Æt trong c¸c thanh ghi ®Ó t¨ng hiÖu qu¶, nhng viÖc khai b¸o thanh ghi chØ lµ mét híng dÉn cho ch¬ng tr×nh dÞch vµ kh«ng liªn quan g× ®Õn c¸c thanh ghi ®Æc biÖt cña m¸y. C kh«ng ph¶i lµ mét ng«n ng÷ cã kiÓu m¹nh mÏ theo nghÜa cña PASCAL hoÆc ALGOL/68. Nã t¬ng ®èi tho¶i m¸i trong chuyÓn ®æi d÷ liÖu nhng kh«ng tù ®éng chuyÓn c¸c kiÓu d÷ liÖu mét c¸ch phãng tóng nh cña PL/I. C¸c ch¬ng tr×nh dÞch hiÖn cã ®Òu kh«ng ®a ra c¬ chÕ kiÓm tra chØ sè m¶ng, kiÓu ®èi sè… MÆc dï vËy, C vÉn cßn tån t¹i mét sè nhîc ®iÓm nh mét sè phÐp to¸n cã thø tù thùc hiÖn cha ®óng; mét sè phÇn có -6- Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá ph¸p cã thÓ lµm tèt h¬n; hiÖn cã nhiÒu phiªn b¶n cña ng«n ng÷, chØ kh¸c nhau ë mét vµi chi tiÕt. Tãm l¹i, C vÉn tá ra lµ mét ng«n ng÷ cùc kú hiÖu qu¶ vµ ®Çy søc diÔn c¶m ®èi víi nhiÒu lÜnh vùc øng dông lËp tr×nh. H¬n n÷a, ta biÕt r»ng hÖ mËt chuÈn hay ch÷ ký sè lu«n cÇn mét bé sè rÊt lín tøc lµ kÝch cì cña kh«ng gian kho¸ rÊt lín kho¶ng trªn 300 sè thËp ph©n. Do ®ã, ng«n ng÷ C ®ñ m¹nh ®Ó cã thÓ ®¸p øng ®îc ®iÒu ®ã. Ch¬ng II CH÷ Ký Sè II.1. Giíi thiÖu chung vÒ ch÷ ký sè Nh chóng ta ®· biÕt, ch÷ ký viÕt tay “thêng lÖ” g¾n víi tµi liÖu ®îc dïng ®Ó chØ ra ngêi ®· ký nã. Ch÷ ký ®îc sö dông hµng ngµy nh ®Ó viÕt th, ký hîp ®ång... -7- Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá ë ®©y, chóng ta t×m hiÓu vÒ ch÷ ký hoµn toµn kh¸c ®ã lµ ch÷ ký sè. Nã lµ ph¬ng ph¸p ký th«ng b¸o ®îc lu díi d¹ng ®iÖn tö vµ th«ng b¸o ®îc ký cã thÓ truyÒn trªn m¹ng m¸y tÝnh. Ch÷ ký tay vµ ch÷ ký sè dï cïng cã nhiÖm vô chung lµ ký nhng cã sù kh¸c nhau c¬ b¶n gi÷a chóng. Thø nhÊt, vÒ viÖc ký tµi liÖu: Víi ch÷ ký tay th× ch÷ ký lµ bé phËn vËt lý cña tµi liÖu ®îc ký. Tuy nhiªn, ch÷ ký sè kh«ng g¾n mét c¸ch vËt lý víi th«ng b¸o ®îc ký mµ ®îc g¾n víi th«ng b¸o theo logic, do ®ã thuËt to¸n ®îc dïng ph¶i “trãi” ch÷ ký víi th«ng b¸o theo mét c¸ch nµo ®ã. Thø hai, vÒ viÖc kiÓm tra: ch÷ ký tay ®îc kiÓm tra b»ng c¸ch so s¸nh nã víi nh÷ng c¸i kh¸c, nh÷ng ch÷ ký ®· x¸c thùc. VÝ dô, mét ngêi ký trªn mét tÊm sÐc mua hµng, ngêi b¸n hµng ph¶i so s¸nh ch÷ ký trªn tÊm sÐc víi ch÷ ký n»m ë sau thÎ tÝn dông ®Ó kiÓm tra. TÊt nhiªn, ph¬ng ph¸p nµy kh«ng an toµn l¾m v× nã t¬ng ®èi dÔ ®¸nh lõa bëi ch÷ ký cña ngêi kh¸c. Kh¸c víi ch÷ ký tay, ch÷ ký sè cã thÓ ®îc kiÓm tra b»ng c¸ch dïng thuËt to¸n kiÓm tra c«ng khai ®· biÕt. V× vËy, bÊt kú ngêi nµo ®ã ®Òu cã thÓ kiÓm tra ch÷ ký sè. Vµ viÖc sö dông lîc ®å ký an toµn sÏ ng¨n chÆn kh¶ n¨ng ®¸nh lõa. §iÒu kh¸c nhau c¬ b¶n gi÷a ch÷ ký tay vµ ch÷ ký sè lµ “b¶n sao” th«ng b¸o sè ®îc ký lµ ®ång nhÊt víi b¶n gèc. Trong khi ®ã, b¶n sao chÐp tµi liÖu giÊy ®· ký thêng lµ kh¸c víi b¶n gèc. §iÒu nµy nghÜa lµ ph¶i cÈn thËn ®Ó ng¨n chÆn mét th«ng b¸o ®· ký sè bÞ sö dông l¹i. VÝ dô, nÕu Bob ký th«ng b¸o sè -8- Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá cho quyÒn Alice rót $100 tõ tµi kho¶n ë nhµ b¨ng cña m×nh, anh ta chØ muèn Alice lµm viÖc ®ã mét lÇn. Do ®ã, th«ng b¸o tù nã ph¶i chøa th«ng tin ®Ó ng¨n chÆn Alice lµm l¹i viÖc ®ã nhiÒu lÇn. Lîc ®å ch÷ ký sè gåm 2 thµnh phÇn: mét thuËt to¸n ký vµ mét thuËt to¸n kiÓm tra. Bob cã thÓ ký th«ng b¸o x nhê thuËt to¸n ký (bÝ mËt) Sig. Ch÷ ký thu ®îc Sig(x) sau ®ã cã thÓ ®îc kiÓm tra nhê thuËt to¸n kiÓm tra c«ng khai Ver. Khi cho cÆp (x,y) thuËt to¸n kiÓm tra sÏ tr¶ lêi “®óng” hoÆc “sai” phô thuéc vµo viÖc ch÷ ký cã ®Ých thùc kh«ng? II. 2. §Þnh nghÜa lîc ®å ch÷ ký sè Lîc ®å ch÷ ký sè lµ mét bé n¨m phÇn tö (P, A, K, S, V) tho¶ m·n c¸c ®iÒu kiÖn sau: 1. P _ lµ mét tËp h÷u h¹n c¸c th«ng b¸o. 2. A _tËp h÷u h¹n c¸c ch÷ ký cã thÓ. 3. K _tËp h÷u h¹n c¸c kho¸, kh«ng gian kho¸. 4. Víi mçi k  K,  sigk  S vµ verk V Mçi sigk: P A, 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:  true, Ver(x,y) =  false,  khi khi y  sig  x  . y  sig  x  *Yªu cÇu: - Víi mçi kho¸ k  K, c¸c hµm sigk vµ verk lµ c¸c hµm thêi gian ®a thøc. - Verk lµ hµm c«ng khai; sig k lµ hµm bÝ mËt ®Ó tr¸nh trêng hîp Orcar cã thÓ gi¶ m¹o ch÷ ký cña Bob ®Ó ký th«ng b¸o x. Víi mçi x chØ duy nhÊt Bob tÝnh ®îc ch÷ ký y sao cho: -9- Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá Ver(x, y) = True. Lîc ®å ch÷ ký ph¶i an toµn. Bëi v× Orcar cã thÓ kiÓm tra tÊt c¶ c¸c kh¶ n¨ng cña ch÷ ký y nhê thuËt to¸n kiÓm tra c«ng khai Ver cho tíi khi ®¹t ®îc yªu cÇu tøc lµ t×m ®îc ch÷ ký ®óng. Do ®ã, nÕu cã ®ñ thêi gian cÇn thiÕt Orcar cã thÓ gi¶ m¹o ®îc ch÷ ký cña Bob. V× vËy môc ®Ých cña chóng ta lµ t×m c¸c lîc ®å ch÷ ký sao cho Orcar kh«ng ®ñ thêi gian thùc tÕ ®Ó thö nh thÕ. II. 3. Mét vµi lîc ®å ch÷ ký sè II.3. 1. Lîc ®å ch÷ ký sè RSA Lîc ®å ch÷ ký RSA ®îc ®Þnh nghÜa nh sau: * T¹o kho¸: Cho n = p. q; víi p, q lµ c¸c sè nguyªn tè lín kh¸c nhau, (n) = (p - 1)(q - 1). Cho P = A = Zn vµ ®Þnh nghÜa: K = {(n, p, q, a, b): n = p.q; p, q lµ c¸c sè nguyªn tè; ab  1mod (n)} C¸c gi¸ trÞ n vµ b lµ c«ng khai; c¸c gi¸ trÞ p, q, a lµ bÝ mËt. * T¹o ch÷ ký: Víi K = (n, p, q, a, b) x¸c ®Þnh: SigK(x) = xa mod n * KiÓm tra ch÷ ký: VerK(x, y) = true  x  yb mod n; x, y Zn. Gi¶ sö Bob muèn ký th«ng b¸o x, anh ta tÝnh ch÷ ký y b»ng c¸ch: y = sigK(x) = xa B modn (aB lµ tham sè bÝ mËt cña Bob). - 10 - Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá Bob göi cÆp (x, y) cho Alice. NhËn ®îc th«ng b¸o x vµ ch÷ ký sè y, Alice tiÕn hµnh kiÓm tra ®¼ng thøc: x = yb B modn (bB lµ khãa c«ng khai cña Bob) NÕu ®óng, Alice c«ng nhËn y lµ ch÷ ký trªn x cña Bob. Ngîc l¹i, Alice sÏ coi x kh«ng ph¶i cña Bob göi cho m×nh (ch÷ ký kh«ng tin cËy). Ngêi ta cã thÓ gi¶ m¹o ch÷ ký cña Bob nh sau: chän y, sau ®ã tÝnh x = verK(y), khi ®ã y = sigK(x). Mét c¸ch ®Ó kh¾c phôc khã kh¨n nµy lµ viÖc yªu cÇu x ph¶i cã nghÜa. Do ®ã ch÷ ký gi¶ m¹o nãi trªn sÏ thµnh c«ng víi x¸c suÊt rÊt nhá. Ta cã thÓ kÕt hîp ch÷ ký víi m· ho¸ sÏ lµm cho ®é an toµn cña ch÷ ký t¨ng thªm. Gi¶ sö r»ng, Alice sÏ tÝnh ch÷ ký cña c« ta lµ y = sigAlice(x), vµ sau ®ã m· ho¸ c¶ x vµ y b»ng c¸ch sö dông mËt m· c«ng khai eBob cña Bob, khi ®ã c« ta nhËn ®îc z = eBob(x, y). B¶n m· z sÏ ®îc truyÒn tíi Bob. Khi nhËn ®îc z, viÖc tríc tiªn lµ anh ta gi¶i m· b»ng hµm dBob ®Ó nhËn ®îc (x, y). Sau ®ã anh ta sö dông hµm kiÓm tra c«ng khai cña Alice ®Ó kiÓm tra xem liÖu verAlice(x, y) = true? NÕu Alice m· ho¸ x tríc råi sau ®ã míi ký lªn b¶n m· ®· ®îc m· ho¸ th× sao? Khi ®ã c« ta tÝnh: y = sigAlice(eBob(x)) Alice sÏ truyÒn cÆp (z, y) cho Bob. Bob sÏ gi¶i m· z, nhËn ®îc x vµ kiÓm tra ch÷ ký y trªn b»ng c¸ch sö dông ver Alice. - 11 - Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá Mét vÊn ®Ò tiÒm Èn trong biÖn ph¸p nµy lµ nÕu Orcar cã ®îc cÆp (z, y) kiÓu nµy, anh ta cã thÓ thay thÕ ch÷ ký y cña Alice b»ng ch÷ ký cña anh ta: y’ = sigOrcar(eBob(x)) Chó ý r»ng Orcar cã thÓ ký b¶n m· e bob(x) ngay c¶ khi anh ta kh«ng biÕt b¶n râ x. Khi ®ã, nÕu Orcar truyÒn (z, y’ ) tíi Bob, ch÷ ký cña Orcar sÏ ®îc kiÓm thö v× Bob sö dông ver Orcar, vµ Bob cã thÓ suy ra r»ng b¶n râ x xuÊt ph¸t tõ Orcar. §iÒu nµy còng lµm cho ngêi sö dông hiÓu r»ng nªn ký tríc råi sau ®ã míi tiÕn hµnh m· ho¸. VÝ dô: Gi¶ sö Bob dïng lîc ®å ch÷ ký sè RSA víi n = 247 (p = 13, q = 19); (n) = 12.18 = 216. Kho¸ c«ng khai cña Bob lµ b = 7  a = 7-1mod216 = 31. Bob c«ng khai (n, b) = (247, 7). Bob ký lªn th«ng b¸o x = 100 víi ch÷ ký: y = xa modn = 10031 mod247 = 74. Bob göi cÆp (x, y) = (100, 74) cho Alice. Alice kiÓm tra b»ng c¸ch sö dông kho¸ c«ng khai cña Bob nh sau: x = yb modn = 747 mod247 = 100 = x.  Alice chÊp nhËn y = 74 lµ ch÷ ký tin cËy. II.3.2. Lîc ®å ch÷ ký ElGamal Lîc ®å ch÷ ký sè ElGamal ®îc giíi thiÖu n¨m 1985 vµ ®îc ViÖn tiªu chuÈn vµ C«ng nghÖ quèc gia Mü söa ®æi thµnh chuÈn ch÷ ký sè. Lîc ®å ElGamal kh«ng tÊt ®Þnh còng gièng nh hÖ thèng m· ho¸ c«ng khai ElGamal. §iÒu nµy cã nghÜa lµ - 12 - Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá cã nhiÒu ch÷ ký hîp lÖ cho mét th«ng b¸o bÊt kú. ThuËt to¸n kiÓm tra ph¶i cã kh¶ n¨ng chÊp nhËn bÊt kú ch÷ ký hîp lÖ nµo khi x¸c minh. Lîc ®å ch÷ ký sè ElGamal ®îc ®Þnh nghÜa nh sau: * T¹o kho¸: Cho p lµ sè nguyªn tè sao cho bµi to¸n l«garit rêi r¹c trong Zp lµ khã vµ gi¶ sö  Z *p lµ phÇn tö nguyªn thñy. Cho P = Z *p , A = Z *p  Zp-1 vµ ®Þnh nghÜa: K = {(p, a, , ):  = a modp }. C¸c gi¸ trÞ p, ,  lµ c«ng khai, a lµ bÝ mËt. * T¹o ch÷ ký: Víi K = (p, a, , ) vµ víi sè ngÉu nhiªn k Z *p 1 , ®Þnh nghÜa:sigk(, ), trong ®ã:  = k modp vµ  = (x - a) k -1mod(p - 1). * KiÓm tra ch÷ ký sè: Víi x,   Z *p vµ  Zp-1, ta ®Þnh nghÜa: Ver (x, , ) = True  .   x modp. Chøng minh: NÕu ch÷ ký ®îc thiÕt lËp ®óng th× kiÓm tra sÏ thµnh c«ng v×:    a. r. modp  x modp ( v× a + r  x mod(p - 1)). Bob tÝnh ch÷ ký b»ng c¸ch dïng c¶ gi¸ trÞ bÝ mËt a ( lµ mét phÇn cña kho¸) lÉn sè ngÉu nhiªn bÝ mËt k (dïng ®Ó ký trªn x). ViÖc kiÓm ta cã thÓ thùc - 13 - Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá hiÖn duy nhÊt b»ng th«ng tin c«ng khai. VÝ dô: Gi¶ sö p = 467,  = 2, a = 127 Khi ®ã:  = a modp = 2127mod467 = 132 Gi¶ sö Bob cã th«ng b¸o x = 100 vµ anh ta chän ngÉu nhiªn k = 213 v× (213, 466) =1 vµ 213-1 mod466 = 431 Bob ký trªn x nh sau:  = k modp = 2213mod467 = 29 vµ  = (x - a)k-1 mod(p -1) = (100 – 127. 29).431 mod466 = 51. Ch÷ ký cña Bob trªn x = 100 lµ (29, 51). BÊt kú ngêi nµo ®ã còng cã thÓ kiÓm tra ch÷ ký nµy b»ng c¸ch: 13229 . 2951  189 mod 467 2100  189 mod 467 Do ®ã ch÷ ký lµ tin cËy. B©y giê, ta xÐt ®é an toµn cña lîc ®å ch÷ ký ElGamal. Gi¶ sö Orcar thö gi¶ m¹o ch÷ ký trªn th«ng b¸o x cho tríc mµ kh«ng biÕt a. NÕu Orcar chän gi¸ trÞ  vµ thö t×m  t¬ng øng, anh ta ph¶i tÝnh logarit rêi r¹c cña log x -. MÆt kh¸c, nÕu anh ta chän  tríc vµ sau ®ã thö t×m  th× anh ta ph¶i gi¶i ph¬ng tr×nh    x modp, trong ®ã  lµ Èn. Bµi to¸n nµy cha cã lêi gi¶i, tuy nhiªn dêng nh nã liªn quan ®Õn bµi to¸n ®· nghiªn cøu. VÉn cßn cã kh¶ n¨ng lµ t×m  vµ  ®ång thêi ®Ó (, ) lµ ch÷ ký. HiÖn thêi kh«ng ai t×m ®îc c¸ch gi¶i song còng kh«ng ai kh¼ng ®Þnh ®îc lµ nã kh«ng cã lêi gi¶i. NÕu Orcar chän  vµ , sau ®ã thö gi¶i ®Ó t×m x, anh ta sÏ ph¶i tÝnh bµi to¸n logarit rêi r¹c, tøc ph¶i tÝnh log   . V× - 14 - Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá thÕ Orcar kh«ng thÓ ký mét th«ng ®iÖp ngÉu nhiªn b»ng c¸ch nµy. Tuy nhiªn cã mét c¸ch ®Ó Orcar ký lªn th«ng ®iÖp ngÉu nhiªn b»ng viÖc chän , , x ®ång thêi. Gi¶ thiÕt i vµ j lµ c¸c sè nguyªn 0  i  p – 2; 0  j  p – 2 vµ (j, p - 1) =1. Khi ®ã thùc hiÖn c¸c phÐp tÝnh:  = i j modp  = -.j-1mod(p - 1) x = - i.j-1mod(p - 1) = i. mod(p - 1). Trong ®ã j-1 ®îc tÝnh theo module (p - 1). Ta thÊy r»ng (, ) lµ ch÷ ký hîp lÖ cña x. §iÒu nµy ®îc chøng minh qua viÖc kiÓm tra:    -(i j )-   -i.j  -.i.j i j 1 1  1 modp - modp  x modp. VÝ dô: p = 467;  = 2;  = 132. Gi¶ sö Orcar chän i = 99; j = 179, khi ®ã j -1 mod(p -1) = 151. Anh ta tÝnh:  = 299 132179mod467 = 117  = - 177. 151 mod466 = 41 x = 99. 41 mod 466 = 331 Vµ (117, 41 ) lµ ch÷ ký trªn x = 331. KiÓm tra: 132117 11741  303mod 467 - 15 - Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá vµ 2331  303 mod467 Do ®ã ch÷ ký lµ hîp lÖ. Orcar cã thÓ gi¶ m¹o ch÷ ký theo kiÓu kh¸c lµ b¾t ®Çu tõ th«ng b¸o x ®· ®îc Bob ký. Gi¶ sö (, ) lµ ch÷ ký hîp lÖ trªn x. Khi ®ã Orcar cã kh¶ n¨ng ký lªn nhiÒu th«ng b¸o kh¸c nhau. Gi¶ sö i, j, h lµ c¸c sè nguyªn; 0  h; i, j  p – 2 vµ (h j, p - 1) = 1. Thùc hiÖn c¸c phÐp tÝnh:  = h i j modp  = (h - j)-1mod(p - 1) x’ = (hx + i)(h - j)-1 mod(p - 1) Trong ®ã (h - j)-1®îc tÝnh theo module (p - 1). KiÓm tra:     x modp  (, ) lµ ch÷ ký hîp lÖ cña x’. ' C¶ 2 ph¬ng ph¸p trªn ®Òu t¹o c¸c ch÷ ký gi¶ m¹o hîp lÖ song kh«ng xuÊt hiÖn kh¶ n¨ng ®èi ph¬ng gi¶ m¹o ch÷ ký trªn th«ng ®iÖp cã lùa chän cña chÝnh hä mµ kh«ng ph¶i gi¶i bµi to¸n logarit rêi r¹c. V× thÕ kh«ng cã g× nguy hiÓm vÒ ®é an toµn cña lîc ®å ElGamal. - 16 - Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá Ch¬ng III Hµm Hash III.1. Giíi thiÖu §èi víi x¸c thùc vµ ch÷ ký sè ta thÊy r»ng c¸c thuËt to¸n thêng nhËn ®Çu vµo lµ mét dßng bÝt cã ®é dµi rÊt ng¾n( 64,128,160 bit) vµ tèc ®é thùc hiÖn chËm. MÆt kh¸c, c¸c th«ng b¸o cÇn ký thêng cã ®é dµi kh¸c nhau vµ trong nhiÒu trêng hîp chóng cã ®é dµi lín cì vµi Kil«byte hoÆc vµi Megabyte. Do vËy, muèn ký mét ch÷ ký ng¾n trªn mét th«ng b¸o dµi ta cÇn ph¶i c¾t th«ng b¸o ra nhiÒu ®o¹n cã ®é dµi h÷u h¹n vµ cè ®Þnh råi tiÕn hµnh ký ®éc lËp tõng ®o¹n ®ã - 17 - Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá vµ göi tõng ®o¹n ®ã ®i. Khi ®ã l¹i xuÊt hiÖn nhiÒu vÊn ®Ò nh: - Tèc ®é thùc hiÖn sÏ rÊt chËm v× ph¶i ký trªn qu¸ nhiÒu ®o¹n. - DÔ x¶y ra trêng hîp kh«ng s¾p xÕp ®îc th«ng b¸o theo ®óng trËt tù ban ®Çu. - Cã thÓ bÞ mÊt c¸c ®o¹n riªng biÖt trong qu¸ tr×nh truyÒn tin. §Ó gi¶i quyÕt nh÷ng vÊn ®Ò nµy ta cã thÓ dïng hµm Hash. Hµm Hash chÊp nhËn mét th«ng b¸o cã ®é dµi bÊt kú lµm ®Çu vµo, hµm Hash sÏ biÕn ®æi th«ng b¸o nµy thµnh mét th«ng b¸o rót gän, sau ®ã ta sÏ dïng lîc ®å ch÷ ký ®Ó ký th«ng b¸o rót gän. Ta cã m« h×nh chung nh sau: Th«ng b¸o x ®é dµi tuú ý  Th«ng b¸o rót gän z = h(x) 160 bit  Ch÷ ký y = sigK(x) 320 bit NÕu kh«ng cÇn bÝ mËt x ta sÏ göi cÆp (x, y) cho ngêi nhËn. NÕu cÇn gi÷ bÝ mËt x th× ta sÏ m· ho¸ th«ng b¸o x thµnh x’ vµ göi cÆp (x’, y). III.2. §Þnh nghÜa - 18 - Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá Hµm Hash lµ mét hµm tÝnh to¸n cã hiÖu qu¶ khi ¸nh x¹ c¸c dßng nhÞ ph©n cã ®é dµi tuú ý thµnh c¸c dßng nhÞ ph©n cã ®é dµi cè ®Þnh nµo ®ã. - Hµm Hash yÕu: Hµm Hash ®îc gäi lµ yÕu nÕu cho mét th«ng b¸o x th× vÒ mÆt tÝnh to¸n kh«ng t×m ra ®îc th«ng b¸o x’ kh¸c x sao cho : h(x’) = h(x) - Hµm Hash m¹nh: Hµm Hash ®îc gäi lµ m¹nh nÕu vÒ mÆt tÝnh to¸n kh«ng t×m ra ®îc hai th«ng b¸o x vµ x’ sao cho: x’  x vµ h(x’) = h(x) 1. Chän gi¸ trÞ x ngÉu nhiªn, x  X 2. TÝnh z = h(x) 3. TÝnh x1= A(z) 4. NÕu x1 x th× x1 vµ x va ch¹m díi h( thµnh c«ng) Ngîc l¹i QUIT( thÊt b¹i) - Hµm Hash cã tÝnh chÊt mét chiÒu: Hµm Hash cã tÝnh chÊt mét chiÒu nÕu cho tríc th«ng b¸o rót gän z th× vÒ mÆt tÝnh to¸n kh«ng t×m ra ®îc th«ng b¸o x sao cho h(x) = z. Hµm Hash yÕu lµm cho ch÷ ký sè trë nªn tin cËy gièng nh viÖc ký trªn toµn th«ng b¸o. Hµm Hash m¹nh cã t¸c dông chèng l¹i kÎ gi¶ m¹o t¹o ra hai b¶n th«ng b¸o cã néi dung kh¸c nhau, sau ®ã thu nhËn ch÷ ký hîp ph¸p cho mét b¶n th«ng b¸o dÔ ®îc x¸c nhËn råi lÊy nã gi¶ m¹o lµm ch÷ ký cña th«ng b¸o thø 2. III.3. Mét sè hµm Hash sö dông trong ch÷ ký sè III.3.1. C¸c hµm Hash ®¬n gi¶n - 19 - Ch÷ ký sè ngêi x¸c nhËn kh«ng thÓ chèi bá TÊt c¶ c¸c hµm Hash ®Òu ®îc thùc hiÖn theo nguyªn t¾c chung lµ: §Çu vµo ®îc biÓu diÔn d¹ng mét d·y c¸c khèi cã ®é dµi n bÝt. C¸c khèi n bit nµy ®îc xö lý theo cïng mét kiÓu vµ lÆp ®i lÆp l¹i ®Ó cuèi cïng cho ®Çu ra cã sè bit cè ®Þnh. Hµm Hash ®¬n gi¶n nhÊt lµ thùc hiÖn phÐp to¸n XOR tõng bit mét cña mçi khèi. Nã ®îc biÓu diÔn nh sau: Ci = b1i  b2i …bmi Trong ®ã: Ci: lµ bit thø i cña m· Hash, i = 1, n m: lµ sè c¸c khèi ®Çu vµo. bji: lµ bit thø i trong khèi thø j : lµ phÐp céng modulo 2. S¬ ®å hµm Hash sö dông phÐp XOR: Khèi 1: Khèi 1: … Khèi m: M· b11 b21 … bm1 C1 b12 b22 … bm2 C2 … … … … … b1n b2n … bmn Cn Hash: Ci lµ bit kiÓm tra tÝnh ch½n lÎ cho vÞ trÝ thø i khi ta chia tÖp d÷ liÖu thµnh tõng khèi, mçi khèi cã n vÞ trÝ. Nã cã t¸c dông nh sù kiÓm tra tæng thÓ tÝnh toµn vÑn cña d÷ liÖu. Khi m· ho¸ mét th«ng b¸o dµi th× ta sö dông mode CBC (The Cipher Block Chaining), thùc hiÖn nh sau: - 20 -