Rivest-Shamir-Adleman

Алгоритм RSA

Rivest-Shamir-Adleman

В этой статье рассмотрим еще один один алгоритм шифрования – алгоритм RSA. Будет приведено описание и программная реализация на языке программирования C#.

Алгоритм RSA. Описание

RSA (аббревиатура от фамилий создателей: Rivest, Shamir и Adleman) – один из самых популярных алгоритмов шифрования. Сначала приведем несколько определений:

mod – операция взятия остатка от деления.

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

Шаги алгоритма RSA

Теперь опишем последовательность шагов алгоритма RSA:

  • выбрать два больших простых числа p и q;
  • вычислить: n = p ⋅ q, m = (p – 1) ⋅ (q – 1);
  • выбрать случайное число d, взаимно простое с m;
  • определить такое число e, для которого является истинным выражение: (e ⋅ d) mod (m) = 1;
  • числа e и n – это открытый ключ, а числа d и n – это закрытый ключ;

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

  • разбить шифруемый текст на блоки, каждый из которых может быть представлен в виде числа M(i);

Обычно блок берут равным одному символу и представляют этот символ в виду числа – его номера в алфавите или кода в таблице символов (например ASCII или Unicode).

  • шифрование алгоритмом RSA производится по формуле: C(i) = (M(i)e) mod n;
  • расшифровка сообщения производится с помощью формулы: M(i) = (C(i)d) mod n.

Алгоритм RSA. Программная реализация

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

Рисунок 1. Пользовательский интерфейс программы

В программе будем использовать следующий алфавит:

char[] characters = new char[] { '#', 'А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ё', 'Ж', 'З', 'И', 'Й', 'К', 'Л', 'М', 'Н', 'О', 'П', 'Р', 'С', 'Т', 'У', 'Ф', 'Х', 'Ц', 'Ч', 'Ш', 'Щ', 'Ь', 'Ы', 'Ъ', 'Э', 'Ю', 'Я', ' ', '1', '2', '3', '4', '5', '6', '7', '8', '9', '0' };

char[] characters = new char[] { '#', 'А', 'Б', 'В', 'Г', 'Д', 'Е', 'Ё', 'Ж', 'З', 'И',                                                'Й', 'К', 'Л', 'М', 'Н', 'О', 'П', 'Р', 'С',                                                 'Т', 'У', 'Ф', 'Х', 'Ц', 'Ч', 'Ш', 'Щ', 'Ь', 'Ы', 'Ъ',                                                'Э', 'Ю', 'Я', ' ', '1', '2', '3', '4', '5', '6', '7',

Число M(i) для конкретной буквы будет равно её номеру в массиве characters[].

Приведем код кнопки “Зашифровать”:

private void buttonEncrypt_Click(object sender, EventArgs e){ if ((textBox_p.Text.Length > 0) && (textBox_q.Text.Length > 0)) { long p = Convert.ToInt64(textBox_p.Text); long q = Convert.ToInt64(textBox_q.Text); if (IsTheNumberSimple(p) && IsTheNumberSimple(q)) { string s = «»; StreamReader sr = new StreamReader(«in.txt»); while (!sr.EndOfStream) { s += sr.ReadLine(); } sr.Close(); s = s.ToUpper(); long n = p * q; long m = (p — 1) * (q — 1); long d = Calculate_d(m); long e_ = Calculate_e(d, m); List result = RSA_Endoce(s, e_, n); StreamWriter sw = new StreamWriter(«out1.txt»); foreach (string item in result) sw.WriteLine(item); sw.Close(); textBox_d.Text = d.ToString(); textBox_n.Text = n.ToString(); Process.Start(«out1.txt»); } else MessageBox.Show(«p или q — не простые числа!»); } else MessageBox.Show(«Введите p и q!»);}

private void buttonEncrypt_Click(object sender, EventArgs e)    if ((textBox_p.Text.Length > 0) && (textBox_q.Text.Length > 0))        long p = Convert.ToInt64(textBox_p.Text);        long q = Convert.ToInt64(textBox_q.Text);        if (IsTheNumberSimple(p) && IsTheNumberSimple(q))            StreamReader sr = new StreamReader(«in.txt»);            long m = (p — 1) * (q — 1);            long e_ = Calculate_e(d, m);            List result = RSA_Endoce(s, e_, n);            StreamWriter sw = new StreamWriter(«out1.txt»);            foreach (string item in result)            textBox_d.Text = d.ToString();            textBox_n.Text = n.ToString();            Process.Start(«out1.txt»);            MessageBox.Show(«p или q — не простые числа!»);        MessageBox.Show(«Введите p и q!»);

И кнопки “Расшифровать”:

private void buttonDecipher_Click(object sender, EventArgs e){ if ((textBox_d.Text.Length > 0) && (textBox_n.Text.Length > 0)) { long d = Convert.ToInt64(textBox_d.Text); long n = Convert.ToInt64(textBox_n.Text); List input = new List(); StreamReader sr = new StreamReader(«out1.txt»); while (!sr.EndOfStream) { input.Add(sr.ReadLine()); } sr.Close(); string result = RSA_Dedoce(input, d, n); StreamWriter sw = new StreamWriter(«out2.txt»); sw.WriteLine(result); sw.Close(); Process.Start(«out2.txt»); } else MessageBox.Show(«Введите секретный ключ!»);}

private void buttonDecipher_Click(object sender, EventArgs e)    if ((textBox_d.Text.Length > 0) && (textBox_n.Text.Length > 0))        long d = Convert.ToInt64(textBox_d.Text);        long n = Convert.ToInt64(textBox_n.Text);        List input = new List();        StreamReader sr = new StreamReader(«out1.txt»);            input.Add(sr.ReadLine());        string result = RSA_Dedoce(input, d, n);        StreamWriter sw = new StreamWriter(«out2.txt»);        Process.Start(«out2.txt»);        MessageBox.Show(«Введите секретный ключ!»);

Теперь покажем код остальных методов.

Проверка: является ли число простым?

private bool IsTheNumberSimple(long n){ if (n < 2) return false; if (n == 2) return true; for (long i = 2; i < n; i++) if (n % i == 0) return false; return true;}

private bool IsTheNumberSimple(long n)    for (long i = 2; i

Источник: https://vscode.ru/prog-lessons/algoritm-rsa.html

RSA-шифрование. Описание и реализация алгоритма RSA

Rivest-Shamir-Adleman

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

Ее основное отличие от подобных сервисов в том, что ключ шифрования является открытым и отличается от ключа дешифрования, который держится в секрете.

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

История создания

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

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

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

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

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

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

Идея асимметричного ключа криптосистемы приписывается Диффи и Хеллману, которые опубликовали концепцию в 1976 году, представив цифровые подписи и попытавшись применить теорию чисел.

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

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

Ривест, Ади Шамир и Адлеман в Массачусетском технологическом институте предприняли несколько попыток в течение года, чтобы создать однонаправленную функцию, которую трудно раскодировать.

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

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

Эцп и открытый ключ

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

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

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

В чем суть алгоритма?

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

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

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

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

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

Шифрование файлов RSA и слабые места

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

Поскольку RSA-шифрование является детерминированным алгоритмом (т.е.

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

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

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

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

Безопасность криптосистемы RSA и шифрование информации основаны на двух математических задачах: проблемы разложения на множители больших чисел и собственно проблемы RSA. Полное раскрытие шифротекста и ЭЦП в RSA считается недопустимым на том предположении, что обе эти проблемы невозможно разрешить в совокупности.

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

Автоматизация

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

Большинство реализаций алгоритма многопоточные, что позволяет Yafu в полной мере использовать мульти- или много многоядерные процессоры (в том числе SNFS, SIQS и ECM). Прежде всего, это управляемый инструмент командной строки.

Время, затраченное на поиск фактора шифрования с использованием Yafu на обычном компьютере, может быть уменьшено до 103.1746 секунд. Инструмент производит обработку бинарных файлов емкостью 320 бит или больше.

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

Попытки взлома в новейшее время

В 2009 году Бенджамин Муди с помощью битового ключа RSA-512 работал над расшифровкой криптотекста в течение 73 дней, используя только общеизвестное программное обеспечение (GGNFS) и среднестатистический настольный компьютер (двухъядерный Athlon64 при 1900 МГц). Как показал данный опыт, потребовалось чуть менее 5 гигабайт диска и около 2,5 гигабайт оперативной памяти для процесса «просеивания».

По состоянию на 2010 год, самый большой факторизованный номер RSA был 768 бит длиной (232 десятичные цифры, или RSA-768). Его раскрытие длилось два года на нескольких сотнях компьютеров одновременно.

На практике же ключи RSA имеют большую длину — как правило, от 1024 до 4096 бит. Некоторые эксперты считают, что 1024-битные ключи могут стать ненадежными в ближайшем будущем или даже уже могут быть взломаны достаточно хорошо финансируемым атакующим. Однако, мало кто станет утверждать, что 4096-битные ключи могут быть также раскрыты в обозримом будущем.

Перспективы

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

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

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

Официально в 2003 году была поставлена под сомнение безопасность 1024-битных ключей. В настоящее время рекомендуется иметь длину не менее 2048 бит.

Источник: https://FB.ru/article/255506/rsa-shifrovanie-opisanie-i-realizatsiya-algoritma-rsa

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

Rivest-Shamir-Adleman

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

Общая схема

Схема электронной подписи обычно включает в себя:

  • алгоритм генерации ключевых пар пользователя;
  • функцию вычисления подписи;
  • функцию проверки подписи.

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

Детерминированные функции всегда вычисляют одинаковую подпись по одинаковым входным данным. Вероятностные функции вносят в подпись элемент случайности, что усиливает криптостойкость алгоритмов ЭЦП.

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

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

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

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

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

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

Защищённость

Цифровая подпись обеспечивает:

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

Возможны следующие угрозы цифровой подписи:

  • Злоумышленник может попытаться подделать подпись для выбранного им документа.
  • Злоумышленник может попытаться подобрать документ к данной подписи, чтобы подпись к нему подходила.
  • Злоумышленник может попытаться подделать подпись для какого-нибудь документа.

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

Тем не менее, возможны ещё такие угрозы системам цифровой подписи:

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

Алгоритмы ЭЦП

  • Американские стандарты электронной цифровой подписи: DSA, ECDSA
  • Российские стандарты электронной цифровой подписи: ГОСТ Р 34.10-94 (в настоящее время не действует), ГОСТ Р 34.10-2001
  • Украинский стандарт электронной цифровой подписи: ДСТУ 4145-2002
  • Стандарт PKCS#1 описывает, в частности, схему электронной цифровой подписи на основе алгоритма RSA

Управление ключами

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

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

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

В децентрализованных системах (например PGP) путём перекрёстного подписывания сертификатов знакомых и доверенных людей каждым пользователем строится сеть доверия.

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

Описание алгоритма RSA

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

История

Описание RSA было опубликовано в 1977 году Рональдом Ривестом (Ronald Linn Rivest), Ади Шамиром (Adi Shamir) и Леонардом Адлеманом (Leonard Adleman) из Массачусетского Технологического Института (MIT).

Британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал аналогичную систему в 1973 году во внутренних документах центра, но эта работа не была раскрыта до 1977 года и Райвест, Шамир и Адлеман разработали RSA независимо от работы Кокса.

В 1983 году MIT был выдан патент 4405829 США, срок действия которого истёк 21 сентября 2000 года.

Описание алгоритма

Безопасность алгоритма RSA основана на трудности задачи разложения на множители.

Алгоритм использует два ключа — открытый (public) и секретный (private), вместе открытый и соответствующий ему секретный ключи образуют пару ключей (keypair).

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

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

Для того, чтобы сгенерировать пару ключей выполняются следующие действия:

1. Выбираются два больших простых числа и

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

3. Вычисляется Функция Эйлера

4. Выбирается целое такое, что и взаимно простое с

5. С помощью расширенного алгоритма Евклида находится число такое, что

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

Зашифрование и расшифрование

Для того, чтобы зашифровать сообщение вычисляется

.

Число и используется в качестве шифртекста. Для расшифрования нужно вычислить

.

Нетрудно убедиться, что при расшифровании мы восстановим исходное сообщение:

Из условия

следует, что

для некоторого целого , следовательно

Согласно теореме Эйлера:

,

поэтому

Некоторые особенности алгоритма

Генерация простых чисел

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

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

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

Дополнение сообщений

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

· значения и дадут при зашифровании шифртексты 0 и 1 при любых значениях и .

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

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

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

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

Выбор значения открытого показателя

RSA работает значительно медленнее симметричных алгоритмов. Для повышения скорости шифрования открытый показатель выбирается небольшим, обычно 3, 17 или 65537. Эти числа в двоичном виде содержат только по две единицы, что уменьшает число необходимых операций умножения при возведении в степень. Например, для возведения числа в степень 17 нужно выполнить только 5 операций умножения:

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

Выбор значения секретного показателя

Значение секретного показателя должно быть достаточно большим. В 1990 году Михаэль Винер (Michael J. Wiener) показал, что если и , то имеется эффективный способ вычислить по и . Однако, если значение выбирается небольшим, то оказывается достаточно большим и проблемы не возникает.

Длина ключа

Число n должно иметь размер не меньше 512 бит. В настоящий момент система шифрования на основе RSA считается надёжной, начиная с размера N в 1024 бита.

Применение RSA

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

Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ), а с помощью RSA шифруют лишь этот ключ.

II. Реализация

Для примера была реализована программа для цифрового подписания файлов и проверки подписей. Использовался алгоритм RSA и сертификаты X.509. Сертификат пользователя выбирается из хранилища сертификатов windows.

Цифровые подписи сохраняются в xml файле с именем .sig.xml

Фрагменты кода

public class Signature

{

private X509Certificate2 certificate;

private DateTime date;

private byte[] signedHash;

public X509Certificate2 Certificate

{

get { return certificate; }

set { certificate = value; }

}

public DateTime Date

{

get { return date; }

set { date = value; }

}

public void Sign(string input, X509Certificate2 cert)

{

this.certificate = new X509Certificate2( cert);

date = DateTime.Now;

string stringToEncrypt = input + date.Ticks;

signedHash = ((RSACryptoServiceProvider)cert.PrivateKey).SignData(Utils.StringToBytes(stringToEncrypt),new MD5CryptoServiceProvider());

}

public bool IsValid(string input)

{

string stringToEncrypt = input + date.Ticks;

return ((RSACryptoServiceProvider)certificate.PublicKey.Key).VerifyData(Utils.StringToBytes(stringToEncrypt),new MD5CryptoServiceProvider(), signedHash);

}

public byte[] SignedHash

{

get { return signedHash; }

set { signedHash = value; }

}

}

void DisplaySignatureList()

{

FileSignatures fileSignatures = ReadSignatures(GetSignaturesFileName(fileNameTextBox.Text));

signatureListTextBox.Text = «»;

foreach (Signature signaure in fileSignatures.Signaures)

{

string row = «»;

row+= signaure.Certificate.Subject;

row+=» «+signaure.Date.ToString();

string hash = GetFileHash(fileNameTextBox.Text);

bool valid = signaure.IsValid(hash);

if (valid)

row = «v » + row;

else

row = «x » + row;

signatureListTextBox.Text += row+»\r»;

}

}

III. Литература

  1. С.Бернет, С. Пейн : Криптография. Официальное руководство RSA Security – М. «Бином», 2002
  2. В. Зима : Безопасность глобальных сетевых технологий – «БХВ-Петербург», 2003
  3. Венбо Мао Современная криптография: теория и практика = Modern Cryptography: Theory and Practice. — М.: «Вильямс», 2005. — С. 768. ISBN 0-13-066943-1
  4. Нильс Фергюсон, Брюс Шнайер Практическая криптография : Practical Cryptography: Designing and Implementing Secure Cryptographic Systems. — М.: «Диалектика», 2004. — С. 432. ISBN 0-471-22357-3
  5. Шнайер, Брюс. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си — М.: Издательство ТРИУМФ, 2002 — 816с.:ил. ISBN 5-89392-055-4
  6. http://ru.wikipedia.org/wiki/Категория:Криптография

«,»author»:»ÐÐ²Ñ‚ор: kavayii»,»date_published»:»2020-11-24T00:08:00.000Z»,»lead_image_url»:»http://lh6.ggpht.com/_I2wwdlkfxTs/S0198Q9rMJI/AAAAAAAAAF4/gnKwjREUKcs/w1200-h630-p-k-no-nu/clip_image001_thumb.gif?imgmax=800″,»dek»:null,»next_page_url»:null,»url»:»http://kavayii.blogspot.com/2010/01/rsa.html»,»domain»:»kavayii.blogspot.com»,»excerpt»:»I. Введение Электронная цифровая подпись (ЭЦП)— реквизит электронного документа, предназначенный для удостоверения источника данных и защи…»,»word_count»:1594,»direction»:»ltr»,»total_pages»:1,»rendered_pages»:1}

Источник: http://kavayii.blogspot.com/2010/01/rsa.html

RSA-шифрование: как работает

Rivest-Shamir-Adleman

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

Источник: https://CryptoPerson.ru/cryptography/shifrovanie-pri-pomoshhi-algoritma-rsa

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

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