src/math.c

   1 // custom math routines for shallot
   2
   3 #include "math.h"
   4 #include "defines.h"
   5
   6 void int_pow(uint32_t base, uint8_t pwr, uint64_t *out) { // integer pow()
   7   *out = (uint64_t)base;
   8   uint8_t round = 1;
   9   for(; round < pwr; round++)
  10     *out *= base;
  11 }
  12
  13 // LCM for BIGNUMs
  14 uint8_t BN_lcm(BIGNUM *r, BIGNUM *a, BIGNUM *b, BIGNUM *gcd, BN_CTX *ctx) {
  15   BIGNUM *tmp = BN_CTX_get(ctx);
  16   if(!BN_div(tmp, NULL, a, gcd, ctx))
  17     return 0;
  18   if(!BN_mul(r, b, tmp, ctx))
  19     return 0;
  20   return 1;
  21 }
  22
  23 // wraps RSA key generation, DER encoding, and initial SHA-1 hashing
  24 RSA *easygen(uint16_t num, uint8_t len, uint8_t *der, uint8_t edl,
  25              SHA_CTX *ctx) {
  26   uint8_t der_len;
  27   RSA *rsa;
  28
  29   for(;;) { // ugly, I know, but better than using goto IMHO
  30     rsa = RSA_generate_key(num, 3, NULL, NULL);
  31
  32     if(!rsa) // if key generation fails (no [P]RNG seed?)
  33       return rsa;
  34
  35     // encode RSA key in X.690 DER format
  36     uint8_t *tmp = der;
  37     der_len = i2d_RSAPublicKey(rsa, &tmp);
  38
  39     if(der_len == edl - len + 1)
  40       break; // encoded key was the correct size, keep going
  41
  42     RSA_free(rsa); // encoded key was the wrong size, try again
  43   }
  44
  45   // adjust for the actual size of e
  46   der[RSA_ADD_DER_OFF] += len - 1;
  47   der[der_len - 2]     += len - 1;
  48
  49   // and prepare our hash context
  50   SHA1_Init(ctx);
  51   SHA1_Update(ctx, der, der_len - 1);
  52
  53   return rsa;
  54 }
  55
  56 uint8_t sane_key(RSA *rsa) { // checks sanity of a RSA key (PKCS#1 v2.1)
  57   uint8_t sane = 1;
  58
  59   BN_CTX *ctx = BN_CTX_new();
  60   BN_CTX_start(ctx);
  61   BIGNUM *p1     = BN_CTX_get(ctx), // p - 1
  62          *q1     = BN_CTX_get(ctx), // q - 1
  63          *chk    = BN_CTX_get(ctx), // storage to run checks with
  64          *gcd    = BN_CTX_get(ctx), // GCD(p - 1, q - 1)
  65          *lambda = BN_CTX_get(ctx); // LCM(p - 1, q - 1)
  66
  67   BN_sub(p1, rsa->p, BN_value_one()); // p - 1
  68   BN_sub(q1, rsa->q, BN_value_one()); // q - 1
  69   BN_gcd(gcd, p1, q1, ctx);           // gcd(p - 1, q - 1)
  70   BN_lcm(lambda, p1, q1, gcd, ctx);   // lambda(n)
  71
  72   BN_gcd(chk, lambda, rsa->e, ctx); // check if e is coprime to lambda(n)
  73   if(!BN_is_one(chk))
  74     sane = 0;
  75
  76   // check if public exponent e is less than n - 1
  77   BN_sub(chk, rsa->e, rsa->n); // subtract n from e to avoid checking BN_is_zero
  78   if(!chk->neg)
  79     sane = 0;
  80
  81   BN_mod_inverse(rsa->d, rsa->e, lambda, ctx);    // d
  82   BN_mod(rsa->dmp1, rsa->d, p1, ctx);             // d mod (p - 1)
  83   BN_mod(rsa->dmq1, rsa->d, q1, ctx);             // d mod (q - 1)
  84   BN_mod_inverse(rsa->iqmp, rsa->q, rsa->p, ctx); // q ^ -1 mod p
  85   BN_CTX_end(ctx);
  86   BN_CTX_free(ctx);
  87
  88   // this is excessive but you're better off safe than (very) sorry
  89   // in theory this should never be true unless I made a mistake ;)
  90   if((RSA_check_key(rsa) != 1) && sane) {
  91     fprintf(stderr, "WARNING: Key looked okay, but OpenSSL says otherwise!\n");
  92     sane = 0;
  93   }
  94
  95   return sane;
  96 }
  97