001. Криптография и цифровая подпись RSA-sha256 на платформе 1С

Введение

Криптографические системы с открытым ключом используют так называемые односторонние функции, которые обладают следующим свойством:

Под односторонностью понимается не теоретическая однонаправленность, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства, за обозримый интервал времени.

В основу криптографической системы с открытым ключом RSA положена сложность задачи факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования (обратной операции) за разумное время необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего необходимо знать разложение числа на простые множители.

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. public key), так и закрытым ключом (англ. private key). В криптографической системе RSA каждый ключ состоит из пары целых чисел.

Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются взаимно обратными, то есть:

∀{displaystyle forall } допустимых пар открытого и закрытого ключей (p,s){displaystyle (p,s)}

∃{displaystyle exists } соответствующие функции шифрования Ep(x){displaystyle E_{p}(x)} и расшифрования Ds(x){displaystyle D_{s}(x)} такие, что

∀{displaystyle forall } сообщения m∈M{displaystyle min M}, где M{displaystyle M} — множество допустимых сообщений,

m=Ds(Ep(m))=Ep(Ds(m)).{displaystyle m=D_{s}(E_{p}(m))=E_{p}(D_{s}(m)).}

Алгоритм создания открытого и секретного ключей

RSA-ключи генерируются следующим образом[16]:

1) выбираются два различных случайных простых числаp{displaystyle p} и q{displaystyle q} заданного размера (например, 1024 бита каждое);
2) вычисляется их произведение n=p⋅q{displaystyle n=pcdot q}, которое называется модулем;
3) вычисляется значение функции Эйлера от числа n{displaystyle n}:

φ(n)=(p−1)⋅(q−1){displaystyle varphi (n)=(p-1)cdot (q-1)};
4) выбирается целое число e{displaystyle e} (1<e<φ(n){displaystyle 1<e<varphi (n)}), взаимно простое со значением функции φ(n){displaystyle varphi (n)};

число e{displaystyle e} называется открытой экспонентой (англ. public exponent);
обычно в качестве e{displaystyle e} берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например, простые из чисел Ферма: 17, 257 или 65537, так как в этом случае время, необходимое для шифрования с использованием быстрого возведения в степень, будет меньше;
слишком малые значения e{displaystyle e}, например 3, потенциально могут ослабить безопасность схемы RSA.[17];
5) вычисляется число d{displaystyle d}, мультипликативно обратное к числу e{displaystyle e} по модулю φ(n){displaystyle varphi (n)}, то есть число, удовлетворяющее сравнению:

d⋅e≡1(modφ(n)){displaystyle dcdot eequiv 1{pmod {varphi (n)}}}
(число d{displaystyle d} называется секретной экспонентой; обычно оно вычисляется при помощи расширенного алгоритма Евклида);
6) пара (e,n){displaystyle (e,n)} публикуется в качестве открытого ключа RSA (англ. RSA public key);
7) пара (d,n){displaystyle (d,n)} играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.

Атака винера на rsa

В некоторых приложениях требуется ускорить процесс расшифровывания в алгоритме RSA. Поэтому выбирается небольшая расшифровывающая экспонента. В случае когда расшифровывающая экспонента d<N14{displaystyle d<N^{frac {1}{4}}} можно определить d{displaystyle d} за полиномиальное время с помощью атаки Винера[21], опирающейся на непрерывные дроби.

|EN−kd|<12d2.{displaystyle left|{frac {E}{N}}-{frac {k}{d}}right|<{frac {1}{2d^{2}}}.}
Поскольку НОД(k,d)=1,{displaystyle (k,d)=1,} то kd−{displaystyle {frac {k}{d}}-} подходящая дробь в разложении дроби EN{displaystyle {frac {E}{N}}} в непрерывную. Таким образом, можно узнать расшифровывающую экспоненту, поочерёдно подставляя знаменатели подходящих дробей в выражение:
(ME)d=MmodN{displaystyle (M^{E})^{d}=Mmod N}
для некоторого случайного числа M.{displaystyle M.} Получив равенство, найдём d.{displaystyle d.} Общее число подходящих дробей, которое придётся проверить оценивается как O(lnN).{displaystyle O(lnN).}

Генерация ключей

Генерация ключей в схеме цифровой подписи RSА точно такая же, как и генерация ключей в криптографической системе RSА (см.

«B. Стандарты и организации по стандартизации»
). Алиса выбирает два простых числа p и q и вычисляет n = p x q. Алиса вычисляет varphi  (n) = (p - 1) (q - 1)e, для общедоступного ключа и вычисляет d для частного ключа, такое, что e x d = 1 mod varphi   (n)d и публично объявляет n и e.

В схеме цифровой подписи RSA. dявляется частным;. eи. n- общедоступными.

Подписание и проверка

Рис 3.7 показывает схему цифровой подписи RSA.

Подписание. Алиса на основе сообщения создает подпись, используя частный (секретный) ключ, S = Md mod n, и передает сообщение и подпись Бобу.

Проверка. Боб получает М и S. Он применяет общедоступный ключ Алисы к подписи, чтобы создать копию сообщения М’ = Se mod n. Боб сравнивает значение М’ со значением М.

Последняя конгруэнтность справедлива, потому что d x e = 1 mod  psi (n)
«A. ASCII»
).

Пример 3.1

Для безопасности подписи значения p и q должны быть очень большими. Как тривиальный пример, предположим, что Алиса выбирает p = 823 и q = 953 и вычисляет n = 784319. Значение varphi  (n)782544. Теперь она выбирает e = 313 и вычисляет d = 160009. В этой точке генерация ключей закончена. Теперь вообразим, что Алиса хочет передать сообщение со значением M = 19070 Бобу. Она использует свой частный ключ 160009 для того, чтобы подписать сообщение:

Алиса передает сообщение и подпись Бобу. Боб получает сообщение и подпись. Он вычисляет

Боб принимает сообщение, потому что он проверил подпись Алисы.

Атаки подписи RSA

Есть некоторые атаки, к которым Ева может обратиться для подделки схемы цифровой подписи RSА Алисы.

Атака только на ключ. Ева имеет доступ только к открытому ключу Алисы, перехватывает пару ( М, S ) и пробует создать другое сообщение М.’, такое, что М’ = Se mod n.

Эта проблема по сложности решения равна проблеме дискретного логарифма, которую мы рассмотрели в

«A. ASCII»
. Это — экзистенциальная подделка и обычно бесполезна для Евы.

Атака при известном сообщении. Здесь Ева использует мультипликативное свойство RSА. Предположим, что Ева перехватила две пары подписи сообщения — (M1, S1) и (M2, S2), которые используют один и тот же секретный ключ.

S = S1 x S2 mod n =
(M1d x M2d) mod n =
(M1 x M2)d mod n =
Md mod n

Ева может создать М. = M1 x M2 mod n и может создать S. = S1 x S2 mod n ; глупый Боб поверит, что S — подпись Алисы на сообщении М.

Эта атака, которая называется иногда мультипликативной атакой,
проводится очень просто. Однако это — экзистенциальная подделка так, как сообщение, М является произведением двух предыдущих сообщений, созданных Алисой, а не Евой; сообщение М. обычно бесполезно.

Атака по выбранному сообщению. Эта атака также использует мультипликативное свойство RSA. Ева может так или иначе попросить, чтобы Алиса подписала два законных сообщения М1 и М2.

С помощью их она позже создает новое сообщение М. = M1 x M2. Ева может позже утверждать, что Алиса подписала M. Такую атаку называют так же, как и
предыдущую — мультипликативная атака.

Это очень серьезная атака схемы цифровой подписи RSA, потому что это — селективная подделка. (Ева может перемножать М1 и М2, чтобы получить полезный M ).

Подпись RSA на дайджесте сообщения

Как мы обсуждали прежде, подписание дайджеста сообщения и использование сильного алгоритма хэширования имеет несколько преимуществ. В случае RSA процессы подписания и проверки можно сделать намного быстрее, потому что схема цифровой подписи RSА — не что иное, как шифрование с секретным ключом и дешифрование с открытым ключом.

Алиса, подписывающее лицо, при первом использовании согласует
хэш-функцию, чтобы создать дайджест сообщенияD = h(M). Затем она подписывает дайджест, S = Dd mod n.

Сообщение и подпись передают Бобу. Боб, проверяющий, получает сообщение и подпись. Он сначала использует открытый ключ Алисы, чтобы извлечь (файл) дайджест, D’ = Se mod n. Затем он применяет хэш-алгоритм для того, чтобы получить сообщение D = h(M).

Боб теперь сравнивает эти два дайджеста, D и D’. Если они являются сравнимыми по модулю n, он принимает сообщение.

Атаки на подписанные дайджесты RSA

Насколько восприимчива схема цифровой подписи RSA к нападению, когда дайджест уже подписан?

Атака только на ключ. Мы можем иметь три случая этой атаки.

  1. Ева перехватывает пару (S, M) и пробует найти другое сообщение М’, которое создает тот же самый дайджест, h (M) = h (М’). Как мы узнали в

    «Целостность сообщения и установление подлинности сообщения»
    , если алгоритм хэшированияобладает устойчивостью ко второму прообразу,
    эта атака очень трудна.
  2. Ева находит два сообщения, М. и М’, такие, что h(M) = h(M’). Она соблазняет Алису подписать h(M), чтобы найти S ; теперь Ева имеет пару (М’, S), которое прошло подтверждающий тест, но это — подделка. Мы изучали в

    «Целостность сообщения и установление подлинности сообщения»
    , что если алгоритм хэшированияустойчив к коллизиям, эта атака очень трудна.
  3. Ева случайным подбором может найти дайджест сообщения D, который может соответствовать случайной подписи S. Она тогда находит сообщение М, такое, что D = h (M). Как мы узнали в

    «Целостность сообщения и установление подлинности сообщения»
    , если хэш-функция устойчива к прообразу, эта атака очень трудно осуществима.
Читайте также:  Загрузка контрактов из ЕИС

Атака при известном сообщении. Предположим, что Ева имеет две пары подписи сообщения — (М1,S1) и (М2, S2), которые были созданы с использованием одного и того же секретного ключа.

Ева вычисляет S = S1 x S2. Если она сможет найти сообщение М, такое, что h(M) = h(M1) x h(M2), она сможет подделать новое сообщение.

Атаки по выбранному сообщению. Ева может попросить, чтобы Алиса подписала два законных сообщения — М1,и М2 для нее. Она может создать новую подпись S = S1 x S2.

Так как Ева может вычислить h(M) = h(M1) x h(M2), если она может найти сообщение M данному h (M), это новое сообщение — подделка. Однако нахождение М по данному h (M) -очень трудный процесс, если алгоритм хэшированияустойчив к прообразу.

Когда дайджест подписан непосредственно вместо сообщения, восприимчивость. схемы цифровой подписи RSAзависят от свойств алгоритма хэширования.

Доказательство с помощью малой теоремы ферма.

Доказательство правильности RSA основано на маленькой теореме Ферма , утверждающей, что a p — 1 ≡ 1 (mod p ) для любого целого числа a и простого числа p , не деля a .

Мы хотим показать, что

( м е ) d ≡ м ( мод п q ) { Displaystyle (м ^ {е}) ^ {д} экв м { pmod {pq}}}

для любого целого числа m, когда p и q — различные простые числа, а e и d — натуральные числа, удовлетворяющие ed ed 1 (mod λ ( pq )) .

Поскольку λ ( pq ) = lcm ( p — 1, q — 1) по построению делится как на p — 1, так и на q — 1 , мы можем написать

е d — 1 знак равно час ( п — 1 ) знак равно k ( q — 1 ) { Displaystyle ed-1 = час (п-1) = к (д-1)}

для некоторых неотрицательных целых чисел h и k .

Чтобы проверить , совпадают ли два числа, такие как m ed и m , по модулю  pq , достаточно (и фактически эквивалентно) проверить, что они совпадают по модулю  p и mod  q по отдельности.

Чтобы показать m ed ≡ m (mod p ) , рассмотрим два случая:

  1. Если m ≡ 0 (mod p ) , m делится на p . Таким образом, m ed кратно p . Так m ed ≡ 0 ≡ m (mod p ) .
  2. Если m 0 (mod p ) ≢ { Displaystyle not Equiv} ,
м е d знак равно м е d — 1 м знак равно м час ( п — 1 ) м знак равно ( м п — 1 ) час м ≡ 1 час м ≡ м ( мод п ) , { displaystyle m ^ {ed} = m ^ {ed-1} m = m ^ {h (p-1)} m = (m ^ {p-1}) ^ {h} m Equiv 1 ^ {h } м экв м { pmod {p}},}
где мы использовали малую теорему Ферма для замены m p −1 mod p на 1.

Проверка того, что m ed ≡ m (mod q ) проходит совершенно аналогично:

  1. Если m ≡ 0 (mod q ) , m ed делится на q . Итак, m ed ≡ 0 ≡ m (mod q ) .
  2. Если m 0 (mod q ) ≢ { Displaystyle not Equiv} ,
м е d знак равно м е d — 1 м знак равно м k ( q — 1 ) м знак равно ( м q — 1 ) k м ≡ 1 k м ≡ м ( мод q ) . { displaystyle m ^ {ed} = m ^ {ed-1} m = m ^ {k (q-1)} m = (m ^ {q-1}) ^ {k} m Equiv 1 ^ {k } m Equiv m { pmod ?}.}

Это завершает доказательство того, что для любого целого числа m и целых чисел e , d таких, что ed ≡ 1 (mod λ ( pq )) ,

( м е ) d ≡ м ( мод п q ) . { displaystyle (m ^ {e}) ^ {d} Equiv m { pmod {pq}}.}

Заметки:

Использование китайской теоремы об остатках для ускорения расшифрования

При расшифровании или подписывании сообщения в алгоритме RSA показатель вычисляемой степени будет довольно большим числом (порядка 1000 бит). Поэтому требуется алгоритм, сокращающий количество операций. Так как числа p{displaystyle p} и q{displaystyle q} в разложении N=pq{displaystyle N=pq} известны владельцу закрытого ключа, то можно вычислить:
mp=Cdmodp=Cdmodp−1modp,{displaystyle m_{p}=C^{d}{bmod {p}}=C^{d{bmod {p-1}}}{bmod {p}},}mq=Cdmodq=Cdmodq−1modq.{displaystyle m_?=C^{d}{bmod ?}=C^{d{bmod {q-1}}}{bmod ?}.}Поскольку p{displaystyle p} и q{displaystyle q} — числа порядка 2512,{displaystyle 2^{512},} на эти действия потребуется два возведения числа в 512-битовую степень по модулю 512-битового числа. Это существенно (для 1024 бит тестирование показало в 3 раза) быстрее, чем одно возведение в 1024-битовую степень по модулю 1024-битового числа.
Далее осталось восстановить m{displaystyle m} по mp{displaystyle m_{p}} и mq,{displaystyle m_?,} что можно сделать с помощью китайской теоремы об остатках[21].

История

Опубликованная в ноябре 1976 года статья Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» (англ. New Directions in Cryptography)[4] перевернула представление о криптографических системах, заложив основы криптографии с открытым ключом.

Разработанный впоследствии алгоритм Диффи — Хеллмана позволял двум сторонам получить общий секретный ключ, используя незащищенный канал связи. Однако этот алгоритм не решал проблему аутентификации. Без дополнительных средств пользователи не могли знать наверняка, с кем именно они сгенерировали общий секретный ключ.

Изучив эту статью, трое учёных Рональд Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института (MIT) приступили к поискам математической функции, которая бы позволяла реализовать сформулированную Уитфилдом Диффи и Мартином Хеллманом модель криптографической системы с открытым ключом.

После работы над более чем 40 возможными вариантами им удалось найти алгоритм, основанный на различии в том, насколько легко находить большие простые числа и насколько сложно раскладывать на множители произведение двух больших простых чисел, получивший впоследствии название RSA. Система была названа по первым буквам фамилий её создателей.

В августе 1977 года в колонке «Математические игры» Мартина Гарднера в журнале Scientific American с разрешения Рональда Ривеста[5] появилось первое описание криптосистемы RSA[6]. Читателям также было предложено дешифровать английскую фразу, зашифрованную описанным алгоритмом:

В качестве открытых параметров системы были использованы числа n=

(129 десятичных знаков, 425

, также известно как

) и e=9007. За расшифровку была обещана награда в 100 долларов США. По заявлению Ривеста, для факторизации числа потребовалось бы более 40 квадриллионов лет

[7][3]

. Однако чуть более, чем через 15 лет, 3 сентября

было объявлено о запуске проекта

с координацией через электронную почту по нахождению сомножителей числа RSA-129 и решению головоломки. На протяжении полугода более 600 добровольцев из 20 стран жертвовали процессорное время 1600 машин (три из которых были факс-машинами

[источник не указан 1971 день]

). В результате были найдены простые множители и расшифровано исходное сообщение, которое представляет собой фразу «

THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE (англ.)

» («Волшебные слова — это брезгливый

[8][9]

. Полученную награду победители пожертвовали в

После публикации Мартина Гарднера полное описание новой криптосистемы любой желающий мог получить, выслав по почте запрос Рональду Ривесту с приложенным конвертом с обратным адресом и марками на 35 центов.[6] Полное описание новой криптосистемы было опубликовано в журнале «Communications of the ACM» в феврале 1978 года[10].

Заявка на патент была подана 14 декабря 1977 года, в качестве владельца был указан MIT. Патент 4405829 был выдан 20 сентября 1983 года, а 21 сентября 2000 года срок его действия истёк[11].

В 1982 году Ривест, Шамир и Адлеман организовали компанию RSA Data Security (англ.) (в настоящий момент — подразделение EMC).

В 1989 году RSA, вместе с симметричным шифром DES, упоминается в RFC 1115, тем самым начиная использование алгоритма в зарождающейся сети Internet[13], а в 1990 году использовать алгоритм начинает министерство обороны США[14].

В ноябре 1993 года открыто публикуется версия 1.5 стандарта PKCS1 (англ.), описывающего применение RSA для шифрования и создания электронной подписи.

В декабре 1997 года была обнародована информация, согласно которой британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал криптосистему, аналогичную RSA в 1973 году[15].

Криптоанализ rsa

Стойкость алгоритма основывается на сложности вычисления обратной функции к функции шифрования[22]

c=E(m)=memodn{displaystyle c=E(m)=m^{e}mod n}.

Для вычисления m{displaystyle m} по известным c,e,n{displaystyle c,e,n} нужно найти такой d{displaystyle d}, чтобы

e⋅d≡1(modφ(n)),{displaystyle ecdot dequiv 1{pmod {varphi (n)}},}

то есть

d≡e−1(modφ(n)).{displaystyle dequiv e^{-1}{pmod {varphi (n)}}.}

Вычисление обратного элемента по модулю не является сложной задачей, однако злоумышленнику неизвестно значение φ(n){displaystyle varphi (n)}. Для вычисления функции Эйлера от известного числа n{displaystyle n} необходимо знать разложение этого числа на простые множители. Нахождение таких множителей и является сложной задачей, а знание этих множителей — «потайной дверцей» (англ. backdoor), которая используется для вычисления d{displaystyle d} владельцем ключа. Существует множество алгоритмов для нахождения простых сомножителей, так называемой факторизации, самый быстрый из которых на сегодняшний день — общий метод решета числового поля, скорость которого для k-битного целого числа составляет

exp⁡((c o(1))k13log23⁡k){displaystyle exp((c o(1))k^{frac {1}{3}}log ^{frac {2}{3}}k)} для некоторого c<2{displaystyle c<2}.

В 2021 году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит. Нахождение простых сомножителей осуществлялось общим методом решета числового поля[23].

По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года[24].

Кроме того, при неправильной или неоптимальной реализации или использовании алгоритма возможны специальные криптографические атаки, такие как атаки на схемы с малой секретной экспонентой или на схемы с общим выбранным значением модуля.

Литература

  • Diffie W., Hellman M. E.New Directions in Cryptography (англ.) // IEEE Trans. Inf. Theory / F. KschischangIEEE, 1976. — Vol. 22, Iss. 6. — P. 644—654. — ISSN 0018-9448; 1557-9654doi:10.1109/TIT.1976.1055638
  • Gardner M.A New Kind of Cipher that Would Take Millions of Years to Break (англ.) // Sci. Amer.NYC: NPG, 1977. — Vol. 237, Iss. 2. — P. 120—124. — ISSN 0036-8733; 1946-7087doi:10.1038/SCIENTIFICAMERICAN0877-120
  • Rivest R., Shamir A., Adleman L.A method for obtaining digital signatures and public-key cryptosystems (англ.) // Commun. ACMNYC, USA: ACM, 1978. — Vol. 21, Iss. 2. — P. 120—126. — ISSN 0001-0782; 1557-7317doi:10.1145/359340.359342
  • Menezes A. J., Oorschot P. v., Vanstone S. A.Handbook of Applied Cryptography (англ.)CRC Press, 1996. — 816 p. — (Discrete Mathematics and Its Applications) — ISBN 978-0-8493-8523-0
  • Boneh D.Twenty Years of attacks on the RSA Cryptosystem (англ.) // Notices Amer. Math. Soc. / F. MorganAMS, 1999. — Vol. 46, Iss. 2. — P. 203–213. — ISSN 0002-9920; 1088-9477
  • Bakhtiari M., Maarof M. A.Serious Security Weakness in RSA Cryptosystem (англ.) // IJCSI — 2021. — Vol. 9, Iss. 1, No 3. — P. 175—178. — ISSN 1694-0814; 1694-0784

Пример

Вот пример шифрования и дешифрования RSA. Используемые здесь параметры искусственно малы, но можно также использовать OpenSSL для генерации и проверки реальной пары ключей .

Читайте также:  Универсальная электронная карта гражданина (УЭК)

  1. Выберите два различных простых числа, например
    п знак равно 61 год { displaystyle p = 61} а также q знак равно 53 { displaystyle q = 53}
  2. Вычислить n = pq, давая
    п знак равно 61 год × 53 знак равно 3233 { Displaystyle п = 61 раз 53 = 3233}
  3. Вычислите общую функцию произведения Кармайкла как λ ( n ) = lcm ( p — 1, q — 1), что дает
    λ ( 3233 ) знак равно lcm ⁡ ( 60 , 52 ) знак равно 780 { displaystyle lambda (3233) = operatorname {lcm} (60,52) = 780}

  4. Выберите любое число 1 < e <780 , которое взаимно просто с 780. Выбор простого числа для e оставляет нам только проверить, не является ли e не делителем 780.
    Позволять е знак равно 17 { displaystyle e = 17}
  5. Вычислите d , модульное мультипликативное обратное к e (mod λ ( n )), в результате получим,
    в виде 1 знак равно ( 17 × 413 ) мод 7 80. { displaystyle 1 = (17 times 413) { bmod {7}} 80.}

Открытый ключом является ( п = 3233 , е = 17 ). Для сообщения m с открытым текстом с заполнением функция шифрования

c ( м ) знак равно м е мод п c ( м ) знак равно м 17 мод 3 233 { displaystyle { begin {align} c (m) & = m ^ {e} { bmod {n}} \ c (m) & = m ^ {17} { bmod {3}} 233 end {выровнено}}}

Секретный ключ является ( п = 3233 , д = 413 ). Для зашифрованного зашифрованного текста c функция дешифрования

м ( c ) знак равно c d мод п м ( c ) знак равно c 413 мод 3 233 { Displaystyle { begin {align} m (c) & = c ^ {d} { bmod {n}} \ m (c) & = c ^ {413} { bmod {3}} 233 end {выровнено}}}

Например, чтобы зашифровать m = 65 , мы вычисляем

c знак равно 65 17 мод 3 233 знак равно 2790 { displaystyle c = 65 ^ {17} { bmod {3}} 233 = 2790}

Для расшифровки c = 2790 вычисляем

м знак равно 2790 413 мод 3 233 знак равно 65 { displaystyle m = 2790 ^ {413} { bmod {3}} 233 = 65}

Оба этих вычисления можно эффективно вычислить с помощью алгоритма возведения в квадрат и умножения для модульного возведения в степень .

В реальных ситуациях выбранные простые числа будут намного больше; в нашем примере было бы тривиально разложить n , 3233 (полученное из свободно доступного открытого ключа) обратно на простые числа p и q . e , также из открытого ключа, затем инвертируется, чтобы получить d , таким образом получая закрытый ключ.

Практические реализации используют китайскую теорему об остатках для ускорения вычислений с использованием модуля факторов (mod pq, используя mod p и mod q ).

Значения d p , d q и q inv , которые являются частью закрытого ключа, вычисляются следующим образом:

d п знак равно d мод ( п — 1 ) знак равно 413 мод ( 61 год — 1 ) знак равно 53 d q знак равно d мод ( q — 1 ) знак равно 413 мод ( 53 — 1 ) знак равно 49 q inv знак равно q — 1 мод п знак равно 53 — 1 мод 6 1 знак равно 38 ⇒ ( q inv × q ) мод п знак равно 38 × 53 мод 6 1 знак равно 1 { displaystyle { begin {align} d_ {p} = {} & d { bmod {(}} p-1) = 413 { bmod {(}} 61-1) = 53 \ d_ ? = {} & d { bmod {(}} q-1) = 413 { bmod {(}} 53-1) = 49 \ q _ { text {inv}} = {} & q ^ {- 1} { bmod {p}} = 53 ^ {- 1} { bmod {6}} 1 = 38 \ Rightarrow {} & (q _ { text {inv}} times q) { bmod {p}} = 38 times 53 { bmod {6}} 1 = 1 конец {выровнено}}}

Вот как d p , d q и q inv используются для эффективного дешифрования. (Шифрование эффективно при выборе подходящей пары d и e )

м 1 знак равно c d п мод п знак равно 2790 53 мод 6 1 знак равно 4 м 2 знак равно c d q мод q знак равно 2790 49 мод 5 3 знак равно 12 час знак равно ( q inv × ( м 1 — м 2 ) ) мод п знак равно ( 38 × — 8 ) мод 6 1 знак равно 1 м знак равно м 2 час × q знак равно 12 1 × 53 знак равно 65 { displaystyle { begin {align} m_ {1} & = c ^ {d_ {p}} { bmod {p}} = 2790 ^ {53} { bmod {6}} 1 = 4 \ m_ { 2} & = c ^ {d_ ?} { bmod ?} = 2790 ^ {49} { bmod {5}} 3 = 12 \ h & = (q _ { text {inv}} раз (m_ {1} -m_ {2})) { bmod {p}} = (38 times -8) { bmod {6}} 1 = 1 \ m & = m_ {2} h times q = 12 1 times 53 = 65 end {align}}}

Примечания

  1. Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its FoundersSociety for Industrial and Applied Mathematics.
  2. Introduction to Modern Cryptography (англ.) — 2 — CRC Press, 2021. — P. 411. — 583 p. — ISBN 978-1-4665-7026-9
  3. 12Bakhtiari, Maarof, 2021, p. 175.
  4. Diffie, Hellman, 1976.
  5. A Quarter Century of Recreational Mathematics, by Martin Gardner (англ.) (недоступная ссылка). Scientific American. — «Ronald L. Rivest of the Massachusetts Institute of Technology allowed me to be the first to reveal—in the August 1977 column—the «publickey» cipher system that he co-invented». Дата обращения: 3 марта 2021.Архивировано 23 июня 2021 года.
  6. 12Gardner, 1977.
  7. Bruce Schneier.Factoring — State of the Art and Predictions (англ.) (недоступная ссылка) (12 February 1995). Дата обращения: 3 марта 2021.Архивировано 23 июня 2021 года.
  8. Donald T. Davis.A Discussion of RSA-129 Activity (англ.) (недоступная ссылка) (25 November 2003). Дата обращения: 3 марта 2021.Архивировано 23 июня 2021 года.
  9. Чмора А. Л.4.6.4. Силовая атака на основе распределенных вычислений // Современная прикладная криптография. — 2002. — 2000 экз. — ISBN 5-85438-046-3.
  10. Rivest, Shamir, Adleman, 1978.
  11. Ronald L. Rivest et al. Cryptographic Communications System and Method
  12. Adam Back.PGP Timeline (англ.) (недоступная ссылка). Дата обращения: 3 марта 2021.Архивировано 23 июня 2021 года.
  13. J. Linn.Privacy Enhancement for Internet Electronic Mail: Part III — Algorithms, Modes, and Identifiers (англ.) (недоступная ссылка) (август 1989). Дата обращения: 18 марта 2021.Архивировано 23 июня 2021 года.
  14. RSA Security Inc. Company history (англ.) (недоступная ссылка). FundingUniverse. Дата обращения: 18 марта 2021.Архивировано 23 июня 2021 года.
  15. C. C. Cocks A note on «non-secret encryption»Архивировано 4 августа 2009 года. (англ.) 20 ноября 1973
  16. 123Menezes, Oorschot, Vanstone, 1996, 8.2. RSA public-key encryption.
  17. Boneh, 1999.
  18. 12Брюс Шнайер. Прикладная криптография 2-е издание протоколы, алгоритмы и исходные тексты на языке C
  19. Rivest, Shamir, Adleman, 1978, pp. 7—8.
  20. Rivest, Shamir, Adleman, 1978, p. 8.
  21. 123 Н. СМАРТ Мир программирования Криптография — изд. Техносфера, Москва 2006
  22. Ян С. Й. Криптоанализ RSA. — М.—Ижевск: НИЦ «Регулярная и хаотическая динамика», Ижевский институт компьютерных исследований, 2021. — 312 с.
  23. Анонс факторизации RSA-768 (англ.)
  24. Факторизация RSA-768 (англ.)
  25. Dates for Phasing out MD5-based signatures and 1024-bit moduli

Скорость работы алгоритма rsa

Поскольку генерация ключей происходит значительно реже операций, реализующих шифрование, расшифрование, а также создание и проверку цифровой подписи, задача вычисления a=bcmodn{displaystyle a=b^{c}{bmod {n}}} представляет основную вычислительную сложность. Эта задача может быть разрешена с помощью алгоритма быстрого возведения в степень. С использованием этого алгоритма для вычисления memodn{displaystyle m^{e}{bmod {n}}} требуется O(ln⁡e){displaystyle Oleft(ln eright)} операций умножения по модулю[20].
Чтобы проанализировать время выполнения операций с открытым и закрытым ключами, предположим, что открытый ключ {e,n}{displaystyle left{e,nright}} и закрытый ключ {d,n}{displaystyle left{d,nright}} удовлетворяют соотношениям log2⁡e=O(1){displaystyle log _{2}e=O(1)}, log2⁡d≤β{displaystyle log _{2}dleq beta }. Тогда в процессах их применения выполняется соответственно O(1){displaystyle Oleft(1right)} и O(β){displaystyle Oleft(beta right)} умножений по модулю.

Таким образом время выполнения операций растёт с увеличением количества ненулевых битов в двоичном представлении открытой экспоненты e. Чтобы увеличить скорость шифрования, значение e часто выбирают равным 17, 257 или 65537 — простым числам, двоичное представление которых содержит лишь две единицы:

По эвристическим оценкам длина секретной экспоненты d{displaystyle d}, нетривиальным образом зависящей от открытой экспоненты e{displaystyle e} и модуля n{displaystyle n}, с большой вероятностью близка к длине n{displaystyle n}. Поэтому расшифрование данных идёт медленнее, чем шифрование, а проверка подписи – быстрее, чем её создание.

Алгоритм RSA намного медленнее, чем AES и другие алгоритмы, использующие симметричные блочные шифры.

Стандарт цифровой подписи (dss)

Стандарт цифровой подписи (DSS — Digital Signature Standard) был принят национальным Институтом Стандартов и Технологии (NIST) в 1994 г. NIST издал DSS как FIPS-186 (FEDERAL INFORMATION PROCESSING STANDARD 186).

DSS применяет алгоритм цифровой подписи (DSA), основанный на схеме Эль-Гамаля, с использованием некоторых идей из схемы Шнорра. DSS критиковался со времени его издания.

В процессе подписания две функции создают две подписи; в процессе проверки выход одной функции сравнивается с первой подписью для проверки. Это подобно схеме Шнорра, но входы различны. Другое отличие: эта схема использует дайджест сообщения (не само сообщение) как часть входов к функциям 1 и 3.

Интересно то, что схема применяет два общедоступных модуля: p и q. Функции 1 и 3 используют оба модуля p и q, функция 2 — только q. Детали входов и функций коротко рассматриваются ниже.

Генерация ключей

Перед подписанием сообщения к любому объекту Алиса должна генерировать ключи и объявить общедоступные ключи.

  1. Алиса выбирает простое число длиной p. между 512 и 1024 битами. Число битов в p должно быть кратно числу 64.
  2. Алиса выбирает простое число на 160 битов q с таким условием, чтобы оно делилось на (p — 1).
  3. Алиса использует две группы умножения, <Zp*, x > и <Zq* ,x > ; вторая — подгруппа первой.
  4. Алиса создает e1, такое, чтобы оно было q -тым корнем 1 по модулю p (e1p = 1 mod p). Она поступает так: выбирает элемент в Zp, e, и вычисляет e1 = e(p-1)/q mod p.
  5. Алиса выбирает d как секретный ключ и вычисляет e2 = e1d
  6. Общедоступный ключ Алисы — (e1, e2, p, q), ее секретный ключ — (d).

Подписание и проверка

Рисунок 3.14 показывает схему DSS.

Подписание. Ниже показаны шаги подписания сообщения.

  1. Алиса выбирает случайное число (1 <= r <= q). Обратите внимание, что хотя открытые и секретные ключи могут быть выбраны один раз и использоваться для того, чтобы подписать много сообщений, Алиса должна выбирать каждый раз новый r, когда она должна подписать новое сообщение.
  2. Алиса вычисляет первую подпись S1 = (e1 mod p) mod q. Обратите внимание: значение первой подписи не зависит от М (сообщения).
  3. Алиса создает дайджест сообщенияh (M).
  4. Алиса вычисляет вторую подпись S2 = (h(M) dS1)r-1mod q. Обратите внимание, что вычисление S2 делается по модулю q.
  5. Алиса посылает M, S1 и S2 Бобу.

Проверка (верификация). Для проверки сообщения обычно применяются следующие шаги, когда получены М, S1 и S2.

  1. Боб проверяет S1 0 < S1 < q.
  2. Боб проверяет S2 0 < S2 < q.
  3. Боб вычисляет дайджест М, применяя алгоритм хэширования, используемый Алисой.
  4. Боб вычисляет V = [(e1h(M)/S2 e2S1/S2) mod p] mod q.
  5. Если S конгруэнтен V, сообщение принимается; иначе — отклоняется.

Пример 3.5

Алиса выбирает q = 101 и p = 8081. Алиса выбирает e0 = 3 и вычисляет e1 = e0(p-1)/q mod p = 6968.

Алиса выбирает d = 61 в качестве секретного ключа и вычисляет e2 = e1d mod p = 2038. Теперь Алиса может передать сообщение Бобу. Предположим, что h (M) = 5000, и Алиса выбирает r = 61:

Поскольку Sj и V являются подходящими, Боб принимает сообщение.

Сравнение DSS и RSА

Вычисление DSS-подписи быстрее, чем вычисление подписей RSА, при использовании того же самого p.

Сравнение DSS и схемы Эль-Гамаля

DSS-подпись — меньше, чем подписи в схеме Эль-Гамаля, потому что q меньше, чем p.

Схема цифровой подписи шнорра

Проблема схемы цифровой подписи Эль-Гамаля — в том, что p должно быть очень большим, чтобы сделать трудной проблему дискретного логарифмаZp*.

Рекомендуется длина p по крайней мере 1024 битов. Можно сделать подпись размером 2048 бит. Чтобы уменьшить размер подписи, Шнорр предложил новую схему, основанную на схеме Эль-Гамаля , но с уменьшенным размером подписи.
рис. 3.11 дает общую идею схемы цифровой подписи Шнорра.

В процессе подписания две функции создают две подписи; в процессе проверки выход одной функции сравнивается с первой подписью для проверки.
рис. 3.11 показывает входы к каждой функции. Важно то, что схема использует два модуля: p и q.

Генерация ключей

Перед подписанием сообщения Алиса должна генерировать ключи и объявить всем общедоступные ключи.

  1. Алиса выбирает простое число p, которое обычно равно по длине 1024 битам.
  2. Алиса выбирает другое простое число q, которое имеет тот же самый размер, что и дайджест, созданный функцией криптографического хэширования (в настоящее время 160 битов, но это может измениться в будущем). Простое число q должно делиться на (p — 1). Другими словами, (p — 1) = 0 mod q.
  3. Алиса выбирает e1, q -тый
    корень которого был бы равен 1 mod p. Чтобы сделать это, Алиса выбирает примитивный элемент в Zp, e(см.
    «G. Список неприводимых и примитивных полиномов»
    ) и вычисляет e1 = e(p-1)/q mod p.
  4. Алиса выбирает целое число, d, как свой секретный ключ.
  5. Алиса вычисляет e2 = e1d mod p.
  6. Общедоступный ключ Алисы — (e1, e2, p, q), ее секретный ключ — (d).

В схеме цифровой подписи Шнорраобщедоступный ключ Алисы — (e1, e2, p, q) ; ее секретный ключ — (d).

Подписание и проверка

Рисунок 3.12 показывает схему цифровой подписи Шнорра.

Подписание

  1. Алиса выбирает случайное число r. Обратите внимание, что открытый и секретный ключи могут использоваться для подписи многих сообщений. Но Алиса должна изменять r каждый раз,
    когда она передает новое сообщение. Обратите внимание также на то, что r должен иметь значение между 1 и q.
  2. Алиса вычисляет первую подпись S1 = h(M | e1r mod p) . Сообщение присоединяется (конкатенируется) спереди к значению e1r mod p, затем применяется хэш-функция, чтобы создать дайджест. Обратите внимание, что хэш-функция непосредственно не применяется к сообщению, но вместо этого она получается из последовательного соединения М. и e1r mod p.
  3. Алиса вычисляет вторую подпись S2 = r d x S1 mod q. Обратите внимание, что эта часть — вычисление S2 — делается в арифметике по модулю q.
  4. Алиса передает М., S1 и S2.

Верификация (проверка) сообщения. Приемник, например Боб, получает М., S1 и S2.

  1. Боб вычисляет V = h (М | e1S2 e2-S1 mod p).
  2. Если S2 конгруэнтно V по модулю p, сообщение принято; иначе оно отклоняется.

Пример 3.4

Вот тривиальный пример. Предположим, что мы выбираем q = 103 и p = 2267. Обратите внимание на то, что p = 22 x q 1. Мы выбираем e0 = 2, которое является элементом в Z2267*.

Мы выбираем d = 30, тогда e2 = 35430 mod 2267 = 1206. Секретный ключ Алисы -теперь — (d), ее общедоступный ключ — (e1,e2,p,q).

Алиса хочет передать сообщение М. Она выбирает r = 11 и вычисляет er = 35411 = 630 mod 2267. Предположим, что сообщение — 1000, и конкатенация (последовательное соединение) означает 1000630.

Также предположим, что хэширование этого значения дает дайджест h (1000630) = 200. Это означает S1 = 200. Алиса вычисляет S2 = r d x S1 mod q = 11 1026 200 mod 103 = 11 24 = 35.

Подделка по схеме подписи Шнорра

Похоже, что все атаки на схему Эль-Гамаля могут быть применены к схеме Шнорра. Однако схема Шнорра находится в лучшем положении, потому что S1 = h (М.

Схема цифровой подписи эль-гамаля

Криптосистема Эль-Гамаля была обсуждена в
«B. Стандарты и организации по стандартизации»
. Схема цифровой подписи Эль-Гамаля использует те же самые ключи, но алгоритм различен.
рис. 3.9 дает общую идею схемы цифровой подписи Эль-Гамаля.

В процессе подписания две функции создают две подписи. На стороне подтверждения обрабатывают выходы двух функций и сравнивают между собой для проверки. Обратите внимание, что одна и та же функция применяется и для подписания, и для проверки, но использует различные входы.

Рисунок показывает входы каждой функции. Сообщение — часть входа, для обеспечения функционирования при подписании; оно же — часть входа к функции 1 при подтверждении. Обратите внимание, что вычисления в функциях 1 и 3 проводятся по модулю p, а функции 2 — по модулю p — 1.

Генерация ключей

Процедура генерации ключей здесь точно такая же, как та, которая используется в криптографической системе. Выберем достаточно большое простое число p, чтобы в поле Z p* проблема дискретного логарифма была достаточно трудной.

Пусть e1 — простой элемент в Z p*. Алиса выбирает свой секретный ключ d, чтобы он был меньше, чем p — 1. Она вычисляет e2 = e1d.

Всхеме цифровой подписи Эль-Гамаля(e1, e2, p)- открытый ключ Алисы; d-секретный ключ Алисы.

Подтверждение и проверка

Рисунок 3.10 показывает схему цифровой подписи Эль-Гамаля.

Подписывающаяся Алиса может подписать дайджест сообщения, направленный к любому объекту, включая Боба.

  1. Алиса выбирает секретное случайное число r. Обратите внимание, что хотя открытые и секретные ключи могут использоваться неоднократно, Алиса каждый раз нуждается в новом r, когда она подписывает новое сообщение.
  2. Алиса вычисляет первую подпись S1 = er mod p.
  3. Алиса вычисляет вторую подпись S2 = (М — d x S1) x r-1 mod (p — 1),где r — мультипликативная инверсия r по модулю p — 1.
  4. Алиса передает М, S1 и S2 Бобу.

Проверка. Объект, например Боб, получает М, S1 и S2 и может проверить их следующим образом.

  1. Боб проверяет, что 0 < S1 < p.
  2. Боб проверяет, что 0 < S2 < p — 1.
  3. Боб вычисляет V1 = e1M mod p.
  4. Боб вычисляет V2 = e2S1 x e2S2 mod p.
  5. Если V1 является конгруэнтным V2, сообщение принято; иначе оно будет отклонено. Мы можем доказать правильность этого критерия проверки, используя e2 = e1d и S1 = e1r:

    V_{1} equiv  V_{2} (mod  p) to  e_{1}^{M}  equiv  e_{2}^{M} times S_{1}^{M} mod  p  equiv  (e_{1}^{d1})^{S1} times  (e_{1}^{r})^{S2} (mod  p)  equiv  e_{1}^{dS1 rS2} mod  p

    Мы имеем e_{1}^{M } equiv  e_{1}^{dS1   rS2} mod  p

    Поскольку e1первообразный корень, может быть доказано, что вышеупомянутое сравнение справедливо тогда и только тогда, когда M equiv  [dS_{1}   rS_{2}] mod   (p-1)  S_{2} equiv  [(M - d  times  S_{1}) times r^{-1}] mod  (p-1), и результат сравнения есть тот же самый S2, с которого мы начали процесс подписания.

Пример 3.2

Ниже приводится тривиальный пример. Алиса выбрала p = 3119, e1 = 2, d = 127 и вычислила e2 = 2127 mod 3119 = 1702.

Она выбрала r равным 307. Она объявила e1, e2 и p ; она сохранила в тайне d. Далее показано, как Алиса может подписать сообщение.

Алиса передает М, S1 и S2 Бобу. Боб использует открытый ключ, чтобы вычислить, что сообщение подписано Алисой, потому что никто, кроме Алисы, не имеет секретного ключа d.

Поскольку V1 и V2 являются конгруэнтными, Боб принимает сообщение, и он предполагает, что сообщение было подписано Алисой, потому что никто, кроме нее, не имеет секретного ключа Алисы d.

Пример 3.3

Теперь вообразите, что Алиса хочет передать другое сообщение, М = 3000, Тэду. Она выбирает новое r = 107. Алиса передает М., S1 и S2 Тэду.

Поскольку V1 и V2 являются конгруэнтными, Тэд принимает сообщение; он предполагает, что сообщение подписано Алисой, потому что никто, кроме нее, не имеет секретного ключа Алисы d.

Подделка цифровой подписи в схеме Эль-Гамаля

Схема цифровой подписи Эль-Гамаля уязвима к экзистенциальной подделке, но селективную подделку на этой схеме сделать очень трудно.

Подделка только ключа. В этом типе подделки Ева имеет доступ только к открытому ключу. Возможны два варианта:

  1. Ева имеет заранее заданное сообщение М. Она должна подделать подпись Алисы на этом сообщении. Ева должна найти две правильных подписи S1 и S2 для этого сообщения. Это — селективная подделка.
  2. Ева может методом случайного подбора найти три значения, М, S1 и S2, такие, что подпись первого используется для второго. Если Ева может найти два новых параметра x и y, такие, что М = xS2 mod (p — 1) и S1 = -y S2 mod (p — 1), то она может подделать сообщение, но серьезной выгоды не получит, поскольку это — экзистенциальная подделка.

Подделка при известном сообщении. Если Ева перехватила сообщение М и его две подписи S1 и S2, она может найти другое сообщение М’, с той же самой парой подписей S1 и S2. Однако обратите внимание, что это — экзистенциальная подделка, которая не помогает Еве.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Adblock
detector