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

Improve this question
$\endgroup$
6
  • 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, 2017 at 18:35
  • $\begingroup$ Will this solution work independent of the values of P and of M? @puzzlepalace $\endgroup$
    – Denis Jones
    Oct 3, 2017 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, 2017 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, 2017 at 19:19
  • $\begingroup$ There could be infinitely many formulas for w. $\endgroup$
    – Denis Jones
    Oct 3, 2017 at 19:19

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
7
  • $\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, 2017 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, 2017 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, 2017 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, 2017 at 3:01
  • $\begingroup$ I will try and do it, thanks for all your help @poncho $\endgroup$
    – Denis Jones
    Oct 4, 2017 at 3:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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