Contents

Algorithm
2013.04.23 12:41

[security] RSA 암호화 설명과 예..

조회 수 16987 댓글 0
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
?

단축키

Prev이전 문서

Next다음 문서

크게 작게 위로 아래로 댓글로 가기 인쇄
암호화와 복호화에 앞서 거쳐야 할 기본적인 과정임~

1) 적당히 비슷하고 큰 소수 p, q를 구함
2) 공개키 n을 생성 (n=pq)
3) φ를 구함 φ = (p-1)(q-1)
4) gcd(s,φ)=1을 만족하는 즉 서로 소인 또다른 공개키 s를 생성합니다. 1< s < φ
5) 유클리드 알고리듬을 이용하여 비밀키 d를 만듦 d = s^-1 (mod φ) (sd≡1 (mod φ) 를 구하는 것. 무엇을 선택하든 상관없음) 를 구하는 것 1< d < φ

※ 확장된 유클리드 알고리듬으로 정수 d를 구하는 법
t_0 = 0
t_1 = 1
t_j = t_(j-2)-q_(j-1)t_(j-1) mod r_0 (단, j≥2)

위 방법을 이용하여 d를 구한다.


암호화) n보다 작은 수로 메세지 M을 정한 다음,암호문 c = M^s (mod n) 을 계산하여 암호문 c를 보낸다.
복호화) M = c^d (mod n)을 사용해 복호한다.

예를 들어..
1) 소수 5와 7을 골랐다면..
2) 공개키 n=35를 만들게 됨.
3) φ=24를 구함.
4) 24와 서로소인 11=s를 구함.
5) 현재 공개키 (n,s) = (35,11)을 구함.
6) 비밀키 d를 구함.

d = 11^-1 (mod 24)
확장된 유클리드 알고리듬의 적용.

11^-1 (mod 24) --- 주어진 식

24 = 2*11+2(=r1)
--- 24(=n)를 앞의 11(=s)로 나누어 몫과 나머지 형태로 나타낸 것. n = q(=몫)*s+r1(=나머지1)

(t_2)0-2*1 (mod 24) = -2 (mod 24) = 22(=r2) (mod 24)
--- t_(2-2)=0이므로 0-2(=q)*1(t_(2-1)=1) (mod 24) = -2 (mod 24) = 24-2 (mod 24) = 22 (mod 24)

11 = 5(=q2)*2(r1)+1(r3) 
---s를 앞에서 나온 나머지 r1으로 나눈 것입니다. 검산식 형태. (현재 여기서는 나머지가 1이 나왔기 때문에 유클리드 알고리듬은 끝이 난 것입니다.)

(t_3)1-22*5 (mod 24) = -109 (mod 24) = 11 (mod 24)
--- 1(=t_(3-2)) - 22(r2)*5(q2) (mod 24) = -109 (mod 24) = 24*5-109 (mod 24)=11(mod 24)

따라서 d = 11.
암호화) 메세지 3을 암호화 해본다. 암호문 c = 3^11 (mod 35) = 12
복호화) 암호문 12를 복호화 해본다. 메세지 M = 12^11 (mod 35) = 3.

복호화가 제대로 되었다.
중요 포인트는 확장된 유클리드 알고리듬을 적용할 때, 나머지가 1이 나올 때까지 계속 반복해야 한다는 점이다.
(여기서 φ는 φ(n)을 뜻하는 오일러 함수 값) 

RSA는 공개키라고 해서 서버가 암호를 가지고 있다가 클라이언트가 접속을 하면 그 암호를 보내줌.
그럼 서버와 클라이언트가 그 암호를 이용해 서로서로 확인을 함.

공개키와 수신자의 개인키가 암호화/복호화 과정에서 이러한 공식을 사용하기 때문에 클라이언트 단에서 End User가 알기는 힘듦.
수신자가 암호화 알고리즘을 알 필요도 없고 알수도 없고, 수신자의 개인키가 복호화를 하기 때문..


?

List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
923 Develop [asem] CMOS 패스워드 알아내기.. 소스.. file hooni 2003.04.23 8883
922 Develop [c++] namespace 사용 예 hooni 2003.04.23 8844
921 Develop [c++] template 사용예 hooni 2003.04.23 7295
920 System/OS [web] 웹서비스 취약점 자료.. (논문첨부) file hooni 2003.04.23 18316
919 System/OS [linux] 꿀통(honeyd) 설치하기.. 메뉴얼 과정 6 file hooni 2006.04.23 20528
918 System/OS [linux] 데비안(debian.org) 리눅스 명령어 예제 hooni 2006.04.23 10706
917 System/OS [mysql] 시간 관련 SQL구문.. hooni 2013.04.23 11103
916 Database [mysql] 쿼리 로그 저장 매뉴얼 file hooni 2013.04.23 15679
» Algorithm [security] RSA 암호화 설명과 예.. hooni 2013.04.23 16987
914 Algorithm 스터디 자료, 암호화에 대해서.. 나중에 볼 ppt.. file hooni 2013.04.23 13801
913 Develop [c] 최대공약수, 최소공배수, 서로소 구하기 (펌) hooni 2013.04.23 11279
912 Develop [c++] RSA Sample 4 CPP hooni 2013.04.23 9392
Board Pagination Prev 1 ... 17 18 19 20 21 22 23 24 25 26 ... 98 Next
/ 98