Post-Quantum Crypto Library Installation + Justifying Algorithm Selection (Unfinished)
Published: 2021-03-20 12:07:34

This write-up is to be included alongside the general Foobar Protocol documentation to illustrate the relative ease with which one can download & install every single pq-crypto contestant for the [NIST post-quantum competition](https://csrc.nist.gov/projects/post-quantum-cryptography). 

There will be a separate write-up that explains **which algorithms** will be used for the project (and why). 

However, to mitigate suspense: 

1. 'SIKE' will be used as the long-term PKI algorithm. It was a Round 3 finalist and also produces the smallest signature size out of all other pq-crypto algos (by a long stretch; \<300 bytes now )
2. ['SIKE' is constructed by taking the supersingular isogeny of two derived elliptic curves](https://eprint.iacr.org/2019/499) ; so, this keeps us 'home' with a concept we're generally familiar with (*nearly every cryptocurrency the author can think of utilizes either an Edwards' curve or an NIST Elliptic Curve algorithm as its address generation scheme*)

To that point about the key sizes above, the following figure from a recent published study outlining efficiency improvements in the algorithm's implementation is provided below: 

![](https://notes.librehash.org/uploads/upload_b4cb07a7a4abda5b1e422ea852f038b4.png)

> **source**: *https://sike.org/files/SIDH-spec.pdf*

'SIKEp751' and 'SIKEp610' were both outlined above because a final decision on **which** will ultimately be chosen has not been made yet at the time of writing. 

More information must be gleaned to assess what trade-offs there are in speed / performance one would suffer by opting for the more secure (p751) instantiation of the algorithm (performance degradation due to increased overhead from additional cryptographic operations). 

In either case, the **compressed version of the algorithm will be chosen** (for obvious reasons; there are no meaningful reductions in security / performance we suffer for opting to go with the 'compressed' version of the algorithm). 

Before we delve into key size comparisons, its worth noting that other pq-schemes have signature / pubkey (privkey) sizes in excess of several KBs in some cases. 

*Alternative Research Outlines a Proposed Optimization With Greater Key Size Reductions* 

In a study published in 2019 by researchers from Microsoft and '*Digital Security Group*', titled, ['*Dual Isogenies and Their Application to Public-Key Compression for Isogeny-based Cryptography*'](https://eprint.iacr.org/2019/499.pdf), researchers outlined a different proposed optimization for the algorithm (SIKE) that provided even smaller signatures. 

Specifically, the study notes: 

> "Compression has been included in the Round 2 submission of SIKE and, along with the introduction of new parameter sets, has enabled public keys of **merely 196 bytes** and **ciphertexts of only 209 bytes for NIST level 1**"

The 'level 1' designation from the NIST mentioned in the excerpt above refers to the theoretical bit-strength of the algorithm assuming a quantum-capable adversary. 

![](https://notes.librehash.org/uploads/upload_2f195b1d2b3ccf76377531569f022601.png)

> **source**: *https://eprint.iacr.org/2019/711.pdf* 

**Addressing the Size of the 'Secret Key' / 'Public Key' / 'Ciphertext' / 'Shared Secret'** 

Bitcoin uses secp256k1 (ecdsa). Compressed raw public keys are 33 bytes (one additional byte added because the pubkey coordinate / data-point is a signed integer [must specify whether the 'y' is north or south of the 'zero line']). 

This means that: 

- The 'p610' SIKE iteration's private key is 15x the size of the secp256k1 private key size,  its public key is 8.5x the secp256k1 pubkey size, and  

**Alternative Library** = https://libpqcrypto.org/install.html

- Instructions are for Debian / Ubuntu systems (that's fine; don't want to fuck around or fiddle w Arch for this anyway)

- Needs to be installed before any Python integration can be completed 

- Once this is done, the necessary steps can be added to the default container instances for Docker (for the server being instantiated so that we can benefit from PQCrypto in all situations ; no reason not to enjoy the benefits that it provides us)  


1. `sudo apt install build-essential` 

2. `sudo apt install libssl-dev` 

3. `sudo apt install libgmp-dev` 

4. `sudo apt install python3` # will already be downloaded at that point

> "Check that `df /home/` shows at least 300000 1K-blocks available, and that `df -i /home/` shows at least 30000 inodes free. Currently a typical compile-and-test run uses about 200MB and about 15000 inodes."

After the above precaution has been taken, craft the following script: 

```
#!/bin/sh

# Before proceeding, have to create a 'libpqcrypto' system user 

sudo adduser --disabled-password --gecos libpqcrypto libpqcrypto

# login to the newly created user 

su - libpqcrypto 

# Run these commands as said user (in one script) 

touch pqinstall.sh # (to create the file) 

cat <<EOF >>pqinstall.sh 
wget -m https://libpqcrypto.org/libpqcrypto-latest-version.txt
version=$(cat libpqcrypto.org/libpqcrypto-latest-version.txt)
wget -m https://libpqcrypto.org/libpqcrypto-$version.tar.gz
tar -xzf libpqcrypto.org/libpqcrypto-$version.tar.gz
cd libpqcrypto-$version
ln -s $HOME link-build
ln -s $HOME link-install 
EOF
```

From that point, we run `chmod +x pqinstall.sh`. Afterward, we execute the `pqinstall.sh` file. 

When the script runs its course, we run `./do` ["compile, test and install; this is going to take a considerable amount of time since its going to compile, test and install over 75 diff cryptographic algorithms"]

Once this is done we can run the `exit` command from there (this could probably all be compiled in one script; need to look back to see what they're referring to with the 'do' command // a simple `cat do` should be sufficient)

**Downloading 'GMP'** 

> what the fuck are they referring to with this? 

` GMP header files: sudo apt install libgmp-dev`

^^^ (this was noted at the beginning of this write-up; just wasn't paying attention / this should be installed and ready to go & OpenSSL comes pre-compiled with any regular Ubuntu / Debian instance)

### Post libpqcrypto installation: CLI Setup 

(URL = https://libpqcrypto.org/command.html)

Once the library has been installed successfully, it suggests adding `/home/libpqcrypto/command` to the 'PATH' ; need to ensure that this is actually where the library was installed at 

> *this will be successful if we begin the installation process from the root home directory of the newly created libpqcrypto user* 

Specifically, the command is: `export PATH=$PATH:/home/libpqcrypto/command`

^ Preferably this is added to the `~/.bashrc` file. 

**Additional Information** 

Based on what I'm reading, it appears that the '/home/libpqcrypto/command' directory will contain binaries that can be directly called. 

This is evidenced by the additional note: 

> ""You can indstead put /home/libpqcrypto/command/ in front of each command name; but this does not work for the pq-*-all wrappers."

**Signature Generation Example** (this boilerplate applies to for all signatures)

1. Generating a new keypair: `pq-keypair-sphincsf256sha256 5>publickey 9>secretkey` (what the fuck do the '5' and '9' mean?)

2. Signing a message: `pq-sign-sphincsf256sha256 <message 8\<secretkey \>signedmessage`

3.  To verify a signed message and recover the original message: `pq-open-sphincsf256sha256 <signedmessage 4<publickey >message`

4. *If verification fails*, `pq-open-sphincsf256sha256` *produces an empty output, prints an error message on stderr, and exits 100*

**Encryption Examples** (boilerplate applies for all encryption-based pq algos) 

> *"There is a unified interface for all encryption systems"*

1. To generate a key pair: `pq-keypair-mceliece8192128 5>publickey 9>secretkey`
2. To encrypt a message: `pq-encrypt-mceliece8192128 <message 4<publickey >ciphertext`
3. To decrypt a ciphertext and recover the original message: `pq-decrypt-mceliece8192128 <ciphertext 8<secretkey >message`

#### Python Instantiation 

Relevant information and commands included here (this is what we were looking for) = https://libpqcrypto.org/python.html

Just need to add `import pqcrypto` at the beginning of scripts after exporting the 'Pythonpath' (this is something that's going to be created as a subdirectory underneath the 'libqcrypto' project folder ; or run the command:

`export PYTHONPATH="/home/libpqcrypto/python${PYTHONPATH+:$PYTHONPATH}"` (this code is meant to be all on one line ; formatting might be a little funky) 

All of the relevant information is at the URL link provided above (just need to modify the boilerplate scripts in accordance with whichever post-quantum algorithm that I'm looking to use). 

> **Sidenote**: *If REPL allowed users to 'sudo' within the containers, then I could provide an embedded instance that would allow people to run various code designed to produce the signatures, associated public / private key pairs accompanying various pq-crypto algorithms etc. - but, alas, they restrict this feature; so, I can't* [**perhaps I could go with Katacoda**]