Thursday, November 23, 2017

Cryptopals Set 5 - F#


Set 5 was advertised as difficult, but I found the implementations to be quicker that previous sets as they involve more number theory and less programming.

https://github.com/tkuriyama/cryptopals/tree/master/set5

I took a few implementation shortcuts (each of them a good exercise to do properly, but I'd rather forge ahead and get through the cryptographic concepts at this point):
  • Client-server interactions are simulated (still haven't sorted out F# package manager yet)
  • Prime numbers are drawn from known list rather than generated 
  • Cube root solving is ignored (p40 just tests the result against the cube of the original message, rather than testing the cube root of the result against the original message)
I spent some time trying to implement Newton's method of approximating roots, which worked fine for square roots but in my implementation almost always did not converge for cube roots (once a guess became negative, it stayed negative... how to constrain to positive numbers while improving the guess in each iteration?). Something else to investigate in the future.