암호학을 위한 기본 수학 지식

 

 

암호학 수업이 있어서 공부를 하려는데 수학 지식이 없어서 조금씩 포스팅 하려고 한다. RSA는 어느 정도 알지만 RABIN 암호와 ElGamal 암호를 공부하다가 수학 지식이 없어서 공부하고 다시 도전하려고 한다.

 

1. 소인수 분해 문제

432 = 2*2*2*2*3*3*3 인데 소인수를 다항식 시간 안에 찾는 알고리즘은 아직까지 존재하지 않아서 풀기 어렵다고 한다.

 

 

2. 이산 대수 문제

y = g^x (mod p) 에서 y, g, p 3가지가 주어져도 x를 다항식 시간 안에 구하는 알고리즘이 존재하지 않는다. NP 문제이다.

 

 

3. 페르마의 소정리

p가 소수이면 어떤 a에 대해서 아래 식이 성립한다.

a^(p-1) = 1 (mod p)

 

4. 중국인의 나머지 정리

x = 1 (mod 5), x = 0 (mod 7), x=3 (mod 9) 3가지 값이 있다고 가정하자. 더 많은 값이 있어도 되지만 3가지 값으로 설명하겠다. M을 mod 값 들을 모두 곱한 값이라고 하자.

 

M = 5 * 7 * 9 = 315

 

M1, M2, M3는 각각 mod 값을 M에서 나눈 값이라고 하자.

 

M1 = 315 / 5 = 63, M2 = 315 / 7 = 45, M3 = 315 / 9 = 35

 

이제 M1, M2, M3에 대해 각각 역원을 구한다.

-> mod 값이 소수인 경우에는 페르마의 소정리로 빠르게 구할 수 있다. 쉬우니깐 생략

아닌 경우에는 유클리드 확장 알고리즘을 이용하면 된다. -> https://kbw1101.tistory.com/53

 

M3_1은 9가 소수가 아니므로 유클리드 확장 알고리즘으로 풀면 된다.

35를 9로 나눈 나머지는 8이므로 8의 역원을 구하겠다.

8 * (8의 역원) = 1 (mod 9) -> 9*s + 8*t = 1 (mod 9)

s와 t를 구하는데 t가 역원이다.

 

_______________________________________

|  q  |  r1  |  r2  |  r  |  s1  |  s2  |  s  |  t1  |  t2  |  t    |

-----------------------------------------------------------------

|  1  |   9  |   8  |  1  |   1  |   0   |  1  |   0  |   1  |  -1  |

|  8  |   8  |   1  |  0  |   0  |   1   |  -8 |   1  |   -1 |   9  |

|      |   1  |   0  |      |  1   |        |      |   -1   

 

s 값은 1이고 t 값은 -1 이다. 따라서 역원은 -1이다. 하지만 9를 더해서 8로 그냥 계산해서 아래처럼 계산한다.

-1로 해도 되는데 그냥 책에 8로 되어 있으니깐 8로 하겠습니다. 계산해보면 아마 똑같음..

 

 

M1_1 = 2(mod5), M2_1 = 5(mod 7), M3_1 = 8(mod 9)

 

구한 값들을 모두 곱해서 합친다.

 

mod값 * M1 * M1_1 + mod값 * M2 * M2_1 + mod값 * M3 * M3_1 (mod M)

-> 1*63*2 + 0*45*5 + 3*35*8 = 21 mod 315

-> x = 21

 

5. 오일러 판정법

모르면 그냥 외워라..증명의 길은 고난할텐데..

 

a^((p-1)/2) = 1 mod p -> a에 해가 존재한다.

a^((p-1)/2) = -1 mod p -> a는 해가 존재하지 않는다.

 

 

 

6. 오일러 정리

p가 소수일 때 ϕ(n) = p-1

서로소인 정수 m, n에 대하여, ϕ(m * n) = ϕ(m) *  ϕ(n)

 

ex) ϕ(10) = ϕ(2) * ϕ(5) = 1 * 4 = 4