Криптосистема RSA на каждом такте шифрования преобразует двоичный блок открытого текста m длины size(n), рассматриваемый как целое число, в соответствии с формулой: c = m e (mod n).
При этом n = pq, где p и q - случайные простые числа большой разрядности, которые уничтожаются после формирования модуля и ключей. Открытый ключ состоит из пары чисел e и n. Подключ e выбирается как достаточно большое число из диапазона 1 < e < φ(n), с условием: НОД(e, j(n)) = 1, где j(n) - наименьшее общее кратное чисел p–1 и q–1. Далее, решая в целых числах x, y уравнение xe + yφ(n) = 1, полагается d = х, т.е. ed = 1(j(n)). При этом для всех m выполняется соотношение m ed = m(n), поэтому знание d позволяет расшифровывать криптограммы.
Чтобы гарантировать надежную защиту информации, к системам с открытым ключом предъявляются два следующих требования.
1. Преобразование исходного текста должно исключать его восстановление на основе открытого ключа.
2. Определение закрытого ключа на основе открытого также должно быть вычислительно нереализуемым. При этом желательна точная нижняя оценка сложности (количества операций) раскрытия шифра.
Алгоритмы шифрования с открытым ключом получили широкое распространение в современных информационных системах.
Рассмотрим построение криптосистемы RSA на простом примере.
1. Выберем p = 3 и q = 11.
2. Определим n = 3 ∙ 11 = 33.
3. Найдем j(n) = (p – 1)(q – 1) = 20.
5. Выберем число d, удовлетворяющее 7d = 1(mоd 20).
Легко увидеть, что d = 3(mоd 20).
Представим шифруемое сообщение как последовательность целых чисел с помощью соответствия: А = 1, B = 2, С = 3, ..., Z = 26. Поскольку size(n) = 6, то наша криптосистема в состоянии зашифровывать буквы латинского алфавита, рассматриваемые как блоки, Опубликуем открытый ключ (e, n) = (7, 33) и предложим прочим участникам системы секретной связи зашифровывать с его помощью сообщения, направляемые в наш адрес.Пусть такимсообщением будет CAB, которое в выбранном нами кодировке принимает вид (3, 1, 2).Отправитель должензашифроватькаждый блок и отправитьзашифрованное сообщение в наш адрес:
RSA(C) = RSA(3) = 3 7 = 2187 = 9(mod 33);
RSA(A) = RSA(1) = 1 7 = 1(mod 33);
RSA(B) = RSA(1) = 2 7 = 128 = 29(mod 33).
Получив зашифрованное сообщение (9, 1, 29), мы сможем его расшифровать на основе секретного ключа (d, n) = (3, 33), возводя каждый блок в степень d = 3:
9 3 = 729 = 3(mоd 33);
1 3 = 1(mоd 33);
29 3 = 24389 = 2(mоd 33).
Для нашего примера легко найти секретный ключ перебором. На практике это невозможно, т.к. для использования на практике рекомендуются в настоящее время следующие значения size(n):
· 512–768 бит - для частных лиц;
· 1024 бит - для коммерческой информации;
· 2048 бит- для секретной информации.
Пример реализации алгоритма RSA представлен в листингах 18.1 и 18.2 (компиляторы - Delphi, FreePascal).
Листинг 18.1. Пример реализации алгоритма RSA на языке Pascal
program Rsa;
{$APPTYPE CONSOLE}
{$IFDEF FPC}
{$MODE DELPHI}
{$ENDIF}
uses SysUtils, uBigNumber;
//Генератор случайных чисел
var t: array of Byte;
var pos: Integer;
var cbox: array of Byte =
(237, 240, 161, 1, 130, 141, 205, 98, 27, 169, 181, 202, 173, 47, 114, 224, 35, 183, 79, 82, 153, 220, 172, 22, 17, 11, 200, 131, 14, 154, 167, 91, 250, 31, 213, 112, 126, 241, 236, 155, 198, 96, 87, 143, 244, 151, 134, 38, 129, 233, 186, 101, 41, 94, 231, 115, 113, 199, 51, 145, 229, 37, 69, 180, 85, 33, 207, 163, 102, 187, 4, 89, 7, 44, 75, 88, 81, 120, 10, 232, 221, 168, 230, 158, 247, 211, 216, 156, 95, 64, 242, 215, 77, 165, 122, 5, 15, 119, 100, 43, 34, 48, 30, 39, 195, 222, 184, 92, 78, 135, 103, 166, 147, 32, 60, 185, 26, 251, 214, 90, 139, 45, 73, 150, 97, 116, 136, 68, 219, 248, 191, 192, 16, 8, 243, 50, 132, 105, 62, 201, 204, 65, 0, 99, 182, 121, 194, 108, 160, 170, 56, 226, 206, 254, 117, 178, 9, 197, 234, 127, 58, 171, 40, 29, 177, 142, 3, 228, 188, 162, 212, 157, 49, 175, 174, 140, 70, 106, 123, 66, 196, 246, 179, 42, 218, 71, 217, 227, 18, 164, 24, 67, 159, 25, 111, 255, 193, 245, 2, 238, 133, 21, 137, 152, 109, 148, 63, 124, 203, 104, 54, 55, 223, 80, 107, 210, 225, 149, 252, 76, 12, 189, 93, 46, 23, 13, 36, 209, 61, 249, 110, 144, 86, 52, 253, 72, 28, 53, 57, 125, 59, 235, 84, 128, 208, 146, 20, 74, 6, 239, 190, 83, 19, 138, 118, 176);
procedure InicMyRandom;
var i: Integer;
var s: string;
begin
WriteLn("Введите какой-либо текст для инициализации генератора
случайных чисел (до 256 символов):");
ReadLn(s);
i:= 1;
while (i<=255) and (i<=Length(s)) do
RSA-шифрование представляет собой одну из первых практических криптосистем с открытым ключом, которая широко используется для безопасной передачи данных. Ее основное отличие от подобных сервисов в том, что ключ шифрования является открытым и отличается от ключа дешифрования, который держится в секрете. В технологии RSA основана на практической сложности факторингового воспроизведения двух больших простых чисел (проблема факторинга).
Название RSA состоит из начальных букв фамилий Ривест, Шамир и Адлеман, - ученых, которые впервые публично описали подобные в 1977 году. Клиффорд Кокс, английский математик, работавший на спецслужбы Великобритании, впервые разработал эквивалентную систему в 1973 году, но она не была рассекречена до 1997 г.
Пользователь RSA создает и затем публикует открытый ключ, основанный на двух больших простых числах вместе со вспомогательным значением. должны храниться в тайне. Любой человек может использовать открытый ключ для шифрования сообщения, но если он достаточно большой, то только кто-либо со знанием простых чисел может декодировать сообщение. Раскрытие RSA шифрования известно как основная проблема: сегодня остается открытой дискуссия о том, насколько это надежный механизм.
RSA является относительно медленным алгоритмом, по причине чего он не так широко используется для непосредственного пользователя. Чаще всего этот метод используют для передачи в зашифрованном виде общих ключей для симметричного ключа шифрования, который, в свою очередь, может выполнять операции массового шифрования и дешифрования на гораздо более высокой скорости.
Идея асимметричного ключа криптосистемы приписывается Диффи и Хеллману, которые опубликовали концепцию в 1976 году, представив цифровые подписи и попытавшись применить теорию чисел. Их формулировка использует общий секретный ключ, созданный из экспоненциации некоторого числа по модулю простого числа. Тем не менее, они оставили открытой проблему реализации этой функции, поскольку принципы факторинга не были хорошо изучены в то время.
Ривест, Ади Шамир и Адлеман в Массачусетском технологическом институте предприняли несколько попыток в течение года, чтобы создать однонаправленную функцию, которую трудно раскодировать. Ривест и Шамир (как компьютерные ученые) предложили множество потенциальных функций, в то время как Адлеманом (как математиком) осуществлялся поиск «слабых мест» алгоритма. Они использовали много подходов и в конечном итоге в апреле 1977 года разработали окончательно систему, сегодня известную как 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 бит.
Доброго времени суток, уважаемые читатели.Как видно из этого, пускай несколько надуманного, но все же не столь и утопичного примера, RSA не столь надежна как это принято считать. Да конечно, можно сказать, что Алиса сама дура и никто ее не просил отвечать на такой серьезный для нее вопрос односложно. Так что же теперь запретить использование односложных ответов в криптографии? Конечно, нет. Все не так плохо, достаточно чтобы алгоритм добавлял к тексту некоторую случайную информацию, которую бы невозможно было предугадать и коварный Мэлори будет бессилен. Ведь, в самом деле, не сможет же он предсказать, что ответ «Да» после обработки алгоритмом превратится, например, в «Да4FE6DA54», а следовательно и зашифровать это сообщение он не сможет и нечего ему будет сравнивать с перехваченным криптотекстом.
Таким образом, уже сейчас можно сказать, что RSA во всех своих проявлениях будь то PGP или SSL не шифрует только отправленные на вход шифрующей функции данные. Алгоритм сперва добавляет к этим данным блоки содержащие случайный набор бит. И только после этого полученный результат шифруется. Т.е. вместо привычной всем
C=M E (mod N
)
получаем более близкую к действительности
C=(M||Rand) E (mod N
),
где Rand случайное число.
Такую методику называют схемами дополнения. В настоящее время использование RSA без схем дополнения является не столько плохим тоном, сколько непосредственно нарушением стандартов .
Но это далеко не все. Считается, что даже если криптоситема удовлетворяет сформулированному выше требованию, это еще не доказывает ее пригодность в практических целях. Сформулируем еще одно требование к стойкости асимметричного алгоритма.
Требование 2:
Пусть злоумышленник имеет доступ к расшифровывающему «черному ящику». Т.е. любой криптотекст по просьбе злоумышленника может быть расшифрован. Далее злоумышленник создает два открытых текста M 1 и M 2 . Один из этих текстов шифруется и полученный в результате криптотекст C b возвращается злоумышленнику. Задача злоумышленника угадать с вероятностью большей чем 0.5 какому из сообщений M 1 и M 2 соответсвует криптотекст C b . При этом он может попросить расшифровать любое сообщение, кроме C b (в противном случае игра не имеет смысла). Говорят что криптосистема стойкая, если злоумышленник, даже в таких прекрасных для себя условиях, не сможет указать какому исходному тексту соответствует C b с вероятностью большей 0.5.
В свете вышесказанного посмотрим как с этим обстоят дела в RSA.
Итак, злоумышленник имеет два сообщения M 1 и M 2 . А также криптотекст
C b =M 1 E (mod N
).
Ему необходимо указать какому конкретно из двух текстов соответствует C b . Для этого он может предпринять следующее. Зная открытый ключ E, он может создать сообщение
C"=2 E *C b (mod N
).
Далее он просит расшифровывающий «черный ящик» расшифровать сообщение C". А затем несложная арифметика ему в помощь. Имеем:
M"=C" D (mod N
)=2 ED *M 1 ED (mod N
)=2*M 1 (mod N
).
Т.е. вычислив M"/2 злоумышленник увидит M 1 . А это означает, что он поймет что в нашем примере было зашифровано сообщение M 1 , а следовательно мы еще раз убедились в неприемлемости использования RSA в его наивном виде на практике.
Устранить и эту неприятность помогают схемы дополнения. Только теперь к ним выдвигается требование не только о том, чтобы дополнительная информация была абсолютно случайной и непрогнозируемой. Но так же и том, чтобы дополнительные блоки помогали определить был ли шифротекст получен в результате работы шифрующей функции или он смоделирован злоумышленником. Причем в случае, если будет обнаружено, что шифротекст смоделирован вместо расшифрованных данных атакующему будет выдано сообщение о несоответствие данных реальному криптотексту.
Казалось бы, реализация такой схемы дополнения является труднорешаемой задачей, но ведь в криптографии уже есть готовый инструмент контроля целостности данных. Конечно же, это хеш-функции. Все современные схемы дополнений реализованы на идее применения хеш-функции в качестве проверки расшифрованных данных на подлинность.
В RSA при подписи и при шифровании данных используют две различные схемы дополнений. Схема, реализуемая для подписания документов, называется RSA-PSS(probabilistic signature scheme) или вероятностная схема подписи. Схема, используемая при шифровании – RSA-OAEP(Optimal asymmetric encryption padding) или оптимизированное асимметричное дополнение шифрования , на примере OAEP и рассмотрим как на самом деле происходит шифрование сообщений в RSA.
Upd: перенес в блог криптография.
upd2:
Литература и ссылки:
1. Н. Фергюссон, Б. Шнайер «Практическая криптография»
2. Н. Смарт «Криптография»
Электронная цифровая подпись (ЭЦП)— реквизит электронного документа, предназначенный для удостоверения источника данных и защиты данного электронного документа от подделки.
Схема электронной подписи обычно включает в себя:
Функция вычисления подписи на основе документа и секретного ключа пользователя вычисляет собственно подпись. В зависимости от алгоритма функция вычисления подписи может быть детерминированной или вероятностной. Детерминированные функции всегда вычисляют одинаковую подпись по одинаковым входным данным. Вероятностные функции вносят в подпись элемент случайности, что усиливает криптостойкость алгоритмов ЭЦП. Однако, для вероятностных схем необходим надёжный источник случайности (либо аппаратный генератор шума, либо криптографически надёжный генератор псевдослучайных бит), что усложняет реализацию.
В настоящее время детерминированые схемы практически не используются.
Функция проверки подписи проверяет, соответствует ли данная подпись данному документу и открытому ключу пользователя. Открытый ключ пользователя доступен всем, так что любой может проверить подпись под данным документом.
Поскольку подписываемые документы — переменной (и достаточно большой) длины, в схемах ЭЦП зачастую подпись ставится не на сам документ, а на его хэш. Для вычисления хэша используются криптографические хэш-функции, что гарантирует выявление изменений документа при проверке подписи. Хэш-функции не являются частью алгоритма ЭЦП, поэтому в схеме может быть использована любая надёжная хэш-функция.
Цифровая подпись обеспечивает:
Возможны следующие угрозы цифровой подписи:
При использовании надёжной хэш-функции, вычислительно сложно создать поддельный документ с таким же хэшем, как у подлинного. Однако, эти угрозы могут реализоваться из-за слабостей конкретных алгоритмов хэширования, подписи, или ошибок в их реализациях.
Тем не менее, возможны ещё такие угрозы системам цифровой подписи:
Важной проблемой всей криптографии с открытым ключом, в том числе и систем ЭЦП, является управление открытыми ключами. Необходимо обеспечить доступ любого пользователя к подлинному открытому ключу любого другого пользователя, защитить эти ключи от подмены злоумышленником, а также организовать отзыв ключа в случае его компрометации.
Задача защиты ключей от подмены решается с помощью сертификатов. Сертификат позволяет удостоверить заключённые в нём данные о владельце и его открытый ключ подписью какого-либо доверенного лица. В централизованных системах сертификатов (например PKI) используются центры сертификации, поддерживаемые доверенными организациями. В децентрализованных системах (например PGP) путём перекрёстного подписывания сертификатов знакомых и доверенных людей каждым пользователем строится сеть доверия.
Управлением ключами занимаются центры распространения сертификатов. Обратившись к такому центру пользователь может получить сертификат какого-либо пользователя, а также проверить, не отозван ли ещё тот или иной открытый ключ.
RSA — криптографический алгоритм с открытым ключом. RSA стал первым алгоритмом такого типа, пригодным и для шифрования и для цифровой подписи. Алгоритм используется в большом числе криптографических приложений.
История
Британский математик Клиффорд Кокс (Clifford Cocks), работавший в центре правительственной связи (GCHQ) Великобритании, описал аналогичную систему в 1973 году во внутренних документах центра, но эта работа не была раскрыта до 1977 года и Райвест, Шамир и Адлеман разработали RSA независимо от работы Кокса.
В 1983 году MIT был выдан патент 4405829 США, срок действия которого истёк 21 сентября 2000 года.
Описание алгоритма
Безопасность алгоритма RSA основана на трудности задачи разложения на множители. Алгоритм использует два ключа — открытый (public) и секретный (private), вместе открытый и соответствующий ему секретный ключи образуют пару ключей (keypair). Открытый ключ не требуется сохранять в тайне, он используется для зашифрования данных. Если сообщение было зашифровано открытым ключом, то расшифровать его можно только соответствующим секретным ключом.
Генерация ключей
Для того, чтобы сгенерировать пару ключей выполняются следующие действия:
1. Выбираются два больших простых числа и
2. Вычисляется их произведение
3. Вычисляется Функция Эйлера
4. Выбирается целое такое, что 
и взаимно простое с
5. С помощью расширенного алгоритма Евклида находится число такое, что
Число и используется в качестве шифртекста. Для расшифрования нужно вычислить
Нетрудно убедиться, что при расшифровании мы восстановим исходное сообщение:
Из условия
следует, что
для некоторого целого , следовательно
Согласно теореме Эйлера:
Некоторые особенности алгоритма
Генерация простых чисел
Для нахождения двух больших простых чисел и , при генерации ключа, обычно используются вероятностные тесты чисел на простоту, которые позволяют быстро выявить и отбросить составные числа.
· при малом значении открытого показателя (, например) возможна ситуация, когда окажется, что . Тогда , и нарушитель легко сможет восстановить исходное сообщение вычислив корень степени из .
· поскольку RSA является детерминированным алгоритмом, т.е. не использует случайных значений в процессе работы, то нарушитель может использовать атаку с выбранным открытым текстом.
Для решения перечисленных проблем сообщения дополняются перед каждым зашифрованием некоторым случайным значением — солью. Дополнение выполняется таким образом, чтобы гарантировать, что , и . Кроме того, поскольку сообщение дополняется случайными данными, то зашифровывая один и тот же открытый текст мы каждый раз будем получать другое значение шифртекста, что делает атаку с выбранным открытым текстом невозможной.
Выбор значения открытого показателя
RSA работает значительно медленнее симметричных алгоритмов. Для повышения скорости шифрования открытый показатель выбирается небольшим, обычно 3, 17 или 65537. Эти числа в двоичном виде содержат только по две единицы, что уменьшает число необходимых операций умножения при возведении в степень. Например, для возведения числа в степень 17 нужно выполнить только 5 операций умножения:
должно быть достаточно большим. В 1990 году Михаэль Винер (Michael J. Wiener) показал, что если выбирается небольшим, то оказывается достаточно большим и проблемы не возникает.
Длина ключа
Число n должно иметь размер не меньше 512 бит. В настоящий момент система шифрования на основе RSA считается надёжной, начиная с размера N в 1024 бита.
Применение RSA
Система RSA используется для защиты программного обеспечения и в схемах цифровой подписи. Также она используется в открытой системе шифрования PGP.
Из-за низкой скорости шифрования (около 30 кбит/с при 512 битном ключе на процессоре 2 ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ключом (сеансовый ключ ), а с помощью RSA шифруют лишь этот ключ.
Для примера была реализована программа для цифрового подписания файлов и проверки подписей. Использовался алгоритм 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;
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);
row = "v " + row;
row = "x " + row;
signatureListTextBox.Text += row+"\r\n";
Наконец-то настало время заняться описанием RSA-криптосистемы. Помимо объяснения, как она работает, мы должны в деталях обсудить ее безопасность; другими словами, почему настолько трудно взломать сообщение, зашифрованное RSA-криптосистемой?
Чтобы реализовать систему шифрования RSA, предназначенную для одного пользователя, необходимо выбрать два различных простых числа р и q и вычислить их произведение Простые р и q хранятся в тайне, в то время как число становится частью открытого ключа. В § 12.5 мы подробно обсудим метод выбора простых составляющих ключа, а также то, как этот выбор связан с надежностью системы.
Сообщение (которое можно считать целым числом) шифруется путем возведения в некоторую степень по модулю Поэтому сначала мы должны найти способ представить текст сообщения в виде списка классов по модулю Это, в действительности, еще не процесс шифрования, а только подготовка сообщения к тому, чтобы его можно было зашифровать.
Для простоты предположим, что текст сообщения содержит только слова, записанные заглавными буквами. Таким образом, сообщение, в конечном счете, - последовательность букв и пробелов. Первый шаг состоит в замене каждой буквы сообщения числом, которое выбирается из следующей таблицы:
(см. скан)
Пробел между словами заменяется на число 99. Проделав эту процедуру, мы получим число, возможно очень большое, если сообщение было длинным. Однако, это еще не окончательное число, к которому мы стремимся, а всего лишь набор классов по модулю И теперь нам нужно разбить численное представление сообщения на кусочки, каждый из которых - натуральное число, не превосходящее Эти кусочки принято называть блоками сообщения.
Например, численное представление девиза «ПОЗНАЙ СЕБЯ» выглядит так:
Выбрав простые мы получим произведение Поэтому численное представление сообщения, выписанное выше, нужно разбить на блоки, меньшие чем 23 393. Приведем одно из таких разбиений.
Конечно, выбор блоков не однозначен, но и не совсем произволен. Например, во избежание двусмысленностей на стадии
расшифровки не следует выделять блоки, начинающиеся с нуля.
При расшифровке сообщения, зашифрованного системой шифрования RSA, получают последовательность блоков. Затем их соединяют вместе и получают численное представление сообщения. И только после замены чисел буквами в соответствии с приведенной таблицей можно будет прочесть исходное сообщение.
Обратите внимание на то, что каждая буква таблицы кодируется двузначным числом. Так делается для предотвращения путаницы. Предположим, мы пронумеровали буквы по порядку, начиная с 1, т.е. А соответствует 1, Б - 2, и так далее. В этом случае мы не сможем точно сказать, обозначает ли блок 12 пару букв или только одну букву двенадцатую букву алфавита. Конечно, для численного представления сообщения можно использовать любое однозначное соответствие между буквами и числами, например, -кодировку, при которой перевод сообщения в цифровую форму автоматически выполняется компьютером.
Сообщение, подготовленное к шифровке по методу § 12.1, состоит из последовательности блоков, каждый из которых - число, меньшее, чем Теперь обсудим, как шифруется каждый блок. Для этого нам потребуется число равное произведению простых и натуральное число, обратимое по модулю т.е. число удовлетворяющее условию
Напомним, что по известным р и q число легко вычисляется. Действительно,
Пара называется открытым, или кодирующим, ключом криптосистемы RSA, которую мы описываем. Пусть блок сообщения, то есть целое число, удовлетворяющее неравенству Символом мы будем обозначать блок зашифрованного сообщения, соответствующий Он вычисляется по следующему правилу:
Заметим, что каждый блок сообщения шифруется отдельно. Поэтому зашифрованное сообщение, фактически, состоит из отдельных закодированных блоков. Более того, мы не можем объединить эти блоки в одно большое число, поскольку в результате расшифровать сообщение станет невозможно. Вскоре мы увидим причину этого.
Вернемся к примеру, который начали рассматривать в первом параграфе. Мы зафиксировали так что Теперь нужно выбрать число Напомним, что оно должно быть взаимно простым с Наименьшее простое число, не делящее 23088, равно 5. Положим Чтобы закодировать первый блок сообщения из § 12.1, нам предстоит определить вычет числа 25245 по модулю 23 393. С помощью программы символьных вычислений (или калькулятора, если хватит терпения) мы получим, что искомый вычет равен 22 752. Итак, Все же зашифрованное сообщение представляется следующей последовательностью блоков:
Посмотрим, как декодируются блоки зашифрованного сообщения. Чтобы приступить к дешифровке, нам необходимо знать и обратный элемент к по модулю Последний из них - это натуральное число, которое мы будем обозначать через Пара называется секретным, или декодирующим ключом системы шифрования RSA. Если а - блок зашифрованного сообщения, то соответствующая его дешифровка
Получается в результате операции:
Прежде чем вернуться к примеру, необходимо дать некоторые комментарии. Во-первых, вычислить очень легко, если знать Действительно, секретный ключ определяется с помощью расширенного алгоритма Евклида. Во-вторых, если блок исходного сообщения, то мы вправе ожидать равенства Другими словами, декодируя блок шифрованного сообщения, мы надеемся узнать соответствующий блок исходного. То, что это так и будет, не следует непосредственно из описанного выше алгоритма, но мы все подробно обсудим в следующем параграфе.
Наконец, как мы утверждали во введении и на протяжении всей книги, для взлома RSA-криптосистемы необходимо разложить на множители, потому что для дешифровки сообщения нужно знать Однако после того, как работа системы подробно описана, ясно, что последнее утверждение не совсем точно. Чтобы прочесть шифровку, кроме самого нужно знать только обратный к элемент по модулю Поэтому для взлома системы достаточно вычислить при известных Оказывается, это вычисление равносильно разложению числа на множители, как мы убедимся в § 12.4.
В обсуждаемом примере Для определения применим расширенный алгоритм Евклида к числам и 5.
(см. скан)
Таким образом, Следовательно, обратным к 5 по модулю будет -9235 и
Наименьшее натуральное число, сравнимое с -9235 по модулю Значит, для раскодирования блока шифрованного сообщения мы должны возвести его в степень 13 853 по модулю 23 393. В нашем примере первый закодированный блок - это 22 752. Вычисляя вычет числа 22 75213853 по модулю 23 393, получим Заметьте, что даже при таких малых числах требования, предъявляемые при работе RSA-криптосистемы, превышают возможности большинства карманных калькуляторов.
Как мы уже отмечали ранее, шаги, описанные выше, приводят к работающей криптосистеме, только если в результате декодирования каждого блока шифрованного сообщения будет восстанавливаться соответствующий блок исходного. Предположим, что мы имеем дело с системой RSA, имеющей открытый ключ и секретный ключ Придерживаясь обозначений § 12.2, нам нужно показать, что для любого целого числа удовлетворяющего неравенству выполняется тождество
На самом деле, достаточно доказать, что
Действительно, как 6, так и неотрицательные целые числа, меньшие Поэтому они сравнимы по модулю тогда и только тогда, когда они равны. Это, в частности, объясняет, почему мы разбиваем численное представление сообщения на блоки, меньшие Кроме того, отсюда видно, что блоки
закодированного сообщения необходимо записывать отдельно: в противном случае наши рассуждения не будут работать.
Из рецептов шифрования и дешифрования следует, что
Поскольку элементы взаимно обратны по модулю найдется такое натуральное к, что Более того, по условию, числа больше Следовательно, Подставляя вместо произведения в уравнение (3.1), получаем
Теперь воспользуемся теоремой Эйлера, которая утверждает, что Отсюда т. е.
и мы полностью получили бы доказательство, если бы в него не закралась маленькая ошибочка.
Внимательно просмотрев еще раз наши рассуждения, Вы заметите, что мы не учитывали условий теоремы Эйлера. На самом деле, прежде чем применять теорему, необходимо убедиться во взаимной простоте чисел За этим, казалось бы, нужно следить при подготовке сообщения к шифровке, т.е. во время разбиения численного представления сообщения на блоки нужно добиваться уверенности в том, что все получающиеся блоки взаимно просты с К счастью, в этом нет необходимости, потому что на самом деле сравнение выполнено для любого блока. И ошибка кроется не в результате, который мы хотим доказать, а только лишь в самом доказательстве. Правильный подход основывается на рассуждениях, использованных при доказательстве теоремы Корселта в главе 7.
Напомним, что где различные простые числа. Определим вычеты числа по модулям Поскольку
вычисления для обоих простых чисел аналогичны, мы проработаем в деталях только случай Итак, мы уже убедились в том, что
для некоторого целого Следовательно,
Мы хотели бы теперь применить теорему Ферма, но имеем право сделать это, только если не делит Пусть это требование выполнено. Тогда и мы получаем, что
Заменив теорему Ферма теоремой Эйлера, мы не решили возникшей проблемы: сравнение справедливо только для некоторых, но не для всех блоков. Однако теперь блоки, для которых рассуждения не проходят, должны делиться на Далее, если делит то как 6, так и сравнимы с 0 по модулю а значит сравнимы между собой. Таким образом, доказываемое сравнение справедливо и в этом случае. Следовательно, сравнение истинно для любого целого числа Обратите внимание на то, что мы не. могли использовать подобное рассуждение, когда применяли теорему Эйлера к Действительно, неравенство не означает сравнения потому что число составное.
Итак, мы доказали, что Аналогично доказывается сравнение Другими словами, делится и на и на Но различные простые числа, так что Таким образом, лемма из § 3.6 гарантирует нам, что делит А так как мы имеем для любого целого числа Другими словами, Как мы отметили в начале параграфа, этого достаточно для доказательства равенства поскольку обе его части - неотрицательные целые числа, меньшие Подводя итог, можно утверждать, что
алгоритм предыдущего параграфа приводит к практической криптосистеме. Теперь нужно убедиться в ее надежности.
Напомним, что RSA - система шифрования с открытым ключом, состоящим из произведения различных простых чисел и натурального числа обратимого по модулю Посмотрим внимательно, что можно сделать для взлома RSA, если все, что известно, это пара
Чтобы раскодировать блок, зашифрованный с помощью RSA, мы должны узнать число обратное к по модулю Проблема в том, что практически единственный известный способ сделать это основывается на применении расширенного алгоритма Евклида к Однако для вычисления по формуле из § 9.4 нам нужно знать что подтверждает первоначальное утверждение: взлом RSA требует разложения на множители. А поскольку трудности разложения носят принципиальный характер, система RSA безопасна.
Можно, конечно, предположить, что когда-нибудь кто-нибудь откроет алгоритм, вычисляющий без информации о множителях числа Что, например, произойдет, если некто придумает эффективный способ определения непосредственно по На самом деле, это всего лишь замаскированный способ разложения Точнее говоря, если
известны, то мы с легкостью вычисляем Действительно,
так что сумма искомых простых делителей известна. Далее,
поэтому разность тоже известна. Теперь, решая простую систему линейных уравнений, легко наг ходим разложение на множители.
Значит, алгоритм, вычисляющий фактически раскладывает число на множители, так что это одного поля ягодки. Но успокаиваться пока рано. Можно пойти дальше в своих фантазиях и предположить, что кто-то изобрел алгоритм, определяющий непосредственно по Но Так что, если нам известны то мы знаем число, кратное Оказывается, такой информации тоже достаточно для разложения Вероятностный алгоритм, приводящий к такому разложению, можно найти в . В упражнении 7 приведен похожий (но более простой) алгоритм разложения в предположении, что криптосистему Рабина можно взломать. Он даст вам представление о вероятностном алгоритме из .
Остается последняя возможность для взлома: попытка восстановления блока непосредственно по вычету по модулю Если достаточно большое, то систематический перебор всех возможных кандидатов для поиска единственный выход. Никто еще не придумал ничего лучшего. Мы перечислили основные аргументы, объясняющие, почему взлом RSA-криптосистемы считается равносильным разложению на простые множители, хотя строгого доказательства этого утверждения пока еще нет.
Из предыдущего обсуждения вытекает, что для безопасности RSA-криптосистемы важно правильно выбрать простые числа Естественно, если они малы, то система легко взламывается. Однако недостаточно выбрать большие Действительно, даже если р и q огромны, но разность мала, их произведение легко разлагается на множители с помощью алгоритма Ферма (см. § 3.4).
Это не праздный разговор. В 1995 году два студента одного американского университета взломали версию RSA, находящуюся в общественном пользовании. Такое стало возможным из-за плохого выбора простых множителей системы.
С другой стороны, RSA использовалась в течение долгого времени и, если простые сомножители выбраны тщательно, то система в действительности оказывается достаточно надежной. Таким образом, любому программисту системы шифрования RSA необходим эффективный метод удачного выбора простых чисел.
Предположим, мы хотим создать RSA-криптосистему с открытым ключом в котором целое число имеет около знаков. Сначала выберем простое число количество знаков которого лежит между возьмем близким к В настоящее время рекомендованный для персонального использования размер ключа равен 768 битам, т.е. должно приблизительно состоять из 231 цифры. Чтобы построить такое число, нам потребуются два простых, скажем, из 104 и 127 знаков. Обратите внимание на то, что выбранные таким образом простые достаточно далеки друг от друга, т.е. применение алгоритма Ферма для разложения в этой ситуации непрактично. Кроме того, нам нужно удостовериться в том, что в разложении чисел на простые множители участвуют не только малые делители, но и большие. Действительно, в противном случае, число становится легкой добычей для некоторых известных алгоритмов разложения (см. ). Рассмотрим теперь метод, с помощью которого находят простые числа, удовлетворяющие перечисленным условиям.
Сначала нам потребуется один простой результат о распределении простых чисел. Напомним, что обозначает количество простых, не превосходящих х. Учитывая теорему о простых числах, мы видим, что для больших х число приблизительно равно где натуральный логарифм
по основанию (см. § 4.5). Пусть очень большое, какое-то положительное число. Мы хотим оценить количество простых чисел, лежащих между прикинуть разность Благодаря теореме о простых числах и свойствам логарифма, разность приблизительно равна
Предполагая, что очень мало, мы можем считать значение равным 0 и получить разумную оценку разности Итак, число простых, заключенных между приблизительно равно Естественно, оценка тем точнее, чем больше х и меньше Для более подробного знакомства с такой оценкой см. ([Д.10]).
Предположим, что нам нужно выбрать простое число в окрестности целого х. Для определенности будем считать, что х имеет порядок , а простое ищем в интервале от х до Было бы полезно знать заранее, сколько простых чисел находится в этом интервале. Для оценки количества простых можно воспользоваться только что полученным результатом. В нашем примере величина имеет очень маленький порядок: Поэтому по формуле, выписанной выше, мы заключаем, что в интервале между лежит приблизительно
простых числа. В конце второго параграфа главы 11 мы сформулировали стратегию, предназначенную для доказательства простоты данного нечетного числа Она состоит из трех шагов.
