# 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)) } |
This comment has been minimized.
This comment has been minimized.
$public_key$e $private_key $private_key$d |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
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