362 http://inventwithpython.com/hacking
Email questions to the author: [email protected]
Prime Numbers
A prime number is an integer (that is, a whole number) that is greater than 1 and has only two
factors: 1 and itself. Remember that the factors of a number are the numbers that can be
multiplied to equal the original number. The numbers 3 and 7 are factors of 21. The number 12
has factors 2 and 6, but also 3 and 4.
Every number has factors of 1 and itself. The numbers 1 and 21 are factors of 21. The numbers 1
and 12 are factors of 12. This is because 1 times any number will always be that same number.
But if no other factors exist for that number, then that number is prime.
Here’s a list of prime numbers (note that 1 is not considered a prime number):
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103,
107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281 ...and so on, FOREVER.
There are an infinite number of prime numbers. This means there is no “largest” prime. They just
keep getting bigger and bigger, just like regular numbers do. (See http://invpy.com/infiniteprimes
for a proof of this.) The RSA cipher makes use of very large prime numbers in the keys it uses.
Because of this, there will be far too many keys to brute-force through.
A googol is the number that has a one with a hundred zeros behind it:
10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,00
0,000,000,000,000,000,000,000,000,000,000,000
(As a bit of history: the name of the search engine company Google came from misspelling
“googol”, but they decided they liked that spelling better and kept it.)
A billion billion billion googols has twenty-seven more zeros than a googol:
10,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,00
0,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000
But these are tiny numbers. A typical prime number used in our RSA program will have hundreds
of digits:
112,829,754,900,439,506,175,719,191,782,841,802,172,556,768,253,593,054,977,186,235 5 ,84,9
79,780,304,652,423,405,148,425,447,063,090,165,759,070,742,102,132,335,103,295,947,000,71
8,386,333,756,395,799,633,478,227,612,244,071,875,721,006,813,307,628,061,280,861,610,153,
485,352,017,238,548,269,452,852,733,818,231,045,171,038,838,387,845,888,589,411,762,622,0
41,204,120,706,150,518,465,720,862,068,595,814,264,819