Introduction to Cryptography

The art of scrambling messages has actually been in use for thousands of years. However, beginning with the development of the telegraph during the latter part of the 1800’s, cryptography has been growing outside of military and highly diplomatic circles, and into the public domain. E-commerce, personal and corporate privacy have continued the pervasive need for secure communications. Additionally, cryptographic techniques are not limited to the purpose of hiding messages, for instance, archeologists can use cryptographic techniques to interpret ancient or lost languages.

Cryptography, which derives from the Greek word kryptos meaning hidden, is both an art and a science. The field of study that cryptography is a part of is called cryptology. There are two forms of secret communication cryptography and steganography. Cryptography is the making of a cipher system and the breaking of a cipher system is called cryptanalysis. Steganography is the art of hiding a message within another cover message. The main thrust of cryptography uses two general scrambling techniques, transposition, where each symbol maintains its identity but changes its position and substitution, where each symbol maintains its position but changes its identity. Modern cryptography also consists of asymmetrical techniques, where for a given encryption key the corresponding decryption key is different. Unfortunately, there does not exist a mathematical proof for security, thus it is currently impossible to achieve absolute security. Proof of security is usually reduced to some other problem known to be extremely difficult to solve, such as the factorization of large numbers.

There exist three fundamental parts to the encryption/decryption process the message, a key and an algorithm. Currently, as per Kerckhoff’s Principle, the algorithm can be disclosed to the public, but keeping the key secret during actual encryption and decryption of a message is the most significant aspect to effective cryptography. One of the challenges of maintaining secure communications is key management. As the number of users and messages increase the more keys are used, thus increasing the chance of making mistakes or exposing patterns and vulnerabilities. Security requires four fundamental services integrity, confidentiality, authentication and nonrepudiation. Security attacks can be either passive, such as eavesdropping or active, such as modifying a message, and exist in four general categories interruption, interception, modification and fabrication.

Cryptography requires problems that are computationally hard so that scrambled messages are hard to break without the correct key. Checking whether or not a key is correct is easily verifiable, which might suggest that cryptographic problems are class NP problems. However, cryptographic strength does not relate to NP-complete problems because NP-complete problems deal with difficulty in the worst case, which means that the problem may be easily solvable in all other cases. Complexity for cryptography requires analyzing best case solutions, such that a candidate for a cipher system would be difficult in the best case to solve, thus not being concerned with worst case complexity. Hence, a cipher system requires that average case complexity needs to be difficult, to achieve a cipher system that is practically unbreakable.

A futuristic implication of complexity theory for cryptography is quantum computing, or better known as quantum cryptography. Quantum computers behave in accordance with quantum physics, which defy the laws of classical physics. A quantum computation consists of quantum particles known as photons or qubits, which are analogous to bits in a classical computer, for representing information. The main idea behind quantum computing is the superposition of qubits that can take on the values 1 and 0 simultaneously. This would mean that current brute force algorithms could run in a single step because a quantum computer can compute all possibilities at once. This would further imply that the power could shift back to the cryptanalysts because all known modern day cipher systems such as RSA could be broken by a quantum computer. However, cryptographers could also utilize quantum computing to build stronger crypto-systems as well.

Chinese Remainder Theorem

http://bletchleypark.net/cryptology/Chinese_Remainder_Theorem.html

Euclid’s Algorithm

http://bletchleypark.net/cryptology/Euclids_Algorithm.html

Fermat’s Theorem

http://bletchleypark.net/cryptology/Fermats_Theorem.html

Prime Numbers

http://bletchleypark.net/cryptology/Prime_Numbers.html

Number Theory

http://bletchleypark.net/cryptology/Number_Theory.html

Cryptanalysis

“The attackers find a buffer overflow and never bother attacking the cryptography. …however, … An attacker who breaks the cryptography has a low chance of being detected.” – Bruce Schneier.

Introduction

Cryptanalysis is the arduous work of breaking a cipher system. Cryptanalysis has its roots in around 650 AD during which theologians wanted to verify the authenticity of ancient manuscripts by comparing the consistency of various words. However, true cryptanalysis probably began in Europe. In fact, one of the most famous cryptanalytic successes occurred in the late 1500’s in England, leading to the arrest and execution of the Mary Queen of Scots for treason. Historically, the most common form of cryptanalysis is frequency analysis, which is basically counting the amount of each letter or symbol that occurred in an encrypted message and comparing those amounts with a table of average, normal, language frequency of letters for plaintext messages.

http://bletchleypark.net/cryptology/cryptanalysis.html