RSA public-key cryptography

So a few months ago, I implemented RSA in pure Lua, and I thought I may as well publish it here for people to use.

Don't know what RSA or public-key cryptography is? Here are 2 great videos by Brady Haran: https://www.youtube....h?v=GSIDS_lvRv4 and https://www.youtube....h?v=M7kEpw1tn50

Just a word of warning, I am no cryptographer whatsoever. My implementation is probably flawed in a million different ways, and can probably be optimized to be 2x faster. I'm just some random guy who wanted to see if I could implemented RSA in pure Lua with little idea about the underlying maths and concepts. If you find any issues or have any suggestions, tell me!

Here's the key pair generator: http://pastebin.com/udGZapmD
And here's the encryption/decryption library with an example at the bottom that you can run: http://pastebin.com/0zZYjxLw
Licenses: http://pastebin.com/9gWSyqQt

The generator generates a public and private key pair stored under /public.key and /private.key respectively. The keys it generates are extremely insecure, as the prime numbers are only 39 digits, so the keys are 256 bit. This means the key can be factored in less than a minute on a decent desktop computer using something like http://sourceforge.net/projects/yafu/. I tried running YAFU in a virtual machine on my MacBook Pro, and it only took 3 minutes to factor the key, on average it only used 30% of my CPU (not sure why):


So yeah, super insecure keys, don't use them for anything super serious. If anything, this is more for educational purposes rather than proper cryptography.

If you have any questions, feel free to ask me here. If I don't respond here, email me at [email="me@chuie.io"]me@chuie.io[/email] to get my attention.

That is pretty awesome, a huge keysize improvement over my puny 60-bits keys proof of concept.
Thought I wonder, are you limited to 256-bits keys because of the key generation, or because of encryption/decryption?
What if larger keypairs were generated outside of CC, would it still encrypt/decrypt efficiently?

Anavrins, on 11 October 2015 - 09:17 PM said:

That is pretty awesome, a huge keysize improvement over my puny 60-bits keys proof of concept.
Thought I wonder, are you limited to 256-bits keys because of the key generation, or because of encryption/decryption?
What if larger keypairs were generated outside of CC, would it still encrypt/decrypt efficiently?

I limited it to 256 bit keys because they already take on average about 100 seconds to generate, and 1-2 seconds to encrypt/decrypt. Larger keys take longer to generate and to encrypt/decrypt with. It becomes impractical if you try to generate keys that are any larger, but you can try it for yourself.

Thanks for sharing. :D/> +1

You should implement signing & verification. Would be *super* useful.

You've implemented quantum physics. GJ. I tried to run your demo on CC 1.74 and it errored "Arguments must be the same lenght". So I went to CC 1.73 and tried to look at it, and it worked like it should.