SEED 암호 알고리즘 소스코드는 KISA에서 배포하기도 하고,
일전의 포스팅에서 소개한 devpia 자료실에도 올라와 있기 때문에 딱히 올릴 생각은 없었지만 ...

요즘 통 ... 암호 관련 포스팅을 하지 않아서 ... 그냥 가지고 있는 소스나 올려보자하는 땜빵 포스팅인거죠 ;;
(사실 암호학 포스팅하면서 수식쓰기가 귀찮아서 ... 계속 진행을 미루고 있는 게으름 탓이지만요 ㅠㅠ)

이번 포스팅은 역시 차별화(?)를 두기위해 C++/CLR로 작성된 코드이며 .. 작성한지 2년정도 된 듯 싶네요 ...

 

public ref class SEED {

 

private:

 

    array<Byte>^    Plaintext;

    array<Byte>^    Ciphertext;

    array<Byte>^    SecretKey;

 

    UInt32            G_Function(UInt32 unGin);

    UInt64            F_Function(UInt64 unFin, UInt64 unRoundKey);

    array<UInt64>^    KeySchedule(array<Byte>^ ucKey);

    void            Encryption(array<Byte>^ ucPlaintext, array<Byte>^ ucKey, array<Byte>^ ucCiphertext);

 

public:

 

    SEED();

 

    static array<Byte>^        S1 = {

        0xA9, 0x85, 0xD6, 0xD3, 0x54, 0x1D, 0xAC, 0x25, 0x5D, 0x43, 0x18, 0x1E, 0x51, 0xFC, 0xCA, 0x63,

        0x28, 0x44, 0x20, 0x9D, 0xE0, 0xE2, 0xC8, 0x17, 0xA5, 0x8F, 0x03, 0x7B, 0xBB, 0x13, 0xD2, 0xEE,

        0x70, 0x8C, 0x3F, 0xA8, 0x32, 0xDD, 0xF6, 0x74, 0xEC, 0x95, 0x0B, 0x57, 0x5C, 0x5B, 0xBD, 0x01,

        0x24, 0x1C, 0x73, 0x98, 0x10, 0xCC, 0xF2, 0xD9, 0x2C, 0xE7, 0x72, 0x83, 0x9B, 0xD1, 0x86, 0xC9,

        0x60, 0x50, 0xA3, 0xEB, 0x0D, 0xB6, 0x9E, 0x4F, 0xB7, 0x5A, 0xC6, 0x78, 0xA6, 0x12, 0xAF, 0xD5,

        0x61, 0xC3, 0xB4, 0x41, 0x52, 0x7D, 0x8D, 0x08, 0x1F, 0x99, 0x00, 0x19, 0x04, 0x53, 0xF7, 0xE1,

        0xFD, 0x76, 0x2F, 0x27, 0xB0, 0x8B, 0x0E, 0xAB, 0xA2, 0x6E, 0x93, 0x4D, 0x69, 0x7C, 0x09, 0x0A,

        0xBF, 0xEF, 0xF3, 0xC5, 0x87, 0x14, 0xFE, 0x64, 0xDE, 0x2E, 0x4B, 0x1A, 0x06, 0x21, 0x6B, 0x66,

        0x02, 0xF5, 0x92, 0x8A, 0x0C, 0xB3, 0x7E, 0xD0, 0x7A, 0x47, 0x96, 0xE5, 0x26, 0x80, 0xAD, 0xDF,

        0xA1, 0x30, 0x37, 0xAE, 0x36, 0x15, 0x22, 0x38, 0xF4, 0xA7, 0x45, 0x4C, 0x81, 0xE9, 0x84, 0x97,

        0x35, 0xCB, 0xCE, 0x3C, 0x71, 0x11, 0xC7, 0x89, 0x75, 0xFB, 0xDA, 0xF8, 0x94, 0x59, 0x82, 0xC4,

        0xFF, 0x49, 0x39, 0x67, 0xC0, 0xCF, 0xD7, 0xB8, 0x0F, 0x8E, 0x42, 0x23, 0x91, 0x6C, 0xDB, 0xA4,

        0x34, 0xF1, 0x48, 0xC2, 0x6F, 0x3D, 0x2D, 0x40, 0xBE, 0x3E, 0xBC, 0xC1, 0xAA, 0xBA, 0x4E, 0x55,

        0x3B, 0xDC, 0x68, 0x7F, 0x9C, 0xD8, 0x4A, 0x56, 0x77, 0xA0, 0xED, 0x46, 0xB5, 0x2B, 0x65, 0xFA,

        0xE3, 0xB9, 0xB1, 0x9F, 0x5E, 0xF9, 0xE6, 0xB2, 0x31, 0xEA, 0x6D, 0x5F, 0xE4, 0xF0, 0xCD, 0x88,

        0x16, 0x3A, 0x58, 0xD4, 0x62, 0x29, 0x07, 0x33, 0xE8, 0x1B, 0x05, 0x79, 0x90, 0x6A, 0x2A, 0x9A

    };

 

    static array<Byte>^        S2 = {

        0x38, 0xE8, 0x2D, 0xA6, 0xCF, 0xDE, 0xB3, 0xB8, 0xAF, 0x60, 0x55, 0xC7, 0x44, 0x6F, 0x6B, 0x5B,

        0xC3, 0x62, 0x33, 0xB5, 0x29, 0xA0, 0xE2, 0xA7, 0xD3, 0x91, 0x11, 0x06, 0x1C, 0xBC, 0x36, 0x4B,

        0xEF, 0x88, 0x6C, 0xA8, 0x17, 0xC4, 0x16, 0xF4, 0xC2, 0x45, 0xE1, 0xD6, 0x3F, 0x3D, 0x8E, 0x98,

        0x28, 0x4E, 0xF6, 0x3E, 0xA5, 0xF9, 0x0D, 0xDF, 0xD8, 0x2B, 0x66, 0x7A, 0x27, 0x2F, 0xF1, 0x72,

        0x42, 0xD4, 0x41, 0xC0, 0x73, 0x67, 0xAC, 0x8B, 0xF7, 0xAD, 0x80, 0x1F, 0xCA, 0x2C, 0xAA, 0x34,

        0xD2, 0x0B, 0xEE, 0xE9, 0x5D, 0x94, 0x18, 0xF8, 0x57, 0xAE, 0x08, 0xC5, 0x13, 0xCD, 0x86, 0xB9,

        0xFF, 0x7D, 0xC1, 0x31, 0xF5, 0x8A, 0x6A, 0xB1, 0xD1, 0x20, 0xD7, 0x02, 0x22, 0x04, 0x68, 0x71,

        0x07, 0xDB, 0x9D, 0x99, 0x61, 0xBE, 0xE6, 0x59, 0xDD, 0x51, 0x90, 0xDC, 0x9A, 0xA3, 0xAB, 0xD0,

        0x81, 0x0F, 0x47, 0x1A, 0xE3, 0xEC, 0x8D, 0xBF, 0x96, 0x7B, 0x5C, 0xA2, 0xA1, 0x63, 0x23, 0x4D,

        0xC8, 0x9E, 0x9C, 0x3A, 0x0C, 0x2E, 0xBA, 0x6E, 0x9F, 0x5A, 0xF2, 0x92, 0xF3, 0x49, 0x78, 0xCC,

        0x15, 0xFB, 0x70, 0x75, 0x7F, 0x35, 0x10, 0x03, 0x64, 0x6D, 0xC6, 0x74, 0xD5, 0xB4, 0xEA, 0x09,

        0x76, 0x19, 0xFE, 0x40, 0x12, 0xE0, 0xBD, 0x05, 0xFA, 0x01, 0xF0, 0x2A, 0x5E, 0xA9, 0x56, 0x43,

        0x85, 0x14, 0x89, 0x9B, 0xB0, 0xE5, 0x48, 0x79, 0x97, 0xFC, 0x1E, 0x82, 0x21, 0x8C, 0x1B, 0x5F,

        0x77, 0x54, 0xB2, 0x1D, 0x25, 0x4F, 0x00, 0x46, 0xED, 0x58, 0x52, 0xEB, 0x7E, 0xDA, 0xC9, 0xFD,

        0x30, 0x95, 0x65, 0x3C, 0xB6, 0xE4, 0xBB, 0x7C, 0x0E, 0x50, 0x39, 0x26, 0x32, 0x84, 0x69, 0x93,

        0x37, 0xE7, 0x24, 0xA4, 0xCB, 0x53, 0x0A, 0x87, 0xD9, 0x4C, 0x83, 0x8F, 0xCE, 0x3B, 0x4A, 0xB7

    };

 

    static array<UInt32>^    KC = {

        0x9E3779B9, 0x3C6EF373, 0x78DDE6E6, 0xF1BBCDCC, 0xE3779B99, 0xC6EF3733, 0x8DDE6E67, 0x1BBCDCCF,

        0x3779B99E, 0x6EF3733C, 0xDDE6E678, 0xBBCDCCF1, 0x779B99E3, 0xEF3733C6, 0xDE6E678D, 0xBCDCCF1B

    };

 

    String^    G_Function(String^ strInput);

    String^    Encryption(void);

    void    SetPlaintext(String^ strPlaintext);

    void    SetKey(String^ strKey);

};


클래스 구성은 대략 이렇게 했고,

멤버함수는 ... 접어둡니다 ...
(오버로딩 된 함수나 입출력 관련된 함수는 길기만 하고 딱히 관계없으므로 생략합니다)

출처 - http://reinliebe.tistory.com/
RSA가 소인수분해의 어려움에 기반한 암호 알고리즘이라는 사실은 이미 지난 포스트에서 설명을 했습니다.
(관련 포스트 : http://reinliebe.tistory.com/79)

게다가 해독 사례도 이미 언급을 하였습니다 (관련 포스트 : http://reinliebe.tistory.com/83)

일단 앞서 언급한 내용과 더불어

오늘은 RSA 암호의 안전성에 대하여 알아 보겠습니다.

우선 RSA 암호를 공격한다는 의미는 공개키를 이용하여 암호문으로 부터 원 메시지를 복원 한다는 의미와 같은데, 아직까지는 소인수분해를 이용하여  φ(n) 과 d 를 계산하는 방법 말고 특별히 이렇다 할 효율적인 알고리즘이 알려져 있지 않다지요 ...

물론 소인수분해 외의 방법이 존재 할 지도 모르고요 ...

아무튼 이어서... RSA 암호의 공격 방법에 대하여 알아보아요 ...

▶ Protocol 공격

  - 작은 e를 사용하는 경우

  - 작은 d를 사용하는 경우

  - Multiplicative 특성을 이용한 공격

  - 여러 암호문을 보낼 때 공통의 modulus를 사용하는 경우

  - 순환 공격

  - 부분 키 노출 공격

  - Timing 공격

 

▶ 소인수분해 공격

  - Trial Division

  - Pollard rho 공격

  - Pollard p-1 공격

  - 타원곡선을 이용한 공격

  - Dixon's random square 공격

  - Quadratic sieve 공격

  - Number field sieve 공격

 

물론 이 밖에도 다양한 알고리즘과 공격 방법이 존재 할 수 있습니다.
(일단 참고한 자료들이 조금 오래된 자료기 때문에 지금은 더 효율적인 알고리즘들이 나왔을 것으로 추정됩니다만)

 

아무튼 이런 공격들로부터 안전한 RSA를 구현하기 위해
매우 큰 소수(1024bit 이나 2048bit 정도)를 사용하도록 권장하며,
소수를 선택함에 있어 아래와 같은 규칙을 갖게 됩니다.

▶ 소수 선택의 조건

  - 두 소수 p, q의 크기가 거의 같아야 함

  - p-q가 너무 작으면 안됨

  - p-1이 큰 수를 인수로 가져야 함

  - p+1이 큰 수를 인수를 가져야 함


출처 - http://reinliebe.tistory.com/
이전의 포스팅에서 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를 이용하여 전자서명을 하는 방법은 ...

 

▷ 전자서명

  메시지 ms = 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/

+ Recent posts