Log In
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 125 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

1 vote
2 answers
Using the RSA public key cryptosystem, with a = 1, b = 2 . . . y = 25, z = 26. (a) If p = 5 and q = 13, list five legal values for d. (b) If p = 5, q = 31, and d = 37, find e. (c) Using p = 3, q = 11, and d = 9, find e and encrypt ‘‘hello’’.
asked Mar 19, 2019 in Computer Networks ajaysoni1924 198 views
0 votes
1 answer
A math class has 25 students. Assuming that all of the students were born in the first half of the year—between January 1st and June 30th— what is the probability that at least two students have the same birthday? Assume that nobody was born on leap day, so there are 181 possible birthdays.
asked Mar 19, 2019 in Computer Networks ajaysoni1924 115 views
0 votes
0 answers
Alice wants to communicate with Bob, using public-key cryptography. She establishes a connection to someone she hopes is Bob. She asks him for his public key and he sends it to her in plaintext along with an X.509 certificate signed by the root CA. Alice already has the public key ... is talking to Bob? Assume that Bob does not care who he is talking to (e.g., Bob is some kind of public service).
asked Mar 19, 2019 in Computer Networks ajaysoni1924 70 views
0 votes
0 answers
33. Two users can establish a shared secret key using the Diffie-Hellman algorithm, even if they have never met, share no secrets, and have no certificates (a) Explain how this algorithm is susceptible to a man-in-the-middle attack. (b) How would this susceptibility change if n or g were secret?
asked Mar 19, 2019 in Computer Networks ajaysoni1924 94 views