An inefficient/insecure implementation of RSA using very small numbers. Meant for demonstration of the underlying math and using the same variable names as in Stalling's "Cryptography and Network Security" 6th edition.

smallrsa.go

package main

import (
	"fmt"
)

type RSA struct {
	p          int
	q          int
	e          int
	printedN   bool
	printedPhi bool
	printedD   bool
}

func main() {
	a := RSA{p: 3, q: 11, e: 7}
	ciphertext := a.Encrypt(5)
	a.Decrypt(ciphertext)

	b := RSA{p: 5, q: 11, e: 3}
	ciphertext = b.Encrypt(9)
	b.Decrypt(ciphertext)

	c := RSA{p: 7, q: 11, e: 17}
	ciphertext = c.Encrypt(8)
	c.Decrypt(ciphertext)

	d := RSA{p: 11, q: 13, e: 11}
	ciphertext = d.Encrypt(7)
	d.Decrypt(ciphertext)

	e := RSA{p: 17, q: 31, e: 7}
	ciphertext = e.Encrypt(2)
	e.Decrypt(ciphertext)
}

func (r *RSA) N() int {
	answer := r.p * r.q
	if !r.printedN {
		fmt.Printf("n = p * q\n")
		fmt.Printf("%d = %d * %d\n", answer, r.p, r.q)
		r.printedN = true
	}

	return answer
}

func (r *RSA) Phi() int {
	answer := (r.p - 1) * (r.q - 1)
	if !r.printedPhi {
		fmt.Printf("ϕ(n) = (p - 1)(q - 1)\n")
		fmt.Printf("%d = (%d - 1)(%d - 1)\n", answer, r.p, r.q)
		r.printedPhi = true
	}

	return answer
}

func (r *RSA) D() int {
	ϕ := r.Phi()
	answer := FindD(ϕ, r.e)
	if !r.printedD {
		fmt.Printf("d ≡ e^-1(mod ϕ(n))\n")
		fmt.Printf("%d ≡ %d^-1(mod %d)\n", answer, r.e, ϕ)
		r.printedD = true
	}

	return answer
}

func (r RSA) Encrypt(message int) int {
	n := r.N()
	fmt.Printf("encrypting with public key\n")
	fmt.Printf("PU = {e, n} = {%d, %d}\n", r.e, n)
	if n <= message {
		panic("n must be larger than the message")
	}
	answer := ModularExp(message, r.e, n)
	fmt.Printf("C = M^e mod n\n")
	fmt.Printf("%d = %d^%d mod %d\n", answer, message, r.e, n)

	return answer
}

func (r RSA) Decrypt(ciphertext int) int {
	n := r.N()
	d := r.D()
	fmt.Printf("decrypting with private key\n")
	fmt.Printf("PR = {d, n} = {%d, %d}\n", d, n)
	message := ModularExp(ciphertext, d, n)
	fmt.Printf("M = C^d mod n\n")
	fmt.Printf("%d = %d^%d mod %d\n\n", message, ciphertext, d, n)

	return message
}

func GCD(a, b int) int {
	for b != 0 {
		t := b
		b = a % b
		a = t
	}
	return a
}

func ExtGCD(a, b int) (int, int, int, int) {
	prevx, x := 1, 0
	prevy, y := 0, 1
	for b != 0 {
		q := a / b
		x, prevx = prevx-q*x, x
		y, prevy = prevy-q*y, y
		a, b = b, a%b
	}
	return a, prevx, prevy, y
}

// see also inverse(a, n) at https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
func FindD(ϕ, e int) int {
	_, _, d, y := ExtGCD(ϕ, e)
	if d < 0 {
		d = y + d
	}
	return d
}

func ModularExp(base, exponent, modulo int) int {
	base = base % modulo
	result := 1
	for i := 0; i < exponent; i++ {
		result = (result * base) % modulo
	}
	return result
}