[보안] 암호화 알고리즘

by Blogger 하얀쿠아
2012. 7. 18. 13:31 소프트웨어 Note/Algorithm

DES (Data Encryption Standard) ; 데이터 암호 표준


 DES는 개인키를 사용하여 데이터를 암호화하는 방법으로서 널리 사용되며, 미국 정부는 이 알고리즘을 해독하기 어렵다고 판정하고 다른 나라들에 수출하는 것을 금지하고 있다. DES에는 72,000,000,000,000,000 (72천조)개 이상의 암호 키가 사용되는 것이 가능하다. 주어진 각 메시지를 위한 키는, 이렇게 막대한 량의 키 중에서 무작위로 선택된다. 다른 개인키 암호화 방법과 마찬가지로, 송신자와 수신자 둘 모두는 동일한 개인키를 알고, 사용해야만 한다.


 DES는 각 64 비트 데이터 블록에, 56 비트 길이의 키를 적용한다. 이 과정은 여러 가지 모드에서 실행될 수 있으며, 16번의 연산이 수반된다. 비록 DES가 강력한 암호화이라고 판단되고는 있지만, 많은 회사들은 세 개의 키가 잇달아 적용되는 "트리플 DES"를 사용한다. 그렇다고 해서 DES로 암호화된 메시지가 해독될 수 없다고 말하는 것은 아니다. 1997년 초에, 다른 암호화 방식의 소유자인 RSA가 DES 메시지 해독에 10,000 달러의 상금을 걸었다. 인터넷상에서 14,000명 이상의 사용자들이 다양한 키들을 시험하는 공동 노력으로 결국 그 메시지를 해독하였는데, 가능한 72천조 개의 키 중에서 고작 18천조 개의 시험을 통해 그 키가 발견되었다. 그러나, 오늘날 DES 암호화로 발송되는 것 중, 이러한 종류의 코드 해독 노력에 영향을 받을 것 같은 메시지는 거의 없다.


 DES는 1977년에 IBM에서 발명하였으며, 미국 국방부에 의해 채택되었다. 이것은 ANSI X3.92와 X3.106 표준 및 미국 연방정부 FIPS 46과 81 표준에 정의되어 있다. 이 암호화 알고리즘이 비우호적인 국가에 의해 사용될 수 있다는 염려 때문에, 미국 정부는 암호화 소프트웨어의 수출을 막고 있다. 그러나, 이 소프트웨어의 프리버전은 BBS나 웹사이트 등에서 어렵잖게 입수할 수 있다. 이 암호화 알고리즘이 깨지지 않고 비교적 오래 남아있을 것이라는 일부 관심이 있지만, NIST는 DES를 대체하기 위한 새로운 표준이나 대안에 관한 작업이 진행중이므로 DES를 다시 인증하는 일은 없을 것이라고 지적했다. 그후 2001년에 DES를 대체하는 표준으로 AES (Advanced Encryption Standard)가 선정되었다.


AES (advanced encryption standard) ; 고급 암호 표준


 AES는, 민감하지만 비밀로 분류되지는 않은 자료들에 대해 보안을 유지하기 위해 미국 정부기관들이 사용하는 암호화 알고리즘이며, 그에 따라 민간 부문의 상업 거래용으로서 사실상의 암호화 표준으로 자리 잡을 것으로 보인다 (미군이나 그밖에 극비로 분류된 통신은 별도의 비밀 알고리즘에 의해 암호화된다).


1997년 1월에, 기존의 데이터 암호 표준, 즉 DES를 대체할 보다 강력한 알고리즘을 찾기 위한 공모 작업이 미국 상무부의 한 기관인 표준기술연구소(NIST)에 의해 시작되었다. 새로운 알고리즘이 충족해야 할 규격 요건으로는, 최소 128 비트나 192 비트 또는 256 비트 크기의 키를 지원하는 128 비트 크기의 블록 암호화를 사용한 대칭형 (암호화나 복호화를 하는데 동일한 키가 사용되는) 알고리즘으로서, 전 세계적으로 로열티 없이 사용할 수 있어야 하며, 향후 20년~30년 동안 데이터를 보호하기 위해 충분한 정도의 보안성을 제공할 것이 요구되었다. 또한, 이 알고리즘은 스마트카드 등과 같은 제한된 환경을 포함하여 하드웨어나 소프트웨어로 구현하기 쉬워야 했으며, 다양한 공격 기술에 대해서도 잘 방어할 수 있어야 했다.


전반적인 선정 과정은 대중적 조사와 평가에 완전히 공개되었으며, 이러한 투명성으로 인해 제출된 모든 설계안들에 대해 최적의 분석이 가능하였다. 1998년에 NIST는 미국 안보국을 포함, 세계의 암호화 단체에 의해 기본적인 분석을 받게 될 15개의 AES 후보작을 선정하였다. 여기에 기반을 두고 1999년 8월, NIST는 보다 심도 있는 2차 분석을 받게 될 다음의 5개 알고리즘을 선정하였다.


MARS: IBM 연구소 제출

RC6: RSA Security 제출

Rijndael: 두 명의 벨기에 암호학자 Joan Daemen와 Vincent Rijmen 공동 제출

Serpent: Ross Andersen, Eli Biham 그리고 Lars Knudsen의 공동 제출

Twofish: Counterpane의 존경받는 암호학자 Bruce Schneier를 비롯한 대규모 연구팀 제출


 

위의 다섯 개 알고리즘은 모두 ANSI C와 자바 언어를 이용, 하드웨어와 소프트웨어 중심의 시스템 모두에서, 암호화와 복호화 속도 측정, 키와 알고리즘 설정 시간, 다양한 공격에 대한 저항성 등과 같은 심도 있는 시험을 거쳤다. 그 후, 이들 알고리즘은 새로운 암호화 체계를 깨보고자 자원하는 일부 팀을 포함 세계적인 암호화 단체들에 의해 다시 한번, 자세한 분석이 이루어졌다. 그 결과, 2000년 10월 2일에 NIST는 Rijndael를 표준안으로 최종 선정하였다. 2001년 12월 6일, 미 상무부 장관은 민감하지만 비밀로 분류되지 않은 모든 문서들에 AES로서 Rijndael을 사용할 것을 규정하는 연방 정보처리 표준, 즉 FIPS 197을 공식 승인하였다.


RSA (Rivest-Shamir-Adleman)


 RSA는 1977년에 Ron Rivest, Adi Shamir와 Leonard Adleman에 의해 개발된 알고리즘을 사용하는 인터넷 암호화 및 인증 시스템이다. RSA 알고리즘은 가장 보편적으로 사용되는 암호화 및 인증 알고리즘으로서, 넷스케이프와 마이크로소프트 웹브라우저 기능의 일부로 포함된다. 이것은 또한 로터스 노츠, 인튜잇의 Quicken 등 많은 제품에 채용되어 있기도 하다. 이 암호화 시스템의 소유권은 RSA Security라는 회사가 가지고 있다. 이 회사는 알고리즘 기술들을 라이선스 해주고, 또 개발도구 등을 판매하기도 한다. 이 기술들은 기존에 이미 나와있거나 제안되어 있는 웹, 인터넷 및 컴퓨팅 표준들의 일부를 이루고 있다.


RSA 시스템의 동작원리


공개키와 개인키의 획득에 사용되는 알고리즘의 상세한 수학적 설명은 RSA 웹사이트에서 찾아볼 수 있다. 간단히 말해, 이 알고리즘은 두 개의 큰 소수 (소수는 그 숫자와 1로만 나누어지는 수이다)들의 곱과, 추가 연산을 통해 하나는 공개키를 구성하고 또하나는 개인키를 구성하는데 사용되는 두 세트의 수 체계를 유도하는 작업이 수반된다. 한번 그 키들이 만들어지면, 원래의 소수는 더 이상 중요하지 않으며, 버릴 수 있다. 공개 및 개인키 둘 모두는 암호화/복호화를 위해 필요하지만, 오직 개인키의 소유자만이 그것을 알 필요가 있다. RSA 시스템을 사용하면, 개인키는 절대로 인터넷을 통해 보내지지 않는다.


개인키는 공개키에 의해 암호화된 텍스트를 복호화하는데 사용된다. 그러므로, 내가 만약 누군가에게 메시지를 보내는 상황을 가정해 보면, 나는 중앙의 관리자로부터 수신자의 공개키를 찾은 다음, 그 공개키를 사용하여 보내는 메시지를 암호화할 수 있다. 수신자는 그것을 받아서, 자신의 개인키로 복호화하면 된다. 프라이버시를 확실하게 하기 위해 메시지를 암호화하는 것 외에도, 자신의 개인키를 사용하여 디지털 서명을 암호화해서 함께 보냄으로써, 그 메시지가 틀림없이 바로 당신에게서 온 것임을 받는 사람에게 확신시켜줄 수 있다. 메시지를 받은 사람은, 발신자의 공개키를 이용해 메시지를 복호화할 수 있다. 아래의 표가 이러한 과정을 이해하는데 도움을 줄 수 있을 것이다.



구 분누구의 어떤 키를 사용하나?
암호화된 메시지를 보냄수신자의 공개키
암호화된 서명을 보냄발신자의 개인키
암호화된 메시지를 복호화수신자의 개인키
암호화된 서명 (발신자 인증) 을 복호화발신자의 공개키

이 댓글을 비밀 댓글로

10진수를 2진수로 변환하는 알고리즘 (또다른 방법)

by Blogger 하얀쿠아
2011. 7. 22. 16:25 소프트웨어 Note/Algorithm

10진수를 2진수로 변환하는 알고리즘 (또다른 방법)

우선 몇자리의 2진수를 만들것인지를 알아내거나 제시한다.

그리고, 기본적인 아래의 규칙 하나만 기억한다.

rule : 작으면 0 / 크거나 같으면 1


예를 들어보겠다. 10진수 600 10자리의 2진수로 만들 경우를 생각해보자.

10자리의 2진수로 만들 것이므로, 2의 10승 = 1024 부터 시작한다.

그 후, 2의 9승, 2의 8승... 2의 1승까지 차례로 rule대로 비교해 내려간다.

아래의 과정으로 간단하게 만들 수 있다.

600 이 1024보다 작으므로 0
600이 512보다 크거나 같으므로 1, 그리고 600 - 512 = 88
88이 256보다 작으므로 0
88이 128보다 작으므로 0
88이 64보다 크거나 같으므로 1, 그리고 88-64 = 24
24가 32보다 작으므로 0
24가 16보다 크거나 같으므로 1, 그리고 24-16 = 8
8이 8보다 크거나 같으므로 1, 그리고 8-8 = 0
0이 4보다 작으므로 0
0이 2보다 작으므로 0

마지막으로 붉은색 숫자를 위에서부터 아래 순서로 나열한다.

0100101100

이것이 600을 2진수 10자리로 만든 것이다.





이 댓글을 비밀 댓글로
    • sellester
    • 2011.10.25 13:15
    틀렸음 512부터 시작합니다.
    • 1024부터 시작하거나 512부터 시작하거나 구하는 2진수의 자리수만 다를뿐, 구해지는 2진수는 같지 않은가요?

      1024부터 시작하면 0100101100
      512부터 시작하면 100101100

      이렇게 구해지는 것이지 않나요.
    • 정말감사합니다.
    • 2014.04.08 09:44
    힌트를 얻어서 풀게 되었습니다. 감사합니다 ㅋㅋㅋ

해시 테이블에 대하여 (about Hash Table)

by Blogger 하얀쿠아
2011. 6. 11. 10:43 소프트웨어 Note/Algorithm

해시 테이블은 한마디로

 

공간을 팔아 시간을 사다

 

라는 말로 표현할 수 있다. 주소를 이용해서 배열같이 직접 탐색이 가능하다.

 

해시테이블의 기본 개념은 다음과 같다.

 

데이터를 담을 테이블을 미리 크게 확보해 놓은 후 입력받은 데이터를 해시하여

테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것,

 

이것이 바로 해시 테이블의 기본 개념이다.

해시테이블은 특이하게도 데이터가 입력되지 않은 여유공간이 많아야 제 성능을 발휘할 수 있다.

 

테이블 내의 주소를 계산할 때는 해시함수를 이용하는 데 이에는 두가지 방법이 사용된다.

 

1) 나눗셈법

 주소 = 입력값 % 테이블의 크기

 하지만 이는 충돌과 클러스터 문제가 발생할  가능성이 높다.

 

2) 자릿수 접기

 Hello -> 72 + 101 + 108 + 111 = 500

 하지만 이는 문자열 키가 고정일 경우 해시테이블의 전체크기를 전부 활용못할 수가 있는데,

이는 따로 루프 반복시마다 왼쪽으로 남은 비트씩 끌어올림으로써 해결 할 수 있다.

 하지만 이 역시 충돌 문제는 해결하지 못한다.

 

 

그래서 충돌문제 해결을 위한 방법이 등장한다.

1) 개방 해싱(Open Hashing) : 해시 테이블의 주소 바깥에 새로운 공간을 할당하여 문제를 수습

2) 폐쇄 해싱(Closed Hashing) : 처음에 주어진 해시 테이블의 공간 안에서 문제를 해결

 

 

 개방 해싱 기법에는 Chaining이 있는데 이는 해시 테이블이 데이터 대신 링크드 리스트에 대한

포인터를 관리한다. 링크드 리스트에 데이터 삽입 시에 테일 다음에 붙이면은 탐색비용이 소요되므로

헤드에 붙인다.

 

 체이닝은 순차탐색으로 해시테이블의 '극한의 탐색'을 위해 고안된 성능을 훼손시키므로

해시테이블 + 이진트리탐색( 특히 레드 블랙 트리)를 사용하여 이 문제를 해결한다.

 

 개방 주소법(Open Addressing)은 충돌이 일어날 때 해시 함수에 의해 얻어진 주소가 아니더라도

얼마든지 다른 주소를 사용할 수 있도록 허용하는 충돌 해결 알고리즘이다.

 이에 비해 체이닝은 해시 함수에 의해 얻어진 주소만 사용하므로 오픈 해싱 기법인 동시에

폐쇄 주소법(Closed Addressing) 알고리즘이기도 하다.

 

 개방 주소법은 탐사가 중요하다.

 

1) 선형탐사(Linear Probing) : 가장 간단한 탐사방법으로 해시 함수로부터 얻어낸 주소에 이미 다른 데이터가

입력되어 있음을 발견하면, 현재 주소에서 고정 폭(예를 들면 1)으로 다음 주소로 이동. 클러스터 문제가 발생한다.

즉 클러스터가 발생하면 새로운 주소를 찾기위해 수행하는 선형 탐사 시간이 길어지고 이로 인해 해시 테이블의

성능은 엄청나게 저하된다.

 

2) 제곱탐사(Quadratic Probing) : 선형 탐사가 다음 주소를 찾기 위해 고정폭만큼 이동하는 것에 비해

제곱탐사는 이동폭이 제곱수로 늘어나는 점이 다를 뿐이다. 이 역시도 클러스터 문제가 발생한다.

 

3) 이중 해싱(Double Hashing) : 클러스터 발생 방지를 위해 탐사 주소의 규칙성을 없애버린다. 한가지 아이디어로

rand()를 이용한 난수를 생각할 수도 있겠지만 같은 키를 입력하면 항상 같은 해시 값(주소)를 얻을 수 있어야

하는데, rand()함수를 이요하면 항상 다른 값을 얻게 되므로 적절한 답은 아니다. 이중 해싱은 이동폭을 제2의

해시 함수로 계산한다. 즉 2개의 해시 함수를 준비해서 하나는 최초의 주소를 얻을 때 사용하고 또 다른 하나는

충돌이 일어났을 때 탐사 이동폭을 얻기 위해 사용한다.

 

 만약 아무리 성능이 뛰어난 충돌 해결 알고리즘도 해시 테이블의 여유공간이 모두 차버려서 발생하는 성능 저하는

당해낼 방법이 없다. 그래서 남은 공간이 거의 없는 해시 테이블에서는 허구헌날 연쇄충돌이 일어날 것이다.

 재해싱(Rehashing)은 이 문제를 해결할 수 있는 방법 중 하나로, 재해싱은 해시 테이블의 크기를 늘리고

늘어난 해시 테이블의 크기에 맞추어 테이블 내의 모든 데이터를 해싱한다.

 

 통계적으로 해시 테이블의 공간 사용률이 70% ~ 80% 에 이르면 성능 저하가 나타나기 시작한다. 그러니 재해싱을

이 전에 수행해야 성능저하가 나타나는 것을 막을 수 있다. 하지만 재해싱 역시 만만치 않은 오버헤드를 요구하기

때문에 재해싱을 수행할 임계치를 너무 낮게 잡는 것도 성능 저하의 원인이 되므로, 임계치는 75% 정도를

사용하는 것이 보통이다.

참고 문헌 : 뇌를 자극하는 알고리즘(한빛미디어, 박상현 저)

 

[출처] 해시 테이블에 대해서|작성자 힝아

이 댓글을 비밀 댓글로

OAuth 인증방식 이해하기

by Blogger 하얀쿠아
2011. 4. 16. 03:18 소프트웨어 Note/Algorithm

OAuth 인증방식 이해하기

본 문서는 OAuth의 이해를 돕기 위해 작성되었습니다.

OAuth 학습을 뛰어넘고 바로 예제 소스를 보며 개발을 하고 싶다면, 튜토리얼를 참고하시기 바랍니다.

본 문서 내의 용어 일관성을 위해 OAuth스팩에 있는 용어를 사용하였습니다. 본 문서에서 용어는 모두 이탤릭체로 표시됩니다.

용어정의

  • 서비스 프로바이더(Service Provider) – API를 제공하는 서비스를 말합니다. 예> 스프링노트
  • 사용자(users) - 서비스 프로바이더 혹은(그리고) 컨수머를 사용하는 이를 말합니다. 
  • 컨수머(Consumer) – API를 사용하여 개발된 애플리케이션 서비스를 말합니다. 예> 스프링노트의 API를 이용하여 개발된 매시업
  • 보호된 자원(Protected Resources): 서비스 프로바이더에 존재하는 사용자의 데이터를 의미합니다. 예> 스프링노트의 페이지 혹은 첨부 데이터들
  • 컨수머 개발자(Consumer Developer) : 컨수머를 개발하는 개인 혹은 단체
  • 컨수머 키(Consumer Key) : 서비스 프로바이더에게 컨수머 자신임을 인증하기 위한 키
  • 컨수머 시크릿(Consumer Secret) : 컨수머컨수머 키 소유권한이 있는지 인증하기 위한 키
  • 토큰(Tokens) – 컨수머에서 서비스 프로바이더에 있는 사용자보호된 자원에 접근하기 위해 사용되는 사용자의 인증정보입니다. 예를들어 스프링노트의 API를 사용해 개발된 매시업 M이 스프링노트(서비스 프로바이더)에 있는 사용자 U의  보호된 데이터에 접근하기 위해서는 사용자 U의 인증정보(credential)가 필요합니다. 그 인증정보를 위해 사용되는 것이 토큰입니다.

    • 리퀘스트 토큰(Request Token) :  컨수머사용자에게  접근권환을 획득하는 과정에서 사용하는 값이며, 이것은 차후 액세스 토큰으로 교환됩니다.
    • 리퀘스트 토큰 시크릿(Request Token Secret) :  리퀘스트토큰이 사용자의 것임을 인증하기 위한 값입니다.
    • 액세스 토큰(Access Token) : 컨수머사용자서비스 프로바이더를 통해서가 아닌 컨수머를 통해서 보호된 자원에 접근할 수 있는 권한을 받기 위한 값입니다.
    • 액세스 토큰 시크릿(Access Token Secret) : 액세스토큰사용자의 것임을 인증하기 위한 값입니다.

 

용어를 숙지 하셨다면, 이해를 쉽게 하기 위해 두 가지 관점에서 인증과정을 살펴보겠습니다.

사용자 관점에서 바라보았을 때의 인증과정을 학습하셨다면, 개발을 하기 위해 OAuth프로토콜 관점에서 바라보았을 때의 OAuth 인증과정을 통해 좀 더 자세히 OAuth인증 과정 학습 및 개발을 할 수 있습니다.

Tags
이 댓글을 비밀 댓글로

Travelling Salesman Problem Portal Site

by Blogger 하얀쿠아
2011. 4. 13. 15:36 소프트웨어 Note/Algorithm

최단경로로 모든 도시를 돌아다니는 경로/회로를 찾는 문제.

http://www.tsp.gatech.edu/
이 댓글을 비밀 댓글로