• Advertisement
Sign in to follow this  

RSA Implementation - Optimizing Key Generation

This topic is 3958 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've decided to use RSA as the asymmetric encryption system for my network engine (Along with Blowfish or possibly AES for the symmetric side) and I'm looking for help doing some optimizations for my implementation. Currently it takes a rather large amount of time to generate 1024 bit keys (I'm not how long on average, because I haven't ran it for very long), and an average of about 6 seconds to generate a 512 bit key. This is way longer than it should be, and I'm not sure why. Here's the code as of June 23 http://nick.weihs.googlepages.com/rsa.zip The bulk of the implementation is put into the large integer class. I have the 4 standard arithmetic ops as well as left/right shifting. I'm using the square and multiply method for modular exponentiation: http://en.wikipedia.org/wiki/Modular_exponentiation I'm using the Rabin-Miller test for primality testing (as well as testing the first 70 or so primes initially): http://en.wikipedia.org/wiki/Miller-Rabin The method I'm using for sampling prime numbers is to generate a random number, multiply by 6 and add 1. This is the main area that I'm looking for improvement in, since it is such a naive method. Any advice/comments are useful.

Share this post


Link to post
Share on other sites
Advertisement
First off, why are you writing an RSA key generator yourself? A brief google came up with about a dozen open source implementations already available.

Secondly: RSA key generation is slow. You shouldn't need to generate more than one keypair (if you do, you've probably done something wrong) for your server, ever. That typically means you don't even need a key generator algorithm at all, just ask them to provide a certificate which can be produced by pretty much any certificate generator (OpenSSL for instance).

Things to note: If your private key gets compromised (very very unlikely unless your server is broken into), you'll need to generate another keypair, again, OpenSSL etc. can all do this for you, best not to implement it yourself.

Share this post


Link to post
Share on other sites
I wanted to do it myself because I like writing code and I wanted to see if I could do it. If nothing else, I learn a bit about how encryption works. Plus I'd rather not have any dependencies if I can help it.

If I can get good performance with generating keys, I don't see why I couldn't generate a new key whenever I started a server up. Also, this is an instance where more than one person will be running a server (like counter-strike), so the point here is really more just to prevent people from snooping/tampering with packets.

Share this post


Link to post
Share on other sites
Quote:
Original post by NickW
I wanted to do it myself because I like writing code and I wanted to see if I could do it. If nothing else, I learn a bit about how encryption works.

I doubt writing a keypair generator will teach you much about encryption theory, none the less enjoy.
Quote:
Plus I'd rather not have any dependencies if I can help it.

Hate to break it to you, but middleware is a fact of life, it reduces development time, and decreases the number of bugs you have to deal with. You're going to have dependencies on any number of systems as it is (your host operating system's API for instance).
Quote:
If I can get good performance with generating keys, I don't see why I couldn't generate a new key whenever I started a server up. Also, this is an instance where more than one person will be running a server (like counter-strike), so the point here is really more just to prevent people from snooping/tampering with packets.

Huh? Why on earth would you generate a key each time it launched? That's just silly. There is no point in it. Furthermore, as I mentioned above, having them provide the key means it will be different for each server. Not to mention: If they want snoop the packet, it will be snooped before it's even encrypted. Not to mention the added overhead of encrypting and decrypting the packets on both ends (the exception here is authentication, in which case security is a must) will incure a non-negligible performance penalty for both the client and the server. (You'll note that CS does not encrypt it's packets noticably, nor do most other games.)

Share this post


Link to post
Share on other sites
Well, having written the entire encryption system (not just the keypair generator), I have learned a lot about encryption.

Yes, I realize the benefits of middleware. The network engine is intended to be (somewhat) middleware itself. However, seeing as how this is just a hobby project, I have no deadlines or expectations, so I don't really care about development time. In the past, I have used crypto++, which is a very robust and extensive encryption library, but it is also rather unwieldy and cumbersome. I therefore decided for as much as the reasons I've already stated, that I'd try to write my own. If someone had come to me, for example, to ask for help on optimizing their 3d engine (of which there are an overabundance of open source solutions), I would probably try to help them instead of berating their attempt.

Forcing the server operators to generate their own key pair just makes it harder for casual users to run servers, which I think should be as easy as possible. At the company I work (which this project is not a part of), we use exclusively encrypted data streams for our games, and there are plenty of other games that do this as well. Since it's impossible to access the data before it's encrypted (it's running on a PS3), it's practically impossible to tamper with the data stream. The overhead of decrypting packets is just dealt with, since packets are only received sporadically in the overall scheme of things. On a PC it is possible to examine/tamper with memory, however many games still encrypt their data (I think WoW does).

Share this post


Link to post
Share on other sites
Quote:
Original post by NickW
Yes, I realize the benefits of middleware. The network engine is intended to be (somewhat) middleware itself. However, seeing as how this is just a hobby project, I have no deadlines or expectations, so I don't really care about development time. In the past, I have used crypto++, which is a very robust and extensive encryption library, but it is also rather unwieldy and cumbersome. I therefore decided for as much as the reasons I've already stated, that I'd try to write my own. If someone had come to me, for example, to ask for help on optimizing their 3d engine (of which there are an overabundance of open source solutions), I would probably try to help them instead of berating their attempt.
You were helped. But since the help was not explicit you probably didn't realize it. If you've ever run CN or any other key-pair generating executable then you will note that it typically takes several seconds (or longer) to run. This isn't because they've opted to let it run slow.
Quote:
Forcing the server operators to generate their own key pair just makes it harder for casual users to run servers, which I think should be as easy as possible. At the company I work (which this project is not a part of), we use exclusively encrypted data streams for our games, and there are plenty of other games that do this as well. Since it's impossible to access the data before it's encrypted (it's running on a PS3), it's practically impossible to tamper with the data stream. The overhead of decrypting packets is just dealt with, since packets are only received sporadically in the overall scheme of things. On a PC it is possible to examine/tamper with memory, however many games still encrypt their data (I think WoW does).

If wow uses any encryption at all for non-authentication data, which i doubt, then it is not noticable when examining the source of the many WoW Emu's that exist today. Neither does Lineage 2, Everquest, nor most other MMOs. The fact of the matter is, encrypting data for a high traffic game (such as action games like FPS, MMOGs, etc.) is not useful nor very secure in the end (as the end user already has access to the packet before it's sent. On console platforms it is true that the user may not be able to access the data prior to it being sent, however that would also require the server to be on a PS3, or non-PS3 software being only accessable by the vendor, this of course has additional problems (as L2 has had more than once). This is a rather stringent platform limitation, but certainly one that could be demanded.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement