암호학 3주차

1. 암호학

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

• 좁은 의미: 제삼자로부터 정보를 보호하는 방법에 대한 연구 - 키생성, 암호화, 복호화

- 키 생성: 암호화 및 복호화에 사용할 키를 만드는 과정

- 암호화: 키를 이용해 평문을 암호문으로 변환하는 과정

- 복호화: 송신자가 암호문을 전송하면 수신자가 키를 이용해 암호문을 평문으로 복화화

-> 암호 시스템: 암호화와 복호화로 정보가 전달되는 체계

​

+ 인코딩

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

• 데이터의 기밀성 고려 안 함
• 누구나 디코딩해서 원문을 구할 수 있음
• 압축도 인코딩의 예시

​

---

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

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

: 입력으로 들어온 두 인자가 서로 다를 때, 참을 반환하는 연산

두 입력 값을 2진법으로 표기했을 때, 각 자릿수의 값이 다르면 1, 같으면 0이 출력

 

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

• 임의의 정수를 자기 자신과 XOR 하면 결과값은 0 이다. 왜냐하면 각 자릿수의 값이 다 같기 때문이다.
• 예시

3⊕10=0011(2)⊕1010(2)=1001(2)=9

​

​

• 합동식

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

 

-a와 b를 각각 m으로 나눈 나머지가 같으면 수학적으로 a와 b가 mod m에

대해 합동(congruent)이라고 한다.

​

- 예시

7%10=7이고 17%10=7이다. 7과 17은 정수 10으로 나눴을 때 나머지가 같다.

따라서 7과 17은 mod 10에 대해 합동이다. ( 7≡17(mod 10) )

​

- 합동의 성립

a≡b(mod m) 이라고 가정했을 때

a+x≡b+x(mod m)

a−x≡b−x(mod m)

ax≡bx(mod m)

은 성립한다.

​

하지만 나눗셈에 대해서 a/x ≡ b/x ((modm) 이 성립하지 않는다,

​

- 합동식에서 곱셈의 역원

- 정수 a,m에 대해 a×b≡1(mod m)을 만족하는 b를 mod m에 대한 a의 곱의 역원이라 한다.

- a^{-1}로 표기한다.

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

- 예시: 2X4=8≡1(mod7)이다. mod 7에서 2에 대한 역원은 4이다.

​