commit 366d50d1b96c53baebf425aa76bc5a955db3cc1a
parent 036cd862f1a7ee69895219e74134958eb9a6a22c
Author: Jared Tobin <jared@jtobin.io>
Date: Sat, 19 Aug 2023 18:25:29 -0230
Add 5.40.
Diffstat:
3 files changed, 79 insertions(+), 11 deletions(-)
diff --git a/cryptopals.cabal b/cryptopals.cabal
@@ -51,6 +51,7 @@ library
, containers
, cryptonite
, HTTP
+ , integer-roots
, mwc-random
, network
, network-simple
diff --git a/docs/s5.md b/docs/s5.md
@@ -353,7 +353,7 @@ the result pretty quickly:
#### 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
+looked at how it should be done. It seems straightforward; 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
@@ -363,10 +363,17 @@ 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:
+In any case, RSA: one finds two n-bit primes, 'p' and 'q', and uses
+their product to construct a modulus N = (p - 1) (q - 1). The public
+key is (N, e) for 'e' a number relatively prime to that modulus, and
+the private key is (N, d), for d such that ed = 1 mod N (i.e., 'd' is
+congruent mod N to the inverse of e). "Relatively prime" means, for two
+numbers 'a' and 'b', that they have a greatest common denominator of 1.
+
+Encryption and decryption are then just modular exponentiation
+operations using the keys. To go from Natural to ByteString and back,
+I used some old functions -- roll and unroll -- that I wrote for
+[urbit-hob](http://git.jtobin.io/urbit-hob) a few years back:
data Key = Key Natural Natural
deriving (Eq, Show)
@@ -387,13 +394,13 @@ back:
md = invmod e et
case md of
Nothing -> loop
- Just d -> pure $ Keypair (Key e n) (Key d n)
+ Just d -> pure $ Keypair (Key d n) (Key e 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)
+ decrypt = encrypt
Works fine:
@@ -405,3 +412,58 @@ Works fine:
> msg
"secret!"
+The Cryptopals.RSA module exports the keygen, encrypt, and decrypt
+functions, as well as invmod and roll & unroll.
+
+#### 5.40
+
+The problem behind the Chinese Remainder Theorem, as formulated by one
+孫子 and passed on to me via Wikipedia, is:
+
+> There are certain things whose number is unknown. If we count them by
+> threes, we have two left over; by fives, we have three left over; and
+> by sevens, two are left over. How many things are there?
+
+I.e. what is x, if x is congruent to 2 mod 3, 3 mod 5, and 2 mod 7?
+
+In Sunzi's case the answer is congruent to 23 mod 105, and the Chinese
+Remainder Theorem states that such a solution always exists given
+certain conditions (notably that the moduli are pairwise coprime).
+
+In our case, for plaintext 'm' and ciphertexts c0, c1, and c2, we have
+that m ^ 3 is congruent modulo to c0 mod n0, c1 mod n1, and c2 mod n2.
+The Chinese Remainder Theorem asserts that there exists some 'c' that is
+congruent to m ^ 3 modulo `n0 * n1 * n2`. The trick here (this is known
+as Håstad's attack, apparently) is that since m is smaller than every n,
+we have that m ^ 3 is smaller than `n0 * n1 * n2`, and so that 'c' is
+precisely equal to m ^ 3, rather than congruent to it.
+
+So, following the CRT construction:
+
+ > let msg = "attack at 10pm"
+ >
+ > Keypair _ p0@(Key e0 n0) <- keygen 1024
+ > Keypair _ p1@(Key e1 n1) <- keygen 1024
+ > Keypair _ p2@(Key e2 n2) <- keygen 1024
+ >
+ > let c0 = encrypt p0 msg
+ > let c1 = encrypt p1 msg
+ > let c2 = encrypt p2 msg
+ >
+ > let ms0 = n1 * n2
+ > let ms1 = n0 * n2
+ > let ms2 = n0 * n1
+ >
+ > :{
+ > let res = (roll c0 * ms0 * M.fromJust (invmod ms0 n0)
+ > + roll c1 * ms1 * M.fromJust (invmod ms1 n1)
+ > + roll c2 * ms2 * M.fromJust (invmod ms2 n2))
+ > `mod`
+ > (n0 * n1 * n2)
+ > :}
+
+The 'integer-roots' package provides a helpful cube root function:
+
+ > unroll $ R.integerCubeRoot res
+ "attack at 10pm"
+
diff --git a/lib/Cryptopals/RSA.hs b/lib/Cryptopals/RSA.hs
@@ -1,9 +1,12 @@
module Cryptopals.RSA (
- invmod
+ Key(..)
+ , Keypair(..)
+ , keygen
+
, unroll
, roll
- , keygen
+ , invmod
, encrypt
, decrypt
) where
@@ -14,6 +17,8 @@ import qualified Data.Binary as DB
import qualified Data.Bits as B
import qualified Data.ByteString as BS
import Data.List (unfoldr)
+import qualified Data.Maybe as M
+import qualified Math.NumberTheory.Roots as R
import Numeric.Natural
-- | Simple little-endian ByteString encoding for Naturals.
@@ -70,11 +75,11 @@ keygen siz = loop where
md = invmod e et
case md of
Nothing -> loop
- Just d -> pure $ Keypair (Key e n) (Key d n)
+ Just d -> pure $ Keypair (Key d n) (Key e 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)
+decrypt = encrypt
