Debian Codegraph @

rfc1439.html

raw
1 <pre>Network Working Group C. Finseth
2 Request for Comments: 1439 University of Minnesota
3 March 1993
4
5
6 <span class="h1">The Uniqueness of Unique Identifiers</span>
7
8 Status of this Memo
9
10 This memo provides information for the Internet community. It does
11 not specify an Internet standard. Distribution of this memo is
12 unlimited.
13
14 Abstract
15
16 This RFC provides information that may be useful when selecting a
17 method to use for assigning unique identifiers to people.
18
19 <span class="h2"><a class="selflink" id="section-1" href="#section-1">1</a>. The Issue</span>
20
21 Computer systems require a way to identify the people associated with
22 them. These identifiers have been called "user names" or "account
23 names." The identifers are typically short, alphanumeric strings.
24 In general, these identifiers must be unique.
25
26 The uniqueness is usually achieved in one of three ways:
27
28 1) The identifiers are assigned in a unique manner without using
29 information associated with the individual. Example identifiers are:
30
31 ax54tv
32 cs00034
33
34 This method was often used by large timesharing systems. While it
35 achieved the uniqueness property, there was no way of guessing the
36 identifier without knowing it through other means.
37
38 2) The identifiers are assigned in a unique manner where the bulk of
39 the identifier is algorithmically derived from the individual's name.
40 Example identifers are:
41
42 Craig.A.Finseth-1
43 Finseth1
44 caf-1
45 fins0001
46
47 3) The identifiers are in general not assigned in a unique manner:
48 the identifier is algorithmically derived from the individual's name
49
50
51
52 <span class="grey">Finseth [Page 1]</span></pre>
53 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-2" ></span>
54 <span class="grey"><a href="./rfc1439">RFC 1439</a> Uniqueness of Unique Identifiers March 1993</span>
55
56
57 and duplicates are handled in an ad-hoc manner. Example identifiers
58 are:
59
60 Craig.Finseth
61 caf
62
63 Now that we have widespread electronic mail, an important feature of
64 an identifier system is the ability to predict the identifier based
65 on other information associated with the individual. This other
66 information is typically the person's name.
67
68 Methods two and three make such predictions possible, especially if
69 you have one example mapping from a person's name to the identifier.
70 Method two relies on using some or all of the name and
71 algorithmically varying it to ensure uniqueness (for example, by
72 appending an integer). Method three relies on using some or all of
73 the name and selects an alternate identifier in the case of a
74 duplication.
75
76 For both methods, it is important to minimize the need for making the
77 adjustments required to ensure uniqueness (i.e., an integer that is
78 not 1 or an alternate identifier). The probability that an
79 adjustment will be required depends on the format of the identifer
80 and the size of the organization.
81
82 <span class="h2"><a class="selflink" id="section-2" href="#section-2">2</a>. Identifier Formats</span>
83
84 There are a number of popular identifier formats. This section will
85 list some of them and supply both typical and maximum values for the
86 number of possible identifiers. A "typical" value is the number that
87 you are likely to run into in real life. A "maximum" value is the
88 largest number of possible (without getting extreme about it) values.
89 All ranges are expressed as a number of bits.
90
91 <span class="h3"><a class="selflink" id="section-2.1" href="#section-2.1">2.1</a> Initials</span>
92
93 There are three popular formats based on initials: those with one,
94 two, or three letters. (The number of people with more than three
95 initials is assumed to be small.) Values:
96
97 format typical maximum
98
99 I 4 5
100 II 8 10
101 III 12 15
102
103
104
105
106
107
108 <span class="grey">Finseth [Page 2]</span></pre>
109 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-3" ></span>
110 <span class="grey"><a href="./rfc1439">RFC 1439</a> Uniqueness of Unique Identifiers March 1993</span>
111
112
113 You can also think of these as first, middle, and last initials:
114
115 I 4 5
116 F L 8 10
117 F M L 12 15
118
119 <span class="h3"><a class="selflink" id="section-2.2" href="#section-2.2">2.2</a> Names</span>
120
121 Again, there are three popular formats based on using names: those
122 with the first name, last name, and both first and last names.
123 Values:
124
125 format typical maximum
126
127 First 8 14
128 Last 9 13
129 First Last 17 27
130
131 <span class="h3"><a class="selflink" id="section-2.3" href="#section-2.3">2.3</a> Combinations</span>
132
133 I have seen these combinations in use ("F" is first initial, "M" is
134 middle initial, and "L" is last initial):
135
136 format typical maximum
137
138 F Last 13 18
139 F M Last 17 23
140 First L 12 19
141 First M Last 21 32
142
143 <span class="h3"><a class="selflink" id="section-2.4" href="#section-2.4">2.4</a> Complete List</span>
144
145 Here are all possible combinations of nothing, initial, and full name
146 for first, middle, and last. The number of Middle names is assumed
147 to be the same as the number of First names. Values:
148
149 format typical maximum
150
151 _ _ _ 0 0
152 _ _ L 4 5
153 _ _ Last 9 13
154
155 _ M _ 4 5
156 _ M L 5 10
157 _ M Last 13 18
158
159 _ Middle _ 8 14
160 _ Middle L 12 19
161
162
163
164 <span class="grey">Finseth [Page 3]</span></pre>
165 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-4" ></span>
166 <span class="grey"><a href="./rfc1439">RFC 1439</a> Uniqueness of Unique Identifiers March 1993</span>
167
168
169 _ Middle Last 17 27
170
171 F _ _ 4 5
172 F _ L 5 10
173 F _ Last 13 18
174
175 F M _ 5 10
176 F M L 12 15
177 F M Last 17 23
178
179 F Middle _ 12 19
180 F Middle L 16 24
181 F Middle Last 21 32
182
183 First _ _ 8 14
184 First _ L 12 19
185 First _ Last 17 27
186
187 First M _ 12 19
188 First M L 16 24
189 First M Last 21 32
190
191 First Middle _ 16 28
192 First Middle L 20 33
193 First Middle Last 26 40
194
195 <span class="h2"><a class="selflink" id="section-3" href="#section-3">3</a>. Probabilities of Duplicates</span>
196
197 As can be seen, the information content in these identifiers in no
198 case exceeds 40 bits and the typical information content never
199 exceeds 26 bits. The content of most of them is in the 8 to 20 bit
200 range. Duplicates are thus not only possible but likely.
201
202 The method used to compute the probability of duplicates is the same
203 as that of the well-known "birthday" problem. For a universe of N
204 items, the probability of duplicates in X members is expressed by:
205
206 N N-1 N-2 N-(X-1)
207 - x --- x --- x ... x -------
208 N N N N
209
210 A program to compute this function for selected values of N is given
211 in the appendix, as is its complete output.
212
213 The "1%" column is the number of items (people) before an
214 organization of that (universe) size has a 1% chance of a duplicate.
215 Similarly for 2%, 5%, 10%, and 20%.
216
217
218
219
220 <span class="grey">Finseth [Page 4]</span></pre>
221 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-5" ></span>
222 <span class="grey"><a href="./rfc1439">RFC 1439</a> Uniqueness of Unique Identifiers March 1993</span>
223
224
225 bits universe 1% 2% 5% 10% 20%
226
227 6 64 2 3 4 5 6
228 7 128 3 3 5 6 8
229 8 256 3 4 6 8 12
230 9 512 4 6 8 11 16
231 10 1,024 6 7 11 16 22
232 11 2,048 7 10 15 22 31
233 12 4,096 10 14 21 30 44
234 13 8,192 14 19 30 43 61
235 14 16,384 19 27 42 60 86
236 15 32,768 27 37 59 84 122
237 16 65,536 37 52 83 118 172
238 17 131,072 52 74 117 167 243
239 18 262,144 74 104 165 236 343
240 19 524,288 104 147 233 333 485
241 20 1,048,576 146 207 329 471 685
242 21 2,097,152 206 292 465 666 968
243 22 4,194,304 291 413 657 941 1369
244 23 8,388,608 412 583 929 1330 1936
245 24 16,777,216 582 824 1313 1881 2737
246 25 33,554,432 822 1165 1856 2660 3871
247 26 67,108,864 1162 1648 2625 3761 5474
248 27 134,217,728 1644 2330 3712 5319 7740
249 28 268,435,456 2324 3294 5249 7522 10946
250 29 536,870,912 3286 4659 7422 10637 15480
251 30 1,073,741,824 4647 6588 10496 15043 21891
252 31 2,147,483,648 6571 9316 14844 21273 30959
253
254 For example, assume an organization were to select the "First Last"
255 form. This form has 17 bits (typical) and 27 bits (maximum) of
256 information. The relevant line is:
257
258 17 131,072 52 74 117 167 243
259
260 For an organization with 100 people, the probability of a duplicate
261 would be between 2% and 5% (probably around 4%). If the organization
262 had 1,000 people, the probability of a duplicate would be much
263 greater than 20%.
264
265 Appendix: Reuse of Identifiers and Privacy Issues
266
267 Let's say that an organization were to select the format:
268
269 First.M.Last-#
270
271 as my own organization has. Is the -# required, or can one simply
272 do:
273
274
275
276 <span class="grey">Finseth [Page 5]</span></pre>
277 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-6" ></span>
278 <span class="grey"><a href="./rfc1439">RFC 1439</a> Uniqueness of Unique Identifiers March 1993</span>
279
280
281 Craig.A.Finseth
282
283 for the first one and
284
285 Craig.A.Finseth-2
286
287 (or -1) for the second? The answer is "no," although for non-obvious
288 reasons.
289
290 Assume that the organization has made this selection and a third
291 party wants to send e-mail to Craig.A.Finseth. Because of the
292 Electronic Communications Privacy Act of 1987, an organization must
293 treat electronic mail with care. In this case, there is no way for
294 the third party user to reliably know that sending to Craig.A.Finseth
295 is (may be) the wrong party. On the other hand, if the -# suffix is
296 always present and attempts to send mail to the non-suffix form are
297 rejected, the third party user will realize that they must have the
298 suffix in order to have a unique identifier.
299
300 For similar reasons, identifiers in this form should not be re-used
301 in the life of the mail system.
302
303 Appendix: Perl Program to Compute Probabilities
304
305 #!/usr/local/bin/perl
306
307 for $bits (6..31) {
308 &amp;Compute($bits);
309 }
310 exit(0);
311
312 # ------------------------------------------------------------
313
314 sub Compute {
315 $bits = $_[0];
316 $num = 1 &lt;&lt; $bits;
317 $cnt = $num;
318
319 print "bits $bitsnumber $num:0;
320
321 for ($prob = 1; $prob &gt; 0.99; ) {
322 $prob *= $cnt / $num;
323 $cnt--;
324 }
325
326 print "", $num - $cnt, "$prob0;
327
328 for (; $prob &gt; 0.98; ) {
329
330
331
332 <span class="grey">Finseth [Page 6]</span></pre>
333 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-7" ></span>
334 <span class="grey"><a href="./rfc1439">RFC 1439</a> Uniqueness of Unique Identifiers March 1993</span>
335
336
337 $prob *= $cnt / $num;
338 $cnt--;
339 }
340 print "", $num - $cnt, "$prob0;
341
342 for (; $prob &gt; 0.95; ) {
343 $prob *= $cnt / $num;
344 $cnt--;
345 }
346 print "", $num - $cnt, "$prob0;
347
348 for (; $prob &gt; 0.90; ) {
349 $prob *= $cnt / $num;
350 $cnt--;
351 }
352 print "", $num - $cnt, "$prob0;
353
354 for (; $prob &gt; 0.80; ) {
355 $prob *= $cnt / $num;
356 $cnt--;
357 }
358 print "", $num - $cnt, "$prob0;
359
360 print "0;
361 }
362
363 Appendix: Perl Program Output
364
365 bits 6 number 64:
366 2 0.984375
367 3 0.95361328125
368 4 0.90891265869140625
369 5 0.85210561752319335938
370 6 0.78553486615419387817
371
372 bits 7 number 128:
373 3 0.9766845703125
374 3 0.9766845703125
375 5 0.92398747801780700684
376 6 0.88789421715773642063
377 8 0.79999355674331695809
378
379 bits 8 number 256:
380 3 0.988311767578125
381 4 0.97672998905181884766
382 6 0.94268989971169503406
383 8 0.89542306910786462204
384 12 0.76969425214152431547
385
386
387
388 <span class="grey">Finseth [Page 7]</span></pre>
389 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-8" ></span>
390 <span class="grey"><a href="./rfc1439">RFC 1439</a> Uniqueness of Unique Identifiers March 1993</span>
391
392
393 bits 9 number 512:
394 4 0.98832316696643829346
395 6 0.97102570187075798458
396 8 0.94652632751096643648
397 11 0.89748056780293572476
398 16 0.78916761796439427457
399
400 bits 10 number 1024:
401 6 0.98543241551841020964
402 7 0.97965839745873206645
403 11 0.94753115178840541244
404 16 0.88888866335604777014
405 22 0.79677613655632184564
406
407 bits 11 number 2048:
408 7 0.98978773152834598203
409 10 0.97823367137821537476
410 15 0.94990722378677450166
411 22 0.89298119682681720288
412 31 0.79597589885472519455
413
414 bits 12 number 4096:
415 10 0.98906539062491305447
416 14 0.97800426773009718762
417 21 0.94994111694430838355
418 30 0.89901365764115603874
419 44 0.79312138620093930452
420
421 bits 13 number 8192:
422 14 0.98894703242829806733
423 19 0.97932692503837115439
424 30 0.94822407309193512681
425 43 0.89545741661906652631
426 61 0.7993625840767998314
427
428 bits 14 number 16384:
429 19 0.98961337517641645434
430 27 0.97879319536756481668
431 42 0.94876352395820107155
432 60 0.89748107890372830209
433 86 0.79973683158771624591
434
435 bits 15 number 32768:
436 27 0.98934263776790121181
437 37 0.97987304880641035165
438 59 0.94909471808051404373
439 84 0.89899774209805793923
440 122 0.79809378598190949816
441
442
443
444 <span class="grey">Finseth [Page 8]</span></pre>
445 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-9" ></span>
446 <span class="grey"><a href="./rfc1439">RFC 1439</a> Uniqueness of Unique Identifiers March 1993</span>
447
448
449 bits 16 number 65536:
450 37 0.98988724065590050216
451 52 0.97996496661944154649
452 83 0.94937874420413270737
453 118 0.89996948010355670711
454 172 0.79884228150816105618
455
456 bits 17 number 131072:
457 52 0.98993311138884398925
458 74 0.97960010416289267088
459 117 0.94952974978505377823
460 167 0.89960828942716541956
461 243 0.79894309171178368167
462
463 bits 18 number 262144:
464 74 0.98974844864797828503
465 104 0.97977315557223210174
466 165 0.94968621078621640041
467 236 0.8995926348279144058
468 343 0.7994422793765953994
469
470 bits 19 number 524288:
471 104 0.98983557888923057178
472 147 0.97973841652874515962
473 233 0.94974719445364064185
474 333 0.89991342619657743729
475 485 0.79936749144148444568
476
477 bits 20 number 1048576:
478 146 0.98995567500195758015
479 207 0.97987072919607220989
480 329 0.94983990872655321702
481 471 0.89980857451706741656
482 685 0.79974215234216872172
483
484 bits 21 number 2097152:
485 206 0.98998177463778547214
486 292 0.97994400939715686771
487 465 0.94985589918092261374
488 666 0.89978055267663470396
489 968 0.79994886751736571373
490
491 bits 22 number 4194304:
492 291 0.98999013137747737812
493 413 0.97991951242142538714
494 657 0.94991674892578203959
495 941 0.89991652739633254399
496 1369 0.79989205747440361716
497
498
499
500 <span class="grey">Finseth [Page 9]</span></pre>
501 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-10" ></span>
502 <span class="grey"><a href="./rfc1439">RFC 1439</a> Uniqueness of Unique Identifiers March 1993</span>
503
504
505 bits 23 number 8388608:
506 412 0.98995762604049764022
507 583 0.97997846530691334888
508 929 0.94991024716640248826
509 1330 0.89999961063320443877
510 1936 0.79987028265451087794
511
512 bits 24 number 16777216:
513 582 0.98997307486745211857
514 824 0.97999203469417239809
515 1313 0.94995516684099989835
516 1881 0.89997049960675035152
517 2737 0.79996700222056416063
518
519 bits 25 number 33554432:
520 822 0.98999408609360783906
521 1165 0.9799956928177964155
522 1856 0.9499899669674316538
523 2660 0.8999664414095410736
524 3871 0.79992328289672998132
525
526 bits 26 number 67108864:
527 1162 0.98999884535478044345
528 1648 0.9799801637652703068
529 2625 0.94997437525354821997
530 3761 0.89999748465616635773
531 5474 0.79993922903192515861
532
533 bits 27 number 134217728:
534 1644 0.9899880636014986024
535 2330 0.97998730103356856969
536 3712 0.94997727934463771504
537 5319 0.89998552434244594167
538 7740 0.79999591580103557309
539
540 bits 28 number 268435456:
541 2324 0.98999458855588851058
542 3294 0.97999828329325222587
543 5249 0.94998397932368705554
544 7522 0.89998576049206902017
545 10946 0.79999058777500076101
546
547 bits 29 number 536870912:
548 3286 0.98999717306002099626
549 4659 0.97999160965267329004
550 7422 0.94999720388831232487
551 10637 0.89999506567702891591
552 15480 0.7999860979665908145
553
554
555
556 <span class="grey">Finseth [Page 10]</span></pre>
557 <hr class='noprint'/><!--NewPage--><pre class='newpage'><span id="page-11" ></span>
558 <span class="grey"><a href="./rfc1439">RFC 1439</a> Uniqueness of Unique Identifiers March 1993</span>
559
560
561 bits 30 number 1073741824:
562 4647 0.98999674474047760775
563 6588 0.97999531736215383937
564 10496 0.94999806770951356061
565 15043 0.89999250738244507275
566 21891 0.79999995570982085358
567
568 bits 31 number 2147483648:
569 6571 0.98999869761078929109
570 9316 0.97999801528523688976
571 14844 0.94999403283519279206
572 21273 0.89999983631135749285
573 30959 0.79999272222201334159
574
575 References
576
577 Bruce Lansky (1984). The Best Baby Name Book. Deephaven, MN:
578 Meadowbrook. ISBN 0-671-54463-2.
579
580 Lareina Rule (1988). Name Your Baby. Bantam. ISBN 0-553-27145-8.
581
582 Security Considerations
583
584 Security issues are not discussed in this memo.
585
586 Author's Address
587
588 Craig A. Finseth
589 Networking Services
590 Computer and Information Services
591 University of Minnesota
592 130 Lind Hall
593 207 Church St. SE
594 Minneapolis, MN 55455-0134
595
596 EMail: [email protected] or
597 [email protected]
598
599 Phone: +1 612 624 3375
600 Fax: +1 612 626 1002
601
602
603
604
605
606
607
608
609
610
611
612 Finseth [Page 11]
613 </pre>