РегистрацияМатематика
Криптографические алгоритмы обычно основаны на математических конструкциях, особенно из теории групп и теории чисел. Я не собираюсь давать здесь научный курс теории чисел — по данному предмету и так полно хорошей литературы, — но я бы хотел привести используемые свойства и их обозначения. Теория групп здесь не описана, поскольку к настоящему времени 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). Часто это слишком большой размер, чтобы уместить его в памяти, поэтому такое выражение вычисляется так:
|
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. |
1 Либо b ∈ φ(n), однако φ(n) не всегда известна.
Комментариев нет [показать комментарии/форму]
Ваша оценка документа [показать результаты]
