# What kind of RSA is this?

I'm currently trying to write a server emulator for a multiplayer game. I've found what I believe to be the RSA keys. I've found that by editing them I can get the real login server to reject them saying they are corrupt, IE. not encrypted properly. So from that I can confirm they are the correct keys. However, I can't figure out how to generate my own because they are a little weird.

The modulus is 511 bits long and the exponent is 128. Does this mean they are a 512-bit RSA key? When I generate my own, my public keys exponent is much smaller at only 17 bits long. How can I create my own key pair that is this strange size?

Sorry if this is a bad question, I am new to this.

• What makes you think that they're RSA keys? What makes you think that the parts have these sizes? Such sizes would indeed be very strange. If you tell us everything you've found out about how these keys are represented and used, we may be able to help. As it is, I don't think it's possible to deduce any useful information from your question, other than “you're probably reading it wrong”. – Gilles 'SO- stop being evil' Jul 10 '18 at 6:31
• In the code they are used like this: BigInteger bigInteger3 = new BigInteger(arrby); BigInteger bigInteger4 = bigInteger3.modPow(bigInteger, bigInteger2); bigInteger and bigInteger2 are the exponent and modulus values. bigInteger3 is the incoming buffer to decrypt sorry for the variable names. They are decompiled – Tyler H Jul 10 '18 at 7:36
• That's really a bad implementation. – Changyu Dong Jul 10 '18 at 7:49
• Its not mine, its from a game from around 2005 – Tyler H Jul 10 '18 at 12:08
• @TylerH if you are user60258 you may want to merge your accounts. – SEJPM Jul 10 '18 at 12:37

Does this mean they are a 512-bit RSA key?

No, this means they're using a 511-bit RSA key. A 511-bit key is for all security-related aspects essentially the same as a 512-bit key, but well, technically it isn't.

When I generate my own, my public keys exponent is much smaller at only 17 bits long.

The implementation you used to generate the keys probably picked the standard exponent which is $e=65537=2^{16}+1$, whereas the developers of the key in question probably rolled their own key generation and just generated a random 128-bit exponent, which is valid, albeit quite slow.

How can I create my own key pair that is this strange size?

What they have likely done is they sampled two primes $p,q$ that satisfy $2^{255}\leq p,q<2^{256}$ and got two primes which are closer to $2^{255}$ than to $2^{256}$ which results in their product only taking up 511 instead of the expected 512 bits. One small scale example for this would be $17$ and $19$ which when multiplied yield $323$, the latter taking only 9 bits to represent and the former two both taking 5 bits each to represent.

What you can now do is to either just break the key-pair they used by factoring their modulus, which would cost about 50-100USD on Amazon's AWS EC2 these days, this may be illegal though. Or you could just instruct your implementation to generate 511 bit keys if you really want to, which should work, otherwise you'll probably have to generate your own primes and just try 256-bit primes until you get a pair that yields a 511-bit product and then do the RSA key generation math, it's no that hard and I think the Java standard library has helper functions for that. Using this way you can also just pick a 128-bit public key. But note that depending on how you implement the prime search the private key may be easily factorable, but then this may not matter to you.

The key size of RSA is the size of the public modulus $N$. Thus it is likely 512-bit RSA if it is indeed an RSA key. As to the public exponent $e$, it is valid as long as it is co-prime to $\phi(N)=(p-1)(q-1)$, so that you can find $d$ that satisfies $e\cdot d \equiv 1 \bmod \phi(N)$. Usually for efficiency, a small exponent like 65537 is used, but you can generate a random longer one if there is a reason ro do so.

• However, in this case, the keys length is 511 – Tyler H Jul 10 '18 at 12:08
• yes, 1 bit doesn't make too much difference, it is roughly 512-bit, which I guess is the goal of the game developer. You can call it RSA-511 if you want. It is likely they "homebrewed" their own implementation and did not quite work out how to generate proper keys. – Changyu Dong Jul 10 '18 at 12:58