수학

RSA 암호화 - RSA의 작동 원리

RSA 암호화 RSA 암호화 - 개념편 RSA 암호화 - 수학편: RSA와 소수 RSA 암호화 - 수학편: 나머지 계산 RSA 암호화 - RSA의 동작 방식 RSA 암호화 - RSA의 작동 원리 [알림] 이 글은 RSA 암호화 시리즈의 5편입니다. 앞선 편을 모두 읽고 이 편을 읽는 것을 추천합니다! 오일러 정리 RSA 암호화에서는 페르마 소정리가 일반화된 정리 격인 오일러 정리가 핵심 역할을 한다. 오일러 정리 서로소인 두 정수 $a$와 $n$에 대해 $a^{\phi (n)} \equiv 1\:(\mathrm{mod}\:n)$이다. 여기서 $\phi(n)$은 오일러 피 함수로 $n$ 미만의 자연수 중 $n$과 서로소인 수의 개수를 말한다. 오일러 피 함수는 자기 자신보다 작은 자연수 중 자신과 서로소인..

RSA 암호화 - RSA의 동작 방식

RSA 암호화 RSA 암호화 - 개념편 RSA 암호화 - 수학편: RSA와 소수 RSA 암호화 - 수학편: 나머지 계산 RSA 암호화 - RSA의 동작 방식 RSA 암호화 - RSA의 작동 원리 [알림] 이 글은 RSA 암호화 시리즈의 4편입니다. 앞선 편을 모두 읽고 이 편을 읽는 것을 추천합니다! RSA의 작동 방식 RSA는 다음 방식으로 작동한다. 키 쌍 생성: 아주 큰 두 소수 $p$, $q$를 생성한다. $N=pq$를 계산한다. $(p-1)(q-1)$과 서로소인 정수 $e$를 하나 정한다. $ed$를 $(p-1)(q-1)$로 나눈 나머지가 1인 정수 $d$를 계산한다. $p$와 $q$, $p-1$, $q-1$은 삭제한다. 공개키는 $N$과 $e$가 되고 비밀키는 $d$가 된다. 3단계에서 $e$..

RSA 암호화 - 수학편: 나머지 계산

RSA 암호화 RSA 암호화 - 개념편 RSA 암호화 - 수학편: RSA와 소수 RSA 암호화 - 수학편: 나머지 계산 RSA 암호화 - RSA의 동작 방식 RSA 암호화 - RSA의 작동 원리 [알림] 이 글은 RSA 암호화 시리즈의 3편입니다. 앞선 편을 모두 읽고 이 편을 읽는 것을 추천합니다! 특수한 형태의 나머지 연산의 필요성 RSA암호는 나머지 연산을 매우 자주 활용한다. 어떤 정수를 다른 정수로 나누었을 때의 나머지를 구하는 것이다. 컴퓨터 입장에서 나머지 연산은 매우 쉬운 일이다. C언어에서 $a$를 $b$로 나눈 나머지를 계산해서 $c$에 저장하는 코드는 다음 한 줄이면 된다. c=a%b; 이 방법은 매우 효과적이지만 RSA에 사용하기에는 적절하지 못하다. RSA에는 $a^b \equiv..

RSA 암호화 - 수학편: RSA와 소수

RSA 암호화 RSA 암호화 - 개념편 RSA 암호화 - 수학편: RSA와 소수 RSA 암호화 - 수학편: 나머지 계산 RSA 암호화 - RSA의 동작 방식 RSA 암호화 - RSA의 작동 원리 [알림] 이 글은 RSA 암호화 시리즈의 2편입니다. 앞선 편을 모두 읽고 이 편을 읽는 것을 추천합니다! 비대칭키 암호화의 기본 비대칭키 암호화는 비밀키로 공개키를 알 수는 있지만 공개키로는 비밀키를 알 수 없고, 두 키가 암복호화에 따로따로 사용돼야 하는 한 쌍의 키가 필요하다. 이는 보통 이산대수의 어려움을 통하여 구현된다. 이번 글에서 다룰 RSA는 소인수분해의 난해함을 기초로 보안이 유지된다. 두 소수 $p$와 $q$가 있다. 이 두 수를 곱하여 $pq$를 계산 하는 일은 누구나 쉽게 할 수 있으며 컴퓨..

원주율의 근사방법

원주율이란, 원에서 지름과 반지름의 길이비로 정의된다. 모든 원에서 이 값은 일정하며, 따라서 상수이다. 원주율이 무리수라는 증명은 이미 존재하는데, 이는 곧 원주율은 원을 하나 그리고, 원주와 반지름의 길이를 실측해서 나타낼 수 없음을 의미한다. 따라서 여타 다른 무리수, 이를테면 $\sqrt{2}$와 같이 $\pi$도 근사를 통해 그 값을 구해야 한다. #include #include #include #include #define BATCH 999999 #define WILL_TRY 1400000 #define SQUARE 14000 #define RND(M) rand()%M #define DOUBLE_SIZE sizeof(double) clock_t start_p, end_p; void approx..

유클리드 호제법과 디오판토스 방정식

일반적으로 두 자연수의 최대공약수를 구하기 위해 우리는 두 수를 소인수 분해한다. 예를 들어 두 자연수 $a$와 $b$가 있고 이들을 소인수 분해한 것이 $a=pq^2$이고 $b=p^2q$인 경우 두 수의 최대공약수 $g=pq$이다. 이때 $g=(a,b)=pq$로 쓸 수 있다. 이 방법은 분명 효과적이지만 두 수가 매우 큰 경우 그리 효과적인 방법은 아니다. 이 글에서는 두 수의 최대공약수를 구하는 다른 방법인 유클리드 호제법에 대해 다룬다. 유클리드 호제법 유클리드 호제법은 다음과 같은 정리이다. 두 자연수 $a$와 $b$가 있을 때 $a=bq+r$ ($q,r \in \mathbb{Z}$)라면 $(a,b)=(b,r)$이다. 이에 대한 증명은 다음과 같다. $(a,b)=G$라고 하고 $a=GA$, $b=..

일정한 차이가 나는 소수

이 글에서는 일정한 차이가 나는 소수들에 대해 탐구하여 본다. 조금 더 자세히는 다음 성질을 증명한다. 소수 $p$와 자연수 $d$에 대해 $p$, $p+d$, $p+2d$, $\cdots$, $p+(n-1)d$가 모두 소수일 때 $d$는 $n$보다 작은 모든 소수들로 나누어 떨어진다. 증명의 방법 위의 명제를 귀류법으로 증명할 것이다. 즉, $q$가 $n$보다 작은 어떤 소수일 때, $d$가 $q$로 나누어 떨어지지 않는다고 가정해보자. 완전잉여계 증명 증명은 우선 $p$, $p+d$, $p+2d$ $\cdots$ $p+(q-1)d$가 $q$에 대한 완전잉여계임을 보임으로 시작한다. 이는 귀류법으로 증명할 수 있다. 만일 위의 소수들이 $q$에 대해 완전잉여계가 아니라면 $0 \leq i < j \le..

분할과 분배 Pt. 2

이전글 이전글에 이어서 이번 글에서는 나머지 2가지 경우에서 공을 상자에 나눠담는 경우를 생각해 볼 것이다. 이전글에서 이어지는 내용도 일부 있으니 파트 1을 먼저 읽고 오는 것을 추천한다. 이 글에서는 상자를 구분할 수 없는 경우에 대해 알아본다. 공을 구분할 수 없고 상자를 구분할 수 없는 경우 $n$개의 같은 공을 $k$개의 같은 상자에 빈상자를 허용하지 않으며 넣는다고 하자. $i$번째 상자에 들어가는 공의 개수를 $n_i$라고 하면 다음과 같은 식이 성립할 것이다. $n_1+n_2+\cdots+n_k=n$, 여기서 $(n_i \geq 1)$, $(i=1, 2, 3, \cdots, k)$ 즉, $n$을 $k$개의 자연수의 합으로 나타내는 경우의 수와 같으며 이를 $p(n,\:k)$라고 한다. 여기..