XOR 연산, XOR 암호화

XOR연산

어떠한 공부를 할때에는 정의부터 정확히 짚고 가는것이 좋다고 생각함으로...

XOR 연산 이란 : 배타적 논리합 이라고도 하며 밑에 있는 기호를 사용하고 코딩상에서는 ^ 를 사용한다. 제곱?

⊕

두 명제 중에 정확히 하나만 참일 경우 참 값을 돌려주는 연산

XOR 연산
입력값	결과값
0 , 0	0
0 , 1	1
1 , 0	1
1 , 1	0

OS 를 공부할때 XOR 로 사라진 파일에 대한 백업처리를 했던 것이 기억이 난다.

XOR을 두번 한다면 원래 자기자신이 되거 OR 나 AND 연산에 비해 그 패턴이 독특하기때문에, 암호화에도 많이 쓰인다고 한다. 고급 암호화 표준에서 MixColumns 라는 단계에서 XOR 을 특별하게 사용하고 AddRoundKey 에서도 XOR을 쓴다고 하지만...이해하기 어려우므로 패스...

XOR 이 가지는 가장 특이한 성질은 바로 반전 시켜줄수 있다는 것이다. 위의 입력값과 결과값을 보라, 생각을 해보자, 0일때 1을 만나면 1이 되고, 0일때 0 을 만나면 그대로 0이다.

1일땐 1을 만나면 0이되고 0을 만나면 1이된다.

1이 1만나면 0 / 0이 1만나면 1 그렇다 

어떠한 비트가 있을 때, 1111 1111 과 XOR 연산을 시키면 원래의 비트의 0과 1이 반전되어 

나타난다. 실제로 그러한지 몇번 해보자

입력값	0011 1010	1001 0110
XOR	1111 1111	1111 1111
결과값	1100 0101	0110 1001

 

0과 1이 반전되어 나왔다. 

그리고 다시한번 이를 XOR 연산을 한다면 

        

입력값	1100 0101	0110 1001
XOR	1111 1111	1111 1111
결과값	0011 1010	1001 0110

같은 대상에 대해서 같은 XOR 을 두번했더니 자기 자신이 나왔다. 이제 실제 숫자를 가지고 한번 생각을 해보자.

65 라는 숫자를 비트로 나타내보면 0100 0001 이고

42 라는 숫자를 비트로 나타내보면 0010 1010 이다. 자 이제 이 두 수를 XOR 해보자

65	0100 0001
42	0010 1010
결과 [ 107 ]	0110 1011

65와 42를 XOR 연산 했더니 107이 나왔다.

자 그럼 이제 이 107을 다시 42와 XOR 연산을 해보자

107	0110 1011
42	0010 1010
결과 [ 65 ]	0110 0001

원래데로 65가 나왔다. 놀랍다

그런데 이를 보고있으면 한가지 특성을 더 알수있다. 결과값이 107이나 65만을 보고서는

앞에 XOR 연산된 두비트중 앞에 것이 True 인지 뒤에것이 True 인지 알수가 없다는 것이다.

XOR 연산 결과가 1 이면 이는 ( 0 , 1 ) 일수도 ( 1 , 0 ) 일수도 있다는 것이다 ! 

그럼 이제 이러한 XOR 을 가지고 어떻게 암호화를 하는지 알아보자

---------------------------------------------------------------------

우선 XOR 은 CPU 에서 제공하는 연산으로 128비트를 암/복호화 하는데 만여 사이클이 소요되는 AES 암/복호화와 달리 많아야 100사이클정도면 128비트를 암호화 할수 있다고 한다.

한마디로 굉장히 빠르다는 것 ! 

일단 가장 기본적인 암호화를 생각해보자 우리가 임의의 KEY 를 만들고 우리가 가진 데이터를 이 KEY 로 XOR 연산을 해서 저장하거나 전송하는것이다. 다른 사이트에서 친절하게 연습해놓은 코드를 살포시 가져와서 보자.

http://www.gamedevforever.com/165 이곳 출처

47a3efc2 라는 KEY 를 가지고 XOR 연산을 한것으로 결과값을 보면 도저히 알아볼수가 없다.

와 암호화 성공! 이라고 하고싶지만, 의외로 XOR 만을 이용해서는 힘들다고한다.

만약 AAAAA 이렇게 보내면 ? 어떠한 값이 나올것이고 BBBBB 로 다시보내고 이런식으로 보내서 바뀌는 패턴을 보고 하다보면 KEY를 들키는 것은 시간문제라고 한다.

왜냐하면 앞에서도 봤듯이, XOR 에는 '복원' 시켜주는 성질이 있기 때문이다.

A,B,C 라는 것이있을때 A ^ B = C 가 성립하는것을 알고있고, A,B,C 중 두개를 알면 나머지 하나를 알아낼 수 있기 때문이라고한다.

즉 XOR 만을 이용한 어떠한 암호화 과정을 거친다한들 AAA, BBB, CCC 등을 보내면서 몇 비트 

단위로 반복되는지 확인하고, 바뀌어서 나온 값을 원래 입력한 값과 비교해나가다 보면 내가 숨긴 KEY 를 찾을 수있다는것.

결론 : XOR 만을 가지고서는 어느정도의 보안성을 갖출순 있지만, 어렵지않게 뚫릴수 있다. 

돌아다니다 보니 흥미로운 그림을 찾을수 있었다.

이런 그림이 있는데 이 그림을 AND 연산을 해서 하면 어떻게 될까 ? 

AND 연산의 결과다. 뭔가 뿌옇게 됬다고 해야할까, 바뀌었다. 그럼 OR 연산을 하면 어떻게 될까.

선명하다, 나름 마지막으로 XOR 연산을 한다면 어떻게 될까 

원래 뭐였는지 알아볼수 없게 되었다. XOR최고!