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 }