Answer in Java.

RSA Public-Key Cryptosystem Overview. Write a program to implement the RSA public-key cryptosystem. The RSA (Rivest-Shamir-Adleman) cryptosystem is widely used for secure communication in browsers, bank ATM machines, credit card machines, mobile phones, smart cards, and the Windows operating system. It works by manipulating integers. To thwart eavesdroppers, the RSA cryptosystem must manipulate huge integers (hundreds of digits). The built-in C type int is only capable of dealing with 16 or 32 bit integers, providing little or no security. You will design, implement, and analyze an extended precision arithmetic data type that is capable of manipulating much larger integers. You will use this data type to write a client program that encrypts and decrypts messages using RSA. Note: the training wheels are off on this assignment - you're starting with a blank screen, not our code. This means that you must pay particular attention to the process of building up your program from scratch. Consider carefully how your program should be structured and how you are going to implement the various functions before plunging in. Remember to thoroughly test and debug each function as you write it. The RSA cryptosystem. As discussed in Lecture S1, the RSA public key cryptosystem involves three integer parameters d, e, and n that satisfy certain mathematical properties. The private key (d, n) is known only by Bob, while the public key (e, n) is published on the Internet. If Alice wants to send Bob a message (e.g., her credit card number) she encodes her message as an integer Mthat is between O and n-1. Then she computes: I E(M)= M modn and sends the integer E(M) to Bob. As an example, if M = 2003, e=7, d = 2563, n= 3713, then Alice computes E(M) = 20037 mod 3713 = 129,350,063,142,700.422.208,187 mod 3713 = 746. When Bob receives the encrypted communication E(M), he decrypts it by computing: M=E(Mdmodn. Continuing with the example above, Bob recovers the original message by computing: M=7462563 mod 3713 = 2003. To check your arithmetic, you may use hs, maple, or more Paragraph Styles Part 1 (extended precision arithmetic). The RSA cryptosystem is easily broken if the private key d or the modulus n are too small (e.g., 32 bit integers). The built-in C types int and long can typically handle only 16 or 32 bit integers. Your main challenge is to design, implement, and analyze an extended precision arithmetic data type that can manipulate large (nonnegative) integers. To make it easier to check your work, we recommend working with integers represented using familiar decimal (base 10) notation. (We note that you could achieve superior performance by using a base that is a power of 2, e.g., 256 or 32,768.) Your data type will support the following operations: addition, subtraction, multiplication, division, modular exponentiation, and comparison. You may use the header file xech Data structure. The first and most critical step is to choose an appropriate data structure to represent N-digit extended precision integers. A natural approach is to store each digit as an element in an array. To avoid pointers and memory allocation and deallocation headaches, consider packaging the array up in a struct as follows: #define 100 // maximum number of digits supported #define (2*x + 2) // number of digits allocated typedef struct unsigned char digita): We declare our array to have slightly more than N elements to give ourselves a bit of extra scratch space to store intermediate results - the exact reason for using 2N + I will become clear later. Advanced students (who like pointers) may wish to make it a true first class ADT as in Sedgewick, p. 181. Initialization. Implement a function XRADEBRAL) that takes a string of decimal digits as input, and returns the extended precision integer corresponding to this string. If you represent integers using decimal notation, this will be straightforward, if you use base 2 or 256. consider using Horner's method to do the conversion. Display. Implement a function XrRoosaar that takes an extended precision integer as input and prints out a (decimal) representation of that integer. Addition. Implement the function XReddy). It should take two extended precision integers as input and return a third extended precision integer that is the sum of the two. Implement the method you leamed in grade school. Observe that if a and bare 2N-digit integers, the sum will have at most 2N + 1 digits. Once you've written the above three function, you should be able to write code like: > XP: Paragraph 6 Styles // 1c 123456789 54545454 = a + b XP a, b, c: // declare extended precision variables - EADERSSO"123456789"); - KADAR SERI 54545454"): C - Breda, b); Sabor Reseabic): // print 178002243 Random number generation. Implement a function Xreauso that takes as input an integer n and returns a pseudo-random extended precision integer of at most n digits by choosing each digit at random. This will be useful in debugging the subsequent code, and also in analyzing its complexity. Parity. Implement the function XRaads) that takes an extended precision integer as input and return 1 if and only if it is odd. You may assume that the base is even, so that this amount to checking the parity of the least significant bit. Comparisons. Implement the following functions: XRDESATSEL), XRASERO) and XRe90). They should take two (2N+1)-digit extended precision integers as input and retum 1 if and only if the first integer is greater than (less than, equal to) the second Subtraction. Implement the functions xReyk!). It should take two (2N+1). digit extended precision integers as input and return a third extended precision integer that is the difference of the two. You should check that the first integer is greater than or equal to the second before subtracting; otherwise output an error message. Submit everything above for the warmup Multiplication. Implement the function X. It should take two extended precision integers as input and return a third extended precision integer that is the product of the two. Observe that if a and bare N-digit integers, the product will have at most 2N digits. Division. Integer division is the most complicated of the arithmetic functions. Here is one of the simplest algorithms to compute q = a/b and r = a mod b, where a and b are extended precision integers, with b not equal to 0. This algorithm requires the least amount of code, but its correctness may not be immediately apparent. diy (a, b) 1 ( ab) return (0, a) Styles Paragraph if ( URBARS.SOSEURES I # Alice encrypts mail bob@princeton.edu