Chapter$7$: Problem $4$

Next Problem

$(1$ point$)$ The speed of RSA hinges on the ability to do large modular exponentiations quickly.

While $e$ can be made small, $d$ generally cannot.

A popular method for fast modular exponentiation is the Square and Multiply algorithm.

Suppose that $N=14981$ and $d=10691.$ We want to use the Square and Multiply algorithm to quickly decrypt $y=9070.$

a$)$ Express $d$ as a binary string $($e$.$g$.10110110).$

b$)$ Supposing that initially $r=y=9070,$ enter the order of square operations $($ SQ $)$ and multiply operations $($MUL$)$ that must be performed on $r$ to compute $y^d$ mod $N.$ Enter as a comma separated list, for example $SQ\frac{,}{M}UL,SQ,SQ,SQ\frac{,}{M}UL,SQ,SQ\frac{,}{M}UL,SQ,SQ.$

c$)$ What is $x=y^d$modN $?$

Solve this problem please