Logo ROOT   6.21/01
Reference Guide
rsaaux.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 <ctype.h>
34 #include <string.h>
35 #include <stdlib.h>
36 #include <time.h>
37 #include <sys/types.h>
38 #include <sys/stat.h>
39 #include <fcntl.h>
40 
41 #ifdef WIN32
42 # include <io.h>
43 typedef long off_t;
44 #else
45 # include <unistd.h>
46 # include <sys/time.h>
47 #endif
48 
49 #include "rsaaux.h"
50 #include "rsalib.h"
51 
52 /********************************************************************************
53  * *
54  * arith.c *
55  * *
56  ********************************************************************************/
57 
58 /*
59  * !!!!!!!!!!!!!!!!!!!!!!!!!!!! ACHTUNG !!!!!!!!!!!!!!!!!!!!!!!!!!!!
60  * Es findet keinerlei Ueberpruefung auf Bereichsueberschreitung
61  * statt. Alle Werte muessen natuerliche Zahlen aus dem Bereich
62  * 0 ... (rsa_MAXINT+1)^rsa_MAXLEN-1 sein.
63  *
64  *
65  * Bei keiner Funktion oder Hilsfunktion werden Annahmen getroffen,
66  * ueber die Verschiedenheit von Eingabe- & Ausgabe-Werten.
67  *
68  *
69  * Funktionen:
70  *
71  * a_add( s1, s2, d )
72  * rsa_NUMBER *s1,*s2,*d;
73  * *d = *s1 + *s2;
74  *
75  * a_assign( *d, *s )
76  * rsa_NUMBER *d,*s;
77  * *d = *s;
78  *
79  * int a_cmp( c1, c2 )
80  * rsa_NUMBER *c1,*c2;
81  * 1 : falls *c1 > *c2
82  * 0 : falls *c1 == *c2
83  * -1 : falls *c1 < *c2
84  *
85  * a_div( d1, d2, q, r )
86  * rsa_NUMBER *d1,*d2,*q,*r;
87  * *q = *d1 / *d2 Rest *r;
88  *
89  * a_div2( n )
90  * rsa_NUMBER *n;
91  * *n /= 2;
92  *
93  * a_ggt( a, b, f )
94  * rsa_NUMBER *a,*b,*f;
95  * *f = ( *a, *b );
96  *
97  * a_imult( n, m, d )
98  * rsa_NUMBER *n;
99  * rsa_INT m;
100  * rsa_NUMBER *d;
101  * *d = *n * m
102  *
103  * a_mult( m1, m2, d )
104  * rsa_NUMBER *m1,*m2,*d;
105  * *d = *m1 * *m2;
106  *
107  * a_sub( s1, s2, d )
108  * rsa_NUMBER *s1,*s2,*d;
109  * *d = *s1 - *s2;
110  *
111  * Modulare Funktionen
112  * m_init( n, o )
113  * rsa_NUMBER *n,*o;
114  * Initialsierung der Modularen Funktionen
115  * o != 0 : *o = alter Wert
116  *
117  * m_add( s1, s2, d )
118  * rsa_NUMBER *s1, *s2, *d;
119  * *d = *s1 + *s2;
120  *
121  * m_mult( m1, m2, d )
122  * rsa_NUMBER *m1,*m2,*d;
123  *
124  * m_exp( x, n, z )
125  * rsa_NUMBER *x,*n,*z;
126  * *z = *x exp *n;
127  *
128  *
129  * Hilfs-Funktionen:
130  *
131  * int n_bits( n, b )
132  * rsa_NUMBER *n;
133  * int b;
134  * return( unterste b Bits der Dualdarstellung von n)
135  *
136  * n_div( d1, z2, q, r )
137  * rsa_NUMBER *d1,z2[rsa_MAXBIT],*q,*r;
138  * *q = *d1 / z2[0] Rest *r;
139  * z2[i] = z2[0] * 2^i, i=0..rsa_MAXBIT-1
140  *
141  * int n_cmp( i1, i2, l )
142  * rsa_INT i1[l], i2[l];
143  * 1 : falls i1 > i2
144  * 0 : falls i1 == i2
145  * -1 : falls i1 < i2
146  *
147  * int n_mult( n, m, d, l)
148  * rsa_INT n[l], m, d[];
149  * d = m * n;
150  * return( sizeof(d) ); d.h. 'l' oder 'l+1'
151  *
152  * int n_sub( p1, p2, p3, l, lo )
153  * rsa_INT p1[l], p2[lo], p3[];
154  * p3 = p1 - p2;
155  * return( sizeof(p3) ); d.h. '<= min(l,lo)'
156  *
157  * int n_bitlen( n )
158  * rsa_NUMBER *n;
159  * return( sizeof(n) in bits )
160  *
161  */
162 
163 
164 ////////////////////////////////////////////////////////////////////////////////
165 /// rand() implementation using /udev/random or /dev/random, if available
166 
167 static int aux_rand()
168 {
169 #ifndef WIN32
170  int frnd = open("/dev/urandom", O_RDONLY);
171  if (frnd < 0) frnd = open("/dev/random", O_RDONLY);
172  int r;
173  if (frnd >= 0) {
174  ssize_t rs = read(frnd, (void *) &r, sizeof(int));
175  close(frnd);
176  if (r < 0) r = -r;
177  if (rs == sizeof(int)) return r;
178  }
179  printf("+++ERROR+++ : aux_rand: neither /dev/urandom nor /dev/random are available or readable!\n");
180  struct timeval tv;
181  if (gettimeofday(&tv,0) == 0) {
182  int t1, t2;
183  memcpy((void *)&t1, (void *)&tv.tv_sec, sizeof(int));
184  memcpy((void *)&t2, (void *)&tv.tv_usec, sizeof(int));
185  r = t1 + t2;
186  if (r < 0) r = -r;
187  return r;
188  }
189  return -1;
190 #else
191  // No special random device available: use rand()
192  return rand();
193 #endif
194 }
195 
196 /*
197  * Konstante 1, 2
198  */
200  1,
201  { (rsa_INT)1, },
202 };
203 
205 #if rsa_MAXINT == 1
206  2,
207  { 0, (rsa_INT)1, },
208 #else
209  1,
210  { (rsa_INT)2, },
211 #endif
212 };
213 
214 
215 /*
216  * Vergleiche zwei rsa_INT arrays der Laenge l
217  */
218 int n_cmp(rsa_INT *i1, rsa_INT *i2, int l)
219 {
220  i1 += (l-1); /* Pointer ans Ende */
221  i2 += (l-1);
222 
223  for (;l--;)
224  if ( *i1-- != *i2-- )
225  return( i1[1] > i2[1] ? 1 : -1 );
226 
227  return(0);
228 }
229 
230 /*
231  * Vergleiche zwei rsa_NUMBER
232  */
234 {
235  int l;
236  /* bei verschiedener Laenge klar*/
237  if ( (l=c1->n_len) != c2->n_len)
238  return( l - c2->n_len);
239 
240  /* vergleiche als arrays */
241  return( n_cmp( c1->n_part, c2->n_part, l) );
242 }
243 
244 /*
245  * Zuweisung einer rsa_NUMBER (d = s)
246  */
248 {
249  int l;
250 
251  if (s == d) /* nichts zu kopieren */
252  return;
253 
254  if ((l=s->n_len))
255  memcpy( d->n_part, s->n_part, sizeof(rsa_INT)*l);
256 
257  d->n_len = l;
258 }
259 
260 /*
261  * Addiere zwei rsa_NUMBER (d = s1 + s2)
262  */
264 {
265  int l,lo,ld,same;
266  rsa_LONG sum;
267  rsa_INT *p1,*p2,*p3;
268  rsa_INT b;
269 
270  /* setze s1 auch die groessere Zahl */
271  l = s1->n_len;
272  if ( (l=s1->n_len) < s2->n_len) {
273  rsa_NUMBER *tmp = s1;
274 
275  s1 = s2;
276  s2 = tmp;
277 
278  l = s1->n_len;
279  }
280 
281  ld = l;
282  lo = s2->n_len;
283  p1 = s1->n_part;
284  p2 = s2->n_part;
285  p3 = d->n_part;
286  same = (s1 == d);
287  sum = 0;
288 
289  while (l --) {
290  if (lo) { /* es ist noch was von s2 da */
291  lo--;
292  b = *p2++;
293  }
294  else
295  b = 0; /* ansonten 0 nehmen */
296 
297  sum += (rsa_LONG)*p1++ + (rsa_LONG)b;
298  *p3++ = rsa_TOINT(sum);
299 
300  if (sum > (rsa_LONG)rsa_MAXINT) { /* carry merken */
301  sum = 1;
302  }
303  else
304  sum = 0;
305 
306  if (!lo && same && !sum) /* nichts mehr zu tuen */
307  break;
308  }
309 
310  if (sum) { /* letztes carry beruecksichtigen */
311  ld++;
312  *p3 = sum;
313  }
314 
315  d->n_len = ld; /* Laenge setzen */
316 }
317 
318 /*
319  * Subtrahiere zwei rsa_INT arrays. return( Laenge Ergebniss )
320  * l == Laenge p1
321  * lo== Laenge p3
322  */
323 int n_sub(rsa_INT *p1, rsa_INT *p2, rsa_INT *p3, int l, int lo)
324 {
325  int ld,lc,same;
326  int over = 0;
327  rsa_LONG dif;
328  rsa_LONG a,b;
329 
330  same = (p1 == p3); /* frueher Abbruch moeglich */
331 
332  for (lc=1, ld=0; l--; lc++) {
333  a = (rsa_LONG)*p1++;
334  if (lo) { /* ist noch was von p2 da ? */
335  lo--;
336  b = (rsa_LONG)*p2++;
337  }
338  else
339  b=0; /* ansonten 0 nehmen */
340 
341  if (over) /* frueherer Overflow */
342  b++;
343  if ( b > a) { /* jetzt Overflow ? */
344  over = 1;
345  dif = (rsa_MAXINT +1) + a;
346  }
347  else {
348  over = 0;
349  dif = a;
350  }
351  dif -= b;
352  *p3++ = (rsa_INT)dif;
353 
354  if (dif) /* Teil != 0 : Laenge neu */
355  ld = lc;
356  if (!lo && same && !over) { /* nichts mehr zu tuen */
357  if (l > 0) /* Laenge korrigieren */
358  ld = lc + l;
359  break;
360  }
361  }
362 
363  return( ld );
364 }
365 
366 /*
367  * Subtrahiere zwei rsa_NUMBER (d= s1 - s2)
368  */
370 {
371  d->n_len = n_sub( s1->n_part, s2->n_part, d->n_part
372  ,s1->n_len, s2->n_len );
373 }
374 
375 /*
376  * Mulitipliziere rsa_INT array der Laenge l mit einer rsa_INT (d = n * m)
377  * return neue Laenge
378  */
380 {
381  int i;
382  rsa_LONG mul;
383 
384  for (i=l,mul=0; i; i--) {
385  mul += (rsa_LONG)m * (rsa_LONG)*n++;
386  *d++ = rsa_TOINT(mul);
387  mul = rsa_DIVMAX1( mul );
388  }
389 
390  if (mul) { /* carry ? */
391  l++;
392  *d = mul;
393  }
394 
395  return( l );
396 }
397 
398 /*
399  * Mulitipliziere eine rsa_NUMBER mit einer rsa_INT (d = n * m)
400  */
402 {
403  if (m == 0)
404  d->n_len=0;
405  else if (m == 1)
406  a_assign( d, n );
407  else
408  d->n_len = n_mult( n->n_part, m, d->n_part, n->n_len );
409 }
410 
411 /*
412  * Multipliziere zwei rsa_NUMBER (d = m1 * m2)
413  */
415 {
416  static rsa_INT id[ rsa_MAXLEN ]; /* Zwischenspeicher */
417  rsa_INT *vp; /* Pointer darin */
418  rsa_LONG sum; /* Summe fuer jede Stelle */
419  rsa_LONG tp1; /* Zwischenspeicher fuer m1 */
420  rsa_INT *p2;
421  rsa_INT *p1;
422  int l1,l2,ld,lc,l,i,j;
423 
424  l1 = m1->n_len;
425  l2 = m2->n_len;
426  l = l1 + l2;
427  if (l >= rsa_MAXLEN)
428  abort();
429 
430  for (i=l, vp=id; i--;)
431  *vp++ = 0;
432 
433  /* ohne Uebertrag in Zwischenspeicher multiplizieren */
434  for ( p1 = m1->n_part, i=0; i < l1 ; i++, p1++) {
435 
436  tp1 = (rsa_LONG)*p1;
437  vp = &id[i];
438  sum = 0;
439  for ( p2 = m2->n_part, j = l2; j--;) {
440  sum += (rsa_LONG)*vp + (tp1 * (rsa_LONG)*p2++);
441  *vp++ = rsa_TOINT( sum );
442  sum = rsa_DIVMAX1(sum);
443  }
444  *vp++ += (rsa_INT)sum;
445  }
446 
447  /* jetzt alle Uebertraege beruecksichtigen */
448  ld = 0;
449  for (lc=0, vp=id, p1=d->n_part; lc++ < l;) {
450  if ( (*p1++ = *vp++))
451  ld = lc;
452  }
453 
454  d->n_len = ld;
455 }
456 
457 
458 /*
459  * Dividiere Zwei rsa_NUMBER mit Rest (q= d1 / z2[0] Rest r)
460  * z2[i] = z2[0] * 2^i, i=0..rsa_MAXBIT-1
461  * r = 0 : kein Rest
462  * q = 0 : kein Quotient
463  */
465 {
466  static rsa_NUMBER dummy_rest; /* Dummy Variable, falls r = 0 */
467  static rsa_NUMBER dummy_quot; /* Dummy Variable, falla q = 0 */
468  rsa_INT *i1,*i1e,*i3;
469  int l2,ld,l,lq;
470 #if rsa_MAXINT != 1
471  rsa_INT z;
472  int pw,l2t;
473 #endif
474 
475  if (!z2->n_len)
476  abort();
477 
478  if (!r)
479  r = &dummy_rest;
480  if (!q)
481  q = &dummy_quot;
482 
483  a_assign( r, d1 ); /* Kopie von d1 in den Rest */
484 
485  l2= z2->n_len; /* Laenge von z2[0] */
486  l = r->n_len - l2; /* Laenge des noch ''rechts'' liegenden
487  Stuecks von d1 */
488  lq= l +1; /* Laenge des Quotienten */
489  i3= q->n_part + l;
490  i1= r->n_part + l;
491  ld = l2; /* aktuelle Laenge des ''Vergleichsstuecks''
492  von d1 */
493  i1e= i1 + (ld-1);
494 
495  for (; l >= 0; ld++, i1--, i1e--, l--, i3--) {
496  *i3 = 0;
497 
498  if (ld == l2 && ! *i1e) {
499  ld--;
500  continue;
501  }
502 
503  if ( ld > l2 || (ld == l2 && n_cmp( i1, z2->n_part, l2) >= 0) ) {
504 #if rsa_MAXINT != 1
505  /* nach 2er-Potenzen zerlegen */
506  for (pw=rsa_MAXBIT-1, z=(rsa_INT)rsa_HIGHBIT; pw >= 0; pw--, z /= 2) {
507  if ( ld > (l2t= z2[pw].n_len)
508  || (ld == l2t
509  && n_cmp( i1, z2[pw].n_part, ld) >= 0)) {
510  ld = n_sub( i1, z2[pw].n_part, i1, ld, l2t );
511  (*i3) += z;
512  }
513  }
514 #else
515  /* bei rsa_MAXINT == 1 alles viel einfacher */
516  ld = n_sub( i1, z2->n_part, i1, ld, l2 );
517  (*i3) ++;
518 #endif
519  }
520  }
521 
522  /* Korrektur, falls l von Anfang an Negativ war */
523  l ++;
524  lq -= l;
525  ld += l;
526 
527  if (lq>0 && !q->n_part[lq -1]) /* evtl. Laenge korrigieren */
528  lq--;
529 
530  q->n_len = lq;
531  r->n_len = ld -1;
532 }
533 
534 /*
535  * Dividiere Zwei rsa_NUMBER mit Rest (q= d1 / z2[0] Rest r)
536  * z2[i] = z2[0] * 2^i, i=0..rsa_MAXBIT-1
537  * r = 0 : kein Rest
538  * q = 0 : kein Quotient
539  */
541 {
542 #if rsa_MAXINT != 1
544  rsa_INT z;
545  int i;
546 
547  a_assign( &z2[0], d2 );
548  for (i=1,z=2; i < rsa_MAXBIT; i++, z *= 2)
549  a_imult( d2, z, &z2[i] );
550 
551  d2 = z2;
552 #endif
553 
554  n_div( d1, d2, q, r );
555 }
556 
557 /*
558  * Dividiere eine rsa_NUMBER durch 2
559  */
561 {
562 #if rsa_MAXBIT == rsa_LOWBITS
563  rsa_INT *p;
564  int i;
565 
566 #if rsa_MAXINT != 1
567  rsa_INT h;
568  int c;
569 
570  c=0;
571  i= n->n_len;
572  p= &n->n_part[i-1];
573 
574  for (; i--;) {
575  if (c) {
576  c = (h= *p) & 1;
577  h /= 2;
578  h |= rsa_HIGHBIT;
579  }
580  else {
581  c = (h= *p) & 1;
582  h /= 2;
583  }
584 
585  *p-- = h;
586  }
587 
588  if ( (i= n->n_len) && n->n_part[i-1] == 0 )
589  n->n_len = i-1;
590 
591 #else /* rsa_MAXBIT != 1 */
592  p = n->n_part;
593  i = n->n_len;
594 
595  if (i) {
596  n->n_len = i-1;
597  for (; --i ; p++)
598  p[0] = p[1];
599  }
600 #endif /* rsa_MAXBIT != 1 */
601 #else /* rsa_MAXBIT == rsa_LOWBITS */
602  a_div( n, &a_two, n, rsa_NUM0P );
603 #endif /* rsa_MAXBIT == rsa_LOWBITS */
604 }
605 
606 
607 /*
608  * MODULO-FUNKTIONEN
609  */
610 
612 
613 /*
614  * Init
615  */
617 {
618  rsa_INT z;
619  int i;
620 
621  if (o)
622  a_assign( o, &g_mod_z2[0] );
623 
624  if (! a_cmp( n, &g_mod_z2[0]) )
625  return;
626 
627  for (i=0,z=1; i < rsa_MAXBIT; i++, z *= 2)
628  a_imult( n, z, &g_mod_z2[i] );
629 }
630 
632 {
633  a_add( s1, s2, d );
634  if (a_cmp( d, g_mod_z2) >= 0)
635  a_sub( d, g_mod_z2, d );
636 }
637 
639 {
640  a_mult( m1, m2, d );
641  n_div( d, g_mod_z2, rsa_NUM0P, d );
642 }
643 
644 /*
645  * Restklassen Exponent
646  */
648 {
649  rsa_NUMBER xt,nt;
650 
651  a_assign( &nt, n );
652  a_assign( &xt, x );
653  a_assign( z, &a_one );
654 
655  while (nt.n_len) {
656  while ( ! (nt.n_part[0] & 1)) {
657  m_mult( &xt, &xt, &xt );
658  a_div2( &nt );
659  }
660  m_mult( &xt, z, z );
661  a_sub( &nt, &a_one, &nt );
662  }
663 }
664 
665 /*
666  * GGT
667  */
669 {
670  rsa_NUMBER t[2];
671  int at,bt, tmp;
672 
673  a_assign( &t[0], a ); at= 0;
674  a_assign( &t[1], b ); bt= 1;
675 
676  if ( a_cmp( &t[at], &t[bt]) < 0) {
677  tmp= at; at= bt; bt= tmp;
678  }
679  /* euklidischer Algorithmus */
680  while ( t[bt].n_len) {
681  a_div( &t[at], &t[bt], rsa_NUM0P, &t[at] );
682  tmp= at; at= bt; bt= tmp;
683  }
684 
685  a_assign( f, &t[at] );
686 }
687 
688 /*
689  * die untersten b bits der Dualdarstellung von n
690  * die bits muessen in ein int passen
691  */
692 int n_bits(rsa_NUMBER *n, int b)
693 {
694  rsa_INT *p;
695  int l;
696  unsigned r;
697  int m = (1<<b) -1;
698 
699  if ( n->n_len == 0)
700  return(0);
701 
702  if (rsa_LOWBITS >= b)
703  return( n->n_part[0] & m );
704 
705 #if rsa_LOWBITS != 0
706  l = (b-1) / rsa_LOWBITS;
707 #else
708  l = n->n_len -1;
709 #endif
710  for (p= &n->n_part[l],r=0; l-- >= 0 && b > 0; b-= rsa_LOWBITS, p--) {
711  r = rsa_MULMAX1( r );
712  r += (unsigned)*p;
713  }
714 
715  return( r & m );
716 }
717 
718 /*
719  * Anzahl der bits von n bei Dualdarstellung
720  */
722 {
723  rsa_NUMBER b;
724  int i;
725 
726  a_assign( &b, &a_one );
727 
728  for (i=0; a_cmp( &b, n) <= 0; a_mult( &b, &a_two, &b ), i++)
729  ;
730 
731  return(i);
732 }
733 
734 
735 /*******************************************************************************
736  * *
737  * prim.c *
738  * *
739  ********************************************************************************/
740 
741 /*
742  * RSA
743  *
744  * p,q prim
745  * p != q
746  * n = p*q
747  * phi = (p -1)*(q -1)
748  * e,d aus 0...n-1
749  * e*d == 1 mod phi
750  *
751  * m aus 0...n-1 sei eine Nachricht
752  *
753  * Verschluesseln:
754  * E(x) = x^e mod n ( n,e oeffendlich )
755  *
756  * Entschluesseln:
757  * D(x) = x^d mod n ( d geheim )
758  *
759  *
760  * Sicherheit:
761  *
762  * p,q sollten bei mind. 10^100 liegen.
763  * (d,phi) == 1, das gilt fuer alle Primzahlen > max(p,q).
764  * Allerdings sollte d moeglichst gross sein ( d < phi-1 )
765  * um direktes Suchen zu verhindern.
766  */
767 
768 
769 /*
770  * FUNKTIONEN um RSA Schluessel zu generieren.
771  *
772  * int p_prim( n, m )
773  * rsa_NUMBER *n;
774  * int m;
775  * 0 : n ist nicht prim
776  * 1 : n ist mit Wahrscheinlichkeit (1-1/2^m) prim
777  * ACHTUNG !!!!
778  * p_prim benutzt m_init
779  *
780  * inv( d, phi, e )
781  * rsa_NUMBER *d,*phi,*e;
782  * *e = *d^-1 (mod phi)
783  * ACHTUNG !!!!
784  * p_prim benutzt m_init
785  */
786 
787 /*
788  * Prototypes
789  */
790 static int jak_f( rsa_NUMBER* );
791 static int jak_g( rsa_NUMBER*, rsa_NUMBER* );
792 static int jakobi( rsa_NUMBER*, rsa_NUMBER* );
793 
794 /*
795  * Hilfs-Funktion fuer jakobi
796  */
797 static int jak_f(rsa_NUMBER *n)
798 {
799  int f,ret;
800 
801  f = n_bits( n, 3 );
802 
803  ret = ((f == 1) || (f == 7)) ? 1 : -1;
804 
805  return(ret);
806 }
807 
808 /*
809  * Hilfs-Funktuion fuer jakobi
810  */
811 static int jak_g(rsa_NUMBER *a, rsa_NUMBER *n)
812 {
813  int ret;
814 
815  if ( n_bits( n, 2) == 1 ||
816  n_bits( a, 2) == 1 )
817  ret = 1;
818  else
819  ret = -1;
820 
821  return(ret);
822 }
823 
824 /*
825  * Jakobi-Symbol
826  */
828 {
829  rsa_NUMBER t[2];
830  int at,nt, ret;
831 
832  a_assign( &t[0], a ); at = 0;
833  a_assign( &t[1], n ); nt = 1;
834 
835  /*
836  * b > 1
837  *
838  * J( a, b) =
839  * a == 1 : 1
840  * a == 2 : f(n)
841  * a == 2*b : J(b,n)*J(2,n) ( == J(b,n)*f(n) )
842  * a == 2*b -1 : J(n % a,a)*g(a,n)
843  *
844  */
845 
846  ret = 1;
847  while (1) {
848  if (! a_cmp(&t[at],&a_one)) {
849  break;
850  }
851  if (! a_cmp(&t[at],&a_two)) {
852  ret *= jak_f( &t[nt] );
853  break;
854  }
855  if ( ! t[at].n_len ) /* Fehler :-) */
856  abort();
857  if ( t[at].n_part[0] & 1) { /* a == 2*b -1 */
858  int tmp;
859 
860  ret *= jak_g( &t[at], &t[nt] );
861  a_div( &t[nt], &t[at], rsa_NUM0P, &t[nt] );
862  tmp = at; at = nt; nt = tmp;
863  }
864  else { /* a == 2*b */
865  ret *= jak_f( &t[nt] );
866  a_div2( &t[at] );
867  }
868 
869  }
870 
871  return(ret);
872 }
873 
874 /*
875  * Probabilistischer Primzahltest
876  *
877  * 0 -> n nicht prim
878  * 1 -> n prim mit (1-1/2^m) Wahrscheinlichkeit.
879  *
880  * ACHTUNG !!!!!!
881  * p_prim benutzt m_init !!
882  *
883  */
884 int p_prim(rsa_NUMBER *n, int m)
885 {
886  rsa_NUMBER gt,n1,n2,a;
887  rsa_INT *p;
888  int i,w,j;
889 
890  if (a_cmp(n,&a_two) <= 0 || m <= 0)
891  abort();
892 
893  a_sub( n, &a_one, &n1 ); /* n1 = -1 mod n */
894  a_assign( &n2, &n1 );
895  a_div2( &n2 ); /* n2 = ( n -1) / 2 */
896 
897  m_init( n, rsa_NUM0P );
898 
899  w = 1;
900  for (; w && m; m--) {
901  /* ziehe zufaellig a aus 2..n-1 */
902  do {
903  for (i=n->n_len-1, p=a.n_part; i; i--)
904  *p++ = (rsa_INT)aux_rand();
905  if ((i=n->n_len) )
906  *p = (rsa_INT)( aux_rand() % ((unsigned long)n->n_part[i-1] +1) );
907  while ( i && ! *p )
908  p--,i--;
909  a.n_len = i;
910  } while ( a_cmp( &a, n) >= 0 || a_cmp( &a, &a_two) < 0 );
911 
912  /* jetzt ist a fertig */
913 
914  /*
915  * n ist nicht prim wenn gilt:
916  * (a,n) != 1
917  * oder
918  * a^( (n-1)/2) != J(a,n) mod n
919  *
920  */
921 
922  a_ggt( &a, n, &gt );
923  if ( a_cmp( &gt, &a_one) == 0) {
924 
925  j= jakobi( &a, n );
926  m_exp( &a, &n2, &a );
927 
928  if ( ( a_cmp( &a, &a_one) == 0 && j == 1 )
929  || ( a_cmp( &a, &n1 ) == 0 && j == -1) )
930  w = 1;
931  else
932  w = 0;
933  }
934  else
935  w = 0;
936  }
937 
938  return( w );
939 }
940 
941 /*
942  * Berechne mulitiplikatives Inverses zu d (mod phi)
943  * d relativ prim zu phi ( d < phi )
944  * d.h. (d,phi) == 1
945  *
946  * ACHTUNG !!!!
947  * inv benutzt m_init
948  */
950 {
951  int k, i0, i1, i2;
952  rsa_NUMBER r[3],p[3],c;
953 
954  /*
955  * Berlekamp-Algorithmus
956  * ( fuer diesen Spezialfall vereinfacht )
957  */
958 
959  if (a_cmp(phi,d) <= 0)
960  abort();
961 
962  m_init( phi, rsa_NUM0P );
963 
964  p[1].n_len = 0;
965  a_assign( &p[2], &a_one );
966  a_assign( &r[1], phi );
967  a_assign( &r[2], d );
968 
969  k = -1;
970  do {
971  k++;
972  i0=k%3; i1=(k+2)%3; i2=(k+1)%3;
973  a_div( &r[i2], &r[i1], &c, &r[i0] );
974  m_mult( &c, &p[i1], &p[i0] );
975  m_add( &p[i0], &p[i2], &p[i0] );
976  } while (r[i0].n_len);
977 
978  if ( a_cmp( &r[i1], &a_one) ) /* r[i1] == (d,phi) muss 1 sein */
979  abort();
980 
981  if ( k & 1 ) /* falsches ''Vorzeichen'' */
982  a_sub( phi, &p[i1], e );
983  else
984  a_assign( e, &p[i1] );
985 }
986 
987 
988 /*******************************************************************************
989  * *
990  * rnd.c *
991  * *
992  ********************************************************************************/
993 
994 void gen_number(int len, rsa_NUMBER *n)
995 {
996  const char *hex = "0123456789ABCDEF" ;
997  char num[ rsa_STRLEN +1 ];
998  char *p;
999  int i,l;
1000 
1001  p=&num[ sizeof(num) -1];
1002  *p-- = '\0';
1003 
1004  for (l=len; l--; p--) {
1005  i = aux_rand() % 16;
1006  *p = hex[ i ];
1007  }
1008  p++;
1009 
1010  while (len-- && *p == '0')
1011  p++;
1012 
1013  rsa_num_sget( n, p );
1014 }
1015 
1016 void init_rnd()
1017 {
1018  const char *randdev = "/dev/urandom";
1019 
1020  int fd;
1021  unsigned int seed;
1022  if ((fd = open(randdev, O_RDONLY)) != -1) {
1023  if (read(fd, &seed, sizeof(seed))) {;}
1024  close(fd);
1025  } else {
1026  seed = (unsigned int)time(0); //better use times() + win32 equivalent
1027  }
1028  srand( seed );
1029 }
1030 
1031 
1032 /*******************************************************************************
1033  * *
1034  * aux.c *
1035  * *
1036  ********************************************************************************/
1037 
1038 /* These are not needed, for the moment
1039 
1040 int get_clear(char *p, FILE *fp)
1041 {
1042 int n;
1043 
1044 n = fread( p, 1, clear_siz, fp );
1045 
1046 if (n <= 0)
1047 return(0);
1048 
1049 memset( p + n, 0, enc_siz - n );
1050 
1051 return(1);
1052 }
1053 
1054 int get_enc(char *p, FILE *fp)
1055 {
1056  int n;
1057 
1058  n = fread( p, 1, enc_siz, fp );
1059 
1060  if (n != enc_siz)
1061  return(0);
1062 
1063  return(1);
1064 }
1065 
1066 int put_clear(char *p, FILE *fp)
1067 {
1068  int n;
1069 
1070  n = fwrite( p, 1, clear_siz, fp );
1071 
1072  if (n != clear_siz)
1073  return(0);
1074 
1075  return(1);
1076 }
1077 
1078 int put_enc(char *p, FILE *fp)
1079 {
1080  int n;
1081 
1082  n = fwrite( p, 1, enc_siz, fp );
1083 
1084  if (n != enc_siz)
1085  return(0);
1086 
1087  return(1);
1088 }
1089 
1090 */
1091 
1092 void do_crypt(char *s, char *d, int len, rsa_NUMBER *e)
1093 {
1094  static char hex[] = "0123456789ABCDEF";
1095  rsa_NUMBER n;
1096  char buf[ rsa_STRLEN + 1 ];
1097  char *ph;
1098  int i,c;
1099 
1100  ph = buf + rsa_STRLEN - 1;
1101  ph[1] = '\0';
1102 
1103  for (i=len; i; i--) {
1104  c = *s++;
1105  *ph-- = hex[ (c >> 4) & 0xF ];
1106  *ph-- = hex[ c & 0xF ];
1107  }
1108  ph++;
1109 
1110  rsa_num_sget( &n, ph );
1111 
1112  m_exp( &n, e, &n );
1113 
1114  rsa_num_sput( &n, buf, rsa_STRLEN +1 );
1115 
1116  ph = buf + (i=strlen(buf)) -1;
1117 
1118  for (; len; len--) {
1119  if (i-- > 0) {
1120  c = (strchr( hex, *ph) - hex) << 4;
1121  ph--;
1122  }
1123  else
1124  c=0;
1125  if (i-- > 0) {
1126  c |= strchr( hex, *ph) - hex;
1127  ph--;
1128  }
1129 
1130  *d++ = c;
1131  }
1132 }
1133 
rsa_NUMBER a_one
Definition: rsaaux.cxx:199
#define rsa_DIVMAX1(x)
Definition: rsadef.h:91
void inv(rsa_NUMBER *d, rsa_NUMBER *phi, rsa_NUMBER *e)
Definition: rsaaux.cxx:949
static long int sum(long int i)
Definition: Factory.cxx:2276
auto * m
Definition: textangle.C:8
unsigned short rsa_INT
Definition: rsadef.h:37
void a_imult(rsa_NUMBER *n, rsa_INT m, rsa_NUMBER *d)
Definition: rsaaux.cxx:401
int n_cmp(rsa_INT *i1, rsa_INT *i2, int l)
Definition: rsaaux.cxx:218
return c1
Definition: legend1.C:41
int * lq
Definition: THbookFile.cxx:86
int p_prim(rsa_NUMBER *n, int m)
Definition: rsaaux.cxx:884
#define rsa_TOINT(x)
Definition: rsadef.h:72
static int aux_rand()
rand() implementation using /udev/random or /dev/random, if available
Definition: rsaaux.cxx:167
void a_div(rsa_NUMBER *d1, rsa_NUMBER *d2, rsa_NUMBER *q, rsa_NUMBER *r)
Definition: rsaaux.cxx:540
#define f(i)
Definition: RSha256.hxx:104
int a_cmp(rsa_NUMBER *c1, rsa_NUMBER *c2)
Definition: rsaaux.cxx:233
void m_init(rsa_NUMBER *n, rsa_NUMBER *o)
Definition: rsaaux.cxx:616
void m_add(rsa_NUMBER *s1, rsa_NUMBER *s2, rsa_NUMBER *d)
Definition: rsaaux.cxx:631
#define rsa_HIGHBIT
Definition: rsadef.h:88
#define rsa_NUM0P
Definition: rsadef.h:109
void a_assign(rsa_NUMBER *d, rsa_NUMBER *s)
Definition: rsaaux.cxx:247
Double_t x[n]
Definition: legend1.C:17
void a_ggt(rsa_NUMBER *a, rsa_NUMBER *b, rsa_NUMBER *f)
Definition: rsaaux.cxx:668
void init_rnd()
Definition: rsaaux.cxx:1016
static constexpr double s
void m_exp(rsa_NUMBER *x, rsa_NUMBER *n, rsa_NUMBER *z)
Definition: rsaaux.cxx:647
void a_sub(rsa_NUMBER *s1, rsa_NUMBER *s2, rsa_NUMBER *d)
Definition: rsaaux.cxx:369
rsa_INT n_part[rsa_MAXLEN]
Definition: rsadef.h:106
static int jakobi(rsa_NUMBER *, rsa_NUMBER *)
Definition: rsaaux.cxx:827
int n_len
Definition: rsadef.h:105
rsa_NUMBER a_two
Definition: rsaaux.cxx:204
void do_crypt(char *s, char *d, int len, rsa_NUMBER *e)
Definition: rsaaux.cxx:1092
static constexpr double m2
ROOT::R::TRInterface & r
Definition: Object.C:4
int rsa_num_sget(rsa_NUMBER *, char *)
Definition: rsalib.cxx:374
auto * a
Definition: textangle.C:12
void n_div(rsa_NUMBER *d1, rsa_NUMBER *z2, rsa_NUMBER *q, rsa_NUMBER *r)
Definition: rsaaux.cxx:464
unsigned long rsa_LONG
Definition: rsadef.h:38
void m_mult(rsa_NUMBER *m1, rsa_NUMBER *m2, rsa_NUMBER *d)
Definition: rsaaux.cxx:638
#define rsa_MAXLEN
Definition: rsadef.h:86
void a_add(rsa_NUMBER *s1, rsa_NUMBER *s2, rsa_NUMBER *d)
Definition: rsaaux.cxx:263
#define s1(x)
Definition: RSha256.hxx:91
int rsa_num_sput(rsa_NUMBER *, char *, int)
Definition: rsalib.cxx:276
#define h(i)
Definition: RSha256.hxx:106
#define rsa_MAXINT
Definition: rsadef.h:53
void gen_number(int len, rsa_NUMBER *n)
Definition: rsaaux.cxx:994
#define d(i)
Definition: RSha256.hxx:102
#define rsa_STRLEN
Definition: rsadef.h:87
return c2
Definition: legend2.C:14
void a_div2(rsa_NUMBER *n)
Definition: rsaaux.cxx:560
#define rsa_LOWBITS
Definition: rsadef.h:80
auto * t1
Definition: textangle.C:20
int n_sub(rsa_INT *p1, rsa_INT *p2, rsa_INT *p3, int l, int lo)
Definition: rsaaux.cxx:323
int n_bits(rsa_NUMBER *n, int b)
Definition: rsaaux.cxx:692
#define rsa_MULMAX1(x)
Definition: rsadef.h:93
you should not use this method at all Int_t Int_t Double_t Double_t Double_t e
Definition: TRolke.cxx:630
static rsa_NUMBER g_mod_z2[rsa_MAXBIT]
Definition: rsaaux.cxx:611
you should not use this method at all Int_t Int_t z
Definition: TRolke.cxx:630
static int jak_g(rsa_NUMBER *, rsa_NUMBER *)
Definition: rsaaux.cxx:811
auto * l
Definition: textangle.C:4
you should not use this method at all Int_t Int_t Double_t Double_t Double_t Int_t Double_t Double_t Double_t Double_t b
Definition: TRolke.cxx:630
#define c(i)
Definition: RSha256.hxx:101
static int jak_f(rsa_NUMBER *)
Definition: rsaaux.cxx:797
int n_bitlen(rsa_NUMBER *n)
Definition: rsaaux.cxx:721
float * q
Definition: THbookFile.cxx:87
#define rsa_MAXBIT
Definition: rsadef.h:71
const Int_t n
Definition: legend1.C:16
int n_mult(rsa_INT *n, rsa_INT m, rsa_INT *d, int l)
Definition: rsaaux.cxx:379
void a_mult(rsa_NUMBER *m1, rsa_NUMBER *m2, rsa_NUMBER *d)
Definition: rsaaux.cxx:414