Mật mã hóa khóa công khai

Tổ hợp khoá bí mật mình với khoá công khai của người khác tạo ra khoá dùng chung chỉ hai người biết.

Mật mã hóa khóa công khai là một dạng mật mã hóa cho phép người sử dụng trao đổi các thông tin mật mà không cần phải trao đổi các khóa chung bí mật trước đó. Điều này được thực hiện bằng cách sử dụng một cặp khóa có quan hệ toán học với nhau là khóa công khai và khóa cá nhân (hay khóa bí mật).

Thuật ngữ mật mã hóa khóa bất đối xứng thường được dùng đồng nghĩa với mật mã hóa khóa công khai mặc dù hai khái niệm không hoàn toàn tương đương. Có những thuật toán mật mã khóa bất đối xứng không có tính chất khóa công khai và bí mật như đề cập ở trên mà cả hai khóa (cho mã hóa và giải mã) đều cần phải giữ bí mật.

Trong mật mã hóa khóa công khai, khóa cá nhân phải được giữ bí mật trong khi khóa công khai được phổ biến công khai. Trong 2 khóa, một dùng để mã hóa và khóa còn lại dùng để giải mã. Điều quan trọng đối với hệ thống là không thể tìm ra khóa bí mật nếu chỉ biết khóa công khai.

Hệ thống mật mã hóa khóa công khai có thể sử dụng với các mục đích:

Mã hóa: giữ bí mật thông tin và chỉ có người có khóa bí mật mới giải mã được.
Tạo chữ ký số: cho phép kiểm tra một văn bản có phải đã được tạo với một khóa bí mật nào đó hay không.
Thỏa thuận khóa: cho phép thiết lập khóa dùng để trao đổi thông tin mật giữa 2 bên.

Thông thường, các kỹ thuật mật mã hóa khóa công khai đòi hỏi khối lượng tính toán nhiều hơn các kỹ thuật mã hóa khóa đối xứng nhưng những lợi điểm mà chúng mang lại khiến cho chúng được áp dụng trong nhiều ứng dụng.

Lịch sử

Trong hầu hết lịch sử mật mã học, khóa dùng trong các quá trình mã hóa và giải mã phải được giữ bí mật và cần được trao đổi bằng một phương pháp an toàn khác (không dùng mật mã) như gặp nhau trực tiếp hay thông qua một người đưa thư tin cậy. Vì vậy quá trình phân phối khóa trong thực tế gặp rất nhiều khó khăn, đặc biệt là khi số lượng người sử dụng rất lớn. Mật mã hóa khóa công khai đã giải quyết được vấn đề này vì nó cho phép người dùng gửi thông tin mật trên đường truyền không an toàn mà không cần thỏa thuận khóa từ trước.

Năm 1874, William Stanley Jevons xuất bản một cuốn sách ^[1] mô tả mối quan hệ giữa các hàm một chiều với mật mã học đồng thời đi sâu vào bài toán phân tích ra thừa số nguyên tố (sử dụng trong thuật toán RSA). Tháng 7 năm 1996, một nhà nghiên cứu^[2] đã bình luận về cuốn sách trên như sau:

Trong cuốn The Principles of Science: A Treatise on Logic and Scientific Method được xuất bản năm 1890^[3], William S. Jevons đã phát hiện nhiều phép toán rất dễ thực hiện theo một chiều nhưng rất khó theo chiều ngược lại. Một ví dụ đã chứng tỏ mã hóa rất dễ dàng trong khi giải mã thì không. Vẫn trong phần nói trên ở chương 7 (Giới thiệu về phép tính ngược) tác giả đề cập đến nguyên lý: ta có thể dễ dàng nhân các số tự nhiên nhưng phân tích kết quả ra thừa số nguyên tố thì không hề đơn giản. Đây chính là nguyên tắc cơ bản của thuật toán mật mã hóa khóa công khai RSA mặc dù tác giả không phải là người phát minh ra mật mã hóa khóa công khai.

Thuật toán mật mã hóa khóa công khai được thiết kế đầu tiên^[4] bởi James H. Ellis, Clifford Cocks, và Malcolm Williamson tại GCHQ (Anh) vào đầu thập kỷ 1970. Thuật toán sau này được phát triển và biết đến dưới tên Diffie-Hellman, và là một trường hợp đặc biệt của RSA. Tuy nhiên những thông tin này chỉ được tiết lộ vào năm 1997.

Năm 1976, Whitfield Diffie và Martin Hellman công bố một hệ thống mật mã hóa khóa bất đối xứng trong đó nêu ra phương pháp trao đổi khóa công khai. Công trình này chịu sự ảnh hưởng từ xuất bản trước đó của Ralph Merkle về phân phối khóa công khai. Trao đổi khóa Diffie-Hellman là phương pháp có thể áp dụng trên thực tế đầu tiên để phân phối khóa bí mật thông qua một kênh thông tin không an toàn. Kỹ thuật thỏa thuận khóa của Merkle có tên là hệ thống câu đố Merkle.

Thuật toán đầu tiên cũng được Rivest, Shamir và Adleman tìm ra vào năm 1977 tại MIT. Công trình này được công bố vào năm 1978 và thuật toán được đặt tên là RSA. RSA sử dụng phép toán tính hàm mũ môđun (môđun được tính bằng tích số của 2 số nguyên tố lớn) để mã hóa và giải mã cũng như tạo chữ ký số. An toàn của thuật toán được đảm bảo với điều kiện là không tồn tại kỹ thuật hiệu quả để phân tích một số rất lớn thành thừa số nguyên tố.

Kể từ thập kỷ 1970, đã có rất nhiều thuật toán mã hóa, tạo chữ ký số, thỏa thuận khóa.. được phát triển. Các thuật toán như ElGamal (mật mã) do Netscape phát triển hay DSA do NSA và NIST cũng dựa trên các bài toán lôgarit rời rạc tương tự như RSA. Vào giữa thập kỷ 1980, Neal Koblitz bắt đầu cho một dòng thuật toán mới: mật mã đường cong elliptic và cũng tạo ra nhiều thuật toán tương tự. Mặc dù cơ sở toán học của dòng thuật toán này phức tạp hơn nhưng lại giúp làm giảm khối lượng tính toán đặc biệt khi khóa có độ dài lớn.

An toàn

Về khía cạnh an toàn, các thuật toán mật mã hóa khóa bất đối xứng cũng không khác nhiều với các thuật toán mã hóa khóa đối xứng. Có những thuật toán được dùng rộng rãi, có thuật toán chủ yếu trên lý thuyết; có thuật toán vẫn được xem là an toàn, có thuật toán đã bị phá vỡ... Cũng cần lưu ý là những thuật toán được dùng rộng rãi không phải lúc nào cũng đảm bảo an toàn. Một số thuật toán có những chứng minh về độ an toàn với những tiêu chuẩn khác nhau. Nhiều chứng minh gắn việc phá vỡ thuật toán với những bài toán nổi tiếng vẫn được cho là không có lời giải trong thời gian đa thức (Xem thêm: Lý thuyết độ phức tạp tính toán). Nhìn chung, chưa có thuật toán nào được chứng minh là an toàn tuyệt đối (như hệ thống mật mã sử dụng một lần). Vì vậy, cũng giống như tất cả các thuật toán mật mã nói chung, các thuật toán mã hóa khóa công khai cần phải được sử dụng một cách thận trọng.

Các ứng dụng

Ứng dụng rõ ràng nhất của mật mã hóa khóa công khai là bảo mật: một văn bản được mã hóa bằng khóa công khai của một người sử dụng thì chỉ có thể giải mã với khóa bí mật của người đó.

Các thuật toán tạo chữ ký số khóa công khai có thể dùng để nhận thực. Một người sử dụng có thể mã hóa văn bản với khóa bí mật của mình. Nếu một người khác có thể giải mã với khóa công khai của người gửi thì có thể tin rằng văn bản thực sự xuất phát từ người gắn với khóa công khai đó.

Các đặc điểm trên còn có ích cho nhiều ứng dụng khác như: tiền điện tử, thỏa thuận khóa...

Những vấn đề đặt ra trong thực tế

Sự tương tự với bưu chính

Để thấy rõ hơn ưu điểm của hệ thống mật mã hóa khóa bất đối xứng ta có thể dùng sự tương tự với hệ thống bưu chính trong ví dụ sau: 2 người (Alice và Bob) trao đổi thông tin mật thông qua hệ thống bưu chính. Alice cần gửi một bức thư có nội dung cần giữ bí mật tới cho Bob và sau đó nhận lại thư trả lời (cũng cần giữ bí mật) từ Bob.

Trong hệ thống mật mã hóa khóa đối xứng, Alice sẽ cho bức thư vào hộp và khóa lại rồi gửi hộp theo đường bưu chính bình thường tới cho Bob. Khi Bob nhận được hộp, anh ta dùng một khóa giống hệt như khóa Alice đã dùng để mở hộp, đọc thông tin và gửi thư trả lời theo cách tương tự. Vấn đề đặt ra là Alice và Bob phải có 2 khóa giống hệt nhau bằng một cách an toàn nào đó từ trước (chẳng hạn như gặp mặt trực tiếp).

Trong hệ thống mật mã hóa khóa bất đối xứng, Bob và Alice có hai khóa khác nhau. Đầu tiên, Alice yêu cầu Bob gửi cho mình khóa (công khai) theo đường bưu chính bình thường và giữ lại khóa bí mật. Khi cần gửi thư, Alice sử dụng khóa nhận được từ Bob để khóa hộp. Khi nhận được hộp đã khóa bằng khóa công khai của mình, Bob có thể mở khóa và đọc thông tin. Để trả lời Alice, Bob cũng thực hiện theo quá trình tương tự với khóa của Alice.

Điều quan trọng nhất ở đây là Bob và Alice không cần phải gửi đi khóa bí mật của mình. Điều này làm giảm nguy cơ một kẻ thứ 3 (chẳng hạn như một nhân viên bưu chính biến chất) làm giả khóa trong quá trình vận chuyển và đọc những thông tin trao đổi giữa 2 người trong tương lai. Thêm vào đó, trong trường hợp Bob do sơ suất làm lộ khóa của mình thì các thông tin do Alice gửi cho người khác vẫn giữ bí mật (vì sử dụng các cặp khóa khác).

Thuật toán: liên kết giữa 2 khóa trong cặp

Không phải tất cả các thuật toán mật mã hóa khóa bất đối xứng đều hoạt động giống nhau nhưng phần lớn đều gồm 2 khóa có quan hệ toán học với nhau: một cho mã hóa và một để giải mã. Để thuật toán đảm bảo an toàn thì không thể tìm được khóa giải mã nếu chỉ biết khóa đã dùng mã hóa. Điều này còn được gọi là mã hóa công khai vì khóa dùng để mã hóa có thể công bố công khai mà không ảnh hưởng đến bí mật của văn bản mã hóa. Trong ví dụ ở trên, khóa công khai có thể là những hướng dẫn đủ để tạo ra khóa với tính chất là một khi đã khóa thì không thể mở được nếu chỉ biết những hướng dẫn đã cho. Các thông tin để mở khóa thì chỉ có người sở hữu mới biết.

Những điểm yếu

Tồn tại khả năng một người nào đó có thể tìm ra được khóa bí mật. Không giống với hệ thống mật mã sử dụng một lần (one-time pad) hoặc tương đương, chưa có thuật toán mã hóa khóa bất đối xứng nào được chứng minh là an toàn trước các tấn công dựa trên bản chất toán học của thuật toán. Khả năng một mối quan hệ nào đó giữa 2 khóa hay điểm yếu của thuật toán dẫn tới cho phép giải mã không cần tới khóa hay chỉ cần khóa mã hóa vẫn chưa được loại trừ. An toàn của các thuật toán này đều dựa trên các ước lượng về khối lượng tính toán để giải các bài toán gắn với chúng. Các ước lượng này lại luôn thay đổi tùy thuộc khả năng của máy tính và các phát hiện toán học mới.

Mặc dù vậy, độ an toàn của các thuật toán mật mã hóa khóa công khai cũng tương đối đảm bảo. Nếu thời gian để phá một mã (bằng phương pháp duyệt toàn bộ) được ước lượng là 1000 năm thì thuật toán này hoàn toàn có thể dùng để mã hóa các thông tin về thẻ tín dụng - Rõ ràng là thời gian phá mã lớn hơn nhiều lần thời gian tồn tại của thẻ (vài năm).

Nhiều điểm yếu của một số thuật toán mật mã hóa khóa bất đối xứng đã được tìm ra trong quá khứ. Thuật toán đóng gói ba lô là một ví dụ. Nó chỉ được xem là không an toàn khi một dạng tấn công không lường trước bị phát hiện. Gần đây, một số dạng tấn công đã đơn giản hóa việc tìm khóa giải mã dựa trên việc đo đạc chính xác thời gian mà một hệ thống phần cứng thực hiện mã hóa. Vì vậy, việc sử dụng mã hóa khóa bất đối xứng không thể đảm bảo an toàn tuyệt đối. Đây là một lĩnh vực đang được tích cực nghiên cứu để tìm ra những dạng tấn công mới.

Một điểm yếu tiềm tàng trong việc sử dụng khóa bất đối xứng là khả năng bị tấn công dạng kẻ tấn công đứng giữa (man in the middle attack): kẻ tấn công lợi dụng việc phân phối khóa công khai để thay đổi khóa công khai. Sau khi đã giả mạo được khóa công khai, kẻ tấn công đứng ở giữa 2 bên để nhận các gói tin, giải mã rồi lại mã hóa với khóa đúng và gửi đến nơi nhận để tránh bị phát hiện. Dạng tấn công kiểu này có thể phòng ngừa bằng các phương pháp trao đổi khóa an toàn nhằm đảm bảo nhận thực người gửi và toàn vẹn thông tin. Một điều cần lưu ý là khi các chính phủ quan tâm đến dạng tấn công này: họ có thể thuyết phục (hay bắt buộc) nhà cung cấp chứng thực số xác nhận một khóa giả mạo và có thể đọc các thông tin mã hóa.

Khối lượng tính toán

Để đạt được độ an toàn tương đương, thuật toán mật mã hóa khóa bất đối xứng đòi hỏi khối lượng tính toán nhiều hơn đáng kể so với thuật toán mật mã hóa khóa đối xứng. Vì thế trong thực tế hai dạng thuật toán này thường được dùng bổ sung cho nhau để đạt hiệu quả cao. Trong mô hình này, một bên tham gia trao đổi thông tin tạo ra một khóa đối xứng dùng cho phiên giao dịch. Khóa này sẽ được trao đổi an toàn thông qua hệ thống mã hóa khóa bất đối xứng. Sau đó 2 bên trao đổi thông tin bí mật bằng hệ thống mã hóa đối xứng trong suốt phiên giao dịch.

Mối quan hệ giữa khóa công khai với thực thể sở hữu khóa

Để có thể đạt được những ưu điểm của hệ thống thì mối quan hệ giữa khóa công khai và thực thể sở hữu khóa phải được đảm bảo chính xác. Vì thế các giao thức thiết lập và kiểm tra mối quan hệ này là đặc biệt quan trọng. Việc gắn một khóa công khai với một định danh người sử dụng thường được thực hiện bởi các giao thức thực hiện hạ tầng khóa công khai (PKI). Các giao thức này cho phép kiểm tra mối quan hệ giữa khóa và người được cho là sở hữu khóa thông qua một bên thứ ba được tin tưởng. Mô hình tổ chức của hệ thống kiểm tra có thể theo phân lớp (các nhà cung cấp chứng thực số - X.509) hoặc theo thống kê (mạng lưới tín nhiệm - PGP, GPG) hoặc theo mô hình tín nhiệm nội bộ (SPKI). Không phụ thuộc vào bản chất của thuật toán hay giao thức, việc đánh giá mối quan hệ giữa khóa và người sở hữu khóa vẫn phải dựa trên những đánh giá chủ quan của bên thứ ba bởi vì khóa là một thực thể toán học còn người sở hữu và mối quan hệ thì không. Hạ tầng khóa công khai chính là các thiết chế để đưa ra những chính sách cho việc đánh giá này.

Các vấn đề liên quan tới thời gian thực

Một khóa công khai nào đó có thể liên quan tới một số lượng lớn và khó xác định người sử dụng. Vì thế sẽ tốn rất nhiều thời gian khi muốn thu hồi hoặc thay thế một khóa vì lý do an ninh. Do vậy, các hệ thống hoạt động trong thời gian thực khi áp dụng mã hóa khóa công khai cần phải hết sức thận trọng. Có ít nhất 4 vấn đề cần quan tâm được đề cập sau đây.

Thẩm quyền thu hồi khóa

Việc thu hồi khóa có tính phá hoại hoặc sai sót sẽ có khả năng gây ra ảnh hưởng nghiêm trọng tới hệ thống. Trường hợp này hoàn toàn có thể xảy ra nếu việc thu hồi khóa có thể được thực hiện bởi chỉ một thực thể. Chúng ta có thể làm giảm nguy cơ này bằng cách thực hiện chính sách thu hồi khóa với sự tham gia của hai thực thể trở lên. Chẳng hạn, một khóa chỉ bị thu hồi khi có sự chấp thuận của cả Alice và Bob. Tuy nhiên, xét về phương diện an ninh thì chính sách này tạo nên điểm yếu cho hệ thống. Kẻ tấn công chỉ cần thực hiện tấn công từ chối dịch vụ (DoS) vào Bob hoặc Alice là có thể làm hệ thống ngừng hoạt động.

Do thực thể có thẩm quyền thu hồi khóa rất quan trọng đối với hệ thống nên các cơ chế thực hiện cần đảm bảo càng nhiều bên tham gia càng tốt để chống lại phá hoại đồng thời lại phải đảm bảo càng ít càng tốt để có thể thực hiện việc thu hồi nhanh chóng.

Phân phối khóa mới

Sau khi một khóa bị thu hồi thì một khóa mới cần được phân phối theo một trình tự định trước.

Giả sử khóa của Carol đã bị thu hồi. Trước khi có khóa mới Carol không thể tham gia trao đổi thông tin mật. Không ai có thể gửi thông tin cho Carol mà không vi phạm an ninh hệ thống và các thông tin từ Carol sẽ bị loại bỏ. Điều này cũng có nghĩa phần của hệ thống do Carol kiểm soát ngừng hoạt động. Trong trường hợp này yêu cầu về an ninh được đặt lên trên yêu cầu về tính sẵn sàng của hệ thống.

Trong hệ thống, người có thẩm quyền tạo khóa mới có thể trùng với người có thẩm quyền thu hồi khóa nhưng không bắt buộc như vậy. Nếu xét về phương diện an ninh thì đây không phải là ý tưởng tốt. Vấn đề nảy sinh là chúng ta cần giảm khoảng thời gian giữa thời điểm thu hồi khóa và thời điểm tạo khóa mới tới mức tối thiểu. Để làm tốt việc này lại đòi hỏi một nơi/một thực thể có đủ 2 thẩm quyền nêu trên. Vấn đề là chúng ta phải cân bằng giữa yêu cầu về an ninh và yêu cầu về tính sẵn sàng của hệ thống.

Thông báo thông tin về thu hồi khóa

Thông báo về một khóa nào đó bị thu hồi cần đến được tất cả những người đang sử dụng nó trong thời gian ngắn nhất có thể.

Đối với hệ thống phân phối người ta có 2 cách đưa các thông tin thu hồi khóa đến người dùng: thông tin được đẩy (push) từ điểm trung tâm tới người dùng hoặc người dùng lấy (pull) thông tin từ trung tâm.

Đẩy thông tin từ trung tâm là cách đơn giản nhất để gửi thông tin tới toàn thể người sử dụng. Tuy nhiên không thể đảm bảo là thông tin thực sự tới được đích và đối với một hệ thống lớn thì khả năng gửi thành công tới tất cả người dùng là thấp. Thêm vào đó, thời gian hoàn thành truyền tin sẽ là khá lớn và trong suốt quá trình này thì hệ thống có thể bị lợi dụng. Vì vậy, phương pháp này không đảm bảo an toàn cũng như không tin cậy.

Phương pháp thứ hai người sử dụng lấy thông tin về khóa từ trung tâm trước mỗi lần sử dụng. Điểm yếu của phương pháp này là người sử dụng sẽ bị chặn nếu không kết nối được với trung tâm. Ở đây chúng ta lại thấy một lần nữa mối liên hệ trái chiều giữa an ninh và tính sẵn sàng: càng nhiều server (tăng độ tin cậy) thì thời gian cửa sổ càng lớn (độ an toàn giảm).

Ngoài ra còn một phương án nữa là cung cấp các chứng thực có thời hạn. Việc xác định thời gian sống của mỗi chứng thực sẽ là sự cân bằng giữa yêu cầu an toàn và tính sẵn sàng của hệ thống và người dùng.

Các biện pháp tiến hành khi lộ khóa

Hầu hết các trường hợp thu hồi khóa xảy ra khi có sự kiện nào đó chứng tỏ khóa bí mật đã bị lộ. Ta gọi thời điểm xảy ra sự kiện đó là T.

Điều này dẫn tới 2 hệ quả: Các văn bản mã hóa với khóa công khai sau thời điểm T không còn được xem là bí mật; và các chữ ký số thực hiện với khóa bí mật sau thời điểm T không còn được xem là thật nếu không có những tìm hiểu kỹ lưỡng các sự kiện để tìm ra nơi thực hiện chữ ký.

Nếu nguyên nhân của việc lộ bí mật là lỗi hệ thống thì cần tiến hành ngay lập tức chiến lược phục hồi. Chiến lược này sẽ xác định người có quyền thu hồi khóa, cách thức truyền thông tin tới người dùng, cách thức xử lý các văn bản mã hóa với khóa bị lộ sau thời điểm T. Quy trình phục hồi có thể rất phức tạp và trong lúc tiến hành thì hệ thống rất dễ bị tấn công từ chối dịch vụ (DoS).

Một số ví dụ

Một số thuật toán mã hóa khóa công khai được đánh giá cao:

Trao đổi khóa Diffie-Hellman
DSS (Tiêu chuẩn chữ ký số)
ElGamal
Các kỹ thuật Mã hóa đường cong elliptic
Các kỹ thuật Thỏa thuật khóa chứng thực bằng mật khẩu
Hệ thống mật mã Paillier
Thuật toán mã hóa RSA (PKCS)

Một số thuật toán không được đánh giá cao:

Merkle-Hellman (sử dụng bài toán cái balô)

Một số ví dụ về giao thức sử dụng mã hóa khóa công khai:

GPG thực hiện giao thức OpenPGP
IKE
Pretty Good Privacy
SSH
Secure Socket Layer tiêu chuẩn IETF -- TLS
SILC

Tham khảo

^ Jevons, William Stanley, The Principles of Science: A Treatise on Logic and Scientific Method, Macmillan & Co., London, 1874, 2nd ed. 1877, 3rd ed. 1879. Reprinted with a foreword by Ernst Nagel, Dover Publications, New York, NY, 1958.
^ Solomon W. Golomb, On Factoring Jevons' Number, CRYPTOLOGIA 243 (July 1996).
^ Năm xuất bản trong lời bình luận này không chính xác.
^ The NSA has also claimed to have invented public-key cryptography, in the 1960s; however, there is currently (as of 2004) little supporting public evidence for this claim [1].

Xem thêm

Liên kết ngoài

An account of how GCHQ kept their invention of PKE secret until 1997

[1] Jevons, William Stanley, The Principles of Science: A Treatise on Logic and Scientific Method, Macmillan & Co., London, 1874, 2nd ed. 1877, 3rd ed. 1879. Reprinted with a foreword by Ernst Nagel, Dover Publications, New York, NY, 1958.

[2] Solomon W. Golomb, On Factoring Jevons' Number, CRYPTOLOGIA 243 (July 1996).

[3] Năm xuất bản trong lời bình luận này không chính xác.

[4] The NSA has also claimed to have invented public-key cryptography, in the 1960s; however, there is currently (as of 2004) little supporting public evidence for this claim [1].

[1]

[2]

[3]

[4]