프래피티 STUDY - 다이나믹 배열, 해시 함수 속성 및 유형

프래피티 STUDY

Dynamic array drawbacks (다이나믹 배열의 단점)

• 장점인 배열의 길이 변경이 가능하다는 점
• 반면에 그 장점을 구현하기 위해서 배열 삭제, 추가, 복제 등이 일어나면서 이 것을 진행하는 동안 리소스, 과정, 연산, 시간 등이 소요되기 때문에 단점 등이 발생

Hash function properties and types (해시 함수 속성 및 유형)

• 해시 함수의 주요 특성
  1. 결정성(Deterministic): 동일한 입력에 대해 항상 동일한 출력(해시 값)을 반환해야 합니다.
  2. 빠른 연산 속도: 데이터의 크기와 상관없이 해시 값을 빠르게 계산할 수 있어야 합니다.
  3. 일정한 해시 값 길이: 해시 함수는 다양한 길이의 입력에 대해 항상 일정한 길이의 출력을 반환해야 합니다.
  4. 높은 확산성: 작은 입력값의 변화도 출력된 해시 값에 큰 변화를 가져와야 합니다.
  5. 충돌 최소화: 두 개 이상의 다른 입력값이 동일한 해시 값을 반환하는 경우를 "충돌"이라고 합니다. 좋은 해시 함수는 이러한 충돌을 최소화 해야 합니다.
• 해시 함수의 주요 유형
  1. 일반 해시 함수: 데이터 구조에서 효율적인 데이터 검색, 삽입, 삭제를 위해 사용됩니다. 예로 해시 테이블에서 주로 사용됩니다.
• 일반 해시 함수의 주요 특성:
  1. 고정된 출력 길이: 일반적으로 해시 테이블의 크기에 따라 해시 함수는 고정된 길이의 출력값을 반환합니다.
  2. 빠른 연산: 일반 해시 함수는 빠른 시간 내에 해시 값을 계산할 수 있어야 합니다.
  3. 분포: 좋은 해시 함수는 입력값을 균일하게 분포시켜야 합니다. 이렇게 해야 해시 테이블에서의 충돌이 최소화됩니다.
• 일반 해시 함수의 예:
  1. 나눗셈(Division) 메서드: 입력값을 특정 숫자로 나눈 나머지를 해시 값으로 사용합니다. h(k)=kmodm 여기서 m은 해시 테이블의 크기입니다.
  2. ℎ(�)=�mod  �
  3. 곱셈(Multiplication) 메서드: 입력값에 특정 상수를 곱하고, 그 결과의 소수 부분과 해시 테이블의 크기를 곱해서 해시 값을 얻습니다.
  4. 중간 제곱(Mid-Square) 메서드: 입력값을 제곱한 후, 중간의 몇 자리를 해시 값으로 사용합니다.
• 암호 해시 함수(Cryptographic Hash Function): 보안 관련 애플리케이션에서 사용되며, 특정 속성(역산 어려움, 충돌 저항성 등)이 있어야 합니다. 예로 MD5, SHA-256 등이 있습니다.
  • 암호 해시 함수의 주요 속성:
    1. 역산 어려움(Pre-image resistance): 주어진 해시 값 h(y)에 대해 원래의 입력 y를 찾는 것이 계산상 불가능해야 합니다.
    2. 제2 역상 어려움(Second pre-image resistance): 주어진 입력 x에 대해 같은 해시 값을 가지는 다른 입력 y를 찾는 것이 계산상 불가능해야 합니다.
    3. 충돌 저항성(Collision resistance): 두 개의 다른 입력 x와 y가 동일한 해시 값을 가질 확률이 매우 낮아야 합니다.
    4. 높은 확산성(Avalanche effect): 입력 데이터의 아주 작은 변경이 해시 값에 큰 변화를 가져와야 합니다.
  • 암호 해시 함수의 예:
    1. MD5 (Message-Digest Algorithm 5): 과거에 널리 사용되었지만, 현재는 취약점이 발견되어 보안 목적으로는 권장되지 않습니다.
    2. SHA-1 (Secure Hash Algorithm 1): 또한 취약점이 발견되어 현재는 보안 애플리케이션에서의 사용이 권장되지 않습니다.
    3. SHA-256: SHA-2 패밀리에 속하며, 현재 널리 사용되는 암호 해시 함수 중 하나입니다.

암호 함수들 중에서 해시 함수가 쓰이는 이유

• 데이터 무결성 확인: 해시 함수는 데이터가 변경되었는지 확인하기 위해 사용됩니다. 변경이 없으면 동일한 해시 값을 생성하므로, 데이터의 무결성을 보장할 수 있습니다.
• 비밀번호 저장: 사용자의 비밀번호를 직접 저장하는 대신 비밀번호의 해시 값을 저장하여 보안을 강화할 수 있습니다.
• 데이터 구조 최적화: 해시 테이블 같은 데이터 구조에서 빠른 검색 속도를 제공합니다.
• 디지털 서명: 해시 함수는 디지털 서명의 작성 및 검증 과정에서 중요한 역할을 합니다.

여러 암호화 방식 중에 해시 함수(암호 해시 함수)가 선택되는 이유(내 생각)

• 완벽한 암호화 방식은 아니지만 사용가능한 수준으로 암호화 방법이 비교적 간단해 연산속도가 빠르다

1. AES (Advanced Encryption Standard)

• 유형: 대칭키 암호화 방식
• 특징:
  • Rijndael 암호화 방식에 기반하여 개발되었습니다.
  • 128비트 블록 크기를 가지며, 키 길이는 128, 192, 256비트 중 선택할 수 있습니다.
  • 키와 함께 데이터를 암호화하고 복호화합니다.
  • 블록 암호화 방식으로, 데이터를 블록 단위로 나누어 암호화하고 복호화합니다.
• 사용 사례: HTTPS, 파일 암호화, Wi-Fi 보안 등 다양한 분야에서 사용됩니다.

2. RSA (Rivest–Shamir–Adleman)

• 유형: 비대칭키 암호화 방식
• 특징:
  • 두 개의 키 (공개 키와 개인 키)를 사용합니다.
  • 공개 키로 암호화한 데이터는 개인 키로만 복호화할 수 있으며, 개인 키로 암호화한 데이터는 공개 키로만 복호화할 수 있습니다.
  • 주로 디지털 서명 및 키 교환에 사용됩니다.
  • 큰 수의 소인수 분해 문제의 어려움에 기반하여 보안성이 확보됩니다.
• 사용 사례: SSL/TLS, 이메일 보안, 디지털 서명 등 다양한 온라인 보안 프로토콜과 시스템에서 사용됩니다.

SHA-256 (Secure Hash Algorithm 256-bit)

1. 정의:
   • SHA-256은 SHA-2 (Secure Hash Algorithm 2) 패밀리의 일원으로, 메시지를 받아 고정 길이의 256비트 (32바이트) 해시 값을 생성하는 암호해시 함수입니다.
2. 작동 원리:
   • 메시지 전처리: 주어진 입력 메시지는 512비트 블록으로 나누어집니다. 이를 위해 메시지에 패딩이 추가되어, 전체 길이가 512의 배수가 되게 합니다.
   • 메시지 스케줄: 각 512비트 블록은 64개의 32비트 워드로 나누어져, 이 워드들은 특정한 연산을 통해 확장됩니다.
   • 메인 루프: 확장된 워드들은 초기 해시 값과 함께 64번의 라운드를 거칩니다. 각 라운드에서는 논리 연산, 비트 시프트, 모듈러 덧셈 등의 연산이 수행됩니다.
   • 결과 생성: 마지막 라운드 후, 중간 해시 값이 최종 해시 값에 더해져, 256비트 길이의 최종 해시 출력이 생성됩니다.
3. 보안 특성:
   • 역산 어려움 (사전 이미지 저항성): 주어진 해시 출력값 h에 대응하는 입력 값을 찾는 것은 계산적으로 어렵습니다.
   • 제2 역상 어려움 (제2 사전 이미지 저항성): 특정 입력 값에 대한 해시 값을 알고 있을 때, 해당 해시 값과 동일한 다른 입력 값을 찾는 것은 계산적으로 어렵습니다.
   • 충돌 저항성: 두 개의 다른 입력 값에 대해 동일한 해시 값을 생성하는 것은 계산적으로 어렵습니다.
4. 사용 사례:
   • 데이터 무결성 검증: SHA-256 해시는 파일의 무결성을 확인하는 데 사용될 수 있습니다. 파일의 내용이 변경되지 않았는지 확인하기 위해, 원래의 해시 값과 비교할 수 있습니다.
   • 디지털 서명: 비밀키를 사용하여 생성된 해시 값은, 메시지와 함께 전송되어 수신자가 메시지의 무결성과 발신자의 정체성을 검증할 수 있게 해줍니다.
   • 암호화 화폐: SHA-256은 비트코인 블록체인에서의 작업 증명 (Proof of Work) 알고리즘으로 사용됩니다.
5. 성능:
   • SHA-256의 연산 속도는 해당 알고리즘을 실행하는 하드웨어나 소프트웨어 구현 방법에 따라 다를 수 있습니다. 최적화된 하드웨어 구현은 고성능의 암호 연산을 제공할 수 있으며, 클라우드 환경에서는 병렬 처리 능력을 활용해 높은 처리량을 달성할 수 있습니다.
6. 하드웨어 및 소프트웨어 구현:
   • SHA-256은 ASIC, FPGA와 같은 특수한 하드웨어에서 구현될 수 있습니다. 이런 하드웨어 구현은 암호화 화폐 채굴 같은 특정 응용에서 요구되는 고성능 연산을 위해 사용됩니다.
   • 소프트웨어 구현의 경우, 다양한 프로그래밍 언어와 라이브러리를 통해 제공됩니다. 표준 라이브러리를 사용함으로써 개발자는 안정적이고 검증된 코드의 장점을 활용할 수 있습니다.
7. 약점 및 대응책:
   • 현재까지는 SHA-256의 기본 구조에 대한 중대한 취약점은 발견되지 않았습니다. 그러나 해시 함수의 보안 특성을 유지하기 위해서는 정기적인 검토와 연구가 필요합니다.
   • 일반적으로, 길이 확장 공격 같은 일부 약점을 방지하기 위해 HMAC와 같은 메시지 인증 코드 구조에서 해시 함수를 사용하는 것이 권장됩니다.
8. 미래:
   • SHA-3이라는 새로운 해시 알고리즘이 NIST에 의해 2015년에 표준화되었습니다. SHA-3는 SHA-2와는 다른 내부 구조를 가지며, 미래의 잠재적인 위협에 대비하는 추가적인 선택지를 제공합니다.
   • 그러나 현재까지 SHA-256은 널리 인정받고 있으며, 많은 시스템과 애플리케이션에서 여전히 주요 해시 함수로서 사용되고 있습니다.
9. 결론:
   • SHA-256은 암호학적으로 안전하고 성능이 우수한 해시 함수로 널리 알려져 있습니다. 이 알고리즘은 다양한 응용 분야에서 데이터의 무결성 및 인증을 보장하는데 필수적입니다. 끊임없는 연구와 기술 발전에 따라 SHA-256의 위치는 변할 수 있으나, 현재로서는 그 중요성과 가치가 계속 유지되고 있습니다.

암호 해시 함수의 보안성 강화 방법

1. 키화된 해시 함수 (HMAC, Keyed-Hash Message Authentication Code):
   • HMAC은 해시 함수의 보안성을 강화하기 위해 설계된 암호 기술입니다. 시크릿 키를 사용하여 해시 함수의 출력을 변형함으로써, 일반적인 해시 함수의 취약점을 완화할 수 있습니다.
2. 솔트 (Salt) 사용:
   • 패스워드와 같은 입력 값에 임의의 값을 추가하여 해시 입력을 변형하는 방법입니다. 이는 동일한 입력에 대한 해시 값의 예측을 어렵게 만듭니다.
3. 이터레이션 (Iteration):
   • 해시 함수를 여러 번 반복적으로 적용하여 결과를 도출하는 방법입니다. 이로 인해 해시 함수의 연산을 복잡하게 만들어, 브루트포스 공격에 대한 저항성을 향상시킬 수 있습니다.
4. 머클 댐가드 구조 (Merkle–Damgård Construction):
   • 이 구조는 해시 함수의 길이 확장 공격에 대한 저항성을 제공합니다. 대부분의 암호 해시 함수들, 예를 들면 SHA-2,는 이 구조를 사용합니다.
5. 해시 함수 체이닝:
   • 여러 다른 해시 함수를 연속적으로 적용하여 결과를 도출하는 방법입니다. 이를 통해 한 해시 함수의 취약점이 보안에 큰 영향을 주는 것을 방지할 수 있습니다.

SHA-3에 대한 설명

• SHA-3은 NIST (미국 국립 표준 기술 연구소)에 의해 2015년에 표준화된 최신 해시 함수입니다. SHA-3는 Keccak 알고리즘을 기반으로 하며, SHA-2와는 다른 설계 구조를 가지고 있습니다.
• 디자인: SHA-3는 스폰지 구조 (sponge construction)를 사용하며, 이는 입력을 받아들이고 (absorbing phase) 그 후 결과를 출력 (squeezing phase)하는 방식으로 작동합니다.
• 보안성: SHA-3는 현재까지 알려진 공격에 대해 매우 견고한 것으로 판명되었습니다. 이는 Keccak 알고리즘의 유연한 디자인 덕분입니다.
• 성능: SHA-3은 다양한 플랫폼에서 효율적으로 구현될 수 있습니다. 하드웨어 구현에서 특히 뛰어난 성능을 보여줍니다.
• 영역: SHA-3는 SHA-2와 동일한 해시 길이를 제공합니다 (예: 224, 256, 384, 512비트).
• 추가적인 특징: SHA-3은 해시 함수 외에도 다양한 암호 기술, 예를 들면, 스트림 암호, 블록 암호, 랜덤 난수 생성 등을 지원하기 위한 기능을 추가적으로 제공합니다.
• 종합적으로, SHA-3은 현대 암호학의 최신 연구 결과를 바탕으로 설계되었으며, 다양한 보안 요구사항과 성능 특성을 만족하는 현대적인 해시 함수입니다.

머클 댐가드 구조 (Merkle-Damgård 구조)

1. 정의

• 머클 댐가드 구조는 암호 해시 함수를 설계하는 방법 중 하나로, 다양한 길이의 입력을 고정된 길이의 출력으로 변환하는데 사용됩니다. 머클 트리의 개념과는 별개로, 머클 댐가드 구조는 암호 해시 함수의 블록 연산 방식을 정의합니다.

2. 작동 원리

• 입력 분할: 주어진 입력 메시지는 고정된 길이의 블록들로 분할됩니다.
• 패딩: 마지막 블록이 고정된 길이보다 짧을 경우 패딩을 추가하여 블록 길이를 맞춥니다.
• 초기 해시 값 설정: 일반적으로 특정 고정 값으로 시작합니다.
• 순차적 해싱: 각 블록은 이전 블록의 해시 값과 결합되어 순차적으로 해시됩니다.

3. 특징:

• 강한 충돌 저항성: 머클 댐가드 구조를 사용하는 해시 함수는 임의의 두 메시지에 대해 동일한 해시 값을 생성하는 것이 매우 어렵습니다.
• 데이터 무결성: 작은 변경도 해시 값에 큰 변화를 일으킵니다.

Merkle-Damgård 구조의 기원:

• 'Merkle-Damgård'는 이 구조를 처음 제안한 두 연구자의 성을 따서 명명된 것입니다. 그 두 연구자는 Ralph Merkle과 Ivan Damgård입니다. 따라서, 'Merkle-Damgård'는 사람 이름에서 유래한 용어입니다.
• ‘댐가드’ 라고 하길래 먼가 싶었는데 사람 이름이라고 한다….

해시 함수 체이닝 (Hash Function Chaining)

1. 정의:

• 해시 함수 체이닝은 여러 해시 함수를 연속적으로 적용하는 기법입니다. 이 방식은 보안 강도를 높이기 위해 사용될 수 있습니다.

2. 작동 원리:

1. 초기 입력: 원하는 데이터를 초기 입력으로 사용합니다.
2. 체이닝 시작: 초기 입력에 해시 함수를 적용하여 첫 번째 해시 값을 생성합니다.
3. 계속적인 체이닝: 첫 번째 해시 값에 다시 해시 함수를 적용하여 두 번째 해시 값을 생성합니다. 이 과정을 원하는 횟수만큼 반복합니다.

3. 특징:

• 보안 강화: 단일 해시 함수를 사용할 때보다 체이닝을 사용하면 보안 강도가 높아질 수 있습니다.
• 성능 저하: 연속적인 해싱은 연산 시간을 증가시킬 수 있습니다.

4. 결론:

• 머클 댐가드 구조와 해시 함수 체이닝은 각각 다른 목적으로 설계된 기술입니다. 머클 댐가드는 다양한 길이의 입력을 안전하게 고정된 길이의 출력으로 변환하는 데 초점을 맞추고 있으며, 해시 함수 체이닝은 보안 강도를 높이기 위해 사용됩니다.

SHA-3와 스폰지 구조 (Sponge Construction)

1. 스폰지 구조의 개요:

• 스폰지 구조는 암호 해시 함수와 관련된 블록 실현 구조 중 하나입니다. 이 구조는 "흡수(absorbing)" 단계와 "압출(squeezing)" 단계로 이루어져 있으며, 이 두 단계는 스폰지가 물을 흡수하고 짜내는 원리를 모방한 것입니다.

2. 작동 원리:

1. 흡수 단계 (Absorbing Phase):
   • 입력 메시지는 고정된 길이의 블록으로 나누어집니다.
   • 각 블록은 내부 상태와 XOR 연산됩니다.
   • 이후, 내부 상태는 전환 함수(permutation function)를 통해 변환됩니다.
   • 이 과정은 모든 입력 블록에 대해 반복됩니다.
2. 압출 단계 (Squeezing Phase):
   • 압출 단계에서는 원하는 길이의 해시 출력을 얻을 때까지 내부 상태의 일부분이 출력됩니다.
   • 각 출력 후, 내부 상태는 다시 전환 함수를 통해 변환됩니다.

3. 특징:

• 유연성: 스폰지 구조는 다양한 출력 길이의 해시 값을 생성하는 데 사용될 수 있습니다.
• 보안: 내부 상태의 모든 부분이 입력과 상호 작용하며, 전환 함수는 내부 상태를 균일하게 섞는 역할을 하기 때문에 높은 보안성을 제공합니다.

4. SHA-3의 사용:

• SHA-3는 NIST (미국 국립 표준 기술 연구소)에 의해 2015년에 표준화되었으며, KECCAK 해시 함수를 기반으로 합니다. 스폰지 구조의 적용으로 SHA-3는 이전 SHA-2 시리즈와는 구조적으로 다르며, 이로 인해 SHA-2에서 알려진 특정 취약성에 대한 내성을 갖게 되었습니다.

5. 결론:

• 스폰지 구조는 그 특성상 매우 유연하며, 이로 인해 SHA-3는 다양한 크기의 해시 출력을 생성할 수 있습니다. 이 구조의 도입으로 SHA-3는 고유한 보안 특성을 갖게 되었고, 현대의 암호 해시 함수 중 하나로 널리 인정받고 있습니다.

내가 이해한 것으론 스폰지 구조는

• 맨 처음은 그냥 읽은 후 변형이겠고 이 변형된 데이터를 삭제 하지 않고 새로운 변환해야 할 데이터가 있으면 이거랑 혼합해서 다시 변형하는 식으로 나름 누적해서 계속 처리해서 암호화 해 나간다는 말인 것 같다.