0
$\begingroup$

I have a prime number, $p$, with $n$ bits. To generate a new prime number, $q$, I shift the bits of $p$ from left to right by a certain length. For example, if $p$ is represented as 1101110011 in base $2$ (which is $883$ in decimal) and it happens to be prime, I shift it one bit to the right, resulting in 1011100111 (which is $743$ in decimal) that is also prime. I then calculate $n$ as the product of $p$ and $q$, which serves as the RSA modulus for encryption. My question is whether this method is safe and secure for generating the RSA modulus.

For example, the $1024$-bit RSA modulus is generated using the method described above.

$n = $

63718268871597560696653954290116581339328462620726387291442709151555295568035819872493504
64060392834792456200674884691716619818185759860260778102047453963044402666539625420377995
81365586527381292006286694174283245096321055586348628562719185315653329548533123076367167
68258255097713817450042270958549927196063
$\endgroup$
3
  • 1
    $\begingroup$ HINT: $q=2(p-2^{n-1})+1$ $\endgroup$
    – Daniel S
    Dec 10, 2023 at 12:31
  • $\begingroup$ @DanielS: I think you mean that if the shift is one, then $q = 2\left(p - 2^{n-1}\right) - 1$. There is a typo in your formula. $\endgroup$
    – Lisbeth
    Dec 10, 2023 at 13:22
  • 1
    $\begingroup$ There is no typo. You can check this with your example $p=883$ and $q=743$. We have $743=2*(883-512)+1$. $\endgroup$
    – Daniel S
    Dec 10, 2023 at 17:25

1 Answer 1

2
$\begingroup$

No it is not secure, at least for small amount of shifts.

Lets assume we applied $k$ bits circular shift to $p$ and obtained $q$. The relationship between $p$ and $q$ becomes:

$q = 2^{k}.p-m.2^{n} +m$.

where $m$ is an integer that is represented by leftmost $k-bits$ of $p$ such that $(m<2^{k})$.

Then, since $N = pq$, we can write $N =p.(2^{k}.p-m.2^{n} +m)$ that yields:

$2^{k}.p^{2}+(m-m.2^{n}).p-N = 0$.

We know that there is a positive integer solution which is our $p$ and we can observe that products of the roots of equation is equal to $-N/2^{k}$ which is negative. So, we may directly say that

$$p=\frac{(m.2^{n}-m)+ \sqrt{(m.2^{n}-m)^2+4.2^{k}N}}{2^{k+1}}.$$

Since $p$ is an integer and $2^{k+1} \mid m.2^{n}$, we can expect:

$2^{k+1} \mid \sqrt{(m.2^{n}-m)^2+4.2^{k}N}-m$

So, $(m.2^{n}-m)^2+4.2^{k}N = (a.2^{k+1}+m)^2$ where $a$ is a positive integer.

As a result, $p= (m.2^{n}/2^{k+1}) +a.$

As an algorithm for finding $p$:

We guess the $m$ and check whether or not $(m.2^{n}-m)^2+4.2^{k}N$ is square and $2^{k+1} \mid \sqrt{(m.2^{n}-m)^2+4.2^{k}N}-m$. If conditions are satisfied, $p$ can be found as

$$p=\frac{(m.2^{n}-m)+ \sqrt{(m.2^{n}-m)^2+4.2^{k}N}}{2^{k+1}} = (m.2^{n}/2^{k+1}) +a.$$

Complexity of algorithm is $\mathcal{O}(2^k)$ where $k$ is amount of shifts. $k<30$ is feasible for standard pc. Due to the symmetry it works for $k>482$ for the case of $n = 512$.

I cannot define the security level of your method in general but since you have asked the question for "certain length", I can say it is not secure.

$\endgroup$
1
  • 1
    $\begingroup$ An even stronger attack is to use the bivariate Coppersmith attack for $p(X,Y)=(2^mX+Y)(2^{n-m}Y+X)-N$ where $X$ has $m-n$ bits and $y$ has $m$ bits (we can do an outer loop over at most $n$ values of $m$). $\endgroup$
    – Daniel S
    Dec 11, 2023 at 9:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.