[exim.git] / src / src / pdkim / rsa.c

/*
 *  The RSA public-key cryptosystem
 *
 *  Copyright (C) 2006-2010, Brainspark B.V.
 *
 *  This file is part of PolarSSL (http://www.polarssl.org)
 *  Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
 *
 *  All rights reserved.
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program; if not, write to the Free Software Foundation, Inc.,
 *  51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
/*
 *  RSA was designed by Ron Rivest, Adi Shamir and Len Adleman.
 *
 *  http://theory.lcs.mit.edu/~rivest/rsapaper.pdf
 *  http://www.cacr.math.uwaterloo.ca/hac/about/chap8.pdf
 */

#include "polarssl/config.h"

#if defined(POLARSSL_RSA_C)

#include "polarssl/rsa.h"

#include <stdlib.h>
#include <string.h>
#include <stdio.h>

/*
 * Initialize an RSA context
 */
void rsa_init( rsa_context *ctx,
               int padding,
               int hash_id )
{
    memset( ctx, 0, sizeof( rsa_context ) );

    ctx->padding = padding;
    ctx->hash_id = hash_id;
}

#if defined(POLARSSL_GENPRIME)

/*
 * Generate an RSA keypair
 */
int rsa_gen_key( rsa_context *ctx,
        int (*f_rng)(void *),
        void *p_rng,
        int nbits, int exponent )
{
    int ret;
    mpi P1, Q1, H, G;

    if( f_rng == NULL || nbits < 128 || exponent < 3 )
        return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );

    mpi_init( &P1, &Q1, &H, &G, NULL );

    /*
     * find primes P and Q with Q < P so that:
     * GCD( E, (P-1)*(Q-1) ) == 1
     */
    MPI_CHK( mpi_lset( &ctx->E, exponent ) );

    do
    {
        MPI_CHK( mpi_gen_prime( &ctx->P, ( nbits + 1 ) >> 1, 0,
                                f_rng, p_rng ) );

        MPI_CHK( mpi_gen_prime( &ctx->Q, ( nbits + 1 ) >> 1, 0,
                                f_rng, p_rng ) );

        if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) < 0 )
            mpi_swap( &ctx->P, &ctx->Q );

        if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) == 0 )
            continue;

        MPI_CHK( mpi_mul_mpi( &ctx->N, &ctx->P, &ctx->Q ) );
        if( mpi_msb( &ctx->N ) != nbits )
            continue;

        MPI_CHK( mpi_sub_int( &P1, &ctx->P, 1 ) );
        MPI_CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) );
        MPI_CHK( mpi_mul_mpi( &H, &P1, &Q1 ) );
        MPI_CHK( mpi_gcd( &G, &ctx->E, &H  ) );
    }
    while( mpi_cmp_int( &G, 1 ) != 0 );

    /*
     * D  = E^-1 mod ((P-1)*(Q-1))
     * DP = D mod (P - 1)
     * DQ = D mod (Q - 1)
     * QP = Q^-1 mod P
     */
    MPI_CHK( mpi_inv_mod( &ctx->D , &ctx->E, &H  ) );
    MPI_CHK( mpi_mod_mpi( &ctx->DP, &ctx->D, &P1 ) );
    MPI_CHK( mpi_mod_mpi( &ctx->DQ, &ctx->D, &Q1 ) );
    MPI_CHK( mpi_inv_mod( &ctx->QP, &ctx->Q, &ctx->P ) );

    ctx->len = ( mpi_msb( &ctx->N ) + 7 ) >> 3;

cleanup:

    mpi_free( &G, &H, &Q1, &P1, NULL );

    if( ret != 0 )
    {
        rsa_free( ctx );
        return( POLARSSL_ERR_RSA_KEY_GEN_FAILED | ret );
    }

    return( 0 );
}

#endif

/*
 * Check a public RSA key
 */
int rsa_check_pubkey( const rsa_context *ctx )
{
    if( !ctx->N.p || !ctx->E.p )
        return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );

    if( ( ctx->N.p[0] & 1 ) == 0 ||
        ( ctx->E.p[0] & 1 ) == 0 )
        return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );

    if( mpi_msb( &ctx->N ) < 128 ||
        mpi_msb( &ctx->N ) > 4096 )
        return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );

    if( mpi_msb( &ctx->E ) < 2 ||
        mpi_msb( &ctx->E ) > 64 )
        return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );

    return( 0 );
}

/*
 * Check a private RSA key
 */
int rsa_check_privkey( const rsa_context *ctx )
{
    int ret;
    mpi PQ, DE, P1, Q1, H, I, G, G2, L1, L2;

    if( ( ret = rsa_check_pubkey( ctx ) ) != 0 )
        return( ret );

    if( !ctx->P.p || !ctx->Q.p || !ctx->D.p )
        return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );

    mpi_init( &PQ, &DE, &P1, &Q1, &H, &I, &G, &G2, &L1, &L2, NULL );

    MPI_CHK( mpi_mul_mpi( &PQ, &ctx->P, &ctx->Q ) );
    MPI_CHK( mpi_mul_mpi( &DE, &ctx->D, &ctx->E ) );
    MPI_CHK( mpi_sub_int( &P1, &ctx->P, 1 ) );
    MPI_CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) );
    MPI_CHK( mpi_mul_mpi( &H, &P1, &Q1 ) );
    MPI_CHK( mpi_gcd( &G, &ctx->E, &H  ) );

    MPI_CHK( mpi_gcd( &G2, &P1, &Q1 ) );
    MPI_CHK( mpi_div_mpi( &L1, &L2, &H, &G2 ) );
    MPI_CHK( mpi_mod_mpi( &I, &DE, &L1  ) );

    /*
     * Check for a valid PKCS1v2 private key
     */
    if( mpi_cmp_mpi( &PQ, &ctx->N ) == 0 &&
        mpi_cmp_int( &L2, 0 ) == 0 &&
        mpi_cmp_int( &I, 1 ) == 0 &&
        mpi_cmp_int( &G, 1 ) == 0 )
    {
        mpi_free( &G, &I, &H, &Q1, &P1, &DE, &PQ, &G2, &L1, &L2, NULL );
        return( 0 );
    }


cleanup:

    mpi_free( &G, &I, &H, &Q1, &P1, &DE, &PQ, &G2, &L1, &L2, NULL );
    return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED | ret );
}

/*
 * Do an RSA public key operation
 */
int rsa_public( rsa_context *ctx,
                const unsigned char *input,
                unsigned char *output )
{
    int ret, olen;
    mpi T;

    mpi_init( &T, NULL );

    MPI_CHK( mpi_read_binary( &T, input, ctx->len ) );

    if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 )
    {
        mpi_free( &T, NULL );
        return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
    }

    olen = ctx->len;
    MPI_CHK( mpi_exp_mod( &T, &T, &ctx->E, &ctx->N, &ctx->RN ) );
    MPI_CHK( mpi_write_binary( &T, output, olen ) );

cleanup:

    mpi_free( &T, NULL );

    if( ret != 0 )
        return( POLARSSL_ERR_RSA_PUBLIC_FAILED | ret );

    return( 0 );
}

/*
 * Do an RSA private key operation
 */
int rsa_private( rsa_context *ctx,
                 const unsigned char *input,
                 unsigned char *output )
{
    int ret, olen;
    mpi T, T1, T2;

    mpi_init( &T, &T1, &T2, NULL );

    MPI_CHK( mpi_read_binary( &T, input, ctx->len ) );

    if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 )
    {
        mpi_free( &T, NULL );
        return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
    }

#if 0
    MPI_CHK( mpi_exp_mod( &T, &T, &ctx->D, &ctx->N, &ctx->RN ) );
#else
    /*
     * faster decryption using the CRT
     *
     * T1 = input ^ dP mod P
     * T2 = input ^ dQ mod Q
     */
    MPI_CHK( mpi_exp_mod( &T1, &T, &ctx->DP, &ctx->P, &ctx->RP ) );
    MPI_CHK( mpi_exp_mod( &T2, &T, &ctx->DQ, &ctx->Q, &ctx->RQ ) );

    /*
     * T = (T1 - T2) * (Q^-1 mod P) mod P
     */
    MPI_CHK( mpi_sub_mpi( &T, &T1, &T2 ) );
    MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->QP ) );
    MPI_CHK( mpi_mod_mpi( &T, &T1, &ctx->P ) );

    /*
     * output = T2 + T * Q
     */
    MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->Q ) );
    MPI_CHK( mpi_add_mpi( &T, &T2, &T1 ) );
#endif

    olen = ctx->len;
    MPI_CHK( mpi_write_binary( &T, output, olen ) );

cleanup:

    mpi_free( &T, &T1, &T2, NULL );

    if( ret != 0 )
        return( POLARSSL_ERR_RSA_PRIVATE_FAILED | ret );

    return( 0 );
}

/*
 * Add the message padding, then do an RSA operation
 */
int rsa_pkcs1_encrypt( rsa_context *ctx,
                       int (*f_rng)(void *),
                       void *p_rng,
                       int mode, int  ilen,
                       const unsigned char *input,
                       unsigned char *output )
{
    int nb_pad, olen;
    unsigned char *p = output;

    olen = ctx->len;

    switch( ctx->padding )
    {
        case RSA_PKCS_V15:

            if( ilen < 0 || olen < ilen + 11 || f_rng == NULL )
                return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );

            nb_pad = olen - 3 - ilen;

            *p++ = 0;
            *p++ = RSA_CRYPT;

            while( nb_pad-- > 0 )
            {
                int rng_dl = 100;

                do {
                    *p = (unsigned char) f_rng( p_rng );
                } while( *p == 0 && --rng_dl );

                // Check if RNG failed to generate data
                //
                if( rng_dl == 0 )
                    return POLARSSL_ERR_RSA_RNG_FAILED;

                p++;
            }
            *p++ = 0;
            memcpy( p, input, ilen );
            break;

        default:

            return( POLARSSL_ERR_RSA_INVALID_PADDING );
    }

    return( ( mode == RSA_PUBLIC )
            ? rsa_public(  ctx, output, output )
            : rsa_private( ctx, output, output ) );
}

/*
 * Do an RSA operation, then remove the message padding
 */
int rsa_pkcs1_decrypt( rsa_context *ctx,
                       int mode, int *olen,
                       const unsigned char *input,
                       unsigned char *output,
                       int output_max_len)
{
    int ret, ilen;
    unsigned char *p;
    unsigned char buf[1024];

    ilen = ctx->len;

    if( ilen < 16 || ilen > (int) sizeof( buf ) )
        return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );

    ret = ( mode == RSA_PUBLIC )
          ? rsa_public(  ctx, input, buf )
          : rsa_private( ctx, input, buf );

    if( ret != 0 )
        return( ret );

    p = buf;

    switch( ctx->padding )
    {
        case RSA_PKCS_V15:

            if( *p++ != 0 || *p++ != RSA_CRYPT )
                return( POLARSSL_ERR_RSA_INVALID_PADDING );

            while( *p != 0 )
            {
                if( p >= buf + ilen - 1 )
                    return( POLARSSL_ERR_RSA_INVALID_PADDING );
                p++;
            }
            p++;
            break;

        default:

            return( POLARSSL_ERR_RSA_INVALID_PADDING );
    }

    if (ilen - (int)(p - buf) > output_max_len)
    	return( POLARSSL_ERR_RSA_OUTPUT_TOO_LARGE );

    *olen = ilen - (int)(p - buf);
    memcpy( output, p, *olen );

    return( 0 );
}

/*
 * Do an RSA operation to sign the message digest
 */
int rsa_pkcs1_sign( rsa_context *ctx,
                    int mode,
                    int hash_id,
                    int hashlen,
                    const unsigned char *hash,
                    unsigned char *sig )
{
    int nb_pad, olen;
    unsigned char *p = sig;

    olen = ctx->len;

    switch( ctx->padding )
    {
        case RSA_PKCS_V15:

            switch( hash_id )
            {
                case SIG_RSA_RAW:
                    nb_pad = olen - 3 - hashlen;
                    break;

                case SIG_RSA_MD2:
                case SIG_RSA_MD4:
                case SIG_RSA_MD5:
                    nb_pad = olen - 3 - 34;
                    break;

                case SIG_RSA_SHA1:
                    nb_pad = olen - 3 - 35;
                    break;

                case SIG_RSA_SHA224:
                    nb_pad = olen - 3 - 47;
                    break;

                case SIG_RSA_SHA256:
                    nb_pad = olen - 3 - 51;
                    break;

                case SIG_RSA_SHA384:
                    nb_pad = olen - 3 - 67;
                    break;

                case SIG_RSA_SHA512:
                    nb_pad = olen - 3 - 83;
                    break;


                default:
                    return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
            }

            if( nb_pad < 8 )
                return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );

            *p++ = 0;
            *p++ = RSA_SIGN;
            memset( p, 0xFF, nb_pad );
            p += nb_pad;
            *p++ = 0;
            break;

        default:

            return( POLARSSL_ERR_RSA_INVALID_PADDING );
    }

    switch( hash_id )
    {
        case SIG_RSA_RAW:
            memcpy( p, hash, hashlen );
            break;

        case SIG_RSA_MD2:
            memcpy( p, ASN1_HASH_MDX, 18 );
            memcpy( p + 18, hash, 16 );
            p[13] = 2; break;

        case SIG_RSA_MD4:
            memcpy( p, ASN1_HASH_MDX, 18 );
            memcpy( p + 18, hash, 16 );
            p[13] = 4; break;

        case SIG_RSA_MD5:
            memcpy( p, ASN1_HASH_MDX, 18 );
            memcpy( p + 18, hash, 16 );
            p[13] = 5; break;

        case SIG_RSA_SHA1:
            memcpy( p, ASN1_HASH_SHA1, 15 );
            memcpy( p + 15, hash, 20 );
            break;

        case SIG_RSA_SHA224:
            memcpy( p, ASN1_HASH_SHA2X, 19 );
            memcpy( p + 19, hash, 28 );
            p[1] += 28; p[14] = 4; p[18] += 28; break;

        case SIG_RSA_SHA256:
            memcpy( p, ASN1_HASH_SHA2X, 19 );
            memcpy( p + 19, hash, 32 );
            p[1] += 32; p[14] = 1; p[18] += 32; break;

        case SIG_RSA_SHA384:
            memcpy( p, ASN1_HASH_SHA2X, 19 );
            memcpy( p + 19, hash, 48 );
            p[1] += 48; p[14] = 2; p[18] += 48; break;

        case SIG_RSA_SHA512:
            memcpy( p, ASN1_HASH_SHA2X, 19 );
            memcpy( p + 19, hash, 64 );
            p[1] += 64; p[14] = 3; p[18] += 64; break;

        default:
            return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
    }

    return( ( mode == RSA_PUBLIC )
            ? rsa_public(  ctx, sig, sig )
            : rsa_private( ctx, sig, sig ) );
}

/*
 * Do an RSA operation and check the message digest
 */
int rsa_pkcs1_verify( rsa_context *ctx,
                      int mode,
                      int hash_id,
                      int hashlen,
                      const unsigned char *hash,
                      unsigned char *sig )
{
    int ret, len, siglen;
    unsigned char *p, c;
    unsigned char buf[1024];

    siglen = ctx->len;

    if( siglen < 16 || siglen > (int) sizeof( buf ) )
        return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );

    ret = ( mode == RSA_PUBLIC )
          ? rsa_public(  ctx, sig, buf )
          : rsa_private( ctx, sig, buf );

    if( ret != 0 )
        return( ret );

    p = buf;

    switch( ctx->padding )
    {
        case RSA_PKCS_V15:

            if( *p++ != 0 || *p++ != RSA_SIGN )
                return( POLARSSL_ERR_RSA_INVALID_PADDING );

            while( *p != 0 )
            {
                if( p >= buf + siglen - 1 || *p != 0xFF )
                    return( POLARSSL_ERR_RSA_INVALID_PADDING );
                p++;
            }
            p++;
            break;

        default:

            return( POLARSSL_ERR_RSA_INVALID_PADDING );
    }

    len = siglen - (int)( p - buf );

    if( len == 34 )
    {
        c = p[13];
        p[13] = 0;

        if( memcmp( p, ASN1_HASH_MDX, 18 ) != 0 )
            return( POLARSSL_ERR_RSA_VERIFY_FAILED );

        if( ( c == 2 && hash_id == SIG_RSA_MD2 ) ||
            ( c == 4 && hash_id == SIG_RSA_MD4 ) ||
            ( c == 5 && hash_id == SIG_RSA_MD5 ) )
        {
            if( memcmp( p + 18, hash, 16 ) == 0 )
                return( 0 );
            else
                return( POLARSSL_ERR_RSA_VERIFY_FAILED );
        }
    }

    if( len == 35 && hash_id == SIG_RSA_SHA1 )
    {
        if( memcmp( p, ASN1_HASH_SHA1, 15 ) == 0 &&
            memcmp( p + 15, hash, 20 ) == 0 )
            return( 0 );
        else
            return( POLARSSL_ERR_RSA_VERIFY_FAILED );
    }
    if( ( len == 19 + 28 && p[14] == 4 && hash_id == SIG_RSA_SHA224 ) ||
        ( len == 19 + 32 && p[14] == 1 && hash_id == SIG_RSA_SHA256 ) ||
        ( len == 19 + 48 && p[14] == 2 && hash_id == SIG_RSA_SHA384 ) ||
        ( len == 19 + 64 && p[14] == 3 && hash_id == SIG_RSA_SHA512 ) )
    {
    	c = p[1] - 17;
        p[1] = 17;
        p[14] = 0;

        if( p[18] == c &&
                memcmp( p, ASN1_HASH_SHA2X, 18 ) == 0 &&
                memcmp( p + 19, hash, c ) == 0 )
            return( 0 );
        else
            return( POLARSSL_ERR_RSA_VERIFY_FAILED );
    }

    if( len == hashlen && hash_id == SIG_RSA_RAW )
    {
        if( memcmp( p, hash, hashlen ) == 0 )
            return( 0 );
        else
            return( POLARSSL_ERR_RSA_VERIFY_FAILED );
    }

    return( POLARSSL_ERR_RSA_INVALID_PADDING );
}

/*
 * Free the components of an RSA key
 */
void rsa_free( rsa_context *ctx )
{
    mpi_free( &ctx->RQ, &ctx->RP, &ctx->RN,
              &ctx->QP, &ctx->DQ, &ctx->DP,
              &ctx->Q,  &ctx->P,  &ctx->D,
              &ctx->E,  &ctx->N,  NULL );
}

#if defined(POLARSSL_SELF_TEST)

#include "polarssl/sha1.h"

/*
 * Example RSA-1024 keypair, for test purposes
 */
#define KEY_LEN 128

#define RSA_N   "9292758453063D803DD603D5E777D788" \
                "8ED1D5BF35786190FA2F23EBC0848AEA" \
                "DDA92CA6C3D80B32C4D109BE0F36D6AE" \
                "7130B9CED7ACDF54CFC7555AC14EEBAB" \
                "93A89813FBF3C4F8066D2D800F7C38A8" \
                "1AE31942917403FF4946B0A83D3D3E05" \
                "EE57C6F5F5606FB5D4BC6CD34EE0801A" \
                "5E94BB77B07507233A0BC7BAC8F90F79"

#define RSA_E   "10001"

#define RSA_D   "24BF6185468786FDD303083D25E64EFC" \
                "66CA472BC44D253102F8B4A9D3BFA750" \
                "91386C0077937FE33FA3252D28855837" \
                "AE1B484A8A9A45F7EE8C0C634F99E8CD" \
                "DF79C5CE07EE72C7F123142198164234" \
                "CABB724CF78B8173B9F880FC86322407" \
                "AF1FEDFDDE2BEB674CA15F3E81A1521E" \
                "071513A1E85B5DFA031F21ECAE91A34D"

#define RSA_P   "C36D0EB7FCD285223CFB5AABA5BDA3D8" \
                "2C01CAD19EA484A87EA4377637E75500" \
                "FCB2005C5C7DD6EC4AC023CDA285D796" \
                "C3D9E75E1EFC42488BB4F1D13AC30A57"

#define RSA_Q   "C000DF51A7C77AE8D7C7370C1FF55B69" \
                "E211C2B9E5DB1ED0BF61D0D9899620F4" \
                "910E4168387E3C30AA1E00C339A79508" \
                "8452DD96A9A5EA5D9DCA68DA636032AF"

#define RSA_DP  "C1ACF567564274FB07A0BBAD5D26E298" \
                "3C94D22288ACD763FD8E5600ED4A702D" \
                "F84198A5F06C2E72236AE490C93F07F8" \
                "3CC559CD27BC2D1CA488811730BB5725"

#define RSA_DQ  "4959CBF6F8FEF750AEE6977C155579C7" \
                "D8AAEA56749EA28623272E4F7D0592AF" \
                "7C1F1313CAC9471B5C523BFE592F517B" \
                "407A1BD76C164B93DA2D32A383E58357"

#define RSA_QP  "9AE7FBC99546432DF71896FC239EADAE" \
                "F38D18D2B2F0E2DD275AA977E2BF4411" \
                "F5A3B2A5D33605AEBBCCBA7FEB9F2D2F" \
                "A74206CEC169D74BF5A8C50D6F48EA08"

#define PT_LEN  24
#define RSA_PT  "\xAA\xBB\xCC\x03\x02\x01\x00\xFF\xFF\xFF\xFF\xFF" \
                "\x11\x22\x33\x0A\x0B\x0C\xCC\xDD\xDD\xDD\xDD\xDD"

static int myrand( void *rng_state )
{
    if( rng_state != NULL )
        rng_state  = NULL;

    return( rand() );
}

/*
 * Checkup routine
 */
int rsa_self_test( int verbose )
{
    int len;
    rsa_context rsa;
    unsigned char sha1sum[20];
    unsigned char rsa_plaintext[PT_LEN];
    unsigned char rsa_decrypted[PT_LEN];
    unsigned char rsa_ciphertext[KEY_LEN];

    rsa_init( &rsa, RSA_PKCS_V15, 0 );

    rsa.len = KEY_LEN;
    mpi_read_string( &rsa.N , 16, RSA_N  );
    mpi_read_string( &rsa.E , 16, RSA_E  );
    mpi_read_string( &rsa.D , 16, RSA_D  );
    mpi_read_string( &rsa.P , 16, RSA_P  );
    mpi_read_string( &rsa.Q , 16, RSA_Q  );
    mpi_read_string( &rsa.DP, 16, RSA_DP );
    mpi_read_string( &rsa.DQ, 16, RSA_DQ );
    mpi_read_string( &rsa.QP, 16, RSA_QP );

    if( verbose != 0 )
        printf( "  RSA key validation: " );

    if( rsa_check_pubkey(  &rsa ) != 0 ||
        rsa_check_privkey( &rsa ) != 0 )
    {
        if( verbose != 0 )
            printf( "failed\n" );

        return( 1 );
    }

    if( verbose != 0 )
        printf( "passed\n  PKCS#1 encryption : " );

    memcpy( rsa_plaintext, RSA_PT, PT_LEN );

    if( rsa_pkcs1_encrypt( &rsa, &myrand, NULL, RSA_PUBLIC, PT_LEN,
                           rsa_plaintext, rsa_ciphertext ) != 0 )
    {
        if( verbose != 0 )
            printf( "failed\n" );

        return( 1 );
    }

    if( verbose != 0 )
        printf( "passed\n  PKCS#1 decryption : " );

    if( rsa_pkcs1_decrypt( &rsa, RSA_PRIVATE, &len,
                           rsa_ciphertext, rsa_decrypted,
			   sizeof(rsa_decrypted) ) != 0 )
    {
        if( verbose != 0 )
            printf( "failed\n" );

        return( 1 );
    }

    if( memcmp( rsa_decrypted, rsa_plaintext, len ) != 0 )
    {
        if( verbose != 0 )
            printf( "failed\n" );

        return( 1 );
    }

    if( verbose != 0 )
        printf( "passed\n  PKCS#1 data sign  : " );

    sha1( rsa_plaintext, PT_LEN, sha1sum );

    if( rsa_pkcs1_sign( &rsa, RSA_PRIVATE, SIG_RSA_SHA1, 20,
                        sha1sum, rsa_ciphertext ) != 0 )
    {
        if( verbose != 0 )
            printf( "failed\n" );

        return( 1 );
    }

    if( verbose != 0 )
        printf( "passed\n  PKCS#1 sig. verify: " );

    if( rsa_pkcs1_verify( &rsa, RSA_PUBLIC, SIG_RSA_SHA1, 20,
                          sha1sum, rsa_ciphertext ) != 0 )
    {
        if( verbose != 0 )
            printf( "failed\n" );

        return( 1 );
    }

    if( verbose != 0 )
        printf( "passed\n\n" );

    rsa_free( &rsa );

    return( 0 );
}

#endif

#endif
Commit	Line	Data
80a47a2c TK	1	/*
	2	* The RSA public-key cryptosystem
	3	*
62d3e98d TK	4	* Copyright (C) 2006-2010, Brainspark B.V.
	5	*
	6	* This file is part of PolarSSL (http://www.polarssl.org)
	7	* Lead Maintainer: Paul Bakker <polarssl_maintainer at polarssl.org>
80a47a2c	8	*
62d3e98d	9	* All rights reserved.
80a47a2c TK	10	*
	11	* This program is free software; you can redistribute it and/or modify
	12	* it under the terms of the GNU General Public License as published by
	13	* the Free Software Foundation; either version 2 of the License, or
	14	* (at your option) any later version.
	15	*
	16	* This program is distributed in the hope that it will be useful,
	17	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	18	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	19	* GNU General Public License for more details.
	20	*
	21	* You should have received a copy of the GNU General Public License along
	22	* with this program; if not, write to the Free Software Foundation, Inc.,
	23	* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
	24	*/
	25	/*
	26	* RSA was designed by Ron Rivest, Adi Shamir and Len Adleman.
	27	*
	28	* http://theory.lcs.mit.edu/~rivest/rsapaper.pdf
	29	* http://www.cacr.math.uwaterloo.ca/hac/about/chap8.pdf
	30	*/
	31
ac3ad426 AM	32	#include "polarssl/config.h"
	33
	34	#if defined(POLARSSL_RSA_C)
	35
	36	#include "polarssl/rsa.h"
80a47a2c TK	37
	38	#include <stdlib.h>
	39	#include <string.h>
	40	#include <stdio.h>
	41
80a47a2c TK	42	/*
	43	* Initialize an RSA context
	44	*/
	45	void rsa_init( rsa_context *ctx,
	46	int padding,
62d3e98d	47	int hash_id )
80a47a2c TK	48	{
	49	memset( ctx, 0, sizeof( rsa_context ) );
	50
	51	ctx->padding = padding;
	52	ctx->hash_id = hash_id;
62d3e98d TK	53	}
	54
	55	#if defined(POLARSSL_GENPRIME)
	56
	57	/*
	58	* Generate an RSA keypair
	59	*/
	60	int rsa_gen_key( rsa_context *ctx,
	61	int (f_rng)(void ),
	62	void *p_rng,
	63	int nbits, int exponent )
	64	{
	65	int ret;
	66	mpi P1, Q1, H, G;
	67
	68	if( f_rng == NULL \|\| nbits < 128 \|\| exponent < 3 )
	69	return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
	70
	71	mpi_init( &P1, &Q1, &H, &G, NULL );
	72
	73	/*
	74	* find primes P and Q with Q < P so that:
	75	* GCD( E, (P-1)*(Q-1) ) == 1
	76	*/
	77	MPI_CHK( mpi_lset( &ctx->E, exponent ) );
	78
	79	do
	80	{
94431adb	81	MPI_CHK( mpi_gen_prime( &ctx->P, ( nbits + 1 ) >> 1, 0,
62d3e98d TK	82	f_rng, p_rng ) );
	83
	84	MPI_CHK( mpi_gen_prime( &ctx->Q, ( nbits + 1 ) >> 1, 0,
	85	f_rng, p_rng ) );
	86
	87	if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) < 0 )
	88	mpi_swap( &ctx->P, &ctx->Q );
	89
	90	if( mpi_cmp_mpi( &ctx->P, &ctx->Q ) == 0 )
	91	continue;
80a47a2c	92
62d3e98d TK	93	MPI_CHK( mpi_mul_mpi( &ctx->N, &ctx->P, &ctx->Q ) );
	94	if( mpi_msb( &ctx->N ) != nbits )
	95	continue;
	96
	97	MPI_CHK( mpi_sub_int( &P1, &ctx->P, 1 ) );
	98	MPI_CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) );
	99	MPI_CHK( mpi_mul_mpi( &H, &P1, &Q1 ) );
	100	MPI_CHK( mpi_gcd( &G, &ctx->E, &H ) );
	101	}
	102	while( mpi_cmp_int( &G, 1 ) != 0 );
	103
	104	/*
	105	* D = E^-1 mod ((P-1)*(Q-1))
	106	* DP = D mod (P - 1)
	107	* DQ = D mod (Q - 1)
	108	* QP = Q^-1 mod P
	109	*/
	110	MPI_CHK( mpi_inv_mod( &ctx->D , &ctx->E, &H ) );
	111	MPI_CHK( mpi_mod_mpi( &ctx->DP, &ctx->D, &P1 ) );
	112	MPI_CHK( mpi_mod_mpi( &ctx->DQ, &ctx->D, &Q1 ) );
	113	MPI_CHK( mpi_inv_mod( &ctx->QP, &ctx->Q, &ctx->P ) );
	114
	115	ctx->len = ( mpi_msb( &ctx->N ) + 7 ) >> 3;
	116
	117	cleanup:
	118
	119	mpi_free( &G, &H, &Q1, &P1, NULL );
	120
	121	if( ret != 0 )
	122	{
	123	rsa_free( ctx );
	124	return( POLARSSL_ERR_RSA_KEY_GEN_FAILED \| ret );
	125	}
	126
94431adb	127	return( 0 );
80a47a2c TK	128	}
80a47a2c TK	129
62d3e98d	130	#endif
80a47a2c TK	131
	132	/*
	133	* Check a public RSA key
	134	*/
62d3e98d	135	int rsa_check_pubkey( const rsa_context *ctx )
80a47a2c	136	{
67932e54 TK	137	if( !ctx->N.p \|\| !ctx->E.p )
	138	return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
	139
80a47a2c TK	140	if( ( ctx->N.p[0] & 1 ) == 0 \|\|
	141	( ctx->E.p[0] & 1 ) == 0 )
	142	return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
	143
	144	if( mpi_msb( &ctx->N ) < 128 \|\|
	145	mpi_msb( &ctx->N ) > 4096 )
	146	return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
	147
	148	if( mpi_msb( &ctx->E ) < 2 \|\|
	149	mpi_msb( &ctx->E ) > 64 )
	150	return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
	151
	152	return( 0 );
	153	}
	154
	155	/*
	156	* Check a private RSA key
	157	*/
62d3e98d	158	int rsa_check_privkey( const rsa_context *ctx )
80a47a2c TK	159	{
80a47a2c TK	160	int ret;
62d3e98d	161	mpi PQ, DE, P1, Q1, H, I, G, G2, L1, L2;
80a47a2c TK	162
	163	if( ( ret = rsa_check_pubkey( ctx ) ) != 0 )
	164	return( ret );
	165
67932e54 TK	166	if( !ctx->P.p \|\| !ctx->Q.p \|\| !ctx->D.p )
	167	return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED );
	168
62d3e98d	169	mpi_init( &PQ, &DE, &P1, &Q1, &H, &I, &G, &G2, &L1, &L2, NULL );
80a47a2c TK	170
	171	MPI_CHK( mpi_mul_mpi( &PQ, &ctx->P, &ctx->Q ) );
	172	MPI_CHK( mpi_mul_mpi( &DE, &ctx->D, &ctx->E ) );
	173	MPI_CHK( mpi_sub_int( &P1, &ctx->P, 1 ) );
	174	MPI_CHK( mpi_sub_int( &Q1, &ctx->Q, 1 ) );
	175	MPI_CHK( mpi_mul_mpi( &H, &P1, &Q1 ) );
80a47a2c TK	176	MPI_CHK( mpi_gcd( &G, &ctx->E, &H ) );
80a47a2c TK	177
62d3e98d	178	MPI_CHK( mpi_gcd( &G2, &P1, &Q1 ) );
94431adb	179	MPI_CHK( mpi_div_mpi( &L1, &L2, &H, &G2 ) );
62d3e98d TK	180	MPI_CHK( mpi_mod_mpi( &I, &DE, &L1 ) );
	181
	182	/*
	183	* Check for a valid PKCS1v2 private key
	184	*/
80a47a2c	185	if( mpi_cmp_mpi( &PQ, &ctx->N ) == 0 &&
62d3e98d	186	mpi_cmp_int( &L2, 0 ) == 0 &&
80a47a2c TK	187	mpi_cmp_int( &I, 1 ) == 0 &&
	188	mpi_cmp_int( &G, 1 ) == 0 )
	189	{
62d3e98d	190	mpi_free( &G, &I, &H, &Q1, &P1, &DE, &PQ, &G2, &L1, &L2, NULL );
80a47a2c TK	191	return( 0 );
	192	}
	193
94431adb	194
80a47a2c TK	195	cleanup:
80a47a2c TK	196
62d3e98d	197	mpi_free( &G, &I, &H, &Q1, &P1, &DE, &PQ, &G2, &L1, &L2, NULL );
80a47a2c TK	198	return( POLARSSL_ERR_RSA_KEY_CHECK_FAILED \| ret );
	199	}
	200
	201	/*
	202	* Do an RSA public key operation
	203	*/
	204	int rsa_public( rsa_context *ctx,
62d3e98d	205	const unsigned char *input,
80a47a2c TK	206	unsigned char *output )
	207	{
	208	int ret, olen;
	209	mpi T;
	210
	211	mpi_init( &T, NULL );
	212
	213	MPI_CHK( mpi_read_binary( &T, input, ctx->len ) );
	214
	215	if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 )
	216	{
	217	mpi_free( &T, NULL );
	218	return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
	219	}
	220
	221	olen = ctx->len;
	222	MPI_CHK( mpi_exp_mod( &T, &T, &ctx->E, &ctx->N, &ctx->RN ) );
	223	MPI_CHK( mpi_write_binary( &T, output, olen ) );
	224
	225	cleanup:
	226
	227	mpi_free( &T, NULL );
	228
	229	if( ret != 0 )
	230	return( POLARSSL_ERR_RSA_PUBLIC_FAILED \| ret );
	231
	232	return( 0 );
	233	}
	234
	235	/*
	236	* Do an RSA private key operation
	237	*/
	238	int rsa_private( rsa_context *ctx,
62d3e98d	239	const unsigned char *input,
80a47a2c TK	240	unsigned char *output )
	241	{
	242	int ret, olen;
	243	mpi T, T1, T2;
	244
	245	mpi_init( &T, &T1, &T2, NULL );
	246
	247	MPI_CHK( mpi_read_binary( &T, input, ctx->len ) );
	248
	249	if( mpi_cmp_mpi( &T, &ctx->N ) >= 0 )
	250	{
	251	mpi_free( &T, NULL );
	252	return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
	253	}
	254
	255	#if 0
	256	MPI_CHK( mpi_exp_mod( &T, &T, &ctx->D, &ctx->N, &ctx->RN ) );
	257	#else
	258	/*
	259	* faster decryption using the CRT
	260	*
	261	* T1 = input ^ dP mod P
	262	* T2 = input ^ dQ mod Q
	263	*/
	264	MPI_CHK( mpi_exp_mod( &T1, &T, &ctx->DP, &ctx->P, &ctx->RP ) );
	265	MPI_CHK( mpi_exp_mod( &T2, &T, &ctx->DQ, &ctx->Q, &ctx->RQ ) );
	266
	267	/*
	268	* T = (T1 - T2) * (Q^-1 mod P) mod P
	269	*/
	270	MPI_CHK( mpi_sub_mpi( &T, &T1, &T2 ) );
	271	MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->QP ) );
	272	MPI_CHK( mpi_mod_mpi( &T, &T1, &ctx->P ) );
	273
	274	/*
	275	* output = T2 + T * Q
	276	*/
	277	MPI_CHK( mpi_mul_mpi( &T1, &T, &ctx->Q ) );
	278	MPI_CHK( mpi_add_mpi( &T, &T2, &T1 ) );
	279	#endif
	280
	281	olen = ctx->len;
	282	MPI_CHK( mpi_write_binary( &T, output, olen ) );
	283
	284	cleanup:
	285
	286	mpi_free( &T, &T1, &T2, NULL );
	287
	288	if( ret != 0 )
	289	return( POLARSSL_ERR_RSA_PRIVATE_FAILED \| ret );
	290
	291	return( 0 );
	292	}
	293
	294	/*
	295	* Add the message padding, then do an RSA operation
	296	*/
	297	int rsa_pkcs1_encrypt( rsa_context *ctx,
62d3e98d TK	298	int (f_rng)(void ),
62d3e98d TK	299	void *p_rng,
80a47a2c	300	int mode, int ilen,
62d3e98d	301	const unsigned char *input,
80a47a2c TK	302	unsigned char *output )
	303	{
	304	int nb_pad, olen;
	305	unsigned char *p = output;
	306
	307	olen = ctx->len;
	308
	309	switch( ctx->padding )
	310	{
	311	case RSA_PKCS_V15:
	312
62d3e98d	313	if( ilen < 0 \|\| olen < ilen + 11 \|\| f_rng == NULL )
80a47a2c TK	314	return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
	315
	316	nb_pad = olen - 3 - ilen;
	317
	318	*p++ = 0;
	319	*p++ = RSA_CRYPT;
	320
	321	while( nb_pad-- > 0 )
	322	{
62d3e98d TK	323	int rng_dl = 100;
62d3e98d TK	324
80a47a2c	325	do {
62d3e98d TK	326	*p = (unsigned char) f_rng( p_rng );
	327	} while( *p == 0 && --rng_dl );
	328
	329	// Check if RNG failed to generate data
	330	//
	331	if( rng_dl == 0 )
	332	return POLARSSL_ERR_RSA_RNG_FAILED;
	333
80a47a2c TK	334	p++;
	335	}
	336	*p++ = 0;
	337	memcpy( p, input, ilen );
	338	break;
	339
	340	default:
	341
	342	return( POLARSSL_ERR_RSA_INVALID_PADDING );
	343	}
	344
	345	return( ( mode == RSA_PUBLIC )
	346	? rsa_public( ctx, output, output )
	347	: rsa_private( ctx, output, output ) );
	348	}
	349
	350	/*
	351	* Do an RSA operation, then remove the message padding
	352	*/
	353	int rsa_pkcs1_decrypt( rsa_context *ctx,
	354	int mode, int *olen,
62d3e98d	355	const unsigned char *input,
80a47a2c	356	unsigned char *output,
67932e54	357	int output_max_len)
80a47a2c TK	358	{
	359	int ret, ilen;
	360	unsigned char *p;
67932e54	361	unsigned char buf[1024];
80a47a2c TK	362
	363	ilen = ctx->len;
	364
	365	if( ilen < 16 \|\| ilen > (int) sizeof( buf ) )
	366	return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
	367
	368	ret = ( mode == RSA_PUBLIC )
	369	? rsa_public( ctx, input, buf )
	370	: rsa_private( ctx, input, buf );
	371
	372	if( ret != 0 )
	373	return( ret );
	374
	375	p = buf;
	376
	377	switch( ctx->padding )
	378	{
	379	case RSA_PKCS_V15:
	380
	381	if( p++ != 0 \|\| p++ != RSA_CRYPT )
	382	return( POLARSSL_ERR_RSA_INVALID_PADDING );
	383
	384	while( *p != 0 )
	385	{
	386	if( p >= buf + ilen - 1 )
	387	return( POLARSSL_ERR_RSA_INVALID_PADDING );
	388	p++;
	389	}
	390	p++;
	391	break;
	392
	393	default:
	394
	395	return( POLARSSL_ERR_RSA_INVALID_PADDING );
	396	}
	397
	398	if (ilen - (int)(p - buf) > output_max_len)
ac3ad426	399	return( POLARSSL_ERR_RSA_OUTPUT_TOO_LARGE );
80a47a2c TK	400
	401	*olen = ilen - (int)(p - buf);
	402	memcpy( output, p, *olen );
	403
	404	return( 0 );
	405	}
	406
	407	/*
	408	* Do an RSA operation to sign the message digest
	409	*/
	410	int rsa_pkcs1_sign( rsa_context *ctx,
	411	int mode,
	412	int hash_id,
	413	int hashlen,
62d3e98d	414	const unsigned char *hash,
80a47a2c TK	415	unsigned char *sig )
	416	{
	417	int nb_pad, olen;
	418	unsigned char *p = sig;
	419
	420	olen = ctx->len;
	421
	422	switch( ctx->padding )
	423	{
	424	case RSA_PKCS_V15:
	425
	426	switch( hash_id )
	427	{
67932e54	428	case SIG_RSA_RAW:
80a47a2c TK	429	nb_pad = olen - 3 - hashlen;
	430	break;
	431
67932e54 TK	432	case SIG_RSA_MD2:
	433	case SIG_RSA_MD4:
	434	case SIG_RSA_MD5:
	435	nb_pad = olen - 3 - 34;
80a47a2c TK	436	break;
80a47a2c TK	437
67932e54 TK	438	case SIG_RSA_SHA1:
67932e54 TK	439	nb_pad = olen - 3 - 35;
80a47a2c TK	440	break;
80a47a2c TK	441
67932e54 TK	442	case SIG_RSA_SHA224:
67932e54 TK	443	nb_pad = olen - 3 - 47;
80a47a2c TK	444	break;
80a47a2c TK	445
67932e54 TK	446	case SIG_RSA_SHA256:
	447	nb_pad = olen - 3 - 51;
	448	break;
	449
	450	case SIG_RSA_SHA384:
	451	nb_pad = olen - 3 - 67;
	452	break;
	453
	454	case SIG_RSA_SHA512:
	455	nb_pad = olen - 3 - 83;
	456	break;
	457
	458
80a47a2c TK	459	default:
	460	return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
	461	}
	462
	463	if( nb_pad < 8 )
	464	return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
	465
	466	*p++ = 0;
	467	*p++ = RSA_SIGN;
	468	memset( p, 0xFF, nb_pad );
	469	p += nb_pad;
	470	*p++ = 0;
	471	break;
	472
	473	default:
	474
	475	return( POLARSSL_ERR_RSA_INVALID_PADDING );
	476	}
	477
	478	switch( hash_id )
	479	{
67932e54	480	case SIG_RSA_RAW:
80a47a2c TK	481	memcpy( p, hash, hashlen );
	482	break;
	483
67932e54	484	case SIG_RSA_MD2:
80a47a2c TK	485	memcpy( p, ASN1_HASH_MDX, 18 );
	486	memcpy( p + 18, hash, 16 );
	487	p[13] = 2; break;
	488
67932e54	489	case SIG_RSA_MD4:
80a47a2c TK	490	memcpy( p, ASN1_HASH_MDX, 18 );
	491	memcpy( p + 18, hash, 16 );
	492	p[13] = 4; break;
	493
67932e54	494	case SIG_RSA_MD5:
80a47a2c TK	495	memcpy( p, ASN1_HASH_MDX, 18 );
	496	memcpy( p + 18, hash, 16 );
	497	p[13] = 5; break;
	498
67932e54	499	case SIG_RSA_SHA1:
80a47a2c TK	500	memcpy( p, ASN1_HASH_SHA1, 15 );
	501	memcpy( p + 15, hash, 20 );
	502	break;
	503
67932e54 TK	504	case SIG_RSA_SHA224:
	505	memcpy( p, ASN1_HASH_SHA2X, 19 );
	506	memcpy( p + 19, hash, 28 );
	507	p[1] += 28; p[14] = 4; p[18] += 28; break;
	508
	509	case SIG_RSA_SHA256:
	510	memcpy( p, ASN1_HASH_SHA2X, 19 );
80a47a2c	511	memcpy( p + 19, hash, 32 );
67932e54 TK	512	p[1] += 32; p[14] = 1; p[18] += 32; break;
	513
	514	case SIG_RSA_SHA384:
	515	memcpy( p, ASN1_HASH_SHA2X, 19 );
	516	memcpy( p + 19, hash, 48 );
	517	p[1] += 48; p[14] = 2; p[18] += 48; break;
	518
	519	case SIG_RSA_SHA512:
	520	memcpy( p, ASN1_HASH_SHA2X, 19 );
	521	memcpy( p + 19, hash, 64 );
	522	p[1] += 64; p[14] = 3; p[18] += 64; break;
80a47a2c TK	523
	524	default:
	525	return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
	526	}
	527
	528	return( ( mode == RSA_PUBLIC )
	529	? rsa_public( ctx, sig, sig )
	530	: rsa_private( ctx, sig, sig ) );
	531	}
	532
	533	/*
	534	* Do an RSA operation and check the message digest
	535	*/
	536	int rsa_pkcs1_verify( rsa_context *ctx,
	537	int mode,
	538	int hash_id,
	539	int hashlen,
62d3e98d	540	const unsigned char *hash,
80a47a2c TK	541	unsigned char *sig )
	542	{
	543	int ret, len, siglen;
	544	unsigned char *p, c;
67932e54	545	unsigned char buf[1024];
80a47a2c TK	546
	547	siglen = ctx->len;
	548
	549	if( siglen < 16 \|\| siglen > (int) sizeof( buf ) )
	550	return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
	551
	552	ret = ( mode == RSA_PUBLIC )
	553	? rsa_public( ctx, sig, buf )
	554	: rsa_private( ctx, sig, buf );
	555
	556	if( ret != 0 )
	557	return( ret );
	558
	559	p = buf;
	560
	561	switch( ctx->padding )
	562	{
	563	case RSA_PKCS_V15:
	564
	565	if( p++ != 0 \|\| p++ != RSA_SIGN )
	566	return( POLARSSL_ERR_RSA_INVALID_PADDING );
	567
	568	while( *p != 0 )
	569	{
	570	if( p >= buf + siglen - 1 \|\| *p != 0xFF )
	571	return( POLARSSL_ERR_RSA_INVALID_PADDING );
	572	p++;
	573	}
	574	p++;
	575	break;
	576
	577	default:
	578
	579	return( POLARSSL_ERR_RSA_INVALID_PADDING );
	580	}
	581
	582	len = siglen - (int)( p - buf );
	583
	584	if( len == 34 )
	585	{
	586	c = p[13];
	587	p[13] = 0;
	588
	589	if( memcmp( p, ASN1_HASH_MDX, 18 ) != 0 )
	590	return( POLARSSL_ERR_RSA_VERIFY_FAILED );
	591
67932e54 TK	592	if( ( c == 2 && hash_id == SIG_RSA_MD2 ) \|\|
	593	( c == 4 && hash_id == SIG_RSA_MD4 ) \|\|
	594	( c == 5 && hash_id == SIG_RSA_MD5 ) )
80a47a2c TK	595	{
	596	if( memcmp( p + 18, hash, 16 ) == 0 )
	597	return( 0 );
	598	else
	599	return( POLARSSL_ERR_RSA_VERIFY_FAILED );
	600	}
	601	}
	602
67932e54	603	if( len == 35 && hash_id == SIG_RSA_SHA1 )
80a47a2c TK	604	{
	605	if( memcmp( p, ASN1_HASH_SHA1, 15 ) == 0 &&
	606	memcmp( p + 15, hash, 20 ) == 0 )
	607	return( 0 );
	608	else
	609	return( POLARSSL_ERR_RSA_VERIFY_FAILED );
	610	}
67932e54 TK	611	if( ( len == 19 + 28 && p[14] == 4 && hash_id == SIG_RSA_SHA224 ) \|\|
	612	( len == 19 + 32 && p[14] == 1 && hash_id == SIG_RSA_SHA256 ) \|\|
	613	( len == 19 + 48 && p[14] == 2 && hash_id == SIG_RSA_SHA384 ) \|\|
	614	( len == 19 + 64 && p[14] == 3 && hash_id == SIG_RSA_SHA512 ) )
80a47a2c	615	{
ac3ad426	616	c = p[1] - 17;
67932e54 TK	617	p[1] = 17;
	618	p[14] = 0;
	619
	620	if( p[18] == c &&
	621	memcmp( p, ASN1_HASH_SHA2X, 18 ) == 0 &&
	622	memcmp( p + 19, hash, c ) == 0 )
80a47a2c TK	623	return( 0 );
	624	else
	625	return( POLARSSL_ERR_RSA_VERIFY_FAILED );
	626	}
	627
67932e54	628	if( len == hashlen && hash_id == SIG_RSA_RAW )
80a47a2c TK	629	{
	630	if( memcmp( p, hash, hashlen ) == 0 )
	631	return( 0 );
	632	else
	633	return( POLARSSL_ERR_RSA_VERIFY_FAILED );
	634	}
	635
	636	return( POLARSSL_ERR_RSA_INVALID_PADDING );
	637	}
	638
	639	/*
	640	* Free the components of an RSA key
	641	*/
	642	void rsa_free( rsa_context *ctx )
	643	{
	644	mpi_free( &ctx->RQ, &ctx->RP, &ctx->RN,
	645	&ctx->QP, &ctx->DQ, &ctx->DP,
	646	&ctx->Q, &ctx->P, &ctx->D,
	647	&ctx->E, &ctx->N, NULL );
	648	}
	649
ac3ad426 AM	650	#if defined(POLARSSL_SELF_TEST)
	651
	652	#include "polarssl/sha1.h"
62d3e98d	653
80a47a2c	654	/*
ac3ad426 AM	655	* Example RSA-1024 keypair, for test purposes
	656	*/
	657	#define KEY_LEN 128
	658
	659	#define RSA_N "9292758453063D803DD603D5E777D788" \
	660	"8ED1D5BF35786190FA2F23EBC0848AEA" \
	661	"DDA92CA6C3D80B32C4D109BE0F36D6AE" \
	662	"7130B9CED7ACDF54CFC7555AC14EEBAB" \
	663	"93A89813FBF3C4F8066D2D800F7C38A8" \
	664	"1AE31942917403FF4946B0A83D3D3E05" \
	665	"EE57C6F5F5606FB5D4BC6CD34EE0801A" \
	666	"5E94BB77B07507233A0BC7BAC8F90F79"
	667
	668	#define RSA_E "10001"
	669
	670	#define RSA_D "24BF6185468786FDD303083D25E64EFC" \
	671	"66CA472BC44D253102F8B4A9D3BFA750" \
	672	"91386C0077937FE33FA3252D28855837" \
	673	"AE1B484A8A9A45F7EE8C0C634F99E8CD" \
	674	"DF79C5CE07EE72C7F123142198164234" \
	675	"CABB724CF78B8173B9F880FC86322407" \
	676	"AF1FEDFDDE2BEB674CA15F3E81A1521E" \
	677	"071513A1E85B5DFA031F21ECAE91A34D"
	678
	679	#define RSA_P "C36D0EB7FCD285223CFB5AABA5BDA3D8" \
	680	"2C01CAD19EA484A87EA4377637E75500" \
	681	"FCB2005C5C7DD6EC4AC023CDA285D796" \
	682	"C3D9E75E1EFC42488BB4F1D13AC30A57"
	683
	684	#define RSA_Q "C000DF51A7C77AE8D7C7370C1FF55B69" \
	685	"E211C2B9E5DB1ED0BF61D0D9899620F4" \
	686	"910E4168387E3C30AA1E00C339A79508" \
	687	"8452DD96A9A5EA5D9DCA68DA636032AF"
	688
	689	#define RSA_DP "C1ACF567564274FB07A0BBAD5D26E298" \
	690	"3C94D22288ACD763FD8E5600ED4A702D" \
	691	"F84198A5F06C2E72236AE490C93F07F8" \
	692	"3CC559CD27BC2D1CA488811730BB5725"
	693
	694	#define RSA_DQ "4959CBF6F8FEF750AEE6977C155579C7" \
	695	"D8AAEA56749EA28623272E4F7D0592AF" \
	696	"7C1F1313CAC9471B5C523BFE592F517B" \
	697	"407A1BD76C164B93DA2D32A383E58357"
	698
	699	#define RSA_QP "9AE7FBC99546432DF71896FC239EADAE" \
	700	"F38D18D2B2F0E2DD275AA977E2BF4411" \
	701	"F5A3B2A5D33605AEBBCCBA7FEB9F2D2F" \
	702	"A74206CEC169D74BF5A8C50D6F48EA08"
	703
	704	#define PT_LEN 24
	705	#define RSA_PT "\xAA\xBB\xCC\x03\x02\x01\x00\xFF\xFF\xFF\xFF\xFF" \
	706	"\x11\x22\x33\x0A\x0B\x0C\xCC\xDD\xDD\xDD\xDD\xDD"
	707
	708	static int myrand( void *rng_state )
80a47a2c	709	{
ac3ad426 AM	710	if( rng_state != NULL )
ac3ad426 AM	711	rng_state = NULL;
80a47a2c	712
ac3ad426	713	return( rand() );
80a47a2c TK	714	}
	715
	716	/*
ac3ad426	717	* Checkup routine
80a47a2c	718	*/
ac3ad426	719	int rsa_self_test( int verbose )
80a47a2c	720	{
ac3ad426 AM	721	int len;
	722	rsa_context rsa;
	723	unsigned char sha1sum[20];
	724	unsigned char rsa_plaintext[PT_LEN];
	725	unsigned char rsa_decrypted[PT_LEN];
	726	unsigned char rsa_ciphertext[KEY_LEN];
	727
	728	rsa_init( &rsa, RSA_PKCS_V15, 0 );
	729
	730	rsa.len = KEY_LEN;
	731	mpi_read_string( &rsa.N , 16, RSA_N );
	732	mpi_read_string( &rsa.E , 16, RSA_E );
	733	mpi_read_string( &rsa.D , 16, RSA_D );
	734	mpi_read_string( &rsa.P , 16, RSA_P );
	735	mpi_read_string( &rsa.Q , 16, RSA_Q );
	736	mpi_read_string( &rsa.DP, 16, RSA_DP );
	737	mpi_read_string( &rsa.DQ, 16, RSA_DQ );
	738	mpi_read_string( &rsa.QP, 16, RSA_QP );
	739
	740	if( verbose != 0 )
	741	printf( " RSA key validation: " );
	742
	743	if( rsa_check_pubkey( &rsa ) != 0 \|\|
	744	rsa_check_privkey( &rsa ) != 0 )
80a47a2c	745	{
ac3ad426 AM	746	if( verbose != 0 )
ac3ad426 AM	747	printf( "failed\n" );
80a47a2c	748
ac3ad426	749	return( 1 );
80a47a2c TK	750	}
80a47a2c TK	751
ac3ad426 AM	752	if( verbose != 0 )
ac3ad426 AM	753	printf( "passed\n PKCS#1 encryption : " );
80a47a2c	754
ac3ad426	755	memcpy( rsa_plaintext, RSA_PT, PT_LEN );
80a47a2c	756
ac3ad426 AM	757	if( rsa_pkcs1_encrypt( &rsa, &myrand, NULL, RSA_PUBLIC, PT_LEN,
ac3ad426 AM	758	rsa_plaintext, rsa_ciphertext ) != 0 )
80a47a2c	759	{
ac3ad426 AM	760	if( verbose != 0 )
ac3ad426 AM	761	printf( "failed\n" );
80a47a2c	762
ac3ad426	763	return( 1 );
80a47a2c TK	764	}
80a47a2c TK	765
ac3ad426 AM	766	if( verbose != 0 )
ac3ad426 AM	767	printf( "passed\n PKCS#1 decryption : " );
80a47a2c	768
ac3ad426 AM	769	if( rsa_pkcs1_decrypt( &rsa, RSA_PRIVATE, &len,
	770	rsa_ciphertext, rsa_decrypted,
	771	sizeof(rsa_decrypted) ) != 0 )
80a47a2c	772	{
ac3ad426 AM	773	if( verbose != 0 )
ac3ad426 AM	774	printf( "failed\n" );
80a47a2c	775
ac3ad426	776	return( 1 );
80a47a2c TK	777	}
80a47a2c TK	778
ac3ad426	779	if( memcmp( rsa_decrypted, rsa_plaintext, len ) != 0 )
80a47a2c	780	{
ac3ad426 AM	781	if( verbose != 0 )
ac3ad426 AM	782	printf( "failed\n" );
80a47a2c	783
ac3ad426	784	return( 1 );
80a47a2c TK	785	}
80a47a2c TK	786
ac3ad426 AM	787	if( verbose != 0 )
ac3ad426 AM	788	printf( "passed\n PKCS#1 data sign : " );
80a47a2c	789
ac3ad426	790	sha1( rsa_plaintext, PT_LEN, sha1sum );
80a47a2c	791
ac3ad426 AM	792	if( rsa_pkcs1_sign( &rsa, RSA_PRIVATE, SIG_RSA_SHA1, 20,
ac3ad426 AM	793	sha1sum, rsa_ciphertext ) != 0 )
80a47a2c	794	{
ac3ad426 AM	795	if( verbose != 0 )
ac3ad426 AM	796	printf( "failed\n" );
80a47a2c	797
ac3ad426	798	return( 1 );
80a47a2c TK	799	}
80a47a2c TK	800
ac3ad426 AM	801	if( verbose != 0 )
	802	printf( "passed\n PKCS#1 sig. verify: " );
	803
	804	if( rsa_pkcs1_verify( &rsa, RSA_PUBLIC, SIG_RSA_SHA1, 20,
	805	sha1sum, rsa_ciphertext ) != 0 )
80a47a2c	806	{
ac3ad426 AM	807	if( verbose != 0 )
ac3ad426 AM	808	printf( "failed\n" );
80a47a2c	809
ac3ad426	810	return( 1 );
80a47a2c TK	811	}
80a47a2c TK	812
ac3ad426 AM	813	if( verbose != 0 )
	814	printf( "passed\n\n" );
	815
	816	rsa_free( &rsa );
80a47a2c TK	817
	818	return( 0 );
	819	}
ac3ad426 AM	820
	821	#endif
	822
	823	#endif