RSA算法描述：
1) 选择两个大素数 p、q， 计算 n = p*q;
2) 产生 e, d 使：
e*d = 1mod(p-1)(q-1)
e 与 (p-1)(q-1) 互质
[公钥] e、n
[私钥] d、n
3) 加密：
c = m^d mod n
4) 解密：
m = c^e mod n
--------------------------------------------------------------------------------------
libtommath是一个大数算法库。以下的代码是用这个库中的函数实现的，相当简单。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
#include <tommath.h>
typedef
struct
{
int
bits;
/* bits in key */
mp_int n;
/* modulus */
mp_int e;
/* public exponent */
mp_int d;
/* private exponent */
}rsa_key;
int
rsa_rng(unsigned
char
*dst,
int
len,
void
*dat)
{
int
x;
for
(x = 0; x < len; x++) dst[x] =
rand
() & 0xFF;
return
len;
}
int
rsa_preme_random( mp_int *a,
int
bits )
{
int
err = mp_prime_random_ex( a, 8, bits, LTM_PRIME_2MSB_ON|LTM_PRIME_SAFE, rsa_rng, NULL );
if
(err != MP_OKAY) {
return
-1;
}
return
0;
}
int
rsa_gen_key( rsa_key *key,
int
bits )
{
mp_int p, q;
mp_int sp, sq;
mp_int n, m;
mp_int e, d;
mp_int t;
//init mp_ints
mp_init( &p ); mp_init( &q ); mp_init( &sp ); mp_init( &sq );
mp_init( &n ); mp_init( &m ); mp_init( &e ); mp_init( &d ); mp_init( &t );
//genarate p & q
rsa_preme_random( &p, bits/2 );
rsa_preme_random( &q, bits/2 );
//make n & m
mp_sub_d( &p, 1, &sp );
mp_sub_d( &q, 1, &sq );
mp_mul( &p, &q, &n );
mp_mul( &sp, &sq, &m );
//make e & d
mp_set( &e, 127 );
retry_e:
mp_gcd( &e, &m, &t );
if
( ( mp_cmp_d(&t, 1) ) > 0 ){
mp_add_d( &e, 2, &e );
goto
retry_e;
}
mp_invmod( &e, &m, &d );
//copy n d e to key struct
mp_init( &key->n );
mp_init( &key->d );
mp_init( &key->e );
key->bits = bits;
mp_copy( &n, &key->n );
mp_copy( &d, &key->d );
mp_copy( &e, &key->e );
mp_clear( &p ); mp_clear( &q ); mp_clear( &sp );mp_clear( &sq );
mp_clear( &n ); mp_clear( &m ); mp_clear( &e ); mp_clear( &d ); mp_clear( &t );
return
0;
}
/*set rsa key by string */
int
rsa_set_key( rsa_key *key,
char
*sn,
char
*se,
char
*sd,
int
bits,
int
radix )
{
key->bits = bits;
mp_init( &key->n );
mp_init( &key->d );
mp_init( &key->e );
if
( sn ) mp_read_radix( &key->n, sn, radix );
if
( se ) mp_read_radix( &key->e, se, radix );
if
( sd ) mp_read_radix( &key->d, sd, radix );
return
0;
}
/*encrypt by private key */
int
rsa_encrypt(mp_int *c, mp_int *m, rsa_key *key)
{
mp_exptmod( c, &key->d, &key->n, m );
return
0;
}
/*decrypt by public key */
int
rsa_decrypt(mp_int *m, mp_int *c, rsa_key *key)
{
mp_exptmod( m, &key->e, &key->n, c );
return
0;
}
int
rsa_test()
{
mp_int c, m;
rsa_key key;
char
sn[] =
"BB7F51983FD8707FD6227C23DEF5D5377A5A737CEF3C5252E578EFE136DF87B50473F9341F1640C8D258034E14C16993FCE6C6B8C3CEEB65FC8FBCD8EB77B3B05AC7C4D09E0FA1BA2EFE87D3184DB6718AE41A7CAD89B8DCE0FE80CEB523D5D647F9DB58A31D2E71AC677E67FA6E75820736C9893761EE4ACD11F31DBDC349EF"
;
char
se[] =
"010001"
;
char
sm[] =
"AA7B0BF4AAE8B7C2ECC485ACFA57770E50BB9207233E4278654717E470691981C187F81FFC3B90895063EF98C0D86B5297B655399309E6699FEE2270B0F3431B5ABAD7E516261926C35BF6BBFEFB49366EBE96DC510E9CBD915337E8188D517D15DCF90298C40233EEEAFD5A9459F5D3410E6B89B44DF6E818FA3594EF935534"
;
char
sc[1024];
mp_init( &c );
mp_init( &m );
rsa_set_key( &key, sn, se, NULL, 128, 16 );
mp_read_radix( &m, sm, 16 );
rsa_decrypt( &m, &c, &key );
mp_toradix( &c, sc, 16 );
printf
(
"%s\n"
, sc);
return
0;
}
|
