Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
Drexel University 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/public-key-cryptography
>
> > Diffie-Hellman 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) = (p-1)(q-1). 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 (p-1)(q-1)
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
|
|
|
|
