Báo cáo Sơ đồ chữ ký số ELGAMAL

BÁO CÁO BÀI TẬPAN TOÀN BẢO MẬT THÔNG TIN GV hướng dẫn: Trần Ngọc Thái Nhóm sinh viên: Đỗ Thanh Tùng Nguyễn Viết Huy Lớp: CT702 Tên đề tài: Sơ đồ chữ ký số ELGAMAL TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG KHOA CÔNG NGHỆ THÔNG TIN I-Giới thiệu chung về chữ ký số: Thông thường chữ ký viết tay trên các văn bản, trên các tài liệu hay trên các hợp đồng kinh tế ..v.v.. thì được dùng để xác nhận người kí nó . Sơ đồ chữ kí ( hay còn gọi là chữ ký số ) là phương pháp ký một bức điện lưu dưới dạng điện tử. Chẳng hạn một bức điện có chữ ký được truyền trên mạng máy tính. Một sơ đồ chữ ký số thường chứa hai thành phần: Thuật toán ký và thuật toán xác minh. Người A có thể ký bức điện x dùng thuật toán ký an toàn. Chữ ký Sig(x) nhận được có thể kiểm tra bằng thuật toán xác minh công khai Ver . Khi cho trước cặp (x,y) thuật toán xác minh cho giá trị TRUE hay FALSE tùy thuộc vào việc chữ ký được xác thực như thế nào. Đị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 : 1. P: là tập hữu hạn các bức điện có thể. 2. A: là tập hữu hạn các chữ ký có thể . 3. K: là tập hữu hạn các khóa, mỗi khóa KK gồm có 2 phần K=(K’,K’’), K’ là bí mật, K’’ là công khai 4. Với mọi K=(K’,K’’) tồn tại một thuật toán ký SigKS và một thuật toán kiểm thử 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: I-Giới thiệu chung về chữ ký số: 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. I-Giới thiệu chung về chữ ký số: II-Sơ đồ ký Elgamal: 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ý đó. II-Sơ đồ ký Elgamal: 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à rất khó và giả sử   Zp* là phần tử nguyên thuỷ Cho p = Zp* , A=Zp* Zp-1, và ký hiệu: K={(p, , a, ) |   a (mod p) } Giá trị K’=a là mật, K’’=(p, , ) là công khai Với K= (p, , a, ) và với một số ngẫu nhiên (mật) k  Zp-1* II-Sơ đồ ký Elgamal: Định nghĩa: Sigk(x,k) = (,). Trong đó  = k mod p và  = (x-a )k-1 mod (p-1). Với x,  Zp* và  Zp-1 ta định nghĩa Ver(x,y,) = True    x (mod p). Nếu chữ ký được thiết lập đúng thì xác minh sẽ thành công vì :    a k (mod p)  x (mod p ). II-Sơ đồ ký Elgamal: Ở đây ta dùng hệ thức: a  + k   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. II-Sơ đồ ký Elgamal: Ta xét một ví dụ sau: Giả sử : Cho p =467 , =2 , a=127 khi đó:  = a 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)mod466 =431. Khi đó :  = 2213 mod 467 =29 và  = (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ệ . III-Độ 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  và sau đó thử tìm giá trị  tương ứng. Anh ta phải tính Logarithm rời rạc Logx-. Mặt khác, nếu đầu tiên anh ta chọn  và sau đó thử tìm  và thử giải phương trình:   x ( mod p ) . III-Độ mật của sơ đồ chữ ký Elgamal: Để tìm . Đâ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  và  đồng thời để ( ,  ) 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. III-Độ mật của sơ đồ chữ ký Elgamal: Nếu Oscar chọn  và  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 Log. 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  )-1 mod ( p –1 ). III-Độ mật của sơ đồ chữ ký Elgamal: 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ử ( ,1 ) là chữ ký trên x1 và( ,2 ) là chữ ký trên x2. Khi đó ta có: 1  x1 (mod p) và 2  x2 (mod p) Như vậy: x1..x2   12 (mod p). III-Độ mật của sơ đồ chữ ký Elgamal: Khi đó ta có: 1  x1 (mod p) và 2  x2 (mod p) Như vậy: x1..x2   12 ( mod p ). Nếu viết  = k ta nhận được phương trình tìm k chưa biết sau:  x1-.x2  k( 1- 2 ) ( mod p ). tương đương với phương trình: x1 - x2  k (1-2) (mod p-1). Bây giờ giả sử d = USCLN (1-2 ,p –1). Vì d | ( p –1) và d | (1-2 ) nên suy ra d | (x1-x2). Ta định nghĩa: x’ = (x1-x2 )/d; ’ = ( 1-2 ) / d; p’ = ( p-1 ) / d III-Độ mật của sơ đồ chữ ký Elgamal: Khi đó đồng dư thức trở thành: x’  k ’ ( mod p’ ) Vì USCLN (’,p’ ) =1, nên ta có thể tính:  = ( ’ ) –1 mod p’. Khi đó giá trị k xác định theo modulo p sẽ là : k = x’  mod p’ Phương trình này cho d giá trị có thể của k: k = x’  + 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:   k ( mod p ) Lời cảm ơn Chúng em rất mong nhận được sự đóng góp ý kiến của thầy(cô) cùng toàn thể các bạn. Chúng em xin chân thành cảm ơn!