Cryptanalysis is the study of analyzing information systems in order to study the hidden aspects of the systems. Cryptanalysis is used to breach cryptographic security systems and gain access to the contents of encrypted messages if the cryptographic key is unknown. In addition to mathematical analysis of cryptographic algorithms, cryptanalysis includes the study of side-channel attacks that do not target weaknesses in the cryptographic algorithms themselves, but instead exploit weaknesses in their implementation. Though the goal has been the same, the methods and techniques of cryptanalysis have changed drastically through the history of cryptography, adapting to increasing cryptographic complexity, ranging from the pen-and-paper methods of the past, through machines like the British Bombes and Colossus computers at Bletchley Park in World War II, to the mathematically advanced computerized schemes of the present. Methods for breaking modern cryptosystems involve solving constructed problems in pure mathematics, the best-known being integer factorization.
Given some encrypted data, the goal of the cryptanalyst is to gain as much information as possible about the original, unencrypted data. It is useful to consider two aspects of achieving this; the first is breaking the system —, discovering how the encipherment process works. The second is solving the key, unique for a particular encrypted message or group of messages. Attacks can be classified based on; as a basic starting point it is assumed that, for the purposes of analysis, the general algorithm is known. This is a reasonable assumption in practice — throughout history, there are countless examples of secret algorithms falling into wider knowledge, variously through espionage and reverse engineering.: Ciphertext-only: the cryptanalyst has access only to a collection of ciphertexts or codetexts. Known-plaintext: the attacker has a set of ciphertexts to which he knows the corresponding plaintext. Chosen-plaintext: the attacker can obtain the ciphertexts corresponding to an arbitrary set of plaintexts of his own choosing.
Adaptive chosen-plaintext: like a chosen-plaintext attack, except the attacker can choose subsequent plaintexts based on information learned from previous encryptions. Adaptive chosen ciphertext attack. Related-key attack: Like a chosen-plaintext attack, except the attacker can obtain ciphertexts encrypted under two different keys; the keys are unknown. Attacks can be characterised by the resources they require; those resources include: Time -- the number of computation steps. Memory — the amount of storage required to perform the attack. Data — the quantity and type of plaintexts and ciphertexts required for a particular approach. It's sometimes difficult to predict these quantities especially when the attack isn't practical to implement for testing, but academic cryptanalysts tend to provide at least the estimated order of magnitude of their attacks' difficulty, for example, "SHA-1 collisions now 252."Bruce Schneier notes that computationally impractical attacks can be considered breaks: "Breaking a cipher means finding a weakness in the cipher that can be exploited with a complexity less than brute force.
Never mind that brute-force might require 2128 encryptions. The results of cryptanalysis can vary in usefulness. For example, cryptographer Lars Knudsen classified various types of attack on block ciphers according to the amount and quality of secret information, discovered: Total break — the attacker deduces the secret key. Global deduction — the attacker discovers a functionally equivalent algorithm for encryption and decryption, but without learning the key. Instance deduction — the attacker discovers additional plaintexts not known. Information deduction — the attacker gains some Shannon information about plaintexts not known. Distinguishing algorithm — the attacker can distinguish the cipher from a random permutation. Academic attacks are against weakened versions of a cryptosystem, such as a block cipher or hash function with some rounds removed. Many, but not all, attacks become exponentially more difficult to execute as rounds are added to a cryptosystem, so it's possible for the full cryptosystem to be strong though reduced-round variants are weak.
Nonetheless, partial breaks that come close to breaking the original cryptosystem may mean that a full break will follow. In academic cryptography, a weakness or a break in a scheme is defined quite conservatively: it might require impractical amounts of time, memory, or known plaintexts, it might require the attacker be able to do things many real-world attackers can't: for example, the attacker may need to choose particular plaintexts to be encrypted or to ask for plaintexts to be encrypted using several keys related to the secret key. Furthermore
In cryptography, CAST-128 is a symmetric-key block cipher used in a number of products, notably as the default cipher in some versions of GPG and PGP. It has been approved for Government of Canada use by the Communications Security Establishment; the algorithm was created in 1996 by Carlisle Adams and Stafford Tavares using the CAST design procedure. Another member of the CAST family of ciphers, CAST-256 was derived from CAST-128. According to some sources, the CAST name is based on the initials of its inventors, though Bruce Schneier reports the authors' claim that "the name should conjure up images of randomness". CAST-128 is a 12- or 16-round Feistel network with a 64-bit block size and a key size of between 40 and 128 bits; the full 16 rounds are used. Components include large 8×32-bit S-boxes based on bent functions, key-dependent rotations, modular addition and subtraction, XOR operations. There are three alternating types of round function, but they are similar in structure and differ only in the choice of the exact operation at various points.
Although Entrust holds a patent on the CAST design procedure, CAST-128 is available worldwide on a royalty-free basis for commercial and non-commercial uses. PGP GPG AES RFC 2144 The CAST-128 Encryption Algorithm "CAST Encryption Algorithm Related Publications". Archived from the original on 2007-12-17. Retrieved 2013-01-15. CS1 maint: BOT: original-url status unknown "Standard Cryptographic Algorithm Naming: Symmetric Ciphers - CAST-128". Retrieved 2013-01-14."CSEC Approved Cryptographic Algorithms for the Protection of Sensitive Information and for Electronic Authentication and Authorization Applications within GC". Communications Security Establishment Canada. 2011-03-01. Retrieved 2014-12-04
In cryptography, XTEA is a block cipher designed to correct weaknesses in TEA. The cipher's designers were David Wheeler and Roger Needham of the Cambridge Computer Laboratory, the algorithm was presented in an unpublished technical report in 1997, it is not subject to any patents. Like TEA, XTEA is a 64-bit block Feistel cipher with a suggested 64 rounds. Several differences from TEA are apparent, including a somewhat more complex key-schedule and a rearrangement of the shifts, XORs, additions; this standard C source code, adapted from the reference code released into the public domain by David Wheeler and Roger Needham and decrypts using XTEA: The changes from the reference source code are minor: The reference source code used the unsigned long type rather than the 64-bit clean uint32_t. The reference source code did not use const types; the reference source code omitted redundant parentheses, using C precedence to write the round function as e.g. v1 += + v0 ^ sum + k. To additionally improve speed, the loop can be unrolled by pre-computing the values of sum+key.
In 2004, Ko et al. presented a related-key differential attack on 27 out of 64 rounds of XTEA, requiring 220.5 chosen plaintexts and a time complexity of 2115.15. In 2009, Lu presented a related-key rectangle attack on 36 rounds of XTEA, breaking more rounds than any published cryptanalytic results for XTEA; the paper presents two attacks, one without and with a weak key assumption, which corresponds to 264.98 bytes of data and 2126.44 operations, 263.83 bytes of data and 2104.33 operations respectively. Presented along with XTEA was a variable-width block cipher termed Block TEA, which uses the XTEA round function, but Block TEA applies it cyclically across an entire message for several iterations; because it operates on the entire message, Block TEA has the property that it does not need a mode of operation. An attack on the full Block TEA was described in, which details a weakness in Block TEA's successor, XXTEA. RC4 — A stream cipher that, just like XTEA, is designed to be simple to implement.
XXTEA — Block TEA's successor. TEA — Block TEA's precursor. Sekar, Gautham. Kiayias, A. ed. Meet-in-the-Middle Attacks on Reduced-Round XTEA. Topics in Cryptology – CT-RSA 2011. Lecture Notes in Computer Science. 6558. Pp. 250–267. Doi:10.1007/978-3-642-19074-2_17. ISBN 978-3-642-19073-5. Retrieved 2018-10-10. Ko, Youngdai. Related Key Differential Attacks on 27 Rounds of XTEA and Full-Round GOST. Fast Software Encryption. Lecture Notes in Computer Science. 3017. Pp. 299–316. Doi:10.1007/978-3-540-25937-4_19. ISBN 978-3-540-22171-5. Retrieved 2018-10-10. Hong, Seokhie. Differential Cryptanalysis of TEA and XTEA. Information Security and Cryptology - ICISC 2003. Lecture Notes in Computer Science. 2971. Pp. 402–417. Doi:10.1007/978-3-540-24691-6_30. ISBN 978-3-540-21376-5. Moon, Dukjae. Impossible Differential Cryptanalysis of Reduced Round XTEA and TEA. Fast Software Encryption. Lecture Notes in Computer Science. 2365. Pp. 49–60. Doi:10.1007/3-540-45661-9_4. ISBN 978-3-540-44009-3. Retrieved 2018-10-10. Andem, Vikram Reddy.
A stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream. In a stream cipher, each plaintext digit is encrypted one at a time with the corresponding digit of the keystream, to give a digit of the ciphertext stream. Since encryption of each digit is dependent on the current state of the cipher, it is known as state cipher. In practice, a digit is a bit and the combining operation an exclusive-or; the pseudorandom keystream is generated serially from a random seed value using digital shift registers. The seed value serves as the cryptographic key for decrypting the ciphertext stream. Stream ciphers represent a different approach to symmetric encryption from block ciphers. Block ciphers operate on large blocks of digits with a fixed, unvarying transformation; this distinction is not always clear-cut: in some modes of operation, a block cipher primitive is used in such a way that it acts as a stream cipher. Stream ciphers execute at a higher speed than block ciphers and have lower hardware complexity.
However, stream ciphers can be susceptible to serious security problems. Stream ciphers can be viewed as approximating the action of a proven unbreakable cipher, the one-time pad, sometimes known as the Vernam cipher. A one-time pad uses a keystream of random digits; the keystream is combined with the plaintext digits one at a time to form the ciphertext. This system was proved to be secure by Claude E. Shannon in 1949. However, the keystream must be generated at random with at least the same length as the plaintext and cannot be used more than once; this makes the system cumbersome to implement in many practical applications, as a result the one-time pad has not been used, except for the most critical applications. Key generation and management are critical for those applications. A stream cipher makes use of a more convenient key such as 128 bits. Based on this key, it generates a pseudorandom keystream which can be combined with the plaintext digits in a similar fashion to the one-time pad. However, this comes at a cost.
The keystream is now pseudorandom and so is not random. The proof of security associated with the one-time pad no longer holds, it is quite possible for a stream cipher to be insecure. A stream cipher generates successive elements of the keystream based on an internal state; this state is updated in two ways: if the state changes independently of the plaintext or ciphertext messages, the cipher is classified as a synchronous stream cipher. By contrast, self-synchronising stream ciphers update their state based on previous ciphertext digits. In a synchronous stream cipher a stream of pseudo-random digits is generated independently of the plaintext and ciphertext messages, combined with the plaintext or the ciphertext. In the most common form, binary digits are used, the keystream is combined with the plaintext using the exclusive or operation; this is termed a binary additive stream cipher. In a synchronous stream cipher, the sender and receiver must be in step for decryption to be successful. If digits are added or removed from the message during transmission, synchronisation is lost.
To restore synchronisation, various offsets can be tried systematically to obtain the correct decryption. Another approach is to tag the ciphertext with markers at regular points in the output. If, however, a digit is corrupted in transmission, rather than added or lost, only a single digit in the plaintext is affected and the error does not propagate to other parts of the message; this property is useful. Moreover, because of this property, synchronous stream ciphers are susceptible to active attacks: if an attacker can change a digit in the ciphertext, he might be able to make predictable changes to the corresponding plaintext bit. Another approach uses several of the previous N ciphertext digits to compute the keystream; such schemes are known as self-synchronizing stream ciphers, asynchronous stream ciphers or ciphertext autokey. The idea of self-synchronization was patented in 1946, has the advantage that the receiver will automatically synchronise with the keystream generator after receiving N ciphertext digits, making it easier to recover if digits are dropped or added to the message stream.
Single-digit errors are limited in their effect, affecting only up to N plaintext digits. An example of a self-synchronising stream cipher is a block cipher in cipher feedback mode. Binary stream ciphers are constructed using linear-feedback shift registers because they can be implemented in hardware and can be analysed mathematically; the use of LFSRs on their own, however, is insufficient to provide good security. Various schemes have been proposed to increase the security of LFSRs; because LFSRs are inherently linear, one technique for removing the linearity is to feed the outputs of several parallel LFSRs into a non-linear Boolean function to form a combination generator. Various properties of such a combining function are critical for ensuring the security of the resultant scheme, for example, in order to avoid correlation attacks. LFSRs are stepped regularly. One approach to introducing non-linearity is to have the LFSR clocked irregularly, controlled by the output of a second LFSR; such generators include the sto
Blowfish is a symmetric-key block cipher, designed in 1993 by Bruce Schneier and included in a large number of cipher suites and encryption products. Blowfish provides a good encryption rate in software and no effective cryptanalysis of it has been found to date. However, the Advanced Encryption Standard now receives more attention, Schneier recommends Twofish for modern applications. Schneier designed Blowfish as a general-purpose algorithm, intended as an alternative to the aging DES and free of the problems and constraints associated with other algorithms. At the time Blowfish was released, many other designs were proprietary, encumbered by patents or were commercial or government secrets. Schneier has stated that, "Blowfish is unpatented, will remain so in all countries; the algorithm is hereby placed in the public domain, can be used by anyone."Notable features of the design include key-dependent S-boxes and a complex key schedule. Blowfish has a variable key length from 32 bits up to 448 bits.
It uses large key-dependent S-boxes. In structure it resembles CAST-128; the adjacent diagram shows Blowfish's encryption routine. Each line represents 32 bits. There are five subkey-arrays: four 256-entry S-boxes; every round r consists of 4 actions: The F-function splits the 32-bit input into four eight-bit quarters, uses the quarters as input to the S-boxes. The S-boxes produce 32-bit output; the outputs are added XORed to produce the final 32-bit output. After the 16th round, undo the last swap, XOR L with K18 and R with K17. Decryption is the same as encryption, except that P1, P2, …, P18 are used in the reverse order; this is not so obvious because xor is associative. A common misconception is to use inverse order of encryption as decryption algorithm. Blowfish's key schedule starts by initializing the P-array and S-boxes with values derived from the hexadecimal digits of pi, which contain no obvious pattern; the secret key is byte by byte, cycling the key if necessary, XORed with all the P-entries in order.
A 64-bit all-zero block is encrypted with the algorithm as it stands. The resultant ciphertext replaces P1 and P2; the same ciphertext is encrypted again with the new subkeys, the new ciphertext replaces P3 and P4. This continues, replacing all the S-box entries. In all, the Blowfish encryption algorithm will run 521 times to generate all the subkeys - about 4KB of data is processed; because the P-array is 576 bits long, the key bytes are XORed through all these 576 bits during the initialization, many implementations support key sizes up to 576 bits. The reason for, a discrepancy between the original Blowfish description, which uses 448-bit key, its reference implementation, which uses 576-bit key; the test vectors for verifying third party implementations were produced with 576-bit keys. When asked which Blowfish version is the correct one, Bruce Schneier answered: "The test vectors should be used to determine the one true Blowfish". Another opinion is that the 448 bits limit is here to ensure that every bit of every subkey depends on every bit of the key, as the last four values of the P-array don't affect every bit of the ciphertext.
This point should be taken in consideration for implementations with a different number of rounds, as though it increases security against an exhaustive attack, it weakens the security guaranteed by the algorithm. And given the slow initialization of the cipher with each change of key, it is granted a natural protection against brute-force attacks, which doesn't justify key sizes longer than 448 bits. Blowfish is a fast block cipher, except; each new key requires pre-processing equivalent to encrypting about 4 kilobytes of text, slow compared to other block ciphers. This is not a problem in others. In one application Blowfish's slow key changing is a benefit: the password-hashing method used in OpenBSD uses an algorithm derived from Blowfish that makes use of the slow key schedule. See key stretching. Blowfish has a memory footprint of just over 4 kilobytes of RAM; this constraint is not a problem for older desktop and laptop computers, though it does prevent use in the smallest embedded systems such as early smartcards.
Blowfish was one of the first secure block ciphers not subject to any patents and therefore available for anyone to use. This benefit has contributed to its popularity in cryptographic software. Bcrypt is a password hashing function which, combined with a variable number of iterations, exploits the expensive key setup phase of Blowfish to increase the workload and duration of hash calculations, further reducing threats from brute force attacks. Bcrypt is the name of a cross-platform file encryption utility implementing Blowfish developed in 2002. Blowfish's use of a 64-bit block size makes it vulnerable to birthday attacks in contexts like HTTPS. In 2016, the SWEET32 attack demonstrated how to leverage birthday attacks to perform plaintext recovery against ciphers with a 64-bit block size; the GnuPG project recommends that Blowfish not be used to encrypt files larger than 4 GB
In geometry, an affine transformation, affine map or an affinity is a function between affine spaces which preserves points, straight lines and planes. Sets of parallel lines remain parallel after an affine transformation. An affine transformation does not preserve angles between lines or distances between points, though it does preserve ratios of distances between points lying on a straight line. Examples of affine transformations include translation, homothety, similarity transformation, rotation, shear mapping, compositions of them in any combination and sequence. If X and Y are affine spaces every affine transformation f: X → Y is of the form x ↦ M x + b, where M is a linear transformation on the space X, x is a vector in X, b is a vector in Y. Unlike a purely linear transformation, an affine map need not preserve the zero point in a linear space. Thus, every linear transformation is affine. All Euclidean spaces are affine. In affine coordinates, which include Cartesian coordinates in Euclidean spaces, each output coordinate of an affine map is a linear function of all input coordinates.
Another way to deal with affine transformations systematically is to select a point as the origin. An affine map f: A → B between two affine spaces is a map on the points that acts linearly on the vectors. In symbols, f determines a linear transformation φ such that, for any pair of points P, Q ∈ A: f f → = φ or f − f = φ. We can interpret this definition in a few other ways. If an origin O ∈ A is chosen, B denotes its image f ∈ B this means that for any vector x →: f: ↦. If an origin O ′ ∈ B is chosen, this can be decomposed as an affine transformation g: A → B that sends O ↦ O ′, namely g: ↦,followed by the translation by a vector b → = O ′ B →; the conclusion is that, intuitively, f consists of a linear map. Given two affine spaces A and B, over the same field, a function f: A → B is an affine map if and only if for every family i ∈ I of weighted points in A such that ∑ i ∈ I λ i = 1,we have f = ∑ i ∈ I λ i f. I
Cryptography or cryptology is the practice and study of techniques for secure communication in the presence of third parties called adversaries. More cryptography is about constructing and analyzing protocols that prevent third parties or the public from reading private messages. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, electrical engineering, communication science, physics. Applications of cryptography include electronic commerce, chip-based payment cards, digital currencies, computer passwords, military communications. Cryptography prior to the modern age was synonymous with encryption, the conversion of information from a readable state to apparent nonsense; the originator of an encrypted message shares the decoding technique only with intended recipients to preclude access from adversaries. The cryptography literature uses the names Alice for the sender, Bob for the intended recipient, Eve for the adversary. Since the development of rotor cipher machines in World War I and the advent of computers in World War II, the methods used to carry out cryptology have become complex and its application more widespread.
Modern cryptography is based on mathematical theory and computer science practice. It is theoretically possible to break such a system, but it is infeasible to do so by any known practical means; these schemes are therefore termed computationally secure. There exist information-theoretically secure schemes that provably cannot be broken with unlimited computing power—an example is the one-time pad—but these schemes are more difficult to use in practice than the best theoretically breakable but computationally secure mechanisms; the growth of cryptographic technology has raised a number of legal issues in the information age. Cryptography's potential for use as a tool for espionage and sedition has led many governments to classify it as a weapon and to limit or prohibit its use and export. In some jurisdictions where the use of cryptography is legal, laws permit investigators to compel the disclosure of encryption keys for documents relevant to an investigation. Cryptography plays a major role in digital rights management and copyright infringement of digital media.
The first use of the term cryptograph dates back to the 19th century—originating from The Gold-Bug, a novel by Edgar Allan Poe. Until modern times, cryptography referred exclusively to encryption, the process of converting ordinary information into unintelligible form. Decryption is the reverse, in other words, moving from the unintelligible ciphertext back to plaintext. A cipher is a pair of algorithms that create the reversing decryption; the detailed operation of a cipher is controlled both by the algorithm and in each instance by a "key". The key is a secret a short string of characters, needed to decrypt the ciphertext. Formally, a "cryptosystem" is the ordered list of elements of finite possible plaintexts, finite possible cyphertexts, finite possible keys, the encryption and decryption algorithms which correspond to each key. Keys are important both formally and in actual practice, as ciphers without variable keys can be trivially broken with only the knowledge of the cipher used and are therefore useless for most purposes.
Ciphers were used directly for encryption or decryption without additional procedures such as authentication or integrity checks. There are two kinds of cryptosystems: asymmetric. In symmetric systems the same key is used to decrypt a message. Data manipulation in symmetric systems is faster than asymmetric systems as they use shorter key lengths. Asymmetric systems use a public key to encrypt a private key to decrypt it. Use of asymmetric systems enhances the security of communication. Examples of asymmetric systems include RSA, ECC. Symmetric models include the used AES which replaced the older DES. In colloquial use, the term "code" is used to mean any method of encryption or concealment of meaning. However, in cryptography, code has a more specific meaning, it means the replacement of a unit of plaintext with a code word. Cryptanalysis is the term used for the study of methods for obtaining the meaning of encrypted information without access to the key required to do so; some use the terms cryptography and cryptology interchangeably in English, while others use cryptography to refer to the use and practice of cryptographic techniques and cryptology to refer to the combined study of cryptography and cryptanalysis.
English is more flexible than several other languages in which crypto