Lược đồ Chữ Ký Số Elgamal - 123doc

Năm 1985, Taher Elgamal [69] đề xuất một phương pháp mới của mã hóa khóa công khai dựa trên bài toán logarit rời rạc. Hệ mật Elgamal bao gồm thuật toán chữ ký số và thuật toán mật mã khóa công khai. Các chuẩn chữ ký số DSS [52] của Mỹ được phát triển trên cơ sở thuật toán chữ ký số của hệ mật Elgamal.

Hệ mật Elgamal là một biến thể của sơ đồ phân phối khóa Diffie - Hellman [73], tính an toàn của hệ mật dựa trên tính khó giải của bài toán logarit rời rạc. Tuy nhiên, nhược điểm lớn nhất của hệ mật Elgamal là kích thước thông tin sau khi mã hóa gửi đi sẽ tăng gấp đôi so với thông tin gốc.

1.4.2.1. Thuật toán chữ ký số Elgamal

Thuật toán Elgamal gồm các quá trình thực hiện như sau:

- Tạo các tham số và khóa.

- Tạo chữ ký.

- Kiểm tra chữ ký.

a. Tạo các tham số và khóa

1. Chọn số nguyên tố p đủ lớn sao cho bài toán logarit trong Zp là khó giải.

2. Chọn phần tử nguyên thủy g: *

p

gZ

3. Chọn ngẫu nhiên khóa bí mật x sao cho: 1 x p

4. Tính khóa công khai: ygxmodp Trong đó:

- y là khóa công khai; - x là khóa bí mật;

- p, g là các tham số công khai.

b. Tạo chữ ký

Thuật toán ký lên thông điệp dữ liệu M gồm các bước sau: 1. Chọn ngẫu nhiên giá trị k thỏa mãn điều kiện:

1  k p 1 và gcd( ,k p 1) 1 2. Tính thành phần thứ nhất (r) và thành phần thứ hai (s) của chữ ký: 1 mod , ( ( ) ) mod ( 1). k r g p s k H M x r p           Trong đó: - H(.) là hàm băm. c. Kiểm tra chữ ký 1. Tính vế thứ nhất: u gH M( )mod p 2. Tính vế thứ hai: v yrrsmod p

3. Kiểm tra: Nếu (uv) thì chữ ký ( , )r s là hợp lệ, ngược lại chữ ký ( , )r s là giả mạo.

1.4.2.2. Độ an toàn của hệ mật Elgamal

Mức độ an toàn của hệ mật Elgamal sẽ bị phá vỡ khi kẻ tấn công có thể khôi phục thông điệp dữ liệu m từ bản mã (r,s) và các tham số công khai của hệ thống p, y, g.

a. Trường hợp tính được khóa mật x hoặc k.

Để tính được x hoặc k, kẻ tấn công cần phải giải một trong hai bài toán logarit rời rạc: y  gx modp hoặc: r gk modp. Tuy nhiên, việc giải bài toán logarit rời rạc là một việc khó và chưa có cách hữu hiệu nào để thực hiện được. Điều này đã được chứng minh trong [45] và [66].

b. Trường hợp khôi phục nội dung thông điệp dữ liệu m.

Để khôi phục được nội dung thông điệp dữ liệu m kẻ tấn công cần phải giải được: m c  y kmod p

trong trường hợp không biết k (trong đó y là khóa công khai của người nhận), hoặc: m c  r xmodp trong trường hợp không biết x (khóa bí mật của người nhận). Có thể thấy rằng, việc khôi phục m từ việc giải trực tiếp các bài toán này cũng khó như việc giải bài toán logarit rời rạc để tìm x hoặc k.

c. Trường hợp sử dụng lại khóa k.

Trong hệ mật Elgamal, khi giá trị k dùng cho hai lần ký khác nhau thì nguy cơ bị tấn công có thể xảy ra.

Giả thiết, nếu ta sử dụng cùng một giá trị k để mã hóa hai thông điệp dữ liệu m1 và m2 được các bản mã tương ứng là (c1, r1) và (c2, r2), khi đó:

        1 1 1 2 1 x k 2 x k mod c c m g m g p        Suy ra:   1 2 1 2 1mod 1 m  c c  m pm

Điều này chứng tỏ kẻ tấn công sẽ dễ dàng biết được nội dung của thông điệp dữ liệu còn lại nếu biết nội dung của một trong hai thông điệp dữ liệu m1

hoặc m2.

Hệ mật Elgamal được xây dựng dựa trên bài toán logarit rời rạc. Do đó, tính an toàn của hệ mật tùy thuộc vào độ phức tạp của bài toán logarit. Khi chọn số nguyên tố p đủ lớn, thuật toán mã hóa Elgamal chưa có phương pháp thám mã hiệu quả.