Почему безопасность RSA зависит от не-факторизуемости модуля n?

Question

Просто интересно, почему безопасность RSA зависит от не-факторизуемости модуля n?

Cheers!

Answer 1

хорошо ... не-факторизуемости модуля п не вся история ...

, как влад уже отмечалось, вы можете легко вычислить частный показатель, если вы знаете, факторы п ..

(p-1) (q-1) ... или более вообще ... если вы знаете простые множители P [i] числа n, то вы можете вычислить произведение всех (P [i] - 1) ... это функция PHI Эйлера ... знать число обратимых мультипликативных элементов mod n

Если вы можете разложить n, то вычисление станет тривиальным ... если n состоит только из 2 большой при mes, и эта факторизация сложна, но это не совсем тривиально ...

однако ... если вы придумаете другую идею вычисления PHI (n) ... числа элементов mod n, которые имеют мультипликативный обратный ... факторизация не будет больше, вероятно, не будет ваша проблема ...

в настоящее время нет другого общественного известный способ расчета фи, чем eulers образом ... тычок (P [я] - 1)

, так что либо найти способ факторизации, либо вычислить PHI (n) по-другому, вероятно, приведет к разрыву RSA

Answer 2

Публичные данные в RSA - это n - публичный модуль, а e - публичный показатель. Секрет d - частный экспонент. При создании параметров вы сначала генерируете два случайных числа p и q, а затем вычисляете открытый модуль n = p * q. Итак, p и q - факторизация n. На самом деле вы можете использовать больше простых чисел, но большинство из них используют только два. Затем вы выбираете общедоступный показатель e, который обычно представляет собой небольшое число, такое как 65537 или 17 или даже 3. Ваш секретный показатель d будет тогда d = 1/e mod (p-1) (q-1).

Так ясно, что любой может вычислить d, если они знают p и q, что является факторизацией.