Двоичная система и битовые операции

Вспомните

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

1. Что вернет 170 & 85 в Python? А 170 ^ 85?

2. Сколько бит в байте? А в слове SHA-256?

3. Как перевести число 0xFF в десятичную систему?

Если ответили уверенно — отлично, пробегитесь по разделу для проверки. Если нет — этот урок для вас. Каждый раунд SHA-256 работает с 32-битными словами, а все ключи и хеши отображаются в hex.

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

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

Перевод из десятичной в двоичную: делим на 2 и собираем остатки снизу вверх.

Пример: 170 в двоичной

170 / 2 = 85, остаток 0
 85 / 2 = 42, остаток 1
 42 / 2 = 21, остаток 0
 21 / 2 = 10, остаток 1
 10 / 2 = 5,  остаток 0
  5 / 2 = 2,  остаток 1
  2 / 2 = 1,  остаток 0
  1 / 2 = 0,  остаток 1
Читаем снизу вверх: 10101010

# Python:
print(bin(170))          # '0b10101010'
print(int('10101010', 2)) # 170

# Каждый SHA-256 раунд оперирует 32-битными словами:
word = 0b11010010000100100001001001101000  # 32 бита
print(f"{word:032b}")  # двоичное с ведущими нулями

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

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

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

Попробуйте:

• Установите 255 — все нибли FF
• Установите 256 — видно, как переход через 1 байт меняет структуру
• Установите 48879 (0xBEEF) — hex используется даже для мнемонических значений

# Hex в Python:
print(hex(255))           # '0xff'
print(int('FF', 16))      # 255

# Приватный ключ Bitcoin -- 32 байта = 64 hex-символа:
key_hex = "a1b2c3d4" * 8  # пример 256-битного ключа
print(f"Длина: {len(key_hex)} hex-символов = {len(key_hex) * 4} бит")

Битовые операции

Битовые операции работают с каждым битом отдельно. Это основа криптографических алгоритмов — SHA-256 использует AND, OR, XOR, NOT и ротации в каждом из 64 раундов.

AND (&) — оба бита должны быть 1

Аналогия: фильтр. Оставляет только те биты, которые установлены в обоих числах. В SHA-256 используется в функции Ch(e, f, g) = (e AND f) XOR (NOT e AND g).

OR (|) — хотя бы один бит равен 1

Аналогия: объединение. Собирает биты из обоих чисел.

XOR (^) — ровно один бит равен 1

XOR — король криптографии. Почему? Потому что XOR обратим: a ^ b ^ b = a. Это свойство лежит в основе:

• Шифрования: XOR с ключом шифрует, XOR с тем же ключом расшифровывает
• SHA-256: функции Sigma и sigma строятся на XOR ротаций
• One-time pad: единственный теоретически невзламываемый шифр — это XOR с одноразовым ключом

# XOR обратим:
secret = 42
key = 137
encrypted = secret ^ key   # 163
decrypted = encrypted ^ key # 42 -- исходное значение!
assert decrypted == secret

NOT (~) — инвертирует все биты

Побитовое дополнение. В Python ~n дает -(n+1) для знаковых чисел, поэтому для 8-битной маски используйте ~n & 0xFF.

Битовые сдвиги и ротация

Левый сдвиг (left shift) <<

Сдвигает все биты влево, заполняя нулями справа. Эквивалент умножения на 2.

print(170 << 1)  # 340 (в 8-битном: 10101010 -> 01010100 = 84)
print(1 << 8)    # 256 (быстрый способ вычислить 2^8)

Правый сдвиг (right shift) >>

Сдвигает все биты вправо, отбрасывая младшие. Эквивалент целочисленного деления на 2.

print(170 >> 1)  # 85 (10101010 -> 01010101)
print(170 >> 4)  # 10 (10101010 -> 00001010)

Циклическая ротация (rotate)

В Python нет оператора ротации, но SHA-256 активно её использует. При ротации биты, “выпадающие” с одного конца, появляются с другого:

def rotr(x, n, bits=32):
    """Циклическая ротация вправо на n позиций (32-битное слово)."""
    return ((x >> n) | (x << (bits - n))) & ((1 << bits) - 1)

# SHA-256 sigma0: ROTR(x,7) XOR ROTR(x,18) XOR SHR(x,3)
x = 0xDEADBEEF
sigma0 = rotr(x, 7) ^ rotr(x, 18) ^ (x >> 3)
print(f"sigma0(0x{x:08X}) = 0x{sigma0:08X}")

Байт, слово, порядок байтов

Endianness (порядок байтов):

• Big-endian: старший байт первый. SHA-256 и сетевые протоколы.
• Little-endian: младший байт первый. x86 процессоры, Bitcoin.

# Big-endian vs Little-endian:
n = 0x01020304
print(n.to_bytes(4, 'big'))    # b'\x01\x02\x03\x04'
print(n.to_bytes(4, 'little')) # b'\x04\x03\x02\x01'

Справочник Python

# Конвертация
bin(42)              # '0b101010'
hex(42)              # '0x2a'
int('101010', 2)     # 42
int('2A', 16)        # 42

# Битовые операции
a & b                # AND
a | b                # OR
a ^ b                # XOR
~a                   # NOT
a >> n               # Right shift
a << n               # Left shift

# Байты
int.from_bytes(b'\xff\x00', 'big')     # 65280
(255).to_bytes(1, 'big')               # b'\xff'

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

Что дальше?

В следующем (необязательном) уроке мы вспомним функции и координатную плоскость — подготовка к CRYPTO-09 (Эллиптические кривые). Если вы уверены в этих темах, переходите сразу к CRYPTO-01: Модулярная арифметика.