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

Текст из файла (страница 4)

Вопрос 12

Схема Диффи — Хеллмана

Авторами исторически первой системы с открытым ключом являются Whitfield Diffie и Martin E. Hellman. Цель описанного ниже протокола — создание секретного значения k, известного обоим участникам, но не известного стороннему наблюдателю. Такое значение k может быть использовано в качестве сеансового ключа для криптосистемы с секретным ключом.

Протокол Диффи — Хеллмана для создания общего секретного значения.

Параметры системы: р — простое число, g — образующий элемент Z_p* Все вычисления будут делаться в Z_p. Можно также рассматривать варианты этой схемы для любой группы, в которой трудно вычислять дискретный логарифм.

Ключи: для каждого использования протокола А выбирает случайно закрытый ключ (фактически достаточно ), а В — закрытый ключ (фактически достаточно ).

Выбор параметров криптосистемы. Чтобы усложнить вычисление дискретного логарифма в Z_p*, выберем простое р равным 2q+1, где q — простое число. В этом случае количество образующих элементов Z_p* равно  (р-1)=q-1 и их можно искать подбором, проверяя условия g²1 и g^q1.

Чтобы определить значение k, не зная закрытых ключей, нужно уметь вычислять g^xy пo g^x и g^y или, что то же самое, находить а^х по a и g^x. Умение вычислять дискретный логарифм дает нам решение этой задачи. Эквивалентность вычисления дискретного логарифма и определения k доказана только для частных случаев, например если все простые делители числа (р -1) малы.

Открытое распределение секретных ключей

Схема Диффи — Хеллмана не является криптосистемой в смысле см. вопрос 6. Она представляет собой схему открытого распределения секретных ключей. Асимметричные криптосистемы также могут использоваться для открытого распределения секретных ключей, при этом участник А выбирает секретный ключ и передает его участнику В в виде k_B(k), где k_в — открытый ключ участника В. [1]

Вопрос 13

Криптосистема RSA

Конструкция

Через НОД(a₁,…,a_k) будем обозначать наименьшее общее кратное a₁,...,a_k .

Теорема. Пусть n=p₁ ,...,p_k , р_i — различные простые числа. Положим М=НОД( р₁ -1,..., p_k -1 ), с 1 (modM). Тогда для любого x Z_n верно х^с  х (modn).

Доказательство. Рассмотрим разложение х| (х₁ ,...,х_k) из Китайской теоремы. Тогда либо х_i=0, либо  1(modp_i) по Малой теореме Ферма. В любом случае 1(mod p_i), и вследствие однозначности разложения получаем утверждение теоремы.

Схема RSA (Ronald Rivest, AdiShamir, Leonard M. Adleman, 1978)

Параметры системы

Пусть n=pq, где р и q — большие простые числа, состоящие каждое из (log₂ n)/2 битов, М=НОД(р-1,q-1),

е —простое число. de (modM).

Ключи

• Закрытый ключ (n,d,p,q),

• Открытый ключ (п,е).

Пусть т  Z_n — сообщение.

Шифрование открытым ключом с = т^е mod n.

Дешифрование закрытым ключом m = c^d mod n.

С помощью Китайской теоремы можно сэкономить — вычислить

а затем найти

где uq1(mod p). Значение и можно вычислить заранее и рассматривать в качестве компоненты закрытого ключа.

Атаки на RSA

Если известно разложение числа п на множители, то закрытый показатель степени d вычисляется по открытому ключу (n,е) и, следовательно, становится возможным вычислить сообщение т по шифрограмме с. Известно, что если существует эффективный алгоритм нахождения d по е при заданном модуле п, то можно найти (n) и разложить n на множители. До сих пор неизвестно, эквивалентна ли задача вычисления т по с задаче факторизации n.

Шифрование по RSA скрывает не всю информацию относительно сообщения т, например сохраняется значение символа Якоби:

Для сокрытия всей информации о сообщении следует выбирать длину сообщения меньше |n| (количества битов в n) и дополнять сообщение до |n| битов случайными битами.

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

• Если одно сообщение т зашифровано е различными ключами с общим открытым показателем степени е и модулями соответственно п₁,...,п_е. Пусть c_i=m^emodn,, i=l,...,e. По построению, скорее всего, п₁,...,п_е взаимно просты. Положим N= п₁,...,п_е и с помощью Китайской теоремы найдем c Z_N такое, что с modn_i=c_i для всех i. Поскольку m^e<N, c=m^e и значение т можно найти путем извлечения корня в Z.

В работе [85] это рассуждение обобщено на случай шифрования различными ключами линейно зависимых сообщений.

• Пусть два сообщения т₁ и m₂ из Z_n таких, что m₂=am₁+b, а и b —
  известные константы, зашифрованы с помощью одного и того же ключа c открытым показателем е=3: с_i=m_i³ mod n, i=1,2. Тогда

В работе [86] этот результат обобщается на случай нескольких сообщений, связанных полиномиальным соотношением более высокой степени.

Вывод: для повышения надежности шифрования открытый показатель степени е должен иметь тот же порядок величины, что и модуль n.

Утверждение. Схема RSA неустойчива к атакам с выбором шифрограммы.

Доказательство. Предположим, что имеется некто, выполняющий операцию дешифрования RSA, но отказывающийся расшифровывать некоторые «значимые» сообщения. Пусть «значимое» сообщение т зашифровано, c=m^emodn. Предложим для расшифровки замаскированное сообщение с' =х^ес mod п, х Z_n^* . Получим результат расшифровки

т' = с' ^d modn = x^edc^d modn = хт modn

и найдем т = х^-1т' modn. [1]

Вопрос 14

Аутентификация

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

Рассмотрим эти вопросы более подробно.

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

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

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

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

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

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

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

Цифровая подпись

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

Характеристики

Список файлов ответов (шпаргалок)