Анализ стойкости криптографических систем с использованием искусственного интеллекта

ГЛАВА 1. АНАЛИЗ ПРЕДМЕТНОЙ ОБЛАСТИ Последние десятилетие характеризуется резким увеличением числа открытых работ по всем вопросам криптологии, а криптоанализ становится одной из наиболее активно развивающихся областей исследований. Многие криптосистемы, стойкость которых не вызывала особых сомнений, оказались успешно раскрытыми. При этом разработан большой арсенал математических методов, представляющих прямой интерес для криптоаналитика. В начале 1970-х гг. была известна только классическая одноключевая криптография,

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

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

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

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

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

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

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

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

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

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

ИС можно привести следующие - алфавит Z33 32 буквы русского алфавита исключая ё и пробел - алфавит Z256 символы, входящие в стандартные коды ASCII и КОИ-8 - двоичный алфавит Z2 0,1 - восьмеричный или шестнадцатеричный алфавит. Шифрование процесс преобразования исходного текста, который носит также название открытого текста, в шифрованный текст. Расшифрование процесс, обратный шифрованию.

На основе ключа шифрованный текст преобразуется в исходный. Криптографическая система представляет собой семейство T преобразований открытого текста. Члены этого семейства индексируются, или обозначаются символом k параметр k обычно называется ключом. Преобразование Tk определяется соответствующим алгоритмом и значением ключа k.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

и получить пару ключей k1, k2 . Один из ключей например, k1 публикуется, он называется открытым, а второй, называемый секретным, хранится в тайне. Алгоритмы шифрования и расшифрования таковы, что для любого открытого текста m . Рассмотрим теперь гипотетическую атаку злоумышленника на эту систему. Противнику известен открытый ключ k1, но неизвестен соответствующий секретный ключ k2. Противник перехватил криптограмму d и пытается найти сообщение m, где .

Поскольку алгоритм шифрования открыт, противник может просто последовательно перебрать все возможные сообщения длины n, вычислить для каждого такого сообщения mi криптограмму и сравнить di с d. То сообщение, для которого di d и будет искомым открытым текстом. Если повезет, то открытый текст будет найден достаточно быстро. В худшем же случае перебор будет выполнен за время порядка 2nT n , где

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

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

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

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

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

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

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

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

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

т. е. предположения о сложности конкретных теоретико-числовых задач. Все эти предположения в литературе обычно называются криптографическими. Рассмотрим одно из таких предположений. Обозначим через S Sn ? n. L О S L, x О L П L f S S x О S f x . L NP SґS 0,1 L x y P x,y y Ј ? x . То есть язык L принадлежит

NP, если для всякого слова из L длины п можно угадать некоторую строку полиномиальной от п длины и затем с помощью предиката Р убедиться в правильности догадки. Ясно, что РНNP P NP NP , NP NP P NP. Нам еще потребуется понятие вероятностной машины Тьюринга. В обычных машинах Тьюринга их называют детерминированными новое состояние, в которое машина переходит на очередном шаге, полностью определяется текущим состоянием и тем символом, который обозревает

головка на ленте. В вероятностных машинах новое состояние может зависеть еще и от случайной величины, которая принимает значения 0 и 1 с вероятностью 1 2 каждое. Можно считать, что вероятностная машина Тьюринга имеет дополнительную случайную ленту, на которой записана бесконечная двоичная случайная строка. Случайная лента может читаться только в одном направлении и переход в новое состояние может зависеть от символа, обозреваемого на этой ленте.

Рассмотрим теперь следующий естественный вопрос не является ли гипотеза P NP ? В самом деле, необходимость во многих случаях почти очевидна. Вернемся к рассмотренному выше примеру. Определим следующий язык L k1,d,i mi 1 . Ясно, что L О NP i ? 1 k1,d,i В предположении P NP существует детерминированный полиномиальный алгоритм, распознающий язык

L. Зная k1 и d, с помощью этого алгоритма можно последовательно, по биту, вычислить открытый текст т. Тем самым доказано, что криптосистема нестойкая. Что же касается вопроса о достаточности предположения P NP, NP NP ? 80 Результатом всех этих попыток стало осознание следующего факта даже если P NP, NP NP P NP 1.2.1. Односторонние функции и функции-ловушки Центральным понятием в теории асимметричных криптографических систем является понятие односторонней

функции. Неформально под односторонней функцией понимается эффективно вычислимая функция, для обращения которой т.е. для поиска хотя бы одного значения аргумента по заданному значению функции не существует эффективных алгоритмов. Заметим, что обратная функция может и не существовать. Под функцией мы будем понимать семейство отображений fn , где fn Sn Sm, m m n n fn f , q x , n q m n і n. Формально понятие односторонней функции описывается следующим

образом Четная функция f называется односторонней, если 1. Существует полиномиальный алгоритм, который для всякого x вычисляет f x 2. Для любой полиномиальной вероятностной машины Тьюринга A выполнено следующее. Пусть строка x выбрана случайным образом из множества Sn. p ? n P f A f x f x 1 p n . Второе условие качественно означает следующее.

Любая полиномиальная вероятностная машина Тьюринга A может по данному y найти x из уравнения f x y лишь с пренебрежимо малой вероятностью. Заметим, что требование честности опустить нельзя. Поскольку длина входного слова f x машины A равна m, ей может не хватить полиномиального от m времени просто на выписывание строки x. Существование односторонних функций является необходимым условием стойкости

многих криптосистем. Рассмотрим функцию f, такую, что f r k1. Она вычислима с помощью алгоритма G за полиномиальное время. Покажем, что если f не односторонняя функция, то криптосистема нестойкая. Предположим, что существует полиномиальный вероятностный алгоритм A, обращающий f с вероятностью по крайней мере 1 p n для некоторого полинома p.

Злоумышленник может подать на вход алгоритма значение ключа k1 и получить с указанной вероятностью некоторое значение r из прообраза. Далее злоумышленник подает r на вход алгоритма G и получает пару ключей k1, k2 . Хотя k2 не обязательно совпадает с k2, по определению криптосистемы для любого открытого текста m. Поскольку k2 найден с вероятностью по крайней мере 1 p n , схема нестойкая. Функцией-ловушкой называется односторонняя функция, для которой обратную функцию вычислить просто,

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

Допустим, задано большое простое число p и пусть g примитивный элемент поля GF p . Тогда для любого a вычислить ga mod p просто, а вычислить a по заданным k ga mod p и p оказывается затруднительным. Криптосистемы с открытым ключом основываются на односторонних функциях-ловушках. При этом открытый ключ определяет конкретную реализацию функции, а секретный ключ дает информацию о ловушке. Любой, знающий ловушку, может легко вычислять функцию в обоих направлениях, но тот, у кого

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

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

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

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

Ривеста-Шамира-Адельмана, основанные на сложностях соответственно дискретного логарифмирования и разложения целого числа на множители. Предположительно стойкие криптоалгоритмы основаны на сложности решения частной математической задачи, которая не сводится к хорошо известным задачам и которую пытались решить один или несколько человек. Примерами могут быть криптоалгоритмы ГОСТ 28147-89, DES, FEAL. К сожалению, безусловно стойкие криптосистемы неудобны на практике системы

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

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

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

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

функцию имитозащиты. Операции шифрования и расшифрования можно описать так Y E X , X D Y . Для взаимной однозначности необходимо, чтобы DE было единичным преобразованием. Предполагаться наличие у отправителя и получателя общего секретного ключа 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 e , где e -

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

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

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

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

текст, обладающий таким же образом, вычислительно невозможно. Задача создания стойкой хэш-функции возникает, например, при цифровой подписи текстов. Одно из возможных самостоятельных применений хэш-функций - это опознавание пользователя с помощью цепочки вида x , h x , h h x h 2 x , h 3 x , h k x . Последнее значение цепочки h k x является контрольной информацией для проверяющего, а пользователь знает h k-1 x и предъявляет эту информацию по требованию проверяющего.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ВС, выделим следующие причины ненадежности криптографических программ 1. Невозможность применения стойких криптоалгоритмов 2. Ошибки в реализации криптоалгоритмов 3. Неправильное применение криптоалгоритмов 4. Человеческий фактор. Причины ненадежности можно отобразить на следующей схеме 2.1.4. Невозможность применения стойких криптоалгоритмов Эта группа причин является наиболее распространенной

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

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

приобретать патент или права на них. В частности, из США запрещен экспорт криптоалгоритмов с длиной ключа более 40 бит. Очевидно, что такая криптостойкость не может считаться надежной при современных вычислительных мощностях и даже на персональном компьютере, положив скорость перебора в 50 000 паролей сек, получим время перебора в среднем порядка 4 месяцев. Известные примеры программ, подверженных экспортным ограничениям - это

последние версии браузеров browser Интернета, в частности фирмы и фирмы . Они предоставляют шифрование со 128-битным ключом для пользователей внутри США и с 40-битным ключом для всех остальных. Также в эту группу попадает версия архиватора , известного своим слабым алгоритмом шифрования архивов. Теперь пользователи внутри США могут использовать криптостойкий алгоритм ГОСТ.

Комизм ситуации в том, что хотя этот алгоритм является российским, даже россияне по законам США все равно не могут воспользоваться им в программе ARJ. 1.2.2.3. Использование собственных криптоалгоритмов Незнание или нежелание использовать известные алгоритмы - такая ситуация, как ни парадоксально, также имеет место быть, особенно в программах типа Freeware и

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

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

с легкостью определит пароль архива и извлечет оттуда все остальные файлы криптостойкость ARJпри наличии открытого текста - 20 Даже если ни одного файла в незашифрованном виде нет, то все равно простое гаммирование позволяет достичь скорости перебора в 350000 паролей сек. на машине класса Pentium. Аналогичная ситуация имеет место и в случае с популярными программами из - для определения пароля там необходимо знать всего 16 байт файла или , после чего достаточно перебрать всего 24 вариантов.

В Microsoft Office 97 сделаны значительные улучшения алгоритмов шифрования, в результате чего осталась возможность только полного перебора, но не везде использует примитивнейший алгоритм, причем шифруются не данные, а сам пароль операцией XOR с фиксированной константой! В сетевой ОС фирмы версии 3.х и 4.х также применяется собственный алгоритм хеширования. На входе хэш-функция получает 32-байтовое значение, полученное из оригинального пароля пользователя

путем либо сжатия пароля длиной более 32 символов с помощью операции XOR, либо размножением пароля длиной менее 32 символов а на выходе - 16-байтовое хэш-значение Hash16 . Именно оно для Novell Netware 3.х хранится в базе данных связок bindery в виде свойства PASSWORD . Одним из основных свойств криптостойкой хэш-функции должно быть то, что она не должна допускать

легкого построения коллизий таковой, например, является функция crypt , используемая в UNIX, которая основана на DES . Именно это свойство нарушено в хэш-функции, применяемой в Novell Netware. Была построена процедура, которая из данного хэш-значения путем небольшого перебора несколько секунд на машине класса 80486DX2-66 получает 32-байтовую последовательность, которая, конечно, не является истинным паролем, но, тем не менее, воспринимается

Novell Netware как таковой, т.к. применение к ней хэш-алгоритма, выдает в точности имеющееся хэш-значение. Рассмотренный хэш-алгоритм остался и в 4 версии Novell Netware. В свою очередь, фирма Microsoft также имеет серьезнейшие недостатки в своем основном хэш-алгоритме, применяемом в своих ОС, начиная с Windows 3.11, при аутентификации в локальных протокол NetBIOS и глобальных протоколы CIFS и http сетях, называемым

LM Lan Manager -хэш. Впрочем, Microsoft ссылается на то, что он остался еще со времен OS 2 и что его разрабатывала IBM . Он вычисляется следующим образом 1. Пароль превращается в 14-символьную строку путем либо отсечки более длинных паролей, либо дополнения коротких паролей нулевыми элементами. 2. Все символы нижнего регистра заменяются на символы верхнего регистра. Цифры и специальные символы остаются без изменений.

3. 14-байтовая строка разбивается на две семибайтовых половины. 4. Используя каждую половину строки в роли ключа DES, с ним шифруется фиксированная константа, получая на выходе две 8-байтовые строки. 5. Эти строки сливаются для создания 16-разрядного значения хэш-функции. Очевидно, что атаки на LM-хэш легко достигают успеха по следующим причинам 1. Преобразование всех символов в верхний регистр ограничивает и без того небольшое число возможных комбинаций

для каждого 26 10 32 68 . 2. Две семибайтовых половины пароля хэшируются независимо друг от друга. Таким образом, две половины могут подбираться перебором независимо друг от друга, и пароли, длина которых превышает семь символов, не сильнее, чем пароли с длиной семь символов. Таким образом, для гарантированного нахождения пароля необходимо перебрать вместо 940 941 9414 4L1027 всего лишь 2L 680 681 687 1L1013 т.е. почти в 1014 раз меньше комбинаций.

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

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

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

Поэтому пользователь, задав, например, достаточно надежный пароль passwordIsgood19, будет весьма удивлен, узнав, что хакер вошел в систему под его именем с помощью элементарного пароля password. 2. Novell Netware позволяет пользователям иметь пароли до 128 байт, что дает считая латинские буквы без учета регистра, цифры и спецсимволы 68128 2779 комбинаций. Но при этом, во-первых, хэш-функция см. выше получает на входе всего лишь 32-байтовое значение, что

ограничивает эффективную длину пароля этой же величиной. Более того, во-вторых, на выходе хэш-значение имеет длину всего 128 бит, что соответствует 2128 комбинаций. Это дополнительно снижает эффективную длину до 21 символа, т.е. в 6 раз по сравнению с первоначальной. 3. Полностью аналогичная ситуация происходит с архиватором версий 1.5x - выбор пароля больше 10 символов не приводит к росту времени, необходимого на его вскрытие.

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

атак перебором не ключей, а паролей. 2.2.2. Отсутствие проверки на слабые ключи Некоторые криптоалгоритмы в частности, DES, IDEA при шифровании со специфическими ключами не могут обеспечить должный уровень криптостойкости. Такие ключи называют слабыми weak . Для DES известно 4 слабых и 12 полуслабых semi-weak ключей. И хотя вероятность попасть в них равняется 2L10-16, для серьезных криптографических систем пренебрегать

ей нельзя. Мощность множества слабых ключей IDEA составляет не много - не мало - 251 впрочем, из-за того, что всего ключей 2128, вероятность попасть в него в 3L107 раз меньше, чем у DES . 2.2.3. Недостаточная защищенность от РПС РПС разрушающие программные средства - это компьютерные вирусы, троянские кони, программные закладки и тому подобные программы, способные перехватить секретный ключ или сами нешифрованные данные, а также просто подменить алгоритм на некриптостойкий.

В случае если программист не предусмотрел достаточных способов защиты от РПС, они легко способны нарушить безопасность криптосистемы. Особенно это актуально для операционных систем, не имеющих встроенных средств защиты или средств разграничения доступа - типа MS DOS или Windows 95 1. Перехват пароля. Как пример можно привести самый старый способ похищения пароля, известный еще со времен больших

ЭВМ, когда программа- фантом эмулирует приглашение ОС, предлагая ввести имя пользователя и пароль, запоминает его в некотором файле и прекращает работу с сообщением Invalid password . Для MS DOS и Windows существует множество закладок для чтения и сохранения паролей, набираемых на клавиатуре через перехват соответствующего прерывания , например, при работе утилиты 2. Подмена криптоалгоритма. Примером реализации этого случая является закладка, маскируемая

под прикладную программу-ускоритель типа Turbo Krypton. Эта закладка заменяет алгоритм шифрования ГОСТ 28147-89, реализуемой платой Krypton-3 демонстрационный вариант , другим, простым и легко дешифруемым алгоритмом. 3. Троянский конь в электронной почте. Примером служит имевшие место в июне 1998 года попытки проникновения троянского коня через электронную почту. В письмо были вложены порнографическая картинка и

EXE-файл FREECD.EXE, который за то время, пока пользователь развлекался с письмом, расшифровывал пароли на соединение с провайдером Dial-Up и отправлял их на адрес ispp usa.net. 1.2.2.4. Наличие зависимости во времени обработки ключей Это сравнительно новый аспект недостаточно корректной реализации криптоалгоритмов. Многие криптосистемы неодинаково быстро обрабатывают разные входные данные.

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

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

защитные методы программирования и специализированные средства разработки особенно компиляторы . 2.2.4. Ошибки в программной реализации Ясно, что пока программы будут писаться людьми, этот фактор всегда будет иметь место. Хороший пример - ОС Novell Netware 3.12, где, несмотря на достаточно продуманную систему аутентификации, при которой, по заявлениям фирмы Novell, нешифрованный пароль никогда не передается по сети , удалось найти ошибку в программе

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

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

AWARD SW и СУБД фирмы , также имеющая суперпароли jIGGAe и nx66ppx . Вплотную к наличию люков в реализации очевидно, что в этом случае они используют явно нестойкие алгоритмы или хранят ключ вместе с данными примыкают алгоритмы, дающие возможность третьему лицу читать зашифрованное сообщение, как это сделано в нашумевшем проекте , где третьим лицом выступает государство, всегда любящее совать нос в тайны своих граждан. 2.2.6. Недостатки датчика случайных чисел

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

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

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

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

ПСЧ, используя текущее время в секундах sec и микросекундах usec , а также идентификаторы процесса pid и ppid . Как выяснили исследователи Я. Голдберг и Д. Вагнер, при такой схеме как максимум получалось 47 значащих бит информации притом, что этот датчик использовался для получения 40- или 128 -битных ключей . Но, если у злоумышленника была возможность перехватить пакеты, передаваемые по сети, и был доступ account

на компьютер, где запущена программа, то для него не составляло труда с большой степенью вероятности узнать sec, pid и ppid. Если это не удавалось, то злоумышленник все равно мог попытаться установить время через сетевые демоны time, pid мог бы быть получен через демон SMTP обычно он входит в поле Message-ID , а ppid либо не сильно отличается от pid, либо вообще равен 1. Исследователи написали программу , которая, перебирая микросекунды, находила секретный 40-битный ключ

в среднем за минуту. 2.3.4. Неправильное применение криптоалгоритмов Эта группа причин приводит к тому, что оказывается ненадежными криптостойкие и корректно реализованные алгоритмы. 1.2.4.1. Малая длина ключа Это самая очевидная причина. Возникает вопрос как стойкие криптоалгоритмы могут иметь малую длину ключа? Видимо, вследствие двух факторов 1. Некоторые алгоритмы могут работать с переменной длиной ключа, обеспечивая

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

RSA, для вскрытия которого необходимо решать задачу факторизации. В марте 1994 была закончена длившаяся в течение 8 месяцев факторизация числа из 129 цифр 428 бит . Для этого было задействовано 600 добровольцев и 1600 машин, связанных посредством электронной почты. Затраченное машинное время было эквивалентно примерно 5000 MIPS-лет. Прогресс в решении проблемы факторизации во многом связан не только с ростом вычислительных

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

29 января 1997 фирмой RSA Labs был объявлен конкурс на вскрытие симметричного алгоритма RC5. 40-битный ключ был вскрыт через 3.5 часа после начала конкурса! Для этого даже не потребовалась связывать компьютеры через Интернет - хватило локальной сети из 250 машин в Берклевском университете . Через 313 часов был вскрыт и 48-битный ключ. Таким образом, всем стало очевидно, что длина ключа, удовлетворяющая

экспортным ограничениям, не может обеспечить даже минимальной надежности. Параллельно со вскрытием RC5 был дан вызов и столпу американской криптографии - алгоритму DES, имеющему ключ в 56 бит. И он пал 17 июня 1997 года, через 140 дней после начала конкурса при этом было протестировано около 25 всех возможных ключей и затрачено примерно 450 MIPS-лет . Это было, безусловно, выдающееся достижение, которое означало фактическую смерть

DES как стандарта шифрования. И действительно, когда в начала 1998 года следующее соревнование по нахождению ключа DES привело к успеху всего за 39 дней, национальный институт стандартов США NIST объявил конкурс на утверждение нового стандарта AES Advanced Encryption Standard . AES должен быть полностью открытым симметричным алгоритмом с ключом размером 128, 192, 256 бит и блоком шифрования размером 128 бит.

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

BIOS, хранящий вместо хэша пароля его зашифрованный вариант, который, естественно, легко дешифруется. Во всех сетевых процедурах аутентификации естественно применять ассиметричную криптографию, которая не позволит подобрать ключ даже при полном перехвате трафика. Однако такие алгоритмы из сетевых OC пока реализует только Novell Netware 4.x, остальные же довольствуются в лучшем случае! стандартной схемой запрос-отклик ,

при которой можно вести достаточно быстрый перебор по перехваченным значениям запроса и отклика . 1.2.4.3. Повторное наложение гаммы шифра Уже классическим примером стала уязвимость в Windows 3.x и первых версиях Windows 95, связанная с шифрованием. В этом случае программисты фирмы Microsoft, хорошо известные своими знаниями в области безопасности, применяли алгоритм RC4 представляющем собой ни что иное, как шифрование гаммированием , не меняя гаммы,

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

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

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

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

Отсюда следует, что где-то внутри любого браузера, почтового или ftp-клиента будь то Netscape Communicator, Eudora, Outlook, FAR и т.п. лежат все ваши пароли в практически открытом виде, и что расшифровать их не представляет труда. Чаще всего, кстати, пароль в таких программах даже не шифруется, а кодируется алгоритмом типа base-64 . 1.2.5. Человеческий фактор В любой критической системе ошибки человека-оператора являются чуть ли не самыми

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

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

была реализована так, что выполнялась почти 1 секунду на машину класса PDP, то за двадцать лет скорость ее вычисления увеличилась в 15000 раз Поэтому если раньше хакеры и разработчики, которые ограничили длину пароля 8 символами и представить себе не могли полный перебор, то сегодня такая атака в среднем приведет к успеху за 80 дней. Скорость перебора паролей для различных криптосистем приведена в таблице

Криптосистема Скорость, паролей cек. ARJ 2.50 350 000 RC5 - 56 бит 150 000 LM-хэш 50 000 Novell Netware 3.x 25 000 MS Office 97 15 000 UNIX - crypt 15 000 RAR 2.0 1 000 UNIX -MD5 500 Скорость полного перебора на компьютере класса Pentium 166 MHz. Однако вернемся на несколько лет назад, когда вычислительной мощности для полного перебора

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

размером всего 1000 слов Даже вирус Морриса в 1988 г. применял такой способ, тем более что в UNIX под рукой часто оказывается файл-словарь, обычно используемый программами-корректорами. Что же касается собственных паролей, то файл может дать немало информации о пользователе его входное имя, имя и фамилию, домашний каталог. Вирус Морриса с успехом пользовался следующими предположениями 1. В качестве пароля берется входное имя пользователя 2.

Пароль представляет собой двойной повтор имени пользователя 3. То же, но прочитанное справа налево 4. Имя или фамилия пользователя 5. То же, но в нижнем регистре. Пусть сегодня пользователи уже понимают, что выбирать такие пароли нельзя, но до тех пор, пока с компьютером работает человек, эксперты по компьютерной безопасности не дождутся использования таких простых и радующих душу паролей, как 34jXs5U bTa!6.

Поэтому даже искушенный пользователь хитрит и выбирает такие пароли, как hope1, user1997, pAsSwOrD, toor, roottoor, parol, gfhjkm, asxz. Видно, что все они, как правило, базируются на осмысленном слове и некотором простом правиле его преобразования прибавить цифру, прибавить год, перевести через букву в другой регистр, записать слово наоборот, прибавить записанное наоборот слово, записать русское слово латинскими буквами, набрать русское слово на клавиатуре с латинской раскладкой, составить пароль из

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

Во многих книгах по безопасности предлагается выбирать в качестве надежного пароля два осмысленных слова, разделенных некоторым знаком, например good!password . Подсчитаем, за сколько времени в среднем будут сломаны такие пароли, если такое правило включено в набор программы-взломщика пусть словарь 10000 слов, разделительными знаками могут быть 10 цифр и 32 знака препинания и специальных символа, машина класса

Pentium со скоростью 15000 crypt сек 140 000 секунд или менее 1.5 дней! Постепенно разработчики осознают необходимость применения зарекомендовавших себя алгоритмов, сдвигаются с мертвой точки позиции некоторых стран в вопросе экспорта криптоалгоритмов, разрабатываются новые алгоритмы и стандарты с большей длиной ключа и эффективностью для реализации на всех типах процессоров, от 8-битных до RISC. Тем не менее, остается огромная пропасть между уровнем стойкости и надежности существующего

сейчас ПО, применяющего криптоалгоритмы, в котором до сих пор находятся детские дыры пример - реализация PPTP от Microsoft и тем уровнем криптостойкости, который демонстрируют последние, независимо проанализированные ведущими криптоаналитиками алгоритмы и протоколы, где серьезной уязвимостью считается, например, та, что требует 265 блоков шифрованного текста и затем 258 перебора вариантов или одного открытого текста, зашифрованного 233 разными, но зависимыми друг от друга ключами и затем сложности анализа, равного 257.

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

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

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

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

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

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

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

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

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

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

шифра. Это означает, что если выполнить операцию XOR над некоторыми битами открытого текста, затем над некоторыми битами шифротекста, а затем над результатами, получится бит, который представляет собой XOR некоторых бит ключа. Это называется линейным приближением, которое может быть верным с некоторой вероятностью p. Если p?1 2, то это смещение можно использовать. Можно использовать собранные открытые тексты и связанные шифротексты для предположения о значениях

битов ключа. Чем больше данных, тем вернее предположение, чем больше смещение, тем быстрее вскрытие увенчается успехом. 1.3.4. Метод встречи посередине Если множество ключей криптоалгоритма замкнуто относительно композиции, то есть для любых ключей z i и z j найдется ключ zk такой, что результат шифрования любого текста последовательно на z i и z j равен шифрограмме этого же числа на zk , то есть F z j ,F z i , x

F z k , x , то можно воспользоваться этим свойством. Пусть нам нужно найти ключ zk. Тогда для нахождения ключа zk, необходимо найти эквивалентную ему пару ключей zi , zj. Данный метод криптоанализа основан на парадоксе дней рождения . Известно, что если считать, что дни рождения распределены равномерно, то в группе из 24 человек с вероятностью 0,5 у двух человек дни рождения совпадут. Пусть известен открытый текст x и его шифрограмма y.

Для текста x строим базу данных, содержащую случайное множество ключей z и соответствующих шифрограмм w F z , x , и упорядочиваем ее по шифрограммам w. Затем подбираем случайным образом ключи z для расшифровки текста y и результат расшифрования v F z , y сравниваем с базой данных. Если текст v окажется равным одной из шифрограмм w, то ключ z z эквивалентен искомому ключу z. Временная сложность метода составляет О Ц z log z . log z ?

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

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

Кроме того, для нейросетей разработаны мощные алгоритмы обучения, позволяющие автоматизировать процесс создания и настройки системы. 1.5. Выводы В ходе проведения аналитического обзора была изучена предметная область, рассмотрены существующие методы криптографии и криптоанализа, обнаружены их основные достоинства и недостатки. В аналитическом обзоре показано, что создание системы анализа криптографических алгоритмов является актуальной задачей. ГЛАВА 2. РАЗРАБОТКА СИСТЕМЫ

АНАЛИЗА КРИПТОГРАФИЧЕСКИХ СИСТЕМ С ИСПОЛЬЗОВАНИЕМ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА Система анализа криптографических алгоритмов состоит из двух подсистем подсистемы криптографической защиты информации с использованием представителей различных классов шифров и подсистемы криптоанализа. Схема системы анализа криптографических алгоритмов представлена на рисунке 2.1. Рис. 2.1 Схема системы криптоанализа 2.1. Разработка системы криптографического анализа с использованием

представителей различных классов шифров. 2.1.1. Шифр DES DES представляет собой блочный шифр, он шифрует данные 64-битовыми блоками. С одного конца алгоритма вводится 64-битовый блок открытого текста, а с другого конца выходит 64-битовый блок шифротекста. DES является симметричным алгоритмом для шифрования и дешифрирования используются одинаковые алгоритм и ключ за исключением небольших различий в использовании ключа . длина ключа равна 56

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

чем комбинация двух основных методов шифрования смещения и диффузии. Фундаментальным строительным блоком DES является применение к тексту единичной комбинации этих методов подстановка, а за ней DES 16 16 Рис. 2.2 DES Алгоритм использует только стандартную арифметику 64-битовых чисел и логические операции, поэтому он легко реализовывался в аппаратуре второй половины 70-х. Изобилие повторений в алгоритме делает его идеальным для реализации в специализированной микросхеме.

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

перестановкой обратной по отношению к первоначальной . На каждом этапе биты ключа сдвигаются, и затем из 56 битов ключа выбираются 48 битов. Правая половина данных увеличивается до 48 битов с помощью перестановки с расширением, объединяется посредством ХОR. с 48 битами смещенного и переставленного ключа, проходит через 8 8-блоков, образуя 32 новых бита, и переставляется снова. Эти четыре операции и выполняются функцией f.

Затем результат функции f объединяется с левой половиной с помощью другого ХОR В итоге этих действий появляется новая правая половина, а старая правая половина становится новой левой. Эти действия повторяются 16 раз, образуя 16 этапов DES Рис. 2.3 Один этап DES. Если Вi - i Li Ri ?i, Ki - 48 i f R Начальная перестановка выполняется еще до этапа 1, при этом входной блок переставляется.

Начальная перестановка Таблица 2. Начальная перестановка Шифра DES. 58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4 62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8 57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3 61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7 Начальная перестановка и соответствующая заключительная перестановка не влияют на безопасность DES Как можно легко заметить, эта перестановка в первую очередь служит для облегчения побайтной загрузки данных открытого текста и шифротекста в микросхему

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

DES. Преобразования ключа 64-битовый ключ DES уменьшается до 56-битового ключа отбрасыванием каждого восьмого бита. Эти биты используются только для контроля четности, позволяя проверять правильность ключа. После извлечения 56-битового ключа для каждого из 16 этапов DES генерируется новый 48-битовый подключ и эти подключи, Ki, определяются следующим образом Таблица 3. Преобразования ключа

DES. 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 Во первых, 56-битовый ключ делится на две 28-битовых половинки. Затем, половинки циклически сдвигаются налево на один или два бита в зависимости от этапа. Таблица 4. Число битов сдвига в зависимости от этапа DES. Этап 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Число 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

После сдвига выбирается 48 из 56 битов. Так как при этом не только выбирается подмножество битов, но и изменяется их порядок, эта операция называется перестановка со сжатием. Ее результатом является набор из 48 битов. Например, бит сдвинутого ключа в позиции 33 перемещается в позицию 35 результата, а 18-й бит сдвинутого ключа отбрасывается. Таблица 5. Перестановка со сжатием. 14 17 11 24 1 5 3 28 15 6 21 10 23 19 11 4 26 8 16 7 27 20 13 2 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32

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

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

DES спроектирован так, чтобы как можно быстрее добиться зависимости каждого бита шифротекста от каждого бита открытого текста и каждого бита ключа. Перестановка с расширением показана на 9-й. Иногда она называется Е-блоком от expansion . для каждого 4-битового входного блока первый и четвертый бит представляют собой два бита выходного блока, а второй и третий биты - один бит выходного блока. В 7-й показано, какие позиции результата соответствуют каким позициям исходных данных.

Например, бит входного блока в позиции З переместится в позицию 4 выходного блока, а бит входного блока в позиции 21 - в позиции 30 и 32 выходного блока. Рис. 2.4. Перестановка с расширением Хотя выходной блок больше входного, каждый входной блок генерирует уникальный выходной блок Таблица 6. Перестановка с расширением DES. 32 1 2 3 4 5 4 5 6 7 8 9 8 9 10 11 12 13 12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29 30 31 32 1

Подстановка с помощью S-блоков После объединения сжатого блока с расширенным блоком с помощью ХОR. над 48-битовым результатом выполняется операция подстановки. Подстановки производятся в восьми блоках подстановки, или S-блоках от Substitution . У каждого 8-блока 6-битовый вход и 4-битовый выход, всего используется восемь различных S-блоков. для восьми S-блоков DES потребуется 256 байтов памяти.

48 битов делятся на восемь 6-битовых подблока. Каждый отдельный подблок обрабатывается отдельным S-блоком первый подблок - S 1 S 2 ? Рис 2.5 Подстановка S блоки Каждый S-блок представляет собой таблицу из 2 строк и 16 столбцов. Каждый элемент в блоке является 4- битовым числом. По 6 входным битам S-блока определяется, под какими номерами столбцов и строк искать выходное значение.

Перестановка с помощью Р-блоков 32-битовый выход подстановки с помощью S-блоков, перетасовываются в соответствии с Р-блоком. Эта перестановка перемещает каждый входной бит в другую позицию, ни один бит не используется дважды, и ни один бит не игнорируется. Этот процесс называется прямой перестановкой или просто перестановкой. Например, бит 21 перемещается в позицию 4, а бит 4 31.

Таблица 7. перестановка с помощью P блоков. 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 Наконец, результат перестановки с помощью Р-блока объединяется посредством XOR. с левой половиной первоначального 64-битового блока. Затем левая и правая половины меняются местами, и начинается следующий этап. Заключительная перестановка является обратной по отношению к начальной перестановки.

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

DES. 40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31 38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29 36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27 34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25 Дешифрирование DES После всех подстановок, перестановок, операций XOR. и циклических сдвигов можно подумать, что алгоритм дешифрирования, резко отличаясь от алгоритма шифрования, точно также запутан. Напротив, различные компоненты DES были подобраны так, чтобы выполнялось очень полезное свойство для шифрования и дешифрирования используется

один и тот же алгоритм. DES позволяет использовать для шифрования или дешифрирования блока одну и ту же функцию. Единственное отличие состоит в том, что ключи должны использоваться в обратном порядке. То есть, если на этапах шифрования использовались ключи К1, К2, К3 ?16, ?16, ?15, ?14 ?1 0, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1. 2.1.2. Шифр Feal В качестве входа процесса шифрования используется 64-битовый блок открытого текста.

Сначала блок данных подвергается операции XOR. с 64 битами ключа, а затем блок данных расщепляется не левую и правую половины. Объединение левой и правой половин с помощью ХОР. образует новую правую половину. Левая половина и новая правая половина проходят через n этапов первоначально четыре . На каждом этапе правая половина объединяется с помощью функции f с шестнадцатью битами ключа и с помощью XOR n n ? XOR 64 64 Рис. 2.6

Один этап Feal Функция f берет 32 бита данных и 16 битов ключа и смешивает их вместе. Сначала блок данных разбивается на 8-битовые кусочки, которые затем объединяются с помощью XOR. и заменяют друг друга. Две функции S0 и S1 определяются следующим образом S0 а,b циклический сдвиг влево на два бита а b mod 256 S1 а,b циклический сдвиг влево на два бита а b 1 mod 256

Рис. 2.7 Функция f. Тот же алгоритм может быть использован для дешифрирования. Единственным отличием является то, что при дешифрировании порядок использования частей ключа меняется на обратный. Сначала 64-битовый ключ делится на две половины, к которым применятся операции XOR и функции f. 32 8 S0 ? S1 16 Рис. 2.8 Обработка ключ в Feal. 2.1.3. Шифр REDOC REDOC выполняет все манипуляции - перестановки, подстановки и

XOR с ключом - с байтами, этот алгоритм эффективен при программной реализации. REDOC использует меняющиеся табличные функции. В отличие от DES, имеющего фиксированный хотя и оптимизированных для безопасности набор таблиц подстановок и перестановок REDOC использует зависимые от ключа и открытого текста наборы таблиц по сути S-блоков . У REDOC 10 этапов, каждый этап представляет собой сложную последовательность манипуляций

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

Томас Кузик Thomas Cusick выполнил крипто анализ одного этапа REDOC, но ему не удалось расширить вскрытие на несколько этапов. Используя дифференциальный криптоанализ, Бихам и Шамир достигли успеха в криптоанализе одного этапа REDOC с помощью 2300 выбранных открытых текстов Они не смогли расширить это вскрытие на несколько этапов, но им удалось получить три значения маски после 4 этапов.

2.1.4. Шифр LOKI Механизм LOKI похож на DES. Блок данных делится на левую и правую половины и проходит через 16 этапов, что очень походе на DES. На каждом этапе правая половина сначала подвергается оп е-рации XOR с частью ключа, а затем над ней выполняется перестановка с расширением. Рис. 2.9 Шифр LOKI91 4 3 2 1 32 31 20 29 28 27 26 25 28 27 26 25 24 23 22 21 20 19 18 17 20 19 18 17 16 15 14 13 12 11 10 9 12 11 10 9 8 7 6 5 4 3 2 1 48-битовый результат делится на четыре 12-битовых блока, для каждого из которых выполняется следующая подстановка

с использованием S-блока берется каждый 12-битовый вход, по 2 крайних левых и крайних правых бита используются для получения номера r, в 8 центральных бит образуют номер c. Результатом S-блока - O - является следующее значение О r,с C г 17 Oxff Oxff 31 mod Pr Затем четыре 8-битовых результата снова объединяются, образуя 32-битовое число, которое подвергается операции перестановки.

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

На каждом этапе подключом является левая половина. Далее она циклически сдвигается влево на 12 или 13 битов, затем после каждых двух этапов левая и правая половины меняются местами. Как и в DES для шифрования и дешифрирования используется один и тот же алгоритм с некоторыми изменениями в использовании подключей. 2.1.5.Шифр RC2 RC2 представляет собой алгоритм с переменной длиной ключа.

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

RC2 в три раза быстрее DES. Алгоритм может использовать ключ переменной длины, от 0 байтов до максимальной длины строки, поддерживаемой компьютерной системой, скорость шифрования не зависит от размера ключа. Этот ключ предварительно используется для заполнения 128-байтовой таблицы, зависящей от ключа. Поэтому множество действительно различных ключей составляет 21024. RC2 не использует S-блоков, используются две операции - смешивание и перемешивание mix и mash , для

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

и утверждает, что позволит криптоаналитикам опубликовать любые обнаруженные негативные результаты. 2.1.6 Шифр RC5 RC5 представляет собой блочный шифр с большим числом параметров размером блока, размером ключа и количеством этапов. Он также был изобретен Роном Ривестом. Используются три действия XOR, сложение и циклические сдвиги. На большинстве процессоров операции циклического сдвига выполняются за постоянное время, переменные

циклические сдвиги являются нелинейной функцией. Эти циклические сдвиги, зависят и от ключа и от данных. RC5 использует блок переменной длины, но мы рассмотрим 64-битовый блок. Шифрование использует 2r 2 зависящих от ключа 32-битовых слов S0, S1, S2, S2r 1 где r число этапов. Для шифрования блок открытого текста делится на два 32-битовых слова А и В, затем A A S0 B B S1 For i 1 to r A A Е

B B S2i B B Е A A S2i 1 Результат находится в регистрах А и В. Дешифрование также просто. For i r down to 1 B B S2i 1 A Е A A A S2i B Е B B B S1 A A S0 Символ обозначает циклический сдвиг направо. Сложения и вычитания выполняются по модулю 232. Создание массива ключей также прямолинейно. Сначала байты ключа копируются в массив L из 32-битовых слов, дополняя по необходимости заключительное

слово нулями. Затем массив S инициализируется при помощи линейного конгруэнтного генератора по модулю 232 S0 P For i 1 to 2 r 1 1 Si Si-1 Q mod 232 P 0xB7E15163 и Q 0x9E3779B9, эти константы основываются на двоичном представлении e и phi. Далее подставляем L в S i j 0 A B 0 For k max 2 r 1 , c A Si Si A B 3 B Li Li A B A B i i 1 mod 2 r 1 j j 1 mod c

По сути RC5 представляет собой семейство алгоритмов. Можно использовать RC5 с 32-битовым словом и 64-битовым блоком и с 64-битовым словом и 128-битовым. Дифференциальный криптоанализ требует 224 выбранных открытых текстов для 5 этапов, 245 для 10 этапов, 253 для 12 этапов и 268 для 15 этапов. Существует только 264 возможных открытых текстов, поэтому такой анализ невозможен для алгоритма с 15

и более этапами. Линейный криптоанализ неприменим после 6 этапов. Алгоритм шифрования RSA Алгоритм RSA предполагает, что посланное закодированное сообщение может быть прочитано адресатом и только им. В этом алгоритме используется два ключа открытый и секретный. Данный алгоритм привлекателен также в случае, когда большое число субъектов N должно общаться по схеме все-со-всеми. В случае симметричной схемы шифрования каждый из субъектов

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

M , и только адресату известно, как выполнить операцию f-1. Адресат выбирает два больших простых prime числа p и q, которые делает секретными. Он объявляет n pq и число d, c d,p-1 d,q-1 1 один из возможных способов выполнить это условие, выбрать d больше чем p 2 и q 2 . Шифрование производится по формуле f M є Md mod n, где M и f M оба Ј n-1. Как было показано, может быть вычислено за разумное время, даже

если M, d и n содержит весьма большое число знаков. Адресат вычисляет M на основе Md, используя свое знание p и q. В соответствие со следствием 6, если dc є p-1 1, тогда Md eє p1. Исходный текст M получается адресатом из зашифрованного F M путем преобразования M F M e mod pq . Здесь как исходный текст, так и зашифрованный рассматриваются

как длинные двоичные числа. Аналогично Md e є qM, если dc є q-1 1. e удовлетворяет этим двум условиям, если cd є p-1 q-1 1. Теорема 1 гласит, что мы можем позволить e x, когда x является решением уравнения dx p-1 q-1 y 1. Так как Md e M делимо на p и q, оно делимо и на pq, следовательно, мы можем определить M, зная Md, вычислив его значение в степени e и определив остаток от деления на pq.

Для соблюдения секретности важно, чтобы, зная n, было нельзя вычислить p и q. Если n содержит 100 цифр, подбор шифра связан с перебором 1050 комбинаций. Данная проблема изучается уже около 100 лет. RSA-алгоритм запатентован 20 сентября 1983, действует до 2000 года . Теоретически можно предположить, что возможно выполнение операции f-1, не вычисляя p и q. Но в любом случае задача эта не проста и разработчики считают ее трудно факторизуемой.

Предположим, что мы имеем зашифрованный текст f M и исходный текст M, и мы хотим найти значения p и q. Нетрудно показать, что таких исходных данных для решения задачи недостаточно надо знать все возможные значения Mi. Проясним использование алгоритма RSA на конкретном примере. Выбираем два простые числа p 7 q 17 на практике эти числа во много раз длиннее .

В этом случае n p q будет равно 119. Теперь необходимо выбрать e, выбираем e 5. Следующий шаг связан с формированием числа d так, чтобы d e 1 mod p-1 q-1 . d 77 использован расширенный алгоритм Эвклида . d секретный ключ, а e и n характеризуют открытый ключ. Пусть текст, который нам нужно зашифровать представляется M 19. С Memod n. Получаем зашифрованный текст C 66.

Этот текст может быть послан соответствующему адресату. Получатель дешифрует полученное сообщение, используя М Cdmod n и C 66. В результате получается M 19. На практике общедоступные ключи могут помещаться в специальную базу данных. При необходимости послать партнеру зашифрованное сообщение можно сделать сначала запрос его открытого ключа. Получив его, можно запустить программу шифрации, а результат ее работы послать

адресату. На использовании общедоступных ключей базируется и так называемая электронная подпись, которая позволяет однозначно идентифицировать отправителя. Сходные средства могут применяться для предотвращения внесения каких-либо корректив в сообщение на пути от отправителя к получателю. Быстродействующие аппаратные 512-битовые модули могут обеспечить скорость шифрования на уровне 64 кбит в сек. Готовятся ИС, способные выполнять такие операции со скоростью 1

Мбайт сек. Разумный выбор параметра e позволяет заметно ускорить реализацию алгоритма. 2.2. Разработка подсистемы криптоанализа 2.2.1 Нейрокомпьютерная сеть встречного распространения. Сеть встречного распространения функционирует подобно столу справок, способному к обобщению. В процессе обучения входные векторы ассоциируются с соответствующими выходными векторами. Эти векторы могут быть двоичными, состоящими из нулей и единиц, или непрерывными.

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

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

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

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

Кохонена выдает на выходе логическую единицу, все остальные выдают ноль. Нейроны Кохонена можно воспринимать как набор электрических лампочек, так что для любого входного вектора загорается одна из них. Ассоциированное с каждым нейроном Кохонена множество весов соединяет его с каждым входом. Например, на рис.4.1 нейрон Кохонена К1 имеет веса w11, w21 wm1, составляющие весовой вектор

W1. Они соединяются-через входной слой с входными сигналами х1, x2 xm, составляющими входной вектор X. Подобно нейронам большинства сетей выход NET каждого нейрона Кохонена является просто суммой взвешенных входов. Это может быть выражено следующим образом NETj w1jx1 w2jx2 wmjxm 4.1 где NETj это выход NET нейрона Кохонена j, 4.2 или в векторной записи

N XW, 4.3 где N вектор выходов NET слоя Кохонена. Нейрон Кохонена с максимальным значением NET является победителем . Его выход равен единице, у остальных он равен нулю. Слой Гроссберга Слой Гроссберга функционирует в сходной манере. Его выход NET является взвешенной суммой выходов k1,k2 kn слоя

Кохонена, образующих вектор К. Вектор соединяющих весов, обозначенный через V, состоит из весов v11, v21 vnp. Тогда выход NET каждого нейрона Гроссберга есть , 4.4 где NETj выход j-го нейрона Гроссберга, или в векторной форме Y KV, 4.5 где Y выходной вектор слоя Гроссберга, К выходной вектор слоя Кохонена, V матрица весов слоя Гроссберга. Если слой

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

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

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

вектора. В алгебраической записи 4.6 Это превращает входной вектор в единичный вектор с тем же самым направлением, т.е. в вектор единичной длины в n-мерном пространстве. Уравнение 4.6 обобщает хорошо известный случай двух измерений, когда длина вектора равна гипотенузе прямоугольного треугольника, образованного его х и у компонентами, как это следует из известной теоремы Пифагора. На рис.4.2а такой двумерный вектор V представлен в координатах х-у, причем координата х равна

четырем, а координата y трем. Квадратный корень из суммы квадратов этих компонент равен пяти. Деление каждой компоненты V на пять дает вектор V с компонентами 4 5 и 3 5, где V указывает в том же направлении, что и V, но имеет единичную длину. На рис.4.26 показано несколько единичных векторов. Они оканчиваются в точках единичной окружности окружности единичного радиуса , что имеет место, когда

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

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

выборе нейрона Кохонена с весовым вектором, наиболее близким к входному вектору, и дальнейшем приближении весового вектора к входному. Снова отметим, что процесс является самообучением, выполняемым без учителя. Сеть самоорганизуется таким образом, что данный нейрон Кохонена имеет максимальный выход для данного входного вектора. Уравнение, описывающее процесс обучения имеет следующий вид wн wс a x ? w 4.7 где wн новое значение

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

Сначала находится вектор X Wс, для этого проводится отрезок из конца W в конец X. Затем этот вектор укорачивается умножением его на скалярную величину a W Рис.2.13. Вращение весового вектора в процессе обучения Wн вектор новых весовых коэффициентов, Wс вектор старых весовых коэффициентов Переменная к является коэффициентом скорости обучения, который вначале обычно равен 0,7 и может постепенно

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

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

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

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

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

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

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

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

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

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

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

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

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

Например, можно построить нейросеть, разбивающую точки 0,0 и 1,1 на два класса для двумерного сигнала, но невозможно решить задачу по разбиению точек 0,0 , 1,1 первый класс, и 0,1 , 1,0 второй. Это широко известный пример неспособности простого персептрона решить задачу исключающее или Рис. 2.10 Теорема Минского 2. Разделение входных данных гиперповерхностями многослойные персептроны .

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

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

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

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

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

связей. Если сеть находится в режиме обучения, то для выигравшего нейрона происходит коррекция весов матрицы связи по формуле wн wс ? x wс , где wн новое значение веса, wс старое значение скорость обучения, x величина входа. Геометрически это правило иллюстрирует рис. Рис. 2.12 Коррекция весов нейрона Кохонена. Так как входной вектор x нормирован, т. е. расположен на гиперсфере единичного радиуса в пространстве весов, то при коррекции весов по этому правилу происходит

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

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

пока не станет активным и не начнет подвергаться обучению. Этот метод позволяет также решить проблему тонкой классификации если образуется группа входных данных, расположенных близко друг к другу, с этой группой ассоциируется и большое число нейронов Кохонена, которые разбивают её на классы. Правило желания работать записывается в следующей форме wн wc wс? 1 - a , где wн новое значение веса, wс старое значение скорость модификации, a активность нейрона.

Чем меньше активность нейрона, тем больше увеличиваются веса связей. Далее сигнал через матрицу весов V поступает на слой Гроссберга здесь слой срабатывает по старому методу. Алгоритм обучения Входные данные обучающая выборка набор входных векторов выходные данные скорректированные связи 1. Предъявить сети входной вектор 2. Выполнять итерации до установления стабильного состояния 3.

Для всех узлов сети выполнить коррекцию связей согласно 2 или 3 4. Повторять 1-3 для каждого входного вектора 2.3.Выводы Разработанная система криптоанализа является достаточно универсальной, не требовательна к памяти и показала себя эффективней, чем классические методы криптоанализа. Достоинствами данной системы являются скорость анализа, легкость адаптации, универсальность существующие

алгоритмы не защищены от такого вида анализа . ГЛАВА 3. РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ КРИПТОАНАЛИЗА В соответствии с алгоритмом была написана программа, осуществляющая криптоанализ трех выбранных представителей блочных шифров DES, RSA, RC2 RC5. Программа была написана в среде Borland Delphi 7. Внешний вид программы представлен на рисунке 3.1.

Рис.3.1. Внешний вид программы криптоанализа Разработанной программой были проанализированный три вида криптографических алгоритмов DES, RSA, RC2. C различными длинами ключа 16, 24, 56. также варьировалось количество зашифрованных символов. Сводные результаты анализа приведены в диаграмме. Рис. 3.2. Среднее время в секундах, необходимое для нахождения закрытого текста с 16 битным ключом на машине класса PIV 1,8 GHZ. Таблица анализа 16 битного ключа показывает, что криптостойкость выбранных

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

образом влияет на криптостойкость, что и подтверждает таблица, представленная ниже. Рис. 3.3. Среднее время в секундах, необходимое для нахождения закрытого текста с 24 битным ключом на машине класса PIV 1,8 GHZ. Криптостойкость с увеличением размера ключа резко возрастает. Причем DES приблизился по криптостойкости к RC2, тогда как для RC5 стойкость возросла в гораздо большей степени. 3.1 .

Выводы Проведенный криптоанализ шифров DES, RC2 и RC5 показал, что шифр RC5 является более стойким по сравнению с другими рассмотренными шифрами. Следовательно, алгоритм RC5 более предпочтительно использовать при шифровании в случаях необходимости защиты данных. Также из анализа видно, что увеличение длины ключа существенно увеличивает криптостойкость шифров. ТЕХНИКО-ЭКОНОМИЧЕСКИЕ показатели 4.1 Технико-экономическое обоснование выбора объекта проектирования

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

A - амортизационные отчисления на износ основных средств выделяются из накладных расходов только в тех случаях, когда оборудование используется только для создания рассматриваемой программной разработки , руб. Эл расходы на электроэнергию, руб процент накладных расходов 120 Разработка программного продукта проводилась на личной технике, амортизационные отчисления, которой входят в состав накладных расходов и отдельно не выносятся.

Заработная плата программистов определяется по следующей формуле , где число разработчиков программного продукта, чел трудоемкость работ i-го разработчика, чел мес основная заработная плата i-го разработчика, руб. мес коэффициент, учитывающий дополнительные выплаты 0,35 - коэффициент, учитывающий отчисления на социальные нужды по действующему законодательству 0,356 . Число разработчиков рассчитывается по следующей формуле , где - общая трудоемкость разработки программного

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

Nоб потребляемая мощность используемого оборудования, кВт Tоб время работы программы при написании программы, ч. аэл установленный тариф за 1 кВт ч. Стоимость материалов на эксплуатационные нужды , где Мi стоимость i-го материала, руб. Ki количество i-го материала, шт. n количество материалов, шт. Амартизационные отчисления , где - установленная норма амортизации j-го вида оборудования приложение 2

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

приведены в таблице 1. Таблица 1. Исходные данные для расчета Название Обозначение Значение Предполагаемое число операторов q 4500 Коэффициент сложности программы c 2.02 Коэффициент коррекции программы p 0.065 Коэффициент квалификации разработчика k 0.8 Стоимость одного машинного часа, руб. Cмч 14 Установленный тариф за 1 кВт. ч руб. aэл 0.9

Время работы оборудования при написании программы, час. tоб 1125 Потребляемая мощность используемого оборудования, кВт. Nоб 0.83 Число видов оборудования, применяемого при разработке m 3 Число тысяч исходных команд n тик 4.5 Коэффициент дополнительных выплат разработчикам а доп 0.35 Коэффициент, учитывающий отчисления на социальные нужды а сн 0.356

Процент накладных расходов, П нр 120 Уровень рентабельности, p 30 Кол-во предполагаемых копий программы, шт. K 1 Стоимость носителей программы для одной копии, руб. Kст 15 Значение НДС, Rндс 20 Стоимость материалов, использованных в процессе создания ПО, более подробно расписана в таблице 2. Таблица 2. Стоимость материалов на эксплуатационные нужды Название материала

Кол-во Ед. изм. Цена, руб. Сумма, руб. Бумага 1 пачка 100 100 гибкий диск 1 шт. 15 15 Картридж для принтера 1 шт. 650 650 Итого за материалы 765 На основании принятых соглашений определим себестоимость программы Сначала определим общую трудоемкость разработки чел мес. Определим продолжительность разработки мес. Определим число разработчиков чел.

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

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

Бровкова М.Б. Разработчик программы Борисов А.А. Программист Сороконенко В. А Определим уровень компетентности каждого эксперта по формуле , где KKi коэффициент компетенции i-го эксперта Kаi коэффициент аргументации i-го эксперта, 0 KaiЈ1 Koci коэффициент осведомленности i-го эксперта Kосmax предельное значение коэффициентов осведомленности и аргументации равное 1.

Для определения коэффициента аргументации используются значения, приведенные в таблице 3. Таблица 3. Коэффициенты аргументации. Источник аргументации Степень влияния источника Высокая Средняя Низкая Проведенный теоретический анализ 0,3 0,2 0,1 Практический исследовательский опыт 0,5 0,4 0,2 Обобщение работ отечественных авторов 0,05 0,05 0,05 Обобщение работ зарубежных авторов 0,05 0,05 0,05 Личное знакомство с состоянием дел за рубежом 0,05 0,05 0,05

Интуиция 0,05 0,05 0,05 Таблица 4. Степень влияния источника Эксперт Степень влияния источника 1 2 3 4 5 6 Бровкова М.Б. 0.30 0.40 0.05 0.05 0.05 0.05 Борисов А.А. 0.30 0.50 0.05 0.05 0.05 0.05 Сороконенко В. А. 0.20 0.40 0.05 0.05 0.05 0.05 Таблица 5. Суммарный коэффициент по таблице 4. Коэффициент аргументации

Бровкова М.Б. 0.90 Борисов А.А. 1.00 Сороконенко В. А. 0.80 Получаем коэффициенты аргументации для каждого эксперта Кa1 0,3 0,4 0,05 0,05 0,05 0,05 0,9 Кa2 0,3 0,5 0,05 0,05 0,05 0,05 1,0 Кa3 0,2 0,4 0,05 0,05 0,05 0,05 0,8 Коэффициент осведомленности устанавливается по усмотрению самих экспертов Таблица 6. Коэффициент осведомленности. Коэффициент осведомленности

Бровкова М.Б. 0.8 Борисов А.А. 0.9 Сороконенко В. А. 0.85 Koc1 0,7 Koc2 0,8 Koc3 0,6. Таким образом, коэффициенты компетентности Таблица 7. Коэффициент компетентности. Коэффициент компетентности Бровкова М.Б. 0.85 Борисов А.А. 0.95 Сороконенко В. А. 0.825 Кк1 0,9 0,8 2 0,85 Кк2 1,0 0,9 2 0,95 Kк3 0,8 0,85 2 0,825.

Возьмем 12 характеристик Таблица 8. Перечень критериев. Перечень критериев Функциональная корректность 1 Способность к взаимодействию 2 Мобильность 3 Понятность 4 Обучаемость 5 Комфортность эксплуатации 6 Устойчивость 7 Восстанавливаемость 8 Время реакции 9 Пропускная способность 10 Занятость ресурсов 11 Используемость ресурсов 12

Таблица 9. Коэффициенты важности характеристик по отобранным критериям. Номер критерия Бровкова М.Б Борисов А.А. Сороконенко В. А. Общее значение 1 1 1 1 0.8750 2 0.75 0.75 0.5 0.5875 3 1 0.75 0.5 0.6583 4 1 1 0.75 0.7271 5 0.5 0.75 0.75 0.5854 6 0.75 0.75 1 0.7250 7 1 1 1 0.8750 8 0.75 0.5 1 0.6458 9 0.75 0.25 0.5 0.4292 10 0.25 0.5 0.25 0.2979 11 0.75 0.75 0.75 0.6563 12 0.75 0.5 0.75 0.5771 Определим общую согласованную оценку каждой характеристики по формуле , где n число экспертов mij оценка i-ым экспертом j-ой характеристики Ккi коэффициент компетентности i-го эксперта

Mj обобщенная оценка экспертов по j-ой характеристике. M1 0.8750 M2 0,5875 M3 0,6583 M4 0,7271 M5 0,5854 M6 0,7250 M7 0,8750 M8 0,6458 M9 0,4292 M10 0,2979 M11 0,6563 M12 0,5771 Затем каждый эксперт устанавливает степень осуществления программного продукта в баллах 0 10 и подсчитывается согласованная оценка по формуле , где n число экспертов vij оценка i-

ым экспертом j-ой характеристики Ккi коэффициент компетентности i-го эксперта Vj обобщенная оценка экспертов по j-ой характеристике. Таблица 10. Оценка характеристик программных продуктов Степень осуществления атрибутов для программы-аналога Номер критерия Бровкова М.Б. Борисов А.А. Сороконенко

В. А. Общее значение Суммарное значение 1 7 5 5 4.9417 4.324 2 3 4 3 2.9417 1.728 3 4 3 4 3.1833 2.096 4 7 6 5 5.2583 3.823 5 4 4 7 4.3250 2.532 6 6 4 7 4.8917 3.546 7 5 5 6 4.6500 4.069 8 4 2 3 2.5917 1.674 9 7 7 8 6.4000 2.747 10 6 4 5 4.3417 1.293 11 3 7 4 4.1667 2.734 12 6 5 9 5.7583 3.323 Таблица 11. Оценка характеристик программных продуктов Степень осуществления атрибутов для разработки Номер критерия Бровкова М.Б. Борисов А.А. Сороконенко В.А. Общее значение Суммарное значение 1 8 8 8 7.0000 6.13 2 7 8 7 6.4417 3.78 3 8 7 9 6.9583 4.58 4 8 9 9 7.5917 5.52 5 8 6 8 6.3667 3.73 6 7 9 7 6.7583 4.9 7 6 8 8 6.4333 5.63 8 8 7 7 6.4083 4.14 9 8 8 7 6.7250 2.89 10 8 9 8 7.3167 2.18 11 7 9 7 6.7583 4.44 12 9 9 8 7.3167 4.22

Находим комплексный показатель уровня конкурентоспособности , для программы-аналога 33.8896 для разработанной программы 52.1284 Сравним полученные уровни качества для аналога и разработки. Имеет место превышение конкурентоспособности программной разработки над аналогом в 1.54 раза. 4.4 Определение цены программной разработки. Цена, программного продукта определяется следующим образом , где - стоимость носителей информации, необходимых для одной копии программы 1 дискета стоимостью 15

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

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

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

одного машинного часа. Экономический эффект пользователя равен , руб руб руб. 4.6 Сводные экономические показатели Все основные экономические показатели, рассчитанные в данной главе, сведены в таблицу 12. Таблица 12. 1. Себестоимость программной разработки 118 815 руб. 2. Цена программы 185 370 руб. 3. Трудоемкость разработки программы 22 чел мес. 4. Продолжительность разработки 6.7 мес. 5. Эксплуатационные расходы 765 руб.

6 Экономический эффект разработчика 66 555 руб. 7 Экономический эффект пользователя 120 032 руб. Структура себестоимости в виде диаграммы 4.7 Выводы В процессе выполнения данного раздела были проведены следующие действия 1. Представлено технико-экономическое обоснование необходимости разработки программного продукта 2. Представлены расчеты затрат на разработку ПО, трудоемкость и продолжительность разработки, с учетом

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