{"id":1235,"date":"2022-09-20T16:56:52","date_gmt":"2022-09-20T21:56:52","guid":{"rendered":"https:\/\/dda.ndus.edu\/ddreview\/?p=1235"},"modified":"2023-04-18T16:22:19","modified_gmt":"2023-04-18T21:22:19","slug":"the-unencrypted-history-of-cryptography","status":"publish","type":"post","link":"https:\/\/dda.ndus.edu\/ddreview\/the-unencrypted-history-of-cryptography\/","title":{"rendered":"The Unencrypted History of Cryptography"},"content":{"rendered":"\n

It is 58 B.C. and a Roman general sits atop a hill studying the opposing army, consisting of warriors from several Gallic tribes, in what is now a forested area on the eastern side of central France. He receives a message from Julius Caesar, his commander, and is quite certain no one else has read it. <\/p>\n\n\n\n

Jenny logs into her bank account using her password. She is quite certain no one else can read her account balance or uncover her account number. <\/p>\n\n\n\n

Kevin makes a purchase using his debit card and pin number. Again, he and his bank can be certain no one else is making this transaction. <\/p>\n\n\n\n

What do these three situations have in common? All three involve some sort of secret sharing scheme. The study of secret sharing is known as cryptography. In this article, I will take you on a historical journey through this fascinating subject. In a future article, I will go over more of the science of cryptography.<\/p>\n\n\n\n

\"\"
Metal type for newspaper printing, arranged to illustrate a Caesar Shift, courtesy of the Braddock Letterpress Museum in Braddock, ND. The museum is a collaborative effort between the town of Braddock (population 16) and the Emmons County Record, the local newspaper. The museum shop is setup to look and operate as a weekly newspaper from 1885 to 1920, featuring vintage equipment, such as the 1891 Walter Scott Pony Press. Visitors can see the presses at work during the Annual South Central Threshing Bee on the weekend after Labor Day.<\/figcaption><\/figure>\n\n\n\n

Caesar Shift <\/h1>\n\n\n\n

One of the first recorded secret-sharing schemes is known as the Caesar Shift. The idea is to take a message and shift each letter in the text three places (or any number 1-25) forward or back in the alphabet: A\u2192D, B\u2192E, M\u2192P, Z\u2192C and then A\u2192D again. The security is given by the key, which is how many places to shift the letters. Then anyone knowing the key can quickly read the message. <\/p>\n\n\n\n

The Caesar Shift, while neat, is not very secure. In times of less literacy, it was secure, but in modern times it falls quite quickly to frequency analysis, using the fact that all letter As get encoded by the same letter (D) each time. This results in the relative frequencies of the letters and words staying the same: E is the most common letter\u2014which would be H in this Caesar Shift. Similarly, \u201ca,\u201d \u201can\u201d and \u201cthe\u201d are the most common words, which would become \u201cd,\u201d \u201cdq\u201d and \u201cwjh.\u201d <\/p>\n\n\n\n

Vigen\u00e8re Cypher<\/h1>\n\n\n\n

The next step forward in cryptography was the Vigen\u00e8re Cypher\u2014chronicled first in 1553 by Giovan Battista Bellaso but then miscredited to another 16th century cryptographer Blaise de Vigen\u00e8re\u2014which uses a key word to shift the letters of the message. For example, if we pick the key word \u201cdance,\u201d we would obtain a shift key of 4, 1, 14, 3, 5. Given the message \u201cmeet at noon,\u201d we would shift the first letter by 4, the second by 1, the third by 14, the fourth by 3, the fifth by 5, and then repeat: the sixth by 4 and so on. The advantage here is that two occurrences of E would be encoded differently, hence the frequency analysis would not be quite as effective. <\/p>\n\n\n\n

\"\"
Metal type for newspaper\nprinting, arranged to illustrate\nthe Vigen\u00e8re cypher, courtesy\nof the Braddock Letterpress\nMuseum in Braddock, ND.\nSince 2016, students taking\nthe Intro to Publishing\ncourse at NDSU typically\ntravel to the museum to learn\nabout moveable type and\nexperience operating the\nChandler & Price letterpress.\nMany pieces of letterpress\nequipment were donated\nby the Borlaug family\nnewspapers, which were\npublished in Washburn, ND.<\/figcaption><\/figure>\n\n\n\n

As is the case with the Caesar Shift, there are known attacks on the Vigen\u00e8re Cypher which are very effective at breaking it. They can be done by hand with some work. <\/p>\n\n\n\n

With the Vigen\u00e8re Cypher, we begin to see how mathematics was applied to early cryptography. We can replace letters with their equivalent place in the alphabet, then with the key word, this becomes a sequence of shift numbers. The next step is to add each key letter into the plain text letter. If the result is more than 26, we do \u201cclock arithmetic\u201d and subtract 26 to obtain a result between 1 and 26. What we mean here is the following: If we have the letter Y it corresponds to the number 25. If we then us the key letter D, corresponding to 4 we add 4 to 25 to obtain 29. The challenge is that 29 is not in our list of 1-26. So what we do is subtract 26 to obtain 3, which is then the code letter C. <\/p>\n\n\n\n

Enigma <\/h1>\n\n\n\n

The mathematical nature of cryptography developed through the centuries such that cyphers become entirely mathematical by World War II, during which there were significant advancements in cryptography and cryptanalysis (the study of cryptosystems). The Germans developed an entirely new machine and encryption\/decryption system called Enigma. This was no ordinary substitution cypher. Enigma relied on three wheels, each of which was a permutation cypher; a plug board, which was another permutation; and a reflector. <\/p>\n\n\n\n

When a key was pressed on the Enigma machine the letter was passed through the plugboard, then through each of the three permutation discs, hit the reflector, back through the permutation discs, then to a light board showing the encrypted letter. Then when the next key was pressed, the first wheel was rotated so that it aligned with the other two differently. Hence the entire system changed a bit. <\/p>\n\n\n\n

\"\"
The Enigma machine is a cypher device used extensively by the Nazi Armed Forces during World War II to encrypt and decrypt top-secret messages.<\/figcaption><\/figure>\n\n\n\n

The Germans thought that this code was unbreakable. But three Polish mathematicians, after a few weeks of listening to German radio communication, were able to not only break the codes but build a machine similar to what the Germans had without ever seeing it. They then went on to build a machine to break the codes called the bomba kryptologiczna<\/em> or cryptologic bomb.<\/p>\n\n\n\n

Shortly before Poland was invaded, these three mathematicians presented their work at a conference to French and British cryptographers. Thus, they passed on their knowledge of not only how the codes worked but how to break them. Alan Turing used the information from the Polish cryptographers to develop the British Bombe, the electromechanical device used to break the enigma codes throughout the war. Many historians believe that knowing how to break the codes shortened the war by at least two years. <\/p>\n\n\n\n

The Cold War<\/h1>\n\n\n\n

A new era of cryptography began after World War II at the start of the Cold War. Information security was considered an absolute necessity by the U.S. and USSR. Both countries set up agencies dedicated to information security and warfare. Cryptography entered the academic research mainstream.<\/p>\n\n\n\n

The U.S. developed the Data Encryption Standard (DES) for secret communications, which was deployed from 1979 to 2005. DES uses a 56-bit key (a string of 56 zeroes and ones) and works on block lengths of 64 bits. DES is considered insecure by modern standards because the encryption is easily broken.<\/p>\n\n\n\n

Advanced Encryption Standard<\/h1>\n\n\n\n

In 2000, the Advanced Encryption Standard (AES) replaced DES. AES also works on blocks of data and can accept keys up to 256 bits in length. Currently, AES serves as the standard for encryption in the U.S. and many parts of the world. It is used heavily in internet communication because it is fast and secure. <\/p>\n\n\n\n

Security Concerns<\/h1>\n\n\n\n

All the codes mentioned so far are termed symmetric cyphers, meaning that both the sender and receiver need to have the same key to encrypt and decrypt messages. This poses a challenge in that some other communication method must be used to share the secret keys since the internet might not be insecure. Embassies, for example, relied on DES for decades. Diplomats used diplomatic pouches\u2014which by international agreement, cannot be opened at border crossings\u2014to deliver secret keys to and from their governments to their embassies and consulates. <\/p>\n\n\n\n

The underlying reason for this is a fundamental of cryptography, Kerckhoffs\u2019s principle (after a 19th-century Dutch linguist and cryptographer) states: A cryptosystem should only depend on the key, not on the algorithm used. What this means is that a secure cryptosystem should be able to share how it works with any user, including the attacker, but should still be secure as long as the key is kept secure. Another way to say this is: \u201cSecurity through obscurity is not security.\u201d That is, all security systems should be secure even if publicly known. As a corollary to Kerckhoffs\u2019s principle and this statement is that the more secrets a security system has, the more vulnerabilities it also possesses.<\/p>\n\n\n\n

Both DES and AES are public algorithms in that how they work is completely known. This allows for any cryptographer to study the algorithm and see if flaws can be found. A fundamental rule of cryptography is that anyone can make a system that he or she can\u2019t break, but, no matter how complex, someone else might be able to break the system. <\/p>\n\n\n\n

So, DES and AES satisfy Kerckhoff\u2019s principle in that the only piece of information that is needed for the system to be secure is the key. <\/p>\n\n\n\n

One-Time Pad<\/h1>\n\n\n\n

The ultimate in security is given by the one-time pad. Here the secret key is at least as long as the message. What we want the key to be is as random as possible, in order that an eavesdropper not only can\u2019t read the message but can\u2019t tell that it\u2019s a message in the first place\u2014analogous to background noise in electric transmissions. The key is then used to encrypt the message letter by letter. The result, if the key indeed looks like noise, is a message that appears to be random noise. Any plain text of the same length as the encrypted text is just as likely. As an example, if we encode \u201ctruth\u201d using a particular one time pad we might obtain the cypher text \u201cAQHBT\u201d. Now if we know the key, we easily obtain our original message. But it turns out that without the correct key, a different key could give any other five letter word, such as \u201cwhose.\u201d As a result, the one-time pad provides the highest level of security. <\/p>\n\n\n\n

Key Exchange and Public Key Cryptography<\/h2>\n\n\n\n

The challenge for the one-time pad is that both sides need to have obtained the same secret key somehow. In 1976, two researchers from Stanford University, Whitfield Diffie and Martin Hellman, published a paper that revolutionized cryptography and made encryption across the internet possible. In this paper, they introduced the notion of public key cryptography. <\/p>\n\n\n\n

Public key cryptography is different than symmetric key cyphers (where the encryption and decryption keys are the same) in that there are two different keys, one for encryption and one for decryption. A user is then able to publish his or her encryption key that anyone can use to encrypt messages. The message is then decrypted using the decryption key or private key. <\/p>\n\n\n\n

While they didn\u2019t have a public key cryptosystem, they did publish a method for two people to develop a key across an insecure channel. Using this key exchange, two users can have the same private key that an observer cannot obtain by any known method except brute force (testing all possibilities), which would take thousands of years. The two users would then use an agreed-upon symmetric algorithm like AES.<\/p>\n\n\n\n

RSA<\/h1>\n\n\n\n

Public key cryptography became a reality with the development of a new algorithm by Rivest-Shamir-Adleman known as RSA. The math behind RSA is not terribly difficult and is accessible to an advanced high school student. However, without the secret numbers\u2014two secret numbers (prime numbers of 200 digits or more) are chosen to generate the private key\u2014it is very difficult to generate the private key from the public key, unless one has thousands of years of computer time available.<\/p>\n\n\n\n

Elliptic Curve Cryptography<\/h1>\n\n\n\n

The next major advancement in public key cryptography came in the form of elliptic curves (y2=x3+ax+b). In the xy-plane, shown in the graph below, elliptical curves are well behaved, but in clock arithmetic they act somewhat randomly, which makes them quite adept at generating secret keys. Using surprisingly simple math equations, we can produce these common secret keys. This key-exchange algorithm has become the standard at many websites, including Google and Wikipedia. <\/p>\n\n\n\n

The magic of elliptic curve cryptography is that the key size is significantly shorter than the RSA keys. As a comparison, an elliptic curve key of length 256 bits is equivalent to an RSA key of 4096 bits. Further, the algorithm is very fast.<\/p>\n\n\n\n

Digital Signatures <\/h1>\n\n\n\n

One fascinating facet of all current public key algorithms is that the public key and private key can be applied in any order. This allows for signing of documents. What the user does is apply his or her private key to the document to \u201csign\u201d it. Anyone can then verify the signature by applying the appropriate public key. Two users can sign the same document by applying their private keys in succession. Then again, the signatures can be verified by applying the appropriate public keys. <\/p>\n\n\n\n

\"\"
Elliptic Curve Cryptography: The elliptic curve, y2=x3-2x+4I, is all points (x,y) satisfying this equation. The curve (the red line) is symmetric about the x-axis because of the y2 term. The second step involves point addition on elliptic curves: Choose two points, P and Q, and draw a line between them. One property of elliptic curves is that this then crosses the curve exactly once. Take this new point and reflect it across the x-axis to arrive at R = P+Q. This \u201caddition\u201d property is essential to elliptic curve cryptography. The third step involves an elliptic curve in clock arithmetic, which produces a random distribution of points that renders a specific message indistinguishable from any other message of the same length.<\/figcaption><\/figure>\n\n\n\n

Bitcoin<\/h1>\n\n\n\n

The bitcoin algorithm uses elliptic curve cryptography in its implementation. What bitcoin is at its core is a ledger of how much bitcoin an account has. The accounts are given by public keys of the elliptic curve cryptosystem. When a user wants to spend their Bitcoin, they specify a different account and then sign the transaction with their private key. Anyone can verify this is a legitimate transaction by applying the public key to the transaction. There is more that goes into the algorithm, but this is the heart of how transactions work. <\/p>\n\n\n\n

Protection vs Security & Privacy <\/h1>\n\n\n\n

The American public is heavily reliant on cryptography for day-to-day functions. From securely browsing the internet, to chip-and-pin transactions on debit cards, or chip-only transactions with credit cards. Further, there are many chat programs that rely on cryptography to keep the user\u2019s messages secure from eavesdroppers.<\/p>\n\n\n\n

Currently, however, there is legislation under consideration in Congress, which according to many experts unintentionally puts digital privacy at risk for private citizens and the business and industry sectors. <\/p>\n\n\n\n

The EARN IT Act was originally introduced in 2020 with the aim of protecting children from online sexual exploitation. Strong public opposition and pushback from human rights organizations caused the bill to be shelved. Then the bill was re-introduced to the U.S. Senate in February 2022 and soon endorsed by the National Center for Missing and Exploited Children and the National Center on Sexual Exploitation. The bill would create a National Commission on Online Child Sexual Exploitation Prevention with laudable goals. <\/p>\n\n\n\n

The problem is that implementation would almost certainly grant the government access to end-to-end encryption in order to identify, track and prosecute criminals. End-to-end encryption is fundamental to privacy for email providers and security for business communications, which often involve highly sensitive data. Legislating backdoors to this encryption will allow access without notification not only to government agencies, including law enforcement, at the local, state and federal levels\u2014but worse, the backdoors will also enable hackers to gain the same access.<\/p>\n\n\n\n

In short, privacy and security in digital services and communications will be irreparably shattered. Not surprisingly, the government will be exempt from these measures. The Electronic Frontier Foundation criticized the EARN IT Act as \u201ca direct threat to constitutional protections for free speech and expression.\u201d In a poll this July from AXIS Research, respondents identified privacy (21 percent) as the top issue Congress should focus on concerning tech-related issues. Protecting children online certainly concerns voters but ranked third at 11 percent.<\/p>\n\n\n\n

The choice between privacy and protection, unfortunately, is a fundamental either\/or. There is no legislative fence to land on; encryption\u2019s backdoor is open or shut, never slightly ajar. \uf0aa<\/p>\n\n\n\n

Further Reading<\/h1>\n\n\n\n

If you are interested in learning more about cryptography, there are a few excellent texts available:<\/p>\n\n\n\n

Serious Cryptography<\/em> by Jean-Philippe Aumasson is accessible to many but has some technical details.<\/p>\n\n\n\n

For those more interested in the algorithms, I recommend the classical text Applied Cryptography<\/em> by Bruce Schneier.<\/p>\n\n\n\n

The mathematics behind the algorithms is discussed in Introduction to Cryptography with Coding Theory<\/em> by Wade Trappe and Lawrence Washington.<\/p>\n\n\n\n

For more information on Kerckhoffs\u2019s principle, see this article: https:\/\/www.schneier.com\/crypto-gram\/archives\/2002\/0515.html#1<\/a><\/p>\n\n\n\n

Lastly, I will be teaching a course on cryptography through the Dakota Digital Academy and Dickinson State University in the spring of 2023. <\/p>\n","protected":false},"excerpt":{"rendered":"

It is 58 B.C. and a Roman general sits atop a hill studying the opposing army, consisting of warriors from several Gallic tribes, in what is now a forested area […]<\/p>\n","protected":false},"author":44,"featured_media":1318,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[285,20,4,278],"tags":[431,428,420,444,440,423,427,419,429,418,424,417,259,430,439,441,438,426,422,103,432,435,442,443,433,436,437,421,434,425],"_links":{"self":[{"href":"https:\/\/dda.ndus.edu\/ddreview\/wp-json\/wp\/v2\/posts\/1235"}],"collection":[{"href":"https:\/\/dda.ndus.edu\/ddreview\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dda.ndus.edu\/ddreview\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dda.ndus.edu\/ddreview\/wp-json\/wp\/v2\/users\/44"}],"replies":[{"embeddable":true,"href":"https:\/\/dda.ndus.edu\/ddreview\/wp-json\/wp\/v2\/comments?post=1235"}],"version-history":[{"count":5,"href":"https:\/\/dda.ndus.edu\/ddreview\/wp-json\/wp\/v2\/posts\/1235\/revisions"}],"predecessor-version":[{"id":1369,"href":"https:\/\/dda.ndus.edu\/ddreview\/wp-json\/wp\/v2\/posts\/1235\/revisions\/1369"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/dda.ndus.edu\/ddreview\/wp-json\/wp\/v2\/media\/1318"}],"wp:attachment":[{"href":"https:\/\/dda.ndus.edu\/ddreview\/wp-json\/wp\/v2\/media?parent=1235"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dda.ndus.edu\/ddreview\/wp-json\/wp\/v2\/categories?post=1235"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dda.ndus.edu\/ddreview\/wp-json\/wp\/v2\/tags?post=1235"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}