Statistics

Problem Statement for "RSABreaker"

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

  1. 3

    10

    3

    Returns: 7

    This is the example from the problem statement.

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

  3. 1

    42

    17

    Returns: 17

    In this case, m = 12 and we can take d = 1.

  4. 5

    997

    7

    Returns: 523

    Beware of overflow.

  5. 47

    843

    822

    Returns: 831

  6. 999

    786

    56

    Returns: 614

  7. 67

    238

    93

    Returns: 121

  8. 589

    563

    469

    Returns: 364

  9. 233

    511

    209

    Returns: 209

  10. 287

    287

    98

    Returns: 119

  11. 599

    151

    71

    Returns: 134

  12. 865

    454

    51

    Returns: 143

  13. 755

    193

    53

    Returns: 176

  14. 289

    674

    73

    Returns: 641

  15. 681

    902

    12

    Returns: 12

  16. 481

    802

    632

    Returns: 476

  17. 627

    467

    417

    Returns: 410

  18. 775

    29

    6

    Returns: 13

  19. 839

    615

    607

    Returns: 538

  20. 165

    30

    27

    Returns: 27

  21. 647

    935

    513

    Returns: 827

  22. 549

    538

    48

    Returns: 262

  23. 859

    865

    779

    Returns: 694

  24. 691

    922

    24

    Returns: 24

  25. 553

    206

    152

    Returns: 144

  26. 151

    766

    699

    Returns: 505

  27. 119

    805

    340

    Returns: 555

  28. 971

    535

    118

    Returns: 297

  29. 491

    914

    176

    Returns: 22

  30. 151

    102

    66

    Returns: 42

  31. 523

    471

    309

    Returns: 69

  32. 587

    111

    84

    Returns: 63

  33. 577

    263

    91

    Returns: 161

  34. 309

    510

    504

    Returns: 24

  35. 769

    777

    654

    Returns: 213

  36. 359

    454

    216

    Returns: 354

  37. 185

    415

    161

    Returns: 191

  38. 629

    469

    297

    Returns: 439

  39. 277

    395

    379

    Returns: 314

  40. 39

    391

    129

    Returns: 379

  41. 751

    611

    405

    Returns: 505

  42. 107

    969

    311

    Returns: 125

  43. 991

    886

    493

    Returns: 127

  44. 895

    499

    455

    Returns: 441

  45. 127

    498

    129

    Returns: 447

  46. 617

    319

    94

    Returns: 7

  47. 403

    607

    9

    Returns: 428

  48. 439

    598

    122

    Returns: 424

  49. 511

    470

    176

    Returns: 116

  50. 979

    122

    67

    Returns: 79

  51. 639

    934

    772

    Returns: 832

  52. 769

    815

    105

    Returns: 105

  53. 809

    341

    108

    Returns: 60

  54. 89

    866

    31

    Returns: 321

  55. 451

    766

    166

    Returns: 246

  56. 403

    519

    82

    Returns: 103

  57. 453

    177

    83

    Returns: 101

  58. 55

    563

    169

    Returns: 555

  59. 441

    46

    19

    Returns: 19

  60. 581

    941

    775

    Returns: 545

  61. 311

    695

    149

    Returns: 39

  62. 641

    307

    147

    Returns: 189

  63. 929

    658

    12

    Returns: 178

  64. 317

    703

    663

    Returns: 386

  65. 349

    319

    132

    Returns: 165

  66. 859

    91

    10

    Returns: 10

  67. 269

    523

    467

    Returns: 518

  68. 257

    377

    72

    Returns: 11

  69. 989

    93

    15

    Returns: 60

  70. 821

    133

    15

    Returns: 78

  71. 491

    958

    124

    Returns: 136

  72. 997

    74

    23

    Returns: 23

  73. 577

    151

    139

    Returns: 62

  74. 517

    19

    13

    Returns: 10

  75. 815

    767

    450

    Returns: 148

  76. 149

    919

    0

    Returns: 0

  77. 835

    254

    190

    Returns: 246

  78. 613

    733

    552

    Returns: 237

  79. 89

    886

    392

    Returns: 288

  80. 503

    906

    120

    Returns: 708

  81. 169

    417

    24

    Returns: 144

  82. 507

    958

    929

    Returns: 579

  83. 59

    246

    80

    Returns: 20

  84. 667

    898

    860

    Returns: 682

  85. 23

    597

    126

    Returns: 45

  86. 629

    742

    98

    Returns: 602

  87. 407

    553

    300

    Returns: 48

  88. 501

    697

    581

    Returns: 403

  89. 173

    899

    381

    Returns: 267

  90. 79

    902

    130

    Returns: 170

  91. 67

    187

    0

    Returns: 0

  92. 447

    557

    278

    Returns: 357

  93. 625

    398

    247

    Returns: 41

  94. 103

    745

    425

    Returns: 155

  95. 787

    713

    526

    Returns: 681

  96. 7

    878

    643

    Returns: 121

  97. 843

    743

    67

    Returns: 555

  98. 179

    634

    538

    Returns: 148

  99. 739

    133

    33

    Returns: 33

  100. 335

    258

    244

    Returns: 46

  101. 5

    997

    7

    Returns: 523

  102. 5

    997

    9

    Returns: 250

  103. 5

    997

    996

    Returns: 996

  104. 3

    10

    3

    Returns: 7

  105. 715

    910

    531

    Returns: 41

  106. 17

    33

    4

    Returns: 31

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: