Một thẻ đã tồn tại với tên chi nhánh được cung cấp. Nhiều lệnh Git chấp nhận cả tên thẻ và tên nhánh, vì vậy việc tạo nhánh này có thể gây ra hành vi không mong muốn. Bạn có chắc chắn muốn tạo nhánh này không?
Trong bài đăng đầu tiên của tôi trên blog này, tôi muốn mở rộng phạm vi chủ đề của nó sang mật mã học ứng dụng và chia sẻ một số phát hiện mới thú vị mà cho đến nay chưa được báo cáo ở bất kỳ nơi nào khác ngoại trừ cuộc nói chuyện về phiên thảo luận của Eurocrypt'12
Vào ngày lễ tình nhân đầu năm nay, bài báo có tiêu đề hơi bí ẩn “Ron đã sai, Whit đúng” đã xuất hiện dưới dạng bản in sẵn trên trang web của IACR. Tất nhiên, nó không cáo buộc rằng Ron [Rivest] đã làm điều gì đó sai trái khủng khiếp mà Whit [Diffie] đã không làm, mà đúng hơn là một số người đã tạo ra các khóa RSA đã làm sai điều gì đó. Các tác giả của bài báo, Lenstra et al. , đã đưa ra một thông báo đáng ngạc nhiên rằng họ đã quản lý để tạo ra nhiều mô-đun RSA được thu thập từ web
Việc tính một số RSA 1024 bit duy nhất là khó, vượt xa nguồn lực của một nhóm nghiên cứu [kỷ lục thế giới công khai đã tính một số 768 bit vào năm 2010, yêu cầu khoảng 2000 năm lõi CPU; tính một số 1024 bit . Mặt khác, việc phân tích hai mô đun RSA sẽ dễ dàng nếu chúng có chung thừa số nguyên tố, bằng cách tính ước số chung lớn nhất của chúng
Lenstra và cộng sự. phát hiện ra rằng hơn mười nghìn mô-đun RSA được thu thập từ nhiều nguồn [chủ yếu là X. 509 từ web và khóa PGP] đã chia sẻ thừa số nguyên tố với ít nhất một mô-đun khác trong tập dữ liệu đó, cho phép bất kỳ ai, không chỉ chủ sở hữu chứng chỉ, tính các số đó
Tin tức đã được các phương tiện truyền thông đưa tin rộng rãi bao gồm cả The New York Times, nhưng tôi đặc biệt thích phản ứng của Nadia Heninger trên blog Freedom to Tinker. Cô ấy đã đưa một số tuyên bố giật gân từ báo chí vào bài đăng của mình với cái tên tự giải thích “Nghiên cứu mới. Không cần phải lo lắng về các khóa có thể sử dụng được—chỉ cần lưu ý đến Ps và Qs của bạn. ” Bài báo cũng là chủ đề của một số lời nói đùa thân thiện của Whitfield Diffie, Ron Rivest và Adi Shamir trong Hội đồng các nhà mật mã học từ Hội nghị RSA, có thể xem [tối thiểu 2–10]
Bản gốc Lenstra et al. bài báo đã cẩn thận không tiết lộ nhiều chi tiết cần thiết để giải thích hoặc sao chép những phát hiện của họ nhằm bảo vệ các hệ thống bị xâm nhập. Nó tự nhiên khơi dậy sự tò mò của các đồng nghiệp của tôi, những người đã quyết định sao chép kết quả của bài báo trên bộ dữ liệu có sẵn cho chúng tôi [ví dụ về hiệu ứng Streisand?]. Chúng tôi cũng muốn xác minh rằng các khóa riêng của Microsoft không có trong bộ nhân tố
Sau đây là phần tóm tắt về công việc chung của Martín Abadi, Andrew Birrell, Ted Wobber, bản thân tôi [Ilya Mironov] và một số người khác trong Microsoft. Vì các nhà cung cấp và quản trị viên của các hệ thống dễ bị tổn thương đã được các nhóm EPFL và UCSD thông báo, chúng tôi không nghĩ rằng ấn phẩm này khiến bất kỳ ai gặp rủi ro. Phần đầu tiên của bài đăng bao gồm thuật toán để thực hiện tính toán GCD hàng loạt và trong phần thứ hai, chúng tôi xem xét lại một số lý thuyết đã được đưa ra để giải thích hiện tượng lặp lại các số nguyên tố. Chúng tôi cũng sẽ mô tả một thuộc tính lấy dấu vân tay gây tò mò của thư viện OpenSSL, khám phá của nó là tài sản thế chấp cho nỗ lực chính của chúng tôi
Đầu tiên chúng ta hãy thiết lập một số ký hiệu. Đặt là các mô-đun RSA riêng biệt. Chúng tôi muốn tìm tất cả các mô-đun từ tập hợp này chia sẻ một yếu tố không tầm thường với những người khác. Một cách để thực hiện nó là tính toán tất cả theo cặp .
Để giúp bạn hình dung về quy mô của hoạt động này, đây là một số con số cụ thể. Chúng tôi có quyền truy cập vào tập dữ liệu [ảnh chụp nhanh của Đài quan sát SSL EFF từ giữa năm 2010] với khoảng 4. 4 triệu khóa RSA riêng biệt, hầu hết tất cả đều có độ dài 1024 hoặc 2048 bit. Tính toán GCD của hai số 1024 bit mất khoảng trên 2. Intel Core i7 93 GHz, do đó, việc tính toán tất cả các GCD thông minh theo cặp mất khoảng 5 năm lõi CPU—một nhiệm vụ có thể thực hiện dễ dàng trong vài ngày trên một cụm có kích thước vừa phải. Trên thực tế, song song với công việc được mô tả bên dưới, chúng tôi đã làm được điều đó—xét cho cùng, một trong những đặc quyền khi làm việc cho Microsoft là khả năng tiếp cận cơ sở hạ tầng máy tính khổng lồ. Về mặt tiệm cận, việc tính toán một GCD duy nhất gồm hai số bit cần [tất nhiên, có tồn tại các phương pháp GCD bậc hai nhưng đối với of interest they don’t do better than Lehmer’s algorithm]. Computing all pair-wise GCDs takes time , một nỗ lực bậc hai. Hóa ra chúng ta có thể làm tốt hơn thế nhiều, xác định các mô đun chia sẻ các yếu tố không tầm thường với các yếu tố khác trong thời gian gần như tuyến tính.
Lấy gợi ý từ bài đăng của Nadia, chúng tôi tính tích của tất cả các số rồi kiểm tra xem có chia thừa số với người khác hay không, kiểm tra xem < . .
Do đó, vấn đề được chia thành hai bước. Đầu tiên, chúng tôi tính toán tích của tất cả các mô-đun có kích thước lớn hơn 650 MByte. Làm xong việc đó, chúng ta sẽ tính GCD của con số khổng lồ này với tất cả bình phương.
Giai đoạn I. Trong một thế giới mà thói quen nhân tốt nhất hiện có là bậc hai [i. e. , nhân hai số có độ dài mất thời gian], tính toán tích khổng lồ sẽ là bậc hai theo độ dài . Chúng ta sẽ tận dụng phép nhân bậc hai để giảm đáng kể chi phí của bước này.
Quan sát quan trọng ở đây là trong khi phép nhân có tính liên kết, thì thời gian chạy của nó không phải là. Nói cách khác, tính toán tích nhanh hơn tính toán từ trái sang phải , nếu thuật toán nhân dài là bậc hai. Nói chung, việc tính toán tích của số bit có thể được thực hiện kịp thời bằng cách sử dụng phép nhân FFT, còn được gọi là thuật toán Schönhage-Strassen.
Để tận dụng phép nhân FFT đạt hiệu quả tối đa, chúng tôi muốn nhân các đầu vào cân bằng [i. e. , có kích thước gần bằng nhau] bất cứ khi nào có thể. Nó thúc đẩy việc tổ chức tính toán trong một cây, thường được gọi là cây sản phẩm. Để biết lịch sử từ năm 1958 và nhiều ứng dụng của cây tích trong lý thuyết số tính toán, hãy xem khảo sát của Dan Bernstein “Phép nhân nhanh và các ứng dụng của nó”. Ví dụ về cây sản phẩm trên tám số được đưa ra dưới đây
Vì phép nhân FFT của hai số -bit cần có thời gian , cấp độ cây đầu tiên sẽ mất < . , etc. All together there are cấp độ, mỗi cấp thực hiện bước, dẫn đến tổng số bước [giả sử ], which is a big, indeed huge, saving compared to the naïve algorithm.
Mặc dù việc triển khai FFT trong thư viện GMP không bắt đầu cho đến khi các con số trở nên lớn tới 500K bit, đây chính xác là nơi mà một thuật toán bậc hai chậm hơn sẽ dành phần lớn thời gian chạy của nó
Giai đoạn II. Khi chúng tôi tính toán sản phẩm khổng lồ bằng cách sử dụng cây nhị phân, chúng tôi sẽ làm gì với nó? . for all ’s, but doing it naïvely would again take quadratic time.
Đầu tiên, chúng tôi quan sát thấy rằng , vì vậy, thay vì tính toán GCD, trong đó một số rất lớn, trước tiên chúng tôi thực hiện modular reductions, followed by instances of -bit GCDs.
Chúng tôi sẽ sử dụng phương trình đơn giản , phương trình này gợi ý sử dụng cây nhị phân một lần nữa. Trên thực tế, chúng tôi có thể sử dụng cùng một cây được tính toán trong Giai đoạn I, chỉ lần này chúng tôi sẽ duyệt nó từ trên xuống dưới. Ở mức cao nhất, chúng tôi tính toán , điều này thật dễ dàng vì nó bằng . Sau đó, chúng tôi tính toán và bằng cách bình phương các nút bên trong của cây được tính toán trong Giai đoạn I. Ở mỗi cấp độ tiếp theo, chúng tôi lấy kết quả từ cấp độ trước đó và giảm nó theo modulo các nút bên trong của cây sản phẩm, bình phương. Độ dài của các con số giảm đi một nửa với mỗi cấp độ chúng ta đi xuống cây.
Phương pháp tính toán này được gọi là cây còn lại và được minh họa ở trên. Một lần nữa chúng tôi đề cập đến cuộc khảo sát của Dan Bernstein cho các ứng dụng và thư mục của nó
Giai đoạn III. Sau khi cây còn lại được xây dựng, chúng ta có thể tính toán . Đối với hầu hết của , nghĩa là là nguyên tố cùng nhau với tất cả các mô đun khác trong tập dữ liệu. Đối với một số [10.827 trong trường hợp của chúng tôi], chúng tôi có thể tính đến ngay lập tức nếu , vì trong trường hợp này là không . Điều đó sẽ quan tâm đến những mà một trong các thừa số nguyên tố của chúng được chia sẻ với một số mô đun khác. Nó để lại một thiểu số rất nhỏ [38 trong tập dữ liệu của chúng tôi] mà tất cả các thừa số nguyên tố của chúng xuất hiện ở một nơi khác và do đó . Đối với những con số đó, vì có rất ít trong số chúng, nên chúng tôi có thể chỉ tính toán GCD của chúng với tất cả các có thể phân tích được.
Vì việc giảm mô-đun cần thời gian tỷ lệ thuận với phép nhân, nên thời gian chạy của Giai đoạn II gần giống như thời gian của Giai đoạn I. hằng số quan trọng. Trong quá trình triển khai của chúng tôi, Giai đoạn I mất khoảng 20 phút, Giai đoạn II khoảng 10 giờ và Giai đoạn III vài giây trên một lõi đơn. Thách thức triển khai chính là tìm một máy có đủ bộ nhớ để vừa với cây sản phẩm trong RAM [mức sử dụng bộ nhớ đạt đỉnh là 29 GB], mặc dù việc tổ chức tính toán cẩn thận hơn có thể giảm chi phí bộ nhớ xuống một hệ số không đổi so với kích thước của đầu vào
So sánh nó với 5 năm lõi CPU theo yêu cầu của tính toán GCD thông minh theo cặp và lần tới khi bạn biết rằng phép nhân FFT không liên quan đến các ứng dụng ["stunt"], chẳng hạn như điện toán to 10 trillion decimal digits, don’t count], refer the skeptic to this post.
Chúng tôi đã triển khai và chạy thuật toán được mô tả ở trên trên bộ sưu tập chứng chỉ của mình. Đúng như dự đoán, chúng tôi đã tìm thấy nhiều mô đun có thể nhân tố hóa [không có mô đun nào của Microsoft], xác nhận những phát hiện chính của Lenstra et al. Tập dữ liệu của chúng tôi nhỏ hơn một chút so với Lenstra et al. ’s nhưng đủ gần để hiểu rõ hơn về nguyên nhân cơ bản của lỗ hổng này. Trong phần thứ hai của bài đăng này, chúng tôi sẽ kiểm tra một số lời giải thích hợp lý cho trường hợp kỳ lạ lặp lại các số nguyên tố và đưa ra một số lời giải thích của riêng chúng tôi.