Потоковые шифры (лекция 2)

Август 11, 2022

Главная
Информатика
Потоковые шифры (лекция 2)

Содержание

2. Потоковый шифр — это симметричный шифр, который выполняет преобразования над битами, реже байтами и словами Шифрование
3. Процедуры шифрования и дешифрования выполняются побитово по следующим формулам Ci = Pi XOR Ki, Pi =
4. Гамма шифра - случайная или псевдослучайной последовательность Полученный зашифрованный текст является достаточно трудным для раскрытия в
5. В потоковых шифрах каждый символ открытого текста шифруется, передается и дешифруется независимо от других символов. В
6. Сфера применения потоковых шифров - военные, сетевые, телефонные и другие системы, где необходимо преобразование речевой информации
7. Классический пример потоковых шифров – шифр Вернама, или одноразовый блокнот. Если для гаммы последовательность битов выбирается
8. Поэтому основная идея современных потоковых шифров – реализовать концепцию одноразового блокнота, используя секретный ключ меньшей длины,
9. Гамму получают с помощью детерминированного генератора псевдослучайных чисел. Последовательность гаммы зависит только от параметров инициализации. Запущенный
10. Схема потокового шифра
11. Стойкость системы целиком зависит от внутренней структуры генератора ключевой последовательности.
12. Синхронные потоковые шифры Синхронные поточные шифры (СПШ) — шифры, в которых поток ключей генерируется независимо от
13. Плюсы СПШ: отсутствие эффекта распространения ошибок (только искажённый бит будет расшифрован неверно); предохраняют от любых вставок
14. Самосинхронизирующиеся поточные шифры Самосинхронизирующиеся поточные шифры (асинхронные поточные шифры (АПШ)) – шифры, в которых поток ключей
15. Реализация этого режима происходит следующим образом: каждое сообщение начинается случайным заголовком длиной N битов; заголовок шифруется,
16. Плюсы АПШ: Размешивание статистики открытого текста. Так как каждый знак открытого текста влияет на следующий шифротекст,
17. Виды гаммирования Побитовое шифрование потока данных. 2. Побитовое шифрование потока данных с обратной связью (ОС) по
18. Генераторы ПСЧ Поскольку потоковый шифр максимально должен имитировать одноразовый блокнот, то шифрующая гамма должна по своим
19. 1. физические генераторы случайных чисел – устройства, генерирующие последовательность случайных чисел на основе измеряемых параметров определенных
20. 3. алгоритмические генераторы – программно-аппаратные средства, которые генерируют псевдослучайные последовательности, похожие по свойствам на случайные числа.
21. Псевдослучайный числовой генератор должен генерировать последовательности, статистические свойства которых не должны отличаться от свойств истинно случайной
22. Если генератор криптографически безопасный, то три нижеперечисленные задачи для криптоаналитика оказываются вычислительно неразрешимыми:  определение следующего
23. Характеристики ГПСЧ Длиною периода гаммы называется минимальное количество символов, после которого последовательность начинает повторяться. Случайность распределения
24. Если гамма имеет период 2256 бит, но при этом для восстановления всей гаммы требуется только 2000
25. линейный конгруэнтный генератор псевдослучайных чисел Xi+1 = (a* Xi + b) mod m, где a, b
26. Два линейных конгруэнтных генератора могут быть объединены. Генерируется две последовательности с различными константами и из первой
27. Криптографически стойким ГПСЧ является алгоритм Блюм - Блюм - Шуба (BBS). Xi+1 = Xi2 mod m,
28. Сдвиговые регистры Сдвиговые регистры с обратной связью могут применяться для получения потока псевдослучайных бит. Сдвиговый регистр
29. Извлекать биты из сдвигового регистра можно только по одному. Если необходимо извлечь следующий бит, все биты
30. Через некоторое количество тактов работы регистра последовательность битов начнет повторяться. Длина получаемой последовательности до начала ее
31. Если длина равна n битам, то регистр называют n-битовым сдвиговым регистром. Максимальное возможное число состояний сдвигового
32. Обратные связи соответствуют коэффициентам полинома C(x)= cLxL ⊕ cL-1xL-1 ⊕… ⊕c1x+1, c∈ {0,1}, i = 1,...,
34. Для того чтобы генераторы на основе РСЛОС можно было использовать в криптографических приложениях, выходы нескольких независимо
35. ПОСТУЛАТЫ ГОЛОМБА Это необходимые, но не достаточные условия, позволяющие принять псевдослучайную последовательность за истинно случайную На
36. ФУНКЦИЯ АВТОКОРРЕЛЯЦИИ ПОСЛЕДОВАТЕЛЬНОСТИ – результат «XOR-вания» исходной последовательности и ее копии, сдвину-той на величину d ;
37. Тестирование псевдослучайных последовательностей Псевдослучайные последовательности, порождаемые любым генератором для криптографических целей, подлежат обязательному тестированию. Тестирование псевдослучайных
38. Графические тесты К этой категории относятся тесты, результаты которых отображаются в виде графиков, характеризующих свойства исследуемой
39. ГРАФИЧЕСКИЕ ТЕСТЫ ДЛЯ СТАТИСТИЧЕСКОЙ ОЦЕНКИ КАЧЕСТВА ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Гистограмма распределения элементов последовательности
40. ГРАФИЧЕСКИЕ ТЕСТЫ ДЛЯ СТАТИСТИЧЕСКОЙ ОЦЕНКИ КАЧЕСТВА ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Распределение на плоскости Поле размером , где –
41. Выходная последовательность генератора Фибоначчи Выходная последовательность генератора Галуа
42. ГРАФИЧЕСКИЕ ТЕСТЫ ДЛЯ СТАТИСТИЧЕСКОЙ ОЦЕНКИ КАЧЕСТВА ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Графическая проверка серий Цель – определение равномерности распределения
43. ГРАФИЧЕСКИЕ ТЕСТЫ ДЛЯ СТАТИСТИЧЕСКОЙ ОЦЕНКИ КАЧЕСТВА ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Графическая проверка монотонности оценки равномерности распределения символов сравнением
44. Статистические тесты В отличие от графических тестов, статистические тесты выдают численную характеристику последовательности и позволяют однозначно
45. Пакет NIST STS включает в себя 16 статистических тестов, которые разработаны для проверки гипотезы о случайности
46. Частотный тест. Состоит в подсчете количества нулей и единиц в последовательности битов. Единиц и нулей должно
47. Проверка рангов матриц оценивается равномерность распределения 0 и1, для чего из членов последовательности образуются матрицы и
48. Примеры потоковых шифров A5 (шифрование в GSM) ЛРР(22) ЛРР (19) ЛРР(23) Схема упр. тактированием 8 10
50. Шифр A5. используется в современной сотовой связи в Европе и США. Шифр A5 состоит из трёх
51. Генератор A5 состоит из трёх регистров сдвига с обратной связью, причём разной длины. Предположительно, длина периода
52. RC4 RC – сокращение от Rivest’s Cipher. Шифр не был запатентован, но находился в частной собственности
53. Далее выполняется перемешивание блоков в соответствии с ключом. j = 0 For i = 0 to
55. Скачать презентацию

Слайд 2

Потоковый шифр — это симметричный шифр, который выполняет преобразования над битами, реже

байтами и словами Шифрование и дешифрование в потоковых шифрах осуществляется путем наложения на исходный или зашифрованный текст гаммы шифра

Слайд 3

Процедуры шифрования и дешифрования выполняются побитово по следующим формулам
Ci = Pi XOR Ki,
Pi =

Ci XOR Ki.
Ci – бит исходного текста, Ki– бит гаммы, Pi – бит защифрованного текста
Иногда используется сложение и вычитание гаммы:
C = (P + K) mod N
P = (C +N - K) mod N
N – число символов в алфавите

Слайд 4

Гамма шифра - случайная или псевдослучайной последовательность
Полученный зашифрованный текст является достаточно

трудным для раскрытия в том случае, когда гамма шифра не содержит повторяющихся битовых последовательностей.
Обычно наложение гаммы заключается в использовании операции "исключающее ИЛИ", называемое также сложением по модулю 2.
Каждый бит зашифрованного текста зависит от ключа и номера шифруемого бита исходного текста.

Слайд 5

В потоковых шифрах каждый символ открытого текста шифруется, передается и дешифруется

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

Достоинства и недостатки

Слайд 6

Сфера применения потоковых шифров - военные, сетевые, телефонные и другие системы, где

необходимо преобразование речевой информации в цифровую форму и надежное шифрование данных. Причина популярности – высокое быстродействие, простота реализации и конструирования генераторов, надежность шифрования, отсутствие ошибок в потоковом шифре.

Слайд 7

Классический пример потоковых шифров – шифр Вернама, или одноразовый блокнот. Если

для гаммы последовательность битов выбирается случайно и длина гаммы равна длине сообщения, то взломать шифр невозможно. Но у данного режима шифрования есть и отрицательная особенность – проблемы с передачей и хранением ключей, ведь ключи, сравнимые по длине с передаваемыми сообщениями, трудно использовать на практике.

Слайд 8

Поэтому основная идея современных потоковых шифров – реализовать концепцию одноразового блокнота,

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

Слайд 9

Гамму получают с помощью детерминированного генератора псевдослучайных чисел. Последовательность гаммы зависит

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

Слайд 10

Схема потокового шифра

Слайд 11

Стойкость системы целиком зависит от внутренней структуры генератора ключевой последовательности.

Слайд 12

Синхронные потоковые шифры
Синхронные поточные шифры (СПШ) — шифры, в которых поток ключей

генерируется независимо от открытого текста и шифротекста и зависит только от исходного секретного ключа шифра ki = f(K)
При шифровании генератор потока ключей выдаёт биты потока ключей, которые идентичны битам потока ключей при дешифровании. Потеря знака шифротекста приведёт к нарушению синхронизации между этими двумя генераторами и невозможности расшифрования оставшейся части сообщения. Очевидно, что в этой ситуации отправитель и получатель должны повторно синхронизоваться для продолжения работы.
Обычно синхронизация производится вставкой в передаваемое сообщение специальных маркеров. В результате этого пропущенный при передаче знак приводит к неверному расшифрованию лишь до тех пор, пока не будет принят один из маркеров.

Слайд 13

Плюсы СПШ:
отсутствие эффекта распространения ошибок (только искажённый бит будет расшифрован неверно);
предохраняют

от любых вставок и удалений шифротекста, так как они приведут к потере синхронизации и будут обнаружены.
Минусы СПШ:
уязвимы к изменению отдельных бит шифрованного текста. Если злоумышленнику известен открытый текст, он может изменить эти биты так, чтобы они расшифровывались, как ему надо.

Слайд 14

Самосинхронизирующиеся поточные шифры
Самосинхронизирующиеся поточные шифры (асинхронные поточные шифры (АПШ)) – шифры, в

которых поток ключей создаётся функцией ключа и фиксированного числа знаков шифротекста.
ki = f(K,y1, y2,…,yN )
В этом случае на стороне получателя генератор начнет синхронно работать с передающей стороной после получения N битов
Расшифрующий генератор потока ключей, приняв N битов, автоматически синхронизируется с шифрующим генератором.

Слайд 15

Реализация этого режима происходит следующим образом: каждое сообщение начинается случайным заголовком

длиной N битов; заголовок шифруется, передаётся и расшифровывается; расшифровка является неправильной, зато после этих N бит оба генератора будут синхронизированы
Недостаток этих потоковых шифров – распространение ошибок, так как искажение одного бита в процессе передачи шифротекста приведет к искажению N битов гаммы.

Слайд 16

Плюсы АПШ:
Размешивание статистики открытого текста. Так как каждый знак открытого текста

влияет на следующий шифротекст, статистические свойства открытого текста распространяются на весь шифротекст. Следовательно, АПШ может быть более устойчивым к атакам на основе избыточности открытого текста, чем СПШ.
Минусы АПШ:
распространение ошибки (каждому неправильному биту шифротекста соответствуют N ошибок в открытом тексте);
чувствительны к вскрытию повторной передачей.

Слайд 17

Виды гаммирования
Побитовое шифрование потока данных.
2. Побитовое шифрование потока данных с

обратной связью (ОС) по шифртексту.
3. Побитовое шифрование потока данных с ОС по исходному тексту.
4. Побитовое шифрование потока данных с ОС по шифртексту и по исходному тексту.

Слайд 18

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

гамма должна по своим свойствам походить на истинно случайную числовую последовательность. Устройство, с помощью которого реализуют истинно случайную последовательность, называют ее генератором, а члены последовательности – случайными числами.
На сегодняшний день создано огромное количество генераторов псевдослучайных чисел. Все они являются периодическими. Но их периоды могут значительно превышать размеры данных, которые будут когда-либо зашифрованы такими генераторами, либо возможности компьютеров сгенерировать последовательность такой длины. Период последовательности в 264 считается достаточным для использования в самых серьезных криптографических приложениях.
Стойкость гаммирования однозначно определяется длиной периода гаммы

Слайд 19

1. физические генераторы случайных чисел – устройства, генерирующие последовательность случайных чисел

на основе измеряемых параметров определенных физических процессов
на основе теплового шума (обусловлен тепловым движением носителей заряда в проводнике),
интервалы времени между последовательными нажатиями на клавиатуру;
счетчик тактов процессора;
объем свободной памяти
2. табличные генераторы – таблицы случайных чисел, полученные экспериментально как выборки из равномерного распределения Недостатки: ограниченный объем таблиц, большой объем памяти компьютера при их хранении;

Слайд 20

3. алгоритмические генераторы – программно-аппаратные средства, которые генерируют псевдослучайные последовательности, похожие

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

Слайд 21

Псевдослучайный числовой генератор
должен генерировать последовательности, статистические свойства которых не должны

отличаться от свойств истинно случайной последовательности;
быть непредсказуемым, т.е. невозможно предсказать значение каких-либо членов последовательности, зная какие либо другие ее члены:
быть невоспроизводимым, т.е. разные начальные состояния генератора должны порождать разные числовые последовательности.
Период выходных последовательностей криптографически безопасного генератора должен быть очень большим. Надо соизмерять длину периода гаммы и шифруемого сообщения. К примеру, если период гаммы 232 , то гамма начнет повторяться после ~ 8,5 минут шифрования при скорости 1МВ/c).

Слайд 22

Если генератор криптографически безопасный, то три нижеперечисленные задачи для криптоаналитика оказываются

вычислительно неразрешимыми: 
определение следующего члена последовательности на основе ее известных членов (атака из прошлого); 
по известным членам последовательности невозможно восстановить предыдущие члены (атака из будущего); 
нахождение ключа по известным фрагментам гаммы конечной длины.

Слайд 23

Характеристики ГПСЧ
Длиною периода гаммы называется минимальное количество символов, после которого последовательность

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

Слайд 24

Если гамма имеет период 2256 бит, но при этом для восстановления

всей гаммы требуется только 2000 символов открытого текста, то такой алгоритм не может быть использован в криптографических целях. И если, зная 2000 символов невозможно вскрыть всю последовательность, но при этом период составляет всего 4000 символов, то такой алгоритм также не может быть использован в криптографических целях. Если гамма имеет достаточный период и непредсказуема, но при этом 75 % битов равно «1»”, то злоумышленник может восстановить ~50 % бит, не взламывая генератор. Гамма должна иметь большой период, достаточный для шифрования всех сообщений, в течение всего срока службы, быть статистически случайной и непредсказуемой

Слайд 25

линейный конгруэнтный генератор псевдослучайных чисел
Xi+1 = (a* Xi + b) mod m,
где a,

b и m – некоторые коэффициенты.
Период линейной конгруэнтной последовательности будет максимальным и равен m, если: НОД (b;m) =1;  число a -1 делится нацело на каждый простой делитель p модуля m;  число a -1 делится нацело на 4, если модуль m кратный 4. При этих условиях получаемая последовательность называется линейным генератором максимального периода.
Например, при b = 0; a = 75; m= 212 147 483 647 получим
так называемый генератор Парка – Миллера Xi+1 = 75 Xi mod 231 -1 с максимальным периодом 231 -1

Слайд 26

Два линейных конгруэнтных генератора могут быть объединены. Генерируется две последовательности с

различными константами и из первой вычитается вторая. В этом случае для модулей порядка 231, период объединенной последовательности может достигать 260.
квадратичные генераторы
Xi+1 = (a *Xi2 + b *Xi + с) mod m
кубические генераторы
Xi+1 = (a *Xi3 + b* Xi2 + c *Xi + d) mod m.

Слайд 27

Криптографически стойким ГПСЧ является алгоритм Блюм - Блюм - Шуба (BBS).
Xi+1 = Xi2 mod m,
где

m = p * q – является произведением двух больших простых p и q, сравнимых с 3 по модулю 4.
Пример с использованием двух малых простых чисел.
p = 7 (7 mod 4 = 3) и q = 19 (19 mod 4 = 3).
m = 7 * 19 = 133.
X0 = 53.
Метод Фибоначчи с запаздываниями
Xi = Xi-a — Xi-b, где переменная состояния X — беззнаковое целое. Величины запаздываний a и b берутся не какие угодно, а строго определенные, для достижения максимального качества рекомендуются пары (17,5), (55,24) или (97,33). Чем больше запаздывание, тем больше период и лучше спектральные свойства последовательности.

Слайд 28

Сдвиговые регистры
Сдвиговые регистры с обратной связью могут применяться для получения потока

псевдослучайных бит. Сдвиговый регистр с обратной связью состоит из двух частей: собственно n-битного сдвигового регистра и устройства обратной связи
Регистр представляет собой последовательность бит.

Слайд 29

Извлекать биты из сдвигового регистра можно только по одному. Если необходимо

извлечь следующий бит, все биты регистра сдвигаются влево на 1 разряд. в старший записывается выход функции обратной связи, а младший становится элементом ключевой последовательности либо проходит дополнительные преобразования.
Если функция обратной связи представляет собой сложение по модулю 2 некоторых битов регистра, то обратная связь называется линейной. Перечень битов, участвующих в сложении называется отводной последовательностью, или отводами

Слайд 30

Через некоторое количество тактов работы регистра последовательность битов начнет повторяться.
Длина получаемой последовательности

до начала ее повторения называется периодом сдвигового регистра.
Простейшим видом сдвигового регистра с обратной связью является линейный сдвиговый регистр с обратной связью (linearfeedback shift register – LFSR) или РСЛОС. Обратная связь в этом устройстве реализуется просто как сумма по модулю 2 всех (или некоторых) битов регистра. Биты, которые участвуют в обратной связи, образуют отводную последовательность. Линейные сдвиговые регистры с обратной связью или их модификации часто применяется в криптографии.

Слайд 31

Если длина равна n битам, то регистр называют n-битовым сдвиговым регистром.

Максимальное возможное число состояний сдвигового регистра равно 2n–1
Ключом РСЛОС является начальное состояние регистра и отводная последовательность. Так как не все последовательности позволяют генерировать последовательности максимальной длины, то перед использованием они должны проверяться. Для того чтобы проверить, является ли РСЛОС максимальным, необходимо из отводной последовательности и 1 образовать многочлен и проверить его на примитивность.
Многочлен является примитивным, если он является неприводимым и является делителем
Например, примитивным является многочлен .

Слайд 32

Обратные связи соответствуют коэффициентам полинома
C(x)= cLxL ⊕ cL-1xL-1 ⊕… ⊕c1x+1,
c∈ {0,1},

i = 1,..., L , c = 0,1,
0 соответствует отсутствию связи, а 1 –ее наличию. Все операции ыполняются по модулю 2.

Слайд 33

Слайд 34

Для того чтобы генераторы на основе РСЛОС можно было использовать в

криптографических приложениях, выходы нескольких независимо работающих регистров пропускают через некоторую нелинейную функцию
В качестве нелинейной комбинирующей, выбирают булеву функцию равную сумме различных произведений выходов РСЛОС. Например:
Желательно, чтобы таблица истинности такой функции содержала примерно равное число нулей и единиц.

Слайд 35

ПОСТУЛАТЫ ГОЛОМБА
Это необходимые, но не достаточные условия, позволяющие принять псевдослучайную последовательность

за истинно случайную
На периоде должны выполняться:
І ПОСТУЛАТ: |число «1» – число «0»| < 1;
ІІ ПОСТУЛАТ: половина отрезков может иметь длину 1, четверть отрезков – длину 2; восьмая часть отрез-ков – длину 4 и т.д. На периоде должна быть одинаковое количество блоков и лакун
Типы отрезков длины s: блок и лакуна
ІІІ ПОСТУЛАТ: функция автокорреляции должна быть
бути двузначной

Слайд 36

ФУНКЦИЯ АВТОКОРРЕЛЯЦИИ ПОСЛЕДОВАТЕЛЬНОСТИ
– результат «XOR-вания» исходной последовательности и ее копии,

сдвину-той на величину d ;
и – число блоков 0 и 1 в последовательности
;
– функция автокорреляции после-
довательности .
ВЫХОДНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ LFSR УДОВЛЕТВОРЯЮТ
ПОСТУЛАТАМ ГОЛОМБА

Слайд 37

Тестирование псевдослучайных последовательностей
Псевдослучайные последовательности, порождаемые любым генератором для криптографических целей, подлежат

обязательному тестированию.
Тестирование псевдослучайных последовательностей — совокупность методов определения меры близости заданной псевдослучайной последовательности к случайной. В качестве такой меры обычно выступает наличие равномерного распределения, большого периода, равной частоты появления одинаковых подстрок и т. п.
Существует несколько методов тестирования ПСП:
Ø Графический тест
Ø Статистический

Слайд 38

Графические тесты
К этой категории относятся тесты, результаты которых отображаются в виде

графиков, характеризующих свойства исследуемой последовательности. Среди них:
1. гистограмма распределения элементов последовательности (позволяет оценить равномерность распределения символов в последовательности и определить частоту повторения каждого символа);
2. распределение на плоскости (предназначено для определения зависимости между элементами последовательности);
3. проверка серий (позволяет определить равномерность отдельных символов в последовательности, а так же равномерность распределения серий из k бит);
Результаты графических тестов интерпретируются человеком, поэтому на их основе выводы могут быть неоднозначными.

Слайд 39

ГРАФИЧЕСКИЕ ТЕСТЫ ДЛЯ СТАТИСТИЧЕСКОЙ ОЦЕНКИ КАЧЕСТВА ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Гистограмма распределения элементов

последовательности

Слайд 40

ГРАФИЧЕСКИЕ ТЕСТЫ ДЛЯ СТАТИСТИЧЕСКОЙ ОЦЕНКИ КАЧЕСТВА ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Распределение на плоскости
Поле

размером , где – разрядность чисел последовательности, строят точки с координатами

Слайд 41

Выходная последовательность генератора Фибоначчи
Выходная
последовательность
генератора
Галуа

Слайд 42

ГРАФИЧЕСКИЕ ТЕСТЫ ДЛЯ СТАТИСТИЧЕСКОЙ ОЦЕНКИ КАЧЕСТВА ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Графическая проверка серий

Цель – определение равномерности распределения символов. Анализ частоты появления 0 и 1, и разных s-грамм (без перекрытия). (в последовательности подсчитывают число 0, 1, биграмм (00, 01, 10, 11), триграмм (000, 001, 010, 011, 100, 101, 110, 111) и т.д.).
Тест пройден Тест не пройден

Слайд 43

ГРАФИЧЕСКИЕ ТЕСТЫ ДЛЯ СТАТИСТИЧЕСКОЙ ОЦЕНКИ КАЧЕСТВА ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
Графическая проверка монотонности

оценки равномерности распределения символов сравнением длин отрезков невозростания и неубывания членов.

Слайд 44

Статистические тесты
В отличие от графических тестов, статистические тесты выдают численную характеристику

последовательности и позволяют однозначно сказать, пройден ли тест. Наиболее известные тесты:
§ Подборка статистических тестов Д. Кнута;
§ DIEHARD;
§ CRYPT-X;
§ NIST STS;

Слайд 45

Пакет NIST STS включает в себя 16 статистических тестов, которые разработаны

для проверки гипотезы о случайности двоичных последовательностей произвольной длины, порождаемых ГСЧ или ГПСЧ. Все тесты направлены на выявление различных дефектов случайности. Основным принципом тестирования является проверка нулевой гипотезы Н0, заключающейся в том, что тестируемая последовательность является случайной. Альтернативной гипотезой На является гипотеза о том, что тестируемая последовательность не случайна. По результатам применения каждого теста нулевая гипотеза либо принимается, либо отвергается. Решение о том, что будет ли заданная последовательность нулей и единиц случайной или нет принимается по совокупности результатов всех тестов.

Слайд 46

Частотный тест. Состоит в подсчете количества нулей и единиц в

последовательности битов. Единиц и нулей должно быть примерно поровну.
Тест на последовательность одинаковых битов. Ищутся ряды одинаковых битов, вида 000...0 или 111...1. Распределение частот, с которыми встречаются ряды, в зависимости от их длины, должно соответствовать такому распределению для истинно случайного сигнала.
Автокорреляционный тест. Подсчитывается значение корреляции между копиями последовательности, сдвинутыми друг относительно друга. Тест позволяет найти повторяющиеся участки в последовательности.

Слайд 47

Проверка рангов матриц оценивается равномерность распределения 0 и1, для чего из

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

Слайд 48

Примеры потоковых шифров
A5 (шифрование в GSM)
ЛРР(22)
ЛРР (19)
ЛРР(23)
Схема упр. тактированием
8
10
10

Слайд 49

Слайд 50

Шифр A5.
используется в современной сотовой связи в Европе и США. Шифр

A5 состоит из трёх регистров сдвига.

Слайд 51

Генератор A5 состоит из трёх регистров сдвига с обратной связью, причём

разной длины. Предположительно, длина периода равна перемножению периодов каждого из трёх генераторов, причём здесь используется нетривиальная схема тактирования. Выделяется 3 бита, а затем вычисляется мажоритарная функция, и дальше сдвигаются те регистры, у которых данный бит равен значению мажоритарной функции (мажоритарная функция даёт на выходе 0, если в качестве её аргументов выступают нули; если это не так, то на выходе 1). То есть сдвигаются те регистры, у которых в данных ячейках совпадающие биты. Оказалось, что у такой сложной структуры реально в среднем число периодов составляет 223 (не очень большой период для такой сложной схемы). Более того, к данному шрифту возникали претензии: по поводу генерации пароля, по поводу инициализации и т. д. Сложность атаки для данного шифра составляет 240. Это означает, что сейчас взломать данный шифр может любой персональный компьютер.

Слайд 52

RC4
RC – сокращение от Rivest’s Cipher. Шифр не был запатентован, но

находился в частной собственности и оставался коммерческой тайной. RC4 может использовать различные длины слов и различные длины ключей. Но кроме требований к лицензированию, он также подпадает под экспортные ограничения законодательства США, поэтому в России он не может быть законно использован с длиной ключа более 40 бит.
Основным определяющим параметром является размер слова n (шифр работает не с битами, а со словами). В большинстве примеров это 8 бит, но на сегодняшний день может использоваться и 16. Количество ячеек внутреннего состояния равно 2n, каждая по n бит. Необходимо, что бы все возможные слова были записаны в ячейках внутреннего состояния. На первом этапе инициализации ячейки (S-блоки) заполняются последовательно значениями от 0 до 2n -1.
For i = 0 to 2n -1
S[i] = i

Слайд 53

Далее выполняется перемешивание блоков в соответствии с ключом.
j = 0
For i

= 0 to 2n -1
j = (j + S[i] + Key[i mod l]) mod 2n
Перестановка (S[i], S[j])
Здесь Key – ключ (инициализирующая последовательность) длины l бит. Для длины ключа здесь нет никаких ограничений (кроме законодательных).
Устанавливаются значения внутренних переменных – индексов
i = 0
j = 0
После завершения этих подготовительных этапов может выполняться непосредственно шифрование.
Для каждого цикла шифрования устанавливаются новые значения индексов:
i = (i + 1) mod 2n
j = (j + S[i]) mod 2n
Выполняется перестановка блоков с индексами i и j:
Перестановка (S[i], S[j])
Результатом является:
K = S[(S[i] + S[j]) mod 2n].

Потоковые шифры (лекция 2)

Содержание

Потоковый шифр — это симметричный шифр, который выполняет преобразования над битами, реже

Процедуры шифрования и дешифрования выполняются побитово по следующим формуламCi = Pi XOR Ki, Pi =

Гамма шифра - случайная или псевдослучайной последовательностьПолученный зашифрованный текст является достаточно

В потоковых шифрах каждый символ открытого текста шифруется, передается и дешифруется

Сфера применения потоковых шифров - военные, сетевые, телефонные и другие системы, где

Классический пример потоковых шифров – шифр Вернама, или одноразовый блокнот. Если

Поэтому основная идея современных потоковых шифров – реализовать концепцию одноразового блокнота,

Гамму получают с помощью детерминированного генератора псевдослучайных чисел. Последовательность гаммы зависит

Схема потокового шифра

Стойкость системы целиком зависит от внутренней структуры генератора ключевой последовательности.

Синхронные потоковые шифрыСинхронные поточные шифры (СПШ) — шифры, в которых поток ключей

Плюсы СПШ:отсутствие эффекта распространения ошибок (только искажённый бит будет расшифрован неверно);предохраняют

Самосинхронизирующиеся поточные шифрыСамосинхронизирующиеся поточные шифры (асинхронные поточные шифры (АПШ)) – шифры, в

Реализация этого режима происходит следующим образом: каждое сообщение начинается случайным заголовком

Плюсы АПШ:Размешивание статистики открытого текста. Так как каждый знак открытого текста

Виды гаммированияПобитовое шифрование потока данных. 2. Побитовое шифрование потока данных с

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

1. физические генераторы случайных чисел – устройства, генерирующие последовательность случайных чисел

3. алгоритмические генераторы – программно-аппаратные средства, которые генерируют псевдослучайные последовательности, похожие

Псевдослучайный числовой генератор должен генерировать последовательности, статистические свойства которых не должны

Если генератор криптографически безопасный, то три нижеперечисленные задачи для криптоаналитика оказываются

Характеристики ГПСЧДлиною периода гаммы называется минимальное количество символов, после которого последовательность

Если гамма имеет период 2256 бит, но при этом для восстановления

линейный конгруэнтный генератор псевдослучайных чисел Xi+1 = (a* Xi + b) mod m, где a,

Два линейных конгруэнтных генератора могут быть объединены. Генерируется две последовательности с

Криптографически стойким ГПСЧ является алгоритм Блюм - Блюм - Шуба (BBS).Xi+1 = Xi2 mod m, где

Сдвиговые регистрыСдвиговые регистры с обратной связью могут применяться для получения потока

Извлекать биты из сдвигового регистра можно только по одному. Если необходимо

Через некоторое количество тактов работы регистра последовательность битов начнет повторяться. Длина получаемой последовательности

Если длина равна n битам, то регистр называют n-битовым сдвиговым регистром.

Обратные связи соответствуют коэффициентам полиномаC(x)= cLxL ⊕ cL-1xL-1 ⊕… ⊕c1x+1,c∈ {0,1},

Для того чтобы генераторы на основе РСЛОС можно было использовать в

ПОСТУЛАТЫ ГОЛОМБАЭто необходимые, но не достаточные условия, позволяющие принять псевдослучайную последовательность

ФУНКЦИЯ АВТОКОРРЕЛЯЦИИ ПОСЛЕДОВАТЕЛЬНОСТИ – результат «XOR-вания» исходной последовательности и ее копии,

Тестирование псевдослучайных последовательностейПсевдослучайные последовательности, порождаемые любым генератором для криптографических целей, подлежат

Графические тесты К этой категории относятся тесты, результаты которых отображаются в виде

ГРАФИЧЕСКИЕ ТЕСТЫ ДЛЯ СТАТИСТИЧЕСКОЙ ОЦЕНКИ КАЧЕСТВА ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Гистограмма распределения элементов

ГРАФИЧЕСКИЕ ТЕСТЫ ДЛЯ СТАТИСТИЧЕСКОЙ ОЦЕНКИ КАЧЕСТВА ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Распределение на плоскостиПоле

Выходная последовательность генератора ФибоначчиВыходная последовательность генератора Галуа

ГРАФИЧЕСКИЕ ТЕСТЫ ДЛЯ СТАТИСТИЧЕСКОЙ ОЦЕНКИ КАЧЕСТВА ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Графическая проверка серий

ГРАФИЧЕСКИЕ ТЕСТЫ ДЛЯ СТАТИСТИЧЕСКОЙ ОЦЕНКИ КАЧЕСТВА ПСЕВДОСЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ Графическая проверка монотонности

Статистические тесты В отличие от графических тестов, статистические тесты выдают численную характеристику