AVR Random Number Generator

Saya telah membaca appnote dari TI ( slaa338 ) yang menjelaskan teknik untuk menghasilkan angka acak "nyata" (bukan "pseudo"). Itu mengeksploitasi subsistem jam agak eksotis dari MSP430 untuk mencapai tujuan ini. Adakah yang tahu teknik yang dapat diterapkan pada AVR (Saya tertarik pada XMega khususnya) untuk menghasilkan angka acak "nyata"?

Seberapa buruk Anda menggunakan XMega? Jika crypto dan pembangkitan angka acak adalah bagian besar dari proyek Anda, Atmel's seri SecureAVR memiliki nomor acak perangkat keras yang terpasang, dan dirancang untuk aplikasi kriptografi.

Apapun, saya ragu bahwa Anda akan menemukan sumber benih acak yang memiliki distribusi yang baik. Anda akan ingin menjalankannya melalui generator angka acak semu beberapa kali. Selama Anda mulai dengan seed yang berbeda setiap kali, ini akan memberi Anda satu set angka acak yang bagus. LGC adalah generator acak semu yang cepat dan mudah:

static unsigned long Seed; 

/* Call before first use of NextVal */
unsigned long InitSeed()
{
   //Your code for random seed here

   // Correct distribution errors in seed
   NextVal();
   NextVal();
   NextVal();
   return NextVal();
}

 /* Linear Congruential Generator 
  * Constants from  
  * "Numerical Recipes in C" 
  * by way of 
   * <http://en.wikipedia.org/wiki/Linear_congruential_generator#LCGs_in_common_use>
   * Note: Secure implementations may want to get uncommon/new LCG values
  */
unsigned long NextVal()
{
  Seed=Seed*1664525L+1013904223L;
  return Seed;
} 

Hubungkan ADC ke sumber derau perangkat keras dan gunakan perangkat lunak untuk "memutihkan" angka acak jika perlu.

Berikut adalah proyek berbasis AVR yang melakukan ini: Mini Portable Random Number Generator (mPRNG) Leon

Bergantung pada seberapa aman pengamanan kriptografi, Anda dapat menggunakan derau input analog yang di-ground atau " sensor suhu internal " sebagai seed randomness Anda alih-alih perangkat keras eksternal.

Pembaruan : Saya kemudian menulis sebuah program untuk Arduino yang menggunakan penghitung waktu chip sebagai sumber entropi (ADC ternyata tidak berguna karena bit yang berisik dipotong), dan ini mengilhami pembuatan perpustakaan Entropy .

Dalam kedua kasus, keacakan bukan dari, misalnya, nilai suhu itu sendiri, yang hanya berubah secara perlahan, tetapi dari bit yang paling signifikan , yang bervariasi secara acak dari satu pembacaan ke yang berikutnya. Saya membaca nilai beberapa kali, sekali untuk setiap bit output, bitshifting dan XORing dengan bacaan sebelumnya. XORing bit yang benar-benar acak dengan bit yang tidak berkorelasi menjaga keacakan , sehingga keacakan menyebar ke semua bit dan itu menjadi white noise benar. Namun, bit rate Anda tidak akan terlalu tinggi, karena Anda hanya mendapatkan satu bit output per waktu akuisisi atau siklus timer. Dengan metode timer, saya mendapatkan sekitar 64 bit / s.

Trik lain untuk menghasilkan seed secara acak, adalah menghitung jumlah siklus clock hingga peristiwa eksternal. Misalnya jika ini adalah perangkat yang akan digunakan oleh seseorang, hitung jumlah siklus jam sampai dia menekan tombol 'pergi', dan gunakan itu sebagai seed acak.

Untuk memastikan tidak memulai kembali dengan urutan yang sama, saya menggunakan byte somme di eeprom:

#include <avr/eeprom.h>
#include <stdlib.h> // rand

u16  EEMEM randinit; 

int main(void) {
        srand(eeprom_read_word(&randinit));
        eeprom_write_word(&randinit,rand());
        [...]
 }

Ini memberikan acak yang cukup baik, dan tidak membutuhkan biaya banyak dalam program / memori.

Saya telah membuat perpustakaan yang sementara asli dirancang untuk Arduino berfungsi dengan baik sebagai kelas dalam implementasi C ++ menggunakan g ++ pada avr, memang baru-baru ini porting ke arsitektur ARM juga.

Itu menggunakan jitter antara pengawas waktu dan jam sistem dan telah diuji pada sejumlah chip yang berbeda (didokumentasikan pada halaman wiki)

http://code.google.com/p/avr-hardware-random-number-generation/wiki/WikiAVRentropy

Pernahkah Anda melihat menggunakan sesuatu seperti randomSeed () ? - Digunakan dalam Arduino IDE

Anda dapat menggunakan fungsi ini untuk mencicipi pin analog mengambang (gratis) pada atmel AVR, yang kemudian menggunakan nilai untuk membuat titik awal sembarang untuk pseudo fungsi angka acak - acak ().

Nilai yang dibuat secara acak () bisa berupa angka acak semu - tetapi titik awal arbitrer yang dibuat oleh randomSeed () harus sama nyata dengan angka / nilai acak yang Anda bisa dapatkan.

Ada sebuah kertas tentang bagaimana mencapainya dengan perangkat keras AVR. Ini melibatkan mengandalkan jam jitter. Pada dasarnya, Anda menggunakan penghitung waktu berdasarkan dari satu sumber clock untuk mengambil sampel bit yang lebih rendah dari penghitung waktu yang terpisah yang mencatat sumber jam independen yang terpisah. Kedua jam akan memiliki beberapa jitter acak yang terkait dengannya dan pengambilan sampel tidak akan sempurna secara berkala.

Saya melakukan sedikit bukti konsep ini pada mikrokontroler STM32, kode ada di github di sini . Itu mendapat beberapa hasil yang baik berdasarkan satu set suite tes pengacakan.

Menurut pendapat saya, saya pikir ini lebih baik daripada mengambil sampel floating pin dengan ADC yang sangat mudah diserang (ikat pin ke ground dan nomor Anda tidak begitu acak lagi!). Saya yakin ada cara untuk memanipulasi clock jitter berbasis RNG, tetapi itu membuat saya merasa sedikit lebih baik bahwa saya dapat melakukan ini murni berdasarkan pada sumber clock internal on-chip.