RSAの仕組み


long int でも計算すぐにオーバーフローするので多倍長化

openssl でチェック大丈夫そうだ

$ openssl genrsa 128 > 128.key
Generating RSA private key, 128 bit long modulus
..+++++++++++++++++++++++++++
...+++++++++++++++++++++++++++
e is 65537 (0x10001)
$ openssl rsa -in 128.key -text
Private-Key: (128 bit)
modulus:
00:bd:ce:f1:ba:04:cd:63:86:25:bf:a3:b4:a8:27:
dd:b7
publicExponent: 65537 (0x10001)
privateExponent:
7b:f8:11:c1:61:29:94:7a:04:eb:42:d3:90:17:f1:
81
prime1:
00:ea:3d:3a:7f:35:f0:4e:51
prime2:
00:cf:71:0b:5d:aa:cc:41:87
exponent1:
00:c6:22:12:78:06:1d:05:71
exponent2:
42:42:24:54:3d:ca:d2:1f
coefficient:
16:69:e5:85:b1:4e:a7:15
writing RSA key
-----BEGIN RSA PRIVATE KEY-----
MGICAQACEQC9zvG6BM1jhiW/o7SoJ923AgMBAAECEHv4EcFhKZR6BOtC05AX8YEC
CQDqPTp/NfBOUQIJAM9xC12qzEGHAgkAxiISeAYdBXECCEJCJFQ9ytIfAggWaeWF
sU6nFQ==
-----END RSA PRIVATE KEY-----

./rsa2 00ea3d3a7f35f04e51 00cf710b5daacc4187
p=ea3d3a7f35f04e51
q=cf710b5daacc4187
phi=bdcef1ba04cd63846c115dd7c76b4de0
e=10001
a=0 b=1 x=10001 y=ade q=bdce33ebd0e192a2d96e84694302
a=1 b=-bdce33ebd0e192a2d96e84694302 x=ade y=60f q=17
a=-17 b=110d86aa2fc4442ca188ede575052f x=60f y=4cf q=1
a=18 b=-11cb54de1b9525bf44625c69de4831 x=4cf y=140 q=1
a=-2f b=22d8db884b5969ebe5eb4a4f534d60 x=140 y=10f q=3
a=a5 b=-7a55e776fda16382f6243b57d83051 x=10f y=31 q=1
a=-d4 b=9d2ec2ff48facd6edc0f85a72b7db1 x=31 y=1a q=5
a=4c9 b=-38c3fb6736a8766ad4271d79bb1a4c6 x=1a y=17 q=1
a=-59d b=4296e7972b382341c1e815d42dd2277 x=17 y=3 q=1
a=a66 b=-7b5ae2fe61e099ac960f334de8ec73d x=3 y=2 q=7
a=-4e67 b=3a2131c8bd85c56f9dc527cf58c49522 x=2 y=1 q=1
a=58cd b=-41d6dff8a3a3cf0a67261b0437535c5f x=1 y=0 q=2
-a734*bdcef1ba04cd63846c115dd7c76b4de0+7bf811c16129947a04eb42d39017f181*10001=1
7bf811c16129947a04eb42d39017f181*10001 mod bdcef1ba04cd63846c115dd7c76b4de0=1
public key e=10001 n=bdcef1ba04cd638625bfa3b4a827ddb7
secret key d=7bf811c16129947a04eb42d39017f181 n=bdcef1ba04cd638625bfa3b4a827ddb7

------------------------------------------------------------
#include
#include
#include
int dd=10;
void euclid(mpz_t r,mpz_t x,mpz_t y){
mpz_t q,x1,y1,a,b,a1,b1,xx;
mpz_init(x1); mpz_init(y1);
mpz_init(a); mpz_init(b);
mpz_init(a1); mpz_init(b1);
mpz_init(q); mpz_init(xx);
mpz_set(x1,x); mpz_set(y1,y);
mpz_set_ui(a,0); mpz_set_ui(b,1); mpz_set_ui(a1,1); mpz_set_ui(b1,0);
while(mpz_cmp_ui(y1,0)!=0){
mpz_div(q,x1,y1); mpz_set(xx,x1); mpz_set(x1,y1); mpz_mod(y1,xx,y1);
mpz_set(xx,a1); mpz_set(a1,a); mpz_mul(a,a,q); mpz_sub(a,xx,a);
mpz_set(xx,b1); mpz_set(b1,b); mpz_mul(b,b,q); mpz_sub(b,xx,b);
printf("a="); mpz_out_str(stdout,dd,a1);
printf(" b="); mpz_out_str(stdout,dd,b1);
printf(" x="); mpz_out_str(stdout,dd,x1);
printf(" y="); mpz_out_str(stdout,dd,y1);
printf(" q="); mpz_out_str(stdout,dd,q);
printf("\n");
}
if(mpz_cmp_ui(b1,0)<0){mpz_add(b1,b1,x);mpz_sub(a1,a1,y);}
mpz_set(r,b1);
mpz_out_str(stdout,dd,a1);
printf("*"); mpz_out_str(stdout,dd,x);
printf("+"); mpz_out_str(stdout,dd,b1);
printf("*"); mpz_out_str(stdout,dd,y);
printf("=1\n");
mpz_out_str(stdout,dd,b1);
printf("*"); mpz_out_str(stdout,dd,y);
printf(" mod "); mpz_out_str(stdout,dd,x);
printf("=1\n");
}
int main(int ac,char *av[]){
mpz_t ret,p,q,x,y,e,d,n;
mpz_init(ret);
mpz_init(e); mpz_init(d); mpz_init(n);
mpz_init(p); mpz_init(q);
mpz_init(x); mpz_init(y);
if(ac<3){printf("usage: ./rsa2 p q [e]\n");exit(-1);}
if(av[1][0]=='0')dd=16;
mpz_set_str(p,av[1],dd);
mpz_set_str(q,av[2],dd);
if(ac<4) mpz_set_str(e,"10001",16);
else mpz_set_str(e,av[3],dd);
mpz_sub_ui(x,p,1);
mpz_sub_ui(y,q,1);
mpz_mul(n,x,y);
printf("p="); mpz_out_str(stdout,dd,p);printf("\n");
printf("q="); mpz_out_str(stdout,dd,q);printf("\n");
printf("phi="); mpz_out_str(stdout,dd,n);printf("\n");
printf("e="); mpz_out_str(stdout,dd,e);printf("\n");
mpz_gcd(ret,n,e);
if(mpz_cmp_ui(ret,1)!=0){
printf("gcd(phi,e)="); mpz_out_str(stdout,dd,ret);
printf(" change e\n");exit(-1);}
euclid(d,n,e);
mpz_mul(n,p,q);
printf("public key e="); mpz_out_str(stdout,dd,e);
printf(" n="); mpz_out_str(stdout,dd,n); printf("\n");
printf("secret key d="); mpz_out_str(stdout,dd,d);
printf(" n="); mpz_out_str(stdout,dd,n); printf("\n");
exit(0);
}

ブログ気持玉

クリックして気持ちを伝えよう!

ログインしてクリックすれば、自分のブログへのリンクが付きます。

→ログインへ

なるほど(納得、参考になった、ヘー)
驚いた
面白い
ナイス
ガッツ(がんばれ!)
かわいい

気持玉数 : 0

この記事へのコメント

この記事へのトラックバック