Mã nén lecture5 -RSA

5
Khoá mã công khai
6
Các đặctrưng của khoá công khai
Public-Key Characteristics
•Cácthuật toán khoá công khai dùng 2 khoá với các đặc
trưng
– Không có khả năng tính toán để tìm khoá giảimãnếu
chỉ biếtthuật toán và khoá mã
–Cóthể dễ dàng mã hoá hoặcgiảimãmẩu tin nếubiết
khoá tương ứng
–Trongmộtsố sơđồ: một khoá bấtkỳ trong hai khoá có
thể dùng để mã, còn khoá kia dùng để giảimã
7
Khoá mã công khai
8
Các ứng dụng khoá công khai
Public-Key Applications
•Cóthể phân loại ứng dụng thành 3 loại:
–Mã/giải mã – cung cấpbảomật
–Chữ ký điệntử - cung cấpxácthực
–Thỏa thuận khóa
•Mộtsố thuật toán phù hợpvớimọi ứng dụng, còn mộtsố
chuyên dùng cho ứng dụng cụ thể.
9
Sơ đồ mã hóa/giải mã dùng khóa công
khai
Dùng khoá công khai
để mã hóa.
Nhưng dùng khoá bí
mật để giải mã
10
Chữ ký số - Dùng khoá bí mật để ký một thông
báo;dùng khoá công khai để xác minh chữ ký.
11
Thỏa thuận khóa -
Tổ hợp khoá bí mật mình với
khoá bí mật của người khác để tạo ra khoá dùng chung
chỉ hai người biết.
12
Thuật toán RSA
• Được công bố bởi Rivest, Shamir & Adleman tại Học
viện Công nghệ Massachusetts - MIT vào năm 1977.
• Là mã công khai đượcbiết đếnnhiềunhấtvàsử dụng
rộng rãi nhất.
•Thuật toán RSA có hai khóa
: khóa công khai và khóa bí
mật. Khóa công khai được công bố rộng rãi cho mọi
người. Những thông tin được mã hóa bằng khóa công
khai chỉ có thể được giải mã bằng khóa bí mật tương ứng.
13
Khởitạo khoá RSA
•Mỗingườitạomộtcặp khoá công khai – riêng như sau:
•Chọnngẫu nhiên 2 số nguyên tố lớn khác nhau p và q
•Tínhsố làm modulo củahệ thống: N = p.q
–Ta đãbiết ø(N)=(p-1)(q-1)
–Vàcóthể dùng Định lý Trung Hoa để giảmbớt tính toán
•Chọnngẫu nhiên khoá mã e
– Trong đó 1<e<ø(N), gcd(e,ø(N))=1
•Giảiphương trình sau để tìm khoá giảimã d
– e.d=1 mod ø(N) với0≤d≤ ø(N)
• In khoá mã công khai PU={e,N}
•Giữ khoá riêng bí mật PR={d,N} hoặc PR={d,p,q}
14
Sử dụng RSA - RSA Use
• Để mã hoá mẩu tin, ngườigửi:
–Lấy khoá công khai củangườinhậnPU={e,n}
–TínhC = M
e
mod N, trong đó0≤M<N
• Để giải mã hoá bản mã, ngườisở hữunhận:
–Sử dụng khóa riêng PR={d,n} hoặc PR={d,p,q}
–TínhM = C
d
mod n
•Lưuý rằng bản tin M < N, do đó khi cần thì chia nhỏ khốibảnrõ.

Xem chi tiết: Mã nén lecture5 -RSA