Clarify nonce generation

 - Separate nonce generation into getting a random byte string and converting it to a suitable scalar ...
 - ... to make clear that the byte string can be generated differently.
 - Make the warning a little bit more prominent and improve writing

1 files changed, 5 insertions, 4 deletions

diff --git a/bip-schnorr.mediawiki b/bip-schnorr.mediawiki
index b20fb48..084b33f 100644
--- a/bip-schnorr.mediawiki
+++ b/bip-schnorr.mediawiki
@@ -151,7 +151,8 @@ The algorithm ''Sign(sk, m)'' is defined as:
 * Fail if ''d' = 0'' or ''d' ≥ n''
 * Let ''P = d'⋅G''
 * Let ''d = d' '' if ''has_square_y(P)'', otherwise let ''d = n - d' ''.
-* Let ''k' = int(hash<sub>BIPSchnorrDerive</sub>(bytes(d) || m)) mod n''<ref>Note that in general, taking the output of a hash function modulo the curve order will produce an unacceptably biased result. However, for the secp256k1 curve, the order is sufficiently close to ''2<sup>256</sup>'' that this bias is not observable (''1 - n / 2<sup>256</sup>'' is around ''1.27 * 2<sup>-128</sup>'').</ref>.
+* Let ''rand = hash<sub>BIPSchnorrDerive</sub>(bytes(d) || m)''.
+* Let ''k' = int(rand) mod n''<ref>Note that in general, taking a uniformly random 256-bit integer modulo the curve order will produce an unacceptably biased result. However, for the secp256k1 curve, the order is sufficiently close to ''2<sup>256</sup>'' that this bias is not observable (''1 - n / 2<sup>256</sup>'' is around ''1.27 * 2<sup>-128</sup>'').</ref>.
 * Fail if ''k' = 0''.
 * Let ''R = k'⋅G''.
 * Let ''k = k' '' if ''has_square_y(R)'', otherwise let ''k = n - k' ''.
@@ -160,14 +161,14 @@ The algorithm ''Sign(sk, m)'' is defined as:
 
 ==== Alternative Signing ====
 
-It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The algorithm in the previous section will always produce the same signature for a given message and public key, but the ''k'' value (and hence ''R'') may be generated in other ways, producing a different, but still valid, signature (in other words, it is not a ''unique'' signature scheme).
+It should be noted that various alternative signing algorithms can be used to produce equally valid signatures. The algorithm in the previous section is deterministic, i.e., it will always produce the same signature for a given message and secret key. This method does not need a random number generator (RNG) at signing time and is thus trivially robust against failures of RNGs. Alternatively the 32-byte ''rand'' value may be generated in other ways, producing a different but still valid signature (in other words, this is not a ''unique'' signature scheme). '''No matter which method is used to generate the ''rand'' value, the value must be a fresh uniformly random 32-byte string which is not even partially predictable for the attacker.'''
 
-'''Synthetic nonces''' When a random number generator (RNG) is available, 32 bytes of RNG output can be appended to the input to ''hash<sub>BIPSchnorrDerive</sub>''. This will change the corresponding line in the signing algorithm to ''k' = int(hash<sub>BIPSchnorrDerive</sub>(bytes(d) || m || get_32_bytes_from_rng())) mod n'', where ''get_32_bytes_from_rng()'' is the call to the RNG. Adding RNG output may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks]. It is safe to add randomness from a low-quality randomness source, i.e., an RNG with low entropy.
+'''Synthetic nonces''' For instance when a RNG is available, 32 bytes of RNG output can be appended to the input to ''hash<sub>BIPSchnorrDerive</sub>''. This will change the corresponding line in the signing algorithm to ''rand = hash<sub>BIPSchnorrDerive</sub>(bytes(d) || m || get_32_bytes_from_rng())'', where ''get_32_bytes_from_rng()'' is the call to the RNG. Adding RNG output may improve protection against [https://moderncrypto.org/mail-archive/curves/2017/000925.html fault injection attacks and side-channel attacks], and it is safe to add the output of a low-entropy RNG.
 
 '''Nonce exfiltration protection''' It is possible to strengthen the nonce generation algorithm using a second device. In this case, the second device contributes randomness which the actual signer provably incorporates into its nonce. This prevents certain attacks where the signer device is compromised and intentionally tries to leak the secret key through its nonce selection.
 
 '''Multisignatures''' This signature scheme is compatible with various types of multisignature and threshold schemes such as [https://eprint.iacr.org/2018/068 MuSig], where a single public key requires holders of multiple secret keys to participate in signing (see Applications below).
-'''It is important to note that multisignature signing schemes in general are insecure with the nonce generation from the default signing algorithm above (or any deterministic nonce algorithm).'''
+'''It is important to note that multisignature signing schemes in general are insecure with the ''rand'' generation from the default signing algorithm above (or any other deterministic method).'''
 
 ==== Verification ====