The Gateway to Computer Science Excellence
0 votes
Alice and Bob use RSA public key encryption in order to communicate between them.
Trudy finds out that Alice and Bob shared one of the primes used to determine the
number n of their public key pairs. In other words, Trudy found out that na = pa × q
and nb = pb × q. How can Trudy use this information to break Alice’s code?
in Computer Networks by | 114 views

1 Answer

0 votes
According to the given question the intruder found out that A and B have a common prime factor

$(n_{a}, e_{a})$ and $(n_{b}, e_{b})$ are public keys

to find out the common factor the intruder finds GCD($n_{a}$, $n_{b}$)=q

as one of the common prime factors is found. The other primes can be found by

$p_{a}=\frac{n_{a}}{q}$ and $p_{b}=\frac{n_{b}}{q}$

now the intruder has both $n_{a}$ and $n_{b}$

next, the intruder can compute $\phi(n_{a})$ and $\phi(n_{b})$

to break A's ciphertext intruder needs private key of A which is $(d_{a}, n_{a})$

to find the private key, the intruder will simply apply

$e_{a}*d_{a}=1 MOD \phi(n_{a})$

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,375 questions
60,554 answers
95,374 users