The Gateway to Computer Science Excellence
0 votes
31 views
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 Boss (10.5k points) | 31 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})$
by Active (5k points)

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
50,650 questions
56,242 answers
194,293 comments
95,944 users