Given an RSA key (n,e,d), construct a program to encrypt and decrypt plaintext messages strings.

Background

RSA code is used to encode secret messages. It is named after Ron Rivest, Adi Shamir, and Leonard Adleman who published it at MIT in 1977. The advantage of this type of encryption is that you can distribute the number “



n


{\displaystyle n}

” and “



e


{\displaystyle e}

” (which makes up the Public Key used for encryption) to everyone. The Private Key used for decryption “



d


{\displaystyle d}

” is kept secret, so that only the recipient can read the encrypted plaintext.

The process by which this is done is that a message, for example “Hello World” is encoded as numbers (This could be encoding as ASCII or as a subset of characters 



a
=
01
,
b
=
02
,
.
.
.
,
z
=
26


{\displaystyle a=01,b=02,...,z=26}

). This yields a string of numbers, generally referred to as "numerical plaintext", “



P


{\displaystyle P}

”. For example, “Hello World” encoded with a=1,...,z=26 by hundreds would yield 



08051212152315181204


{\displaystyle 08051212152315181204}

.

The plaintext must also be split into blocks so that the numerical plaintext is smaller than 



n


{\displaystyle n}

 otherwise the decryption will fail.

The ciphertext, 



C


{\displaystyle C}

, is then computed by taking each block of 



P


{\displaystyle P}

, and computing

 



C
≡

P

e



mod


n


{\displaystyle C\equiv P^{e}\mod n}


Similarly, to decode, one computes

 



P
≡

C

d



mod


n


{\displaystyle P\equiv C^{d}\mod n}

 
To generate a key, one finds 2 (ideally large) primes 



p


{\displaystyle p}

 and 



q


{\displaystyle q}

. the value “



n


{\displaystyle n}

” is simply: 



n
=
p
×
q


{\displaystyle n=p\times q}

.
One must then choose an “



e


{\displaystyle e}

” such that 



gcd
(
e
,
(
p
−
1
)
×
(
q
−
1
)
)
=
1


{\displaystyle \gcd(e,(p-1)\times (q-1))=1}

. That is to say, 



e


{\displaystyle e}

 and 



(
p
−
1
)
×
(
q
−
1
)


{\displaystyle (p-1)\times (q-1)}

 are relatively prime to each other.

The decryption value 



d


{\displaystyle d}

 is then found by solving

 



d
×
e
≡
1

mod


(
p
−
1
)
×
(
q
−
1
)


{\displaystyle d\times e\equiv 1\mod (p-1)\times (q-1)}


The security of the code is based on the secrecy of the Private Key (decryption exponent) “



d


{\displaystyle d}

” and the difficulty in factoring “



n


{\displaystyle n}

”. Research into RSA facilitated advances in factoring and a number of factoring challenges. Keys of 768 bits have been successfully factored. While factoring of keys of 1024 bits has not been demonstrated, NIST expected them to be factorable by 2010 and now recommends 2048 bit keys going forward (see Asymmetric algorithm key lengths or NIST 800-57 Pt 1 Revised Table 4: Recommended algorithms and minimum key sizes).

Summary of the task requirements:

 Encrypt and Decrypt a short message or two using RSA with a demonstration key. 
 Implement RSA do not call a library.
 Encode and decode the message using any reversible method of your choice (ASCII or a=1,..,z=26 are equally fine). 
 Either support blocking or give an error if the message would require blocking)
 Demonstrate that your solution could support real keys by using a non-trivial key that requires large integer support (built-in or libraries). There is no need to include library code but it must be referenced unless it is built into the language. The following keys will be meet this requirement;however, they are NOT long enough to be considered secure:
 n = 9516311845790656153499716760847001433441357
 e = 65537
 d = 5617843187844953170308463622230283376298685
 Messages can be hard-coded into the program, there is no need for elaborate input coding.
 Demonstrate that your implementation works by showing plaintext, intermediate results, encrypted text, and decrypted text.


 Warning
Rosetta Code is not a place you should rely on for examples of code in critical roles, including security.
Cryptographic routines should be validated before being used.
For a discussion of limitations and please refer to Talk:RSA_code#Difference_from_practical_cryptographical_version.

#lang racket
(require math/number-theory)
(define-logger rsa)
(current-logger rsa-logger)
 
;; -| STRING TO NUMBER MAPPING |----------------------------------------------------------------------
(define (bytes->number B) ; We'll need our data in numerical form ..
  (for/fold ((rv 0)) ((b B)) (+ b (* rv 256))))
 
(define (number->bytes N) ; .. and back again
  (define (inr n b) (if (zero? n) b (inr (quotient n 256) (bytes-append (bytes (modulo n 256)) b))))
  (inr N (bytes)))
 
;; -| RSA PUBLIC / PRIVATE FUNCTIONS |----------------------------------------------------------------
;; The basic definitions... pretty well lifted from the text book!
(define ((C e n) p)
  ;; Just do the arithmetic to demonstrate RSA...
  ;; breaking large messages into blocks is something for another day.
  (unless (< p n) (raise-argument-error 'C (format "(and/c integer? (</c ~a))" n) p))
  (modular-expt p e n))
 
(define ((P d n) c)
  (modular-expt c d n))
 
;; -| RSA KEY GENERATION |----------------------------------------------------------------------------
;; Key generation
;; Full description of the steps can be found on Wikipedia
(define (RSA-keyset function-base-name)
  (log-info "RSA-keyset: ~s" function-base-name)
  (define max-k 4294967087)
  ;; I'm guessing this RNG is about as cryptographically strong as replacing spaces with tabs.
  (define (big-random n-rolls)
    (for/fold ((rv 1)) ((roll (in-range n-rolls 0 -1))) (+ (* rv (add1 max-k)) 1 (random max-k))))
  (define (big-random-prime)
    (define start-number (big-random (/ 1024 32)))
    (log-debug "got large (possibly non-prime) number, finding next prime")
    (next-prime (match start-number ((? odd? o) o) ((app add1 e) e))))
 
  ;; [1] Choose two distinct prime numbers p and q.
  (log-debug "generating p")
  (define p (big-random-prime))
  (log-debug "p generated")
  (log-debug "generating q")
  (define q (big-random-prime))
  (log-debug "q generated")
  (log-info "primes generated")
 
  ;; [2] Compute n = pq.
  (define n (* p q))
 
  ;; [3] Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1),
  ;;                    where φ is Euler's totient function.
  (define φ (- n (+ p q -1)))
 
  ;; [4] Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are
  ;;     coprime. ... most commonly 2^16 + 1 = 65,537 ...
  (define e (+ (expt 2 16) 1))
 
  ;; [5] Determine d as d ≡ e−1 (mod φ(n)); i.e., d is the multiplicative inverse of e (modulo φ(n)).
  (log-debug "generating d")
  (define d (modular-inverse e φ))
  (log-info "d generated")
  (values n e d))
 
;; -| GIVE A USABLE SET OF PRIVATE STUFF TO A USER |--------------------------------------------------
;; six values: the public (encrypt) function (numeric) 
;;             the private (decrypt) function (numeric)
;;             the public (encrypt) function (bytes) 
;;             the private (decrypt) function (bytes)
;;             private (list n e d)
;;             public (list n e)
(define (RSA-key-pack #:function-base-name function-base-name)
  (define (rnm-fn f s) (procedure-rename f (string->symbol (format "~a-~a" function-base-name s))))
  (define-values (n e d) (RSA-keyset function-base-name))
  (define my-C (rnm-fn (C e n) "C"))
  (define my-P (rnm-fn (P d n) "P"))
  (define my-encrypt (rnm-fn (compose number->bytes my-C bytes->number) "encrypt"))
  (define my-decrypt (rnm-fn (compose number->bytes my-P bytes->number) "decrypt"))
  (values my-C my-P my-encrypt my-decrypt (list n e d) (list n e)))
 
;; -| HEREON IS JUST A LOAD OF CHATTY DEMOS |---------------------------------------------------------
(define (narrated-encrypt-bytes C who plain-text)
  (define plain-n (bytes->number plain-text))
  (define cypher-n (C plain-n))
  (define cypher-text (number->bytes cypher-n))
  (printf #<<EOS
~a wants to send plain text: ~s
  as number: ~s
  cyphered number: ~s
sent by ~a over the public interwebs:
~s
...
 
 
EOS
          who plain-text plain-n cypher-n who cypher-text)
  cypher-text)
 
(define (narrated-decrypt-bytes P who cypher-text)
  (define cypher-n (bytes->number cypher-text))
  (define plain-n (P cypher-n))
  (define plain-text (number->bytes plain-n))
  (printf #<<EOS
...
~s
  received by ~a
  as number: ~s
  decyphered (with P) number: ~s
decyphered text:
~s
 
 
EOS
          cypher-text who cypher-n plain-n plain-text)
  plain-text)
 
;; ENCRYPT AND DECRYPT A MESSAGE WITH THE e.g. KEYS
(define-values (given-n given-e given-d)
  (values 9516311845790656153499716760847001433441357
          65537
          5617843187844953170308463622230283376298685))
 
;; Get the keys specific RSA functions
(for ((message-text (list #"hello world" #"TOP SECRET!")))
  (define Bobs-public-function (C given-e given-n))
  (define Bobs-private-function (P given-d given-n))
  (define cypher-text (narrated-encrypt-bytes Bobs-public-function "Alice" message-text))
  (define plain-text (narrated-decrypt-bytes Bobs-private-function "Bob" cypher-text))
  plain-text)
 
;; Demonstrate with larger keys.
;; (And include a free recap on digital signatures, too)
(define-values (A-pub-C A-pvt-P A-pub-encrypt A-pvt-decrypt A-pvt-keys A-pub-keys)
  (RSA-key-pack #:function-base-name 'Alice))
(define-values (B-pub-C B-pvt-P B-pub-encrypt B-pvt-decrypt B-pvt-keys B-pub-keys)
  (RSA-key-pack #:function-base-name 'Bob))
 
;; Since p and q are random, it is possible that message' = "message modulo {A,B}-key-n" will be too
;; big for "message' modulo {B,A}-key-n", if that happens then I run the program again until it
;; works. Strictly, we need blocking of the signed message -- which is not yet implemented.
(let* ((plain-A-to-B #"Dear Bob, meet you in Lymm at 1200, Alice")
       (signed-A-to-B         (A-pvt-decrypt plain-A-to-B))
       (unsigned-A-to-B       (A-pub-encrypt signed-A-to-B))
       (crypt-signed-A-to-B   (B-pub-encrypt signed-A-to-B))
       (decrypt-signed-A-to-B (B-pvt-decrypt crypt-signed-A-to-B))
       (decrypt-verified-B    (A-pub-encrypt decrypt-signed-A-to-B)))
  (printf
   #<<EOS
Alice wants to send ~s to Bob.
She "encrypts" with her private "decryption" key.
(A-prv msg) -> ~s
Only she could have done this (only she has the her private key data) -- so this is a signature on the
message. Anyone can verify the signature by "decrypting" the message with the public "encryption" key.
(A-pub (A-prv msg)) -> ~s
But anyone is able to do this, so there is no privacy here.
Everyone knows that it can only be Alice at Lymm at noon, but this message is for Bob's eyes only.
We need to encrypt this with his public key:
(B-pub (A-prv msg)) -> ~s
Which is what gets posted to alt.chat.secret-rendezvous
Bob decrypts this to get the signed message from Alice:
(B-prv (B-pub (A-prv msg))) -> ~s
And verifies Alice's signature:
(A-pub (B-prv (B-pub (A-prv msg)))) -> ~s
Alice genuinely sent the message.
And nobody else (on a.c.s-r, at least) has read it.
 
KEYS:
 Alice's full set: ~s
 Bob's full set: ~s
EOS
   plain-A-to-B signed-A-to-B unsigned-A-to-B crypt-signed-A-to-B decrypt-signed-A-to-B
   decrypt-verified-B A-pvt-keys B-pvt-keys))