W6 Flashcards
How many primes are there up to n?
n / ln(n)
What theorem is the foundation of the p−1p - 1p−1 factoring method?
What does this theorem state?
How is the p−1 method used to find a factor p?
What are the key steps of the p−1 factoring method?
Why is s chosen with many small prime factors in the p−1method?
What to do if the computation fails to find a factor?
Fermat’s Little Theorem,
a^(p−1) ≡ 1 mod p for prime p and gcd(a, p) = 1.
By calculating gcd(a^(p−1) − 1,n) for various values of aaa and using modular arithmetic.
1.Choose a large s:
Select s as a number with many small prime factors (e.g., lcm(1,2,…,20).
2. Choose a random base, a, coprime to n.
3. Compute a^s mod n:
Use a random base a and fast exponentiation.
4. Compute gcd(a^(s−1),n):
If gcd returns a non-trivial factor of n, a factor of n is found.
To ensure s has a high likelihood of being a multiple of p−1, increasing the chance of success.
Increase s by including larger prime factors OR Choose a different random base a.
What is the common knowledge shared by all parties in the Diffie-Hellman Key Exchange?
What prerequisites must Alice, Bob have for Diffie-Hellman Key Exchange?
How is the shared secret key generated in Diffie-Hellman?
What is the purpose of hashing the shared secret g^ab?
What is the main application of the shared key in Diffie-Hellman?
Everyone knows a group G and a generator g
A private key a (a random integer).
A public key h_A=g^a
The shared secret key is h_Ab=(g^a)^b=g^ab=(g^b)^a=h_Ba.
The hash of g^ab is used as the key for symmetric cryptography.
Alice and Bob use the shared key to authenticate and encrypt their communication using symmetric cryptography
Why are some groups G unsafe for Diffie-Hellman?
What group did Diffie and Hellman suggest using?
What groups are commonly used in practice for Diffie-Hellman?
Certain G, like (Q,⋅) with g=2, can reveal private keys because they may have small bit lengths.
(F_p^∗,⋅), where g is a primitive element, meaning a generator of the entire group.
Subgroups of (Fp∗,⋅) with g of large prime order.
What is the Computational Diffie-Hellman Problem (CDHP)?
What is the Decisional Diffie-Hellman Problem (DDHP)?
What is the Discrete Logarithm Problem (DLP)?
How are DLP, CDHP, and DDHP related in terms of difficulty?
Given g, g^a, and g^b, compute g^{ab}
Given g, g^a, g^b, and g^c, decide whether g^c = g^ab
Given g, g^a, compute a.
If DLP can be solved, then CDHP and DDHP are easy.
If CDHP can be solved, then DDHP is easy.
How can a Man-in-the-Middle attack occur in Diffie-Hellman?
Eve intercepts and replaces public keys exchanged between Alice and Bob.
She establishes separate shared secrets with each, decrypting and re-encrypting messages to appear as if they are communicating directly.
This happens because DH lacks authentication.
What is Semi-Static Diffie-Hellman (DH)?
What is a static key?
What is an ephemeral key?
What are the steps involved in Semi-Static DH?
How is symmetric encryption used in Semi-Static DH?
Semi-Static DH combines public-key and symmetric-key cryptography for secure communication between a static key holder (Alice) and an ephemeral key user (Bob).
A static key is a long-term key pair used by Alice for multiple communications.
An ephemeral key is a short-lived key used by Bob for a single session to ensure forward secrecy.
- Key Preparation:
Alice publishes long-term public key h_A = g^a.
Bob generates an ephemeral private key k randomly and computes r = g^k. - Encryption by Bob:
Bob computes shared secret : (h_A)^k = (g^a)^k = g^(ak)
Bob derives symmetric encryption key by hashing (h_A)^k: H((h_A)^k)
Bob encrypts message using symmetric encryption key and sends ciphertext c alongside public key r=g^k to Alice. - Decryption by Alice:
Alice receives Bob’s r=g^k and computes r^a = g^(ka).
She derives symmetric key by hashing r^a.
Decrypts ciphertext.
Symmetric encryption secures the actual message after deriving a shared secret through DH.
What is the objective of the Baby-Step Giant-Step attack?
What is its use in cryptology?
What is a cyclic group?
What is the setup step in the Baby-Step Giant-Step Algorithm?
What happens during the baby steps in the BSGS algorithm?
What happens during the giant steps in the BSGS algorithm?
What happens if a match is found?
What is the time complexity of this algorithm?
What is the time complexity?
How many multiplications and inversions does BSGS require?
To compute the discrete logarithm a in a cyclic group with generator g, given h_A=g^a.
Generic attack on cryptographic groups, emphasizing the importance of choosing groups where such attacks are computationally hard.
A cyclic group is generated by g, and its order l is the number of elements in the group
Compute m= floor(sqrt(l)), where l is the order of the generator g
Precompute and store g^i for i=0,1,…,m−1 in a hash table for efficient lookup.
Compute S= g^{-m}, then calculate h_A * S^j for j=0,1,… and check for matches with precomputed baby steps.
If a match is found, let g^i be the matching baby step and h_A * S^J be the corresponding giant step.
Solve for a using:
g^i = h_A * S^j equiv to
g^i = g^a * g^(-mj) equiv to
a = i + mj
O(sqrt(l)) - baby steps + giant steps
O(sqrt(l)) - storing the baby steps
2m+2 multiplications and 1 inversion
Does BSGS work in any cyclic group?
What does this mean about the DLP?
Yes
It cannot be harder than O(sqrt(|G|))
How does the parity (even/odd) of a, b, or c help in attacking DDHP?
How can one determine whether if a in h_A = g^a is even without knowing a?
How is the probability of being able to reject c calculated?
If at least one of a or b is even, ab mod (p−1) is even.
If both are odd, ab mod (p−1) is odd.
This property can detect c with a probability of 1/2.
By computing h_A^((p-1)/2), which is 1 if a is even and p-1 if a is odd.
If a or b are even, ab is even. ab is thus even with prob 3/4.
Else, ab is odd if a,b are odd. Prob 1/4.
In either cases, there is a 1/2 chance that c has the parity.
Thus, prob of being able to reject c is (3/4 + 1/4) * 1/2 = 1/2
How does Alice generate her keys in ElGamal encryption?
How does a user encrypt a message for Alice using ElGamal encryption?
How does Alice decrypt a ciphertext in ElGamal encryption?
What are the positive aspects of ElGamal encryption?
What are the downsides of ElGamal encryption?
Publishes her public key h_A=g^a, where g is a generator and a is her private key.
Keeps her private key a secret.
To encrypt m∈G a user:
1. Picks a random k and computes r=g^k.
2. Encrypts the message as c=(g^ a)^k⋅m.
3. Sends (r,c) to Alice.
Alice decrypts (r,c) by:
1. Computing r^a=(g^k)^a=g^(ak).
2. Finding m = c /r^a =(g^(ak)⋅m)/g^(ak)=m.
ElGamal:
Is homomorphic (supports certain computations on ciphertexts).
Is randomized, providing additional security by using a random k for each encryption.
Downsides include:
1 Requires m∈G (messages must belong to the group GGG).
2. Its homomorphic property can be a double-edged sword, potentially weakening security in some scenarios.
3. It is not OW-CCA II secure (not secure under chosen-ciphertext attacks).
What are Alice’s keys in the ElGamal signature scheme?
How does Alice sign a message m in ElGamal?
How is an ElGamal signature verified?
Where do the computations in the ElGamal signature scheme take place?
Why is k crucial in ElGamal signatures?
Public Key: h_A=g^a, where g is the generator.
Private Key: a, kept secret.
- Pick a random k.
- Compute r=g^k.
- Compute s ≡ k^(−1) (H(m)−ar) mod l, where H(m) is the hash of the message.
- The signature is (r,s).
Compute g^ H(m)− r^s ⋅ (h_A)^r.
If the result equals 0, the signature is valid.
All computations in the exponents are performed modulo the order of g (ℓ).
Ensures that the signature is unique and secure for each message, even if the same private key is used.
What is a threshold system?
Why are threshold systems used in cryptography?
How can threshold systems emulate more powerful users?
How many points are needed to uniquely determine a line?
What information does a single point provide about a line?
How many points are needed to uniquely determine a polynomial of degree t−1?
A system where a secret is shared among N users, and any t-out-of-N users can recover the secret, while t−1 or fewer users gain no information about it.
They ensure that private keys (or secrets) are not controlled by a single individual but instead require collaboration from a group to perform actions like decryption or signing.
By giving more shares to specific users, making their participation more critical in reconstructing the secret.
Two points are needed to uniquely determine a line.
A single point provides no information about where the line intersects the y-axis, as many lines can pass through the same point.
t points are needed to uniquely determine a polynomial of degree t-1
What is the purpose of Shamir Secret Sharing?
How is the polynomial in Shamir Secret Sharing defined?
What key property does the polynomial f(x) satisfy in Shamir Secret Sharing?
How are shares generated in Shamir Secret Sharing?
To securely share a secret a among N users, where any t-out-of-N users can reconstruct the secret, while t−1 or fewer cannot learn anything about it.
A degree t−1 polynomial is created as:
f(x)=a+ sum from i=1 to i=t-1 of f_i * x^i,
where a is the secret, and f1,f2,…,ft−1 are random coefficients.
f(0) = a, ensuring that the secret a can be recovered
each user receives a secret share (i, f(i)) where i is not 0 or the same for different users
How is the secret reconstructed in Shamir Secret Sharing?
What is Lagrange Interpolation?
What is the formula for Lagrange Interpolation in Shamir Secret Sharing?
Any t shares can reconstruct f(x) using Lagrange Interpolation to compute f(0)=a.
A mathematical method used to reconstruct a polynomial from ttt points.
(Sum from j=1 to t OF f(i_j)) *
(Product from k=1, k!=j to k=t OF (i_k / i_k - i_j) )
What happens after t parties compute a?
What is a better alternative to having a trusted party compute a?
How does the additivity of shares improve the scheme?
They no longer need the other shares, and a can be used by a trusted party, which then forgets both a and the shares.
Use the shares locally for partial decryption/signature, then combine these parts using Lagrange coefficients
It allows users to combine partial results locally without relying on a centralized trusted party.
