암호학과 정수론

목차

1. 암호학
(1) 고전 암호학
(2) 현대 암호학

2. 공개키 암호
(1) 공개키 알고리즘과 비밀키 알고리즘
(2) 공개키 알고리즘의 특징
(3) 공개키 암호 알고리즘의 시스템 구성

3. RSA 공개키 암호
(1) RSA(Rivest Shamir Adleman)란?
(2) RSA 공개키 암호에 사용되는 정수론
(3) RSA 암호시스템에서의 각 사용자를 위한 키 쌍 생성 절차
(4) RSA 암호의 시스템 설정 및 암복호화 과정
(5) RSA 암호의 안전성

4. RSA를 응용한 암호
(1) Rabin 공개키 암호
(2) Diffie-Hellman 키배송
(3) ElGamal암호

5. Reference

본문내용

를 정한다. (
F`
,
E(F)
,
G
)를 공개키로 한다.
1 단계
수신자
개인비밀키
y
로 선택하고,
yG``
를 계산하여
yG``
를 공개키로 한다.
2 단계
송신자
E(F)
의 원소 중 평문
M``
을 준비한다. 임의의 정수
k
를 선택하여
C_1` = kG``
,
C_2 = M + k(yG)
을 계산하여 암호문
(C_1 , C_2 )
을 수신자에게 보낸다
복호화
수신자
수신자는
C_2 - yC_1`
을 계산하여 평문
M``
을 얻는다.
(예). [암호화와 복호화하기] (예6)에서와 같이 공개키로서
F= _11
,
a=4,~b=3
과
G=(0,5)
를 공개한다. 그리고 수신자는 개인비밀키로
y=5
, 송신자는 수신자에게 보낼 평문
M=(3,3)
을 준비한다.
먼저 수신자가 개인비밀키 5로
yG=5(0,5) = (5,7)
을 계산하여 공개키로
(5,7)
을 공개한다.
다음에 송신자는 임의의 정수
k=3
을 선택하여 공개키
G=(0,5)
와 수신자의 공개키
(5,7)
를 이용하여 암호문
C_1 ```=` kG ``=``3(0,5) = (10,8)
과
C■_2 &= M + k(yG) #&= (3,3) +[3 (5,7)] # &= (3,3)+(0,5)#& = (6,10)
을 계산하여
(C_1 ,C_2 )
를 수신자에게 보낸다.
수신자는 다음 계산을 하여 복호화한다.
C_2 - yC_1 &= M+ k(yG) - y(kG) #&= (6,10) - 5(10,8) #&=(6,10) - (0,5) #&=(6,10) + (0,6) #&= (3,3).
타원곡선을 이용한 Massey-Omura암호
이 암호는 단순히 타원곡선의 이산대수문제만을 이용한 암호이다. 이 암호는 사용자 각자가
gcd(e , N)=1`
인 수
e ~( 1 < e < N``)
를 선택하여 유틀리드 알고리즘을 이용하여
e d == 1 ~(mod~N)``
인 수
d``
를 구하여
(e,d``)
를 비밀키로 하여 전달하고자 하는 평문에 각 개인의 비밀키만을 곱하여 두 번 주고받으면 암호문을 전달할 수 있는 암호계이다. 자세히 요약하면 <아래 표>와 같다.
타원곡선 Massey-Omura암호 알고리즘
단 계
행위자
내 용
준 비
공 통
유한체
F`
상의 타원곡선군
E(F)
와
E(F)
의 위수
N``
을 구하여
(
F`
,
E(F)
,
N``
)를 공개한다.
송신자(A)
gcd(e_A , N)=1`
인 수
e_A``
를 임의로 선택하여, 유클리드 알고리즘을 이용하여
e_A d_A == 1 ~(mod~N)``
인 수
d_A``
를 구하고, (
e_A``
,
d_A``
)를 비밀키로 한다.
E(F)
의 원소 중 평문
M``
을 준비한다.
수신자(B)
gcd(e_B , N)=1`
인 수
e_B``
를 임의로 선택하여 유클리드 알고리즘을 이용하여
e_B d_B == 1 ~(mod~N)``
인 수
d_B``
를 구하고, (
e_B``
,
d_B``
)를 비밀키로 한다.
1 단계
송신자(A)
e_A M``
을 계산하여 B에게 보낸다.
2 단계
수신자(B)
e_B (e_A M``)`
을 계산하여 A에게 보낸다.
3 단계
송신자(A)
d_A (e_B e_A M``) = e_B M `
을 계산하여 B에게 보낸다.
4 단계
수신자(B)
d_B ( e_B M``) = M `
을 계산하여 평문
M``
을 얻는다.
암호공격자가 각 단계에서
e_A M``
,
e_B (e_A M``)`
나
e_B M``
을 입수하였다 하더라도
e_A``
나
e_B``
를 구하면 법
N``
에 관한 역원을 구할 수 있어 암호가 깨지지만, 이 역시 이산대수의 문제를 풀어야 하므로 대단히 어려운 문제이다.
이 암호는 개인의 키를 공개하지 않고 또한 상대방에게 비밀키를 전달하지 않으며, 단순히 비밀키의 곱셈만으로 암호화와 복호화를 할 수 있지만, 통신의 회수가 늘어난다는 단점이 있다.
그 외에 RSA암호에서와 마찬가지로 타원곡선 암호를 이용한 Diffie-Hellman 키배송의 알고리즘도 생각할 수 있다.
타원곡선암호 공격법
전통적인 방법으로 Baby-step giant-step, Pollard-
rho`
, Pohlig-Hellmann 등이 있다. (강주성 외: 현대암호학 p. 168)
5. References
■ 김 철, 암호학의 이해, 영풍문고, 1996.
■ 이임영■송유진, 현대암호, 생능출판사, 1999.
■ 강주성 외 6, 현대암호학, 경문사, 2002.
■ 육군사관학교 수학과, 암호학 개론, 경문사, 2001.
■ 이민섭, 현대암호학, 교우사, 2001.
■ http://enigma.dongseo.ac.kr/cipher/lecture/lec4.htm
■ http://www.math.snu.ac.kr/%7Emhkim/a-chosuncrpt.html
■
http://www.rsasecurity.com/rsalabs/cryptobytes/index.html
■ http://www.cipher.or.kr/algorithm/block_cipher/Rsa2.htm
■ http://no-smok.net/ns/moin.cgi/_be_cf_c8_a3
■ http://uukhyun.mytripod.co.kr/rsa_1.htm
■ http://100.naver.com/100.php?id=770223&cid=AD1070875069645&adflag=1
강주성외(2000), 현대암호학, 경문사
박창섭(1999), 암호이론과 보안, 대영사
이민섭(2000), 현대암호학, 교우사.
강주성 외(2000), 현대암호학, 경문사.
전자통신연구원(1999), 암호학의 기초, 경문사.
박승안(1999), 대수학과 암호학, 경문사.
김응태·박승안(1998), 정수론 제4판, 경문사.
이현열 역(1997), 암호조립법 입문, 대영사.
[H] 한국전자통신 연구원, 암호학의 기초, 경문사, 1999.
[SKI] 서광석, 김용태, 임종인, 김창한, 수론과 암호학, 경문사, 1998.

키워드

정수론,   암호학,   정수론 응용의 예