python code

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

Part II $($RSA Cryptosystem$)$ Problem $7($Keygen Program$)$

Write a program called keygen.py that accepts lo $($int$)$ and hi $($int$)$ as command$-$line arguments, generates public$/$private keys $($n$,$e$,$d$),$ and writes the keys to standard output, separated by a space

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

$ python$3$ keygen.py $50100359917592839$

Part II $($RSA Cryptosystem$)$ Problem $7($Keygen Program$)$

Accept lo $($int$)$ and hi $($int$)$ as command$-$line arguments Get public$/$private keys as a tuple

Write the three values in the tuple, separated by a space