it-swarm-id.com

Memecahkan generator kongruensial linier

Saya baru-baru ini mendengarkan keamanan sekarang podcast, dan mereka menyebutkan secara sepintas bahwa generator congrunential linear (LCG) sepele untuk dipecahkan. Saya menggunakan LCG di kelas komputasi statistik tahun pertama dan berpikir bahwa memecahkannya akan membuat masalah "ekstra" yang bagus.

Apakah ada cara yang bagus untuk memecahkan LCG yang tidak melibatkan kekerasan?


Saya tidak yakin apakah pertanyaan ini adalah PL, tetapi saya tidak yakin di mana lagi harus mengirim pertanyaan. Selain itu, tag saya tidak terlalu membantu karena saya tidak punya cukup tenaga untuk membuat tag baru.

34
csgillespie

Iya. Ada cara yang sangat efisien untuk memutus generator kongruensial linier.

Generator kongruensial linier didefinisikan oleh sn +1 = a sn + b mod m, di mana m adalah modulus. Dalam bentuknya yang paling sederhana, generator hanya mengeluarkan sn sebagai nnomor acak acak. Jika m diketahui oleh penyerang dan a, b tidak diketahui, maka Thomas menjelaskan cara memecahkannya.

Jika tidak ada a, b, m diketahui, orang masih dapat memecahkan generator kongruensi linear, dengan terlebih dahulu memulihkan m. Ini adalah latihan yang menarik untuk mendapatkan cara melakukannya secara efisien; itu bisa dilakukan. Saya akan menunjukkan caranya di bawah ini; jangan baca jika Anda lebih suka mencoba mencari tahu sendiri.

Untuk memulihkan m, tentukan tn = sn +1 - sn dan n = |tn + 2 tn - t2n +1|; maka dengan probabilitas tinggi Anda akan memiliki m = gcd (kamu1, kamu2, ..., kamu10). 10 di sini arbitrer; jika Anda membuatnya k, maka kemungkinan kegagalan ini secara eksponensial kecil dalam k. Saya dapat membagikan petunjuk mengapa ini berhasil, jika ada yang tertarik.

Pelajaran penting adalah bahwa generator kongruensial linier adalah tidak aman tak dapat dihilangkan dan sama sekali tidak cocok untuk penggunaan kriptografi.


Ditambahkan: @AviD akan lebih membenci saya :), tapi inilah perhitungannya mengapa ini berhasil, bagi mereka yang memintanya.

Gagasan kunci: tn +1 = sn +1 - sn = (a sn - b) - (an-1 - b a sn - sebagain-1 = a tn) == mod m, dan tn + 2 = a2 tn mod m, dan tn + 3 = a3 tn mod m. Karena itu tn + 2 tn - tn +12 = 0 mod m, mis., |tn + 2 tn - tn +12| adalah kelipatan acak m. Fakta teori angka bagus: gcd dua kelipatan acak m akan m dengan probabilitas 6/π2 = 0,61; dan jika Anda mengambil gcd dari k dari mereka, probabilitas ini menjadi sangat dekat dengan 1 (secara eksponensial cepat dalam k). Apakah itu keren, atau apa?

36
D.W.

Generator kongruensial linier adalah linear, yang seharusnya mengatakan semuanya.

Yaitu, Anda memiliki status s, yang diperbarui dengan: s ← sebagai + b mod w, untuk dua konstanta a dan b, dan modulus yang nyaman w (biasanya 232: s, a dan b adalah 32-bit kata); output terdiri dari nilai berturut-turut s. Jika Anda memiliki tiga output berturut-turut (s, s1 dan s2), maka Anda mendapatkan dua persamaan linear dalam dua yang tidak diketahui (a dan b), yang mudah diselesaikan dengan aritmatika dasar.

Ini dapat diperluas ke varian di mana Anda hanya mendapatkan bagian dari nilai s, mungkin tidak berturut-turut. Jika a dan b adalah dua konstanta 32-bit, Anda hanya membutuhkan sekitar 96 bit nilai output untuk mengkomputasi ulang konstanta.

18
Thomas Pornin

Metode penyelesaian lain untuk m berasal dari ini kertas .

Pada dasarnya, metode ini mengeksploitasi fakta bahwa generator kongruensial linier secara dramatis gagal dalam tes pesawat. Penentu matriks 3x3 menggunakan 4 output adalah kelipatan dari m .

Gcd dua kelipatan ( n_1 dan n_2 dari m adalah m jika x_1 = n_1 / m dan x_2 = n_2 / m adalah co-prime.

Probabilitas bahwa k bilangan bulat adalah co-prime diberikan oleh 1/ζ (k) sehingga probabilitas bahwa x_1 dan x_2 adalah co-prime adalah 1/ζ (2) atau 6/π ^ 2, sekitar 61%.

Seperti @Thomas berkata, sekali m ditemukan sisa masalahnya mudah.

3
Jon Takagi