неверно что требованием к безопасности асимметричной системы является

Асимметричные криптосистемы шифрования

У. Диффи и М. Хеллман сформулировали требования, выполнение которых обеспечивает безопасность асимметричной криптосистемы.
1. Вычисление пары ключей (К_в, к_в) получателем В должно быть простым.
2. Отправитель А, зная открытый ключ К_в и сообщение М, может легко вычислить криптограмму С=Е_Кв(М).
3. Получатель В, используя секретный ключ к_в и криптограмму С, может легко восстановить исходное сообщение М=О_кя(С).
4. Противник, зная открытый ключ К_в, при попытке вычислить секретный ключ к_в наталкивается на непреодолимую вычислительную проблему.
5. Противник, зная пару (К_в, С), при попытке вычислить исходное сообщение М наталкивается на непреодолимую вычислительную проблему.

Концепция асимметричных криптографических систем с открытым ключом основана на применении однонаправленных функций. Однонаправленной функцией называется функция F(X), обладающая двумя свойствами:
• существует алгоритм вычисления значений функции Y= F(X);
• не существует эффективного алгоритма обращения (инвертирования) функции F (т. е. не существует решения уравнения F(X) = Y относительно X).

В качестве примера однонаправленной функции можно указать целочисленное умножение. Прямая задача — вычисление произведения двух очень больших целых чисел Р и Q, т. е. нахождение значения N = P × Q — относительно несложная задача для компьютера.

Обратная задача — факторизация, или разложение на множители большого целого числа, т. е. нахождение делителей Р и Q большого целого числа N = Р × Q, — является практически неразрешимой при достаточно больших значениях N.

Другой характерный пример однонаправленной функции — это модульная экспонента с фиксированными основанием и модулем.

Как и в случае симметричных криптографических систем, с помощью асимметричных криптосистем обеспечивается не только конфиденциальность, но также подлинность и целостность передаваемой информации. Подлинность и целостность любого сообщения обеспечивается формированием цифровой подписи этого сообщения и отправкой в зашифрованном виде сообщения вместе с цифровой подписью. Проверка соответствия подписи полученному сообщению после его предварительного расшифровывания представляет собой проверку целостности и подлинности принятого сообщения. Процедуры формирования и проверки электронной цифровой подписи рассмотрены в разделе «Электронная цифровая подпись и функция хэширования».

Преимущества асимметричных криптографических систем перед симметричными криптосистемами:
• в асимметричных криптосистемах решена сложная проблема распределения ключей между пользователями, так как каждый пользователь может сгенерировать свою пару ключей сам, а открытые ключи пользователей могут свободно публиковаться и распространяться по сетевым коммуникациям;
• исчезает квадратичная зависимость числа ключей от числа пользователей; в асимметричной криптосистеме число используемых ключей связано с числом абонентов линейной зависимостью (в системе из N пользователей используются 2N ключей), а не квадратичной, как в симметричных системах;
• асимметричные криптосистемы позволяют реализовать протоколы взаимодействия сторон, которые не доверяют друг другу, поскольку при использовании асимметричных криптосистем закрытый ключ должен быть известен только его владельцу.

Недостатки асимметричных криптосистем:

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

Эта статья была опубликована Вторник, 11 августа, 2009 at 16:23 в рубрике Принципы криптографической защиты информации. Вы можете следить за ответами через RSS 2.0 feed.

Источник

Асимметричное шифрование

Асимметричное шифрование — это метод шифрования данных, предполагающий использование двух ключей — открытого и закрытого. Открытый (публичный) ключ применяется для шифрования информации и может передаваться по незащищенным каналам. Закрытый (приватный) ключ применяется для расшифровки данных, зашифрованных открытым ключом. Открытый и закрытый ключи — это очень большие числа, связанные друг с другом определенной функцией, но так, что, зная одно, крайне сложно вычислить второе.

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

Принцип действия асимметричного шифрования

Схема передачи данных между двумя субъектами (А и Б) с использованием открытого ключа выглядит следующим образом:

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

Применение асимметричных алгоритмов

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

Например, стандарты SSL и TLS используют асимметричный алгоритм на стадии установки соединения (рукопожатия): с его помощью кодируют и передают ключ от симметричного шифра, которым и пользуются в ходе дальнейшей передачи данных.

Также асимметричные алгоритмы применяются для создания электронных подписей для подтверждения авторства и (или) целостности данных. При этом подпись генерируется с помощью закрытого ключа, а проверяется с помощью открытого.

Асимметричные алгоритмы

Наиболее распространенные алгоритмы асимметричного шифрования:

Надежность асимметричного шифрования

Теоретически приватный ключ от асимметричного шифра можно вычислить, зная публичный ключ и механизм, лежащий в основе алгоритма шифрования (последнее — открытая информация). Надежными считаются шифры, для которых это нецелесообразно с практической точки зрения. Так, на взлом шифра, выполненного с помощью алгоритма RSA с ключом длиной 768 бит на компьютере с одноядерным процессором AMD Opteron с частотой 2,2 ГГц, бывшем в ходу в середине 2000-х, ушло бы 2000 лет.

При этом фактическая надежность шифрования зависит в основном от длины ключа и сложности решения задачи, лежащей в основе алгоритма шифрования, для существующих технологий. Поскольку производительность вычислительных машин постоянно растет, длину ключей необходимо время от времени увеличивать. Так, в 1977-м (год публикации алгоритма RSA) невозможной с практической точки зрения считалась расшифровка сообщения, закодированного с помощью ключа длиной 426 бит, а сейчас для шифрования этим методом используются ключи от 1024 до 4096 бит, причем первые уже переходят в категорию ненадежных.

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

Публикации на схожие темы

Сквозное шифрование: что это и зачем оно нужно вам

Квантовые компьютеры и криптография для чайников

Квантовые компьютеры — для «чайников»

Эволюция шифровальщика JSWorm

Программы-вымогатели: пара хороших новостей

Дорога к «интернету вещей»: преимущества и риски смарт-езды

Источник

Асимметричное шифрование на практике

Приветствую вас, хабравчане!

Проблемы безопасности — это слабое место большинства из нас. Всем нам неприятно сталкиваться и тем более терять что—то ценное из—за случайного клика мышью. И именно поэтому я решила поделиться найденными материалами с вами.

В стремлении развеять наиболее часто задаваемый вопрос — почему будут атаковать меня? Кому я нужен? — мы начнем статью именно с него.

Нужно учитывать, что атаковать вас может не только человек. Это может делать, например, бот.
Каждый из нас подключен к интернет провайдеру. А на него, скорее всего, происходят атаки буквально каждый день. Замечали у себя на почте раздел «спам»? В каждом таком письме потенциально есть фишинговая атака. Это атака не персонально на вас. Это масштабная атака, ориентированная на широкий круг лиц. Мы потенциально жертвы.

Чаще всего их цель — деньги. Как они могут их получить?

Например, использовать ваш компьютер в качестве web сервера, красть ваш контент, производить email атаки, деятельность в ботнете, кража аккаунтов, атаки с целью вымогательства. Да и email аккаунт — потенциально важная вещь, потому что все мы достаточно часто используем один и тот же пароль на нескольких сервисах.

Время дорого, и мы хотим тратить как можно меньше времени на вопросы, связанные с безопасностью.

И поэтому первое, что нужно сделать — это ответить для себя на несколько вопросов:

Окей, мы определились с тем, что нам необходимо защитить. Следующий шаг — выбор метода защиты.

Да, разумеется, в мире существует множество атак и защититься от всех просто невозможно.
Поэтому мы рассмотрим один из наиболее эффективных инструментов — шифрование.

Что такое шифрование?

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

Шифрование — это метод преобразования данных, пригодных для чтения человеком, в форму, которую человек не сможет прочитать. За счет этого данные остаются конфиденциальными и приватными.

Дешифрование — обратная операция. Преобразование нечитаемых данных в читаемые.

Окей, где это применяется? На самом деле во многих местах. Например, обращали внимание на протокол «https»? Именно за счет него ваши данные не может перехватить 3-й человек во время вашего лазания в интернете. Объясню подробнее. Вы заходите на сайт «www.google.com», делаете любой запрос. При этом все данные, которые необходимы для отображения выдачи результатов, передаются с помощью протокола «https». А значит, если какой-либо человек решит просмотреть данные о вашем трафике (атака Man In the Middle), то он увидит лишь то, что вы зашли на Google. В придачу он получит множество зашифрованных пакетов. То есть можно сказать, что он не получит ничего.

Но вернемся к базовой теории. В процессе шифрования участвуют 2 основных компонента — алгоритм и ключ.

Алгоритм — это в каком-то смысле замок, который позволяет хранить ваши данные в тайне. За счет него происходит преобразование текста.

Ключ — это, уж простите за тавтологию, ключ от замка. Кусочек уникальных данных, с помощью которых происходит преобразование текста

Хм, хорошо. Едем дальше. Слегка повысим напряжение.

Виды шифрования

Как еще мы можем использовать шифрование в своих, корыстных целях? Для простоты понимания мы рассмотрим шифрование архива. При архивации во многих архиваторах присутствует возможность установить пароль. При этом архиватор использует какой-либо алгоритм для шифрования. И чаще всего это симметричный алгоритм.

Симметричное шифрование

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

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

Например, при смещении в 5 символов, символ, который стоит на первой позиции заменить на символ 6 позиции и так далее.

Наиболее стойким на данный момент считается алгоритм AES (Advanced Encryption Standard).
Стоит упомянуть еще один момент — мощность пароля. Мощность пароля измеряется в битах. Одним из наиболее распространенных решений является 128 или 256 бит. Это то количество бит, которое будет выделено для пароля. Так же это число означает количество паролей, которое вы можете получить при данном алгоритме шифрования. Но чем больше длина ключа, тем медленнее протекает процесс шифрования или дешифрования.

Но чаще всего используется асимметричное шифрование

И так, мы зашифровали письмо, но как его отправить нашему другу? Отправлять в соц. сетях или текстовым сообщением — не самая лучшая затея. Как и говорить его по телефону.

И это приводит нас к новому типу шифрования.

В ассиметричном шифровании используется 2 ключа — открытый и закрытый(тайный).
Открытый ключ для шифрования, закрытый — для дешифрования.

Какие алгоритмы позволяют пользоваться этой технологией?

Так как во мне есть жилка программиста, а также любовь к математике, то я просто не могу не рассказать о том, как все работает «под капотом»

Рассмотрим на примере алгоритма RSA.

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

1) Мы выбираем два простых числа. Желательно, чтобы они были достаточно близкими

2) Вычисляем их произведение, а также функцию Эйлера

n = p * s
f = (p — 1) * (s — 1)

3) Теперь наиболее затратная по времени часть — выбор экспоненты и произвольного коэффициента.

Дело в том, что при выбранных коэффициентах значение «d» должно быть целым. «d» — необходимая составляющая алгоритма

e = 5
k = 9
d = (k * f + 1)/e

Теперь наш открытый ключ (для шифрования сообщения) состоит из значений переменных «e» и «n», а закрытый ключ (для дешифрования) из значений «d» и «n».
То есть в нашем случае…

Тогда шифрование сообщения происходит по формуле: crypt = m^e%n.
А дешифрование: decrypt = crypt^d%n.

Ну и с точки зрения программиста, мы можем использовать эту информацию следующим образом:

Теперь, зная теорию, плюсы и минусы алгоритма, а также для чего вообще нужно им пользоваться, мы можем говорить о практическом применении.

Среди всех найденных программ, наиболее удобной мне показалась gpg4usb.

Данная программа использует PGP шифрование. Почему я рекомендую использовать именно его?

Все просто. Этот тип шифрования до сих пор еще не удалось взломать. Никому. Так что пользуйтесь.

Пользоваться программой достаточно просто. Нужно лишь знать куда нажимать.
И именно об этом сейчас пойдет речь.

Первое, что необходимо сделать — скачать программу. Вы можете это сделать по ссылке:
ссылка.

Скажу сразу — эта программа кросс—платформенная. То есть вы можете использовать ее как на Windows, так и на Linux.

Второе — это создание пары ключей шифрования.

Это можно сделать, выполнив следующую последовательность действий:

1) Переходим в раздел «Менеджер ключей»

2) Выбираем в верхней панели «Ключ», затем «Генерировать ключ»

Должно выглядеть примерно так:

3) Заполняем необходимые поля. Предупрежу сразу — пароль лучше куда-нибудь записать (или запомнить), потому что он понадобится в последующем для дешифрования сообщения.

Теперь ключ создан, и мы можем приступать непосредственно к шифрованию.

На главном экране присутствует текстовое поле — это наш плацдарм для создания сообщений. В правой боковой панели помечаем галочкой свой ключ.

Введя сообщение в поле, смело нажимаем в верхней панели «Зашифровать».

Поздравляю, вы умеете шифровать сообщения.

Дешифровка происходит аналогично, разве что вместо «Зашифровать» вы пользуетесь кнопкой «Расшифровать».

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

Как оказалось, все достаточно просто. В окне, в котором мы создавали ключи для шифрования, мы помечаем галочкой нужный ключ и в верхней панели выбираем «Экспорт в файл». Мы получили открытый ключ и можем передавать кому угодно, чтобы получать от него зашифрованные сообщения, которые можем прочитать только мы.

Так, а теперь я хочу получить закрытый ключ (а вдруг буду работать с другого компьютера? Ведь ключи хранятся локально).

Чтобы решить эту задачу, мы вновь возвращаемся на главный экран, в правой боковой панели нажимаем правой кнопкой мыши на нужный ключ и выбираем «Показать свойства ключа». А в открывшемся окне выбираем «Экспортировать Секретный ключ».

Готово, теперь у вас «на руках» открытый и закрытый ключи шифрования, которыми вы можете распоряжаться по своему усмотрению.

Ну и в завершении статьи хочу поделиться полезной методикой: моделирование угроз и оценка рисков.

Первое, что нужно понять — нельзя обеспечить 100% безопасность, как и свести все риски к нулю. Нельзя получить 100% анонимность. Нельзя получить 100% безопасность (разве что не использовать телефон и ПК).

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

Мы должны использовать риск—ориентированный подход.

Риск = уязвимость * угрозы * последствия

Например, кража ноутбука. Что мы можем сделать? Зашифровать весь диск, добавить дополнительные этапы авторизации.

Для обеспечения качественной защиты нужно пройти несколько этапов:

Источник

Математические методы защиты информации. 2021 (ответы на тест) [СИНЕРГИЯ]

Описание работы

2. Алгоритмы формирования и проверки электронной цифровой подписи

3. В асимметричной криптосистеме RSA

4. В асимметричной системе шифрования для независимой работы N абонентов требуется …

5. В поточных шифрах в один момент времени процедура шифрования производится над

7. В симметричной системе шифрования для независимой работы N абонентов требуется …

8. В системе открытого распределения ключей Диффи-Хеллмана используется

9. В совершенном (идеальном) шифре апостериорные вероятности открытых текстов (вычисленные после получения криптограммы)

10. В шифре простой замены каждому символу исходного сообщения соответствует

11. Важнейшим компонентом шифра является

14. Достоинством асимметричных систем шифрования (по сравнению с симметричными системами) является

15. Зашифрованное сообщение должно поддаваться чтению

17. Знание противником алгоритма шифрования

18. Идеальная безопасность обеспечивается, когда длина ключа

19. Имитовставка предназначена для проверки

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

21. Код аутентификации сообщения обеспечивает..

22. Максимальное количество раундов шифрования по стандарту ГОСТ 28147-89 составляет..

23. Мерой имитостойкости шифра является вероятность успешного

25. Моделирование процедуры дешифрования предусматривает

26. Моделирование процедуры расшифрования предусматривает

27. Надежность алгоритма RSA основывается

28. Наиболее надежной считается оценка практической стойкости шифра, если количество символов ключа

29. Неверно, что активная атака, проводимая противником, предусматривает

30. Неверно, что к достоинствам поточных систем относится

34. Неверно, что при искусственном формировании речевого сигнала используется такая его характеристика, как

35. Неверно., что к достоинствам блочных систем относятся

37. Недостатком асимметричных систем шифрования является

количество ключей, требуемых для работы в сети

38. Одноразовое шифрование наиболее приемлемо для обработки

39. Одноразовый блокнот проверку целостности сообщения

41. Основой для формирования алгоритмов симметричного шифрования является предположение, что …

42. Открытый и закрытый ключи в асимметричной системе

43. Параметр q отечественного стандарта цифровой подписи ГОСТ Р 34.10-94 имеет размерность

44. Пассивная атака, проводимая противником, связана с

47. Под шифром обычно понимается

49. Подмена шифрованного сообщения предусматривает.

50. Практическая реализация алгоритма Диффи-Хеллмана

51. При зашифровании по стандарту шифрования ГОСТ 28147-89 полное рассеивание входных данных происходит после

52. При моделировании активных действий противника, его обычно ставят

53. При проведении словарной атаки

54. При проверке цифровой подписи используется

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

56. При скремблировании речевого сигнала изменяются

57. При формировании цифровой подписи используется

58. Противник, производя подмену или имитацию сообщения исходит из предположения, что

59. Протокол Диффи-Хеллмана

60. Протокол Диффи-Хеллмана является протоколом

61. Рабочая характеристика шифра

62. Результатом генерации исходной информации при предварительном распределении ключей является

63. Ренегатство – это

64. С увеличением полосы пропускания канала возможность голосовой идентификации

65. Содержание имитовставки должно зависеть

66. Спектром сигнала называется эквивалентный сигналу.

67. Средняя продолжительность взрывного звука составляет

68. Средняя продолжительность фрикативного звука составляет

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

72. Электронная цифровая подпись – это

73. Элемент одноразового блокнота представляет из себя

Источник

9 Асимметричные криптосистемы

4.1. Концепция криптосистемы с открытым ключом

Эффективными системами криптографической защиты данных являются асимметричные криптосистемы, называемые также криптосистемами с открытым ключом. В таких системах для зашифрования данных используется один ключ, а для расшифрования – другой ключ (отсюда и название – асимметричные). Первый ключ является открытым и может быть опубликован для использования всеми пользователями системы, которые зашифровывают данные. Расшифрование данных с помощью открытого ключа невозможно.

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

Обобщенная схема асимметричной криптосистемы с открытым ключом показана на рис. 4.1. В этой криптосистеме применяют два различных ключа: К_в – открытый ключ отправителя А; k_в – секретный ключ получателя В. Генератор ключей целесообразно располагать на стороне получателя В (чтобы не пересылать секретный ключ k_в по незащищенному каналу). Значения ключей К_в и k_в зависят от начального состояния генератора ключей.

Раскрытие секретного ключа k_в по известному открытому ключу К_в должно быть вычислительно неразрешимой задачей.

Характерные особенности асимметричных криптосистем:

1. Открытый ключ К_в и криптограмма С могут быть отправлены по незащищенным каналам, т.е. противнику известны К_в и С.

2. Алгоритмы шифрования и расшифрования

Рекомендуемые файлы

Рисунок 4.1 – Обобщенная схема асимметричной криптосистемы с открытым ключом

Защита информации в асимметричной криптосистеме основана на секретности ключа k_в.

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

1. Вычисление пары ключей (К_в, k_в) получателем В на основе начального условия должно быть простым.

2. Отправитель А, зная открытый ключ К_в и сообщение М, может легко вычислить криптограмму

С = (М) = Е_в (М). (4.1)

3. Получатель В, используя секретный ключ k_в и криптограмму С, может легко восстановить исходное сообщение

М = (С) = D_в(С) = D_в [Е_в(М)]. (4.2)

4. Противник, зная открытый ключ К_в, при попытке вычислить секретный ключ k_в наталкивается на непреодолимую вычислительную проблему.

5. Противник, зная пару (К_в, С), при попытке вычислить исходное сообщение М наталкивается на непреодолимую вычислительную проблему [28].

4.2. Однонаправленные функции

Концепция асимметричных криптографических систем с открытым ключом основана на применении однонаправленных функций. Неформально однонаправленную функцию можно определить следующим образом. Пусть X и Y – некоторые произвольные множества. Функция

является однонаправленной, если для всех xÎX можно легко вычислить функцию

И в то же время для большинства yÎY достаточно сложно получить значение xÎX, такое, что f (x)=y (при этом полагают, что существует по крайней мере одно такое значение x).

Основным критерием отнесения функции f к классу однонаправленных функций является отсутствие эффективных алгоритмов обратного преобразования Y ® X.

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

является относительно несложной задачей для ЭВМ.

Обратная задача – разложение на множители большого целого числа, т.е. нахождение делителей P и Q большого целого числа N = P*Q, является практически неразрешимой задачей при достаточно больших значениях N. По современным оценкам теории чисел при целом N»2 664 и P»Q для разложения числа N потребуется около 10 23 операций, т.е. задача практически неразрешима на современных ЭВМ.

Следующий характерный пример однонаправленной функции – это модульная экспонента с фиксированными основанием и модулем. Пусть A и N – целые числа, такие, что 1£ А x (mod N), (4.4)

где X – целое число, 1£ x £ N –1.

Существуют эффективные алгоритмы, позволяющие достаточно быстро вычислить значения функции f_A,N (x).

Поэтому задачу обращения функции f_A,N(x) называют задачей нахождения дискретного логарифма или задачей дискретного логарифмирования.

Задача дискретного логарифмирования формулируется следующим образом. Для известных целых A, N, Y найти целое число X, такое, что

Алгоритм вычисления дискретного логарифма за приемлемое время пока не найден. Поэтому модульная экспонента считается однонаправленной функцией.

По современным оценкам теории чисел при целых числах A » 2 664 и N » 2 664 решение задачи дискретного логарифмирования (нахождение показателя степени x для известного y) потребует около 10 26 операций, т.е. эта задача имеет в 10 3 раз большую вычислительную сложность, чем задача разложения на множители. При увеличении длины чисел разница в оценках сложности задач возрастает.

Следует отметить, что пока не удалось доказать, что не существует эффективного алгоритма вычисления дискретного логарифма за приемлемое время. Исходя из этого, модульная экспонента отнесена к однонаправленным функциям условно, что, однако, не мешает с успехом применять ее на практике.

Вторым важным классом функций, используемых при построении криптосистем с открытым ключом, являются так называемые однонаправленные функции с «потайным ходом» (с лазейкой). Дадим неформальное определение такой функции. Функция

относится к классу однонаправленных функций с «потайным ходом» в том случае, если она является однонаправленной и, кроме того, возможно эффективное вычисление обратной функции, если известен «потайной ход» (секретное число, строка или другая информация, ассоциирующаяся с данной функцией).

В качестве примера однонаправленной функции с «потайным ходом» можно указать используемую в криптосистеме RSA модульную экспоненту с фиксированными модулем и показателем степени. Переменное основание модульной экспоненты используется для указания числового значения сообщения M либо криптограммы C

4.3. Криптосистема шифрования данных RSA

Алгоритм RSA предложили в 1978 г. три автора: Р.Райвест (Rivest), А.Шамир (Shamir) и А.Адлеман (Adleman). Алгоритм получил свое название по первым буквам фамилий его авторов. Алгоритм RSA стал первым полноценным алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.

Надежность алгоритма основывается на трудности факторизации больших чисел и трудности вычисления дискретных логарифмов.

В криптосистеме RSA открытый ключ К_в, секретный ключ k_в, сообщение М и криптограмма С принадлежат множеству це-лых чисел

Здесь P и Q – случайные большие простые числа. Для обеспечения максимальной безопасности выбирают P и Q равной длины и хранят в секрете.

Множество Z_N с операциями сложения и умножения по модулю N образует арифметику по модулю N.

Открытый ключ К_в выбирают случайным образом так, чтобы выполнялись условия:

Это можно осуществить, так как получатель В знает пару простых чисел (P,Q) и может легко найти j (N). Заметим, что k_в и N должны быть взаимно простыми.

Открытый ключ К_в используют для шифрования данных, а секретный ключ k_в – для расшифрования.

Преобразование шифрования определяет криптограмму С через пару (открытый ключ К_в, сообщение М) в соответствии со следующей формулой:

C = (M) = E_В (M) = (mod N). (4.10)

В качестве алгоритма быстрого вычисления значения C используют ряд последовательных возведений в квадрат целого M и умножений на M с приведением по модулю N.

Однако обратную задачу, т.е. задачу расшифрования криптограммы С, можно решить, используя пару (секретный ключ k_в, криптограмма С) по следующей формуле:

М = (С) = D_В (C) = (mod N). (4.11)

Процесс расшифрования можно записать так:

Подставляя в (4.12) значения (4.10) и (4.11), получаем:

= М (mod N)

= M (mod N). (4.13)

Величина j (N) играет важную роль в теореме Эйлера, которая утверждает, что если НОД (x, N) =1, то

или в несколько более общей форме

x n × j ( N )+1 º x (mod N). (4.14)

Сопоставляя выражения (4.13) и (4.14), получаем

или, что то же самое,

Именно поэтому для вычисления секретного ключа k_в используют соотношение (4.9).

Таким образом, если криптограмму

C = (mod N)

возвести в степень k_в, то в результате восстанавливается исходный открытый текст М, так как

= = M n × j ( N )+1 º M (mod N).

Таким образом, получатель В, который создает криптосистему, защищает два параметра: 1) секретный ключ k_в и 2) пару чисел (P,Q), произведение которых дает значение модуля N. С другой стороны, получатель В открывает значение модуля N и открытый ключ К_в.

Противнику известны лишь значения К_в и N. Если бы он смог разложить число N на множители P и Q, то он узнал бы «потайной ход» – тройку чиселв>, вычислил значение функции Эйлера

и определил значение секретного ключа k_в.

Однако, как уже отмечалось, разложение очень большого N на множители вычислительно не осуществимо (при условии, что длины выбранных P и Q составляют не менее 100 десятичных знаков).

4.3.1. Процедуры шифрования и расшифрования в

Предположим, что пользователь А хочет передать пользователю В сообщение в зашифрованном виде, используя криптосистему RSA. В таком случае пользователь А выступает в роли отправителя сообщения, а пользователь В – в роли получателя. Как отмечалось выше, криптосистему RSA должен сформировать получатель сообщения, т.е. пользователь В. Рассмотрим последовательность действий пользователя В и пользователя А.

1. Пользователь В выбирает два произвольных больших простых числа P и Q.

2. Пользователь В вычисляет значение модуля N = P * Q.

3. Пользователь В вычисляет функцию Эйлера

и выбирает случайным образом значение открытого ключа К_в с учетом выполнения условий:

5. Пользователь В пересылает пользователю А пару чисел (N, К_в) по незащищенному каналу.

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

6. Пользователь А разбивает исходный открытый текст М на блоки, каждый из которых может быть представлен в ви-де числа

7. Пользователь А шифрует текст, представленный в виде последовательности чисел М_i по формуле

C_i = (mod N)

и отправляет криптограмму

8. Пользователь В расшифровывает принятую криптограмму

используя секретный ключ k_в, по формуле

М_i = (mod N).

В результате будет получена последовательность чисел М_i, которые представляют собой исходное сообщение М. Чтобы алгоритм RSA имел практическую ценность, необходимо иметь возможность без существенных затрат генерировать большие простые числа, уметь оперативно вычислять значения ключей К_в и k_в.

4.3.2. Безопасность и быстродействие криптосистемы

Безопасность алгоритма RSA базируется на трудности решения задачи факторизации больших чисел, являющихся произведениями двух больших простых чисел. Действительно, криптостойкость алгоритма RSA определяется тем, что после формирования секретного ключа k_в и открытого ключа К_в «стираются» значения простых чисел Р и Q, и тогда исключительно трудно определить секретный ключ k_в по открытому ключу К_в, поскольку для этого необходимо решить задачу нахождения делителей Р и Q модуля N.

Разложение величины N на простые множители Р и Q позволяет вычислить функцию j (N) = (P –1)(Q –1) и затем определить секретное значение k_в, используя уравнение

Другим возможным способом криптоанализа алгоритма RSA является непосредственное вычисление или подбор значения функции

j (N) = (P –1)(Q –1). Если установлено значение j (n), то сомножители P и Q вычисляются достаточно просто. В самом деле, пусть

y = (P – Q) 2 = (Р + Q) 2 – 4*N.

Зная j (N), можно определить x и затем y; зная x и y, можно определить числа Р и Q из следующих соотношений:

P = 1/2 (x +), Q = 1/2 (x –).

Однако эта атака не проще задачи факторизации модуля N [28].

Задача факторизации является трудно разрешимой задачей для больших значений модуля N.

Сначала авторы алгоритма RSA предлагали для вычисления модуля N выбирать простые числа P и Q случайным образом, по 50 десятичных разрядов каждое. Считалось, что такие большие числа N очень трудно разложить на простые множители. Один из авторов алгоритма RSA, P. Pайвест, полагал, что разложение на простые множители числа из почти 130 десятичных цифр, приведенного в их публикации, потребует более 40 квадриллионов лет машинного времени. Однако этот прогноз не оправдался из-за сравнительно быстрого прогресса компьютеров и их вычислительной мощности, а также улучшения алгоритмов факторизации.

Ряд алгоритмов факторизации приведен в [45]. Один из наиболее быстрых алгоритмов, известных в настоящее время, алгоритм NFS (Number Field Sieve) может выполнить факторизацию большого числа N (с числом десятичных разрядов больше 120) за число шагов, оцениваемых величиной

.

В 1994 г. было факторизовано число со 129 десятичными цифрами. Это удалось осуществить математикам А.Ленстра и М.Манасси посредством организации распределенных вычислений на 1600 компьютерах, объединенных сетью, в течение восьми месяцев. По мнению А.Ленстра и М.Манасси, их работа компрометирует криптосистемы RSA и создает большую угрозу их дальнейшим применениям. Теперь разработчикам криптоалгоритмов с открытым ключом на базе RSA приходится избегать применения чисел длиной менее 200 десятичных разрядов. Самые последние публикации предлагают применять для этого числа длиной не менее 250 – 300 десятичных разрядов.

Была сделана попытка расчета оценок безопасных длин ключей асимметричных криптосистем на ближайшие 20 лет исходя из прогноза развития компьютеров и их вычислительной мощности, а также возможного совершенствования алгоритмов факторизации. Эти оценки (табл.4.1.) даны для трех групп пользователей (индивидуальных пользователей, корпораций и государственных организаций), в соответствии с различием требований к их информационной безопасности. Конечно, данные оценки следует рассматривать как сугубо приблизительные, как возможную тенденцию изменений безопасных длин ключей асимметричных криптосистем со временем.

Источник