Курс "Защита информации", кафедра радиотехники, Московский физико-технический институт (МФТИ)

2010: Главная Экзамен Лекции Семинары Проекты Эссе | Преподаватели Литература | Архив: 2009 2008-fall 2008 2007 2006 2005 2004 2003 | English
HTML-версия эссе "Timed-released Crypto", Petrov, 2004, сгенерированная из pdf/rtf.
Конвертация не вcегда корректна. Смотрите исходный pdf.
Петров Роман 015 группа
Timed-released crypto
Общие сведения.
Криптография с временным раскрытием (Timed-released crypto) - способ защиты информации с возможностью расшифровки сообщения лишь по прошествию определенного промжутка времени. T. May (Тимоти Мэй) был первым, кто обратил внимание на эту проблему.
Практическое применение timed-released crypto может найти, например, в шифровании личных дневников, с последующим обнародованием, допустим через 100 лет. Если зашифровать таким образом сообщения, цель которых - перевести деньги с одного счета на другой, но с разными датами, то мы получим возможность «помесячной оплаты». И, наконец, схема шифрования с депонированием ключей может быть легко реализована на базе TRC. Таким образом, ключи будут доступны лишь по прошествию определенного промежутка времени.
Существует два подхода для создания Timed-Released Message:
•    Использование так называемых «шарад с временным замком» (Time-Lock Puzzles) - задач, которые не могут быть решены без продолжительных вычислений и требуют определенного промежутка времени для нахождения ответа.
•    Использование доверенных лиц, которые не открывают секрета в течение указанного срока
Каждый способ имеет свои недостатки. Так, процессорное время, необходимое дл ярешения задачи может меняться как из-за технического прогресса (более быстрые машины), научного прогресса или простого распараллеливания вычислений.
А при использовании доверенных лиц встает проблема их надежности.
Time-Lock Puzzles
Итак, создание time-lock puzzles, основано на некотором процессе вычислений, который занимает определенное время. Решение дает ключ К, которым и расшифровывается сообщение М. Поскольку мы стремимся сделать реальное время эквивалентным «компьютерному», необходимо не допустить возможности распараллеливания, поскольку в противном случае задача может быть решена в несколько раз быстрее. Ключ также должен быть достаточно большим, чтоб нельзя было его подобрать грубой атакой за время, меньшее, чем отведено по условию time-lock puzzle. Необходимо учитывать то, что шарады дают решения через Tдействия , а не точно в назначенный момент.
Решения, получаемые на разных технологических элементах (на базе арсенида галия быстрее чем на базе кремния). Поэтому метод доверенных лиц предпочтительнее, когда речь идет о долгих сроках (более дешев) или при необходимости открытия точно в заданное время.
Методический вариант
Сначала рассмотрим не работающий вариант создания головоломки, полезный в методических целях, предложенный Мерклем (Mercle R. C.) (который ввел термин Time-lock puzzle):
Пусть М - сообщение и S- скорость компьютера (расшифровок в секунду). Чтобы существовала возможность расшифровать М не раньше, чем через Т секунд, будем
шифровать, например, используя RC5 с ключем К длины_             бит, а затем
удалим ключ К. Тогда простым перебором вариантов удастся подобрать К приблизительно за Т секунд (в среднем, разумеется). Легко видеть два недостатка такой схемы:
•    дает возможность распараллелить вычисления
•    ключ можно найти как значительно раньше Т, так и значительно позже
Метод Ривеста, Шамира и Вагнера (Rivest, Shamir, Vagner)
Пусть пользователь А хочет зашифровать сообщение М на Т секунд. Он создает число n=pq, где p и q - простые числа.
1)Также А вычисляетгде S количество возведений в квадрат по модулю n за секунду компьютера, который будет производить решение TLP.
2)  А берет достаточно длинный ключ К (опять же чтоб его нельзя было найти грубой атакой за время Т) и зашифровывает своё сообщение М ключем К, используя для этого, например,RC5.
3) А берет произвольное число a (1
Чтобы сделать это быстро (ведь мы знаем p и q)
4)при этом параметры р и q стерты.
Решение
Поскольку К достаточно длинен по построению, искать его прямым перебором
бессмысленно. Наиболее быстрым вариантом будет высчитать
B=a2t,
Поскольку мы не знаем Ф(n)
А так как B будет высчитываться последовательно (ведь каждый раз возводится в квадрат
предыдущий вариант) то распараллелить такой процесс будет невозможно. Правда стоит
заметить, что существует возможность распараллелить саму операцию возведения в
квадрат - но это несущественно.
Таким образом головоломка будет раскрыта лишь по прошествию определенного времени
Использование доверенных лиц
Естественный путь - использование доверенного агента, который будет хранить сообщение М до необходимой даты.
Улучшение этого метода состоит в разделении М на фрагменты, которые будут храниться у разных агентов, которые также опубликуют свои части М во время Т, тем самым позволяя реконструировать сообщение. (таким образом мы уменьшаем вероятность досрочного получения сообщения подкупом)
Дальнейшее улучшение - агенты хранят лишь часть ключа (похоже на Time Lock Puzzle), что уменьшает объем хранимой информации. При этом сам шифр С=Е(К, М) находится в доступном месте. После того, как все части ключа опубликованы, ключ восстанавливается и М расшифровывается.
Подход Ривеста, Шамира и Вагнера (Rivest, Shamir, Vagner)
•    Агентам нет необходимости хранить никакой информации, выданной пользователем. Объем информации строго фиксирован независимо от числа попросивших об услуге.
•    Главная задача агента - периодически (допустим, раз в час) опубликовывать свой так называемый секрет. Пусть «секрет», опубликовываемый i-тым агентом во время t, обозначается какАгент подписывает свой секрет своей цифровой подписью.
•    Всё, что разрешено агенту, - отвечать на запросы вида «Вот значения Y и t — верните- Y зашифрованное личным ключем агента Кш который будет открыт во время t. Предполагается, что алгоритм шифровки защищен от атак вида «chosen message attack», т.е. по ответам на разные сообщения клиент не сможет узнать Sit
•    Агент возвращает подписанное сообщение где I -идентификатор агента, t - время открытия, t0- текущее время по часам агента. М зашифровано KU клиента и подписано Кr агента.
•    Кто угодно может предложить свои услуги в качестве агента без координации с другими агентами. Т. е. Последовательность секретов одного агента независима от последовательности секретов другого агента.
•    Последовательность секретов, опубликовываемая агентом, должна иметь следующее свойство - из должна легко посчитатьгдеПоэтому достаточно узнать последний секрет, чтобы просчитать все предыдущие. Итак
Причем, функция f не должна иметь обратной, чтобы нельзя было узнать будущие ключи. (1)
•    Для того, чтобы получить trc пользователь шифрует С=E(К, М) произвольным ключемК. Выбирает d агентов си получает от них
•    Пользователь также может выбрать ө порог ( т.е. число агентов из d, получив которых, можно восстановить ключ).
Агентам необходимо:
•    создать последовательностьудовлетворяющую (1)
•    расшифровать своим Кr сообщение от клиента и получить y и t/
•    зашифровать уполучив С
•    возвратить С подписанное цифровой подпись агента и зашифрованноеклиента
•    опубликоватьво время t
С такими требованиями вполне по силам справиться и простому устройству. Использованная литература:
Rivest Ronald L., Shamir A., Wagner David A. Time-lock puzzle and timed-released Crypto. Manuscript, 1996. http://theory.lcs.mit.edu/~rivest/publication.html


Page last update: Fri Jun 10 10:12:31 2005 MSD.
Website last update:
Rambler's Top100 Рейтинг@Mail.ru