[현대암호학] 제 9장 - 비대칭 키 암호수학 (1)

(2021.11.05)
이번에 정리할 부분 목차

9.1 소수
 9.1.1 정의
 9.1.2 소수 집합의 크기
 9.1.3 소수 판정
 9.1.4 오일러의 φ 함수
 9.1.5 페르마의 리틀 정리
 9.1.6 오일러 정리
 9.1.7 소수 생성

9.2 소수 판정
 9.2.1 결정적 알고리즘
 9.2.2 확률적 알고리즘
 9.2.3 추천하는 소수 검증

9.3 소인수분해
 9.3.1 산술 기본 정리
 9.3.2 소인수 분해 방법
 9.3.3 페르마 방법
 9.3.4 pollard p-1 방법
 9.3.5 Pollard rho 방법
 9.3.6 더 효율적인 방법

 

 

9.1 소수

 

9.1.1 소수의 정의

 

소수: 1과 자기자신만을 약수로 가지는 수

합성수: 소수가 아닌 수 --> 3개 이상의 약수를 가짐

1은 소수가 아니다 --> 가장 작은 소수는 2이다

 

 

 

양의 정수 a,b 에 대해서 gcd(a,b)=1 이라면, a,b는 서로소이다.

p가 소수라면, 1부터 p-1까지 모든 정수는 p와 서로소이다.

암호는 모듈러 p가 소수인 Zp와 Zp* 를 사용한다.

(Zp는 덧셈에 대한 역원, Zp*은 곱셈에 대한 역원)

 

 

 

 

 

9.1.2 소수 집합의 크기

 

소수는 무한개이다.(infinite)

소수의 개수가 유한개라고 가정하면, 가장 큰 소수가 있을 것이다. 
가장 큰소수를 p라고 하고, 유한 개의 소수를 모두 곱한 수를 P=2 x 3 x ... x p 라고 둘 수 있다.

그러면, P+1 은 p보다 작은 q 를 약수로 가지지 못한다.
proof: q는 p보다 작은 소수이고, P의 약수라고 둔다. (P+1)-(P)=1 인데, (P+1)의 약수가 q라고 하면, (P+1)-P 는 q로 나누어 떨어진다. 그러나 (P+1)-P=1 인데 1을 나누어떨어지게 하는 수는 1밖에 없다. 그렇게 되면 q는 1이 된다는 말인데 q는 p보다 작은 소수라고 정의했기 때문에 모순이 된다.
따라서, P+1은 소수가 된다. 
결국, 가장 큰 소수 P는 존재할 수 없기 때문에 소수의 개수는 무한개이다.

 

 

π(n): n보다 작거나 같은 소수의 개수

[n/(ln n)] < π(n) < [n/(ln n-1.08366)]

 

 

 

 

 

9.1.3 소수 판정

 

n이 소수인지 판정하는 방법

: 루트 n보다 작은 소수에 대해서 나누어 떨어지지 않으면, 소수이다.

 

 

에라토스테네스의 체

출처: 교수님 강의노트

 

 

 

9.1.4 오일러의 φ함수 (Euler's phi-function)

 

 

 

 

 

 

9.1.5 페르마의 리틀 정리

 

 

 

 

 

9.1.6 오일러 정리

 

 

 

9.1.7 소수 생성

 

수학자 메르센과 페르마는 소수를 생성할 수 있는 공식을 개발했다.

 

 

 

 

 

 

 

9.2 소수 판정

• 결정적 알고리즘: 나눔 알고리즘, AKS 알고리즘
• 확률적 알고리즘: 페르마 소수 검증, 제곱근 소수 검증, 밀러-라빈 소수 검증

 

 

9.2.1 결정적 알고리즘

 

하나의 수를 입력받아서 그 수가 소수인지 합성수인지를 분명하게 알려준다.

 

• 나눔 알고리즘(divisibility test)

 

 

출처: 교수님 강의노트

 

 

• AES 알고리즘

 

 

 

9.2.2 확률적 알고리즘

 

AKS 알고리즘이 정식으로 표준이 될 때까지 실제로 사용했다.

확률적 알고리즘으로 판정한 소수는 반드시 소수라는 보장은 없다.

합성수인데 소수라고 판정할 확률이 ε일 때, 알고리즘을 n번 반복하면 소수라고 판정할 확률이 0으로 줄어든다.

 

 

• 페르마 소수 검증(Fermat primality test)

 

 

• 제곱근 소수 검증(square root primality test)

 

 

• 밀러-라빈 소수 검증(Miller-Rabin primality test)

 

출처: 교수님 강의노트

 

 

 

9.2.3 추천하는 소수 검증

 

나눔 알고리즘과 밀러-라빈 검증을 조합한다.

 

출처: 암호학과 네트워크 보안 교재 286p

 

 

 

 

 

 

 

9.3 소인수분해

 

9.3.1 산술 기본 정리(Fundamental Rheorem of Arithmetic)

 

 

 

 

9.3.2 소인수분해 방법

 

전수 나눔 소인수분해 방법은 가장 간단하면서, 효울이 떨어지는 알고리즘이다.

n에 대해서 루트 n보다 작은 수에 대해서 하나씩 나눠보는 방법이다.

 

 

 

 

 

9.3.3 페르마 방법

 

 

 

 

 

9.3.4 Pollard p-1 방법

 

 

 

 

9.3.5 Pollard rho 방법

(어려움 살짝 이해 안감)