学习了一下RSA的实现

pointer

主要参考PKCS#1文档
利用了gmp和mhash库.
使用示例:

./rsa -k rsakey --pin password -f testin -o eout
./rsa -k rsakey --pin password -d -f eout -o dout

Key-Pair示例

1. 
   
2. # rsakey file
   
3. # every line should like below verbosly without #
   
4. #p=1234345234521
   
5. #p=0xabcd78681
   
6. #p=071234
   
7. 
   
8. # has these sections
   
9. # p,q private prime
   
10. # n   modulus, n's length should be at least hash_len+4 bytes, the longer the better,
    
11. #     and more efficent for size.
    
12. #     the hash_len for sha1 is 20, and sha256 is 32. cur use sha1.
    
13. # d   decrypt priavte key
    
14. # e   encrypt public key
    
15. #  e=3213531385645551797655269345573485190241206387309544045384388753404578116867113921876014611339100923015091369066697829034443462519195336194839504846753773774626577528969985966217658232582247938901026223885442288817533990973400082467391172354029840157896081712524931431293739237905110365860173846145516826473720173566603102479940816595204190897685793188168701573643367447673000281308639244587618508591206234889570336933007277222902143744080839473018561732769400144090027728147701711440722839602873469978897861479886422925304985168762104108292149429656210650105528213534039327391044048786478565209414879849225257747337
    
16. d=169258535211602407454289366564760320314234449009819175987247464020576502124431674676109820966938765248459868936451649729834408405473756699992778158122135155340959763340236569311539730618855953
    
17. n=3356290175696944624889977359872915979764431525108550170386939121287775220471939091212620798724268489404968079532769980701058719660984642444522841248246878762394831180392646437417022723983414069327776338557319351828352982962288653043591388990548600488975194801824576739762555445519545665671552544553787647853875680072274077042431073586458592666493927202419993693748745226844065298333730440143538863306890276021012673272660746971921282501693884488811972505697716590409600692791313052443703252691607181569688328691460606100738042959614921557621790163293233102615102397781075505774943293514173712562558459824017024904519
    

复制代码

1. 
   
2. /*
   
3. /*
   
4. * try to implments RSA and learn gmp
   
5. *
   
6. * gcc -lmhash -lgmp rsa.c -o rsa
   
7. *
   
8. */
   
9. #include<stdio.h>
   
10. #include<gmp.h>
    
11. #include<mhash.h>
    
12. #include<getopt.h>
    
13. #include<assert.h>
    
14. 
    
15. typedef struct
    
16. {
    
17. mpz_t n; // the RSA modulus, a positive integer
    
18. mpz_t e; // the RSA public exponent, a positive integer
    
19. mpz_t d; // the RSA private exponent, a positive integer
    
20. int   k; // the length in ocets of the modulus n.
    
21. mpz_t p; // the first factor, a positive integer
    
22. mpz_t q; // the second factor, a positive integer
    
23. }rsa_key_t;
    
24. 
    
25. typedef struct
    
26. {
    
27. int hLen;
    
28. int limit;
    
29. unsigned char *(*func)(unsigned char *t, int l);
    
30. }hash_t;
    
31. 
    
32. 
    
33. /*
    
34. * formula
    
35. * e*d \equiv 1 \mod \lambda(n) ==> e*d=1 mod (phi(n))
    
36. * e*dP = 1 mod (p-1)
    
37. * e*dQ = 1 mod (q-1)
    
38. * q*qInv = 1 mod p
    
39. */
    
40. 
    
41. 
    
42. /*
    
43. * I2OSP (x, xLen)
    
44. *
    
45. * input x nonegative  integer to be converted.
    
46. *       xLen intended length of the resulting octet string.
    
47. * output X corresponding octet string of length xLen.
    
48. * Error: "integer too large"
    
49. */
    
50. 
    
51. // assume pool has least xLen's length!
    
52. int i2osp(mpz_t x, unsigned char* pool, int xLen)
    
53. {
    
54. int s, bs;
    
55. s=mpz_sizeinbase(x, 2);
    
56. bs=((s+7)>>3);
    
57. if(bs>xLen) return -2;
    
58. memset(pool, 0, xLen-bs);
    
59. mpz_export(pool+xLen-bs, NULL, 1, 1, 1, 0, x);
    
60. return 1;
    
61. }
    
62. 
    
63. /*
    
64. * OS2IP
    
65. * Input:         X        octet string to be converted
    
66. *  Output:        x        corresponding nonnegative integer
    
67. */
    
68. int os2ip(mpz_t x, unsigned char *pool, int len)
    
69. {
    
70. mpz_import(x, len, 1, sizeof(pool[0]), 1, 0, pool);
    
71. return 1;
    
72. }
    
73. 
    
74. 
    
75. inline int hrsapowm(mpz_t c, mpz_t n, mpz_t e, mpz_t m)
    
76. {
    
77. /* non check, just work for right case?
    
78. if(mpz_cmp(n,m)<1 || mpz_sgn(m)==-1)
    
79.   {
    
80.    exit(17);
    
81.    return -1;
    
82.   }
    
83. */
    
84. mpz_powm(c, m, e, n);
    
85. return 1;
    
86. }
    
87. 
    
88. /*
    
89. * RSAEP ((n, e), m)
    
90. * Input:
    
91. * (n, e) RSA public key
    
92. * m message representative, an integer between 0 and n ­ 1
    
93. * Output:
    
94. * c      ciphertext representative, an integer between 0 and n ­ 1
    
95. * Error:        "message representative out of range"
    
96. * Assumption: RSA public key (n, e) is valid
    
97. */
    
98. 
    
99. int rsaep(mpz_t x, rsa_key_t *K, mpz_t m)
    
100. {
     
101. return hrsapowm(x, K->n, K->e, m);
     
102. }
     
103. 
     
104. 
     
105. /*
     
106. * RSADP (K, c)
     
107. * Input:
     
108. * K RSA private key, where K has one of the following forms:
     
109. * a pair (n, d)
     
110. * a quintuple (p, q, dP, dQ, qInv) and
     
111. * a possibly empty sequence of triplets (ri, di, ti), i = 3, ..., u
     
112. * c      ciphertext representative, an integer between 0 and n ­ 1
     
113. * Output:
     
114. * m      message representative, an integer between 0 and n ­ 1
     
115. * Error:  "ciphertext representative out of range"
     
116. * Assumption: RSA private key K is valid
     
117. */
     
118. 
     
119. int  rsadp(mpz_t m, rsa_key_t *K, mpz_t c)
     
120. {
     
121. return hrsapowm(m, K->n, K->d, c);
     
122. }
     
123. 
     
124. int rsasp1(mpz_t c, rsa_key_t *K, mpz_t m)
     
125. {
     
126. return rsadp(c, K, m);
     
127. }
     
128. 
     
129. int resvp1(mpz_t c, rsa_key_t *K, mpz_t m)
     
130. {
     
131. return rsaep(c, K, m);
     
132. }
     
133. 
     
134. void osxor(unsigned char*dst, int len,
     
135.            unsigned char*s1, unsigned char*s2)
     
136. {
     
137. int i;
     
138. for(i=0;i<len;++i)
     
139.   {
     
140.    dst[i]=s1[i] ^ s2[i];
     
141.   }
     
142. }
     
143. 
     
144. 
     
145. // mask should be at least mask_len+hash_len-1 size;
     
146. // tmpppool should be at least seed_len+4 size
     
147. void mgf1(unsigned char *seed, int seedlen, hash_t *hash,
     
148.           unsigned char *mask, int masklen, unsigned char * tmppool)
     
149. {
     
150. int i;
     
151. int c=(masklen+hash->hLen-1)/hash->hLen;
     
152. 
     
153. memcpy(tmppool, seed, seedlen);
     
154. unsigned char* Hash;
     
155. for(i=0;i<c;++i)
     
156.   {
     
157.    tmppool[seedlen]=(i>>24);
     
158.    tmppool[seedlen+1]=(i>>16);
     
159.    tmppool[seedlen+2]=(i>>8);
     
160.    tmppool[seedlen+3]=i;
     
161.    Hash=hash->func(tmppool, seedlen+4);
     
162.    memcpy(mask+i*hash->hLen,Hash, hash->hLen);
     
163.   }
     
164. }
     
165. 
     
166. typedef struct {
     
167. unsigned char *DB, *dbmask;
     
168. unsigned char *tmppool;
     
169. unsigned char *seed, *seedmask;
     
170. unsigned char *EM;
     
171. unsigned char *pin;
     
172. mpz_t ic, im;
     
173. }oaep_pool_t;
     
174. 
     
175. void init_oaep_pool(oaep_pool_t *pool, rsa_key_t *K, hash_t *hash, char *pin)
     
176. {
     
177. pool->DB=(unsigned char*)malloc(K->k-hash->hLen-1);
     
178. pool->dbmask=(unsigned char*)malloc(K->k-2);
     
179. pool->seed=(unsigned char*)malloc(hash->hLen);
     
180. pool->seedmask=(unsigned char*)malloc(hash->hLen+hash->hLen-1);
     
181. pool->EM=(unsigned char*)malloc(K->k);
     
182. pool->tmppool=hash->func((unsigned char*)pin, strlen(pin));
     
183. pool->pin=(unsigned char*)malloc(hash->hLen);
     
184. memcpy(pool->pin, pool->tmppool, hash->hLen);
     
185. pool->tmppool=(unsigned char*)malloc(K->k+4);
     
186. mpz_init2(pool->ic, K->k*8);
     
187. mpz_init2(pool->im, K->k*8);
     
188. }
     
189. 
     
190. void deinit_oaep_pool(oaep_pool_t *pool)
     
191. {
     
192. mpz_clear(pool->ic);
     
193. mpz_clear(pool->im);
     
194. free(pool->DB);
     
195. free(pool->dbmask);
     
196. free(pool->seedmask);
     
197. free(pool->seed);
     
198. free(pool->tmppool);
     
199. free(pool->EM);
     
200. free(pool->pin);
     
201. }
     
202. 
     
203. 
     
204. unsigned char *rsaes_oaep_encrypt(rsa_key_t *K,
     
205.                                   unsigned char *M, int mLen,
     
206.                                   unsigned char *L, int lLen,
     
207.                                   hash_t *hash,
     
208.                                   oaep_pool_t *pool)
     
209. 
     
210. {
     
211. //len checking ...
     
212. if(lLen>hash->limit
     
213.     || mLen> K->k-2*hash->hLen-2 )
     
214.    return NULL;
     
215. 
     
216. // EME-OAEP encoding
     
217. unsigned char * Hash;
     
218. int i, lPs=K->k-mLen-2*hash->hLen-2;
     
219. Hash=hash->func(L, lLen);
     
220. // set DB
     
221. int dbLen=K->k-hash->hLen-1;
     
222. memcpy(pool->DB, Hash, hash->hLen);
     
223. memset(pool->DB+hash->hLen, 0, lPs);
     
224. pool->DB[lPs+hash->hLen]=1;
     
225. memcpy(pool->DB+lPs+hash->hLen+1, M, mLen);
     
226. for(i=0;i<hash->hLen;++i)  pool->seed[i]=random();
     
227. 
     
228. mgf1(pool->seed, hash->hLen, hash,
     
229.       pool->dbmask, dbLen, pool->tmppool);
     
230. osxor(pool->DB, dbLen, pool->DB, pool->dbmask);
     
231. 
     
232. mgf1(pool->DB, dbLen, hash,
     
233.       pool->seedmask, hash->hLen, pool->tmppool);
     
234. osxor(pool->seed, hash->hLen, pool->seed, pool->seedmask);
     
235. // added by pointer, not standard!!
     
236. osxor(pool->seed, hash->hLen, pool->pin, pool->seed);
     
237. 
     
238. pool->EM[0]=0;
     
239. memcpy(pool->EM+1, pool->seed, hash->hLen);
     
240. memcpy(pool->EM+hash->hLen+1, pool->DB, dbLen);
     
241. 
     
242. os2ip(pool->im, pool->EM, K->k);
     
243. rsaep(pool->ic, K, pool->im);
     
244. i2osp(pool->ic, pool->EM, K->k);
     
245. 
     
246. return pool->EM;
     
247. }
     
248. 
     
249. 
     
250. unsigned char * rsaes_oaep_decrypt(rsa_key_t *K,
     
251.                                    unsigned char *C, int k,
     
252.                                    unsigned char *L, int lLen,
     
253.                                    hash_t *hash,
     
254.                                    oaep_pool_t *pool)
     
255. {
     
256. if(lLen>hash->limit
     
257.     || k!= K->k
     
258.     || k< 2*hash->hLen+2)
     
259.   return NULL;
     
260. int i;
     
261. os2ip(pool->ic, C, K->k);
     
262. if(rsadp(pool->im, K, pool->ic)<0)
     
263.   return NULL;
     
264. i=i2osp(pool->im, pool->EM, K->k);
     
265. if(i==-1 || pool->EM[0]!=0) {
     
266.   fprintf(stderr, "not like a encrypted block?\n");
     
267.   return NULL;
     
268. }
     
269. 
     
270. int dbLen=K->k-hash->hLen-1;
     
271. mgf1(pool->EM+1+hash->hLen, dbLen, hash,
     
272.       pool->seedmask, hash->hLen, pool->tmppool);
     
273. osxor(pool->seed, hash->hLen, pool->EM+1, pool->seedmask);
     
274. // added by pointer, not standard!!
     
275. osxor(pool->seed, hash->hLen, pool->seed, pool->pin);
     
276. 
     
277. mgf1(pool->seed, hash->hLen, hash,
     
278.       pool->dbmask, dbLen, pool->tmppool);
     
279. osxor(pool->DB, dbLen, pool->EM+1+hash->hLen, pool->dbmask);
     
280. 
     
281. unsigned char *Hash=hash->func(L, lLen);
     
282. if(memcmp(Hash, pool->DB, hash->hLen)!=0)
     
283.   {
     
284.    fprintf(stderr, "[decrypt][warning] check hash fail, maybe incorrect ...\n");
     
285.   }
     
286. i=hash->hLen;
     
287. while(i<K->k && pool->DB[i]==0) ++i;
     
288. if(i==K->k || pool->DB[i]!= 1)
     
289.   {
     
290.    fprintf(stderr, "[decrypt] fail with K.k=%d i=%d %.2x!=01\n", K->k, i, pool->DB[i]);
     
291.    return NULL;
     
292.   }
     
293. return pool->DB+i+1;
     
294. }
     
295.                   
     
296. 
     
297. unsigned char *hash_sha1(unsigned char *t, int len)
     
298. {
     
299. static unsigned char hash[20];
     
300. MHASH td=mhash_init(MHASH_SHA1);
     
301. if(td == MHASH_FAILED) exit(13);
     
302. mhash(td, t, len);
     
303. mhash_deinit(td, hash);
     
304. return hash;
     
305. }
     
306. 
     
307. void init_hash(hash_t *hash)
     
308. {
     
309. hash->hLen=20;
     
310. hash->limit=INT_MAX;
     
311. hash->func = hash_sha1;
     
312. }
     
313. 
     
314. int main(int argc, char *argv[])
     
315. {
     
316. char *usage="%s -k keyfile [-e] [-d] [--pin password] [-f inputfile] [-o outputfile]\n";
     
317. int is_encrypt=1;
     
318. int is_decrypt=0;
     
319. unsigned char *label=(unsigned char*)"seceret";
     
320. int lLen;
     
321. char *infile=NULL;
     
322. char *outfile=NULL;
     
323. char *keyfile=NULL;
     
324. char *pin=argv[0];
     
325. 
     
326. FILE *ifp=NULL, *ofp=NULL, *kfp=NULL;
     
327. 
     
328.   rsa_key_t K;
     
329.   mpz_init(K.p);
     
330.   mpz_init(K.q);
     
331.   mpz_init(K.e);
     
332.   mpz_init(K.d);
     
333.   mpz_init(K.n);
     
334. 
     
335. struct option lopt[]=
     
336.   {
     
337.    {"key-file", 1, 0, 'k'},
     
338.    {"encrypt", 0, 0, 'e'},
     
339.    {"decrypt", 0, 0, 'd'},
     
340.    {"input", 1, 0, 'f'},
     
341.    {"output", 1, 0, 'o'},
     
342.    {"label",1,0,'l'},
     
343.    {"help",0,0,'h'},
     
344.    {"pin",1,0,'p'},
     
345.    {"Kn",1, 0, 257},
     
346.    {"Ke",1, 0, 258},
     
347.    {"Kd",1, 0, 259},
     
348.    {"Kp",1, 0, 260},
     
349.    {"Kq",1, 0, 261},
     
350.    {0,0,0,0}
     
351.   };
     
352. int c, opt_idx;
     
353. 
     
354. while(1)
     
355.   {
     
356.    c=getopt_long(argc, argv, "k:f:o:l:p:edh", lopt, &opt_idx);
     
357.    if(c==-1) break;
     
358.    switch(c)
     
359.     {
     
360.     case 0:
     
361.      break;
     
362.     case 'f':
     
363.      infile=optarg;
     
364.      if(ifp!=NULL) fclose(ifp);
     
365.      ifp=fopen(infile, "rb");
     
366.      break;
     
367.     case 'o':
     
368.      outfile=optarg;
     
369.      if(ofp!=NULL) fclose(ofp);
     
370.      ofp=fopen(outfile, "wb");
     
371.      break;
     
372.     case 'k':
     
373.      keyfile=optarg;
     
374.      if(kfp!=NULL) fclose(kfp);
     
375.      kfp=fopen(keyfile, "r");
     
376.      break;
     
377.     case 'e':
     
378.      is_encrypt=1;
     
379.      is_decrypt=0;
     
380.      break;
     
381.     case 'd':
     
382.      is_decrypt=1;
     
383.      is_encrypt=0;
     
384.      break;
     
385.     case 'l':
     
386.      label=(unsigned char*)optarg;
     
387.      break;
     
388.     case 'p':
     
389.      pin=optarg;
     
390.      break;
     
391.     case 257://Kn
     
392.      mpz_set_str(K.n, optarg, 0);
     
393.      break;
     
394.     case 258://Ke
     
395.      mpz_set_str(K.e, optarg, 0);
     
396.      break;
     
397.     case 259://Kd
     
398.      mpz_set_str(K.d, optarg, 0);
     
399.      break;
     
400.     case 260://Kp
     
401.      mpz_set_str(K.p, optarg, 0);
     
402.      break;
     
403.     case 261://Kq
     
404.      mpz_set_str(K.q, optarg, 0);
     
405.      break;
     
406.     default:
     
407.      fprintf(stderr, usage, argv[0]);
     
408.      return 1;
     
409.     }
     
410.   }
     
411. if(ifp==NULL) ifp=stdin;
     
412. if(ofp==NULL) ofp=stdout;
     
413. lLen=strlen((char*)label);
     
414. 
     
415. 
     
416. unsigned char buf[1<<16], *p;
     
417. while(kfp!=NULL && !feof(kfp))
     
418.   {
     
419.    fgets((char*)buf, 1<<16, kfp);
     
420.    switch(buf[0])
     
421.     {
     
422.     case ' ':
     
423.     case '\t':
     
424.     case   0:
     
425.     case '#':
     
426.     case '\r':
     
427.     case '\n':
     
428.      break;
     
429.     case 'p':
     
430.      if(buf[1]=='=' && mpz_sgn(K.p)==0 ) mpz_set_str(K.p,(char*)buf+2, 0);
     
431.      break;
     
432.     case 'q':
     
433.      if(buf[1]=='=' && mpz_sgn(K.q)==0 ) mpz_set_str(K.q,(char*)buf+2, 0);
     
434.      break;
     
435.     case 'd':
     
436.      if(buf[1]=='=' && mpz_sgn(K.d)==0 ) mpz_set_str(K.d,(char*)buf+2, 0);
     
437.      break;
     
438.     case 'e':
     
439.      if(buf[1]=='=' && mpz_sgn(K.e)==0 ) mpz_set_str(K.e,(char*)buf+2, 0);
     
440.      break;
     
441.     case 'n':
     
442.      if(buf[1]=='=' && mpz_sgn(K.n)==0 ) mpz_set_str(K.n,(char*)buf+2, 0);
     
443.      break;
     
444.     default:
     
445.      fprintf(stderr, "rsakey error: %s\n", buf);
     
446.      break;
     
447.     }
     
448.   }
     
449. if(kfp!=NULL) fclose(kfp);
     
450. 
     
451. if(mpz_sgn(K.n)!=1)
     
452.   {
     
453.    if(mpz_sgn(K.p)==1 && mpz_sgn(K.q)==1)
     
454.     {
     
455.      mpz_mul(K.n, K.p, K.q);
     
456.     }
     
457.    else
     
458.     {
     
459.      fprintf(stderr, "[K] modulus not set, and not p or q, ...\n");
     
460.      return 21;
     
461.     }
     
462.   }
     
463. 
     
464. K.k=(mpz_sizeinbase(K.n, 2)+7)/8;
     
465. 
     
466. hash_t hash;
     
467. init_hash(&hash);
     
468. oaep_pool_t pool;
     
469. init_oaep_pool(&pool, &K, &hash, pin);
     
470. int len, t;
     
471. 
     
472. if(is_decrypt)
     
473.   {
     
474.    if(mpz_sgn(K.n)!=1 || mpz_sgn(K.d)!=1)
     
475.     {
     
476.      fprintf(stderr, "[main] no private set to decrypt ...\n");
     
477.      return 23;
     
478.     }
     
479.    while(!feof(ifp))
     
480.     {
     
481.      len=fread(buf, 1, K.k, ifp);
     
482.      if(len==K.k)
     
483.       {
     
484.        p=rsaes_oaep_decrypt(&K, buf, K.k, label, lLen, &hash, &pool);
     
485.        if(p==NULL) exit(1);
     
486.        t=K.k-hash.hLen-1-(p-pool.DB);
     
487.        fwrite(p, 1, t, ofp);
     
488.       }
     
489.      else
     
490.       {
     
491.        if(len>0)
     
492.         fprintf(stderr, "fread wrong, len=%d K.k=%d\n", len, K.k);
     
493.        break;
     
494.       }
     
495.     }
     
496.   }
     
497. else
     
498.   {
     
499.    if(mpz_sgn(K.n)!=1 || mpz_sgn(K.e)!=1)
     
500.     {
     
501.      fprintf(stderr, "[main] no public set to encrypt ...\n");
     
502.      return 24;
     
503.     }
     
504.    int mLen=K.k-2*hash.hLen-2;
     
505.    while(!feof(ifp))
     
506.     {
     
507.      len=fread(buf, 1, mLen, ifp);
     
508.      if(len)
     
509.       {
     
510.        p=rsaes_oaep_encrypt(&K, buf, len, label, lLen, &hash, &pool);
     
511.        if(p==NULL) exit(1);
     
512.        fwrite(p, 1, K.k, ofp);
     
513.       }
     
514.     }
     
515.   }
     
516. fclose(ifp);
     
517. fclose(ofp);
     
518. deinit_oaep_pool(&pool);
     
519. return 0;
     
520. }
     

复制代码