123 views
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
22?
0
Please explain how did u calculated 22^29 mod 35 , how to decide that 29 should be broken into 14 *15 or 16*17 or 28*1 , how to decide that , is there any rule for this ?
0
1. If power is even then we can directly break into equal parts like 22, which is divisible by 2, So we can take the set (11, 11)

2. if the power is odd the like 23, then the highest value which is less then and divisible by 2 is 22, then we have (11, 11 ) and 1 is remaining, so we have the   set (11, 12)

$22^{28} = 22^{14} * 22^{14}$

$22^{28} = 22^1*22^{14} * 22^{14} = 22^{14} * 22^{15}$

Hope, this can clear your doubt

$(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
0
Thanks a lot for such a brief and precise solution .

Please discuss if any doubt :)

+1
how u calculated $22^{14}$?
0
Please explain how did u calculated 22^14 mod 35 , for 22^14 only I am getting very large value in the calculator , did u use any trick ?
+1
I just used the Gate calculator. Also mod operation is used. Basically I took by trial method any value that is not out of bounds of calc. I don't know if it's a correct way.. But it gives correct answer in less time.

Also mod rules are applied.
0
when I did from that calculator directly by taking 22^29 mod 35 , I am getting 14 as answer .

There is definitely some logic for calculating x^a mod n , because we can break a in any power terms and how to get a hit of breaking the power ?
0

2229 does not fit in the calculator. u can see an error term there... hence its not the correct way and will lead to incorrect solution...

my thought :

power =29 ...so cannot break it in 2 factors ,that multiply to give 29.

so break in such a way that addition of 2 numbers gives 29.

now randomly do like this... 20,9 ...but for 2220 ...out of bound.

15 ,14  yes correct.

hope this way of thinking will help :)

0

Please see this , it calculated 22^29 , its gate virtual calculator only .

+1

Dont use virtual calculator for calculating mod or power of hight number , it give correct answer till certain point.

This link will solve some kind of problems: https://crypto.stackexchange.com/questions/5889/calculating-rsa-private-exponent-when-given-public-exponent-and-the-modulus-fact

+1 vote
1
2