6. Basic Mathematics for Cryptography

Prime number

모든 숫자들은 prime 의 곱으로 표현될 수 있다.

10 = 2 x 5

20 = 2 x 2 x 5

60 = 2 x 2 x 3 x 5

 

모순에 의한 증명

1. 모든 숫자는 소수의 곱이다.

s 는 prime 의 곱으로 표현될 수 없는 자연수이다.

s는 소수가 아니므로 AxB 의 형태로 표현되어야 한다. (A,B 는 1과 자기 자신이 아닌 숫자)

s를 나타내기 위해 곱하는 숫자 중 가장 작은 숫자를 C라고 하자. 

이때 c는 소수가 아니다.

따라서 c도 c1 * c2 의 형태로 표현되지만, c1,c2는 {S} 에 포함되지 않는다.

왜냐하면 {s} 중 가장 작은 소수가 아닌 숫자가 C였기 때문이다. 

따라서 c1,c2는 소수의 곱으로 이루어진 숫자임을 알 수 있고, 그렇다면 c도 소수의 곱으로 이루어진 것이다.

그러므로 S는 존재하지 않는다.

 

2. 소수의 곱으로 표현되는 숫자는 항상 유일하다.

 

 

Prime Factorization

소인수분해란 자연수를 소수들의 곱으로 나타내는 것이다.

아주 큰 소수들의 곱으로 표현된 숫자는 소인수분해가 매우 어려울 것이다. 따라서 이를 RSA 에서 사용한다.

 

Relatively Prime Numbers

두 숫자 a,b 에 대해 공통점으로 포함되는 공약수가 1을 제외하고 없을 때 서로소라고 한다.

ex) 13 and 19 / 8 and 15

 

 

Greatest common Divisor (GCD)

각 숫자의 소인수분해를 비교함으로써 공통된 값들 중 가장 큰 값이 최대공약수가 된다.

 

 

Euclid's Algorithm

ex) a = 54, b = 30 이라고 하자.

gcd(54,30) = gcd(30, 54%30) = gcd(30,24)

gcd(30,24) = gcd(24, 30%24) = gcd(24,6)

gcd(24,6) = gcd(6, 24%6) = gcd(6,0)

gcd(6,0) = 6

// gcd(54,30) = 6

 

 

gcd(a,b) 는 a와 b의 linear combination 으로 표현된다.

ax + by -> a와 b의 linear comination

d는 정수 x,y 에 대하여 ax + by 로 표현할 수 있는 가장 작은 정수이다.

gcd(a,b) = d

 

 

 

Extended Euclidean Algorithm

GCD(a,b)=d 라고 할 때 ,

ax+by=d 를 만족하는 x,y 가 존재하며 이는 유클리드 호제법의 과정을 역으로 따라가면 찾을 수 있다

 

 

Modular Arithmetic

a mod n -> a 을 n으로 나누고 난 나머지

 

Congruence(합동)

b = a  (mod n),

a,b가 n으로 나눠져서 나오는 나머지 값이 같을 때다.

 

Residue

a mod n 의 결과값 b는 Residue 라고 한다.

a = qn + b 로 쓸 수 있다.

보통은 결과값 b로 음수가 아닌 가장 작은 양수가 선택된다.

ex) -12 mod 7 = -5 mod 7 = 2 mod 7 = 9 mod 7

 

 

만약 a = b (mod n) 그리고 c = d (mod n) 이라면,

a+c = b+d (mod n)

ac = bd (mod n)

a^k = b^k (mod n)

a + kn = b (mod n) 

과 같은 특징들이 성립된다.

 

 

multipllicative inverse 구하기

 

a = 13, a^i = 37 , 13*37 = 1 (mod 60)

 

 

Euler Totient Function

n = 10 일때,

Complete set of residues : 0 , 1, 2, ..., 9

Reduced set of residues : 1, 3, 7, 9 (10 과 서로소)

 

서로소 숫자 계산법 

ex ) 

φ(37) = 36, φ(11) = 10

φ(10) = (2-1) x (5-1) = 4 {1,3,7,9}

 

 

Fermat's Little Theorem

ex) a = 2, p = 7

2^6 = 1 (mod 7)

 

 

ex) 4^37 mod 7 = 4

19^45 mod 23 = 19

89^1001 mod 101 = 89

 

 

 

Euler's Theorem

ex) 25^120 mod 143 = 25^(11-1)*(13-1) mod 11*13 = 1

19^60 mod 77 = 19^(11-1)(7-1) mod 11*7 = 1

 

25^1201 mod 143 = 25^((11-1)(13-1)^10) + 1 mod 11*13 = 25

19*481 mod 77 = 19^((11-1)(7-1)^8)+1 mod 11*7 = 19

 

 

Random and Pseudo-Random Generator

- True Random number Generators

RNG 는 하드웨어에 의존해서 난수를 생성한다.

• Radioactive decay
• Thermal noise
• Polarization of photons

 

 

- Pseudo Random Number Generators (PRNGs)

다음과 같은 linear output 은 random 하게 보일지 몰라도, 예측가능하므로 안좋은 선택이다.

 

 

- Linear Complexity

linear complexity 를 측정함으로써 좋은 output stream 인지 테스트할 수 있다.

-> Berlekamp-Masseyu Algorithm

• 주어진 수열을 만들 수 있는 가장 작은 LFSR 을 찾는 알고리즘이다.
• 즉, 선형 점화식의 최소 다항식을 구하는 알고리즘이다.

- Maurer's Universal Test

• output sequence 를 압축한다.
• redundancy 가 작다면, 많이 압축되지 X

 

Cryptographically Secure Pseudo Random Number

- 'next bit' 테스트를 통과해야만 한다.

• x-bit 의 난수열이 주어져 있을 때 50%보다 큰 확률로 x+1 번째 bit 를 예측할 수 있는 다항식 알고리즘이 존재한다면 next-bit 테스트를 통과한다고 정의한다.

 

Blum-Micali Generator

p가 소수일 때, g는 primitive root modulo p 이고, x0 는 seed 이다.

이때 xi+1 로 xi 를 track back 하는 것은 어려울 것이다.

xi 가 (p-1)/2 보다 작다면 1, 그렇지 않다면 0 을 출력할 것이다.

 

primitive root modulo

정수 a 가 주어졌을 때, a^n 의 형태가 (mod n) 의 모든 나머지를 가지고 있다면, primitive root 라고 한다.

아래의 경우에는 3이 primitive root modulo 7 이다.

 

Blum, Blum and Shub (BBS)

Integer factorization 의 어려움을 이용한 유사 난수 생성기이다.

-> n = p * q (숫자가 무지하게 커진다면 소인수분해가 어려움)

예시)

즉, xn 으로 xn+1을 계산하는 것은 쉽지만, 그 역은 매우 어렵다.