[Dreamhack] Cryptography Introduction

[Dreamhack] Cryptography Introduction

---

# 암호학

• 좁은 의미에서 제 삼자로부터 정보를 보호하는 방법에 대한 연구이다.
• 핵심 연구 주제: 키 생성(Key Generation), 암호화(Encryption), 복호화(Decryption)
  
  • 키 생성: 암호화 및 복호화에 사용할 키를 만드는 과정이다.
  • 암호화: 키를 이용해 평문(Plaintext)을 암호문(Ciphertext)으로 변환하는 과정이다.
  • 복호화: 송신자가 암호문을 전송하면 수신자는 키를 이용해 암호문을 평문으로 복호화한다.
• 암호 시스템(Cryptosystem): 암호화와 복호화로 정보가 전달되는 체계이다.

💡 암호화와 인코딩

• 인코딩(Encoding): 암호화와 유사하게 데이터를 다른 형태로 변환하는 것이다.
  • 데이터의 기밀성을 고려하지 않으며, 누구나 디코딩하여 원문을 구할 수 있다.
  • 데이터를 숨기기 위해 사용하기 보다는 크기를 줄이거나 컴퓨터가 이해하기 쉬운 형식으로 변형하려고 사용한다.
  • ex) 압축

 

 

# 배타적 논리합

• 배타적 논리합(eXclusive OR, XOR): 입력으로 들어온 두 인자가 서로 다를 때, 참을 변환하는 연산이다.
• 암호학에서 배타적 논리합은 일반적으로 비트 단위로 이루어진다.
• 두 입력 값을 2진법으로 표기했을 때, 각 자릿수의 값이 다르면 1, 같으면 0이 출력된다.
• 임의의 정수를 자기 자신과 배타적 논리합하면 결과 값은 0이다.

• 다음은 배타적 논리합 연산의 예시이다.

 

 

# 합동식

• 합동식은 두 정수 a, b를 각각 정수 m으로 나눴을 때 나머지가 같은지를 판별하는 식이다.
• a와 b 각각을 m으로 나눈 나머지가 같을 때, 수학적으로 a와 b가 mod m에 대해 합동(congruent)이라고 표현한다.
• 예를 들어, 7과 17은 10으로 나눈 나머지가 같기 때문에 7과 17은 mod 10에 대해 합동이며, 기호로는 7 ≡ 17(mod 10) 으로 나타낸다.
• 반대로 12와 5는 3으로 나눈 나머지가 다르므로 12와 5는 mod 3에 대해 합동이 아니며, 기호로는 12 ≡ 5(mod 3)으로 나타낸다.
• a, b가 mod m에 대해 합동일 경우 a, b 각각에 정수 x를 더하거나 빼거나 곱해도 여전히 합동이다,

• 그러나 나눗셈에 대해서는 성립하지 않는다.

• 합동식에서 곱셈의 역원
  • 정수 a, m에 대해 a × b ≡ 1(mod m)을 만족하는 b를 mod m에 대한 a의 곱의 역원이라고 부르며, a^{-1}로 표기한다.
  • 예를 들어 2 × 4 ≡ 1(mod7)이므로 mod 7에서 2에 대한 역원은 4이다.
  • 역원은 a와 m이 서로소일 때에만 존재한다.

 

 

# Quiz