더 나은 세상은 가능하다, 이정환닷컴!

RSA 공개 열쇠의 이해.

Written by leejeonghwan

February 28, 2004

‘RSA 공개 열쇠 방식’의 암호화는 다음의 3단계 과정이 필요하다.

1단계 : 공개 열쇠 만들기.

1. 암호를 받는 쪽에서는 아무거나 두 소수, p와 q를 생각한다.
2. p와 q를 곱해 N을 만든다.

3. 아무 숫자나 다음 식을 만족하는 두 숫자를 생각한다.

1=(e*d)mod[(p-1)(q-1)]

4. mod()는 나머지를 구하는 함수다. 40mod(7)은 40을 7로 나눈 나머지를 구하라는 말이다. 답은 5다.

5. N과 e는 공개 열쇠다. 전화로 불러줘도 되고 사람들에게 알려줘도 된다. 전혀 문제가 없다.

2단계 : 암호 만들기.

1. 이제 암호를 만드는 쪽에서는 공개 열쇠 N과 e를 써서 암호를 만들어보자. 문제는 다른 사람들도 모두 이 공개 열쇠를 알고 있다는 사실이다. 열쇠는 공개돼 있지만 받는쪽에서만 풀 수 있어야 한다.

2. 먼저, 문서의 모든 글자를 이진수로 바꾸고 다시 십진수로 바꾼다. 이 숫자를 M이라고 한다. 우리는 지금부터 M을 암호로 바꾼다.

3. 다음 식을 써서 암호 C를 만든다.

C=Memod(N)

3단계 : 암호 풀기.

1. 암호 C를 받아서 원래 문서 M으로 풀어보자.
2. 공식은 간단하다. N과 d를 집어넣으면 된다.

M=Cdmod(N)

3. N과 e는 공개돼 있지만 다른 사람들은 p와 q를 알 방법이 없다. 한번 더 계산해서 만든 d는 더 알 수 없다.

백문이 불여일견, 예제를 풀어보자.

1단계 : 공개 열쇠 만들기.

1. 이정환은 두 소수 11과 17을 생각하고 곱해서 공개 열쇠 N을 187로 잡는다.

2. 이정환은 대충 d를 23로 놓고 다음 공식에 넣어서 공개 열쇠 e를 7으로 잡는다.

1=(e*d)mod[(p-1)(q-1)]

1=(7*23)mod(10*16)
1=161mod(160)

3. N과 e, 187과 7을 공개한다. 얘들아, 우리 이걸로 암호 만들거다. 풀 수 있으면 풀어봐라.

2단계 : 암호 만들기.

1. 백우진은 ‘X’를 암호화하려고 한다. 이진수로 바꾸면 1011000, 다시 십진수로 바꾸면 M은 88이 된다. 백우진은 M을 공개 열쇠 N과 e, 187과 7을 써서 암호로 바꾼다.
2. 공식에 집어넣는다.

C=Memod(N)

C=887mod(187)
C=40867559636992mod(187)
C=11

3. 40867559636992을 187로 나누면 나머지가 11이 나온다는 이야기다. 11이 암호다. 11를 이정환에게 보낸다.

3단계 : 암호 풀기.

1. 이정환은 이제 암호 C, 11을 풀어 원래 숫자 M을 찾아내야 한다.

2. 공식에 집어넣는다. N과 d는 각각 187과 23이다.

M=Cdmod(N)

M=1123mod(187)
M=895430243255237372246531mod(187)
M=88

3. 88, 암호를 풀었다. N은 공개 열쇠지만 d는 이정환만 아는 숫자다. 처음에 생각한 숫자 p와 q를 곱해서 N을 만들고 이걸 조합해서 d와 e를 만들었는데, 공개된 N과 e만 가지고 d를 찾기는 굉장히 어렵다. 거의 불가능하다.

‘RSA 공개 열쇠 방식’은 MIT 컴퓨터 사이언스 실험실의 론 리베스트와 아디 샤미르, 레너드 애들먼, 세 사람이 발명했다. RSA는 이들의 머릿글자 모음이다. 이 암호화 방식의 핵심은 소인수 분해에 있다.

두 소수 p와 q를 곱해서 공개 열쇠 N을 만들면 이걸 쥐고 아무리 난리법석을 떨어도 원래 숫자를 찾을 방법이 없다.

35가 5와 7로 나눠져 있다는 건 쉽게 알 수 있다. 소인수 분해는 하나하나 숫자를 맞춰보는 수밖에 딱히 방법이 없다. 숫자가 커지면 슈퍼컴퓨터를 돌려도 몇십년씩 걸린다. 17과 19607843을 곱하면 333333331이 된다는 건 쉽게 알 수 있지만 그걸 찾기가 어렵다는 이야기다. 실제로 수학자들은 수백년동안 이 숫자가 소수라고 생각해왔다.

여기서 문제를 한번 더 뒤집어 공개 열쇠를 두개 만들어 놓고 이걸 꼬아서 혼자만 아는 결정적인 열쇠 d를 만들어 놓으면 당신의 암호는 거의 완벽하다고 할 수 있다.

위의 예제에서 공개 열쇠 N과 d는 각각 187과 23이다. 이걸 풀려면 N이 먼저 뭐와 뭐의 곱인가 알아야 한다. 그리고 그 뭐와 뭐에서 각각 1을 뺀 숫자의 곱을 구하고 거기서 다시 1을 뺀 수가 d의 몇배인가도 알아야 한다. 몇배인가만 알면 암호는 풀리겠지만, 한번 해봐라. 결코 만만치 않다.

187 정도면 어떻게 풀릴 수도 있지만 보통은 자릿수가 308 이상이다. 한번 보겠는가.

42862803482534211706798214808651328230664709384460955058223172
53594081284811174502841027019385211055596446229489549303819644
28810975665933446128475648233786783165271201909145648566923460
34861045432664821339360726024914127372458700660631558817488152
09209628292540917153643678925903600113305305488204665213841469
51941511609433057270365759591953092186117381932611793105118548
0744699627495237

이게 308자리 숫자다. 이게 뭐와 뭐, 두 소수의 곱으로 돼 있는가 맞춰봐라. 이 정도면 1억대의 PC를 한꺼번에 돌려도 1000년이 넘게 걸린다고 한다. 현재의 과학기술로는 이런 암호를 풀 방법이 없다.

도움 말씀 : 백우진.
참고문헌 : ‘코드북’, ‘현대수학의 여행자, ‘수학: 양식의 과학’, ‘영부터 무한대까지’, ‘수학의 황제 가우스’.

Related Articles

Related

잔여백신 예약 노하우.

잔여백신 예약 노하우.

“나만 안 맞았어 백신(EVEM, Everybody Vaccinated. Except Me.)” 증후군에 시달리다가 오늘 작정하고 휴가부터 냈습니다. 10시부터 매복하다가 5분 만에 예약 성공해서 맞고 왔습니다. 위에 그림에서 보는 것처럼 터치를 네 번 해야 되는데, 이걸 1초 만에 끝내는 게 관건입니다. 별 건 아니지만 약간의 노하우가 있어서 정리해 봅니다. 0. 잔여 백신은 노쇼 백신과는 좀 다른 의미입니다. 일단 1병을 개봉해서 여러 명이 맞을 수 있는데 LDS(Low...

모니터 연결 없이 라즈베리파이 원격 제어하기.

모니터 연결 없이 라즈베리파이 원격 제어하기.

1. 일단 SD카드를 컴퓨터에 연결해서 라즈베리 OS를 설치해 줍니다. 2. 자동으로 와이파이를 잡아주기 위해 루트 디렉토리에 wpa_supplicant.conf 파일을 만들고 다음과 같이 적어줍니다. 터미널 프로그램으로 접속하면 됩니다. cd /Volumes/boot touch ssh vi wpa_supplicant.conf country=US ctrl_interface=DIR=/var/run/wpa_supplicant GROUP=netdev update_config=1...

티본 스테이크, 실패 없이 잘 굽는 방법.

티본 스테이크, 실패 없이 잘 굽는 방법.

유튜브에 뒤져보면 온갖 비법이 넘쳐나는데 전문가들도 조금씩 스타일이 다르다. 스테이크를 잘 굽는 모든 노하우는 결국 안쪽까지 온도가 잘 전달되게 만드는 것이 전부다. 자칫 겉은 타고 안은 피가 뚝뚝 떨어지는 상황을 피하려면 최적의 온도와 시간을 맞춰야 한다. 이게 다 고기가 두꺼워서 생기는 문제다. 몇 가지 기본만 갖추면 된다. 첫째, 겉면을 굽고(시어링), 둘째, 버터를 끼얹으면서 안쪽까지 열이 전달되도록 하고(베이스팅), 셋째, 꺼내서 적정 시간을 식힌다(레스팅). 핵심은...

더 나은 세상은 가능하다, 이정환닷컴!

Join

Subscribe For Updates.

이정환닷컴 뉴스레터를 구독하세요.