diff options
Diffstat (limited to 'firmware/lib/cryptolib/rsa.c')
-rw-r--r-- | firmware/lib/cryptolib/rsa.c | 187 |
1 files changed, 187 insertions, 0 deletions
diff --git a/firmware/lib/cryptolib/rsa.c b/firmware/lib/cryptolib/rsa.c new file mode 100644 index 00000000..bfc64469 --- /dev/null +++ b/firmware/lib/cryptolib/rsa.c @@ -0,0 +1,187 @@ +/* Copyright (c) 2010 The Chromium OS Authors. All rights reserved. + * Use of this source code is governed by a BSD-style license that can be + * found in the LICENSE file. + */ + +/* Implementation of RSA signature verification which uses a pre-processed + * key for computation. The code extends Android's RSA verification code to + * support multiple RSA key lengths and hash digest algorithms. + */ + +#include "cryptolib.h" +#include "utility.h" + +/* a[] -= mod */ +static void subM(const RSAPublicKey *key, uint32_t *a) { + int64_t A = 0; + int i; + for (i = 0; i < key->len; ++i) { + A += (uint64_t)a[i] - key->n[i]; + a[i] = (uint32_t)A; + A >>= 32; + } +} + +/* return a[] >= mod */ +static int geM(const RSAPublicKey *key, uint32_t *a) { + int i; + for (i = key->len; i;) { + --i; + if (a[i] < key->n[i]) return 0; + if (a[i] > key->n[i]) return 1; + } + return 1; /* equal */ + } + +/* montgomery c[] += a * b[] / R % mod */ +static void montMulAdd(const RSAPublicKey *key, + uint32_t* c, + const uint32_t a, + const uint32_t* b) { + uint64_t A = (uint64_t)a * b[0] + c[0]; + uint32_t d0 = (uint32_t)A * key->n0inv; + uint64_t B = (uint64_t)d0 * key->n[0] + (uint32_t)A; + int i; + + for (i = 1; i < key->len; ++i) { + A = (A >> 32) + (uint64_t)a * b[i] + c[i]; + B = (B >> 32) + (uint64_t)d0 * key->n[i] + (uint32_t)A; + c[i - 1] = (uint32_t)B; + } + + A = (A >> 32) + (B >> 32); + + c[i - 1] = (uint32_t)A; + + if (A >> 32) { + subM(key, c); + } +} + +/* montgomery c[] = a[] * b[] / R % mod */ +static void montMul(const RSAPublicKey *key, + uint32_t* c, + uint32_t* a, + uint32_t* b) { + int i; + for (i = 0; i < key->len; ++i) { + c[i] = 0; + } + for (i = 0; i < key->len; ++i) { + montMulAdd(key, c, a[i], b); + } +} + +/* In-place public exponentiation. (65537} + * Input and output big-endian byte array in inout. + */ +static void modpowF4(const RSAPublicKey *key, + uint8_t* inout) { + uint32_t* a = (uint32_t*) Malloc(key->len * sizeof(uint32_t)); + uint32_t* aR = (uint32_t*) Malloc(key->len * sizeof(uint32_t)); + uint32_t* aaR = (uint32_t*) Malloc(key->len * sizeof(uint32_t)); + + uint32_t* aaa = aaR; /* Re-use location. */ + int i; + + /* Convert from big endian byte array to little endian word array. */ + for (i = 0; i < key->len; ++i) { + uint32_t tmp = + (inout[((key->len - 1 - i) * 4) + 0] << 24) | + (inout[((key->len - 1 - i) * 4) + 1] << 16) | + (inout[((key->len - 1 - i) * 4) + 2] << 8) | + (inout[((key->len - 1 - i) * 4) + 3] << 0); + a[i] = tmp; + } + + montMul(key, aR, a, key->rr); /* aR = a * RR / R mod M */ + for (i = 0; i < 16; i+=2) { + montMul(key, aaR, aR, aR); /* aaR = aR * aR / R mod M */ + montMul(key, aR, aaR, aaR); /* aR = aaR * aaR / R mod M */ + } + montMul(key, aaa, aR, a); /* aaa = aR * a / R mod M */ + + + /* Make sure aaa < mod; aaa is at most 1x mod too large. */ + if (geM(key, aaa)) { + subM(key, aaa); + } + + /* Convert to bigendian byte array */ + for (i = key->len - 1; i >= 0; --i) { + uint32_t tmp = aaa[i]; + *inout++ = tmp >> 24; + *inout++ = tmp >> 16; + *inout++ = tmp >> 8; + *inout++ = tmp >> 0; + } + + Free(a); + Free(aR); + Free(aaR); +} + +/* Verify a RSA PKCS1.5 signature against an expected hash. + * Returns 0 on failure, 1 on success. + */ +int RSAVerify(const RSAPublicKey *key, + const uint8_t *sig, + const int sig_len, + const uint8_t sig_type, + const uint8_t *hash) { + int i; + uint8_t* buf; + const uint8_t* padding; + int success = 1; + + if (sig_len != (key->len * sizeof(uint32_t))) { + debug("Signature is of incorrect length!\n"); + return 0; + } + + if (sig_type >= kNumAlgorithms) { + debug("Invalid signature type!\n"); + return 0; + } + + if (key->len != siglen_map[sig_type] / sizeof(uint32_t)) { + debug("Wrong key passed in!\n"); + return 0; + } + + buf = (uint8_t*) Malloc(sig_len); + Memcpy(buf, sig, sig_len); + + modpowF4(key, buf); + + /* Determine padding to use depending on the signature type. */ + padding = padding_map[sig_type]; + + /* Check pkcs1.5 padding bytes. */ + for (i = 0; i < padding_size_map[sig_type]; ++i) { + if (buf[i] != padding[i]) { +#ifndef NDEBUG +/* TODO(gauravsh): Replace with a macro call for logging. */ + debug("Padding: Expecting = %02x Got = %02x\n", padding[i], + buf[i]); +#endif + success = 0; + } + } + + /* Check if digest matches. */ + for (; i < sig_len; ++i) { + if (buf[i] != *hash++) { +#ifndef NDEBUG +/* TODO(gauravsh): Replace with a macro call for logging. */ + debug("Digest: Expecting = %02x Got = %02x\n", padding[i], + buf[i]); +#endif + success = 0; + } + } + + Free(buf); + + return success; +} |