Scott Fluhrer edited untitled.tex  almost 9 years ago

Commit id: 391c354a18c091068f9de887cb9b5f156a0f96fe

deletions | additions      

       

\item Convert both $t_1$ and $b$ into base-48, giving $t_3$, and $t_4$  \iten Add $t_3$ and $t_4$ together as base-48 numbers, giving $t_5$  \item Compute $t_5G$ (using the base-48 multiplication algorithm outlined earlier), with $r$ being the x-coordinate of the resulting point  \item Compute $u_1 = au$ au \bmod n$  and $u_2 = bu$ bu \bmod n$  \item Compute $u_3 = u_1 + u_2 \bmod n$, and then compute $u_4 = u_3^{-1} \bmod n$  \item Compute $s = u_4u(z + rd)$ (where $z$, $r$ and $d$ have the normal meanings for ECDSA; $z$ is the hash, $r$ is the x-coordinate computed previously, and $d$ is the ECDSA private key).  \end{itemize}  If you go through this procedure, it should be clear that this is effectively the ECDSA signature algorithm (with $k = a+b \bmod n$), and that the internal bits of all the intermediate values are uncorrelated to the bits of $k$, hence we have achieved blinding against first order side channel attacks. In addition, the operations that we have added over the straight-forward ECDSA signature generation with Coron blinding (generating $2\log{n}$ additional random bits, three additional multiplications, one additional binary addition, one addition in base-48, and two base conversions) are relatively cheap (say, compared to computing the multiplicative inverse), and so we haven't increased the expense significantly.