ZD - RSA::encrypt()
Rivest, Shamir and Adelman published their famous RSA encryption algorithm in 1977. In this problem, you are asked to implement a 32-bit version of RSA encryption. You will be given an integer n which is the product of two primes p and q (both are unknown to you). You will also be given an integer e (which is relatively prime to (p-1)(q-1)). n and e together are referred to as the public key. Then follows a text message which you are to encrypt using the public key. First, the message is transofmed into a sequence of 32-bit integers (unsigned). This is done by taking the given text string, writing it as a sequence of bytes in ASCII and interpreting the bytes as an array of 32-bit integers. For example, the string
is represented in ASCII as the sequence of bytes
which are written in hexadecimal notation as
When concatenated together, these 16 bytes occupy exactly four 32-bit integers:
which are written in decimal as
The next step in encryption is to raise each of the 32-bit integers to the power e modulo n. To avoid losing information, n has to be bigger than or equal to 232. Call each 32-bit integer P. Then the corresponding encrypted 32-bit integer, C, is computed as follows.
If n=10002200057 and e=5, then the four numbers in the above example are encrypted to produce the four C-numbers
which look like this in hexadecimal:
Since n can not be smaller than 232, some of these numbers might not fit into 4 bytes (32 bits). In this example, n occupies 34 bits (at least 5 bytes). So we will use 5 bytes to represent each of the four C-numbers:
When interpreted as ASCII codes, these bytes look like the characters
(?? represents unprintable characters) Since the resulting cyphertext is binary garbage (that is the point of encryption, after all) and can contain unprintable and control characters, your program should output the hexadecimal values of the characters. See the first input/output sample below. Notes: This long explanation may sound complicated, but in reality, the type conversion steps can be implemented using a pair of pointer casts (in C/C++). For example, to make a string into an array of integers, simply cast it like this:
char str[] = "DEOXYRIBONUCLEIC";
This is not entirely true, however. One needs to worry about the order of bytes in an integer. For example, on an Intel CPU, ints[0] will be 584F4544 in hex instead of 44454F58. To conform to the scheme described above, the byte order needs to be flipped. If you want to make your code portable, you should use the functions htonl() and ntohl() (see their man pages). Another way to think about the flipping-of-bytes is to imagine rearranging each quadruple of characters in the string before converting it to integers. For example, turn
into
and then proceed without worrying about byte order. If the given plaintext string's length is not a multiple of 4, pad the string at the end with zero characters. InputThe input will consist of a number of test cases. Each test case is comprised of 2 lines. The first line contains the public key, n and e. The second line is the message. OutputGiven n, you will need to find the smallest number of bytes needed to store n numbers (it was 5 in the above example). Call this number b. For example, if n is 221, b is 1 because one byte can represent 221 different numbers. If n is 65537, b is 3. In this problem, since n>=232, b will never be smaller than 4. For each test case, output 4 things:
The hex digits A-F should be capital letters. Sample input10002200057 5 DEOXYRIBONUCLEIC 1210140803471 1100089 Plumes of smoke rise and merge into the leaden sky Sample output10002200057 5 5 016C182123 0217126914 011B229825 0249D48C6D 1210140803471 1100089 6 010E746CB830 001E4C23CD53 002564CA1DC8 00ED1D0A132F 00A6CCE34282 00FF954B9B7E 0021A5E3C35C 0107C8BB0462 000E5BA63D64 00978F262566 00FB81D3BC15 0021E9B6585B 00D3E5E1B9CD |