Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С

• Название: Криптография 2е издание Протоколы, алгоритмы и исходные тексты на языке С
• Дата: 29.04.2022
• Размер: 3.25 Mb.
• Имя файла: Shnayer_Prikladnaya-kriptografiya.352928.pdf
• Тип: Протокол; #504484
• страница: 22 из 78

2
mod n)
2
mod n
Вычисление a x
, где x не является степенью 2, ненамного труднее. Двоичная запись представляет x в виде суммы степеней 2: 25 - это бинарное 11001, поэтому 25 = 24 + 23 + 20. Поэтому a
25
mod n = (a*a
24
) mod n = (a* a
8
*a
16
) mod n =
= (a*(( a
2
)
2
)
2
*((( a
2
)
2
)
2
)
2
) mod n = (a*((( a*a
2
)
2
)
2
)
2
) mod n
С продуманным сохранением промежуточных результатов вам понадобится только шесть умножений:
(((((((a
2
mod n)* a)
2
mod n)
2
mod n)
2
mod n)
2
mod n)
2
*a) mod n
Такой прием называется цепочкой сложений [863], или методом двоичных квадратов и умножения. Он и с- пользует простую и очевидную цепочку сложений, в основе которой лежит двоичное представление числа. На языке C это выглядит следующим образом:
unsigned long qe2(unsigned long x, unsigned long y, unsigned long n) {
unsigned long s, t, u;
int i;
s=1; t=x; u=y;
while (u) {
if(u&1) s=(s*t)%n;
u>>1;
t=(t*t)%n;
}
return(s)
}
А вот другой, рекурсивный, алгоритм:
unsigned long fast_exp(unsigned long x, unsigned long y, unsigned long N) {
unsigned long tmp;

if(y==l) return(x % N);
if (l^(x&l)) {
tmp= fast_exp(x,y/2,N);
return ((tmp*tmp)%N);
else {
tmp = fast_exp(x,(y-1)/2,N);
tmp = (tmp*tmp)%N;
tmp = (tmp*x)%N;
return (tmp);
}
}
Этот метод уменьшает количество операций, в среднем, до 1.5* k операций, где k - длина числа x в битах.
Найти способ вычисления с наименьшим количеством операций - трудная проблема (было доказано, что посл е- довательность должна содержать не меньше k-1 операций), но нетрудно снизить число операций до 1.1* k или даже лучше при больших k.
Эффективным способом много раз выполнять приведение по модулю для одного n является метод Монтго- мери [1111]. Другой метод называется алгоритмом Баррета [87]. Эффективность описанного алгоритма и этих двух методов рассматривается в [210]: алгоритм, рассмотренный мною, является наилучшим для едини ч- ного приведения по модулю, алгоритм Баррета - наилучшим для малых аргументов, а метод Монтгомери - на и- лучшим для обычного возведения в степень по модулю. (Метод Монтгомери также использует преимущество малых показателей степени, используя прием, называющийся смешанной арифметикой.)
Операция, обратная возведению в степень по модулю n, вычисляет дискретный логарифм. Я дальше вкратце рассмотрю эту операцию.
Простые числа
Простым называется целое число, большее единицы, единственными множителями которого является 1 и оно само: оно не делится ни на одно другое число. Два - это простое число. Простыми являются и 73, 2521,
2365347734339 и 2 756839
-1. Существует бесконечно много простых чисел. Криптография, особенно криптография с открытыми ключами, часто использует большие простые числа (512 бит и даже бол ьше).
Евангелос Кранакис (Evangelos Kranakis) написал отличную книгу по теории чисел, простым числам и их применению в криптографии [896]. Паула Рибенбойм (Paula Ribenboim) написала две отличных справочных работы по простым числам вообще [1307, 1308].
Наибольший общий делитель
Два числа называются взаимно простыми, если у них нет общих множителей кроме 1. Иными словами, е с- ли наибольший общий делитель a и n равен 1. Это записывается как:
НОД(a,n)=1
Взаимно просты числа 15 и 28. 15 и 27 не являются взаимно простыми, а 13 и 500 - являются. Простое число взаимно просто со всеми другими числами, кроме ч исел, кратных данному простому числу.
Одним из способов вычислить наибольший общий делитель двух чисел является алгоритм Эвклида. Эвк- лид описал этот алгоритм в своей книге, Элементы, написанной в 300 году до нашей эры. Он не изобрел его.
Историки считают, что этот алгоритм лет на 200 старше. Это самый древний нетривиальный алгоритм, который дошел до наших дней, и он все еще хорош. Кнут описал алгоритм и его современные модификации в [863]. На языке C:
/* возвращает НОД (gcd) x и y */
int gcd (int x, int y) {
int g;
if (x < 0)
x = -x;
if (y < 0)
y = -y;
if (x + y == 0 )
ERROR ;

g = y;
while (x > 0) {
g = x;
x = y % x;
y = g;
}
return g;
}
Этот алгоритм можно обобщить для получения НОД массива m чисел:
/* возвращает НОД (gcd) xl, x2...xm */
int multiple_gcd (int m, int *x) {
slze_t i;
int g;
if (m < 1)
return 0;
g = x [0];
for (i=l; ig = gcd(g, x[i]);
/* оптимизация, так как для случайных x[i], g==l в 60% случаев: */
if (g == 1)
return 1;
}
return g;
}
Обратные значения по модулю
Помните, что такое обратные значения? Обратное значение для 4 - 1/4, потому что 4*1/4 =1. В мире вычетов проблема усложняется:
4*x = 1 (mod 7)
Это уравнение эквивалентно обнаружению x и k, таких что
4x = 7k + 1
где x и k - целые числа. Общая задача состоит в нахождении x, такого что
1 = (a*x) mod n
Это также можно записать как a
-1
? x (mod n)
Проблему обратных значений по модулю решить нелегко. Иногда у нее есть решение, иногда нет. Например,
обратное значение 5 по модулю 14 равно 3. С другой стороны у числа 2 нет обратного значения по модулю 14.
В общем случае у уравнения a
-1
? x (mod n) существует единственное решение, если a и n взаимно просты.
Если a и n не являются взаимно простыми, то a
-1
? x (mod n) не имеет решений. Если n является простым чи с- лом, то любое число от 1 до n -1 взаимно просто с n и имеет в точности одно обратное значение по модулю n.
Так, хорошо. А теперь как вы собираетесь искать обратное значение a по модулю n? Существует два пути.
Обратное значение a по модулю n можно вычислить с помощью алгоритма Эвклида. Иногда это называется расширенным алгоритмом Эвклида.
Вот этот алгоритм на языке C++:
#define isEven(x) ((x & 0x01) == 0)
#define isOdd(x) (x& 0x01)
#define swap(x,y) (x^= y, y^= x, x^= y)
void ExtBinEuclid(int *u, int *v, int *u1, int *u2, int *u3) {
// предупреждение: u и v будут переставлены, если u

if (*u < *v) swap(*u<,*v);
for (k = 0; isEven(*u) && isEven(*v); ++k) {
*u>>=1; *v >>1;
}
*u1 = 1; *u2 = 0; *u3 = *u; t1 = *v; t2 = *u - 1; t3 = *v;
do {
do {
if (isEven(*u3)) {
if (isOdd(*ul) || isOdd(*u2)) {
*u1 += *v; *u2 += *u;
}
*ul >>* 1; *u2 >>= 1; *u3 >>= 1;
}
if (isEven(t3) || *u3 < t3) {
swap(*ul,tl); smap(*u2,t2); smap(*u3,t3);
}
} while (isEven(*u3));
while (*ul < tl || *u2 < t2) {
*ul += *v; *u2 += *u;
}
ul -= tl; *u2 -= t2; *u3 -= t3;
} while (t3 > 0);
while (*ul >= *v && *u2 >= *u) {
*ul>l -= *v; *u2 -= *u;
}
*u <<= k; *v <<= k; *u3 << k;
}
main(int argc, char **argv) {
int a, b, gcd;
if (argc < 3) {
cerr << "как использовать: xeuclid u v" << end1;
return -1;
}
int u = atoi(argv[1]);
int v = atoi(argv[2]);
if (u <= 0 || v <= 0 ) {
cerr << "Аргумент должен быть положителен!" << end1;
return -2;
}
// предупреждение: u и v будут переставлены если u < v
ExtBinEuclid(&u, &v, &a, &b, &gcd);
cout << a <<" * " << u << " + (-"
<< b << ") * " << v << " = " << gcd << end1;
if (gcd == 1)
cout << "Обратное значение " << v << " mod " << u << " is: "
<< u - b << end1;
return 0;
}
Я не собираюсь доказывать, что это работает, или приводить теоретическое обоснование. Подробности мо ж- но найти в [863] или в любой из приведенных ранее работ по теории чисел.
Алгоритм итеративен и для больших чисел может работать медленно. Кнут показал, что среднее число в ы-

полняемых алгоритмом делений равно:
0.843*log
2
(n) + 1.47
Решение для коэффициентов
Алгоритм Эвклида можно использовать и для решения следующих проблем: дан массив из m переменных x
1
, x
2
, ..., x m
, найти массив m коэффициентов, u l
, u
2
, ..., u m
, таких что u
l
* x
1
+...+ u m
* x m
, = 1
Малая теорема Ферма
Если m - простое число, и a не кратно m, то малая теорема Ферма утверждает a
m-1
? 1 (mod m)
(Пьер де Ферма (Pierre de Fermat), французский математик, жил с 1601 по 1665 год. Эта теорема не имеет ничего общего с его знаменитой теоремой.)
Функция Эйлера
Существует другой способ вычислить обратное значение по модулю n, но его не всегда возможно использ о- вать. Приведенным множеством остатков mod n называется подмножество полного множества остатков, чл е- ны которого взаимно просты с n. Например, приведенное множество остатков mod 12 - это {1, 5, 7, 11}. Если n - простое число, то приведенное множество остатков mod n - это множество всех чисел от 1 до n-1. Для любого n,
не равного 1,число 0 никогда не входит в приведенное множество остатков.
Функция Эйлера, которую также называют функцией фи Эйлера и записывают как ?(n), - это количество элементов в приведенном множестве остатков по модулю n. Иными словами, ?(n) - это количество положитель- ных целых чисел, меньших n и взаимно простых с n (для любого n, большего 1). (Леонард Эйлер (Leonhard
Euler), швейцарский математик, жил с 1707 по 1783 год.)
Если n - простое число, то ?(n) = n-1. Если n = pq, где p и q -простые числа, то ?(n)= (p - 1)(q - 1). Эти числа появляются в некоторых алгоритмах с открытыми ключами, и вот почему. В соответствии с обобщением Эйл е- ра малой теоремы Ферма, если НОД(a,n) = 1, то a
?(n) mod n = 1
Теперь легко вычислить a
-1
mod n:
x = a
?(n)-1
mod n
Например, какое число является обратным для 5 по модулю 7? Так как 7 - простое число, ?(7) = 7 - 1 = 6.
Итак, число, обратное к 5 по модулю 7, равно
5 6-1
mod 7 = 5 5
mod 7 = 3
Эти методы вычисления обратных значений можно расширить для более общей проблемы нахождения x
(если НОД(a,n) = 1):
(a*x) mod n = b
Используя обобщение Эйлера, решаем x = (b* a
?(n)-1
) mod n
Используя алгоритм Эвклида, находим x = (b* (a
-1
mod n) ) mod n
В общем случае для вычисления обратных значений алгоритм Эвклида быстрее, чем обобщение Эйлера,
особенно для чисел длиной порядка 500 бит. Если НОД( a,n) ? 1, не все потеряно. В этом общем случае ( a*x)
mod n=b, может иметь или несколько решений, или ни одного.
Китайская теорема об остатках
Если известно разложение числа n на простые сомножители, то для решения полной системы уравнений можно воспользоваться Китайской теоремой об остатках. Основной вариант этой теоремы был открыт в первом веке китайским математиком Сун Цзе.
В общем случае, если разложение числа n на простые сомножители представляет собой p
1
*p
2
*...*p t
, то сис- тема уравнений

(x mod p i
) = a i
, где i = 1, 2, . . . , t имеет единственное решение, x, меньшее n. (Обратите внимание, что некоторые простые числа могут поя в- ляться несколько раз. Например, p
1
может быть равно p
2
.) Другими словами, число (меньшее, чем произведение нескольких простых чисел) однозначно определяется своими остатками от деления на эти простые числа.
Например, возьмем простые числа 3 и 5, и 14 в качестве заданного числа. 14 mod 3 = 2, и 14 mod 5 = 4. С у- ществует единственное число, меньшее 3*5 = 15, с такими остатками: 14. Два остатка однозначно определяют число.
Поэтому для произвольного a < p и b < q (где p и q - простые числа), существует единственное число x,
меньшее pq, такое что x ? a (mod p), и x ? b (mod q)
Для получения x сначала воспользуемся алгоритмом Эвклида, чтобы найти u, такое что u*q ? 1 (mod p)
Затем вычислим:
x = (((a - b) *u) mod p) * q + b
Вот как выглядит Китайская теорема об остатках на языке C:
/* r - это количество элементов в массивах m and u;
m - это массив (попарно взаимно простых) модулей u - это массив коэффициентов возвращает значение n, такое что n == u[k]%m[k] (k=0..r-1) и n < [m[0]*m[l]*...*m[r-1]
*/
/* Получение функции Эйлера (totient) остается упражнением для читателя. */
int Chinese_remainder (size_t r, int *m, int *u) {
size_t i;
int modulus;
int n;
modulus=1;
for (i=0; imodulus*=m[i];
n=0;
for (i=0; in+=u[i] * modexp(modulus/m[i]*totient(m[i]),m[i]);
n %= modulus;
}
return n;
}
Обращение Китайской теоремы об остатках может быть использовано для решения следующей проблемы:
если p и q - простые числа, и p меньше q, то существует единственное x, меньшее, чем pq, такое что a ? x (mod p), и b ? x (mod q)
Если a ?b mod p, то x = (((a - (b mod p)) * u) mod p) * q + b
Если a < b mod p, то x = (((a + p - (b mod p))*u) mod p)*q + b
Квадратичные вычеты
Если p - простое число, и a больше 0, но меньше p, то a представляет собой квадратичный вычет по модулю p, если x
2
? a (mod p), для некоторых x

Не все значения a соответствуют этому требованию. Чтобы a было квадратичным вычетом по n, оно должно быть квадратичным вычетом по модулю всех простых сомножителей n. Например, если p = 7, квадратичными вычетами являются числа 1, 2, и 4:
1 2
= 1 ? 1 (mod 7)
2 2
= 4 ? 4 (mod 7)
3 2
= 9 ? 2 (mod 7)
4 2
= 16 ? 2 (mod 7)
5 2
= 25 ? 4 (mod 7)
6 2
= 36 ? 1 (mod 7)
Заметьте, что каждый квадратичный вычет дважды появляется в этом списке. Значений x, удовлетворяющих любому из следующих уравнений, не существует:
x
2
? 3 (mod 7)
x
2
? 5 (mod 7)
x
2
? 6 (mod 7)
Эти числа - 3, 5 и 6 - не являются квадратичными вычетами по модулю 7.
Хотя я этого и не делаю, несложно доказать, что когда p нечетно, существует в точности (p - 1)/2 квадратич- ных вычетов по модулю p, и столько же чисел, не являющихся квадратичными вычетами по модулю p. Кроме того, если a - это квадратичный вычет по модулю p, то у a в точности два квадратных корня, один между 0 и
(p-1)/2, а второй - между (p - 1)/2 и (p - 1). Один из этих квадратных корней одновременно является квадрати ч- ным остатком по модулю p, он называется главным квадратным корнем.
Если n является произведением двух простых чисел, p и q, то существует ровно (p - l)(q - 1)/4 квадратичных вычетов по модулю n. Квадратичный вычет по модулю n является совершенным квадратом по модулю n, пото- му что для того, чтобы быть квадратом по модулю n, вычет должен быть квадратом по модулю p и квадратом по модулю q. Например, существует одиннадцать квадратичных остатков mod 35: 1, 4, 9, 11, 15, 16, 21, 25, 29 и
30. У каждого квадратичного вычета ровно четыре квадратных корня.
Символ Лежандра
Символ Лежандра, L(a,p), определен, если a - это любое целое число, а p - простое число, большее, чем 2.
Он равен 0, 1 или -1.
L(a,p) = 0, если a делится на p.
L(a,p) = 1, если a - квадратичный вычет по модулю p.
L(a,p) = -1, если a не является квадратичным вычетом по модулю p.
L(a,p) можно рассчитать следующим образом:
L(a,p) = a
(p-1)/2
mod p
Или можно воспользоваться следующим алгоритмом:
1. Если a = 1, то L(a,p) = 1 2. Если a четно, то L(a,p) = L(a/2,p) * ( )
(
)/
?
?
1 2
1 8
з
3. Если a нечетно (и ? 1), то L(a,p)= L(p mod a, p)*(-1)
(a-1)(p-1)/4
Обратите внимание, что этот метод также является эффективным способом определить, является ли a квад- ратичным вычетом по модулю p (для простого числа p).
Символ Якоби
Символ Якоби, J(a,n), представляет собой обобщение символа Лежандра на составные модули, он определ я- ется для любого целого a и любого нечетного целого n. Функция удобна при проверке на простоту. Символ Як о- би является функцией на множестве полученных вычетов делителей n и может быть вычислен по различным формулам [1412]. Вот один из способов:
Определение 1: J(a,n) определен, только если n нечетно.
Определение 2: J(0,n) = 0.

Определение 3: Если n - простое число, то символ Якоби J(a,n) = 0, если a делится на n.
Определение 4: Если n - простое число, то символ Якоби J(a,n) = 1, если a - квадратичный вычет по модулю n.
Определение 5: Если n - простое число, то символ Якоби J(a,n) = -1, если a не является квадратичным выч е- том по модулю n.
Определение 6: Если n - составное число, то символ Якоби J(a,n) = J(a,p
1
)* ... * J(a,p m
), где p
1
, ... , p m
- это разложение n на простые сомножители.
Следующий алгоритм рекурсивно рассчитывает символ Якоби:
Правило 1: J(1,n) = 1
Правило 2: J(a*b,n) = J(a,n)* J(b,n)
Правило 3: J(2,n) =, если (n
2
-1) /8 нечетно, и -1 в противном случае
Правило 4: J(a,n)= J((a mod n),n)
Правило 5: J(a, b
1
*b
2
) = J(a, b
1
)* J(a, b
2
)
Правило 6: Если наибольший общий делитель a и b = 1, а также a и b нечетны:
Правило 6a: J(a,b)= J(b, a), если (a - l)(b - 1)/4 четно
Правило 6b: J(a,b)= -J(b, a), если (a - l)(b - 1)/4 нечетно
Вот алгоритм на языке C:
/* Этот алгоритм рекурсивно вычисляет символ Якоби */
int jacobi(int a, int b) {
int g;
assert(odd(b));
if (a >= b) a %= b; /* по правилу 4 */
if (a == 0) return 0; /* по определению 1 */
if (a == 1) return 1; /* по правилу 1 */
if (a < 0)
if ((b-l)/2 % 2 == 0)
return jacobi(-a,b);
else return -jacobi(-a,b);
if (a % 2 == 0) /* a четно */
if (((b*b -1)/8) % 2 == 0)
return +jacobi(a/2,b);
else return -jacobi(a/2,b); /* по правилам 3 и 2 */
g = gcd(a,b);
assert(odd(a)); /* это обеспечивается проверкой (a % 2 == 0) */
if (g == a) /* b делится на a */
return 0; /* по правилу 5 */
else if (g != 1)
return jacobi(g,b)*jacobi(a/g,b); /* по правилу 2 */
else if (((a-l)*(b-l)/4) % 2 == 0)
return +jacobi(b,a); /* по правилу 6a */
else return -jacobi(b,a); /* по правилу 6b */
}
Если заранее известно, что n - простое число, вместо использования предыдущего алгоритма просто вычис- лите a((n-1)/2) mod n, в этом случае J(a,n) эквивалентен символу Лежандра.
Символ Якоби нельзя использовать для определения того, является ли a квадратичным вычетом по модулю

n (если, конечно, n не является простым числом). Обратите внимание, что если J( a,n) = 1 и n - составное число,
то утверждение, что a является квадратичным вычетом по модулю n, не обязательно будет истиной. Например:
J(7,143) = J(7,11)* J(7,13) = (-1)(-1) = 1
Однако не существует таких целых чисел x, что x
2
? 7 (mod 143).