Числа и нотация
Зачем этот раздел?
Этот раздел — опциональный. Если вы уверенно работаете с системами счисления и нотация вроде a ≡ b (mod n) или ∀ a ∈ G вам знакома, смело переходите к CRYPTO-01: Модулярная арифметика. Если нет — за 15 минут мы вспомним всё, что нужно.
Вспомните
Прежде чем читать дальше, попробуйте ответить:
1. Что такое простое число? Перечислите первые 10 простых чисел.
2. Переведите число 255 в двоичную систему. А 0xFF — это сколько в десятичной?
3. Что означает символ
∈в записиa ∈ Z?
Если ответили уверенно — отлично, просто пробегитесь по разделу для проверки. Если нет — это нормально, именно для этого мы здесь.
Натуральные, целые, рациональные числа
Вы это знаете. Вот словарь обозначений:
| Множество | Обозначение | Что это | Пример |
|---|---|---|---|
| Натуральные | N | Числа для счёта | 1, 2, 3, … |
| Целые | Z | С отрицательными | …, -2, -1, 0, 1, 2, … |
| Рациональные | Q | Дроби | 1/2, 3/4, -7/3 |
| Вещественные | R | С иррациональными | pi, sqrt(2), e |
В криптографии мы почти всегда работаем с 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. Каждый разряд (бит) имеет вес, равный степени двойки:
| Бит 7 | Бит 6 | Бит 5 | Бит 4 | Бит 3 | Бит 2 | Бит 1 | Бит 0 |
|---|---|---|---|---|---|---|---|
| 128 | 64 | 32 | 16 | 8 | 4 | 2 | 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 |
|---|---|---|
| 0 | 0000 | 0 |
| 9 | 1001 | 9 |
| 10 | 1010 | A |
| 15 | 1111 | 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 | Где |
|---|---|---|---|
≡ | конгруэнтно | % (оператор остатка) | CRYPTO-01 |
∀ | для всех | for ... in / all() | CRYPTO-02 |
∃ | существует | any() | CRYPTO-02 |
∈ | принадлежит | in | CRYPTO-01, CRYPTO-02 |
∉ | не принадлежит | not in | CRYPTO-02 |
| | делит | % == 0 | CRYPTO-01, CRYPTO-08 |
⟺ | тогда и только тогда | == (эквивалентность) | CRYPTO-01 |
→ | следует / отображение | if...then / lambda | CRYPTO-02, CRYPTO-04 |
∅ | пустое множество | set() | CRYPTO-02 |
⊂ | подмножество | issubset() / < | CRYPTO-02 |
∪ | объединение | | (для set) | CRYPTO-02 |
∩ | пересечение | & (для set) | CRYPTO-02 |
Таблица “Нотация = Python”
| Математика | Читается | Python |
|---|---|---|
a ≡ b (mod n) | a конгруэнтно b по модулю n | a % n == b % n |
∀ a ∈ G | для всех a в G | for a in G |
∃ x: P(x) | существует x такой что P(x) | any(P(x) for x in ...) |
a ∈ S | a принадлежит S | a in S |
a | b | a делит b | b % a == 0 |
P ⟺ Q | P тогда и только тогда когда Q | P == Q |
P → Q | из P следует Q | if P: assert Q |
∅ | пустое множество | set() |
A ⊂ B | A подмножество B | A < B или A.issubset(B) |
Чтение подстрочных и надстрочных индексов
В математике часто используются индексы:
| Запись | Читается | Что означает |
|---|---|---|
| a_i | ”a sub i” | Элемент с индексом i (как a[i]) |
| x^n | ”x в степени n” | x умноженное на себя n раз (x**n) |
| Z_p | ”Z sub p” | Целые числа по модулю p |
| GF(p) | “Galois field of p” | Конечное поле из p элементов (то же что Z_p для простого p) |
| a^(-1) | “a обратное” | Обратный элемент (pow(a, -1, p)) |
# В 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]Где вы это встретите
| Тема из этого урока | Где в курсе | Зачем |
|---|---|---|
| Двоичная/hex система | CRYPTO-04 (SHA-256) | Хеш-функции работают с битами и выдают hex |
| Нотация ≡ (конгруэнция) | CRYPTO-01 (модулярная арифметика) | Основная запись модулярных операций |
| Нотация ∀, ∈ | CRYPTO-02 (группы и поля) | Аксиомы группы записаны через ∀ и ∈ |
| Числовые множества Z, Z_p | Весь курс | Z_p — основное множество в криптографии |
| Степени x^n | CRYPTO-01, CRYPTO-08 (RSA) | Возведение в степень по модулю |
Что дальше?
В следующем уроке мы вспомним простые числа, делимость и НОД — фундамент, на котором строится вся криптография от модулярной арифметики до RSA.
Закончили урок?
Отметьте его как пройденный, чтобы отслеживать свой прогресс