Please use IE (from MS) to view this, the formatting works much better than Netscape. I have no idea how to fix it for netscape and do not have the time.

RSA - Why does it work?

This document is incomplete and in preliminary condition.
Proof by Partha Dasgupta, based on a proof by Zvi M. Kedem

p, q are distinct primes

N = p·q

Find a, b such that a·b = 1 mod (p-1)(q-1)

Encryption Key: e = (b, n) Decryption Key: d = (a, n)

Encryption of message m: E_e(m) = m^b mod n = C (cipher)

Decryption of C : D_d(C) = y^a mod n = m

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

(m^b)^a = m mod n - [1]

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, 2p, 3p,…. (q-1)p q-1

q, 2q, 3q,…. (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 (if ab is less than n, else we have to do the following)

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₁, b₂, … , b_f(n)}

For any a e Z*_n,
Let S_a = {a·b₁ mod n, a·b₂ mod n, …, a·b_f(n) mod n}

Claim 2: S_a º Z*

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 b_j (b_i < b_j)

a· b_i = an + g

a· b_j = bn + g

Subtracting, (b_i – b_j)·a = (b-a)·n or x· a = y· n

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_i <m.

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 $ b_k e Z*_n, s.t. ab_k = 1 mod n

Corollary is proven in the prior paragraph.

EndClaim2

Claim3: if a e Z*_n then a^f(n) = 1 mod n

Define c and A such that:

b₁ · b₂ · … · b_f(n) = c mod n

(ab₁ · ab₂ · … · ab_f(n)) = A mod n [Note, A and c are less than n]

Now since ab₁ mod n · ab₂ mod n · … · ab_f(n) = A mod n

By Claim 2, ab₁ mod n, ab₂ mod n,… · ab_f(n) mod n is a permutation of Z*_n

Hence: A = c (plain arithmetic)

Now distributing the sequence differently:

(ab₁ · ab₂ · … · ab_f(n)) = a^f(n)· (b₁ · b₂ · … · b_f(n)) ….. [1]

Let a^f(n) = a mod n

Taking the modulo of both sides of [1] uses rule [PD] below

A = a · c,
Replacing A with c, c = a · c , (plain arithmetic, not modulo).

Hence a = 1.

Thus: a^f(n) = 1 mod n

EndClaim3

Rule [PD] – [needs to be stated better]

For all a, b e Z_n (not Z*_n)

if (ab = c mod n) and (a = x mod n) and (b = y mod n) and (xy = z mod n)

then c = z

Claim4: if a and f(n) are relatively prime then $ b, s.t. ab = 1 mod f(n)

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 = kf(n) + 1 (regular arithmetic)

EndClaim4

Proof of RSA (for all messages in Z*_n)

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^{kf(n) + 1} = m^kf(n) m = m^f(n) m^{f(n) … …} m^f(n) m

Take the modulo of the last term and since m^f(n) = 1 mod n, then result is m.

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

To fix this problem: There is a proof that all numbers in have the above property, but that proof is rather complex.

EndProof

How to really find a, b?

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

Find a, relatively prime to 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 n and a as input and get x and y [note: GCD(a,n) = 1]

· We know a·b = α·n + 1

Or – α·n + a·b = 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² = 1 mod p .
has only 2 solutions, 1 and p–1 (or –1 mod p)

Lets say the equation has 2 solutions, S₁ and S₂ .

Thus S₁² = 1 + kp

Hence (S₁+1) · (S₁-1) = kp

This means either (S₁+1) or (S₁-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) is divisible, then
S₁ = 1 mod p.
If (S₁-1) is divisible by p then
S₁ = - 1 mod p (or S₁₊₁ = p-1 mod p)

Thus the two solutions have to be 1 and –1. (same happens for S₂)

EndClaim

PRIME NUMBER HUNT

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-1 is 1 (mod p). Secondly, we know that if for some x (where x is not 1 or p-1), if x² is 1 or p-1 (mod p) then p is not prime.

Now we compute a^p-1 fast. Since the computing involves squaring numbers, we can do the x² test also.

Computing a^x can be done as follows. Put 1 in a result variable. Take the binary representation of x. Then for every bit in the binary representation, working from left to right (MSB to LSB), for every 0 square the result variable. For every 1, square the result variable and multiply with a.

b[k] b[k-1] … b[1] b[0] is the binary representation of p – 1

result = 1 // start with the value of a⁰

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 (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

}

if result = 1 then n is “possibly prime” // good

else p is not prime // bad

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.