Xem mẫu
- Ứng dụng của nhóm:
Các hệ mã công khai
(Phụ lục Bài giảng 3)
PGS TS Trần Đan Thư
tdthu@fit.hcmus.edu.vn
- Nhờ hệ quả định lý Lagrange
Nhóm G cấp n, ta có xn = e, ∀x∈G.
Từ đó suy ra: xkn+1 = x, ∀x∈G.
Tìm E và D sao cho: E.D = kn+1.
Ta có: ( xE )D = x, ∀x∈G.
E, D ∈ nhóm U(Zn) và D = E-1.
Xét ví dụ:
G là nhóm cộng ( ℤ35, +);
G là nhóm nhân (ℤ37* , .) (chú ý 37 nguyên tố).
Thảo luận chi tiết: Xem trình bày trên bảng. 2
- Nhờ định lý Euler
Giả sử n nguyên ≥ 2.
Đặt ϕ(n) là số các số k sao cho: 1 ≤ k ≤ n, (k, n)=1.
Ta có: xϕ(n) =⎯ 1 với mọi x =⎯ m ∈ ℤn ; (m, n)=1.
Suy ra: xkϕ(n)+1 = x (*)
Tìm E và D sao cho: E.D = kϕ(n)+1.
E, D ∈ nhóm U(Zϕ(n)) và D = E-1.
Tuy nhiên nếu (m, n) ≠ 1 thì phương trình (*) có
đúng hay không?
Định lý RSA
3
- Định lý
(Rivest, Shamir, Adleman (RSA): công bố 1978; Clifford Cocks: công bố 1973)
Giả sử n = pq với p, q nguyên tố và p ≠ q.
Ta luôn có: xkϕ(n)+1 = x với mọi x∈ ℤn.
Ghi chú:
• Như vậy không cần điều kiện x =⎯ m ∈ ℤn ; (m, n)=1.
• Định lý cũng mở rộng cho trường hợp n bằng tích các số nguyên tố
đôi một phân biệt.
• Nếu chọn E, D ∈ nhóm U(ℤ ϕ(n)) và D = E-1, thì ta có
(xE) D = x với mọi x∈ ℤn.
Xem trình bày trên bảng
• Ví dụ với n = 33 và n=35;
• Ví dụ với n = 63 (không thỏa điều kiện);
• Giới thiệu và thảo luận về phần công bố hay dấu đi của hệ mã…
4
nguon tai.lieu . vn
