Використання генератора випадкових чисел Arduino: функції Random і RandomSeed. Курс Arduino - Час та Random Arduino генерація випадкової послідовності біт

При програмуванні Arduino бувають випадки, коли потрібно отримати число, яке заздалегідь не буде відоме ні програмісту, що пише скетч, ні користувачеві, який використовуватиме Arduino з такою програмою. У разі на допомогу приходить генератор випадкових (а точніше псевдовипадкових) чисел.

Для активації цього генератора достатньо використовувати функції random() або randomSeed(). У цьому матеріалі буде показано, як працювати з цими функціями, а також як позбутися псевдовипадковості при генеруванні чисел.

Взагалі генератор псевдовипадкових чисел імітує хаотичність чи випадковість появи чисел, але насправді, якщо аналізувати ряд цих чисел протягом досить тривалого періоду, можна помітити певну закономірність.

Отже, функція random для генерування псевдовипадкових чисел може мати два параметри і записуватися як random(max) або random(min, max). Тут параметр maxякий є обов'язковим, задає верхню межу діапазону генерації псевдовипадкових чисел. За допомогою додаткового параметра min можна встановити нижню межу діапазону. У результаті функція поверне якесь псевдовипадкове число у проміжку від min до max-1.

Важливо розуміти, що при використанні функції random() щоразу буде згенерований такий самий список псевдо випадкових чисел. Наприклад, якщо ви зробите ігровий автомат, і при першому натисканні ручки випаде виграшна комбінація, то ви можете бути впевнені, що якщо перезавантажте Arduino і натиснете на ручку ще раз, цей ігровий автомат покаже таку ж виграшну комбінацію. Справді, на Arduino не просто реалізувати ігровий апарат з цілком випадковою генерацією чисел, як це, наприклад, реалізовано в ігрових апаратах www.igrovye-apparati-vulcan.com/, але можна частково вирішити проблему за допомогою функції randomSeed().

Ця функція приймає значення (наприклад, цілечисленне), і використовує число, щоб змінити випадковий список, що генерується функцією random(). Але і в цьому випадку буде загвоздка, що полягає в тому, що хоча послідовність випадкових чисел буде відрізнятися при використанні функції randomSeed(), вона все одно буде такою ж кожного разу, коли запускатиметься скетч.

Єдиним рішенням у такому разі може бути варіант із застосуванням аналогової периферії (АЦП) та відповідної функції analogRead(). Якщо аналогове введення ні до чого не підключати, тобто залишити його «висіти» в повітрі, завдяки шуму на цій лінії можна отримати дійсно випадкові числа. Тоді в налаштуванні setup можна записати так randomSeed(analogRead(A0)). За умови, що аналоговий порт A0 нікуди не підключено.

Про генератори випадкових чисел написано дуже багато, але майже завжди, коли справа доходить до реалізації, мається на увазі (чи явно говориться), що мова йдепро x86/x64 та інші «дорослі» архітектури. У той же час, форуми, присвячені розробці пристроїв на мікроконтролерах, рясніють питаннями «як мені згенерувати випадкове число на %controllername%?». Причому діапазон відповідей тягнеться від «дивися гугл/вікіпедію» до «використовуй стандартну функцію». Далеко не завжди ця «стандартна функція» є і влаштовує розробника за всіма параметрами, частіше навпаки: чи то числа виходять далекі від випадкових, чи то швидкість роботи надто мала, а то отриманий код взагалі не поміщається у вільну пам'ять.
Спробуємо розібратися, які бувають алгоритми генерації випадкових чисел, як вибрати відповідний, а головне, у чому особливості реалізації цих алгоритмів на контролерах.

Оцінка «випадковості»

Застосування для ГСЧ можуть знайтися різні, від іграшок до серйозної криптографії. Відповідно, і вимоги до генератора теж сильно варіюються. Для оцінки якості (рівня "випадковості") генератора існують спеціальні тести. Ось основні з них:

• Частотний тест. Складається у підрахунку кількості нулів та одиниць у послідовності бітів. Одиниць та нулів має бути приблизно порівну.
• Тест на послідовність однакових бітів. Шукаються ряди однакових бітів, виду 000...0 чи 111...1. Розподіл частот, з якими зустрічаються ряди, залежно від їхньої довжини, повинен відповідати такому розподілу для випадкового сигналу.
• Спектральний тест. До вихідної послідовності застосовується дискретне перетворення Фур'є. Отриманий спектр не повинен мати значних піків, які б говорили про наявність періодичних властивостей послідовності.
• Автокореляційний тест. Підраховується значення кореляції між копіями послідовності, зрушеними один щодо одного. Тест дозволяє знайти повторювані ділянки у послідовності.

Існують спеціальні набори, що включають десятки подібних тестів:
NIST – використовувався у конкурсі AES для оцінки алгоритмів шифрування.
DIEHARD - один із найсуворіших існуючих наборів.

Алгоритми ДПСЛ

Будь-яка послідовність, згенерована за жорстко заданим алгоритмом, не може вважатися істинно випадковою, тому, ведучи мову про алгоритмічні генератори, вживають термін псевдовипадковапослідовність. Будь-який генератор псевдовипадкових чисел (ГПСЧ) рано чи пізно зациклюється, інша річ у тому, що це «пізно» може наступити за кілька мілісекунд, а може за кілька років. Довжина циклу залежить від обсягу внутрішнього стану генератора N (власне, це обсяг пам'яті, необхідний генератору), і становить від 2 (N/2) до 2 N біт.
Алгоритмів ДПСЧ придумано безліч, але далеко не всі вони зручні для реалізації на мікроконтролерах. Ми сильно обмежені в швидкодії та доступному об'ємі пам'яті, багато контролерів не підтримують речову арифметику і навіть команди множення. Пам'ятаючи про такі обмеження, розглянемо деякі відомі алгоритми.

Лінійний конгруентний метод

Черговий член послідовності розраховується за формулою
X i+1 = (aX i + c) mod m
Число mвизначає максимальний період послідовності, цілі числа aі c- Магічні коефіцієнти. Число mрозумно вибирати рівним мірою двійки, у такому разі опреація приведення по модулю зводиться до відкидання старших бітів. Для того, щоб отримати максимальний період, потрібно дотримуватися таких умов:
- cі m повинні бути взаємно простими,
- a-1має бути кратно pдля всіх простих дільників pчисла m,
- якщо mкратно 4 (а в нашому випадку воно буде кратно), то й a-1має бути кратно 4.
Є ще одна тонкість: як результат слід брати лише старші біти змінної стану X, оскільки молодших біт статистичні параметри випадковості значно гірше. Лінійний конгруентний алгоритм зазвичай реалізований як стандартний rand() у багатьох бібліотеках.

Плюси:

• максимально можливий період для заданого розміру змінного стану;
• досить швидкий;
• часто вже реалізовано у бібліотеці компілятора.

Мінуси:

• потрібна операція множення;
• не всі біти однаково випадкові.

Резюме:швидкий та простий алгоритм для не дуже відповідальних застосувань.

Метод Фібоначчі із запізнюваннями

У цьому алгоритмі використовується співвідношення
X i = X i-a - X i-b,
де змінна стани X- Беззнакове ціле. Величини запізнювань aі bберуться не які завгодно, а чітко визначені, для досягнення максимальної якості рекомендуються пари (17,5), (55,24) або (97,33). Чим більше запізнення, тим більше період і краще спектральні властивості послідовності. З іншого боку, до роботи генератора потрібно зберігати max(a,b) попередніх чисел, що завжди прийнятно. Також для запуску генератора потрібно max(a,b) чисел, які зазвичай одержують за допомогою більш простого ГПСЧ.

Плюси:

• не потребує операцій множення;
• всі біти випадкового числа рівнозначні за статистичними властивостями.

Мінуси:

• потребує великого обсягу пам'яті;
• потребує великого масиву чисел для запуску.

Резюме:дуже якісний, але ресурсомісткий алгоритм.

Регістр зсуву з лінійним зворотним зв'язком

Змінна стани зберігається в регістрі довжини N. Генерація наступного стану включає два кроки:

1. Підраховується значення біта C = X i1 xor X i2 xor X ik , де i1, i2… ik- Номери бітів регістра, звані відведеннями.
2. Регістр зсувається на 1 біт праворуч, крайній лівий біт приймає значення З.

Виходом генератора є крайній правий (або крайній лівий або будь-який інший) біт регістра, тобто псевдовипадкова послідовність генерується по одному біту за ітерацію. При правильно вибраних номерах відводів період генератора становитиме 2 N - 1. «Мінус один», оскільки існує заборонений нульовий стан регістра. Номери відводів для Nвід 3 до 168 можна переглянути в цьому документі.
Крім описаної вище конфігурації, яка, до речі, називається конфігурацією Фібоначчі (не плутати з однойменним методом ГПСЧ!), Існує т.зв. конфігурація Галуа.


Замість того, щоб використовувати для створення нового крайнього лівого біта суму бітів відвідної послідовності, виконується XOR кожного біта відвідної послідовності з крайнім правим бітом, потім виконується циклічний зсув всього регістра вправо. Ця схема складніша для розуміння, але простіше у реалізації, оскільки всі операції XOR можна виконати одночасно. За довжиною періоду та якістю псевдовипадкових чисел схеми Фібоначчі та Галуа еквівалентні.

Плюси:

• дуже проста реалізація, не потрібно навіть арифметики, тільки бітові операції та зрушення;
• дуже швидкий алгоритм (особливо схема Галуа);
• Хороші статистичні властивості.

Мінуси:

• Необхідно перевіряти початкове значення на нерівність нулю.

Резюме:дуже швидкий та досить якісний алгоритм.

Криптостійкі алгоритми

Для застосування у криптографії до ГПСЧ пред'являється ще одна суттєва вимога: незворотність. Усі перелічені вище алгоритми цієї властивості не мають: знаючи кілька вихідних значень ГПСЧ, можна, вирішивши нескладну систему рівнянь, знайти параметри алгоритму (ті самі «магічні» константи a, b, сі т.д). А знаючи параметри, можна відтворити всю псевдовипадкову послідовність.
Як криптографічно стійкий алгоритм ГПСЧ можна використовувати будь-який досить сильний блоковий шифр. Вибравши секретний ключ, можна отримувати блоки псевдовипадкових чисел, застосовуючи алгоритм до послідовних натуральних чисел. Для N-бітного блочного шифру період буде не більше ніж 2 N . Безпека такої схеми залежить від секретності ключа.
Всі сучасні криптографічні алгоритми проходять перевірку на використання як ГПСЧ, тобто, використовуючи сертифікований алгоритм, не потрібно спеціально дбати про статистичні та спектральні властивості вихідного потоку. Переживати потрібно лише про обчислювальну «ненажерливість» криптоалгоритмів. Якщо потрібно виконувати велику кількість операцій шифрування, можна вибрати контролер з апаратними криптографічними блоками. Часто в таких контролерах є і дуже непоганий криптостійкий апаратний ГПСЧ.

Джерела ентропії

Як було зазначено, використовуючи лише детерміновані алгоритми, неможливо згенерувати істинно випадкове число. Тому зазвичай застосовується зв'язка ГПСЧ + зовнішній джерело ентропії. Джерело ентропії використовується завдання початкового значення для ГПСЧ, а завдання останнього зводиться до забезпечення спектральної і статистичної чистоти послідовності. Що ж можна використовувати як джерело ентропії? І практично що завгодно.

Активність користувача

Якщо пристрій взаємодіє з користувачем, досить хорошим рішенням буде використовувати як джерело ентропії самого користувача. Наприклад, час натискання на кнопку, виміряний з точністю до мікросекунди (а точніше його молодші розряди), повністю непередбачувано. Однак часто пристрій має працювати автономно, а значить цього чудового каналу інформації ми втрачаємо.

Аналого-цифровий перетворювач

Багато контролерів є вбудовані АЦП. І в багатьох контролерах вони дуже посередньої якості, зроблені просто «щоб було». Молодші біти результату АЦП майже завжди містять значний шум, навіть якщо вимірюється постійна напруга. Це можна використовувати: підключіть вхід АЦП до напруги живлення через дільник, проведіть кілька десятків вимірювань, візьміть молодші біти – ось вам чудове випадкове число. Якщо АЦП містить вбудований підсилювач, увімкніть його, він також шумить.

Асинхронні генератори

Можна використовувати різницю двох періодів несинхронізованих тактових генераторів. Більшість контролерів містять, наприклад, сторожовий таймер. Для підвищення надійності він тактується від окремого генератора ніяк не пов'язаного з основним тактовим сигналом. Достатньо підрахувати число тактів основного тактового сигналу за період сторожового таймера. Якщо підібрати періоди те щоб лічильник за час виміру багаторазово переповнився, можна отримати досить випадкове число. Недолік цього - він вимагає багато часу, до кількох секунд.

Годинник реального часу

Якщо у схемі є годинник реального часу, можна використовувати їх поточні показання для ініціалізації ДПСЛ Наприклад, перетворивши поточну дату/час у формат Unix time, ми отримаємо відразу 32 біти, які ніколибільше не повторяться, якщо тільки не знімати показання частіше одного разу на секунду. Використання реального часу дає унікальність значень, але не дає жодної непередбачуваності, тому краще комбінувати даний спосібз іншими.

RC-ланцюг

Якщо контролер не має жодних периферійних пристроївКрім портів вводу-виводу, можна вчинити наступним чином: одна з ніг приєднується через конденсатор до землі, а через резистор - до напруги живлення. Якщо входи контролера мають внутрішні підтягуючі резистори, зовнішній резистор не потрібен.

Виводимо цей порт сигнал «0» - конденсатор розряджається. Перемикаємо порт у режим входу – конденсатор починає заряджатися. Коли напруга на ньому досягне порога, вхід переключиться зі стану "0" в "1". Час заряду залежить від багатьох чинників: напруження живлення, дрейфу параметрів RC-ланцюга, нестабільності порога, температури, витоків, перешкод. Вимірюючи його з достатньою точністю та беручи молодші біти, можна отримати гарну випадковість.

Апаратний генератор шуму

Для багатьох серйозних додатків (насамперед мається на увазі криптографія), потрібне надійніше джерело ентропії, ніж перераховані вище. У таких випадках використовують оцифрування сигналу з генератора шуму, заснованого на тепловому, дробовому, або навіть квантових ефектах. Шумним елементом зазвичай служить спеціальний діод або стабілітрон, сигнал з якого посилюють і подають на компаратор, що формує двійковий бітовий потік.

Для того, щоб поріг спрацьовування компаратора не впливав на статистичні властивості отриманого сигналу, застосовують два генератори шуму, що працюють на один компаратор:

Висновок

Насамкінець розповім одну історію з життя. Почалася вона із чергового заданого на форумі питання «як мені згенерувати випадкове число на контролері?». Автор питання пояснив, що робить як курсовий проект пристрій, що емулює кидання гральної кістки. Після кількох безуспішних спроб розібратися в алгоритмах, топікстартер поділився своїм рішенням: він просто кинув 1000 разів справжній кубик і забив отриманими числами всю вільну пам'ять контролера. Генератор блискуче пройшов усі тести на «випадковість», враховуючи те, що за час демонстрації витратив менше третини свого «запасу».
Отже, таке рішення теж має право на життя, особливо якщо висуваються дуже суворі вимоги до випадковості чисел, але вони потрібні не дуже часто. Враховуючи стрімко падаючі ціни на пам'ять, можливо розумним забезпечити пристрій флешкою ​​із «запасом хаосу», якого вистачить на весь час життя пристрою.
Дякую за увагу!

UPD1:Як було справедливо зазначено в коментарях, якщо передбачається атака на ГСЧ, і у зловмисника буде апаратний доступ до пристрою, застосовувати зовнішні джерела ентропії потрібно з великою обережністю, так як не складно підмінити сигнал від зовнішнього джерела. Слід використовувати внутрішні джерела, які можна на додаток до зовнішніх.
Також хороша ідея - накопичувати ентропію. вільний часа використовувати її тоді, коли потрібно згенерувати чергове випадкове число. Зазвичай у разі використовується т.зв. Entropy pool- масив, над яким періодично виконується одна з функцій ДПСЧ, і куди постійно підмішуються дані із джерел ентропії.

UPD2:У багатьох випадках корисний вміст Entropy pool (вибачте, не знаю нормального російського перекладу) зберігати в EEPROM для того, щоб після вимкнення-ввімкнення пристрою не накопичувати його заново. Це відноситься, перш за все, до отримання ентропії методом асинхронних генераторів: за досить стабільних умов після кожного включення може генеруватися та сама послідовність.
Якщо очікується атака, вживіть заходів проти заміни вмісту EEPROM. Якщо дозволяє контролер, заблокуйте читання/стирання/запис за допомогою lock-бітів, при включенні контролюйте цілісність EEPROM, хоча б за допомогою найпростіших контрольних сум.

Теги:

• гсч
• гпсч
• мікроконтролери
• алгоритми

Додати теги

randomSeed (seed)

Встановлює значення, або початкове число, як початкова точка функції random().

randomSeed (value); // задає 'value' як початкове значення random

Оскільки Arduino не може створювати дійсно випадкових чисел, randomSeed дозволяє вам помістити змінну, константу або іншу функцію в random функцію, що допомагає генерувати більш випадкові чисел

"Random" числа. Є безліч різних початкових чисел, або функцій, які можуть бути використані в цій функції, включаючи millis() або навіть analogRead() для читання електричних шумів через аналоговий висновок.

random (max)

random (min, max)

Функція random дозволяє повернути псевдовипадкове число в діапазоні, заданому значеннями min і max.

value = random (100, 200); // задає 'value' випадковим

// числом між 100 та 200

Примітка:Використовуйте це після використання функції randomSeed(). Наступний приклад створює випадкове число між 0 та 255 і виводить PWM

сигнал на PWM висновок, що дорівнює випадковому значенню:

int randNumber; // Змінна для зберігання випадкового значення

int led = 10; // LED з резистором на виводі 10

void setup() () // setup не потрібний

randomSeed (millis()); // задає millis() початковим числом

randNumber = random (255); // Довільне число з 0 - 255 analogWrite (led, randNumber); // Висновок PWM сигналу

delay (500); // пауза на півсекунди

Джерело: Гололобов В. - З чого починаються роботи. Про проект Arduino для школярів (і не лише) – 2011

Related Posts

Serial.begin (rate) Відкриває послідовний порт і задає швидкість послідовної передачі даних. Типова швидкість обміну для комп'ютерної комунікації – 9600, хоча підтримуються й інші швидкості. void setup () (Serial.begin…….

Усі змінні мають бути задекларовані до того, як вони можуть використовуватись. Оголошення змінної означає визначення типу її значення: int, long, float і т.д., завдання унікального імені змінної та додатково їй…….

Добре, що ми встановили цю програму. Ми налагодили "механізм" роботи з модулем. І переглянули кілька прикладів. Але хотілося б і самим творити щось корисне. Спробуємо. Спочатку закриємо попередній проект. Для цього…….

Увага! При роботі з модулем Arduino в інших середовищах розробки слід уважно ставитись до конфігурації мікроконтролера (Fuses). Доки ви точно не знаєте, до чого може призвести зміна…….

Час та рандом. Реакція

На цей раз ми дізнаємося, що таке «Випадкові» значення, а також навчимося працювати з часом.

Нам знадобляться:

• Кнопка тактова
• Їжачка
• Провід з'єднувальні «ПАТА-ПАПА»

Реакція

Наше завдання сьогодні – зібрати схему, яка дозволяє дізнатися швидкість нашої реакції.

При натисканні на ліву кнопку лунає сигнал через «випадковий» час. А при натисканні на праву відзначається, скільки часу пройшло з писку до натискання на праву кнопку.

Хто скіловий - пробує сам, а ми дивимося на схему.

#define BUZ 8 #define START 9 #define STOP 7 int time; //Змінна для синхронізації void setup() ( Serial. begin(9600); pinMode(START, INPUT_PULLUP); pinMode(STOP, INPUT_PULLUP); pinMode(BUZ, OUTPUT); ) void loop() ( if(digitalRead(START) == 0) // При натисканні на Кнопку СТАРТ.. ( int start_time = millis(); Згенеруємо "випадкову" затримку time = time + Rand; //Додамо час затримки delay(Rand); //Почекаємо tone(BUZ, 3000, 500); //Пищимо! ) if(digitalRead(STOP) == 0 && digitalRead( START) == 1)// При натисканні на кнопку СТОП... ( int stop_time = millis(); //Запам'ятаємо час зупинки. time = stop_time - time; // Обчислимо різницю в часі. Serial.println("Time: "); // Виведемо час у Серіал. Serial.println(time); delay(1000); ) ) //Перед другою спробою натискай на кнопку СТАРТ знову.

Пояснення

int time; Змінним (не всім), при їх позначенні, не обов'язково задавати будь-яке значення. Цю змінну ми використовували для того, щоб зв'язати два оператори if.

У С++ змінні, оголошені всередині циклу, не будуть доступні в інших циклах, оскільки вони діють лише всередині цього циклу. Це робиться для того, щоб запобігти помилкам у програмуванні. Коли код програми розростеться, ти зрозумієш, про що я говорю.

Щоб змінна була доступна для кількох операторів, потрібно зробити її глобальною. Тобто. оголосити змінну поза функціями.

millis();Повертає кількість мілісекунд, що пройшли із запуску програми.

Нам вона потрібна для того, щоб відміряти кількість часу, що минув від сигналу до натискання на кнопку.

random(min,max);Це генератор «випадкових» чисел. Приймає два значення. Він генерує число у діапазоні від min до max.

"Випадкові" числа тому, що це певна послідовність значень. Дуже довга, але одна й та сама. Для того, щоб отримувати різні послідовності, варто скористатися RandomSeed();

Вона, функція, ініціалізує генератор. А якщо задати параметром випадковий, то ми отримуватимемо потрібні нам послідовності. Одинака послідовність буде, якщо параметр буде фіксованим.

Висновок

Тепер ти можеш тренувати свою реакцію за допомогою власноручного пристрою. А можеш продовжувати займатись далі.

Список радіоелементів

Позначення	Тип	Номінал	Кількість	Примітка	Магазин	Мій блокнот
	Плата Arduino	Arduino Uno	1			До блокноту
	Макетна плата	Breadboard-half	1			До блокноту
	П'єзовипромінювач	Пасивний	1			До блокноту
	Кнопка тактова	Без фіксатора	2			До блокноту
	З'єднувальні дроти	"Папа-Папа"	1