2. Простые числа и их свойства

Натуральное число n>1 называется простым, если оно имеет в точности два различных натуральных делителя – 1 и n, в противном случае n называется составным.

Пример 4.4 Числа 2,3,7 являются простыми. Числа 4,6,8 – составными, так как их делителем является число 2.

Свойства простых чисел:

1. Если p₁ и p₂ – простые и , то p₁ не делится на p₂.

2. Пусть p – простое число, а n – натуральное, тогда n делится на p или наибольший общий делитель чисел n и p равен 1.

3. Если делится на простое число , то m делится на p или n делится на p.

4. Если делится на простое число , то существует , которое делится на .

Известна следующая теорема:

Теорема 4.1. Любое натуральное число n>1 либо просто, либо раскладывается в произведение простых чисел и притом единственным образом с точностью до порядка следования сомножителей: , где . Данное разложение называется канонической формой числа n.

Задача представления числа n в канонической форме называется задачей факторизации числа n.

Существенный с точки зрения криптографии факт состоит в том, что в арифметике не известно никакого эффективного алгоритма факторизации числа n. Никаких эффективных методов неизвестно даже в таком простом случае, когда необходимо найти два простых числа p и q, таких, что .

Известен ряд подходов, позволяющих выполнить проверку простоты целого числа n – решето Эратосфена, критерий Вильсона, тестирование на основе малой теоремы Ферма, тест Соловея-Штрассена, тест Рабина-Миллера и др.

Наибольшим общим делителем целых чисел a и b, обозначаемым как НОД(a,b) или просто (a,b), - это наибольшее целое, делящее одновременно числа a и b. Если (a,b)=1, то a и b называют взаимно простыми.

3. Числовые функции

В теории чисел и в криптографии большое значение имеют следующие числовые функции [Error: Reference source not found].

- определяет количество простых чисел от 2 до n. Точной формулы для вычисления данной функции не известно. Грубой оценкой данной функции является следующая: .

- определяет количество всех делителей числа n.

Пусть канонической формой числа n является . Тогда .

- определяет сумму всех делителей числа n,

- функция Эйлера, определяет количество чисел меньших n и взаимнопростых с n,

(4.1)

Пример 4.5

Для числа n=720 найдем , , .

Представим число 720 в канонической форме - .

Тогда

3. Методы и средства криптографической защиты

   1. Принципы криптографической защиты информации

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

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

Будем называть открытым текстом M исходное сообщение, которое шифруют для его сокрытия от посторонних лиц. Сообщение, формируемое в результате шифрования открытого текста, будем называть закрытым текстом (шифротекстом) С.

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

Существуют несколько основных типов криптоаналитических атак [Error: Reference source not found]. Реализация каждой из них предполагает, что злоумышленник знает применяемый алгоритм шифрования.

1. Криптоаналитическая атака при наличии только известного закрытого текста С.

2. Криптоаналитическая атака при наличии известного открытого текста (атака по открытому тексту). В этом случае, криптоаналитику известен открытый текст M и соответствующий ему закрытый текст C. Задача криптоаналитика состоит в нахождении ключа шифрования K для возможности прямой расшифровки последующих шифротекстов. Более мощным вариантом данного метода криптоанализа является криптоаналитическая атака при возможности выбора криптоаналитиком открытого текста.

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

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

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

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

1.Зашифрованный текст должен поддаваться чтению только при наличии секретного ключа шифрования.

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

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

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

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

6. Избыточность информации, вносимая в шифротекст за счет шифрования, должна быть незначительной.

7. Алгоритм шифрования должен допускать как программную, так и аппаратную реализацию.