Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
# 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

This comment has been minimized.

Copy link
Owner Author

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

This comment has been minimized.

Copy link
Owner Author

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.