So far as we know. It scares some people that maybe co-primes working might be a sign of some future attack. Nobody has been able to figure out how such an attack works, but considering RSA is defined for primes, that some non-prime numbers also work is scary.
> Nobody has been able to figure out how such an attack works, but considering RSA is defined for primes, that some non-prime numbers also work is scary.
What do you mean by some non-prime numbers working? Do you mean that instead of picking two primes, p and q, and then e and d such that ed = 1 mod ϕ(pq) one can sometimes pick a prime p and composite q or even composite p and composite q, compute e and d such that ed = 1 mod ϕ(pq), and still get a working RSA system?
If so, that shouldn't actually be scary. Consider a composite positive integer N. The positive integers that are less than N and relatively prime to it form a finite group under multiplication mod N with ϕ(N) elements. For each element a in that group, a^ϕ(N) = 1 mod N. We can raise that to any positive integer power k giving a^(k ϕ(N)) = 1 mod N. Multiply by a giving a^(k ϕ(N) + 1) = a mod N.
If we pick e and d such that ed = k ϕ(N) + 1 for some k, then we will have (a^e)^d = a mod N for all a in the group, i.e., for all a in [1, N) that are relatively prime to N.
That almost gives us RSA E(m) = m^e mod N for encryption and D(m) = m^d mod N for encryption. Given our initial N, e and d are easy to compute because ed = k ϕ(N) + 1 for some k is true for any e, d where ed = 1 mod ϕ(N). So as long as we pick N so that we can easily compute ϕ(N) but someone just given N and e cannot, we are all set--except for one thing.
That one thing is that the above reasoning only shows that it works when m is relatively prime to N. We would like it to work for all messages in [1, N), not just the ones relatively prime to N.
If we pick N = p q where p and q are primes then the messages m that we have to worry about are: p, 2p, ..., (q-1)p and q, 2q, ..., (p-1)q. All the other possible messages will be relatively prime to pq and so are covered by the earlier arguments.
Because (ab)^e = a^e b^e, if our system works for a and b, it will work for ab, so we only need to show it works for p and that will also cover 2p, 3p, ..., (q-1)p, and similarly for q.
To show it works for p, we can consider powers of p mod q. In particular p and q are relatively prime, and p^ϕ(q) = 1 mod q.
Recall that N=pq. ϕ is multiplicative, and so ϕ(q) divides ϕ(N), and so p^ϕ(N) = 1 mod q, or p^(ϕ(N)+1) = p mod q. Note that also p^(ϕ(N)+1) = p mod p (because both sides are 0 mod p). And since p and q are relatively prime, p^(ϕ(N)+1) = p mod pq, or p^(ϕ(N)+1) = p mod N. So our almost RSA does work for p. Similar argument shows it works for N, and or almost RSA turns out to be actual RSA.
What if we try it where N is a product of 3 distinct primes instead of 2? The messages that are not relatively prime to N then will fall into 6 classes: messages where gcd(m,N) = one of the prime factors of N, and messages were gcd(m,N) = the product of two of the prime factors of N.
The above argument to show that a message equal to p is fine when N=pq extends fairly straightforwardly to show that those 6 classes of non-relatively prime messages an N that is a product of 3 distinct primes works.
So as long as your composite N is square free it should be suitable for an RSA system.
