Криптостойкий генератор псевдослучайных чисел

Министерство образования и науки Российской Федерации  
КАЗАНСКИЙ (ПРИВОЛЖСКИЙ) ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ  
ИНСТИТУТ ФИЗИКИ   

КАФЕДРА РАДИОФИЗИКИ   

Направление: 10.03.01 –   Безопасность автоматизированных  систем 


Курсовая работа
Криптостойкий генератор псевдослучайных чисел





Работу выполнил: 
студент гр.06-408        
«___»_________ 2017 г.                                                                               ___________ Фомин А. Е. 

Научный руководитель:
ассистент кафедры радиофизики 
«___»_________ 2017 г.                                                                               ___________ Шагиев Р. И.             

Казань – 2017 

Оглавление
Введение	3




1. Введение
В современном мире сложно представить жизнь без свободного доступа к информации, ведь даже 200 лет назад было сказано: «Кто владеет информацией - владеет всем». Мы привыкли получать доступ к чему угодно, когда угодно, где угодно и на каких угодно языках. Основным помощником в в этом вопросе являются интернет-технологии, поскольку мы живём в эпоху глобального развития IT. А ведь всего 20 лет назад, за получением информации приходилось ходить в библиотеки, покупать журналы и газеты для того, чтобы узнать хотя бы актуальные новости. 
Большей частью нашей жизни стали мессенджеры, социальные сети, неограниченный доступ к фильмам и музыке, навигация с помощью интернета, и прочее. Это доказывает, что интернет плотно вошел в нашу жизнь, а смартфон заменил десятки книжек и устройств. В начале мая 2017 года  компания Microsoft официально опубликовала следующую информацию:
Глобальный интернет трафик: В 1992 году - 100 ГБ в день, в 2017 году - 20.000 ГБ в секунду. 
Поток обмена данными за 15 лет увеличился почти в 2 миллиона. Современное общество все в большей степени становится информационно обусловленным, успех любого вида деятельности все сильней зависит от обладания определенными сведениями и от их отсутствия у конкурентов. И чем сильней проявляется конкуренция на основе ,владения информации тем больше потенциальные убытки от злоупотреблений в информационной сфере, и тем больше потребность в защите информации.
Широкое применение компьютерных технологий и постоянное увеличение объема информационных потоков вызывает постоянный рост интереса к способам защиты информации. Проблема использования методов шифрования в информационных системах (ИС) стала в настоящий момент особо актуальна, поскольку расширилось использование компьютерных сетей, в частности глобальной сети Internet, по которым передаются большие объемы информации государственного, военного, коммерческого и частного характера, не допускающего возможность доступа к ней посторонних лиц. Чтобы передать конфиденциальную информацию нужному адресату по общедоступному каналу связи, необходимо её преобразовать таким образом, чтобы восстановить смог только получатель. Здесь речь заходит о криптографии. В последние десятилетия она широко используется во всех сферах жизни, где есть информационные технологии. 
С широким распространением письменности криптография стала формироваться как самостоятельная наука. Первые криптосистемы встречаются уже в начале нашей эры. Так, Цезарь в своей переписке использовал уже более менее систематический шифр, получивший его имя. Бурное развитие криптографические системы получили в годы первой и второй мировых войн. Начиная с послевоенного времени и по нынешний день появление вычислительных средств ускорило разработку и совершенствование криптографических методов.
Чтобы безопасно передать информацию от отправителя к получателю используются различные ключи шифрования. Например, симметричный ключ шифрования должен выбираться случайным образом. При генерации ключей для асимметричной криптосистемы необходимо иметь достаточно большой объем случайных данных. Поэтому в криптографии находят широкое применение так называемые генераторы псевдослучайных чисел (ГПСЧ).
Целью моей работы является исследование генератора псевдослучайных чисел в криптографии. Для этого мной были поставлены следующие задачи:
1. Сравнение псевдослучайного генератора с генератором случайных чисел, 
2. Проанализировать последовательности чисел на наличие закономерностей между ними;
3. Проанализировать различные генераторы случайных чисел на наличие криптостойкости;
Актуальность моей работы состоит в том, что генераторы псевдослучайных чисел гораздо дешевле использовать чем генераторы случайных чисел, потому что реализация математическим способом гораздо проще и дешевле машинного.









1. Генераторы случайных чисел
Случайная последовательность – последовательность, возникновение которой в событиях одинаково вероятно и не зависит от внешних факторов.
1.1 История создания генератора случайных чисел
Возможно, самый примитивный генератор случайных чисел - монета. С древних времен монета использовалась, чтобы разрешить определенные споры со сложностью, чтобы сделать информированный выбор. Но монета прежде не всегда имела универсальные преимущества и распределение веса. Поэтому нельзя было считать, что этот RNG генерирует независимую последовательность. И монеты были далеки от всех под рукой.
Более интересный представитель древних генераторов случайных чисел - игровой куб. Самые старые игры в кости приблизительно 5200 лет были найдены в Иране. В его сущности это - генератор, способный к генерации последовательности от 1 до 6 с равной вероятностью (если это не смещает центр тяжести). В 1890 английский проводник Francis Galton описал использование играющих костей, чтобы генерировать случайные числа в научных целях.
Дальнейшее развитие аппаратных генераторов случайных чисел может считаться специальными устройствами - lototrons, использоваться, чтобы генерировать числа в лото и кено. Они, главным образом, состоят из барабана, который смешивает шары с числами и устройство, которое извлекает их из него поочередно. Но такой метод генерации очень медленный и неподходящий для автоматической генерации больших наборов данных. Для приложений были необходимы большие наборы данных. В 1939 MJ Kendall и B. Babington-Smith создали первую машину, генерирующую случайные числа, чтобы создать таблицу, содержащую 100,000 случайных чисел. И после 16 лет, RAND Corporation, используя специальные устройства, создавала таблицу миллиона случайных чисел. Несмотря на возрождение табличного метода в 1996, Марсала, кто создавал 650 Мбайт случайных чисел, диапазон применимости таких таблиц, очень узкая
Генераторы случайных чисел, которые генерируют их в режиме реального времени, намного более широко распространены. В 1951 программа была включена в Ferranti Mark 1 компьютер, идея ??, который принадлежал A. Turing, генерируя случайные числа, используя шум Резистора. И в 1957 машина, ERNIE (Электронное оборудование Индикатора Случайного числа) был изобретен, четвертая версия которого была представлена в 2004. Это устройство было первоначально разработано, чтобы генерировать числа завоевания связей в британском lottery2.
Задача получения "случайной" последовательности чисел, используя компьютер удивительно сложна. Интуитивно, это может быть выровнено по ширине тем, что философия цифровых систем и архитектура современных компьютеров нацелены на достижение абсолютной точности, чтобы устранить даже подсказку неопределенности в результате работы. Хранившие и переданные данные сертифицируются с контрольными суммами, электрические схемы дублированы.
Много практических проблем требуют для их решения реализовать алгоритмы, которые используют достаточно длинные случайные последовательности. В каждом случае есть надлежащее понимание, из которого последовательности можно уже считать случайными и которые еще не.
Казалось бы, что природа обеспечивает достаточно хаоса, почему бы не использовать его. Достаточно сделать цифровой преобразователь для некоторого процесса (тепловые шумы, вспышки на солнце, бросая монету), соединить его с компьютером и соглашением со шляпой. Однако практическое применение "чистых" аппаратных средств RNG ограничено следующими факторами:
Во-первых, скорость генерации чисел может не быть достаточно высокой, и приложения могут использовать их так быстро, что даже современные интерфейсы как PCI Express будут загружены в глаз.
Во-вторых, статистические характеристики такой последовательности могут не быть лучшими - распределение не изменяет ни одного со временем, ширина чисел - меньше, чем требуемый, тенденция выделить нули чаще, чем (английское смещение), и т.д.
В-третьих, цена такого качественного устройства может быть довольно высокой, который ограничит его объем областями с самыми строгими требованиями для случайности.
Наконец, потребляемая мощность и размерности генератора случайных чисел могут не подойти для мобильного девайса.
Классификация генераторов случайных чисел
Случайные последовательности находят в наших жизнях все больше возможностей для приложения:
* Имитационное моделирование
* Генетические алгоритмы
* Числовая интеграция и решение систем линейных уравнений (методы Монте-Карло)
* Игры
* Генератор сеанса в PHPSESSID
* Генерация URL’ов
* Генерация CAPTCHA
* Шифрование
* Генерация соли для хранения паролей
* Генератор пароля
* Процедура для распределительных карт, лотереи, рулетки в интернет-казино
* Использование в математическом моделировании процессов
Так каким образом и как можно получить случайную последовательность?
Генераторы номеров разделены на генераторы случайных чисел и генераторы псевдослучайного числа (GPRS).
Источники энтропии используются, чтобы накопить энтропию и затем получить из него начальное значение (семя, семя) требуемый генераторами случайных чисел (RNGs), чтобы сформировать случайные числа. GPRS использует единственное начальное значение, следовательно его псевдослучайность, и RNG всегда формирует случайное число, первоначально обеспечивая высококачественную случайную переменную по различным источникам энтропии. Энтропия - мера разупорядочения. Информационная энтропия - мера неопределенности или непредсказуемость информации. Можно сказать что RNG = GPRS + источник энтропии 4
Есть два способа генерировать случайные числа (SCH):
1) использование специального физического датчика;
2) с помощью специальных программ
Физические датчики случайных эффектов
Чтобы определить случайную последовательность, определенная случайная переменная необходима. И где я могу получить его? Конечно, по своей природе! Начиная с некоторого кванта механические процессы абсолютно случайны, они - "золотой стандарт" для RNG. Явления, используемые в генераторах, включают: * Дробовой шум - шум в электрических схемах, вызванных дискретностью носителей заряда. Также этот термин вызывают шумом в оптических устройствах, вызванных дискретностью легкого поставщика услуг. В этом случае фотоэлектрический множитель или вакуумные лампы используются в качестве источника шумов. 
Радиоактивное затухание используется в качестве источника шума, так как это характеризуется случайностью каждого отдельного действия затухания. В результате различное количество частиц вводит получатель (например, Счетчик Гейгера или счетчик сцинтилляции) в различных временных интервалах. * Непосредственное параметрическое рассеивание (процесс в квантовой оптике) может также использоваться в генераторах случайных чисел.
Неквантовые явления проще обнаружить, но AHSDs на основе их будет зависеть строго от температуры (например, величина теплового шума пропорциональна температуре окружающей среды). Среди процессов, используемых в AHSD, возможно отметить: Тепловой шум в резисторе, от который, после усиления, случайный генератор напряжения получен. В частности Ferranti Mark 1 компьютерный генератор номеров основывался на этом явлении. Атмосферные помехи, измеренные радиоприемником, могут также быть приписаны приему частиц, прибывающих, чтобы Заземлить от пространства, которые зарегистрированы получателем и их числом наугад интервалы. Различие в скорости часов - явление, что штрих различных часов не будет точно тем же.
С быстрым увеличением количества компьютеров (и моделирующий), все больше внимания было обращено на методы генерации или генераторы, случайные числа, совместимые со способом, которым работают компьютеры. С этим методом генерации случайные числа сгенерированы специальным электронным присоединением - генератор (датчик) среднего диапазона, служа одним из внешних устройств компьютера. Как физический эффект, лежащий в основе таких генераторов чисел, и т.д. чаще всего используется шум в электронных и полупроводниковых устройствах, явлениях затухания радиоактивных элементов. (Количество радиоактивных частиц).
Преимущество физических датчиков - высокая скорость генерации случайных чисел.
Недостатки физических датчиков случайных чисел включают:
1) производство отдельного устройства;
2) не позволяйте гарантировать качество последовательности непосредственно во время моделирования системы на компьютере, и также получать на моделировании идентичные последовательности чисел.
Метод программного обеспечения для получения псевдослучайной последовательности
Самое большое применение в практике компьютерного моделирования для поколения последовательностей псевдослучайных чисел было получено алгоритмами формы:  1 = ?? (??) представление отношений повторения первого порядка, для которых даны начальный номер x0 и постоянные параметры.
У хорошего арифметического генератора случайных чисел должны быть следующие свойства.
1. Получающиеся числа должны быть однородно распределены в интервале [0,1] и не должны иметь корреляции друг с другом, иначе результаты моделирования могут быть абсолютно недействительными.
2. То, что генератор мог использоваться на практике, он должен иметь скорость и не требует большой памяти.
3. Генератор должен быть в состоянии точно воспроизвести данный поток случайных чисел.
4. У генератора должен быть простой способ получить отдельные потоки случайных чисел. Поток - просто часть последовательности случайных чисел, произведенных генератором, следующий поток начинается в пункте, где предыдущий заканчивается.
Алгоритмы для получения псевдослучайных чисел
Метод средних площадей
Одна из исторически первых процедур получения псевдослучайных чисел была процедурой, известной как средние площади, был предложен фон Нейманом и Метрополисом в 1940-х.
.......................