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

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++.

doc45 trang | Chia sẻ: lvcdongnoi | Ngày: 30/06/2013 | Lượt xem: 1601 | Lượt tải: 3download
Bạn đang xem nội dung tài liệu Một số thuật toán ký và xác nhận chữ ký điện tử, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
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.

Các file đính kèm theo tài liệu này:

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