id: Гость   вход   регистрация
текущее время 09:14 18/09/2019
Владелец: SATtva (создано 14/09/2006 22:50), редакция от 17/12/2007 19:54 (автор: SATtva) Печать
Категории: криптография, софт, pgp, сайт проекта, статьи
создать
просмотр
редакции
ссылки

Математика


Криптографические алгоритмы обычно основаны на математических конструкциях, особенно из теории групп и теории чисел. Я не собираюсь давать здесь научный курс теории чисел — по данному предмету и так полно хорошей литературы, — но я бы хотел привести используемые свойства и их обозначения. Теория групп здесь не описана, поскольку к настоящему времени 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). Часто это слишком большой размер, чтобы уместить его в памяти, поэтому такое выражение вычисляется так:

  1. записываем b в двоичном виде:
    b=2i0 + 2i1 + ... + 2im,
  2. вычисляем
    k0=1, k1=a, k2 = a2mod(n), k3 = k22mod(n), ...
  3. и затем вычисляем ответ при
    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.

Назад | Дальше



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


 
Комментариев нет [показать комментарии/форму]
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3