Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Пользователи, для которых доверенный орган генерирует закрытые ключи, должны доверять ему полностью и безусловно: они не должны беспокоиться, что доверенный орган может читать всю их закрытую переписку или фальсифицировать их подписи. Следовательно, личностная криптография пригодна лишь для приложений, в которых пользователи могут безусловно доверять друг другу. Предположим, что в некоей организации каждый сотрудник полностью владеет информацией, которой владеют и обмениваются другие пользователи. В этом случае сотрудники могут сами играть роль доверенного органа. Однако возможна ситуация, когда доверенный орган представляет собой набор сущностей, коллективно вычисляющих закрытый ключ (13.3.1) для пользователя. Это открывает возможность для массового вмешательства в частную переписку. В таких системах должен применяться принцип коллективного доверия, описанный в разделе 13.3.7.1.
Если в качестве открытого ключа используется уникальная информация, идентифицирующая пользователя, в криптографической системе, основанной на идентификации, не нужен канал для обмена ключами, изображенный на рис. 7.1 и 10.1. Более того, ключи ке на рис. 7.1 иЬна рис. 10.1 можно заменить строкой, содержащей очевидную информацию, например, глобально распознаваемое имя.
13.3.1 Личностная схема цифровой подписи Шамира
В личностной схеме цифровой подписи Шамира применяются четыре алгоритма.
488
Часть IV. Аутентификаци:
• Setup: этот алгоритм выполняется доверенным органом (с этого момента мы| будем называть его Трентом) и предназначен для формирования глобальных параметров системы и главного ключа.
• User-key-generate: этот алгоритм также выполняется Трентом. На его вхог. поступает главный ключ и произвольная строка битов id (Е {0,1}*, а ег! результатом является закрытый ключ, соответствующий идентификатору id. Этот алгоритм является конкретизацией формулы (13.3.1).
• Sign: алгоритм генерации подписи. На вход этого алгоритма поступает сообщение и закрытый ключ подписывающего лица, а его результатом являете] цифровая подпись.
• Verify: алгоритм верификации подписи. На вход этого алгоритма поступает] пара "сообщение-подпись" и идентификатор id, а его результатом является значение True или False.
Личностная схема цифровой подписи Шамира представлена в алгоритме 13.1. i Если результатом верификации подписи является значение True, значит, Алиса владеет как числом ID - так и его единственным корнем е-й степени по модулю А^, равным числу s. Единственность корня гарантируется условием gcd(e,<?(A0) = l.
Вычисление значения ID • th^M^ не обязательно должно быть сложным. Ha-i пример, можно выбрать случайное число t, вычислить сначала значение h(t \\ М), а затем Ф^м) (mod М) и умножить его на идентификатор ID. Однако, поскольку благодаря применению криптографической функции хэширования число ID ¦ .ф(*\\м) (mod Аг),являетсяраспознаваемым, вычисление корня е-й степени должно представлять собой трудноразрешимую задачу. Следовательно, предполагается, что Алиса должна знать корень е-й степени числа ID (закрытый ключ, сгенерированный Трентом) и применять его при создании цифровой подписи.
Однако мы не приводим формальные и строгие аргументы, гарантирующие невозможность фальсификации в личностной схеме цифровой подписи Шамира. Поскольку устойчивость фальсификации зависит от вычисления числа ID -f/^*"^ (mod AT) и его корня е-й степени по модулю А^, очевидно, она определяется особенностями применяемой функции хэширования (в дополнение к проблеме RSA). Как и в других схемах цифровой подписи, для строгого доказательства стойкости личностной схемы цифровой подписи Шамира необходимо создать формальную модель функции хэширования h. Эта модель приводится в следующей главе.
Глава 13. Аутентификация в криптографии с открытым ключом
489
Алгоритм 13.1. Личностная схема цифровой подписи Шамира Установка системных параметров
Трент устанавливает следующие параметры.
1. N: произведение двух больших простых множителей.
2. е: целое число, удовлетворяющее условию gcd(e,0(Af)) = 1.
(* (N, е) — открытые параметры, предназначенные для системных пользователей. *)
3. d: целое число, удовлетворяющее условию ed = l(mod0(Af)). (* Число d является главным ключом Трента. *)
4. к-.^ху^Ъ^у
(* Число h — стойкая однонаправленная функция хэширования. *) Трент хранит число d как закрытый системный ключ (главный ключ) и обнародует системные параметры (N, е, h).
Генерация ключа пользователя
Пусть ID — однозначно распознаваемый идентификатор Алисы. Выполнив физическую идентификацию Алисы и убедившись в уникальности ее идентификатора ID, Трент выполняет операцию
g<-\Dd(modN).
Генерация подписи
Для подписи сообщения М € {0,1}* Алиса выбирает число г € иЩц и выполняет следующие операции.
t*-re(modA0, st-g^lt ||M)(modA0.
Подписью является пара (s, t). Верификация подписи
Получив сообщение М и подпись (s, t), Боб использует идентификатор Алисы ID для проверки подлинности подписи.
Verify(ID, s, ?, М) = True, если se =
13.3.2 Преимущества личностной схемы цифровой подписи Шамира
