# Is a prime shifting method for RSA modulus generation safe?

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

• HINT: $q=2(p-2^{n-1})+1$ Dec 10, 2023 at 12:31
• @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. Dec 10, 2023 at 13:22
• There is no typo. You can check this with your example $p=883$ and $q=743$. We have $743=2*(883-512)+1$. Dec 10, 2023 at 17:25

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.

• 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$). Dec 11, 2023 at 9:34