📚 Введение
Битовые операции — основа многих криптографических и системных алгоритмов. Почему? Потому что:
- Они быстрые.
Нет делений, умножений — только сдвиги, AND, OR, XOR. - Они точные.
Работают напрямую с представлением данных в памяти. - Их любят компиляторы, криптографы и интервьюеры.
🧩 Задача 1: Установить флаг в битовой маске
Условие:
Дано целое число flags, в котором каждый бит — это флаг. Установить k-й флаг в 1.
flags = 0b00000000 # Все флаги выключены (все биты 0)
k = 3 # Нужно включить 4-й бит (нумерация с нуля)
flags |= (1 << k) # Сдвигаем 1 влево на k позиций → получаем маску: 0b00001000
# Затем применяем побитовое ИЛИ: устанавливаем нужный бит
print(bin(flags)) # Вывод: 0b1000
🧠 Зачем это нужно?
Так работают флаги состояния: например, FLAG_IS_ENCRYPTED, FLAG_IS_ADMIN, и пр.
🧹 Задача 2: Сбросить флаг
Условие:
Выключить k-й флаг в числе flags.
flags = 0b11111111 # Все флаги включены (все биты = 1)
k = 5 # Хотим выключить 6-й флаг
flags &= ~(1 << k) # Создаём маску: 1 << 5 = 0b00100000
# Инвертируем: 0b11011111
# Применяем побитовое И: убираем 6-й бит
print(bin(flags)) # Вывод: 0b11011111
🔍 Полезно при сбросе флагов состояний, например, "отключить авторизацию".
🔍 Задача 3: Проверка, установлен ли бит
Условие:
Проверить, установлен ли k-й бит в flags.
flags = 0b00100000 # Бит 5 установлен
k = 5
is_set = bool(flags & (1 << k)) # Сдвигаем 1 влево: 0b00100000
# Побитовое И покажет ненулевой результат, если бит установлен
print(is_set) # True
✅ Используется, например, чтобы проверить, активирован ли флаг "has_permission".
🔁 Задача 4: Инвертировать бит
Условие:
Поменять значение k-го бита: если 1 → 0, если 0 → 1.
flags = 0b10101010 # Чередование битов
k = 1 # Меняем второй бит (с конца)
flags ^= (1 << k) # XOR с маской: бит "переключится"
print(bin(flags)) # 0b10101000
🔁 Этот трюк часто используется для переключения режима: "включить, если выключено", и наоборот.
🔐 Задача 5: XOR-шифрование строки
Условие:
Зашифровать строку с помощью XOR и расшифровать её тем же ключом.
message = "hello" # Строка для шифрования
key = 42 # Простой числовой ключ
# Шифруем: каждый символ превращаем в код и XOR'им с ключом
encrypted = [ord(c) ^ key for c in message]
print(encrypted) # Список зашифрованных чисел
# Расшифровка — просто повторный XOR с тем же ключом
decrypted = ''.join(chr(c ^ key) for c in encrypted)
print(decrypted) # hello
🔑 Почему это работает?
Потому что a ^ k ^ k = a.
Так работает однократный шифр (One-Time Pad) — в простейшем виде.
🔄 Задача 6: Поменять местами два бита
Условие:
Дано число, нужно поменять местами биты с индексами i и j.
def swap_bits(n, i, j):
# Проверим: если биты отличаются, только тогда меняем
if ((n >> i) & 1) != ((n >> j) & 1):
# XOR двух масок "переключит" оба бита
n ^= (1 << i) | (1 << j)
return n
print(bin(swap_bits(0b10100100, 2, 5))) # 0b10000110
🔁 Используется в перестановках в DES, AES, SHA и других шифрах.
🎲 Задача 7: Генерация псевдослучайных чисел (LFSR)
Условие:
Сгенерировать последовательность псевдослучайных чисел на основе LFSR (linear feedback shift register).
def lfsr(seed, taps):
reg = seed # Начальное значение регистра
while True:
xor = 0
for t in taps:
xor ^= (reg >> t) & 1 # Получаем нужный бит и XOR'им
reg = ((reg << 1) | xor) & 0xFFFF # Сдвиг и вставка нового бита
yield reg # Возвращаем текущее значение
gen = lfsr(0b1010010010000001, [15, 13]) # Старшие биты как "тапы"
for _ in range(5):
print(bin(next(gen))) # Последовательность из 5 псевдочисел
🧠 Используется в потоковых шифрах, генераторах ключей и даже в Bluetooth.
🧮 Задача 8: Подсчёт единичных битов (битовая плотность)
Условие:
Посчитать, сколько бит установлено в 1 в числе n.
def count_ones(n):
count = 0
while n:
n &= n - 1 # Убираем младший установл. бит
count += 1
return count
print(count_ones(0b10101100)) # 4
📦 Используется для оценки энтропии, веса Хэмминга и анализа шифрованных данных.
📦 Задача 9: Упаковка и распаковка флагов
Условие:
Упаковать 4 бита (a, b, c, d) в байт, а затем распаковать их обратно.
def pack_flags(a, b, c, d):
# Каждый бит ставим на нужную позицию и объединяем
return (a << 3) | (b << 2) | (c << 1) | d
def unpack_flags(flags):
# Достаём каждый бит маской и сдвигом
return ((flags >> 3) & 1, (flags >> 2) & 1, (flags >> 1) & 1, flags & 1)
flags = pack_flags(1, 0, 1, 1)
print(bin(flags)) # 0b1011
print(unpack_flags(flags)) # (1, 0, 1, 1)
🧩 Так кодируются конфигурации, права доступа, байты настроек и флаги заголовков в сетях.
🔁 Задача 10: Реверс битов
Условие:
Развернуть число n в пределах bit_size бит (перевернуть порядок битов).
def reverse_bits(n, bit_size=8):
res = 0
for _ in range(bit_size):
res = (res << 1) | (n & 1) # Сдвигаем результат влево и добавляем младший бит
n >>= 1 # Сдвигаем исходное число вправо
return res
print(bin(reverse_bits(0b11010010))) # 0b01001011
🔍 Зачем это нужно?
Реверс битов используется в криптографических и хэш-функциях (например, SHA-1, SHA-256), при быстром преобразовании форматов и даже в алгоритмах визуализации, например, быстрое преобразование Фурье (FFT) на графических процессорах.
🧠 Итоги
Битовые операции — это не просто низкоуровневый хардкор. Это:
- 🎯 Оптимизация: с ними можно делать быстрее, чем с классическими условными операциями.
- 🧩 Минимализм: вы упаковываете максимум информации в минимум байтов.
- 🔐 Криптография: без битовых трюков не было бы ни DES, ни AES, ни RSA.
📚 Дополнительно: где это используется в криптографии
🔐 Продолжение: Биты в криптографии — своими руками:
🔬 Глава 1: Свой мини-шифр на основе XOR + LFSR + перестановки битов
Цель: создать простой потоковый шифратор, используя:
- XOR — для шифрования,
- LFSR — как генератор ключевого потока,
- битовую перестановку — для запутанности (confusion).
✅ Что будем делать:
- Дано: строка message, битовый ключ seed, перестановка битов.
- Нужно: зашифровать и расшифровать.
def lfsr(seed, taps, bits=8):
"""Генератор псевдослучайных чисел с помощью LFSR"""
reg = seed
while True:
xor = 0
for t in taps:
xor ^= (reg >> t) & 1
reg = ((reg << 1) | xor) & ((1 << bits) - 1)
yield reg
def permute_bits(byte, pattern):
"""Переупорядочиваем биты по заданному шаблону"""
result = 0
for i, pos in enumerate(pattern):
result |= ((byte >> pos) & 1) << i
return result
# Шаблон перестановки: биты 0 → 2, 1 → 5, 2 → 0 и т.д.
permutation = [2, 5, 0, 7, 3, 6, 1, 4]
seed = 0b10100101
taps = [7, 5]
gen = lfsr(seed, taps)
message = "hello"
encrypted = []
# Шифрование
for char in message:
key = next(gen)
mix = ord(char) ^ key
obfuscated = permute_bits(mix, permutation)
encrypted.append(obfuscated)
print("Encrypted:", encrypted)
# Расшифровка (инвертируем перестановку)
inverse_perm = [permutation.index(i) for i in range(8)]
gen = lfsr(seed, taps)
decrypted = ''
for byte in encrypted:
key = next(gen)
unperm = permute_bits(byte, inverse_perm)
decrypted += chr(unperm ^ key)
print("Decrypted:", decrypted)
🧠 Итог: ты только что построил простейший потоковый шифр с перестановкой и генерацией ключа.
⚙️ Глава 2: Свой MiniAES с S-box
S-box (Substitution box) — это таблица, которая заменяет один байт на другой. Используется в AES для внесения "нелинейности".
✅ Упрощённый S-box и MiniAES
# Мини-S-box (частичная таблица замены)
SBOX = [
0x6, 0x4, 0xC, 0x5,
0x0, 0x7, 0x2, 0xE,
0x1, 0xF, 0x3, 0xD,
0x8, 0xA, 0x9, 0xB
]
def sbox_sub(byte):
"""Заменяет каждый полубайт (4 бита) через S-box"""
high = SBOX[(byte >> 4) & 0xF]
low = SBOX[byte & 0xF]
return (high << 4) | low
def encrypt_block(byte, key):
"""Простейшее шифрование: сначала XOR, потом S-box"""
byte ^= key # Ключевой XOR
byte = sbox_sub(byte) # Нелинейная подстановка
return byte
def decrypt_block(byte, key):
"""Обратное шифрование: инвертированный S-box, затем XOR"""
# Получаем обратный S-box
INV_SBOX = [0]*16
for i, val in enumerate(SBOX):
INV_SBOX[val] = i
high = INV_SBOX[(byte >> 4) & 0xF]
low = INV_SBOX[byte & 0xF]
byte = (high << 4) | low
return byte ^ key
message = "Hi!"
key = 0x3C
# Шифрование
encrypted = [encrypt_block(ord(c), key) for c in message]
print("Encrypted:", encrypted)
# Расшифровка
decrypted = ''.join(chr(decrypt_block(c, key)) for c in encrypted)
print("Decrypted:", decrypted)
💡 Пример показывает, как работает логика S-box замены, как в AES, только намного проще.
📡 Глава 3: Упаковка TCP-заголовков с помощью битовых флагов
Контекст: в TCP-заголовке есть 6 основных флагов: URG, ACK, PSH, RST, SYN, FIN. Каждый — 1 бит. Мы упакуем их в байт и распакуем.
✅ Упаковка:
def pack_tcp_flags(URG, ACK, PSH, RST, SYN, FIN):
return (URG << 5) | (ACK << 4) | (PSH << 3) | (RST << 2) | (SYN << 1) | FIN
flags = pack_tcp_flags(URG=1, ACK=1, PSH=0, RST=0, SYN=1, FIN=0)
print(bin(flags)) # 0b110010
✅ Распаковка:
def unpack_tcp_flags(byte):
return {
"URG": (byte >> 5) & 1,
"ACK": (byte >> 4) & 1,
"PSH": (byte >> 3) & 1,
"RST": (byte >> 2) & 1,
"SYN": (byte >> 1) & 1,
"FIN": byte & 1,
}
print(unpack_tcp_flags(flags))
🛰️ Так устроены заголовки сетевых пакетов: каждый бит = отдельный смысл. И всё это нужно упаковывать быстро и компактно.
🧠 Финал: что ты теперь умеешь
Ты своими руками реализовал:
- Потоковый шифр на XOR + LFSR + permute
- Упрощённую версию S-box из AES
- Упаковку и декодирование TCP-флагов с помощью битов
🔒 Всё это — не учебные игрушки, а базовые элементы настоящей криптографии и сетей.