Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Graham Cooper

Posts: 4,253
Registered: 5/20/10
Re: OT: Public key cryptography [22+ min]
Posted: Feb 29, 2012 4:21 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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




Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.