home *** CD-ROM | disk | FTP | other *** search
open in: 
MacOS 8.1
|
Win98
|
DOS
view JSON data
|
view as text
This file was processed as: Mailbox/MIME Entity
(archive/mbox).
You can browse this item here: factor.txt
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| dexvert
| Mailbox/MIME Entity (archive/mbox)
| magic
| Supported |
| 100%
| dexvert
| Internet Message Format (text/imf)
| magic
| Supported |
| 1%
| dexvert
| Swift 3D 3D Graphic (poly/swift3D3DGraphic)
| ext
| Unsupported |
| 1%
| dexvert
| Boost Text serialization (other/boostTextSerialization)
| ext
| Unsupported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| Mailbox text, 1st line "From owner-cypherpunks@toad.com Sun Feb 12 18:49:24 1995", ASCII text, with CRLF line terminators
| default
| |
| 100%
| TrID
| E-Mail message (Var. 2)
| default
| |
| 100%
| checkBytes
| Printable ASCII
| default
| |
| 100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
| 100%
| siegfried
| x-fmt/111 Plain Text File
| default
| |
| 100%
| gt2
| Textdatei (DOS)
| default
| |
| 100%
| detectItEasy
| Format: plain text[CRLF]
| default (weak)
| |
| 100%
| xdgMime
| application/mbox
| default
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 46 72 6f 6d 20 6f 77 6e | 65 72 2d 63 79 70 68 65 |From own|er-cyphe|
|00000010| 72 70 75 6e 6b 73 40 74 | 6f 61 64 2e 63 6f 6d 20 |rpunks@t|oad.com |
|00000020| 20 53 75 6e 20 46 65 62 | 20 31 32 20 31 38 3a 34 | Sun Feb| 12 18:4|
|00000030| 39 3a 32 34 20 31 39 39 | 35 0d 0a 46 72 6f 6d 3a |9:24 199|5..From:|
|00000040| 20 73 63 68 6e 65 69 65 | 72 40 63 68 69 6e 65 74 | schneie|r@chinet|
|00000050| 2e 63 68 69 6e 65 74 2e | 63 6f 6d 0d 0a 53 75 62 |.chinet.|com..Sub|
|00000060| 6a 65 63 74 3a 20 46 61 | 63 74 6f 72 69 6e 67 20 |ject: Fa|ctoring |
|00000070| 2d 20 53 74 61 74 65 20 | 6f 66 20 74 68 65 20 41 |- State |of the A|
|00000080| 72 74 20 61 6e 64 20 50 | 72 65 64 69 63 74 69 6f |rt and P|redictio|
|00000090| 6e 73 0d 0a 54 6f 3a 20 | 63 79 70 68 65 72 70 75 |ns..To: |cypherpu|
|000000a0| 6e 6b 73 40 74 6f 61 64 | 2e 63 6f 6d 0d 0a 44 61 |nks@toad|.com..Da|
|000000b0| 74 65 3a 20 53 75 6e 2c | 20 31 32 20 46 65 62 20 |te: Sun,| 12 Feb |
|000000c0| 31 39 39 35 20 31 37 3a | 32 39 3a 35 33 20 2d 30 |1995 17:|29:53 -0|
|000000d0| 36 30 30 20 28 43 53 54 | 29 0d 0a 0d 0a 28 28 43 |600 (CST|)....((C|
|000000e0| 6f 6d 6d 65 6e 74 73 20 | 61 72 65 20 61 70 70 72 |omments |are appr|
|000000f0| 65 63 69 61 74 65 64 2e | 20 20 2d 42 72 75 63 65 |eciated.| -Bruce|
|00000100| 29 29 0d 0a 0d 0a 0d 0a | 46 61 63 74 6f 72 69 6e |))......|Factorin|
|00000110| 67 20 6c 61 72 67 65 20 | 6e 75 6d 62 65 72 73 20 |g large |numbers |
|00000120| 69 73 20 68 61 72 64 2e | 20 20 55 6e 66 6f 72 74 |is hard.| Unfort|
|00000130| 75 6e 61 74 65 6c 79 20 | 66 6f 72 20 61 6c 67 6f |unately |for algo|
|00000140| 72 69 74 68 6d 0d 0a 64 | 65 73 69 67 6e 65 72 73 |rithm..d|esigners|
|00000150| 2c 20 69 74 20 69 73 20 | 67 65 74 74 69 6e 67 20 |, it is |getting |
|00000160| 65 61 73 69 65 72 2e 20 | 20 45 76 65 6e 20 77 6f |easier. | Even wo|
|00000170| 72 73 65 2c 20 69 74 20 | 69 73 20 67 65 74 74 69 |rse, it |is getti|
|00000180| 6e 67 0d 0a 65 61 73 69 | 65 72 20 66 61 73 74 65 |ng..easi|er faste|
|00000190| 72 20 74 68 61 6e 20 6d | 61 74 68 65 6d 61 74 69 |r than m|athemati|
|000001a0| 63 69 61 6e 73 20 65 78 | 70 65 63 74 65 64 2e 20 |cians ex|pected. |
|000001b0| 20 49 6e 20 31 39 37 36 | 20 52 69 63 68 61 72 64 | In 1976| Richard|
|000001c0| 20 47 75 79 0d 0a 77 72 | 6f 74 65 3a 20 22 49 20 | Guy..wr|ote: "I |
|000001d0| 73 68 61 6c 6c 20 62 65 | 20 73 75 72 70 72 69 73 |shall be| surpris|
|000001e0| 65 64 20 69 66 20 61 6e | 79 6f 6e 65 20 72 65 67 |ed if an|yone reg|
|000001f0| 75 6c 61 72 6c 79 20 66 | 61 63 74 6f 72 73 20 6e |ularly f|actors n|
|00000200| 75 6d 62 65 72 73 0d 0a | 6f 66 20 73 69 7a 65 20 |umbers..|of size |
|00000210| 31 30 5e 38 30 20 77 69 | 74 68 6f 75 74 20 73 70 |10^80 wi|thout sp|
|00000220| 65 63 69 61 6c 20 66 6f | 72 6d 20 64 75 72 69 6e |ecial fo|rm durin|
|00000230| 67 20 74 68 65 20 70 72 | 65 73 65 6e 74 20 63 65 |g the pr|esent ce|
|00000240| 6e 74 75 72 79 2e 22 20 | 0d 0a 49 6e 20 31 39 37 |ntury." |..In 197|
|00000250| 37 20 52 6f 6e 20 52 69 | 76 65 73 74 20 73 61 69 |7 Ron Ri|vest sai|
|00000260| 64 20 74 68 61 74 20 66 | 61 63 74 6f 72 69 6e 67 |d that f|actoring|
|00000270| 20 61 20 31 32 35 2d 64 | 69 67 69 74 20 6e 75 6d | a 125-d|igit num|
|00000280| 62 65 72 20 77 6f 75 6c | 64 0d 0a 74 61 6b 65 20 |ber woul|d..take |
|00000290| 34 30 20 71 75 61 64 72 | 69 6c 6c 69 6f 6e 20 79 |40 quadr|illion y|
|000002a0| 65 61 72 73 2e 20 20 49 | 6e 20 31 39 39 34 20 61 |ears. I|n 1994 a|
|000002b0| 20 31 32 39 2d 64 69 67 | 69 74 20 6e 75 6d 62 65 | 129-dig|it numbe|
|000002c0| 72 20 77 61 73 0d 0a 66 | 61 63 74 6f 72 65 64 2e |r was..f|actored.|
|000002d0| 20 20 49 66 20 74 68 65 | 72 65 20 69 73 20 61 6e | If the|re is an|
|000002e0| 79 20 6c 65 73 73 6f 6e | 20 69 6e 20 61 6c 6c 20 |y lesson| in all |
|000002f0| 74 68 69 73 2c 20 69 74 | 20 69 73 20 74 68 61 74 |this, it| is that|
|00000300| 20 6d 61 6b 69 6e 67 0d | 0a 70 72 65 64 69 63 74 | making.|.predict|
|00000310| 69 6f 6e 73 20 69 73 20 | 66 6f 6f 6c 69 73 68 2e |ions is |foolish.|
|00000320| 0d 0a 0d 0a 54 61 62 6c | 65 20 31 20 73 68 6f 77 |....Tabl|e 1 show|
|00000330| 73 20 66 61 63 74 6f 72 | 69 6e 67 20 72 65 63 6f |s factor|ing reco|
|00000340| 72 64 73 20 6f 76 65 72 | 20 74 68 65 20 70 61 73 |rds over| the pas|
|00000350| 74 20 64 6f 7a 65 6e 20 | 79 65 61 72 73 2e 20 20 |t dozen |years. |
|00000360| 54 68 65 0d 0a 66 61 73 | 74 65 73 74 20 66 61 63 |The..fas|test fac|
|00000370| 74 6f 72 69 6e 67 20 61 | 6c 67 6f 72 69 74 68 6d |toring a|lgorithm|
|00000380| 20 64 75 72 69 6e 67 20 | 74 68 65 20 74 69 6d 65 | during |the time|
|00000390| 20 77 61 73 20 74 68 65 | 20 71 75 61 64 72 61 74 | was the| quadrat|
|000003a0| 69 63 0d 0a 73 69 65 76 | 65 2e 0d 0a 0d 0a 20 20 |ic..siev|e..... |
|000003b0| 20 20 20 20 20 20 20 54 | 61 62 6c 65 20 31 3a 20 | T|able 1: |
|000003c0| 20 46 61 63 74 6f 72 69 | 6e 67 20 55 73 69 6e 67 | Factori|ng Using|
|000003d0| 20 74 68 65 20 51 75 61 | 64 72 61 74 69 63 20 53 | the Qua|dratic S|
|000003e0| 69 65 76 65 0d 0a 0d 0a | 20 20 20 20 20 20 20 20 |ieve....| |
|000003f0| 20 79 65 61 72 20 20 20 | 20 20 23 20 6f 66 20 64 | year | # of d|
|00000400| 65 63 69 6d 61 6c 20 20 | 20 20 20 20 20 20 20 20 |ecimal | |
|00000410| 20 20 20 20 20 68 6f 77 | 20 6d 61 6e 79 20 74 69 | how| many ti|
|00000420| 6d 65 73 20 68 61 72 64 | 65 72 20 74 6f 0d 0a 20 |mes hard|er to.. |
|00000430| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000440| 20 64 69 67 69 74 73 20 | 66 61 63 74 6f 72 65 64 | digits |factored|
|00000450| 20 20 20 20 20 20 20 20 | 20 20 20 20 66 61 63 74 | | fact|
|00000460| 6f 72 20 61 20 35 31 32 | 2d 62 69 74 20 6e 75 6d |or a 512|-bit num|
|00000470| 62 65 72 0d 0a 20 20 20 | 20 20 20 20 20 20 31 39 |ber.. | 19|
|00000480| 38 33 20 20 20 20 20 37 | 31 20 20 20 20 20 20 20 |83 7|1 |
|00000490| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000004a0| 20 20 3e 20 32 30 20 6d | 69 6c 6c 69 6f 6e 0d 0a | > 20 m|illion..|
|000004b0| 20 20 20 20 20 20 20 20 | 20 31 39 38 35 20 20 20 | | 1985 |
|000004c0| 20 20 38 30 20 20 20 20 | 20 20 20 20 20 20 20 20 | 80 | |
|000004d0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 3e 20 32 | | > 2|
|000004e0| 20 6d 69 6c 6c 69 6f 6e | 0d 0a 20 20 20 20 20 20 | million|.. |
|000004f0| 20 20 20 31 39 38 38 20 | 20 20 20 20 39 30 20 20 | 1988 | 90 |
|00000500| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000510| 20 20 20 20 20 20 20 32 | 35 30 2c 30 30 30 0d 0a | 2|50,000..|
|00000520| 20 20 20 20 20 20 20 20 | 20 31 39 38 39 20 20 20 | | 1989 |
|00000530| 20 20 31 30 30 20 20 20 | 20 20 20 20 20 20 20 20 | 100 | |
|00000540| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 33 30 2c | | 30,|
|00000550| 30 30 30 0d 0a 20 20 20 | 20 20 20 20 20 20 31 39 |000.. | 19|
|00000560| 39 33 20 20 20 20 20 31 | 32 30 20 20 20 20 20 20 |93 1|20 |
|00000570| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000580| 20 20 35 30 30 0d 0a 20 | 20 20 20 20 20 20 20 20 | 500.. | |
|00000590| 31 39 39 34 20 20 20 20 | 20 31 32 39 20 20 20 20 |1994 | 129 |
|000005a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|000005b0| 20 20 20 20 31 30 30 0d | 0a 0d 0a 54 68 65 73 65 | 100.|...These|
|000005c0| 20 6e 75 6d 62 65 72 73 | 20 61 72 65 20 70 72 65 | numbers| are pre|
|000005d0| 74 74 79 20 66 72 69 67 | 68 74 65 6e 69 6e 67 2e |tty frig|htening.|
|000005e0| 20 20 54 6f 64 61 79 20 | 69 74 20 69 73 20 6e 6f | Today |it is no|
|000005f0| 74 20 75 6e 63 6f 6d 6d | 6f 6e 0d 0a 74 6f 20 73 |t uncomm|on..to s|
|00000600| 65 65 20 35 31 32 2d 62 | 69 74 20 6e 75 6d 62 65 |ee 512-b|it numbe|
|00000610| 72 73 20 75 73 65 64 20 | 69 6e 20 6f 70 65 72 61 |rs used |in opera|
|00000620| 74 69 6f 6e 61 6c 20 73 | 79 73 74 65 6d 73 2e 20 |tional s|ystems. |
|00000630| 20 46 61 63 74 6f 72 69 | 6e 67 0d 0a 74 68 65 6d | Factori|ng..them|
|00000640| 2c 20 61 6e 64 20 74 68 | 65 72 65 62 79 20 63 6f |, and th|ereby co|
|00000650| 6d 70 6c 65 74 65 6c 79 | 20 63 6f 6d 70 72 6f 6d |mpletely| comprom|
|00000660| 69 73 69 6e 67 20 74 68 | 65 69 72 20 73 65 63 75 |ising th|eir secu|
|00000670| 72 69 74 79 2c 20 69 73 | 20 77 65 6c 6c 0d 0a 69 |rity, is| well..i|
|00000680| 6e 20 74 68 65 20 72 61 | 6e 67 65 20 6f 66 20 70 |n the ra|nge of p|
|00000690| 6f 73 73 69 62 69 6c 69 | 74 79 3a 20 41 20 77 65 |ossibili|ty: A we|
|000006a0| 65 6b 65 6e 64 2d 6c 6f | 6e 67 20 77 6f 72 6d 20 |ekend-lo|ng worm |
|000006b0| 6f 6e 20 74 68 65 20 49 | 6e 74 65 72 6e 65 74 0d |on the I|nternet.|
|000006c0| 0a 63 6f 75 6c 64 20 64 | 6f 20 69 74 2e 0d 0a 0d |.could d|o it....|
|000006d0| 0a 43 6f 6d 70 75 74 69 | 6e 67 20 70 6f 77 65 72 |.Computi|ng power|
|000006e0| 20 69 73 20 67 65 6e 65 | 72 61 6c 6c 79 20 6d 65 | is gene|rally me|
|000006f0| 61 73 75 72 65 64 20 69 | 6e 20 6d 69 70 73 2d 79 |asured i|n mips-y|
|00000700| 65 61 72 73 3a 20 61 20 | 6f 6e 65 2d 0d 0a 6d 69 |ears: a |one-..mi|
|00000710| 6c 6c 69 6f 6e 2d 69 6e | 73 74 72 75 63 74 69 6f |llion-in|structio|
|00000720| 6e 2d 70 65 72 2d 73 65 | 63 6f 6e 64 20 63 6f 6d |n-per-se|cond com|
|00000730| 70 75 74 65 72 20 72 75 | 6e 6e 69 6e 67 20 66 6f |puter ru|nning fo|
|00000740| 72 20 6f 6e 65 20 79 65 | 61 72 2c 20 6f 72 0d 0a |r one ye|ar, or..|
|00000750| 61 62 6f 75 74 20 33 2a | 31 30 5e 31 33 20 69 6e |about 3*|10^13 in|
|00000760| 73 74 72 75 63 74 69 6f | 6e 73 2e 20 20 42 79 20 |structio|ns. By |
|00000770| 63 6f 6e 76 65 6e 74 69 | 6f 6e 2c 20 61 20 31 20 |conventi|on, a 1 |
|00000780| 6d 69 70 73 20 6d 61 63 | 68 69 6e 65 20 69 73 0d |mips mac|hine is.|
|00000790| 0a 65 71 75 69 76 61 6c | 65 6e 74 20 74 6f 20 74 |.equival|ent to t|
|000007a0| 68 65 20 44 45 43 20 56 | 41 58 20 31 31 2f 37 38 |he DEC V|AX 11/78|
|000007b0| 30 2e 20 20 48 65 6e 63 | 65 2c 20 61 20 6d 69 70 |0. Henc|e, a mip|
|000007c0| 73 2d 79 65 61 72 20 69 | 73 20 61 20 56 41 58 0d |s-year i|s a VAX.|
|000007d0| 0a 31 31 2f 37 38 30 20 | 72 75 6e 6e 69 6e 67 20 |.11/780 |running |
|000007e0| 66 6f 72 20 61 20 79 65 | 61 72 2c 20 6f 72 20 74 |for a ye|ar, or t|
|000007f0| 68 65 20 65 71 75 69 76 | 61 6c 65 6e 74 2e 0d 0a |he equiv|alent...|
|00000800| 0d 0a 54 68 65 20 31 39 | 38 33 20 66 61 63 74 6f |..The 19|83 facto|
|00000810| 72 69 7a 61 74 69 6f 6e | 20 6f 66 20 61 20 37 31 |rization| of a 71|
|00000820| 2d 64 69 67 69 74 20 6e | 75 6d 62 65 72 20 72 65 |-digit n|umber re|
|00000830| 71 75 69 72 65 64 20 30 | 2e 31 20 6d 69 70 73 2d |quired 0|.1 mips-|
|00000840| 0d 0a 79 65 61 72 73 3b | 20 74 68 65 20 31 39 39 |..years;| the 199|
|00000850| 34 20 66 61 63 74 6f 72 | 69 7a 61 74 69 6f 6e 20 |4 factor|ization |
|00000860| 6f 66 20 61 20 31 32 39 | 2d 64 69 67 69 74 20 6e |of a 129|-digit n|
|00000870| 75 6d 62 65 72 20 72 65 | 71 75 69 72 65 64 0d 0a |umber re|quired..|
|00000880| 35 30 30 30 2e 20 20 54 | 68 69 73 20 64 72 61 6d |5000. T|his dram|
|00000890| 61 74 69 63 20 69 6e 63 | 72 65 61 73 65 20 69 6e |atic inc|rease in|
|000008a0| 20 63 6f 6d 70 75 74 69 | 6e 67 20 70 6f 77 65 72 | computi|ng power|
|000008b0| 20 72 65 73 75 6c 74 65 | 64 20 6c 61 72 67 65 6c | resulte|d largel|
|000008c0| 79 0d 0a 66 72 6f 6d 20 | 74 68 65 20 69 6e 74 72 |y..from |the intr|
|000008d0| 6f 64 75 63 74 69 6f 6e | 20 6f 66 20 64 69 73 74 |oduction| of dist|
|000008e0| 72 69 62 75 74 65 64 20 | 63 6f 6d 70 75 74 69 6e |ributed |computin|
|000008f0| 67 2c 20 75 73 69 6e 67 | 20 74 68 65 20 69 64 6c |g, using| the idl|
|00000900| 65 0d 0a 74 69 6d 65 20 | 6f 6e 20 61 20 6e 65 74 |e..time |on a net|
|00000910| 77 6f 72 6b 20 6f 66 20 | 77 6f 72 6b 73 74 61 74 |work of |workstat|
|00000920| 69 6f 6e 73 2e 20 20 54 | 68 65 20 31 39 38 33 20 |ions. T|he 1983 |
|00000930| 66 61 63 74 6f 72 69 7a | 61 74 69 6f 6e 20 75 73 |factoriz|ation us|
|00000940| 65 64 0d 0a 39 2e 35 20 | 43 50 55 20 68 6f 75 72 |ed..9.5 |CPU hour|
|00000950| 73 20 6f 6e 20 61 20 73 | 69 6e 67 6c 65 20 43 72 |s on a s|ingle Cr|
|00000960| 61 79 20 58 2d 4d 50 3b | 20 74 68 65 20 31 39 39 |ay X-MP;| the 199|
|00000970| 34 20 66 61 63 74 6f 72 | 69 7a 61 74 69 6f 6e 20 |4 factor|ization |
|00000980| 75 73 65 64 0d 0a 74 68 | 65 20 69 64 6c 65 20 74 |used..th|e idle t|
|00000990| 69 6d 65 20 6f 6e 20 31 | 36 30 30 20 63 6f 6d 70 |ime on 1|600 comp|
|000009a0| 75 74 65 72 73 20 61 72 | 6f 75 6e 64 20 74 68 65 |uters ar|ound the|
|000009b0| 20 77 6f 72 6c 64 20 66 | 6f 72 20 61 62 6f 75 74 | world f|or about|
|000009c0| 20 38 0d 0a 6d 6f 6e 74 | 68 73 2e 20 20 4d 6f 64 | 8..mont|hs. Mod|
|000009d0| 65 72 6e 20 66 61 63 74 | 6f 72 69 6e 67 20 6d 65 |ern fact|oring me|
|000009e0| 74 68 6f 64 73 20 6c 65 | 6e 64 20 74 68 65 6d 73 |thods le|nd thems|
|000009f0| 65 6c 76 65 73 20 74 6f | 20 74 68 69 73 20 6b 69 |elves to| this ki|
|00000a00| 6e 64 20 6f 66 0d 0a 64 | 69 73 74 72 69 62 75 74 |nd of..d|istribut|
|00000a10| 65 64 20 69 6d 70 6c 65 | 6d 65 6e 74 61 74 69 6f |ed imple|mentatio|
|00000a20| 6e 2e 0d 0a 0d 0a 54 68 | 65 20 70 69 63 74 75 72 |n.....Th|e pictur|
|00000a30| 65 20 67 65 74 73 20 65 | 76 65 6e 20 77 6f 72 73 |e gets e|ven wors|
|00000a40| 65 2e 20 20 41 20 6e 65 | 77 20 66 61 63 74 6f 72 |e. A ne|w factor|
|00000a50| 69 6e 67 20 61 6c 67 6f | 72 69 74 68 6d 20 68 61 |ing algo|rithm ha|
|00000a60| 73 20 74 61 6b 65 6e 0d | 0a 6f 76 65 72 20 66 72 |s taken.|.over fr|
|00000a70| 6f 6d 20 74 68 65 20 71 | 75 61 64 72 61 74 69 63 |om the q|uadratic|
|00000a80| 20 73 69 65 76 65 3a 20 | 74 68 65 20 67 65 6e 65 | sieve: |the gene|
|00000a90| 72 61 6c 20 6e 75 6d 62 | 65 72 20 66 69 65 6c 64 |ral numb|er field|
|00000aa0| 20 73 69 65 76 65 2e 20 | 0d 0a 49 6e 20 31 39 38 | sieve. |..In 198|
|00000ab0| 39 20 6d 61 74 68 65 6d | 61 74 69 63 69 61 6e 73 |9 mathem|aticians|
|00000ac0| 20 77 6f 75 6c 64 20 68 | 61 76 65 20 74 6f 6c 64 | would h|ave told|
|00000ad0| 20 79 6f 75 20 74 68 61 | 74 20 74 68 65 20 67 65 | you tha|t the ge|
|00000ae0| 6e 65 72 61 6c 0d 0a 6e | 75 6d 62 65 72 20 66 69 |neral..n|umber fi|
|00000af0| 65 6c 64 20 73 69 65 76 | 65 20 77 6f 75 6c 64 20 |eld siev|e would |
|00000b00| 6e 65 76 65 72 20 62 65 | 20 70 72 61 63 74 69 63 |never be| practic|
|00000b10| 61 6c 2e 20 20 49 6e 20 | 31 39 39 32 20 74 68 65 |al. In |1992 the|
|00000b20| 79 20 77 6f 75 6c 64 0d | 0a 68 61 76 65 20 74 6f |y would.|.have to|
|00000b30| 6c 64 20 79 6f 75 20 74 | 68 61 74 20 69 74 20 77 |ld you t|hat it w|
|00000b40| 61 73 20 70 72 61 63 74 | 69 63 61 6c 2c 20 62 75 |as pract|ical, bu|
|00000b50| 74 20 6f 6e 6c 79 20 66 | 61 73 74 65 72 20 74 68 |t only f|aster th|
|00000b60| 61 6e 20 74 68 65 0d 0a | 71 75 61 64 72 61 74 69 |an the..|quadrati|
|00000b70| 63 20 73 69 65 76 65 20 | 66 6f 72 20 6e 75 6d 62 |c sieve |for numb|
|00000b80| 65 72 73 20 67 72 65 61 | 74 65 72 20 74 68 61 6e |ers grea|ter than|
|00000b90| 20 31 33 30 2d 31 35 30 | 20 64 69 67 69 74 73 20 | 130-150| digits |
|00000ba0| 6f 72 20 73 6f 2e 20 0d | 0a 54 6f 64 61 79 20 69 |or so. .|.Today i|
|00000bb0| 74 20 69 73 20 6b 6e 6f | 77 6e 20 74 6f 20 62 65 |t is kno|wn to be|
|00000bc0| 20 66 61 73 74 65 72 20 | 74 68 61 6e 20 74 68 65 | faster |than the|
|00000bd0| 20 71 75 61 64 72 61 74 | 69 63 20 73 69 65 76 65 | quadrat|ic sieve|
|00000be0| 20 66 6f 72 0d 0a 6e 75 | 6d 62 65 72 73 20 77 65 | for..nu|mbers we|
|00000bf0| 6c 6c 20 62 65 6c 6f 77 | 20 31 31 36 20 64 69 67 |ll below| 116 dig|
|00000c00| 69 74 73 2e 20 20 54 68 | 65 20 67 65 6e 65 72 61 |its. Th|e genera|
|00000c10| 6c 20 6e 75 6d 62 65 72 | 20 66 69 65 6c 64 20 73 |l number| field s|
|00000c20| 69 65 76 65 0d 0a 63 61 | 6e 20 66 61 63 74 6f 72 |ieve..ca|n factor|
|00000c30| 20 61 20 35 31 32 2d 62 | 69 74 20 6e 75 6d 62 65 | a 512-b|it numbe|
|00000c40| 72 20 6f 76 65 72 20 31 | 30 20 74 69 6d 65 73 20 |r over 1|0 times |
|00000c50| 66 61 73 74 65 72 20 74 | 68 61 6e 20 74 68 65 0d |faster t|han the.|
|00000c60| 0a 71 75 61 64 72 61 74 | 69 63 20 73 69 65 76 65 |.quadrat|ic sieve|
|00000c70| 2e 20 20 54 68 65 20 61 | 6c 67 6f 72 69 74 68 6d |. The a|lgorithm|
|00000c80| 20 77 6f 75 6c 64 20 72 | 65 71 75 69 72 65 20 6c | would r|equire l|
|00000c90| 65 73 73 20 74 68 61 6e | 20 61 20 79 65 61 72 20 |ess than| a year |
|00000ca0| 74 6f 0d 0a 72 75 6e 20 | 6f 6e 20 61 6e 20 31 38 |to..run |on an 18|
|00000cb0| 30 30 2d 6e 6f 64 65 20 | 49 6e 74 65 6c 20 50 61 |00-node |Intel Pa|
|00000cc0| 72 61 67 6f 6e 2e 20 20 | 54 61 62 6c 65 20 32 20 |ragon. |Table 2 |
|00000cd0| 67 69 76 65 73 20 74 68 | 65 20 6e 75 6d 62 65 72 |gives th|e number|
|00000ce0| 20 6f 66 0d 0a 6d 69 70 | 73 2d 79 65 61 72 73 20 | of..mip|s-years |
|00000cf0| 72 65 71 75 69 72 65 64 | 20 74 6f 20 66 61 63 74 |required| to fact|
|00000d00| 6f 72 20 6e 75 6d 62 65 | 72 73 20 6f 66 20 64 69 |or numbe|rs of di|
|00000d10| 66 66 65 72 65 6e 74 20 | 73 69 7a 65 73 2c 20 67 |fferent |sizes, g|
|00000d20| 69 76 65 6e 0d 0a 63 75 | 72 72 65 6e 74 20 69 6d |iven..cu|rrent im|
|00000d30| 70 6c 65 6d 65 6e 74 61 | 74 69 6f 6e 73 20 6f 66 |plementa|tions of|
|00000d40| 20 74 68 65 20 67 65 6e | 65 72 61 6c 20 6e 75 6d | the gen|eral num|
|00000d50| 62 65 72 20 66 69 65 6c | 64 20 73 69 65 76 65 2e |ber fiel|d sieve.|
|00000d60| 0d 0a 0d 0a 20 20 20 20 | 20 20 20 20 20 54 61 62 |.... | Tab|
|00000d70| 6c 65 20 32 3a 20 46 61 | 63 74 6f 72 69 6e 67 20 |le 2: Fa|ctoring |
|00000d80| 55 73 69 6e 67 20 74 68 | 65 20 47 65 6e 65 72 61 |Using th|e Genera|
|00000d90| 6c 20 4e 75 6d 62 65 72 | 20 46 69 65 6c 64 20 53 |l Number| Field S|
|00000da0| 69 65 76 65 0d 0a 0d 0a | 20 20 20 20 20 20 20 20 |ieve....| |
|00000db0| 20 23 20 6f 66 20 62 69 | 74 73 20 20 20 20 20 20 | # of bi|ts |
|00000dc0| 20 20 20 6d 69 70 73 2d | 79 65 61 72 73 20 72 65 | mips-|years re|
|00000dd0| 71 75 69 72 65 64 20 74 | 6f 20 66 61 63 74 6f 72 |quired t|o factor|
|00000de0| 0d 0a 0d 0a 20 20 20 20 | 20 20 20 20 20 35 31 32 |.... | 512|
|00000df0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 33 | | 3|
|00000e00| 30 2c 30 30 30 0d 0a 20 | 20 20 20 20 20 20 20 20 |0,000.. | |
|00000e10| 37 36 38 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |768 | |
|00000e20| 20 20 32 2a 31 30 5e 38 | 0d 0a 20 20 20 20 20 20 | 2*10^8|.. |
|00000e30| 20 20 20 31 30 32 34 20 | 20 20 20 20 20 20 20 20 | 1024 | |
|00000e40| 20 20 20 20 20 33 2a 31 | 30 5e 31 31 0d 0a 20 20 | 3*1|0^11.. |
|00000e50| 20 20 20 20 20 20 20 31 | 32 38 30 20 20 20 20 20 | 1|280 |
|00000e60| 20 20 20 20 20 20 20 20 | 20 31 2a 31 30 5e 31 34 | | 1*10^14|
|00000e70| 0d 0a 20 20 20 20 20 20 | 20 20 20 31 35 33 36 20 |.. | 1536 |
|00000e80| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 33 2a 31 | | 3*1|
|00000e90| 30 5e 31 36 0d 0a 20 20 | 20 20 20 20 20 20 20 32 |0^16.. | 2|
|00000ea0| 30 34 38 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |048 | |
|00000eb0| 20 33 2a 31 30 5e 32 30 | 0d 0a 0d 0a 41 6e 64 20 | 3*10^20|....And |
|00000ec0| 74 68 65 20 67 65 6e 65 | 72 61 6c 20 6e 75 6d 62 |the gene|ral numb|
|00000ed0| 65 72 20 66 69 65 6c 64 | 20 73 69 65 76 65 20 69 |er field| sieve i|
|00000ee0| 73 20 73 74 69 6c 6c 20 | 67 65 74 74 69 6e 67 20 |s still |getting |
|00000ef0| 66 61 73 74 65 72 2e 20 | 0d 0a 4d 61 74 68 65 6d |faster. |..Mathem|
|00000f00| 61 74 69 63 69 61 6e 73 | 20 6b 65 65 70 20 63 6f |aticians| keep co|
|00000f10| 6d 69 6e 67 20 75 70 20 | 77 69 74 68 20 6e 65 77 |ming up |with new|
|00000f20| 20 74 72 69 63 6b 73 2c | 20 6e 65 77 20 6f 70 74 | tricks,| new opt|
|00000f30| 69 6d 69 7a 61 74 69 6f | 6e 73 2c 0d 0a 6e 65 77 |imizatio|ns,..new|
|00000f40| 20 74 65 63 68 6e 69 71 | 75 65 73 2e 20 20 54 68 | techniq|ues. Th|
|00000f50| 65 72 65 27 73 20 6e 6f | 20 72 65 61 73 6f 6e 20 |ere's no| reason |
|00000f60| 74 6f 20 74 68 69 6e 6b | 20 74 68 69 73 20 74 72 |to think| this tr|
|00000f70| 65 6e 64 20 77 6f 6e 27 | 74 0d 0a 63 6f 6e 74 69 |end won'|t..conti|
|00000f80| 6e 75 65 2e 20 20 41 20 | 72 65 6c 61 74 65 64 20 |nue. A |related |
|00000f90| 61 6c 67 6f 72 69 74 68 | 6d 2c 20 74 68 65 20 73 |algorith|m, the s|
|00000fa0| 70 65 63 69 61 6c 20 6e | 75 6d 62 65 72 20 66 69 |pecial n|umber fi|
|00000fb0| 65 6c 64 20 73 69 65 76 | 65 2c 0d 0a 63 61 6e 20 |eld siev|e,..can |
|00000fc0| 61 6c 72 65 61 64 79 20 | 66 61 63 74 6f 72 20 6e |already |factor n|
|00000fd0| 75 6d 62 65 72 73 20 6f | 66 20 61 20 63 65 72 74 |umbers o|f a cert|
|00000fe0| 61 69 6e 20 73 70 65 63 | 69 61 6c 69 7a 65 64 20 |ain spec|ialized |
|00000ff0| 66 6f 72 6d 2d 2d 6e 75 | 6d 62 65 72 73 0d 0a 6e |form--nu|mbers..n|
|00001000| 6f 74 20 67 65 6e 65 72 | 61 6c 6c 79 20 75 73 65 |ot gener|ally use|
|00001010| 64 20 66 6f 72 20 63 72 | 79 70 74 6f 67 72 61 70 |d for cr|yptograp|
|00001020| 68 79 2d 2d 6d 75 73 74 | 20 66 61 73 74 65 72 20 |hy--must| faster |
|00001030| 74 68 61 6e 20 74 68 65 | 20 67 65 6e 65 72 61 6c |than the| general|
|00001040| 0d 0a 6e 75 6d 62 65 72 | 20 66 69 65 6c 64 20 73 |..number| field s|
|00001050| 69 65 76 65 20 63 61 6e | 20 66 61 63 74 6f 72 20 |ieve can| factor |
|00001060| 67 65 6e 65 72 61 6c 20 | 6e 75 6d 62 65 72 73 20 |general |numbers |
|00001070| 6f 66 20 74 68 65 20 73 | 61 6d 65 20 73 69 7a 65 |of the s|ame size|
|00001080| 2e 20 0d 0a 49 74 20 69 | 73 20 6e 6f 74 20 75 6e |. ..It i|s not un|
|00001090| 72 65 61 73 6f 6e 61 62 | 6c 65 20 74 6f 20 61 73 |reasonab|le to as|
|000010a0| 73 75 6d 65 20 74 68 61 | 74 20 74 68 65 20 67 65 |sume tha|t the ge|
|000010b0| 6e 65 72 61 6c 20 6e 75 | 6d 62 65 72 20 66 69 65 |neral nu|mber fie|
|000010c0| 6c 64 0d 0a 73 69 65 76 | 65 20 63 61 6e 20 62 65 |ld..siev|e can be|
|000010d0| 20 6f 70 74 69 6d 69 7a | 65 64 20 74 6f 20 72 75 | optimiz|ed to ru|
|000010e0| 6e 20 74 68 69 73 20 66 | 61 73 74 3b 20 69 74 20 |n this f|ast; it |
|000010f0| 69 73 20 70 6f 73 73 69 | 62 6c 65 20 74 68 61 74 |is possi|ble that|
|00001100| 20 74 68 65 0d 0a 4e 53 | 41 20 61 6c 72 65 61 64 | the..NS|A alread|
|00001110| 79 20 6b 6e 6f 77 73 20 | 68 6f 77 20 74 6f 20 64 |y knows |how to d|
|00001120| 6f 20 74 68 69 73 2e 20 | 20 54 61 62 6c 65 20 33 |o this. | Table 3|
|00001130| 20 67 69 76 65 73 20 74 | 68 65 20 6e 75 6d 62 65 | gives t|he numbe|
|00001140| 72 20 6f 66 0d 0a 6d 69 | 70 73 2d 79 65 61 72 73 |r of..mi|ps-years|
|00001150| 20 72 65 71 75 69 72 65 | 64 20 66 6f 72 20 74 68 | require|d for th|
|00001160| 65 20 73 70 65 63 69 61 | 6c 20 6e 75 6d 62 65 72 |e specia|l number|
|00001170| 20 66 69 65 6c 64 20 73 | 69 65 76 65 20 74 6f 20 | field s|ieve to |
|00001180| 66 61 63 74 6f 72 0d 0a | 6e 75 6d 62 65 72 73 20 |factor..|numbers |
|00001190| 6f 66 20 64 69 66 66 65 | 72 65 6e 74 20 6c 65 6e |of diffe|rent len|
|000011a0| 67 74 68 73 2e 0d 0a 0d | 0a 20 20 20 20 20 20 20 |gths....|. |
|000011b0| 20 20 54 61 62 6c 65 20 | 33 3a 20 46 61 63 74 6f | Table |3: Facto|
|000011c0| 72 69 6e 67 20 55 73 69 | 6e 67 20 74 68 65 20 53 |ring Usi|ng the S|
|000011d0| 70 65 63 69 61 6c 20 4e | 75 6d 62 65 72 20 46 69 |pecial N|umber Fi|
|000011e0| 65 6c 64 20 53 69 65 76 | 65 0d 0a 0d 0a 20 20 20 |eld Siev|e.... |
|000011f0| 20 20 20 20 20 20 23 20 | 6f 66 20 62 69 74 73 20 | # |of bits |
|00001200| 20 20 20 20 20 20 20 20 | 6d 69 70 73 2d 79 65 61 | |mips-yea|
|00001210| 72 73 20 72 65 71 75 69 | 72 65 64 20 74 6f 20 66 |rs requi|red to f|
|00001220| 61 63 74 6f 72 0d 0a 0d | 0a 20 20 20 20 20 20 20 |actor...|. |
|00001230| 20 20 35 31 32 20 20 20 | 20 20 20 20 20 20 20 20 | 512 | |
|00001240| 20 20 20 20 3c 20 32 30 | 30 0d 0a 20 20 20 20 20 | < 20|0.. |
|00001250| 20 20 20 20 37 36 38 20 | 20 20 20 20 20 20 20 20 | 768 | |
|00001260| 20 20 20 20 20 20 31 30 | 30 2c 30 30 30 0d 0a 20 | 10|0,000.. |
|00001270| 20 20 20 20 20 20 20 20 | 31 30 32 34 20 20 20 20 | |1024 |
|00001280| 20 20 20 20 20 20 20 20 | 20 20 33 2a 31 30 5e 37 | | 3*10^7|
|00001290| 0d 0a 20 20 20 20 20 20 | 20 20 20 31 32 38 30 20 |.. | 1280 |
|000012a0| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 33 2a 31 | | 3*1|
|000012b0| 30 5e 39 0d 0a 20 20 20 | 20 20 20 20 20 20 31 35 |0^9.. | 15|
|000012c0| 33 36 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |36 | |
|000012d0| 32 2a 31 30 5e 31 31 0d | 0a 20 20 20 20 20 20 20 |2*10^11.|. |
|000012e0| 20 20 32 30 34 38 20 20 | 20 20 20 20 20 20 20 20 | 2048 | |
|000012f0| 20 20 20 20 34 2a 31 30 | 5e 31 34 0d 0a 0d 0a 41 | 4*10|^14....A|
|00001300| 74 20 61 20 45 75 72 6f | 70 65 61 6e 20 49 6e 73 |t a Euro|pean Ins|
|00001310| 74 69 74 75 74 65 20 66 | 6f 72 20 53 79 73 74 65 |titute f|or Syste|
|00001320| 6d 20 53 65 63 75 72 69 | 74 79 20 77 6f 72 6b 73 |m Securi|ty works|
|00001330| 68 6f 70 20 69 6e 20 31 | 39 39 32 2c 20 74 68 65 |hop in 1|992, the|
|00001340| 0d 0a 70 61 72 74 69 63 | 69 70 61 6e 74 73 20 61 |..partic|ipants a|
|00001350| 67 72 65 65 64 20 74 68 | 61 74 20 61 20 31 30 32 |greed th|at a 102|
|00001360| 34 2d 62 69 74 20 6d 6f | 64 75 6c 75 73 20 73 68 |4-bit mo|dulus sh|
|00001370| 6f 75 6c 64 20 62 65 20 | 73 75 66 66 69 63 69 65 |ould be |sufficie|
|00001380| 6e 74 0d 0a 66 6f 72 20 | 6c 6f 6e 67 2d 74 65 72 |nt..for |long-ter|
|00001390| 6d 20 73 65 63 72 65 74 | 73 20 74 68 72 6f 75 67 |m secret|s throug|
|000013a0| 68 20 32 30 30 32 2e 20 | 20 48 6f 77 65 76 65 72 |h 2002. | However|
|000013b0| 2c 20 74 68 65 79 20 77 | 61 72 6e 65 64 3a 20 0d |, they w|arned: .|
|000013c0| 0a 22 41 6c 74 68 6f 75 | 67 68 20 74 68 65 20 70 |."Althou|gh the p|
|000013d0| 61 72 74 69 63 69 70 61 | 6e 74 73 20 6f 66 20 74 |articipa|nts of t|
|000013e0| 68 69 73 20 77 6f 72 6b | 73 68 6f 70 20 66 65 65 |his work|shop fee|
|000013f0| 6c 20 62 65 73 74 20 71 | 75 61 6c 69 66 69 65 64 |l best q|ualified|
|00001400| 0d 0a 69 6e 20 74 68 65 | 69 72 20 72 65 73 70 65 |..in the|ir respe|
|00001410| 63 74 69 76 65 20 61 72 | 65 61 73 2c 20 74 68 69 |ctive ar|eas, thi|
|00001420| 73 20 73 74 61 74 65 6d | 65 6e 74 20 5b 77 69 74 |s statem|ent [wit|
|00001430| 68 20 72 65 73 70 65 63 | 74 20 74 6f 0d 0a 6c 61 |h respec|t to..la|
|00001440| 73 74 69 6e 67 20 73 65 | 63 75 72 69 74 79 5d 20 |sting se|curity] |
|00001450| 73 68 6f 75 6c 64 20 62 | 65 20 74 61 6b 65 6e 20 |should b|e taken |
|00001460| 77 69 74 68 20 63 61 75 | 74 69 6f 6e 2e 22 20 20 |with cau|tion." |
|00001470| 54 68 69 73 20 69 73 20 | 67 6f 6f 64 0d 0a 61 64 |This is |good..ad|
|00001480| 76 69 63 65 2e 0d 0a 0d | 0a 54 68 65 20 77 69 73 |vice....|.The wis|
|00001490| 65 20 63 72 79 70 74 6f | 67 72 61 70 68 65 72 20 |e crypto|grapher |
|000014a0| 69 73 20 75 6c 74 72 61 | 2d 63 6f 6e 73 65 72 76 |is ultra|-conserv|
|000014b0| 61 74 69 76 65 20 77 68 | 65 6e 20 63 68 6f 6f 73 |ative wh|en choos|
|000014c0| 69 6e 67 0d 0a 70 75 62 | 6c 69 63 2d 6b 65 79 20 |ing..pub|lic-key |
|000014d0| 6b 65 79 20 6c 65 6e 67 | 74 68 73 2e 20 20 54 6f |key leng|ths. To|
|000014e0| 20 64 65 74 65 72 6d 69 | 6e 65 20 68 6f 77 20 6c | determi|ne how l|
|000014f0| 6f 6e 67 20 61 20 6b 65 | 79 20 79 6f 75 20 6e 65 |ong a ke|y you ne|
|00001500| 65 64 0d 0a 72 65 71 75 | 69 72 65 73 20 79 6f 75 |ed..requ|ires you|
|00001510| 20 74 6f 20 6c 6f 6f 6b | 20 61 74 20 62 6f 74 68 | to look| at both|
|00001520| 20 74 68 65 20 69 6e 74 | 65 6e 64 65 64 20 73 65 | the int|ended se|
|00001530| 63 75 72 69 74 79 20 61 | 6e 64 20 6c 69 66 65 74 |curity a|nd lifet|
|00001540| 69 6d 65 0d 0a 6f 66 20 | 74 68 65 20 6b 65 79 2c |ime..of |the key,|
|00001550| 20 61 6e 64 20 74 68 65 | 20 63 75 72 72 65 6e 74 | and the| current|
|00001560| 20 73 74 61 74 65 2d 6f | 66 2d 74 68 65 2d 61 72 | state-o|f-the-ar|
|00001570| 74 20 6f 66 20 66 61 63 | 74 6f 72 69 6e 67 2e 20 |t of fac|toring. |
|00001580| 20 54 6f 64 61 79 0d 0a | 79 6f 75 20 6e 65 65 64 | Today..|you need|
|00001590| 20 61 20 31 30 32 34 2d | 62 69 74 20 6e 75 6d 62 | a 1024-|bit numb|
|000015a0| 65 72 20 74 6f 20 67 65 | 74 20 74 68 65 20 6c 65 |er to ge|t the le|
|000015b0| 76 65 6c 20 6f 66 20 73 | 65 63 75 72 69 74 79 20 |vel of s|ecurity |
|000015c0| 79 6f 75 20 67 6f 74 0d | 0a 66 72 6f 6d 20 61 20 |you got.|.from a |
|000015d0| 35 31 32 2d 62 69 74 20 | 6e 75 6d 62 65 72 20 69 |512-bit |number i|
|000015e0| 6e 20 74 68 65 20 65 61 | 72 6c 79 20 31 39 38 30 |n the ea|rly 1980|
|000015f0| 73 2e 20 20 49 66 20 79 | 6f 75 20 77 61 6e 74 20 |s. If y|ou want |
|00001600| 79 6f 75 72 20 6b 65 79 | 73 0d 0a 74 6f 20 72 65 |your key|s..to re|
|00001610| 6d 61 69 6e 20 73 65 63 | 75 72 65 20 66 6f 72 20 |main sec|ure for |
|00001620| 32 30 20 79 65 61 72 73 | 2c 20 31 30 32 34 20 62 |20 years|, 1024 b|
|00001630| 69 74 73 20 69 73 20 6c | 69 6b 65 6c 79 20 74 6f |its is l|ikely to|
|00001640| 6f 20 73 68 6f 72 74 2e | 0d 0a 0d 0a 45 76 65 6e |o short.|....Even|
|00001650| 20 69 66 20 79 6f 75 72 | 20 70 61 72 74 69 63 75 | if your| particu|
|00001660| 6c 61 72 20 73 65 63 72 | 65 74 73 20 61 72 65 6e |lar secr|ets aren|
|00001670| 27 74 20 77 6f 72 74 68 | 20 74 68 65 20 65 66 66 |'t worth| the eff|
|00001680| 6f 72 74 20 72 65 71 75 | 69 72 65 64 0d 0a 74 6f |ort requ|ired..to|
|00001690| 20 66 61 63 74 6f 72 20 | 79 6f 75 72 20 6d 6f 64 | factor |your mod|
|000016a0| 75 6c 75 73 2c 20 79 6f | 75 20 6d 61 79 20 62 65 |ulus, yo|u may be|
|000016b0| 20 61 74 20 72 69 73 6b | 2e 20 20 49 6d 61 67 69 | at risk|. Imagi|
|000016c0| 6e 65 20 61 6e 20 61 75 | 74 6f 6d 61 74 69 63 0d |ne an au|tomatic.|
|000016d0| 0a 62 61 6e 6b 69 6e 67 | 20 73 79 73 74 65 6d 20 |.banking| system |
|000016e0| 74 68 61 74 20 75 73 65 | 73 20 52 53 41 20 66 6f |that use|s RSA fo|
|000016f0| 72 20 73 65 63 75 72 69 | 74 79 2e 20 20 4d 61 6c |r securi|ty. Mal|
|00001700| 6c 6f 72 79 20 63 61 6e | 20 73 74 61 6e 64 20 75 |lory can| stand u|
|00001710| 70 0d 0a 69 6e 20 63 6f | 75 72 74 20 61 6e 64 20 |p..in co|urt and |
|00001720| 73 61 79 3a 20 22 44 69 | 64 20 79 6f 75 20 72 65 |say: "Di|d you re|
|00001730| 61 64 20 69 6e 20 74 68 | 65 20 6e 65 77 73 70 61 |ad in th|e newspa|
|00001740| 70 65 72 20 69 6e 20 31 | 39 39 34 20 74 68 61 74 |per in 1|994 that|
|00001750| 0d 0a 52 53 41 2d 31 32 | 39 20 77 61 73 20 62 72 |..RSA-12|9 was br|
|00001760| 6f 6b 65 6e 2c 20 61 6e | 64 20 74 68 61 74 20 35 |oken, an|d that 5|
|00001770| 31 32 2d 62 69 74 20 6e | 75 6d 62 65 72 73 20 63 |12-bit n|umbers c|
|00001780| 61 6e 20 62 65 20 66 61 | 63 74 6f 72 65 64 20 62 |an be fa|ctored b|
|00001790| 79 0d 0a 61 6e 79 20 6f | 72 67 61 6e 69 7a 61 74 |y..any o|rganizat|
|000017a0| 69 6f 6e 20 77 69 6c 6c | 69 6e 67 20 74 6f 20 73 |ion will|ing to s|
|000017b0| 70 65 6e 64 20 61 20 66 | 65 77 20 6d 69 6c 6c 69 |pend a f|ew milli|
|000017c0| 6f 6e 20 64 6f 6c 6c 61 | 72 73 20 61 6e 64 20 77 |on dolla|rs and w|
|000017d0| 61 69 74 0d 0a 61 20 66 | 65 77 20 6d 6f 6e 74 68 |ait..a f|ew month|
|000017e0| 73 3f 20 20 4d 79 20 62 | 61 6e 6b 20 75 73 65 73 |s? My b|ank uses|
|000017f0| 20 35 31 32 2d 62 69 74 | 20 6e 75 6d 62 65 72 73 | 512-bit| numbers|
|00001800| 20 66 6f 72 20 73 65 63 | 75 72 69 74 79 2c 20 61 | for sec|urity, a|
|00001810| 6e 64 20 62 79 0d 0a 74 | 68 65 20 77 61 79 20 49 |nd by..t|he way I|
|00001820| 20 64 69 64 6e 27 74 20 | 6d 61 6b 65 20 74 68 65 | didn't |make the|
|00001830| 73 65 20 73 65 76 65 6e | 20 77 69 74 68 64 72 61 |se seven| withdra|
|00001840| 77 61 6c 73 2e 22 20 20 | 45 76 65 6e 20 69 66 20 |wals." |Even if |
|00001850| 4d 61 6c 6c 6f 72 79 0d | 0a 69 73 20 6c 79 69 6e |Mallory.|.is lyin|
|00001860| 67 2c 20 74 68 65 20 6a | 75 64 67 65 20 77 69 6c |g, the j|udge wil|
|00001870| 6c 20 70 72 6f 62 61 62 | 6c 79 20 70 75 74 20 74 |l probab|ly put t|
|00001880| 68 65 20 6f 6e 75 73 20 | 6f 6e 20 74 68 65 20 62 |he onus |on the b|
|00001890| 61 6e 6b 20 74 6f 0d 0a | 70 72 6f 76 65 20 69 74 |ank to..|prove it|
|000018a0| 2e 0d 0a 0d 0a 45 61 72 | 6c 69 65 72 20 49 20 63 |.....Ear|lier I c|
|000018b0| 61 6c 6c 65 64 20 6d 61 | 6b 69 6e 67 20 70 72 65 |alled ma|king pre|
|000018c0| 64 69 63 74 69 6f 6e 73 | 20 66 6f 6f 6c 69 73 68 |dictions| foolish|
|000018d0| 2e 20 20 4e 6f 77 20 49 | 20 61 6d 20 61 62 6f 75 |. Now I| am abou|
|000018e0| 74 20 74 6f 0d 0a 6d 61 | 6b 65 20 73 6f 6d 65 2e |t to..ma|ke some.|
|000018f0| 20 20 54 61 62 6c 65 20 | 34 20 67 69 76 65 73 20 | Table |4 gives |
|00001900| 6d 79 20 72 65 63 6f 6d | 6d 65 6e 64 61 74 69 6f |my recom|mendatio|
|00001910| 6e 73 20 66 6f 72 20 70 | 75 62 6c 69 63 2d 6b 65 |ns for p|ublic-ke|
|00001920| 79 0d 0a 6c 65 6e 67 74 | 68 73 2c 20 64 65 70 65 |y..lengt|hs, depe|
|00001930| 6e 64 69 6e 67 20 6f 6e | 20 68 6f 77 20 6c 6f 6e |nding on| how lon|
|00001940| 67 20 79 6f 75 20 72 65 | 71 75 69 72 65 20 74 68 |g you re|quire th|
|00001950| 65 20 6b 65 79 20 74 6f | 20 62 65 20 73 65 63 75 |e key to| be secu|
|00001960| 72 65 2e 20 0d 0a 54 68 | 65 72 65 20 61 72 65 20 |re. ..Th|ere are |
|00001970| 74 68 72 65 65 20 6b 65 | 79 20 6c 65 6e 67 74 68 |three ke|y length|
|00001980| 73 20 66 6f 72 20 65 61 | 63 68 20 79 65 61 72 2c |s for ea|ch year,|
|00001990| 20 6f 6e 65 20 73 65 63 | 75 72 65 20 61 67 61 69 | one sec|ure agai|
|000019a0| 6e 73 74 20 61 6e 0d 0a | 69 6e 64 69 76 69 64 75 |nst an..|individu|
|000019b0| 61 6c 2c 20 6f 6e 65 20 | 73 65 63 75 72 65 20 61 |al, one |secure a|
|000019c0| 67 61 69 6e 73 74 20 61 | 20 6d 61 6a 6f 72 20 63 |gainst a| major c|
|000019d0| 6f 72 70 6f 72 61 74 69 | 6f 6e 2c 20 61 6e 64 20 |orporati|on, and |
|000019e0| 74 68 65 20 74 68 69 72 | 64 0d 0a 73 65 63 75 72 |the thir|d..secur|
|000019f0| 65 20 61 67 61 69 6e 73 | 74 20 61 20 6d 61 6a 6f |e agains|t a majo|
|00001a00| 72 20 67 6f 76 65 72 6e | 6d 65 6e 74 2e 0d 0a 0d |r govern|ment....|
|00001a10| 0a 48 65 72 65 20 61 72 | 65 20 73 6f 6d 65 20 61 |.Here ar|e some a|
|00001a20| 73 73 75 6d 70 74 69 6f | 6e 73 20 66 72 6f 6d 20 |ssumptio|ns from |
|00001a30| 74 68 65 20 6d 61 74 68 | 65 6d 61 74 69 63 69 61 |the math|ematicia|
|00001a40| 6e 73 20 77 68 6f 20 66 | 61 63 74 6f 72 65 64 0d |ns who f|actored.|
|00001a50| 0a 52 53 41 2d 31 32 39 | 3a 0d 0a 0d 0a 20 20 20 |.RSA-129|:.... |
|00001a60| 20 20 20 20 20 20 57 65 | 20 62 65 6c 69 65 76 65 | We| believe|
|00001a70| 20 74 68 61 74 20 77 65 | 20 63 6f 75 6c 64 20 61 | that we| could a|
|00001a80| 63 71 75 69 72 65 20 31 | 30 30 20 74 68 6f 75 73 |cquire 1|00 thous|
|00001a90| 61 6e 64 20 6d 61 63 68 | 69 6e 65 73 0d 0a 20 20 |and mach|ines.. |
|00001aa0| 20 20 20 20 20 20 20 77 | 69 74 68 6f 75 74 20 73 | w|ithout s|
|00001ab0| 75 70 65 72 68 75 6d 61 | 6e 20 6f 72 20 75 6e 65 |uperhuma|n or une|
|00001ac0| 74 68 69 63 61 6c 20 65 | 66 66 6f 72 74 73 2e 20 |thical e|fforts. |
|00001ad0| 20 54 68 61 74 20 69 73 | 2c 20 77 65 20 77 6f 75 | That is|, we wou|
|00001ae0| 6c 64 0d 0a 20 20 20 20 | 20 20 20 20 20 6e 6f 74 |ld.. | not|
|00001af0| 20 73 65 74 20 66 72 65 | 65 20 61 6e 20 49 6e 74 | set fre|e an Int|
|00001b00| 65 72 6e 65 74 20 77 6f | 72 6d 20 6f 72 20 76 69 |ernet wo|rm or vi|
|00001b10| 72 75 73 20 74 6f 20 66 | 69 6e 64 20 72 65 73 6f |rus to f|ind reso|
|00001b20| 75 72 63 65 73 20 66 6f | 72 0d 0a 20 20 20 20 20 |urces fo|r.. |
|00001b30| 20 20 20 20 75 73 2e 20 | 20 4d 61 6e 79 20 6f 72 | us. | Many or|
|00001b40| 67 61 6e 69 7a 61 74 69 | 6f 6e 73 20 68 61 76 65 |ganizati|ons have|
|00001b50| 20 73 65 76 65 72 61 6c | 20 74 68 6f 75 73 61 6e | several| thousan|
|00001b60| 64 20 6d 61 63 68 69 6e | 65 73 20 65 61 63 68 0d |d machin|es each.|
|00001b70| 0a 20 20 20 20 20 20 20 | 20 20 6f 6e 20 74 68 65 |. | on the|
|00001b80| 20 6e 65 74 2e 20 20 4d | 61 6b 69 6e 67 20 75 73 | net. M|aking us|
|00001b90| 65 20 6f 66 20 74 68 65 | 69 72 20 66 61 63 69 6c |e of the|ir facil|
|00001ba0| 69 74 69 65 73 20 77 6f | 75 6c 64 20 72 65 71 75 |ities wo|uld requ|
|00001bb0| 69 72 65 0d 0a 20 20 20 | 20 20 20 20 20 20 73 6b |ire.. | sk|
|00001bc0| 69 6c 6c 66 75 6c 20 64 | 69 70 6c 6f 6d 61 63 79 |illful d|iplomacy|
|00001bd0| 2c 20 62 75 74 20 73 68 | 6f 75 6c 64 20 6e 6f 74 |, but sh|ould not|
|00001be0| 20 62 65 20 69 6d 70 6f | 73 73 69 62 6c 65 2e 20 | be impo|ssible. |
|00001bf0| 20 41 73 73 75 6d 69 6e | 67 0d 0a 20 20 20 20 20 | Assumin|g.. |
|00001c00| 20 20 20 20 74 68 65 20 | 35 20 6d 69 70 73 20 61 | the |5 mips a|
|00001c10| 76 65 72 61 67 65 20 70 | 6f 77 65 72 2c 20 61 6e |verage p|ower, an|
|00001c20| 64 20 6f 6e 65 20 79 65 | 61 72 20 65 6c 61 70 73 |d one ye|ar elaps|
|00001c30| 65 64 20 74 69 6d 65 2c | 20 69 74 20 69 73 0d 0a |ed time,| it is..|
|00001c40| 20 20 20 20 20 20 20 20 | 20 6e 6f 74 20 74 6f 6f | | not too|
|00001c50| 20 75 6e 72 65 61 73 6f | 6e 61 62 6c 65 20 74 6f | unreaso|nable to|
|00001c60| 20 65 6d 62 61 72 6b 20 | 6f 6e 20 61 20 70 72 6f | embark |on a pro|
|00001c70| 6a 65 63 74 20 77 68 69 | 63 68 20 77 6f 75 6c 64 |ject whi|ch would|
|00001c80| 0d 0a 20 20 20 20 20 20 | 20 20 20 72 65 71 75 69 |.. | requi|
|00001c90| 72 65 20 68 61 6c 66 20 | 61 20 6d 69 6c 6c 69 6f |re half |a millio|
|00001ca0| 6e 20 6d 69 70 73 20 79 | 65 61 72 73 2e 0d 0a 0d |n mips y|ears....|
|00001cb0| 0a 54 68 65 20 70 72 6f | 6a 65 63 74 20 74 6f 20 |.The pro|ject to |
|00001cc0| 66 61 63 74 6f 72 20 74 | 68 65 20 31 32 39 2d 64 |factor t|he 129-d|
|00001cd0| 69 67 69 74 20 6e 75 6d | 62 65 72 20 68 61 72 6e |igit num|ber harn|
|00001ce0| 65 73 73 65 73 20 61 6e | 20 65 73 74 69 6d 61 74 |esses an| estimat|
|00001cf0| 65 64 0d 0a 30 2e 30 33 | 25 20 6f 66 20 74 68 65 |ed..0.03|% of the|
|00001d00| 20 74 6f 74 61 6c 20 63 | 6f 6d 70 75 74 69 6e 67 | total c|omputing|
|00001d10| 20 70 6f 77 65 72 20 6f | 66 20 74 68 65 20 49 6e | power o|f the In|
|00001d20| 74 65 72 6e 65 74 2c 20 | 61 6e 64 20 74 68 65 79 |ternet, |and they|
|00001d30| 0d 0a 64 69 64 6e 27 74 | 20 65 76 65 6e 20 74 72 |..didn't| even tr|
|00001d40| 79 20 76 65 72 79 20 68 | 61 72 64 2e 20 20 49 74 |y very h|ard. It|
|00001d50| 20 69 73 6e 27 74 20 75 | 6e 72 65 61 73 6f 6e 61 | isn't u|nreasona|
|00001d60| 62 6c 65 20 74 6f 20 61 | 73 73 75 6d 65 20 74 68 |ble to a|ssume th|
|00001d70| 61 74 0d 0a 61 20 77 65 | 6c 6c 2d 70 75 62 6c 69 |at..a we|ll-publi|
|00001d80| 63 69 7a 65 64 20 70 72 | 6f 6a 65 63 74 20 63 61 |cized pr|oject ca|
|00001d90| 6e 20 68 61 72 6e 65 73 | 73 20 30 2e 31 25 20 6f |n harnes|s 0.1% o|
|00001da0| 66 20 74 68 65 20 77 6f | 72 6c 64 27 73 0d 0a 63 |f the wo|rld's..c|
|00001db0| 6f 6d 70 75 74 69 6e 67 | 20 70 6f 77 65 72 20 66 |omputing| power f|
|00001dc0| 6f 72 20 61 20 79 65 61 | 72 2e 0d 0a 0d 0a 41 73 |or a yea|r.....As|
|00001dd0| 73 75 6d 65 20 61 20 64 | 65 64 69 63 61 74 65 64 |sume a d|edicated|
|00001de0| 20 63 72 79 70 74 61 6e | 61 6c 79 73 74 20 63 61 | cryptan|alyst ca|
|00001df0| 6e 20 67 65 74 20 68 69 | 73 20 68 61 6e 64 73 20 |n get hi|s hands |
|00001e00| 6f 6e 20 31 30 2c 30 30 | 30 20 6d 69 70 73 2d 0d |on 10,00|0 mips-.|
|00001e10| 0a 79 65 61 72 73 2c 20 | 61 20 6c 61 72 67 65 20 |.years, |a large |
|00001e20| 63 6f 72 70 6f 72 61 74 | 69 6f 6e 20 63 61 6e 20 |corporat|ion can |
|00001e30| 67 65 74 20 31 30 5e 37 | 20 6d 69 70 73 2d 79 65 |get 10^7| mips-ye|
|00001e40| 61 72 73 2c 20 61 6e 64 | 20 74 68 61 74 20 61 0d |ars, and| that a.|
|00001e50| 0a 6c 61 72 67 65 20 67 | 6f 76 65 72 6e 6d 65 6e |.large g|overnmen|
|00001e60| 74 20 63 61 6e 20 67 65 | 74 20 31 30 5e 39 20 6d |t can ge|t 10^9 m|
|00001e70| 69 70 73 2d 79 65 61 72 | 73 2e 20 20 41 6c 73 6f |ips-year|s. Also|
|00001e80| 20 61 73 73 75 6d 65 20 | 74 68 61 74 0d 0a 63 6f | assume |that..co|
|00001e90| 6d 70 75 74 69 6e 67 20 | 70 6f 77 65 72 20 77 69 |mputing |power wi|
|00001ea0| 6c 6c 20 69 6e 63 72 65 | 61 73 65 20 62 79 20 61 |ll incre|ase by a|
|00001eb0| 20 66 61 63 74 6f 72 20 | 6f 66 20 74 65 6e 20 65 | factor |of ten e|
|00001ec0| 76 65 72 79 20 66 69 76 | 65 0d 0a 79 65 61 72 73 |very fiv|e..years|
|00001ed0| 2e 20 20 41 6e 64 20 66 | 69 6e 61 6c 6c 79 2c 20 |. And f|inally, |
|00001ee0| 61 73 73 75 6d 65 20 74 | 68 61 74 20 61 64 76 61 |assume t|hat adva|
|00001ef0| 6e 63 65 73 20 69 6e 20 | 66 61 63 74 6f 72 69 6e |nces in |factorin|
|00001f00| 67 0d 0a 6d 61 74 68 65 | 6d 61 74 69 63 73 20 61 |g..mathe|matics a|
|00001f10| 6c 6c 6f 77 73 20 75 73 | 20 74 6f 20 66 61 63 74 |llows us| to fact|
|00001f20| 6f 72 20 67 65 6e 65 72 | 61 6c 20 6e 75 6d 62 65 |or gener|al numbe|
|00001f30| 72 73 20 61 74 20 74 68 | 65 20 73 70 65 65 64 73 |rs at th|e speeds|
|00001f40| 20 6f 66 0d 0a 74 68 65 | 20 73 70 65 63 69 61 6c | of..the| special|
|00001f50| 20 6e 75 6d 62 65 72 20 | 66 69 65 6c 64 20 73 69 | number |field si|
|00001f60| 65 76 65 2e 20 20 54 61 | 62 6c 65 20 34 20 72 65 |eve. Ta|ble 4 re|
|00001f70| 63 6f 6d 6d 65 6e 64 73 | 20 64 69 66 66 65 72 65 |commends| differe|
|00001f80| 6e 74 20 6b 65 79 0d 0a | 6c 65 6e 67 74 68 73 20 |nt key..|lengths |
|00001f90| 66 6f 72 20 73 65 63 75 | 72 69 74 79 20 64 75 72 |for secu|rity dur|
|00001fa0| 69 6e 67 20 64 69 66 66 | 65 72 65 6e 74 20 79 65 |ing diff|erent ye|
|00001fb0| 61 72 73 2e 0d 0a 0d 0a | 20 20 20 20 20 20 20 20 |ars.....| |
|00001fc0| 20 54 61 62 6c 65 20 34 | 3a 20 52 65 63 6f 6d 6d | Table 4|: Recomm|
|00001fd0| 65 6e 64 65 64 20 70 75 | 62 6c 69 63 2d 6b 65 79 |ended pu|blic-key|
|00001fe0| 20 6b 65 79 20 6c 65 6e | 67 74 68 73 20 28 69 6e | key len|gths (in|
|00001ff0| 20 62 69 74 73 29 0d 0a | 0d 0a 20 20 20 20 20 20 | bits)..|.. |
|00002000| 20 20 20 59 65 61 72 20 | 20 20 20 20 76 73 2e 20 | Year | vs. |
|00002010| 49 20 20 20 20 20 20 20 | 20 20 20 20 20 20 76 73 |I | vs|
|00002020| 2e 20 43 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |. C | |
|00002030| 76 73 2e 20 47 0d 0a 20 | 20 20 20 20 20 20 20 20 |vs. G.. | |
|00002040| 31 39 39 35 20 20 20 20 | 20 20 37 36 38 20 20 20 |1995 | 768 |
|00002050| 20 20 20 20 20 20 20 20 | 20 20 20 31 32 38 30 20 | | 1280 |
|00002060| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 31 35 33 | | 153|
|00002070| 36 0d 0a 20 20 20 20 20 | 20 20 20 20 32 30 30 30 |6.. | 2000|
|00002080| 20 20 20 20 20 31 30 32 | 34 20 20 20 20 20 20 20 | 102|4 |
|00002090| 20 20 20 20 20 20 20 31 | 32 38 30 20 20 20 20 20 | 1|280 |
|000020a0| 20 20 20 20 20 20 20 20 | 20 31 35 33 36 0d 0a 20 | | 1536.. |
|000020b0| 20 20 20 20 20 20 20 20 | 32 30 30 35 20 20 20 20 | |2005 |
|000020c0| 20 31 32 38 30 20 20 20 | 20 20 20 20 20 20 20 20 | 1280 | |
|000020d0| 20 20 20 31 35 33 36 20 | 20 20 20 20 20 20 20 20 | 1536 | |
|000020e0| 20 20 20 20 20 32 30 34 | 38 0d 0a 20 20 20 20 20 | 204|8.. |
|000020f0| 20 20 20 20 32 30 31 30 | 20 20 20 20 20 31 32 38 | 2010| 128|
|00002100| 30 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 31 |0 | 1|
|00002110| 35 33 36 20 20 20 20 20 | 20 20 20 20 20 20 20 20 |536 | |
|00002120| 20 32 30 34 38 0d 0a 20 | 20 20 20 20 20 20 20 20 | 2048.. | |
|00002130| 32 30 31 35 20 20 20 20 | 20 31 35 33 36 20 20 20 |2015 | 1536 |
|00002140| 20 20 20 20 20 20 20 20 | 20 20 20 32 30 34 38 20 | | 2048 |
|00002150| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 32 30 34 | | 204|
|00002160| 38 0d 0a 0d 0a 52 65 6d | 65 6d 62 65 72 20 74 6f |8....Rem|ember to|
|00002170| 20 74 61 6b 65 20 74 68 | 65 20 76 61 6c 75 65 20 | take th|e value |
|00002180| 6f 66 20 74 68 65 20 6b | 65 79 20 69 6e 74 6f 20 |of the k|ey into |
|00002190| 61 63 63 6f 75 6e 74 2e | 20 20 50 75 62 6c 69 63 |account.| Public|
|000021a0| 20 6b 65 79 73 0d 0a 61 | 72 65 20 6f 66 74 65 6e | keys..a|re often|
|000021b0| 20 75 73 65 64 20 74 6f | 20 73 65 63 75 72 65 20 | used to| secure |
|000021c0| 74 68 69 6e 67 73 20 6f | 66 20 67 72 65 61 74 20 |things o|f great |
|000021d0| 76 61 6c 75 65 20 66 6f | 72 20 61 20 6c 6f 6e 67 |value fo|r a long|
|000021e0| 20 74 69 6d 65 3a 0d 0a | 74 68 65 20 62 61 6e 6b | time:..|the bank|
|000021f0| 27 73 20 6d 61 73 74 65 | 72 20 6b 65 79 20 66 6f |'s maste|r key fo|
|00002200| 72 20 61 20 64 69 67 69 | 74 61 6c 20 63 61 73 68 |r a digi|tal cash|
|00002210| 20 73 79 73 74 65 6d 2c | 20 74 68 65 20 6b 65 79 | system,| the key|
|00002220| 20 74 68 65 0d 0a 67 6f | 76 65 72 6e 6d 65 6e 74 | the..go|vernment|
|00002230| 20 75 73 65 73 20 74 6f | 20 63 65 72 74 69 66 79 | uses to| certify|
|00002240| 20 69 74 73 20 70 61 73 | 73 70 6f 72 74 73 2c 20 | its pas|sports, |
|00002250| 61 20 6e 6f 74 61 72 79 | 20 70 75 62 6c 69 63 27 |a notary| public'|
|00002260| 73 0d 0a 64 69 67 69 74 | 61 6c 20 73 69 67 6e 61 |s..digit|al signa|
|00002270| 74 75 72 65 20 6b 65 79 | 2e 20 20 49 74 20 70 72 |ture key|. It pr|
|00002280| 6f 62 61 62 6c 79 20 69 | 73 6e 27 74 20 77 6f 72 |obably i|sn't wor|
|00002290| 74 68 20 74 68 65 20 65 | 66 66 6f 72 74 20 74 6f |th the e|ffort to|
|000022a0| 0d 0a 73 70 65 6e 64 20 | 6d 6f 6e 74 68 73 20 6f |..spend |months o|
|000022b0| 66 20 63 6f 6d 70 75 74 | 69 6e 67 20 74 69 6d 65 |f comput|ing time|
|000022c0| 20 74 6f 20 62 72 65 61 | 6b 20 61 6e 20 69 6e 64 | to brea|k an ind|
|000022d0| 69 76 69 64 75 61 6c 27 | 73 20 70 72 69 76 61 74 |ividual'|s privat|
|000022e0| 65 0d 0a 6b 65 79 2c 20 | 62 75 74 20 69 66 20 79 |e..key, |but if y|
|000022f0| 6f 75 20 63 61 6e 20 70 | 72 69 6e 74 20 79 6f 75 |ou can p|rint you|
|00002300| 72 20 6f 77 6e 20 6d 6f | 6e 65 79 20 77 69 74 68 |r own mo|ney with|
|00002310| 20 61 20 62 72 6f 6b 65 | 6e 20 6b 65 79 20 74 68 | a broke|n key th|
|00002320| 65 0d 0a 69 64 65 61 20 | 62 65 63 6f 6d 65 73 20 |e..idea |becomes |
|00002330| 6d 6f 72 65 20 61 74 74 | 72 61 63 74 69 76 65 2e |more att|ractive.|
|00002340| 20 20 41 20 31 30 32 34 | 2d 62 69 74 20 6b 65 79 | A 1024|-bit key|
|00002350| 20 69 73 20 6c 6f 6e 67 | 20 65 6e 6f 75 67 68 20 | is long| enough |
|00002360| 74 6f 0d 0a 73 69 67 6e | 20 73 6f 6d 65 74 68 69 |to..sign| somethi|
|00002370| 6e 67 20 74 68 61 74 20 | 77 69 6c 6c 20 62 65 20 |ng that |will be |
|00002380| 76 65 72 69 66 69 65 64 | 20 77 69 74 68 69 6e 20 |verified| within |
|00002390| 74 68 65 20 77 65 65 6b | 2c 20 6f 72 20 6d 6f 6e |the week|, or mon|
|000023a0| 74 68 2c 0d 0a 6f 72 20 | 65 76 65 6e 20 61 20 66 |th,..or |even a f|
|000023b0| 65 77 20 79 65 61 72 73 | 2e 20 20 42 75 74 20 79 |ew years|. But y|
|000023c0| 6f 75 20 64 6f 6e 27 74 | 20 77 61 6e 74 20 74 6f |ou don't| want to|
|000023d0| 20 73 74 61 6e 64 20 75 | 70 20 69 6e 20 63 6f 75 | stand u|p in cou|
|000023e0| 72 74 0d 0a 74 77 65 6e | 74 79 20 79 65 61 72 73 |rt..twen|ty years|
|000023f0| 20 66 72 6f 6d 20 6e 6f | 77 20 77 69 74 68 20 61 | from no|w with a|
|00002400| 20 64 69 67 69 74 61 6c | 6c 79 20 73 69 67 6e 65 | digital|ly signe|
|00002410| 64 20 64 6f 63 75 6d 65 | 6e 74 2c 20 61 6e 64 20 |d docume|nt, and |
|00002420| 68 61 76 65 0d 0a 74 68 | 65 20 6f 70 70 6f 73 69 |have..th|e opposi|
|00002430| 74 69 6f 6e 20 64 65 6d | 6f 6e 73 74 72 61 74 65 |tion dem|onstrate|
|00002440| 20 68 6f 77 20 74 6f 20 | 66 6f 72 67 65 20 64 6f | how to |forge do|
|00002450| 63 75 6d 65 6e 74 73 20 | 77 69 74 68 20 74 68 65 |cuments |with the|
|00002460| 20 73 61 6d 65 0d 0a 73 | 69 67 6e 61 74 75 72 65 | same..s|ignature|
|00002470| 2e 0d 0a 0d 0a 4d 61 6b | 69 6e 67 20 70 72 65 64 |.....Mak|ing pred|
|00002480| 69 63 74 69 6f 6e 73 20 | 62 65 79 6f 6e 64 20 74 |ictions |beyond t|
|00002490| 68 65 20 6e 65 61 72 20 | 66 75 74 75 72 65 20 69 |he near |future i|
|000024a0| 73 20 65 76 65 6e 20 6d | 6f 72 65 20 66 6f 6f 6c |s even m|ore fool|
|000024b0| 69 73 68 2e 20 0d 0a 57 | 68 6f 20 6b 6e 6f 77 73 |ish. ..W|ho knows|
|000024c0| 20 77 68 61 74 20 6b 69 | 6e 64 20 6f 66 20 61 64 | what ki|nd of ad|
|000024d0| 76 61 6e 63 65 73 20 69 | 6e 20 63 6f 6d 70 75 74 |vances i|n comput|
|000024e0| 69 6e 67 2c 20 6e 65 74 | 77 6f 72 6b 69 6e 67 2c |ing, net|working,|
|000024f0| 20 61 6e 64 0d 0a 6d 61 | 74 68 65 6d 61 74 69 63 | and..ma|thematic|
|00002500| 73 20 61 72 65 20 67 6f | 69 6e 67 20 74 6f 20 68 |s are go|ing to h|
|00002510| 61 70 70 65 6e 20 62 79 | 20 32 30 32 30 3f 20 20 |appen by| 2020? |
|00002520| 48 6f 77 65 76 65 72 2c | 20 69 66 20 79 6f 75 20 |However,| if you |
|00002530| 6c 6f 6f 6b 20 61 74 0d | 0a 74 68 65 20 62 72 6f |look at.|.the bro|
|00002540| 61 64 20 70 69 63 74 75 | 72 65 2c 20 69 6e 20 65 |ad pictu|re, in e|
|00002550| 76 65 72 79 20 64 65 63 | 61 64 65 20 77 65 20 63 |very dec|ade we c|
|00002560| 61 6e 20 66 61 63 74 6f | 72 20 6e 75 6d 62 65 72 |an facto|r number|
|00002570| 73 20 74 77 69 63 65 20 | 61 73 0d 0a 6c 6f 6e 67 |s twice |as..long|
|00002580| 20 61 73 20 69 6e 20 74 | 68 65 20 70 72 65 76 69 | as in t|he previ|
|00002590| 6f 75 73 20 64 65 63 61 | 64 65 2e 20 20 54 68 69 |ous deca|de. Thi|
|000025a0| 73 20 6c 65 61 64 73 20 | 74 6f 20 54 61 62 6c 65 |s leads |to Table|
|000025b0| 20 35 2e 0d 0a 0d 0a 20 | 20 20 20 20 20 20 20 20 | 5..... | |
|000025c0| 54 61 62 6c 65 20 35 3a | 20 20 4c 6f 6e 67 2d 72 |Table 5:| Long-r|
|000025d0| 61 6e 67 65 20 66 61 63 | 74 6f 72 69 6e 67 20 70 |ange fac|toring p|
|000025e0| 72 65 64 69 63 74 69 6f | 6e 73 20 0d 0a 0d 0a 20 |redictio|ns .... |
|000025f0| 20 20 20 20 20 20 20 20 | 59 65 61 72 20 20 20 20 | |Year |
|00002600| 20 4b 65 79 20 6c 65 6e | 67 74 68 20 28 69 6e 20 | Key len|gth (in |
|00002610| 62 69 74 73 29 0d 0a 20 | 20 20 20 20 20 20 20 20 |bits).. | |
|00002620| 31 39 39 35 20 20 20 20 | 20 31 30 32 34 0d 0a 20 |1995 | 1024.. |
|00002630| 20 20 20 20 20 20 20 20 | 32 30 30 35 20 20 20 20 | |2005 |
|00002640| 20 32 30 34 38 0d 0a 20 | 20 20 20 20 20 20 20 20 | 2048.. | |
|00002650| 32 30 31 35 20 20 20 20 | 20 34 30 39 36 0d 0a 20 |2015 | 4096.. |
|00002660| 20 20 20 20 20 20 20 20 | 32 30 32 35 20 20 20 20 | |2025 |
|00002670| 20 38 31 39 32 0d 0a 20 | 20 20 20 20 20 20 20 20 | 8192.. | |
|00002680| 32 30 33 35 20 20 20 20 | 20 31 36 2c 33 38 34 0d |2035 | 16,384.|
|00002690| 0a 20 20 20 20 20 20 20 | 20 20 32 30 34 35 20 20 |. | 2045 |
|000026a0| 20 20 20 33 32 2c 37 36 | 38 0d 0a 0d 0a 4e 6f 74 | 32,76|8....Not|
|000026b0| 20 65 76 65 72 79 6f 6e | 65 20 77 69 6c 6c 20 61 | everyon|e will a|
|000026c0| 67 72 65 65 20 77 69 74 | 68 20 6d 79 20 72 65 63 |gree wit|h my rec|
|000026d0| 6f 6d 6d 65 6e 64 61 74 | 69 6f 6e 73 2e 20 20 54 |ommendat|ions. T|
|000026e0| 68 65 20 4e 53 41 20 68 | 61 73 0d 0a 6d 61 6e 64 |he NSA h|as..mand|
|000026f0| 61 74 65 64 20 35 31 32 | 2d 62 69 74 20 74 6f 20 |ated 512|-bit to |
|00002700| 31 30 32 34 2d 62 69 74 | 20 6b 65 79 73 20 66 6f |1024-bit| keys fo|
|00002710| 72 20 74 68 65 69 72 20 | 44 69 67 69 74 61 6c 20 |r their |Digital |
|00002720| 53 69 67 6e 61 74 75 72 | 65 0d 0a 53 74 61 6e 64 |Signatur|e..Stand|
|00002730| 61 72 64 2d 2d 66 61 72 | 20 6c 65 73 73 20 74 68 |ard--far| less th|
|00002740| 61 6e 20 49 20 72 65 63 | 6f 6d 6d 65 6e 64 20 66 |an I rec|ommend f|
|00002750| 6f 72 20 6c 6f 6e 67 2d | 74 65 72 6d 20 73 65 63 |or long-|term sec|
|00002760| 75 72 69 74 79 2e 20 20 | 50 47 50 0d 0a 68 61 73 |urity. |PGP..has|
|00002770| 20 61 20 6d 61 78 69 6d | 75 6d 20 52 53 41 20 6b | a maxim|um RSA k|
|00002780| 65 79 20 6c 65 6e 67 74 | 68 20 6f 66 20 31 32 38 |ey lengt|h of 128|
|00002790| 30 20 62 69 74 73 2e 20 | 20 4c 65 6e 73 74 72 61 |0 bits. | Lenstra|
|000027a0| 2c 20 74 68 65 20 77 6f | 72 6c 64 27 73 0d 0a 6d |, the wo|rld's..m|
|000027b0| 6f 73 74 20 73 75 63 63 | 65 73 73 66 75 6c 20 66 |ost succ|essful f|
|000027c0| 61 63 74 6f 72 65 72 2c | 20 72 65 66 75 73 65 73 |actorer,| refuses|
|000027d0| 20 74 6f 20 6d 61 6b 65 | 20 70 72 65 64 69 63 74 | to make| predict|
|000027e0| 69 6f 6e 73 20 70 61 73 | 74 20 74 65 6e 0d 0a 79 |ions pas|t ten..y|
|000027f0| 65 61 72 73 2e 20 20 41 | 6e 64 20 54 61 62 6c 65 |ears. A|nd Table|
|00002800| 20 36 20 67 69 76 65 73 | 20 52 6f 6e 20 52 69 76 | 6 gives| Ron Riv|
|00002810| 65 73 74 27 73 20 6b 65 | 79 2d 6c 65 6e 67 74 68 |est's ke|y-length|
|00002820| 0d 0a 72 65 63 6f 6d 6d | 65 6e 64 61 74 69 6f 6e |..recomm|endation|
|00002830| 73 2c 20 6f 72 69 67 69 | 6e 61 6c 6c 79 20 6d 61 |s, origi|nally ma|
|00002840| 64 65 20 69 6e 20 31 39 | 39 30 2c 20 77 68 69 63 |de in 19|90, whic|
|00002850| 68 20 49 20 63 6f 6e 73 | 69 64 65 72 20 6d 75 63 |h I cons|ider muc|
|00002860| 68 0d 0a 74 6f 6f 20 6f | 70 74 69 6d 69 73 74 69 |h..too o|ptimisti|
|00002870| 63 2e 20 20 57 68 69 6c | 65 20 68 69 73 20 61 6e |c. Whil|e his an|
|00002880| 61 6c 79 73 69 73 20 6c | 6f 6f 6b 73 20 66 69 6e |alysis l|ooks fin|
|00002890| 65 20 6f 6e 20 70 61 70 | 65 72 2c 20 72 65 63 65 |e on pap|er, rece|
|000028a0| 6e 74 0d 0a 68 69 73 74 | 6f 72 79 20 69 6c 6c 75 |nt..hist|ory illu|
|000028b0| 73 74 72 61 74 65 73 20 | 74 68 61 74 20 73 75 72 |strates |that sur|
|000028c0| 70 72 69 73 65 73 20 72 | 65 67 75 6c 61 72 6c 79 |prises r|egularly|
|000028d0| 20 68 61 70 70 65 6e 2e | 20 20 49 74 20 6d 61 6b | happen.| It mak|
|000028e0| 65 73 0d 0a 73 65 6e 73 | 65 20 74 6f 20 63 68 6f |es..sens|e to cho|
|000028f0| 6f 73 65 20 79 6f 75 72 | 20 6b 65 79 73 20 74 6f |ose your| keys to|
|00002900| 20 62 65 20 72 65 73 69 | 6c 69 65 6e 74 20 61 67 | be resi|lient ag|
|00002910| 61 69 6e 73 74 20 66 75 | 74 75 72 65 0d 0a 73 75 |ainst fu|ture..su|
|00002920| 72 70 72 69 73 65 73 2e | 0d 0a 0d 0a 20 20 20 20 |rprises.|.... |
|00002930| 20 20 20 20 20 54 61 62 | 6c 65 20 36 3a 20 52 69 | Tab|le 6: Ri|
|00002940| 76 65 73 74 27 73 20 4f | 70 74 69 6d 69 73 74 69 |vest's O|ptimisti|
|00002950| 63 20 4b 65 79 2d 4c 65 | 6e 67 74 68 20 52 65 63 |c Key-Le|ngth Rec|
|00002960| 6f 6d 6d 65 6e 64 61 74 | 69 6f 6e 73 20 28 49 6e |ommendat|ions (In|
|00002970| 0d 0a 20 20 20 20 20 20 | 20 20 20 42 69 74 73 29 |.. | Bits)|
|00002980| 0d 0a 0d 0a 20 20 20 20 | 20 20 20 20 20 59 65 61 |.... | Yea|
|00002990| 72 20 20 20 20 20 4c 6f | 77 20 20 20 20 20 20 41 |r Lo|w A|
|000029a0| 76 67 20 20 20 20 20 20 | 48 69 67 68 0d 0a 20 20 |vg |High.. |
|000029b0| 20 20 20 20 20 20 20 31 | 39 39 30 20 20 20 20 20 | 1|990 |
|000029c0| 33 39 38 20 20 20 20 20 | 20 35 31 35 20 20 20 20 |398 | 515 |
|000029d0| 20 20 31 32 38 39 0d 0a | 20 20 20 20 20 20 20 20 | 1289..| |
|000029e0| 20 31 39 39 35 20 20 20 | 20 20 34 30 35 20 20 20 | 1995 | 405 |
|000029f0| 20 20 20 35 34 32 20 20 | 20 20 20 20 31 33 39 39 | 542 | 1399|
|00002a00| 0d 0a 20 20 20 20 20 20 | 20 20 20 32 30 30 30 20 |.. | 2000 |
|00002a10| 20 20 20 20 34 32 32 20 | 20 20 20 20 20 35 37 32 | 422 | 572|
|00002a20| 20 20 20 20 20 20 31 35 | 31 32 0d 0a 20 20 20 20 | 15|12.. |
|00002a30| 20 20 20 20 20 32 30 30 | 35 20 20 20 20 20 34 33 | 200|5 43|
|00002a40| 39 20 20 20 20 20 20 36 | 30 32 20 20 20 20 20 20 |9 6|02 |
|00002a50| 31 36 32 38 0d 0a 20 20 | 20 20 20 20 20 20 20 32 |1628.. | 2|
|00002a60| 30 31 30 20 20 20 20 20 | 34 35 35 20 20 20 20 20 |010 |455 |
|00002a70| 20 36 33 31 20 20 20 20 | 20 20 31 37 35 34 0d 0a | 631 | 1754..|
|00002a80| 20 20 20 20 20 20 20 20 | 20 32 30 31 35 20 20 20 | | 2015 |
|00002a90| 20 20 34 37 32 20 20 20 | 20 20 20 36 36 31 20 20 | 472 | 661 |
|00002aa0| 20 20 20 20 31 38 38 34 | 0d 0a 20 20 20 20 20 20 | 1884|.. |
|00002ab0| 20 20 20 32 30 32 30 20 | 20 20 20 20 34 38 39 20 | 2020 | 489 |
|00002ac0| 20 20 20 20 20 36 37 37 | 20 20 20 20 20 20 32 30 | 677| 20|
|00002ad0| 31 37 0d 0a 0d 0a 20 20 | 20 20 20 20 20 20 20 4c |17.... | L|
|00002ae0| 6f 77 20 65 73 74 69 6d | 61 74 65 73 20 61 73 73 |ow estim|ates ass|
|00002af0| 75 6d 65 20 61 20 62 75 | 64 67 65 74 20 6f 66 20 |ume a bu|dget of |
|00002b00| 24 32 35 2c 30 30 30 2c | 20 74 68 65 20 71 75 61 |$25,000,| the qua|
|00002b10| 64 72 61 74 69 63 0d 0a | 20 20 20 20 20 20 20 20 |dratic..| |
|00002b20| 20 73 69 65 76 65 20 61 | 6c 67 6f 72 69 74 68 6d | sieve a|lgorithm|
|00002b30| 2c 20 61 6e 64 20 61 20 | 74 65 63 68 6e 6f 6c 6f |, and a |technolo|
|00002b40| 67 79 20 61 64 76 61 6e | 63 65 20 6f 66 20 32 30 |gy advan|ce of 20|
|00002b50| 25 20 70 65 72 20 79 65 | 61 72 2e 20 0d 0a 20 20 |% per ye|ar. .. |
|00002b60| 20 20 20 20 20 20 20 41 | 76 65 72 61 67 65 20 65 | A|verage e|
|00002b70| 73 74 69 6d 61 74 65 73 | 20 61 73 73 75 6d 65 20 |stimates| assume |
|00002b80| 61 20 62 75 64 67 65 74 | 20 6f 66 20 24 32 35 20 |a budget| of $25 |
|00002b90| 6d 69 6c 6c 69 6f 6e 2c | 20 74 68 65 0d 0a 20 20 |million,| the.. |
|00002ba0| 20 20 20 20 20 20 20 67 | 65 6e 65 72 61 6c 20 6e | g|eneral n|
|00002bb0| 75 6d 62 65 72 20 66 69 | 65 6c 64 20 73 69 65 76 |umber fi|eld siev|
|00002bc0| 65 20 61 6c 67 6f 72 69 | 74 68 6d 2c 20 61 6e 64 |e algori|thm, and|
|00002bd0| 20 61 20 74 65 63 68 6e | 6f 6c 6f 67 79 0d 0a 20 | a techn|ology.. |
|00002be0| 20 20 20 20 20 20 20 20 | 61 64 76 61 6e 63 65 20 | |advance |
|00002bf0| 6f 66 20 33 33 25 20 70 | 65 72 20 79 65 61 72 2e |of 33% p|er year.|
|00002c00| 20 20 48 69 67 68 20 65 | 73 74 69 6d 61 74 65 73 | High e|stimates|
|00002c10| 20 61 73 73 75 6d 65 20 | 61 20 62 75 64 67 65 74 | assume |a budget|
|00002c20| 20 6f 66 0d 0a 20 20 20 | 20 20 20 20 20 20 24 32 | of.. | $2|
|00002c30| 35 20 62 69 6c 6c 69 6f | 6e 2c 20 61 20 67 65 6e |5 billio|n, a gen|
|00002c40| 65 72 61 6c 20 71 75 61 | 64 72 61 74 69 63 20 73 |eral qua|dratic s|
|00002c50| 69 65 76 65 20 61 6c 67 | 6f 72 69 74 68 6d 20 72 |ieve alg|orithm r|
|00002c60| 75 6e 6e 69 6e 67 20 61 | 74 0d 0a 20 20 20 20 20 |unning a|t.. |
|00002c70| 20 20 20 20 74 68 65 20 | 73 70 65 65 64 20 6f 66 | the |speed of|
|00002c80| 20 74 68 65 20 73 70 65 | 63 69 61 6c 20 6e 75 6d | the spe|cial num|
|00002c90| 62 65 72 20 66 69 65 6c | 64 20 73 69 65 76 65 2c |ber fiel|d sieve,|
|00002ca0| 20 61 6e 64 20 61 0d 0a | 20 20 20 20 20 20 20 20 | and a..| |
|00002cb0| 20 74 65 63 68 6e 6f 6c | 6f 67 79 20 61 64 76 61 | technol|ogy adva|
|00002cc0| 6e 63 65 20 6f 66 20 34 | 35 25 20 70 65 72 20 79 |nce of 4|5% per y|
|00002cd0| 65 61 72 2e 0d 0a 0d 0a | 54 68 65 72 65 20 69 73 |ear.....|There is|
|00002ce0| 20 61 6c 77 61 79 73 20 | 74 68 65 20 70 6f 73 73 | always |the poss|
|00002cf0| 69 62 69 6c 69 74 79 20 | 74 68 61 74 20 61 6e 20 |ibility |that an |
|00002d00| 61 64 76 61 6e 63 65 20 | 69 6e 20 66 61 63 74 6f |advance |in facto|
|00002d10| 72 69 6e 67 20 77 69 6c | 6c 0d 0a 73 75 72 70 72 |ring wil|l..surpr|
|00002d20| 69 73 65 20 6d 65 20 61 | 73 20 77 65 6c 6c 2c 20 |ise me a|s well, |
|00002d30| 62 75 74 20 49 20 74 68 | 69 6e 6b 20 74 68 61 74 |but I th|ink that|
|00002d40| 20 75 6e 6c 69 6b 65 6c | 79 2e 20 20 42 75 74 20 | unlikel|y. But |
|00002d50| 77 68 79 20 74 72 75 73 | 74 0d 0a 6d 65 3f 20 20 |why trus|t..me? |
|00002d60| 49 20 6a 75 73 74 20 70 | 72 6f 76 65 64 20 6d 79 |I just p|roved my|
|00002d70| 20 6f 77 6e 20 66 6f 6f | 6c 69 73 68 6e 65 73 73 | own foo|lishness|
|00002d80| 20 62 79 20 6d 61 6b 69 | 6e 67 20 70 72 65 64 69 | by maki|ng predi|
|00002d90| 63 74 69 6f 6e 73 2e 0d | 0a 0d 0a |ctions..|... |
+--------+-------------------------+-------------------------+--------+--------+
