Вычисления по модулю
Равенство a ≡ b mod m означает, что a и b дают одинаковый остаток при делении на m. Для байтов часто используют модуль 256. После сложения или умножения берут остаток, чтобы результат снова оказался в диапазоне 0–255.
В преобразовании y = (a·x + b) mod 256 восстановление имеет вид x = a⁻¹·(y−b) mod 256. Обратный множитель a⁻¹ существует тогда и только тогда, когда gcd(a, 256) = 1. Для модуля 256 это означает нечётное a.
Рабочий пример
Пусть y = (5x + 7) mod 256. Число 205 обратно к 5, потому что 5·205 = 1025 ≡ 1 mod 256. Если y=76, то x = 205·69 mod 256 = 65.
a, b, m = 5, 7, 256
inv = pow(a, -1, m)
y = 76
x = (inv * (y - b)) % m
assert (a*x + b) % m == y
print(x) # 65Как обращать цепочку
Если прямой путь — XOR, затем сложение, затем перестановка, обратный путь начинается с обратной перестановки, потом вычитания и только затем XOR. Для зависимого состояния учитывай, использует ли следующий шаг старый или уже обновлённый байт.
Что помнить про RSA
В учебной модели n=pq, а открытая степень e и секретная d связаны обратимостью по подходящему модулю. Но реальная безопасность RSA зависит не только от арифметики: нужны достаточные параметры и корректная схема дополнения. Не переносить «голый» учебный RSA в настоящую защиту данных.
Типичные ошибки: деление обычным / вместо обратного элемента; забытый модуль после вычитания; попытка обратить чётный множитель modulo 256; проверка только первых символов результата.
Материалы для углубления