3/27

#include <stdio.h>

#include <stdlib.h>

#include "gmp.h"

#include <time.h>

clock_t elapsed;

float sec;

#define START_WATCH \

{\

elapsed = -clock(); \

}\

#define STOP_WATCH \

{\

elapsed += clock(); \

sec = (float)elapsed / CLOCKS_PER_SEC; \

}\

#define PRINT_TIME(qstr) \

{\

printf("\n[%s: %.5f s]\n", qstr, sec); \

}\

void RSA_speed_test(int RSA_SIZE, gmp_randstate_t state) {

//RSA Key Generation

//공개키 : n, e

//비밀키 : p,q,d

mpz_t n, e, p, q, d;

mpz_t m, c, tmp;

// int RSA_SIZE;

int mr_itr;

//gmp_randstate_t state;

mpz_init(n);

mpz_init(e);

mpz_init(p);

mpz_init(q);

mpz_init(d);

mpz_init(m);

mpz_init(c);

mpz_init(tmp);

gmp_randinit_default(state);

//RSA_SIZE = 2048;

if (RSA_SIZE == 1024) mr_itr = 40;

else if (RSA_SIZE == 2048) mr_itr = 56;

else if (RSA_SIZE == 3072) mr_itr = 64;

else if (RSA_SIZE == 4096) mr_itr = 96;

// e=2^16+1=0x10001

e->_mp_d[0] = 0x10001;

e->_mp_size = 1;

//위 두 줄 대신 set_str이용해줄수도 있다!

//mpz_set_str(e, "10001", 16);

// p 생성 : 난수생성 -> 소수판정

START_WATCH;

while (1)

{

mpz_urandomb(p, state, (RSA_SIZE>>1));

p->_mp_d[mpz_size(p)-1] |= 0x80000000;

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

if (mpz_probab_prime_p(p, mr_itr)) {

//gcd(p-1,e)=1;

p->_mp_d[0] &= 0xfffffffe; //for p-1

//gcd(p-1,e)=1;

mpz_gcd(n, p, e);

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

if ((n->_mp_size == 1) && (n->_mp_d[0] == 1))break;

}

}

STOP_WATCH;

PRINT_TIME("p generate");

// q 생성 : 난수생성 -> 소수판정

START_WATCH;

while (1)

{

mpz_urandomb(q, state, (RSA_SIZE>>1));

q->_mp_d[mpz_size(q)-1] |= 0x80000000;

q->_mp_d[0] |= 0x00000001;

if (mpz_probab_prime_p(q, mr_itr)) {

//gcd(q-1,e)=1;

q->_mp_d[0] &= 0xfffffffe; //for q-1

//gcd(q-1,e)=1;

mpz_gcd(n, q, e);

q->_mp_d[0] |= 0x00000001;

if ((n->_mp_size == 1) && (n->_mp_d[0] == 1))break;

}

}

STOP_WATCH;

PRINT_TIME("q generate");

// d = e^(-1) mod phi(n)=(p-1)*(q-1)

START_WATCH;

p->_mp_d[0] &= 0xfffffffe; //p-1

q->_mp_d[0] &= 0xfffffffe; //q-1

mpz_mul(n, p, q);

mpz_invert(d, e, n);

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

q->_mp_d[0] |= 0x00000001;

STOP_WATCH;

PRINT_TIME("d generate")

// n = p*q 계산

START_WATCH;

mpz_mul(n, p, q);

STOP_WATCH;

PRINT_TIME("calculate n")

//암호화 (n보다 작은 message 랜덤하게!)

mpz_urandomm(m, state, n);

START_WATCH;

mpz_powm(c, m, e, n);

STOP_WATCH;

PRINT_TIME("encrypt time");

//복호화

START_WATCH;

mpz_powm(tmp, c, d, n);

STOP_WATCH;

PRINT_TIME("decrypt time");

//출력

// gmp_printf("n : %Zx \n", n);

// gmp_printf("e : %Zx \n", e);

// gmp_printf("p : %Zx \n", p);

// gmp_printf("q : %Zx \n", q);

// gmp_printf("d : %Zx \n", d);

// gmp_printf("m : %Zx \n", m);

// gmp_printf("c : %Zx \n", c);

// gmp_printf("tmp : %Zx \n", tmp);

//실제로는 0으로 초기화시킨후 clear

mpz_clear(n);

mpz_clear(e);

mpz_clear(p);

mpz_clear(q);

mpz_clear(d);

mpz_clear(m);

mpz_clear(c);

mpz_clear(tmp);

}

void main() {

gmp_randstate_t state;

gmp_randinit_default(state);

printf("1024\n");

RSA_speed_test(1024,state);

printf("=========================================\n\n");

printf("2048\n");

RSA_speed_test(2048,state);

printf("=========================================\n\n");

printf("3072\n");

RSA_speed_test(3072,state);

printf("=========================================\n\n");

printf("4096\n");

RSA_speed_test(4096,state);

printf("=========================================\n\n");

}

mpz

ui붙은건->unsigned int

addmul->a*b+c=c

GMP는 문자열 기반이 아니라 숫자기반

ex) 2의 거듭제곱에서 shift가 아닌 mul_2exp

       MR         p,q generate time(대략)

n=1024 80bit 40                   0.25

n=2048 112bit 56                   3.5

n=3072 128bit 64                   8  

n=4096 192bit 96                   30

--------------------------------------------

문제점: 키 생성이 많이 느리다, 암복호화 속도가 이상하다 이론치와 다르다

state란 무엇인가

seed -> 난수발생기 -> 난수

큰 수!!

32비트가 32개 있어야 1024!!

그래서 2^31