Cải biên chữ ký số Rabin

Bài viết đưa ra một cải tiến trong thuật toán tạo chữ ký Rabin-William mà không cần đến việc tính ký hiệu Jacobi, ký hiệu là RW0; Tiếp đến do các modulo được sử dụng của sơ đồ RWbị giảm đi cỡ một nửa so với sơ đồ Rabin nên đóng góp thứ hai của bài viết là đưa ra sơ đồ chữ ký Rabin mới, ký hiệu là R0, với chi phí kiểm tra tăng lên không đáng kể so với sơ đồ gốc, còn chi phí cho thuật toán tạo chữ ký cũng không cần đến việc tính ký hiệu Jacobi.
Nội dung trích xuất từ tài liệu:
Cải biên chữ ký số RabinNghiên cứu khoa học công nghệ CẢI BIÊN CHỮ KÝ SỐ RABIN Hoàng Thị Mai* Tóm tắt: Bài báo đưa ra một cải tiến trong thuật toán tạo chữ ký Rabin-William mà không cần đến việc tính ký hiệu Jacobi, ký hiệu là RW0; Tiếp đến do các modulo được sử dụng của sơ đồ RWbị giảm đi cỡ một nửa so với sơ đồ Rabin nên đóng góp thứ hai của bài báo là đưa ra sơ đồ chữ ký Rabin mới, ký hiệu là R0, với chi phí kiểm tra tăng lên không đáng kể so với sơ đồ gốc, còn chi phí cho thuật toán tạo chữ ký cũng không cần đến việc tính ký hiệu Jacobi.Từ khoá: Chữ ký số, Lược đồ chữ ký số, Lược đồ chữ ký số Rabin, Lược đồ chữ ký số Rabin-William. 1. ĐẶT VẤN ĐỀ Nghiên cứu phát triển các lược đồ chữ ký số là một trong những nội dungnghiên cứu khoa học quan trọng và mang tính thời sự của an toàn thông tin. Trongsự phát triển của khoa học mật mã, một trong nhữngbước tiến đột phá là sự ra đờicủa các hệ mật khóa công khai mà độ an toàn được đảm bảo bằng các bài toán khócủa lý thuyết số. Sau khi đưa ra sơ đồ hệ mật khóa công khai mang tên mình (hệ mật Rabin) cóđộ an toàn đúng bằng độ khó của bài toán phân tích số, năm 1979 M. O. Rabin(xem [Rabin M. O.]) công bố tiếp một sơ đồ chữ ký số tương ứng với thuật toánkiểm tra chỉ cần một phép bình phương modulo. Tuy nhiên, để tạo ra được chữ kýtheo hệ mật của ông lại cần nhiều hơn trung bình 4 phép tính ký hiệu Jacobi so vớisơ đồ chữ ký RSA. Tháng 10 năm 1980 Williams đưa ra một cải biên sơ đồ Ra bin,viết tắt bởi tên chung của hai ông là RW (xem [Williams H.]). Sơ đồ RW chỉ cầnnhiều hơn đúng 1 phép tính ký hiệu Jacobi so với sơ đồ chữ ký RSA và với ưu việttrên nó đã được đưa vào các chuẩn IEEE năm 2004 và ISO năm 2008 (xem [IEEE2004], [ISO/IEC 2008]). Bài báo này sẽ đưa ra một cải tiến trong thuật toán tạo chữ ký RW mà khôngcần đến việc tính ký hiệu Jacobi, ký hiệu là RW0. Trong sơ đồ RW, các modulođược sử dụng bị giảm đi cỡ một nửa so với sơ đồ Rabin nên đóng góp thứ hai củabài báo là đưa ra sơ đồ chữ ký Rabin mới, ký hiệu là R0, với chi phí cho phép kiểmtra tăng lên không đáng kể so với sơ đồ gốc, còn chi phí cho thuật toán tạo chữ kýcũng không cần đến việc tính ký hiệu Jacobi. 2. SƠ ĐỒ CHỮ KÝ RABIN VÀ CẢI BIÊN CỦA WILLIAMS2.1. Sơ đồ chữ ký Rabin Trong [Rabin M. O.] sơ đồ chữ ký Rabin được trình bày như sau.2.1.1. Tham số hệ thống Số nguyên n = p.q trong đó p, q là hai số nguyên tố khác nhau với p, q ≡ 3 (mod 4) (1) và b ∈ℤ∗ . Các số nguyên n thỏa mãn điều kiện (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ácthực chữ ký là (n, b). Hàm tóm lược, Hash: {0,1}¥ ®{0,1} .Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 73 Công nghệ thông tin Hàm đổi xâu bít sang số nguyên có biểu diễn nhị phân là xâu bít đó,Code:{0,1}¥ ® ℤ.2.1.2. Thuật toán tạo chữ kí 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) ∈ℤ∗ ´{0,1} là chữ ký của người giữ bộ (n, p, q, b) lên M. 1. Lấy ngẫu nhiên xâu k bít R. 2. Tính u = Code(Hash(M||R)). 3. Giải phương trình x(x + b) = u (mod n) (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 (2). 4. Trả về cặp (s,R).■2.1.3. Thuật toán kiểm tra Input: M, (s,R), (n, b). Trong đó: M ∈{0,1}¥ là thông báo được ký; (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ôngkhai (n,b). 1. Tính u = Code(Hash(M||R)). 2. 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 (2).■2.2. Sơ đồ chữ ký Rabin-Williams Tháng 10 năm 1980 Williams đưa ra một cải biên sơ đồ Rabin, sơ đồ được viếttắt là RW, bởi tên chung của hai ông (xem [Williams H.]). Sơ đồ RW đã được đưavào các chuẩn IEEE năm 2004 và ISO năm 2008 (xem [IEEE 2004], [ISO/IEC2008]) có thể được trình bày như sau.2.2.1. Tham số hệ thống Số blum n = p.q thỏa mãn p ≠ q (mod 8). (3) và c = q. (q mod p). (4) 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ườixá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} ®ℤ∗ sao cho với mọi H ∈{0,1} thì f(H) ≡ 12 (mod 16). ...