cryptography
Author: seyon
Date: 2002-09-26 오후 2:30:19 from '211.38.3.65' of '211.38.3.65'
1. Letters as Numbers
모든 data를 숫자로 표현할수있다
2. Why Math?
symetric key cryptography는 swap, rotate, excluesive-or등의 연산으로 수학이 아니어도 가능하나
public key cryptography는 현재 수학만이 가능하다.
-Metaphor
circular train track와 같다. 이 트랙만을 돌수 있고, reverse는 안된다.
3. Some background
-Inverse
5 * 2 = 10
10 / 2 = 5
5 * 2 = 10
10 * 1/2 = 5
-Other Inverse
6th st. walk west one block -> 7th st.
7th st. walk east one block -> 6th st.
-Cryptographic Inverse
symetric -> inverse function, public key -> inverse number (inverse key)
어떻게 inverse number를 얻는가? prime number와 modular 연산
-Prime Numbers
relatively prime
38(1, 2, 19), 55(1, 5, 11)처럼 둘다 prime이 아니고 1만 공통적일때
-Modular Math
나눠서 나머지를 얻음
7^8 mod 11 = 524,702 나머지 9
-Some Exponential Identities
X^a * X^b = X^(a+b)
(X^a)^b = X^(a*b)
-RSA
m^(p-1) mod p = 1 ( m은 p보다 작은 양수) Fermat
m^(p-1)(q-1) mod n = 1 (n = p * q 이고, p, q는 prime) Euler
m^((p-1)(p-1)+1) mod n = m ( X^a * X^b = X^(a+b)에서)
-Two Trips
e * d = [ (p-1) * (q-1) ] + 1
이 되는 두 수 e, d를 찾는다.
Alice 는 e만큼 여행하고 Bob은 Alice가 놓은것을 줏어서 d만큼 여행한다.
Alice m^e mod n => c
Bob c^d mod n => m
Alice는 m부터 시작하고 e거리만큼 여행한다. 즉 m^e이다. 그녀가 끝난곳이 어디인가? c라부르는 어딘
가에서 끝난다. (ciphertext) . Bob은 Alice가 내려놓은지점 c에서 시작하고 d거리만큼 여행한다
즉 c^d 이다.
우리는 bob이 alice가 시작한곳 m에서 끝났다는 것을 알고 있다.
c = m^e mod n에서
bob은 결국 (m^e)^d mod n만큼 여행했다. 이것은 즉 m^(e*d) mod n이다.
그런데 e * d가 [(p-1)*(p-1)] + 1 이므로 Bob은 결국 m^((p-1)(q-1)+1) mod n이 되고 이는 m
이 된다.
Bob이 계산할때 실제로 c를 m^e로 치환하지는 않는다. 그는 c를 수행할 뿐이다.
그러나 수학적으로 말하면 c를 수행하는 것은 m^e를 수행하는것과 같다. 왜냐하면 두개가
같기 때문이다.
예 p = 5, q = 11, n = 55 이면
[ (p-1) * (q-1)] + 1 = 41
e * d = 41 인데 41은 prime이므로 이를 만족하는 e, d는 없지만 41은 1 mod 40 과 같다
실세계에서는 e를 먼저 찍고 이로부터 d를 구한다. e는 대부분 3을 사용한다.
3 * d = 1 mod 40 (Extended Euclidian algorithm)
3 * 27 = 81 =
81 / 40 = 2 나머지 1
즉 81 - ( 2* 40)
3 * 27 = 1 mod 40
여기서 잠시 생각해보면 지금 55의 modulus에 대해서 생각하고 있는데 갑자기 40에 대한 modulus
얘기가 나온다. 어느것인가? 이것은 RSA 알고리즘의 trick이다. key생성을 위해서 하나의 modulus
를 쓰고 encrypt를 위해서 또하나의 modulus를 쓴다. encrypt와 decrypt를 위한 modulus는 p*q이다
key pair를 결정하는 modulus는 (p-1)*(p-1)이다.
다음과 같이 생각하라
step 1: 두 소수 p, q를 찾는다.
step 2: Combine those two prime numbers by multiplying, n = pq
step 3: Combine those two prime numbers another way, pi = (p-1)(q-1)
step 4: pi를 사용하여 key pair e, d를 생성
step 5: e, d, n을 사용하여 encrypt, decrypt
참고로 inverse에 대한 얘기를 기억하여 inverse number를 생각하면 우리는 숫자 3을 기억한다
이의 inverse는 27이다. 어떻게 3의 inverse가 27이 되는가는 3 * 27 mod 40 = 1이므로..
각 operation은 자신의 특수한 inverse number에 대한 개념을 가지고 있다. 곱셈에서는
one over the number가 inverse number이고 "walk west"를 가지고 보면 는 지구 둘레의 나머지
어떤 거리 만큼이다. 우리는 'modular multiplication inverse'를 얻었다.
예를 들어 글자 's'를 encrypt해보자. 우리는 이를 숫자로 변환하고 encrypt number로 변환한다
19번째 알파벳이므로 19로 바꾸자. 19를 encrypt하기위해서 19^3 mod 55를 계산기로 계산하면
39가 나온다. 이것이 ciphertext이다.
decrypt하기위해서는 39^27를 계산해야 하는데 계산기가 이렇게 큰 수를 지원하지 않을수 있으므로
X^a * X^b = X^(a+b)를 이용한다.
39^1 = 39 = 39 = 39 mod 55
39^2 = 39 * 39 = 1521 = 36 mod 55
39^4 = 39^2 * 39^2 => 36 * 36 = 1296 = 31 mod 55
이런식으로 계산하면
39^27 mod 55 = (39^16 * 39^8 * 39^2 * 19) mod 55
= (16 * 26 * 36 * 39) mod 55
= 19
우리는 39에서 시작해서 27거리만큼 여행하면 19에서 끝난다. 이것이 오리지널 메세지이다.
RSA 알고리즘
1. 두 소수 p, q를 찾는다.
2. 이둘을 곱해서 n이라한다.
3. relatively prime (p-1)과 (q-1)의 public exponent를 선택한다. e라 부르는.
4. e*d= 1 mod (p-1)*(q-1) 이 되는 d를 찾는다.
5. n, e를 public하게 d(와 p와 q)를 secret하게 만든다.
6. message m을 encrypt하기위해서 ciphertext c=m^e mod n
7. decrypt하기위해서 m = c^d mod n
2개의 moduli가 포함된다는것을 기억하라. d (private key)를 발견하면 (p-1)*(q-1)의 modulus를
사용한다. encrypted할때, p * q의 modulus를 사용한다. 수학의 기발함으로 생각된다. moduli를
mixing함으로인하여 algorithm은 secure하게 된다.
-Security
1024bit(308 decimal digit)
한번에 한글자가 아니라 modulus가 매우 크기때문에 한꺼번에 encrypt함. 8bit letter를 사용하므로
128자까지 한번에 encrypt할수 있다.
big prime은 어떻게 구하는가? Fermat test를 통해서 어렵지 않게 구할수 있다.
-One Last Question
지금까지 inverse number만 가지고 얘기했는데 RSA의 inverse function이 있는가?
있다. 그러나 매우시간이 걸린다. 나에게는 쉽고 너에게는 어렵다.
-Finding Primes
1. Find a random number
2. Perform the Fermat test
1. Find a random number
2. Make sure it's odd, since all primes (other than 2) are odd.
3. Perform the Fermat test
4. If it passes, great; you'v probably got a prime. Exit. If not, continue on to step 5.
5. Add 2 to the current candidate (you now have the next odd number) and return to step 3
1. Find a random number
2. Make sure it's odd, since all primes (other than 2) are odd
3. Divide by known primes
a. Divide by 3.
4. Perform the Fermat test
5. If it passes, great; you've probably got a prime. Exit. If not, continue on to step 6.
6. Add 2 to the current candidate and return to step 3
| |
