LINUX.ORG.RU

Комутативное шифрование


0

1

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

val == encrypt key1 val >>= encrypt key2 >>= encrypt key3 >>= uncrypt key1 >>= uncrypt key3 >>= uncrypt key2
При условии что encrypt — функция шифрующая открытый текст по ключу, а uncrypt — функция расшифровывающая зашифрованное значение по ключу. Существуют ли какие-то рабочие решения или хотя бы интересные статьи по этой теме?

★★★★★
Ответ на: комментарий от Harald

Вообще да, но меня смущает его применимость. Кроме того, мне нужно чтобы функция encrypt одновременно была сносным криптографическим хэшем для ключа и значения (то есть была бы нетривиальной задача подобрать для пары val1 val2 такие key1 и key2, что

encrypt key1 val1 == encrypt key2 val2
).

KblCb ★★★★★
() автор топика

Используя ключ, запускаешь криптографический PRG (псевдо рандомный генератор) - получаешь расширение ключа до размера текста. Далее xor, как уже сказали (PRG(key) xor MSG).

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

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

Кроме того, если ты задаешь такие вопросы, то реализовать алгоритм ты точно не сможешь.

Вот полезная ссылка: https://www.coursera.org/course/crypto

x_hash
()
Ответ на: комментарий от KblCb

сносным криптографическим хэшем для ключа и значения

Надеюсь ты отдаешь себе отчет о несерьезности своей затеи.

x_hash
()

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

А вообще какая более глобальная задача?

x_hash
()
Ответ на: комментарий от x_hash

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

Самым простым решением задачи было бы простое хэширование карт. Игрок хэширует со случайной солью все свои карты по отдельности и передаёт хэши первому оппоненту, он хэши хэширует ещё раз (со своими солями), перемешивает и отдаёт следующему и так далее. Когда карта открывается, все её соли открываются вместе с ней. Знания хэша карты с начала сессии в известной степени гарантирует, что с начала сессии она не менялась. При этом порядок следования карт неизвестен никому. Когда карта открывается она пускается по кругу в обратную сторону. И вот тут основная проблема данного подхода. Вполне допустима ситуация, когда узнать значение карты должен оппонент, а не игрок (разумеется по обоюдному согласию). Но данный подход этого не позволяет, поскольку только он сопоставить самый нижний хэш со значением. В случае применения шифрования с ключом, мы имеем всё ту же проблему: игрок должен узнать от какой именно карты ему отдать ключ (то есть узнать что это за карта), либо отдать все ключи, что позволяет оппонентом сговориться (особенно легко если он один) и узнать значение всех карт.

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

KblCb ★★★★★
() автор топика
Ответ на: комментарий от KblCb

Почитай Шнайера уже. Там книжка коротенькая, но при этом есть куча алгоритмов и другой полезной инфы. Вроде бы что-то было и по твоей тематике.

А то тебе сейчас насоветуют аналитики, а звездюлей тебе в одиночестве получать придется.

trex6 ★★★★★
()
Ответ на: комментарий от trex6

Ммм… Я кажется понял какого именно Шнайера, но у него по всей видимости больше одной публикации. Можно конкретнее что именно нужно почитать?

KblCb ★★★★★
() автор топика
Ответ на: комментарий от delete83

можно было бы расшифровать теми же ключами в произвольном порядке

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

delete83 ★★
()
Ответ на: комментарий от delete83

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

KblCb ★★★★★
() автор топика
Ответ на: комментарий от Eddy_Em

Да она есть. Я просто решил что я — умный, а aspell — нет. Кажется задача решается если таскать для каждой карты хэш и XOR используя каждый для своих целей.

KblCb ★★★★★
() автор топика
Ответ на: комментарий от KblCb

Поясню немного в силу своих познаний. Если ключ шифруется вместе с сообщением (E(k1, k2+E(k2, k3+E(k3,m)))), то ни о какой коммутативности говорить не приходится, потому что в исходное сообщение на каждом шаге вносятся искажения в виде ключевой информации. Если же ключи передаются отдельно, то подойдет абсолютно любой коммутативный алгоритм шифрования: XOR, сдвиг, шифр Цезаря или еще что-то посложнее. Можно даже что-нибудь из высшей математики подобрать. Вопрос тут стоит лишь в оценке надежности алгоритма шифрования.

delete83 ★★
()
Последнее исправление: delete83 (всего исправлений: 1)
Ответ на: комментарий от KblCb

Скажите, зачем вам три ключа? Вдруг можно подобрать альтернативу...

delete83 ★★
()
Последнее исправление: delete83 (всего исправлений: 1)
Ответ на: комментарий от delete83

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

KblCb ★★★★★
() автор топика
Ответ на: комментарий от KblCb

В таком случае я вначале вам правильно ссылку дал на AACS. Хоть в этом алгоритме ключ и шифруется вместе с сообщением, но расшифровать без «своего» личного ключа все равно не получится. Алгоритм сегодня считается взломанным.

delete83 ★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.