Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: OT: Public key cryptography [22+ min]
Replies: 2   Last Post: Feb 29, 2012 4:21 PM

 Messages: [ Previous | Next ]
 Graham Cooper Posts: 4,495 Registered: 5/20/10
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

Date Subject Author
2/29/12 Sam Wormley
2/29/12 PD
2/29/12 Graham Cooper