Suppose that primes for RSA modulus are generated using formula:
$P_i(x,y) = \operatorname{next\_prime}(x^{z_i}+y^{z_i}) = x^{z_i}+y^{z_i}+d_i$
where $x,y$ are unknown random numbers with size 128 bits
$z_i$ - are known small integers exponents, lower than 16
$d_i$ - unknown small integer to make it prime

There is given number of primes(5) and exponents:
$Z = [4, 5, 7, 9, 11]$

It gives modulus with size about 4600 bits, primes are very unbalanced(~512,~640,~900,~1150,~1400 bits).
And finally modulus equation:
$N(x,y) = (x^4+y^4+d_0)*(x^5+y^5+d_1)*(x^7+y^7+d_2)*(x^9+y^9+d_3)*(x^{11}+y^{11}+d_4)$

Is that system of primes generation weak?
Can modulus be "easily"(on home computer) factored for given Z? Maybe for other Z too?
Can we use some variant of Coppersmith attack to factor(here are primes lower than $N^{1/4}$)?

  • 1
    $\begingroup$ Should be noted that this was a challenge at ASIS CTF Quals 2019, called "X Interpretation", by factoreal and nobody solved it. $\endgroup$ – Hyperflame Jun 14 at 6:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.