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

schnorrkel/
sign.rs
