В настоящее время существует два основных метода построения криптосистем с временным раскрытием :
- «шарады» с временным замком на базе вычислительных проблем с существенно последовательными алгоритмами решения;
- использования доверенных агентов , принимающих на себя обязательство не раскрывать информацию в течение заданного интервала времени.
Очевидно, что при использовании доверенных агентов возникает проблемма надёжности, которая частично может быть решена за счёт применения криптографической техники разделения секрета. Процессорное время необходимое для решения «шарады» зависит от количества и вида применяемого аппаратного обеспечения, а также достижений в области распаралеливания вычислений. Далее будут рассмотрены оба метода.
«Шарады» с временным замком (time – lock puzzles)
Идея заключается в том, что решение «шарады» позволяет получить секретный ключ для дешифрования ранее зашифрованного сообщения. Это значит, что применяя «силовую атаку» (исчерпывающий перебор в ключевом пространстве), злоумышленник сможет раскрыть сообщение, только тогда, когда содержание, раскрытого им сообщения уже не будет актуальным. Как было отмечено выше, сложность ( время ) решения «шарады» существенно зависит от количества вычислительных ресурсов . Таким образом , основная задача при построении любой «шарады» сводится к выбору алгоритма доказуемо – последовательной природы, то есть алгоритма, который не может быть распараллелен в принципе и эффективность ( сложность ) которого существенно не зависит от вложенных в аппаратуру и програмное обеспечение средств. При этом использование нескольких работающих параллельно компьютеров не позволяет ускорить решение «шарады».
Однако такой подход к построению «шарад» не позволяет точно определить время решения, так как использование различных технологических элементов приводит к разбросу производительности конечных аппаратных реализациий. Метод, основаный на использовании доверенных агентов, является более продподчтительным в случае, когда решение должно быть предьявлено точно в указанный срок.
Необходимо подчеркнуть, что предлагаемый метод построения «шарад» не позволяет автоматически получать решение через определённое время, а требует непрерывной работы компьютера в течение заданного времени. Например, решение, рассчитанное на 10 лет, требует непрерывных вычислений в течение всего этого времени. Очевидно, что решение не будет получено через 10 лет, если вычислительный процесс был запущен через 5 лет ( на машине, производительность которой соответствует пятилетней давности ) после того , как сообщение было зашифровано. Таким образом по сравнению с использованием доверенных агентов, метод последовательных ввычислений требует большего количества ресурсов ( для выполнения непрерывных вычислений ) и может эффективно применяться для решения простых «шарад» ( например с временем раскрытия в один месяц ).
Для пояснения задачи рассмотрим следующий пример. Обозначим через М сообщение, которое должно быть зашифровано, а через S производительность ( дешифрований в секунду ) компьютера. Для шифрования сообщения М так, чтобы оно могло быть дешифровано по истечении Т секунд, выберем симметричную криптосистему ( например RC5 ).И выполним шифрование сообщения на ключе длинной
K = lg ( 2ST )
бит. Сохраним криптограмму и уничтожим ключ. После этого применение «силовой атаки» ( исчерпывающего перебора в ключевом пространстве ) позволит найти ключ в среднем за Т секунд.
В связи с таким построением возникают две проблемы :
- «силовая атака» допускает тривиальное распараллеливание, в результате чего применение 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) на документах: сторона, которой мы доверяем, подписывает документ со штампом времени с помошью своего секретного ключа и, таким образом, подтверждает, что документ уже существовал в момент, объявленный в штампе времени.