[강연] 타원곡선암호 (ECC, Elliptic Curve Cryptography)

이상엽Math
5 팔로워
후원 | 우리은행 1002-031-127166 (이상엽)
00:00 들어가며
03:17 ① 타원곡선암호란?
05:25 ② 타원곡선이란?
07:07 ③ 타원곡선상의 연산
16:17 ④ 나머지(Modular) 연산
21:47 ⑤ 나머지 연산이 적용된 타원곡선
31:25 ⑥ 나머지 연산이 적용된 타원곡선의 특성
33:11 ⑦ 타원곡선상의 이산대수문제 (ECDLP)
37:02 ⑧ 타원곡선암호의 예
#암호 #암호학 #응용수학
http://이상엽Math.com
사원곡선 암호랑 이제 나중에 이걸 가지고 페르마의 마지막 정의라고 하는 수학계의 위대해서도 난제가 있습니다.
그거를 또 어떻게 해결까지 했는가 라는 거를 쭉 이야기를 할 거고 필기를 좀 많이 했으면 좋겠습니다.
수학이라고 해서 여러분들이 고등학교 때 배우는 수학 내용들, 미적분 이런 것들 대체 현실에서 어디 쓰이냐 궁금해 하는 학생들도 많고
대표적으로 그런 이제 고차원적인 수학 내용들이 많이 쓰이는 분야가 암호학이에요.
현대시대는 우리가 지금 살고 있는 현대시대는 사실상 암호학이라는 기반 위에 세워진 사회다라고 봐도 과언이 아니거든요.
만약에 암호라는 게 없으면 어떻게 될까?
그쵸 그러니까 기본적으로 어디 웹사이트 홈페이지 이런 데 회원 가입하는 것 자체가 무의미하게 돼요.
왜? 나의 그런 모든 개인적인 정보들 비밀번호 이런 것들은 누구나 맘먹고 열람하려고 하면 볼 수 있는 정보가 돼 버리거든요.
우리가 우리의 비밀번호나 이런 것들이 개인적인 신상들이 퍼지지 않는 이유는 이것들이 전부 다 암호화 되어서 저장되어 있기 때문이에요.
그러니까 해커가 진짜 맘먹고 그 암호를 해독하는 방식으로 들어가지 않으면 우리의 정보를 알아내기가 쉽지 않은 것이죠.
또 여러분들이 친구들 간에 카톡도 아마 못 보낼 겁니다.
여러분이 친구한테 카톡을 보낸 것도 누군가 맘먹고 보려고 하면 아무나 볼 수 있게 되거든요.
암호라는 게 없으면 뭐 금융거래 같은 거 가능할까요?
여러분들이 친구한테 모바일로 돈을 보낸다. 중간에 해커가 마음껏 빼낼 겁니다.
카드 결제 가능할까요? 불가능해요.
암호라는 게 만약에 없으면 우리는 오로지 사람이 얼굴 맞대고 만나서
직접 현금으로 이렇게 그냥 지폐로 주고받는 시계 거래밖에 못합니다.
내가 왜 현대사회가 암호화기의, 암호화기라는 기반 위에 세워진 사회다라고 말하는지 알겠죠?
근데 이 암호화기의 기반은 또 무엇이냐라고 하면 수학입니다.
왜 해커들이 여러분들의 개인 정보를 빼내는 게 쉽지 않은가 라고 하면
어려워서 거든요. 그거를 암호 해독하는 게 왜 어려울까요?
그 어려운 근본적인 이유는 어려운 수학 문제를 바탕으로 암호를 만들기 때문이에요.
그러니까 아직까지 현대시대까지도 해결되지 않은 수학의 난제들을 바탕으로 암호 시스템을 만들어요.
그러니까 해커가 그 수학 난제를 해결할 정도의 해커가 되지 않는 이상 쉽게 암호를 빼놓을 수가 없는 거예요.
그러니까 어떻게 보면 제가 옛날에 그런 말을 한 적이 있어요. 수학이 어렵죠.
어려운 수학이기 때문에 현대사회가 이렇게 온전하게 돌아갈 수 있는 것이다.
안 그러면 암호라는 게 존재할 수 없고 우리는 아까 말했던 것처럼 원시시대로 돌아갈 수밖에 없어요.
그래서 오늘 같이 볼 타원곡선 암호 같은 경우는 현대시대에서 쓰이고 있는 대표적인 암호 시스템이에요.
그래서 오늘 이런 내용들을 잘 알아두면 좋겠다.
그래서 간단하게 타원곡선 암호라는 게 뭔지 정의를 좀 써주자면
타원곡선 암호란, 지금 학생들 글씨 잘 보이는, 일단 타원곡선 이론에 기반을 둔 암호 방식입니다.
여러분 RSA 암호라는 말 들어본 적 있어요?
RSA 암호 방식도 사실 보편성을 따지면 RSA 암호 방식이 더 보편적으로 많이 쓰여요.
왜냐하면 RSA 암호가 타원곡선 암호에 비해서 10년 정도 일찍 개발이 됐거든요.
선점 효과식으로 먼저 개발이 되면서 산업 전반적으로 보편적으로 쓰이게 됐는데 RSA가.
근데 타원곡선 암호가 현대에 들어서 많이 각광을 받는 이유가
타원곡선 암호가 RSA보다 두드러지는 강점이 있어요.
뭐냐면은 더 짧은 키로도 강한 보안을 하는 게 가능해요.
그러니까 뭐 제가 여기 적어놓지는 않았지만 구체적으로 얘기를 하자면은
타원곡선 암호로는 한 255 비트 정도?
비트 단위 알죠? 비트. 0과 1 그 두 개 비트라고 그러죠?
그래서 255 비트라고 하면 0, 1이 들어갈 수 있는 그게 255 칸이다 생각하면 돼요.
한 255 비트 정도의 타원곡선 암호의 그 안전성 정도는 RSA 암호로 치환했었을 때는 2048 비트 정도로 만들어야 됩니다.
그러니까 바꿔 말해서 타원곡선 암호가 짧은 키로도 더 강력한 보안을 만들어낼 수 있습니다.
다만 산업 전체적으로는 아직까지는 RSA가 많이 쓰인다.
타원곡선 암호는 요새 많이 각광받는 이유가 비트코인 같은 거 들어갔죠?
비트코인 같은 그런 암호 화폐라고 그러죠?
그 암호 화폐가 암호를 기반으로 만들어진 화폐잖아요?
그 암호가 대체로 타원곡선 암호를 써요.
그래서 요새 또 많이 주목을 받고 있죠.
혹시 뭐 이거에 대해서 궁금한 학생들은
제가 유튜브에 예전에 가격을 올렸던 게 있어요.
그래서 RSA 검색하면 제 영상에 나올 거니까
이거 보고 공부하면 되겠습니다.
타원곡선은 제가 써놨다시피
여러분들이 타원곡선이라고 하면 마치 타원형의 곡선일 거라고 생각하지만
사실 타원곡선은 타원 모양이 아니에요.
그럼 왜 타원곡선이라고 불리느냐?
처음에 이 타원곡선이라는 게 연구된 시작 자체가
타원의 호의 길이를 구하는 것에서부터 시작됐어요.
그러니까 타원의 둘레 길이를 구한다고 생각하면 돼요.
타원의 둘레 길이를 구하는 데 있어서 쓰이는 접근 함수가
거기에서 이제부터 계속 보게 될 방정식이 나와요.
그렇기 때문에 타원곡선이라고 부르지만
사실 타원곡선 자체는 타원형이 아닙니다.
이제부터 계속 보게 될 타원곡선이란
이러한 방정식 호를 말을 해요, 밑에 있는.
예를 들어서 그래프를 하나 그려보자.
이러한 타원곡선을 가져보겠습니다.
y제곱은 x세제곱 마이너스 2x 플러스 4
그래프를 그리면 이렇게 돼요.
왼쪽이 y제곱이니까
제곱을 풀어주면 플러스 마이너스 루트가 되잖아요.
그래서 플러스 루트가 밑에는 여기가 되는 거고
마이너스 루트가 여기에 되는 거고
그러니까 x축을 기준으로 대칭 형태를 띄게 되죠.
오른쪽에 있는 3차식은 여러분들이 그릴 수 있잖아요.
예를 들어서 x가 0일 때
x에 0을 대입하면 y는 풀 마 2가 나오죠.
그래서 여기 0 대입하면 풀 마 2가 나오는 거예요.
괜찮죠?
마이너스 2를 대입하면
그러면 마이너스 8에 플러스 4 플러스 4하니까 0이 되죠.
그래서 마이너스 2는 정확하게 0 여기 찍히는 거죠.
괜찮아요?
이런 게 타원곡선이에요. 쉽죠?
그런데 이제부터가 재미있는 얘기예요.
이 타원곡선에서 이제부터 여러분들이 알고 있는
더셈 곱셈이 아니라 새로운 방식의 더셈과 곱셈을 이야기할 거예요.
그러니까 여러분들이 기존에 갖고 있었던 더셈에 대한 이미지는
지금부터 지워야 돼요.
그래서 이 타원곡선에서 더셈이라는 걸 새롭게 정의를 할 건데
어떻게 정의할 거냐면 지금 써놓은 것처럼
타원곡선상의 어떤 두 점을 a랑 b라는 걸 우리가 찍어보면
이 둘에 대한 더셈은 선을 긋고 만나는 점의 대칭점이에요.
이런 식이에요.
a랑 b라는 두 개의 점을 찍어요.
그럼 a 더하기 b는 뭐냐?
이 둘로부터 선을 이어요.
그러면 만나는 점이 있죠?
거기서 대칭점을 찾아요.
그게 바로 뭐다?
a 더하기 b라는 결과다 라고 정의를 하는 거예요.
좀 독특하죠. 그렇죠?
왜 이런 더셈을 만들었느냐?
그것까지 얘기하면 좀 딥하긴 한데
처음 이러한 연산을 만든 수학자가
앙드레 베요라는 수학자가 있어요.
아 하는 학생 누구예요? 대단한데?
앙드레 베요도 유명한 수학자입니다.
니콜라 부르바키라고 하는 수학자 단체가 있는데
거기의 초대 리더이기도 하고
20세기에 이 수학사에 큰 영향을 끼치신 분이세요.
근데 이 앙드레 베요는 처음에 왜 이런 더셈을 정의를 했느냐?
물론 그때가 1920년대 이때쯤이에요.
그때는 컴퓨터가 있을 때도 아니었고
당연히 암호학이나 이런 거에 쓰일 것을 염두해둔 게 아니고
앙드레 베요는 너무 교과의긴 한데
대수구조에서 군이라는 구조를 만들고 싶었던 거예요.
그게 뭐냐? 우리가 수체계로 했을 때
자연수, 정수 이런 걸 얘기하잖아요.
정수. 정수가 바로 더셈에 대해서 군을 이루는 대수구조에요.
그러니까 이 정수라는 수에 대한 연산을
이 타원곡선에서 점들에 대해서도
똑같은 구조를 만들어줄 수 있다는 것을 베요는 보이고 싶었어요.
그리고 그거를 보인 거예요.
이건 이제 순수수학적으로는 상당히 놀랍고 재미있는 결과였어요.
여기서 말하는 a랑 b가 우리가 말하는 정수
1, 2, 3, 4, 5, 6 이런 거랑 똑같이 대응시킬 수 있네라는 거가
입증이 된 거라서 수학자들은 와 했었죠.
근데 이 결과가 현재는 암호학에 응용이 된 거예요.
수학이라는 건 늘 그렇습니다.
처음 이론이 만들어질 때부터
아 이거 현실을 어떻게 쓰겠다라는 식으로 만들어지기보다는
처음에는 수학자들의 지적 호기심
이렇게 되면 어떻게 될까?
이거를 똑같은 구조로 뭔가 만들어볼 수 없을까?
이런 식으로 연구를 하던 그 이론들이고
그것이 후대에 시간이 지나서 현실에 쓰이게 되는 경우가 많은데
이것도 그런 경우에요.
그래서 하여튼 우리한테 중요한 거는
a랑 b랑 두 개의 점이 있으면
선을 긋고 만나는 점을 대칭시켜서 더셈의 결과라고 합니다.
예시인데요.
타원곡선 y제곱은 x제곱 플러스 1이라는
이게 이제 이 그래프에요.
여러분 실제로 해봐요.
a랑 b라는 점을 내가 0,1 그리고 2,3이라고 했어요.
그러면 방금 방식으로 a 더하기 b라고 하면
이 결과는 몇 콤마 몇이 나올지
지금 계산을 빨리 하는 학생은 상품을 주라고 하겠습니다.
어디? 지금 대답하는 학생.
어 맞아요.
1,0이에요.
오 학생 이름 뭐예요?
맞습니다.
자 어떻게 구분하는지 앞에 봅시다.
일단 a랑 b라는 두 개의 점을요.
있는 그래프 직선을 만들어줘야 되겠죠.
그리고 직선 만드는 거 여러분들이
충분히 고1 학생들도 할 수 있습니다.
그쵸?
직선의 방정식.
그럼 이 방정식을 이제 얘랑 타원곡선이랑 연립하면 돼요.
그럼 대입을 해서 전개를 쭉 하면
x가 이렇게 이렇게 이렇게 나와요.
근데 a랑 b가 지금 x가 0이랑 2였잖아요.
그러니까 0,2는 제외시키고
마이너스 1이 새로운 좌표겠죠.
그쵸?
그럼 마이너스 1을 이제 대입을 해봐요.
그럼 이제 0이 나옵니다.
그쵸?
근데 이제 0은 뒤집어도 마이너스 0도 0이죠.
그렇기 때문에 마이너스 1,0이 나오고
요거 실제로 앞에서 그래프를
요거를 두 개를 이어보면은
정확하게 요 점을 지나가야 될 거예요.
질문 없죠?
쉽죠? 어렵지 않죠?
자, 만약에 더하는 두 개의 점이 일치하면 어떻게 할까?
이 경우에는 앞에 제가 써놓은 것처럼
접선을 그려주면 됩니다.
이게 a 더하기 a를 하고 싶다라고 하는 거예요.
그러면은 이 점에 접선을 긋고서
배칭점을 찾으면 요걸 우리는 ea라고 해주면 돼요.
요것도 선택 미적분화 학생들 몇 명이나 있을까?
선택 미적분화 학생 있어요?
손 들어보세요.
선택 미적분.
손 든 학생들은 할 수 있어야 돼요.
그니까 이 타원 곡선에서
이제 선택 미적분 과목에 있는
음암수의 미분이라는 걸 해주면 됩니다.
y제곱을 미분하면 ey죠.
y에 대해서 미분하면
그게 지금 여기로 갔어요.
그리고 이 우변을 x에 대해서 미분하면
3x제곱 마이너스 1이죠?
그게 여기 위로 갔어요.
그래서 ey분의 3x제곱 마이너스 제곱 1이 dy, dx가 돼요.
그래서 여기에다가 이제 마이너스 1, 1을 대입을 해주면
1이라는 걸 얻고 이게 바로 뭐냐?
접선의 기울기예요.
이제 선택 미적분은 이해되죠?
그래요.
그래서 기울기 1자리이고
이 점을 지나는 직선의 방정식을 만들어주면 되고
그리고 똑같은 방식으로 이 방정식을 열립을 해줘서
우리는 찾아낼 수가 있다라는 거죠.
근데 이거 한번 주의해야 되겠죠?
앞에 봅시다.
마이너스 1 또는 3이 나오는데
3을 여기다 대입을 해봐요.
그러면 5가 되죠?
근데 여기 답은 마이너스 5라고 해야 되겠죠?
왜?
대칭해야 되니까 그렇죠.
훌륭합니다. 잘 따라왔네요.
그렇게 해서 할 수 있고
이게 이제 뭐다?
타원곡선상에서 더셈을 이렇게 한다라는 거예요.
이제 두 번째 연산을 볼 건데
부호를 반전하는 걸 볼 거예요.
어떤 점 a가 주어졌다.
그럼 이 점 a에 대해서 마이너스 a는 대칭해주면 됩니다.
이게 이제 마이너스 a의 값이에요.
어렵지 않죠?
근데 이제 문제는 a랑 마이너스 a를 이렇게 하고 나면
이 둘을 더하면 뭐가 되느냐?
그렇죠? 이 둘을 더하면
실제로 다른 타원곡선의 어느 다른 점이랑 만나지가 않아요.
그렇죠? 만나는 교점이 없죠.
우린 이러한 경우를 뭐라 그러냐?
무한원점 5랑 만났다고 얘기를 해요.
무한원점 5.
무한원점 5라는 것은 관념적인 개념이에요.
이 앞에 있는 이 그래프에서는
이 무한원점 5라는 게 표시되지 않습니다.
다만 이러한 방식처럼
이 둘을 이어 썼을 때 만나는 교차점이 없어요.
그러면 이 둘은 정확하게 0이 되면서
우리는 또 다른 그 교차점을
무한원점이라고 관념적으로 이야기를 하는 거예요.
이 5라는 것은, 이 무한원점 5는
실제로 우리가 정수에서 0 같은 역할을 하는 것이죠.
더했었을 때 플러스만 해서 더하면 0이 되는 것처럼.
질문? 없어요?
그러면 여태까지 내용들을 바탕으로
우리는 어떤 점에 대해서 정수배를 할 수가 있습니다.
앞에 보면 A가 있어요.
우린 그 A에다가 접선 긋고 교차하면 2A를 찾죠.
그러면 A랑 2A를 이어요.
그렇게 해서 만나는 이 점을 대칭해주면 3A를 얻는 것이죠.
그리고 이 3A랑 또 A를 이어요.
그러면 만나는 점을 대칭해주면 4A를 얻는 것이죠.
마찬가지로 5A, 6A, 7A 마음껏 얻을 수 있겠죠.
5A는 어디 있을까?
5A는 여기서 이렇게 있고, 저 밑에서 만나고,
저 위에 생기겠죠.
그러면 이 A에 대해서 우리는 이제 마찬가지로
이런 식으로 마이너스 A, 마이너스 C, 마이너스 3A들도 할 수 있습니다.
A에서 대칭해주면 마이너스 A.
그리고 마이너스 A에서 접선 긋고
만나는 점을 대칭해주면 마이너스 2A.
마이너스 3A를 얻으려면 얘랑 얘랑 있고
만나는 점에서 대칭해주면 마이너스 3A가 되는 거죠.
그래서 우리는 뭐다?
타원곡선 상에 어떠한 점 A를 딱 찍고
그 A에 대한 정수배를 할 수가 있다는 겁니다.
괜찮습니까?
무한원점은 여기 그릴 수 없지만
어떤 관념적으로 일단 약속해놓고
자, 그래서 이제부터 새로운 연산에 대해서 이야기를 해볼건데
사실 말이죠, 방금 봤었던 타원곡선은
앞에 봅시다.
얘는요, 내가 지금 정수 이야기를 했지만
사실 여기 있는 X들은 정수가 아니라 실수죠.
그쵸?
실수.
근데 적어도 암호화학에서는 실수를 다루는 걸 상당히 꺼려해요.
더 크게 말해서 컴퓨터화학에서는.
컴퓨터를 다룰 때는 실수 다루는 거가 상당히 까다롭습니다.
왜 그럴까?
뭐 그런 이유도 있고요.
실수는 기본적으로 무한소수를 상정하죠.
근데 컴퓨터에다 무한소수를 입력할 수 있는가?
0.333333 무한소수는 컴퓨터에 입력할 수 없어요.
그래서 컴퓨터를 적어도 취급할 때는
실수라는 것은 정확하게 그 값을 알 수가 없고
대부분은 근사값을 이용할 수밖에 없습니다.
이해돼요?
근데 암호학에서는 그런 식의 근사값 처리가 상당히 치명적이죠.
왜? 암호학은 정확해야 되거든요.
그렇기 때문에 실수를 다루는 걸 별로 좋아하지 않아요.
그러면 어떻게, 얘는 실수잖아요.
이 실수를 우리가 어떻게 정수로 다시 바꿔주느냐?
거기에 대표적인 연산 방식이 나머지 연산이라는 걸 많이 써요.
영어로는 모듈러 연산이라는 말 정도는 기억해 주면 좋습니다.
한국어로는 이걸 나머지 연산이라고 그러는데
이러한 거예요.
중학교 때 혹시 뭐 수학 올림피아드나 이런 거 준비하는 학생들은
이거 본 적도 있을 거예요.
a를 n으로 나눴었을 때 나머지가 r이다라는 의미예요.
밑에 예시를 보면은 7 모듈러 5를 하면 2입니다.
괜찮아요? 7을 5로 나왔을 때 나머지는 2니까.
그리고 이러한 기호도 이제 많이 씁니다.
얘는 뭐냐면 모듈러 n에 대해서 a랑 b가 합동이다라고 읽어요.
이 3개짜리 등호는 합동이라고 읽어주고요.
이건 뭔 말이냐?
a를 n으로 나눈 나머지와 b를 n으로 나눈 나머지가 같다라는 얘기예요.
그래서 밑에를 보면은 12랑 7은 모듈러 5에 대해서 합동입니다.
나머지가 2니까.
괜찮아요?
근데 이 나머지 연산 자체가 보면은 알겠지만
기본적으로 이 r값으로 나올 수 있는 수가 제한되죠?
그쵸? 나머지라는 거 자체가 n보다 커질 수가 없겠죠?
n 이상이 될 수는 없습니다.
그러면 한 번 더 나눠지게 되니까.
그래서 그 값을 제한하는 성격이 있어요.
그래서 왜 나머지 연산보다는 모듈러 연산이라고 많이 부르느냐?
여담입니다.
나머지는 영어로 뭐죠?
residue.
나머지는 영어로 residue.
근데 residue 연산이라고 안하고 모듈러 연산이라고 하는 이유는
모듈러라는 의미 자체가 수를
모듈러스, 여기 뒤에 있는 n이라는 걸 우리는 모듈러스라고 말해요.
그러니까 제한해주는 수고요.
그리고 모듈러 연산은 그 수를
모듈러스를 기준으로
수를 일정 범위 내로 제한시키는 것이 그 목적이기 때문에
단순히 그 나머지라고 말하는 것은 그 모듈러 연산의 값인 거죠.
근데 그 값 자체가 중요한 게 아니라
얘를 제한시켜주는 그 연산 자체를 더 중요하게 여기는 거예요.
그래서 모듈러 연산이란 말을 더 많이 써요.
자, 넘어갈게요.
나머지 연산의 예를 봅시다.
가는 게 예를 들어서 3 더하기 7 모듈러 4를 한다.
그러면은 10 나누기 4.
그러면 나머지는 2다.
괜찮죠?
3 빼기 7, 자 이거 앞에 보시다.
이런 것부터 조금 이제 재밌죠.
얘는 결과가 마이너스 4예요.
마이너스 4를 6으로 나누면
우린 이걸 이제 뭐라고 해 주느냐?
2라고 해 줘요.
그러니까 기본적으로 이 나머지 값은
의미 아닌 정수를 우리는 뽑아줍니다.
의미 아닌 정수.
근데 마이너스 4는 6에서 마이너스 4만큼 모자라다
라고 생각할 수도 있겠죠?
그래서 2가 나오는 거예요.
3 곱하기 7 하면은 21이죠.
얘는 정확하게 7로 나눠 떨어지기 때문에
값은 0이에요.
자, 이것도 재밌어요.
3 나누기 7은 7분의 3인데
얘를 모듈러 5 하면 뭐라고 해석해야 될까?
밑에 보면은요.
우린 나누기 7을요.
이건 초등학교 때도 배운 내용이죠.
곱하기 7분의 1로 해석할 수가 있습니다.
그쵸?
근데 이거 곱하기 7분의 1이라는 것은
7이랑 결합했었을 때
앞에 보면은 7 곱하기 7분의 1을 해 주면
1이 나오죠.
그쵸?
그럼 1은 모듈러 5 했었을 때 1이 나오잖아요.
근데 이렇게 되게 하는
정수를 찾아주면
7에다가 무언가를 곱했을 때
나머지 1이 나오게 하는
그러한 정수를 찾아주면 3이 되거든요.
7 곱하기 3은 21이고
21에 모듈러 5를 하면 1이 되잖아요.
21 나누기 5 하면
몫이 4고
나머지는 1이니까.
그쵸?
그러니까 바꿔 말해서 뭐해요?
이 나머지 연산, 이 모듈러 연산 안에서는
곱하기 7분의 1을 하는 것은
곱하기 3을 하는 것과 같아요.
괜찮아요?
다 이제 정수로 바꿔줄 수가 있어요.
그래서 밑에 이제 예를 들어서
이게 3 나누기 7 한다.
3 나누기 7은 이제부터
3 나누기 7이 아니라
3 곱하기 3으로 보는 거예요.
나누기 7은 곱하기 3이다.
그래서 3 곱하기 3은 9고
모듈러 5를 하면 4가 나오겠죠.
그래서 이 결과는 4예요.
이거 잘 이해했으면 좋겠네.
이해 안 되면 질문하세요.
다 이해됐어요?
그러면 여기서 문제 하나 또 낼게요.
맞추는 학생은 말씀드리겠습니다.
자, 10분의 1의 모듈러 13을 부해보세요.
가장 먼저 답한 학생에게 선물을 주도록 하겠습니다.
맞아요.
답은 4입니다.
잘 따라와서 뿌듯하네요.
자, 어떻게 하느냐?
우리는 이 10분의 1이라는 걸 어떻게 생각하느냐?
11을 곱했었을 때 1이 나와
나머지가 1이 되게 해야 돼요.
근데 우리 나눠주는 게 뭐냐면
모듈러 수가 13이에요.
근데 13에 곱하기 3을 하면
그러니까 10에다가 4를 곱했었을 때
40이 되면서 39로 나누면 나머지가 1이 되죠.
괜찮아. 13으로 나눠서 나머지가 1이 되는 게 목적인데
10에다가 그럼 뭘 곱해야 되느냐?
4를 곱하면 40되고
39로 나눠주면 빼주면서 1이 나오더라.
그래서 10분의 1은
이 모듈러 13에서는 4랑 같은 값이 됩니다.
자, 그래서 이제 나머지 연산의 특성이라는 걸 제가 여기 써놨죠.
여기서 말하는 앞에 나눠주는 걸 뭐라 그러냐면
모듈러스라고 해요.
제가 이후로 모듈러스라고 하면
나눠지는 값이라고 생각하면 돼요.
한국어로는 이걸 법이라고 번역할 거예요.
개라고 번역하기도 하는데
모듈러스라고 불러줍니다.
그래서 결과를 일정 범위 내에 순환 반복시키는 패턴을 만들어줍니다.
자, 그리고 이제 우리 아까 타원 곡선이라는 걸 봤었죠?
그리고 나머지 연산이라는 걸 봤어요.
이제 이 둘을 결합하면
암호화학에서 쓰는 타원 곡선을 말할 수가 있는 거예요.
그래서 이제 나머지 연산에 적용된 타원 곡선에 대해서 얘기를 해보겠습니다.
흥미진진하죠?
자, 제가 써놓은 것을 앞에 봅시다.
실제 타원 곡선 암호화학에서는
실수라는 것을 다루지 않고
일반적으로 나머지 연산의 결과를 대상으로 한다.
그 이유는 아까 말씀드렸어요.
실수를 대상으로 하기에는
실수라는 것 자체에 무한소수를 입력할 수 없기 때문에
늘 근사값을 얘기할 수밖에 없고
그러면 오차가 생길 수밖에 없어요.
그렇기 때문에 정수로 우린 계산해 주는 걸 원해요.
거기다 추가적으로 정수라고 한다 하더라도
정수를 0에서부터 무한대까지 한다.
그럼 또 어쨌든 무한이 많은 수잖아요.
그렇게 처리하는 것보다 나머지 연산이 강력한 게 뭐예요?
일정 수의 범위로 한정시키죠.
그쵸? 그 결과 값을.
그렇게 무한계의 정수를 다루는 게 아니라
유한계의 정수를 다루게 만들어줄 수 있게 하는 게
바로 나머지 연산의 큰 의의예요.
우린 타원 곡선을 이제 나머지 연산에 이식시킬 건데
이런 식으로 써볼 수가 있습니다.
얘는 이제 어떻게 우리가 해석할 수 있느냐?
이 좌변의 y제곱을 11로 나눈 나머지와
우변의 요거를 11로 나눈 나머지가 서로 같다라고 해석할 수가 있는 거죠.
지금 x에다가 0을 넣었어요.
여기도 0을 넣었어요.
그러면 얘가 1이 나와요.
그 모듈로 11 나면 1이 나와요.
여기도 똑같이 모듈로 11 했을 때 1이 나오게 하려면
얘가 마이너스 1이거나 1이면 돼요.
1인 건 괜찮습니다.
근데 마이너스 1이라는 것은 우리가 의미의 정수니까
얘를 바꿔줄 겁니다.
뭐라고? 10이라고.
왜? 11로 나눴었을 때 마이너스 1이라는 것은
그렇죠, 10이라는 것과 같은 얘기니까.
11에서 1이 모자라다는 얘기니까.
이것도 한번 해봅시다.
이것도 내가 빨리 푸는 학생에게 한번 주도록 하겠습니다.
x랑 y가 모두 의미하는 정수인 타원 곡선
예에서 x가 1일 때 y의 값을 구하는 거.
해보세요.
이 학생에게 내가 선물을 주도록 할게요.
학생 이름 뭐죠?
자, 이거의 답은 플러스 마이너스 5인데
근데 마이너스 5는 6이라고 바꿀 수 있죠.
자, 다시 보면 이 오른쪽은 x가 1이면
얘가 3이 돼요.
그러니까 y에다가 뭘 대입을 해서
정수인 y를 대입을 해서 11로 나왔을 때
나머지가 3이 되느냐는 걸 따져보면
25면 됩니다.
y제곱이.
얘가 왼쪽에 25면 25를 11로 나누면
나누기 11을 하면 몫이 2고 나머지가 3이 나오잖아요.
그러니까 y는 이때 플러스 마이너스 5가 된다.
근데 이제 마이너스 5는 모듈러스 11에서는
6이라고도 바꿀 수가 있는 것이죠.
그래서 결과적으로 1,5랑 1,6
그 두 개의 값이 나오는 거예요.
괜찮습니까?
그래서 이제 이 타원 곡선에 대해서
가능한 모든 값을 다 좌표로 찍어보면 이렇게 나와요.
모듈러스가 11이니까
11인데 끝에는 밑으로 연결이 되죠.
보면 0,1 그리고 0,10 아까 봤었죠 예제로.
그리고 1,5 1,6 방금 한 거예요.
2,0도 되는 거 봅시다.
2를 대입을 하면 11이 딱 나오기 때문에
이때는 나머지가 0이 되겠죠.
그리고 3,3 대칭해서 3,8
4,5 대칭해서 4,6
근데 보다시피 점이 안 찍히는 것도 있어요.
여기가 x가 5인 자리인데
여러분들은 5,1을 대입을 해보면
131이 나와요.
근데 여기서는 y가 0부터 10까지
다 y를 해봐도 맞지 않아요.
그래서 여기서는 아예 좌표가 찍히지가 않습니다.
7도 안 돼요.
여기 9도 안 되고 10도 안 돼요.
그러니까 이게 만약에 말이죠.
이게 항상 좌표들이 다 찍힌다고 하면
상대적으로 이 타원곡선 암호는 쉬워졌을 거예요.
근데 타원곡선 암호가 어려운 이유는
어떤 모듈러스를 택하냐에 따라서
점이 찍히기도 하고 안 찍히기도 해요.
그리고 보다시피 얘는 기본적으로 한 가운데를 중심으로
위아래 대칭 구조를 이루는데
얘처럼 대칭점이 안 찍히는 곳도 있어요.
이런 식으로 막 중구난방이에요.
그렇기 때문에 타원곡선 암호가 어려워지는 거거든요.
컴퓨터가 풀어내기에는
이게 지금 컴퓨터가 암호학에서 쓰는 타원곡선인데
타원 형태도 아니고 곡선도 아닙니다.
하지만 우린 이걸 타원곡선이라고 불러요.
근데 우리 아까 타원곡선에서
더하고 실수배하고 하는 거 했었잖아요.
여기서 똑같이 할 수 있어요.
아까 우리가 직선 그려서 하는 거 했었잖아요.
똑같이 할 수 있어요.
0,1과 얘를 A라고 한다 치고
4,5를 B라고 한다 치면
A 더하기 B를 하면
그러면 여기서 대칭한 이 점
8,2가 A 더하기 B가 결과 값으로 나와요.
5타입니다, 이거.
이거 4,5입니다.
이걸 지난 직선의 방정식은 쉽게 할 수 있죠.
얘를 연립해요, 얘랑.
여기다 넣고 연립해봐요.
그러면 X가 0,4
4는 이제 0이랑 4에다가 하나의 점에다 나올 거예요.
그럼 이 알파에 대해서
이 오른쪽에 얘가 0이고
여기서 4랑 알파가 나올 거잖아요.
그러면 우리는 2차 방정식 근과 개수와의 관계를 써줘서
4랑 알파랑 더한 것은 1이 나와야 되고
마이너스 A분의 B
4랑 A랑 곱한 것은 마이너스 1이 나와야 되겠죠.
근데 마이너스 1은 우리가 모듈로 10일에서는
어떻게 하는지 아까 봤죠.
그렇게 나오게 하는 알파 값을 구하면 8이 나와요.
앞에 봅시다.
8에다가 실제로 4를 더해봐요.
그러면 12죠.
11로 나누면 나머지 1이죠.
8을 4랑 곱해봐요.
32죠.
31을 11로 나누면 1이 모자라죠.
11, 22, 33
33에서 마이너스 1 하면 32가 나오는 거죠.
괜찮아요?
그렇게 해서 우리는 알파라는 게 8이라는 걸 찾았다고요.
그게 지금 정확하게 뭐예요?
얘잖아요.
대칭 이동까지 해줘야 되겠죠.
그럼 여기가 정확하게 A 플러스 B가 된다.
여기서 뭐 이렇게도 해볼까요?
앞에 보면은 0, 10 얘랑 3, 8을 더해봐요.
이렇게 더하면 결과 값은 뭐가 나올까요?
얘랑 얘랑 더하면 여기 부딪히죠?
근데 얘가 값은 아니고
얘를 대칭 이동한 6, 5가 나오는 거죠.
그런데 여기서 재미난 건 뭐냐면
앞에 보면은요.
앞에 집중.
여기서 얘가 모듈러의 연산의 특징이 뭐냐면
수가 커지면은 다시 반복되죠.
순환하게 되거든요.
그러니까 여기서 뭐냐면
0부터 얘가 10하고
사실 위로 올라가면 밑으로 다시 순환하게 돼요.
그러니까 이런 식의 행위가 가능해요.
이런 식으로 내가 0, 1이랑 1, 5를 더하고 싶다.
이 둘에 있는 직선을 그려봐요.
그럼 여기서 끝나죠.
근데 끝나는 게 아니라
사실 밑에서부터 다시 순환한다는 거죠.
이 둘을 잇고 쭉 가면은
여기서 밑으로 와서 순환입니다.
또 밑으로 와서 순환, 또 밑으로 와서 순환
이렇게 되는 거예요.
그래서 이 둘이 지나가는 선을 쭉 이어보면
만나는 점이 있어요.
그럼 이거에서 대칭해주면
얘가 바로 얘 더하기 얘라는 거예요.
이해됐죠? 이게 순환하게 된다라는 거.
자, 심지어 우리는 아까 타공극상 했었던
접선의 방정식도 똑같이 적용할 수 있어요.
가령 예를 들어서
점을 지금 내가 a를 0, 1이라고 해보겠습니다.
그러니까 여기서 앞에 보면 얘는
봐봐요.
이 0, 1에서
여기서 접선을 그린다는 게 웃기잖아요.
아까 타원곡선은 얘는 이렇게 생겨가지고
접선이라는 걸 생각해볼 수가 있었지만
얘는 지금 하나의 따로 떨어진 점인데
여기서 접선을 생각하는 게 어렵잖아요.
근데 우리는 똑같은 방식으로 적용하면 됩니다.
그래서 0, 1에서 일단
우리는 타원곡선 위분을 해요.
음암수 위분을 해서 이렇게 구해주면
얘에다가 0, 1을 대입하면 1분의 1이 나와요.
이게 뭐냐면 접선의 기울기인 거예요.
이게 선택미적분학생은 이해해야 되는 거죠.
그래서 1분의 1이고
그러면 얘를 지나면서 기울기가 1분의 1인
직선의 방정식은 이렇게 만들어주면 돼요.
그러면 이 y는 1분의 1 x 플러스 1을
아까 타원곡선에 연립해서 구할 수도 있고
아니면 얘를 그려볼 수도 있는 거죠.
그러면은 이 점을 지나면서
기울기가 1분의 1인 거 그리면
이게 끝나는 게 아니라
앞으로 와서 만나는 점이 있습니다.
그거를 대칭이동해 준 게 바로 뭐다?
EA라는 거예요.
이 내용은 아마 모를 수 있는데
여기는 여러분들의 선택미적분 내용이라서
여기는 모를 수 있어요.
하지만 이 밑으로는 이해할 수 있어야 돼요.
기울기가 1분의 1이면서
이 점을 지나는 직선의 방정식
그리고 그 직선의 방정식이랑
아까 타원곡선이랑 연립한 거예요.
그 결과 x는 0 또는 4분의 1인데
0은 처음 점이 없었고
4분의 1이 우리의 타깃이고
4분의 1은 모듈러 11에서는
정수 3으로 바꿔줄 수 있습니다.
왜냐하면 4 곱하기 3은 4 3 12
그래서 나머지가 1이 되죠.
근데 이렇게 대수적으로 복잡하게 계산할 것이 아니라
우리는 그냥 접이 평면에서
그래프 쫙쫙 그려서 만나는 점 찾아주면 된다는 거예요.
그래서 우리는 어떤 점 A에 대한
정수배도 마찬가지로 수행할 수가 있는데
특성들을 제가 몇 개 정리를 해볼게요.
이제 나머지 연산을 적용시킨 타원곡선의 특징은
아까 내가 얘기를 한 게 있었어요.
뭐냐면 얘는 아까 봤던 것처럼 5, 7, 9, 10과 같이
그 값이 정의가 되지 않는 그런 곳이 생겨요.
항상 생기는 게 아니에요.
그리고 일반적으로 이 모듈러스의 나누기 이한 5.5 선을 기준으로
얘는 위아래 상하 대칭을 이루는데
이것도 일반적인 게 아니에요.
왜냐하면 2, 0처럼 예외의 점이 있어요.
이런 식의 예외성이 모듈러스를 몇으로 하느냐에 따라서 계속 달라져요.
얘는 모듈러스를 11로 했지만
일반적으로 모듈러스는 소수라는 게 아니라
프라임넘버 11, 13, 17, 19, 23 이런 것들 다 소수들이죠.
일반적으로는 이걸 소수로 잡아줍니다.
왜 소수로 잡느냐를 얘기하려면 좀 복잡해지긴 합니다.
그 개념까지 얘기하려면 유한체에 대한 얘기를 해줘야 되고
유한체의 성질을 이야기해줘야 되는데
너무 고차원적인 얘기기 때문에
그냥 여러분들은 이 모듈러스는 일반적으로 소수로 잡는다
라고만 생각하면 좋겠어요.
그래서 예외성들이 생기기 때문에
그래서 이후로 보게 될 타원곡선상의 이산대수 문제가 어려워지게 됩니다.
이게 이제 핵심이에요.
아까 RSA 암호라는 거 얘기했었잖아요.
RSA 암호가 왜 해독하기가 어려우냐?
어떤 큰 정수를 소인수분해하는 게 어렵다는 문제에서부터
기인하는 거라고 운을 띄웠었죠.
타원곡선 암호가 왜 암호해되기 어려우냐?
타원곡선상의 이산대수 문제가 해결이 어렵기 때문에
암호해되기 어려운 거예요.
그래서 이 타원곡선상의 이산대수 문제
엘립틱 커브 디스크레이트 로가리듐 프로블럼이에요.
그래서 이걸 풀네임으로 부르기 어려우니까
그냥 ECDLP 이렇게 불러줘요.
이게 뭐냐?
그 문제를 핵심을 말하면 뭐냐면
어떤 점, 타원곡선상의 이미의 점
우리는 여태까지 A, B 이렇게 얘기했지만
이제 G라고 얘기를 해줍니다.
어떤 점 G를 찍고
그리고 그것의 X배를 한 X, G가 주어졌다고 해봐요.
이 두 개의 정보를 알아요.
그럼 이 둘의 정보로부터 X를 찾아낼 수 있느냐라는 문제가
바로 ECDLP예요.
다시 G를 알아요, 어떤 점
그리고 이것의 X배를 한 X, G의 점을 알아요.
그 두 개를 알고 있는 상황에서
X를 찾아낼 수 있느냐라는 게 바로 ECDLP입니다.
근데 이 X를 찾는 게 어떻더라?
어렵다라는 거예요.
앞에 봅시다.
처음에 A라는 점, 여기를 G라고 해보겠습니다.
0, 1
그리고 내가 여기를 X, A라고 해볼게요.
6, 6 여기를
그러면 이 X는 몇일까?
구해보자는 거죠.
근데 이게 어렵습니다.
한 번에 찾아내는 게
여러분들이 여기서부터
2, A 만들고 3, A 만들고 해보면
거슬러 올라가면 쉽거든요?
사실 3이에요, 얘는
앞에 봅시다, 앞에 보면
여기서 얘가 2, A였죠?
근데 앞에, 파이팅 집중
여기가 A고 여기가 2, A면
이 둘을 이어주면은 여기서 만나죠.
그쵸?
그럼 여기서 대칭이동하면
여기 6콤마 여기 나오죠.
얘가 바로 3, A예요.
그래서 아까 내가 봤었던 얘가 이제 3입니다.
근데 이렇게 말을 하면 이해가 되지만
그냥 얘랑 얘랑 동그라미 줘놓고
X 구하라고 하면 어렵다라는 거예요.
만약에 여러분들이
이렇게 어떤 점 하나 주고
X, A 딱 줬었을 때
이 X값을 한 번에 찾아낼 수 있는
어떤 공식 같은 걸 만든다.
쉽게 말해서면
그늘 공식 같은 개념이겠죠?
그러한 공식을 만약에 만들어낸다.
이거는 모듈러가 정해지지 않은 상태에서
X를 구하는 걸 좋아하시는 거죠?
이미의 모듈러 쓰면서
그쵸?
이게 이제 뭐다?
수학계의 아직까지 미해결 난제예요.
그래서 이 난제를 바탕으로
암호가 만들어진 거예요.
여러분들 혹시라도
도전해보라 학생이 있으면 한 번 해봐요.
자, 근데 우리가 지금 봤었던
이 앞에까지 봤던 거는
모듈러스가 몇이었느냐?
11이었죠.
그쵸?
당연히 모듈러스가 커지면 커질수록
X를 찾아내는 거는 훨씬 더 어려워지겠죠.
그쵸?
근데 현재 지금 실용적으로 쓰고 있는
타원곡선 암호에서
이 모듈러스는 어느 정도 수준을 쓰고 있느냐?
앞에 써놓은 것처럼
NIST, 내셔널 인스티튜트 오브 스탠다드 앤 테크놀로지
아까예요.
미국의 군익표준기술연구소에서는
커브 PA 521에서는
2의 521제곱빼기 1을 써줘요.
얘가 이제 일반적으로 메르센소수라고 그러죠?
얘를 계산해보면 밑에 있는 것처럼
157자리수예요.
11은 몇 자리수죠?
두 자리, 얘는 몇 자리?
157자리
이 정도의 수를 현재 지금 실용적으로 쓰고 있는 암호입니다.
당연히 G랑 XG 있었을 때
와 이거 찾는 거는
해커들이 그걸 해독하려고 해도
슈퍼컴퓨터 몇 대를 돌린다 하더라도
이거 하려면은 엄청 걸리거든요.
근데 근외공식 같은 걸 찾아낸다?
끝나는 거죠.
자 그래서 지금부터
자 지금부터는
앞에까지 봤던 내용을 바탕으로
우리가 이제 어떠한 식으로
문자메시지나 이런 거 보낼 때
어떻게 암호화가 되는지를 이야기해줄게요.
실용적으로
그래서 제가 예시를 이런 식으로 들었습니다.
있지랑 엠믹스가 서로 통신을 주고받을 거예요.
그리고 에스파는 다른 회사죠.
에스파가 이 통신을
해킹을 하고 있다고 해볼게요.
근데 어떻게 이 정보가 보호될 수 있는가
라는 걸 보시면은
일단 있지랑 엠비스는
그 점 G 타원국선상에서
하나의 점을 서로 일단 주고받아요.
근데 주고받는다는 말은 뭐냐면
통신한다는 얘기고
얘는 에스파한테 걸리게 됩니다.
에스파는 계속 통신을 해킹하고 있는 거예요.
그러면 얘네들이 주고받는 것은
에스파가 알게 돼요.
근데 이제 여기서
있지는 A라는 난수를 준비해
엠빅스도 난수 B를 준비해요.
A랑 B는 서로 주고받지 않아요.
그러니까 있지는 A를 갖고 있고
엠빅스도 B를 갖고 있어요.
근데 이건 서로도 몰라요.
있지도 B를 모르고 엠빅스도 A를 몰라요.
이건 서로 그냥 같이 갖고 있는 거예요.
당연히 에스파도 알 수가 없죠.
근데 이 상황에서 이제
있지가 엠빅스한테
있지는 A라는 게 있었죠.
그리고 G라는 것을 일단 서로 주고받았잖아요.
그러면 G에다가 A 배를 해요.
그럼 A, G 이거를 통신해요.
엠빅스한테
그럼 이 통신화 쓰니까
에스파는 이것도 알게 됩니다.
참고로
참고로 알게 돼요.
그리고 이제 엠빅스는
있지한테 B, G를 통신해요.
이 B, G도 에스파는 알게 됩니다.
자, 근데 지금 재미있는 건 뭐냐면
있지는
있지는 엠빅스한테 B, G를 받았죠.
그러니까 자기는 A를 갖고 있죠.
그러니까 이 A랑 B, G를 곱해요.
그러면 A, B, G를 넣게 되죠.
A, B, G를
엠빅스는 A, G를 받았죠.
B를 갖고 있는 상황에서
그러면 이거 똑같이 B를 곱하면
A, B, G를 또 얻게 돼요.
현재까지
근데 에스파는
A, G를 알고
B, G를 알고
G도 알지만
A, B, G를 알 수가 없다는 거죠.
ECDLP가 얘랑 얘를 안다고 해서
A를 알 수가 없고
얘랑 얘를 안다고 해서
B를 알 수가 없으니까
이거를 뭘로 곱하는지도 알 수가 없는 거죠.
그러니까 에스파는 이 세 개를 다 알지만
A, B, G는 몰라요.
다시 한 번만 설명해 주겠습니다.
처음에 타원곡선에서
어떤 점 G라는 걸 찍어요.
그거는 엠빅스랑 잇지가 서로 주고받습니다.
그러니까 서로 G를 알아요.
이 과정에서 에스파도 G를 알게 돼요.
그리고 이제 잇지는
A라는 수를 준비하고
엠빅스는 B라는 수를 준비해요.
이제 그러고서
이 잇지는 A랑 G를 곱한 것을 전송해요.
그리고 엠빅스는
이렇게
그러면 그 과정에서 에스파는
A, G랑 B, G를 중간에 해킹해서 알게 돼요.
그럼 이제 이 상태에서
잇지는 B, G를 전송받은 것을 A를 곱해요.
그러면 A, B, G를 최종적으로 얻어요.
엠빅스는 이제 A, G 전송받은 걸 가지고
B를 곱해서 A, B, G를 또 마찬가지로 얻어내요.
괜찮죠?
그러면 A, B, G라는 정보를
잇지랑 엠빅스는 알게 되지만
에스파는 A, B, G를 알 수가 없어요.
왜?
ECDAP때문에
괜찮습니까?
어, 이해됐습니까?
그래서
자, 이제
여러분들이 문자메시지 카톡 같은 걸 주고받을 때 어떻게 하느냐
잇지는요
이 M이라는 거는 이제 문자메시지 같은 걸 생각하면 돼요.
이 M에다가 A, B, G를 더한 것을 전송합니다.
M에다가
이 메시지에다가 A, B, G를 더한 것을 전송을 하고
그리고 엠빅스는
이 수신한 M 더하기 A, B, G에서
A, B, G를 알고 있으니까 빼줘요.
그러면 고스란히 M을 얻을 수 있는 거죠.
하지만 에스파는
M 더하기 A, B, G를 알아요.
이거는 해킹해서 알아낼 수 있어요.
하지만 A, B, G를 모르기 때문에
결국 M을 알아낼 수가 없어요.
이해됩니까?
아주 지극히 실용적으로 쓰이고 있는 과모의 예시입니다, 지금.
지금까지가 이제 뭐다?
타원곡선
여러분들이 한 번도 아마 들어보지 못했을 개념일텐데
시작해서 실용적인 예시까지
제가 쭉 설명을 한 겁니다.
질문 있으면 하세요.
