본문 바로가기

보안(Security)

ECDSA Sign & Verify ECDSA(Elliptic Curve Digital Signature Algorithm) : 타원 곡선을 이용한 전자 서명 검증 알고리즘 시나리오 : 앨리스는 그녀의 메시지를 개인키 $d_A$를 이용해 서명을 하고, 밥은 그녀의 공개키 $H_A$를 이용해 유효성 검증을 한다. 앨리스만이 유효한 서명을 할수 있고, 모두가 서명을 확인할 수 있다. 1) 서명 생성 전제 조건 : 도메인 파라미터(D)는 표준을 따른다. 입력 : - 랜덤 변수 $ k \in {1, ..., n-1} $ 혹은 ephemeral key, 혹은 ek. - 해쉬 메시지 z (혹은 4.29 그림에 의하면 $ e = H(m) $) , 혹은 hm. - 개인키 $ d_A $ (4.29 그림의 d), 혹은 pk1 출력 : (r, s) 1. 랜덤.. 더보기
Ecc Point Doubling/Addition 및 고찰 1. Ecc Point Doubling Input : P Output : 2P If $ P =0 $ : then $2P = 0 $. Else $ P = (x, y)$ : If $y = 0$ : then $2P = 0$ Else $ y \ne 0 $ : then let $ s = (3x^2 + a)/(2y) $, $ x_2 = s^2 - 2x $, $ y_2 = s(x - x_2) - y $, and $ 2P = (x_2, y_2)$ --> 6 multiplications, 4 additions/subtractions, and 1 division 2. Ecc Point Addition Input : P, Q Output : P + Q, $(P \ne Q) $ If $P = 0$ : then $P + Q =.. 더보기
Non-adjacent form 1. 정의 NAF(non-adjacent form)는 부호가 있는 정수 표현의 특별한 형태이다. 양의 정수의 이진표현에 서 0이 아닌 비트의 평균 밀도를 낮추어 해밍 웨이트를 최소화시킨다. 정수 7를 예로 들때 $k_i \times k_{i+1} = 0 $를 만족하고 해밍 웨이트가 최소인 $(1001)_2$ 이 정수 7의 NAF가 된다 2. 설명 [Reference] http://www.danielkrenn.at/downloads/talk-advtop2011-wnaf/Graz-2011-03-18-Advanced-Topics.pdf 더보기
ECC(Elliptic Curve Cryptography) - Scalar Multiplication Double and Add Algorithm Ecc는 타원곡선 상에서 정의된 스칼라 곱을 아래와 같이 정의한다. $$ Q = nP = \underbrace{P + P + \cdots + P}_{n\ \text{times}} $$ ※ 참고로, 대칭키 교환 알고리즘인 ECDH에 의하면 여기서 Q가 공개키가 되고, n은 비밀키가 된다. 타원 곡선상의 기본점(Base Point) P는 주로 표준을 따른다(link1)(link2). Scalar Multiplication을 Naive 하게 연산하게 되면 $O(M^2)$ 복잡도를 가진다. 여기서 M은 n을 표현하기 위한 이진 비트수를 뜻한다. (자세한건 링크[2] 참조) Scalar Multiplication을 쉽게하는 알고리즘으로 double and add가 있고.. 더보기