Generator angka acak menggunakan pin GPIO?

22

Saya baru saja membaca pertanyaan AVR Random Number Generator dan menemukan sejumlah cara untuk menghasilkan benih acak dalam AVR:

  • Gunakan tujuan khusus "AVR Aman"
  • Gunakan sensor suhu internal
  • Baca EEPROM tidak tertulis
  • Ukur interval waktu antara input pengguna
  • Gunakan pin ADC mengambang.

Mengapa tidak hanya pin digital tunggal, yang dikonfigurasi sebagai input tanpa pull-up dan floating? Secara teori itu harus menghasilkan aliran bit acak. Kenapa tidak menggunakan ini? Apakah negara terlalu lambat berubah? Apakah cenderung macet pada 1 atau 0? Ada masalah lain?

Vorac
sumber
1
Secure AVR sudah mati AFAIK
vicatcu
1
Bukankah eeprom tidak tertulis selalu 0xFF?
vsz
@ vsz, mungkin jika Anda menulis sesuatu dan melupakan apa yang Anda tulis, itu "acak" sekarang. lol.
Vorac

Jawaban:

5

"Acak" adalah kata yang sulit. Dalam beberapa konteks, itu hanya berarti "tidak dapat diprediksi", tetapi dalam konteks lain - khususnya, yang terkait dengan pemrosesan sinyal dan kriptografi - itu berarti "tidak berkorelasi secara statistik".

Bahkan jika nilai yang dibaca dari floating pin tidak dapat diprediksi ("acak" dalam arti pertama), itu tidak mungkin berguna dalam arti kedua.

Dave Tweed
sumber
15

Perbedaan jelas antara menggunakan input digital, dan input analog, adalah bahwa ada rentang nilai seed yang lebih besar dalam analog.

Kedua, tetapi mungkin lebih penting: Jika nilai mengambang "median" pin digital tidak tepat di tengah-tengah antara tingkat logika (yang bukan daya dan tingkat rel tanah, tetapi beralih ambang batas untuk sirkuit input) bit stream yang dihasilkan akan memiliki Bias yang kuat terhadap 1 atau 0. Bias ini membuat benih jauh lebih kuat dari pada tingkat analog.

Dibutuhkan sedikit sambungan, baik dari jejak atau sinyal terdekat, atau melalui beberapa pull-up / pull-down resistif, baik yang dirancang atau tidak disengaja, untuk mendorong pin digital "mengambang" untuk tidak terangkat - dan itu bisa juga terjadi setelah penyebaran. Dalam rekayasa desain apa pun, bentuk mode kegagalan ini sebaiknya dihindari.

Anindo Ghosh
sumber
14

Input mengambang tidak terdefinisi. Ini bisa memberi Anda bit acak, tetapi juga bisa cenderung macet pada angka 0 atau 1. Sebagian besar waktu akan macet. Dan ketika benar-benar mengambang, itu dapat menyebabkan peningkatan kebisingan sistem dan konsumsi daya. Input mengambang umumnya merupakan hal yang buruk, bahkan ketika input tidak digunakan untuk apa pun.


sumber
Tidak hanya akan macet pada 0 atau 1 beberapa waktu, tetapi kecuali jika dua transistor yang membentuk tahap pertama dari buffer input seimbang dengan sempurna , atau ada beberapa sumber arus eksternal di jalan atau yang lain, input akan mengambang hingga 1 atau turun ke 0 pada akhirnya.
wjl
9

Solusi paling sederhana adalah membangun rangkaian generator sinyal acak perangkat keras dari rangkaian transistor kolektor terbuka yang disalahgunakan. Gunakan output bit-stream ke input pada micro-controller. Cicipi bit yang masuk secara berkala. Untuk memastikan angka 1s dan 0s secara kasar, gunakan saja perubahan status sebagai 1 dan tidak ada perubahan sebagai nol. Google untuk generator derau transistor untuk informasi lebih lanjut.

chris
sumber
Menarik. Seperti apa "rangkaian transistor kolektor terbuka yang disalahgunakan"?
Stephen Collings
7
@Remiel - Anda membalikkan bias basis-emitor dari transistor, dan berfungsi seperti zener yang benar-benar jelek. Anda mengambil zener yang sangat bising, dan Anda memperbesar suara untuk mendapatkan bitstream acak. Lihat robseward.com/misc/RNG2
Connor Wolf
3

Satu generator acak yang tersedia di banyak mikrokontroler adalah kesalahan antara dua sumber clock (mungkin satu internal dan eksternal lainnya). Ketika Anda membandingkannya, mereka sedikit melayang karena kebisingan dan itu dapat digunakan.

Pada akhirnya itu tergantung untuk apa Anda membutuhkannya? Sedikit pengacakan dan Anda bahkan dapat menggunakan pin ADC yang terhubung dengan apa pun. Atau cukup gunakan algoritma seperti

Mersenne twister http://en.wikipedia.org/wiki/Mersenne_twister

Tidak ada jika ini aman secara kriptografis, tetapi cukup baik untuk sebagian besar tujuan.

Gustavo Litovsky
sumber
itu adalah pendekatan yang diambil dalam catatan aplikasi msp430 dalam pertanyaan sebelumnya yang direferensikan, setahu saya sistem jam AVR tidak mendukung teknik ini
vicatcu
Benar. Seharusnya masih dimungkinkan untuk melakukannya dengan sumber jam yang sama, meskipun tidak didukung secara langsung.
Gustavo Litovsky
3

Kualitas benih acak dan algoritmanya ditentukan oleh jumlah entropi atau ketidakpastian di setiap bit acak. Kemudian generator terbaik dari benih menggunakan entropi tinggi dengan langkah yang sangat sedikit daripada banyak langkah dengan entropi rendah.

Contoh yang baik dari entropi tinggi menggunakan Kotak Latin metode untuk seed acak.

Input mengambang mudah bias oleh cacat, kebocoran atau kebisingan masuk.

Tony Stewart Sunnyskyguy EE75
sumber
0

Dalam mikroprosesor PIC18F Anda harus memiliki seed untuk nomor acak. Benih dapat berupa apa saja dari 0 hingga 32767 (15 bit). Saya akan menyarankan pada awal program Anda membuat salah satu pin dan pin input analog. Baca pin ini dan ambil bit paling signifikan dan masukkan ke dalam variabel 16 bit. Kemudian geser variabel ke kiri dengan 1. Baca kembali pin dan letakkan LSB dari hasil ADC ke dalam bit pertama dari variabel tempat Anda menyimpan bit terakhir. Geser ke kiri lagi .....

Ulangi ini sampai Anda memiliki 15 bit dalam variabel Anda. Ini adalah nomor yang perlu Anda masukkan ke dalam benih Anda.

Setelah Anda melakukan ini, Anda bisa membuat pin input analog menjadi pin input digital dan mengaktifkan penarik lemah di atasnya, atau menjadikannya pin output digital. Salah satu dari mereka akan menghentikan pin ini mengambang.

portreathbeach
sumber