이동식 저장소

13주 2차시 본문

CS/암호학

13주 2차시

해스끼 2020. 11. 28. 14:47

미래의 암호

아주 피상적으로 이런 암호를 생각해 볼 수 있다.

 

빨간색 ``마법 잉크``를 이용하여 글씨를 쓴다. ``마법 잉크``는 평소에는 빨간색이지만, 빛을 받으면 검은색으로 변한다. 즉 수신자가 편지를 열어봤을 때 글씨가 빨간색이었다면(곧 검은색으로 변하겠지만) 아무도 이 편지를 열어보지 않았음을 알 수 있다. 그런데 열어봤더니 글씨가 검은색이라면 누군가 편지를 열어봤음을 알 수 있다.

 

뭔 소리냐고?

지금부터 얘기할 것들을 자세히 이해하려면 물리를 깊게 알아야 한다. 잠깐 딴 얘기좀 하겠다.

물리가 뭔데?

  • 픽션 세계에서는 무엇이든 가능하다.
  • SF에서는 적당히 과학처럼 보이도록 하면 섞으면 무엇이든 가능하다. 물론 너무 비과학적이면 욕을 먹긴 하겠지만.
  • 수학 세계에서 일어나는 일은 논리적이고 모순이 없지만 현실에서 반드시 성립한다는 보장은 없다. (예시: 무한집합)
  • 물리는 수학적이어야 하며, 동시에 실험적으로 성립해야 한다.

그럼 아는 게 뭔데?

  • 논리 세계에서는 모순 없는 공리 집합이 주어지고, 공리로부터 증명될 수 있는 모든 명제는 참이다.
  • 물리에서는 실험을 여러 번 반복하여 같은 결과를 얻을 때 ``어떤 사실을 안다``고 말한다. 논리 세계보다 조금 약하다. 

논리를 왜 믿는데?

이렇게 주장할 수도 있다.

  • 논리가 complete하기 때문이다. 즉, 모든 사실인 ``Theorem``은 증명될 수 있기 때문이다.
  • 논리가 consistent하기 때문이다. 즉 모든 사실은 모순이 없다.

아닌데?

괴델의 ``불완전성 정리 1``에 의하면 증명할 수 없는 사실이 존재한다. 즉 어떤 사실 $T$가 사실이라고 증명할 수 없기 때문에 $\sim T$가 거짓이라고 할 수도 없다는 말이다. 

 

$T=$``이 Theorem은 증명이 없다``라고 해 보자.

  • $T$가 참이고 $T$의 증명이 존재한다면 $T$는 사실이다. 따라서 $T$에 의해 $T$의 증명은 존재하지 않는다. 모순!
  • $T$가 거짓이면 $\sim T$가 참이므로 $T$의 증명이 존재하게 된다.

따라서 $T$는 참이지만 증명이 없는 경우만이 모순되지 않는다. 사실 완전히 증명한 건 아니다. 공리계가 모순이 없다고 가정하고 얘기했을 뿐이다. 만약 공리계가 모순이 없음을 보일 수 있다면 $T$를 증명할 수 있다. 그런데 위에서 $T$의 증명이 없다는 것을 보였다.

 

즉 공리계가 모순이 없다는 걸 알 수 없다. 이것이 ``불완전성 정리 2``이다.

 

????????????

공리계에 모순이 존재한다면 $T$도 성립하고 $\sim T$도 성립하는 경우가 있을 수 있다. 사실 이것이 음모론자들의 논리이다. 하지만 수천 년 동안 아무도 수학의 공리계에서 모순을 찾지 못했다. 즉 물리에서의 사실처럼 경험적으로 믿어 볼 만하다는 얘기다. 증명할 수는 없지만 아마도 모순이 없지 않을까? 

오컴의 면도날

  • 하나의 실험 결과를 여러 개의 이론으로 설명할 수 있다면, 가장 짧은 이론을 선택하라.

즉 공리계를 가능한 한 작게 만들라는 말이다. 공리계가 작아질수록 공리로부터 도출되는 사실을 예측하기가 더 쉬워지기 때문이다.

 

PS에서도 성립하는 말이다. 같은 결과를 내는 코드는 간결할수록 좋다. 그렇다고 숏코딩처럼 과하게 하진 말고..

 

다시 물리로 돌아가자.

과학의 원리

다음의 세 문장은 모두 동치이다.

 

  • 무언가가 존재한다는 사실을 실험으로 보일 수 없다면, 그 ``무언가``는 존재하지 않는 것이다.
  • 어떤 차이가 존재한다는 사실을 실험으로 보일 수 없다면, 그 ``차이``는 존재하지 않는 것이다.
  • 두 물체를 실험을 통해 구분할 수 없다면, 두 물체는 같은 물체이다.

과학에서는 실험이 왕이다. (실제로 하신 말)

다음의 예시를 읽으면서 과학의 원리에 대해 생각해 보자.

천동설과 지동설

옛날 사람들은 지구는 멈춰 있고, 하늘(천구)이 움직인다고 생각했다. 왜냐고? 지구에서 보면 그렇게 보이니까. 지구가 돌면 어지럽지 않겠냐? 옛날 사람들은 지구가 중앙에 있고, 수성, 금성, 태양 등은 천구 상에서 움직인다고 생각했다.

 

그런데 관측 결과를 천동설로 설명하려는 과정에서 모델이 너무 복잡해졌다. 주전원이니 뭐니 하는 것들을 계속 넣으니까 약간 비상식적으로 보이기까지 한다. 논리적으로는 모순이 없고 관측 결과와도 일치하지만, 천동설은 너무나도 복잡했다. 

 

오컴의 면도날을 적용해 보면 천동설은 사실이 아닌 것처럼 보인다. 왜냐하면 ``지구가 움직인다``는 가정 아래에서 모든 관측 결과를 훨씬 더 간단하게 설명할 수 있거든! 와!

특수 상대성 이론

뉴턴 역학은 약 120년 정도 전까지는 완벽히 성립했다. 사실 뉴턴 역학도 상대론이다. 뉴턴 이전의 역학은 모두 땅을 중심으로 생각했지만, 뉴턴 역학은 물체의 움직임에 절대적인 기준을 두지 않는다. 즉 ``내가 봤을 때 가만히 있는 사람``은 존재하지만, ``절대적으로 가만히 있는 사람``은 생각할 수 없다.

 

그런데 약간 문제가 생겼다. 사람들이 빛의 속력을 재 보니 약 $300,000km/s$가 나왔다. 만약 내가 빛과 같은 방향으로 $100,000km/s$로 움직인다면, 뉴턴 역학에 의해 내가 보는 빛의 속력은 $200,000km/s$일 것이다.

 

그런데 그렇지 않더라!

가만히 서 있는 사람이 봐도, $100,000km/s$로 움직이는 사람이 봐도, 누가 봐도 빛의 속력은 항상 똑같다. 실제로 어떤 사람이 초속 10만km/s로 움직여본 건 아니고, 다른 방법으로 실험을 해 봤다. 어쨌든 결과는 같다.

 

누가 봐도 속력이 같다? 이게 말이 되냐?

이 문제를 해결한 사람이 바로 아인슈타인이다. 아인슈타인은 뉴턴 역학에 ``광속은 절대적``이라는 개념을 성공적으로 편입했다. 아인슈타인은 빛의 속력을 절대적으로 만들었고, 대신 시간과 공간을 상대적으로 만들었다. 예컨대 나보다 빠르게 움직이는 사람의 시간은 나보다 천천히 흐른다. 날씬하게 보이고 싶다면 수평 방향으로 광속에 가깝게 움직이자!

 

시간과 공간을 상대적으로 만들면 $e=mc^{2}$라는 공식도 알아낼 수 있다. 다음 시간에 이어서 얘기한다.

'CS > 암호학' 카테고리의 다른 글

14주 2차시  (0) 2020.12.06
14주 1차시  (0) 2020.12.05
13주차 1차시  (0) 2020.11.25
12주차 2차시  (0) 2020.11.21
12주차 1차시  (0) 2020.11.19
Comments