This document is incomplete and in preliminary condition.

Proof by Partha Dasgupta,
based on a proof by Zvi M. Kedem

Outline of RSA algorithm:

*p*, *q* are distinct primes

N = *p*·q

Define: F = (p-1)(q-1)

Find *a*, *b* such that they are relatively prime
to F
and *a*·*b*
= 1 mod F

- e.g. a = 65537 = 2^16+1

Encryption of message m:
E_{e}(*m*) = *m*^{b}
mod *n* = C (cipher)

Decryption of
C : D_{d}(C) = *y*^{a}
mod *n* = *m*

Encryption Key: *e* = (*b*, *n*)

Decryption Key: *d* = (*a*, *n*) [Note, *e* and *d* are
interchangeable]

So in order for
RSA to work we must have the property :

(*m ^{b}*)

In this document (7 pages, large font text), we will

· Prove [1]

·
Show how to find *p, q, a* and *b*.

·
Show how to compute *m*^{b}
fast

Preliminaries:

**Z**_{n} = {0, 1, 2,
n-1}

**Z***_{n} = {*x* <*n*-1 | *x*
and *n* are relatively prime}

*f(n)* = number of elements of **Z**_{n}
that are relatively prime to n.

Hence *f(n)*
= | **Z***_{n}|

*How to find **f(n)?*

All those number that are not multiples of p or q are in f(n).
If we count all the multiples of *p* and *q*.

0, 1

*p*, 2*p*, 3*p*,
.
(*q*-1)*p* *q*-1

*q*, 2*q*, 3*q*,
.
(*p*-1)*q* *p*-1

hence

*f**(n) = pq* 1 (*q* 1) (*p* 1) = *pq* *p* ** *q*
+1 = (*p* 1)(*q* 1)

Example: *p*=3,
*q*=5 *n*=15.

Now *f(n)*
= 2*4 = 8 = {1, 2, 4, 7, 8, 11, 13, 14}

__Claim 1__: Z*_{n }is closed under
multiplication mod *n*.

If *a,b* e Z*_{n}
then *ab* and *n* are relatively prime i.e.
*ab* shares no primes with n. By definition of
Z*_{n} a, b do not share primes with n. Their product, *ab*, gets its primes from *a *and *b* and
therefore does not share primes with *n*.

The product can be written as *ab**
= **an
+ **g.*
We just need to show that g is in Z*_{n} . But if it is not, then it shares
primes with *n* and the right hand side is divisible by some prime that is
a factor of *n*. But then, so is the left side, which is impossible as we
showed that it is relatively prime with *n*.

__EndClaim1__

__Definition:__

** Z***_{n }= {*b _{1},
b_{2},
, b*

For any *a* e **Z***_{n},

Let S_{a} = {*a**·b _{1}*
mod n

**Claim 2: S _{a} **

*First*, by Claim 1,
all elements of S_{a} are in **Z***_{n}

*Second*, no two
elements can be the same. Suppose they were, then for some *b _{i}*
and

*a**· b _{i}*
=

*a**· b _{j}*

Subtracting, (*b _{i} b_{j}*)

*x**· a *and* y**· n* are the same
product of primes. Since *a* and *n* do not share any common primes.
All primes that form n has to appear in *x*.

Hence *x>= n*. That is a contradiction, as *b _{j}*

Since all elements of S_{a} are distinct, and in **Z***_{n},
then S_{a} and **Z***_{n }are identical.

Note that since all elements of **Z***_{n} are
produced when *a* is multiplied by each element of **Z***_{n},
then the element 1 is also a result of such a multiplication. Hence we get the
following: [Note: Not useful at this point]

**Corollary: if a ****e Z* _{n} then **

Corollary is proven in the prior paragraph.

__Claim3__: if a **e Z* _{n}
then a**

Define c and A such that:

*b _{1} *

*(ab _{1} *

Now since *ab*_{1}
mod *n* ·
*ab*_{2} mod *n* ·
· *ab** _{f(n)}* =

By Claim 2, *ab*_{1}
mod *n*, *ab*_{2} mod *n*,
· *ab*_{f(n}_{)}
mod *n* is a permutation of **Z***_{n}

Hence: *A*
= *c* (plain arithmetic, both are
less than *n*)

Now we take the following equation:

*(ab _{1}
*

Now take the modulus of both sides:

* A
= (a*^{f(n)}*·* *c
*mod* n)*,

Since c is less than n, *a*^{f(n}^{)}
mod n must be 1*.*

Thus: *a** ^{f(n)}* = 1 mod

** Claim4**: if

If *a* and *f(n)* are relatively
prime, then *a* e **Z***_{ }_{f(n)}_{ }and
from Corollary of Claim 2 we know that *b* exists (and is a member of **Z***_{
}_{f(n)}).

Thus there exists *a* and *b*, both relatively
prime to *f(n),*
such that:

*a**·b = k**f(n) +*
1 (regular arithmetic)

Take a message *m < n* and choose *a*
relatively prime to f(n)
and find *b* such that *a**· b*=1 mod f(n).

Now compute *(m ^{a})^{b}*
using modulo n arithmetic:

*(m ^{a})^{b} = m^{k}*

Take the modulo of the last term and since *m** ^{f(n) } =* 1 mod

Hence *(m ^{a})^{b}
= m mod n*

*Deficiency of this proof*: The proof is for all
messages in Z*_{n}

If n=512 bit number, then the chance of a number being in Z_{n}
but not in Z*_{n} is about 10^{25}. That is negligible J

__How to really find a, b?__

We know that given *a, b* exists, but how to find them?

Find *a*, relatively prime to *f(n)*
(3, 5, 7 etc start with a small odd number and work your way up). Note that *f(n)*
is even.

Then find *b* using extended Euclidean algorithm as
follows

*Extended Euclidean Algorithm:*

Given *p* and *q, p>q* the algorithm finds *x* and *y*,
such that

* x*·*p + y*·*q =* GCD(*p, q*)

[note: regular arithmetic, *x* or *y* is negative]

So we use it as follows:

·
We provide *f(n)* and *a* as
input (*p* and *q*) and get *x* and *y* [note: GCD(*a,n*) = 1] that is we get the values of x and y,
such that

*a*y + **f(n)*x = 1.*

·
*Also note that a*·*b = 1 mod **f(n)*
, that is

*a*·*b
= η*·*f(n)+1
or a*·*b - η*·*f(n) *= 1

So *b
= y*

Hence in modulo arithmetic,

·
*b = y*, if *y* is positive and

·
*b = **f(n) y*, if *y* is negative

**Now we need to find p, q and hence N**.

*p* and *q* are large prime numbers. So the
problem is to find large prime numbers. There is no good deterministic way of
doing this. However we can do it with probabilistic algorithms.

**Fact:** There are lots of large prime numbers. The
number of prime numbers below *N* is about *N/(ln
n)* and hence for a random 2048 bit number, the probability of it being
prime is about 0.0007(one in 1500).

**Claim 5: If p is prime, for any a < p, a^{p-}^{1} = 1 mod p**

Since p is prime, a e Z*_{ p }and f(p) =
p 1

Thus a^{p-1} = a^{f(p) }=
1 mod p

__EndClaim__

**Claim
6: If p is prime, the equation x^{2} = 1 mod p .
**

has only 2 solutions, 1 and p1 (or 1 mod p)

Lets say the equation has 2 solutions, *S*_{1 }and
*S*_{2} .

Thus *S*_{1}^{2}_{
}= 1 + *kp*

Hence (*S*_{1}+1)
·
(*S*_{1}-1) = *kp*

This means either (*S*_{1}+1) or (*S*_{1}-1)
or both is divisible by *p*.

Suppose both are divisible by *p*. But these two
numbers are only 2 apart and unless if *p*=2 this is not possible.

Thus only one of them is divisible by *p*. If (*S*_{1}+1)
is divisible, then

*S*_{1}
= 1 mod *p*.

If (*S*_{1}-1) is divisible by *p* then

*S*_{1}
= - 1 mod *p* (or *S*_{1+1}
= *p*-1 mod *p*)

Thus the two solutions have to be 1 and 1. (same happens for *S*_{2})

Choose a number *p*, randomly. This number, if large
has a chance of being prime in the order of 1 in several thousand (*good*!).

Then choose a number *a < p*, randomly. We will use *a*
to test the primality of *p*. First, we know
that if *p* is prime, *a ^{p-}*

Now we compute *a ^{p-}*

Computing *a ^{x}* can be done as follows. Put 1
in a result variable. Take the binary representation of

b[k]
b[k-1]
b[1] b[0] is the binary representation of x

result
= 1 // start with the value of a^{0}

for i = k downto
0 { //from
MSB to LSB

temp = result; // store
prev result for checking

result = (result * result) mod n //square prev result

//if we are
doing primality testing then add this step

if
(result = 1) and (temp!=1) and (temp!=n-1)

then p is not prime; //by Claim 6

break;

if b[i] = 1 then result =
(result*a) mod n //mult
by a

}

//
now we know n is possibly prime

If the above test says *possibly prime* then the
number *p* is not prime with probability 0.5. Hence if we run the test R
times, then *p* is not prime, with probability (0.5)^{R}. If R = 100
and for all the 100 tests the result was *possibly prime*, then the
chance of the number being not prime is a one in a million.

So we select 1 large number. Test for primality
about 500 times. In about a 2000 choices, we will find a prime number. Do it
again for another prime number. Now call them *p* and *q*. All this
should take about 1-2 seconds. Definitely under 10 secs.

And the rest, as they say is trivial J

Note that encryption and decryption uses the same fast exponenting algorithm as shown above.