src/modules/recovery/tests_exhaustive_impl.h

   1 /***********************************************************************
   2  * Copyright (c) 2016 Andrew Poelstra                                  *
   3  * Distributed under the MIT software license, see the accompanying    *
   4  * file COPYING or https://www.opensource.org/licenses/mit-license.php.*
   5  ***********************************************************************/
   6
   7 #ifndef SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H
   8 #define SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H
   9
  10 #include "src/modules/recovery/main_impl.h"
  11 #include "../../../include/secp256k1_recovery.h"
  12
  13 void test_exhaustive_recovery_sign(const secp256k1_context *ctx, const secp256k1_ge *group) {
  14     int i, j, k;
  15     uint64_t iter = 0;
  16
  17     /* Loop */
  18     for (i = 1; i < EXHAUSTIVE_TEST_ORDER; i++) {  /* message */
  19         for (j = 1; j < EXHAUSTIVE_TEST_ORDER; j++) {  /* key */
  20             if (skip_section(&iter)) continue;
  21             for (k = 1; k < EXHAUSTIVE_TEST_ORDER; k++) {  /* nonce */
  22                 const int starting_k = k;
  23                 secp256k1_fe r_dot_y_normalized;
  24                 secp256k1_ecdsa_recoverable_signature rsig;
  25                 secp256k1_ecdsa_signature sig;
  26                 secp256k1_scalar sk, msg, r, s, expected_r;
  27                 unsigned char sk32[32], msg32[32];
  28                 int expected_recid;
  29                 int recid;
  30                 int overflow;
  31                 secp256k1_scalar_set_int(&msg, i);
  32                 secp256k1_scalar_set_int(&sk, j);
  33                 secp256k1_scalar_get_b32(sk32, &sk);
  34                 secp256k1_scalar_get_b32(msg32, &msg);
  35
  36                 secp256k1_ecdsa_sign_recoverable(ctx, &rsig, msg32, sk32, secp256k1_nonce_function_smallint, &k);
  37
  38                 /* Check directly */
  39                 secp256k1_ecdsa_recoverable_signature_load(ctx, &r, &s, &recid, &rsig);
  40                 r_from_k(&expected_r, group, k, &overflow);
  41                 CHECK(r == expected_r);
  42                 CHECK((k * s) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER ||
  43                       (k * (EXHAUSTIVE_TEST_ORDER - s)) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER);
  44                 /* The recid's second bit is for conveying overflow (R.x value >= group order).
  45                  * In the actual secp256k1 this is an astronomically unlikely event, but in the
  46                  * small group used here, it will be the case for all points except the ones where
  47                  * R.x=1 (which the group is specifically selected to have).
  48                  * Note that this isn't actually useful; full recovery would need to convey
  49                  * floor(R.x / group_order), but only one bit is used as that is sufficient
  50                  * in the real group. */
  51                 expected_recid = overflow ? 2 : 0;
  52                 r_dot_y_normalized = group[k].y;
  53                 secp256k1_fe_normalize(&r_dot_y_normalized);
  54                 /* Also the recovery id is flipped depending if we hit the low-s branch */
  55                 if ((k * s) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER) {
  56                     expected_recid |= secp256k1_fe_is_odd(&r_dot_y_normalized);
  57                 } else {
  58                     expected_recid |= !secp256k1_fe_is_odd(&r_dot_y_normalized);
  59                 }
  60                 CHECK(recid == expected_recid);
  61
  62                 /* Convert to a standard sig then check */
  63                 secp256k1_ecdsa_recoverable_signature_convert(ctx, &sig, &rsig);
  64                 secp256k1_ecdsa_signature_load(ctx, &r, &s, &sig);
  65                 /* Note that we compute expected_r *after* signing -- this is important
  66                  * because our nonce-computing function function might change k during
  67                  * signing. */
  68                 r_from_k(&expected_r, group, k, NULL);
  69                 CHECK(r == expected_r);
  70                 CHECK((k * s) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER ||
  71                       (k * (EXHAUSTIVE_TEST_ORDER - s)) % EXHAUSTIVE_TEST_ORDER == (i + r * j) % EXHAUSTIVE_TEST_ORDER);
  72
  73                 /* Overflow means we've tried every possible nonce */
  74                 if (k < starting_k) {
  75                     break;
  76                 }
  77             }
  78         }
  79     }
  80 }
  81
  82 void test_exhaustive_recovery_verify(const secp256k1_context *ctx, const secp256k1_ge *group) {
  83     /* This is essentially a copy of test_exhaustive_verify, with recovery added */
  84     int s, r, msg, key;
  85     uint64_t iter = 0;
  86     for (s = 1; s < EXHAUSTIVE_TEST_ORDER; s++) {
  87         for (r = 1; r < EXHAUSTIVE_TEST_ORDER; r++) {
  88             for (msg = 1; msg < EXHAUSTIVE_TEST_ORDER; msg++) {
  89                 for (key = 1; key < EXHAUSTIVE_TEST_ORDER; key++) {
  90                     secp256k1_ge nonconst_ge;
  91                     secp256k1_ecdsa_recoverable_signature rsig;
  92                     secp256k1_ecdsa_signature sig;
  93                     secp256k1_pubkey pk;
  94                     secp256k1_scalar sk_s, msg_s, r_s, s_s;
  95                     secp256k1_scalar s_times_k_s, msg_plus_r_times_sk_s;
  96                     int recid = 0;
  97                     int k, should_verify;
  98                     unsigned char msg32[32];
  99
 100                     if (skip_section(&iter)) continue;
 101
 102                     secp256k1_scalar_set_int(&s_s, s);
 103                     secp256k1_scalar_set_int(&r_s, r);
 104                     secp256k1_scalar_set_int(&msg_s, msg);
 105                     secp256k1_scalar_set_int(&sk_s, key);
 106                     secp256k1_scalar_get_b32(msg32, &msg_s);
 107
 108                     /* Verify by hand */
 109                     /* Run through every k value that gives us this r and check that *one* works.
 110                      * Note there could be none, there could be multiple, ECDSA is weird. */
 111                     should_verify = 0;
 112                     for (k = 0; k < EXHAUSTIVE_TEST_ORDER; k++) {
 113                         secp256k1_scalar check_x_s;
 114                         r_from_k(&check_x_s, group, k, NULL);
 115                         if (r_s == check_x_s) {
 116                             secp256k1_scalar_set_int(&s_times_k_s, k);
 117                             secp256k1_scalar_mul(&s_times_k_s, &s_times_k_s, &s_s);
 118                             secp256k1_scalar_mul(&msg_plus_r_times_sk_s, &r_s, &sk_s);
 119                             secp256k1_scalar_add(&msg_plus_r_times_sk_s, &msg_plus_r_times_sk_s, &msg_s);
 120                             should_verify |= secp256k1_scalar_eq(&s_times_k_s, &msg_plus_r_times_sk_s);
 121                         }
 122                     }
 123                     /* nb we have a "high s" rule */
 124                     should_verify &= !secp256k1_scalar_is_high(&s_s);
 125
 126                     /* We would like to try recovering the pubkey and checking that it matches,
 127                      * but pubkey recovery is impossible in the exhaustive tests (the reason
 128                      * being that there are 12 nonzero r values, 12 nonzero points, and no
 129                      * overlap between the sets, so there are no valid signatures). */
 130
 131                     /* Verify by converting to a standard signature and calling verify */
 132                     secp256k1_ecdsa_recoverable_signature_save(&rsig, &r_s, &s_s, recid);
 133                     secp256k1_ecdsa_recoverable_signature_convert(ctx, &sig, &rsig);
 134                     memcpy(&nonconst_ge, &group[sk_s], sizeof(nonconst_ge));
 135                     secp256k1_pubkey_save(&pk, &nonconst_ge);
 136                     CHECK(should_verify ==
 137                           secp256k1_ecdsa_verify(ctx, &sig, msg32, &pk));
 138                 }
 139             }
 140         }
 141     }
 142 }
 143
 144 static void test_exhaustive_recovery(const secp256k1_context *ctx, const secp256k1_ge *group) {
 145     test_exhaustive_recovery_sign(ctx, group);
 146     test_exhaustive_recovery_verify(ctx, group);
 147 }
 148
 149 #endif /* SECP256K1_MODULE_RECOVERY_EXHAUSTIVE_TESTS_H */