Cải biên chữ ký số Rabin - Hoàng Thị Mai

Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 73 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 dung 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 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 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ó 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án kiể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ới sơ đồ 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ần 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 trên nó đã được đưa vào các chuẩn IEEE năm 2004 và ISO năm 2008 (xem [IEEE 2004], [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ông cầ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ủa 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 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. 2. SƠ ĐỒ CHỮ KÝ RABIN VÀ CẢI BIÊN CỦA WILLIAMS 2.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ác thực chữ ký là (n, b). Hàm tóm lược, Hash: {0,1}¥®{0,1}. Công nghệ thông tin Hoàng Thị Mai, “Cải biên chữ ký số Rabin.” 74 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ông khai (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ết tắt là RW, bởi tên chung của hai ông (xem [Williams H.]). Sơ đồ RW đã được đưa vào các chuẩn IEEE năm 2004 và ISO năm 2008 (xem [IEEE 2004], [ISO/IEC 2008]) 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ườ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}®ℤ ∗ sao cho với mọi H ∈{0,1} thì f(H) ≡ 12 (mod 16). (5) 2.2.2. Thuật toán tạo chữ ký Input: M, (n, p, q, c). Trong đó: M ∈{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: s ∈ℤ ∗ sao cho 0  s < n/2 là chữ ký của người giữ bộ (n, p, q, c) lên M. 1. u ← f(Hash(M)); Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 75 2. if = 1 then v ← u; else v ← u/2; 3.j ← v mod p; 4.j ← v mod q; 5. j ← (c.(j − j) + j) mod n; (6) 6. s ← min(j, n – j); 7. return s;■ 2.2.3. Thuật toán kiểm tra Input: M, s, n. Trong đó: M ∈{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ý. Output: Accept ∈ {0,1}. 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. 1. if s ∉0, then: Accept = 0; goto 5; 2. u ← f(Hash(M)); 3. v ← s mod n; 4. if (v ∈ {u, n – u} then Accept ← 1; else: v ← 2.v; if (v ∈ {u, n – u} then Accept ← 1; else Accept ← 0; 5. return Accept;■ 3. SƠ ĐỒ RW0 3.1. Sơ đồ chữ ký RW0 3.1.1. Tham số hệ thống Số n = p.q và c giống như trong sơ đồ RW. Ngoài ra, còn cần thêm tham số d được xác định theo công thức sau: d = (c.(d − d) + d) mod n (7) với d = 2 mod p và d = 2 mod q. (8) 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 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}´{0,1}®ℤ ∗ được xác định như sau với mọi R ∈{0,1} và H ∈{0,1} thì: f(R,H) = (H) + (Hash(R||H)).2 + (R).2. (9) ở trên k + 2.h <logn −8 (10) và (xx x) = x2 + x2 + ⋯ + x. (11) Công nghệ thông tin Hoàng Thị Mai, “Cải biên chữ ký số Rabin.” 76 3.1.2. Thuật toán tạo chữ ký Input: M, (n, p, q, c, d). Trong đó: M ∈{0,1}¥ là thông báo cần ký. (n, p, q, c, d) là khóa bí mật của người ký. Output: (R,s) ∈{0,1}´ℤ ∗ sao cho 0  s < n/2 là chữ ký của người giữ bộ (n, p, q, c, d) lên M. 1. Choosen R randomly in {0,1}; 2. v ← f(R, Hash(M)); 3.s ← v mod p; 4.s ← v mod q; 5. s ← (c.(s − s) + s) mod n; 6. u ← s mod n; 7. if u ∉ {v, n – v} then s ← d.s mod n; 8. s ← min(s, n – s); 9. return (R,s);■ 3.1.3. Thuật toán kiểm tra Input: M, (R, s), n. Trong đó: M ∈{0,1}¥ là thông báo được ký. (R,s) là chữ ký lên M. n là khóa công khai của người ký. Output: Accept ∈ {0,1}. 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. 1. if s ∉0, then: Accept = 0; goto 5; 2. v ← f(R, Hash(M)); 3. u ← s mod n; 4. if u ∈ {v, n – v, 2v, n – 2v} then Accept ← 1; else Accept ← 0; 5. return Accept;■ 3.2. Tính đúng đắn của sơ đồ RW0 Theo sơ đồ RW thì chữ ký s thu được trong thuật toán tạo chữ ký chính là một căn bậc hai nào đó của một trong bốn giá trị ±u hoặc ±u/2 với u = f(Hash(M)), giá trị này được ký hiệu là v (trong bước 2) do đó thuật toán kiểm tra chữ ký là việc kiểm tra điều trên. Trong RW0 thì giá trị s được lựa chọn là một căn bậc hai nào đó của một trong bốn giá trị ±u hoặc ±2u với u = f(R, Hash(M)) và thuật toán kiểm tra tương ứng là chứng thực lại điều này qua bước 4. Như vậy, để chứng tỏ tính đúng đắn của sơ đồ RW0 ta chỉ cần chỉ ra rằng giá trị s tìm được trong thuật toán tạo chữ ký của RW0 đúng như điều mong muốn trên. Để làm điều này, trước hết ta cần nhắc lại một số kết quả liên quan đến định lý phần dư Trung hoa có trong tài liệu [R. Crandall] sau đây. Kết quả 1. Cho n tích của hai số nguyên tố khác nhau p và q. (1.a) Khi đó, với mỗi giá trị x ∈ℤ ∗ được tương ứng duy nhất với cặp (,) ∈ℤ ∗´ℤ ∗ trong đó Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 77 = x mod p và= x mod q. (12) Hơn nữa, theo thuật toán Garner (thuật toán 2.1.7 trang 88) thì x còn tính lại được từ (,) theo công thức sau: x = (q.( mod p).( − ) + ) mod n. (13) Từ thực tế trên, ta có thể viết x = (,). (1.b) Nếu x = (,) và y = (,) thì ta có đẳng thức sau x.y mod n = ( , ).■ (14) Với kết quả trên ta thu được bổ đề sau. Bổ đề 1. Cho số blum n = pq. Với v ∈ℤ ∗ , ký hiệu s = (q.( mod p).( − ) + ) mod n (15) với = mod p và = mod q. (16) Ta có: mod n ∈ {v, n – v} khi và chỉ khi = 1. (17) Chứng minh: Theo công thức (13), (15) và (16) ta có: s = (s,s) = v mod p, v mod q. Áp dụng đẳng thức (14) thu được: s mod n = v mod p, v mod q = v mod p, v mod q = v mod p, v mod q. Như vậy, s mod n ∈ {v, n – v} khi và chỉ khi = hay = = 1. Bổ đề đã được chứng minh.■ Đến đây ta có được định lý sau. Định lý 1. Sơ đồ RW0 là đúng đắn. Chứng minh: Từ c được lấy theo công thức (4) nên giá trị s tìm được tại bước 5 của thuật toán tạo chữ ký theo sơ đồ RW0 chính là giá trị tính theo công thức (15) với s và s lấy theo công thức (16) cho nên theo bổ đề 1 không thỏa mãn điều kiện trong bước 7 của thuật toán này xảy ra khi và chỉ khi = 1. Trong trường hợp này, điều kiện trong bước 4 của thuật toán kiểm tra đã được thỏa mãn. Ngược lại, nếu = –1 thì s = d.s mod n với d được tính theo công thức (7). Theo đẳng thức (14) ta có: d.s mod n = 2 . v mod p, 2 . v mod q = (2v) mod p, (2v) mod q. Lại từ p, q thỏa mãn điều kiện (3) nên = –1 hay = 1 nên bổ đề 1 cho ta điều kiện: Công nghệ thông tin Hoàng Thị Mai, “Cải biên chữ ký số Rabin.” 78 (d. s) mod n ∈ {2v, n – 2v} Điều này có nghĩa giá trị s thu được tại đầu ra của thuật toán sẽ cho sự thỏa mãn điều kiện trong bước 4 của thuật toán kiểm tra. Tóm lại định lý đã được chứng minh.■ 3.3. Tính hiệu quả của sơ đồ RW0 Sự khác biệt về mặt tính toán giữa hai thuật toán tạo chữ ký RW và RW0 là: Đối với RW cần tính giá trị tại bước 2. Đối với RW0 cần tính s mod n tại bước 6 và trong điều kiện u ∉ {v, n – v} thì cần thêm một phép nhân d.s mod n trong bước 7. Điều trên cho ta hệ quả sau. Hệ quả 1. Ký hiệu và lần lượt là thời gian ký theo sơ đồ RW và RW0; và lần lượt là thời gian thực hiện phép tính ký hiệu Jacobi và phép nhân trên ℤ ∗ thì: − = − 2.■ (18) Nhận xét. Trong [Crandall-Pomerance] thì thời gian để tính ký hiệu Jacobi (theo thuật toán 2.3.5 trang 98) là O(lnn) phép toán bít, còn thời gian để thực hiện phép nhân (hoặc bình phương) hai số nguyên không quá n theo phương pháp Karratsuba và Toom-Cook (trang 474) là O(lnn) phép toán bít và việc rút gọn số nguyên x với x <n theo modulo n bằng thuật toán Barrett (trang 36 trong [Hankerson-Menezes-Vasntone]) thì chỉ cần đến 2 phép nhân số nguyên cho nên thời gian tính phép nhân trên ℤ ∗ bằng 3 lần thời gian thực hiện phép nhân hai số nguyên. Mặc dù cho đến nay chưa có một công bố nào cho phép so sánh hai đại lượng t và t một cách chi tiết hơn nhưng chúng ta có thể tin tưởng rằng thuật toán tạo chữ ký RW0 là hiệu quả hơn RW0.■ 4. SƠ ĐỒ R0 4.1. Sơ đồ chữ ký R0 4.1.1. Tham số hệ thống n = p.q với p, q ≡ 3 (mod 4) là hai số nguyên tố khác nhau. b là số tự nhiên nhỏ nhất sao cho = −1. (19) c là giá trị được tính theo công thức sau (tương tự như trong sơ đồ RW) c = q. (q mod p). (20) Ngoài ra, còn cần thêm tham số d được xác định theo công thức sau: d = (c.(d − d) + d) mod n (21) với d = b mod p và d = b mod q. (22) 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 người xác thực chữ ký là (n, b). Hàm tóm lược Hash và hàm định dạng thông báo f giống như của RW0. 4.1.2. Thuật toán tạo chữ ký Thuật toán tạo chữ ký của R0 giống hệt như của RW0, cụ thể là. Input: M, (n, p, q, c, d). Trong đó: Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 79 M ∈{0,1}¥ là thông báo cần ký. (n, p, q, c, d) là khóa bí mật của người ký. Output: (R,s) ∈{0,1}´ℤ ∗ sao cho 0  s < n/2 là chữ ký của người giữ bộ (n, p, q, c, d) lên M. 1. Choosen randomly R in {0,1}; 2. v ← f(R, Hash(M)); 3.s ← v mod p; 4.s ← v mod q; 5. s ← (c.(s − s) + s) mod n; 6. u ← s mod n; 7. if u ∉ {v, n – v} then s ← d.s mod n; 8. s ← min(s, n – s); 9. return (R,s); 4.1.3. Thuật toán kiểm tra Input: M, (R, s), (n, b). Trong đó: M ∈{0,1}¥ là thông báo được ký. (R,s) là chữ ký lên M. (n, b) là khóa công khai của người ký. Output: Accept ∈ {0,1}. 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. 1. if s ∉0, then: Accept = 0; goto 5; 2. v ← f(R, Hash(M)); 3. u ← s mod n; 4. if u ∈ {v, n – v } then: Accept ← 1; goto 5; else: v ← v.b mod n; if u ∈ {v, n – v } then Accept ← 1; else Accept ← 0; 5. return Accept;■ 4.2. So sánh tính hiệu quả của hai sơ đồ chữ ký Rabin và R0 Do việc chứng minh tính đúng đắn của sơ đồ R0 giống hệt như đối với RW0 (chỉ việc thay giá trị 2 bởi tham số b) nên trong phần này chúng ta chỉ cần bàn đến tính hiệu quả của R0 so với sơ đồ Rabin. 4.2.1. So sánh về hai thuật toán tạo chữ ký Đương nhiên, thuật toán tạo chữ ký theo Rabin cần đến tìm được tham số ngẫu nhiên R sao cho phương trình sau đây có nghiệm. x(x + b) = u (mod n) với u = Code(Hash(M||R)). Công nghệ thông tin Hoàng Thị Mai, “Cải biên chữ ký số Rabin.” 80 Biết rằng phương trình bậc hai trên có nghiệm khi và chỉ khi biệt thức của nó D = b+ 4u là thặng dư bậc hai theo modulo n, mà điều này đồng nghĩa với sự thỏa mãn điều kiện sau = = 1. Điều kiện trên chỉ xảy ra với xác suất đúng bằng 0.25 cho nên trung bình thuật toán ký của Rabin cần đến khoảng 4 lần lặp từ bước 1 đến bước 3. Nếu thực hiện việc phát hiện tính vô nghiệm của phương trình (2) trong bước 3 của thuật toán Rabin bởi đoạn giả mã sau: D ← b+ 4u; if = –1 then goto 1; if = –1 then goto 1; thì mỗi lần lặp cần đến từ 1 hoặc 2 (ứng với = 1) phép tính ký hiệu Legendre cho nên số phép tính này trung bình sẽ là 6 cho mỗi lần tạo chữ ký hay tương ứng bằng 3 lần tính ký hiệu Jacobi . Mặt khác, việc tìm một nghiệm của phương trình (2) phải trải qua việc tìm một căn bậc hai của D nên đến đây ta có thể đưa ra kết luận sau. Hệ quả 2. Thời gian thực hiện của thuật toán tạo chữ ký Rabin lâu hơn thời gian tạo chữ ký của R0 ít nhất là 3.■ 4.2.2. So sánh về hai thuật toán kiểm tra chữ ký Việc kiểm tra chữ ký của sơ đồ Rabin là xác định s là nghiệm của phương trình (2), do vậy, chỉ cần đúng một phép tính s(s+b) mod n. Trong khi của sơ đồ R0 ngoài việc thực hiện tính s mod n tại bước 3 còn có thể cần thêm việc tính v.b mod n tại bước 4. Như vậy, thuật toán kiểm tra của R0 nhiều hơn của Rabin việc tính v.b mod n. Bây giờ, chúng ta sẽ phân tích kỹ hơn về thời gian thực hiện của phép toán v.b mod n. Theo phần xác định tham số của R0 thì b là số tự nhiên nhỏ nhất sao cho = −1, theo kết quả do N. Ankeny đưa ra từ năm 1952 (định lý 1.4.5 trang 42 trong [Crandall-Pomerance]) thì giá trị b thỏa mãn b < 3lnn. Như vậy tích v.b chỉ là nhân v với một số “nhỏ”, thêm vào nữa theo bước 1 của thuật toán tạo chữ ký thì v = f(R,H) với f(R.H) được xác định theo công thức (9) nên nếu chọn k đủ nhỏ cho công thức này ta sẽ có v.b <n. Điều trên đồng nghĩa với việc tính v.b mod n đúng bằng việc tính tích v với số nguyên nhỏ b cho nên thời gian này là không đáng kể và ta có được kết luận sau. Hệ quả 3. Thời gian thực hiện của thuật toán kiểm tra chữ ký của sơ đồ Rabin và R0 là xấp xỉ nhau.■ 5. KẾT LUẬN 5.1. Vấn đề hàm định dạng văn bản f Ngay từ năm 1996, khi bàn về độ an toàn thực sự của hệ chữ ký RSA và Rabin trong [Bellare-Rogaway1996] các tác giả đã chỉ ra nguy cơ mất an toàn của các hệ này trong trường hợp hàm định dạng văn bản là tất định. Như một ví dụ cho nhận Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san CNTT, 12 - 2017 81 định trên, năm 2015 Evgeny Sidorov đã công bố kết quả phá được hệ chữ ký số Rabin-Williams với định dạng văn bản theo EMSA2 trong chuẩn IEEE 1363-2004 (xem [Sidorov 2015]). M. Bellare và P. Rogaway cũng đề xuất kiểu định dạng ngẫu nhiên kiểu như công thức (9) và với một định dạng cụ thể cho hệ chữ ký RSA được đưa vào PKCS #1 v2.1 (xem [RSA]) hai ông đã chứng minh được sơ đồ này là an toàn theo mô hình “tiên tri ngẫu nhiên” (ROM-Random Oracle Modem). Chính vì lý do trên nên hai sơ đồ chữ ký RW0 và R0 đề sử dụng kiểu định dạng ngẫu nhiên nêu trên. Để có thể đưa ra một kết quả cụ thể như của M. Bellare và P. Rogaway đối với sơ đồ chữ ký RW0 và R0 cần phải nghiên cứu thêm và đây là một định hướng cho công việc sắp tới của người viết. 5.2. Khả năng mở rộng tập tham số modulo n cho sơ đồ hệ mật và chữ ký Rabin Với sơ đồ R0, người viết đã đưa vào sử dụng được các modulo n là các số blum. Tuy nhiên, một câu hỏi có thể được đặt ra là: “Liệu với modulo RSA bất kỳ có thể xây dựng được hệ chữ ký số kiểu Rabin hay không?”. Vấn đề trên sẽ là một định hướng nghiên cứu tiếp theo của tác giả bài báo. 5.3. Địa chỉ ứng dụng cho dòng chữ ký số Rabin Các sơ đồ chữ ký dòng Rabin có một ưu điểm nổi bật đó là thời gian để kiểm tra chữ ký là nhanh thậm chí là nhanh nhất trong toàn bộ các sơ đồ chữ ký hiện có. Như vậy, địa chỉ thích hợp nhất để sử dụng dòng chữ ký này có thể là: Thứ nhất: Trong các giao dịch “nhiều-một” chẳng hạn những điểm tiếp nhận hồ sơ của dịch vụ hành chính công,... Thứ hai: Trong các hoạt động cần đến việc xác thực như một “nghi thức bắt buộc” chẳng hạn như việc kiểm tra các chứng chỉ số,... TÀI LIỆU THAM KHẢO [1]. [Bellare-Rogaway 1996], M. and Rogaway, P. (1996). “The exact security of digital signatures: How to sign with RSA and Rabin”. Appears in Advances in Cryptology – Eurocrypt 96 Proceedings, Lecture Notes in Computer Science Vol. 1070, U. Maurer ed., Springer-Verlag, 1996. Available from: [2]. [Sidorov 2015] “Breaking the Rabin-Williams digital signature system implementation in the Crypto++ library”, IACR Cryptology ePrint Archive, pp 368, URL: https://eprint.iacr.org/2015/368.pdf [3]. [RSA 2002] RSA Laboratories (14/6/2002), RSA Cryptography Standard PKCS#1 v2.1. [4]. [Rabin M. O. 1978] Rabin, M. O., “Digitalized signatures, Foundations of Secure Computations”, R. Lipton and R. DeMillo editors, Academic Press New York, 1978. [5]. [Williams H. 1980] Williams H. “A modification ofthe RSA public-key encryption procedure (Corresp.)”. Infomation Theory, IEEE Transactions on, 26(6): 726-729, Nov 1980. Công nghệ thông tin Hoàng Thị Mai, “Cải biên chữ ký số Rabin.” 82 [6]. [Crandall-Pomerance 2005] Richard Crandall and Carl Pomerance, “Prime Numbers A Computational Perspective”, (Second Edition 2005) Springer Science+Business Media, Inc. [7]. [Hankerson-Menezes-Vasntone 2004], Darrel Hankerson, Alfred Menezes and Scott Vasntone, “Guide to Elliptic Curve Cryptography”, 2004 Springer- Verlag New York, Inc. [8]. [IEEE 2004] “IEEE Standard for Local and metropolitan area networks”, proved 4 June 2004 American National Standard Institute, Approved 9 February 2004 IEEE-SA Standards Board. [9]. [ISO/IEC 2008] International Standard ISO/IEC 27005 Information technology – Security techniques- InformationSecurity risk management. ABSTRACT AN IMPROVEMENT OF THE RABIN SIGNATURE SCHEME In the paper, an improvement in the RW signature generation algorithm without the need to compute the Jacobi notation, denoted RW0 is presented; Next, due to the RW scheme, the modulo would be reduced by half compared to the Rabin scheme. The second contribution of the article was the introduction of a new Rabin signature scheme, R0. This allows for a negligible increase in comparison to the original scheme, while the cost of the signature generation algorithm does not require the computation of the Jacobi notation. Keywords: Digital Signature, Digital Signature Scheme, Rabin Signature Scheme, Rabin-William Signature Scheme. Nhận bài ngày 16 tháng 8 năm 2017 Hoàn thiện ngày 26 tháng 11 năm 2017 Chấp nhận đăng ngày 28 tháng 11 năm 2017 Địa chỉ: Trường Đại học Thủ đô Hà Nội. * Email: htmai@daihocthudo.edu.vn.