Новый алгоритм ГСЧ на замену /dev/random

    Как известно, генерация случайных чисел является ключевым элементом для приложений криптографии, экономики, информационной безопасности, имитационного моделирования (прогнозы погоды) и многих других. Все существующие алгоритмы ГСЧ используют внешний источник энтропии, например, счётчик тактов процессора, шум звуковой карты, движение мыши пользователя и т.д.

    Немецкие исследователи Бернард Фечнер (университет Хагена) и Андре Остерлох (BTC AG) заявили о прорыве в методах генерации случайных чисел. Они разработали алгоритм, который обеспечивает дискретное равномерное распределение до 20 раз лучше существующих методов. К работе прилагаются результаты тестов по сравнению качества случайных чисел, генерируемых разными методами.

    Разработанный немцами ГСЧ считывает последовательность битов из памяти (метастабильное состояние) и по таблице меняет местами 0 и 1. Таблица — это дополнительный уровень случайности, который позволяет на порядок повысить качество случайных чисел. Специфика метода (считывание из памяти) обеспечивает максимально возможную скорость работы алгоритма. Он не только качественнее, но и на порядок быстрее, чем алгоритм LFSR плюс счётчик тактов процессора — такая связка используется в стандартной программе /dev/random, которая идёт в комплекте с Unix.

    Предполагается, что идеальная последовательность ГСЧ близка по свойствам к настоящим случайным числам, таким как, например, показания детекторов космического излучения или событий ионизирующей радиации, то есть не существует даже теоретического способа предсказать следующее число в последовательности.

    Результаты своей работы Бернард Фечнер и Андре Остерлох опубликовали в журнале International Journal of Critical Computer-Based Systems. [A meta-level true random number generator. Int. J. Critical Computer-Based Systems, 2010, 1, 267-279, PDF]

    via ScienceDaily
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 64

      0
      Когда нужно были нужны реально рандомные значения просто высовывался чувствительный микрофон на улицу и ln -s /dev/snd0 /dev/random
        +7
        Что-то мне сдается, что…
        Во-первых, random накапливает энтропию и гарантирует не нулевое её значение. snd что-нибудь накапливает? хранит состояния? — нет.
        Во-вторых, random дополнительно перемешивает биты, обеспечивая дополнительную рэндомизацию. snd зашумляет данные аудиокарты? — нет.
        Ну и в-третьих, приведённая команда какая-то странная… она из времён, когда не было devfs? и даже в те времена (лет 10 назад) она бы вам сказала что-то вроде: «ln: /dev/random: File exists»
          –10
          Во-вторых, random дополнительно перемешивает биты, обеспечивая дополнительную рэндомизацию.

          Да вы наверное шутите!
            +6
            Нисколько.
            Если вы не в состоянии разобраться в исходниках (там много комментариев на тему, зачем там SHA), то, возможно вас убедит фраза из википедии «uses secure hashes», которая как бы намекает…
              +1
              Почитал, прояснилось.
            –8
            нет ни чего рандомнее чем звуки толпы в центре города.
              –7
              Мне в голову пришла бредовейшая из моих бредовых идей — проанализировать звуки толпы на улице и выстроить бесполезные графики активности, частоты скачков и затишья, шум в ночное, вечернее время, час пик… и в метро. Очень интересно будет в метро. только как-то отфильтровать звуки самих поездов, и проанализировать только людей.
                +6
                Вы бы еще так написали, было бы еще удобочитаемей.
                  0
                  Чёрт, да вы правы ;)
                +3
                вы не путайте, звук использую как энтропию, но не как генератор ПСП, звук толпы волне можно предсказать.
                  –6
                  попробуйте предсказать когда гопник слева скажет "№я
                    +2
                    он скажет это с вероятностью близкой к единице))
                  +27
                  Рандомность обманчива.

                  На пример, много умных дядей думали, что ГСЧ в FORTRAN рандомен. Прошли десятки лет и ВНЕЗАПНО обнаружилось, что если использовать последовательность, выдаваемую им в качестве координат точек: x, y, z, x, y, z, x, y, z..., то все точки ложатся всего на несколько плоскостей. Оказывается, этим свойством обладают все конгруэнтные датчики. Однако большинство библиотек не собираются переходить на что-нибудь поприличнее (хотя бы метод Фибоначчи с запаздываниями). Пиплу и так рандомно.

                  Почитайте исходники, на которые я сослался. Лично у меня просто сердце кровью обливается, когда я вижу, сколько идей заложено в random, сколько за этим математики, сколько анализа… и тут приходит neochapay, который всех умней, и делает ln -s. Люди для вас стараются. Используют серьёзный матан. Ломают копья на конференциях. Сделали витаминизированный напиток, а вы им: «в унитазе вода такая же, буду пить оттуда». А всякие superhabra-ы вас плюсуют и верят вам больше чем вики… больно смотреть на это торжество невежества и мракобесия. Вы уж простите.
                    +1
                    полностью с вами солидарен, товарищ просто, видимо где-то прочел коммент такого же как он об этом, и теперь народ дезинформирует.
                      0
                      Скорее всего, он где-то слышал, что сигнал младшего бита с АЦП звуковухи можно при определенных условиях использовать в качестве аргумента для функции ГСЧ. Но деталей то ли не услышал, то ли не счел их важными. Хотя именно накопление энтропии и сама функция и дают по сути 90% случайности.
                      –10
                      Потом являются всякие michurin'ы и заявляют что они одни — д'Артаньяны. Плавали, знаем.
                    0
                    Я проверял, правда под виндой, нормальное распределение получается…
                      –2
                      Если с микрофона ловить сигнал прямо в софтину.
                        –2
                        Прямо в маткад на график можно пулять, будет клёвый колокол :)
                          +1
                          Ну конечно! Это ж бабл гам.

                          Правда можно преобразовать к равномерному. :)
                            –1
                            Да, онотоле не одобрил бы формулировку )))
                        +6
                        Часто в серверах нет ни микрофонов, ни аудиокарт. В виртуальных серверах — тем более. Да и насколько данные были реально случайные — Вы проверяли как? На веру?
                          –1
                          ну сервер был на основе обычного PC так что… а проблемма с отсутствием можно решить передачей звука по сети.
                            +1
                            )) и как же вы собрались использовать такое в криптографическом софте? или в других задачах связанных с трудоемкими вычислениями? а внутри ядра как?)
                            +6
                            Я читал исходники.

                            А вам отвечу:

                            1) если ваш виртуальный сервер хостится не на реальном… что ж, у вас проблемы :-)

                            2) основной источник энтропии не микрофоны, а сетевухи. У них пропускная способность больше в сотни раз, то есть энтропия из них прёт на несколько порядков быстрее. А спамеры не дремлют… шлют энтропию на интерфейс.
                          +1
                          Не совсем понял, они используют обычные ячейки памяти?
                            +2
                            Они используют их как именно генератор случайных чисел перевродя их в неустойчивое состояние. Т.е. работа с памятью ведется на уровне железа и используются её физические, а не логические свойства.
                            +37
                            для имитационного моделирования (прогнозы погоды)

                            Так воот значит как у нас прогнозы составляют) Я всегда что-то подозревал.
                              +7
                              имитационным моделированием и ракеты считают, и ничего — летают!
                                +4
                                >> и ничего — летают!

                                — Но не все и не всегда (ц) )))
                              +7
                              Возможно, в тексте должно быть не LSFR, а LFSR(Linear feedback shift register)? Очепятка?)
                                +3
                                >> that uses an extra layer of randomness by making a computer memory element, a flip-flop, twitch randomly between its two states 1 or 0
                                Вот этот второй «randomly» — он, как я понимаю, с того же железного генератора? ))
                                Да-а, прорыв у ребят, ничего не скажешь. RNDxRND. Британские ученые аплодируют стоя.
                                  +2
                                  отличный ГСЧ это стрельба наших биатлонистов, предсказать невозможно
                                    –10
                                    А давайте Ваша стрельба с 50 метров по мишени пусть метр на метр?
                                    Или Вы можете стрелять менее «случайно»?

                                    Раз самые умные — выходите и сами бегите. А все поржут над вами. И Ваш феил по ящику покажут.
                                      +9
                                      моя стрельба в биатлоне более прогнозируемая, т.к. я нифига это делать не умею :)
                                    +2
                                    Отличный ГСЧ это работа IE 6.
                                      +1
                                      Не сказал бы, в IE 6/7 всё очень предсказуемо и лечится обычно двумя простыми методами, чего не скажешь об Опере
                                        +2
                                        Не сказал бы, в Опере всё очень предсказуемо и даже не надо ничего лечить, чего не скажешь об IE.
                                          +3
                                          Вам бы погоду предсказывать!)
                                            0
                                            Никогда не приходилось сталкиваться и лечить ≠ ничего не надо лечить ; )
                                            Даже сходу могу сказать несколько, например: неработающий reflow при вертикальном ресайзе документа с каркасом в min-height: 100% или же глючное абсолютное позиционирование внутри инлайн (и вроде даже флоат) блоков с паддингами, а-ля блок без hasLayout в IE<=7.
                                            В случае с IE<=7 всё решается включением hasLayout ± применением position: relative, а вот в опере в лучшем случае решается добавлением обёрток : (
                                              +1
                                              Меньше всего нареканий обычно вызывают Webkit-based браузеры, потом Gecko и IE8: D
                                                0
                                                Спасибо за эти рецепты. Будет о чём подумать на досуге.

                                                А на самом деле — take it easy. Никогда не думал, что выступать в роли фанатика, просто ответил шуткой на, как мне показалось, неуместный оффтоп. Без обид :-)
                                                  0
                                                  Да я не со зла, что вы: )
                                              0
                                              Ни разу не возникало проблем с оперой.
                                              С ФФ и ИЕ бывало.
                                                0
                                                Всё ещё впереди значит: )
                                            +9
                                            В каком-то смысле /dev/random не программа. Это скорее интерфейс к генератору случ. чисел ядра, псевдоустройство.
                                              +1
                                              >Разработанный немцами ГСЧ считывает последовательность битов из памяти (метастабильное состояние) и по таблице меняет местами 0 и 1
                                              Т.е. имея в руках эту таблицу и сгенерированную последовательность, можно восстановить содержимое памяти? А содержимое какой области памяти берется?
                                              • НЛО прилетело и опубликовало эту надпись здесь
                                                  +5
                                                  Вы по критериям NIST гоняли? Интересно, что было использовано в качестве источника энтропии, а так же, для чего использовался куб. Если не затруднит, не можете кратко описать алгоритм)
                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                      0
                                                      спасибо)
                                                        0
                                                        Я бы тоже хотел подписаться =)
                                                      0
                                                      Для тестирования по тому же NIST STS если мне мой склероз не изменяет достаточно не пройти 3 :]
                                                      0
                                                      Простите, может кто ответить, что выступает источником энтропии в данном ГСЧ? он не ГПСЧ, а именно ГСЧ? Ну или сорцы показать, раз на замену /dev/random
                                                        +1
                                                        вот я тоже думаю, неужели товарищи наконец сделали прорыв и изобрели таки ГСЧ на замену ГПСЧ...) а вообще проблема то не в том что там генерит /dev/random, его случайности вполне хватает, проблема в энтропии, а по этому тексту я не вижу как они с этим разобрались.
                                                        +2
                                                        Прочитал статью, не нашел ни строчки про перестановки по таблице, но про чтение последовательностей бит из памяти.

                                                        Судя по всему, используется массив из триггеров. Кажется, это RS-триггеры, состояние которого при установке сигнала логической единицы на R-вход и S-вход в общем случае определить невозможно, т.к. зависит от малейших колебаний параметров элементов, составляющих триггер. Например, соотношение паразитных емкостей транзисторов.
                                                          +1
                                                          1-1 на RS-триггер — и результат действительно непредсказуем.
                                                            0
                                                            Очень даже предсказуем и зависит от запоминающего элемента. Но это конечно если до этого триггер был в определенном состоянии. Или я что-то неправильно понимаю? :)
                                                              +1
                                                              Для р-с триггера подача R=1, S=1 запрещённа.
                                                              И какое состояние было «до» неважно, «после» будет случайным.
                                                            0
                                                            Помнится были в инете публикации, что излучением при низких температурах удавалось заставить аппаратные Intell'овские ГСЧ (которые в hub) генерировать предсказуемую последовательность.
                                                            Так что, не всё просто с триггерами :)
                                                            0
                                                            Спасибо, буквально пару недель, как стал интересоваться ГСЧ и Ко. Добавил в закладки :)
                                                              0
                                                              «Новый „Генератор Случайных Чисел 3.14“ — еще случайнее, еще непредсказуемее!»

                                                              Я полный профан в данной области, но если гсч выдает недостаточно «случайные» числа, его нужно называть генератором псевдослучайных чисел?
                                                                0
                                                                Его нужно назвать говном. ГПСЧ — это когда по входной последовательности однозначно восстанавливается выход, тем не менее выход соответствует критериям случайной последовательности.
                                                                0
                                                                Ссылка на пдф не работает. У меня получилось скачать отсюда

                                                                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                                Самое читаемое