home *** CD-ROM | disk | FTP | other *** search
/ linuxmafia.com 2013 / 2013.06.linuxmafia.com / linuxmafia.com / pub / linux / security / gnupg / rsa.c < prev   
Encoding:
C/C++ Source or Header  |  2000-09-06  |  14.0 KB  |  533 lines
  1. /* rsa.c  -  RSA function
  2.  *    Copyright (c) 1997,1998,1999 by Werner Koch (dd9jn)
  3.  ***********************************************************************
  4.  * ATTENTION: This code should not be exported to the United States
  5.  * nor should it be used there without a license agreement with PKP.
  6.  * The RSA algorithm is protected by U.S. Patent #4,405,829 which
  7.  * expires on September 20, 2000!
  8.  ***********************************************************************
  9.  *
  10.  * Permission is hereby granted, free of charge, to any person obtaining a
  11.  * copy of this software and associated documentation files (the "Software"),
  12.  * to deal in the Software without restriction, including without limitation
  13.  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  14.  * and/or sell copies of the Software, and to permit persons to whom the
  15.  * Software is furnished to do so, subject to the following conditions:
  16.  *
  17.  * The above copyright notice and this permission notice shall be included in
  18.  * all copies or substantial portions of the Software.
  19.  *
  20.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  21.  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  22.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  23.  * WERNER KOCH BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  24.  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  25.  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  26.  *
  27.  * Except as contained in this notice, the name of Werner Koch shall not be
  28.  * used in advertising or otherwise to promote the sale, use or other dealings
  29.  * in this Software without prior written authorization from Werner Koch.
  30.  */
  31.  
  32. /* How to compile:
  33.  *
  34.      gcc -Wall -O2 -shared -fPIC -o rsa rsa.c
  35.  */
  36.  
  37. #include <stdio.h>
  38. #include <stdlib.h>
  39. #include <string.h>
  40. #include <assert.h>
  41.  
  42. /* configuration stuff */
  43. #ifdef __alpha__
  44.   #define SIZEOF_UNSIGNED_LONG 8
  45. #else
  46.   #define SIZEOF_UNSIGNED_LONG 4
  47. #endif
  48.  
  49. #if defined(__mc68000__) || defined (__sparc__) || defined (__PPC__) \
  50.     || (defined(__mips__) && (defined(MIPSEB) || defined (__MIPSEB__)) ) \
  51.     || defined(__hpux__)  /* should be replaced by the macro for the PA */
  52.   #define BIG_ENDIAN_HOST 1
  53. #else
  54.   #define LITTLE_ENDIAN_HOST 1
  55. #endif
  56.  
  57. typedef unsigned long  ulong;
  58. typedef unsigned short ushort;
  59. typedef unsigned char  byte;
  60.  
  61. typedef unsigned short u16;
  62. typedef unsigned long  u32;
  63.  
  64. /* end configurable stuff */
  65.  
  66.  
  67. const char * const gnupgext_version = "RSA ($Revision: 1.10 $)";
  68.  
  69. #ifndef DIM
  70.   #define DIM(v) (sizeof(v)/sizeof((v)[0]))
  71.   #define DIMof(type,member)   DIM(((type *)0)->member)
  72. #endif
  73.  
  74. #define is_RSA(a) ((a)>=1 && (a)<=3)
  75.  
  76. #define BAD_ALGO  4
  77. #define BAD_KEY   7
  78. #define BAD_SIGN  8
  79.  
  80. struct mpi_struct { int hidden_stuff; };
  81. typedef struct mpi_struct *MPI;
  82.  
  83. extern int g10c_debug_mode;
  84. extern int g10_opt_verbose;
  85.  
  86.  
  87.  
  88. typedef struct {
  89.     MPI n;        /* modulus */
  90.     MPI e;        /* exponent */
  91. } RSA_public_key;
  92.  
  93.  
  94. typedef struct {
  95.     MPI n;        /* public modulus */
  96.     MPI e;        /* public exponent */
  97.     MPI d;        /* exponent */
  98.     MPI p;        /* prime  p. */
  99.     MPI q;        /* prime  q. */
  100.     MPI u;        /* inverse of p mod q. */
  101. } RSA_secret_key;
  102.  
  103. /* imports */
  104. void *g10_malloc( size_t n );
  105. void *g10_calloc( size_t n );
  106. void g10_free( void *p);
  107. void g10_log_fatal( const char *fmt, ... );
  108. void g10_log_error( const char *fmt, ... );
  109. void g10_log_info( const char *fmt, ... );
  110. void g10_log_debug( const char *fmt, ... );
  111. void g10_log_hexdump( const char *text, char *buf, size_t len );
  112. void g10_log_mpidump( const char *text, MPI a );
  113. MPI  g10c_generate_secret_prime( unsigned nbits );
  114. char *g10c_get_random_bits( unsigned nbits, int level, int secure );
  115. MPI  g10m_new( unsigned nbits );
  116. MPI  g10m_new_secure( unsigned nbits );
  117. void g10m_release( MPI a );
  118. void g10m_set( MPI w, MPI u);
  119. void g10m_set_ui( MPI w, unsigned long u);
  120. void g10m_set_buffer( MPI a, const char *buffer, unsigned nbytes, int sign );
  121. MPI  g10m_copy( MPI a );
  122. void g10m_swap( MPI a, MPI b);
  123. unsigned g10m_get_nbits( MPI a );
  124. unsigned g10m_get_size( MPI a );
  125. int  g10m_cmp( MPI u, MPI v );
  126. void g10m_add_ui(MPI w, MPI u, unsigned long v );
  127. void g10m_sub_ui(MPI w, MPI u, unsigned long v );
  128. void g10m_mul( MPI w, MPI u, MPI v);
  129. void g10m_fdiv_q( MPI quot, MPI dividend, MPI divisor );
  130. void g10m_powm( MPI res, MPI base, MPI exp, MPI mod);
  131. int  g10m_gcd( MPI g, MPI a, MPI b );
  132. int  g10m_invm( MPI x, MPI u, MPI v );
  133.  
  134. /* local prototypes */
  135. static void test_keys( RSA_secret_key *sk, unsigned nbits );
  136. static void generate( RSA_secret_key *sk, unsigned nbits );
  137. static int  check_secret_key( RSA_secret_key *sk );
  138. static void public(MPI output, MPI input, RSA_public_key *skey );
  139. static void secret(MPI output, MPI input, RSA_secret_key *skey );
  140.  
  141.  
  142. static void
  143. test_keys( RSA_secret_key *sk, unsigned nbits )
  144. {
  145.     RSA_public_key pk;
  146.     MPI test = g10m_new( nbits );
  147.     MPI out1 = g10m_new( nbits );
  148.     MPI out2 = g10m_new( nbits );
  149.  
  150.     pk.n = sk->n;
  151.     pk.e = sk->e;
  152.     {    char *p = g10c_get_random_bits( nbits, 0, 0 );
  153.     g10m_set_buffer( test, p, (nbits+7)/8, 0 );
  154.     g10_free(p);
  155.     }
  156.  
  157.     public( out1, test, &pk );
  158.     secret( out2, out1, sk );
  159.     if( g10m_cmp( test, out2 ) )
  160.     g10_log_fatal("RSA operation: public, secret failed\n");
  161.     secret( out1, test, sk );
  162.     public( out2, out1, &pk );
  163.     if( g10m_cmp( test, out2 ) )
  164.     g10_log_fatal("RSA operation: secret, public failed\n");
  165.     g10m_release( test );
  166.     g10m_release( out1 );
  167.     g10m_release( out2 );
  168. }
  169.  
  170. /****************
  171.  * Generate a key pair with a key of size NBITS
  172.  * Returns: 2 structures filles with all needed values
  173.  */
  174. static void
  175. generate( RSA_secret_key *sk, unsigned nbits )
  176. {
  177.     MPI p, q; /* the two primes */
  178.     MPI d;    /* the private key */
  179.     MPI u;
  180.     MPI t1, t2;
  181.     MPI n;    /* the public key */
  182.     MPI e;    /* the exponent */
  183.     MPI phi;  /* helper: (p-a)(q-1) */
  184.     MPI g;
  185.     MPI f;
  186.  
  187.     /* select two (very secret) primes */
  188.     p = g10c_generate_secret_prime( nbits / 2 );
  189.     q = g10c_generate_secret_prime( nbits / 2 );
  190.     if( g10m_cmp( p, q ) > 0 ) /* p shall be smaller than q (for calc of u)*/
  191.     g10m_swap(p,q);
  192.     /* calculate Euler totient: phi = (p-1)(q-1) */
  193.     t1 = g10m_new_secure( g10m_get_size(p) );
  194.     t2 = g10m_new_secure( g10m_get_size(p) );
  195.     phi = g10m_new_secure( nbits );
  196.     g    = g10m_new_secure( nbits  );
  197.     f    = g10m_new_secure( nbits  );
  198.     g10m_sub_ui( t1, p, 1 );
  199.     g10m_sub_ui( t2, q, 1 );
  200.     g10m_mul( phi, t1, t2 );
  201.     g10m_gcd(g, t1, t2);
  202.     g10m_fdiv_q(f, phi, g);
  203.     /* multiply them to make the private key */
  204.     n = g10m_new( nbits );
  205.     g10m_mul( n, p, q );
  206.     /* find a public exponent  */
  207.     e = g10m_new(6);
  208.     g10m_set_ui( e, 17); /* start with 17 */
  209.     while( !g10m_gcd(t1, e, phi) ) /* (while gcd is not 1) */
  210.     g10m_add_ui( e, e, 2);
  211.     /* calculate the secret key d = e^1 mod phi */
  212.     d = g10m_new( nbits );
  213.     g10m_invm(d, e, f );
  214.     /* calculate the inverse of p and q (used for chinese remainder theorem)*/
  215.     u = g10m_new( nbits );
  216.     g10m_invm(u, p, q );
  217.  
  218.     if( g10c_debug_mode ) {
  219.     g10_log_mpidump("  p= ", p );
  220.     g10_log_mpidump("  q= ", q );
  221.     g10_log_mpidump("phi= ", phi );
  222.     g10_log_mpidump("  g= ", g );
  223.     g10_log_mpidump("  f= ", f );
  224.     g10_log_mpidump("  n= ", n );
  225.     g10_log_mpidump("  e= ", e );
  226.     g10_log_mpidump("  d= ", d );
  227.     g10_log_mpidump("  u= ", u );
  228.     }
  229.  
  230.     g10m_release(t1);
  231.     g10m_release(t2);
  232.     g10m_release(phi);
  233.     g10m_release(f);
  234.     g10m_release(g);
  235.  
  236.     sk->n = n;
  237.     sk->e = e;
  238.     sk->p = p;
  239.     sk->q = q;
  240.     sk->d = d;
  241.     sk->u = u;
  242.  
  243.     /* now we can test our keys (this should never fail!) */
  244.     test_keys( sk, nbits - 64 );
  245. }
  246.  
  247.  
  248. /****************
  249.  * Test wether the secret key is valid.
  250.  * Returns: true if this is a valid key.
  251.  */
  252. static int
  253. check_secret_key( RSA_secret_key *sk )
  254. {
  255.     int rc;
  256.     MPI temp = g10m_new( g10m_get_size(sk->p)*2 );
  257.  
  258.     g10m_mul(temp, sk->p, sk->q );
  259.     rc = g10m_cmp( temp, sk->n );
  260.     g10m_release(temp);
  261.     return !rc;
  262. }
  263.  
  264.  
  265.  
  266. /****************
  267.  * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT.
  268.  *
  269.  *    c = m^e mod n
  270.  *
  271.  * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY.
  272.  */
  273. static void
  274. public(MPI output, MPI input, RSA_public_key *pkey )
  275. {
  276.     if( output == input ) { /* powm doesn't like output and input the same */
  277.     MPI x = g10m_new( g10m_get_size(input)*2 );
  278.     g10m_powm( x, input, pkey->e, pkey->n );
  279.     g10m_set(output, x);
  280.     g10m_release(x);
  281.     }
  282.     else
  283.     g10m_powm( output, input, pkey->e, pkey->n );
  284. }
  285.  
  286. /****************
  287.  * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT.
  288.  *
  289.  *    m = c^d mod n
  290.  *
  291.  * Where m is OUTPUT, c is INPUT and d,n are elements of PKEY.
  292.  *
  293.  * FIXME: We should better use the Chinese Remainder Theorem
  294.  */
  295. static void
  296. secret(MPI output, MPI input, RSA_secret_key *skey )
  297. {
  298.     g10m_powm( output, input, skey->d, skey->n );
  299. }
  300.  
  301.  
  302. /*********************************************
  303.  **************  interface  ******************
  304.  *********************************************/
  305.  
  306. static int
  307. do_generate( int algo, unsigned nbits, MPI *skey, MPI **retfactors )
  308. {
  309.     RSA_secret_key sk;
  310.  
  311.     if( !is_RSA(algo) )
  312.     return BAD_ALGO;
  313.  
  314.     generate( &sk, nbits );
  315.     skey[0] = sk.n;
  316.     skey[1] = sk.e;
  317.     skey[2] = sk.d;
  318.     skey[3] = sk.p;
  319.     skey[4] = sk.q;
  320.     skey[5] = sk.u;
  321.     /* make an empty list of factors */
  322.     *retfactors = g10_calloc( 1 * sizeof **retfactors );
  323.     return 0;
  324. }
  325.  
  326.  
  327. static int
  328. do_check_secret_key( int algo, MPI *skey )
  329. {
  330.     RSA_secret_key sk;
  331.  
  332.     if( !is_RSA(algo) )
  333.     return BAD_ALGO;
  334.  
  335.     sk.n = skey[0];
  336.     sk.e = skey[1];
  337.     sk.d = skey[2];
  338.     sk.p = skey[3];
  339.     sk.q = skey[4];
  340.     sk.u = skey[5];
  341.     if( !check_secret_key( &sk ) )
  342.     return BAD_KEY;
  343.  
  344.     return 0;
  345. }
  346.  
  347.  
  348.  
  349. static int
  350. do_encrypt( int algo, MPI *resarr, MPI data, MPI *pkey )
  351. {
  352.     RSA_public_key pk;
  353.  
  354.     if( algo != 1 && algo != 2 )
  355.     return BAD_ALGO;
  356.  
  357.     pk.n = pkey[0];
  358.     pk.e = pkey[1];
  359.     resarr[0] = g10m_new( g10m_get_size( pk.n ) );
  360.     public( resarr[0], data, &pk );
  361.     return 0;
  362. }
  363.  
  364. static int
  365. do_decrypt( int algo, MPI *result, MPI *data, MPI *skey )
  366. {
  367.     RSA_secret_key sk;
  368.  
  369.     if( algo != 1 && algo != 2 )
  370.     return BAD_ALGO;
  371.  
  372.     sk.n = skey[0];
  373.     sk.e = skey[1];
  374.     sk.d = skey[2];
  375.     sk.p = skey[3];
  376.     sk.q = skey[4];
  377.     sk.u = skey[5];
  378.     *result = g10m_new_secure( g10m_get_size( sk.n ) );
  379.     secret( *result, data[0], &sk );
  380.     return 0;
  381. }
  382.  
  383. static int
  384. do_sign( int algo, MPI *resarr, MPI data, MPI *skey )
  385. {
  386.     RSA_secret_key sk;
  387.  
  388.     if( algo != 1 && algo != 3 )
  389.     return BAD_ALGO;
  390.  
  391.     sk.n = skey[0];
  392.     sk.e = skey[1];
  393.     sk.d = skey[2];
  394.     sk.p = skey[3];
  395.     sk.q = skey[4];
  396.     sk.u = skey[5];
  397.     resarr[0] = g10m_new( g10m_get_size( sk.n ) );
  398.     secret( resarr[0], data, &sk );
  399.  
  400.     return 0;
  401. }
  402.  
  403. static int
  404. do_verify( int algo, MPI hash, MPI *data, MPI *pkey,
  405.        int (*cmp)(void *opaque, MPI tmp), void *opaquev )
  406. {
  407.     RSA_public_key pk;
  408.     MPI result;
  409.     int rc;
  410.  
  411.     if( algo != 1 && algo != 3 )
  412.     return BAD_ALGO;
  413.     pk.n = pkey[0];
  414.     pk.e = pkey[1];
  415.     result = g10m_new(160);
  416.     public( result, data[0], &pk );
  417.     /*rc = (*cmp)( opaquev, result );*/
  418.     rc = g10m_cmp( result, hash )? BAD_SIGN:0;
  419.     g10m_release(result);
  420.  
  421.     return rc;
  422. }
  423.  
  424.  
  425. static unsigned
  426. do_get_nbits( int algo, MPI *pkey )
  427. {
  428.     if( !is_RSA(algo) )
  429.     return 0;
  430.     return g10m_get_nbits( pkey[0] );
  431. }
  432.  
  433.  
  434. /****************
  435.  * Return some information about the algorithm.  We need algo here to
  436.  * distinguish different flavors of the algorithm.
  437.  * Returns: A pointer to string describing the algorithm or NULL if
  438.  *        the ALGO is invalid.
  439.  * Usage: Bit 0 set : allows signing
  440.  *          1 set : allows encryption
  441.  */
  442. static const char *
  443. rsa_get_info( int algo,
  444.           int *npkey, int *nskey, int *nenc, int *nsig, int *usage,
  445.     int (**r_generate)( int algo, unsigned nbits, MPI *skey, MPI **retfactors ),
  446.     int (**r_check_secret_key)( int algo, MPI *skey ),
  447.     int (**r_encrypt)( int algo, MPI *resarr, MPI data, MPI *pkey ),
  448.     int (**r_decrypt)( int algo, MPI *result, MPI *data, MPI *skey ),
  449.     int (**r_sign)( int algo, MPI *resarr, MPI data, MPI *skey ),
  450.     int (**r_verify)( int algo, MPI hash, MPI *data, MPI *pkey,
  451.                     int (*)(void *, MPI), void *),
  452.     unsigned (**r_get_nbits)( int algo, MPI *pkey ) )
  453. {
  454.     *npkey = 2;
  455.     *nskey = 6;
  456.     *nenc = 1;
  457.     *nsig = 1;
  458.     *r_generate     = do_generate         ;
  459.     *r_check_secret_key = do_check_secret_key;
  460.     *r_encrypt        = do_encrypt         ;
  461.     *r_decrypt        = do_decrypt         ;
  462.     *r_sign        = do_sign         ;
  463.     *r_verify        = do_verify         ;
  464.     *r_get_nbits    = do_get_nbits         ;
  465.  
  466.     switch( algo ) {
  467.       case 1: *usage = 2|1; return "RSA";
  468.       case 2: *usage = 2  ; return "RSA-E";
  469.       case 3: *usage =     1; return "RSA-S";
  470.       default:*usage = 0; return NULL;
  471.     }
  472. }
  473.  
  474.  
  475. static struct {
  476.     int class;
  477.     int version;
  478.     int  value;
  479.     void (*func)(void);
  480. } func_table[] = {
  481.     { 30, 1, 0, (void(*)(void))rsa_get_info },
  482.     { 31, 1, 1 }, /* RSA */
  483.     { 31, 1, 2 }, /* RSA encrypt only */
  484.     { 31, 1, 3 }, /* RSA sign only */
  485. };
  486.  
  487.  
  488.  
  489. /****************
  490.  * Enumerate the names of the functions together with informations about
  491.  * this function. Set sequence to an integer with a initial value of 0 and
  492.  * do not change it.
  493.  * If what is 0 all kind of functions are returned.
  494.  * Return values: class := class of function:
  495.  *               10 = message digest algorithm info function
  496.  *               11 = integer with available md algorithms
  497.  *               20 = cipher algorithm info function
  498.  *               21 = integer with available cipher algorithms
  499.  *               30 = public key algorithm info function
  500.  *               31 = integer with available pubkey algorithms
  501.  *          version = interface version of the function/pointer
  502.  */
  503. void *
  504. gnupgext_enum_func( int what, int *sequence, int *class, int *vers )
  505. {
  506.     void *ret;
  507.     int i = *sequence;
  508.  
  509.     do {
  510.     if( i >= DIM(func_table) || i < 0 ) {
  511.         return NULL;
  512.     }
  513.     *class = func_table[i].class;
  514.     *vers  = func_table[i].version;
  515.     switch( *class ) {
  516.       case 11:
  517.       case 21:
  518.       case 31:
  519.         ret = &func_table[i].value;
  520.         break;
  521.       default:
  522.         ret = func_table[i].func;
  523.         break;
  524.     }
  525.     i++;
  526.     } while( what && what != *class );
  527.  
  528.     *sequence = i;
  529.     return ret;
  530. }
  531.  
  532.  
  533.