Криптография и теория информации

Справочник

Термины, формулы и обозначения, которые встречаются в статьях и в лаборатории, — в одном месте.

Глоссарий

Алфавит
Конечное множество символов, из которых источник составляет сообщения. → статья
Асимметричный шифр
Шифр с парой ключей: открытым (для шифрования) и секретным (для расшифрования). Синоним — шифр с открытым ключом. → статья
Блочный код (n, k)
Код, переводящий каждые k бит данных в кодовое слово из n бит; скорость кода k/n. → статья
Вероятностное шифрование
Шифрование, при котором один и тот же открытый текст даёт разные шифртексты за счёт случайности. → статья
Группа
Моноид, в котором у каждого элемента есть обратный. → статья
Диофантово уравнение
Уравнение с целыми коэффициентами, решения которого ищутся в целых числах. → статья
Дискретный логарифм
Для g, y и модуля p — такое x, что g^x ≡ y (mod p). Вычислительно трудная задача при больших p. → статья
Избыточность
Доля «лишних» символов: R = 1 − H / log₂ N для источника или 1 − k/n для блочного кода. Сжатие уменьшает избыточность, помехоустойчивое кодирование намеренно её добавляет. → статья
Канал связи
Среда, по которой передаётся закодированное сообщение; в канале с шумом символы могут искажаться. → статья
Квадратичный вычет
Число a, для которого сравнение x² ≡ a (mod p) разрешимо. → статья
Китайская теорема об остатках
Система x ≡ a_i (mod m_i) с попарно взаимно простыми модулями имеет единственное решение по модулю M = m_1·…·m_k. → статья
Класс вычетов
Множество всех целых чисел, сравнимых с данным числом по модулю m. → статья
Код Адамара
Код из строк матрицы Адамара и их инверсий; при n = 2^r — код Рида–Маллера первого порядка с расстоянием n/2. → статья
Код Хаффмана
Оптимальный префиксный код: дерево строится снизу вверх объединением двух узлов с наименьшими частотами. → статья
Код Шеннона–Фано
Префиксный код: отсортированные символы рекурсивно делятся на две группы с близкими суммами частот. → статья
Корреляционное декодирование
Выбор кодового слова с наибольшим скалярным произведением с принятым вектором (в ±1-форме). → статья
Критерий Поклингтона
Достаточное условие простоты n по известному разложению части F числа n − 1, где F > √n. → статья
Матрица Адамара
Квадратная матрица из ±1 с попарно ортогональными строками: H·Hᵀ = n·E. → статья
Минимальное расстояние
Наименьшее расстояние Хэмминга между различными кодовыми словами d. Код обнаруживает d − 1 ошибок и исправляет ⌊(d − 1)/2⌋. → статья
Моноид
Множество с ассоциативной бинарной операцией и нейтральным элементом. → статья
Неравенство Крафта
Префиксный двоичный код с длинами l_1, …, l_N существует тогда и только тогда, когда Σ 2^(−l_i) ≤ 1. → статья
Первообразный корень
Элемент g порядка φ(m): его степени пробегают всю приведённую систему вычетов. → статья
Полугруппа
Множество с ассоциативной бинарной операцией (нейтральный элемент не требуется). → статья
Порядок элемента
Наименьшее d > 0, такое что a^d ≡ 1 (mod m). Всегда делит φ(m). → статья
Префиксный код
Код, в котором ни одно кодовое слово не является началом другого. Декодируется однозначно и без разделителей. → статья
Приведённая система вычетов
Представители классов вычетов, взаимно простых с m; их ровно φ(m). → статья
Принцип Керкгоффса
Стойкость шифра должна определяться только секретностью ключа, а не секретностью алгоритма. → статья
Простое число
Натуральное число больше 1, у которого ровно два делителя: 1 и само число. → статья
Протокол Диффи–Хеллмана
Выработка общего секрета g^(ab) по открытому каналу: стороны обмениваются g^a и g^b. → статья
Расстояние Хэмминга
Число позиций, в которых различаются два слова одинаковой длины. → статья
Расширенный алгоритм Евклида
Алгоритм Евклида, который вместе с НОД(a, b) находит коэффициенты Безу s, t. → статья
Сеансовый ключ
Случайное одноразовое число k в шифре Эль-Гамаля; делает шифрование вероятностным. Повторное использование k раскрывает сообщения. → статья
Сертификат простоты
Данные, по которым простоту числа можно быстро перепроверить, не повторяя поиск (например, цепочка Поклингтона). → статья
Синдром
Результат проверки принятого слова проверочными соотношениями. В коде Хэмминга синдром равен номеру позиции ошибки (0 — ошибок нет). → статья
Совершенный код
Код, на котором граница Хэмминга достигается с равенством: шары радиуса t вокруг кодовых слов покрывают всё пространство. Пример — коды Хэмминга. → статья
Соотношение Безу
Для любых целых a, b существуют целые s, t, такие что a·s + b·t = НОД(a, b). → статья
Сравнение по модулю
a ≡ b (mod m) ⇔ m | (a − b): числа дают одинаковые остатки при делении на m. → статья
Средняя длина кода
L = Σ p_i·l_i — математическое ожидание длины кодового слова. Для кода Хаффмана H ≤ L < H + 1. → статья
Тест Миллера–Рабина
Вероятностный тест простоты: составное число проходит один раунд с вероятностью не больше 1/4. → статья
Тест Ферма
Если a^(n−1) ≢ 1 (mod n) для некоторого a, взаимно простого с n, то n составное. Обратное неверно (числа Кармайкла). → статья
Функция Эйлера
φ(m) — количество чисел от 1 до m, взаимно простых с m. → статья
Частотный анализ
Вскрытие шифра замены по статистике: частоты символов шифртекста повторяют частоты языка. → статья
Числа Кармайкла
Составные n, для которых a^(n−1) ≡ 1 (mod n) при всех a, взаимно простых с n. Наименьшее — 561 = 3·11·17. → статья
Шифр замены
Шифр, который заменяет каждый символ другим по правилу (ключу); порядок символов сохраняется. → статья
Шифр перестановки
Шифр, который меняет порядок символов, не меняя сами символы. → статья
Энтропия
Среднее количество информации на символ источника: H = −Σ p_i·log₂ p_i бит. Нижняя граница средней длины любого однозначно декодируемого кода. → статья

Сводка формул

Теория информации

Количество информации в исходе с вероятностью p I = −log₂ p бит
Энтропия источника H = −Σ p_i·log₂ p_i, 0 ≤ H ≤ log₂ N
Средняя длина кода L = Σ p_i·l_i
Неравенство Крафта Σ 2^(−l_i) ≤ 1
Теорема Шеннона для оптимального кода H ≤ L < H + 1
Избыточность кода R = 1 − H / L

Помехоустойчивые коды

Обнаружение и исправление ошибок обнаруживает d − 1 ошибок, исправляет t = ⌊(d − 1)/2⌋
Код Хэмминга n = 2^m − 1, k = n − m, d = 3
Граница Хэмминга (t = 1) 2^k·(n + 1) ≤ 2^n
Синдром кода Хэмминга s = номер позиции ошибки (0 — ошибок нет)
Матрица Адамара (Сильвестр) H_1 = [1], H_(2n) = [[H_n, H_n], [H_n, −H_n]]
Ортогональность строк H·Hᵀ = n·E
Код Адамара порядка n = 2^r k = r + 1 бит, d = n/2, t = ⌊(n/2 − 1)/2⌋

Теория чисел

Соотношение Безу a·s + b·t = НОД(a, b)
Решения ax + by = c x = x_0 + (b/d)·t, y = y_0 − (a/d)·t, d = НОД(a, b)
Малая теорема Ферма a^(p−1) ≡ 1 (mod p), p ∤ a
Теорема Эйлера a^φ(m) ≡ 1 (mod m), НОД(a, m) = 1
Функция Эйлера φ(p^k) = p^(k−1)·(p − 1), φ(ab) = φ(a)·φ(b) при НОД(a, b) = 1
Критерий Эйлера a^((p−1)/2) ≡ 1 ⇔ a — квадратичный вычет по модулю p
Первообразный корень g — первообразный ⇔ g^((p−1)/q) ≢ 1 для всех простых q | p − 1
Китайская теорема x = Σ a_i·M_i·(M_i⁻¹ mod m_i) mod M, M_i = M / m_i

Криптография

Ключи Эль-Гамаля y = g^x mod p; открытый (p, g, y), секретный x
Шифрование Эль-Гамаля a = g^k mod p, b = y^k·M mod p
Расшифрование Эль-Гамаля M = b·(a^x)⁻¹ mod p
Общий секрет Диффи–Хеллмана K = (g^a)^b = (g^b)^a = g^(ab) mod p
Критерий Поклингтона n − 1 = F·R, F > √n, a^(n−1) ≡ 1, НОД(a^((n−1)/q) − 1, n) = 1 для всех q | F

Обозначения

ЗаписьСмысл
a | b a делит b
a ∤ b a не делит b
НОД(a, b) наибольший общий делитель
a ≡ b (mod m) a и b сравнимы по модулю m
a mod m остаток от деления a на m (от 0 до m − 1)
a⁻¹ mod m обратный элемент: a·a⁻¹ ≡ 1 (mod m)
ℤₘ кольцо вычетов по модулю m
ℤₘ* группа обратимых вычетов по модулю m
φ(m) функция Эйлера
ord_m(a) порядок a по модулю m
⌊x⌋ целая часть (округление вниз)
log₂ двоичный логарифм
⊕ сложение по модулю 2 (XOR)
d(x, y) расстояние Хэмминга

Литература

Теория информации и кодирование

  1. Shannon C. E. A Mathematical Theory of Communication // Bell System Technical Journal. 1948. Vol. 27. P. 379–423, 623–656.
  2. Шеннон К. Работы по теории информации и кибернетике. — М.: Издательство иностранной литературы, 1963.
  3. Cover T. M., Thomas J. A. Elements of Information Theory. — 2nd ed. — Wiley, 2006.
  4. Huffman D. A. A Method for the Construction of Minimum-Redundancy Codes // Proceedings of the IRE. 1952. Vol. 40, № 9. P. 1098–1101.
  5. Fano R. M. The Transmission of Information. — Technical Report № 65, MIT Research Laboratory of Electronics, 1949.

Помехоустойчивое кодирование

  1. Hamming R. W. Error Detecting and Error Correcting Codes // Bell System Technical Journal. 1950. Vol. 29, № 2. P. 147–160.
  2. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976.
  3. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. — М.: Связь, 1979.

Теория чисел и алгебра

  1. Виноградов И. М. Основы теории чисел. — 9-е изд. — М.: Наука, 1981.
  2. Бухштаб А. А. Теория чисел. — 2-е изд. — М.: Просвещение, 1966.
  3. Кострикин А. И. Введение в алгебру. Ч. I. Основы алгебры. — М.: Физматлит, 2000.
  4. Кнут Д. Э. Искусство программирования. Т. 2. Получисленные алгоритмы. — 3-е изд. — М.: Вильямс, 2000.

Криптография

  1. Diffie W., Hellman M. E. New Directions in Cryptography // IEEE Transactions on Information Theory. 1976. Vol. 22, № 6. P. 644–654.
  2. ElGamal T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms // IEEE Transactions on Information Theory. 1985. Vol. 31, № 4. P. 469–472.
  3. Pocklington H. C. The Determination of the Prime or Composite Nature of Large Numbers by Fermat's Theorem // Proceedings of the Cambridge Philosophical Society. 1914. Vol. 18. P. 29–30.
  4. Maurer U. M. Fast Generation of Prime Numbers and Secure Public-Key Cryptographic Parameters // Journal of Cryptology. 1995. Vol. 8, № 3. P. 123–155.
  5. Menezes A. J., van Oorschot P. C., Vanstone S. A. Handbook of Applied Cryptography. — CRC Press, 1996. https://cacr.uwaterloo.ca/hac/
  6. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003.
  7. Смарт Н. Криптография. — М.: Техносфера, 2005.
  8. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. — М.: Триумф, 2002.