Is a prime shifting method for RSA modulus generation safe?

Question

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

Answer 1

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.