You are part of the Cryptographic Security Team at a military facility, tasked w

Question

You are part of the Cryptographic Security Team at a military facility, tasked with decoding messages as required. A message has come in from HQ, as an ordered collection of numbers, which is personalised for yourself and aimed at testing aspects of your decoding skills. 441293, 62726, 85337, 485650, 337275, 91235, 360194, 126355, 266199, 315721, 329746, 442869 These numbers (above) have each been encoded using RSA with a modulus of m = pq = 496241 (with p and q being primes) and encoding exponent of 218821. You are advised that {13631, 142703} is a valid encoding-decoding pair for the same modulus, m. (a) Use this information to determine psi (m) for this modulus. (Using software to directly factorise m is not a valid option for doing this part.) (b) Verify your answer by determining the primes p and q. Show how these combine to give both m and psi (m). (c) Calculate the decoding exponent for 218821, as encoding exponent, using the extended Euclidean algorithm. (Again, using software to directly obtain this is not a valid option, though you are welcome to use software to confirm your answer.) (d) For each of the 12 numbers in your message, verify they have no prime factors in common with m. (It is OK to use software for this task, provided you have answered the previous part.) The next part is optional, for bonus marks. Your final task - should you accept it - is to decode the personalised message represented by the set of numbers above, resulting from an RSA encoding of a message, with exponent 218821. The message, before RSA has been applied, was constructed as described below. You will know that you have successfully decoded the message, since your own student ID appears at some place within the message surrounded by a pair of colons (:), starting at character k say. Your answer to this task should consist of the text of the message, along with the number k at which character the colon preceding the student ID appears, as well as a description of how you obtained it. You are free to use any software that you like in attempting to decode your message. Messages are built using the 40 characters comprising digits, capital letters, space character and some punctuation as shown in the following ordered list - the space character is at position 11 (shown in quotes), with A at position 12. 0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z, : .

Explanation / Answer

Given m=pq = 496241
exponent e = 218821

Factors of m=496241 are 677 × 733
Therefore p = 677
q = 733

a)(m) = (p - 1) * (q - 1)
= (677-1)) * (733-1)
= 676 * 732
= 494832

b) p = 677 ; q = 733

c) Given, encoding exponent e = 218821

Now, Based on extended euclidean algorithm goal is to find d such that ed = 1 mod (m)

* calculate x and y such that ax+by=gcd(a,b).
Here, a=e, b=(m), and thus gcd(e,(m))=1

Now, ex+(m)y = 1

In this case "x" is decoded exponent (x=d)

we have, e = 218821 and (m) = 494832

ex+(m)y = 1 => 218821x + 494832y = 1

we need to solve this equation for finding "x".

we can write, 494832 = 2*218821 + 57190 ( with e and (m))
similarly, 218821 = 3*57190 + 47251
now, 57190 = 1*47251 + 9939
47251 = 4*9939 + 7495
9939 = 1*7495 + 2444
7495 = 3*2444 + 163
2444 = 14*163 + 162
163 = 1*162 + 1

write last one as 163 - 1*162 = 1
Now substitute in place of 162 as => 163 - 1*(2444 - 14*163) = 1 and so on
=> 163 - 1*(2444 - 14*(7495 - 3*2444)) = 1
=> 163 - 1*(2444 - 14*(7495 - 3*(9939 - 1*7495))) = 1
=> 163 - 1*(2444 - 14*(7495 - 3*(9939 - 1*(47251 - 4*9939)))) = 1
=> 163 - 1*(2444 - 14*(7495 - 3*(9939 - 1*(47251 - 4*(57190 - 1*47251))))) = 1
=> 163 - 1*(2444 - 14*(7495 - 3*(9939 - 1*(47251 - 4*(57190 - 1*(218821 - 3*57190)))))) = 1
=> 163 - 1*(2444 - 14*(7495 - 3*(9939 - 1*(47251 - 4*(57190 - 1*(218821 - 3*(494832 - 2*218821))))))) = 1

Make this as a linear combination of e and (m) i.e, 218821 and 494832

i.e, (d)* 218821 + (some constant)*(494832) = 1

you will get the "d" value and it is the decode exponent of the given "e" value.

d)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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