Note: The second edition of this book is available under the title Cracking Codes with Python

 

“Why shouldn’t I work for the NSA? That’s a tough one, but I’ll take a shot. Say I’m working at the NSA and somebody puts a code on my desk, something no one else can break. Maybe I take a shot at it, and maybe I break it. I’m real happy with myself, ‘cause I did my job well. But maybe that code was the location of some rebel army in North Africa or the Middle East and once they have that location they bomb the village where the rebels are hiding. Fifteen hundred people that I never met, never had no problem with, get killed.

 

Now the politicians are saying ‘Oh, send in the Marines to secure the area,’ ‘cause they don’t give a shit. It won’t be their kid over there getting shot just like it wasn’t them when their number got called ‘cause they were pulling a tour in the National Guard. It’ll be some kid from Southie over there taking shrapnel in the ass. He comes back to find that the plant he used to work at got exported to the country he just got back from, and the guy that put the shrapnel in his ass got his old job, ‘cause he’ll work for fifteen cents a day and no bathroom breaks.

 

Meanwhile he realizes that the only reason he was over there in the first place was so we could install a government that would sell us oil at a good price. And of course the oil companies use the little skirmish to scare up domestic oil prices, a cute little ancillary benefit for them, but it ain’t helping my buddy at two-fifty a gallon. They’re taking their sweet time bringing the oil back, of course, and maybe they took the liberty of hiring an alcoholic skipper who likes to drink martinis and fucking play slalom with the icebergs. It ain’t too long until he hits one, spills the oil, and kills all the sea life in the North Atlantic.

 

So now my buddy’s out of work, he can’t afford to drive, so he’s walking to the fucking job interviews which sucks because the shrapnel in his ass is giving him chronic hemorrhoids. And meanwhile he’s starving ‘cause any time he tries to get a bite to eat the only Blue Plate Special they’re serving is North Atlantic Scrod with Quaker State.

 

So what did I think? I’m holding out for something better.”

 

“Good Will Hunting”

Public Key Cryptography

All of the ciphers in this book so far have one thing in common: the key used for encryption is the same key used for decryption. This leads to a tricky problem: How do you share encrypted messages with someone you’ve never talked to before?

Say someone on the other side of the world wants to communicate with you. But you both know that spy agencies are monitoring all emails, letters, texts, and calls that you send. You could send them encrypted messages, however you would both have to agree on a secret key to use. But if one of you emailed the other a secret key to use, then the spy agency would be able to see this key and then decrypt any future messages you send with that key. Normally you would both secretly meet in person and exchange the key then. But you can’t do this if the person is on the other side of the world. You could try encrypting the key before you send it, but then you would have to send the secret key for that message to the other person and it would also be intercepted.

This is a problem solved by public key cryptography. Public key cryptography ciphers have two keys, one used for encryption and one used for decryption. A cipher that uses different keys for encryption and decryption is called an asymmetric cipher, while the ciphers that use the same key for encryption and decryption (like all the previous ciphers in this book) are called symmetric ciphers.

The important thing to know is that a message encrypted with one key can only be decrypted with the other key. So even if someone got their hands on the encryption key, they would not be able to read an encrypted message because the encryption key can only encrypt; it cannot be used to decrypt messages that it encrypted.

So when we have these two keys, we call one the public key and one the private key. The public key is shared with the entire world. However, the private key must be kept secret.

If Alice wants to send Bob a message, Alice finds Bob’s public key (or Bob can give it to her). Then Alice encrypts her message to Bob with Bob’s public key. Since the public key cannot decrypt a message that was encrypted with it, it doesn’t matter that everyone else has Bob’s public key.

When Bob receives the encrypted message, he uses his private key to decrypt it. If Bob wants to reply to Alice, he finds her public key and encrypts his reply with it. Since only Alice knows her own private key, Alice will be the only person who can decrypt the encrypted message.

Remember that when sending encrypted messages using a public key cipher:

·   The public key is used for encrypting.

·   The private key is used for decrypting.

To go back to the example of communicating with someone across the world, now it doesn’t matter if you send them your public key. Even if the spy agency has your public key, they cannot read messages that were encrypted with the public key. Only your private key can decrypt those messages, and you keep that key a secret.

The particular public key cipher that we will implement is called the RSA cipher, which was invented in 1977 and named after its inventors: Ron Rivest, Adi Shamir and Leonard Adleman.

The Dangers of “Textbook” RSA

While we don’t write a hacking program for the RSA cipher program in this book, don’t make the mistake of thinking the rsaCipher.py program featured in this chapter is secure. Getting cryptography right is very hard and requires a lot of experience to know if a cipher (and a program that implements it) is truly secure.

The RSA program in this chapter is known as textbook RSA because, while it does implement the RSA algorithm correctly using large prime numbers, there are several subtle faults with it that can lead to its encrypted messages being hacked. The difference between pseudorandom and truly random number generation functions is one such fault. But there are many others.

So while you might not be able to hack the ciphertext created by rsaCipher.py, don’t think that no one else can. The highly accomplished cryptographer Bruce Schneier once said, “Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can’t break. It’s not even hard. What is hard is creating an algorithm that no one else can break, even after years of analysis. And the only way to prove that is to subject the algorithm to years of analysis by the best cryptographers around.”

The program in this book is a fun example, but stick to professional encryption software to secure your files. You can find a list of (usually free) encryption software here: http://invpy.com/realcrypto.

A Note About Authentication

There is a slight problem with public key ciphers. Imagine you got an email that said this:

“Hello. I am Emmanuel Goldstein, leader of the resistance. I would like to communicate secretly with you about very important matters. Attached is my public key.”

Using the public key, you can be sure that the messages you send cannot be read by anyone other than “Emmanuel Goldstein”. But how do you know the person who sent you this is actually Emmanuel Goldstein? Maybe it is Emmanuel Goldstein that you are sending encrypted messages to, or maybe it is a spy agency that is pretending to be Emmanuel Goldstein to lure you into a trap.

So while public key ciphers (and, in fact, all the ciphers in this book) can provide confidentiality (that is, keeping the message a secret), they don’t provide authentication (that is, proof that who you are communicating with really is who they say they are).

Normally this isn’t a problem with symmetric ciphers, because when you exchange keys with the person you can see them for yourself. However, you don’t need to see a person in order to get their public key and begin sending them encrypted messages. This is something to keep in mind when using public key cryptography.

There is an entire field called PKI (Public Key Infrastructure) that deals with authentication so that you can match public keys to people with some level of security; however, PKI is beyond the scope of this book.

The Man-In-The-Middle Attack

Even more insidious than hacking our encrypted messages is a man-in-the-middle attack. Say Emmanuel Goldstein really did want to communicate with you and sent you the above message, but the spy agency intercepted it. They could then replace the public key Emmanuel attached to the email with their own public key, and then send it on to you. You would think the spy agency’s key was Emmanuel’s key!

Now when you encrypt a reply to Emmanuel, they intercept that message, decrypt it (since you really encrypted the message with the spy agency’s public key, not Emmanuel’s public key) and read it, and then they re-encrypt it with Emmanuel’s actual public key and send it to him. They do the same thing with any messages that Emmanuel sends to you.

Figure 24-1. A man-in-the-middle attack.

To both you and Emmanuel, it looks like you are communicating secretly with each other. But actually, the spy agency is doing a man-in-the-middle attack and reading all of your messages. You and Emmanuel are actually encrypting your messages public keys generated by the spy agency! Again, this problem is caused by the fact that the public key cipher only provides confidentiality, but does not provide authentication.

Generating Public and Private Keys

A key in the RSA scheme is made of two numbers. There are three steps to creating the keys:

1.      Create two random, distinct, very large prime numbers. These numbers will be called p and q. Multiply these numbers to get a number which we will call n.

2.      Create a random number, called e, which is relatively prime with (p – 1) × (q – 1).

3.      Calculate the modular inverse of e. This number will be called d.

The public key will be the two numbers n and e. The private key will be the two numbers n and d. (Notice that both keys have the number n in them.) We will cover how to encrypt and decrypt with these numbers when the RSA cipher program is explained. First let’s write a program to generate these keys.

Source Code for the RSA Key Generation Program

Open a new file editor window by clicking on File ► New Window. Type in the following code into the file editor, and then save it as makeRsaKeys.py.

Sample Run of the RSA Key Generation Program

When you run the makeRsaKeys.py program, the output will look something like this (of course, the numbers for your keys will be different since they are random numbers):

These two keys are written out to two different files, al_sweigart_pubkey.txt and al_sweigart_privkey.txt. These filenames are used because the string 'al_sweigart' was passed to the makeKeyFiles() function. You can specify a different filenames by passing a different string. These key files will be used by the RSA cipher program to encrypt and decrypt messages.

If you try to run makeRsaKeys.py again with the same string being passed to makeKeyFiles(), the output of the program will look like this:

This warning is here so you don’t accidentally overwrite your key files, making any files you encrypted with them impossible to recover. Keep your keys safe!

How the Key Generation Program Works

The program imports the rabinMiller and cryptomath modules that we created in the last chapter, along with a few others.

When makeRsaKeys.py is run, the main() function is called, which will create the key files. Since the keys might take a while for the computer to generate, we print a message on line 9 before the makeKeyFiles() call so the user knows what the program is doing.

The makeKeyFiles() call on line 10 passes the string 'al_sweigart' and the integer 1024. This will generate keys with a size of 1024 bits and store them in files named al_sweigart_pubkey.txt and al_sweigart_privkey.txt.

The Program’s generateKey() Function

The first step of creating keys is coming up with two random prime numbers which are called p and q. The generateLargePrime() function we wrote in the last chapter’s rabinMiller.py program will return a prime number (as an integer value) of the size determined by the value in keySize on line 19 and line 21. These integer values are stored in variables named p <<<<<<< HEAD and q. Make sure that p and q are not the same number.

======= and q.

>>>>>>> 23da471aa4d8b7af4ca17689e75270d654c60320

On line 22, the number n is calculated by multiplying p and q, and stored in n.

The second step is calculating a number e which is relatively prime to the product of p – 1 and q – 1. The while loop on line 26 is an infinite loop. The random.randrange() call on line 28 returns a random integer (stored in the e variable) and line 29 tests if this random number is relatively prime to (p - 1) * (q - 1). If it is, the break statement on line 30 breaks out of the infinite loop. Otherwise, the program execution jumps back to line 26 and will keep trying different random numbers until it finds one that is relatively prime with (p - 1) * (q - 1).

This way we can guarantee that when the program execution gets past this while loop, the variable e will contain a number that is relatively prime to (p - 1) * (q - 1).

The third step is to find the mod inverse of e. The findModInverse() function that we wrote for our cryptomath module in Chapter 14 will do this calculation for us. The mod inverse of e is stored in a variable named d.

In the RSA cipher, each key is made up of two numbers. The public key will be the integers stored in n and e, and the private key will be the integers stored in n and d. Lines 36 and 37 store these integers as tuples in the variables publicKey and privateKey.

There’s no reason e has to be in the public key and d in the private key, and you could swap them. However, once you make the public key public, you must keep the private key a secret.

The remaining lines in the generateKey() function print the keys on the screen with print() calls on lines 39 and 40. Then line 42’s generateKey() call returns a tuple with publicKey and privateKey.

 

While the generateKey() function will generate the actual integers for the public and private keys, we need to store these numbers in a file so that our RSA cipher program can use them later to encrypt and decrypt. Each of the keys are made of two integers that are hundreds of digits long; that’s too many to memorize or conveniently write down. The easiest way to store them is as text files on your computer.

This means that you have to be sure that nobody hacks your computer and copies these key files. It might be a good idea to store these files on a USB thumb drive instead of on your computer. However, this is also risky. If someone borrows the thumb drive then they could copy the key files, or if you accidentally break or lose the thumb drive then you will lose your own private key!

To prevent us from accidentally deleting our key files by running the program again, line 51 checks to see if the public or private key files with the given name already exist. If they do, the program will exit with a warning message.

After the check, line 54 has a call to generateKey() to get the public and private keys using the multiple assignment trick. The generateKey() function returns a tuple of two tuples. The first tuple has two integers for the public key and the second tuple has two integers for the private key. These are stored in the variables publicKey and privateKey.

RSA Key File Format

Line 57 prints some information about the public key. It can tell how many digits are in the integer in publicKey[0] and publicKey[1] by converting those values to strings with the str() function, and then finding the length of the string with the len() function.

The key file’s contents will be the key size, a comma, the n integer, another comma, and the e (or d) integer. The file’s contents will look like: <key size integer>,<n integer>,<e or d integer>

Lines 59 to 61 open a file in write mode, as you can tell from the 'w' string passed to open().

Lines 63 to 68 do the exact same thing as lines 56 and 61, except for writing the private key out to a file.

Lines 73 and 74 are at the bottom of the program, and call main() if makeRsaKeys.py is being run as a program instead of imported as a module by another program.

Hybrid Cryptosystems

In real life, the complicated mathematics make RSA and public-key encryption slow to compute. This is especially true for servers that need to make hundreds or thousands of encrypted connections a second. Instead, the RSA cipher is often used to encrypt the key for a symmetric key cipher. The encrypted key is then sent to the other person, and that key is used to pass messages that are encrypted using the (faster) symmetric cipher. Using a symmetric key cipher and an asymmetric key cipher to securely communicate like this is called a hybrid cryptosystem. More information about hybrid cryptosystems can be found at https://en.wikipedia.org/wiki/Hybrid_cryptosystem.

It’s not recommended to use the rsaCipher.py program to encrypt the keys for, say, the vigenereCipher.py program. We’ve already proven that the Vigenère cipher is hackable. A strong symmetric key cipher isn’t covered in this book, but you can still use rsaCipher.py to encrypt your files anyway.

Source Code for the RSA Cipher Program

Now that you can create key files, let’s write the program that does encryption and decryption with the RSA cipher. Open a new file editor window by clicking on File ► New Window. Type in the following code into the file editor, and then save it as rsaCipher.py.

Sample Run of the RSA Cipher Program

Once you have a public and private key file, you can send anyone your public file (or post it somewhere online) so others can send you messages. If you want to send a secret message to someone, first get their public key file and place it in the same directory as the rsaCipher.py program. Set the message variable on line 19 to the string of the message to encrypt.

Make sure the mode variable is set to the string 'encrypt' on line 16, and set the pubKeyFilename variable to the public key file’s filename on line 20. The filename variable holds a string of the file that the ciphertext will be written to.

When you run the program, the output will look like this:

At the start of the text is 262 (which is the original message length), followed by an underscore and then 128 (which is the “block size”; block sizes are explained later). If you look carefully at the long string of digits after that, you will find two commas. The message is encrypted into three very large integers, separated by commas. These integers are the encrypted form of the string in the message variable on line 19.

To decrypt, change the mode variable to 'decrypt' and run the program again. Make sure privKeyFilename on line 28 is set to the filename of the private key file and that this file is in the same folder as rsaCipher.py. When you run the program, the output on the screen will look like this:

Note that the way the RSA cipher program is implemented, it can only encrypt and decrypt plaintext files. A plaintext file (not to be confused with “plaintext” in the cryptography sense) is a file that only contains text characters (like the kind that you can type on your keyboard). For example, the .py files that you type for your Python programs are plaintext files. Plaintext files are the type created with text editor software such as Notepad (on Windows), TextMate (on OS X), or Gedit (on Ubuntu). Specifically, plaintext files are files that only contain ASCII values (which are described later in this chapter).

Files such as images, videos, executable programs, or word processor files are called binary files.(Word processor files are binary files because their text has font, color, and size information bundled with the text.) More information about plaintext files and binary files can be found at http://invpy.com/plainvsbinary.

Practice Exercises, Chapter 24, Set A

Practice exercises can be found at http://invpy.com/hackingpractice24A.

Digital Signatures

Digital signatures is a very large topic of its own, but we can cover a little of it here. Let’s say Alice sent this email to Bob:

 

This is great news to Bob, who wants to get rid of his worthless laptop for any price. But what if Alice later claims that she didn’t make this promise, and that the email Bob has is a forgery that didn’t really come from her. The email just exists as some file on Bob’s computer. Bob could have easily created this file himself.

If they had met in person, Alice and Bob could have signed a contract. The handwritten signature is not easy to forge and provides some proof that Alice really did make this promise. But even if Alice signed such a paper, took a photo of it with her digital camera, and sent Bob the image file, it is still believable for Alice to say that the image was photoshopped.

The RSA cipher (and any public key cipher) not only provides encryption, but it can also provide a way to digitally sign a file or string. Remember that RSA has a public key and a private key, and that any string that is encrypted with one key produces ciphertext that can only be decrypted with the other key. Normally we encrypt with the public key, so that only the owner of the private key can decrypt this ciphertext.

But we can also do the reverse. If Alice writes this message, and then “encrypts” it with her private key, this will produce “ciphertext” that only Alice’s public key can decrypt. This “ciphertext” isn’t really so secret since everyone in the world has access to Alice’s public key to decrypt it. But by encrypting a message with her own private key, Alice has digitally signed the message in a way that cannot be forged. Everyone can decrypt this signed message with her public key, and since only Alice has access to her private key, only Alice could have produced this ciphertext. Alice has to stick to her digital signature; she can’t say that Bob forged or photoshopped it!

This feature is called nonrepudiation. Nonrepudiation is where someone who has made a statement or claim cannot later refute that they made that statement or claim. Alice could always claim that her computer was hacked and somebody else had access to her private key, but this would mean that any other documents she signed could be called into question. (And it would be very suspicious if Alice’s computer kept “getting hacked” each time she wanted to back out of a promise.)

Digital signatures can also provide authentication, which allows someone to prove they are who they say they are. If Alice gets an email claiming to be from the President but wants to be sure it really is the President, she could always respond with, “Prove you’re the President! Encrypt the string 'SIMTAVOKXVAHXXSLBGZXVPKNMQMHOYGWFQMXEBCC' with the President’s private key.” and Alice would be able to decrypt the reply with the President’s public key to see if it decrypted to her random string. This is called a challenge-response authentication system.

Digital signatures can be used to do many important things, including digital cash, authentication of public keys, or anonymous web surfing. If you’d like to find out more, go to http://invpy.com/digitalsignatures.

How the RSA Cipher Program Works

A single “byte” can hold a number between 0 and 255, that is, 256 different numbers. We will use this fact in some of the block-related math explained later. This is why the BYTE_SIZE constant is set to 256. The DEFAULT_BLOCK_SIZE constant is set to 128 because we will be using block sizes of 128 bytes by default in our program. (Block sizes are explained later.)

If mode is set to 'encrypt' the program encrypts a message (and writes it to the file that is named in filename). If mode is set to 'decrypt' the program reads the contents of an encrypted file (specified by the string in filename) to decrypt it.

The message variable contains the text to be encrypted, and pubKeyFilename contains the filename of the public key file. Line 22 calls the encryptAndWriteToFile() function, which will encrypt message using the key, and write the encrypted message to the file named in filename.

The code that handles calling the decryption function is similar to the code on lines 18 to 33. The filename of the private key file is set in privKeyFilename. The encrypted file’s filename is stored in the filename variable. These two variables are passed to a call to readFromFileAndDecrypt(). The return value is stored in decryptedText and then printed to the screen.

ASCII: Using Numbers to Represent Characters

All data is stored on your computer as numbers. A code called the American Standard Code for Information Interchange, or ASCII (pronounced “ask-ee”) maps numbers to characters. Table 24-1 shows how ASCII maps numbers and characters (only numbers 32 to 126 are used):

Table 24-1. The ASCII table.

32	(space)	48	0	64	@	80	P	96	`	112	p
33	!	49	1	65	A	81	Q	97	a	113	q
34	"	50	2	66	B	82	R	98	b	114	r
35	#	51	3	67	C	83	S	99	c	115	s
36	$	52	4	68	D	84	T	100	d	116	t
37	%	53	5	69	E	85	U	101	e	117	u
38	&	54	6	70	F	86	V	102	f	118	v
39	'	55	7	71	G	87	W	103	g	119	w
40	(	56	8	72	H	88	X	104	h	120	x
41	)	57	9	73	I	89	Y	105	i	121	y
42	*	58	:	74	J	90	Z	106	j	122	z
43	+	59	;	75	K	91	[	107	k	123	{
44	,	60	<	76	L	92	\	108	l	124	|
45	-	61	=	77	M	93	]	109	m	125	}
46	.	62	>	78	N	94	^	110	n	126	~
47	/	63	?	79	O	95	_	111	o

 

A single ASCII character uses one byte of memory to store. A byte is enough memory to store a number from 0 to 255 (for a total of 256 different values.) So the string 'Hello' is actually stored on your computer as the numbers 72, 101, 108, 108, and 111. These numbers take up 5 bytes. ASCII provides a standard way to convert string characters to numbers and back.

ASCII works fine for English messages, but not so much for other European languages that have special characters such as the è in “Vigenère”, or languages such as Chinese and Arabic. ASCII doesn’t even work well outside of America, since ASCII includes the $ dollar sign but not the € euro or £ pound signs. If you want to learn about Unicode, the international system of character encoding, go to http://invpy.com/unicode. But this book will use ASCII for simplicity.

The chr() and ord() Functions

Remember from the first chapter where a code was a publicly-known way of translating information from one format to another format? For example, Morse code was a way of translating English letters into electric pulses of dots and dashes. ASCII is just a code. We can encode characters into ASCII numbers and decode ASCII numbers back to characters.

The chr() function (pronounced “char”, short for “character”) takes an integer ASCII number as the argument and returns a single-character string. The ord() function (short for “ordinal”) takes a single-character string as the argument, and returns the integer ASCII value for that character. Try typing the following into the interactive shell:

But if you have a string with many letters, it may be easier to use the encode() and decode() string methods explained later in this chapter.

Practice Exercises, Chapter 24, Set B

Practice exercises can be found at http://invpy.com/hackingpractice24B.

Blocks

In cryptography, a “block” is a fixed length of bits. In our RSA cipher program, a block is represented by an integer. We’ve set the block size to 128 bytes, or 1024 bits (since there are 8 bits in 1 byte). Our message string value will be converted into several integer values (i.e. several blocks).

·        It is important to note that the RSA encryption algorithm requires that the block size be equal or less than the key size. Otherwise, the math doesn’t work and you won’t be able to decrypt the ciphertext the program produced.

So a cryptographic block is really just a very large integer. Since our block size is 128 bytes, it can represent any integer between 0 and up to (but not including) 256 ^ 128, which is 179,769,313,486,231,590,772,930,519,078,902,473,361,797,697,894,230,657,273,430,081,157,732,675,805,500,963,132,708,477,322,407,536,021,120,113,879,871,393,357,658,789,768,814,416,622,492,847,430,639,474,124,377,767,893,424,865,485,276,302,219,601,246,094,119,453,082,952,085,005,768,838,150,682,342,462,881,473,913,110,540,827,237,163,350,510,684,586,298,239,947,245,938,479,716,304,835,356,329,624,224,137,216.

(You might have noticed that the RSA cipher uses a lot of big numbers.)

The reason RSA needs to work on a block (which represents multiple characters) is because if we used the RSA encryption algorithm on a single character, the same plaintext characters would always encrypt to the same ciphertext characters. In that case, the RSA cipher just becomes a simple substitution cipher with fancy mathematics, kind of like the affine and Caesar ciphers.

The RSA cipher works by encrypting an integer that is hundreds of digits long (that is, a block) into a new integer that is hundreds of digits long (that is, a new block). The mathematics of encrypting a large plaintext integer to a large ciphertext integer are simple enough. But first we will need a way to convert between a string and a large integer (that is, a block).

We can use ASCII as a system to convert between a single character and a small integer (between 0 and 255). But we will also need a way to combine several small integers into a large integer that we perform RSA encryption on.

Remember how the affine cipher in Chapter 15 had two keys, Key A and Key B, but they were combined by multiplying Key A by the symbol set size (which was 95) and then adding Key B? This was how we combined two small key integers into one larger key integer.

This worked because the ranges of both Key A and Key B were from 0 to 94. In the RSA program, each character’s ASCII integer ranges from 0 to 255. To combine ASCII integers together into one large number we use the following formula:

Take the ASCII integer of the character at index 0 of the string and multiply it by 256 ^ 0 (but since 256 ^ 0 is 1, and multiplying by 1 leaves you with just the original number, this one is easy). Take the ASCII integer of the character at index 1 and multiply it by 256 ^ 1. Take the ASCII integer of the character at index 2 and multiply it by 256 ^ 2, and so on and so on. To get the final large integer, add all of these products together. This integer is the ciphertext’s block.

Table 24-2 has an example using the string, 'Hello world!':

 

Table 24-2. Encoding a string into a block.

 

(You might have noticed that the RSA cipher does a lot of math with big numbers.)

So the string 'Hello world!' when put into a single large integer “block” becomes the integer 10,334,410,032,606,748,633,331,426,632. This integer uniquely refers to the string 'Hello world!'. By continuing to use larger and larger powers of 256, any string possible has exactly one large integer. For example, 2,175,540 is the integer for '42!' and 17,802,628,493,700,941 is the integer for 'Moose??' and 23,071,981,395,336,227,453,293,155,570,939,985,398,502,658,016,284,755,880,397,214,576,110,064,091,578,359,739,349,325 is the integer for 'My cat's breath smells like cat food.'.

Because our block size is 128 bytes, we can only encrypt up to 128 characters in a single block. But we can just use more blocks if the message is longer than 128 characters. The RSA cipher program will separate the blocks it outputs with commas so we can tell when one block ends and the next one begins.

As an example, here’s a message that is split into blocks, and the integer that represents each block (calculated using the same method in Table 24-2.). Each block has at most 128 characters of the message.

 

Table 24-3. A message split into blocks, with each block’s integer.

	Message	Block Integer
1st Block (128 characters)	Alan Mathison Turing was a British mathematician, logician, cryptanalyst, and computer scientist. He was highly influential in t	81546931218178010029845817915569188970228635035880924048568611897988742463406567023883943221582747883194198801889762995126820043055718365161172430048774726604180301487686042582446510742004253320139858568955596950639178360628971132804888925435112531133886746309774148590001157056903849858716430520524535327809
2nd Block (128 characters)	he development of computer science, providing a formalisation of the concepts of "algorithm" and "computation" with the Turing m	76631289268154712859022451851447083030531656773493193435586385884713450374043199564593208509316042234996861905222506249242068799766044149679741160521638235464390814933437480918921110848346820082794989525095472576883441558434022389690224894703002514434767442075089828357797890134106785932701869224970151814504
3rd Block (128 characters)	achine. Turing is widely considered to be the father of computer science and artificial intelligence. During World War II, Turin	77533874832922662837221187157031815413218696656188289479237285042329317929987590255656863216170413017929282537609866464073913897327838474709028475738093888688583459781662724944601473582838586714473965254498913751782047828043527094001429567417501493130489686652467441331220556610652015232230994266943673361249
4th Block (107 characters)	g worked for the Government Code and Cypher School (GCCS) at Bletchley Park, Britain's codebreaking centre.	87080208891262703930798322686594857958157735191131124701299945788118904302570291378810871619692196042841627479667133454733264625727703476738415017881880631980435061770341231617044485961511191333330447714267734389115735407982254796472640732348730838206586983

Converting Strings to Blocks with getBlocksFromText()

The getBlocksFromText() function takes the message and returns a list of blocks (that is, a list of very large integer values) that represents the message. It is trivially easy to convert between strings to blocks and blocks to strings, so this step isn’t encrypting anything. The encryption will be done later in the encryptMessage() function.

The encode() String Method and the Bytes Data Type

First, we need to convert the characters in the message string into ASCII integers. The encode() string method will return a “bytes” object. Because a byte is represented as a number from 0 to 255, a bytes value is like a list of integers (although these integers have a very limited range of 0 to 255). The len() function and indexing work with a bytes object in the same way a list of integers would. A bytes value can be turned into a list value of integer values by passing it to the list() function. Try typing the following into the interactive shell:

Note that a single bytes value is a collection of values, just like a single list value can contain multiple values. If you try to get a single “byte” from a bytes object (like spam[2] does above), this just evaluates to an integer value.

Line 40 places the bytes form of the message string in a variable named messageBytes.

The bytes() Function and decode() Bytes Method

Just like you can create a list by calling the list() function, you can also create a bytes object by calling the bytes() function. The bytes() function is passed a list of integers for the byte values. Try typing the following into the interactive shell:

You can also directly type a bytes object into your source code just like you type a string or list. A bytes object has the letter b right before what looks like an ordinary string value. But remember, the letter b right before the quotes means that this is a bytes value, not a string value. Try typing the following into the interactive shell, making sure that there is no space between the b and the quote characters:

We don’t use the decode() bytes method in this program, but you should know about it. It does the opposite of the encode() string method. When called on a bytes object, the decode() method returns a string made from the values stored in the bytes object. Try typing the following into the interactive shell:

Practice Exercises, Chapter 24, Set C

Practice exercises can be found at http://invpy.com/hackingpractice24C.

Back to the Code

The blockInts list will contain the large integer “blocks” form of the characters in message. The blockSize parameter is set to DEFAULT_BLOCK_SIZE by default, and the DEFAULT_BLOCK_SIZE constant was set to 128 (meaning, 128 bytes) on line 9. This means that each large integer block can only store 128 string characters at most (since 1 ASCII character takes up 1 byte). See Table 24-3 for an example of a message split into 128-character blocks.

Line 43’s for loop will set the value in blockStart so that on each iteration it will be set to the index of the block being created. For example, if blockSize is set to 128, then the index of the start of the first block will be 0, the index of the start of the second block will be 128, the index of the start of the third block will be 256, and so on as long as the index is less than len(messageBytes).

The min() and max() Functions

The min() function returns the smallest (that is, the minimum) value of its arguments. Try typing the following into the interactive shell:

You can also pass min() a single argument if the argument is a list or tuple value. In this case, min() returns the smallest value in that list or tuple. Try typing the following into the interactive shell:

The max() function will return the largest (that is, the maximum) value of its arguments:

The code inside line 43’s for loop will create the very large integer for a single block. Recall from earlier in this chapter that this is done by multiplying the ASCII value of the character by (256 ^ index-of-character).

The very large integer will eventually be stored in blockInt, which starts at 0 on line 45. (This is much like how our previous cipher programs had a translated variable that started as a blank string but eventually held the encrypted or decrypted message by the end of the program.) Line 46’s for loop sets i to be the index of all the characters in message for this block. This index should start at blockStart and go up to blockStart + blockSize (that is, blockSize characters after blockStart) or len(messageBytes), whichever is smaller. The min() call on line 46 will return the smaller of these two expressions.

The second argument to range() on line 46 should be the smaller of these values because each block will always be made up of 128 (or whatever value is in blockSize) characters, except for the last block. The last block might be exactly 128 characters, but more likely it is less than the full 128 characters. In that case we want i to stop at len(messageBytes) because that will be the last index in messageBytes.

The value that is added to the block integer in blockInt is the ASCII value of the character (which is what messageBytes[i] evaluates to) multiplied by (256 ^ index-of-character).

The variable i cannot directly be used for the index-of-character part of the equation, because it is the index in the entire messageBytes object which has indexes from 0 up to len(messageBytes). We only want the index relative to the current iteration’s block, which will always be from 0 to blockSize. This table shows the difference between these indexes:

Table 24-4. The indexes of the full message on top, and indexes relative to the block on bottom.

By modding i by blockSize, we can get the position relative to the block. This is why line 47 is BYTE_SIZE ** (i % blockSize) instead of BYTE_SIZE ** i.

After line 46’s for loop completes, the very large integer for the block has been calculated. We want to append this block integer to the blockInts list. The next iteration of line 43’s for loop will calculate the block integer for the next block of the message.

After line 43’s for loop has finished, all of the block integers have been calculated and are stored in the blockInts list. Line 49 returns blockInts from getBlocksFromText().

The getTextFromBlocks() function does the opposite of getBlocksFromText(). This function is passed a list of block integers (as the blockInts parameter) and returns the string value that these blocks represent. The function needs the length of the message encoded in messageLength, since this information is needed to get the string from the last block integer if it is not a full 128 characters in size.

Just as before, blockSize will default to DEFAULT_BLOCK_SIZE if no third argument is passed to getTextFromBlocks(), and DEFAULT_BLOCK_SIZE was set to 128 on line 9.

The message list (which starts as blank on line 56) will contain a string value for each character that was computed from each block integer in blockInts. (This list of strings will be joined together to form the complete string at the end of getTextFromBlocks().) The message list starts off empty on line 56. The for loop on line 57 iterates over each block integer in the blockInts list.

Inside the for loop, the code from lines 58 to 65 calculates the letters that are in the current iteration’s block. Recall from Chapter 15’s affine cipher program how one integer key was split into two integer keys:

The code in getTextFromBlocks() works in a similar way, except the single integer (i.e. the block integer) is split into 128 integers (and each is the ASCII value for a single character). The way the ASCII numbers are extracted from blockInt has to work backwards, which is why the for loop on line 59 starts at blockSize - 1, and then subtracts 1 on each iteration down to (but not including) -1. This means the value of i on the last iteration will be 0.

The length of the message list will be how many characters have been translated from blocks so far. The if statement on line 60 makes sure the code does not keep computing text from the block after i has reached the end of the message.

The ASCII number of the next character from the block is calculated by integer dividing blockInt by (BYTE_SIZE ** i). Now that we have calculated this character, we can “remove” it from the block by setting blockInt to the remainder of blockInt divided by (BYTE_SIZE ** i). The % mod operator is used to calculate the remainder.

The insert() List Method

While the append() list method only adds values to the end of a list, the insert() list method can add a value anywhere in the list. The arguments to insert() are an integer index of where in the list to insert the value, and the value to be inserted. Try typing the following into the interactive shell:

Using the chr() function, the character that asciiNumber is the ASCII number of is inserted to the beginning of the list at index 0.

After the for loop on line 59 completes, blockMessage will be a list of single-character strings that were computed from the current block integer. The strings in this list are appended to the end of the message list with the extend() method.

After the for loop on line 57 completes, the single-character strings in message are joined together into a single string which is the complete message. This string is then returned from the getTextFromBlocks() function.

The Mathematics of RSA Encrypting and Decrypting

With the numbers for e, d, and n from the public and private keys, the mathematics done on the block integers to encrypt and decrypt them can be summarized as follows:

·        Encrypted Block = Plaintext Block ^ e mod n

·        Decrypted Block = Ciphertext Block ^ d mod n

The encryptMessage() function is passed the plaintext string along with the two-integer tuple of the private key. The function returns a list of integer blocks of the encrypted ciphertext. First, the encryptedBlocks variable starts as an empty list that holds the integer blocks and the two integers in key are assigned to variables n and e.

The pow() Function

While the ** operator does exponents, the pow() function handles exponents and mod. The expression pow(a, b, c) is equivalent to (a ** b) % c. However, the code inside the pow() function knows how to intelligently handle very large integers and is much faster than typing the expression (a ** b) % c. Try typing the following into the interactive shell:

While creating the public and private keys involved a lot of math, the actual math of the encryption is simple. The very large integer of the block created from the string in message is raised to e and then modded by n. This expression evaluates to the encrypted block integer, and is then appended to encryptedBlocks on line 78.

After all the blocks have been encrypted, the function returns encryptedBlocks on line 79.

The math used in the decryptMessage() function is also simple. The decryptedBlocks variable will store a list of the decrypted integer blocks, and the two integers of the key tuple are placed in n and d respectively using the multiple assignment trick.

The math of the decryption on line 90 is the same as the encryption’s math, except the integer block is being raised to d instead of e.

The decrypted blocks along with the messageLength and blockSize parameters are passed getTextFromBlocks() so that the decrypted plaintext as a string is returned from decryptMessage().

Reading in the Public & Private Keys from their Key Files

The key files that makeRsakeys.py creates look like this:

<key size as an integer>,<big integer for N>,<big integer for E or D>

The readKeyFile() function is called to read the key size, n, and e (for the public key) or d (for the private key) values from the key file. Lines 97 to 99 open this file and read in the contents as a string into the content variable.

The split() string method splits up the string in content along the commas. The list that split() returns will have three items in it, and the multiple assignment trick will place each of these items into the keySize, n, and EorD variables respectively on line 100.

Remember that content was a string when it was read from the file, and the items in the list that split() returns will also be string values. So before returning the keySize, n, and EorD values, they are each passed to int() to return an integer form of the value. This is how readKeyFile() returns three integers that were read from the key file.

The Full RSA Encryption Process

The encryptAndWriteToFile() function is passed three string arguments: a filename to write the encrypted message in, a filename of the public key to use, and a message to be encrypted. This function handles not just encrypting the string with the key, but also creating the file that contains the encrypted contents. (The blockSize parameter can also be specified, but it will be set to DEFAULT_BLOCK_SIZE by default, which is 128.)

The first step is to read in the values for keySize, n, and e from the key file by calling readKeyFile() on line 107.

In order for the mathematics of the RSA cipher to work, the key size must be equal to or greater than the block size. The blockSize value is in bytes, while the key size that was stored in the key file was in bits, so we multiply the integer in blockSize by 8 on line 110 so that both of these values represent number of bits.

If keySize is less than blockSize * 8, the program exits with an error message. The user will either have to decrease the value passed for blockSize or use a larger key.

Now that we have the n and e values for the key, we call the encryptMessage() function which returns a list of integer blocks on line 115. The encryptMessage() is expecting a two-integer tuple for the key, which is why the n and e variables are placed inside a tuple that is then passed as the second argument for encryptMessage().

The join() method will return a string of the blocks separated by commas, but join() only works on lists with string values, and encryptedBlocks is a list of integers. These integers will have to first be converted into strings.

The for loop on line 118 iterates through each index in encryptedBlocks, replacing the integer at encryptedBlocks[i] with a string form of the integer. When the loop completes, encryptedBlocks now contains a list of string values instead of a list of integer values.

The list of string values is passed to the join() method, which returns a single string of the list’s strings joined together with commas. Line 120 stores this string in a variable named encryptedContent.

We want to write out more than just the encrypted integer blocks to the file though, so line 123 changes the encryptedContent variable to include the size of the message (as an integer), followed by an underscore, followed by the blockSize (which is also an integer), followed by another underscore, and then followed by the encrypted integer blocks.

The last step is to write out the contents of the encrypted file. The filename provided by the messageFilename parameter is created with the call to open() on line 124. (The 'w' argument tells open() to open the file in “write mode”.) Note that if a file with this name already exists, then it will be overwritten by the new file.

The string in encryptedContent is written to the file by calling the write() method on line 125. Now that we are done writing the file’s contents, line 126 closes the file object in fo.

Finally, the string in encryptedContent is returned from the encryptAndWriteToFile() function on line 128. (This is so that the code that calls the function can use this string to, for example, print it on the screen.)

The Full RSA Decryption Process

The readFromFileAndDecrypt() function, like encryptAndWriteToFile(), has parameters for the encrypted message file’s filename and the key file’s filename. (Be sure to pass the filename of the private key for keyFilename, not the public key.)

The first step is the same as encryptAndWriteToFile(): the readKeyFile() function is called to get the values for the keySize, n, and d variables.

The second step is to read in the contents of the file. The messageFilename file is opened for reading (the lack of a second argument means open() will use “read mode”) on line 138. The read() method call on line 139 will return a string of the full contents of the file.

Remember that the encrypted file’s format has an integer of the message length, an integer for the block size used, and then the encrypted integer blocks (all separated by underscore characters). Line 140 calls the split() method to return a list of these three values, and the multiple assignment trick places the three values into the messageLength, blockSize, and message variables respectively.

Because the values returned by split() will be strings, lines 141 and 142 will set messageLength and blockSize to their integer form, respectively.

The readFromFileAndDecrypt() function also has a check that the block size is equal to or less than the key size. This should always pass, because if the block size was too small, then it would have been impossible to create this encrypted file. Most likely the wrong private key file was specified for the keyFilename parameter, which means the key would not have decrypted the file correctly anyway.

The encryptedMessage string contains many integer characters joined together with commas. Line 150’s for loop iterates over the list returned by the split() method. This list contains strings of individual blocks. The integer form of these strings is appended to the encryptedBlocks list (which starts as an empty list on line 149) each time line 151 is executed. After the for loop on line 150 completes, the encryptedBlocks list contains integer values of the numbers that were in the encryptedMessage string.

The list in encryptedBlocks is passed to decryptMessage(), along with messageLength, the private key (which is a tuple value of the two integers in n and d), and the block size. The decryptMessage() function returns a single string value of the decrypted message, which itself is returned from readFileAndDecrypt() on line 154.

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/hackingpractice24D.

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.

(Remember, prime numbers have no factors besides 1 and themselves. If you multiply two prime numbers, that new number will only have the factors of 1 and itself, and also the two prime numbers.)

So to solve everything and hack the RSA cipher, all we need to do is figure out what the factors are for n. Since there are two and only two numbers that multiply to n, we won’t have several different numbers to choose from. Then we can calculate (p – 1) × (q – 1) and then calculate d. This seems pretty easy. We already have code that finds factors in primeSieve.py’s isPrime() function:

We can just modify this code to return the first factors it finds (since we know that there can be only two factors for n besides 1 and n):

We can just call this function, pass it n (which we get from the public key file), and wait for it to find our factors, p and q. Then we can know what (p – 1) × (q – 1) is, which means we can calculate the mod inverse of e mod (p – 1) × (q – 1), which is d, the decryption key. Then it would be easy to calculate M, the plaintext message.

There’s a problem, though. Remember that n is a number that is around 600 digits long. In fact, Python’s math.sqrt() function can’t even handle a number that big (it will give you an error message). But even if it could, Python would be executing that for loop for a very, very long time.

Our Sun doesn’t have enough mass to eventually go supernova, but in 5 billion years it will expand into a red giant star and utterly destroy the Earth. Even if your computer was still running then, there’s still no chance that 5 billion years is long enough to find the factors of n. That is how big the numbers we are dealing with are.

And here’s where the strength of the RSA cipher comes from: Mathematically, there is no shortcut to finding the factors of a number. It’s easy to look at a small number like 15 and say, “Oh, 5 and 3 are two numbers that multiply to 15. Those are factors of 15.” But it’s another thing entirely to take a (relatively small) number like 178,565,887,643,607,245,654,502,737 and try to figure out the factors for it. The only way we can try is by brute-forcing through numbers, but there are too many numbers.

It is really easy to come up with two prime numbers p and q and multiply them together to get n. But it is reasonably impossible to take a number n and figure out what p and q are. These facts make the RSA cipher usable as a cryptographic cipher.

Summary

That’s it! This is the last chapter of the book! There is no “Hacking the RSA Cipher” chapter because there’s no straightforward attack on the mathematics behind the RSA cipher. And any brute-force attack would fail, because there are far too many possible keys to try: the keys are literally hundreds of digits long. If you had a trillion buildings each with a trillion computers that each tried a trillion keys every nanosecond, it would still take longer than the universe as been in existence to go through a fraction of the possible keys. (And the electric bill for all those computers would bankrupt every industrialized nation on the planet.)

That’s a lot of possible keys.

The RSA algorithm is a real encryption cipher used in professional encryption software. When you log into a website or buy something off the Internet, the RSA cipher (or one like it) is used to keep passwords and credit card numbers secret from anyone who may be intercepting your network traffic.

Actually, while the basic mathematics used for professional encryption software are the same as described in this chapter, you probably don’t want to use this program for your secret files. The hacks against an encryption program like rsaCipher.py are pretty sophisticated, but they do exist. (For example, the “random” numbers returned from random.randint() aren’t truly random and can be predicted, meaning that a hacker could figure out which “random” numbers were used for the prime numbers of your private key.)

You’ve seen how all the previous ciphers in this book have each been hacked and rendered worthless. In general, you don’t want to write your own cryptography code for things you want to keep secret, because you will probably make subtle mistakes in the implementation of these programs. And hackers and spy agencies use these mistakes to hack your encrypted messages.

A cipher is only secure if everything but the key can be revealed but still keep the message a secret. You cannot rely on a cryptanalyst not having access to the same encryption software or knowing what cipher you used. Remember Shannon’s Maxim: The enemy knows the system!

Professional encryption software is written by cryptographers who have spent years studying the mathematics and potential weaknesses of various ciphers. Even then, the software they write is inspected by other cryptographers to check for mistakes or potential weaknesses. You are perfectly capable of learning about these cipher systems  and cryptographic mathematics too. It’s not about being the smartest hacker, but spending the time to study to become the most knowledgeable hacker.

I hope you’ve found this book to be a helpful start on becoming an elite hacker and programmer. There is a lot more to learn about programming and cryptography than what is in this book, but I encourage you explore and learn more! One great book about the general history of cryptography that I highly recommend is “The Code Book” by Simon Singh. You can go to http://invpy.com/morehacking for a list of other books and websites to learn more about cryptography. Feel free to email me your programming or cryptography questions at [email protected].

Good luck!