8. Hash_Digital_Signature

CA·2025년 5월 28일

컴퓨터 보안

목록 보기

8/10

Hash Function

임의의 길이의 데이터를 고정된 길이의 데이터로 변환해주는 것.
Compression(압축): 압축하는것이 중요한데, 압축하는데 드는 비용이 적어야 된다. 압축하는데 드는 비용이 많이 드는 경우 효율성이 떨어진다.
Ease of computation: 입력 x가 주어졌을때 출력 h 구하는 과정이 쉬워야 된다.

Hash, Mac, Digital Signature을 만들 때 Hash Function이 쓰임.

침입 탐지에도 사용됨. (바이러스 detection)

PRNG

Cryptography hash function이 되기 위해서는 One-way hash function + (one-way property, Collision-free property)을 만족 해야된다.

Split two classes

Unkeyed hash functions

Keyed hash functions

Computationally infeasible:
해시값이 주어졌을 때 그 해시값을 만들어내는 입력값을 찾는게 Computationally 불가능해야 된다. (one-way property)

임의의 길이의 데이터를 고정된 길이로 데이터를 보내다보면 충돌이 일어날 수 있다.
ex) 2^10 -> 2^4이라면 반드시 겹치는 부분이 발생할 수 있다.(collision)
출력bit를 2^256으로 sha256? (Collision-free)하게 만들기 위해.
-> Collision-free property
같은 hash값을 갖는 서로 다른 데이터 오브젝트를 찾아내는 것이 Computationally infeasible 해야된다.
-> 출력 bit를 조절.

무결성 체크

방법: 데이터를 보낼 때 해당 데이터에 대한 해시값을 구해서 같이 보낸다. 그리고 hash function을 통해 hash 값을 구하고 데이터와 같이 받은 해시값과 비교해서 동일한지를 비교한다.
Man-in-the-middle attack에 취약하다. 만약 보안이 없다면.

Message Authentication Code (MAC)

데이터 무결성에 많이 사용됨.
secret key가 존재 해야 됨. (symmetric key)
공격자가 secret key를 알지 못할 경우, 메시지를 원하는 걸로 바꿔서 유효한 MAC 값을 만들어낼 수 없다.

ex) 엘리스 - 밥이 같은 데이터에 대해 MAC을 사용하면 엘리스도 MAC값을 통해 데이터 값을 변경 가능하고, 밥 또한 MAC값 즉 secret key를 공유하기에 데이터의 값을 변경이 가능하다. 그때 문제가 발생할 수 있음.

Digital Signature

전자서명
MAC과 비슷하게 입력값만 필요한게 아니라 MAC에서는 secret key가 필요했듯 뭔가 필요함.
Private key의 소유자만 Digital Signature를 만들 수 있음.
데이터를 수정할 수 있는 사람은 전자서명이 있는 사람만이 가능하다는 것을 보증.
Encryption할 때 Private key 사용 = Digital Signature 생성
서명할 때 사용한 Private key에 대응하는 Public key를 가진 누구나 Decryption 가능

Preimage

입력값
Hash Function을 H라 하고, H는 임의의 길이의 데이터를 고정된 길이의 데이터로 변환하기에 many-to-one mapping이고 그때 해시값 h = H(x)로 Preimage는 x를 말한다.

Collision

입력값이 다른데 같은 해시값이 나오는 것
x != y일 때, H(x) == H(y) 인 것

Requirements and Security

Efficiency:
x가 주어지면 H(x)를 쉽게 구할 수 있어야 함.

Preimage resistant(one-way property):
h값을 주고 h값을 만드는 메시지 y를 찾는 것이 computationally infeasible 해야한다.
Second preimage resistant(weak collision resistant):
입력 x가 주어지고 x !=y 입력에 대해 H(x) = H(y)가 computationally infeasible 해야한다.
Collision resistant(strong collision resistant):
동일한 h값을 만들어 내는 서로 다른 Preimage 2개 구하는것이 computationally infeasible.

One-way preoperty를 만족하고 Collision이 없을 경우 Cryptographic Hash Function으로 사용할 수 있다.

Collision Resistant Attacks

공격자가 서로 다른 두 개의 메시지나 데이터 블록을 찾아서 같은 해시 값을 갖도록 만드는 것을 목표로 한다.
-> input1 != input2, hash(input1) == hash(input2) 되게 만드는 것

이런 해시 충돌을 찾는 데 걸리는 노력은 생일 역설을 통해 설명 됨

생일 역설 (Birthday Paradox)

n비트 해시 함수에 대해 충돌을 찾는 데 필요한 시도 횟수는 2^(n/2)이다.
예: 120비트 해시 함수 → 2^(120/2) = 2^60

보안 수준 필요한 해시 출력 비트 수 (n)
Preimage, Second Preimage 저항성 2^n 시도 필요 → n비트 해시면 2ⁿ 시도 필요
Collision 저항성 (Birthday Attack) 2^(n/2) 시도면 충돌 가능 → n비트 해시라도 2ⁿ⁄² 시도로 충돌 찾을 수 있음

즉,
충돌 저항성을 위해선 해시 길이를 두 배로 해야 실제 보안성이 올라갑니다.
예: 128비트 해시 → 약 2⁶⁴ 시도로 충돌 가능
→ SHA-256 (256비트)을 쓰는 이유는 충돌 저항성을 2¹²⁸ 수준으로 보장하기 위해서예요.

공격 예시: 120비트 해시 함수 + 1GHz 컴퓨터
1GHz 컴퓨터는 초당 10^9 = 1,000,000,000번 연산 가능.
공격자가 충돌을 찾기 위해 2^60번의 해시 계산이 필요.
-> 2^60 / 10^9 = 35년.
즉, 한 대의 1GHz 컴퓨터로 120비트 해시 함수에 충돌 공격을 시도하면 약 35년이 소요된다는 의미.

목적 필요한 출력 비트 수
Preimage / Second Preimage 보안 n비트 해시 → 보안성 2ⁿ 수준
Collision 보안 (Birthday attack 저항) n비트 해시 → 보안성 2^(n/2) 수준

📌 예시:
원하는 보안 수준이 2¹²⁸이면:
Preimage 저항: 128비트 해시
Collision 저항: 256비트 해시 필요!

충돌 저항성을 위해선 해시 길이를 두 배로 해야 실제 보안성이 올라감
예: 128비트 해시 → 약 2⁶⁴ 시도로 충돌 가능
→ SHA-256 (256비트)을 쓰는 이유는 충돌 저항성을 2¹²⁸ 수준으로 보장하기 위해서.

해시 길이 (n비트) 충돌 기대 시도 횟수 실제 보안 수준
128비트 약 $2^{64}$ 중간 수준 보안
256비트 약 $2^{128}$ 고급 수준 보안

보안 수준	필요한 해시 출력 비트 수 (n)
Preimage, Second Preimage 저항성	`2^n` 시도 필요 → n비트 해시면 2ⁿ 시도 필요
Collision 저항성 (Birthday Attack)	`2^(n/2)` 시도면 충돌 가능 → n비트 해시라도 2ⁿ⁄² 시도로 충돌 찾을 수 있음

목적	필요한 출력 비트 수
Preimage / Second Preimage 보안	n비트 해시 → 보안성 `2ⁿ` 수준
Collision 보안 (Birthday attack 저항)	n비트 해시 → 보안성 `2^(n/2)` 수준

해시 길이 (n비트)	충돌 기대 시도 횟수	실제 보안 수준
128비트	약 $2^{64}$	중간 수준 보안
256비트	약 $2^{128}$	고급 수준 보안

Merkle-Damgård

전처리
목적: 공격자가 다른 메시지에 대해 같은 해시값을 만드는 것을 어렵게 만듦.

특징:

입력 메시지 길이에 관계없이 고정 길이 해시 생성 가능.

충돌 내성 제공, 하지만 길이 확장 공격에 취약.

현대 해시 함수들은 이 구조를 변형하거나 보완한 형태로 사용.

SHA-1, SHA-2

SHA

SHA-1

160비트 해시 값을 생성.

보안상의 취약점이 발견되어 현재는 권장 x

SHA-2

SHA-1의 보안 문제를 개선한 새로운 해시 알고리즘

256,384,512 비트

SHA-2는 실제로는 여러 버전(SHA-256, SHA-384, SHA-512 등)을 포함한 알고리즘 모음

"SHA-1과 SHA-2의 구조는 비슷"
→ 이 말은 두 해시 알고리즘이 내부적으로 Merkle-Damgård 구조를 기반으로 하고 있으며, 입력 블록을 반복적으로 압축하는 방식이 유사하다는 뜻입니다.
→ 단, SHA-2는 더 큰 해시 값과 더 복잡한 연산 구조로 보안이 강화되었어요.

SHA-3

SHA-2를 대체하는 것이 아니라 보완. (SHA-2가 깨지지 않음.)

항목 SHA-1 SHA-2 SHA-3
구조 Merkle-Damgård Merkle-Damgård Sponge 구조
발표 1995 2002 2012 (Keccak)
보안성 취약 안전 매우 안전 (새 구조)
역할 역사적 의미 주요 표준 SHA-2 보완용
용도 과거 사용 현재 널리 사용 고보안 환경, 선택적 사용

항목	SHA-1	SHA-2	SHA-3
구조	Merkle-Damgård	Merkle-Damgård	Sponge 구조
발표	1995	2002	2012 (Keccak)
보안성	취약	안전	매우 안전 (새 구조)
역할	역사적 의미	주요 표준	SHA-2 보완용
용도	과거 사용	현재 널리 사용	고보안 환경, 선택적 사용

HMAC

MAC(Message Authentication Code)

MAC은 메시지의 무결성(integrity) 과 인증(authenticity) 을 확인하는 데 사용되는 코드.
송신자가 메시지와 함께 MAC 값을 전송하면, 수신자는 동일한 방식으로 계산해본 MAC 값과 비교하여 메시지가 위조되지 않았는지 확인.

동기:

해시 함수(MD5, SHA 등) 는 블록 암호(AES, DES등) 보다 일반적으로 소프트웨어 환경에서 실행 속도가 더 빠름

다양한 프로그래밍 언어에서 MD5, SHA 등 해시 함수 라이브러리가 이미 구현됨.
-> 개발자가 별도로 암호화 알고리즘을 구현하지 않아도 MAC 적용 가능.

HMAC (Hash-based MAC)

HMAC은 해시 함수(MD5, SHA-1, SHA-2 등) 와 비밀 키(송신자와 수신자 대칭 키 사용)를 조합해서 MAC을 생성함

보안성, 속도, 호환성 측면에서 매우 실용적이기 때문에, 인터넷 프로토콜(예: TLS, IPsec 등)에서 광범위하게 사용됨

Digital Signature 1

각 사용자는:

개인키 (private key): 본인만 알고 있는 비밀 키

공개키 (public key): 누구나 알 수 있게 공개된 키

예: RSA, DSA 등

개인키를 가진 사람만이 서명 가능.

이 개인키는 본인만 알고 있어야 하며, 이 키로 생성된 서명은 본인만 만들 수 있음.

누구든지 공개키(Verification key)만 알면 서명의 유효성을 검증할 수 있다.

공개키는 인터넷에 공개해도 안전하며, 서명자가 누군지를 증명할 수 있다.

서명은 다음 정보들을 증명할 수 있어야 함:

누가 서명했는지 (작성자 인증)

언제 서명했는지 (서명 시점)

서명된 문서의 내용이 서명 시점과 동일한지 확인할 수 있어야 한다.

제3자(예: 법원, 감사인 등)가 서명을 검증 가능해야 함

공개키를 알고 있어도, 심지어 유효한 서명을 봤어도 서명을 위조할 수 없다. (개인 키가 없으니)

단계 송신자 수신자
🔑 키 사용 개인키 (sign) 공개키 (verify)
🔐 서명 생성 Sign(private_key, H(m)) Verify(public_key, signature, H(m))
🛡️ 보장 무결성 + 인증 + 부인 방지
🤝 키 공유 필요? ❌ (비밀 키 공유 안 함)

Hash vs MAC vs Digital Signature

구분 Hash MAC (Message Authentication Code) Digital Signature
Data Integrity ✅ Yes ✅ Yes ✅ Yes
Authentication ❌ No ✅ Yes ✅ Yes
Non-repudiation(부인 방지) ❌ No ❌ No ✅ Yes
Key Type ❌ 없음 (비키 기반) 🔐 대칭키 (Symmetric) 🔐 비대칭키 (Asymmetric)

💡 용어정리

Data Integrity: 데이터가 중간에 변조되지 않았음을 확인
Authentication: 메시지의 보낸 사람을 확인할 수 있음
Non-repudiation (부인 방지): 나중에 "내가 안 보냈다"라고 부인할 수 없음
Key Type:

❌ Hash는 키가 필요 없음

🔐 MAC은 송신자와 수신자가 같은 비밀 키 공유 (대칭키)

🔐 Digital Signature는 개인키로 서명, 공개키로 검증 (비대칭키)

단계	송신자	수신자
🔑 키 사용	개인키 (sign)	공개키 (verify)
🔐 서명 생성	`Sign(private_key, H(m))`	`Verify(public_key, signature, H(m))`
🛡️ 보장	무결성 + 인증 + 부인 방지
🤝 키 공유 필요?	❌ (비밀 키 공유 안 함)

구분	Hash	MAC (Message Authentication Code)	Digital Signature
Data Integrity	✅ Yes	✅ Yes	✅ Yes
Authentication	❌ No	✅ Yes	✅ Yes
Non-repudiation(부인 방지)	❌ No	❌ No	✅ Yes
Key Type	❌ 없음 (비키 기반)	🔐 대칭키 (Symmetric)	🔐 비대칭키 (Asymmetric)

Digital Signature 2

요구 사항 설명
서명 생성 쉬움 송신자가 서명을 빠르게 만들 수 있어야 함
서명 검증 쉬움 수신자가 공개키로 빠르게 검증할 수 있어야 함
위조 불가능 공격자가 서명 없이 메시지를 위조하거나, 메시지 없이 서명을 위조하는 것이 계산적으로 불가능해야 함

Key-only attackc (키-단독 공격)

공격자 C가 오직 A의 공개키만 일고 있는 상황에서 공격 시도.
공개키만으로 서명 위조 시도

Known message attack (알려진 메시지 공격)

공격자 C가 몇 개의 메시지와 그 메시지들에 대한 유효한 서명 쌍(메시지 + 서명)을 알고 있는 경우
C는 실제로 A가 서명한 메시지와 그 서명을 입수하여, 이 정보로부터 서명 알고리즘의 약점을 찾아내거나 다른 메시지에 대한 서명을 위조하려고 시도.

Generic chosen message attack (일반적 선택 메시지 공격)

공격자 C가 먼저 깨뜨리려는 서명 시스템 A의 공개키와 상관없이, 자신이 원하는 메시지 리스트를 먼저 정하고, 그 메시지들에 대해 A로부터 실제 서명을 받아서 서명 데이터를 수집한 후, 이 정보를 가지고 다른 메시지의 서명을 위조하거나 시스템을 공격하려는 경우.
공격자가 임의로 메시지를 골라 서명을 받고, 이 서명들을 바탕으로 서명 체계를 깨려는 더 강력한 공격 유형.

Directed chosen message attack (지정 선택 메시지 공격)

일반적 선택 메시지 공격과 매우 유사하지만, 공격자 C가 A의 공개키를 먼저 알고 난 뒤에 서명을 받을 메시지 리스트를 선택한다는 점과 아직 서명을 받기 전에 메시지를 정한다는 점이 다르다.

Adaptive chosen message attack (적응형 선택 메시지 공격)

공격자 C는 A에게 서명을 요청할 메시지를 점진적으로 선택할 수 있다.
즉, 처음에는 한두 개 메시지의 서명을 받아서, 그 결과를 보고 다음에 어떤 메시지를 요청할지 결정한다.
공격자가 A의 서명에 대해 순차적으로, 적응적으로 메시지를 선택하면서 서명 요청을 한다.
이 방식으로 공격자는 점점 더 유리한 메시지를 골라내며 서명 알고리즘의 약점을 파헤치려고 한다.

공격 종류 공격자가 아는 정보 및 조건 공격 방식 및 특징
Key-only attack A의 공개키만 알고 있음 공개키만으로 서명 위조 시도
Known message attack 몇 개의 메시지와 그 메시지에 대한 서명 쌍을 알고 있음 알려진 메시지-서명 쌍을 이용해 서명 위조나 공격 시도
Generic chosen message attack 공격자가 A의 공개키와 무관하게, 먼저 메시지 리스트를 선택함 선택한 메시지들에 대해 A로부터 서명을 받고, 이를 분석해 공격 시도
Directed chosen message attack A의 공개키를 먼저 알고, 그 후 서명을 요청할 메시지 리스트를 선택함 공개키를 참고해 메시지 리스트를 정하고 서명을 요청하여 공격 시도
Adaptive chosen message attack A의 공개키를 알고 있고, 이전에 받은 메시지-서명 쌍을 참고해 메시지를 점진적으로 선택함 이전 서명 결과를 바탕으로 다음 메시지를 정해 서명을 요청하며 점진적으로 공격 시도

요구 사항	설명
서명 생성 쉬움	송신자가 서명을 빠르게 만들 수 있어야 함
서명 검증 쉬움	수신자가 공개키로 빠르게 검증할 수 있어야 함
위조 불가능	공격자가 서명 없이 메시지를 위조하거나, 메시지 없이 서명을 위조하는 것이 계산적으로 불가능해야 함

공격 종류	공격자가 아는 정보 및 조건	공격 방식 및 특징
Key-only attack	A의 공개키만 알고 있음	공개키만으로 서명 위조 시도
Known message attack	몇 개의 메시지와 그 메시지에 대한 서명 쌍을 알고 있음	알려진 메시지-서명 쌍을 이용해 서명 위조나 공격 시도
Generic chosen message attack	공격자가 A의 공개키와 무관하게, 먼저 메시지 리스트를 선택함	선택한 메시지들에 대해 A로부터 서명을 받고, 이를 분석해 공격 시도
Directed chosen message attack	A의 공개키를 먼저 알고, 그 후 서명을 요청할 메시지 리스트를 선택함	공개키를 참고해 메시지 리스트를 정하고 서명을 요청하여 공격 시도
Adaptive chosen message attack	A의 공개키를 알고 있고, 이전에 받은 메시지-서명 쌍을 참고해 메시지를 점진적으로 선택함	이전 서명 결과를 바탕으로 다음 메시지를 정해 서명을 요청하며 점진적으로 공격 시도

Digital Signature Forgeries(위조)

Total break (완전 붕괴)

공격자 C가 A의 개인키를 완전히 알아내는 상황

Universal forgery (범용 위조)

C가 서명을 만드는 새로운 알고리즘이나 방법을 찾아서, 아무 메시지에 대해서도 올바른 서명을 만들 수 있는 상황.

Selective forgery (선택적 위조)

C가 자신이 원하는 특정 메시지 하나에 대해 서명을 위조하는 경우

Existential forgery (존재적 위조)

C가 적어도 하나의 메시지에 대해 서명을 위조하는 데 성공했지만, 그 메시지를 직접 선택하지 못한 경우.

위조 종류 특징 공격자의 메시지 선택 권한 결과
Total break A의 개인키를 완전히 알아냄 - 모든 메시지 서명 자유롭게 위조 가능
Universal forgery 임의 메시지에 대해 효율적인 서명 생성 방법을 찾음 - 모든 메시지에 대해 서명 위조 가능
Selective forgery 공격자가 특정 메시지를 정해 그 메시지에 대해 서명 위조 있음 특정 메시지에 대해 위조 서명 생성 가능
Existential forgery 적어도 하나의 위조 서명 생성 성공, 메시지는 공격자가 선택하지 못함 없음 어떤 메시지에 대해 위조 서명 생성 가능

위조 종류	특징	공격자의 메시지 선택 권한	결과
Total break	A의 개인키를 완전히 알아냄	-	모든 메시지 서명 자유롭게 위조 가능
Universal forgery	임의 메시지에 대해 효율적인 서명 생성 방법을 찾음	-	모든 메시지에 대해 서명 위조 가능
Selective forgery	공격자가 특정 메시지를 정해 그 메시지에 대해 서명 위조	있음	특정 메시지에 대해 위조 서명 생성 가능
Existential forgery	적어도 하나의 위조 서명 생성 성공, 메시지는 공격자가 선택하지 못함	없음	어떤 메시지에 대해 위조 서명 생성 가능

RSA signature

공개키 (pk) : (e, n)
개인키 (sk) : (d, n)
n = p x q (두 개의 큰 소수의 곱)
e = 공개 지수
d = 개인 지수 (e의 모듈러 역원)
s = 시그니처

Existential Forgery with Key-Only Attack

공격자 C는 A의 공개키 (e,n)만 알고 있음.
목표: 유효한 (m, s) 서명 쌍을 위조. (메시지를 마음대로 고를 수 없음 — Existential forgery)
1. 무작위로 s를 하나 선택.
2. 𝑚 = 𝑠^𝑒(𝑚𝑜𝑑 𝑛)
3. 이제 (m, s) 쌍이 생겼고, 검증 절차에서:
𝑉𝑒𝑟 𝑝𝑘 𝑠 → 𝑚′ ≡ 𝑠^𝑒 𝑚𝑜𝑑 𝑛
𝑚 =? 𝑚′
-> 검증 통과

이것이 바로 Existential Forgery (존재 위조):
"의미 없는 메시지라도, 검증 가능한 위조를 만들어냈다!"

항목 설명
s 공격자가 임의로 고른 서명값 (정수)
m = s^e mod n 이 서명값이 유효하다고 보이는 메시지
메시지 m 대부분의 경우 사람이 이해할 수 없는 의미 없는 숫자
목적 단 한 개라도 유효한 (m, s) 쌍을 만드는 것. (메시지가 의미 있는지 여부는 상관 없음)

Existential Forgery with Known Message Attack

공격자는 (m1,s1)와 (m2,s2)라는 두 개의 유효한 서명 쌍을 알고 있음.
s₁ ≡ m₁^d mod n
s₂ ≡ m₂^d mod n
개인키 d는 모름

공격 방법:
새로운 메시지 m3를 만듬
s3 = s₁ × s₂ ≡ m₁^d × m₂^d ≡ (m₁ × m₂)^d mod n

새로운 메시지: m₃ = m₁ × m₂ mod n
새로운 서명: s₃ = s₁ × s₂ mod n
검증: s₃^e mod n = (s₁ × s₂)^e = m₁ × m₂

✅ 결론: 이전에 알고 있던 서명을 조합해 새로운 유효한 서명 쌍을 생성함
→ Existential forgery 성공!

공격 종류 공격자가 아는 것 위조 방식 위조된 메시지 선택 가능 여부
Existential forgery with key-only 공개키 (N, e) 무작위 서명 s 선택 → m = s^e mod n 계산 ❌ (무작위 메시지)
Existential forgery with known message 공개키 + 유효한 서명 쌍 2개 s₃ = s₁ × s₂ mod n 계산 → 메시지 m₃ = m₁ × m₂ mod n ❌ (결과로 생긴 메시지)

항목	설명
`s`	공격자가 임의로 고른 서명값 (정수)
`m = s^e mod n`	이 서명값이 유효하다고 보이는 메시지
메시지 m	대부분의 경우 사람이 이해할 수 없는 의미 없는 숫자
목적	단 한 개라도 유효한 (m, s) 쌍을 만드는 것. (메시지가 의미 있는지 여부는 상관 없음)

공격 종류	공격자가 아는 것	위조 방식	위조된 메시지 선택 가능 여부
Existential forgery with key-only	공개키 (N, e)	무작위 서명 `s` 선택 → `m = s^e mod n` 계산	❌ (무작위 메시지)
Existential forgery with known message	공개키 + 유효한 서명 쌍 2개	`s₃ = s₁ × s₂ mod n` 계산 → 메시지 `m₃ = m₁ × m₂ mod n`	❌ (결과로 생긴 메시지)

RSA Signature with Hash Function

해시를 사용하여 앞 두 공격에 대해 안전성을 보장할 수 있음.
항상 같은 길이가 나옴으로 연산 오버헤드 부분에서도 이점이 있음.
message m이 오면 우선 hash 씌움 -> S가 됨.

RSA Signature with Hash Function

Existential Forgery with Key-Only Attack

공격 절차:
1. 공격자는 공개키 (n,e)만 앎
2. 임의의 숫자 s를 서명값이라고 가정
3. m' = s^e mod n -> 이걸 위조된 해시값이라 생각
4. 이 해시값이 어떤 메시지의 해시값 즉 h(m)이 되는지 찾아야됨. 즉 우린 m값이 궁금한거임.
m' = s^e mod n 이 실제로 어떤 메시지 m의 해시값이 되려면 해시 함수의 preimage resistance(역상 저항성)을 깨야 함.

h(m) = m' => m을 찾는게 매우 어렵다.

Existential Forgery with Known Message Attack (메시지-서명 쌍 2개를 알고 위조)

두 개의 메시지 m1, m2와 서명값 s1,s2를 알고 있음.
각각:

h(m1) x h(m2)이 실제 어떤 메시지 m3의 해시값일까?
아닐거다. preimage resistance 문제.

공격 종류 설명 왜 실패함?
Key-only 공격 무작위 $s$ 로 $m = s^e \mod n$ 계산 → 위조된 해시값 $m$ 을 찾기 위해 해시 함수의 역상을 구해야 함 → 어려움
Known-message 공격 $s_1, s_2$ 를 곱해서 새로운 서명 만듦 $h(m_1) \cdot h(m_2)$ 이 실제 어떤 메시지의 해시인지 알아야 함 → 역시 어렵다

공격 종류	설명	왜 실패함?
Key-only 공격	무작위 $s$ 로 $m = s^e \mod n$ 계산 → 위조된 해시값	$m$ 을 찾기 위해 해시 함수의 역상을 구해야 함 → 어려움
Known-message 공격	$s_1, s_2$ 를 곱해서 새로운 서명 만듦	$h(m_1) \cdot h(m_2)$ 이 실제 어떤 메시지의 해시인지 알아야 함 → 역시 어렵다

Digital Signature Algorithm (DSA)

DLP에서의 안전성을 가지고 있음.
키 생성:

공개 파라미터:

p: 약 1024비트 크기의 큰 소수

q: 약 160비트 크기의 소수, q | (p-1)

g: an element of 𝑍𝑝∗ of order 𝑞

개인키:

x: 비밀 키(1 <= x <= q-1)

공개키:

y = g^x mod p

감마 γ=(g^k mod p)mod q
: 앞 단계에서 계산한 서명 값
델타 δ=(h(m)+x⋅γ)⋅k^−1 mod q

항목 설명
$p, q, g$ 공개 파라미터
$x$ 비밀 키
$y = g^x \mod p$ 공개 키
서명 $\gamma = (g^k \mod p) \mod q$ , $\delta = (h(m) + x\gamma) \cdot k^{-1} \mod q$
검증 $v = (g^{e_1} \cdot y^{e_2} \mod p) \mod q$ , $v =? \gamma$

항목	설명
$p, q, g$	공개 파라미터
$x$	비밀 키
$y = g^x \mod p$	공개 키
서명	$\gamma = (g^k \mod p) \mod q$ , $\delta = (h(m) + x\gamma) \cdot k^{-1} \mod q$
검증	$v = (g^{e_1} \cdot y^{e_2} \mod p) \mod q$ , $v =? \gamma$

Elliptic Curve Digital Signature Algorithm (ECDSA)

Elliptic Curve에서의 DLP문제는 generator
G가 주어졌을 때 G를 몇번 더했는지가 비밀값 (base point)
d: 비밀키
Q: 공개키 - G를 비밀키(d) 만큼 더한 값이다.
이때 d값을 구하기가 어려운게 ECDLP문제에 기반.

서명과정:
1. 무작위 정수 k 선택 (1 <= k <= n)
2. 점 kG = (x1, y1) 계산
3. γ = x1 mod n
-> 이게 서명의 첫 번째 절반
-> 만약 γ = 0이면 다시 처음부터
4. δ = k^-1(h(m) + dA * γ) mod n
-> 서명의 두 번째 절반
-> h(m)은 메시지 해시값
5. 결과: 서명 쌍(γ, δ)

검증과정:
1. 유효성 확인:

γ, δ가 (0 <= γ, δ <n)인지 확인

해시 계산:

h(m)

w = δ^-1 mod n

중간 값 계산:

u1 = h(m) x w mod n
u2 = γ x w mod n

점 계산 :

(x1', y1') = u1G+u2QA

검증:

𝛾 ≡ 𝑥1′ (𝑚𝑜𝑑 𝑛) 같다면 서명 유효

단계 설명
서명자 키 개인키 $d_A$ , 공개키 $Q_A = d_A G$
서명 값 $\gamma = x_1 \mod n$ , $\delta = k^{-1}(h(m) + d_A \cdot \gamma) \mod n$
검증 값 $\gamma \stackrel{?}{=} x_1' \mod n$ , $x_1'$ 는 $u_1G + u_2Q_A$ 에서 유도

단계	설명
서명자 키	개인키 $d_A$ , 공개키 $Q_A = d_A G$
서명 값	$\gamma = x_1 \mod n$ , $\delta = k^{-1}(h(m) + d_A \cdot \gamma) \mod n$
검증 값	$\gamma \stackrel{?}{=} x_1' \mod n$ , $x_1'$ 는 $u_1G + u_2Q_A$ 에서 유도

Certificate Chain

여기서 SK는 CA의 SK이고 PK또한 CA의 PK이다.
신뢰할 수 있는 root 인증서를 관리하는 리스트(Trust Anchor) 안에 들어 있어야만 신뢰함.

naver라는 웹사이트를 신뢰하는게 아닌 naver라는 웹 사이트가 발급받은 인증서의 체인에 연결되어있는 마지막 root CA를 신뢰하는 것이다.

8. Hash_Digital_Signature

컴퓨터 보안

Hash Function

무결성 체크

Message Authentication Code (MAC)

Digital Signature

Preimage

Collision

Requirements and Security

Collision Resistant Attacks

생일 역설 (Birthday Paradox)

Merkle-Damgård

SHA

SHA-1

SHA-2

SHA-3

HMAC

MAC(Message Authentication Code)

HMAC (Hash-based MAC)

Digital Signature 1

Hash vs MAC vs Digital Signature

💡 용어정리

Digital Signature 2

Key-only attackc (키-단독 공격)

Known message attack (알려진 메시지 공격)

Generic chosen message attack (일반적 선택 메시지 공격)

Directed chosen message attack (지정 선택 메시지 공격)

Adaptive chosen message attack (적응형 선택 메시지 공격)

Digital Signature Forgeries(위조)

Total break (완전 붕괴)

Universal forgery (범용 위조)

Selective forgery (선택적 위조)

Existential forgery (존재적 위조)

RSA signature

Existential Forgery with Key-Only Attack

Existential Forgery with Known Message Attack

RSA Signature with Hash Function

RSA Signature with Hash Function

Existential Forgery with Key-Only Attack

Existential Forgery with Known Message Attack (메시지-서명 쌍 2개를 알고 위조)

Digital Signature Algorithm (DSA)

Elliptic Curve Digital Signature Algorithm (ECDSA)

Certificate Chain

7. Public Key Cryptography

9. TLS_Protocol

0개의 댓글