Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
36 БИЛЕТ
1. Элементы теории чисел. Функция Эйлера. Теорема Ферма.При разработке алгоритмов шифрования используется ряд понятий теории чисел и модулярной арифметики. Теория чисел, или высшая арифметика, изучает свойства целых чисел. Как наука она оформилась, начиная с открытий П. Ферма. Под целыми числами понимают числа …, -4, -3, -2, -1, 0, 1, 2, 3, 4, … Особое место среди целых чисел занимают натуральные числа – целые положительные числа 1, 2, 3, 4, … Высшая арифметика — дедуктивная наука, основанная на законах арифметики. Целые числа образуют бесконечный ряд (множество) Z, где выполняются основные арифметические операции: сложение, вычитание и умножение. Частное от деления целых чисел не всегда является целым числом. Поэтому множество целых чисел образует кольцо. Мы назовём одно число a делителем другого числа b, если b = a ⋅ c для некоторого числа c . Примем обозначение a /b, означающее, что a делит b нацело, или a является делителем b. Если число a не является делителем другого числа b, то используем обозначение: a не делит b. Натуральное число p называется простым, если p > 1 и не имеет положительных делителей, отличных от 1 и p. Натуральное число N называется составным, если N > 1 и имеет, по крайней мере, один положительный делитель, отличный от 1 и N.Функция Эйлера φ(n) — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним. При этом полагают, что число 1 взаимно просто со всеми натуральными числами, и φ(1) = 1.Например, для числа 24 существует 8 взаимно простых с ним чисел (1, 5, 7, 11, 13, 17, 19, 23), поэтому φ(24) = 8.Названа в честь Эйлера, который впервые использовал её в 1760 году в своих работах по теории чисел для доказательства малой теоремы Ферма, а затем и для доказательства более общего утверждения — теоремы Эйлера. Позднее функцию использовал Гаусс в своем труде «Арифметические исследования» (Disquisitiones Arithmeticae (англ.)), вышедшем в свет в 1801 году. Гаусс ввёл ставшее стандартным обозначение φ(n).Функция Эйлера находит применение в вопросах, касающихся теории делимости и вычетов, теории чисел, криптографии. Функция Эйлера играет ключевую роль в алгоритме RSA.Функция Эйлера показывает, сколько натуральных чисел из отрезка имеют c только один общий делитель - единицу. Функция Эйлера определена на множестве натуральных чисел, и значения ее лежат в множестве натуральных чисел.
Как следует из определения, чтобы вычислить нужно перебрать все числа от до и для каждого проверить, имеет ли оно общие делители с а затем подсчитать, сколько чисел оказались взаимно простыми с Эта процедура весьма трудоемка, поэтому для вычисления используют другие методы, которые основываются на специфических свойствах функции Эйлера.Ма́лая теоре́ма Ферма́ — классическая теорема теории чисел, которая утверждает, что Если p — простое число, и а не делится на р, то ар-1=1 (mod p). Другими словами, ар-1 при делении нацело на р даёт в остатке 1.Равносильная формулировка:Для любого простого р и целого а:(ар-а) делится на рЕсли — простое число, а и — такие положительные целые числа, что , тогда . Это утверждение используется в системе шифрования с открытым ключом RSA.Если — простое число, отличное от 2 и 5, то число , запись которого состоит из одних девяток, делится на . Отсюда легко следует, что для любого целого числа , которое не делится на 2 и на 5, можно
ПРОДОЛЖЕНИЕ БИЛЕТА 36
подобрать число, состоящее только из девяток, которое делится на . Этот факт используется в теории признаков делимости и периодических дробей.
Малая теорема Ферма является частным случаем теоремы Эйлера, которая, в свою очередь, является частным случаем теорем Кармайкла и Лагранжа для конечных циклических групп.
2. Алгоритмы шифрования Виженера, Цезаря.
Шифр Цезаря — это вид шифра подстановки, в котором каждый символ в открытом тексте заменяется буквой находящейся на некоторое постоянное число позиций левее или правее него в алфавите. Например, в шифре со сдвигом 3 А была бы заменена на Г, Б станет Д, и так далее.
Шифр назван в честь римского императора Гая Юлия Цезаря, использовавшего его для секретной переписки со своими генералами.
Шаг шифрования, выполняемый шифром Цезаря, часто включается как часть более сложных схем, таких как шифр Виженера, и все ещё имеет современное приложение в системе ROT13. Как и все моноалфавитные шифры, шифр Цезаря легко взламывается и не имеет практически никакого применения на практике.
Этот метод является простой формой многоалфавитной замены. Шифр Виженера изобретался многократно. Впервые этот метод описал Джован Баттиста Беллазо (итал. Giovan Battista Bellaso) в книге La cifra del. Sig. Giovan Battista Bellasо в 1553 году, однако в XIX веке получил имя Блеза Виженера, французского дипломата. Метод прост для понимания и реализации, он является недоступным для простых методов криптоанализа.
А Б В Г Д Е Ж З И К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я
3. Задача. Зашифруйте и расшифруйте сообщение m по алгоритму RSA, при P=3, Q=11, сообщение m= «БОЛТ».
1. Вычислим n (n=p*q) n=33
2. Расчитали функцию Эйлера (f=(p-1)(q-1)) f=20
3. Возьмем открытый ключ (любое простое число) е=7.
4. Коэффициент d=3
5. Запишем двоичной записью буквы слова по их порядковому номеру (00010011100101110010)
6. Последовательность чисел шифрограммы 13 7 16 13
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №37
1 Реализация асимметричных криптосистем основана на использовании однонаправленных функций.Пусть X и Y – некоторые произвольные множества. Функция на-зывается однонаправленной функцией, если для любого элемента можно легко вычислить его образ, однако, зная элемент, достаточно сложно получить его прообраз, хотя такой элемент x однозначно существует хотя бы один.Одним из основных критериев, по которому функцию f можно считать однонаправленной, является отсутствие эффективных алгоритмов обратного пре-образования, что не позволяет обратить данную функцию за приемлемое время.Рассмотрим несколько примеров однонаправленных функций, имеющих большое значение для криптографии.
Целочисленное умножение
Вычисление произведения двух очень больших целых чисел P и Q (N=P*Q) является несложной задачей для ЭВМ. Однако, решение обратной за-дачи, заключающейся в нахождении делителей P и Q большого числа N (в осо-бенности, когда P и Q – большие простые числа), является практически нераз-решимой задачей при больших N. Если N?2664 и P?Q, то задача факторизации не разрешима за приемлемое время на современных ЭВМ. Поэтому целочисленное умножение является однонаправленной функцией.
Модульная экспонента
Возведение очень большого числа A в очень большую степень x по любо-му модулю M ( ), то есть вычисление является не-сложной задачей для ЭВМ. Однако решение обратной задачи – нахождения степени x по известным у,A,M такой, что (задача дискретного логарифмирования, ), практически не разрешима за приемлемое время на современных ЭВМ (эффективного алгоритма вычисления дискретного логарифма пока не найдено). Поэтому модульная экспонента является однонаправленной функцией.
2. Защита информации в интернете
Интернет – это общая, открытая и небезопасная сеть. Вирусы, трояны, шпионские программы – это факторы риска, угрожающие работоспособности вашего компьютера и безопасности персональной информации после выхода в Интернет.
Платой за пользование Internet является всеобщее снижение информационной безопасности, поэтому для предотвращения несанкционированного доступа к своим компьютерам все корпоративные и ведомственные сети, а также предприятия, использующие технологию intranet, ставят фильтры (fire-wall) между внутренней сетью и Internet, что фактически означает выход из единого адресного пространства. Еще большую безопасность даст отход от протокола TCP/IP.
Одним из наиболее распространенных механизмов защиты от интернетовских бандитов - “хакеров” является применение межсетевых экранов - брэндмауэров (firewalls).
Также существует множество антивирусов предназначенных для защиты информации в интернетею Например: Kaspersky Internet security, Doctor Web, NOD 32, Avast и т.д. Которые служат для обнаружения компьютерных вирусов, а также нежелательных (считающихся вредоносными) программ вообще и восстановления зараженных (модифицированных) такими программами файлов, а также для профилактики — предотвращения заражения (модификации) информации (данных) или операционной системы вредоносным код.
ЗАДАЧА RSA (23)
Зашифровать сообщение
m={заря};p=3 q=13;Решение;{заря}={7, 1, 17, 32};n=p*q=36;f(p,q)=(p-1)(q-1)=24
Выберем е=7;d находим из условия;e*d mod f(p,q) = 1;7*d mod 24 = 1
Используя метод Эвклида
d=7 Проверка: 7*7 mod 24=49 mod 24= 1
(7, 36) – открытый ключ
Зашифруем сообщение открытым ключом (7, 36)
7 7 mod 36 = 13
1 7 mod 36 = 1
17 7 mod 36 = 17
32 7 mod 36 = 32
m'={13, 1, 17, 32}
расшифруем сообщение:
13 7 mod 36 = 13
1 7 mod 36 = 1
17 7 mod 36 = 17
32 7 mod 36 = 32
m={13, 1, 17, 32}={заря}
ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №38
1. Простой и обобщенный алгоритмы Эвклида.
Алгоритм Эвклида для целых чисел
Пусть и — целые числа, не равные одновременно нулю, и последовательность чисел
определена тем, что каждое — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть
Тогда НОД(a,b), наибольший общий делитель и , равен , последнему ненулевому члену этой последовательности.
Существование таких , то есть возможность деления с остатком на для любого целого и целого , доказывается индукцией по m.
Корректность этого алгоритма вытекает из следующих двух утверждений:
Доказательство
Проще сформулировать алгоритм Евклида так: если даны натуральные числа и и, пока получается положительное число, по очереди вычитать из большего меньшее, то в результате получится НОД.
3. Для шифра Эль-Гамаля с заданными параметрами p,g,CB,K найти недостающие параметры и описать процесс передачи сообщения пользователю В. Дано p=23, g=7, CB= 3, K=15,m=5Для всей группы абонентов выбираются некоторое большое про стое число р и число g, такие, что различные степени g суть различные числа по модулю р. Числа р и g передаются абонентам в открытом виде. Затем каждый абонент группы выбирает свое секретное число ci, 1<Ci<р-1, и вычисляет соответствующее ему открытое число di по формуле di=gcimodp.
Пусть пользователь A выбрал для себя секретное число сA = 5 и вычислил соответствующее ему открытое число da = 75 mod 23 = 17. Также поступил и пользователь B, выбрав CB= 3 и вычислив db = 73 mod 23 = 21.
Передадим сообщение m = 5 от А к В. Возьмем р = 23, g = 7.
Пользователь А выбирает случайно число k, например k = 15, и вычисляет:
r = gk mod p = 715 mod 23 = 14
е = m dBk mod p = 52115 mod 23 = 12
Теперь A посылает к В зашифрованное сообщение в виде пары чисел (r, е).
В, получив (r,е), вычисляет m' = е rp-1-cBmod р = 121423-1-3 mod 23= 5. Мы видим, что В смог расшифровать переданное сообщение.
2. Блочное и потоковое шифрование
|
Блочные алгоритмы |
|
Как уже было сказано выше, в блочных схемах открытый текст разбивается на блоки и эти блоки обрабатывается алгоритмом шифрования независимо друг от друга. |
|
В качестве алгоритма может применяться один из криптографических примитивов. Примером такого примитива является сеть Фейстеля, использующаяся во множестве блочных шифров. |
|
Сообщение разбивается на блоки, каждый блок сообщения делится на две части, левую и правую, и проходят n раундов преобразования. В каждом раунде новая правая часть получается как сумма по модулю два предыдущей левой части с результатом шифрования предыдущей правой части, а новая левая часть равна правой части предыдущего раунда. Расшифровывание происходит в обратном порядке следования подключей. Потоковые шифры Чаще всего в качестве криптографического примитива потоковых шифров применяется регистр сдвига с линейной обратной связью (РСЛОС). БИЛЕТ №39 1. Электронно-цифровая подпись. ЭЦП - аналог ручной подписи, обеспечивающий возможность проверки, подлинности к корректности документа.Электронная цифровая подпись позволяет заменить при безбумажном документообороте традиционные печать и подпись. Цифровая подпись не имеет ничего общего с последовательностью символов, соответствующих печати или подписи, приписанной к документу. При построении цифровой подписи вместо обычной связи между печатью или рукописной подписью и листом бумаги выступает сложная математическая зависимость между документом, секретным и общедоступным ключами, а также цифровой подписью. Получение фальшивой подписи, не имея секретного ключа — задача практически нерешаемая даже для очень слабых шифров и хэшей.Электронная цифровая подпись может иметь следующее назначение:1)Удостоверение источника документа. В зависимости от деталей определения документа могут быть подписаны такие поля, как «автор», «внесённые изменения», «метка времени» и т. д. 2)Защиту от изменений документа. При любом случайном или преднамеренном изменении документа (или подписи) изменится хэш, следовательно, подпись станет недействительной. 3)Невозможность отказа от авторства. Так как создать корректную подпись можно, лишь зная закрытый ключ, а он известен только владельцу, то владелец не может отказаться от своей подписи под документом. 4)Предприятиям и коммерческим организациям сдачу финансовой отчетности в государственные учреждения в электронном виде 3. Для шифра Эль-Гамаля с заданными параметрами p,g,CB,K найти недостающие параметры и описать процесс передачи сообщения пользователю В. Дано p=23, g=7, CB= 3, K=15,m=5 Для всей группы абонентов выбираются некоторое большое про стое число р и число g, такие, что различные степени g суть различные числа по модулю р. Числа р и g передаются абонентам в открытом виде. Затем каждый абонент группы выбирает свое секретное число ci, 1<Ci<р-1, и вычисляет соответствующее ему открытое число di по формуле di=gcimodp. Пусть пользователь A выбрал для себя секретное число сA = 5 и вычислил соответствующее ему открытое число da = 75 mod 23 = 17. Также поступил и пользователь B, выбрав CB= 3 и вычислив db = 73 mod 23 = 21. Передадим сообщение m = 5 от А к В. Возьмем р = 23, g = 7. Пользователь А выбирает случайно число k, например k = 15, и вычисляет: r = gk mod p = 715 mod 23 = 14 е = m dBk mod p = 52115 mod 23 = 12 Теперь A посылает к В зашифрованное сообщение в виде пары чисел (r, е). В, получив (r,е), вычисляет m' = е rp-1-cBmod р = 121423-1-3 mod 23= 5. Мы видим, что В смог расшифровать переданное сообщение. |