MAT246 Lecture 5 (2012-10-10)
RSA coding
Relatively prime: two integers a & b are relatively prime if their only common factor is 1.
Receiver:
Chooses 2 distinct large prime p and q, and lets N=pq
Note that:
Chooses a relatively prime E to
Announces the pair (N,E)
Sender:
Message must be natural number, M, that is less than N
Note that:
Sends the remainder R
Theorem 6.1.1:
let N=pq, where p and q are distinct prime numbers, and let . If k
and a are any natural numbers, then .
Proof:
Known that and , then
Since N=pq, this means that
and
Consider p first, same proof for q.
Case 1: if , then
Case 2: if p does not divide a then, by Fermat’s THM, , thus,
=> that is,
=>
Same proof for q, thus
Decoding:
A natural number D (decoder) satisfies that for some natural number k
=> => that is
By THM 6.1.1, , thus,
Ex1. p=11, q=7, N=77, =60, M=71, encode message.
Step 1: find E
E is relatively prime to
Let E=13
Step 2: find R
M=71 => =>
Since =>
Since => =>
=> => =>
=> => =>
. MAT246 Lecture 5 (2012-10-10)
Since => , that is
=> R=15
Thus the encoded version o

More
Less