RSA Encryption

      When I was in high school, students would pass notes to each other in class. I even had an English teacher who was rumored to be having an affair with another teacher, and she would pass notes to him, using a student to deliver the note. Nowadays, students would use their phones and text each other.

      I recently learned a small amount about encryption for a discrete math class. Encryption is the process of scrambling readable data into unreadable code using a secret mathematical key. Cryptography is the general subject of securing information by converting it into unreadable code. During World War II, mathematician Alan Turing played a crucial role in deciphering German messages. Also during World War II, Native American Code Talkers created unbreakable code that enemy cryptographers could never decipher. Today encryption is used in protecting usernames, passwords, and personal data from interception, in many areas such as financial transactions.

      Cryptography is a vast subject. I will limit this essay to the RSA algorithm which is reasonably simple, although it becomes computationally complex for large files. I am also intentionally using small numbers; real RSA uses enormous numbers that make it hard to hack. In fact, RSA is being phased out starting in 2030 due to the threat of future quantum computers.

      Briefly, if you and I agree to use the RSA encryption algorithm, and you have the public key number (n,e) where n is the product of two prime numbers and the private key number d, then I can give you an encrypted message and you can decrypt it.

      Suppose the public key is (n,e) = (33,3) and the private key is d = 7. I have a message, and I encrypt it. Suppose my encrypted message is 3 32 12 3 11 26 32 16 9 21 15 32 28 1 5 31 24 1 32 8 21 24 5 28 . Prior to encryption, 1 is a, 2 is b, etc., 27 is comma, and 32 is space. If you can decrypt this, you will know a secret of my youth :)

      Recall the modulo operator "mod": if x and y are integers, x mod y is the remainder after x/y. For example, 17 mod 12 = 5, because 17/12 = 1 + remainder 5.

      The following is a brief summary of RSA encryption with small numbers:

The recipient has a public key (n,e) that is available to the sender, eg (33,3); and a private key, eg d = 7. (The recipient first chooses primes p and q, eg 3 and 11, and computes n = p*q. The recipient computes Totient φ = (p-1)(q-1)=20, and selects an e that is coprime to φ. Then the recipient performs a modular inverse to solve for d in e*d = 1 mod φ, eg 3*d = 1 mod 20; this can be done using the Extended Euclidean Algorithm, although R package numbers does this as d <- modinv(e,φ) . Here d is 7.)

The sender converts the message from letter to plaintext m, eg m=13; and then from m to encrypted ciphertext = (m^e)(mod n), eg c = (13^3)(mod 33) = 19. (The R expression is (m^e) %% n . However, this may fail if numbers get too large. One alternative is modpower(13,3,33) from the numbers package.)

The recipient decrypts c to recover m, m = (c^d)mod n, eg m = (19^7)(mod 33) = 13.

As an example, if the message is “math”, the plaintext m is (13 1 20 8), the encrypted ciphertext c is (19 1 14 17), the decrypted plaintext m is (13 1 20 8), and the decrypted message is (m a t h).

      Here is my R code.

library(numbers)

# --- RECIPIENT KEYS ---
p <- 3
q <- 11
n <- p * q
phi <- (p - 1) * (q - 1)
e <- 3
d <- modinv(e, phi)

# --- SENDER SIDE ---
m_text <- "MATH"
m_text <- tolower(m_text)
print(paste("The unencrypted message m is:", m_text))

char_vector <- unlist(strsplit(m_text, split = ""))

# Mapping: letters → 1–26, punctuation → custom codes
special_lookup <- c("," = 27, "." = 28, " " = 32)

m_tokens <- sapply(char_vector, function(char) {
  if (char %in% names(special_lookup)) {
    special_lookup[char]
  } else if (char %in% letters) {
    match(char, letters)
  } else {
    stop(paste("Unsupported character:", char))
  }
})

# Encryption
c <- sapply(m_tokens, function(msg_num) modpower(msg_num, e, n))
print(paste("The encrypted ciphertext c is:", paste(c, collapse = " ")))

# Decryption
m_decrypted <- sapply(c, function(cipher_num) modpower(cipher_num, d, n))

# Reverse mapping
result <- sapply(m_decrypted, function(num) {
  if (num %in% special_lookup) {
    names(special_lookup)[special_lookup == num]
  } else {
    letters[num]
  }
})

print(paste("The decrypted ciphertext integers are:", paste(m_decrypted, collapse = " ")))
print(paste("The decrypted message is:", paste(result, collapse = " ")))

End