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

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

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

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

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

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

Шифрование

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Важно! Сегодня алгоритм RSA проигрывает в скорости большинству альтернативных способов блокового шифрования. Так DES минимум в сто раз быстрее при аппаратной реализации.

Как взламывают алгоритм RSA?

RSA – это изученный метод шифрования, который можно взломать несколькими способами. Самым эффективным является поиск закрытого ключа, который позволяет открыть информацию из открытого ключа. Позволяет получать всю информацию, которая была зашифрованной, также внедряться в код подписи, подделывая ее. Для проведения атаки необходимо найти сомножители общего модуля n – p и q. Благодаря данным p, q, e, хакер может без проблем получить частный показатель d. Основная трудность метода – поиск сомножителей. В основе безопасности лежит схема определения множителей, что позволяет создать задачу без эффективных вариантов решения.

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

Следующая возможность взлома заключается в поиске способа определения корня степени e из mod n. Если злоумышленник получит корень из уравнения C = Me, то он получает доступ к зашифрованным сообщениям и возможность подделки подписи без знания приватного ключа. Сегодня не получается узнать схему, благодаря которой алгоритм взламывается подобным способом.

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

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

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

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

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

Что собой представляют «устойчивые числа»?

Для защиты шифрования должны использоваться устойчивые числа p и q. Они необходимы для выявления свойств, затрудняющих получение множителей. Одним из таких являются главные делители: p – 1 и p + 1. Это позволяет создать защиту от определения множителей различными методами, которые можно применять только в отношении небольших делителей. Использование устойчивых чисел даже закреплено в правилах некоторых стандартов, например, ANSI X9.31.

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

Важно! Если будут разработаны дополнительные способы факторинга, то в RSA можно будет увеличить количество символов в числе для усложнения задачи.

Рекомендованный размер ключа

При определении размера ключа требуется опираться от модуля n, являющегося суммой p и q, которые для корректной работы должны иметь примерно равную длину. Если модуль равен 524 битам, то приблизительный размер 262 бита.

  1. M = (p+q)/2
  2. Если p < q, получаем 0 ≤ м – sqrt (n) ≤ (q — p)2/8p.

Так как p = M*(± ), то значения p и q можно без труда найти, если разность чисел небольшая.

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

Логарифм Rivest стал основой для проведения тестов по безопасности ключей в зависимости от их длины. Полученные данные можно применять и к RSA-шифрованию. Обзор защиты проводится на основании способов определения множителей, которые улучшаются благодаря привлечению дополнительных вычислительных ресурсов. В 1997 году 512-битный ключ можно было вскрыть только при помощи оборудования за 1 000 000 USD, для чего потребовалось бы 8 месяцев. Этот же ключ через два года, можно было вскрыть при помощи того же оборудования, но уже за 7 месяцев. Это показывает, как быстро технология приходит в «негодность» за счет срока своей работы.

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

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

Множество простых чисел

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

Интересно! Ключ длиной 512 битов включает в себя 10150  возможных значений.

Как это работает?

В реальности защищенная передача сообщений возможна при использовании двух криптосистем: RSA и DES. Алгоритм процесса:

  1. Пользователь «А» отправляет сообщение пользователю «Б».
  2. Сперва сообщение шифруется по алгоритму DES.
  3. Ключ DES шифруется по алгоритму RSA, принадлежащему получателю «Б» и находящемуся в открытом доступе.
  4. Сообщение и ключ конвертируются в RSA, после чего отправляются пользователю «Б».
  5. Пользователь «Б» может расшифровать полученное письмо при помощи приватного RSA ключа, а доступ к самому тексту сообщения можно получить при использовании DES ключа.

Пример работы

Работа шифрования заключается в трех этапах:

  1. Подготовка ключей. Генерируются публичный и приватный ключ.
  2. Шифрование на основе публичного ключа, сгенерированного при подготовке.
  3. Дешифрование при помощи публичного и приватного ключа.

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

Понравилась статья? Поделиться с друзьями:
Добавить комментарий

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: