Реферат: Отправка сообщения в будущее
В связи с таким построением возникают две проблемы :
- «силовая атака» допускает тривиальное распараллеливание, в результате чего применение N компьютеров позволяет получить результат в N раз быстрее
- время T является ожидаемым временем дешифрования; на практике это время может быть существенно больше или меньше, в зависимости от того , в каком порядке проверяются ключи.
То есть, необходимо чтобы, схема была построена таким образом, чтобы распараллелить вычисления не представлялось возможным. Справиться со второй проблеммой при построении схемы не удастся, так как порядок перебора ключей, во всём их множестве, может регулировать только сам злоумышленник, желающий узнать конфиденциальную информацию. Первую проблему можно решить выбрав алгоритм шифрования доказуемо – последовательной природы, что и было сделано.
Рассмотрим метод построения “шарад”, предложенный Р.Л.Райвестом, А.Шамиром, Д.А.Вагнером и основанный на последовательном применении операции возведения в квадрат.
Предположим, Алиса желает зашифровать сообщение М, так, чтобы его можно было расшифровать через Т секунд.
Для этого Алиса :
· генерирует сооставной модуль n = pq как произведение двух простых случайно выбранных чисел p и q и вычисляет f(n) = (p-1) (q-1);
· далее вычисляет t = T S , где S – производительность (число возведений в квадрат по модулю n в секунду ) компьютера, предназначенного для решения шарады;
· генерирует случайный ключ К для симметричной криптосистемы, например RC5 . Ключ должен быть достаточно длинным;
· шифрует М на К с помощью RC5 . C(M) = RC5( K, M ) ;
· случайным образом выбирает а по модулю n (1<a<n), и шифрует секретный ключ К таким бразом: C(К) = K + b , для чего сначала вычисляет e = 2t(mod f(n)) (1), и затем b = ae (mod n) (2);
· обьявляет “шараду” в виде набора параметров (n, a, t, C(K), C(M) ) и стирает переменные ( такие ,как : p, q, e, b, n ), созданные в процессе вычислений.
Таким образом, по построению ключ К не может быть найден при помощи “силовой атаки”. Поэтому самый быстрый способ решения “шарады” – это вычисление
b = ae (mod n).
При известном f(n) можно быстро вычислить e, по формуле (1) и затем b по формуле (2). Однако известно, что вычисление f(n) по n столь же трудоёмкая задача, что и разложение n на множители. Таким образом, единственный известный в настоящее время способ вычисления b ( при правильно выбранных параметрах p, q, а ) сводится к последовательному возведению а в кврдрат (t раз), причём каждый раз в квадрат возводится предыдущий результат (таким образом исключается распараллеливание вычислений при “силовой атаке” ).
Хотя попытка разложения n на множители представляет собой альтернативный метод решения, но при достаточно больших p и q такой подход менее эффективен, чем последовательное возведение в квадрат.
Число возведений в квадрат t может контролироваться с точностью до операции, следовательно имеется возможность построения “шарад” с различными уровнями сложности решения.
Более важное обстоятельство заключается в том, что алгоритм вычисления b по формуле (2) является доказуемо – последовательным. Иными словами, алгоритм параллельного вычисления b по формуле (2) в настоящее время неизвестен. Возможность распараллеливания существует только для отдельной операции возведения в квадрат, таким образом, в данной ситуации число компьютеров, применяемых для решения, значения не имеет.
Чтобы, сама Алиса могла расшифровать криптограмму ей не нужно хранить в тайне ключ К , но необходимо знать секрет f(n), чтобы в заданный момент времени вычислить e по формуле (1) и b по формуле (2), расшифровать секретный ключ К и дешифровать своё сообщение.
Следует учесть что такую схему стоит применять только в случае, когда Т не превышает 5 лет , при выполнении всех условий построения схемы. Такой вывод можно сделать по результатам представленым в статье Ю. Е. Пудовченко «Когда наступит время подбирать ключи», а именно , что через каждые 5 лет производительность комтьютеров возрастает в 10 раз. То есть, если зашифровать сообщение , используя такую схему , на десять лет, то через пять лет «силовая атака» ( на более мощных, соответствующих своему времени машинах ) займёт времени в 10 раз меньше , в нашем случае это составит 1 год. Таким образом всё время секретности данного сообщения составит 6 лет, что намного меньше требуемого срока.
Например, для преодоления этого барьера, можно за S ( производительность машины ) принять величину, которая , по каким – то соображениям, будет соответствовать времени раскрытия сообщения или использовать ключи такой длины, чтобы энергия, требуемая для вскрытия ( считая, что на один шаг затрачивается минимальный квантовомеханический квант энергии ) превзошла массу солнца или вселенной. Но, тогда длина ключа может так сильно возрасти, что превысит длину самого сообщения. К тому же оценка может оказаться неправильной. Поэтому , наиболее надёжной схемой, для решения задачи отправки сообщения в далёкое будущее , будет являться схема с использованием доверенных агентов.
Используемые понятия
Для того, чтобы более подробно понять схему с использованием доверенных агентов дадим некоторые базовые понятия.
· Криптография с открытым ключом. В схеме с открытым ключом имеется два ключа, открытый [public] и секретный [private, secret], выбранные таким образом, что их последовательное применение к массиву данных оставляет этот массив без изменений. Шифрующая процедура использует открытый ключ, дешифрующая - секретный. Дешифрование кода без знания секретного ключа практически неосуществимо; в частности, практически неразрешима задача вычисления секретного ключа по известному открытому ключу. Основное преимущество криптографии с открытым ключом – упрощенный механизм обмена ключами. При осуществлении коммуникации по каналу связи передается только открытый ключ, что делает возможным использование для этой цели обычного канала и устраняет потребность в специальном защищенном канале для передачи ключа.
· Цифровая подпись. Цифровой подписью называют блок данных, сгенерированный с использованием некоторого секретного ключа. При этом с помощью открытого ключа можно проверить, что данные были действительно сгенерированы с помощью этого секретного ключа. Это делается таким образом : отправитель шифрует своё сообщение на своём секретном ключе и на открытом получателя, после чего отсылает криптограмму получателю; получатель, в свою очередь дешифрует полученую криптограмму на своём секретном ключе и на открытом отправителя; после этих манипуляций у получателя должно получиться искомое сообщение от отправителя. Цифровые подписи используются для того, чтобы подтвердить, что сообщение пришло действительно от данного отправителя (в предположении, что лишь отправитель обладает секретным ключом, соответствующим его открытому ключу). Также подписи используются для проставления штампа времени (timestamp) на документах: сторона, которой мы доверяем, подписывает документ со штампом времени с помошью своего секретного ключа и, таким образом, подтверждает, что документ уже существовал в момент, объявленный в штампе времени.
· Односторонняя хеш функция. Такая функция не поддаётся обращению - нельзя узнать её аргумент, зная результат. Также существует односторонняя функция с потайным ходом ("лазейкой"). Идея состоит в том, чтобы построить функцию, обратить которую можно только зная некоторую "лазейку" - секретный ключ.
· RC5. RC5 это довольно-таки быстрый блочный шифр разработанный Ривестом для RSA Data Security. Этот алгаритм параметричен, т.е. с пременным размером блока, длинной ключа и переменным числом проходов. Размер блока может быть 32, 64, или 128 битов. Количество проходов в промежутке от 0 до 2048 бит. Параметричность такого рода дает гибкость и эффективность шифрования. RC5 состоит из ввода ключа (key expansion), шифрования и дешифрования. При вводе ключа вводятся также количество проходов, размер блока и т.д. Шифрование состоит из 3 примитвных операций : сложения, побитового XOR и чередования (rotation). Исключительная простота RC5 делает его простым в использовании, RC5 текст, также как и RSA, может быть дописан в конец письма в зашифрованном виде. Безопасность RC5 основывается на зависящем от данных чередованием и смешиванием результатов различных операций. RC5 с размером блока 64 бита и 12 или более проходов обеспечивает хорошую стойкость против дифференциального и линейного криптанализов.
· Схема разделения секрета. Математика разделения секрета достаточно сложна, и является темой отдельного разговора, поэтому дадим неформальное определение данного понятия. Схемой разделения секрета называется такая схема, которая позволяет «распределить» секрет между n участниками таким образом, чтобы заранее заданные разрешённые множества ( множества “теней секрета” ) участников могли однозначно восстановить секрет, а неразрешённые - не получили никакой дополнительной информации о возможном значении секрета. Пороговая схема разделения секрета, (n , θ ) – схема, позволяет восстанавливать секрет, если разрешённым множеством является любое множество из θ или более “теней секрета”.
Схема с использованием доверенных агентов.
Данная схема является более предпочтительной для сохранения секретности сообщения долгое время, именно эта схема должна использоваться в ситуации с «замороженными» людьми, так как время пребывания в летаргическом сне ограничивается ни несколькими годами, а несколькими десятилетиями.
Итак, подход данного метода заключается в использовании доверенных агентов для хранения сообщения М в течение заданного интервала времени t . Для большей надёжности схемы шифрования , ключ К , на котором собираемся зашифровать сообщение М поделим на d “теней”, воспользовавшись техникой разделения секрета предложенной А.Шамиром, и распределим “ тени “ секретного ключа среди нескольких агентов, заручившись с их стороны обязательством, что соответствующие фрагменты будут предъявлены по истечении времени t . Заметим, что используемая техника разделения секрета обладает избыточностью и позволяет восстанавливать секретный ключ в случае, когда некоторые агенты не в состоянии выполнять свои функции. Тогда криптограмма С =Е ( К,М ) может быть помещена в общедоступное место с тем, чтобы можно было получить сообщение М (воостановив ключ К и дешифровав сообщение С ) по истечении времени t .
Итак Райвист, Шамир и Вагнер предложили альтернативный метод со следующими свойствами:
· Агенты не хранят ключи, применяемые в схеме шифрования.. Каждый агент хранит “тень” ключа, получаемую с помощью техники разделения секрета. Необходимый объём памяти, выделенной под “тень” ключа, фиксирован и не зависит от числа секретных компонент, доверенных агенту.
· Сначала, каждый агент формирует свой секретный ключ, который он раскроет в момент времени t . Далее, с помощью этого ключа, агент должен будет подтверждать своё существование и свою личность.
· Основная задача агента : периодически ( например, в начале каждого часа ) раскрывать ранее секретное значение - Si,t ( получать новое значение хеш-функции) и заверять раскрытый секрет цифровой подписью на своём секретном ключе, который раскрывается в заданный момент времени. Под выражением ранее секретное значение - Si,t понимается старый результат хеш-функции.
· Также, агент должен отвечать на вопросы вида : “Для заданных значений у и t возвратите значение функции E( y , Si,t ) – результат шифрования у на секретном ключе Si,t , который Вы предполагаете раскрыть в момент времени t”. Предполагается, что используемая для шифрования криптосистема устойчива к атаке на открытом тексте, то есть злоумышленник не сможет восстановить секретный ключ Si,t , располагая результатами шифрования различных у –ов на фиксированном ключе Si,t. Сформировать сообщение, подписать его на открытом ключе пользователя и на закрытом агента. Сформированное сообщение должно содержать номер агента, текущее время, время t, раскрытый и подписаный секрет Si,t и значение функции E( y , Si,t ).
