Yali Devlog: Intro

Introduction

I have always been fascinated by modern encryption. I have tried multiple times to implement RSA. But I have failed every single time. Why? Because I wrote it in Python I didn’t make it blazingly fast by writing it from scratch in 100% safe Rust.

So I started writing my own large int library from scratch. And I am finally able to perform 1024-bit RSA decryption under 500 ms on my desktop computer :)

1
2

[svante@desktop-nixos ~/development/yali]$ time target/release/yali
target/release/yali  0,25s user 0,00s system 99% cpu 0,250 total

How did I get here

I started out, thinking it was easy, by just storing all data in a simple Vec<u8>, and using a lot of greedy algorithms. This was extremely slow, taking multiple seconds just performing RSA encryption.

As I continued, I made a couple of optimisations:

1. Implement a more efficient multiplication alogorithm
2. Implement a more efficient exponetiation algorithm
3. Implement a more efficient division algorithm

And one of the most effective changes was: Changing the underlying datatype from Vec<u8> to [u8; N]. This avoids allocating memory on the heap every time you perform an operation.

Future plans

In the future, I’m planning to implement:

• Toom-Cook multiplication
• Montgomery modular multiplication

My current goal is reaching <100 ms.

Bye bye :33