Suppose you want to receive private messages (from anyone located anywhere in th

Question

Suppose you want to receive private messages (from anyone located anywhere in the world-even people you've never met). To set up a Public key system, you pick two primes p and q and set = pq. The n you choose a positive integer e that relatively prime with phi(n) = (p - 1)(q ? 1) (here Phi(n) is the Euler phi function that returns the number of positive integers less than and relatively prime to n). Suppose you choose p = 101 and q = 29, so n = 2929 and phi(n) = 2800. Next you choose e = 2291 which is relatively prime to phi(n) = 2800. The pair (e, n) = (2291, 2929) is your enciphering key. You now make public (only) your enciphering key. (Of course, p and q need to be much larger in real life, so that n will be hard to factor.) Now suppose i have your enciphering key and decide to send you an encrypted message. Given the size of n, the block size should be m = 2 (two letters per numerical block). I use your public key to encipher a message as follows. First i translated my message to a numerical one. Here we have used the translation table: We added the symbol "-" since all message need to have length divisible by m(2 in this case) so we can add a "-" to make an odd length even. To encode the first block of the message above, i raise 805 to the power c= 2291 and take the result modulo n = 2929 obtaining 1372. The first couple of blocks of the encrypted example message are: 1372 937 2313. Ok now I am sending you the following message using your encrypting key: Your mission is to compute your deciphering key from the setup above and decode the message. Here is another message, using your enciphering key: Decipher and turn in (in words) both of the message above. Also email to me at least one message of your own using my enciphering key: (e, n) = (7, 3131)(Use block length m = 2.)

Explanation / Answer

Greetings.

Above is an instance of RSA encryption method. Here we are already given the value of p,q,n and euler phi function.

When e was selected to be 2291, we can easily obtain the value of d(using extended euclid algorithm). Here we get d = 11

So, to decrypt the message, we just raise each numeric encryption, say x to (xd) and take mod of n.

For example, in first message, 149 is decrypted to 614 which becomes 0614 which becomes 'go'

1) So, the first message when decrypted entirely gives :

"god made the integers - the rest is the work of man - leopoldkronecker-"

2) And similarly, second message decrypts to :

"all mathematicians are doing number theory - its just that some domt know it yet"

3) We encrypt "hello" using the given encryption key as :

encrypted message : 641 1111 341

Hope it helps. Thanks

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.