Хэлп!!! Задание по криптографии

криптоZ,

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

Выполняем следующий протокол:
1. Анна вычисляет K' = K (XOR) R и отправляет его Борису.
2. Борис вычисляет K = K' (XOR) R...
3. Что дальше? Пересылка по открытому каналу K в качестве подтверждения раскроет K, что, как я понимаю, в наши планы не входит. Пересылка R также раскроет K, если злоумышленник на канале связи вёл запись протокола.

Усилить схему можно следующим образом:
1. Вводим в схему R1 — дополнительную строку битов фиксированной длины.
2. R удлиняем на число бит R1, т.е. R длина должна быть равна конкатенации K и R1.

Выполняем протокол:
1. Анна вычисляет K' = ( K + R1 ) (XOR) R, где знак '+' означает конкатенацию элементов. Затем отправляет K' Борису.
2. Борис вычисляет ( K + R1 ) = K' (XOR) R.
3. Борис, зная длину ключа K или длину строки R1, отделяет эту строку от K и отправляет её по открытому каналу Анне.
4. Анна сверяет R1 с той, что отправлялась на первом этапе протокола. Если R1 совпадает, значит протокол завершён успешно. При этом злоумышленник не будет знать ни R, ни K, использовавшихся в ходе протокола, при условии, что строка R представляет собой последовательность истинно случайных битов. Кроме того, как и в любом случае применения алгоритма Вернама, строка R (одноразовый блокнот) может быть использована лишь единожды и должна уничтожаться по окончании выполнения протокола.

Вопрос второй. Просто возьми любое хорошее описание DES и загляни в раздел преобразований ключа. Вот описание Шнайера из "Прикладной криптографии" (перевод Семьянова, издательство Триумф, 2003 г., стр. 311):

Первоначально 64-битовый ключ DES сокращается до 56-битового ключа отбрасыванием каждого восьмого бита. Эти биты используются только для контроля чётности... После извлечения 56-битового ключа, для каждого из 16 раундов DES генерируется новый 48-битовый подключ. Эти подключи, Ki, определяются следующим образом.

Во-первых, 56-битовый ключ делится на две 28-битовых половины. Затем эти половины циклически сдвигаются налево на одил или два бита, в зависимости от раунда...

После сдвига выбираются 48 из 56 битов. Поскольку при этом не только выбирается подмножество битов, но и изменяется их порядок, данная операция называется сжимающей перестановкой. В её результате появляется набор из 48 битов. Сжимающая перестановка (называемая также перестановочной выборкой) определена в таблице... Например, бит сдвинутого ключа в позицию 33 перемещается в позицию 35 результат, а 18-й бит сдвинутого ключа отбрасывается.

Благодаря сдвигу, в каждом подключе используется отличное от других подмножество битов ключа. Каждый бит используется приблизительно в 14 из 16 подключей, хотя не все биты используются в точности одинаковое число раз.

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

КриптоZ, кого, простите, не советуете? Шнайера? Всё там отлично прописано. :) Дело привычки, наверное...

Удач всяческих!

ну вот...сказала про сайт – и народ начал просить ещё "посмотреть " задачку...вот – если кто увидит, узнает, решит:
"Рассмотрим проблему использования алгоритма шифрования для создания
односторонней функции хэширования. Испольуем алгоритм RSA с известным
ключем. Выполним обработку сообщения, складывающегося из
последовательноти блоков, по следующей схеме: шифруется первый блок с
помощью операции XOR результат объединяется со вторым блоком и
шифруется снова и т.д. Докажите что этоа схема недостаточно защищена,
решив следующие задачу. Пусть имеется двухблоковое собщение B1, B2 и
его хэш код RSAH(B1, B2) = RSA(RSA(B1) сложение по модулю
два(хэширование) B2)
Для произвольного данного блока С1 найдите такой С2, чтобы выполнить
равенство RSAH(С1, С2) = RSAH(B1, B2)."

Из текста задачи не совсем ясно, что нам дано по условию. Буду исходить из следующего (поправьте меня, если ошибаюсь; как-то очень просто всё получается).

Имеем:
k — ключевая пара (открытый и закрытый ключ) для вычисления имитовставки.
RSA H (B1, B2) — хэш-значение первого сообщения.
C1 — блок второго сообщения.
Найти:
Такой C2, чтобы RSA H (С1, С2) = RSA H (B1, B2).

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

1. Вычисляем ( B2 (XOR) RSA (B1) ) = RSA Dk ( B2 (XOR) RSA (B1) ). Теперь мы знаем XOR второго блока с шифртекстом первого. Предположим, это битовая последовательность "011010111110010011".
2. Не зная значения одного из блоков (B1 или B2), мы не сможем получить ни один из них. Но этого нам и не надо. Мы зашифровываем C1, вычисляя RSA Ek (С1). Предположим, что в результате получили последовательность "001011000101101010".
3. Теперь руководствуясь правилом, что XOR одинаковых битов даёт "0", а разных — "1", вычисляем C2 = "010001111011111001".
4. Объединяем ( C2 (XOR) RSA (C1) ), получая искомые "011010111110010011". Зашифровываем результат RSA Ek ( C2 (XOR) RSA (C1) ).

Условие выполнено:
RSA H (С1, С2) = RSA H (B1, B2)

Успехов!

Добавлено:

Если по условию закрытый ключ RSA нам неизвестен, но доступны блоки B1 и B2 (путанный текст задачи :? ), взлом также возможен. Просто вычисляем ( B2 (XOR) RSA (B1) ) не расшифрованием RSA ( B2 (XOR) RSA (B1) ), а зашифрованием и объединением B1 и B2. А дальше всё так же, как описано выше.

Если ни закрытый ключ RSA, ни открытый текст первого сообщения неизвестны, обращайтесь к Ади Шамиру. ;)

Спасибо SATtva! Весьма познавательно.
Прошу прощения. Как я понимаю, алгоритм подтверждения идентичности открытого ключа, описанный в первом постинге, – равно как и его усиленная версия, предложенная тобой, мало подходят для примения на практике, так как требуют предварительной защищённой передачи одноразового шифроблокнота – т.е. того самого случайного значения R? (Или некоторого их набора) Т.е. уничтожается сам смысл применения несимметричных криптоалгоритмов – возможность обмена открытыми ключами через незащищённый канал связи. Разве что достигается некоторая свобода по времени, если открытый ключ к моменту защищённой передачи шифроблокнота сторонам неизвестен...
Я понимаю так, что это была исключительно учебная задача?

Про протокол взаимоблокировки я, разумеется, помню.

Ghola, да, задачка учебная, как сказала криптоZ. Но до изобретения алгоритмов с открытым ключом применялись именно такие (или подобные) схемы: скажем, предварительно по какому-нибудь надёжному каналу (через курьера, например) согласовывали мастер-ключ, а уже им шифровали сеансовые, которыми обменивались по открытому каналу связи.

Кстати, у первого вопроса из первого постинга есть и другое решение. Можно не усиливать схему при помощи R1. Просто по окончании передачи K' = ( K (XOR) R ) Борис вычисляет K, зашифровывает им какую-нибудь осмысленную фразу, скажем, "Наша Анна громко плачет, уронила в речку мячик", S = Ek §, и отправляет S Анне. Если она сумеет своим ключом расшифровать и прочитать эту фразу, значит Борис обладает копией того же ключа.

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

спасибо!:)))
ужасно интересно!!!!

SATtva, первый раз залез на Ваш форум и вижу, что модератор читать не умеет, зачем конкатенация, алгоритм изложенный криптоZ абсолютно правелен и не надо ничего выдумывать:
Анка генерирует R и XORит с К(ключом),
Березка свою копию К XORит с результатом, получая R, осталось только послать это R Анке
криптоZ,
интересно, где же растят таких гениев защиты информации?

Справедливое замечание. А вот нападки никогда ни к чему хорошему не приводят. У модератора и без того дел полно.