OpenSSL and RSA Keys – Building strong keys

Recently, I was reviewing the number theory associated with RSA Public Key Encryption. (I know, I need to get a life.) I noticed that there were several precautions listed for selecting the primes used to generate these keys:

1. p and q should differ in length by a few digits
2. Both p – 1 and q – 1 should contain large prime factors
3. gcd(p – 1, q – 1) should be small

([Den84] Dorothy Denning. Cryptography and Data Security. Addison-Wesley, 1984. )

While precaution 1 can be checked by observation, precautions 2 and 3 are met by picking your primes in particular ways.  (To be discussed some time in the future, assuming I don’t get a life before then…)

Nerd that I am, I fired up OpenSSL and took a look at some keys. What I found was that all of the keys failed test 1, some of them badly.

For example, this command will create a 2048 bit RSA key, and display it on the terminal:

openssl genrsa -3 2048 | openssl rsa -text –noout

Parsing through the output, you’ll find the two primes used to create the key:

[stuff removed]
prime1:
00:df:5f:81:5b:54:38:20:a4:bb:11:62:1f:05:33:
e2:68:27:f3:25:c9:2b:f9:75:5c:75:10:c0:70:67:
99:6b:9d:2c:99:5d:3a:1e:3a:ff:7e:dc:65:6a:a2:
09:44:0f:b8:10:43:b6:66:15:05:da:52:7b:79:a7:
79:d5:d7:84:01:c8:84:d2:76:0b:80:4b:3d:68:28:
d6:3c:f2:e6:02:27:11:f8:e8:52:ef:f3:5a:79:d9:
89:1f:fb:4b:fd:63:c9:fb:da:97:0f:e4:36:95:73:
a0:53:bf:cf:e8:a6:e0:7e:86:7e:23:14:a8:82:bb:
5f:7a:3e:14:a5:c2:7c:8c:eb
prime2:
00:df:46:72:0f:05:aa:b3:33:3b:e8:57:c7:40:43:
e8:42:0c:00:5e:a5:48:cc:48:76:3b:bd:8a:a5:29:
55:a5:17:0b:a7:e8:65:55:43:e0:22:63:13:33:87:
b6:45:0a:77:70:54:d2:be:c6:d8:41:22:8f:d6:19:
40:95:7f:7e:cc:75:c6:7f:80:bd:89:ab:d4:b7:69:
9f:73:2b:53:12:4b:14:ff:b3:b4:b6:c1:c2:88:f2:
34:d7:c7:34:2c:2f:86:9a:12:41:22:53:2c:2e:1e:
f4:37:d7:51:d5:cf:6e:bd:3b:0c:ac:10:1b:76:5a:
88:52:fa:10:61:9b:6e:a4:89
[more stuff removed]

Note that in this example, the two primes are the same length, and have the same prefix:

00:df:

I repeated the test a number of times, with similar results; the lengths were always roughly the same (within a bit or two) though the values of the generated primes generally differed by more than above.

I can’t speak to precautions 2 and 3, as I haven’t read the key generating code, and don’t know how they go about picking their primes. (Anybody out there familiar with this?)

Given the size of the key, this probably isn’t a big concern for most applications. If you are restricted to smaller keys, however, you may want to generate a few keys, and select one with a significant difference between the values of the primes.

Conclusion: OpenSSL can generate keys that violate precaution 1.  I don’t know yet about conditions 2 and 3, but I think it is unlikely that either of them are met.

NSA Wiretapping – Better than on-line ads?

Recent news about the NSA’s wiretapping program doesn’t come as much of a surprise. We knew they were doing wiretaps. What was surprising was the scale: they wanted to monitor everyone and everything. It’s hard to imagine that they will obtain useful information from such a broad-based approach.

Consider on-line advertising. There are a number of very large companies doing ad placement on the web. These companies have loads of personal information about us, extensive data mining tools, and years of experience trying to predict our interests and behavior.

And the result? Most of these ads are so ineffective that they are only worth around $0.00001 each.

Additionally, unlike the terrorists, most of us are not trying to hide our interests/behavior. So you would expect the results for the NSA to be even worse.

Now this comparison may not be fair (I’d love your feedback on this) but it makes me wonder how the NSA is going to get much value from this program. A lead on a potential terrorist that’s only worth $0.00001?

Setting the bar too low

Like many nerds, I was amused by The Google’s motto: “don’t be evil”. It had a nice David vs Goliath image, and made a point about Microsoft’s evil empire.

But David has grown up. Between The Google’s user knowledge, and their extensive data mining abilities, they are capable of doing terrible things.

“Don’t be evil” sets the bar way too low.

Da first post

Created by my master impersonator, who will subsequently be handed a pink slip.