Отправка сообщения в будущее
* «шарады» с временным замком на базе вычислительных проблем с существенно последовательными алгоритмами решения;
* использования доверенных агентов, принимающих на себя обязательство нераскрывать информацию в течение заданного интервалавремени.
Специфика первого метода заключается втом, что в отличие от традиционныхкриптографических методов, предполагающих наличие у получателясообщения секретного ключа отправителя (в симметричных криптосистемах) или у отправителя сообщения аутентичного ( подлинного ) открытого ключа получателя ( в асимметричных криптосистемах ), секретный ключ уничтожается сразу после шифрования и неизвестен как отправителю, так и получателю сообщения. А при использованиивторого метода с довереннымидоверенных агентов возникает проблемма надёжности, котораячастично может быть решена за счёт применения криптографической техники разделения секрета. В данной работе будут рассмотрены оба метода.
Оглавление
1. Ведение ……………………………………………………………4
2. Анализ литературы………………………………………………..5
3. Используемые обозначения……………………………………...6
4. Глава 1. Решаемые проблемы…………………………………....7
5. Глава 2. Методы построения криптосистем с временным раскрытием…………………………………………………………8
5.1. «Шарады» с временным замком (time – lock puzzles) ……9
5.2. Используемые понятия…………………………………….12
5.3. Схема с использованием доверенных агентов…………14
6. Заключение…………………………………………………………19
7. Список литературы………………………………………………..20
Ведение
Испокон веков не было ценности большей, чем информация. ХХ век - век информатики и информатизации. Технология дает возможность передавать и хранить все большие объемы информации. Это благо имеет и оборотную сторону. Информация становится все более уязвимой по разным причинам:
* возрастающие объемы хранимых и передаваемых данных;
* расширение круга пользователей, имеющих доступ к ресурсам ЭВМ, программам и данным;
* усложнение режимов эксплуатации вычислительных систем.
Поэтому все большую важность приобретает проблема защиты информации от несанкционированного доступа при передаче и хранении.
Сейчас услугикриптографии необходимы почти во всех областяхдеятельности человека. С развитием прогресса, появляется необходимость решать задачи, которые, совсем недавно,писателинаучно-фантастического жанра описывали в своихпроизведениях.
Ещё совсем недавно проблема отправки секретных сообщений в будущееволновала только любителей фантастической литературы. Однако сегодня она становится всё более актуальной, всвязи с научно-техническим прогрессом.
Например, известно, что современные технологии позволяют
«замораживать»телочеловека доуровня поддержания минимальныхфункций жизнедеятельностиорганизма и надёжно хранить определённоевремя. Услуги подобного рода, в ряде случаев, являютсяединственной надеждойлюдей, страдающих тяжелыми заболеваниями. Следует учесть, что с ростом продолжительности жизни человека,ухудшения экологической обстановки, количество таких болезней сильно увеличилось в наши дни. Например, есличеловек мучается болезнью, которая сегодня неизлечима,но имеет достаточно средств, то он может «отправить себя в будущее», воспользовавшись услугами криогенных депозитариев. Именно здесь и появляетсяпроблеманадёжностишифрования сообщений. Очевидно, что «замороженный» человек не является дееспособными не может отвечать закакую-либо секретную информацию. Вместе с тем, он должен иметь возможность оставить некоторые распоряжения ( установить номер счёта, точное содержание завещания, если произойдёт несчастный случай, историю болезни и т. п.), которые гарантированно были бы выполнены только по истечении заданного срока – не раньше и не позже.
Эту проблему позволяют решить криптографические методы обеспеченияконфиденциальности и целостности при заданномвремени дешифрования сообщения на неизвестном ключе.
Анализ литературы.
Публикаций натемуданной работы очень мало. Это обусловлено, в первую очередь тем, что ранее не существовалосильной необходимости в шифровке сообщений на такой длинный период времени. Первым, кто обратился к сообществу Intеrnet с предложением рассмотреть подобную задачу в связи с потребностями людей, пользующихся услугами криогенных депозитариев, был Тимоти Мэй. Именно он и предложил использовать в криптографической схеме довереннях агентов. Как ответ на этот запрос и возникли рассматриваемые схемы, которые были разработаны известными криптографами Рональдом Л. Ривестом , Ади Шамиром и Девидом А. Вагнером. Насколько мне известно, других криптографических схем, направленых именно на решение этой проблеммы нет. Никакойлитературы, кроме ответной статьи Ривеста, Шамира,Вагнера и дополнения этой же статьи в журнале “Конфидент”5’96 мне найти не удалось. Следует учесть, что предложенные схемы основываютсянабазовых понятиях криптографии, с которыми можно ознакомиться в любой специализированной литературе.
Используемые обозначения.
? М-секретное сообщение.
? К-секретный ключ, на котором шифруется М.
? t - время, на которое шифруется М.
? t?- текущее время.
? S - производительность компьютера.
? Е- выбранный алгоритм шифрования.
? p ,q – простые числа.
? n –формируется, как произведение чисел pи q.
? f(n) –формируется , как произведение чисел (p-1) и (q-1).
? d– количество, доверенных агнтов.
? i[М1]–номер агента.
? ?– порог схемы разделения секрета.
? Si,t- секретный ключ агента.
? Di,t – открытый ключ агента.
? yj –“тень” ключа К , j-ого агента
? rj – криптограмма “тени” ключа К , j-ого агента
? F – односторонняя хеш-функция.
Глава 1. Решаемые проблемы.
Кроме сохранения информации о «замороженном», на заданный сроктакже, необходимо упомянутьи некоторые другие практические приложениякриптографиис временным раскрытием:
* участник торгов может пожелать «запечатать» предложение цены с тем, чтобыоно было «распечатано» по завершении торговой сессии;
* домовладелецхочет предоставитьдержателю закладной возможностьосуществлять платежис использованием зашифрованного цифрового кэша (digital cash) с различными датами дешифрования так, чтобы оплата выполнялась в начале каждого следующего месяца;
* частное лицо может пожелать зашифровать свой дневник так, чтобы он могбыть дешифрован по истечении определённогосрока;
* схема шифрованияс депонированиемключей (key-escrow scheme) может быть реализована на базе “шарад” с временным замкомс тем,чтобы правительственные организациимоглиполучить ключи длярасшифровки сообщения только только по истеченииопределённого периода времени.
В некоторых из вышеперечисленныхситуацияхвремяна котороесообщение остаётсясекретнымколеблется в рамках1 года,когдав случае с«замороженным»человеком или шифровкой дневника этот срок ограничиваетсяснизу, какминимум, 2-3 годами , верхняя оценка является вообще неопределённой. Учитывая данное обстоятельство, естественно было бы предложить два метода шифрования сообщения, на не очень длительный период времени 2-3 года и на достаточно длительное время , порядка нескольких десятилетий, что и было сделано. Каждый из методовдолжен использоваться в соответствующей ситуации.
В основном, криптографическая задача шифрования сообщениярассматривается таким образом,чтобы полученная криптограмма моглабыть дешифрована ( в том числе и самим отправителем сообщения) по истечениизаданного интервала времени. Атака на подобную криптосистему считается успешной , еслиудаётся дешифровать сообщение существенноранееустановленного срока. Такой способ защиты, с возможностьюраскрытиясекретной информации по истечении определённого времени,и называется криптографией с временным раскрытием( timed - release crypto ).
Глава 2. Методы построения криптосистем с временным раскрытием.
Криптосистема свременнымраскрытием, предложенная Р.Л.Райвестом, А.Шамиром и Д.А.Вагнером получила название «шарады» с временным замком (time – lock puzzles ).Данный подход к защите информации связан именно с проблемами, возникающимипри отправкесекретного сообщения в будущее. Егоспецификазаключается втом , что в отличие от традиционныхкриптографических методов, предполагающих наличие у получателясообщения секретного ключа отправителя ( в симметричных криптосистемах) или у отправителя сообщения аутентичного ( подлинного ) открытого ключа получателя ( в асимметричных криптосистемах ) , секретный ключ уничтожается сразу после шифрования и неизвестен как отправителю, так и получателю сообщения.
В настоящее время существует два основных метода построения криптосистем с временным раскрытием :
* «шарады» с временным замком на базе вычислительных проблем с существенно последовательными алгоритмами решения;
* использования доверенных агентов , принимающих на себя обязательство нераскрывать информацию в течение заданного интервалавремени.
Очевидно, что при использовании доверенных агентов возникает проблемма надёжности, котораячастично может быть решена за счёт применения криптографической техники разделения секрета. Процессорное время необходимое для решения «шарады» зависит от количества и вида применяемого аппаратного обеспечения, а также достиженийв области распаралеливания вычислений. Далее будут рассмотрены оба метода.
«Шарады» с временным замком (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
Таким образом, по построению ключ К не может быть найден при помощи “силовой атаки”. Поэтому самый быстрый способ решения “шарады” – это вычисление
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 ).
* каждый агент всегда подписываетсвои секретный и открытый ключи.
Итак, схема с использованием доверенных агентов выглядит так : сначаланаслучайно выбраном ключе К при помощи симметричной криптосистемы пользовательшифрует сообщение М , и получает
С=( К, М ).
Далее, выбрав 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 – lockpuzzle 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/ Александру Ежову занекоторые идеидлярешения этой задачи и статью Ю. Е. Пудовченко, “Когда наступит время подбирать ключи“.
[М1]
[М2]
[М3]
[М4]
[М5]