RSA Encryption

This is a discussion on RSA Encryption within the Tech Board forums, part of the Community Boards category; This explanation and example of RSA encryption is confusing me. I found this in a pdf on the web. quote: ...

  1. #1
    Funniest man in this seat minesweeper's Avatar
    Join Date
    Mar 2002
    Posts
    801

    RSA Encryption

    This explanation and example of RSA encryption is confusing me. I found this in a pdf on the web.



    quote:
    --------------------------------------------------------------------------------

    Example: RSA
    n, e = public key, n = product of two primes p and q
    d = private key
    Encryption: C = M^e mod n
    Decryption: M = C^d mod n
    p, q = 5, 7
    n = p * q = 35
    e = 5
    d = e^-1 mod ((p-1)(q-1)) = 5

    Message M = 4
    Encryption: C = 4^5 mod 35 = 9
    Decryption: M = 9^5 mod 35
    = 59049 mod 35
    = 4


    --------------------------------------------------------------------------------

    If you aren't aware, M is the original message and C is the encrypted message (ciphertext).


    Now, the calculation,

    d = e^-1 mod ((p-1)(q-1)) = 5

    seems to me to be wrong, unless I’m being a complete muppet. Surely it should be,

    d = e^-1 mod ((p-1)(q-1))
    = (1/5) mod 24
    = 0.2.

    However,

    M != 9^0.2 mod 35, so the algorithm wouldn’t work.

    As illustrated in the example, d = 5 makes the algorithm work. But having the private key identical to the public key (or even the inverse of it for that matter) doesn’t strike me as being particularly secure.

    I found a different explanation of RSA that gave the same theory as this one. Can anyone shed some light on how this algorithm is supposed to work?

    Ta Guys.

  2. #2
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    What site did you get this from?
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  3. #3
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    0.2^-1 == 5.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  4. #4
    Funniest man in this seat minesweeper's Avatar
    Join Date
    Mar 2002
    Posts
    801
    This was the site I got the pdf from. The relative stuff starts on page 21.

    http://www.cryptoengines.com/~peter/part1.pdf

  5. #5
    Comment your source code! Lynux-Penguin's Avatar
    Join Date
    Apr 2002
    Posts
    533
    http://public.csusm.edu/public/FranzL/M372/numth.pdf

    in the chapter about linear congruences (2 i think) there is an example of RSA encryption, the best I have found so far.

    -LC
    Asking the right question is sometimes more important than knowing the answer.
    Please read the FAQ
    C Reference Card (A MUST!)
    Pointers and Memory
    The Essentials
    CString lib

  6. #6
    Registered User Markallen85's Avatar
    Join Date
    Nov 2002
    Posts
    53
    The way that I was shown to do it is using the Euclidean Algorithm to find d.

    try searching for that on google, I remember there are some examples of it around. like this one:

    http://www.math.umn.edu/~garrett/js/gcd.html

    I can't remember exactly what you do with it, I did all this stuff a long time ago, but it's something like running through Euclid's algorithm with Phi(n) and d, then you retrieve the third column of this process and use it to create e. I've got all the code to do it, but I don't have time to figure out exactly how I wrote it.

    I also wrote a javascript RSA app a few years ago. It's not that great, I'm not even sure if it's still functional (I know it regularly corrupts the last few characters) and the source is horrendous (was actually one of the first programs I ever wrote, so it's full of yukky stuff):

    RSApage

    sorry if all that's a load of babble, I just happen to like RSA quite a bit....

    -mark
    "never argue with an idiot, they will drag you down to their level and beat you with experience"

  7. #7
    Xei
    Xei is offline
    Registered User Xei's Avatar
    Join Date
    May 2002
    Posts
    719
    Rijndael is the current standard. You can get it on PDF, and it is quite similar.
    "What are you after - the vague post of the week award?" - Salem
    IPv6 Ready.
    Travel the world, meet interesting people...kill them.
    Trying to fix or change something, only guaruntees and perpetuates its existence.
    I don't know about angels, but it is fear that gives men wings.
    The problem with wanting something is the fear of losing it, or never having it. The thought makes you weak.

    E-Mail Xei

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. RSA Encryption Algorithm help
    By gL_nEwB in forum C++ Programming
    Replies: 2
    Last Post: 04-27-2008, 04:14 AM
  2. Replies: 16
    Last Post: 11-23-2007, 12:48 PM
  3. RSA encryption with 1024 bit keys
    By bennyandthejets in forum C++ Programming
    Replies: 23
    Last Post: 09-18-2005, 08:14 AM
  4. What's wrong with my Stream Cipher Encryption?
    By Davros in forum C++ Programming
    Replies: 3
    Last Post: 04-18-2002, 09:51 PM
  5. File Encryption & Read/Write in Binary Mode
    By kuphryn in forum C++ Programming
    Replies: 5
    Last Post: 11-30-2001, 05:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21