it-swarm-vi.com

Làm cách nào để ước tính thời gian cần thiết để bẻ khóa mã hóa RSA?

Làm cách nào để ước tính thời gian cần thiết để bẻ khóa mã hóa RSA? Ý tôi là thời gian cần thiết để bẻ khóa mã hóa Rsa với độ dài khóa 1024, 2048, 3072, 4096, 5120, 6144, 5120, 7168, 8192, 9216, 10240, 11264, 12288, 13312, 14336, 15360, và 16384?

67
Predator

Xem trang web này để biết tóm tắt về các ước tính sức mạnh chính được sử dụng bởi các nhà nghiên cứu và tổ chức khác nhau.

"512 bit trong 12 giây" của bạn hoàn toàn không có thật. Chúng ta hãy xem nó đến từ đâu. 1999 là năm mà hệ số tổng quát 512 bit đầu tiên được thực hiện, trên một thách thức được công bố bởi RSA (công ty) và được gọi là RSA-155 (vì số này bao gồm 155 chữ số thập phân - ở dạng nhị phân , độ dài là 512 bit). Hệ số đó mất 6 tháng. Tại sự kiện Eurocrypt được tổ chức cùng năm (vào tháng 5; tại thời điểm đó, nỗ lực nhân tố 512 bit đã bắt đầu nhưng chưa hoàn thành), Adi Shamir , từ Weizmann Viện, đã trình bày một thiết bị lý thuyết có tên TWINKLE mà, được cho là, có thể giúp ích khá nhiều trong nỗ lực nhân tố hóa. Nó nên bao gồm một số lượng lớn các điốt nhấp nháy ở tần số được lựa chọn cẩn thận, trong một loại ống đen. Shamir mang một thiết bị tùy chỉnh, cách đó 10 mét, trông giống như một máy pha cà phê. Anh ta yêu cầu mọi người tắt đèn, để người tham dự Eurocrypt có thể ngạc nhiên với bốn điốt đỏ nhấp nháy ở các khoảng 2, 3, 5 và 7 giây. Ôi! và Aah! họ đã đi, mặc dù máy thực tế, sẽ được chế tạo, sẽ cần vài triệu điốt và tần số trong 10 hoặc 100 gigahertz. Vì vậy, ý tưởng này rất thú vị (ít nhất là đối với các nhà nghiên cứu về mật mã học, những người được biết đến là người có khiếu hài hước kỳ lạ) nhưng vẫn chưa vượt qua bước phác thảo lý thuyết. Shamir là một người trình diễn tuyệt vời.

Tuy nhiên, TWinkLE chỉ là "trợ giúp". Thuật toán nhân tố được biết đến nhiều nhất được gọi là Sàng trường số chung ; hai thuật toán tiếp theo là Quadratic SàngPhương pháp đường cong Elliptic . Một số 512 bit nằm ngoài tầm với của QS và ECM với công nghệ ngày nay và một fortiori với công nghệ của năm 1999. GNFS rất phức tạp (nói một cách toán học), đặc biệt vì nó yêu cầu lựa chọn cẩn thận một số tham số quan trọng ("lựa chọn đa thức"). Vì vậy, phải có một nỗ lực ban đầu bởi bộ não rất thông minh (với máy tính lớn, nhưng bộ não là quan trọng nhất ở đây). Sau đó, GNFS bao gồm hai phần, sàng giảm tuyến tính. Rây có thể được chế tạo song song trên hàng trăm hoặc hàng nghìn máy, vẫn phải tương đối lớn (trong RAM), nhưng điều này là có thể thực hiện được. Việc giảm tuyến tính liên quan đến việc tính toán mọi thứ với một ma trận quá lớn để phù hợp với máy tính (theo một số bậc độ lớn và ngay cả khi chúng ta cho rằng máy tính nói trên có terabyte RAM nhanh). Có các thuật toán để giữ ma trận (khá thưa thớt) ở định dạng nén và vẫn có thể tính toán trên đó, nhưng điều này thật khó. Trong hệ số nhân đôi 512 bit, sàng chiếm khoảng 80% tổng thời gian, nhưng đối với số lượng lớn hơn thì việc giảm tuyến tính là nút cổ chai.

TWinkLE chỉ là về việc tăng tốc phần sàng. Nó không làm gì về việc giảm tuyến tính. Nói cách khác, nó tăng tốc phần dễ dàng (nói tương đối). Ngay cả một nửa sàng được tăng cường TWinkLE sẽ không ở đâu gần 12s. Thay vào đó, nó sẽ giúp mang lại một nỗ lực sàng lọc bốn tháng xuống, nói, ba tuần. Điều này là tốt, theo một cách khoa học, nhưng không phải là một phá vỡ kỷ lục, đặc biệt là khi giảm tuyến tính chiếm ưu thế cho kích thước lớn hơn. Con số 12 dường như đến từ một sự nhầm lẫn với một con quái vật thậm chí còn thần thoại hơn, Máy tính lượng tử , có thể dễ dàng tạo ra những con số lớn nếu có thể xây dựng QC với 512 "qubit". D-Wave gần đây đã công bố một máy tính lượng tử với 128 qubit, nhưng hóa ra đó là những qubit không "thật" và chúng không phù hợp với yếu tố hóa (về mặt lý thuyết, chúng vẫn có thể làm được một số xấp xỉ hiệu quả trong các vấn đề tối ưu hóa, rất tuyệt nhưng về cơ bản không áp dụng được cho mật mã, bởi vì các thuật toán mật mã không thể tuân theo các phép gần đúng - chúng được thiết kế sao cho một bit sai làm xáo trộn toàn bộ). QC "thực" tốt nhất cho đến nay dường như là nguyên mẫu của IBM, theo như tôi nhớ, có 5 qubit, cho phép nó xác định rằng 15 bằng 3 lần 5.

Bản ghi nhân tố RSA hiện tại là số nguyên 768 bit , được công bố vào tháng 12 năm 2009. Phải mất bốn năm và liên quan đến các nhà lý thuyết số thông minh nhất hiện đang sống trên Trái đất, bao gồm Lenstra và Montgomery, người có phần thần thánh giống như trạng thái trong những vòng tròn đó. Gần đây tôi đã biết rằng việc lựa chọn các tham số cho hệ số hóa 1024 bit đã bắt đầu (đó là phần "cân não"); Việc sàng là khả thi về mặt kỹ thuật (sẽ tốn kém và liên quan đến nhiều năm tính toán trên nhiều cụm trường đại học), nhưng hiện tại, không ai biết cách thực hiện phần giảm tuyến tính cho số nguyên 1024 bit. Vì vậy, đừng mong đợi một sự phá vỡ 1024 bit bất cứ lúc nào sớm.

Ngay bây giờ, một người nghiệp dư chuyên dụng sử dụng mã được xuất bản (ví dụ Msieve ) có thể đạt được hệ số 512 bit nếu anh ta có quyền truy cập vào các máy tính mạnh (vài chục PC lớn và ít nhất một đồng hồ đầy RAM nhanh ) và một vài tháng rảnh rỗi; về cơ bản, "nghiệp dư chuyên dụng" có nghĩa là "sinh viên khoa học máy tính chán trong một trường đại học giàu có". Bất cứ điều gì ngoài 512 bit là ngoài tầm với của một người nghiệp dư.

Tóm tắt: trong mã của bạn, bạn có thể trả về "thực tế vô hạn" dưới dạng thời gian bẻ khóa cho tất cả các độ dài khóa. Một người dùng thông thường sẽ không phá khóa RSA 1024 bit, không phải bây giờ và không trong mười năm nữa. Có khoảng một chục người trên Trái đất có thể, với bất kỳ sự tin cậy nào, cho rằng điều đó có thể hiểu được, với xác suất thấp nhưng khác không, rằng họ might có thể tính được một 1024- số nguyên bit tại một số thời điểm không xác định trước năm 2020.

(Tuy nhiên, cực kỳ dễ dàng để thực hiện triển khai RSA hoặc bất kỳ ứng dụng nào sử dụng RSA theo cách mà dữ liệu bí mật mà nó lưu giữ có thể được phục hồi mà không cần bận tâm đến khóa RSA. Nếu bạn sử dụng khóa RSA 1024 bit, bạn có thể chắc chắn rằng khi ứng dụng của bạn bị hack, nó sẽ không thông qua hệ số khóa RSA.)

90
Thomas Pornin

Câu trả lời ngắn : Phương pháp đơn giản nhất là sử dụng định lý số nguyên tố , nhưng lưu ý rằng đó là một xấp xỉ. Ước tính bạn sẽ mất bao lâu để thử từng số nguyên tố đó; thời gian trên mỗi số nguyên tố * số nguyên tố cung cấp cho bạn tổng thời gian. Điều này sẽ cung cấp cho bạn một ước tính cho tìm kiếm vũ phu.

Bạn cũng có thể sử dụng ước tính thời gian chạy cho sàng sàng bậc hai hoặc sàng số trường chung . Điều này sẽ cung cấp cho bạn các ước tính cho các thuật toán bao thanh toán thực sự được sử dụng bởi những người phá vỡ số RSA.

Nền dài :

Số lý thuyết thời gian!

Đầu tiên, chúng ta hãy xem kích thước của những con số bạn đang nói đến. Cho 2 ^ 3 = 8, là 1000 ở dạng nhị phân, chúng ta có thể thấy đây là một số có bốn bit, mức tối thiểu như vậy là có thể. Vậy, 2 ^ 2 = 4 là số 3 bit (100). Vì vậy, với một x đã cho, giá trị tối thiểu có thể có để đảm bảo chúng ta có đủ bit là 2 ^ (x-1). 2 ^ 2047 = 16158503035655503650357438344334975980222051334857742016065172713762327569433945446598600705761456731844358980460949009747059779575245460547544076193224141560315438683650498045875098875194826053398028819192033784138396109321309878080919047169238085235290822926018152521443787945770532904303776199561965192760957166694834171210342487393282284747428088017663161029038902829665513096354230157075129296432088558362971801859230928678799175576150822952201848806616643615613562842355410104862578550863465661734839271290328348967522998634176499319107762583194718667771801067716614802322659239302476074096777926805529798115328. Đó là kích thước của số bạn đang làm việc với ở đây, ví dụ: kích thước của n được yếu tố.

Câu hỏi lớn tiếp theo là n được xây dựng như thế nào? n=pq Như bạn đã biết từ định nghĩa của RSA, vì vậy bạn đang tìm kiếm hai số nguyên tố là các yếu tố của số đó. Câu hỏi sau đó trở thành cách chúng ta xác định một số là số nguyên tố và chúng ta có thể đếm chúng không?

Vì vậy, theo định nghĩa, một số là không thể giảm nếu, với bất kỳ số nào x nhỏ hơn số đó, \gcd(p, x) = 1 ngoại trừ x=1. Tuy nhiên, chúng ta có thể cải thiện điều đó. Bạn nên nhận ra khá nhanh rằng với bất kỳ số nào, nó là số nguyên tố hoặc không. Nếu nó không phải là số nguyên tố thì gcd của nó và ít nhất một số nguyên tố phải lớn hơn 1 (nếu không nó sẽ là số nguyên tố). Chúng tôi kết luận rằng bất kỳ số nguyên không nguyên tố nào cũng phải chia hết cho một tập hợp các số nguyên tố. Một bằng chứng toán học chính thức không thực sự là một bước nhảy vọt từ đây.

Đây được gọi là định lý cơ bản của arithemtic và đơn giản hóa các vấn đề một chút. Vì vậy, bây giờ, khi làm việc nếu một số là số nguyên tố, chúng ta không còn cần phải thử mọi số, chỉ những số chúng ta đã biết là số nguyên tố!

Điều này rõ ràng vẫn còn rất chậm, vì vậy hãy thực hiện một quan sát khác - các yếu tố đã cho xảy ra theo cặp, phần dưới của hai số nhiều nhất là căn bậc hai của số. Nếu chúng ta bị giới hạn ở N (tập hợp các số tự nhiên), nó đại diện cho giới hạn trên của giá trị lớn nhất có thể chúng ta cần kiểm tra. Vì vậy, bây giờ, đối với bất kỳ số N nào, chúng ta phải tìm kiếm từng số nguyên bắt đầu từ 2 và hướng đến sqrt (N) cho mỗi số chúng ta xác định là số nguyên tố trong danh sách đó. Chúng ta có thể sau đó, nếu chúng ta tìm thấy một số nguyên tố, suy ra liệu nó có phải là yếu tố N hay không. Tôi sẽ không ước tính thời gian chạy vì điều đó chắc chắn tôi sẽ nói sai, nhưng sẽ mất nhiều thời gian.

Bây giờ bạn thấy sức mạnh của RSA. Chọn một số nguyên tố rất lớn và bạn sẽ đi được một chặng đường dài. Vì hiện tại, chúng tôi phải bắt đầu từ 2, điều này rõ ràng là khủng khiếp.

Kiểm tra tính nguyên thủy nhằm mục đích cải thiện điều đó bằng cách sử dụng nhiều kỹ thuật khác nhau. Phương pháp ngây thơ là phương pháp chúng ta vừa thảo luận. Tôi nghĩ rằng một cuộc thảo luận chi tiết về các kỹ thuật này có lẽ phù hợp hơn với môn Toán, vì vậy hãy để tôi tổng hợp lại: tất cả các thời gian chạy đều là rác rưởi và sử dụng nó như một cách để đếm các số nguyên tố sẽ rất tệ.

Vì vậy, chúng ta không thể đếm số lượng các số nguyên tố ít hơn một số mà không mất mãi mãi, vì nó thực sự tương tự như hệ số nguyên. Điều gì về một chức năng bằng cách nào đó đếm số nguyên tố theo cách khác?

Nhập \pi(n) = \frac{n}{\log(n) - 1.08366}, một lần thử tại Định lý số nguyên tố gần đúng với số lượng các số nguyên tố. Đó là, tuy nhiên, chính xác đó; Mục đích của một chức năng như vậy là để đếm chính xác số lượng các số nguyên tố nhưng hiện tại nó chỉ đơn giản là cung cấp cho bạn một ước tính. Đối với mục đích của bạn, điều này có thể được coi là đủ tốt.

Tuy nhiên, nó hoàn toàn vẫn là một xấp xỉ. Hãy xem phần còn lại của bài viết. Trong số những thứ khác, các ước tính khác phụ thuộc vào Giả thuyết Riemann.

Ok, vậy còn hệ số nguyên ? Chà, phương pháp tốt thứ hai cho đến nay được gọi là Quadratic Sàng và phương pháp tốt nhất được gọi là sàng số trường chung . Cả hai phương pháp này đều chạm vào một số toán học khá tiên tiến; giả sử bạn nghiêm túc về các số nguyên tố bao thanh toán, tôi sẽ đọc những thứ này. Chắc chắn bạn sẽ có thể sử dụng các ước tính cho cả hai để cải thiện việc sử dụng định lý số nguyên tố, vì nếu bạn định tính các số nguyên tố lớn, bạn muốn sử dụng các ước tính này chứ không phải tìm kiếm vũ lực.

Nhưng tôi muốn biết về lượng tử?

Được rồi. Hệ số nguyên trên máy tính lượng tử có thể được thực hiện trong khoảng thời gian ngắn một cách lố bịch giả sử chúng ta sẽ có thể thực hiện Thuật toán của Shor . Tôi nên chỉ ra, tuy nhiên, điều này đòi hỏi một máy tính lượng tử. Theo như tôi biết, việc phát triển các máy tính lượng tử có quy mô có thể bẻ khóa RSA hiện đang là một lối thoát. Xem phát triển điện toán lượng tử .

Trong mọi trường hợp, Thuật toán của Shor sẽ nhanh hơn theo cấp số nhân. Trang trên đó cung cấp cho bạn ước tính về thời gian chạy của trang đó, mà bạn có thể muốn đưa vào ước tính của mình.

25
user2213

Một tùy chọn khác là tạo một cơ sở dữ liệu lớn về các khóa có thể và sử dụng nó làm bảng tra cứu. Rõ ràng bạn thậm chí không cần TẤT CẢ các số nguyên tố, chỉ một vài điều sẽ giúp bạn vượt qua một tỷ lệ lớn lưu lượng truy cập internet.

Nguồn: https://freedom-to-tinker.com/blog/haldermanheninger/how-is-nsa-breaking-so-much-crypto/

0
Evgeny