Decoding an RSA value on paper

Problem 10 on the 2019 Sample 9 test is an RSA question that asks us to decode an encrypted value using a private key:

 

10) [120 points] Jonathan and Madison are accountants for a very large bank, and have started a friendship. They communicate via email, because they live thousands of miles apart. Madison gets curious and asks Jonathan the year that they were born. Jonathan doesn t mind telling Madison, but they know that the bank monitors all employee emails, and is afraid of being the victim of age discrimination. Therefore, Madison suggests that they use RSA, and they provide their public key: (5767, 3665). Jonathan replies with the ciphertext 983. Madison s private key is 4289. In what year was Jonathan born?

In order to decode, we need to decode the cipher text using the function:
Cd mod n.

Because of the size of the values, we have to use the Rapid Modular Exponentiation method, also known as the method of repeated squaring.

We start off by identifying the values we need:

c = 983 (The cipher text)

d = 4289 (Madison s private key)

n = 5767 (The larger number in the public key)

First, we need to convert Madison's private key d to binary which will tell us how many operations we will need to do. Start by creating a table which will eventually have several columns but for now we just fill in the first two columns.

d

binary

4289

Next, we want to convert it to binary. To do this, we take the integer portion of the value and divide it by 2. If the number has a remainder of .5 or more (i.e. the original number was odd) we put a 1 in the binary column, otherwise we put a 0. If we are doing this on a calculator, we can do this quickly by taking the original number and dividing by 2 then keep hitting the equals sign to repeat the division by 2, BUT we must carefully look at the number to the right of the decimal to see if it is .5 or higher. When we are done, we will have the number in binary form with the low bit to high bit like:

d

binary

4289

2144.5

1

1072

0

536

0

268

0

134

0

67

0

33.5

1

16.5

1

8

0

4

0

2

0

1

0

0.5

1

Next, we want to compute the powers (mod n) and write them next to the corresponding binary number. To do this, we put the value of c in the first row and then for each row below it, we square the previous number and compute the mod n value. We must do this at each level because the numbers get big quite quickly. If we want to do this quickly on a calculator, there are a couple of tricks that can really speed it up. First store the n value into the memory of the calculator  MC   5   7   6   7   M+ . Then we can square the number and mod it quickly. For example, with the second row, enter  9   8   3   x   =  to square it and see 966,289. Then we compute the mod by dividing by n (which should be in memory)  ÷   MR   =  producing 167.55488, subtract off the integer portion  -   1   6   7   =  and then multiply it by the mod value  x   MR   =  producing 3199.9929 which we round to 3200 and write that down. Repeat this process for all the rows.

d

binary

c mod n

How to compute

4289

5767

 

2144.5

1

983

Write c (983) down

1072

0

3200

(983*983) mod 5767

536

0

3575

(3200*3200) mod 5767

268

0

953

(3575*3575) mod 5767

134

0

2790

(953*953) mod 5767

67

0

4417

(2790*2790) mod 5767

33.5

1

128

(4417*4417) mod 5767

16.5

1

4850

(128*128) mod 5767

8

0

4674

(4850*4850) mod 5767

4

0

880

(4674*4674) mod 5767

2

0

1622

(880*880) mod 5767

1

0

1132

(1622*1622) mod 5767

0.5

1

1150

(1132*1132) mod 5767

Next, we need to combine the mod values for all the places where we have a 1 bit. Again, we will need to do this a step at a time because it will overflow the calculator quickly. First go down the rows until we find the first 1 in the binary column. In this case it is the first bit, but it doesn t matter where, simply copy the 983 from the c mod n column and write it into the Accumulate column. Next, we go down the rows until find another 1 in the binary column. For this we multiply the current c mod n column by the previous Accumulate column value and then do a mod n (which should be in memory). In this case we enter  1   2   8   x   9   8   3   =  which gives 125,824, then take the mod with  ÷   MR   =  producing 21.817929, subtract off the integer portion  -   2   1   =  and then multiply it by the mod value  x   MR   =  producing 4716.9965 which we round to 4717 and write that down. Repeat the process until we get to the last row in the table (which will always have a 1 in the binary column) and the value we compute for the Accumulate column will be the answer of 1966.

d

binary

c mod n

Accumulate

How to compute

4289

5767

 

2144.5

1

983

983

First row with a 1 so we copy the c mod n value.

1072

0

3200

 

536

0

3575

 

268

0

953

 

134

0

2790

 

67

0

4417

 

33.5

1

128

4717

(128*983) mod 5767

16.5

1

4850

5528

(4850*4717) mod 5767

8

0

4674

 

4

0

880

 

2

0

1622

 

1

0

1132

 

0.5

1

1150

1966

(1150*5528) mod 5767