{-# LANGUAGE ScopedTypeVariables #-}

-- |
-- Module      : Crypto.PubKey.RSA
-- License     : BSD-style
-- Maintainer  : Vincent Hanquez <vincent@snarc.org>
-- Stability   : experimental
-- Portability : Good
module Crypto.PubKey.RSA (
    Error (..),
    PublicKey (..),
    PrivateKey (..),
    Blinder (..),

    -- * Generation function
    generateWith,
    generate,
    generateBlinder,
) where

import Crypto.Internal.ByteArray (ScrubbedBytes)
import Crypto.Number.Generate (generateMax)
import Crypto.Number.ModArithmetic (
    expSafe,
    inverse,
    inverseCoprimes,
    inverseSafe,
 )
import Crypto.Number.Prime (generatePrime)
import Crypto.Number.Serialize (os2ip)
import Crypto.PubKey.RSA.Types
import Crypto.Random.Types

{-
-- some bad implementation will not serialize ASN.1 integer properly, leading
-- to negative modulus.
-- TODO : Find a better place for this
toPositive :: Integer -> Integer
toPositive int
    | int < 0   = uintOfBytes $ bytesOfInt int
    | otherwise = int
  where uintOfBytes = foldl (\acc n -> (acc `shiftL` 8) + fromIntegral n) 0
        bytesOfInt :: Integer -> [Word8]
        bytesOfInt n = if testBit (head nints) 7 then nints else 0xff : nints
          where nints = reverse $ plusOne $ reverse $ map complement $ bytesOfUInt (abs n)
                plusOne []     = [1]
                plusOne (x:xs) = if x == 0xff then 0 : plusOne xs else (x+1) : xs
                bytesOfUInt x = reverse (list x)
                  where list i = if i <= 0xff then [fromIntegral i] else (fromIntegral i .&. 0xff) : list (i `shiftR` 8)
-}

-- | Generate a key pair given p and q.
--
-- p and q need to be distinct prime numbers.
--
-- e need to be coprime to phi=(p-1)*(q-1). If that's not the
-- case, the function will not return a key pair.
-- A small hamming weight results in better performance.
--
-- * e=0x10001 is a popular choice
--
-- * e=3 is popular as well, but proven to not be as secure for some cases.
--
-- /WARNING:/ Making a key is not constant time, and cannot be: the search for
-- the two primes takes as long as it takes, and 'Crypto.Number.Prime' is not
-- constant time either.  What that leaks is about the search rather than
-- about the primes it settles on.  Of the arithmetic that does touch them,
-- the inverse of one prime modulo the other is worked out without a side
-- channel, and so is the private exponent, which is the inverse of @e@ modulo
-- @(p-1)*(q-1)@: @e@ being public lets that be worked out as a remainder, an
-- inverse modulo @e@ itself, and an exact division, none of which follows the
-- number being inverted.  An @e@ that is not prime keeps the extended
-- Euclidean algorithm, which for a public @e@ is one division by a small
-- number and then a few steps on numbers under it.
generateWith
    :: (Integer, Integer)
    -- ^ chosen distinct primes p and q
    -> Int
    -- ^ size in bytes
    -> Integer
    -- ^ RSA public exponent @e@
    -> Maybe (PublicKey, PrivateKey)
generateWith :: (Integer, Integer)
-> Int -> Integer -> Maybe (PublicKey, PrivateKey)
generateWith (Integer
p, Integer
q) Int
size Integer
e =
    case Maybe Integer
privateExponent of
        Maybe Integer
Nothing -> Maybe (PublicKey, PrivateKey)
forall a. Maybe a
Nothing
        Just Integer
d -> (PublicKey, PrivateKey) -> Maybe (PublicKey, PrivateKey)
forall a. a -> Maybe a
Just (PublicKey
pub, Integer -> PrivateKey
priv Integer
d)
  where
    n :: Integer
n = Integer
p Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
q
    phi :: Integer
phi = (Integer
p Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* (Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1)
    -- The private exponent is the inverse of e modulo phi, and phi is the
    -- key.  The extended Euclidean algorithm would take a number of steps
    -- that follows it; e being public lets the work be about e instead.
    --
    -- Whatever d is, e * d = 1 + k * phi for some k under e, and reading that
    -- modulo e gives k = -phi^-1 mod e -- an inverse modulo a number of a
    -- handful of bits, which for a prime e is Fermat.  Then d is an exact
    -- division by e.  Nothing in that follows phi: the remainder and the
    -- division are one pass each over its limbs, and the rest is arithmetic
    -- the size of e.
    --
    -- Fermat wants a prime e, and rather than ask whether e is one -- which
    -- costs more than everything else here -- the k it gives is checked,
    -- which is arithmetic the size of e.  A composite e that fails the check
    -- keeps the algorithm it had.
    privateExponent :: Maybe Integer
privateExponent
        | Integer
e Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
1 = Maybe Integer
forall a. Maybe a
Nothing
        | Integer
t Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = Maybe Integer
forall a. Maybe a
Nothing -- e divides phi, so there is no inverse
        | (Integer
k Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
t) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
e Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
e Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1 = Integer -> Maybe Integer
forall a. a -> Maybe a
Just ((Integer
1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
k Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
phi) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` Integer
e)
        | Bool
otherwise = Integer -> Integer -> Maybe Integer
inverse Integer
e Integer
phi
      where
        t :: Integer
t = Integer
phi Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
e
        k :: Integer
k = (Integer
e Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer -> Integer -> Integer -> Integer
expSafe Integer
t (Integer
e Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
2) Integer
e) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
e
    -- q and p should be *distinct* *prime* numbers, hence always coprime.
    -- Both of them are the key itself, so the inverse is worked out through
    -- Fermat's little theorem rather than the extended Euclidean algorithm,
    -- whose steps follow the numbers it is given.  It falls back on the one
    -- that raises, which is what a p that is not prime deserves.
    qinv :: Integer
qinv = case Integer -> Integer -> Maybe Integer
inverseSafe Integer
q Integer
p of
        Just Integer
i -> Integer
i
        Maybe Integer
Nothing -> Integer -> Integer -> Integer
inverseCoprimes Integer
q Integer
p
    pub :: PublicKey
pub =
        PublicKey
            { public_size :: Int
public_size = Int
size
            , public_n :: Integer
public_n = Integer
n
            , public_e :: Integer
public_e = Integer
e
            }
    priv :: Integer -> PrivateKey
priv Integer
d =
        PrivateKey
            { private_pub :: PublicKey
private_pub = PublicKey
pub
            , private_d :: Integer
private_d = Integer
d
            , private_p :: Integer
private_p = Integer
p
            , private_q :: Integer
private_q = Integer
q
            , private_dP :: Integer
private_dP = Integer
d Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` (Integer
p Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1)
            , private_dQ :: Integer
private_dQ = Integer
d Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` (Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1)
            , private_qinv :: Integer
private_qinv = Integer
qinv
            }

-- | generate a pair of (private, public) key of size in bytes.
generate
    :: MonadRandom m
    => Int
    -- ^ size in bytes
    -> Integer
    -- ^ RSA public exponent @e@
    -> m (PublicKey, PrivateKey)
generate :: forall (m :: * -> *).
MonadRandom m =>
Int -> Integer -> m (PublicKey, PrivateKey)
generate Int
size Integer
e = m (PublicKey, PrivateKey)
loop
  where
    loop :: m (PublicKey, PrivateKey)
loop = do
        -- loop until we find a valid key pair given e
        (Integer, Integer)
pq <- m (Integer, Integer)
generatePQ
        case (Integer, Integer)
-> Int -> Integer -> Maybe (PublicKey, PrivateKey)
generateWith (Integer, Integer)
pq Int
size Integer
e of
            Maybe (PublicKey, PrivateKey)
Nothing -> m (PublicKey, PrivateKey)
loop
            Just (PublicKey, PrivateKey)
pp -> (PublicKey, PrivateKey) -> m (PublicKey, PrivateKey)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (PublicKey, PrivateKey)
pp
    generatePQ :: m (Integer, Integer)
generatePQ = do
        Integer
p <- Int -> m Integer
forall (m :: * -> *). MonadRandom m => Int -> m Integer
generatePrime (Int
8 Int -> Int -> Int
forall a. Num a => a -> a -> a
* (Int
size Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2))
        Integer
q <- Integer -> m Integer
forall {m :: * -> *}. MonadRandom m => Integer -> m Integer
generateQ Integer
p
        (Integer, Integer) -> m (Integer, Integer)
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Integer
p, Integer
q)
    generateQ :: Integer -> m Integer
generateQ Integer
p = do
        Integer
q <- Int -> m Integer
forall (m :: * -> *). MonadRandom m => Int -> m Integer
generatePrime (Int
8 Int -> Int -> Int
forall a. Num a => a -> a -> a
* (Int
size Int -> Int -> Int
forall a. Num a => a -> a -> a
- (Int
size Int -> Int -> Int
forall a. Integral a => a -> a -> a
`div` Int
2)))
        if Integer
p Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
q then Integer -> m Integer
generateQ Integer
p else Integer -> m Integer
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return Integer
q

-- | Generate a blinder to use with decryption and signing operation
--
-- the unique parameter apart from the random number generator is the
-- public key value N.
--
-- The blinder holds a random number and its inverse.  N is composite, so
-- Fermat has no answer for the inverse and it goes through the extended
-- Euclidean algorithm, whose steps follow the number handed to it -- which
-- would be the number the blinding rests on.  So the algorithm is handed that
-- number multiplied by another random one instead, and its answer multiplied
-- by that number again, which leaves the inverse wanted and shows the
-- algorithm nothing that has anything to do with it.
generateBlinder
    :: forall m
     . MonadRandom m
    => Integer
    -- ^ RSA public N parameter.
    -> m Blinder
generateBlinder :: forall (m :: * -> *). MonadRandom m => Integer -> m Blinder
generateBlinder Integer
n = do
    Integer
r <- Integer -> m Integer
forall {m :: * -> *}. MonadRandom m => Integer -> m Integer
generateMax Integer
n
    -- The inverse goes through the extended Euclidean algorithm, whose steps
    -- follow the number handed to it, and r is what the blinding rests on.
    -- So another random number goes with it: the product is uniform and says
    -- nothing about r on its own, and multiplying its inverse by that number
    -- again leaves the inverse of r.  Sixteen bytes are enough to hide it and
    -- are under either prime, so the product is coprime with n whenever r is,
    -- as it was before.
    Integer
u <- ScrubbedBytes -> Integer
forall ba. ByteArrayAccess ba => ba -> Integer
os2ip (ScrubbedBytes -> Integer) -> m ScrubbedBytes -> m Integer
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (Int -> m ScrubbedBytes
forall byteArray. ByteArray byteArray => Int -> m byteArray
forall (m :: * -> *) byteArray.
(MonadRandom m, ByteArray byteArray) =>
Int -> m byteArray
getRandomBytes Int
16 :: m ScrubbedBytes)
    let v :: Integer
v = (Integer
r Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
u) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
n
        rm1 :: Integer
rm1 = (Integer -> Integer -> Integer
inverseCoprimes Integer
v Integer
n Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
u) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
n
    Blinder -> m Blinder
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return (Blinder -> m Blinder) -> Blinder -> m Blinder
forall a b. (a -> b) -> a -> b
$ Integer -> Integer -> Blinder
Blinder Integer
r Integer
rm1