ZD - RSA::encrypt()

Here are a few hints on how to avoid overflow in this problem.

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

D E O X Y R I B O N U C L E I C

is represented in ASCII as the sequence of bytes

68 69 79 88 89 82 89 66 79 78 85 67 76 69 73 67

which are written in hexadecimal notation as

44 45 4F 58 59 52 49 42 4F 4E 55 43 4C 45 49 43

When concatenated together, these 16 bytes occupy exactly four 32-bit integers:

44454F58 59524942 4F4E5543 4C454943

which are written in decimal as

1145392984 1498564930 1330533699 1279609155

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.

C = Pe mod n

If n=10002200057 and e=5, then the four numbers in the above example are encrypted to produce the four C-numbers

6108487971 8977017108 4750219301 5083928637

which look like this in hexadecimal:

016C182123 0217126914 011B229825 0249D48C6D

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:

01 6C 18 21 23
02 17 12 69 14
01 1B 22 98 25
01 2F 06 98 3D

When interpreted as ASCII codes, these bytes look like the characters

?? l ?? ! # ?? ?? ?? i ?? ?? ?? " % ?? / ?? =

(?? 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";
unsigned int *ints = ( unsigned int* )str;
// ints[0], ints[1], ... are now the P-numbers.

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
D E O X
Y R I B
O N U C
L E I C

into

X O E D
B I R Y
C U N O
C I E L

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.

Input

The 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.

Output

Given 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:

  1. A line containing n, a space, then e.
  2. A line containing The value of b for this test case.
  3. The hex values of encrypted bytes, 2b characters (one encrypted integer) per line.
  4. An empty line.

The hex digits A-F should be capital letters.

Sample input

10002200057 5
DEOXYRIBONUCLEIC
1210140803471 1100089
Plumes of smoke rise and merge into the leaden sky

Sample output

10002200057 5
5
016C182123
0217126914
011B229825
0249D48C6D

1210140803471 1100089
6
010E746CB830
001E4C23CD53
002564CA1DC8
00ED1D0A132F
00A6CCE34282
00FF954B9B7E
0021A5E3C35C
0107C8BB0462
000E5BA63D64
00978F262566
00FB81D3BC15
0021E9B6585B
00D3E5E1B9CD