.RU
Карта сайта

Математические основы формирования шумоподобных сигналов. Понятие случайных сигналов - 3


^ 16. Математические основы компьютерной криптографии. Алгоритм Евклида. Полиномиальные дроби. (криптосистема без передачи ключей)


Основу данного метода криптографии составляют теоремы Эйлера и Ферма, а также алгоритмы решения сравнений первой степени, базирующиеся, в свою очередь, на алгоритме Евклида.
Сущность алгоритма Евклида состоит в отыскании нод(a,b) и заключается в следующем. Пусть и положительные целые числа и . Тогда для указанных значений будут справедливы соотношения:




Алгоритм заканчивается при получении некоторого остатка Наибольшим общим делителем тогда будет последний не равный нулю остаток .
525
231b
Алгоритм Евклида можно представить также в виде следующих арифметических действий:
2
462
(525, 231)=21.
63
231
3
189
42
63
1
42
21
42
q4=2 n=4
42
(2.2)
0
В теории существует математическая связь данного алгоритма и представления частного от деления двух чисел в виде полиномиальных дробей:
(2.3)
Из данных равенств следует: (2.4)

Обычно эти вычисления представляют в виде таблицы:

^ 17. Математические основы компьютерной криптографии.Свойства сравнений.


Сравнения обладают рядом свойств, характерных для обыкновенных равенств:
а) если два числа сравнимы с третьим, то все три числа сравнимы между собой по заданному модулю;
б) сравнения можно почленно складывать:
(2.7)
тогда: (2.8)
в) слагаемое, стоящее в какой либо части сравнения, можно переносить в другую часть, переменив знак на противоположный:
(2.9)
Например:
г) к каждой части сравнения можно прибавить любое число, кратное модулю:
; (2.10)
д) сравнения можно почленно перемножать:
(2.11)
е) следствие из (2.11): (2.12)
ж) если выражения для многочленов А и В сравнимы по модулю , то есть: (2.13)
то сравнимы и сами многочлены А и В по модулю : (2.14) Данное свойство является обобщением предыдущих свойств сложения и умножения;
з) обе части сравнения и модуль можно умножить на одно и тоже число:
(2.15)

^ 18. Математические основы компьютерной криптографии. Теорема Эйлера.


Решение сравнений первой степени с одним неизвестным.


Теорема Эйлера

: пусть числа и взаимно простые, то есть , тогда будет справедливо равенство: (2.16)
где - это функция Эйлера, которая показывает число чисел взаимно простых с с учетом 1. Считается, что 1 же обладает взаимной простотой с .

Например:

, так как в ряду 1,2,3,4,5 только два числа 1 и 5 считаются взаимно простыми с числом 6. Соответственно: (2.17)
Приведенные две теоремы (имеется ввиду эта теорема и теорема Ферма из следущего вопроса. Примечание DoctorClo ) в задачах криптографии применяются для решения сравнений, корни которых используются для выбора секретных ключей.
Пусть требуется решить сравнение первой степени с одним неизвестным:
. (2.19)
Принцип решения сравнения (2.19) основывается на разложении отношения в непрерывную (полиномиальную) дробь. Согласно свойствам непрерывных дробей можно записать: . (2.20)
Тогда, рассматривая две последние подходящие дроби, имеем:
(2.21)
Отсюда следует, что: (2.22)
Итак, для решения сравнения (2.19) необходимо определить только числитель подходящей дроби согласно алгоритму Евклида и подставить его в решение (2.22).

^ 19. Математические основы компьютерной криптографии. Теорема Ферма.


Решение сравнений первой степени с одним неизвестным.


Теорема Ферма:

если -простое число, а число не делится на , то есть , то имеет место сравнение вида : (2.18)
где .

Например:


Приведенные две теоремы (имеется ввиду эта теорема и теорема Элера из прошлого вопроса. Примечание DoctorClo ) в задачах криптографии применяются для решения сравнений, корни которых используются для выбора секретных ключей.
Пусть требуется решить сравнение первой степени с одним неизвестным:
. (2.19)
Принцип решения сравнения (2.19) основывается на разложении отношения в непрерывную (полиномиальную) дробь. Согласно свойствам непрерывных дробей можно записать: . (2.20)
Тогда, рассматривая две последние подходящие дроби, имеем:
(2.21)
Отсюда следует, что: (2.22)
Итак, для решения сравнения (2.19) необходимо определить только числитель подходящей дроби согласно алгоритму Евклида и подставить его в решение (2.22).

^ 20. Математические основы компьютерной криптографии. Криптосистема без передачи ключей.


Основу данного метода криптографии составляют теоремы Эйлера и Ферма, а также алгоритмы решения сравнений первой степени, базирующиеся, в свою очередь, на алгоритме Евклида.
Сущность алгоритма Евклида состоит в отыскании нод(a,b) и заключается в следующем. Пусть и положительные целые числа и . Тогда для указанных значений будут справедливы соотношения:


(2.1)

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

^ Теорема Эйлера

: пусть числа и взаимно простые, то есть , тогда будет справедливо равенство: (2.16)
где - это функция Эйлера, которая показывает число чисел взаимно простых с с учетом 1. Считается, что 1 же обладает взаимной простотой с .

Например:

, так как в ряду 1,2,3,4,5 только два числа 1 и 5 считаются взаимно простыми с числом 6. Соответственно: (2.17)

Теорема Ферма:

если -простое число, а число не делится на , то есть , то имеет место сравнение вида: (2.18)
где .

Например:


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

^ 21. Математические основы компьютерной криптографии. Криптосистема с открытым ключом (RSA).


Данный метод не является самостоятельным, так как базируется на предыдущем алгоритме. ^ RSARivest, Shamir, Adleman.
Пусть абоненты А и В хотят наладить между собой секретный обмен данными с открытым ключом. С этой целью каждый из них, независимо друг от друга, выбирает два больших простых числа и и находит их произведение равное и соответственно. После этого определяется функция Эйлера от этих чисел:
и . (2.38)
Для шифрования сообщений абоненты выбирают свои случайные числа (открытые ключи) из условия: (2.39)

Значения и , а также и носят открытый характер и размещаются в Интернете на заранее оговоренных сайтах.
Далее каждый из абонентов находит свой секретный ключ из сравнений:
и , (2.40)
где а - секретные ключи, известные только самим пользователям.
При необходимости посылки информации от абонента А к абоненту В текст разделяется на блоки длиной . После чего каждый блок кодируется в соответствии с правилом: (2.41) и передается в сеть.
Абонент В расшифровывает это сообщение, используя свой секретный ключ : . (2.42)
Учитывая, что: (2.43)
имеем равенство , так как (2.40).
Отличительной особенностью данного алгоритма по отношению к криптосистеме без передачи ключей является наличие своих модулей и для передачи информации у каждого пользователя сети.
Другая особенность метода состоит в использовании больших простых чисел и для формирования произведения и , что дает возможность выбирать ключи и в широком диапазоне значений и, следовательно, существенно затруднить процесс расшифровывания.

^ 22. Электронная криптографическая подпись.


Криптосистемы c открытым ключом обладают существенным недостатком, а именно: получатель шифрованных данных не имеет информации об отправителе, если абонентов-источников несколько. Этого недостатка лишена шифросистема с электронной криптографической подписью. Сущность данного метода шифрования заключается в следующем.
Пусть имеется сеть передачи информации вида рис. 2.1.
Для организации секретной связи каждый из абонентов Аi и банк данных независимо друг от друга выбирают по два достаточно больших простых числа. Пусть и простые числа банка, а - простые числа абонентов . Для
всех значений определяются числа , , как произведения:
(2.44)
При этом должно выполняться неравенство
На следующем этапе все участники связи выбирают случайные числа из условия:
(2.45)
после чего в Интернете размещается таблица открытых ключей
(2.46)
которая доступна всем желающим.
Далее, банк и каждый из абонентов Аi находят свои секретные ключи и из условий:
Теперь, пусть абонент ^ А1 хочет передать информацию абоненту B, причем будем считать, что в данном случае выполняется неравенство кроме того считаем, что и . Абонент А1 шифрует сообщение своим первым секретным ключом, а потом открытым ключом банка (i=1):
(2.48)
Абонент B, получив шифрованное сообщение , расшифровывает его, пользуясь сначала своим секретным ключом : (2.49)
а потом открытым ключом абонента :
Математическое доказательство тождеств (2.48)-(2.49) следует из ряда соотношений. Так как: . (2.51)
При имеем: . (2.52)
Следовательно: . Учитывая же что а также окончательно имеем:
Из сравнений при имеем: . (2.53)
Опять же, при а также окончательно имеем: Причем, если полученное сообщение принадлежит смысловым конструкциям используемого языка, то считается, что сообщение прислано абонентом .

^ 23. Шифросистема Эль-Гамаля.


Основу данного способа криптографии составляет малая теорема Ферма, которая используется следующим образом.
Очевидно, что любое сообщение может быть представлено в виде:
. (2.58)
Введем обозначения в сравнении (2.58) в соответствии с равенствами: . (2.59) Тогда: . (2.60) Теперь, полагая, что создаем систему открытых и секретных ключей: открытый ключ - (2.61) секретный ключ - . В данном случае необходимо, чтобы секретный ключ был известен как абоненту-источнику, так и приемнику информации. При этом правило обмена данными будет заключаться в выполнении следующих действий.
Абонент-источник выбирает сообщение , кодирует его в соответствии с соотношением: (2.62)
и предает его в канал связи.
Абонент-приемник принимает слово и, используя множитель , расшифровывает его в соответствии со сравнением: . (2.63)
Шифросистема Эль-Гамаля обретает криптографическую стойкость, если для каждого слова выбирается свой секретный ключ , который кодировано, передается с шифротекстом . Однако длина текста при шифровании в такой системе удваивается, что является существенным недостатком с точки зрения обнаружения самого канала связи.

^ 24. Цифровая криптографическая подпись Эль-Гамаля.


Цифровая подпись Эль-Гамаля используется для передачи сообщения от абонента-источника к абоненту-приемнику, а также установления подлинности источника пославшего сообщение.
Пусть - простое число и , тогда, выбрав в качестве полусекретного ключа значение , вычислим (2.64)
и разместим в Интернете набор вида .
Подпись для сообщения зашифровывается по следующему правилу.
Абонент-источник выбирает случайное целое число являющееся, по сути, переменным секретным ключом и определяются параметры: (2.65) Параметры являются пересы- лаемой информацией, содержащей подтверждение или подпись для сообщения .
Абонент-приемник, зная полуоткрытый ключ абонента-источника выполняет следующие действия. Во-первых, получает произведение
, (2.66)
а из сравнения (2.66) цифровую подпись вида: . (2.67)
Во-вторых, зная и открытое значение легко устанавливает идентичность присланного сообщения и подписи (2.67)
Схема цифровой подписи Эль-Гамаля послужила образцом для построения большого семейства во многом сходных по своим свойствам алгоритмов формирования подписей. В их основе лежит проверка сравнения вида: , (2.68)
в котором тройка A,B,C определяется некоторым набором параметров при некотором выборе знаков.
Например, исходная схема Эль-Гамаля получается при , и . При этом получаем: . (2.69)
Подставляя в (2.69) значения , имеем сравнение:
. (2.70)
При , из (2.70) следует тождество:
(2.71)
Таким образом, (2.69) достоверно и .
На базе схем подписи из этого семейства построены стандарты цифровой криптоподписи США (DSSDigital Signature Standard) и России, что подтверждает эффективность метода на соответствующем классе задач.
2014-07-19 18:44
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • Контрольная работа
  • © sanaalar.ru
    Образовательные документы для студентов.