Simplicity is prerequisite for reliability––Edsger W. Dijkstra
A collection of short pedagogic programs introducing data structures and computational math puzzles. Implement hash tables, RSA encryption, compiler functions and blockchain technology.
To run the programs, you will need to have installed Node.js and npm (Node.js package manager) on your local machine.
Programs are written in TypeScript. For the latest version, run:
npm install -g typescript
To run any simple-program, first compile into JavaScript using
tsc [simple-*].ts
And then run:
node [simple-*].js
A simple blockchain in 90 lines.
To use library, import simple-blockchain
and create a new Blockchain
object with a difficulty integer as its constructor argument.
- To add new blocks to the Blockchain, call the class method
createNewBlock
with an array of Transactions and an optional proof of work as its arguments - To add transactions to an existing block, call the class method
addTransaction
with a Transaction and an optional Block; if no Block is passed, the method will add the transaction to the last block in the chain - To mine an existing block, call the class method
mine
; if no Block is passed, the method will mine the last block in the chain - To verify the proof of work of a Block, call the class method
verifyProofOfWork
; if no Block is passed, the method will verify the last block in the chain - To verify the validity of the Blockchain, call the class method
verifyBlockchain
- The consensus is that the longest chain of Blocks is the valid Blockchain
Requires crypto-js library (MIT License). To install dependency, run:
npm install crypto-js
References: "But how does bitcoin actually work?"––3blue1brown
A simple compiler in 64 lines.
To use library, import function compile
from simple-compiler
.
Takes only one argument: a line of code, i.e. a string
, written in simple-math syntax (very short documentation
available below), and converts it to calculator-executable math.
Note: Although it does not convert the instructions into machine-readable code (1s and 0s) like a traditional compiler, it accomplishes the same elementary task: taking a line written in a higher-level programming language and converting it into lower-level code for a computing machine––in this case, a simple calculator.
Very short simple-math Syntax Documentation
- Each line in simple-math is an expression
- Each expression is either a floating point or a function call with one or more expressions as its arguments
- A function call is done by enclosing in parenthesis the function name followed by its arguments
- There are 5 supported functions: "sum", "dot", "div", "exp", and "mod"
Regex shortcuts:
num := -?[0-9]*.?[0-9]+
fnct := sum | dot | div | exp | mod
expr := num | ( fnct expr+ )
Examples:
- "(sum 1 2 3)" => "(1+2+3)"
- "(dot 0.5 (div 7 1.4))" => "(0.5*(7/1.4))"
- "(exp 2 (mod (dot 3 -6) 4))" => "(2**((3*(-6))%4))"
A simple hashtable in 83 lines.
To use library, import simple-hashtable
and create a new Hashtable
object.
Class methods insert
, search
, and delete
allow for insertion, searching, and deletion of elements of type Pair
inside
hash table.
References: "Notes on Data Structures and Programming Techniques, 5.4 Hash tables" (CPSC 223, Spring 2020)––James Aspnes
A simple RSA encryption program in 87 lines.
To use library, import simple-rsa
and create a new RSA
object. When creating a new RSA(e: bigint?, p1: bigint?, p2: bigint?)
, it will generate a new public encryption key and new private prime factors, if none are provided in its constructor.
The RSA implementation is comprised of the following: a public modulo n
, a public encryption key e
, a private decryption key d
, and an inbox containing any encripted messages.
- To add a message to the inbox to be encrypted, call the class method
addToInbox
that takes one argument: a message of typeBigInt
- To view the inbox and its encrypted content, call the class method
viewInbox
- To decrypt the entire inbox, call the class method
decryptInbox
(the method will also empty the inbox)
Note: This specific implementation of the RSA algorithm uses BigInt
(see Documentation). This is done in an attempt to avoid adding unnecesarry complexity to the contents of the program and allow for the generating larger prime numbers with ease. However, for real cryptographic applications, it is recommended to avoid using BigInt
due to operations not being constant-time (see BigInt
documentation under "Usage recommendations > Cryptography" and "A beginner's guide to constant-time cryptography")
The library also includes an abstract class RSAMath
, which provides the mathematical functions necessary for the implementation of the RSA algorithm.
- The static method
generateEncryptionKey
takes an argument:phi
, and generates a small encryption key that does not share any prime factors withphi
- The static method
generatePrime
takes two optional arguments:bitSize
andbitRange
, and generates a random prime number ofbitSize ± bitRange
bits. By defaultbitSize = 42
andbitRange = 4
- The static method
simplePrimalityTest
takes an argument:n
, and returns whethern
is prime or not - The static method
modularExponentiation
takes three arguments:a
,b
, andm
, and returns the result of the calculationa^b mod m
- The static method
modularInverse
takes two arguments:e
andm
, and returns the inverse ofe
, i.e.d
such thated = de = 1 (mod m)
, or-1n
if such a number does not exist - The static method
extendedEuclidianAlgorithm
takes two arguments:a
andb
, and returns the solution to the equationay + bx = gcd(a, b)
in an array of three elements:[y, x, gcd(a, b)]
References: "Notes on Discrete Mathematics, 8.7. RSA encryption (CPSC 202, Spring 2020)––James Aspnes"
Additional resources: "Modular multiplicative inverse", "Bézout's identity and extended GCD algorithm", "Euler's theorem"