1f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* LibTomCrypt, modular cryptographic library -- Tom St Denis 2f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 3f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * LibTomCrypt is a library that provides various cryptographic 4f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * algorithms in a highly modular and flexible manner. 5f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 6f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library is free for all purposes without any express 7f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * guarantee it works. 8f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 9f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Tom St Denis, tomstdenis@gmail.com, http://libtomcrypt.com 10f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 11f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#include "tomcrypt.h" 12f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 13f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/** 14f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project @file rsa_exptmod.c 15f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project RSA PKCS exptmod, Tom St Denis 16f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project*/ 17f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 18f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef MRSA 19f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 20f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/** 21f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project Compute an RSA modular exponentiation 22f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project @param in The input data to send into RSA 23f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project @param inlen The length of the input (octets) 24f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project @param out [out] The destination 25f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project @param outlen [in/out] The max size and resulting size of the output 26f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project @param which Which exponent to use, e.g. PK_PRIVATE or PK_PUBLIC 27f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project @param key The RSA key to use 28f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project @return CRYPT_OK if successful 29f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project*/ 30f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint rsa_exptmod(const unsigned char *in, unsigned long inlen, 31f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project unsigned char *out, unsigned long *outlen, int which, 32f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project rsa_key *key) 33f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 34f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project void *tmp, *tmpa, *tmpb; 35f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project unsigned long x; 36f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int err; 37f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 38f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project LTC_ARGCHK(in != NULL); 39f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project LTC_ARGCHK(out != NULL); 40f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project LTC_ARGCHK(outlen != NULL); 41f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project LTC_ARGCHK(key != NULL); 42f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 43f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* is the key of the right type for the operation? */ 44f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (which == PK_PRIVATE && (key->type != PK_PRIVATE)) { 45f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return CRYPT_PK_NOT_PRIVATE; 46f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 47f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 48f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* must be a private or public operation */ 49f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (which != PK_PRIVATE && which != PK_PUBLIC) { 50f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return CRYPT_PK_INVALID_TYPE; 51f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 52f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 53f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* init and copy into tmp */ 54f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_init_multi(&tmp, &tmpa, &tmpb, NULL)) != CRYPT_OK) { return err; } 55f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_read_unsigned_bin(tmp, (unsigned char *)in, (int)inlen)) != CRYPT_OK) { goto error; } 56f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 57f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* sanity check on the input */ 58f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp(key->N, tmp) == LTC_MP_LT) { 59f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project err = CRYPT_PK_INVALID_SIZE; 60f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto error; 61f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 62f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 63f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* are we using the private exponent and is the key optimized? */ 64f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (which == PK_PRIVATE) { 65f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* tmpa = tmp^dP mod p */ 66f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_exptmod(tmp, key->dP, key->p, tmpa)) != CRYPT_OK) { goto error; } 67f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 68f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* tmpb = tmp^dQ mod q */ 69f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_exptmod(tmp, key->dQ, key->q, tmpb)) != CRYPT_OK) { goto error; } 70f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 71f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* tmp = (tmpa - tmpb) * qInv (mod p) */ 72f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_sub(tmpa, tmpb, tmp)) != CRYPT_OK) { goto error; } 73f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_mulmod(tmp, key->qP, key->p, tmp)) != CRYPT_OK) { goto error; } 74f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 75f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* tmp = tmpb + q * tmp */ 76f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_mul(tmp, key->q, tmp)) != CRYPT_OK) { goto error; } 77f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_add(tmp, tmpb, tmp)) != CRYPT_OK) { goto error; } 78f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } else { 79f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* exptmod it */ 80f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_exptmod(tmp, key->e, key->N, tmp)) != CRYPT_OK) { goto error; } 81f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 82f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 83f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* read it back */ 84f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project x = (unsigned long)mp_unsigned_bin_size(key->N); 85f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (x > *outlen) { 86f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project *outlen = x; 87f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project err = CRYPT_BUFFER_OVERFLOW; 88f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto error; 89f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 90f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 91f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* this should never happen ... */ 92f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_unsigned_bin_size(tmp) > mp_unsigned_bin_size(key->N)) { 93f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project err = CRYPT_ERROR; 94f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto error; 95f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 96f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project *outlen = x; 97f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 98f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* convert it */ 99f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project zeromem(out, x); 100f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_to_unsigned_bin(tmp, out+(x-mp_unsigned_bin_size(tmp)))) != CRYPT_OK) { goto error; } 101f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 102f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* clean up and return */ 103f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project err = CRYPT_OK; 104f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projecterror: 105f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_clear_multi(tmp, tmpa, tmpb, NULL); 106f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return err; 107f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 108f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 109f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 110f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 111f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Source: /cvs/libtom/libtomcrypt/src/pk/rsa/rsa_exptmod.c,v $ */ 112f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Revision: 1.16 $ */ 113f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Date: 2006/12/04 03:09:28 $ */ 114