퀀텀 컴터와 RSA에 관해서(암호관련입니다)..

  • #99936
    타고난혀 38.***.222.120 2846

    저는 도통 모르겟네요..

    밑에, 썬 서울님께서 주신 글 잘봤습니다, 웃으면서 한편 생각하길.. 공부 좀 해야겟다란 생각을 다시 하게끔 만듭니다.. 정말 머리가 무거워지는 이유가 돌이 점점 sign up을 해서가 아닌가 란 생각을 하고 있습니다.

    일전에 생각 했던것 중 하나가 만약 원자 세계의 단위에 1과 0을 씌워서 그걸 읽을수 있게 된다면, 1 테라 바이트가 얼마 단위의 걸로 줄어 들까란 생각을 해봤습니다.

    공상 과학 이야기로,

    간단하게 1개의 깨지지 않는 matter 안에 proton이 6.02 * 10^23개 있다고 가정을 하면요.

    1000,000,000,000 byte 1 byte가 8개의 1 과 0 으로 구분된다고 보면, 총
    8000,000,000,000 bits가 1테라 바이트의 구성 요소가 아닌가 합니다

    위의 것과 비교 하면요.

    602,000,000,000,000,000,000,000 개의 원자가 1g안에 존재 한다는것인데요. 이걸 1과 0으로 씌어 버리게 되면.. 1테라 정도는 껌딱지가 아닌가 하는 생각이 듭니다.

    근데 문제는 과연 이러한 것처럼 1과 0을 씌운 원자를 얼마나 효율적으로 읽을수 있는 장치를 만들까 궁금합니다.(저는 이게 1과 0또는 blind상태를 어떻게 기록할수 있나 궁금합니다)

    또 ㅋㅝㅁ텀 컴터 이야기 하면 꼭 암호를 깨는 방식에 관해서 이야기가 나오는데, 암호를 어떻게 깨는것일까요??

    말은 바로 해야 하는게, 현재 운용되는 암호화 방식을 생각 해 보면, 깨진다는 표현 보다는 때려 맞춰서 소가 뒷걸을 질 쳐서 쥐잡는것과 비슷하다고 표현하는게 정확하지 않나 봅니다.

    저는 똑똑하신 분들은 소 뒷걸음 질 치는 범위를 상당히 효율적으로 줄이시는 분들로 생각 하고 있습니다.. 예를 들어서 바로 쥐가 튀어나올 위치을 예상해서 소를 바로 앞에 배치 시킬수 있는 분들..또 뒷걸음 질로 쥐를 밟을 확률을 0% 가깝게 만드시는 분들이 진짜 ‘천재’들이 아니신가 하고 생각하고 있습니다..

    퀀텀 컴터 이야기 하면 RSA로 이야기가 많이 나오는데요. RSA의 핵심은 소인수 분해에 있다고 봅니다.

    결국 2개의 수를 통해서 곱을 구한후, 서로 하나의 수로 다른 하나의 수를 구하는건 일도 아니지만, 단순히 곱의 결과 만으로는 2개의 소수를 유추 하기가 쉽지 않다고 생각 하고 있사옵니다… 또 소수 특성까지 고려하면 이건 이야기가 또 달라지지 않나 합니다. (근데 소수의 곱은 다시 소수가 맞지요??)

    근데 만약 두소수의 곱이 8943895622347074358734895794357938759837594 이런식으로 나간다면, 슈퍼 컴터도 계산하다 토할꺼라 생각 합니다.

    이 점을 이용해서 RSA가 뜬거라 생각하고 있는데요,

    또 RSA 연산이기에 시간이 좀 걸립니다.그래서 2중 암호를 선택합니다. 즉 RSA로 DES란 ‘암호키’를 포장하는건데요..

    RSA를 풀어도 안에 있는 DES란게 3중 으로 철통 보안 되어 있으면, 이건 또다른 이야기가 됩니다.

    근데, 이 퀀텀 컴터가 어떻게 이 RSA와 70개의 키 조합이 튀어나온다는 DES를 쉽게 깰수 있는것인건가요?

    일전에 어느 분이 DES를 1994년에 인터넷을 통한 분산 시스템을 이용해서 10조개 근처로 풀은적이 있습니다..이경우 최대한 많은 암호가 될수 잇는 문자를 조합해서 넣는 시도를 효율적으로 처리해서 풀은경우가 될지 싶은데요…

    퀀텀이 RSA를 쉽게 푼다 해도.. 만약 RSA의 키 값을 올려서 결국 자릿수를 기존의 것보다 수십배 올려 버리면 과연 퀀텀이 이것역시 풀을수 있는건지요??

    • 내속탄다 68.***.4.232

      수박은 칼을 들고 ‘잘라’ 먹어야 그 맛을 알 수 있는데 참. 잡지만 무성하게 읽어대시는 듯.

    • gonfly 71.***.210.232

      타고난혀님은 전산학보다 수학과쪽에 더 적성이 맞는듯 하네요..^^; 알고리듬 책보면 NP문제가 나오는데 조금 더 파보시면 세계에서 7대 수학 난제라고 하던가 그런게 있는데 그쪽도 한번 공부해보시면 타고난혀님에게 재미있을듯하네요. 어쨋든 이런거 하는 아들 보면 다 수학과 아들이 정말 잘 하는것 같더군요..

    • 타고난혀 38.***.222.120

      저는 개인적으로 NP문제 갖고 이걸 풀어야 한다면서 이론적으로 넘어가시는 고수들을 보면 내공이 딸라서 그런지 좀 이해할 엄두를 못내겠습니다.

      위 암호중 하나는 70조개의 숫자를 대입시켜서 풀어 버리는건데..저는 70조도 거의 NP개념이라고 생각 했었습니다.(한국 있을때 펜ㅌㅕㅁ 급 3대 4일간 돌려도 답 안나오던것중 하나 였습니다.)

      이게 현재 잘나가는 기계 성능을 기반으로 70조를 계산 하는게 시간이 오래 걸리기에 사용되는거지, 과학의 발달로 1분안에 70조의 키조합을 만드는 기계가 튀나오면, 다시 700조의 키조합을 이용하는 암호를 만들면 되지 않나 생각 하고 있사옵니다.

      즉 NP문제라고 지칭되는 문제들은 아직 컴터의 성능문제(계산상의 시간)때문에 NP로 분류가 된거라고 생각하고 있는게몇개 있습니다. 예로 100년 전 사람들의 NP범위가 현재의 NP범위와 사뭇 다를꺼라 생각 하고 있습니다.

      퀀텀역시 RSA의 소인수 분해를 엄청 빨리 한다고 하지만, 만약 다시 범위가 늘어나 버리면 이게 또 새로운 개념의 컴터를 개발해야 하는건가요??

      저는 퀀텀 컴터가 현재 쓰이는 컴터보다 개념상 훨씬 빠르다는데, 어떻게해서 빨라질까가 궁금합니다.. 암호 풀어 버리는건, 새로운 개념에 따라 같이 올라오는 option이 아닐까 생각 중입니다.

      곤플라이님// 제가 수학이 적성에 맞다고 말씀 하시는걸 살짝 돌려서 표현하면…

      ‘타이슨은 축구선수가 되었어야되’ 라고 말씀하시는것과 동급이라고 감–휘~ 표현 합니다.

      (참고로 세계 7대 난제같은걸 풀수 있는 분 계시면, .. 돈줘서라도 대화 한번 갖어 보고 싶은 바램이 있습니다..뇌구조가 어떻게 되시길래..저런것에 도전장을 디미실수 있는지 말이지요.)

    • gonfly 71.***.210.232

      존 내쉬다 라는 분은 게임이론에서 비협력 게임 분야를 개척하신분인데 뷰리플 마인드의 실제 주인공 모델이죠. 영화에서 보면 제 기억으론 비둘기를 행동을 보고 그 행동을 수학공식으로 만들려고 하던게 생각나네요. 일단 알고리즘쪽으로 마음이 기우신다면 당연히 수학을 잘 해야 할것 같네요. 이론적으로 아무리 문제를 풀었다고 하더라도 수학적으로 공식화해서 설명하지 못하면 완성된 이론이 아니라고 하더군요(수학교수의 말에 의하면)..일단 NP문제는 현재 존재하는 가장 우수한 슈퍼컴퓨터를 가지고도 경우의수를 계산해서 보면 엄청난 시간이 걸리기에 풀수없는 거라고 할수 있겟죠. 타고남혀님 말대로 정말로 슈퍼 울트라 메가 컴퓨터가 개발되면 그 시간을 단축시킬수 있을지도 모르니 그때가선 NP문제라고 할수가 없겠지요. 하지만 몇초안에 문제가 풀려야 하는데 위의 슈퍼 울트라 메가 컴퓨터가 한달안에 풀수 있다면 그것또한 당장 실용성은 없을 듯 하네요. 어쨋든 에니메이션중에 공각기동대 시리즈 중에 하나를 보면 인간이 전뇌화를 한후에 인간끼리 네트워크를 구성할수있다고 되어 있는데 만약 이런게 현실화된다면 충분히 위의 문제를 한순간에 풀수 있을거라고 생각되네요.
      근데 공각기동대 시즌3는 단편 하나 나오곤 나선 시리즈가 왜 안나오나 모르겠네요. 정말 공각기동대의 스토리를 보면 정말 미래에 전뇌화가 가능하게 되면 인간은 평생 살수 있을거 같은데 정말 흥미로운 이야기인거 같기도 하면서 약간 무서워 지기도 하네요.
      이야기가 딴곳으로 흘러서 죄송합니다. ㅎㅎ..^^;

    • gonfly 71.***.210.232

      아 그리고 NP문제에 대해서 기억나는것이 문제를 풀었다 해도 그게 정말 정답인지 그걸 증명해야 하는게 또 힘들더군요. 예를 들어 무지 복잡한 데이터에서 최대값을 구하는 문제가 있을경우 일단 어떤 최적의 알고리즘을 이용해서 답을 구해도 이게 정말 최대값인지 수학적으로 증명이 되어야 인정이 된다고 하더군요. 근데 그게 너무 힘들어서 최대값을 구해도 이게 정말 최대값이진 알수 없기에 NP문제다라는게 제가 기억나는 대목이네요..^^; 횡설수설이었습니다. 케엑..ㅡ,ㅡ;

    • 타고난혀 38.***.222.120

      곤플라이님//저는 뇌를 0과 1로 표현할수 있는 세상이 오기를 바라지 않는 인간적인 컴터 공학도 입니다. 삽결살에 친구들과 쏘주 마시는 장면이 0과 1로 표현이 된다고 생각 하니 간이 시꺼멓게 타들어가는 기분입니다.

    • 타고난혀 38.***.222.120

      이야기가 NP로 흘러가는데, 뭐 제 글에는 주제도 없고, 방향도 없는 난잡함이기때문에, 그냥 흘려서 이야기를 드리고 싶습니다요.

      컴터로 표현할수 없는 문제가 NP라고 규정을 짓고 예를 들자면, 반경 2키로 터지는 폭탄이 있는데, 높이 10M까지 그리고 반경 2KM내에 퍼지는 열을 10^-9cm3단위의 사각형으로 표현을 하라고 하는 순간, 이건 NP로 넘어 갑니다.

      예를 들어서 점점 단위가 적어져서 사각형의 크기가 더 줄어든다면, 10^-23cm3의 단위로 갈수록 메모리의 한계에 부딪히고 표현할수가 없어집니다.

      요게 NP로 갈리는 척도가 아닌가 합니다, 즉 환경적인 요소때문에 한계를 알수 없는 문제들, 이러한건 과학이 발달하면 많이 줄어들꺼란 생각을 하고 있습니다.

      자연수의 3승을 99999999999999999999999999999999999 자리까리 구하라 라고 하면 현재 슈퍼 컴터로도 한참 거릴꺼란 생각이 듭니다, 근데 만약 어떤 matter를 개발됐고, 열을1도씨 올릴때마다 원자의 움직이는 속도가 3승단위로 증가할경우,걸리는 시간은

      현재 컴터의 계산 방식 같은수 3번 곱하기와 다르게 한번의 측정으로 이뤄지지 않을까 생각 합니다.

      그럼 슈퍼 컴터에서 NP로 분류가 될똥 말똥한 문제들이 NP범위에서 없어지지 않을까 생각 하고 있습니다..즉 NP문제들중 풀리지 않는것들은 현재 과학 수준에 비례해서 올라간게 아닌가 하고 혼자서 생각 중입니다..

      근데 퀀텀이 NP를 다 없애줄순 없겟지요??

    • duke 24.***.123.126

      타고난혀님, 내속탄다님의 말씀이 이해가 가시는지요?

      직접 프로그램을 작성하시고, 단지 64비트 소수 두개의 곱을 구한다음, 두개의 소인수로 분해해 보세요.

      왜? 그런 알고리즘이 아직도 쓰이고 있을까를 알게 됩니다.

      프로그래머를 꿈꾸는 사람들은, 수학만으로 많은 것들을 풀어대던 아인슈타인과는 다른 종족일 것입니다.

      간단히.. 한권의 프로그래밍 연습책의 연습문제 어느것이라도 펼치면서, 코딩방법이 생각날정도의 경험이 우선필요합니다.

      영민한 머리가 있으면 되는것이 아니겠느냐고 생각하시지만, 다른이들은 즉답이 나올것을 생각하는 시간이 필요하다하면, 밥줄이 오락가락 합니다.

    • duke 24.***.123.126

      아, 대답을 빠뜨렸습니다.
      예. 퀀텀은 RSA암호화 키의 크기와 관계없이 풀어낼 수 있다는 것입니다.

    • 타고난혀 38.***.222.120

      >>직접 프로그램을 작성하시고, 단지 64비트 소수 두개의 곱을 구한다음, 두개의 소인수로 분해해 보세요.

      이걸 꼭 해봐야 하는건가요?? 그럼 제가 해본 잡다한 헛삽질을 알려드려야 하는건가 싶네요..

      >>영민한 머리가 있으면 되는것이 아니겠느냐고 생각하시지만, 다른이들은 즉답이 나올것을 생각하는 시간이 필요하다하면, 밥줄이 오락가락 합니다.

      저는 ‘영민한 머리’관련 부분은 생각도 하지 않는 사람인데요, 무슨 말씀 하시는것인건가요??

      어떻게 퀀텀이 RSA 암호화 키를 크기와 상관없이 풀어 낼수 있는건가요?? 제가 개인적으로 파고 있는 부분역시 how입니다.

    • duke 24.***.123.126

      타고난혀님, 사과요. 정정합니다.
      말의 표현이 잘못 되었습니다.
      – 영민한 머리가 있으면 되는것이 아니겠느냐고 “생각하실지 모르겠지만”.
      이어야 할 말 이었습니다.

    • 타고난혀 38.***.222.120

      듀크님//저는 말 꼬투리 잡는건 관심이 없습니다. 단지, 쓸때 없는 assumption이 몇개 있으신것 같아서 ,그 부분에 관해서 잠시 언급했을 뿐입니다.

      다시 본론으로 가서, 듀크님의 말씀 하신 부분중, 키의 크기와 관계 없이 풀어낼수 있다고 하셨는데..

      RSA역시, 원리는 다 공개된 상태 입니다, 즉 키의 크기와 상관없이 풀수 있습니다. 단지 걸리는 시간이 현존하는 컴터의 경우 수억년 걸리게 만들어 버렸을 뿐입니다.

      즉 위의 퀀텀이나 클래식 컴터나 둘다 비슷하게 키의 크기와 상관없이 풀수 있습니다. 정작 답을 안달아 주신것중 하나가, 어떻게, 빠르게 풀어낼수 있냐라는 부분입니다.

      >>간단히.. 한권의 프로그래밍 연습책의 연습문제 어느것이라도 펼치면서, 코딩방법이 생각날정도의 경험이 우선필요합니다.

      백번 맞는 말씀 입니다. 개인적인 입장에서 코딩방법의 경험보다 컴터 란 놈이 어떻게 0과 1로 굴러가며, 퀀텀 컴터가 1과0 그리고 중간 상태를 표현해서 패러다임을 바꿀수 있나가 궁금한것이지요.

    • 타고난혀 38.***.222.120

      듀크님 덕분에 간만에 암호공부좀 다시 해봤습니다. 그리고 위의 64비트 소수 2개 곱한다음에 소인수 분해 하라는건, 농담이시죠?? 참고로 64비트면 8바이트고 1바이트당 숫자 하나이미, 총 8 digit수의 소수 2개를 곱한후, 그걸 소인수 분해 시키라는것인데..

      10513*14323 대략 이렇게 5자리수만 해도 벅찹니다.

      대략 듀크님역시, 암호 모듈을 보셨다란 가정하에 질문을 드리겠습니다. 나름대로 양자컴터에 휘발유를 뿌리신 Shor님의 알고리듬의 핵심은 주기를 찾아내는데 있습니다.

      즉 100자리 소수든 뭐든, 임의의 수 x에 a승의 값을 구한후, 그 주기 r을 통해서, (x (r/2) +1)(x (r/2)-1)/N=0 이걸 풀어 버립니다.

      여기서 N은 큰 소수, 공개키입니다.

      즉 GCD(x (r/2) +1,N)과 GCD(x (r/2) -1,N)을 해버리면 마지막에 소인수분해되서 떨어지는 놈들이 고약한 2개의 암호 소수 라는것인데요.

      듀크님께서 말씀 하신바로면, 키의 크기와 상관없이 빨리 풀수 있다고 하셨는데, 어떻게 빨리 풀을수 있는건지요??

      삽질한걸 보여드리자면..shor의 알고리듬의 핵심은 주기를 찾아낸후 그 주기 만큼 의 승의 값을 빨리 구해 버리며는게 관건입니다.

      202356th 2 first remainder is 2

      x를 2로 잡고 (2의 202356 승 + 1)(2의 202356 승 – 1)/N=0을 계산해야 합니다.
      6273036th 3 first remainder is 3 이건 3의 6273036 승 +1 ,-1을 구해야 합니다.

      101178th 4 first remainder is 4 이건 4의 101178승 +1 -1을 구해야 합니다.

      8364048th 5 first remainder is 5 이건 5의8364048+1 -1을 구해야 합니다.

      위의 숫자 모두 계산을 해버리면 소인수 분해가 되버리더군요. 수학이란게 참 웃긴것 같습니다.

      듀크님 말씀대로, 키의 크기와 상관이 없다고 하셨는데, 저는 5자리 소수 2개를 곱한 값이 150,577,699 이렇게 되네요

      참고로 현재 존재하는 RSA에 쓰이는 키값중 소인수 분해된 최근 버전은 100자리수 2개 입니다. 즉 200자리 수가 독일 security관련된 국가기관에서 풀은건데요..

      양자 컴터가 이걸 어떻게 빨리 풀수 있는걸까요?

    • . 71.***.81.1

      NP 개념을 기본적으로 잘못 알고 계신것 같아서 적습니다.
      현재 컴퓨터로 너무 오래 걸려서 NP가 아닙니다. 쉽게 얘기드리면, 기준이 되는 데이터 셋의 개수가 증가함에 따라, 이를 해결하는데 걸리는 시간이 기하급수적으로 증가하는 문제가 NP입니다. 아무리 빠른 컴퓨터가 나와도 NP는 NP인 겁니다.