WWW.LIBRUS.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - собрание публикаций
 

«ПО АРИФМЕТИЧЕСКИМ ВОПРОСАМ КРИПТОГРАФИИ Москва УДК 511 Минеев М. П., Чубариков В. Н. Лекции по арифметическим вопросам криптографии. — М.: Издво «Попечительский совет ...»

М. П. Минеев, В. Н. Чубариков

ЛЕКЦИИ

ПО АРИФМЕТИЧЕСКИМ

ВОПРОСАМ

КРИПТОГРАФИИ

Москва

УДК 511

Минеев М. П., Чубариков В. Н .

Лекции по арифметическим вопросам криптографии. — М.: Издво «Попечительский совет Механико-математического факультета

МГУ им. М. В. Ломоносова», 2010. — 186 с .

Книга является учебным пособием по арифметическим приложениям

к криптографии. В е основу положены лекции по специальному курсу е и занятия специального семинара, проводимые авторами на механикоматематическом факультете МГУ имени М. В. Ломоносова .

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

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

УДК 511 М. П. Минеев, 2010 c В. Н. Чубариков, 2010 c

ПРЕДИСЛОВИЕ

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

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

Во второй мировой войне “советская шифровальная служба в основном учла опыт своей российской предшественницы времен первой мировой войны”. Известный специалист в области истории криптографии Д. Кан [19] писал: “Немецкая радиоразведка против Советского Союза была малоэффективной. В стратегическом отношении она вообще не имела ни одного сколько-нибудь заметного успеха .

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

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

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

Широкое распространение компьютеров, бурное развитие информационных технологий и внедрение автоматизированных методов и средств обработки информации практически во все сферы человечеПредисловие ской деятельности в 60-х годах привели к необходимости массового использования криптографических средств и постановке новых задач защиты информации в цифровой форме. В частности, А. Н. Колмогоров [23] ввел понятие “битовой” сложности для последовательностей, составленных из нулей и единиц, и понятие сложности выполнения арифметических операций над натуральными числами .





До сих пор остается нерешенной проблема А. Н. Колмогорова о том, что операция умножения двух многозначных чисел сложнее операции сложения их. В 1961 г. А. А. Карацуба [20] доказал замечательную теорему о том, что два n-значных натуральных числа можно перемножить не за O(n2 ) битовых операций, как в “школьном” способе умножения чисел в столбик, а за число операций O(n ), где = log2 3 1, 585.... Эта теорема положила начало совершенно новому направлению в вычислительной математике — теории быстрых вычислений .

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

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

лишение пользователя санкции на использование информации .

В 1976 г. специалисты из Стэнфордского университета Диффи, Хэллман и Мркль [14] сделали выдающееся открытие. Они ввели е понятие открытого ключа и нашли новый изобретательный метод обмена ключами по открытому каналу связи, основанный на сложности нахождения значений функции “дискретный логарифм” .

В 1978 г. Ривест, Шамир и Адлеман [39] дали первый практический способ шифрования с открытым ключом, получивший в дальнейшем название RSA-метода, а также новую схему построения цифПредисловие 5 ровой подписи. Их метод шифрования полагался на сложность разложения натуральных чисел на простые сомножители .

В 1985 г. Эль-Гамаль [16] получил новый класс систем шифрования с открытым ключом, основанный на сложности нахождения дискретного логарифма .

В 1991 г. был принят первый международный стандарт цифровой подписи (ISO/IEC 9796), в основе которого лежал метод RSA. В 1991 г. правительство США приняло стандарт цифровой подписи FIPS 186 на основе схемы Эль Гамаля, а в 1994 г. был принят российский государственный стандарт ГОСТ Р34.10-94, полагающийся также на вариацию схемы цифровой подписи Эль Гамаля .

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

Указанные цели, задачи и средства криптографии потребовали введения новых и развития старых теоретико-числовых методов .

Перейдем к описанию содержания настоящей книги .

Первая глава является введением в криптографию. Здесь дано понятие информации, ее кодирование и сформулированы основные задачи теории кодирования. Далее вводится понятие алфавитного кодирования. Рассматриваются коды Шеннона и Гилберта–Мура .

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

Во второй главе изучаются свойства префиксных кодов, доказывается неравенство Крафта – МакМиллана и выводится теорема о минимальной длине префиксного кода .

Третья глава посвящена конечным полям и циклическим кодам .

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

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

В шестой главе изучаются асимметричные шифры. Вводится понятие однонаправленной функции. Решается задача “об укладке рюкзака” и дается ее применение к системе шифрования. Разбирается система RSA шифрования с открытым ключом. Рассмотрен интересный пример криптографической хэш-функции .

Наконец, седьмая глава называется “Задачи теории чисел”. Все задачи распределены по следующим разделам: квадратичные вычеты и невычеты по простому модулю, символ Лежандра; извлечение квадратного корня из числа по простому модулю; символ Якоби; извлечение квадратного корня из числа по составному модулю; целая часть квадратного корня из натурального числа; символ Кронекера;

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

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

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

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

М. П. Минеев, В. Н. Чубариков Глава I ВВЕДЕНИЕ § 1. Понятие информации и ее кодирование Важнейшей причиной возрастания интереса к теории чисел в последнее время явилось мощное развитие вычислительной техники и методов хранения, обработки, передачи, извлечения, классификации и оценки качества информации .

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

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

–  –  –

Кстати отметим, что азбука Морзе при передаче сообщения предполагает использование знака пробела между буквами, словами и предложениями, который обычно достаточно часто встречается в нем. С другой стороны, с помощью двух знаков 0 и 1 можно представить алфавит из 32 букв, не требующий обозначения пробела между буквами при передаче сообщения. Для этого достаточно рассмотреть 32 8 Глава I.

Введение двоичных слова длины 5:

(00000), (00001), (00010),..., (11111) .

Далее все сообщения будут представлены в дискретном виде, т.е .

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

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

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

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

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

В 70-е годы прошлого века в работе Диффи и Хеллмана [14] появился второй вид шифрования, называемый открытым шифрованием, которое не требует секретного распределения ключей. Новым элементом открытого шифрования является использование односторонней функции, вычисление значений которой достаточно просто, но вычисление значений обратной функции без знания некоторого “секрета” представляет собой весьма трудную задачу. Во введении § 2. Основные задачи теории кодирования 9 мы описываем одну из систем открытого шифрования — систему Ривеста–Шамира–Адлемана (систему RSA) [39] .

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

§ 2. Основные задачи теории кодирования Простейшая схема передачи сообщения (исходного текста, информации) имеет вид

–  –  –

В частности, отметим,что под помехами понимают и несанкционированный доступ к информации .

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

Пусть pt обозначает открытый текст, ct = Ek (pt) — кодированный текст, Dk (ct) = pt — декодированный текст, и элемент k принадлежит K — некоторому “пространству ключей”. Тогда процесс передачи информации можно представить более подробной схемой 10 Глава I. Введение

–  –  –

Криптоаналитик Среди основных задач теории кодирования находятся следующие .

1) Обеспечение помехоустойчивости при передаче информации по каналам связи. Отметим, что информация при прохождении по каналу связи может искажаться, поэтому ставится задача после приема ее абонентом восстановление истинной информации .

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

3) Защита информации от несанкционированного доступа при хранении и передаче ее по каналам связи, нахождение критериев надежности криптографических систем .

§ 3. Алфавитное кодирование Алфавит A представляет собой конечный набор символов (букв, знаков) (a1, a2,..., ar ), r 1. Конечный набор букв (возможно с повторением) из A называется словом в алфавите A. Множество всех слов в алфавите A обозначим символом S(A). Пусть задан другой алфавит B = {b1, b2,..., bs }, s 1 и S(B) — множество его слов .

Рассмотрим непустые подмножества M в S(A) и C в S(B). Отображение F : M C называется кодированием, при этом слова из множества M называются сообщениями, а их образы в C — кодами сообщений из M, кроме того, A называется алфавитом сообщений, а B — кодирующим алфавитом. Кодирование F (или код C) называется взаимно однозначным или однозначно декодируемым, если каждое кодовое сообщение из C имеет ровно одно сообщение из M в качестве прообраза отображения F .

Пусть задано отображение букв алфавита A в множество S(B), т.е. : ak Bk, k = 1,..., r. Определим кодирование F : S(A) S(B), удовлетворяющее следующим условиям

1) F (ak ) = Bk, k = 1,..., r;

2) F (ak1 ak2... aks ) = Bk1 Bk2... Bks, 1 k1, k2,..., ks r, s 1;

§ 3. Алфавитное кодирование 11 где под произведением слов Bk Bl понимается приписывание слова Bl справа к слову Bk. Отображение F называется алфавитным кодированием, задаваемым схемой. Множество кодовых слов {B1, B2,..., Br } обозначается символом C() и называется кодом алфавита A в схеме .

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

Пример 1. Пусть A = {a1, a2, a3 } и B = {b1, b2 } .

Пусть, также, задана схема алфавитного кодирования вида:

: a1 b1, a2 b2, a3 b2 b2 .

Тогда слово a1 a2 a3 кодируется словом b1 b2 b2 b2, которое нельзя однозначно декодировать. Если в кодовом слове расставить скобки следующим образом (b1 )(b2 )(b2 )(b2 ), (b1 )(b2 )(b2 b2 ), (b1 )(b2 b2 )(b2 ), то соответствующее сообщение будет иметь вид a1 a2 a2 a2, a1 a2 a3 или a1 a3 a2 .

Пример 2. Пусть A = {a1, a2 }, B = {b1, b2 } и : a1 b1, a2 b1 b2 .

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

Например, пусть задано кодовое сообщение C вида b1 b1 b2 b1 b2 b1 b1 b1 b2. Выделим в нем все пары b1 b2. Найдем b1 (b1 b2 )(b1 b2 )b1 b1 (b1 b2 ). Следовательно, открытое сообщение имеет вид a1 a2 a2 a1 a1 a2 .

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

Пусть сообщение C имеет вид C C. Тогда C называется префиксом или началом сообщения C, а C — суффиксом или концом сообщения C. Пустое (не содержащее букв алфавита B) сообщение и само сообщение C будем считать началом и концом сообщения C .

Начала и концы сообщения C, отличные от пустого и самого сообщения C, называются собственными префиксами и соответственно собственными суффиксами сообщения C .

Пусть, как и раньше, для любой буквы ak, k = 1,..., r из алфавита A задано отображение F (ak ) = Bk и C() = {B1,..., Br } .

12 Глава I. Введение Говорят, что схема обладает свойством префикса, если ни одно слово из C() не является префиксом никакого другого слова из C() .

Например, пусть заданы алфавиты A = {a1, a2, a3, a4 } и B = {0, 1} .

Определим схему, как отображение F (ak ) = Bk, k = 1,..., 4, где B1 = 0, B2 = 10, B3 = 110, B4 = 111. Тогда эта схема обладает свойством префикса .

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

Будем рассуждать от противного. Пусть при кодировании F : S(A) S(B) слово C не имеет однозначного декодирования, т.е .

–  –  –

Так как слова ak1 ak2... aks и al1 al2... alt различны, то при некоr, имеем ak1 = al1,..., akn1 = aln1, akn = aln .

тором n, 1 n Следовательно, Bk1 = Bl1,..., Bkn1 = Bln1, Bkn = Bln. Поскольку последние слова представляют одно и то же слово C, одно из слов Bkn или Bln является префиксом другого, что противоречит свойству префикса для схемы .

Пример 2 показывает, что свойство префикса для схемы не является необходимым для однозначного декодирования сообщения .

Пример 3. Важной задачей алфавитного кодирования является построение кода с минимальной средней длиной .

Пусть задан алфавит A = (a1,..., am ) и известны соответствующие вероятности p1,..., pm появления букв из алфавита A в открытом тексте. Пусть буквы алфавита A занумерованы по убыванию вероятностей, т.е .

p1 p2... pm. Далее вводятся величины Qs, называемые кумулятивными вероятностями, следующим образом

–  –  –

Построим код Шеннона. Кодовым словом bs в нем, отвечающим букве as, s = 1,..., m, является двоичная последовательность, представляющая собой первые ls = [ log2 ps ] + 1 знаков после запятой в двоичной записи числа Qs .

Покажем, что код Шеннона является префиксным. При r s § 3. Алфавитное кодирование 13

–  –  –

Построенные шары не пересекаются. Предположим противное .

Пусть точка = (1, 2, 3, 4, 5 ) принадлежит указанным выше шарам Bx и By. Тогда по неравенству треугольника имеем

–  –  –

делим функцию (1, 2 ) следующим образом (0, 0) = (1, 1) = 0, (0, 1) = (1, 0) = 1 .

Рассмотрим векторы X вида X = (1, 2, 1, 2, (1, 2 )), где k, k = 1, 2, принимает одно из значений 0 или 1. Векторов X будет ровно 4. Покажем, что расстояние между двумя различными векторами из них не меньше, чем 3. Рассмотрим два различных вектора X = X(1, 2 ) = (1, 2, 1, 2, (1, 2 )) и X = X (, ) = (1, 2, 1, 2, (1, 2 )). Покажем, что (X, X ) 3. Очевидно, что (1, 2 ) = (, ). Возможны только три следующих случая. Имеем a) 1 =, 2 =, тогда из определения расстояния находим (X, X ) = 4; б) 1 =, 2 =, тогда из определения расстояния получим (X, X ) = 3; в) 1 =, 2 =, тогда (X, X ) = 3 .

Следовательно, имеем (X, X ) 3 .

В заключение параграфа приведем другое доказательство неравенства треугольника. Рассмотрим множество M векторов x = (x1, x2,..., xn ) с целочисленными координатами, принимающими значения от 0 до l 1. Неотрицательное целое число (, y ), ука- x зывающее число мест, на которых находятся различные компоненты векторов x и y, удовлетворяет всем свойствам расстояния. Свойства неотрицательности и симметричности функции очевидны. Докажем неравенство треугольника для функции. Рассмотрим любые три вектора x, y и z. Разместим их друг под другом так, чтобы координаты с одинаковыми номерами находились в одном столбце. Перемена мест столбцов не меняет значение функции. Если у двух векторов координаты с одинаковыми номерами i не совпадают, то будем обозначать их так: i, i. Пусть (, y ) = k. Поменяем коордиx натные столбцы для векторов x, y, z так, что получилась следующая таблица

–  –  –

Тем самым установлено неравенство треугольника для функции .

§ 5. Об увеличении скорости передачи информации 17 § 5 .

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

Поясним суть данного эффекта на известном простом примере .

Суть его такова [3, с. 18–22]. Пусть задана информация, составленная из четырех сообщений A1, A2, A3, A4, некоторой длины и вероятности их появления в тексте равны P (A1 ) = 1/2, P (A2 ) = 1/4, P (A3 ) = P (A4 ) = 1/8 .

Указанные сообщения можно закодировать двоичными словами длины 2 следующим образом:

( ) A1 A2 A3 A4 .

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

–  –  –

и 125 3 символов и, наконец, 125 сообщений A4 и 125 3 символов. Таким образом указанный способ кодирования потребует 500 1 + 250 2 + 125 3 + 125 3 = 1750 символов и средняя длина кодового слова 1,75 символа .

С другой стороны, способ кодирования, не учитывающий вероятности сообщений, более точно, рассматривающий равномерное распределение сообщений A1, A2, A3, A4 в тексте из 1000 слов, требует для кодирования информации 1000 2 = 2000 символов и средняя длина кодового слова равна 2 .

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

Приведем еще один пример кода Фано. Пусть алфавит сообщения состоит из восьми букв.

Каждая буква сообщения встречается со следующими вероятностями:

P (a1 ) = 0,3, P (a2 ) = P (a3 ) = P (a4 ) = 0,15, P (a5 ) = P (a6 ) = P (a7 ) = 0,07, P (a8 ) = 0,04 .

Кодирующий алфавит состоит из трех символов {0, 1, 2}. Расположим буквы в порядке убывания вероятностей в сообщении. Затем все буквы алфавита разбиваем на три группы с приблизительно одинаковой вероятностью их появления в сообщении. Кодирование производим следующим образом. В первую группу попала одна буква a1. Ее кодируем символом 0. Каждую букву второй группы — a2, a3 — кодируем символом 1. Буквы a4, a5, a6, a7, a8, попавшие в третью группу, кодируем символом 2. Далее с получившимися группами поступаем аналогичным образом. Первая группа, состоящая из одной буквы, из дальнейшего кодирования исключается. Во второй группе букве a2 присваиваем следующий кодовый символ 0, а букве a3 — символ 1, и прекращаем кодирование букв второй группы. Третью группу букв разбиваем на три подгруппы {a4 }, {a5, a6 } и {a7, a8 } с приблизительно равными вероятностями. Буквам первой подгруппы присваиваем кодовый символ 0, буквам второй — символ 1, наконец, буквам третьей подгруппы — символ 2. Дальнейшее кодирование букв первой подгруппы не производим. Во второй подгруппе букве a5 присваиваем кодовый символ 0, а букве a6 — символ

1. Наконец, в третьей подгруппе букве a7 присваиваем кодовый символ 0, а букве a8 — символ 1. Имеем таблицу § 6. О защите информации 19

–  –  –

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

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

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

Формализуем сказанное. Обозначим через X конечное множество возможных открытых текстов, через K — конечное множество ключей и через Y — конечное множество шифрованных текстов. Правило шифрования на некотором ключе k K обозначим символом Ek. Оно определяется отображением Ek : X Y. Множество всех правил шифрования обозначается буквой E, т.е. E = {Ek | k K} .

Шифрованный текст Ek (X) с помощью ключа k открытого текста X имеет вид Ek (X) = {Ek (x) | x X} .

Пусть Dk обозначает правило дешифрования текста Ek (X) на ключе k K, т.е. Dk : Ek (X) X. Множество шифров по всем ключам обозначим буквой D, т.е. D = {Dk | k K}. Предполагается, если k K представляется в виде (ks, kd ), где ks — ключ шифрования, kd — ключ дешифрования, то Ek понимается как Eks, а Dk — как 20 Глава I. Введение

–  –  –

причем количества элементов в множествах A и B равны и множество ключей K совпадает с множеством биекций A на B .

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

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

Конечно, такой шифр не является стойким. Применение этого шифра можно усложнить. Например, можно взять несколько подстановок, и на каждом шаге шифрования пользоваться очередной § 8. О шифровании с открытым ключом 21 подстановкой .

Определим еще один шифр, называемый шифром перестановки .

Пусть X = Y = AL, и пусть K SL, где SL — симметрическая группа подстановок множества {1, 2,... L}. Для любого ключа k, открытого текста x = (x1,..., xL ) и шифрованного текста y = (y1,..., yL ) правила шифрования и дешифрования шифра перестановки определяются формулами Ek (x) = (xk(1),..., xk(L) ), Dk (y) = (yk1 (1),..., yk1 (L) ), где k — подстановка, обратная к подстановке k .

Приведем пример шифра перестановки. Зашифруем выражение этобылоуморя .

В качестве ключа рассмотрим подстановку ( ) .

Получим шифр тоэылбуморяо .

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

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

1) Абонент A выбирает два различных простых числа p, q и полагает n = pq .

2) Абонент A находит значение функции Эйлера (n) = (p 1)(q 1), выбирает число e, 0 e (n), такое, что (e, (n)) = 1, и пару чисел (n, e) объявляет открытым ключом, а число d такое, что de 1 (mod (n)) — секретным ключом .

3) Абонент B задает сообщение m, 0 m n1, создает шифрованное сообщение E(m) me (mod n) и посылает его по открытому 22 Глава I. Введение каналу связи абоненту A .

4) Абонент A c помощью секретного ключа d дешифрует его следующим образом D(E(m)) (me )d mde m (mod n) .

Таким образом абонент A получил сообщение абонента B .

5) Докажем, что D(E(m)) = m. Достаточно установить, что mde m (mod n) .

Если числа m и n взаимно просты, то по теореме Эйлера имеем m(n) m (mod n). Тогда из условия de 1 (mod (n)), имеем искомое утверждение mde m (mod n) .

Пусть теперь (m, n) 1. Тогда достаточно доказать, что справедливы сравнения mde m (mod p), mde m (mod q), поскольку из условия (p, q) = 1, pq = n, следует, что mde m (mod n) .

Представим число de в виде de = 1 + k(n). Тогда при p | m по малой теореме Ферма имеем mp1 1 (mod p), mde m(mp1 )k(q1) m (mod p) .

Пусть теперь p | m. Тогда m 0 (mod p) и mde m (mod p) .

Аналогично доказывается утверждение, что mde m (mod n) .

Заметим, что секретным ключом в данной системе шифрования является набор чисел (p, q, (n), d), а открытый ключ составляет пара чисел (n, e) .

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

Глава II

ПРЕФИКСНЫЕ КОДЫ. КОДЫ

ШЕННОНА И ГИЛБЕРТА–МУРА

§ 1. Префиксные коды. Неравенство Крафта – МакМиллана Пусть задан алфавит сообщений A, состоящий из r букв a1,..., ar, и кодирующий алфавит B, состоящий из q букв b1,..., bq .

Зададим отображение букв алфавита A в множество S(B) слов алфавита B, т.е. взаимно однозначное отображение : ak Bk, k = 1,..., r. Определим кодирование F : S(A) S(B), удовлетворяющее следующим условиям

1) F (ak ) = Bk, k = 1,..., r;

2) F (ak1 ak2... aks ) = Bk1 Bk2... Bks, 1 k1, k2,..., ks r, s 1;

где под произведением слов Bk Bl понимается приписывание слова Bl справа к слову Bk. Множество кодовых слов {B1, B2,..., Br } обозначают символом C() и называют кодом алфавита A в схеме .

Выделим некоторые классы алфавитных кодов. Код алфавита A в схеме называют однозначно декодируемым, если любое конечное слово из букв алфавита B имеет не более одного прообраза. Частным случаем однозначно декодируемых кодов являются префиксные коды. Код назовем префиксным, если для любых слов Bk, Bl, являющихся образами букв ak, al соответственно, каждое из них не является префиксом (началом) другого .

Пусть lk длина слова Bk, k = 1,..., r. Средней длиной кода в r схеме называется величина L() = pk lk, где pk — частота поk=1 явления буквы ak в открытом тексте .

Теорема (Неравенство Крафта – МакМиллана). Для того, чтобы существовал префиксный код с длинами l1,... lr, необходимо и достаточно, чтобы выполнялось неравенство

–  –  –

Необходимость. Пусть существует префиксный код с длинами l1,..., lr и l = max {l1,..., lr }. Символом nm обозначим количество 24 Глава II. Префиксные коды. Коды Шеннона и Гилберта–Мура

–  –  –

причем величина bm представляет собой количество способов из s кодовых слов из набора B1,..., Br составить кодовое слово длины m. Так как из свойства префиксности кода следует его однозначная rm .

декодируемость, то для величины bm имеем неравенство bm s 1/s Отсюда находим K ls. Следовательно, K (ls). Устремим s к бесконечности. Получим, что K 1 .

Достаточность. Построим префиксный код с заданным набором длин l1,..., lr кодовых слов. Определим величину l = max {l1,..., lr }. Количество однобуквенных слов обозначим через n1, двухбуквенных — через n2 и т.д .

Проведем индукцию по числу букв в кодовых словах. Так как алфавит A состоит из r букв, то можно произвольным образом выбрать n1 r однобуквенных кодовых слов. Двухбуквенных слов имеется в точности r2. Так как код является префиксным, то нельзя использовать слова, начинающиеся с n1 выбранных букв. Тогда количество n2 двухбуквенных обязано удовлетворять неравенству n2 r2 n1 r .

Предположим, что при 1 k l построены кодовые слова с длинами, не превосходящими k. Их количество nk будет не превосходить rk nk1 r · · · n1 rk1. Докажем утверждение для k + 1nk буквенных слов при условии, что k + 1 l. Префиксный код, содержащий nk+1 кодовых слов длины k + 1, должен удовлетворять соотношению nk+1 rk+1 nk r · · · n1 rk, поскольку следует исключить слова, которые являются префиксами. Таким образом, на l-м шаге получим rl n1 rl1 · · · nl1 r .

0 nl § 2. Теорема о минимальной длине префиксного кода 25

–  –  –

Далее нам понадобится понятие выпуклости функции одной переменной (см., например, [2], [гл. V, §14]). Функция f (x) называется выпуклой вверх на интервале (a, b), если для любых неотрицательных чисел 1,..., r с условием 1 + · · · + r = 1 и для любых 26 Глава II. Префиксные коды. Коды Шеннона и Гилберта–Мура

–  –  –

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

Для построения конечных полей нам понадобится кольцо многочленов Zp [x] от неизвестного x с коэффициентами из Zp. Каждый многочлен f (x) из Zp [x] можно записать в виде f (x) = an xn + an1 xn1 + · · · + a1 x + a0, где n — степень многочлена, an, an1,..., a1, a0 — коэффициенты многочлена, a0 — свободный член, an = 0 — коэффициент при старшей степени многочлена. Если an = 1, то многочлен f (x) называется нормированным многочленом. Многочлен f (x) из Zp [x] называется неприводимым, если он не может быть представлен в виде произведения двух многочленов положительной степени .

Пример. Выпишем все неприводимые многочлены первой, второй, третьей и четвертой степеней из кольца многочленов Z2 [x]. Имеем x, x + 1, x2 + x + 1, x3 + x2 + 1, <

x4 + x3 + x2 + x + 1, x4 + x3 + 1, x4 + x + 1 .

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

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

Заметим, что количество нормированных многочленов степени n равно pn. Символом ((n)) обозначим количество нормированных неприводимых многочленов степени n .

Рассмотрим функцию комплексного переменного p (z) = .

1 pz Докажем следующее вспомогательное утверждение .

Лемма 1. При |z| 1/p справедливо равенство

–  –  –

f (x) делит A(x) B(x). Для этого вводят следующее обозначение:

A(x) B(x) (mod f (x)) .

Над классами вычетов по модулю f (x) стандартным образом можно определить операции сложения, вычитания и умножения. Далее, для неприводимого многочлена f (x) и любого многочлена A(x) можно найти многочлен X(x) такой, что A(x)X(x) 1 (mod f (x)) .

Последнее утверждение следует из того, что с помощью алгоритма Евклида находятся многочлены X(x) и Y (x) с коэффициентами из Zp такие, что выполняется равенство A(x)X(x) + f (x)Y (x) = 1 .

Таким образом определяется деление в кольце классов вычетов по модулю неприводимого многочлена f (x). Тем самым, классы вычетов по модулю неприводимого многочлена образуют поле. Эти классы вычетов можно отождествить с многочленами степени, меньшей n. Их количество в Zp [x] будет равно pn .

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

Пусть элементы a и b имеют порядки m и n соответственно, и пусть l = [m, n] — наименьшее общее кратное этих чисел. Из канонического разложения чисел m и n на простые сомножители находим l = m0 n0, (m0, n0 ) = 1 и m = m0 m1, n = n0 n1. Тогда элемент c = am1 bn1 имеет порядок l. Действительно, пусть натуральное число s — порядок элемента c. Тогда число s — наименьшее натуральное число с условием cs = 1. Имеем, также, cl = (am1 bm1 )l = amn0 bnm0 =

1. Разделим число l с остатком на s. Получим l = sl1 + r, 0 r s .

Отсюда находим cr = clsl1 = 1. Следовательно, r = 0. В противном случае 0 r s, cr = 1, что противоречит минимальности выбора натурального числа s с условием cs = 1. Таким образом, s | l .

Далее, имеем 1 = csm0 = ams bn1 m0 s = bn1 m0 s. Порядок элемента b равен n. Отсюда следует, что n1 m0 s делится на n, т.е. n0 | s. Аналогично находим 1 = csn0 = an0 m1 s. Следовательно, m0 | s. Так как m0 и n0 взаимно просты, то l | s, где l = m0 n0 .

Из доказанного следует, что l = s, т.е. элемент c имеет порядок l .

Пусть конечная подгруппа G мультипликативной группы поля имеет порядок. Тогда максимальный из порядков m элементов этой подгруппы не превосходит. Аналогично предыдущему можно показать, порядок каждого элемента подгруппы является делителем числа m, т.е. все элементы из G удовлетворяют уравнению xm 1 = 0 .

§ 1. Конечные поля. Неприводимые многочлены 33

–  –  –

где символ a пробегает все элементы поля K .

Пример. Пусть GF (24 ) — поле Галуа из 16 элементов, представляющее собой все классы вычетов в кольце многочленов Z2 [x] по модулю неприводимого многочлена x4 + x + 1 в Z2 [x]. Пусть, также a — образующая мультипликативной группы поля. Тогда имеем a4 + a + 1 = 0. Следовательно, все ненулевые элементы поля можно представить в виде a0 = 1, a1 = a, a2 = a2, a3 = a3, a4 = a + 1, a5 = a2 + a, a6 = a3 + a2, a7 = a3 + a + 1, a8 = a2 + 1, a9 = a3 + a, a10 = a2 + a + 1, a11 = a3 + a2 + a, a12 = a3 + a2 + a + 1, a13 = a3 + a2 + 1, a14 = a3 + 1, a15 = 1 .

Заметим, что количество образующих мультипликативной группы поля GF (pn ) равно (pn 1) .

Теорема 3. Пусть n — любое натуральное число и p — любое простое число .

Тогда для двух неприводимых многочленов f (x) и g(x) поля их классов вычетов по модулям этих многочленов изоморфны .

При доказательстве теоремы 2 установлено, что конечное поле классов вычетов по модулю неприводимого многочлена f (x) степени n n из кольца Zp [x], изоморфно полю корней многочлена xp x. Это и доказывает искомый изоморфизм .

Теорема 4. Пусть n — любое натуральное число и p — любое простое число .

Тогда с точностью до изоморфизма существует единственное поле из pn элементов .

34 Глава III. Конечные поля. Циклические коды Поскольку мультипликативная группа конечного поля из pn является циклической группой, каждый элемент a этой группы удовлетворяет уравнению xp 1 1 = 0, причем найдется элемент, поn рядок которого равен pn 1. Таким образом установлен изоморфизм мультипликативных групп конечных полей из pn элементов .

§ 2. Циклические коды Пусть V — линейное k-мерное подпространство арифметического n-мерного пространства L = LF, k n, наборов v = (vn1,..., v1, v0 ) с координатами из любого поля F, например, Z2. Тогда подпространство V называется циклическим кодом, если для любого набора a = (an1,..., a1, a0 ) из V набор a = (an2,..., a1, a0, an1 ) принадлежит V. Другими словами, набор a получен из набора a циклическим сдвигом всех координат на одну координату вправо .

Для описания циклических кодов воспользуемся кольцом многочленов F[x]. Набору (an1,..., a1, a0 ) поставим в соответствие многочлен f (x) = an1 xn1 + · · · + a1 x + a0 степени, не превосходящей n 1. Тогда циклическому сдвигу отвечает умножение многочлена f (x) на переменную x и рассмотрение класса вычетов по модулю xn 1. Действительно, имеем xf (x) = x(an1 xn1 + · · · + a1 x + a0 ) = an1 (xn 1)+ +an2 xn1 + an3 xn2 + · · · + a0 x + an1 = an1 (xn 1) + g(x) .

Следовательно, получим сравнение g(x) xf (x) (mod (xn 1)), где многочлен g(x) из кольца F[x] отвечает циклическому сдвигу всех координат вектора a на одну координату вправо .

В любом классе вычетов в кольце многочленов F[x] по модулю xn 1 содержится в точности один многочлен степени, меньшей n .

Совокупность всех этих классов образует кольцо Fn .

Теорема. Пусть Fn — кольцо классов вычетов по модулю xn 1 в кольце F[x], где F — некоторое поле. Для того чтобы линейное подпространство V из Fn было циклическим кодом необходимо и достаточно, чтобы оно было идеалом в кольце Fn .

Необходимость. Дано, что код V — циклический. Далее, для любого набора v = (an1, .

.., a1, a0 ) из V умножение многочлена f (x) = an1 xn1 +...+a1 x+a0 из Fn на переменную x дает многочлен g(x) = an2 xn1 + an3 xn2 + · · · + a0 x + an1 Fn, который отвечает циклическому сдвигу v = (an2,..., a1, a0, an1 ) из V. Отсюда следует, что многочленам f (x), xf (x), x2 f (x),..., xn1 f (x) из Fn § 2. Циклические коды 35 также отвечают кодовые слова v, v, v,..., v(n1) из V. Поскольку V является подпространством, любая линейная комбинация наборов v, v, v,..., v(n1) принадлежит V, т.е. для любых постоянных c0, c1,..., cn1 из F имеем c0 v + c1 v + c2 v +... + cn1 v(n1) V .

Другими словами, многочлен c0 f (x) + c1 xf (x) + c2 x2 f (x) +... + cn1 xn1 f (x) = c(x)f (x) принадлежит Fn. Это обстоятельство позволяет сказать, что множество всех многочленов, отвечающих наборам из подпространства V, образует идеал в кольце многочленов Fn. Необходимость утверждения теоремы доказана .

Достаточность. Пусть J — любой идеал в кольце многочленов Fn. Возьмем любой многочлен f (x) = an1 xn1 + · · · + a0 из J. Ему отвечает кодовое слово v = (an1,..., a1, a0 ). Рассмотрим многочлен xf (x) J. Ему отвечает кодовое слово v = (an2,..., a0, an1 ), которое является циклическим сдвигом на одну координату вправо кодового слова v, тем самым идеалу J кольца Fn отвечает циклический код .

Теорема. Пусть Fn — кольцо классов вычетов по модулю x 1 n в кольце многочленов F[x], где F — некоторое поле. Тогда кольцо Fn является кольцом главных идеалов, т.е. найдется фиксированный многочлен из Fn такой, что все элементы идеала кратны этому многочлену .

Пусть f (x) — нормированный многочлен наименьшей степени, принадлежащий рассматриваемому идеалу J. Возьмем любой многочлен g(x) J и разделим его с остатком на f (x). Получим g(x) = f (x)q(x) + r(x), где многочлен r(x) либо имеет степень меньшую, чем степень многочлена f (x), либо равен r(x) 0 в Fn. Поскольку r(x) также принадлежит идеалу J, первая возможность не имеет места (f (x) — многочлен наименьшей степени из J). Следовательно, r(x) 0 .

Многочлен f (x) наименьшей степени, принадлежащий идеалу J, называется многочленом, порождающим идеал J из кольца Fn .

Теорема. Пусть многочлен f (x) порождает идеал J из Fn. Тогда f (x) является делителем xn 1 .

Разделим многочлен xn 1 с остатком на f (x) в кольце многочленов F[x]. Получим g(x) = f (x)q(x) + r(x), 36 Глава III. Конечные поля. Циклические коды

–  –  –

§ 4. Линейные рекуррентные уравнения произвольного порядка Пусть последовательность {un }, n 0, удовлетворяет линейному с постоянными коэффициентами рекуррентному уравнению порядка r следующего вида un+r = a1 un+r1 + a2 un+r2 +... + ar un, n 0, причем заданы первые r членов последовательности us = cs, 0 r 1, числа cs — абсолютные постоянные и они задают наs чальные условия для данного рекуррентного уравнения. Будем счиЛинейные рекуррентные уравнения произвольного порядка 45

–  –  –

§ 5. Рекуррентные соотношения первого порядка в кольцах вычетов Пусть, теперь, для любого натурального n задано рекуррентное соотношение xn+1 = f (xn ) и множество значений xn конечно и не превосходит N. Тогда в последовательности x1, x2,..., xk при k N найдутся одинаковые значения xs. Значит, последовательность {xn } имеет период, не превосходящий N. Периодом последовательности {xn } называется минимальное натуральное число T такое, что xn+T = xn при всех n, превосходящих некоторое число n0 .

Рассмотрим последовательность {xn }, заданную рекуррентным соотношением xn+1 axn (mod N ) по некоторому натуральному 2 и (a, N ) = 1. Из определения имеем xn an1 x1 модулю N (mod N ). Пусть T — наименьшее натуральное число с условием aT 1 (mod N ). Тогда T является периодом последовательности {xn } .

Наконец, пусть задана последовательность вида xn+1 axn + c (mod m). Вновь обратимся к задаче о нахождении периода этой последовательности. Справедлива следующая теорема .

Теорема. Для того чтобы последовательность xn+1 axn + c (mod m) имела период m необходимо и достаточно, чтобы выполнялись следующие условия

а) числа c и m взаимно просты,

б) число a 1 делится на любой простой делитель числа m,

в) число a 1 делится на 4, если 4 | m .

Пусть m = m1 m2 и (m1, m2 ) = 1. Представим xn, a, c в виде xn m2 yn + mm1 (mod m), a m2 a1 + m1 a2 (mod m), c m2 c1 + m1 c2 (mod m), где yn, a1, c1 могут принимать значения из полной системы вычетов по модулю m1, а вычеты zn, a2, c2 — из полной системы вычетов по модулю m2. Тогда по решению xn сравнения xn+1 axn + c (mod m) однозначно находятся решения yn, zn системы сравнений yn+1 a1 yn + c1 (mod m1 ), zn+1 a2 zn + c2 (mod m2 ), и наоборот .

Пусть T1 — период последовательности {yn } и T2 — период последовательности {zn }. Тогда период T последовательности {xn } равен наименьшему общему кратному чисел T1 и T2 .

§ 5. Рекуррентные соотношения первого порядка в кольцах вычетов47

–  –  –

Следовательно, f (x)g(x) = xr1 (xT 1). Поскольку f (0) = 1, многочлен xr1 будет взаимно прост с f (x). Отсюда получим, что многочлен f (x) является делителем xT 1 в кольце многочленов Fq [x] .

Утверждение леммы 3 позволяет дать следующее определение .

Назовем порядком многочлена f (x) из Fq [x] минимальное натуральное число C такое, что f (x) является делителем xC 1 в кольце многочленов Fq [x] .

Отсюда находим, что порядок ord f многочлена f (x) не меньше его степени r = deg f .

Из леммы 3 следует, что C T, где T — период последовательности (1) с начальными условиями u0 =... = ur2 = 0, ur1 = 1 .

Лемма 4. Пусть задан многочлен f (x) Fq [x] f (0) = 0, и пусть при некотором натуральном числе T многочлен f (x) является делителем многочлена xT 1 в Fq [x] .

Пусть, также, C = ord f. Тогда имеем, что T 0 (mod C), т.е. число T делится на C .

Разделим натуральное число T с остатком на C. Получим T = uC + v, 0 v C. Поскольку T C, находим, что u 1 .

По условию леммы имеем, что найдутся многочлены gC (x) и gT (x), удовлетворяющие соотношениям

–  –  –

Продолжая этот процесс u раз, найдем f (x)Gu (x) = xv 1. Неравенство v 0 противоречит условию минимальности выбора натурального числа C с условием f (x)gC (x) = xC 1. Следовательно, v = 0 и число T делится на C .

Лемма 5. Пусть порядок характеристического многочлена f (x) Fq [x], f (0) = 0, последовательности (1) равен C, и пусть натуральное число T является периодом этой последовательности в Fq с начальными условиями u0 = .

.. = ur2 = 0, ur1 = 1. Тогда имеем, что T = C .

По лемме 4 имеем, что T = uC, u 1. Далее воспользуемся леммой 2. Получим f (x)g(x) = xr1 (xuC 1). Из определения мноРекуррентные соотношения в конечных полях 53

–  –  –

и свободный член g0 (x) равен 1 .

Из (4) имеем, что uC =... = uC+r2 = 0 и uC+r1 = 1. Таким образом, период последовательности (1) с начальными условиями u0 =... = ur2 = 0 и ur1 = 1 не превосходит C. С другой стороны, число C делитель периода этой последовательности, т.е. не меньше C. Значит, период этой последовательности равен C .

Далее, понадобится определение неприводимого многочлена на полем Fq. Говорят, что многочлен f (x) из Fq [x] неприводим над полем Fq, если не существует многочленов g(x), h(x) Fq [x], таких, что f (x) = g(x)h(x) .

Лемма 6. Пусть порядок характеристического многочлена f (x) Fq [x], f (0) = 0, последовательности (1) равен C, и пусть натуральное число T является периодом этой последовательности в Fq с начальными условиями u0 = .

.. = us1 = 0, us = 1, us+1 = ur1 = 0, где s — любое целое число из промежутка от 0 до r 1, т.е. последовательность un совпадает с последовательностью s (n), введенной выше. Тогда имеем, что T = C .

Предыдущая лемма была доказана для последовательности r1 (n) и в этом случае по формулировке она совпадает с леммой 6 .

Для последовательностей s (n), s = 0,..., r 2 ход доказательства леммы 6 ничем не отличается доказательства леммы 5 .

Лемма 7. Пусть характеристический многочлен f (x) Fq [x] последовательности (1) неприводим над Fq и пусть начальные условия таковы: u0 = c0, .

.., ur2 = cr2, ur1 = cr1, где c0... cr2 cr1 = 0. Тогда последовательность (1) является чисто периодической с периодом, равным порядку многочлена f (x) .

По лемме 1 для любых m и n имеем un+m = um1 1 (n) +... + umr+1 r1 (n) .

В частности, пусть C — период каждой из последовательностей 1 (n),..., r (n). По лемме 6 он совпадает с порядком характеристического многочлена f (x) этой последовательности. Отсюда находим un+m+C = um1 1 (n + C) +... + umr+1 r (n + C) = 54 Глава IV. Рекуррентные соотношения. Производящие функции um1 1 (n) +... + umr+1 r1 (n) = un+m, т.е. период T последовательности un не превосходит C .

С другой стороны, по лемме 4 справедливо неравенство T C .

Следовательно, T = C, и последовательность un будет чисто периодической .

Лемма 8. Пусть многочлен f (x) Fq [x] неприводим над Fq и пусть его степень равна r .

Тогда порядок многочлена f (x) является делителем числа q r 1 .

По лемме 7 любая последовательность (1) с ненулевыми начальными условиями имеет период, равный C — порядку характеристического многочлена f (x). Из неприводимости многочлена f (x) следует, что f (0) = 0. Число всех различных последовательностей (1) с ненулевыми начальными условиями в количестве r будет равно q r 1 .

Как и ранее, будем считать, что последовательность (1) определена для всех целых n. Тогда последовательности, полученные сдвигом номера n на любое целое число, будут совпадать с первоначальной последовательностью, но они отвечают различным начальным условиям (u0, u1,..., ur1 ). Так как значения последовательности определяются ее значениями на периоде, то все начальные условия разбиваются на непересекающиеся подмножества по C = ord f элементов в каждом. Таким образом доказано, что C делит q r 1 .

Лемма 9. Пусть многочлен f (x) F2 [x] неприводим над F2 и его степень равна r .

Пусть, также, число 2r 1 — простое. Тогда период ненулевой последовательности un с характеристическим многочленом f (x) равен числа 2r 1 .

По предыдущей лемме длина C периода последовательности (1) является делителем простого числа 2r 1. Следовательно, C = 2r 1 .

Заметим, что простые числа вида 2r 1 называются простыми числами Мерсенна, причем r также является простым числом. Имеется гипотеза, что простых чисел Мерсенна бесконечно много. Не доказано также, что простые числа Мерсенна имеют нулевую плотность во множестве всех чисел Мерсенна. Другими словами, обозначим через M (x) количество простых p1 = 2p 1, где p пробегает все простые числа, не превосходящие x. Тогда предполагают, что lim M (x)/(x) = 0, где (x) — количество всех простых чисел, не x превосходящих x .

Глава V

АРИФМЕТИЧЕСКИЙ ПОДХОД К

ИСКАЖЕНИЮ ЗНАКОВ В

ШИФРАХ ПРОСТОЙ ЗАМЕНЫ И

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

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

Первое, дошедшее до нас, описание подобного частотного метода криптоанализа относится к IX веку [43], с.30–32. Оно принадлежит известному “философу арабского мира” Абу Юсуф Якуб ибн Исхак ибн ас-Сабах ибн Умран ибн Исмаил аль-Кинди. Его знаменитый трактат “Рукопись по дешифрованию криптографических сообщений” был открыт в 1987 г. в Стамбуле в оттоманском архиве Сулайманийа. Как указывает С. Сингх [43], в этом трактате дан подробный анализ статистики, фонетики и синтаксиса арабского языка и приведена “революционная система криптоанализа аль-Кинди, которая умещается в следующие два коротких абзаца .

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

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

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

Для того, чтобы значительно усложнить задачу вскрытия шифра простой замены применяют методы “рандомизации” и “сжатия” открытых текстов [1], с.106. Они используются в компьютерных архиваторах .

Другой пример “сжатия” алфавита приводится в книге С. Сингха [43] в приложении F (с. 416-417): “Шифр ADFGVX” .

Зашифровывание здесь состоит в том, матрица размером 66 заполняется 26 буквами и 10 цифрами в произвольном порядке. Каждая строка и каждый столбец задаются одной из шести букв: A, D, F, G, V и X. Расположение элементов в матрице служит ключом .

Например, матрица имеет вид

–  –  –

мер, 8 заменяется на AA, символ p — на AD .

Таким образом алфавит шифртекста будет использовать только 6 букв: A, D, F, G, V, X. Тем самым, произведено “сжатие” алфавита, но тем не менее для взлома шифрсообщения здесь достаточно воспользоваться частотным анализом для биграмм. Как указано в [43], применение дополнительно перестановки символов с использованием еще одного ключа приводит к более сложному криптоанализу .

Буквы A, D, F, G, V, X выбраны с той целью, чтобы они существенно отличались в представлении в виде точек и тире азбуки Морзе .

Отметим также, что указанные выше виды шифрования основаны на комбинаторных соображениях .

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

§ 2. Метод искажения знаков в шифре простой замены с помощью извлечения корня квадратного Изложим метод искажения знаков в шифре простой замены с помощью извлечения корня квадратного по некоторому модулю. Пусть алфавит открытого текста состоит из n букв. Шифрование исходного текста способом простой однобуквенной замены (см. [27] — [24]) основано на некоторой подстановке множества букв алфавита. Следовательно, эта подстановка является ключом такой криптосистемы, и, значит, количество возможных ключей будет равно n!. Отметим, что различным символам шифрованного текста соответствуют различные буквы исходного текста. Далее, в исходном тексте различные буквы, как правило, встречаются с разной частотой при достаточно большой его длине .

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

Расположим буквы в порядке убывания частот:

1) о — 0,090, 2) е, — 0,072, 3) а — 0,062, 4) и — 0,062, е

5) н — 0,053, 6) т — 0,053 7) с — 0,045,..., 31) ф — 0,002 .

Поскольку число 31 — простое, все вычеты по модулю 31 можно разбить на три класса: квадратичные вычеты, квадратичные невычеты и вычет, отвечающий нулю. Как известно, количество квадратичных невычетов и количество квадратичных вычетов в полной 58 Глава V. Арифметический подход к искажению знаков системе вычетов по простому модулю одинаково и в данном случае оно равно 15. Все квадратичные вычеты по модулю 31 исчерпываются следующими классами вычетов по модулю 31: 1, 22, 32,..., 152 .

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

Если a — квадратичный вычет по модулю 31, то решения сравнения x2 a (mod 31) представляют собой два различных вычета по модулю 31: a1 = b и a2 = 31 b .

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

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

Далее продолжим шифрование следующим образом. Пусть буква зашифрована числом a и a — квадратичный вычет по модулю 31, и пусть вычеты a1, a2 решения сравнения x2 a (mod 31). Тогда последовательности указанного числа a в криптограмме шифра простой замены ставим в соответствие последовательность чисел a1, a2, a1, a2,.... Например, если в криптограмме имеется 5 мест, на которых стоит число a, то заменяем в этих местах число a на следующую последовательность чисел a1, a2, a1, a2, a1. Пусть, теперь, буква закодирована числом a и a — квадратичный невычет по модулю 31 или 0. Тогда в криптограмме это число a оставляем без изменения .

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

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

Последовательно обозначим места, на которых стоят квадратичные вычеты по модулю 31, — единицами, а места, на которых стоят квадратичные невычеты, — нулями. Полученную последовательность чисел 1,..., n, составленную из нулей и единиц, можно рассматривать как запись некоторого числа m в двоичной системе счисления. Таким образом отправителю достаточно передать построенное число m .

§ 2. Метод искажения знаков в шифре простой замены 59 Итак, абонент A должен послать “секретное” число m абоненту B по каналу связи .

Для этого можно воспользоваться, например, известным алгоритмом А. Шамира для передачи секретной информации по каналу связи (см., например, [31, 47]). Приведем здесь этот алгоритм .

Абоненты A и B выбирают достаточно большое простое число p m. Затем абонент A выбирает секретный ключ a, 1 a p 1, (a, p1) = 1, а абонент B — секретный ключ b, 1 b p1, (b, p1) =

1. Для проверки условия взаимной простоты a и p 1 абонент A может использовать алгоритм Евклида. В случае, если числа a и p1 не взаимно просты, то следует проверить на взаимную простоту числа a+1 и p1 и т.д. Указанный процесс выбора ключа a оборвется через конечное число шагов, так как, например, (p 2, p 1) = 1 .

Аналогичным образом может поступить и абонент B. Далее абонент A находит натуральное число такое, что a 1 (mod p 1), 1 p 1 .

Аналогично поступает абонент B. Он находит число с условиями b 1 (mod p 1), 1 p 1 .

Итак, абонент A имеет секретный ключ (a, ), а абонент B — секретный ключ (b, ) .

Теперь абонент A пересылает число m абоненту B по открытому каналу за следующие четыре шага .

1-й шаг. Абонент A посылает абоненту B число m1 ma 0 m1 p 1 .

(mod p), 2-й шаг. Абонент B посылает абоненту A число m2 mb 0 m2 p 1 .

(mod p),

–  –  –

Далее можно рекуррентным образом продолжить процедуру “сжатия алфавита” .

Пусть l — натуральное число и q — простое число вида q = 2l + 1 .

Тогда простое число q обязано быть простым числом Ферма q = m Fm = 22 + 1, m 0. На сегодняшний день известно только пять простых чисел Ферма F0 = 3, F1 = 5, F2 = 17, F3 = 28 + 1 = 257 и F4 = 216 + 1 = 65537. Мультипликативная группа поля Fq является циклической и состоит из q 1 = 2l элементов. Каждый из них имеет порядок 2k, 0 k 2l .

Пусть теперь алфавит A состоит из q = 2l + 1, l = 2m, 0 m 4, символов. Тогда, используя процедуру, описанную выше, в точности l раз, приходим к шифрованному тексту, алфавит которого отвечает только квадратичным невычетам и нулевому вычету по модулю q .

Таким образом алфавит шифрованного текста будет состоять из (q + 1)/2 символа .

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

Опишем процедуру шифрования .

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

Разобьем все вычеты по модулю 31 на два класса: первый класс состоит из 15 квадратичных невычетов, второй — из 15 квадратичных вычетов и нуля .

1) Зашифруем открытый текст методом простой замены с помощью некоторой подстановки .

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

3) Далее, тем буквам зашифрованного текста в соответствии с пунктом 2), которым соответствуют квадратичные невычеты поставим в соответствие квадраты этих чисел по модулю 31 из отрезка [0, 30], а для букв, отвечающих квадратичным вычетам и нулю, сохраним те же значения квадратичных вычетов и нуля .

§ 3. Метод искажения знаков в шифре простой замены 61

4) Подведем итог процедуры шифрования. Итак, получен зашифрованный текст S, алфавит которого состоит только из квадратичных вычетов и нуля по модулю 31, т.е. содержит только 16 знаков .

5) Чтобы провести расшифрование, надо знать те места, на которых стоят квадраты квадратичных невычетов. Для этого составим двоичное число m, отвечающее шифртексту, следующим образом: те места, на которых стояли квадратичные невычеты, обозначим 1; а остальные — 0 .

Тем самым, процедура шифрования завершена .

Процедура расшифрования происходит следующим образом .

а) Абоненту передается зашифрованный текст S и число m. Число m передается с помощью известного алгоритма А. Шамира (см., например, [31, 27, 47]) .

б) Для восстановления первоначальной криптограммы, полученной в 1), необходимо на местах, отвечающих 1 в двоичной записи числа m (т.е. на местах, где стоят квадраты квадратичных невычетов), поставить первоначальные квадратичные невычеты, решая сравнение x2 t (mod 31) относительно x, причем надо выбрать именно то решение данного сравнения, которое возводилось в квадрат .

в) При простом числе p = 31 имеем p 3 (mod 4). Тогда вычет числа 1 является квадратичным невычетом по модулю 31. Пусть a — квадратичный невычет по модулю 31. Тогда сравнению x2 a2 (mod 31) отвечают два решения a и a (mod 31), из которых a — квадратичный невычет (по выбору), и a = (1)a является квадратичным вычетом, как произведение двух квадратичных невычетов .

г) Простой способ извлечения корня квадратного из числа b простому модулю p 3 (mod 4) (см., например, [10]) т.е. способ наp+1 хождения решения сравнения x2 b (mod p), таков x ±b 2 (mod p). Проверка числа на принадлежность к квадратичным вычетам или невычетам по модулю p осуществляется с помощью криp1 терия Л. Эйлера: x x 2 (mod p) .

p Пусть, теперь, количество букв алфавита будет простым числом p, сравнимым с 1 по модулю 4. Разобьем все вычеты по модулю p на два класса: в первый класс войдут все квадратичные невычеты по модулю p, не превосходящие (p 1)/2 (их количество равно (p 1)/4); во второй класс — оставшиеся квадратичные невычеты, все квадратичные вычеты и 0 .

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

1) Как и раньше, текст шифруется способом простой замены .

62 Глава V. Арифметический подход к искажению знаков

2) Затем буквы шифрованного текста располагаем в порядке убывания частот их появления. Первым (p 1)/4 буквам присваиваем значения последовательных квадратичных невычетов из первого класса, остальным буквам присваиваем значения из второго класса .

3) Буквам, которые соответствуют числа из первого класса, поставим в соответствие квадраты этих чисел по модулю p из отрезка [0, p 1] .

4) Составим двоичное число m, отвечающее шифртексту, следующим образом: места, на которых находятся числа из первого класса, обозначим 1, а остальные — 0 .

Далее поступаем, как в предыдущем случае. Отметим, что извлечение квадратного корня по модулю p в данном случае будет несколько сложнее (см. [10]) .

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

1) Возьмем любую подстановку из 31 знака и зашифруем текст методом простой замены с помощью этой подстановки .

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

3) Далее, тем буквам зашифрованного текста в соответствии с пунктом 2), которым соответствуют квадратичные невычеты поставим в соответствие квадраты этих чисел по модулю 31 из отрезка [0, 30], а для букв, отвечающих квадратичным вычетам и нулю, поставим в соответствие значения квадратных корней из этих вычетов по модулю 31 и нуля, причем для квадратичного вычета a по модулю 31 решения a1, a2, (a1 a2 ) сравнения x2 a (mod 31) заменяют последовательность чисел a в криптограмме на последовательность чисел a1, a2, a1, a2,... .

4) Наконец, составим двоичное число m, отвечающее шифртексту, следующим образом: те места, на которых стояли квадратичные невычеты, обозначим 1; а остальные — 0 .

Процедура шифрования завершена .

§ 5. Анализ методов искажения знаков 63 Опишем процедуру расшифрования .

а) Абоненту передается зашифрованный текст S и число m. Число m передается с помощью известного алгоритма А. Шамира .

б) Для восстановления первоначальной криптограммы, полученной в 1), необходимо на местах, отвечающих 1 в двоичной записи числа m (т.е. на местах, где стоят квадраты квадратичных невычетов), поставить первоначальные квадратичные невычеты, решая сравнение x2 t (mod 31) относительно x, причем надо выбрать именно то значение x, которое возводилось в квадрат .

При простом числе p = 31 имеем p 3 (mod 4). Тогда вычет числа 1 является квадратичным невычетом по модулю 31. Пусть a — квадратичный невычет по модулю 31. Тогда сравнению x2 a2 (mod 31) отвечают два решения a и a (mod 31), из которых a — квадратичный невычет (по выбору), и a = (1)a является квадратичным вычетом, как произведение двух квадратичных невычетов .

Cпособ извлечения корня квадратного из числа b по простому модулю p 3 (mod 4) (см., например, [10]) т.е. способ нахождения p+1 решения сравнения x2 b (mod p), таков: x ±b 2 (mod p).

Проверка числа на принадлежность к квадратичным вычетам или невычетам по модулю p осуществляется с помощью критерия Л.Эйлера:

() p1

p x x (mod p) .

в) Продолжим восстановление первоначальной криптограммы .

На местах, отвечающих 0 в двоичной записи числа m, поставим первоначальные значения квадратичных вычетов по модулю 31, возводя в квадрат вычеты, стоящие на этих местах .

Процедура расшифрования завершена .

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

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

64 Глава V. Арифметический подход к искажению знаков

–  –  –

Пусть, теперь, b1,s, b2,s,..., bms,s — полная система вычетов по модулю ms, например, 1, 2,..., ms, 1 s r. Составим r таблиц Виженера для каждого из алфавитов b1,s, b2,s,..., bms,s, 1 s r .

Для каждой из приведенных выше таблиц Виженера при некотором натуральном числе ts с условиями 1 ts ms, задаем ключ ks = (bk1,s, bk2,s,..., bkts,s ), 1 s r .

Пусть, далее, задан открытый текст ah1 ah2... ahu. По формуле (2) преобразуем его в r текстов. Имеем bh1,s bh2,s... bhu,s, s = 1, 2,..., r .

Аналогично вышеприведенному с помощью таблицы Виженера с номером s и ключа ks шифруем текст bh1,s bh2,s... bhu,s, s = 1, 2,..., r .

Расшифрование проводится также аналогично вышеизложенному .

§ 7. Арифметический вариант шифра Виженера Рассмотрим один из возможных путей обобщения шифра Виженера (см. [31, 4]), использующий возможность аддитивного представления целых чисел. Пусть m — количество всех символов алфавита и для натуральных чисел m, m1, m2 справедливы равенства m = m1 m2, (m1, m2 ) = 1, m1 1, m2 1. Например, m = 30, m1 = 5, m2 = 6 .

Далее, пусть 1 пробегает полную систему вычетов по модулю m2, а 2 — полную систему вычетов по модулю m1. Тогда сумма m1 1 + m2 2 пробегает полную систему вычетов по модулю m (см .

[10]). Другими словами, любое целое число a с условием 1 a m при некоторых фиксированных b1 по модулю m2 и b2 по модулю m1 единственным образом представляется в виде a b1 m1 a1 + b2 m2 a2 (mod m), (1) m1, находятся из сравнений b1 m1 a1 a где 1 a1 m2, 1 a2 (mod m2 ) и b2 m2 a2 a (mod m1 ) .

Таким образом, каждому целому числу a, 1 a m, отвечает единственная пара целых чисел (a1, a2 ), удовлетворяющая сравнению (1). Расположение пар (a1, a2 ) в указанном выше соответствии может служить частью секретного ключа. По формуле (1) этот ключ однозначно задается парой (b1, b2 ), где 1 b1 m2, 1 b2 m1 .

Следовательно, число возможных ключей равно m = m1 m2 .

Более того, каждому символу a алфавита можно поставить некоторым образом в соответствие любую пару (1, 2 с условием 1 1 m2, 1 2 m1. Тогда число всевозможных ключей будет равно m1 !m2 ! .

68 Глава V. Арифметический подход к искажению знаков Далее, составим таблицу Виженера по следующему правилу: в строку с номером k поместим элементы ((1 +ck) (mod m2 ), (2 +ck) (mod m1 )), где различные пары (1 (mod m2 ), 2 (mod m1 )) образуют первую строку, величина k изменяется от 0 до m 1 и c — любое целое число, взаимно простое с m. Для того, чтобы полученная таблица была таблицей Виженера необходимо и достаточно, чтобы строки с разными номерами были различными. Предположим, что в построенной таблице строки с номерами k и k совпадают. Тогда, очевидно, имеем c(k k ) 0 (mod m2 ), c(k k ) 0 (mod m1 ) .

Отсюда получим, что m | (k k ). Это означает, что k = k. Тем самым доказано, что построенная таблица является таблицей Виженера. Отметим, что число c также может служить частью секретного ключа .

Шифрование и дешифрование по построенной таблице осуществляется стандартным образом .

Обратим внимание еще на один момент составления таблицы Виженера. Пусть количество символов алфавита равно m, число m представляется в виде m = m1... mr, r 2, и mk, ml попарно взаимно просты при k, l = 1,..., r. Далее, каждому символу a, являющемуся вычетом по модулю m, взаимно однозначным образом поставим в соответствие набор (a1,..., ar ), где ak, k = 1,..., r, принимает значения из полной системы вычетов по модулю mk. Например, это соответствие можно установить следующим образом .

Положим Mk = mm1. Тогда любой вычет a по модулю m одноk значным образом представляется в виде a M1 a1 +... + Mr ar (mod m), где ak, k = 1,..., r, принимает значения из полной системы вычетов по модулю mk. Различным наборам (a1,..., ar ), где 0 ak mk, k = 1,..., r, отвечают различные вычеты a по модулю m. Таким образом, при указанных соответствиях существует m1 !... mr ! секретных ключей .

По аналогии с предыдущим, составим таблицу Виженера по следующему правилу: в строку с номером k поместим элементы ((a1 + ck) (mod m1 ),..., (ar + ck) (mod mr )), где различные пары (a1 (mod m1 ),..., ar (mod mr )) образуют первую строку, величина k изменяется от 0 до m 1 и c — любое целое число, взаимно простое с m. Строки с разными номерами в этой таблице будут различными, так что получена таблица Виженера .

Глава VI

АСИММЕТРИЧНЫЕ ШИФРЫ

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

Идея шифрования с открытым ключом тесно связана с понятием однонаправленной (односторонней) функцией. На качественном уровне оно определяется так. Взаимно однозначное отображение f : X Y двух текстов X и Y называется строго однонаправленной, если выполняется следующее условие: существует “эффективный” метод вычисления f (x) для всех x X, но не существует “эффективного” метода для вычисления x из соотношения y = f (x) для всех y f (X), где f (X) — образ множества X при отображении f .

В качестве начальной иллюстрации приведем замечательный пример из книги Саломаа [40] однонаправленной функции. Построение ее основано на телефонном справочнике. Шифрование происходит побуквенно. Возьмем, например, “Большую телефонную книгу Юго-западного административного округа города Москвы за 2008– 2009 гг.” Для необходимой буквы x X в справочнике ищем слово, начинающееся на x, и шифруем соответствующим телефонным номером. Например, зашифруем слово “мехмат”. Находим м майский 1349396 е евросеть, торговый дом 9353857 х химической физики институт 9397249 м московский университет 1340483 а алтайский 4204600 т тамань 4258233 Таким образом, слово “мехмат” шифруется следующей последоваГлава VI. Асимметричные шифры тельностью кодовых обозначений: “1349396 9353857 9397249 1340433 4204600 4258233”. Однонаправленная функция, использованная для шифрования, ставит для законного расшифровальщика непреодолимые трудности. Он и наблюдатель испытывают одинаковые трудности. Если же легальный абонент имеет обратный телефонный справочник, то процедура расшифрования упрощается .

Уточним понятие односторонней функции. Взаимно однозначное соответствие f : X Y называется однонаправленной функцией с секретом (с лазейкой), если

а) существует “эффективный” метод вычисления f (x) для всех x X;

б) существует “эффективный” метод вычисления f 1 (y) для всех y f (X), но он не может быть получен “эффективно” из соотношения y = f (x) для всех y f (X): необходима дополнительная секретная информация “секрет” (“лазейка”) .

В качестве одного из первых примеров применения односторонних функций рассмотрим задачу о сохранении паролей .

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

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

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

В 1981 г. Лампорт (см., например, [18]) предложил усилить защиту доступа к компьютеру. Пусть некоторый пароль каким-то образом стал известен незаконному пользователю. Для усиления гаранВведение 71 тии законного доступа к компьютеру можно выполнить следующую процедуру .

1. Каждому законному пользователю дается свой начальный пароль 0 .

2. Затем для некоторого натурального числа m вычисляются m последовательных итераций функции f : 1 = f (0 ), 2 = f (1 ),..., m = f (m1 ), и пользователь сохраняет значения 0, 1,..., m1 .

3. Наконец, в память компьютера вводится m = f (m1 ) .

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

4. Для получения доступа к компьютеру пользователь вводит в него m1 и вычисляет значение m = f (m1 ) .

5. Проведя проверку значения f (m1 ) = m, пользователь стирает из памяти компьютера m и заменяет его на m1 .

6. В следующем сеансе связи роль m1 будет выполнять m2 и т.д .

Рассмотренная процедура позволяет провести m сеансов связи .

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

Обратимся теперь к построению некоторых односторонних функций .

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

Задают большое простое число p и первообразный корень g по модулю p. Далее, в приведенной системе вычетов по модулю p определяют взаимно однозначное отображение x f (x) g x (mod p) .

Заметим, что возведение в степень числа g выполняется достаточно просто. Оно сводится, в частности, к последовательным возведениям числа g в квадрат. Например, вычислим g 11. Имеем 11 = 23 + 21 + 20. Отсюда находим ( )2 g 11 = (g 2 )2 · g 2 · g .

С другой стороны, все известные алгоритмы вычисления обратной функции f 1, т.е. вычисления дискретного логарифма или индекса вычета по модулю p, требуют для вычисления ее значения времени, 72 Глава VI. Асимметричные шифры которое растет относительно log2 p не полиномиальным образом (величина [log2 p] равна количеству цифр в записи натурального числа p в двоичной системе счисления). Отметим,что, если число p содержит несколько сотен цифр, то в современных ЭВМ использование этих алгоритмов не является целесообразным .

Рассмотрим, теперь, пример криптосистемы с открытым ключом, основанной на вычислении дискретного логарифма в конечном поле .

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

Пусть, например, абонент A желает передать абоненту B сообщение a1,..., an на языке конечного поля Zp. С этой целью они вырабатывают секретный ключ : 1,..., n. Далее, абонент A передает по открытому каналу связи абоненту B шифртекст a1 + 1,..., an + n .

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

На практике, как правило, последовательность вырабатывается детерминированным образом, но так, чтобы на конечном участке она “выглядела” бы как случайная. В первую очередь стремятся к тому, чтобы последовательность по модулю p имела максимальный период.

В частности, ее можно задать рекуррентным образом:

m+1 am + c (mod p), m 0. Тогда для того, чтобы согласовать ключ, достаточно произвести согласование только первого члена последовательности 0. Один из методов такого согласования предложен Диффи и Хеллманом. Он основан на использовании дискретного логарифма .

–  –  –

§ 3. Система шифрования, основанная на задаче о рюкзаке Предположим, что элементы открытого текста обозначаются kразрядными двоичными числами, где k — некоторое натуральное число. Например, для русского алфавита, состоящего из 31 буквы, каждую из них можно обозначить пятиразрядным двоичным числом от 0 = (00000)2 до 30 = (11110)2, т.е. а = 00000, б = 00001,..., е = 00101,..., н = 01101,..., т = 10010,... .

Далее, каждый пользователь выбирает следующие параметры:

1) сверх растущий набор a = (a1,..., ak ),

2) натуральное число m такое, что m a1 + a2 +... + ak,

3) натуральное число такое, что 1 m и (, m) = 1 .

По выбранным параметрам вычисляются:

1) натуральное число такое, что 1 (mod m), где 1 m,

2) k-элементный набор w = (w1, w2,..., wk ), где ws = as, s = 1,..., k .

Заметим, что набор w не обязан быть сверх растущим .

Например, если возьмем сверхрастущий набор a = (a1,..., a5 ) = (2, 3, 7, 15, 31), m = 61 2 + 3 + 7 + 15 + 31 = 58, = 17, (17, 61) = 1, то получим = 18 и w = (w1,..., w5 ) a = (34, 51, 58, 11, 39) (mod 61) .

Пусть, теперь, требуется передать по открытому каналу связи сообщение (1, 2,..., k ), где s принимают значения либо 0, § 3. Рюкзачная система шифрования 75

–  –  –

рюкзака. Имеем единственное решение S = 24 = 2 + 7 + 15, (1) = (0, 1, 1, 0, 1), 9 = 2 + 7, (2) = (0, 0, 1, 0, 1), 34 = 31 + 3, (3) = (1, 0, 0, 1, 0) .

Тем самым, прочитано слово “НЕТ” .

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

Рассмотрим на примере способ шифрования биграмм. Пусть задан сверх растущий набор из десяти чисел a = (a1, a2,..., a10 ) = (2, 3, 7, 31, 60, 119, 239, 477, 954), причем as = 1907 .

s=1 В качестве модуля m возьмем число 1909. Положим = 3. Отсюда получим = 1273, поскольку 1 (mod m) и 3 · 1273 1 (mod 1909) .

Находим открытый ключ KE шифрования w = a = (w1, w2,..., w10 ) = (6, 9, 21, 45, 93, 180, 357, 717, 1431, 953) .

Секретный ключ KD дешифрования имеет вид KD = (m, ) = (1909, 1273) .

Пусть, как и раньше, по открытому каналу связи требуется передать слово “НЕТ”. Разобьем слово НЕТ на биграммы (в качестве пустышки возьмем букву а). Получим НЕ-ТА. В открытом тексте буквы обозначаются пятизначными двоичными числами. Имеем Н есть 01101, E — 00101, Т — 10010, А — 00000. Отсюда находим НE — 0110100101, ТА — 1001000000 .

Далее шифруем биграммы НЕ и ТА. Соответственно имеем 1 · 6 + 0 · 9 + 1 · 21 + 0 · 45 + 0 · 93 + 1 · 180+ +0 · 357 + 1 · 717 + 1 · 1431 + 0 · 953 446 (mod 1909), 0 · 6 + 0 · 9 + 0 · 21 + 0 · 45 + 0 · 93 + 1 · 180+ +0 · 357 + 0 · 717 + 0 · 1431 + 1 · 953 1310 (mod 1909) .

Абоненту передается два числа: 446, 1310. Он начинает дешифровку домножением этих чисел на = 1273 и нахождением наименьших положительных вычетов по модулю 1909.

Получает набор двух чисел:

785, 1073. Наконец, решая аддитивную задачу об укладке рюкзака, находит ответ .

§ 4. Система шифрования RSA 77 § 4. Система Ривеста – Шамира – Адельмана шифрования с открытым ключом Перейдем к построению системы RSA шифрования с открытым ключом. Отметим основные элементы, необходимые для этой системы .

1) Надо уметь находить большие простые числа, по крайней мере, два простых числа p и q .

2) Кодирование сообщений в системе RSA основывается на числе n = pq .

3) В основе декодирования системы RSA лежит знание чисел p и q .

4) Безопасность системы RSA обеспечивается алгоритмической сложностью разложения на простые сомножители числа n .

Сначала опишем схему процесса шифрования и дешифрования .

Пусть требуется передать по открытому каналу связи сообщение “МУДРОМУ ДОСТАТОЧНО”. Подготовим его к передаче с помощью системы RSA. Сначала возьмем p = 73, q = 97, n = pq = 7081 .

Представим текст сообщения в виде последовательности классов вычетов по модулю n = 7081. Каждую букву русского алфавита и пробел заменим двузначным числом. Имеем следующую таблицу .

–  –  –

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

При расшифровке шифртекста находится система блоков чисел .

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

Шифрование сообщения. Сначала выберем различные простые числа p и q. Найдем число n = pq и значение функции Эйлера (n) = (p 1)(q 1). Далее, выбираем число e такое, что (e, (n)) = 1, 1 e (n). Пару чисел (n, e) называют шифрующим ключом и она объявляется открытым ключом. Пусть a обозначает любой блок сообщения, причем 1 a n. Тогда зашифрование происходит по следующему правилу: E(a) ae (mod n), т.е. блок b зашифрованного сообщения имеет вид b = E(a) ae (mod n) .

Дешифрование сообщения. Найдем элемент d, обратный к e по модулю (n), т.е. de 1 (mod (n)). Пара чисел ((n), d) называется секретным ключом или дешифрующим ключом системы шифрования RSA. Пусть b — блок зашифрованного сообщения. Тогда дешифрование D(b) получается из соотношения D(b) bd (mod n) .

Докажем, теперь, что D(E(a)) = a. Рассмотрим сначала случай (a, n) = 1. Используя теорему Эйлера, т.е. утверждение a(n) 1 (mod n), найдем d D(E(a)) (ae ) = aed a (mod n) .

Пусть, теперь (a, n) 1. Так как n = pq, то либо p | a, либо q | a. Без ограничения общности будем считать, что p | a. Тогда a 0 (mod p) .

Следовательно, aed 0 a (mod p). Аналогично, доказывается, что aed a (mod q). Отсюда получим, что p | (aed a), q | (aed a), n = pq | (aed a), aed a (mod n), т.е. при любом целом числе a имеем D(E(a)) = a .

Пример 1. Этот замечательный пример взят из [1] .

Зашифруем аббревиатуру RSA с помощью системы шифрования RSA. Возьмем простые числа p = 17 и q = 31. Имеем n = pq = 17 · 31 = 527 и (n) = (p 1)(q 1) = 16 · 30 = 480. Возьмем e = 7. Получим (e, (n)) = (7, 480) = 1, 1 7 480. Найдем элемент d, обратный к e = 7 по модулю (n) = 480. Для этого с помощью алгоритма Евклида находим целые числа и такие, что e · + (n) · = 1 .

Имеем 480 = 7 · 68 + 4, 7 = 4 · 1 + 3, 4 = 3 · 1 + 1 .

§ 4. Система шифрования RSA 79

–  –  –

407343 33 (mod 527) .

Переходя отсюда к буквенной записи, имеем аббревиатуру RSA .

Приведем несколько простейших случаев, когда шифрование методом RSA будет нестойким .

Разложение на множители числа n, вычисление (n) и дешифрование сообщения. Пусть при данном натуральном числе n значение функции Эйлера (n) известно. Тогда легко находится секретный ключ ((n), d). В частности, если известно разложение числа n на простые сомножители n = pq, где p и q — простые числа, то (n) = (p 1)(q 1) .

Пусть, теперь, известны числа n и (n) и известно, что число n является произведением двух простых сомножителей, причем сами сомножители неизвестны. Тогда можно найти простые числа p и q такие, что n = pq, т.е. найти разложение на простые сомножители числа n. Имеем (n) = (p 1)(q 1) = pq (p + q) + 1 = n (p + q) + 1, т.е. находим p + q = n (n) + 1 .

Зная произведение pq и сумму p+q, по теореме Виета заключаем, что числа p и q являются корнями квадратного уравнения x2 (n (n) + 1)x + n = 0 .

С другой стороны, используя соотношение (p + q)2 (p q)2 = 4pq = 4n, числа p и q можно найти из системы линейных уравнений { p + q = (n) + 1, n p q = (n (n) + 1)2 4n .

–  –  –

Дешифрование сообщения и малый показатель степени e открытого ключа. Пусть несколько абонентов в открытом ключе криптосистемы RSA имеют одну и ту же степень e. Например, три абонента имеют открытые ключи (n1, e), (n2, e) и (n3, e) с взаимно простыми модулями n1, n2, n3. Пусть один из абонентов посылает циркулярное числовое сообщение M. По условию шифрования выполняются неравенства 0 M min {n1, n2, n3 }. Наблюдатель может получить три шифрованных текста y1, y2, y3 вида

–  –  –

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

Другими словами, хэш-функцией называется любая функция y = h(x1 x2... xn ) сообщения x = x1 x2... xn произвольной длины n ставит в соответствие целое число y фиксированной длины .

Примером хэш-функции может служить контрольная сумма для сообщения x1 x2... xn, т.е. функция h(x1 x2... xn ) x1 + x2 +... + xn (mod 2 ), где является максимальным размером машинного слова .

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

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

(n)

1) Для любого заданного x из Z2 значение функции y = h(x) должно вычисляться достаточно “легко” и “быстро” .

2) Для любого y практически невозможно найти x такое, что y = h(x) .

3) Для любого сообщения x практически невозможно найти x = x такое, что h(x ) = h(x) .

4) Практически невозможно найти пару различных сообщений x и x таких, что h(x ) = h(x) .

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

Следующий пример хэш-функции предложил Дамгард (см., например, [18], с.112–113). Пусть задано множество E наборов длины

n, составленных из 0 и 1. На этом множестве определим две односторонние функции f0 и f1 со следующими свойствами:

1) отображения f0 и f1 являются взаимно однозначными из E на E, т.е. эти функции задают перестановки элементов множества E;

2) пару (a, b) из декартова произведения множеств E E называют встречей функций f0 и f1, если f0 (a) = f1 (b.) Будем говорить, что пара функций f0 и f1 не встречаются с друг другом, если алгоритмически сложно найти их встречу. Будем считать, что f0 и f1 не встречаются с друг другом .

Пусть {0, 1} обозначает множество всех конечных последоваХэш-функции 83 тельностей, составленных из 0 и 1. Итак, пусть заданы две односторонние функции f0 и f1 со свойствами 1) и 2), и некоторый элемент e E. Определим сжимающую функцию F, заданную на множестве {0, 1}, следующим образом F : {0, 1} E, причем для любого x = x1 x2... xk из {0, 1} имеем F(x) = fx1 (fx2 (... fxk (e)...)) .

Утверждение 1. Пусть функции f0 и f1 являются односторонними и не встречаются друг с другом. Тогда функция F не имеет совпадений .

Предположим, что F имеет по крайней мере одно совпадение .

Выберем среди слов, для которых есть совпадение, слово с минимальной длиной. Если их несколько, то возьмем любое из них с минимальной длиной. Таким образом, найдутся различные x = x1 x2... xk и x = x x... x такие, что F(x) = F(x ). Без ограничения общноk сти можно считать, что k k. Пусть сначала x = x. Тогда точки a = fx1 (F(x)) и b = fx (F(x )) дают встречу функций fx1 и fx, одна из которых есть f0, а другая — f1. Это противоречит условию утверждения. Пусть, теперь, x1 = x. Тогда пара точек x2... xk и x... x 1 2 k образует еще одно совпадение для функции F, но с меньшей длиной слова, что противоречит выбору слов x и x. Это и доказывает, что функция F не имеет совпадений .

Отсюда имеем, что F представляет собой хэш-функцию .

Пример 1. Пусть g — первообразный корень по простому модулю p, p |c и |c| 1 (mod p) .

Определим функции f0 (x) g x (mod p) и f1 (x) = cf0 (x). Покажем, что эти функции не встречаются друг с другом. Предположим противное, т.е. найдется пара чисел a и b такая, что f0 (a) = f1 (b). Это означает, что g a cg b (mod p). Последнее эквивалентно тому, что g ab c (mod p), т.е. f0 (a b) = c. Следовательно, число c находится как прообраз при отображении обратном f0, но это противоречит тому, что функция f0 — односторонняя .

Пример 2. Пусть n = pq, где p и q — простые числа, сравнимые с 1 по модулю 4, и — нечетное натуральное число, не превосходящее (n) .

Определим функции f0 (x) xe (mod n) на вычетах по модулю n, которые не являются квадратами по модулю n и f1 (x) x2 (mod n). Покажем, что эти функции не встречаются друг с другом .

Предположим противное, т.е. найдется пара чисел a и b такая, что f0 (a) = f1 (b). Это означает, что ae b2 (mod n). Последнее эквивалентно тому, что ae(p1)/2 1 (mod p) и ae(q1)/2 1 (mod q). Так как вычет a по модулю n не является квадратом, то a не является квадратичным вычетом по крайней мере по одному из чисел p и q .

84 Глава VI. Асимметричные шифры Это означает, что хотя одно из последних сравнений противоречиво, поскольку оно превращается либо в сравнение 1 1 (mod p), либо в сравнение 1 1 (mod q). Таким образом, f0 и f1 являются парой функций, которые не встречаются друг с другом .

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

Далее, на основе стойкой шифрующей или односторонней функции с m-битовым входом используется некоторое итерационное соотношение вида Hs = E(Hs1, Ms ), 1 s n, причем число H0 выбирается специальным способом .

Наконец, число H = Hn принимают за значение хэш-функции .

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

Глава VII

ЗАДАЧИ ПО ТЕОРИИ ЧИСЕЛ

–  –  –

в) Предположим, что простых чисел вида p 1 (mod 4) конечное число: p1,..., pn. Число (2p1... pn )2 + 1 в качестве своих простых делителей будет иметь только простые числа вида 4k + 1 и они все будут отличны от чисел p1,..., pn. Наименьший, отличный от единицы, среди делителей числа (2p1... pn )2 + 1 будет простым .

Это противоречит предположению об исчерпании всех простых вида 4k + 1 числами p1,..., pn. Следовательно, простых чисел вида p 1 (mod 4) бесконечно много .

г) Пусть простые числа вида 6k + 1 исчерпываются числами p1,..., pn. Число (2p1... pn )2 +3 имеет простые делители только вида 6k+1, наименьший из которых, отличный от единицы, будет простым и отличным от p1,..., pn. Следовательно, предположение о том, что простых чисел вида 6k + 1 конечно, не имеет места .

§ 1. Квадратичные вычеты и невычеты по простому модулю 93

–  –  –

Следовательно, предположение о разрешимости сравнения x4 + 1 (mod p) неверно .

23. a) При нечетном простом числе p число 1 будет биквадратичным вычетом по модулю p тогда и только тогда, когда p 1 (mod 8) .

б) Существует бесконечно много простых чисел вида 8k + 1 .

a) Пусть p 1 (mod 8). Тогда (p 1)/2 квадратичный вычет по модулю p удовлетворяет сравнению x(p1)/2 1 (mod p). Предположим, теперь, что сравнение x4 1 (mod p) не имеет решений .

Тогда сравнению x(p1)/4 1 (mod p) не удовлетворяет ни один квадратичный вычет по модулю p. Поскольку они удовлетворяют либо сравнению x(p1)/4 1 (mod p), либо сравнению x(p1)/4 1 (mod p), все (p 1)/2 квадратичных вычета по модулю p удовлетворяют второму сравнению. Но это невозможно, поскольку количество 94 Глава VII. Задачи по теории чисел

–  –  –

ло p принадлежит одной из (4q2... qk )/2k с разностью 4q2... qk и некоторыми начальными членами a, взаимно простыми с 4q2... qk .

Используя квадратичный закон взаимности, найдем, что число p удовлетворяет условиям

–  –  –

По критерию Эйлера имеем a(p1)/2 1 (mod p). Отсюда получим a(p1)/4 ±1 (mod p). Если a(p1)/4 1 (mod p), то a2(p+3)/8 a(p+3)/4 a (mod p) .

Тогда в этом случае искомое решение имеет вид x ±a(p+3)/8 (mod p) .

Пусть теперь a(p1)/4 1 (mod p). Поскольку 2 — квадратичный невычет по модулю p, по критерию Эйлера имеем 2(p1)/2 1 (mod p). Следовательно, ( )2 2(p1)/4 a(p+3)/8 2(p1)/2 a(p+3)/4 a (mod p) .

–  –  –

Докажем единственность решения (x, y). Предположим, что (x1, y1 ) — другое решение, удовлетворяющее условию задачи. Имеем § 4. Извлечение квадратного корня по составному модулю 117

–  –  –

найдется простой делитель q числа n такой, что p | (q q 1 ). Далее, (p, q) = 1, поэтому p | q 1 .

Положим q = up + 1. Имеем n = kp2 + 1 = (up + 1)(vp + 1). Следовательно, uvp + u + v = kp. Отсюда при некотором натуральном s находим, что u + v = ps. Далее получим противоречивое неравенство p uv k p .

Таким образом предположение о том, что число n составное, неверно .

–  –  –

является первообразным корнем по модулю 2p .

Утверждение следующей задачи дает способ разыскания первообразных корней по некоторому модулю m. Из утверждения предыдущей задачи имеем, что m равно одному из значений 2, 4, p, 2p, где p — нечетное простое число и — натуральное число .

§ 8. Распознавание простых и составных чисел 139

–  –  –

Тогда число N является простым .

Пусть q — простое число, являющееся делителем N 1 и число aq по модулю N принадлежит показателю q. Тогда из условия aN 1 1 (mod N ) следует, что q | N 1, т.е. при некотором натуq ральном числе uq имеем N 1 = q uq .

Докажем, что (q, uq ) = 1. Предположим противное, т.е. q | uq .

Тогда при некотором натуральном vq получим N 1 = q qvq. Отсюда, используя условие задачи, получим противоречивое соотношение 1 aq vq = a(N 1)/q 1 (mod N ) .

q q

–  –  –

Решая эту систему уравнений и используя утверждение задачи 3, находим u = (1)m1 (pqm1 qpm1 ) = 0, v = (1)m1 (pqm qpm ) = 0 .

Поскольку qm q = uqm + vqm1, целые числа u и v имеют противоположные знаки. Далее по утверждению задачи 8 выражения qm pm и qm1 pm1 имеют разные знаки, следовательно, выражения u(qm pm ) и v(qm1 pm1 ) имеют одинаковый знак .

Таким образом, находим

–  –  –

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

Пусть иррациональное число 1 принадлежит дискриминанту m2 D. Тогда по утверждению предыдущей задачи этому дискриминанту принадлежат все остатки n разложения числа в непрерывную дробь, причем, начиная с некоторого номера n0, все они будут приведенными числами. Количество приведенных чисел, принадлежащих данному дискриминанту, конечно. Поэтому найдутся натуральные числа k 1 и l n0 такие, что l = l+k. Тогда имеем = [a0, a1,..., al1, l ] = [a0, a1,..., al1, al,..., al+k1, l+k ] .

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

Докажем теперь вторую часть утверждения. Пусть l является минимальным номером, при котором l = l+k. Предположим, что l 1, т.е. разложение числа не чисто периодическая непрерывная дробь. Поскольку — приведенное иррациональное число, имеем 1, 1 .

–  –  –

I. Алфавитное кодирование

1. Понятие алфавита и слова в алфавите. Кодирование сообщения. Алфавит сообщений. Алфавит кодирования. Однозначное кодирование .

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

II. Помехоустойчивость

1. Многоразрядный код. Расстояние Хемминга. Неравенство треугольника. Теорема об исправлении ошибок в кодах с любым заданным расстоянием .

2. Пример множества 5-разрядных двоичных кодов, в которых исправляется одна возможная ошибка. Способ построения множества 5-разрядных двоичных кодов, имеющих кодовое расстояние, равное 3 .

III. Передача сообщения по каналу без шума

1. Пример построения кода Фано в случае 4-х буквенного алфавита сообщений и 2-х буквенного алфавита кодирования. Средняя длина кодового слова. Общая схема построения кода Фано, построение таблицы .

2. Бинарное дерево для двоичного кода Фано. Необходимое и достаточное условия существования префиксного кода заданного объема и с заданным набором длин слов. Неравенство Крафта – МакМиллана. Необходимое условие существования однозначно декодируемого кода. Две теоремы об оценке средней длины кодовых слов .

Теорема о минимальной длине префиксного кода

3. Построение оптимального кода Хафмена. Пример .

IV. Способы защиты информации

1. Защита информации с помощью перестановки. Маршрутные перестановки. Шифры вертикальной замены. Решетка Кардано .

2. Защита информации с помощью шифра замены. Система Цезаря и система Цезаря с ключевым словом. Блочные и поточные шифры замены. Примеры блочных шифров замены: шифры Плейфера и Хилла .

Экзаменационные вопросы 181 V. О симметричных шифрах VI. О шифровании с открытым ключом VII. Конечные поля. Циклические коды

1. Конечные поля. Неприводимые многочлены над конечным полем .

2. Циклические коды .

VIII. Рекуррентные соотношения. Производящие функции

1. Примеры рекуррентных соотношений .

2. Последовательность Фибоначчи .

3. Линейные рекуррентные уравнения второго порядка .

4. Линейные рекуррентные уравнения произвольного порядка .

5. Рекуррентные соотношения в кольцах вычетов .

IX. Арифметический подход к искажению знаков в шифрах простой замены и Виженера

1. Примеры шифров со “сжатием” алфавита .

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

3. Метод искажения знаков в шифре простой замены с помощью возведения в квадрат .

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

5. Анализ методов искажения знаков в шифре простой замены .

6. Применение китайской теоремы об остатках к шифру Виженера .

7. Арифметический вариант шифра Виженера .

Литература [1] Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В .

Основы криптографии: Учебное пособие, 2-е изд., испр. и доп. — М.: Гелиос АРВ, 2002. — 480 с .

[2] Архипов Г. И., Садовничий В. А., Чубариков В. Н. Лекции по математическому анализу. Изд. 6-е. — М.: Дрофа, 2008, 640 с .

[3] Аршинов М. Н., Садовский Л. Е. Коды и математика. — М.: Наука, Гл. ред. физ.-мат. лит., 1983 (Библитечка “Квант”. Вып. 30) .

[4] Бабаш А.В., Шанкин Г.П. Криптография. — М.: СОЛОНПРЕСС, 2007. — 511 с .

[5] Баричев С. Криптография без секретов (http://www.artelecom.ru/library/books/swos/index/html) — 44 c .

[6] Bach E., Shallit J. Algorithmic number theory, Volume I: Ecient algorithms. — Massachusetts, MIT Press 1996 .

[7] Брассар Ж. Современная криптология. — М.: ПОЛИМЕД, 1999. — 176 с .

[8] Ван-дер-Варден Б. Л. Алгебра. Пер. с нем. — М.: Наука, 1976, 648 с .

[9] Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. 2-е изд., доп. — М.: МЦНМО, 2006. — 336 с .

[10] Виноградов И. М. Основы теории чисел. — М.: Наука, Гл. ред .

физ.-мат. лит., 1983 .

[11] Гашков С. Б., Чубариков В. Н. Арифметика. Алгоритмы. Сложность вычислений. — М.: Дрофа., 2004 .

[12] Грин Д., Кнут Д. Математические методы анализа алгоритмов. — М.: Мир, 1987 .

[13] Davenport H. A remark on a continued fractions // Michigan Math .

J., 1964. 11, 343–344 .

[14] Die W., Hellman M E. New directions in cryptography // IEEE Trans. of Inf. Theory. 1976, IT-22 .

[15] Dickson L. E. History of the theory of numbers. — Carnegie Inst .

of Washington, 1919. Reprinted by Chelsea Publishing, New York, 1971 .

[16] El Gamal T. A public key cryptosystem and a signature scheme based on discrete logarithms // IEEE Trans. on Inf. Theory, IT-31 .

1985, 469–472 .

Литература 183 [17] Жельников В. Криптография от папируса до компьютора.

— М.:

ABF, 1996. — 335 с .

[18] Земор Ж. Курс криптографии. — М.–Ижевск: НИЦ “Регулярная и хаотическая динамика”; Институт компьютерных исследований, 2006. — 256 с .

[19] Kahn D. The Codebreakers. — N.-Y., 1967 .

[20] Карацуба А. А., Офман Ю. П. Умножение многозначных чисел на автоматах // ДАН СССР. 1962, т. 145, №2, с.293–294 .

[21] Кнут Д. Э. Искусство программирования. Т.II. 3-е изд.: Пер .

с англ. — Москва – Санкт-Петербург – Киев: Издат.дом “Вильямс”, 2000, 832 с .

[22] Коблиц Н. Курс теории чисел и криптографии. — М.: Научное изд-во “ТВП”, 2001 .

[23] Колмогоров А. Н. Три подхода к понятию информации // Проблемы передачи информации, 1965, т. 1, с.3–11 .

[24] Коутинхо С. Введение в теорию чисел. Алгоритм RSA. — М.:

Постмаркет, 2001 .

[25] Маховенко Е. Б. Теоретико-числовые методы в криптографии. — М.: “Гелиос АРВ”, 2006 .

[26] Miller J. C. P., Wheeler D. J. Large prime numbers // Nature, 1951 .

168. 838 .

[27] Минеев М. П., Чубариков В. Н. Задача об искажении частоты появления знаков в шифре простой замены// Математические вопросы кибернетики, 2007, вып. 16, с.242–245 .

[28] Минеев М. П., Чубариков В. Н. Об одном методе искажения частоты появления знаков в шифре простой замены // Докл. РАН, 2008, т. 420, №6, с.736–738 .

[29] Минеев М. П., Чубариков В. Н. К вопросу об искажении частот появления знаков в шифре простой замены // Докл. РАН, 2009, т. 426, №1, с.6–8 .

[30] Молдовян А. А., Молдовян Н. А.,Советов Б. Я. Криптография. — СПб.: Изд-во “Лань”, 2001. — 224 с .

[31] Нечаев В. И. Элементы криптографии (Основы теории защиты информации): Учеб. пос. для ун-тов и пед. вузов — М.:Высш.шк., 1999. — 109 c .

[32] Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. Пер. с англ. — М.: Мир, 1976, 594 с .

[33] Поздняков С. Н., Рыбин С. В. Дискретная математика. — М.:

Изд. центр “Академия”., 2008. — 447 c .

[34] Полиа Г., Сег Г. Задачи и теоремы из анализа. Пер. с нем. Изд .

е 3-е. Ч. I, II. — М.: Наука, 1978 .

184 Литература

–  –  –

Издательство «Попечительский совет Механико-математического факультета МГУ им. М. В. Ломоносова»

Подписано в печать 01.09.2010 .

Формат 6090 1/16. Усл. печ. л. 11,75 .

Тираж 500 экз. Заказ 15 .

Отпечатано с оригинал-макета на типографском оборудовании




Похожие работы:

«Туроператор по Израилю "НТИЦ Искра" предлагает! Экскурсионный тур в Израиль на 8 дней и 7 ночей с отдыхом Эйлате. Рождество Христово на Святой Земле в Израиле. № 1655 Rojdestvo Eilat. Заезды в Израиль: Понедельник. 04.01.2016 11.01.2016.Проживание в Израиле: Иерусалим 3 ночи;Эйлат...»

«35B-1 ГРУППА 35B АНТИБЛОКИРОВОЧНАЯ ТОРМОЗНАЯ СИСТЕМА (ABS) СОДЕРЖАНИЕ ОБЩАЯ ИНФОРМАЦИЯ......... 35B-2 КОНСТРУКТИВНАЯ СХЕМА...... 35B-6 ДАТЧИК... ........................ 35B-6 ИСПОЛНИТЕЛЬНЫЕ МЕХАНИЗМЫ.... 35B-6 ЭБУ ABS......»

«ХАЧАЙ  МИХАИЛ  ЮРЬЕВИЧ КОМИТЕТНЫЕ РЕШЕНИЯ НЕСОВМЕСТНЫХ СИСТЕМ ОГРАНИЧЕНИЙ И МЕТОДЫ ОБУЧЕНИЯ  РАСПОЗНАВАНИЮ 01.01.09  —  дискретная  математика  и  математическая  кибернетика Автореферат  диссертации  на  соискание  ученой  степени доктора  физико-...»

«"СОГЛАСОВАНО ",Руковокитель ГЦИ СИ тf2ге гнсегородский ЦСМ" И. И. Решетник 2010 г. Внесены в Государственный реестр средств измерений комплексы Регистрационный СУТОЧНОГО N°iС. ' •5 МОНИТОРИРОВАНИЯ ЭКГ "КАРДИО "Астел" Взамен )Ч ;! Выпускаются по ТУ 9441-001-33453722-2003 НАЗНАЧЕНИЕ И ОБЛАСТЬ ПРИМЕНЕНИЯ Комплексы суточного...»

«Приложение № 2 к приказу от "15" 01 2018 г. № 7 Состав государственных экзаменационных комиссий Нижегородского государственного технического университета им. Р. Е. Алексеева (НГТУ) на 2018 год Основные професси...»

«www.scientifitrends.de e-mail: orgcom@scientifictrends.de ПРОГРАММА КОНФЕРЕНЦИИ Современный этап развития научно-технического прогресса ‘2018 The current stage of development of scientific and technological progress' 2018 Сучасний етап розвитку науково-технічного прог...»

«Национальная академия наук Украины Донецкий физико-технический институт им. А.А. Галкина ВЫСОКИЕ ДАВЛЕНИЯ – 2012 Фундаментальные и прикладные аспекты 23–27 сентября 2012 г . ТЕЗИСЫ Судак, Крым, Украина В367.1...»

«МАШИНА СУШИЛЬНАЯ “ВЕГА” ВС-25 РУКОВОДСТВО ПО ЭКСПЛУАТАЦИИ ВС-25.00.00.000 РЭ Ввиду того, что конструкция машин и отдельные комплектующие части постоянно совершенствуются, возможны изменения, не отраженные в настоящей документации. Изменения, влияющие на эксплуатацию и техническое обслуживание...»

«МЕЖГОСУДАРСТВЕННЫЙ СОВЕТ ПО СТАНДАРТИЗАЦИИ, МЕТРОЛОГИИ И СЕРТИФИКАЦИИ (МГС) INTERSTATE COUNCIL FOR STANDARDIZATION, METROLOGY AND CERTIFICATION (ISC) ГОСТ МЕЖГОСУДАРСТВЕННЫЙ 32870“ СТАНДАРТ Д ороги автом обильны е общего пользования МАСТИКИ БИТУМНЫЕ Технические требования Издание официальное М осква С та нд а рти н ф орм еле...»

«^4^ БЕЛЯЕВА Елена Юрьевна РАЗРАБОТКА ТЕХНОЛОГИЙ МНОГОАТОМНЫХ СПИРТОВ НЕОПЕНТИЛГЛИКОЛЯ И ЭТРИОЛА НА ОСНОВЕ МАСЛЯНЫХ АЛЬДЕГИДОВ 05 17.04-Технология органических веществ Автореферат диссертации на соискание ученой степ...»

«Elec.ru Электротехническая библиотека Elec.ru Ф ЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ТЕХНИЧЕСКОМУ РЕГУЛИРОВАНИЮ И МЕТРОЛОГИИ НАЦИОНАЛЬНЫЙ ГОСТ Р м э к СТАНДАРТ 62004— РОССИЙСКОЙ ФЕДЕРАЦИИ ПРОВОЛОКА ИЗ ТЕРМОСТОЙКОГО АЛЮМИНИЕВОГО СПЛАВА ДЛЯ ПРОВОДА ВО...»







 
2019 www.librus.dobrota.biz - «Бесплатная электронная библиотека - собрание публикаций»

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