Main Page   Modules   Data Structures   File List   Data Fields   Globals   Related Pages  

beecrypt/dldp.c

Go to the documentation of this file.
00001 
00007 /*
00008  * <conformance statement for IEEE P1363 needed here>
00009  *
00010  * Copyright (c) 2000, 2001 Virtual Unlimited B.V.
00011  *
00012  * Author: Bob Deblier <bob@virtualunlimited.com>
00013  *
00014  * This library is free software; you can redistribute it and/or
00015  * modify it under the terms of the GNU Lesser General Public
00016  * License as published by the Free Software Foundation; either
00017  * version 2.1 of the License, or (at your option) any later version.
00018  *
00019  * This library is distributed in the hope that it will be useful,
00020  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00021  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00022  * Lesser General Public License for more details.
00023  *
00024  * You should have received a copy of the GNU Lesser General Public
00025  * License along with this library; if not, write to the Free Software
00026  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00027  *
00028  */
00029 
00030 #include "system.h"
00031 #include "dldp.h"
00032 #include "mp32.h"
00033 #include "mp32prime.h"
00034 #include "debug.h"
00035 
00038 static int dldp_pgoqGenerator_w(dldp_p* dp, randomGeneratorContext* rgc, /*@out@*/ uint32* wksp)
00039         /*@modifies dp->g, wksp @*/;
00040 
00043 static int dldp_pgonGenerator_w(dldp_p* dp, randomGeneratorContext* rgc, /*@out@*/ uint32* wksp)
00044         /*@modifies dp->g, wksp @*/;
00045 
00046 int dldp_pPrivate(const dldp_p* dp, randomGeneratorContext* rgc, mp32number* x)
00047 {
00048         /*
00049          * Note: the private key is randomly selected to be smaller than q
00050          *
00051          * This is the variant of Diffie-Hellman as described in IEEE P1363
00052          */
00053 
00054         mp32bnrnd(&dp->q, rgc, x);
00055 
00056         return 0;
00057 }
00058 
00059 int dldp_pPublic(const dldp_p* dp, const mp32number* x, mp32number* y)
00060 {
00061         /*
00062          * Public key y is computed as g^x mod p
00063          */
00064 
00065         mp32bnpowmod(&dp->p, &dp->g, x, y);
00066 
00067         return 0;
00068 }
00069 
00070 int dldp_pPair(const dldp_p* dp, randomGeneratorContext* rgc, mp32number* x, mp32number* y)
00071 {
00072         /*
00073          * Combination of the two previous functions
00074          */
00075 
00076         mp32bnrnd(&dp->q, rgc, x);
00077         mp32bnpowmod(&dp->p, &dp->g, x, y);
00078 
00079         return 0;
00080 }
00081 
00082 int dldp_pEqual(const dldp_p* a, const dldp_p* b)
00083 {
00084         return mp32eqx(a->p.size, a->p.modl, b->p.size, b->p.modl) &&
00085                 mp32eqx(a->q.size, a->q.modl, b->q.size, b->q.modl) &&
00086                 mp32eqx(a->g.size, a->g.data, b->g.size, b->g.data);
00087 }
00088 
00092 static int dldp_pValidate(const dldp_p* dp, randomGeneratorContext* rgc)
00093         /*@*/
00094 {
00095         register uint32  size = dp->p.size;
00096         register uint32* temp = (uint32*) malloc((8*size+2) * sizeof(*temp));
00097 
00098         if (temp)
00099         {
00100                 /* check that p > 2 and p odd, then run miller-rabin test with t 50 */
00101                 if (mp32even(dp->p.size, dp->p.modl))
00102                 {
00103                         free(temp);
00104                         return 0;
00105                 }
00106 
00107                 if (mp32pmilrab_w(&dp->p, rgc, 50, temp) == 0)
00108                 {
00109                         free(temp);
00110                         return 0;
00111                 }
00112 
00113                 /* check that q > 2 and q odd, then run miller-rabin test with t 50 */
00114                 if (mp32even(dp->q.size, dp->q.modl))
00115                 {
00116                         free(temp);
00117                         return 0;
00118                 }
00119 
00120                 if (mp32pmilrab_w(&dp->q, rgc, 50, temp) == 0)
00121                 {
00122                         free(temp);
00123                         return 0;
00124                 }
00125 
00126                 free(temp);
00127 
00128                 /* check that 1 < g < p */
00129                 if (mp32leone(dp->g.size, dp->g.data))
00130                         return 0;
00131 
00132                 if (mp32gex(dp->g.size, dp->g.data, dp->p.size, dp->p.modl))
00133                         return 0;
00134 
00135                 return 1;
00136         }
00137         return -1;
00138 }
00139 
00140 int dldp_pInit(dldp_p* dp)
00141 {
00142         mp32bzero(&dp->p);
00143         mp32bzero(&dp->q);
00144         mp32nzero(&dp->g);
00145         mp32nzero(&dp->r);
00146         mp32bzero(&dp->n);
00147 
00148         return 0;
00149 }
00150 
00151 int dldp_pFree(dldp_p* dp)
00152 {
00153         /*@-usedef -compdef@*/
00154         mp32bfree(&dp->p);
00155         mp32bfree(&dp->q);
00156         mp32nfree(&dp->g);
00157         mp32nfree(&dp->r);
00158         mp32bfree(&dp->n);
00159         /*@=usedef =compdef@*/
00160 
00161         return 0;
00162 }
00163 
00164 int dldp_pCopy(dldp_p* dst, const dldp_p* src)
00165 {
00166         mp32bcopy(&dst->p, &src->p);
00167         mp32bcopy(&dst->q, &src->q);
00168         mp32ncopy(&dst->r, &src->r);
00169         mp32ncopy(&dst->g, &src->g);
00170         mp32bcopy(&dst->n, &src->n);
00171 
00172         return 0;
00173 }
00174 
00175 int dldp_pgoqMake(dldp_p* dp, randomGeneratorContext* rgc, uint32 psize, uint32 qsize, int cofactor)
00176 {
00177         /*
00178          * Generate parameters as described by IEEE P1363, A.16.1
00179          */
00180 
00181         register uint32* temp = (uint32*) malloc((8*psize+2) * sizeof(*temp));
00182 
00183         if (temp)
00184         {
00185                 /* first generate q */
00186                 /*@-globs@*/
00187                 mp32prnd_w(&dp->q, rgc, qsize, mp32ptrials(qsize << 5), (const mp32number*) 0, temp);
00188                 /*@=globs@*/
00189 
00190                 /* generate p with the appropriate congruences */
00191                 /*@-globs@*/
00192                 mp32prndconone_w(&dp->p, rgc, psize, mp32ptrials(psize << 5), &dp->q, (const mp32number*) 0, &dp->r, cofactor, temp);
00193                 /*@=globs@*/
00194 
00195                 /* clear n */
00196                 mp32bzero(&dp->n);
00197 
00198                 /* clear g */
00199                 mp32nzero(&dp->g);
00200 
00201                 (void) dldp_pgoqGenerator_w(dp, rgc, temp);
00202 
00203                 free(temp);
00204 
00205                 return 0;
00206         }
00207         return -1;
00208 }
00209 
00210 /*@-bounds@*/
00211 int dldp_pgoqMakeSafe(dldp_p* dp, randomGeneratorContext* rgc, uint32 psize)
00212 {
00213         /*
00214          * Generate parameters with a safe prime; p = 2q+1 i.e. r=2
00215          *
00216          */
00217 
00218         register uint32* temp = (uint32*) malloc((8*psize+2) * sizeof(*temp));
00219 
00220         if (temp)
00221         {
00222                 /* generate p */
00223                 /*@-globs@*/
00224                 mp32prndsafe_w(&dp->p, rgc, psize, mp32ptrials(psize << 5), temp);
00225                 /*@=globs@*/
00226 
00227                 /* set q */
00228                 mp32copy(psize, temp, dp->p.modl);
00229                 mp32divtwo(psize, temp);
00230                 mp32bset(&dp->q, psize, temp);
00231 
00232                 /* set r = 2 */
00233                 mp32nsetw(&dp->r, 2);
00234 
00235                 /* clear n */
00236                 mp32bzero(&dp->n);
00237 
00238                 (void) dldp_pgoqGenerator_w(dp, rgc, temp);
00239 
00240                 free(temp);
00241 
00242                 return 0;
00243         }
00244         return -1;
00245 }
00246 /*@=bounds@*/
00247 
00248 int dldp_pgoqGenerator_w(dldp_p* dp, randomGeneratorContext* rgc, uint32* wksp)
00249 {
00250         /*
00251          * Randomly determine a generator over the subgroup with order q
00252          */
00253 
00254         register uint32  size = dp->p.size;
00255 
00256         mp32nfree(&dp->g);
00257         mp32nsize(&dp->g, size);
00258 
00259         while (1)
00260         {
00261                 /* get a random value h (stored into g) */
00262                 mp32brnd_w(&dp->p, rgc, dp->g.data, wksp);
00263 
00264                 /* first compute h^r mod p (stored in g) */
00265                 mp32bpowmod_w(&dp->p, size, dp->g.data, dp->r.size, dp->r.data, dp->g.data, wksp);
00266 
00267                 if (mp32isone(size, dp->g.data))
00268                         continue;
00269 
00270                 return 0;
00271         }
00272         return -1;
00273 }
00274 
00275 int dldp_pgoqGenerator(dldp_p* dp, randomGeneratorContext* rgc)
00276 {
00277         register uint32  size = dp->p.size;
00278         register uint32* temp = (uint32*) malloc((4*size+2) * sizeof(*temp));
00279 
00280         if (temp)
00281         {
00282                 (void) dldp_pgoqGenerator_w(dp, rgc, temp);
00283 
00284                 free(temp);
00285 
00286                 return 0;
00287         }
00288         return -1;
00289 }
00290 
00291 int dldp_pgoqValidate(const dldp_p* dp, randomGeneratorContext* rgc, /*@unused@*/ int cofactor)
00292 {
00293         register int rc = dldp_pValidate(dp, rgc);
00294 
00295         if (rc <= 0)
00296                 return rc;
00297 
00298         /* check that g^q mod p = 1 */
00299 
00300         /* if r != 0, then check that qr+1 = p */
00301 
00302         /* if cofactor, then check that q does not divide (r) */
00303 
00304         return 1;
00305 }
00306 
00307 int dldp_pgonMake(dldp_p* dp, randomGeneratorContext* rgc, uint32 psize, uint32 qsize)
00308 {
00309         /*
00310          * Generate parameters with a prime p such that p = qr+1, with q prime, and r = 2s, with s prime
00311          */
00312 
00313         register uint32* temp = (uint32*) malloc((8*psize+2) * sizeof(*temp));
00314 
00315         if (temp)
00316         {
00317                 /* generate q */
00318                 /*@-globs@*/
00319                 mp32prnd_w(&dp->q, rgc, qsize, mp32ptrials(qsize << 5), (const mp32number*) 0, temp);
00320                 /*@=globs@*/
00321 
00322                 /* generate p with the appropriate congruences */
00323                 /*@-globs@*/
00324                 mp32prndconone_w(&dp->p, rgc, psize, mp32ptrials(psize << 5), &dp->q, (const mp32number*) 0, &dp->r, 2, temp);
00325                 /*@=globs@*/
00326 
00327                 /* set n */
00328                 mp32bsubone(&dp->p, temp);
00329                 mp32bset(&dp->n, psize, temp);
00330 
00331                 (void) dldp_pgonGenerator_w(dp, rgc, temp);
00332 
00333                 free(temp);
00334 
00335                 return 0;
00336         }
00337         return -1;
00338 }
00339 
00340 int dldp_pgonMakeSafe(dldp_p* dp, randomGeneratorContext* rgc, uint32 psize)
00341 {
00342         /*
00343          * Generate parameters with a safe prime; i.e. p = 2q+1, where q is prime
00344          */
00345 
00346         register uint32* temp = (uint32*) malloc((8*psize+2) * sizeof(*temp));
00347 
00348         if (temp)
00349         {
00350                 /* generate safe p */
00351                 /*@-globs@*/
00352                 mp32prndsafe_w(&dp->p, rgc, psize, mp32ptrials(psize << 5), temp);
00353                 /*@=globs@*/
00354 
00355                 /* set n */
00356                 mp32bsubone(&dp->p, temp);
00357                 mp32bset(&dp->n, psize, temp);
00358 
00359                 /* set q */
00360                 mp32copy(psize, temp, dp->p.modl);
00361                 mp32divtwo(psize, temp);
00362                 mp32bset(&dp->q, psize, temp);
00363 
00364                 /* set r = 2 */
00365                 mp32nsetw(&dp->r, 2);
00366 
00367                 (void) dldp_pgonGenerator_w(dp, rgc, temp);
00368 
00369                 free(temp);
00370 
00371                 return 0;
00372         }
00373         return -1;
00374 }
00375 
00376 int dldp_pgonGenerator_w(dldp_p* dp, randomGeneratorContext* rgc, uint32* wksp)
00377 {
00378         register uint32  size = dp->p.size;
00379 
00380         mp32nfree(&dp->g);
00381         mp32nsize(&dp->g, size);
00382 
00383         while (1)
00384         {
00385                 mp32brnd_w(&dp->p, rgc, dp->g.data, wksp);
00386 
00387                 if (mp32istwo(dp->r.size, dp->r.data))
00388                 {
00389                         /*
00390                          * A little math here: the only element in the group which has order 2 is (p-1);
00391                          * the two group elements raised to power two which result in 1 (mod p) are thus (p-1) and 1
00392                          *
00393                          * mp32brnd_w doesn't return 1 or (p-1), so the test where g^2 mod p = 1 can be safely skipped
00394                          */
00395 
00396                         /* check g^q mod p*/
00397                         mp32bpowmod_w(&dp->p, size, dp->g.data, dp->q.size, dp->q.modl, wksp, wksp+size);
00398                         if (mp32isone(size, wksp))
00399                                 continue;
00400                 }
00401                 else
00402                 {
00403                         /* we can either compute g^r, g^2q and g^(qr/2) or
00404                          * we first compute s = r/2, and then compute g^2s, g^2q and g^qs
00405                          *
00406                          * hence we first compute t = g^s
00407                          * then compute t^2 mod p, and test if one
00408                          * then compute t^q mod p, and test if one
00409                          * then compute (g^q mod p)^2 mod p, and test if one
00410                          */
00411 
00412                         /* compute s = r/2 */
00413                         mp32setx(size, wksp, dp->r.size, dp->r.data);
00414                         mp32divtwo(size, wksp);
00415 
00416                         /* compute t = g^s mod p */
00417                         mp32bpowmod_w(&dp->p, size, dp->g.data, size, wksp, wksp+size, wksp+2*size);
00418                         /* compute t^2 mod p = g^2s mod p = g^r mod p*/
00419                         mp32bsqrmod_w(&dp->p, size, wksp+size, wksp+size, wksp+2*size);
00420                         if (mp32isone(size, wksp+size))
00421                                 continue;
00422 
00423                         /* compute t^q mod p = g^qs mod p */
00424                         mp32bpowmod_w(&dp->p, size, wksp, dp->q.size, dp->q.modl, wksp+size, wksp+2*size);
00425                         if (mp32isone(size, wksp+size))
00426                                 continue;
00427 
00428                         /* compute g^2q mod p */
00429                         mp32bpowmod_w(&dp->p, size, dp->g.data, dp->q.size, dp->q.modl, wksp, wksp+size);
00430                         mp32bsqrmod_w(&dp->p, size, wksp, wksp+size, wksp+2*size);
00431                         if (mp32isone(size, wksp+size))
00432                                 continue;
00433                 }
00434 
00435                 return 0;
00436         }
00437 
00438         return -1;
00439 }
00440 
00441 int dldp_pgonGenerator(dldp_p* dp, randomGeneratorContext* rgc)
00442 {
00443         register uint32  psize = dp->p.size;
00444         register uint32* temp = (uint32*) malloc((8*psize+2) * sizeof(*temp));
00445 
00446         if (temp)
00447         {
00448                 (void) dldp_pgonGenerator_w(dp, rgc, temp);
00449 
00450                 free(temp);
00451 
00452                 return 0;
00453         }
00454         return -1;
00455 }
00456 
00457 int dldp_pgonValidate(const dldp_p* dp, randomGeneratorContext* rgc)
00458 {
00459         return dldp_pValidate((const dldp_p*) dp, rgc);
00460 }

Generated on Wed Sep 4 12:49:47 2002 for rpm by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002