Skip to main content

Public Key Cryptography ~ Concise and Simple

(As with all "concise and simple" articles I assume no prior knowledge of the subject and keep the length to less than 1500 words.)

Sometimes people need privacy: intimate declarations of love, doctors discussing a patient, engineers developing a new top secret world changing product and journalists planning an exposé of government corruption are just a few scenarios where privacy is both a reasonable and legitimate requirement.

This need extends to our digital lives. For example, sensitive credit card information is privately shared to complete on-line purchases. Furthermore, you may be that lover, doctor, engineer or political journalist in need of private communication via the Internet. Maybe you simply don't like the idea of others reading your personal digital communications.

Public key cryptography is probably the most widespread solution to ensure privacy on-line. This article briefly explains what it is and how it works before concentrating on its uses.

Cryptography is the study and application of techniques that secure communication in the presence of third parties (some of whom may wish to eavesdrop). It is traditional to identify the various parties involved in a cryptographic communication as Alice (the sender), Bob (the recipient) and Eve (the [sometimes nefarious] eavesdropper). In the specific case of communications sent via the Internet, messages may be handled by a large number of intermediary devices en-route to their destination. Any of these intermediaries may read the content of the message; in fact, they may need to in order to correctly route it to the intended recipient. To put it another way, the Internet is a public broadcast mechanism and its constituent devices are all Eve.

Eve explains why she's interested in Alice and Bob's communication.

To overcome this problem, the meaningful content of messages (usually called the plaintext) is encrypted (in to something called the ciphertext) before being sent via the Internet. Such content appears as gobbledegook to devices handling the message on its journey to the recipient. Once received the recipient decrypts the ciphertext to retrieve the original meaningful plaintext message.

The process of encryption and decryption is done by a cipher - instructions that explain how to transform plaintext into ciphertext. An additional secret key, known only to the sender and recipients, is also used by the cipher to ensure only those with the key can read such communication.

Within a computing context the plaintext, ciphertext and key are all digital assets - things that are ultimately represented by binary values. In other words, such assets are merely very large numbers. Therefore, the cipher is only a mathematical function. It encrypts by using the key (a number) to turn the plaintext (a number) into the ciphertext (also a number). Decryption is similar in that it uses the key to turn the ciphertext into the original plaintext.

For cryptography to work both sender and receiver[s] must share information about the cipher and key to be used for secure communication. This presents a problem: how should Alice and Bob share such fundamental information? Any communication between them at this stage is insecure because they are yet to share and agree upon the cryptographic means for secure communication. Furthermore, Eve may be listening in to intercept such details and could use what she learns to listen in on the supposed secure communication. Alice and Bob find themselves in a crypto-chicken-and-egg situation.

This is where public key cryptography provides an elegant solution. Rather than use a single key, participants have two: a public key that they share with the whole world and a private key that they keep for themselves. Because of the mathematical relationship between the two keys it is only possible to decrypt a ciphertext with the other key in the pair. If Alice wants to send information to Bob she uses Bob's public key to encrypt her message and sends the resulting ciphertext. Importantly, only Bob can decrypt the message since only his private key can turn the ciphertext into plaintext. Eve can observe the complete exchange without gaining the information she needs to decrypt the message from Alice to Bob because Bob's private key is never transmitted.

Public key cryptography (specifically the RSA algorithm) is thought secure because it depends upon integer factorization - the process of decomposing a number into its constituent prime-number divisors. In other words, every whole number is the result of multiplying a unique set of prime numbers together. For example, to get the number 12 use 2×2×3. As the number gets larger finding the constituent prime numbers becomes too hard to be solved in a realistic amount of time. Public key cryptography uses two huge prime numbers that result in n, an even longer number whose length is measured in "bits" (the longer the better) and whose value is used by the cipher. Currently, n of 2048 bits length is considered secure given currently available computing power (i.e. given a huge amount of computing power it would still take an inordinate amount of time to crack).

In terms of the modus operandi of public key cryptography, that's about all you need to know without going in to technical details. There are many excellent explanations of how public key cryptography works "under to hood" and constraints of space stop me from going in to more detail. However, the video embedded below provides an engaging and comprehensive explanation and is part of the excellent series Gambling with Secrets by Art of the Problem.

An interesting side effect of public key cryptography is that it can be used to "sign" digital assets to prove provenance or identity. Given that any digital asset is simply a large number it is possible to use a hash function - a means of mapping variable length numbers to relatively small, fixed length numbers - to create a unique "signature" that can be cryptographically verified. Consider the following snippet of Python code (don't worry if you can't program, it's easy to follow):

from hashlib import sha1
my_digital_asset = open('war-and-peace.txt').read()
hash = sha1(my_digital_asset)
print int(hash.hexdigest().encode('hex'), 16)

This simply loads the complete text of War and Peace and uses a hashing algorithm called SHA1 to generate the hash that is printed on the screen as an integer (whole number). The resulting hash for War and Peace is the number:

435515005527869578462696388723361351836071321997289162047109517397984640443675003720894549210723

Alice encodes this number with her private key and sends the resulting signature to Bob. Bob uses Alice's public key to decrypt the signature and retrieve the hash we generated above. Then he attempts to create his own hash of the complete text of War and Peace. If his hash matches Alice's he knows that both he and Alice are referencing the same digital asset. If the text for War and Peace had only one letter changed (either by mistake or because someone was tampering with it) then the hashes would have been different. As Bob knows only Alice has access to her private key, and only Alice's public key can decrypt such a signature then he can trust the provenance of the digital asset "signed" by Alice since only she could have created such a signature with her private key. In this way, Alice can also cryptographically sign her own messages to Bob.

It is important to acknowledge the political aspect of public key cryptography. Politicians, the Police and security services complain that terrorists and criminals use strong cryptography to hide their illegal activities. Laws such as the U.K.'s RIPA give the government and other public authorities (such as the Police or local council) powers to force you to hand over your private keys. When challenged about this curtailment of civil liberties (see article 12 of the UN's Universal Declaration of Human Rights) a common response is, "if you have nothing to hide, you have nothing to fear". This is, of course, a dangerous attitude: the authorities get to decide what "nothing to hide" means and this changes all the time. For example, since the introduction of RIPA the list of authorities empowered by the act has increased four times (in 2003, 2005, 2006 and 2010). How would you feel if the recording industry became an authority and insisted you hand over keys so they can check your audio collection?

An Orwellian prospect if ever there was one.

Finally, development of such cryptographic technology is usually done in public by experts. It is open and public because problems and bugs are spotted quicker. Furthermore, designing and implementing cryptographic systems requires significant domain expertise. This convention ensures there are always freely available, well tested and well designed cryptographic libraries for non-expert programmers to re-use in their projects.

The challenge for programmers and cryptographers is to make the use of strong encryption the norm. It is ubiquitous for on-line financial transactions but most other things (email, web browsing, chat and other such digital interactions) are usually not secured. I suspect this will remain the case until people realise that their on-line life is currently like living in a house with no curtains.

Word count: 1439. Thanks to Terry Jones for typo spotting. Image attribution: © Randall Munroe licensed under a Creative Commons BY-NC licence.

The Internet ~ Concise and Simple

(As with all "concise and simple" articles I assume no prior knowledge of the subject and keep the length to less than 1500 words.)

Have you ever wondered what makes it possible to serve web pages like this one, deliver an email or join a video conference, all seemingly in an instant? The answer is the Internet, a decentralised global network of computers. This article explains what's involved.

Devices on the Internet communicate using different yet related protocols. A protocol is a set of rules and conventions that explain how to communicate information. For example, although nothing to do with the Internet, Morse code is a sort of communication protocol.

Strata - Coyote Buttes, Arizona

For the Internet to work, protocols are layered: each layer provides specific functionality needed to make the complete strata of layers work as a whole. Layers depend upon each other with lower levels providing services for the layers above.

At the very lowest layer are protocols concerning how information is physically sent from one device to another. At the very highest layer are protocols for information sharing systems such as the World Wide Web (WWW or just the "Web"), Email, Internet Relay Chat (IRC) and Voice Over IP to name but a few.

These layers have been formalised by the ISO (International Standards Organisation) as the Open Systems Interconnection model. It has seven layers:

  1. The physical layer describes the physical characteristics of communication. For example, protocols at this level specify voltages, layout of plugs and sockets, radio frequencies and so on depending on the physical medium of communication. A helpful transport based analogy is that it's like describing roads as being made of asphalt, traffic lights as having three colours and certain markings being painted where roads intersect.
  2. The data link layer concerns the transfer of information between neighbouring nodes in a network. Some protocols at this level detect and possibly correct errors that may occur in the physical layer. To continue the transport analogy, this layer is the traffic officer controlling and directing the flow of traffic between adjacent neighbourhoods or the practice of stopping at red traffic lights and understanding who has right of way at a roundabout.
  3. The network layer contains protocols that describe how information should be routed across a network including descriptions of how messages should be forwarded to their intended recipient. Its function is similar to that of a navigator reading a map and listening to traffic reports in order to find the route for a long car journey.
  4. The transport layer gives the impression of linking places on the network for a (usually reliable) exchange of information. This may include error detection and correction, flow control (how much information is sent at a time) and segmentation (how messages are split up in to their constituent parts and re-assembled at the receiving end). This is like being able to send letters: your post box and the recipient's letter box are connected together through the workings of the Post Office (the transport layer).
  5. The session layer defines how communication is opened, closed and managed between devices communicating over the network. For example, if an open line of communication between two devices is interrupted then the protocols in this layer will attempt to reconnect. The concept of "letter" would be defined in this layer along with conventions such as starting letters with "Dear So-and-so".
  6. The presentation layer translates raw data in to something that can be sent over the network. This may include serialising complex data structures into strings of characters or describing the characteristics of the message, such as its total size. It is often at this level that encryption takes place in order to secure communications. This layer is analogous to writing a letter on a piece of paper and putting it in an envelope with an address and stamp on the front.
  7. The application layer involves creating and consuming messages needed for applications that work via the Internet. This includes generating and checking data fields or ensuring the correct structure of the message. This is, perhaps, similar to filling in a tax return with the required information before posting it back to the revenue collector (where the "application" is collection of taxes).

Layers are not the end of the story. Messages are split in to chunks of data, sent over the network and then reassembled at the recipient. Each protocol has a different name for such chunks of data: for example, at the data link layer they are called "frames", at the network layer "packets" and at the transport layer they are called "segments" or "datagrams". Chunks of data from higher level protocols are wrapped within those of the lower levels.

Data chunks contain two types of information: control information and the payload (containing data from the higher level protocols). Control information is used by the protocol to fulfil its function while the payload is handed over to the next protocol up in the layers described above.

Furthermore, each connected device needs to have a unique address so it can be found on the network. These are unique numbers called IP addresses implemented in the network layer, most commonly by the Internet Protocol (IP) - hence the name.

Blocks of numbers are assigned to different "entities" (governments, educational institutions, organisations and companies) by the Internet Assigned Numbers Authority (IANA). Such entities further assign sub-blocks until we arrive at a single IP address assigned to an individual device on the network.

IP addresses generally come in two types reflecting the version of IP that they correspond to: IPv4 and IPv6. The maximum number of IPv4 addresses is 4,294,967,296. While this may sound like a lot of potential addresses I'm afraid we've already run out. As a result IPv6 caters for a huge number of addresses: 340,282,366,920,938,463,463,374,607,431,768,211,456 (that's 2128). The Internet is currently transitioning from IPv4 to IPv6.

Because humans are no good at remembering long numbers we refer to devices connected to the Internet with human-friendly domain names such as bbc.co.uk. Whenever we make a request to a domain we must use the Domain Name System (DNS) to map the domain name to the IP address of the correct device on the Internet (so, looking up the bbc.co.uk domain gives an IP address of a device owned by the BBC). DNS is a distributed lookup service that is organised and run by domain name registrars (with whom you register your ownership of a domain) and policed, via laws and legal interventions, by governments and business interests (such as the RIAA and BPI).

However, any single device may be running several different networked applications at the same time (for example, an email client, a web server or a chat service). Numbered ports on a connected device function in a similar way to numbered mail boxes in a block of flats: applications know to "listen" on specific port numbers for only their messages. Standards dictate how certain port numbers map to particular application protocols. For example, unencrypted requests on the web get sent to port 80.

It is because of the existence of ports that there are many more devices connected to the Internet than there are IPv4 addresses. The Internet is, in fact, a collection of many local networks. Within each local network devices are assigned unique IP addresses but the device that is connected to the wider Internet (called a router) only has a single external IP address. How can the router's single IP address be shared by all the devices on the local network?

The answer is Network Address Translation (NAT) - the router maps an external and unused port to an internal (local) device. For example, all requests to the router on port something-or-other could be simply forwarded to the device on the local network identified by a locally unique (internal) IP address.

Finally, network traffic is policed by firewalls using techniques such as IP address blocking. A firewall is like a border control checkpoint: every chunk of data is examined and either discarded or allowed to pass depending on a set of rules. IP address blocking is a specific example of a firewall rule: blacklist any traffic to or from a specific block of IP addresses (such as those from outside China).

Some firewalls are sophisticated enough to do deep packet inspection where the content of network traffic is examined for the purposes of security, data mining, eavesdropping or censorship. Chunks that are deemed bad are not allowed through. Encrypting messages at the higher levels of the Internet stack go some way to circumventing such measures although traffic analysis (an examination of network behaviour) can be used to infer the intent of a message.

Unfortunately, the details of specific protocols can't be explored in such a short introductory essay. However, if you're interested in finding out more you should investigate the Internet Engineering Task Force's (IETF) database of Requests for Comment (RFC) used to define the various protocols.

And remember, most of the above appears to happen instantaneously to connect computers that could be on opposite sides of the planet - something that fills me with amazement.

1499 words. Image credit: © 2007 rickz under a Creative Commons license.

Concise and Simple

lego instructions

Over the coming weeks I will publish a set of articles that are part of a series called "concise and simple". Each article will be about an area of computing that interests me but will be no longer that 1500 words nor assume previous knowledge of the subject under scrutiny.

I have two aims:

  1. To create resources that may be useful for others.
  2. To explain in a simple yet engaging style the essence of a highly technical subject.

The first aim is an act of community service, the second is a personal challenge.

I hope to publish the first article in the next few days: "The Internet ~ Concise and Simple".

Image credit: &copy 2011 Bill Toenjes under a Creative Commons license.

The Twelve Days of Python

One of my less pleasant pass-times is butchering the English language with dodgy verse. I already have a track record wrangling well known poems for friends or re-hashing libretto for vocal performance.

Last week, in the #python-uk IRC channel, there was discussion of what a Pythonic Christmas carol would look like.

Today, given that it's the season of peace and goodwill to all men (and women), I've decided to ignore that sentiment and publish what is, perhaps, my most diabolical creation yet. I give you, "The Twelve Days of Python" (sung to the tune of... well, I'm sure you can figure it out):

On the first day of Christmas, Guido sent to me..
some code in a Git repos'try.

On the second day of Christmas, Guido sent to me...
two pull requests for my code in the Git repos'try.

On the third day of Christmas, Guido sent to me...
three bug reports, two pull requests for my code in the Git repos'try.

On the fourth day of Christmas, Guido sent to me...
four failing tests, three bug reports, two pull requests for my code in the Git repos'try.

On the fifth day of Christmas, Guido sent to me...
five network pings!
Four failing tests, three bug reports, two pull requests for my code in the Git repos'try.

On the sixth day of Christmas, Guido sent to me...
Six functions calling,
Five network pings!
Four failing tests, three bug reports, two pull requests for my code in the Git repos'try.

On the seventh day of Christmas, Guido sent to me...
Seven ifs-or-elsing, six functions calling,
Five network pings!
Four failing tests, three bug reports, two pull requests for my code in the Git repos'try.

On the eighth day of Christmas, Guido sent to me...
Eight scripts-a-parsing, seven ifs-or-elsing, six functions calling,
Five network pings!
Four failing tests, three bug reports, two pull requests for my code in the Git repos'try.

On the ninth day of Christmas, Guido sent to me...
Nine JITs compiling, eight scripts-a-parsing, seven ifs-or-elsing, six functions calling,
Five network pings!
Four failing tests, three bug reports, two pull requests for my code in the Git repos'try.

On the tenth day of Christmas, Guido sent to me...
Ten templates rend'ring, nine JITs compiling, eight scripts-a-parsing, seven ifs-or-elsing, six functions calling,
Five network pings!
Four failing tests, three bug reports, two pull requests for my code in the Git repos'try.

On the eleventh day of Christmas, Guido sent to me...
Eleven exceptions raising, ten templates rend'ring, nine JITs compiling, eight scripts-a-parsing, seven ifs-or-elsing, six functions calling,
Five network pings!
Four failing tests, three bug reports, two pull requests for my code in the Git repos'try.

On the twelfth day of Christmas, Guido sent to me...
Twelve lists comp'rending, eleven exceptions raising, ten templates rend'ring, nine JITs compiling, eight scripts-a-parsing, seven ifs-or-elsing, six functions calling,
Five network pings!
Four failing tests, three bug reports, two pull requests for my code in the Git repos'try.

Some of the lines I discarded were, "X metaclasses confusing", "X classes inher'ting", "X breakpoints breaking" and "X objects instant'ing". However, even I have standards for writing poetry...

:-)

Northackton and the Useless Machine

When time permits I really enjoy attending Northackton, a local hacker / maker group. Last Monday I took my middle son, Sam (8 years old), along to a meeting advertised as a "geek santa" session - an opportunity for attendees to build a geeky gift for a loved one in time for Christmas.

We were all there to make useless machines - wonderfully quirky devices imagined by Artificial Intelligence pioneer Marvin Minsky and first built by the father of information theory, Claude Shannon.

Between ten to fifteen of us turned up to be greeted by friend-of-Northackton Martin Raynsford. Martin provided us all with kits (also available via his website), instructions, encouragement and a helping hand when required. After a couple of hours we were all the proud owners of a working useless machine! Sam was especially pleased because he had a go soldering and the other attendees were very patient (and welcoming) by answering all his inevitable questions. He was also very impressed with the well provisioned tuck shop (lots of chocolate and crisps!).

But, what is a useless machine..? I'll let Sam explain...

If you ever find yourself in the Northampton area and at a loose end on a Monday evening, visit the Northackton website and check if there's a meeting, come along and say "hi". You could also follow the group on Twitter.