Hey, I have a couple of questions I'm trying to answer.
Normally, we have a system with distinct primes p, q and N = p*q, with phi = (p-1)(q-1). We choose e such that gcd(e,phi) = 1 and calculate d = e^-1 mod phi.
I have two questions I've been trying to answer:
1) What goes wrong if we choose e such that gcd(e,phi) != 1
and
2) What happens if p,q aren't distinct
I've put my answers below, let me know if you agree:
--
1) If gcd(e,phi) != 1, we have two problems. First, and most obviously, we can't compute d = e^1 mod phi because computing multiplicative inverses using algorithms such as the extended Euclidean algorithm only works if e and phi are coprime. Secondly, if Alice for example wants to send a message to Bob, if Bob chose e incorrectly it becomes possible that two plaintext messages Alice sends can result in the same ciphertext, making encryption ambiguous. For instance, say we have p=5, q=13 so N=65 and phi = (5-1)(13-1) = 48. Say Bob chooses e=3 and publishes his key (N,e) = (65,3). Now, say Alice wants to encode the plaintexts m=2 and m=32. She uses the function E(n,e) = m^e mod N. Then she gets
For 2: 2^3 mod 65 = 8
For 32: 32^3 mod 65 = 8
So two (or more) plaintexts can yield the same ciphertext and the system breaks.
--
2) If Bob chooses p,q such that they are not distinct, then p=q. This has two obvious problems. First off, the system is no longer secure. If some adversary, Eve, wishes to break the system and knows how Bob chooses p=q, then she can do so easily. If Bob chooses p,q such that p and q are primes and p=q, then N=p*q=p*p=p^2, and phi = (p-1)^2. To break the system, all Eve has to do is take sqrt(N) to find both p and q (since p=q). Then she can calculate (p-1)^2 to find phi. Then, since Bob publicly publishes the key (N,e), Eve can calculate d=e^1 mod phi to find Bob's private key. Then, any messages Alice sends to Bob can be decrypted by Eve using Bob's decryption function which is no longer known only by Bob.
Another problem is this breaks the system in that decryption of some messages do not return the original message. Consider p=5, q=5 and N=25, phi=(5-1)^2 = 16. Bob chooses e=3 which is OK since gcd(3,16) = 1. Then Bob publishes the public key (25,3) and calculates his private key d= 3^-1 mod 16 = 11. Now let's say Alice sends the message "2" and encrypts it as:
2^3 mod 25 = 8. So she sends the ciphertext 8 to Bob. Bob then decrypts by calculating 8^11 mod 25 which should return 2, but in fact 8^11 mod 25 = 17 so encryption and decryption do not work as intended in this case.
--
That's about as far as I've gotten. I'm not sure about my logic in some of them, especially in the second question. Let me know if you see anything wrong, I'll gladly donate some fg for help.