Chữ kí số Elgamal

SƠ ĐỒ CHỮ KÝ SỐ ELGAMAL I.Giới thiệu về chữ ký số Trong cách thức truyền thống, thông báo được truyền đi trong giao dịch thường dưới dạng các văn bản viết tay hoặc đánh máy được kèm thêm chữ ký (viết tay) của người gửi ở bên dưới văn bản. Chữ ký đó là bằng chứng xác nhận thông báo đúng là của người ký, tức là của chủ thể giao dịch, và nếu tờ giấy mang văn bản không bị cắt, dán, tẩy, xóa thì tính toàn vẹn của thông báo cũng được chứng thực bởi chữ ký đó. Chữ ký viết tay có nhiều ưu điểm quen thuộc như dễ kiểm thử, không sao chép được, chữ ký của một người là giống nhau trên nhiều văn bản, nhưng mỗi chữ ký gắn liền với một văn bản cụ thể, .v.v… Khi chuyển sang cách thức truyền tin bằng phương tiện hiện đại, các thông báo được truyền đi trên mạng truyền tin số hóa, bản thân các thông báo cũng được biểu diễn dưới dạn số hóa, tức dưới dạng các bit nhị phân, “chữ ký” nếu có cũng ở dưới dạng các dãy bit, thì các mối quan hệ tự nhiên kể trên không còn giữ được nữa. Chẳng hạn, “ chữ ký ” của mỗi người gửi trên những văn bản khác nhau phải thể hiện được sự gắn kểttách nhiệm của người gửi đối với từng văn bản đó thì tất yếu phải khác nhau chứ không thể là những đoạn bit giống nhau như các chữ ký giống nhau trên các văn bản thông thường. Chữ ký viết tay có thể được kiểm thử bằng cách so sánh với nguyên mẫu, nhưng “ chữ ký ” điện tử thì không thể có “ nguyên mẫu ” để mà so sánh, việc kiểm thử phải được thực hiện bằng những thuật toán đặc biệt. Một vấn đề nữa là việc sao chép một văn bản cùng chữ ký. Nếu là văn bản cùng chữ ký viết tay thì dễ phân biệt bản gốc với bản sao, do đó khó mà dùng lại được một văn bản có chữ ký thật. Còn với văn bản điện tử cùng chữ ký điện tử thì có thể nhân bản sao chép tùy thích, khó mà phân biệt được bản gốc với bản sao, cho nên nguy cơ dùng lại nhiều lần là có thực, do đó cần có biện pháp để tránh nguy cơ đó. II.Định nghĩa hình thức của chữ ký số Mét s¬ ®å ch÷ kÝ sè lµ bé 5 ( P,A,K,S,V) tho¶ m·n c¸c ®iÒu kiÖn sau : P: lµ tËp h÷u h¹n c¸c bøc ®iÖn cã thÓ. A: lµ tËp h÷u h¹n c¸c ch÷ kÝ cã thÓ . K: kh«ng gian kho¸ lµ tËp h÷u h¹n c¸c kho¸ cã thÓ Víi mçi K thuéc K tån t¹i mét thuËt to¸n kÝ SigK ÎS vµ mét thuËt to¸n x¸c minh VerK Î V . Mçi SigK: P -> A vµ VerK :P x A -> { TRUE ,FALSE } lµ nh÷ng hµm sao cho mçi bøc ®iÖn x ÎP vµ mçi bøc ®iÖn y Î A tho¶ m·n ph­¬ng tr×nh sau ®©y: TRUE nÕu y= Sig(x) Ver (x,y) = FALSE nÕu y #Sig(x) Víi mçi K Î K , hµm SigK vµ VerK lµ c¸c hµm thêi gian ®a thøc. VerK sÏ lµ hµm c«ng khai cßn SigK lµ hµm mËt. Ta gäi Alice lµ ng­êi göi cßn Bob lµ ng­êi nhËn. Kh«ng thÓ dÔ dµng tÝnh to¸n ®Ó gi¶ m¹o ch÷ kÝ cña Bob trªn bøc ®iÖn x. NghÜa lµ víi x cho tr­íc, chØ cã Bob míi cã thÓ tÝnh ®­îc ch÷ kÝ y ®Ó Ver(x,y)= True. III. S¬ ®å ch÷ kÝ Elgamal Sau ®©y ta sÏ m« t¶ s¬ ®å ch÷ kÝ sè Elgamal ®· tõng giíi thiÖu trong mét b¸o c¸o n¨m 1985. B¶n c¶i tiÕn cña s¬ ®å nµy ®· ®­îc ViÖn Tiªu chuÈn vµ C«ng nghÖ Quèc gia Mü (NIST) chÊp nhËn lµm chuÈn ch÷ kÝ sè. S¬ ®å Elgamal ®­îc thiÕt kÕ víi môc ®Ých dµnh riªng cho ch÷ kÝ sè. Kh¸c víi s¬ ®å RSA dïng cho c¶ m· kho¸ c«ng khai lÉn ch÷ kÝ sè. S¬ ®å Elgamal ®­îc thiÕt kÕ víi môc ®Ých dµnh riªng cho ch÷ kÝ sè, ®iÓm m¹nh cña nã lµ cïng sè nguyªn tè p trong cïng mét s¬ ®å th× víi k lµ ngÉu nhiªn nªn ta cã thÓ cã nhiÒu ch÷ kÝ sè, kh«ng tÊt ®Þnh gièng nh­ hÖ thèng m· kho¸ c«ng khai Elgamal, ë s¬ ®å ch÷ kÝ RSA ta chØ thÊy trªn cïng mét s¬ ®å víi cïng mét sè nguyªn tè p th× ta chØ cã mét ch÷ kÝ sè. §iÒu nµy cã nghÜa lµ cã nhiÒu ch÷ kÝ hîp lÖ trªn bøc ®iÖn cho tr­íc bÊt k×. ThuËt to¸n x¸c minh ph¶i cã kh¶ n¨ng chÊp nhËn bÊt k× ch÷ kÝ hîp lÖ nµo khi x¸c thùc ch÷ kÝ ®ã. S¬ ®å ch÷ kÝ Elgamal Cho p lµ sè nguyªn tè sao cho bµi to¸n Logarithm rêi r¹c trªn Zp lµ khã vµ gi¶ sö a Î Zp* lµ phÇn tö nguyªn thuû Cho p = Zp* , A=Zp*´ Zp-1, vµ kÝ hiÖu: K={(p,a,a,b):b ºaa (mod p) } Gi¸ trÞ p,a,b lµ c«ng khai, cßn a lµ mËt Víi K=(p,a,a,b) vµ víi mét sè ngÉu nhiªn (mËt) k Î Zp-1* §Þnh nghÜa: Sigk(x,k) = (g,d). Trong ®ã g = ak mod p vµ d = (x-a g)k-1 mod (p-1). Víi x, g ÎZp* vµ d ÎZp-1 ta ®Þnh nghÜa Ver(x,y,d) = True « bg gd ºax (mod p). NÕu ch÷ kÝ ®­îc thiÕt lËp ®óng th× x¸c minh sÏ thµnh c«ng v× : bg gd º aa gak d (mod p) º ax (mod p ). ë ®©y ta dïng hÖ thøc: a g + k d º x (mod p-1). Bob tÝnh ch÷ kÝ b»ng c¸ch dïng c¶ gi¸ trÞ mËt a (lµ mét phÇn cña kho¸ ) lÉn sè ngÉu nhiªn mËt k ( dïng ®Ó kÝ lªn bøc ®iÖn x ). ViÖc x¸c minh cã thÓ thùc hiÖn duy nhÊt b»ng th«ng tin c«ng khai. Ta xÐt mét vÝ dô sau: Gi¶ sö : Cho p =467 , a=2 , a=127 khi ®ã: b = aa mod p = 2127 mod 467 = 132. NÕu Bob muèn kÝ lªn bøc ®iÖn x = 100 vµ chän sè ngÉu nhiªn k = 213 ( chó ý lµ USCLN(213,466) =1 vµ 213-1 mod 466 =431 ). Khi ®ã : g = 2213 mod 467 =29 vµ d = (100 – 127 ´ 29 ) 431 mod 466 = 51 BÊt k× ai còng cã thÓ x¸c minh ch÷ kÝ nµy b»ng c¸ch kiÓm tra : 132292951 º 189 (mod 467 ) vµ 2100 º 189 (mod 467 ) V× thÕ ch÷ kÝ lµ hîp lÖ . Ta xÐt ®é mËt cña s¬ ®å ch÷ kÝ Elgamal. Gi¶ sö, Oscar thö gi¶ m¹o ch÷ kÝ trªn bøc ®iÖn x cho tr­íc mµ kh«ng biÕt a. NÕu Oscar chän g vµ sau ®ã thö t×m gi¸ trÞ d t­¬ng øng. Anh ta ph¶i tÝnh Logarithm rêi r¹c Log gax b-g . MÆt kh¸c, nÕu ®Çu tiªn anh ta chän d vµ sau ®ã thö t×m g vµ thö gi¶i ph­¬ng tr×nh: bg gdº ax ( mod p ) . §Ó t×m g. §©y lµ bµi to¸n ch­a cã lêi gi¶i nµo, tuy nhiªn, d­êng nh­ nã ch­a ®­îc g¾n víi ®Õn bµi to¸n ®· nghiªn cøu kÜ nµo nªn vÉn cßn kh¶ n¨ng cã c¸ch nµo ®ã ®Ó tÝnh d vµ g ®ång thêi ®Ó (d , g ) lµ mét ch÷ kÝ. HiÖn thêi kh«ng ai t×m ®­îc c¸ch gi¶i song còng kh«ng ai kh¼ng ®Þnh ®­îc r»ng nã kh«ng thÓ gi¶i ®­îc. NÕu Oscar chän g vµ d vµ sau ®ã thö gi¶i t×m x, anh ta sÏ ph¶i ®èi mÆt víi bµi to¸n Logarithm rêi r¹c, tøc bµi to¸n tÝnh Logabggd. V× thÕ Oscar kh«ng thÓ kÝ mét bøc ®iÖn ngÉu nhiªn b»ng biÖn ph¸p nµy. Cuèi cïng, ta sÏ nªu c¸ch cã thÓ ph¸ ®­îc s¬ ®å nµy nÕu kh«ng ¸p dông nã mét c¸ch cÈn thËn. Tr­íc hÕt, gi¸ trÞ k ngÉu nhiªn ®­îc dïng ®Ó tÝnh ch÷ kÝ ph¶i ®­îc gi÷ kÝn kh«ng ®­îc ®Ó lé. V× nÕu k bÞ lé, kh¸ ®¬n gi¶n ®Ó tÝnh: a = (x-k g )d-1 mod ( p –1 ). DÜ nhiªn, mét khi a bÞ lé th× hÖ thèng bÞ ph¸ vµ Oscar cã thÓ dÔ dµng gi¶ m¹o ch÷ kÝ. Mét kiÓu dïng sai s¬ ®å n÷a lµ dïng cïng gi¸ trÞ k ®Ó kÝ hai bøc ®iÖn kh¸c nhau. §iÒu nµy còng t¹o thuËn lîi cho Oscar tÝnh a vµ ph¸ hÖ thèng. Sau ®©y lµ c¸ch thùc hiÖn. Gi¶ sö ( g,d1 ) lµ ch÷ kÝ trªn x1 vµ( g,d2 ) lµ ch÷ kÝ trªn x2. Khi ®ã ta cã: bggd1 º ax1 (mod p ) vµ bggd2 º ax2 ( mod p ) Nh­ vËy: ax1..x2 º g d1d2 ( mod p ). NÕu viÕt g = ak ta nhËn ®­îc ph­¬ng tr×nh t×m k ch­a biÕt sau: a x1-.x2 º ak( d1- d2 ) ( mod p ). t­¬ng ®­¬ng víi ph­¬ng tr×nh: x1 - x2 º k (d1-d2) (mod p-1). B©y giê gi¶ sö d = USCLN(d1-d2 ,p –1). V× d | ( p –1) vµ d | (d1-d2 ) nªn suy ra d | (x1-x2). Ta ®Þnh nghÜa: x’ = (x1-x2 )/d; d’ = ( d1-d2 ) / d; p’ = ( p-1 ) / d Khi ®ã ®ång d­ thøc trë thµnh: x’ º k d’ ( mod p’ ) V× USCLN (d’,p’ ) =1, nªn ta cã thÓ tÝnh: e = ( d’ ) –1 mod p’ Khi ®ã gi¸ trÞ k x¸c ®Þnh theo modulo p sÏ lµ : k = x’ e mod p’ Ph­¬ng tr×nh nµy cho d gi¸ trÞ cã thÓ cña k: k = x’ e + i p’ mod p víi i nµo ®ã, 0 £ i £ d-1. Trong ®ã d gi¸ trÞ cã thÓ nµy cã thÓ x¸c ®Þnh ®­îc mét gi¸ trÞ ®óng duy nhÊt qua viÖc kiÓm tra ®iÒu kiÖn: g º ak ( mod p )