diff options
| author | Dennis Brentjes <d.brentjes@gmail.com> | 2017-05-15 13:10:01 +0200 |
|---|---|---|
| committer | Dennis Brentjes <d.brentjes@gmail.com> | 2017-05-15 13:10:01 +0200 |
| commit | 07345c637a79daf3ffb0e5e1a2de22815d0a3693 (patch) | |
| tree | 9e494a2201fc34fbd36bb30d84f304d3cae9b419 /content/implementation.tex | |
| parent | d1e611a70c6c273d007e4aac0b3ed98cd627d0c1 (diff) | |
| download | thesis-07345c637a79daf3ffb0e5e1a2de22815d0a3693.tar.gz thesis-07345c637a79daf3ffb0e5e1a2de22815d0a3693.tar.bz2 thesis-07345c637a79daf3ffb0e5e1a2de22815d0a3693.zip | |
started discussion part of the thesis.
Diffstat (limited to 'content/implementation.tex')
| -rw-r--r-- | content/implementation.tex | 4 |
1 files changed, 2 insertions, 2 deletions
diff --git a/content/implementation.tex b/content/implementation.tex index f2ad497..1da07de 100644 --- a/content/implementation.tex +++ b/content/implementation.tex @@ -22,9 +22,9 @@ You can map a point back to the original string by dividing the y coordinate wit The problem with this probabilistic Koblitz's method is choosing your ``stride''. There is no way of knowing what the max distance between two consecutive suitable y coordinates could be, half of the possible group elements would be suitable, but it is impossible to list all the Ed25519 curve points and check. This makes it an unsolvable problem, but we can make educated guesses and stay on the safe side of those guesses. -Now to address the concern that the you divide your message space by your stride. By doing this you also effect your throughput. Atleast it would if you would optimally pack your messages in the 252 bits you have when using Ed25519. If you only use the lower 248 bits however, which gives you 31 byte messages. you have 4 bits to use as a stride. Which, anecdotally, seems to be enough. Ofcourse you can never know if this stride will work for all possible messages. But for the purpose of this benchmark it seems to work well enough. Maybe it is possible to find out how stride influences the chance of not finding a suitable y coordinate. But that is outside of the scope of this research. +Now to address the concern that the you divide your message space by your stride. By doing this you also effect your throughput. Atleast it would if you would optimally pack your messages in the 252 bits you have when using Ed25519. If you only use the lower 248 bits however, which gives you 31 byte messages. you have 5 bits to use as a stride. Which, anecdotally, seems to be enough. Ofcourse you can never know if this stride will work for all possible messages. But for the purpose of this benchmark it seems to work well enough. Maybe it is possible to find out how stride influences the chance of not finding a suitable y coordinate. But that is outside of the scope of this research. -A couple of small but nice benefits of using $16$ as stride. Multiplication and division are bit shifts as $16$ is a power of $2$. And all the output in hexadecimal numbers are shifted by 1 character. This makes some of the debugging process easier on the mind, but are minor considerations compared to making the stride large enough to actually make the chance of an unmapable input as small as possible. +A couple of small but nice benefits of using $32$ as stride. Multiplication and division are bit shifts as $32$ is a power of $2$. For debugging purposes you might want to consider a stride of $16$. This makes any hexadecimal representation of a number just shift up one character. However in actual runs of the algorithm some runs would fail because there was no suitable $y$ coordinate within $16$ values of the message value. This has not yet happened for $32$. Again this is no guarantee that it will never happen though. \subsection{Debugging the cmix operations.} |
