RSA: numbers not relatively prime to the modulus

Taking an example of RSA with numbers small enough to reason with:

  • primes p1=11, p2=13,
  • modulus = p1 x p2 = 143
  • phi = (p1-1) x (p2-1) = 120
  • e = 7 // chosen to be relatively prime to phi
  • d = 103 // derived from e and phi by extended Euclidian algorithm
  • e x d = 721 = phi x 6 + 1.

Is that right so far?

As it happens, for any i from zero to 142, taking i to the power of 721 mod 143 gives you i back. That's a good thing, because decryption wouldn't work otherwise.

For a number that's relatively prime to the modulus, that's explainable by Euler's theorem - x to the power of phi is 1, and taking those powers out of the equation leaves you with x by itself.

For a number like 26 that has a common factor with the modulus, the encryption/decryption happens to work in this example - 26 to the power of 721 is 26 mod 143. But it's not explainable by the Euler technique, since 26 to the power of phi isn't 1, it's 78.

So why does this work? Should it work? Does RSA require it to work?

EDIT:

To summarize the proof cited in Job's answer:

  • Forget about Euler's theorem - it looks promising but it's a dead end in this case.
  • We use Fermat's little theorem.
  • We also need to use the fact that if two numbers are congruent mod both p1 and p2, then they're congruent mod (p1 x p2). Let's call that FACT X.
  • Break down ed again: ed = 1 mod phi, so ed-1 = k(p1-1)(p2-1) for some k. In the case above, ed-1 = 6(11-1)(13-1). The (p1-1) and (p2-1) parts of the equation will be eaten by Fermat's theorem.
  • $$m^{ed} = m^{ed-1}m = m^{k(p1-1)(p2-1)}m$$
  • If m == 0 mod p1, then Fermat doesn't apply. But m to the power of ed is also == 0 mod p1. Example: 22 == 0 mod 11. 22^721 == 0 mod 11.
  • If m <> 0 mod p1, then Fermat does apply (we're working in mod p1 here):
    $$m^{ed} = m^{k(p1-1)(p2-1)}m = (m^{(p1-1)})^{k(p2-1)}m = 1^{k(p2-1)}m = m $$
  • The two cases above give us the result that m to the power of ed is congruent to m mod p1.
  • Apply the same reasoning for p2.
  • Then use FACT X above to show that m to the power of ed is congruent to m mod (p1 x p2).

Back to the example:

$$ m^{ed} = m.m^{ed-1} = m.m^{720} = m.m^{6.10.12} = m.(m^{10})^{72} = m.(m^{12})^{60} $$

So if m is relatively prime to 11, then Fermat shows that taking m to the power of ed mod 11 is like multiplying by 1. If m isn't relatively prime to 11, then you're multiplying zeros mod 11 and end up with zero.

Similarly for mod 13.

And then FACT X combines the two and shows that taking m to the power of ed leaves the message unchanged mod 11 x 13.

asked 09 May '12, 20:41

ddd's gravatar image

ddd
3278

accept rate: 50%

edited 09 May '12, 23:29

Great , Anything you wrote is correct, inclusive the order of steps. You proved the extended Fermat Theorem $% m^{ed}=m\ (mod\ \varphi(pq))$% for all $%m\in Z$%. Very nice and short too.

(10 May '12, 03:14)

Wolfgang

Wolfgang's gravatar image

3 Answers:

It still works even if the message is not relatively prime to the modulus. Wikipedia offers two proofs - http://en.wikipedia.org/wiki/RSA_(algorithm)#Proofs_of_correctness

link

answered 09 May '12, 21:54

Job%20Evers's gravatar image

Job Evers ♦♦
7.9k21248

A follow-up question for anyone who's been patient enough to read my wall of text above...

If I'm understanding this correctly:

  • RSA is all about Fermat's theorem plus that lemma about products of moduli.
  • Euler's theorem and the calculation of phi is an implementation detail.

e x d doesn't need to be == 1 mod phi. It suffices that it be == 1 mod (p1-1) and mod (p2-1).

In the example above, I can take encryption exponent 7 and decryption exponent 43. 7 x 43 = 301. 301 == 1 mod 10 and mod 12, but it's not == 1 mod phi.

For all i from 0 to 142, you can encrypt by taking the 7th power and decrypt by taking the 43rd power. That seems to me to be a correct cipher.

So the question is:

  • Is the calculation of phi just a reliable algorithm for finding an (e,d) pair whose product is == 1 mod (p1-1) and mod (p2-1).
  • Or is there a security reason why ed has to be == 1 mod phi?

link

answered 10 May '12, 00:24

ddd's gravatar image

ddd
3278

@D__

Ask yourself the following question from group-theory:

Given a finite abelian group $%G$%. For each element $%g\in G$%, the equation $g^r=e$ holds ($%e:=$% neutral element in $%G$%). What properties must $%r$% have ?

EXAMPLE:

[1] $%G:=(Z/2Z \times Z/2Z \times Z/2Z,\ +) $% has 8 elemens. For each $%x\in G$% it holds $%x^2=e$%, hence here is $%r=2$%.

[2] $%G:=(Z/aZ \times Z/bZ,\ +) $% has $%a\cdot b$% elemens. For each $%x\in G$% it holds $%x^{a\cdot b}=e$%, hence $%r\leq ab$% (more precisely $%k\cdot r=a\cdot b$%). BUT if $%a=b$% then $%r=a$% and IF $%a,b\ both\ prime,\ different$% then $%r=a\cdot b$%.

As you can see, the answer depends on the structure of $%G$%. I assume $%r=lcm(a,b)$% in general. If you REALLY want to know, you have to study group- theory.

In our RSA-situation: Only a person who knows $%p,q$% and hence knows $%\varphi(pq)$% can tell you what $%r$%-value is enough. The answer depends on the structure of the multiplicative group $%((Z/\varphi(n))^{\times},\ast)$% . If you know $%r$%, you are able to answer the question for $%e,\ d$%.

This sounds all a bit complex, but it is not since all possible structures of $%((Z/\varphi(n))^{\times},\ast)$% are well known. Each structure defines an $%r$%. Finally you only have to test these finitely many scenarios, hence possibilities for $%r$%. After you know $%r$%, you have to find $%\ e,\ d\ $% with $%\quad ed-1\equiv 1\ mod\ r$%.

(10 May '12, 08:24)

Wolfgang

Wolfgang's gravatar image
1

I think you can figure out the answer to your question by looking here: http://en.wikipedia.org/wiki/Carmichael_function

(10 May '12, 09:30)

Walter

Walter's gravatar image

@Walter

I think you are right. Thanks for the hint. I didn't know about its definition. As a consequence, we also could solve $%\quad e\cdot d\equiv 1\ (mod\ \lambda(n))$%.

And now I see that $%\lambda(n)=\varphi(n)$% if $%n\neq Power\ of\ 2$%, so no big progress.

(10 May '12, 09:35)

Wolfgang

Wolfgang's gravatar image

@Wolfgang : the "power of 2" part is not correct. For instance, let p=11 and q=13. n=pq=143 is not a power of 2, but the totient (120) is not equal to the reduced totient (60).

(10 May '12, 10:31)

Walter

Walter's gravatar image

i refer to your website, not to $%n=pq$%. But you are even right in this case. Thanks for clarification. The website lists all cases where both values are the same.

It seems that the difference of their values is not "too big".

(10 May '12, 11:58)

Wolfgang

Wolfgang's gravatar image

From an implementation point of view, calculating the reduced totient/Carmichael function requires finding the least common multiple of p and q, which I assume involves factoring p-1 and q-1. So that's probably why it's not done in practice.

But from a point of view of proving the correctness of the cipher, it seems to me (correct me if I'm wrong) that the Carmichael function is a more precise definition of what's required of e and d.

Or maybe it's just a matter of least common multiples.

For example, take primes 11 and 13 again, so modulus = 143...

Taking powers of numbers mod 143 gives you subgroups of certain sizes. For example, the powers of 42 are a subgroup of size 15: {42, 48, 14, 16, 100, 53,..., 126, 1}. Not all of the subgroups include 1, for example the powers of 26 are {26, 104, 130, 91, 78}. The biggest subgroups of this kind have size 60, as predicted by the Carmichael function, and all of the subgroup sizes are divisible by 60.

If you look at those sequences mod 11 and mod 13, more structure can be seen. The powers of 42 mod 11 run through the cycle {9,4,3,5,1}, and mod 13, they run through the cycle {3,9,1}, so the period of 15 is the combination of periods of 5 and 3.

So for encryption/decryption to work for 42 (for example) mod_pow(42, ed, 143) needs to be equal to 42. This would work if ed was 16, 31, or in general ed = 15x + 1. For 26, ed needs to be 5y + 1. Applying this to all numbers, ed - 1 needs to be a multiple of all of the subgroup sizes. The least common multiple of the subgroup sizes, which happens to be the Carmichael function, is the smallest possible ed - 1.

(10 May '12, 16:17)

ddd

ddd's gravatar image

@D__

[Literature] $%\quad$% Each $%(e,d)$% with $%\quad e\cdot d\equiv 1\ (mod\ Lcm(p-1,\ q-1))\quad$% would be fine to be used in RSA.

(1) Charmichael function = more precise definition ? --> If you want to use the smallest possible modulus, then Charmichael Numbers are the choice

(2) Since the value of $%\ |\lambda(n)-\varphi(n)|=$%small $%\ $% I think it's not really worth to evaluate $%\lambda(n)$%

(11 May '12, 00:08)

Wolfgang

Wolfgang's gravatar image

@D__ Could you post your follow-up question to the thread Unit 4 Questions that will be used for office hours? I think Prof. Evans should enlighten all of us on this point.

(13 May '12, 08:33)

Leslie B. Klein

Leslie%20B.%20Klein's gravatar image

Job targets the key-point. It's surprising that $%\quad m^{e\cdot d}\equiv m\ (mod\ n)\quad $% with $%\ n\neq prime\ $% holds for ALL $%m\in Z$%. You can use the following ($%p$% and $%q$% connecting) ''theorem'' to remove your problem and to verify Job's statement:

$%\bullet$% Let $%p,q$% be prime and $%p\neq q$%. Then it holds:

$%x\equiv a\ (mod\ p)\quad AND\quad x\equiv a\ (mod\ q)\ \Longleftrightarrow\ x\equiv a\ (mod\ pq)$%

You may also check the (very short) RSA-proof in ''Inroduction to Algorithms'' (Cormen, Lesierson, Rivest). They address exactly your point and they solve the issue nicely.

link

answered 09 May '12, 22:30

Wolfgang's gravatar image

Wolfgang
687310

edited 12 May '12, 05:47

Your answer
Question text:

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags

×9,101
×1,572
×218
×35

Asked: 09 May '12, 20:41

Seen: 2,457 times

Last updated: 13 May '12, 08:36