← Back to branch summary

~ubuntu-branches/ubuntu/karmic/gnupg2/karmic-updates

« back to all changes in this revision

Viewing changes to mpi/mpi-inv.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Urlichs
  • Date: 2006-01-24 04:31:42 UTC
  • mfrom: (1.1.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20060124043142-pbg192or6qxv3yk2
Tags: 1.9.20-1
http://bugs.debian.org/306890
http://bugs.debian.org/344530
http://bugs.debian.org/320490
http://bugs.debian.org/348106
* New Upstream version. Closes:#306890,#344530
  * Closes:#320490: gpg-protect-tool fails to decrypt PKCS-12 files 
* Depend on libopensc2-dev, not -1-. Closes:#348106

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