RSA Protocol/Generating Primes

So, Alice wants to use the RSA protocol and pays Cindy to generate the two (odd) primes p and w so she can use e=65537 and n=pw as her public key. Alice will then, upon receipt of p and w, privately, find d to use as her private key.

Cindy delivers p and w to Alice where p is prime, but she messes up and delivers a number w to Alice which is composite. This number w is the product of two (distinct) primes. (Assume (p,w)=1.) Alice doesn't realize that w is prime and under this assumption finds d. Therefore publishes her public key (65537,pw).

Amazingly, whenever a message M is sent to Alice using RSA using her public key and Alice uses her d, she always recovers the message M correctly! (Of course we assume that M and pw have no common factors).

How in the world is this possible?? What is the formula??

How do we prove that there is no such w that is 512 bits in size??

Edit: Also, how can we prove that two primes dividing w cannot have the same number of bits (in binary representation)?

• As long as Alice computes $d = e^{-1} \text{ mod } \lambda(n)$ correctly the congruence $m \equiv m^{ed} \text{ mod } n$ will hold. – puzzlepalace Oct 3 '17 at 18:35
• Will this solution work independent of the values of P and of M? @puzzlepalace – Denis Jones Oct 3 '17 at 18:42
• I think that the question should state "Alice doesn't realize that $w$ is NOT prime" @puzzlepalace: je dirais même plus, as long as Alice computes a $d$ such that $d\equiv e^{−1}\pmod {λ(n)}$, ${(m^e)}^d\bmod n$ will match $m$ if $0\le m<n$. But, to compute such $d$, it seems that Alice must factor $w$ to compute $λ(n)$. I do not read the problem statement in this way. Perhaps the solution of this enigma does not lie in the Carmichael function? – fgrieu Oct 3 '17 at 19:00
• @Denis Jones: when the question says "whenever a message M is sent to Alice", is that A) in the mathematical sense: for all $M$ in range $[0,N)$ or B) in the cryptographic sense: with overwhelmingly high odds for random $M$ in range $[0,N)$ or C) not clear? Also, when it is written "Assume (p,w)=1" is that a notation for $\gcd(p,w)=1$ ? – fgrieu Oct 3 '17 at 19:19
• There could be infinitely many formulas for w. – Denis Jones Oct 3 '17 at 19:19

1 Answer

How in the world is this possible?

The easiest way this can happen is if $w$ is a Carmichael number (and relatively prime to $p$).

A Carmichael number is a composite number such that $x^{w-1} \equiv 1 \bmod w$ for all $x$ relatively prime to $w$.

If you take a Carmichael number, and just insert it into the RSA machinery; that is, compute $d = e^{-1} \bmod \text{lcm}(p-1, w-1)$ (or $(p-1)(z-1)$, both works in this case), you'll get an encryption/decryption pair that works.

To make things even more interesting, there are also numbers for which $x^{w-1} \equiv 1 \pmod m$ is often (but not always) true (I personally call them quasicarmichael numbers; that might not be standard terminology); then, depending on what $p$ is (actually, it's the factorization of $p-1$ which is critical), and possibly whether you use $\text{lcm}(p-1, w-1)$ or $(p-1)(z-1)$, can also work.

(Of course we assume that M and pw have no common factors).

Actually, we don't need to make that assumption.

How do we prove that there is no such w that is 512 bits in size??

Actually, I believe that there are Carmichael numbers of that size.

• @poncho: what's you favorite quasicarmichael number? Any relation to A257750? You likely mean $x^{w-1} \equiv 1 \pmod w$ where there is $x^{w-1} \equiv 1 \pmod m$ . – fgrieu Oct 3 '17 at 20:33
• @fgrieu: actually, they appear to be separate concepts; it looks like I'll have to find another name for what I mean ("semicarmichael???") – poncho Oct 3 '17 at 20:42
• @poncho Also, how can we prove that two primes dividing w cannot have the same number of bits (in binary representation)? – Denis Jones Oct 4 '17 at 2:36
• @DenisJones: you mean as a zero knowledge proof? You could certainly come up with one, however it is likely not to be simple. – poncho Oct 4 '17 at 3:01
• I will try and do it, thanks for all your help @poncho – Denis Jones Oct 4 '17 at 3:23