Mã hóa RSA: Bí mật giữa thanh thiên bạch nhật

#TL;DR

Trước năm 1976, mọi hệ thống mã hóa đều có cùng một lỗi chết người: bạn cần một khóa bí mật, và cả hai bên phải có nó trước khi họ có thể nói chuyện an toàn. Điều đó có nghĩa là người giao hàng, phong bì niêm phong, mã sách chia sẻ trước — không cái nào hoạt động cho một thế giới nơi những người lạ cần trao đổi số thẻ tín dụng qua một mạng công cộng. Diffie và Hellman chứng minh một ý tưởng cách mạng là có thể: hai người có thể đồng ý về một bí mật chia sẻ mà không bao giờ trao đổi một cái. Một năm sau, ba nhà nghiên cứu MIT — Rivest, Shamir, và Adleman — đã xây dựng hệ thống thực tế đầu tiên: RSA. Mẹo là một cửa sập toán học. Nhân hai số nguyên tố khổng lồ là tầm thường. Phân tích kết quả trở lại các số nguyên tố đó là, với mọi mục đích thực tế, không thể. Mọi kết nối HTTPS bạn từng làm đều phụ thuộc vào sự bất đối xứng này.

#Vấn đề phân phối khóa

Mật mã học cổ xưa. Caesar dịch chuyển các chữ cái. Máy Enigma gần như đã thắng một cuộc chiến. Nhưng mọi hệ thống trước những năm 1970 đều chia sẻ một giả định tê liệt: người gửi và người nhận đã có cùng khóa.

Điều này ổn cho các tướng lĩnh với người giao hàng. Đó là thảm họa cho một mạng.

Tưởng tượng ARPANET năm 1975. Bạn muốn gửi một thông điệp được phân loại từ UCLA đến MIT. Bạn mã hóa nó bằng một khóa bí mật. Nhưng làm thế nào MIT có được khóa đó? Bạn không thể gửi nó qua mạng — bất cứ ai nghe sẽ chặn và đọc thông điệp của bạn. Bạn có thể gửi thư, hoặc bay nó ra, nhưng điều đó đánh bại mục đích có một mạng. Và bạn sẽ cần một khóa khác cho mỗi cặp người giao tiếp. Một mạng 100 nút sẽ cần 4.950 khóa duy nhất, mỗi cái được trao đổi trước.

Điều này được gọi là vấn đề phân phối khóa, và các nhà mật mã học đã mắc kẹt với nó hàng thế kỷ. Mọi phương án mã hóa thông minh đều chỉ chuyển vấn đề xung quanh — bạn vẫn cần một kênh an toàn để chia sẻ khóa, và nếu bạn đã có một kênh an toàn, tại sao bạn cần mã hóa?

#Một bài báo đã thay đổi mọi thứ

Tháng 11 năm 1976, Whitfield Diffie và Martin Hellman tại Stanford xuất bản “New Directions in Cryptography” — một trong những bài báo quan trọng nhất trong lịch sử khoa học máy tính.

Tuệ giác của họ là cách mạng: điều gì nếu mã hóa và giải mã sử dụng các khóa khác nhau? Một khóa khóa hộp. Một khóa hoàn toàn khác mở nó. Bạn có thể công bố khóa-khóa cho thế giới — đóng đinh nó lên bảng thông báo, phát sóng nó trên radio — và chỉ người có khóa-mở mới có thể đọc thông điệp.

Họ gọi điều này là mật mã khóa công khai. Khái niệm thanh lịch và chứng minh được là có thể. Nhưng họ không có triển khai hoạt động. Họ đã chứng minh ổ khóa có thể tồn tại. Họ chưa xây một cái.

Thách thức đó — tìm một hàm toán học dễ tính theo một hướng và thực tế không thể đảo ngược — là một lời thách đối với mọi nhà toán học và nhà khoa học máy tính còn sống.

#Một lễ Passover tại MIT

Tại MIT, ba nhà nghiên cứu trẻ nhận mồi.

Ron Rivest là nhà khoa học máy tính. Adi Shamir là nhà toán học. Leonard Adleman là người hoài nghi — một nhà khoa học máy tính lý thuyết mà vai trò tự-mô-tả của ông là phá bất cứ điều gì Rivest và Shamir đưa ra. Mô hình luôn vậy: Rivest đề xuất một phương án, Shamir giúp tinh chỉnh nó, và Adleman tìm ra lỗi. Họ trải qua hàng chục nỗ lực.

Sau đó, tháng 4 năm 1977, Rivest thức khuya sau một seder Passover, uống rượu và suy nghĩ về lý thuyết số. Đến 4 giờ sáng, anh có một hệ thống đầy đủ — toán học, bằng chứng, thuật toán. Anh viết nó ra và đưa cho Adleman sáng hôm sau.

Adleman không thể phá nó. Không ai có thể.

Hệ thống được đặt tên RSA, theo cả ba tác giả. Tên của Rivest và Shamir đứng đầu theo thứ tự bảng chữ cái, nhưng Adleman ban đầu từ chối có tên mình trên đó — ông nghĩ đó “chỉ là một bài báo khoa học máy tính.” Rivest khăng khăng. Nó trở thành một trong những bài báo được trích dẫn nhiều nhất trong lĩnh vực.

#Cửa sập

RSA dựa trên một sự bất đối xứng duy nhất: nhân thì dễ, phân tích thì khó.

Lấy hai số nguyên tố lớn — gọi chúng là p và q. Nhân chúng là tầm thường, ngay cả với một máy tính năm 1977:

p = 61
q = 53
n = p × q = 3233

Giờ quên p và q. Chỉ cho n = 3233, bạn có thể tìm các số nguyên tố gốc không? Với các số nhỏ, chắc chắn. Nhưng khi p và q mỗi cái dài 300 chữ số, n kết quả dài 600 chữ số — và không thuật toán nào được biết có thể phân tích nó trong bất kỳ thời gian hợp lý nào. Không trong một năm. Không trong tuổi thọ của vũ trụ.

Đây là một hàm cửa sập: dễ rơi qua theo một hướng, thực tế không thể leo lại.

Đây là cách RSA biến điều đó thành mã hóa:

Tạo khóa — phần bạn làm một lần:

from math import gcd

# 1. Chọn hai số nguyên tố (nhỏ ở đây — RSA thực dùng số nguyên tố 1024+ bit)
p, q = 61, 53
n = p * q          # 3233 — modulus, một phần của cả hai khóa

# 2. Tính totient Euler: có bao nhiêu số < n nguyên tố cùng nhau với n
phi = (p - 1) * (q - 1)  # 3120

# 3. Chọn một số mũ công khai e, nguyên tố cùng nhau với phi
e = 17  # lựa chọn phổ biến; triển khai thực thường dùng 65537

# 4. Tính số mũ riêng d: nghịch đảo modular của e mod phi
#    tức là, tìm d sao cho (e * d) % phi == 1
d = pow(e, -1, phi)  # 2753

# Khóa công khai:  (e=17, n=3233)   — công bố điều này cho thế giới
# Khóa riêng: (d=2753, n=3233) — bảo vệ điều này với mạng của bạn

Mã hóa — bất cứ ai cũng có thể làm điều này với khóa công khai của bạn:

message = 65  # số chúng ta muốn mã hóa (ví dụ, ASCII 'A')
ciphertext = pow(message, e, n)  # 65^17 mod 3233 = 2790

Giải mã — chỉ bạn có thể làm điều này với khóa riêng của bạn:

plaintext = pow(ciphertext, d, n)  # 2790^2753 mod 3233 = 65

Điều thần kỳ: 65 → 2790 → 65. Khóa công khai xáo trộn thông điệp. Khóa riêng — chưa bao giờ được truyền, chưa bao giờ chia sẻ, chưa bao giờ rời máy của bạn — gỡ xáo trộn nó.

Một kẻ tấn công chặn được 2790 và biết khóa công khai (17, 3233) sẽ cần phân tích 3233 để khôi phục d. Với các số đồ chơi, đó là tầm thường. Với các khóa 2048-bit được dùng hôm nay, nó không thể về mặt tính toán.

#Chữ ký số: Bằng chứng bạn đã viết nó

RSA có một mẹo thứ hai. Nếu mã hóa đi khóa công khai → khóa riêng (bất cứ ai cũng có thể khóa, chỉ bạn có thể mở), thì đảo hướng cho bạn chữ ký số: khóa riêng → khóa công khai (chỉ bạn có thể ký, bất cứ ai cũng có thể xác minh).

# Ký: mã hóa bằng khóa RIÊNG của BẠN
document_hash = 42
signature = pow(document_hash, d, n)  # chỉ bạn có thể tạo điều này

# Xác minh: giải mã bằng khóa CÔNG KHAI của BẠN
verified = pow(signature, e, n)       # bất cứ ai cũng có thể kiểm tra điều này
assert verified == document_hash      # nếu khớp, bạn đã ký nó

Điều này giải quyết một vấn đề cũ như chữ viết: làm thế nào bạn chứng minh một thông điệp không bị giả mạo, và rằng nó thực sự đến từ người nó tuyên bố? Chữ ký số là nền tảng cho cập nhật phần mềm, tài liệu pháp lý, giao dịch tiền điện tử, và mọi commit git bạn từng ký.

#NSA, bằng sáng chế, và cuộc chiến về ai sở hữu toán học

RSA không đến một cách lặng lẽ. NSA — cơ quan tình báo tín hiệu của Mỹ — vô cùng khó chịu. Họ đã xây dựng quyền lực của mình dựa trên giả định rằng mật mã mạnh là độc quyền của chính phủ. Dân thường không được phép có nó.

Năm 1977, một nhân viên NSA viết một lá thư cho IEEE cảnh báo rằng xuất bản nghiên cứu mật mã có thể vi phạm Đạo luật Kiểm soát Xuất khẩu Vũ khí — cùng luật điều chỉnh công nghệ tên lửa. Hàm ý: Rivest, Shamir, và Adleman có thể phải đối mặt với truy tố vì xuất bản một bài báo toán học.

Mối đe dọa không dính — cộng đồng học thuật phản đối mạnh — nhưng nó báo trước hàng thập kỷ xung đột. Vào những năm 1990, Cuộc chiến Mật mã nổ ra khi chính phủ Mỹ cố gắng hạn chế kích thước khóa mà dân thường có thể sử dụng, bắt buộc backdoor (Chip Clipper), và phân loại phần mềm mã hóa là đạn dược. Phil Zimmermann bị điều tra trong ba năm sau khi phát hành PGP (Pretty Good Privacy), sử dụng RSA, như phần mềm miễn phí.

Các nhà mật mã học đã thắng. Chính phủ rút lui. Mã hóa mạnh trở thành hợp pháp cho mọi người. Nhưng cuộc tranh luận — liệu công dân có nên có quyền truy cập vào mã hóa mà chính phủ không thể phá? — chưa bao giờ thực sự kết thúc. Nó vang vọng trong mọi tranh luận về các ứng dụng nhắn tin được mã hóa ngày nay.

#RSA đã làm đúng gì

RSA được xuất bản 49 năm trước. Máy tính nhanh hơn hàng tỷ lần. Và RSA vẫn hoạt động — không phải vì kẻ tấn công không đã thử, mà vì sự bất đối xứng toán học ở cốt lõi của nó thực sự khó:

Vấn đề phân phối khóa được giải quyết — bạn có thể công bố khóa công khai của mình trên một biển quảng cáo, và hệ thống vẫn an toàn. Hai người lạ có thể giao tiếp riêng tư mà không bao giờ gặp nhau. Đây là nền tảng của thương mại internet.
Xác thực, không chỉ bí mật — chữ ký số chứng minh rằng mật mã khóa công khai không chỉ về ẩn thông điệp. Đó là về chứng minh danh tính, xác minh tính toàn vẹn, và xây dựng niềm tin giữa các máy chưa bao giờ gặp.
Phòng thủ theo chiều sâu — RSA không hoạt động một mình trong thực tế. TLS hiện đại sử dụng RSA (hoặc các kế vị đường cong elliptic của nó) để trao đổi một khóa phiên, sau đó chuyển sang mã hóa đối xứng nhanh hơn như AES cho dữ liệu thực tế. Cách tiếp cận phân tầng này có nghĩa là hệ thống xuống cấp một cách duyên dáng nếu bất kỳ thành phần nào yếu đi.
Toán học như cơ sở hạ tầng — trước RSA, mật mã là nghề gián điệp. Sau RSA, nó là khoa học máy tính. Thuật toán biến một nhánh của nghiên cứu quân sự được phân loại thành một kỷ luật công cộng mà bất cứ ai cũng có thể học, cải thiện, và xây dựng trên.

Có một cảnh báo ở chân trời. Bảo mật của RSA dựa trên giả định rằng phân tích các số lớn là không khả thi về mặt tính toán. Máy tính lượng tử, chạy thuật toán Shor, có thể thay đổi điều đó — phân tích một số 2048-bit trong giờ thay vì thiên niên kỷ. Điều đó chưa xảy ra, nhưng cộng đồng mật mã học đã chuẩn bị, thiết kế các thuật toán hậu-lượng-tử không phụ thuộc vào phân tích. Cửa sập đã giữ vững năm mươi năm có thể cần được thay thế — nhưng ý tưởng về mật mã khóa công khai, cuộc cách mạng mà Diffie, Hellman, Rivest, Shamir, và Adleman bắt đầu, là vĩnh viễn.