베루의 보안공부

이차잉여란 해(근)를 가질 때, 정수 a을 법 m이며, 해(근)를 가지지 않을 때 정수 a을 법 m으로 한 이차비잉여 라고 한다.

이차잉여에서 집합 Z_m* 의 원소를 제곱해서 갑을 구할 수 있다.

이를 계산하기 위해선 오일러의 판정기준이 있다 

홀수인 소수 p와 (a, p) = 1인 정수 a에 대하여 성립한다.

Ⅰ) 정수 a가 이차잉여일 때 필요충분조건은 a^ p-1/2 ≡ 1(mod p)이다.

이때, 합동식 x^2 ≡ a (mod p)에서 꼭 두 개의 해를 가진다.

Ⅱ) 정수 a가 이차비잉여일 때 필요충분조건은 a^ p-1/2 ≡ -1(mod p)이다.

이차비잉여에서 필요충분조건이란 홀수인 소수를 뜻한다.

이때, 합동식 x^2 ≡ a (mod p)에서 해가 존재하지 않는다.

※이차잉여를 계산할 때 기약잉여계를 바탕으로 계산해야한다.

원시근을 하기에 앞서 먼저 배워야 할 것은 위수(order)이다.

(a, m) = 1이 성립되고  a^r ≡ 1 (mod m)을 만족하는 정수 중에서 가장 작은 양의 정수 r(나머지)을 법 m, p에 관한 a의 위수이다.

예시로 들자면 법 7에 관한 2의 위수를 구하여라

2^r ≡ 1(mod 7)을 만족하는 가장 작은 양의 정수 r을 구할 때 2^1 ≡ 1(mod 7), 2^2 ≡ 4 (mod 7),  2^3 ≡  1(mod 7)

법 7에 관한 2의 위수는 3 ≤ ∂(7) = 6이다. 즉 ord_7 2 = 3이다. 

법 7에 관한 3의 위수에서 3^r ≡ 1(mod 7)일 때 3^1 ≡  3 (mod 7), 3^2 ≡  2 (mod 7), 3^3 ≡  6 (mod 7), 3^4 ≡  4 (mod 7), 3^5 ≡  5 (mod 7), 3^6 ≡  1 (mod 7)이며 법 7에 관한 3의 위수는 r = 6이다.  

위수:ord_7 3 = 6인 것이다.

※계산할 때 오일러 피 함수로 모듈러 m, p를 먼저 구하고 나온 값 만큼 거듭제곱을 해야한다. (1 ~ m-1 까지)

n | ∂(m) 은 약수배수 관계이다. 또한 ∂(m)은 원소의 개수와 같다.

원시근과 위수는 꽤나 비슷하다. ord_m a =  ∂(m) 동일한 값이 나오면 원시근, ord_m a 일 때 위수인 것이다.

원시근은 2, 4, p^k, 2p^k만 존재하고 그 이상에 합성수는 존재하지 않는다. 

값이 있더라도 그 값은 해가 될 수 없다.

존재하는 경우는 집합 Z^* p인 기약잉여계 즉 소수일 때만 존재한다.

일차합동식은 일차방정식과 같은 형태지만 합동식이 들어가 있어 일차합동식이라 부른다.

식으로 표현하자면 ax+ b ≡ 0 (mod ⁡m)에 형태이다.

일차방정식이 있듯이 이차방정식이 있고 당연히 이차합동식 또한 존재한다.

x^2 + 1 ≡ 0 (mod 5)일 때  , f(x) = x^2 + 1 ≡ 0 (mod 5)

f(0) = 1 ≡ 1 (mod 5) ,  f(1) = 2 ≡ 2 (mod 5), f(2) = 5 ≡ 0 (mod 5)

f(3) = 10 ≡ 0 (mod 5), f(4) = 17 ≡ 2 (mod 5)

그로 인해 해가 존재하는건  x ≡ 2 (mod 5), x ≡ 3 (mod 5)가 이차합동식의 해이다.

답을 작성할 때 해가 존재하는 경우 위와 같이 적어주고 해가 존재하지 않을 경우 해가 존재하지 않다. 라 작성하면 된다.

위 식에서 계산은 덧셈으로 하였을 때 항등원은 0이며, m = 5 이므로 5 = {0 ,1, 2, 3, 4}로 f(x)의 x값안에 차례대로 대입하여 계산한다.

반대로 

만약 식이 곱셉이였을 때 항등원은 1이며, m 또는 p로 0을 제외한 수로 대입하며 계산해야한다.

일차 합동식 ax ≡ b (mod m)이 해를 가지기 위해 필요충분조건 d = (a, m)과 d | b일 때 성립된다. 

d = (a, m) = gcd (a, m) 즉 최대공약수 1이 되야하며, d | b의 수가 약수, 배수 관계가 되면 가능하다.

위 식의 경우 곱셈으로 되어있는 일차합동식인데 (a x s) + (b x t) = 1이 성립이 되어야 하며, 식을 풀어 나갈 때 "확장된 유클리드 알고리즘"으로 계산 해야한다. 

r = r_1 - (q × r_2 ), S = S1 - (q × S2 ), t = t1 (q x t2 )

r = 나머지

Wilson의 정리란 임의의 소수 p에 대하여 (p - 1)! ≡ -1 (mod p)이고 p는 소수, m은 합성수이다.

예시로 작성한 식으로 p = 5에 대하여 (p - 1)! ≡ -1 (mod p)가 성립함을 보여라

소수

법 5에서 1과 합동인 p-3/2 = 1개가 나온다.

5의 소수는 5 = {2, 3}

2 x 3 ≡ 1(mod 5)

( 2 x 3 ) ≡ 1 (mod 5)

3! ≡ 1 (mod 5)

양변에 6을 곱하면 

6! ≡ 6 (mod 5)

이고

6 ≡ -1 (mod 5)

이기에

6! ≡ -1 (mod 5) 이다.

합성수

(8-1)! = 7!  = 5040 ≡ 0 (mod 8)

윌슨의 정리는 팩토리얼과 유사하다 생각하면 편하다.

▶팩토리얼은 1부터 지정된 수 만큼 곱하는 방식이다.

소수 p일 때는 값이 -1, 합성수 m 일 때 0이 나온다.

역원이란 두 원소를 연산한 결과가 항등원일 때, 한 편에 대하여 다른 편을 이르는 말이다. 덧셈에서의 반수와 곱셈에서의 역수를 일반화한 개념이다.

곱셈의 항등원은 a x b ≡ 1 (mod m), 덧셈의 항등원은 a + b ≡ 0 (mod m)이다.

모듈러 연산에서 각각의 정수는 덧셈, 곱셈에 대한 역원을 갖는다. a * b, a + b의 합동은 1과 0이다.

위 연산이 자기자신도 물론 가능하다. 단 m값보다 작게 나와야 한다. 

a = 8, b = 6, m = 49으로 계산하면 a x b = 48 ≡ 1 (mod 49) 

※ mod 모듈러는 나눗셈이라 생각하면 편하다.

임의의 정수 a ∈ Zm 가 곱셈에 대한 필요충분조건은 gcd(a, m) = 1이 되어야 한다. 

위 조건은 무조건 성립해야한다. 

m의 값이 소수일 경우 곱셈이 역원이 존재, m의 값이 합성수일 때 존재하거나 존재하지 않는다. 

역원을 구할 때는 "확장된 유클리드 알고리즘"을 이용한다.

(m x s) + (b x t) = gcd(m, b) 

이때도 gcd(m, b) =1, 최대공약수 1이 꼭 되어야 한다. 

즉 (m x s) + (b x t)  = 1 ↔  b x t ≡ 1 (mod m)과 같다.   

합동식이란 정수의 합과 곱을 어떤 주어진 수의 나머지에 대하여 정의하는 방법이다.

 modular라 말하며, 계산에서 "mod"로 쓰이는 모듈러 연산자이다.

mod는 × 나 ÷ 와 동일하게 쓰인다.

식으로 표현하면 17 mod 14 = 3으로 나타낼 수 있다.

(17을 14로 나누면 나머지가 3 이랑 동일하다)

https://beru-123.tistory.com/11 에서 나눗셈과 관계식에 대해 설명한 이유는 합동식에서 계속해서 사용하였기에 참고하면서 공부하면 많은 도움이 된다. 

mod m(합성수), p(소수)은(는)  z = { 1, 2, 3, 4, 5} 등과 같은 정수 집합을 가지고 합동식에 사용이 되며, -1과 같은 마이너스의 값일 경우 mod "m", "p"일 때 "역원"을 사용하여 계산한다. 

예시로 설명하자면 -49 mod  15 일 때, 15를 구구단식으로 사용한다. 15 x 2 = 30, 15 x 3 = 45 이를 말하는 거와 같다.

아무튼 다시 식을 계산하면 -49는 45로 계산할 때 모듈값 -4가 나오므로 식이 성립되지 않는다 하지만 15 x 4 = 60이다.

그렇다면 60 - 49 = 11이다. 

즉, ∴  -49 mod 15 ≡ 11 이 답을 말한다. 

-4 = 11과 동일하다는 게 합동식 역원에 의미를 뜻한다.

11은 역원, 모듈러는 15, 나눠야 할 수는 -49 인 것이다.  

합동식의 동치관계

a ≡ a (mod m) : 반사 관계

a ≡ b (mod m) 이면 b ≡ a (mod m)이다. : 대칭관계

a ≡ b (mod m)이고 b ≡ c (mod m)이면  c ≡ a (mod m)이다 : 추이관계

임의의 정수인 법(집합) m에 관하여 m = 숫자만큼 반드시 합동이다. 

두 정수 a와 b에 대하여 다음 성질을 동치이다.

1. a - b가 m의 배수이며, a - b = mk, (k ∈ Z)이다.
2. a와 b는 m을 법으로 합동이다. a ≡ b (mod m)이다.
3. gcd(a, m) = gcd(b, m)이다. 

※ gcd는 최대공약수를 뜻하며, 동치관계는 알아두면 좋다.  

이해가 안 돼 신다 하면 댓글로 최대한 설명하겠습니다.

암호학에서 키, 키쌍은 모두 정수의 형태를 가지고 있고 "소수"를 기반하고 있다.

그 이유는 144자리 이상에 소수를 나누라고 하면 어느 값을 기준으로 그 값을 만들었는지 모르기 때문이다. 

크게 3가지로 본다면 "소수로 이뤄진 합성수", "합성수", "소수"로 분류하며 어느 게 좋다 물어보면 서로 상황에 맞게 쓰이기 때문에 판단하기 어렵다.

위 표와같이 나타낼 수 있고 소수가 왜 중요한지는 합동식을 들어갈 때 설명을 하도록 하겠다.

다음 설명으로 소인수 분해는 1보다 큰 자연수를 소인수(소수인 인수)들만의 곱으로 나타내는 것 또는 합성수를 소수의 곱으로 나타내는 방법이다.

위 그림과 같이 이진트리 형식으로 나타낼 수 있고 식으로 나타내면 864 = (2^5) x (3^3) 으로 보일 수 있다. 

소인수 분해 또한 소수와 동일하게 합동식에서 중요한 역할을 수행한다. 소수를 나눌 때 소인수 분해를 사용한다 하지만 키 값을 가져갔다 했을 때 무슨 수로 나눌건지 정확히 알 수 없기에 중요 포인트중 하나라고 생각해두면 편하다.

다음 글에선 본격적으로 암호 수학의 시작인 합동식을 알아보도록 하겠다.

현대 암호로 들어올 때 정보통신과 컴퓨터의 발달로 인해 암호학이 발달하는 계기가 탄생하였다.

컴퓨터 중심으로 발달된 암호알고리즘은 대표적으로 RSA 알고리즘( Ron Rivest,  Adi Shamir, Leonard Adleman Algorithm) , 디피 헬만 알고리즘(Diffie-Hellman Algorithm)이다. 

RSA와 DH알고리즘의 공통점은 "합동식"을 기반으로 만들어졌으며, 어렸을 때 배웠던 최대공약수, 정수 등을 자주 사용하게 된다. 

합동식 : a ≡ b( mod m )

미국의 CIA는 모두가 알 것이다. 기밀성(Confideniatlity) 무결성(Integration) 가용성(Availblity)을 시작으로 암호 알고리즘에 "필수"로 들어가게 되어야 하며, 시간이 지난 후 부인방지(Non-repudiation)가 들어가야 한다는 새로운 조건이 추가되었다.

RSA 알고리즘

DH 알고리즘

보안에 대한 경각심이 생기게 된 여러 사건이 나오면서 자연스럽게 암호학 또한 발달을 하였다. 암호학은 수학과 관련이 있다 보니 기존 알고리즘의 새로운 수식을 합치면서 현재까지 쓰이고 있다. 

기초 역사에 대해서는 여기까지 작성하여, 작성자가 공부를 어느정도 끝 마치고 여유가 생긴다면 차 후 "미래의 암호 알리즘으로 쓸 수 있는 양자 암호"에 대해 다뤄보겠다