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

Chia sẻ: Cvcxbv Cvcxbv | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

136
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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).

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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