l2-faq.txt

What is the primary purpose of cryptographic hash functions like those found in Python's hashlib module?
Cryptographic hash functions, such as SHA256 or BLAKE2b offered by Python's hashlib module, serve to map arbitrary-length data to a fixed-size string of bytes, known as a digest or hash value. Their primary purpose is to ensure data integrity and authenticity. They are designed to be "one-way" functions, meaning it's computationally easy to calculate the hash from the input data but computationally infeasible to reverse the process (i.e., derive the original data from the hash) or to find two different inputs that produce the same hash (a collision). This makes them essential for verifying that data has not been tampered with and for creating digital signatures. For example, hashlib functions can be used for file hashing to quickly confirm if a file's contents have changed or for key derivation in password hashing, where a good password hashing function is tunable, slow, and includes a salt to resist brute-force attacks.

How do "pricing functions" relate to deterring junk mail and controlling resource access?
Pricing functions, as proposed by Dwork and Naor, are computational techniques designed to combat junk mail and generally control access to shared resources by imposing a "moderately hard, but not intractable" computational cost on users. The sender of, for instance, an email or a request for a resource, would be required to compute a complex function of the message or request ID. This computational effort is designed to be negligible for legitimate, infrequent users but prohibitive for those attempting to send large volumes of unsolicited messages or make frivolous requests, thus deterring abuse without outright prohibiting access.

What are "one-way functions" and how do they differ from "trap-door one-way functions" in cryptography?
A one-way function is a mathematical function that is easy to compute in one direction but computationally infeasible to invert (find the input given the output). Examples include integer factorization and the discrete logarithm problem. The security of many cryptographic systems, including the Diffie-Hellman key exchange, relies on the perceived difficulty of inverting these functions.

A "trap-door one-way function" is a special type of one-way function that has a secret "trap-door" or "shortcut" value. While it is computationally infeasible for anyone without this secret information to invert the function, possessing the trap-door information makes the inversion computationally easy. This property is fundamental to public-key cryptography, where the public key allows easy encryption (one-way computation), but only the corresponding private key (the trap-door) enables efficient decryption (inversion).

What are some practical applications of hash functions beyond basic data integrity checks?
Beyond basic data integrity checks, hash functions have several practical applications:

Digital Signatures: Cryptographic hashes are used to create a fixed-size digest of a message, which is then encrypted with a private key to form a digital signature. This signature, along with the sender's public key, allows recipients to verify the message's authenticity and integrity.
Password Storage: Instead of storing plaintext passwords, systems store their hash values. When a user tries to log in, their entered password's hash is computed and compared to the stored hash. This prevents passwords from being compromised if the database is breached.
Key Derivation: Functions like PBKDF2 and scrypt, which utilize hash algorithms, are specifically designed for secure password hashing and key stretching. They introduce tunable computational costs and incorporate "salt" values to make brute-force attacks significantly more difficult.
Proof-of-Work Systems: As seen in concepts like pricing functions for junk mail, computationally intensive hash calculations can serve as a "cost" or "proof of work" to deter spam or frivolous use of resources.
Blockchains: Hashes are fundamental to blockchain technology, where each block's header includes a hash of the previous block, creating an immutable chain and ensuring the integrity of the entire ledger.
What is the "discrete logarithm problem" and why is its computational difficulty important in cryptography?
The discrete logarithm problem involves finding the exponent (the "logarithm") in a modular exponentiation equation. Specifically, given a prime q, a primitive element α of GF(q), and a value Y, the problem is to find X such that Y = α^X mod q. While computing Y from α, X, and q is computationally easy (polynomial time), finding X given Y, α, and q is considered computationally infeasible for sufficiently large q. This "one-way" property makes the discrete logarithm problem a cornerstone of several cryptographic algorithms, including the Diffie-Hellman key exchange and ElGamal encryption. Its difficulty ensures the security of these systems against eavesdropping, as an attacker cannot easily derive the shared secret key even if they intercept all public communications.

How do public-key cryptosystems address the key distribution problem inherent in traditional cryptography?
Traditional cryptography, also known as symmetric-key cryptography, requires all communicating parties to share a secret key, which poses a significant "key distribution problem" – how to securely exchange this key, especially between parties with no prior secure communication channel. Public-key cryptosystems, introduced by Diffie and Hellman, solve this by using distinct but mathematically linked keys: a public key for encryption and a private key for decryption. The public key can be openly shared without compromising the private key. This means anyone can encrypt a message for a specific recipient using their publicly available key, but only that recipient, possessing the corresponding private key, can decrypt it. This eliminates the need for pre-shared secret keys over secure channels for every pair of communicators, vastly simplifying secure communication in large networks.

What are "elliptic curve domain parameters" and why are they important in elliptic curve cryptography (ECC)?
Elliptic curve domain parameters are a set of mathematical constants that define the specific elliptic curve and its associated properties for use in Elliptic Curve Cryptography (ECC). For curves over a prime field Fp, these parameters typically include:

p: a large prime number defining the finite field.
a, b: coefficients defining the elliptic curve equation (e.g., y^2 = x^3 + ax + b (mod p)).
G: a base point on the curve, also known as the generator.
n: the prime order of the base point G.
h: the cofactor, which relates the order of G to the total number of points on the curve.
These parameters are crucial because the security and efficiency of ECC algorithms depend heavily on their proper selection. Standardized parameters, such as those recommended by Certicom Research (SEC 2), ensure interoperability and provide a foundation of trust, as they are chosen to resist known attacks and offer specified security levels (e.g., 128-bit security for secp256k1). Two main types are Koblitz curves (for efficient implementation) and verifiably random curves (for strong assurance against trapdoors).

What is the relationship between one-way functions and authentication systems, particularly in the context of user logins?
One-way functions are central to user authentication systems, especially for secure login procedures. Instead of storing a user's plaintext password, a system stores a hash (the output of a one-way function) of the password. When a user attempts to log in, the system computes the hash of the provided password and compares it to the stored hash. If they match, the user is authenticated. This approach prevents an attacker who gains access to the password directory from directly learning user passwords, as it is computationally infeasible to reverse the one-way function and derive the original password from its hash. This method protects against the compromise of authentication data when it's not in use, although additional measures like encryption are needed to protect passwords during transmission.