commit 67c35aa9cbe9074d927086e6d46f7e3b64004354
parent 81575fff837bdf0b5666a5ef852000db57823308
Author: Jared Tobin <jared@jtobin.io>
Date: Mon, 21 Aug 2023 14:05:04 -0230
Add signature facilities for RSA.
Diffstat:
2 files changed, 109 insertions(+), 7 deletions(-)
diff --git a/docs/s5.md b/docs/s5.md
@@ -363,13 +363,13 @@ less than 1 / 2^128.
I used cryptonite's Crypto.Number.Prime module, which implements the
above procedure.
-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" or "coprime"
-means, for two numbers 'a' and 'b', that they have a greatest common
-denominator of 1.
+In any case, RSA: one finds two k-bit primes, 'p' and 'q', and uses
+their product to construct a public modulus n = pq and value `t = (p -
+1) (q - 1)`. The public key is (n, e) for 'e' a number relatively prime
+to 't', and the private key is (n, d), for d such that `ed = 1 mod t`
+(i.e., 'd' is congruent mod 't' to the inverse of 'e'). "Relatively
+prime" or "coprime" 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,
diff --git a/lib/Cryptopals/RSA.hs b/lib/Cryptopals/RSA.hs
@@ -8,15 +8,26 @@ module Cryptopals.RSA (
, invmod
, invmod'
+
, encrypt
, decrypt
+
+ , pkcs1v1p5encode
+ , pkcs1v1p5verify
+
+ , sign
+ , verify
+ , sign'
+ , verify'
) where
import qualified Cryptopals.DH as DH
+import qualified Cryptopals.Digest.Pure.SHA as CS
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 qualified Data.ByteString.Lazy as BL
import Data.List (unfoldr)
import Numeric.Natural
@@ -55,6 +66,7 @@ invmod (fromIntegral -> a) (fromIntegral -> m)
| x < 0 = fromIntegral (x + m)
| otherwise = fromIntegral x
+-- unsafe invmod
invmod' :: Natural -> Natural -> Natural
invmod' a m = case invmod a m of
Just x -> x
@@ -93,3 +105,93 @@ decrypt key cip = case key of
Pub {} -> error "decrypt: need secret key"
Sec d n -> unroll (DH.modexp (roll cip) d n)
+-- sign without padding
+sign' :: Key -> BS.ByteString -> (BS.ByteString, BS.ByteString)
+sign' key msg = case key of
+ Pub {} -> error "sign': need secret key"
+ Sec d n ->
+ let h = fromIntegral $ CS.integerDigest (CS.sha512 (BL.fromStrict msg))
+ in (msg, unroll (DH.modexp h d n))
+
+-- verify without padding
+verify' :: Key -> BS.ByteString -> BS.ByteString -> Bool
+verify' key msg sig = case key of
+ Sec {} -> error "verify': need public key"
+ Pub e n ->
+ let h = fromIntegral $ CS.integerDigest (CS.sha512 (BL.fromStrict msg))
+ in h == DH.modexp (roll sig) e n
+
+sign :: Key -> BS.ByteString -> (BS.ByteString, BS.ByteString)
+sign key msg = case key of
+ Pub {} -> error "sign: need secret key"
+ Sec d n ->
+ let padded = pkcs1v1p5encode key msg
+ in (msg, unroll (DH.modexp (roll padded) d n))
+
+verify :: Key -> BS.ByteString -> BS.ByteString -> Bool
+verify key msg sig = case key of
+ Sec {} -> error "verify: need public key"
+ Pub e n ->
+ let h = BL.toStrict $ CS.bytestringDigest (CS.sha512 (BL.fromStrict msg))
+ r = DH.modexp (roll sig) e n
+ in case pkcs1v1p5verify (unroll r) of
+ Nothing -> False
+ Just l -> h == l
+
+-- pkcs#1 v1.5-encode a message
+pkcs1v1p5encode :: Key -> BS.ByteString -> BS.ByteString
+pkcs1v1p5encode key msg =
+ BS.cons 0x00 (BS.snoc (BS.cons 0x01 ffs) 0x00) <> asnSha512 <> has
+ where
+ siz = case key of
+ Pub _ n -> BS.length (unroll n)
+ Sec _ n -> BS.length (unroll n)
+ len = fromIntegral siz - (3 + BS.length (asnSha512 <> has))
+ ffs = BS.replicate len 0xff
+ has = BL.toStrict $ CS.bytestringDigest (CS.sha512 (BL.fromStrict msg))
+
+-- sloppy pkcs#1 v1.5 verification; doesn't check message terminates
+-- after hash
+pkcs1v1p5verify :: BS.ByteString -> Maybe BS.ByteString
+pkcs1v1p5verify = checknul where
+ checknul bs = case BS.uncons bs of
+ Nothing -> Nothing
+ Just (w, etc)
+ | w == 0x00 -> checksoh etc
+ | otherwise -> Nothing
+
+ checksoh bs = case BS.uncons bs of
+ Nothing -> Nothing
+ Just (w, etc)
+ | w == 0x01 -> check255 etc
+ | otherwise -> Nothing
+
+ check255 bs = case BS.uncons bs of
+ Nothing -> Nothing
+ Just (w, etc)
+ | w == 0xff -> check255 etc
+ | w == 0x00 -> checkasn asnSha512 etc
+ | otherwise -> Nothing
+
+ checkasn asn bs = case BS.uncons bs of
+ Nothing -> Nothing
+ Just (w, etc) -> case BS.uncons asn of
+ Nothing -> checkhash bs
+ Just (h, t)
+ | w == h -> checkasn t etc
+ | otherwise -> Nothing
+
+ checkhash bs =
+ let has = BS.take 64 bs
+ in if BS.length has == 64
+ then pure has
+ else Nothing
+
+-- ASN.1 encoding of SHA512
+asnSha512 :: BS.ByteString
+asnSha512 = BS.pack [
+ 0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48
+ , 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x05, 0x00, 0x04
+ , 0x40
+ ]
+
