Решение задачи: Элементы криптоанализа и взлом шифра Виженера

Экзаменационный билет № 16 Вопрос 1. Элементы криптоанализа: взлом, атака, виды атак. Взлом шифра простого блокнота с периодическим ключом (ко-совпадения, частотный анализ). Криптоанализ — это наука о методах получения открытого текста из зашифрованного без знания ключа. Основные понятия: 1. Взлом (раскрытие) — процесс нахождения ключа или открытого текста. 2. Атака — попытка реализации взлома с использованием математических или вычислительных методов. Виды атак: — Атака на основе только шифротекста (самая сложная). — Атака на основе известного открытого текста. — Атака на основе выбранного открытого текста. — Атака на основе выбранного шифротекста. Взлом шифра с периодическим ключом (шифр Виженера): Если ключ повторяется с периодом \( L \), шифр перестает быть абсолютно стойким. 1. Метод ко-совпадений (индекс совпадения): Позволяет определить длину ключа \( L \). Индекс совпадения для случайного текста равен примерно 0.038, а для осмысленного текста (например, русского языка) — около 0.055. 2. Частотный анализ: После определения длины ключа \( L \), текст разбивается на \( L \) групп. Каждая группа зашифрована одним и тем же символом ключа (сдвиг Цезаря). Для каждой группы применяется стандартный частотный анализ (сравнение частот букв в шифровке с эталонными частотами языка). Вопрос 2. Эллиптические кривые над конечными полями. Аддитивная группа на множестве точек. Операция сложения элементов: определение, формулы, примеры вычисления. Эллиптическая кривая \( E \) над конечным полем \( F_p \) (где \( p > 3 \)) задается уравнением Вейерштрасса: \[ y^2 \equiv x^3 + ax + b \pmod{p} \] при условии, что дискриминант \( \Delta = 4a^3 + 27b^2 \not\equiv 0 \pmod{p} \). Множество точек кривой вместе с бесконечно удаленной точкой \( O \) образует аддитивную абелеву группу. Правила сложения точек \( P(x_1, y_1) \) и \( Q(x_2, y_2) \): 1. \( P + O = P \). 2. Если \( x_1 = x_2 \) и \( y_1 = -y_2 \), то \( P + Q = O \). 3. В остальных случаях \( P + Q = R(x_3, y_3) \), где: \[ x_3 = \lambda^2 - x_1 - x_2 \pmod{p} \] \[ y_3 = \lambda(x_1 - x_3) - y_1 \pmod{p} \] Определение коэффициента \( \lambda \): — Если \( P \neq Q \): \[ \lambda = \frac{y_2 - y_1}{x_2 - x_1} \pmod{p} \] — Если \( P = Q \) (удвоение точки): \[ \lambda = \frac{3x_1^2 + a}{2y_1} \pmod{p} \] Пример вычисления: Пусть кривая \( y^2 = x^3 + x + 1 \pmod{5} \). Здесь \( a=1, b=1, p=5 \). Найдем \( 2P \) для точки \( P(0, 1) \): 1. \( \lambda = \frac{3 \cdot 0^2 + 1}{2 \cdot 1} = \frac{1}{2} \equiv 3 \pmod{5} \) (так как \( 2 \cdot 3 = 6 \equiv 1 \)). 2. \( x_3 = 3^2 - 0 - 0 = 9 \equiv 4 \pmod{5} \). 3. \( y_3 = 3(0 - 4) - 1 = -12 - 1 = -13 \equiv 2 \pmod{5} \). Результат: \( 2P = (4, 2) \).