아직 모르는게 너무 많아!

# n | a
  - a는 n의 배수이다.
 
# a mod n
  - a를 n으로 나누었을 때 나머지 값
 
# a ≡ b mod n
  - a와 b는 n으로 나누었을 때 그 나머지가 같다. (a와 b는 합동이다)
 
# 모듈러 연산의 특성
  - a ≡ b mod n 이면, a - b는 n의 배수이다. -> (a - b) mod n = 0
  - mod n = Zn = { 0, 1, ..., n - 1 }
 
# 모듈러 연산 법칙
  - [(a mod n) + (b mod n)] mod n = (a + b) mod n
  - [(a mod n) - (b mod n)] mod n = (a - b) mod n
  - [(a mod n) x (b mod n)] mod n = (a x b) mod n
 
# Galois Fields - GF(p) [아직 명확히 이해 못함. 위수가 단순히 원소의 개수인 것인지... 유한체는 뭔지...]
  - 소수 p에 대하여 위수가 p인 유한체
  - GF(p)는 정수 { 0, 1, ..., p-1 }의 집합 Zp로 정의
  - p가 소수이므로 Zn상의 모든 정수들에 대해 곱셈의 역원이 존재함

회사에서 세미나하는 내용인데 번개같이 넘어가는 바람에 뭔말인지 모르겠어요. ㅋㅋㅋ
이해도 할겸 복습하며 예문 위주로 정리합니다.
내가 이해한대로 정리한거라 틀릴수도 있으니 책임은 못 집니다.

# GCD(a, b) : a와 b의 최대 공약수 (Gratest Common Divisor)
ex) GCD(49, 21) = 7

# 서로소 : GCD(a, b) = 1 인 정수 a와 b를 서로소라 한다
ex) GCD(5, 7) = 1
ex) GCD(6, 11) = 1
ex) GCD(10, 21) = 1

# 소수 : 1 과 자신만으로 나누어지는 1보다 큰 양의 정수
ex) 2, 3, 5, 7, 11, 13, ...

# 합성수 : 소수가 아닌 양의 정수 (1과 자신 이외에 다른 값으로 나누어지는 자연수)
ex) 4, 6, 8, 9, 10, 12, 14, 15, ...

# 모든 정수(n > 1)는 소수의 곱만으로 표현할 수 있으며, 순서를 무시한다면 그 표현방법은 유일하다.
ex) 15 = 3 x 5
ex) 50 = 2 x 25 = 2 x 5 x 5
ex) 100 = 2 x 50 = 2 x 2 x 5 x 5

# 유클리드 알고리즘 : a = bq + r 이면 GCD(a, b) = GCD(b, r)
ex) 49 = 28 x 1 + 21 -> GCD(49, 28) = GCD(28, 21)
ex) 54 = 14 x 3 + 12 -> GCD(54, 14) = GCD(14, 12)
~ a를 b로 나눈 나머지(r)는 항상 최대 공약수의 배수이다. 따라서 b와 r의 최대공약수도 동일하다.

# 유클리드 호제법(互除法 : 번갈아가며 제거하는 방법)
- 유클리드 알고리즘을 반복적으로 적용하여 최대공약수를 구하는 방법
ex) 나머지가 0 이면 작은 값이 최대 공약수 

GCD(1020, 790)	1020 = 1 x 790 + 230
GCD(790, 230)	790 = 3 x 230 + 100
GCD(230, 100)	230 = 2 x 100 + 30
GCD(100, 30)	100 = 3 x 30 + 10
GCD(30, 10)	30 = 3 x 10 + 0

# 베주의 정의 (bezout's identity)
- 동시에 0이 아닌 두 정수 a, b에 대해서 GCD(a, b) = ax + by를 만족하는 정수 x, y가 존재한다.

# 확장 유클리드 알고리즘 : 베주의 정의 GCD(a, b) = ax + by의 해(x, y)를 구하는 방법
- 위 유클리드 호제법 풀이의 나머지 값 외에는 a, b를 대입할 수 있다.
- 이를 이용해 나머지가 최소공약수가 될 때 까지 나머지를 a와 b로 표현하는 방식으로 정리한다.
ex) 위 유클리드 호제법을 사용한 예제. 위 호제법 풀이의 오른쪽 풀어놓은 식에 대입
1020 = 1 x 790 + 230 (위 유클리드 호제법의 풀이에서 가져온 식)
-> a = 1 x b + 230 ^[각주:1]
-> 230 = a - (1 x b) = a - b ^[각주:2]
-> 따라서, 230 = a - b
790 = 3 x 230 + 100 (위 유클리드 호제법의 풀이에서 가져온 식)
-> b = 3 x (a - b) + 100 ^[각주:3]
-> 100 = b - (3 x (a - b)) = b - (3a - 3b) = -3a + 4b ^[각주:4]
-> 따라서, 100 = -3a + 4b
230 = 2 x 100 + 30 (위 유클리드 호제법의 풀이에서 가져온 식)
-> a - b = 2 x (-3a + 4b) + 30 ^[각주:5]
-> 30 = a - b - (2 x (-3a + 4b) = a - b - (-6a + 8b) = 7a - 9b ^[각주:6]
-> 따라서, 30 = 7a - 9b
100 = 3 x 30 + 10 (위 유클리드 호제법의 풀이에서 가져온 식)
-> -3a + 4b = 3 x (7a - 9b) + 10 ^[각주:7]
-> 10 = -3a + 4b - (3 x (7a -9b)) = -3a + 4b - (21a - 27b) = -24a + 31b ^[각주:8]
-> 따라서, 10 = -24a + 31b

10 은 GCD(1020, 790)의 해, 즉 최대공약수이므로 a와 b에 원래의 값을 대입하면
-> GCD(1020, 790) = -24 x 1020 + 31 x 790
-> a = 1020, b = 790 일 경우 GCD(a, b) = ax + by 를 만족하는 x와 y는
※ x = -24, y = 31

확인 : 1020 x -24 + 790 x 31 = -24480 + 24490 = 10

일단 용어 정리부터...
 
비밀키 : 일반적인 암호화에 사용되는 키. A와 B는 같은 비밀키를 공유해야 한다.
공개키 : 공개키 알고리즘에서 사용되는 키로 외부에 공개되는 키
개인키 : 공개키 알고리즘에서 사용되는 키로 개인이 소유하며 외부에 알려주지 않는 키
 
목적 - 공개키 알고리즘을 통해 비밀키를 생성하여 암호화에 사용한다.
 
DH 알고리즘의 핵심은 상대방의 공개키와 나의 개인키를 이용하여 계산을 하면 비밀키가 나온다는 것이다.
그 후 나와 상대방은 비밀키를 사용하여 데이터를 암호화한 후 전달하면 된다.
 
즉, A와 B 사이에서 사용할 비밀키를 생성하는 것을 식으로 나타내면 다음과 같다.
A의 비밀키 = A의 개인키 [DH연산] B의 공개키
B의 비밀키 = B의 개인키 [DH연산] A의 공개키
그리고 A의 비밀키 = B의 비밀키 
 
위 DH연산을 사용하면 A의 비밀키와 B의 비밀키는 같은 값이 나오기 때문에 이것을 암호화에 사용할 수 있는 것이다.
그럼 DH에서 사용하는 연산은 이런 조건을 만족한다는 뜻인데 이 연산은 어떤 것일까?
 
여기서 이번엔 기호 정리...
 
p = DH연산에 사용되는 소수 (1024 bits 이상)
g = DH연산에 사용되는 베이스, 특별한 수. (x1의 값에 따라 나오는 개인키의 종류가 정해진 g는 사용할 수 없다)
s = 비밀키
 
A의 작업
========
1. 임의의 개인키 x1을 생성하고 다음의 식으로 공개키(y1)를 계산한다.
   y1 = g^x1 mod p
2. B에게 자신의 공개키 y1을 전달한다.
B의 작업
========
3. 임의의 개인키 x2를 생성하고 다음의 식으로 공개키(y2)를 계산한다.
   y2 = g^x2 mod p
4. 전달받은 A의 공개키(y1)와 자신의 개인키(x2)를 이용하여 비밀키(s)를 계산한다.
   s = y1^x2 mod p
5. A에게 자신의 공개키 y2를 전달한다.
A의 작업
========
6. 전달받은 B의 공개키(y2)와 자신의 개인키(x1)를 이용하여 비밀키(s)를 계산한다.
   s = y2^x1 mod p
 
위의 결과에서 보면 비밀키(s)가 같으려면 다음의 공식도 만족해야 한다.
   y1^x2 mod p = y2^x1 mod p
위 공식에 y1과 y2를 생성할 때 사용했던 계산식을 넣어보자.
   (g^x1 mod p)^x2 mod p = (g^x2 mod p)^x1 mod p
 
여기서 더 나아가려면 다른 것에 대해서 먼저 알아야되겠다.
((x mod p) * (y mod p)) mod p = xy mod p
 
따라서
(g^x1 mod p)^x2 mod p 는 (g^x1)^x2 mod p 가 되고
(g^x2 mod p)^x1 mod p 는 (g^x2)^x1 mod p 가 된다.
 
그럼 (g^x1)^x2 mod p = (g^x2)^x1 mod p 가 되는데, 이정도 왔으면 왜 같은지 알 것이다. ^^;;
지수승은 곱으로 대체할 수 있으니
g^x1x2 mod p = g^x2x1 mod p 가 된다.
 
끝났다! 

아.. 제길... 이거 쓴다고 야근한 꼴이 되는구나...
((x mod p) * (y mod p)) mod p = xy mod p
이거 증명하려다가 시간 다 보냈다.. ㅠ_ㅠ
결국 증명은 제외 ㅎㅎ

// 상대방과 p와 g를 같은 값을 사용하고 상대방의 공개키를 알고 있는 상황
// p와 g와 자신의 개인키가 포함된 DH* pDH, 상대방의 공개키 BIGNUM* pPubKey
unsigned char abyKey[128]; // 128bit 키라면...
DH_compute_key(abyKey, pPubKey, pDH);

---

싸이 블로그 백업 [하지윤 2008.10.22 18:08]

// pDH에 이미 pDH->p, pDH->g가 세팅되어 있어야 함.
DH_generate_key(pDH);
// pDH->pub_key, pDH->pri_key 사용

---

싸이 블로그 백업 [하지윤 2008.10.22 18:00]

int nDHRet = DH_generate_parameters_ex(pDH, 1024, DH_GENERATOR_2, &g_cb); // 1024 bit에 g는 2로 생성.
if(!DH_check(pDH, &nDHRet))
{
   return;
}
if(nDHRet & DH_CHECK_P_NOT_PRIME)
   printf("p value is not prime\n");
if(nDHRet & DH_CHECK_P_NOT_SAFE_PRIME)
   printf("p value is not a safe prime\n");
if(nDHRet & DH_UNABLE_TO_CHECK_GENERATOR)
   printf("unable to check the generator value\n");
if(nDHRet & DH_NOT_SUITABLE_GENERATOR)
   printf("the g value is not a generator\n");
if(nDHRet == 0)
   printf("DH parameters appear to be ok.\n");

int nPBits = BN_num_bits(pDH->p); // p의 bit 크기 : 1024
int nGBits = BN_num_bits(pDH->g); // g의 bit 크기 : 2 (g가 5일땐 3)

싸이 블로그 백업 [하지윤 2008.10.22 17:55]

p가 소수이고, m이 p와 서로소인 양수일 때, (페르마의 정리)
m(p-1)  mod p = 1 
 
p와 q가 소수일 때, n = p*q, 그리고 m과 n은 서로소일 경우, (오일러의 공식)
m(p-1) (q-1) mod n = 1 
 
이것이 어떻게 사용되는지도 조만간...

---

싸이 블로그 백업 [하zi 2008.07.14 19:03]

"KDMLBRRQ"  이건 뭘까? 
 
이 글에서 이야기 할 시저의 암호화(encryption) 방법으로 암호화 된(encrypted) 암호문(ciphertext)이다. 
 
# 평문이란 암호화하기 전의 원래의 문장을 말한다.
# 일할때는 암호화라는 말은 거의 쓰이지 않는다. 온리 잉글리쉬... ㅡㅡ;;
 
명탐정 코난에서도 이것보다는 더 나은 암호화 방법을 썼던 것 같다. 음표였던가?
아주 단순한 암호화임에도 알아내기는 쉽지 않다.

시저는 이 암호화 방법을 사용하여 메시지를 전달하였고, 이 암호문을 풀기 위한 방법을 부하와 가족들에게 알려주었다.
 
암호화 함수는 우측 쉬프트였고 비밀키는 3이었다.
따라서 복호화 함수는 좌측 쉬프트다. ^^;;
 
글의 시작에 어울리는 쉬운 내용이라 설명 따위는 없다.
어차피 이건 암호학의 역사일 뿐...
 
근데 공개키에 대한 글 쓰려고 들어왔는데 지금 내가 왜 이걸 쓰고 있는걸까?
 
내가 이 블로그 만든 건 경력관리의 일환이라고~
근데 이런 쉬운 내용을 써놓으면 뭐하냐고~

싸이 블로그 백업 [2008.06.26 01:08]