$x_3 \equiv s^2 - x_1 - x_2 \pmod p$

$y_3 \equiv s \cdot (x_1 - x_3) - y_1 \pmod p$

$s \equiv \frac{y_2 - y_1}{x_2 - x_1} \pmod p$

$s \equiv \frac{3x_1^2 + a}{2y_1} \pmod p$

1 ECDH

개인 키 $a = 6$
상대방의 공개 키 $B = (5, 9)$
타원 곡선 $E: y^2 \equiv x^3 + x + 6 \pmod{11}$
(즉, $A = 1, B_{curve} = 6, p = 11$)

$B \rightarrow 2B \rightarrow 3B \rightarrow 6B$ 순서로 도출

1. 2B 구하기 (Point Doubling)
   

2. 3B 구하기 (Point Addition)
   

3. 6B 구하기 (Point Doubling)
   

2 RSA verification

1. $(x = 123, sig(x) = 6292)$
   검증식: $6292^{131} \pmod{9797}$
   연산 결과: $123$
   판정: 연산 결과가 원본 메시지 $123$과 일치하므로 유효한 서명입니다.

2. $(x = 4333, sig(x) = 4768)$
   검증식: $4768^{131} \pmod{9797}$
   연산 결과: $4333$과 일치하지 않습니다.
   판정: 유효하지 않은 서명입니다.

3. $(x = 4333, sig(x) = 1424)$
   검증식: $1424^{131} \pmod{9797}$
   연산 결과: $4333$
   판정: 연산 결과가 원본 메시지 $4333$과 일치하므로 유효한 서명입니다.

3 MAC-then-Encrypt

As we have seen, MACs can be used to authenticate messages. With this problem, we want to show the difference between two protocols—one with a MAC, one with a digital signature. In the two protocols, the sending party performs the following operation:

1. protocol A

where x is the message, h) is a hash function such as SHA-1, e is a private-key encryption algorithm, "||" denotes simple concatenation, and ki, kz are secret keys which are only known to the sender and the receiver.

문제의 핵심은 이 수식이 MAC(메시지 인증 코드) 기반의 프로토콜임을 인지하고, 이것이 디지털 서명(Digital Signature) 프로토콜과 어떤 결정적인 차이가 있는지 도출해내는 것입니다.

Key Difference: Non-repudiation

• MAC Protocol (Given): Uses shared secret keys ($k_1$, $k_2$). Since both parties know the keys, the receiver can also create the MAC. Thus, the sender can deny sending the message.

• Digital Signature: Uses the sender's unique private key. The receiver cannot forge the signature, guaranteeing that the sender cannot deny sending the message (Provides non-repudiation).

2. Protocol B

Provide a step-by-step description (e.g., with an itemized list) of what the receiver does upon receipt of y. You may want to draw a block diagram for the process on the receiver's side, but that's optional.

Receiver's Step-by-Step Process:

1. Decrypt: Decrypt the ciphertext $y$ using the shared symmetric key $k$ to retrieve $x || sig_{k_{pr}}(h(x))$.
2. Parse: Separate the original message $x$ and the digital signature $sig_{k_{pr}}(h(x))$.
3. Hash: Compute the hash of the received message independently to get a local $h(x)$.
4. Verify Signature: Decrypt the signature using the sender's public key $k_{pub}$ to extract the original $h(x)$.
5. Compare: Compare the local hash with the extracted hash. If they match, the message is authenticated and accepted.

4

You have to choose the cryptographic algorithms for a KDC where two different classes of encryption occur:

• $e_{k_{U,KDC}}()$ , where U denotes an arbitrary network node (user),
• $e_{k_{ses}}()$ for the communication between two users.

You have the choice between two different algorithms, DES and 3DES (Triple-DES), and you are advised to use distinct algorithms for both encryption classes. Which algorithm do you use for which class? Justify your answer including aspects of security as well as celerity

Algorithm Assignment:
$e_{k_{U,KDC}}()$: 3DES
$e_{k_{ses}}()$: DES

• Security: The master key ($k_{U,KDC}$) is long-term and critical; if compromised, all session keys are exposed. Thus, it requires the higher security of 3DES. The session key ($k_{ses}$) is short-lived, so the lower security of DES is acceptable since an attack would only compromise a single, temporary session.

• Celerity (Speed): User-to-user communication ($e_{k_{ses}}()$) involves encrypting large amounts of bulk data, which requires the faster processing speed of DES. Conversely, KDC-to-user communication only encrypts very small data (the session key itself), so the slower speed of 3DES does not cause performance issues.