2
$\begingroup$

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 = 
14522618414940330316720825703581818668232873090304101572437636625555724423016860272078630876437311699654574728861003760005749922965011995280733350140951078582251915088752445284367570052512244148190787248024210133865389997079370997487944695554576118063909791694130590309282475787773038629510027418889258775385528586923797001536550693747542175352795990447587607573178468163072638937166644494792819801190648017979291433924036979787320417318300097159771644354505341347447630385539964985486870484105658158920683576559610148645140369543464668029642924347163891332219762178122417025302960610955472998102936056418443726953009 
e = 65537

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

Factor $n$ assuming

cp = 
3873680249623467826367539364615622589341354860958676387978659380263546197984522526560815271059808890968051330871282433149509587198357995235098402597562394532942248440785823812744245775541457429705400656431200565210880345454073114392081573852975647397894188392554441729200872482027630124098341536309658821020887879754305515982200459718246770965592051443891902975413068576099241022023087113547866192282458339642152774673429640500380196758464923112739607056897968627591289881579460166394238775676402099831162820645802017259999853129954464949014713129189051795007415064128397315657343793939830810688657224114493477678984
$\endgroup$
  • $\begingroup$ from my homework $\endgroup$ – doggodonger Nov 24 '18 at 12:43
0
$\begingroup$

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.

$\endgroup$

Your Answer

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

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