Đề tài Sơ đồ 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 )