reddsa.ml
(*****************************************************************************)
(* *)
(* Copyright (c) 2021 Danny Willems <be.danny.willems@gmail.com> *)
(* *)
(* Permission is hereby granted, free of charge, to any person obtaining a *)
(* copy of this software and associated documentation files (the "Software"),*)
(* to deal in the Software without restriction, including without limitation *)
(* the rights to use, copy, modify, merge, publish, distribute, sublicense, *)
(* and/or sell copies of the Software, and to permit persons to whom the *)
(* Software is furnished to do so, subject to the following conditions: *)
(* *)
(* The above copyright notice and this permission notice shall be included *)
(* in all copies or substantial portions of the Software. *)
(* *)
(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, *)
(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL *)
(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING *)
(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER *)
(* DEALINGS IN THE SOFTWARE. *)
(* *)
(*****************************************************************************)
module type SIGNATURE_SCHEME = sig
type secret_key
type public_key
type signature
val signature_to_bytes : signature -> Bytes.t
val sign : secret_key -> Bytes.t -> signature
val sign_deterministic : Bytes.t -> secret_key -> Bytes.t -> signature
val verify : public_key -> Bytes.t -> signature -> bool
end
module MakeRedDSA
(Ec : Ec_sig.AffineEdwardsT) (Param : sig
val length : int
val hash : Bytes.t -> Bytes.t
val generator : Ec.t
val to_compressed : Ec.t -> Bytes.t
val of_compressed_opt : Bytes.t -> Ec.t option
end) =
struct
let () =
if Param.length mod 8 <> 0 then failwith "Length must be a multiple of 8"
let hash_star bytes =
let limbs = Param.hash bytes in
Ec.Scalar.of_bytes_exn limbs
type secret_key = Ec.Scalar.t
type public_key = Ec.t
type signature = {r : Bytes.t; s : Bytes.t}
let signature_to_bytes signature =
Bytes.concat Bytes.empty [signature.r; signature.s]
let sign_deterministic randomness sk message =
(* length is given in bits *)
let length = (Param.length + 128) / 8 in
assert (Bytes.length randomness = length) ;
(* IMPORTANT!!!
r = H*(T || vk || M) --> This is the spec in the Sapling PDF. However,
the reference implementation do not use the vk:
- https://github.com/zcash/librustzcash/blob/da431a0eb207f69c9b0631d7d02136d819e1bfd9/zcash_primitives/src/sapling/redjubjub.rs#L80
- https://github.com/zcash/librustzcash/blob/da431a0eb207f69c9b0631d7d02136d819e1bfd9/zcash_primitives/src/sapling/util.rs#L9
- https://github.com/zcash/librustzcash/issues/179
*)
let r = hash_star (Bytes.concat Bytes.empty [randomness; message]) in
(* R = r . P *)
let p_r = Ec.mul Param.generator r in
(* Get the little endian encoding of the point R *)
let p_r_le = Param.to_compressed p_r in
(* s = r + sk . H*(LE(P) || M) *)
let s = hash_star (Bytes.concat Bytes.empty [p_r_le; message]) in
let s = Ec.Scalar.(sk * s) in
let s = Ec.Scalar.(r + s) in
(* R || S *)
{r = p_r_le; s = Ec.Scalar.to_bytes s}
let sign sk message =
(* Generate T, length + 128 bits *)
let t =
Bytes.init
((Param.length + 128) / 8)
(fun _ -> char_of_int (Random.int 256))
in
sign_deterministic t sk message
let verify vk message signature =
(* we do not have to check the first condition as it is an invariant of the
type signature
*)
let r = Param.of_compressed_opt signature.r in
let s = Z.of_bits (Bytes.to_string signature.s) in
(* The Sapling PDF does use vk in the hash, but not the reference
implementation of zcash. Therefore, ignoring it
- https://github.com/zcash/librustzcash/blob/da431a0eb207f69c9b0631d7d02136d819e1bfd9/zcash_primitives/src/sapling/redjubjub.rs#L80
- https://github.com/zcash/librustzcash/blob/da431a0eb207f69c9b0631d7d02136d819e1bfd9/zcash_primitives/src/sapling/util.rs#L9
- https://github.com/zcash/librustzcash/issues/179
*)
let c = hash_star (Bytes.concat Bytes.empty [signature.r; message]) in
(* FIXME: not constant time!! Like everything... *)
match r with
| None -> false
| Some r ->
let s_leq_r = Z.(leq s Ec.Scalar.order) in
(* [c] * vk *)
let c_vk = Ec.(mul vk c) in
(* [S] * P_G *)
let s_p_g = Ec.(mul Param.generator (Scalar.of_z s)) in
(* -[S] * P_G + R + [c] vk *)
let res = Ec.(add (add (negate s_p_g) r) c_vk) in
(* multiply by the cofactor -> [h_G] res *)
let res = Ec.(mul res (Scalar.of_z cofactor)) in
let res_is_null = Ec.is_zero res in
s_leq_r && res_is_null
end