Hacking Secret Ciphers with Python

418 http://inventwithpython.com/hacking

Email questions to the author: [email protected]

Lines 159 and 160 call the main() function if this program was run by itself rather than
imported by another program.

Practice Exercises, Chapter 24, Set D

Practice exercises can be found at http://invpy.com/hackingpractice 24 D.

Why Can’t We Hack the RSA Cipher

All the different types of cryptographic attacks we’ve used in this book can’t be used against the
RSA cipher:

1. The brute-force attack won’t work. There are too many possible keys to go through.


2. A dictionary attack won’t work because the keys are based on numbers, not words.


3. A word pattern attack can’t be used because the same plaintext word can be encrypted
   differently depending on where in the block it appears.


4. Frequency analysis can’t be used. Since a single encrypted block represents several
   characters, we can’t get a frequency count of the individual characters.

There are no mathematical tricks that work, either. Remember, the RSA decryption equation is:

M = C^d mod n

Where M is the message block integer, C is the ciphertext block integer, and the private key is
made up of the two numbers (d, n). Everyone (including a cryptanalyst) has the public key file,
which provides (e, n), so the n number is known. If the cryptanalyst can intercept the ciphertext
(which we should always assume is possible), then she knows C as well. But without knowing d,
it is impossible to do the decryption and calculate M, the original message.

A cryptanalyst knows that d is the inverse of e mod (p – 1) × (q – 1) and also knows e from the
public key. But there’s no way she knows what (p – 1) × (q – 1) is. There are some hints to figure
it out though.

The key sizes are known (it’s in the public key file), so the cryptanalyst knows that p and q are
less than 2 ^ 1024 and that e is relatively prime with (p – 1) × (q – 1). But e is relatively prime
with a lot of numbers, and with a range of 0 to 2 ^ 1024 possible numbers, it is too large to brute-
force.

The cryptanalyst has another hint from the public key, though. The public key is two numbers (e,
n). And from the RSA algorithm she knows that n = p × q. And since p and q are both prime
numbers, for the given n number there can be only two numbers for p and q.