I am studying RSA couldn't understand this question:

Alice encrypts the private factors of the modulus using her private key. In order to increase security, she multiplies them with a random integer $k$ she performs the following operations

$$cp = (k \cdot p)^e \bmod n \text{ and } cq = (k\cdot q)^e \bmod n,$$

n = 
e = 65537

Why this is not secure as anyone who obtains $cp$ or $cq$ can factor n.

Factor $n$ assuming

cp = 
  • source of the question? – kelalaka Nov 24 at 12:33
  • from my homework – doggodonger Nov 24 at 12:43

I will give the hint:

It is a simple Mathematics rule, given $cp, e$, and $n$ we have this relation:

$(k \cdot p)^e \equiv cp \bmod n$, then we can write this modular relation as;

$k^e \cdot p^e = cp + l\cdot n$, for some $l \in \mathbb{Z}$

$p$ divides $n$ that we already know, and from the equality, $p$ also divides the $np$

Rest left to the op.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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