Например, модуль RSA Пайе равен $n=pq$, а модуль RSA OU равен $p^2q$. Я думаю, что когда два $n$ одинаковы, безопасность двух криптографических схем должна быть разной. Например, если я возьму 3072 для $n$ Пайе, сколько времени мне потребуется для $n$ OU?
#гомоморфное шифрование #paillier
В фразе «Я беру 3072 за $n$ Пайе» 3072, несомненно, соответствует битовому размеру $n$. Поэтому я прочитаю вопрос так:
Насколько широкой должна быть $n=p^2q$ OU, чтобы она была такой же безопасной, как $n=pq$ Пайе, составляющая 3072 бита?
Самая известная атака на обе криптосистемы — это факторизация $n$.
Самый известный метод факторизации для $n=pq$ со случайными простыми числами $p$ и $q$ примерно одинакового размера: ГНФС, стоимостью $L_n[1/3,4\cdot3^{-2/3}]$, за Обозначение L.
Для факторизации $n=p^2q$ GNFS также работает с аналогичной стоимостью, поэтому мы должны иметь $n$ как минимум 3072-битный. Однако, ЕСМ Ленстры также следует учитывать, и (я думаю) его стоимость составляет около $L_{\min(p,q)}[1/2,2^{1/2}]$. Таким образом, чтобы максимизировать устойчивость к этому более позднему алгоритму, мы должны иметь $p$ и $q$ примерно одинакового размера. Этот размер должен быть не менее 1024 бит, чтобы получить 3072-битный $n$. А если мы посчитаем и проигнорируем $o(1)$ в $L_k[\alpha,c]=e^{(c+o(1))\ln(k)^\alpha\ln(\ln( k))^{1-\alpha}}$, мы получаем, что 1024-битных $p$ и $q$ (едва) достаточно, чтобы ECM был более дорогим, чем GNFS.
Следовательно, мы должны иметь $p$ и $q$ как минимум 1024-битные, например. в диапазоне $[2^{1024-1/3},2^{1024}]$ для 3072-битного $n$. Если мы хотим ошибиться на всякий случай, потому что мы проигнорировали $o(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)];
Log[2., LLenstra[2^{1024,1152}]/LGNFS[2^3072]]
![[EMPO ,Сергей Яременко] Мастер-класс по веб-аналитике](/assets/images/icons/forum4.png){kind=icon}
![[калугин Алексей] Javascript С Самого Начала](/assets/images/icons/forum1.png){kind=icon}
