← Back to branch summary

~ubuntu-branches/ubuntu/utopic/dropbear/utopic-proposed

« back to all changes in this revision

Viewing changes to libtommath/bn_mp_invmod_slow.c

  • Committer: Bazaar Package Importer
  • Author(s): Matt Johnston
  • Date: 2005-12-08 19:20:21 UTC
  • mfrom: (1.2.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20051208192021-nyp9rwnt77nsg6ty
Tags: 0.47-1
* New upstream release.
* SECURITY: Fix incorrect buffer sizing.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libtommath/bn_mp_invmod_slow.c
33
33
  }
34
34
 
35
35
  /* x = a, y = b */
36
 
  if ((res = mp_copy (a, &x)) != MP_OKAY) {
37
 
    goto __ERR;
 
36
  if ((res = mp_mod(a, b, &x)) != MP_OKAY) {
 
37
      goto LBL_ERR;
38
38
  }
39
39
  if ((res = mp_copy (b, &y)) != MP_OKAY) {
40
 
    goto __ERR;
 
40
    goto LBL_ERR;
41
41
  }
42
42
 
43
43
  /* 2. [modified] if x,y are both even then return an error! */
44
44
  if (mp_iseven (&x) == 1 && mp_iseven (&y) == 1) {
45
45
    res = MP_VAL;
46
 
    goto __ERR;
 
46
    goto LBL_ERR;
47
47
  }
48
48
 
49
49
  /* 3. u=x, v=y, A=1, B=0, C=0,D=1 */
50
50
  if ((res = mp_copy (&x, &u)) != MP_OKAY) {
51
 
    goto __ERR;
 
51
    goto LBL_ERR;
52
52
  }
53
53
  if ((res = mp_copy (&y, &v)) != MP_OKAY) {
54
 
    goto __ERR;
 
54
    goto LBL_ERR;
55
55
  }
56
56
  mp_set (&A, 1);
57
57
  mp_set (&D, 1);
61
61
  while (mp_iseven (&u) == 1) {
62
62
    /* 4.1 u = u/2 */
63
63
    if ((res = mp_div_2 (&u, &u)) != MP_OKAY) {
64
 
      goto __ERR;
 
64
      goto LBL_ERR;
65
65
    }
66
66
    /* 4.2 if A or B is odd then */
67
67
    if (mp_isodd (&A) == 1 || mp_isodd (&B) == 1) {
68
68
      /* A = (A+y)/2, B = (B-x)/2 */
69
69
      if ((res = mp_add (&A, &y, &A)) != MP_OKAY) {
70
 
         goto __ERR;
 
70
         goto LBL_ERR;
71
71
      }
72
72
      if ((res = mp_sub (&B, &x, &B)) != MP_OKAY) {
73
 
         goto __ERR;
 
73
         goto LBL_ERR;
74
74
      }
75
75
    }
76
76
    /* A = A/2, B = B/2 */
77
77
    if ((res = mp_div_2 (&A, &A)) != MP_OKAY) {
78
 
      goto __ERR;
 
78
      goto LBL_ERR;
79
79
    }
80
80
    if ((res = mp_div_2 (&B, &B)) != MP_OKAY) {
81
 
      goto __ERR;
 
81
      goto LBL_ERR;
82
82
    }
83
83
  }
84
84
 
86
86
  while (mp_iseven (&v) == 1) {
87
87
    /* 5.1 v = v/2 */
88
88
    if ((res = mp_div_2 (&v, &v)) != MP_OKAY) {
89
 
      goto __ERR;
 
89
      goto LBL_ERR;
90
90
    }
91
91
    /* 5.2 if C or D is odd then */
92
92
    if (mp_isodd (&C) == 1 || mp_isodd (&D) == 1) {
93
93
      /* C = (C+y)/2, D = (D-x)/2 */
94
94
      if ((res = mp_add (&C, &y, &C)) != MP_OKAY) {
95
 
         goto __ERR;
 
95
         goto LBL_ERR;
96
96
      }
97
97
      if ((res = mp_sub (&D, &x, &D)) != MP_OKAY) {
98
 
         goto __ERR;
 
98
         goto LBL_ERR;
99
99
      }
100
100
    }
101
101
    /* C = C/2, D = D/2 */
102
102
    if ((res = mp_div_2 (&C, &C)) != MP_OKAY) {
103
 
      goto __ERR;
 
103
      goto LBL_ERR;
104
104
    }
105
105
    if ((res = mp_div_2 (&D, &D)) != MP_OKAY) {
106
 
      goto __ERR;
 
106
      goto LBL_ERR;
107
107
    }
108
108
  }
109
109
 
111
111
  if (mp_cmp (&u, &v) != MP_LT) {
112
112
    /* u = u - v, A = A - C, B = B - D */
113
113
    if ((res = mp_sub (&u, &v, &u)) != MP_OKAY) {
114
 
      goto __ERR;
 
114
      goto LBL_ERR;
115
115
    }
116
116
 
117
117
    if ((res = mp_sub (&A, &C, &A)) != MP_OKAY) {
118
 
      goto __ERR;
 
118
      goto LBL_ERR;
119
119
    }
120
120
 
121
121
    if ((res = mp_sub (&B, &D, &B)) != MP_OKAY) {
122
 
      goto __ERR;
 
122
      goto LBL_ERR;
123
123
    }
124
124
  } else {
125
125
    /* v - v - u, C = C - A, D = D - B */
126
126
    if ((res = mp_sub (&v, &u, &v)) != MP_OKAY) {
127
 
      goto __ERR;
 
127
      goto LBL_ERR;
128
128
    }
129
129
 
130
130
    if ((res = mp_sub (&C, &A, &C)) != MP_OKAY) {
131
 
      goto __ERR;
 
131
      goto LBL_ERR;
132
132
    }
133
133
 
134
134
    if ((res = mp_sub (&D, &B, &D)) != MP_OKAY) {
135
 
      goto __ERR;
 
135
      goto LBL_ERR;
136
136
    }
137
137
  }
138
138
 
145
145
  /* if v != 1 then there is no inverse */
146
146
  if (mp_cmp_d (&v, 1) != MP_EQ) {
147
147
    res = MP_VAL;
148
 
    goto __ERR;
 
148
    goto LBL_ERR;
149
149
  }
150
150
 
151
151
  /* if its too low */
152
152
  while (mp_cmp_d(&C, 0) == MP_LT) {
153
153
      if ((res = mp_add(&C, b, &C)) != MP_OKAY) {
154
 
         goto __ERR;
 
154
         goto LBL_ERR;
155
155
      }
156
156
  }
157
157
  
158
158
  /* too big */
159
159
  while (mp_cmp_mag(&C, b) != MP_LT) {
160
160
      if ((res = mp_sub(&C, b, &C)) != MP_OKAY) {
161
 
         goto __ERR;
 
161
         goto LBL_ERR;
162
162
      }
163
163
  }
164
164
  
165
165
  /* C is now the inverse */
166
166
  mp_exch (&C, c);
167
167
  res = MP_OKAY;
168
 
__ERR:mp_clear_multi (&x, &y, &u, &v, &A, &B, &C, &D, NULL);
 
168
LBL_ERR:mp_clear_multi (&x, &y, &u, &v, &A, &B, &C, &D, NULL);
169
169
  return res;
170
170
}
171
171
#endif