[contravariant]

Wouldn't RSA just fail if you used a non-prime factor? You shouldn't be able to decrypt any messages if you calculate the totient incorrectly, and for a public key pq, if either p or q isn't prime then (p-1)(q-1) won't be the totient.

[strags]

I've always wondered about this.

Wikipedia says ( http://en.wikipedia.org/wiki/RSA_(cryptosystem) ): "When m is not relatively prime to n, the argument just given is invalid. This is highly improbable (only a proportion of 1/p + 1/q − 1/(pq) numbers have this property), but even in this case the desired congruence is still true. Either m ≡ 0 (mod p) or m ≡ 0 (mod q), and these cases can be treated using the previous proof.".

I'm not sure I follow 100% - perhaps someone smarter can explain.

[contravariant]

I think that's a different problem, although it is not entirely irrelevant since having a small prime factor like 3 implies that that the method will fail in at least 1/3 of the cases.

The other problem is that the value φ(n) will be wrong, even then there are some rare cases where the method might still work (see eximius comment about carmicheal numbers) but those are exceedingly rare.

[eximius]

http://en.m.wikipedia.org/wiki/Carmichael_number

[contravariant]

I suppose that would work, although with a factor of 3 more than 1/3 of all inputs are not relatively prime so in those cases it would fail anyway.