последовательность, представляет натуральный ряд 1, 2, 3,...
Однако если его использовать для шифрования, то даже ребенок по
3-4 последовательным членам догадается, какое значение будет
следующим. Несомненно, что любую последовательность чисел можно
представить как функцию от натурального ряда F1, F2, F3,...
потому что аргумент можно рассматривать как простую нумерацию.
Сложностью или порядком функции F назовем минимально необходимое
число п последовательных членов ряда, которое необходимо, чтобы
реконструировать ряд целиком. При этом можно считать, что закон F
формирования ряда известен, а значения F, принадлежат множеству
{0,1}. В этом случае максимальное возможное число ключей, которые
придется перебрать, чтобы гарантировано вскрыть шифр, равно 2**n,
так как длина периода F, не превышает этой величины.
Когда рассматриваем вскрытие шифра, то предполагаем, что
существует программа универсальной ЭВМ, которая имитирует собой
криптографическую машину, и некоторые начальные данные в виде
секретного ключа, по которым программа может восстановить точный
текст сообщения, подбирая все возможные ключи (Этот способ взлома
шифров восходит к Шеннону и обычно называется "полным перебором
ключей".). Криптографы считают, что программа шифрования
общедоступна и секрета не представляет, значит, сложность
вскрытия шифра зависит лишь от количества секретных ключей. У
такого определения сложности раскалывания шифра есть уязвимое
место. Согласно известной теореме Гёделя проблема
криптографической атаки на шифр не имеет универсального решения.
А это означает: всегда есть надежда, что кому-нибудь придет в
голову остроумная идея, позволяющая неожиданно просто прочесть
нераскрываемые до этого шифры. Следовательно, несмотря на
прогресс в создании устойчивых шифров, криптографы буквально
ходят по краю пропасти, зажмурив глаза, а криптоаналитики
пытаются их туда столкнуть. Нужно сказать, что практика
криптологии и не отрицает этого. Действительно, ряд теоретических
открытий дал пути для чтения некоторых типов шифров, раньше
казавшихся нераскрываемыми. Тем не менее, больше похожа на
реальную ситуацию другая схема, считающая, что теоретики если и
смогут основательно упростить подбор ключа, то все равно
останется так много переборов, что их выполнение за ограниченное
время на современной технике будет невозможно. Иными словами,
раскрытие очень длинного ключа методом полного перебора в
реальных условиях невозможно, однако не исключена возможность
создания принципиально нового метода результативной атаки на
шифр.
Теперь подведем итоги. Известны два основных типа шифров,
комбинации которых образуют классические криптографические
системы. Главная идея, положенная в основу их конструирования,
состоит в комбинации функций, преобразующих исходные сообщения в
текст шифровки, то есть превращающих эти исходные сообщения с
помощью секретных ключей в нечитаемый вид. Но непосредственное
применение функций сразу ко всему сообщению реализуется очень
редко. Все практически применяемые криптографические методы
связаны с разбиением сообщения на большое число частей
фиксированного размера, каждая из которых шифруется отдельно,
если не независимо. Это существенно упрощает задачу шифрования,
так как сообщения обычно имеют различную длину. Поэтому можно
выделить четыре основных метода шифрования: потоковый, блочный, с
открытым ключом и сверточный. Их различия заключаются в
следующем:
* При потоковом шифровании каждый знак тек-
ста шифровки является функцией значения и
положения соответствующего знака открытого
текста. Знаками бывают биты, байты и редко
единицы текста покрупнее. Потоковое шифро-
вание представляет собой шифровку замены
знаков.
* При блочном шифровании исходный текст
сначала разбивается на равные по длине блоки
бит. К блокам применяется зависящая от клю-
ча функция шифрования для преобразования
их в блоки шифровки такой же длины. Обычно
блоки шифруются взбиванием.
* Основное отличие систем с открытым ключом
состоит в том, что в ней знание ключа шифро-
вания недостаточно для расшифровывания и
наоборот. Системы с открытым ключом всегда
блочные.
* Если в потоковом и блочном шифре функция
шифрования зависит только от ключа, то в
шифрах со сверткой она зависит как от ключа,
так и от одного или более предшествующих
символов или блоков текста шифровки.
Чтобы классифицировать эти методы шифрования данных
необходимо определить некоторое число характерных признаков,
которые можно использовать для установления различия между
шифрами. Принимается также, что каждый блок или знак сообщения
шифруется отдельно в определенном порядке. При этом условии
выделяются четыре характерных признака классификации
криптографических систем.
1. Нужно определить, над какими объектами ис-
ходного текста производятся криптографиче-
ские преобразования: над отдельными битами,
байтами или блоками. Например, в шифре
Энигмы операции производятся побайтно, в то
время как DES оперирует одновременно со
множеством бит,.называемым блоком. Свойст-
во системы использовать блоки бит назовем
блочностью.
2. Функции шифрования могут зависеть от знаков
сообщения. В системах, обладающих свойством
зависимости функции шифрования от знаков
сообщения, будет наблюдаться размножение
ошибок: если при передаче исказится хоть
один бит шифровки, то после расшифровыва-
ния текст будет содержать некоторое количест-
во ошибок. Зависимость функции шифрования
от знаков сообщения назовем сверточностыо.
3. Шифрование отдельных знаков сообщения
может зависеть от их положения в тексте. В
приведенном только что примере сверточного
шифрования, различные знаки сообщения шиф-
руются с учетом их положения. Поэтому потеря
при передаче любой части текста шифровки
приведет к неправильному расшифрованию
всех последующих частей сообщения. Незави-
симость знаков шифра от их положения в ис-
ходном тексте назовем транзитивностью.
4. Системы шифрования могут быть как симмет-
ричные, с одним ключом, так и асимметрич-
ными, с разными ключами для шифрования и
расшифровывания. Основное различие между
ними состоит в том, что в асимметричной сис-
теме знание одного ключа недостаточно для рас-
крытия соответствующего ему второго ключа.
Типы систем Блочность Сверточность Транзитивность Симметричность
Потоковые - - - +
Блочные + - + -
С открытым ключом + - + +
Сверточные + + + +
В данной таблице приведены свойства систем шифрования. Для
реализации потокового шифрования необходимо сконструировать
генератор ключевой последовательности, выход которого
используется для познакового шифрования открытого текста. К
преимуществам потоковых шифров относятся отсутствие размножения
ошибок, простая реализация и высокая скорость шифрования.
Основным же недостатком является необходимость передачи
информации синхронизации перед заголовком сообщения, которая
должна быть принята до расшифровывания любого сообщения. Это свя-
зано с тем, что если два различных сообщения шифруются на одном и
том же ключе, то для расшифровывания этих сообщений должна
использоваться одна и та же ключевая последовательность. Это
может создать угрозу криптографической стойкости системы, и
поэтому всегда необходимо применять дополнительный, случайно
выбираемый ключ, который передается в начале сообщения и
используется для модификации основного ключа шифрования.
Потоковые шифры широко используются в военных и других
системах, близких к ним по назначению, для шифрования данных и
преобразованных в цифровую форму речевых сигналов. До недавнего
времени эти применения преобладали для данного метода шифрования.
Это объясняется, в частности, относительной простотой конструиро-
вания и реализации генераторов хороших шифрующих
последовательностей. Но главным фактором, конечно, было
отсутствие размножения ошибок в потоковом шифре. Так как для
передачи данных и речевых сообщений в стратегической связи
используются каналы недостаточно высокого качества, то любая
криптографическая система, увеличивающая и без того нередкие
ошибки, неприменима. Кроме указанных приложений потоковые шифры
используются и в системах шифрования каналов передачи данных, где
их непрерывное действие препятствует эффективному криптоанализу.
Единственным стандартным методом потокового шифрования
является вариант, употребленный в стандарте шифрования данных
DES. Первый такой алгоритм был реализован фирмой Harris
Semiconductor в ее криптографическом процессоре на микросхеме
HS3447 Cipher 1. Хотя алгоритм остается секретным, известно, что
в этом кристалле применено потоковое шифрование. Другим примером
использования потокового шифрования можно назвать алгоритм В152
фирмы British Telecom, реализованный в приборах В-CRYPT этой
фирмы. Этот алгоритм также является секретным. В настоящее время
в России нашли широкое применение устройства потокового
шифрования STEN для защиты банковских коммуникаций SWIFT. За
рубежом можно купить массу всевозможных устройств потокового
шифрования от $1000 как Mesa 432 фирмы Western DataCom,
позволяющих поддерживать асинхронный протокол модемов V. 32 на
скоростях до 19.2 килобит/с, и до аппаратов Secure Х.25 фирмы
Cylink, поддерживающих синхронный протокол узлов Х.25 на скорости
64 килобит/с, но стоящих свыше $5000.
Главное свойство блочного шифрования состоит в том, что
каждый бит блока текста шифровки является функцией почти всех бит
соответствующего блока открытого текста, и никакие два блока
открытого текста не могут быть представлены одним и тем же блоком
текста шифровки. Основное преимущество простого блочного
шифрования состоит в том, что в хорошо сконструированной системе
небольшие изменения открытого текста или ключа вызывают большие и
непредсказуемые изменения в тексте шифра. Однако употребление
простейших блочных шифров связано с серьезными недостатками.
Первый из них состоит в том, что если ко всем блокам применить
один и тот же ключ, то даже при сравнительно большой длине блока,
как в DES, возможен криптоанализ "со словарем". Ясно, что блок
небольшого размера, как в стандарте DES, может даже повториться в
сообщении вследствие большой избыточности открытого текста. Это
может привести к тому, что идентичные блоки открытого текста в
сообщении будут представлены идентичными блоками текста шифровки,
что дает криптоаналитику шанс в угадывании текста и атаке на
ключ. Другой потенциальный недостаток этого шифра связан с
размножением ошибок внутри блока. Результатом изменения одного
бита в принятом блоке шифровки будет неправильное расшифровывание
всего блока. Вследствие отмеченных недостатков простейшие блочные
шифры не употребляются для шифрования длинных сообщений. Но в
финансовых учреждениях, где сообщения часто состоят всего из
одного или двух блоков, блочные шифры типа DES широко применяются
в простейшем варианте. Поскольку использование этого варианта
связано с необходимостью частой смены ключа шифрования, то
вероятность шифрования двух идентичных блоков открытого текста на
одном и том же ключе очень мала.
Возможно образование смешанных систем потокового и блочного
шифрования c использованием лучших свойств каждого из этих
шифров. В таких системах потоковое шифрование комбинируется с
перестановками бит в блоках. Открытый текст сначала шифруется,
как при обычном потоковом шифровании, затем полученный текст
шифровки разбивается на блоки фиксированного размера и в каждом
блоке дополнительно производится перестановка под управлением
ключа. В результате получается шифр, не размножающий ошибки, но
обладающий дополнительным свойством, которого нет у примитивного
потокового шифра замены на основе операции XOR, состоящим в том,
что перехватчик не знает, какому биту открытого текста
соответствует бит текста шифровки. Благодаря этому зашифрованное
сообщение становится гораздо более сложным для раскрытия.
Криптографическая система с открытым ключом, как уже видели,
представляет собой систему блочного шифрования, оперирующей с
блоками большой длины. Это обусловлено тем, что криптоаналитик,
знающий открытый ключ шифрования, мог бы предварительно вычислить
и составить таблицу соответствия блоков открытого текста и
шифровки. Если длина блоков мала, то число возможных блоков будет
не слишком большим и может быть составлена полная таблица, дающая
возможность моментального расшифрования любого шифрованного
сообщения с использованием известного открытого ключа. Ни один
алгоритм шифрования с открытым ключом не может быть применен для
каналов с большой скоростью. Это значит, что использование таких
систем для блочного шифрования ограничено лишь распределением
ключей, аутентификацией и формированием цифровой подписи.
Системы шифрования на основе свертки встречаются в различных
практических вариантах. Применение крийтографических систем
блочного шифрования в сочетании со сверткой дает ряд важных
преимуществ. Первое и самое значительное, это возможность
использования их для обнаружения манипуляций с сообщениями,
производимых активными перехватчиками. При этом используется факт
размножения ошибок, а также способность этих систем генерировать
код аутентификации сообщений. Другое преимущество состоит в том,
что такие шифры, в отличие от блочных, могут не требовать
начальной синхронизации. Это значит, что если какая-то часть
сообщения была пропущена при приеме, то оставшаяся часть его все
равно может быть расшифрована. Таким системам свойственны и
определенные недостатки. Основной из них - это размножение
ошибок. Один ошибочный бит при передаче вызовет блок ошибок в
расшифрованном тексте. При этом требование увеличения зависимости
одного знака текста шифровки от как можно более длинного его
предыдущего участка, повышает криптографическую стойкость, но
противоречит требованию надежности, связанному с размножением
ошибок. Другой недостаток состоит в том, что разработка и
реализация систем шифрования с обратной связью оказываются более
трудными, чем систем потокового шифрования. Впрочем, размножение
ошибок может быть и положительным свойством, если важно, чтобы
данные принимались точно и даже одна ошибка в них недопустима.
Так как сплошной поток ошибок может быть обнаружен несравненно
легче, чем одиночный сбой, то в данном случае размножение ошибок
уже не является недостатком шифра.
На этом можно было бы и закончить рассмотрение сверточных
шифров, однако стоит упомянуть особый вид сверточного шифрования,
представляющий большой практический интерес. В простейшем случае
имеем код со скоростью х. Это означает, что каждый бит сообщения
Ti на выходе схемы кодирования заменяется на два бита, например,
Ti+T(i-1) и Ti+T(i-1)+T(i-2). Декодирование этого кода довольно
сложно и осуществляется обычно методом динамического
программирования, при этом достаточно сохранять в памяти лишь 4
варианта возможных входных последовательностей. В процессе
декодирования сохраняются лишь те варианты, которые лучше
согласованы с входными данными. Для сверточных кодов со скоростью
k/n на k входных бит приходится п выходных комбинаций этих бит.
Есть возможность случайным образом управлять этими комбинациями,
что и приводит к особому виду шифрования. Его свойства следующие:
1. Декодирование этого шифра сложно, но может
быть выполнено в реальном времени с мини-
мальной задержкой.
2. Есть возможность создания шифров, устра-
няющих ошибки.
3. Можно управлять размножением ошибок. На-
пример, выбор выходных комбинаций бит Ti+T(i-1)
и Ti+T(i-2) в коде со скоростью х при двух иска-
жениях в трех последовательных битах приво-
дит к тому, что ошибки начнут катастрофиче-
ски размножаться.
Таким образом, существует возможность реализации в одном
алгоритме целого набора шифров, резко различающихся по своим
свойствам. К недостаткам таких шифров относятся увеличение объема
сообщения с преобразованием его в шифровку и сложность схемы
декодирования при больших значениях n. Однако эти недостатки не
настолько серьезны, чтобы исключить возможность применения
указанной схемы в связных коммуникациях или аппаратуре ЭВМ.
Первый вывод, который можно сделать из проведенного анализа,
состоит в том, что в большинстве практических криптографических
систем применяются алгоритмы или потокового шифрования, или
шифрования со сверткой. Большинство криптографических систем
потокового шифрования использует оригинальные алгоритмы для
коммерческого сектора или секретные правительственные алгоритмы.
Такое положение, очевидно, сохранится еще в ближайшие годы.
Возможно также, что большинство систем шифрования со сверткой
будет основано на применении алгоритмов блочного шифрования в
специальном варианте, в частности, наиболее известного алгоритма
блочного шифрования DES. О других методах шифрования можно
сказать, что несмотря на быстрый рост публикаций по
криптографическим системам с открытым ключом, они еще не
полностью выдержали испытание временем, хотя обойтись без них
сейчас уже невозможно. Поэтому для потенциальных пользователей
криптографии приходится выбирать между системами потокового
шифрования и системами шифрования со сверткой, основанными на
применении алгоритмов блочного шифрования типа DES. Однако
существуют определенные области применения, например, финансовые
операции, где вполне возможно использование методов простейшего
блочного шифрования. Выбор криптографического алгоритма в
значительной мере зависит от его назначения. Некоторые данные,
которыми можно руководствоваться при выборе типа
криптографических систем, приведены в таблице.
Типы систем Размножение ошибок Аутентификация Алгоритм Скорость
Потоковые нет нет нет типовых большая
Блочные есть нет DES и аналоги большая
С открытым ключом есть есть RSA, ЭльГамаля очень низкая
Сверточные есть есть Делаются на основе
блочных большая
К характеристикам, влияющим на выбор типа криптографической
системы, в первую очередь относится требуемая скорость
шифрования. Например, при очень низкой скорости вполне возможно
применение криптографической системы RSA. Системы блочного
шифрования в программном варианте тоже относятся к
низкоскоростным, но в аппаратном варианте, например, по алгоритму
DES, могут работать почти с любыми скоростями. Если требуются
очень высокие скорости, то лучшей может быть система потокового
шифрования с высоким быстродействием как в программном, так и в
аппаратном вариантах. Если же требуется аутентификация, то должны
применяться системы со сверткой текста шифровки или открытым клю-
чом. И, наконец, если имеющийся канал связи относится к каналам,
подверженным ошибкам, которые не должны размножаться
криптографической системой, то выбору системы потокового
шифрования нет альтернативы.
ПСЕВДОСЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЕЛ
Секретные ключи представляют собой основу криптографических
преобразований, для которых, следуя правилу Керкхофа, стойкость
хорошей шифровальной системы определяется лишь секретностью
ключа. Однако в практике создание, распределение и хранение
ключей редко были сложными технически, хотя и дорогими задачами.
Основная проблема классической криптографии долгое время
заключалась в трудности генерирования непредсказуемых двоичных
последовательностей большой длины с применением короткого
случайного ключа. Для ее решения широко используются генераторы
двоичных псевдослучайных последовательностей. Существенный
прогресс в разработке и анализе этих генераторов был достигнут
лишь к началу шестидесятых годов. Поэтому в данной главе
рассмотрены правила получения ключей и генерации на их основе
длинных псевдослучайных последовательностей, используемых
криптографическими системами для преобразования сообщения в
шифровку.
Получаемые программно из ключа, случайные или псевдослучайные
ряды чисел называются на жаргоне отечественных криптографов
гаммой, по названию у - буквы греческого алфавита, которой в
математических записях обозначаются случайные величины. Интересно
отметить, что в книге "Незнакомцы на мосту", написанной адвокатом
разведчика Абеля, приводится термин гамма, который специалисты
ЦРУ пометили комментарием - "музыкальное упражнение?", то есть в
пятидесятые годы они не знали его смысла. Получение и размножение
реализаций настоящих случайных рядов опасно, сложно и накладно.
Физическое моделирование случайности с помощью таких физических
явлений, как радиоактивное излучение, дробовой шум в электронной
лампе или туннельный пробой полупроводникового стабилитрона не
дают настоящих случайных процессов. Хотя известны случаи удачных
применений их в генерации ключей, например, в российском
криптографическом устройстве КРИПТОН. Поэтому вместо физических
процессов для генерации гаммы применяют программы для ЭВМ,
которые хотя и называются генераторами случайных чисел, но на
самом деле выдающие детерминированные числовые ряды, которые
только кажутся случайными по своим свойствам. От них требуется,
чтобы, даже зная закон формирования, но не зная ключа в виде
начальных условий, никто не смог бы отличить числовой ряд от
случайного, как будто он получен бросанием идеальных игральных
костей. Можно сформулировать три основных требования к
криптографически стойкому генератору псевдослучайной
последовательности или гаммы:
1. Период гаммы должен быть достаточно боль-
шим для шифрования сообщений различной
длины.
2. Гамма должна быть трудно предсказуемой. Это
значит, что если известны тип генератора и ку-
сок гаммы, то невозможно предсказать сле-
дующий за этим куском бит гаммы с вероятно-
стью выше х. Если криптоаналитику станет из-
вестна какая-то часть гаммы, он все же не
сможет определить биты, предшествующие ей
или следующие за ней.
3. Генерирование гаммы не должно быть связано
с большими техническими и организационны-
ми трудностями.
Самая важная характеристика генератора псевдослучайных чисел
- информационная длина периода, после которого числа либо начнут
просто повторяться, либо их можно будет предсказывать. Эта длина
фактически определяет возможное число ключей системы и зависит от
алгоритма получения псевдослучайных чисел. Требуемую длину
периода определяет степень секретности данных. Чем длиннее ключ,
тем труднее его подобрать. Однако не только длина ключа
гарантирует его стойкость к взлому. В том случае, если содержание
шифрованного сообщения жизненно важно для государства и им
заинтересуется национальная служба безопасности, то заранее нужно
быть готовым к неудаче в столь неравном состязании. Люди из
спецслужб легко найдут требуемый ключ своими специфическими
неджентльменскими методами, далекими от математики и
криптографии. Скорее всего, ключ им даст сам владелец на блюдечке
с голубой каемкой и будет этому искренне рад.
Вторая проблема состоит в следующем: на основании чего можно
сделать заключение, что гамма конкретного генератора является
непредсказуемой? Пока в мире нет еще универсальных и практически
проверяемых критериев, позволяющих утверждать это. Неизвестна и
общая теория криптоанализа, которая могла бы быть применена для
такого доказательства, за исключением все возрастающего
количества конкретных способов анализа, выработанных для
различных практических целей. Интуитивно случайность
воспринимается как непредсказуемость. Чтобы гамма считалось
случайной, как минимум необходимо, чтобы ее период был очень
большим, а различные комбинации бит определенной длины равномерно
распределялись по всей ее длине. Итак, второе требование к ряду
заключается в подтверждаемом статистически подобии его свойств
настоящей случайной выборки. Каждый порядок элементов гаммы
должен быть так же случаен, как и любой другой. Это требование
статистики можно толковать и как сложность закона формирования
ряда псевдослучайных чисел. Практически, если по достаточно
длинной реализации этот закон вскрыть не удается ни на
статистическом уровне, ни аналитически, то этим нужно
удовлетвориться. Чем длиннее требуемая длина ряда, тем жестче к
нему требования. Теперь подробнее расскажем, как вскрывались
скрытые закономерности в последовательностях чисел. С древнейших
времен люди наблюдали и изучали периодически повторяющиеся
процессы, как фазы Луны, движения планет, чередования времен
года, но не все такие цикличности выражены явно. Например,
солнечные пятна, наблюдаемые невооруженным глазом с начала нашей
эры и в телескопы с начала XVII века, дают пример скрытой
периодичности в II лет, впервые обнаруженной Генрихом Швабе лишь
в 1843 году. А вот среднегодовые температуры и изменение климата
Земли связаны с циклами в 19 лет. Работы Винера и Хинчина
поставили анализ периодичностей с головы на ноги. Ими предложено
оценивать спектр случайных колебаний значений элементов гаммы как
преобразование Фурье функции автокорреляции. При этом
шумоподобному равномерному спектру гаммы без скрытых
периодичностей соответствует автокорреляционная функция в виде
одиночного выброса в нуле, то есть так называемая дельта-функция.
Этот результат можно интерпретировать как непохожесть
последовательности на себя при любом ее сдвиге.
И, наконец, последнее третье требование связано с
возможностью практической реализации генератора в виде программы
или электронного устройства, быстродействием, необходимым для
применения в современных коммуникациях, а также удобством его
практического использования.
Простейшие алгоритмы генерации
Заслуга конструирования длинных псевдослучайных рядов с
хорошими статистическими свойствами полностью принадлежит
криптографии. Не следует думать, что они нужны лишь криптографам
- картирование Венеры стало возможным, когда длина периода
случайного ряда импульсов превысила 10**40. Фотографирование этой
планеты нельзя было сделать потому, что она всегда закрыта
плотным слоем облаков. Локация же ее с Земли затруднена обилием
помех и высокими требованиями к разрешению. Поэтому зондирование
выполнялось случайной последовательностью импульсов указанного
периода. После 300 зондирований, на что ушло более полгода, была
получена карта, где различимы объекты размером около километра, а
по высоте разрешение получено такое, какое достигнуто не везде на
Земле. Генераторы псевдослучайных чисел используются очень широко
в сотнях программных приложений от конструирования ядерных
реакторов и радиолокационных систем раннего обнаружения до
поисков нефти и многоканальной связи. Генерация псевдослучайных
последовательностей давно занимала математиков. Одним из первых
было предложение получать их как значения дробной части
Дата добавления: 2015-08-28; просмотров: 23 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |