Comments 20
Зачем столько выделений? Вы считаете людей слепыми?
-5
Хм, интересно! Возникает 2 вопроса: можно ли зная n и e число щагов, необходимых для получения расшифрованного сообщения? Можно ли после того, как атака проведена, узнать p, q, или d?
0
Задача определения числа шагов этой атаки для вскрытия шифрсообщения пока даже не сформулирована и, конечно, не решена. Закрытый ключ, по-видимому, узнать можно по паре открытый текст шифрованный текст и n,e, но алгоритма пока нет. Вообще это проблемы алгебраического конечного кольца вычетов по составному модулю n
0
Жаль, спасибо! Занимаюсь проблемой RSA «на коленке» и не слышал ранее о такой атаке :-)
0
sage: multiplicative_order(Mod(7, 480))
4
Вот вам число шагов этой «атаки».
> Закрытый ключ, по-видимому, узнать можно по паре открытый текст шифрованный текст
А ничего что открытый ключ позволяет шифровать, и тем самым получать такие пары пачками?
+4
Нет, в процессе атаки ничего не подбирается, идет многошаговое шифрование на открытом ключе е шифртекста до совпадения результата с начальным шифртекстом. Для получения результата значения р и q не требуются. Имеются другие примеры, в которых открытый текст получаем за 60 шагов.
0
Всё так. Шифрование шифротекста (простите за каламбур) i раз выглядит так:
(((ce)e)…)e (mod n) = cei(mod φ(n)) (mod n), [1]
что довольно очевидно. Если для какого-то i будет в результате получен открытый текст, то также очевидно, что
ei = d (mod φ(n)), [2]
поскольку
cd (mod n) = med (mod n) = me ( ei (mod φ(n) ) (mod n). [3]
С этим разобрались. В вашем посте утверждается что могут существовать такие n и e, что формула [2] справедлива для малых i. Да, могут.
(((ce)e)…)e (mod n) = cei(mod φ(n)) (mod n), [1]
что довольно очевидно. Если для какого-то i будет в результате получен открытый текст, то также очевидно, что
ei = d (mod φ(n)), [2]
поскольку
cd (mod n) = med (mod n) = me ( ei (mod φ(n) ) (mod n). [3]
С этим разобрались. В вашем посте утверждается что могут существовать такие n и e, что формула [2] справедлива для малых i. Да, могут.
0
Выше уже написали, когда такое может быть.
0
Гораздо более интересен другой вопрос: можно ли по данным n и e оценить хотя бы порядок размера группы ei (mod φ(n))
-1
О группе, ее подгруппах и их порядках следует говорить в плане дальнейшего анализа проблемы. Конечно, в основе анализа лежит теорема Лагранжа о порядках подгрупп. До такого анализа руки пока не дошли (временной дефицит), но буду признателен, если кто-то возьмет на себя такой труд и оповестит о результатах.
-2
Что за бред? Вы и вправду планируете шифровать сообщения RSA с модулем такого размера? (да ещё и поблочно). Хотите показать атаку — покажите на достаточно большом модуле, который нельзя сломать втупую. Пусть даже модуль будет специально сформированным — это хотя бы покажет что данная атака может иметь место в реальности.
В любом случае в статье должно быть описано, в каких случаях данная атака работает, или хотя бы как это можно проверить, или хотя бы оценить вероятность при случайном выборе параметров. А то получается «параметры RSA выбирать надо осторожно, вот есть атака, хз когда её можно применить, но вы параметры выбирайте осторожнее, ага».
Если интересны адекватные атаки на RSA (а их очень и очень много), рекомендую обзор
Twenty years of attacks on the RSA cryptosystem (survey)
или целую книгу (одну из многих):
Cryptanalysis of RSA and Its Variants.
В любом случае в статье должно быть описано, в каких случаях данная атака работает, или хотя бы как это можно проверить, или хотя бы оценить вероятность при случайном выборе параметров. А то получается «параметры RSA выбирать надо осторожно, вот есть атака, хз когда её можно применить, но вы параметры выбирайте осторожнее, ага».
Если интересны адекватные атаки на RSA (а их очень и очень много), рекомендую обзор
Twenty years of attacks on the RSA cryptosystem (survey)
или целую книгу (одну из многих):
Cryptanalysis of RSA and Its Variants.
+9
Здесь скорее не про криптоанализ RSA как таковой, а про тупые ошибки в реализации.
0
Возможно Ваши претензии следует адресовать авторам учебного пособия «Основы криптографии» А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, Москва. «Гелиос АРВ», 2001г., на странице 316, что указаны в посте. Мне и самому этот пример стал интересен по нескольким причинам, часть которых совпадает с Вашими замечаниями. По этому пособию учат и рекомендуют учить завтрашних специалистов криптографов.
0
Касательно невозможности расшифровать некоторые значения. Я даже не знаю с чего начать, стока прям всего интересного вы понаписали.:)
Во-первых сами же говорите:
Теперь что касается самих шифруемых чисел 187, 341, 154 и 373. Тут от модуля конечно же ничего не зависит. При любом выбранном модуле будут наблюдаться числа, которые при шифровании будут равны сами себе. Об этом можно в 9 главе Handbook of Applied Cryptography почитать.
А вот если мы говорим о числа 187 и 341 то тут на самом деле проблема похлеще существует, чем та которую вы описали. Эти числа имеют общий делитель с числом N. Соответственно вычислив НОД(m, N) для таких сообщений атакующий сразу может вскрыть секретный ключ. Поэтому не стоит особо расстраиваться, что RSA не умеет шифровать такие числа, считайте это фичей.:)
Во-первых сами же говорите:
Экспонента е открытого ключа шифра может быть любым взаимно простым числом с функцией Эйлера φ(n)а сами в качестве примера зачем то приводите 2, 4, 9, 111, которые вовсе не взаимно простые с 480. Естественно, это приводит к тому, что расшифровать сообщение невозможно, т.к. эти числа необратимы по модулю φ(n).
Теперь что касается самих шифруемых чисел 187, 341, 154 и 373. Тут от модуля конечно же ничего не зависит. При любом выбранном модуле будут наблюдаться числа, которые при шифровании будут равны сами себе. Об этом можно в 9 главе Handbook of Applied Cryptography почитать.
А вот если мы говорим о числа 187 и 341 то тут на самом деле проблема похлеще существует, чем та которую вы описали. Эти числа имеют общий делитель с числом N. Соответственно вычислив НОД(m, N) для таких сообщений атакующий сразу может вскрыть секретный ключ. Поэтому не стоит особо расстраиваться, что RSA не умеет шифровать такие числа, считайте это фичей.:)
+4
ну вот. только задумал новую лабораторную для студентов подготовить, а вы тут сразу статью-решение.
теперь придется усложнять =)
теперь придется усложнять =)
-1
Sign up to leave a comment.
Выбор параметров шифра RSA и возможные последствия