{{ message }}

Instantly share code, notes, and snippets.

# MartinMSPedersen/RSA_simple.R

Last active Aug 14, 2019
 # 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)) }

### MartinMSPedersen commented Aug 13, 2019

 `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

### MartinMSPedersen commented Aug 13, 2019

 `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