Dựng nước - Giữ nước
Tin tức:
 
*
Chào Khách. Bạn có thể đăng nhập hoặc đăng ký. 01 Tháng Mười Hai, 2021, 10:29:40 am


Đăng nhập với Tên truy nhập, Mật khẩu và thời gian tự động thoát


Trang: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 »   Xuống
  In  
Tác giả Chủ đề: Mật Mã - Từ cổ điển đến lượng tử  (Đọc 10503 lần)
0 Thành viên và 1 Khách đang xem chủ đề.
Giangtvx
Thượng tá
*
Bài viết: 25400


« Trả lời #140 vào lúc: 07 Tháng Sáu, 2020, 08:57:33 am »


        Vì Heilman không có nhiều kinh phí nên ông không thể chi trả cho việc thuê người bạn cùng chí hướng mới như một nghiên cứu viên. Thay vì thế, Diffie đăng ký như một nghiên cứu sinh. Cùng với nhau, Heilman và Diffie bắt đầu nghiên cứu vấn đề phân phối chìa khóa mã, họ cố gắng không mệt mỏi để tìm ra một cách thức có thể thay thế cho việc chuyên chở chìa khóa mã bằng con người một cách mệt nhọc qua những khoảng cách lớn. Trong quá trình đó, họ đã cộng tác với Ralph Merkle. Merkle là một người tị nạn về trí tuệ, ông di cư đến từ một nhóm nghiên cứu khác mà giáo sư ở đó không đồng cảm với giấc mơ giải quyết vấn đề phân phối chìa khóa mã, một vấn đề được coi là bất khả. Heilman kể:

        Cũng giống như chúng tôi, Ralph sẵn lòng làm một thằng ngốc. Và con đường đạt tới đỉnh cao thông qua sự triển khai nghiên cứu lại từ đầu phải là của kẻ ngốc vì chỉ có ngốc mới kiên trì thử mãi như vậy. Anh có ý tưởng số 1, anh rất phấn khích, và rồi nó thất bại. Sau đó anh lại nảy ra ý tưởng số 2, anh rất hứng khởi, nhưng rồi nó lại thất bại. Rồi anh có ý tưởng số 99, anh lại rất hứng khởi, nhưng nó cũng lại thất bại nốt. Chỉ có kẻ ngốc mới hứng khởi đến ý tưởng thứ 100, nhưng rất có thể phải mất đến 100 ý tưởng thì người ta mới được đền đáp. Trừ phi anh đủ ngốc để tiếp tục hứng khởi, nếu không thì anh làm gì có động cơ, làm gì có năng lượng để đi tiếp. Quả là Chúa ban thưởng cho những thằng ngốc.

        Toàn bộ vấn đề phân phối chìa khóa mã là một tình huống kiểu catch-22 cổ điển[3l Nếu hai người muốn trao đổi thông tin bí mật qua điện thoại, người gửi phải mã hóa nó. Để mã hóa thông tin, người gửi phải sử dụng chìa khóa mã mà bản thân nó cũng lại là bí mật, vì vậy mới nảy sinh vấn đề là làm sao chuyển chìa khóa mã bí mật cho người nhận để truyền đi thông tin bí mật. Tóm lại, trước khi hai người có thể trao đổi một bí mật (một bức thư mã hóa), họ đã phải chia sẻ một bí mật khác (chìa khóa mã).

        Khi xét đến vấn đề phân phối chìa khóa mã, để cho dễ hình dung, ta coi Alice, Bob và Eve, ba nhân vật hư cấu, những người đã trở thành tiêu chuẩn công nghiệp để thảo luận về khoa học mật mã. Trong một tình huống điển hình, Alice muốn gửi một bức thư cho Bob hay ngược lại, còn Eve thì đang cố nghe lén. Nếu Alice muốn gửi các bức thư riêng cho Bob, cô ta sẽ mã hóa từng cái trước khi gửi, mỗi lần sử dụng một chìa khóa mã khác nhau. Alice phải đối mặt với vấn đề phân phối chìa khóa mã vì cô phải chuyển chìa khóa mã cho Bob một cách bí mật, nếu không anh ta sẽ không thể giải mã được bức thư. Một cách để giải quyết vấn đề này là Alice và Bob gặp nhau trực tiếp một tuần một lần và trao đổi đủ số chìa khóa mã cho các bức thư sẽ gửi trong vòng bảy ngày sau đó. Trao đổi chìa khóa mã trực tiếp chắc chắn là an toàn, song lại không thuận tiện, nếu như Alice hoặc Bob bị ốm chẳng hạn, thì hệ thống sẽ bị đổ vỡ. Một cách khác là Alice và Bob thuê người chuyển hộ, như thế sẽ ít an toàn hơn và lại đắt hơn, song ít nhất thì họ cũng ủy thác được phần nào công việc. Dù theo cách nào thì việc phân phối chìa khóa mã là điều không thể tránh khỏi. Trong suốt hai ngàn năm, điều này được xem nhu là một tiên đề của khoa mật mã - tức là một sự thật không phải bàn cãi. Tuy nhiên, có một thí nghiệm tưởng tượng dường như như thách thức tiên đề này.

Hình 63 Martin Heilman.
Logged

Giangtvx
Thượng tá
*
Bài viết: 25400


« Trả lời #141 vào lúc: 07 Tháng Sáu, 2020, 08:58:16 am »


        Hãy tưởng tượng rằng Alice và Bob sống trong cùng một đất nước nơi mà hệ thống bưu điện là hoàn toàn phi đạo đức, những nhân viên bưu điện có thể đọc bất cứ thông tin nào không được bảo đảm. Một hôm, Alice muốn gửi một bức thư rất riêng tư cho Bob. Cô bỏ thư vào một hộp sắt, đóng lại và bảo vệ nó bằng khóa móc và chìa khóa. Cô gửi hộp có khóa móc ở bưu điện và giữ lại chìa khóa. Tuy nhiên, khi cái hộp đến chỗ Bob, anh không thể mở được nó ra vì không có chìa khóa. Alice có tính đến chuyện bỏ chìa khóa vào một cái hộp khác, khóa lại và gửi đến cho Bob, song không có chìa khóa thì Bob cũng không thể mở được chiếc hộp thứ hai và vì vậy không thể lấy được chìa khóa để mở hộp thứ nhất. Chỉ có một cách là Alice đánh một chiếc chìa khóa nữa và đưa trước cho Bob khi họ gặp nhau lúc uống cà phê. Cho đến đây, tôi đã kể lại một câu chuyện cũ chỉ có điều là theo một kịch bản mới. Tránh việc phân phối chìa khóa mã dường như là một điều không thể về mặt logic - chắc chắn rồi, vì nếu Alice muốn khóa thứ gì đó trong hộp mà chỉ có Bob mới mở được thì cô ấy phải đưa cho anh ta một chìa khóa khác. Trao đổi chìa khóa là một phần không thể thiếu trong việc mã hóa - hay là không phải như vậy?

        Bây giờ hãy hình dung một kịch bản sau. Cũng như trước, Alice muốn gửi một bức thư rất riêng tư cho Bob. Một lần nữa, cô lại bỏ thư vào một hộp sắt, khóa nó lại và gửi đến cho Bob. Khi hộp đến nơi, Bob sẽ thêm vào đó một khóa móc của mình và gửi lại cho Alice. Khi Alice nhận được chiếc hộp thì nó rất an toàn vì có cả hai khóa trên đó. Cô mở khóa của mình ra, nhưng giữ nguyên chiếc khóa của Bob để đảm bảo an toàn cho chiếc hộp. Cuối cùng cô gửi chiếc hộp lại cho Bob. Và lúc này có sự khác biệt rất quan trọng: Bob có thể mở được hộp vì nó được bảo đảm an toàn bằng khóa của chính anh, cái khóa mà chỉ mình anh có chìa.

        Hàm ý của câu chuyện nhỏ này là rất lớn. Nó chứng minh rằng một thông tin bí mật có thể trao đổi một cách an toàn giữa hai người mà không cần thiết phải trao đổi chìa khóa mã. Lần đầu tiên chúng ta có được một gợi ý rằng trao đổi chìa khóa mã không phải là một phần tất yếu của khoa mật mã. Chúng ta có thể diễn giải lại câu chuyện này thông qua việc mã hóa. Alice sử dụng chính chìa khóa mã của mình để mã hóa một bức thư gửi cho Bob, đến lượt mình, Bob lại mã hóa nó bằng chìa khóa của mình rồi gửi trả lại. Khi Alice nhận được bức thư được mã hóa hai lần, cô bỏ đi mã hóa của mình và gửi lại cho Bob, và anh này sau đó sẽ giải mã của chính mình và có thể đọc được bức thư.

        Dường như vấn đề phân phối chìa khóa mã đã có thể được giải quyết vì cơ chế mã hóa kép không đòi hỏi phải trao đổi chìa khóa mã. Tuy nhiên, có một trở ngại cơ bản đối với việc thực hiện một hệ thống mà trong đó Alice mã hóa, Bob mã hóa, Alice giải mã, Bob giải mã. vấn đề là ở trình tự tiến hành mã hóa và giải mã. Nói chung, trình tự mã hóa và giải mã là rất quan trọng, và phải tuân thủ quy tắc “vào sau ra trước”. Nói cách khác, bước mã hóa cuối cùng sẽ phải giải mã đầu tiên. Trong kịch bản trên, Bob thực hiện bước mã hóa cuối cùng, vì vậy lẽ ra nó sẽ phải được giải mã trước, song ở đây chính Alice lại là người giải mã trước rồi mới đến Bob. Sự quan trọng của trình tự dễ hình dung nhất khi quan sát những việc chúng ta làm hằng ngày. Buổi sáng chúng ta đi tất vào trước rồi sau đó mới đi giày, và buổi tối, chúng ta cởi giày ra trước rồi mới cởi tất - không thể cởi tất trước khi cởi giày. Chúng ta phải tuân thủ châm ngôn “vào sau ra trước”.

        Đối với một số mật mã rất sơ cấp, như mật mã Ceasar, chúng đơn giản đến mức trình tự không thành vấn đề. Tuy nhiên, trong những năm 1970, dường như bất kỳ dạng mã hóa mạnh nào cũng luôn phải tuân thủ quy tắc “vào sau ra trước”. Nếu một bức thư được mã hóa bằng chìa khóa mã của Alice rồi sau đó bằng chìa khóa mã của Bob thì nó phải được giải mã bằng chìa khóa mã của Bob trước khi được giải mã bằng chìa khóa mã của Alice. Trình tự quan trọng ngay cả đối với mật mã thay thế dùng một bảng chữ cái. Hãy hình dung Alice và Bob đều có chìa khóa mã riêng, như trình bày dưới đây, và chúng ta hãy xem điều gì xảy ra nếu trình tự được thực hiện không đúng. Alice sử dụng chìa khóa mã để mã hóa một bức thư gửi cho Bob, sau đó Bob mã hóa tiếp bằng chìa khóa mã của anh ta; Alice giải mã phần của mình nhờ chìa khóa mã riêng và cuối cùng Bob sử dụng chìa khóa mã của mình để giải mã toàn bộ.

        Chìa khóa mã của Alice

        abcdefghijklmnopqrstuvwxyz
        HFSUGTAKVDEOYJBPNXWCQRIMZL

        Chìa khóa mã của Bob

        abcdefghijklmnopqrstuvwxyz
        CPMGATNOJEFWIQBURYHXSDZKLV

        Thư (Gặp em vào buổi trưa)
        meetmeatnoon

        Mã hóa bằng chìa khóa mã YGGCYGHCJBBJ của Alice

        Mã hóa bằng chìa khóa mã LNNMLNOMEPPE của Bob

        Mã hóa bằng chìa khóa mã ZQQXZQLXKPPK của Alice

        Mã hóa bằng chìa khóa mã wnntwnytxbbx của Bob
Logged

Giangtvx
Thượng tá
*
Bài viết: 25400


« Trả lời #142 vào lúc: 08 Tháng Sáu, 2020, 05:46:24 am »

    
        Kết quả nhận được là vô nghĩa. Tuy nhiên, bạn có thể tự kiểm tra đối với trình tự giải mã ngược lại, cụ thể là Bob giải mã trước Alice, tức là tuân thủ quy tắc “vào sau ra trước”, thì kết quả sẽ lại là bức thư ban đầu. Song nếu trình tự là quan trọng như vậy thì tại sao hệ thống khóa móc lại có kết quả trong giai thoại về các hộp có khóa? Câu trả lời là trình tự không quan trọng với khóa móc. Tôi có thể sử dụng 20 khóa móc vào một hộp và mở chúng theo bất kỳ trình tự nào thì cuối cùng cái hộp cũng sẽ mở ra được. Tiếc thay là hệ thống mã hóa lại nhạy cảm hơn nhiều đối với trình tự.

        Mặc dù cách tiếp cận hộp khóa kép không ứng dụng được cho khoa mật mã trong thế giới thực, song nó vẫn gây cảm hứng cho Diffie và Heilman tìm kiếm một phương pháp thực tế để giải quyết khôn khéo vấn đề phân phối chìa khóa mã. Họ miệt mài hết tháng này đến tháng khác cố gắng tìm ra một giải pháp. Mặc dù mỗi ý tưởng đều kết thúc thất bại, song họ xử sự như những thằng ngốc lý tưởng và hết sức kiên trì. Nghiên cứu của họ tập trung xem xét các hàm số toán học khác nhau. Hàm số là phép toán nào đó biến một số này thành một số khác. Ví dụ, “nhân đôi” là một dạng hàm số, vì nó biến số 3 thành 6, hay số 9 thành 18. Hơn nữa, chúng ta cũng có thể cho rằng tất cả các dạng mã hóa bằng máy tính cũng là các hàm số vì chúng biến một số (văn bản thường) thành một số khác (văn bản mật mã).

        Hầu hết các hàm số toán học được phân loại là các hàm số hai chiều vì chúng dễ thực hiện và dễ làm ngược lại. Ví dụ, “nhân đôi” là một hàm số hai chiều vì dễ dàng nhân đôi một số để tạo thành một số mới, và cũng dễ dàng làm hàm số ngược lại, tức là chuyển số gấp đôi trở về số ban đầu. Chẳng hạn, nếu chúng ta biết kết quả gấp đôi là 26 thì sẽ không khó khăn khi đảo ngược hàm và suy ra số ban đầu là 13. Cách đơn giản nhất để hiểu về khái niệm hàm hai chiều là xét một hành động hằng ngày. Động tác bật công tắc đèn là một hàm số, vì nó biến một bóng đèn bình thường thành một bóng đèn phát sáng. Hàm số này là hai chiều vì nếu một công tắc được bật lên thì cũng dễ dàng tắt nó đi và biến bóng đèn trở về trạng thái ban đầu.

        Tuy nhiên Diffie và Heilman không quan tâm đến các hàm số hai chiều. Họ tập trung sự chú ý của mình đến các hàm số một chiều. Như tên gọi của chúng gợi ý, hàm số một chiều là dễ dàng thực hiện song rất khó để đảo ngược lại. Nói cách khác, hàm số hai chiều là có thể đảo ngược còn hàm một chiều là không thể đảo ngược. Một lần nữa, cách minh họa tốt nhất về hàm một chiều là xét một hành động hằng ngày. Trộn sơn màu vàng và màu xanh da trời để tạo ra sơn màu xanh lá cây là một hàm một chiều, vì rất dễ dàng trộn sơn vào với nhau song lại không thể tách chúng ra khỏi nhau. Một hàm số một chiều khác đó là đánh vỡ một quả trứng, rất dễ làm vỡ trứng song lại không thể biến nó trở lại thành quả trứng nguyên vẹn như ban đầu. Với lý do này, hàm số một chiều đôi khi còn được gọi là các hàm Humpty Dumptyt1.

        Số học môđun hay số học đồng dư, đôi khi còn gọi là số học đồng hồ, là một lĩnh vực toán học rất giàu các hàm số một chiều. Trong số học môđun, các nhà toán học xem xét một nhóm hữu hạn các con số được xếp thành vòng tròn, giống như các số trên mặt đồng hồ. Chẳng hạn, Hình 64 trình bày một đồng hồ với môđun 7 (hay viết tắt là mod 7), chỉ với bảy con số từ 0 đến 6. Để tính 2 + 3, chúng ta bắt đầu từ số 2 và dịch chuyển theo vòng tròn đi ba vị trí sẽ đạt đến số 5, một kết quả giống như số học thông thường. Để tính 2 + 6, chúng ta bắt đầu từ 2 và dịch chuyển đi sáu vị trí, nhưng lần này chúng ta đi quanh vòng tròn và đến vị trí số 1, không giống với kết quả mà chúng ta thu được trong số học thông thường. Kết quả này được biểu thị như sau:

        2 + 3 (mod 7) = 5            và 2 + 6 (mod 7) = 1

Hình 64 Số học môđun được thực hiện trên một tập hợp số hữu hạn, có thể coi như các số trên mặt đồng hồ. Trong trường hợp này, chúng ta có thể tính 6 + 5 theo môđun 7 bằng cách nhìn vào số 6 và dịch chuyển theo vòng tròn đi năm vị trí, ta sẽ nhận được kết quả là 4.

-------------------------
       1. Đây là tên một nhân vật có hình quả trứng trong cuốn truyện nổi tiếng Alice ở thế giới thần kỳ của Lewis Carroll. Để hiểu các hàm một chiều tại sao lại được gọi là các hàm số Humpty Dumpty hãy đọc đoạn thơ sau mà Alice đã đọc để chế nhạo Humpty Dumpty:

        Ngài Humpty Dumpty ngồi trên bức tường
        Ngài Humpty Dumpty bị ngã rất đau
        Tất cả ngựa và quân lỉnh của nhà Vua
        Cũng không đặt được Ngài về chỗ cũ. (ND)

Logged

Giangtvx
Thượng tá
*
Bài viết: 25400


« Trả lời #143 vào lúc: 08 Tháng Sáu, 2020, 05:52:59 am »


        Số học môđun tương đối đơn giản, và trong thực tế chúng ta dùng nó hằng ngày khi nói về thời gian. Nếu hiện tại là 9 giờ, chúng ta có cuộc gặp sau 8 tiếng nữa, chúng ta thường nói là sẽ gặp nhau vào lúc 5 giờ, chứ không nói là 17 giờ. Ở đây chúng ta đã tính nhẩm 9 + 8 theo (mod 12). Hãy tưởng tượng ra mặt đồng hồ, nhìn vào số 9 sau đó dịch chuyển theo vòng tròn 8 vị trí và kết thúc tại 5:

        9 + 8 (mod 12) = 5

        Thay vì nhìn vào đồng hồ, các nhà toán học thường làm tắt việc tính toán các môđun theo cách sau. Trước hết, thực hiện phép tính trong số học thông thường. Sau đó, nếu chúng ta muốn biết kết quả theo (môđun x), chúng ta chia kết quả thông thường cho X và ghi lại số dư. số dư này chính là kết quả theo (mod x). Để tính 11* 9 (mod 13), chúng ta làm như sau:

        11*9 = 99
        99 (mod  13) =  8
        11*9 (mod 13) = 8
       
        Các hàm số thực hiện trong môi trường số học môđun đều có xu hướng hành xử một cách thất thường, vì vậy đôi khi biến chúng thành các hàm số một chiều. Điều này trở nên rõ ràng khi so sánh một hàm số đơn giản trong số học thông thường với cùng hàm số đó trong số học môđun. Trong môi trường thứ nhất, hàm số sẽ là hai chiều và dễ đảo ngược; trong môi trường thứ hai, nó sẽ là một chiều và khó đảo ngược. Chúng ta hãy lấy ví dụ như hàm 3x, chẳng hạn. Tức là lấy một số X rồi nhân 3 với chính nó X lần để đạt được một số mới. Chẳng hạn, nếu X = 2 và chúng ta thực hiện hàm số đó, thì:

        3X = 32 = 3 * 3 = 9.

        Nói cách khác, hàm số này biến số 2 thành số 9. Trong số học thông thường, khi giá trị của X tăng thì kết quả của hàm số cũng tăng. Do đó, nếu chúng ta được cho trước kết quả của hàm thì sẽ khá dễ dàng tính ngược lại và suy ra số ban đầu. Yí dụ, nếu kết quả là 81, chúng ta có thể suy ra X = 4 vì 34 = 81. Nếu chúng ta nhầm lẫn và đoán X = 5 thì có thể tính ra 35 = 243, cho thấy sự lựa chọn của chúng ta về giá trị của X là quá lớn. Sau đó, chúng ta giảm giá trị lựa chọn của X xuống 4, và khi đó sẽ thu được kết quả đúng. Tóm lại, ngay cả khi chúng ta đoán sai, chúng ta vẫn có thể tìm đúng giá trị của X, và nhờ đó mà đảo ngược được hàm số.
Tuy nhiên, trong số học môđun, hàm số này không hành xử một cách hợp lý như vậy. Hãy tưởng tượng rằng người ta cho chúng ta biết giá trị của 3X theo (mod 7) là 1, và yêu cầu tìm giá trị của X. Không giá trị nào lấp ló trong đầu vì chúng ta nhìn chung là không quen với số học môđun. Ta có thể đoán là X = 5 và tính ra kết quả của 35 (mod 7). Kết quả tính được là 5, quá lớn, vì kết quả mong đợi là 1. Chúng ta thử giảm giá trị của X và thử lần nữa. Nhưng làm như vậy là sai hướng vì giá trị thực của X là bằng 6.

        Trong số học thông thường, chúng ta có thể thử các số và có thể cảm giác được chúng ta đang “ấm” lên hay “lạnh” đi. Song môi trường số học môđun lại chẳng cho ta những đầu mối hữu ích nào và do đó việc đảo ngược hàm số khó hơn rất nhiều. Thường chỉ có một cách đảo ngược hàm trong số học môđun, đó là lập một bảng tính toán giá trị của hàm tại nhiều giá trị của X cho đến khi tìm thấy kết quả đúng. Bảng 25 trình bày kết quả tính một số giá trị của hàm trong cả số học thông thường lẫn số học môđun. Nó minh họa một cách rõ ràng hành vi thất thường của hàm số khi được tính trong số học môđun. Mặc dù lập ra một bảng như vậy chỉ là việc làm tẻ ngắt khi tính toán với các số tương đối nhỏ, song sẽ là rất khổ nhọc nếu phải lập một bảng với hàm số như 453x (mod 21.997). Đây là một ví dụ kinh điển về hàm một chiều, vì tôi có thể lấy một giá trị của X và tính toán ra kết quả của hàm, song nếu tôi đưa cho bạn một kết quả, giả sử là 5.787 thì bạn sẽ cực kỳ khó khăn để đảo ngược hàm và suy ra giá trị của X. Sẽ chỉ mất vài giây để tôi tính toán và tìm ra 5.787 song bạn sẽ phải mất hàng giờ để lập bảng và tính ra giá trị của X.

Bảng 25 Giá trị của hàm 3X được tính trong số học thông thường (dòng thứ hai) và số học môđun (dòng thứ ba). Hàm số tăng lên liên tục ở số học thông thường song lại rất thất thường trong số học môđun.
Logged

Giangtvx
Thượng tá
*
Bài viết: 25400


« Trả lời #144 vào lúc: 08 Tháng Sáu, 2020, 05:58:12 am »

       
        Sau hai năm tập trung vào số học môđun và hàm số một chiều, sự ngốc nghếch của Heilman bắt đầu được đền đáp. Vào mùa xuân năm 1976, ông đã tìm ra một chiến lược giải quyết được vấn đề trao đổi chìa khóa mã. Trong vòng một tiếng rưỡi đồng hồ viết nguệch ngoạc một cách điên rồ trên bảng, ông đã chứng minh rằng Alice và Bob có thể thống nhất một chìa khóa mã mà không cần gặp nhau, nhờ đó đã đánh bại một chân lý đã tồn tại hàng thế kỷ nay. Ý tưởng của Heilman dựa trên hàm số một chiều có dạng Yx(mod P). Ban đầu, Alice và Bob thống nhất giá trị của Y và P. Hầu hết mọi giá trị đều có thể chấp nhận, song có một số giới hạn, chẳng hạn như Y phải nhỏ hơn P. Các giá trị này không cần giữ bí mật, nên Alice có thể gọi thẳng cho Bob và đề nghị, chẳng hạn Y=7 và P = 11. Ngay cả nếu đường dây điện thoại không an toàn và Eve xấu bụng nghe được cuộc nói chuyện này thì cũng không quan trọng, như sau này chúng ta sẽ thấy. Như vậy, Alice và Bob giờ đã thống nhất hàm số một chiều 7x(mod 11). Lúc này, họ có thể bắt đầu quá trình thử thiết lập một chìa khóa mã mà không cần gặp nhau. Vì họ làm song song nên tôi giải thích hành động của họ ở hai cột như trên Bảng 26.

        Sau khi thực hiện theo các bước trong Bảng 26, bạn sẽ thấy, không cần gặp nhau, Alice và Bob vẫn thống nhất được một chìa khóa mã mà họ có thể sử dụng để mã hóa thư. Chẳng hạn, họ có thể sử dụng số 9 như là chìa khóa mã cho mã hóa bằng DES. (DES thực sự sử dụng các số lớn hơn nhiều để làm chìa khóa mã và quá trình trao đổi được mô tả trong Bảng 26 sẽ được thực hiện với các số lớn hơn nhiều, tạo ra chìa khóa mã DES cũng lớn hơn). Bằng việc sử dụng cơ chế của Heilman, Alice và Bob đã có thể thống nhất chìa khóa mã, song họ không phải gặp nhau và thì thầm với nhau về chìa khóa mã. Thành công kỳ diệu là chìa khóa mã được thống nhất qua trao đổi trên đường dây điện thoại thông thường. Nhưng nếu Eve nghe trộm được thì liệu có chắc chắn là cô ta sẽ không thể biết được chìa khóa mã không?

        Bây giờ chúng ta hãy thử kiểm tra sơ đồ của Heilman theo quan điểm của Eve. Nếu cô ấy nghe lén và biết các thông tin sau: hàm số là 7X (mod 11), Alice gửi α = 2 và Bob gửi β = 4. Để tìm ra chìa khóa mã, Eve phải làm như Bob, tức là biến α thành chìa khóa mã nhờ đã biết B, hay làm như Alice biến β thành chìa khóa mã nhờ đã biết A. Tuy nhiên, Eve không biết giá trị của A hay B vì Alice và Bob không trao đổi các số này và giữ bí mật chúng. Và Eve rơi vào ngõ cụt. Cô chỉ còn một hy vọng: về lý thuyết, cô có thể tính ra A từ α, vì α là kết quả của việc thay A vào hàm số mà Eve đã biết. Hoặc cô cũng có thể tính B từ β vì β là kết quả của việc thay B vào hàm số mà cô cũng đã biết. Không may cho Eve, hàm số là một chiều nên trong khi Alice dễ dàng biến A thành α và Bob biến B thành β nhưng Eva lại rất khó khăn để đảo ngược lại quá trình đó, đặc biệt là nếu các con số là cực lớn.

        Bảng 26 Hàm số một chiều tổng quát là Yx (mod P). Alice và Bob cùng lựa chọn giá trị cho Y và P, và vì vậy thống nhất được hàm một chiều là 7x(mod 11).
Logged

Giangtvx
Thượng tá
*
Bài viết: 25400


« Trả lời #145 vào lúc: 08 Tháng Sáu, 2020, 06:01:37 am »


        Bob và Alice đã trao đổi thông tin đủ để giúp họ thiết lập nên một chìa khóa mã, song thông tin này lại không đủ với Eve để tính toán ra chìa khóa mã. Cũng tương tự như sơ đồ của Heilman, hãy tưởng tượng một mật mã bằng cách nào đó dùng màu sắc làm chìa khóa mã. Trước hết, chúng ta giả định rằng mọi người, trong đó có cả Alice, Bob và Eve, đều có một lọ dung tích ba lít chứa một lít sơn màu vàng. Nếu Alice và Bob muốn thống nhất chìa khóa mã, mỗi người đổ thêm vào lọ của mình một lít màu bí mật. Alice có thể đổ một ít màu tím trong khi Bob có thể đổ thêm vào màu đỏ sẫm. Mỗi người sau đó gửi lọ hỗn hợp của mình cho nhau. Cuối cùng, Alice đổ thêm vào hỗn hợp của Bob màu bí mật của cô còn Bob đổ vào hỗn hợp của Alice màu bí mật của anh. Cả hai lọ lúc này sẽ có cùng một màu, vì chúng đều có chứa một lít màu vàng, một lít màu tím và một lít màu đỏ sẫm. Đây chính là màu chính xác của cái lọ đã được pha thêm hai lần và được sử dụng làm chìa khóa mã. Alice không biết Bob đã đổ thêm màu gì và Bob cũng vậy, song cuối cùng họ đều thu được cùng một màu. Trong khi đó Eve lại rất bối rối. Ngay cả khi cô bắt được những cái lọ trung gian, cô cũng không thể tìm ra màu của cái lọ cuối cùng, chính là chìa khóa mã đã được thống nhất. Cô có thể nhìn thấy màu của cái lọ hỗn hợp của màu vàng và màu mà Alice đã thêm vào trên đường gửi đến chỗ Bob, và cũng có thể nhìn thấy màu của cái lọ hỗn hợp màu vàng và màu bí mật mà Bob đã thêm vào trên đường gửi đến chỗ Alice, song để tìm ra chìa khóa mã, cô cần phải biết màu bí mật ban đầu của Alice và Bob. Tuy nhiên, Eve không thể tìm ra nếu chỉ nhìn vào lọ hỗn hợp. Ngay cả nếu cô có lấy mẫu từ một trong các màu sơn hỗn hợp, cổ cũng không thể tách màu ra để tìm được màu bí mật, vì hỗn hợp sơn là hàm số một chiều.

        Đột phá của Heilman nảy ra khi ông làm việc ở nhà một hôm vào đêm khuya, nên lúc ông tính toán xong thì đã quá muộn để gọi điện cho Diffie và Merkle. Ông đã chờ cho đến sáng hôm sau để tiết lộ phát minh của mình cho hai người bạn, hai người duy nhất trên thế giới cũng tin rằng có một giải pháp khả thi đối với vấn đề phân phối chìa khóa mã. “Nàng thơ đã thì thầm riêng với tôi”, Heilman kể, “song tất cả chúng tôi đã cùng nhau đặt nền móng”. Diffie ngay lập tức nhận ra sức mạnh của phát minh của Heilman: “Marty đã giải thích hệ thống của anh về trao đổi chìa khóa mã với tất cả sự đơn giản đến mức không thể tin nổi của nó. Lắng nghe anh ấy nói, tôi chợt nhận ra ý niệm đó đôi khi cũng đã từng lấp ló trong tâm trí tôi, song nó đã không thực sự bật ra.”

        Sơ đồ trao đổi chìa khóa mã Diffie-Hellman-Merkle, như được gọi ngày nay, đã giúp Alice và Bob có thể thiết lập một bí mật qua trao đổi công khai. Đó là một trong những khám phá khác thường nhất trong lịch sử khoa học và buộc các cơ quan mật mã phải viết lại các quy tắc mã hóa. Diffie, Heilman và Merkle đã chứng minh công khai những khám phá của họ tại Hội nghị Máy tính Quốc gia vào tháng Sáu năm 1976, và đã làm cho cử tọa là các chuyên gia mật mã phải kinh ngạc. Một năm sau, họ đã được nhận bằng phát minh sáng chế. Từ nay, Alice và Bob không phải gặp nhau để trao đổi chìa khóa mã nữa. Thay vào đó, Alice có thể gọi cho Bob trên điện thoại, trao đổi một cặp số với Bob, rồi cùng nhau thiết lập một chìa khóa mã và sau đó tiến hành mã hóa.

        Tuy trao đổi chìa khóa mã Diffie-Hellman-Merkle là một bước nhảy vượt bậc, song hệ thống vẫn chưa hoàn hảo vì vẫn còn có những bất tiện. Hãy tưởng tượng rằng Alice sống ở Hawaii, và cô muốn gửi thư điện tử cho Bob ở Instanbul. Bob có thể đang ngủ, song điểm thú vị của e-mail, đó là Alice có thể gửi thư vào bất cứ lúc nào và nó vẫn đợi trên máy tính của Bob khi anh tỉnh giấc. Tuy nhiên, nếu Alice muốn mã hóa thư của mình thì cô phải thống nhất chìa khóa mã với Bob, và để tiến hành trao đổi thì thích hợp nhất là Alice và Bob phải cùng trên mạng, vì thiết lập một chìa khóa mã đòi hỏi sự trao đổi thông tin hai chiều. Muốn vậy, Alice phải đợi Bob thức dậy. Một cách khác, Alice có thể chuyển phần của mình trước rồi đợi trả lời của Bob sau 12 tiếng, lúc ấy chìa khóa sẽ được thiết lập và Alice có thể, nếu cô chưa ngủ, mã hóa và gửi thư đi. Dù theo cách nào thì hệ thống trao đổi chìa khóa mã của Heilman vẫn làm chậm tính tức thời của thư điện tử.

        Như vậy, Heilman đã làm tiêu tan một trong những giáo lý của khoa mật mã và chứng minh được rằng Bob và Alice không phải gặp nhau để thống nhất chìa khóa mã. Tiếp theo, chỉ cần một ai khác tìm ra một sơ đồ hiệu quả hơn là vấn đề phân phối chìa khóa mã sẽ được giải quyết một cách trọn vẹn.
Logged

Giangtvx
Thượng tá
*
Bài viết: 25400


« Trả lời #146 vào lúc: 09 Tháng Sáu, 2020, 05:18:35 am »


        SỰ RA ĐỜI CỦA MẬT MÃ CHÌA KHÓA CÔNG KHAI

        Mary Fisher không bao giờ quên lần đầu tiên Whitfield Diffie hẹn hò bà: “Ồng ấy biết tôi yêu thích không gian nên đã mời tôi đi chơi và ăn trưa. Whit giải thích rằng tối hôm ấy ông sẽ đi xem Skylab (Phòng thí nghiệm không gian) cất cánh, và vì vậy chúng tôi đã lái xe suốt đêm và tới đó lúc 3 giờ sáng. Con chim đã ở trên đường, như họ vẫn thường nói hồi đó. Whit có những thành tích nổi bật chứ tôi thì không. Vì vậy, khi họ hỏi thẻ căn cước của tôi và hỏi tôi là ai, Whit nói ‘Vợ tôi’. Đó là ngày 16 tháng Mười một năm 1973”. Họ cuối cùng đã lấy nhau, và trong suốt những năm đầu, Mary đã giúp đỡ ông trong những lúc ông mải mê suy tư về mật mã. Lúc đó Diffie vẫn còn là nghiên cứu sinh nên ông chỉ nhận được đồng lương ít ỏi. Còn Mary, một nhà khảo cổ học được đào tạo bài bản, đã kiếm được việc làm ở Công ty Dầu mỏ Anh quốc nên cũng tùng tiệm đủ sống.

        Trong khi Martin Heilman đang nghiên cứu phương pháp trao đổi chìa khóa mã của mình thì Whitfield Diffie lại thực hiện một cách tiếp cận hoàn toàn khác để giải quyết vấn đề phân phối chìa khóa mã. Ồng thường mất những khoảng thời gian dài tập trung suy nghĩ nhưng không mang lại kết quả. Và một lần vào năm 1975, ông đã thất vọng đến mức buột miệng bảo với Mary rằng ông là một nhà khoa học thất bại, chẳng bao giờ làm nên trò trống gì. Ông thậm chí còn bảo bà nên tìm một người đàn ông khác. Mary đã nói với ông rằng bà có một niềm tin tuyệt đối vào ông và chỉ hai tuần sau Diffie đã nảy ra một ý tưởng thực sự sáng chói.

        Ông vẫn nhớ được ý tưởng đó đã lóe lên trong óc ông như thế nào và sau đó thì hầu như biến mất: “Tôi đi xuống tầng dưới để lấy một lon Coke và gần như đã quên biến ý tưởng đó. Tôi nhớ rằng mình đang nghĩ về một điều gì đó rất lý thú, song không thể nhớ lại được nó là cái gì. Rồi, nó bỗng trở lại trong sự phấn khích dâng trào thực sự. Tôi nhận ra rằng lần đầu tiên tôi đã khám phá ra một cái gì đó thực sự có giá trị trong sự nghiệp nghiên cứu mật mã của mình. Mọi thứ mà tôi đã khám phá trong lĩnh vực này từ trước tới nay đối với tôi dường như chỉ là những chi tiết kỹ thuật không mấy quan trọng”. Lúc đó là vào khoảng giữa buổi chiều và ông phải đợi vài giờ sau Mary mới trở về. “Whit đang đứng đợi trước cửa”, bà nhớ lại. “Ồng ấy bảo có một chuyện muốn nói với tôi và trên mặt ông ấy có vẻ gì đó rất buồn cười. Tôi bước vào và ông ấy nói, ‘Ngồi xuống đi em, anh muốn nói chuyện với em. Anh tin rằng mình đã có một khám phá vĩ đại - Anh biết anh là người đầu tiên làm được việc này’. Thế giới dường như ngưng lại với tôi giây phút đó. Tôi cảm thấy như mình đang sống trong một bộ phim của Hollywood.”

        Diffie đã tạo ra một loại mật mã mới, kết hợp chặt chẽ với cái được gọi là chìa khóa mã bất đối xứng. Cho đến đây, tất cả các kỹ thuật mã hóa mô tả trong cuốn sách này đều là đối xứng, tức là quá trình giải mã chỉ đơn giản là làm ngược lại với quá trình mã hóa. Chẳng hạn, máy Enigma sử dụng cách cài đặt chìa khóa mã nhất định để mã hóa thông tin và người nhận sử dụng một cái máy giống hệt với cùng một cách cài đặt chìa khóa mã. Tương tự như vậy, mã hóa DES sử dụng một chìa khóa mã để thực hiện 16 vòng mã hóa, và sau đó việc giải mã DES cũng sử dụng cùng chìa khóa mã để thực hiện 16 vòng đảo ngược lại. Cả người gửi và người nhận đều có sự hiểu biết tương đương nhau, và họ đều sử dụng cùng một chìa khóa mã để mã hóa và giải mã, tức mối quan hệ giữa họ là đối xứng. Trái lại, trong một hệ thống chìa khóa mã bất đối xứng, chìa khóa để mã hóa và chìa khóa để giải mã không giống hệt như nhau, đúng như cái tên của nó cho thấy. Trong mật mã bất đối xứng, nếu Alice biết chìa khóa để mã hóa, cô ấy có thể mã hóa thư, song cô ấy không thể giải mã được bức thư đó. Để giải mã, Alice phải có được chìa khóa giải mã. Sự khác biệt giữa chìa khóa để mã hóa và giải mã chính là điểm khiến cho mật mã bất đối xứng trở nên đặc biệt.

        Đến đây cũng cần nhấn mạnh rằng Diffie mới chỉ tìm ra khái niệm chung về một mật mã bất đối xứng, chứ chưa thực sự tạo ra một ví dụ mật mã cụ thể nào. Tuy nhiên, chỉ riêng khái niệm về một mật mã bất đối xứng thôi cũng đã là một cuộc cách mạng. Nếu các nhà tạo mã có thể tìm ra một mật mã bất đối xứng thực sự, một hệ thống thỏa mãn các yêu cầu của Diffie, thì những hệ quả của nó đối với Alice và Bob sẽ là cực kỳ to lớn. Alice có thể tạo ra các cặp chìa khóa của riêng mình: chìa khóa mã hóa và chìa khóa giải mã. Nếu chúng ta giả sử rằng mật mã bất đối xứng là một dạng mật mã máy tính thì chìa khóa mã hóa của Alice sẽ là một con số, và chìa khóa giải mã là một con số khác. Alice giữ bí mật chìa khóa giải mã, vì vậy thường thì nó được gọi là chìa khóa riêng của Alice. Tuy nhiên, cô ấy lại công khai chìa khóa mã hóa và ai cũng có thể có nó, vì vậy nó thường được gọi là chìa khóa công khai của Alice. Nếu Bob muốn gửi cho Alice một bức thư, anh đơn giản chỉ cần tìm chìa khóa mã công khai của cô ấy trong một danh sách tương tự như danh bạ điện thoại. Sau đó, Bob sử dụng chìa khóa mã công khai của Alice để mã hóa thư. Anh gửi bức thư mã hóa cho Alice và sau khi bức thư đến nơi, Alice có thể giải mã nó bằng chìa khóa giải mã riêng của mình. Tương tự, nếu Charlie, Dawn, hay Edward muốn gửi thư được mã hóa cho Alice, họ cũng có thể tìm chìa khóa công khai của Alice và trong mỗi trường hợp, chỉ có mình Alice là có chìa khóa giải mã riêng để giải mã các bức thư đó.
Logged

Giangtvx
Thượng tá
*
Bài viết: 25400


« Trả lời #147 vào lúc: 09 Tháng Sáu, 2020, 05:18:59 am »


        Lợi thế to lớn của hệ thống này, đó là nó không cần có sự đi lại như khi trao đổi chìa khóa mã Diffie-Hellman-Merkle. Bob không phải đợi nhận được thông tin từ Alice trước khi mã hóa và gửi thư cho cô, anh ta chỉ cần tìm chìa khóa mã hóa công khai của Alice mà thôi. Hơn nữa, mật mã bất đối xứng cũng vẫn giải quyết được vấn đề phân phối chìa khóa mã. Alice không phải chuyển chìa khóa mã công khai của mình một cách bí mật cho Bob, mà hoàn toàn ngược lại, bây giờ cô có thể công khai chìa khóa mã hóa của mình rộng rãi đến đâu cũng được. Thậm chí cô có thể cho cả thế giới biết chìa khóa mã công khai của mình để mọi người đều có thể sử dụng nó để gửi thư bí mật cho cô. Đồng thời, ngay cả nếu toàn thế giới biết chìa khóa công khai của Alice thì cũng không có ai trong số họ, kể cả Eve, có thể giải mã được bất kỳ bức thư đã được mã hóa nào bằng chìa khóa đó, vì việc biết chìa khóa công khai không giúp ích gì cho việc giải mã hết. Thực tế, một khi Bob đã mã hóa thư bằng chìa khóa công khai của Alice thì ngay cả anh cũng không thể giải mã nổi. Chỉ Alice, người sở hữu chìa khóa mã riêng mới có thể giải mã được bức thư đó.

        Điều này hoàn toàn ngược lại với mật mã đối xứng truyền thống, trong đó Alice phải đi một chặng đường dài để chuyển chìa khóa mã một cách an toàn đến cho Bob. Trong mật mã đối xứng, chìa khóa mã hóa cũng chính là chìa khóa giải mã, nên Alice và Bob phải cực kỳ thận trọng để đảm bảo rằng chìa khóa này không bị rơi vào tay Eve. Đây chính là cái gốc của vấn đề phân phối chìa khóa mã.

        Trở lại sự tương tự với các khóa móc, thì mật mã bất đối xứng có thể được hình dung như sau. Bất kỳ ai cũng có thể khóa một chiếc khóa móc một cách đơn giản là bấm nó vào, nhưng chỉ người có chìa khóa mới có thể mở được nó. Khóa (mã hóa) thì dễ, một điều mà ai cũng có thể làm được, song mở (giải mã) thì chỉ có thể thực hiện được bởi người sở hữu chìa khóa. Việc biết bấm chiếc khóa móc tầm thường không cho bạn biết làm thế nào để mở nó. Nói rộng ra, hãy tưởng tượng Alice thiết kế một khóa móc và chìa khóa của nó. Cô ấy giữ chìa khóa song cho sản xuất hàng ngàn khóa móc giống hệt nhau và gửi chúng đi khắp thế giới qua bưu điện. Nếu Bob muốn gửi một bức thư, anh cho nó vào một cái hộp, đến bưu điện địa phương và yêu cầu một “khóa móc Alice” rồi khóa hộp lại. Giờ thì anh không thể mở được hộp nữa, nhưng khi Alice nhận được, cô ấy có thể mở nó bằng chiếc chìa khóa duy nhất. Khóa móc và quá trình bấm khóa là tương đương với chìa khóa mã hóa công khai, vì mọi người đều có thể có được khóa móc, và ai cũng có thể sử dụng khóa móc để niêm phong thư trong hộp. Chìa khóa của khóa móc tương đương với chìa khóa giải mã riêng, vì chỉ Alice mới có nó, chỉ cô mới mở được khóa và chỉ cô mới lấy được lá thư trong hộp ra.

        Hệ thống có vẻ như đơn giản khi được giải thích nhờ sự tương tự với các khóa móc, song việc tìm ra một hàm số toán học thực hiện được điều tương tự lại không hề tầm thường, khi kết hợp nó vào một hệ thống mật mã khả thi. Để đưa mật mã bất đối xứng từ một ý tưởng lớn thành một phát minh dùng được trong thực tế thì phải có ai đó tìm ra một hàm số toán học thích hợp. Diffie đã nghiên cứu một loại hàm số một chiều đặc biệt, một hàm số có thể đảo ngược được trong những điều kiện ngoại lệ. Trong hệ thống bất đối xứng của Diffie, Bob mã hóa bức thư bằng chìa khóa công khai, song anh không thể giải mã được nó - đây thực sự chính là hàm số một chiều. Tuy nhiên, Alice có thể giải mã được bức thư vì cô có chìa khóa riêng, đó là một ít thông tin đặc biệt giúp cô đảo ngược được hàm số này. Một lần nữa, khóa móc lại là một sự tương tự hữu ích - bấm khóa móc vào là một hàm số một chiều, vì nói chung là khó mở ra nếu không có gì đó đặc biệt (chìa khóa riêng), nhưng nếu có nó, hàm số lại được đảo ngược dễ dàng.

        Diffie đã cho công bố một bài báo trình bày khái quát ý tưởng của mình vào mùa hè năm 1975, rồi sau đó các nhà khoa học khác đã tham gia nghiên cứu nhằm tìm kiếm một hàm số một chiều thích hợp, tức là một hàm số thỏa mãn những điều kiện mà một mật mã bất đối xứng đòi hỏi. Ban đầu ai nấy đều rất lạc quan, song cho đến cuối năm đó, vẫn chẳng ai tìm ra một hàm số nào thích hợp. Nhiều tháng trôi qua, dường như ngày càng chắc chắn rằng hàm số một chiều đặc biệt đó không tồn tại. Dường như ý tưởng của Diffie chỉ thực hiện trên lý thuyết mà không tồn tại trong thực tế. Nhưng dù sao, đến cuối năm 1976, nhóm của Diffie, Heilman và Merkle cũng đã làm được một cuộc cách mạng trong thế giới mật mã. Họ đã thuyết phục phần còn lại của thế giới rằng có một giải pháp cho vấn đề phân phối chìa khóa mã, và đã tạo ra cái gọi là trao đổi chìa khóa mã Diffie-Hellman-Merkle - một hệ thống vận hành được nhưng chưa hoàn hảo. Họ cũng đã đưa ra khái niệm về mật mã bất đối xứng - một hệ thống hoàn hảo nhưng chưa vận hành được. Họ tiếp tục những nghiên cứu của mình tại Đại học Stanford, cố gắng tìm ra một hàm số một chiều đặc biệt khiến mật mã bất đối xứng trở thành hiện thực. Tuy nhiên, họ đã thất bại. Chiến thắng trong cuộc chạy đua tìm kiếm mật mã bất đối xứng lại thuộc về một bộ ba nghiên cứu khác, cách Bờ Đông nước Mỹ 5.000km.
Logged

Giangtvx
Thượng tá
*
Bài viết: 25400


« Trả lời #148 vào lúc: 09 Tháng Sáu, 2020, 05:21:02 am »


        CÁC SỐ NGUYÊN TỐ BƯỚC RA SÂN KHẤU

        “Tôi bước vào văn phòng của Ron Rivest”, Leonard Adleman nhớ lại, “và Ron đang cầm bài báo đó trong tay. Anh ấy bắt đầu nói: ‘Mấy gã Stanford này đúng là ba láp quá’. Và tôi nhớ mình đã nghĩ ‘Tuyệt lắm, Ron, nhưng tôi có chuyện khác muốn nói với anh đây’. Tôi hoàn toàn không hay biết gì về lịch sử khoa học mật mã và tôi cũng chẳng hứng thú gì với những điều anh ấy đang nói”. Bài báo khiến Ron Rivest kích động đến như vậy là của Diffie và Heilman, trong đó mô tả khái niệm mật mã bất đối xứng. Cuối cùng, Rivest cũng thuyết phục được Adleman rằng có thể có những điều thú vị về toán học trong vấn đề này và họ đã cùng nhau giải quyết để cố tìm ra một hàm số một chiều thỏa mãn những yêu cầu của một mật mã bất đối xứng. Trong cuộc săn tìm này, họ đã hợp tác với Adi Shamir. Cả ba đều là các nhà nghiên cứu làm việc trên tầng tám của Phòng Thí nghiệm về Khoa học máy tính của MIT.

        Rivest, Shamir và Adleman đã hình thành nên một nhóm hoàn hảo. Rivest là một nhà khoa học về máy tính với khả năng hấp thu những ý tưởng mới rất khác thường và ứng dụng chúng vào những chỗ không chắc thành công. Ông luôn theo dõi sát những bài báo khoa học mới nhất, chính chúng đã tạo cho ông cảm hứng tìm ra một loạt những ứng viên kỳ lạ và tuyệt vời cho hàm số một chiều là trung tâm của mật mã bất đối xứng. Tuy nhiên, mỗi ứng viên lại có những thiếu sót khác nhau. Shamir, một nhà khoa học máy tính khác, lại có một trí tuệ sắc sảo và một khả năng nhìn xuyên thấu những thứ vụn vặt để tập trung vào cốt lõi của vấn đề. Ông cũng thường nghĩ ra những ý tưởng về tạo mật mã bất đối xứng, song những ý tưởng của ông cuối cùng vẫn có những sơ hở. Adleman, một nhà toán học với khả năng chịu đựng cực lớn, chặt chẽ và kiên nhẫn, người có trách nhiệm rất lớn là phát hiện ra những sai sót trong các ý tưởng của Rivest và Shamir, bảo đảm rằng họ không lãng phí thời gian theo đuổi những phương hướng sai lầm. Rivest và Shamir mất một năm theo đuổi những ý tưởng mới, và Adleman mất một năm để hạ gục chúng. Cả ba người phần nào đã bắt đầu mất hy vọng, song họ không nhận ra rằng quá trình thất bại liên tiếp đó là một phần tất yếu trong nghiên cứu của họ, nó đã dần dần lái họ rời xa lãnh địa toán học khô cằn và hướng đến một vùng đất màu mỡ hơn. Trong quá trình đó, những nỗ lực của họ đã được đền bù.

        Vào tháng Tư năm 1977, Rivest, Shamir và Adleman nghỉ lễ Quá Hải1 tại nhà của một sinh viên và uống khá nhiều rượu Manischewitzt2. Mãi nửa đêm họ mới trở về nhà. Rivest, không ngủ được, vừa nằm trên đivăng vừa đọc một cuốn sách giáo khoa toán. Rồi ông chuyển sang suy ngẫm về câu hỏi đã khiến ông trăn trở hàng tuần lễ - liệu có thể tạo được một mật mã bất đối xứng hay không? Có thể tìm ra một hàm số một chiều mà có thể đảo ngược được chỉ khi người nhận có những thông tin nào đó đặc biệt không? Bất chợt màn sương mù tan dần và ông đã có một phát hiện. Thời gian còn lại của đêm đó, ông định hình ý tưởng của mình, và viết ngay một bài báo khoa học hoàn chỉnh trước khi trời sáng. Rivest đã có một đột phá, song nó chỉ nảy sinh sau suốt một năm hợp tác với Shamir và Adleman, và nó sẽ không thể có được nếu thiếu sự cộng tác của họ. Rivest đã kết thúc bài báo với tên tác giả được viết theo vần abc: Adleman, Rivest, Shamir.

        Sáng hôm sau, Rivest đưa bài báo cho Adleman, người đã quen với việc thường xuyên phải xé chúng đi, nhưng lần này, ông đã không tìm thấy một lỗi nào. Ông chỉ phê phán về tên tác giả. “Tôi đã bảo Ron bỏ tên tôi ra khỏi bài báo”, Adleman nhớ lại, “Tôi nói với anh ấy rằng đấy là phát minh của anh, không phải của tôi. Nhưng Ron từ chối và chúng tôi đã thảo luận về chuyện đó. Chúng tôi đã thỏa thuận rằng tôi sẽ về nhà và suy nghĩ một đêm về điều đó, và cân nhắc xem tôi muốn làm gì. Tôi trở lại ngày hôm sau và đề nghị Ron rằng tôi là tác giả thứ ba. Tôi nhớ lúc đó mình đã nghĩ rằng đó là bài báo ít thú vị nhất mà tôi đã từng đứng tên.” Adleman không thể sai lầm hơn thế. Hệ thống, được gọi là RSA (Rivest, Shamir, Adleman) đảo ngược của ARS, đã trở thành mật mã có ảnh hưởng lớn nhất trong khoa học mật mã hiện đại.

Hình 65 Ronald Rivest, Adi Shamir và Leonard Adleman.
------------------------
        1. Lễ kỷ niệm việc người Do Thái rời khỏi Ai Cập. (ND)

        2. Rượu làm từ nho và được ướp lạnh, uống vào dịp lễ của người Do Thái. (ND)

Logged

Giangtvx
Thượng tá
*
Bài viết: 25400


« Trả lời #149 vào lúc: 09 Tháng Sáu, 2020, 05:21:30 am »

               
        Trước khi xem xét ý tưởng của Ri vest, dưới đây tôi xin nhắc lại ngắn gọn điều mà các nhà khoa học tìm kiếm nhằm tạo ra mật mã bất đối xứng:

        (1) Alice phải tạo một chìa khóa công khai mà sau đó cô sẽ công bố rộng rãi nên Bob (và mọi người khác) có thể sử dụng nó để mã hóa thư gửi cho cô. Vì chìa khóa công khai là hàm số một chiều nên hầu như không ai có thể đảo ngược được nó và giải mã được các bức thư của Alice.

        (2) Tuy nhiên, Alice cần phải giải mã được những bức thư gửi đến cho cô. Vì vậy, cô phải có một chìa khóa riêng, tức một mẩu thông tin đặc biệt nào đó cho phép cô đảo ngược được tác dụng của chìa khóa mã công khai. Nhờ vậy, Alice (và chỉ Alice) mới có khả năng giải mã bất kỳ bức thư nào gửi tới cho cô.

        Cốt lõi của mật mã bất đối xứng của Rivest là một hàm một chiều dựa trên loại các hàm môđun như đã trình bày ở đầu chương. Hàm một chiều của Rivest có thể được sử dụng để mã hóa thư - thư ở đây thực chất chỉ là một số, được nạp vào hàm, và kết quả nhận được chính là văn bản mật mã, cũng là một con số. Tôi sẽ không mô tả chi tiết hàm số một chiều của Rivest ở đây (xin xem Phụ Lục J), song tôi sẽ giải thích một khía cạnh đặc biệt của nó, được gọi đơn giản là N, vì chính N làm cho hàm số một chiều có thể đảo ngược được dưới những điều kiện nhất định, và vì vậy là rất lý tưởng để sử dụng như một mật mã bất đối xứng.

        N rất quan trọng vì nó là thành phần linh hoạt trong hàm số một chiều, tức là mỗi người có thể chọn một giá trị riêng cho N, và tạo ra hàm số một chiều riêng. Để chọn giá trị của N riêng cho mình, Alice lấy hai số nguyên tố, p và q, và nhân chúng với nhau. Một số nguyên tố là số chỉ chia hết cho 1 và chính nó. Chẳng hạn, 7 là số nguyên tố vì 7 chỉ chia hết cho 1 và 7. Tương tự, 13 là số nguyên tố vì nó chỉ chia hết cho 1 và 13. Tuy nhiên, 8 không phải là số nguyên tố vì nó chia hết cho cả 2 và 4.

        Chẳng hạn, Alice có thể chọn số nguyên tố của mình là p = 17.159 và q = 10.247. Nhân hai số này với nhau ta được A=17.159 * 10.247 = 175.828.273. Lựa chọn N của Alice chính là chìa khóa mã hóa công khai, và cô có thể in vào danh thiếp, thông báo trên Internet, hoặc đưa vào một danh bạ chìa khóa mã công khai cùng với các giá trị N của những người khác. Nếu Bob muốn mã hóa thư gửi cho Alice, anh tìm giá trị N (175.828.273) của Alice và sau đó thay vào công thức chung của hàm một chiều, hàm này cũng được thông báo công khai. Giờ Bob có hàm một chiều tạo bởi chìa khóa công khai của Alice, được gọi là hàm số một chiều của Alice. Để mã hóa thư gửi Alice, anh lấy hàm một chiều của Alice, nạp thư vào và ghi lại kết quả rồi gửi cho Alice.

        Lúc này, bức thư mã hóa là an toàn vì không ai có thể giải mã được nó. Thư đã được mã hóa với hàm số một chiều nên đảo ngược hàm một chiều và giải mã thư, theo định nghĩa, là rất khó khăn. Tuy nhiên, còn một vấn đề là - làm thế nào Alice giải mã được thư? Để đọc thư gửi đến cho mình, Alice phải có một cách đảo ngược hàm một chiều. Cô cần có được chút ít thông tin đặc biệt nào đó cho phép cô giải mã thư. May mắn cho Alice là Rivest đã thiết lập hàm số một chiều sao cho có thể đảo ngược được nếu ai đó biết được giá trị của p và q, hai số nguyên tố mà tích của chúng cho giá trị N. Mặc dù Alice đã thông báo cho cả thế giới biết về giá trị N là 175.828.273, song cô không tiết lộ các giá trị của p và q, vì vậy chỉ mình cô có thông tin đặc biệt cần thiết để giải mã các bức thư của mình.

        Chúng ta có thể hiểu rằng N là chìa khóa công khai, một thông tin sẵn có cho tất cả mọi người và cần thiết để mã hóa thư gửi cho Alice. Trong khi đó, p và q là chìa khóa riêng, chỉ dành riêng cho Alice, tức là thông tin cần thiết để giải mã thư.

        Các chi tiết chính xác về việc sử dụng p và q như thế nào để đảo ngược hàm số một chiều được nêu tóm tắt trong Phụ lục J. Tuy nhiên, có một câu hỏi cần được nói ngay ở đây. Nếu ai cũng biết N, tức chìa khóa mã công khai, thì biết đâu người ta cũng có thể suy ra p và q, chìa khóa riêng, và đọc được thư của Alice? Xét cho cùng, chính N được tạo bởi p và q. Tuy nhiên, thực tế, nếu N đủ lớn thì gần như không thể suy ra p và q từ N, và có lẽ đây chính là khía cạnh đẹp và tao nhã nhất của mật mã bất đối xứng RSA.
Logged

Trang: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 »   Lên
  In  
 
Chuyển tới:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines

Valid XHTML 1.0! Valid CSS! Dilber MC Theme by HarzeM