배타적 논리합

배타적 논리합(排他的論理合, XOR, exclusive or)은 수리 논리학에서 주어진 2개의 명제 가운데 1개만 참일 경우 판단하는 논리 연산이며, 약칭으로 XOR, EOR, EXOR이라고 쓴다. exclusive OR, exclusive NOR, 보통 exclusive의 e나 x를 따와서 EOR 또는 XOR로 표기하는데, 보통 XOR로 많이 사용한다. exclusive는 '배타적'이라는 뜻으로, 우리들은 일상속에서 남을 배척하는 것을 보통 배타적이라고 말한다. X, Y가 0또는 1인 값을 가질 때, X와 Y의 배타적 논리합을 X⊕Y로 표현할 수 있다. X와 Y의 값이 같을 때 X⊕Y=0, 값이 다를 때 X⊕Y=1로 출력된다.

연산자는 ⊻, ⩒ 이다. 혼동이 되지 않을 경우 XOR, xor, ⊕, +, ≠라고도 쓴다. 추가로 컴퓨터 프로그래밍 등에서 응용 수학으로 비트간 배타적 논리합(bitwise exclusive or)을 간단히 배타적 논리합, XOR이라고 부르는 경우가 있다. 연산자는 XOR, xor, ⊕, ^ 등을 사용한다.

특징

배타적 논리합은 논리곱(⋀), 분리(⋁), 부정(¬)을 사용하여

$P$ ⊻ $Q$$=$$(P$ ⋀ ¬$Q)$ ⋁ $($¬$P$ ⋀ $Q)$

$P$ ⊻ $Q$$=$$(P$ ⋁ $Q)$ ⋀ $($¬$P$ ⋁ ¬$Q)$

$P$ ⊻ $Q$$=$$(P$ ⋁  $Q)$ ⋀ ¬$($$P$ ⋀ $Q)$

라고 표현할 수 있다.

2를 몫으로 하는 잉여류체ℤ/$[2]$의 가감산(덧셈과 뺄셈이 같다)은 0을 거짓, 1을 참으로 생각하면 배타적 논리합이 된다.

대체 기호

배타적 분리에 사용되는 기호는 응용 분야마다 다르고 주어진 논의 상황에서 강조되는 속성에 따라 달라진다. 약아 "XOR" 이외에도 표시된다.

• $+$ : 더하기 부호는 수학링과 필드의 모든 일반적인 대수적 속성은 추가하지 않고도 사용할 수 있다는 장점이 있지만, 더하기 기호는 또한 일부 표기 시스템에서 포괄적 분리에 사용된다.
• ⊕ : 이 기호는 수학에서 대수적 구조의 직접전인 합으로도 사용된다.
• ⊻, ⩒ : 포괄적인 분리 기호이다.

진리표

명제 P	명제 Q	P ⊻ Q
1	1	0
1	0	1
0	1	1
0	0	0

• ^(캐럿) : C, C++, C#, 자바, 펄, 루비, PHP, 파이썬과 같은 여러 프로그래밍 언어에서 사용되며, 비트의 XOR 연산자를 나타낸다. 캐럿의 다른 사용과 너무 쉽게 혼동되므로 프로그래밍 컨텍스츠 외부에서 사용되지 않는다.

배타적 논리합 게이트

배타적 논리합(XOR)게이트는 참 입력의 개수가 홀수일 때 참(1/high) 출력을 보내는 디지털 논리 게이트이다. 배타적 논리합을 구현하며 게이트의 입력중 하나만이 오직 참이라면 그 결과는 참이 된다. 즉, XOR 게이트에서 입력 값이 A가 Low이고 입력 값이 B가 High이거나 또는 입력 값이 A가 High이고 입력 값이 B가 Low일 때 출력은 High가 되며, A와 B가 모두 High이거나 Low이면 출력은 Low가 된다. XOR 게이트의 기호는 두 가지로 전통적인 기호와 IEEE 기호가 있다.

배타적 논리합 게이트

전통적인 XOR 기호

IEEE XOR 기호

비트간 배타적 논리합

비트간 배타적 논리합은 이진법으로 표현한 수의 각 비트에 대한 2진 집합체 ℤ/$[2]$에 가감산의 결과를 비트간 배타적 논리합, 배타적 비트화라고 하며 단순하게 배타적 논리합이라고도 한다. 비트간 배타적 논리합은 이진 유한체 $GF(2^{n}),n$ ∈ ℕ로 가감산이 동일하다. 추가로 ℤ/$[2]$는 이진 유한체 $GF(2)$이다.

0(거짓)과 1(참)에 대한 배타적 논리합과 비트간 배타적 논리합은 같다. 하지만 0과 1이외 다른 형태의 데이터가 있는 환경에서는 다른 형태의 데이터와 백타적 논리합이 되어 결과적으로는 비트간 배타적 논리합과 다른 결과가 나오므로 주의해야 한다. 비트간 배타적 논리합은 비트 연산에서 특정 비트를 반전시키는 데 사용된다. 어느 수에서 반전을 하고 싶은 부분의 비트를 1로 채워진 수와 배타적 논리합을 하면 지정된 부분이 반전된 수를 얻을 수 있다.

$0011$(₂) ⊕ $0110$(₂) $=0101$(₂)

비트간 배타적 논리합으로 다수의 입력에 대한 오류 짝수 홀수 패리티를 계산하여 오류 검출에 사용된다. 이 목적으로 배타적 논리합 게이트를 트리 구조로 접속된 회로를 패리티 트리라고 한다.

암호 키

비트칸 배타적 논리합은 특정 비트의 반전이므로, 2회 반복하면 원래대로 된다.

$(P$ ⊕ $K)$ ⊕ $K=P$

이를 이용하여, $K$의 키를 사용하여 암호화할 수 있다. $P$를 암호화하면 $P$ ⊕ $K$가 된다. 위의 예시로 $0011$(₂)는 키 $0110$(₂)를 이용하여 $0101$(₂)로 암호화된다.

$0110$(₂) ⊕ $0110$(₂) $=0011$(₂)

으로 키를 이용하여 암호를 복원할 수 있다. 단지 이것만으로 쉽게 풀려버리기 때문에 실제 암호화에는 다른 여러 가지 연산을 같이 사용한다.

참고자료

• 〈Exclusive or〉, 《위키피디아》
• 〈배타적 논리합〉, 《위키백과》
• 〈XOR 게이트〉, 《위키백과》
• thrillfighter, 〈배타적 OR(XOR), 배타적 NOR(XNOR) 게이트〉, 2015-07-26

같이 보기

• 부정연산
• 논리합
• 논리곱
• 부정논리합
• 부정논리곱

이 배타적 논리합 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반