В «Я беру 3072 для Пайе $n$", 3072, безусловно, битовый размер $n$. Таким образом, я прочитаю вопрос как:
Насколько широкими должны быть OU $n=p^2q$ быть таким же безопасным, как у Пайе $n=pq$ из 3072 бит?
Наиболее известной атакой на обе криптосистемы является факторизация $n$.
Самый известный метод факторизации $n=pq$ с $р$ и $q$ случайные простые числа примерно одинакового размера GNFS, стоимости $L_n[1/3,4\cdot3^{-2/3}]$, за обозначение LÂ.
Для факторизации $n=p^2q$, GNFS также работает с аналогичной стоимостью, поэтому мы должны иметь $n$ не менее 3072 бит. Однако, ЕСМ Ленстры также следует учитывать, и (я думаю) его стоимость составляет около $ L _ {\ мин (p, q)} [1/2,2 ^ {1/2}] $. Таким образом, чтобы максимизировать устойчивость к этому более позднему алгоритму, мы должны иметь $р$ и $q$ примерно такого же размера. Этот размер должен быть не менее 1024 бит, чтобы получить 3072-битное $n$. И если мы сделаем математику и проигнорируем $о(1)$ в $L_k[\alpha,c]=e^{(c+o(1))\ln(k)^\alpha\ln(\ln(k))^{1-\alpha}}$, мы получаем этот 1024-битный $р$ и $q$ (едва ли) достаточно, чтобы ECM был более дорогостоящим, чем GNFS.
Следовательно, мы должны иметь $р$ и $q$ не менее 1024 бит, например. в диапазоне $[2^{1024-1/3},2^{1024}]$ для 3072-бит $n$. Если мы хотим ошибиться из соображений безопасности, потому что мы проигнорировали $о(1)$, мы можем немного увеличить это, например. 1152-бит, например. в диапазоне $[2^{1152-1/3},2^{1152}]$ для 3456-бит $n$.
Тот же расчет поддерживает Цитата загадочного капитана Немо «Модули RSA должны иметь 3 простых фактора».
Дополнение: подтверждающие данные в системе Mathematica, дающие 0,5… (соответственно 10,3…) для логарифма по основанию 2 отношения работы между коэффициентами ECM @1024-бит (соответственно @1152 бит) к работе для GNFS @3072-битный продукт. Попробуйте онлайн!.
L[n_, a_, c_] := Exp[c (Log[n]^a) (Log[Log[n]]^(1-a))];
LGNFS[n_] := L[n, 1/3, 4 3^(-2/3)];
LLenstra[p_] := L[p, 1/2, 2^(1/2)];
Журнал[2., LLenstra[2^{1024,1152}]/LGNFS[2^3072]]
