Гарантии вывода алгоритмов сжатия / шифрования - PullRequest
4 голосов
/ 25 ноября 2011

Мой вопрос здесь касается алгоритмов сжатия / шифрования в целом и для меня звучит как полный нубийский. Теперь я понимаю, что «в целом» «все зависит», но предположим, что мы говорим об алгоритмах, которые имеют справочную реализацию / опубликованные спецификации и в целом являются настолько стандартными. Чтобы быть более конкретным, я использую .NET реализации AES-256 и GZip / Deflate

Так что вот так. Можно ли предположить, что при точно одинаковых входных данных оба типа алгоритмов будут давать точно одинаковых выходных данных.

Например, будет ли вывод aes(gzip("hello"), key, initVector)) в .NET идентичным выводу в Mac или Linux?

Ответы [ 2 ]

6 голосов
/ 25 ноября 2011

AES определяется жестко, поэтому при одинаковом вводе, одинаковом алгоритме и одинаковом ключе вы получите одинаковый вывод.

Нельзя сказать то же самое для почтового индекса.

Проблема не стандартная. Существует определенный стандарт: поток Deflate - IETF RFC 1950 , поток gzip - IETF RFC 1952 , поэтому любой может создать совместимый zip-компрессор / декодер, начиная с этих определений.

Но zip принадлежат большому семейству компрессоров LZ, которые по своей конструкции не являются ни биективными, ни инъективными. Это означает, что из одного источника существует множество способов описать один и тот же вклад, который действителен, хотя и различен.

Пример. Допустим, мой ввод: ABCABCABC

Допустимые выходы могут быть:

  • 9 литералов

  • 3 литерала, за которыми следует одна копия длиной 6 байтов, начиная со смещения -3

  • 3 литерала, за которыми следуют две копии длиной 3 байта каждая, начиная со смещения -3

  • 6 литералов, за которыми следует одна копия длиной 3 байта, начиная со смещения -6

  • и т.д.

Все эти выходы действительны и описывают (регенерируют) один и тот же вход. Очевидно, что один из них более эффективен (сжимает больше), чем другие. Но вот где реализация может отличаться. Некоторые будут более могущественными, чем другие. Например, известно, что kzip и 7zip генерируют более качественные (более сжатые) zip-файлы, чем gzip. Даже у gzip есть много вариантов сжатия, генерирующих разные сжатые потоки, начиная с одного и того же ввода.

Теперь, если вы хотите постоянно получать один и тот же двоичный вывод, вам нужно больше, чем просто «zip»: вам нужно обеспечить реализацию точной zip и точный параметр сжатия. Тогда вы будете уверены, что генерируете всегда один и тот же двоичный файл.

2 голосов
/ 25 ноября 2011

AES определен в качестве стандарта, поэтому любая соответствующая реализация действительно выдаст тот же результат. GZip - это программа, поэтому возможно, что разные версии программы будут давать разные результаты. Я ожидаю, что более поздняя версия сможет переформатировать вывод из более ранней версии, но обратное может быть невозможным.

Как уже говорили другие, если вы собираетесь сжимать, то сожмите обычный текст, а не шифротекст из AES. Cyphertext не будет хорошо сжиматься, так как он спроектирован так, чтобы казаться случайным.

...