К заглавной странице

Основные Понятия для начинающих.

Итак, Вы решили окунуться в современные шифросистемы и криптографические науки (или хотя бы просто познакомиться с ними поближе). Надеемся, что в данной статье вы найдете все необходимое для того, чтобы больше не пугаться страшных слов DES, RSA, ECB, цифровая подпись и т.д. Если вдруг у Вас возникнут какие-либо вопросы, будем рады ответить на них по адресу wincrypt@mail.ru или в нашей гостевой книге. Ну что же, приступим !!!

1. История шифров

2. Криптология и ее основные понятия.

3. Симметричные криптосистемы.

3.1 Блочные шифры.

3.2 Поточные шифры.

4. Асимметричные криптосистемы.

4.1 Односторонние функции.

4.2 Принцип работы.

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

6. Хэш-функции.

7. Распределение ключей.

2. Криптология и ее основные понятия.

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

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

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

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

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

Криптографическая система - семейство преобразований шифра и совокупность ключей (т.е алгоритм + ключи). Само по себе описание алгоритма не является криптосистемой. Только дополненное схемами распределения и управления ключами оно становится системой. Примеры алгоритмов - описания DES, ГОСТ28.147-89. Дополненые алгоритмами выработки ключей, они превращаются в криптосиситемы. Как правило, описание алгоритма шифрования уже включает в себя все необходимые части. 

Современные криптосистемы классифицируют следующим образом:

System.gif (1563 bytes)

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

Симметричные криптосистемы (с секретным ключом - secret key systems)- данные криптосистемы построены на основе сохранения в тайне ключа шифрования. Процессы зашифрования и расшифрования используют один и тот же ключ. Секретность ключа является постулатом. Основная проблема при применении симметричных криптосистем для связи заключается в сложности передачи обоим сторонам секретного ключа. Однако данные системы обладают высоким быстродействием. Раскрытие ключа злоумышленником грозит раскрытием только той информации, что была зашифрована на этом ключе.  Американский и Российский стандарты шифрования DES и ГОСТ28.147-89, кандидаты на AES - все эти алгоритмы являются представителями симметричных криптосистем.   

Асимметричные криптосистемы (системы открытого шифрования - о.ш., с открытым ключом и т.д.- public key systems) - смысл данных криптосистем состоит в том, что для зашифрования и расшифрования используются разные преобразования. Одно из них - зашифрование - является абсолютно открытым для всех. Другое же - расшифрование - остается секретным. Таким образом, любой, кто хочет что-либо зашифровать, пользуется открытым преобразованием. Но расшифровать и прочитать это сможет лишь тот, кто владее секретным преобразованием. В настоящий момент во многих асимметричных криптосистемах вид преобразования определяется ключом. Т.е у пользователя есть два ключа - секретный и открытый. Открытый ключ публикуется в общедоступном месте, и каждый, кто захочет послать сообщение этому пользователю - зашифровывает текст открытым ключом. Расшифровать сможет только упомянутый пользователь с секретным ключом. Таким образом, пропадает проблема передачи секретного ключа (как у симметричных систем). Однако, несмотря на все свои преимущества, эти криптосистемы достаточно трудоемки и медлительны. Стойкость асимметричных криптосистем базируется, в основном,  на алгоритмической трудности решить за приемлимое время какую-либо задачу. Если злоумышленнику удастся построить такой алгоритм, то дискредетирована будет вся система и все сообщения, зашифрованые с помощью этой системы. В этом состоит главная опасность асимметричных криптосистем в отличие от симметричных. Примеры - системы о.ш. RSA, система о.ш. Рабина и т.д.

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

  3. Симметричные Криптосистемы.

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

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

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

Однако не следует считать это разделение закостенелым. Так, например, при использовании некоторых ухищрений получают из блочного шифра - поточный и наоборот (см. БЛОЧНЫЕ ШИФРЫ). А, например, блочный шифр с размером выходного блока 8 бит (один символ) можно считать поточным.

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

Begin1.gif (3676 bytes)

  где М - открытый текст, К - секретный ключ, передаваемый по закрытому каналу, Ек(М) - операция зашифрования, а Dk(M) - операция расшифрования. Возникает вопрос - почему нельзя передавать данные сразу по закрытому каналу, ведь используется же он для передачи ключа? Ответ прост. Как правило, закрытый канал имеет очень высокую защищенность, но в то же время и очень низкую пропускную способность, т.е. работает на очень низких скоростях. Гораздо проще передать по нему маленький ключ, чем мегабайты информации. Или же в качестве закрытого канала используется курьерская доставка, обмен секретным ключом при встрече и т.д. 

3.1 Блочные шифры

Устройство шифров.

Блочные шифры оперируют с блоками открытого текста. К ним предъявляются следующие требования:

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

Само преобразование шифра должно использовать следующие принципы (по К. Шеннону):

Практически все современные блочные шифры являются композиционными - т.е состоят из композиции простых преобразований или F=F1oF2oF3oF4o..oFn, где F-преобразование шифра, Fi-простое преобразование, называемое также i-ым циклом шифрования. Само по себе преобразование может и не обеспечивать нужных свойств, но их цепочка позволяет получить необходимый результат. Например, стандарт DES состоит из 16 циклов. В иностранной литературе такие шифры часто называют послойными (layered). Если же используется одно и то же преобразование, т.е. Fi постоянно для "i, то такой композиционный шифр называют итерационным шифром.   

Наибольшую популярность имеют шифры, устроенные по принципу "шифра Фейстеля (Файстеля - Feistel)" (петли Фейстеля, сети Файстеля), т.е в которых:

  1. входной блок для каждого преобразования разбивается на две половины: p=(l,r), где l-левая, r-правая;
  2. используется преобразование вида Fi ( l, r )=( r, l Д fi (r) ), где fi - зависящая от ключа Ki функция, а Д - операция XOR или некая другая.

. Функция fi называется цикловой функцией, а ключ Ki, используемый для получения функции fi называется цикловым ключом. Как можно заметить, с цикловой функцией складывается только левая половина, а правая остается неизменной. Затем обе половины меняются местами. Это преобразование прокручивается несколько раз (несколько циклов) и выходом шифра является получившаяся в конце пара (l,r) Графически  все выглядит следующим образом:

Begin2.gif (3245 bytes)

В качестве функции fi выступает некая комбинация перестановок, подстановок, сдвигов, добавлений ключа и прочих преобразований. Так, при использовании подстановок информация проходит через специальные блоки, называемые S-блоками (S-боксами, S-boxes), в которых значение группы битов заменяется на другое значение. По такому принципу (с небольшими отличиями) построены многие алгоритмы: DES, FEAL, серия LOKI и т.д.

В других алгоритмах используются несколько иные принципы. Так, например, алгоритмы, построенные по SP-принципу (SP-сети) осуществляют преобразование, пропуская блок через последовательность подстановок (Substitutions) и перстановок (Permutations). Отсюда и название - SP-сети, т.е. сети "подстановок-перстановок". Примером такого алгоритма является очень перспективная разработка Rijndael. Возможно применение в алгоритмах и каких-либо новых конструкций, но как правило, они несут в себе оперделенные ошибки (пример - FROG, HPC). Но все перечисленные алгоритмы являются композиционными. Саму идею построения криптографически стойкой системы путем последовательного применения относительно простых криптографических преобразований была высказана Шенноном (идея многократного шифрования).

Размеры блоков в каждом алгоритме свои. DES использует блоки по 64 бита (две половинки по 32 бита), LOKI97 - 128 бит. При размере выходных блоков до 8 бит шифр можно считать поточным.

Получение цикловых ключей.

Ключ имеет фиксированную длину. Однако при прокрутке хотя бы 8 циклов шифрования с размером блока, скажем, 128 бит даже при простом прибавлении посредством XOR потребуется 8*128=1024 бита ключа, поскольку нельзя добавлять в каждом цикле одно и то же значение - это ослабляет шифр. Посему для получения последовательности ключевых бит придумывают специальный алгоритм выработки цикловых ключей (ключевое расписание - key schedule). В результате работы этого алгоритма из исходных бит ключа шифрования получается массив бит определенной длины, из которого по определенным правилам составляются цикловые ключи. Каждый шифр имеет свой алгоритм выработки цикловых ключей.

Режимы работы блочных шифров.

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

Обозначим применение шифра к блоку открытого текста как Ek(M)=C, где k - ключ, M - блок открытого текста, а C - получающийся шифротекст.

Электронная Кодовая Книга (ECB)

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

begin3.gif (4007 bytes)

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

Основным достоинством этого режима является простота реализации.

Сцепление блоков шифротекста (CBC)

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

  1. Первый блок складывается побитно по модулю 2 (XOR) с неким значением IV - начальным вектором (Init Vector), который выбирается независимо перед началом шифрования.
  2. Полученное значение шифруется.
  3. Полученный в результате блок шифротекста отправляется получателю и одновременно служит начальным вектором IV для следующего блока открытого текста.

Расшифрование осуществляется в обратном порядке. Графически схема выглядит следующим образом:

begin4.gif (6071 bytes)

В виде формулы, преобразование в режиме CBC можно представить как Ci=Ek(MiЕCi-1), где i - номер соответствующего блока. Из-за использования такого сцепления блоков шифротекста с открытым текстом пропадают указанные выше недостатки режима ECB, поскольку каждый последующий блок зависит от всех предыдущих. Если во время передачи один из блоков шифротекста исказится (передастся с ошибкой), то получатель сможет корректно расшифровать последующие блоки сообщения. Проблемы возникнут только с этим "бракованным" и следующим блоками. Одним из важных свойств этого режима является "распространение ошибки" - изменение блока открытого текста меняет все последующие блоки шифротекста. Поскольку последний блок шифротекста зависит от всех блоков открытого текста, то его можно использовать для контроля целостности и аутентичности (проверки подлинности) сообщения. Его называют кодом аутентификации сообщения (MAC - Message Authentication Code). Он может защитить как от случайных, так и преднамеренных изменений в сообщениях.

Обратная связь по шифротексту (CFB)

Режим может использоваться для получения из поточного шифра из блочного. Размер блока в данном режиме меньше либо равен размеру блока шифра. Схема данного режима:

begin5.gif (5381 bytes)

  1. IV представляет собой сдвиговый регистр. Вначале IV заполняется неким значением, которое называется синхропосылкой, не является секретным и передается перед сеансом связи получателю.
  2. Значение IV шифруется.
  3. Берутся первые k бит зашифрованного значения IV и складываются (XOR) с k битами открытого текста Ю получается блок шифротекста из k бит.
  4. Значение IV сдвигается на k битов влево, а вместо него становится значение ш.т.
  5. Затем опять 2 пункт и т.д до конца.

Расшифрование аналогично.

Особенностью данного режима является распространение ошибки на весь последующий текст. Рекомендованные значения k: 1 =< k =< 8. 

Применяется как правило для шифрования потоков информации типа оцифрованной речи, видео.

Обратная связь по выходу (OFB)

Данный режим примечателен тем, что позволяет получать поточный шифр в его классическом виде (см ПОТОЧНЫЕ ШИФРЫ), в отличии от режима CFB, в котором присутствует связь с шифротекстом. Принцип работы схож с принципом работы режима CFB, но сдвиговый регистр IV заполняется не битами шифротекста, а битами, выходящими из под усечения. Вот его схема:

begin6.gif (5497 bytes)

Расшифрование осуществляется аналогично. Т.е. для любого блока длины k операция зашифрования выглядит следующим образом: Ci=MiЕGi, где Gi - результат зашифрования некоторого вектора, являющегося заполнением сдвигового регистра. Главное свойство шифра - единичные ошибки не распространяются, т.к заполнение сдвигового регистра осуществляется не зависимо от шифротекста.

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

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

Настал черед еще нескольких определений:

Аутентификация (authentication) - проверка подлинности чего(или кого-)-либо. Может быть аутентификация пользователя, сообщения и т.д. Необходимо отличать ее от следующего понятия:

Идентификация (identification) - некое описательное представление какого-то субьекта. Так, если кто-то заявляет, что он - Вася Иванов, то он идентифицирует себя как "Вася Иванов". Но проверить, так ли это на самом деле (провести аутентификацию) мы можем только при помощи его паспорта.

Итак, как же можно проверить подлинность сообщения с помощью блочного шифра? Довольно просто.

  1. Отправитель А хочет отправить некое сообщение (a1,..,at ). Он зашифровывает его на секретном ключе, который знает только он и получатель, в режиме CBC или CFB это сообщение, а затем из получившегося шифротекста берет последний блок bt из к бит (при этом к должно быть достаточно большим).
  2. Отправитель А посылает сообщение (a1, .. , at , bt ) получателю в открытом виде или зашифровав его на другом ключе.
  3. Получатель В, получив сообщение,  (a1, .. , at , bt ), зашифровывает (a1,..,at ) в том же режиме, что и А (должна быть договоренность) на том же секретном ключе (который знает только он и А).
  4. Сравнивая полученный результат с bt он удостоверяется, что сообщение отправил А, что оно не было подделано на узле связи (в случае передачи в открытом виде).

В данной схеме bt является кодом аутентификации сообщения (МАС). Для российского стандарта шифрования процесс получения кода аутентификации называется работой в режиме имитовставки.

Некоторые комментарии:

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

3.2 Поточные шифры

Устройство шифров.

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

                            ci = mi Е ki для i=1,2,3...  

где ci - знак шифротекста, mi - знак открытого текста, ki - знак ключевой последовательности. Расшифрование выглядит так:

                           mi = ci Е ki для i=1,2,3... 

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

begin7.gif (2770 bytes)

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

Синхронные поточные шифры - ключевой поток (выходная гамма) получается независимо от исходного и шифрованного текстов.   В данном случае наша иллюстрация меняется в следующую:

begin8.gif (3559 bytes)

Шифр вырабатывает гамму на основе секретного ключа, она складывается с открытым текстом и результат посылается другому абоненту и расшифровывается аналогично. Блок, вырабатывающий гамму называется генератором гаммы или псевдослучайным генератором (гаммы) - PRG(Pseudo Random Generator). Любой блочный шифр в режиме OFB представляет собой синхронный поточный шифр.

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

Генераторы гаммы вырабатывают так называемые псевдослучайные последовательности, которые зависят от ключа шифрования, но тем не менее по своим характеристикам сходны со случайными. Задача ставится таким образом, чтобы при наличии определнного количества битов последовательности нельзя было предсказать следующие биты. Помимо этого 1 и 0 на входе должны быть равновероятны (т.е. вероятность появления 1 = вер-ти появления 0 = 0.5). Для достижения этого последовательности исследуются статистическими тестами.

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

Синхронные поточные шифры обладают следующими свойствами:

Рассмотрим одну из атак на такие шифры.

O1O2O3... - знаки открытого текста.

К1К2К3... - знаки ключевой последовательности.

С1С2С3... - знаки шифротекста, полученные следующим образом:

begin10.gif (722 bytes)

Допустим, что при повторном шифровании на том же ключе произошла вставка одного знака O':

begin11.gif (722 bytes)

Криптоаналитик противника перехватил обе последовательности C1C2C3C4 и C1C'2C'3C'4. Составив затем уравнения: К2 =C'2 Е O'; O2=C2 Е К2; К3=C'3 Е O2; O3=C3ЕК3 и т.д., и подобрав значение одного знака O' он сможет прочитать сообщение после этого знака. Поскольку в результате исследований у него будет фрагмент ключевой последовательности (гаммы), то он может попытаться восстановить всю гамму и получить сообщение целиком (если вэтом есть необходимость, конечно).  Отсюда можно сделать вывод, что нельзя дважды использовать один и тот же ключ.

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

Даже если 2 абсолютно различных текста шифруются на одном ключе, противник может вычислить сумму знаков шифртекстов Ci1Е Ci2 =Oi1Е Кi Е Кi Е Oi2=Oi1Е Oi2, где Ci1- i-ый знак первого шифртекста, Ci2 - i-ый знак второго, Oi1 и Oi2 - знаки открытых текстов соответственно.

Сумма открытых текстов отнюдь не случайна и противник сможет восстановить 2 сообщения.

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

begin12.gif (4030 bytes)

Данному типу шифров соответствуют блочные шифры, работающие в режиме CFB.

Самосинхронизирующиеся поточные шифры обладают следующими свойствами:

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

  4. Асимметричные Криптосистемы.

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

4.1 Односторонние функции

Односторонняя (однонаправленная) функция (one way function) - это функция f осуществляющая отображение X->Y, где X и Y - произвольные множества, и удовлетворяющая следующим условиям:

  1. "xОX (области оперделения) легко вычислить y=f(x), yОY.
  2. Почти для любого yОY (области значения) найти f -1(y), т.е. x, для которого y=f(x), вычислительно невозможно.

Почему в определнии стоит "почти для любого"? Потому, что если взять некоторый x и вычислить для него y=f(x), то мы уже будем знать, что полученному y соответствует взятый нами x. Сохраним эти 2 значения и если когда-нибудь мы столкнемся с таким y, то мы спокойно найдем x.

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

Примером применения односторонней функции может служить следующая схема идентифкации.

Абонент A вырабатывает следующую последовательность: x0, f(x0)=x1, ..., f(x99)=x100.

Затем  x100 передается по секретному каналу (или при встрече) абоненту B.

Когда А необходимо идентифицировать себя, он передает по открытому каналуB x99 . В проверяет, f(x99)=?x100 .

В следующий раз А передаст x99 и В проверит f(x98)=?x99  и т.д. Перехват сообщений на i-ом этапе в открытом канале ничего не даст злоумышленнику, т.к. он не сможет получить соответсвующее значение xi-1(из-за односторонней функции), чтобы в следующий раз идентифицировать себя как абонента А. Данная схема представлена на следующем рисунке:

begin9.gif (2587 bytes)

Такие схемы применяются для идентифкации "свой/чужой".

Односторонней функцией с секретом (trapdoor one way function) называют функцию fk осуществляющая отображение X->Y, где X и Y - произвольные множества, и удовлетворяющая следующим условиям:

  1. "xОX (области оперделения) легко вычислить y=fk(x), yОY.
  2. При известном k "yОY  легко вычислить x=fk -1(y),xОX.
  3. Почти для всех k и почти для всех y нахождение x=fk -1(y) вычислительно невозможно без знания параметра k.

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

4.2 Принцип работы

Существует несколько хорошо известных асимметричных криптосистем: RSA, Эль Гамаля (El Gamal), Рабина (Rabin). Поскольку в этих криптосистемах вид преобразования определяется ключом, публикуют только открытый ключ с указанием, для какой криптосистемы он используется. Секретный и открытый ключ как правило взаимосвязаны между собой, но то, как конкретно они связаны - известно только их владельцу и получить секретный ключ по соответствующему открытому ключу вычислительно невозможно.

Итак, пусть имеются 2 абонента A и В. A имеет открытый ключ e и соответствующий секретный ключ d. Открытый ключ оперделяет преобразование зашифрования Ee , а секретный - преобразование расшифрования Dd. Открытый ключ e абонента А находится в общедоступном месте. Когда B желает послать сообщение m абоненту A, он берет открытый ключ e, принадлежащий А, и, используя его, получает шифртекст c=Ee(m). Затем он посылает c абоненту А. Для того, чтобы расшифровать сообщение, А, используя свой секретный ключ применяет  преобразование расшифрования и получает исходное сообщение: m=Dd (c).

begin13.gif (2801 bytes)

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

Чтобы проиллюстрировать работу асимметричных криптосистем, приведем описание схемы RSA (в упрощенном варианте, т.е. без математических основ теории чисел, теорем и т.д.) и на ее примере рассмотрим основные моменты, присущие асимметричным криптосистемам.

  1. Выбираются p,q - большие простые числа. Вычисляется произведение n=pq.
  2. Выбирается число e - такое, что (e, j(n))=1 (т.е e и j(n) - взаимнопросты), где j(n)=(p-1)(q-1) - функция Эйлера от n.
  3. Из уравнения ed=1(mod j(n)) находится число d. Запись x mod n означает, что берется остаток от деления x на n (x по модулю n), а запись x=a (mod n) означает, что остаток от деления x на n равен а. Т.е. находится такое число d, что остаток от деления произведения ed на n равен 1.

Полученные числа e,n - открытый ключ пользователя, а d - секретный ключ. Из условия 3 следует, что ed=1+kj(n),где k - какое-то число.

Процедура зашифрования: C=E(e,n)(M)=Me(mod n), где С-получаемый ш.т. , M - о.т., удовлетворяющий следующему условию: Mj(n)=1(mod n).

Процедура расшифрования: M=D(d,n)(C)=Cd(mod n)=(Me)d(mod n)=(M1+kj(n))(mod n)=M(Mj(n))k(mod n)=M.

В криптосистеме RSA, как и во многих других асимметричных криптосистемах, сообщение представляется в виде некоторого числа, которое потом обрабатывается определенным образом (например, зашифровывается). Практически все ассиметричные криптосистемы строятся на основе математических проблем, для которых пока не найдено эффективного алгоритма решения. Следовательно, все параметры RSA должны выбираться таким образом, чтобы злоумышленник не мог за приемлимое время получить ключи схемы или какие-либо другие параметры (например, числа p и q), позволяющие ему осуществить атаку. Так, для RSA рекомендована длина n 768 бит, в случае долговременного  использования - 1024 бита (в этом случае длина p и q будет по 512 бит).

Скорость работы и экспонента e

Поскольку криптосистема работает с очень большими числами и выполняет такие "трудные" действия, как возведение в степень, то быстродействие криптосистемы невысоко. Асимметричные криптосистемы уступают в скорости симметричным именно "благодаря" использованию таких преобразований. Существуют различные методы повышения скорости RSA. Например, в качестве открытого ключа e берется e=3. Тогда для того, чтобы зашифровать, необходимо всего 3 умножения. Правда в этом случае получается большое d, но предполагают, что у расшифровывающего есть время. Однако использование малой экспоненты e приводит к проблемам с маленькими сообщениями, т.е таких, что M<n1/e, поскольку в этом случае M может быть получено из шифртекста C=Me mod n путем вычисления корня e-ой степени из C.

Добавление в сообщение дополнительной информации (salting)

Для того, чтобы избежать описанной проблемы для маленьких сообщений, а также для невозможности осуществления других атак (см. Криптоанализ:Атаки на RSA) в сообщение добавляется некоторая случайная строка определенной длины (salt). После получения и расшифровки эта строка удаляется.

Мультипликативные свойства

Пусть m1 b m2 - 2 различных открытых текста, а c1 и с2 - соответствующие им шифртексты. Заметим, что

(m1m2)e=m1e m2e=c1c2 (mod n)

Другими словами, шифртекст открытого текста m=m1m2 есть c=c1c2 (mod n). Это свойство, называемое также гомоморфным свойством RSA, позволет осуществить атаку по выбранному шифртексту (см. Криптоанализ:Атаки на RSA).

Блочная структура

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

  

 

 

 

 

Пока конец.