Given p = 17; q = 31; e = 7; C = 128, please calculate the d value for private k

Question

Given p = 17; q = 31; e = 7; C = 128, please calculate the d value for private key and recover the original plain text message M. (Need to show the details of the calculation in details)

Explanation / Answer

1)n=pq n=17*31=527 2)Phi(n) = (p-1)(q-1)=16*30=480 3)e=5 4)compute d. (d*e)mod phi(n) = 1 7.d mod 480 = 1 gcd(7,480) Step1: Euclidean algorithm: 480 = 68*7+4 7=1*4+3 4=1*3+1 Step 2: method back tracing 1=4-(1.3) 1=4-1.(7-1.4) 1=4-1.7=1.4 ===>2.4-1.7 1=2.(480-68.7)-1.7 1=2.480-136.7-1.7 1=2.480-137.7 ===> d= 137 5) public key (e,n) ==>(7,527) 6)private key(d,n) ==>(137,527) 7)plain Text P= C(power)d mod n (128)d mod 527 (128)137 mod 527 = (128)1 mod 527 = 128 (128)2 mod 527 = 128 * 128 mod 527 = 47 (128)4 mod 527 = 47*47 mod 527 = 101 (128)8 mod 527 = 101*101 mod 527 = 188 (128)16 mod 527 = 188 * 188 mod 527 = 35 (128)32 mod 527 = 35*35 mod 527 = 171 (128)64 mod 527 = 171*171 mod 527 = 256 (128)137 mod 527 = (128)64 mod 527 * (128)64 mod 527 * (128)8 mod 527 * (128)1 mod 527 =256*256*188*128 mod 527 = 264

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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