암호화 기법 이해

 

웹에서 패킷은 여러 단계를 거쳐가기 때문에

악의의 목적을 가진 사람이 패킷을 낚아채서 사용자의 개인정보를 알 수 있거나 변조해서 엉뚱한 값을 전송할 수 있다.

이를 방지하기 위해 암호화 기술이 발전하였다.

크게 암호화에 사용되는 키와 복호화에 사용되는 키가 같은지 여부에 따라 대칭키 방식과 공개키(비대칭) 방식이 존재한다.

우선 대칭키 암호화에 사용되는 방법은 순서 바꾸기, 자리바꾸기,  비트 연산 (<< >> 같은 시프트 연산이나 특정 키로 xor 연산) 등이다.

대칭키 기법 여러 사이트 뒤져가면 읽어보면 다른건 그렇게 어렵지 않고, xor 연산이 평상시에 자주 써먹지 않아서 조금 낯설 수 있다.

일단 컴퓨터 소스코드에서 xor연산은 ^로 표시합니다. ^가 제곱을 의미하는 지수승이 아님을 유의하세요.

P ^ K로 xor 연산을 수행 후 이 값을 다시 ^ K하면 원래의 P값으로 돌아옵니다.

비트 연산이므로 0, 0의 경우 / 1, 0의 경우 / 0, 1의 경우 / 1, 1의 경우 즉  4가지 경우가 전부이므로

xor에 따른 비트값의 변화과정을 살펴보면 이해할 수 있다.

여기서 K가 흔히 말하는 키입니다. xor 연산의 이런 성질은 암호화에 정통으로 써먹을 수 있겠죠.

xor 연산의 성질: https://ko.wikipedia.org/wiki/배타적_논리합 을 참조하면 된다. 

암호화에 사용되는 성질은 다시 말하지만 (P^K)^K하면 다시 P로 복원된다는 부분입니다.

대칭키 알고리즘이 이런 연산들을 섞으면서 수십번 혹은 수백번 수행해도 이 알고리즘을 역순으로 수행하면 원래의 평문을 얻을 수 있다.

그래서 아무리 복잡하게 해도 보안에 취약할 수 밖에 없다. 웹상에서 대칭키나 암호화 알고리즘 코드 역시 상대에게 전송해야 되는데,

패킷을 낚아채는 해커는 이 모든 정보를 얻게 된다. 물론 암호화된 문자들을 보면 머리가 지끈거리고 해석 시도를 포기하는 일반유저들에게는 소용이 있을 것이다.

비대칭 방식은 굉장히 획기적인 방식입니다. 미지의 수학적 난제를 암호화 기법에 적용하는 발상의 전환입니다.

실제 인터넷에 적용되는 형태는 해커가 중간에서 키(공개키라고 함)와 알고리즘을 가로채도

이 정보로는 도저히 평문으로 복원하기가 지난합니다.

(개인키를 얻으려면 소인수분해를 해야 되는데 이게 슈퍼컴퓨터로 수십년 걸린다고 함. 키가 더 길면 더 증가)

사실상 평문 복원은 개인키를 가진 쪽에서만 가능합니다. 따라서 공개키와 알고리즘만 보내줘도 되고

악의에 해커에게 공개키가 탈취당해도 복호화가 지난하므로 보안에 획기적인 방식이죠.

보내는 쪽에서 공개키로 암호화를 해서 보내면,,, 받는 쪽에서 소중히 간직하고 있는 개인키로 복호화해서 원래의 평문을 얻게 됩니다.

암호화와 복호화에 필요한 키가 2개(1쌍) 존재하는데. 나중에 알고리즘 해석하면서 자세히 알게되겠지만

이 둘은 어느 키로 암호화하면 다른키로 복호화를 할 수 있는 관계에 놓여 있습니다. 두개의 키 중 한쪽을 골라서 공개키라고 명명합니다.

공개하거나 아무나 알아도 괜찮다는 의미입니다. 다른 하나는 개인키로 노출되지 않도록 철저하게 보안에 신경써야 합니다.

공개키(비대칭) 방식에도 단점이 있는데 연산에 시간이 오래 걸리는 점입니다.

매우 큰 단위의 지수승으로 계산하므로 상당히 cpu를 혹사하고 연산시간이 좀 걸림.

그래서 하이브리드 식으로 대칭키 방식과 혼용하는 방식이 등장하는데

대칭키의 키부분만 공개키 방식의 암호화 처리를 하고

실제 텍스트 등 내용은 속도 빠른 대칭키 방식으로 암호화하는 형태를 사용하기도 합니다. 효율적이겠죠.

또 한가지 미래에 양자 컴퓨터라는게 등장한다고 하는데 이게 성능이 엄청나게 좋다고 합니다.

앞의 소인수분해해서 개인키를 찾는 과정을 하루만에 뚝딱 끝내버리면 보안기능을 상실하게 되겠죠. 

그 때되면 지금의 128바이트, 256바이트 키 방식은 무용지물되겠죠. 

아마 저런 울트라 컴으로도 오래 걸리게 키를 더 크게 하거나 다른 암호화 방식을 사용하게 되겠죠.

 

참고로 공개키 방식이 사용자의 컴퓨터에 각종 키로거, 트로이 목마 등 바이러스가 활개쳐서

키 타이핑과 동시에 바로 공격자에게 전송되거나

서버 쪽 보안이 허접해서 개인키를 탈취당하는 그런 상황까지는 방어 못합니다.

평소 백신, 보안관리는 항상 철저히 하고 실행중 프로세스 확인하는 습관을 들입시다.

=========================================================================================

공개키 방식중에 가장 널리 상용화된 RSA암호화 방식을 파헤쳐보기로 하겠습니다.

수학공식이 많이 들어가 있습니다. 직관적으로 한방에 이해하면 좋겠지만

기초 개념, 공식부터 시작해서 어떤 사실을 증명하고 그 증명된 사실을 바탕으로 또 새로운 사실을 증명하는 식으로 구성되어 있습니다.

암호화 기법에 필요한 수학 기본 개념, 표기법부터 서술한다.

약수: 약수(約數, divisor)는 어떤 수를 나누었을 때 나머지가 0인 수. 가령 12는  1, 2, 3, 4, 6, 12로 나눌 수 있으므로 이 수들이 약수가 된다.

        기호 |로 으로 표기한다. 예를 들어, 3이 15의 약수라는 표현은 3|15와 같이 표현한다.

         정수 a, b에 대해 b/a가 나누어 떨어지면, a를 b의 약수라고 한다(a|b).

         0의 약수는 0을 제외한 모든 정수이다.  0/1, 0/2, 0/3,...는 연산이 가능하다. 0 = 1* 0, 0 = 2*0, 0 = 3*0...으로 표현가능 

배수: 어떤 수의 배수(倍數)란 그 어떤 수를 정수배(특히 자연수배)한 수를 말한다.
        정수 a, b에 대해 b/a가 나누어 떨어지면, b를 a의 배수라고 한다(a|b).

공약수: 두 정수에서 약수들 중 공통되는 약수. 가령 12와 18에서 1, 2, 3, 6이 공약수들이다.

최대 공약수: 공약수 중에서 가장 큰 수를 말한다. 가령 위 12와 18에서 6이 최대 공약수이다.

                   두 정수 a와 b의 최대공약수를 기호로 gcd(a, b)로 표기하거나, 더 간단히 (a, b)로도 표기한다.

인수: factor 어떤 정수를 곱셈의 형식으로 나타날 대 각각의 요소들을 인수라고 한다. 12 = 2 * 6이라 할때 2, 6은 인수이다.

        약수와 비슷. 인수는 곱셈표현식에서 각각의 요소라는 관점에서 바라본 것이라고 이해하면 된다.

소수: 2.56 등 이런 소수점 찍는 숫자가 아니다. 여기서 소수는 素數, prime number. 구분하기 위해 솟수라고도 함.

    약수가 1과 자기 자신 뿐인 1보다 큰 자연수. ex)  2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37... 무한히 존재한다.

    어떤수가 소수인지 손쉽게 판별하는 규칙은 아직 발견되지 않았고, 루트(어떤수의 제곱근)까지 직접 하나하나 나눠가며 조사해야 한다.

 소수 관련 포스팅을 읽어보니 요즘은 확률적인 알고리즘 등을 도입해서 소수 판정이 조금 빨라졌다고 합니다.

그리고   매우 큰 서로 다른 소수끼리 곱셈을 하여 어떤 수를 만든 경우는 그 수를 쉽고 빠르게 소인수 분해하는 규칙이나 알고리즘이 없습니다.

그 수보다 작은 굉장히 많은 소수들을 일일이 대입하는 무식한 방법을 쓰거나 조금 개선된 알고리즘을 써야 하는데 이렇게 해도 수십년 걸린다고 합니다.

양자 컴퓨터 같이 획기적인 성능의 컴퓨터가 나오면 이런 무식한 방법이라도 무진장 빨라져서 위험해지는것임.

 빠른 시간에 손쉽게 구해지는 규칙이 있었으면 암호화에 사용되지 못했을 것이다. 수학적인 난제가 이런식으로 굉장한 역할을 하고 있다.^^

소수가 뭐길래? 책 발췌문

"소수가 암호에도 사용된다

소수는 특히 첨단 정보화 사회가 된 오늘날에는 정보를 보호하는 암호에 사용되고 있다. 최근에 사용되는 암호는 대부분 소수를 이용한 공개 열쇠 암호 방식으로 만들어져 있다. 공개 열쇠 암호 방식은 암호를 만드는 방식은 공개되지만 그 암호를 원래의 문장으로 돌려놓는(이 과정을 복호라고 한다) 열쇠를 알아내기가 거의 불가능한 방식이다. 이런 방식이 가능한 이유는 큰 정수를 소인수 분해 하는 것이 매우 어렵기 때문이다. 예를 들어 어떤 두 소수를 곱한 수 4067351을 이용하여 암호를 만들었다는 것을 공개한다. 그런데 암호를 원래의 문장으로 돌려놓기 위해서는 이 수가 어떤 두 소수의 곱으로 되어 있는지 알아야 한다. 사실 이 수는 두 소수 1733과 2347의 곱이다. 그런데 두 소수 1733과 2347을 주고 이들의 곱 4067351을 계산하는 문제는 아주 쉽지만, 거꾸로 4067351이 어떤 두 소수의 곱으로 되어 있는지를 찾는 소인수분해 문제는 매우 어렵다. 실제로 사용되는 공개 열쇠 암호 방식은 예를 든 방법보다 훨씬 복잡하고 정교하지만, 소인수분해가 어렵다는 암호의 근본 원리는 같다.

1977년에 공개열쇠 암호 방식이 처음 발표될 당시, 예로 들었던 두 소수를 곱한 수(수가 너무 크기 때문에 여기서는 생략한다)를 인수분해 하는데 약 40,000,000,000,000,000년이 걸릴 것으로 예상했다. 그러다가 1994년에 인수분해 알고리즘이 개발되며 인수분해를 좀 더 빨리 할 수 있게 되었는데, 다행스럽게도 인수분해 알고리즘을 이용해도 100년 이상 걸린다. 그래서 공개열쇠 암호방식은 오늘날 은행의 저금통장의 비밀번호에서부터 인터넷에서 사용되는 ID와 암호 등 다양하게 이용되고 있다. 그러나 인수분해 알고리즘이 계속해서 발전하고 있기 때문에 그에 대응하여 더 큰 소수가 필요하게 되었다. 그래서 소수를 연구하는 수학자들은 더 큰 소수를 찾기 위해 지금도 노력하고 있다."

 

암호화에 사용되는 수의 예시. 참고) https://en.wikipedia.org/wiki/RSA_numbers#RSA-2048

RSA-2048 = 2519590847565789349402718324004839857142928212620403202777713783604366202070
7595556264018525880784406918290641249515082189298559149176184502808489120072
8449926873928072877767359714183472702618963750149718246911650776133798590957
0009733045974880842840179742910064245869181719511874612151517265463228221686
9987549182422433637259085141865462043576798423387184774447920739934236584823
8242811981638150106748104516603773060562016196762561338441436038339044149526
3443219011465754445417842402092461651572335077870774981712577246796292638635
6373289912154831438167899885040445364023527381951378636564391212010397122822
120720357

이 수를 소인수분해하면 20만 달러 상금을 준다고 한다. https://en.wikipedia.org/wiki/RSA_Factoring_Challenge

합성수: 소수를 합성(소수끼리의 곱셈)해서 만든 수라고 보면 된다.

      어떤 수가 그보다 작은 소수의 곱셈으로 만들 수 있으면 합성수이고 이게 안되면 새로운 소수가 탄생하는 것이다.

      가령 4=2*2, 6=2*3, 8=2*2*2, 9=3*3, ...

인수분해: 어떤 수나 다항식을 곱셈의 형식으로 구성하는 경우를 인수분해라고 한다.

      가령 12 = 3 * 4,  x2승 + 7x + 12 = (x + 3)(x + 4)

              

소인수분해: 합성수를 소수의 곱으로 나타내는 것을 말한다. 즉 위 인수분해를 가장 밑바닥인 소수부분까지 구성하는 것을 소인수분해라고 한다.

   소인수는 말그대로 소수인 인수, 즉 곱셈으로 구성시 인수들이 모두 소수인 경우를 말한다.

   ex) 12 = 2*2*3

서로소: 두 수 사이의 관계에서 1 이외에는 공약수가 없는 경우를 서로소라고 한다. 가령 6, 7은 서로소이다.

            모든 정수는 소수와 소수의 조합(합성수. 즉 소인수분해로 구성가능)으로 구성된다는 관점에서 보면

            둘 사이에 겹치는 소수(혹은 소인수)가 없다는 걸 의미한다.

            참고로 당연하겠지만 소수와 자기보다 작은 수는 무조건 서로소 관계이다. 

            a, b, c가 셋 다 서로 소인 경우. a*b와 c도 서로소, a와 b*c도 서로소, a*c와 b도 서로소이다. 겹치는 소수(혹은 소인수)가 하나도 없기 때문이다.

            a와 x가 서로소, b와 x가 서로소인 경우 a*b와 x도 서로소가 된다.

            비록 a와 b 사이에 소수(혹은 소인수)가 겹칠 수 있겠지만 x와 겹치는 소수(혹은 소인수)는 a나 b에 없기 때문이다.

합동식과 그 성질: 위까지는 비교적 쉬운 개념이었다. 합동식은 생소할 것이다. 이게 증명의 기초적인 토대이다.

정수 a,b,m에 대하여, m|(a−b)일 때( m * 아무개 = (a - b) 인 경우. 즉 a-b가 m으로 나누어 떨어질 때 | 기호(약수기호)를 써서 표시함),
a는 법 m에 대하여 b와 합동이다.이 때, 기호로는 a≡b (mod m)이라고 쓴다.
m를 합동의 법(모듈러, modular)이라고 한다.

즉 어떤 수들을 m으로 나눌 때 그 나머지가 같은 경우 저렇게 표시한다.

가령  17≡2 (mod 5)가 된다. 나머지가 2로 같고

뺄셈식으로 표현하면 17 - 2는 15이고 이것은 5*3이므로 5로 나누어 떨어진다.

일상적으로 나머지라 함은 나눗셈만 생각하고 떨거지 부분이라고 생각하는데. 

저렇게 뺄셈까지 연관지어 생각하면 뭔가 근사한 공식이 되고 수학자들은 다음과 같은 성질을 도출했다.

참고로  합동식 기호 말고 등호를 사용하는 경우 우리가 일상적으로 나머지라고 부르는 값인 0 ~ (m-1) 범위의 값을 취한다.

ex) 2 mod5 = 7 mod5 = 2가 된다.

합동식은 다음의 성질을 가진다. 참조: https://namu.wiki/w/합동식

10, 11은 추가하였다.

1. (반사율) a≡a(mod m)이다.a≡a(mod m)이다.
2. (대칭률) a≡b(mod m)이면 b≡a(mod m)이다.
3. (추이율) a≡b(mod m),b≡c(mod m)이면 a≡c(mod m)이다.
4. a≡b(mod m),c≡d(mod m)이면, a±c≡b±d(mod m)이다. (복부호동순)
5. a≡b(mod m),c≡d(mod m)이면, ac≡bd(mod m)이다.
6. a≡b(mod m)이면, a의k승 ≡ b의k승 (mod m)이다. 컴퓨터 소스코드에서는 지수승은 pow(a, k)로 표현. pow는 지수 표준함수
7. ab≡ac(mod m)이고, 최대공약수 d=gcd(a,m)이면, b≡c(mod m/d)이다.
8. a≡b(mod m)이고, n이 m의 약수이면, a≡b(mod n)이다.
9. a≡b(mod m)이고, d>0이 a,b,m의 공약수이면, a/d ≡ b/d (mod m/d)이다.

10. a≡b(mod m)이고, a≡b(mod n)이고 최소공배수 l=lcm(m,n)이면, a≡b(mod l)이다.

11. 매우 기초적인 성질이다. 동일한 값이므로  좌항->우항, 우항->좌항 형태로 변환가능하다.

     ab(mod m) <=>  (a(mod m) * b(mod m))(mod m) 이다.

     (a ± b) (mod m) <=>  (a(mod m) ±  b(mod m))(mod m) 이다.

    합동식으로 아래와 같이 표현할 수도 있다. 합동식은 당연히 좌항, 우항을 바꿔서 구성할 수 있다. 위 2번 성질

      ab ≡ (a(mod m) * b(mod m)) (mod m)

     (a ± b) ≡  (a(mod m) ±  b(mod m)) (mod m) 이다.

증명 부분) 4번까지는 직관적으로 이해가 간다. 5번부터 유심히 보자.

1. 명제) (반사율) a≡a(mod m)이다.a≡a(mod m)이다.

   a - a = 0이고 m*0 = 0이므로 m|0이다. 따라서 a≡a(mod m)이다.

2. 명제) (대칭률) a≡b(mod m)이면 b≡a(mod m)이다.

  a≡b(mod m)이면 m|(a-b)이다. 또 m|(b-a)이다. 따라서 b≡a(mod m)이다.

3. 명제) (추이율) a≡b(mod m),b≡c(mod m)이면 a≡c(mod m)이다.

  a≡b(mod m)이면 m|(a-b)이고 b≡c(mod m)이면 m|(b-c)이다. 그러므로 m|(a-b) + (b-c)이다.

  즉 m|(a-c)이다. 따라서 a≡c(mod m)이다.

4. 명제) a≡b(mod m),c≡d(mod m)이면, a±c≡b±d(mod m)이다. (복부호동순)

  a≡b(mod m)이면 m|(a-b)이고 c≡d(mod m)이면 m|(c-d)이다. 그러므로 m|(a-b) ± (c-d)이다.

  즉 m|(a±c) - (b±d)이다. 따라서 a±c≡b±d(mod m)이다.

5. 명제) a≡b(mod m),c≡d(mod m)이면, ac≡bd(mod m)이다.

  a≡b(mod m)이면 m|(a-b)이고 c≡d(mod m)이면 m|(c-d)이다. 그러므로 m|(a-b)c + (c-d)b이다.

 갑자기 (a-b)에 c를 곱해서 황당할 수 있는데 a-b에 어떤수를 곱해도 결국 a-b의배수이므로 m으로 나누어 떨어진다.

 (c-d)b 역시 c-d가 나누어 떨어지므로 어떤수를 곱해도 m으로 나누어 떨어진다.

그리고 나누어 떨어지는 수끼리 더해도 당연히 나누어 떨어진다.

ex) 7이나 21는 7로 나누어떨어지는데 7 + 21 역시 당연히 나누어떨어짐. 모두 7의 배수이다. 

 우항을 연산하면 m|(ac−bd)이다. 따라서, ac≡bd(mod m)이다.

6. 명제) a≡b(mod m)이면, a의k승 ≡ b의k승 (mod m)이다.

  a≡b(mod m)이면 m|(a-b)이다. 또 k≥2일때

  a의k승 - b의k승 = (a - b)(a의 k-1승 + a의k-2승*b + ... + a*b의k-2승 + b의k-1승)으로 표현가능하므로

  m으로 나누어 떨어진다. m|(a의k승-b의k승)이 되고 따라서 a의k승 ≡ b의k승 (mod m)이다.

  이 명제는 좌항과 우항을 계속 자기자신을 곱해나가므로 5번 성질을 연속으로 적용한 것으로도 증명할 수 있을 것이다.

7. 명제) ab≡ac(mod m)이고, d=gcd(a,m)이면, b≡c(mod m/d)이다.

  ab≡ac(mod m)이면 m|a(b-c)이다. 최대공약수 d = gcd(a,m)이므로 a=d*x1, m=d*x2를 만족하는 x1, x2가 존재한다.

  참고로 여기서 x1과 x2는 서로소 관계가 된다. 최대공약수는 두 수의 겹치는 모든 소수(혹은 소인수)부분들의 전체곱셈이기 때문이다.
  겹치는 부분이 없으면 1이 된다.

  가령 12, 20의 경우 소인수분해하면 12 = 2*2*3, 20 = 2*2*5이고 최대공약수는 겹치는 모든 부분인 2*2인 4이다.

  겹치는 최대공약수 부분을 덜어내면 12는 3, 20은 5 즉 서로소 관계인 부분만 남는다.

  (참고로 공약수는 겹치는 부분들끼리의 요소별 곱셈 조합일 것임을 예측할 수 있다.

   그리고 공약수는 공통된 부분을 최대로 뽑은 최대공약수의 약수들이라고도 볼 수 있습니다.)

  이제 식을 다시 풀어쓰면 d*x2 | d*x1(b - c)이다. d를 떨구면 x2 | x1(b - c)이 된다.
   (갑자기 나눠서 당황한 경우 대비 d*x2*아무개 = d*x1(b - c) 이므로 d를 나눌 수 있다. 그리고 마찬가지로 곱셈도 가능하다.)
   x2 | x1(b - c)에서 x1과 x2는 서로소이므로 필수적으로 (b-c)는 x2로 나누어 떨어져야 한다. 즉 x2|(b-c)가 되어야 한다.
   x2 = m/d이므로 m/d | (b-c)이다. 따라서 b≡c(mod m/d)이다.

 이 성질은 좌항과 우항을 어떤수로 나눌 수 있을 때 유용하다. 주의할게 일괄적으로 같은 수로 나누는게 아니라 

 모듈러 부분은 최대공약수로 나누어야 한다.
 여기서 m이 나누는 수와 서로소 관계이면 최대공약수는 1이므로 

 모듈러에는 어떤 변화없이 좌항, 우항만 나눗셈 처리해서 가볍게 만들 수 있다.

 가령 30≡9(mod7)일 때 좌항과 우항을 3으로 나누는 경우.

 (이때 mod 7에서 7과 3은 서로소여서 최대공약수는 1이므로 변화없다.)

 10≡3(mod7)이 된다. 참고해볼게 나머지는 위식에서는 2 vs 아래식에서는 3으로 변화가 있었지만 

 어쨌든 좌항과 우항은 같은 나머지를 가지므로 참이 된다.

 (참고로 명제 9에서 증명되듯이 셋다 동일한 약수가 있는 경우 물론 같은 수로 나눌 수 있다.

 7번 명제는 이보다 디테일하거나 조금 다른 상황에서의 명제로 좌항과 우항은 공통된 약수가 있지만

 모듈러 부분은 그렇지 않을 때 적용할 수 있는 성질로 생각하면 된다.)

8. 명제) a≡b(mod m)이고, n이 m의 약수이면, a≡b(mod n)이다.
   a≡b(mod m)이면 m|(a-b)이다. 또 n|m이면 n|(a-b)이다. 따라서 a≡b(mod n)이다.
   쉽게 m*아무개 = a-b이고 n은 약수이므로 m = n*아무개이다. m부분을 대체하면 n*아무개*아무개 = a-b이므로
   a-b는 n으로 필연적으로 나누어 떨어진다.

  직관적으로 4로 나누어 떨어지면 2로도 깔끔하게 나눠지겠죠.

9. 명제) a≡b(mod m)이고, d>0이 a,b,m의 공약수이면, a/d ≡ b/d (mod m/d)이다.
   a≡b(mod m)이면 m|(a-b)이다. d가 a, b, m의 공약수이므로 a = d*x1, b = d*x2, m = d*x3를 만족하는 정수 x1, x2, x3가 존재한다.
   위 식을 다시 풀어쓰면 d*x3 | d(x1-x2)이다. d를 나눠서 떨구면 x3 | x1- x2가 성립한다. x1 = a/d, x2 = b/d, x3 = m/d이므로
   m/d | (a/d - b/d)이다. 따라서 a/d ≡ b/d (mod m/d)이다.

10. 명제) a≡b(mod m)이고, a≡b(mod n)이고,  최소공배수 l=lcm(m,n)이면, a≡b(mod l)이다.

가정에 따라  b-a는 m의 배수여야 하고, n의 배수이기도 해야 한다.

동시에 m의 배수, n의 배수인 수는 m, n의 최소공배수 lcm(m, n)의 배수라는 의미이다.

b-a는  최소공배수 lcm(m, n)의 배수이므로 위 명제가 성립한다.

아래는 소수, 서로소, 최대공약수와 최소공배수의 연관성을 토대로 또 다른 방식으로 증명하는 경우이다.

  최대공약수 g = gcd(m, n) 이라고 할 때  m = g*m', n = g*n'으로 표현할 수 있고 

  이 경우 최소공배수 l = g*m'*n'이 된다. 이때 m'과 n'은 서로소 관계이다.  (최대공약수와 최소공배수의 성질 및 상관관계)

  ex) 6 = 2*3, 15 = 3*5인 경우, 최대공약수는 공통된 소인수인 3, 최소공배수는 최대공약수*2*5으로 30이다.

      (2, 5는 각각 안 겹치는 부분으로 서로소 관계임을 알 수 있다..) 

 a - b = m*x = g*m'*x으로 표현할 수 있다. x는 수식을 만족하는 어떤 정수를 의미한다. 마찬가지로

 a - b = n*y = g*n'*y로 표현할 수 있다. y는 수식을 만족하는 어떤 정수를 의미한다.

 위 두식은 같으므로   g*m'*x =  g*n'*y이 된다. 여기서 g를 나눠서 없애주면 m'*x =  n'*y가 된다. 

 m'과 n'은 서로소 관계이므로 반드시 x는 n'로 나누어 떨어져야 한다. 그러므로 x = n'*z로 표현할 수 있다. z는 수식을 만족하는 어떤 정수를 의미한다.

이제  a - b = m*x = g*m'*x =  g*m'*n'*z로 표현할 수 있다.

여기서 마지막 식의  g*m'*n'는 최소공배수 l과  동일하므로 a - b = l * z가 되어  나누어 떨어지므로 a≡b(mod l)가 성립한다.

 ex) 32≡2(mod 6)이고 32≡2(mod 15)이면 32≡2(mod 30)이 된다.

   얼핏 보기에도 앞의 mod6, mod15 수식에서 나머지가 같아야 하는 조건 자체가 동시에 충족되려면

   최소공배수인 30단위로 움직여야 됨이 직관적으로 느껴진다. 32 62 92, 122, ...일 때 조건이 충족될 것이고 결국 mod 30 합동식이 되는 셈이다.

11. 매우 기초적인 성질이다. 동일한 값이므로  좌항->우항, 우항->좌항 형태로 변환가능하다.

     ab(mod m) <=>  (a(mod m) * b(mod m))(mod m) 이다.

     (a ± b) (mod m) <=>  (a(mod m) ±  b(mod m))(mod m) 이다.

    합동식으로 아래와 같이 표현할 수도 있다. 합동식은 당연히 좌항, 우항을 바꿔서 구성할 수 있다. 위 2번 성질

      ab ≡ (a(mod m) * b(mod m)) (mod m)

     (a ± b) ≡  (a(mod m) ±  b(mod m)) (mod m) 이다.

a, b를 모듈러 m 기준으로 수식으로 표현하면

a = mk + a', b = mk' + b'라고 표현할 수 있다. (k, k'는 식을 만족하는 어떤 정수이고 a', b'는 0<= a' < m,  0<= b' <m인 나머지를 의미한다.)

그리고 a(mod m) = a', b(mod m) = b'가 된다.

첫줄 곱셈:  좌항 ab = (mk + a')( mk' + b' ) = mmkk' + mkb' + mk'a' + a'b' = m(mkk' + kb' + k'a') + a'b'가 된다.

m(mkk' + kb' + k'a')는 m으로 나누어 떨어지므로  모듈러식으로 표현하면 이부분은 없앨 수 있고 ab (mod m) =  a'b' (mod m) 이다.

우항 역시 a'b' (mod m) 값이므로 서로 동일하고 그 역도 성립하게 된다.  

두번째줄 덧셈, 뺄셈 : 좌항 a ± b = mk ±  a' +  mk' ± b' = m(k ± k') + a' ± b'이고

 m(k ± k')는 m으로 나누어  떨어지므로 모듈러식으로 표현하면  이부분은 없앨 수 있고 (a ± b) (mod m) =  (a' ± b') (mod m)가 된다.

역시 우항과 동일하고 그 역도 성립하게 된다.

합동식에 대해서도 당연히 성립한다.

곱셈) 좌항 - 우항 =  m(mkk' + kb' + k'a') + a'b' - a'b' =  m(mkk' + kb' + k'a')으로 m으로 나누어 떨어진다.

덧뺄셈) 좌항 - 우항 =   m(k ± k') + a' ± b' -  (a' ±  b') =  m(k ± k')으로  m으로 나누어 떨어진다.

이런 성질은 개별적 단위로 분리해서 계산할 때 유용하다.

가령 (2^56 + 3) mod 4 = ((2^56)mod4 + 3mod4) mod4이다. 여기서 (2^56)mod4 = (4^28)mod4이므로 나누어 떨어지므로 0이다.

그래서 (0 + 3)mod4이므로 결과는  3 mod4 즉 3이 된다.

 

  

======================================================================================================================

<공개키 암호 알고리즘의 심플한 형태>

성립을 위한 기본적인 조건
- 서로 다른 키가 2개 존재해야 하고 공개키로 암호를 걸면 개인키로는 암호를 풀어 평문으로 만들 수 있어야 한다.
 - 다른 문자를 암호화했을 경우 다른 값을 가져야 한다. A라는 문자를 암호화했을 경우 101, B라는 문자를 암호화해도 101이면 안되겠죠.
- 서로 다른 암호화 값를 평문으로 복원했을 때 같은 결과가 나오면 당연히 안되겠죠.

우선 서로 다른 값인데 공통으로 처리할 수 있는게 딱 생각해도 그동안 주구장창 다뤄온 나머지를 이용하면 되겠다 하는 생각이 들죠.
RSA 암호화에서 알고리즘을 나머지를 나타내는 합동식으로 구성합니다.
가령 3과 23은 서로 다른 수이지만 10으로 나눈 나머지는 3으로 같습니다.
그러므로 3인 평문을 암호화해서 어떤수로 바꾸고 그 암호화된 어떤수를 13, 23, 33, 43,...과 같은 나머지가 3인 수로 만들 수 있으면 평문으로 복원되겠죠,

ex) 매우 심플한 사례
즉 1 ~ 9까지의 9개의 평문 문자가 있다고 할 때. 공개키 3, 개인키 7로 설정한다. 키는 곱셈을 하는데 사용한다.
(평문 * 3)을 10으로 나눈 나머지 => 암호. 이건 굳이 10으로 나눌 필요는 없으나 3, 6, 9, 12, 15, 18, 21,24, 27하면 너무 쉽게 노출된다.
3, 6, 9, 2, 5, 8, 1, 4, 7도 파악이 어렵진 않으나 위보다는 나은 듯;;;
(암호 * 7)을 10으로 나눈 나머지 => 평문

평문 1 -> 암호 3 -> 평문 1
평문 2 -> 암호 6 -> 평문 2
평문 3 -> 암호 9 -> 평문 3
평문 4 -> 암호 2 -> 평문 4
평문 5 -> 암호 5 -> 평문 5
평문 6 -> 암호 8 -> 평문 6
평문 7 -> 암호 1 -> 평문 7
평문 8 -> 암호 4 -> 평문 8
평문 9 -> 암호 7 -> 평문 9

더이상 내려갈 수 없을만큼 심플하지만 어쨌든 암호화된 값들이 겹치는게 없이 모두 다르다.

약간 신기하다는 느낌을 잠시 접고, 좀 다르게 키를 곱셈으로 처리하지 말고 지수승으로 해서 처리해보자.
(평문의 3승)을 10으로 나눈 나머지 => 암호
(암호의 7승)을 10으로 나눈 나머지 => 평문

평문 1 -> 1 암호 1 -> 1 평문 1
평문 2 -> 8 암호 8 -> 2097152 평문 2
평문 3 -> 27 암호 7 -> 823543 평문 3
평문 4 -> 64 암호 4 -> 16384 평문 4
평문 5 -> 125 암호 5 -> 78125 평문 5
평문 6 -> 216 암호 6 -> 279936 평문 6
평문 7 -> 343 암호 3 -> 2187 평문 7
평문 8 -> 512 암호 2 -> 128 평문 8
평문 9 -> 729 암호 9 -> 4782969 평문 9

놀랍게도 지수승으로 처리해도 각각의 암호화된 나머지값이 겹치지 않고 복호화가 제대로 된다.
판타스틱 쇼킹~
여기에 앞서 배운 수식이 적용되어 있다. 수학자들 정말 무서운 사람들이군요.;;;

나누는 값인 10 = 소인수2 * 소인수5이고
공개키 3은 오일러 함수에서 (소수-1)(소수-1)인 (2-1)*(5-1)인 4보다 작은 수중에 서로소인 3을 취한 결과이다.
개인키 7은 모듈러 연산에서 역원(곱셈연산시 나머지 1인 되는  수)을 구한 값이다.(오일러 함수는 아래에서 서술함)

앞은 너무나 심플한 예이고 이제 더 생각할볼만한 조건은
우선 나머지가 각각의 문자에 대응하므로 나머지의 개수가 모든 문자의 개수보다 커야 하므로 너무 작은 수로 나누면 안되겠고,
공격자측에서 쉽게 파악할 수 없도록 거대한 수로 만들어야 하고 알고리즘을 쉽게 풀수 없게 해야 합니다.
거대한 수를 사용하면 거대한 경우의 수가 나오게 될 것이므로 첫번째 조건은 당연히 충족될 것입니다.

RSA를 이해하기 위해서는 수학 이론을 더 이해해야 한다.  계속 수학 개념들을 서술한다.

======================================================================================================================

페르마의 소: https://ko.wikipedia.org/wiki/페르마의_소정리 참조한다. 최대한 자세하게 쉽게 풀어쓸려고 했다.

페르마의 소는 합동식에서 소수 관련 지수승을 하는 경우 나타나는 독특한 특징에 대해서 다룬다.

 p가 소수이고, a가 정수이며, a와 p가 서로소인 경우
a^p ≡ a (mod p)
위 식은 a는 0인 경우 당연히 성립하고 0이 아닌 경우 양변을 a로 나누면
a^(p-1) ≡ 1 (mod p)이 성립한다.

합동식에서 곱셈의 항등원인 1이 도출될 수 있는 이런 특징은 암호화, 복호화를 가능하게 하고,

어떤수와 이에 대한 역원으로 공개키, 개인키 쌍을 구성할 수 있다.

갑자기 항등원, 역원이 나와서 당황스러울 수 있다. 항등원과 역원에 대해서 자세히 설명하기로 한다.
일단 합동식 말고 일반적인 식를 생각해보자.
우선 항등원은 대상을 어떤수와 연산시 결과가 대상 자기자신이 되는 경우 어떤수를 말한다. 따라서 덧셈에서는 0, 곱셈에서는 1이 항등원이 된다.
역원은 대상을 어떤수와 연산시 결과가 항등원이 되는 경우 그 어떤수를 말한다. 덧셈에서는 대상이 a이라면 -a가 역원, 곱셈에서는 1/a이 역원이 될 것이다.
여기서 곱셈의 역원부분을 염두에 두고 생각해보자. 만약 n이라는 숫자에 a를 곱했다고 하자.
그러면 그 결과값은 n*a이다. 이걸 다시 1/a를 곱하면 n*a*(1/a)이 되므로 다시 n값으로 돌아온다.
a와 1/a는 곱셈시 서로 역원관계에 있으므로 두수를 곱하면 항등원으로 원래의 수로 돌릴 수 있게 된다.
암호화를 저런 간단한 수식으로 구성한다면 a가 암호화키, 1/a가 복호화키의 역할을 할 수 있다.

이제 합동식의 곱셈에서 항등원과 역원을 생각해 보자.
합동식 곱셈에서 항등원이 되려면 즉 a * 아무개의 값이 a가 되려면
아무개는 나머지가 1인 수들이야 함을 직관적으로 알 수 있다.
굳이 증명하자면 mon n인 경우 나머지가 1인 수는 n*k + 1로 표현할 수 있다.(k는 어떤 정수)
a에 이 수를 곱하면 a*(n*k + 1) = a*n*k + a가 된다. a*n*k는 항상 n의 배수이므로 a (mod m)이 된다. 

즉 1(mod n)에 속하는 수들이 합동식 곱셈에서 항등원이 된다.
ex) a(mod7)은 1, 8, 15, 22,...등 나머지가 1인 수들 즉 1(mod7)과 곱하면 항상 자기자신 a(mod7) 그대로 유지된다.

보다시피 일반수식과 개념상 유사하다. 역시 1의 값이고
다만 합동식이기 때문에 저렇게 나머지가 1인 수들 전체를 의미한다.
이를테면 합동식은 수를 나머지를 기준으로 분류해서 집합처럼 관리, 처리한다.

역원은 대상을 어떤수와 연산할 때
항등원인 나머지가 1인 수 즉, 1(mod n)으로 만들수 있는 경우, 그 어떤수를 말한다.
수식으로 표현하면 대상을 e라 할때 e*d ≡ 1(mod n)이 되면 d를 e의 역원이라고 한다.

그리고 d*e 역시 결과값이 다르지 않으므로 상호 역원관계이다.

역원이 성립하는 경우 평문 m은 e를 곱하여 m*e로 만들고(암호화)
m*e에 d를 곱하면 m*e*d가 되는데 e*d는 곱셈의 항등원 1이므로 다시 평문 m으로 돌릴 수 있게 된다.(복호화)
서로에 대해 역원관계이므로 당연히 d키로 암호화해서 e키로 복호화할 수도 있다.
이렇게 m*e로 암호화, 그 값에 d를 곱해 복화화하는 알고리즘을 작성해도 되지만 
이 경우 알고리즘이 너무 단순해서 쉽게 파악이 된다는 문제가 생긴다. 암호문은 m*e이므로 e키 단위로 일정하게 증가할 것이다.
단순하고, 규칙성이 너무 쉽게 드러나므로 공격자에게 알고리즘이 쉽게 파악된다.

RSA에서는 암호화 체계를 평문 m의 지수승으로 구성한다.
항등원과 역원 역시 지수승과 연계해서 구성되고, 암호화, 복호화도 지수승으로 계산한다.
설명이 차근차근 진행되면 무슨 소리인지 알게 된다.
일단 기초적인 설명을 했으니 이제 페르마의 소를 증명한다. 앞에서 링크한 위키를 바탕으로 최대한 쉽게 설명한다.

페르마의 소 증명)
명제: p가 소수이고, a가 정수이며, a와 p가 서로소인 경우
a^(p-1)≡1 (mod p) 이다.
예를 들어 p = 5인 경우 1^4 = 1 / 2^4 = 16 / 3^4 = 81 / 4^4 = 256으로 신기하게도 모두 5로 나눌때 1로 떨어진다.
저기에 거대한 소수를 넣어도 저런 법칙이 통용된다니,,, 페르마나 오일러, 유클리드 등 수학자들에 감탄을 금치 못하겠다.

페르마의 소 정리를 증명하는 방법은 여러가지가 있을 수 있지만, 가장 쉬운 방법으로 합동식을 이용하는 방법이 있다.
a와 서로소인 소수 p에 대해 a, 2a, 3a, ..., (p-1)a인 p-1개의 수를 가정하자.
이 수들을 각각 p로 나눈 경우 이 수들을 p로 나눴을 때 나오는 나머지는 모두 다르다.
ex) a=2, p=5인 경우 2, 2*2, 3*2, 4*2 => 5로 나눈 나머지는 각각 2, 4, 1, 3으로 다르다.

위 사실 증명: 귀류법 사용(전제를 참이라고 가정하고 해석한 결과 결론이 거짓이면 그 전제는 참이 아니라는 식. 수학증명에서 매우 자주 사용)
위 범위의 수에서 서로 같은 나머지를 가진 두 수, ia와 ja가 있다고 전제하자(0 < i < j < p인 정수).
그렇다면 이 두 수의 차는 p로 나누어질 떨어질 것이다. 두 수의 차는 (j-i)a이다.
그런데 0 < j-i < p이므로 j-i는 p와 서로소이며,(p는 소수이므로 1과 자신 외에는 약수가 없다. 그러므로 소수는 그보다 작은 수에 대해 항상 서로소)
문제의 가정에 따라 a는 p와 서로소이다. j-i도 p로 나누어 떨이지지 않고, a역시 p로 나누어 떨어지지 않는다.
이에 따라 (j-i)a 역시 p로 나누어 떨어지지 않는다. 그러므로 같은 나머지를 가진다는 것은 성립 불가능하다.
  따라서 위의 전제는 거짓이고 위 범위의 수들을 p로 나눈 나머지는 각각 다르게 된다.

또 0 < i < p인 어떤 i에 대해서도 i, p는 서로소 관계이고 a, p도 서로소 관계이므로
i*a 역시 p와 서로소 관계가 된다.(i,a는 p와 공통된 소수나 소인수를 가지지 않으므로 i*a 곱셈해도 마찬가지이다.)
즉 i*a는 p로 나누어 떨어지지 않으므로 1 ~ p-1범위의 나머지값을 갖게 된다.

범위의 수 i*a들은 모듈러 p를 기준으로 다음과 같이 표현할 수 있다.
a = pk1 + r1
2a = pk2 + r2
3a = pk3 + r3
...
(p-1)a = pk모 + r모..

범위의 수를 모두 곱하면
  a * 2a * 3a ... (p-1)a  =  (pk1 + r1) * (pk2 + r2) * (pk2 + r2)... (pk모 + r모)  =  p*(~) + (r1 * r2 * r3 *... * r모)가 된다.

(~는 수식을 만족하는 어떤 식이다. 아무튼 전체 나머지 곱부분을 제외하고 모두 필수적으로 p곱셈이 들어간다.)
모듈러 p 합동식으로 구성시 p*(~) 부분는 p의 배수이므로 떨굴 수 있다. 간결하게 전체 나머지 곱부분만 남길 수 있다.

앞에서 증명되었듯이 이 나머지들은 모두 각각 다르고 1 ~ p-1범위의 값이므로 
나머지의 집합인 {r1, r2, r3....r모}는 {1,2,3,...,p-1}과 같은 집합이므로.
  모두 곱한 값 (r1 * r2 * r3 *... * r모)는 (1 * 2 * 3 * ... * (p-1))이다.

위 사실을 토대로 합동식으로 구성해서 정리하면
  a * 2a * 3a ... (p-1)a ≡ (r1 * r2 * r3 *... * r모) ≡ (1 * 2 * 3 * ... * (p-1)) (mod p)가 된다.
좌항에서 a의 지수승을 좌측으로 몰아서 형태를 재구성하면 아래와 같이
a^(p-1)*(1 * 2 * 3 * ... * (p-1)) ≡ (1 * 2 * 3 * ... * (p-1)) (mod p)이 된다.

여기서 좌우의 공통된 1 * 2 * 3 * ... * (p-1) 부분을 나눠서 없애고 싶은 충동이 들 것이다.^^
공통된 약수가 존재하면 나눌수 있는데 주의할 점이 모듈러 p에 대해서도 최대공약수로 나눠줘야 한다.(합동식 성질 7)
그런데 p는 소수이므로 1 * 2 * 3 * ... * (p-1)과는 절대 공통된 소수(소인수)를 가질 수 없다.
즉 서로소이고 최대공약수는 1이므로 p값은 그대로 유지된다.

깔끔하게 나누어주면 a^(p-1) ≡ 1 (mod p) 이다. 

소수와 지수승이 결합된 항등원식이 구성되었다.

특정한 수와 이에 대한 역원(이 둘은 공개키, 개인키 1쌍이 된다.)을 연산하여 항등원식을 구성할 수 있으면

암호화에 이용할 수 있게 된다.

참고로 페르마의 소를 만족한다고 해서 a가 꼭 소수는 아니라고 한다. 소수의 필요조건이지만 충분조건은 아님.
소수가 아닌데도 저런 수식을 만족하는 수를 카마이클수라고 한다.

소수 p를 이용하여 암호화식을 모듈러 p의 합동식으로 구성하고 e, d키 구성시 

소수 p, 공개키 e를  공개적으로 전달하는데 이경우 이 정보로 바로 개인키 d를 알아챌 수있게 된다.

그래서 단순한 소수 하나로는 암호화체계를 구성하면 안된다. 아래서 자세히 설명한다.

평문이 m이고 m을 지수승의 대상이라고 할때 페르마의 소를 적용하면

m^(p-1) ≡ 1 (mod p) 이 된다. 이 경우 임의의 정수를 k라고 할 때

m^((p-1)k) ≡ 1 (mod p) 역시 1이 된다.(1을 아무리 지수승해봐야 1)

여기서 지수승 부분이 (p - 1)k + 1의 형태가 되면 복호화식이 된다.

m^((p-1)k + 1) ≡ m^((p-1)k) * m  ≡  m (mod p) 이 되어 복호화가 될 수 있다. m*1(항등원)은 m이다.

이를 바탕으로 위의 지수승 부분을 공개키*개인키 키셋인 e*d으로 구성할 수 있다.

e*d가  (p - 1)k + 1 형태가 되면 위 식에 의해 복호화가 가능해지는 것이다.

e*d = (p - 1)k + 1를 합동식으로 간결이 표시하면 ed  ≡ 1 (mod p-1)이다.

이 경우를 수학적으로 표현하면 법(모듈러) p-1에서 곱셈연산시 e와 d는 서로 역원관계에 있다고 한다.

주의할게 공개키*개인키 구성식에서의 모듈러는 p가 아니라 p-1임을 유의한다.

ed  ≡ 1 (mod p-1) 식에서 e에 특정한 수를 지정해 이것을 공개키로 하고 그 역원 d를 산출해 개인키로 삼게 된다.

여기서 매우 큰 문제점이 발생한다. 암호화를 위해서는 개인키 e뿐 아니라 p 역시 전달해야 한다.

p는 p보다 작은 나머지 값을 산출하기 위한 기준이 되는 값이므로 반드시 필요하다.

※ 참고) 만약 암호화 체계를 e공개키만 전달하고 p를 전달하지 않은 방식으로 구성한다면

거대한 지수승이 적용된 울트라 초거대한 암호문을 날것 그대로 생성, 전송, 해석해야 한다.

나머지가 아닌 8943269977653533543476^90356875221(지수승) 같은 초거대한 수를 있는 그대로 처리하는 것은 

CPU 연산, 메모리 부하, 네트워크 시간 지연 등의 문제를 일으킬 것이다.

그리고 수학적으로 모듈러 연산을 하지 않으면 아주 치명적인 결함이 존재하게 되는데

평문 m을 바로 구할 수 있다는 점이다. 가령 m^3 = 8에서 암호문이 8이면 m은 2이다.

아무리 복잡해도 m이라는 해를 구할 수 있을 것이다. 그런데 m^e(mod p) = c  모듈러 연산이면 

m^e = pk + c의 형태의 부정방정식의 해 m을 구하는 문제가 되므로 

무수히 많은 후보들이 존재하므로 어느게 진짜 m인지 알 수 없다.

p 전달시의 문제는 p와 공개키 e값으로 누구나 개인키 d를 구할 수 있게 되버리는 점이다.

가령  p = 11이고 e가 3이면 암호화 공식은 m^3 (mod 11)이다.

위 키 생성공식에 의해 3d ≡ 1 (mod 10)을 만족하는 d값이 산출된다. 개인키 d는 7이다.

참고로  복호화 공식은암호문이 c일때 c^7 (mod 11)이다. 위 암호화식과 연계해서 풀어보면

c = m^3이므로  복호화식에 적용하면 m^21(mod 11)이고 이것은 (m^10)^2 * m (mod11)으로 구성할 수 있다.

앞의 m^10부분은 페르마 소 정리에 의해 1(항등원)이 되므로 결국 원래의 평문 m만 남게 된다. .

이런 문제가 생기기 때문에 소수 하나로 모듈러 mod p를 구성하지 않고

서로 다른 소수의 곱 n = p*q으로 mod n을 구성하고 n과 공개키 e를 전달한다.

이전에 계속 언급했지만 n값을 가지고 p, q를 찾는 소인수분해가 매우 어렵고 굉장히 오래 걸린다고 한다.

빠른 소인수 분해나 획기적인 알고리즘이 등장하지 않는 한  암호화에 사용될 수 있다.

이제 모듈러가 하나의 소수가 아닌 두 소수의 곱 p*q일 때 암호화는 어떤식으로 이루어지는지 알아보기로 한다.

오일러의 정리, 함수에 의해 이것은 구현된다.

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

오일러 함수: https://ko.wikipedia.org/wiki/오일러_피_함수 참조
위 골격을 바탕으로 자세히 알기쉽게 풀어쓴다.

정수론에서, 오일러 φ 함수(Euler φ 函數, 영어: Euler’s phi (totient) function)는
1부터 n까지의 양의 정수 중에 n과 서로소인 것의 개수를 나타내는 함수이다.
양의 정수 n에 대하여 정의되며, 함수로는, 일반적으로 φ(n)으로 표기한다.

ex) 1, 2, 3, 4, 5, 6 중에, 6과 서로소인 수는 1, 5 두 개이다. 따라서, φ(6) = 2
1, 2, 3, 4, 5, 6, 7 중에, 7 이외에는 모두 7과 서로소이다. 따라서, φ(7) =6
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 중에, 모두 11과 서로소이다. 그러므로 11-1=10 따라서, φ(11)=10이다.

다음과 같은 성질을 가집니다.

우선 n이 1인 경우 φ(1) = 1입니다. 서로소라는 개념이 1과 자기자신을 약수로 갖는다입니다.
1 역시 1과 자기자신인 1이 약수이니까요. 간단한건데 헷갈릴 수 있으니 유의합시다.

다음으로 소수에 관련된 성질부터 살펴봅니다.

소수인 경우 개념상 1과 자기자신만이 약수이므로 그보다 작은 수에 대해 항상 서로소이므로
파이함수의 값은 p-1개가 될 것입니다.
φ(p) = p - 1입니다.

소수의 지수승인 경우, 다음과 같은 수식이 성립합니다.
φ(p^k) = p^k - p^(k-1) = p^k(1 - 1/p) 이다.
얼핏 보기에는 뭔가 어려운 공식 같은데 단순히 전체 개수에서 p의 배수인 것들의 개수를 빼준 것이다.
p가 소수이므로 1 ~ p^k 범위의 수에서 p의 배수인 것들만이 약수가 됩니다.
p^k은 전체 개수이고 이 중 p의 배수의 개수는 p로 나눈 p^k / p = p^(k-1)입니다.
ex) 7^3인 343에서 7의 배수는 7, 14, 21... 343까지 49개 즉 343/7개가 존재한다.
전체개수에서 p의 배수를 빼준게 서로소인 것의 개수이다.


이제 일반적인 공식을 알아보겠습니다.
φ(n) = n * (1 - 1/p1)*(1 - 1/p2)*(1 - 1/p3)*...*(1 - 1/pi) 을 살펴보겠습니다.
n은 대상이 되는 양의 정수, p1, p2, p3,...pi는 n을 구성하는 소수 혹은 소인수(소인수분해시)입니다.

참고로 누적 곱하기인 수학기호(대문자 파이∏)로 축약해서 아래와 같이 표시하기도 합니다.
φ(n) = n * ∏ (1- 1/p) (참고로 p|n은 p가 n의 약수를 의미. |이 약수기호임)
              p|n

양의 정수를 소수 관점에서 바라보면 1 이외 양의 정수는 소수와 합성수로 구성됩니다.
여기서 합성수는 소인수 분해(소수들의 곱의 형식)가 되므로, 1을 제외하고 양의 정수는 모두 본질적으로 소수의 조합입니다.
참고로 1은 앞에서 언급했듯이 φ(1) = 1이고 저 공식에 넣어도 적용됨을 볼 수 있습니다.
1은 개념상 소수가 아니고 소인수분해 역시 개념상 안되므로 n값에 1만 들어가고 옆의 소수 관련 식은 무시됩니다..
이제 n > 1인 수에 대해서 증명하면 됩니다.

앞의 소수의 조합으로 수가 구성된다는 개념아래
n = p1^a1 * p2^a2 * p3^a3 *...(n > 1, p○는 소수, a○는 소수의 지수승)

1 ~ n 범위의 수에서 서로소인 수가 되려면 해당 수는 p1, p2, p3,... 소수들로 구성되지 않아야 합니다.
즉 p1의 배수가 아니어야 하고, p2의 배수가 아니어야 하고, p3의 배수가 아니어야 하고,.... 즉 수를 구성하는 소수들의 배수가 아니어야 합니다.

1 ~ n 범위의 수에서 p1의 배수의 개수는 그냥 n을 p1으로 나누면 됩니다. p는 n의 약수이므로 반드시 나누어 떨어집니다.

p1 배수의 개수 = n/p1,
p2 배수의 개수 = n/p2,
p3 배수의 개수 = n/p3,
...

n에서 저런 배수들의 총 개수를 뺀게 파이함수의 값이 됩니다.
정확히 저런 모든 배수들의 총 합집합의 원소 개수를 뺀게 파이함수의 값입니다.
유념할게 단순 빼기로만 끝내면 안되고 겹치는 부분 즉 교집합 부분을 고려해야 한다는 점입니다.
가령 2의배수 2, 4, 6,....과 3의 배수 3,6,9,...에서 6, 12,...와 같은 6의 배수들이 겹치게 되죠.
참고로 저런 공통된 부분의 배수의 개수를 구하는게 거창한게 아니고 그냥 해당수를 나누기하면 됩니다.
n/(p1*p2)이 p1*p2배수의 개수입니다.

집합의 정리중 포함배제의 원리 적용하여 위 계산을 규칙적으로 처리할 수 있습니다.
(포함배제의 원리는 쉽게 말해 합집합을 교집합을 이용해서 나타낸 식입니다.
식의 형태가 포함(+), 배제(-), 포함(+), 배제(-)....식으로 구성되므로 재밌는 이름이 붙음)

아래는 집합의 개수에 따라 포함배제의 식을 나타낸 것입니다.
집합 2개시: │A∪B│= │A│+│B│-│A∩B│ // 포함, 배제
집합 3개시: │A∪B∪C│=│A│+│B│+│C│- (│A∩B│+│A∩C│+│B∩C│)+│A∩B∩C│ // 포함, 배제, 포함
집합 4개시: │A∪B∪C∪D│=│A│+│B│+│C│+│D│- (│A∩B│+│A∩C│+│A∩D│+ ...) + (|A∩B∩C│+│A∩B∩D│....) - A∩B∩C∩D // 포함, 배제, 포함, 배제
...
이렇게 한번은 포함으로 +, 한번은 배제로 -하는 규칙성을 띄고 있습니다.
왜냐하면 처음에 포함시 중복부분이 있어서 이 부분을 빼줘야 하는데, 이 일괄적인 빼기 과정에서 또  중복하여 빼는 부분이 있어서 
다음번엔 더해줘야 합니다. 이 과정에서도 중복하여 더하는 부분이 있어서 다음번엔 또 빼줘야 하구요.
이런식으로 한번은 더했다 한번은 뺐다... 전체 집합들의 교집합까지 이어집니다..

이걸 오일러 파이 함수에 적용해보면, 전체에서 합집합을 빼는 식이므로 다음과 같습니다.
n - (p1배수개수 + p2배수개수 + p3배수개수...) + (p1*p2배수개수 + p1*p3배수개수+...) - (p1*p2*p3배수개수 + ...) +... +(혹은-)(p1*p2*p3*p4*p5...)
이 됩니다. 배수개수를 수식으로 표현하면
n - (n/p1 + n/p2 + n/p3...) + (n/(p1*p2) + n/(p2*p3) +...) - (n/(p1*p2*p3) + .....)+...+(혹은-)(n/p1*p2*p3*p4*p5...)
수식을 유심히 살펴보면 모두 n이 분자에 있습니다. 그래서 n을 따로 빼서 정리하면
n * (1 - (1/p1 + 1/p2 + 1/p3...) + (1/(p1*p2) + 1/(p2*p3) +...) - (1/(p1*p2*p3) + .....)+...+(혹은-)(1/p1*p2*p3*p4*p5...))
괄호식 안의 부분은  (1-a)(1-b)(1-c)(1-d)... 형태의 다항식의 전개와 같습니다. 따라서
φ(n) = n * (1 - 1/p1)*(1 - 1/p2)*(1 - 1/p3)*...이 됩니다.
공식이 증명되었습니다. 공식에서 주목할만한 점은 소수의 지수승 부분은 계산에 별 필요없다는 점입니다.

지수승이 크면 n값이 좀 크겠군 이정도 의미.

n과 그 구성요소인 소수만 알면 산출됩니다.


다음을 증명한다. m과 n이 서로소인 경우
φ(mn) = φ(m)*φ(n) 이다.

m, n을 소수의 곱으로 표현해보자.
m = p1^a1 * p2^a2 * p3^a3 *... // p는 소수, a는 지수. 참고로 위에서 언급했듯이 지수승 부분은 계산에서 별 의미없다.
n = q1^b1 * q2^b2 * q3^b3 *... // q는 소수, b는 지수.

m, n이 서로소이므로
p1, p2, p3, ..., q1, q2, q3, ...에 공통된 소수가 없다.

처음 공식에 의해...
φ(m) = m * (1 - 1/p1) * (1 -1/p2) * (1 -1/p3) * ...
φ(n) = n * (1 - 1/q1) * (1 -1/q2) * (1 -1/q3) * ...
두식을 를 곱하면
φ(m)*φ(n) = mn * (1 - 1/p1) * (1 -1/p2) * (1 -1/p3) * ... *(1 - 1/p1) * (1 -1/p2) * (1 -1/p3) * ...

이제 φ(mn)을 처리해 보자.
우선 mn = m*n이므로
mn = p1^a1 * p2^a2 * p3^a3 *...* q1^b1 * q2^b2 * q3^b3 *...가 된다.
서로소이므로 p1, p2, p3, ..., q1, q2, q3, ...에서 공통된 소수는 없다. 공식으로 처리하면
φ(mn) = mn * (1 - 1/p1) * (1 -1/p2) * (1 -1/p3) * ... *(1 - 1/p1) * (1 -1/p2) * (1 -1/p3) * ...이다.
위의 φ(m)*φ(n)과 결과가 동일함을 알 수 있다.


위는 서로소인 경우에만 성립되는 식이고 최대공약수가 존재하는 모든 경우까지 고려해보자.
결론부터 말하면 최대공약수가 g = gcd(m,n)인 경우
φ(mn) = φ(m)*φ(n) * g / φ(g)이 성립한다.
서로소 상관없이 모든 양수에 적용된다.

g = c1^d1 * c2^d2 * c3^d3 *... // c는 소수, d는 지수
m = c1^e1 * c2^e2 * c3^e3 *... * p1^a1 * p2^a2 * p3^a3 *... // c, p는 소수, e, a는 지수
n = c1^f1 * c2^f2 * c3^f3 *... * q1^b1 * q2^b2 * q3^b3 *... // c, q는 소수, e, b는 지수
m, n에는 공통된 소수들인 c1, c2, c3,...가 들어가 있다.
여기서 c1, c2, c3,..., p1, p2, p3,..., q1, q2, q3,...는 전부 다른 소수들이다.
최대공약수는 각각의 수에서 공통된 소수 부분들의 전체곱이다.(이를테면 교집합)

참고로 주의해볼게 c1, c2, c3... 공통된 소수의 지수부분은 각각의 수마다 다를 수 있다.
최대공약수 g를 구성하는 소수의 지수를 d1, e1, f1,...로 표시했는데 g의 지수부분은 최대공약수이므로

개념상 필연적으로 m, n의 소수의 지수보다 작거나 같을 것이다.(d1<=e1, d1<=f1,...)
예를 들어 12=2*2*3, 18=2*3*3 두 수에서 2,3은 공통된 소수지만 각각의 지수 부분은 다르다. 

12 = 2^2*3    vs    18 = 2*3^2 이고  최대공약수는 2*3이다.

공통된 소수의 지수가 다르고 최대공약수 부분의 지수가 가장 작음을 알 수 있다.

간혹 착각하기 쉬운게 어떤 수의 최대공약수 이외의 부분과 최대공약수가 서로소라고 여기는 것이다.

그렇지 않다. 두 수(비교대상)에서 각각의 최대공약수 이외의 부분들이 서로소이다.

ex) 12, 18에서 최대공약수는 6이다. 12라는 수에서 최대공약수 6과 이외의 부분인 2는 서로소가 아님을 알 수 있다.

    마찬가지로 18에서 최대공약수 6과 이외의 부분인 3은 서로소가 아니다. 12와 18의 이외의 부분들인 2, 3이 서로소이다.

이제 φ(m), φ(n) 파이함수를 풀어써보자.
φ(m) = m * (1 - 1/c1) * (1 -1/c2) * (1 -1/c3) *...* (1 - 1/p1) * (1 -1/p2) * (1 -1/p3) *...
φ(n) = n * (1 - 1/c1) * (1 -1/c2) * (1 -1/c3) *...* (1 - 1/q1) * (1 -1/q2) * (1 -1/q3) *...

φ(m)*φ(n) = m * (1 - 1/c1) * (1 -1/c2) * (1 -1/c3) *...* (1 - 1/p1) * (1 -1/p2) * (1 -1/p3) *...
                 *n * (1 - 1/c1) * (1 -1/c2) * (1 -1/c3) *...* (1 - 1/q1) * (1 -1/q2) * (1 -1/q3) *...
여기서 (1 - 1/c1) * (1 -1/c2) * (1 -1/c3)*... 부분은 공통되므로 두번 곱해진다. mn을 좌측으로 위치시키고 보기좋게 구성하면
= mn * (1 - 1/c1) * (1 -1/c2) * (1 -1/c3) * ... * (1 - 1/c1) * (1 -1/c2) * (1 -1/c3) * ...
          (1 - 1/p1) * (1 -1/p2) * (1 -1/p3) * ... *(1 - 1/q1) * (1 -1/q2) * (1 -1/q3) * ...이 된다.

φ(mn)을 알아보자.
우선 m*n은 앞의 m, n 정의에 의해
= c1^(e1+f1) * c2^(e2+f2) * c3^(e3+f3) * ... * p1^a1 * p2^a2 * p3^a3 *...q1^b1 * q2^b2 * q3^b3 *...가 된다.

앞에서 언급했듯이 지수승은 파이함수 계산에서 중요요소로 사용되지 않는다.
다만 n값이 크다는 거... 예를 들어 3^5보다 3^8이 숫자가 더 크다는 기본숫자가 크다는 의미 정도 있다.;
오일러의 파이함수를 적용하면
φ(mn) = mn * (1 - 1/c1) * (1 -1/c2) * (1 -1/c3) * ...*
                    (1 - 1/p1) * (1 -1/p2) * (1 -1/p3) * ... *(1 - 1/p1) * (1 -1/p2) * (1 -1/p3) * ...이 된다.

위의 φ(m)*φ(n)과 비교하면 (1 - 1/c1) * (1 -1/c2) * (1 -1/c3) *... 부분이 한번밖에 없음을 알 수 있다.

이러한 사실을 바탕으로 식을 구성하면
φ(mn) = φ(m)*φ(n) / ((1 - 1/c1) * (1 -1/c2) * (1 -1/c3) *...)이다.

(1 - 1/c1) * (1 -1/c2) * (1 -1/c3) *... 부분은 오일러의 파이함수 수식 형태라는 걸 누가 봐도 알 수 있다.
최대공약수 g에 대한 파이함수는 공식에 의해
φ(g) = g * (1 - 1/c1) * (1 -1/c2) * (1 -1/c3) *... 이다.
이것을 g로 나누면 φ(g) / g = (1 - 1/c1) * (1 -1/c2) * (1 -1/c3) *...이다.

대입해서 수식을 구성하면(대입부분이 분모라서 뒤집혀서 들어갈 것이다.)
φ(mn) = φ(m)*φ(n)  * g / φ(g) 로 해당 명제가 증명된다.

다음 성질과 그 증명이다.
임의의 수의 약수들의 파이 함수값들의 합은 원래 수와 같다. ∑는 시그마 기호이고 옆의 처리결과의 합계를 의미한다.
  ∑φ(d)= n
  d|n

n이 1인 경우는 1이므로 참이다.
n > 1인 경우 n을 소수의 곱으로 구성하면
n = p^i * q^j * r^k *... // p, q, r...는 소수, i, j, k,...는 지수

각각의 소수와 지수승별로 정리하면
{1, p, p^2,..., p^i} // i + 1개
{1, q, q^2,..., q^j} // j + 1개
{1, r, r^2,..., r^k} // k + 1개
...

각각의 줄단위 집합에서 하나씩 골라서 곱한게 약수가 된다.
참고로 약수의 총 개수는 (i + 1)(j + 1)(k + 1)개가 된다.

약수는 구체적으로
1, p, q, r,..., pq, qr,...pqr,... p^2*q^2*r^2, ... ,p^i*q^j*r^k...형태가 된다.
위 집합들에서 하나의 원소씩을 택해서 그수들의 곱으로 이루어지게 된다.
∑시그마 함수는 위 약수들의 파이값의 합계이므로
φ(1) + φ(p) +... + φ(pq) + φ(qr) + ...+ φ(pqr)+...+ φ(p^2*q^2*r^2) +...+ φ(p^i*q^j*r^k)...으로 표현된다.

여기서 각각의 소수들은 서로소 관계이므로 φ(mn) = φ(m)*φ(n) 공식이 성립한다. 앞에서 이미 증명하였다.
곱셈부분을 분리해서 표현하면 아래와 같다.
φ(1) + φ(p) +... + φ(p)*φ(q) + φ(q)*φ(r) + ...+ φ(p)*φ(q)*φ(r)+...+ φ(p^2)*φ(q^2)*φ(r^2) +...+ φ(p^i)*φ(q^j)*φ(r^k)...

수식을 다항식으로 고쳐쓰면 깔끔하게
(φ(1) + φ(p) + φ(p^2) +...+ φ(p^i)) *
(φ(1) + φ(q) + φ(q^2) +...+ φ(q^j)) *
(φ(1) + φ(r) + φ(r^2) +...+ φ(r^k)) *
...

이 된다. 소수별로 정리된다. 여기서 더 깔끔하게 줄일 수 있다.

앞에서 언급했듯이 소수의 지수승인 경우, 다음과 같은 수식이 성립한다.
φ(p^k) = p^k - p^(k-1) 이다.
얼핏 보기에는 뭔가 어려운 공식 같은데 단순히 전체 개수  p^k에서 p의 배수인 것들의 개수 p^(k-1)를 빼준 것이다.
p가 소수이므로 1 ~ p^k 범위의 수에서 p의 배수인 것들만이 약수가 된다.

일단 다항식의 첫번째 줄에서 요소별로 이를 적용해서 살펴보면
φ(1) = 1,
φ(p) = p - 1,
φ(p^2) = p^2 - p,
φ(p^3) = p^3 - p^2,
...
φ(p^i) = p^i - p^(i-1)

뒷식의 마이너스 부분이 앞식의 첫번째 값임을 알 수 있다. 즉 모두 더하면 맨 끝의 p^i만 남게 된다.

다항식의 다른 줄에도 모두 적용하면 파이함수 합계식은
∑φ(d) = p^i * q^j * r^k *...만 남게 된다.
이것은 앞에서 정의한 n과 동일하므로 증명이 성립된다.

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

오일러의 함수를 써내려가다보니 좀 길어졌다. 실제로 암호화에 사용되는 부분은
 m과 n이 서로소인 경우 φ(mn) = φ(m)*φ(n) 이 부분이다.

이제 RSA 핵심 원리인 오일러의 정리를 알아보기로 하겠습니다. 참조: https://namu.wiki/w/오일러의%20정리
오일러의 정리는 페르마의 소의 확장이라고 할 수 있습니다.

a와 n이 서로소인 양의 정수들이라 하면

a^φ(n) ≡ 1 (mod n)이다.

페르마 소의 경우 모듈러 n에 소수가 설정되는데 오일러 정리에서는 a와 n이 서로소이기만 하면 됩니다.

대신 지수승 부분에는 (소수-1)이 아닌 보다 작은 서로소인 수들의 갯수인 오일러 파이함수 φ(n)가 들어갑니다.

ex) a=3, n=8인 경우. n은 소수는 아니지만 3과 서로소. 오일러 파이 함수 φ(8) = 4이고
      3^4은 81이므로 8로 나눈 나머지가 1이 됨을 알 수 있다. 


증명방법은 페르마의 소와 붕어빵입니다.
a와 n은 서로소이고. n보다 작은 양의 정수 중 서로소인 수들의 집합을 {r1, r2, r3,...}라고 하면
오일러 파이함수에 의해 위 집합의 원소들의 개수는 φ(n)이 됩니다.

먼저 기본적인 수의 성질로... a와 위 집합의 원소인 임의의 ri를 곱한 값은
a과 ri이 모두 n과 서로소이므로 a*ri역시 서로소가 됩니다.
서로소라는 건 수를 소수로 나타낼 경우 둘 사이에 공통된 소수가 없다는 걸 의미합니다.
(참고로 1인 경우는 개념상 모든 수와 서로소이구요.)
서로소 관계이므로 a와 n사이에 공통된 소수가 없고, ri와 n사이에도 공통된 소수가 없습니다.
따라서 두 수의 곱인 a*ri에도 n과 공통된 소수는 존재하지 않습니다. 그러므로 필연적으로 서로소입니다.

다음으로 두 수가 서로소인 관계인 경우 나눗셈을 하는 경우

나누는 수와  나머지 역시 서로소가 됩니다. 이 부분 설명을 빠뜨리는게 많더군요.
ex) 두 수가 7, 11인 경우... 11을 7으로 나눈 나머지는 4이고 7, 4는 서로소입니다.
유념할만한게 4가 소수는 아니죠. 즉 서로소까지만 보장해줍니다.
증명은 간단합니다. a와 b는 서로소이고 a = bk + c로 나타내는 경우(c는 나머지)
만약 b와 c가 서로소가 아니면 1보다 큰 공통된 약수가 있다는 의미이고 이것을 d라고 하는 경우
우항의 식은 d로 나누어떨어진다는 의미이고 이것은 좌항의 a역시 d로 나누어떨어져야 한다는 의미입니다.
이렇게 되면 d는 a의 약수여야 하는데 이것은 a, b의 약수에 1보다 큰 d가 존재하는 걸 의미하므로 a,b가 서로소라는 전제에 위배됩니다
그러므로 나누는 수와 나머지 역시 서로소여야 합니다. 나누는 수가 n인 경우 나머지는 나머지니까 당연히 n보다 작고,

또 서로소이므로 앞에서 설정한 서로소 집합의 원소들 중 하나임을  알 수 있습니다.

페르마의 소 증명 방식과 유사하게 나머지가 서로 다름을 증명하겠습니다.
위 사실 증명: 귀류법 사용(전제를 참이라고 가정하고 해석한 결과 결론이 거짓이면 그 전제는 참이 아니라는 식. 수학증명에서 매우 자주 사용)
n과 서로소인 수들의 집합인 {r1, r2, r3,...}에서 위 집합의 원소와 a와 곱한 경우
서로 같은 나머지를 가진 두 수 ri*a와 rj*a가 있다고 전제하자(0 < ri < rj < n인 정수)
나머지가 같은 수라면 이 두 수의 차는 n으로 나누어 떨어질 것이다. 두 수의 차는 (rj-ri)*a이다.
n과 a는 서로소이므로 이게 성립되려면 rj-ri가 n으로 나누어 떨어져야 한다. 그런데 rj-ri는 n보다 작은 수끼리의 뺄셈이므로
두 수가 같아서 0이 되지 않는 한 나누어떨어지지 않는다. ri, rj는 다른 수이므로 결코 나누어 떨어지지 않는다.
나머지가 같은게 있다는 전제가 모순이 된다. 그러므로 나머지는 모두 다르다.

위 사실들을 바탕으로 n와 서로소인 {r1, r2, r3,...}집합의 원소와 a를 곱한
a*ri는 n으로 나눌시 항상 나머지가 존재하고 그 나머지와 n 역시 서로소 관계이고, 각각의 나머지가 모두 다릅니다.
각각의 원소를 곱하면 나머지가 존재하므로 위 집합 원소의 개수 φ(n)과 나머지의 개수는 동일합니다.
그러므로 나머지들의 집합은 n보다 작은 서로소인 수의 집합 {r1, r2, r3,...}과 완전히 일치하게 됩니다.
뭐가 뭐에 대응하는지 구체적으로 특정할 순 없어도 필연적으로 집합은 일치하겠죠.
그래서 나머지의 전체 곱은 {r1, r2, r3,...} 원소들의 각각의 전체곱과 같게됩니다.

이제 a*ri의 모든 수를 곱해봅시다.
(a*r1) * (a*r2) * (a*r3) * ... 를 mon n 합동식으로 처리하면 이 식은 각각의 수를 n으로 나눈 나머지들의 곱으로 처리할 수 있습니다.
(합동식의 기초적인 성질. 굳이 증명하면 a = nk + s, b = nl + t라고 할 때(s,t는 나머지)
두수의 곱은 n(kl+k+l) + st이 되고 여기서 n(~)부분은 n으로 나누면 떨어지므로 나머지의 곱인 st만 남길 수 있다.)
전체 나머지들의 곱은 바로 위 단락에서 언급했듯이 {r1, r2, r3,...} 원소들의 전체곱과 같습니다.

(a*r1) * (a*r2) * (a*r3) * ... ≡ r1*r2*r3*... (mod n) 이 성립합니다. a곱셈부분을 모두 좌측으로 위치시키면
a^φ(n)*(r1*r2*r3*...) ≡ r1*r2*r3*... (mod n)이 됩니다.

좌항과 우항의 r1*r2*r3*...가 공통된 약수이므로 나눠서 가볍게 합시다.
이때 유념할게 모듈러 n에 대해서도 처리해줘야 합니다. 나누려는 수와 n의 최대공약수를 구해서 나눠줘야 합니다.(합동식 성질 7)
r1*r2*r3*...과 n에서 n과 r1, r2, r3,...각각의 수들은 서로소라서 공통된 소수가 존재하지 않으므로 전체곱도 서로소입니다.
최대공약수는 1이므로 그대로 유지됩니다. 양변을 나누면

a^φ(n) ≡ 1(mod n)이 됩니다.

합동식의 곱셈에 대한 항등원인 1을 구하는 식이 완성되었습니다.

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

유클리드 호제법(- 互除法, Euclidean algorithm): 참조) https://ko.wikipedia.org/wiki/유클리드_호제법
정수나 다항식의 최대공약수를 구하기 쉽게 만들어주는 알고리즘.
호제법이란 말은 두 수가 서로(互) 상대방 수를 나눈다는(除) 의미.
정수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b),
a와 b의 최대공약수는 b와 r(나머지)의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여
나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

수식으로 표현해보면
a = bq + r (a, b는 대상인 정수들, a >= b 즉 계산편의를 위해 a에 크거나 같은 수 지정, r은 나머지이므로 0 <= r< b인 정수)
이때, 최대공약수 gcd(a,b)= gcd(b r)과 같습니다. 나누는 수와 나머지의 최대공약수와도 같다는 법칙입니다.
증명은 그렇게 어려운 편은 아니지만 저런 개념 자체가 굉장하죠.

ex) 78696과 19332의 최대공약수를 구하면,
78696 ＝ 19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
1368 ＝ 180×7 ＋ 108
180 ＝ 108×1 + 72
108 ＝ 72×1 ＋ 36
72 ＝ 36×2

이전식의 나누는 수와 나머지가 다음식에서 좌측으로 ↙ ↙ 식으로 위치가가 이동하죠.
나눗셈을 수행하면 숫자 단위가 팍팍 줄어나가므로 엄청나게 큰 수들의 최대공약수를 구하는 경우
획기적으로 계산시간을 줄여줍니다.

증명)
a, b의 최대공약수 gcd(a, b) = d라고 하는 경우
a= da', b = db'로 표현할 수 있습니다. 이때 a', b'는 서로소 관계입니다.
a = bq + r을 r 기준으로 재구성하면
r = bq - a이고 a, b에 최대공약수로 구성한 값을 대입하면
r = db'q - da' = d(b'q - a')가 되어 r은 d로 나누어 떨어지므로 d는 r의 약수입니다.
즉, a, r이나 b, r의 관계에서 d는 공약수입니다.
일단 공약수가 맞다는 건 증명되었습니다.

유념할게 b와 r사이에 d가 공약수임이 증명되었지만 최대공약수인지는 모른다는 점입니다.
그래서 해당 공약수 d가 b와 r사이의 최대공약수인지 확인해야 합니다.

증명을 위해 귀류법을 사용합니다.(어떤 전제를 참이라 가정하고 식을 전개하는 경우 결론이 모순이면 전제가 거짓이라는 증명방식)
r과 b 사이에 공약수 d보다 큰 최대공약수가 존재한다고 가정하고 g라고 합시다.(g > d)
r = gr", b = gb"로 표현가능합니다.(r"와 b"는 서로소)

a = bq + r 수식을 다시 쓰면
a = gb"q + gr" = g(b"q + r")이 되어 a 역시 g로 나누어 떨어집니다.
즉 a 역시 d보다 큰 g를 약수로 가진다는 의미인데 이것은 a, b의 최대공약수가 d라는 사실에 위배되죠.
그러므로 r과 b 사이에 d 공약수보다 큰 최대공약수가 존재한다는 것은 사실이 아닙니다.
이에 따라 r, b사이에서도 d가 최대공약수가 됩니다.

참고로 증명방법은 다른 방식도 상당히 많습니다. 다른 사이트에서는 다른 방식으로 증명하기도 함.
여담으로 이제껏 많은 증명을 다뤘는데 방식이 많이 비슷비슷하죠.
소수, 서로소, 최대공약수 이런 개념들로 분해하고, 귀류법적 증명이 상당히 많음.

// c 소스로 나타내면 다음과 같습니다.
int gcd(int a, int b)
{
  return b ? gcd(b, a % b) : a;
}


유클리드 호제법의 확장:
별도의 이론, 정리는 아니고 최대공약수를 구하는 유클리드 호제법을 사용하는 과정에서
ax + by = c 형태의 일차 부정방정식의 정수해 또한 구할 수 있다는 의미입니다.(일거양득)
여기서 c는 반드시 a, b의 최대공약수의 배수여야 하므로 부정방정식이 맞게 성립하는지 여부도 확인할 수 있습니다.
(참고로 c가 a, b의 최대공약수의 배수인 경우 정수해가 반드시 존재한다는 것은 베주의 항등식으로 증명됨. 맨 아랫부분 부록 참조)

특히, a, b가 서로소(최대공약수 gcd(a,b) = 1)인 경우 유용하다.이 경우 위의 식은 ax + by = 1가 되고 법 b 합동식으로 표현하면 ax≡1 (mod b)이다.
법 b 합동식에서 곱셈연산시 x는 a의 역원(modular multiplicative inverse)이 된다. 물론 a 역시 x의 역원이다.(상호 역원관계)
합동식에서 곱셈의 역원은 RSA 암호화 알고리즘, 중국인의 나머지 정리 등에서 뼈대가 됩니다.(중국인의 나머지 정리는 맨 아랫부분 부록 참조)

ex) 710x + 68y = 8의 정수해를 구하는 문제인 경우.

a=710, b=68인 경우 유클리드 호제법을 전개하면 다음과 같습니다.
710 = 68 * 10 + 30
68 = 30 * 2 + 8
30 = 8 * 3 + 6
8 = 6 * 1 + 2
6 = 2 * 3 + 0
최대공약수는 2임을 알 수 있고, 8은 최대공약수 2의 배수이므로 정수해가 존재하고 방정식은 맞게 성립합니다.
만약 10이 아닌 1이나 3 등 최대공약수 2의 배수가 아니면 방정식의 정수해는 존재하지 않습니다.

이 경우 먼저 710x + 68y = 2의 해를 구한 후, 8 = 2*4이므로 구해진 해에 4배를 곱하면 최종해를 구할 수 있습니다.
(무수히 많은 정수해들 중 하나를 의미, 부정방정식이므로 해가 무수히 많이 존재합니다.)
710을 a, 68을 b로 치환하고 식을 나머지 기준으로 구성합니다.
다음줄의 제수(나누는 수)와 나머지는 이전줄의 값으로 치환합니다.
a = 10b + 30 → 나머지 30 = a - 10b
b = (a - 10b)2 + 8 → 나머지 8 = -2a + 21b
a - 10b = (-2a + 21b)3 + 6 → 나머지 6 = 7a - 73b
-2a + 21b = 7a - 73b + 2 → 나머지 2 = -9a + 94b
마지막 줄은 변환 필요 없음.(나머지가 최대공약수일 때까지만 전개하면 된다.)

-9a + 94b = 2이므로 x가 -9, y가 94일때 2가 된다. 이 값에 4배를 곱한
x = -36, y = 376은 710x + 68y = 8의 정수해들 중 하나이다.

참고로 이런 부정방정식의 정수해를 구하는 형태를 디오판토스 방정식이라고 합니다..
일차 부정방정식의 해에는 일정한 규칙성이 존재하는데 
특정한 해가 (x, y)라면 a, b의 최대공약수를 d라고 할 때 (x + k*b/d, y - k*a/d) 역시 해가 됩니다.(k는 임의의 정수)
왜냐하면 a(x + kb/d) + b(y - ka/d) = ax + kab/d + by -kab/d = ax + by가 되기 때문이죠.
즉 x는 b/d단위로 증감, y는 a/b단위로 증감(단 한쪽은 증가하면 한쪽은 감소)해도 덧붙인 값들이 상쇄되기 때문에 최종값은 동일하게 유지됩니다.
(어려운 형태의 수식은 아님. 다른 변수 앞에 붙은 상수를 곱하고, 한쪽은 더하기, 다른쪽은 빼기로 구성하면 상쇄될 것임을 직관적으로 알 수 있다.)
이에 따라 ..., (-36, 376), (-2, 21), (32, -334), (66, -689), (100, -1044), ... 규칙적으로 정수해가 존재합니다.

위 부정 방정식은 710x ≡ 8 (mod 68)의 합동식으로 구성할 수 있습니다. 참고로 합동식의 경우 몫인 y값에는 관심을 두지 않고 x에만 관심을 둡니다.

해는 위처럼 유클리드 호제법의 확장으로 구하면 x ≡ -36 (mod 68)인데 이를 0이상의 정수로 보기 좋게 나타내면 x ≡ 32(mod 68)입니다.

주의할게 해는 하나 더 존재하는데 x ≡ 66 (mod 68)도 해가 됩니다.

a, b의 최대공약수가 d라면 d개만큼 해가 존재하는데 여기서는 2이므로 해가 2개 존재합니다.

만약 서로소이면 최대공약수가 1이므로 해는 하나만 존재합니다.

왜냐하면 앞에서 보았듯이 x는 b/d만큼, y는 a/d만큼 규칙적으로 증감(참고로 한쪽이 증가하면 다른쪽은 감소해야 됨)해도 해가 되기 때문입니다.
즉 특정 해 x에서 68/2 = 34만큼 증감한 ..., -36, -2, 32, 66, 100, ...도 해가 됩니다.
주의할게 모듈러 68인 상황에서 68이 증감한다는 것은 합동식에서 같은 해라는 의미입니다.
합동식에서 나머지가 같은 수들은 하나의 집합에(동치류라고 함) 속하고 하나로 봅니다. 위에서 x가 -36, 32, 100 모두 x≡32 (mod 68)입니다.
x는 b/d단위로 증감하면 해가 되므로 0 ~ (d-1) 범위의 수를 곱해 더한 (x), (x + b/d), (x + 2b/d),...,(x + (d-1)b/d)까지만 다른 해가 됩니다.

(0 ~ (d-1)까지이므로 개수는 d개) 이를 초과한 경우 이전 해들과 같은 해입니다.  이전해에서 딱 모듈러 수 단위로 증가한 수일뿐입니다.
가령 d를 곱해 더한수는 (x + db/d) = (x + b)인데 이것은 x에 모듈러인 b를 더한 값이므로  x와 같은 해가 됩니다. x ≡ x + b (mod b)
d+1을 곱해 더한수는 (x + b + b/d)인데 마찬가지로 x + b/d에 b를 더한 값일뿐이므로 같은 해입니다. x + b/d ≡ x + b + b/d (mod b)

그리고 합동식으로 구성시 각 수들이 서로소가 아니면 서로소 관계가 되도록 공약수로 나누어

보다 작은 단위의 모듈러로 만들고 다수의 해를 1개로 만들 수 있습니다.(서로소이면 해가 하나 존재)

위의 경우  710x ≡ 8 (mod 68) 세 수를 최대 공약수 2로 나누어버리면 355x ≡ 4 (mod 34)가 됩니다. (합동식 성질 9)

해는 x ≡ 32 (mod 34) 하나 존재하고, 이것은 모듈러 68일 경우 x ≡ 32 (mod 68),  x≡66 (mod 68) 모두 만족하죠. 

아마 위에서 번거롭게 2개의 해를 도출할 때 이처럼 하나의 해로 구성하고 싶은 충동이 들었을 겁니다.^^

참고로 합동식에서 나눠서 가볍게 만드는 다른 방법도 있습니다. 합동식 성질 7을 이용하면 됩니다.

가령 6x ≡ 4 (mod 5)는 세 수에 공통되는 공약수는 없지만 6, 4는 공약수 2가 존재합니다. 공약수 2와 모듈러 5는 서로소 즉 최대공약수가 1이므로 

모듈러는 변화 없이 나누면 됩니다. 3x ≡ 2 (mod5)로 축약가능함. 해는 식이 단순해서 그냥 암산으로 대입해도 x ≡ 4 (mod5)가 나오죠.

==================================================================================================================

RSA 암호화, 복호화 분석: 참조) https://ko.wikipedia.org/wiki/RSA_암호
                                              https://en.wikipedia.org/wiki/RSA_(cryptosystem)

RSA는 오일러의 정리를 바탕으로(혹은 페르마의 소. 오일러의 정리가 페르마의 소 정리를 소수→서로소인 수까지 확장한 것임)
암호화 체계를 구성하고 있습니다.

일단 모듈러 n은 소인수분해를 어렵게 하기 위해 거대한 두 소수 p, q를 곱하여 n = p * q로 생성합니다.
φ(n)은 1부터 n까지의 수 중 n과 서로소인 수들의 개수를 의미하며 오일러 파이함수의 결과값입니다.
p, q는 소수이므로 서로소이고 오일러 파이함수 결과는 φ(n) = φ(pq) = φ(p)*φ(q) = (p-1)*(q-1)입니다.(서로소일때만 적용됨)
RSA 암호화 체계에서는 평문 m이 지수승의 대상이 됩니다.
그리고 지수승 부분을 개인키과 공개키 한쌍으로 구성해 해당키들의 지수승 연산으로 암호화와 복호화를 수행합니다.
평문 m과 모듈러 n(pq곱)은 m < p, m < q이면 항상 서로소가 됩니다. 소수는 자기자신보다 작은 수와는 항상 서로소입니다.
이제 오일러 정리를 적용하면 다음과 같습니다.
m^φ(n) ≡ 1 (mod n)

합동식에서 1은 곱셈의 항등원입니다. 1은 몇 지수승을 하더라도 항상 1이 되므로 임의의 양의 정수 k에 대하여
m^(φ(n)*k) ≡ 1 (mod n) 이 됩니다.

그리고 평문 m과 항등원 1을 곱하면 다시 m이 되므로
m*m^(φ(n)*k) ≡ m*1 ≡ m (mod n) 입니다.

좌변 m*m^(φ(n)*k)을 모두 m의 지수승으로 다시 고쳐쓰면
m^(φ(n)*k + 1) ≡ m (mod n) 입니다.

여기서 좌변의 지수승 부분에 집중해봅시다.
만약 어떤 수들을 연산해서 φ(n)*k + 1 결과가 되고(k는 임의의 양의 정수)
합동식에서 이 값을 지수승으로 연산하면 최종결과는 원래의 평문 m이 될 것입니다.

가령 e, d는 양의 정수이고 e*d = φ(n)*k + 1 이면 암호화 체계를 구성할 수 있게 됩니다.
합동식으로 이를 나타내면 ed ≡ 1 (mod φ(n)) 이 됩니다.
여기서 1은 합동식 곱셈의 항등원이므로 e와 d는 법 φ(n)에 대하여 곱셈시 서로 역원관계입니다.(승산역원이라고도 함)
주의할게 여기서 법(모듈러)는 n이 아니라 φ(n)이라는 것입니다.
위의 식을 성립하는 e, d 한쌍은 한쪽으로 암호화하면 한쪽으로는 복호화가 가능하게 됩니다.
이러한 키를 하나는 공개키로 지정해 공개하고, 하나는 개인키로 지정해 철저히 보안유지합니다.

ed ≡ 1 (mod φ(n)) 식에서 e키 지정시 몇가지 사항을 유의해야 합니다.
우선 e와 φ(n)는 항상 서로소여야 합니다.
유클리드 호제법 부분에서 증명하였듯이 일차부정방정식 혹은 이를 변환한 합동식이 정수해를 가지려면
부정방정식의 결과 부분 혹은 합동식의 우변이 반드시 최대공약수의 배수여야 합니다.
즉 e, n의 최대공약수가 1인 경우 즉 서로소일때만 합동식의 우변에 1이 오는게 가능합니다.
그리고 e를 1로 지정하면 암호화된 값이 평문 m과 항상 같으므로 암호화 자체가 안됩니다.
한가지 더 참고해볼게 소수 중에 오로지 짝수는 2뿐입니다. 다른 짝수는 모두 2의 배수이기 때문입니다.
2를 제외한 모든 소수는 홀수가 되는데 이에 따라 φ(n) = (p-1)*(q-1)에서
p, q는 서로 다른 소수이므로 (p-1)나 (q-1) 중 하나는 반드시 짝수가 되고, 곱의 결과인 φ(n)은 항상 짝수가 됩니다.
e가 2이면 φ(n) 사이에 최대공약수 2가 존재하여 서로소가 아니므로 앞서 말했듯이 우변이 1인 식은 결코 성립할 수 없습니다.
그래서 실질적으로 e는 소수 3부터 지정 가능합니다.
e를 지정하고 ed ≡ 1 (mod φ(n)) 합동식을 확장된 유클리드 호제법으로 풀면 역원 d를 구할 수 있습니다.

구체적인 암호화, 복호화 과정을 살펴보자. e는 공개키, d는 개인키라 할 때
평문 m을 e지수승해 c = m^e (mod n) 암호문 c를 생성하고(암호화),
이 암호문 c를 d지수승하면 c^d ≡ (m^e)^d ≡ m^ed ≡ m^(φ(n)*k + 1) ≡ m*m^(φ(n)*k) (mod n)이 됩니다.

여기서 c^d ≡ (m^e)^d 표현 부분에서, c는 모듈러 mod n 연산을 거친 나머지 값인데
바로 c에 m^e(나머지 적용 전의 수)를 대입하는 것에 약간 의아한 생각이 들 수 있습니다.
이를 테면 c = 27 (mod 10)라면 c는 27 아닌 나머지값인 7인데, 다음 줄에서 c부분에 7 아닌 27을 넣 것에 의아할 수 있다.
합동식에서는 이게 가능합니다. 합동식에서는 모듈러 n의 배수만큼 더하거나 빼든 나머지는 변동이 없으므로 이러한 수들은 모두 합동입니다.
예를 들어 모듈러 10이면 2, 12, 22, 32,...수들은은 서로 합동이고, 7, 17, 27, 37,...수들은 서로 모두 합동이다.
그러므로 합동식의 좌변이나 우변을 입맛대로 모듈러 n의 배수 부분을 소거해 간략하게 표시할 수도 있고,
필요에 따라 모듈러 n의 배수만큼 증감해서 표시해도 아무런 문제가 없습니다.
이러한 개념을 염두에 두고 증명을 해보면
우선 암호화식 c = m^e (mod n)에서 m^e은 nk + c (k는 식을 만족하는 정수), 즉 n의 배수 + c로 표현가능합니다.
이에 따라 c^d = (nk + c)^d가 되는데, 여기서 우변 (nk + c)^d = nk(~~~) + c^d 형태로 전개된다. nk(~~~)은 nk 곱셈이 포함된 부분들의 식이다.
c^d 빼곤 필연적으로 nk곱이 포함되게 된다. 합동식에서 n의 배수부분은 합동식에서 나누어 떨어지므로 소거가능하고(나머지의 변동이 없음)
c^d와 합동이 된다.

또한 mod n 내부에 mod n식이 들어가는 경우 안의 mod n은 소거가능하다는 기본성질로부터(합동식 성질 11)
c^d (mod n) → (m^e(mod n))^d (mod n) → (m^e)^d (mod n)이 되는 것으로 이해할 수도 있습니다.
합동식 성질 11의 증명도 결국 위에서 서술한 n의 배수 + 나머지 형태로 구성해서 증명하므로 결국 본질은 같은 것입니다.


m^(φ(n)*k) 부분은 오일러 정리에 의해 1(곱셈의 항등원)이 되므로
결국 c^d ≡ m (mod n), 즉 평문 m으로 복원되게 됩니다.(복호화)

이처럼 RSA는 "오일러 정리 * 평문 m이다."라고 말 할 수 있을 정도입니다.

한편 위키에서처럼 페르마의 소를 통해 증명도 가능한데 n이 두 소수 p,q 의 곱으로 이루어졌기 때문입니다.
앞서 기술했듯이 p, q가 소수이면 오일러 파이 함수의 결과값 φ(n)은 (p-1)*(q-1)입니다.
φ(n)에 이 값을 넣어서 암호화, 복호화 과정을 다시 표현해보면
암호화시 c = m^e (mod n)으로 암호문 c를 생성하고
복호화시 c^d ≡ (m^e)^d ≡ m^ed ≡ m^(φ(n)*k + 1) ≡ m*m^(φ(n)*k) ≡ m*m^(k*(p-1)*(q-1)) (mod p)

한가지 짚고 넘어갈게 c는 mod n의 연산의 결과값인데 다른 모듈러인 mod p 연산의 대상으로 별도의 처리 없이 바로 쓸 수 있느냐 하는 점입니다.
c는 m^e의 mod n 합동식의 결과(나머지)이므로 m^e = n의 배수 + c로 표현가능합니다.
이에 따라 두번째 복호화식에서 (m^e)^d = (n의 배수 + c)^d 이고 이를 풀어쓰면 n(~~~) + c^d 형태가 된다. n(~~~)은 n 곱셈이 포함된 부분들의 식이다.
n의 배수는 개념필연적으로 n의 약수인 p의 배수이기 때문에(예를 들어 15의 배수는 무조건 3의 배수이다.) 나누어 떨어지므로
합동식에서 소거가능합니다. 결국 mod p 합동식에서 (m^e)^d는 c^d와 합동이 됩니다.
즉 모듈러가 n에서 p로 바뀌어도 c^d ≡ (m^e)^d (mod p) 식은 맞게 성립하게 됩니다.(모듈러가 약수인 경우 무조건 성립함)

모듈러 p 합동식에서 페르마의 소 정리에 의해 m^(p-1)은 1이 되고
1을 몇 지수승해도 1이므로 m^(k*(p-1)*(q-1)) 역시 1이 되어 평문 m만 남습니다. 즉
c^d ≡ m (mod p)이 됩니다. 모듈러 q에 대해서도 마찬가지로 전개하고, 페르마의 소 정리를 적용하면 m^(q-1)이 1이 되므로
c^d ≡ m (mod q)이 됩니다.

이제 위 사실로부터 mod n 즉 mod pq에 대해서 c^d와 m이 합동이라는 걸 증명해야 합니다.
위 두 식에 의해 (c^d - m)은 p의 배수이기도 하고, q의 배수이기도 합니다.
그러므로 (c^d - m)는 p와 q의 최소공배수의 배수여야 하는데(기초적인 성질. 합동식 성질 10 참조)
p, q는 소수이므로 최소공배수는 서로의 곱인 pq 즉 n입니다.
이에 따라 c^d ≡ m (mod n) 역시 성립합니다. 개념빨로 해결되죠.^^;
ex) 17≡2(mod 3), 17≡2(mod 5)이면 17≡2(mod 15)이다.


아래는 이해를 돕기 위해 매우 작은 소수들을 선택해 암호화, 복호화를 수행하는 예이다.
1. 서로 다른 두 소수 p = 61, q = 53을 선택한다.
두 수의 곱인 n = 3233이다.
2. 오일러 파이함수의 값을 구한다.(1부터 n까지의 수들 중 n과 서로소인 수들의 개수)
φ(n) = (p-1)*(q-1) = 3120
3. 키 산출식 ed ≡ 1 (mod φ(n))에서 e를 지정하고, 역원 d를 계산을 통해 산출한다.
φ(n)값인 3120 이하인 양의 정수 중에서 서로소인 e = 17을 선택한다.
17d ≡ 1 (mod 3120) 합동식을 확장된 유클리드 호제법으로 풀면 역원 d = 2753이 된다.
4. n과 e를 공개로 설정하고 상대방에게 전송한다.
d는 개인키로 노출되지 않도록 보안유지에 신경써야 한다.
5, <n, e>를 전송받은 측은 평문 m = 65를 암호화해서 암호문 c로 만든 후 전송한다.
c = m^e (mod n) → c = 65^17 (mod 3233) = 2790
참고로 대입기호 =로 받는 경우 우리가 일상적으로 나머지라고 부르는 값을 취한다.(0 <= c < n)
6. 암호문 c를 수신한 측에서는 개인키로 복호화를 수행한다.
m = c^d (mod n) → m = 2790^2753 (mod 3233) = 65

---------------------------------------------- 참고) 복호화 실제 구현 ----------------------------------------------
참고로 실제 프로그래밍으로 복호화 구현시 pq같은 거대한 수의 연산은 부담이 되므로
유명한 암호화 라이브러리(OpenSSL, Java and .NET)들에서는 중국인의 나머지 정리를 기초로 컴퓨터 연산에 효율적인 복호화를 수행한다.
pq보다 작은 수인 p, q를 모듈러로 개별 연산 후 조합하는 방식을 취하므로 이 경우 p, q값을 보존하고 있어야 한다.
(중국인의 나머지 정리는 부록 참조)

중국인의 나머지 정리에 의해 p, q가 서로소인 경우
x ≡ c^d (mod p)이고 x ≡ c^d (mod q)를 동시에 만족하는 해 x는 반드시 존재하고 그 해는 mod pq에서 유일하다.
그 해는 반드시 x ≡ c^d (mod pq)가 될 것이다. 왜냐하면 애초부터 c^d이라는 동일한 수를 대상으로 했기 때문이다.
마치 결과를 미리 알고 문제를 구성하는 것과 같다.
가령 8(mod15)에서 모듈러 15는 소수 3*5로 구성된다.
8을 15의 약수인 작은 모듈러 3, 5연산으로 변환하면 8≡2(mod3)과 8≡3(mod5)이다
이를 바탕으로 문제를 구성해보면 "x≡2(mod3), x≡3(mod5)를 동시에 만족하는 해 x를 구하시오."가 된다.
해는 x≡8(mod15)가 된다. 이론적으로 해석하면 개별적인 mod p, mod q 합동식을 모두 만족하는 x는 반드시 존재하고
p, q의 최소공배수 15를 모듈러로 취할시 해 x≡8(mod15)는 유일하다는 것이다.

여기서 x ≡ c^d (mod pq) 합동식은 작은 수인 p, q의 모듈러 연산으로 개별적으로 쪼개서 구성할 수 있고,
개별적인 mod p, mod q 연산으로부터 다시 해를 구할 있는 관계에 있게 된다.
구현코드에서는 작은 단위의 mod p, mod q연산의 결과를 조합하여 해를 구한다는 점에 포커스를 맞추고 있다.

중국인의 나머리 정리가 구현코드의 이론적인 토대이지만 널리 알려진 공식대로 해를 구하진 않는다.
널리 알려진 해의 공식은 x ≡ (a1*o1*x1) + (a2*o2*x2) + (a3*o3*x3) + ... + (an*on*xn) (mod m) 형태이다.(아래 부록 참조)
그런데 이 방식대로 해를 구할시 덧셈의 최종값은 pq를 초과하는 경우가 많다. 즉 pq보다 작음을 보장하지 않는다.
연산의 값이 pq 이상인 경우 평문 m을 구하기 위해서는 pq를 나눈 나머지를 취해야 한다.

실제 프로그래밍 구현에서는 위 과정이 필요 없도록 반드시 pq보다 작게 나오게 식을 구성한다. 아래와 같이 구현한다.

우선 계산에 자주 사용되는 dp, dq, qinv은 미리 계산해놓는다.
dp, dq는 페르마의 소 정리로 간결하게 처리 후 남는 지수승 부분(실제 연산시 이 지수승만 수행하면 됨)을 의미한다.
합동식에서 거대한 지수승은 모듈러가 소수이고 지수승의 대상과 서로소인 경우 페르마의 소 정리로 간단하게 줄일 수 있다.
가령 3^59 mod7은 ((3^6)^9)*3^5 mod7으로 고쳐쓸 수 있고, 여기서 3^6 mod 7은 페르마의 소 정리로 1이 되고, 1은 지수승해봐야 1이므로
3^5 mod7으로 간단하게 줄일 수 있다. 3^59지수승의 거대한 수의 계산 없이 3^5지수승만 계산해서 처리하면 된다.
이렇게 페르마의 소는 거대한 지수승을 줄이는 용도로도 사용가능하다. 오일러의 정리 역시 이러한 목적으로 자주 사용된다.
복호화시 암호문에 거대한 d지수승을 하므로 페르마의 소 정리로 이 부분을 아래와 같이 작은 수로 간단하게 줄일 수 있다.
dp = d (mod p-1)
dq = d (mod q-1)
위 식은 복잡한 게 아니라 d를 (소수-1)로 나눌시 나머지를 의미한다.
실제 합동식에서 연산시 dp, dq지수승만 계산해도 페르마의 소에 의해 d지수승과 같은 결과가 된다.
c^d ≡ c^dp (mod p)
c^d ≡ c^dq (mod q)

qinv는 mod p 합동식에서 곱셈시 q의 역원이다. 아래에서 h를 얻기 위해 사용된다. 역원이므로 mod p에서 q*qinv는 1이 된다.
qinv = q^-1(mod p)

암호문 c의 복호화 요청시 아래와 같이 연산이 수행된다. m1, m2는 암호문을 개별적인 mod p, mod q 연산한 결과값이다.
m1 = c^d ≡ c^dp (mod p)
m2 = c^d ≡ c^dq (mod q)
아래 m은 위 두식을 만족하는 해가 된다.
h = (qinv * (m1 - m2)) (mod p)
m = m2 + q*h

해가 맞게 성립하는지, 즉 m (mod p) = m1이 되는지, m (mod q) = m2가 되는지 확인해보자.
해 m에 mod p 합동식을 적용해보면
m (mod p) = (m2 + q*h) (mod p) // 위 h 대입식을 풀어쓴다.
= (m2 + q * ((qinv * (m1 - m2)) (mod p)))(mod p) // mod p가 전체를 감싸므로 안의 mod p는 생략할 수 있다.(합동식의 기본성질)
= (m2 + q*qinv*(m1 - m2)) (mod p) // q, qinv는 서로 역원관계이므로 q*qinv는 항등원 1이 된다.
= (m2 + m1 - m2) (mod p)
= m1 (mod p)
= m1

다음으로 mod q 합동식을 적용해보자.
m (mod q) = (m2 + q*h) (mod q) // q*h는 q로 나누어 떨어지므로 합동식에서 소거 가능하다.
= m2 (mod q)
= m2

위에서 보듯이 해 m은 두 식을 모두 만족함을 알 수 있다.
이 해는 중국인의 나머지 정리에 의해 개별 모듈러 p, q의 최소공배수 pq 즉 n 합동식으로 구성시 유일한 해가 된다.
해를 합동식으로 표현하면 m ≡ (m2 + q*h)(mod n)이 된다.

주의깊게 살펴볼게 h는 mod p 합동식 연산의 나머지이므로 h의 최대값은 p-1이다.
마찬가지로 m2는 mod q 연산의 나머지이므로 최대값은 q-1이다.
그러므로 m2 + hq의 최대값은 q-1 + (p-1)q = pq-1이다. 이 값은 반드시 pq보다 작으므로
pq보다 큰 수인지 체크해서 나누는 과정을 수행할 필요 없이 바로 평문이 된다.
즉 (m2 + q*h)(mod n) = m2 + q*h이다.
복호화에서 연산부담이 되는 매우 큰 수 pq의 연산을 배제할 수 있게 된다.

ex) p = 61, q = 53, n = p*q = 3233, 암호문 c = 2790, 개인키 d = 2753일 때
원래의 복호화 식 m = 2790^2753 (mod 3233) = 65을 위의 방식으로 풀어쓰면 다음과 같다.

먼저 복호화시 항상 사용하는 아래의 3개를 미리 연산해 저장해 놓는다.
dp = d (mod p-1) = 2753 (mod60) = 53
dq = d (mod q-1) = 2753 (mod52) = 49
qinv = q^-1(mod p) = 53^-1(mod61) = 38 // 유클리드 확장 호제법으로 53*qinv ≡ 1 (mod 61) 합동식을 풀면 된다.

이제 암호문 c의 해석을 요청받을 때 mod p, mod q 합동식 연산을 해서 m1, m2, h를 구한 후 이들을 조합하면 된다.
m1 = c^d ≡ c^dp (mod p) = 2790^53 (mod 61) = 4
m2 = c^d ≡ c^dq (mod q) = 2790^49 (mod 53) = 12
h = (qinv * (m1 - m2)) (mod p) = (38 * -8) (mod 61) = 1
m = m2 + q*h = 12 + 1*53 = 65

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

공격 포인트와 방어, 소수 p, q 선택시 제안사항

1. 소인수분해 시도

2. 개인키 무작위 대입

3. 암호화된 메시지로부터 평문 유추

 

============================================== 부록) 수학 이론 ==============================================

나눗셈 정리

/////////////////////////////////////////////////////////////////////////

임의의 양의 정수 a, b에 대하여 
b = aq + r    (0  <=  r < a)를 만족시키는 정수 q, r이 유일하게 존재한다.

r은 remainder 나머지를 의미한다.

q는 quotient  몫을 의미한다.

//////////////////////////////////////////////////////////////////////////

증명을 위해 r기준으로 식을 생각해보자. 

r = b - qa   (a, b는 양의 정수, r >= 0인 정수)

중요 포인트는 나누는 수 a보다 작은 r이 존재하는 것과(존재성)

이러한 a보다 작은 r이 딱 하나만 있다는 것을(유일성) 증명해야 한다.

아직은 저 식을 만족하는게 몇개 있는지 모른다는 가정하에

r = b - qa 식을 만족하는 r을 원소로 하는 집합을 생각해보자.

전제는 a, b는 양의 정수, r >= 0인 정수이다. 유념할게 r이 a보다 작은 수라는 건 전제가 아니다. 

위 조건을 만족하는  원소 중 최소값을 뽑아서 그 최소값이 a보다 작다는 것을 증명해야 한다.

즉 a보다 작은 r이 존재한다는 것을 증명해야 한다.(존재성)

이것은 아래에서 첫번째로 증명해야 할 사실이다.

우선 r 원소를 집합에 담는다고 할 때  집합의 원소는 반드시 존재하게 된다.

이 부분은 뜬구름 식으로 생각할 필요 없다.

구체적으로 서술하면 (참고로 r >= 0 전제조건을 만족시켜야 한다는 것을 유념하자)

우선 바로 생각할 수 있는게 q = 0인 경우  r = b가 되므로 하나의 원소는 분명히 존재한다.

그리고 y = b-ax 형태의 일차 방정식 그래프를 생각하면 된다. 

이 중에 y가 0이상 정수, q가 정수를 만족하는 부분이 집합 원소에 해당될 것이다.

ex) b=10, a=3이면 식을 만족하는 해들을 (q, r)로 표현할 때 (3, 1), (2, 4), (1, 7), (0, 10), (-1, 13), (-2, 16),....식으로 

     r의 원소는 존재할 것이다.

   
좌우지간 어떤 경우에도 모두 집합의 원소가 1개 이상 존재하게 된다는 것은 사실이다.

그리고 r은 0이상의 정수 범위에 해당하므로 해당집합에서 최소값이 분명히 존재한다.

즉 최소값을 특정할 수 있다.(well-ordering 원리(정렬 원리)라고 함. 어떤 집합에서  순위를 정할 수 있다는 의미 

자연수의 집합에서 최소값이나 7이상의 정수의 집합 등에서 최소값은 분명히 존재하게 되고 이를 기준으로 순위를 정할 수 있음.  

이에 반해 막연한 자연수의 최대값(한없이 크다)이나 정수에서 최소값(마이너스쪽으로 한없이 큰 경우 생각해보라), 

0에 가장 가까운 소수점 숫자(0.0000000~~~~~로 무한대로 갈 수 있다) 등은 무한대로 존재하므로 특정이 안된다.

자연수의 최대값, 음수의 최소값,  0에 가장 가까운 소수점 숫자 등의 기준으로는 순위 정하는게 안된다.

이런 의미로 이해하면 됨.)

집합에서 최소값인 원소를 r'라 하고 이게 a보다 작다는 것에 대해 증명해보자.
이를 증명하려면 귀류법을 사용한다.(전제한 조건이 참이라는 가정하에 이론을 전개하지만 결론이 모순이기 때문에 전제가 거짓라는 증명 방식.)
최소값인 r' >= a 일 때 모순이 생기면 r' >= a이라 전제가 거짓이므로 집합중 최소값인 r'는 a보다 작다는게 성립하게 됩니다.
r' >= a라고 전제할 때 r' = b - q'a >= a이 된다.

모든 변에서 a를 빼주면 r' - a = b - (q' + 1)a >= 0 형태로 구성된다.
두번째 부분을 유심히 보면  b - ○a 형태로 집합의 성립식의 형태이다. 
그리고 좌항 (r' - a)는 0이상이고 r'에서 뺀 값이므로 r'보다 작다. 즉 r'보다 작은 0이상의 정수라는 소리이다.

즉 b - ○a 수식을 만족하는 집합의 원소  (r' - a)가 존재하고 이게 r'보다 작다는 걸 의미하므로 r'가 최소값이라는 것에 모순이 된다.
이에 따라 전제가 거짓이므로 최소값 r'는 반드시 나누는 수인 a보다 작아야 한다.

이제 0이상 a미만의 r은 2개 이상 존재할 수 없고 유일하게 한개만 존재한다는 것을 증명해보자.(유일성) 

이것 역시 귀류법으로 증명한다.
만약에 또 다른 존재가 있다고 가정하고 이게 모순되는 결과가 나오면 또 다른 존재는 없다는 소리이다.

0 <=  r" <a이면서  수식을 만족하는 또다른 r"가 있다고 가정하자. r" = b - q"a 이 될 것이다.
그리고 앞의 증명에서 최소값인 r' = b - q'a 을 만족하는 r'는 존재한다.( 0 <=  r' <a )

b기준으로 재구성하면

b =  r' + q'a 

b = r" + q"a 이므로 r' + q'a = r" + q"a 가 된다. 식을 재구성하면 r' - r" = (q"-q')a이다.
여기서 (q"-q')a 부분을 살펴보자. q', q"서로 다른 값이므로 절대값|q"-q'|는 반드시 1이상의 정수이다.

1이상의 정수와 a를 곱하면 값은 a이상이어야 한다. 
그러므로 |r' - r"| = |(q"-q') * a| >= a이다.

가장 좌변인 |r' - r"|를 살펴보자.

0 <=  r' <a , 0 <=  r" <a 조건인 경우 다른 나머지끼리 뺀 값의 절대값 |r' - r"|은 반드시  a보다 작아야 한다. 

그래서 위식에서 a 이상라는 건 모순이다.

그러므로 a보다 작은 또다른 나머지 r이 존재한다는건 거짓이고 유일하게 1개만 존재한다.

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

 * 약수, 배수 개념은 0이 들어가면 헷갈리기 쉽습니다.

   이때는 나누어 떨어지는(나머지가 0인) 나누기로 생각하는게 좋습니다.

   일단 약수는 어떤 수가 나누어질 때 나누는 수(분모)를 말합니다. 수를 0으로 나눌 수는 없으니 0이 어떤수의 약수가 되는 일은 없습니다.

   이에 반해 0/1, 0/2, 0/3...이렇게 0 제외 모든 수를 나누는 게 가능하니, 0의 약수는 0을 제외한 모든 수가 되겠습니다.

   배수는 나누기시 분모가 대상이고 분자가 결과가 됩니다. ex) 0/2, 2/2, 4/2, 6/2, ...나누어 떨어짐 ->  2의 배수는 0, 2, 4, 6...

   일단 분모가 0이면 식이 성립불가능하므로 0의 배수는 개념성립이 불가능하다는 것을 기억해놓습니다.

   왠지 0*0 = 0이니 0이 배수일 것 같은데 개념 자체가 불성립함을 주의합니다.

   이에 반해 0/1, 0/2, 0/3...이렇게  분자에 0이 되는건 가능하므로 0은 0을 제외한 모든 수의 배수가 됩니다.

   무엇(대상)의 약수라고 할때 대상은 분자... 약수는 분모

   무엇(대상)의 배수라고 할때 대상은 분모... 배수는 분자

   일단 대상 부분을 통과해야 개념 자체가 성립됨.

    b/a 식에서 분모 a가 0인 경우는 개념 성립 및 연산이 불가능합니다.

   

   배수에서 0의 배수라는 개념 자체가 성립이 불가능합니다.  0*0=0이므로 왠지 0이 배수일것 같은데 0의 배수라는 개념이 없음을 유의.

   대신 분자가 0인 되는 경우는 연산이 가능하고 무수히 존재하므로 ex)   0/1, 0/2, 0/3,...

   모든 수의 배수에는 0이 포함됩니다. 즉 0은 모든 수의 배수가  됩니다.(정확히는 0을 제외한 모든 정수의 배수)

   약수 관련해서도 0의 약수는 가능합니다.   0/1, 0/2, 0/3,..이 되므로 0의 약수는 0을 제외한 모든 정수임.

   분모는 0이 될 수 없으므로 어떤수의 약수가 0이라는 되는 개념 역시 불가능합니다.

   공약수, 공배수에 관해서도 주의해야 합니다.

   0, n일때 (n은 0이 아님)
   최대공약수는 n입니다. 0의 약수는 0을 제외한 모든 정수이므로 n과 공통된 약수중에 최대값인 n이 최대공약수가 되겠죠.  
   최소공배수는 0입니다. 원래 0의 배수라는 개념은 불가능하지만 0과 n의 최소공배수에 한해 0으로 하기로 약속했습니다.

 다시 말하지만 0의 배수는 개념성립이 불가능하다는 것과

 0과 어떤수의 최소공배수는 0으로 하기로 약속을 한 것 정도는 기억합시다. 나머지는 일반적, 합리적으로 생각하면 됨.

---------------------------------------------------------------------------------------------------------------------------
베주 항등식 : 참조) http://www.mathwiki.net/index.php/베주_항등식

//////////////////////////////////////////////////////////////////////////////////
a, b가 정수(둘 중 하나는 0이 아님), d = gcd(a, b)라고 할 때(a, b의 최대공약수)
ax + by = d를 만족하는 정수 x, y가 존재한다.
또한 d는 ax + by꼴로 나타낼 수 있는 최소의 양의 정수이다.

그리고 ax + by꼴은 모두 최소의 양의 정수 d의 배수이다.
//////////////////////////////////////////////////////////////////////////////////

a, b가 0이 아닌 정수, x, y는 정수일 때
ax + by가 0이상인 경우 원소로 취하는 집합을 S라고 하자.

x=a, y=b인 경우 a^2 + b^2이고 이 값은 반드시 0보다 크므로
집합 S에서 0보다 큰 수는 반드시 존재한다.

집합 S에서 0보다 큰 수 중 최소값인 원소를 s, 집합 성립식을 만족하는 x, y을 x', y'라 하면
s = ax' + by'이다. 그리고 a, b의 최대공약수를 d = gcd(a, b)라고 하자.

1. 집합 S에서 0보다 큰 원소들 중 최소원소 s가 최대공약수 gcd(a,b)임을 증명한다.
일단 a를 최소원소 s로 표현해보자. 나눗셈 정리에 의해
a = qs + r (q는 몫, r은 나머지로 0 <= r < s)이다.
r을 좌변으로 재구성하면 r = a - qs이다. s에 ax' + by'를 넣으면
r = a - q(ax' + by') → r = a(1-qx') + b(-qy')이다.
우변은 집합의 성립식인 a○ + b○의 형태이고
좌변의 나머지 r은 0 <= r < s이므로 만약 r이 0이 아닌 경우 s보다 작은 원소가 되는데
이것은 최소원소가 s라는 것에 모순이므로 반드시 r은 0이어야 한다.
r은 0이므로 a = qs 즉 s는 a의 약수이고 기호로 표시하면 s|a가 된다.
마찬가지로 b를 최소원소 s로 표현하고 위와 동일하게 전개하면 s는 b의 약수이고 기호로 표시하면 s|b가 된다.
s는 a의 약수임과 동시에 b의 약수이기도 하므로 a, b의 공약수이다.
개념 필수적으로 공약수는 최대공약수의 약수이다. s|a, s|b → s|d

한편 a, b의 최대공약수가 d이므로 a = da', b = db'로 표현할 수 있다.
s = ax' + by'에 이를 대입하면 s = d(a'x' + b'y')가 된다.
여기서 s는 d로 나누어 떨어지므로 최대공약수 d는 s의 약수이다. d|s

위에서 s가 최대공약수의 약수(s|d)임과 동시에 최대공약수의 배수(d|s)이기도 하다.
이를 동시에 만족하려면 s = d 즉 동일해야 하므로 s는 최대공약수여야만 한다.

2. 집합 S의 모든 원소는 최소원소 s의 배수임을 증명한다.

증명 1에서 최대공약수 d가 집합 S의 양의 정수 중 최소원소 s임을 증명했다.(s = d)

그리고 ax + by 형태의 식은 필연적으로 a, b의 최대공약수 d의 배수이므로(증명 1의 하단부 참조)

모든 원소는 최소원소 s의 배수가 된다.

// 0, s, 이외의 수를 구분하여 증명시 참고
일단 ax + by = 0인 경우를 생각하면 0은 모든 정수의 배수이므로(정확히 0을 제외한 모든 정수의 배수. 0의 배수는 개념 자체가 성립 불가능)
집합 S에서 원소 0은 s의 배수라는게 개념상 성립하게 된다.
그리고 0 제외 자기자신은 항상 자기자신의 배수이므로 개념상 s는 s의 배수이다. .
이제 집합 S에서 0, s가 아닌 원소가 s의 배수임을 증명하면 된다.

증명 1에서 최대공약수 d가 집합 S의 최소원소 s임을 증명했다. 그리고 ax + by 형태의 식은

필연적으로 a, b의 최대공약수의 배수이므로(증명 1의 하단부 참조)

모든 원소는 최소원소 s의 배수가 된다.

// 참고) 아래의 증명 방식은 영문 사이트에서 찾은 것으로 특이해서 따와 봄.

// 증명 1을 먼저 하지 않고 최소원소 s가 집합의 모든 원소의 배수라는 증명을 먼저 하고 있음.
집합 S에서 0, s가 아닌 아닌 임의의 원소를 t라고 하고 집합 성립식을 만족하는 x, y를 x", y"라고 하면
t = ax" + by"가 된다. 원소 t를 나눗셈 정리에 의해 최소원소 s로 표현하면
t = qs + r (q는 몫, r은 나머지로 0 <= r < s)이다. 상하식에서 t는 같으므로
ax" + by" = qs + r가 되고 이 식의 s에 ax' + by'를 집어 넣으면
ax" + by" = q(ax' + by') + r이 된다. r을 좌변으로 식을 재구성하면
r = ax" + by" - qax' - qby' → r = a(x"- qx') + b(y" - qy')가 된다.
a(x"- qx') + b(y" - qy')은 집합의 성립식인 a○ + b○의 형태이다.
그리고 나머지 r은 0 <= r < s이므로 만약 r이 0이 아닌 경우 s보다 작은 원소가 되는데
이것은 최소원소가 s라는 것에 모순이므로 반드시 r은 0이어야 한다.
r이 0이면 t = qs이므로 집합에서 임의의 원소 t는 최소원소인 s의 배수가 된다.

-----------------------------------------------------------------------------------------------
중국인의 나머지 정리: 참조) https://ko.wikipedia.org/wiki/중국인의_나머지_정리

                                          https://namu.wiki/w/중국인의%20나머지%20정리

중국 남북조시대의 수학서인 '손자산경'에 다음과 같은 문제가 나온다.
"개수를 알지 못하는 어떤 것이 있다. 셋씩 센다면 두 개가 남고, 다섯씩 센다면 세 개가 남고, 일곱씩 센다면 두 개가 남는다. 총 몇개인가?"
今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問：物幾何？

이 문제는 x≡2(mod 3), x≡3(mod 5), x≡2(mod 7) 연립합동식의 해를 구하는 문제이다.

//////////////////////////////////////////////////////////////////////////////////////////
m1, m2, m3,..., mn이 각각의 관계가 모두 서로소이면 다음 연립 합동 방정식
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
x ≡ a3 (mod m3)
...
x ≡ an (mod mn)
은 해가 존재한다.(존재성) 이 해는 법 m1*m2*m3*...*mn에 대하여 유일하다.(유일성)

//////////////////////////////////////////////////////////////////////////////////////////

모듈러 수들 간에 모두 서로소이면 위 모든 합동식들을 모두 만족시키는 해가 반드시 존재하고,
규칙성을 띄고 무수히 존재하는데 그 해들은 mod m 합동식(m은 모듈러들의 최소공배수)으로 나타낼 수 있다.
즉 해가 최소공배수 단위로 일정하게 증감한다는 의미이다.
합동식에서는 나머지가 동일하면 하나로 취급한다. 저기서 유일성은 이런 측면에서 표현된 것이다.


증명)
1 ~ n에서 특정 인덱스를 i라고 한다.
모듈러 전체의 곱은 m이라 한다. m = m1*m2*m3*...*mn이다.
특정 인덱스의 모듈러를 mi라고 한다.
mi를 제외한 다른 모듈러들의 곱을 oi라고 한다.이 값은 전체곱에서 해당 모듈러를 나누면 되므로 oi = m/mi이다.
그리고 각각의 모듈러 수들은 모두 서로소이므로 각각 공통된 소수 부분이 전혀 없다.(겹치는 소수가 없음)
동일한 모듈러가 중복해서 포함되지 않는 이상 개별적인 곱들 역시 서로소이다.
이에 따라 최대공약수 gcd(oi, mi) = 1이다.
베주의 항등식 정리에 의해 oi*xi + mi*yi = 1을 만족하는 정수, xi, yi가 존재한다.
이것을 합동식의 형태로 변환하면 oi*xi ≡ 1(mod mi)이다.
이렇게 최대공약수가 1인 서로소 관계이면 합동식에서 곱셈의 항등원인 1을 도출하는 식으로 구성할 수 있다.
그리고 이 경우 oi, xi는 역원관계에 있다고 일컬으며 각각을 서로에 대한 역원이라고 한다.
앞에서 살펴보았듯이 이런 항등원, 역원은 암호화 알고리즘에서도 핵심요소로 사용된다.

더 참고해볼만한게 이렇게 다항식을 합동식으로 변환시 xi와 나머지 부분에만 관심을 두고 yi 부분에는 관심을 두지 않는다.
그리고 합동식은 같은 나머지를 가진 수는 하나로 표현하고 동일하게 취급하므로 ex) x = 1, 4, 7, 10,... → x≡1 (mod3)
일반 다항식에서는 무수히 많은 해를 가지지만 합동식에서는 하나의 해만 존재할 수 있다.
이 부분은 유일성 증명 부분에서 자세히 서술한다.

x = (a1*o1*x1) + (a2*o2*x2) + (a3*o3*x3) + ... + (an*on*xn) 이면 조건의 모든 합동식을 만족한다.
위 연립 합동 방정식의 해 x를 도출하는 원리는 다음과 같다.
일단 모듈러 mi에 대해 mi의 배수인 수는 mi로 나누어 떨어지므로 합동식 구성시 이 부분을 소거할 수 있다.
ex) 3 + (7*1) + (7*5) + (7*17)를 mod7 합동식으로 표현시 7의 배수 부분들은 7로 나누어 떨어지므로 간단히 3(mod 7)로 표현할 수 있다.
그리고 합동식에서 ai와 항등원 1을 곱하면 다시 ai가 된다.
베주의 항등식 변환 합동식에 의해 도출된 oi*xi는 곱셈의 항등원 1이므로 어떤 수를 곱하더라도 자신이 된다. (ai*oi*xi)(mod mi) → ai (mod mi)이다.
위 사항들을 동시에 만족시켜려고 연립 합동 방정식의 해 x가 저렇게 길게 늘어지는 형태가 된다.
조건의 합동식들을 인덱스별로 인덱스식이라 명명할 때
자신의 인덱스식에서는 항등원 곱셈식이 적용되도록 하고 다른 인덱스식에서는 해당 모듈러 mi의 배수로 만들어 소거할 수 있게 하면 된다.
그러한 노력의 결과가 x이다.

구체적으로 첫번째 식 x(mod m1)을 살펴보면 우선 a1*o1*x1을 제외한 a2*o2*x2 + a3*o3*x3 + ... + an*on*xn 부분은 각각 모두 m1의 배수이다.
oi는 mi를 제외한 모든 모듈러 수들의 곱셈이므로 o2, o3,...,on들은 모두 m1의 배수이기 때문이다.
합동식 구성시 모듈러 m1의 배수 부분은 떨굴 수 있으므로 x≡a1*o1*x1 (mod m1)가 된다.
그리고 이전에 설명했듯이 o1*x1는 곱셈의 항등원 1이므로 x≡a1*o1*x1(mod m1) → x≡a1(mod m1)이므로 해당 합동식을 만족한다.
마찬가지로 다른 합동식들에 대해서도 위와 동일한 전개를 하면 결과는 x≡ai(mod mi)이 되어 해당 식들을 만족함을 알 수 있다.
이에 따라 모든 합동식을 만족하는 x라는 해가 존재함이 증명되었다.


이제 법 m = m1*m2*m3*...*mn에 대하여 유일성을 증명하기로 한다.
우선 해가 유일한 하나라는 의미를 알아본다. 합동식은 나머지가 같은 수를 동일하게 여기고 하나로 본다.
가령 x≡1(mod3)를 만족하는 x는 ..., -5, -2, 1, 4, 7, 10, 13,...이다. 개별적인 수로 생각하면 수도 없이 많지만
합동식에선 {..., -5, -2, 1, 4, 7, 10,...} 이런 나머지가 같은 수들은 집합으로 묶어서 x≡1(mod3)이라 표현하고 하나로 본다.
mod n의 경우 이런 집합이 n개 있을 것이다. 합동식에서 해가 유일하다는 소리는 이런 집합들 중 하나만이 해가 된다는 의미이다.
가령 mod 3은 나머지가 0, 1, 2 이렇게 3개 존재하므로 저런 집합들이 3개 존재하고
x≡1(mod3)일 때만 참이면 해가 1개
x≡1(mod3)일 때도 참, x≡2(mod3)일 때도 참이면, 해가 2개라고 한다.

다음으로 두 합동식을 만족하는 해가 존재하는 경우 모듈러들의 최소공배수 연관성에 대해 생각해보자.
왠지 직관적으로 합동식들을 동시에 만족하는 해가 존재한다면 그 값이 최소공배수 단위로 증가해야 다시 해가 될 것이라는 예상이 들기는 한다.
ex) 2로 나누어 나머지 1이고 3으로 나누어도 나머지가 1이려면, 일단 쉽게 1이라는 해가 존재함을 알 수 있고
다음 해는 최소공배수 lcm(2, 3) = 6을 더한 7, 그 다음 해는 역시 6을 더한 13,... 즉 최소공배수 단위로 증가해야 함을 예측할 수 있다.
합동식으로 표현하면 x≡1(mod2), x≡1(mod3)을 동시에 충족하는 해는 x≡1(mod6)이다.

모두 서로소인 수들은 공통된 소수가 하나도 존재하지 않으므로 전체의 수들을 모두 곱해야 최소공배수가 된다.

mi들은 각각 모두 서로소이므로 이 수들의 최소공배수는 모든 mi들의 곱인 m이 된다.
m은 모듈러들의 전체곱(m = m1*m2*m3*...*mn)인 최소공배수이므로 어떤 mi에 대해서도 항상 배수가 된다.
그러므로 합동식의 해 x에 m을 더하든 빼든, 2m을 더하든 빼든, 3m을 더하든 빼든, 증감 부분은 나누어 떨어지므로 여전히 해가 될 것이다.
이런 규칙적인 해들은 mod m 합동식인 x ≡ (a1*o1*x1) + (a2*o2*x2) + (a3*o3*x3) + ... + (an*on*xn) (mod m) 으로 표현할 수 있게 된다.

그렇다면 이게 조건의 모든 합동식들을 만족시키는 유일한 해인지 증명해야만 한다.
아직 x외에 특정한 다른 해가 더 존재하는지 밝혀지지 않았기 때문이다.

다른 해 x'가 존재한다고 가정하자. 그렇다면
x≡x' (mod m1)
x≡x' (mod m2)
x≡x' (mod m3)
...
x≡x' (mod mn)
이 된다. 각 식에서 ≡ai 부분은 증명에 필요없으므로 생략한다.

합동식의 기초적 성질에 의해 (x'-x)는 m1의 배수여야 하고, m2의 배수도 되어야 하고, m3의 배수도 되어야 하고,...mn의 배수도 되어야 한다.
그러므로 (x'-x)는 위 모든 수들의 최소공배수 lcm(m1,m2,m3,...,mn)의 배수여야 한다.
이전에도 언급했듯이 각각의 mi들은 모두 서로소이므로 최소공배수는 m1,m2,m3,...,mn의 전체 수들의 곱이 된다.
이 값은 m = m1*m2*m3*...*mn이므로 결국 (x'-x)는 최소공배수 m의 배수여야 한다.
즉 다른 해 x'는 결국 기존의 해 x에서 m의 배수만큼 더하거나 뺀 값이라는 의미가 된다.
굳이 식으로 표현하자면 x' - x = mk (k는 식을 만족하는 임의의 정수) → x' = x + mk
이것은 결국 모듈러 m 합동식 구성시 같은 해라는 의미이다.
그러므로 법 m에 대하여 x ≡ (a1*o1*x1) + (a2*o2*x2) + (a3*o3*x3) + ... + (an*on*xn) (mod m) 이외에 다른 해는 존재하지 않고 유일하다.


구체적인 문제 풀이 과정) 증명과정과 붕어빵이다.
m = m1*m2*m3*...*mn ,

각각의 oi(자기자신인 mi를 제외한 다른 모듈러들의 곱)을 산출하고(m/mi로도 표현가능),
각각의 베주 항등식의 변환 합동식 oi*xi ≡ 1(mod mi)의 해 xi를 구한다.(oi의 역원)

단순한 경우 암산으로 풀 수 있고, 복잡한 경우 확장 유클리드 호제법으로 풀면 된다.
x = (a1*o1*x1) + (a2*o2*x2) + (a3*o3*x3) + ... + (an*on*xn) 식에 각각의 값들을 넣고 계산하여
최종적으로 x≡○ (mod m) 형태로 구성하면 된다.

ex) x ≡ 2(mod 3) ≡ 3(mod 5) ≡ 2(mod 7) 연립 합동 방정식의 경우.
m = 3*5*7 = 105;
o1 = 5*7 = 35;
o2 = 3*7 = 21;
o3 = 3*5 = 15;
베주 항등식의 변환 합동식으로 구성해 역원을구한다. .
35*x1 ≡ 1 (mod3) → x1 = 2;
21*x2 ≡ 1 (mod5) → x2 = 1;
15*x3 ≡ 1 (mod7) → x3 = 1;

참고로 합동식을 대입 기호 =로 받는 경우 우리가 일상생활에서 나머지라고 부르는 값 0 ~ (모듈러-1)을 취한다.

x = (2*35*2) + (3*21*1) + (2*15*1) = 233
x≡233 (mod 105)에서 233을 105로 나눈 나머지 부분만 남겨 보기좋게 표현하면
x≡23 (mod 105)이 해가 된다.