The RSA cryptosystem involves three integers n$,$ e$,$ and d that satisfy certain mathematical properties The public key $($n$,$e$)$ is made public on the Internet, while the private key $($n$,$d$)$ is only known to Bob

If Alice wants to send Bob a message x in $[0,$n$),$ she encrypts it using the function E$($x$)=$ xe mod n$,$ where n $=$ pq for two distinct large prime numbers p and q chosen at random, and e is a random prime number less than

m $=($p $1)($q $1)$ such that e does not divide m

Example: suppose p $=47$ and q $=79$; then n $=3713$ and m $=3588$; further suppose e $=7$; if Alice wants to send the message x $=2020$ to Bob, she encrypts it as E$(2020)=20207$ mod $3713=516$

When Bob receives the encrypted message y$,$ he decrypts it using the function D$($y$)=$ yd mod n$,$ where d in $[1,$ m$)$ is an integer that satisfies the equation ed mod m $=1$

Continuing the example above, if d $=2563,$ then when Bob receives the encrypted message y $=516$ from Alice, he decrypts it to recover the original message as D$(516)=5162563$ mod $3713=2020$

Part II $($RSA Cryptosystem$)$ Problem $6($RSA Library$)$

Implement a library called rsa.py that provides functions needed for developing the RSA cryptosystem and supports the following API

$2$ rsa

keygen$($lo$,$ hi$)$ generates and returns the public$/$private keys as a tuple $($n$,$e$,$d$),$ picking prime numbers p and q needed to generate the keys from the interval $[$lo$,$ hi$)$

encrypt$($x$,$ n$,$ e$)$ encrypts x $($int$)$ using the public key $($n$,$ e$)$ and returns the encrypted value

decrypt$($y$,$ n$,$ d$)$ decrypts y $($int$)$ using the private key $($n$,$ d$)$ and returns the decrypted value

bitLength$($n$)$ returns the least number of bits needed to represent n

dec$2$bin$($n$,$ width$)$ returns the binary representation of n expressed in decimal, having the given width and padded with leading zeros

bin$2$dec$($n$)$ returns the decimal representation of n expressed in binary

$$ ~$/$workspace$/$rsa cryptosystem

$ python$3$ rsa.py S encrypt$($S$)=1743$

decrypt $(1743)$ bitLength $(83)$

dec$2$bin $(83)=1010011$ bin$2$dec $(1010011)=83$

$=$ S $=7$

Part II $($RSA Cryptosystem$)$ Problem $6($RSA Library$)$

keygen$($lo$,$ hi$)$

$-$ Get a list of primes from the interval $[$lo$,$hi$)$

$-$ Sample two distinct random primes p and q from that list

$-$ Set n and m to pq and $($p $1)($q $1),$ respectively

$-$ Get a list primes from the interval $[2,$ m$)$

$-$ Choose a random prime e from the list such that e does not divide m $($you will need a loop for this$)-$ Findad in $[1,$m$)$suchthatedmodm$=1($youwillneedaloopforthis$)$

$-$ Return the tuple$1($n$,$ e$,$ d$)$

encrypt$($x$,$ n$,$ e$)$

$-$ Implement the function E$($x$)=$ xe mod n decrypt$($y$,$ n$,$ d$)$

$-$ Implement the function D$($y$)=$ yd mod n

$1$A tuple is like a list, but is immutable. You create a tuple by enclosing comma$-$separated values within matched parentheses, eg$,$ a $=(1,2,3).$ If a is a tuple, a$[$i$]$ is the ith element in it

Part II $($RSA Cryptosystem$)$ Problem $6($RSA Library$)$

$\_$primes$($lo$,$ hi$)$

$-$ Create an empty list

$-$ Foreachp in $[$lo$,$hi$),$ifpisaprime,addptothelist $-$ Return the list

$\_$sample$($a$,$ k$)$

$-$ Create a list b that is a copy $($not an alias$)$ of a $-$ Shuffle the first k elements of b

$-$ Return a list containing the first k elements of b

$\_$choice$($a$)$

$-$ Get a random number r in $[0,$ l$),$ where l is the number of elements in a $-$ Return the element in a at the index r