Rate this post
Mật mã RSA do ba nhà toán học người Mỹ Ron Rivest, Adi Shamir and Leonard Adleman đưa ra lần đầu vào năm 1977. RSA là thuật toán mật mã khóa công khai nổi tiếng và được phổ biến rộng rãi cho đến tận ngày nay. Cơ sở của nó là phép lũy thừa trên trường Galoa của các số nguyên theo modulo của số nguyên tố lớn. Phép tính lũy thừa có độ phức tạp O((log n)3) là khá dễ so với độ phức tạp của bài toán ngược lại là bài toán logarit rời rạc. Sự an toàn của RSA dựa trên mức độ khó của bài toán phân tích một số lớn ra thừa số và bài toán logarit rời rạc. Bài toán phân tích n ra thừa số có độ phức tạp là: O(elog n log log n). Còn bài toán logarit rời rạc với modulo p là số nguyên tố có độ phức tạp cỡ:
Các bài viết liên quan:
Nội dung thuật toán RSA
Để cài đặt thuật toán RSA, người ta chia thành ba giai đoạn riêng biệt là: tạo khoá, mã hoá và giải mã.
Tạo khóa
Người dùng tạo cặp khóa công khai/cá nhân:
Chọn 2 số nguyên tố lớn ngẫu nhiên p ≠ q (>120 chữ số thập phân) Tính số N = p × q, số φ(N) = (p – 1) × (q – 1)
Chọn số e ngẫu nhiên 0 < e < φ(N) sao cho: (e, φ(N)) = 1 Tính số d = e-1 mod φ(N) với 0 < d < φ(N)
Để tính số nghịch đảo d ta có thể sử dụng thuật toán Euclid mở rộng
Khóa công khai là cặp: ku = {e,N} Khóa cá nhân là cặp: kr = {d,N}
Các giá trị d, p, q và φ(N) cần được giữ bí mật
Trong khi đó các giá trị e, N được công bố công khai.
Số e thường nhỏ, có thể dùng chung một giá trị e cho nhiều người. Trước kia người ta thường hay chọn e = 3, bây giờ người ta hay chọn e = 65535. Tuy nhiên, số d tính được thì thường là rất lớn.
Xem thêm Xác thực thông điệp(message authentication) là gì?
Mã hóa
Sử dụng khoá công khai đã tạo ra ở trên để mã hoá thông điệp.
Thông điệp cần mã hoá: M ( 0 < M < N );
Người gửi sử dụng khóa công khai của người nhận ku = {e, N} để mã hoá M;
Tính: C = Me mod N, với 0 < C < N.
Để tính giá trị C ta có thể sử dụng thuật toán bình phương và nhân
C chính là bản mã sẽ được gửi đi cho người nhận
Giải mã
Sử dụng khoá cá nhân để giải mã thông điệp.
Thông điệp cần giải mã là C
Người nhận sử dụng khóa cá nhân của mình kr = {d, N} để giải mã C
Tính: M‟ = Cd mod N, với 0 < M‟ < N
Để tính giá trị M’ ta cũng có thể sử dụng thuật toán bình phương và nhân. Nếu quá trình giải mã thành công thì M’chính là bản nguồn M. Thật vậy:
Theo quá trình tạo khoá của thuật toán RSA thì các số d và e là nghịch đảo của nhau theo mod φ(N), tức là: d = e-1 mod φ(N), khi đó tồn tại số nguyên s sao cho: e × d = 1 + s × φ(N), do đó từ điều kiện mã hoá C = Me ta suy ra Cd = (Me)d = Me×d = M1+s×φ(N) = M × (Mφ(N))s ?= M × (1)s mod N = M.
Nếu ta chứng minh được Mφ(N) = 1 mod N thì chuỗi đẳng thức trên sẽ đúng và ta sẽ có điều phải chứng minh. Xét hai trường hợp có thể xảy ra:
Nếu (M, N) = 1 thì theo định lý Euler ta có: Mφ(N) = 1 mod N (đpcm).
Nếu (M, N) ≠ 1 thì vì N = p × q và p, q là hai số nguyên tố và 0 < M < N nên (M, N) = p hoặc (M, N) = q.
Không mất tính tổng quát giả sử (M, N)= p ? p|M ? M = t × p (với t là số nguyên nào đó) và khi đó: (q, M)=1 ? Mφ(q) = mod q (theo định lý Euler) ? Mφ(q) = 1 + c × q với c là số nguyên ? M × Mφ(q) = M × (1 + c × q) = M + t × p × c × q = M + t × c × N = M mod N
? Mφ(q) = 1 mod N.
Từ đây ta có: Mφ(N) = M(q-1)(p-1) = Mφ(q)×(p-1) = 1(p-1) mod N = 1 mod N (đpcm).
Xem thêm Mã hóa ELGAMAL
Cài đặt thuật toán RSA
Sau đây ta xét ví dụ thuật toán RSA với: p = 7, q =17, e = 11. Chúng ta thực hiện các phép tính sau đây:
- Tính cặp khóa cá nhân và công khai.
- Mã hóa thông điệp M = 20 và sau đó giải mã.
- TẠO KHOÁ: N = p × q = 7 × 17 = 119 φ(N) = (7 – 1) × (17 – 1) = 96
Dùng thuật toán Euclid kiểm tra hai số có nguyên tố cùng nhau hay không: (φ(N), e) = (96, 11) = (11, 8) = (8, 3) = (3, 2) = (2, 1) = 1 OK!
Tính d = e-1 mod φ(N) = 11-1 mod 96
yqv–960–11188-813922-261135
Khóa công khai: (e, N) = (11,119) Khóa cá nhân: (d, N) = (35,119)
MÃ HÓA : C = Me mod N = 2011 mod 119
10112011202 = 400 = 4320 × 1 = 201432 = 1849=6420 × 43 = 860=270642 = 4096= 50–1–27 × 50 = 1350 = 41
Như vậy giá trị M = 20 đã được mã hoá thành C = 41
GIẢI MÃ: Cd = 4135
1000114111412 = 1681 = 151 × 41 = 411152 = 225 = -1341 × 15 = 615 = 200(-13)2=169= 50–0502 = 2500 = 1–012 = 1–1–20 × 1= 20
Kết quả giải mã C = 41 nhận được giá trị ban đầu M = 20
Triển khai RSA trên thực tế
An toàn của thuật toán RSA phụ thuộc vào độ khó khăn trong việc tính φ(N) hoặc tính các giá trị p, q – đây là bài toán phân tích N ra thành tích của các thừa số nguyên tố.
Bài toán phân tích N thành các thừa số nguyên tố thực sự là một bài toán khó khăn vì N là một số rất lớn (1024 hoặc 2048 bit) và hơn nữa N có rất ít ước số nguyên tố (hai). Ví dụ khi N là số có 120 chữ số thập phân (400 bit) thì số lượng phép toán cần thiết để phân tích N thành thừa số nguyên tố theo thuật toán Brent – Pollard là 7,7 × 1013, tức là mất khoảng hơn 2 năm thực hiện với một máy tính với tốc độ 1 triệu phép toán trong một giây.
Xem thêm:
Khi N có độ dài 200 chữ số thập phân (670 bit), thời gian tính toán sẽ tăng theo cấp số nhân tới gần 1 triệu năm. Trong thực tế, chúng ta sử dụng N có ít nhất 300 chữ số thập phân (1024 bit). Do đó có thể nói, việc thám mã theo cách này là không tưởng.
Trên thực tế, để tính toán với các số lớn, người ta sử dụng các thư viện hàm có sẵn được xây dựng và tích hợp trong các bộ dịch của các ngôn ngữ lập trình. Tuy nhiên, có thể sử dụng vài kỹ thuật tăng tốc cho các tính toán của thuật toán RSA. Ví dụ, thông thường phép nhân sử dụng O(n2) phép tính bit.
Tuy nhiên, thuật toán Schonhage – Strassen rút gọn số phép tính xuống còn O(n × log n). Khi mã hóa, ta tính C = Me với e nhỏ nên thường nhanh, tuy nhiên khi giải mã, cần tính M = Cd với d lớn nên có thể rất lâu. Ở đây, ta có thể dùng định lý số dư Trung Hoa (Chinese Remainder Theorem) để làm nhanh quá trình. Chẳng hạn, với N = p × q nếu tính trực tiếp theo mod N thì sẽ rất lâu, do đó, ta có thể thay nó bởi các phép tính theo mod p và mod q sẽ nhanh hơn nhiều.
Ví dụ. Cần tính: M = Cd mod N, trong đó N = p × q Ta tính như sau (dễ):
Vp = Cd mod p = Cd mod (p-1) mod p (theo định lý Fermat: Cp-1 =1 mod p) Vq = Cd mod q = Cd mod (p-1) mod q
Tiếp theo ta tính:
Xp = q × (q-1 mod p), Xq = p × (p-1 mod q) (Dùng thuật toán Euclid mở rộng)
Theo định lý số dư Trung Hoa: M = (Vp Xp + Vq Xq) mod N Ví dụ: C = 41, d = 35, N = 119, p = 7 và q = 17 ta có:
V7 = 4135 mod 7 = 4135 mod 6 mod 7 = (-1)5 mod 7 = 6
V17 = 4135 mod 17 = 4135 mod 16 mod 7 = 73 mod 17 = 3
X7 = 17 × (17-1 mod 7) = 17 × 5 = 85
X17 = 7 × (7-1 mod 17) = 7 × 5 = 35
M = (V7 X7 + V17 X17) mod 119 = (6 × 85 + 3 × 35) mod 119 = 20.
Ngoài ra, người ta còn có thể kết hợp định lý số dư Trung Hoa với thuật toán Ganner để tăng tốc tính toán.
Khi sử dụng thuật toán RSA trên thực tế, chúng ta còn phải tìm và kiểm tra các số nguyên tố lớn cho các giá trị p và q. Để tăng tốc tính toán, chúng ta có thể sử dụng bộ lọc Fermat hoặc bộ lọc Miller–Rabin để chọn ra các số nguyên tố với độ chính xác từ 75% đến 95%.
Xem thêm 50 + câu hỏi trắc nghiệm về testing software
Một số kiểu tấn công RSA phổ biến:
- Tính khoá d bằng vét cạn: Biết C = Me mod N. Thử lần lượt các giá trị d: 0 < d < φ(N), sao cho: M = Cd mod N; Số lần thử sẽ là φ(N) ≈ N
> 21000 (quá lớn !!!)
- Tìm φ(N): Biết N, e, C = Me. Muốn tính φ(N) phải tính p và q – đây là bài toán phân tích thừa số có độ phức tạp lớn.
- Tìm d: Biết n, e, C = Me và cả M. Tìm trực tiếp d từ công thức: M = Cd mod N – đây là bài toán logarit rời rạc – độ phức tạp cao.
Xem thêm Mã hóa công khai( public key)
