암호학에 대한 질문 하나 드립니다

athxue의 이미지

현재 쓰이는 암호화 방식중에 공개키-비밀키 방식이 있다고 들었습니다.
공개키로 암호화하면 비밀키로 복호화 하는 형태인데 이때 공개키는 공개
해도 상관없이 없을정도로 비밀키를 알아내기 위한 연산이 많다고 들었습니다.
그렇다면 공개키로 암호화된 정보를 해독하는 쪽은 비밀키를 가지고 있어야
하는데 이 방식과 단순한 비밀키 방식이 어떤 차이점이 있는지 궁굼합니다.
약간 혼동되었던게 단순한 비밀키도 결국에는 상대방에게 키를 전해주어야
하고 공개키-비밀키 방식도 비밀키를 상대에게 전달해주어야 하는것이
아닌가요?

밑에 댓글로 질문을 하나 더 달아놨습니다.
만약 C언어에서 이 방식을 사용한다면 큰 두 소수를 이용하여 제곱 연산을
하게 되지 않나요? 그런데 C언어에서 그렇게 큰 값을 저장할만한 자료형이 있나요?
아니면 자료형을 문자열로 해야 하나요?

moonend의 이미지

앨리스는 '밥에게 보내는 공개키'와 '앨리스의 메시지를 해독하기 위한 비밀키'를 가지고 있으며,
밥은 '앨리스에게 보내는 공개키'와 '밥의 메시지를 해독하기 위한 비밀키'를 가지고 있습니다.

비밀키를 주고받는 형식일 때에는 하나의 암호 시스템만으로 운영이 가능합니다.
[이렇게 운영하면 안됩니다만, 구성은 할 수 있습니다]
공개키를 이용하는 방식에서는 메시지의 교류를 위해서는 두개의 암호 시스템이 독립적으로 운영되어야 합니다.
공개키 암호화 방식은 단방향으로 이루어지는 메시지 암호화 방법입니다.

이를 위해서 쓰이는 방식이 소수를 이용한 소인수 분해 방식입니다.
수 n이 어떤 소수 a,b의 조합인지 알아내려면 1부터 n까지의 숫자를 하나씩 대입해보아야 합니다.

예를 들자면, 91이라는 숫자를 뿌립니다.
숫자는 작지만, 컴퓨터식으로 알아내려면 1부터 시작해서 일일히 나누어보는 수밖에 없습니다.
91이 어떤 두 소수의 곱인지 알려고 하면 일일히 계산하는 방법밖에 없습니다.
지구상의 누구라도, 어떤 두 소수의 곱이 91이라는 값을 내는지 알기 위해서는 똑같은 과정을 거쳐야 합니다.

그래서 은행 거래에 있어서는 10의 308제곱 이상의 숫자를 사용합니다.
이 정도 자리수의 소인수를 찾으려면 1억대의 컴퓨터가 1000년 정도 계산을 해야합니다.
[펜티엄 100mhz 기준]

cypher의 이미지

예전에 봤던 책에 좋은 비유가 있었습니다.

A에게 개인 자물쇠 a가 있고, B에게도 개인 자물쇠 b가 있습니다.
그리고 A와 B 두명 모두 가지고 있는 공개 자물쇠 c가 있습니다.

A가 B에게 편지를 보내려고 합니다. A는 편지를 상자에 넣고 개인 자물쇠 a로 잠그고,
공개 자물쇠 c로 한번 더 잠급니다. 상자는 a와 c로 잠겨져 있고, 이 상태로 B에게 보냅니다.
B는 상자를 받아서 자신의 개인 자물쇠 b로 잠급니다. 그리고 다시 a,b,c 세 개의 자물쇠가
채워진 상자를 A에게 보냅니다. 상자를 받은 A는 자신의 개인 자물쇠 a를 열고 B에게
돌려보냅니다. 이제 B가 받은 상자에는 자물쇠 b,c 만 채워져 있습니다. 자신의 개인키와
공개키를 이용해서 열면 되죠.

이 상황에서 A와 B는 개인키를 주고받은적이 없지만,
공개키만으로도 상자의 내용은 안전하게 전달되었습니다.

moonend의 이미지

사이먼 싱의 '코드 북'이라는 책이 있는데, 일종의 필독서입니다.
지금까지 읽어본 책 중에서 가장 쉬운 편에 속합니다.

jiee의 이미지

그렇다면 공개키로 암호화된 정보를 해독하는 쪽은 비밀키를 가지고 있어야
하는데 이 방식과 단순한 비밀키 방식이 어떤 차이점이 있는지 궁굼합니다.

=> 님께서 말씀하신 용어로 차이를 설명하자면,
내가 단순히 비밀키로 암호화해서 보내고 상대방에서 동일한 비밀키로 복호화하는 방법은 중간에 해커가 비밀키를 가로채 복호화해 내용을 확인할수 있습니다. 왜냐하면. 같은 비밀키를 상대에게 전달해줘야 하기 때문입니다.
하지만, 공개키로 암호화하고 비밀키로 복호화하는 방법은 중간에 해커가 가로채도 복호화할 수 없습니다. 왜냐하면, 공개키로 암호화되어 있는 내용을 보려면 비밀키가 필요한데 이는 실제 사용자만 가지고 있기 때문입니다.

약간 혼동되었던게 단순한 비밀키도 결국에는 상대방에게 키를 전해주어야
하고 공개키-비밀키 방식도 비밀키를 상대에게 전달해주어야 하는것이
아닌가요?

=> 단순 비밀키방식은 님께서 말씀하신데로 상대방에게도 키를 전달해줘야합니다. 하지만 공개키-비밀키 방식일 경우 상대에게 비밀키를 전달하지 않습니다. 왜냐하면, 상대방은 내 공개키로 암호화해 보내고 내가 그것을 받았을 때는 내 비밀키로 복호화하기 때문입니다. 내가 보낼때는 상대방의 공개키로 암호화하고 상대방이 그것을 그의 비밀키로 복호화하는 방식입니다.
즉, 중간에 공개키는 돌아다녀도 비밀키는 항시 자신에게만 존재하는 것이지요. 아마 RSA가 이런 방법의 암호화 알고리즘일겁니다.

이상이 제가 기억하는 바입니다. 좀 되어서 기억이 흐릿한데 대체로 맞을 겁니다. 틀리면 다른 분이 지적해주시겠죠..ㅎㅎ

그럼, 즐거운 주말되세요~~

토나오게...

lacovnk의 이미지

키를 한번에 두개 생성합니다. keyA와 keyB라고 하지요. 이 두 키는 다음과 같은 성질을 갖고 있습니다. 중요합니다.

1. 내용을 keyA로 암호화한 것은, keyB로만 풀 수 있습니다.
2. 거꾸로, 내용을 keyB로 암호화한 것은 keyA로만 풀 수 있습니다.

갑이 보내고 을이 받을 때, 비밀이 보장되려면, 을만 풀 수 있어야 합니다. 어떻게 하면 될까요?

1. 을은 keyA를 공개해버립니다. 모두가 을의 keyA를 공개키로 알게 됩니다.
2. 그리고 갑은 keyA를 이용해 자신의 메시지를 암호화하고, 을에게 보냅니다.

이 메시지는 keyB로만 풀 수 있는데, 을은 이 keyB를 꽁꽁 숨겨뒀습니다. 중간에 누가 가로채더라도 풀 수가 없습니다. 비밀이 보장되었군요! :)

참고로, 이를 거꾸로 사용해서, 서명을 확인하는 데 이용할 수 있습니다. 을이 자신의 비밀키, keyB를 이용해 암호화해서 뿌렸다고 칩시다. 이를 을의 공개키 keyA로 복호화해서 확인할 수 있습니다. 즉, "다른 사람이 아닌 을 본인"임을 확인하는 데 사용되는 것입니다.

ㅡ,.ㅡ;;의 이미지

그런데 항상이게 궁금..해었죠..
keyA 로 암호화한것은 keyA가 있다면 그암호를 풀수도 있지 않을까요..?


----------------------------------------------------------------------------

lacovnk의 이미지

그렇지 않은 알고리즘입니다.. 이전까지 쓰던 key의 개념과 다른 것이지요.

여는 열쇠와 잠그는 열쇠가 다른 것입니다 :)

jiee의 이미지

http://ko.wikipedia.org/wiki/RSA 이 사이트 참고하시면 될 것 같네요. :)

토나오게...

ㅡ,.ㅡ;;의 이미지

그렇군요..

그런데 또 한가지 잡생각이드네요..

소인수분해가 불가능하게 하기위해서는 매우큰수를 이용해야하는데...

그렇다면... A는 매우큰 두소인수를 찾아야하는 과제도 생기는데..

예를들어 천자리숫자를 만들기위해 500자리소수 2개를 생성해야하는데..

A가 힘들거라는...
만일 이걸 빠르게 하는만큼(자릿수를줄인다던가..) 소인수분해도 그만큼빠르게 할수 있지 않을까하는...
예를들어 테이블을 이용한다던가..


----------------------------------------------------------------------------

kane의 이미지

키는 한번만 생성하면 되기 때문에 별 문제는 아닙니다. 그리고 임의의 큰 수를 생성하고 소수 여부만을 판단하면 되기 때문에, 소인수분해와는 비교되지 않을만큼 간단한 과정인 걸로 알고 있습니다. 소인수분해를 어렵게 할려고 자리수를 늘린 건데 키 생성을 빨리하자고 도로 줄이지는 않겠죠? ^^;

ㅡ,.ㅡ;;의 이미지

x(임의의 매우큰수)

A의 입장 x를 생성하고 소수인지 아닌지 판별 즉,소인수분해가 가능한가 아닌가를 판별해야되는거아닌가요..

어차피 소인수분해해야될꺼같은데..
물론 A는 B보다 반정도되는 두수를 소인수분해하면되고..
B는 A보다 두배정도자리수가큰 하나의수를 소인수분해해야
암호를풀수있다는결론인거 같은데...


----------------------------------------------------------------------------

kane의 이미지

소인수분해를 하는 것과 소인수분해가 '가능'한지를 판별하는 일이 다른 난이도를 가집니다. 굳이 소인수분해를 안해봐도 소수인지 알 수 있다는 거죠.

다만, 소수 여부를 완전히 판별할 수 있는 알고리즘이 없어서 확률에 의존한 방법을 썼다고 알고 있습니다. 그래도 매우 믿을만한 방법이라고 알고 있습니다. 그리고 몇년 전에 인도 수학자가 소수 여부를 완전히 판별할 수 있는 알고리즘을 만들었다는 소식을 들었는데, 그 후로 어떤 변화가 있었는지는 모르겠습니다. 이 인도 수학자 얘기는 KLDP에서도 찾아보면 있을 겁니다.

athxue의 이미지

아주 큰 두 소수를 가지고 연산을 한다고 들었습니다. 그렇다면 그 값을 저장할만한 자료형은
long형 밖에 없는데 이렇게 큰 값이 저장될 수 있나요?

jiee의 이미지

큰 수 계산할 때,
저는 배열에 큰 수를 저장해서 계산하는 방식을 사용합니다.
예를 들어,
char bigint1[1000] = {"123337348684658456....39473874"}; //1000자리 숫자
char bigint2[1000] = {"388298923933434344....33893989"}; //다른 1000자리
char result[1000]; // 결과를 담을 큰 수.
result = bigint1 + bigint2;
(여기서 =, +연산자는 c++에서 연산자 오버로딩으로 적절히 구현했다고 가정합니다. C경우에는 함수로 구현해야겠죠. 예를 들어, AddBigInt(bigint1, bigint2, result)와 같이)

이렇게 배열에 저장되어 있는 숫자를 계산하는 방식입니다.
구현하는 건 bigint로 검색하면 나올 듯 합니다.

c++이나 java같은 경우 bigint클래스가 있었던 걸로 기억되는데..-_-a

그런데 이런 방식이 암호화에 쓰이는 큰 소수계산에 사용되는지는 잘 모르겠네요..

토나오게...

eminency의 이미지

제가 아는게 암호화 알고리즘에도 적용되는 지는 모르겠지만...
큰 소수를 이용한 알고리즘은 그 곱셈 결과를 이용하는 것이 아니라 나머지를 이용하는 것으로 압니다.
나머지만 알면 된다면 굳이 큰 수를 저장할 자료형은 필요하지 않지요.

(a^100) mod b

(((a * a) mod b) *a) mod b ....

와 같은 결과입니다.

노루가 사냥꾼의 손에서 벗어나는 것 같이, 새가 그물치는 자의 손에서 벗어나는 것 같이 스스로 구원하라 -잠언 6:5

jiee의 이미지

보안 관련 책 찾아보니까 RSA의 경우,
공개키와 비밀키를 일반적으로 1024비트나 2048비트짜리로 사용한다는군요.

그리고, 질문자께 도움이 될만한...
http://ko.wikipedia.org/wiki/RSA
http://en.wikipedia.org/wiki/RSA

토나오게...

IsExist의 이미지

공개키는 (e, n) 개인키는 (d, n) 입니다. RSA 공개키 방식을 널리 사용한 곳은 PGP 입니다.

이 공개키에 소유자 정보 + alpha + 제3자의 신뢰기관의 서명을 더해서 X.509 인증서
(요즘 전자상거래나 인터넷 뱅킹시 사용하는 공인인증서)라는걸 만들었습니다.

인증서에는 (e,n)이 들어 가있고 실제로 인증서 패스워드라고 하는건 개인키를 암호화할때
사용하는 건데 실제 개인키 파일은 (e,n,d,p-1,q-1,etc) 데이타로 구성됩니다.

---------
간디가 말한 우리를 파괴시키는 7가지 요소

첫째, 노동 없는 부(富)/둘째, 양심 없는 쾌락
셋째, 인격 없는 지! 식/넷째, 윤리 없는 비지니스

이익추구를 위해서라면..

다섯째, 인성(人性)없는 과학
여섯째, 희생 없는 종교/일곱째, 신념 없는 정치

---------
간디가 말한 우리를 파괴시키는 7가지 요소

첫째, 노동 없는 부(富)/둘째, 양심 없는 쾌락
셋째, 인격 없는 지! 식/넷째, 윤리 없는 비지니스

이익추구를 위해서라면..

다섯째, 인성(人性)없는 과학
여섯째, 희생 없는 종교/일곱째, 신념 없는 정치

mithrandir의 이미지

큰 수를 다루기 위한 라이브러리가 있습니다.

쉽게 접할 수 있는것으로는 gnump가 있겠군요. openssl소스 내부에도 있고, 암호화 라이브러리라면 자체구현이든 외부구현이든 사용할테니 찾아보시면 될겁니다.

언제나 삽질 - http://tisphie.net/typo/
프로그래밍 언어 개발 - http://langdev.net

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.