Scott Fluhrer edited untitled.tex  almost 9 years ago

Commit id: 5e68094b992d1d4ffb3762df4478aaa3e07959a6

deletions | additions      

       

\item The operation of multiplying a point by $b$ can be efficiently done by doing $m$ point doublings  \end{itemize}  However, if we look at that value of $n$ expressed in such a base $b$ if the prime has special structure, we see a regular pattern. For example, the value of $n$ for the Elliptic Curve Curve25519 (which has the special form prime $2^{255}-19$)  for $b=32$ is: 04 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00\  00 00 00 20 27 27 28 29 29 08 23 23 19 19 11 05 16 04 19 03 03 09 14\  15 11 20 31 13  Note the long string of zero's at the beginning; these are what makes scalar randomization less effective. Other special form primes also have long strings of 0's or $b-1$ values at the beginning.  However, let us consider what happens if we consider a $b$ which is not a power of 2. For example,  if we were to consider take  the same $n$ for $b=33$, we get: 28 11 05 18 10 15 07 20 27 20 16 24 12 03 10 09 25 17 04 17 16 19 31\  26 11 07 00 31 07 22 23 00 16 27 29 01 25 17 10 19 05 30 17 19 16 08\  07 06 05 01  Here, we don't get any regular pattern, and this value would, at first glance, appear random.  - Non-power of 2