commit 4ab6c492675ae8cadd151004cd1e51e07d7f89c2
parent 4c29eb21c741ada8593b5266d39b4561b25071b6
Author: Jared Tobin <jared@jtobin.io>
Date: Sat, 12 Aug 2023 11:36:12 -0230
Add 5.33.
Diffstat:
5 files changed, 134 insertions(+), 0 deletions(-)
diff --git a/.ghci b/.ghci
@@ -15,3 +15,5 @@ import Data.Traversable
import qualified Data.Text.IO as TIO
import qualified Data.Text.Encoding as TE
import qualified Data.Text as T
+import Numeric.Natural
+import qualified System.Random.MWC as MWC
diff --git a/README.md b/README.md
@@ -12,4 +12,5 @@ to build binaries. Use `cabal install` to (I think) dump them in
* [Problem Set 2](docs/s2.md)
* [Problem Set 3](docs/s3.md)
* [Problem Set 4](docs/s4.md)
+* [Problem Set 5](docs/s5.md)
diff --git a/cryptopals.cabal b/cryptopals.cabal
@@ -23,6 +23,7 @@ library
Cryptopals.AES
, Cryptopals.Block.Attacks
, Cryptopals.Block.Tools
+ , Cryptopals.DH
, Cryptopals.Digest.Pure.MD4
, Cryptopals.Digest.Pure.SHA
, Cryptopals.MAC
diff --git a/docs/s5.md b/docs/s5.md
@@ -0,0 +1,80 @@
+#### 5.33
+
+The basic Diffie-Hellman algorithm for key exchange between Alice and
+Bob goes as follows. Alice and Bob agree on a cyclic group of some
+particular order to use. They each randomly and independently pick some
+number of times to perform the group operation (which must be less than
+the order of the group) and perform the group operation on the generator
+that number of times, publishing their results. For generator g, Alice's
+number x, and Bob's number y: Alice publishes g ^ x, and Bob publishes g
+^ y.
+
+Each then performs his or her own secret number of additional group
+operations on the other's public result, establishing the key g ^ xy.
+Since the discrete logarithm problem is hard, an eavesdropper can't (for
+an appropriate group) determine how many times either has performed the
+individual group operations, even given g; he can only naïvely calculate
+g ^ (x + y).
+
+For the initial illustration here we're using a decidedly insecure
+group, i.e. the multiplicative group of 16-bit words modulo 37:
+
+ > gen <- MWC.create
+ > let p = 37
+ > let g = 5
+ > a <- fmap (`mod` p) (MWC.uniform gen) :: IO Word16
+ > b <- fmap (`mod` p) (MWC.uniform gen) :: IO Word16
+ > let bigA = g ^ a `mod` p
+ > let bigB = g ^ b `mod` p
+ > let s = bigB ^ a `mod` p
+ > let t = bigA ^ b `mod` p
+ > s == t
+ True
+ > let k = S.sha1 . BP.runPut $ BP.putWord16be s
+ > k
+ ace6f761db204030c1a65c0930bd01fd55ecc429
+
+For the big guns, we can pull out GHC's Natural type, for which
+mwc-random (our preferred random library) can generate something in a
+range. First a modular exponentiation routine:
+
+ -- modified from https://gist.github.com/trevordixon/6788535
+ modexp :: Natural -> Natural -> Natural -> Natural
+ modexp b e m
+ | e == 0 = 1
+ | otherwise =
+ let t = if B.testBit e 0 then b `mod` m else 1
+ in t * modexp ((b * b) `mod` m) (B.shiftR e 1) m `mod` m
+
+and given that (and appropriate p, g), the key exchange:
+
+ > gen <- MWC.create
+ > a <- fmap (`mod` p) (MWC.uniformRM (0, p - 1) gen)
+ > b <- fmap (`mod` p) (MWC.uniformRM (0, p - 1) gen)
+ > let bigA = modexp g a p
+ > let bigB = modexp g b p
+ > let s = modexp bigB a p
+ > let t = modexp bigA b p
+ > s == t
+ True
+
+Our SHA1 function needs a bytestring to operate on, so to hash the
+Natural key we need a quick serialization routine from Naturals
+to ByteString. I happened to write one of these a few years ago
+for [urbit-hob](http://git.jtobin.io/urbit-hob); it serializes in
+little-endian format, and here we'll use a lazy bytestring:
+
+ unroll :: Natural -> BL.ByteString
+ unroll nat = case nat of
+ 0 -> BL.singleton 0
+ _ -> BL.pack (L.unfoldr step nat)
+ where
+ step 0 = Nothing
+ step i = Just (fromIntegral i, i `B.shiftR` 8)
+
+so we can get a key via:
+
+ > let k = S.sha1 $ unroll s
+ > k
+ 6a86b02347be741dfb6f876819022ae1d7adda18
+
diff --git a/lib/Cryptopals/DH.hs b/lib/Cryptopals/DH.hs
@@ -0,0 +1,50 @@
+
+module Cryptopals.DH (
+ p
+ , g
+ , modexp
+
+ , unroll
+ , roll
+ ) where
+
+import Control.Monad.Primitive
+import qualified Control.Monad.Trans.Reader as R
+import qualified Cryptopals.Digest.Pure.SHA as S
+import qualified Data.Binary.Get as BG
+import qualified Data.Binary.Put as BP
+import Data.Bits ((.|.))
+import qualified Data.Bits as B
+import qualified Data.ByteString.Lazy as BL
+import qualified Data.List as L
+import Numeric.Natural
+import qualified System.Random.MWC as MWC
+import GHC.Word (Word16)
+
+-- modified from https://gist.github.com/trevordixon/6788535
+modexp :: Natural -> Natural -> Natural -> Natural
+modexp b e m
+ | e == 0 = 1
+ | otherwise =
+ let t = if B.testBit e 0 then b `mod` m else 1
+ in t * modexp ((b * b) `mod` m) (B.shiftR e 1) m `mod` m
+
+-- little-endian natural serialization
+unroll :: Natural -> BL.ByteString
+unroll nat = case nat of
+ 0 -> BL.singleton 0
+ _ -> BL.pack (L.unfoldr step nat)
+ where
+ step 0 = Nothing
+ step i = Just (fromIntegral i, i `B.shiftR` 8)
+
+roll :: BL.ByteString -> Natural
+roll = foldr unstep 0 . BL.unpack where
+ unstep b a = a `B.shiftL` 8 .|. fromIntegral b
+
+p :: Natural
+p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca237327ffffffffffffffff
+
+g :: Natural
+g = 2
+
