home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / crypl200.zip / LIB_DSA.C < prev    next >
Text File  |  1996-10-06  |  14KB  |  396 lines
  1. /****************************************************************************
  2. *                                                                            *
  3. *                        cryptlib DSA Encryption Routines                    *
  4. *                        Copyright Peter Gutmann 1995-1996                    *
  5. *                                                                            *
  6. ****************************************************************************/
  7.  
  8. #include <stdlib.h>
  9. #include <string.h>
  10. #include "crypt.h"
  11.  
  12. /****************************************************************************
  13. *                                                                            *
  14. *                            DSA Self-test Routines                            *
  15. *                                                                            *
  16. ****************************************************************************/
  17.  
  18. /* Test the DSA implementation using the sample key from FIPS 186.  Because a
  19.    lot of the high-level encryption routines don't exist yet, we cheat a bit
  20.    and set up a dummy encryption context with just enough information for the
  21.    following code to work */
  22.  
  23. typedef struct {
  24.     int pLen; BYTE p[ 64 ];
  25.     int qLen; BYTE q[ 20 ];
  26.     int gLen; BYTE g[ 64 ];
  27.     int xLen; BYTE x[ 20 ];
  28.     int yLen; BYTE y[ 64 ];
  29.     } DSA_PRIVKEY;
  30.  
  31. static DSA_PRIVKEY dsaTestKey = {
  32.     /* p */
  33.     512,
  34.     { 0x8D, 0xF2, 0xA4, 0x94, 0x49, 0x22, 0x76, 0xAA,
  35.       0x3D, 0x25, 0x75, 0x9B, 0xB0, 0x68, 0x69, 0xCB,
  36.       0xEA, 0xC0, 0xD8, 0x3A, 0xFB, 0x8D, 0x0C, 0xF7,
  37.       0xCB, 0xB8, 0x32, 0x4F, 0x0D, 0x78, 0x82, 0xE5,
  38.       0xD0, 0x76, 0x2F, 0xC5, 0xB7, 0x21, 0x0E, 0xAF,
  39.       0xC2, 0xE9, 0xAD, 0xAC, 0x32, 0xAB, 0x7A, 0xAC,
  40.       0x49, 0x69, 0x3D, 0xFB, 0xF8, 0x37, 0x24, 0xC2,
  41.       0xEC, 0x07, 0x36, 0xEE, 0x31, 0xC8, 0x02, 0x91 },
  42.     /* q */
  43.     160,
  44.     { 0xC7, 0x73, 0x21, 0x8C, 0x73, 0x7E, 0xC8, 0xEE,
  45.       0x99, 0x3B, 0x4F, 0x2D, 0xED, 0x30, 0xF4, 0x8E,
  46.       0xDA, 0xCE, 0x91, 0x5F },
  47.     /* g */
  48.     512,
  49.     { 0x62, 0x6D, 0x02, 0x78, 0x39, 0xEA, 0x0A, 0x13,
  50.       0x41, 0x31, 0x63, 0xA5, 0x5B, 0x4C, 0xB5, 0x00,
  51.       0x29, 0x9D, 0x55, 0x22, 0x95, 0x6C, 0xEF, 0xCB,
  52.       0x3B, 0xFF, 0x10, 0xF3, 0x99, 0xCE, 0x2C, 0x2E,
  53.       0x71, 0xCB, 0x9D, 0xE5, 0xFA, 0x24, 0xBA, 0xBF,
  54.       0x58, 0xE5, 0xB7, 0x95, 0x21, 0x92, 0x5C, 0x9C,
  55.       0xC4, 0x2E, 0x9F, 0x6F, 0x46, 0x4B, 0x08, 0x8C,
  56.       0xC5, 0x72, 0xAF, 0x53, 0xE6, 0xD7, 0x88, 0x02 },
  57.     /* x */
  58.     160,
  59.     { 0x20, 0x70, 0xB3, 0x22, 0x3D, 0xBA, 0x37, 0x2F,
  60.       0xDE, 0x1C, 0x0F, 0xFC, 0x7B, 0x2E, 0x3B, 0x49,
  61.       0x8B, 0x26, 0x06, 0x14 },
  62.     /* y */
  63.     512,
  64.     { 0x19, 0x13, 0x18, 0x71, 0xD7, 0x5B, 0x16, 0x12,
  65.       0xA8, 0x19, 0xF2, 0x9D, 0x78, 0xD1, 0xB0, 0xD7,
  66.       0x34, 0x6F, 0x7A, 0xA7, 0x7B, 0xB6, 0x2A, 0x85,
  67.       0x9B, 0xFD, 0x6C, 0x56, 0x75, 0xDA, 0x9D, 0x21,
  68.       0x2D, 0x3A, 0x36, 0xEF, 0x16, 0x72, 0xEF, 0x66,
  69.       0x0B, 0x8C, 0x7C, 0x25, 0x5C, 0xC0, 0xEC, 0x74,
  70.       0x85, 0x8F, 0xBA, 0x33, 0xF4, 0x4C, 0x06, 0x69,
  71.       0x96, 0x30, 0xA7, 0x6B, 0x03, 0x0E, 0xE3, 0x33 }
  72.     };
  73.  
  74. #if 0
  75. k =    0x35, 0x8D, 0xAD, 0x57, 0x14, 0x62, 0x71, 0x0F,
  76.     0x50, 0xE2, 0x54, 0xCF, 0x1A, 0x37, 0x6B, 0x2B,
  77.     0xDE, 0xAA, 0xDF, 0xBF
  78.  
  79. kinv =
  80.     0x0D, 0x51, 0x67, 0x29, 0x82, 0x02, 0xE4, 0x9B,
  81.     0x41, 0x16, 0xAC, 0x10, 0x4F, 0xC3, 0xF4, 0x15,
  82.     0xAE, 0x52, 0xF9, 0x17
  83.  
  84. SHA(M) =
  85.     0xA9, 0x99, 0x3E, 0x36, 0x47, 0x06, 0x81, 0x6A,
  86.     0xBA, 0x3E, 0x25, 0x71, 0x78, 0x50, 0xC2, 0x6C,
  87.     0x9C, 0xD0, 0xD8, 0x9D
  88.  
  89. r =    0x8B, 0xAC, 0x1A, 0xB6, 0x64, 0x10, 0x43, 0x5C,
  90.     0xB7, 0x18, 0x1F, 0x95, 0xB1, 0x6A, 0xB9, 0x7C,
  91.     0x92, 0xB3, 0x41, 0xC0
  92.  
  93. s =    0x41, 0xE2, 0x34, 0x5F, 0x1F, 0x56, 0xDF, 0x24,
  94.     0x58, 0xF4, 0x26, 0xD1, 0x55, 0xB4, 0xBA, 0x2D,
  95.     0xB6, 0xDC, 0xD8, 0xC8
  96.  
  97. w =    0x9D, 0xF4, 0xEC, 0xE5, 0x82, 0x6B, 0xE9, 0x5F,
  98.     0xED, 0x40, 0x6D, 0x41, 0xB4, 0x3E, 0xDC, 0x0B,
  99.     0x1C, 0x18, 0x84, 0x1B
  100.  
  101. u1 =
  102.     0xBF, 0x65, 0x5B, 0xD0, 0x46, 0xF0, 0xB3, 0x5E,
  103.     0xC7, 0x91, 0xB0, 0x04, 0x80, 0x4A, 0xFC, 0xBB,
  104.     0x8E, 0xF7, 0xD6, 0x9D
  105.  
  106. u2 =
  107.     0x82, 0x1A, 0x92, 0x63, 0x12, 0xE9, 0x7A, 0xDE,
  108.     0xAB, 0xCC, 0x8D, 0x08, 0x2B, 0x52, 0x78, 0x97,
  109.     0x8A, 0x2D, 0xF4, 0xB0
  110.  
  111. gu1 moD p =
  112.     0x51, 0xB1, 0xBF, 0x86, 0x78, 0x88, 0xE5, 0xF3,
  113.     0xAF, 0x6F, 0xB4, 0x76, 0x9D, 0xD0, 0x16, 0xBC,
  114.     0xFE, 0x66, 0x7A, 0x65, 0xAA, 0xFC, 0x27, 0x53,
  115.     0x90, 0x63, 0xBD, 0x3D, 0x2B, 0x13, 0x8B, 0x4C,
  116.     0xE0, 0x2C, 0xC0, 0xC0, 0x2E, 0xC6, 0x2B, 0xB6,
  117.     0x73, 0x06, 0xC6, 0x3E, 0x4D, 0xB9, 0x5B, 0xBF,
  118.     0x6F, 0x96, 0x66, 0x2A, 0x19, 0x87, 0xA2, 0x1B,
  119.     0xE4, 0xEC, 0x10, 0x71, 0x01, 0x0B, 0x60, 0x69
  120.  
  121. yu2 moD p =
  122.     0x8B, 0x51, 0x00, 0x71, 0x29, 0x57, 0xE9, 0x50,
  123.     0x50, 0xD6, 0xB8, 0xFD, 0x37, 0x6A, 0x66, 0x8E,
  124.     0x4B, 0x0D, 0x63, 0x3C, 0x1E, 0x46, 0xE6, 0x65,
  125.     0x5C, 0x61, 0x1A, 0x72, 0xE2, 0xB2, 0x84, 0x83,
  126.     0xBE, 0x52, 0xC7, 0x4D, 0x4B, 0x30, 0xDE, 0x61,
  127.     0xA6, 0x68, 0x96, 0x6E, 0xDC, 0x30, 0x7A, 0x67,
  128.     0xC1, 0x94, 0x41, 0xF4, 0x22, 0xBF, 0x3C, 0x34,
  129.     0x08, 0xAE, 0xBA, 0x1F, 0x0A, 0x4D, 0xBE, 0xC7
  130.  
  131. v =    0x8B, 0xAC, 0x1A, 0xB6, 0x64, 0x10, 0x43, 0x5C,
  132.     0xB7, 0x18, 0x1F, 0x95, 0xB1, 0x6A, 0xB9, 0x7C,
  133.     0x92, 0xB3, 0x41, 0xC0
  134. #endif
  135.  
  136. int dsaInitKey( CRYPT_INFO *cryptInfo );
  137. int dsaEncrypt( CRYPT_INFO *cryptInfo, BYTE *buffer, int noBytes );
  138. int dsaDecrypt( CRYPT_INFO *cryptInfo, BYTE *buffer, int noBytes );
  139.  
  140. int dsaSelfTest( void )
  141.     {
  142.     CRYPT_INFO cryptInfo;
  143.     CRYPT_PKCINFO_DSA *dsaKey;
  144.     CAPABILITY_INFO capabilityInfo = { CRYPT_ALGO_DSA, CRYPT_MODE_PKC, 0,
  145.                                        NULL, NULL, CRYPT_ERROR, 64, 128, 512,
  146.                                        0, 0, 0, NULL, NULL, NULL, NULL, NULL,
  147.                                        NULL, NULL, NULL, NULL, NULL,
  148.                                        CRYPT_ERROR, NULL };
  149.     BYTE buffer[ 64 ];
  150.     int status;
  151.  
  152.     /* Allocate room for the public-key components */
  153.     if( ( dsaKey = ( CRYPT_PKCINFO_DSA * ) malloc( sizeof( CRYPT_PKCINFO_DSA ) ) ) == NULL )
  154.         return( CRYPT_NOMEM );
  155.  
  156.     /* Initialise the BigNum information and components */
  157.     memset( &cryptInfo, 0, sizeof( CRYPT_INFO ) );
  158.     bnBegin( &cryptInfo.pkcParam1 );
  159.     bnBegin( &cryptInfo.pkcParam2 );
  160.     bnBegin( &cryptInfo.pkcParam3 );
  161.     bnBegin( &cryptInfo.pkcParam4 );
  162.     bnBegin( &cryptInfo.pkcParam5 );
  163.     bnBegin( &cryptInfo.pkcParam6 );
  164.     bnBegin( &cryptInfo.pkcParam7 );
  165.     bnBegin( &cryptInfo.pkcParam8 );
  166.     cryptInfo.keyComponentsLittleEndian = FALSE;
  167.     cryptInitComponents( dsaKey, CRYPT_COMPONENTS_BIGENDIAN,
  168.                          CRYPT_KEYTYPE_PRIVATE );
  169.     cryptSetComponent( dsaKey->p, dsaTestKey.p, dsaTestKey.pLen );
  170.     cryptSetComponent( dsaKey->q, dsaTestKey.q, dsaTestKey.qLen );
  171.     cryptSetComponent( dsaKey->g, dsaTestKey.g, dsaTestKey.gLen );
  172.     cryptSetComponent( dsaKey->x, dsaTestKey.x, dsaTestKey.xLen );
  173.     cryptSetComponent( dsaKey->y, dsaTestKey.y, dsaTestKey.yLen );
  174.     cryptInfo.keyComponentPtr = dsaKey;
  175.     cryptInfo.capabilityInfo = &capabilityInfo;
  176.  
  177.     /* Perform the test en/decryption of a block of data */
  178.     memset( buffer, 0, 64 );
  179.     memcpy( buffer, "abcde", 5 );
  180.     dsaInitKey( &cryptInfo );
  181. #if 0    /* Make sure noone uses us for now */
  182.     if( ( status = dsaEncrypt( &cryptInfo, buffer, CRYPT_USE_DEFAULT ) ) == CRYPT_OK )
  183.         status = dsaDecrypt( &cryptInfo, buffer, CRYPT_USE_DEFAULT );
  184.     if( status != CRYPT_OK || memcmp( buffer, "abcde", 5 ) )
  185. #endif /* 0 */
  186.         status = CRYPT_SELFTEST;
  187.  
  188.     /* Clean up */
  189.     cryptDestroyComponents( dsaKey );
  190.     bnEnd( &cryptInfo.pkcParam1 );
  191.     bnEnd( &cryptInfo.pkcParam2 );
  192.     bnEnd( &cryptInfo.pkcParam3 );
  193.     bnEnd( &cryptInfo.pkcParam4 );
  194.     bnEnd( &cryptInfo.pkcParam5 );
  195.     bnEnd( &cryptInfo.pkcParam6 );
  196.     bnEnd( &cryptInfo.pkcParam7 );
  197.     bnEnd( &cryptInfo.pkcParam8 );
  198.     zeroise( &cryptInfo, sizeof( CRYPT_INFO ) );
  199.     free( dsaKey );
  200.  
  201.     return( status );
  202.     }
  203.  
  204. /****************************************************************************
  205. *                                                                            *
  206. *                            Init/Shutdown Routines                            *
  207. *                                                                            *
  208. ****************************************************************************/
  209.  
  210. /* Not needed for the DSA routines */
  211.  
  212. /****************************************************************************
  213. *                                                                            *
  214. *                            DSA En/Decryption Routines                        *
  215. *                                                                            *
  216. ****************************************************************************/
  217.  
  218. /* Encrypt (sign) a single block of data  */
  219.  
  220. int dsaEncrypt( CRYPT_INFO *cryptInfo, BYTE *buffer, int noBytes )
  221.     {
  222.     BIGNUM *p = &cryptInfo->dsaParam_p, *q = &cryptInfo->dsaParam_q;
  223.     BIGNUM *g = &cryptInfo->dsaParam_g, *x = &cryptInfo->dsaParam_x;
  224.     BIGNUM hash, k, r, s, temp;
  225.     BYTE kBuffer[ CRYPT_MAX_PKCSIZE ];
  226.     int length = bitsToBytes( cryptInfo->keySizeBits ), i, status = CRYPT_OK;
  227.  
  228.     /* The length of the encrypted data is determined by the PKC key size */
  229.     UNUSED( noBytes );
  230.  
  231.     /* Initialise the bignums */
  232.     bnBegin( &hash );
  233.     bnBegin( &k );
  234.     bnBegin( &r );
  235.     bnBegin( &s );
  236.     bnBegin( &temp );
  237.  
  238.     /* Generate the secret random value k */
  239.     for( i = 0; i < length; i++ )
  240.         kBuffer[ i ] = getRandomByte();
  241.     kBuffer[ 0 ] |= 0x80;    /* Make the random value as big as possible */
  242.     bnInsertBigBytes( &k, kBuffer, 0, length );
  243.     bnMod( &k, &k, q );        /* Reduce k to the correct range */
  244.     zeroise( kBuffer, length );
  245.  
  246.     /* Move the data from the buffer into a bignum */
  247.     bnInsertBigBytes( &hash, buffer, 0, length );
  248.  
  249.     /* r = ( g ^ k mod p ) mod q */
  250.     CK( bnExpMod( &r, g, &k, p ) );
  251.     CK( bnMod( &r, &r, q ) );
  252.  
  253.     /* s = k^-1 * ( hash + x * r ) mod q */
  254.     CK( bnInv( &temp, &k, q ) );        /* temp = k^-1 */
  255.     CK( bnMul( &s, x, &r ) );            /* s = x * r */
  256.     CK( bnMod( &s, &s, q ) );            /* s = s mod q */
  257.     CK( bnAdd( &s, &hash ) );            /* s = s + hash */
  258.     if( bnCmp( &s, q ) > 0 )            /* if s > q */
  259.         CK( bnSub( &s, q ) );            /*     s = s - q */
  260.     CK( bnMul( &s, &s, &temp ) );        /* s = s * k^-1 */
  261.     CK( bnMod( &s, &s, q ) );            /* s = s mod q */
  262.  
  263.     /* Copy the result to the output buffer and destroy sensitive data */
  264.     bnExtractBigBytes( &r, buffer, 0, length );
  265.     bnBegin( &temp );
  266.     bnBegin( &s );
  267.     bnBegin( &r );
  268.     bnBegin( &k );
  269.     bnBegin( &hash );
  270.  
  271.     return( ( status == -1 ) ? CRYPT_PKCCRYPT : CRYPT_OK );
  272.     }
  273.  
  274. /* Decryption (signature check) a single block of data */
  275.  
  276. int dsaDecrypt( CRYPT_INFO *cryptInfo, BYTE *buffer, int noBytes )
  277.     {
  278.     BIGNUM *p = &cryptInfo->dsaParam_p, *q = &cryptInfo->dsaParam_q;
  279.     BIGNUM *g = &cryptInfo->dsaParam_g, *y = &cryptInfo->dsaParam_y;
  280.     BIGNUM r, s, w, u1, u2;
  281.     int length = bitsToBytes( cryptInfo->keySizeBits ), status = 0;
  282.  
  283.     /* The length of the encrypted data is determined by the PKC key size */
  284.     UNUSED( noBytes );
  285.  
  286.     /* Initialise the bignums */
  287.     bnBegin( &r );
  288.     bnBegin( &s );
  289.     bnBegin( &w );
  290.     bnBegin( &u1 );
  291.     bnBegin( &u2 );
  292.     bnInsertBigBytes( &r, buffer, 0, length );
  293.  
  294.     /* w = s^-1 mod q */
  295.     CK( bnInv( &w, &s, q ) );
  296.  
  297.     /* u1 = ( hash * w ) mod q
  298.     CK( bnMul( &u1, hash, &w ) );
  299.     CK( bnMod(&u1, &u1, q ) );
  300.  
  301.     /* u2 = ( r * w ) mod q */
  302.     CK( bnMul( &u2, &r, &w ) );
  303.     CK( bnMod( &u2, &u2, q ) );
  304.  
  305.     /* v = ( ( ( g^u1 ) * ( y^u2 ) ) mod p ) mod q */
  306.     CK( bnDoubleExpMod( &w, g, &u1, y, &u2, p ) );
  307.     CK( bnMod( &w, &w, q ) );
  308.  
  309.     /* if( !bnCmp( r, &w ) ) => sig = OK */
  310.  
  311.     /* Copy the result to the output buffer and destroy sensitive data */
  312.     bnExtractBigBytes( &w, buffer, 0, length );
  313.     bnBegin( &u2 );
  314.     bnBegin( &u1 );
  315.     bnBegin( &w );
  316.     bnBegin( &s );
  317.     bnBegin( &r );
  318.  
  319.     return( ( status == -1 ) ? CRYPT_PKCCRYPT : CRYPT_OK );
  320.     }
  321.  
  322. /****************************************************************************
  323. *                                                                            *
  324. *                            DSA Key Management Routines                        *
  325. *                                                                            *
  326. ****************************************************************************/
  327.  
  328. /* Load DSA public/private key components into an encryption context */
  329.  
  330. int dsaInitKey( CRYPT_INFO *cryptInfo )
  331.     {
  332.     CRYPT_PKCINFO_DSA *dsaKey = ( CRYPT_PKCINFO_DSA * ) cryptInfo->keyComponentPtr;
  333.     int status = CRYPT_OK;
  334.  
  335.     /* Allocate storage for the external-format key components */
  336.     if( ( status = secureMalloc( &cryptInfo->pkcInfo,
  337.                                  sizeof( CRYPT_PKCINFO_DSA ) ) ) != CRYPT_OK )
  338.         return( status );
  339.  
  340.     /* Load the key component from the external representation into the
  341.        internal BigNums */
  342.     cryptInfo->keyComponentsLittleEndian = dsaKey->endianness;
  343.     cryptInfo->isPublicKey = dsaKey->isPublicKey;
  344.     if( cryptInfo->keyComponentsLittleEndian )
  345.         {
  346.         bnInsertLittleBytes( &cryptInfo->dsaParam_p, dsaKey->p, 0,
  347.                              bitsToBytes( dsaKey->pLen ) );
  348.         bnInsertLittleBytes( &cryptInfo->dsaParam_q, dsaKey->q, 0,
  349.                              bitsToBytes( dsaKey->qLen ) );
  350.         bnInsertLittleBytes( &cryptInfo->dsaParam_g, dsaKey->g, 0,
  351.                              bitsToBytes( dsaKey->gLen ) );
  352.         bnInsertLittleBytes( &cryptInfo->dsaParam_x, dsaKey->x, 0,
  353.                              bitsToBytes( dsaKey->xLen ) );
  354.         if( !dsaKey->isPublicKey )
  355.             bnInsertLittleBytes( &cryptInfo->dsaParam_y, dsaKey->y, 0,
  356.                                  bitsToBytes( dsaKey->yLen ) );
  357.         }
  358.     else
  359.         {
  360.         bnInsertBigBytes( &cryptInfo->dsaParam_p, dsaKey->p, 0,
  361.                           bitsToBytes( dsaKey->pLen ) );
  362.         bnInsertBigBytes( &cryptInfo->dsaParam_q, dsaKey->q, 0,
  363.                           bitsToBytes( dsaKey->qLen ) );
  364.         bnInsertBigBytes( &cryptInfo->dsaParam_g, dsaKey->g, 0,
  365.                           bitsToBytes( dsaKey->gLen ) );
  366.         bnInsertBigBytes( &cryptInfo->dsaParam_x, dsaKey->x, 0,
  367.                           bitsToBytes( dsaKey->xLen ) );
  368.         if( !dsaKey->isPublicKey )
  369.             bnInsertBigBytes( &cryptInfo->dsaParam_y, dsaKey->y, 0,
  370.                               bitsToBytes( dsaKey->yLen ) );
  371.         }
  372.  
  373.     /* Load the key components into the external-format component storage */
  374.     memcpy( cryptInfo->pkcInfo, dsaKey, sizeof( CRYPT_PKCINFO_DSA ) );
  375.  
  376.     /* Make sure the necessary key parameters have been initialised */
  377.     if( !bnCmpQ( &cryptInfo->dsaParam_p, 0 ) || \
  378.         !bnCmpQ( &cryptInfo->dsaParam_q, 0 ) || \
  379.         !bnCmpQ( &cryptInfo->dsaParam_g, 0 ) || \
  380.         !bnCmpQ( &cryptInfo->dsaParam_x, 0 ) )
  381.         status = CRYPT_BADPARM2;
  382.     if( !dsaKey->isPublicKey )
  383.         if( !bnCmpQ( &cryptInfo->dsaParam_y, 0 ) )
  384.         status = CRYPT_BADPARM2;
  385.  
  386.     /* Set the nominal keysize in bits */
  387.     cryptInfo->keySizeBits = dsaKey->pLen;
  388.  
  389.     /* Finally, generate a key ID for this key */
  390.     if( cryptStatusOK( status ) )
  391.         status = generateKeyID( CRYPT_ALGO_DSA, cryptInfo->keyID, \
  392.                                 &cryptInfo->keyIDlength, dsaKey );
  393.  
  394.     return( status );
  395.     }
  396.