'Etc../Encryption'에 해당되는 글 3건

  1. 2010.06.16 Cryptography!
  2. 2009.11.06 What is CRC?
  3. 2009.10.31 What is Padding?

2010.06.16 00:53 Etc../Encryption

대칭키 & 비밀키 (Symmetric-key cryptography &  private key)

대칭키 OR 비밀키로 불리는 암호화는 송,수신자가 같은 키를 사용하여 부호화, 복호화 하는 것을 말합니다




[+]블록 암호화

 정해진 비트 길이의 정보를 암호화하는 암호 방식으로, 이때의 정보 단위를 블록이라고 부릅니다. 만약 암호화하려는 정보가 블록 길이보다 길 경우에는 블록 암호를 바로 이용할 수 없기 때문에, 특정한 운영 모드가 사용됩니다

이 운영 모드는 각 블록들간의 연관성 또는 의존성을 주는 방식이라고 보면 되죠

-운영모드

Ex) ECB, CBC, PCBC, CFB, OFB, CTR








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


블록 암호의 일종으로, 미국 NBS (National Bureau of Standards, 현재 NIST)에서 국가 표준으로 정한 암호.

일반적인 DES는 현재 취약한 것으로 알려져 있습니다




Key Sizes : 56bits

Block Sizes : 64 bits

Rounds : 16

많은 회사들이 세개의 키가 잇달아 적용되는 'Triple DES' 사용


http://en.wikipedia.org/wiki/Data_Encryption_Standard































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

DES를 대체하기 위한 목적으로 등장.  미국정보 표준으로 지정된 암호 형식


Key Sizes  : 128, 192 or 256  bits

Block Sizes : 128 bits

Rounds : 10, 12 or 14 [ depending on key size ]

http://en.wikipedia.org/wiki/Advanced_Encryption_Standard

High-level description of the algorithm

  1. AddRoundKey—each byte of the state is combined with the round key using bitwise xor
  • Rounds
  1. SubBytes—a non-linear substitution step where each byte is replaced with another according to a lookup table.
  2. ShiftRows—a transposition step where each row of the state is shifted cyclically a certain number of steps.
  3. MixColumns—a mixing operation which operates on the columns of the state, combining the four bytes in each column.
  4. AddRoundKey
  • Final Round (no MixColumns)
  1. SubBytes
  2. ShiftRows
  3. AddRoundKey



Blowfish

마찬가지로 DES를 대체하는데 사용될 수 있는 암호화 알고리즘. 32~ 488 비트까지 가변적인 길이의 키를 사용하는 대칭 블록.

미국 내 뿐만 아니라 수출용으로도 이상적으로 사용될 수 있다는군요.


http://en.wikipedia.org/wiki/Blowfish_(cipher)






[+]스트림 암호화

 스트림 암호에서는 연속적인 데이터 입력을 하나씩 받으면서 암호화한다. 하지만 블록 암호에서도 OFB나 OTR 등의 운영 모드를 사용할 경우 스트림 암호처럼 사용할 수 있는 등, 두 암호 사이의 구분이 확실한 것은 아님.

http://en.wikipedia.org/wiki/Stream_cipher

Ex) A5/1, A5/2, RC4, SEAL,

HASH

모든 해시 함수의 가장 기본적인 성질은 두 해시 값이 다르다면 원래의 데이터도 어딘가 다르다는 것.

같은 해시 값을 가진다면, 원래의 입력값이 같다는 것을 시사하지만 보장해주지는 않음.

원래 입력의 한 비트만 바뀌더라도 해시 함수의 성질로 인해 해시 값은 크게 달라집니다.

Ex) MD5, SHA

http://en.wikipedia.org/wiki/Hash_function


A hash function that maps names to integers from 0 to 15. There is a collision between keys "John Smith" and "Sandra Dee".








공개 키 암호화(Public-key cryptography)


신뢰할 수 있는 기관에서 부여된 한쌍의 공개키와 개인키를 사용함으로써, 안전하고 은밀하게 데이터나 자금을 교환 할 수 있게 함.

대칭키 암호화의 경우 여러 사용자가 사용하려면 (n*(n-1)/2)  대칭키가 필요하게 되고 이러한 생성과 분배는

유지, 관리를 어렵게 하는 문제점이 있을 뿐더러, 인터넷과 같은 개방형 시스템에서 동일한 대칭키를 가지는 것은

위험하기 때문에 공개키 암호화 방식이 등장하게 되었습니다


[+]PKI 구성 요소

1. 디질털 인증서를 발급하고 검증하는 인증기관

2. 공개키 또는 공개키에 관한 정보를 포함하고 있는 인증서

3. 디지털 인증서가 신청자에게 발급되기 전에 인증기관의 입증을 대행하는 등록기관

4. 공개키를 가진 인증서들이 보관되고 있는 하나 이상의 디렉토리

5. 인증서 관리 시스템



[+] 동작 원리


다음의 일을 하기 위해 ...
누구 것을 사용?
어떤 키를 사용?
암호화된 메시지를 송신
수신자의
공개키
암호화된 서명을 송신
송신자의
개인키
암호화된 메시지의 해독
수신자의
개인키
암호화된 서명의 해독 (그리고 송신자의 인증)
송신자의
공개키





[+] 키의 생성

  1. p \,와 q \, 라고 하는 두 개의 서로 다른 (p \ne q소수를 고른다.
  2. 두 수를 곱하여 N = p q \, 을 찾는다.
  3. \varphi(N) = (p-1)(q-1) \, 를 구한다.
  4. \varphi(N) 보단 작고, \varphi(N)와 서로 소인 정수 를 찾는다.
  5. 유클리드 호제법을 이용하여 d e \equiv 1 \pmod{\varphi(N)} 을 만족시키는 를 구한다.

A의 공개키는 위에서 구한 두 개의 숫자로 이루어진 <Ne>이고, 개인키는 이다. A는 <Ne>만을 B에게 공개하고, B는 이 공개키를 사용하여 자신의 메시지를 암호화하게 된다. 여기서 와 의 보안은 매우 중요하다. 이를 가지고 와 의 계산이 가능하기 때문이다. 그리하여 공개키와 개인키가 생성이 된 후에는 이 두 숫자를 지워버리는 것이 안전하다.




- 유클리드 호제법

2개의 자연수의 최대공약수를 구하는 알고리즘의 하나

문제) 1071과 1029의 최대공약수를 구하라.
  • 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. => 42
  • 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. => 21
  • 42은 21로 나누어 떨어진다.

따라서, 최대공약수는 21이다.





- 확장된 유클리드 호제법

정수 m, n 의 최대공약수(Greatest Common Divisor)를 gcd(m,n)와 나타낼 때,

확장된 유클리드 호제법을 이용하여,

am + bn = gcd(m,n)의 해가 되는 정수 a, b 짝을 찾아낼 수 있다. 위에서 든 예의 경우,

1071 = 1 * 1029 + 42 
1029 = 24 * 42 + 21 
42 = 2 * 21 

이므로

21 = 1029 - 24 * 42 = 1029 - 24 * (1071 - 1 * 1029) = -24 * 1071 + 25 * 1029 

가 된다.

특히, m, n이 서로소(최대공약수가 1)인 경우, am + bn = c는 임의의 정수 c에 대해서 정수해 (a,b)가 존재한다.


'Etc.. > Encryption' 카테고리의 다른 글

Cryptography!  (0) 2010.06.16
What is CRC?  (0) 2009.11.06
What is Padding?  (0) 2009.10.31
Posted by LinkC

2009.11.06 09:53 Etc../Encryption


순환 중복 검사(巡環重復檢査), CRC(cyclic redundancy check)는 네트워크 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크값을 결정하는 방식을 말한다.

데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다. 이어서 두 값을 비교하고, 이 두 값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것 임을 알 수 있다.

CRC는 이진법 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 흔한 오류들을 검출하는 데 탁월하다. 하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터의 무결성을 검사하는 데는 사용될 수 없다. 이런 용도로는 MD5 등의 함수들이 사용된다.


CRC는 가환환(commutative ring)의 나눗셈에 기반한다. 여기서 쓰이는 환은 법 2 (modulo 2) 정수에서 정의된 다항식의 환이다. 쉽게 말하면, 이는 한 비트의 계수를 갖는 다항식의 집합이고, 이 다항식들간의 사칙연산은 다시 계수들을 가장 아래 비트만 따도록 정의하여 한 비트 계수의 다항식으로 표현하도록 정의된다. 예를 들면:

(x2 + x) + (x + 1) = x2 + 2x + 1 = (x + 1)2

위 식에서 2는 이진수로 10이고, 따라서 정의에 의해서 가장 아랫자리 수(또는, 가장 아래 비트)인 0을 취하고 그 이상의 자리수는 버린다. 다음은 곱셈의 예이다:

(x2 + x)(x + 1) = x3 + 2x2 + x = x3 + x

더하기와 곱하기 말고 나누기도 정의할 수 있다. 예를 들어, x3 + x2 + xx + 1 로 나눈다고 해 보자.

x3 + x2 + x = (x + 1)(x2 + 1) − 1 = (x + 1)(x2 + 1) + 1.

으로 정리할 수 있다. 다시 말하면, 나눗셈의 몫은 x2 + 1 이고 나머지는 -1 이고, -1은 홀수이기 때문에 1이 된다.

모든 데이터 비트 스트림은 이러한 다항식의 계수로 상상할 수 있다. 즉, 101 은 0번자리가 1, 1번자리가 0, 2번자리가 1이므로, 다항식 x2 + 1에 해당한다고 볼 수 있다. CRC 값은, 정해진 특정 다항식으로 데이터 스트링으로 주어진 다항식을 나누어 그 나머지를 나타내는 특정 길이의 비트 스트링이 된다. 이 나머지를 구하는 간단하고 빠른 알고리즘은 잘 알려져 있다. CRC는 종종 체크섬(checksum)으로 불리는데, 엄밀히 말하면 나눗셈을 통해 얻어지는 CRC 값에는 옳지 않은 이름이다.

CRC의 중심을 이루는 알고리즘은 의사코드로 다음과 같이 쓸 수 있다:

function crc(bit array bitString[1..len], int polynomial) {
    shiftRegister := initial value // 보통 00000000 또는 11111111
    for i from 1 to len {
        if (shiftRegister의 최상위 비트) xor bitString[i] = 1
            shiftRegister := (shiftRegister left shift 1) xor polynomial
        else
            shiftRegister := shiftRegister left shift 1
    }
    return shiftRegister
}

(참고: 실제로는 여러 개의 최상위 비트들에 해당하는 shiftRegister의 표를 만들어서 한꺼번에 여러 비트를 처리해 속도를 높이는 방법을 쓰며, 특히 8비트 단위로 처리하는 방법이 많이 사용된다.)

위의 구현은 다음과 같은 두 가지 방법으로 고칠 수 있으며, 따라서 둘 중 하나를 적용하거나 둘 다 적용할 경우 CRC 값을 계산하는 네 가지 동등한 방법이 존재한다:

  1. shiftRegister를 비트 단위로 뒤집고, 각 단계에서 최하위 비트를 테스트한 뒤 오른쪽으로 1비트 쉬프트한다. 이 경우 polynomial의 값을 비트 단위로 뒤집어야 하고, 결과물 역시 비트 단위로 뒤집어진다.
  2. shiftRegister의 한 비트와 bitString의 한 비트를 xor하는 대신에, shiftRegisterbitString에서 polynomial에 설정된 비트에 해당하는 모든 비트들을 xor한 1비트 결과를 shiftRegister에 더한다. polynomial을 적당히 고치면 같은 나머지를 얻을 수 있다. 이 방법은 소프트웨어에서 구현하기는 힘들지만 하드웨어 구현에서는 종종 사용되며, CRC와 깊은 관련이 있는 선형 피드백 쉬프트 레지스터를 설명하는 데 자주 사용된다.

특정한 CRC는 사용되는 다항식으로 정의한다. n비트 CRC를 만드는 데는 xn + ... + 1 꼴의 n차 다항식이 필요하다. 이 다항식은 기본적으로 (n+1)비트 문자열로 나타낼 수 있지만, 차수가 가장 높은 xn 항의 계수는 항상 1이기 때문에 이 항을 빼고 n비트 문자열로 나타낼 수 있다. 예를 들어 CRC-16 표준에 사용되는 다항식인 x16 + x15 + x2 + 1은 비트 순서에 따라서 16진수 숫자 0x8005나 0xa001로 나타낼 수 있으며, 이더넷, FDDI, PKZIP, WinZip, PNG 등에서 널리 사용되는 CRC-32의 경우 0x04C11DB7 또는 0xEDB88320으로 쓸 수 있다.


출처: http://ko.wikipedia.org/wiki/%EC%88%9C%ED%99%98_%EC%A4%91%EB%B3%B5_%EA%B2%80%EC%82%AC

'Etc.. > Encryption' 카테고리의 다른 글

Cryptography!  (0) 2010.06.16
What is CRC?  (0) 2009.11.06
What is Padding?  (0) 2009.10.31
Posted by LinkC
 TAG CRC, CRC-32, crc32

2009.10.31 15:33 Etc../Encryption


 

패딩은 무엇인가?

ECB, CBC 모드의 DES, Blowfish 같은 블럭 암호 알고리즘은 암호 입력이 블럭 크기의 정확한 배수가 되어야 한다.
만약, 암호화될 평문이 정확한 배수가 아니면, 암호화전에 패딩 데이터를 추가하는 것이 필요하다.
복호화할때, 수신측은 명백한 방법으로 패딩을 제거하는 방법을 알아야 한다.



5가지 일반적인 방법.

1. 패딩되는 바이트의 수의 같은 값으로 모두 패딩 : PKCS7 패딩
2. 0x80 패딩 후 0으로 패딩
3. 0으로 패딩 후 마지막 바이트는 패딩되는 바이트의 수로 패딩 : ANSIX923 패딩
4. 0으로 패딩 : Zeros 패딩
5. 0x20으로 패딩



랜덤 패딩

만약 전송할 메시지가 블럭 길이보다 작고, ECB 모드로 암호화된다면, 암호문은 동일한 메시지에 동일한 값이 될것이다.
한 해결책은 위 3번째 방법을 사용하되, 0 대신 랜덤 값을 패딩해라.




언제 패딩을 해야하고 언제 안해야 하나?

1. 일반적인 방법으로, 만약 프로그래머로서 당신이 제어할 수 없는 가변 길이의 데이터를 암호화한다면,
CBC 모드로 패딩해라. 모호함을 피하기위해서, 패딩을 추가하는 표준 방법을 항상 사용해라.
2. 만약 평문이 항상 고정 길이를 가진다면, 패딩 사용을 피할 수 있다. -> 고정 길이와 블록 길이가 같다는 조건이 필요
3. 암호화에 CFB 또는 OFB 모드가 사용되거나 RC4 등 스트림 암호 알고리즘이 사용된다면, 패딩을 할 필요가 없다.

출처 : http://www.di-mgt.com.au/cryptopad.html



 

NET Framework Class Library

(System.Security.Cryptography, PaddingMode Enumeration)

대부분의 일반 텍스트 메시지는 블록의 바이트 수가 완전히 채워져 있지 않으므로 마지막 블록을 채우기에 바이트가 모자란 경우가 가끔 있습니다. 이런 경우에는 택스트에 패딩 문자열이 추가됩니다. 예를 들어, 블록 길이가 64비트이고 마지막 블록에 40비트만 있으면 패딩 문자열 24비트가 추가됩니다.

일부 암호화 표준이 특정한 패딩 구성표를 지정합니다. 다음 예제에서는 이러한 모드의 작동 방식을 보여 줍니다. 블록 길이가 8, 데이터 길이가 9, 8진수 패딩 수가 7 그리고 데이터가 FF FF FF FF FF FF FF FF FF인 경우 결과는 다음과 같습니다.

데이터: FF FF FF FF FF FF FF FF FF
a. None : FF FF FF FF FF FF FF FF FF
아무 것도 채워지지 않았습니다(*. 파일 암호화시 문제가 발생한다).

b. X923 패딩: FF FF FF FF FF FF FF FF FF 00 00 00 00 00 00 07
ANSIX923 패딩 문자열에서는 마지막 바이트를 총 패딩 바이트 수로 설정하고 나머지 바이트는 0으로 채웁니다.

c. PKCS7 패딩: FF FF FF FF FF FF FF FF FF 07 07 07 07 07 07 07
PKCS #7 패딩 문자열은 바이트 시퀀스로 구성되어 있으며, 각각의 시퀀스는 추가된 패딩 바이트의 전체 수와 동일합니다. 

d. ISO10126 패딩: FF FF FF FF FF FF FF FF FF 7D 2A 75 EF F8 EF 07
ISO10126 패딩 문자열에서는 마지막 바이트를 총 패딩 바이트 수로 설정하고 나머지 바이트는 임의의 데이터로 채웁니다.

e. Zeros 패딩 : FF FF FF FF FF FF FF FF FF 00 00 00 00 00 00 00
패딩 문자열은 0으로 설정된 바이트로 구성됩니다.

출처 : MSDN


'Etc.. > Encryption' 카테고리의 다른 글

Cryptography!  (0) 2010.06.16
What is CRC?  (0) 2009.11.06
What is Padding?  (0) 2009.10.31
Posted by LinkC
이전버튼 1 이전버튼

블로그 이미지
LinkC

태그목록

Tistory Cumulus Flash tag cloud by BLUEnLIVE requires Flash Player 9 or better.

공지사항

Yesterday301
Today84
Total298,301

달력

 « |  » 2018.02
        1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28      

최근에 받은 트랙백

글 보관함


. .