RSA: Do I need to use a big int package for this?

This is a discussion on RSA: Do I need to use a big int package for this? within the C Programming forums, part of the General Programming Boards category; Hello I am teaching myself encryption using C. At the moment I'm implementing RSA. I'm only using prime numbers smaller ...

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    18

    RSA: Do I need to use a big int package for this?

    Hello

    I am teaching myself encryption using C.

    At the moment I'm implementing RSA. I'm only using prime numbers smaller than 1000.

    When it comes to encrypting, and especially decrypting, I'm getting some pretty massive numbers.

    For example:

    If I encrypt the number 6 using the key pair (79, 1121):

    (6 ^ 79) mod 1121 = 693

    I then decrypt using the key pair (859, 1121):

    (693 ^ 859) mod 1121... Error. My compiler doesn't like 693 ^ 859. The number is too big.

    Is there a smart way around this, or do I need to install a big int package?

    Note I am already using long doubles.

    Any help greatly appreciated.

    Thank you.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    There's a smart way around this, to wit: reduce often. More precisely, if you are doing anything other than squaring-mod and multiplying-mod, you're not doing it right. Even more precisely, successive squaring gives 693^2, 693^4, 693^8, 693^16, 693^32, etc., reduced of course. Writing the exponent in binary (or using the computer's internal representation of the exponent as same) will allow you to multiply the appropriate squares together to get 693^859.

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    Holy cow, I hope you're not actually fully calculating 693 ^ 859 and then modding by 1121. You need to be implementing modular exponentiation. I could explain it for you here, but I think its probably best to let Google and Wikipedia do their jobs.

    http://en.wikipedia.org/wiki/Modular_exponentiation

    The "efficient right-to-left algorithm" is the version I most often see implemented as its very short and straightforward.

  4. #4
    Registered User
    Join Date
    Mar 2008
    Posts
    18
    Thank you both for your replies.

    I'm new to C and cryptorgraphy, so you have both been a great help.

    Thanks!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how to combine these working parts??
    By transgalactic2 in forum C Programming
    Replies: 0
    Last Post: 02-01-2009, 08:19 AM
  2. Code review
    By Elysia in forum C++ Programming
    Replies: 71
    Last Post: 05-13-2008, 10:42 PM
  3. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 03:39 PM
  4. newbie needs help with code
    By compudude86 in forum C Programming
    Replies: 6
    Last Post: 07-23-2006, 09:54 PM
  5. Quack! It doesn't work! >.<
    By *Michelle* in forum C++ Programming
    Replies: 8
    Last Post: 03-02-2003, 12:26 AM

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