Основы криптографии
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?иведением конечного результата по модулю п
(а + b) mod n == ((a mod ri) + (b mod и)) mod n
(а - b) mod n == ((a mod и) - (b mod и)) mod n
(а * b) mod n == ((a mod ri) * (b mod и)) mod n
(а * (b+c)) mod n == (((a*b} mod ri} + ((a*c) mod и)) mod n
Вычисление mod n часто используется в криптографии, так как вычисление дискретных логарифмов и квадратных корней mod n может быть нелегкой проблемой. Арифметика вычетов, к тому же, легче реализуется на компьютерах, поскольку она ограничивает диапазон промежуточных значений и результата. Для k-битовых вычетов n, промежуточные результаты любого сложения, вычитание или умножения будут не длиннее, чем 2 k бит. Поэтому в арифметике вычетов мы можем выполнить возведение в степень без огромных промежуточных peзультатов. Вычисление степени некоторого числа по модулю другого числа,
ax mod n,
представляет собой просто последовательность умножений и делений, но существуют приемы, ускоряющие это действие. Один из таких приемов стремится минимизировать количество умножений по модулю, другой -оптимизировать отдельные умножения по модулю. Так как операции дистрибутивны, быстрее выполнить возвeдение в степень как поток последовательных умножений, каждый раз получая вычеты. Сейчас вы не чувствуете разницы, но она будет заметна при умножении 200-битовых чисел.
Например, если вы хотите вычислить a8 mod n, не выполняйте наивно семь умножений и одно приведение по модулю:
(a * a * a * a * a * a * a * a) mod n
Вместо этого выполните три меньших умножения и три меньших приведения по модулю:
((a2 mod n)2 mod n)2 mod n
Точно также,
a16 mod n =(((a2 mod n)2 mod n)2 mod n)2 mod n
Вычисление ax, где x не является степенью 2, ненамного труднее. Двоичная запись представляет x в виде суммы степеней 2: 25 - это бинарное 11001, поэтому 25 = 24 + 23 + 20. Поэтому
25 mod n = (a*a24) mod n = (a* aS*a16) mod n =
= (a*(( a2)2)2*((( a2)2)2)2) mod n = (a*((( a*a2)2)2)2) mod n
С продуманным сохранением промежуточных результатов вам понадобится только шесть умножений:
(((((((a2 mod ri}* a)2 mod и)2 mod и)2 mod и)2 mod и)2 *a) mod n
Такой прием называется цепочкой сложений , или методом двоичных квадратов и умножения. Он использует простую и очевидную цепочку сложений, в основе которой лежит двоичное представление числа. На языке С это выглядит следующим образом:
long qe2(unsigned long x, unsigned long у, unsigned long n) {
unsigned long s, t, u; i;
s=l; t=x; u=y; (u) {
if(u&l) s=(s*t)%n; u>>l;
t=(t*t)%n;
}(s)
}
А вот другой, рекурсивный, алгоритм:
unsigned long fast_exp(unsigned long x, unsigned long у, unsigned long N)
{
unsigned long tmp;
if(y==l) return(x % N); (l^(x&l)) {
tmp= fast_exp(x,y/2,N);
return ( (tmp*tmp) %N) ;
else {
tmp = fast_exp(x,(y-l)/2,N);
tmp = (tmp*tmp) %N;
tmp = (tmp*x)%N;
return (tmp) ;
}
return 0;
Этот метод уменьшает количество операций, в среднем, до 1.5* k операций, где k - длина числа x в битах. Найти способ вычисления с наименьшим количеством операций - трудная проблема (было доказано, что послeдовательность должна содержать не меньше k- \ операций), но нетрудно снизить число операций до 1 . 1 * k или даже лучше при больших k.
Операция, обратная возведению в степень по модулю и, вычисляет дискретный логарифм Я дальше вкратце рассмотрю эту операцию.
Простые числа
Простым называется целое число, большее единицы, единственными множителями которого является 1 и оно само: оно не делится ни на одно другое число. Два - это простое число. Простыми являются и 73, 2521, 2365347734339 и 275б839-1. Существует бесконечно много простых чисел. Криптография, особенно криптография с открытыми ключами, часто использует большие простые числа (512 бит и даже больше).
Наибольший общий делитель
Два числа называются взаимно простыми, если у них нет общих множителей кроме 1 . Иными словами, e c-ли наибольший общий делитель а и n равен 1 . Это записывается как:
НОД(а,и)=1
Взаимно просты числа 15 и 28. 15 и 27 не являются взаимно простыми, а 13 и 500 - являются. Простое число взаимно просто со всеми другими числами, кроме чисел, кратных данному простому числу.
Одним из способов вычислить наибольший общий делитель двух чисел является алгоритм Эвклида. Эвклид описал этот алгоритм в своей книге, Элементы, написанной в 300 году до нашей эры. Он не изобрел его. Историки iитают, что этот алгоритм лет на 200 старше. Это самый древний нетривиальный алгоритм, который дошел до наших дней, и он все еще хорош. Кнут описал алгоритм и его современные модификации в [863]. На языке С:
/* возвращает НОД (gcd) x и у */
int gcd (int x, int у) {g;(x < 0)(у < 0)
у = -у;
if (x + у == 0 ) ERROR ;
g = у;(x > 0) { g = x; = у % x;
у = g;
}
return g;
}
Обратные значения по модулю
Помните, что такое обратные значения? Обратное значение для 4 - 1/4, потому что 4*1/4 =1. В мире вычетов проблема усложняется:
*;c = 1 (mod 7)
Это уравнение эквивалентно обнаружению x и k, таких что
x = lk+l
где x и k - целые числа. Общая задача состоит в нахождении x, такого что
= (a*x) mod n
Это также можно записать как
а"1 =x (mod w)
Проблему обратных значений по модулю решить нелегко. Иногда у нее есть решение, иногда нет. Например, обратное значение 5 по модулю 14 равно 3. С другой стороны у числа 2 нет обратного значения по модулю 14.
В общем случае у уравнения а"1 = x (mod ri) существует единственное решение, если a и n взаимно просты. Если a и n не являются взаимно простыми, то а"1 = x (mod ri) не имеет решений. Если n является простым числом, то любое число от 1 до n -1 взаимно просто с n и имеет в точности одно обратное значение по модулю п.
Так, хорошо. А теперь как вы собираетесь искать обратное