Разное

Схема rsa: Rsa | Контроль Разума | Fandom

Содержание

Схема шифрования RSA и её программная реализация


Короткова Дарья Алексеевна,

студентка Ульяновский государственный университет

E-mail: [email protected]


Аннотация


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


Чтобы обеспечить безопасность личных данных при передаче, необходимо зашифровывать информацию.


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


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


Ключевые слова: шифр, C++, безопасность, RSA, OAEP.


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


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


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


· Если известно x, то вычислить f(x) просто.


· Если известно y=f(x), то для вычисления x нет простого пути.


Алгоритм RSA:


1. Создание открытого и закрытого ключа.


1. Выбирается два простых числа u и v.


2. Вычисляется произведение p=u*v.


3. Вычисляется функция Эйлера φ(p)=(u-1)(v-1)


4. Выбираем открытую экспоненту e (1<e< φ(p))


5. Вычисляем закрытую экспоненту d, где (d*e) mod φ(p) =1


6. Получаем открытый ключ (e, p) и закрытый ключ (d, p).


2. Шифрование и дешифрование.


Посмотрим модель шифрования и дешифрования сообщения на конкретном примере. Пусть Алиса хочет послать Бобу сообщение h.



У Алисы есть открытый ключ Боба. А Боб владеет своим закрытым ключом.


w=G(h)= he mod p h=Q(w)=wd mod p


Безопасность схемы шифрования RSA:


Я написала программу на языке высокого уровня С++, где каждый символ кодируется на основании таблицы ASCII, и затем осуществляется алгоритм RSA.



Например, берем символ I, по таблице ASCII его код равен 73. Генерация ключей такая же, как и в примере написанной программы.


w=G(h)= he mod p = 732075 mod 21823=8774; (посчитано на инженерном стандартном калькуляторе в операционной системе Windows)


h=Q(w)=wd mod p = 877483 mod 21823 = 73 = I


Надёжность шифрования обеспечивается тем, что третьему лицу (старающемуся взломать шифр) очень трудно вычислить закрытый ключ по открытому. Оба ключа вычисляются из одной пары простых чисел (v и u). То есть ключи связаны между собой. Но установить эту связь очень сложно. Основной загвоздкой является декомпозиция модуля на простые сомножители v и u. Если число является произведением двух очень больших простых чисел, что его очень трудно разложить на множители.


Некоторые атаки на RSA.


1. Разложение на множители.


Реализуется на подборе простых чисел u, v, для надёжности числа должны быть большими.


2. Выборка шифрованного текста.


Пусть Ева перехватывает сообщение w от Алисы к Бобу w=ze (mod n), где z- открытый текст, е — открытый ключ; Ева выбирает число r, r<n и вычисляет с помощью открытого ключа x=re (mod n) ,y= x*c (mod n)


Ева передает Y бобу для дешифрования и получает g = yd mod n. Ева может легко найти z

g= yd mod n=(w*xe)d mod n = (wd*xed)mod n = (wd*x) mod n =(z*x)mod n

z= (z*x) mod n -> z=w*x-1 mod n

3. Исходный текст.


Криптосистема RSA обладает низкой криптостойкостью при малой экспоненте на коротком сообщении. Действительно, при c = me < n открытый текст m может быть восстановлен по шифротексту © при помощи процедуры извлечения корня. Однако меры противодействия также очевидны, — либо открытый ключ e должен быть достаточно большим, либо открытый текст не должен быть коротким. Выбор малого e обусловлен соображениями вычислительной эффективности шифрования и проверки подписи.


Это показывает, что применение на практике шифрования RSA обладает низкой криптостойкостью, поэтому пользуются схемой дополнительного шифрования OAEP.


Оптимальное асимметричное дополнение шифрования (OAEP — Optimal Assimetric Encryption Padding) — схема дополнения, обычно используемая совместно с какой-либо односторонней функцией с потайным входом (например RSA или функции Рабина) для повышения криптостойкости последней.


Шифрование. Ниже показаны шаги процесса шифрования.

  1. Дополняем сообщение, чтобы сделать его w -битовым. Обозначим его W.
  2. Выбираем случайное число s (одноразовое число) из k бит.
  3. Используем общедоступную одностороннюю функцию G, которая принимает целое s -битовое число, и создает w -разрядное целое число (w — размера W, и s <w ).
  4. Применяет маску, G (s), чтобы создать первую часть исходного текста P1=W+G(s) является замаскированным сообщением.
  5. Создаём вторую часть исходного текста P2 = H(P1) + s. Функция H — другая общедоступная функция, которая принимает w -битовые входные сообщения и создает k -битовые выходные сообщения.
  6. Cоздаём C = Pe = (P1 || P2) e и передаём C.


Дешифрование. Следующие шаги показывают процесс дешифрования:

  1. Создаём P = Cd = (P1 || P2).
  2. Обновляем значение s, используя H(P1) + P2= H(P1) + H(P2) + s =s.
  3. Применяет G(s) + P = G(s) + G(s) + W=W , чтобы обновить значение дополненного сообщения.
  4. После удаления дополнения W, находим первоначальное сообщение.


Алгоритм OAEP применяется для предварительной обработки сообщения перед использованием RSA. Сначала сообщение дополняется до фиксированной длины с помощью OAEP, затем шифруется с помощью RSA.


Литература:

  1. Венбо Мао. Современная криптография. Теория и практика = Modern Cryptography: Theory and Practice. — М.: Вильямс, 2005.
  2. Нильс Фергюсон, Брюс Шнайер. Практическая криптография = Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: Диалектика, 2004.
  3. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф, 2002.

RSA, а так ли все просто? / Хабр

Прелюдия

Доброго времени суток, уважаемые читатели.
Скорее всего, большинству из вас известно, что из себя представляет асимметричный алгоритм шифрования RSA. В самом деле, этому вопросу по всему рунету и на этом ресурсе в частности посвящено столько статей, что сказать о нем что то новое практически невозможно.
Ну что там, ей богу, можно еще придумать и так все давным-давно понятно. Рецепт приготовления прост:
Два простых числа P и Q.
Перемножить до получения числа N.
Выбрать произвольное E.
Найти D=E-1(mod(P-1)(Q-1)).
Для шифрования сообщение M возводим в степень E по модулю N. Для дешифрования криптотекст C в степень D по все тому же модулю N. Все криптопримитив готов. Берем и пользуемся, так? На самом деле, не так. Дело все в том, что это и в самом деле не более чем криптопримитив и в реальном мире все самую чуточку сложнее.

Немного теории

Для того чтобы понять почему крайне не рекомендуется использовать RSA в его наиболее простой форме сперва отметим следующее требование, выдвигаемое к асимметричным криптосистемам.
Требование 1:
Современная асимметричная криптосистема может(но это еще не факт) считаться стойкой, если злоумышленник, имея два открытых текста M1 и M2, а также один шифротекст Cb не может с вероятностью большей, чем 0.5 определить какому из двух открытых текстов соответствует шифротекст Cb.
Посмотрим, удовлетворяет ли RSA данному требованию. Итак, представим, злоумышленник Мэлори прослушивает переписку Алисы и Боба. В один чудесный для себя день он видит, что Боб в открытом виде задал Алисе очень важный вопрос, знание ответа на который обогатит, ну или, по крайней мере, безмерно потешит любопытство Мэлори. Алиса односложно отвечает Бобу на этот вопрос личного характера. Она шифрует свой ответ открытым ключом Боба и отправляет шифротекст. Далее Мэлори перехватывает шифротекст и подозревает, что в нем зашифровано либо «Да», либо «Нет». Всё, что ему теперь нужно сделать для того чтобы узнать ответ Алисы это зашифровать открытым ключом Боба слово «Да» и если полученный криптотекст совпадет с перехваченным, то это означает, что Алиса ответила «Да», в противном же случает злоумышленник поймет, что ответом было «Нет».

Как видно из этого, пускай несколько надуманного, но все же не столь и утопичного примера, RSA не столь надежна как это принято считать. Да конечно, можно сказать, что Алиса сама дура и никто ее не просил отвечать на такой серьезный для нее вопрос односложно. Так что же теперь запретить использование односложных ответов в криптографии? Конечно, нет. Все не так плохо, достаточно чтобы алгоритм добавлял к тексту некоторую случайную информацию, которую бы невозможно было предугадать и коварный Мэлори будет бессилен. Ведь, в самом деле, не сможет же он предсказать, что ответ «Да» после обработки алгоритмом превратится, например, в «Да4FE6DA54», а следовательно и зашифровать это сообщение он не сможет и нечего ему будет сравнивать с перехваченным криптотекстом.

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

C=ME(mod N)

получаем более близкую к действительности

C=(M||Rand)E(mod N),

где Rand случайное число.

Такую методику называют схемами дополнения. В настоящее время использование RSA без схем дополнения является не столько плохим тоном, сколько непосредственно нарушением стандартов.

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

Требование 2:

Пусть злоумышленник имеет доступ к расшифровывающему «черному ящику». Т.е. любой криптотекст по просьбе злоумышленника может быть расшифрован. Далее злоумышленник создает два открытых текста M1 и M2. Один из этих текстов шифруется и полученный в результате криптотекст Cb возвращается злоумышленнику. Задача злоумышленника угадать с вероятностью большей чем 0.5 какому из сообщений M1 и M2 соответсвует криптотекст Cb. При этом он может попросить расшифровать любое сообщение, кроме Cb(в противном случае игра не имеет смысла). Говорят что криптосистема стойкая, если злоумышленник, даже в таких прекрасных для себя условиях, не сможет указать какому исходному тексту соответствует Cb с вероятностью большей 0.5.

В свете вышесказанного посмотрим как с этим обстоят дела в RSA.

Итак, злоумышленник имеет два сообщения M1 и M2. А также криптотекст

Cb=M1E(mod N).

Ему необходимо указать какому конкретно из двух текстов соответствует Cb. Для этого он может предпринять следующее. Зная открытый ключ E, он может создать сообщение

C’=2E*Cb(mod N).

Далее он просит расшифровывающий «черный ящик» расшифровать сообщение C’. А затем несложная арифметика ему в помощь. Имеем:

M’=C’D(mod N)=2ED*M1ED(mod N)=2*M1(mod N).

Т.е. вычислив M’/2 злоумышленник увидит M1. А это означает, что он поймет что в нашем примере было зашифровано сообщение M1, а следовательно мы еще раз убедились в неприемлемости использования RSA в его наивном виде на практике.

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

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

В RSA при подписи и при шифровании данных используют две различные схемы дополнений. Схема, реализуемая для подписания документов, называется RSA-PSS(probabilistic signature scheme) или вероятностная схема подписи. Схема, используемая при шифровании – RSA-OAEP(Optimal asymmetric encryption padding) или оптимизированное асимметричное дополнение шифрования, на примере OAEP и рассмотрим как на самом деле происходит шифрование сообщений в RSA.

RSA-OAEP

Итак чтобы зашифровать абсолютно любое сообщение в RSA-OAEP делается следующее:

  1. Выбираются две хеш-функции G(x) и H(x) таким образом, чтобы суммарная длина результатов хеш-функций не превышала длины ключа RSA.
  2. Генерируется случайная строка битов l. Длина строки должна быть равна длине результата хеш-функции H(x).
  3. Сообщение M разбивают на блоки по k-бит. Затем к каждому полученному блоку m дописывают (n-k) нулей. Где n-длина хеш-функции G(x).
  4. Определяют следующий набор бит: {m||0(n-k)⊕G(l)}||{l⊕H(m||0(n-k)⊕G(l))}
  5. Полученные биты представляют в виде целого числа M1
  6. Криптотекст получают по формуле: C=M1E(mod N)

Процесс дешифрования выглядит следующим образом:

  1. Находят M1 по формуле M1=CD(mod N)
  2. В полученном наборе бит отсекают левую часть. В смысле: левой частью служат n левых бит числа M1 где n-длина хеш-функции G(x). Обозначим эти биты условно T. И заметим, что T={m||0(n-k)⊕G(l)}. Все остальные биты являются правой частью.
  3. Находим H(T)=H(m||0(n-k)⊕G(l))
  4. Зная H(T) получаем l, т.к. знаем l⊕H(T)-это правая часть блока.
  5. Вычислив l, находим m из T⊕G(l) т.к. T={m||0(n-k)⊕G(l)}
  6. Если m заканчивается (n-k)-нулями значит сообщение зашифровано правильно. Если нет то это значит, что шифротекст некорректен, а следовательно он скорее всего подделан злоумышленником.

Заключение

Т.е. RSA это не только возведение в степень по модулю большого числа. Это еще и добавление избыточных данных позволяющих реализовать дополнительную защиту вашей информации. Вы, возможно, спросите: а зачем это все нужно? Неужели в действительности может произойти такая ситуация, когда атакующий получит доступ к расшифровывающему алгоритму? Совсем по другому поводу как-то было сказано: если какая-либо неприятность может произойти, она обязательно произойдет. Только вот с использованием схем дополнений это уже не будет считаться неприятностью.

upd: перенес в блог криптография.

upd2:

Литература и ссылки:

1. Н. Фергюссон, Б. Шнайер «Практическая криптография»

2. Н. Смарт «Криптография»

3. Спецификация RSA-OAEP(pdf)

Основы шифрования (часть 2) — Алгоритм RSA

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

Автор: Malarkey

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

Алгоритм RSA

Шифрование с использованием публичного ключа

Шифрование при помощи публичного ключа используется повсеместно. Если вы хотя бы раз оплачивали что-то в интернете, то уже пользовались этим методом (я надеюсь!). Сразу же возникает вопрос о том, как работает эта защита. Если я ввожу номер своей кредитной карты, чтобы что-то купить, почему кроме адресата никто не может подсмотреть эти сведения? Приведу метафору. Чтобы открыть сейф, вам требуется ключ (или молоток, но, к счастью, сейфы и замки защищены от такого рода деятелей). В шифровании с использованием публичного ключа происходит примерно то же самое. Вы показываете замок на всеобщее обозрение, но ключ от этого замка есть только у избранных, а другими методами открыть дверь практически невозможно.

RSA – один из алгоритмов, реализующих вышеуказанную схему. Кроме того, мы можем использовать этот алгоритм для подтверждения подлинности нашей личности. Если вы, используя секретный ключ, отсылаете кому-то зашифрованное сообщение, адресат при помощи публичного ключа может расшифровать ваше послание. Эта технология позволяет подписывать сообщения, и тем самым подтверждается подлинность отправителя.

Демо-программа на базе алгоритма RSA

Я написал небольшую программу с реализацией шифрования по алгоритму RSA. При помощи флагов –t и –m (с указанием любого целого числа на ваш выбор) демонстрируются базовые возможности шифрования сообщения с использованием публичного ключа.

Рисунок 1: Процедура шифрования, дешифрования и цифровой подписи при помощи алгоритма RSA

В примере выше показана пошаговая схема использования публичного и секретного ключа. Публичный ключ состоит из двух чисел: (3233, 17). Первое число (3233) является результатом умножения двух простых чисел (61 и 53). Второе число (17) – простое. Единственный общий множитель двух чисел нашего ключа – единица. Далее мы генерируем секретный ключ, используя выбранные ранее два простых числа. Затем мы можем шифровать и дешифровать сообщения при помощи публичного и секретного ключа соответственно. Если мы хотим подписать сообщение, то используем ключи в обратном порядке (сначала секретный, потом – публичный).

У программы есть дополнительные опции (см. рисунок ниже), позволяющие задавать собственные ключи.

Рисунок 2: Другие опции демонстрационной программы

Один нюанс – программа работает некорректно, если сообщение больше, чем публичный ключ.

Математическая сторона вопроса

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

  1. Выбираем два простых числа p и q.

  2. Вычисляем n = p*q (часть публичного ключа).

  3. Вычисляем тотиент от n, t, который заканчивается числом (p-1)*(q-1).

  4. Выбираем простое число e < t и проверяем, чтобы t % e не было равно 0 (e – вторая часть публичного ключа).

  5. Вычисляем секретный ключ d = e ^ -1 mod t, где d*e mod t = 1.

Теперь по шагам рассмотрим процесс шифрования и дешифрования:

  1. Чтобы зашифровать сообщение, используем формулу E = m^e mod n (m – сообщение).

  2. Чтобы расшифровать сообщение, используем формулу E ^ d mod n.

Доказательство того, что Дешифровка( Шифровка ( M ) ) = M приводится в Википедии. Здесь мы еще больше погружаемся в математику и доказательство теорем. Если вы не особо подкованы в этой области, просто попробуйте позапускать скрипт с различными ключами и сообщениями и убедитесь, что все работает корректно.

Рискну предположить, что многим из вас интересно, как взломать систему, построенную на основе алгоритма RSA. Злоумышленник знает числа n и e. Если взломщик сможет найти число t, то вычислит секретный ключ. Задача заключается в том, чтобы факторизовать публичный ключ. Однако целочисленная факторизация – довольно сложная задача, и именно поэтому алгоритм RSA довольно устойчив. Возможно, когда появятся квантовые машины, вычислить секретный ключ не будет составлять особого труда, но сейчас достаточной длинный ключ сможет защитить наши данные.

Дополнительные размышления

При чтении статьи у вас, возможно, возник следующий вопрос: «Как мне удостовериться в том, что полученный публичный ключ именно того человека, которому я хочу отослать сообщение?». Если мы можем обнародовать публичный ключ, то с таким же успехом могли бы поделиться и секретным ключом. Более того, я не могу сходить в офис Амазона и получить от них публичный ключ. Я веду к тому, что мне нужно получить этот ключ каким-то образом. Инфраструктура открытых ключей (Public Key Infrastructure, PKI) – технология, позволяющая управлять всеми этими ключами. Мы используем шифрование для подтверждения наших ключей, предназначенных для шифрования (получается замкнутый круг). Рассмотреть эту проблему в рамках одной статьи не получится. Если вы хотите узнать подробности, гугл вам в помощь.

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

Надеюсь, вы подчерпнули для себя нечто новое. Шифруйте и подписывайте свои сообщения!

Ссылки

https://en.wikipedia.org/wiki/RSA_(cryptosystem)

Выбор параметров шифра RSA и возможные последствия / Хабр

Под катом описаны примеры выбора «плохих» параметров шифра RSA.

Процитируем авторов учебного пособия «Основы криптографии» А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, Москва. «Гелиос АРВ», 2001г., на странице 316:

«Следует подчеркнуть необходимость соблюдения осторожности в выборе модуля RSA (числа n) для каждого из корреспондентов сети. В связи с этим можно сказать следующее. Читатель может самостоятельно убедиться в том, что зная одну из трех величин p, q или φ(n), можно легко найти секретный ключ RSA…».

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

Для этого достаточно располагать зашифрованным текстом, заданным модулем шифра n, открытым ключом е шифра и выполнить всего три шага атаки «бесключевого чтения». После четвертого атакующего шага устанавливается, что на предыдущем шаге был получен исходный текст, он может быть прочитан. Покажем, насколько просто это делается.

Вначале приведем сам пример со стр. 313-315 из названного пособия.

Пример

Шифрование короткого исходного текстового сообщения: RSA.
Получатель устанавливает шифр с характеристиками n=pq=527, где р=17, q=31 и φ(n)=(р –1)(q – 1)=480. В качестве открытого ключа е выбрано число, взаимно простое с φ(n), е=7. Для этого числа с помощью расширенного алгоритма Евклида найдены целые числа u и v, удовлетворяющие соотношению е∙u+φ(n)∙v=1:

480=7∙68+4,

7=4∙1+3,

4=3∙1+1,

1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,

v=2, u=–137
.

Поскольку –137≡343(mod480), то d=343.

Проверка: 7∙343=2401≡1(mod480).

Текстовое сообщение представляется в виде последовательности чисел, содержащихся в интервале [0, 526]. Для этого буквы R, S и A кодируются пятиразрядными двоичными числами. Используются порядковые номера этих букв в английском алфавите при их двоичном представлении:

R=1810=(10010)2, S=1910=(10011)2,
A=110=(00001)2.

Тогда RSA=(100101001100001)2. Разбиение текста на блоки ограниченной длины дает представление из двух блоков: RSA=(100101001), (100001)=(М1=297, М2=33).

Последовательно шифруются блоки исходного текста М1=297, М2=33:
y1k1)=М1e≡2977(mod527)=474.

Здесь воспользовались тем, что:

2977=((2972)3)297≡(mod527)=(2003(mod527)297)(mod527)=474,
y2k2)=M2e≡337(mod527)=407.

Шифрованный текст, как и исходный, получаем в виде двух блоков: у1=474; у2=407.

Расшифрование представляется последовательностью действий Dk(yi )=(yi )d=(yi )343(mod 527), i=1,2.

Вычисления возведения в степень d более удобно проводить, предварительно представляя показатель степени суммой степеней числа 2, а именно: 343=256+64+16+4+2+1.

Используя это представление показателя степени d=343, получаем:

4742≡174(mod527),

4744≡237(mod527),

4748≡307(mod527),

47416≡443(mod527),

47432≡205(mod527),

47464≡392(mod527),

474128≡307(mod527),

474256≡443(mod527),


и окончательно 474343(mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

Аналогично вычисляется значение 407343(mod527)=33.

Переход к буквенному представлению расшифрованного сообщения дает: RSA.

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

Атака на шифр RSA

Рассмотрим пример атаки на шифр RSA. Воспользуемся данными примера, приведенного на странице 313-315 в учебном пособии «Основы криптографии» А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, Москва. «Гелиос АРВ», 2001.

Неудачность (недопустимость) выбранных параметров системы в этом примере легко показывается вычислениями, реализующими атаку бесключевого чтения исходного текста. Сущность такой атаки состоит в следующем. Заданы открытый ключ шифра RSA (е=7, n=527) и шифрованный текст. В примере шифрованный текст представлен двумя блоками
у=(у1=474, у2=407).

Каждый шифрованный блок атакуется индивидуально, вначале атакуем у1=474, после его дешифрования, атакуем другой блок у2=407.

Далее формируется путем многократного зашифрования с сохранением результатов двух последовательных шагов алгоритма атаки и с использованием открытого ключа последовательность числовых значений уi, у1 имеющийся шифрованный текст.

В алгоритме атаки на шифрованный текст определяется такой номер шага j, для которого yiej(mod n)=(yiej–1(mod n))e(mod n)=yi, i>1. Из последнего соотношения видим, что при возведении в степень е значения (yiej–1(mod n)) получается начальный шифoртекст yi = у1.

Но это и означает, что на этом шаге шифровался открытый текст. Непосредственными вычислениями (их оказывается совсем немного) с использованием экранного калькулятора находим то значение j, при котором цикл шифрования завершается значением y1, с которого цикл и был начат.

Атака на первый блок у1=474 шифртекста.
Шаг 1: &nbsp 4747(mod527)=382;
Шаг 2: &nbsp 3827(mod527)=423;
Шаг 3: &nbsp 4237(mod527)=297;
Шаг 4: &nbsp на этом шаге шифруется уже найденный исходный текст, но его необходимо выполнить, так как атакующий исходного текста не знает. Признаком завершения атаки является совпадение начального значения шифртекста (474) и результата 4-го шага зашифрования. Именно такое совпадение и имеет место.

2977(mod527)=474 получили начальный (первый) блок шифртекста. Атака на первый блок завершена успешно у1=474. Предшествующий результат шага 3 равен открытому тексту М1=297.

По существу в кольце вычетов по модулю n=527 реализовался короткий цикл обработки вычета r=297 по модулю n=527. Это записывается так yi1=297. Формируем степенные вычеты
(((2977(mod527))7(mod527))7(mod527))7=297.

Атака на второй блок у2=407 шифртекста.
Шаг 1: &nbsp 4077(mod527)=16;
Шаг 2: &nbsp 167(mod527)=101;
Шаг 3: &nbsp 1017(mod527)=33;
Шаг 4: &nbsp 337(mod527)=407.

Вновь на третьем шаге получен блок исходного текста (М2=33), но атакующему это неизвестно, и он выполняет следующий (четвертый шаг), результат которого (407) совпадает с начальным шифртекстом у2=407.

По существу в кольце вычетов по модулю n=527 реализовался короткий цикл обработки вычета r=33 по модулю n=527. Это записывается так yi2=33.

Формируем степенные вычеты ((337(mod527))7(mod527))7(mod527)=33.

Результат атаки (исходный текст М1=297, М2=33) получен трехкратным шифрованием заданного шифртекста. Больший успех для атакующего шифртекст трудно представить.

Продолжая обсуждение вопроса о выборе модуля и других параметров шифра, можно добавить, что модуль шифра (n=527) некоторые исходные тексты вообще не позволяет шифровать. При этом выбор значения открытого ключа е большой роли не играет. Существуют значения исходных текстов, которые вообще невозможно зашифровать выбранным шифром с модулем n=527.

Ни на одном из заданных е не удается зашифровать исходные тексты, представляемые числами
187, 341, 154 и 373.

Пример (невозможность шифрования значений некоторых исходных текстов)

Пусть исходные тексты представлены четырьмя блоками y=(y1=154, y2=187, y3=341, y4=373). Экспонента е открытого ключа шифра может быть любым взаимно простым числом с функцией Эйлера φ(n)=φ(527)=480. Впрочем, для рассматриваемого случая открытый ключ е может быть задан произвольно. Действительно, пусть е=2, 4, 7, 9, 17, 111 тогда:

1542(mod527)=1;
1544(mod527)=1;
1547(mod527)=154;
1549(mod527)=154;
15417(mod527)=154;
154111(mod527)=154;
1872(mod527)=187;
1874(mod527)=187;
1877(mod527)=187;
1879(mod527)=187;
18717(mod527)=187;
187111(mod527)=187;
3412(mod527)=341;
3414(mod527)=1;
3417(mod527)=341;
3419(mod527)=341;
34117(mod527)=341;
341111(mod527)=341;
3732(mod527)=1;
3734(mod527)=373;
3737(mod527)=373;
3739(mod527)=373;
37317(mod527)=373;
373111(mod527)=373.

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

Алгоритм RSA на Go | 4gophers.ru

Алгоритм RSA на Go

Перевод статьи “RSA — theory and implementation“

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

Алгоритм RSA

Красота алгоритма RSA в его простоте. Вам достаточно знакомства с элементарной теорией чисел, чтобы разобраться в сути за пару часов.

Договоримся, сто в этой статье M это сообщение, которое хотим зашифровать. C — уже зашифрованный текст. C и M большие целые числа. В разделе “Практические соображения” описано как можно представить любые данные в виде больших целых чисел.

Алгоритм RSA состоит из трех основных фаз: генерация ключа, шифрование и дешифрование.

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

Первое что нужно сделать при использовании RSA — сгенерировать приватный и публичный ключи. Это делается в несколько этапов.

Шаг 1: Выбираем два случайных больших числа p и q и вычисляем n=pq. Насколько большими должны быть эти числа? Рекомендуется выбирать размер для n не меньше 2048 бит, более 600 десятичных цифр. Предполагается, что сообщение M представлено числом меньше чем n(в разделе “Практические соображения” рассказывается что делать если сообщение слишком большое).

Шаг 2: Выбираем маленькое нечетное число e, которое будет относительно простым к общей функции Эйлера \(\phi(n)\), которая рассчитывается по формуле эйлера:

$$
\phi(n) =n \prod_{p\mid n} \left(1-\frac{1}{p}\right)
$$

Для \(n=pq\) где p и q простые числа получаем:

$$
\phi(n)=n\frac{p-1}{p}\frac{q-1}{q}=(p-1)(q-1)
$$

На практике рекомендуется выбирать e как одно из известных простых чисел, чаще всего это 65537. Выбор заранее известного числа никак не влияет на безопасность алгоритма, но дает плюсы в производительности [1].

Шаг 3: Вычисляем d как мультипликативного обратного по модулю e от \(\phi(n)\). Лемма 3 в этой статье гарантирует что d существует и будет уникальным(еще там объясняется что такое модуль мультипликативного обратного).

Сейчас у нас есть все для генерации приватного и публичного ключа. Публичный ключ это пара \([e,n]\), приватный это пара \([d,n]\). На практике, при расшифровке у нас уже есть доступ к n (из публичного ключа), поэтому действительно приватным будет только d.

Шифрование и дешифрование

Шифрование и дешифрование выполняются с помощью одной и той же модульной формулы возведения в степень. Меняются только значения x и y

$$
f(x)=x^y\pmod{n}
$$

Для шифрования входное значение будет M, а показатель степени e:

$$
Enc(M)=M^e\pmod{n}
$$

Для дешифровки входное значение это закодированный текст C, а степень будет d:

$$
Dec(C )=C^d\pmod{n}
$$

Почему это работает?

Для шифрования сообщения M мы возводим его в степень e по модулю n. Этот процесс обратим. С помощью возведения в степень d по модулю n мы получим обратно наше сообщение M. Но почему это работает?

Доказательство:

$$
Dec(Enc(M))=M^{ed}\pmod{n}
$$

Напомню, что e и d мультипликативно инверсные по модулю \(\phi(n)\). Это значит \(ed\equiv 1\pmod{\phi(n)}\). Отсюда следует, что для некоторых целых чисел k у нас есть \(ed=1+k\phi(n)\) или \(ed=1+k(p-1)(q-1)\).

Теперь посмотрим что такое \(M^{ed}\) по модулю p. Подставляем формулу для ed получим:

$$
M^{ed}\equiv M(M^{p-1})^{k(q-1)}\pmod{p}
$$

Теперь модем использовать малую теорему Ферма, из которой следует что если M не делится на p то \(M^{p-1}\equiv 1\pmod{p}\). Эта теорема частный случай теоремы Эйлера, доказательство я приводил в этой статье.

В последнем выражении можно убрать 1 для \(M^{p-1}\) и возведение 1 в любую степень тоже дает 1:

$$
M^{ed}\equiv M\pmod{p}
$$

Заметим, что малая теорема ферма работает когда M не делится на p. Мы можем утверждать это, потому что если \(M\equiv 0\pmod{p}\) то \(M^{ed}\equiv 0\pmod{p}\) и снова \(M^{ed}\equiv M\pmod{p}\)

Аналогично можем доказать что:

$$
M^{ed}\equiv M\pmod{q}
$$

И так, получается \(M^{ed}\equiv M\) для простых множителей ed. Согласно следствию китайской теоремы об остатках, получается что

$$
M^{ed}\equiv M\pmod{n}
$$

Так как изначально мы определили что M меньше n, то выполняется \(Dec(Enc(M))=M\)

Почему это безопасно?

Без приватного ключа, злоумышленник может вычислить только \(M^e\pmod {n}\) и значения n и e (как части публичного ключа). Может ли он получить значение M в этом случае?

Нет известных способов сделать это без факторизации n(оригинальная спецификация RSA, секция IX), а факторизация, как известно, сложная задача. В частности, предполагается что M и e достаточно большие что \(M^e > n\)(иначе дешифровка была бы очень простой)

Если бы факторинг был бы простым, то можно было бы разложить n на p и q, потом вычислить \(\phi(n)\) и в конце концов найти d из \(ed\equiv 1\pmod{\phi(n)}\) использую расширенный алгоритм Евклида.

Практические соображения

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

Существует простая схема заполнения PKCS #1 v1.5. Она использовалась много лет определена в стандарте RFC 2313. Сейчас вместо нее рекомендуется использовать более продвинутые схемы, например OAEP. Но PKCS #1 v1.5 проще для понимания, поэтому я объясню принцип на ее примере.

Предположим, у нас есть некоторые двоичные данные D для шифрования. Описанный метод подходит для данных любого размера, но мы сосредоточимся на шифровании небольших фрагментов. На практике этого, как правило, достаточно — RSA обычно используется для шифрования только симметричного ключа, который намного меньше чем ключ RSA [2]. Но такая схема может работать с данными любого объема, достаточно просто разделить их на блоки с заранее известным размером.

Из данных D создаем блок для шифрования. Размер блока равен длине нашего RSA ключа:

PS — это заполнение которое занимает все байты не занятые заголовком и данными D в рамках блока. Оно должно быть не меньше 8 байт(если это не так, то данные могут быть разбиты на несколько блоков). Заполнение — это последовательность случайных не нулевых байт, которая генерируется отдельно для каждого шифрования. Как только мы сформируем этот блок данных, преобразовываем его в число используя big-endian кодировку [3]. В итоге у нас получается большое число, которое уже можно шифровать с помощью RSA \(Enc(x)=x^e\pmod{n}\). Результат кодируем в бинарный вид и отправляем по сети.

Дешифровка проходит в обратном порядке. Принятый поток байт превращаем в число, выполняем \(Dec©=C^d\pmod{n}\), удаляем все заполнения. В заполнении нет 0 байтов а разделяются они как раз 0 байтами, поэтому вырезать их просто. В итоге у нас получается наше исходное сообщение.

Случайное заполнение усиливает стойкость и атаки на “книжный” алгоритм RSA становятся непрактичными. Но в целом, в некоторых случаях схема все еще уязвима для более сложных атак. Поэтому на практике стоит использовать более современные схемы заполнения, такие как OAEP.

Реализация RSA на Go

Я реализовал на Go описанный в этой статье простой вариант шифрования и дешифрования RSA. Реализация на Go таких криптографических алгоритмов довольно простое дело из-за возможности работы с большими числами произвольной точности. Для этого используется пакет bid из стандартной библиотеки. В этом пакете поддерживаются не только основные манипуляции с числами, но и есть несколько примитивов специально для криптографии. Например метод Exp используется для эффективного возведения в степень, а метод ModInverse позволяет искать мультипликативно обратных по модулю. А в модуле crypto/rand есть примитивы специально предназначенные для использования в криптографии.

Кстати, в Go уже есть реализация RSA в пакете crypto/rsa. Для реальных проектов лучше использовать его[4], чем писать свой велосипед. Код ниже стоит использовать только для учебных целей.

Весь код целиком доступен на GitHub.

Начинаем с определения структур для публичного и приватного ключа:

type PublicKey struct {
  N *big.Int
  E *big.Int
}

type PrivateKey struct {
  N *big.Int
  D *big.Int
}

В коде есть функция GenerateKeys, которая случайным образом генерирует эти ключи с заданной длинной.

Имея публичный ключ, шифрование будет очень простым:

func encrypt(pub *PublicKey, m *big.Int) *big.Int {
  c := new(big.Int)
  c.Exp(m, pub.E, pub.N)
  return c
}

А дешифрование

func decrypt(priv *PrivateKey, c *big.Int) *big.Int {
  m := new(big.Int)
  m.Exp(c, priv.D, priv.N)
  return m
}

Логика в этих функциях одинаковая и очень простая. Это просто типизированные обертки над Exp.

В конце нам нужно добавить реализацию PKCS #1 v1.5:

// EncryptRSA encrypts the message m using public key pub and returns the
// encrypted bytes. The length of m must be <= size_in_bytes(pub.N) - 11,
// otherwise an error is returned. The encryption block format is based on
// PKCS #1 v1.5 (RFC 2313).
func EncryptRSA(pub *PublicKey, m []byte) ([]byte, error) {
  // Compute length of key in bytes, rounding up.
  keyLen := (pub.N.BitLen() + 7) / 8
  if len(m) > keyLen-11 {
    return nil, fmt.Errorf("len(m)=%v, too long", len(m))
  }

  // Following RFC 2313, using block type 02 as recommended for encryption:
  // EB = 00 || 02 || PS || 00 || D
  psLen := keyLen - len(m) - 3
  eb := make([]byte, keyLen)
  eb[0] = 0x00
  eb[1] = 0x02

  // Fill PS with random non-zero bytes.
  for i := 2; i < 2+psLen; {
    _, err := rand.Read(eb[i : i+1])
    if err != nil {
      return nil, err
    }
    if eb[i] != 0x00 {
      i++
    }
  }
  eb[2+psLen] = 0x00

  // Copy the message m into the rest of the encryption block.
  copy(eb[3+psLen:], m)

  // Now the encryption block is complete; we take it as a m-byte big.Int and
  // RSA-encrypt it with the public key.
  mnum := new(big.Int).SetBytes(eb)
  c := encrypt(pub, mnum)

  // The result is a big.Int, which we want to convert to a byte slice of
  // length keyLen. It's highly likely that the size of c in bytes is keyLen,
  // but in rare cases we may need to pad it on the left with zeros (this only
  // happens if the whole MSB of c is zeros, meaning that it's more than 256
  // times smaller than the modulus).
  padLen := keyLen - len(c.Bytes())
  for i := 0; i < padLen; i++ {
    eb[i] = 0x00
  }
  copy(eb[padLen:], c.Bytes())
  return eb, nil
}

И обратные преобразования:

// DecryptRSA decrypts the message c using private key priv and returns the
// decrypted bytes, based on block 02 from PKCS #1 v1.5 (RCS 2313).
// It expects the length in bytes of the private key modulo to be len(eb).
// Important: this is a simple implementation not designed to be resilient to
// timing attacks.
func DecryptRSA(priv *PrivateKey, c []byte) ([]byte, error) {
  keyLen := (priv.N.BitLen() + 7) / 8
  if len(c) != keyLen {
    return nil, fmt.Errorf("len(c)=%v, want keyLen=%v", len(c), keyLen)
  }

  // Convert c into a bit.Int and decrypt it using the private key.
  cnum := new(big.Int).SetBytes(c)
  mnum := decrypt(priv, cnum)

  // Write the bytes of mnum into m, left-padding if needed.
  m := make([]byte, keyLen)
  copy(m[keyLen-len(mnum.Bytes()):], mnum.Bytes())

  // Expect proper block 02 beginning.
  if m[0] != 0x00 {
    return nil, fmt.Errorf("m[0]=%v, want 0x00", m[0])
  }
  if m[1] != 0x02 {
    return nil, fmt.Errorf("m[1]=%v, want 0x02", m[1])
  }

  // Skip over random padding until a 0x00 byte is reached. +2 adjusts the index
  // back to the full slice.
  endPad := bytes.IndexByte(m[2:], 0x00) + 2
  if endPad < 2 {
    return nil, fmt.Errorf("end of padding not found")
  }

  return m[endPad+1:], nil
}

RSA для цифровой подписи

RSA можно использовать для цифровой подписи. Как это работает:

  1. Генерируются и распространяются ключи также. У Алисы есть открытый и закрытый ключи. Она публикует свой открытый ключ в интернете.
  2. Когда Алиса захочет отправить сообщение Бобу, ей нужно убедить его, что это она отправляет сообщение. Для этого она шифрует сообщение своим секретным ключем \(S=Sign(M)=M^d\pmod{n}\). Подпись добавляется к сообщению.
  3. Когда Боб получает сообщение, он может расшифровать подпись с помощью публичного ключа Алисы: \(Check(S)=S^e\pmod{n}\) и если получится восстановить исходное сообщение, от подпись верна.

Доказательство верности утверждения будет таким же, как и для шифрования. Никто другой не смог бы подписать сообщение, потому что приватный ключ есть только у Алисы.

Это тоже “книжный” алгоритм подписи. В реальных алгоритмах подписи тоже используется механизм заполнения. Для подписи рекомендуют использовать PSS [5]. Я не буду в этой статье реализовывать алгоритм подписи, в стандартной библиотеке Go уже есть отличные реализации, например rsa.SignPKCS1v15 и rsa.SignPSS.

Примечания

  • 1. Под двум причинам: во-первых, не нужно находить другое случайное большое число и это экономит время, во-вторых 65537 имеет только два выставленных бита в двоичном представлении, а это делает алгоритм возведения в степень быстрее.
  • 2. Сильный AES ключ это 256 бит. RSA, как правило, 2048. RSA работает достаточно медленно, поэтому для потоковых данных часто используют гибридную схему, когда с помощью RSA шифруется только сильные AES ключ. Ёто основополагающая идея работы TLS и похожих протоколов.
  • 3. Обратите внимание, что первые 8 бит блока данных равны 0. Это позволяет гарантировать, что число, которое мы шифруем, меньше n
  • 4. Реализация в стандартной библиотеке устойчива к атакам типа стороннего канала. Использует алгоритмы время выполнения которых не зависит от характеристик входных данных — это делает атаки основанные на временны’х эффектах менее осуществимыми.
  • 5. Причина в различных алгоритмах заполнения для подписи и шифрования в том, что атаки тоже различаются. Если при шифровании злоумышленник ничего не знает о тексте сообщения, то в случае с подписью это не так.

НОУ ИНТУИТ | Лекция | Электронная цифровая подпись

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

Цель лекции: познакомиться с некоторыми алгоритмами формирования и проверки электронной цифровой подписи (ЭЦП, ЭП).

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

Рассмотренная нами в Лекции 11 схема использования алгоритма RSA при большом модуле N практически не позволяет злоумышленнику получить закрытый ключ и прочитать зашифрованное сообщение. Однако она дает возможность злоумышленнику подменить сообщение от абонента А к абоненту Б, так как абонент А шифрует свое сообщение открытым ключом, полученным от Б по открытому каналу связи. А раз открытый ключ передается по открытому каналу, любой может получить его и использовать для подмены сообщения. Избежать этого можно, используя более сложные протоколы, например, следующий.

Пусть, как и раньше, пользователь А хочет передать пользователю Б сообщение, состоящее из нескольких блоков mi. Перед началом сеанса связи абоненты генерируют открытые и закрытые ключи, обозначаемые, как указано в следующей таблице:

Открытый ключЗакрытый ключ
Пользователь А NA, dAeA
Пользователь Б NБ, dБeБ

В результате каждый пользователь имеет свои собственные открытый (состоящий из двух частей) и закрытый ключи. Затем пользователи обмениваются открытыми ключами. Это подготовительный этап протокола.

Основная часть протокола состоит из следующих шагов.

  1. Сначала пользователь А вычисляет числа , то есть шифрует сообщение своим закрытым ключом. В результате этих действий пользователь А подписывает сообщение.
  2. Затем пользователь А вычисляет числа , то есть шифрует то, что получилось на шаге 1 открытым ключом пользователя Б. На этом этапе сообщение шифруется, чтобы никто посторонний не мог его прочитать.
  3. Последовательность чисел gi передается к пользователю Б.
  4. Пользователь Б получает gi и вначале вычисляет последовательно числа , используя свой закрытый ключ. При этом сообщение расшифровывается.
  5. Затем Б определяет числа , используя открытый ключ пользователя А.
    За счет выполнения этого этапа производится проверка подписи пользователя А.

В результате абонент Б получает исходное сообщение и убеждается в том, что его отправил именно абонент А. Данная схема позволяет защититься от нескольких видов возможных нарушений, а именно:

  • пользователь А не может отказаться от своего сообщения, если он признает, что секретный ключ известен только ему;
  • нарушитель без знания секретного ключа не может ни сформировать, ни сделать осмысленное изменение сообщения, передаваемого по линии связи.

Данная схема позволяет избежать многих конфликтных ситуаций. Иногда нет необходимости зашифровывать передаваемое сообщение, но нужно его скрепить электронной подписью. В этом случае из приведенного выше протокола исключаются шаги 2 и 4, то есть текст шифруется закрытым ключом отправителя, и полученная последовательность присоединяется к документу. Получатель с помощью открытого ключа отправителя расшифровывает прикрепленную подпись, которая, по сути, является зашифрованным повторением основного сообщения. Если расшифрованная подпись совпадает с основным текстом, значит, подпись верна.

Существуют и другие варианты применения алгоритма RSA для формирования ЭЦП. Например, можно шифровать (то есть подписывать) открытым ключом не само сообщение, а хеш-код от него.

Возможность применения алгоритма RSA для получения электронной подписи связана с тем, что секретный и открытый ключи в этой системе равноправны. Каждый из ключей, d или e, могут использоваться как для шифрования, так и для расшифрования. Это свойство выполняется не во всех криптосистемах с открытым ключом.

Алгоритм RSA можно использовать также и для обмена ключами.

Цифровая подпись на основе алгоритма Эль-Гамаля

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

Алгоритм Эль-Гамаля также можно использовать для формирования цифровой подписи. Группа пользователей выбирает общие параметры Р и А. Затем каждый абонент группы выбирает свое секретное число Хi, 1 < Хi< Р-1, и вычисляет соответствующее ему открытое число . Таким образом, каждый пользователь получает пару (закрытый ключ; открытый ключ) = (Хi, Yi). Открытые ключи пользователей могут храниться в общей базе системы распределения ключей и при необходимости предоставляться всем абонентам системы.

Сообщение, предназначенное для подписи, должно быть представлено в виде числа, меньшего модуля Р. При большом размере сообщение разбивается на блоки необходимого размера. В некоторых случаях подписывается не само сообщение, а значение хеш-функции от него. В любом варианте цифровая подпись вычисляется в зависимости от некоторого числа m (m < P).

Пусть пользователь 1 хочет подписать свое сообщение цифровой подписью и передать его пользователю 2. В этом случае алгоритм действий следующий.

  1. Первый пользователь выбирает случайное секретное число k, взаимно простое с Р-1, и вычисляет число
  2. Затем с помощью расширенного алгоритма Евклида необходимо найти значение b в следующем уравнении:
    m = (X1 * a +k * b) mod (P-1)

    Пара чисел (a, b) будет цифровой подписью сообщения m.

  3. Сообщение m вместе с подписью (a, b) отправляется пользователю 2.
  4. Пользователь 2 получает сообщение m и с использованием открытого ключа первого абонента Y1 вычисляет два числа по следующим формулам: Если с1 = с2, то цифровая подпись первого пользователя верная. Для подписывания каждого нового сообщения должно каждый раз выбираться новое значение k.

Подписи, созданные с использованием алгоритма Эль-Гамаля, называются рандомизированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будут создаваться разные подписи (a,b), поскольку каждый раз будет использоваться новое значение k. Подписи, созданные с применением алгоритма RSA, называются детерминированными, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будет создаваться одна и та же подпись.

Пример вычисления и проверки цифровой подписи

Пусть абоненты, обменивающиеся через Интернет зашифрованными сообщениями, имеют следующие общие параметры: Р = 11, А = 7.

Один из пользователей этой системы связи хочет подписать свое сообщение m=5 цифровой подписью, сформированной по алгоритму Эль-Гамаля. Вначале он должен выбрать себе закрытый ключ, например, Х1=3 и сформировать открытый ключ Y1 = 73 mod 11 = 2. Открытый ключ может быть передан всем заинтересованным абонентам или помещен в базу данных открытых ключей системы связи.

Затем пользователь выбирает случайное секретное число k, взаимно простое с Р-1. Пусть k=9 ( 9 не имеет общих делителей с 10 ). Далее необходимо вычислить число

После этого с помощью расширенного алгоритма Евклида находится значение b в уравнении:

Решением последнего уравнения будет значение b=9.

Таким образом, пара чисел (8, 9) будет цифровой подписью сообщения m=5.

Если любой другой пользователь сети желает проверить цифровую подпись в сообщении, он должен получить из базы данных открытый ключ первого пользователя (он равен 2 ), вычислить два числа с1 и с2 и сравнить их.

Так как с1 = с2, то цифровая подпись первого пользователя в сообщения m=5 верная.

Создание ключей, шифрование и дешифрование сообщений в системе RSA

Библиографическое описание:


Наумчик, Н. С. Создание ключей, шифрование и дешифрование сообщений в системе RSA / Н. С. Наумчик, С. А. Васи. — Текст : непосредственный // Молодой ученый. — 2019. — № 45 (283). — С. 1-3. — URL: https://moluch.ru/archive/283/63831/ (дата обращения: 03.10.2020).



Криптосистема RSA — ассиметричная система с открытым ключом, названная в честь ее создателей: Rivest, Shamir, Adleman. Несмотря на то, что после создания криптосистемы прошло уже около сорока лет, она до сих пор остается самой используемой из всех систем со схожими алгоритмами работы из-за вычислительной сложности задачи факторизации больших целых чисел. Примечателен тот факт, что RSA стала первой системой, пригодной как для шифрования, так и для цифровой подписи.

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

Так что же послужило толчком для создания такой криптосистемы как RSA? Дело в том, что после опубликования статьи Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии», о которой ранее уже упоминалось, трое ученых Рональд Ривест, Ади Шамир (специалисты в сфере компьютерных технологий) и Леонард Адлеман (математик) из Массачусетского технологического института (MIT) приступили к поискам математической функции, позволяющей в полной мере реализовать модель криптосистемы с открытым ключом. После рассмотрения многих вариантов, ученые все же нашли алгоритм, с помощью которого можно легко находить большие простые числа, но очень сложно раскладывать произведение двух простых чисел на множители.

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

Таким образом, криптографическая система RSA остается на сегодняшний день одной из самых надежных (при длине ключе от 1024 бит).

Алгоритм работы RSA содержит в себе четыре основных этапа: генерация ключей, их распределение, шифрование и дешифрование.

На этапе создания ключей производятся следующие операции:

  1. Выбираются два больших простых числа p и q.
  2. Вычисляется их произведение , называемое модулем.
  3. Вычисляется значение функции Эйлера от полученного произведения .
  4. Выбирается произвольное число e, такое, что , причем
  5. С помощью алгоритма Евклида вычисляется некоторое число d, удовлетворяющее условию .

На этапе распределения ключей:

  1. Пара {e,n} выступает в качестве открытого ключа RSA.
  2. Пара {d,n} выступает в качестве закрытого ключа RSA.

На этапе шифрования и дешифрования:

Со стороны отправителя:

  1. Взять открытый ключ {e,n} получателя.
  2. Взять открытый текст m.
  3. Зашифровать сообщение с использованием открытого ключа получателя: .

Со стороны получателя:

  1. Принять зашифрованное сообщение C.
  2. Взять свой закрытый ключ (d,n).
  3. Применить закрытый ключ для дешифрования сообщения: .

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

Пример. Этап создания ключей:

1.Выберем два простых числа и , причем таких, что . Пусть и ;

2.Вычислим произведение взятых чисел:

3.Вычислим функцию Эйлера. Для этого воспользуемся формулой . Тогда ;

4.Выберем произвольное число e. Пусть ;

5.С помощью алгоритма Евклида вычислим число d, удовлетворяющее условию . Получим .

Переходим к этапу распределения ключей.

  1. Назначаем пару {3,9173503} в качестве открытого ключа;
  2. Назначаем пару {6111579,9173503} в качестве закрытого ключа.

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

  1. Выбираем некоторый текст m, который необходимо зашифровать (шифрование будем выполнять с помощью открытого ключа). Пусть .
  1. Шифруем сообщение с использованием открытого ключа получателя: .

.

Заключительным этапом будет этап дешифрования.

  1. Возьмем полученный зашифрованный текст c и дешифруем его с помощью закрытого ключа .

Итак, поскольку , то

.

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

Литература:

  1. RSA [электронный ресурс] — Режим доступа: URL: https://ru.wikipedia.org/wiki/RSA. Дата обращения 06.10.2019.
  2. Бернет С., Пэйн С. Криптография. Официальное руководство RSA Security/ Бернет С., Пэйн С. — Бином, 2002–381с.
  3. Виноградов, И. М. Основы теории чисел: учебное пособие [Текст] / И. М. Виноградов. — 12-е изд. — М.: Лань, 2009. — 176 с.
  4. Коутинхо С. Введение в теорию чисел. Алгоритм RSA/ Коутинхо С. — М.: Постмаркет, 2011 -328с.

Основные термины (генерируются автоматически): RSA, открытый ключ, закрытый ключ, число, криптографическая система, GCHQ, MIT, помощь алгоритма, произвольное число, этап распределения ключей.

Online RSA Encryption, Decryption and Key Generator Tool

RSA (Ривест-Шамир-Адлеман) — это асимметричное шифрование
метод, который использует два разных ключа как открытый и закрытый ключи для выполнения
шифрование и дешифрование. С RSA вы можете зашифровать конфиденциальную информацию с помощью
открытый ключ и соответствующий закрытый ключ используются для расшифровки зашифрованного сообщения.Асимметричное шифрование в основном используется, когда есть 2 разных конечных точки.
задействованы такие как клиент и сервер VPN, SSH и т. д.

Ниже представлен онлайн-инструмент для выполнения шифрования и дешифрования RSA как RSA.
калькулятор.

Для реализации RSA на Java вы можете следовать этому
статья.

Во-первых, нам требуются открытый и закрытый ключи для шифрования и дешифрования RSA. Следовательно,
Ниже приведен инструмент для создания ключа RSA в режиме онлайн. Он генерирует открытый ключ RSA
а также закрытый ключ размером 512 бит, 1024 бит, 2048 бит, 3072 бит и
4096 бит с Base64
закодировано.

По умолчанию закрытый ключ создается в формате PKCS # 8, а открытый ключ создается в X.509 формат.

Шифрование и дешифрование RSA в Интернете

Ниже приведен инструмент для шифрования и дешифрования. Либо вы можете использовать общедоступный / частный
ключи, созданные выше, или предоставить свои собственные открытые / закрытые ключи.

Любое значение частного или открытого ключа, которое вы вводите или которое мы генерируем, не сохраняется в
этот сайт,
этот инструмент предоставляется через URL-адрес HTTPS, чтобы гарантировать, что закрытые ключи не могут быть
украли.

Этот инструмент обеспечивает гибкость шифрования RSA с использованием открытого и закрытого ключей.
вместе с расшифровкой RSA с открытым или закрытым ключом.

Шифрование RSA

Введите обычный текст для шифрования

Введите публичный / частный
ключ

Выбрать тип шифра
RSARSA / ECB / PKCS1Padding
RSA / ECB / OAEPWithSHA-1AndMGF1Padding

Зашифровать

зашифрованный вывод
(Base64):

Руководство по использованию

— Шифрование и дешифрование RSA в Интернете

В первом разделе этого инструмента вы можете сгенерировать открытые или закрытые ключи.Для этого
выберите размер ключа RSA из 515, 1024, 2048 и 4096 бит, нажмите кнопку.
Это сгенерирует для вас ключи.

Для шифрования и дешифрования введите простой текст и укажите ключ. Как шифрование
можно сделать с помощью обоих ключей, вам нужно сообщить инструменту о типе ключа, который вы
поставили с помощью радиокнопки.По умолчанию выбран открытый ключ. Потом,
вы можете использовать тип шифра, который будет использоваться для шифрования. Различные варианты шифратора
являются
ЮАР,
RSA / ECB / PKCS1Padding и
RSA / ECB / OAEPWithSHA-1AndMGF1Padding. Теперь, как только вы нажмете
зашифровать, зашифрованный результат будет показан в текстовом поле чуть ниже
кнопка.

Помните, что зашифрованный результат по умолчанию закодирован в формате base64.

Точно так же и для расшифровки. Здесь вам нужно ввести зашифрованный RSA
текст, и результатом будет простой текст. У вас есть оба варианта расшифровать
шифрование с
открытые и закрытые ключи.

.Теория

Rsa — CTF Wiki

跳转 至

CTF Wiki

Теория RSA

Инициализация поиска

    ctf-вики / ctf-вики

    CTF Wiki

    ctf-вики / ctf-вики

    • Вступление

      Вступление

      • Начиная

      • История CTF

      • Введение в форму конкурса CTF

      • Контент конкурса CTF

      • Сводка опыта автономной атаки и защиты

      • CGC Super Challenge

      • Учебные ресурсы

    • Разное

      Разное

      • Разное Введение

      • Технология сбора информации

      • Анализ кода

        Анализ кода

        • Обычно используемое кодирование в области коммуникации

        • Компьютерное кодирование

        • Часто используемые кодировки в реальном мире

      • Судебная стеганография

      • Анализ изображений

        Анализ изображений

        • Введение в анализ изображений

        • PNG

        • JPG

        • Гифка

      • Анализ пакетов трафика

        Анализ пакетов трафика

        • Введение в анализ пакетов трафика

        • Восстановление файла PCAP

        • Анализ протокола

          Анализ протокола

          • Обзор анализа протокола

          • Wireshark

          • HTTP

          • HTTPS

          • FTP

          • DNS

          • ВАЙ-ФАЙ

          • USB

        • Извлечение данных

      • Анализ сжатого пакета

        Анализ сжатого пакета

        • ZIP формат

        • Формат RAR

      • Аудио стеганография

    .

    RSA (шаг за шагом) — CrypTool Portal

    Этот модуль демонстрирует пошаговое шифрование или дешифрование.
    методом RSA.
    Отправитель использует открытый ключ получателя для
    шифрование; получатель использует связанный с ним закрытый ключ для
    расшифровать.

    Основные факторы

    Безопасность RSA основана на том, что его легко
    вычислить произведение n двух больших простых чисел p и
    q .
    Однако определить только по продукту очень сложно.
    n два простых числа, которые дают произведение.Это разложение также называется факторизацией n .

    В качестве отправной точки для RSA выберите два простых числа p и
    q .

    Чтобы алгоритм работал, два простых числа должны быть разными.

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

    Открытый ключ

    Продукт n также называется модулем в методе RSA.
    Открытый ключ состоит из модуля n и экспоненты
    и .

    Этот e может быть предварительно выбран и одинаков для всех
    участников.

    Секретный ключ

    RSA использует φ-функцию Эйлера n для вычисления
    Секретный ключ.
    Это определяется как

    φ ( n ) = ( p — 1) ×
    ( кв. — 1)

    Здесь используется, что p и q разные.В противном случае функция φ рассчитывалась бы иначе.

    Для RSA важно, чтобы значение функции φ было
    взаимно проста с e (наибольший общий делитель должен быть равен 1).

    Для определения значения φ ( n ) недостаточно
    знать н .
    Только со знанием p и q мы можем
    эффективно определить φ ( n ).

    Секретный ключ также состоит из n и d с
    свойство, что e × d кратно
    φ ( n ) плюс один.

    В формулах должно применяться следующее:

    e × d = 1 (mod φ ( n ))

    В данном случае выражение mod означает равенство по отношению к
    остаточный класс. Это x = y (mod z ), если и
    только если есть целое число a с x y =
    z × a .

    Для выбранных значений p , q и e получаем
    d как:

    Это d всегда можно определить (если было выбрано e
    с ограничением, описанным выше) — например, с
    расширенный алгоритм Евклида.

    Шифрование и дешифрование

    Внутренне этот метод работает только с числами (без текста), которые
    находятся между 0 и n .

    Шифрование сообщения м (номер) открытым ключом
    ( n , e ) рассчитывается:

    м ‘: = м e (мод. n )

    Расшифровка закрытым ключом ( n , d ) выполняется
    аналогично с

    м ‘: = м’ d (модель n ).

    Это

    м » = м e × d (мод.
    ).

    RSA теперь использует свойство, которое

    x a = x b
    (мод. n )

    если

    a = b (mod φ ( n ))

    Поскольку e и d были выбраны надлежащим образом, это

    м » = м .

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

    сообщений

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

    Библиотека б / у

    Эта страница использует библиотеку
    BigInteger.js
    работать с большими числами.

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

    CTOAUTHORS: Timm Knape (спасибо Bernhard
    Esslinger за обзор)

    .

    Атака RSA ради развлечения и CTF очков — часть 1

    Введение

    RSA — моя любимая криптосистема. 🙂 Это просто и эффективно.

    В этой серии я постараюсь пройти через все известные мне атаки на RSA, которые полезны для решения задач CTF.
    Я не собираюсь давать вам сценарии, которые сделают всю работу за вас, а просто объясню, как работают атаки. Цель этой серии статей — понять, какие атаки вы используете и какая из них наиболее подходит в зависимости от задачи.Я постараюсь быть дружелюбным к новичкам и повторяться вначале, но потом я буду предполагать, что читатель усвоил концепции.

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

    Как простая математика может сохранить конфиденциальность ваших данных

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

    А вот и самая важная часть, это нужно полностью понимать, чтобы понимать атаки, которые будут описаны.
    Модуль выбирается из двух простых чисел:

    с простыми целыми числами и (тщательно выбирается)

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

    Примечание. Теперь в реальном RSA вы используете не тотальную функцию Эйлера, а скорее общую функцию Кармайкла.

    Затем необходимо проверить эти 2 условия:

    и, значит, и взаимно просты.

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

    Примечание: ключи закодированы в формате PEM, но это не имеет отношения к этому примеру.

    Процесс шифрования

    Допустим, вы хотите зашифровать это сообщение своим открытым ключом: «Номер моей кредитной карты — 1337».

    Открытый ключ:

     n = 30994968412821274638126108542140224647370292100079091608343041083209715023181825537637957453183815788151099869840363450721
    е = 65537 

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

     >>> "Номер моей кредитной карты 1337" .encode ('шестнадцатеричный')
    '4d79206372656469742063617264206e756d6265722069732031333337'
    >>> m = 0x4d79206372656469742063617264206e756d6265722069732031333337
    >>> м
    2088672004503895363248317162088008321096572194316716175821104101929783L 

    Затем вы вычисляете, где находится результирующий зашифрованный текст.Только вы (у кого есть закрытый ключ) сможете его расшифровать. По крайней мере, теоретически, потому что об этом и идет речь в этой серии: об атаке на RSA

     >>> c = pow (m, e, n)
    >>> c
    374080828312674378947365821688800423775615197038542211223070217521467041504557851181342878693752301699652110

    52458274L

    Процесс расшифровки

    Чтобы расшифровать зашифрованный текст, вам необходимо знать закрытый ключ, соответствующий открытому ключу, используемому для его шифрования. Закрытый ключ:

     n = 30994968412821274638126108542140224647370292100079091608343041083209715023181825537637957453183815788151099869840363450721
    d = 10949944362147351445695313961215384000802056441294706923101734114824865877971959648683318864984560110549528540371119079473 

    Когда у вас есть все, вы выполняете ту же операцию, что и для шифрования, за исключением того, что вы используете в качестве экспоненты вместо:

    где — результирующий открытый текст.

     >>> t = pow (c, d, n)
    >>> т
    2088672004503895363248317162088008321096572194316716175821104101929783L
    >>> шестнадцатеричный (t)
    '0x4d79206372656469742063617264206e756d6265722069732031333337L'
    >>> "4d79206372656469742063617264206e756d6265722069732031333337" .decode ('шестнадцатеричный')
    «Номер моей кредитной карты 1337» 

    Ключевая структура

    Я уже говорил вам в начале, что ключи кодируются в формате PEM. Вот как они выглядят на самом деле:

     ----- НАЧАТЬ ПУБЛИЧНЫЙ КЛЮЧ -----
    MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAIw / U51Fghh6WumZQjg9l3a6AjFZ + xm2
    x2 + 9ja + 8n8Yg95Hbxsp9vCpwlIol1A5wMo6p / hNlxzAE3 / cY08eKzDMCAwEAAQ ==
    ----- КОНЕЦ ОБЩЕСТВЕННОГО КЛЮЧА ----- 
     ----- НАЧАТЬ ЧАСТНЫЙ КЛЮЧ RSA -----
    MIIBOQIBAAJBAIw / U51Fghh6WumZQjg9l3a6AjFZ + xm2x2 + 9ja + 8n8Yg95Hbxsp9
    vCpwlIol1A5wMo6p / hNlxzAE3 / cY08eKzDMCAwEAAQJAJearQxJYwSK31O9dDPPg
    Le7AzvOBP4a8yP7R / o8cIp + 3XdCXzuUreFzTWTXIg76tohg8cQb77HT / jVo2rLXa
    AQIhAOrtFkJ0So2NZIp4xBPLqFozaSJNti8Yx8w1IOWoS2szAiEAmNQCPrBaB6p4
    heIDYgaTYpJa4gbw3tLe82AAKzFLGwECIE / ZA37Uzd4s16ZlA6gCyZbW8h4zUd / S
    GV6kFClauT + XAiBZuddbkNQ6vfYmvIw56Bxt + flLzMFsQSfOgaV3tmgfAQIgKW7C
    LI1 + rBn3TvmyLMZ7 + 3TEtVeTVRgabLWyOUjmv7w =
    ----- КОНЕЦ ЧАСТНОГО КЛЮЧА RSA ----- 

    Я не буду подробно описывать используемый формат.PEM — это просто данные ASN.1, помещенные между заголовками. ASN.1 — это форматированное двоичное представление данных, в котором для окончательного кодирования используется base64.

    Вы можете использовать онлайн-декодер, openssl или python для извлечения данных из ключей.

     из Crypto.PublicKey импорт RSA
    
    f = open ('public.pem', 'r')
    ключ = RSA.importKey (f.read ())
    печать (key.n)
    печать (ключ. e) 

    Давайте проверим, что открытый ключ содержит только и.

    Это ASN вверху.1 структура открытого ключа. Есть некоторые метаданные, указывающие тип шифрования, а в конце есть два целых числа: 512-битное и классическое.

    Я говорил вам, что закрытый ключ содержит больше, чем просто и. Это синтаксис ASN.1 для PKCS1

    Version :: = INTEGER {two-prime (0), multi (1)}
    (ОГРАНИЧЕНО
    {- версия должна быть multi, если присутствует otherPrimeInfos -})

    RSAPrivateKey :: = SEQUENCE {
    version Version,
    modulus INTEGER, — n
    publicExponent INTEGER, — e
    privateExponent INTEGER, — d
    prime1 INTEGER, — p
    prime2 INTEGER, — q
    exponent1 INTEGER, — d mod (p -1)
    exponent2 INTEGER, — d mod (q-1)
    коэффициент INTEGER, — (инверсия q) mod p
    otherPrimeInfos OtherPrimeInfos ДОПОЛНИТЕЛЬНО
    }

    Вы можете попробовать это сами, как мы это сделали с открытым ключом 🙂

    факторизация открытого ключа

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

    Вы можете выполнить атаку полным перебором, чтобы определить возможное. Это можно сделать, когда он маленький (менее 256 бит). Рекомендуется использовать длину не менее 2048 бит.

    Даже если вам нужно разбить более крупный, иногда он известен, и его факторы уже находятся в базе данных!

    Пример:

     п = 9567648541342714273618397561214215397959 

    это известный коэффициент:

     p = 70636931
    q = 135448247905089679980836052478189 

    Первое, что нужно попробовать, — это проверить, известно ли что-то, это быстрая проверка, которая может сэкономить вам много времени.😉

    Имейте в виду, что это очень просто, и обычно вы не можете разложить модуль на множители.

    Что вы можете сделать, если вы не можете разложить модуль на множители? Просто злоупотребляйте потоками в реализации или выбором значений! Есть так много способов испортить реализацию RSA

    Общий модуль

    Как внешний злоумышленник

    В этом сценарии представьте, что несколько человек общаются по общедоступной сети. Поскольку они не хотели создавать разные модули для каждого человека, они решили, что у всех будет один и тот же модуль.
    У каждого пользователя будет уникальный открытый ключ (,) и уникальный закрытый ключ (,).
    Вам удалось перехватить важное сообщение, отправленное пользователям A и B. Но поскольку оно зашифровано, у вас есть и. Как его восстановить?

    Compute, он должен быть равен 1. Используя личность Безу, мы знаем, что они существуют, и так далее.
    Вы можете вычислить и использовать расширенный алгоритм Евклида.

    и

    .

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

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