Доказательство при нулевом знании

adm  •  15 April, 2008

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


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

Доказывающий A и контролер B оба знают идентификатор I и открытый ключ (N, Е), но A кроме того знает еще, секретное число S=I**D MOD N, сформированное по секретному ключу D. Сначала A генерирует случайное число Х и вычисляет Y=X**E MOD N. Затем он отсылает [I, Y] к B.

После этого B генерирует и передает A случайное число V.

Затем A вычисляет и передает B число W=X*(Y**V) MOD N.

Контролер B проверяет принадлежность идентификатора I к A, контролируя тождество W**E=Y*(I**V) MOD P.
Случайный запрос обычно представлен вектором, координаты которого принимают значения 0 или 1, но он может быть любым вектором, координаты которого вычисляются по модулю числа Е. На этом можно подвести итоги краткого рассмотрения криптографических систем с открытым ключом. Их изобретение, похоже, лишь добавило головную боль криптографам по следующим веским причинам:

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

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

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

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

Нет невзламываемых шифров. Все системы шифрования просто делают взламывание шифровок или заведомо дороже содержащейся в сообщении информации, или затягивают расшифровывание на неприемлемо большой срок по времени. При разработке шифра устанавливают приемлемые цену или время взламывания и дальше уже не обращают внимания на очень богатых или терпеливых взломщиков. Необходимую сложность ключа в классических криптографических системах вычислить нетрудно, если знать технические возможности источника угрозы и плату за ошибку в оценке надежности шифра. Например, любопытствующий не переберет вручную и сотни ключей - устанет, а больших неприятностей от него ждать не приходится. Поэтому тысяча вариантов ключей достаточна, что эквивалентно информационной длине ключа 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}. В этом случае максимальное возможное число ключей, которые придется перебрать, чтобы гарантировано вскрыть шифр, равно 2**n, так как длина периода F, не превышает этой величины. Когда рассматриваем вскрытие шифра, то предполагаем, что существует программа универсальной ЭВМ, которая имитирует собой криптографическую машину, и некоторые начальные данные в виде секретного ключа, по которым программа может восстановить точный текст сообщения, подбирая все возможные ключи (Этот способ взлома шифров восходит к Шеннону и обычно называется "полным перебором ключей".) . Криптографы считают, что программа шифрования общедоступна и секрета не представляет, значит, сложность вскрытия шифра зависит лишь от количества секретных ключей. У такого определения сложности раскалывания шифра есть уязвимое место. Согласно известной теореме Гёделя проблема криптографической атаки на шифр не имеет универсального решения. А это означает: всегда есть надежда, что кому-нибудь придет в голову остроумная идея, позволяющая неожиданно просто прочесть нераскрываемые до этого шифры. Следовательно, несмотря на прогресс в создании устойчивых шифров, криптографы буквально ходят по краю пропасти, зажмурив глаза, а криптоаналитики пытаются их туда столкнуть. Нужно сказать, что практика криптологии и не отрицает этого. Действительно, ряд теоретических открытий дал пути для чтения некоторых типов шифров, раньше казавшихся нераскрываемыми. Тем не менее, больше похожа на реальную ситуацию другая схема, считающая, что теоретики если и смогут основательно упростить подбор ключа, то все равно останется так много переборов, что их выполнение за ограниченное время на современной технике будет невозможно. Иными словами, раскрытие очень длинного ключа методом полного перебора в реальных условиях невозможно, однако не исключена возможность создания принципиально нового метода результативной атаки на шифр.

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

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

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

Основное отличие систем с открытым ключом состоит в том, что в ней знание ключа шифрования недостаточно для расшифровывания и наоборот. Системы с открытым ключом всегда блочные.

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

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

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

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

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

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

Потоковые шифры широко используются в военных и других системах, близких к ним по назначению, для шифрования данных и преобразованных в цифровую форму речевых сигналов. До недавнего времени эти применения преобладали для данного метода шифрования. Это объясняется, в частности, относительной простотой конструирования и реализации генераторов хороших шифрующих последовательностей. Но главным фактором, конечно, было отсутствие размножения ошибок в потоковом шифре. Так как для передачи данных и речевых сообщений в стратегической связи используются каналы недостаточно высокого качества, то любая криптографическая система, увеличивающая и без того нередкие ошибки, неприменима. Кроме указанных приложений потоковые шифры используются и в системах шифрования каналов передачи данных, где их непрерывное действие препятствует эффективному криптоанализу. Единственным стандартным методом потокового шифрования является вариант, употребленный в стандарте шифрования данных 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 входных бит приходится п выходных комбинаций этих бит. Есть возможность случайным образом управлять этими комбинациями, что и приводит к особому виду шифрования. Его свойства следующие:

Декодирование этого шифра сложно, но может быть выполнено в реальном времени с мини- мальной задержкой.
Есть возможность создания шифров, устра- няющих ошибки.
Можно управлять размножением ошибок. На- пример, выбор выходных комбинаций бит Ti+T(i-1) и Ti+T(i-2) в коде со скоростью х при двух иска- жениях в трех последовательных битах приво- дит к тому, что ошибки начнут катастрофиче- ски размножаться.
Таким образом, существует возможность реализации в одном алгоритме целого набора шифров, резко различающихся по своим свойствам. К недостаткам таких шифров относятся увеличение объема сообщения с преобразованием его в шифровку и сложность схемы декодирования при больших значениях n. Однако эти недостатки не настолько серьезны, чтобы исключить возможность применения указанной схемы в связных коммуникациях или аппаратуре ЭВМ.

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

Типы систем Размножение ошибок Аутентификация Алгоритм Скорость
Потоковые нет нет нет типовых большая
Блочные есть нет DES и аналоги большая
С открытым ключом есть есть RSA, ЭльГамаля очень низкая
Сверточные есть есть Делаются на основе
блочных большая

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

Комментарии

Нет комментариев. Вы можете быть первым!

Оставить комментарий