# Toy RSA in TypeScript (Part 2, Digital Signatures)

This article is the second in my Toy RSA series. In [the first article](https://hackmd.io/@sp1derca7/crypto-rsa-1), I introduced the basic principles of [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) and wrote a toy library using TypeScript. Here, we will briefly review RSA, including how to generate key pairs and perform encryption and decryption. Subsequently, I will introduce how to use RSA to generate and verify [Digital Signatures](https://en.wikipedia.org/wiki/Digital_signature), and I will also provide a practical example.

## KeyGen, Encryption & Decryption

RSA is based on the [Prime Factorization Problem](https://en.wikipedia.org/wiki/Integer_factorization). Let's review how to generate an RSA key pair:

* Randomly generate two very large (e.g., 1024 bits) prime numbers `p` and `q`
* Calculate the product `n` of `p` and `q`: `n = p⋅q`
* Compute `φ(n)` where `φ` is the [Euler's Totient Function](https://en.wikipedia.org/wiki/Euler%27s_totient_function)
* Choose an integer `e` such that `1 < e < φ(n)` and `gcd(e, φ(n)) = 1`
* Compute the [Multiplicative Inverse](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) `d` of `e` modulo `φ(n)`, that is, `e⋅d ≡ 1 (mod φ(n))`
* Make `d` the Private Key, and keep it confidential along with `p` and `q`
* Make `(n, e)` the Public Key and disclose it to the public

The encryption and decryption algorithms of RSA are very simple. We use the public key to encrypt the plaintext and the private key to decrypt the ciphertext, which can be expressed by the formulas:
$$
\begin{align*}
E(m, e, n) &= m^e \bmod n = c \\
D(c, d, n) &= c^d \bmod n = m
\end{align*}
$$

In the previous article, we wrote a Toy RSA library in TypeScript. Here is the code for the encryption and decryption functions:

function rsaEncrypt(m: bigint, pubKey: RsaPubKey): bigint {
  return powerMod(m, pubKey.e, pubKey.n);
}
function rsaDecrypt(c: bigint, privKey: RsaPrivKey): bigint {
  return powerMod(c, privKey.d, privKey.n);
}

The following figure shows the entire process of RSA key pair generation, as well as encryption and decryption:


## Digital Signatures

Based on our previous review, we know that anyone can use the public key to encrypt a message (a certain large integer) to obtain the ciphertext (another large integer), but only the corresponding private key can decrypt it.

By reversing this process, we can derive the digital signature algorithm: using the private key to "decrypt" certain information (a large integer) yields a digital signature (obtaining another large integer). Anyone can use the public key to "encrypt" the digital signature to restore the original information, thereby verifying the signature. We can express the signature and verification functions with formulas as follows:
$$
\begin{align*}
S(m, d, n) &= m^d \bmod n = s \\
V(s, e, n) &= s^e \bmod n = m
\end{align*}
$$

To clearly express our intention, we can use `rsaDecrypt()` to implement the signature function and `rsaEncrypt()` to implement the function that verifies the signature. We then add these two functions to our toy library:

function rsaSign(m: bigint, privKey: RsaPrivKey): bigint {
  return rsaDecrypt(m, privKey);
}
function rsaVerifySig(m: bigint, s: bigint, pubKey: RsaPubKey) {
  return rsaEncrypt(s, pubKey) == m;
}

We slightly modify the figure from the previous section to illustrate the process of RSA signing and signature verification:


## A Practical Example

Although the RSA encryption and decryption algorithms are very simple, directly using RSA to encrypt and decrypt large amounts of data is not very efficient. Therefore, RSA is usually only used to encrypt and decrypt the keys of some symmetric encryption algorithms (such as [AES](https://en.wikipedia.org/wiki/Advanced_Encryption_Standard)).

Similarly, directly using RSA to digitally sign large amounts of data is not very efficient. Therefore, it is common practice to first compute a digest of the data (which is much shorter than the original) using an efficient cryptographic [Hash](https://en.wikipedia.org/wiki/Cryptographic_hash_function) function (such as [SHA-2](https://en.wikipedia.org/wiki/SHA-2)), and then to digitally sign this digest.

Moreover, actual encryption, decryption, and digital signature algorithms need to consider many other details, such as [padding](https://en.wikipedia.org/wiki/Padding_(cryptography)). Taking digital signatures as an example, the following figure (from [this blog post](https://bntan.medium.com/understanding-rsa-digital-signatures-cfba3bc67428)) shows these details:


Node.js provides a [crypto](https://nodejs.org/api/crypto.html) library, which we used in the previous article to generate RSA key pairs. This library can also generate and verify RSA signatures. Below is a test:

import * as crypto from 'crypto';

function testSignVerify() {
  const { publicKey, privateKey } = generateKeyPairSync('rsa', {modulusLength: 512});
  console.log('pubKey:', publicKey.export({ format: 'jwk' }));
  console.log('privKey:', privateKey.export({ format: 'jwk' }));

  const data = Buffer.from("Toy RSA in TypeScript"); 
  const hash = crypto.createHash('SHA256').update(data).digest('hex');
  console.log('digest:', hash);

  const sig = crypto.sign('RSA-SHA256', data, privateKey).toString("hex"); 
  console.log("signature:", sig);

  const verify = crypto.verify('RSA-SHA256', data, publicKey, Buffer.from(sig, "hex"));
  console.log("verfication:", verify);
}

As with the previous article, we print out the public and private keys in [JWT](https://jwt.io/) format to clearly display the various parameters of the key pair. The first argument we pass to the [sign()](https://nodejs.org/api/crypto.html#crypto_class_sign) function is `RSA-SHA256`, indicating that we want to generate an RSA digital signature using SHA-256 for hashing. Additionally, this function [defaults](https://nodejs.org/api/crypto.html#cryptosignalgorithm-data-key-callback) to using the [PKCS#1 v1.5](https://en.wikipedia.org/wiki/PKCS_1) padding scheme. Running the above test will produce output similar to the following:

pubKey: {
  kty: 'RSA',
  n: 'zugRK3B3P7DSkNKzV4S-TxH-AsBlx9dpdgSVgCl56kpmfpXnKi5GVXMlnZHaz9IOP6kDGb0YLc-ApcqHWg7HyQ',
  e: 'AQAB'
}
privKey: {
  kty: 'RSA',
  n: 'zugRK3B3P7DSkNKzV4S-TxH-AsBlx9dpdgSVgCl56kpmfpXnKi5GVXMlnZHaz9IOP6kDGb0YLc-ApcqHWg7HyQ',
  e: 'AQAB',
  d: 'O87ZJ7Vaww5Zz4MYVDQKztBknGcBBMM_uN2aWXGjzBUwU28jv7UIxHGXqifFK8PG8K0tL4XIukqVtyXeaKEoAQ',
  p: '8eAHjgEyHDOvhnMk2O5CmwtCyh4Zcg5WqnHPFY7MXiM',
  q: '2v1EFswcDNCLBpMVBDYyOWoud7rzUjri_7FygSpmgyM',
  dp: 'kVtaDuwHCk3BaWJfPYMKQhTlYYPvNM0LJklY8xKrHNM',
  dq: 'RLvdlTI3U6ZZHJUpsYq5NOAo-ZeKK7Mj8JFnmTcPufU',
  qi: 'JPHMJULvzPoq4mRnq1C0nptzYpfg8MeU7Pbr8bpt_lQ'
}
digest: aa23971be46426633e1f6e17cd34e2bd524ce7d64634bae97c26ffebbc185645
signature： a740befbd529cb4b57fe5aad5ed15a605f369157f8072c00a47fd30b2f9b030b2ec980251381488c664852bad745fc1cea3525f45e5b0a96c88044702bb84141
verfication: true

JWT uses [Base64URL](https://www.rfc-editor.org/rfc/rfc4648#section-5) to encode field values, so we need to decode these parameters. Based on the decoded parameters, we can write a test to verify the digital signature generated above:

function testVerifySig() {
  const p = 0xf1e0078e01321c33af867324d8ee429b0b42ca1e19720e56aa71cf158ecc5e23n;
  const q = 0xdafd4416cc1c0cd08b069315043632396a2e77baf3523ae2ffb172812a668323n;
  const n = 0xcee8112b70773fb0d290d2b35784be4f11fe02c065c7d769760495802979ea4a667e95e72a2e465573259d91dacfd20e3fa90319bd182dcf80a5ca875a0ec7c9n;
  const e = 0x010001n; // 65537n
  const d = 0x3bced927b55ac30e59cf831854340aced0649c670104c33fb8dd9a5971a3cc1530536f23bfb508c47197aa27c52bc3c6f0ad2d2f85c8ba4a95b725de68a12801n;

  const digest = 0xaa23971be46426633e1f6e17cd34e2bd524ce7d64634bae97c26ffebbc185645n;
  const sig = 0xa740befbd529cb4b57fe5aad5ed15a605f369157f8072c00a47fd30b2f9b030b2ec980251381488c664852bad745fc1cea3525f45e5b0a96c88044702bb84141n;
  
  const pubKey = {e, n};
  const privKey = {d, n};
  const data = rsaEncrypt(sig, pubKey);
  console.log(data.toString(16));
  assert.ok(data.toString(16).endsWith(digest.toString(16)));
}

We first recover the signed data (padding + digest) through `rsaEncrypt()`, and then compare it with the digest to prove that the signature is valid. Here, we focus on the data that is actullay signed, which is the output printed by running the above test:

1ffffffffffffffffffff003031300d060960864801650304020105000420aa23971be46426633e1f6e17cd34e2bd524ce7d64634bae97c26ffebbc185645

Breaking it down into four parts makes it easier to understand:

* `0x1`, maybe this is the version number
* `0xffffffffffffffffffff`, padding, the number of `f`s is `(key_bits/8 - 54)*2`
* `0x003031300D060960864801650304020105000420`, [ASN.1 DER encoding](https://stackoverflow.com/questions/3713774/c-sharp-how-to-calculate-asn-1-der-encoding-of-a-particular-hash-algorithm) of hash algorithm `SHA256`
* `0xaa23971be46426633e1f6e17cd34e2bd524ce7d64634bae97c26ffebbc185645`, this is the digest

## Summary

Let's review the key points discussed in this article:

- RSA is an asymmetric encryption algorithm, with the public key used for encryption and the private key for decryption. Due to the relatively slow speed of RSA encryption and decryption, it is typically only used to encrypt and decrypt keys for other symmetric encryption algorithms.
- The process can be reversed for digital signatures: the private key is used to generate a digital signature through decryption, and the public key is used to verify the signature through encryption. Similarly, we first hash larger data to obtain a digest, which is then signed. In practice, padding the digest before signing is also necessary.
- Although the principle of RSA is not complicated, we should avoid attempting to implement it ourselves and instead rely on mature cryptographic libraries whenever possible, such as the crypto library provided by Node.js.

Buy me a cup of coffee if this article has been helpful to you:

* EVM: `0x8f7BEE940b9F27E8d12F6a4046b9EC57c940c0FA`