• Home
  • About
    • Jiwon Jeong photo

      Jiwon Jeong

      끊임없이 배우며 성장하는 엔지니어

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
    • All Categories
  • Projects

타원곡선암호학

01 Jul 2022

Reading time ~2 minutes

타원곡선벙정식

  • P + Q + R = 0 => 우리가 정의하는 수체계, 직선의 방정식
    • P, Q, R은 하나의 직선 위에 존재하는 점
    • P, Q만 알면 나머지 R 점은 찾기 쉽다!
    • P + Q = -R (점들의 덧셈을 정의하는 공식 탄생)

contentMap

  • 타원 위의 서로 다른 두 점 P, Q의 덧셈을 구하려고 할 때 기울기 m은 다음과 같이 구해진다.
  • 이를 바탕으로 R의 (x,y) 점도 구해진다

contentMap

타원곡선에서의 스칼라 곱셈

contentMap

  • 동일 점을 덧셈하는 경우 즉, P+P=2P의 연산에 대해서는 점P의 접선과 만나는 점의 대칭점을 2P 라고 한다.

double and add algorithm

  • 타원 곡선의 점 곱셈 연산은 점의 스칼라 곱셈(scalar multiplication)이다. 즉, 8∗G는 점G를 8번 더한 것이다.
const A = -7
const B = 10

function add(p, q){
    if(p === undefined) return q
    if(q === undefined) return p

    if(p[0] != q[0]){
        m = (q[1] - p[1]) / (q[0] - p[0])
    }else{
        m = (3*(p[0]**2) + A)/(2*p[1])
    }
    x = m**2 - p[0] - q[0]
    y = p[1] + m*(x - p[0]);

    return [x, y];
}
/*
> p1 = [1,2]
> q1 = [-3,2]
> add(p1 ,q1)
[ 2, 2 ] 
*/


// P+P 연산
function double(p){
    return add(p, p)
}


function scalarMult(p, n){
    let doubled = p // 1P, 2P, 4P, 8P... 이렇게 변할 임시변수
    let power = 0 // 급수
    let result = undefined
    while(n >= (1 << power)){ // 비트연산인데, n >= 2**power 와 같은 표현
        if(((1 << power) & n) != 0) { // 1 << power) 과 n이 같은 값이고, 0이 아니라면 
            result = add(result, doubled)
        }
        doubled = double(doubled)
        power += 1
    } 
    return result

}
  • 우리의 목표는 n * P 를 추측하기 어렵게 하는 것!
    • 그런데, scalarMult 한 결과는 나머지 연산 처럼 계속 순환한다. (특정 수 체계 내에서 닫혀있다)
    • 따라서 모듈러 연산을 적용가능하다.
  • Q = kP 를 만족하는 k를 찾는 것은 매우 어렵다.
    • 단, 특정한 커브들에 대해서만 이를 어렵게 만듦
      • 이더리움이 사용하는 커브는 secp256k1 알고리즘


BlockChainSecuirity Share Tweet +1