Bài giảng Ứng dụng của nhóm: Các hệ mã công khai - PGS TS Trần Đan Thư

Mật mã hóa khóa công khai là một dạng mật mã hóa cho phép người sử dụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa chung bí mật trước đó. Điều này được thực hiện bằng cách sử dụng một cặp khóa có quan hệ toán học với nhau là khóa công khai và khóa cá nhân (hay khóa bí mật).
Nội dung trích xuất từ tài liệu:
Bài giảng Ứng dụng của nhóm: Các hệ mã công khai - PGS TS Trần Đan Thư Ứ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