Группы и конечные поля

Зачем это блокчейну?

Эллиптические кривые Bitcoin и Ethereum работают над конечными полями. Публичный ключ — это точка на кривой secp256k1, определенной над полем GF(p), где p = 2^256 - 2^32 - 977. Безопасность всей системы опирается на задачу дискретного логарифма в циклической группе: зная g и g^k, невозможно эффективно вычислить k.

# Кривая secp256k1 определена над конечным полем GF(p):
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
# Порядок группы точек кривой:
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

# Генератор G — фиксированная точка на кривой
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

# Публичный ключ = private_key * G (скалярное умножение в группе точек)
# Все операции — в конечном поле GF(p)

Чтобы понять почему приватный ключ невозможно вычислить из публичного, нужно понять структуру конечных полей и циклических групп.

Интуитивное объяснение: «клуб с правилами»

Представьте закрытый клуб с числами-членами и операцией (например, умножение). У клуба четыре правила:

1. Замкнутость: результат операции — всегда член клуба (никто не «выпадает»)
2. Единица: есть специальный член (1), который ничего не меняет
3. Обратные: у каждого члена есть «партнер», с которым они дают единицу
4. Ассоциативность: порядок вычислений не важен: (a * b) * c = a * (b * c)

Если все четыре правила выполняются — это группа.

Z*_7 = {1, 2, 3, 4, 5, 6} с операцией умножения по модулю 7 — это группа. Проверим:

• Замкнутость: 3 * 5 = 15 = 1 (mod 7) — результат в множестве
• Единица: 1 (любое a * 1 = a)
• Обратные: 3^(-1) = 5, потому что 3 * 5 = 1
• Ассоциативность: (2 * 3) * 5 = 6 * 5 = 30 = 2 и 2 * (3 * 5) = 2 * 1 = 2 — одинаково

Конечные поля GF(p)

Конечное поле GF(p) (Galois Field) — это множество {0, 1, 2, ..., p-1} с двумя операциями: сложением и умножением по модулю простого p.

Почему p должно быть простым? Потому что только тогда каждый ненулевой элемент имеет мультипликативный обратный:

# GF(7) — поле: все ненулевые элементы имеют обратные
p = 7
for a in range(1, p):
    inv = pow(a, -1, p)
    print(f"{a} * {inv} = {(a * inv) % p} (mod {p})")

# GF(6) — НЕ поле! 6 не простое
# 2 * 3 = 6 = 0 (mod 6) — делители нуля!
# У 2 нет обратного в Z_6

Таблица умножения

Изучите структуру конечного поля через таблицу умножения. Обратите внимание:

• Строка 0 — все нули (умножение на 0)
• Каждая ненулевая строка содержит все ненулевые элементы ровно по одному разу
• Это свойство гарантирует существование обратных

Алгоритмический уровень: Python

Операции в конечном поле можно выполнять вручную или с помощью библиотеки galois:

# === Ручная реализация GF(p) ===
class GF:
    """Простая реализация элемента конечного поля"""
    def __init__(self, value, p):
        self.value = value % p
        self.p = p

    def __add__(self, other):
        return GF((self.value + other.value) % self.p, self.p)

    def __mul__(self, other):
        return GF((self.value * other.value) % self.p, self.p)

    def inverse(self):
        return GF(pow(self.value, -1, self.p), self.p)

    def __repr__(self):
        return f"GF({self.p})({self.value})"

# Пример
a = GF(3, 7)
b = GF(5, 7)
print(a + b)        # GF(7)(1)
print(a * b)        # GF(7)(1)
print(a.inverse())  # GF(7)(5)

# === С библиотекой galois ===
import galois

GF7 = galois.GF(7)
a = GF7(3)
b = GF7(5)
print(a + b)         # 1
print(a * b)         # 1
print(GF7(3) ** -1)  # 5

# Таблица умножения
print("Таблица умножения GF(7):")
for i in range(7):
    row = [int(GF7(i) * GF7(j)) for j in range(7)]
    print(row)

Циклические группы и генераторы

Циклическая группа — группа, в которой все элементы можно получить как степени одного элемента — генератора g:

G = {g^0, g^1, g^2, ..., g^(n-1)}

где n — порядок группы.

# Z*_7 — циклическая группа порядка 6
# g = 3 — генератор
p = 7
g = 3

# Вычисляем все степени g
powers = []
for i in range(p - 1):
    powers.append(pow(g, i, p))
print(f"Степени g={g}: {powers}")
# [1, 3, 2, 6, 4, 5] — все элементы Z*_7!

# g = 2 — тоже генератор
g = 2
powers = [pow(g, i, p) for i in range(p - 1)]
print(f"Степени g={g}: {powers}")
# [1, 2, 4, 1, 2, 4] — НЕ все элементы, порядок = 3
# Значит 2 — НЕ генератор Z*_7

Важно: не каждый элемент является генератором. Генераторы Z*_p — это примитивные корни по модулю p.

Попробуйте:

• Для p = 7, g = 3: генератор посещает все 6 элементов
• Для p = 7, g = 2: порядок элемента = 3, посещает только 4
• Для p = 11, g = 2: генератор — посещает все 10 элементов

Почему генераторы важны для криптографии?

В Bitcoin генератор G кривой secp256k1 — фиксированная точка. Публичный ключ P = k * G (скалярное умножение). Зная G и P, найти k — это задача дискретного логарифма. В циклической группе большого порядка эта задача вычислительно неразрешима.

# Дискретный логарифм — легкий пример (малый порядок)
p = 23
g = 5
target = 8  # Найти x: g^x = target (mod p)

# Перебор (работает только для малых чисел!)
for x in range(p - 1):
    if pow(g, x, p) == target:
        print(f"Дискретный логарифм: {g}^{x} = {target} (mod {p})")
        break

# Для secp256k1 порядок ~ 2^256 — перебор невозможен

Математический уровень

Определение группы

Множество G с операцией * является группой (G, *), если:

1. Замкнутость: ∀ a, b ∈ G: a * b ∈ G
2. Ассоциативность: ∀ a, b, c ∈ G: (a * b) * c = a * (b * c)
3. Нейтральный элемент: ∃ e ∈ G: ∀ a ∈ G: a * e = e * a = a
4. Обратный элемент: ∀ a ∈ G: ∃ a^(-1) ∈ G: a * a^(-1) = e

Если дополнительно a * b = b * a (коммутативность), группа называется абелевой.

Определение поля

Множество F с операциями + и * является полем, если:

1. (F, +) — абелева группа с нейтральным элементом 0
2. (F \ {0}, *) — абелева группа с нейтральным элементом 1
3. Дистрибутивность: a * (b + c) = a*b + a*c

GF(p) для простого p — конечное поле с p элементами.

Структура подгрупп

По теореме Лагранжа, порядок подгруппы делит порядок группы. Для Z*_p порядок = p - 1, поэтому:

p = 13  # |Z*_13| = 12
# Возможные порядки элементов: делители 12 = {1, 2, 3, 4, 6, 12}
for a in range(1, p):
    order = 1
    current = a
    while current != 1:
        current = (current * a) % p
        order += 1
    print(f"ord({a}) = {order}")

Почему конкретные простые числа?

Bitcoin использует кривую secp256k1 над полем GF(p), где:

p = 2^256 - 2^32 - 977

Это число выбрано не случайно:

• Близко к степени двойки — эффективные операции на процессорах
• Специальная структура — позволяет быструю редукцию по модулю
• Достаточный размер — 256 бит обеспечивают ~128 бит безопасности
• Простое — гарантирует структуру поля

Для сравнения, простые числа Мерсенна 2^p - 1 используются в других криптосистемах из-за еще более эффективной арифметики.

Практика

Закрепите знания в Jupyter notebook: реализуйте класс конечного поля, найдите генераторы циклических групп, вычислите порядки элементов и поработайте с библиотекой galois.

Notebook: labs/crypto/notebooks/02-finite-fields.ipynb

Что дальше?

Теперь у вас есть математический фундамент: модулярная арифметика и конечные поля. В следующих уроках мы применим эти знания к хеш-функциям (CRYPTO-03, CRYPTO-04), где увидим, как односторонние функции строятся на основе этих алгебраических структур.