home *** CD-ROM | disk | FTP | other *** search
/ linuxmafia.com 2016 / linuxmafia.com.tar / linuxmafia.com / pub / linux / security / gnupg / idea.c < prev    next >
C/C++ Source or Header  |  2000-09-05  |  15KB  |  537 lines
  1. /* idea.c  -  IDEA function
  2.  *    Copyright (c) 1997,1998,1999 by Werner Koch (dd9jn)
  3.  ************************************************************************
  4.  * ATTENTION: The used algorithm is patented and may need a license
  5.           for any use.  See below for more information.
  6.  ************************************************************************
  7.  *
  8.  * Permission is hereby granted, free of charge, to any person obtaining a
  9.  * copy of this software and associated documentation files (the "Software"),
  10.  * to deal in the Software without restriction, including without limitation
  11.  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  12.  * and/or sell copies of the Software, and to permit persons to whom the
  13.  * Software is furnished to do so, subject to the following conditions:
  14.  *
  15.  * The above copyright notice and this permission notice shall be included in
  16.  * all copies or substantial portions of the Software.
  17.  *
  18.  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  19.  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  20.  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  21.  * WERNER KOCH BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
  22.  * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  23.  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  24.  *
  25.  * Except as contained in this notice, the name of Werner Koch shall not be
  26.  * used in advertising or otherwise to promote the sale, use or other dealings
  27.  * in this Software without prior written authorization from Werner Koch.
  28.  */
  29.  
  30. /*--------------------------------------------------------------
  31.  The code herein has been taken from:
  32.    Bruce Schneier: Applied Cryptography. John Wiley & Sons, 1996.
  33.    ISBN 0-471-11709-9. .
  34.  
  35.  The IDEA algorithm is patented by Ascom Systec Ltd. of CH-5506 Maegenwil,
  36.  Switzerland, who allow it to be used on a royalty-free basis for certain
  37.  non-profit applications.  Commercial users must obtain a license from the
  38.  company in order to use IDEA.    IDEA may be used on a royalty-free basis under
  39.  the following conditions:
  40.  
  41.  Free use for private purposes:
  42.  
  43.  The free use of software containing the algorithm is strictly limited to non
  44.  revenue generating data transfer between private individuals, ie not serving
  45.  commercial purposes.  Requests by freeware developers to obtain a
  46.  royalty-free license to spread an application program containing the
  47.  algorithm for non-commercial purposes must be directed to Ascom.
  48.  
  49.  Special offer for shareware developers:
  50.  
  51.  There is a special waiver for shareware developers.  Such waiver eliminates
  52.  the upfront fees as well as royalties for the first US$10,000 gross sales of
  53.  a product containing the algorithm if and only if:
  54.  
  55.  1. The product is being sold for a minimum of US$10 and a maximum of US$50.
  56.  2. The source code for the shareware is available to the public.
  57.  
  58.  Special conditions for research projects:
  59.  
  60.  The use of the algorithm in research projects is free provided that it serves
  61.  the purpose of such project and within the project duration.  Any use of the
  62.  algorithm after the termination of a project including activities resulting
  63.  from a project and for purposes not directly related to the project requires
  64.  a license.
  65.  
  66.  Ascom Tech requires the following notice to be included for freeware
  67.  products:
  68.  
  69.  This software product contains the IDEA algorithm as described and claimed in
  70.  US patent 5,214,703, EPO patent 0482154 (covering Austria, France, Germany,
  71.  Italy, the Netherlands, Spain, Sweden, Switzerland, and the UK), and Japanese
  72.  patent application 508119/1991, "Device for the conversion of a digital block
  73.  and use of same" (hereinafter referred to as "the algorithm").  Any use of
  74.  the algorithm for commercial purposes is thus subject to a license from Ascom
  75.  Systec Ltd. of CH-5506 Maegenwil (Switzerland), being the patentee and sole
  76.  owner of all rights, including the trademark IDEA.
  77.  
  78.  Commercial purposes shall mean any revenue generating purpose including but
  79.  not limited to:
  80.  
  81.  i) Using the algorithm for company internal purposes (subject to a site
  82.     license).
  83.  
  84.  ii) Incorporating the algorithm into any software and distributing such
  85.      software and/or providing services relating thereto to others (subject to
  86.      a product license).
  87.  
  88.  iii) Using a product containing the algorithm not covered by an IDEA license
  89.       (subject to an end user license).
  90.  
  91.  All such end user license agreements are available exclusively from Ascom
  92.  Systec Ltd and may be requested via the WWW at http://www.ascom.ch/systec or
  93.  by email to idea@ascom.ch.
  94.  
  95.  Use other than for commercial purposes is strictly limited to non-revenue
  96.  generating data transfer between private individuals.    The use by government
  97.  agencies, non-profit organizations, etc is considered as use for commercial
  98.  purposes but may be subject to special conditions.  Any misuse will be
  99.  prosecuted.
  100. -------------------------------------------------------------------*/
  101.  
  102. /* How to compile:
  103.  *
  104.        gcc -Wall -O2 -shared -fPIC -o idea idea.c
  105.  */
  106.  
  107.  
  108. #include <stdio.h>
  109. #include <stdlib.h>
  110. #include <string.h>
  111. #include <assert.h>
  112.  
  113. /* configuration stuff */
  114. #ifdef __alpha__
  115.   #define SIZEOF_UNSIGNED_LONG 8
  116. #else
  117.   #define SIZEOF_UNSIGNED_LONG 4
  118. #endif
  119.  
  120. #if defined(__mc68000__) || defined (__sparc__) || defined (__PPC__) \
  121.     || (defined(__mips__) && (defined(MIPSEB) || defined (__MIPSEB__)) ) \
  122.     ||    defined(__hpux__) /* should be replaced by the Macro for the PA */
  123.   #define BIG_ENDIAN_HOST 1
  124. #else
  125.   #define LITTLE_ENDIAN_HOST 1
  126. #endif
  127.  
  128. typedef unsigned long  ulong;
  129. typedef unsigned short ushort;
  130. typedef unsigned char  byte;
  131.  
  132. typedef unsigned short u16;
  133. typedef unsigned long  u32;
  134.  
  135. /* end configurable stuff */
  136.  
  137. #ifndef DIM
  138.   #define DIM(v) (sizeof(v)/sizeof((v)[0]))
  139.   #define DIMof(type,member)   DIM(((type *)0)->member)
  140. #endif
  141.  
  142. /* imports */
  143. void g10_log_fatal( const char *fmt, ... );
  144.  
  145.  
  146. /* local stuff */
  147.  
  148. #define FNCCAST_SETKEY(f)  ((int(*)(void*, byte*, unsigned))(f))
  149. #define FNCCAST_CRYPT(f)   ((void(*)(void*, byte*, byte*))(f))
  150.  
  151. #define IDEA_KEYSIZE 16
  152. #define IDEA_BLOCKSIZE 8
  153. #define IDEA_ROUNDS 8
  154. #define IDEA_KEYLEN (6*IDEA_ROUNDS+4)
  155.  
  156. typedef struct {
  157.     u16 ek[IDEA_KEYLEN];
  158.     u16 dk[IDEA_KEYLEN];
  159.     int have_dk;
  160. } IDEA_context;
  161.  
  162.  
  163. static int do_setkey( IDEA_context *c, byte *key, unsigned keylen );
  164. static void encrypt_block( IDEA_context *bc, byte *outbuf, byte *inbuf );
  165. static void decrypt_block( IDEA_context *bc, byte *outbuf, byte *inbuf );
  166. static void selftest(int);
  167.  
  168.  
  169.  
  170. static u16
  171. mul_inv( u16 x )
  172. {
  173.     u16 t0, t1;
  174.     u16 q, y;
  175.  
  176.     if( x < 2 )
  177.     return x;
  178.     t1 = 0x10001L / x;
  179.     y =  0x10001L % x;
  180.     if( y == 1 )
  181.     return (1-t1) & 0xffff;
  182.  
  183.     t0 = 1;
  184.     do {
  185.     q = x / y;
  186.     x = x % y;
  187.     t0 += q * t1;
  188.     if( x == 1 )
  189.         return t0;
  190.     q = y / x;
  191.     y = y % x;
  192.     t1 += q * t0;
  193.     } while( y != 1 );
  194.     return (1-t1) & 0xffff;
  195. }
  196.  
  197.  
  198.  
  199. static void
  200. expand_key( byte *userkey, u16 *ek )
  201. {
  202.     int i,j;
  203.  
  204.     for(j=0; j < 8; j++ ) {
  205.     ek[j] = (*userkey << 8) + userkey[1];
  206.     userkey += 2;
  207.     }
  208.     for(i=0; j < IDEA_KEYLEN; j++ ) {
  209.     i++;
  210.     ek[i+7] = ek[i&7] << 9 | ek[(i+1)&7] >> 7;
  211.     ek += i & 8;
  212.     i &= 7;
  213.     }
  214. }
  215.  
  216.  
  217. static void
  218. invert_key( u16 *ek, u16 dk[IDEA_KEYLEN] )
  219. {
  220.     int i;
  221.     u16 t1, t2, t3;
  222.     u16 temp[IDEA_KEYLEN];
  223.     u16 *p = temp + IDEA_KEYLEN;
  224.  
  225.     t1 = mul_inv( *ek++ );
  226.     t2 = -*ek++;
  227.     t3 = -*ek++;
  228.     *--p = mul_inv( *ek++ );
  229.     *--p = t3;
  230.     *--p = t2;
  231.     *--p = t1;
  232.  
  233.     for(i=0; i < IDEA_ROUNDS-1; i++ ) {
  234.     t1 = *ek++;
  235.     *--p = *ek++;
  236.     *--p = t1;
  237.  
  238.     t1 = mul_inv( *ek++ );
  239.     t2 = -*ek++;
  240.     t3 = -*ek++;
  241.     *--p = mul_inv( *ek++ );
  242.     *--p = t3;
  243.     *--p = t2;
  244.     *--p = t1;
  245.     }
  246.     t1 = *ek++;
  247.     *--p = *ek++;
  248.     *--p = t1;
  249.  
  250.     t1 = mul_inv( *ek++ );
  251.     t2 = -*ek++;
  252.     t3 = -*ek++;
  253.     *--p = mul_inv( *ek++ );
  254.     *--p = t3;
  255.     *--p = t2;
  256.     *--p = t1;
  257.     memcpy(dk, temp, sizeof(temp) );
  258.     memset(temp, 0, sizeof(temp) );  /* burn temp */
  259. }
  260.  
  261.  
  262. static void
  263. cipher( byte *outbuf, byte *inbuf, u16 *key )
  264. {
  265.     u16 x1, x2, x3,x4, s2, s3;
  266.     u16 *in, *out;
  267.     int r = IDEA_ROUNDS;
  268.   #define MUL(x,y) \
  269.     do {u16 _t16; u32 _t32;             \
  270.         if( (_t16 = (y)) ) {            \
  271.         if( (x = (x)&0xffff) ) {        \
  272.             _t32 = (u32)x * _t16;        \
  273.             x = _t32 & 0xffff;            \
  274.             _t16 = _t32 >> 16;            \
  275.             x = ((x)-_t16) + (x<_t16?1:0);  \
  276.         }                    \
  277.         else {                    \
  278.             x = 1 - _t16;            \
  279.         }                    \
  280.         }                        \
  281.         else {                    \
  282.         x = 1 - x;                \
  283.         }                        \
  284.     } while(0)
  285.  
  286.     in = (u16*)inbuf;
  287.     x1 = *in++;
  288.     x2 = *in++;
  289.     x3 = *in++;
  290.     x4 = *in;
  291.   #ifdef LITTLE_ENDIAN_HOST
  292.     x1 = (x1>>8) | (x1<<8);
  293.     x2 = (x2>>8) | (x2<<8);
  294.     x3 = (x3>>8) | (x3<<8);
  295.     x4 = (x4>>8) | (x4<<8);
  296.   #endif
  297.     do {
  298.     MUL(x1, *key++);
  299.     x2 += *key++;
  300.     x3 += *key++;
  301.     MUL(x4, *key++ );
  302.  
  303.     s3 = x3;
  304.     x3 ^= x1;
  305.     MUL(x3, *key++);
  306.     s2 = x2;
  307.     x2 ^=x4;
  308.     x2 += x3;
  309.     MUL(x2, *key++);
  310.     x3 += x2;
  311.  
  312.     x1 ^= x2;
  313.     x4 ^= x3;
  314.  
  315.     x2 ^= s3;
  316.     x3 ^= s2;
  317.     } while( --r );
  318.     MUL(x1, *key++);
  319.     x3 += *key++;
  320.     x2 += *key++;
  321.     MUL(x4, *key);
  322.  
  323.     out = (u16*)outbuf;
  324.   #ifdef LITTLE_ENDIAN_HOST
  325.     *out++ = (x1>>8) | (x1<<8);
  326.     *out++ = (x3>>8) | (x3<<8);
  327.     *out++ = (x2>>8) | (x2<<8);
  328.     *out   = (x4>>8) | (x4<<8);
  329.   #else
  330.     *out++ = x1;
  331.     *out++ = x3;
  332.     *out++ = x2;
  333.     *out   = x4;
  334.   #endif
  335.   #undef MUL
  336. }
  337.  
  338.  
  339. static int
  340. do_setkey( IDEA_context *c, byte *key, unsigned keylen )
  341. {
  342.     static int initialized = 0;
  343.  
  344.     if( !initialized ) {
  345.     initialized = 1;
  346.     selftest(0);
  347.     }
  348.     assert(keylen == 16);
  349.     c->have_dk = 0;
  350.     expand_key( key, c->ek );
  351.     invert_key( c->ek, c->dk );
  352.     return 0;
  353. }
  354.  
  355. static void
  356. encrypt_block( IDEA_context *c, byte *outbuf, byte *inbuf )
  357. {
  358.     cipher( outbuf, inbuf, c->ek );
  359. }
  360.  
  361. static void
  362. decrypt_block( IDEA_context *c, byte *outbuf, byte *inbuf )
  363. {
  364.     static int initialized;
  365.  
  366.     if( !initialized ) {
  367.     initialized = 1;
  368.     selftest(1);
  369.     }
  370.     if( !c->have_dk ) {
  371.        c->have_dk = 1;
  372.        invert_key( c->ek, c->dk );
  373.     }
  374.     cipher( outbuf, inbuf, c->dk );
  375. }
  376.  
  377.  
  378. static void
  379. selftest( int check_decrypt )
  380. {
  381. static struct {
  382.     byte key[16];
  383.     byte plain[8];
  384.     byte cipher[8];
  385. } test_vectors[] = {
  386.     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
  387.     0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
  388.       { 0x00, 0x00, 0x00, 0x01, 0x00, 0x02, 0x00, 0x03 },
  389.       { 0x11, 0xFB, 0xED, 0x2B, 0x01, 0x98, 0x6D, 0xE5 } },
  390.     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
  391.     0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
  392.       { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },
  393.       { 0x54, 0x0E, 0x5F, 0xEA, 0x18, 0xC2, 0xF8, 0xB1 } },
  394.     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
  395.     0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
  396.       { 0x00, 0x19, 0x32, 0x4B, 0x64, 0x7D, 0x96, 0xAF },
  397.       { 0x9F, 0x0A, 0x0A, 0xB6, 0xE1, 0x0C, 0xED, 0x78 } },
  398.     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
  399.     0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
  400.       { 0xF5, 0x20, 0x2D, 0x5B, 0x9C, 0x67, 0x1B, 0x08 },
  401.       { 0xCF, 0x18, 0xFD, 0x73, 0x55, 0xE2, 0xC5, 0xC5 } },
  402.     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
  403.     0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
  404.       { 0xFA, 0xE6, 0xD2, 0xBE, 0xAA, 0x96, 0x82, 0x6E },
  405.       { 0x85, 0xDF, 0x52, 0x00, 0x56, 0x08, 0x19, 0x3D } },
  406.     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
  407.     0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
  408.       { 0x0A, 0x14, 0x1E, 0x28, 0x32, 0x3C, 0x46, 0x50 },
  409.       { 0x2F, 0x7D, 0xE7, 0x50, 0x21, 0x2F, 0xB7, 0x34 } },
  410.     { { 0x00, 0x01, 0x00, 0x02, 0x00, 0x03, 0x00, 0x04,
  411.     0x00, 0x05, 0x00, 0x06, 0x00, 0x07, 0x00, 0x08 },
  412.       { 0x05, 0x0A, 0x0F, 0x14, 0x19, 0x1E, 0x23, 0x28 },
  413.       { 0x7B, 0x73, 0x14, 0x92, 0x5D, 0xE5, 0x9C, 0x09 } },
  414.     { { 0x00, 0x05, 0x00, 0x0A, 0x00, 0x0F, 0x00, 0x14,
  415.     0x00, 0x19, 0x00, 0x1E, 0x00, 0x23, 0x00, 0x28 },
  416.       { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },
  417.       { 0x3E, 0xC0, 0x47, 0x80, 0xBE, 0xFF, 0x6E, 0x20 } },
  418.     { { 0x3A, 0x98, 0x4E, 0x20, 0x00, 0x19, 0x5D, 0xB3,
  419.     0x2E, 0xE5, 0x01, 0xC8, 0xC4, 0x7C, 0xEA, 0x60 },
  420.       { 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08 },
  421.       { 0x97, 0xBC, 0xD8, 0x20, 0x07, 0x80, 0xDA, 0x86 } },
  422.     { { 0x00, 0x64, 0x00, 0xC8, 0x01, 0x2C, 0x01, 0x90,
  423.     0x01, 0xF4, 0x02, 0x58, 0x02, 0xBC, 0x03, 0x20 },
  424.       { 0x05, 0x32, 0x0A, 0x64, 0x14, 0xC8, 0x19, 0xFA },
  425.       { 0x65, 0xBE, 0x87, 0xE7, 0xA2, 0x53, 0x8A, 0xED } },
  426.     { { 0x9D, 0x40, 0x75, 0xC1, 0x03, 0xBC, 0x32, 0x2A,
  427.     0xFB, 0x03, 0xE7, 0xBE, 0x6A, 0xB3, 0x00, 0x06 },
  428.       { 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08 },
  429.       { 0xF5, 0xDB, 0x1A, 0xC4, 0x5E, 0x5E, 0xF9, 0xF9 } }
  430. };
  431.     IDEA_context c;
  432.     byte buffer[8];
  433.     int i;
  434.  
  435.     for(i=0; i < DIM(test_vectors); i++ ) {
  436.     do_setkey( &c, test_vectors[i].key, 16 );
  437.     if( !check_decrypt ) {
  438.         encrypt_block( &c, buffer, test_vectors[i].plain );
  439.         if( memcmp( buffer, test_vectors[i].cipher, 8 ) )
  440.         g10_log_fatal("idea encryption (%d) failed\n", i);
  441.     }
  442.     else {
  443.         decrypt_block( &c, buffer, test_vectors[i].cipher );
  444.         if( memcmp( buffer, test_vectors[i].plain, 8 ) )
  445.         g10_log_fatal("idea decryption (%d) failed\n", i);
  446.     }
  447.     }
  448. }
  449.  
  450.  
  451. /****************
  452.  * Return some information about the algorithm.  We need algo here to
  453.  * distinguish different flavors of the algorithm.
  454.  * Returns: A pointer to string describing the algorithm or NULL if
  455.  *        the ALGO is invalid.
  456.  */
  457. const char *
  458. idea_get_info( int algo, size_t *keylen,
  459.            size_t *blocksize, size_t *contextsize,
  460.            int    (**r_setkey)( void *c, byte *key, unsigned keylen ),
  461.            void (**r_encrypt)( void *c, byte *outbuf, byte *inbuf ),
  462.            void (**r_decrypt)( void *c, byte *outbuf, byte *inbuf )
  463.          )
  464. {
  465.     *keylen = 128;
  466.     *blocksize = 8;
  467.     *contextsize = sizeof(IDEA_context);
  468.     *r_setkey = FNCCAST_SETKEY(do_setkey);
  469.     *r_encrypt= FNCCAST_CRYPT(encrypt_block);
  470.     *r_decrypt= FNCCAST_CRYPT(decrypt_block);
  471.     if( algo == 1 )
  472.     return "IDEA";
  473.     return NULL;
  474. }
  475.  
  476.  
  477.  
  478. const char * const gnupgext_version = "IDEA ($Revision: 1.11 $)";
  479.  
  480. static struct {
  481.     int class;
  482.     int version;
  483.     int  value;
  484.     void (*func)(void);
  485. } func_table[] = {
  486.     { 20, 1, 0, (void(*)(void))idea_get_info },
  487.     { 21, 1, 1 },
  488. };
  489.  
  490.  
  491.  
  492. /****************
  493.  * Enumerate the names of the functions together with informations about
  494.  * this function. Set sequence to an integer with a initial value of 0 and
  495.  * do not change it.
  496.  * If what is 0 all kind of functions are returned.
  497.  * Return values: class := class of function:
  498.  *               10 = message digest algorithm info function
  499.  *               11 = integer with available md algorithms
  500.  *               20 = cipher algorithm info function
  501.  *               21 = integer with available cipher algorithms
  502.  *               30 = public key algorithm info function
  503.  *               31 = integer with available pubkey algorithms
  504.  *          version = interface version of the function/pointer
  505.  *                (currently this is 1 for all functions)
  506.  */
  507. void *
  508. gnupgext_enum_func( int what, int *sequence, int *class, int *vers )
  509. {
  510.     void *ret;
  511.     int i = *sequence;
  512.  
  513.     do {
  514.     if( i >= DIM(func_table) || i < 0 ) {
  515.         return NULL;
  516.     }
  517.     *class = func_table[i].class;
  518.     *vers  = func_table[i].version;
  519.     switch( *class ) {
  520.       case 11:
  521.       case 21:
  522.       case 31:
  523.         ret = &func_table[i].value;
  524.         break;
  525.       default:
  526.         ret = func_table[i].func;
  527.         break;
  528.     }
  529.     i++;
  530.     } while( what && what != *class );
  531.  
  532.     *sequence = i;
  533.     return ret;
  534. }
  535.  
  536.  
  537.