RSA encryption with 1024 bit keys

This is a discussion on RSA encryption with 1024 bit keys within the C++ Programming forums, part of the General Programming Boards category; I've just completed a program which does arithmetic on arbitrarily large integers, and I'd now like to implement RSA encryption ...

  1. #1
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401

    RSA encryption with 1024 bit keys

    I've just completed a program which does arithmetic on arbitrarily large integers, and I'd now like to implement RSA encryption with it. Unfortunately, it seems that I am doing things very inefficiently. I have a binary powering routine, and am trying to calculate a number on the order of:

    50^(2^512) (mod 2^1024)

    The program grinds to a halt almost immediately, because the powers of 50 soon become incredibly large.

    I'm not aware of any techniques for RSA encryption except binary powering, but I'm sure there must be cleverer ways to do it. Does anyone have any advice?
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,588
    Unfortunately, it seems that I am doing things very inefficiently.
    And how might you be doing things currently?

    Have you considered using an existing library such as the GMP?
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    And how might you be doing things currently?
    I have some value 'a' that I want to raise to the power of 'e', then take modulo 'm'. I split a^e into multiple factors, each a binary power of a. Ie: a^7=(a^4)(a^2)(a^1). I calculate each of those factors by squaring the previous factor and taking modulo m. Afterwards I multiply all the appropriate factors together, taking modulo m each step of the way.

    The numbers are all stored as an array of chars, each storing 8 bits. Addition and multiplication are performed just like you would on paper.

    Thanks for the link to the GMP, but the reason I was coding this was to learn how to work with large numbers, not just to encrypt things.
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  4. #4
    Super Moderater.
    Join Date
    Jan 2005
    Posts
    374
    Have you thought about using Chinese remainder theorem to simplify the mammoth computation of finding 50^(2^512) (mod 2^1024).

    With RSA there are a few tricks you can use to simplify the amount of math you have to do.

    Invariably you have to have a system which can handle v. large numbers. You say you have implemented the addition and multiplication part.

    What about the division and modulus part? That may be your next step if you haven't done so already.

    Thanks for the link to the GMP, but the reason I was coding this was to learn how to work with large numbers, not just to encrypt things.
    The GMP handles large numbers. I'm not sure what you mean by the 'encryption' comment?

    Have a looky here for extra ideas, in particular the pdf about rsa and its implementation.

    Encryption Contest

    Btw the hardest part is generating large prime numbers. I'll let you find out about that

  5. #5
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    I can't use the Chinese Remainder Theorem because the whole point is that RSA encryption keys are too large to factor, so I won't know the factors of whatever 'm' is.

    I've implemented a good division and modulus system, but it's not nearly fast enough to compute such large numbers as the ones I need.

    What I meant about the GMP is that I don't want something else to do the work for me; I want to know for myself how to optimize the arithmetic. Encrypting data will just be an added bonus. I'll check out those links, thanks.

    I'm not so concerned about generating large primes. I've read about a few algorithms that can produce large primes with a lot of certainty.
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  6. #6
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    What sort of algorithm are you using for multiplication? Is it O(n^2) or is it O(n log n)?

  7. #7
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    I'm not familiar with that terminology. Could you briefly explain each one, or refer me to an online resource?
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,588
    You could have a look at an article on Arbitrary-Precision Arithmetic. The author's intention is not so much to provide solutions as to provide a problem, but he does list Karatsuba's algorithm as one thing to try, and Fourier transformations as another.

    I'm not familiar with that terminology.
    You could take a look at The Big Oh Notation.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Sep 2005
    Location
    USA
    Posts
    69
    That is a really big number. I think that FAQ says that scientists use fortron to crunch really big numbers. Does this number have to be exact or can you use scientific notation?
    Well, good luck with your problem,
    Adam

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,588
    Does this number have to be exact or can you use scientific notation?
    It has to be exact since he's doing cryptography.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    Sep 2005
    Location
    USA
    Posts
    69
    Oops, sorry, I guess from now on, I'll have to read the whole thread before I reply.
    Adam

  12. #12
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    I've been looking at the source for GMP, but the actual computational code is in assembly, and I'm not very proficient at reading it. Does this sort of thing absolutely have to be done in assembly, or could it be done fast enough in straight c++?
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

  13. #13
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    if you want it as fast as possible, yes, especially using mmx,sse etc.
    You may find this useful
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  14. #14
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Don't bother with assembly; something's wrong with the algorithms you're using. If I can write Ruby code that performs 50 ^ (2 ^ 512) (mod 2^1024) - order calculations almost instantaneously, than using assembly won't help; it will only scale your running time down a little bit.

    I can write
    Code:
    def powmod(b,x,m)
      if (x == 0)
        return 1
      end
    
      tmp = powmod(b, x / 2, m)
    
      if (x % 2 == 1)
        return (((tmp * tmp) % m) * b) % m
      else
        return (tmp * tmp) % m
      end
    end
    This Ruby function computed powmod(123, 2 ** 512 + 12344535, 2 ** 2048 + 1234) and produced
    Code:
    22813624981075065545135850558173269231510448307866093786909898690881909635625
    28026233653165635689972639687049986456799967595172328506910777276889008060872302
    35464631832286336920331501492018763317107266447462587900392315073114991959333059
    51421717310407289760318099206126989926255863894581434267272318153188897013984781
    84378062834515623677409012707914256130537336028576225644897284752852800312488149
    65148676160157595427552224160566504933248486744939428838549003370569396501573929
    63204417521093027295195029595437349786705582067498498129131203940551923664015160
    678987418146095882019961441850108090812140059913087917725917
    in less than a second. It's your algorithm that's the problem, and jumping into assembly language would not help.

  15. #15
    mustang benny bennyandthejets's Avatar
    Join Date
    Jul 2002
    Posts
    1,401
    if you want it as fast as possible
    Nup, I just want something reasonable. I would like to be able to perform operations that large at something like 15 per second.

    something's wrong with the algorithms you're using
    I'm sure that's the case. I don't understand how your code works though. Does this "Ruby" thing have built in support for arbitrarily large numbers? My whole aim was to implement that functionality myself, in C++. How should I do that?
    benforbes@optusnet.com.au
    Microsoft Visual Studio .NET 2003 Enterprise Architect
    Windows XP Pro

    Code Tags
    Programming FAQ
    Tutorials

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Copy bit to bit
    By Coder2Die4 in forum C Programming
    Replies: 15
    Last Post: 06-26-2003, 09:58 AM
  2. binary numbers
    By watshamacalit in forum C Programming
    Replies: 4
    Last Post: 01-14-2003, 10:06 PM
  3. 16 bit or 32 bit
    By Juganoo in forum C Programming
    Replies: 9
    Last Post: 12-19-2002, 06:24 AM
  4. 40, 128 BIT encryption
    By GaPe in forum C Programming
    Replies: 14
    Last Post: 02-04-2002, 12:44 PM
  5. Array of boolean
    By DMaxJ in forum C++ Programming
    Replies: 11
    Last Post: 10-25-2001, 11:45 PM

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