Электронная подпись RSA

Лекция 5. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... Лекция 5. Конспект лекций do.sibsutis.ru 5.1. Электронная подпись RSA После появления криптографии с открытым ключом произошла настоящая революция в современных компьютерных и сетевых технологиях. Появилась возможность решать задачи, которые ранее считались неразрешимыми, а теперь находят широкое применение на практике. В настоящее время при помощи этих технологий ежедневно проводятся расчеты и совершаются сделки на многие миллиарды долларов, рублей, евро и т.п. Одним из важны элементов этих технологий является электронная, или цифровая подпись. Во многих странах и, в частности, в России введены стандарты на электронную (цифровую) подпись, а само это понятие введено в гражданское законодательство. Термин «электронная подпись» более привычен для России, хотя в последнее время все чаще используется принятый в других странах (прежде всего, в США) термин «цифровая подпись», что отражено и в новых российских стандартах. Оба термина означают одно и то же. Прежде чем начать рассмотрение криптографической цифровой подписи, сформулируем три свойства, которым (в идеале) должна удовлетворять любая, в частности, обычная рукописная подпись: 1. Подписать документ может только «законный» владелец подписи (и, следовательно, никто не может подделать подпись). 2. Автор подписи не может от нее отказаться. 3. В случае возникновения спора возможно участие третьих лиц (например, суда) для установления подлинности подписи. Разумеется, цифровая (электронная) подпись также должна обладать всеми этими свойствами, однако лица, подписывающие документы и проверяющие их подлинность, могут находиться за тысячи километров друг от друга и взаимодействовать только через компьютерную сеть. Кроме обычной подписи, в реальной жизни используется так называемая нотариальная подпись, когда специально выделяемое лицо (нотариус) заверяет документы своей подписью и печатью, так что любое другое лицо может удостовериться в их подлинности. Аналог этой подписи также востребован в киберпространстве. Электронная нотариальная подпись реализуется точно так же, как и подпись любого другого лица. В этом разделе мы рассмотрим электронную подпись, базирующуюся на схеме RSA. Если Алиса планирует подписывать документы, то она должна вначале выбрать параметры RSA точно так же, как это описано в разд. 2.б. Для этого Алиса выбирает два больших просты числа Р и Q, вычисляет . Затем она выбирает число d, взаимно простое с , и вычисляет . Наконец, она публикует числа N и d, например, помещает их на своем сайте, ассоциировав со своим именем, и хранит в секрете число с (остальные числа Р, Q и можно забыть, они больше не потребуются). Теперь Алиса готова ставить свои подписи на документах или сообщениях. Пусть Алиса хочет подписать сообщение криптографическую хеш-функцию Стр. 1 из 7 =m1, ... , mn. Тогда вначале она вычисляет 21.03.2022, 22:35 Лекция 5. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... которая ставит в соответствие сообщению число у. Предполагается, что алгоритм вычисления хеш-функции всем известен. Отметим наиболее важное для нас свойство используемой хешфункции: практически невозможно изменить основной текст m1, ... , mn, не изменив y. Поэтому на следующем шаге Алисе достаточно снабдить подписью только число y, и эта подпись будет относиться ко всему сообщению . Алиса вычисляет число (5.1) т.е. она возводит число y в свою секретную степень. Число s это и есть цифровая подпись. Она просто добавляется к сообщению , и тем самым Алиса имеет сформированное подписанное сообщение (5.2) Теперь каждый, кто знает открытые параметры Алисы, ассоциированные с ее именем, т.е. числа N и d, может проверить подлинность ее подписи. Для этого необходимо, взяв подписанное сообщение (5.2), вычислить значение хеш-функции , число (5.3) и проверить выполнение равенства = Утверждение 5.1. Если подпись подлинная, то . = . Д о к а з а т е л ь с т в о. Из (5.3), (5.1) и свойств схемы RSA (см. разд. 2.б) следует Утверждение 5.2. Описанная электронная подпись удовлетворяет всем требованиям, предъявляемым к подписи. Д о к а з а т е л ь с т в о. Проверим первое свойство подписи. Никто не может разложить число N на простые множители (при боль-ших N порядка 1024 бит по состоянию на 2005 год эта задача практически неразрешима). Поэтому, зная N и д невозможно найти с. Действительно, чтобы вычислить , нужно знать , а для этого нужно знать простые множители Р и Q. Таким образом, первое свойство выполнено никто, кроме Алисы, не может знать число с и поэтому не может подписать сообщение. Второе свойство выполнено вследствие первого. Автор подписи не может от нее отказаться, так как никто другой не может «сфабриковать» подпись от его имени. Третье свойство также очевидно в случае спора заинтересованная сторона может предъявить судье все вычисления для их проверки и выяснения истины. П р и м е р 5.1. Пусть Р = 5, Q = 11. Тогда N = 5 • 11 = 55, выбор d возможен, так как (40, 3)= 1. Параметр обобщенного алгоритма Евклида (см. разд. 2.3), с = 27. Стр. 2 из 7 = 4 • 10 = 40. Пусть d = 3. Такой вычисляем с помощью 21.03.2022, 22:35 Лекция 5. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... Пусть, например, Алиса хочет подписать сообщение функции равно, скажем, 13: , для которого значение хеш- В этом случае Алиса вычисляет по (5.1) и формирует подписанное сообщение Теперь тот, кто знает открытые ключи Алисы N = 55 и d = 3, может проверить подлинность подписи. Получив подписанное сообщение, он заново вычисляет значение хеш-функции (если содержание сообщения не изменено, то значение хеш-функции совпадет с тем, которое вычисляла Алиса) и вычисляет по (5.3) Значения и хеш-функции совпали, значит, подпись верна. З а м е ч а н и е. Обратим внимание на то, что одна и та же схема RSA, сгенерированная Алисой, может использоваться для решения двух задач. Во-первых, Алиса может подписывать сообщения, как это было показано в данном разделе, используя свой секретный ключ с. Во-вторых, кто угодно может послать Алисе зашифрованное сообщение (число), расшифровать которое, как это было показано в разд. 2.6, сможет только она, используя для шифрования ее открытый ключ d. 5.2. Стандарты на электронную (цифровую) подпись Во многих странах сегодня существуют стандарты на электронную (цифровую) подпись. В этом разделе мы опишем российский государственный стандарт ГОСТ Р34.10-94 и стандарт США FIPS 186. Российский стандарт, как следует из его обозначения, был принят в 1994 году, американский в 1991. В основе обоих стандартов лежит по сути один и тот же алгоритм, называемый DSA (Digital Signature Algorithm). Мы подробно рассмотрим российскую версию алгоритма, а затем укажем на отличия американской версии. Вначале для некоторого сообщества пользователей выбираются общие несекретные параметры. Прежде всего необходимо найти два простых числа, q длиной 256 бит и р длиной 1024 бита, между которыми выполняется соотношение (5.4) для некоторого целого Ь. Старшие биты в р и q должны быть равны единице. Затем выбирается число а > 1, такое, что Стр. 3 из 7 (5.5) 21.03.2022, 22:35 Лекция 5. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... В результате получаем три общих параметра р, q и а. З а м е ч а н и е. Равенство (5.5) означает, что при возведении а в степени по модулю р показатели = (мы уже проводили обоснование приводятся по модулю q, т.е. подобного феномена при доказательстве утверждения 2.10 на стр. 35). Такое приведение будет постоянно выполняться при генерации и проверке подписи, в результате чего длина показателей степени в рамках рассматриваемого алгоритма никогда не будет превышать 256 бит, что упрощает вычисления. Далее, каждый пользователь выбирает случайно число х, удовлетворяющее неравенству 0 < х < q, и вычисляет (5.6) Число х будет секретным ключом пользователя, а число у открытым ключом. Предполагается, что открытые ключи всех пользователей указываются в некотором несекретном, но «сертифицированном» справочнике, который должен быть у всех, кто собирается проверять подписи. Отметим, что в настоящее время найти х по у практически невозможно при указанной выше длине модуля р. На этом этап выбора параметров заканчивается, и мы готовы к тому, чтобы формировать и проверять подписи. Пусть имеется сообщение следующим образом: , которое необходимо подписать. Генерация подписи выполняется для сообщения m, значение хеш-функции должно 1. Вычисляем значение хеш-функции h = лежать в пределах 0 < h < q (в российском варианте хеш-функция определяется ГОСТом Р34.11-94). 2. Формируем случайное число k, 0 < k < q. . Если оказывается так, что r = 0, то возвращаемся к 3. Вычисляем шагу 2. . Если s = 0, то возвращаемся к шагу 2. 4. Вычисляем 5. Получаем подписанное сообщение . Для проверки подписи делаем следующее. 1. Вычисляем хеш-функцию для сообщения h = . 2. Проверяем выполнение неравенств 0 < r < q, 0 < s < q. 3. Вычисляем , . 4. Вычисляем 5. Проверяем выполнение равенства . . Если хотя бы одна из проверок на шагах 2 и 5 не дает нужного результата, то подпись считается недействительной. Если же все проверки удачны, то подпись считается подлинной. Утверждение 5.3. Если подпись к сообщению была сформирована законно, т.е. обладателем Стр. 4 из 7 21.03.2022, 22:35 Лекция 5. Конспект лекций секретного ключа х, то file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... . Д о к а з а т е л ь с т в о. Запишем следующую цепочку равенств, которая следует непосредственно из описания метода (напомним, что показатели степени приводятся по модулю q): З а м е ч а н и е. Чтобы найти параметр а, удовлетворяющий (5.5), рекомендуется использовать следующий метод. Берем случайное число g > 1 и вычисляем (5.7) Если а > 1, то это то, что нам нужно. Действительно, на основании (5.7) и теоремы Ферма имеем т.е. выполняется равенство (5.5). Если при вычислении по (5.7) мы получаем а = 1 (крайне маловероятный случай), то нужно просто взять другое число g. Пример 5.2. Выберем общие несекретные параметры возьмем g = 10 и вычислим Выберем секретный ключ х = 6 и вычислим открытый ключ Сформируем подпись для сообщения = ЬааааЬ. Пусть для хеш-функции этого сообщения = 3. Возьмем случайно число k = 8. Вычислим Получаем подписанное сообщение Теперь выполним проверку подписи. Если сообщение не изменено, то h = 3. Вычислим Стр. 5 из 7 21.03.2022, 22:35 Лекция 5. Конспект лекций file:///C:/Users/Denis/YandexDisk/%D0%A3%D1%87%D0%B5%D... Мы видим, что , значит подпись верна. Теперь остановимся на отличиях американского стандарта от российского. Они сводятся к следующему. 1. Длина числа q берется равной 160 бит. 2. В качестве хеш-функции используется алгоритм SHA-1. 3. При генерации подписи на шаге 4 параметр s вычисляется по формуле . 4. При проверке подписи на шаге 3 u1 и u2 вычисляются по формулам , . С учетом этих отличий нетрудно переписать всю схему подписи в «американском» стиле. Доказательство корректности алгоритма проводится совершенно аналогично. Задачи и упражнения Во всех задачах будем предполагать, что h(m) = m для всех значений m. 5.1. Построить подпись RSA для сообщения m при следующих параметрах пользователя: См. ответ. 5.2. Для указаннных открытых ключей пользователя RSA проверить подлинность подписанных сообщений: Стр. 6 из 7 21.03.2022, 22:35