1 /*-
2 * Copyright (c) 1998-2008 DHIS, Dynamic Host Information System
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24 * SUCH DAMAGE.
25 *
26 */
27
28
29 #include<stdio.h>
30 #include<stdlib.h>
31 #include<string.h>
32 #include<time.h>
33
34 #include "qrc.h"
35
36 char gauthp[2][256];
37 char gauthq[2][256];
38 char gauthn[4][256];
39
40 /* qrc_random() - Generates a random integer of n digits
41 * n may be up to 1024
42 */
qrc_random(mpz_t x,int n)43 void qrc_random(mpz_t x,int n) {
44
45 char buff[1024],temp[128];
46 static int seed=0;
47
48 if(!seed) { seed++; srandom(time(NULL)); }
49 memset(buff,0,256);
50 memset(temp,0,128);
51
52 do {
53 sprintf(temp,"%lu",random());
54 strcat(buff,temp);
55
56 } while(strlen(buff) < n);
57 buff[n]='\0';
58
59 mpz_set_str(x,buff,10);
60 return;
61 }
62
63 /* qrc_genkey() - Generates an integer of 100 digits being congruent
64 * to 3 mod 4
65 *
66 */
67
qrc_genkey(mpz_t k)68 void qrc_genkey(mpz_t k) {
69
70 int flag=1;
71
72 do {
73
74
75 mpz_t a,b;
76
77 /* Get a prime number */
78 do qrc_random(k,100); while(!mpz_probab_prime_p(k,5));
79
80 /* Now see if it is congruent to 3 mod 4 */
81 mpz_init(a);mpz_init(b);
82 mpz_set_ui(a,4);
83 mpz_mod(b,k,a);
84 mpz_set_ui(a,3);
85 if(!mpz_cmp(a,b)) flag=0;
86 mpz_clear(a);
87 mpz_clear(b);
88
89 } while(flag);
90
91 }
gen_qrc(void)92 void gen_qrc(void) {
93
94 mpz_t p,q,n;
95
96 mpz_init(p);
97 mpz_init(q);
98 mpz_init(n);
99
100 qrc_genkey(p);
101 show_key(p,2,1);
102 qrc_genkey(q);
103 show_key(q,2,2);
104 mpz_mul(n,p,q);
105 show_key(n,4,3);
106 mpz_clear(p);
107 mpz_clear(q);
108 mpz_clear(n);
109 return;
110 }
111
show_key(mpz_t key,int n,int variab)112 void show_key(mpz_t key,int n,int variab) {
113
114 char buff[1024];
115 char chunk[128];
116 char *cp;
117 int i;
118
119 mpz_get_str(buff,10,key);
120
121 cp=buff;
122 for(i=0;i<n;i++) {
123 memcpy(chunk,cp,50);
124 chunk[50]='\0';
125 if(variab==1) strcpy(gauthp[i],chunk);
126 if(variab==2) strcpy(gauthq[i],chunk);
127 if(variab==3) strcpy(gauthn[i],chunk);
128 cp+=50;
129 }
130 }
131
132 /* qrc_genx() - Geretates a random x relatively prime to n
133 *
134 */
qrc_genx(mpz_t x,mpz_t n)135 void qrc_genx(mpz_t x,mpz_t n) {
136
137 int i;
138 mpz_t t;
139
140 i=mpz_sizeinbase(n,10); /* Get size of n and take 1 */
141 i--;
142
143 mpz_init(t);
144
145 do { /* Generate x of n-1 digits */
146 qrc_random(x,i);
147 qrc_geny(t,x,n); /* square it modulo n to get */
148 mpz_set(x,t); /* quadractic residue */
149 mpz_gcd(t,x,n);
150
151 } while(mpz_cmp_ui(t,1)); /* test relative primeness */
152
153 mpz_clear(t);
154 }
155
156 /* qrc_geny() - y is the quadractic residue given by x^2 mod n
157 *
158 */
qrc_geny(mpz_t y,mpz_t x,mpz_t n)159 void qrc_geny(mpz_t y,mpz_t x,mpz_t n) {
160
161 mpz_powm_ui(y,x,2,n);
162 }
163 /* qrc_sqrty() - Calculates the square root of y mod k using a^((k+1)/4))mod k
164 *
165 */
166
qrc_sqrty(mpz_t s,mpz_t y,mpz_t k)167 void qrc_sqrty(mpz_t s,mpz_t y,mpz_t k) {
168
169 mpz_t t1,t2,t3;
170
171 mpz_init(t1);
172 mpz_init(t2);
173 mpz_init(t3);
174 mpz_set(t1,k);
175 mpz_set_ui(t3,4);
176 mpz_add_ui(t2,t1,1); /* t2 = k+1 */
177 mpz_divexact(t1,t2,t3); /* t1 = t2/4 */
178 mpz_powm(s,y,t1,k);
179 mpz_clear(t1);
180 mpz_clear(t2);
181 mpz_clear(t3);
182 }
183 /* qrc_crt() - Applies the Chinese remainder theorem and calculates x
184 *
185 */
qrc_crt(mpz_t x,mpz_t xp,mpz_t xq,mpz_t p,mpz_t q)186 void qrc_crt(mpz_t x,mpz_t xp,mpz_t xq,mpz_t p,mpz_t q) {
187
188 mpz_t s,t,g1,g2;
189 mpz_t temp;
190
191 mpz_init(s);
192 mpz_init(t);
193 mpz_init(g1);
194 mpz_init(g2);
195 mpz_init(temp);
196
197 /* Use Euclid's theorem to find s and t */
198 mpz_gcdext(g1,s,t,q,p);
199
200 mpz_mul(temp,xp,s); /* Do g1 = x1.s.q */
201 mpz_mul(g1,temp,q);
202
203 mpz_mul(temp,xq,t); /* Do g2 = x2.t.p */
204 mpz_mul(g2,temp,p);
205
206 mpz_add(x,g1,g2); /* Do x = g1 + g2 */
207
208 mpz_clear(temp);
209 mpz_clear(s);
210 mpz_clear(t);
211 mpz_clear(g1);
212 mpz_clear(g2);
213
214 }
215
216 /* qrc_fill_str() - This function fills a buffer pointed by str
217 * with n digits of x. Adds 0's to the left if
218 * required.
219 */
qrc_fill_str(mpz_t x,char * str,int n)220 void qrc_fill_str(mpz_t x, char *str,int n) {
221
222 int i,j;
223 char buff[1024];
224 char buff2[1024];
225 char *cp1,*cp2;
226
227 i=mpz_sizeinbase(x,10); /* Get size of x */
228 j=n-i; /* j = number of 0's to add */
229 if(j<0) return;
230
231 buff[0]='\0';
232 for(i=0;i<j;i++) strcat(buff,"0"); /* Place 0's */
233
234 mpz_get_str(buff2,10,x); /* Add x */
235 strcat(buff,buff2);
236
237 /* Now copy n digits to str */
238 cp1=str;
239 cp2=buff;
240 for(i=0;i<n;i++)
241 *cp1++ = *cp2++;
242 return;
243 }
244
245