it-swarm-vi.com

Bẻ khóa một máy phát đồng quy tuyến tính

Gần đây tôi đã nghe podcast về bảo mật và họ đã đề cập đến việc thông qua rằng trình tạo cộng hưởng tuyến tính (LCG) là không đáng kể để bẻ khóa. Tôi sử dụng LCG trong lớp tính toán thống kê năm đầu tiên và nghĩ rằng việc bẻ khóa nó sẽ tạo ra một vấn đề "thêm" thú vị.

Có cách nào hay để bẻ khóa LCG mà không liên quan đến vũ lực không?


Tôi không chắc câu hỏi này có phải là OT không, nhưng tôi không chắc nơi nào khác để đăng câu hỏi. Ngoài ra, các thẻ của tôi không hữu ích lắm vì tôi không có đủ đại diện để tạo các thẻ mới.

34
csgillespie

Đúng. Có những cách cực kỳ hiệu quả để phá vỡ một máy phát đồng quy tuyến tính.

Một bộ tạo đồng quy tuyến tính được định nghĩa bởi sn + 1 = a sn + b mod m, trong đó m là mô đun. Ở dạng đơn giản nhất, trình tạo chỉ xuất ra sn là nsố giả danh thứ. Nếu m được biết đến với kẻ tấn công và a, b không được biết, thì Thomas đã mô tả cách phá vỡ nó.

Nếu không có a, b, m được biết đến, người ta vẫn có thể phá vỡ một trình tạo đồng quy tuyến tính, bằng cách khôi phục đầu tiên m. Đó là một bài tập thú vị để rút ra cách làm như vậy một cách hiệu quả; nó có thể được thực hiện Tôi sẽ chỉ ra cách bên dưới; đừng đọc tiếp nếu bạn muốn tự mình tìm ra nó.

Để khôi phục m, xác định tn = sn + 1 - snn = |tn + 2 tn - t2n + 1|; sau đó với xác suất cao bạn sẽ có m = gcd (bạn1, bạn2, ..., bạn10). 10 ở đây là tùy ý; nếu bạn thực hiện nó k, thì xác suất thất bại này nhỏ theo cấp số nhân trong k. Tôi có thể chia sẻ một con trỏ về lý do tại sao điều này hoạt động, nếu bất cứ ai quan tâm.

Bài học quan trọng là trình tạo đồng quy tuyến tính là không thể bảo đảm an toànhoàn toàn không phù hợp để sử dụng mật mã.


Đã thêm: @AviD sẽ ghét tôi hơn nữa :), nhưng đây là phép toán tại sao nó hoạt động, cho những người yêu cầu nó.

Ý tưởng chính: tn + 1 = sn + 1 - sn = (một sn - b) - (một sn-1 - b a sn - nhưn-1 = một tn) == mod mtn + 2 = a2 tn mod mtn + 3 = a3 tn mod m. vì thế tn + 2 tn - tn + 12 = 0 mod m, tức là, |tn + 2 tn - tn + 12| là bội số ngẫu nhiên của m. Thực tế lý thuyết số tiện lợi: gcd của hai bội số ngẫu nhiên m sẽ là m với xác suất 6/π2 = 0,61; và nếu bạn lấy gcd của k trong số chúng, xác suất này sẽ rất gần với 1 (nhanh theo cấp số nhân tính theo k). Là mát mẻ, hoặc những gì?

36
D.W.

Một trình tạo đồng quy tuyến tính là tuyến tính, sẽ nói lên tất cả.

Cụ thể, bạn có trạng thái s, được cập nhật với: s ← as + b mod w, cho hai hằng số ab và mô-đun thuận tiện w (thường 232: s, ab là các từ 32 bit); đầu ra bao gồm các giá trị liên tiếp của s. Nếu bạn có ba đầu ra liên tiếp (s, s1s2), sau đó bạn nhận được hai phương trình tuyến tính trong hai ẩn số (ab), có thể dễ dàng giải bằng các phép tính sơ cấp.

Điều này có thể được mở rộng thành các biến thể trong đó bạn chỉ nhận được các phần của các giá trị s, có thể không liên tiếp. Nếu ab là hai hằng số 32 bit, bạn chỉ cần khoảng 96 bit giá trị đầu ra để tính toán lại các hằng số.

18
Thomas Pornin

Một phương pháp giải khác cho m xuất phát từ điều này giấy .

Về cơ bản, phương pháp này khai thác thực tế là máy phát đồng quy tuyến tính thất bại đáng kể trong thử nghiệm máy bay. Hệ số xác định của ma trận 3x3 sử dụng 4 đầu ra là bội số của m .

Gcd của hai bội số ( n_1 n_2 của m m nếu x_1 = n_1 / m x_2 = n_2 / m là đồng nguyên tố.

Xác suất mà số nguyên k là đồng nguyên tố được cho bởi 1/(k) nên xác suất x_1 x_2 là đồng nguyên tố là 1/(2) hoặc 6/π ^ 2, khoảng 61%.

Giống như @Thomas đã nói, một lần m được tìm thấy phần còn lại của vấn đề là dễ dàng.

3
Jon Takagi