Скрыть объявление
На нашем форуме недоступен просмотр изображений для неавторизованных пользователей. Если Вы уже зарегистрированы на нашем форуме, то можете войти. Если у Вас еще нет аккаунта, мы будем рады, если Вы к нам присоединитесь. Зарегистрироваться Вы можете здесь.

Делюсь опытом Генератор случайной последовательности

Тема в разделе "Идеи", создана пользователем Юрий Ботов, 8 янв 2019.

Метки:
  1. Юрий Ботов

    Юрий Ботов Moderator Команда форума

    Сообщения:
    967
    Симпатии:
    162
    Недавно для железки на stm32 мне понадобился генератор случайной последовательности байтов.
    L4x2 (и более дорогие) - имеют внутренний TRNG (True Random Numbers Generanor) - но дороговаты, а младшие модели (412-432) реально недоступны лично мне на рынке, есть только в виде Nucleo... Пришлось экспериментировать:
    - шум транзисторов и стабилитронов - легко создать, хорошо воспроизводится, но требуется 9+ вольт питания, да и уровень маловат (десятки микровольт) - нужно городить усилители, а прикосновение рукой к донглу полностью подменяет шум меандром 50Гц...
    - шум стабилизаторов (а ля lm317) - гораздо интереснее (единицы милливольт), но под осциллографом раскрылось, что на самом деле это периодическая пила случайной амплитуды. Для тестирования радио-устройств - нормально, а вот для генератора действительно случайных чисел - сомнительно.
    - в конце концов решил использовать реально дешевый f103c8t6 - и попытаться что то вытянуть из шума АЦП... Вернее из его самого младшего разряда. Поток с младшего бита имеет примерно такой вид: "000000000101110000000000100010000000011001000", то есть, что-то похожее на случайные числа перемежающиеся блоками нулей случайной длины. Пробовал проредить нули - бяка. Решил поиграться с XOR - и даже первый результат (a[0]^a[10]) превзошел ожидания. Далее долгие эксперименты по разному сочетанию битов. Результат прилагаю. (Результат уже на esp8266, оно превосходно работает и на ней).

    Итак mytrng.h
    Код (C):
    1. #ifndef _mytrng_h_
    2. #define _mytrng_h_
    3.  
    4. class TRNG {
    5.   public:
    6.     inline TRNG(void) { buf = 0; }
    7.     inline ~TRNG(void){}
    8.     inline void Init( u16 p){ port = p; for (u8 i = 0; i < 12; i++) { buf = buf << 1 | Bit();} }
    9.     inline u8 Bit(void){ delay(1); buf = buf << 1 | (analogRead(port) & 1); return (buf&1)^(buf>>1&1)^(buf>>2&1)^(buf>>10&1); }
    10.     inline u8 Byte(void){ u8 r = 0; for (u8 i = 0; i < 8; i++) { r = r << 1 | Bit();} return r;}
    11.     inline u8 Byte(u8 max) { return Byte()*max/0xff; }
    12.     inline u16 Word(void){ u16 r = 0; for (u8 i = 0; i < 2; i++) { r = r << 8 | Byte();} return r;}
    13.     inline u16 Word(u16 max) { return Word()*max/0xffff; }
    14.     inline u32 Dword(void){ u32 r = 0; for (u8 i = 0; i < 2; i++) { r = r << 16 | Word();} return r;}
    15.     inline u32 Dword(u32 max) { return Dword()*max/0xffffffff; }
    16.   private:
    17.     u16 buf;
    18.     u16 port;
    19. };
    20.  
    21. #endif
    Код в Arduino esp8266 для тестирования:
    Код (C):
    1. //#include "d:/include/mytypes.h"
    2. #include "d:/include/mytrng.h"
    3.  
    4. TRNG Random;
    5.  
    6. void setup() {
    7.   Serial.begin(115200);
    8.   Random.Init(A0);
    9. }
    10.  
    11. void loop() {
    12.   Serial.println(Random.Byte());
    13. }
    Не забудьте исправить пути до инклюд-файлов на свои.
    Первый "инклюд" не нужен под esp, там и так это объявлено, только под stm.
    Если кому надо - вот он:
    Код (C):
    1. #ifndef _mytypes_h_
    2. #define _mytypes_h_
    3.  
    4. typedef unsigned char u8;
    5. typedef signed char i8;
    6. typedef unsigned short u16;
    7. typedef signed short i16;
    8. typedef unsigned long u32;
    9. typedef signed long i32;
    10.  
    11. #endif
    А это результат - таблица частот выпадения значений:
    Код (Text):
    1.     1705    1682    1725    1718    1691    1739    1799    1714    1657    1637    1739    1648    1756    1673    1637    1693
    2.  
    3.     1657    1637    1739    1648    1756    1673    1637    1693    1712    1720    1687    1697    1717    1660    1720    1729
    4.  
    5.     1712    1720    1687    1697    1717    1660    1720    1729    1634    1736    1727    1697    1744    1665    1728    1649
    6.  
    7.     1634    1736    1727    1697    1744    1665    1728    1649    1715    1696    1715    1737    1762    1690    1723    1704
    8.  
    9.     1715    1696    1715    1737    1762    1690    1723    1704    1694    1660    1749    1649    1744    1661    1694    1736
    10.  
    11.     1694    1660    1749    1649    1744    1661    1694    1736    1602    1768    1799    1644    1673    1661    1711    1712
    12.  
    13.     1602    1768    1799    1644    1673    1661    1711    1712    1717    1739    1677    1741    1687    1753    1730    1684
    14.  
    15.     1717    1739    1677    1741    1687    1753    1730    1684    1733    1727    1723    1726    1668    1723    1687    1662
    16.  
    17.     1733    1727    1723    1726    1668    1723    1687    1662    1745    1738    1765    1702    1666    1734    1679    1719
    18.  
    19.     1745    1738    1765    1702    1666    1734    1679    1719    1682    1713    1757    1723    1686    1691    1653    1749
    20.  
    21.     1682    1713    1757    1723    1686    1691    1653    1749    1693    1757    1717    1774    1620    1727    1718    1776
    22.  
    23.     1693    1757    1717    1774    1620    1727    1718    1776    1674    1701    1740    1704    1740    1724    1704    1700
    24.  
    25.     1674    1701    1740    1704    1740    1724    1704    1700    1629    1680    1688    1672    1805    1615    1713    1643
    26.  
    27.     1629    1680    1688    1672    1805    1615    1713    1643    1799    1687    1690    1674    1632    1698    1726    1688
    28.  
    29.     1799    1687    1690    1674    1632    1698    1726    1688    1710    1753    1722    1711    1728    1625    1760    1764
    30.  
    31.     1710    1753    1722    1711    1728    1625    1760    1764    1646    1728    1744    1707    1762    1697    1757    1713
    32.  
    33.  
    34. обработано байт: 436698, min: 1602, max: 1805, avg: 1705, разброс: 11 %
    разброс = 100* (max-min)/avg
    Учтите, что разброс уменьшается при увеличении размера выборки, так у меня на выборке около 70000 он был 33%, а тут на выборке примерно 400000 уже 11%, что радует глаз в гораздо большей степени :)

    Верхнее левое число таблицы - количество 0-байтов, потом 1... справа верх 15 ну и право низ соответственно 255.
    Баланс 0 и 1 терпимый - разница менее 1%.

    ВАЖНО:
    - увы нельзя использовать один и тот же вывод и для генерации случайных чисел и как просто АЦП
    - вывод АЦП должен "висеть в воздухе"! То есть на NodeMCU вы получите вместо случайных чисел пачку нулей (проверил :) ). Впрочем никто не запрещает аккуратно перерезать дорожку.
    - это не быстрый генератор (около 1ms на бит - там внутри есть миллисекундная задержка между запросами к АЦП - если ее убрать, равномерность резко ухудшается)

    Кому как а мне для моей задачи - хватило.
     
    Последнее редактирование: 8 янв 2019
    Сергей_Ф нравится это.
  2. enjoynering

    enjoynering Авторитетный участник сообщества

    Сообщения:
    403
    Симпатии:
    45
    а вы не боитесь что специально обученная наводка на контакты ацп превратит ваши шумы в тыкву?
     
  3. Юрий Ботов

    Юрий Ботов Moderator Команда форума

    Сообщения:
    967
    Симпатии:
    162
    enjoynering, да, работу в микроволновке, открытом космосе и последствий ядерных взрывов я не предусмотрел :) Просто встроенный в более дорогие чипы TRNG падет под специально обученной наводкой с тем же успехом. Я не предлагаю данное решение как коммерческий продукт или для управления технологическими процессами. А для DIY - вполне. К слову для превращения моих шумов в тыкву достаточно обычного молотка. Обучать наводку - это перебор.
     
  4. view24

    view24 Читатель

    Сообщения:
    77
    Симпатии:
    5
    Гениально!
     
  5. Юрий Ботов

    Юрий Ботов Moderator Команда форума

    Сообщения:
    967
    Симпатии:
    162
    Прошу вспомнить, что изначально это было устройство на stm32 - токен с единственным интерфейсом наружу: USB HID keyboard. Устройство по определению работает только "на вывод" и никакой информации от компьютера получать не имеет права.
    Так вот. На программной проверке идеи я разумеется использовал программный генератор и мне его недостатки были даже удобны :)
    По большому счету, есть два основных вида программной реализации (известные мне): "сдвиговый регистр с обратной связью" и криптографический (на основе эллиптических кривых).
    У первого есть два недостатка: неизменное начало последовательности - с этим можно было бы как то бороться если получить случайное число для начала каким-то другим, не программным, способом и ... полная предсказуемость последовательности выдаваемых значений (это вообще "машина состояний") - это не лечится никак. Основной плюс - высокая "равномерность" и удобство при отладке :) - знаешь что получишь.
    Второй тоже грешит неизменностью начального значения - лечится аналогично. Последовательность предсказать труднее. Но самая большая беда второго алгоритма - он очень прожорлив по отношению к памяти, и чем он качественнее, тем прожорливей. В общем, у меня, в 20кБ ОЗУ он просто не влез, и при тестировании использовался первый вариант с длиной регистра 32 бита.

    Итак ответ на собственно вопрос: не устроила полная предсказуемость генерируемой последовательности (с неизменным началом я вполне мог справиться)

    Там вверху есть "таблица частот выпадения значений" - это и есть распределение. Распределение практически равномерное в диапазоне 0-255 с разбросом в среднем 7% и максимальным выбросом 11%. Это на полмиллиона "испытаний" - около часа работы генератора. Зависимость от количества испытаний прослеживается правильная: чем больше испытаний тем меньше разброс (то есть в пределе сходится к равномерному закону распределения).
    Терминами "белый и розовый" шум - не пользуюсь тут принципиально ввиду принципиальной ограниченности возможных значений результата, а белый шум подразумевает дельта функцию и бесконечный спектр...

    Да ничем не лучше. Просто они для разных задач. Просто в варианте с использованием АЦП заранее не известны не первое, не каждое следующее значение. Недостатки тоже есть - нельзя гарантировать равномерность соотношения 0 и 1 на коротких последовательностях - для классической криптографии это придется корректировать.
     
  6. nikolz

    nikolz Гуру

    Сообщения:
    3.105
    Симпатии:
    331
    Благодарю за ответ.
    Несколько замечаний и предложений
    1) Есть существенно лучшие алгоритмы генерации случайных кодов например
    Алгоритм Л'Экюера, комбинирующий две последовательности
    Алгоритм Л'Экюера, комбинирующий две последовательности
    как видим период его повторения не достижим на компе и тем более на MCU
    У него нет требований по памяти Есть требование умножать и делить
    -----------------------
    2) закон распределения значений и спектральная плотность - это две большие разницы
    У Вас приведены данные по оценке первого .
    Но это распределение ничего не знает и нам не говорит о независимости (коррелированности) значений во времени т е предсказуемости процесса - а это и есть мера случайности.
    ------------------
     
  7. Юрий Ботов

    Юрий Ботов Moderator Команда форума

    Сообщения:
    967
    Симпатии:
    162
    Немного порассуждаю:
    - я априори полагаю что код известен "злоумышленику". "защита кода" stm32 10x серии давно взломана и расчитывать на нее нельзя, у esp она отсутствует как класс. Потому свой код в случае успешного окончанию работы я скорее всего опубликую - нет смысла его прятать.
    - то что не достижимо сегодня на компе, легко достижимо способом "аренды вычислительной мощности" крипто-фермы. Мода на криптовалюты пошла на спад и владельцы ферм с удовольствием продают "время" за "живые" деньги - причем сравнительно небольшие.
    Учитывая сказанное, алгоритм ЛЭкюера болен теми же болезнями, что и предыдущие: как только будут известны начальные условия двух последовательностей (а алгоритм известен по определению) - вся последовательность становится на 100% предсказуемой... Да, сломать его дороже, но тому кто готов платить - взлом вполне доступен, причем в обозримое время.

    Не могу не согласиться :)
    Просто руки не дошли еще до полноценного анализа последовательности, прежде чем вбрасывать это "в мир" - разумеется сделаю.
    Если кому то интересно, могу выслать файл часового "потока случайных чисел" (это около 500кБ в zip) в формате:
    Код (Text):
    1. 79
    2. 97
    3. 170
    4. 11
    5. 26
    6. 90
    7. 31
    8. 148
    9. 205
    10. 45
    11. 48
    12. 113
    13. 43
    14. 24
    15. 172
    16. 109
    17. 173
    18. 78
    19. 118
    20. 142
    21. 220
    22. 19
    23. 234
    24. 239
    25. 123
    26. 36
    27. 11
    28. 191
    29. 251
    То есть цифры в текстовом формате разделенные CR/LF
    (специально выбрал отрезок в котором есть неподалеку два одинаковых значения - 11, что бы было видно что не с предыдущими ни с последующими значениями они не связаны)
     
    Последнее редактирование: 14 янв 2019 в 17:43
  8. nikolz

    nikolz Гуру

    Сообщения:
    3.105
    Симпатии:
    331
    Тоже немного порассуждаю.
    Крипто фермы для взлома генератора шума типа ЛЭкюера не применимы.
    Там параллельно решается совершенно другая задача. При этом аппаратно реализуется лишь SHA256 для биткоина
    в остальных случаях - это программный поиск решения.
    Написать программу поиска решения для взлома генератора шума при неизвестном алгоритме будет стоить очень дорого.
    Но главное - что Вы хотите так тщательно шифровать? И зачем нужен генератор псевдослучайной последовательности ?
    ---------
    еще замечу, что аналоговый генератор будет генерить еще и нестационарный шум с неизвестными и меняющимися параметрами. Не могу понять куда его будете применять.
     
    Последнее редактирование: 14 янв 2019 в 19:15
  9. Юрий Ботов

    Юрий Ботов Moderator Команда форума

    Сообщения:
    967
    Симпатии:
    162
    Учитывая, что к данному форуму, да и к теме это имеет ооочень отдаленное отношение :) я на днях опишу это в личке.
     
  10. nikolz

    nikolz Гуру

    Сообщения:
    3.105
    Симпатии:
    331
    спасибо.
    Я не критики ради, а дискуссии для.
     
  11. Сергей_Ф

    Сергей_Ф Moderator Команда форума

    Сообщения:
    1.678
    Симпатии:
    172
    Юрий Ботов, а в условиях помех не проверяли? Мне кажется, даже обычный коллекторный двигатель на 4В рядом с этим esp способен в этот генератор внести устойчивую последовательность.
    Тем не менее, это отличный способ получить первое случайное число.
     
  12. nikolz

    nikolz Гуру

    Сообщения:
    3.105
    Симпатии:
    331
    огибающая похожа на синусоиду (может это наводка от 50 гц?)
     
  13. nikolz

    nikolz Гуру

    Сообщения:
    3.105
    Симпатии:
    331
    Ничто так не воодушевляет, как отклик посетителей форума "Гениfльно" на пост " 2 умножить на да будет 4"
    --------------------
    В продолжении обсуждения темы.
    Правильно ли я Вас понял.
    Вам не понравилось что простейший генератор кода на 32 битах имеет период 100 000 000 и 2^31 вариантов , поэтому Вы изобрели аналоговый генератор байтов , с 256 вариантами кода?
    или я что-то упустил?
     
  14. Юрий Ботов

    Юрий Ботов Moderator Команда форума

    Сообщения:
    967
    Симпатии:
    162
    :) немного терпения, просто сейчас очень занят - напишу про свою задачу в личке.
    Лично этот "классический" уже генератор я "взломал" на своем компе за 8 часов - 3 часа на поиск "точки старта" и 5 часов на генерацию 40 Гб полной последовательности (основное время на обращение к диску). По моему, это слишком быстро.
     
  15. enjoynering

    enjoynering Авторитетный участник сообщества

    Сообщения:
    403
    Симпатии:
    45
    по это я автору намекал

     
  16. Юрий Ботов

    Юрий Ботов Moderator Команда форума

    Сообщения:
    967
    Симпатии:
    162
    enjoynering, Не спорю :) ! Повторю, изначально это токен на stm32, никаких моторов, помехи - только наводка от руки владельца (я их отсеиваю на другом этапе авторизации - все вам рассказывать? Не маленькие же :) ). А иные виды использования - на усмотрение Homo Sapiens.

    Прообраз токена.. узнаете? DSC01015 (2).JPG
     
    Последнее редактирование: 15 янв 2019 в 20:19
  17. nikolz

    nikolz Гуру

    Сообщения:
    3.105
    Симпатии:
    331
    так и не понял, что же Вы делаете.
    Генератор шума - это не шифратор.
    Зачем его взламывать?
    --------------------
    попробуйте взломать генератор ЛЭкюера .
    У него период 10^18 что в 10 000 000 000 раз больше, чем у того который Вы взломали.
    если взломаете, то найду Вам круче.
     
  18. Юрий Ботов

    Юрий Ботов Moderator Команда форума

    Сообщения:
    967
    Симпатии:
    162
    Уффф... я же просил потерпеть чуть чуть.... я делаю "АВТОРИЗАЦИЮ без крипто-алгритмов".
     
  19. nikolz

    nikolz Гуру

    Сообщения:
    3.105
    Симпатии:
    331
    пардон, больше не буду.
     
  20. view24

    view24 Читатель

    Сообщения:
    77
    Симпатии:
    5
     

Поделиться этой страницей