close

Вход

Забыли?

вход по аккаунту

?

Krizhanovskii Kireeva Pugin Sredstva obespech inform bezop v setyah peredahi dannih

код для вставкиСкачать
Министерство связи и массовых коммуникаций Российской Федерации
Государственное образовательное учреждение
высшего профессионального образования
ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ
ЭЛЕКТРОННАЯ
БИБЛИОТЕЧНАЯ СИСТЕМА
Самара
Федеральное агентство связи
Государственное образовательное учреждение высшего
профессионального образования
Поволжская государственная академия телекоммуникаций
и информатики
Кафедра передачи дискретных сообщений
Задачи и методические указания для практических
занятий по дисциплине
СРЕДСТВА ОБЕСПЕЧЕНИЯ ИНФОРМАЦИОННОЙ
БЕЗОПАСНОСТИ В СЕТЯХ ПЕРЕДАЧИ ДАННЫХ
для студентов, обучающихся по специальностям 210403,210404,210406
Составители:
к.т.н., доцент Крыжановский А.В.
к.т.н., доцент Киреева Н.В.
к.т.н., доцент Пугин В.В.
Редактор:
д.т.н., профессор Лихтциндер Б.Я.
Рецензент:
д.т.н., профессор Карташевский В.Г
Самара 2008
2
Задачи и методические указания для практических по дисциплине « Средства обеспечения информационной безопасности в сетях передачи данных» /Сост.
к.т.н., доцент А.В.Крыжановский, к.т.н., доцент Н.В.Киреева, к.т.н., доцент
В.В.Пугин – Самара, 2008-61 с.,ил.
Приведены краткие теоретические сведения, тексты задач и решения к ним
по основным аспектам информационной безопасности: симметричные и асимметричные криптосистемы, политика безопасности, электронная цифровая
подпись, распределение ключей в компьютерной сети, протоколы идентификации и аутентификации.
Методические разработки утверждены на заседании кафедры ПДС
12.03.2008 г. протокол № 5.
Редактор – д.т.н., профессор Б.Я.Лихтциндер
Рецензент – д.т.н., профессор В.Г. Карташевский
3
Содержание
Занятие 1
Традиционные симметричные криптосистемы……………………….....4
1.1 Основные понятия и определения……............................. …………….4
1.2 Шифры перестановки………………………………………………........6
1.2.1 Шифрующие таблицы……………………………………………….6
1.2.2 Шифрование магическими квадратами……………………….. …..9
1.3 Шифры простой замены………………………………………………….11
1.3.1 Шифрование на основе квадрата Полибия…………………………….11
1.3.2 Система шифрования Цезаря………………………………………......12
1.3.3 Система Цезаря с ключевым словом……………………..…… ………13
1.3.4 Шифрующие таблицы Трисемуса………..............................................14
1.3.5 Биграммный шифр Плейфейра………………………………………...16
Занятие 2
Методы шифрования………………………………………………........18
2.1 Метод перестановок на основе маршрутов Гамильна….……………...18
2.2 Аналитические методы шифрования……………….…………………...20
Занятие 3
Асимметричная криптосистема RSA. Расширенный алгоритм
Евклида……………………………………………………………….........23
Занятие 4
Политика безопасности………………………………………………….28
Занятие 5
Алгоритмы электронной цифровой подписи………………………......32
5.1 Алгоритм цифровой подписи RSA…………………………………........32
5.2 Алгоритм цифровой подписи Эль Гамаля (EGSA)…………………......35
Занятие 6
4
Распределение ключей в компьютерной сети………………………....40
6.1 Алгоритм открытого распределения ключей Диффи-Хеллмана……...40
Занятие 7
Протоколы идентификации с нулевой передачей знаний………........44
7.1 Упрощенная схема идентификации с нулевой передачей знаний…...44
7.2 Параллельная схема идентификации с нулевой
передачей знаний……………………………………………………………….......46
Приложение…………………………………………………….........50
5
Занятие 1
Традиционные симметричные криптосистемы
1.1 Основные понятия и определения
Большинство средств защиты информации базируется на использовании
криптографических шифров и процедур шифрования-расшифрования. В соответствии со стандартом ГОСТ 28147-89 под шифром понимают совокупность
обратимых преобразований множества открытых данных на множество зашифрованных данных, задаваемых ключом и алгоритмом криптографического преобразования.
Ключ-это конкретное секретное состояние некоторых параметров алгоритма
криптографического преобразования данных, обеспечивающее выбор только
одного варианта из всех возможных для данного алгоритма.
Основной характеристикой шифра является криптостойкость, которая определяет его стойкость к раскрытию методами криптоанализа. Обычно эта характеристика определяется интервалом времени, необходимым для раскрытия
шифра.
К шифрам, используемым для криптографической защиты информации,
предъявляется ряд требований:
● достаточная криптостойкость (надѐжность закрытия данных);
● простота процедур шифрования и расшифрования;
● незначительная избыточность информации за счет шифрования;
● нечувствительность к небольшим ошибкам шифрования и др.
В той или иной мере этим требованиям отвечают:
● шифры перестановок;
● шифры замены;
● шифры гаммирования;
● шифры, основанные на аналитических преобразованиях шифруемых данных.
Шифрование перестановкой заключается в том, что символы шифруемого
текста переставляются по определенному правилу в пределах некоторого блока
6
этого текста. При достаточной длине блока, в пределах которого осуществляется перестановка, и сложном неповторяющемся порядке перестановки можно достигнуть приемлемой для простых практических приложений стойкости
шифра.
Шифрование заменой (подстановкой) заключается в том, что символы шифруемого текста заменяются символами того же или другого алфавита в соответствии с заранее обусловленной схемой замены.
Шифрование гаммированием заключается в том, что символы шифруемого
текста складываются с символами некоторой случайной последовательности,
именуемой гаммой шифра. Стойкость шифрования определяется, в основном,
длиной (периодом) неповторяющейся части гаммы шифра. Поскольку с помощью ЭВМ можно генерировать практически бесконечную гамму шифра, то
данный способ является одним из основных для шифрования информации в автоматизированных системах.
Шифрование аналитическим преобразованием заключается в том, что шифруемый текст преобразуется по некоторому аналитическому правилу (формуле).
Например, можно использовать правило умножения вектора на матрицу,
причем умножаемая матрица является ключом шифрования (поэтому ее размер
и содержание должны храниться в секрете),а символами умножаемого вектора
последовательно служат символы шифруемого текста. Другим примером может
служить использование так называемых однонаправленных функций для построения криптосистем с открытым ключом.
Процессы шифрования и расшифрования осуществляются в рамках некоторой криптосистемы. Характерной особенностью симметричной криптосистемы
является применение одного и того же секретного ключа как при шифровании,
так и при расшифровании сообщений.
7
1.2 Шифры перестановки
При шифровании перестановкой символы шифруемого текста переставляются по определенному правилу в пределах блока этого текста.
1.2.1 Шифрующие таблицы
Правила перестановки букв в сообщении задают шифрующие таблицы. В
качестве ключа в шифрующих таблицах используются:
● размер таблицы;
● слово или фраза, задающие перестановку;
● особенности структуры таблицы.
Одним из самых примитивных табличных шифров перестановки является
простая перестановка, для которой ключом служит размер таблицы.
Задача 1.1 Зашифровать методами простой перестановки сообщение:
ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ
Решение
Сообщение записывается в таблицу поочерѐдно по столбцам. Считывание
производится по строкам.
Т
Н
П
В
Е
Г
Л
Е
А
Р
А
Д
О
Н
Р
Т
И
Е
Ь
В
О
М
О
Б
Т
М
П
Ч
И
Р
Ы
С
О
О
Ь
Шифртекст записывается группами по пять букв:
ТНПВЕ
ГЛЕАР
АДОНР
ТИЕЬВ
ОМОБТ
МПЧИР
ЫСООЬ
8
Отправитель и получатель сообщения должны заранее условиться об общем
ключе в виде размера таблицы. Объединение букв шифртекста в 5-буквенные
группы не входит в ключ шифра и осуществляется для удобства записи несмыслового текста. При расшифровании действия выполняют в обратном порядке.
Несколько большей стойкостью к раскрытию обладает метод шифрования,
называемый одиночной перестановкой по ключу. Этот метод отличается от
предыдущего тем, что столбцы таблицы переставляются по ключевому слову,
фразе или набору чисел длиной в строку таблицы.
Задача 1.2 Зашифровать сообщение задачи 1.1. методом одиночной перестановки по ключу. В качестве ключа использовать слово П Е Л И К А Н.
Решение
Составим две таблицы, заполненные текстом сообщения и ключевым словом. На рис. 1.1 представлена таблица до перестановки, а на рис. 1.2 – после
перестановки.
Ключ
П
Е
Л
И
К
А
Н
7
2
5
3
4
1
6
Т
Н
П
В
Е
Г
Л
Е
А
Р
А
Д
О
Н
Р
Т
И
Е
Ь
В
О
М
О
Б
Т
М
П
Ч
И
Р
Ы
С
О
О
Ь
Рисунок 1.1 – Таблица до перестановки
9
А
Е
И
К
Л
Н
П
1
2
3
4
5
6
7
Г
Н
В
Е
П
Л
Т
О
А
А
Д
Р
Н
Е
В
Т
Е
Ь
И
О
Р
П
О
Т
М
Б
Ч
М
О
Р
С
О
Ы
Ь
И
Рисунок 1.2 – Таблица после перестановки
В верхней строке верхней таблицы записан ключ, а номера под буквами ключа определены в соответствии с естественным порядком соответствующих букв ключа в алфавите. Если бы в ключе встретились одинаковые буквы, они бы были пронумерованы слева направо. В нижней таблице столбцы переставлены в соответствии с упорядоченными номерами букв ключа.
При считывании содержимого нижней таблицы по строкам и записи шифртекста группами по пять букв получим шифрованное сообщение:
ГНВЕП
ЛТООА
ДРНЕР
ТЕЬИО
РПОТМ
БЧМОР
СОЫЬИ
Для обеспечения дополнительной скрытности можно повторно зашифровать
сообщение, которое уже прошло шифрование. Такой метод шифрования называется двойной перестановкой. В случае двойной перестановки столбцов и
строк таблицы перестановки определяются отдельно для столбцов и отдельно
для строк. Сначала в таблицу записывается текст сообщения, потом поочередно
переставляются столбцы, а затем строки. При расшифровании порядок перестановок должен быть обратным.
Задача 1.3 Зашифровать методом двойной перестановки сообщение:
П РИ Л Е Т А Ю В О С Ь М О Г О
Для шифрования использовать ключи:
по столбцам- 4 1 3 2, по строкам- 3 1 4 2
10
Решение
Текст исходного сообщения записывается в таблицу 4×4, т.к. сообщение содержит 16 символов. Затем поочередно переставляются столбцы, а затем строки.
Исходная
таблица
1
2
Перестановка
Перестановка
столбцов
столбцов
3 4
4 1 3 2
1 Т Ю А Е
3 ПР И Л
2 О О Г М
1 Е Т А Ю
3 Р Л И П
4 В О С Ь
4 О Ь С В
2 МО Г О
1
2
3 4
3 Р Л И П
1 Т Ю А Е
4 О Ь С В
2 О О Г М
Если считывать шифртекст из правой таблицы построчно блоками по четыре буквы, то получится следующее:
ТЮАЕ ООГМ РЛИП ОЬСВ
Число вариантов двойной перестановки быстро возрастает при увеличении
размера таблицы:
• для таблицы 3×3
-
36 вариантов;
• для таблицы 4×4 -
576 вариантов;
• для таблицы 5×5 - 14400 вариантов.
Однако двойная перестановка не отличается высокой стойкостью и сравнительно просто “взламывается” при любом размере таблицы шифрования.
1.2.2 Шифрование магическими квадратами
Магическими квадратами называют квадратные таблицы с вписанными в их
клетки последовательными натуральными числами, начиная от 1, которые дают
11
в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то
же число.
Шифруемый текст вписывали в магические квадраты в соответствии с нумерацией их клеток. Если затем выписать содержимое такой таблицы по строкам,то получится шифртекст, сформированный благодаря перестановке букв
исходного сообщения. Считалось, что созданные с помощью магических квадратов шифртексты охраняет не только ключ, но и магическая сила.
Задача 1.4 Зашифровать сообщение:
ПРИЛЕТАЮ ВОСЬМОГО
с помощью магического квадрата. Считать шифртекст построчно блоками по
четыре буквы.
Решение
Используем магический квадрат 4×4 и заполним его заданным сообщением. Вначале пронумеруем буквы:
ПРИЛЕТАЮ ВОСЬМОГО
1 2 3 4 5 67 8
9 10111213141516
16
3
2
13
О
И
Р
М
5
10
11
8
Е
О
С
Ю
9
6
7
12
В
Т
А
Ь
4
15
14
1
Л
Г
О
П
Рисунок 1.3 – Магический квадрат 4х4 и его заполнение сообщением
Шифртекст, получаемый при считывании содержимого правой таблицы по
строкам, имеет вид:
12
ОИРМ ЕОСЮ ВТАЬ ЛГОП
Число магических квадратов быстро возрастает с увеличением размера
квадрата. Существует только один магический квадрат размером 3х3. Количество магических квадратов 4х4 - 880, а 5х5 - 250000.
1.3 Шифры простой замены
При шифровании заменой (подстановкой) символы шифруемого текста заменяются символами того же или другого алфавита по заранее установленным
правилам замены. В шифре простой замены каждый символ исходного текста
заменяется символами того же алфавита
наково на всем протяжении текста. Часто
ры простой замены называют шифрами
алфавитной подстановки.
























одишифодно-
1.3.1 Шифрование на основе квадрата Полибия (полибианского квадрата)
Полибианский квадрат выглядит следующим образом:
Рисунок 1.4 – Полибианский квадрат
Для шифровании в этом полибианском квадрате находили очередную букву
открытого текста и записывали в шифртекст букву, расположенную ниже неѐ в
том же столбце. Если буква текста оказывалась в нижней строчке таблицы, то
для шифртекста брали самую верхнюю букву из того же столбца.
Задача 1.5 Зашифровать сообщение  с помощью полибианского квадрата.
Решение
13
Шифртекст имеет вид 
1.3.2 Система шифрования Цезаря
Шифр Цезаря является частным случаем шифра простой замены (одноалфавитной подстановки). При шифровании исходного текста каждая буква заменялась на другую букву того же алфавита по следующему правилу. Заменяющая буква определялась путѐм смещения по алфавиту от исходной буквы на К
букв. При достижении конца алфавита выполнялся циклический переход к его
началу. Цезарь использовал шифр замены при смещении К=3. Такой шифр замены можно задать таблицей подстановок, содержащей соответствующие пары
букв открытого текста и шифртекста.
AD
JM
SV
BE
KN
TW
CF
LO
UX
DG
MP
VY
EH
NQ
WZ
FI
OR
XA
GJ
PS
YB
HK
QT
ZC
IL
RU
Рисунок1.4 - Таблица подстановок Цезаря
Задача 1.6 Зашифровать послание Цезаря:VENI VIDI VICI.
Решение
Используя таблицу подстановок (рис.1.4) получаем шифртекст: YHQL
YLGL YLFL
14
1.3.3 Система Цезаря с ключевым словом
Система шифрования Цезаря с ключевым словом является одноалфавитной
системой подстановок. Особенностью этой системы является использование
ключевого слова для смещения и изменения порядка символов в алфавите подстановок.
Задача 1.7 Зашифровать сообщение SEND MORE
MONEY по системе Цеза-
ря с ключевым словом DIPLOMAT.
Решение
Выберем некоторое число k, 0  k < 25. Ключевое слово записывается под
буквами алфавита, начиная с буквы, числовой код которой совпадает с
выбранным числом k:
012345
Оставшиеся
алфавита
буквы
подстановки
записываются
10
15
20
25
A B C D E F G H I J K L M NO P QR S T U V W XY Z
D I P LO MA T
после
ключевого слова в алфавитном порядке:
5
A B C D E F G H I J K L M N O P Q R S T U V WX Y Z
V WX Y Z D I P L O M A T B C E F G H J K N Q R S U
Теперь мы имеем подстановку для каждой буквы произвольного сообщения.
Исходное сообщение SEND MORE MONEY
шифруется как HZBY TCGZ TCBZS
Разновидностью рассмотренной системы, является система, в которой требование о различии всех букв ключевого слова не является обязательным. В
этом случае ключевое слово (или фраза) записывается без повторения одинаковых букв.
15
Задача 1. 8 Сформировать таблицу подстановок в системе с ключевой фразой
КАК ДЫМ ОТЕЧЕСТВА НАМ СЛАДОК И ПРИЯТЕН
Полагая k = 3 и исключая повторяющиеся буквы в ключевой фразе, получим
следующую систему подстановок:
0
3
АБВ Г ДЕЖЗ ИЙКЛМНОПРСТУФХЦЧШЩЬ ЫЪ Э ЮЯ
ЪЭЮКАДЫМОТЕЧ С ВНЛИПРЯБГ ЖЗ ЙУ ФХ ЦШЩ Ь
Достоинством системы Цезаря с ключевым словом является то, что количество возможных ключевых слов практически неисчерпаемо. Недостатком этой
системы является возможность взлома шифртекста на основе анализа частот
появления букв.
1.3.4 Шифрующие таблицы Трисемуса
В 1508 г. аббат из Германии Иоганн Трисемус написал печатную работу по
криптологии под названием "Полиграфия". В этой книге он впервые систематически описал применение шифрующих таблиц, заполненных алфавитом в
случайном порядке. Для получения такого шифра замены обычно использовались таблица для записи букв алфавита и ключевое слово (или фраза). В таблицу сначала вписывалось по строкам ключевое слово, причем повторяющиеся
буквы отбрасывались. Затем эта таблица дополнялась не вошедшими в нее буквами алфавита по порядку. При шифровании находят в этой таблице очередную
букву открытого текста и записывают в шифртекст букву, расположенную ниже неѐ в том же столбце. Если буква текста оказывается в нижней строке таблицы, тогда для шифртекста берут самая верхнюю букву из того же столбца.
Задача 1.9 Зашифровать таблицей Трисемуса сообщение:
16
ВЫЛЕТАЕМ ПЯТОГО
Решение
Для русского алфавита шифрующая таблица может иметь размер 48.
Шифрующая таблица выглядит так:
Б
А
Н
Д
Е
Р
О
Л
Ь
В
Г
Ж
З
И
Й
К
М
П
С
Т
У
Ф
Х
Ц
Ч
Ш Щ Ы
Ъ
Э
Ю
Я
Рисунок 1.5 - Шифрующая таблица Трисемуса с ключевым словом БАНДЕРОЛЬ
Используя эту таблицу в соответствии с вышеизложенной методикой, получаем шифртекст
ПДКЗЫВЗЧШЛЫЙСЙ.
Такие табличные шифры называются монограммными, так как шифрование
выполняется по одной букве. Трисемус первым заметил, что шифрующие таблицы позволяют шифровать сразу по две буквы. Такие шифры называются биграммными.
1.3.5 Биграммный шифр Плейфейра
Шифр Плейфейра, изобретенный в 1854 г., является наиболее известным биграммным шифром замены. Он применялся Великобританией во время первой
мировой войны. Основой шифра Плейфейра является шифрующая таблица со
случайно расположенными буквами алфавита исходных сообщений.
17
Для удобства запоминания шифрующей таблицы отправителем и получателем сообщений можно использовать ключевое слово (или фразу) при заполнении
начальных строк таблицы. В целом структура шифрующей таблицы системы
Плейфейра полностью аналогична структуре шифрующей таблицы Трисемуса.
Поэтому для пояснения процедур шифрования и расшифрования в системе
Плейфейра воспользуемся шифрующей таблицей Трисемуса из предыдущей задачи ( рис. 1.5).
Процедура шифрования включает следующие шаги.
1. Открытый текст исходного сообщения разбивается на пары букв (биграммы).
Текст должен иметь четное количество букв и в нем не должно быть биграмм, содержащих две одинаковые буквы. Если эти требования не выполнены, то текст модифицируется даже из-за незначительных орфографических
ошибок.
2. Последовательность биграмм открытого текста преобразуется с помощью
шифрующей таблицы в последовательность биграмм шифртекста по следующим правилам:
2а.Если обе буквы биграммы открытого текста не попадают на одну строку
или столбец (как, например, буквы А и Й в табл. на рис.2.6), тогда находят
буквы в углах прямоугольника, определяемого данной парой букв. (В нашем примере это – буквы АЙОВ. Пара букв АЙ отображается в пару ОВ.
Последовательность букв в биграмме шифртекста должна быть зеркально
расположенной по отношению к последовательности букв в биграмме открытого текста.)
2б.Если обе буквы биграммы открытого текста принадлежат одному столбцу
таблицы, то буквами шифртекста считаются буквы, которые лежат под
ними. (Например, биграмма НС дает биграмму шифртекста ГЩ.) Если при
этом буква открытого текста находится в нижней строке, то для шифртекста
берется соответствующая буква из верхней строки того же столбца. (Например, биграмма ВШ дает биграмму шифртекста ПА.)
18
2в.Если обе буквы биграммы открытого текста принадлежат одной строке
таблицы, то буквами шифртекста считаются буквы, которые лежат справа
от них. (Например, биграмма НО дает биграмму шифртекста ДЛ.) Если
при этом буква открытого текста находится в крайнем правом столбце, то
для шифра берут соответствующую букву из левого столбца в той же строке. (Например, биграмма ФЦ дает биграмму шифртекста ХМ.)
Задача 1.10 Зашифровать биграммным шифром Плейфера текст
ВСЕ ТАЙНОЕ СТАНЕТ ЯВНЫМ
Решение
Разобьѐм этот текст на биграммы:
ВС ЕТ АЙ НО ЕС ТА НЕ ТЯ ВН ЫМ
Данная последовательность биграмм открытого текста преобразуется с помощью шифрующей таблицы (рис. 1.5) в следующую последовательность биграмм шифртекста
ГП ДУ ОВ ДЛ НУ ПД ДР ЦЫ ГА ЧТ
При расшифровании применяется обратный порядок действий.
Шифрование биграммами резко повышает стойкость шифров к вскрытию.
Хотя книга И.Трисемуса "Полиграфия" была относительно доступной, описанные в ней идеи получили признание лишь спустя три столетия. По всей вероятности, это было обусловлено плохой осведомленностью криптографов о работах богослова и библиофила Трисемуса в области криптографии.
19
Занятие 2
Методы шифрования
2.1 Метод перестановок на основе маршрутов Гамильтона
Этот метод реализуется путем выполнения следующих шагов.
Шаг 1. Исходный текст разбивается на блоки. Если длина шифруемого текста
не кратна длине блока, то на свободные места последнего блока помещаются
служебные символы-заполнители(например,*)
Шаг 2. Символами блока заполняется таблица, в которой для каждого порядкового номера символа в блоке отводится вполне определенное место (рис. 2.1).
5
5
6
5
1
6
2
1
3
1
3
3
4
4
8
7
7
Исходная
таблица
2
2
4
7
6
8
8
Маршрут 1
Маршрут 2
Рисунок 2.1 - Вариант 8-элементной таблицы и маршрутов Гамильтона
Шаг 3. Считывание символов из таблицы осуществляется по одному из маршрутов. Увеличение числа маршрутов повышает криптостойкость шифра.
Маршруты выбирают либо последовательно, либо их очерѐдность задаѐтся
ключом К.
Шаг 4. Зашифрованная последовательность символов разбивается на блоки
фиксированной длины L. Величина L может отличаться от длины блоков, на которые разбивается исходный текст на шаге 1.
Расшифрование производится в обратном порядке.
20
Задача 2.1 Требуется зашифровать текст Т 0  <МЕТОДЫ ПЕРЕСТАНОВКИ>. Ключ и длины зашифрованных блоков равны: К=<2,1,1>, L=4. Для шифрования использовать таблицу и два маршрута, представленные на рис.2.1.
Решение
Воспользуемся вышеизложенной методикой построения шифра по шагам.
Шаг 1. Исходный текст разбивается на 3 блока:
Блок Б1 =<МЕТОДЫ П>
Блок Б 2 =<ЕРЕС ТАНО>
Б3 =<ВКИ*****>
Шаг 2. Заполняется 3 матрицы с маршрутами 2,1,1 (рис.2.2.)
Д
Ы
М
Т
Т
Е
Е
О
Е
П
-
А
Маршрут 2
*
Р
С
Н
О
Маршрут 1
*
В
К
И
*
*
*
Маршрут 1
Рисунок 2.2 - Шифрование с помощью маршрутов Гамильтона
Шаг 3. Получение шифртекста путѐм расстановки символов в соответствии с
маршрутами.
Т1 =<ОП_ТМЕЫДЕСРЕТАОНИ*КВ****>
Шаг 4. Разбиение на блоки шифртекста
Т1 =<ОП_Т МЕЫД ЕСРЕ ТАОН И*КВ ****>
Возможно применение и других маршрутов.
21
2.2 Аналитические методы шифрования
Среди аналитических методов наибольшее распространение получили методы, основанные на использовании матриц. Зашифрование К-го блока исходной
информации, представленного в виде вектора Вк  вij осуществляется путѐмперемножения матрицы ключа A  a ij и вектора Bk . В результате перемножения получается блок шифртекста в виде вектора Ck  ci , где элементы вектора
C k определяются по формуле:
Ci   aij b j ,
(2.1)
j 1
Расшифрование информации осуществляется путѐм последовательного перемножения векторов Ck и обратной матрицы A 1 .
Задача 2.2 Требуется зашифровать слово T0 =<ЗАБАВА> с помощью матрицыключа А.
1 4 8 
A= 3 7 2
6 9 5 
Решение
1.Определим числовой эквивалент исходного слова как последовательность
соответствующих порядковых номеров букв слова T0 :
TЭ =<8,1,2,1,3,1>
2.Разобьѐм Т э на два вектора В1  8,1,2 и В2  1,3,1
3. Умножим матрицу А на векторы В1 и В2 :
1 4 8  8 
С1  3 7 2  1  =
6 9 5   2 
 28
35
 
67
1 4 8  1 
С 2  3 7 2  3 =
 
6 9 5  1 
 21
 26
 
38
22
4.
Зашифрованное
слово
запишем
в
виде
последовательности
чисел
T1 =<28,35,67,21,26,38>.
Задача 2.3 Расшифровать текст, полученный в задаче 2.2.
Решение
1.Вычисляется определитель А  115 .
2.Определяется присоединѐнная матрица А* , каждый элемент которой является
алгебраическим дополнением элемента аij матрицы А:

A  

3
 43
22
17
52
 48
 15
15 
 5 
3.Получается транспонированная матрица АТ
 17
А = 3

  15
Т
 48
22 
 5 
52
 43
15
4.Вычисляется обратная матрица А 1 по формуле:
А
1
АТ
= ,
А
В результате вычислений обратная матрица имеет вид:
 17
115

1

3
А 
 115
15
 115
 52
115
43
115
 15
115
48

115 
 22 
115

5
115 
5.Определяются векторы В1 и В2 :
В1  А1С1 ; В2  А1С2
  17
115

В1   3115

 15

115
 52
115
43
115
 15
115
48
115
 22
115
5
115







 
 28   8
 35  =  1

 
 67   2

 






23
  17
115

В2   3115

 15

115
 52
115
43
115
 15
115
48
115
 22
115
5
115







 21
 26

 38



=





 1 
 3 


 1 


6.Получаем числовой эквивалент расшифрованного слова:
Tэ =<8,1,2,1,3,1>, который заменяется символами, в результате получается ис-
ходное слово
Т о  <ЗАБАВА>
Занятие 3
Асимметричная криптосистема RSA.
Расширенный алгоритм Евклида
1. Выбирают два больших простых числа pи q. Для большей криптостойкости p и q выбирают равной длины.
2. Вычисляют произведение: n=pq
3. Вычисляют z=(p-1)(q-1) и выбирают число е взаимно простое с z, т.е.
НОД (е,z)=1.
4. Для вычисления закрытого (секретного) ключа d решается сравнение
еd  1modz (1)
Решение (1) имеет вид d   1k 1 Qk 1
Для вычисления ключа d воспользуемся расширенным алгоритмом Евклида.
Для этого число
e
обращается в конечную цепную дробь:
z
e  zq 0  e1
z  e1 q1  e2
e1  e2 q 2  e3
e 2  e3 q 3  e 4
.....................
ek  2  ek 1 q k 1  ek
ek 1  ek q k  0
24
Цепная дробь имеет вид:
e
 q0 , q1 , q 2 ,.....,q k  , а последовательности Pn  и Qn 
z
числителей и знаменателей подходящих дробей к цепной дроби определяются
рекуррентно:
P2  0,
P1  1 , Q2  1,
Q1  0 .
Pn  qn Pn1  Pn2 , n  0
Qn  qn Qn1  Qn2 , n  0
Их вычисления удобно оформить в виде таблицы:
n
-2
-1
qn
0
1
2
…………….
k-1
k
q0
q1
q2
.......................
q k 1
qk
Pn
0
1
P0
P1
P2
........................
Pk 1
Pk
Qn
1
0
Q0
Q1
Q2
.....................
Qk 1
Qk
Задача 3.1 Пусть выбраны простые числа р =47 и q=71 и открытый ключ
е=71.
Требуется выполнить шифрование и дешифрование в асимметричной криптосистеме RSA сообщения:
688 232 687 966 668 3
Укажите последовательность операций.
Решение
1. z   p  1q  1  46  70  3220
2. Найдѐм секретный ключ d в результате решения сравнения:
de mod z  1 ,
d  79 mod 3220  1 .
Воспользуемся расширенным алгоритмом Евклида:
79=3220*0+79,
3220=79*40+60,
25
79=60*1+19,
60=19*3+3,
19=3*6+1,
3=1*3+0.
Результаты вычислений сведѐм в таблицу:
2
n
1
qn
Pn
0
1
Qn
1
0
0
1
2
3
4
5
0
40
1
3
6
3
1
40
41
163
1019 3220
Q1
Q2
Q3
Q4
Q5 .
Q0  q 0 Q 1 Q 2  0  0  1  1
Q1  q1Q0  Q1  40  1  0  40
Q2  q 2 Q1  Q0  1  40  1  41
Q3  q3 Q2  Q1  3  41  40  163
Q4  q 4 Q3  Q2  6  163 41  1019
Q5  q5 Q4  Q3  3  1019 163  3220
к=5 d   1k 1 Qk 1  Q4  1019
В самом деле 79  1019  1 mod 3220
79  1019  80501 ,
8051
 25,0003
3220
3220  25  80500
Следовательно, d=1019.
3. Разобьѐм сообщение на блоки mi, которые должны иметь длину, меньшую, чем п= pq = 47.17 = 3337. m1  668, m2  232, m3  687, m4  966,
m  668, m6  003
4. Затем шифруем блоки: Ci  mie modn
C1  68879 mod3337 1570, и т.д.
Получим криптограмму: С=( C1 , C2 , С3 , C4 , C5 , C6 ) =
5
=1570
C1
2756 2091 2276 2423 0158
C2
C3
C4
C5
C6 .
26
5. Для дешифрования нужно выполнить возведение в степень, используя ключ
дешифрования d, т.е. mi  Cid modn
m1  1570
1019
mod3337  688 и т.д.
Задача 3.2 Зашифровать и расшифровать сообщение САВ. Для простоты вычислений использовать небольшие числа: р =3 , q=11, открытый ключ е=7. Для
вычисления секретного ключа d воспользоваться расширенным алгоритмом
Евклида.
Решение
Действия пользователя В- получателя сообщения.
1. Выбирает р =3 и q=11.
2. Вычисляет модуль n=p*q=3*11=33.
3. Вычисляет значение функции Эйлера для n = 33:
z(33) = (p –1)(q –1) = 210 = 20.
Выбирает в качестве открытого ключа е произвольное число с учетом выполнения условий:
1< е  20, НОД (e, 20) = 1.
Пусть e= 7.
4. Вычисляет значение секретного ключа d, используя расширенный алгоритм
Евклида при решении сравнения
d  7–1 (mod 20).
Решение дает d= 3.
5. Пересылает пользователю А (отправителю) пару чисел (n = 33, e= 7).
Действия пользователя A-отправителя сообщения.
6. Представляет шифруемое сообщение как последовательность целых чисел в
диапазоне 0 ... 32. Пусть буква А представляется как число 1, буква В – как
число 2, буква С – как число 3. Тогда сообщение САВ можно представить как
последовательность чисел 312, т.е. m1 = 3, m2 = 1, m3 = 2.
27
7. Шифрует текст, представленный в виде последовательности чисел m1 , m2 и
m3 , используя ключ e= 7 и n = 33, по формуле
mie modn  mi7 mod33
Получает криптограмму:
С1 = 37 (mod 33) = 2187 (mod 33) = 9,
С2 =1 7 (mod 33) =1 (mod 33) =1,
С3 = 27 (mod 33) =128 (mod 33) = 29.
Отправляет пользователю В криптограмму
С1, С2, С3 = 9, 1, 29.
Действия пользователя В.
8. Расшифровывает принятую криптограмму С1, С2, С3, используя секретный
ключ d=3, по формуле
mi  Cid modn
Получает:
3
m1 = 9 (mod 33) = 729 (mod 33) = 3,
3
m2 =1 (mod 33) =1 (mod 33) =1,
3
m3 = 29 (mod 33) = 24389 (mod 33) = 2.
Таким образом, восстановлено исходное сообщение: С А В
31 2
28
Занятие 4
Политика безопасности
Политика безопасности – это набор правил, которые регулируют управление, защиту и распределение ценной информации.
Политика безопасности включает:
1. Множество возможных операций над объектами.
2. Множество разрешенных операций для каждой пары «субъект-объект».
Существует два типа политики безопасности:
1. дискреционная; 2. мандатная.
Дискреционная политика определяет следующие правила.
1. Все субъекты (S) и объекты (O) должны быть идентифицированы.
2. Права доступа субъекта к объекту определяются на основе некоторого внешнего по отношению к системе правила.
Дискреционная политика задается матрицей доступа:
S
O1
O2
…
On
O
S1
own, r, w
S2
…
Sm
Множество прав доступа R=(own, r, w) включает права:
own – владение, r – чтение, w – запись.
Собственник (own) может определять права доступа других субъектов к
данному объекту.
29
Мандатная политика определяет следующие правила.
1. Все субъекты и объекты должны быть идентифицированы.
2. Задан линейно упорядоченный набор меток секретности (решетка секретности).
3. Каждому объекту присваивается метка секретности, определяющая ценность
содержащейся в нем информации.
4. Каждому субъекту присваивается метка секретности, определяющая уровень
доверия к нему.
В мандатной политике вводится понятие информационного потока.
Информационный поток X  Y (Х – источник, Y – получатель) разрешен
тогда и только тогда, когда с(Y)с(Х) по решетке секретности.
В системе с двумя доступами r и w мандатная политика определяет следующие правила доступа:
X  Y  c( X )  c(Y )
X  Y  c( X )  c(Y )
Задача 4.1 В сети применяется дискреционная политика безопасности и матрица доступа имеет вид:
O1
O2
own
U1
r
w
w
own
U2
r
w
Обозначения:
U1 – законный пользователь;
30
U2 – злоумышленник;
О1 – объект, содержащий ценную информацию;
О2 – объект, содержащий программу «Троянский конь».
Показать, что злоумышленник U2 может считать ценную информацию объекта О1.
Решение
1. Злоумышленник U2 является собственником (own) программы О2.
2. Злоумышленник U2 заставляет U1 каким-либо образом запустить программу
«Троянский конь». Для этого О2 может, например, выглядеть интересной
компьютерной игрой.
3. Если пользователь U1 обратится к О2, то он запустит скрытую программу Т
(«Троянский конь»). Эта программа обладает правами доступа пользователя
О1, поскольку была им запущена.
4. Программа Т, обладая правами доступа пользователя U1, списывает (w) в
объект О2 информацию, содержащуюся в объекте О1.
5. Злоумышленник U2 владеет (own) объектом О2 и пользуясь своими правами
имеет возможность считать из объекта О2 ценную информацию объекта О1.
Задача 4.2 Требуется показать, что мандатная политика безопасности устойчива к атаке «Троянский конь».
Решение
Введем обозначения:
U1 – законный (авторизованный) пользователь;
U2 – злоумышленник;
О1 – объект, содержащий ценную информацию;
О2 – объект, содержащий программу «Троянский конь» Т.
1. Предположим, что пользователи U1 и U2 находятся на разных уровнях доступа, т.е.
31
с(U1) > c(U2) ,
(4.1)
по решетке секретности.
2. Пусть пользователь U1 размещает в объекте О1 ценную информацию, т.е.
w
U1 

O1 , при выполнении условия
с(О1)с(U1) ,
(4.2)
3. «Троянский конь», содержащийся в объекте О2, может считать информацию
из О1 при выполнении условия:
с(О2)с(О1) ,
(4.3)
4. Объединяя (4.1), (4.2) и (4.3) получим:
c(U 2 )  c(U1 )  c(O1 )

,
c(O2 )  c(O1 )
(4.4)
Из (4.4) следует, что
с(О2)>c(U1).
(4.5)
Следовательно, пользователь U2 не имеет доступа к объекту О2.
Поэтому считывание информации из объекта О1 и запись ее в объект О2
для злоумышленника U2 являются бесполезными.
Расположение меток секретности условно выглядит так:
________________с(О2)
________________с(О1)
________________с(U1)
________________с(U2)
32
Занятие 5
Алгоритмы электронной цифровой подписи
5.1 Алгоритм цифровой подписи RSA
Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электронных документов выбирает
два больших простых числа P и Q, затем находит их произведение
N=PQ ,
(5.1)
и значение функции

(N)
=
(P
–1)(Q
–1)
,
(5.2)
Далее отправитель вычисляет число E из условий:
E   (N), НОД (E,  (N)) =1 ,
(5.3)
и число D из условий:
D < N, E  D 1 (mod  (N)) ,
(5.4)
Пара чисел (E,N) является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ для подписывания.
Обобщенная схема формирования и проверки цифровой подписи RSA показана на рис.5.1.
Допустим, что отправитель хочет подписать сообщение M перед его отправкой. Сначала он сжимает сообщение M (блок информации, файл, таблица) с
помощью хэш-функции h(·) и получает число m:
m = h(M) ,
(5.5)
Затем вычисляет цифровую подпись S под электронным документом M, используя хэш-значение m и секретный ключ D:
33
S = mD (mod N) ,
(5.6)
Пара (M,S) передается партнеру-получателю как электрон-ный документ M,
подписанный цифровой подписью S, причем подпись S сформирована обладателем секретного ключа D.
После приема пары (M,S) получатель вычисляет хэш-значение сообщения M
двумя разными способами. Прежде всего он восстанавливает хэш-значение
m´, применяя криптографическое преобразование подписи S с использованием открытого ключа E:
m´ = SE (mod N) ,
(5.7)
Отправитель
Сообщение
Канал
Получатель
M
M
Блок
сжатия
m=
h(M)mD
S = mD (mod N)
SE (mod
N)=m
SE
D, N
Генератор
ключей
E,
N
?
E
Не S (mod N) =
= h(M)
т
M
Блок
сжатия
Да
m = h(M)
Рисунок 5.1- Обобщенная схема цифровой подписи RSA
Кроме того, он находит результат хэширования принятого сообщения M с
помощью такой же хэш-функции h(·):
m = h(M),
(5.8)
Если соблюдается равенство вычисленных значений, т.е.
SE (mod N) = h(M),
(5.9)
34
то получатель признает пару (M,S) подлинной. Доказано, что только обладатель секретного ключа D может сформировать цифровую подпись S по документу M, а определить секретное число D по открытому числу E не легче, чем
разложить модуль N на множители.
Кроме того, можно строго математически доказать, что результат проверки
цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ D, соответствующий открытому
ключу E. Поэтому открытый ключ E иногда называют "идентификатором"
подписавшего.
Недостатки алгоритма цифровой подписи RSA.
1. При вычислении модуля N, ключей E и D необходимо проверять большое
количество дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение. При подписании важных документов нельзя допускать такую возможность даже теоретически.
2. Для обеспечения криптостойкости цифровой подписи RSA по отношению к
попыткам фальсификации на уровне 1018 (стандарт США) необходимо использовать при вычислениях N, D и E целые числа не менее 2512 (или около 10154) ,
что требует больших вычислительных затрат, превышающих на 20…30% вычислительные затраты других алгоритмов цифровой подписи при сохранении
того же уровня криптостойкости.
3. Цифровая подпись RSA уязвима к так называемой мультипликативной атаке.
Иначе говоря, алгоритм цифровой подписи RSA позволяет злоумышленнику
без знания секретного ключа D сформировать подписи под теми документами,
у которых результат хэширования можно вычислить как произведение результатов хэширования уже подписанных документов.
5.1 Показать, что цифровая подпись RSA уязвима к мультипликативной атаке.
Решение
35
Допустим, что злоумышленник может сконструировать три сообщения M1,
M2 и M3, у которых хэш-значения
m1 = h(M1), m2 = h(M2), m3 = h(M3),
причем
m3 = m1  m2 (mod N).
Допустим также, что для двух сообщений M1 и M2 получены законные подписи
S1 = m1D (mod N) и S2 = m2D (mod N).
Тогда злоумышленник может легко вычислить подпись S3 для документа M3,
даже не зная секретного ключа D:
S3 = S1  S2 (mod N).
Действительно,
S1  S2 (mod N) = m1D  m2D (mod N) = (m1m2)D (mod N) =
= m3D (mod N) = S3.
Более надежный и удобный для реализации на персональных компьютерах
алгоритм цифровой подписи был разработан в 1984 г. американцем арабского
происхождения Тахером Эль Гамалем. В 1991 г. НИСТ США обосновал перед
комиссией Конгресса США выбор алгоритма цифровой подписи Эль Гамаля в
качестве основы для национального стандарта.
5.2 Алгоритм цифровой подписи Эль Гамаля (EGSA)
Название EGSA происходит от слов El Gamal Signature Algorithm (алгоритм цифровой подписи Эль Гамаля). Идея EGSA основана на том, что для
обоснования практической невозможности фальсификации цифровой подписи
может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа,– задача дискретного логарифмирования. Кроме того, Эль Гамалю удалось избежать явной слабости алгоритма
цифровой подписи RSA, связанной с возможностью подделки цифровой
подписи под некоторыми сообщениями без определения секретного ключа.
36
Для того чтобы сгенерировать пару ключей (открытый ключ – секретный
ключ), сначала выбирают некоторое большое простое целое число P и большое
целое число G, причем G < P. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа P (~10308
или ~21024) и G (~10154 или ~2512), которые не являются секретными.
Отправитель
выбирает
случайное
целое
число
X, 1< X  (P –1), и
вычисляет
Y = GX mod P ,
(5.10)
Число Y является открытым ключом, используемым для проверки подписи
отправителя. Число Y открыто передается всем потенциальным получателям
документов.
Число X является секретным ключом отправителя для подписывания документов и должно храниться в секрете.
Для того чтобы подписать сообщение M, сначала отправитель хэширует его
с помощью хэш-функции h(·) в целое число m:
m = h(M), 1< m < (P –1),
(5.11)
и генерирует случайное целое число K, 1< K< (P –1), такое, что K и (P –1) являются взаимно простыми. Затем отправитель вычисляет целое число a:
a = GK mod P ,
(5.12)
и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного
ключа X целое число b из уравнения
m =( X a + K  b) (mod (P –1)),
(5.13)
Пара чисел (a,b) образует цифровую подпись S:
S = (a,b),
(5.14)
37
проставляемую под документом M.
Тройка чисел (M,a,b) передается получателю, в то время как пара чисел
(X,K) держится в секрете.
После приема подписанного сообщения (M,a,b) получатель должен проверить, соответствует ли подпись S = (a,b) сообщению M. Для этого получатель
сначала вычисляет по принятому сообщению M число
m = h(M),
(5.15)
т.е. хэширует принятое сообщение M.
Затем получатель вычисляет значение
A = Ya ab (mod P),
(5.16)
и признает сообщение M подлинным, если, и только если
A = Gm (mod P),
(5.17)
Иначе говоря, получатель проверяет справедливость соотношения
Ya ab (mod P) = Gm (mod P) ,
(5.18)
Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S=(a,b) под документом M получена с помощью именно того секретного ключа X, из которого был получен
открытый ключ Y. Таким образом, можно надежно удостовериться, что отправителем сообщения M был обладатель именно данного секретного ключа X,
не раскрывая при этом сам ключ, и что отправитель подписал именно этот конкретный документ M.
Выполнение каждой подписи по методу Эль Гамаля требует нового значения K, причем это значение должно выбираться случайным образом. Если нарушитель раскроет значение K, повторно используемое отправителем, то он
сможет раскрыть секретный ключ X отправителя.
38
Задача 5.2 Сформировать и проверить ЭЦП Эль Гамаля при следующих начальных условиях: Р=11, G=2, секретный ключ Х=8.
Решение
Вычисляем значение открытого ключа:
Y = GX mod P = Y = 28 mod 11 = 3.
Предположим, что исходному сообщению M соответствует хэш-значение
m = 5.
Для того,чтобы вычислить цифровую подпись под сообщением M, имеющем
хэш-значение m = 5, сначала выберем случайное целое число K = 9. Убедимся, что числа K и (P – 1) являются взаимно простыми. Действительно,
НОД (9, 10) = 1.
Далее вычисляем элементы a и b подписи:
a = GK mod P = 29 mod 11 = 6,
элемент b определяем, используя расширенный алгоритм Евклида:
m = (X  a + K  b) (mod (P – 1)).
При m = 5, a = 6, X = 8, K = 9, P = 11 получаем
5 = (6  8 + 9  b)(mod 10)
или
9  b  – 43 (mod 10).
Решая сравнение, получаем b = 3. Цифровая подпись представляет собой пару:
а = 6, b = 3.
Далее отправитель передает подписанное сообщение. Приняв подписанное
сообщение и открытый ключ Y = 3, получатель вычисляет хэш-значение для
сообщения M : m = 5, а затем вычисляет два числа:
1) Yaab (mod P) = 36  63 (mod 11) =10 ;
2) Gm (mod P) = 25 (mod 11) =10.
39
Так как эти два целых числа равны, принятое получателем сообщение признается подлинным.
Следует отметить, что схема Эль Гамаля является характерным примером
подхода, который допускает пересылку сообщения M в открытой форме вместе
с присоединенным аутентификатором (a,b). В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия
аутентификатора сообщению.
Схема цифровой подписи Эль Гамаля имеет ряд преимуществ по сравнению
со схемой цифровой подписи RSA.
1. При заданном уровне стойкости алгоритма цифровой подписи целые числа,
участвующие в вычислениях, имеют запись на 25% короче, что уменьшает
сложность вычислений почти в два раза и позволяет заметно сократить объем
используемой памяти.
2. При выборе модуля P достаточно проверить, что это число является простым
и что у числа (P –1) имеется большой простой множитель (т.е. всего два достаточно просто проверяемых условия).
3. Процедура формирования подписи по схеме Эль Гамаля не позволяет вычислять цифровые подписи под новыми сообщениями без знания секретного ключа
(как в RSA).
Однако алгоритм цифровой подписи Эль Гамаля имеет и некоторые недостатки по сравнению со схемой подписи RSA. В частности, длина цифровой
подписи получается в 1,5 раза больше, что, в свою очередь, увеличивает время
ее вычисления.
40
Занятие 6
Распределение ключей в компьютерной сети
При использовании для информационного обмена криптосистемы с симметричным секретным ключом два пользователя, желающие обменяться криптографически защищенной информацией, должны обладать общим секретным
ключом. Пользователи должны обменяться общим ключом по каналу связи
безопасным образом. Если пользователи меняют ключ достаточно часто, то
доставка ключа превращается в серьезную проблему.
Для решения этой проблемы можно применить два способа:
1) использование криптосистемы с открытым ключом для шифрования и передачи секретного ключа симметричной криптосистемы;
2) использование системы открытого распределения ключей Диффи–Хеллмана.
6.1 Алгоритм открытого распределения ключей Диффи – Хеллмана
Алгоритм Диффи–Хеллмана был первым алгоритмом с открытыми ключами
(предложен в 1976 г.). Его безопасность обусловлена трудностью вычисления
дискретных логарифмов в конечном поле, в отличие от легкости дискретного
возведения в степень в том же конечном поле.
Предположим, что два пользователя А и В хотят организовать защищенный
коммуникационный канал.
1. Обе стороны заранее уславливаются о модуле N (N должен быть простым
числом) и примитивном элементе g, (1  g  N –1).
Эти два целых числа N и g могут не храниться в секрете. Как правило, эти
значения являются общими для всех пользователей системы.
2. Затем пользователи А и В независимо друг от друга выбирают собственные секретные ключи kА и kВ (kА и kВ – случайные большие целые числа,
которые хранятся пользователями А и В в секрете).
3. Далее пользователь А вычисляет открытый ключ
yA = gk (mod N),
A
41
а пользователь В – открытый ключ
yВ = gk (mod N).
4. Затем стороны А и В обмениваются вычисленными значениями открытых
B
ключей yA и yВ по незащищенному каналу.
5. Далее пользователи А и В вычисляют общий секретный ключ, используя
следующие выражения:
пользователь А: К = (yB )k = (gk )k (mod N);
A
B
A
пользователь В: К´ = (yA )k = (gk )k (mod N).
B
A
B
При этом К = К´, так как (gk )k = (gk )k (mod N).
B
A
A
B
Схема реализации алгоритма Диффи–Хеллмана показана на рис. 6.1.
Ключ К может использоваться в качестве общего секретного ключа (ключа
шифрования ключей) в симметричной криптосистеме. Кроме того, обе стороны
А и В могут шифровать сообщения, используя следующее преобразование
шифрования (типа RSA): С = ЕK (М) = МК (mod N).
Пользователь А
g, N
Секретный
ключ kA
Пользователь
Незащищенный
канал
В
g, N
Секретный
ключ kВ
yA = gkA (mod N)
YA = gkВ (mod N)
К = yBkA (mod N)
К´= yAkB (mod N)
К = К´= gkAkB (mod
N) алгоритма Диффи–Хеллмана
Рисунок 6.1- Схема реализации
ХХХХеХеллмана
Для выполнения расшифрования получатель сначала находит ключ расшифрования К* с помощью сравнения
К  К*  1 (mod N –1),
(6.1)
а затем восстанавливает сообщение
М = DK (C) = CK*(mod N).
(6.2)
Задача 6.1 Реализовать алгоритм открытого распределения ключей ДиффиХеллмана при следующих начальных условиях: модуль N=47, примитивный
42
элемент g=23, секретные ключи пользователей А и В: KА=12, КВ=33 соответственно.
Решение
Для того, чтобы иметь общий секретный ключ К, пользователи А и В сначала вычисляют значения частных открытых ключей:
yA =
gk A
yВ =
gkB
(mod N)= 2312(mod 47) = 27 ,
(mod N)= 2333(mod 47) = 33
После того, как пользователи А и В обменяются своими значениями y A и
yВ , они вычисляют общий секретный ключ
К = (y B )k (mod N)= (y A )k (mod N)= 3312(mod 47)= 2733 (mod 47)= =2312*33 (mod 47)=
A
B
25 .
Кроме того, они находят секретный ключ расшифрования, решая следующее сравнение:
К  К*  1 (mod N –1),
откуда К* = 35.
Если сообщение М =16, то криптограмма:
С = МК =1625(mod 47) = 21.
Получатель восстанавливает сообщение :
М = СК* = 2135(mod 47) =16.
Злоумышленник, перехватив значения N, g, yА и yВ, тоже хотел бы определить значение ключа К. Очевидный путь для решения этой задачи состоит в
вычислении такого значения kА по N, g, yА, что gk mod N = yА (поскольку в
A
этом случае, вычислив kА, можно найти К= (yB )k mod N). Однако нахождение
A
kА по N, g и yА – задача нахождения дискретного логарифма в конечном поле,
которая считается неразрешимой.
Выбор значений N и g может иметь существенное влияние на безопасность этой системы. Модуль N должен быть большим и простым числом. Чис-
43
ло (N –1)/2 также должно быть простым числом. Число g желательно выбирать таким, чтобы оно было примитивным элементом множества ZN.
Алгоритм открытого распределения ключей ДиффиХеллмана позволяет
обойтись без защищенного канала для передачи ключей. Однако, работая с
этим алгоритмом, необходимо иметь гарантию того, что пользователь А получил открытый ключ именно от пользователя В, и наоборот. Эта проблема решается с помощью электронной подписи, которой подписываются сообщения
об открытом ключе.
Метод Диффи–Хеллмана дает возможность шифровать данные при каждом
сеансе связи на новых ключах. Это позволяет не хранить секреты на дискетах
или других носителях. Не следует забывать, что любое хранение секретов повышает вероятность попадания их в руки конкурентов или противника.
Преимущество метода Диффи–Хеллмана по сравнению с методом RSA заключается в том, что формирование общего секретного ключа происходит в
сотни раз быстрее. В системе RSA генерация новых секретных и открытых
ключей основана на генерации новых простых чисел, что занимает много времени.
44
Занятие 7
Протоколы идентификации с нулевой передачей знаний
Широкое распространение интеллектуальных карт (смарт-карт) для разнообразных коммерческих, гражданских и военных применений (кредитные карты, карты социального страхования, карты доступа в охраняемое помещение,
компьютерные пароли и ключи, и т.п.) потребовало обеспечения безопасной
идентификации таких карт и их владельцев. Во многих приложениях главная
проблема заключается в том, чтобы при предъявлении интеллектуальной карты
оперативно обнаружить обман и отказать обманщику в допуске, ответе или обслуживании.
Для безопасного использования интеллектуальных карт разработаны протоколы идентификации с нулевой передачей знаний. Секретный ключ владельца карты становится неотъемлемым признаком его личности. Доказательство
знания этого секретного ключа с нулевой передачей этого знания служит доказательством подлинности личности владельца карты.
7.1 Упрощенная схема идентификации с нулевой передачей знаний
Схему идентификации с нулевой передачей знаний предложили в 1986 г.
У.Фейге, А.Фиат и А.Шамир. Она является наиболее известным доказательством идентичности с нулевой передачей конфиденциальной информации.
Рассмотрим сначала упрощенный вариант схемы идентификации с нулевой
передачей знаний для более четкого выявления ее основной концепции. Прежде
всего, выбирают случайное значение модуля n, который является произведением двух больших простых чисел. Модуль n должен иметь длину 512…1024
бит. Это значение n может быть представлено группе пользователей, которым
придется доказывать свою подлинность. В процессе идентификации участвуют
две стороны:
 сторона А, доказывающая свою подлинность,
 сторона В, проверяющая представляемое стороной А доказательство.
45
Для того чтобы сгенерировать открытый и секретный ключи для стороны А,
доверенный арбитр (Центр) выбирает некоторое число V, которое является
квадратичным вычетом по модулю n. Иначе говоря, выбирается такое число V,
что сравнение
x2  V (mod n)
имеет решение и существует целое число
V –1 mod n.
Выбранное значение V является открытым ключом для А. Затем вычисляют наименьшее значение S, для которого
S  sqrt (V –1) (mod n).
Это значение S является секретным ключом для А.
Теперь можно приступить к выполнению протокола идентификации.
1. Сторона А выбирает некоторое случайное число r, r< n. Затем она вычисляет
x = r 2 mod n
и отправляет x стороне В.
2. Сторона В посылает А случайный бит b.
3. Если b=0, тогда А отправляет r стороне В. Если b=1, то А отправляет
стороне В
y = r  S mod n.
4. Если 1) b = 0, сторона В проверяет, что
1) x = r2 mod n,
чтобы убедиться, что А знает sqrt (x). Если 2) b=1, сторона В проверяет, что
2) x = y2 V mod n,
чтобы быть уверенной, что А знает sqrt (V –1).
Эти шаги образуют один цикл протокола, называемый аккредитацией. Стороны А и В повторяют этот цикл t раз при разных случайных значениях r и b
до тех пор, пока В не убедится, что А знает значение S.
Если сторона А не знает значения S, она может выбрать такое значение r,
которое позволит ей обмануть сторону В, если В отправит ей b=0, либо А
46
может выбрать такое r, которое позволит обмануть В, если В отправит ей
b=1. Но этого невозможно сделать в обоих случаях. Вероятность того, что А
обманет В в одном цикле, составляет 1/2. Вероятность обмануть В в t циклах
равна (1/2)t.
Для того чтобы этот протокол работал, сторона А никогда не должна повторно использовать значение r. Если А поступила бы таким образом, а сторона В отправила бы стороне А на шаге 2 другой случайный бит b, то В
имела бы оба ответа А. После этого В может вычислить значение S, и для А
все закончено.
7.2.Параллельная схема идентификации с нулевой передачей знаний
Параллельная схема идентификации позволяет увеличить число аккредитаций, выполняемых за один цикл, и тем самым уменьшить длительность процесса идентификации.
Как и в предыдущем случае, сначала генерируется число n как произведение двух больших чисел. Для того, чтобы сгенерировать открытый и секретный
ключи для стороны А, сначала выбирают К различных чисел V1, V2, ..., VК, где
каждое Vi является квадратичным вычетом по модулю n. Иначе говоря, выбирают значение Vi таким, что сравнение
x2  Vi mod n
имеет решение и существует Vi–1 mod n. Полученная строка V1, V2, ..., VК является открытым ключом.
Затем вычисляют такие наименьшие значения Si, что
Si = sqrt (Vi–1) mod n.
Эта строка S1, S2, ..., SK является секретным ключом стороны А.
Протокол процесса идентификации имеет следующий вид:
1. Сторона А выбирает некоторое случайное число r, r<n. Затем она вычисляет x=r2 mod n и посылает x стороне В.
2. Сторона В отправляет стороне А некоторую случайную двоичную строку
из K бит: b1, b2, ..., bK.
47
3. Сторона А вычисляет
y = r  (S1b1  S2b2  ...  SKbK) mod n.
Перемножаются только те значения Si, для которых bi=1. Например, если b1=1,
то сомножитель S1 входит в произведение, если же b1=0, то S1 не входит в
произведение, и т.д. Вычисленное значение y отправляется стороне В.
4. Сторона В проверяет, что
x = y2  (V1b1  V2b2  ...  VKbK) mod n.
Фактически сторона В перемножает только те значения Vi, для которых bi=1.
Стороны А и В повторяют этот протокол t раз, пока В не убедится, что А знает S1, S2, ..., SK.
Вероятность того, что А может обмануть В, равна (1/2)Кt. Авторы рекомендуют в качестве контрольного значения брать вероятность обмана В равной
(1/2)20 при К=5 и t=4.
Задача 7.1 Требуется рассмотреть работу параллельной схемы идентификации
с нулевой передачей знаний, если модуль п=35 (произведение двух простых
чисел 5 и 7).
Решение
Возможные квадратичные вычеты будут следующими:
1: x2 1 (mod 35)
имеет решения: x =1, 6, 29, 34;
4: x2  4 (mod 35)
имеет решения: x = 2, 12, 23, 33;
9: x2  9 (mod 35)
имеет решения: x = 3, 17, 18, 32;
11: x2 11 (mod 35)
имеет решения: x = 9, 16, 19, 26;
14: x2 14 (mod 35)
имеет решения: x = 7, 28;
15: x2 15 (mod 35)
имеет решения: x = 15, 20;
16: x2 16 (mod 35)
имеет решения: x = 4, 11, 24, 31;
21: x2  21 (mod 35)
имеет решения: x =14, 21;
25: x2  25 (mod 35)
имеет решения: x = 5, 30;
29: x2  29 (mod 35)
имеет решения: x = 8, 13, 22, 27;
48
30: x2  30 (mod 35)
имеет решения: x =10, 25.
Заметим, что 14, 15, 21, 25 и 30 не имеют обратных значений по модулю 35,
потому что они не являются взаимно простыми с 35. Следует также отметить,
что число квадратичных вычетов по модулю 35, взаимно простых с n = p  q =
5  7 = 35 (для которых НОД (x, 35) =1), равно
(p –1) (q –1)/4 = (5 –1) (7 –1)/4 = 6.
Составим таблицу квадратичных вычетов по модулю 35, обратных к ним
значений по модулю 35 и их квадратных корней.
Таблица 7.1
V
V –1
S = sqrt (V –1)
1
1
1
4
9
3
9
4
2
11
16
4
16
11
9
29
29
8
Итак, сторона А получает открытый ключ, состоящий из К=4 значений V:
[4, 11, 16, 29].
Соответствующий секретный ключ, состоящий из К=4 значений S:
[3 4 9 8].
Рассмотрим один цикл протокола.
1. Сторона А выбирает некоторое случайное число r=16, вычисляет
x =162 mod 35 =11
и посылает это значение x стороне В.
2. Сторона
В
отправляет стороне
А
некоторую случайную
двоич-
ную строку
[1, 1, 0, 1].
3. Сторона А вычисляет значение
y = r  ( S1b  S 2b ... S Kb ) mod n =16(31419081) mod35= 31
1
2
K
49
и отправляет это значение y стороне В.
4. Сторона В проверяет, что
x=y2 (V1b  V 2b ... VKb )mod n =312(41111160291) mod35 =11.
1
2
K
Стороны А и В повторяют этот протокол t раз, каждый раз с разным случайным числом r, пока сторона В не будет удовлетворена.
При малых значениях величин, как в данном примере, не достигается настоящей безопасности. Но если n представляет собой число длиной 512 бит и
более, сторона В не сможет узнать ничего о секретном ключе стороны А, кроме того факта, что сторона А знает этот ключ.
50
Приложение
Элементы теории чисел
Модулярная арифметика
Модулярная арифметика часто изучается в школе как "арифметика часов". Если отсчитать 14 часов от 3 часов после полудня, то получится 5 часов
утра следующего дня:
3 +14  5 (mod 12)
или
(3 +14) mod 12 = 5.
Это арифметика по модулю 12.
Обычная запись в модулярной арифметике
a  b (mod n) ,
читается так: "a сравнимо с b по модулю n". Это соотношение справедливо для
целых значений a,b и n  0, если, и только если
a=b+kn,
для некоторого целого k.
Отсюда, в частности, следует
n | (a – b) .
Это читается как "n делит (a – b )".
Если
a  b (mod n),
то b называют вычетом числа a по модулю n.
Операцию нахождения вычета числа a по модулю n
a (mod n) ,
называют приведением числа a по модулю n или приведением по модулю.
В нашем примере
(3 +14) mod 12 =17 mod 12 = 5 ,
51
или
17  5 (mod 12),
число 5 является вычетом числа 17 по модулю 12.
Набор целых чисел от 0 до (n –1) называют полным набором вычетов по
модулю n. Это означает, что для любого целого a (a > 0) его вычет r по модулю n есть некоторое целое число в интервале от 0 до (n –1), определяемое из
соотношения
r = a – k  n,
где k – целое число.
Например, для n =12 полный набор вычетов:
{0, 1, 2, …, 11}.
Обычно предпочитают использовать вычеты
r  {0, 1, 2, …, n –1},
но иногда полезны вычеты в диапазоне целых:
1
 1

r   (n  1),..., (n  1) .
2
2


Заметим, что
–12 (mod 7)  –5 (mod 7)  2 (mod 7)  9 (mod 7) и т.д.
Модулярная арифметика аналогична во многом обычной арифметике: она
коммутативна, ассоциативна и дистрибутивна. Точнее говоря, целые числа по
модулю n с использованием операций сложения и умножения образуют коммутативное кольцо при соблюдении законов ассоциативности, коммутативности и дистрибутивности.
Фактически мы можем либо сначала приводить по модулю n, а затем выполнять операции, либо сначала выполнять операции, а затем приводить по модулю n, поскольку приведение по модулю n является гомоморфным отображением из кольца целых в кольцо целых по модулю n:
(a + b) mod n = [a (mod n) + b (mod n)] mod n,
(a – b) mod n = [a (mod n) – b (mod n)] mod n,
52
(a  b) mod n = [a (mod n)  b (mod n)] mod n,
[a  (b + c)] mod n = {[a  b (mod n)] + [a  c (mod n)]} mod n.
Криптография использует множество вычислений по модулю n, потому
что задачи типа вычисления дискретных логарифмов и квадратных корней
очень трудны. Кроме того, с вычислениями по модулю удобнее работать, потому что они ограничивают диапазон всех промежуточных величин и результата.
Для модуля n длиной k бит промежуточные результаты любого сложения, вычитания или умножения будут не длиннее
2k бит. Поэтому возведение в степень в модулярной арифметике можно выполнить без генерации очень больших промежуточных результатов.
Вычисление степени числа a по модулю n
ax mod n ,
можно выполнить как ряд умножений и делений. Существуют способы сделать
это быстрее. Поскольку эти операции дистрибутивны, быстрее произвести возведение в степень как ряд последовательных умножений, выполняя каждый раз
приведение по модулю. Это особенно заметно, если работать с длинными числами (200 бит и более).
Например, если нужно вычислить
a8 mod n,
не следует применять примитивный подход с выполнением семи перемножений
и одного приведения по модулю громадного числа:
(a  a  a  a  a  a  a  a) mod n.
Вместо этого выполняют три малых умножения и три малых приведения по
модулю:
((a2 mod n)2 mod n)2 mod n.
Тем же способом вычисляют
a16 mod n = (((a2 mod n)2 mod n)2 mod n)2 mod n.
Вычисление
ax mod n,
53
где x не является степенью 2, лишь немного сложнее. Двоичная запись числа
x позволяет представить число x как сумму степеней 2:
x = 25(10)  1 1 0 0 1(2), поэтому 25 = 24 + 23 + 20.
Тогда
a25 mod n = (aa24) mod n = (aa8 a16) mod n =
= a  ((a2)2)2  (((a2)2)2)2 mod n = ((((a2  a)2)2)2  a) mod n.
При разумном накоплении промежуточных результатов потребуется только
шесть умножений:
(((((((a2 mod n)  a) mod n)2 mod n)2 mod n)2 mod n)  a) mod n.
Этот метод уменьшает трудоемкость вычислений до 1,5хk операций в среднем,
где k – длина числа в битах.
Поскольку многие алгоритмы шифрования основаны на возведении в
степень по модулю n, целесообразно использовать алгоритмы быстрого возведения в степень.
Вычисление обратных величин
В арифметике действительных чисел нетрудно вычислить мультипликативную обратную величину a–1 для ненулевого a:
a–1 =1/a или a  a–1 =1.
Например, мультипликативная обратная величина от числа 4 равна 1/4, поскольку
4  1 =1.
4
В модулярной арифметике вычисление обратной величины является более сложной задачей. Например, решение сравнения
4  x 1 (mod 7)
эквивалентно нахождению таких значений x и k, что
4  x  7  k +1,
где x и k – целые числа.
54
Общая формулировка этой задачи – нахождение такого целого числа x,
что
a  x (mod n) =1.
Можно также записать
a–1  x (mod n).
Решение этой задачи иногда существует, а иногда его нет. Например, обратная величина для числа 5 по модулю 14 равна 3, поскольку
5  3 =15  1 (mod 14).
С другой стороны, число 2 не имеет обратной величины по модулю 14.
Вообще сравнение
a–1  x (mod n)
имеет единственное решение, если a и n – взаимно простые числа.
Если числа a и n не являются взаимно простыми, тогда сравнение
a–1  x (mod n)
не имеет решения.
Сформулируем основные способы нахождения обратных величин. Пусть
целое число a  {0, 1, 2, …, n – 1}.
Если НОД (a, n) =1, то a  i (mod n) при i = 0, 1, 2, …, n –1 является перестановкой множества {0, 1, 2, …, n – 1}.
Например, если a = 3 и n = 7 (НОД (3,7) =1), то
3  i (mod 7)
при i = 0, 1, 2, …, 6
является последовательностью 0, 3, 6, 2, 5, 1, 4, т.е. перестановкой множества
{0, 1, 2, …, 6}.
Это становится неверным, когда НОД (a, n)  1. Например, если a = 2 и
n = 6, то 2  i (mod 6)  0, 2, 4, 0, 2, 4 при i = 0, 1, 2, …, 5.
Если НОД (a,n) =1, тогда существует обратное число a–1, 0 < a–1 < n, такое, что
a  a–1 1 (mod n).
55
Действительно, a  i (mod n) является перестановкой 0, 1, ..., n –1, поэтому существует i, такое, что
a  i 1 (mod n).
Как уже отмечалось, набор целых чисел от 0 до n –1 называют полным
набором вычетов по модулю n. Это означает, что для любого целого числа a (a
> 0) его вычет r = a (mod n) – это некоторое целое число в интервале от 0 до n
–1.
Выделим из полного набора вычетов подмножество вычетов, взаимно
простых с n. Такое подмножество называют приведенным набором вычетов.
Пример. Пусть модуль n =11 – простое число. Полный набор вычетов по
модулю 11
{0, 1, 2, …, 10}.
При формировании приведенного набора вычетов из них удаляется только один
элемент – 0. Приведенный набор вычетов по модулю 11 имеет 11 – 1 = 10
элементов.
Вообще приведенный набор вычетов по модулю простого числа n имеет
n –1 элементов.
Пример. Пусть модуль n =10. Полный набор вычетов по модулю n =10
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Из них только 1, 3, 7, 9 не имеют общего сомножителя с числом 10. Поэтому
приведенный набор вычетов по модулю 10 равен {1, 3, 7, 9}. При формировании этого приведенного набора были исключены элементы:
0
(1 элемент),
кратные 2
(4 элемента),
кратные 5
(1 элемент),
т.е. всего шесть элементов. Вычитая их из 10, получаем 10 – 1 – 4 – 1 = 4, т.е.
четыре элемента в приведенном наборе.
56
Для произведения простых чисел p  q = n приведенный набор вычетов
имеет (p –1)(q –1) элементов. При n=p  q=2  5=10 число элементов в приведенном наборе
(p – 1)(q – 1) = (2 – 1) (5 –1) = 4.
Пример. Приведенный набор вычетов по модулю 27=33 имеет 18 элементов:
{1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26}.
Из полного набора вычетов исключены элементы, кратные 3 (всего девять элементов).
Для модуля в виде простой степени nr приведенный набор вычетов имеет nr–1 (n –1) элементов.
При n = 3, r = 3 получаем 33–1 (3 –1) = 32  2 =18.
Функция Эйлера (n) характеризует число элементов в приведенном наборе вычетов (табл. П.1).
Таблица П.1
Модуль n
n – простое
Функция (n)
n –1
n (n –1)
n2
…
…
nr–1 (n – 1)
nr
57
p  q (p, q – проИначе говоря, функ-
…
стые)
…
ция (n) – это количество
положительных
t
piei1 (pi  1)
i1
 pi ei (pi – проt
целых,
меньших n, которые вза-
(p – 1) (q – 1)
i1
стые)
имно просты с n.
Малая теорема Ферма: если n– простое и НОД (a,n)=1, то
an–1 1 (mod n).
Согласно обобщению Эйлером малой теоремы Ферма имеем: если НОД
(a,n) =1, то
a(n) 1 (mod n).
Если n – простое число, то предыдущий результат, учитывая, что (n) = n –1,
приводится к виду (малой теоремы Ферма)
an–1 1 (mod n).
Основные способы нахождения обратных величин
a–1  1 (mod n).
1. Проверить поочередно значения 1, 2, ..., n – 1, пока не будет найден a–
1
1 (mod n), такой, что aa–1 (mod n)  1.
2. Если известна функция Эйлера (n), то можно вы-числить
a–1 (mod n)  a(n)–1 (mod n),
используя алгоритм быстрого возведения в степень.
3. Если функция Эйлера (n) не известна, можно использовать расширенный
алгоритм Евклида.
Проиллюстрируем эти способы на числовых примерах.
1. Поочередная проверка значений 1, 2, ..., n – 1, пока не будет найден x
= a–1 (mod n), такой что a  x  1 (mod n).
Пусть n = 7, a = 5. Требуется найти x = a–1 (mod n).
58
a  x  1 (mod n) или 5  x  1 (mod 7).
n – 1 = 7 – 1 = 6.
Получаем x = 5–1 (mod 7) = 3.
Результаты проверки сведены в табл. П.2.
Таблица П.2
x
5x
5  x (mod 7)
1
5
5
2
10
3
3
15
1
4
20
6
5
25
4
6
30
2
2. Нахождение a–1 (mod n), если известна функция Эйлера (n).
Пусть n = 7, a = 5. Найти x = a–1 (mod n) = 5–1 (mod 7). Модуль n = 7 – простое число. Поэтому функция Эйлера (n) = (7) = = n –1 = 6. Обратная величина от 5 по mod 7
a–1 (mod n) = a(n)–1 (mod n) =
= 56–1 mod 7 = 55 mod 7 = (52 mod 7)(53 mod 7) mod 7 =
= (25 mod 7)(125 mod 7) mod 7 = (4  6) mod 7 = 24 mod 7 = 3.
Итак, x = 5–1 (mod 7) = 3.
3. Нахождение обратной величины a–1 (mod n) с помощью расширенного
алгоритма Евклида.
Алгоритм Евклида можно обобщить способом, который имеет большое
практическое значение. При этом способе во время вычисления НОД (a,b) можно попутно вычислить такие целые числа u1 и u2, что
a  u1 + b  u2 = НОД (a,b).
59
Это обобщение (расширение) алгоритма Евклида удобно описать, используя векторные обозначения.
Квадратичные вычеты
Рассмотрим некоторое простое p > 2 и число a < p. Если число a сравнимо с квадратом некоторого числа x по модулю p, т.е. выполняется сравнение x2  a (mod p), тогда a называют квадратичным вычетом по модулю p. В
противном случае a называют квадратичным невычетом по модулю p.
Если a – квадратичный вычет, сравнение x2  a (mod p) имеет два решения: +x и –x, т.е. a имеет два квадратных корня по модулю p.
Все квадратичные вычеты находят возведением в квадрат элементов 1, 2,
3, ..., (p –1)/2.
Не все значения a < p являются квадратичными вычетами. Например,
при p = 7 квадратичные вычеты это 1, 2, 4:
12 = 1  (mod 7),
22 = 4  4 (mod 7),
32 = 9  2 (mod 7),
42 =16  2 (mod 7),
52 = 25  4 (mod 7),
62 = 36 1 (mod 7).
Заметим, что каждый квадратичный вычет появляется в этом списке дважды. Не существует никаких значений x, которые удовлетворяли бы любому
из следующих уравнений:
x2  3 (mod 7),
x2  5 (mod 7),
x2  6 (mod 7).
60
Числа 3, 5 и 6 – квадратичные невычеты по модулю 7. Можно доказать,
что существует точно (p –1)/2 квадратичных вычетов по модулю p и (p –1)/2
квадратичных невычетов по модулю p.
Если a – квадратичный вычет по модулю p, то a имеет точно два квадратных корня: один корень между 0 и (p –1)/2, другой корень между (p –1)/2 и
(p –1).
Один из этих квадратных корней также является квадратичным вычетом
по модулю p; он называется главным квадратным корнем.
Вычиcление квадратных корней при p=7 представлено в табл. П.4.
Таблица П.4
Корни
x  a (mod 7)
2
x1
x2
12  1(mod 7)
+1
–1 = –1 + 7 = 6
22  4(mod 7)
+2
–2 = –2 + 7 = 5
32  2(mod 7)
+3
–3 = –3 + 7 = 4
Если n – произведение двух простых p и q, т.е. n = p  q, то существуют точно
(p –1)(q –1)/4
квадратичных вычетов по модулю n, взаимно простых с n. Например, по модулю 35 (p = 5, q = 7, n = 5  7 = 35) существуют
(5  7)(7  1) 4  6

4
4
=6
квадратичных вычетов: 1, 4, 9, 11, 16, 29, взаимно простых с 35.
61
Документ
Категория
Без категории
Просмотров
6
Размер файла
928 Кб
Теги
krizhanovskii, bezop, kireevu, pugin, sredstv, setyam, obespech, inform, peredahi, dannih
1/--страниц
Пожаловаться на содержимое документа