Mã hóa RSA¶

Estimated time to read: 4 minutes

December 17, 2020 · ~5 minutes

Thông tin¶

Trong mật mã học, RSA¹ là một thuật toán mật mã hóa khóa công khai. Đây là thuật toán đầu tiên phù hợp với việc tạo ra chữ ký điện tử đồng thời với việc mã hóa. Nó đánh dấu một sự tiến bộ vượt bậc của lĩnh vực mật mã học trong việc sử dụng khóa công cộng. RSA đang được sử dụng phổ biến trong thương mại điện tử và được cho là đảm bảo an toàn với điều kiện độ dài khóa đủ lớn.

RSA được xây dựng dựa trên lý thuyết số. Bằng việc dựa trên sự phân tích một số là hợp số lớn thành tích 2 số nguyên tố lớn.

Lý thuyết cơ bản toán học trong RSA¶

Mô tả sơ lược lý thuyết¶

Để học tốt RSA, chúng ta cần phải biết một vài lý thuyết số về đồng dư thức, module, số nguyên tố, hàm Euler, ...

Quá trình tạo khóa và giải mã¶

Quá trình tạo khóa¶

Bước 1: Chọn 2 số nguyên tố lớn \(p\) và \(q\) sao cho \(p \ne q\)

Bước 2: Tính \(n=pq\)

Bước 3: Tính giá trị của hàm Euler: \(\phi(n) = \big(p - 1\big)\big(q-1\big)\)

Bước 4: Chọn một số tự nhiên \(e\) sao cho \(\begin{cases} 1<e<\phi(n) \\ \big(e, \phi(n)\big) = 1 \end{cases}\)

Bước 5: Tính \(d\) sao cho \(de \equiv 1 \ \big(mod \ \phi(n) \big)\)

Quá trình mã hóa¶

Giả sử An là người nhận thông điệp bí mật, chỉ An biết khóa bí mật \(\big\{d, n\big\}\) và mọi người có thể biết khóa công khai \(\big\{e, n\big\}\). Nếu người gửi gửi một thông điệp \(m\) cần được giữ bí mật cho An, hãy chọn khóa công khai của An \(\big\{e, n\big\}\) và sau đó tính \(c = m^e \ mod \ n\) rồi gửi đến cho An.

Quá trình giải mã¶

Sau khi nhận được \(c\), An sẽ tính toán theo khóa bí mật mà cô ấy có bằng cách tính \(m = c^d \ mod \ n\). Kết quả là thông điệp sẽ được gửi bởi người gửi.

Tham khảo thêm¶

Xem thêm số nguyên tố

Xem thêm hàm Euler

Xem thêm định lý số dư Trung Hoa

Xem thêm đồng dư thức

Comments