RSA_simple.R

# work-in-progress
# based on https://www.di-mgt.com.au/rsa_alg.html

library(gmp)

# returns a random odd value. The first bit and last bit is 1.
random_value <- function(how_many_bits = 512) {
	hex_values <- ceiling(how_many_bits/4)-4
        if (hex_values < 1) stop("more bits please.")
        result <- c(
			sample(c("8","9","a","b","c","d","e","f"), 1),
			sample(c(0:9,c("a","b","c","d","e","f")), hex_values, replace = TRUE),
			sample(c("1","3","5","7","9","b","d","f"), 1))
	as.bigz(paste0(c("0x",result), collapse = ""))
}

find_prime <- function(how_many_bits = 512) {
	while (TRUE) {
		candidate <- random_value(how_many_bits)
		tries <- 0
		while (2*tries < how_many_bits) {
			tries <- tries + 1
			if (isprime(candidate) > 0) return(candidate)
			candidate <- candidate + 2
			
		}
	}
}

modular_multiplicative_inverse <- function(e, n) {
	e_gcd <- extended_gcd(e, n)
	if (e_gcd$x < 0) e_gcd$x <- e_gcd$x + n
	e_gcd$x
}

# https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
extended_gcd <- function(a, b) {
	x <- 0 ; lastx <- 1
	y <- 1 ; lasty <- 0
	
	while (b != 0) {
		quotient <- a %/% b
		r <- a %% b
		a <- b
		b <- r

		x_saved <- x
		x <- lastx - quotient*x
		lastx <- x_saved

		y_saved <- y
		y <- lasty - quotient*y
		lasty <- y_saved
	}
	return(list(x = lastx, y = lasty))
}
	
rsa_generate_keys <- function(how_many_bits = 512) {
	p <- find_prime(how_many_bits / 2)
	q <- find_prime(how_many_bits / 2)
	while (p == q) {
		q <- find_prime(how_many_bits / 2)
	}
	n <- p*q
	phi <- lcm.bigz((p-1),(q-1))
	e <- 65537
	d <- modular_multiplicative_inverse(e, phi)
	return(list(public_key = list(n = n, e = e), private_key = list(n = n, d = d)))
}

rsa_encrypt <- function(message, n, e) { return(powm(message,e,n)) }
rsa_decrypt <- function(cipher, n, d) { return(powm(cipher,d,n)) }

keys <- rsa_generate_keys(how_many_bits = 64)
rsa_encrypt(100, keys$public_key$n, keys$public_key$e)
Big Integer ('bigz') :
[1] 70288726484816

rsa_decrypt(70288726484816, keys$private_key$n, keys$private_key$d)
Big Integer ('bigz') :
[1] 100

keys
$public_key
$public_key$n
Big Integer ('bigz') :
[1] 151440469274741

$public_key$e
[1] 65537

$private_key
$private_key$n
Big Integer ('bigz') :
[1] 151440469274741

$private_key$d
Big Integer ('bigz') :
[1] 11490266682593