Python generated RSA keys looks the same

Question

I'm working on a sharing protocol, and the handshake, authentication etc. is done with RSA keys. By default I use 4096 bit keys, but it seems the beginning and end of any key generated are the same, how worried should I be?

This phenomenon happens both on Windows and Linux.

The python code generating the keys is roughly this:

from Crypto.PublicKey import RSA
from Crypto import Random

random_generator = Random.new().read
prv = RSA.generate(4096, random_generator)

Some example keys I generated (snipped), two on Windows, one on Linux:

30820222300d06092a864886f70d01010105000382020f003082020a0282020100b420065527689ff14a115a9c1b63bf79294407bf621d4ab...0da370203010001
30820222300d06092a864886f70d01010105000382020f003082020a0282020100b39291f674eddfe8d8571b856bf7f83c01ca8ba231f16e8...678590203010001
30820222300d06092a864886f70d01010105000382020f003082020a02820201009a2bec7fad52fe7c50cce509b3406b8ff981a626f28082e...0e98d0203010001

As you can see, the some 66 first and 10 last nibbles are identical, over 300 bits.

Should I ditch the rng for some other or am I just too paranoid?

Answer 1

The two large primes that make up the RSA private key are different each time you run the script.

I added a line to the end of your script, to output the RSA private key in PEM format produced by the script:

from Crypto.PublicKey import RSA
from Crypto import Random

random_generator = Random.new().read
prv = RSA.generate(4096, random_generator)

print(prv.exportKey().decode())

Then, I saved the script as genrsa.py. If you run genrsa.py, you'll see that it produces an RSA private key, in PEM format.

Try running the script, and redirect the output to a file called privatekey.pem:

 python3 genrsa.py > privatekey.pem

Now, use openssl to examine the contents of privatekey.pem:

openssl rsa -noout -text -inform PEM -in privatekey.pem

Look at the two primes. Then, repeat the steps above, and compare the two primes created in the second run to those created in the first run. The two pairs are very different.

With regard to the question about why the beginning and ending bytes of the PEM file produced are always the same - this has to do with the RSA format itself, and the ASN.1 and DER encoding standards that are used to create PEM files. See https://stackoverflow.com/questions/18039401/how-can-i-transform-between-the-two-styles-of-public-key-format-one-begin-rsa for more information.

For more information on the anatomy of an RSA private key PEM file, and how you can examine the underlying components of the private key contained in the file, see: https://crypto.stackexchange.com/questions/45151/anatomy-of-an-rsa-private-key.