1

I think my confusion here is just which how the question was given to me. I am having trouble decrypting this simple RSA message.

Message: $0882~ 1090~ 1471~ 1899~ 2753~ 0309$

$p = 43 ; q = 71; e = 19$.

Someone please check my work that I have so far and I would appreciate help getting the final answer.

I have $N = 3053$ ; $\phi = 2940$; and $d = 619$

I am having trouble getting the answer, I know $M = C^d \pmod N$.

But does that mean I take the entire long message and raise it to the power of $19$?

UPDATE: FULL PROMPT:

"Assume that someone is going to send you an encrypted message (C = Me (mod pq)), and provide you with the following key (e,n), where n = p × q = 43 × 71 and e = 19. Given that you know the factorization of n, you can calculate d for decrypting the message by using PA1 extended Euclidean to calculate d (remember d is the inverse of e mod(p−1)(q−1)). Write the code for modular exponentiation because as you will see, d is a large number and you need this code to figure out what the message M was using the formula M = C d (mod pq). For both, Encryption and Decryption, each block message we will use two letters. Remember, we represent each letter of the alphabet by two digits, starting with 00 for space, 01 for A, 02 for B, etc....a total of 26 letters (including X, Y, Z). Decrypt the following message: 0882 1090 1471 1899 2753 0309. Good luck!

Note: You only need to solve on paper, do not write a code"

Watson
  • 11
  • Yes the message in encrypted and I am decrypting. The words are coded simply by coordinating the numbers of the alphabets (0 is a space, 01 is A, 02 is B, etc... 26 is Z) – Watson Dec 13 '15 at 19:08
  • unfortunately not, but when I do e*d mod PHI(N) i end up with 57 + (-56) = 1. But i am not sure how I would be my d value from that – Watson Dec 13 '15 at 19:17
  • $d = e^{-1} \pmod {\varphi(n)} = 19^{-1} \pmod {2940} = 619$. – Moo Dec 13 '15 at 19:19
  • Okay, that is what I had originally. But my question is where do I go from here..? do I plug my d into the M = C^d (mod N) equation? and is M equal to the long encrypted sting given to me? (sorry if I am asking alot of basic questions this is my first time doing one of these, hense the mass confusion) – Watson Dec 13 '15 at 19:25
  • I can post the prompt if that will help, but wouldn't all of the 4 bit blocks all be < 3053. ie 0882 < 3053 and so on.. – Watson Dec 13 '15 at 19:28
  • Yes, you do the decryption for each block of $4$. Please post as written. – Moo Dec 13 '15 at 19:31
  • I get plaintext = $801, 1616, 2508, 1512, 904, 125$. Unfortunately, that does not read off as an actual message. Going in reverse, this PT can be used to generate the CT and that works correctly. – Moo Dec 13 '15 at 19:36
  • hmm, so my professor gave me a problem I can't even solve! great. Ill have to email her and inform her. – Watson Dec 13 '15 at 19:40
  • No, my answer is correct - "Happy Holiday" is the PT. – Moo Dec 13 '15 at 19:40
  • Oh sorry I miss read your last comment, Thanks for the help. I am going to try and solve it and see if I can get my solution to match. Sincerely thank you! – Watson Dec 13 '15 at 19:42

1 Answers1

1

If you want to decrypt, you need to raise each chunk to the power $d=619$, so if the Message you have is encrypted, the first chunk of the decrypted part would be $0822^{619} \pmod {3053}=0801=HA$ according to Alpha. Keep going

Ross Millikan
  • 374,822