Chữ ký số RSA

Tạo chữ ký số RSA

Sơ đồ chữ ký
1/. Tạo cặp khóa  (bí mật, công khai)  (a, b) :

     Chọn bí mật số nguyên tố lớn  p, q,  tính   n = p * q,  công khai  n,  đặt  P = A = Zn

     Tính bí mật  f(n) = (p-1).(q-1).

     Chọn khóa công khai  b < f(n), nguyên tố cung nhau với f(n).

     Khóa bí mật  a  là phần tử nghịch đảo của b theo mod  f(n):  a*b º 1 (mod f(n).

     Tập cặp khóa  (bí mật, công khai)  K = {(a, b)/  a, b  Î Zn ,  a*b º 1 (mod f(n))}.

2/.  Ký số: Chữ ký trên  x Î P là  y = Sig k (x) =  x a  (mod  n),   y Î A.  (R1)

3/. Kiểm tra chữ ký:      Verk  (x, y) = đúng   Û   x  º  y b (mod n).                (R2)

Chú ý

     - So sánh giữa sơ đồ chữ ký RSA và sơ đồ mã hóa  RSA ta thấy có sự tương ứng.   

     - Việc ký chẳng qua là mã hoá, việc kiểm thử lại chính là việc giải mã:      

     Việc “ký số”  vào x tương ứng với việc “mã hoá”  tài liệu  x.

     Kiểm thử chữ ký chính là việc giải mã “chữ ký”, để kiểm tra xem tài liệu đã giải mã có đúng là tài liệu trước khi ký không. Thuật toán và khóa kiểm thử  “chữ ký” là công khai, ai cũng có thể kiểm thử chữ ký được.

Ví dụ : Chữ ký trên  x = 2

*Tạo cặp khóa  (bí mật, công khai)  (a, b) :

     Chọn bí mật số nguyên tố  p=3,  q=5,   tính  n = p * q = 3*5 = 15,  công khai n. 

     Đặt  P = A = Zn  = Zn .  Tính bí mật  f(n) = (p-1).(q-1) =  2 * 4 = 8.

     Chọn khóa công khai  b = 3 < f(n), nguyên tố với f(n) = 8. 

     Khóa bí mật a = 3, là phần tử nghịch đảo của b theo mod  f(n):  a*b º 1 (mod f(n)).

* Ký số:      Chữ ký trên  x = 2 Î P là 

    y = Sig k (x) =  x a  (mod  n)=  2 3  (mod  15) =  8,        y Î A. 

* Kiểm tra chữ ký:     Verk  (x, y) = đúng  Û  x  º  y b (mod n) 

                                                                    Û  2  º  8 3 (mod 15).      

Độ an toàn của chữ ký   RSA

     * Bài toán căn bản bảo đảm độ an toàn của Sơ đồ chữ ký  RSA:

     Bài toán tách số nguyên n thành tích của  2 số nguyên tố:   n = p*q

     Vì nếu giải được bài toán này thì có thể tính được khóa mật  a  từ  khóa công khai b  và  phần tử công khai n.

1). Người gửi G gửi tài liệu x cùng chữ ký y đến người nhận N, có 2 cách xử lý:

a).   Ký trước,  Mã hóa sau:

     G  ký trước vào x  bằng chữ ký  y = SigG (x),  sau đó mã hoá  x và y  nhận được 

     z = eG (x, y).   G  gửi  z  cho N.

     Nhận được z,  N  giải mã z để  được x, y.  

     Tiếp theo kiểm tra chữ ký   VerN (x, y) = true  ?

b).   Mã hóa trước, Ký sau:

     G  mã hoá trước  x  bằng  u = eG (x),  sau đó ký vào  u  bằng chữ ký  v = SigG (u).

     G  gửi  (u, v)  cho N.

     Nhận được (u, v),  N giải mã u được  x.  

     Tiếp theo kiểm tra chữ ký   VerN (u, v) = true  ? 

2). Giả sử  H  lấy trộm được thông tin trên đường truyền từ G đến N.

     + Trong trường hợp a,  H lấy được  z.    Trong trường hợp b,   H lấy được  (u, v).

     + Để tấn công  x, trong cả hai trường hợp, H đều phải giải mã thông tin lấy được.    

     + Để tấn công vào chữ ký,  thay bằng chữ ký  (giả mạo),  thì  xảy ra  điều gì  ?

          - Trường hợp a,  để tấn công chữ ký y,  H phải giải mã z,  mới nhận được  y.             

          - Trường hợp b,  để tấn công chữ ký v,  H đã sẵn có v,  H chỉ việc thay  v  bằng v’.

          H thay chữ ký v trên u, bằng chữ ký của H là  v’ = SigH(u),  gửi (u,  v’)  đến N.

          Khi nhận được v’,  N kiểm thử thấy sai, gửi phản hồi lại G. 

          G  có thể chứng minh chữ ký đó là giả mạo. 

          G gửi chữ ký đúng  v  cho N,  nhưng quá trình truyền tin sẽ bị chậm lại.

     + Như vậy trong trường hợp b,   H có thể giả mạo chữ ký mà không cần giải mã.

Vì thế có lời khuyên:  Hãy  ký trước, sau đó mã hoá cả chữ ký.