In this assignment, you will implement the RSA algorithm in Python. You will learn how modu$-$ lar arithmetic can be leveraged to enforce security in a PKI system. Unlike the shift cipher you$$ve encountered in class. This means that the encryption key used to secure a message is different from the decryption key, which is kept confi$-$ dential and known only to the intended recipient. The computational hardness of this algorithm is prime factorization. To decrypt the messages, an adversary needs to recover the prime numbers p and q from the common modulus n $=$ p $$ q$.$ While this is far more secure than a symmetric key encryp$-$ tion technique like the shift cipher, there are many known vulnerabilities in RSA. However, they are beyond the scope of this course. In class, you learned how to encrypt integers using modular exponentiation, however, in this program$-$ ming assignment, you will be encrypting strings. For example, in the string $$hello world!$,$ we need to encrypt the space and special character $!$ in addition to the characters. Specifically, $$ Your encryption$/$decryption should support all characters corresponding to ASCII values in the range $32-128($inclusive$).$ Your encryption$/$decryption should support $$chunking$$ i$.$e$.,$ instead of encrypting$/$decrypting each character of a string using RSA, you will split the string into chunks $($substrings$)$ and then encrypt$/$decrypt those chunks. For example, with a chunk size of $2,$ the string $$hello$$ is split as $$he$,$ll$,$ o$.$ Observe that we apply the necessary padding to generate chunks of equal size. Without chunking, an individual character would be mapped to a unique value modulo n $($for a given public modulus n$).$ You need to map $$chunks$$ to unique values according to the following strategy: Treat each chunk as a base$-$n number and convert it to decimal. If your chunk has k characters, a chunk could have a total of nk values $($more secure$!).$ Based on this strategy, what would you do after decrypting the chunks in order to recover the plain$-$ text message? You need to figure out the answer to this question to complete the decryption function. $1\mathrm{.}1$ Function Descriptions You need to implement the following functions: $$ generate prime: This function accepts a value n and generates a random n$$bit prime number. We will test your function and verify that it can generate large prime numbers $($e$.$g$.,1024-$bit prime numbers$)$ within a reasonable amount of time. If you try to brute force the prime number generation, you will not receive points for this. Consider using a primality test to implement the prime number generation process $($e$.$g$.,$ Fermat$$s primality test$).$ CMPSC $360,$ Fall $2024,$ Extra Credit $1$ generate keypair: This function accepts two distinct prime numbers and generates the public and private key pairs. The format MUST be of the form $(($n$,$ e$),($n$,$ d$))$ where n is the common modulus, e is the public exponent, and d is the private exponent. If the input integers p and q are invalid, you MUST raise a Value Error exception. Please refer to the class slides and textbook about how to compute these values. $$ chunk to num: This function maps a message chunk $($substring$)$ to a unique value based on the base conversion strategy from section $1.$ The only parameter is the chunk $($substring$).$ num to chunk: Maps a number back to a chunk $($substring$)$ using the base conversion strategy from section $1.$ You will need this to implement the RSA decryption process. The parameters are the number and the chunk size. $$ rsa encrypt: The RSA encryption function that encrypts a message using a public key and specified chunk size. $$ rsa decrypt: The RSA decryption function that decrypts a message using a private key and specified chunk size. You will need to write helper functions to complete the functions provided in the starter code. Note that the first two functions are fairly straightforward in the sense that they directly operate on integers, but you$$ll need to implement the code to break strings according to the provided chunking scheme. Here are the functionalities that you will need to implement as helper functions: $$ Modular Exponentiation: Recall that encryption and decryption are implemented by computing modular exponentiation problems $($see lecture slides for more details$).$ You should implement your own modular exponentiation computation that operates on integers. $$ Modular Inverse: You need to implement a helper function $($or incorporate this code in the starter code$)$ to find the private key $$ is prime function: This can optionally be implemented as a helper function or something you directly write in the generate prime function as part of a primality test. $$ gcd: You will need to write your own gcd function given two numbers. $($Hint: Which part of the RSA encryption process needs this?$)$ Note: When choosing the value of your public exponent $,$ please choose the smallest value of e $>2$ for a given k