количество раундов и длина пароля.

gazlan

чё -то ты не туда гребёшь: ты разделяй кодирование с целью сжатия и кодирование с целью шифрования.
одно дело, когда зашифровали сжатый текст - другое, когда не сжатый: даже зная плейнтекст, задача уже сложней, ибо архив со своей более высокой энтропией увеличивает кол-во вероятностных зависимостей при использование стат-ких методик слома. алгебраические методы тоже будут испытывать неудобства) да, и, вообще, надо помнить, что все методы слома заточены на текст: взять тот же слом ксора - вопрос: этот метод будет пахать на архиве или медийном файле?)
TOLSTOPUZ

мля, не люблю жестоких людей) [Шутка]
псевдораспаковка - идея неплоха, но я сделаю иначе)

 

Я не об этом. Не о паковке и не о шифровании. О самом понятии "избыточность" - это вешь, которой нет. Фиктивный параметр. Как "центробежная сила" или "центр тяжести".

И, разумеется, знание модели источника (характеристик сообщения) обязательный элемент взлома зашифрованного сообщения. Не имея такой модели, невозможно установить даже сам факт дешифровки

 

Какой же это миф?
Избыточность можно увидеть, глянув в любую книгу. Буква А в некой пропорции появляется чаще чем буква Ф.

Конечно при анализе одного сектора избыточность не увидишь.
Но искать закономерность в секторе - глупо. Особенно если ключ равен сектору.
Можно ведь проанализироваь сходство самих секторов по определённому алгоритму. (Не буду приводить тут...)
И при большом количестве секторов неминуемо вылезет закономерность. А тут уже и карты в руки...
Ключа это может и не даст, но ограничит пределы автоперебора. И если использован известный шифр, то взлом вероятно реален именно из-за этой злокознённой избыточности.

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

 

gazlan

Просто ты не знаешь определения. Избыточность зависит от используемой кодировки.
Как только ты распаковал текст в открытую - внес избыточность. Записал стенографическим кодом - уменьшил избыточность и т.д.

 

Не поделитесь идейками?
Так, для общего развития, для политесу...
Подискутируем...

 

gazlan
нашёл миф)))))) благодаря этому "legend" есть шифры, кои можно сломать без поиска ключа: самые простые примеры: код цезаря (подстановки с сохранением статистики появления символа) и ксор.

 

Сильно ушли от темы топика, но все же ...

Да хоть от погоды на Марсе. Перечитываем вопрос.

Более формально: имеются два взаимно-однозначных преобразования над текстом - прямое и обратное (упаковка\распаковка, шифрование\дешифрование, cyrillic\translit, Win-1251\KOI8-R etc). Иными словами, "прямой" и "обратный" текст _идентичны_ с точностью до обозначений.

"Избыточность" - такой же миф в теории информации, как "флогистон" - в теории горения.

_Любой_ шифр ломается перебором (исключая одноразовый блокнот), если точно известна модель источника.
Англичане занимались этим еще во время War II ("тикающая бомба"). Без знания же модели источника невозможно дешифровать даже оригинальный шифр Цезаря.

Но модель несводима к "избыточности".

 

gazlan

ну, ты отжигать начал)))))))) да, любой взлом является перебором, только область перебора на каждом шаге может сужаться меньше/больше - брутфорс - это перебор всех состояний заданного унивёрсума)

одно знания что плейнтекст на евроязыке являет собой хорошую модель)

 

gazlan
и ещё один момент, избыточность - это основополагающие понятие для всех трёх направлений кодирования (помехоустойчивость, сжатие, шифры). ничего мифического тут и впомине нет.

 

gazlan,
Вы лично пробовали себя
во взломе какого-нибудь шифра?
Есть подвижки?

Блин, пишу кратко один из своих АЛГО как взломать несжатый текст.

Итак возможные варианты связок:
сектор 64 ключ 56
сектор 64 ключ 64
...
...
... сектор 256байт ключ 256 байт

+++++++++++++++++++++++++++
JMP_NEXT
Ломаем вариант
сектор 256байт ключ 256 байт
(Какой алгоритм - нам пофиг. Мы поймаем этот самый миф - избыточность)
если соблюдается правило - "сектор 256байт ключ 256 байт"


В секторе могут быть такие варианты::

байт ключа 0h шифрует байт текста 0h = байт шифросимвола 1x
байт ключа 0h шифрует байт текста 1h = байт шифросимвола 2x
байт ключа 0h шифрует байт текста 2h = байт шифросимвола 3x
байт ключа 0h шифрует байт текста 3h = байт шифросимвола 4x
...
...
байт ключа 0FFh шифрует байт текста FFh = байт шифросимвола 65536x

===============================================================

Итак: в секторе размером 256 байт с ключом 256 байт
возможны 65536 вариантов байт шифросимвола.
Но самым частым вариантом сочетаний будет всё-таки
байт ключа - диапазон (0h-0FFh) шифрует байт текста "A"

Так как нам известно, что это САМАЯ распространённая буква.

Итак мы получили самый распространённый символ сектора:
Вот он:

диапазон 0h-0FFh

Улыбки на лицах - это же вся таблица ASCII.

Но думаем напряжённей - мы и не собираемся ловить в секторе символ "А".
Мы поймаем сам пароль. По повторениям сочетаний этих символов.
Для этого нам нужно единственное -
- иметь 65536 или больше РАЗНЫХ секторов для получения статистики сочетаний.

(Конечно это минимум. Реальней в 20-100 раз более)

И если зашифрован обычный несжатый русский текст, мы получаем сам пароль.
Если и не точный, то диапазон ну просто очень мал, теперь ломаем его перебором и читаем "Войну и Мир"

А теперь допустим что текст сжат. НУ И ЧТО? Ну НЕ МОЖЕТ архиватор дать 100% энтропию. НЕ МОЖЕТ. Пусть он сжал текст на 99%. Для его взлома и получения ключа нам нужно теперь 65536Х100 секторов. (файл полтора Гигабайта) И мы ломаем его даже не распаковывая архив.
Уточнение - полтора Гига - это минимум, как вы поняли.
Навряд ли бывают зашифрованные сообщения такого размера. Единственный способ их получить - постоянный перехват и "накопление".
И самый простой способ защититься - как только общий объём шифротекста перевалил за критический для нас Гигабайт - меняем пароль. Пусть противник снова копит файлы.
Математика однако...

P.S.
Вот Ваш упомянутый одноразовый блокнот как раз и даёт отсутствие избыточности.

invoke Odnoraz_bloknot,ADDR plentext,ADDR algo,ADDR sifertext

 

TOLSTOPUZ

математика для криптоаналитика депрессивная наука))
--------
ваш призыв к дискуссии пока поддержать не могу - нет времени на занятие своим алгосом, занят другим делом. когда сделаю, с удовольствием с вами подисскутирую.

 

TOLSTOPUZ

тут вы не правы: ваш алгос будет ломать алгосы, где ключ на каждом шаге тот же. если на каждом шаге key=f(key), то ситуация резко усугубляется.

 

Ошибаетесь.
Эта распространённая схема тоже ненадёжна. Если Вы с авторучкой в руках немного сосредоточитесь, то также увидите простой алгоритм взлома. Она ломается. Если кратенько - опять таки всё равно вылезает закономерность. Но к сожалению (или к счастью) только в математической модели, где время взлома и количество секторов можно обозначить как бесконечность. (Пардон, даже не бесконечность, а реальное время, но очень большое). Получить в "нашем мире" такое количество секторов с шифротекстом нереально - очень уж большое число.
Но в математической модели - дыра! Ломается! А это уже не есть хорошо.

Я изобразил общее направление. И даже не это.
Я хотел подчеркнуть, что если и дальше следовать канону, что главное - спрятать истинную избыточность за счёт длины ключей реально делает текст неуязвимым, но в математической модели остаются изъяны.

А вот "игры с теорией вероятности" позволяют замахнуться на "святая святых" - реально уничтожить настоящую избыточность. Это я о методе подмены настоящей избыточности ложной, организованной по принципу

Сжатие - Разжатие по ключу с созданием ложной избыточности.

Мы подменяем самое главное - избыточность.

И вот как раз тут математические модели не смогут работать. То есть они конечно с лёгкостью вычислят текст по избыточности, но при открытии там будет всякая хренотень.

Интересное направление... Да и пароль... Достаточно 2 байтов пароля... (Если потом поддельную избыточность дополнително зашифровать популярным методом.


P.S.
Пардон, только что математически "сломал" этот метод...
Нужно в секторе просто перебрать все вероятности поддельных избыточностей, а потом ещё просто взломать обычный шифр...

Блин, цифры такие... Скажем так, большие... На практике уж точно не взломаешь...

 

Я вот тут сижу сейчас перед работой, дурью маюсь, пытаюсь изобразить нелепую задачку.
Кратенько звучит "переменная длина сектора".
Длина следующего сектора зависит от (варианты).

 

TOLSTOPUZ

в том -то и дело) и заметьте: обработка большого кол-ва секторов будет медленней, нежели простой перебор ключа, правда, нужно знать сифер.

 

У вас есть ответ на первоначальный вопрос (в №19)?
После этого я с удовольствием выслушаю все остальное.

AES не ломал (и не планирую). А всякие "home made" поделки - во множестве (зашифрованные словники электронных словарей, базы данных итп). Самой трудной оказалась DBF-база от Aladdin: XOR, длина ключа 16 Kb (длину ключа определил только с третьей попытки), plain text'a у меня не было. База оказалась двуязычной (английский/иврит).

 

gazlan

итак, надеюсь, вы не отрицаете понятие "оптимальное кодирование" . избыточность - это когда блок длины x бит имеет вероятность появления P, где x>lg2(P). на основе этого факта и работают архиваторы, используя этот миф, для не мифических результов более того, замечу, что классическое определение избыточности более узко, чем на самом деле - простой пример: с рядом чисел (1, 2, 3...n) 7z не справится, меж тем сжатие сего не составляет труда.

 

И причем тут "избыточность". "Оптимальное кодирование" _по_определению_ является _переименованием_. Я, по-прежнему, прошу сначала ответить на поставленный вопрос.

Какие-то вы не те книжки читаете ...

Статические методы сжатия НЕ используют вероятности - все события уже свершились, они оперируют детерминированными частотностями.

Существует ровно две модели компрессии (+ их комбинация): 1) битовые цепочки постоянной длины заменяются на битовые цепочки переменной длины (Haffman etc) и 2) битовые цепочки переменной длины заменяются на битовые цепочки постоянной длины (LZ etc).

При использовании статических методов все сжатие сводится к табличной замене одних цепочек на другие (по сути - к переименованию). В динамических методах эти таблички обновляются по мере обработки текста.

 

gazlan

вы придираетесь, однако))

моделей больше, чем две: есть ещё координатное кодирование и на теорие множеств тоже можно замутить алгосы.
------
но меж тем вы правы, как это непародоксально прозвучит)), правда, вы плохо доказываете свою правоту сейчас:
во - первых, избыточность есть, но в шифрах архив мало что даёт, впрочем, в моём алгосе он будет полезен
во -вторых: любой архив, в утрированном виде, состоит из таблицы и вереницы ссылок на элементы этой таблицы. ссылки невыровнены по границе 8x бит, что усложняет анализ, к тому же, они могут быть разной длины, но порядок следования, безусловно, тот же - вот это и являет собой зацепку для криптоаналитика.
-----------
в итоге: архив полезен (особенно с ссылками варьированной длины), меж тем преувеличивать его значение не стоит.

 

Где-то я этот самодельный термин уже видел. Отправим его туда же, куда и избыточность. Никаких других моделей (кроме двух указанных) не существует.

Что касается шифрования, то хотя цели и различны, методы, в сущности, одинаковы. Все то же самое, только преобразования управляются не только входными данными, но и ключом.

В классической постановке, шифрование - это аддитивное подмешивание к информации шума. Грубо говоря, (независимый) сдвиг/поворот по каждой из степеней свободы исходного сообщения. Если вы представите себе эти преобразования как некие обобщенные сдвиг и поворот в дискретной нелинейной системе координат, то алгебраическая тождественность компрессии и шифрования станет очевидной. Разница только в "траектории движения" - при компрессии минимизируют "обобщенный объем", при шифровании - "дисперсию". Поскольку минимизация "объема" одновременно минимизирует "дисперсию", статистически компрессия и шифрование неразличимы. Семантически же, компрессия - это "шифрование с открытым ключом". Спрячьте таблицы подстановок ("ключ") - и архив превратится в шифровку

Гм. На compression.ru вы этого, наверное, не прочитаете, но сжатие данных - это классическая задача обработки (трансляции) текста. По классической же двухфазной схеме: 1. лексический анализ 2. синтаксический анализ

Lexer разбивает входной поток на лексемы (в простейших случаях - побайтно),
Parser обрабатывает поток лексем в соответствии с заданной грамматикой (в простейших случаях - просто табличная замена).

Статическим методам сжатия соответствует компиляция, динамическим - интерпретация (набор лексем и грамматика могут изменяться "по ходу игры").

IMHO, сейчас для вас "деревья" ("ссылки невыровнены по границе 8x бит") скрывают "лес" - очень простую, в сущности, модель преобразования данных.

Думайте не в терминах "таблицы и вереницы ссылок", а займитесь лексическим анализатором - ключ к высокой компрессии здесь: в построении адекватной модели источника. Собственно сжатие (кодирование) - это рутина. Обычно выбирают между H и Ari + детали имплементации (RLE, MTF, BWT etc). Ну, и всякие прочие глупости: хранить данные в хэш-таблице или суффиксном дереве, как выбрать глубину обратной связи (демпфирование), чем инициализировать словарь итп. На эту тему есть сотни книг и тысячи статей - и изучив их все, можно выжать еше полпроцента компресии или быстродействия.