Prime Numbers & Security

Recent news indicates that the NSA has the ability to break some encryption by way of performing large computations against the pool of commonly used prime numbers used during the Diffie-Hellman key exchange. With this information it is possible to obtain the private key and therefore decrypt all communication between the two parties.

The time required to perform these intense calculations against a single prime number is no small task but it has been estimated that it would cost a few hundred million dollars for a machine that would take approximately one year to break a 1024 bit prime number. So, given a large enough budget and powerful enough computers, both of which are within grasp of the NSA it is possible to perform this kind of attack against the standardized prime number pool.

How do we protect ourselves against such attacks?

The answer to this is rather simple. If most of the internet traffic uses these prime numbers it is advantageous to perform these calculations; but if you generate your own unique prime number, then the cost involved in breaking your prime number becomes infeasible. Especially if you choose a prime number larger than 1024 bits, because the time required grows exponentially. Let's say, for example, you generate a prime number, oh I don't know, 8192 bits long. Then you will be safe for a long, long time.

So, I took the time to generate some. Fifty in fact. Why? Well, prime numbers are revealed during the handshake so they aren't secret, and I had the time (two weeks). So here are 50 8192 bit prime numbers for you to pick and choose from.

Here is an example

-----BEGIN DH PARAMETERS-----
MIIECAKCBAEAz571zbueooaT5C8M3DFkpU6pCgnYkgfYsJt1cFqts1s/NSNIGg+y  
U8XMnl0feFBw1t/RieDvViR8ZeHD2zF3UNlGFe/YqTRuMKT9+jFlqTrQ2Pji0mV+  
EMHZTgKD+Ysr67m7KJ/h88VteQocKjvbu2N8LvgpTPPxw2/jabu/KPAuh88feEK4  
dnH2/Y4UOpVO4X+Tr0ZekzY8Urd3zR8tthmqg+6z5h+vz9G0Bh/Qh2cJwXORC4Qe  
97HFhBQW2Bk1aLfMvMiB0ozW/2S78PWxf5jVGx8ppL98hDkJu4lJuuFrhjuFvt6z  
SUBCoDgoFHZKZHgA0szyVGmmuqKALDY4CtrjlDcjnV/0CBjDPZhCGPp8Y5u8WwVr  
TnuIQRPjW7+2CFQ8ObnBnpcJBSK4sItaGw7wboI2LuMVBMrwLe7VfB7ja1Pxu7mC  
x5KRAYFNGP0Uhbue12v3JpyNKfCTnaDYYmmrmq3rOXRV62AqozwGyh7FLN1UXk8g  
Yv/7rpiXQv/i7U5vppMC6L07kQApxfl5R405owmzKlH3UM3pmXqfnT4h3UgNYx1Q  
DMFkkhnVjxgIcUFtICdd6QonWdfqzo3HdGK0mriIJL3wRfTlLgUeYG3wYwMBR5Ph  
K1sboeeFxacSkpo5868F51MjgYIQfdPCzZvE/WD9Fo8ZTDFSlah3z1VLpRlJG54O  
C1c86eAdMuE5WovhiZigHw7v8Ygn0ooiEgXAMJic0PCGEXKk6RJUG8fEncU65FOa  
1161wCto7oDPvXBbO7ZWf4wfa/3iqN2lLY9gZNo/JKKOYjyEmhcQ6vQEompdgFa7  
7MUt9cp/k60Mf/kaU23L1kEfDr0B3kZ4qRwx5syhe/4LRr9H7B8IwK0NBb6j0/75  
i0tCPuFesaqB2CjteZJyAxhy3ZmX5aSahxPofv8pSgfKSwKlbZgjrll3OPTXZC+Q  
CHqa6tkKvMOjoO4iv+8YkZCbDwB0xL3aykV2ZUVahGy1rohVypZkfrAkZtqVdhxD  
86ATArF9NhN50nogm1qgmXFmMqvbQbAd5W2KnA3jX726Ktv65VDFUyVJnTri4nzI  
a1YpY64eQdoHRkL5v1JjsXcuKLm3ZvrSbMUuuNxG2umkDdV2YUlCujSg2CWMdpv5  
ozdUPSQqyd5pJHSxUk3In0ysN9EUgV/cD0RnvYFJWJgstO/jKWjHe7lfxARCpa/9  
DIY0MievFLTjR5dNNV7V3kgYMZekXxeH/Fi+/mcd4maQtK578WCG/oUI2ejgaYND  
i0Pn94yqQn1HiqB6mH94YIYUBHieY6JGQam9Y0rvBzhJe9lg2/9mjoElbgwL4t/0  
YnTBLbfBTMoZZLl5FPyUdDT8xOwDxMOGEwIBAg==  
-----END DH PARAMETERS-----

    PKCS#3 DH Parameters: (8192 bit)
        prime:
            00:cf:9e:f5:cd:bb:9e:a2:86:93:e4:2f:0c:dc:31:
            64:a5:4e:a9:0a:09:d8:92:07:d8:b0:9b:75:70:5a:
            ad:b3:5b:3f:35:23:48:1a:0f:b2:53:c5:cc:9e:5d:
            1f:78:50:70:d6:df:d1:89:e0:ef:56:24:7c:65:e1:
            c3:db:31:77:50:d9:46:15:ef:d8:a9:34:6e:30:a4:
            fd:fa:31:65:a9:3a:d0:d8:f8:e2:d2:65:7e:10:c1:
            d9:4e:02:83:f9:8b:2b:eb:b9:bb:28:9f:e1:f3:c5:
            6d:79:0a:1c:2a:3b:db:bb:63:7c:2e:f8:29:4c:f3:
            f1:c3:6f:e3:69:bb:bf:28:f0:2e:87:cf:1f:78:42:
            b8:76:71:f6:fd:8e:14:3a:95:4e:e1:7f:93:af:46:
            5e:93:36:3c:52:b7:77:cd:1f:2d:b6:19:aa:83:ee:
            b3:e6:1f:af:cf:d1:b4:06:1f:d0:87:67:09:c1:73:
            91:0b:84:1e:f7:b1:c5:84:14:16:d8:19:35:68:b7:
            cc:bc:c8:81:d2:8c:d6:ff:64:bb:f0:f5:b1:7f:98:
            d5:1b:1f:29:a4:bf:7c:84:39:09:bb:89:49:ba:e1:
            6b:86:3b:85:be:de:b3:49:40:42:a0:38:28:14:76:
            4a:64:78:00:d2:cc:f2:54:69:a6:ba:a2:80:2c:36:
            38:0a:da:e3:94:37:23:9d:5f:f4:08:18:c3:3d:98:
            42:18:fa:7c:63:9b:bc:5b:05:6b:4e:7b:88:41:13:
            e3:5b:bf:b6:08:54:3c:39:b9:c1:9e:97:09:05:22:
            b8:b0:8b:5a:1b:0e:f0:6e:82:36:2e:e3:15:04:ca:
            f0:2d:ee:d5:7c:1e:e3:6b:53:f1:bb:b9:82:c7:92:
            91:01:81:4d:18:fd:14:85:bb:9e:d7:6b:f7:26:9c:
            8d:29:f0:93:9d:a0:d8:62:69:ab:9a:ad:eb:39:74:
            55:eb:60:2a:a3:3c:06:ca:1e:c5:2c:dd:54:5e:4f:
            20:62:ff:fb:ae:98:97:42:ff:e2:ed:4e:6f:a6:93:
            02:e8:bd:3b:91:00:29:c5:f9:79:47:8d:39:a3:09:
            b3:2a:51:f7:50:cd:e9:99:7a:9f:9d:3e:21:dd:48:
            0d:63:1d:50:0c:c1:64:92:19:d5:8f:18:08:71:41:
            6d:20:27:5d:e9:0a:27:59:d7:ea:ce:8d:c7:74:62:
            b4:9a:b8:88:24:bd:f0:45:f4:e5:2e:05:1e:60:6d:
            f0:63:03:01:47:93:e1:2b:5b:1b:a1:e7:85:c5:a7:
            12:92:9a:39:f3:af:05:e7:53:23:81:82:10:7d:d3:
            c2:cd:9b:c4:fd:60:fd:16:8f:19:4c:31:52:95:a8:
            77:cf:55:4b:a5:19:49:1b:9e:0e:0b:57:3c:e9:e0:
            1d:32:e1:39:5a:8b:e1:89:98:a0:1f:0e:ef:f1:88:
            27:d2:8a:22:12:05:c0:30:98:9c:d0:f0:86:11:72:
            a4:e9:12:54:1b:c7:c4:9d:c5:3a:e4:53:9a:d7:5e:
            b5:c0:2b:68:ee:80:cf:bd:70:5b:3b:b6:56:7f:8c:
            1f:6b:fd:e2:a8:dd:a5:2d:8f:60:64:da:3f:24:a2:
            8e:62:3c:84:9a:17:10:ea:f4:04:a2:6a:5d:80:56:
            bb:ec:c5:2d:f5:ca:7f:93:ad:0c:7f:f9:1a:53:6d:
            cb:d6:41:1f:0e:bd:01:de:46:78:a9:1c:31:e6:cc:
            a1:7b:fe:0b:46:bf:47:ec:1f:08:c0:ad:0d:05:be:
            a3:d3:fe:f9:8b:4b:42:3e:e1:5e:b1:aa:81:d8:28:
            ed:79:92:72:03:18:72:dd:99:97:e5:a4:9a:87:13:
            e8:7e:ff:29:4a:07:ca:4b:02:a5:6d:98:23:ae:59:
            77:38:f4:d7:64:2f:90:08:7a:9a:ea:d9:0a:bc:c3:
            a3:a0:ee:22:bf:ef:18:91:90:9b:0f:00:74:c4:bd:
            da:ca:45:76:65:45:5a:84:6c:b5:ae:88:55:ca:96:
            64:7e:b0:24:66:da:95:76:1c:43:f3:a0:13:02:b1:
            7d:36:13:79:d2:7a:20:9b:5a:a0:99:71:66:32:ab:
            db:41:b0:1d:e5:6d:8a:9c:0d:e3:5f:bd:ba:2a:db:
            fa:e5:50:c5:53:25:49:9d:3a:e2:e2:7c:c8:6b:56:
            29:63:ae:1e:41:da:07:46:42:f9:bf:52:63:b1:77:
            2e:28:b9:b7:66:fa:d2:6c:c5:2e:b8:dc:46:da:e9:
            a4:0d:d5:76:61:49:42:ba:34:a0:d8:25:8c:76:9b:
            f9:a3:37:54:3d:24:2a:c9:de:69:24:74:b1:52:4d:
            c8:9f:4c:ac:37:d1:14:81:5f:dc:0f:44:67:bd:81:
            49:58:98:2c:b4:ef:e3:29:68:c7:7b:b9:5f:c4:04:
            42:a5:af:fd:0c:86:34:32:27:af:14:b4:e3:47:97:
            4d:35:5e:d5:de:48:18:31:97:a4:5f:17:87:fc:58:
            be:fe:67:1d:e2:66:90:b4:ae:7b:f1:60:86:fe:85:
            08:d9:e8:e0:69:83:43:8b:43:e7:f7:8c:aa:42:7d:
            47:8a:a0:7a:98:7f:78:60:86:14:04:78:9e:63:a2:
            46:41:a9:bd:63:4a:ef:07:38:49:7b:d9:60:db:ff:
            66:8e:81:25:6e:0c:0b:e2:df:f4:62:74:c1:2d:b7:
            c1:4c:ca:19:64:b9:79:14:fc:94:74:34:fc:c4:ec:
            03:c4:c3:86:13
        generator: 2 (0x2)