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

Nghiên cứu khoa học công nghệ<br /> <br /> CẢI BIÊN CHỮ KÝ SỐ RABIN<br /> Hoàng Thị Mai*<br /> 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<br /> 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<br /> đượ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<br /> 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í<br /> 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<br /> chữ ký cũng không cần đến việc tính ký hiệu Jacobi.<br /> Từ khoá: Chữ ký số, Lược đồ chữ ký số, Lược đồ chữ ký số Rabin, Lược đồ chữ ký số Rabin-William.<br /> <br /> 1. ĐẶT VẤN ĐỀ<br /> Nghiên cứu phát triển các lược đồ chữ ký số là một trong những nội dung<br /> nghiên cứu khoa học quan trọng và mang tính thời sự của an toàn thông tin. Trong<br /> sự 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 đời<br /> củ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ó<br /> của lý thuyết số.<br /> Sau khi đưa ra sơ đồ hệ mật khóa công khai mang tên mình (hệ mật Rabin) có<br /> độ an toàn đúng bằng độ khó của bài toán phân tích số, năm 1979 M. O. Rabin<br /> (xem [Rabin M. O.]) công bố tiếp một sơ đồ chữ ký số tương ứng với thuật toán<br /> kiểm tra chỉ cần một phép bình phương modulo. Tuy nhiên, để tạo ra được chữ ký<br /> 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ới<br /> sơ đồ chữ ký RSA. Tháng 10 năm 1980 Williams đưa ra một cải biên sơ đồ Ra bin,<br /> viết tắt bởi tên chung của hai ông là RW (xem [Williams H.]). Sơ đồ RW chỉ cần<br /> nhiề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ệt<br /> trên nó đã được đưa vào các chuẩn IEEE năm 2004 và ISO năm 2008 (xem [IEEE<br /> 2004], [ISO/IEC 2008]).<br /> 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ông<br /> cần đến việc tính ký hiệu Jacobi, ký hiệu là RW0. Trong sơ đồ RW, các modulo<br /> đượ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ủa<br /> bà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ểm<br /> 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ý<br /> cũng không cần đến việc tính ký hiệu Jacobi.<br /> 2. SƠ ĐỒ CHỮ KÝ RABIN VÀ CẢI BIÊN CỦA WILLIAMS<br /> 2.1. Sơ đồ chữ ký Rabin<br /> Trong [Rabin M. O.] sơ đồ chữ ký Rabin được trình bày như sau.<br /> 2.1.1. Tham số hệ thống<br /> Số nguyên n = p.q trong đó p, q là hai số nguyên tố khác nhau với<br /> p, q ≡ 3 (mod 4) (1)<br /> và b ∈ℤ∗ .<br /> 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”.<br /> 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<br /> thực chữ ký là (n, b).<br /> Hàm tóm lược, Hash: {0,1}¥ ®{0,1} .<br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 73<br />  Công nghệ thông tin<br /> <br /> Hàm đổi xâu bít sang số nguyên có biểu diễn nhị phân là xâu bít đó,<br /> Code:{0,1}¥ ® ℤ.<br /> 2.1.2. Thuật toán tạo chữ kí<br /> Input: M ∈{0,1}¥ , (n, p, q, b). Trong đó:<br /> M là thông báo cần ký.<br /> (n, p, q, b) là khóa bí mật của người ký.<br /> Output: (s,R) ∈ℤ∗ ´{0,1} là chữ ký của người giữ bộ (n, p, q, b) lên M.<br /> 1. Lấy ngẫu nhiên xâu k bít R.<br /> 2. Tính u = Code(Hash(M||R)).<br /> 3. Giải phương trình<br /> x(x + b) = u (mod n) (2)<br /> Nếu vô nghiệm, quay lại bước 1.<br /> Ngược lại, lấy s là một nghiệm của phương trình (2).<br /> 4. Trả về cặp (s,R).■<br /> 2.1.3. Thuật toán kiểm tra<br /> Input: M, (s,R), (n, b). Trong đó:<br /> M ∈{0,1}¥ là thông báo được ký;<br /> (s,R) là chữ ký lên M;<br /> (n,b) là khóa công khai của người ký.<br /> 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<br /> khai (n,b).<br /> 1. Tính u = Code(Hash(M||R)).<br /> 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<br /> (n,b) khi và chỉ khi s là nghiệm của (2).■<br /> 2.2. Sơ đồ chữ ký Rabin-Williams<br /> Tháng 10 năm 1980 Williams đưa ra một cải biên sơ đồ Rabin, sơ đồ được viết<br /> tắt là RW, bởi tên chung của hai ông (xem [Williams H.]). Sơ đồ RW đã được đưa<br /> vào các chuẩn IEEE năm 2004 và ISO năm 2008 (xem [IEEE 2004], [ISO/IEC<br /> 2008]) có thể được trình bày như sau.<br /> 2.2.1. Tham số hệ thống<br /> Số blum n = p.q thỏa mãn<br /> p ≠ q (mod 8). (3)<br /> và<br /> c = q. (q mod p). (4)<br /> 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<br /> xác thực chữ ký là n.<br /> Hàm tóm lược, Hash: {0,1}¥ ®{0,1} .<br /> Hàm định dạng thông báo f: {0,1} ®ℤ∗ sao cho với mọi H ∈{0,1} thì<br /> f(H) ≡ 12 (mod 16). (5)<br /> 2.2.2. Thuật toán tạo chữ ký<br /> Input: M, (n, p, q, c). Trong đó:<br /> M ∈{0,1}¥ là thông báo cần ký.<br /> (n, p, q, c) là khóa bí mật của người ký.<br /> Output: s ∈ℤ∗ sao cho 0  s < n/2 là chữ ký của người giữ bộ (n, p, q, c) lên M.<br /> 1. u ← f(Hash(M));<br /> <br /> <br /> 74 Hoàng Thị Mai, “Cải biên chữ ký số Rabin.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> 2. if = 1 then v ← u;<br /> else v ← u/2;<br /> 3.j ← v mod p;<br /> 4.j ← v mod q;<br /> 5. j ← (c.(j − j ) + j ) mod n; (6)<br /> 6. s ← min(j, n – j);<br /> 7. return s;■<br /> 2.2.3. Thuật toán kiểm tra<br /> Input: M, s, n. Trong đó:<br /> M ∈{0,1}¥ là thông báo được ký.<br /> s là chữ ký lên M.<br /> n là khóa công khai của người ký.<br /> Output: Accept ∈ {0,1}. Trong đó sự chấp nhận s là chữ ký lên M của người có<br /> khóa công khai n khi và chỉ khi Accept = 1.<br /> 1. if s ∉ 0, then: Accept = 0; goto 5;<br /> 2. u ← f(Hash(M));<br /> 3. v ← s mod n;<br /> 4. if (v ∈ {u, n – u} then Accept ← 1;<br /> else:<br /> v ← 2.v;<br /> if (v ∈ {u, n – u} then Accept ← 1;<br /> else Accept ← 0;<br /> 5. return Accept;■<br /> 3. SƠ ĐỒ RW0<br /> 3.1. Sơ đồ chữ ký RW0<br /> 3.1.1. Tham số hệ thống<br /> Số n = p.q và c giống như trong sơ đồ RW. Ngoài ra, còn cần thêm tham số d<br /> được xác định theo công thức sau:<br /> d = (c.(d − d ) + d ) mod n (7)<br /> với<br /> d = 2 mod p và d = 2 mod q. (8)<br /> Khóa bí mật do người ký giữ là bộ (n, p, q, c, d) và khóa công khai cho các<br /> người xác thực chữ ký là n.<br /> Hàm tóm lược, Hash: {0,1}¥ ®{0,1} .<br /> Hàm định dạng thông báo f: {0,1} ´{0,1} ®ℤ∗ được xác định như sau với mọi<br /> R ∈{0,1} và H ∈{0,1} thì:<br /> f(R,H) = (H) + (Hash(R||H)).2 + (R).2 . (9)<br /> ở trên<br /> k + 2.h