티스토리 뷰
보안에 수학에 적용되다
금요일, 세계에서 가장 유명한 암호학자가 널 리 사용되는 컴퓨터 칩에 수학적 오류가 있어서 전 세 계 전자상거래 시스템을 위험에 빠뜨릴 수 있다고 경 고했댜 이스라엘 바이츠만 연구소의 아디 샤미르 교수는 그 문제를 언급한 연구 기록을 일부 동료들에게 배포 했다 연구 기록에는 현대 마이크로프로세서 칩의 복 잡도가 날로 증가하면서 탐지되지 않는 오류가 발생 할 가능성을 피할 수 없다는 내용이 들어 있었댜 박사 는 과거에 그런 위험이 실제 발생한 사례로 1994년 인 텔사 펜티엄 마이크로프로세서에서 나눗셈 오류가 발 견된 사건, 그리고 더 최근에는 마이크로소프트의 스 프레드시트 프로그램인 엑셀에서 곱셈 오류가 발견된 사건을들었다 미묘한 수학 오류가 존재하면 공격자는 공개키 암 호화라는 대증적인 기술로 보호된 전자 메시지의 일 부를 깨뜨릴 수 있댜 공개키 암호화 방식은 공개된 숫 자를 사용해서 메시지를 암호화하고 혼자만 알고 있 는 비밀 숫자로 암호를 푸는 것이다. 이 기술을 사용하 면 모르는 사람끼리 안전하게 정보를 교환할 수 있어 서 다양한 종류의 전자 거래에 기반 기술로 사용되고 있다고 합니다.
또한 샤미르 박사는 정보기관 사람들이 보편적으로 사용 되는 컴퓨터 칩에서 오류를 찾아낸다면, 그 칩이 내장 된 PC의 보안 소프트웨어는 ‘메시지를 단 한 번만 가 로채도 쉽게 깨뜨릴 수 있다’고 말했다 또한 보안 소 프트웨어를 공격할 때 필요한 것이라고는 컴퓨터에 존재하는 수학적 결함에 대한 지식, 그리고 공격 대상 컴퓨터에 ‘독이 른 암호화 메시지를 보낼 수 있는 능 력뿐이라고 했다 그러면 공격 대상 컴퓨터에서 사용 하는 비밀키 값을 계산할 수 있다 샤미르 박사는 이 방법으로 “각 컴퓨터의 운영환경 을 일일이 조작할 필요 없이 수백만 대의 PC를 동시에공격할 수 있다"고 썼다 암호 전문가들은 샤미르 박사 의 글이 매우 증요하다고 말했는데, 그 이유는 해커로 부터 전자상거래를 보호하는 데 널리 사용되는 RSA 공개키 알고리즘을 설계할 때 샤미르 박사가 그와 관 련된 역할을 담당했기 때문이라고 합니다.
한편 벨기에 루뱅 가톨릭대학의 암호학자 장자크 키스쿼 테Jean-Jacques Quisquater 교수는 “이 연구 기록에서 놀라운 점은 아디 샤미르 교수가 RSA에도 취약한 부 분이 있다고 밝힌 겁니다"라고 말했다. RSA 알고리즘 에서 S는 바로 샤미르 박사를 의미한다. 박사는 로널 드 리베스트 교수, 레너드 애들먼 교수와 함께 1977년 RSA 알고리즘을 만들었댜 샤미르 박사는 연구 기록에서 마이크로프로세서 칩 의 정확한 작동방식은 기업 비밀에 관한 법률로 보호 받기 때문에, 정확하게 설계되었는지 확인하기가 완 전히 볼가능할 정도는 아니라도 매우 어려운 게 사실 이라고 기록했다 또한 “인텔에서 펜티엄 오류 문제로 교훈을 얻어 마이크로프로세서의 곱셈 회로를 꼼꼼하 게 확인했다고 해도, 인텔만큼 꼼꼼하게 설계하지 않 았을 것 같은 소규모 마이크로프로세서 제조사들도 많다”고말했다고합니다.
미국 샌프란시스코에 있는 컨설팅 및 설계 회사인 크립 토그래피 리서치의 폴 코커 대 표는 많은 암호 전문가가 샤미르 박사가 언급한 문제 를 예전부터 심도 있게 연구하고 있다고 말했댜 그리 고 그걸 보면 아무리 보안이 강력해도 작은 결함에 무 너질수있다는말도했다 인텔의 대변인 조지 앨프스는 그 결함이 이론적인 것이며 실제 생기려면 우연이 아주 많이 일어나야 한 다고 말했댜 그러면서 “지적해주셔서 감사하고 모든 경우의 수를 살펴보겠다”라는 말도 덧붙였다. 연구 기록을 보낸 후 샤미르 박사는 이메일을 통해 자신이 언급한 방식으로 실제 공격을 감행한 사람이 있다는 증거는 갖고 있지 않다고 말했다. 세계 컴퓨터학회에서 발행하는 학술지 <세계 컴퓨 터학회 커뮤니케이션Communications of the Association of Computing Machinery>9월호에 실 린 머 리기사가 인터넷에 게재되자, 블과 이틀 만에 평소의 10배가 넘는 독자들이 기사를 내려받으면서 지난달 독특한논란이발생했습니다.
그 기사의 주제는란 이론 컴퓨터과학과 복잡도 이론 분 야의 중요한 문제 해결에(별로 없어 보이긴 하지만) 진전 이 있는지 설문조사를 한 것이다. 그 문제는 좀 더 어 려운 이름으로는 'p vs NP' 문제라고 하는데, 컴퓨터 삽에 들어가는 트랜지스터 설계를 최적화한다거나 컵 퓨터 암호를 깨는 등 현실 세계의 문제와 연관이 있다. 과거 ‘페르마의 마지막 정리’ 같은 수학 난제처럼 이 문제에도 엄청난 상금이 걸려 있다 그 중에서도 10여 년 전 클레이수학연구소에서 에베레스트 산에 오르는 것처럼 어려운 7개의 빌레니엄 문제Millennium Problems'를 제시하고 문제를 푸는 사람에게 주겠다며 내걸었던 100만 달러의 상금이 가장 크다 지금까지는 상금에 가까이 다가간 사람이 아무도 없는 것 같다 가장 간단하게 설명하자면(그렇다고 가장 이해하기 쉽다는 말은 아니다) P vs NP 문제를 푼다는 것 은 P와 NP가 같은지 다른지 알아내는 것이다. P는 다 항시간 내에, 그러니까 합리적인 수준에서 빠르게 ‘폴’ 수 있는 유형의 문제를 말한다 NP는 다항시간 내에 ‘검증'할 수 있는 유형의 문제를 말한다. P= NP를 증 명할 수 있다면 세상은 완전히 다른 곳으로 바뀔지도 모른댜 P vs NP 문제는 ‘출장 중인 외판원 문제(정해진 제약 조건 안에서 여러 도시를 지나가는 가장 효율적인 경로를 계 산하는 문제)'같은 컴퓨터과학의 고전 문제를 연구하는 사람들에게 매우 중요하다고 합니다.
가장 큰 수를 인수분해 하는 것도 NP 문제로 거론되는 대표적인 사례댜 다항시간 내에 큰 수를 인수분해 할 수 있다고 널리 인정된 방법 은 아직 없지만, 답이 제시되었을 때 그 답이 맞는지 검증하는것은쉽댜 컴퓨터 칩에 들어가는 트랜지스터를 가장 효율적으 로 설계하는 일은 NP 문제로 거론되는 또 다른 사례 댜 P vs NP 문제의 매력은 그 문제를 해결했을 때 기 대할 수 있는 명성이나 상금 외에도, 만일 P가 NP와 같다는 것을 실제로 증명할 수 있다면 컴퓨터 연산에 서 가장 어려운 문제의 일부가 풀릴 가능성이 있다는 것이다 그렇게 되면 경제적 • 기술적으로 생산성이 폭발적으로 늘어나게 된다. 출장 중인 외판원’ 문제처럼 위에서 언급한 문제는 모두 문제의 크기가 커질수록, 그러니까 외판원이 방 문해야 할 도시나 칩에 들어가는 트랜지스터가 하나 더 많아지면, 문제를 푸는 데 필요한 컴퓨터 연산 시간 이 기하급수적으로 증가한다 방문할 도시가 하나 더 많아지면 문제는 10배가 어려워지는 것이라고 합니다.
또한 어떤 해 법이 정확한지 검증하기는 쉽지만, 아주 커다란 문제 에 최적의 해법을 찾기는 매우 어렵다 캘리포니아주 멘로파크에 있는 연구집단 SRI 인터내셔널의 컴퓨터과학연구소장 패트릭 링컨Patrick Lincoln은 "많은 수 재들이 이 문제를 폴려고 했지만, 그 문제를 풀 수 없 다는 것조차 증명하지 못했다”고 말했다. <세계 컴퓨터학회 커뮤니케이션>의 편집자들은 직 접 쓴 기사가 화제가 되어 무척 기쁘다고 했다. 편집장 인 라이스대학 컴퓨터 과학자 모셰 Y. 바르디Moshe Y. Vardi 박사는 이렇게 말했다. "발행하자마자 이렇게 폭 발적인 반응을 보인 기사는 이번이 처음인 것 같다. 이 메일 계정이 완전히 폭발해버렸다. 많은 사람이 기사 롤 클릭하지 않고는 못 배기는 것 같았다." 기사를 쓴 주인공인 노스웨스턴대학 매코믹 공과대 학의 랜스 포트나우Lance Fortnow 교수는 처음에 바 르디 박사에게 기사가 그리 길지 않을 거라고 말했었 댜 그 문제의 진척 상황에 관한 기사를 쓰면서 포트나 우 교수가 처음 썼던 말은 ‘문제가 아직 완전히 해결되 지 않았다'였다 포트나우 교수 말로는 아직은 실낱같 은 희망이 남아 있다고 한다. 1971년 토론토대학의 컴 퓨터 과학자 스티븐 A. 쿡Stephen A. Cook 교수가 대 수기하학이라는 난해한 수학 분야에서 P = NP를 증 경하거나 P ~ NP를 증명하는 방법을 제시할지도 모 른다는 딸을 처음 간략하게 언급한 적이 있기 때문입니다.