Kiến thức nền

Liên quan

Bản thiết kế · 2.154 từ · 9 phút đọc

Diffie-Hellman: Trao đổi khóa đã làm RSA có thể

Trước khi Rivest, Shamir, và Adleman xây ổ khóa, Whitfield Diffie và Martin Hellman đã chứng minh ổ khóa có thể tồn tại. Bài báo năm 1976 của họ là nơi mật mã khóa công khai thực sự bắt đầu.

Mục lục
  1. TL;DR
  2. Vấn đề: Hai người lạ, một bí mật
  3. Phép loại suy sơn chia sẻ
  4. Toán học
  5. Tại sao logarithm rời rạc khó
  6. Diffie-Hellman không phải RSA
  7. Mẹo “phù du”: Forward Secrecy
  8. Diffie-Hellman đường cong Elliptic
  9. Điều duy nhất Diffie-Hellman không thể làm
  10. Điều Diffie-Hellman thực sự chứng minh

#TL;DR

Tháng 11 năm 1976, Whitfield Diffie và Martin Hellman xuất bản “New Directions in Cryptography” — bài báo chứng minh rằng hai người lạ có thể đồng ý về một bí mật chia sẻ qua một kênh công khai mà không bao giờ gặp nhau, và không có kẻ tấn công nào thấy mọi thông điệp có thể học được bí mật đó. Một năm sau, Rivest, Shamir, và Adleman sẽ xuất bản RSA — hệ thống mã hóa khóa công khai thực tế đầu tiên. Nhưng chính Diffie và Hellman đã cho thấy ý tưởng có thể, và giao thức trao đổi khóa của họ vẫn là nguyên thủy mà TLS, SSH, và Signal sử dụng để thiết lập khóa phiên. Năm mươi năm sau, thuật toán trong bài báo đã được nâng cấp để chạy trên đường cong elliptic, nhưng mẹo vẫn vậy.

#Vấn đề: Hai người lạ, một bí mật

Giả sử bạn và tôi muốn trao đổi các thông điệp được mã hóa. Chúng ta cần một khóa chia sẻ — một chuỗi byte mà cả hai chúng ta đều biết và không ai khác biết. Mã hóa đối xứng, loại duy nhất tồn tại trước 1976, giả định khóa này đã tồn tại.

Làm thế nào chúng ta có nó?

Trước Diffie-Hellman, có hai câu trả lời:

  1. Chúng ta gặp trực tiếp và trao đổi khóa trên một tờ giấy, một USB, hay một phiếu đục lỗ.
  2. Chúng ta tin tưởng một người giao hàng — thường là một chính phủ — giao khóa thay mặt chúng ta.

Không cách nào mở rộng được. Nếu một ngân hàng muốn trao đổi thông điệp được mã hóa với một triệu khách hàng, nó không thể gửi một triệu phong bì. Nếu hai nhà nghiên cứu ARPANET cần giao tiếp riêng tư, họ không thể bay đến các tổ chức của nhau trước. Vấn đề phân phối khóa là trở ngại cơ bản với mật mã ở quy mô mạng, và trong hầu hết thế kỷ 20, các nhà mật mã học coi đó là điều kiện tiên quyết, không phải thứ bạn có thể giải bằng toán học.

Diffie và Hellman đã giải nó bằng toán học.

#Phép loại suy sơn chia sẻ

Trước các phương trình, một mẹo giải thích chuẩn: tưởng tượng bạn và tôi mỗi người có một lon sơn giống hệt. Chúng ta muốn đồng ý về một màu chia sẻ, chỉ sử dụng một kênh công khai — bất kỳ lô sơn nào chúng ta gửi đều qua một kho nơi một người nghe lén có thể nhìn trộm.

Đây là những gì chúng ta làm:

  1. Chúng ta công khai đồng ý về một màu khởi đầu — giả sử vàng. Mọi người trên thế giới biết chúng ta bắt đầu với vàng.
  2. Tôi bí mật chọn một màu — xanh lam. Tôi trộn vàng + xanh lam, tạo ra xanh lục. Tôi gửi lon xanh lục cho bạn.
  3. Bạn bí mật chọn một màu — đỏ. Bạn trộn vàng + đỏ, tạo ra cam. Bạn gửi lon cam cho tôi.
  4. Tôi nhận lon cam của bạn. Tôi trộn vào xanh lam bí mật của tôi, tạo ra (cam + xanh lam) = nâu.
  5. Bạn nhận lon xanh lục của tôi. Bạn trộn vào đỏ bí mật của bạn, tạo ra (xanh lục + đỏ) = nâu.

Cả hai chúng ta đều có nâu. Người nghe lén trong kho thấy vàng, xanh lục, và cam — nhưng tổ hợp tạo ra nâu yêu cầu ít nhất một trong các màu bí mật, mà họ không bao giờ thấy.

Mẹo dựa vào hai tính chất của trộn sơn:

  • Trộn dễ — cho hai màu, bạn có thể trộn chúng trong vài giây.
  • Tách khó — cho một màu đã trộn, xác định các thành phần gốc về cơ bản là không thể.

Đó là một hàm một chiều. Tuệ giác của Diffie và Hellman là lũy thừa modular có cùng tính chất, và bạn có thể xây một giao thức thực trên nó.

#Toán học

Diffie-Hellman thay “sơn” bằng các số modulo một số nguyên tố lớn.

Tham số công khai (mọi người đều biết):
  p = một số nguyên tố lớn
  g = một generator của nhóm nhân mod p  (trong thực tế, g=2 hoặc g=5)

Bí mật của Alice:  a (số ngẫu nhiên, giữ riêng tư)
Bí mật của Bob:    b (số ngẫu nhiên, giữ riêng tư)

Alice gửi:     A = g^a mod p
Bob gửi:       B = g^b mod p

Alice tính:    s = B^a mod p  =  (g^b)^a mod p  =  g^(ab) mod p
Bob tính:      s = A^b mod p  =  (g^a)^b mod p  =  g^(ab) mod p

Cả hai đều có s. Một kẻ tấn công có p, g, A, B — nhưng không có a hay b.

Bí mật chia sẻ là g^(ab) mod p. Cả Alice và Bob tính nó từ giá trị công khai của bên kia nâng lên số mũ riêng tư của họ. Họ đến cùng một số vì lũy thừa modular là giao hoán trong số mũ: (g^a)^b = (g^b)^a = g^(ab).

p = 23     # số nguyên tố đồ chơi — Diffie-Hellman thực dùng số nguyên tố 2048+ bit
g = 5

# Alice chọn một bí mật
a = 6
A = pow(g, a, p)  # 5^6 mod 23 = 8

# Bob chọn một bí mật
b = 15
B = pow(g, b, p)  # 5^15 mod 23 = 19

# Kênh công khai: Alice → Bob gửi A=8; Bob → Alice gửi B=19

# Alice tính bí mật chia sẻ
s_alice = pow(B, a, p)  # 19^6 mod 23 = 2

# Bob tính bí mật chia sẻ
s_bob = pow(A, b, p)    # 8^15 mod 23 = 2

assert s_alice == s_bob == 2

Người nghe lén thấy p=23, g=5, A=8, B=19. Để tìm bí mật chia sẻ, họ cần hoặc a riêng tư của Alice hoặc b riêng tư của Bob. Khôi phục a từ A = g^a mod p được gọi là vấn đề logarithm rời rạc — và đó là độ khó làm cho phương án an toàn.

#Tại sao logarithm rời rạc khó

Tính g^a mod p cho a, g, và p thì nhanh — vài mili giây ngay cả cho các số 2048-bit, vì lũy-thừa-bằng-bình-phương cho phép bạn làm điều đó trong khoảng log(a) phép nhân.

Đi ngược lại — cho g^a mod p, khôi phục a — yêu cầu giải vấn đề logarithm rời rạc, và không có thuật toán nào biết làm điều đó một cách hiệu quả trên máy tính cổ điển.

Các thuật toán tốt nhất cho các trường nguyên tố tổng quát nằm trong họ sàng trường số tổng quát, và thời gian chạy của chúng tăng dưới-mũ với kích thước của p. Cho một số nguyên tố 2048-bit, chi phí tính toán tương đương với phân tích một khóa RSA 2048-bit — vượt xa khả năng của bất kỳ hệ thống nào biết đến.

Logarithm rời rạc và phân tích số nguyên không phải cùng vấn đề, nhưng cả hai đều trong cùng họ mật mã: các vấn đề được tin là khó cổ điển nhưng rơi vào máy tính lượng tử chạy thuật toán Shor. Điểm yếu chung đó là lý do sự chuyển tiếp hậu-lượng-tử ảnh hưởng đến cả RSA và Diffie-Hellman cổ điển cùng lúc.

#Diffie-Hellman không phải RSA

Một điểm tinh tế gây bẫy mọi người: Diffie-Hellman không mã hóa bất cứ điều gì. Nó là một giao thức thỏa thuận khóa — kết thúc của nó, Alice và Bob chia sẻ một bí mật. Họ làm gì với bí mật đó là một câu hỏi riêng.

Trong thực tế, bí mật chia sẻ được đưa vào một hàm dẫn xuất khóa (như HKDF) để tạo ra một hay nhiều khóa đối xứng, và các khóa đó được dùng cho thứ gì đó như AES-GCM để mã hóa cuộc trò chuyện thực tế.

RSA, ngược lại, có thể mã hóa (bạn có thể mã hóa dữ liệu bằng khóa công khai của ai đó) và cũng ký (bạn có thể ký dữ liệu bằng khóa riêng của bạn). RSA làm nhiều hơn. Diffie-Hellman hẹp hơn: nó được tối ưu cho một công việc thiết lập một khóa đối xứng chia sẻ.

Đây thực sự là lý do Diffie-Hellman đã già đi tốt hơn trong thực tế so với RSA. Các giao thức hiện đại gần như không bao giờ mã hóa RSA dữ liệu cuộc trò chuyện trực tiếp — RSA quá chậm cho mã hóa số lượng lớn, và việc sử dụng RSA cho vận chuyển khóa đã được thay thế bằng thỏa thuận khóa dựa trên Diffie-Hellman. TLS hiện đại làm một bắt tay ECDHE (Diffie-Hellman đường cong elliptic, phù du) để dẫn xuất các khóa phiên, và chỉ dùng RSA cho chữ ký chứng chỉ của server (chứng minh danh tính của server).

#Mẹo “phù du”: Forward Secrecy

Nếu Alice và Bob luôn sử dụng cùng các khóa riêng DH dài-hạn, một kẻ tấn công sau này trộm một trong các khóa đó có thể giải mã mọi cuộc trò chuyện đã ghi lại. Đây được gọi là thất bại forward-secrecy.

Sửa là Diffie-Hellman phù du (DHE hoặc ECDHE). Alice và Bob tạo a và b mới, ngẫu nhiên cho mỗi phiên, loại bỏ chúng ngay sau khi dẫn xuất khóa phiên, và không bao giờ ghi chúng vào đĩa. Nếu một kẻ tấn công sau này trộm các khóa danh tính dài-hạn, họ vẫn không thể giải mã các phiên cũ — a và b phù du đã mất mãi mãi.

TLS hiện đại nhấn mạnh thỏa thuận khóa phù du theo mặc định. “E” trong ECDHE là “ephemeral” và không phải tùy chọn trong TLS 1.3.

#Diffie-Hellman đường cong Elliptic

Diffie-Hellman cổ điển hoạt động trong nhóm nhân của các số nguyên mod một số nguyên tố. Diffie-Hellman đường cong Elliptic (ECDH) làm cùng giao thức chính xác qua nhóm các điểm trên một đường cong elliptic.

Mẹo là trên một đường cong elliptic, vấn đề logarithm rời rạc dường như khó hơn trên mỗi bit. Một khóa ECDH 256-bit cung cấp bảo mật khoảng tương đương với một khóa DH cổ điển 3072-bit. Điều này có nghĩa là các khóa và thông điệp ECDH nhỏ hơn nhiều, vấn đề rất lớn trên các thiết bị di động, hệ thống nhúng, và bất kỳ giao thức nào mà mỗi byte đều quan trọng.

Đường cong cụ thể quan trọng: Curve25519 (được Daniel J. Bernstein thiết kế) là mặc định trên thực tế cho hầu hết các giao thức hiện đại, vì nó nhanh, có các quy tắc triển khai đơn giản, và tránh một số lớp lỗi tinh vi mà các đường cong trước cho phép. Signal, WireGuard, SSH hiện đại, TLS 1.3, và các giao thức dựa trên Noise tất cả đều dùng Curve25519 cho thỏa thuận khóa.

Toán đường cong elliptic là cả một chủ đề và bài RSA điểm qua nó. Điều quan trọng ở đây là giao thức của Diffie-Hellman giống hệt — cùng bắt tay, cùng cấu trúc toán, cùng lập luận bảo mật — chỉ qua một nhóm khác.

#Điều duy nhất Diffie-Hellman không thể làm

Diffie-Hellman thiết lập một bí mật chia sẻ giữa hai bên. Điều nó không thể làm là nói cho bạn biết bạn thiết lập bí mật đó với ai.

Nếu Mallory ngồi ở giữa kết nối, cô ta có thể chạy giao thức Diffie-Hellman hai lần — một lần với Alice, một lần với Bob — và kết thúc bằng việc chia sẻ một khóa khác với mỗi người trong số họ. Alice nghĩ cô đang nói với Bob. Bob nghĩ anh đang nói với Alice. Mallory chuyển tiếp mọi thông điệp giữa họ, giải mã và mã hóa lại khi cô đi, đọc mọi thứ.

Đây là cuộc tấn công người-ở-giữa, và đó là lý do Diffie-Hellman thô không bao giờ được dùng trong thực tế. Bạn cần xác thực — cách nào đó để chứng minh giá trị công khai bạn nhận được thực sự đến từ bên bạn định nói chuyện.

Đây là điều chữ ký số giải quyết. Trong TLS, server trình bày một chứng chỉ được ký bởi một CA đáng tin, client xác minh chữ ký, và sau đó họ chạy Diffie-Hellman với sự tự tin rằng các giá trị công khai là xác thực. Hai nguyên thủy bổ sung cho nhau: Diffie-Hellman thiết lập khóa; chữ ký xác thực các bên.

#Điều Diffie-Hellman thực sự chứng minh

Bài viết RSA gọi bài báo của Diffie-Hellman là “khái niệm thanh lịch và chứng minh được là có thể.” Điều đó bán rẻ những gì xảy ra vào tháng 11 năm 1976. Bài báo:

  • Giới thiệu ý tưởng về mật mã khóa công khai. Trước bài báo này, không có khái niệm học thuật về “mã hóa với các khóa khác nhau cho khóa và mở khóa.” Diffie và Hellman đặt tên cho thứ đó và chứng minh nó nhất quán về mặt toán học.
  • Cho một giao thức hoạt động cho một trong hai vấn đề (thỏa thuận khóa). Họ chưa thể làm mã hóa hay chữ ký trong một nguyên thủy duy nhất — đó là đóng góp của RSA — nhưng họ cho thấy vấn đề phân phối khóa có thể giải được.
  • Làm cho mật mã là một chủ đề công khai-học thuật. Trước 1976, nghiên cứu mật mã nghiêm túc về cơ bản tất cả đều được phân loại. Bài báo Diffie-Hellman là khoảnh khắc lĩnh vực vượt từ chính phủ sang khoa học mở.

Rivest, Shamir, và Adleman sẽ hoàn thành công việc một năm sau với một hệ thống mã hóa khóa công khai đầy đủ. Nhưng họ đang xây dựng trên kết quả của Diffie và Hellman, và các giao thức hiện đại đã quay lại nó: hầu hết khóa phiên của internet công cộng ngày nay đến từ một trao đổi Diffie-Hellman đường cong elliptic, không phải mã hóa RSA. Nguyên thủy đã tồn tại lâu hơn người em họ trẻ hơn, nổi tiếng hơn của nó. Không tệ cho một giao thức chỉ đồng ý về một con số.