How can maths be used in code cracking and how does the methodology differ?

Name:
Professor:
Subject:
Date:
USE OF MATHEMATICS IN CODE BREAKING
INTRODUCTION
Human beings have always needed for secret communications through public channels. The message has to be transformed to form that cannot be read to facilitate secret communication. The message that is unreadable is called a coded message. In technical terms, the original message is the called the plaintext while the unreadable message is called the ciphertext. The conversion of plaintext to ciphertext is called encryption while the conversion of ciphertext to plain text is called decryption. The process of encryption and decryption is called cryptography. The process of cryptography involves coming up with a method of converting the plaintext to ciphertext and recovering the plaintext from the ciphertext.
Cryptography is today used in to secure communication is phones, credit card information, PIN, and password used in web accounts. A cryptographic system is said to be secure when the plaintext cannot be deduced from the ciphertext. The process of trying to determine the plaintext from ciphertext through analysis of the cipher or the ciphertext is called cryptanalysis. In non-technical English is known as code breaking. Code breaking employs techniques from various fields of mathematics such as statistics, number theory, and differential calculus. Math is applied in identifying the extent to which a system is vulnerable, the probability of success in a certain algorithm and the actual cracking of the code.

CRYPTOGRAPHY
To appreciate the mathematics of code-breaking, first, we need to understand the various techniques used in cryptography. These are hashing, symmetric key cryptography, and public key cryptography. Hashing involves irreversibly changing the plaintext using a hashing function, which is an algorithm that is used to convert the plaintext to the ciphertext. In cryptography, a key is a parameter that is used with the algorithm to produce the ciphertext from the plaintext. When the key is known, then the message can be decrypted. A system that uses the same key in encrypting and decrypting messages is called symmetric key cryptography. On the other hand, a system that uses different keys for encryption and decryption is known as public key cryptography (Courtois et al. 13). The diagram below shows the general structure of a symmetric key cryptosystem. The eavesdropper is the codebreaker since they want the plaintext but do not have the key.
In hash function cryptography, a word known as a hash is used to represent a message. The hash is a fixed length and should be adequate in representing the message. The number of hashes is always smaller than the number of messages hence in some instances the same hashes may be produced. This is called a collision. To illustrate hash functions we use communications between two parties A and B. For them to communicate they have to share a secret value SAB. When A needs to send a message to B, it calculates the hash function by concatenating the secret value of the message. This yields MDM = H(SAB║║ M. A then sends M [MDM] to B. Since SAB, is possessed by both A and B, B can recompute H (SAB7 M) and verify the message digest. Since the secret value is not transmitted, the attacker is not able to modify the message even if they can intercept it. The secrecy of the message is guaranteed by the confidentiality of the key. Below is a diagram that illustrates how hash functions are used (Stinson 56).
In hash function cryptography, a word known as a hash is used to represent a message. The hash is a fixed length and should be adequate in representing the message. The number of hashes is always smaller than the number of messages hence in some instances the same hashes may be produced. This is called a collision. To illustrate hash functions we use communications between two parties A and B. For them to communicate they have to share a secret value SAB. When A needs to send a message to B, it calculates the hash function by concatenating the secret value of the message. This yields MDM = H(SAB║║ M. A then sends’M MDM] to B. Since SAB, is possessed by both A and B, B can recompute H (SAB7 M) and verify the message digest. Since the secret value is not transmitted, the attacker is not able to modify the message even if they can intercept it. The secrecy of the message is guaranteed by the secrecy of the key. Below is a diagram that illustrates how hash functions are used (Stinson 56).
Symmetric Key Cryptography involves a system where the sender has a key which is shared with the receiver. The sender uses them to encrypt the message, and the receiver uses the same key to decrypt the message. The requirements for secure symmetric cryptography are needed for a robust algorithm for encryption and a reliable way of sending the key from the sender to the receiver. A good algorithm implies that even if an attacker now the algorithm, and has access to the ciphertext; they should still be unable to get the plaintext. Without the key, the attacker should not be able to decrypt the ciphertext text even if they know the algorithm and hare in possession of some plaintext/ciphertext pairs. Similarly there sharing of the key has to be in a secure fashion since the key if the key can be discovered, all the communication is accessible to an attacker.
The most common algorithms used in Symmetric key cryptography are the DES, AES and triple DES used in block ciphers.
Public key cryptography is based on two keys. The sender generates a pair of keys that will be used for the encryption and decryption of the message. One of the keys is called a private key, and the other is the public key. The public key is placed in a public register so that each recipient of the sender s message can use the public key n decrypting the message sent. The retained private key is the one used by the sender in encrypting the message. When one receives a message, they decode it using their private key. No one else can decrypt a message intended for someone since they do not have their private key. Unlike the symmetric key system, both the encrypting and decrypting keys are generated locally, and there is no need for transmission of the key. The algorithms used in public key system are mathematically rigorous and not simple operations as those used in symmetric key cryptography. These algorithms include an elliptic curve, Diffie-Hellman algorithm, RSA, and DSS (Schaeffer 34).
CRYPTANALYSIS AND ATTACKS ON CRYPTOGRAPHIC SYSTEMS
To To break the code, various methods may be used. One is the known plaintext (KP), another is the chosen plaintext (CP), and the third is called, the ciphertext-only attack (CO). In the known plaintext attack, the attacker has only the plaintext and tries to determine the cipher given the ciphertext/plaintext pair. The ciphertext-only attack is where the attacker has only the ciphertext and tries to deduce the plaintext from that. The chosen plaintext is a less practical situation where the attacker has access to the cipher and may use the cipher to generate plaintext/ciphertext pairs from which he may break the cipher.
There are several forms of attacks that may be launched against a cryptographic system. Since mode cryptography is purely based on mathematics, code-breaking equally relies on extensive use of mathematics. Math is used to determine the ability of the attacker to break the cipher, the computational capacity required to break the cipher and even developing algorithms to break the cipher. There are various methods of code-breaking these methods are categorized depending on the technique of cryptography used. These broad categories include classical cryptanalysis, symmetric algorithms, and hash function attacks. These attacks may be implemented in various scenarios and models discussed previously. We shall look into two attacks, one classical attack on the affine cipher and another attack on the hash function which is based on probability and statistics.
Attacking the affine cipher
To demonstrate how mathematics is used in cryptanalysis, first, we have to demonstrate how the cryptographic system is implemented. For this illustration, we will use a classical cryptographic technique known as affine/Caesar’s. The cipher and the cryptanalysis of this system use number theory. In the affine system the message i is encrypted in the following manner:
ek1i=(ai+b, mod M)Where a and b are integers. A has an inverse of class c modulo M. The key used for encryption k1 is formed by the (a,b) pair while the key used in the decryption k2 is formed by the (c,b) pair. The decryption is done in the following manner.
ek1i=(ai+b, mod M)This method of encryption usually has very few possible keys and may be attacked by ciphertext-only attack if there is some structure in the message. This attack can be done by checking the possible keys one by one to find the plaintext. Frequency tables can also be used to find structure in the data and in that manner, the problem can be made to a known plaintext attack when specific parts of the plaintext are found such as the most common letter. For a known plaintext attack, it is adequate to find two message symbol-crypto-symbol pairs (I1, J1) and (I2, J2) such that gcd(i1-i2, M)=1. Such a pair can be found in a long ciphertext. In that case, the matrix i11i21 can be inverted to modulo M, and the key can easily be obtained (Schaeffer 26).
j1j2≡ i11i21ab mod M.
ab≡(i1-i2)-11-1-i2i1j1j2 Mod 1As seen above, AFFINE is easy to crack and is only suitable where security is not of crucial concern.
Birthday attack on Hash function
One method of breaking hash function sis using birthday attack. The premise of this attack is the probability based on the fact that given a group of 23 people, there is a high probability that two of them share a birthday. This logic can be extended to determine the probability of hash collisions in a given system. Given K number of messages to the hash code, so that the chances of duplication be at least 0.5, the number k is given by k=2m2. Given a hash function that gets an arbitrary message and produces an n-bit digest, the total possible numbers of digests are2n.. To find two messages with the same digest, we need 21/2n trials.
Where n has a large value, birthday attack may not be feasible. The sender encrypts the message by appending an m-bit hash code using the secret key. An attacker generates a variation of the same message to the order of 21/2m (Bellare, Mihir, and Tadayoshi 2) All these variations give a similar meaning. The attacker then prepares the same number of fake messages to substitute for the real message. When the two sets of messages are compared, a pair of messages with the same hash code can be determined. If no match is found, additional fake messages are generated until such a match is found.
Brute force attacks
This involves trying all the possible keys until the right key is found. To be successful, on average half of all keys have to be worked. The brute force attack may be limited by the computational capacity required to try all the keys within practical time limits. The table below illustrates the various periods needed to break multiple DES systems with different computational capabilities (Hoffstein 54).
Key Size (bits) Number of Alternative Keys Time Required at 1 Decryption/µs Time Required at 106 Decryptions/µs
32 232 = 4.3 * 109 231ms = 35.8 minutes 2.15 milliseconds
56 256 = 7.2 * 1016 255ms = 1142 years 10.01 hours
128 2128 = 3.4 * 1038 2127ms = 5.4 * 1024 years 5.4 * 1018 years
168 2168 = 3.7 * 1050 2167ms = 5.9 * 1036 years 5.9 * 1030 years
26 characters (permutation) 26! = 4 * 1026 2 * 1026ms = 6.4 * 1012 years 6.4 * 106 years
Differential cryptanalysis
Used for multi-round ciphers such as DES. This method is applied when the attacker has a large number of large plaintext/ciphertext pairs. Differential cryptanalysis involves determining how the differences in input can affect the resulting difference in the output. In block ciphers, it entails tracing the differences through the transformations and identifying where the ciphers characteristics are not random. To break the code, these non-random characteristics are used to determine the pattern and thus the key used in the encryption (Stallings et al. 67).
Linear cryptanalysis
Linear cryptanalysis is a technique that is related to differential cryptanalysis. However, rather than looking for isolated points where a block cipher depicts some patterns in small parts, it entails attempting to approximate the entire block cipher.
CONCLUSION
Cryptography and transmission of coded information is an essential part of modern communication systems. The essence of cryptography is ensuring that messages can be securely shared in publish channels while maintaining confidentiality. To achieve confidentiality, several methods have been developed for coding messages and ensuring confidentiality. These methods fall into the categories of hash function, symmetric key systems and public key cryptographic. These methods involve the application of mathematics and algorithms in converting plaintext to ciphertext and in recovering plaintext from the ciphertext. The security of a system is not guaranteed by the privacy of the algorithm used but by the strength of the algorithm. A system only becomes vulnerable when the attacker has bot the algorithm and the key. Having an algorithm and the ciphertext should not be sufficient to determine the plaintext.
The process of obtaining the message without having the key is known as code breaking. The codebreaker may have only the ciphertext only, plaintext/ciphertext pairs or limited access to the cipher, which enables the attacker to produce ciphertext/plaintext pairs of his choice.As we have seen, for classical ciphers, statistical methods such as the use of frequency tables may be used to determine the plaintext from the ciphertext. A clear illustration is the breaking of the affine cipher. For more complex ciphers, advanced approaches may be used. Examples of these approaches include the birthday attack, differential and linear cryptanalysis and brute force attacks.
Work cited
Stinson, Douglas R. Cryptography: theory and practice. CRC press, 2005.
Courtois, Nicolas, and Josef Pieprzyk. “Cryptanalysis of block ciphers with overdefined systems of equations.” Advances in Cryptology—ASIACRYPT 2002 (2002): 267-287.
Stallings, William, and Mohit P. Tahiliani. Cryptography and network security: principles and practice. Vol. 6. London: Pearson, 2014.
Schaefer, Edward. “An introduction to cryptography and cryptanalysis.” California’s Silicon Valley: Santa Clara University (2009): 4-5
Hoffstein, Jeffrey, et al. An introduction to mathematical cryptography. Vol. 1. New York: springer, 2008.
Bellare, Mihir, and Tadayoshi Kohno. “Hash function balance and its impact on birthday attacks.” International Conference on the Theory and Applications of Cryptographic Techniques. Springer Berlin Heidelberg, 2004.