The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

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

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

1) 22 2) 29

3) 35 4) 31

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

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

+2 votes

Best answer

$(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$

+2 votes

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.

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 ?

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

22^{29} 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 22^{20} ...out of bound.

15 ,14 yes correct.

hope this way of thinking will help :)

+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

- All categories
- General Aptitude 1.5k
- Engineering Mathematics 7.3k
- Digital Logic 2.7k
- Programming & DS 4.9k
- Algorithms 4.2k
- Theory of Computation 5.4k
- Compiler Design 2.1k
- Databases 4k
- CO & Architecture 3.5k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.5k
- Admissions 568
- Exam Queries 566
- Tier 1 Placement Questions 23
- Job Queries 70
- Projects 18

48,634 questions

52,768 answers

183,405 comments

68,307 users