Реферат: Отправка сообщения в будущее
· каждый агент всегда подписывает свои секретный и открытый ключи.
Итак, схема с использованием доверенных агентов выглядит так : сначала на случайно выбраном ключе К при помощи симметричной криптосистемы пользователь шифрует сообщение М , и получает
С=( К, М ).
Далее, выбрав d агентов i1, [М2] i2,… ,id пользователь публикует :
( С, i1, [М3] i2,… ,id. , r1, r[М4] rrRRgКкпрпл2,… ,rd ) ,
где r1, r[М5] rrRRgКкпрпл2,… ,rd - d криптограмм “теней” ключа К . “Тени” получены по схеме разделения секрета, позволяющие восстанавливать ключ К в момент времени t ,после того, как агенты раскроют свои секреты. Размер “тени” ключа фиксирован и не зависит от числа секретных компонент, доверенных агенту. Также пользователь может установить порог θ (0 < θ ≤ d ) такой, что восстановление ключа К будет возможно только при θ или большем числе “теней” ключа К . Для этого пользователь просто разбивает ключ К на d “теней” по любой схеме разделения секрета с порогом θ.
После шифрования ключ К удаляется.
Далее пользователь просит агента возвратить ему криптограмму, соответствующей агенту, «тени» ключа на секрете агента . Тогда
rj = E( yj , Si,t ) ,
где (y1, y2 , …. ,yd) d “теней” ключа К .
После, пользователь генерирует составной модуль
n = pq ,
как произведение двух простых случайно выбранных чисел p и q . После чего вычисляет
f(n) = (p-1) (q-1) и
e = 2t(mod f(n)).
Пара чисел (e, n) и будет являться открытым ключём пользователя.
Итак, данная схема представляет собой асимметричную систему с открытым ключом. Каждый из участников данной схемы имеет свой открытый и закрытый ключ, закрытые ключи агентов - их секреты, у пользователя количество закрытых ключей может равняться количеству агентов, так, чтобы понимать их сообщения или же пользователь должен иметь один универсальный закрытый ключ, который он смог бы применять для дешифрования всех получаемых им сообщений.
Таким образом обязанности агента заключаются в следующем:
Þ переодически раскрывать ранее секретное значение –получать новое значение хеш-функции. Обозначим за Sij,t секретное значение раскрываемое ij агентом в момент времени t . Последовательность секретов, раскрытых одним агентом, не зависит от последовательности секретов раскрытых другими агентами. Такая последовательность обладает следующим свойством : из каждого Sij,t΄ можно просто вычислить Sij,t для всех t΄ ≤ t .Секрет, раскрываемый агентом может быть использован для вычисления всех ранее раскрываемых секретов в силу следующего рекуррентного уравнения : Si,(t-1) = F ( Si,t ) (3), где f - некоторая односторонняя хеш-функция (Si,(t-1) –новый секрет, Si, t – старый, индекс (t-1) - означает время которое осталось до раскрытия секрета, 1 применяемая в записи, условна и означает время, которое прошло с прошлого раскрытия секрета до текущего момента времени) Поскольку функция F является односторонней, раскрытие Si,t не позволяет раскрыть прошлые секреты Si,t. (В противном случае злоумышленник мог бы вычислить последовательность секретов по формуле (3), начиная с некоторой точки в будущем, или выбрать функцию F с “лазейкой”, так чтобы только он смог вычислить Si,t - секретный ключ агента из Si,(t-1) ). Каждый раскрытый секрет агент должен подписать на своём секретном ключе. Новый, полученый секрет объявляется открытым и используется для общения агента с пользователем то есть, чтобы пользователь мог удостовериться в личности агента .
Þ дешифровать, на своём секретном ключе, сообщение пользователя вида (y, t, (e, n)) зашифрованные на открытом ключе агента, где y - любое сообщение пользователя не содержащее никакой секретной информации.
Þ шифровать сообщение y на секрете Si,t ,раскрываемого агентом в момент времени t . Таким образом имеем криптограмму E(Si,t ,y).
Þ сформировать сообщение вида :
m=( i, t, t˚ , E(Si,t ,y)),
где i - индекс агента, t – время раскрытия в будущем, t˚ - текущее время ( по
часам агента). Это сообщение шифруется на открытом ключе пользователя
(e, n) и подписывается на полученном секрете агента - Si,t˚ :
E( E( m , (e, n) ) , Si,t˚ ).
Выполнение неравенства t > t˚ не требуется, однако
рассматривается как норма.
· раскрыть подписаный секрет Si,t в момент времени t .
Сразу после шифровки “тени” основного ключа К агент должен раскрыть свой секрет – получить значение хеш-функции, проделать все полагающиеся манипуляции и объявить пользователю свой открытый ключ – раскрытый секрет Si,t , подписаный на своём секретном ключе. Изначально аргументом используемой хеш-функции является секретный ключ агента. Таким образом агент уже выполнил свои обязанности один раз и схема должна сработать. Как видно по построению, сколько раз или когда именно агент будет раскрывать свой секрет – не важно. Также нет никакой зависимости между количеством раскрытия секрета разными агентами. Вообще, агент может учавствовать во всей схеме два раза : первый – зашифровать “тень”, подписать новый секрет и т.д. ; второй – раскрыть свой секретный ключ в заданное время.
Столь простой набор функций допускает простую реализацию в виде устойчивого к вскрытию, секретного, компактного и надежного устройства. Роль пользователя в такой схеме осуществляет сервер, который контролирует все манипуляции агентов при раскрытии секрета. Сообщение у может либо заранее задаваться администратором, либо генерироваться самим сервером, так как никакой смысловой нагрузки не несёт, а служит для аутентификации агента. Как было сказано выше, каждый агент имеет свой секретный ключ, который раскрывается в момент времени t, этот ключ учавствует в схеме в нескольких случаях – когда шифруется “тень” основного ключа К, когда агент дешифрует сообщение пользователя , подписывает сообщение у и раскрываемый секрет. Новый раскрытый и подписанный секрет, учавствует в диалоге пользователя и агента, и является открытым для пользователя, чтобы пользователь мог дешифровать ответное сообщение.
Работоспособность такой схемы достигается за счет применения пороговой схемы разделения секрета, обладающей избыточностью и позволяющей восстанавливать сообщение в случае, когда некоторые агенты не в состоянии выполнять свои функции. Если в системе существует не менее θ агентов, сообщение с гарантией будет восстановлено в указанные сроки, в противном случае будет восстановлено в будущем.
Описанная схема использования доверенных агентов не “верифицируема” в том смысле, что по опубликованым данным невозможно заранее принять решение о восстановлении сообщения. Сообщение М может быть восстановлено только после раскрытия агентами своих секретов, дешифрования rj с целью получения yj для дальнейшего восстановления секретного ключа К и дешифрования С. Для
решения проблемы необходимо применять “верифицируемые” схемы разделения секрета.
Для уменьшения потока обращений к пользователю рекомендуется поступать таким образом : с самого начала, агенты формируют свои открытые и секретные ключи Di,t и Si,t соответственно, где Di,t = f (Si,t). Для большей надёжности агенты всегда подписывают свои открытые и закрытые ключи. Агент делает доступным ключ Di,t для пользователя. Тогда пользователь сам может проделать все необходимые манипуляции с сообщением y используя вместо секретного ключа агента, подписаный агентом открытый ключ Di,t. Таким образом в обязанности агента будет входить :
· периодическое раскрытие своего открытого ключа Di,t – получение нового значения хеш – функции.
· подписывание полученного значения на своём секретном ключе Si,t.
· раскрыть подписаный секрет Si,t в момент времени t .
Таким образом пользователь будет уверен, в личности агента и в том, что агент существует.
Обе приведённые схемы с использованием доверенных агентов будут выполнять свою задачу – сохранять секретное сообщение одинакого. Разница заключается только в том, что во второй схеме у агента намного меньше обязанностей : агенту не так часто надо раскрывать свой секрет и время выполнения обязательных манипуляций намного меньше. На практике оба метода могут использоваться вместе. Например, агенты, которые находятся далеко от пользователя ( то есть передача сообщения между ними занимает значительное количество времени ) могут использовать вторую схему, тогда как, агенты, находяциеся не так далеко могут использовать первую схему.
На мой взгляд, по истечении хотя бы половины заданного срока можно добиться раскрытия сообщения применяя “грубую силу” к самой криптограмме С ( то есть простой перебор ключей К ), к тому времени производительность машин может сильно возрасти и время ожидания при атаке “грубая сила” значительно снизится . Для преодоления этого препядствия, как мне кажется, можно внести некоторые изменения. Например потребовать, чтобы в заданное время t часть секретов была раскрыта агентами на определённых терминалах ( например, находящихся в здании криогенного депозитария, рядом с сервером ) или в определённой последовательности.
Для преодоления договорённости между агентами , на мой взгляд, необходимо увеличить число агентов, причём некоторым раздать “тени” искомого ключа, а некоторым “белый шум” , таким образом агентам будет очень сложно сговориться. Но вообще , считается, что агент - человек заслуживающии доверия.
Учитывая всё вышесказанное следует отметить, что такой подход требует большего объёма памяти для хранения списка открытых ключей, которые будут использованы в будущем, и списка раскрытых ранее секретных ключей. Так , необходимый объём памяти на пятьдесят лет (из расчёта один ключ на каждый день ) при размере ключа 200 бит составит 3,5 Мбайт.
Заключение.
Эта работа посвящена криптографическим схемам сохранения секретного сообщения на долгое время (от месяца до нескольких десятков лет). Существует две схемы подобного типа : «Шарады» с временным замком (time – lock puzzles) и схема с использованием доверенных агентов. Первая схема заключается в том, что сообщение кодируется ключом, который неизвестен как отправителю, так и получателю сообщения и который не будет раскрыт в течение времени секретности данного сообщения, за счёт своей длины. Недостаток такого метода, заключается в небольшом периоде времни секретности сообщения, из за прогресса вычислительных мощностей компьютеров. Наиболее интересна вторая схема, так как позволяет оставить сообщение секретным на более долгий срок (этот срок ограничивается длиной жизни как минимум θ агентов) . Суть метода заключается в том, что “тени” ключа, на котором шифруется секретное сообщения, распределяются между доверенными агентами. Агенты шифруют свои “тени” с помощью выбранного алгоритма на своём секретном ключе, который они раскроют только по истечении заданного времени. Каждый агент должен периодически подтверждать своё существование и личность с помощью определённых действий. В заданный момент времени агенты должны раскрыть свои секреты, дешифровать соответствующие “тени”, “собрать” из полученных “теней” искомый ключ и дешифровать сообщение. Стойкость такой схемы обеспечивает не только длина ключа но и не “верифицируемость” , то есть принять какое либо решение о восстановлении сообщения, по опубликованным данным, невозможно. Все действия агентов, по заверению своей личности, выполняются в строгом порядке и регулируются “пользователем” – сервером.
Насколько мне известно, других криптографических схем, направленых именно на решение этой проблеммы нет. Сейчас существуют криптографические схемы, которые решают проблему длительной секретности сообщения, за счёт длины ключа. На сегодняшний день, рекомендованная длина ключа составляет около 4000 бит.
На мой взгляд, в будущем, большую популярность приобретут именно схемы с доверенными агентами. Со временем, мощности машин будут увеличиваться, а значит многие задачи ( разложение большого целого числа на простые множители, вычисление дискретного логарифма по модулю большого целого числа) будут решаться намного быстрее и срок секретности сообщения будет также уменьшаться. Использование доверенных агентов или иерархий доверия, основаных на цифровой подписи, в такой ситуации будет оптимальным решением проблемы секретности собщений. Поэтому , как мне кажется, развиваться будут именно криптографические схемы “с доверием”.
Литература.
1. Ronald L. Rivest, Adi Shamir and David A.Wagner “Time – lock puzzle and time-release Crypto”. (http://theory.lcs.mit.edu/~rivest - 1999г. на сегодняшний день сайт обновлён и данной публикации не содержит)
2. А.Л.Чмора, “Шифровка в будущее” , “Конфидент”5’96
3. Ю. Е. Пудовченко, “Когда наступит время подбирать ключи“
4. Перевод статьи Tatu Ylonen “Introduction to Cryptography“
5. Г.А.Кабатянский, “Математика разделения секрета”.
Особое спасибо web-мастеру страницы http://www.ssl.stu.neva.ru/ Александру Ежову за некоторые идеи для решения этой задачи и статью Ю. Е. Пудовченко, “Когда наступит время подбирать ключи“.
