Beta Phase: Square45 is currently in beta testing. Expect some features or content to be incomplete or missing.
45

Cryptography

Field: Information Security

The practice and study of techniques for secure communication in the presence of third parties.

Sequence of Expressions

Let MM be the plaintext message and KK be the secret key, where M,K∈{0,1}nM, K \in \{0, 1\}^n. Define the encryption function EK:{0,1}n→{0,1}mE_K: \{0, 1\}^n \to \{0, 1\}^m and the decryption function DK:{0,1}m→{0,1}nD_K: \{0, 1\}^m \to \{0, 1\}^n. The system must satisfy the following properties for all valid inputs MM and KK:\nDecryption Property: DK(EK(M))=M\text{Decryption Property: } D_K(E_K(M)) = M\nKey Dependency: EK(M)≠EK′(M) for K≠K′\text{Key Dependency: } E_K(M) \neq E_{K'}(M) \text{ for } K \neq K'
Let MM be the message, PKPK be the public key, and SKSK be the private key. Define the encryption function EPK:{0,1}n→{0,1}mE_{PK}: \{0, 1\}^n \to \{0, 1\}^m and the decryption function DSK:{0,1}m→{0,1}nD_{SK}: \{0, 1\}^m \to \{0, 1\}^n. The system must satisfy:\nDecryption Property: DSK(EPK(M))=M\text{Decryption Property: } D_{SK}(E_{PK}(M)) = M\nKey Separation: The computational difficulty of deriving SK from PK must be intractable.\text{Key Separation: } \text{The computational difficulty of deriving } SK \text{ from } PK \text{ must be intractable.}
Define a hash function $H: \Sigma^* \to \\{0, 1\}^n$ (where the output length is fixed). The function must satisfy three properties: \n1. \textbf{Pre-image Resistance:} Given $h \in \text{Range}(H)$, finding $M$ such that $H(M) = h$ must be computationally infeasible.\n2. \textbf{Second Pre-image Resistance:} Given $M_1$, finding $M_2 \neq M_1$ such that $H(M_2) = H(M_1)$ must be computationally infeasible.\n3. \textbf{Collision Resistance:} Finding any pair $(M_1, M_2)$ such that $M_1 \neq M_2$ and $H(M_1) = H(M_2)$ must be computationally infeasible.
Let XX be a discrete random variable representing the source output alphabet X\mathcal{X} with probability mass function P(x)P(x). The entropy of XX is defined as H(X)=−∑x∈XP(x)log⁡2P(x)H(X) = -\sum_{x \in \mathcal{X}} P(x) \log_2 P(x). For any uniquely decodable code C={cx}x∈X\mathcal{C} = \{c_x \}_{x \in \mathcal{X}} with average code length L=E[∣cX∣]L = E[|c_X|], the following inequality holds:\n1N∑i=1N∣cXi∣≥H(X)−12log⁡2(eN)\frac{1}{N} \sum_{i=1}^{N} |c_{X_i}| \ge H(X) - \frac{1}{2} \log_2 (e N) \nAs N→∞N \to \infty, the minimum average code length LminL_{min} approaches the entropy: Lmin≥H(X)L_{min} \ge H(X). Furthermore, there exists a code such that Lmin≤H(X)+ϵL_{min} \le H(X) + \epsilon for any ϵ>0\epsilon > 0.
Let MM be the size of the hash output space (the number of possible hash values). Consider a sequence of NN randomly chosen inputs x1,x2,…,xNx_1, x_2, \dots, x_N mapping to H(xi)∈{0,1}kH(x_i) \in \{0, 1\}^k, where M=2kM = 2^k. The probability P(N)P(N) of finding at least one collision (i.e., H(xi)=H(xj)H(x_i) = H(x_j) for i≠ji \ne j) is given by:\nP(N)=1−∏i=1N−1(1−iM)P(N) = 1 - \prod_{i=1}^{N-1} \left(1 - \frac{i}{M}\right) \nFor N≪MN \ll M, the probability of collision approaches 1/21/2 when NN reaches approximately πM/2\sqrt{\pi M / 2}. Specifically, N≈1.2MN \approx 1.2 \sqrt{M} ensures P(N)≥0.5P(N) \ge 0.5.
Let (PKA,SKA)(PK_A, SK_A) be the public/secret key pair for signer AA, and H:M→HH: \mathcal{M} \to \mathcal{H} be a collision-resistant hash function mapping messages M\mathcal{M} to hash values H\mathcal{H}. To sign a message MM: \n1. Compute the hash digest: h=H(M)h = H(M). \n2. Generate the signature σ\sigma: σ=SignSKA(h)\sigma = \text{Sign}_{SK_A}(h). \nVerification by recipient BB: \n1. Compute the expected hash: h′=H(M)h' = H(M). \n2. Verify the signature using AA's public key: VerifyPKA(h′,σ)=True\text{Verify}_{PK_A}(h', \sigma) = \text{True}. \nThe security relies on the computational difficulty of solving the underlying hard problem (e.g., factoring or discrete logarithm) to forge σ\sigma without SKASK_A.
Let MM be the plaintext message, KK be the key, and CC be the ciphertext, all defined over a finite field F2L\mathbb{F}_2^L (vectors of length LL). The key KK must satisfy K∈F2LK \in \mathbb{F}_2^L and be uniformly random and never reused. The encryption operation E\mathcal{E} and decryption operation D\mathcal{D} are defined using the XOR operation (⊕\oplus):\nEncryption: C=M⊕K\text{Encryption: } C = M \oplus K \nDecryption: M=C⊕K\text{Decryption: } M = C \oplus K \nSince KK is uniformly random and independent of MM, the resulting ciphertext CC is statistically indistinguishable from a uniform random sequence, ensuring perfect secrecy (Shannon's perfect secrecy).
Principle

Diffusion

Let E:{0,1}n×{0,1}k→{0,1}mE: \{0, 1\}^n \times \{0, 1\}^k \to \{0, 1\}^m be the cryptographic transformation, where MM is the plaintext and KK is the key. Diffusion requires that a small change in the input (plaintext or key) results in a large, unpredictable change in the output. Formally, for any two inputs (M,K)(M, K) and (M′,K′)(M', K') such that the Hamming distance H(M,M′)=1H(M, M') = 1 and H(K,K′)=0H(K, K') = 0, the output distance must be large:\nH(E(M,K),E(M′,K))≥m2−O(1)H(E(M, K), E(M', K)) \ge \frac{m}{2} - O(1) \n(Where H(⋅,⋅)H(\cdot, \cdot) is the Hamming distance and mm is the output length.)
Principle

Confusion

Let E:{0,1}n×{0,1}k→{0,1}mE: \{0, 1\}^n \times \{0, 1\}^k \to \{0, 1\}^m be the cryptographic function mapping plaintext MM and key KK to ciphertext CC. Confusion dictates that the relationship between CC and KK must be highly complex, ideally resisting algebraic analysis. This is formalized by requiring that the function C=E(M,K)C = E(M, K) cannot be accurately approximated by a low-degree polynomial over a finite field Fq\mathbb{F}_q:\nFor any polynomial P∈Fq[x1,…,xm] of degree d≪m, the probability P(C)=0 must be negligible.\text{For any polynomial } P \in \mathbb{F}_q[x_1, \dots, x_m] \text{ of degree } d \ll m, \text{ the probability } P(C) = 0 \text{ must be negligible.}
Let XX and YY be discrete random variables with joint probability mass function P(x,y)P(x, y). The entropy of XX is defined as H(X)=−∑xP(x)log⁡2P(x)H(X) = -\sum_{x} P(x) \log_2 P(x). The joint entropy is H(X,Y)=−∑x,yP(x,y)log⁡2P(x,y)H(X, Y) = -\sum_{x, y} P(x, y) \log_2 P(x, y). The mutual information I(X;Y)I(X; Y) quantifies the reduction in uncertainty about XX given YY, and is formally defined as:\nI(X;Y)=∑x,yP(x,y)log⁡2(P(x,y)P(x)P(y))I(X; Y) = \sum_{x, y} P(x, y) \log_2 \left(\frac{P(x, y)}{P(x)P(y)}\right) \nIt satisfies the chain rule: H(X,Y)=H(X)+H(Y∣X)H(X, Y) = H(X) + H(Y|X), where H(Y∣X)=−∑x,yP(x,y)log⁡2P(y∣x)H(Y|X) = -\sum_{x, y} P(x, y) \log_2 P(y|x) is the conditional entropy.