Encrypt the message ATTACK using the RSA system with n = 43 * 59 and e = 13, translating each letter into integers and grouping together pairs of integers

Question

I need the full detail of how you got the answer so I know how to do the problem for the future

Answer 1

Lets start with encoding your letters. Some classes will encode directly from the position in the alphabet, 1 thru 26. So A is 01, T - 20, C- 03, etc. Others will encode using 0-25, so A is 0, B is 1, C is 2, etc. Only you will know how your teacher or class does it. I’ll assume 1-26. RSA uses a public key, found from the product of 2 large primes. In your case, they selected 43 and 59, so your public key is 43*59 or 2537. You were also given e=13. Your first letters are AT, so in numbers it would be 0120 (The A is 01, the T 20). To encrypt this, we need to find 120^13 (mod 2537). Now, you can imagine that 120^13 is a really big number, so it will be hard to work with as such, especially to find the value mod 2537. We can take advantage of what you may have previously learned about modulo arithmetic. We’ll make a small table:

120 ^ 1 (mod 2537) = 120

120^2 (mod 2537) = 1715

120^4(mod 2537) = 1715*1715 (mod 2537) = 842

120^8(mod 2537) = 842*842 (mod 2537) = 1141

120^12(mod 2537)= 1141*842 (mod 2537) = 1736

So finally, 120^13 (mod 2537) = 1736*120 (mod 2537) = 286

So you would send 0286 for your first two letters. Your next two letters, TA, would start as 2001, and to encrypt, we would need to do the same thing, find 2001^13 (mod 2537). And so on. I know it's rather long. I hope this helps you start at least.

Good luck! Ed