Don’t forget to carry the 1

I’ve been working on my assignment for almost five hours now. I know that it shouldn’t take this long but sometimes when you’ve been working on something for a long period of time, obvious things aren’t so obvious. It took me two hours to work on a problem and I’ve finally solved it. Now I can carry on to the other part of the assignments.

This assignment for my networking class is about cryptography, mainly the RSA algorithm. This algorithm was created by Ron Rivest, Adi Shamir, and Leonard Adleman hence that’s how it got its name. The whole thing involves three steps, key generation, encryption and decryption. The last two steps are easy so long as you’ve completed the first step correctly.

The key generation step involves the following.

You need two prime numbers, p and q. Next, you have to compute n = pq. Then you compute the φ(n) = (p – 1) (q – 1). And finally, you have to solve for d which is the private key. For my assignment, the numbers were as follows:

p = 23
q = 17
e = 19
n = pq
n = 23 x 17
n = 391
φ(n) = (p – 1) (q – 1)
φ(n) = (23 – 1)(17 – 1)
φ(n) = 22 x 16
φ(n) = 352

With all of these calculations out of the way, I can go ahead and solve for d. I had a little bit of a hard time solving this equation because I kept losing track of what number goes where and which numbers to subtracted from which column. I took me about two hours before I finally arrived at the correct answer.

e φ(n) (1,0) (0,1) Comments
19 352 (1,0) (0,1)  
19 10 (1,0) (-18,1) y = 18, r = 10; (0,1) – 18(1,0) = (0,1) – (18,0)
9 10 (19,-1) (-18,1) y = 1, r = 9; (1,0) – (-18,1) = (19,-1)
9 1 (19,-1) (-37,2) y = 1, r = 1; (-18,1)-(19,-1) = (-37,2)
0 1 (314,-19) (-37, 2) y = 9, r = 0; (19,-1) – 9(-37,2) = (-19,-1) – (-333,18) = (314,-19)

What is happening here is that you would keep calculating the numbers until either the e or the φ(n) reaches a value of 1, in this case, it did in a few steps. Whichever column has a value of 1, that’s where the answer is for d. In this case, it’s -37 but d cannot be negative so we have to solve it further.

d = -37 mod φ(n)
d = -37 mod 352
d = 315

For anyone who isn’t familiar with programming, mod means to divide and take the remainder. So 5 mod 4 means that 4 goes into 5 once and has a remainder of 1. In this case, the remainder would be a negative number so you subtract from the divisor. I don’t remember learning that part when I was in school but now I know.

So d = 315 and that becomes the private key. Now that you have the private key, you can encrypt and decrypt your message. To encrypt the message you use this formula:
c = md mod n
and to decrypt you use this formula:
m = cd mod n
Where m is the message and c is the cipher text.

During the key generation step, I did everything that I was supposed to do only I forgot to carry the one and received an answer of -27 instead of -37 and that’s what messed everything up. The stupid part about it was that I kept getting -27 every time and I didn’t see that mistake until I went over it again and again. But at least I managed to get a lot of practice working in this because I know that it’ll be on the exam and now I can do it all by hand.

One thought on “Don’t forget to carry the 1

Comments are closed.