← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/gnupg2/oneiric-updates

« back to all changes in this revision

Viewing changes to mpi/mpi-inv.c

  • Committer: Bazaar Package Importer
  • Author(s): Thomas Viehmann
  • Date: 2008-10-04 10:25:53 UTC
  • mfrom: (5.1.15 intrepid)
  • Revision ID: james.westby@ubuntu.com-20081004102553-fv62pp8dsitxli47
Tags: 2.0.9-3.1
http://bugs.debian.org/499569
* Non-maintainer upload.
* agent/gpg-agent.c: Deinit the threading library before exec'ing
  the command to run in --daemon mode. And because that still doesn't
  restore the sigprocmask, do that manually. Closes: #499569

Show diffs side-by-side

added added

removed removed

Lines of Context:
mpi/mpi-inv.c
1
 
/* mpi-inv.c  -  MPI functions
2
 
 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3
 
 *
4
 
 * This file is part of GnuPG.
5
 
 *
6
 
 * GnuPG is free software; you can redistribute it and/or modify
7
 
 * it under the terms of the GNU General Public License as published by
8
 
 * the Free Software Foundation; either version 2 of the License, or
9
 
 * (at your option) any later version.
10
 
 *
11
 
 * GnuPG is distributed in the hope that it will be useful,
12
 
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13
 
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14
 
 * GNU General Public License for more details.
15
 
 *
16
 
 * You should have received a copy of the GNU General Public License
17
 
 * along with this program; if not, write to the Free Software
18
 
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19
 
 */
20
 
 
21
 
#include <config.h>
22
 
#include <stdio.h>
23
 
#include <stdlib.h>
24
 
#include "mpi-internal.h"
25
 
 
26
 
 
27
 
/****************
28
 
 * Calculate the multiplicative inverse X of A mod N
29
 
 * That is: Find the solution x for
30
 
 *              1 = (a*x) mod n
31
 
 */
32
 
void
33
 
mpi_invm( MPI x, MPI a, MPI n )
34
 
{
35
 
  #if 0
36
 
    MPI u, v, u1, u2, u3, v1, v2, v3, q, t1, t2, t3;
37
 
    MPI ta, tb, tc;
38
 
 
39
 
    u = mpi_copy(a);
40
 
    v = mpi_copy(n);
41
 
    u1 = mpi_alloc_set_ui(1);
42
 
    u2 = mpi_alloc_set_ui(0);
43
 
    u3 = mpi_copy(u);
44
 
    v1 = mpi_alloc_set_ui(0);
45
 
    v2 = mpi_alloc_set_ui(1);
46
 
    v3 = mpi_copy(v);
47
 
    q  = mpi_alloc( mpi_get_nlimbs(u)+1 );
48
 
    t1 = mpi_alloc( mpi_get_nlimbs(u)+1 );
49
 
    t2 = mpi_alloc( mpi_get_nlimbs(u)+1 );
50
 
    t3 = mpi_alloc( mpi_get_nlimbs(u)+1 );
51
 
    while( mpi_cmp_ui( v3, 0 ) ) {
52
 
        mpi_fdiv_q( q, u3, v3 );
53
 
        mpi_mul(t1, v1, q); mpi_mul(t2, v2, q); mpi_mul(t3, v3, q);
54
 
        mpi_sub(t1, u1, t1); mpi_sub(t2, u2, t2); mpi_sub(t3, u3, t3);
55
 
        mpi_set(u1, v1); mpi_set(u2, v2); mpi_set(u3, v3);
56
 
        mpi_set(v1, t1); mpi_set(v2, t2); mpi_set(v3, t3);
57
 
    }
58
 
    /*  log_debug("result:\n");
59
 
        log_mpidump("q =", q );
60
 
        log_mpidump("u1=", u1);
61
 
        log_mpidump("u2=", u2);
62
 
        log_mpidump("u3=", u3);
63
 
        log_mpidump("v1=", v1);
64
 
        log_mpidump("v2=", v2); */
65
 
    mpi_set(x, u1);
66
 
 
67
 
    mpi_free(u1);
68
 
    mpi_free(u2);
69
 
    mpi_free(u3);
70
 
    mpi_free(v1);
71
 
    mpi_free(v2);
72
 
    mpi_free(v3);
73
 
    mpi_free(q);
74
 
    mpi_free(t1);
75
 
    mpi_free(t2);
76
 
    mpi_free(t3);
77
 
    mpi_free(u);
78
 
    mpi_free(v);
79
 
  #elif 0
80
 
    /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
81
 
     * modified according to Michael Penk's solution for Exercice 35 */
82
 
 
83
 
    /* FIXME: we can simplify this in most cases (see Knuth) */
84
 
    MPI u, v, u1, u2, u3, v1, v2, v3, t1, t2, t3;
85
 
    unsigned k;
86
 
    int sign;
87
 
 
88
 
    u = mpi_copy(a);
89
 
    v = mpi_copy(n);
90
 
    for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
91
 
        mpi_rshift(u, u, 1);
92
 
        mpi_rshift(v, v, 1);
93
 
    }
94
 
 
95
 
 
96
 
    u1 = mpi_alloc_set_ui(1);
97
 
    u2 = mpi_alloc_set_ui(0);
98
 
    u3 = mpi_copy(u);
99
 
    v1 = mpi_copy(v);                              /* !-- used as const 1 */
100
 
    v2 = mpi_alloc( mpi_get_nlimbs(u) ); mpi_sub( v2, u1, u );
101
 
    v3 = mpi_copy(v);
102
 
    if( mpi_test_bit(u, 0) ) { /* u is odd */
103
 
        t1 = mpi_alloc_set_ui(0);
104
 
        t2 = mpi_alloc_set_ui(1); t2->sign = 1;
105
 
        t3 = mpi_copy(v); t3->sign = !t3->sign;
106
 
        goto Y4;
107
 
    }
108
 
    else {
109
 
        t1 = mpi_alloc_set_ui(1);
110
 
        t2 = mpi_alloc_set_ui(0);
111
 
        t3 = mpi_copy(u);
112
 
    }
113
 
    do {
114
 
        do {
115
 
            if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
116
 
                mpi_add(t1, t1, v);
117
 
                mpi_sub(t2, t2, u);
118
 
            }
119
 
            mpi_rshift(t1, t1, 1);
120
 
            mpi_rshift(t2, t2, 1);
121
 
            mpi_rshift(t3, t3, 1);
122
 
          Y4:
123
 
            ;
124
 
        } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
125
 
 
126
 
        if( !t3->sign ) {
127
 
            mpi_set(u1, t1);
128
 
            mpi_set(u2, t2);
129
 
            mpi_set(u3, t3);
130
 
        }
131
 
        else {
132
 
            mpi_sub(v1, v, t1);
133
 
            sign = u->sign; u->sign = !u->sign;
134
 
            mpi_sub(v2, u, t2);
135
 
            u->sign = sign;
136
 
            sign = t3->sign; t3->sign = !t3->sign;
137
 
            mpi_set(v3, t3);
138
 
            t3->sign = sign;
139
 
        }
140
 
        mpi_sub(t1, u1, v1);
141
 
        mpi_sub(t2, u2, v2);
142
 
        mpi_sub(t3, u3, v3);
143
 
        if( t1->sign ) {
144
 
            mpi_add(t1, t1, v);
145
 
            mpi_sub(t2, t2, u);
146
 
        }
147
 
    } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
148
 
    /* mpi_lshift( u3, k ); */
149
 
    mpi_set(x, u1);
150
 
 
151
 
    mpi_free(u1);
152
 
    mpi_free(u2);
153
 
    mpi_free(u3);
154
 
    mpi_free(v1);
155
 
    mpi_free(v2);
156
 
    mpi_free(v3);
157
 
    mpi_free(t1);
158
 
    mpi_free(t2);
159
 
    mpi_free(t3);
160
 
  #else
161
 
    /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
162
 
     * modified according to Michael Penk's solution for Exercice 35
163
 
     * with further enhancement */
164
 
    MPI u, v, u1, u2=NULL, u3, v1, v2=NULL, v3, t1, t2=NULL, t3;
165
 
    unsigned k;
166
 
    int sign;
167
 
    int odd ;
168
 
 
169
 
    u = mpi_copy(a);
170
 
    v = mpi_copy(n);
171
 
 
172
 
    for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
173
 
        mpi_rshift(u, u, 1);
174
 
        mpi_rshift(v, v, 1);
175
 
    }
176
 
    odd = mpi_test_bit(v,0);
177
 
 
178
 
    u1 = mpi_alloc_set_ui(1);
179
 
    if( !odd )
180
 
        u2 = mpi_alloc_set_ui(0);
181
 
    u3 = mpi_copy(u);
182
 
    v1 = mpi_copy(v);
183
 
    if( !odd ) {
184
 
        v2 = mpi_alloc( mpi_get_nlimbs(u) );
185
 
        mpi_sub( v2, u1, u ); /* U is used as const 1 */
186
 
    }
187
 
    v3 = mpi_copy(v);
188
 
    if( mpi_test_bit(u, 0) ) { /* u is odd */
189
 
        t1 = mpi_alloc_set_ui(0);
190
 
        if( !odd ) {
191
 
            t2 = mpi_alloc_set_ui(1); t2->sign = 1;
192
 
        }
193
 
        t3 = mpi_copy(v); t3->sign = !t3->sign;
194
 
        goto Y4;
195
 
    }
196
 
    else {
197
 
        t1 = mpi_alloc_set_ui(1);
198
 
        if( !odd )
199
 
            t2 = mpi_alloc_set_ui(0);
200
 
        t3 = mpi_copy(u);
201
 
    }
202
 
    do {
203
 
        do {
204
 
            if( !odd ) {
205
 
                if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
206
 
                    mpi_add(t1, t1, v);
207
 
                    mpi_sub(t2, t2, u);
208
 
                }
209
 
                mpi_rshift(t1, t1, 1);
210
 
                mpi_rshift(t2, t2, 1);
211
 
                mpi_rshift(t3, t3, 1);
212
 
            }
213
 
            else {
214
 
                if( mpi_test_bit(t1, 0) )
215
 
                    mpi_add(t1, t1, v);
216
 
                mpi_rshift(t1, t1, 1);
217
 
                mpi_rshift(t3, t3, 1);
218
 
            }
219
 
          Y4:
220
 
            ;
221
 
        } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
222
 
 
223
 
        if( !t3->sign ) {
224
 
            mpi_set(u1, t1);
225
 
            if( !odd )
226
 
                mpi_set(u2, t2);
227
 
            mpi_set(u3, t3);
228
 
        }
229
 
        else {
230
 
            mpi_sub(v1, v, t1);
231
 
            sign = u->sign; u->sign = !u->sign;
232
 
            if( !odd )
233
 
                mpi_sub(v2, u, t2);
234
 
            u->sign = sign;
235
 
            sign = t3->sign; t3->sign = !t3->sign;
236
 
            mpi_set(v3, t3);
237
 
            t3->sign = sign;
238
 
        }
239
 
        mpi_sub(t1, u1, v1);
240
 
        if( !odd )
241
 
            mpi_sub(t2, u2, v2);
242
 
        mpi_sub(t3, u3, v3);
243
 
        if( t1->sign ) {
244
 
            mpi_add(t1, t1, v);
245
 
            if( !odd )
246
 
                mpi_sub(t2, t2, u);
247
 
        }
248
 
    } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
249
 
    /* mpi_lshift( u3, k ); */
250
 
    mpi_set(x, u1);
251
 
 
252
 
    mpi_free(u1);
253
 
    mpi_free(v1);
254
 
    mpi_free(t1);
255
 
    if( !odd ) {
256
 
        mpi_free(u2);
257
 
        mpi_free(v2);
258
 
        mpi_free(t2);
259
 
    }
260
 
    mpi_free(u3);
261
 
    mpi_free(v3);
262
 
    mpi_free(t3);
263
 
 
264
 
    mpi_free(u);
265
 
    mpi_free(v);
266
 
  #endif
267
 
}
268
 
 
269
 
 
270