В колонках играет - QueenКриптография: основные методы построения криптоалгоритмов
Базовые определения и принципы криптографии
Прежде всего, мне хотелось бы ввести несколько определений, которые будут использоваться в данной статье. Открытым текстом (plaintext) называются исходные данные, которые подлежат шифрованию, шифротекстом (ciphertext) называются зашифрованные данные. Шифрованием или криптографическим преобразованием называется процедура, отображающая открытый текст в шифротекст, и, соответственно, дешифрованием или обратным криптографическим преобразованием называют процесс расшифровки шифротекста в открытый текст. Для шифрования/дешифрования текста в одноключевых (симметричных) системах необходим так называемый секретный ключ (secret key), который должен быть известен только тем людям, которые имеют право доступа к открытому тексту, и не должен оказаться в руках злоумышленника. В некоторых алгоритмах используется так называемый открытый ключ (public key), который может (и должен) быть известен всем. Он необходим для двухключевых (или ассиметричных) криптоалгоритмов, в которых текст, зашифрованный с помощью открытого ключа, можно восстановить только с помощью секретного ключа.
Криптостойкостью или прочностью криптоалгоритма называют его устойчивость к разнообразным атакам, которых существует очень много (линейный и дифференциальный криптоанализ, различные атаки, базирующиеся на известных криптоаналитику открытых текстах и/или шифротекстах и прямой перебор всевозможных ключей (лобовая атака, brute-force attack)). Цель любой атаки – заполучить секретный ключ. Атаки на основе дифференциального анализа осуществляются на основе изучения несходства шифротекстов, получаемых шифрованием открытых текстов с небольшими различиями (аналог дифференциала), путем пропускания их через шифр с одним и тем же секретным ключом. Линейный анализ использует так называемые линейные приближения. Линейное приближение – это бит, с определенной вероятностью истинности являющийся результатом сложения по модулю 2 (XOR) некоторых битов ключа. Метод получения таких приближений состоит в XOR-сложении определенных бит открытого текста и соответствующих бит шифротекста. Результат применения операции XOR от получившихся результатов дает некий бит, называемый линейным приближением. Атаки, основанные на прямом переборе всего множества ключей, точно могут гарантировать нахождение нужного ключа, но осуществить их для больших ключей за разумное время должно быть невозможно. Часто бывает невозможно осуществить другие, теоретически верные атаки, на порядки менее трудоемкие, чем лобовая, но не только из-за недостаточной мощности вычислительных средств, а чаще из-за большого, а то и огромного количества памяти, нужной для хранения промежуточных результатов (срабатывает золотое правило программирования).
Считается, что криптоалгоритм обладает идеальной прочностью, если не существует способа получить секретный ключ за меньшее время, чем требуется для лобовой атаки. (Доказать это теоретически трудно, а практически невозможно – вдруг найдется более быстрый способ, поэтому подчас бывает намного легче опровергнуть надежность алгоритма, чем ее доказать.) При этом, как правило, увеличение длины ключа ведет за собой не меньше, чем экспоненциальное увеличение времени полного перебора (но не забывайте о законах, ограничивающих использование определенных криптосистем с длинными ключами). Но независимо от длины используемого ключа, у некоторых алгоритмов есть слабые ключи, для получения которых не обязательно делать полный перебор, а, например, достаточно иметь несколько пар “открытый текст шифротекст”.
Некоторые обозначения
Договоримся, что в формулах, приводимых в этой статье, будут использоваться следующие обозначения:
· k – ключ (key);
· Ek – процедура шифрования по ключу k (encrypt);
· Dk – процедура дешифрования по ключу k (decrypt);
· – побитовая операция сложения по модулю 2 (т.е. обычный XOR или побитовое исключающее ИЛИ);
· (mod ) – такая конструкция, стоящая в конце формулы, означает, что все операции в данной формуле выполняются по модулю .
Общие принципы
Основная схема, для которой используют криптоалгоритмы, выглядит так: есть так называемый открытый канал связи (например, Интернет или локальная сеть, где каждый пакет данных может быть прочитан посторонним человеком), по которому необходимо передать или обменяться конфиденциальными сообщениями между людьми A и B. Этот канал связи может прослушиваться неким злоумышленником C, который может перехватить любое сообщение (пассивный перехват) и даже подменить своим (активный перехват)! В криптографической литературе вошло в традицию называть этих людей именами по первым буквам: Алисой, Бобом и Кларком (Alice, Bob, Clark). В такой схеме сообщение перед отправкой, например, Алисой, шифруется при помощи секретного ключа, а потом отправляется шифротекстом по открытому каналу Бобу (тут Кларк отдыхает, не зная ключа узнать содержимое шифротекста ему очень сложно). Боб, получив сообщение, применяет к нему и ключу обратное преобразование и получает открытый текст. А вот о ключе, с помощью которого происходит шифрование, Алиса и Боб договариваются по некоему секретному каналу, прослушивание которого исключается. Данная схема называется одноключевой или симметричной, так как для шифрования/дешифрования используется один и тот же секретный ключ.
Все бы хорошо, но у данной схемы есть большой недостаток: создание абсолютно надежных секретных каналов для всех пар Алис и Бобов является непосильно трудной проблемой, требующей больших затрат. Для решения данной задачи была предложена идея двухключевых (ассиметричных) криптоалгоритмов.
В такой схеме сообщение от Алисы, предназначенное для отправки Бобу, шифруется с использованием уникального открытого ключа Боба. После чего оно отправляется по открытому каналу, а Боб для дешифрования пришедших к нему сообщений использует свой секретный ключ. При этом получить секретный ключ, зная соответствующий ему открытый ключ, довольно трудоемко. В данной схеме обмен открытыми ключами между Алисой и Бобом происходит через аутентичный канал, то есть канал, гарантирующий подлинность источника данных. Но стоит отметить, что аутентичный канал является открытым, и вся передаваемая по нему информация может читаться противником. Однако подменить ее он не может благодаря аутентичности (иначе Кларк просто мог бы дезинформировать Алису и/или Боба, подменив их открытые ключи своими, и читая и подменивая все проходящие через него шифротексты).
Симметричные криптосистемы
По применению процедуры шифрования/дешифрования их можно подразделить на блочные и поточные шифры. Рассмотрим, в чем же между ними разница.
Блочные шифры
В блочных шифрах (block cipher) открытый текст разбивается на блоки фиксированной длины, в большинстве алгоритмов это 64 или 128 бит (если последний блок получается короче, то его обычно «набивают» до нужной длины). Далее, с помощью секретного ключа и прямого криптографического преобразования каждый блок открытого текста отображается в блок шифротекста той же длины. Обратное криптографическое преобразование сохраняет это соответствие. В блочных шифрах большое значение имеет так называемый принцип итерирования, который заключается в многократном применении процедуры шифрования к каждому блоку. Например, в классическом шифре DES – 16 итераций, а в шифре ГОСТ 28147-89 – 32 итерации. Увеличение числа циклов хорошего криптоалгоритма способствует так называемому лавинному эффекту (avalanche effect), который позволяет наилучшим образом «запутывать» взаимосвязь между текстом и шифротекстом, представляя каждый бит блока шифротекста нелинейной функцией от всех бит соответствующего блока открытого текста и всех бит ключа. Кроме того, чем больше циклов, – тем выше стойкость к криптоанализу, но ниже скорость работы.
Сеть Фейстеля
Конструкция или сеть Фейстеля (H.Feistel, в разных источниках встречаются переводы Файстель и Фейштель) представляет собой итерированный блочный шифр, придуманный Фейстелем еще в 1970-х годах. Для ее работы необходима некая шифрующая функция f и секретный ключ k. Для прямого криптографического преобразования каждый блок открытого текста разбивается на две равные половины (разумеется, длина блока должна быть четная), после чего выполняются следующие действия (см. рисунок 1). На каждой i-той итерации (i = 1,…,m) левая часть подвергается сложению XOR с результатом шифрования f(Ri,ki) от правой части блока Ri и подключа ki, получаемого из секретного ключа k: Li+1 = Li f(Ri,ki), правая часть остается без изменений: Ri+1 = Ri. После чего левая и правая части меняются местами (только на последнем m-ом шаге левую и правую части менять местами не надо).
Процедура дешифрования выполняется аналогично, только ключи ki берутся в обратном порядке. Сеть Фейстеля замечательна тем, что для нее прямое и обратное криптографические преобразования выполняются по одной схеме, и для функции f не требуется ее обратимость. Криптостойкость сети Фейстеля целиком определяется функцией f, причем она повышается при увеличении числа итераций.
Сеть Фейстеля применяется во многих блочных шифрах. Иногда применяются различные модификации сети Фейстеля, отличающиеся делением блока не на две, а на большее количество частей и более усложненной взаимосвязью между этими частями.
Функция f является шифрующей функцией криптоалгоритма. Обычно она состоит из некоторой последовательности различных преобразований над текстом. Такими преобразованиями могут быть различные XOR-наложения ключа на блок, отдельных частей блока между собой и т.д. Также часто применяются циклические битовые сдвиги (shift), перестановки (permutation) некоторых бит местами, подстановки и много еще чего. Подстановкой называют функцию, заменяющую передаваемую ей последовательность бит на другую последовательность, в соответствии с заданной функцией. Часто подстановки задаются блоками (не путать с блоками, на которые делится текст (block), у этих терминов разный английский перевод). Блок (box) – это матрица с некоторыми значениями. Из передаваемой подстановке последовательности бит вычисляются смещения по вертикали и горизонтали, и возвращается значение матричной ячейки, соответствующей этим смещениям. Содержимое этих ячеек представляют собой некоторые последовательности бит, которые могут быть задано жестко, а могут и заполняться материалами ключа и/или открытого текста. В последнем случае криптостойкость, как правило, только повышается. В соответствии с этим, перестановки также часто задаются блоками. В зависимости от длины входящей и выходящей последовательностей бит, подстановки бывают сжимающими (shrinking), расширяющими (expansion) и заменяющими (substitution).
Наиболее распространенные режимы шифрования
Сеть Фейстеля задает правило, по которому шифруется каждый блок открытого текста. Так как для шифрования всего текста необходимо зашифровать все его блоки, то правила, определяющие в какой взаимосвязи между собой будут зашифрованы блоки открытого текста, называют рабочими режимами шифрования блочных шифров. Такие режимы не должны снижать прочность и эффективность криптосистемы.
Обозначения mi и ci на рисунках будут подразумевать i-тый блок открытого текста и шифротекста, соответственно. Каждый такой текст делится на n блоков считая с 1.
ECB (Electronic Code Book) – режим электронной кодовой книги. В данном режиме (см. рисунок 2) каждый i-тый блок шифруется/дешифруется независимо. Имеют место формулы шифрования ci = Ek(mi) и дешифрования mi = Di(ci). Где процедуры прямого и обратного криптографических преобразований Ek и Dk подразумевают под собой некие правила, которые надо выполнить над отдельно взятым блоком. Такими правилами может быть, к примеру, описанная выше сеть Фейстеля. Здесь и далее иллюстрации показывают только процесс шифрования, процесс дешифрования нетрудно восстановить по приводимым формулам.
Прочность режима ECB не ниже, чем у используемого криптоалгоритма. Недостатки: фиксированные блоки шифротекста соответствуют фиксированным блокам открытого текста, из-за чего открытый текст легко может быть изменен путем манипуляций с блоками шифротекста (удаление отдельных блоков, перестановка). Достоинства: скорость шифрования определяется только скоростью обработки отдельных блоков (т.е. скоростью работы f), кроме того ECB очень хорошо поддается распараллеливанию.
CBC (Cipher Block Chaining) – сцепление блоков шифра. Каждый i-тый блок открытого текста mi суммируется (сцепляется) по модулю 2 с предыдущим (i-1)-м блоком шифротекста ci-1, а затем шифруется (рисунок 3). Начальное значение блока c0 задается вектором инициализации. На основании таких рассуждений можно записать следующие формулы: ci = Ek(mici-1), mk = Dk(ci)ci-1.
Прочность реализации CBC определяется прочностью используемого алгоритма. Скорость шифрования также зависит только от скорости обработки отдельных блоков (операция XOR на аппаратном уровне выполняется очень быстро – за один такт). Режим CBC позволяет устранить недостаток режим ECB: теперь каждый блок открытого текста «маскируется» накладыванием на него предыдущего блока шифротекста. И хотя распараллелить такой процесс шифрования очень трудно, процесс дешифрования распараллеливается значительно легче.
CFB (Cipher Feedback) – обратная связь по шифротексту. Каждый i-тый блок шифротекста ci получается шифрованием результата операции XOR от ci-1 и mi-1. Начальное значение c0 также задается вектором инициализации. Шифрование и дешифрование производится по таким формулам: ci = miEk(ci-1), mi = ciDk(ci-1). Обратная связь здесь проявляется в том, что, фактически, на каждом i-ом шаге шифрованию подвергается не текущий i-ый блок, а предыдущий, (i-1)-ый. В целях криптостойкости данный режим можно реализовать так, чтобы обратная связь использовала не все биты блока, а только часть их. В общем, CFB довольно похож на предыдущий режим CBC, как видно из рисунка 4, и характеристики у него аналогичны с CBC. Разве что добавился еще один недостаток: при использовании полноблочной обратной связи, при появлении двух одинаковых блоков шифротекста, результат, например, DES-шифрования на следующем шаге будет тем же.
OFB (Output Feedback) – обратная связь по выходу. Аналогичен CFB, только теперь накладываемые вспомогательные блоки si генерируются отдельно (рисунок 5), путем шифрования предыдущего блока: si = Ek(si-1). Значение s0 задается вектором инициализации. После чего на i-ом шаге текущий блок открытого текста накладывается с помощью XOR на текущий вспомогательный блок: ci = misi. А дешифрование производится по такой формуле: mi = cisi. Обратная связь с использованием не всех битов блока не рекомендуется в силу возможного уменьшения прочности. Недостаток: также, как и в ECB, в данном режиме возможно изменение открытого текста путем манипуляций с блоками шифротекста. Достоинства: скорость шифрования в режиме OFB совпадает со скоростью блочного шифра, и хотя с трудом поддается распараллеливанию, возможна оптимизация, заключающаяся в предварительном вычислении вспомогательных блоков si, а их дальнейшее XOR-накладывание выполняется, как уже было сказано, очень быстро. Возможное искажение в шифротексте, вызванные передачей по каналу с шумом, режим OFB при дешифровании не «размазывает» по всем последующим блокам открытого текста, а локализует в пределах одного блока. В целях избавления от недостатков, иногда предлагают использовать усовершенствованный OFB, в котором вспомогательные блоки получаются по формуле: si = Ek(si-1+V) (mod 2p), где p – количество бит в блоке, а V – вектор инизиализации.
PCBC (Propagating Cipher Block Chaining) – сцепление блоков шифра с распространением ошибки. Представляет собой модифицированный режим CBC, где используется «двойной» вектор инициализации: m0c0. На каждом шаге блок шифротекста ci получается блочным шифрованием суммы (XOR) блоков mi, mi-1 и ci-1 (см. рисунок 6). Это правило записывается такими формулами: ci = Ek(mimi-1ci-1), mi = Dk(ci)ci-1mi-1.
Режим PCBC замечателен тем, что он идеально подходит для использования каналов с шумом. Единичную ошибку в блоке шифротекста при дешифровании он распространяет на все последующие блоки открытого текста, что позволяет легко обнаруживать ошибки при передаче данных.
Выбор режима шифрования
Существуют и более сложные «многоэтажные» режимы (здесь я привел только «одноэтажные»), где количество «этажей» измеряется в вызовах функции Ek (или Dk) на каждом шаге. Их описание выходит за рамки этой статьи.
Режим шифрования следует выбирать исходя конкретных предъявляемых требований задачи и свойств самого режима. Режим ECB самый простой и быстрый, но он и самый уязвимый, поэтому использовать его не рекомендуется. Он может быть пригоден только для шифрования случайных данных, небольших по размеру. Чаще всего используются CBC, CFB и OFB. Для шифрования файлов наиболее предпочтителен CBC, который обеспечивает необходимую безопасность и надежность при появлении ошибок.
Обзор наиболее распространенных блочных шифров
DES – классический блочный шифр, федеральный стандарт США, ставший впоследствии мировым. Разработан более 20 лет назад, использует 64-битовые блоки и 56-битовый ключ (в классическом варианте). Построен по схеме Фейстеля с 16 итерациями, на каждой итерации из 56 бит ключа с помощью S-блоков выбирается подключ длиной 48 бит, шифрующая функция построена на основе S-блоков и P-блоков. DES проектировался для аппаратной реализации, поэтому скорость его программной реализации очень низка. А длина ключа в 56 бит делает его уязвимым для лобовой атаки программными средствами.
В связи с этим предпринимались попытки усовершенствования DES. Одна из таких попыток называется тройным DES (EDE или Triple DES), в ней данные сначала шифруются на первом ключе, потом дешифруются на втором, а затем шифруются на третьем. При выборе хороших ключей и режима шифрования (TCBC, CBCM) эта схема уже позволяет противостоять лобовой атаке, хотя не защищает от других атак (т.к. размер блока по-роежнему 64 бита). Существует шифр DEAL, который использует сеть Фейстеля из 6 циклов, ключ – 128, 192 или 256 бит, длину блока в 128 бит и обычный DES вместо функции f. В итоге получается скорость как у тройного DES и весьма неплохая криптостойкость.
Rijndael – победитель американского конкурса Advanced Encrypting Standard, проводимого Американским институтом стандартизации (
www.nist.gov) в 1997-2000 годах с целью найти надежный и быстрый симметричный блочный алгоритм, способный работать с длинными ключами и оптимизированный под 32-разрядные процессоры, заменивший бы стареющий DES. С победителя сняты все патентые ограничения, и появилась возможность свободно его использовать. Поддерживает длину ключа в 128, 160 и 192 бит, количество итераций колеблется между 10 и 14. Каждая итерация шифрования состоит из четырех частей: представление блока в виде матрицы размерностью 4x4, 4x6 или 4x8 байт с помощью S-блока (размерность зависит от длины ключа), циклический сдвиг в строках таблицы, перемешивание данных в столбцах и XOR-наложение на результат таблицы ключа. На последней итерации отсутствует преобразование, перемешивающее ячейки в столбцах – это делает шифрование обратимым. Считается, что данный алгоритм должен стать стандартом де факто в криптографии на ближайшие 20-30 лет. Другие четыре финалиста конкурса MARS, RC6, Serpent и TwoFish также являются достаточно надежными (а некоторые еще и более быстрыми) криптоалгоритмами.
REDOC – использует 160-битный ключ, 80-битный блок и 10 циклов преобразования. Ориентирован на программную реализацию, использует меняющиеся таблицы подстановок и перестановок. Для него бесперспективна лобовая атака; дифференциальный анализ одного цикла преобразования возможен, но попытки для двух и более циклов успехом не увенчались. Криптографически стойкий шифр.
ГОСТ 28147-89 – российский стандарт, разрабатывался как компромисс между криптостойкостью и эффективностью, и как наш ответ DES’у. Использует 64-битные блоки, 256-битный ключ и сеть Фейстеля с 32 циклами преобразования. Лобовая атака тут непосильна (перебрать 2256 ключей – это страшное дело). О применимости к нему дифференциального и линейного криптоанализа спорят до сих пор (хотя еще ни одного прецедента не было). Хотя у ГОСТа функция f послабее, чем у DES, но большое число циклов сильно усложняют криптоанализ. Алгоритм можно найти в статье А.Шепелева «Алгоритм защиты ГОСТ28147-89» за №8_2002.
Далее кратко: из оставшихся известных мне криптоалгоритмов можно считать довольно надежными RC5 и Khufu, а вот IDEA, FEAL, LOKI и Khafre имеют некоторые слабые стороны, использовать их я бы не порекомендовал.
Поточные шифры
Поточные шифры (stream cipher) или скремблеры преобразовывают открытый текст в шифротекст по одному биту за один такт (clock). При прямом криптографическом преобразовании для каждого i-го бита открытого текста mi по секретному ключу k генерируется бит-ключ ki и накладывается на него: ci = miki. При обратном криптографическом преобразовании происходит наложение ключа ki на соответствующий бит шифротекста ci: mi = ciki. Последовательность ключей k1, k2,…, ki,… генерируется с помощью генератора потока ключей, sequence generator (его еще называют генератором бегущих ключей, саму последовательность называют бегущим ключом или гаммой (keystream), а процесс ее наложения – гаммированием).
Свойства криптосистемы целиком зависят от используемого генератора потока ключей, чем ближе выходящий из него поток бит к случайному, тем надежней будет шифр. Генератор потока ключей должен выдавать поток бит, кажущийся на первый взгляд случайным, но на самом деле являющийся детерминированным, поэтому тот же поток будет восстановлен при дешифровании (при совпадении секретных ключей, конечно). Если выходной поток будет состоять из одинаковых или циклически повторяющихся бит (с маленьким циклом), то прочность такого шифра будет стремиться к нулю.
Для поточных шифров также возможно применение уже упомянутых режимов реализации.
Регистры сдвига с обратной связью
Генераторы потока ключей большинства поточных шифров работают на основе регистров сдвига с обратной связью по переносу (РСОСП, feedback with carry shift register). РСОСП состоит из n-битного регистра, заполняемого первоначально материалом ключа, и функции обратной связи (рисунок 7). Для генерирования очередного бита-ключа ki на каждом такте выполняются следующие действия:
1. все биты в регистре сдвигаются вправо на одну позицию, самый младший, «вылезающий», бит является выходом генератора потока ключей;
2. самый старший бит заполняется результатом функции обратной связи, аргументы которой – или все биты регистра, или только биты с выборочных позиций.
Регистры сдвига с линейной обратной связью
Linear feedback shift register. Сокращенно называются РСЛОС. По сути являются частным случаем РСОСП, в которых функция обратной связи представляет собой суммирование всех аргументов по модулю 2. Регистр РСЛОС может находится в 2n-1 всевозможных состояниях, и последовательность псевдослучайных бит, которые он генерирует, циклична, и теоретически имеет максимальный период 2n-1, хотя при определенных условиях его цикл может иметь и меньшую длину. Если последовательность генерируемых бит интерполировать, описать многочленом (двоичным, естественно, его степень будет равна n), то если такой многочлен не будет разложим на произведения многочленов меньшей степени (будет примитивным), то тогда бегущий ключ такой РСЛОС будет действительно иметь максимальный период. Последовательность генерируемых бит всецело зависит от секретного ключа, и если ключ «плохой», например, состоит из всех нулевых бит, то РСЛОС будет выдавать одни нули.
Не смотря на свои недостатки и подверженность криптоанализу, РСЛОС и его более стойкие модификации часто используют в поточных алгоритмах.
Обзор некоторых поточных шифров
RC4 – поточный шифр, разработанный Р.Ривестом в 1987 году. Алгоритм работает в режиме OFB, может иметь ключ произвольной длины. Скорость шифрования примерно в 10 раз превышает скорость DES. Утверждается, что RC4 в высокой степени нелинеен и устойчив к линейному и дифференциальному криптоанализу. Довольно распространенный алгоритм, входит во многие коммерческие продукты.
SEAL – весьма быстрый шифр, использующий в своей работе семейство псевдослучайных функций, его алгоритм оптимизирован под 32-разрядные процессоры. Не является традиционным поточным шифром, хотя бы потому, что любой i-ый бит его бегущего ключа может быть получен сразу, в любой момент времени, и для этого не требуется считать предыдущие биты с 1 по i-1. Это может быть полезно, например, для шифрования раздела жесткого диска «на лету». При шифровании/дешифровании каждого сектора можно быстро получить нужную последовательность бит ключа и наложить ее на данные.
A5 – поточный шифр, входит в стандарт шифрования цифровых данных мобильных телефонов GSM. Использует три не совсем стандартные РСЛОС длиной 19, 22 и 23 бит. Выходной бит генератора получается из XOR выходных битов этих РСЛОС. Тактирование каждого РСЛОС осуществляется в зависимости от состояния среднего бита в его регистре, поэтому на каждом этапе тактируется в среднем два РСЛОС. Алгоритм, по большому счету, не является очень надежным (в основном из-за коротких регистров), но лежащие в его основе идеи позволяют создавать действительно стойкие шифры.
Асимметричные криптосистемы
Как уже было сказано, ассиметричные шифры используют два ключа: открытый для прямого и секретный для обратного криптографического преобразования. Основные идеи построения таких шифров заключаются в том, что почти все они основаны на алгебре больших целых чисел (от десятков до сотен знаков в десятичном представлении). Поэтому все операции с такими числами реализуются программно, что отрицательно сказывается на скорости. Посему в этом разделе я рассмотрю наиболее распространенный криптоалгоритм RSA. Другой представитель этой группы описан в статье А.Беляева «Асимметричная криптография: схема ElGamal» в номере тут номер журнала. Отмечу лишь, что программная реализация алгоритма ЭльГамаля примерно на порядок медленнее RSA.
Криптосистема RSA
Алгоритм RSA (R.Rivest, A.Shamir, L.Adleman) был предложен еще в 1977 году. С тех пор он весьма упорно противостоит различным атакам, и сейчас является самым распространенным криптоалгоритмом в мире. Он входит во многие криптографические стандарты, используется во многих приложениях и секретных протоколах (включая PEM, S-HTTP и SSL).
Основные принципы работы RSA
Сначала пара математических определений. Целое число называют простым (prime), если оно делится нацело только на единицу и на само себя, иначе его называют составным (composite). Два целых числа называют взаимно простыми (relatively prime), если их наибольший общий делитель (НОД) равен 1.
Алгоритм работы RSA таков. Сначала надо получить открытый и секретный ключи:
1. берутся два больших целых простых числа p и q (лучше равной длины, для большей криптостойкости);
2. вычисляется n = pq и -функцию Эйлера (Euler’s phi function) (n) = (p-1)(q-1);
3. потом случайным образом выбирается число e, такое чтобы e и (n) были взаимно простыми (чаще всего для эффективности предлагают брать 3, 17 или 65537);
4. вычисляется d, как решение уравнения de = 1 (mod (n)).
В результате получаем составные ключи: открытый – (e, n) и секретный – (d, n).
Прямое и обратное криптографическое преобразования RSA производятся над блоками текста, длина которых меньше длины n в двоичном представлении (за длину блока можно взять самую большую степень 2, меньшую n, т.е. log2 n ). Для шифрования надо разбить открытый текст m на блоки и выполнить над каждым блоком такое действие: ci = (mi)e (mod n), а для дешифрования: mi = (ci)d (mod n). Верно будет и обратное: если Алиса зашифрует сообщение на своем секретном ключе, то любой сможет его расшифровать на Алисином открытом ключе, действительно убедившись, что сообщение было отправлено Алисой. Это один из примеров цифровой подписи (digital signature). И еще: когда говорят о длине ключа RSA, имеют в виду длину числа n.
Особенности RSA
Криптосистема RSA основана на том, что зная только e и n, злоумышленнику для получения компоненты секретного ключа d надо найти только (n) (то есть, фактически, p и q). Cделать это он может разложив n на простые множители (факторизовав, factorization), а вот сколько-нибудь приемлемого по времени работы алгоритма, позволяющего такое сделать, еще придумали. Даже самые быстрые современные суперкомпьютеры, используя наиболее совершенный на сегодняшний день алгоритм (метод обобщенного решета числового поля, general number field sieve), не способны разложить взятое наугад 200-значное число за разумное время. Но никогда не было доказано математически, что факторизация является такой трудоемкой процедурой. Однако за 35 лет существования RSA достаточно быстрого способа так и не придумали, и это наводит на мысль, что это действительно так.
В 1990-х годах с помощью распределенных вычислений через Internet предпринимались удачные попытки факторизовать некоторые произвольные большие числа. Максимальное факторизованное число имело 140 десятичных разрядов (1999 год), на что ушло около 2000 MY (Mips/Year – годовая работа компьютера мощностью в миллион целочисленных операций в секунду). Учитывая это, сейчас специалисты (Лаборатория RSA,
www.rsa.com/rsalabs) рекомендуют использовать минимальную длину ключа n, не менее чем 768 бит (~230 десятичных рзрядов) для малосекретной информации, 1024 бит для обычной и 2048 для особо секретной. Использующаяся в старых продуктах длина ключа в 512 бит (~160 разрядов) уже под угрозой взлома.
Известно, что RSA имеет низкую криптостойкость при шифровании коротких блоков. В таких случаях злоумышленник может взять от блока шифротекста корень степени e по модулю n, что в данном случае будет намного быстрее факторизации. Поэтому короткие блоки обязательно надо «набивать» дополнительными битами.
Еще один интересный вопрос касается простых чисел. Для построения ключей алгоритму RSA необходимо найти два простых числа. Благо, среди чисел простые попадаются довольно часто: на отрезке от 1 до n примерно n/ln(n) чисел являются простыми. Поэтому можно просто брать псевдослучайные числа нужной длины и проверять их на простоту. Проверку числа на простоту можно делать двумя способами: «в лоб», перебором всех его делителей (от 2 до округленного корня из n), или с помощью более «хитрых» тестов на делимость. При переборе всех делителей мы гарантированно можем утверждать, что прошедшее такую проверку число является простым. Однако, время работы такой процедуры будет очень велико. Среди «хитрых» тестов надо выделить тест Миллера–Рабина, так как он на сегодняшний день является наиболее лучшим по всем параметрам. Так вот, проверка Миллера–Рабина работает намного быстрее перебора делителей, но в отличие от него, число, выдаваемое им как простое, с некоторой очень маленькой вероятностью может оказаться составным. На практике обычно применяют последовательно несколько разных «хитрых» тестов, минимизируя тем самым вероятность ошибки.
Программная реализация RSA работает медленнее примерно на два порядка по сравнению с симметричными алгоритмами. RSA часто используют вместе с каким-нибудь симметричным шифром. При таком способе все сообщения шифруются с помощью более быстрого симметричного алгоритма, а для пересылки сессионного секретного ключа этого симметричного алгоритма используется RSA. Получается вычислительно дешево и сердито.
Вместо заключения
Пара практических советов. Если в шифре не оговаривается алгоритм «набивки» (padding) не кратного длине блока сообщения, то можно применить такой наиболее распространенный способ: сообщение дополняется до длины, кратной длине блока, и минус 64 бита мусором или нулями с первой единицей, а последним недостающим 64 битам присваивается настоящая длина сообщения. Что касается выбора длины ключа, то тут эксперты часто расходятся во мнениях. И если вам не страшны ограничения, накладываемые законодательством, то, выбирая длину ключа, всегда встает дилемма между надежностью и скоростью. Всегда склоняйтесь к первому: мощность компьютеров со временем растет, а с ней и опасность взлома. Надо сопоставлять время, в течение которого шифруемая информация должна быть секретна, с временем возможной лобовой атаки, учитывая стоимость информации и стоимость для злоумышленника тех вычислительных средств, которые он может привлечь, а также рост мощностей этих средств со временем.
Что хотелось бы посоветовать программистам, впервые столкнувшимся с проблемой использования криптоалгоритмов? При выборе нужного алгоритма надо посоветоваться с более сведущими людьми и серьезно поизучать хорошую литературу, которой, к сожалению, на русском языке встречается очень мало (теперь угадайте, зачем я давал английские термины?). И не изобретайте своих алгоритмов, так как, скорее всего, это будет защита только от домохозяек.
Литература
[1] А.Чмора, «Современная прикладная криптография», М.: Гелиос APB, 2002.
[2] Под ред. В.Ященко, «Введение в криптографию», М.: МЦНМО, 2000.
[3] Т.Кормен, Ч.Лейзерсон, Р.Ривест, «Алгоритмы: построение и анализ», М.: МЦНМО, 2001. Здесь можно найти алгоритм RSA.
[4] www.cryptography.ru
Вложение: 3523221_cryptography.doc
Вложение: 3523547_KIRPICHI.doc
