work smart !!

이전의 포스팅에서 Shannon의 Confusion/Diffusion에 대한 용어를 사용하였는데

Shannon, 풀 네임 Claude Elwood Shannon (1916-2001)이 제안한
Confusion (혼돈) 과 Diffusion (확산)을 간단히 정리하면 다음과 같습니다.

▷ Confusion : 평문과 암호문 사이의 관계를 알기 어려워야 함,
▷ Confusion : 다시 말해 평문 1 비트의 변화가 암호문에 어떤 변화를 초래할 지 예측할 수 없어야 함

▷ Diffusion : 평문을 구성하는 각각의 비트들의 정보가 여러개의 암호문 비트에 영향을 미쳐야 함

뭐 당연한 말이지만 ...

혼돈이론에 따르면,
0x0000을 암호화 했더니 0xFFFF가 나왔다, 그래서 0x0001을 암호화 했더니 0xFFFE 가 나왔다 ...
이런식으로 되면 안된다는거지요
0x0000을 암호화 했더니 0xFFFF가 나왔다, 그래서 0x0001을 암호화 했더니 0x4F9B 가 나왔다 ...
이런식으로 ... 1비트의 입력 변화에 따른 출력을 예측할 수 없어야 합니다

확산이론에 따르면 0x0000 과 0x0001을 암호화 할 경우,
비록 입력 1비트가 변화했지만 그 1비트가 암호문의 여러 비트에 영향을 주어야 합니다.

앞에서 SPN 구조가 Confusion과 Diffusion의 원리를 이용한다 언급하였지요
그 SPN 구조의 AES 알고리즘을 예를 들면
ByteSub Layer(S-Box)가 Confusion을 위해
Shift row/MixColumb Layer가 Diffusion을 위해 존재한다 보시면 됩니다.

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

Secure Hash Algorithm 1

주요 특징을 살펴보면 ... 일단 미국 표준입니다 ...
미쿡 NSA 에서 1995년에 개발하였으며 ...
블록 크기 : 512bit, 출력 크기 : 160bit를 갖습니다.

... ...

SHA1을 C# 으로 구현한 소스 ... ... ... 를 올리려 했는데 ...

충격적인 사실 ... ... .NET Framework엔 SHA1이 이미 구현 되어있네요 ... ...
구현하다 포기했습니다 ...

using System.Security.Cryptography;

네임스페이스를 추가 하셨으면 ...

byte[] data    = new byte[DATA_SIZE];

byte[] result;

 

SHA1 sha = new SHA1CryptoServiceProvider();

result = sha.ComputeHash(data);

이렇게 하시면 됩니다 ... ...

-------------------------------------------------
여담으로 ...
저도 Hash Function을 종종(?) 사용하는데 ...

일전의 잉여 프로그램 만들기 할 때, 중복된 이미지 검사를 할 때 사용했습니다 ... ...
이 밖에 ... 생각보다 다양한 용도로 사용 가능합니다

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

Hash 함수는 정확히 암호학 ... ... 이라기 보다는 일종의 압축(?) 알고리즘이라고 볼 수 있습니다만,

보안 응용분야에 널리(?) 사용되고 있기 때문에 ... 암호학의 범주안에 들어오는 것 같아 소개를 합니다 ...

처음에 Hash 함수를 압축 알고리즘이라고 표현을 했는데,

엄밀히 말하면 ... ... 임의의 메시지를 줄여서 특별한 정보로 만드는것 ... 이라고 봐야겠네요 ...
그 특별한 정보를 몇몇 책에는 메시지의 '지문'과 같은것 이라고 표현을 하기도 합니다
즉, Hash 값은 ... 원 메시지를 대신할 수 있는 작은 값으로 볼 수 있습니다.

하지만 ... 문제는 ... ... N:M 의 함수에서 ... N<M 이라면 결국 어딘가에는 충돌쌍이 존재한다는 거지요 ... ...

그래서 Hash는 충돌쌍을 예측하기 매우 어렵게 만들어야 합니다...

이 Hash에 대한 얘기는 ... ... 가장 흔하게 알려진게 ... Birthday Paradox ... 지요
http://en.wikipedia.org/wiki/Birthday_Paradox

그럼 왜 Hash가 필요하냐 ... ... ... 그것은 바로 효율때문입니다 ...
앞서 전자서명(http://reinliebe.tistory.com/29)에 대한 설명을 했었는데

결국 메시지의 n제곱을 계산해야하기 때문에, 메시지 길이가 길면 연산시간이 매우 오래걸리지요 ...
따라서 원본 메시지를 대신할 그 무엇인가가 필요하게 되고 ...
실제로 그런 용도로 많이 쓰입니다 ...



앞서 RSA를 언급하면서 썼던 공인인증서 예입니다 ...

서명 해시 알고리즘에 SHA1 이라고 적힌 것을 볼 수 있습니다 ...
알게 모르게 Hash 알고리즘은 주변에서 이미 널리 사용되고 있지요 ...

결국 최종적으로 ...
Hash 알고리즘은 ...

1. 입력값보다 출력값이 작아야 한다.
2. 계산이 용이해야 한다.
3. 출력값을 보고 입력값을 예측할 수 없어야 한다.
4. 같은 Hash값을 갖는 서로다른 입력값이 알려지면 안된다(찾기 어려워야 한다)

... 이정도로 줄일 수 있겠네요 ...

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

RSA 암호 알고리즘이 소인수분해 문제의 어려움에 기반한다면,

 

엘가말 암호는 이산대수 문제의 어려움에 기반한 암호 알고리즘입니다.

 

이산대수 문제의 어려움이란,

 

주어진 g, x, p 를 이용하여 y = g^x mod p 를 구하긴 쉽지만

 

g, y , p 값을 이용하여 원래의 x를 찾기 어렵다는 것이지요.

 

엘가말 암호는 1984년 스탠퍼드 대학의 테하르 엘가말(Tehar ElGamal)이 제안한 암호로,

 

키 생성, 암호화, 복호화 과정은 아래와 같습니다.

 

▷ 키 생성

  - 큰 소수 p를 선택하고 생성자 g를 선택.

  - 비밀키 x를 선택하고 공개키 y = g^e mod p를 계산.

  - [y, g, p]를 공개키로 공개하고, 비밀키 x는 보관.

 

▷ 암호화

  - 메시지 m을 암호화하기 위해 난수 k 선택.

  - 암호문 r = g^k mod p

  - 암호문 s = my^k mod p

  - 암호문 [r, s]를 수신자에게 전달

 

▷ 복호화

  - 메시지 m = s/r^x mod p 로 계산

 

엘가말 암호의 장점이라면

 

난수 k를 이용하기 때문에, 매 암호화 시 다른 암호문을 얻어 RSA에 비해 더 안전하다고 볼 수 있습니다

왜냐하면 RSA는 같은 메시지, 같은 키 값을 이용할 경우 그 암호문이 항상 일정한 데 반해

엘가말 암호는 같은 메시지, 같은 키 값을 사용해도 암호화시 마다 그 암호문의 값이 변하기 때문이지요

 

다만 메시지 m을 암호화 하면 그 길이가 두 배가 되는 단점이 있습니다.

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

현대인에게 있어 전자서명이라는 용어가 그리 낮설지는 않을 것입니다.

 

전자서명, 문자 그대로 내가 작성한 문서임을 증빙하기 위해 서명을 하는데

 

이를 컴퓨터를 이용하여 한다는 것이지요.

 

전자서명이 필요한 이유는 신분 확인(인증)과

 

전자 상거래 등에 있어서 본인이 작성한 문서임을 증빙하기 위하여 반드시 필요합니다.

(내가 서명한 문서와 타인이 서명한 문서를 구분 지을 수 있어야 하며,

혹 내가 서명하지도 않은 계약서를 들이밀면서 지불을 요구하는 사례가 없어야기 때문이지요)

 

전자서명 알고리즘은 다음과 같은 요구사항을 만족해야 합니다.

전자서명을 위해서 우선적으로 정당한 서명자 이외에 타인이 서명을 위조할 수 없도록 해야하며,

전자서명만 보고도 누가 서명한 것인지 알 수 있어야 합니다.

또한 서명자는 문서에 서명한 사실에 대하여 부인 할 수 없어야 하고,

한 번 서명한 문서의 내용은 변경 불가능 해야 합니다.

마지막으로 하나의 서명을 가지고 다른 문서에 재 사용 하는 일이 없도록 해야합니다.

 

앞 포스팅에서 설명드린 RSA를 이용하여 전자서명을 하는 방법은 ...

 

▷ 전자서명

  메시지 m을 s = m^d mod n 으로 서명하고,

 

▷ 서명검증

  m = s^e mod n 으로 검증합니다.

 

여기서 d와 e, n에 대한 설명은 RSA와 같습니다.

만일 ... 어? RSA를 반대로 한거네 ? 라고 생각이 드신다면 ... 정확히 맞습니다.

 

전자서명이 사용되는 범위는,

 

일반 웹 페이지에 보안 섹션뿐만 아니라,

 

인터넷뱅킹 및 전자상거래에 관련된 모든 분야에서 널리 사용되고 있으며,

 

넓게는 전자여권 및 다양한 응용 분야에 활용 되고 있습니다.

 

국내에서는 1999년 2월 제정된 전자서명법이 제정되고 같은해 7월부터 시행되어

 

전자서명도 수기서명과 같이 법적으로 문서에 대한 서명으로 인정을 받게 되었습니다.

 

Reference

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

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

RSA 알고리즘의 C 코드는 구글에서 찾아보면 쉽게 얻을 수 있습니다...

간단히 참고 할 만한 C 소스 파일들을 보면 ...

1. http://www.codase.com/search/display?file=L2dlbnRvbzIvdmFyL3RtcC9yZXBvcy9jb2Rhc2UuYy9wYWtldHRvLTEuMTAtcjEvd29yay9wYWtldHRvLTEuMTAvbGlidG9tY3J5cHQvcnNhLmM=&lang=c

2. http://en.pudn.com/downloads3/sourcecode/crypt/detail11349_en.html

이 정도가 되겠지만 ... ... 둘 다 쉽지 않습니다.

그나마 2번 vlong class를 이용한 소스코드는 그나마 볼만한 수준이지만, 1번 소스 코드는 참고하기 어렵지요 ...

이는 RSA에서 사용하는 [매우 큰 정수]의 연산을 지원하는 함수,
하다못해 덧셈 뺄셈과 같은 기본 연산도 새로 구성해줘야 하기 때문인데

.NET Framework 4.0부터는 이를 해결하기 위한 BigInteger class가 생겼습니다.

C#으로 간단히 RSA 연산을 구현하면 아래의 코드와 같습니다.
(소스 코드는 이전 포스트 : http://reinliebe.tistory.com/79 에 올린 RSA 예제를 사용했습니다)

using System;

using System.Numerics;

 

class RSA_TEST

{

    static void Main(string[] args)

    {

        BigInteger d = new BigInteger(422191);

        BigInteger n = new BigInteger(6012707);

        BigInteger e = new BigInteger(3674911);

        BigInteger M = new BigInteger(5234673);

        BigInteger C = new BigInteger();

 

        // Encryption

        C = BigInteger.ModPow(M, e, n);

        Console.WriteLine("Cipertext : "+C);

 

        // Decryption

        M = BigInteger.ModPow(C, d, n);

        Console.WriteLine("Plaintext : " + M);

    }

}

▷ 결과


p.s Ciphertext 에서 h 빠진건 ... 애교로 봐주세요 ... ;ㅂ;

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

앞서 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 으로 암호화 되어있습니다 와 같은 문구를 보실 수 있습니다)

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

▷ 키 생성
  - 두 개의 큰 소수 p와 q를 선택하고, 이들의 곱 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로 구할 수 있습니다.
 여기서 n과 e 즉, 6012707과 36749911을 공개하고,  d = 422191을 개인키로 보관합니다.

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

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

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

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