689 views
0 votes
0 votes
RSA public key cryptography used with public key pair (e,n) is given as (5 ,35) and the primitive key pair (d,n) as (29,35) .

If receiver receives message as 22 , what would be the message sent by the sender :

1) 22                                                       2) 29

3) 35                                                       4) 31

2 Answers

Best answer
2 votes
2 votes

$(e,n)$ $\rightarrow$ $(5 ,35)$

$(d,n)$ $\rightarrow$ $(29 ,35)$

encrypted message, $c = 22$

we need to find original message,

Let the original message is p

we know that

$p = c^d$ mod $n$

    $= 22^{29}$ mod $35$

Now how to calculate $22^{29}$ mod $35$

Approach 1: simple divide and conquer strategy

divide the power into 2 parts 

$22^{14 + 15}$ mod $35$

$22^{14} * 22^{15}$ mod $35$

$( (22^{14}$ mod $35)$  $*$ $(22^{15}$ mod $35) )$ mod $35$               $\because A *B$ mod $n$ = $((A $ mod $n)$ *  $(B $ mod $n))$  mod $n$

$22^{14}$ mod $35$

$= 22^7 * 22^7$ mod $35$

$= ( (22^{7}$ mod $35)$  $*$ $(22^{7}$ mod $35) )$ mod $35$

$= (8 *8 )$ mod $35$

$= 64$ mod $35$   

$= 29$ 

Simarly we can do it for $22^{15}$ , we will get $8$

$( 29 $ mod $35)$  $*$ $(8$ mod $35) )$ mod $35

$= ( 29 *8 )$ mod $35

$=22$

Approach 2

Divide the power  lets say B in power of 2 by writing it in binary form  

$29_{10}$ = ${11101}_{2}$

Start from the rightmost digit, let k = 0, for each digit

               1. if the digit is 1 then we need $2^k$, otherwise, we do not

               2. add 1 to k and move left to the next digit 

$29_{10}$ = $ 2^4 + 2^3 + 2^2 + 2^0$ = $ 16+ 8 + 4 + 1$ 

$22^{29} \rightarrow 22^{16+8+4+1} \rightarrow 22^{16} * 22^8 * 22^4 *22^1$

$22^{29}$ mod $35$  =  $(22^{16} * 22^8 * 22^4 *22^1)$ mod  $35$

$22^{16}$ mod $35$ = $1$

$22^{8}$ mod $35$ = $1$

$22^{4}$ mod $35$ = $1$

$22^{1}$ mod $35$ = $22$

$22^{29}$ mod $35$  =  $(1 * 1 * 1 *22)$ mod  $35$ = $22$

selected by
2 votes
2 votes

Please discuss if any doubt :) 

Related questions