rfc2777.txt

RFC 的详细文档！

         2. Mary         12. Pendragon       22. Sloth
         3. Bashful      13. Pandora         23. Envy
         4. Dopey        14. Faith           24. Anger
         5. Sleepy       15. Hope            25. Kasczynski
         6. Grouchy      16. Charity
         7. Doc          17. Love
         8. Sneazy       18. Longsuffering
         9. Handsome     19. Chastity
        10. Cassandra    20. Smith

   Assume the following (fake example) ordered list of randomness
   sources:

    1. The People's Democracy of Betastani State Lottery six winning
       numbers (ignoring the seventh "extra" number) for 1 October 1998.
    2. Numbers of the winning horses at Hialeia for all races for the
       first day on or after x September 1998 on which at least two
       races are run.
    3. The Republic of Alphaland State Lottery daily number for 1
       October 1998 treated as a single four digit integer.
    4. Closing price of Example Corporation stock on the Lunar Stock
       Exchange for the first business day after x September 1998 when
       it trades.

   Randomness publicly produced:

       Source 1:  9, 18, 26, 34, 41, 45
       Source 2:  2, 5, 12, 8, 10
       Source 3:  9319
       Source 4:  13 11/16

   Resulting key string:

       9.18.26.34.41.45./2.5.8.10.12./9319./13.6875/



Eastlake                     Informational                      [Page 6]

RFC 2777              Verifiable Random Selection          February 2000


   The table below gives the hex of the MD5 of the above key string
   bracketed with a byte whose value is successively 0x00, 0x01, 0x02,
   through 0x09.  The divisor for the number size of the remaining pool
   at each stage is given and the index of the selectee as per the
   original number of those in the pool.

   index        hex value of MD5        div  selected
    1  746612D0A75D2A2A39C0A957CF825F8D  25  -> 12 <-
    2  95E31A4429ED5AAF7377A15A8E10CD9D  24  ->  6 <-
    3  AFB2B3FD30E82AD6DC35B4D2F1CFC77A  23  ->  8 <-
    4  06821016C2A2EA14A6452F4A769ED1CC  22  ->  3 <-
    5  94DA30E11CA7F9D05C66D0FD3C75D6F7  21  ->  2 <-
    6  2FAE3964D5B1DEDD33FDA80F4B8EF45E  20  -> 24 <-
    7  F1E7AB6753A773EFE46393515FDA8AF8  19  -> 11 <-
    8  700B81738E07DECB4470879BEC6E0286  18  -> 19 <-
    9  1F23F8F8F8E5638A29D332BC418E0689  17  -> 15 <-
   10  61A789BA86BF412B550A5A05E821E0ED  16  -> 22 <-

   Resulting selection, in order selected:

         1. Pendragon (12)     6. Anger (24)
         2. Grouchy (6)        7. Pollyanna (11)
         3. Sneazy (8)         8. Chastity (19)
         4. Bashful (3)        9. Hope (15)
         5. Mary (2)          10. Sloth (22)

6. Security Considerations

   Careful choice of should be made of randomness inputs so that there
   is no reasonable suspicion that they are under the control of the
   administrator.  Guidelines given above to use a small number of
   inputs with a substantial amount of entropy from the last shoud be
   followed.  And equal care needs to be given that the algorithm
   selected is faithfully executed with the designated inputs values.
   Publication of the results and a week or so window for the community
   of interest to duplicate the calculations should give a reasonable
   assurance against implementation tampering.

   To maintain the unpredictable character of selections, should a
   member of the nomcom need to be replaced due to death, resignation,
   expulsion, etc., new publicly announced future random sources should
   be used for the selection of their replacement.









Eastlake                     Informational                      [Page 7]

RFC 2777              Verifiable Random Selection          February 2000


7.  Reference Code

   This code makes use of the MD5 reference code from [RFC 1321] ("RSA
   Data Security, Inc. MD5 Message-Digest Algorithm").  The portion of
   the code dealing with multiple floating point numbers was written by
   Matt Crawford.

   /****************************************************************
    *
    *  Reference code for
    *      "Publicly Verifiable Nomcom Random Selection"
    *          Donald E. Eastlake 3rd
    *
    ****************************************************************/
   #include <limits.h>
   #include <math.h>
   #include <stdio.h>
   #include <stdlib.h>
   #include <string.h>

   #include "global.h"
   #include "MD5.h"

   /* local prototypes */
   int longremainder ( unsigned char divisor,
                       unsigned char dividend[16] );
   int getinteger ( char *string );
   double NPentropy ( int N, int P );


   /* limited to 16 inputs of up to sixteen integers each */
   /****************************************************************/

   main ()
   {
   int         i, j,  k, k2, err, keysize, pool, selection;
   unsigned char   unch, uc16[16], remaining, *selected;
   long int    temp, array[16];
   MD5_CTX ctx;
   char        buffer[257], key [800], sarray[16][256];

   pool = getinteger ( "Type size of pool:\n" );
   if ( pool > 255 )

       {
       printf ( "Pool too big.\n" );
       exit ( 1 );
       }



Eastlake                     Informational                      [Page 8]

RFC 2777              Verifiable Random Selection          February 2000


   selected = (unsigned char *) malloc ( pool );
   if ( !selected )
       {
       printf ( "Out of memory.\n" );
       exit ( 1 );
       }
   selection = getinteger ( "Type number of items to be selected:\n" );
   if ( selection > pool )
       {
       printf ( "Pool too small.\n" );
       exit ( 1 );
       }
   if ( selection == pool )
       {
       printf ( "All of the pool is selected.\n" );
       exit ( 0 );
       }
   err = printf ( "Approximately %.1f bits of entropy needed.\n",
                  NPentropy ( selection, pool ) + 0.1 );
   if ( err <= 0 ) exit ( 1 );
   for ( i = 0, keysize = 0; i < 16; ++i )
       {
       if ( keysize > 500 )
           {
           printf ( "Too much input.\n" );
           exit ( 1 );
           }
       /* get the "random" inputs. echo back to user so the user may
          be able to tell if truncation or other glitches occur.  */
       err = printf (
           "\nType #%d randomness or 'end' followed by new line.\n"
           "Up to 16 integers or the word 'float' followed by up\n"
           "to 16 x.y format reals.\n", i+1 );
       if ( err <= 0 ) exit ( 1 );
       gets ( buffer );
       j = sscanf ( buffer,
               "%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld%ld",
           &array[0], &array[1], &array[2], &array[3],
           &array[4], &array[5], &array[6], &array[7],
           &array[8], &array[9], &array[10], &array[11],
           &array[12], &array[13], &array[14], &array[15] );
       if ( j == EOF )
           exit ( j );
       if ( !j )
           if ( buffer[0] == 'e' )
               break;

           else



Eastlake                     Informational                      [Page 9]

RFC 2777              Verifiable Random Selection          February 2000


               {   /* floating point code by Matt Crawford */
               j = sscanf ( buffer,
                   "float %ld.%[0-9]%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]"
                   "%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]"
                   "%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]"
                   "%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]%ld.%[0-9]",
                   &array[0], sarray[0], &array[1], sarray[1],
                   &array[2], sarray[2], &array[3], sarray[3],
                   &array[4], sarray[4], &array[5], sarray[5],
                   &array[6], sarray[6], &array[7], sarray[7],
                   &array[8], sarray[8], &array[9], sarray[9],
                   &array[10], sarray[10], &array[11], sarray[11],
                   &array[12], sarray[12], &array[13], sarray[13],
                   &array[14], sarray[14], &array[15], sarray[15] );
               if ( j == 0 || j & 1 )
                   printf ( "Bad format." );
               else {
                    for ( k = 0, j /= 2; k < j; k++ )
                    {
                          /* strip trailing zeros */
                    for ( k2=strlen(sarray[k]); sarray[k][--k2]=='0';)
                          sarray[k][k2] = '\0';
                    err = printf ( "%ld.%s\n", array[k], sarray[k] );
                    if ( err <= 0 ) exit ( 1 );
                    keysize += sprintf ( &key[keysize], "%ld.%s",
                                         array[k], sarray[k] );
                    }
                    keysize += sprintf ( &key[keysize], "/" );
                    }
               }
       else
           {   /* sort values, not a very efficient algorithm */
           for ( k2 = 0; k2 < j - 1; ++k2 )
               for ( k = 0; k < j - 1; ++k )
                   if ( array[k] > array[k+1] )
                       {
                       temp = array[k];
                       array[k] = array[k+1];
                       array[k+1] = temp;
                       }
           for ( k = 0; k < j; ++k )
               { /* print for user check */
               err = printf ( "%ld ", array[k] );
               if ( err <= 0 ) exit ( 1 );
               keysize += sprintf ( &key[keysize], "%ld.", array[k] );
               }
           keysize += sprintf ( &key[keysize], "/" );
           }



Eastlake                     Informational                     [Page 10]

RFC 2777              Verifiable Random Selection          February 2000


       }   /* end for i */

   /* have obtained all the input, now produce the output */
   err = printf ( "Key is:\n %s\n", key );
   if ( err <= 0 ) exit ( 1 );
   for ( i = 0; i < pool; ++i )
       selected [i] = i + 1;
   printf ( "index        hex value of MD5        div  selected\n" );
   for (   unch = 0, remaining = pool;
           unch < selection;
           ++unch, --remaining )
       {
       MD5Init ( &ctx );
       MD5Update ( &ctx, &unch, 1 );
       MD5Update ( &ctx, (unsigned char *)key, keysize );
       MD5Update ( &ctx, &unch, 1 );
       MD5Final ( uc16, &ctx );
       k = longremainder ( remaining, uc16 );
   /* printf ( "Remaining = %d, remainder = %d.\n", remaining, k ); */
       for ( j = 0; j < pool; ++j )
           if ( selected[j] )
               if ( --k < 0 )
                   {
                   printf ( "%2d  "
   "%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X%02X  "
   "%2d  -> %2d <-\n",
   unch+1, uc16[0],uc16[1],uc16[2],uc16[3],uc16[4],uc16[5],uc16[6],
   uc16[7],uc16[8],uc16[9],uc16[10],uc16[11],uc16[12],uc16[13],uc16[14],
   uc16[15], remaining, selected[j] );
                   selected[j] = 0;
                   break;
                   }
       }
   printf ( "\nDone, type any character to exit.\n" );