Module Mirage_crypto_pk.Rsa

RSA public-key cryptography algorithm.

Keys

Messages are checked not to exceed the key size, and this is signalled via the Insufficient_key exception.

Private-key operations are optionally protected through RSA blinding.

exception Insufficient_key

Raised if the key is too small to transform the given message, i.e. if the numerical interpretation of the (potentially padded) message is not smaller than the modulus.

type pub = private {
  1. e : Z.t;
    (*

    Public exponent

    *)
  2. n : Z.t;
    (*

    Modulus

    *)
}

The public portion of the key.

val pub : e:Z.t -> n:Z.t -> (pub, [> `Msg of string ]) Stdlib.result

pub ~e ~n validates the public key: 1 < e < n, n > 0, is_odd n, and numbits n >= 89 (a requirement for PKCS1 operations).

type priv = private {
  1. e : Z.t;
    (*

    Public exponent

    *)
  2. d : Z.t;
    (*

    Private exponent

    *)
  3. n : Z.t;
    (*

    Modulus (p q)

    *)
  4. p : Z.t;
    (*

    Prime factor p

    *)
  5. q : Z.t;
    (*

    Prime factor q

    *)
  6. dp : Z.t;
    (*

    d mod (p-1)

    *)
  7. dq : Z.t;
    (*

    d mod (q-1)

    *)
  8. q' : Z.t;
    (*

    q^(-1) mod p

    *)
}

Full private key (two-factor version).

Note The key layout assumes that p > q, which affects the quantity q' (sometimes called u), and the computation of the private transform. Some systems assume otherwise. When using keys produced by a system that computes u = p^(-1) mod q, either exchange p with q and dp with dq, or re-generate the full private key using priv_of_primes.

val priv : e:Z.t -> d:Z.t -> n:Z.t -> p:Z.t -> q:Z.t -> dp:Z.t -> dq:Z.t -> q':Z.t -> (priv, [> `Msg of string ]) Stdlib.result

priv ~e ~d ~n ~p ~q ~dp ~dq ~q' validates the private key: e, n must be a valid pub, p and q valid prime numbers > 0, odd, probabilistically prime, p <> q, n = p * q, e probabilistically prime and coprime to both p and q, q' = q ^ -1 mod p, 1 < d < n, dp = d mod (p - 1), dq = d mod (q - 1), and d = e ^ -1 mod (p - 1) (q - 1).

val pub_bits : pub -> int

Bit-size of a public key.

val priv_bits : priv -> int

Bit-size of a private key.

val priv_of_primes : e:Z.t -> p:Z.t -> q:Z.t -> (priv, [> `Msg of string ]) Stdlib.result

priv_of_primes ~e ~p ~q is the private key derived from the minimal description (e, p, q).

val priv_of_exp : ?g:Mirage_crypto_rng.g -> ?attempts:int -> e:Z.t -> d:Z.t -> n:Z.t -> unit -> (priv, [> `Msg of string ]) Stdlib.result

priv_of_exp ?g ?attempts ~e ~d n is the unique private key characterized by the public (e) and private (d) exponents, and modulus n. This operation uses a probabilistic process that can fail to recover the key.

~attempts is the number of trials. For triplets that form an RSA key, the probability of failure is at most 2^(-attempts). attempts defaults to an unspecified number that yields a very high probability of recovering valid keys.

Note that no time masking is done for the computations in this function.

val pub_of_priv : priv -> pub

Extract the public component from a private key.

The RSA transformation

type 'a or_digest = [
  1. | `Message of 'a
  2. | `Digest of string
]

Either an 'a or its digest, according to some hash algorithm.

type mask = [
  1. | `No
  2. | `Yes
  3. | `Yes_with of Mirage_crypto_rng.g
]

Masking (cryptographic blinding) mode for the RSA transform with the private key. Masking does not change the result, but it does change the timing profile of the operation.

  • `No disables masking. It is slightly faster but it exposes the private key to timing-based attacks.
  • `Yes uses random masking with the global RNG instance. This is the sane option.
  • `Yes_with g uses random masking with the generator g.
val encrypt : key:pub -> string -> string

encrypt key message is the encrypted message.

  • raises Invalid_argument

    if message is 0x00 or 0x01.

val decrypt : ?crt_hardening:bool -> ?mask:mask -> key:priv -> string -> string

decrypt ~crt_hardening ~mask key ciphertext is the decrypted ciphertext, left-padded with 0x00 up to key size.

~crt_hardening defaults to false. If true verifies that the result is correct. This is to counter Chinese remainder theorem attacks to factorize primes. If the computed signature is incorrect, it is again computed in the classical way (c ^ d mod n) without the Chinese remainder theorem optimization. The deterministic PKCS1 signing, which is at danger, uses true as default.

~mask defaults to `Yes.

Key generation

val generate : ?g:Mirage_crypto_rng.g -> ?e:Z.t -> bits:int -> unit -> priv

generate ~g ~e ~bits () is a new private key. The new key is guaranteed to be well formed, see priv.

e defaults to 2^16+1.

Note This process might diverge if there are no keys for the given bit size. This can happen when bits is extremely small.

  • raises Invalid_argument

    if e is not a prime number (checked probabilistically) or not in the range 1 < e < 2^bits, or if bits < 89 (as above, required for PKCS1 operations).

PKCS#1 padded modes

module PKCS1 : sig ... end

PKCS v1.5 operations, as defined by PKCS #1 v1.5.

OAEP padded modes

module OAEP (H : Digestif.S) : sig ... end

OAEP-padded encryption, as defined by PKCS #1 v2.1.

PSS signing

module PSS (H : Digestif.S) : sig ... end

PSS-based signing, as defined by PKCS #1 v2.1.