Bẻ khóa RSA (hoặc các thuật toán khác) theo cách thủ công bởi một người hiểu biết

Sức mạnh của mật mã RSA đến từ độ cứng (hoặc chúng tôi tin như vậy) của việc bao thanh toán các số lớn. Đối với độ dài khóa trên 2048 bit, các máy tính hiện tại hoặc tương lai gần không thể tính các số đó trong một thời gian hợp lý.

Nhưng còn bộ não con người thì sao? Có những người có khả năng toán học vượt trội; ví dụ, những người hiểu biết có thể thực hiện nhiều phép tính phức tạp. Hãy tưởng tượng một người tập trung vào các số tổng hợp bao thanh toán. Có lẽ khả năng của anh ấy hoặc cô ấy có thể được tăng cường bằng thuốc.

Đây có phải là mối quan tâm thực sự khi thiết kế mật mã không? Liệu một tổ chức xấu xa có thể sử dụng một trong những người này để bẻ khóa mật mã (đối với bất kỳ mật mã hiện đại nào) không? Có lẽ có một số ví dụ thực tế?

Suy nghĩ của bạn đi ngược lại với lẽ thường trong mật mã và điện toán. Và nói thẳng ra, đó là giả khoa học trắng trợn.

Bộ não con người và các tế bào thần kinh bên trong hoạt động ở trạng thái vô hướng. Mặc dù vẫn còn tranh cãi liệu quá trình não bộ là xác định hay xác suất, nhưng nó không có khả năng tạo ra các trạng thái chồng chất như máy tính lượng tử có thể làm được. Do đó, không có lợi thế nào so với các siêu máy tính cổ điển về hệ số nguyên hoặc logarit rời rạc (thuật toán của Shor), cũng như không có bất kỳ lợi thế nào khi tìm kiếm thông qua cơ sở dữ liệu chưa được sắp xếp (thuật toán của Grover).

Đối với bộ não con người, thật quá dễ dàng để bỏ qua độ sâu của 2048+ chút nhân vật. Hãy làm một số bài tập phỏng đoán kỹ thuật để minh họa.

Bài đăng gốc của @derjack dài gần 700 ký tự. Đây là một số 2048 bit, được viết bằng 617 chữ số thập phân (gần bằng độ dài của câu hỏi):

32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448280710318450446268407511633591722075539194702809692695116208601753153385228164358637425253452063124531982403270024154882788029124087013649227429510942494747262878176328960795460204004486651813356499189783184670257748061985168288109350852763136493356212118910302261417784227884243069534873234110239729827362916848850208533176280055919120540762635115410724871087269605319201076899957787049604743491139956908133927452563472712188255099007744935013999050172650250829825

Bạn có thể hiểu ý tôi rằng đó là một hợp số (nghĩa là không phải số nguyên tố).

Bạn cũng có thể nhìn kỹ hơn và quan sát rằng chữ số cuối cùng là 5 và do đó, 5 là một ước số. Nhưng chỉ đơn giản là một thử thách, bạn có thể tìm ra những yếu tố lớn hơn không?

Hãy thiết lập một giới hạn thấp hơn về thời gian một con người hiện tại có thể phá vỡ điều này. Các tài liệu tham khảo của tôi rất khó hiểu ở đây¹, nhưng có vẻ hợp lý để lấy 3850 từ mỗi phút như một giới hạn trên về tốc độ đọc của con người. Đã chuyển đổi, đó là 302 ký tự mỗi giây (với độ dài từ trung bình là 4,7 trong tiếng Anh²). Tôi cũng sẽ ngoại suy con số này thành những con số dài; vì vậy chúng tôi đến sân bóng của 300 chữ số trên giây tốc độ đọc.

>>> 617 / 301.6
2.045755968169761

Các người đọc nhanh nhất thế giới sẽ cần không ít hơn 2045 mili giây chỉ để tải số vào bộ nhớ của họ. Đối với những độc giả bình thường hơn như tôi và bạn, có 17à thừa số¹; Vì thế chỉ cần đọc số sẽ mất 35 giây không hơn không kém.Lưu ý rằng đối với ước tính giới hạn dưới mà chúng ta đang thực hiện ở đây, chúng ta phải giả sử vô tận hiệu suất số nguyên-FLOPS của não. 35 giây sẽ là IO trước khi tính toán.

¹: https://www.brainread.com/en/the-fastest-reader-in-the-world/

²: https://norvig.com/mayzner.html

Bây giờ, tôi khuyên bạn nên tự lặp lại bài tập, ví dụ: cho 4096 bit. Nó không nhiều gấp đôi! Mức độ trừu tượng sai nếu bạn nghĩ như vậy. 4096-bit numbers are on average 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 times larger than 2048-bit numbers, in absolute value.

Bài tập này có thể giúp bạn nhận ra rằng việc nghe điều gì đó về phép tính "N-bit" và tưởng tượng rằng bạn đã hiểu điều gì đó thật dễ bị đánh lừa. đó là đường khó hơn âm thanh—nếu bạn làm toán.

Bất kỳ người nào có thể tính các số 2048 bit trong đầu nhanh hơn máy tính gần như chắc chắn là người đã phát hiện ra một thuật toán mới để tính các số. Mà, nếu được thực hiện trên máy tính, sẽ còn nhanh hơn nữa.

Nhưng điều đó không loại trừ điều này.

Tôi sẽ ít hơn một chút so với hoàn toàn chính xác dưới đây. Ví dụ, tôi sẽ kết hợp các bài toán quyết định và các thuật toán để giữ cho các thuật ngữ được đơn giản.

Chúng tôi không biết các con số bao thanh toán thực sự khó như thế nào. Chúng tôi biết nó thuộc lớp phức tạp BQP, dành cho máy tính cổ điển (hoặc con người chạy thuật toán cổ điển trong đầu) trong NP.

Một vấn đề là trong NP nếu nó tương đối rẻ để thẩm tra bạn đã có câu trả lời đúng. Ví dụ ở đây là nếu ai đó nói rằng thừa số của một số là A và B, bạn có thể kiểm tra bằng cách ... tính A*B và xem nó có khớp không.

Nhưng không có bằng chứng nào cho thấy NP không giống như P. Nếu NP=P, thì mọi bài toán đều có thể có lời giải xác minh nhanh có thể được giải quyết Nhanh. (Điều này rất gợn sóng, nhưng đúng trong những giới hạn đó). Và nếu NP=P, thì BQP nằm trong NP cũng nằm trong P.

Đối với các vấn đề trong NP, chúng tôi biết không có thuật toán cổ điển nào nhanh hơn nhiều so với "chỉ cần thử mọi khả năng" ở đây để có các định nghĩa rộng rãi về "tất cả chỉ có vậy". (các thuật toán bao thanh toán nhanh nhất hoàn toàn là cấp số nhân phụ; như O(e^(k + bits^(1/3)*ln(bits)^(2/3)) nếu tôi đã sao chép đúng).

Vì vậy, nếu ai đó nghĩ ra một thuật toán để phân tích các số lớn theo thời gian đa thức, về lý thuyết, họ có thể học cách chạy thuật toán trong đầu và có thể phân tích các số tổng hợp lớn nhanh hơn bất kỳ máy tính nào.

Điều này là không thể tin được. Và, thành thật mà nói, một thuật toán như vậy có lẽ sẽ có giá trị hơn để chia sẻ hơn là nhét vào đầu bạn.

Savant có thể tìm ra thừa số nhanh không có hiển thị NP=P hoặc thậm chí là BQP=P; ví dụ: có thể việc phân tích thừa số của các loại số nguyên tố cụ thể mà chúng tôi sử dụng để mã hóa dễ dàng hơn so với bài toán tổng quát hoặc có thể phần trăm lớn các số hỗn hợp như vậy dễ dàng phân tích (nhưng không phải tất cả chúng), hoặc có một số "trường hợp góc" khác cho phép nó hoạt động (thậm chí đôi khi) cực kỳ nhanh hơn "thử mọi trường hợp". Một kết quả như vậy sẽ rất hiệu quả, nhưng sẽ không mang tính cách mạng trên quy mô viết lại phần lớn những gì chúng ta coi là toán học thú vị (điều mà một thuật toán P hiệu quả cho các bài toán NP sẽ làm được, một cách trung thực).

Các câu trả lời khác đã chỉ ra một cách chính xác rằng bộ não động vật chậm hơn rất nhiều và dễ mắc lỗi hơn so với các máy tính hiện đại trong tất cả các tác vụ tính toán, ngoại trừ một số ít được hưởng lợi rất nhiều từ loại kỹ năng lập kế hoạch và nhận dạng mẫu cụ thể mà bộ não đã được phát triển cho . Rõ ràng, điều này không có nghĩa là não động vật không thể hữu ích về mặt mật mã: thực sự, các cuộc tấn công mật mã tốt nhất được biết đến ngày nay đều đã được tìm thấy ít nhất một phần bởi não động vật. Tuy nhiên, đối với các sơ đồ mật mã tiêu chuẩn, dường như rất khó xảy ra trường hợp một bộ não có thể chạy một cuộc tấn công thành công (tuy nhiên, nó có thể rất hữu ích ở giai đoạn lập kế hoạch nó).

Điều đó nói rằng, tôi thấy câu hỏi thú vị là liệu một sơ đồ mật mã có thể được thiết kế an toàn trước tất cả các cuộc tấn công đã biết dựa trên thuật toán tấn công có thể xác định đầy đủ nhưng không an toàn trước phân tích mật mã bằng giấy và bút chì. Tôi không nghĩ rằng câu trả lời cho điều này rõ ràng là tiêu cực. Chẳng hạn, người ta có thể nghĩ đến việc mã hóa một chuỗi bit ngẫu nhiên dài thành một loạt lược đồ Winograd. Sau đó, người nhận sẽ giải quyết các lược đồ Winograd theo cách thủ công và sau đó xử lý hậu kỳ chuỗi bit đã khôi phục để khuếch đại quyền riêng tư-khuếch đại lợi thế giải mã của họ so với các mô hình ngôn ngữ nghệ thuật hiện đại và nhận được một bộ đệm một lần không thể tái tạo với độ chính xác cao bằng các phương pháp tự động.Cuối cùng, OTP dẫn xuất sẽ được sử dụng để mã hóa một tin nhắn ngắn.

Tuy nhiên, vì không có bằng chứng nào cho thấy bộ não về bản chất tốt hơn bất cứ thứ gì so với máy tính, nên tất cả các kế hoạch như vậy cuối cùng sẽ có xu hướng bị tấn công tự động thực tế.

Số thập phân 2048 bit 617 chữ số @ulidtko được đăng ở trên có thể được tính tính bằng giờ hoặc ít hơn và có thể bởi một nhà bác học với bộ máy tính số nguyên lớn. Tôi đã tính điều này và tìm thấy dạng đặc biệt của các thừa số. Yếu tố nhỏ thì dễ, yếu tố lớn thì không nếu bạn không tìm ra hình thức đặc biệt.

Loại khả năng bác học cần thiết là khả năng phát hiện các mẫu trong hệ nhị phân. biểu diễn các thừa số nhỏ hơn của số 2048 bit.

Dưới đây là các giá trị thập phân và nhị phân của các yếu tố thấp nhất: 3 - 11, 5 - 101, 7 - 111, 13 - 1101, 17 - 10001, 97 - 1100001, 193 - 11000001, 241 - 11110001, 257 - 100000001

Bạn có thể nhìn thấy các mô hình? Có 3 mẫu. Mẫu đầu tiên tất cả 11111 mẫu thứ 2 101,10001, 100000001 mẫu thứ 3 khác 1101, 1100001, 11110001

Mẫu thứ 2 là 2^k+1. Mẫu đầu tiên là 2^k-1. Nếu bạn chọn mẫu thứ 2 và thử chia ra 2^k+1 thừa số, điều này sẽ giảm thừa số hóa.

Các yếu tố là: 3^3 x 5^2 x 7 x 13 x 17 x (2^768+1)(2^384+1)(2^256+1)(2^192+1)(2^128+1)(2^96+1)(2^64+1)(2^48+1)(2^32+1)(2^24+1)(2^16+1)(2^12+1)(2^8+1)

Sau khi chia 2^k+1 thừa số lớn hơn, bạn còn lại 1044225=3^3 x 5^2 x 7 x 13 x 17 để yếu tố.

Lịch sử: Alan Turing và bẻ khóa cỗ máy Enigma. Như vậy:

Đây có phải là mối quan tâm thực sự khi thiết kế mật mã không? Liệu một tổ chức xấu xa có thể sử dụng một trong những người này để bẻ khóa mật mã (đối với bất kỳ mật mã hiện đại nào) không?

Có, miễn là bạn có thể tìm thấy Alan Turing của mình và cung cấp những gì cần thiết (hoặc xây dựng nó từ đầu, như trường hợp của "quả bom" máy Enigma).

Không, nếu bạn nghĩ rằng Alan Turing của bạn sẽ làm điều đó bằng giấy và bút chì.

Trên thực tế, nếu bạn có thể tìm được một người am hiểu về bao thanh toán, thì đó sẽ là bằng chứng cho thấy p=np (hoặc một vụ gian lận lớn đang được thực hiện bằng chi phí của bạn), tôi sẽ đặt cược một số tiền lớn vào trường hợp thứ hai.