앞서 RSA 시스템이 소인수분해문제의 어려움을 기반으로 한다 하였습니다.

하지만 컴퓨터의 발달과 다양한 암호분석기법이 발전하면서,
실제로 우리가 사용하는 암호 시스템이 얼마나 안전한지 검증 해야 할 필요가 있습니다.

따라서 이번 포스팅에서는 이런 암호 검증과 관련된 사례를 하나 소개하고자 합니다.

RSA사에서 내건 RSA-200 소인수분해 공모 문제로
663-bit, 10진수로 200자리의 수인

2799783391122132787082946763872260162107044678695542853756000992932612840010760934567105295536085606
1822351910951365788637105954482006576775098580557613579098734950144178863178946295187237869221823983

를 소인수 분해 하는 문제가
2005년 5월 9일 F.Bahr, M.Boehm, J.Franke, T.Kleinjung에 의해 풀렸습니다.
※ 참고 : http://www.loria.fr/~zimmerma/records/rsa200

그들이 사용한 방법은 GNFS(General Number Field Sieve)이며,
이는 네트워크를 통한 다수의 컴퓨터의 컴퓨팅 파워를 동원하는 방법입니다.

그들이 찾은 답은

3532461934402770121272604978198464368671197400197625023649303468776121253679423200058547956528088349



7925869954478333033347085841480059687737975857364219960734330341455767872818152135381409304740185467

인데 ...
시간이 되시면 한번 검증 해 보심을 추천합니다 ... ...

요즘에는 최소 RSA 2048 bit 이상의 시스템 사용을 권장합니다 ...

Reference
[1] 정교일, 이병천, 진승헌, "훤히 보이는 정보보호", 2008

출처 - http://reinliebe.tistory.com/

Rivest Shamir Adleman

RSA 암호는 1978년 MIT의 리베스트, 샤미르, 에이들먼이 제안한 공개키 암호 알고리즘으로,
소인수분해 문제의 어려움에 이론적 기초를 둔 암호 알고리즘입니다.


※ 왼쪽부터 ... 샤미르, 리베스트, 에이들먼
※ 이 분들의 사진은 요기에서 ... http://www.ams.org/featurecolumn/archive/internet.html

RSA 암호의 기반이 되는 소인수분해 문제(Integer Factorization Problem)란 ...

간단히 말해서 임의의 소수를 이용하여 합성수를 만드는 것은 쉽지만,
합성수를 소인수분해 하여 소수로 만드는것은 어렵다는 거지요 ...

소인수분해 문제는 NP(비결정론적 다항식 시간)의 의미에서 어려운 문제라 알려져 있는데

간단히 예를 들면, 소수 19와 17의 곱으로 323 이라는 합성수를 만들긴 쉽지만
323 이라는 합성수를 보고 어떤 수의 곱으로 이루어졌는지 찾기위해서는 시간이 필요하다는것이지요

하물며 이런 작은 숫자가 아니라 300자리 이상의 소수의 곱으로 이루어진 RSA시스템에서
그 소인수분해를 하기란 시간적으로 매우 오래 걸린다는 것입니다

아무튼 이런 간단한(?) 원리를 이용하면서도 안전성이 높아 ...
(정확히 말하면 계산학적으로 풀기 어려운게 아니라 ... 시간적으로 오래 걸리기 때문에)

현재 널리 사용되고 있습니다 ...

사용되는 용도는 .... ... 현대인이라면 누구나 하나쯤 가지고 있다는 그 ... 공인인증서 ! ...
(은행 인터넷 뱅킹 페이지 등에 가시면 ... 본 사이트는 RSA 2048bit 으로 암호화 되어있습니다 와 같은 문구를 보실 수 있습니다)


여러가지 배경은 여기까지로 압축 하기로 하고,
본격적으로 알고리즘은 다음과 같습니다.

▷ 키 생성
  - 두 개의 큰 소수 pq를 선택하고, 이들의 곱 n=pq를 계산한다.
  - φ(n) = (p-1)(q-1)
  - n과 서로소인 e를 선택하고 de=1mod φ(n) 를 만족하는 수 d를 계산한다.
  - (n, e)는 공개키로 공개하고, d는 개인키로 보관한다. 

▷ 암호화
  - 메시지 m을 공개키(n,e)를 이용하여 c=m^e·mod n 로 암호화 한다.
 
▷ 복호화
  - 암호문 c를 자신의 비밀키 d를 이용하여 m = c^d·mod n 으로 복호화 한다.


그럼 RSA의 간단한 예를 들어보도록 하겠습니다.

▶ 키 생성
  p = 2357, q = 2551, n = pq = 6012707
  φ(n) = (p-1)(q-1) = 6007800
  e = 36749911 로 결정하면 유클리드 알고리즘을 이용하여 d = 422191로 구할 수 있습니다.
 여기서 ne 즉, 6012707 36749911을 공개하고,  d = 422191을 개인키로 보관합니다.

▶ 암호화
  메시지 m = 5234673 이라면
  암호문  c=m^e·mod n = 5234673^3674911 mod 6012707 = 3650502
  즉, 메시지 m = 5234673을 공개키 ne를 이용하여 암호화 하면 암호문 c = 3650502를 얻습니다.

▶ 복호화
  메시지 m = c^d·mod n = 3650502^422191 mod 6012707 = 5234673
  암호문 c = 3650502를 개인키 d를 이용하여 복호화 하면 원래의 메시지 m = 5234673을 얻을 수 있습니다.

Reference
  [1] 한국전자통신연구원, "암호학의 기초", 1999

출처 - http://reinliebe.tistory.com/

이번에 소개해 드릴 암호 알고리즘은 ... ARIA ...

.. ... Academy, Research Institute, Agency

이전 포스팅의 SEED와 마찬가지로 국가 표준 암호 알고리즘입니다.

다만 다른점이 있다면, SEED가 Feistel 구조의 블록 암호라면, ARIA는 SPN 구조의 블록암호라는 차이가 있습니다.
(정확하게는 Involutional SPN 구조 입니다만 ... )

다른 설명보다도 공식 상세 문서를 보시면 더 이해하시기가 편하실 겁니다 ...
관련 자료는 ...

ARIA 공식 홈페이지(?) - http://210.104.33.10/ARIA/index.html
국가정보원 - http://service2.nis.go.kr/

에서 다운로드 받으 실 수 있습니다만 ... ... 이번에도 제가 미리 받아 둔 파일을 첨부합니다.

 - 상세문서 :

 - 테스트벡터 :
 - 소스코드
소스코드는 위에 링크한 국정원 홈페이지에서 배포한 것을 그대로 재 첨부 한것이며,
국가정보원 표 소스코드는 JAVA / C(32Bit) / ANSI C 세 가지 스타일로 작성되어 있습니다.

※ 주의사항
ARIA 상세 명세서 ... 12 페이지 그림 잘못되어있습니다
절대 12 페이지 보고 구현하면 ... 망합니다 ... (제가 그 피해자 입니다...)
문제는 수정판이 있는데 ... 공식 홈페이지와 국정원 모두 잘못된 구 버전 명세서가 올라가있습니다 ... (2010년 2월 기준)

출처 - http://reinliebe.tistory.com/
이전 포스팅에서 소개한 DES와 AES가 미국 표준(이라고 쓰고 국제 표준이라고 읽습니다) 암호 알고리즘 이었다면

이번과 다음 포스팅에서 소개하는 알고리즘들은 국내 표준 암호 알고리즘입니다.

참고로 논란의 여지가 있어서 언급하는 겁니다만,
SEED도 국제 표준(ISO/IEC 18033-3, IETF RFC 4269)에 등록되어있습니다.
AES나 DES 만큼 여러 나라에서 사용하지 않아서 그렇지요 (거의 우리나라만 쓸겁니다)... ... ;;;;;;;


SEED 암호 알고리즘은 Feistel 구조의 블록 암호 알고리즘으로,
1999년 한국정보보호진흥원(KISA: 현 한국인터넷진흥원)에서 개발, 국내의 금융 IC 카드 등에 사용되는 알고리즘 입니다.

- 128-Bit symmetric
- Feistel structure with 16 rounds
- Two 8x8 S-boxes
- National industrial association standard (TTAS KO-12.0004, 1999)

상세 명세서와 소스코드는 KISA 홈페이지에서 받으 실 수 있습니다만,
저도 자주 보는 터라 받아 둔 게 있어 올려봅니다.

- SEED 명세서

- SEED 테스트벡터

참고 : 한국인터넷진흥원 - http://www.kisa.or.kr

현재 SEED 소스는 KISA 홈페이지에서 요청 등록을 하면 주는 식으로 바뀌어 있는 것 같습니다
따라서 SEED 소스는 Devpia 자료실의 자료를 링크합니다.
KISA 에서 제공한 C 코드를 조금 수정한 코드라는데 ... ... KISA에서 제공한 소스랑 거의 같네요 ;;
http://www.devpia.com/MAEUL/Contents/Detail.aspx?BoardID=278&MAEULNo=20&no=17329&ref=17329


출처 - http://reinliebe.tistory.com/

이번 프로그램은 일전의 AES C# 소스 코드 포스팅의 확장입니다 ...

 

자세한 설명은 앞의 포스팅을 참고하시길 ...

 

제가 올린 소스코드에서 입출력 부분을 조금 바꾼 뒤,

 

이를 이용하여 파일 암호 프로그램으로 변형 해 보았습니다 ...

 

바꾼 입출력은 아래 예시 처럼 매우 간단한지라 ... 따로 소스는 올리지 않습니다.

 

입력예시..


대신 바뀐 클래스의 DLL 파일을 첨부합니다.

 

 

이 DLL 파일을 이용하여, 간단하게 windows form 을 이용한

 

파일 암호화 프로그램을 만들어 보았습니다.

(아래 프로그램 실행 시 위의 DLL 파일을 필요로 합니다)

 


 

작성 언어가 당연히 ... 지난 포스팅의 연속이므로 C#이며

 

실행을 위해서는 .NET 프레임웍이 필요합니다.

 

만들고나니 소스가 200줄밖에 안되는군요 ;;

출처 - http://reinliebe.tistory.com/

인터넷상에 널리고 널린게 AES 코드지만, 저도 하나 올려봅니다 ...

C/C++ 언어로 작성된 AES 코드는 많지만 C#은 많지 않기에 ... 그냥 한번 만들어 보았습니다.

일단 C# 언어로 작성되어있지만,
C/C++코드가 필요하신 분들이 가급적 보기 쉽고 바꾸기 좋도록(?) 만들었습니다.
(그래봤자 foreach를 for 로 만든 것 밖에 없지만 ...)


저의 프로그래밍 철학은 무조건 가독성이 높게 가 모토이므로,
코드가 단순 무식해 보일지도 모르지만 (사실 실력이 좋지 않습니다 ... 게다가 가독성도 .. (응?))
무릇 고급언어(C, JAVA 등)라는 것은 기계어(어셈블리어 등)에 비해 인간이 보기 쉽고
논리적으로 판단하기 쉽게 만들어야 한다고 생각합니다.
(이렇게 밖에 프로그램을 못하는 자의 비겁한 변명이려나요  .. 그냥
프로그램 잘 하는 사람들이 그냥 부러울 뿐이에요 ;;)
 

코드보기



코드가 귀찮으신 분은 ... 아래 dll 파일을

참조하신 뒤에

 

코드보기..


이렇게 하셔도 무방합니다 ...

 

일단 TEST VECTOR 를 넣고 테스트를 해 본 결과, 결과 값이 잘 나오는 것을 확인 하였지만

논리적으로 문제가 발견되면 언제든 Feedback 받습니다 ...

 

이용은 자유지만, ㅊ..추천이나 ..ㄷ..ㄷㅐ댓글같은걸 바라ㅈ ... ... 쿨럭!

언제나 오픈 마인드입니다 ... 'ㅂ'/


출처 - http://reinliebe.tistory.com/

Advanced Encryption Standard

앞 포스트에서 DES 암호 알고리즘에 대하여 살펴보았습니다.

앞 포스팅을 간단히 요약하면, 30년 가량 써온 DES 알고리즘이 .. 사용에 큰 지장은 없었으나 ...

DES 알고리즘의 문제점으로 키 길이가 너무 짧다.
또한 Differential Cryptanalysis(1990년, Biham & Shamir)와 Linear Cryptanalysis(1993년, Matsui)이 등장하면서
DES 키 분석이 더 쉬워졌다.
그래서 2개의 키로 3번 반복하는 Triple-DES(이하 T-DES)를 사용한다.
하지만 3번 반복하다보니 ... 3배로 느리다 ...
더 중요한건 키 길이는 112비트가 되었지만, 여전히 암호 블록은 64비트이다...

... 이런 이유에서 AES가 나오게 됩니다 ...

앞 포스트에도 있는 내용이지만 ... ...
3차에 걸친 DES Challenge를 통하여 DES의 (키 길이가 짧아서 생긴)취약성을 증명하였고
동시에 1997년 미쿡의 NIST에서는 DES를 대신할 새로운 블록 암호 공모를 시작하였습니다.

제안된 수많은 암호 알고리즘들 중에서 ... (그 중에는 우리나라에서 제안한 것도 있었다고 합니다 ...)

2000년 10월 2일 Rijndael(라인달 이라고 읽으면 됩니다)을 AES로 선정합니다.
(만든 사람인 Joan Daemen과 Vincent Rijmen의 이름을 따서 지어진 이름이라지요 ;;)

그리고 이듬해인 2001년 1월 16일, FIPS197로 표준을 공표합니다.

AES 소스는 웹 상에 많이 널려 있지만 ...
C# 언어로 작성한 소스 코드를 다음 포스트에 게시합니다.

더불어 AES 암호 알고리즘의 상세 문서는 ... 이것 !!!




출처 - http://reinliebe.tistory.com/

DES 알고리즘을 C#으로 만들어 보았습니다 ...

DES 암호 알고리즘이 나온지 벌써 30년이 넘었기 때문에,
웹 상에 정말 널리고 널렸기에 크게 의미는 없습니다만 ...

아무튼 ... 널리고 널린 DES 코드인 만큼 저도 다른 사람들이 만든 코드를 활용해보았습니다.
결국 구글에 DES C CODE라고 치면 두번째로 검색되는
(앞서 DES 포스트에도 언급 되어있는 소스코드 입니다)

http://ubiqx.org/libcifs/source/Auth/DES.c

위의 C코드를 C#으로 바꾼 것 밖에 한 것이 없네요 ...
(코드는 스크롤 압박이 심해서 접어둡니다)


암호학 - Block Cipher :: DES C# 소스

'Security > Cryptography' 카테고리의 다른 글

암호학 - Block Cipher :: AES C# 소스  (0) 2011.05.07
암호학 - Block Cipher :: AES  (0) 2011.05.07
암호학 - Block Cipher :: DES  (0) 2011.05.07
암호학 - Block Cipher  (0) 2011.05.07
암호학 - Introduction  (0) 2011.05.07

+ Recent posts