Một số thuật toán ký và xác nhận chữ ký điện tử

Tr­êng ®¹i häc quèc gia hµ néi Khoa c«ng nghÖ Hoµng ThÞ Thanh LiÔu Mét sè thuËt to¸n ký vµ x¸c nhËn ch÷ ký ®IÖn tö kho¸ luËn tèt nghiÖp hÖ ®¹i häc chÝnh quy Ngµnh: C«ng nghÖ th«ng tin Hµ Néi 6-2001 Tr­êng ®¹i häc quèc gia hµ néi Khoa c«ng nghÖ Hoµng ThÞ Thanh LiÔu Mét sè thuËt to¸n ký vµ x¸c nhËn ch÷ ký ®IÖn tö kho¸ luËn tèt nghiÖp hÖ ®¹i häc chÝnh quy Ngµnh: C«ng nghÖ th«ng tin C¸n bé h­íng dÉn: TS. TrÞnh NhËt TiÕn Hµ Néi 6-2001 Môc lôc Lêi nãi ®Çu TruyÒn th«ng trªn m¹ng ®·, ®ang vµ sÏ phæ biÕn trong c¸c ho¹t ®éng kinh tÕ x· héi. Th«ng tin ®­îc truyÒn ®i nhanh chãng, tiÖn lîi. Ng­êi ta cã thÓ “nãi chuyÖn” víi nhau, gi¶i trÝ cïng nhau, mua b¸n trao ®æi víi nhau trªn m¹ng,. . . khi c¸ch xa nhau hµng tr¨m ngµn c©y sè. ViÖc mua b¸n trªn m¹ng ®­îc thùc hiÖn nh­ thÕ nµo? Víi mét giao dÞch mua b¸n b×nh th­êng, ng­êi mua vµ ng­êi b¸n x¸c nhËn sù ®ång ý mua b¸n b»ng c¸ch ký tay vµo cuèi hîp ®ång mua b¸n. V× b»ng c¸ch nµo ®ã ng­êi ta ph¶i thÓ hiÖn ®ã lµ ch÷ ký cña hä vµ kÎ kh¸c kh«ng thÓ gi¶ m¹o. Mäi c¸ch sao chÐp trªn v¨n b¶n th­êng ®Òu bÞ ph¸t hiÖn v× b¶n sao dÔ bÞ ph©n biÖt ®­îc víi b¶n gèc. Mua b¸n trªn m¹ng còng ®­îc thùc hiÖn theo c¸ch thøc t­¬ng tù nh­ vËy. NghÜa lµ ng­êi göi vµ ng­êi nhËn còng ph¶i “ký” vµo hîp ®ång mua b¸n. Mét sè v¨n b¶n kh¸c còng cÇn ph¶i x¸c nhËn tr¸ch nhiÖm cña ng­êi göi ®èi víi v¨n b¶n göi ®i tøc lµ hä ph¶i “ký” vµo v¨n b¶n tr­íc khi göi. Nh­ng “ký” trªn v¨n b¶n truyÒn qua m¹ng nh­ thÕ nµo, khi tÊt c¶ néi dung v¨n b¶n ®Òu ®­îc biÓu diÔn d­íi d¹ng sè ho¸ (chØ dïng hai sè 0 vµ 1 – ta gäi v¨n b¶n lo¹i nµy lµ v¨n b¶n sè). ViÖc gi¶ m¹o vµ sao chÐp l¹i ®èi víi v¨n b¶n sè lµ hoµn toµn dÔ dµng vµ kh«ng thÓ ph©n biÖt ®­îc b¶n gèc víi b¶n sao. H¬n n÷a, mét v¨n b¶n sè cã thÓ bÞ c¾t d¸n, l¾p ghÐp lµ hoµn toµn cã thÓ vµ ta kh«ng thÓ ph©n biÖt ®­îc b¶n gèc víi b¶n sao. VËy mét ch÷ ký ë cuèi v¨n b¶n lo¹i nµy kh«ng thÓ chÞu tr¸ch nhiÖm ®èi víi toµn néi dung v¨n b¶n. Ch÷ ký nh­ thÕ nµo th× míi thÓ hiÖn ®­îc tr¸ch nhiÖm ®èi víi toµn bé v¨n b¶n? Ch¾c ch¾n ch÷ ký ®ã ph¶i ®­îc ký trªn tõng bÝt cña v¨n b¶n. Nh­ vËy th«ng tin trªn m¹ng cã thÓ bÞ lÊy c¾p, bÞ c¾t d¸n, l¾p ghÐp mµ ®èi víi nh÷ng v¨n b¶n cÇn ký tªn hay cÇn sù x¸c nhËn cña ng­êi göi ®èi víi v¨n b¶n l¹i lµ nh÷ng v¨n b¶n quan träng (nhÊt lµ trong c¸c lÜnh vùc qu©n sù, ng©n hµng, th­¬ng m¹i ®iÖn tö), cÇn ®­îc b¶o vÖ an toµn khi truyÒn trªn m¹ng. M· ho¸ th«ng tin sÏ gióp chóng ta b¶o vÖ th«ng tin an toµn. Trë l¹i c©u hái “ký” trªn v¨n b¶n sè ®­îc thùc hiÖn nh­ thÕ nµo? Thùc chÊt cña viÖc ký ®iÖn tö lµ m· ho¸. ViÖc x¸c nhËn ch÷ ký lµ kiÓm nghiÖm viÖc m· ho¸ trªn cã ®óng kh«ng. LuËn v¨n cña em ®i vµo nghiªn cøu t×m hiÓu mét sè thuËt to¸n ký vµ x¸c nhËn ch÷ ký thùc chÊt lµ thuËt to¸n m· ho¸ vµ viÖc kiÓm tra viÖc m· ho¸. Ch­¬ng I. Mét sè kh¸i niÖm c¬ së. Tr×nh bµy nh÷ng kh¸i niÖm lµm c¬ së cho lý thuyÕt m· ho¸ th«ng tin vµ ký ®iÖn tö. Ch­¬ng II. VÊn ®Ò m· ho¸. Tr×nh bµy kh¸i niÖm chung vÒ hÖ mËt m· vµ mét hÖ m· kho¸ c«ng khai - hÖ mËt m· RSA. Ch­¬ng III. VÊn ®Ò ký ®iÖn tö. Nghiªn cøu chung vÒ mét sè s¬ ®å ch÷ ký, bao gåm mét sè thuËt to¸n ký, giao thøc chèi bá, giao thøc kiÓm thö . . . Ch­¬ng IV. Mét thö nghiÖm ký ®iÖn tö theo s¬ ®å ch÷ ký RSA. Thö nghiÖm m· ho¸ th«ng tin theo hÖ MËt m· RSA vµ ký ®iÖn tö theo s¬ ®å ch÷ ký RSA. Trong ch­¬ng tr×nh thö nghiÖm, viÖc m· ho¸ vµ ký lµ trªn 1 v¨n b¶n víi bé ch÷ c¸i tiÕng Anh. ViÖc sö dông víi bé ch÷ c¸i kh¸c (nh­ bé ch÷ c¸i tiÕng ViÖt) còng t­¬ng tù nh­ vËy. Ch­¬ng tr×nh ®­îc viÕt b»ng ng«n ng÷ Turbo C/C++. Ch­¬ng I Mét sè kh¸i niÖm c¬ së 1. 1. KÝ hiÖu vµ kh¸i niÖm * KÝ hiÖu chia hÕt: Cho a vµ b lµ hai sè nguyªn d­¬ng. - Sè a chia hÕt cho sè b ký hiÖu lµ a M b Û Tån t¹i n Î N sao cho a = b*n, - Khi ®ã ng­êi ta nãi b lµ ­íc cña a vµ ký hiÖu: b | a. * ­íc sè chung lín nhÊt: Cho a vµ b lµ hai sè nguyªn d­¬ng. - ¦íc sè chung lín nhÊt cña a vµ b lµ sè tù nhiªn m lín nhÊt sao cho m | a vµ m | b. Khi ®ã ký hiÖu lµ ¦CLN(a, b) = m. * Hai sè nguyªn tè cïng nhau: Cho a vµ b lµ hai sè nguyªn d­¬ng. - Sè a vµ sè b ®­îc gäi lµ 2 nguyªn tè cïng nhau Û ¦CLN (a, b) = 1. *§ång d­ modulo: Cho n Î N, n ¹ 0 vµ a, b Î . KÝ hiÖu a º b (mod n) nghÜa lµ a ®ång d­ víi b theo mod n Û tån t¹i sè nguyªn k Î sao cho a = b+k*n Tøc lµ (a-b) = k*n, nh­ vËy n | (a-b). * Mét sè tÝnh chÊt cña ®ång d­ modulo: (a±b) (mod n) º [(a mod n) ±(b mod n)] (mod n) (a*b) (mod n) º [(a mod n) *(b mod n)] (mod n) * Kh¸i niÖm Nhãm: Nhãm lµ mét cÆp (G, *), trong ®ã G lµ tËp hîp kh¸c rçng, * lµ phÐp to¸n hai ng«i trªn G tho¶ m·n ba ®iÒu kiÖn sau: PhÐp to¸n cã tÝnh kÕt hîp: (x*y)* z = x*(y*z) víi mäi x, y, z ÎG. Cã phÇn tö phÇn tö trung lËp e Î G: x*e = e*x = x víi mäi x Î G. 3. Víi mäi xÎG, cã phÇn tö nghÞch ®¶o x’Î G: x*x’ = x’*x = e * Nhãm Cyclic: - Nhãm G ®­îc gäi lµ nhãm Cyclic nÕu nã ®­îc sinh ra bëi mét trong c¸c phÇn tö cña nã. Tøc lµ cã phÇn tö g Î G mµ mäi phÇn tö a Î G ®Òu tån t¹i sè n Î N ®Ó gn = a. - Khi ®ã g ®­îc gäi lµ phÇn tö sinh hay phÇn tö nguyªn thuû cña nhãm G. VÝ dô: Nhãm céng Z gåm c¸c sè nguyªn lµ nhãm Cyclic cã phÇn tö sinh lµ 1. - CÊp cña G lµ sè phÇn tö cña G nÕu G cã h÷u h¹n phÇn tö, vµ b»ng ¥ nÕu G cã v« h¹n phÇn tö. VÝ dô: Nhãm céng Z gåm c¸c sè nguyªn lµ nhãm Cyclic v« h¹n. - NÕu kh«ng tån t¹i sè tù nhiªn n ®Ó gn =e th× G cã cÊp lµ ¥. - Trong tr­êng hîp ng­îc l¹i, tån t¹i sè tù nhiªn nhá nhÊt n mµ gn = e th× G sÏ gåm n phÇn tö kh¸c nhau: e, g, g2, g3, .. . , gn-1. Khi ®ã G ®­îc gäi lµ nhãm Cyclic h÷u h¹n cÊp n. - PhÇn tö a Î G ®­îc gäi lµ cã cÊp d nÕu d lµ sè nguyªn d­¬ng nhá nhÊt sao cho ad = e. Nã cã cÊp 1 nÕu a = e. ChÝnh v× lÏ trªn, nhãm Cyclic cßn ®­îc ®Þnh nghÜa nh­ sau: - Nhãm G ®­îc gäi lµ nhãm Cyclic nÕu tån t¹i sè g sao cho mäi phÇn tö trong G ®Òu lµ mét luü thõa nguyªn nµo ®ã cña g. * Nhãm con: Cho G lµ mét nhãm, cho S Ì G vµ S ¹ f. - S ®­îc gäi lµ nhãm con cña G nÕu 1. PhÇn tö trung lËp e cña G n»m trong S. 2. S khÐp kÝn ®èi víi luËt hîp thµnh trong G (tøc lµ x*y Î S víi mäi x, yÎ S). 3. S khÐp kÝn ®èi víi phÐp lÊy nghÞch ®¶o trong G (tøc x-1 Î S víi mäi xÎS). * KÝ hiÖu: Zn = {0, 1, 2, .. . , n-1}. Tøc Zn lµ tËp c¸c sè nguyªn kh«ng ©m < n. TËp nµy cïng víi phÐp céng lËp thµnh nhãm Cyclic cã phÇn tö sinh lµ 1. §ã lµ nhãm h÷u h¹n cã cÊp n. = {e Î Zn, e lµ nguyªn tè cïng nhau víi n}. Tøc lµ e # 0. - §ã lµ tËp c¸c sè nguyªn d­¬ng < n, nh­ng nguyªn tè cïng nhau víi n. - ®­îc gäi lµ tËp ThÆng d­ thu gän theo mod n, lËp thµnh mét nhãm víi phÐp nh©n mod n. f(n) lµ sè c¸c phÇn tö cña tËp . * Mét sè kÕt qu¶: Nh÷ng kÕt qu¶ sau ®· ®­îc chøng minh, nh¾c l¹i ®Ó sö dông. - §Þnh lý Lagrange: Cho G lµ nhãm cÊp n vµ gÎ G. Khi ®ã CÊp cña g lµ ­íc cña n. - HÖ qu¶: Gi¶ sö gÎ cã CÊp m th× m lµ ­íc cña f(n). NÕu b Î th× bf(n) º 1 (mod n). NÕu p lµ sè nguyªn tè th× f(p) = p-1. Do ®ã víi mäi b Î (tøc b nguyªn tè víi p) th× bf(p) º 1 (mod n) hay bp -1 º 1 (mod n). - §Þnh lý: NÕu p lµ sè nguyªn tè th× lµ nhãm Cyclic. Chó ý Theo c¸c ®Þnh nghÜa trªn ta cã: phÇn tö a Î cã cÊp d nÕu d lµ sè nguyªn d­¬ng nhá nhÊt sao cho ad = e trong , tøc lµ ad º 1 (mod n). 1. 2. Logarit rêi r¹c * Kh¸i niÖm Logarit rêi r¹c: Cho p lµ sè nguyªn tè, a lµ phÇn tö nguyªn thuû cña Zp, bÎ Logarit rêi r¹c chÝnh lµ viÖc gi¶i ph­¬ng tr×nh x = loga b (mod p) víi Èn x. Hay ph¶i t×m sè x duy nhÊt sao cho: ax º b (mod p). - Bæ ®Ò: NÕu (a, n) = 1 th× tån t¹i a-1 Î Zn tho¶ m·n a * a-1 º 1 (mod n) - §Þnh lý (Euler tæng qu¸t): NÕu (a, n) = 1 th× af(n) mod n = 1 - HÖ qu¶: Víi p lµ mét sè nguyªn tè vµ (a, p) = 1 th× ap-1 (mod p) = 1 1. 3. ThÆng d­ bËc hai vµ ký hiÖu Legendre * ThÆng d­ bËc hai: Cho p lµ sè nguyªn tè lÎ, x lµ mét sè nguyªn d­¬ng £ p-1. x ®­îc gäi lµ thÆng d­ bËc hai mod p, nÕu ph­¬ng tr×nh y2 º x mod p cã lêi gi¶i. * KÝ hiÖu Legendre: Cho p lµ sè nguyªn tè lÎ, vµ a lµ mét sè nguyªn d­¬ng bÊt kú. ký hiÖu Legendre nh­ sau: a 0 nÕu a º 0 mod p = 1, nÕu a lµ thÆng d­ bËc hai mod p b 1, trong c¸c tr­êng hîp cßn l¹i. 1. 4. Hµm mét phÝa vµ hµm cöa sËp mét phÝa. Hµm f(x) ®­îc gäi lµ hµm mét phÝa nÕu tÝnh y = f(x) th× “dÔ”, nh­ng tÝnh x = f -1 (y) l¹i rÊt “khã”. VÝ dô: 1. Hµm f(x) = a x (mod p), víi p lµ sè nguyªn tè lín, (a lµ phÇn tö nguyªn thuû mod p) lµ hµm mét phÝa. - Hµm f(x) ®­îc gäi lµ hµm cöa sËp mét phÝa nÕu tÝnh y = f(x) th× “dÔ”, tÝnh x = f -1 (y) l¹i rÊt “khã”. Tuy nhiªn cã cöa sËp z ®Ó tÝnh x = f -1 (y) lµ “dÔ”. VÝ dô: Hµm f(x) = xa (mod n) (víi n lµ tÝch cña hai sè nguyªn tè lín n = p*q) lµ hµm mét phÝa. NÕu chØ biÕt a vµ n th× tÝnh x = f-1(y) rÊt khã nh­ng nÕu biÕt cöa sËp p vµ q th× tÝnh ®­îc f-1(y) lµ kh¸ dÔ. 1. 5. ThuËt to¸n tÝnh nghÞch ®¶o Cho a Î, a-1 ®­îc gäi lµ nghÞch ®¶o cña a Û a*a-1 (mod n) = 1. Mét sè thuËt to¸n tÝnh nghÞch ®¶o: Cho a-1 ch¹y tõ 2 ®Õn n-1 ®Õn khi ®­îc a*a-1 (mod n) = 1. NÕu biÕt f (n) th× chØ cÇn tÝnh: a-1 º af (n)-1 (mod n) Dïng thuËt to¸n Euclidean më réng nh­ sau: §Çu vµo: b vµ n. §Çu ra: - nghÞch ®¶o cña b theo mod n nÕu tån t¹i, - 0 nÕu kh«ng tån t¹i §Æt n0 = n; b0 = b; t0 = 1; t1 = 1; q = n0/b0; r = n0 - q*b0; while(r>0) { t2 = t0- q*t1; if(t2³0 ) t2 = t2 mod n; else t2 = n- (- t2 mod n); t0 = t1; t1 = t2; n0 = b0; b0 = r; q = n0/b0; r = n0- q *b0; } if(b0 = = 1) return t mod n; else return 0; 1. 6. ThuËt to¸n ph©n tÝch ra thõa sè Bµi to¸n: cho n lµ tÝch cña hai sè nguyªn tè lín p vµ q, n = p*q, bµi to¸n ®Æt ra lµ nÕu biÕt n, cã c¸ch nµo ®Ó t×m ®­îc p vµ q kh«ng? HiÖn nay ng­êi ta ch­a cã c¸ch nµo tÝnh trùc tiÕp p, q h÷u hiÖu tõ n trõ khi biÕt f(n). V× khi biÕt f (n), ta cã: p*q = n f (n) = (p-1)*(q-1) Þ p+q = n-f(n)+1 Dùa vµo ®Þnh lý Viet p vµ q lµ nghiÖm cña ph­¬ng tr×nh: x2 - (n-f(n) +1)*x+n = 0 Gi¶i ph­¬ng tr×nh nµy ta dÔ dµng t×m ®­îc p vµ q. VÝ dô n = 84773093, f(n) = 84754668 Þ q = 9539, p = 8887. Ngoµi ra theo c¸ch cæ ®iÓn, sö dông thuËt to¸n : // Input: n // Output: p tho¶ m·n p | n // // 0 trong tr­êng hîp ng­îc l¹i for( int i = 3; i< = sqrt(n); i+ = 2) if (!n%i) return i; return 0; Trong thuËt to¸n trªn vßng lÆp lµ (n1/ 2/2). NÕu n cã 512 bit, gi¸ trÞ lín nhÊt cña n lµ 2512. NÕu 1 m¸y tÝnh thùc hiÖn 106 chØ lÖnh trong 1 gi©y th× thêi gian thùc hiÖn lµ: T = n1/ 2 /2 £ 21/2*512 /2 = 2256 /2 = 2255(gi©y) @ 2238 (ngµy) @ 2230 n¨m. (1 ngµy = 60*60*24 = 86400 gi©y @ 217 gi©y. 1 n¨m = 30*12*86400 gi©y = 31104000 gi©y @ 225 gi©y.) NÕu kÎ gi¶ m¹o muèn t×m p, q theo c¸ch nµy th× ®©y lµ ®iÒu kh«ng t­ëng. Ch­¬ng II VÊn ®Ò m· ho¸ 2. 1. §Æt vÊn ®Ò Ta biÕt r»ng tin truyÒn trªn m¹ng rÊt dÔ bÞ lÊy c¾p. §Ó ®¶m b¶o viÖc truyÒn tin an toµn, ng­êi ta th­êng m· ho¸ th«ng tin tr­íc khi truyÒn ®i. ViÖc m· ho¸ cÇn theo quy t¾c nhÊt ®Þnh gäi lµ HÖ mËt m·. HiÖn nay cã hai lo¹i MËt m·: MËt m· cæ ®iÓn vµ MËt m· kho¸ c«ng khai. MËt m· cæ ®iÓn dÔ hiÓu, dÔ thùc thi nh­ng cã ®é an toµn kh«ng cao. V× giíi h¹n tÝnh to¸n chØ thùc hiÖn trong ph¹m vi b¶ng ch÷ c¸i sö dông trong v¨n b¶n cÇn m· (vÝ dô lµ Z26 nÕu dïng c¸c ch÷ c¸i tiÕng Anh, Z256 nÕu dïng b¶ng m· ASCII . . .). Víi c¸c hÖ m· cæ ®iÓn, nÕu biÕt kho¸ lËp m· hay thuËt to¸n lËp m·, ng­êi ta cã thÓ t×m ra ngay ®­îc b¶n râ. Ng­îc l¹i, c¸c hÖ mËt m· kho¸ c«ng khai cho biÕt kho¸ lËp m· K vµ hµm lËp m· ek , th× còng rÊt khã t×m ®­îc c¸ch gi¶i m·. Vµ viÖc th¸m m· lµ rÊt khã kh¨n do ®é phøc t¹p tÝnh to¸n lín. V× thÕ trong ch­¬ng nµy, ®Çu tiªn ta ®Þnh nghÜa kh¸i niÖm vÒ mËt m· sau ®ã t×m hiÓu HÖ mËt m· c«ng khai RSA v× nã thiÕt thùc cho ký ®iÖn tö. Sau ®©y lµ kh¸i niÖm hÖ mËt m·. 2. 2. Kh¸i niÖm hÖ MËt m· HÖ mËt m· ®­îc ®Þnh nghÜa lµ bé n¨m (P, C, K, E, D), trong ®ã: 1. P lµ mét tËp h÷u h¹n c¸c b¶n râ cã thÓ. 2. C lµ mét tËp h÷u h¹n c¸c b¶n m· cã thÓ. 3. K lµ mét tËp h÷u h¹n c¸c kho¸ cã thÓ. 4. E lµ tËp c¸c hµm lËp m·. 5. D lµ tËp c¸c hµm gi¶i m·. Víi mçi kÎ K, cã mét hµm lËp m· ekÎ E, ek: P®C, vµ mét hµm gi¶i m· dkÎ D, dk: C®P sao cho dk (ek (x)) = x " xÎP. §­êng ®i cña th«ng tin trong s¬ ®å m· ho¸ nh­ sau: Ng­êi göi G ® Ng­êi nhËn N ­ KÎ tÊn c«ng H Ng­êi göi G muèn göi mét v¨n b¶n cho ng­êi nhËn N, thay v× göi v¨n b¶n b×nh th­êng, G m· ho¸ v¨n b¶n ®ã råi míi göi (tÊt nhiªn ph¶i cho ng­êi nhËn biÕt kho¸ ®Ó gi¶i m·). Khi ng­êi N nhËn ®­îc b¶n m·, hä dïng kho¸ do G göi ®Ó gi¶i m· th× míi ®äc ®­îc. NÕu H lÊy c¾p b¶n tin nµy trªn m¹ng th× anh ta còng kh«ng ®äc ®­îc nÕu kh«ng cã kho¸ më. L­u ý: 1. Sau nµy khi nh¾c ®Õn c¸c ký hiÖu P, C, K, E, D, ta ngÇm ®Þnh chóng cã ý nghÜa nh­ trong ®Þnh nghÜa s¬ ®å ch÷ ký trªn. 2. §èi víi c¸c hµm m· ho¸ ek(x), hµm lËp m· dk(y), . . . th× ®ã lµ c¸c ký hiÖu chung. Cßn khi dïng chØ sè kh¸c (nh­ G, H, N) th× ta ngÇm ®Þnh lµ do ng­êi göi (G), ng­êi nhËn (N), hay kÎ tÊn c«ng (H) ®­a ra. Sau ®©y ta xÐt mét hÖ mËt m· cô thÓ.  2. 3. HÖ mËt m· RSA 2. 3. 1. §Þnh nghÜa s¬ ®å hÖ mËt m· RSA Cho n = p*q víi p, q lµ sè nguyªn tè lín. §Æt P = C = Zn Chän b nguyªn tè víi f (n), f(n) = (p-1). (q-1). Ta ®Þnh nghÜa: K = {(n, a, b): a*b º 1 (mod f (n))}. Gi¸ trÞ n vµ b lµ c«ng khai, vµ a lµ bÝ mËt Víi mçi K = (n, a, b), mçi x Î P, y Î C, ®Þnh nghÜa: Hµm m· ho¸: y = ek (x) = xb mod n Hµm gi¶i m·: dk (x) = ya mod n H×nh 1: S¬ ®å hÖ mËt m· RSA Chó ý: Theo s¬ ®å trªn, ng­êi th­êng ta chän b tr­íc sau ®ã tÝnh a = b -1. VÝ dô 1 - Chän p = 109, q = 409 khi ®ã n = p*q = 109*409 = 44581, f(n) = (p-1)*(q-1) = 108*408 = 32*27*51 = 44064. - Chän b sao cho b nguyªn tè víi f (n) tøc lµ chän b sao cho b kh«ng chia hÕt cho 2, 3 vµ 51. LÊy b = 43*929 = 39947 khi ®ã a = b-1 trong f (n) Þ a = 13475. Khi ®ã phÐp lËp m· vµ gi¶i m· ®­îc tÝnh: ek (x) = xb mod n = x39947 mod 44581 dk (x) = ya mod n = y13475 mod 44581 NÕu lÊy x = 9798, ta ®­îc y = 9229. 2. 3. 2. XÐt ®é an toµn trong hÖ mËt m· RSA Ta thÊy hÖ mËt m· RSA chØ ®­îc an toµn khi gi÷ bÝ mËt kho¸ gi¶i m· a vµ 2 thõa sè p vµ q hay gi÷ bÝ mËt f(n). Tr­êng hîp biÕt ®­îc p vµ q th× H dÔ dµng tÝnh ®­îc f(n) = (q-1)*(p-1). Khi biÕt ®­îc f(n) th× H sÏ tÝnh ®­îc a theo thuËt to¸n Euclidean më réng. Khi biÕt a th× toµn hÖ thèng sÏ bÞ ph¸ vì ngay lËp tøc. V× khi biÕt a, toµn bé kho¸ K = (n, a, b) ®Òu ®­îc biÕt vµ H ®äc ngay ®­îc b¶n râ. Ngoµi ra, H cã thÓ lËp m· trªn v¨n b¶n kh¸c ®Ó göi tiÕp ®Õn N. Mµ ta biÕt viÖc H ®äc ®­îc b¶n râ hay lËp m· trªn v¨n b¶n kh¸c lµ cùc kú nguy hiÓm. NhÊt lµ nh÷ng th«ng tin liªn quan ®Õn an ninh quèc gia, qu©n ®éi, ng©n hµng. . . Ch­¬ng III VÊn ®Ò ký ®iÖn tö 3. 1. Kh¸i niÖm ký ®iÖn tö * KÝ ®iÖn tö lµ g× ? * KÝ ®iÖn tö nh­ thÕ nµo ? - TruyÒn trªn m¹ng lµ c¸c th«ng tin sè hãa, tøc lµ d·y c¸c bÝt. - VËy ph¶i kÝ trªn tõng bit mét S¬ ®å ch÷ ký lµ mét bé n¨m (P, A, K, S, V ), trong ®ã: P lµ mét tËp h÷u h¹n c¸c v¨n b¶n cã thÓ. A lµ mét tËp h÷u h¹n c¸c ch÷ ký cã thÓ. K lµ mét tËp h÷u h¹n c¸c kho¸ cã thÓ. S lµ tËp c¸c thuËt to¸n ký. V lµ tËp c¸c thuËt to¸n kiÓm thö. Víi mçi KÎ K, cã mét thuËt to¸n ký sigK Î S, sigK: P® A, vµ mét thuËt to¸n kiÓm thö verK Î V, verK: P ´ A® {®óng, sai}, tho¶ m·n ®iÒu kiÖn sau ®©y víi mäi xÎP, yÎ A: VerK (x, y) = ®óng, nÕu y = sigK (x), sai, nÕu y # sigK (x). Ta h×nh dung mét qu¸ tr×nh ký, nhËn vµ kiÓm thö nh­ sau: Ng­êi göi G KÎ tÊn c«ng H KiÓm thö Ng­êi nhËn N - Ng­êi göi G chuyÓn v¨n b¶n trªn m¹ng cho ng­êi nhËn N. Khi nhËn ®­îc, N sÏ kiÓm thö xem ch÷ ký ®ã lµ ®óng hay sai ®Ó håi ®¸p l¹i cho G. KÎ tÊn c«ng H cã thÓ ®ét nhËp vµo qu¸ tr×nh truyÒn th«ng tin tõ G ®Õn N, lÊy c¾p v¨n b¶n, gi¶ m¹o ch÷ ký sau ®ã míi göi ®Õn N. - LiÖu H cã thÓ gi¶ m¹o ®­îc kh«ng? §iÒu nµy lµ hoµn toµn cã thÓ khi c¸c thuËt to¸n verk vµ sigk lµ c¸c thuËt to¸n ®a thøc, tËp v¨n b¶n vµ tËp ch÷ ký ®Òu lµ h÷u h¹n, th× H sÏ thö mäi tr­êng hîp cã thÓ ®Ó ®¹t ®­îc ®iÒu kiÖn kiÓm thö ®óng. - Cô thÓ lµ ®Ó chuyÓn ®i v¨n b¶n x, G ký y= sigK(x) sao cho verK(x, y) = true. Khi trém ®­îc x, H kiÓm tra víi mäi y cã thÓ trªn x cho ®Õn khi verK(x, y) = true. HiÖn nay cã nhiÒu lo¹i s¬ ®å ch÷ ký, sau ®©y em xin tr×nh bµy mét sè s¬ ®å ch÷ ký.  3. 2. S¬ ®å ch÷ ký RSA ThuËt to¸n ký ph¶i dùa vµo hÖ m· ho¸ bëi v× c¸c th«ng tin cÇn ®­îc ký ch¾c lµ c¸c th«ng tin ph¶i ®­îc gi÷ bÝ mËt hoÆc lµ ph¶i tr¸nh bÞ tÊn c«ng, do ®ã b¶n ký vµ c¶ ch÷ ký ®Òu cÇn ®­îc b¶o mËt. Trªn c¬ së mét sè hÖ mËt m·, ng­êi ta ®· x©y dùng nªn c¸c s¬ ®å ch÷ ký t­¬ng øng. S¬ ®å ch÷ ký RSA ®­îc x©y dùng dùa trªn hÖ mËt m· RSA. 3. 2. 1. S¬ ®å ch÷ ký RSA Cho n = p*q víi p, q lµ sè nguyªn tè lín. §Æt P = A = Zn K= {(n, p, q, a, b): n = p*q, p, q lµ c¸c sè nguyªn tè, a*b º 1 (mod f (n))}. Gi¸ trÞ n vµ b lµ c«ng khai, vµ c¸c gi¸ trÞ a, p, q lµ bÝ mËt. Víi mçi K = (n, p, q, a, b), x Î P ta ®Þnh nghÜa: y = sigK (x) = xa mod n, y Î A. verK (x, y) = ®óng Û x º yb (mod n). H×nh 2: S¬ ®å ch÷ ký RSA Chó ý - So s¸nh gi÷a s¬ ®å ch÷ ký RSA vµ s¬ ®å mËt m· RSA ta thÊy cã sù t­¬ng øng. ViÖc G ký vµo x t­¬ng øng víi viÖc m· ho¸ v¨n b¶n x. ThuËt to¸n kiÓm thö chÝnh lµ viÖc sö dông hµm gi¶i m· nh­ trong RSA ®Ó kiÓm tra xem sau khi gi¶i m· cã ®óng lµ v¨n b¶n tr­íc khi ký kh«ng. Khi thuËt to¸n kiÓm thö lµ c«ng khai, bÊt kú ai còng cã thÓ kiÓm thö ch÷ ký ®­îc. - Nh­ vËy viÖc ký ch¼ng qua lµ mét lÇn m· ho¸, viÖc kiÓm thö l¹i chÝnh lµ viÖc gi¶i m·. Nh­ ®· nãi ë trªn, c¶ v¨n b¶n göi ®i còng cÇn ph¶i ®­îc gi÷ bÝ mËt. Do ®ã v¨n b¶n göi ®i x cÇn ph¶i ®­îc m· ho¸ tr­íc khi göi. Nh­ng gi÷a viÖc ký vµ m· ho¸ cã mèi liªn hÖ g× kh«ng? Nªn ký tr­íc hay m· ho¸ tr­íc? 3. 2. 2. Chèng gi¶ m¹o ch÷ ký * Gi¶ sö G muèn göi v¨n b¶n x cïng b¶n ký ®Õn N, xuÊt hiÖn 2 c¸ch xö lý : a. Tr­êng hîp G ký y = sigK(x) tr­íc, sau ®ã sö dông hµm m· ho¸ eN ®Ó m· ho¸ c¶ x vµ y ®­îc z = eN (x, y) råi göi b¶n m· ®Õn N. Khi N nhËn ®­îc, ®Çu tiªn dïng hµm gi¶i m· dN ®Ó ®­îc x, y sau ®ã kiÓm tra verK(x, y) = true? b. Tr­êng hîp G m· ho¸ x tr­íc b»ng z = eN(x) sau ®ã ký: y = sigG(z) = sigG(eN(x)). TiÕp theo göi cÆp (z, y) ®Õn N. N gi¶i m· z ®­îc x vµ dïng thuËt to¸n kiÓm thö verG víi y ®Ó ®­îc x. * Gi¶ sö H lÊy c¾p ®­îc th«ng tin trªn ®­êng truyÒn tõ G ®Õn N. Trong tr­êng hîp a, H lÊy ®­îc z. Trong tr­êng hîp b, H lÊy ®­îc (z, y). - NÕu muèn tÊn c«ng v¨n b¶n x th× trong c¶ hai tr­êng hîp, H ®Òu ph¶i gi¶i m· th«ng tin lÊy ®­îc. Nh­ng nÕu muèn tÊn c«ng vµo b¶n ký (®Ó gi¶ m¹o) th× sao? - Trong tr­êng hîp a, H ph¶i gi¶i m· z th× míi cã thÓ tÊn c«ng vµo ch÷ ký. - Trong tr­êng hîp b, H sÏ thay ch÷ ký y cña G bëi y’ = sigH(eN(x)), sau ®ã göi ®Õn N. Khi nhËn ®­îc, N kiÓm thö thÊy sai sÏ göi ph¶n håi l¹i G. G cã thÓ chøng minh ch÷ ký ®ã lµ gi¶ m¹o vµ göi v¨n b¶n cïng ch÷ ký ®óng cho N nh­ng qu¸ tr×nh truyÒn tin sÏ bÞ chËm l¹i. Nh­ vËy trong tr­êng hîp nµy, H cã thÓ gi¶ m¹o ch÷ ký mµ kh«ng cÇn gi¶i m·. - V× thÕ cã lêi khuyªn lµ ta nªn ký tr­íc khi m· ho¸. 3. 3. S¬ ®å ch÷ ký ®iÖn tö ELGamal S¬ ®å ELGamal ®­îc ®Ò xuÊt n¨m 1985, phiªn b¶n söa ®æi cña s¬ ®å nµy ®­îc chÊp nhËn lµ chuÈn ch÷ ký sè bëi NIST (National Institute of Standards and Technology – ViÖn quèc gia vÒ c¸c chuÈn vµ c«ng nghÖ Mü). S¬ ®å ch÷ ký ELGamal ®­îc thiÕt kÕ ®Æc biÖt cho môc ®Ých ký. Nã cã thÓ sö dông c¶ hai hÖ mËt m· kho¸ c«ng khai vµ s¬ ®å ch÷ ký (®iÒu nµy kh¸c víi RSA). 3. 3. 1. S¬ ®å ch÷ ký ELGamal Gi¶ sö p lµ sè nguyªn tè sao cho bµi to¸n log rêi r¹c trong Zp lµ khã. Gi¶ sö a lµ phÇn tö nguyªn thñy cña . §Æt P = , A = ´ Zp-1 vµ K = {(p, a, a, b): a Î , b º a a mod p } Víi mçi K = (p, a, a, b), k’ = a bÝ mËt, k” = (p, a b) c«ng khai. Chän ngÉu nhiªn k Î Zp* vµ gi÷ bÝ mËt, lËp ch÷ ký trªn x Î P (x ¹ 0) sau: y = sigk’ (x, k) = (g, d), y ÎA Trong ®ã g Î , d Î Zp-1vµ ®­îc tÝnh nh­ sau: g = a k mod p d = (x-a*g)*k-1 mod (p -1) ThuËt to¸n kiÓm thö ®­îc ®Þnh nghÜa bëi: verk” (x, g, d) = ®óng Û b g *g d º a x mod p. H×nh 3: S¬ ®å ch÷ ký ElGamal NÕu ch÷ ký ®­îc lËp ®óng, b¶n kiÓm thö sÏ thµnh c«ng khi b g g d º a a* g * a k* d mod p º a x mod p. v× k*d +a*g º x mod (p-1). G dïng c¶ hai gi¸ trÞ bÝ mËt a vµ sè ngÉu nhiªn k ®Ó tÝnh ch÷ ký. B¶n kiÓm thö ®­îc hoµn thµnh chØ nhê vµo c¸c thuËt to¸n c«ng khai. VÝ dô 2: LÊy p = 463, a = 2, a = 211. Khi ®ã b = aa mod p = 2221 mod 463 = 249. Gi¶ sö G ký trªn v¨n b¶n x = 112, chän sè ngÉu nhiªn k = 235 (¦CLN(235, 462) = 1) vµ ®­îc 213 -1 mod 462 = 289. Khi ®ã g = a k mod p = 2235 mod 463 = 16 d = (x-a*g)*k-1 mod (p-1) = (112- 211*16)*289 mod 462 = 108 §Ó kiÓm thö ta tÝnh: b g * g d mod p = 249 16 * 16 108 mod 463 = 132 vµ a x mod p = 2112 mod 463 = 132, Hai gi¸ trÞ ®ã b»ng nhau, ch÷ ký lµ ®óng. 3. 3. 2. VÊn ®Ò gi¶ m¹o ch÷ ký - Gi¶ sö H cè g¾ng gi¶ m¹o ch÷ ký trªn x mµ kh«ng biÕt tr­íc a. Muèn vËy, anh ta ph¶i tÝnh ®­îc g vµ d. * NÕu chän tr­íc g th× ph¶i t×m d, tøc lµ ph¶i tÝnh logg axb -g. Ng­îc l¹i nÕu chän tr­íc d th× ph¶i t×m g b»ng c¸ch gi¶i ph­¬ng tr×nh: b g. g d º a x mod p víi Èn g. - Ng­êi ta ch­a biÕt cã c¸ch gi¶i nµo h÷u hiÖu nh­ng pháng ®o¸n lµ khã h¬n bµi to¸n logarit rêi r¹c. Cã thÓ cã mét vµi c¸ch tÝnh g, d ®ång thêi víi (g, d) lµ ch÷ ký? §ã lµ c©u hái ®Æt ra nh­ng ch­a cã c©u tr¶ lêi minh b¹ch. * NÕu H chän g vµ d vµ sau ®ã thö t×m x th× anh ta ph¶i ®èi ®Çu víi bµi to¸n logarit rêi r¹c loga b -g gd. V× vËy H kh«ng thÓ ký trªn mét v¨n b¶n ngÉu nhiªn b»ng c¸ch gi¶i t­¬ng tù. Nh­ng cã mét ph­¬ng thøc H cã thÓ ký trªn v¨n b¶n ngÉu nhiªn b»ng c¸ch chän x, g, d ®ång thêi. Cã hai c¸ch gi¶ m¹o ch÷ ký cïng víi v¨n b¶n ®­îc ký C¸ch 1 Chän c¶ x, g, d tho¶ m·n ®iÒu kiÖn kiÓm thö nh­ sau: LÊy c¸c sè nguyªn i, j sao cho 0 £ i, j £ p-2, (j, p-1) = 1 vµ tiÕn hµnh c¸c phÐp tÝnh: g = a i b j mod p, d = -g *j -1 mod (p -1), x = -g *i*j -1 mod (p -1), trong ®ã j -1 ®­îc tÝnh theo mod p -1 (nghÜa lµ j nguyªn tè víi p-1). Ta chøng minh (g, d) lµ ch÷ ký trªn v¨n b¶n x b»ng c¸ch kiÓm tra c¸c ®iÒu kiÖn kiÓm thö: b g g d º b g (a i*b j) -g * j-1 mod p º b g a - i*g * j-1 *b -g mod p º a x mod p VÝ dô 3 LÊy p = 463, a = 2, a = 135. Gi¶ sö H chän i = 89, j = 125 Khi ®ã j -1 mod (p-1) = 377. Sau ®ã tÝnh: b = 2a mod p = 2135 mod 463 = 272. g = a i b j mod p = 289 *272125 mod 463 = 218 d = -g *j -1 mod (p -1) = -218*377mod 462 = 50 x = -g *i*j -1 mod (p -1) = -218*89*377 mod 462 = 292 Khi ®ã (218, 50) lµ ch÷ ký ®óng ®èi víi v¨n b¶n x = 292, v×: b g * g d = 272 218 * 218 50 º 322 (mod 463) vµ a x = 2292 º 322 (mod 467) C¸ch 2 C¸ch gi¶ m¹o thø hai, gi¶ sö (g, d) lµ ch÷ ký ®óng trªn v¨n b¶n x cã tõ tr­íc th× H cã thÓ ký trªn v¨n b¶n x’ kh¸c. Gi¶ sö c¸c sè nguyªn h, i, j sao cho 0 £ h, i, j £ p-2, (h*g-j*d, p-1) = 1 vµ tiÕn hµnh c¸c phÐp tÝnh: l = g h a i b j (mod p), m = d l (h g -j d)-1 mod (p -1), x’ = l (hx+i d) (h g -j d)-1 mod (p -1) ë ®©y (h g - j d) -1 tÝnh theo mod (p -1). Cã thÓ thö l¹i r»ng: b l l m º a x’ mod p, Tøc (l, m) lµ ch÷ ký ®óng ®èi víi v¨n b¶n x’. C¶ hai c¸ch gi¶ m¹o nãi trªn ®Òu cho ch÷ ký ®óng trªn v¨n b¶n t­¬ng øng, nh­ng v¨n b¶n ®ã kh«ng ph¶i lµ v¨n b¶n ®­îc chän theo ý cña ng­êi gi¶ m¹o, c¸c v¨n b¶n ®ã ®Òu ®­îc tÝnh sau khi tÝnh ch÷ ký, v× vËy kh¶ n¨ng sö dông cho viÖc gi¶ m¹o trong thùc tÕ còng kh«ng cã ý nghÜa. 3. 3. 3. VÊn ®Ò Ph¸ khãa theo s¬ ®å ELGamal Kho¸ bÝ mËt a cã thÓ bÞ ph¸t hiÖn nÕu viÖc ký kh«ng thËn träng. VÝ dô trong c¸c tr­êng hîp: sè ngÉu nhiªn k bÞ lé, hoÆc dïng k cho hai lÇn ký kh¸c nhau. a. Tr­êng hîp sè ngÉu nhiªn k bÞ lé: Khi ®ã sè a, tøc kho¸ mËt, ®­îc tÝnh bëi: a = (x-k d) g -1 mod (p-1). Khi biÕt a, hÖ thèng bÞ ph¸ vì vµ H cã thÓ gi¶ m¹o ch÷ ký ngay lËp tøc. b. Tr­êng hîp dïng k cho hai lÇn ký kh¸c nhau: Khi ®ã, H dÔ dµng tÝnh a. Gi¶ sö (g, d1) lµ ch÷ ký trªn v¨n b¶n x1, (g, d2) lµ ch÷ ký víi v¨n b¶n x2, ta cã: Do ®ã ta cã §Æt g = a k ta cã t­¬ng ®­¬ng víi x1-x2 º k (d1 - d2) mod (p-1) (1) §Æt d = (d1 - d2, p -1). Khi ®ã d| p-1, d| d1 - d2, Þ d| x1-x2. Khi ®ã ®ång d­ thøc (1) trë thµnh: x'º k* d' (mod p') V× (d', p') = 1 nªn tÝnh e = (d')-1 mod p' vµ tÝnh k: k = x'*e mod p' Þ k = x'*e +i*p' mod (p-1), víi i lµ gi¸ trÞ nµo ®ã, 0£ i £ d-1. Thö víi gi¸ trÞ ®ã, ta sÏ t×m ®­îc k (®iÒu kiÖn thö ®Ó x¸c ®Þnh k lµ g = ak mod p). Tõ k, sÏ tÝnh ®­îc a. 3. 4. ChuÈn ch÷ ký sè DSS (Digital Signature Standard) ChuÈn ch÷ ký sè (DSS) ®­îc ®Ò xuÊt tõ n¨m 1991 lµ b¶n söa cña s¬ ®å ch÷ ký ElGamal vµ ®­îc chÊp nhËn lµ chuÈn vµo n¨m 1994 ®Ó dïng trong mét sè lÜnh vùc giao dÞch ë Mü. NhiÒu v¨n b¶n ®­îc m· ho¸ vµ gi¶i m· 1 lÇn. C¸c hÖ m· ho¸ ®· biÕt chØ ®­îc b¶o mËt khi v¨n b¶n ®ang ®­îc m· ho¸. Ng­îc l¹i, 1 b¶n ký l¹i liªn quan ®Õn ph¸p luËt vµ ph¶i ®­îc kiÓm thö sau nhiÒu n¨m ký. Do ®ã, sè nguyªn tè p ph¶i ®ñ lín ch¼ng h¹n dµi 512 bit nh­ng nhiÒu ng­êi ®Ò nghÞ nã ph¶i dµi 1024 bit. Tuy nhiªn, ®é dµi ch÷ ký theo s¬ ®å ELGamal lµ gÊp ®«i sè bit cña p; do ®ã nÕu p dµi 512 bit th× ®é dµi ch÷ ký ®· lµ 1024 bit. Trong mét sè øng dông cã dïng c¸c thÎ th«ng minh (Smart card) l¹i mong muèn cã ch÷ ký ng¾n, nªn gi¶i ph¸p söa ®æi lµ mét mÆt dïng p víi ®é dµi cËn tõ 512 bit ®Õn 1024 bit (lÊy mét béi cña 64), mÆt kh¸c trong ch÷ ký (g, d), c¸c sè g, d cã ®é dµi biÓu diÔn ng¾n, ch¼ng h¹n 160 bit. Khi ®ã ®é dµi ch÷ ký lµ 320 bit. §iÒu nµy ®­îc thùc hiÖn b»ng c¸ch dïng mét nhãm con xyclic cña (ta gäi lµ ) thay cho chÝnh b¶n th©n , do ®ã mäi tÝnh to¸n ®­îc thùc hiÖn trong nh­ng c¸c d÷ liÖu vµ thµnh phÇn ch÷ ký l¹i thuéc . Thay ®æi c«ng thøc tÝnh d trong s¬ ®å ch÷ ký ElGamal thµnh d = (x+a*g) k-1 mod (p -1) §iÒu kiÖn kiÓm thö nh­ sau: a xb g º gd (mod p) (1) NÕu (x+a *g, p-1) = 1 th× d -1 mod p tån t¹i. Khi ®ã (1) ®­îc söa thµnh: Ta ®­îc s¬ ®å DSS m« t¶ nh­ sau: Gi¶ sö p lµ sè nguyªn tè 512 bit sao cho bµi to¸n log rêi r¹c trong Zp lµ khã. q lµ ­íc nguyªn tè cña p-1, q cã 160 bit. Gi¶ sö a Î lµ mét c¨n bËc q cña 1 mod p. §Æt P = , A = ´ vµ K = {(p, q, a, a, b): a Î , b º a a mod p } - Víi mçi K = (p, q, a, a, b), k’ = a bÝ mËt, k” = (p, q, a, b) c«ng khai. - Cho x Î , chän mét sè ngÉu nhiªn k (víi 0£ n £ q-1), råi lËp ch÷ ký: sigk’ (x, k) = (g, d), Trong ®ã g = (ak mod p) mod q, d = ((x + a*g)*k -1 mod q. - ThuËt to¸n kiÓm thö ®­îc ®Þnh nghÜa bëi: verk” (x; g, d) = ®óng Û Víi e1 = x* d -1 mod q, e2 = g * d -1 mod q. H×nh 4: S¬ ®å ch÷ ký DSS Chó ý r»ng ta ph¶i cã d # 0 (mod q) ®Ó ®­îc d -1 mod q trong ®iÒu kiÖn kiÓm thö (t­¬ng ®­¬ng (d, p-1) = 1), v× vËy nÕu chän k mµ kh«ng ®­îc ®iÒu kiÖn trªn, th× ta ph¶i chän k kh¸c ®Ó cã d # 0 mod q. Tuy nhiªn kh¶ n¨ng d º 0 mod q lµ 2-160 nªn ®iÒu ®ã hÇu nh­ kh«ng bao giê x¶y ra. Mét ®iÒu n÷a lµ thay v× tÝnh p tr­íc råi míi tÝnh q, ta sÏ tÝnh q tr­íc råi t×m p. VÝ dô 4 LÊy q = 239, p = 32*q+1 = 7649, 3 lµ phÇn tö nguyªn thuû trong Z7649, a = 332 mod 7649 = 7098, a = 85. Khi ®ã b = aa mod p = 709885 mod 7649 = 5387. Gi¶ sö G muèn ký trªn v¨n b¶n x = 1246 vµ chän sè ngÉu nhiªn k = 58. Ta cã: k -1 mod q = 58-1 mod 239 = 136. g = (a k mod p) mod q = (709858 mod 7649) mod 239 = 593 mod 239 = 115 d = (x+ a*g)*k-1 mod q = (1246+85*115)* 136 -1 mod 239 = 87. Khi ®ã (115, 87) lµ ch÷ ký ®óng ®èi víi v¨n b¶n x = 1246, v×: d -1 = 87 -1 mod 239 = 11 e1 = x* d-1 mod q = 1246*11 mod 239 = 83 e2 = g *d-1 mod q = 115*11 mod 239 = 70 XÐt ®iÒu kiÖn kiÓm thö : Û (709883 *538770 mod 7649) mod 239 = 593 mod 239 = 115 = g. V× vËy ch÷ ký lµ ®óng. Khi DSS ®­îc ®­a ra n¨m 1991, cã mét vµi b×nh phÈm. §é dµi cè ®Þnh cña p lµ 512 bit. NhiÒu ng­êi muèn p cã thÓ thay ®æi lín h¬n nÕu muèn. V× thÕ NIST söa ®æi lµ p cã ®é dµi thay ®æi lµ c¸c béi cña 64 cËn tõ 512 ®Õn 1024 bit. NÕu RSA sö dông sö ®å ch÷ ký vµ thµnh phÇn kiÓm thö ch÷ ký lµ rÊt nhá th× viÖc kiÓm thö ®­îc thùc hiÖn nhanh h¬n viÖc ký, th× trong DSS, thuËt to¸n ký nhanh h¬n lµ kiÓm thö. §iÒu nµy dÉn ®Õn hai vÊn ®Ò: Mét v¨n b¶n chØ ®­îc ký mét lÇn nh­ng nã l¹i ®­îc kiÓm thö nhiÒu lÇn nªn ng­êi ta muèn thuËt to¸n kiÓm thö nhanh h¬n. M¸y tÝnh ký vµ kiÓm thö nh­ thÕ nµo? NhiÒu øng dông sö dông thÎ th«ng minh víi kh¶ n¨ng cã h¹n, kÕt nèi víi 1 m¸y tÝnh m¹nh h¬n, v× vËy nªn x©y dùng s¬ ®å ch÷ ký Ýt liªn quan ®Õn thÎ. Nh­ng 1 t×nh huèng ®Æt ra lµ mét thÎ th«ng minh cã thÓ sinh ra ch÷ ký vµ còng cã thÓ kiÓm thö ch÷ ký do vËy rÊt khã kÕt luËn. NIST tr¶ lêi r»ng thêi gian kiÓm thö vµ sinh ch÷ ký, c¸i nµo nhanh h¬n kh«ng quan träng miÔn lµ ®ñ nhanh. 3. 5. S¬ ®å ch÷ ký 1 lÇn PhÇn nµy ®­a ra kh¸i niÖm ®¬n gi¶n trong x©y dùng mét s¬ ®å ch÷ ký 1 lÇn tõ bÊt kú hµm 1 phÝa. ThuËt ng÷ one- time nghÜa lµ víi mét kho¸ ®­a ra, chØ ®­îc dïng mét lÇn ®Ó ký trªn mét v¨n b¶n (tÊt nhiªn ch÷ ký cã thÓ ®­îc kiÓm thö víi sè lÇn tuú ý) mang tªn lµ s¬ ®å ch÷ ký Lamport. M« t¶ nh­ sau: Gi¶ sö k lµ mét sè nguyªn d­¬ng; P = {0, 1}k f: Y ®Z lµ hµm mét phÝa víi Y lµ tËp tïy chän (gi¶ sö Y = Zn , n Î N. A = Yk. K = {(y’s,z’s): y’s = {yi, j: 1£ i £ k, j = 0,1}, z’s = {zi, j: 1£ i £ k, j = 0, 1}, yi,j Î Y chän ngÉu nhiªn, zi, j = f(yi, j, zi, j) "1£ i £ k, j = 0 hoÆc 1} trong ®ã thµnh phÇn k y's b¶o mËt vµ z's c«ng khai. Víi mçi K ÎK,K = (yi, j, zi, j: 1£ i £ k, j = 0, 1), x ÎP ta ®Þnh nghÜa: Û " 1£ i £ k H×nh 5: s¬ ®å ch÷ ký mét lÇn Mçi v¨n b¶n ®­îc ký cã biÓu diÔn d­íi d¹ng nhÞ ph©n gåm k bit. Mçi bit ®­îc ký riªng biÖt nhau. Ta chän ngÉu nhiªn 2*k gi¸ trÞ yi, j Î Y, sè ngÉu nhiªn yi, j chÝnh lµ ch÷ ký cña bit thø i øng víi gi¸ trÞ j (nÕu bit thø i cã gi¸ trÞ 0 th× ch÷ ký cã gi¸ trÞ yi, 0 ng­îc l¹i cã gi¸ trÞ yi, 1). Nh­ vËy viÖc ký chÝnh lµ viÖc ¸nh x¹ mét gi¸ trÞ cña mçi bit trong v¨n b¶n gèc t­¬ng øng víi mét gi¸ trÞ ngÉu nhiªn Î Y. zi, j lµ ¶nh cña yi, j d­íi t¸c ®éng cña hµm f. B¶n kiÓm thö lµ viÖc kiÓm tra c¸c phÇn tö trong ch÷ ký cã ph¶i lµ ¶nh gèc cña zi, j theo hµm f kh«ng. VÝ dô 5: Sö dông hµm luü thõa f(x) = a x mod p víi a lµ phÇn tö nguyªn thuû mod p. LÊy p = 7649 lµ sè nguyªn tè, 3 lµ phÇn tö nguyªn thuû trong Z7649. Gi¶ sö G muèn ký trªn v¨n b¶n cã ®é dµi 3 bit, anh chän (2*3 = ) 6 sè ngÉu nhiªn bÝ mËt. Khi ®ã: y1, 0 = 4728 y1, 1 = 3591 y2, 0 = 209 y2, 1 = 5571 y3, 0 = 3721 y3, 1 = 4963 G tÝnh c¸c y’s theo hµm f: z1, 0 = 1800 z1, 1 = 5991 z2, 0 = 67 z2, 1 = 6815 z3, 0 = 3657 z3, 1 = 6773 Gi¶ sö G muèn ký trªn v¨n b¶n x = (1, 0, 1) Khi ®ã ch÷ ký lµ: (y1, 1, y2, 0, y3, 1) = (5991, 67, 6773) §Ó kiÓm thö N tÝnh: 33591 mod 7649 = 5991 3209 mod 7649 = 67 34963 mod 7649 = 6773 V× vËy ch÷ ký lµ ®óng. H kh«ng thÓ gi¶ m¹o ch÷ ký v× anh ta kh«ng thÓ tÝnh ng­îc hµm mét phÝa f ®Ó ®­îc y’s b¶o mËt khi sö dông ch÷ ký trªn 1 v¨n b¶n. Nh­ng nÕu ký trªn 2 v¨n b¶n kh¸c nhau th× H dÔ dµng lËp ch÷ ký trªn c¸c v¨n b¶n kh¸c dùa trªn 2 v¨n b¶n trªn. Cô thÓ, nÕu G dïng kho¸ y’s trªn hai v¨n b¶n x vµ x’. V× hai v¨n b¶n nµy cã gi¸ trÞ kh¸c nhau nªn ta gi¶ sö sè bit cã gi¸ trÞ kh¸c nhau lµ m bit. Khi ®ã cã thÓ lËp ch÷ ký trªn 2m –2 v¨n b¶n kh¸c nhau vµ kh¸c hai v¨n b¶n trªn. Chøng minh: Gi¶ sö m bit kh¸c nhau lÇn l­ît lµ bi (1£ i £ m ). Ta muèn lËp ch÷ ký trªn v¨n b¶n x” kh¸c th×: Trªn bit thø nhÊt cña v¨n b¶n x”, cã hai c¸ch chän. Trªn bit thø hai cña v¨n b¶n x”, cã hai c¸ch chän. . . . m. Trªn bit thø m cña v¨n b¶n x”, cã hai c¸ch chän. Theo ®¹i sè tæ hîp th× ®©y chÝnh lµ chØnh hîp lÆp chËp m cña 2 phÇn tö. Do ®ã cã tÊt c¶ 2m c¸ch chän. TÊt nhiªn gåm c¶ hai c¸ch chän trïng víi gi¸ trÞ cña hai v¨n b¶n ®Çu. Nªn ta cã tÊt c¶ 2m –2 c¸ch chän v¨n b¶n x” ®Ó ký. VÝ dô 6: Gi¶ sö hai v¨n b¶n (0, 1, 1) vµ (1, 0, 1) sö dông chung 1 s¬ ®å. Ch÷ ký cña (0, 1, 1) lµ bé ba (y1, 0, y2, 1, y3, 1) vµ cña (1, 0, 1) lµ (y1, 1, y2, 0, y3, 1). Cho hai ch÷ ký, H cã thÓ x¸c ®Þnh ch÷ ký ®èi víi v¨n b¶n (1, 1, 1) (lµ (y1, 1, y2, 1, y3, 1)) vµ (0, 0, 1) (lµ (y1, 0, y2, 0, y3, 1)). Dï s¬ ®å nµy kh¸ tèt v× ch÷ ký lµ trªn c¸c bit vµ kh«ng theo mét luËt nµo c¶ nªn H khã cã thÓ gi¶ m¹o ®­îc, tuy nhiªn nã kh«ng ®­îc dïng nhiÒu trong thùc tÕ do ®é dµi ch÷ ký. NÕu lÊy sè p cã 512 bit th× mçi bit trong b¶n gèc t­¬ng øng víi 512 bit trong b¶n ký. Nh­ vËy ®é dµi ch÷ ký ph¶i lín h¬n b¶n gèc lµ 512 lÇn. §èi víi s¬ ®å nµy, em ®­a ý t­ëng lµ dïng sè p víi gi¸ trÞ nhá, cã thÓ lµ 8 hoÆc 16 bit, cã thÓ Ýt h¬n, nhiÒu h¬n tuú theo møc ®é cÇn b¶o mËt. Do viÖc ký lµ trªn tõng bit vµ kh«ng theo mét quy luËt nµo c¶ nªn dï p cã gi¸ trÞ nhá, H còng khã mµ gi¶ m¹o ®­îc. 3. 6. Ch÷ ký kh«ng phñ ®Þnh ®­îc 6. 1. §Æt vÊn ®Ò Trong phÇn tr­íc ta ®· tr×nh bµy mét sè s¬ ®å ch÷ ký ®iÖn tö. Trong c¸c s¬ ®å ®ã, viÖc kiÓm thö tÝnh ®óng ®¾n cña ch÷ ký lµ do ng­êi nhËn thùc hiÖn. Nh»m tr¸nh viÖc nh©n b¶n ch÷ ký ®Ó sö dông nhiÒu lÇn, tèt nhÊt lµ ng­êi göi tham gia trùc tiÕp vµo viÖc kiÓm thö ch÷ ký. §iÒu ®ã ®­îc thùc hiÖn b»ng mét giao thøc kiÓm thö, d­íi d¹ng mét giao thøc mêi hái vµ tr¶ lêi. Gi¶ sö v¨n b¶n cïng ch÷ ký lµ tõ G göi ®Õn N. Khi sù céng t¸c cña G lµ mét ®ßi hái cïng kiÓm thö ch÷ ký th× mét vÊn ®Ò kh¸c n¶y ra lµ lµm sao ®Ó ng¨n c¶n G chèi bá mét ch÷ ký mµ anh ta ®· ký b»ng c¸ch tuyªn bè r»ng ch÷ ký ®ã lµ gi¶ m¹o? §Ó thùc hiÖn ®­îc viÖc ®ã, cÇn cã thªm mét giao thøc chèi bá, b»ng giao thøc ®ã, G cã thÓ chøng minh mét ch÷ ký lµ gi¶ m¹o. NÕu G tõ chèi tham gia vµo giao thøc ®ã th× cã thÓ xem r»ng G kh«ng chøng minh ®­îc ch÷ ký lµ gi¶ m¹o. Nh­ vËy mét s¬ ®å ch÷ ký kh«ng phñ ®Þnh ®­îc gåm 3 phÇn: mét thuËt to¸n ký, mét giao thøc kiÓm thö vµ mét giao thøc chèi bá. 6. 2. S¬ ®å ch÷ ký kh«ng phñ ®Þnh ®­îc Chaum - van Antverpen Gi¶ sö p lµ sè nguyªn tè sao cho bµi to¸n log rêi r¹c trong Zp lµ khã, p = 2*q+1, vµ q còng lµ sè nguyªn tè, a Î lµ mét phÇn tö cÊp q. Gäi P lµ nhãm nh©n con cña theo q (P gåm c¸c thÆng d­ bËc hai theo mod p). §Æt P = A = P, K = {(p, a, a, b): a Î Zq*, b º a a mod p } ThuËt to¸n ký : gi¶ sö G cã kho¸ k = (p, a, a, b), víi kho¸ mËt k’ = a, kho¸ c«ng khai k” = (p, a, b). G ký trªn v¨n b¶n x theo: y = sigk’ (x) = xa mod p Giao thøc kiÓm thö :Víi x, y Î P, ng­êi nhËn N cïng víi G thùc hiÖn giao thøc kiÓm thö sau ®©y: 1. N Chän ngÉu nhiªn e1, e2 Î Zq*, 2. N tÝnh vµ göi c cho G. 3. G TÝnh vµ göi d cho N. 4. N chÊp nhËn y lµ ch÷ ký ®óng nÕu . H×nh 6: S¬ ®å ch÷ ký kh«ng phñ ®Þnh ®­îc Chaum - van Antverpen Giao thøc chèi bá 1. N Chän ngÉu nhiªn e1, e2 Î Zp*, 2. N tÝnh vµ göi c cho G, 3. G tÝnh vµ göi d cho N, 4. N thö ®iÒu kiÖn d # xe1 ae2 (mod p) 5. N chän ngÉu nhiªn f1, f2 Î Zp*, 6. N tÝnh vµ göi C cho G, 7. G tÝnh vµ göi D cho N, 8. N thö ®iÒu kiÖn D # 9. N kÕt luËn y lµ ch÷ ký gi¶ m¹o nÕu: H×nh 7: Giao thøc chèi bá 3. 6. 3. C¸c tÝnh chÊt cña s¬ ®å Chaum - van Antverpen §Þnh lý 1: NÕu y º xa mod p, tøc y lµ ch÷ ký ®óng ®èi víi x, th× theo giao thøc kiÓm thö, ch¾c ch¾n N sÏ chÊp nhËn y lµ ch÷ ký ®óng ®èi víi x. Chøng minh : Gi¶ sö y º xa mod p. Khi ®ã ya-1 º x mod p. (chó ý r»ng tÊt c¶ c¸c sè mò ®­îc tÝnh theo mod q). Ta còng cã b a-1º mod q. Khi ®ã y a-1 º x mod p. Do ®ã V× vËy theo giao thøc kiÓm thö, N chÊp nhËn y lµ ch÷ ký ®óng ®èi víi x. §èi víi giao thøc chèi bá ta cã ®Þnh lý sau ®©y: §Þnh lý 2 : NÕu y # xa mod p, vµ c¶ G vµ N tu©n theo giao thøc chèi bá th× N sÏ chøng minh ch÷ ký ®ã lµ gi¶ m¹o . Tøc ®ång d­ thøc lµ ®óng Chøng minh : V× c vµ d ®­îc tÝnh theo c¸c b­íc 2, 3 cña giao thøc, vµ v× b º a a mod p nªn bÊt ®ång d­ thøc ë b­íc 4 vµ b­íc 8 trong giao thøc chèi bá lµ ®óng. TiÕp theo tÝnh: T­¬ng tù, v× C vµ D ®­îc tÝnh theo c¸c b­íc 6 vµ 7 cña giao thøc, nªn ta cã: Tõ ®ã suy ra ®ång d­ thøc cÇn t×m Chó ý r»ng trong giao thøc chèi bá, phÇn sö dông e1, e2 lµ ®Ó t¹o ra x0 víi y # x0a mod p, cßn phÇn sö dông f1, f2 lµ ®Ó thùc hiÖn giao thøc kiÓm thö y cã lµ ch÷ ký ®èi víi x hay kh«ng. VÝ dô 7: Ta lÊy p = 463, a = 4 lµ phÇn tö sinh cña nhãm P cÊp q = 233, lÊy a = 121. Khi ®ã ta cã b = a a mod 467 = 4121 mod 467 = 422 G chän khãa (p, a, a, b) = (467, 4, 121, ), trong ®ã a = 121 lµ bÝ mËt. Ch÷ ký cña G trªn v¨n b¶n x = 229 lµ: y = 229121 mod 467 = 9 Gi¶ sö N muèn dïng giao thøc kiÓm thö ®Ó biÕt y cã ®óng lµ ch÷ ký cña B trªn v¨n b¶n x hay kh«ng. N chän ngÉu nhiªn e1 = 48, e2 = 213, vµ tÝnh ®­îc c = 116, B sÏ tr¶ lêi l¹i b»ng d = 235. N thö ®iÒu kiÖn Tøc : 22948*4213 º 235 mod 467. §ång d­ thøc ®ã ®óng. N chÊp nhËn 9 ®óng lµ ch÷ ký cña G trªn 229. Gi¶ sö G göi v¨n b¶n x = 226 víi ch÷ ký y = 183. Giao thøc chèi bá ®­îc thùc hiÖn nh­ sau: N chän ngÉu nhiªn e1 = 47, e2 = 137, vµ tÝnh ®­îc c = 306; G sÏ tr¶ lêi l¹i b»ng d = 184. G thö ®iÒu kiÖn Tøc : 22647*4137 º 145 mod 467, V× 184 ¹ 145, N l¹i tiÕp tôc tÝnh b­íc 5 cña giao thøc. N chän ngÉu nhiªn f1 = 225, f2 = 19 vµ tÝnh ®­îc C = 348, G tr¶ lêi r»ng D = 426. N l¹i tÝnh 226225*419 º 295 mod 467 V× 295 ¹ 426, N thùc hiÖn b­íc 9 b»ng c¸ch tÝnh : (d* a -e2)f1 º (184 * 4 -137)225 º 79 mod 467 (D* a -f2)e1 º (426 * 4 -19)47 º 79 mod 467 Hai gi¸ trÞ ®ã b»ng nhau. KÕt luËn ch÷ ký lµ kh«ng ®óng. 3. 7. S¬ ®å ch÷ ký Fail - Stop S¬ ®å ch÷ ký Fail-Stop ng¨n chÆn viÖc gi¶ m¹o kh¸ h÷u hiÖu. NÕu H gi¶ m¹o ch÷ ký cña G th× G sÏ chøng minh ®­îc ngay ch÷ ký ®ã lµ gi¶ m¹o. S¬ ®å nµy ®­îc x©y dùng n¨m 1992 bëi van Heyst vµ Pedersen. §©y lµ ch÷ ký 1 lÇn (tøc mét kho¸ cho tr­íc chØ ký 1 lÇn trªn 1 v¨n b¶n). HÖ gåm thuËt to¸n ký, thuËt to¸n kiÓm thö vµ chøng minh tÝnh gi¶ m¹o. Gi¶ sö p lµ sè nguyªn tè sao cho bµi to¸n log rêi r¹c trong Zp lµ khã, p = 2*q+1, vµ q còng lµ sè nguyªn tè, a Î Zp* lµ mét phÇn tö cÊp q. 1 £ a0 £ q-1 vµ . C¸c gi¸ trÞ p, q, a, b lµ c«ng khai, a0 lµ b¶o mËt. §Æt P = Zq vµ A = Zq ´ Zq Kho¸ cã d¹ng K = (g1, g2, a1, a2, b1, b2) Víi a1, a2, b1, b2 Î Zq g1 = aa1*ba2 mod p g2 = ab1*bb2 mod p Víi x Î Zq, ta ®Þnh nghÜa: Sigk(x) = (y1, y2) Víi y1 = a1 + x*b1 mod q y2 = a2 +x*b2 mod q. §Ó kiÓm thö ta tÝnh verk (x, y) = true Û H×nh 8: ThuËt to¸n ký vµ kiÓm thö trong s¬ ®å ch÷ ký Fail - Stop §Ó ch÷ ký cña G tho¶ m·n ®iÒu kiÖn kiÓm thö, ta trë l¹i vÊn ®Ò b¶o mËt vµ c¸ch lµm viÖc cña s¬ ®å. Ta ®Þnh nghÜa 2 kho¸ (g1, g2, a1, a2, b1, b2) vµ (g1’, g2’, a1’, a2’, b1’, b2’) lµ b»ng nhau khi g1 = g1’ vµ g2 = g2’. Bæ ®Ò: Gi¶ sö 2 kho¸ k vµ k' b»ng nhau vµ verk (x, y) = true khi ®ã verk’(x, y) = true. Gi¶ sö k = (g1, g2, a1, a2, b1, b2) vµ k’ = (g1’, g2’, a1’, a2’, b1’, b2’) víi Gi¶ sö v¨n b¶n x ®­îc ký b»ng c¸ch sö dông kho¸ k cho ta y = (y1, y2) víi y1 = a1 + x*b1 mod q y2 = a2 +x*b2 mod q. Sau ®ã ta kiÓm tra y b»ng c¸ch sö dông kho¸ k’: Do ®ã y ®­îc kiÓm thö b»ng c¸ch sö dông kho¸ k’. Bæ ®Ò: Gi¶ sö k lµ kho¸, y = sigk(x). Khi ®ã cã ®óng q kho¸ k' = k tho¶ m·n y = sigk'(x). Chøng minh: gi¶ sö g1, g2 trong k lµ c«ng khai. Ta ph¶i x©y dùng bé 4 (a1’, a2’, b1’, b2’) tho¶ m·n: y1 = a1 + x*b1 (mod q) y2 = a2 + x*b2 (mod q). NÕu a lµ phÇn tö sinh cña P, khi ®ã tån t¹i duy nhÊt cÆp c1, c2, a0 sao cho: §©y lµ ®iÒu kiÖn cÇn vµ ®ñ ®Ó tho¶ m·n hÖ ph­¬ng tr×nh ®ång d­ c1 º a1 + a0 *a2 (mod q) c2 º b1 + a0 *b2 (mod q) y1 º a1 + x *b1 (mod q) y2 º a1 + x *b2 (mod q) Ta viÕt d­íi d¹ng ma trËn nh­ sau: CÊp cña ma trËn hÖ sè lµ 3 (cÊp cña ma trËn lµ sè hµng ®éc lËp tuyÕn tÝnh mµ nã cã hay lµ cÊp cña ®Þnh thøc con lín nhÊt cã gi¸ trÞ kh¸c 0). Cã thÓ ®­a ma trËn hÖ sè vÒ d¹ng tam gi¸c råi tÝnh ®ång thêi t×m ma trËn cÊp 3 cã ®Þnh thøc ¹ 0. HoÆc tÝnh: r1 +x*r2 -r3 -a0 *r4 = (0, 0, 0, 0). Víi ri lµ hµng thø i cña ma trËn. Cã Ýt nhÊt 1 c¸ch gi¶i lµ sö dông kho¸ k. Khi cÊp cña ma trËn lµ 3, sè chiÒu trong kh«ng gian lêi gi¶i lµ 4-3 = 1 vµ cã ®óng q lêi gi¶i. T­¬ng tù ta cã hÖ qu¶ 6, chóng t«i bá qua chøng minh Bæ ®Ò : Gi¶ sö k lµ kho¸, y = sigk(x) vµ verk (x’, y’) = true. Víi x’ ¹ x. vµ cã nhiÒu nhÊt 1 kho¸ k sao cho y = sigk’(x) vµ y’ = sigk’(x’). Ph¶i hiÓu r»ng 2 hÖ qu¶ trªn ®Òu nãi vÒ tÝnh b¶o mËt cña s¬ ®å. Cho y lµ ch÷ ký ®óng ®èi víi v¨n b¶n x, th× cã thÓ cã q kho¸ ký trªn x ®Ó ®­îc y. Nh­ng víi mäi x’ ¹ x, c¸c kho¸ q nµy t¹o ra q ch÷ ký kh¸c trªn v¨n b¶n x’. Ch­¬ng VI Thö nghiÖm ký ®iÖn tö b»ng ch­¬ng tr×nh 4. 1. Ch­¬ng tr×nh m· ho¸ RSA Ch­¬ng tr×nh cã menu chÝnh nh­ sau: Vµo b¶n râ Xem b¶n râ Xem b¶n sè ho¸ Xem b¶n m· Gi¶i m· v¨n b¶n VÒ b¶n râ Tho¸t Qu¸ tr×nh m· ho¸ nh­ sau: B¶n râ ® chuyÓn sè ho¸ ® m· ho¸ ® gi¶i m·. C¸c v¨n b¶n sÏ lÇn l­ît ®­îc sinh ra nh­ sau: “Banro” ® “sohoa” ®”vbma” ® “vbgiai” ® “vesohoa” ® “vebanro” S¬ ®å thùc hiÖn theo c¸c b­íc: 1. §Çu tiªn G chuyÓn "banro" (lµ v¨n b¶n cÇn ký) thµnh b¶n "sohoa" chÝnh lµ viÕt l¹i v¨n b¶n theo quy ­íc l¹i b¶ng ký tù. 2. Dïng hµm lËp m· ®Ó m· ho¸ trªn v¨n b¶n "sohoa" ®­îc b¶n "vbma". 3. G göi "vbma" cïng kho¸ cho N. 4. N dïng hµm gi¶i m· víi kho¸ ®· biÕt ®Ó gi¶i m· "vbma" ®­îc "vesohoa", v¨n b¶n nµy trïng víi v¨n b¶n "sohoa". 5. Cuèi cïng dïng ng­îc l¹i quy ­íc b¶ng ký tù ®Ó ®­îc "banro" ban ®Çu. §Çu vµo cña s¬ ®å lµ mét v¨n b¶n. Trong v¨n b¶n sö dông bé ch÷ c¸i tiÕng Anh gåm 52 ký tù hoa (tõ A ®Õn Z) vµ th­êng (tõ a ®Õn z), 9 ch÷ sè (tõ 0 ®Õn 9), c¸c dÊu c¸ch (‘ ’), dÊu xuèng dßng, mét sè dÊu c©u(, . : ? !), tÊt c¶ lµ 70 ký tù. Ta gäi ®©y lµ qu¸ tr×nh chuyÓn sè ho¸. Thùc ra ®©y còng chÝnh lµ mét ph­¬ng ph¸p m· ho¸ cæ ®iÓn. Quy ­íc: ký tù m· chuyÓn ký tù m· chuyÓn ký tù m· chuyÓn A 00 A 26 0 52 B 01 B 27 1 53 .. . .. . .. . Z 25 Z 51 9 61 ‘ ’ 62 ‘\n’ 63 , 64 . 65 ? 66 : 67 ! 68 TiÕp theo, G m· ho¸ trªn v¨n b¶n võa t¹o ra. V¨n b¶n cã thÓ dµi ng¾n tuú ý do ®ã G sÏ “chia” v¨n b¶n ra ®Ó m· ho¸. Trong vÝ dô G m· ho¸ trªn tõng cÆp 2 ký tù. Sö dông thuËt to¸n m· ho¸ RSA nh­ ë trªn. Chän c¸c sè nguyªn tè p vµ q b»ng c¸ch sö dông hµm ramdom() vµ sau ®ã sö dông thuËt to¸n Solovay – Strassen ®Ó thö tÝnh nguyªn tè. Ch­¬ng tr×nh ®­îc viÕt nh­ sau: // Hµm tr¶ l¹i 1 nÕu n lµ sè nguyªn tè // Tr¶ l¹i 0 trong tr­êng hîp ng­îc l¹i. int isprime(unsigned long n){ unsigned long ret1, ret2, a; ramdomize(); a = ramdom(n); ret1 = legendre(a, n); ret2 = xpmodn(a, (n-1)/2, n); if(ret1 = = ret2) return 1; return 0; } Trong ®ã c¸c hµm legendre vµ xpmodn ®­îc khai b¸o vµ sö dông nh­ sau: Hµm legendre: Khai b¸o: unsigned long legendre(unsigned long a, unsigned long b): Sö dông: TÝnh legendre cña . Hµm xpmodn: Khai b¸o: unsigned long xpmodn(unsigned long x,unsigned long p,unsigned long n); Sö dông: Lµ hµm tr¶ l¹i gi¸ trÞ xp mod n. Nh­ vËy p vµ q ®­îc chän "ngÉu nhiªn". Thùc ra lµ gi¶ ngÉu nhiªn (do tÝnh chÊt cña hµm random()). Ch¼ng h¹n chän p = 83, q = 89 Þ f(n) = 11*41*8 = 7216, n = 7387. Chän b sao cho ¦CLN(b, f(n) = 1) Þ ta chän b kh«ng chia hÕt cho 11, 41 vµ 2 Chän b = 9*17 = 153 Þ a = b-1 = 4905. Hµm nghÞch ®¶o ®­îc tÝnh nh­ sau: unsigned long nghichdao(unsigned long a, unsigned long n) { unsigned long i; for(i = 2;i<sqrt(n); i++) if(ptdongdu(i, n) = = 1) return 1; return 0; } Hµm nµy tr¶ l¹i b Î tho¶ m·n a*b º 1 (mod n) nÕu tån t¹i, tr­êng hîp ng­îc l¹i tr¶ l¹i 0. VÝ dô v¨n b¶n cÇn göi cã néi dung: "HOM NAY NGAY 19 THANG 5 toi chuan bi bao cao khoa hoc. " §Çu tiªn G t¹o b¶n sè ho¸ nh­ sau (dùa vµo b¶ng quy ­íc trªn): "071412621300246213060024625361621907001306625763 45403462283346263962273462272640622826402662334028656362" NÕu G m· ho¸ tõng cÆp 2 ký tù mét, anh chia x1 = 0714, x2 = 1262, x3 = 1300, .. . , x16 = 6362 Sau ®ã G m· yi = xib mod n = xi153 mod 7387. §­îc "banma" nh­ sau: "511825311718719621871341633316746348278903722051 2315090033563515525808332533710720027107020230684995316873664345" Sau ®ã G göi ®Õn N. Khi nhËn ®­îc b¶n m·, ®Çu tiªn N gi¶i m· "banma" ®Ó ®­îc b¶n "vesohoa". NÕu dïng ®óng hµm gi¶i m·, v¨n b¶n nµy trïng víi b¶n "sohoa". Tõ b¶n "vesohoa" ph¶i qua mét lÇn chuyÓn ng­îc l¹i qu¸ tr×nh sè ho¸ míi vÒ b¶n gèc. Nh­ vËy v¨n b¶n ®­îc m· hai lÇn chø kh«ng ph¶i mét lÇn, b»ng c¸ch sö dông c¸c c¸ch chuyÓn sè ho¸ kh¸c nhau (quy ­íc m· kh¸c nhau). §iÒu nµy lµm t¨ng tÝnh b¶o mËt cña s¬ ®å. 4. 2. Ch­¬ng tr×nh ký ®iÖn tö theo s¬ ®å ch÷ ký RSA Ch­¬ng tr×nh cã menu chÝnh nh­ sau: Vµo b¶n râ Xem b¶n râ Xem b¶n sè ho¸ Xem b¶n ký Xem b¶n m· Xem ch÷ ký m· Gi¶i m· v¨n b¶n Gi¶i m· ch÷ ký VÒ b¶n sè ho¸ VÒ b¶n râ KiÓm thö Tho¸t Qu¸ tr×nh ký nh­ sau: B¶n râ ® sè hãa ®ký ® m· hãa ® gi¶i m· ® kiÓm thö C¸c v¨n b¶n lÇn l­ît ®­îc sinh ra: “banro” ® “sohoa” ®”banky” ® (“vbma”, ”ckma”) ® (“vbgiai”, “ckgiai”) ® “vebanro” C¸c b­íc thùc hiÖn : G chuyÓn "banro" thµnh b¶n "sohoa"(sö dông b¶ng ký tù quy ­íc trªn). Sau ®ã G ký trªn b¶n "banro" ®­îc "banky". G Dïng hµm lËp m· ®Ó m· ho¸ trªn v¨n b¶n "sohoa" vµ "banky" ®­îc hai v¨n b¶n "vbma" vµ "ckma". G göi "vbma", "ckma" cïng kho¸ cho N. N dïng hµm gi¶i m· víi kho¸ ®· biÕt ®Ó gi¶i m· "vbma" vµ "ckma" ®­îc "vbgiai" vµ "ckgiai". N kiÓm thö trªn "ckgiai", ®ßng thêi dïng ng­îc l¹i quy ­íc b¶ng ký tù trªn v¨n b¶n "vbgiai" ®Ó ®­îc "banro" ban ®Çu. Gi¶ sö G muèn ký trªn v¨n b¶n "banro" cã néi dung: "Ngay chu nhat 27 thang 5 toi o nha khong di dau ca. " Sö dông quy ­íc chuyÓn sè ho¸ nh­ trong hÖ mËt m· RSA, G ®­îc b¶n "sohoa" sau: "13322650622833466239332645625459624533263932625762454034624062393326623633403932622934622926466228266563" Sau ®ã G ký trªn b¶n "sohoa", sö dông thuËt to¸n ký: y = sigk (x) = xa mod n Gi¶ sö G chän ngÉu nhiªn p vµ q ®­îc p = 83, q = 89 Þ f(n) = 11*41*8 = 7216, n = 7387. Chän b sao cho ¦CLN(b, f(n) = 1), chän b kh«ng chia hÕt cho 11, 41 vµ 2 Chän b = 9*17 = 153 Þ a = b-1 = 4905. G ký trªn tõng cÆp 2 ký tù. G chia b¶n "sohoa" nh­ sau: x1 = 1332, x2 = 2650, .. . , x26 = 6563. Sau ®ã tÝnh yi = xib mod n, ®­îc "banky" : "7161156220025387613118417045054772351841333254837235644633736311841020231683332035509004547306015176572 ” Sau khi ký, G m· c¶ "banky" vµ b¶n "sohoa" tøc G l¹i ph¶i tÝnh hµm lËp m· vµ gi¶i m·. Sö dông s¬ ®å mËt m· RSA, G chän p1 = 73, q1 = 97, f(n) = 72*96 = 256*27 = 6912, n = 7081, b1 = 101*67 = 6767 Þ a1 = b1-1 = 143. Thùc hiÖn viÖc m· ho¸ nh­ trªn ®­îc hai b¶n "vbma" vµ "ckma": "vbma" cã néi dung: "33543952268247514146363454000406288936345307262128894576639941463634353705155307423164571740173047385673” V¨n b¶n "ckma": "55692842090931734525470425574013050247044248108605020959215645254704192810174248596461290299680156624563” TiÕp sau ®ã G göi hai v¨n b¶n "vbma" vµ "ckma" cïng kho¸ (a, a1) ®Õn cho N. Khi nhËn ®­îc b¶n m·, ®Çu tiªn N gi¶i m· "vbma" vµ "ckma" ®Ó ®­îc "vbgiai" vµ "ckgiai". Sau ®ã N kiÓm thö ch÷ ký trªn v¨n b¶n ckgiai vµ thùc hiÖn ng­îc qu¸ tr×nh chuyÓn sè ho¸ "vbgiai" ®Ó ®­îc b¶n râ. NÕu qu¸ tr×nh kiÓm thö ch÷ ký thµnh c«ng, N göi th«ng b¸o "ChÊp nhËn ch÷ ký ®óng.” ®Õn G, ng­îc l¹i, nÕu kiÓm thö thÊy ch÷ ký kh«n0g ®óng anh còng th«ng b¸o l¹i r»ng "Ch÷ ký kh«ng ®óng.” ®Õn G. Tµi liÖu tham kh¶o 1. Douglas, Cryptography, Theory and Practice, CRT Press. 2. Josef Pieprzyk & Jennifer Seberry, Cryptography: An introducetion to Computer Security. 3. Sze-tsen Hu. §¹i sè hiÖn ®¹i. 4. Ph¹m V¨n Êt, Kü thuËt lËp tr×nh C c¬ së vµ n©ng cao, nhµ xuÊt b¶n khoa häc vµ kü thuËt. 5. Ph¹m V¨n Êt, C++ vµ lËp tr×nh h­íng ®èi t­îng, nhµ xuÊt b¶n khoa häc vµ kü thuËt. 6. NguyÔn H÷u ViÖt H­ng, §¹i sè ®¹i c­¬ng, Nhµ xuÊt b¶n gi¸o dôc.