Математика

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

size(a)	Размер числа. Это количество бит, необходимое для записания числа в двоичной форме, т.е. size(a)≅log2(a).
a+b	Сложение целых чисел.
a-b	Вычитание целых чисел.
a∗b	Обычное умножение. Я предпочитаю явно указывать знак операции вместо формы ab. Подобная запись принята в математической литературе, но я программист, а там знак умножения ∗ необходим.
a|b	Читается как "a делит b". Не путайте, это значит, что b является кратным a.
НОД(a,b)	Наибольший общий делитель a и b. Обозначает наибольшее число c, при котором c|a и c|b. Его можно рассчитать с помощью повторения НОД(a,b) = НОД(b-a,a). Это называется алгоритмом Евклида. Евклидов алгоритм является одним из древнейших алгоритмов (был изобретен в древней Греции), и очень важен в теории чисел.
a mod n	Это число c, при условии, что 0≤с<n, для которого существует такое k, что a=c+k∗n.
a+b mod(n)	Сначала вычислите a+b (это примерно на один бит больше, чем a или b) и затем примените к результату операцию mod n. Для каждого n, все числа с, 0≤c<n, образуют группу со сложением по модулю n в качестве групповой операции.
a∗b mod(n)	Сначала вычислите a∗b (это приблизительно равно размеру size(a)+size(b)) и затем примените mod(n).
ab mod(n)	Обычно берется b∈Ζn, 1 и тогда примерный размер ab равен size(a)∗size(b). Часто это слишком большой размер, чтобы уместить его в памяти, поэтому такое выражение вычисляется так: записываем b в двоичном виде: b=2i0 + 2i1 + ... + 2im, вычисляем k0=1, k1=a, k2 = a2mod(n), k3 = k22mod(n), ... и затем вычисляем ответ при abmod(n)=((ki0 ∗ ki1) mod(n) ∗ ki2) mod(n) ∗ ... ∗ kimmod(n).
a-1mod(n)	Действие, рассмотренное выше, применимо только при 0≤b<n. a-1mod(n) – это такое число, что a-1∗a mod(n) = 1. Оно существует, если НОД(a,n)=1. Его можно рассчитать с использованием некоторых промежуточных значений, которые вы получаете при вычислении НОД(a,n) по (расширенному) алгоритму Евклида.
Ζn	Аддитивная группа членов x, при 0≤x<n, и с групповой операцией "сложение по модулю n": c = a+b mod(n).
Ζn∗	Мультипликативная группа членов x, при 0<x<n и НОД(x,n)=1. Групповая операция – c = a∗b mod(n).
φ(n)	Количество членов мультипликативной группы Ζn∗. Это n-1, если n – простое число. Малая теорема Ферма гласит, что если a∗b mod φ(n) = 1, тогда для всех b∈Ζn∗, (ma) b mod(n) = m. Вычисление φ(n) – трудная задача, если вы не знаете сомножителей n.
a⊕b	Побитовое исключающее ИЛИ двух целых чисел (XOR). Вычисляется так: записываем числа в двоичном виде, выводим результирующий бит 1, если входные биты различны, 0 – если одинаковы. Например, 12⊕10 = 1100⊕1010 = 0110 = 6.
ord(g)	Порядок элемента g в группе – это наименьшее число k, такое, что gk=1.

Назад^[link1] | Дальше^[link2]

---

¹ Либо b ∈ φ(n), однако φ(n) не всегда известна.