Элементы дискретной математики

Алгоритм цифровой подписи DSA

Алгоритм цифровой подписи DSA (Digital Signature Algorithm) был предложен в 1991 году Национальным институтом стандартов и технологии США (National Institute of Standards and Technology − NIST) и стал стандартом США в 1993 году. Алгоритм DSA является развитием алгоритмов цифровой подписи Эль Гамаля и К Шнорра. Ниже приводятся процедуры генерации ключей, генерации подписи и проверки подписи в алгоритме DSA.

Генерация ключей DSA

Отправитель и получатель электронного документа используют при вычислениях большие целые числа; g и p - простые числа, длиной L битов каждое (512 ≤ L ≤ 1024); q − простое число длиной 160 бит (делитель числа (р-1). Числа g, р, q являются открытыми и могут быть общими для всех пользователей сети.

Отправитель выбирает случайное целое число х, 1 <х< q. Число x является секретным ключом отправителя для формирования электронной цифровой подписи.

Затем отправитель вычисляет значение

у = g^x mod р.

Число у является открытым ключом для проверки подписи отправителя. Число y передается всем получателям документов.

Генерация подписи DSA

Этот алгоритм предусматривает использование односторонней функции хэширо­вания h(.). В стандарте определен алгоритм безопасного хэширования SНА-1. Для того чтобы подписать сообщение М, участник A выполняет следующие шаги:

1. Выбирает случайное целое k в интервале [1, q - 1].

2. Вычисляет r =(g^x mod р) mod q.

3. Вычисляет k^-1 mod q.

4. Вычисляет s = k^-1{h(M)+xr } mod q, где h есть алгоритм хэширования SНА-1.

5. Если s=0 тогда перейти к шагу 1. (Если s=0, тогда s^-1 mod q не существует; (s требуется на шаге 2 процедуры проверки подписи.)

6. Подпись для сообщения М есть пара целых чисел (r, s).

Проверка подписи DSA

Для того, чтобы проверить подпись (r, s) сообщения М от участника А, участник В делает следующие шаги:

1. Получает подлинную копию открытого ключа у участника А.

2. Вычисляет w= s^-1 mod q и хэш-значение h(М).

3. Вычисляет значения u₁=h(M) w mod q и u₂=(rw) mod.

4. Используя открытый ключ у, вычисляет значение

v=(g^u1y^u2 mod p) mod q.

5. Признает подпись (r, s) под документом М подлинной, если v = r.

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

Алгоритмы ЭЦП:

· Стандарт цифровой подписи ГОСТ Р34.10-94;

· Алгоритм цифровой подписи ECDSA;

· Отечественный стандарт цифровой подписи ГОСТ Р34.10-2001.

Содержание

Введение. 3

ЛОГИЧЕСКИЕ (БУЛЕВЫ) ФУНКЦИИ.. 4

1. Основные логические функции. 4

2. Свойства конъюнкции, дизъюнкции и отрицания. 8

3. ДНФ, СДНФ, КНФ, СКНФ.. 10

4. Представление логических функций в виде СДНФ (СКНФ) 12

5. Нахождение сокращенной ДНФ по таблице истинности (карты Карно) 13

6. Суперпозиция функций. Замыкание набора функций.Замкнутые классы функций. Полные наборы. Базисы.. 15

7. Некоторые приложения теории булевых функций. 18

7.1. Функциональные элементы и схемы.. 18

7.2. Решение логических задач с помощью теории булевых функци й. 20

ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ.. 21

8. Общие понятия теории графов. 21

9. Эйлеровы и полуэйлеровы графы.. 23

10. Матрицы и графы. Нахождение путей и сечений с помощью структурной матрицы.. 27

11. Раскраска графа. 28

12. Деревья и их простейшие свойства. 31

13. Решение типовых задач. 31

14. Задачи соответствующие вариантам.. 36

ЛИТЕРАТУРА.. 41

Введение

Для успешного выполнения контрольной работы студент должен самостоятельно изучить соответствующий теоретический материал и ознакомиться с решением типовых примеров, приведенных в настоящем издании. Контрольная работа по дискретной математике составлена так, что если студент выполняет ее САМОСТОЯТЕЛЬНО, то подготовка его к зачету займет очень небольшое время. Заметим также, что задачи по дискретной математике НЕ ТРЕБУЮТ предварительных дополнительных знаний и, как нам кажется, любой здравомыслящий человек, претендующий на получение высшего технического образования, должен суметь выполнить эту работу (и это не должно занять у него много времени). Кроме того, современная жизнь абсолютно немыслима без компьютеров, а в основе ЛЮБОГО вычислительного устройства лежат знания именно дискретной математики, (которая является наукой 20-го века, и без ее развития были бы немыслимы успехи технического прогресса). Поэтому освоение ЭЛЕМЕНТАРНЫХ знаний в области дискретной математики расширит кругозор студента, позволит ему в какой-то степени понимать работу вычислительных устройств и лучше ориентироваться в современном мире. Заметим также, что в классический курс дискретной математики входят также такие разделы, как кодирование (необходимое для безошибочной передачи информации на расстояние, именно с помощью кодирования работают Интернет и электронная почта) и теория алгоритмов (в данном издании отсутствуют). Контрольная работа составлена по двум темам: “Булевы функции” и “Элементы теории графов”. Последняя тема важна тем, что сеть связи (телефонной) обычно изображается и изучается как сетевой граф.

Каждый студент выполняет контрольную работу по одному из десяти вариантов в соответствии с начальной буквой своей фамилии. Работа выполняется в 12-ти листовой тетради.

Начальные буквы фамилий студентов	Варианты контрольных работ
А, Б, Я
В, Г, Ч,
Е, Ж, З, И
К, Л, Ц,
М, Ю, О
П, Р, Щ
С, Т
Н, Х,
У,Ф,
Ш, Д

Каждому варианту соответствуют следующие задачи:

Вариант	Выполняемые задачи

Дата добавления: 2015-05-09