# pfranusic/why-RSA-works

### Subversion checkout URL

You can clone with
or
.
 9e6d37e Added actual files to repo. pfranusic authored Jun 25, 2012 1 %%%% why-RSA-works/conclusions.tex 2 %%%% Copyright 2012 Peter Franusic. 3 %%%% All rights reserved. 4 %%%% 5 6 So why does RSA work? 7 Why is it that we can take some message $m$, 8 run it through two modex operations, and come out with the same $m$? 9 There are several reasons. 10 First of all, RSA computations are done in a commutative ring 11 and the multiplicative association property holds in commutative rings. 12 This property tells us that 13 the two exponentiations $(m^e)^d$ are the same as the one exponentiation $m^{ed}$. 14 15 A second reason is that exponents $e$ and $d$ are chosen 16 such that they satisfy the multiples-plus-one condition $ed = k\lambda + 1$. 17 This insures that $ed$ is one of the identity columns 18 in the exponential table of ring $\mathcal{R}_n$. 19 20 A third reason is that the exponential table contains 21 repeating blocks of columns where $m^a=m^{k\lambda+a}$. 22 This is the wallpaper pattern that we saw in Table \ref{modex-33}. 23 This pattern is the reason for the multiples-plus-one condition. 24 25 Finally, RSA works because it relies on the intractability of the factoring problem. 26 A huge RSA modulus $n$ cannot be factored expeditiously. 27 Given that $n$ is the product of two distinct huge random primes, 28 it is virtually impossible to factor $n$ in any reasonable amount of time, 29 even if the factoring effort is distributed across thousands of computers. 30