Криптология

Криптология

Криптография и криптоанализ

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

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

 

Стойкость криптографического алгоритма

Криптология — «особая» область исследований. О достижениях этой науки все чаще сообщают не только научные, но и научно-популярные журналы и обычная пресса. За рубежом в последние годы наблюдается небывалый бум в области криптологии. Это связано с тем, что ее достижения стали применяться не только в узких ведомственных кругах, но и в жизни миллионов граждан.

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

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

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

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

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

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

у = F( z , х ) + х

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

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

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

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

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

Примерами могут криптоалгоритмы ГОСТ 28147-89, DES, FEAL.

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

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

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

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

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

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

В эту схему могут быть включены еще рандомизатор и решающее устройство.

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

Операции шифрования и расшифрования можно описать так:

  Y = Е(Х), X = D(Y)

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

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

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

Криптографические алгоритмы обычно строятся с использованием простых и быстро выполняемых операторов нескольких типов. Множество обратимых операторов, преобразующих текст длиной n бит в текст длинной n бит, являются элементами группы обратимых операторов по умножению (подстановок n-разрядных слов). Пусть f, g, h — обратимые операторы, то есть существуют f-1, g -1, h -1. Поэтому hgf — последовательное выполнение операторов f, g, h — тоже обратимый оператор (операторы выполняются справа налево) с обратным оператором к этому произведению f-1, g -1, h -1. Поэтому дешифратор выполняет те же операции, что и шифратор, но в обратном порядке, и каждый оператор расшифрования является обратным к соответствующему оператору шифрования. Некоторые операторы являются взаимно обратными, то есть выполнение подряд два раза некоторой операции над текстом дает исходный текст. В терминах теории групп это записывается уравнением f 2 = е, где е — единичный оператор. Такой оператор называется инволюцией. Можно сказать, что инволюция представляет собой корень из единицы. Примером инволюции является сложение по модулю 2 текста с ключом.

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

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

Существует еще одно важное применение одноключевой криптографии. Это осуществление вычислимого в одну сторону преобразования информации. Такое преобразование называется хэш-функцией. Особенность этого преобразования заключается в том, что прямое преобразование y=h(x) вычисляется легко, а обратное x=h-l(y) — трудно. Вообще говоря, обратное преобразование не является функцией, поэтому правильнее говорить о нахождении одного из прообразов для данного значения хэш-функции. В этом случае ключа, понимаемого как некоторая конфиденциальная информация, нет. Однако стойкие хэш-функции, для которых прообраз по данному значению функции тяжело найти, реализуются криптографическими методами и требуют для обоснования стойкости проведения криптографических исследований. Типичное применение хэш-функции — создание сжатого образа для исходного текста такого, что найти другой текст, обладающий таким же образом, вычислительно невозможно.

Задача создания стойкой хэш-функции возникает, например, при цифровой подписи текстов.

Одно из возможных самостоятельных применений хэш-функций — это опознавание пользователя с помощью цепочки вида х, h(x), h(h(x)) = h 2(x), h 3(x),..., h k(x).

Последнее значение цепочки h k(x) является контрольной информацией для проверяющего, а пользователь знает h k-l(x) и предъявляет эту информацию по требованию проверяющего. Проверяющий вычисляет h(h k-l(x)) и сравнивает с контрольной. В следующий раз этот пользователь должен предъявить h k-2(x), a контрольной информацией является h k-l(x). Это интересное решение, предложенное А. Конхеймом, однако имеет ряд недостатков.

Во-первых, пользователю надо хранить всю цепочку h i(x), что требует большого объема памяти, если число опознаваний может быть велико.

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

 

Стойкость криптосистемы

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

  •  стойкость ключа (сложность раскрытия ключа наилучшим известным алгоритмом);
  •  стойкость бесключевого чтения;
  •  имитостойкость (сложность навязывания ложной  информации наилучшим известным алгоритмом);
  •  вероятность навязывания ложной информации.

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

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

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

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

Понятие «наилучшего алгоритма» раскрытия ключа в определении стойкости неконструктивно и допускает субъективное толкование (для кого-то из разработчиков наилучшим алгоритмом может быть простой перебор ключей).

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

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

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

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

 

Необходимость криптоанализа

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

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

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

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

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

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

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

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

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

 

Методы криптоанализа классических шифров

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

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

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

Метод встречи посередине

В случае, если множество ключей криптоалгоритма замкнуто относительно композиции, то есть для любых ключей Zi  и Zj найдется ключ Zk такой, что результат шифрования любого текста последовательно на zi и zj равен шифрограмме этого же числа на Zk, то есть F(ZJ, F(ZI, x))= F(zk, x), то можно  воспользоваться этим свойством. Пусть нам нужно найти ключ Zk. Тогда для нахождения ключа zk, необходимо найти эквивалентную ему пару ключей zi, zj. Данный метод криптоанализа основан на «парадоксе дней рождения».

Известно, что если считать, что дни рождения распределены равномерно, то в группе из 24 человек с вероятностью 0,5 у двух человек дни рождения совпадут.

Этот же метод применим, если множество ключей содержит достаточно большое подмножество, являющееся полугруппой.

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

Этот алгоритм является вероятностным. Однако существуют и детерминированный аналог этого алгоритма «giant step — baby step» с такой же сложностью, предложенный американским математиком Д.Шенксом.

Метод Полларда

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

Дифференциальный метод криптоанализа

Дифференциальный метод криптоанализа (ДКА) был предложен Э.Бихамом и А.Шамиром в 1990 г. Дифференциальный криптоанализ —это попытка вскрытия секретного ключа блочных шифров, которые основаны на повторном применении криптографически слабой цифровой операции шифрования г раз. При анализе предполагается, что на каждом цикле используется свой под ключ шифрования. ДКА может использовать как выбранные, так и известные открытые тексты.

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

Предложенный впервые для анализа конкретного шифра, ДКА оказался применимым для анализа широкого класса марковских шифров. Марковским называется шифр, у которого уравнение шифрования на одном цикле удовлетворяет условию:

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

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

 

Линейный метод криптоанализа

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

Обычно при шифровании используется сложение по модулю 2 текста с ключом и операции рассеивания и перемешивания. Задача криптоаналитика — найти наилучшую линейную аппроксимацию (после всех циклов шифрования) выражения;

xi1+ .... + xir + yj1 + yjs=zk1 +....+ zkt

Пусть pL — вероятность того, что формула выполняется, при этом необходимо, чтобы величина |pL-l/2| была максимальна. В случае, если |pL-l/2| достаточно велика и криптоаналитику известно достаточное число пар открытых и соответствующих зашифрованных текстов, то сумма по модулю 2 бит ключа на соответствующей позиции в правой части формулы равна наиболее вероятному значению суммы по модулю 2 соответствующих бит открытых и зашифрованных текстов в левой части. В случае, если pL > 1/2, то сумма бит ключа в правой части формулы равна нулю, если сумма бит в левой части равна нулю больше, чем для половины пар зашифрованных текстов, и сумма бит ключа в правой части формулы равна единице, если сумма бит в левой части равна единице больше, чем для половины текстов. В случае, если pL< 1/2, то наоборот: сумма выключав правой части формулы равна нулю, если сумма бит в левой части равна единице больше, чем для половины пар открытых и зашифрованных текстовой сумма бит ключа в правой части формулы равна единице, если сумма бит в левой части равна нулю больше, чем для половины текстов. Для нахождения каждого бита собственно ключа теперь нужно решить систему линейных уравнений для известных линейных комбинаций этих бит, но эта процедура не представляет сложности, так как сложность решения системы линейных уравнений описывается полиномом не более третьей степени от длины ключа.

Требуемое для раскрытия ключа количество N пар открытых и зашифрованных текстов (блоков) оценивается выражением N >>pL-1/2|-2.

Для раскрытия ключа шифра DES этим методом необходимо 247 пар известных открытых и зашифрованных текстов. 

 

Инструменты криптоанализа

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

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

Подход «разделяй и властвуй» может быть использован и

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

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

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

Андельман и Риде для анализа шифров предложили использовать переход от исходного дискретного шифратора к «непрерывному» шифратору, который совпадаете исходным на вершинах n-мерного единичного куба, и далее искать непрерывный ключ с использованием техники поиска экстремумов непрерывных отображений. Заметим, что здесь кроется определенная сложность. Это вызвано тем, что все элементы кольца полиномов Жегалкина или кольца булевых функций с операциями И, ИЛИ, НЕ является идемпотентными. Пусть переменные принимают значения из некоторого непрерывного подмножества А вещественных чисел. Для численных значений вещественных аналогов булевых формул необходимо обеспечить x2=x, для любого рационального числа r. Таким образом, все вещественные числа А оказываются равными, то есть элементы А являются элементами факторгруппы R/Q. Нетрудно видеть, что ни в одной вычислительной модели с конечной разрядностью числа из А непредставимы, поэтому такой метод не работает (по крайней мере, для вещественных и, следовательно, для комплексных чисел).

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

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

 

Надежность цифровой подписи

С ростом популярности Internet довольно остро встал вопрос использования ее в деловых целях. Первой ласточкой стала деловая переписка, которая чаще ведется именно по Сети. Появились серверы, предлагающие услуги online-торговли самого разного рода — от покупки продуктов до недвижимости.

Но если вы получаете по e-mail письмо, подписанное «Саша Сидоров» или расплачиваетесь кредитной картой в online-магазине, вы не можете быть на сто процентов уверены, что письмо действительно послал ваш друг Саша, а магазин настоящий, а не очередная хакерская проделка, и номер вашей кредитки и ваш PIN-код не станут достоянием всей хакерской братии.

Поэтому, как только в Internet пришел бизнес, а с ним и необходимость всегда Точно определять, с кем имеешь дело, довольно широко стали использоваться технологии, позволяющие аутентифицировать субъектов Сети, как пользователей, так и серверы. Одна из них — электронная подпись (ЭП), стандарт которой (DSS) был выработан в 1991 году.

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

Как работает электронная подпись?

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

Контрольная сумма

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

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

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

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

Шифрование с открытым ключом

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

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

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

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

Кстати, в структуру ЭП (по международному стандарту CCITT X.509) входит не только публичный ключ отправителя, но и его имя, серийный номер ЭП (номер определяет уполномоченная фирма, выдавшая ему набор из приватного и публичного ключа), название этой уполномоченной фирмы и даже ее собственная ЭП.

Как все выглядит хорошо и заманчиво. Кажется, установил на компьютере Digital ID — и дело в шляпе. АН нет. Специалисты говорят, что достоверность собственно ЭП целиком и полностью определяется качеством шифрующей системы (казалось бы). «Казалось бы» потому, что на самом деле с ЭП все не так просто, и число уязвимых точек ЭП, базирующейся на шифровании с открытым ключом, настолько велико, что целесообразность использования подобного метода вызывает большие сомнения.

Мечтания продвинутых адептов виртуальной реальности, узревших в Internet следующее за московским метро чудо света, неизлечимая булемия (а по-русски выражаясь — жор) заокеанских чудищ, порождающих одного за другим монстров интегрированных сред и телепортационных механизмов, космический размах шпиономании спецслужб прочно внедрили в общественное мировое сознание мысль о неизбежности прихода в наискорейшем будущем электронных денег, базирующихся на шифровании с открытым ключом. Эксклюзивное право на него принадлежит исконно американской фирме RSA Data Security (причем вне зависимости от метода шифрования).

Уже сегодня даже отечественные правления банков, которые, как известно, просто-таки с клептоматической страстью оснащают свои банки самыми современными технологиями и даже во сне видят, как все эти средства — от автоматических телекамер по периметру до нелегально вы везенных суперЭВМ, способных управлять системой ПВО небольшой европейской страны, — обогатят гуляющий вокруг банков народ и поднимут российскую экономику на невиданные доселе высоты, — уже сегодня эти правления вовсю внедряют системы прямой телекоммуникационной связи «клиент-банк» и даже ощущают тягу профинансировать разработки опирающихся на Internet систем «home banking» для пенсионеров, инвалидов и просто очень занятых людей, испытывающих сложности с выходом из дома или занятых на непрерывном конвейерном производстве.

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

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

1. Защита надежна и безопасна, если не предпринимаются попытки ее взлома;

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

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

  •  Конверт с электронной подписью может состоять из  данных, контрольной суммы CRS, зашифрованной приватным ключом РК1, и соответствующего открытого ключа OK1. Злоумышленник перехватывает конверт, отрезает ЭП = PK1*CRS1 + OK1, меняет данные, генерирует пару ключей РК2ОК2 и вновь собирает конверт. Получатель проверяет ЭП, убеждается, что ОК2 дешифрует PK2*CRS2 так, что CRS2 соответствует «данным2», и что подпись настоящая и данные оригинальны. Для того чтобы описанный подлог был невозможен, ключ OK1 не должен находиться в конверте, а должен быть доставлен получателю отдельно, причем по каналу секретной связи. Таким образом исключаются перехват и подмена. Однако о какой секретной связи мы говорим, если речь идет об ОК-шифровании? Таким образом, «открытый ключ» вовсе не является открытым, он должен быть передан приватным образом, но в этом случае мы получаем перерождение ОК-шифрования в классическое симметричное с приватной передачей секретного ключа.
  •  Сборщик информации генерирует пару ключей РК1 — OK1, рассылает открытый ключ OK1 всем партнерам, которые должны прислать ему секретную (друг от друга и всех посторонних) информацию. Злоумышленник заранее генерирует свою пару ключей РК2 — ОК2, перехватывает одну из передач OK1, подменяет его на ОК2, а затем перехватывает данные, зашифрованные ключом ОК2, дешифрует их своим РК2, читает, затем вновь шифрует «правильным» OK1 и отправляет дальше — сборщику информации, который ни о чем не заподозрит. Для того чтобы это злодейство было исключено, все копии OK1 должны быть розданы самым приватным образом, то есть, опять открытый ключ на поверку оказывается секретным, опять задача решается симметричным методом, а хитроумный наворот с ОК-шифрованием на руку лишь тому, кто задумал злодейство.
  •  Система «клиент-банк»: каждый клиент Kiимеет на руках индивидуальный приватный ключ Рi, в банке хранится таблица соответствующих открытых ключей Ki — OKi. Клиент Ki посылает в банк платежное поручение, банк удостоверяется в подписи клиента по таблице и производит соответствующую денежную операцию. Злоумышленник генерирует свою пару ключей РКХ — ОКХ, подменяет открытый ключ клиента К2 в банке с ОК2 на ОКХ (не знаем, как насчет швейцарских банков, а в российских такая подмена не составляет труда, так как самое большее, что, как правило, используют наши банки для защиты от НСД своих компьютеров — это милицию в бронежилетах и варианты парольного ограничения доступа). Среднестатистический российский банкир просто не обращает на подобную ерунду внимания и отправляет свою платежку. Банк получает платежку злоумышленника, идентифицирует его как клиента 2 и переводит все денежки клиента туда, куда направил их злоумышленник.

Создание защищенной системы регистрации

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

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

Протоколы защищенной телекоммуникационной связи SSL

Широко разрекламированная и уже собирающая колоссальные дивиденды защищенная телекоммуникационная связь с протоколами SSL 2,3 предусматривает обмен абонентов открытыми ключами, шифрование данных двойными — своим секретным и чужим открытым — ключами, еще массу всяких наворотов, убеждающих пользователя в бесконечной секретности соединения, однако как выяснить, кто, собственно, с кем соединился?

В конечном итоге выясняется, что пользователь должен таки предварительно сходить в тот или иной идентификационный центр и получить там уникальный сертификат, на основании которого и строится весь последующий секретный диалог с открытыми ключами. Причем так или иначе в этом диалоге оказывается задействованным и идентификационный центр, выдавший пользователю сертификат (абонент А посылает абоненту В открытый ключ ОКА; В посылает А свой сертификационный ключ OKA*PKBI*SKB, зашифрованный сначала приватным PKBI, а потом открытым ОКА; А дешифрует SKB до состояния PKBI*SKB; затем связывается с идентификационным центром I; центр высылает А открытый ключ OKI; А отправляет в центр ключи ОКА1, OKI*PKAI*SKA, OKI*PKBI*SKB; I, имеющий парные ключи PKI, ОЮЦ, OKBI, дешифрует сертификаты -SKA, SKB и сверяет их с базовой информацией, после чего высылает абоненту А ответ, зашифрованный ключами ОКА1*РК1, относительно личности В; и А идентифицирует В; потом В так же идентифицирует А; наконец они переходят к собственно обмену данными). Опять ОК-шифрование реально базируется на секретном симметричном ключе (сертификате) и надежность всей схемы зависит в первую очередь от того, насколько надежно охраняются сертификаты пользователей, а во вторую — не вклинится ли кто-нибудь в диалог абонентов уже после того, как идентификация состоялась, как это описано в двух первых примерах.

Резюмируя все вышеизложенное, можно утверждать, что «реальные» электронные деньги и электронные подписи с публичным ключом требуют безусловно более надежную концепцию и методы ОК-шифрования, что фактически исключено ввиду четырех главных позиций:

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

Дополнительные сложности в аутентификации создают контрольные суммы. Разработчики в азарте творчества часто преувеличивают свои достижения до абсурда, утверждая, например, что контроль целостности произвольных данных произвольного объема может быть обеспечен числом из 15 или 20 знаков, что противоречит теории информации так же, как вечный двигатель — законам термодинамики. На самом деле для обеспечения стопроцентной гарантии целостности данных объем «довешиваемой» информации должен составлять, в зависимости от шумового коэффициента исходного материала, от доли процента до ста процентов объема исходных данных. Для текста ЭП гарантирующая целостность исходного документа составляет не менее 10% его объема, для архивного файла — не менее 70%. (Вы можете легко проверить, выполняется ли это условие в используемых вами подписях.) Заметим, что, в отличие от ЭП, шифрование (с обратной связью) дает стопроцентную гарантию целостности данных без увеличения их объема вне зависимости от природы этих данных.

Электронная подпись — вовсе не подпись в собственном смысле этого слова, а композиция сложных информационно-математических и технических манипуляций. При всем своем желании органический субъект ни в каком будущем не сможет что-либо «черкануть» в виртуальном электронном пространстве, состоящем сплошь из единичек и ноликов. Воспитанная на бумажном делопроизводстве, человеческая психология срабатывает рефлексом Павлова на слово «подпись» и фантазирует свое, канцелярское, невзирая на отсутствие привычных чернил или штемпелей.

Представление, что поставленная на документе электронная подпись может служить для решения юридических споров и установления какой бы то ни было истины, в корне ошибочно: действие электронной подписи распространяется на психологическую сферу, но никак не на юридическую. Сертификаты ФАПСИ дают право фирмам-разработчикам продавать электронную подпись, но не имеют никакого отношения к правовым аспектам ее использования. В случае, если вы заявите, что никогда не посылали документ, заверенный «вашей» электронной подписью, никакой суд не докажет обратное, и вам даже не потребуется наличие свидетелей или алиби. И это правильно, потому что существует слишком много возможностей подделки или похищения подписи, о чем уже говорилось выше. Кроме того, никто, в конечном итоге, не возьмет на себя ответственность за надежность и безопасность программной системы, обеспечивающей электронную подпись, даже если в ней не видно явных ошибок.

Сертификаты ФАПСИ, как уже упоминалось, являются лишь относительными гарантиями, основное их назначение — регулировка рынка.

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

Еще в 1994 г. были обнаружены закладки, в частности против систем, построенных на основе пакета PGP (Pretty Good Privacy), при помощи которых были подделаны электронные, документы. Между тем PGP построен на наиболее распространенном во всем мире (и в том числе в России) методе шифрования RSA, считающимся стандартом в США (опять же для неправительственных и «Outside USA» сфер). Что после этого можно сказать об отечественных подписях, опирающихся на тот же метод RSA либо на наши ГОСТ Р 34.10-94 и ГОСТ Р 34.11-94, которые практически не используются в международных масштабах и соответственно не подвергаются массированным атакам со стороны разного рода хакеров...

 

Криптография для начинающих

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

ГДЕ АББА

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

В результате проведенного преобразования получится шифрограмма:

 ЁЖЗ ГДДГ

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

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

CDB EFFE

Рациональнее использованный в последнем случае ключ записать в виде таблицы: 

 А Б В Г Д Е

 Е F А С D В

При шифровании буквы могут быть заменены числами (в простейшем случае порядковыми номерами букв в алфавите). Тогда наша шифровка будет выглядеть так:

4-5-6-1-2-2-1

Замена символов открытого текста может происходить на специальные символы, например на «пляшущих человечков», как в рассказе К.Дойля.

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

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

Ниже приведен фрагмент многоалфавитного ключа замены.

А

Б

В

Г

Д

Е

18

7

5

19

21

2

12

4

90

35

83

15

48

14

22

10

99

32

С помощью многоалфавитного шифра сообщение «ГДЕ АББА» можно зашифровать несколькими способами:

19-83-32-48-4-7-12 

10-99-15-12-4-14-12 ;

и так далее...

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

Рассмотрим еще один многоалфавитный шифр замены, который был описан в 1585 году французским дипломатом Блезом де Виженером. Шифрование производится с помощью, так называемой таблицы Виженера. Каждая строка в этой таблице соответствует одному шифру простой замены (типа шифра Цезаря). При шифровании сообщения его записывают в строку, а под ним помещают ключ. В случае, если ключ Оказывается короче сообщения, то ключ циклически повторяют. Шифровку получают, находя символ в матрице букв шифрограммы. Символ шифрограммы находится на пересечении столбца с буквой открытого текста и строки с соответствующей буквой ключа.

Предположим, что нужно зашифровать сообщение «ГДЕ АББА». В качестве ключа выберем слово «ДЕВА». В результате получим:

сообщение

Г

Д

Е

А

Б

Б

А

ключ

Д

Е

В

А

Д

Е

В

шифровка

Я

Я

Г

А

Э

Ъ

Ю

В результате преобразований получится шифровка: ЯЯГ АЗЪЮ

Рассмотрим примеры шифрования сообщения методом перестановки.

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

Для пояснения идеи возьмем квадрат (матрицу) 8x8, будем записывать текст последовательно по строкам сверху вниз, а считывать по столбцам последовательно слева направо.

Предположим, что требуется зашифровать сообщение:

НА ПЕРВОМ КУРСЕ ТЯЖЕЛО УЧИТЬСЯ ТОЛЬКО ПЕРВЫЕ ЧЕТЫРЕ ГОДА

ДЕКАНАТ

Н А _ П Е Р В О

М_КУРСЕ_

Т Я Ж Е Л 0 _ У

Ч И Т Ь С Я_т

0 Л Ь К 0 _ П Е 

Р В Ы Е _ Ч Е Т 

Ы Р Е _ Г О Д А 

_ Д Е К А Н А Т

В таблице символом «_» обозначен пробел.

В.результате преобразований получится шифровка:

НМТЧОРЫ_А_ЯИЛВРД_КЖТЬЫЕЕПУЕЬКЕ_КЕРЛСО_ГАРСОЯ_ ЧОНВЕ_ПЕДАО_УТЕТАТ

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

Методы замены и перестановки по отдельности не обеспечивают необходимую криптостойкость. Поэтому их используют совместно, а также в сочетании с аддитивным методом.

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

 

Криптографическая система с открытым ключом

Рассматриваемый метод закрытия информации разработали в 1976 г. американцы Уитфилд Диффи и Мартин Хеллман.

Опишем пример использования такой системы.

Пусть абонент А (например, банкир) и абонент В (например, вкладчик) решили установить между собой секретную передачу шифрованной информации с открытым ключом.

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

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

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

Действия

Абонент А(банкир)                  Абонент В(вкладчик)

1. Выбор двух простых чисел р и q

Р =7;                                              q = 13

 р = 11;                                          q = 23

2. Вычисление произведения r = р? q

r= 7? 13 '= 91                               r = 11? 23 = 253

3. Расчет функции Эйлера j (r) = r-p-q+1

j (r) = 72                                       j (r) = 220

4. Выбор случайного числа s, взаимно простого с j (r) из интервала  0 < s < j (r) >

s = 5                                               s = 31

5. Расчет секретного ключа t из соотношения s? t = f (modj (r))

5? t = 1(mod(72)) t =29                 31? t = 1(mod(220)) t =71

6. Публикация открытых ключей s, r

s = 5, r = 91                                  s = 31, r =253

Использованная в таблице запись а = b (mod(g)) означает, что при целочисленном делении числа а на число g остаток равен b.

Функция Эйлера — арифметическая функция j (r), значение которой равно количеству положительных чисел, не превосходящих r и взаимно простых с r.

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

Абонент А шифрует число 2 открытым (опубликованным) ключом абонента В. Для шифрования число 2 возводится в степень s = 31, то есть:

m = 231 = 2147483648

Затем находят остаток от деления числа m на величину r = 253, в,результате которого получается число 167. Напомним, что числа s и r являются открытым ключом абонента В.

В линию передается число 167, которое является шифром исходного числа 2.

Получив шифрограмму, абонент В использует свой секретный ключ t = 71. Для дешифрации он возводит полученное число 167 в степень 71 и находит остаток отделения на число 253. Математически это записывается так:

16771 ? 2(mod(253))

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

Предположим, что абонент В решил ответить абоненту А и направить ему букву, зашифрованную числом 3.

Абонент В использует открытый (опубликованный) ключ абонента A (s = 5, r = 91) и выполняет шифрующее преобразование числа 3. Математически это записывается так:

35 ? 61(mod(91))

В линию отправляется число 61. Получив это число, абонент А восстанавливает исходный текст с помощью своего секретного ключа t =29:

6129 ? 3(mod(91))

В результате дешифрации на приемной стороне получено число 3, которое отправил абонент В.

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

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

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

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

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

Рассмотрим пример.

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

415 ? 6(mod(91))

В результате шифрования получено число 6.

Дальше вкладчик повторно шифрует это сообщение своим секретным ключом 71:

 671 ? 94(mod(253)) 

Шифрограмма 94 отправляется банкиру.

Банкир, получив секретное сообщение, использует вначале открытый ключ вкладчика:

9431 ? 6(mod(253))

Затем банкир использует свой секретный ключ:

629 ? 41(mod(91))

В результате абонент А (банкир) получает сообщение, состоящее из числа 41.

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



Опубликовал admin
13 Июн, Воскресенье 2004г.



Программирование для чайников.