[RevEng] Challenge/keygenme #88: the solution

For a keygenme #88.

Yes, this is (textbook) RSA.

I've seen this code in wild and decided I could make a keygenme out of it.

There was issues in the original code I saw.

First, toyish implementation of bignum functions. Bignum is usually divided by limbs (in GNU MP lingo) and each limb is usually occupies one CPU register (32 or 64 bits). But here limb has a size of 31 bits. (As if the author only had signed data types.) This makes all bignum functions slightly more complicated, confusing and slow. But workable.

Another oddity: while $e$ constant in RSA is usually a small number (often, 65537), here it was big. This is still secure, but not recommended, because it can make $d$ (too) small. Hence, encryption process is slower. (But decryption is faster.)

Also, it was a textbook RSA, which is deterministic. Ciphertext is each time the same for each plaintext. This is generally undesirable property even in cryptography of WW2 times. (Use paddings.)

Also, no checksum or MAC. But magic cookie is checked. (MAC is important.)

As you may see, all license codes are slightly different in lenght -- just because these are bignum numbers.

When I prepared this keygenme, I set RSA modulo to ~400 bits, so that it can be factored by CADO-NFS in several hours on a decent CPU.

The source code for keygenme88.

At least two guys solved this keygenme correctly. Hall of fame:

25-Jan-2022: psraining(a)gmail.com (correct code) c12f38864ca77cdd12d867f8e309dbbbcc9238a8ce5eb15c9fca2d81143a8d5ff20078978512a324218afad66f5b88daf66f

24-Mar-2022: cdemirer(@)protonmail.com (keygen!)

(the post first published at 20231029.)

List of my other blog posts.

Subscribe to my news feed

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.