In this post I plan on first giving an overview how RSA and public-key cryptography in general work, followed by a basic implementation of RSA in the Dart programming language.

Overview

The analogy

Say you have Bob who wishes to send a secret message to Alice and an evil person, Eve who intercepts and reads all of their communications. Alice and Bob had no time beforehand to exchange secret keys so how do they communicate without eavesdropping? Simple, Alice buys a padlock, unlocks it and sends it to Bob (keeping the key). Bob then places his message in a box and locks it with the padlock; he sends the secured box to Alice. Eve intercepts the box however she can't unlock it, meaning she is forced to let it continue to Alice without recovering the message. This means that only when Alice receives the box and uses her key can the message be read.

In the above example the padlock can be thought of as the public key, something that is viewable by everybody and can lock (encrypt) the message but not decrypt it. Alice's key can be thought of as the private key, something that only she possesses that can unlock (decrypt) the message but not encrypt it.

This may be very easy in the real world but how is this possible computationally? The answer lies within a very clever algorithm named RSA.

The trapdoor

The secret to public-key cryptography is a function that is easy to perform in one direction however difficult to reverse without a special piece of information called the trapdoor.

In RSA the trapdoor works as follows. It is fairly easy to compute a large $d$, $e$ and $n$ such that:

$$(m^e) ^d\equiv m\mod n$$

for all integer $m$. This means we can give away $e$ and $n$ as the public key and encrypt the message $m$ thus:

$$m^e\equiv c\mod n$$

where $c$ is the encrypted message. Here is our one way function as it is very difficult to recover $m$ given only $e$ and $n$. The trapdoor turns out to be the secret (private key) $d$ as:

$$c^d\equiv (m ^e) ^d\equiv m\mod n$$

Now, you may be wondering how we generate a $d$, $e$ and $n$ so that with $e$ and $n$ it is very difficult to work out $d$. For this we need a second one way function. This is where the magic begins.

Time complexity

It is relativity easy for a computer to both find large prime numbers and multiply large numbers; it is hard however for a computer to find the prime factorisation of a large number.

So if we take two large prime numbers, $p$ and $q$ and say:

$$p\times q=n$$

then we have a one way function as it is easy to compute $n$ given $p$ and $q$ however very hard to calculate $p$ and $q$ given $n$. Now all we need to do is find a function that depends on knowing the prime factorisation of $n$.

Euler's totient function

Euler's toitent function takes a number, $x$ and returns how many numbers below $x$ share no prime factors with $x$. The function is denoted with $\phi$ (phi), so:

$$\phi(6)=2$$

as $1$ and $5$ share no prime factors with $6$. What is interesting to note is that Euler's toitent function is very hard to calculate in all cases except when the argument, $x$ is prime. In that case:

$$\phi(x)=x-1$$

as it $x$ only shares a prime factor with itself. Also, it happens that:

$$\phi(xy)=\phi(x)\phi(y)$$

so long as $x$ and $y$ are coprime (share no prime factors).

To relate this back to our $p$, $q$ and $n$, we know that:

$$\phi(n)=\phi(p)\phi(q)=(p-1)(q-1)$$

Now we just have one more step to make before everything should fall into place.

Euler's theorem

Euler's theorem states that:

$$m^{\phi(n)}\equiv1\mod n$$

for any integer m as long as $m$ and $n$ are coprime which is very likely in our case $n$ is a product of 2 primes (also RSA doesn't break even if they are coprime). This means that:

$$(m^{\phi(n)}) ^k\equiv m ^{k\times\phi(n)}\equiv1 ^k\equiv1\mod n$$

so:

$$m\times m ^{k\times\phi(n)}\equiv m\equiv(m ^d) ^e\equiv m ^{de}\mod n$$

thus:

$$m ^{k\times\phi(n)+1}\equiv m ^{de}\mod n$$

meaning:

$$k\times\phi(n)+1=de$$

and finally have an equation for $de$ which is dependant on $\phi(n)$. This means that it is very difficult do work out $d$ (the private key) from $e$ (the public key) without $\phi(n)$. All we need to do now is rearrange:

$$d=\frac{k\times\phi(n)+1}{e}$$

, chose an $e$ so that it is coprime with $\phi(n)$ ($3$ and $2^{16}+1$ are common choices) and find the lowest value of $k$ that makes $d$ an integer.

We are done!!! That is it, we have our $d$, $e$ and $n$ which meet all the criteria and are ready to go.

An example with small numbers

Note, in real cases you should use very large primes. We will get to that when we start our Dart program.

Lets say Bob wants to send the message, $m=42$ to Alice without Eve decrypting it. First Alice chooses two random primes, $p=29,q=47$ and multiplies them to get $n=1363$. She also calculates $(p-1)\times(q-1)=28\times40=1288=\phi(n)$. Now we know:

$$d=\frac{k\times1288+1}{e}$$

so if we use $e=3$ (making the lowest $k=2$):

$$d=\frac{2\times1288+1}{3}=859$$

Now she sends $e$ and $n$ to Bob. He calculates:

$$c=42^3=486\mod1363$$

and sends $c$ to Alice. Eve has no way of getting the original message as only Alice knows the private key. Finally Alice calculates:

$$m=486^859=42\mod1363$$

to decrypt the message.

We have a working algorithm. Now to implement it Dart.

Implementation

We will be referring to this document to make sure our algorithm is as secure as possible.

Generating p and q

The document states that before generating p and q, we must first chose an e. We will chose the bare minimum of $2^{16}+1$. Next we will implement the algorithm specified in B.3.3. Our nlen will be $2048$.

The first big obstacle I can see is the limitation in length of Dart's int data type. Luckily there is also BigInt which supports arbitrarily large integers and is what we will be using. It also has a number of helpful methods.

Unfortunately there is no direct way to generate a random BigInt so we will use a large number of bools to do so.

BigInt randomBigInt(Random rng, int bitLength) {
  BigInt bigInt = BigInt.zero;
  for (int i = 0; i < bitLength; i++) {
    if (rng.nextBool()) {
      bigInt = (bigInt << 1) + BigInt.one;
    } else {
      bigInt = bigInt << 1;
    }
  }
  return bigInt;
}

Another obstacle is testing weather or not a number is prime. To do this we will use a certain number of Miller-Rabin tests (5 in our case). So the next step is to implement that as documented in C.3.1.

bool isPrime(Random rng, BigInt w, int iterations) {
  if (w.isEven) {
    return false;
  }

  int a = 0;
  BigInt m = w - BigInt.one;
  while (m.isEven) {
    m = m >> 1;
    a += 1;
  }

  for (var i = 0; i < iterations; i++) {
    BigInt b = BigInt.zero;
    while ((b <= BigInt.one) || (b >= (w - BigInt.one))) {
      b = randomBigInt(rng, w.bitLength);
    }

    BigInt z = b.modPow(m, w);

    if ((z != 1) && (z != (w - BigInt.one))) {
      bool broken = false;
      for (int j = 0; j < (a - 1); j++) {
        z = z.modPow(BigInt.two, w);

        if (z == BigInt.one) {
          return false;
        } else if (z == (w - BigInt.one)) {
          broken = true;
          break;
        }
      }
      if (!broken) {
        return false;
      }
    }
  }
  return true;
}

Okay, now we are actually ready to generate p and q.

List<BigInt> genPQ(Random rng, int nLen, BigInt e) {
  BigInt p = BigInt.zero;
  while ((!isPrime(rng, p, 5)) || ((p - BigInt.one).gcd(e) != BigInt.one)) {
    p = BigInt.zero;
    while (p < (((BigInt.two.pow((nLen ~/ 2) - 1))
        ~/ BigInt.from(70)) * BigInt.from(99))) {
      p = randomBigInt(rng, nLen ~/ 2);
      if (p.isEven) {
        p = p + BigInt.one;
      }
    }
  }

  BigInt q = BigInt.zero;
  while ((!isPrime(rng, q, 5)) || ((q - BigInt.one).gcd(e) != BigInt.one)) {
    q = BigInt.zero;
    while (((p - q).abs() <= BigInt.two.pow((nLen ~/ 2) - 100)) ||
        (q < (((BigInt.two.pow((nLen ~/ 2) - 1)) ~/
            BigInt.from(70)) * BigInt.from(99)))) {
      q = randomBigInt(rng, nLen ~/ 2);
      if (q.isEven) {
        q = q + BigInt.one;
      }
    }
  }

  return <BigInt>[p, q];
}

It takes about a minute to run but it works! We have generated our two primes. Now all we need to do is generate d and n and we have a working implementation.

Generating d and n

This is luckily the easiest part of the whole process and as such we can just put the code in our main function and we should be done.

void main() {
  Random rng = new Random.secure();
  BigInt e = BigInt.from(pow(2, 16) + 1);
  print('e -> $e');
  
  List<BigInt> pq = genPQ(rng, 2048, e);
  BigInt p = pq[0];
  BigInt q = pq[1];
  print('p -> $p');
  print('q -> $q');

  BigInt n = p * q;
  print('n -> $n');

  BigInt k = BigInt.one;
  while (((k * ((p - BigInt.one) * (q - BigInt.one))) + BigInt.one)
      .remainder(e) != BigInt.zero) {
    k = k + BigInt.one;
  }
  BigInt d = ((k * ((p - BigInt.one) * (q - BigInt.one))) + BigInt.one) ~/ e;
  print('d -> $d');

  print('');
  print('Test with message 42:');
  BigInt ct = BigInt.from(42).modPow(e, n);
  print('c -> $ct');
  BigInt mt = ct.modPow(d, n);
  print('m -> $mt');
}

You can find the full implementation here (it is usual for it to take several minutes to work).

Closing notes

Signing

Because:

$$(m ^e) ^d\equiv (m ^d) ^e$$

the process actually works both ways meaning it is possible to encrypt with the private key and decrypt with the private key. This concept is used in signing messages to prove the identity of the sender.

References

I would never have been able to comprehend half of this stuff without these great resources:


Thank you for reading,

Joseph.

P.S. If you see any mistakes or parts that could be clearer, please contact me through twitter @OshawkUK.