Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 20
Зачем столько выделений? Вы считаете людей слепыми?
Хм, интересно! Возникает 2 вопроса: можно ли зная n и e число щагов, необходимых для получения расшифрованного сообщения? Можно ли после того, как атака проведена, узнать p, q, или d?
Задача определения числа шагов этой атаки для вскрытия шифрсообщения пока даже не сформулирована и, конечно, не решена. Закрытый ключ, по-видимому, узнать можно по паре открытый текст шифрованный текст и n,e, но алгоритма пока нет. Вообще это проблемы алгебраического конечного кольца вычетов по составному модулю n
Жаль, спасибо! Занимаюсь проблемой RSA «на коленке» и не слышал ранее о такой атаке :-)
sage: multiplicative_order(Mod(7, 480))
4
Вот вам число шагов этой «атаки».
> Закрытый ключ, по-видимому, узнать можно по паре открытый текст шифрованный текст
А ничего что открытый ключ позволяет шифровать, и тем самым получать такие пары пачками?
Нет, в процессе атаки ничего не подбирается, идет многошаговое шифрование на открытом ключе е шифртекста до совпадения результата с начальным шифртекстом. Для получения результата значения р и q не требуются. Имеются другие примеры, в которых открытый текст получаем за 60 шагов.
Всё так. Шифрование шифротекста (простите за каламбур) 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. Да, могут.
Выше уже написали, когда такое может быть.
Гораздо более интересен другой вопрос: можно ли по данным n и e оценить хотя бы порядок размера группы ei (mod φ(n))
О группе, ее подгруппах и их порядках следует говорить в плане дальнейшего анализа проблемы. Конечно, в основе анализа лежит теорема Лагранжа о порядках подгрупп. До такого анализа руки пока не дошли (временной дефицит), но буду признателен, если кто-то возьмет на себя такой труд и оповестит о результатах.
Что за бред? Вы и вправду планируете шифровать сообщения 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.
Здесь скорее не про криптоанализ RSA как таковой, а про тупые ошибки в реализации.
Возможно Ваши претензии следует адресовать авторам учебного пособия «Основы криптографии» А.П. Алферов, А.Ю. Зубов, А.С. Кузьмин, А.В. Черемушкин, Москва. «Гелиос АРВ», 2001г., на странице 316, что указаны в посте. Мне и самому этот пример стал интересен по нескольким причинам, часть которых совпадает с Вашими замечаниями. По этому пособию учат и рекомендуют учить завтрашних специалистов криптографов.
Касательно невозможности расшифровать некоторые значения. Я даже не знаю с чего начать, стока прям всего интересного вы понаписали.:)
Во-первых сами же говорите:
Теперь что касается самих шифруемых чисел 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 не умеет шифровать такие числа, считайте это фичей.:)
ну вот. только задумал новую лабораторную для студентов подготовить, а вы тут сразу статью-решение.
теперь придется усложнять =)
теперь придется усложнять =)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Выбор параметров шифра RSA и возможные последствия