Title: INTROSEC / asymmetric_cryptography
Tags: asymmetric_cryptography RSA digital_signatures diffie_hellman asymmetric_encryption hash_functions symmetric_cryptography

Q: What are the benefits of asymmetric cryptography?
A: - every communication party needs less keys (\(n\) pairs instead of \(\approx n^2\))
- public keys can be distributed over insecure channels

Q: Explain asymmetric encryption.
A: Asymmetric encryption schemes use different keys for encryption (public) and decryption (private). The decryption key must not be derivable from the encryption key.

Q: Which one-way functions are used in asymmetric schemes?
A: - Integer factorization (\(p \cdot q \ |\ (p,q) \in P\))
- Discrete logarithms (\(g^x\mod p\))

Q: What is Euler's totient function?
A: The Euler's totient function \(\Phi\) maps each integer \(n\) to the number of integers up to \(n\) that are coprime to \(n\) (i.e., greatest common divisor is 1)
- if \(n\) is prime, \(\Phi(n)=n-1\)
- if \(n=pq\) : \(\Phi(n)=(p-1)(q-1)\)

Q: How is a RSA Key generated?
A: 1. Generate two large primes \(p,q\)
2. Compute the modulus \(N=pq\)
3. Choose a public exponent \(e <N\) coprime to \(\Phi(n)\), usually \(65537=2^{16}+1\)
4. The private exponent \(d\) is the modular inverse of \(e \text{ modulo } \Phi(N)\)

Q: What is the formula for encrypting a message with RSA?
A: \(c=m^e \mod N\)

Q: What is the formula for decrypting a message with RSA?
A: \(m=c^d \mod N\)

Q: What determines the security of the RSA algorithm?
A: The difficulty to factorize the modulus \(N\) as well as the secrecy of the totient value \(\Phi(N)\).

Q: What are the problems of Textbook RSA?
A: - Determinism: If the same message is encrypted multiple times with the same public key, the produced ciphertexts are the same
- Small messages can be brute-force decrypted with the formula \(m=\sqrt[e]{c+kN}\)

Q: What are the benefits of digital signatures over MACs?
A: Digital signatures provide data integrity and authenticity (Same as MAC). Additonally, they also provide public verifiability and nonrepudiation.

Explain the process of an asymmetric encryption scheme for digital signatures.

Q: How is RSA used for digital signatures?
A: \(m<N\ ... \) the message to be signed and
\(s\ ...\) the corresponding signature
- Signing: \(s = m^d \mod N\)
- Verification: Check if \(s^e \mod N\) equals \(m\)

Q: Is RSA secure for digital signatures?
A: No: Malleability of RSA can be used to generate valid signatures for new messages starting from signatures of other messages. If the private key’so owner is willing to sign only some of the attacker’s messages, arbitrary signatures can be computed.

Q: How do hash functions in digital signatures work?
A: 1. Hash the message
2. Sign the hash value of the message

Q: What are the benefits of hash functions in digital signatures?
A: - Efficient
- Diffusion
- Collision resistance

Q: Which method of digital signing is more secure, RSA or Hashing?
A: Hashing.
- It prevents attacks based on malleability, which are possible with RSA
- Hash is usually padded before signature computation; this helps to detect if the signature has been tampered with

Q: What is the Diffie-Hellman Protocol?
A: The Diffie-Hellman protocol is a key exchange protocol that enables the generation of a secret shared between two communicating parties over a public channel. It is based on the difficulty to compute discrete logarithms.

Q: How does the Diffie-Hellman Protocol work?
A: Let \(A\) and \(B\) be communication Partners.
1) The two communication partners need to (publicly) aggree on two parameters \(p,g\)
- \(p\) is a large prime number
- \(g\) is a primitive root modulo \(p\) (\(\{g^k \mod p \ | 1 \le k \le p\} = \{1,2,\dots,p-1\}\))
2) \(A\) and \(B\) each choose a private, random integer \(prv_A\) and \(prv_B\) as their private key: \(2 \le prv_{A,B} < p-2\)
3) Generation of public keys \(PUB\):
- for \(A\): \(PUB_{A}=g^{prv_A} \mod p\)
- for \(B\): \(PUB_{B}=g^{prv_B} \mod p\)
4) Public keys \(PUB\) get exchanged
5) The shared secret  \(S\) is calculated:
- \(S_{A}=(PUB_{B})^{prv_A} \mod p\)
- \(S_{B}=(PUB_A)^{prv_B} \mod p\)
\(S_A = S_B = S\)

Q: Which values should not be used for private keys in the Diffie-Hellman protocoll?
A: \(K_{prv} \neq \{1,\ p-1\}\)

Q: When are attacks possible with the Diffie-Helmann protocol?
A: When there is no authentication.

Q: Where is symmetric and asymmetric cryptogrophy used in an internet connection?
A: - asymmetric: authentication and key exchange
- symmetric: data exchange