73 lines
7.9 KiB
Markdown
73 lines
7.9 KiB
Markdown
|
## psycher
|
|||
|
|
|
|||
|
|
В данной задаче необходимо реализовать 128-битный линейный [блочный шифр](https://ru.wikipedia.org/wiki/Блочный_шифр). Этот cipher назван в честь psycho, придумавшего эту задачу.
|
|||
|
|
|
|||
|
|
### Шифрование за 5 минут
|
|||
|
|
|
|||
|
|
Шифрование - это способ обмена информацией так, чтобы противник, стоящий посередине, не узнал **ничего**.
|
|||
|
|
|
|||
|
|
Для такого свойства необходим секрет, которым владеют участники обмена информацией. Этот секрет может быть общим для обоих участников, тогда соответствующий шифр называется **симметричным** (примеры: aes, des). Если же ключи разные, то шифрование **асимметричное** (примеры: rsa, ecdsa).
|
|||
|
|
|
|||
|
|
С помощью секрета делается хитрое преобразование информации и передается собеседнику. Собеседник дешифрует со своим секретом и узнает, что было передано. Противник посередине видит преобразованное значение и ничего не понимает.
|
|||
|
|
|
|||
|
|
Блочный шифр - это разновидность симметричного шифра. Отличительная особенность в том, что имеется простой интерфейс - принять блок данных фиксированного размера (обычно 64-256 бит) и зашифровать/дешифровать его. По сути шифр - функция {0,1}^n -> {0,1}^n, причем такая, что значение на выходе *не отличимо* от рандомно сгенерированного значения
|
|||
|
|
|
|||
|
|
Для шифрования данных произвольного размера используются режимы шифрования. По сути данные разбиваются на привычные блоки для блочного шифра, шифруются им и комбинируются хитрым образом (комбинирование и есть суть режима шифрования). По сути результат шифрования более поздних блоков зависит от предыдущих. Такую зависимость нужно вводить, чтобы не показывать противнику паттерны в данных от блоков. (режимы шифрования в задаче не потребуются, это рассказано просто в образовательных целях)
|
|||
|
|
|
|||
|
|
### Легенда psycher
|
|||
|
|
|
|||
|
|
Представьте себе пространство {0,1}^128 над полем {0,1}. А теперь давайте возьмем в нем какой-нибудь базис и будем переводить в него векторы из тривиального базиса [{1, 0, 0, ...}, {0, 1, 0, ...}, ...]
|
|||
|
|
|
|||
|
|
Вы спросите, зачем нам это делать? А теперь я расскажу что придумал
|
|||
|
|
|
|||
|
|
|
|||
|
|
Выбранный базис в виде 128 векторов размерности 128 будет нашим симметричным ключом. Шифрование данных - это перевод вектора в этот базис. Дешифрование - обратное преобразование.
|
|||
|
|
|
|||
|
|
При выборе произвольного базиса результат преобразования будет определенно неотличим от произвольной последовательности бит (ну, кроме нулевого вектора). То есть получился полноценный шифр!
|
|||
|
|
|
|||
|
|
Вообще теория говорит, что линейные шифры - это некруто и на практике их не так сложно взломать, как кажется. Но зато такой шифр отлично подходит для оттачивания навыков с курса :)
|
|||
|
|
|
|||
|
|
### Я программист, можно на человеческом?
|
|||
|
|
|
|||
|
|
Да, можно. При создании объекта шифра нам передается список из 128 значений, каждое - 128 бит (нигде не проверяется, но давайте считать, что данные представляют собой линейно независимые векторы).
|
|||
|
|
|
|||
|
|
При шифровании нужно сделать следующее:
|
|||
|
|
1. Собираем все позиции в битовом представлении входных данных (128-битный блок)
|
|||
|
|
2. Применяем xor всех значений с данными позициями из списка инициализации объекта
|
|||
|
|
3. Возвращаем результат
|
|||
|
|
|
|||
|
|
Более того, этот функционал уже реализован в тестовом файле.
|
|||
|
|
|
|||
|
|
Для дешифрования нужно решать систему линейных уравнений. Это скучно, давайте не реализовывать дешифрование.
|
|||
|
|
|
|||
|
|
### Ничего не понял, а задача-то в чем?
|
|||
|
|
|
|||
|
|
А предоставленное решение-то медленное. Надо его ускорить.
|
|||
|
|
|
|||
|
|
Здесь вам помогут знания об оптимизациях компилятора, умение работать с бенчмарками и pprof.
|
|||
|
|
|
|||
|
|
Авторское решение лучше наивного примерно в 60 раз. Здесь не учитывается время создания шифра, но не стоит злоупотреблять этим. В идеале нужно понимать, какого размера шифротексты в среднем подаются на вход, т.е. сколько раз вызовется функция шифрования, чтобы правильно выбрать баланс между более тяжелым New и более тяжелым Encrypt. Rule of thumb - использовать не более единиц-десятков КБ доп памяти.
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
cpu: Intel(R) Core(TM) i7-9850H CPU @ 2.60GHz
|
|||
|
|
BenchmarkSlowCipher
|
|||
|
|
BenchmarkSlowCipher-12 731576 1592 ns/op 10.05 MB/s 0 B/op 0 allocs/op
|
|||
|
|
BenchmarkCipher
|
|||
|
|
BenchmarkCipher-12 39978231 26.47 ns/op 604.54 MB/s 0 B/op 0 allocs/op
|
|||
|
|
PASS
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### Подсказка по оптимизации
|
|||
|
|
|
|||
|
|
Можно использовать следующую схему. Она описывает порядок, в котором нужно оптимизировать программу.
|
|||
|
|
|
|||
|
|
1. Алгоритм (улучшение асимптотической сложности, константы)
|
|||
|
|
2. Распараллеливание (разделяй и властвуй, здесь надо понять стоят ли накладные расходы того)
|
|||
|
|
3. Микрооптимизации кода (pprof, gcflags -m, аллокации, ...)
|
|||
|
|
4. Hardware оптимизации (кэш процессора, asm, unsafe)
|
|||
|
|
|
|||
|
|
На каждом шаге можно вернуться наверх, если приходит хорошая идея. Но тогда дальнейшие шаги возможно нужно перепридумать. И не обязательно в каждом что-то делать, это скорее порядок, в котором надо подумать.
|
|||
|
|
|
|||
|
|
|
|||
|
|
|