[c] RSA 암호화 구현(gmp 라이브러리 활용)

수업 시간에 하는 내용 올려놓고 공유하는 곳.

# RSA

public key : n, e (n=2048bit)

private key : p, q, d (p=1024bit prime)

# 소수판정

MR-prime test

(100% 아니고 에러 확률 1/4)

test 횟수?

-> 에러 확률 어느 정도로 맞출 것이냐?

-> 보안 강도를 어느정도로 맞출 것이냐?

-> ex) 에러 확률 1/122는 56번 돌린다.

(1/4)^56 = 1/(2)^112

1024bit random number -> MR-prime test 56회 -> true -> P

1024bit random number -> masking(홀수만나오게) -> MR-prime test 56회 -> true -> P

0번째 bit값이 0이면 짝수^^

mpz_t p, q;

p->_mp_d[0] = p->_mp_d[0] | 1;

# 중국인의 나머지 정리 (CRT)

d = 2048 bit

c = 2048 bit

p = 1024 bit

x = c^d mod p    =>    x = (c mod p)^(d mod p-1) mod p

y = c^d mod q    =>    y = (c mod q)^(d mod q-1) mod q

z = c^d mod n    =>    z = ( x(q^-1 mod p) ) q + ( y(p^-1 mod q) )p