Не так давно на одном из контестов codechef была такая же задачка. Только базы систем исчисления произвольные от 2 до 16, и нужно было первые 1000 палиндромов меньшие 2^60. Ограничение по времени — 8 сек (правда на входе может быть 5 тестов). Editorial там же есть.
> По количеству пользователей RC5 стоит в одном ряду с такими известными алгоритмами как IDEA и Blowfish.
Можно какие-нибудь ссылки, откуда инфа?
По поводу криптанализа — шифр взломан ещё в прошлом веке (с точки зрения академической криптографии), и с тех пор им почти никто не интересуется (опять же, среди криптоаналитиков). Поэтому утверждение
> у алгоритма RC5 практически отсутствуют недостатки с точки зрения его стойкости
слишком самоуверенно. Вы предлагаете 18-20 раундов для 32х битной версии (причем только как замечание в конце статьи), но вы не знаете какую стойкость эта версия гарантирует. 2^60? 2^70? Кроме того, «революционное решение» использовать переменные сдвиги очень сомнительное. Есть ли примеры не таких старых невзломанных шифров, использующих этот приём? А «поразительная простота» алгоритма, которая вас удивила, давно породила парадигму ARX шифров.
Я понимаю что статья про имплементацию чего попало на питоне, но почему бы не использовать для этого современные шифры?
К недостаткам логично отнести то что ключ 2n бит даёт стойкость всего n бит. За 2^n ломается очевидным mitm'ом. Соответственно, логично либо использовать один и тот же ключ два раза, либо использовать KDF (чтобы получить из одного ключа два). Есть ли у этих способов слабости, или, наоборот, доказательства стойкости?
Нечто похожее, но на системах линейных уравнений, уже есть — Learning With Errors. Насколько я помню, LWE считается (но не доказано) сложной проблемой для квантовых компьютеров, поэтому активно продвигается в post-quantum криптосистемах.
Большая эээ, как вы называете, «энтропия» входных данных как раз не способствует стойкости шифра, а наоборот. Чтобы статистически «запутать» все биты текста и ключа, при большем размере входных данных потребуется больше раундов. Вы взяли количество раундов «от балды», и для 512 бит это может оказаться недостаточным.
Кроме того, насколько видно из схемы — диффузия в вашем шифре очень слабая (грубейшая ошибка!): межбайтовая диффузия есть только там, где сложение первого байта с 6м, и 4го с 5м. По сути, ваш шифр практически полностью байт-ориентирован и наверняка подвержен Integral attack, не говоря про обычные дифференциалы.
Описывать проектирование шифра и не замолвиться о диффузии — это, простите, фэйл. Не говоря про остальные косяки. Вместо создания недошифра, лучше бы в качестве примера разобрали какой-нибудь известный шифр.
Да вы правы, со сложением это только аддитивная группа.
Замечание было скорее в том, что сложение по модулю степени двойки к полям не имеет никакого отношения (кроме степени = 1). В конечном поле GF(2^k) сложение это xor. Сложение по модулю простого числа — это сложение в конечном поле, да.
Только M * M1 а не M + M1. Ну и библиотека, которую использует автор, использует PKCS1.5 паддинг так что эта модификация идёт лесом (но на PKCS1.5 есть куча других атак, нужно использовать OAEP).
Во первых иллюстрировано не шифрование с помощью RSA, а обмен ключами. Во вторых, либо я неправильно понял аналогию, либо тут ошибка: если чемодан — публичный ключ, а «ключ» — приватный — то Саша не должен посылать обратно свой ключ, только чемодан.
А вот это предложение вообще ерунда какая-то:
Теперь Тимуру больше не нужен свой чемодан и свой ключ. Он может пользоваться теми, что ему передал Саша.
Шифрование бы выглядело так:
1. Тимур даёт Саше чемодан (публичный ключ)
2. Саша кладет туда сообщение и захлопывает, отдаёт обратно.
3. Тимур открывает ключом чемодан и читает сообщение.
Вроде там PCKS1.5 используется. Он конечно тоже взломан, но не так печально как совсем без паддинга. Ну а автор действительно некомпетентен, раз не понимает даже при чем тут блоки. Видимо поэтому большая часть статьи — картинки не по теме.
Примерно так работает алгоритм шифрования RSA. Ключ, конечно, можно подобрать или расшифровать. Но на этой уйдет 2^32 попыток. Это очень много, и для этого нужно очень много мощных компьютеров, которые будут работать несколько дней. Т.к. ключи могут меняться в ходе переписки, то задача становится еще более трудоемкой.
Можно какие-нибудь ссылки, откуда инфа?
По поводу криптанализа — шифр взломан ещё в прошлом веке (с точки зрения академической криптографии), и с тех пор им почти никто не интересуется (опять же, среди криптоаналитиков). Поэтому утверждение
> у алгоритма RC5 практически отсутствуют недостатки с точки зрения его стойкости
слишком самоуверенно. Вы предлагаете 18-20 раундов для 32х битной версии (причем только как замечание в конце статьи), но вы не знаете какую стойкость эта версия гарантирует. 2^60? 2^70? Кроме того, «революционное решение» использовать переменные сдвиги очень сомнительное. Есть ли примеры не таких старых невзломанных шифров, использующих этот приём? А «поразительная простота» алгоритма, которая вас удивила, давно породила парадигму ARX шифров.
Я понимаю что статья про имплементацию чего попало на питоне, но почему бы не использовать для этого современные шифры?
Может base64 было бы достаточно? Или недостаточно «мешанины»?
Кроме того, насколько видно из схемы — диффузия в вашем шифре очень слабая (грубейшая ошибка!): межбайтовая диффузия есть только там, где сложение первого байта с 6м, и 4го с 5м. По сути, ваш шифр практически полностью байт-ориентирован и наверняка подвержен Integral attack, не говоря про обычные дифференциалы.
Описывать проектирование шифра и не замолвиться о диффузии — это, простите, фэйл. Не говоря про остальные косяки. Вместо создания недошифра, лучше бы в качестве примера разобрали какой-нибудь известный шифр.
Замечание было скорее в том, что сложение по модулю степени двойки к полям не имеет никакого отношения (кроме степени = 1). В конечном поле GF(2^k) сложение это xor. Сложение по модулю простого числа — это сложение в конечном поле, да.
А вот это предложение вообще ерунда какая-то:
Шифрование бы выглядело так:
1. Тимур даёт Саше чемодан (публичный ключ)
2. Саша кладет туда сообщение и захлопывает, отдаёт обратно.
3. Тимур открывает ключом чемодан и читает сообщение.
PS: я больше угорел по тексту на http://bakhirev.biz/demo/crypto/#!view=how_works:
И вроде бы не 1е апреля…