[암호학] 배타적 논리합과 합동식

배타적 논리합(XOR; exclusive or)

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

 - 일반적으로 비트 단위로 이뤄진다.

 

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

 

 - 임의의 정수를 자기 자신과 배타적 논리합하면, 결과값은 0이다.

 - 즉, 임의의 정수 x에 대해 x ⊕ x = 0이다.

 

합동식

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

 - 두 정수 a, b를 각각 정수 m으로 나눈 나머지가 같을 때, 수학적으로 a와 b가 mod m에 대해 합동(congruent)이다.

 

 - 예를 들어, 7과 17은 10으로 나눈 나머지가 같으므로, 7과 17은 mod 10에 대해 합동이다.

 - 이를 기호로는 7 ≡ 17(mod 10)로 나타낸다.

 

 - 반대로, 5와 12는 3으로 나눈 나머지가 같으므로, 5와 12는 mod 3에 대해 합동이 아니다.

 - 이를 기호로는 5 ≡ 12(mod 3)로 나타낸다.

 

 - a, b가 mod m에 대해 합동일 경우, a, b 각각에 정수 x를 더하거나 빼거나 곱해도 여전히 합동이다.

 

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

 

합동식에서 곱셈의 역원

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

으로 표기한다.

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

 

 - 예를 들어, 2 × 4 = 8 ≡ 1(mod 7)이므로 mod 7에서 2에 대한 역원은 4이다.

 

마치며

Q1. x ⊕ 10 = 7일 때, x는?

A1. 13

 

Q2. 다음 중 잘못된 식은?

A2. (4)

 

Q3. 드림이는 친구에게 소스 코드를 주고 싶은데 USB의 용량이 부족해서 비밀번호를 걸지 않고 압축한 후 USB에 압축 파일을 담았습니다. 이 파일은 누구나 압축을 해제할 수 있으므로 [     ] 되었다고 볼 수 있습니다.

A3. 인코딩