Они доступны узким специалистам, но сложны для понимания, и удалились из широкого обсуждения.
не могу согласиться с вами. Для решения этой задачи можно использовать регистры сдвига с линейной обратной связью. Они имеют простую конструкцию, отличные (и даже доказуемые!) статистические свойства и относительно легко анализируются.
Но ведь они обсуждают все свои планы публично. Заранее известно что будут закупать/продавать. Разве сговор не требует наличие секрета? В чем разница между
1. Большая компания публично говорит что будет закупать акции чего-то и закупает их.
2. Толпа людей публично говорит что будет закупать акции чего-то и закупает их.
Интересно, можно ли идею алгоритма адаптировать для решения многомерных квадратичных уравнений на конечным полем. Возможно это позволило бы построить новую атаку на соответствующие криптосистемы, такие как Rainbow (финалист конкурса nist по постквантовой криптографии)
Было бы интересно увидеть сравнение этой модели с GPT-3. Обладает ли она полезными свойствами, как few-short learning? Или чем-то другим. Как она себя показала на различных тестовых заданиях? А то толку то с одного лишь количества параметров.
Кроме того он (Rijndael) использовал новые приемы шифрования, для которых не было разработан криптоанализ. Поэтому его сложность было тяжело оценить.
Rijndael как раз наоборот был спроектирован так, чтобы сложность атак было легко оценить на основе характеристик S-боксов и рассеивающего слоя. Это и стало решающим преимуществом над другими шифрами.
В случае RC6 из-за ARX дизайна намного сложнее дать оценку стойкости к различным атакам. Даже сейчас, спустя 20 лет! Думаю, это было одной из причин того, что он проиграл.
К хеш функциям и "генераторам рандома" предъявляются различные требования при разработке. Криптографические Хеш функции должны быть устойчивы к коллизиям, нахождению прообраза, нахождению второго прообраза и обеспечивать компрессию строк большой длинны в строку малого размера. Генераторы рандома должны уметь генерировать последовательность бит вычислимо неотличимую от случайной последовательности. Так как эти свойства хеш функций и псевдослучайных генераторов не являются эквивалентными, то соответственно криптопримитивы не взаимозаменяемыми в общем случае.
Когда криптоаналитик знает для каждого ключа, как распределены выбранные 8 битов на каждом слое, он может сравнить полученные распределения с теми, которые получаются в реальной системе. Для этого нужен доступ к алгоритму шифрования и большое количество текстов для шифрования. Из всех возможных ключей выбирается тот, который минимизирует расстояние между теоретическим и экспериментальным распределениями.
А какая реальная стоимость этой атаки на PRESENT? Насколько много надо пар открый текст/шифротекст?
А также функция распределения ошибок \chiберется нормальное распределение, для красивых формул в доказательствах);
не только для «красивых формул». Распределение так же влияет на безопасность прямым образом. Грубо говоря, при нормальном распределении требуются меньшие значения общесистемных параметров.
Однако нас интересует модификация задачи, так называемое обучение с ошибками на решётках (LWE on lattices).
Модификация? Нахождение решения «зашумленой» системы уравнений и решение задач на решетке, построенной ниже, это просто эквивалентное задание одной и той же задачи.
Немного добавлю от себя. Как правильно замечено в конце статьи, для криптографических применений необходима сложность в среднем (average case hardness), а не худшем случае (worst case hardness). Задача о ранце была первой попыткой привязать сложность к NP-полноте. Сейчас эта идея получила существенное развитие в криптографии на решетках. В 2005 году Regev предложил задачу LWE (Learning with errors) и доказал, что она имеет сложность в среднем, как задача GapSVP (NP-полная задача при определенных условиях) в худшем случае. Сейчас LWE и его модификации очень широко используются в криптографии на решетках. Но есть нюанс. В зависимости от параметров одна и та же задача может лежать в разных классах сложности. Те варианты LWE, которые используются на практике, лежат в пересечении NP и coNP, но они не обладают NP-полнотой. И более того, скорей всего, построить такую криптосистему, чтобы NP-полная GapSVP сводилась к LWE, не получится. (Это не доказано, но существует множество аргументов в пользу этого). Так что вопрос "а можем ли мы построить криптосистему, сложность которой основана на NP-полной задаче?" остается открытым и пока результаты не утешительные.
Небольшое замечание: в статье вы расматриваете только линейные диофантовые уравнения. Из заголовка кажется что в статье будет речь про общий случай. Кстати, в общем случае доказано, что не существует алгоритма, который узнавал бы по произвольному диофантову уравнению, имеет ли оно решения в целых числах или нет.
1. Большая компания публично говорит что будет закупать акции чего-то и закупает их.
2. Толпа людей публично говорит что будет закупать акции чего-то и закупает их.
Интересно, можно ли идею алгоритма адаптировать для решения многомерных квадратичных уравнений на конечным полем. Возможно это позволило бы построить новую атаку на соответствующие криптосистемы, такие как Rainbow (финалист конкурса nist по постквантовой криптографии)
Осталось биочипы изобрести)
Было бы интересно увидеть сравнение этой модели с GPT-3. Обладает ли она полезными свойствами, как few-short learning? Или чем-то другим. Как она себя показала на различных тестовых заданиях? А то толку то с одного лишь количества параметров.
Спасибо за интересную статью! Скажите, а почему нельзя было использовать ida pro или ghidra? Удобнее же чем свои велосипеды.
Ну и вот как после таких новостей не использовать маты? =)
Rijndael как раз наоборот был спроектирован так, чтобы сложность атак было легко оценить на основе характеристик S-боксов и рассеивающего слоя. Это и стало решающим преимуществом над другими шифрами.
В случае RC6 из-за ARX дизайна намного сложнее дать оценку стойкости к различным атакам. Даже сейчас, спустя 20 лет! Думаю, это было одной из причин того, что он проиграл.
К хеш функциям и "генераторам рандома" предъявляются различные требования при разработке. Криптографические Хеш функции должны быть устойчивы к коллизиям, нахождению прообраза, нахождению второго прообраза и обеспечивать компрессию строк большой длинны в строку малого размера. Генераторы рандома должны уметь генерировать последовательность бит вычислимо неотличимую от случайной последовательности. Так как эти свойства хеш функций и псевдослучайных генераторов не являются эквивалентными, то соответственно криптопримитивы не взаимозаменяемыми в общем случае.
high tech, low life
Касательно применения ещё можно добавить, что в Украине стандартизирована модификация SNOW 2 с 64-битными словами. (ДСТУ 8845:2019 "Струмок")
Немного добавлю от себя. Как правильно замечено в конце статьи, для криптографических применений необходима сложность в среднем (average case hardness), а не худшем случае (worst case hardness). Задача о ранце была первой попыткой привязать сложность к NP-полноте. Сейчас эта идея получила существенное развитие в криптографии на решетках. В 2005 году Regev предложил задачу LWE (Learning with errors) и доказал, что она имеет сложность в среднем, как задача GapSVP (NP-полная задача при определенных условиях) в худшем случае. Сейчас LWE и его модификации очень широко используются в криптографии на решетках. Но есть нюанс. В зависимости от параметров одна и та же задача может лежать в разных классах сложности. Те варианты LWE, которые используются на практике, лежат в пересечении NP и coNP, но они не обладают NP-полнотой. И более того, скорей всего, построить такую криптосистему, чтобы NP-полная GapSVP сводилась к LWE, не получится. (Это не доказано, но существует множество аргументов в пользу этого). Так что вопрос "а можем ли мы построить криптосистему, сложность которой основана на NP-полной задаче?" остается открытым и пока результаты не утешительные.
Вы как-то слишком серьезно мемы воспринимаете.
https://notabug.org/davidak/youtube-dl
Небольшое замечание: в статье вы расматриваете только линейные диофантовые уравнения. Из заголовка кажется что в статье будет речь про общий случай. Кстати, в общем случае доказано, что не существует алгоритма, который узнавал бы по произвольному диофантову уравнению, имеет ли оно решения в целых числах или нет.