Криптоанализ систем шифрования, основанных на сложности задачи факторизации

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

Существует также другой переборный метод (метод Ферма), который основан на представлении числа n в виде разности квадратов:

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

(2).

Не каждая пара чисел, удовлетворяющая ему, позволяет разложить n на множители. Для нахождения чисел, связанных соотношением (2), Лежандр использовал непрерывные дроби. В его работе описано некоторое усовершенствование метода Ферма.

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

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

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

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

Рассмотрим еще один субъкспоненциальный алгоритм факторизации — метод Диксона. Пусть — число, которое мы хотим разложить на множители, — некоторая постоянная, значение которой будет определено ниже. Факторной базой будем называть множество простых чисел таких, что (где). Обозначим символом k количество простых чисел в факторной базе, а Q (m);

наименьший неотрицательный вычет в классе .

Случайным перебором ищем числа такие, что:

.

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

Обозначим — векторы показателей в разложении на множители (- векторное пространство столбцов длины с координатами из).

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

Для вычисленных значений справедливо соотношение:

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

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

• § Стратегия LP (использование больших простых чисел)
• § Стратегия PS (применение алгоритма Полларда—Штрассена)
• § Стратегия EAS (стратегия раннего обрыва)

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

В качестве факторной базы выберем ограниченные по величине некоторым параметром простые числа, такие что, где — так называемый символ Якоби. Обозначим буквой s количество таких чисел.

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

т.е. Q (t) раскладывается в факторной базе. Тогда, обозначая B = H (t), получаем сравнение, и, накопив достаточно много таких соотношений, проводим исключение переменных и строим соотношение так же, как в алгоритме Диксона.

Эвристическая оценка сложности усовершенствованного алгоритма квадратичного решета составляет арифметических операций. Рекордное значение для факторизованных этим методом чисел составляет 129-значное RSA-число n. Метод квадратичного решета следует применять для факторизации, если число n не превосходит 10 110. Для чисел большей величины следует использовать алгоритмы решета числового поля. Решето числового поля по сути не является алгоритмом: это метод вычисления, состоящий из нескольких этапов, и каждый из этих этапов обслуживается несколькими алгоритмами. Описание этого метода слишком объемно, чтобы уместиться в рамках данной курсовой работы. На сегодняшний день алгоритмы решета числового поля и квадратичное решето Померанца — самые быстрые из известных алгоритмов факторизации больших чисел.

Практика

• 1) Метод экспоненциального ключевого обмена Диффи — Хеллмана
• s = секретный ключ. s = 2

g = открытое простое число. g = 5.

p = открытое простое число. p = 23.

a = секретный ключ Алисы. a = 6.

A = открытый ключ Алисы. A = ga mod p = 8.

b = секретный ключ Боба. b = 15.

B = открытый ключ Боба. B = gb mod p = 19.

Алиса знает.

p = 23.

g = 5.

a = 6.

A = 56 mod 23 = 8.

B = 5b mod 23 = 19.

• s = 196 mod 23 = 2
• s = 8b mod 23 = 2
• s = 196 mod 23 = 8b mod 23
• s = 2

Алиса не знает.

b=?

Боб знает.

p = 23.

g = 5.

b = 15.

B = 515 mod 23 = 19.

A = 5a mod 23 = 8.

• s = 815 mod 23 = 2
• s = 19a mod 23 = 2
• s = 815 mod 23 = 19a mod 23
• s = 2

Боб не знает а=?

Ева знает.

p = 23.

g = 5.

A = 5a mod 23 = 8.

B = 5b mod 23 = 19.

• s = 19a mod 23
• s = 8b mod 23
• s = 19a mod 23 = 8b mod 23

Ева не знает а=?

b=?

s=?

• 2) Алгоритм Эль-Гамаля
• 1. Шифрование

a. Допустим что нужно зашифровать сообщение .

b. Произведем генерацию ключей :

i. пусть. Выберем — случайное целое число такое, что .

ii. Вычислим .

iii. Итак, открытым является тройка, а закрытым ключом является число .

c. Выбираем случайное целое число такое, что 1 < k < (p? 1). Пусть .

d. Вычисляем число .

e. Вычисляем число .

f. Полученная пара является шифротекстом.

2. Расшифрование.

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

b. Вычисляем M по формуле:

c. Получили исходное сообщение .

• 3) Алгоритм RSA
• 1) Рассматиравать будем на примере слова БЛОГИ, но начнем сначала, а именно с создания пары ключей.
• 1. p=3 q=11
• 2. N=33
• 3. F (p, q)=20
• 4. D=3
• 5. 7*3 mod 20 =1, e=7

Шифруем слово.

2) Получаем цифровой эквивалент слова БЛОГИ я решил получить его с помошью вычисления их порядковых номеров в алфавите Цифровой эквивалент = 2(Б) 13(Л) 16(О) 4(Г) 10(И).

Шифрование производится по формуле yi=xie mod N, где xi цифровой эквивалент букве, остальные значения получены выше.

y1=27 mod 33=128 mod 33= 29.

y2=137 mod 33=62 748 517 mod 33= 7.

y3=167 mod 33=268 435 456 mod 33= 25.

y4=47 mod 33=16 384 mod 33= 16.

y5=107 mod 33=10 000 000 mod 33= 10.

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

Дешифрация.

3) Расшифрование производится по формуле xi=yid mod N

После небольших мучений с калькулятором мы получаем:

x1=293 mod 33=24 389 mod 33= 2.

x2=73 mod 33=343 mod 33= 13.

x3=253 mod 33=15 625 mod 33= 16.

x4=163 mod 33=4096 mod 33= 4.

x5=103 mod 33=1000 mod 33= 10.

Как видно если сравнить xi c порядковыми номерами букв мы получим слово БЛОГИ.

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

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

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

Для уменьшения возможного ущерба, вызванного несвоевременной заменой криптоалгоритма, потерявшего свою стойкость, желательна периодическая перепроверка стойкости криптоалгоритма. То обстоятельство, что любую задачу отыскания способа раскрытия некоторой конкретной криптосистемы можно переформулировать как привлекательную математическую задачу, при решении которой удается использовать многие методы той же теории сложности, теории чисел и алгебры, привело к раскрытию многих криптосистем. С развитием математики и средств вычислительной техники стойкость криптоалгоритма может только уменьшаться. Если влияние роста мощности компьютеров на стойкость алгоритмов еще можно предсказать с той или иной степенью точности (до настоящего момента каждое десятилетие скорость вычислений вырастала на порядок), то оценить перспективы научного прогресса не под силу даже ученым-криптографам с мировым именем. Так, в 1977 году Рон Ривест заявил, что разложение на множители 125-разрядного числа потребует 40 квадриллионов лет. Однако уже в 1994 г. было факторизовано число, состоящее из 129 двоичных разрядов!

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