Любой начинающий программист на haskell/scheme/другом_яфп реализовывал эти тривиальные примеры применения рекурсии. В С же везде тут рекурсия является лишней и только замедляет работу программы (особенно ужасен фибоначчи с двойной рекурсией).
Из нерекурсивных обмен переменных — но он весьма затаскан и о недостатках его говорилось очень много.
Из википедии: en.wikipedia.org/wiki/Entropy_(information_theory)
The entropy rate of English text is between 1.0 and 1.5 bits per letter, or as low as 0.6 to 1.3 bits per letter, according to estimates by Shannon based on human experiments.
Анализ последовательностей символов — это автокорреляция.
И это в случае если комбинация процедуры расширения ключа и исходного шифра будет надежной и не породит новых уязвимостей, или их еще не обнаружат при криптоанализе, так как они всегда есть в таких комбинациях и теоретически позволяют свести сложность атаки на комбинированный шифр до максимума из этих двух сложностей.
Расширение ключа как одна из операций комбинированного шифра используется, и часто помогает его улучшить, но это опять же наворачивание дополнительных улучшений на исходный шифр перестановки.
Сложность атаки будет примерно = сложность_атаки_на_шифр_перестановки * сложность_атаки_на_ГПСЧ, использованный при расширении ключа.
Файл внутри PE exec — знаем, что первые два байта MZ/PE, узнаем первые два символа перестановки, перебор сокращается в 1122 раз.
Статистическое распределение символов внутри перестановка сохраняет — можем узнать тип содержимого, проанализировать условные вероятности последовательностей символов — энтропия английского текста на уровне 1-1.5 бит на символ, следовательно корреляционная атака сократит ключ еще раз в 6-8. А там и перебирать останется совсем капли.
Вот еще пример бинарного файла, выбрал что побольше:
$ ent /usr/bin/emacs
Entropy = 4.189078 bits per byte.
Optimum compression would reduce the size
of this 10803128 byte file by 47 percent.
Chi square distribution for 10803128 samples is 859695276.68, and randomly
would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 56.3785 (127.5 = random).
Monte Carlo value for Pi is 3.784757856 (error 20.47 percent).
Serial correlation coefficient is 0.470131 (totally uncorrelated = 0.0).
обратите внимание на последнюю строку — она как раз показывает автокорреляцию данного файла, т.е. отклонение от равновероятностьи различных последовательностей символов. Даже не зная информацию о содержимом, это можно использовать в корреляционной атаке.
ГПСЧ не берут энтропию из воздуха — она берут ее только из ключа. Если вариантов ключа меньше, чем перестановок, ключами будет только подмножество всех возможных перестановок мощности 2^размер_ключа
Насчет легковзламываемости имелось ввиду — при сопоставимой длинне ключа с другими шифрами. Перестановочные шифры имеют значительно худшие храктеристики в равных условиях.
4096 перестановка — ключ размера 43250.046889935249 бит. Сравните с AES 256 бит ключа. Даже 128 бит AES на практике не взламывается, хотя считается в перспективе не надежным.
Чистые шифры перестановок очень чувствительны к избыточности исходного сообщения. Их надежность падает экспоненциально при уменьшении энтропии относительно максимальной. Простейший пример — сигнатуры файлов в которых положение определенных байт известно — позволяет уменьшить n! до (n-k)!.. Также известны вероятностные распределения символов для естественных языков — можно использовать любую избыточность.
Да, конечно, можно использовать алгоритмы сжатия и другие преобразования, увеличивающие энтропию или преобразовывающие известное распределение в неизвестное — но это уже комбинированный шифр, а в их составе перестановки вполне имеют место.
Томский государственный. А под криптографией я имел ввиду «основы криптографии» и «введение в компьютерную безопасность» на первом курсе, «теория чисел в криптографии» на втором, «криптографические методы защиты информации» на третьем, «булевы функции в криптографии» на четвертом и «криптографические протоколы», «аппаратная реализация криптоалгоритмов», «конечно-автоматные криптосистемы» и «квантовая криптография» на пятом. Очень подробные курсы, с обширной теорией и практикой. www.fpmk.tsu.ru/entrance/directions/
Не злитесь, это слова человека, которому пять лет в университете вдалбливали криптографию. А хабр — не личный бложик, чтобы постить на него все что в голову пришло, невзирая на полезность и адекватность пришеднего. Я же не лезу на CNN вещать свои дилетантские мысли на тему экономики.
Все существующие шифры перестановки с легкостью взламываются с помощью компьютера. Ваш шифр неплохо бы пошел на школьную олимпиаду по криптографии, не больше.
«И тогда мой мозг понесся думать про XOR-шифрование. Оно ведь довольно простое, а я думал, как можно его улучшить.» — алгоритм XOR-шифрования (или, более канонично, шифр Вернама), несмотря на свою простоту, является абсолютным шифром (скорее всего единственным таковым) — в случае одноразовых равновероятных ключей длиной с само сообщение. А ваш шифр вообще из категории шифров перестановки, не понимаю как его можно считать «улучшенным» шифром Вернама.
Но согласитесь, рекламировать гугл на площадках самого гугла — занятие довольно глупое. Необходимо привлекать пользователей со стороны. К тому же в США у них нехилая конкуренция с Bing'ом, который активно пытается отжать часть рынка у гугла.
Условие последней С4 для меня не совсем ясно. В условии говориться про максимальное произведение скоростей — интепретировать числа как скорости, или как числа? Если как скорости, то необходимо найти максимальное произведение по модулю (какая разница, в какую сторону летят частицы, если нам важна их скорость), если же как числа — без модуля.
Из нерекурсивных обмен переменных — но он весьма затаскан и о недостатках его говорилось очень много.
The entropy rate of English text is between 1.0 and 1.5 bits per letter, or as low as 0.6 to 1.3 bits per letter, according to estimates by Shannon based on human experiments.
Анализ последовательностей символов — это автокорреляция.
Сложность атаки будет примерно = сложность_атаки_на_шифр_перестановки * сложность_атаки_на_ГПСЧ, использованный при расширении ключа.
Статистическое распределение символов внутри перестановка сохраняет — можем узнать тип содержимого, проанализировать условные вероятности последовательностей символов — энтропия английского текста на уровне 1-1.5 бит на символ, следовательно корреляционная атака сократит ключ еще раз в 6-8. А там и перебирать останется совсем капли.
Вот еще пример бинарного файла, выбрал что побольше:
$ ent /usr/bin/emacs
Entropy = 4.189078 bits per byte.
Optimum compression would reduce the size
of this 10803128 byte file by 47 percent.
Chi square distribution for 10803128 samples is 859695276.68, and randomly
would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 56.3785 (127.5 = random).
Monte Carlo value for Pi is 3.784757856 (error 20.47 percent).
Serial correlation coefficient is 0.470131 (totally uncorrelated = 0.0).
обратите внимание на последнюю строку — она как раз показывает автокорреляцию данного файла, т.е. отклонение от равновероятностьи различных последовательностей символов. Даже не зная информацию о содержимом, это можно использовать в корреляционной атаке.
4096 перестановка — ключ размера 43250.046889935249 бит. Сравните с AES 256 бит ключа. Даже 128 бит AES на практике не взламывается, хотя считается в перспективе не надежным.
Да, конечно, можно использовать алгоритмы сжатия и другие преобразования, увеличивающие энтропию или преобразовывающие известное распределение в неизвестное — но это уже комбинированный шифр, а в их составе перестановки вполне имеют место.
www.fpmk.tsu.ru/entrance/directions/