Математика и криптография. - презентация

1 Математика и криптография

2 Защита информации Математика Криптография

3 Что такое криптография? А) Наука о способах преобразования информации с целью ее защиты от посторонних. Б) Область научных и инженерно-технических исследований и практической деятельности, которая занимается разработкой, анализом и обоснованием стойкости криптографических средств защиты информации от угроз со стороны противника. Основные задачи криптографии – обеспечение секретности,целостности, аутентификации, невозможности отказа, неотслеживаемости

4 Классические шифры Текстm1m1 m2m2 …mTmT Шифр (m 1 ) (m 2 ) … (m T ) Шифр простой замены. A={a 1,…,a N } – алфавит открытого текста, B={b 1,…,b N } – алфавит шифртекста. Ключ – функция (подстановка) : A B, S N Обратное преобразование –1. Число ключей = N! Сохраняются частоты букв и структура текста: А.Конан-Дойль, Э.По Шифр Цезаря: сдвиг по алфавиту на 3 буквы: (a)=d, (b)=e, (c)=f, (d)=g, (e)=h,…

5 Классические шифры Шифр Виженера (XVI век) Ключ – лозунг k 0 k 1 …k L–1 в алфавите A={a 1,…,a N } = Z N. Открытый текст M={m 1 m 2 …}, Шифртекст C = {c 1 c 2 …}: c t = m t + k t mod L, t =1,2,… Обратное преобразование - вычитание абвгд аабвгд ббвгде ввгдеж ггдежз ддежзи Вернам (1926): лозунг бесконечной длины

6 Классические шифры Сложение с ключом по модулю – простая замена В шифрах Виженера и Вернама выбором этих замен (подстановок) управляет лозунг. Дисковый шифратор – устройство, которое способом, зависящим от ключа, вырабатывает последовательность наборов подстановок ( t1, t2,…, tk ), t =1,2,… Текст M={m 1,m 2,…} шифруется произведениями t = tk tk–1 … t1 : c t = t m t, t = 1,2,… Обратное преобразование – с помощью t –1 Пример: Энигма

7 Задача анализа Известны: шифртекст, конструкция шифратора и, возможно, открытый текст. Сколько потребуется времени для того, чтобы найти ключ? Шифр простой замены на небольшом алфавите вскрывается быстро. Шифр типа Энигмы вскрыть трудно, если подстановки t выбираются нерегулярно и равновероятно. Эти свойства должны обеспечиваться конструкцией шифратора.

8 Шифр Теоретическая схема Атаки Практическая реализация Атаки Неизвестные свойства Атаки Теперь В будущем

9 Современные Будущие Математические методы Вычислительные алгоритмы Технические возможности Будущая Современная Надежность конкретного метода защиты информации

10 Этапы развития криптографии 1) До II мировой войны: классические шифры 2) От II мировой войны до 70-х годов: интенсивная радиопереписка. Электронные шифраторы. Шеннон – основатель криптографии как науки 3) От 70-х годов: резкое увеличение спроса на защиту информации. Электронные сети связи. Криптография используется вне государственного сектора. Открытые конференции и публикации. Массовое привлечение профессиональных математиков

11 CRYPTO: 1981 – … EUROCRYPT: 1982 – … ASIACRYPT: 1990 – … Fast Software Encryption: 1994 – … Selected Areas in Cryptography: 1994 – … Public Key Cryptography: 1998 – … INDOCRYPT: 2000 – … Journal of Cryptology Designs, Codes and Cryptology Internet………. Труды по дискретной математике 1997 – … МАБИТ: 2001 –...

12 Защищен- ный канал

13 Теорема Шеннона о совершенном шифре P{μ = m} = P от (m), P{θ = k} = P K (k), P{μ = m, ξ = x} = k K: T k (m)=x P от (m) P K (k), P{ξ = x} = m Z от P{μ = m, ξ = x}, P{μ = m|ξ = x} = P{μ = m,ξ = x} / P{ξ = x}. Шифр совершенный, если для всех m Z от и x Z шт P{μ = m|ξ = x} = P{μ = m}. Теорема. а) Если шифр совершенный, то |K||Z от |. б) При |K| = |Z от | существует совершенный шифр.

14 Пусть Z от = K = {0,1,…,N–1}, P К (θ) = 1 / N, θ K, ξ =T θ (m) = m + θ (mod N). Тогда P{μ = m, ξ =x} = P от (m)P К (x–m) = 1 / N P от (m), P{ξ = x} = m 1 / N P от (m) = 1 / N и поэтому P{μ = m|ξ = x} = P от (m), т.е. шифр совершенный. Если A = {0,1,…,N–1} – алфавит, M={m 1,m 2,…,m L } – текст, θ 1,θ 2,...,θ L – независимые случайные величины, равномерно распределенные на A, то ξ 1,ξ 2,...,ξ L, где ξ j = m j + θ j (mod N), j = 1,…,L, – реализация совершенного шифра. Ключ {θ 1,θ 2,...,θ L } имеет ту же длину, что текст M. Пример совершенного по Шеннону шифра

15 Математические модели и реальность (Ω,F,P): Ω – множество элементарных событий F – σ-алгебра измеримых подмножеств (событий) P – вероятностная мера на F Случайная величина – измеримая функция ξ:Ω R Утверждения описывают свойства мер событий. а) Конкретный набор чисел – не объект теории вероятностей. Свойства набора чисел и набора функций не могут полностью совпадать. б) С вероятностной точки зрения все реализации набора независимых величин, равномерно распределенных на A = {0,…,N–1}, равноправны.

16 Псевдослучайные числа Датчик псевдослучайных чисел: устройство, преобразующее короткое начальное значение (ключ) в последовательность большой длины. Применения: статистическое моделирование, метод Монте-Карло, криптография Желательные свойства датчика: а) большая длина периода, б) неотличимость отрезков псевдослучайных чисел от отрезков реализаций независимых случайных величин, имеющих равномерное распределение.

17 Псевдослучайные числа – 2 Примеры. а) Линейный конгруэнтный датчик x n+1 = ax n + b (mod N); y n = x n /N [0,1). б) Линейная рекуррентная последовательность над конечным полем F (например, над Z N, GF(2 m )) x n+k = a 0 x n +a 1 x n+1 +…+a k–1 x n+k–1. Характеристический многочлен f(u) = u k – a k–1 u k–1 –...– a 1 u – a 0 F [u]. в) Регистр сдвига с переносом y n = x n mod 2, где x n+1 2x n (mod N), n = 0,1,... {x n } – знаки 2-адического числа M / N

18 Псевдослучайные числа – 3 Теоретико-числовые датчики г) x n+1 =a(x n ) –1 +b GF(p r ), p – простое, y n =x n p –r [0,1], x n =(x n,1,x n,2,…,x n,r ), z n =x n,1 p –1 +x n,2 p –2 +…+x n,r p –r [0,1] д) x n+1 (x n ) e (mod p r ), p – простое, НОД(e, (p r ))=1 Рассеяние (discrepancy) последовательностей: {x n [0,1] } {X n =(x dn+1,x dn+2,…,x dn+n ) [0,1] d }, M(N;b 1,…,b d ) = |{n [1,…,N]: X n [0,b 1 ] … [0,b d ]}|, D N =max{ | 1 / N M(N;b 1,…,b d ) – b 1 …b d |: 0

19 Псевдослучайные числа - 4 Условия максимальности периода а) x n+1 = ax n + b (mod N) имеет период N (b,N)=1, p|N p|a–1, 4|N 4|a–1. б) x n+k = a 0 x n +a 1 x n+1 +…+a k–1 x n+k–1 mod p имеет период p k –1 многочлен f(u) Z p [u] примитивен min{d: u d –1 делится на f(u)} = p k –1 f(u) порождает группу поля GF(p k )*. Условия примитивности многочлена = ? в) Регистр сдвига с переносом имеет период N–1, если N – простое и 2 – первообразный корень по модулю N.

20 Псевдослучайные числа - 5 Необходимые статистические и другие свойства а) Исследование условий, при которых свойства псевдослучайных последовательностей могут заметно отличаться от свойств «настоящих» случайных последовательностей б) Отсев «плохих» наборов параметров датчиков с помощью стандартных и специальных статистических критериев (наборы тестов Д.Кнута, NIST, Diehard, Testu0-1 и др.) в) Исследование возможности восстановления начального состояния датчика по частично наблюдаемым выходным значениям

21 Псевдослучайные числа – 6 Нетривиальное свойство G.Marsaglia Random numbers fall mainly in the planes. – Proc.Nat.Acad.Sci.USA, 1968 x n+1 ax n (mod N) x n+k a k x n (mod N). Если существуют такие целые числа c 0,…,c k, что c 0 +c 1 a+… +c k–1 a k–1 +c k a k 0 (mod N), то c 0 x n +c 1 x n+1 +… +c k–1 x n+k–1 +c k x n+k 0 (mod N), т.е. векторы (x n,x n+1,…,x n+k ) {0,1,…,N–1} k+1 R k+1 лежат на |c 0 |+|c 1 |+… +|c k–1 |+|c k | гиперплоскостях c 0 x n +c 1 x n+1 +… +c k–1 x n+k–1 +c k x n+k = mN, m =1,2,… Как правило, от x n переходят к y n =g(x n,x n+1,…,x n+r )

22 Формализации понятия случайности Мизес, Черч, Колмогоров, Мартин-Лёф,... A – конечный алфавит, A* – множество всех конечных слов над A, f : A* A* – вычислимое отображение. Слово y A* – описание слова x A*, если f(y)=x. Сложность L f (x) слова x относительно f – минимальная длина описания x. Отображение f:A* A* не хуже g: A* A*, если существует такое C=C f,g

23 Формализации понятия случайности – 2 Криптографический подход к псевдослучайности Датчик псевдослучайных чисел с качеством S(n) – семейство {F n } конечных автоматов. Автомат F n по случайному набору X n = {x 1,…,x n } {0,1} n строит набор Y n ={y 1,…,y k(n) } {0,1} n. Z n ={ζ 1,…,ζ k(n) } – независимые случайные величины, P{ζ m =0}= P{ζ m =1}= 1 / 2, m=1,2,…, и W n : {0,1} k(n) {0,1} – любая статистика. Если T n – сложность вычисления W n и |P{W n (Z n )=1} – P{W n (Y n )=1}| = n, то T n / n > S(n), где S(n) – заданная функция.

24 Формальная модель датчика Датчик псевдослучайных чисел – конечный автономный автомат F = (S,Y,f,g): S – множество состояний, Y – выходной алфавит, f : S S – функция переходов, g : S S – функция выхода, s n+1 = f(s n ), y n = g(s n ), n = 0,1,… Выходные последовательности конечных автоматов можно назвать детерминированными. Они всегда периодичны знаки =3, – не детерминированная последовательность! Число функций f : S S равно |S| |S|. Как правило, функция порождает период порядка |S| 1/2. g g K – модель поточного шифратора

25 Однонаправленные функции Семейство функций f n : X n Y n – однонаправленное (one-way), если для любого x X n сложность вычисления f n (x) с ростом n растет медленно, а минимальная по y Y n сложность решения уравнения f n (x)=y растет быстро. Гипотеза: f p (x)= x (mod p) и f(p,q)=pq – однонаправ- ленные функции (задачи дискретного логарифми- рования и факторизации вычислительно сложны). Теорема. Если существует однонаправленная функция, то с ее помощью можно построить хороший датчик псевдослучайных чисел.

26 Развитие шифра простой замены Текст – двоичная последовательность – разбивается на блоки длины n (n= 64, 128,…); блоки – буквы алфавита, состоящего из 2 n букв. Устройство, реализующее (зависящие от ключа θ) подстановки f θ на таком алфавите, называется блочным шифратором. Сложность решения систем уравнений {f θ (m k ) = c k } относительно θ должна быть высокой, т.е. f должна быть близка по свойствам к однонаправленной функции. Обоснованием – нижние оценки сложности, но их либо нет, либо они «теоретические».

27 Блочный шифратор AES (с 2002 г.) Блок=128 бит (16 байтов по 8 бит) A=||a ik || i,k=1,…,4. Проводится 10 циклов преобразования по 4 этапа а) a ik (a ik ) –1 в поле GF(2 8 ), к полученной матрице применяется аффинное преобразование; б) элементы i-й строки сдвигаются на i позиций вправо, i = 1,2,3,4; в) (a 1k,a 2k,a 3k,a 4k ) T a 4k x 3 +a 3k x 2 +a 2k x+a 1k GF(2 8 )[x] умножается на 03x 3 +01x 2 +01x+02 по модулю x 4 +1 и образует новый k-й столбец; г) матрица складывается с матрицей, которая зависит от ключа из 128 бит и от номера цикла.

28 Криптография с открытым ключом Be(PA)e(PA) d(SA)d(SA)A K M =e(P A,M) Противник M SASA PAPA d(S A,e(P A,M)) = M = e(P A,d(S A,M)) а) Функции e и d просто вычисляются б) Решение уравнения e(P,M) = c относительно M и нахождение S по P – вычислительно трудные задачи в) Пары (P,S) строить легко

29 Криптография с открытым ключом - 2 Применения: обмен ключами, цифровая подпись, аутентификация и др. RSA (Rivest, Shamir, Adleman). Построение: p, q – простые большие секретные числа, n=pq; (n)=(p–1)(q–1) – функция Эйлера, d – большое целое число, НОД(d, (n))=1, ed 1 (mod (n)). Ключи: P A = (n,e), S A = d, e(P,M) = M e (mod n), d(S,x) = x d (mod n) M ed M k (n)+1 M (mod n) Обоснование: сложность задачи факторизации

30 Криптография с открытым ключом - 3 Схема El-Gamal. Построение: p – большое простое число, - первообразный корень по модулю p. Ключи: S A = x {2,…,p–2}, P A = y = x (mod p). Шифрование сообщения M: выбрать случайно большое число r {2,…,p–2}, вычислить k y r (mod p) M (C 1,C 2 ) = ( r (mod p), kM (mod p)). Расшифрование: k y r ( x ) r ( r ) x (C 1 ) x (mod p), M C 2 k –1 (mod p). Обоснование: сложность задачи дискретного лога- рифмирования – решения сравнения x y (mod p)

31 Криптография с открытым ключом – 4 Сложность факторизации: простой алгоритм – O(n 1/2 ), современный асимптотически наилучший – O(exp(C(ln n) 1/3 (ln ln n) 2/3 ) Алгоритмы с такими же оценками построены для задачи дискретного логарифмирования.

32 Криптография Математика Методы: алгебры, теории чисел, теории вероятностей, теории сложности алгоритмов Разделы: конечные алгебраические структуры (группы, поля, кольца), вычислительная теория чисел, вычислительная алгебра, дискретные вероятностно-статистические задачи, логика (в том числе сложность алгоритмов)

33 Математика на конференциях по криптографии Алгебра (Конечные группы, поля, эллиптические кривые) Булевы функции и отображения конечных пространств Сложность алгоритмов Алгоритмическая теория чисел (дискретные логарифмы, факторизация) Псевдослучайные числа Труды по дискретной математике Линейные рекуррентные последовательности и обобщения Вероятностные задачи (системы случайных уравнений, распределения на конечных группах, конечные вероятностные автоматы, случайные размещения, вероятностная комбинаторика, свойства случайных последовательностей, перестановок, многочленов), Математическая статистика (полиномиальные испытания, цепи Маркова, статистики типа 2 )

34 Из ТДМ: Группы перестановок А.Ю.Зубов (ТДМ-2, 1998). Пусть S N – группа перестановок на {0,1,…,N–1}, g = (0,1,…,N–1) – циклическая перестановка, h = (0,1) S N – транспозиция, D – диаметр группы S N относительно порождающей системы {g,h}. Тогда D [(N–1)/2] ([N/2] + N – 1) + 2N – 1, D 3N 2 /4 – 2N, N четно, D 3[N/2] 2 – N + 3, N нечетно.

35 Из ТДМ: классические шифры Пусть A – конечный алфавит, A n – множество всех слов длины n над алфавитом A. В 1956 году А.А.Марков доказал, что все взаимно однозначные отображения A n A n, не распространяющие ошибок типа замены букв, являются суперпозицией шифров простой замены и перестановки. М.М.Глухов (ТДМ-4, 2001) обобщил эту теорему на отображения, не размножающие ошибки из более широкого класса: замен, удалений и вставок.

36 Из ТДМ: линейные рекуррентные последовательности А.С.Кузьмин, В.Л.Куракин, А.А.Нечаев (ТДМ-1,...,5) изучали свойства линейных и полилинейных рекуррентных последовательностей над квазифробенисовыми модулями и кольцами Галуа. В частности, рассматривались: – условия максимальности периода, – ранги координатных последовательностей, – распределения элементов циклов, – представления последовательностей.

37 Из ТДМ: теория чисел М.И.Анохин (ТДМ-3, 2000) показал, что если вероятностный алгоритм A решает задачу дискретного логарифмирования для множества N модулей с вероятностью p, то существует вероятностный алгоритм B, который находит некоторые делители чисел из N с вероятностью k, 0 < k < 1. Если A имеет полиномиальную сложность, то B тоже имеет полиномиальную сложность.

38 Из ТДМ: теория чисел В.Е.Тараканов (ТДМ-3,4, 2000 – 2001) рассматривал эллиптические кривые y 2 =x 3 +Ax+B над полем Z p, p > 3, 4A 3 +27B 2 0. Для отображения (x) = x 3 +Ax+B найдены числа элементов с k = 0, 1, 2, 3 прообразами, описаны множества элементов группы эллиптической кривой, имеющих порядки 3, 4. Найдено условие, необходимое и достаточное для того, чтобы по- рядок точки эллиптической кривой был равен 2.

39 Из ТДМ: вероятностные автоматы С.Ю.Мельников (ТДМ-7,2004) показал, что для конечного неавтономного автомата множество возможных совместных распределений слов из заданного множества во входных и выходных периодических последовательностях образует выпуклый многогранник. В.А.Иванов (ТДМ-2,3) получил формулы для вероятности изменения символа на выходе конечного неавтономного автоматав результате искажения символа входной последовательности.

40 Из ТДМ: теория вероятностей Г.И.Ивченко, Ю.И.Медведев (ТДМ-2,...,8) применили методы теории разделимых статистик к задачам случайных размещений частиц, случайным многочленам, случайным перестановкам, обобщенным урнам Пойа. Б.А.Севастьянов (ТДМ-3, 2000) нашел предельные распределения перманентов случайных m n-матриц над конечным полем GF(p).

41 Из ТДМ: теория вероятностей В.Г.Михайлов, А.М.Шойтов (ТДМ-3,7,8). Пусть 1,…, n – последовательность независимых одинаково распределенных случайных величин. Доказаны предельные теоремы для числа таких пар (i,j), что s-цепочки ( i+1, i+2,…, i+s ) и ( j,…, j+s ) «похожи», например, различаются только перестановкой элементов. А.М.Зубков (ТДМ-5,2002) предложил эффективный метод точного вычисления распределений сумм зависимых случайных величин, основанный на использовании цепей Маркова.

42 Из ТДМ: математическая статистика Цикл работ М.И.Тихомировой и В.П.Чистякова (ТДМ-1,...,8) посвящен исследованиям статистических критериев (обобщениям критерия Пирсона) для проверки статистических гипотез о структуре дискретных случайных последовательностей; критерии основаны на частотах цепочек, образованных элементами последовательности.