Sơ đồ chữ kí RaBin

Phần 1: Giới thiệu
Con người đã sử dụng các hợp đồng dưới dạng điện tử từ hơn 100 năm nay với việc sử dụng mã Morse và điện tín. Vào năm 1889, tòa án tối cao bang New Hampshire (Hoa kỳ) đã phê chuẩn tính hiệu lực của chữ ký điện tử. Tuy nhiên, chỉ với những phát triển của khoa học kỹ thuật gần đây thì chữ ký điện tử mới đi vào cuộc sống một cách rộng rãi
Vào thập kỷ 1980, các công ty và một số cá nhân bắt đầu sử dụng máy fax để truyền đi các tài liệu quan trọng. Mặc dù chữ ký trên các tài liệu này vẫn thể hiện trên giấy nhưng quá trình truyền và nhận chúng hoàn toàn dựa trên tín hiệu điện tử.
Hiện nay, chữ ký điện tử có thể bao hàm các cam kết gửi bằng email, nhập các số định dạng cá nhân (PIN) vào các máy ATM, ký bằng bút điện tử với thiết bị màn hình cảm ứng tại các quầy tính tiền, chấp nhận các điều khoản người dùng (EULA) khi cài đặt phần mềm máy tính, ký các hợp đồng điện tử online…
Chữ ký số là tập con của chữ kí điện tử và chữ ký số khóa công khai dựa trên nền tảng mật mã hóa khóa công khai. Như sơ đồ chữ kí RSA dựa trên hệ mật mã RSA, sơ đồ chữ kí Elgamal dựa trên hệ mã Elgamal… Và sơ đồ chữ kí Rabin cũng không ngoại lệ, nó được dựa trên nên tảng của hệ mật mã công khai Rabin(một trong những ví dụ đầu tiên về lược đồ khoá công khai đã được chứng minh về tính an toàn)


















Phần 2 Sơ đồ chữ kí Rabin
Sơ đồ chữ kí Rabin
Một sơ đồ chữ ký số là bộ 5 ( P, A, K, S, V) thoả mãn các điều kiện sau :
P: là tập hữu hạn các bức điện có thể.(P∊Qn)
A: là tập hữu hạn các chữ ký có thể .(A∊Zn)
K: là tập hữu hạn các khóa, mỗi khóa K(K gồm có 2 phần K=(K’,K’’).
K’=d=(n-p-q+5)/8 là bí mật dùng để kí.
K’’=n là công khai để kiểm thử chữ kí.
n= p.q ,với p và q là 2 số nguyên tố lớn đồng thời p≡q≡3(mod 4)
VớimọiK=(K’,K’’)tồntạimộtthuậttoánkíSigK’(SvàthuậttoánkiểmthửVerK’’( Vđượcxácđịnhnhưsau:
SigK’ (x)=xd mod n
VerK’’(x,y)= đúng ( x≡y2 mod n
Sơ đồ chữ kí Rabin như nêu trên, nhưng để có thể dùng được trong thực tế, muốn tập các văn bản P không hạn chế trong Qn mà có thể ở không gian rộng hơn như trong Zn. Ta phải sử dụng them hàm R để chuyển 1 x(P về một giá trị m gần với 1 thặng dư bậc 2 theo mod n(a là dư bậc modulo p — nghĩa là tồn tại số nguyên k sao cho k2 ≡ a (mod p))
Ta có bổ đề :
Giả sử p và q là các số nguyên tố khác nhau cùng đồng dư với 3 theo mod 4 và n=p.q,
ta có :
Nếu gcd(x,n)=1 thì x(p-1)(q-1)/2≡1 mod n
Nếu x∊Qn thì x(n-p-q+5)/8 mod n là căn bậc 2 của x theo mod n
Nếu x là số nguyên có (x/n)=1 và d=(n-p-q+5)/8 thì :
x khi x∊Qn
x2d mod n = n-x khi x∉Qn
Nếu p≠q mod 8 thì (2/n)=-1 nên khi nhân số nguyên x bất kì với 2 hoặc 2-1 mod n đều đảo ngược kí hiệu Jacobi của x

Sơ đồ chữ kí Rabin sửa đổi:
Với p,q là hai số nguyên tố có tính chất : p≡3 mod 8, q≡7 mod 8 và p.q=n
Xác định cặp khóa K=(K’,K’’) với K’=n, K’’=(p,q), d=(n-p-q+5)/8
A có khóa K=(K’,K’’) sẽ tạo chữ kí trên văn bản x (x∊Zn, x≤(n-6)/16) theo các bước:
Tính m=R(x)=16x+6
Tính kí hiệu Jacobi=(m/n)
Nếu J=1 thì tính S=md mod n
Nếu J=-1 thì S=(m/2)d mod