Network Working Group D. Eastlake 3rd
Request for Comments: 2777 Motorola
Category: Informational February 2000
Network Working Group D. Eastlake 3rd
Request for Comments: 2777 Motorola
Category: Informational February 2000
Publicly Verifiable Nomcom Random Selection
可公开验证的Nomcom随机选择
Status of this Memo
本备忘录的状况
This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited.
本备忘录为互联网社区提供信息。它没有规定任何类型的互联网标准。本备忘录的分发不受限制。
Copyright Notice
版权公告
Copyright (C) The Internet Society (2000). All Rights Reserved.
版权所有（C）互联网协会（2000年）。版权所有。
Abstract
摘要
This document describes a method for making random selections in such a way that the unbiased nature of the choice is publicly verifiable. As an example, the selection of the voting members of the IETF Nominations Committee from the pool of eligible volunteers is used. Similar techniques would be applicable to other cases.
本文件描述了一种随机选择的方法，其选择的无偏性是可公开验证的。例如，从合格志愿者库中选择IETF提名委员会的投票成员。类似的技术也适用于其他情况。
Acknowledgement
确认
Matt Crawford made major contributions to this document.
马特·克劳福德对本文件做出了重大贡献。
Table of Contents
目录
1. Introduction............................................2
2. General Flow of a Publicly Verifiable Process...........2
2.1 Determination of the Pool..............................2
2.2 Publication of the Algorithm...........................2
2.3 Publication of Selection...............................3
3. Randomness..............................................3
3.1 Sources of Randomness..................................3
3.2 Skew...................................................4
3.3 Entropy Needed.........................................4
4. A Suggested Precise Algorithm...........................5
5. Fully Worked Example....................................6
6. Security Considerations.................................7
7. Reference Code.........................................8
Appendix: History of NomCom Member Selection..............14
References................................................15
Author's Address..........................................15
Full Copyright Statement..................................16
1. Introduction............................................2
2. General Flow of a Publicly Verifiable Process...........2
2.1 Determination of the Pool..............................2
2.2 Publication of the Algorithm...........................2
2.3 Publication of Selection...............................3
3. Randomness..............................................3
3.1 Sources of Randomness..................................3
3.2 Skew...................................................4
3.3 Entropy Needed.........................................4
4. A Suggested Precise Algorithm...........................5
5. Fully Worked Example....................................6
6. Security Considerations.................................7
7. Reference Code.........................................8
Appendix: History of NomCom Member Selection..............14
References................................................15
Author's Address..........................................15
Full Copyright Statement..................................16
Under the IETF rules, each year 10 persons are randomly selected from among the eligible persons who volunteer to be the voting members of the nominations committee (NomCom) to nominate members of the Internet Engineering Steering Group (IESG) and the Internet Architecture Board (IAB) [RFC 2727]. The number of eligible volunteers in recent years has varied in the approximate range of 40 to 60.
根据IETF规则，每年从自愿成为提名委员会（NomCom）投票成员的合格人员中随机选出10人，以提名互联网工程指导小组（IESG）和互联网架构委员会（IAB）[RFC 2727]的成员。近年来，符合条件的志愿者人数大约在40至60人之间。
It is highly desireable that the random selection of the voting NomCom be done in a unimpeachable fashion so that no reasonable charges of bias or favoritism can be brought. This is for the protection of the IETF from bias and protection of the administrator of the selection (currently, the appointed non-voting NomCom chair) from suspicion of bias.
非常希望以无可指责的方式随机选择投票的NomCom，这样就不会产生任何合理的偏见或偏袒指控。这是为了保护IETF不受偏见的影响，以及保护遴选管理人（目前为任命的无投票权NomCom主席）不受偏见的怀疑。
A method such that public information will enable any person to verify the randomness of the selection meets this criterion. This document gives an example of such a method.
公开信息使任何人都能够验证选择的随机性是否符合该标准的方法。本文件给出了此类方法的示例。
In general, a selection of NomCom members publicly verifiable as unbiased or similar selection could follow the three steps given below.
一般而言，可公开验证为无偏见或类似选择的NomCom成员选择可遵循以下三个步骤。
First, you need to determine the pool from which the selection is to be made.
首先，您需要确定要从中进行选择的池。
Volunteers are solicited by the appointed (non-voting) NomCom chair. Their names are then passed through the IETF Secretariat to check eligibility. (Current eligibility criteria relate to IETF meeting attendance, records of which are maintained by the Secretariat.) The full list of eligible volunteers is made public early enough that there is a reasonable time to resolve any disputes as to who should be in the pool, probably a week to ten days before the selection.
志愿者由指定（无投票权）的NomCom主席招募。然后，他们的名字将通过IETF秘书处检查资格。（目前的资格标准涉及IETF会议出席情况，其记录由秘书处保存。）合格志愿者的完整名单尽早公布，以便有合理的时间解决关于谁应该在人才库中的任何争议，可能在选择前一周到十天。
The exact algorithm to be used, including the public future sources of randomness, is made public. For example, the members of the final list of eligible volunteers are ordered by publicly numbering them, several public future sources of randomness such as government run
将要使用的精确算法，包括未来公开的随机性来源，已公开。例如，合格志愿者最终名单的成员是通过公开编号来排序的，这是一些公共的随机性来源，如政府管理
lotteries are specified, and an exact algorithm is specified whereby eligible volunteers are selected based on a strong hash function [RFC 1750] of these future sources of randomness.
指定了彩票，并指定了一个精确的算法，根据这些未来随机性来源的强散列函数[RFC 1750]选择合格的志愿者。
When the prespecified sources of randomness produce their output, those values plus a summary of the execution of the algorithm for selection should be announced so that anyone can verify that the correct randomness source values were used and the algorithm properly executed. A cut off time for any complaint that the algorithm was run with the wrong inputs or not faithfully executed should be specified to finalize the output and provide a stable NomCom.
当预先指定的随机性源产生其输出时，应宣布这些值加上选择算法执行的摘要，以便任何人都可以验证是否使用了正确的随机性源值以及算法是否正确执行。任何关于算法在错误输入下运行或未忠实执行的投诉都应指定截止时间，以最终确定输出并提供稳定的NomCom。
The crux of the unbiased nature of the selection is that it is based exactly on random information which will be revealed in the future and thus can not be known to the person specifying the algorithm by which that random information will be used to select the NomCom members. The random information must be such that it will be publicly revealed in a timely fashion.
选择的无偏性的关键在于，它完全基于未来将披露的随机信息，因此无法为指定使用该随机信息选择NomCom成员的算法的人所知。随机信息必须及时公开披露。
The random sources should not include anything that any reasonable person would believe to be under the control or influence of the IETF or its components, such as IETF meeting attendance statistics, numbers of documents issued, or the like.
随机来源不应包括任何有理性的人认为受IETF或其组成部分控制或影响的任何内容，如IETF会议出席统计、发布的文件数量等。
Examples of good information to use are lottery winning numbers for specified runnings of specified lotteries. Particularly for government run lotteries, great care is usually taken to see that they produce random quantities. Even in the unlikely case one were to have been rigged, it would almost certainly be in connection with winning money in the lottery, not in connection with IETF use.
可以使用的好信息的例子是指定彩票的指定运行的彩票中奖号码。特别是对于政府经营的彩票，通常会非常小心地看到它们产生随机数量。即使在不太可能的情况下，一个被操纵，它几乎肯定与彩票中奖有关，而不是与IETF的使用有关。
Other possibilities are such things as the closing price of a stock on a particular day, daily balance in the US Treasury on a specified day, the volume of trading on the New York Stock exchange on a specified day, etc. (However, the reference code given below will not handle integers that are too large.) Sporting events can be used but only with care to specify exactly what quantities are being presumed random and what will be done if they are cancelled or delayed.
其他可能性包括股票在特定日期的收盘价、美国财政部在特定日期的每日余额、纽约证券交易所在特定日期的交易量等（但是，下面给出的参考代码不会处理过大的整数）体育赛事可以使用，但必须小心地明确规定哪些数量被假定为随机的，以及如果取消或延迟将采取什么措施。
It is important that the last source of randomness, chronologically, produce a substantial amount of the entropy needed. If most of the randomness has come from the earlier of the specified sources, and
重要的是，随机性的最后一个来源，按时间顺序，产生所需的大量熵。如果大部分随机性来自于较早的指定来源，以及
someone has even limited influence on the final source, they might do an exhaustive analysis and exert such influence so as to bias the selection in the direction they wanted. Thus it is best for the last source to be an especially strong and unbiased source of a large amount of randomness such as a government run lottery.
有些人甚至对最终来源的影响有限，他们可能会进行详尽的分析并施加这种影响，从而使选择偏向他们想要的方向。因此，最好是最后一个来源是一个特别强大和无偏见的来源大量的随机性，如政府运行的彩票。
It is best not to use too many different sources. Every additional source increases the probability that it might be delayed or cancelled calling into play contingency plans or, worst of all, possibly creating a situation that was not anticipated. This would either require arbitrary judgement by the Nomcom chair, defeating the randomness of the selection, or a re-run with a new set of sources, causing much delay. Probably a good number of sources is three.
最好不要使用太多不同的来源。每一个额外的来源都增加了延迟或取消应急计划的可能性，或者，最糟糕的是，可能会造成意想不到的情况。这要么需要Nomcom主席的任意判断，克服选择的随机性，要么重新运行一组新的源，造成很大的延迟。可能有很多来源是三个。
Many of the sources of randomness suggested above produce data which is not uniformly distributed. This is certainly true of stock prices and horse race results, for example. However, use of a strong mixing function [RFC 1750] will extract the available entropy and produce a hash value whose bits, remainder modulo a small divisor, etc., are uniformly distributed.
上面提到的许多随机性来源产生的数据不是均匀分布的。例如，股票价格和赛马结果肯定是如此。然而，使用强混合函数[RFC 1750]将提取可用的熵并产生一个散列值，该散列值的位、模小除数的余数等均匀分布。
What we are doing is selection N items without replacement from a population of P items. The number of different ways to do this is as follows, where "!" represents the factorial function:
我们正在做的是从P个项目的总体中选择N个项目而不进行替换。执行此操作的不同方法如下所示，其中“！”表示阶乘函数：
P!
-------------
N! * (P - N)!
P!
-------------
N! * (P - N)!
To do this in a completely random fashion requires as many random bits as the logarithm base 2 of that quantity. Some sample calculated approximate number of random bits for the selection of 10 nomcom members from various pool sizes is given below:
要以完全随机的方式执行此操作，需要与该数量的对数基数2一样多的随机位。下面给出了从各种池大小中选择10个nomcom成员的一些样本计算的近似随机位数：
Random Selection of Ten Items From Pool
从池中随机选择10项
Pool size 20 25 30 35 40 50 60 75 100 Bits needed 18 22 25 28 30 34 37 40 44
池大小20 25 30 35 40 50 60 75 100位需要18 22 25 28 30 34 37 40 44
Using an inadequate number of bits means that not all of the possible selections would be available. For a substantially inadequate amount of entropy, there would be substantial correlations between the selection of two members of the pool, for example. However, as a practical matter, for pool sizes likely to be encountered in IETF
使用的位数不足意味着并非所有可能的选择都可用。例如，如果熵的数量严重不足，则池中两个成员的选择之间会存在大量相关性。然而，实际上，对于IETF中可能遇到的池大小
nomcom membership selection, 40 bits of entropy should always be adequate. Even if there is a large pool and theoretically more bits are needed for complete randomness, 40 bits of entropy will assure that the probability of selection of each pool member differs from that of other pool members, the correlation between the selection of any pair of pool members, etc., differs only insignificantly from that for completely random selection.
nomcom成员选择，40位的熵应该总是足够的。即使存在一个较大的池，并且理论上需要更多的比特来实现完全随机性，40比特的熵将确保每个池成员的选择概率不同于其他池成员的选择概率，任何池成员对的选择之间的相关性等。，与完全随机选择的区别不大。
An MD5 [RFC 1321] hash has 128 bits and therefore can produce no more than that number of bits of entropy. However, this is three times what is likely to ever been needed for IETF nomcom membership selection.
MD5[RFC1321]散列有128位，因此产生的熵位数不超过该位数。然而，这是IETF nomcom成员选择可能需要的三倍。
It is important that a precise algorithm be given for mixing the random sources specified and making the selection based thereon. Sources suggested above each produce either a single positive number (i.e., closing price for a stock) or a small set of positive numbers (many lotteries provide 6 numbers in the range of 1 through 40 or the like, a sporting event could produce the scores of two teams, etc.). A sample precise algorithm is as follows:
重要的是，必须给出一个精确的算法，用于混合指定的随机源，并在此基础上进行选择。上述信息来源分别产生一个正数（即股票收盘价）或一小部分正数（许多彩票提供6个介于1到40之间的数字或类似数字，体育赛事可能产生两支球队的分数等）。精确算法示例如下所示：
For each source producing multiple numeric values, represent each as a decimal number terminated by a period (or with a period separating the whole from the fractional part) and without leading zeroes (except for a single leading zero if the integer part is zero) or trailing zeroes after the period. Order them from smallest to the largest and concatenate them and follow the results by a "/". For each source producing a single number, simply represent it as above with a trailing "/". At this point you have a string for each source, say s1/, s2/, ... Concatenate these strings in a pre-specified order and represent each character as its ASCII code producing s1/s2/.../.
对于产生多个数值的每个源，将每个源表示为一个十进制数，该十进制数以一个句点终止（或以一个句点将整部分与小数部分分开），并且在句点后没有前导零（如果整数部分为零，则只有一个前导零除外）或尾随零。将它们从最小到最大排序，并将它们连接起来，然后在结果后面加一个“/”。对于产生单个数字的每个源，只需如上所述用尾随“/”表示即可。此时，每个源都有一个字符串，比如s1/，s2/。。。以预先指定的顺序连接这些字符串，并将每个字符表示为其产生s1/s2/../ASCII码。
You can then produce a sequence of random values derived from a strong mixing of these sources by calculating the MD5 hash [RFC 1321] of this string prefixed and suffixed with a zero byte for the first value, the string prefixed and suffixed by a 0x01 byte for the second value, etc. Treat each of these derived random values as a positive multiprecision integer. If there are P eligible volunteers, select the first voting member by dividing the first derived random value by P and using the remainder plus one as the position of the selectee in the ordered list or volunteers. Select the second voting member by dividing the second derived random value by P-1 and using the remainder plus one as the position of the selectee in the list with the first selectee eliminated. Etc.
然后，通过计算该字符串的MD5散列[RFC 1321]，该字符串的第一个值以零字节作为前缀和后缀，第二个值以0x01字节作为前缀和后缀，等。将这些导出的随机值视为正多精度整数。如果有P名符合条件的志愿者，则通过将第一个衍生随机值除以P，并使用余数加1作为被选者在有序列表或志愿者中的位置来选择第一个投票成员。通过将第二个衍生随机值除以P-1，并使用余数加1作为列表中被选中者的位置（第一个被选中者被删除），选择第二个投票成员。等
It is recommended that alphanumeric random sources be avoided due to the greater difficulty in canonicalizing them in an independently repeatable fashion; however, if any are used, all white space, punctuation, and special characters should be removed and all letters set to upper case. This will leave only an unbroken sequence of letters A-Z and digits 0-9 which can be treated as a canonicalized number above and suffixed with a "/".
建议避免使用字母数字随机源，因为以独立可重复的方式规范化它们会有更大的困难；但是，如果使用了任何字符，则应删除所有空格、标点符号和特殊字符，并将所有字母设置为大写。这将只留下一个完整的字母A-Z和数字0-9序列，它们可以被视为上面的规范化数字，并以“/”作为后缀。
Assume the following ordered list of 25 eligible volunteers is published in advance of selection:
假设在选择之前公布了以下25名合格志愿者的有序名单：
1. John 11. Pollyanna 21. Pride 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
1.约翰11岁。波利亚娜21。骄傲2。玛丽12岁。彭德拉贡22号。懒惰3。害羞的13。潘多拉23。嫉妒4。愚蠢的14。信仰24。愤怒5。困倦的15岁。希望25。卡钦斯基6。脾气暴躁的16岁。慈善7。文件17。爱8。斯内兹18。长时间忍耐9。漂亮的19岁。贞操10。卡桑德拉20。史密斯
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.
1. 贝塔斯塔尼州人民民主彩票于1998年10月1日发行六张中奖号码（忽略第七张“额外”号码）。2.1998年9月x日当天或之后第一天在Hialeia举行的所有比赛中获胜的马的数量，其中至少有两场比赛。3.阿尔法兰共和国1998年10月1日的州彩票每日号码被视为一个四位数整数。4.1998年9月x日后第一个营业日在月球证券交易所交易的示例公司股票的收盘价。
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
来源1:9,18,26,34,41,45来源2:2,5,12,8,10来源3:9319来源4:13 11/16
Resulting key string:
结果键字符串：
9.18.26.34.41.45./2.5.8.10.12./9319./13.6875/
9.18.26.34.41.45./2.5.8.10.12./9319./13.6875/
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.
下表给出了上述键字符串MD5的十六进制，该字符串用一个字节括起来，该字节的值依次为0x00、0x01、0x02和0x09。给出了每个阶段剩余池数大小的除数，并根据池中剩余池数的原始数给出了被选择者的索引。
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 <-
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)
1. 彭德拉贡（12）6。愤怒（24）2。发牢骚的（6）7。波利亚娜（11）3。斯内兹（8）8。贞操（19）4。羞涩的。希望（15）5。玛丽（2）10。懒惰（22）
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.
为了保持选择的不可预测性，如果由于死亡、辞职、驱逐等原因需要更换nomcom成员，则应使用新的公开宣布的未来随机来源来选择其替代者。
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.
此代码使用了[RFC 1321]（“RSA Data Security，Inc.MD5消息摘要算法”）中的MD5参考代码。处理多个浮点数的代码部分由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>
/****************************************************************
*
* 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"
#包括“global.h”#包括“MD5.h”
/* local prototypes */
int longremainder ( unsigned char divisor,
unsigned char dividend[16] );
int getinteger ( char *string );
double NPentropy ( int N, int P );
/* 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 */
/****************************************************************/
/* 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];
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 )
pool = getinteger ( "Type size of pool:\n" );
if ( pool > 255 )
{
printf ( "Pool too big.\n" );
exit ( 1 );
}
{
printf ( "Pool too big.\n" );
exit ( 1 );
}
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;
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
其他的
{ /* 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], "/" );
}
{ /* 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], "/" );
}
} /* end for i */
} /* 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;
}
/* 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];
/* prompt for an integer input */
/****************************************************************/
int getinteger ( char *string )
{
int i, j;
char tin[257];
while ( 1 )
{
printf ( string );
while ( 1 )
{
printf ( string );
printf ( "(or 'exit' to exit) " );
gets ( tin );
j = sscanf ( tin, "%d", &i );
if ( ( j == EOF )
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 */
}
|| ( !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;
/* 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 */
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 )!
*/
/* 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;
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 */
if ( ( N < 1 ) /* not selecting anything? */
|| ( N >= P ) /* selecting all of pool or more? */
)
return 1.0; /* degenerate case */
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;
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 */
return result;
} /* end NPentropy */
Appendix: History of NomCom Member Selection
附录：NomCom成员选择历史
For reference purposes, here is a list of the IETF Nominations Committee member selection techniques and chairs so far:
以下是迄今为止IETF提名委员会成员选择技巧和主席的列表，仅供参考：
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
1993/1994 Jeff Case神职人员1994/1995 Fred Baker神职人员1995/1996 Guy Almes神职人员1996/1997 Geoff Huston配偶1997/1998 Mike St.Johns算法1998/1999 Donald Eastlake 3th此算法1999/2000 Avri Doria此算法
Clergy = Names were written on pieces of paper, placed in a receptacle, and a member of the clergy picked the Nomcom members.
神职人员=姓名写在纸片上，放在一个容器中，神职人员挑选Nomcom成员。
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.
该算法=使用本文所述算法和参考代码（但不是伪随机性示例源）的算法选择。
References
工具书类
RFC 1321 Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 1992.
RFC 1321 Rivest，R.，“MD5消息摘要算法”，RFC 1321，1992年4月。
RFC 1750 Eastlake, D., 3rd, Crocker, S. and J. Schiller, "Randomness Recommendations for Security", RFC 1750, December 1994.
RFC 1750伊斯特莱克，D.，3，克罗克，S.和J.席勒，“安全性的随机性建议”，RFC 1750，1994年12月。
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.
RFC 2727 Galvin，J.，“IAB和IESG的选择、确认和召回过程：提名和召回委员会的运作”，BCP 10，RFC 2727，2000年2月。
Author's Address
作者地址
Donald E. Eastlake, 3rd Motorola 65 Shindegan Hill Road, RR #1 Carmel, NY 10512 USA
Donald E.Eastlake，摩托罗拉3号，新德干山路65号，美国纽约州卡梅尔市RR#1号，邮编10512
Phone: +1-914-276-2668 (h)
+1-508-261-5434 (w)
Fax: +1-508-261-4447 (w)
EMail: Donald.Eastlake@motorola.com
Phone: +1-914-276-2668 (h)
+1-508-261-5434 (w)
Fax: +1-508-261-4447 (w)
EMail: Donald.Eastlake@motorola.com
Full Copyright Statement
完整版权声明
Copyright (C) The Internet Society (2000). All Rights Reserved.
版权所有（C）互联网协会（2000年）。版权所有。
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.
RFC编辑功能的资金目前由互联网协会提供。