В 1024-битных продуктах, созданных в соответствии с
к описанному методу, если вы повторно используете F.
Если N1 и N2 созданы с одним и тем же F, F можно рассчитать
немедленно:
G = НОД(N1-1,N2-1) = 2Fk.
Фактор G, чтобы получить F, что легко заметить, потому что его длина составляет 461 бит.
Кроме того, безопасность может быть значительно ослаблена, если
сложность факторинга N-1 значительно легче, чем факторинга N.
N-1 представляет собой композит, который может быть значительно проще факторизован, чем
1024-битное произведение двух 512-битных простых чисел.
На основании определений и ограничений F, p и q в вопросе:
N = (2Fp+1)(2Fq+1)
Расширение
N = 4*F^2pq+2Fp+2Fq+1
Перестановка
N = 2F(2Fpq+p+q)+1
N-1 = 2F(2Fpq+p+q)
После факторизации N-1 у вас есть F, прибл. 461-битное простое число.
Пусть u будет (N-1)/2F = (2Fpq+p+q)
и = (2Fpq+p+q)
Затем вычислите s = mod(u,2F) = p+q,
д = с-р
Замените s-p на q и s на p+q
и = (2Fp(s-p)+s)
u = 2Fps-2Fp^2+s
Это приводит к квадратичному по p
-2Fp^2+2Fsp+s-u = 0
p = (Fs - sqrt (F (Fs ^ 2 + 2s - 2u)))/(2F)
д = с-р
Теперь можно вычислить два приблизительно 512-битных простых числа.
N = (2Fp+1)(2Fq+1)
Обратите внимание, что факторинг N-1 все еще может занять значительное время.
требуется GNFS или CADO-NFS, но все же значительно проще учитывать
чем 1024-битное произведение двух 512-битных простых чисел.
