One major drawback of public-key algorithms is that they are relatively slow. In

Question

One major drawback of public-key algorithms is that they are relatively slow.

In Sect. 7.5.1 we learned that an acceleration technique is to use short exponents e.

Now we study short exponents in this problem in more detail.

1. Assume that in an implementation of the RSA cryptosystem one modular squaring

takes 75% of the time of a modular multiplication. How much quicker is

one encryption on average if instead of a 2048-bit public key the short exponent

e=216+1 is used? Assume that the square-and-multiply algorithm is being used

in both cases.

2. Most short exponents are of the form e = 2n +1. Would it be advantageous to

use exponents of the form 2n?1? Justify your answer.

3. Compute the exponentiation xe mod 29 of x = 5 with both variants of e from

above for n = 4. Use the square-and-multiply algorithm and show each step of

your computation.

Explanation / Answer

Answer

1.

On an average one encryption is three times faster if instead of a 2048-bit public key the short exponent e=216+1 is used.

2.

Most short exponents are of the form e = 2n +1 and yes, it is advantageous to use exponents of the form 2n +1 because it makes it easier to find a public key which is a prime and which contain two bits set only. See the below prime that it generates:

p0=21+1=3

p1=22+1=5

p2=24+1=17

p3=28+1=257

p4=216+1=65537

The form 2n +1 makes it faster to get a key.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

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