暗号学

Cryptography — Grokipedia Fact-checked by Grok 3 months ago Cryptography Ara Eve Leo Sal 1x Cryptography is the discipline that embodies the principles, means, and methods for the transformation of data in order to hide their semantic content. [1] Emerging in antiquity with rudimentary techniques like substitution ciphers—such as the shift cipher attributed to Julius Caesar for securing military orders—it has developed into a cornerstone of modern information security, protecting communications, financial transactions, and data integrity against eavesdroppers and adversaries through mathematical algorithms and secret keys. [2] Key historical milestones include the mechanical Enigma rotor machines deployed by Nazi Germany during World War II, whose decryption by Allied codebreakers at Bletchley Park, led by figures like Alan Turing, yielded Ultra intelligence that shortened the war and saved millions of lives by revealing German U-boat positions and strategic plans. [3] [4] The field's transformation accelerated in the 1970s with the invention of public-key cryptography by Whitfield Diffie and Martin Hellman, introducing asymmetric algorithms that enable secure key distribution over insecure channels without pre-shared secrets, foundational to protocols like HTTPS and digital signatures. [5] Yet, cryptography remains contentious, with governments, including the U.S. National Security Agency, historically pressuring for intentional weaknesses or backdoors in standards—evident in the failed Clipper chip initiative of the 1990s and persistent calls to undermine end-to-end encryption—raising debates over balancing privacy against national security imperatives. [6] Terminology and Fundamentals Definitions and Basic Principles Cryptography is the discipline encompassing principles, means, and methods for transforming data to conceal its semantic content, thereby enabling secure communication amid adversarial threats. [1] At its core, it involves converting intelligible data, termed plaintext , into an unintelligible format known as ciphertext via encryption , which employs a cryptographic algorithm and a secret key; the inverse operation, decryption, reverses this to recover the plaintext using the corresponding key. [7] [8] Cryptographic keys consist of bit strings that control the algorithm's operation, determining the specific transformation applied during encryption and decryption. [9] Algorithms, often called ciphers, specify the mathematical steps for these transformations, ranging from simple substitution methods to complex computational routines resistant to reversal without the key. [10] In symmetric encryption , a single shared key suffices for both encryption and decryption, facilitating efficiency but requiring secure key distribution ; asymmetric encryption , by contrast, uses mathematically linked public-private key pairs, allowing public dissemination of the encryption key without compromising security . [11] [9] Fundamental principles guiding cryptographic systems include confidentiality , which restricts access to authorized parties; data integrity , ensuring information remains unaltered during transmission or storage; authentication , verifying the legitimacy of communicants or data origins; and non-repudiation , binding actions to their performers to preclude denial. [12] [10] These objectives derive from the need to counter threats like eavesdropping , tampering, impersonation, and disavowal, with effectiveness hinging on the secrecy and strength of keys alongside algorithm robustness against known attacks. [1] [13] Security Models: Information-Theoretic vs Computational Information-theoretic security , also known as unconditional or perfect security, refers to cryptographic systems where no information about the plaintext is leaked through the ciphertext , even to an adversary with unlimited computational resources and time. This concept was formalized by Claude Shannon in his 1949 paper "Communication Theory of Secrecy Systems," where perfect secrecy is defined such that the posterior probability distribution over possible plaintexts given the ciphertext is identical to the prior distribution, implying zero mutual information between plaintext and ciphertext. [14] Achieving this requires the key space to be at least as large as the message space, as per Shannon's theorem, ensuring that for every ciphertext, every possible plaintext is equally likely under some key. [15] The one-time pad exemplifies information-theoretic security : it encrypts a message by XORing it with a truly random key of equal length, used only once, producing ciphertext indistinguishable from random noise without the key. This construction, independently invented by Gilbert Vernam in 1917 and Joseph Mauborgne, guarantees perfect secrecy because the adversary cannot distinguish the ciphertext from uniform randomness, regardless of attack sophistication, provided key generation and usage rules are followed strictly. [16] However, practical limitations include the need for secure key distribution and storage of keys as long as messages, rendering it inefficient for most applications beyond niche uses like diplomatic communications. [14] In contrast, computational security assumes adversaries are polynomially bounded in resources, relying on the intractability of specific mathematical problems under feasible computation. Security holds if breaking the system requires superpolynomial time, such as solving the integer factorization problem for RSA or finding short vectors in lattices for some modern schemes, with no efficient algorithms known as of 2023 despite extensive cryptanalysis . [17] Examples include the Advanced Encryption Standard (AES), standardized by NIST in 2001 after a public competition, which resists all known attacks within 2^128 operations for the 128-bit variant, and elliptic curve cryptography , where security stems from the elliptic curve discrete logarithm problem. [18] This model underpins modern cryptography but remains conditional: advances in quantum computing , such as Shor's algorithm demonstrated on small instances in 2001, threaten systems like RSA by enabling efficient factoring. [17] Aspect Information-Theoretic Security Computational Security Adversary Model Unlimited computation and time Polynomial-time bounded Security Guarantee Absolute: no information leakage possible Probabilistic: negligible success probability Key Length Requirement At least message length (e.g., one-time pad ) Fixed, independent of message (e.g., 256 bits for AES) Practicality Impractical for large-scale use due to key management Widely deployed, efficient, but assumption-dependent Examples One-time pad AES, RSA, elliptic curve Diffie-Hellman The distinction arises from causal realism in security proofs: information-theoretic models derive from entropy and probability theory , independent of hardware limits, while computational models incorporate real-world constraints like Moore's law and algorithmic complexity, prioritizing deployability over theoretical perfection. [17] Hybrid approaches, such as information-theoretically secure primitives combined with computational assumptions for efficiency, appear in advanced protocols like quantum key distribution , but pure information-theoretic security remains rare outside theoretical analysis. [18] History Ancient and Classical Periods The earliest documented use of cryptography for secure correspondence emerged among the ancient Spartans around 400 BC, employing a transposition cipher device known as the scytale . [19] This method involved wrapping a strip of parchment around a cylindrical baton of fixed diameter, writing the message along the spiral, then unwrapping the strip to produce a jumbled text; reconstruction required a matching baton to realign the characters. [19] Historical accounts, including those from Plutarch , describe its application in military dispatches to prevent interception by enemies, though some scholars debate whether it served primarily as a cipher or a message authentication tool due to the need for identical batons at sender and receiver ends. [20] In classical Greece , further developments included references to cryptographic techniques in military treatises, such as those by Aeneas Tacticus in the 4th century BC, who discussed methods for securing communications against betrayal. [21] Earlier traces appear in Mesopotamian records around 1500 BC, where a scribe obscured a pottery glaze formula using cuneiform substitutions, representing an rudimentary form of secret writing rather than systematic encryption . [22] Egyptian tomb inscriptions from circa 1900 BC employed anomalous hieroglyphs, potentially to conceal ritual knowledge from the uninitiated, though this practice bordered on steganography —hiding meaning through obscurity—rather than formal ciphering. [23] During the Roman Republic , Julius Caesar reportedly utilized a substitution cipher in military correspondence around 58–50 BC, shifting each letter in the Latin alphabet by three positions (e.g., A to D, B to E), rendering plaintext unintelligible without the key shift value. [24] Known as the Caesar cipher , this monoalphabetic technique was simple yet effective against casual readers, as evidenced by Suetonius's accounts of Caesar's encrypted orders to commanders. [25] Its vulnerability to frequency analysis stemmed from preserved letter distributions, but it marked an advancement in deliberate alphabetic transposition for state secrecy. [24] These ancient methods relied on shared secrets or physical devices, lacking mathematical complexity, and were driven by wartime needs to protect strategic information from adversaries. [26] By the end of the classical period, around the 5th century AD, such practices had influenced later Roman and Byzantine codes, though systematic cryptanalysis remained undeveloped until medieval times. [19] Medieval to 19th Century Advances During the Isla