티스토리 뷰
큰수를 나누는 연구 과학에 발전을 가져오다
어느 수백 명이 모인 한 수학자 모임에서 1,000여 대의 컴퓨터를 사용하여 155자리 숫자를 더 나누어지지 않 는 3개의 작은 수로 나눈 일은 1년 전만 해도 불가능해 보였던 수학계의 위업이다. 그 155자리 숫자는 다른 수학자들이 같은 방식으로 나수 있다고 발표했던 그 어떤 숫자보다도 대략 50 자리가 더 길었으므로 해당 수학분야에서는 대단한 성과였다. 암호 전문가들은 어제 그 성과가 은행이나 다른 기 관에서 비밀자료를 암호화하여 전송하는 암호체계에 사상 처음으로 심각한 위협을 줄 가능성이 있다고 말 했댜 은행 같은 기관에서 사용하는 암호체계의 기술 적 기반은 아주 큰 수가 쉽게 인수분해되지 않는다거 나 더 나누어지지 않는 수(소수)들로 쉽게 나눌 수 없 다는 것이다. 예를 들어, 10의 인수는 2와 5이다. 아르옌 렌스트라 박사는 이번 일이 은행 같은 기관 의 암호화 시스템에서 실제 사용하는 크기의 숫자가 인수분해 된 최초의 사례라고 말했다 그는 뉴저지주 모리스타운에 있는 벨 시내전화회사의 연구조직인 벨 코어 주식회사의 프로젝트 책임자다. 이번 작업을 위해 수학자들은 아주 큰 숫자를 각각 7, 49, 99자리의 더 작은 숫자 3개로 나누기 위해 새 로운 방법을 찾아야 했습니다..
지금까지 사용했던 방법으 로는 그 작업을 감당할 수 없었기 때문이다. 렌스트라 박사는 1년 전만 해도 누군가 155자리 숫자를 인수분 해 할 수 있느냐고 물었다면 ‘‘불가능하다고 말했을 것 이다"라고했댜 뉴저지주 머리 힐에 있는 AT&T 벨연구소의 수학자 앤드루 오들리츠코 박사는 ‘‘이건 정말 엄청난 성과다컴퓨터 정수론 관점에서 보면 정말 획기적인 돌파구 가 열린 것”이라고 말했댜 그 155자리 숫자는 그동안 수학자들 사이에서 인수 분해하기 어려운 난제로 유명했다. 100자리 수 인수 분해에 처음 성공한 것은 1988년 10월이었다 수학계 에서는 대략 숫자 10자리가 늘어나면 그 숫자를 인수 분해 하는 컴퓨터의 성능은 10배가 필요하다고 본다. 지금까지만 해도 인수분해 기법의 발전 속도는 한 번 에 대략 10자리 이내였다. 하지만 전문가들은 그 성과가 현실적으로 중요한 영향을 미치는 곳은 암호 분야라고 말했다. 1977년 수 학자 3명으로 구성된 연구팀이 인수분해에 기반한 수 학 공식에 따라 메시지를 뒤섞는 암호화 방법을 만들 었다. 그리고 현재 그 암호화 방법은 은행 거래는 물론 국방부의 보안통신에도 사용되고 있다고합니다..
이러한 암호화 방법에서는 먼저 메시지의 문자열을 숫 자로 바꾼 다음, 그 숫자를 자체적으로 여러 번 곱해서원래 메시지를 알아낼 수 없을 정도의 큰 숫자로 만든 댜 그리고 그 큰 숫자를 인수가 공개되지 않은 조금 작은 수로 나눈다 나누고 남은 나머지, 그러니까 남은 숫자가 바로 암호화된 메시지다. 암호화된 메시지는 암호화 과정에서 큰 수를 나눌 때 사용한 조금 작은 수 의 인수를 아는 사람만 해독할 수 있다. 이런 암호를 만들면서 공학자들은 메시지를 뒤섞을 때 사용할 숫자를 선택하게 되는데, 이때 균형을 아주 절묘하게 맞춰야 한다. 인수분해가 쉬운 숫자를 선택 하면 암호문이 해독될 위험이 있고, 인수분해가 훨씬 어려운 아주 큰 숫자를 선택하면 메시지를 뒤섞는 계 산을 할 때 훨씬 오래 걸린다 뉴멕시코주 앨버커키에 있는 샌디아국립연구소의 선임연구원이며 국방부에 안전한 암호화 방법을 조언 하는 거스 사이먼스Gus Simmons 박사의 말로는 국가 안보를 제외한 대부분의 분야에서 암호 전문가들은 대략 150자리 숫자를 키로 사용한다고 한다. 예전에 100자리 숫자의 인수분해 프로젝트를 이끈 적 있는 렌스트라 박사는 "실제 사용하는 암호 기법의 영역에 사상 처음으로 발을 들이게 된 것이라고 했습니다.
다시 언급 해서 암호 기법의 안전을 보장할 수 없게 된 것이다." 라고말했다 렌스트라 박사와 동료들은 예전에 본인들이 인수분 해 했던 숫자의 수학적 구조가 조금 특별했다는 특징 이 있긴 하지만, 그때 사용했던 인수분해 방법을 수정 하면 더 많은 분야에 적용할 수 있다고 말한다. 하지만 좀 더 신중한 태도를 보이는 사람들도 있다. 사이먼스 박사는 그 방법을 보편적으로 사용할 수 있 다는 것에는 동의하지만, 현실에서 사용할 수 있을 만 큼 다른 수도 빠르게 인수분해 할 수 있는지 보기 위해 기다리는 중이다 사이먼스 박사는 그 방법 때문에 ‘‘암 호 전문가들의 걱정이 커질 수도 있지만, 얼마나 효과 적인가에 따라 상황은 달라질 수 있다”고 말했다. 사이먼스 박사는 그렇긴 해도 이제는 150자리 숫자 를 써도 안전하다고 마음 편히 조언하기는 어렵게 되 었다고 말했다 "국가기밀이 150자리 숫자 뒤에 숨겨 져 있는데, 그 숫자가 인수분해 될 수 있는 상황이 아 주 가까워지고 있는 것이다 더 큰 숫자를 사용하라고정부에 건의하겠느냐고? 당연하다.,, 새롭게 인수분해 된 수는 ‘인수분해 10대 난제’라는 목록에서 가장 큰 숫자였다 목록에는 인수분해 전문 가들에게 난제로 자리 잡은 큰 숫자들이 들어 있다 워 낙 큰 숫자들이기 때문에 수학적으로 특별한 비법이 없다면 인수분해 할 엄두도 내지 못한다. 캘리포니아주 팰로앨토에 있는 디지털 이퀼먼트 코 퍼레이션 시스템연구소의 마크 머내시 박사의 말로는 초당 10억 번의 나눗셈을 할 수 있는 컴퓨터로, 쉽게 나수 있을 것 같은 작은 숫자를 일일이 대입하는 방 법을 써서 그 155자리 큰 수를 인수분해 하면 '10의 60제곱’ 년이 걸린다고 합니다.
이것은 10 뒤에 0이 59개 있는 숫자다 하지만 새로 발견된 인수분해법으로 전 세계 에서 공동작업하면 몇달만에플어낼수있다 새로운 인수분해 방법은 지난해 영국 레딩에 사는 존 폴라드와 UC 버클리의 헨드릭 렌스트라 주니어 박 사가 발견했댜 헨드릭 렌스트라 박사는 아르옌 렌스 트라 박사와 형제지간이다. 두 수학자는 일부러 인수 분해가 어려운 큰 수를 여러 개 고른 다음, 그 큰 수들 의 구조에 잘 맞는 특별한 형태의 인수를 찾는 손쉬운 방법을알아냈다 당시 머내시 박사와 아르옌 렌스트라 박사는 인수 분해 작업을 도와줄 컴퓨터 과학자와 수학자들을 전 세계에서 모집했다 작업을 돕겠다고 지원한 사람들 은 문제의 일부를 자신의 컴퓨터에서 수행할 수 있도 록 특정 프로그램을 내려받았다. 머내시 박사는 그 작업을 아주 커다랗고 삐뚤빼뚤 한 직소 퍼즐을 푸는 것에 비유했댜 각 컴퓨터에 할당 된 수학 작업은 약 5천만 개의 퍼즐 조각이 있는 퍼즐 상자를 자세히 살펴보는 것과 맞먹는댜 아르옌 렌스 트라 박사는 이렇게 말했댜 “그 안에는 퍼즐 조각처럼 보이지만 실제로는 아닌 쓸모없는 온갖 잡동사니도 들어 있다. 사람들마다 상자에 들어 있는 진짜 퍼즐 조 각을 찾아야 한다 어떤 상자에는 퍼즐 조각이 하나도없을 수 있고 어떤 상자에는 한두 개밖에 없을 수도 있 댜" 한 달 정도 지나서 학자들은 대략 250만 개의 퍼즐 조각에 해당하는 작업 결과를 수거했습니다.
이어 탐색 작업의 속도를 높이고 조각들을 모아 숫자를 인수분 해 하기 위해 플로리다대학의 강력한 컴퓨터를 이용 했다. 작업을 3시간 만에 끝낼 수 있는 성능의 컴퓨터 였다. 현재 인수분해 기록 중에서 가장 획기적인 것은 수 학자들의 숨을 맞게 했던 수많은 뛰어난 성과 중에서 도 가장 최근의 기록이다 1971년에 수학A~은 40자 리 숫자를 인수분해 했다 그리고 10년 전만 해도 so 자리 숫자의 인수분해는 거의 불가능한 것으로 여겨 졌다 그 뒤로 연구가 발전하고 예상하지 못한 방법이 등장하면서 60자리, 70자리, 80자리 숫자가 인수분 해 되었댜 100자리 숫자가 인수분해 된 것은 1년 6개 월전이었댜 이스라엘 과학자 두 사람이 강력한 수학 기법을 개 발했다 수많은 기업에서 극비 정보를 암호화할 때 사 용하는 암호 시스템을 특정 조건에서 깨뜨릴 수 있는 기법이며 최초입니다.
다른 전문가들은 그 기법을 사용한 공격이 당장 위협이 되지는 않을 것이라고 말하지만, 정부 표준 암호화 시 스템인 ‘데이터 암호화 표준(Data Encryption Standard, DES)'을 사용하는 기업의 방어막에 커다란 구멍이 뚫 릴것으로본댜 DES로 암호화하는 정보는 보통 최첨단 제품의 설계, 석유나 기타 에너지 비축량에 관한 자료, 금융거래 기록 등이다 이런 정보가 컴퓨터 간에 자주 전송되는 만큼 조작이나 도난에 취약하다고 말하는 정부 관리 들의 우려가 갈수록 커지고 있다. MIT 컴퓨터 과학자이자 암호 전문가인 로널드 리 베스트 교수는 DES가 ‘‘구식 기술이라는 것이 분명해 졌으므로 앞으로 몇 년간 대안을 생각해야 한다”고 말 했c~. 수학 기법을 개발한 당사자인 이스라엘 과학자 아 디 샤미르와 일라이 바이행Eli Biham은 아직 연구결과 롤 공식 발표하지 않았다. 샤미르 박사가 최근 몇몇 미 국 동료들에게 이매일로 알렸을 뿐이다 두 사람이 개 발한 새로운 기법은 엄청난 양의 통계 표본에 존재하 는 미세한 차이를 체계적으로 활용한다고 합니다.