Нет невзламываемых шифров. Все системы шифрования просто делают взламывание шифровок или заведомо дороже содержащейся в сообщении информации, или затягивают расшифровывание на неприемлемо большой срок по времени. При разработке шифра устанавливают приемлемые цену или время взламывания и дальше уже не обращают внимания на очень богатых или терпеливых взломщиков. Необходимую сложность ключа в классических криптографических системах вычислить нетрудно, если знать технические возможности источника угрозы и плату за ошибку в оценке надежности шифра. Например, любопытствующий не переберет вручную и сотни ключей - устанет, а больших неприятностей от него ждать не приходится. Поэтому тысяча вариантов ключей достаточна, что эквивалентно информационной длине ключа 10 бит или ключевому слову из 3-5 букв.
Если же информация представляется стратегической и устареет не быстрее чем за 5 лет, а источник угрозы - крупная фирма, которая может нанять криптоаналитиков и получить доступ к сверхбыстродействующей ЭВМ, то и ключ нужен посложнее. Можно допустить, что они обеспечат проверку миллиона ключей в секунду. Тогда, если оставить противнику один шанс из миллиона, то число ключей должно быть записано с 22 десятичными разрядами, что примерно соответствует 70 битам или ключевому слову из 30-35 букв. Таким образом, число необходимых ключей можно записать в виде формулы:
N=[время жизни шифра]/[скорость подбора ключей]/[шанс взлома]
Время жизни шифра вряд ли целесообразно задавать больше 25 лет. В Британии секретнейшие правительственные решения по истечении этого срока публикуют для историков. А вот скорость подбора ключей всегда вызывает споры. Например, публикация американского стандарта шифрования DES вызвала у ряда криптографов призывы его бойкотировать, так как они утверждали, что за 20 миллионов долларов можно создать ЭВМ, перебирающую миллион ключей в секунду и раскалывающую шифр скорее чем за сутки. Правда, представители национального бюро стандартов возражали, что на создание такой сверхбыстродействующей ЭВМ уйдет 5 лет, а это время - приемлемый срок жизни стандарта и шифров. Последняя величина в формуле, выражающая риск от взлома шифра за указанный срок, весьма индивидуальна и обычно имеет величину от одной тысячной до одной миллионной в зависимости от области его применения.
Трудность вскрытия шифра опирается на понятие алгебраической сложности. При определенных условиях, а именно при совершенстве типа шифра и современном состоянии криптографии, можно утверждать, что сложность зависит лишь от случайной последовательности, которая представима как ряд чисел. Самая простая последовательность чисел - повторение одного и того же числа, как 0, 0, 0,... - фактически оставляет исходный текст открытыми. Более сложную, но не менее естественную последовательность, представляет натуральный ряд 1, 2, 3,... Однако если его использовать для шифрования, то даже ребенок по 3-4 последовательным членам догадается, какое значение будет следующим. Несомненно, что любую последовательность чисел можно представить как функцию от натурального ряда F1, F2, F3,... потому что аргумент можно рассматривать как простую нумерацию. Сложностью или порядком функции F назовем минимально необходимое число п последовательных членов ряда, которое необходимо, чтобы реконструировать ряд целиком. При этом можно считать, что закон F формирования ряда известен, а значения F, принадлежат множеству {0,1}. В этом случае максимальное возможное число ключей, которые придется перебрать, чтобы гарантировано вскрыть шифр, равно 2n, так как длина периода 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, могут работать почти с любыми скоростями. Если требуются очень высокие скорости, то лучшей может быть система потокового шифрования с высоким быстродействием как в программном, так и в аппаратном вариантах. Если же требуется аутентификация, то должны применяться системы со сверткой текста шифровки или открытым ключом. И, наконец, если имеющийся канал связи относится к каналам, подверженным ошибкам, которые не должны размножаться криптографической системой, то выбору системы потокового шифрования нет альтернативы.
Жельников Владимиp. Кpиптогpафия от папиpуса до компьютеpа
Ниже привожу весьма практичный пример хорошего поточного шифра от
Брюса Шнайера, автора «Прикладной криптографии» Президента «Каунтерпейн системс» http://www.counterpane.com
Систему «Пасьянс» я придумал, чтобы агенты на местах могли выходить на связь, не полагаясь на электронику и не имея при себе компрометирующих инструментов. Агент может оказаться в ситуации, где у него просто не будет доступа к компьютеру, или пострадать, если при нем обнаружат средства секретной связи. А колода карт… что может быть безобиднее?
Стойкость «Пасьянса» основана на случайности перетасованной колоды. Манипулируя ею, коммуникант способен создать цепочку «случайных» букв, которые потом комбинируются с сообщением. Разумеется, «Пасьянс» можно воспроизвести на компьютере, но создан он для использования вручную.
Хоть «Пасьянс» и низкотехнологичен, надежность в него заложена высокотехнологическая. Я создавал его в расчете на самого богатого военного противника, обладающего самыми большими компьютерами и самыми толковыми криптоаналитиками. Конечно, не исключено, что кто-то найдет способ взломать «Пасьянс», но алгоритм несомненно лучше, чем все другие способы шифрования с помощью карандаша и бумаги, которые я видел.
Правда, это не быстро. Чтобы зашифровать или расшифровать более или менее длинное сообщение, нужен вечер. В книге «Кан о кодах» Дэвид Кан описывает подлинный метод шифрования с помощью карандаша и бумаги, которым пользовался советский шпион. На шифровку с помощью советского алгоритма и с помощью «Пасьянса» требуется примерно равное время.
ШИФРОВАНИЕ С ПОМОЩЬЮ «ПАСЬЯНСА»
«Пасьянс» – поточный шифр с обратной связью по выходу. Иногда это называется генератор гаммы. Основная идея в том, что «Пасьянс» генерирует шифрующий поток из чисел от 1 до 26. Для шифрования сгенерируйте столько же букв ключевого потока, сколько содержит открытый текст. Потом суммируйте их по модулю 26, одну за другой, с буквами открытого текста. Для расшифрования сгенерируйте тот же ключевой поток и вычитайте по модулю 26 из шифртекста, чтобы получить открытый текст.
Для примера зашифруем простое сообщение, «DO NOT USE PC»:
1. Разбейте сообщение открытого текста на группы по пять букв. (Ничего такого магического в цифре 5 нет, это просто традиция.) Последнюю группу дополните буквами «X». Тогда если сообщение «DO NOT USE PC», то открытый текст:
DONOT USEPC
2. С помощью «Пасьянса» сгенерируйте десять букв шифрующего потока. (Подробности дальше.) Предположим, это:
KDWUP ONOWT
3. Переведите открытый текст из букв в числа: А = 1, В = 2, и так далее:
4 15 14 15 20 21 19 5 16 3
4. Точно так же переведите в числа ключевой поток:
11 4 23 21 16 15 14 15 23 20
5. Сложите числа открытого текста с числами ключевого потока по модулю 26. (То есть если сумма превышает 26, вычтите из результата 26.) Например, 1 + 1 = 2, 26 + 1 = 27, а 27 – 26 = 1, так что 26 + 1 = 1.
15 19 11 10 10 10 7 20 13 23
6. Переведите числа обратно в буквы.
OSKJJ JGTMW
Когда натренируетесь, сможете складывать буквы в уме, не переводя их в числа. Тут надо просто привыкнуть. Легко запомнить А + А = В; труднее, что Т + Q = К.
РАСШИФРОВКА С ПОМОЩЬЮ «ПАСЬЯНСА»
Основная идея состоит в том, что получатель генерирует тот же ключевой поток и потом вычитает буквы ключевого потока из букв шифртекста.
1. Возьмите шифртекст и разбейте его на группы из пяти букв. (Он уже должен быть в таком виде.)
OSKJJ JGTMW
2. С помощью «Пасьянса» сгенерируйте десять букв ключевого потока. Если получатель использует тот же ключ, что и отправитель, буквы должны получиться те же:
KDWUP ONOWT
3. Переведите шифртекст из букв в цифры:
15 19 11 10 10 10 7 20 13 23
4. Переведите ключевой поток аналогичным образом:
11 4 23 21 16 15 14 15 23 20
5. Вычтите числа ключевого потока из чисел шифртекста по модулю 26. Например, 22 – 1 = 20, 1 – 22 = 5. (Это легко. Если первое число меньше второго, перед вычитанием прибавьте к нему 26. Тогда 1 – 22 =? станет 27 – 22 = 5.)
4 15 14 15 20 21 19 5 16 3
6. Переведите числа обратно в буквы.
DONOT USEPC
Расшифрование происходит так же, как зашифрование, только вы вычитаете ключевой поток из шифртекста.
ГЕНЕРАЦИЯ БУКВ КЛЮЧЕВОГО ПОТОКА
Это суть «Пасьянса». Приведенное выше описание шифрования и расшифрования работает для любого поточного шифра с обратной связью по выходу. Дальше объясняется, как работает «Пасьянс».
«Пасьянс» генерирует ключевой поток с помощью колоды карт. Колоду в 54 листа (помните про джокеров) можно представить как 54-элементную перестановку. Существует 54!, или 2, 31 х 1071 возможных раскладов колоды. Что еще лучше, в колоде 52 листа (без джокеров), а в латинском алфавите – 26 букв. Мимо такого совпадения грех пройти.
Для «Пасьянса» в колоде должен быть полный набор из 52 карт и двух джокеров. Джокеры должны как-то отличаться. (Обычно так оно и есть. В колоде, на которую я смотрю, когда пишу, на джокерах звезды: на одном большая, на другом маленькая.) Пусть один джокер будет А, другой Б. Обычно графический элемент у джокеров одинаковый, отличается только размер. Назовите больший джокер «Б» от слова «больше». Если вам так проще, напишите на джокерах «А» и «Б», но помните, что, если вас поймают, вам придется объяснять это тайной полиции.
Для инициализации колоды возьмите ее в руку, лицом вверх. Потом разложите карты в начальной последовательности, которая представляет собой ключ. (Про ключ я объясню позже, но это не то же, что ключевой поток.) Теперь мы готовы сгенерировать цепочку букв ключевого потока.
Вот «Пасьянс»:
1. Найдите джокер А. Переложите его на одну карту вниз. (То есть поменяйте местами с картой, которая лежит сразу под ним.) Если джокер – нижняя карта в колоде, положите его под верхнюю карту.
2. Найдите джокер Б. Переложите его на две карты вниз. Если джокер – нижняя карта в колоде, положите его под две верхние карты. Если предпоследняя, положите сразу под верхнюю. (В общем, представьте, что колода – это петля… ну, поняли.)
Важно выполнять эти два шага в указанной последовательности. Есть соблазн облениться и перекладывать джокеры в том порядке, в каком они вам попадутся. Это не страшно, если только они не лежат близко.
Так что если колода до шага 1 выглядела так:
3 А Б 8 9
то после шага 2 она будет выглядеть:
3 А 8 Б 9
Если есть сомнения, помните, что джокер А надо перекладывать первым. И будьте внимательны, когда джокеры внизу колоды.
3. Подснимите колоду. То есть поменяйте карты над первым джокером с картами под вторым джокером. Если колода выглядела так:
2 4 6 Б 4 8 7 1 А 3 9
то после подснимания она будет выглядеть:
3 9 Б 4 8 7 1 А 2 4 6
«Первый» и «второй» джокер относятся к джокерам, которые лежат соответственно ближе и дальше от верха колоды. На этом шаге не важно, какой из них А, какой Б.
Помните, что джокеры и карты между ними не перекладываются; местами меняются нижняя и верхняя стопка. Если в одной из стопок карт нет (джокеры лежат рядом, либо один из них сверху или снизу), считайте эту стопку пустой и перемещайте ее, как полную.
4. Подснимите по счету. Взгляните на нижнюю карту. Превратите ее в число от 1 до 53. (Последовательность мастей, как в бридже: трефы, бубны, червы, пики. Если карта - трефа, ее значение соответствует достоинству. Если это бубна, то достоинству плюс 13. Если черва, достоинству плюс 26. Если пика, достоинству плюс 39. Один из джокеров – 53.) Отсчитайте от верха колоды это число. (Я обычно считаю от 1 до 13 требуемое число раз: это проще, чем последовательно досчитывать до больших чисел.) Выньте карты ниже той, до которой вы досчитали, оставив последнюю внизу. Если колода выглядела так:
7… карты… 4 5… карты… 8 9
и девятой картой была 4, после подснимания она будет выглядеть так:
5… карты… 8 7… карты… 4 9
Последняя карта остается на месте, чтобы сделать шаг обратимым. Это важно для математического анализа его безопасности.
5. Найдите карту-результат. Посмотрите на верхнюю карту. Переведите ее в число от 1 до 53, как описано выше. Отсчитайте это число карт. (Считайте верхнюю карту номером первым.) Запишите карту после той, до которой вы досчитали, на листке бумаги. Если это джокер, ничего не записывайте и начните снова с шага 1.) Это первая карта-результат. Заметьте, что этот шаг не изменяет состояние колоды.
6. Переведите карту в число. Как и прежде, пользуйтесь последовательностью мастей, принятой в бридже, в порядке возрастания.
Вот и весь «Пасьянс». С его помощью вы можете получить столько чисел ключевого потока, сколько потребуется.
Знаю, что в разных странах колоды немного разные. В целом не важно, какую последовательность мастей использовать или как переводить карты в цифры. Важно лишь, чтобы отправитель и получатель сговорились о правилах. Если вы не будете выполнять все операции одинаково, вы не сможете общаться.
НАСТРОЙКА КОЛОДЫ
«Пасьянс» надежен в той мере, в какой надежен его ключ. То есть простейший способ взломать «Пасьянс» – выяснить, каким ключом пользуются коммуниканты. Если у вас нет хорошего ключа, все остальное бесполезно. Вот несколько советов по поводу обмена ключом.
1. Перетасуйте колоду. Случайный ключ – самый лучший. Один из коммуникантов может случайным образом перетасовать колоду и разложить вторую точно таким же способом. Одна должна быть у получателя, вторая – у отправителя. Большинство людей плохо тасуют карты, поэтому перетасуйте колоду не меньше десяти раз. Лучше взять колоду, которой уже играли, чем только что распечатанную. Обязательно нужно иметь запасную колоду, разложенную в том же порядке, иначе, сделав ошибку, вы уже не сможете прочесть сообщение. И помните, что ключ уязвим: тайная полиция может найти колоду и переписать ее порядок.
2. Используйте бриджевые комбинации. Расклады бриджа, которые печатают в газетах или книгах по карточным играм, соответствую 95-битному ключу. Если коммуниканты договорятся, как, исходя из этого, раскладывать колоды и куда помещать джокеры (может быть, после первых двух карт, упомянутых в разборе), это сработает. Учтите: тайная полиция может найти колонку с бриджем в газете, которой вы решили пользоваться, и списать порядок карт. Можно сговориться на чем-нибудь вроде «используй колонку бриджа из газеты в твоем родном городе на день зашифровки сообщения» или похожем. Можно использовать список ключевых слов для поиска на веб-сайте «Нью-Йорк тайме». Поиск даст вам какую-нибудь статью; возьмите бриджевую колонку из номера, в котором она напечатана. Если ключевые слова будут найдены или перехвачены, их сочтут паролем.
3. Используйте пароль для расклада колоды. В этом методе для первоначального расклада используется алгоритм «Пасьянса». И отправитель, и получатель знают пароль. (Например, «SECRET KEY».) Начните с колоды, разложенной по порядку, самая младшая сверху, последовательность мастей, как в бридже. Проделайте операцию «Пасьянс», но вместо шага 5 выполните еще одно подснимание по счету, основываясь на первой букве пароля (в данном примере 19). (Не забудьте положить верхние карты сразу над нижней картой колоды, как и раньше.) Выполните это по разу на каждую букву. Еще две буквы определят положение джокеров. Помните, впрочем, что уровень случайности на букву в стандартном английском примерно 1, 4 бита. Для безопасности нужен пароль по меньшей мере из 80 букв; я рекомендую не меньше 120. (Уж простите, но более короткий ключ не дает надежного уровня безопасности.)
ПРИМЕРЫ
Вот несколько примеров, чтобы потренироваться с «Пасьянсом»:
Пример 1: Начните с неразложенной колоды: Т¦ – К¦, Т¦ – K¦, Т¦ – К¦, Т¦ – К¦, джокер А, джокер Б (можете считать это последовательностью 1—52, А. Б). Тогда первые десять результатов:
4 49 10 (53) 24 8 51 44 6 33
53, естественно, пропускается. Я оставил это число только для ясности. Если открытый текст:
ААААА ААААА
то шифртекст:
EXKYI ZSGEH
Пример 2: Используя метод настройки 3 ключ «FOO», получаем первые 15 результатов:
8 19 7 25 20 (53) 9 8 22 32 43 5 26 17 (53) 38 48
Если открытый текст состоит из одних «А», то шифртекст будет:
ITHZU JIWGR FARMW
Пример 3: Используя метод настройки 3 и ключ «CRYPTONOMICON», сообщение «SOLITAIRE» зашифровывается как:
KIRAK SFJAN
Разумеется, надо использовать более длинный ключ. Эти примеры приведены только для тренировки. На моем веб-сайте есть еще примеры, и вы можете создать свои, используя программу на языке PERL, приведенную в этой книге.
СОБЛЮДЕНИЕ ТАЙНЫ КАК УСЛОВИЕ БЕЗОПАСНОСТИ
«Пасьянс» рассчитан на то, что враг не сможет взломать его, даже зная алгоритм. Я исходил из допущения, что «Криптономикон» станет бестселлером и купить его можно будет повсюду. Полагаю, АНБ и все остальные изучат алгоритм. Я исхожу из того, что тайным будет только ключ.
Вот почему так важно сохранять ключ в тайне. Если у вас в безопасном месте хранится колода карт, нельзя исключать, что враг заподозрит вас в использовании «Пасьянса». Если у вас в тайнике лежит бриджевая колонка из газеты, это несомненно вызовет интерес. Если известно, что некая группа использует этот алгоритм, тайная полиция постарается следить за бриджевыми колонками. «Пасьянс» надежен, даже если враг знает, что вы им пользуетесь, и простая колода карт – все же не такая улика, как шифровальная программа в вашем ноутбуке, однако этот алгоритм не заменяет житейской смекалки.
СОВЕТЫ ПО ИСПОЛЬЗОВАНИЮ
Первое правило любого поточного шифра с обратной связью по выходу: нельзя использовать один ключ для зашифровки двух разных сообщений. Повторяйте за мной: НИКОГДА НЕ ИСПОЛЬЗУЙ ОДИН КЛЮЧ ДЛЯ ЗАШИФРОВКИ ДВУХ РАЗНЫХ СООБЩЕНИЙ. В противном случае вы разрушаете всю безопасность системы. Вот почему: если у вас есть два потока шифртекста А + К и В + К и вы вычтете один из другого, то получите (А + К) – (В + К)= А + К – В – К = А – В. Это комбинация двух открытых текстов, которую очень легко взломать. Поверьте на слово: вы, может быть, и не восстановите А и В из А – В, но профессиональный криптоаналитик с этим справится. Так что это жизненно важно: никогда не пользоваться одним ключом для зашифровки двух разных сообщений.
Пишите короткие сообщения. Алгоритм рассчитан на сообщения небольшой длины – примерно до двух тысяч знаков. Если вы хотите зашифровать роман в сто тысяч слов, воспользуйтесь компьютерным алгоритмом. Используйте в своих сообщениях стенографию, аббревиатуры, сленг. Не треплитесь попусту.
Для большей безопасности постарайтесь делать все в уме. Если тайная полиция ломает вашу дверь, просто спокойно перетасуйте колоду. (Не бросайте ее в воздух, вы удивитесь, насколько при этом сохраняется порядок карт.) Не забудьте перетасовать контрольную колоду, если она у вас есть.
Скачать программу "Преферанс" для поточного шифрования можно здесь: http://ymilij.ru/uyoba/preferans-beta-1.htm
Источник: Жельников Владимиp. Кpиптогpафия от папиpуса до компьютеpа.
Рейтинг публикации:
|
