Digital RSA Signiture

Intro to Cybersecurity (암호학 전체 지도)

• Symm. (Symmetric - 대칭키): 암호화와 복호화에 같은 키를 쓰는 방식입니다. 프로젝트에서 C언어로 직접 구현하실 DES, AES가 바로 여기에 속합니다.
• Asymm. (Asymmetric - 비대칭키/공개키): 암호화 키와 복호화 키가 다른 방식입니다. 우리가 방금까지 뼈빠지게 공부했던 RSA, D-H, EC (타원 곡선), ECDH가 모두 여기에 있습니다.
• Protocols/Services (응용 프로토콜/서비스): 앞의 두 가지 수학적 도구들을 이용해 실제 보안 서비스를 만드는 단계입니다. 노란색 형광펜이 칠해진 DSA (Digital Signature Algorithm), 그리고 Hash, 인증서(Certificate) 등이 앞으로 배울 기말고사 후반부의 메인 테마입니다.

Introduction to Digital Signature (디지털 서명의 원리)

단순히 데이터를 숨기는 암호화(Encryption)를 넘어, "이 문서를 보낸 사람이 진짜 앨리스가 맞고, 중간에 내용이 변조되지 않았다"는 것을 증명하기 위한 기술입니다.

• Goal: 디지털 세계를 위한 서명 기능 만들기. 여기서 시험에 무조건 써야 할 핵심 키워드는 "proof of authenticity of the sender" (송신자 인증 및 진위 증명) 입니다.

• Traditional (물리적 서명의 치명적 한계):
  교수님이 성적표(Grade)로 아주 직관적인 예시를 드셨네요. 종이 성적표에 '61'점이라고 적고 서명(sig.)을 했을 때, 누군가 서명만 가위로 오려내고 성적을 '98'점으로 위조한 뒤 서명을 다시 풀로 붙여버리면 위조를 알아채기 힘듭니다. 즉, 아날로그 서명은 '문서의 내용(Content)'과 '서명(Signature)'이 독립적으로 분리되어 있다는 치명적인 약점이 있습니다.

• Digital World (디지털 서명의 해결책):
  수식 $Sig_K(x) = y$ 가 핵심입니다.

  • $x$: 원본 문서 (Document)
  • $K$: 서명자의 비밀키 (Private Key)
  • $y$: 생성된 디지털 서명 (Signature)

디지털 서명 $y$는 문서 원본 내용인 $x$를 암호학적 함수에 직접 집어넣어 만듭니다. 만약 해커가 중간에 문서 내용을 단 1비트라도 조작하면(예: 61점을 98점으로 변경), 원본 $x$값이 달라졌기 때문에 기존에 만들어둔 서명 $y$와 수학적으로 짝이 전혀 맞지 않게 됩니다.

대칭키를 이용한 디지털 서명의 한계 (Court Problem)

Alice가 Bob에게 보낼 문서 $x$에 서명($y$)을 할 때, 둘만 아는 대칭키(예: AES 키 $K$)를 사용했다고 가정해 봅시다.

• Sign (서명 생성): $Sig_{AES, K}(x) = y$ (Alice가 키 $K$로 서명)
• Verification (서명 검증): $Ver_K(x, y) = True$ (Bob이 키 $K$로 확인)
• 문제 발생 (The Dispute):
  만약 Alice가 보낸 원래 문서가 $x = \$4K$ 였는데, Bob이 몰래 문서를 $\tilde{x} = \$50K$ 로 위조하고 싶다고 합시다. Bob은 Alice와 똑같은 대칭키 $K$를 공유하고 있으므로, 스스로 위조된 서명 $Sig_K(\tilde{x}) = y$ 를 새로 만들어 낼 수 있습니다.
• Court (법정 분쟁): Alice는 "4K 짜리 문서다!"라고 주장하고, Bob은 "50K 짜리 문서다!"라고 주장하며 법정에 갑니다. 판사는 누구 말이 맞는지 판결할 수 있을까요?
  $\rightarrow$ 절대 불가능합니다. Alice와 Bob 둘 다 똑같은 키 $K$를 가지고 있기 때문에, 이 서명을 누가 만들었는지(Alice가 만들었는지 Bob이 위조했는지) 제3자는 기술적으로 구별할 방법이 없습니다.

보안 서비스의 4대 목표 (4 Important Security Services)

1. Confidentiality (기밀성): 허가된 사람만 정보를 볼 수 있게 숨기는 것. (Encryption)
2. Message Authentication (메시지 인증): 메시지를 보낸 사람이 진짜 그 사람이 맞는지 확인하는 것.
3. Message Integrity (메시지 무결성): 전송 도중 해커(Trudy)에 의해 메시지가 변조되지 않았음을 확인하는 것.
4. Non-repudiation (부인 방지) ★가장 중요★: 메시지를 보낸 사람이 나중에 "내가 안 보냈어!"라고 오리발을 내밀거나, 받는 사람이 "이거 네가 보낸 거 맞잖아!"라고 문서를 위조하여 우기는 것(Insider Attack)을 막는 기능입니다.

결론: 왜 비대칭키(Asymmetric Key)인가?
앞서 본 법정 분쟁(Court Problem)은 결국 Non-repudiation(부인 방지)이 실패했기 때문에 발생했습니다. 대칭키로는 이 문제를 영원히 해결할 수 없습니다.

• 해결책 ($\implies$ Asymm.):
  부인 방지를 달성하려면 무조건 비대칭키(Asymmetric Key)를 써야 합니다.Alice만이 가진 Private Key로 서명을 만들고, 세상 사람 누구나 Alice의 Public Key로 그 서명을 검증할 수 있게 만들면 됩니다. 이렇게 하면 Bob은 Alice의 Private Key를 모르기 때문에 문서를 위조할 수 없고, Alice도 자기가 서명해 놓고 안 했다고 발뺌할 수 없게 됩니다.

암호화(Encryption) vs 서명(Signature)의 결정적 차이

맨 위 빨간색/파란색 펜으로 비교해 둔 부분은 비대칭키(공개키) 암호학에서 가장 헷갈리기 쉬운 개념이자 핵심입니다. "누구의 키를 쓰는가?"가 완전히 반대입니다.

Asymm. Encryption (비대칭키 암호화 - 오른쪽):

• 목적: 기밀성(Confidentiality). 오직 수신자(Bob)만 열어볼 수 있게 숨기는 것.
• 과정: Alice는 Bob의 공개키($K_{pub}$)로 메시지를 암호화($E$)해서 보냅니다.
• 복호화: Bob은 자신만 아는 Bob의 개인키($K_{pr}$)로 복호화($E^{-1}$)해서 읽습니다.

DSA / Digital Signature (디지털 서명 - 왼쪽):

• 목적: 부인 방지(Non-repudiation). 이 문서를 보낸 사람이 진짜 Alice가 맞음을 만천하에 증명하는 것.
• 과정: Alice는 Alice 자신의 개인키($K_{pr}$)로 메시지에 서명($S$)을 합니다.
• 검증: 세상 사람들(Public/Bob)은 누구나 다 아는 Alice의 공개키($K_{pub}$)를 이용해 그 서명을 복호화($S^{-1}$)해보고, 원본 메시지 $x$와 똑같이 나오는지($x' = x$) 확인합니다.

RSA Digital Signature 프로토콜 & 증명

Step 1 & 2: Signing & Verification (서명과 검증)

Alice의 RSA 키 세팅:
개인키 $K_{prA} = d$
공개키 $K_{pubA} = (n, e)$

1. 키 구조 (Key Setup)
   $k_{pr} = d = 2673$: Alice만 알고 있는 비밀 개인키(Private Key)입니다.
   $k_{pub} = (n, e) = (9797, 131)$: 모두에게 공개된 공개키(Public Key)입니다.

2. 서명 생성 (Alice의 관점)
   생성 공식: $y = e_{k_{pr}}(x) = x^d \pmod{n}$
   (여기서 필기의 $y$는 이전 문제의 $sig(x)$를 의미합니다.)

• 예시 (Ex): 원본 메시지 $x = 4333$일 때,
  $y = 4333^{2673} \pmod{9797} = 1424$

3. 서명 검증 (Bob의 관점)
   검증 공식: $x' = d_{k_{pub}}(y) = y^e \pmod{n}$

• Bob은 Alice의 서명 $y(1424)$를 받아서, 누구나 아는 공개키 $e(131)$를 사용해 거듭제곱을 수행합니다.
• 검사 (Check): 계산되어 나온 값 $x'$이 원래 메시지 $x$와 일치하는지(if x = x') 확인합니다.

Existential Forgery Attack (존재적 위조 공격)

이 공격은 해커(Trudy)가 Bob의 개인키($d$)를 전혀 모르더라도, 수학적 트릭을 써서 '검증을 통과하는 유효한 서명'을 임의로 만들어내는 공격입니다.

정상적인 서명 과정: Bob은 자신의 개인키 $d$를 이용해 메시지 $x$에 대한 서명 $S$를 만듭니다. ($S = x^d \bmod n$)

Trudy의 공격 단계 (Active Attacker):
1. Trudy는 그냥 아무 숫자나 하나 골라서 가짜 서명 $S'$라고 우깁니다. ($S' \in \mathbb{Z}_n$)
2. 이 가짜 서명에 Bob의 공개키 $e$를 승수하여 메시지 $x''$를 역으로 계산해 냅니다. ($x'' \equiv (S')^e \pmod n$)
3. 그리고는 Alice에게 $(x'', S')$ 쌍을 보내며 "이거 Bob이 서명한 거야!"라고 속입니다.

Alice의 검증 (Verification):
1. Alice는 받은 가짜 서명 $S'$에 Bob의 공개키 $e$를 승수하여 $x'$를 계산합니다. ($x' \equiv (S')^e \pmod n$)
2. 그리고 받은 메시지 $x''$와 자신이 계산한 $x'$가 같은지 비교합니다. ($x \equiv x'$)
3. 결과: Trudy가 애초에 $x''$를 $(S')^e \bmod n$으로 계산해서 보냈기 때문에, Alice가 계산한 식과 완벽하게 일치합니다!

결론: Alice의 검증 시스템은 이를 Valid signature (유효한 서명)로 판정해 버립니다. 공격 성공!

Limitations (공격의 한계점)

공격이 성공하긴 했지만, 이 공격에는 아주 치명적인 현실적 한계가 있습니다.

• 핵심 한계: Trudy cannot directly control the semantics of the message $x''$. (Trudy는 메시지 $x''$의 의미(Semantics)를 직접 제어할 수 없습니다.)

이유:

• Trudy가 진짜 원하는 것은 "Trudy에게 100만 달러를 송금하라" 같은 의미 있는 메시지에 대한 가짜 서명을 만드는 것입니다.

• 하지만 이 공격은 '가짜 서명 $S'$를 먼저 맘대로 고르고 $\rightarrow$ 그에 맞춰 메시지 $x''$를 수학적으로 역산'하는 방식입니다.

• 이렇게 수학적으로 도출된 $x''$를 텍스트로 변환해 보면 그저 의미를 알 수 없는 외계어, 즉 pseudorandom number (유사 난수/쓰레기 값)에 불과합니다.

MUL DLP $\rightarrow$ impossible:

• 만약 Trudy가 "돈을 보내라"라는 특정 메시지 $X_{target}$을 먼저 정해두고 이에 맞는 서명 $S'$를 찾으려 한다면, $S' \equiv \sqrt[e]{X_{target}} \pmod n$ 을 풀어야 합니다.
• 모듈러 $n$ (1024~2048 bits 크기) 환경에서 이 거듭제곱근을 구하는 것은 개인키 $d$ 없이는 수학적으로 불가능(impossible)합니다. (교수님 필기에는 이를 이산 대수 문제인 MUL DLP와 연관 지어 불가능하다고 표현하셨습니다.)