Cryptography: Concepts, Algorithms, and Security

Posted on Jan 11, 2025 in Information Consulting and Management

Prime Numbers, GCD, and Congruence

Prime Numbers: Numbers > 1 with no divisors other than 1 & itself.

GCD: Largest positive integer dividing 2 numbers without a remainder.

Congruence: 2 numbers are congruent modulo N if they have the same remainder when divided by N (A ≡ B mod N).

Classical vs. Modern Cryptography

Classical Cryptography:

  1. Based on secrecy of the encryption algorithm.
  2. Key distribution was physical & therefore not as secure.
  3. Encryptions like the Caesar cipher were susceptible to frequency analysis & brute force attacks.

Modern Cryptography:

  1. Secrecy relies on the encryption key, not the algorithm (Kerckhoff’s principle).
  2. Mathematical theories to ensure a higher level of security.
  3. Implements complex algorithms that can be securely distributed over digital channels.

Mathematical Foundations

Euler’s Theorem: If N is a positive integer & A is an integer coprime to N, then AΦ(N) ≡ 1 mod N where Φ(N) is Euler’s totient function.

Multiplicative Inverse: For a number A, its inverse modulo N is a number B such that AB ≡ 1 mod N.

Fast Exponentiation: Efficiently compute large exponents modulo N by squaring known powers & multiplying known results.

Asymmetric Encryption and Key Exchange

Asymmetric Encryption/Decryption

RSA Encryption

  1. Obtain the recipient’s public key (n, e).
  2. Represent the plaintext message as an integer m in the range [0, n-1].
  3. Compute the ciphertext c as c = me mod n.

RSA Decryption

  1. Use the private key (n, d) to compute m = cd mod n.
  2. Convert the integer m back to the plaintext format.

Diffie-Hellman Key Exchange (DHKE)

  1. Alice & Bob agree on a prime number p & a base g.
  2. Alice chooses a private key a, computes A = ga mod p, & sends A to Bob.
  3. Bob chooses a private key b, computes B = gb mod p, & sends B to Alice.
  4. Alice computes the shared secret s = Ba mod p.
  5. Bob computes the shared secret s = Ab mod p.
  6. Both Alice & Bob now have the same shared secret s to use for further encryption.

Digital Signature Generation

  1. Create a hash of the message.
  2. Encrypt the hash with the sender’s private key.
  3. Attach this encrypted hash as a digital signature to the message.

Digital Signature Verification

  1. Decrypt the digital signature with the sender’s public key to retrieve the hash.
  2. Create a hash of the received message.
  3. Compare the 2 hashes to verify the signature.

Modular Exponentiation and Algorithms

Modular Exponentiation:

  1. Convert the exponent to binary form.
  2. Square the base for each bit position in the binary form.
  3. Multiply the base powers together where the exponent’s bit is 1.
  4. Reduce each result modulo n during the process to keep the numbers small.

Baby-Step Giant-Step (BSGS) Algorithm:

  1. Calculate m = ⌈√p⌉ where p is the modulus.
  2. Precompute all baby steps: g0, g1, …, g(m-1) mod p.
  3. Precompute all giant steps: h/g0, h/gm, …, h/g(m(m-1)) mod p.
  4. Find a match between the lists of baby steps & giant steps.
  5. Solve for x using the matching entries.

Symmetric Encryption Algorithms

AES: Use When: High speed & efficiency are required; both parties have a secure channel to exchange keys. Vulnerabilities: Susceptible to side-channel attacks; must protect against brute force via strong key management.

DES: Use: Legacy systems that have not yet upgraded (not recommended for new systems). Vulnerable to brute-force attacks due to its short key length (56 bits); also susceptible to more sophisticated cryptanalytic attacks like differential cryptanalysis.

Asymmetric Encryption Algorithms

RSA: Use When: Secure data transmission is needed; establishing digital signatures. Vulnerabilities: Vulnerable to factoring the modulus if it’s too small; needs large key sizes to be secure; susceptible to timing & chosen ciphertext attacks.

DH: Use When: 2 parties need to agree on a shared secret over an insecure channel. Vulnerabilities: Susceptible to man-in-the-middle attacks if not combined with authentication; the discrete log problem might be vulnerable to quantum computing.

Hashing Algorithms

SHA-2,3: Use When: Data integrity & authentication are required without the need for secrecy. Vulnerabilities: Collision resistance is vital; SHA-1 is no longer recommended due to vulnerabilities.

Digital Signature Algorithms

DSA: Use When: Digital signatures are needed for document signing & verification. Vulnerabilities: Requires good random number generation; vulnerable to key recovery attacks if randomness is compromised.

Common Cryptographic Attacks

Side-Channel Attacks (SCA): Exploiting physical implementation; mitigated by careful design to avoid leaking information.

Man-in-the-Middle Attacks (MITMA): Intercepting communications; mitigated by using secure channels & authentication mechanisms.

Timing Attacks: Analyzing computation time to infer information; mitigated by constant-time operations in cryptographic implementations.

Quantum Attacks: Potentially breaking various cryptosystems by quantum algorithms; mitigated by researching & developing quantum-resistant algorithms.

Message Authentication Codes (MACs)

MAC: A short piece of information used to authenticate a message & to confirm that the message comes from the alleged sender (data integrity & authenticity).

Purpose

Authentication: Verifies that the message comes from the specified sender.

Integrity: Ensures that the message has not been altered.

Non-repudiation: Sender cannot deny sending the message.

Key Concepts

Keyed Hash Function: MACs often use a secret key along with a hash function.

Collision Resistance: Hard to find 2 different messages with the same MAC.

Pre-image Resistance: Given a MAC, it should be difficult to find a message that corresponds to it.

Algorithms

HMAC (Hash-based MAC): Uses a hash function (like SHA-256) with a secret key.

Structure: HMAC(K, m) = H((K’ ⊕ opad) + H((K’ ⊕ ipad) + m)) Where K’ is the key standardized to a certain length. ipad & opad are distinct pad values.

CMAC (Cipher-based MAC): Uses a block cipher (like AES) with a secret key. Suitable for environments where block ciphers are preferred or more efficient.

Security Requirements

Forgery Resistance: It should be computationally infeasible to forge a MAC without knowing the secret key.

Unpredictability: It should not be possible to predict future MACs from previous ones.

Use Cases

Network Security: Authenticating messages in protocols like SSL/TLS.

Banking: Ensuring the integrity of transactions.

Best Practices

Secret Key: Must be kept confidential between the sender & the receiver.

Key Management: Regularly update & securely manage the distribution of keys.

Algorithm Selection: Choose an algorithm that fits the security level required by the application.

Attacks

Brute Force Attack: Trying all possible keys to find the correct one.

Cryptanalysis Attack: Exploiting weaknesses in the MAC algorithm or implementation.

Side-Channel Attack: Gleaning information from the physical implementation of the MAC generation process.

MAC vs. Digital Signatures

MACs: Symmetric, require the sender & receiver to share a secret key. Faster than digital signatures.

Digital Signatures: Asymmetric, use a pair of public-private keys. Provide non-repudiation, which MACs do not.

MAC vs. Hash Functions

Hash Functions: Do not use a secret key & only provide data integrity.

MACs: Use a secret key to provide both data integrity & authentication.

Public Key Cryptography

Public Key solves the key distribution problem. Each user has a public key (encryption) and a private key (decryption), enabling secure communication without pre-sharing secret keys.

Possible e’s in RSA: phi(phi(n))

Private key in RSA: (d, phi(n)) used to decrypt

RSA and Euler’s Theorem

Why encryption/decryption work in RSA: gcd(M, n) = 1 because n only has factors p and q and it is unlikely M shares a factor p or q so we can use Euler’s theorem that M(phi(n)*k) mod n is congruent to 1 mod n

Euler’s function finding phi(a): the # of numbers that have an inverse mod a between 0 and a-1

What is phi(primen): primen – prime(n-1)

When does phi(mn) = phi(m) phi(n): when m and n are coprime (their gcd is one)

What is Euler’s theorem?: if m is positive and a is an integer and their gcd =1 then aphi(m) ~= 1 mod m

How to find ab mod c:

  1. Check that gcd(a, c) = 1, then we can apply Euler’s formula
  2. aphi(c) ~= 1 mod c
  3. Solve for phi(c) = #, then a#k ~= 1 mod m where k is an integer greater than or equal to one.
  4. Solve b = # * q + r for q and r
  5. Replace b in ab mod c by (#*q + r) from step four
  6. Solve

What are the last two digits of ab ?: asking for ab mod 100

Shift and Affine Ciphers

What is a shift cipher?: A simple substitution cipher that replaces each letter of the alphabet by a new shifted alphabet.

How do you decrypt a shift cipher?: brute force or frequency analysis

How is frequency analysis of shift ciphers done?: dot product

Dot product steps:

  1. Create a frequency vector for the ciphertext in alphabetical order. (W)
  2. Find the alphabet frequency for the alphabet as a whole in alphabetical order. (A0)
  3. Compute W*A0
  4. Find A1 by shifting the vector one position bringing the last element to the front and shifting the rest to the right.
  5. Compute W*A1
  6. Continue shifting A and multiplying by W until the shifted A reaches back to A0.
  7. Determine the largest W*A#, the # is the likely shift value.

What are affine ciphers?: Generalization of the shift cipher with a tuple as key (alpha, beta)

What is the encryption formula for an affine cipher?: C ~= alpha*p + beta mod m

How many choices are there for alpha mod m in an affine cipher?: phi(m)

How many choices are there for beta mod m in an affine cipher?: m

How many possible keys are there with affine ciphers?: phi(m) * m

LFSRs and Discrete Logarithms

LFSRs: A type of pseudorandom number generators used in stream ciphers. It generates a sequence based on linear recurrence. The sequence repeats after a certain number of steps indicating its period. Secure? No, especially against known-plaintext attacks. Parts of the key can be deduced if both plaintext and ciphertexts are known

Discrete log problem definition to find x in gx ~ a mod p: x ~ Lg(a) mod p-1

Diffie-Hellman and ElGamal

Diffie-Hellman key exchange definition: This is used where each party had a public key and private key that is used to establish an exchange of keys in an unsecure communication channel that can then be used for symmetric encryption.

  1. Publicly Alice and Bob decide on a prime number p and a primitive root, a mod p.
  2. Alice then selects a private key, x, from {1, 2, …, p-2} chosen randomly and kept secret
  3. Alice calculates her public key A as ax mod p
  4. Alice sends A to Bob over the public channel
  5. Bob selects a private key, y, from {1, 2, …, p-2} chosen randomly and kept secret
  6. Bob calculates his public key B as ay mod p.
  7. Bob send B to Alice over the public channel.
  8. They each can calculate the shared key, K, by raising the public key they received to the power of their private key. K = axy mod p.

Why does the ElGamal cryptosystem exist?: it addresses weaknesses in RSA and is based on the Diffie-Hellman key exchange

Cryptographic Principles

Confusion: each bit of the ciphertext should rely on multiple parts of the key.

Diffusion: changing one bit of the plaintext should result in many changes in the ciphertext.

Steps of the ElGamal cryptosystem:

  1. Key Generation
  2. Encryption
  3. Decryption

Hashing and Ciphers

SHA-1: Not secure

Find the key length in a Vigenere cipher: write out the ciphertext on two slips of paper, line them up count coincidences and then shift the bottom paper right one letter and count again, do this until there is only one overlap left. whatever overlap had the most coincidences is the likely key length, perfectly lined up would correspond to zero and would have the most coincidences, don’t consider this.

OTP: (1)symmetric, C= K XOR P and P= C XOR K, (2)random, secret and only used once (3)perfect secrecy.

Oscar trick: replacing encrypted content with their own version since replacing encrypted random data with new random data is indistinguishable.

MACs and digital signatures: (D)message integrity and message authentication, (D)MACs are symmetric key schemes and they do not provide non-repudiation.

Length extension attack: a secret prefix MAC an attacker can append a message to the end of a given MAC value and hash it again to get a new valid MAC value with their new extended message.

Secret suffix MAC constructed: The secret key, k, is appended to the end of the message, m. H(m|| k) is the MAC value where H is the hash function. VUL: an attacker can append a message to the end of a valid message and gain a corresponding MAC value through collision attacks

HMAC: (1) requires a secret shared key between sender and receiver (2) Append a constant k1 to the secret key if needed for block size. XOR a constant k2 with the secret key if needed for block size. (3) H1 = H(k1 || (k2 XOR secret-key) || message) (4) H2 = H(secret-key || H1) (5) HMAC value is H2

Key Management

Key transport: In this method, one party creates the cryptographic key and sends it to the other party. The security of this method relies on the safe transport of the key.

Key agreement: In this method, both parties mutually create and agree on a cryptographic key via a shared protocol. The key is never sent directly, improving security

Key freshness: the concept that keys should be new, unique, and used only once or for a short period of time

Key freshness important: security: limits the window of opportunity for attack, mitigate replay attacks: reusing captured messages in these attacks, limit damage: even if an attacker gets a key they only get access to a small portion of data or only for a limited time. key freshness

Implemented: key rotation: regularly updating encryption keys, forward secrecy: generate random public keys per session, timestamps/counters: tying keys to these to ensure they can only be used for a short window.

Benefits of using derived joint keys and non-secret public parameters to generate/update new keys: key freshness, only a single session is compromised if a key is stolen.

How new keys generated using nonce and shared key: (1) Bob randomly generates a nonce, r . (2): Bob uses the shared key, kAB , to encrypt the nonce, r .(3) Ek (r ) = c; where E denotes the encryption process (could be AES), kAB is the encryption key, and c is the session key