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