Шифрование при помощи алгоритма rsa

Алгоритм цифровой подписи Эль Гамаля (EGSA)

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

Что бы генерировать пару ключей, нужно выбрать простое целое число P и G, причем G < P. Получатель и отправитель подписанного документа используют одинаковые большие числа P — (~10308 = ~21024) и G (~10154 = ~1512) которые не секретные. Отправитель выбирает случайное целое число X, 1 < X £ (P — 1), и вычисляет: Y = GX mod P;

Число Y является открытым ключом, который используется для проверки подписи отправителя. Число Х является секретным ключом отправителя для подписи документов. Что бы подписать сообщение М, сначала нужно что бы отправитель захэшировал его с помощью хэш-функции h в целое число m: m = h(M), 1 < m < (P — 1), и генерирует случайное целое число К, 1 < K < (P — 1). такое что К и (P — 1) будут взаимно простыми. Потом отправитель вычисляет целое число a: a = GK mod P; используя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b: m = X * a + K * b (mod (P — 1)); Пара чисел (a, b) образуют цифровую подпись S: S = (a, b);

Тройка чисел (M, a, b) транспортируется получателю, в то время как пара чисел (X, K) держится в секрете. Получатель получив сообщение (M, a, b) должен вычислить число m: m = h(M). затем получатель вычисляет: A = Ya ab mod (P), и признает сообщение M подлинным, если — A = Gm mod (P). Можно строго математически доказать, что последнее равенство будет равно тогда, когда подпись S под документом M получена с помощью именно секретного ключа X, из которого был получен открытый ключ Y. Нужно отметить, что процедура каждой подписи требует нового значения К, и выбирается случайным образом.

Схема Эль Гамаля является типичным примером, который разрешает пересылку сообщений М в открытой форме вместе с аутентификатором (a, b). Такая схема имеет преимущества перед схемой ЭЦП RSA:

  • Для одинакового уровня стойкости, алгоритм Эль Гамаля использует целые числа короче на 25%, что уменьшает сложность вычислений почти в 2 раза.
  • Выбор модуль Р прост, нужно убедится что число простое, и что у числа (Р — 1_ есть большой простой множитель.
  • Схема создания подписи по алгоритму Эль Гамаля не разрешает вычислять ЭЦП под новыми сообщениями без знания секретного ключа.

К недостаткам можно отнести то, что подпись получается в 1,5 раза больше чем RSA.

Настройка TCP/IP на RSAConfigure TCP/IP on RSA

  1. В задачи начальной настройки щелкните Настройка сети.In Initial Configuration Tasks, click Configure networking.

  2. В разделе Сетевые подключения щелкните правой кнопкой мыши Подключение по локальной сети и выберите пункт Свойства.In Network Connections, right-click Local Area Connection, and then click Properties.

  3. Щелкните пункт IP версия 4 (TCP/IPv4) и нажмите кнопку Свойства.Click Internet Protocol Version 4 (TCP/IPv4), and then click Properties.

  4. Выберите вариант Использовать следующий IP-адрес.Click Use the following IP address. В поле IP-адрес введите 10.0.0.5.In IP address, type 10.0.0.5. В поле Маска подсети введите 255.255.255.0.In Subnet mask, type 255.255.255.0. В качестве шлюза по умолчанию введите 10.0.0.2.In Default Gateway, type 10.0.0.2. Щелкните использовать следующие адреса DNS-серверов в поле Предпочитаемый DNS-сервер, введите 10.0.0.1.Click Use the following DNS server addresses, in Preferred DNS server, type 10.0.0.1.

  5. Нажмите кнопку «Дополнительно» и перейдите на вкладку «DNS».Click Advanced, and then click the DNS tab.

  6. В качестве DNS-суффикса для этого подключения введите Corp.contoso.com, а затем дважды нажмите кнопку ОК .In DNS suffix for this connection, type corp.contoso.com, and then click OK twice.

  7. В диалоговом окне Свойства подключения к локальной сети нажмите кнопку Закрыть.On the Local Area Connection Properties dialog box, click Close.

  8. Закройте окно Сетевые подключения.Close the Network Connections window.

Установка токена программного обеспечения RSA SecurID на компьютере КЛИЕНТ1Install RSA SecurID software token on CLIENT1

Используйте эту процедуру для установки токена программного обеспечения SecurID на компьютере КЛИЕНТ1.Use this procedure to install SecurID software token on CLIENT1.

Установка токена программного обеспечения SecurIDInstall SecurID software token

  1. На компьютере КЛИЕНТ1 создайте папку К:\РСА Files.On the CLIENT1 computer, create the folder C:\RSA Files. Скопируйте файл Software_Tokens.zip из установки К:\РСА на компьютере RSA в файлы К:\РСА.Copy the file Software_Tokens.zip from C:\RSA Installation on the RSA computer to C:\RSA Files. Извлеките файл User1_000031701832. СДТИД в файлы К:\РСА на компьютере КЛИЕНТ1.Extract the file User1_000031701832.SDTID to C:\RSA Files on CLIENT1.

  2. Получите доступ к источнику носителя маркера программного обеспечения RSA SecurID и дважды щелкните RSASECURIDTOKEN410 в папке клиентского приложения SecurID софтваретокен , чтобы запустить установку RSA SecurID.Access the RSA SecurID software token media source, and double-click RSASECURIDTOKEN410 in the SecurID SoftwareToken client app folder to start the RSA SecurID installation. Если появится сообщение Open File-Security Warning , нажмите кнопку Run (выполнить).If the Open File — Security Warning message appears, then click Run.

  3. В диалоговом окне мастера маркеров программного обеспечения RSA SecurID нажмите кнопку Далее дважды.On the RSA SecurID Software Token — InstallShield Wizard dialog click Next twice.

  4. Примите условия лицензионного соглашения и нажмите кнопку Далее.Accept the license agreement, and click Next.

  5. В диалоговом окне тип установки выберите обычный, нажмите кнопку Далее и нажмите кнопку установить.On the Setup Type dialog select Typical, click Next, and click Install.

  6. Если появится диалоговое окно контроля учетных записей, подтвердите, что отображаемое в нем действие именно то, которое требуется, и нажмите кнопку Да.If the User Account Control dialog box appears, confirm that the action it displays is what you want, and then click Yes.

  7. Установите флажок запустить токен программного обеспечения RSA SecurID и нажмите кнопку Готово.Select the Launch RSA SecurID Software Token check box, and click Finish.

  8. Щелкните Импорт из файла.Click Import from File.

  9. Нажмите кнопку Обзор, выберите к:\рса Files \ USER1_000031701832. сдтид и нажмите кнопку Открыть.Click Browse, select C:\RSA Files\User1_000031701832.SDTID, and click Open.

  10. Щелкните дважды ОК.Click OK twice.

Использование криптосистемы RSA в настоящее время

Криптосистема RSA используется в самых различных продуктах, на различных платформах и во многих отраслях. В настоящее время криптосистема RSA встраивается во многие коммерческие продукты, число которых постоянно увеличивается. Также ее используют операционные системы Microsoft, Apple, Sun и Novell. В аппаратном исполнении RSA алгоритм применяется в защищенных телефонах, на сетевых платах Ethernet, на смарт-картах, широко используется в криптографическом оборудовании. Кроме того, алгоритм входит в состав всех основных протоколов для защищенных коммуникаций Internet, в том числе S/MIME, SSL и S/WAN, а также используется во многих учреждениях, например, в правительственных службах, в большинстве корпораций, в государственных лабораториях и университетах. На осень 2000 года технологии с применением алгоритма RSA были лицензированы более чем 700 компаниями.

Технологию шифрования RSA BSAFE используют около 500 миллионов пользователей всего мира. Так как в большинстве случаев при этом используется алгоритм RSA, то его можно считать наиболее распространенной криптосистемой общего (public) ключа в мире и это количество имеет явную тенденцию к увеличению по мере роста Internet.

Общее

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

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

В нашем современном криминальном обществе, ни одно из перечисленных свойств на все 100% не реализуются. Можно и подделать подпись, и убрать но это реализуется не просто и быть пойманным есть риск. Существуют также дополнительные вопросы, при отправки документа по почте. Любой документ можно скопировать вместе с подписью. Также можно внести из мнения после подписания документа. Для ликвидации таких угроз используют электронно цифровую подпись. Подделать подпись очень сложно, так как она создается на основе большого объема математических операций. Цифровая подпись может хранится вместе с документом, или быть отдельно от него.

Электронно цифровая подпись — это метод который позволяет на основе реализации криптографических средств определить автора и подлинность документа. Преимущества электронно цифровой подписи:

  • большая степень защиты от подделок
  • идентификация принадлежности подписи на основе характеристик
  • сильная связь с подписываемым документом

Возможные угрозы которые наносят ущерб развитию электронного документооборота показаны на рис.1. Эти угрозы:

  • отказ от факта получения документа или авторства
  • изменение документа
  • замена документа
  • замена имени
  • повторная рассылка документов

Рисунок — 1

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

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

Проверка подписейVerifying Signatures

Для проверки того, подписаны ли данные определенной стороной, необходимы следующие сведения:To verify that data was signed by a particular party, you must have the following information:

  • открытый ключ стороны, подписавшей данные;The public key of the party that signed the data.

  • цифровая подпись;The digital signature.

  • подписанные данные;The data that was signed.

  • хэш-алгоритм, который использовался при создании подписи.The hash algorithm used by the signer.

Для проверки подписи, созданной с помощью класса RSAPKCS1SignatureFormatter , используется класс RSAPKCS1SignatureDeformatter .To verify a signature signed by the RSAPKCS1SignatureFormatter class, use the RSAPKCS1SignatureDeformatter class. Классу RSAPKCS1SignatureDeformatter необходимо предоставить открытый ключ подписывающей стороны.The RSAPKCS1SignatureDeformatter class must be supplied the public key of the signer. Для RSA потребуются значения модуля и экспоненты, чтобы указать открытый ключ.For RSA, you will need the values of the modulus and the exponent to specify the public key. (Эти значения должны быть предоставлены стороной, создавшей пару открытого и закрытого ключей.) Сначала создайте RSA объект для хранения открытого ключа, который будет проверять подпись, а затем инициализирует RSAParameters структуру значениями модуля и экспоненты, задающих открытый ключ.(The party that generated the public/private key pair should provide these values.) First create an RSA object to hold the public key that will verify the signature, and then initialize an RSAParameters structure to the modulus and exponent values that specify the public key.

В следующем примере кода показано создание структуры RSAParameters .The following code shows the creation of an RSAParameters structure. Свойству присваивается байтовый массив , а свойству — байтовый массив .The property is set to the value of a byte array called and the property is set to the value of a byte array called .

После создания RSAParameters объекта можно инициализировать новый экземпляр класса реализации, применяя значения, RSA указанные в RSAParameters .After you have created the RSAParameters object, you can initialize a new instance of the RSA implementation class to the values specified in RSAParameters. RSAЭкземпляр, в свою очередь, передается конструктору объекта RSAPKCS1SignatureDeformatter для передачи ключа.The RSA instance is, in turn, passed to the constructor of an RSAPKCS1SignatureDeformatter to transfer the key.

Этот процесс показан в приведенном ниже примере.The following example illustrates this process. В этом коде и — байтовые массивы, предоставленные удаленной стороной.In this example, and are arrays of bytes provided by a remote party. Удаленная сторона подписала объект с помощью алгоритма SHA1, создающего цифровую подпись .The remote party has signed the using the SHA1 algorithm, producing the digital signature . RSAPKCS1SignatureDeformatter.VerifySignatureМетод проверяет, является ли цифровая подпись допустимой и использовалась для подписывания .The RSAPKCS1SignatureDeformatter.VerifySignature method verifies that the digital signature is valid and was used to sign the .

Из-за проблем с алгоритмом SHA1 рекомендуется использовать SHA256 или более высокий уровень.Due to collision problems with SHA1, we recommend SHA256 or better. Однако если для создания подписи использовался алгоритм SHA1, для проверки подписи необходимо использовать SHA1.However, if SHA1 was used to create the signature, you have to use SHA1 to verify the signature.

Если подпись действительна, этот фрагмент кода выдаст сообщение «», а в противном случае — сообщение «».This code fragment will display «» if the signature is valid and «» if it is not.

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

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

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

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

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

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

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

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

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

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

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

Взлом криптосистемы RSA

Существует несколько способов взлома RSA. Наиболее эффективная атака — найти секретный ключ, соответствующий необходимому открытому ключу. Это позволит нападающему читать все сообщения, зашифрованные открытым ключом, и подделывать подписи. Такую атаку можно провести, найдя главные сомножители (факторы) общего модуля n — p и q. На основании p, q и e (общий показатель) нападающий может легко вычислить частный показатель d. Основная сложность в поиске главных сомножителей (факторинг) n. Безопасность RSA зависит от разложения на сомножители (факторинга), что является трудной задачей, не имеющей эффективных способов решения.

Фактически, задача восстановления секретного ключа эквивалентна задаче разложения на множители (факторинга) модуля: можно использовать d для поиска сомножителей n, и наоборот, можно использовать n для поиска d (см. подпп. 2.3.4 и 2.3.5 о факторинге). Надо отметить, что усовершенствование вычислительного оборудования само по себе не уменьшит стойкость криптосистемы RSA, если ключи будут иметь достаточную длину. Фактически же совершенствование оборудования увеличивает стойкость криптосистемы (см. подп. 2.3.5).

Другой способ взломать RSA состоит в том, чтобы найти метод вычисления корня степени e из mod n. Поскольку С = Me mod n, то корнем степени e из mod n является сообщение M. Вычислив корень, можно вскрыть зашифрованные сообщения и подделывать подписи, даже не зная частный ключ. Такая атака не эквивалентна факторингу, но в настоящее время неизвестны методы, которые позволяют взломать RSA таким образом. Однако в особых случаях, когда на основе одного и того же показателя относительно небольшой величины шифруется достаточно много связанных сообщений, есть возможность вскрыть сообщения. Упомянутые атаки — единственные способы расшифровать все сообщения, зашифрованные данным ключом RSA.

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

Самое простое нападение на отдельное сообщение — атака по предполагаемому открытому тексту. Нападающий, имея зашифрованный текст, предполагает, что сообщение содержит какой-то определенный текст (например, “Юстас — Алексу”), затем шифрует предполагаемый текст открытым ключом получателя и сравнивает полученный текст с имеющимся зашифрованным текстом. Такую атаку можно предотвратить, добавив в конец сообщения несколько случайных битов. Другая атака на единственное сообщение применяется в том случае, если отправитель посылает одно и то же сообщение M трем корреспондентам, каждый из которых использует общий показатель e = 3. Зная это, нападающий может перехватить эти сообщения и расшифровать сообщение M.

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

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

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

Что представляет собой алгоритм?

Дата создания алгоритма RSA 1977 год. Аббревиатура придумана на основе фамилий разработчиков: R – Ривест, S – Шамир, A – Адлеман. Первый буквы и стали являться наименованием для шифрования и технологии в целом.

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

Шифрование

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

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

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

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

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

Цифровая подпись

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

Благодаря такой основе системе, подпись конфиденциальна. Вся содержащаяся информация сторонах надежно защищена.

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

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

Скорость работы

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

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

  • k2 – процедуры с публичным ключом;
  • k3 – процедуры с приватным ключом;
  • k4 – для создания шифров.

Для ускорения проведения процедур на основе RSA постоянно применяются новые разработки. В качестве таковой мог стать способ «быстрого умножения», который позволял уменьшить число требуемых шагов для успешного и безопасного выполнения операции. БПФ (FFT) не прижилось, ведь для реализации требуется сложное ПО, а для быстрой работы понадобится сделать размер ключей идентичным.

Оцените статью
Рейтинг автора
5
Материал подготовил
Илья Коршунов
Наш эксперт
Написано статей
134
Добавить комментарий