you may use brute force

Recall that an RSA Cryptosystem is defined by five numbers: Public Information: N, E Private Information: P, Q, D, where P, Q are large primes, N = P*Q, E is relatively prime to (P-1) -1), and D is the modular inverse of E mod (P - 1)(Q-1). The pair (E, N) represents the public encryption key, the number D represents the private decryption key. To encrypt a message like 'ABCDEF', translate that into a series of digits (for instance A to 01, B to 02, Z to 26) etc, so the message becomes 010203040506 and partition that into a sequence of blocks numbers such that each number is less than N. In this case, you might have 010, 203, 040, 506. A block M is then encrypted to a ciphertext C using the following map: C = M (mod N), (1) and an encrypted block C is decrypted using the following relationship: M = CD (mod N). Once each block of a message is decrypted, the digits can be worked backwards into the original message (potentially padding things out with O's as necessary, 10 010 for example). The functionality of the system rests on the fact that if C = Me (mod n), then M = Cd (mod n). The security of the system rests on the fact that if all an attacker knows is e, n, and the encrypted message C, is is very hard computationally to work backwards and determine M. Your published encryption keys are N = 2881, E = 1109. Unfortunately, you've lost your private decryption keys P, Q, D! 1) Prove that at least one of P and Q needs to be less than 54. (5 points) 2) Find values for P and Q, and show your work. (10 points) 3) Verify that E is relatively prime to (P-1)(Q - 1), and show your work. (10 points) 4) Find a decryption key D, and show your work. Trial and error does not count. (15 points) 5) You receive the following encrypted message as a sequence of C blocks: 1567, 214, 1023, 398, 581, 1427, 1623, 2679, 895, 948, 951 Decrypt each block to reveal the original block M, and then reconstruct the original message. Show your work. (35 points) Recall that an RSA Cryptosystem is defined by five numbers: Public Information: N, E Private Information: P, Q, D, where P, Q are large primes, N = P*Q, E is relatively prime to (P-1) -1), and D is the modular inverse of E mod (P - 1)(Q-1). The pair (E, N) represents the public encryption key, the number D represents the private decryption key. To encrypt a message like 'ABCDEF', translate that into a series of digits (for instance A to 01, B to 02, Z to 26) etc, so the message becomes 010203040506 and partition that into a sequence of blocks numbers such that each number is less than N. In this case, you might have 010, 203, 040, 506. A block M is then encrypted to a ciphertext C using the following map: C = M (mod N), (1) and an encrypted block C is decrypted using the following relationship: M = CD (mod N). Once each block of a message is decrypted, the digits can be worked backwards into the original message (potentially padding things out with O's as necessary, 10 010 for example). The functionality of the system rests on the fact that if C = Me (mod n), then M = Cd (mod n). The security of the system rests on the fact that if all an attacker knows is e, n, and the encrypted message C, is is very hard computationally to work backwards and determine M. Your published encryption keys are N = 2881, E = 1109. Unfortunately, you've lost your private decryption keys P, Q, D! 1) Prove that at least one of P and Q needs to be less than 54. (5 points) 2) Find values for P and Q, and show your work. (10 points) 3) Verify that E is relatively prime to (P-1)(Q - 1), and show your work. (10 points) 4) Find a decryption key D, and show your work. Trial and error does not count. (15 points) 5) You receive the following encrypted message as a sequence of C blocks: 1567, 214, 1023, 398, 581, 1427, 1623, 2679, 895, 948, 951 Decrypt each block to reveal the original block M, and then reconstruct the original message. Show your work. (35 points)