Scott Fluhrer edited untitled.tex  almost 9 years ago

Commit id: 302ca21cb9a0036570c4e4cfb3a7384b5304f8f9

deletions | additions      

       

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. As one might expect, $rn \approx r2^{252} + r2^{104.45}$, r2^{124.4}$,  and if $r < 2^{148}$, 2^{128}$,  then bits 251 and below of $k + nr$ will be strongly correlated to the corresponding bits of $k$ (because those the  bits of $nr$ with nontrivial contributions to those bits of the sum  will be zero). Other special form primes don't have quite as striking of a form (I chose Curve25519 because it makes it obvious), but they too also have long strings of 0's or $b-1$ values at the beginning, which yields the corresponding weakness. However, let us consider what happens if we consider a $b$ which is not a power of 2. For example, if we were to take the same $n$ expressed in base $b=33$, we get: