* «шарады» с временным замком на базе вычислительных проблем с существенно последовательными алгоритмами решения;
* использования доверенных агентов, принимающих на себя обязательство нераскрывать информацию в течение заданного интервалавремени.
Специфика первого метода заключается втом, что в отличие от традиционныхкриптографических методов, предполагающих наличие у получателясообщения секретного ключа отправителя (в симметричных криптосистемах) или у отправителя сообщения аутентичного ( подлинного ) открытого ключа получателя ( в асимметричных криптосистемах ), секретный ключ уничтожается сразу после шифрования и неизвестен как отправителю, так и получателю сообщения. А при использованиивторого метода с довереннымидоверенных агентов возникает проблемма надёжности, котораячастично может быть решена за счёт применения криптографической техники разделения секрета. В данной работе будут рассмотрены оба метода.
Оглавление
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
После шифрования ключ К удаляется.
Далеепользователь проситагента возвратить ему криптограмму, соответствующей агенту, «тени» ключа на секрете агента . Тогда
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]