전화상에서 동전 던지기 수학이야기


이번에 암호학을 배우다가 재밌는 걸 배웠는데,

재밌는 것은 다같이(...) 재밌어하는게 좋을것 같아서 올립니다.

문제는 전화상에서 동전던지기와 같은 내기를 어떻게 하느냐는 건데,

예전에 유행했던 케잌을 어떻게 잘라 배분해야 모두가 만족하느냐는 문제와 비슷한느낌이 나죠?



A와 B가 전화를 통하여 동전던지기를 진행한다고 가정해봅니다.

A가 동전을 던진다고 하면, B는 동전이 어떻게 나왔는지 확인이 불가능합니다. 반대도 마찬가지구요.

앞면이 나오든 뒷면이 나오든 상대방이 자기한테 유리한쪽으로 뻥카를 칠 수 있으니,

설사 자신이 이기는 패가 나와 사실대로 이야기한다 하더라도 상대방이 납득하지 않을수도 있습니다.

그러니까 전화상에서 동전던지기가 성립하려면 조건이 2개 필요합니다.

(1) A와 B모두 동등한 조건일 것
(2) 이긴쪽이 증거로 상대방을 승복시킬수 있을것


 지금쯤 이글을 읽는 사람들은 다들 이런모습이겠죠?
이런이야기 좋아하잖아요?


(2)번 조건은 둘째치고, (1)번 조건부터 골치가 아파옵니다.

한쪽에서 동전을 던지고 다른쪽은 볼수도 확인할수도 없는데 동등한 조건이게 해야한다니...

그래서 사용하는게 '소인수 분해의 어려움' 과 '중쿡인의 나머지 정리(이하 CRT)' 입니다.
소인수분해의 어려움은  n=pq 일때, n값으로 p,q 값을 알아내기 힘들다는것이고 
CRT는 나누는 수와 나머지에 대한 관계만 있을때, 연립해서 원래 값을 찾아내는거죠.
 

위의 두가지를 이용하여 다음과 같은 방법을 이용합니다.


[1] A가 소수 p,q를 임의로 골라 n을 만들고, B에게는 n만 알려준다.
[2] B는 0<x<n을 만족하는 임의의 x를 선택한다.
[3] B는 x^2 ≡ c mod n 를 만족하는 c를 A에게 알려준다.
[4] A는 CRT를 이용해서 c mod n을 만족하는 해 ±x, ±y를 구해낸다.
[5] A가  x, y 중 하나를 택1하여 B에게 보낸다.
[6] A가 x를 택했으면 A의 승리. (B는 자신이 선택했던 x만 가지고 있으므로 p,q를 구할수 없음)
[7] A가 y를 택했다면 B는 p,q를 구해내어 승리.


여기서 핵심은 [4]에서 A가 CRT를 쓸수 있다는것과, CRT를 사용하면 B가 골랐던 해 x와 다른해y가 나온다는것입니다.

A가 [4]에서 x,y를 구하는 상태에서 아는건 (n, p, q, c) 뿐이니까요. x,y중 어떤게 B가 골랐는지 알방법이 없죠.

반면 B는 x와 y를 둘다 알면 pq를 구할 수 있게되는데, A가 y를 선택하기 전까진 모르죠.
y를 알면 어째서 p,q 값을 알게되는지에 대해선 간단해요.
x,y가 해이기 때문에 x^2≡ y^2≡c mod n이고, n|x^2 - y^2 ⇒ n|(x+y)(x-y) 란 이야기니까 gcd(x+y, n), gcd(x-y, n) 가 p,q가 되죠.



그럼 이제 한번 실습해보면,

원랜 무진장 큰자리를 골라야하지만 사람은 못하니까귀찮으니까 작은수로...

[1] A가 p=5, q=7을 골라서, B는 35만을 알고있습니다.
[2] B는 0<x<n=55을 만족하는 임의의 11을 선택했습니다.
[3] B는 11^2 ≡ 16 mod 35 를 만족하는 16을 A에게 알려줍니다.
[4] A는 CRT를 이용해서 x^2 ≡16 mod 35을 만족하는 x인 ±4, ±11를 구해낸다.
CRT를 쓰면 x^2 ≡2 mod 7, x^2 ≡1 mod 5 로 나뉘고 각각 x=3,4, x=1,4 가 나오지요.
법7에 대해 3인 x : 3, 10, 17, 24, 31
법7에 대해 4인 x : 4, 11, 18, 25, 32 이고,
여기서 법 5에 대해 1,4 인것은 4, 11, 24, 31 뿐이고, 4,11은 법 35에 대해 ±4로 11,24는 법 35에 대해 ±11로 나옵니다.

[5] A가 4, 11 중 하나를 택1하여 B에게 보낸다.
[6] A가 4를 택했으면 A의 승리.
[7] A가 11을 택했다면 B는 5,7을 구해내어 승리.
gcd(11+4, 35)=5, gcd(11-4, 35)=7




네. 전화상에서는 동전던지기가 이렇게 가능합니다.

이제 다들 핸드폰으로 통화하면서 장거리 내기를 해보아요. 우왕국

전화상에서 동전 던지기를 배운뒤, 나으 대응. 화상전화



덧글

  • LeeChai 2011/12/25 09:11 # 답글

    그냥 얼굴 보고 던질래요..
  • YoUZen 2011/12/25 19:03 #

    제 말이...
  • SilverRuin 2011/12/25 10:14 # 답글

    평범한 암호화 복호화 [.....]
    근데 전 저 고양이처럼 귀엽지는 않아서 망했어요
  • YoUZen 2011/12/25 19:08 #

    딱히 복잡한건 아니지만 그래도 발상이 재밌잖아요.
    DES나 RSA는 재밌는게 없어서 올리면 아무도 안읽을것 같아서욬ㅋㅋㅋㅋ

    안귀여워도 괜찮아요. 멋있으면 됩니다. 남자는 역시 멋이죠.
  • 淸嵐☆ 2011/12/25 10:22 # 답글

    가장 기초적인 암호화 복호화 과정이군요..
    저걸 저렇게 써먹을 수도 있다니 참신합니다 ㅎㅎ
  • YoUZen 2011/12/25 19:09 #

    암호학이 여러가지 재밌는 내용이 많아서 좋긴한데, 재밌어하는거랑 성적이랑은 별개더라구요ㅠㅠㅠㅠㅠㅠ
  • 킨키 2011/12/25 17:19 # 답글

    고양이가 귀엽군요
  • YoUZen 2011/12/25 19:10 #

    귀엽지 않다면 올리지 않습니다. 하앜하앜♡
  • 대공 2011/12/26 19:26 # 답글

    근데 B가 x를 y라 뻥치고 pq를 구한다면...
  • YoUZen 2011/12/27 20:05 #

    A가 x를 보낸상태에선 B가 y를 구할수 없습니다. y를 포함하여 더 많은 정보가 없는상태에서 p,q를 구하려면 엄청난 시간이 필요하다능...
  • 학생 2016/06/01 13:53 # 삭제 답글

    음 반대 아닌가요?? A가 y = 4를 선택했으면 x=11임을 알고 있는 B가 5,7을 구해낼 수 있잖아요.
    A가 x = 11을 선택하면 B가 구할 수 없으니까 패배하는 것 같은데요
  • 학생 2016/06/01 13:53 # 삭제 답글

    음 반대 아닌가요?? A가 y = 4를 선택했으면 x=11임을 알고 있는 B가 5,7을 구해낼 수 있잖아요.
    A가 x = 11을 선택하면 B가 구할 수 없으니까 패배하는 것 같은데요
  • 학생 2016/06/01 13:53 # 삭제 답글

    음 반대 아닌가요?? A가 y = 4를 선택했으면 x=11임을 알고 있는 B가 5,7을 구해낼 수 있잖아요.
    A가 x = 11을 선택하면 B가 구할 수 없으니까 패배하는 것 같은데요
댓글 입력 영역


통계 위젯 (화이트)

1610
47
340948

카운터

free counters

글로1ㅡ