Logo ROOT   6.30.04
Reference Guide
 All Namespaces Files Pages
rsalib.cxx
Go to the documentation of this file.
1 /* @(#)root/auth:$Id$ */
2 /* Author: Martin Nicolay 22/11/1988 */
3 
4 /******************************************************************************
5 Copyright (C) 2006 Martin Nicolay <m.nicolay@osm-gmbh.de>
6 
7 This library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Lesser General Public
9 License as published by the Free Software Foundation; either
10 version 2.1 of the License, or (at your option) any later
11 version.
12 
13 This library is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU Lesser General Public License for more details.
17 
18 You should have received a copy of the GNU Lesser General Public
19 License along with this library; if not, write to the Free
20 Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
21 MA 02110-1301 USA
22 ******************************************************************************/
23 
24 /*******************************************************************************
25 * *
26 * Simple RSA public key code. *
27 * Adaptation in library for ROOT by G. Ganis, July 2003 *
28 * (gerardo.ganis@cern.ch) *
29 * *
30 *******************************************************************************/
31 
32 #include <stdio.h>
33 #include <string.h>
34 #include <ctype.h>
35 #include <stdlib.h>
36 #include <errno.h>
37 
38 #include "rsaaux.h"
39 #include "rsalib.h"
40 
41 static int g_clear_siz; /* clear-text blocksize */
42 static int g_enc_siz; /* encoded blocksize */
43  /* g_clear_siz < g_enc_siz */
44 
45 int gLog = 0;
46 int kMAXT = 100;
47 
48 rsa_NUMBER rsa_genprim(int len, int prob)
49 {
50  rsa_NUMBER a_three,a_four;
51  rsa_NUMBER prim;
52  int i;
53 
54  a_add( &a_one, &a_two, &a_three );
55  a_add( &a_two, &a_two, &a_four );
56 
57  /* This is done elsewhere to allow different initialization of
58  rand seed (GGa - Sep 15, 2003) */
59  /* init_rnd(); */
60 
61  do {
62  gen_number( len, &prim );
63  } while ( !prim.n_len );
64 
65  a_mult( &prim, &a_two, &prim );
66  a_mult( &prim, &a_three, &prim );
67  a_add( &prim, &a_one, &prim );
68 
69  for (i=1 ;; i++) {
70 
71  if (p_prim( &prim, prob ))
72  break;
73  if (i % 2)
74  a_add( &prim, &a_four, &prim );
75  else
76  a_add( &prim, &a_two, &prim );
77  }
78 
79  return prim;
80 }
81 
82 int rsa_genrsa(rsa_NUMBER p1, rsa_NUMBER p2, rsa_NUMBER *n, rsa_NUMBER *e, rsa_NUMBER *d)
83 {
84  rsa_NUMBER phi, *max_p;
85  int len;
86  int ii, jj;
87 
88  if ( !a_cmp( &p1, &p2) ) return 1;
89 
90  if (a_cmp( &p1, &p2) > 0)
91  max_p = &p1;
92  else
93  max_p = &p2;
94 
95 
96  a_mult( &p1, &p2, n );
97  a_sub( &p1, &a_one, &phi );
98  a_sub( &p2, &a_one, e );
99  a_mult( &phi, e, &phi );
100 
101  len = n_bitlen( &phi );
102  len = ( len + 3) / 4;
103 
104  a_assign( &p1, &phi );
105  a_sub( &p1, &a_one, &p1 );
106 
107  /* This is done elsewhere to allow different initialization of
108  rand seed (GGa - Sep 15, 2003) */
109  /* init_rnd(); */
110 
111  ii = 0;
112  do {
113  ii++;
114  jj = 0;
115  do {
116  jj++;
117  gen_number( len, d );
118  } while (((a_cmp( d, max_p) <= 0 || a_cmp( d, &p1) >= 0)) && jj < kMAXT);
119 
120  a_ggt( d, &phi, e );
121  } while ( a_cmp( e, &a_one) && ii < kMAXT);
122 
123  if (ii >= kMAXT || jj >= kMAXT)
124  return 2;
125 
126  inv( d, &phi, e );
127 
128  return 0;
129 
130 }
131 
132 int rsa_encode_size(rsa_NUMBER n)
133 {
134  // Returns length unit block of output
135 
136  return ( n_bitlen( &n) + 7) / 8;
137 }
138 
139 int rsa_encode(char *bufin, int lin, rsa_NUMBER n, rsa_NUMBER e)
140 {
141  /* Encodes plain string in 'bufin' (output in 'bufin')
142  Returns length of encoded string
143  (key validity is not checked) */
144 
145  char buf[ rsa_STRLEN*2 ];
146  char bufout[ rsa_STRLEN*2 ];
147  int i, j, lout;
148  char *pout;
149 
150  g_enc_siz = ( n_bitlen( &n) + 7) / 8;
151  g_clear_siz = g_enc_siz -1;
152  m_init( &n, rsa_NUM0P );
153 
154  pout = bufout;
155  lout = 0;
156  for ( i = 0; i < lin; i += g_clear_siz) {
157 
158  memcpy(buf,bufin+i,g_clear_siz);
159 
160  j = ((lin-i) < g_clear_siz) ? lin-i : g_clear_siz;
161  memset(buf+j,0,(g_enc_siz-j));
162 
163  do_crypt( buf, buf, g_enc_siz, &e );
164 
165  memcpy(pout,buf,g_enc_siz);
166 
167  pout += g_enc_siz;
168  lout += g_enc_siz;
169  }
170 
171  memcpy(bufin,bufout,lout);
172 
173  return lout;
174 
175 }
176 
177 int rsa_decode(char *bufin, int lin, rsa_NUMBER n, rsa_NUMBER e)
178 {
179  /* Decodes string in 'bufin' (output in 'bufin')
180  Returns length of plaintext string
181  (key validity is not checked) */
182 
183  char buf[ rsa_STRLEN*2 ];
184  char bufout[ rsa_STRLEN*2 ];
185  int i, lout;
186  char *pout;
187 
188  g_enc_siz = ( n_bitlen( &n) + 7) / 8;
189  g_clear_siz = g_enc_siz -1;
190  m_init( &n, rsa_NUM0P );
191 
192  pout = bufout;
193  lout = 0;
194  for ( i = 0; i < lin; i += g_enc_siz) {
195 
196  memcpy(buf,bufin+i,g_enc_siz);
197 
198  do_crypt( buf, buf, g_enc_siz, &e );
199 
200  memcpy(pout,buf,g_clear_siz);
201 
202  pout += g_clear_siz;
203  lout += g_clear_siz;
204  }
205 
206  memcpy(bufin,bufout,lout);
207 
208  return lout;
209 
210 }
211 
212 
213 /*******************************************************************************
214  * *
215  * nio.c *
216  * *
217  ********************************************************************************/
218 
219 
220 /*
221  * rsa_NUMBER io
222  */
223 
224 /*
225  * Funktionen
226  *
227  * int num_sput( n, s, l)
228  * rsa_NUMBER *n;
229  * char s[l];
230  * schreibt *n als Hex-Zahl in s
231  *
232  * int num_fput( n, f )
233  * rsa_NUMBER *n;
234  * FILE *f;
235  * schreibt *n als Hex-Zahl in File f
236  *
237  * int num_sget( n, s )
238  * rsa_NUMBER *n;
239  * char *s;
240  * liest Hex-Zahl s in *n ein
241  *
242  * int num_fget( n, f )
243  * rsa_NUMBER *n;
244  * FILE *f;
245  * liest eine Hex-Zahl von f in *n ein
246  *
247  */
248 
249 
250 static const char *gHEX="0123456789ABCDEF";
251 static const char *ghex="0123456789abcdef";
252 
253 static rsa_NUMBER gbits[9];
254 static rsa_NUMBER gint16[16];
255 
256 static int ginit = 0;
257 
258 void num_init()
259 {
260  int i;
261 
262  if (ginit) return;
263 
264  a_assign( &gbits[0], &a_one );
265  for ( i=1; i<9; i++)
266  a_add( &gbits[i-1], &gbits[i-1], &gbits[i] );
267 
268  a_assign( &gint16[0], &a_one );
269  for ( i=1; i<16; i++)
270  a_add( &gint16[i-1], &a_one, &gint16[i] );
271 
272  ginit = 1;
273 }
274 
275 
276 int rsa_num_sput(rsa_NUMBER *n, char *s, int l)
277 {
278 #if rsa_MAXINT == ( (1 << rsa_MAXBIT) - 1 )
279  rsa_INT *p;
280  int bi,ab,i;
281  long b;
282  int first = 1;
283 
284  bi = rsa_MAXBIT * n->n_len;
285  ab = 4 - (bi + 3) % 4 -1;
286  p = &n->n_part[n->n_len -1];
287 
288  if ( (bi+3) / 4 >= l )
289  return(EOF);
290 
291  b = 0;
292  while (bi) {
293  b <<= (rsa_MAXBIT);
294  b |= (unsigned long)*p--;
295  bi -= rsa_MAXBIT;
296  ab += rsa_MAXBIT;
297  while (ab >= 4) {
298  i = (b >> (ab - 4));
299  b &= ( 1L << (ab - 4)) -1L;
300  ab -= 4;
301 
302  if (first && !i)
303  continue;
304  first = 0;
305  *s++ = gHEX[ i ];
306  }
307  }
308  if (b)
309  abort();
310  *s = '\0';
311 
312  return (0);
313 #else
314  rsa_NUMBER r,q;
315  int i,b,p,len,low,high;
316  char *np;
317 
318  if (! ginit)
319  num_init();
320 
321  a_assign( &q, n);
322  len = l;
323  np = s + l;
324 
325  for (; q.n_len && len > 1; len --) {
326  a_div( &q, &gbits[4], &q, &r );
327  for (p=8, b=0, i=3; i >= 0; i--, p /= 2) {
328  if ( a_cmp( &r, &gbits[i]) >= 0) {
329  a_sub( &r, &gbits[i], &r );
330  b += p;
331  }
332  }
333  *--np = gHEX[ b ];
334  }
335  if (q.n_len)
336  return(EOF);
337 
338  l -= len;
339  len = l;
340  for (; l--; )
341  *s++ = *np++;
342 
343  *s = '\0';
344 
345  return (0);
346 #endif
347 }
348 
349 
350 int rsa_num_fput(rsa_NUMBER *n, FILE *f)
351 {
352  int j;
353  char *np;
354  char n_print[ rsa_STRLEN + 1 ];
355 
356  if ( rsa_num_sput( n, n_print, sizeof( n_print) ) == EOF )
357  return(EOF);
358 
359  for (j=0, np=n_print; *np ; np++, j++) {
360  if (j==64) {
361  fputs("\n",f);
362  j = 0;
363  }
364  putc((int)*np,f);
365  }
366 
367  if (j)
368  putc('\n',f);
369 
370  return(0);
371 }
372 
373 
374 int rsa_num_sget(rsa_NUMBER *n, char *s)
375 {
376 #if rsa_MAXINT == ( (1 << rsa_MAXBIT) - 1 )
377  rsa_INT *p;
378  const char *hp;
379  int bi,ab,i;
380  long b;
381  int first = 1;
382 
383  bi = 4 * strlen(s);
384  ab = rsa_MAXBIT - (bi + rsa_MAXBIT -1) % rsa_MAXBIT -1;
385  i = (bi + rsa_MAXBIT-1) / rsa_MAXBIT;
386  p = &n->n_part[ i -1 ];
387  n->n_len = i;
388 
389  if ( i > rsa_MAXLEN )
390  return(EOF);
391 
392  b = 0;
393  while (bi > 0) {
394  if ( (hp = strchr( gHEX, *s )) )
395  i = hp - gHEX;
396  else if ((hp = strchr( ghex, *s )) )
397  i = hp - ghex;
398  else
399  return(EOF);
400  s++;
401 
402  b <<= 4;
403  b |= (unsigned long)i;
404  bi -= 4;
405  ab += 4;
406  while (ab >= rsa_MAXBIT) {
407  i = (b >> (ab - rsa_MAXBIT));
408  b &= ( 1L << (ab - rsa_MAXBIT)) -1L;
409  ab -= rsa_MAXBIT;
410  if (first && !i) {
411  p--;
412  n->n_len--;
413  }
414  else {
415  first = 0;
416  *p-- = i;
417  }
418  }
419  }
420  if (b)
421  abort();
422  *s = '\0';
423 
424  return (0);
425 #else
426  char *p;
427  int i,c;
428 
429  if (! ginit)
430  num_init();
431 
432  n->n_len = 0;
433  while ( (c = *s++ & 0xFF)) {
434  if ( p= strchr( gHEX, c) )
435  i = p - gHEX;
436  else if ( p= strchr( ghex, c) )
437  i = p - ghex;
438  else
439  return(EOF);
440 
441  a_mult( n, &gbits[4], n );
442  if (i)
443  a_add( n, &gint16[i-1], n );
444  }
445 
446  return(0);
447 #endif
448 }
449 
450 int rsa_num_fget(rsa_NUMBER *n, FILE *f)
451 {
452  int j,c;
453  char *np;
454  char n_print[ rsa_STRLEN + 1 ];
455 
456  np = n_print;
457  j = sizeof(n_print);
458  while ( (c=getc(f)) != EOF && ( isxdigit(c) || isspace(c)) ) {
459  if (isspace(c))
460  continue;
461  if (! --j)
462  return(EOF);
463  *np++ = (char)c;
464  }
465  *np = '\0';
466 
467  if (c != EOF)
468  ungetc(c,f);
469 
470  if ( rsa_num_sget( n, n_print) == EOF )
471  return( EOF );
472 
473  return(0);
474 }
475 
476 int rsa_cmp(rsa_NUMBER *c1, rsa_NUMBER *c2)
477 {
478  int l;
479  /* bei verschiedener Laenge klar*/
480  if ( (l=c1->n_len) != c2->n_len)
481  return( l - c2->n_len);
482 
483  /* vergleiche als arrays */
484  return( n_cmp( c1->n_part, c2->n_part, l) );
485 }
486 
487 void rsa_assign(rsa_NUMBER *d, rsa_NUMBER *s)
488 {
489  int l;
490 
491  if (s == d) /* nichts zu kopieren */
492  return;
493 
494  if ((l=s->n_len))
495  memcpy( d->n_part, s->n_part, sizeof(rsa_INT)*l);
496 
497  d->n_len = l;
498 }