commit 036cd862f1a7ee69895219e74134958eb9a6a22c
parent 5e5e1796203eebf3ff4ff65306818f0051ede424
Author: Jared Tobin <jared@jtobin.io>
Date: Sat, 19 Aug 2023 08:45:33 -0230
Add 5.39.
Diffstat:
4 files changed, 138 insertions(+), 18 deletions(-)
diff --git a/cryptopals.cabal b/cryptopals.cabal
@@ -32,6 +32,7 @@ library
, Cryptopals.Digest.Pure.SHA
, Cryptopals.MAC
, Cryptopals.MAC.Attacks
+ , Cryptopals.RSA
, Cryptopals.SRP
, Cryptopals.SRP.Simple
, Cryptopals.Stream.Attacks
diff --git a/docs/s5.md b/docs/s5.md
@@ -350,3 +350,58 @@ the result pretty quickly:
(cryptopals) success
(cryptopals) password: omniana
+#### 5.39
+
+A note on primegen for RSA: I didn't bother with it, as recommended, but
+looked at how it should be done. It doesn't seem that bad; one generates
+a sufficiently large random number, then tests that it isn't divisible
+by the first serveral hundred primes, then performs a probabilistic
+primality test sufficiently many times that the error probability is
+very small. A reference suggested that the error probability should be
+less than 1 / 2^128.
+
+I used cryptonite's Crypto.Number.Prime module, which implements the
+above procedure.
+
+In any case, everything else is pretty straightforward. To go from
+Natural to ByteString and back I used some old functions (roll, unroll)
+I wrote for [urbit-hob](http://git.jtobin.io/urbit-hob) a few years
+back:
+
+ data Key = Key Natural Natural
+ deriving (Eq, Show)
+
+ data Keypair = Keypair {
+ sec :: Key
+ , pub :: Key
+ } deriving (Eq, Show)
+
+ keygen :: Int -> IO Keypair
+ keygen siz = loop where
+ loop = do
+ p <- fromIntegral <$> P.generatePrime siz
+ q <- fromIntegral <$> P.generatePrime siz
+ let n = p * q
+ et = pred p * pred q
+ e = 3
+ md = invmod e et
+ case md of
+ Nothing -> loop
+ Just d -> pure $ Keypair (Key e n) (Key d n)
+
+ encrypt :: Key -> BS.ByteString -> BS.ByteString
+ encrypt (Key e n) m = unroll (DH.modexp (roll m) e n)
+
+ decrypt :: Key -> BS.ByteString -> BS.ByteString
+ decrypt (Key d n) c = unroll (DH.modexp (roll c) d n)
+
+Works fine:
+
+ > Keypair sec pub <- keygen 1024
+ > let cip = encrypt pub "secret!"
+ > TIO.putStrLn $ T.take 32 $ B64.encodeBase64 cip
+ zZFjaw7BR6rP0EaNsTFRnCInwsghANrE
+ > let msg = decrypt sec cip
+ > msg
+ "secret!"
+
diff --git a/lib/Cryptopals/RSA.hs b/lib/Cryptopals/RSA.hs
@@ -0,0 +1,80 @@
+module Cryptopals.RSA (
+ invmod
+ , unroll
+ , roll
+
+ , keygen
+ , encrypt
+ , decrypt
+ ) where
+
+import qualified Cryptopals.DH as DH
+import qualified Crypto.Number.Prime as P
+import qualified Data.Binary as DB
+import qualified Data.Bits as B
+import qualified Data.ByteString as BS
+import Data.List (unfoldr)
+import Numeric.Natural
+
+-- | Simple little-endian ByteString encoding for Naturals.
+unroll :: Natural -> BS.ByteString
+unroll nat = case nat of
+ 0 -> BS.singleton 0
+ _ -> BS.pack (unfoldr step nat)
+ where
+ step 0 = Nothing
+ step i = Just (fromIntegral i, i `B.shiftR` 8)
+
+-- | Simple little-endian ByteString decoding for Naturals.
+roll :: BS.ByteString -> Natural
+roll = foldr unstep 0 . BS.unpack where
+ unstep b a = a `B.shiftL` 8 B..|. fromIntegral b
+
+-- egcd/invmod adapted from https://rosettacode.org/wiki/Modular_inverse
+
+-- for a, b, return x, y, g such that ax + by = g for g = gcd(a, b)
+egcd :: Integer -> Integer -> (Integer, Integer, Integer)
+egcd a 0 = (1, 0, a)
+egcd a b =
+ let (q, r) = a `quotRem` b
+ (s, t, g) = egcd b r
+ in (t, s - q * t, g)
+
+-- for a, m return x such that ax = 1 mod m
+invmod :: Natural -> Natural -> Maybe Natural
+invmod (fromIntegral -> a) (fromIntegral -> m)
+ | 1 == g = Just (pos i)
+ | otherwise = Nothing
+ where
+ (i, _, g) = egcd a m
+ pos x
+ | x < 0 = fromIntegral (x + m)
+ | otherwise = fromIntegral x
+
+data Key = Key Natural Natural
+ deriving (Eq, Show)
+
+data Keypair = Keypair {
+ sec :: Key
+ , pub :: Key
+ } deriving (Eq, Show)
+
+keygen :: Int -> IO Keypair
+keygen siz = loop where
+ loop = do
+ p <- fromIntegral <$> P.generatePrime siz
+ q <- fromIntegral <$> P.generatePrime siz
+ let n = p * q
+ et = pred p * pred q
+ e = 3
+ md = invmod e et
+ case md of
+ Nothing -> loop
+ Just d -> pure $ Keypair (Key e n) (Key d n)
+
+encrypt :: Key -> BS.ByteString -> BS.ByteString
+encrypt (Key e n) m = unroll (DH.modexp (roll m) e n)
+
+decrypt :: Key -> BS.ByteString -> BS.ByteString
+decrypt (Key d n) c = unroll (DH.modexp (roll c) d n)
+
diff --git a/lib/Cryptopals/SRP/Simple.hs b/lib/Cryptopals/SRP/Simple.hs
@@ -15,7 +15,6 @@ import qualified Data.ByteString as BS
import qualified Data.ByteString.Base16 as B16
import qualified Data.ByteString.Lazy as BL
import qualified Data.ByteString.Lazy.Char8 as BL8
-import qualified Data.HashMap.Lazy as HML
import qualified Data.Text as T
import qualified Data.Text.Encoding as TE
import qualified Data.Text.IO as TIO
@@ -350,26 +349,11 @@ mitm cmd = do
Nothing -> do
slog "missing required parameters"
pure End
- Just herpub -> do
- slog $ "USiNg PaRaMeTeRs " <> (T.pack . show) herpub
+ Just (T.pack . show -> herpub) -> do
+ slog $ "USiNg PaRaMeTeRs " <> herpub
<> " aNd " <> B16.encodeBase16 mac
slog "GoINg ofFLinE.."
pure End
_ -> srpsimple cmd
-populate
- :: MonadIO m
- => Natural
- -> ReaderT Env m (HML.HashMap BL.ByteString BL.ByteString)
-populate herpub = do
- Env {..} <- ask
- dict <- liftIO $ BL8.readFile "/usr/share/dict/words"
- let ls = BL8.lines dict
- ns = fmap (fromIntegral . CS.integerDigest . CS.sha256) ls :: [Natural]
- ss = fmap (\x -> herpub * DH.modexp eg x en) ns
- hs = fmap (CS.bytestringDigest . CS.sha256 . DB.encode) ss
- ms = fmap (\s -> CS.bytestringDigest (CS.hmacSha256 s mempty)) hs
-
- pure . HML.fromList $ zip ms ls
-
