Содержание
- 2. В асимметричных криптосистемах используются два ключа: один открытый ключ, а другой – секретный. 1)Если открытый ключ
- 3. 1 Системы с открытым ключом В этих системах используются некоторые аналитические преобразования и два различных, но
- 4. Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 3
- 5. Методы аналитических преобразований: Умножение простых чисел (RSA) Задача об укладке рюкзака (метод Меркле-Хеллмана) Дискретное возведение в
- 6. В основе асимметрических систем лежит понятие специальных односторонних функций. Функция — правило, по которому связывают (отображают)
- 7. Односторонняя функция не может быть непосредственно использована в качестве криптосистемы, т.к. законный получатель не сможет расшифровать.
- 8. Метод возведения в степень (метод Эль-Гамаля) Y= x m mod n – прямое преобразование. Эффективного алгоритма
- 9. Метод укладки рюкзака (метод Меркле-Хеллмана) Реализацией задачи об укладке рюкзака является криптоалгоритм Меркле-Хеллмана. Пусть задан набор
- 10. Метод RSA Самым популярным из асимметричных является метод RSA, основанный на операциях с большими (скажем, 100-значными)
- 11. В 1977 году три исследователя из Массачусетсского технологического института (MIT) разработали алгоритм для реализации метода криптографии
- 12. Исследователи в примере своей первой публикации зашифровали фразу из драмы «Юлий Цезарь» В. Шекспира «ITS ALL
- 13. Этапы реализации алгоритма RSA: Получатель выбирает два очень больших простых числа P и Q и вычисляет
- 14. Криптографические методы и средства для защиты информации: Асимметричные криптографические системы . Пример: 13
- 16. Скачать презентацию
В асимметричных криптосистемах используются два ключа: один открытый ключ, а другой
В асимметричных криптосистемах используются два ключа: один открытый ключ, а другой
1)Если открытый ключ используется для шифрования, а секретный ключ – для расшифрования, то такие криптосистемы называются криптосистемами с открытым ключом.
C = Eko( P ), P = Dkc( C ) = Dkc(Eko( P ))
2)Если секретный ключ используется для шифрования, а открытый ключ – для расшифрования, то имеет место система электронной подписи (ЭП). Владелец секретного ключа может зашифровать (подписать) текст, а проверить правильность подписи (расшифровать) может любой пользователь, имеющий в своем распоряжении открытый ключ.
C = Ekc( P ), P = Dko( C ) = Dko(Ekc( P ))
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 1
1 Системы с открытым ключом
В этих системах используются некоторые аналитические преобразования
1 Системы с открытым ключом
В этих системах используются некоторые аналитические преобразования
Методы шифрования должны обладать двумя свойствами:
законный получатель сможет выполнить обратное преобразование и расшифровать сообщение
злоумышленник или криптоаналитик противника, перехвативший сообщение, не сможет восстановить по нему открытый текст без таких затрат времени и средств, которые сделают эту работу нецелесообразной.
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 2
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 3
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 3
Методы аналитических преобразований:
Умножение простых чисел (RSA)
Задача об укладке рюкзака (метод Меркле-Хеллмана)
Дискретное
Умножение простых чисел (RSA)
Задача об укладке рюкзака (метод Меркле-Хеллмана)
Дискретное
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 4
В основе асимметрических систем лежит понятие специальных односторонних функций.
Функция — правило,
В основе асимметрических систем лежит понятие специальных односторонних функций.
Функция — правило,
Обратимая функция — функция, которая связывает каждый элемент в диапазоне с точно одним элементом в домене.
Односторонняя функция (OWF — One Way Function) — функция, которая обладает следующими двумя свойствами:
f вычисляется просто. Другими словами, при данном x может быть легко вычислен y = f (x).
f -1 вычисляется трудно.
Другими словами, при данном y, вычисление
x= f ~1 (y) неосуществимо.
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 5
Односторонняя функция не может быть непосредственно использована в качестве криптосистемы, т.к.
Односторонняя функция не может быть непосредственно использована в качестве криптосистемы, т.к.
Она должна иметь «потайную лазейку», т.е. должен существовать эффективный способ ее вычисления в обоих направлениях. При этом знание прямого преобразования не позволит легко найти обратное преобразование.
"Лазейка" в односторонней функции
"Лазейка" в односторонней функции (TOWF — Trapdoor One Way) — односторонняя функция с третьим свойством:
При данном y и ловушке (секретной) x может быть легко вычислен.
Вычисление ключей осуществляется получателем сообщения, который оставляет у себя ключ для расшифрования - секретный, открытый ключ он высылает отправителю сообщений любым доступным способом или публикует, не опасаясь огласки.
Особенность этих методов заключается в том, что функции шифрования и расшифрования являются обратимыми только тогда, когда они обеспечиваются строго определенной парой ключей. При этом открытый ключ определяет конкретную реализацию функции «ловушки», а секретный ключ дает информацию о «ловушке».
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 6
Метод возведения в степень (метод Эль-Гамаля)
Y= x m mod n –
Метод возведения в степень (метод Эль-Гамаля)
Y= x m mod n –
Эффективного алгоритма для обратной операции – извлечения корня m-ой степени по модулю n для произвольных m и n не найдено. Это проблема дискретного логарифмирования для больших чисел.
Один из методов использует алгоритм извлечения корня при известном разложении числа n на простые множители, это и позволяет отнести функцию F(x) к классу односторонних функций с «потайной лазейкой».
Число Y является открытым ключом Число Y открыто передается или публикуется.
Число m является секретным ключом.
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 7
Метод укладки рюкзака (метод Меркле-Хеллмана)
Реализацией задачи об укладке рюкзака является криптоалгоритм
Метод укладки рюкзака (метод Меркле-Хеллмана)
Реализацией задачи об укладке рюкзака является криптоалгоритм
Пусть задан набор целых положительных чисел А=(а1,а2…аn) и известна некоторая величина Z. Задачей является нахождение таких чисел аi , если это возможно, сумма которых равна числу Z.
В простейшем случае это число Z указывает размер рюкзака , а каждое из чисел аi – размер предмета, который нужно уложить в рюкзак. Задачей является нахождение такого набора предметов, чтобы рюкзак был полностью заполнен.
Пример: Z=3231 и набор из 10 чисел
А=(43, 129, 215, 473, 903,302, 561, 1165,697, 1523)
Заметим, что число Z получится при сложении только некоторых чисел аi.
В принципе решение может быть найдено полным перебором подмножеств А и проверкой , какая из ∑ аi равна числу Z. В нашем примере этот перебор состоит из 210 комбинаций, включая пустое множество.
Решение Z= 3231= 129 + 473 +909 + 561 + 1165.
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 8
Метод RSA
Самым популярным из асимметричных является метод RSA, основанный на операциях
Метод RSA
Самым популярным из асимметричных является метод RSA, основанный на операциях
В 1976 году преподаватели Стэнфордского университета, Витфильд Диффи (Whitfield DifFie) и Мартин Хелман (Martin Heliman), предложили систему под названием "шифрование с применением открытого ключа". Этот метод предполагает наличие двух ключей при каждом сеансе кодирования и хорошо отрекомендовал себя даже в незащищенных сетях. Каждый пользователь создает два ключа. Каждый ключ представляет собой произвольный набор цифр объемом в некоторых случаях более чем в 500 цифр. Оба ключа связаны между собой таким образом, что сообщение можно зашифровать с помощью одного ключа и расшифровать с помощью другого, однако расшифровать сообщение с помощью ключа, использовавшегося для его зашифровки, нельзя.
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 9
В 1977 году три исследователя из Массачусетсского технологического института (MIT) разработали
В 1977 году три исследователя из Массачусетсского технологического института (MIT) разработали
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 10
Исследователи в примере своей первой публикации зашифровали фразу из драмы «Юлий
Исследователи в примере своей первой публикации зашифровали фразу из драмы «Юлий
Xe mod m, где m – 129-разрядное целое число, e=9007.
Шифротекст и числа e и m были опубликованы.
Конечно, многие математики пытались найти способ раскрыть алгоритм криптосистемы с открытым ключом с помощью вычислений (часто весьма объемных), однако пока что никому не удалось найти решение этой математической проблемы. Декодирующие программы используют метод "грубой силы", проверяя все возможные комбинации. Теоретически такой подход позволяет добиться успеха, однако необходимый объем вычислений делает такой вариант нереальным при условии, конечно, что открытый ключ имеет достаточную длину.
Лишь в 1994 году через 17 лет фраза была расшифрована, для этого потребовалось 220 дней, были задействованы 600 человек и 1600 компьютеров, соединенных через Интернет.
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 11
Этапы реализации алгоритма RSA:
Получатель выбирает два очень больших простых числа P
Этапы реализации алгоритма RSA:
Получатель выбирает два очень больших простых числа P
Затем выбирается случайное число E, взаимно простое с M и вычисляется D, удовлетворяющее условию (E x D = 1) mod M
Получатель публикует E и N, как свой открытый ключ, сохраняя D, как секретный ключ.
Отправитель сообщение X представляет в виде набора блоков
xi = (x1, x2, ……xl), 0 < xi < M, затем шифрует его с использованием E и N.
Каждое xi возвести в степень E по модулю N, получится шифрованное сообщение:
(x1 E mod N), (x2 E mod N),……. (x1 E mod N)
Для расшифрования полученного сообщения Получатель, используя свой секретный ключ D, вычисляет для каждого блока
(xi ED mod N), т.к. (ExD = 1) mod M, то утверждается xi ED mod N = xi
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы 12
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы .
Криптографические методы и средства для защиты информации: Асимметричные криптографические системы .