Числа и нотация

Зачем этот раздел?

Этот раздел — опциональный. Если вы уверенно работаете с системами счисления и нотация вроде a ≡ b (mod n) или ∀ a ∈ G вам знакома, смело переходите к CRYPTO-01: Модулярная арифметика. Если нет — за 15 минут мы вспомним всё, что нужно.

Вспомните

Прежде чем читать дальше, попробуйте ответить:

1. Что такое простое число? Перечислите первые 10 простых чисел.

2. Переведите число 255 в двоичную систему. А 0xFF — это сколько в десятичной?

3. Что означает символ ∈ в записи a ∈ Z?

Если ответили уверенно — отлично, просто пробегитесь по разделу для проверки. Если нет — это нормально, именно для этого мы здесь.

Натуральные, целые, рациональные числа

Вы это знаете. Вот словарь обозначений:

В криптографии мы почти всегда работаем с Z (целыми числами), а точнее — с Z_p (целые по модулю простого числа p). Дроби и вещественные числа в криптографии практически не встречаются.

# Python знает всё это:
n = 42          # целое (Z)
q = 3/4         # рациональное (Q) -- но в крипто мы это не используем
p = 2**256 - 2**32 - 977  # огромное целое -- простое число secp256k1
print(type(n))  # <class 'int'>

Двоичная система

Компьютер хранит числа в двоичной системе — только 0 и 1. Каждый разряд (бит) имеет вес, равный степени двойки:

Например, 42 в двоичной системе — это 101010:

32 + 8 + 2 = 42

Попробуйте:

• Установите число 255 — это 11111111 (все 8 бит включены)
• Установите число 128 — это 10000000 (только старший бит)
• Переключитесь на BIN и посмотрите разрядные значения

# Конвертация в Python:
print(bin(42))          # '0b101010'
print(int('101010', 2)) # 42

# Каждый приватный ключ -- это 256-битное число:
key = 0b1010101011001100  # двоичный литерал
print(key)               # 43724

Шестнадцатеричная система

Hex (hexadecimal) группирует каждые 4 бита в один символ: 0-9 и A-F.

Почему криптография использует hex: 256-битное число — это 64 hex-символа вместо 256 двоичных цифр.

# Hex в Python:
print(hex(42))            # '0x2a'
print(int('2A', 16))      # 42

# Биткоин-адрес -- это hex:
tx_hash = "a1b2c3d4e5f6..."  # 64 hex-символа = 256 бит

Математическая нотация — это просто язык

Когда вы видите ∀ a ∈ G: a * e = a, это не магия. Это сокращённая запись, как Python — сокращение для машинного кода. Выучите 12 символов ниже, и математические определения станут такими же читаемыми, как код.

Таблица “Нотация = Python”

Чтение подстрочных и надстрочных индексов

В математике часто используются индексы:

# В Python индексы -- это обычные переменные и операторы:
a = [10, 20, 30]
a_i = a[1]      # a_i = a с индексом i = 20

x = 3
x_n = x ** 5    # x^5 = 243

# Z_p -- это range(p):
p = 7
Z_p = list(range(p))  # [0, 1, 2, 3, 4, 5, 6]

Где вы это встретите

Что дальше?

В следующем уроке мы вспомним простые числа, делимость и НОД — фундамент, на котором строится вся криптография от модулярной арифметики до RSA.