3주차 암호학 정리

1. 커리큘럼 소개

 

 

암호학(Cryptography): 정보를 보호하기 위한 언어학적 및 수학적 방법론을 다루는 학문

(좁은 의미): 제3자로부터 정보를 보호하는 방법에 대한 연구

 

핵심 연구 주제

• 키 생성(Key generation) : 암호화/복호화에 사용할 키를 만드는 과정
• 암호화(Encryption) : 키를 이용해 평문(Plaintext)를 암호문(Ciphertext)로 변환하는 과정
• 복호화(Decryption) : 암호문을 평문으로 변환하는 과정

 

암호화와 복호화로 정보가 전달되는 체계 = 암호 시스템(Cryptosystem)

 

+ 현대에는 암호학의 역할이 확장되어

수신자-송신자 간의 신원 확인, 메시지의 비조작 여부 보증 등의 방법론도 암호학의 분야로 연구되고 있음

 

++ 인코딩(Encoding)

: 암호화와 유사하게 데이터를 다른 형태로 변환하는 것

/ 암호화와는 달리 데이터의 기밀성 고려 x, 누구나 디코딩하여 원문 해독 가능

-> 데이터 은폐보다는 크기 축소나 컴퓨터 친화적인 형식 변형에 사용

ex) 압축

 

---

2. 배타적 논리합과 합동식

 

 

배타적 논리합(eXclusive OR, XOR)

: 입력된 두 인자가 서로 다를 때 참을 반환하는 연산

입력		출력
0	0	0
0	1	1
1	0	1
1	1	0

정수연산에서의 XOR 연산 예시 )

5⊕7 = 101​⊕111 = 010 ​= 2

3⊕10 = 0011⊕1010 = 1001 = 9

 

임의의 정수를 자기 자신과 배타적 논리합하면 (서로 같으므로) 결과값은 0

=> x⊕x = 0

 

 

 

합동식

: 두 정수 a, b를 각각 정수 m으로 나눴을 때 나머지가 같은지를 판별하는 식

a와 b 각각을 m으로 나눈 나머지가 같을 때

수학적으로 a와 b가 mod m에 대해 합동(congruent)이라고 표현함

 

ex) 7과 17은 10으로 나눈 나머지가 같으므로

두 수는 mod 10에 대해 합동

기호 표현 : 7≡17(mod 10)

 

ex2) 12와 5는 3으로 나눈 나머지가 다르므로

12와 5는 mod 3에 대해 합동이 아님

 

a, b가 mod m에 대해 합동일 경우

a, b 각각에 정수 x를 더하거나 빼거나 곱해도 여전히 합동

/ 나눗셈에 대해서는 성립 x

 

 

역원

: 정수 a, m에 대해 a*b≡1(mod m)을 만족하는 b를

(a에 곱해서 m으로 나눴을 때 나머지가 1이 되는 수를)

mod m에 대한 a의 곱의 역원이라고 하고, a^(-1)로 표기한다.

 

ex) 2*4 = 8 ≡ 1 (mod 7) 이므로

모드 7에서 2에 대한 역원은 4이다.

 

* 역원은 a와 m이 서로소일 때만 존재한다.