How to implement RSA in GDScript with BigCat?

Written by Meowing Cat on 5/30/2024, 2:41:00 PM

A simple implementation of RSA in GDScript with my BigCat library.

Hello, cat is here again! Today I will show you how to implement RSA in GDScript with my BigCat library. Let’s get started!

Introduction

Important! Do NOT use this code in production! This is just a simple implementation of RSA in GDScript for educational purposes. Godot Engine already has a built-in encryption system called Crypto that you should use for secure data transmission.

RSA is a public-key encryption encryption algorithm that is widely used in secure data transmission.

The strength of RSA encryption comes from the fact that it is impossibly hard to factorize big prime numbers with our current technology.

As you can see, implementing RSA needs big numbers, and GDScript doesn’t support big numbers natively. That’s why I created BigCat, a library for arithmatical and cryptographic operations with big numbers.

Installation

First, you need to install BigCat. You can download it from the GitHub repository and just put the BigCat.gd file in your project.

Note: You might prefer adding BigCat as a Git submodule to your project too.

Generating Big Primes

To generate big prime numbers, we can use the BigCat.generate_prime() function.

Note: Generating bigger primes than 256 bits might take a long time with BigCat. I optimized it as much as I could, but it’s still slow. I’ll look later to improve it.

extends Node

func _ready():
    var prime = BigCat.BigNumber.generate_prime(256)
    print("Prime: ", str(prime))

This code will generate a 128-bit prime number and print it.

Generating RSA Keys

To generate RSA keys, we need to generate two big prime numbers, p and q. Then we calculate n = p * q, phi = (p - 1) * (q - 1), e = 65537, and d = e^-1 mod phi.

Note: We used 65537 for e. It is commonly used in RSA implementations because it is prime, big enough and its binary representationi is 0b10000000000000001 which is easy to calculate for CPUs due to that it has only two 1 at the beginning and the end and all the rest is 0.

extends Node

@export var BITS = 256

func _ready():
    print("Generating RSA key pair...")

    var p = BigCat.BigNumber.generate_prime(BITS)
    var q = BigCat.BigNumber.generate_prime(BITS)
    var n = p.multiply(q)
    var phi = p.subtract(BigCat.BigNumber.from_int(1)).multiply(q.subtract(BigCat.BigNumber.from_int(1)))
    var e = BigCat.BigNumber.from_int(65537)
    var d = e.inverse_modulo(phi)

    print("Public Key: (" + str(e) + ", " + str(n) + ")")
    print("Private Key: (" + str(d) + ", " + str(n) + ")")

Encrypting and Decrypting

To encrypt and decrypt messages, We’ll use the RSA algorithm. Simply, we can encrypt a message m with the public key (e, n) as c = m^e mod n and decrypt it with the private key (d, n) as m = c^d mod n.

var message = "Hello, World!"
var big = BigCat.BigNumber.from_chars(message.to_ascii_buffer())
var encrypted = big.power_modulo(e, n)
var decrypted = encrypted.power_modulo(d, n)

print("Original Scalar: \t", str(big))
print("Encrypted Scalar: \t", str(encrypted))
print("Decrypted Scalar: \t", str(decrypted))

This code will encrypt and decrypt the message “Hello, World!” with the RSA keys we jut generated.

---

Conclusion

That’s it! We implemented RSA in GDScript with BigCat.

I hope you enjoyed this tutorial. If you have any questions or suggestions, you can open an issue on the BigCat repository on GitHub.

---

Thanks for reading! Meow! 🐾