Основы криптографии

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

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

Продолжаю…

Отправитель, получатель и злоумышленник

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

Сообщения и шифрование

Само сообщение называется открытым текстом . Изменение вида сообщения так, чтобы спрятать его суть называется шифрованием. Шифрованное сообщение называется шифротекстом (шифрограммой). Процесс преобразования шифротекста в открытый текст называется дешифрированием.

Или, изображая графически

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

Обозначим шифротекст как С (от ciphertexеt). Это тоже двоичные данные, иногда того же размера, что и M, иногда больше. (Если шифрование сопровождается сжатием, С может быть меньше чем M. Однако, само шифрование не обеспечивает сжатие информации.) Функция шифрования E действует на M, создавая С. Также обозначим процесс дешифрования через D (decrypt, дешифрование).Или, в математической записи:

E(M) = С

В обратном процессе функция дешифрирования D действует на С, восстанавливая M:

D(C) = M

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

D(E(M)) = M

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

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

Неотрицание авторства. Отправитель не сможет ложно отрицать отправку сообщения.

Алгоритмы и ключи

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

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

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

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

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

Е_К(М)=С

D_K(C)=M

При этом выполняется следующее равенство:

D_K(E_K(M))=M

Для некоторых алгоритмов при шифровании и дешифрировании используются различные ключи (рис № 3)To есть ключ шифрования, К₁, отличается от соответствующего ключа дешифрирования, К₂. В этом случае:

Е_К1/М)=С D_K2(C)=M

В_Кг(Е_к(М))=М

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

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

Или, в случае использования 2-х ключей:

Симметричные алгоритмы

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

Е_К(М)=С D_K(C)=M

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

Алгоритмы с открытым ключом

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

Е_К(М)=С

Хотя открытый и закрытый ключи различны, дешифрирование с соответствующим закрытым ключом обoзначается как:

D_k (C)=M

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

Е_К(М)=С D_K(C)=M

Криптоанализ

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

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

Попытка криптоанализа называется вскрытием. Основное предположение криптоанализа, впервые сформулированное в девятнадцатом веке Датчманом А. Керкхофсом (Dutchman A. Kerckhoffs), состоит в том, что безопасность полностью определяется ключом. Керкхофс предполагает, что у криптоаналитика есть полное описание алгоритма и его реализации. (Конечно же, у ЦРУ не в обычае сообщать Моссад о своих криптoграфических алгоритмах, но Моссад возможно все равно добудет их .) Хотя в реальном мире криптоаналитики не всегда обладают подробной информацией, такое предположение является хорошей рабочей гипотезой . Если противник не сможет взломать алгоритм, даже зная, как он работает, то тем более враг не сможет вскрыть алгоритм без этого знания.

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

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

2. Вскрытие с использованием открытого текста

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

3. Вскрытие с использованием выбранного открытого текста

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

4. Адаптивное вскрытие с использованием открытого текста

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

5. Вскрытие с использованием выбранного шифротекста

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

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

6. Вскрытие с использованием выбранного ключа

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

7. Бандитский криптоанализ.

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

Безопасность алгоритмов

Различные алгоритмы предоставляют различные степени безопасности в зависимости от того, насколько трудно взломать алгоритм. Если стоимость взлома алгоритма выше, чем стоимость зашифрованных данных, вы, скорее всего, в безопасности. Если время взлома алгоритма больше, чем время, в течение которого зашифрованные данные должны сохраняться в секрете, то вы также, скорее всего, в безопасности . Если объем данных, зашифрованных одним ключом, меньше, чем объем данных, необходимый для взлома алгоритма, и тогда вы, скорее всего, в безопасности."Cкорее всего", потому что существует вероятность новых прорывов в криптоанализе. С другой стороны, значимость большинства данных падает со временем. Важно, чтобы значимость данных всегда остaвалась меньше, чем стоимость взлома системы безопасности, защищающей данные .

Типы вскрытия алгоритмов по следующим категориям, приведенным в пoрядке убывания значимости :

Полное вскрытие. Криптоаналитик получил ключ, К, такой, что D_K(C) = Р.

Глобальная дедукция. Криптоаналитик получил альтернативный алгоритм, А, эквивалентный D_K(C) без знания К.

Местная (или локальная)дедукция. Криптоаналитик получил открытый текст для перехваченного шифротекста.

Информационная дедукция. Криптоаналитик получил некоторую информацию о ключе или открытом тексте. Такой информацией могут быть несколько бит ключа, сведения о форме открытого текста и так далее.

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

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

Сложность данных. Объем данных, используемых на входе операции вскрытия.

Сложность обработки. Время, нужное для проведения вскрытия. Часто называется коэффициентом работы.

Требования к памяти. Объем памяти, необходимый для вскрытия.

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

Сложность выражается порядком величины. Если сложность обработки для данного алгоритма составляет 2¹²⁸, то 2¹²⁸ операций требуется для вскрытия алгоритма. (Эти операции могут быть сложными и длительными.) Так, если предполагается, что ваши вычислительные мощности способны выполнять миллион операций в сeкунду, и вы используете для решения задачи миллион параллельных процессоров, получение ключа займет у вас свыше 10¹⁹ лет, что в миллиард раз превышает время существования вселенной. Однако неутешительно...Но! В то время, как сложность вскрытия остается постоянной (пока какой-нибудь криптоаналитик не придумает лучшего способа вскрытия), мощь компьютеров растет. За последние полвека вычислительные мощности фeноменально выросли, и нет никаких причин подозревать, что эта тенденция не будет продолжена. Многие криптографические взломы пригодны для параллельных компьютеров: задача разбивается на миллиарды маленьких кусочков, решение которых не требует межпроцессорного взаимодействия. Объявление алгоритма безопасным просто потому, что его нелегко взломать, используя современную технику, в лучшем случае ненадежно. Хорoшие криптосистемы проектируются устойчивыми к взлому с учетом развития вычислительных средств на много лет вперед.

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

Вскрытие шифра простой замены

Разберем пример. Итак, допустим, на доске объявлений, появилась следующая надпись:

ТБПО ЩИЧЧЖ ЛНИЬЕЭФЭЕЭВЬ ЭКМНИО ИЩЩСКИЬОЭСФБИТЬЛИЬШ ТБПОЧЩЬП ЛНОЭЧЖ Ь ЧЛЭПЛКПЕПООЭ

ЛЭНЛКИВИЫП ФЭБСТПООЖП ЬН ЩИЧЧЖ ЧЧСУЖ

Несомненно, что это шифр. Каков же его тип? Это не может быть шифр перестановки, так как в шифровке четко проглядываются слова с регулярными окончаниями чж, иыи, оэ. Частоты встречи различных знаков шифровки явно неодинаковы. Знаки Ч, И, Э встречаются раз по десять, тогда как У, Ю и М лишь по одному разу, что не бывает в многоалфавитных шифрах, имеющих близкие вероятности знаков.Естественно предположить, что применен шифр простой замены. С чего следует начать расшифровывание? Несомненно, с установления отправителя и получателя сообщения. Вспомним рассуждения Холмса из "Пляшущих человечков", который сразу же отождествил смешную надпись с шифровкой. Что в этой надписи могло напугать героиню, угроза? Представим, что она прочла текст: "Готовься к смерти". Не правда ли, такое неприятное сообщение слишком абстрактно, чтобы заставить ужаснуться спокойного волевого человека: кто должен готовиться и к чьей смерти? Поэтому решил Холмс, героиню напугало собственное имя и начал расшифровку отождествлением слова "Илей" с первыми четырьмя человечками. Зачастую, кроме имени получателя сообщения содержат еще и имя отправителя, как это принято в телеграммах: "Приезжаю шестого. Мама." У нашей шифровки была приписка: "Граждане, ознакомившиеся, запомнившие и исполнившие, принимаются ежедневно и без ограничений. Местком." Из нее ясен отправитель - местком. Поэтому шифрованный текст может не содержать его названия. Получатель все же должен быть доуточнен, как обращение: "всем садоводам..." или "члены кружка...". Однако это - слишком легкий путь. и предположим, что не удалось конкретизировать получателя, чтобы, используя его имя, вскрыть шифр.

Предположение 1. Внимательно просматривая шифровку, можно обнаружить интересное удвоение знака Ч в конце последнего слова и начале последнего: щиччх ЧЧСУХ. Кажется, что этот знак весьма похож на употребление буквы С в русском тексте, как МАССА ССЫЛОК или ЛАССО ССУЧИЛ. Например, для буквы В не удается подобрать хороший пример, чтобы она удваивалась в конце слов, а для буквы Н - в начале. Отметим, что удвоение С в конце характерно для заимствованных существительных, где перед ним стоит чаще всего буква А. Значит, буква шифровки Ч соответствует в тексте С, а И соответствует русской букве А.

Предположение 2. Другое удвоение, знака о, встречается только в конце слов и типично для русской буквы Н. Поэтому сочетания знаков на концах слов шифровки ОЭ и ооэ, скорее всего отвечают русским окончаниям в сообщении НО и ННО. Если это так, то последнее слово шифровки ЧЧСУЖ, начинающееся с СС и состоящее из пяти букв может быть лишь одним из двух слов - ССУДЕ или ССУДЫ, что легко проверить по словарю. Другие варианты прочтения ССУДА, ССОРА и тому подобные отпадают, так как буквы А иО уже разгаданы.

Предположение 3. Знак шифровки ж, стоящий в конце слова ЧЧСУЖ встречается довольно редко, если учесть, что слово щиччж повторяется, а одинаковое окончание последнего и предпоследнего слов представляет собой обычное согласование слов в предложении. Это означает, что знаку ж скорее отвечает буква Ы, чем более часто встречаемая в русских текстах Е, а последнее слово - ССУДЫ. Окончание сообщения ?АССЫ ССУДЫ теперь нетрудно отгадать как КАССЫ ССУДЫ, что весьма близко к осмысленному тексту. Из отгадан- ных букв пятое слово шифровки складывается как АККУ?А?НО, что несомненно означает АККУРАТНО, а седьмое слово ??НОСЫ из контекста можно понять как ВЗНОСЫ. Итак, отгадывание идет вроде бы успешно, что подтверждается частичной расшифровкой:

???Н КАССЫ ВЗА??0?0?0?? 0??ЗАН АККУРАТ-НО У??А??ВАТ? ???НСК?? ВЗНОСЫ ?СВО?ВР???ННО ВОЗВРА?АТ? ?0?У??ННЫ? ?3КАССЫ ССУДЫ

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

ЧЛЕН КАССЫ ВЗАИМОПОМОЩИ ОБЯЗАНАККУРАТНО УПЛАЧИВАТЬ ЧЛЕНСКИЕВЗНОСЫ И СВОЕВРЕМЕННО ВОЗВРАЩАТЬПОЛУЧЕННЫЕ ИЗ КАССЫ ССУДЫ

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

Лучше всего на него ответить словами Архимеда из послания к Эратосфену: "Хотя это всем вышеприведенным рассуждением и не доказано, но все же производит впечатление, что окончательный вывод верен".По ряду свидетельств, опытные криптоаналитики читают такие шифровки "с листа", потратив на это минуту-другую, что свидетельствует о профессиональном видении структуры текста в кажущейся мешанине букв. В этом они сильно превосходят компьютер, которая удовлетворительно читает шифр простой замены лишь при достаточно большой длине сообщения больше сотни символов. Однако и здесь компьютер может серьезно помочь в раскалывании шифра, например, разделив буквы на гласные и согласные. Так как гласные и согласные имеют тенденцию чередоваться, то можно по матрице чередований символов разделить их на эти классы (для этого на компьютере криптоаналитики традиционно используют так называемое сингулярное разложение матрицы переходных вероятностей.). Кроме того, можно программно оценить вероятности принадлежности символов шифра разным буквам выписать их столбцами по убыванию вероятности, что даст другую технику вскрытия этого шифра. Применение распознавания, основанного на оценке лишь вероятностей отдельных символов в тексте и биграмм, за 10 этапов обучения дало по приведенной шифровке следующий текст:

ЧРЕН КАССЫ ВЗАИМОПОМОБИ ОДЯЭАН АККУЛАТНОУПРАЧИВАТЬ ЧРЕНСКИЕ ВЫНОСЫ И СВОЕВЛЕМЕННОВОЗВЛАБАТЬ ПОРУЧЕННЫЕ ИЗ КАССЫ ССУШ

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

После корректировки написания по словарю русского языка, он приобрел такой вид:

ЧЛЕН КАССЫ ВЗАИМОПОМОЩИ ОБЯЗАН АККУРАТНОУПРОЧИВАТЬ ЧЛЕНСКИЕ ВЫНОСЫ И СВОЕВРЕМЕННОВОЗВРАЩАТЬ ПОРУЧЕННЫЕ ИЗ КАССЫ ССУДЫ

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

Ну и в догонку

Взлом многоалфавитных шифров

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

Ключ	???????????????????
вариант 0	ФПЖИСЬИОССАХИЛФИУСС
вариант 1	УОЕЗРЫЗНРР ФЗКУЗТРР
вариант 2	ТНДЖПЪЖМППЯУЖЙТЖСПП
вариант 3	СМГЕОЩЕЛООЮТЕИСЕРОО
вариант 4	РЛВДНШДКННЭСДЗРДПНН
вариант 5	ПКБГМЧГЙММЬРГЖПГОММ
вариант 6	ОЙАВЛЦВИЛЛЫПВЕОВНЛЛ
вариант 7	НИ БКХБЗККЪОБДНБМКК
вариант 8	МЗЯАЙФАЖЙЙЩНАГМАЛЙЙ
вариант 9	ЛЖЮ ИУ ЕИИШМ ВЛ КИИ
сообщение	???????????????????

Предположение 1. Если прочесть исходный текст напрямую не удалось, то попробуем немного порасуждать. Самый частый символ текста - пробел, а разбиение фразы на слова порой может оказать большую помощь в расшифровке, как это уже было в случае вскрытия шифра решетки. Так как длина шифровки равна 19 символам, то она состоит из двух или трех слов, разделенных пробелами. Хорошее положение для пробела дает лишь вариант 1, а другие варианты, 7 и 9 или их сочетания маловероятны. Поэтому будем считать, что текст шифровки разбивается на два слова: ФПХИСЫЮСС ХИЛФИУСС. Из этого следует, что в 11 позиции текста стоит пробел и в той же позиции ключа находится цифра 1.

Предположение 2. У выделенных слов шифровки одинаковое окончание ее, и, весьма вероятно, что период ключа делит 9 - длину второго слова вместе с пробелом. Будем считать, что в этом случае одинаковые окончания слов (Одинаковые окончания часто появляются из-за согласования слов в предложениях на русском языке. Это хорошо видно в поговорках: одИН в поле не воИН, наняЛСЯ - продаЛСЯ.) текста попали на одинаковые участки ключа и дали одинаковые символы шифровки. На первый взгляд может показаться, что это слишком маловероятно, чтобы встречаться в практике. Однако таких находок, помогающих расшифровке, всегда бывает предостаточно в сообщениях большой длины и, порой, приходится жалеть скорее об их обилии, чем отсутствии. Если нет никаких идей о длине ключа, не беда - ее можно подобрать вслепую. Итак, есть два выбора для периода ключа: 3 и 9. Попробуем период длины 3:

ключ	?1??1??1??1??1??1??
вариант 0	Ф ЖИ ЬИ СС ХИ ФИ СС
вариант 1	УОЕЗРЫЗНРР ФЗКУЗТРР
вариант 2	Т ДЖ ЪЖ ПП УЖ ТЖ ПП
вариант 3	С ГЕ ЩЕ ОО ТЕ СЕ ОО
вариант 4	Р БД ШД НН СД РД НН
вариант 5	П БГ ЧГ ММ РГ ПГ ММ
вариант 6	О АВ ЦБ ЛЛ ПВ ОВ ЛЛ
вариант 7	Н Б ХБ КК ОБ НБ КК
вариант 8	М ЯА ФА ЙЙ НА МА ЙЙ
вариант 9	Л Ю У ИИ МЛ ИИ
сообщение	?о??р??н?? ??к??т??

Таблица существенно поредела, но остается все-таки сложной для непосредственного прочтения (Криптоаналитики вряд ли сочтут прямое чтение ее сложным, так как достаточно перебрать лишь 100 вариантов для двух оставшихся цифр ключа вручную за несколько минут.). Поэтому попробуем подобрать символ ключа, стоящий в первой позиции, перебрав 10 вариантов. Так как ключ длиной 3 циклически повторяется, то этот же символ стоит в 4, 7, 10, 13, 16 и 19 позициях ключа. Вероятность варианта для первой цифры ключа равна произведению вероятностей биграмм, состоящих из символа по этому варианту расшифровки и следующего за ним, уже известного символа. Если Li - буква текста, стоящая на месте i, то вероятность одного из 10 вариантов:р (L1L2) p(L4L5) р(L7L8) p(L10L11) p(L13L14) p(L16L17)

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

р(0)=р(ФО)р(ИР)р(ИН)р(С )р(ИК)р(ИТ)=43р(1)=р(УО)р(ЗР)р(ЗН)р(Р )р(ЗК)р(ЗТ)=23р(2)=р(ТО)р(ЖР)р(ЖН)р(П )р(ЖК)р(ЖТ)=27р(3)=р(СО)р(ЕР)р(ЕН)р(О )р(ЕК)р(ЕТ)=50

В результате для первой цифры ключа получается наиболее вероятным 3 вариант расшифровки. Это дает следующую таблицу:

ключ	31?31?31?31?31?31?3
вариант 0	Ж Ь С Х Ф С
вариант 1	ОЕ РЫ HP Ф КУ ТР
вариант 2	Д Ъ П У Т П
вариант 3	С ГЕ ЩЕ ОО ТЕ С ОО
вариант 4	в т н с р н
вариант 5	Б Ч М Р П М
вариант 6	А Ц Л П О Л
вариант 7	Х К О Н К
вариант 8	Я Ф Й Н М Й
вариант 9	Ю У И М Л И
сообщение	СО?ЕР?ЕН?0 ?ЕК?РТ?0

Теперь сообщение читается совсем просто. Достаточно выбрать одну из 10 строк с вариантом для 3 цифры ключа. В результате получим ключ и текст сообщения:сообщение: СОВЕРШЕННО СЕКРЕТНОключ: 3143143143143143143

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

Шифровка	ДДЯ Л ЫСЫ ШНМРКЮЮЩДБЬИЬМЫМТАНЭХЦК
Сообщение	????????????????????????? ТРОЦКИЙ
Ключ	?????????????????????????НАС ЗЛОБ

Не напоминает ли фрагмент НАС ЗЛОБ какой-то известный текст? Не правда ли, очень похоже на слова, переведенной Кржижановским песни польского восстания 1863 года, называемой "Варшавянкой"? Теперь, подставив разгаданный ключ в виде текста песни: ВИХРИ ВРАЖДЕБНЫЕ ВЕЮТ НАД НАМИ ТЕМНЫЕ СИЛЫ НАС ЗЛОБ, можно вскpыть само сообщение:ОБЫВАТЕЛИ СПАЛИ НЕ ЗНАЯ ЧТО МЕНЯЕТСЯ ВЛАСТЬ ТРОЦКИЙ

Такая расшифровка вряд ли заняла бы вместе с составлением сопроводительной записки более часа времени. Ну, а предположим, что отправитель неизвестен? И это не беда, хотя потребует больше времени. Несложно перебрать несколько возможных имен, а в случае неудачи придется подставлять в разные места часто употребляемые слова текста и ключа - ТОВАРИЩ, ВЛАСТЬ, ВОССТАНИЕ. Отгадав одно из двух - текст или ключ, сразу получим второе.Мда неприятная вырисовывается картина однако…. Сразу становится как-то не по себе … получается что вскрывают чаще и проще чем можно подумать…Но унывать не стоит- забегая вперед, скажу что есть нескрываемая системы криптографии- т.н. одноразовый блокнот, и в конце концов вскрыть 512 битовый клоч не так то уж легко и быстро… Но об этом позже….

А теперь настало время самой "труднопроходимой" части. Догадались? Правильно- на сцену выходить её величество-математика, точнее

Теория информации

Современная теория информации впервые была опубликована в 1948 году Клодом Э. Шенноном (Claude Elmwood Shannon).

Энтропия и неопределенность

Теория информации определяет количество информации в сообщении как минимальное количество бит, необходимое для кодирования всех возможных значений сообщения, считая все сообщения равновероятными. Например, для поля дня недели в базе данных достаточно использовать три бита информации, так как вся информация может быть закодирована 3 битами:

1. - Воскресенье

2. - Понедельник

010-Вторник

011 -Среда

100-Четверг

101 -Пятница

110-Суббота

111 - Не используется

Если эта информация была бы представлена соответствующими строками ASCII символов, она заняла бы больше места в памяти, но не содержала бы больше информации. Аналогично, поле базы данных "пол" содеpжит только один бит информации, хотя эта информация может храниться как одно из двух 7-байтовых ASCII строк: "МУЖЧИНА" или "ЖЕНЩИНА".

Формально, количество информации в сообщении M измеряется энтропией сообщения, обозначаемое как H(M). Энтропия сообщения, определяющего пол, составляет! бит, а энтропия сообщения, определяющего день недели, немного меньше, чем 3 бита. В общем случае энтропия сообщения, измеряемая в битах, равна log 2 n, где n - это количество возможных значений. При этом предполагается, что все значения равновероятны.

Энтропия сообщения также является мерой его неопределенности. Это количество битов открытого текста, которое нужно раскрыть в шифротексте сообщения, чтобы узнать весь открытый текст. Например, если блок шифротекста "QHP*5M " означает либо "МУЖЧИНА", либо "ЖЕНЩИНА", то неопределенность сообщения равна 1. Криптоаналитику нужно узнать только один правильно выбранный бит, чтобы раскрыть сообщение.

Норма языка

Для данного языка норма языка равна

r = H(M)/N

где N - это длина сообщения. При больших N норма обычного английского языка принимает различные зонaчения от 1.0 бит/буква до 1.5 бит/буква. Шеннон утверждает, что энтропия зависит от длины текста. Конкретно он показал, что норма для 8-буквенных блоков равна 2.3 бит/буква, но ее значение падает и находится между 1.3 и 1.5 для 16-буквенных блоков. Томас Кавер (Thomas Cover) использовал игровую методику оценки и обнаружил, что энтропия равна 1.3 бит/символ. Я буду использовать значение 1.3 Абсолютная норма языка равна максимальному количеству битов, которое может быть передано каждым символом при условии, что все последовательности символов равновероятны. Если в языке L символов, то абсолютная норма равна:

R = log2 L

Это максимум энтропии отдельных символов.

Для английского языка с 26 буквами абсолютная норма равна log 2 26, или около 4.7 бит/буква. Вас не должно удивлять, что действительная норма английского языка намного меньше, чем абсолютная - естественные языки обладают высокой избыточностью. Избыточность языка, обозначаемая D, определяется как:

D=R-r

Считая, что норма английского языка равна 1.3, избыточность составит 3.4 бит/буква. Это означает, что кaждая английская буква содержит 3.4 бита избыточной информации.

У сообщения ASCII, состоящего только из английских букв, количество информации на каждый байт составляет 1.3 бита. Значит, в каждом байте содержится 6.7 бита избыточной информации, что дает общую избыточность 0.84 бита информации на бит ASCII-текста и энтропию 0.16 бита информации на бит ASCII-текста. To же сообщение, набранное кодом BAUDOT, с 5 битами на символ, имеет избыточность 0.74 бита на бит и энтрoпию 0.26 бита на бит. Пробелы, пунктуация, числа и форматирование изменяют эти результаты.

Расстояние уникальности

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

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

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

U = H(K)/D

Расстояние уникальности является не точным, а вероятностным значением. Оно позволяет оценить минимальное количество шифротекста, при вскрытии которого грубой силой имеется, вероятно, только один разумный способ дешифрирования. Обычно чем больше расстояние уникальности, тем лучше криптосистема. Для DES с 56-битовым ключом и англоязычного сообщения, записанного символами ASCII, расстояние уникальности приблизительно равно 8.2 символа ASCII или 66 бит. В приведены расстояния уникальности для различных длин ключа.

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

Табл. 1. Расстояния уникальности текста ASCII, зашифрованного алгоритмами с различной длиной ключа

Длина ключа (в битах) Расстояние уникальности (в символах)

40 5^9

56 8.2

64 9.4

80 11.8

128 18.8

256 37.6

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

Путаница и диффузия

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

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

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

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

Арифметика вычетов

Вы все учили математику вычетов в школе.Если Маша сказaла, что она будет дома к 10:00, и опоздала на 13 часов, то когда она придет домой, и на сколько лет отец лишит ее водительских прав? Это арифметика по модулю 12. Двадцать три по модулю 12 равно 11.

(10 + 13) mod 12 = 23 mod 12 = 11 mod 12

Другим способом записать это является утверждение об эквивалентности 23 и 11 по модулю 12:

10+13 = ll(modl2)

В основном, а = b (mod n), если а = b + kn для некоторого целого k. Если а неотрицательно и b находится между 0 и и, можно рассматривать b как остаток при делении а на п. Иногда, b называется вычетом а по модулю п. Иногда а называется конгруэнтным b по модулю n (знак тройного равенства, =, обозначает конгруэнтность). Одно и то же можно сказать разными способами.

Множество чисел от 0 до n-\ образует то, что называется полным множеством вычетов по модулю п. Это означает, что для любого целого а, его остаток по модулю n является некоторым числом от 0 до n-1.

Операция a mod n обозначает остаток от а, являющийся некоторым целым числом от 0 до n-1. Эта операция называется приведением по модулю. Например, 5 mod 3 = 2.

Это определение mod может отличаться от принятого в некоторых языках программирования. Например, оператор получения остатка в языке PASCAL иногда возвращает отрицательное число. Он возвращает число между -(и-1) и n-\. В языке С оператор % возвращает остаток от деления первого выражения на второе, оно может быть отрицательным числом, если любой из операндов отрицателен. Для всех алгоритмов, проверяйте, что вы добавляете n к результату операции получения остатка, если она возвращает отрицательное число.

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

(а + b) mod n == ((a mod ri) + (b mod и)) mod n

(а - b) mod n == ((a mod и) - (b mod и)) mod n

(а * b) mod n == ((a mod ri) * (b mod и)) mod n

(а * (b+c)) mod n == (((a*b} mod ri} + ((a*c) mod и)) mod n

Вычисление mod n часто используется в криптографии, так как вычисление дискретных логарифмов и квадратных корней mod n может быть нелегкой проблемой. Арифметика вычетов, к тому же, легче реализуется на компьютерах, поскольку она ограничивает диапазон промежуточных значений и результата. Для k-битовых вычетов n, промежуточные результаты любого сложения, вычитание или умножения будут не длиннее, чем 2 k бит. Поэтому в арифметике вычетов мы можем выполнить возведение в степень без огромных промежуточных peзультатов. Вычисление степени некоторого числа по модулю другого числа,

a^x mod n,

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

Например, если вы хотите вычислить a⁸ mod n, не выполняйте наивно семь умножений и одно приведение по модулю:

(a * a * a * a * a * a * a * a) mod n

Вместо этого выполните три меньших умножения и три меньших приведения по модулю:

((a² mod n)² mod n)² mod n

Точно также,

a¹⁶ mod n =(((a² mod n)² mod n)² mod n)² mod n

Вычисление a^x, где x не является степенью 2, ненамного труднее. Двоичная запись представляет x в виде суммы степеней 2: 25 - это бинарное 11001, поэтому 25 = 24 + 23 + 20. Поэтому

a²⁵ mod n = (a*a²⁴) mod n = (a* a^S*a¹⁶) mod n =

= (a*(( a²)²)²*((( a²)²)²)²) mod n = (a*((( a*a²)²)²)²) mod n

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

(((((((a² mod ri}* a)² mod и)² mod и)² mod и)² mod и)² *a) mod n

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

unsigned long qe2(unsigned long x, unsigned long у, unsigned long n) {

unsigned long s, t, u;

int i;

s=l; t=x; u=y;

while (u) {

if(u&l) s=(s*t)%n; u>>l;

t=(t*t)%n;

}

return(s)

}

А вот другой, рекурсивный, алгоритм:

unsigned long fast_exp(unsigned long x, unsigned long у, unsigned long N)

{

unsigned long tmp;

if(y==l) return(x % N);

if (l^(x&l)) {

tmp= fast_exp(x,y/2,N);

return ( (tmp*tmp) %N) ;

else {

tmp = fast_exp(x,(y-l)/2,N);

tmp = (tmp*tmp) %N;

tmp = (tmp*x)%N;

return (tmp) ;

}

return 0;

Этот метод уменьшает количество операций, в среднем, до 1.5* k операций, где k - длина числа x в битах. Найти способ вычисления с наименьшим количеством операций - трудная проблема (было доказано, что послeдовательность должна содержать не меньше k- \ операций), но нетрудно снизить число операций до 1 . 1 * k или даже лучше при больших k.

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

Простые числа

Простым называется целое число, большее единицы, единственными множителями которого является 1 и оно само: оно не делится ни на одно другое число. Два - это простое число. Простыми являются и 73, 2521, 2365347734339 и 2^75б839-1. Существует бесконечно много простых чисел. Криптография, особенно криптография с открытыми ключами, часто использует большие простые числа (512 бит и даже больше).

Наибольший общий делитель

Два числа называются взаимно простыми, если у них нет общих множителей кроме 1 . Иными словами, e c-ли наибольший общий делитель а и n равен 1 . Это записывается как:

НОД(а,и)=1

Взаимно просты числа 15 и 28. 15 и 27 не являются взаимно простыми, а 13 и 500 - являются. Простое число взаимно просто со всеми другими числами, кроме чисел, кратных данному простому числу.

Одним из способов вычислить наибольший общий делитель двух чисел является алгоритм Эвклида. Эвклид описал этот алгоритм в своей книге, Элементы, написанной в 300 году до нашей эры. Он не изобрел его. Историки считают, что этот алгоритм лет на 200 старше. Это самый древний нетривиальный алгоритм, который дошел до наших дней, и он все еще хорош. Кнут описал алгоритм и его современные модификации в [863]. На языке С:

/* возвращает НОД (gcd) x и у */

int gcd (int x, int у) {

int g;

if (x < 0)

if (у < 0)

у = -у;

if (x + у == 0 ) ERROR ;

g = у;

while (x > 0) { g = x;

x = у % x;

у = g;

}

return g;

}

Обратные значения по модулю

Помните, что такое обратные значения? Обратное значение для 4 - 1/4, потому что 4*1/4 =1. В мире вычетов проблема усложняется:

4*;c = 1 (mod 7)

Это уравнение эквивалентно обнаружению x и k, таких что

4x = lk+l

где x и k - целые числа. Общая задача состоит в нахождении x, такого что

1 = (a*x) mod n

Это также можно записать как

а"¹ =x (mod w)

Проблему обратных значений по модулю решить нелегко. Иногда у нее есть решение, иногда нет. Например, обратное значение 5 по модулю 14 равно 3. С другой стороны у числа 2 нет обратного значения по модулю 14.

В общем случае у уравнения а"¹ = x (mod ri) существует единственное решение, если a и n взаимно просты. Если a и n не являются взаимно простыми, то а"¹ = x (mod ri) не имеет решений. Если n является простым числом, то любое число от 1 до n -1 взаимно просто с n и имеет в точности одно обратное значение по модулю п.

Так, хорошо. А теперь как вы собираетесь искать обратное значение a по модулю и? Существует два пути. Обратное значение а по модулю n можно вычислить с помощью алгоритма Эвклида. Иногда это называется расширенным алгоритмом Эвклида.

Вот этот алгоритм на языке С++:

#define isEven(x) ((x & 0x01) == 0)

#define isOdd(x) (x& 0x01)

#define swap(x,y) (x^= у, y^= x, x^= у)

void ExtBinEuclid(int *u, int *v, int *ul, int *u2, int *u3) {

// предупреждение: u и v будут переставлены, если u<v int k, tl, t2, t3;

if (*u < *v) swap(*u<,*v);

for (k = 0; isEven(*u) && isEven(*v); ++k) {

*u>>=l; *v »1;

}

*ul = 1; *u2 = 0; *u3 = *u; tl = *v; t2 = *u - 1; t3 = *v;

do {

do {

if (isEven(*u3)) {

if (isOdd(*ul) || isOdd(*u2)) {

*ul += *v; *u2 += *u;

} *ul »* 1; *u2 »= 1; *u3 »= 1;

}

if (isEven(t3) II *u3 < t3) { swap(*ul,tl); smap(*u2,t2); smap(*u3,t3);

}

} while (isEven(*u3)); while (*ul < tl || *u2 < t2) { *ul += *v; *u2 += *u; }

ul -= tl; *u2 -= t2; *u3 -= t3; } while (t3 > 0) ;

while (*ul >= *v && *u2 >= *u) { *ul>l -= *v; *u2 -= *u;

}

*u «= k; *v «= k; *u3 « k; }

main(int argc, char **argv) { int a, b, gcd; if (argc < 3) {

cerr « "как использовать: xeuclid u v" « endl; return -1;

}

int u = atoi(argv[l]); int v = atoi(argv[2]); if (u <= 0 || v <= 0 ) {

cerr « "Аргумент должен быть положителен'" « endl; return -2;

}

// предупреждение: u и v будут переставлены если u < v

ExtBinEuclid(&u, &v, &a, &b, &gcd); cout « а «" * " « u « " + (-" « b « ") * " « v « " = " « gcd « endl; if (gcd == 1)

cout « "Обратное значение " « v « " mod " « u « " is: « u - b « endl;

return 0;

Я не собираюсь доказывать, что это работает, или приводить теоретическое обоснование.

Алгоритм итеративен и для больших чисел может работать медленно.

Решение для коэффициентов

Алгоритм Эвклида можно использовать и для решения следующих проблем: дан массив из т переменных

Xi, х₂,..., х_т, найти массив т коэффициентов, u\, и₂,..., и_т, таких что

Mi * Xi+...+ U_m * Х_т, = 1

Малая теорема Ферма

Если т - простое число, и а не кратно т, то малая теорема Ферма утверждает а^тЛ = 1 (mod m)

(Пьер де Ферма (Pierre de Fermat), французский математик, жил с 1601 по 1665 год. Эта теорема не имеет ничего общего с его знаменитой теоремой.)

Функция Эйлера

Существует другой способ вычислить обратное значение по модулю n, но его не всегда возможно использoвать. Приведенным множеством остатков mod n называется подмножество полного множества остатков, члeны которого взаимно просты с п. Например, приведенное множество остатков mod 12 - это {1, 5, 7, 11}. Если n -простое число, то приведенное множество остатков mod n - это множество всех чисел от 1 до n-\. Для любого n, не равного 1,число 0 никогда не входит в приведенное множество остатков.

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

Если n - простое число, то ф(n) = n-\. Если n =pq, где р и q -простые числа, то ф(n)= (p - \)(q - 1). Эти числа появляются в некоторых алгоритмах с открытыми ключами, и вот почему. В соответствии с обобщением Эйлepa малой теоремы Ферма, если НОД(а,n) = 1, то

a ^ф(n) mod n = 1

Теперь легко вычислить а^-1 mod n:

x = a ^ф(n)-1 mod n

Например, какое число является обратным для 5 по модулю 7? Так как 7 - простое число, ф(7) = 7 - 1 = 6. Итак, число, обратное к 5 по модулю 7, равно

5⁶'¹ mod 7 = 5⁵ mod 7 = 3

Эти методы вычисления обратных значений можно расширить для более общей проблемы нахождения x (если НОД(а,n)= 1):

(a*x) mod n = b