Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Re: OT: Public key cryptography [22+ min]
Posted:
Feb 29, 2012 4:21 PM


On Mar 1, 7:06 am, PD <thedraperfam...@gmail.com> wrote: > On 2/29/2012 2:58 PM, Sam Wormley wrote: > > > Public key cryptography (22+ minute video) > >http://www.sciencedump.com/content/publickeycryptography > > > DiffieHellman key exchange explained with color mixing! > > Brilliant!
I worked out an example a few years ago.
In the RSA cryptosystem, two integers e and n are given as public keys. If a message m is converted to an integer less than n, then m may be encryped according to the formula
c = m^e mod n
The intended receiver has a private key that consists of two prime factors, p and q, of n. In other words, n = pq. This means that the receiver of the message can easily find an integer d such that
ed = 1 mod t(n) where t(n) = (p1)(q1). To decipher message c, the receiver computes c^d mod n. This number can be analyzed as follows: c^d mod n = m^(ed) mod n = m^(kQ(n)+1) mod n for some integer k = m.m^(kQ(n)) mod n = m mod n since m^(Q(n)) = 1 mod n = m
****EXAMPLE****
The message has to be smaller than the primes, so our message is 2, or 'B', say I want to buy on your secret stock website.
m=2 e=7 (any medium odd number I think) n=pq = 3 * 5 = 15
encryption = c = m^e mod n = 2^7 mod 15 = 128 mod 15 = 8 (15 is a factor of 120)
so you send me e=7, and n=15 I send you 8.
ed = 1 mod (p1)(q1) ed = 1 mod (2 * 4) ed = 1 mod 8 ed = 1, 9, 17, 25, 33, 41, 49... 7d = 49 d = 7 c^d mod n = 8^7 mod 15 = 2 (just use calculator) = m
So you decode 8 into 2, because you know e=7, p=3 and q=5
Herc  http://Matheology.com



