angka acak lebih enak jika sedikit ladaKami akan menggabungkan teori dengan praktik - kami akan menunjukkan bahwa meningkatkan entropi urutan acak adalah mungkin, setelah itu kami akan melihat kode sumber yang melakukan ini.
Saya benar-benar ingin menulis tentang fakta bahwa generasi nomor acak yang berkualitas tinggi, sangat entropis, sangat penting dalam memecahkan sejumlah besar masalah, tetapi ini mungkin berlebihan. Saya harap semua orang tahu ini dengan sangat baik.
Dalam mengejar angka acak berkualitas, orang menciptakan perangkat yang sangat cerdas (lihat, misalnya, di
sini dan di
sini ). Pada prinsipnya, sumber-sumber keacakan cukup baik dibangun ke dalam API sistem operasi, tetapi ini adalah masalah serius, dan cacing keraguan selalu memakan kita sedikit: apakah RNG yang saya gunakan cukup baik dan itu rusak ... katakanlah, oleh pihak ketiga?
Sedikit teori
Untuk mulai dengan, kami menunjukkan bahwa dengan pendekatan yang tepat, kualitas RNG yang ada tidak dapat diturunkan. Pendekatan yang benar dan paling sederhana adalah untuk melapisi urutan lain melalui operasi XOR pada urutan
utama . Urutan
utama mungkin, misalnya, RNG sistemik, yang kami anggap bagus, tetapi masih ada beberapa keraguan, dan kami memiliki keinginan untuk bermain aman. Sekuens
tambahan mungkin, misalnya, generator bilangan pseudo-acak, yang hasilnya terlihat bagus, tetapi kita tahu bahwa entropinya yang sebenarnya sangat rendah. Urutan yang
dihasilkan akan menjadi hasil dari penerapan operasi XOR ke bit dari urutan primer dan sekunder.
Nuansa yang signifikan: urutan primer dan sekunder harus independen satu sama lain. Artinya, entropi mereka harus diambil dari sumber yang berbeda secara fundamental, yang saling ketergantungan yang tidak dapat dihitung.
Ditunjukkan dengan
x bit berikutnya dari urutan utama, dan
y - bit yang sesuai dari yang tambahan. Bit dari urutan yang dihasilkan dilambangkan dengan
r :
r = x⊕y
Upaya pertama untuk membuktikan. Mari kita coba melalui entropi informasi
x ,
y dan
r . Kami menunjukkan probabilitas nol
x sebagai
p x0 , dan probabilitas nol
y sebagai
p y0 . Entropi informasi
x dan
y dihitung sesuai dengan rumus Shannon:
H
x = - (p
x0 log
2 p
x0 + (1 - p
x0 ) log
2 (1 - p
x0 ))
H
y = - (p
y0 log
2 p
y0 + (1 - p
y0 ) log
2 (1 - p
y0 ))
Nol dalam urutan yang dihasilkan muncul ketika ada dua nol atau dua unit pada input. Probabilitas nol r:
p
r0 = p
x0 p
y0 + (1 - p
x0 ) (1 - p
y0 )
H
r = - (p
r0 log
2 p
r0 + (1 - p
r0 ) log
2 (1 - p
r0 ))
Untuk membuktikan tidak berubahnya urutan utama, perlu untuk membuktikannya
Hr - Hx ≥ 0 untuk nilai
p x0 dan
p y0 . Saya tidak bisa membuktikannya secara analitis, tetapi perhitungan yang divisualisasikan menunjukkan bahwa peningkatan entropi membentuk permukaan yang halus, yang tidak akan berkurang di mana pun:
Sebagai contoh, jika kita menambahkan sinyal tambahan sangat miring dengan
p y0 = 0,1 ke sinyal utama miring c
p x0 = 0,3 (entropi 0,881), kita mendapatkan hasil
p r0 = 0,66 dengan entropi 0,925.
Jadi, entropi tidak bisa rusak, tetapi ini belum akurat. Oleh karena itu, upaya kedua diperlukan. Namun, melalui entropi kita juga bisa membuktikan. Skema (semua langkah cukup sederhana, Anda dapat melakukannya sendiri):
- Kami membuktikan bahwa entropi memiliki maksimum pada titik p 0 = 1/2.
- Kami membuktikan bahwa untuk setiap p x0 dan p y0, nilai p r0 tidak bisa lebih jauh dari 1/2 dari p x0 .
Upaya kedua untuk membuktikan. Melalui kemampuan menebak. Misalkan seorang penyerang a priori memiliki beberapa informasi tentang urutan primer dan sekunder. Kepemilikan informasi dinyatakan dalam kemampuan dengan beberapa probabilitas untuk menebak terlebih dahulu nilai
x ,
y dan, sebagai hasilnya,
r . Probabilitas menebak
x dan
y masing-masing dilambangkan dengan
g x dan
g y (dari kata guess). Bit dari urutan yang dihasilkan ditebak ketika kedua nilai ditebak dengan benar, atau ketika keduanya salah, sehingga kemungkinan menebak adalah ini:
g
r = g
x g
y + (1 - g
x ) (1 - g
y ) = 2 g
x g
y - g
x - g
y + 1
Ketika kita memiliki penebak yang sempurna, kita memiliki
g = 1. Jika kita tidak tahu apa-apa,
g adalah ... tidak, bukan nol, tapi 1/2. Ini persis probabilitas menebak ternyata jika kita membuat keputusan dengan melemparkan koin. Kasus yang sangat menarik adalah ketika
g <1/2. Di satu sisi, penebak seperti itu di suatu tempat di dalam dirinya memiliki data tentang nilai yang diprediksi, tetapi untuk beberapa alasan membalikkan hasilnya, dan dengan demikian
koin menjadi
lebih buruk . Harap ingat frasa "lebih buruk daripada koin", ini akan berguna bagi kami di bawah ini. Dari sudut pandang teori komunikasi matematis (dan, sebagai hasilnya, teori informasi kuantitatif yang akrab bagi kita), situasi ini tidak masuk akal, karena ini bukan teori informasi, tetapi teori disinformasi, tetapi dalam kehidupan kita memiliki situasi ini lebih sering daripada yang kita inginkan .
Pertimbangkan kasus pembatas:
- g x = 1 , mis., urutan x sepenuhnya dapat diprediksi:
g r = g x g y + (1 - g x ) (1 - g y ) = 1 g y + (1−1) (1 - g y ) = g y
Artinya, probabilitas menebak hasilnya sama dengan probabilitas menebak urutan tambahan. - g y = 1 : Mirip dengan yang sebelumnya. Probabilitas menebak hasilnya sama dengan probabilitas menebak urutan utama.
- g x = 1/2 , mis. urutan x benar - benar tidak dapat diprediksi:
g r = 2 g x g y - g x - g y + 1 = 2/2 g y - 1/2 - g y +1 = g y - g y + 1/2 = 1/2
Artinya, penambahan setiap urutan tambahan tidak merusak ketidakpastian sepenuhnya dari yang utama. - g y = 1/2 : Mirip dengan yang sebelumnya. Menambahkan urutan ekstra yang sama sekali tidak dapat diprediksi membuat hasilnya sama sekali tidak dapat diprediksi.
Untuk membuktikan bahwa menambahkan urutan tambahan ke yang utama tidak akan membantu penyerang, kita perlu mencari tahu dalam kondisi apa
gr mungkin lebih besar dari
g x , yaitu.
2 g
x g
y - g
x - g
y + 1> g
xPindahkan g
x dari sisi kanan ke kiri, dan g
y dan 1 ke kanan:
2 g
x g
y - g
x - g
x > g
y - 1
2 g
x g
y - 2 g
x > g
y - 1
Kami mengambil di sisi kiri 2g
x dari tanda kurung:
2 g
x (g
y - 1)> g
y - 1
Karena kita memiliki g
y kurang dari satu (kasus pembatas ketika g
y = 1, kita telah mempertimbangkan), kita mengubah g
y −1 menjadi 1 - g
y , tanpa lupa mengubah "lebih" menjadi "kurang":
2 g
x (1 - g
y ) <1 - g
yKurangi “1 - g
y ” dan dapatkan kondisi di mana menambahkan urutan tambahan akan meningkatkan situasi bagi penyerang untuk menebak:
2 g
x <1
g
x <1/2
Yaitu,
g r bisa lebih besar dari
g x hanya ketika menebak urutan utama
lebih buruk daripada koin . Kemudian, ketika prediktor kita terlibat dalam sabotase sadar.
Beberapa pertimbangan tambahan tentang entropi.- Entropi adalah konsep yang sangat mitologis. Informasi - termasuk. Ini sangat mengganggu. Seringkali, entropi informasi direpresentasikan sebagai semacam masalah halus yang hadir secara objektif dalam data atau tidak. Bahkan, entropi informasi bukanlah sesuatu yang hadir dalam sinyal itu sendiri, tetapi penilaian kuantitatif dari kesadaran a priori penerima pesan mengenai pesan itu sendiri. Artinya, ini bukan hanya tentang sinyal, tetapi juga tentang penerima. Jika penerima sama sekali tidak tahu tentang sinyal di muka, entropi informasi dari unit biner yang ditransmisikan adalah persis 1 bit, terlepas dari bagaimana sinyal itu diterima dan apa itu.
- Kami memiliki teorema penambahan entropi yang menyatakan bahwa total entropi sumber independen sama dengan jumlah entropi dari sumber-sumber ini. Jika kita menggabungkan urutan utama dengan yang tambahan melalui penggabungan, kita akan mempertahankan entropi dari sumber, tetapi akan mendapatkan hasil yang buruk, karena dalam tugas kita kita perlu mengevaluasi bukan total entropi, tetapi yang spesifik, dalam hal bit yang terpisah. Gabungan sumber memberi kita entropi spesifik dari hasil yang sama dengan rata-rata aritmatika dari entropi sumber, dan urutan tambahan yang lemah entropi secara alami memperburuk hasilnya. Penerapan operasi XOR mengarah pada fakta bahwa kami kehilangan beberapa entropi, tetapi kami dijamin memiliki entropi yang dihasilkan tidak lebih buruk daripada entropi maksimum dari persyaratan.
- Cryptographers memiliki dogma: menggunakan pseudo-random number generator adalah arogansi yang tidak termaafkan. Karena generator ini memiliki entropi spesifik kecil. Tetapi kami baru mengetahui bahwa jika semuanya dilakukan dengan benar, entropi menjadi satu tong madu yang tidak dapat dimanjakan oleh jumlah tar.
- Jika kita hanya memiliki 10 byte entropi nyata, tersebar di satu kilobyte data, dari sudut pandang formal, kita hanya memiliki 1% dari entropi spesifik, yang sangat buruk. Tetapi jika 10 byte ini dioleskan secara kualitatif, dan terlepas dari brute force, tidak ada cara untuk menghitung 10 byte ini, semuanya tidak terlihat begitu buruk. 10 byte adalah 2 80 , dan jika brute force kita per detik mencari melalui satu triliun opsi, kita akan memerlukan rata-rata 19 ribu tahun untuk belajar bagaimana menebak karakter berikutnya.
Seperti disebutkan di atas, entropi informasi adalah nilai relatif. Di mana, untuk satu subjek, entropi spesifik adalah 1, untuk yang lain itu mungkin 0. Selain itu, satu dengan 1 mungkin tidak memiliki cara untuk mengetahui keadaan sebenarnya. Sistem RNG menghasilkan aliran yang tidak dapat dibedakan bagi kita dari yang benar-benar acak, tetapi kita hanya bisa berharap itu benar-benar acak
untuk semua orang . Dan percayalah. Jika paranoia menunjukkan bahwa kualitas RNG utama mungkin tiba-tiba tidak memuaskan, masuk akal untuk melakukan lindung nilai dengan bantuan yang lain.
Menerapkan RNG penjumlahan dengan Python
from random import Random, SystemRandom from random import BPF as _BPF, RECIP_BPF as _RECIP_BPF from functools import reduce as _reduce from operator import xor as _xor class CompoundRandom(SystemRandom): def __new__(cls, *sources): """Positional arguments must be descendants of Random""" if not all(isinstance(src, Random) for src in sources): raise TypeError("all the sources must be descendants of Random") return super().__new__(cls) def __init__(self, *sources): """Positional arguments must be descendants of Random""" self.sources = sources super().__init__() def getrandbits(self, k): """getrandbits(k) -> x. Generates an int with k random bits."""
Contoh penggunaan:
>>> import random_xe
SystemRandom, yang dianggap benar, diambil sebagai aliran utama, dan sebagai aliran sekunder - standar PRNG Acak. Poinnya, tentu saja, tidak terlalu banyak. PRNG standar jelas bukan jenis suplemen yang layak dimulainya. Sebagai gantinya, Anda dapat menggabungkan dua RNG sistemik bersama-sama:
>>> myrandom2 = random_xe.CompoundRandom(SystemRandom(), SystemRandom())
Artinya, kebenaran dalam hal ini bahkan lebih sedikit (walaupun karena alasan tertentu Bruce Bruce merekomendasikan dalam Kriptografi Terapan untuk beberapa alasan), karena perhitungan di atas hanya berlaku untuk sumber independen. Jika sistem RNG dikompromikan, hasilnya juga akan dikompromikan. Pada prinsipnya, penerbangan yang mewah dalam mencari sumber entropi tambahan tidak dibatasi oleh apa pun (di dunia kita, gangguan jauh lebih umum daripada pesanan), tetapi sebagai solusi sederhana saya akan menawarkan HashRandom PRSP, juga diterapkan di perpustakaan random_xe.
PRSP didasarkan pada streaming hashing melingkar
Dalam kasus paling sederhana, Anda dapat mengambil sejumlah kecil data awal (misalnya, meminta pengguna untuk menghidupkan keyboard), menghitung hash mereka, dan kemudian menambahkan hash secara siklik ke input algoritma hash dan mengambil hash berikut. Secara skematis, ini dapat direpresentasikan sebagai berikut:
Kekuatan kriptografi dari proses ini didasarkan pada dua asumsi:
- Tugas mengembalikan data asli dari nilai hash sangat rumit.
- Menggunakan nilai hash, tidak mungkin mengembalikan keadaan internal algoritma hashing.
Setelah berkonsultasi dengan paranoid internal, ia mengakui asumsi kedua sebagai tidak perlu, dan oleh karena itu, dalam implementasi akhir dari PRNG, skema ini sedikit rumit:
Sekarang, jika penyerang berhasil mendapatkan nilai "Hash 1r", ia tidak akan dapat menghitung nilai "Hash 2r" yang mengikutinya, karena ia tidak memiliki nilai "Hash 2h" yang tidak dapat dikenali tanpa menghitung fungsi hash "melawan wol". Dengan demikian, kekuatan kriptografi dari skema ini sesuai dengan kekuatan kriptografi dari algoritma hashing yang digunakan.
Contoh penggunaan:
>>>
Secara default, algoritma SHA-256 digunakan. Jika Anda menginginkan sesuatu yang lain, Anda dapat mentransfer jenis algoritma hashing yang diinginkan ke konstruktor dengan parameter kedua. Sebagai contoh, mari kita membuat RNG komposit, meringkas berikut ini di tumpukan:
1. RNG sistemik (ini sakral).
2. Input pengguna diproses oleh algoritma SHA3-512.
3. Waktu yang dihabiskan untuk input ini diproses oleh SHA-256.
>>> from getpass import getpass >>> from time import perf_counter >>> from hashlib import sha3_512
Kesimpulan:- Jika kita tidak yakin dengan generator bilangan acak kita, kita bisa dengan mudah dan luar biasa murah menyelesaikan masalah ini.
- Memecahkan masalah ini, kita tidak bisa berbuat lebih buruk. Hanya lebih baik. Dan itu terbukti secara matematis.
- Kita tidak boleh lupa untuk mencoba memastikan bahwa sumber entropi yang digunakan independen.
Sumber perpustakaan ada di
GitHub .