공개키 암호 알고리즘 개발에 관한 연구

소개글

공개키 암호 알고리즘 개발에 관한 연구에 대한 보고서 자료입니다.

목차

목 차
제 1 장 서 론

제 2 장 공개키 암호알고리즘 기반 논리
제 1 절 소인수분해문제(Integer Factoring Problem)
1. 개요
2. 소수판정 테스트(Primality testing)
3. 인수 분해 알고리즘(Factoring Algorithm)
4. RSA 공개키 암호시스템 및 이에 대한 공격법
5. Dickson 암호시스템과 LUC 암호시스템
제 2 절 이산대수문제(Discrete Log Problem)
1. 개요
2. 이산대수문제에 대한 알고리즘
3. ElGamal 공개키 암호시스템
4. 타원곡선 암호시스템(Elliptic Curve Cryptosystem)
5. 초타원곡선 암호시스템(Hyperelliptic Curve Cryptosystem)
제 3 절 배낭문제(Knapsack Problem)
1. 개요
2. 배낭 유형의 공개키 암호시스템
3. 배낭 유형의 공개키 암호시스템에 대한 공격법
제 4 절 격자축소문제(Lattice Reduction Problem)
1. 개요
2. SVP, CVP, SBP에 대한 근사이론
3. 격자 축소문에 기반 암호알고리즘
제 5 절 그래프 완전지배집합문제(Graph Perfect Dominating Set Problem)
1. 개요
2. Koblitz-Fellows의 암호시스템과 문제점

제 3 장 효율적인 공개키 암호알고리즘 개발
제 1 절 격자축소문제 기반 공개키 암호알고리즘 개발
1. 개요
2. 제안 알고리즘
3. 안전성 분석
4. 프로그램 명세
5. 향후계획
제 2 절 타원곡선 기반 변형 공개키 암호알고리즘 개발
1. 개요
2. 제안 알고리즘
3. 연구결과
4. 프로그램 명세
5. 향후계획
제 3 절 배낭유형의 공개키 암호알고리즘 개발
1. 개요
2. 제안 알고리즘
3. 안전성 분석
4. 프로그램 명세
5. 향후 계획

제 4 장 신규논리 기반 공개키 암호알고리즘 개발
제 1 절 그래프 이론 기반 공개키 암호알고리즘 개발
1. 개요
2. 제안 알고리즘
3. 안전성 분석
4. 향후 계획
제 2 절 기반 공개키 암호알고리즘 개발
1. 개요
2. 제안 알고리즘
3. 안전성 분석
4. 향후 계획

제 5 장 결 론
제 6 장 부 록
제 1 절 격자축소문제 기반 공개키 암호시스템 구현 S/W
제 2 절 타원곡선 기반 변형 공개키 암호시스템 구현 S/W
제 3 절 배낭 유형 공개키 암호시스템 구현S/W

참고문헌

본문내용

저 계산하고, 을 계산해 서명한다. 여기서, . 그리고 이고, 이다.
Boneh, DeMillo, 그리고 Lipton은 Chinese Remainder Theorem에 내재된 위험성을 지적했다. 만약, 서명을 생성하고 있는 와중에, Bob의 computer에 결함이 생겨서 한 가지 명령 수행이 잘못 계산되었다고 하자. 이 경우 Oscar는 Bob의 법 을 쉽게 계산할 수 있다. 그 예로 A. K. Lenstra가 제안한 공격법을 소개해 보겠다. 만약, Bob이 서명을 하고 있는 동안 오류가 한 가지 생겼다고 한다. 그 결과, 또는 중 정확히 한 개가 잘못 계산 될 것이다. 편의상 가 잘못 계산되어 가 되었다고 하자. 그러면, 서명은 로 될 것이다. 만약, Oscarrk 를 도청하면, 가 잘못된 서명이라는 것을 알 수 있다. 왜냐하면, 이기 때문이다. 그리고, 가 성립하므로, 으로부터 의 약수를 구할 수 있다. 이 공격 방법이 성공하기 위해서는, 우선 Oscar는 평문 에 대해 완전히 알고 있어야 한다. 즉, Bob이 어떠한 예비 덧붙이기 과정을 사용하지 않았다고 가정해야 한다. 즉, 이 공격방법을 막기 위해서는 서명하기 이전에 난수만 더해 주면 되겠다. 그렇지 않고, Bob이 서명을 보내기 이전에 서명을 한 번 확인해 보명 더 간단히 해결할 수도 있다. 이러한 확인 과정은, CRT를 이용해 고속연산을 하는 system에 더욱 중요하다. CRT을 이용하지 않은 system을 포함해 많은 system이 random fault를 이용한 공격에 취약하다. 하지만, 이러한 결과들을 너무 이론적인 것이다.
5. Dickson 암호시스템과 LUC 암호시스템
RSA 공개키 암호시스템은 큰 정수를 소인수 분해하는 문제의 어려움에 안전도의 기반을 두고 있으며, 암복호화 과정에서 지수 함수 을 이용한다. 몇몇 암호학자들은 RSA의 지수함수를 대신하여 trapdoor 일방향 함수의 성질을 만족하는 치환 다항식(Permutation polynomial)을 이용한 RSA의 변형시스템을 개발하였다. 1981년에 Muller와 Nobauer는 매개변수 또는 인 경우의 Dickson 함수 을 이용한 Dickson 공개키 암호시스템을 제안하였다. 이 Dickson 시스템의 안전도는 RSA 시스템과 마찬가지로 소인수분해문제를 기반으로 한다. 1993년에 Smith와 Lennon이 개발한 LUC 암호시스템 역시 소인수분해문제에 기반을 두고 있으며, 매개변수 인 Lucas 수열로 정의된 Lucas 함수 을 이용하여 암복호화를 행한다. 여기서는 이와 같은 공개키 암호시스템 중 Dickson 공개키 암호시스템에 대해서 소개한다. 또한, 이 시스템과 RSA 공개키 암호시스템, LUC 암호시스템과의 비교분석을 통하여 Dickson 다항식을 이용한 RSA 유형 공개키 암호시스템의 일반화를 제시한다.
가. Dickson 공개키 암호시스템 및 이에 대한 공격법
Dickson 공개키 암호시스템을 소개하는데 이용할 Dickson 다항식의 정의와 몇가지 기본 성질을 알아보자.
정의 2.1.20을 단위원을 가진 가환환이라 하자. 매개변수 이고 차수가 인 제 1의 Dickson 다항식 를 다음과 같이 정의한다.
여기서 은 과 같거나 작은 가장 큰 정수이다.
인 경우에 라 하면, 인 경우에 이다. 특히, 이면 이 된다. 즉, Dickson 다항식은 지수 함수의 일반형이다. 또한, 임의의 양의 차수 과 임의의 정수 에 대해서 의 계수는 항상 정수임을 알 수 있다. 를 또는 를 만족하는 의 확장환(extension ring) 의 한 단원(unit)이라 하자. Waring\'s formula를 이용하여 다음과 같이 Dickson 다항식을 정의할 수 있다.
위의 식을 이용하면 가 다음과 같은 2차 점화 관계 (the second order recurrence relations)를 만족함을 보일 수 있다. 에 대해 초기값은 이고
위의 점화식을 이용하여 Dickson 다항식을 쉽게 생성할 수 있으며, 다음과 같은 수식들을 얻을 수 있다.
이 두식은 Dickson 다항식을 효율적으로 계산할 수 있는 알고리즘이 이 점화식들을 기반으로 하기 때문에 중요하다. 이 외에도 다음과 같은 식을 만족한다.
이제, Dickson 공개키 암호시스템의 암호화 및 복호화 과정을 살펴보자.
[키 생성 단계]
① Dickson 다항식의 매개변수 를 1 또는 -1로 정함
② 정수 를 선택
③ 임의의 큰 소수 와 지수 를 선택
④와 를 계산
⑤인 임의의 를 선택
⑥인 를 계산
※ 여기서 공개키는 (e,n) 이고, 비밀키는 d이다.
[암호화 단계]
메시지 에 대한 암호문 생성
[복호화 단계]
비밀키 d를 이용하여 평문 을 얻음
이 시스템은 일단 이 소인수 분해되면 복호화 키 와 복호화 함수 를 쉽게 계산할 수 있어 원래의 메시지를 복원할 수 있다. 그러나, 법 을 소인수 분해하는 문제가 Dickson 공개키 암호시스템을 해독하는 것과 동치인지에 대한 증명은 존재하지 않는다. 암호화 함수 의 역함수를 구하는 지금까지 알려진 모든 방법은 법 을 소인수 분해하는 것을 필요로 한다. 이 시스템의 실질적인 문제는 암복호화 시에 개 항의 합을 계산해야 한다는 것이다. Dickson 공개키 암호시스템이 처음 제시되었을 때는 암복호화 함수의 효율적인 계산방법이 제시되지 않았으나, 이후 1988년에 Post1이 위의 두 점화식을 이용하여 를 효율적으로 계산하는 알고리즘을 제시했다. 이를 RSA 공개키 암호시스템에서의 지수함수 과 비교하면 Dickson 다항식의 계산 시간이 가장 빠른 최상의 경우에는 2배만큼 걸린다는 것을 알 수 있다. 1994년에 More는 매개변수 또는 인 경우의 Dickson 공개키 암호시스템의 평균적인 계산량이 RSA 공개키 암호시스템의 약 1.3배 만큼 필요하다는 것을 보였다. 앞으로 본 고에서는 법 인 경우로 제한한다.
소인수 분해 공격을 피하고 메시지 공간을 극대화하기 위해 Dickson 공개키 암호시스템의 키 변수가 만족해야 할 조건은 RSA 시스템에서와 같다.
① 소인수분해문제를 안전도의 기반으로 하기 때문에 강한 소수(strong prime)를 선택해야

키워드

공개키 ,   암호알고리즘,   암호,   알고리즘개발,   암호개발,   암호알고리즘연구,   연구개발