W5 Flashcards
What is the purpose of the Right-to-Left Binary Method?
What are the inputs and output of the Right-to-Left Binary Method?
What are the initializations in the Right-to-Left Binary Method?
What happens in each iteration of the loop?
What is the final result of the Right-to-Left Binary Method?
Why is the Right-to-Left Binary Method efficient?
The Right-to-Left Binary Method is used to compute c ≡ a^b mod n efficiently by processing the binary representation of the exponent b.
Inputs:
a: Base,
b: Exponent (in binary b=bℓ−1…b0,
n: Modulus.
Output:
c ≡ a^b mod n
Initialize c=1 and t=a.
For each bit b_i in the binary representation of b:
If b_i = 1, update c ← c ⋅ t mod n.
Always update t←t^2 mod n.
Continue until all bits of b are processed.
After processing all bits of b, return c, which is a^b mod n.
It processes only the necessary bits of b, skipping computations for b_i = 0.
It avoids directly computing a^b, which would be computationally expensive for large b.
What is the purpose of the Left-to-Right Binary Method?
What are the inputs and output of the Left-to-Right Binary Method?
What are the initializations in the Left-to-Right Binary Method?
What happens in each iteration of the loop in the Left-to-Right Binary Method?
What is the final result of the Left-to-Right Binary Method?
How does the binary representation of the exponent b affect the computation?
The Left-to-Right Binary Method is used to compute c ≡ a^b mod n efficiently by processing the binary representation of the exponent b starting from the most significant bit.
Inputs:
a: Base,
b: Exponent (in binary b = bₗ₋₁ … b₀),
n: Modulus.
Output:
c ≡ a^b mod n.
Initialize c=1
Square c :
c ← c² mod n.
If the current bit bᵢ = 1:
c ← c · a mod n.
After processing all bits of b, return c, which is a^b mod n.
Each bit bᵢ = 1 contributes by multiplying c with a.
For bits bᵢ = 0, only the squaring step is performed, skipping multiplication.
What three algorithms are required for public-key cryptology?
- Key generation, generating a public-key private-key pair.
- Encryption, taking a public key and a message, producing ciphertext
- Decryption, taking a private key and a ciphertext, producing a plaintext
What is the purpose of Schoolbook RSA Encryption?
Schoolbook RSA Encryption is a cryptographic method used for secure communication, involving key generation, encryption, and decryption
How is the RSA public and private key generated?
What is the public key in RSA?
What is the private key in RSA?
How is a message encrypted in RSA?
How is a ciphertext decrypted in RSA?
Why does RSA decryption work?
What is the relationship between e, d, and phi(n) in RSA?
What are the constraints on the message m in RSA?
Why is RSA secure?
Pick two distinct prime numbers p and q.
Compute n = p * q and phi(n) = (p-1) * (q-1).
Select an integer e such that 1 < e < n and gcd(e, phi(n)) = 1.
Compute d as the modular inverse of e mod phi(n).
Output the public key (n, e) and the private key (n, d).
The public key is (n, e), where n is the product of the two primes p and q, and e is the public exponent.
The private key is (n, d), where n = p * q and d is the modular multiplicative inverse of e mod phi(n).
For a message m such that 0 ≤ m < n, compute the ciphertext c as:
c = m^e mod n.
Output c.
For a ciphertext c such that 0 ≤ c < n, compute the plaintext m’ as:
m’ = c^d mod n.
Output m’.
Decryption works because of the relationship ed = 1 + k * phi(n), ensuring:
m’ = c^d = (m^e)^d = m^(ed) = m^(1 + k * phi(n)) = m * m^(kphi(n)) = m(m^(phi(n)))^k = * m*1^k = m mod n.
Using Fermat’s Little Theorem, m^phi(n) = 1 mod n, so m’ = m mod n.
The relationship is:
ed = 1 mod phi(n).
This ensures that d is the modular multiplicative inverse of e mod phi(n).
The message m must satisfy 0 ≤ m < n, where n = p * q.
RSA’s security relies on the difficulty of factoring the large number n = p * q into its prime factors p and q, which is computationally infeasible for sufficiently large n.
What is Fermat’s Little Theorem?
For an integer a with gcd(a,n) = 1, a^phi(n) is equivalent to 1 (mod n), where phi(n) is Euler’s totient function.
What is the formula for Euler’s totient function phi(n) when n is a product of prime powers?
What is Euler’s totient function for n = p * q (product of two primes)?
What does Euler’s theorem state about m^(1 + k * phi(n)) mod n?
For n = p1^e1 * p2^e2 * … * pk^ek where p1, p2, … are distinct primes:
phi(n) = n * (1 - 1/p1) * (1- 1/p2) * .. * (1 - 1/pk)
For n = p * q:
phi(n) = (p - 1) * (q - 1).
It states that for any integer m (even if gcd(m, n) > 1), the relationship m^(1 + k * phi(n)) ≡ m mod n holds true.
What is Lagrange’s theorem in group theory?
What does Lagrange’s theorem imply for modular arithmetic?
For a finite group G and an element a in G:
a ^ (size of G) = 1,
where “1” denotes the neutral element of the group.
It implies that raising an element to the order of the group results in the neutral element, which is essential for many modular arithmetic properties in cryptography.
What is Schoolbook RSA used for in the context of signatures?
What are the steps for RSA key generation in the context of signatures?
How is a message signed using RSA?
How is a signature verified using RSA?
Schoolbook RSA is used for generating digital signatures to authenticate and verify messages.
Pick two distinct prime numbers, p and q.
Compute n = p * q and phi(n) = (p - 1) * (q - 1).
Select an integer e such that 1 < e < n and gcd(e, phi(n)) = 1.
Compute d as the modular inverse of e mod phi(n).
Output the public key (n, e) and the private key (n, d).
Compute s ≡ (h(m))^d mod n, where h(m) is the hash of the message m.
Output the signature s.
Compute h’ ≡ s^e mod n, where s is the signature.
Output “true” if h’ equals h(m) (the hash of the message).
Otherwise, output “false.”
What is the main problem with using a small exponent e in RSA?
Provide an example where Small Exponent RSA fails.
How can the problem with Small Exponent RSA be mitigated?
If both the message m and exponent e are small, the ciphertext c=m^e may not require reduction modulo n, making the ciphertext easy to reverse and compromising security.
For n = 663847, e = 3, and c = 4096:
Since 4096 = 16^3, we can deduce that the message m = 16 without factoring n, as the computation c = m^e is easy to reverse.
The issue can be mitigated by padding the message before encryption, ensuring the encoded message is large enough to prevent the ciphertext from being easily reversible
What is the CRT attack on low-exponent RSA encryption?
How does Eve exploit the CRT attack?
What is the mathematical vulnerability in this CRT attack?
How does randomized padding prevent the CRT attack?
The CRT (Chinese Remainder Theorem) attack exploits the use of the same message encrypted with a low exponent e=3 and different RSA moduli, allowing an attacker to recover the original message m without reduction.
Eve intercepts ciphertexts cA,cB,cCc sent to Alice, Bob, and Charlie, encrypted as cX ≡ m^3 mod n.
Using the Chinese Remainder Theorem, she combines the equations to compute m^3 mod (nA∗nB∗nC).
Since m is smaller than all the n, this results in m^3 < nA∗nB∗nC, so Eve can compute the cube root to recover m.
If m^3 < nA∗nB∗nC, no modular reduction occurs, making m^3 directly recoverable, and the attacker can take the cube root to find m.
By padding the message with random bits before encryption, the effective size of m increases, making m^3 larger than nA∗nB∗nC, thus requiring modular reduction and preventing direct cube root computation.
What is the issue with related messages and small exponents in RSA?
How are the ciphertexts c1 and c2 related in this attack?
What is the key mathematical observation used in this attack?
How is A computed in this attack?
How is B computed in this attack?
How is m1 recovered using A and B?
What is the vulnerability in this attack?
How can this issue with RSA be mitigated?
If two related messages (m2 = a * m1 + b) are encrypted using the same modulus n and a small exponent e = 3, it is possible to recover m1 from the ciphertexts without factoring n.
The ciphertexts are:
c1 = m1^3 mod n
c2 = (a * m1 + b)^3 mod n,
where a and b are known constants.
Expanding c2 = (a * m1 + b)^3 gives:
c2 = a^3 * m1^3 + 3 * a^2 * m1^2 * b + 3 * a * m1 * b^2 + b^3.
This equation allows the attacker to compute m1.
A is computed as:
A = b * (c2 + 2 * a^3 * c1 - b^3).
This simplifies to:
A = 3 * a * b * m1^2 + a * m1 * b + b^2 (mod n).
B is computed as:
B = a * (c2 - a^3 * c1 + 2 * b^3).
This simplifies to:
B = 3 * a * b * m1^2 + a * m1 * b + b^2 (mod n).
The relationship A / B = m1 (mod n) allows the attacker to compute m1 directly once A and B are known.
The vulnerability arises because the messages are related (m2 = a * m1 + b) and the exponent e = 3 is small, allowing the attacker to exploit the mathematical relationship between the ciphertexts.
This issue can be mitigated by using randomized padding, which ensures that related messages m1 and m2 appear completely unrelated after encryption, preventing the attacker from leveraging their relationship.
When is an encryption system homomorphic?
Why is RSA encryption considered homomorphic?
What is the specific operation that makes RSA homomorphic?
Why are RSA signatures not homomorphic?
An encryption system is homomorphic if there exist operations on the ciphertext space and the message space such that the operation on ciphertexts corresponds to an operation on plaintexts.
In mathematical terms:
Enc_k(m1) ∘ Enc_k(m2) = Enc_k(m1 ∆ m2),
where ∘ and ∆ are operations in the ciphertext and message spaces, respectively.
RSA encryption is homomorphic because:
For two messages m1 and m2 encrypted with the same key, the product of their ciphertexts corresponds to the ciphertext of the product of the plaintexts.
Mathematically: c1 * c2 ≡ (m1^e) * (m2^e) ≡ (m1 * m2)^e mod n.
multiplication modulo n
RSA signatures are not homomorphic because they use a hash function h(m) before signing. This hash function breaks the direct mathematical relationship between operations on the ciphertext and plaintext.
What abilities does an attacker have in a chosen ciphertext attack (CCA1, CCA2)?
Why are homomorphic encryption systems vulnerable to chosen ciphertext attacks (CCA2)?
How does an attacker exploit a homomorphic encryption system in a CCA2 attack?
What is the critical property exploited by the attacker in homomorphic encryption?
In CCA1 (non-adaptive), the attacker can ask for decryptions of ciphertexts before seeing the target challenge ciphertext.
In CCA2 (adaptive), the attacker can continue asking for decryptions even after seeing the challenge ciphertext.
Homomorphic encryption systems allow operations on ciphertexts that directly translate to operations on plaintexts. This property can be exploited by an attacker to manipulate ciphertexts and deduce the plaintext.
The attacker picks a random message r.
Computes the ciphertext for r as c_r = Enc_pk(r).
Forms a new ciphertext c’ = c_r ◦ c, where c is the ciphertext of the target message.
Submits c’ for decryption.
The decryption reveals r △ m, allowing the attacker to recover m using r.
The operation ◦ in the ciphertext space directly corresponds to an operation △ in the plaintext space, allowing the attacker to recover relationships between plaintexts.
What is one-wayness in cryptography?
One-wayness is a property of an encryption scheme where it is computationally infeasible to recover the plaintext m from its ciphertext Enc_pk(m) without the private key, ensuring the confidentiality of the message.
What is existential unforgeability (EU) in cryptography?
Existential unforgeability ensures that an attacker cannot create a valid signature for any new message, even if they have access to signatures for other messages.
What is universal unforgeability (UU) in cryptography?
Universal unforgeability ensures that an attacker cannot create a valid signature for a specific chosen message, even if they have access to signatures for other messages.
What are possible attacker goals when Sign(m) ≡ m^d mod n?
What abilities does an attacker have when attacking Sign(m) ≡ m^d mod n?
How does the attacker perform an EU-KMA attack?
How does the attacker perform a UU-CMA attack?
Produce forgeries on any message m, breaking universal unforgeability (UU).
Create some forgery (no control over the message), breaking existential unforgeability (EU).
Known Message Attack (KMA): The attacker knows some (m, Sign(m)) pairs.
Chosen Message Attack (CMA): The attacker can request signatures (m, Sign(m)) on messages of their choice.
Given a known pair (m1, Sign(m1)), the attacker computes:
m2 ≡ m1^2 mod n.
s2 ≡ (Sign(m1))^2 mod n.
The pair (m2, s2) is a valid signature for the new message m2.
To construct a signature for message m, compute:
m’ ≡ m · 2^e mod n.
Request a signature on m’, obtaining:
(m’, Sign(m’)) = (m’, (m · 2^e)^d) = (m’, m^d · 2).
Present the pair (m, (Sign(m’) / 2 mod n)) as a valid signature for message m.
What abilities does an attacker have in a Chosen Plaintext Attack (CPA)?
What is indistinguishability (IND) in cryptography?
Why is Schoolbook RSA not IND-CPA secure?
What is the implication of Schoolbook RSA not being IND-CPA secure?
In a CPA, the attacker can request encryptions of plaintexts of their choice, allowing them to analyze how the encryption algorithm works with different inputs.
Indistinguishability ensures that an attacker cannot determine which of two chosen plaintexts m0m_0m0 or m1m_1m1 was encrypted into a given ciphertext ccc, even with a probability slightly better than random guessing (50%). This is a core property for semantic security.
Schoolbook RSA is deterministic, meaning the same plaintext always encrypts to the same ciphertext.
The attacker can choose two random messages m_0 and m_1, and the challenger encrypts one of them.
The attacker can compute m0^e mod n and m1^e mod n and compare which matches the ciphertext c, breaking indistinguishability.
If Schoolbook RSA is not IND-CPA secure, it is also not IND-CCA secure (indistinguishability under chosen ciphertext attack), as IND-CCA security implies IND-CPA security.
How does RSA PKCS#1 v1.5 work through padding?
What must a decoder check when decoding PKCS#1 v1.5 padded messages?
What vulnerability did Bleichenbacher discover in PKCS#1 v1.5?
How does Bleichenbacher’s attack work in PKCS#1 v1.5?
Padding ensures the message m is randomized and expands to match the length of the modulus n, while adding a structure to the encoded message.
It begins with 00 02, followed by a random r (at least 8 bytes long and does not include 00), then 00 and ends with the message m.
In other words, the structure is:
00 02 r 00 m
Check that pad(m) starts with 00 02.
Locate the separator 00 after r.
Extract m if all conditions are satisfied.
If the padding format is incorrect, decoding fails.
Bleichenbacher discovered that failure messages during decoding could be exploited in an adaptive chosen-ciphertext attack to gradually recover the plaintext mmm.
The attacker sends modified ciphertexts s^e * c mod n for known values of s (where s is an arbitrary multiplier).
Based on decoding success or failure, the attacker infers if s ⋅ pad(m) 00 02.
This process narrows the range of possible plaintexts m.
By repeating the attack, the attacker builds relations to fully recover mmm.
What is the Output-Feedback Mode (OFB) in encryption?
How is encryption performed in OFB?
How is decryption performed in OFB?
What are the main properties of OFB mode?
What are the advantages of using OFB mode?
What are the disadvantages of using OFB mode?
OFB is a block cipher mode where the cipher operates as a stream cipher by using feedback from its own output. The ciphertext is created by XORing the plaintext with a precomputed keystream derived from the encryption of an initialization vector (IV).
Encryption in OFB uses the formula Ci = Mi XOR Enck^(i+1)(IV) for block i.
Each block of plaintext Mi is XORed with the encrypted output of the previous operation, starting with the IV.
Decryption in OFB uses the formula Mi = Ci XOR Enck^(i+1)(IV).
The ciphertext block Ci is XORed with the same precomputed keystream value used during encryption.
OFB does not require the decryption function (Dec).
Encryption resembles the data flow of a stream cipher.
Later blocks have higher computational costs, but the keystream can be precomputed independently of the plaintext.
It can precompute the keystream before encryption or decryption.
Errors in ciphertext do not propagate to subsequent blocks during decryption.
Suitable for streaming data and partial plaintext blocks.
It is sensitive to reuse of the same IV, which can lead to vulnerabilities.
Computationally more expensive for later blocks if the keystream is not precomputed.
It does not provide data integrity protection, as changes in ciphertext go undetected.
What is Counter Mode (CTR) in encryption?
How is encryption performed in CTR mode?
How is decryption performed in CTR mode?
What are the key properties of CTR mode?
What is the role of the IV and counter in CTR mode?
What are the advantages of using CTR mode?
What are the potential disadvantages of CTR mode?
Counter Mode (CTR) is a block cipher mode that transforms a block cipher into a stream cipher. It encrypts plaintext blocks by XORing them with an encrypted counter, which is a concatenation of an initialization vector (IV) and a counter value.
To encrypt in CTR mode, the formula is:
Ci = Mi XOR Enck(IV | i)
where Mi is the plaintext block, Enck is the encryption function with the key, IV is the initialization vector, and i is the counter value.
To decrypt in CTR mode, the formula is:Mi = Ci XOR Enck(IV | i)The same keystream used during encryption is reused during decryption.
CTR does not require the decryption function (Dec).
Each block has the same computational cost.
The encryption stream can be precomputed.
Allows local encryption and decryption for individual blocks.
Parallelizable encryption and decryption for high efficiency.
Precomputation of the encryption stream allows faster processing.
Localized encryption and decryption of specific blocks are possible
Reusing the IV leads to vulnerabilities, including plaintext recovery.
Requires careful management of counters and IVs to avoid reuse.
What is 3-DES and how does it work?
Why is 3-DES less secure when using two keys (k1 = k3)?
3-DES is an encryption method that applies DES three times with three different keys:
C = Enc_k3(Dec_k2(Enc_k1(M))). It can also operate with k1 = k2 = k3
Two-key 3-DES has weaknesses that make it susceptible to attacks requiring only 2^112 steps instead of 2^168
What is the attack cost for 3-DES with three keys?
The attack requires 2^56 storage and 2^112, which is lower than the expected 2^168
