0
$\begingroup$

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)?

$\endgroup$
  • 2
    $\begingroup$ As long as Alice computes $d = e^{-1} \text{ mod } \lambda(n)$ correctly the congruence $m \equiv m^{ed} \text{ mod } n$ will hold. $\endgroup$ – puzzlepalace Oct 3 '17 at 18:35
  • $\begingroup$ Will this solution work independent of the values of P and of M? @puzzlepalace $\endgroup$ – Denis Jones Oct 3 '17 at 18:42
  • $\begingroup$ 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? $\endgroup$ – fgrieu Oct 3 '17 at 19:00
  • $\begingroup$ @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$ ? $\endgroup$ – fgrieu Oct 3 '17 at 19:19
  • $\begingroup$ There could be infinitely many formulas for w. $\endgroup$ – Denis Jones Oct 3 '17 at 19:19
3
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.