made easy test series

Question

In a RSA cryptosystem , a participant uses two prime numbers p and Q is 17 and 11 respectively to generate his/her  public key and private keys. if the public key of participant is 7 and cipher text(C) is 11, then the original message (M) is______?

Comments

149??

---

 

given ans is as above .bt how this one will came! .may yu explain?

Answer 1

Public Key = (n, e)    e = 7 , p = 17  ,  q  = 11 
Private Key = (n, d)  
n = pq = 187

Φ(n) = (p-1)(q-1) so, Φ(n) = 160

d *e mod Φ(n) = 1

d = 23

cipher text , c = 11

Message ,  M = c^d mod n

M = 11²³ mod 187 = 149

Comments

 11²³ mod 187 = 149

procedure to get this value 149 as above? (or yu r using calculator or any hit and trial method )

---

Calculator bro as you will be provided with that

---

by using calculator the answer comes wrong and it is from GATE 2016

---

3 aa raha ha

---

mera 12 aa rha h(by using calculator) ,,bt actual ans is 4.

---

yeah By using virtual calculator answer is : 149

but if we use normal scientific calculator answer will be : 88

but my  question is that..we unable  to reduce it  by applying totient formula  :3

---

if number is very big then VC will give the wrong result and here you can not apply totient method so solve it by splitting method.

---

by splitting method.

@Shubhgupta  How ??

---

$11^{23}mod187 =(11^{10}∗11^{10}∗11^{3})mod187 =(11^{10}mod187∗11^{10}mod187∗11^{3}mod187)mod187 =(66∗66∗22)mod187 =88$

split big power to small small power then VC will show the correct result.

---

@Shubhgupta 

thanks 

---

can someone tell me how 23 calculated . I mean how actual calculation is done?

Answer 2

In RSA we encrypt using public and decrypt using private key

phi = (p-1)(q-1) = 160

Public key = 7

calculate Private key(d) comes out to be 23

let original msg be 'm'

ciphertext be 'c'

c^d mod n = m  // as c = m^e mod n and by euler toitent we know m^ed mod n = m

c = 11, d = 23 and n = p*q calculate m !