Асимметричное шифрование. Как это работает? Методы шифрования данных - блог веб-программиста
Шифрование данных чрезвычайно важно для защиты конфиденциальности. В этой статье я расскажу о различных типах и методах шифрования, которые используются для защиты данных сегодня.
Знаете ли вы?
Еще во времена Римской империи, шифрование использовалось Юлием Цезарем для того, чтобы сделать письма и сообщения нечитаемыми для врага. Это играло важную роль как военная тактика, особенно во время войн.
Так как возможности Интернета продолжают расти, все больше и больше наших предприятий проводятся на работу онлайн. Среди этого наиболее важными являются, интернет банк, онлайн оплата, электронные письма, обмен частными и служебными сообщениями и др., которые предусматривают обмен конфиденциальными данными и информацией. Если эти данные попадут в чужие руки, это может нанести вред не только отдельному пользователю, но и всей онлайн системе бизнеса.
Чтобы этого не происходило, были приняты некоторые сетевые меры безопасности для защиты передачи личных данных. Главными среди них являются процессы шифрования и дешифрования данных, которые известны как криптография. Существуют три основные методы шифрования, используемых в большинстве систем сегодня: хеширование, симметричное и асимметричное шифрование. В следующих строках, я расскажу о каждом из этих типов шифрования более подробно.
Типы шифрования
Симметричное шифрование
При симметричном шифровании, нормальные читабельные данные, известные как обычный текст, кодируется (шифруется), так, что он становится нечитаемым. Это скремблирование данных производится с помощью ключа. Как только данные будут зашифрованы, их можно безопасно передавать на ресивер. У получателя, зашифрованные данные декодируются с помощью того же ключа, который использовался для кодирования.
Таким образом ясно что ключ является наиболее важной частью симметричного шифрования. Он должен быть скрыт от посторонних, так как каждый у кого есть к нему доступ сможет расшифровать приватные данные. Вот почему этот тип шифрования также известен как "секретный ключ".
В современных системах, ключ обычно представляет собой строку данных, которые получены из надежного пароля, или из совершенно случайного источника. Он подается в симметричное шифрование программного обеспечения, которое использует его, чтобы засекретить входные данные. Скремблирование данных достигается с помощью симметричного алгоритма шифрования, такие как Стандарт шифрования данных (DES), расширенный стандарт шифрования (AES), или международный алгоритм шифрования данных (IDEA).
Ограничения
Самым слабым звеном в этом типе шифрования является безопасность ключа, как в плане хранения, так и при передаче аутентифицированного пользователя. Если хакер способен достать этот ключ, он может легко расшифровать зашифрованные данные, уничтожая весь смысл шифрования.
Еще один недостаток объясняется тем, что программное обеспечение, которое обрабатывает данные не может работать с зашифрованными данными. Следовательно, для возможности использовать этого программного обеспечение, данные сначала должны быть декодированы. Если само программное обеспечение скомпрометировано, то злоумышленник сможет легко получить данные.
Асимметричное шифрование
Асимметричный ключ шифрования работает аналогично симметричному ключу, в том, что он использует ключ для кодирования передаваемых сообщений. Однако, вместо того, чтобы использовать тот же ключ, для расшифровки этого сообщения он использует совершенно другой.
Ключ, используемый для кодирования доступен любому и всем пользователям сети. Как таковой он известен как «общественный» ключ. С другой стороны, ключ, используемый для расшифровки, хранится в тайне, и предназначен для использования в частном порядке самим пользователем. Следовательно, он известен как «частный» ключ. Асимметричное шифрование также известно, как шифрование с открытым ключом.
Поскольку, при таком способе, секретный ключ, необходимый для расшифровки сообщения не должен передаваться каждый раз, и он обычно известен только пользователю (приемнику), вероятность того, что хакер сможет расшифровать сообщение значительно ниже.
Diffie-Hellman и RSA являются примерами алгоритмов, использующих шифрование с открытым ключом.
Ограничения
Многие хакеры используют «человека в середине» как форму атаки, чтобы обойти этот тип шифрования. В асимметричном шифровании, вам выдается открытый ключ, который используется для безопасного обмена данными с другим человеком или услугой. Однако, хакеры используют сети обман, чтобы заставить вас общаться с ними, в то время как вас заставили поверить, что вы находитесь на безопасной линии.
Чтобы лучше понять этот тип взлома, рассмотрим две взаимодействующие стороны Сашу и Наташу, и хакера Сергея с умыслом на перехват их разговора. Во-первых, Саша отправляет сообщение по сети, предназначенное для Наташи, прося ее открытый ключ. Сергей перехватывает это сообщение и получает открытый ключ, связанный с ней, и использует его для шифрования и передачи ложного сообщения, Наташе, содержащего его открытый ключ вместо Сашиного.
Наташа, думая, что это сообщение пришло от Саши, теперь шифрует ее с помощью открытого ключа Сергея, и отправляет его обратно. Это сообщение снова перехватил Сергей, расшифровал, изменил (при желании), зашифровал еще раз с помощью открытого ключа, который Саша первоначально отправил, и отправил обратно к Саше.
Таким образом, когда Саша получает это сообщение, его заставили поверить, что оно пришло от Наташи, и продолжает не подозревать о нечестной игре.
Хеширование
Методика хеширования использует алгоритм, известный как хэш-функция для генерации специальной строки из приведенных данных, известных как хэш. Этот хэш имеет следующие свойства:
- одни и те же данные всегда производит тот же самый хэш.
- невозможно, генерировать исходные данные из хэша в одиночку.
- Нецелесообразно пробовать разные комбинации входных данных, чтобы попытаться генерировать тот же самый хэш.
Таким образом, основное различие между хэшированием и двумя другими формами шифрования данных заключается в том, что, как только данные зашифрованы (хешированы), они не могут быть получены обратно в первозданном виде (расшифрованы). Этот факт гарантирует, что даже если хакер получает на руки хэш, это будет бесполезно для него, так как он не сможет расшифровать содержимое сообщения.
Message Digest 5 (MD5) и Secure Hashing Algorithm (SHA) являются двумя широко используемыми алгоритмами хеширования.
Ограничения
Как уже упоминалось ранее, почти невозможно расшифровать данные из заданного хеша. Впрочем, это справедливо, только если реализовано сильное хэширование. В случае слабой реализации техники хеширования, используя достаточное количество ресурсов и атаки грубой силой, настойчивый хакер может найти данные, которые совпадают с хэшем.
Сочетание методов шифрования
Как обсуждалось выше, каждый из этих трех методов шифрования страдает от некоторых недостатков. Однако, когда используется сочетание этих методов, они образуют надежную и высоко эффективную систему шифрования.
Чаще всего, методики секретного и открытого ключа комбинируются и используются вместе. Метод секретного ключа дает возможность быстрой расшифровки, в то время как метод открытого ключа предлагает более безопасный и более удобный способ для передачи секретного ключа. Эта комбинация методов известна как "цифровой конверт". Программа шифрования электронной почты PGP основана на технике "цифровой конверт".
Хеширования находит применение как средство проверки надежности пароля. Если система хранит хэш пароля, вместо самого пароля, он будет более безопасным, так как даже если хакеру попадет в руки этот хеш, он не сможет понять (прочитать) его. В ходе проверки, система проверит хэш входящего пароля, и увидит, если результат совпадает с тем, что хранится. Таким образом, фактический пароль будет виден только в краткие моменты, когда он должен быть изменен или проверен, что позволит существенно снизить вероятность его попадания в чужие руки.
Хеширование также используется для проверки подлинности данных с помощью секретного ключа. Хэш генерируется с использованием данных и этого ключа. Следовательно, видны только данные и хэш, а сам ключ не передается. Таким образом, если изменения будут сделаны либо с данными, либо с хэшем, они будут легко обнаружены.
В заключение можно сказать, что эти методы могут быть использованы для эффективного кодирования данных в нечитаемый формат, который может гарантировать, что они останутся безопасными. Большинство современных систем обычно используют комбинацию этих методов шифрования наряду с сильной реализацией алгоритмов для повышения безопасности. В дополнение к безопасности, эти системы также предоставляют множество дополнительных преимуществ, таких как проверка удостоверения пользователя, и обеспечение того, что полученные данные не могут быть подделаны.
Сергей Панасенко
,
начальник отдела разработки программного обеспечения фирмы «Анкад»,
[email protected]
Основные понятия
Процесс преобразования открытых данных в зашифрованные и наоборот принято называть шифрованием, причем две составляющие этого процесса называют соответственно зашифрованием и расшифрованием. Математически данное преобразование представляется следующими зависимостями, описывающими действия с исходной информацией:
С = Ek1(M)
M" = Dk2(C),
где M (message) - открытая информация (в литературе по защите информации часто
носит название "исходный текст");
C (cipher text) - полученный в результате зашифрования шифртекст (или криптограмма);
E (encryption) - функция зашифрования, выполняющая криптографические преобразования
над исходным текстом;
k1 (key) - параметр функции E, называемый ключом зашифрования;
M" - информация, полученная в результате расшифрования;
D (decryption) - функция расшифрования, выполняющая обратные зашифрованию криптографические
преобразования над шифртекстом;
k2 - ключ, с помощью которого выполняется расшифрование информации.
Понятие "ключ" в стандарте ГОСТ 28147-89 (алгоритм симметричного шифрования) определено следующим образом: "конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования, обеспечивающее выбор одного преобразования из совокупности всевозможных для данного алгоритма преобразований". Иными словами, ключ представляет собой уникальный элемент, с помощью которого можно изменять результаты работы алгоритма шифрования: один и тот же исходный текст при использовании различных ключей будет зашифрован по-разному.
Для того, чтобы результат расшифрования совпал с исходным сообщением (т. е. чтобы M" = M), необходимо одновременное выполнение двух условий. Во-первых, функция расшифрования D должна соответствовать функции зашифрования E. Во-вторых, ключ расшифрования k2 должен соответствовать ключу зашифрования k1.
Если для зашифрования использовался криптостойкий алгоритм шифрования, то при отсутствии правильного ключа k2 получить M" = M невозможно. Криптостойкость - основная характеристика алгоритмов шифрования и указывает прежде всего на степень сложности получения исходного текста из зашифрованного без ключа k2.
Алгоритмы шифрования можно разделить на две категории: симметричного и асимметричного шифрования. Для первых соотношение ключей зашифрования и расшифрования определяется как k1 = k2 = k (т. е. функции E и D используют один и тот же ключ шифрования). При асимметричном шифровании ключ зашифрования k1 вычисляется по ключу k2 таким образом, что обратное преобразование невозможно, например, по формуле k1 = ak2 mod p (a и p - параметры используемого алгоритма).
Симметричное шифрование
Свою историю алгоритмы симметричного шифрования ведут с древности: именно этим способом сокрытия информации пользовался римский император Гай Юлий Цезарь в I веке до н. э., а изобретенный им алгоритм известен как "криптосистема Цезаря".
В настоящее время наиболее известен алгоритм симметричного шифрования DES (Data Encryption Standard), разработанный в 1977 г. До недавнего времени он был "стандартом США", поскольку правительство этой страны рекомендовало применять его для реализации различных систем шифрования данных. Несмотря на то, что изначально DES планировалось использовать не более 10-15 лет, попытки его замены начались только в 1997 г.
Мы не будем рассматривать DES подробно (почти во всех книгах из списка дополнительных материалов есть его подробнейшее описание), а обратимся к более современным алгоритмам шифрования. Стоит только отметить, что основная причина изменения стандарта шифрования - его относительно слабая криптостойкость, причина которой в том, что длина ключа DES составляет всего 56 значащих бит. Известно, что любой криптостойкий алгоритм можно взломать, перебрав все возможные варианты ключей шифрования (так называемый метод грубой силы - brute force attack). Легко подсчитать, что кластер из 1 млн процессоров, каждый из которых вычисляет 1 млн ключей в секунду, проверит 256 вариантов ключей DES почти за 20 ч. А поскольку по нынешним меркам такие вычислительные мощности вполне реальны, ясно, что 56-бит ключ слишком короток и алгоритм DES необходимо заменить на более "сильный".
Сегодня все шире используются два современных криптостойких алгоритма шифрования: отечественный стандарт ГОСТ 28147-89 и новый криптостандарт США - AES (Advanced Encryption Standard).
Стандарт ГОСТ 28147-89
Алгоритм, определяемый ГОСТ 28147-89 (рис. 1), имеет длину ключа шифрования 256 бит. Он шифрует информацию блоками по 64 бит (такие алгоритмы называются блочными), которые затем разбиваются на два субблока по 32 бит (N1 и N2). Субблок N1 обрабатывается определенным образом, после чего его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, т. е. применяется логическая операция XOR - "исключающее или"), а затем субблоки меняются местами. Данное преобразование выполняется определенное число раз ("раундов"): 16 или 32 в зависимости от режима работы алгоритма. В каждом раунде выполняются две операции.
Первая - наложение ключа. Содержимое субблока N1 складывается по модулю 2 с 32-бит частью ключа Kx. Полный ключ шифрования представляется в виде конкатенации 32-бит подключей: K0, K1, K2, K3, K4, K5, K6, K7. В процессе шифрования используется один из этих подключей - в зависимости от номера раунда и режима работы алгоритма.
Вторая операция - табличная замена. После наложения ключа субблок N1 разбивается на 8 частей по 4 бит, значение каждой из которых заменяется в соответствии с таблицей замены для данной части субблока. Затем выполняется побитовый циклический сдвиг субблока влево на 11 бит.
Табличные замены (Substitution box - S-box) часто используются в современных алгоритмах шифрования, поэтому стоит пояснить, как организуется подобная операция. В таблицу записываются выходные значения блоков. Блок данных определенной размерности (в нашем случае - 4-бит) имеет свое числовое представление, которое определяет номер выходного значения. Например, если S-box имеет вид 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 и на вход пришел 4-бит блок "0100" (значение 4), то, согласно таблице, выходное значение будет равно 15, т. е. "1111" (0 а 4, 1 а 11, 2 а 2 ...).
Алгоритм, определяемый ГОСТ 28147-89, предусматривает четыре режима работы: простой замены, гаммирования, гаммирования с обратной связью и генерации имитоприставок. В них используется одно и то же описанное выше шифрующее преобразование, но, поскольку назначение режимов различно, осуществляется это преобразование в каждом из них по-разному.
В режиме простой замены для зашифрования каждого 64-бит блока информации выполняются 32 описанных выше раунда. При этом 32-бит подключи используются в следующей последовательности:
K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 и т. д. - в раундах с 1-го по 24-й;
K7, K6, K5, K4, K3, K2, K1, K0 - в раундах с 25-го по 32-й.
Расшифрование в данном режиме проводится точно так же, но с несколько другой последовательностью применения подключей:
K0, K1, K2, K3, K4, K5, K6, K7 - в раундах с 1-го по 8-й;
K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 и т. д. - в раундах с 9-го по 32-й.
Все блоки шифруются независимо друг от друга, т. е. результат зашифрования каждого блока зависит только от его содержимого (соответствующего блока исходного текста). При наличии нескольких одинаковых блоков исходного (открытого) текста соответствующие им блоки шифртекста тоже будут одинаковы, что дает дополнительную полезную информацию для пытающегося вскрыть шифр криптоаналитика. Поэтому данный режим применяется в основном для шифрования самих ключей шифрования (очень часто реализуются многоключевые схемы, в которых по ряду соображений ключи шифруются друг на друге). Для шифрования собственно информации предназначены два других режима работы - гаммирования и гаммирования с обратной связью.
В режиме гаммирования каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бит. Гамма шифра - это специальная последовательность, которая получается в результате определенных операций с регистрами N1 и N2 (см. рис. 1).
1. В регистры N1 и N2 записывается их начальное заполнение - 64-бит величина, называемая синхропосылкой.
2. Выполняется зашифрование содержимого регистров N1 и N2 (в данном случае - синхропосылки) в режиме простой замены.
3. Содержимое регистра N1 складывается по модулю (232 - 1) с константой C1 = 224 + 216 + 28 + 24, а результат сложения записывается в регистр N1.
4. Содержимое регистра N2 складывается по модулю 232 с константой C2 = 224 + 216 + 28 + 1, а результат сложения записывается в регистр N2.
5. Содержимое регистров N1 и N2 подается на выход в качестве 64-бит блока гаммы шифра (в данном случае N1 и N2 образуют первый блок гаммы).
Если необходим следующий блок гаммы (т. е. необходимо продолжить зашифрование или расшифрование), выполняется возврат к операции 2.
Для расшифрования гамма вырабатывается аналогичным образом, а затем к битам зашифрованного текста и гаммы снова применяется операция XOR. Поскольку эта операция обратима, в случае правильно выработанной гаммы получается исходный текст (таблица).
Зашифрование и расшифрование в режиме гаммирования
Для выработки нужной для расшифровки гаммы шифра у пользователя, расшифровывающего криптограмму, должен быть тот же ключ и то же значение синхропосылки, которые применялись при зашифровании информации. В противном случае получить исходный текст из зашифрованного не удастся.
В большинстве реализаций алгоритма ГОСТ 28147-89 синхропосылка не секретна, однако есть системы, где синхропосылка - такой же секретный элемент, как и ключ шифрования. Для таких систем эффективная длина ключа алгоритма (256 бит) увеличивается еще на 64 бит секретной синхропосылки, которую также можно рассматривать как ключевой элемент.
В режиме гаммирования с обратной связью для заполнения регистров N1 и N2, начиная со 2-го блока, используется не предыдущий блок гаммы, а результат зашифрования предыдущего блока открытого текста (рис. 2). Первый же блок в данном режиме генерируется полностью аналогично предыдущему.
 |
Рис. 2. Выработка гаммы шифра в режиме гаммирования с обратной связью. |
Рассматривая режим генерации имитоприставок , следует определить понятие предмета генерации. Имитоприставка - это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. При генерации имитоприставки выполняются следующие операции: первый 64-бит блок массива информации, для которого вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровывается в сокращенном режиме простой замены (выполняются первые 16 раундов из 32). Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.
Цикл повторяется до последнего блока информации. Получившееся в результате этих преобразований 64-бит содержимое регистров N1 и N2 или его часть и называется имитоприставкой. Размер имитоприставки выбирается, исходя из требуемой достоверности сообщений: при длине имитоприставки r бит вероятность, что изменение сообщения останется незамеченным, равна 2-r.Чаще всего используется 32-бит имитоприставка, т. е. половина содержимого регистров. Этого достаточно, поскольку, как любая контрольная сумма, имитоприставка предназначена прежде всего для защиты от случайных искажений информации. Для защиты же от преднамеренной модификации данных применяются другие криптографические методы - в первую очередь электронная цифровая подпись.
При обмене информацией имитоприставка служит своего рода дополнительным средством контроля. Она вычисляется для открытого текста при зашифровании какой-либо информации и посылается вместе с шифртекстом. После расшифрования вычисляется новое значение имитоприставки, которое сравнивается с присланной. Если значения не совпадают - значит, шифртекст был искажен при передаче или при расшифровании использовались неверные ключи. Особенно полезна имитоприставка для проверки правильности расшифрования ключевой информации при использовании многоключевых схем.
Алгоритм ГОСТ 28147-89 считается очень сильным алгоритмом - в настоящее время для его раскрытия не предложено более эффективных методов, чем упомянутый выше метод "грубой силы". Его высокая стойкость достигается в первую очередь за счет большой длины ключа - 256 бит. При использовании секретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет дополнительные биты. Кроме того, криптостойкость зависит от количества раундов преобразований, которых по ГОСТ 28147-89 должно быть 32 (полный эффект рассеивания входных данных достигается уже после 8 раундов).
Стандарт AES
В отличие от алгоритма ГОСТ 28147-89, который долгое время оставался секретным, американский стандарт шифрования AES, призванный заменить DES, выбирался на открытом конкурсе, где все заинтересованные организации и частные лица могли изучать и комментировать алгоритмы-претенденты.
Конкурс на замену DES был объявлен в 1997 г. Национальным институтом стандартов и технологий США (NIST - National Institute of Standards and Technology). На конкурс было представлено 15 алгоритмов-претендентов, разработанных как известными в области криптографии организациями (RSA Security, Counterpane и т. д.), так и частными лицами. Итоги конкурса были подведены в октябре 2000 г.: победителем был объявлен алгоритм Rijndael, разработанный двумя криптографами из Бельгии, Винсентом Риджменом (Vincent Rijmen) и Джоан Даймен (Joan Daemen).
Алгоритм Rijndael не похож на большинство известных алгоритмов симметричного шифрования, структура которых носит название "сеть Фейстеля" и аналогична российскому ГОСТ 28147-89. Особенность сети Фейстеля состоит в том, что входное значение разбивается на два и более субблоков, часть из которых в каждом раунде обрабатывается по определенному закону, после чего накладывается на необрабатываемые субблоки (см. рис. 1).
В отличие от отечественного стандарта шифрования, алгоритм Rijndael представляет блок данных в виде двухмерного байтового массива размером 4X4, 4X6 или 4X8 (допускается использование нескольких фиксированных размеров шифруемого блока информации). Все операции выполняются с отдельными байтами массива, а также с независимыми столбцами и строками.
Алгоритм Rijndael выполняет четыре преобразования: BS (ByteSub) - табличная замена каждого байта массива (рис. 3); SR (ShiftRow) - сдвиг строк массива (рис. 4). При этой операции первая строка остается без изменений, а остальные циклически побайтно сдвигаются влево на фиксированное число байт, зависящее от размера массива. Например, для массива размером 4X4 строки 2, 3 и 4 сдвигаются соответственно на 1, 2 и 3 байта. Далее идет MC (MixColumn) - операция над независимыми столбцами массива (рис. 5), когда каждый столбец по определенному правилу умножается на фиксированную матрицу c(x). И, наконец, AK (AddRoundKey) - добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим битом ключа раунда, который, в свою очередь, определенным образом вычисляется из ключа шифрования (рис. 6).
 |
| Рис. 3. Операция BS. |
 |
| Рис. 4. Операция SR. |
 |
| Рис. 5. Операция MC. |
Количество раундов шифрования (R) в алгоритме Rijndael переменное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров).
Расшифрование выполняется с помощью следующих обратных операций. Выполняется обращение таблицы и табличная замена на инверсной таблице (относительно применяемой при зашифровании). Обратная операция к SR - это циклический сдвиг строк вправо, а не влево. Обратная операция для MC - умножение по тем же правилам на другую матрицу d(x), удовлетворяющую условию: c(x) * d(x) = 1. Добавление ключа AK является обратным самому себе, поскольку в нем используется только операция XOR. Эти обратные операции применяются при расшифровании в последовательности, обратной той, что использовалась при зашифровании.
Rijndael стал новым стандартом шифрования данных благодаря целому ряду преимуществ перед другими алгоритмами. Прежде всего он обеспечивает высокую скорость шифрования на всех платформах: как при программной, так и при аппаратной реализации. Его отличают несравнимо лучшие возможности распараллеливания вычислений по сравнению с другими алгоритмами, представленными на конкурс. Кроме того, требования к ресурсам для его работы минимальны, что важно при его использовании в устройствах, обладающих ограниченными вычислительными возможностями.
Недостатком же алгоритма можно считать лишь свойственную ему нетрадиционную схему. Дело в том, что свойства алгоритмов, основанных на сети Фейстеля, хорошо исследованы, а Rijndael, в отличие от них, может содержать скрытые уязвимости, которые могут обнаружиться только по прошествии какого-то времени с момента начала его широкого распространения.
Асимметричное шифрование
Алгоритмы асимметричного шифрования, как уже отмечалось, используют два ключа: k1 - ключ зашифрования, или открытый, и k2 - ключ расшифрования, или секретный. Открытый ключ вычисляется из секретного: k1 = f(k2).
Асимметричные алгоритмы шифрования основаны на применении однонаправленных функций. Согласно определению, функция y = f(x) является однонаправленной, если: ее легко вычислить для всех возможных вариантов x и для большинства возможных значений y достаточно сложно вычислить такое значение x, при котором y = f(x).
Примером однонаправленной функции может служить умножение двух больших чисел: N = P*Q. Само по себе такое умножение - простая операция. Однако обратная функция (разложение N на два больших множителя), называемая факторизацией, по современным временным оценкам представляет собой достаточно сложную математическую задачу. Например, разложение на множители N размерностью 664 бит при P ? Q потребует выполнения примерно 1023 операций, а для обратного вычисления х для модульной экспоненты y = ax mod p при известных a, p и y (при такой же размерности a и p) нужно выполнить примерно 1026 операций. Последний из приведенных примеров носит название - "Проблема дискретного логарифма" (DLP - Discrete Logarithm Problem), и такого рода функции часто используются в алгоритмах асимметричного шифрования, а также в алгоритмах, используемых для создания электронной цифровой подписи.
Еще один важный класс функций, используемых в асимметричном шифровании, - однонаправленные функции с потайным ходом. Их определение гласит, что функция является однонаправленной с потайным ходом, если она является однонаправленной и существует возможность эффективного вычисления обратной функции x = f-1(y), т. е. если известен "потайной ход" (некое секретное число, в применении к алгоритмам асимметричного шифрования - значение секретного ключа).
Однонаправленные функции с потайным ходом используются в широко распространенном алгоритме асимметричного шифрования RSA.
Алгоритм RSA
Разработанный в 1978 г. тремя авторами (Rivest, Shamir, Adleman), он получил свое название по первым буквам фамилий разработчиков. Надежность алгоритма основывается на сложности факторизации больших чисел и вычисления дискретных логарифмов. Основной параметр алгоритма RSA - модуль системы N, по которому проводятся все вычисления в системе, а N = P*Q (P и Q - секретные случайные простые большие числа, обычно одинаковой размерности).
Секретный ключ k2 выбирается случайным образом и должен соответствовать следующим условиям:
1 где НОД - наибольший общий делитель, т. е. k1 должен быть взаимно простым со значением функции Эйлера F(N), причем последнее равно количеству положительных целых чисел в диапазоне от 1 до N, взаимно простых с N, и вычисляется как F(N) = (P - 1)*(Q - 1)
. Открытый ключ k1 вычисляется из соотношения (k2*k1) = 1 mod F(N)
, и
для этого используется обобщенный алгоритм Евклида (алгоритм вычисления наибольшего
общего делителя). Зашифрование блока данных M по алгоритму RSA выполняется следующим
образом: C = M[в степени k1]
mod N
. Заметим, что, поскольку в
реальной криптосистеме с использованием RSA число k1 весьма велико (в настоящее
время его размерность может доходить до 2048 бит), прямое вычисление M[в
степени k1]
нереально. Для его получения применяется комбинация многократного
возведения M в квадрат с перемножением результатов. Обращение данной функции при больших размерностях неосуществимо; иными словами, невозможно найти M по известным C, N и k1. Однако, имея секретный ключ k2, при помощи несложных преобразований можно вычислить M = Ck2 mod N. Очевидно, что, помимо собственно секретного ключа, необходимо обеспечивать секретность параметров P и Q. Если злоумышленник добудет их значения, то сможет вычислить и секретный ключ k2. Основной недостаток симметричного шифрования - необходимость передачи ключей "из рук в руки". Недостаток этот весьма серьезен, поскольку делает невозможным использование симметричного шифрования в системах с неограниченным числом участников. Однако в остальном симметричное шифрование имеет одни достоинства, которые хорошо видны на фоне серьезных недостатков шифрования асимметричного. Первый из них - низкая скорость выполнения операций зашифрования и расшифрования, обусловленная наличием ресурсоемких операций. Другой недостаток "теоретический" - математически криптостойкость алгоритмов асимметричного шифрования не доказана. Это связано прежде всего с задачей дискретного логарифма - пока не удалось доказать, что ее решение за приемлемое время невозможно. Излишние трудности создает и необходимость защиты открытых ключей от подмены - подменив открытый ключ легального пользователя, злоумышленник сможет обеспечить зашифрование важного сообщения на своем открытом ключе и впоследствии легко расшифровать его своим секретным ключом. Тем не менее эти недостатки не препятствуют широкому применению алгоритмов
асимметричного шифрования. Сегодня существуют криптосистемы, поддерживающие
сертификацию открытых ключей, а также сочетающие алгоритмы симметричного и асимметричного
шифрования. Но это уже тема для отдельной статьи. Тем читателям, которые непраздно интересуются шифрованием, автор рекомендует
расширить свой кругозор с помощью следующих книг. Полное описание алгоритмов шифрования можно найти в следующих документах: Решение задачи
определения ключа путем простого
перебора всех возможных вариантов, как
правило, является непрактичным, за
исключением использования очень
короткого ключа. Следовательно, если
криптоаналитик хочет иметь реальные
шансы на вскрытие шифра, он должен
отказаться от «лобовых» методов перебора
и применить другую стратегию. При
раскрытии многих схем шифрования может
применяться статистический анализ,
использующий частоту появления отдельных
символов или их комбинаций. Для усложнения
решения задачи вскрытия шифра с
использованием статистического анализа
К. Шеннон предложил две концепции
шифрования, получившие название смешения
(confusion
)
и диффузии
(diffusion
).
Смешение – это применение такой
подстановки, при которой взаимосвязь
между ключом и шифрованным текстом
становится как можно более сложной.
Применение данной концепции усложняет
применение статистического анализа,
сужающего область поиска ключа, и
дешифрование даже очень короткой
последовательности криптограммы требует
перебора большого количества ключей.
В свою очередь диффузия – это применение
таких преобразований, которые сглаживают
статистические различия между символами
и их комбинациями. В результате
использование криптоаналитиком
статистического анализа может привести
к положительному результату только при
перехвате достаточно большого отрезка
шифрованного текста. Реализация целей
провозглашаемых данными концепциями
достигается путем многократного
применения элементарных методов
шифрования таких, как метод подстановки,
перестановки и скремблирования. 10.4.1.
Метод
подстановки.
Простейшим и
имеющим наибольшую историю является
метод подстановки, суть которого
заключается в том, что символ исходного
текста заменяется другим, выбранным из
этого или другого алфавита по правилу,
задаваемому ключом шифрования.
Местоположение символа в тексте при
этом не изменяется. Одним из ранних
примеров использования метода постановки
является шифр
Цезаря
,
который использовался Гаем Юлием Цезарем
во время его Галльских походов. В нем
каждая буква открытого текста заменялась
другой, взятой из того же алфавита, но
циклически сдвинутого на определенное
количество символов. Применение данного
метода шифрования иллюстрирует пример,
представленный на рис.10.3, в котором
шифрующее преобразование основано на
использовании алфавита с циклическим
сдвигом на пять позиций. Рис. 10.3
,
а
) Исходный текст Криптограмма Рис. 10.3
,
б
) Очевидно, что
ключом шифра служит величина циклического
сдвига. При выборе другого ключа, чем
указано в примере, шифр будет изменяться. Другим примером
классической схемы, основанной на методе
подстановки, может служить система
шифрования, называемая квадратом
Полибиуса
.
Применительно к русскому алфавиту
данная схема может быть описана следующим
образом. Первоначально объединяются в
одну буквы Е, Ё; И, Й и Ъ, Ь, истинное
значение которых в дешифрованном тексте
легко восстанавливается из контекста.
Затем 30 символов алфавита размещаются
в таблицу размером 65,
пример заполнения которой представлен
на рис. 10.4. Рис. 10.4.
Шифрование любой
буквы открытого текста осуществляется
заданием ее адреса (т.е. номера строки
и столбца или наоборот) в приведенной
таблице. Так, например, слово ЦЕЗАРЬ
шифруется с помощью квадрата Полибиуса
как 52 21 23 11 41 61. Совершенно ясно, что
изменение кода может быть осуществлено
в результате перестановок букв в таблице.
Следует также заметить, что те, кто
посещал экскурсию по казематам
Петропавловской крепости, должно быть
памятны слова экскурсовода о том, как
заключенные перестукивались между
собой. Очевидно, что их способ общения
полностью подпадает под данный метод
шифрования. Примером
полиалфавитного шифра может служить
схема, основанная на т.н. прогрессивном
ключе Тритемиуса
.
Основой данного способа шифрования
служит таблица, представленная на рис.
10.5, строки которой представляют собой
циклически сдвинутые на одну позицию
копии исходного алфавита. Так, первая
строка имеет нулевой сдвиг, вторая
циклически сдвинута на одну позицию
влево, третья – на две позиции относительно
первой строки и т.д. Рис. 10.5.
Один из методов
шифрования с помощью подобной таблицы
состоит в использовании вместо первого
символа открытого текста символа из
первого циклического сдвига исходного
алфавита, стоящего под шифруемым
символом, второго символа открытого
текста – из строки, соответствующей
второму циклическому сдвигу и т.д. Пример
шифрования сообщения подобным образом
представлен ниже (рис. 10.6). Открытый текст Шифрованный
текст Рис. 10.6.
Известны несколько
интересных вариантов шифров, основанных
на прогрессивном ключе Тритемиуса. В
одном из них, называемом методом
ключа Вижинера
,
применяется ключевое слово, которое
указывает строки для шифрования и
расшифрования каждого последующего
символа открытого текста: первая буква
ключа указывает строку таблицы на рис.
10.5, с помощью которой шифруется первый
символ сообщения, вторая буква ключа
определяет строку таблицы, шифрующей
второй символ открытого текста и т.д.
Пусть в качестве ключа выбрано слово
«ТРОМБ», тогда сообщение, зашифрованное
с помощью ключа Вижинера, может быть
представлено следующим образом (рис.
10.7). Очевидно, что вскрытие ключа возможно
осуществить на основе статистического
анализа шифрограммы. Открытый текст Шифрованный
текст Рис. 10.7.
Разновидностью
этого метода является т.н. метод
автоматического
(открытого
)
ключа
Вижинера
,
в котором в качестве образующего
ключа
используется единственная буква или
слово. Этот ключ дает начальную строку
или строки для шифрования первого или
нескольких первых символов открытого
текста аналогично ранее рассмотренному
примеру. Затем в качестве ключа для
выбора шифрующей строки используются
символы открытого текста. В приведенном
ниже примере в качестве образующего
ключа использована буква «И» (рис. 10.8): Открытый текст Шифрованный
текст Рис. 10.8.
Как показывает
пример, выбор строк шифрования полностью
определяется содержанием открытого
текста, т.е. в процесс шифрования вводится
обратная связь по открытому тексту. Еще одной
разновидностью метода Вижинера служит
метод
автоматического
(шифрованного
)
ключа Вижинера
.
В нем, подобно шифрованию с открытым
ключом, также используется образующий
ключ и обратная связь. Отличие состоит
в том, что после шифрования с помощью
образующего ключа, каждый последующий
символ ключа в последовательности
берется не из открытого текста, а из
получаемой криптограммы. Ниже представлен
пример, поясняющий принцип применения
данного метода шифрования, в котором,
как и ранее, в качестве образующего
ключа использована буква «И» (рис. 10.9): Открытый текст Шифрованный
текст Рис. 10.9.
Как видно из
приведенного примера, хотя каждый
последующий символ ключа определяется
предшествующим ему символом криптограммы,
функционально он зависит от всех
предшествующих символов открытого
сообщения и образующего ключа.
Следовательно, наблюдается эффект
рассеивания статистических свойств
исходного текста, что затрудняет
применение статистического анализа
криптоаналитиком. Слабым звеном данного
метода является то, что шифрованный
текст содержит символы ключа. По нынешним
стандартам шифрование по методу Вижинера
не считается защищенным, основным же
вкладом является открытие того, что
неповторяющиеся ключевые последовательности
могут быть образованы с использованием
либо самих сообщений, либо функций от
сообщений. Вариантом реализации
подстановочной технологии, который в
достаточной степени реализует концепцию
смешения, служит следующий пример,
базирующийся на нелинейном преобразовании.
Поток информационных бит предварительно
разбивается на блоки длиной m
,
причем каждый блок представляется одним
из
различных символов. Затем множество из Рис. 10.10.
Не составляет
труда показать, что существует
Убедимся теперь,
что S
–блок,
представленный на рис. 10.10, действительно
осуществляет нелинейное преобразование,
для чего воспользуемся принципом
суперпозиций: преобразование
10.4.2.
Метод
перестановки.
При
перестановке
(или транспозиции
)
в соответствии с ключом изменяется
порядок следования символов открытого
текста, а значение символа при этом
сохраняется. Шифры перестановки являются
блочными, т. е. исходный текст предварительно
разбивается на блоки, в которых и
осуществляется заданная ключом
перестановка. Простейшим
вариантом реализации данного метода
шифрования может служить рассмотренный
ранее алгоритм перемежения, суть которого
заключается в разбиении потока
информационных символов на блоки длиной
Рис. 10.11.
Рассмотренный
вариант метода перестановки может быть
усложнен введением ключей
Рис. 10.12.
На
рис.
10.13 приведен
пример бинарной перестановки данных
(линейная операция), из которого видно,
что данные просто перемешиваются или
переставляются. Преобразование
осуществляется с помощью блока
перестановки (permutation
block
,
P
–блок).
Технология перестановки, реализуемая
этим блоком, имеет один основной
недостаток: она уязвима по отношению к
обманным сообщениям. Обманное сообщение
изображено на рис. 10.13 и заключается в
подаче на вход одной единственной
единицы при остальных нулях, что позволяет
обнаружить одну из внутренних связей.
Если криптоаналитику необходимо
осуществить анализ подобной схемы с
помощью атаки открытого текста, то он
отправит последовательность подобных
обманных сообщений, смещая при каждой
передаче единственную единицу на одну
позицию. В результате подобной атаки
будут установлены все связи входа и
выхода. Данный пример демонстрирует,
почему защищенность схемы не должна
зависеть от ее архитектуры. 10.4.3.
Метод
гаммирования
. П где коэффициенты
Поскольку число
различных состояний регистра конечно
(не более
Пример
10.4.1.
На
рис. 10.16, a
,
представлена реализация генератора на
основе регистра сдвига с линейной
обратной связью, формирующего двоичную
псевдослучайную последовательность
периода
На первый взгляд
можно предположить, что использование
ПСП большого периода может обеспечить
достаточно высокую защищенность. Так,
например, в сотовой системе мобильной
связи стандарта IS-95
в качестве скремблирующей используется
ПСП периода
Следовательно,
можно предполагать, что поскольку
последовательность не повторяется в
течение такого длительного периода, то
она может рассматриваться случайной и
обеспечивать совершенную секретность.
Однако существует коренное отличие
псевдослучайной последовательности
от действительно случайной
последовательности: псевдослучайная
последовательность формируется согласно
некоторому алгоритму. Таким образом,
если известен алгоритм, то будет известна
и сама последовательность. В результате
этой особенности схема шифрования,
использующая линейный регистр сдвига
с обратной связью, оказывается уязвимой
к атаке известного открытого текста. Для определения
отводов обратной связи, начального
состояния регистра и всей последовательности
криптоаналитику достаточно иметь всего
Пример
10.4.2.
Пусть
в качестве скремблирующей используется
ПСП периода
при начальном
состоянии регистра 0001. В результате
будет сформирована последовательность
.
Предположим, что криптоаналитику,
которому ничего неизвестно о структуре
обратной связи генератора ПСП, удалось
получить Тогда, сложив обе
последовательности по модулю 2,
криптоаналитик получает в свое
распоряжение фрагмент скремблирующей
последовательности, который показывает
состояние регистра сдвига в различные
моменты времени. Так, например, первые
четыре бита ключевой последовательности
отвечают состоянию регистра в некоторый
момент времени
где
Анализируя
состояния регистра сдвига в четыре
последовательные момента времени можно
составить следующую систему четырех
уравнений с четырьмя неизвестными: Решение данной
системы уравнений дает следующие
значения коэффициентов: Таким образом,
определив схему соединений обратной
связи линейного регистра и зная его
состояние в момент времени
Обобщив рассмотренный
пример на случай произвольного регистра
сдвига памяти n
,
исходное уравнение может быть представлено
в виде а система уравнений
записана в следующей матричной форме где
Можно показать,
что столбцы матрицы
Обращение матрицы
требует порядка
Чтобы затруднить
аналитику вычисление элементов ПСП при
сопоставлении фрагментов открытого
текста и шифровки, применяется обратная
связь по выходу и шифротексту. На рис.
10.17 поясняется принцип введения обратной
связи по шифротексту. Рис.
10.17.
Поточное
шифрование с обратной связью. Сначала передается
преамбула, в которой содержится информация
о параметрах генерируемой ПСП, в том
числе и о значении начальной фазы Z
00 .
По каждым n
сформированным символам шифрограммы
вычисляется и устанавливается в
генераторе новое значение фазы
Формально никто не передает никому ключ. В протоколе TLS клиент и сервер должны сгенерировать общий секрет (shared secret), набор из 48 байт. Потом клиент и сервер на основании общего секрета вычисляют ключи: ключ шифрования клиента и ключ шифрования сервера. Процедура вычисления ключей из общего секрета стандартная, и задана в описании протокола TLS. Сервер и клиент знают 2 ключа шифрования, одним шифруют, вторым дешифруют. А теперь самое интересное - как клиент и сервер вычисляют общий секрет. Это зависит от выбранного набора шифров: Про перехват. Как я выше описал, перехватывать сообщения здесь бесполезно, так как в первом случае его может расшифровать только сервер, а во втором используется хитрая криптографическая схема. Алгоритмы шифрования знает и сервер, и клиент. Ведь если клиент не знает, какой алгоритм шифрования, как он будет шифровать данные для отправки? В современной криптографии никто не использует закрытые алгоритмы. Открытые алгоритмы постоянно изучаются лучшими криптографами мира, ищутся уязвимости, и предлагаются решения для их обхода. В TLS мы условно можем сказать, что алгоритмы меняются, так как каждый раз генерируются другие ключи шифрования. А потом, если вы хотите использовать закрытый алгоритм, например для просмотра веб-страницы, каким образом этот алгоритм может быть закрытый, если ваш компьютер/устройство производит шифрование/дешифрование? Я упустил/упростил некоторые детали, что бы описать только основные идеи. Люди еще в древности научились защищать информацию методом её преобразования, чтобы посторонние лица не имели возможности её прочитать. Криптография возникла приблизительно тогда, когда люди только научились разговаривать. Более того, первое время письменность сама по себе представляла криптографическую систему, поскольку ею могли владеть только избранные люди, которым было доступно изучение криптографии. Криптографическим методом защиты информации называется ряд специальных методов кодирования, шифрования или иных преобразований информации, которые позволяют сделать её содержание недоступным для лиц, не обладающих ключом криптограммы. Криптография и шифрование являются самыми надёжными методами защиты, поскольку шифровальщик охраняет непосредственно саму информацию, а не доступ к ней. К примеру, прочтение зашифрованного файла будет невозможным, если даже злоумышленнику удастся похитить носитель. Реализация данного метода защиты осуществляется с помощью программ или пакетов программ. Для многих обывателей термин «криптография» означает что-то загадочное и таинственное. Однако в настоящее время различные виды шифрования можно встретить буквально везде - это и простые кодовые замки на дипломатах, и многоуровневые системы защиты секретных файлов. Люди сталкиваются с ней, когда вставляют в банкомат карточку, совершают денежные переводы, покупают через интернет товары, общаются по Skype, отправляют письма на электронную почту. Любые дела, связанные с информацией, так или иначе имеют отношение к криптографии. Но, несмотря на всё многообразие сфер применения, в настоящее время существует всего несколько способов шифрования. Все эти методы криптографии относятся к двум видам криптографических систем: симметричным (с секретным ключом) и ассиметричным (с открытым ключом). Достоинством любого современного криптографического метода можно назвать возможность обеспечения высокой гарантированной стойкости защиты, рассчитываемой и выражаемой в числовой форме (среднее число операций или время, необходимое для расшифровки секретной информации или подбора ключей). В настоящее время существуют следующие виды криптографии: Видео о криптографии и шифровании
Шифрование
В процессе шифрования в шифруемом сообщении выполняется криптографическое преобразование каждого символа. Среди всех известных способов шифрования можно выделить следующие пять основных групп: Кодирование сообщений
В данном типе криптопреобразований используется замена некоторых элементов данных определёнными кодами (к примеру, это могут быть сочетания цифр и/или букв). Рассечение информации
В этом методе защищаемая информация разделяется на отдельные массивы данных, при расшифровке лишь одного из которых будет невозможно раскрытие засекреченной информации. Сжатие сообщения
Способ сжатия предусматривает замену в защищаемых данных повторяющимися последовательностями символов на меньшие по размерам последовательности. Эффективность такого сжатия зависит от количества одинаковых последовательностей в защищаемом тексте. На протяжении всей многовековой истории криптографии и до настоящего времени это искусство было доступно далеко не каждому. Как правило, эти методы использовали люди, не выходящие за границы резиденций глав держав, посольств, органов разведки. И только несколько десятков лет назад начали происходить кардинальные изменения в этой области - информация стала самостоятельной коммерческой ценностью и превратилась в широко распространённый, почти обычный товар. Её производят, хранят, передают, продают, покупают, а, соответственно - воруют и подделывают. Именно поэтому сегодня существует большое количество учебных пособий и компьютерных программ, предназначенных для обычных пользователей, которым интересна криптография. Обучение некоторым простым видам шифрования может освоить даже школьник. Программа «Шифр Цезаря»
Данный метод шифрования также называют и шифром сдвига. В программном варианте шифр Цезаря представляет собой шифр подстановки с ключом, символы которого заменяются в тексте символами, находящимися на некоторых постоянных числах позиций слева или справа от него в алфавите. К примеру, шифр со сдвигом в правую сторону на три позиции: буква А заменяется на букву Г, Б - на Д и т. д. Следует учитывать, что буква Ё не используется в зашифровке и заменяется буквой Е. Программа: Расшифровка: А Вас увлекает криптография? Разбираетесь ли Вы в ней? Расскажите об этом вКакое шифрование лучше?
Дополнительные источники информации
символов перемешивается таким образом,
чтобы каждый символ заменялся другим
символом из этого множества. После
операции перемешивания символ вновь
превращается вm
–битовый
блок. Устройство, реализующее описанный
алгоритм при
,
представлено нарис.
10.10, где в
таблице задано правило перемешивания
символов множества из
элементов.
различных подстановок или связанных с
ними возможных моделей. В связи, с чем
при больших значенияхm
задача криптоаналитика становится в
вычислительном плане практически
невозможной. Например, при
число возможных подстановок определяется
как
,
т.е. представляет собой астрономическое
число. Очевидно, что при подобном значенииm
данное преобразование с помощью блока
подстановки
(substitution
block
,
S
–блок)
можно считать обладающим практической
секретностью. Однако его практическая
реализация вряд ли возможна, поскольку
предполагает существование
соединений.
является линейным, если.
Предположим, что
,
а
.
Тогда,
а,
откуда следует, чтоS
–блок
является нелинейным.
,
построчной записи его в матрицу памяти
размером
строк и
столбцов и считывании по столбцам.
Иллюстрацией данному алгоритму служит
пример с
на рис. 10.11, в ходе которого производится
запись фразыX
=«скоро
начнется экзаменационная
пора».
Тогда на выходе устройства перестановки
будет получена криптограмма вида
и
,
определяющих порядок записи строк и
считывания столбцов соответственно,
иллюстрацией чему служит таблица на
рис. 10.12. Результата преобразования
будет иметь следующий вид
опытки
приблизиться к совершенной секретности
демонстрируют многие современные
телекоммуникационные системы, использующие
операцию скремблирования. Подскремблированием
понимается процесс наложения на коды
символов открытого текста кодов случайной
последовательности чисел, которую
называют также гаммой (по названию буквы
греческого алфавита, используемой в
математических формулах для обозначения
случайного процесса). Гаммирование
относится к поточным методам шифрования,
когда следующие друг за другом символы
открытого текста последовательно
превращаются в символы шифрограммы,
что повышает скорость преобразования.
Так, например, поток информационных бит
поступает на один вход сумматора по
модулю 2, изображенного на рис. 10.14, тогда
как на второй – скремблирующая двоичная
последовательность
.
В идеале последовательность
должна быть случайной последовательностью
с равновероятными значениями нулей и
единиц. Тогда выходной шифрованный
поток
будет статистически независимым от
информационной последовательности
,
а значит, будет выполняться достаточное
условие совершенной секретности. В
действительности абсолютная случайность
не является необходимой, поскольку в
противном случае получатель не сможет
восстановить открытый текст. Действительно,
восстановление открытого текста на
приемной стороне должно производиться
по правилу
,
так что на приемной стороне должна
генерироваться точно такая же
скремблирующая последовательность и
с той же фазой. Однако вследствие
абсолютной случайности
данная процедура становится невозможной.
На
практике в качестве скремблирующих
широкое применение нашли псевдослучайные
последовательности (ПСП), которые могут
быть воспроизведены на приемной стороне.
В технологии поточного шифрования для
формирования ПСП обычно используют
генератор на основелинейного
регистра сдвига с обратной связью
(linear
feedback
shift
register
(LFSR)).
Типичная структура генератора ПСП,
представленная на рис. 10.15, включает
регистр сдвига, который состоит из
– ичных элементов задержки или разрядов,
имеющих
возможных состояний и хранящих некоторый
элемент поля
в течение тактового интервала, схема
обратной связи, включающей умножители
элементов (состояний), хранящихся в
разрядах, на константы
,
и сумматоров. Формирование ПСП описывается
рекуррентным соотношением вида
– фиксированные константы, принадлежащие
,
согласно которому каждый следующий
элемент последовательности вычисляется
на основанииn
предшествующих.
)
неизбежна ситуация, когда после некоторого
числа тактов состояние повторится в
виде одного из ранее случившихся. Однако,
стартуя с некоторой начальной загрузки,
т.е. фиксированного состояния, схема на
рис. 10.15 сформирует только единственную
последовательность, определяемую
упомянутой рекурсией. Следовательно,
повторение состояния регистра ведет к
повторению всех последующих генерируемых
символов, означающее, что любая ПСП
периодична. Более того, в случае нулевого
состояния регистра (наличия нулей во
всех разрядах) всегда будет формироваться
бесконечная вырожденная последовательность,
состоящая только из одних нулей. Очевидно,
что подобный случай абсолютно
бесперспективен, так что нулевое
состояние регистра должно быть исключено.
В результате остается не более
допустимых состояний регистра, что
ограничивает максимально возможный
период последовательности величиной,
не большей
.
.
Отметим, что в случае двоичной ПСП
умножение на единицу эквивалентно
простому соединению выхода разряда с
сумматором. Рис. 10.16,b
,
иллюстрирует следующие друг за другом
содержания регистра (состояния разрядов),
а также состояния выхода обратной связи
(точка ОС на схеме) при подаче тактовых
импульсов. Последовательность считывается
в виде последовательных состояний
крайнего п
равого
разряда. Считывание состояний других
разрядов приводит к копиям той же самой
последовательности, сдвинутой на один
или два такта.
в числе элементарных чипов. При чиповой
скорости 1.228810 6
симв/сек ее период составляет:
бит открытого текста и соответствующий
им шифрованный текст. Очевидно, что
величина 2n
значительно меньше периода ПСП, равного
.
Проиллюстрируем упомянутую уязвимость
на примере.
,
генерируемая с помощью рекурсии вида
бит
криптограммы и ее открытого эквивалента:
.
Если теперь сдвигать окно, выделяющее
четверку битов на одну позицию вправо,
то будут получены состояния регистра
сдвига в последовательные моменты
времени
.
Учитывая линейную структуру схемы
обратной связи, можно записать, что
символ ПСП, который вырабатывается
схемой обратной связи и подается на
вход первого разряда регистра, а
определяет отсутствие или наличиеi
–го
соединения между выходом разряда
регистра сдвига и сумматором, т.е. схему
обратной связи.
,
криптоаналитик способен воспроизвести
скремблирующую последовательность в
произвольный момент времени, а значит,
способен дешифровать перехваченную
криптограмму.
,
,
,
а
.
линейно независимы и, значит, существует
обратная матрица
.
Следовательно
.
операций, так что при
имеем
,
что для компьютера со скоростью работы
одна операция за 1мкс потребует 1 сек на
обращение матрицы. Очевидно, что слабость
регистра сдвига обусловлена линейностью
обратной связи.
.
Обратная связь делает метод гаммирования
чувствительным к искажениям криптограммы.
Так, из-за помех в канале связи могут
исказиться некоторые принятые символы,
что приведет к вычислению ошибочного
значения фазы ПСП и затруднит дальнейшую
расшифровку, но после полученияn
правильных символов шифрованного текста
система восстанавливается. В то же время
такое искажение можно объяснить попыткой
злоумышленника навязать ложные данные.Виды криптографии
Криптография для начинающих
Зашифровка:
