본문 바로가기
카테고리 없음

RSA 공개키 비밀키 생성 과정

좋은날 2017. 6. 14. 10:20

<RSA 계산기>

https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html


http://blog.naver.com/at3650/40200115609

<모듈라 설명>

a ≡ b (mod d) => a= kd + b  => a-b = kd => a-b ≡ 0  (mod d)



두 수 a,b,c 가 모두 법 d에(mod d) 대해 합동이라 하면

 

(1) 반사성(Refiexible) :  a ≡ a  

(2) 대칭성(Symmetric) : a ≡ b  이면  b ≡ a

(3) 추이성(Transtive) :  a ≡ b 이고 b ≡ c 이면 a≡c

가 성립한다. (1),(2),(3)이 모두 성립하므로 합동식은 동치관계라고 볼 수 있다.


두 수 a,b,c 가 모두 법 d에(mod d) 대해 합동이라 하면

(1)   a ≡ b ,  a` ≡ b` 이면  a+a`  ≡ b+b`

(2)  a ≡ b ,  a` ≡ b` 이면  a-a`  ≡ b-b`

(3) a ≡ b ,  a` ≡ b` 이면   aa`  ≡ bb`


<예시>

2457 = 2 × 10³ + 4 × 10² + 5 ×10 + 7×1

≡ 2×1 + 4×1 + 5×1 + 7× 1   (mod 9)


2 × 10³ 의 경우

1) 2 ≡ 2  (mod 9) ; (∵ reflexible),  

2) 10³  ≡ 1 (mod 9)

⇒ 2×10³ (mod 9) ≡ 2(mod 9) × 1 (mod 9) = 2 (mod 9) (∵  a ≡ b ,  a` ≡ b` 이면   aa`  ≡ bb`

 

<오일러 파이>

φ(n) - 오일러 파이, 특정 자연수와 서로수인 자연수의 갯수

φ(10) = 4 (1,3,5,7)

φ(p) = p-1 (p가 소수일때)


<오일러 파이 구하기>

기본원리 : 전체에서 소인수들의 배수인 수들을 제외하면 됨

=> 1 - n(AUBUC)


φ(30) 구하기 예시

30의 소인수는 2, 3, 5

A=1, B=1/2, C=1/3, D=1/5 라 하면

P(X) = A³ - AB - AC - AD + BC + BD + CD - BCD

P(X) =  A³ - A²B - A²C - A²D + ABC + ABD + ACD - BCD 

P(X) = A³ - (B+C+D)A² + (BC+CD+BD)A - BCD

P(X) = (A-B)(A-C)(A-D) 

따라서 30이 가진 서로수는 8개


앞에서 살펴본 φ(n)를 정규한 수식으로 표현해보면 아래와 같이 표현할수 있음


1000의 오일러 파이 값 구하기 적용

1000 = 2^3 * 5^3 => 1000(1-1/2)(1-1/5) = 400


<페르마의 소정리>

* 기초 원리

 

* 가정

  (어떤 임의의 두 수를 골라도 법 p와 합동이 되지 않는다)


m의 변수들은 모두 나머지가 다르기 때문에 모두를 곱한 값의 (mod p)를 적용해보면

(p-1)! (mod p)가 된다. 따라서 아래식이 성립한다

(p-1)!중에서 p로 나누어지는 수는 없으므로 아래 식은 성립한다

(p가 정수 a를 나누지 않는 소수인 경우)



<페르마의 일반화된 소정리>

 이고   이므로

 (a와 n이 서로 소인경우)


<유클리드 호제법 원리>

A >= B인 어떤 두 정수 A와 B가 있을 때(A = Bq + r로 나타낼 수 있다.)

A와 B의 최대공약수 gcd(A, B) = d는 gcd(B, r)과 같다.

즉, 쉽게 말하면 두 수의 최대공약수는 "큰 수를 작은 수로 나눈 나머지"와 "작은 수"의 최대공약수와 같다는 것이다.


증명.

gcd(A, B) = d에 의해서 A = ad, B = bd (따라서 a와 b는 서로소이다.)

A = Bq + r 이므로 r = A - Bq = ad - bdq = (a-bq)*d 이다.


여기서 B = bd 와 r = (a-bq)d이므로 d는 B와 r의 공약수 중 하나라는 것을 알 수 있다.

B와 r의 최대공약수를 c라 하면 c >= d 라 할 수 있다.


B = cs, r = ct라 하면 (s, t도 서로소)

A = Bq + r = csq + ct = (sq+t)c 이다.

c는 A와 B의 공약 수 중 하나라는 것을 알 수 있다.

따라서 c는 A와 B의 최대 공약수인 d의 약수이고 d >= c 임을 알 수 있다.


따라서 c >= d 이고 d >= c 이므로 d = c 라는 결론을 얻게 된다.

즉 gcd(A, B) = gcd(B, r)이다.


<유클리드 호제법 예시>

A = Bq + r  => gcd(A, B) = gcd(B, r)

GCD(270,192) = GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6


알고리즘

A와 B의 최대공약수 GCD(A,B)를 알아내는 유클리드 호제법은 다음과 같습니다:
  • A=0이면 GCD(0,B)=B이므로 GCD(A,B)=B이고 멈춥니다. 
  • B=0이면 GCD(A,0)=A이므로 GCD(A,B)=A이고 멈춥니다. 
  • A를 A = B⋅Q + R의 형식으로 씁니다
  • GCD(A,B) = GCD(B,R)이므로 유클리드 호제법을 이용하여 GCD(B,R)을 찾습니다.

예제:

270과 192의 최대공약수를 찾아 봅시다
  • A=270, B=192
  • A ≠0
  • B ≠0
  • 긴 나눗셈을 이용하면 270/192=1 나머지 78입니다. 이를 다음과 같이 바꿔 쓸 수 있습니다: 270 = 192 * 1 +78
  • GCD(270,192)=GCD(192,78)이므로 GCD(192,78)를 찾습니다
A=192, B=78
  • A ≠0
  • B ≠0
  • 긴 나눗셈을 이용하면 192/78 = 2 나머지 36입니다. 이를 다음과 같이 바꿔 쓸 수 있습니다:
  • 192 = 78 * 2 + 36
  • GCD(192,78)=GCD(78,36) 이므로 GCD(78,36)을 찾습니다
A=78, B=36
  • A ≠0
  • B ≠0
  • 긴 나눗셈을 이용하면 78/36 = 2 나머지 6입니다. 이를 다음과 같이 바꿔 쓸 수 있습니다:
  • 78 = 36 * 2 + 6
  • GCD(78,36)=GCD(36,6)이므로 GCD(36,6)을 찾습니다
A=36, B=6
  • A ≠0
  • B ≠0
  • 긴 나눗셈을 이용하면 36/6 나머지 0입니다. 이를 다음과 같이 바꿔 쓸 수 있습니다:
  • 36 = 6 * 6 + 0
  • GCD(36,6)=GCD(6,0) 이므로 GCD(6,0)을 찾습니다
A=6, B=0
  • A ≠0
  • B =0, GCD(6,0)=6
이제까지의 과정을 정리하면 다음과 같습니다:
GCD(270,192) = GCD(192,78) = GCD(78,36) = GCD(36,6) = GCD(6,0) = 6
GCD(270,192) = 6


<RSA 공개키 및 비밀키 생성 원리>

온라인으로 검증해보기 : http://rsatools.wforums.net/#encrypt

  • 뽀로로와 패티가 비밀연애를 위해 암호화된 연애편지를 주고 받으려 한다면...
  • 뽀로로는 서로 다른 두 소수 (P, Q)를 선택한다.
  • P와 Q를 곱해 N 을 구한다.  (N=PxQ)
  • 오일러 피 함수에 해당되는 φ(N) = (P-1)(Q-1)을 구한다.
  • φ(N) 보다는 작으면서 φ(N)와 서로소인 정수 e를 찾는다.  (1 < e < φ(N)) 
  • 확장된 유클리드 호제법을 이용해 (d x e)/φ(N) 일 때 나머지가 1인 정수 d 를 구한다. 
  • 처음에 선택한 두 소수 (P, Q) 및 φ(N)는 유출되면 안되므로 삭제한다.
  • 패티도 동일한 과정을 거친다.


<RSA 공개키 및 비밀키 생성 예제>

p=13, q=17 지정

φ(N) = 12 * 16 = 192

공개키는 e 는 5로 지정

비밀키는 아래 식으로 유도

5d = 192k +1

k를 2라고 하면 d는 77이 된다

공개키 (221, 5), 비밀키 (221,77)


<확장된 유클리드 호제법>

GCD(A,B) = c 인경우 => pA+qB = c 식을 구할 수 있음


e가 정해진 경우 d를 구하기 위해 사용

GCD(φ(N),e) => pφ(N)+qe = 1 로 표현가능  ( φ(N), e는 서로소 이므로 c는 1)

pφ(N)+qe = 1 에서 pφ(N)는 φ(N)의 배수 이므로

qe (mod φ(N)) ≡ 1  이어야 한다.

따라서 q값이 우리가 구하는 d값이 된다


<확장된 유클리드 호제법 예시>

p=13, q=17, φ(N)=192, e=5 인경우 d를 구하면

GCD(192,5) => 192 = 5 * 38 +2   => 2 = 192 - 5*38

= GCD(5,2) => 5 = 2 * 2 + 1       

이를 φ(N)=192, e=5 각각 배수의 합 형태로 만들어야 하므로

1 = 5 - 2 * 2

1 = 5 - 2 * (192 - 5*38) = 5 * 77 - 2 * 192

따라서 d는 77이 된다


<암복호화 원리>

c = me mod n

m = cd mod n


cd mod n ≡ med mod n 

 


1) m,n 이 서로소 인경우

페르마의 정리에 따라


2) m,n이 서로소가 아닌경우

φ(n) = (p-1)(q-1) 

이므로

 이 p,q 각각으로 나누었을때 m이 나머지로 남게 된다. 따라서

에서 m을 뺀값은 p,q로 모두 나누어 지며 이는 p*q = n 으로 나누어진다.

따라서 아래와 같이 m 값을 추출되게 된다.


<암복호화 과정 예시>

공개키 (221, 5), 비밀키 (221,77)

* 암호화

c = me mod n

* J(10진수 74)를 암호화 해보자

74^5 mod 221= 211 


* 복호화

공개키 (221, 5), 비밀키 (221,77)

m = cd mod n

211^77 mod 221 = 74


저작자표시 비영리 변경금지

티스토리툴바