Ứ
Ứng d
ng dụ
ụng c
ng củ
ủa nh
a nhó
óm:
m:
C
Cá
ác h
c hệ
ệmã công khai
mã công khai
(Ph
(Phụ
ụl
lụ
ục B
c Bà
ài gi
i giả
ảng 3)
ng 3)
PGS TS Tr
PGS TS Trầ
ần
n Đ
Đan Th
an Thư
ư
tdthu@fit.hcmus.edu.vn
tdthu@fit.hcmus.edu.vn
2
2
Nh
Nhờ
ờh
hệ
ệqu
quả
ả đ
đị
ịnh lý Lagrange
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.
3
3
Nh
Nhờ
ờ đ
đị
ịnh lý Euler
nh lý Euler
Giảsửnnguyên ≥ 2.
Đặt
ϕ
(n) là sốcác sốksao cho: 1
≤
k
≤
n, (k, n)=1.
Ta có: x
ϕ
(n) =
⎯
1vớ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) ≠1thì phương trình (*) có
đúng hay không? Định lý RSA
4
4
Đ
Đị
ịnh lý
nh lý
(
(R
Rivest,
ivest, S
Shamir,
hamir, A
Adleman (
dleman (RSA
RSA): công b
): công bố
ố1978; Clifford Cocks: công b
1978; Clifford Cocks: công bố
ố1973)
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 nbằ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ã…