/*
* The RSA public-key cryptosystem
*
- * Based on XySSL: Copyright (C) 2006-2008 Christophe Devine
+ * Copyright (C) 2006-2010, Brainspark B.V.
*
- * Copyright (C) 2009 Paul Bakker <polarssl_maintainer at polarssl dot org>
+ * 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
* http://www.cacr.math.uwaterloo.ca/hac/about/chap8.pdf
*/
-/* $Cambridge: exim/src/src/pdkim/rsa.c,v 1.2 2009/06/10 07:34:05 tom Exp $ */
+/* $Cambridge: exim/src/src/pdkim/rsa.c,v 1.3 2009/12/07 13:05:07 tom Exp $ */
#include "rsa.h"
#include "base64.h"
#include <stdio.h>
+
+/* *************** begin copy from x509parse.c ********************/
/*
* ASN.1 DER decoding routines
*/
static int asn1_get_len( unsigned char **p,
- unsigned char *end,
+ const unsigned char *end,
int *len )
{
if( ( end - *p ) < 1 )
}
static int asn1_get_tag( unsigned char **p,
- unsigned char *end,
+ const unsigned char *end,
int *len, int tag )
{
if( ( end - *p ) < 1 )
}
static int asn1_get_int( unsigned char **p,
- unsigned char *end,
+ const unsigned char *end,
int *val )
{
int ret, len;
}
static int asn1_get_mpi( unsigned char **p,
- unsigned char *end,
+ const unsigned char *end,
mpi *X )
{
int ret, len;
return( ret );
}
+/* *************** end copy from x509parse.c ********************/
+
+
/*
*/
void rsa_init( rsa_context *ctx,
int padding,
- int hash_id,
- int (*f_rng)(void *),
- void *p_rng )
+ 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 );
+ }
- ctx->f_rng = f_rng;
- ctx->p_rng = p_rng;
+ return( 0 );
}
+#endif
/*
* Check a public RSA key
*/
-int rsa_check_pubkey( rsa_context *ctx )
+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 );
/*
* Check a private RSA key
*/
-int rsa_check_privkey( rsa_context *ctx )
+int rsa_check_privkey( const rsa_context *ctx )
{
int ret;
- mpi PQ, DE, P1, Q1, H, I, G;
+ mpi PQ, DE, P1, Q1, H, I, G, G2, L1, L2;
if( ( ret = rsa_check_pubkey( ctx ) ) != 0 )
return( ret );
- mpi_init( &PQ, &DE, &P1, &Q1, &H, &I, &G, NULL );
+ 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_mod_mpi( &I, &DE, &H ) );
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, NULL );
+ 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, NULL );
+ 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,
- unsigned char *input,
+ const unsigned char *input,
unsigned char *output )
{
int ret, olen;
* Do an RSA private key operation
*/
int rsa_private( rsa_context *ctx,
- unsigned char *input,
+ const unsigned char *input,
unsigned char *output )
{
int ret, olen;
* 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,
- unsigned char *input,
+ const unsigned char *input,
unsigned char *output )
{
int nb_pad, olen;
{
case RSA_PKCS_V15:
- if( ilen < 0 || olen < ilen + 11 )
+ if( ilen < 0 || olen < ilen + 11 || f_rng == NULL )
return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
nb_pad = olen - 3 - ilen;
while( nb_pad-- > 0 )
{
+ int rng_dl = 100;
+
do {
- *p = (unsigned char) rand();
- } while( *p == 0 );
+ *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;
*/
int rsa_pkcs1_decrypt( rsa_context *ctx,
int mode, int *olen,
- unsigned char *input,
+ const unsigned char *input,
unsigned char *output,
- int output_max_len)
+ int output_max_len)
{
int ret, ilen;
unsigned char *p;
- unsigned char buf[512];
+ unsigned char buf[1024];
ilen = ctx->len;
}
if (ilen - (int)(p - buf) > output_max_len)
- return( POLARSSL_ERR_RSA_OUTPUT_TO_LARGE );
+ return( POLARSSL_ERR_RSA_OUTPUT_TOO_LARGE );
*olen = ilen - (int)(p - buf);
memcpy( output, p, *olen );
int mode,
int hash_id,
int hashlen,
- unsigned char *hash,
+ const unsigned char *hash,
unsigned char *sig )
{
int nb_pad, olen;
switch( hash_id )
{
- case RSA_RAW:
+ case SIG_RSA_RAW:
nb_pad = olen - 3 - hashlen;
break;
- case RSA_MD2:
- case RSA_MD4:
- case RSA_MD5:
- nb_pad = olen - 3 - 16 - 18;
+ 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 RSA_SHA1:
- nb_pad = olen - 3 - 20 - 15;
+ case SIG_RSA_SHA384:
+ nb_pad = olen - 3 - 67;
break;
- case RSA_SHA256:
- nb_pad = olen - 3 - 32 - 19;
+ case SIG_RSA_SHA512:
+ nb_pad = olen - 3 - 83;
break;
+
default:
return( POLARSSL_ERR_RSA_BAD_INPUT_DATA );
}
switch( hash_id )
{
- case RSA_RAW:
+ case SIG_RSA_RAW:
memcpy( p, hash, hashlen );
break;
- case RSA_MD2:
+ case SIG_RSA_MD2:
memcpy( p, ASN1_HASH_MDX, 18 );
memcpy( p + 18, hash, 16 );
p[13] = 2; break;
- case RSA_MD4:
+ case SIG_RSA_MD4:
memcpy( p, ASN1_HASH_MDX, 18 );
memcpy( p + 18, hash, 16 );
p[13] = 4; break;
- case RSA_MD5:
+ case SIG_RSA_MD5:
memcpy( p, ASN1_HASH_MDX, 18 );
memcpy( p + 18, hash, 16 );
p[13] = 5; break;
- case RSA_SHA1:
+ case SIG_RSA_SHA1:
memcpy( p, ASN1_HASH_SHA1, 15 );
memcpy( p + 15, hash, 20 );
break;
- case RSA_SHA256:
- memcpy( p, ASN1_HASH_SHA256, 19 );
+ 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 );
- break;
+ 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 );
int mode,
int hash_id,
int hashlen,
- unsigned char *hash,
+ const unsigned char *hash,
unsigned char *sig )
{
int ret, len, siglen;
unsigned char *p, c;
- unsigned char buf[512];
+ unsigned char buf[1024];
siglen = ctx->len;
if( memcmp( p, ASN1_HASH_MDX, 18 ) != 0 )
return( POLARSSL_ERR_RSA_VERIFY_FAILED );
- if( ( c == 2 && hash_id == RSA_MD2 ) ||
- ( c == 4 && hash_id == RSA_MD4 ) ||
- ( c == 5 && hash_id == RSA_MD5 ) )
+ 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 );
}
}
- if( len == 35 && hash_id == RSA_SHA1 )
+ if( len == 35 && hash_id == SIG_RSA_SHA1 )
{
if( memcmp( p, ASN1_HASH_SHA1, 15 ) == 0 &&
memcmp( p + 15, hash, 20 ) == 0 )
else
return( POLARSSL_ERR_RSA_VERIFY_FAILED );
}
-
- if( len == 51 && hash_id == RSA_SHA256 )
+ 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 ) )
{
- if( memcmp( p, ASN1_HASH_SHA256, 19 ) == 0 &&
- memcmp( p + 19, hash, 32 ) == 0 )
+ 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 == RSA_RAW )
+ if( len == hashlen && hash_id == SIG_RSA_RAW )
{
if( memcmp( p, hash, hashlen ) == 0 )
return( 0 );
}
+/* PDKIM code (not copied from polarssl) */
/*
* Parse a public RSA key