rfc2777.txt

著名的RFC文档,其中有一些文档是已经翻译成中文的的.


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" );
   getchar ();
   return 0;
   }

   /* prompt for an integer input */
   /****************************************************************/
   int getinteger ( char *string )
   {
   int     i, j;
   char    tin[257];

   while ( 1 )
   {
   printf ( string );



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


   printf ( "(or 'exit' to exit) " );
   gets ( tin );
   j = sscanf ( tin, "%d", &i );
   if (    ( j == EOF )

       ||  ( !j && ( ( tin[0] == 'e' ) || ( tin[0] == 'E' ) ) )
           )
       exit ( j );
   if ( j == 1 )
       return i;
   }   /* end while */
   }

   /* get remainder of dividing a 16 byte unsigned int
      by a small positive number */
   /****************************************************************/
   int longremainder ( unsigned char divisor,
                       unsigned char dividend[16] )
   {
   int i;
   long int kruft;

   if ( !divisor )
       return -1;
   for ( i = 0, kruft = 0; i < 16; ++i )
       {
       kruft = ( kruft << 8 ) + dividend[i];
       kruft %= divisor;
       }
   return kruft;
   }   /* end longremainder */

   /* calculate how many bits of entropy it takes to select N from P */
   /****************************************************************/
   /*             P!
     log  ( ----------------- )
        2    N! * ( P - N )!
   */

   double NPentropy ( int N, int P )
   {
   int         i;
   double      result = 0.0;

   if (    ( N < 1 )   /* not selecting anything? */
      ||   ( N >= P )  /* selecting all of pool or more? */
      )
       return 1.0;     /* degenerate case */



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


   for ( i = P; i > ( P - N ); --i )
       result += log ( i );
   for ( i = N; i > 1; --i )
       result -= log ( i );
   /* divide by [ log (base e) of 2 ] to convert to bits */
   result /= 0.69315;

   return result;
   }   /* end NPentropy */










































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


Appendix: History of NomCom Member Selection

   For reference purposes, here is a list of the IETF Nominations
   Committee member selection techniques and chairs so far:

           YEAR      CHAIR               SELECTION METHOD

        1993/1994  Jeff Case             Clergy
        1994/1995  Fred Baker            Clergy
        1995/1996  Guy Almes             Clergy
        1996/1997  Geoff Huston          Spouse
        1997/1998  Mike St.Johns         Algorithm
        1998/1999  Donald Eastlake 3rd   This Algorithm
        1999/2000  Avri Doria            This Alogrithm

   Clergy = Names were written on pieces of paper, placed in a
   receptacle, and a member of the clergy picked the Nomcom members.

   Spouse = Same as Clergy except chair's spouse made the selection.

   Algorithm = Algorithmic selection based on the same concepts as
   documented herein.

   This Algorithm = Algorithmic selection using the algorithm and
   reference code (but not the fake example sources of randomness)
   described herein.

























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


References

   RFC 1321  Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321,
             April 1992.

   RFC 1750  Eastlake, D., 3rd, Crocker, S. and J. Schiller, "Randomness
             Recommendations for Security", RFC 1750, December 1994.

   RFC 2727  Galvin, J., "IAB and IESG Selection, Confirmation, and
             Recall Process: Operation of the Nominating and Recall
             Committees", BCP 10, RFC 2727, February 2000.

Author's Address

   Donald E. Eastlake, 3rd
   Motorola
   65 Shindegan Hill Road, RR #1
   Carmel, NY 10512 USA

   Phone:  [phone] (h)
           [phone] (w)
   Fax:    [phone] (w)
   EMail:  [e-mail]




























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


Full Copyright Statement

   Copyright (C) The Internet Society (2000).  All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into languages other than
   English.

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
   BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
   HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Acknowledgement

   Funding for the RFC Editor function is currently provided by the
   Internet Society.



















Eastlake                     Informational                     [Page 16]