CHƯƠNG 1. TỔNG QUAN VỀ CHỮ KÝ SỐ VÀ HƯỚNG NGHIÊN CỨU PHÁT TRIỂN 1. Lược đồ chữ ký số Định nghĩa 1.1 Một lược đồ chữ ký số là một bộ gồm năm thành phần ( P, K , A, S ,V ) thoả mãn các điều kiện sau đây: 1. P là tập hữu hạn các thông báo.
K là tập hữu hạn các khoá bí mật. A là tập hữu hạn các thuật toán ký. S là tập hữu hạn các chữ ký. V là tập hữu hạn các thuật toán kiểm tra.
Với mỗi k K tồn tại một thuật toán ký sigk A và một thuật toán kiểm tra verk V tương ứng, mỗi sig k : P → S và verk : P S → {true, false} là những hàm sao cho với mỗi m P và s S thoả mãn phương trình sau: true, s = sig k (m) verk ( s, m) = false, s sig k (m) Định nghĩa 1.2 Chữ ký số (digital signature) là một chuỗi dữ liệu được sinh ra bởi một lược đồ chữ ký số có chức năng liên kết một thông báo với thực thể tạo ra nó, nhằm đáp ứng các yêu cầu về: tính xác thực về nguồn gốc và tính toàn vẹn về nội dung của thông báo được ký.3 Thuật toán tạo chữ ký (còn gọi là thuật toán ký - digital signature generation algorithm/signature generation algorithm) là một phương pháp tạo lập chữ ký số. luan an 6 Định nghĩa 1.4 Thuật toán kiểm tra chữ ký (digital signature verification algorithm/ verification algorithm) là phương pháp kiểm tra để khẳng định rằng một chữ ký số là hợp lệ hay ngược lại. Các thuộc tính cần có của một lược đồ chữ ký số Một lược đồ chữ ký cần đảm bảo bốn thuộc tính sau đây: • Tính đầy đủ: đảm bảo mọi thông báo đều ký được. • Tính đúng đắn: Trong một lược đồ chữ ký số, mọi chữ ký được tạo ra bởi thuật toán tạo chữ ký đều được chấp nhận bởi thuật toán kiểm tra chữ ký.
• Tính khả thi: Thuật toán tạo chữ ký là dễ dàng đối với người ký (có khóa mật) và thuật toán kiểm tra là dễ dàng đối với mọi người (sử dụng khóa công khai). Thuộc tính này thường được đặc trưng bởi độ phức tạp của thuật toán ký và thuật toán kiểm tra là đa thức đối với các đối tượng tương ứng. • Tính an toàn trước tấn công tìm tham số mật và tấn công giả mạo chữ ký: thuộc tính này thường được đặc trưng bởi một bài toán khó của lý thuyết số.2 Một số lược đồ chữ ký số Trong các lược đồ chữ ký khóa công khai, với mỗi cặp khóa được chọn thì việc tính toán khóa mật từ khóa công khai đều được đảm bảo bằng một bài toán khó của lý thuyết số. Các bài toán cơ bản đó là: • Bài toán phân tích số (FP – Factorization Problem).
Độ khó của bài toán này đảm bảo tính an toàn cho hệ mật RSA và chữ ký số RSA. • Bài toán Logarithm rời rạc (DLP- Discrete Logarithm Problem). Độ khó của bài toán DLP đảm bảo tính an toàn cho hệ mật mã khóa công khai và chữ ký số ElGamal cũng như nhiều hệ chữ ký số khác, chẳng hạn DSA (Digital Signature Algorithm). luan an 7 • Bài toán logarithm rời rạc trên đường cong elliptic (ECDLP-Elliptic Curve Discrete Logarithm Problem).
Độ khó của bài toán này đảm bảo an toàn cho các lược đồ hệ mật trên đường cong Elliptic. Trong phần này, luận án trình bốn lược đồ chữ ký số cơ bản có ảnh hưởng trực tiếp đến vẫn đề nghiên cứu của luận án là lược đồ RSA, lược đồ Rabin và lược đồ Rabin-Williams, lược đồ DSA và lược đồ ECDSA.1 Lược đồ RSA Trong lịch sử phát triển của khoa học mật mã, nếu như Diffie, Hellman và Merkle đã phát minh ra khái niệm mật mã khóa công khai thì Rivest, Shamir và Adleman lại có công lớn lao phát minh ra RSA, một sự thực thi đẹp nhất của hệ mật này. Thuật toán RSA đã được R.Adleman công bố lần đầu tiên vào tháng 8 năm 1977 [2]. Trên vành Zn , thuật toán RSA sử dụng số nguyên dương e là khóa công khai và số nguyên d là khóa bí mật.
Số e cần thỏa mãn nguyên tố cùng nhau với 𝜙(𝑛) = (𝑝 − 1) × (𝑞 − 1) và theo đó, số d tìm được bằng các giải phương trình đồng dư 𝑑𝑒 ≡ 1 𝑚𝑜𝑑 𝜙(𝑛). Để xác định khóa bí mật d từ khóa công khai (n,e) cần xác định được hai nhân tử p và q của n, đây chính là bài toán phân tích số (FP- Factorization Problem).1 – Thuật toán sinh khóa RSA INPUT: tham số an toàn l OUTPUT: khóa công khai (n,e) và khóa bí mật d 1. Chọn hai số nguyên tố lớn p, q có cùng độ dài 𝑙/2 bit; 2. Chọn số nguyên e sao cho 1 < 𝑒 < 𝜙(𝑛) và 𝑔𝑐𝑑(𝑒, 𝜙(𝑛)) = 1; 5.
Tính d sao cho 1 < 𝑑 < 𝜙(𝑛) và 𝑑𝑒 ≡ 1 𝑚𝑜𝑑 𝜙(𝑛); 6. Giả sử h=H(m) là giá trị băm của văn bản m với H(.) là hàm băm mật mã. Khi đó, người ký sử dụng khóa mật d để tạo chữ ký và mọi người sử dụng luan an 8 khóa công khai e để kiểm tra chữ ký. Thuật toán RSA dùng cho ứng dụng xác thực được trình bày như sau: Thuật toán 1.2 – Thuật toán tạo chữ ký RSA INPUT: khóa công khai (n,e), khóa bí mật d, văn bản 𝑚 OUTPUT: chữ ký s 1.3 – Thuật toán kiểm tra chữ ký RSA INPUT: khóa công khai (n,e), văn bản m, chữ ký 𝑠 OUTPUT: Chữ ký hợp lệ hoặc không hợp lệ 1.
If h=h’ then return(“Chữ ký hợp lệ”) else return(“Chữ ký không hợp lệ”). Chi phí thời gian chạy của hệ RSA chủ yếu là chi phí của phép tính lũy thừa theo modulo n. Chi phí thời gian chạy của hệ RSA sẽ được trình bày chi tiết trong mục 1.2 Chữ ký số Rabin Ngay sau khi hệ RSA ra đời, năm 1979 M. Rabin công bố lược đồ chữ ký số Rabin [3] có độ an toàn cũng được đảm bảo bởi độ khó của bài toán phân tích số.
Nếu trong lược đồ chữ ký RSA, tham số e cần thỏa mãn nguyên tố cùng nhau với 𝜙(𝑛), thì trong lược đồ Rabin tham số e=2. Với việc lựa chọn e=2, lược đồ chữ ký Rabin đạt được ưu điểm nổi trội khi chỉ cần thực hiện một phép bình phương modulo n trong thuật toán kiểm tra chữ ký. Tuy nhiên để có được điều này, các tham số hệ thống p, q của lược đồ Rabin cần thỏa mãn là số nguyên tố đồng dư 3 (mod 4). luan an 9 Tham số hệ thống.q trong đó p, q là hai số nguyên tố khác nhau với p, q ≡ 3 (mod 4) (1.
Các số nguyên n thỏa mãn điều kiện (1.1) còn được gọi là các số “blum”. Khóa bí mật do người ký giữ là bộ (n, p, q, b) và khóa công khai cho người xác thực chữ ký là (n, b). Hàm tóm lược, Hash: {0,1} → {0,1}h. Hàm đổi xâu bít sang số nguyên có biểu diễn nhị phân là xâu bít đó, 𝐶𝑜𝑑𝑒: {0,1} → ℤ.
Với xâu bít 𝑥0 𝑥1 … 𝑥𝑡−1 , ta có: 𝐶𝑜𝑑𝑒(𝑥0 𝑥1 … 𝑥𝑡−1 ) = 𝑥0 2𝑡−1 + 𝑥1 2𝑡−2 + ⋯ + 𝑥𝑡−1 Thuật toán 1.4 – Thuật toán tạo chữ ký lược đồ Rabin INPUT: M ∈ {0,1} , (n, p, q, b). Trong đó: M là thông báo cần ký. (n, p, q, b) là khóa bí mật của người ký. OUTPUT: (s,R) ∈ ℤ∗n {0,1}k là chữ ký của người giữ bộ (n, p, q, b) lên thông báo M.
Lấy ngẫu nhiên xâu k bít R. Giải phương trình x(x + b) = u (mod n) (1.2) Nếu vô nghiệm, quay lại bước 1. Ngược lại lấy s là một nghiệm của phương trình (1.5 – Thuật toán kiểm tra chữ ký lược đồ Rabin INPUT: M, (s,R), (n, b). Trong đó: M ∈ {0,1} là thông báo được ký; luan an 10 (s,R) là chữ ký lên M; (n,b) là khóa công khai của người ký.
OUTPUT: Sự chấp nhận hay bác bỏ (s,R) là chữ ký lên M của người có khóa công khai (n,b). Chấp nhận chữ ký (s,R) lên thông báo M là của người có khóa công khai (n,b) khi và chỉ khi s là nghiệm của (1.3 Chữ ký số Rabin-Williams Trong lược đồ chữ ký chữ ký Rabin, chữ ký s là một nghiệm của phương trình đồng dư bậc hai (1.q, thực tế để giải (1.2) cần giải hai phương trình đồng dư: x(x + b) = u (mod p) và x(x + b) = u (mod q) để tìm được bốn nghiệm 𝑠 = ±𝑥 (𝑚𝑜𝑑 𝑝) và 𝑠 = ±𝑥 (𝑚𝑜𝑑 𝑞). Từ bốn nghiệm này, sử dụng định lý phần dư Trung hoa ta tìm được bốn nghiệm khác nhau của s. Việc lựa chọn giá trị s nào trong bốn giá trị tìm được là một trong những vấn đề cần cải tiến của lược đồ Rabin.
Tháng 10 năm 1980 Williams đưa ra một cải biên lược đồ Rabin, lược đồ được viết tắt là RW, bởi tên chung của hai ông [4]. Lược đồ Rabin cần đến 4 phép tính ký hiệu Jacobi trong thuật toán tạo chữ ký, trong khi Williams cải tiến chỉ cần một phép tính ký hiệu Jacobi. Lược đồ RW đã được đưa vào các chuẩn ISO/IEC 9796 [5] Tham số hệ thống.4) luan an 11 Khóa bí mật do người ký giữ là bộ (n, p, q, c) và khóa công khai cho các người xác thực chữ ký là n. Hàm tóm lược, Hash: {0,1} → {0,1}ℎ.
Hàm định dạng thông báo f: {0,1}h → ℤ∗n sao cho với mọi H ∈ {0,1}h thì f(H) ≡ 12 (mod 16).6 – Thuật toán tạo chữ ký lược đồ Rabin-Williams INPUT: M, (n, p, q, c). Trong đó: 𝑀 ∈ {0,1} là thông báo cần ký. (n, p, q, c) là khóa bí mật của người ký. OUTPUT: 𝑠 ∈ ℤn∗ sao cho 0 s < n/2 là chữ ký của người giữ bộ (n,p,q,c) lên thông báo M.
if ( ) = 1 then v ← u; 𝑛 else v ← u/2; 𝑝+1 3.7 – Thuật toán kiểm tra chữ ký lược đồ Rabin-Williams INPUT: M, s, n. Trong đó: 𝑀 ∈ {0,1} là thông báo được ký. s là chữ ký lên M. n là khóa công khai của người ký.
Trong đó sự chấp nhận s là chữ ký lên M của người có khóa công khai n khi và chỉ khi Accept = 1. if s ∉ [0, ] then Accept 0; goto 5; 2 2. if (v ∈ {u, n – u} then Accept ← 1; else v ← 2.v mod n; if (v ∈ {u, n – u} then Accept ← 1; else Accept ← 0; 5. Lược đồ chữ ký DSA Hệ logarithm rời rạc đầu tiên là giao thức thỏa thuận khóa được Diffie và Hellman đề xuất năm 1976 [6].