schnorrkel/
sign.rs

1// -*- mode: rust; -*-
2//
3// This file is part of schnorrkel.
4// Copyright (c) 2017-2019 isis lovecruft
5// Copyright (c) 2019 Web 3 Foundation
6// See LICENSE for licensing information.
7//
8// Authors:
9// - isis agora lovecruft <isis@patternsinthevoid.net>
10// - Jeffrey Burdges <jeff@web3.foundation>
11
12//! ### Schnorr signature creation and verification, including batch verification.
13
14use core::fmt::{Debug};
15
16use curve25519_dalek::constants;
17use curve25519_dalek::ristretto::{CompressedRistretto, RistrettoPoint};
18use curve25519_dalek::scalar::Scalar;
19
20use super::*;
21use crate::context::{SigningTranscript, SigningContext};
22
23// === Actual signature type === //
24
25/// The length of a curve25519 EdDSA `Signature`, in bytes.
26pub const SIGNATURE_LENGTH: usize = 64;
27
28/// A Ristretto Schnorr signature "detached" from the signed message.
29///
30/// These cannot be converted to any Ed25519 signature because they hash
31/// curve points in the Ristretto encoding.
32#[allow(non_snake_case)]
33#[derive(Clone, Copy, Eq, PartialEq)]
34pub struct Signature {
35    /// `R` is a `RistrettoPoint`, formed by using an hash function with
36    /// 512-bits output to produce the digest of:
37    ///
38    /// - the nonce half of the `SecretKey`, and
39    /// - the message to be signed.
40    ///
41    /// This digest is then interpreted as a `Scalar` and reduced into an
42    /// element in ℤ/lℤ.  The scalar is then multiplied by the distinguished
43    /// basepoint to produce `R`, a `RistrettoPoint`.
44    pub(crate) R: CompressedRistretto,
45
46    /// `s` is a `Scalar`, formed by using an hash function with 512-bits output
47    /// to produce the digest of:
48    ///
49    /// - the `r` portion of this `Signature`,
50    /// - the `PublicKey` which should be used to verify this `Signature`, and
51    /// - the message to be signed.
52    ///
53    /// This digest is then interpreted as a `Scalar` and reduced into an
54    /// element in ℤ/lℤ.
55    pub(crate) s: Scalar,
56}
57
58impl Debug for Signature {
59    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
60        write!(f, "Signature( R: {:?}, s: {:?} )", &self.R, &self.s)
61    }
62}
63
64pub(crate) fn check_scalar(bytes: [u8; 32]) -> SignatureResult<Scalar> {
65    // Since this is only used in signature deserialisation (i.e. upon
66    // verification), we can do a "succeed fast" trick by checking that the most
67    // significant 4 bits are unset.  If they are unset, we can succeed fast
68    // because we are guaranteed that the scalar is fully reduced.  However, if
69    // the 4th most significant bit is set, we must do the full reduction check,
70    // as the order of the basepoint is roughly a 2^(252.5) bit number.
71    //
72    // This succeed-fast trick should succeed for roughly half of all scalars.
73    if bytes[31] & 0b11110000 == 0 {
74        #[allow(deprecated)] // Scalar's always reduced here, so this is OK.
75        return Ok(Scalar::from_bits(bytes));
76    }
77
78    crate::scalar_from_canonical_bytes(bytes).ok_or(SignatureError::ScalarFormatError)
79}
80
81impl Signature {
82    const DESCRIPTION: &'static str = "A 64 byte Ristretto Schnorr signature";
83    /*
84    const DESCRIPTION_LONG : &'static str =
85        "A 64 byte Ristretto Schnorr signature, similar to an ed25519 \
86         signature as specified in RFC8032, except the Ristretto point \
87         compression is used for the curve point in the first 32 bytes";
88    */
89
90    /// Convert this `Signature` to a byte array.
91    #[inline]
92    pub fn to_bytes(&self) -> [u8; SIGNATURE_LENGTH] {
93        let mut bytes: [u8; SIGNATURE_LENGTH] = [0u8; SIGNATURE_LENGTH];
94        bytes[..32].copy_from_slice(&self.R.as_bytes()[..]);
95        bytes[32..].copy_from_slice(&self.s.as_bytes()[..]);
96        bytes[63] |= 128;
97        bytes
98    }
99
100    /// Construct a `Signature` from a slice of bytes.
101    ///
102    /// We distinguish schnorrkell signatures from ed25519 signatures
103    /// by setting the high bit of byte 31.  We return an error if
104    /// this marker remains unset because otherwise schnorrkel
105    /// signatures would be indistinguishable from ed25519 signatures.
106    /// We cannot always distinguish between schnorrkel and ed25519
107    /// public keys either, so without this marker bit we could not
108    /// do batch verification in systems that support precisely
109    /// ed25519 and schnorrkel.
110    ///
111    /// We cannot distinguish amongst different `SigningTranscript`
112    /// types using these marker bits, but protocol should not need
113    /// two different transcript types.
114    #[inline]
115    pub fn from_bytes(bytes: &[u8]) -> SignatureResult<Signature> {
116        if bytes.len() != SIGNATURE_LENGTH {
117            return Err(SignatureError::BytesLengthError {
118                name: "Signature",
119                description: Signature::DESCRIPTION,
120                length: SIGNATURE_LENGTH,
121            });
122        }
123
124        let mut lower: [u8; 32] = [0u8; 32];
125        let mut upper: [u8; 32] = [0u8; 32];
126        lower.copy_from_slice(&bytes[..32]);
127        upper.copy_from_slice(&bytes[32..]);
128        if upper[31] & 128 == 0 {
129            return Err(SignatureError::NotMarkedSchnorrkel);
130        }
131        upper[31] &= 127;
132
133        Ok(Signature { R: CompressedRistretto(lower), s: check_scalar(upper)? })
134    }
135
136    /// Deprecated construction of a `Signature` from a slice of bytes
137    /// without checking the bit distinguishing from ed25519.  Deprecated.
138    #[cfg(feature = "preaudit_deprecated")]
139    #[inline]
140    pub fn from_bytes_not_distinguished_from_ed25519(bytes: &[u8]) -> SignatureResult<Signature> {
141        if bytes.len() != SIGNATURE_LENGTH {
142            return Err(SignatureError::BytesLengthError {
143                name: "Signature",
144                description: Signature::DESCRIPTION,
145                length: SIGNATURE_LENGTH,
146            });
147        }
148        let mut bytes0: [u8; SIGNATURE_LENGTH] = [0u8; SIGNATURE_LENGTH];
149        bytes0.copy_from_slice(bytes);
150        bytes0[63] |= 128;
151        Signature::from_bytes(&bytes0[..])
152    }
153}
154
155serde_boilerplate!(Signature);
156
157// === Implement signing and verification operations on key types === //
158
159impl SecretKey {
160    /// Sign a transcript with this `SecretKey`.
161    ///
162    /// Requires a `SigningTranscript`, normally created from a
163    /// `SigningContext` and a message, as well as the public key
164    /// corresponding to `self`.  Returns a Schnorr signature.
165    ///
166    /// We employ a randomized nonce here, but also incorporate the
167    /// transcript like in a derandomized scheme, but only after first
168    /// extending the transcript by the public key.  As a result, there
169    /// should be no attacks even if both the random number generator
170    /// fails and the function gets called with the wrong public key.
171    #[allow(non_snake_case)]
172    pub fn sign<T: SigningTranscript>(&self, mut t: T, public_key: &PublicKey) -> Signature {
173        t.proto_name(b"Schnorr-sig");
174        t.commit_point(b"sign:pk", public_key.as_compressed());
175
176        let mut r = t.witness_scalar(b"signing", &[&self.nonce]); // context, message, A/public_key
177        let R = (&r * constants::RISTRETTO_BASEPOINT_TABLE).compress();
178
179        t.commit_point(b"sign:R", &R);
180
181        let k: Scalar = t.challenge_scalar(b"sign:c"); // context, message, A/public_key, R=rG
182        let s: Scalar = k * self.key + r;
183
184        zeroize::Zeroize::zeroize(&mut r);
185
186        Signature { R, s }
187    }
188
189    /// Sign a message with this `SecretKey`, but doublecheck the result.
190    pub fn sign_doublecheck<T>(&self, t: T, public_key: &PublicKey) -> SignatureResult<Signature>
191    where
192        T: SigningTranscript + Clone,
193    {
194        let sig = self.sign(t.clone(), public_key);
195        let sig = Signature::from_bytes(&sig.to_bytes())?;
196        PublicKey::from_bytes(&public_key.to_bytes())?.verify(t, &sig).map(|()| sig)
197    }
198
199    /// Sign a message with this `SecretKey`.
200    pub fn sign_simple(&self, ctx: &[u8], msg: &[u8], public_key: &PublicKey) -> Signature {
201        let t = SigningContext::new(ctx).bytes(msg);
202        self.sign(t, public_key)
203    }
204
205    /// Sign a message with this `SecretKey`, but doublecheck the result.
206    pub fn sign_simple_doublecheck(
207        &self,
208        ctx: &[u8],
209        msg: &[u8],
210        public_key: &PublicKey,
211    ) -> SignatureResult<Signature> {
212        let t = SigningContext::new(ctx).bytes(msg);
213        let sig = self.sign(t, public_key);
214        let sig = Signature::from_bytes(&sig.to_bytes())?;
215        PublicKey::from_bytes(&public_key.to_bytes())?
216            .verify_simple(ctx, msg, &sig)
217            .map(|()| sig)
218    }
219}
220
221impl PublicKey {
222    /// Verify a signature by this public key on a transcript.
223    ///
224    /// Requires a `SigningTranscript`, normally created from a
225    /// `SigningContext` and a message, as well as the signature
226    /// to be verified.
227    #[allow(non_snake_case)]
228    pub fn verify<T: SigningTranscript>(
229        &self,
230        mut t: T,
231        signature: &Signature,
232    ) -> SignatureResult<()> {
233        let A: &RistrettoPoint = self.as_point();
234
235        t.proto_name(b"Schnorr-sig");
236        t.commit_point(b"sign:pk", self.as_compressed());
237        t.commit_point(b"sign:R", &signature.R);
238
239        let k: Scalar = t.challenge_scalar(b"sign:c"); // context, message, A/public_key, R=rG
240        let R = RistrettoPoint::vartime_double_scalar_mul_basepoint(&k, &(-A), &signature.s);
241
242        if R.compress() == signature.R {
243            Ok(())
244        } else {
245            Err(SignatureError::EquationFalse)
246        }
247    }
248
249    /// Verify a signature by this public key on a message.
250    pub fn verify_simple(
251        &self,
252        ctx: &[u8],
253        msg: &[u8],
254        signature: &Signature,
255    ) -> SignatureResult<()> {
256        let t = SigningContext::new(ctx).bytes(msg);
257        self.verify(t, signature)
258    }
259
260    /// A temporary verification routine for use in transitioning substrate testnets only.
261    #[cfg(feature = "preaudit_deprecated")]
262    #[allow(non_snake_case)]
263    pub fn verify_simple_preaudit_deprecated(
264        &self,
265        ctx: &'static [u8],
266        msg: &[u8],
267        sig: &[u8],
268    ) -> SignatureResult<()> {
269        let t = SigningContext::new(ctx).bytes(msg);
270
271        if let Ok(signature) = Signature::from_bytes(sig) {
272            return self.verify(t, &signature);
273        }
274
275        let signature = Signature::from_bytes_not_distinguished_from_ed25519(sig)?;
276
277        let mut t = merlin::Transcript::new(ctx);
278        t.append_message(b"sign-bytes", msg);
279
280        let A: &RistrettoPoint = self.as_point();
281
282        t.proto_name(b"Schnorr-sig");
283        t.commit_point(b"pk", self.as_compressed());
284        t.commit_point(b"no", &signature.R);
285
286        let k: Scalar = t.challenge_scalar(b""); // context, message, A/public_key, R=rG
287        let R = RistrettoPoint::vartime_double_scalar_mul_basepoint(&k, &(-A), &signature.s);
288
289        if R.compress() == signature.R {
290            Ok(())
291        } else {
292            Err(SignatureError::EquationFalse)
293        }
294    }
295}
296
297impl Keypair {
298    /// Sign a transcript with this keypair's secret key.
299    ///
300    /// Requires a `SigningTranscript`, normally created from a
301    /// `SigningContext` and a message.  Returns a Schnorr signature.
302    ///
303    /// # Examples
304    ///
305    /// Internally, we manage signature transcripts using a 128 bit secure
306    /// STROBE construction based on Keccak, which itself is extremely fast
307    /// and secure.  You might however influence performance or security
308    /// by prehashing your message, like
309    ///
310    /// ```
311    /// use schnorrkel::{Signature,Keypair};
312    /// use rand::prelude::*; // ThreadRng,thread_rng
313    /// use sha3::Shake128;
314    /// use sha3::digest::{Update};
315    ///
316    /// # #[cfg(all(feature = "std"))]
317    /// # fn main() {
318    /// let mut csprng: ThreadRng = thread_rng();
319    /// let keypair: Keypair = Keypair::generate_with(&mut csprng);
320    /// let message: &[u8] = b"All I want is to pet all of the dogs.";
321    ///
322    /// // Create a hash digest object and feed it the message:
323    /// let prehashed = Shake128::default().chain(message);
324    /// # }
325    /// #
326    /// # #[cfg(any(not(feature = "std")))]
327    /// # fn main() { }
328    /// ```
329    ///
330    /// We require a "context" string for all signatures, which should
331    /// be chosen judiciously for your project.  It should represent the
332    /// role the signature plays in your application.  If you use the
333    /// context in two purposes, and the same key, then a signature for
334    /// one purpose can be substituted for the other.
335    ///
336    /// ```
337    /// # use schnorrkel::{Keypair,Signature,signing_context};
338    /// # use rand::prelude::*; // ThreadRng,thread_rng
339    /// # use sha3::digest::Update;
340    /// #
341    /// # #[cfg(all(feature = "std"))]
342    /// # fn main() {
343    /// # let mut csprng: ThreadRng = thread_rng();
344    /// # let keypair: Keypair = Keypair::generate_with(&mut csprng);
345    /// # let message: &[u8] = b"All I want is to pet all of the dogs.";
346    /// # let prehashed = sha3::Shake256::default().chain(message);
347    /// #
348    /// let ctx = signing_context(b"My Signing Context");
349    ///
350    /// let sig: Signature = keypair.sign(ctx.xof(prehashed));
351    /// # }
352    /// #
353    /// # #[cfg(any(not(feature = "std")))]
354    /// # fn main() { }
355    /// ```
356    ///
357    // lol  [terrible_idea]: https://github.com/isislovecruft/scripts/blob/master/gpgkey2bc.py
358    pub fn sign<T: SigningTranscript>(&self, t: T) -> Signature {
359        self.secret.sign(t, &self.public)
360    }
361
362    /// Sign a message with this keypair's secret key.
363    pub fn sign_simple(&self, ctx: &[u8], msg: &[u8]) -> Signature {
364        self.secret.sign_simple(ctx, msg, &self.public)
365    }
366
367    /// Verify a signature by keypair's public key on a transcript.
368    ///
369    /// Requires a `SigningTranscript`, normally created from a
370    /// `SigningContext` and a message, as well as the signature
371    /// to be verified.
372    ///
373    /// # Examples
374    ///
375    /// ```
376    /// use schnorrkel::{Keypair,Signature,signing_context};
377    /// use rand::prelude::*; // ThreadRng,thread_rng
378    ///
379    /// # fn main() {
380    /// # #[cfg(feature = "getrandom")]
381    /// # {
382    /// let mut csprng: ThreadRng = thread_rng();
383    /// let keypair: Keypair = Keypair::generate_with(&mut csprng);
384    /// let message: &[u8] = b"All I want is to pet all of the dogs.";
385    ///
386    /// let ctx = signing_context(b"Some context string");
387    ///
388    /// let sig: Signature = keypair.sign(ctx.bytes(message));
389    ///
390    /// assert!( keypair.public.verify(ctx.bytes(message), &sig).is_ok() );
391    /// # }
392    /// # }
393    /// ```
394    pub fn verify<T: SigningTranscript>(&self, t: T, signature: &Signature) -> SignatureResult<()> {
395        self.public.verify(t, signature)
396    }
397
398    /// Verify a signature by keypair's public key on a message.
399    pub fn verify_simple(
400        &self,
401        ctx: &[u8],
402        msg: &[u8],
403        signature: &Signature,
404    ) -> SignatureResult<()> {
405        self.public.verify_simple(ctx, msg, signature)
406    }
407
408    /// Sign a message with this `SecretKey`, but doublecheck the result.
409    pub fn sign_doublecheck<T>(&self, t: T) -> SignatureResult<Signature>
410    where
411        T: SigningTranscript + Clone,
412    {
413        let sig = self.sign(t.clone());
414        let sig = Signature::from_bytes(&sig.to_bytes())?;
415        PublicKey::from_bytes(&self.public.to_bytes())?.verify(t, &sig).map(|()| sig)
416    }
417
418    /// Sign a message with this `SecretKey`, but doublecheck the result.
419    pub fn sign_simple_doublecheck(&self, ctx: &[u8], msg: &[u8]) -> SignatureResult<Signature> {
420        let t = SigningContext::new(ctx).bytes(msg);
421        let sig = self.sign(t);
422        let sig = Signature::from_bytes(&sig.to_bytes())?;
423        PublicKey::from_bytes(&self.public.to_bytes())?
424            .verify_simple(ctx, msg, &sig)
425            .map(|()| sig)
426    }
427}
428
429#[cfg(test)]
430mod test {
431    use sha3::Shake128;
432    use curve25519_dalek::digest::{Update};
433
434    use super::super::*;
435
436    #[cfg(feature = "getrandom")]
437    #[test]
438    fn sign_verify_bytes() {
439        let good_sig: Signature;
440        let bad_sig: Signature;
441
442        let ctx = signing_context(b"good");
443
444        let good: &[u8] = "test message".as_bytes();
445        let bad: &[u8] = "wrong message".as_bytes();
446
447        let mut csprng = rand_core::OsRng;
448
449        let keypair = Keypair::generate_with(&mut csprng);
450        good_sig = keypair.sign(ctx.bytes(&good));
451        bad_sig = keypair.sign(ctx.bytes(&bad));
452
453        let good_sig = Signature::from_bytes(&good_sig.to_bytes()[..]).unwrap();
454        let bad_sig = Signature::from_bytes(&bad_sig.to_bytes()[..]).unwrap();
455
456        assert!(
457            keypair.verify(ctx.bytes(&good), &good_sig).is_ok(),
458            "Verification of a valid signature failed!"
459        );
460        assert!(
461            !keypair.verify(ctx.bytes(&good), &bad_sig).is_ok(),
462            "Verification of a signature on a different message passed!"
463        );
464        assert!(
465            !keypair.verify(ctx.bytes(&bad), &good_sig).is_ok(),
466            "Verification of a signature on a different message passed!"
467        );
468        assert!(
469            !keypair.verify(signing_context(b"bad").bytes(&good), &good_sig).is_ok(),
470            "Verification of a signature on a different message passed!"
471        );
472    }
473
474    #[cfg(feature = "getrandom")]
475    #[test]
476    fn sign_verify_xof() {
477        let good_sig: Signature;
478        let bad_sig: Signature;
479
480        let ctx = signing_context(b"testing testing 1 2 3");
481
482        let good: &[u8] = b"test message";
483        let bad: &[u8] = b"wrong message";
484
485        let prehashed_good: Shake128 = Shake128::default().chain(good);
486        let prehashed_bad: Shake128 = Shake128::default().chain(bad);
487        // You may verify that `Shake128: Copy` is possible, making these clones below correct.
488
489        let mut csprng = rand_core::OsRng;
490
491        let keypair = Keypair::generate_with(&mut csprng);
492        good_sig = keypair.sign(ctx.xof(prehashed_good.clone()));
493        bad_sig = keypair.sign(ctx.xof(prehashed_bad.clone()));
494
495        let good_sig_d = Signature::from_bytes(&good_sig.to_bytes()[..]).unwrap();
496        let bad_sig_d = Signature::from_bytes(&bad_sig.to_bytes()[..]).unwrap();
497        assert_eq!(good_sig, good_sig_d);
498        assert_eq!(bad_sig, bad_sig_d);
499
500        assert!(
501            keypair.verify(ctx.xof(prehashed_good.clone()), &good_sig).is_ok(),
502            "Verification of a valid signature failed!"
503        );
504        assert!(
505            !keypair.verify(ctx.xof(prehashed_good.clone()), &bad_sig).is_ok(),
506            "Verification of a signature on a different message passed!"
507        );
508        assert!(
509            !keypair.verify(ctx.xof(prehashed_bad.clone()), &good_sig).is_ok(),
510            "Verification of a signature on a different message passed!"
511        );
512        assert!(
513            !keypair.verify(signing_context(b"oops").xof(prehashed_good), &good_sig).is_ok(),
514            "Verification of a signature on a different message passed!"
515        );
516    }
517
518    #[cfg(feature = "preaudit_deprecated")]
519    #[test]
520    fn can_verify_know_preaudit_deprecated_message() {
521        use hex_literal::hex;
522        const SIGNING_CTX: &'static [u8] = b"substrate";
523        let message = b"Verifying that I am the owner of 5G9hQLdsKQswNPgB499DeA5PkFBbgkLPJWkkS6FAM6xGQ8xD. Hash: 221455a3\n";
524        let public = hex!("b4bfa1f7a5166695eb75299fd1c4c03ea212871c342f2c5dfea0902b2c246918");
525        let public = PublicKey::from_bytes(&public[..]).unwrap();
526        let signature = hex!("5a9755f069939f45d96aaf125cf5ce7ba1db998686f87f2fb3cbdea922078741a73891ba265f70c31436e18a9acd14d189d73c12317ab6c313285cd938453202");
527        assert!(public
528            .verify_simple_preaudit_deprecated(SIGNING_CTX, message, &signature[..])
529            .is_ok());
530    }
531}
schnorrkel/sign.rs

schnorrkel/
sign.rs
