Logo ROOT  
Reference Guide
rsaaux.cxx
Go to the documentation of this file.
1/* @(#)root/auth:$Id$ */
2/* Author: Martin Nicolay 22/11/1988 */
3
4/******************************************************************************
5Copyright (C) 2006 Martin Nicolay <m.nicolay@osm-gmbh.de>
6
7This library is free software; you can redistribute it and/or
8modify it under the terms of the GNU Lesser General Public
9License as published by the Free Software Foundation; either
10version 2.1 of the License, or (at your option) any later
11version.
12
13This library is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16GNU Lesser General Public License for more details.
17
18You should have received a copy of the GNU Lesser General Public
19License along with this library; if not, write to the Free
20Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston,
21MA 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>
43typedef 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
167static 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 */
218int 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;
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 */
323int 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 );
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 */
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{
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 */
790static int jak_f( rsa_NUMBER* );
791static int jak_g( rsa_NUMBER*, rsa_NUMBER* );
792static int jakobi( rsa_NUMBER*, rsa_NUMBER* );
793
794/*
795 * Hilfs-Funktion fuer jakobi
796 */
797static 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 */
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 */
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
994void 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
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
1040int get_clear(char *p, FILE *fp)
1041{
1042int n;
1043
1044n = fread( p, 1, clear_siz, fp );
1045
1046if (n <= 0)
1047return(0);
1048
1049memset( p + n, 0, enc_siz - n );
1050
1051return(1);
1052}
1053
1054int 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
1066int 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
1078int 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
1092void 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
long
Definition: Converters.cxx:876
ROOT::R::TRInterface & r
Definition: Object.C:4
#define d(i)
Definition: RSha256.hxx:102
#define b(i)
Definition: RSha256.hxx:100
#define f(i)
Definition: RSha256.hxx:104
#define c(i)
Definition: RSha256.hxx:101
#define s1(x)
Definition: RSha256.hxx:91
#define h(i)
Definition: RSha256.hxx:106
#define e(i)
Definition: RSha256.hxx:103
float * q
Definition: THbookFile.cxx:89
int * lq
Definition: THbookFile.cxx:88
return c1
Definition: legend1.C:41
Double_t x[n]
Definition: legend1.C:17
const Int_t n
Definition: legend1.C:16
return c2
Definition: legend2.C:14
static constexpr double s
static constexpr double m2
int n_cmp(rsa_INT *i1, rsa_INT *i2, int l)
Definition: rsaaux.cxx:218
static rsa_NUMBER g_mod_z2[rsa_MAXBIT]
Definition: rsaaux.cxx:611
void a_imult(rsa_NUMBER *n, rsa_INT m, rsa_NUMBER *d)
Definition: rsaaux.cxx:401
void m_exp(rsa_NUMBER *x, rsa_NUMBER *n, rsa_NUMBER *z)
Definition: rsaaux.cxx:647
void a_mult(rsa_NUMBER *m1, rsa_NUMBER *m2, rsa_NUMBER *d)
Definition: rsaaux.cxx:414
void a_div2(rsa_NUMBER *n)
Definition: rsaaux.cxx:560
void init_rnd()
Definition: rsaaux.cxx:1016
int n_sub(rsa_INT *p1, rsa_INT *p2, rsa_INT *p3, int l, int lo)
Definition: rsaaux.cxx:323
void m_mult(rsa_NUMBER *m1, rsa_NUMBER *m2, rsa_NUMBER *d)
Definition: rsaaux.cxx:638
int a_cmp(rsa_NUMBER *c1, rsa_NUMBER *c2)
Definition: rsaaux.cxx:233
void n_div(rsa_NUMBER *d1, rsa_NUMBER *z2, rsa_NUMBER *q, rsa_NUMBER *r)
Definition: rsaaux.cxx:464
void a_assign(rsa_NUMBER *d, rsa_NUMBER *s)
Definition: rsaaux.cxx:247
static int jak_g(rsa_NUMBER *, rsa_NUMBER *)
Definition: rsaaux.cxx:811
void a_ggt(rsa_NUMBER *a, rsa_NUMBER *b, rsa_NUMBER *f)
Definition: rsaaux.cxx:668
static int jakobi(rsa_NUMBER *, rsa_NUMBER *)
Definition: rsaaux.cxx:827
void gen_number(int len, rsa_NUMBER *n)
Definition: rsaaux.cxx:994
void a_sub(rsa_NUMBER *s1, rsa_NUMBER *s2, rsa_NUMBER *d)
Definition: rsaaux.cxx:369
void a_div(rsa_NUMBER *d1, rsa_NUMBER *d2, rsa_NUMBER *q, rsa_NUMBER *r)
Definition: rsaaux.cxx:540
rsa_NUMBER a_one
Definition: rsaaux.cxx:199
void do_crypt(char *s, char *d, int len, rsa_NUMBER *e)
Definition: rsaaux.cxx:1092
void a_add(rsa_NUMBER *s1, rsa_NUMBER *s2, rsa_NUMBER *d)
Definition: rsaaux.cxx:263
int n_mult(rsa_INT *n, rsa_INT m, rsa_INT *d, int l)
Definition: rsaaux.cxx:379
void m_add(rsa_NUMBER *s1, rsa_NUMBER *s2, rsa_NUMBER *d)
Definition: rsaaux.cxx:631
static int aux_rand()
rand() implementation using /udev/random or /dev/random, if available
Definition: rsaaux.cxx:167
rsa_NUMBER a_two
Definition: rsaaux.cxx:204
static int jak_f(rsa_NUMBER *)
Definition: rsaaux.cxx:797
int n_bits(rsa_NUMBER *n, int b)
Definition: rsaaux.cxx:692
void m_init(rsa_NUMBER *n, rsa_NUMBER *o)
Definition: rsaaux.cxx:616
void inv(rsa_NUMBER *d, rsa_NUMBER *phi, rsa_NUMBER *e)
Definition: rsaaux.cxx:949
int n_bitlen(rsa_NUMBER *n)
Definition: rsaaux.cxx:721
int p_prim(rsa_NUMBER *n, int m)
Definition: rsaaux.cxx:884
#define rsa_MULMAX1(x)
Definition: rsadef.h:93
#define rsa_LOWBITS
Definition: rsadef.h:80
#define rsa_HIGHBIT
Definition: rsadef.h:88
#define rsa_NUM0P
Definition: rsadef.h:109
#define rsa_MAXLEN
Definition: rsadef.h:86
unsigned short rsa_INT
Definition: rsadef.h:37
unsigned long rsa_LONG
Definition: rsadef.h:38
#define rsa_MAXBIT
Definition: rsadef.h:71
#define rsa_STRLEN
Definition: rsadef.h:87
#define rsa_DIVMAX1(x)
Definition: rsadef.h:91
#define rsa_MAXINT
Definition: rsadef.h:53
#define rsa_TOINT(x)
Definition: rsadef.h:72
int rsa_num_sget(rsa_NUMBER *, char *)
Definition: rsalib.cxx:374
int rsa_num_sput(rsa_NUMBER *, char *, int)
Definition: rsalib.cxx:276
int n_len
Definition: rsadef.h:105
rsa_INT n_part[rsa_MAXLEN]
Definition: rsadef.h:106
auto * m
Definition: textangle.C:8
auto * l
Definition: textangle.C:4
auto * a
Definition: textangle.C:12
auto * t1
Definition: textangle.C:20
static uint64_t sum(uint64_t i)
Definition: Factory.cxx:2345