TopCoder problem "RSABreaker" used in SRM 182 (Division II Level Three)



Problem Statement

    This problem statement uses HTML elements which will not appear properly when viewing from some plugins. Please view the statement in the applet.

One of the most famous techniques in computer science is that of RSA encryption. To use it, we begin by choosing positive integers, e, n, d, and m, with the following properties.

  • 1. n is divisible by no perfect squares larger than 1.
  • 2. m is equal to the number of positive integers less than n that share no prime factors with n.
  • 3. e * d has a remainder of 1 when divided by m.
Then, given an integer a, between 0 and n-1 inclusive, we encrypt it as the remainder, again between 0 and n-1 inclusive, when ae is divided by n. Similarly, we decrypt an integer b, between 0 and n-1 inclusive, as the remainder, between 0 and n-1 inclusive, when bd is divided by n. Any kind of data can be decomposed as a list of such integers, and thus, any kind of data can be encrypted and decrypted in this way.

For example, suppose e = 3, n = 10, d = 3, and m = 4. As required,

  • 1. n is divisible by no perfect squares larger than 1.
  • 2. There are precisely m positive integers less than n that share no prime factors with n, namely {1,3,7,9}.
  • 3. d*e = 9, which has a remainder of 1 when divided by m.
We can thus use these values for RSA encryption. For example, we would encrypt 7 as 3, since 7e = 343, which has a remainder of 3 when divided by n. Then, we would decrypt 3 as 7, since 3d = 27, which has a remainder of 7 when divided by n.

Suppose you want to allow people to send you encrypted messages that only you can read, but you have no way of meeting these people privately to agree upon a secret code. Remarkably, RSA encryption makes this possible. First of all, you choose e, n, d, and m satisfying the conditions described above. Then you announce the values of e and n, called the public key, to the entire world. Now, everybody has the information required to encrypt messages. To decrypt these messages, however, it is necessary to know d, called the private key, and only you know that. Other people could theoretically compute a legal value for d, given e and n, but nobody has found a practical method for doing this when n is large.

When n is smaller, however, it is significantly easier to determine a legal private key, and hence to break RSA encryption. Create a class RSABreaker that contains a method decrypt, which is given an int e, an int n, and an int b, representing a public key and an encrypted integer. The method should return the decrypted value of b, as described above.

 

Definition

    
Class:RSABreaker
Method:decrypt
Parameters:int, int, int
Returns:int
Method signature:int decrypt(int e, int n, int b)
(be sure your method is public)
    
 

Notes

-There will always be multiple private keys compatible with each public key. Any one of them will decrypt messages correctly.
 

Constraints

-e will be between 1 and 1000 inclusive.
-n will be between 3 and 1000 inclusive.
-n will be divisible by no perfect squares larger than 1.
-b will be between 0 and n-1 inclusive.
-e and m (as computed above) will share no prime factors. This guarantees the existence of a legal private key.
 

Examples

0)
    
3
10
3
Returns: 7
This is the example from the problem statement.
1)
    
17
33
4
Returns: 31
The integers less than n sharing no prime factor with n are (1,2,4,5,7,8,10,13,14,16,17,19,20,23,25,26,28,29,31,32), so m = 20. We can then take d = 13 since 17*13 = 221, which has a remainder of 1 when divided by m. To decrypt 4, we take the remainder when 4e = 67108864 is divided by 33.
2)
    
1
42
17
Returns: 17
In this case, m = 12 and we can take d = 1.
3)
    
5
997
7
Returns: 523
Beware of overflow.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2310

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=4730&pm=2310

Writer:

dgarthur

Testers:

lbackstrom , brett1479

Problem categories:

Encryption/Compression