타원곡선 편집하기

이동: 둘러보기, 검색

경고: 로그인하지 않았습니다. 편집을 하면 IP 주소가 공개되게 됩니다. 로그인하거나 계정을 생성하면 편집자가 아이디(ID)으로 기록되고, 다른 장점도 있습니다.

편집을 되돌릴 수 있습니다. 이 편집을 되돌리려면 아래의 바뀐 내용을 확인한 후 저장해주세요.
최신판 당신의 편집
38번째 줄: 38번째 줄:
 
'''< 예제 >'''
 
'''< 예제 >'''
 
: y2 = x3-17x+16 에 의해서 정의되는 타원곡선 위의 두 점 P=(0, -4), Q=(1, 0) 이 주어졌을 때, P+Q는 다음과 같이 구할 수 있다. 즉, x1=0, y1 =-4,  x2 =1, y2 =0 을식-1에 대입하면 을 얻게 되므로 P+Q=(15, -56) 이 된다. 실수 계산은 일반적으로 느리며 또한 반올림에 따른 오차로 인하여 정확하지가 않기 때문에 암호 응용에는 적합하지 않아서, [[암호 시스템]] 구축을 위해서는 유한체위에서 정의된 타원곡선 군이 이용된다. P가 소수일 때 유한체 GF(P) 상에서의 타원곡선은 a, b∈GF(P)의 경우에 방정식 y2 mod p =x3+ax+b mod p를 만족하는(x, y) 점들의 집합과 무한대 점 O를 의미하고 x, y∈GF(P)이며, 4a 3 + 27b ≠0 (mod p)이면 타원곡선 군이 정의된다.<ref name="코">코원동서, 〈[http://a.to/19JtTQA 타원곡선 암호 시스템(공개키 암호)]〉 </ref>
 
: y2 = x3-17x+16 에 의해서 정의되는 타원곡선 위의 두 점 P=(0, -4), Q=(1, 0) 이 주어졌을 때, P+Q는 다음과 같이 구할 수 있다. 즉, x1=0, y1 =-4,  x2 =1, y2 =0 을식-1에 대입하면 을 얻게 되므로 P+Q=(15, -56) 이 된다. 실수 계산은 일반적으로 느리며 또한 반올림에 따른 오차로 인하여 정확하지가 않기 때문에 암호 응용에는 적합하지 않아서, [[암호 시스템]] 구축을 위해서는 유한체위에서 정의된 타원곡선 군이 이용된다. P가 소수일 때 유한체 GF(P) 상에서의 타원곡선은 a, b∈GF(P)의 경우에 방정식 y2 mod p =x3+ax+b mod p를 만족하는(x, y) 점들의 집합과 무한대 점 O를 의미하고 x, y∈GF(P)이며, 4a 3 + 27b ≠0 (mod p)이면 타원곡선 군이 정의된다.<ref name="코">코원동서, 〈[http://a.to/19JtTQA 타원곡선 암호 시스템(공개키 암호)]〉 </ref>
 +
 +
[[파일:K9.PNG|썸네일|400픽셀|'''실수체상의 타원곡선 그래프''']]
  
 
* '''타원곡선 이산대수 문제'''
 
* '''타원곡선 이산대수 문제'''
 
: 소수 p에 대해서 GF(p)를 p개의 원소로 구성된 유한체라 하면, 타원곡선 위의 점 P의 위수 t는 TP=O를 만족하는 가장 작은 정수 t로 정의되고, GF(P) 상에서 정의된 타원곡선과 점 Q, 그리 고위수가 t인 타원곡선 위의 점 P가 주어졌을 때 Q=XP를 만족하는 정수 x∈[0, t-1]을 구하는 것을 타원곡선 이산대수 문제이다. 타원곡선 이산대수 문제의 가장 직접적인 해결방법은 Q를 구할 때까지 단순히 P, 2P=P+P, 3P=P+P+P, …를 연속적으로 계산하는 것이지만 t의 값이 매우 클 경우에는 실효성이 게 되어 현재까지 알려진 가장 효율적인 알고리즘은 Pollard의 rho 알고리즘 으로서 번의타원곡선 덧셈이 소요된다. Pohlig-Hellman알고리즘 역시 적용이 가능하지만, t가 소수일 경우에는 [[실효성]] 이 없어지게 되면, 대부분의 학자에 의해서 타원곡선 이산대수 문제는 소인수 분해나 이산대수 문제보다 훨씬 더 어려운 문제로 인식이 된다. 타원곡선 이산대수 문제에 대한 좀 더 적극적인 공격은 Pollard의 rho 알고리즘에 기반을 두고 병렬처리를 가능하게 하는 특수목적의 하드웨어를 구축하는 것이다. 하지만 이런 공격도 t2160 인 경우에는 불가능하게 된다. 현재 타원곡선 암호에 적용 가능한 타원곡선 이산대수의 t 값은 단기적으로 150bit, 장기적으로 180bit 이상이 권고된다.<ref name="코">코원동서, 〈[http://a.to/19JtTQA 타원곡선 암호 시스템(공개키 암호)]〉 </ref>
 
: 소수 p에 대해서 GF(p)를 p개의 원소로 구성된 유한체라 하면, 타원곡선 위의 점 P의 위수 t는 TP=O를 만족하는 가장 작은 정수 t로 정의되고, GF(P) 상에서 정의된 타원곡선과 점 Q, 그리 고위수가 t인 타원곡선 위의 점 P가 주어졌을 때 Q=XP를 만족하는 정수 x∈[0, t-1]을 구하는 것을 타원곡선 이산대수 문제이다. 타원곡선 이산대수 문제의 가장 직접적인 해결방법은 Q를 구할 때까지 단순히 P, 2P=P+P, 3P=P+P+P, …를 연속적으로 계산하는 것이지만 t의 값이 매우 클 경우에는 실효성이 게 되어 현재까지 알려진 가장 효율적인 알고리즘은 Pollard의 rho 알고리즘 으로서 번의타원곡선 덧셈이 소요된다. Pohlig-Hellman알고리즘 역시 적용이 가능하지만, t가 소수일 경우에는 [[실효성]] 이 없어지게 되면, 대부분의 학자에 의해서 타원곡선 이산대수 문제는 소인수 분해나 이산대수 문제보다 훨씬 더 어려운 문제로 인식이 된다. 타원곡선 이산대수 문제에 대한 좀 더 적극적인 공격은 Pollard의 rho 알고리즘에 기반을 두고 병렬처리를 가능하게 하는 특수목적의 하드웨어를 구축하는 것이다. 하지만 이런 공격도 t2160 인 경우에는 불가능하게 된다. 현재 타원곡선 암호에 적용 가능한 타원곡선 이산대수의 t 값은 단기적으로 150bit, 장기적으로 180bit 이상이 권고된다.<ref name="코">코원동서, 〈[http://a.to/19JtTQA 타원곡선 암호 시스템(공개키 암호)]〉 </ref>
 
[[파일:K9.PNG|썸네일|400픽셀|'''실수체상의 타원곡선 그래프''']]
 
  
 
=== 체에대한 타원곡선 ===
 
=== 체에대한 타원곡선 ===

해시넷에서의 모든 기여는 다른 기여자가 편집, 수정, 삭제할 수 있다는 점을 유의해 주세요. 만약 여기에 동의하지 않는다면, 문서를 저장하지 말아 주세요.
또한, 직접 작성했거나 퍼블릭 도메인과 같은 자유 문서에서 가져왔다는 것을 보증해야 합니다 (자세한 사항은 해시넷:저작권 문서를 보세요). 저작권이 있는 내용을 허가 없이 저장하지 마세요!

취소 | 편집 도움말 (새 창에서 열림)