Return to prime.c CVS log

Up to [PGP] / pgp / rsaref / source

Annotation of pgp/rsaref/source/prime.c, revision 1.1

1.1     ! root        1: /* PRIME.C - primality-testing routines
        !             2:  */
        !             3: 
        !             4: /* Copyright (C) RSA Laboratories, a division of RSA Data Security,
        !             5:      Inc., created 1991. All rights reserved.
        !             6:  */
        !             7: 
        !             8: #include "global.h"
        !             9: #include "rsaref.h"
        !            10: #include "r_random.h"
        !            11: #include "nn.h"
        !            12: #include "prime.h"
        !            13: 
        !            14: static unsigned int SMALL_PRIMES[] = { 3, 5, 7, 11 };
        !            15: #define SMALL_PRIME_COUNT 4
        !            16: 
        !            17: static int ProbablePrime PROTO_LIST ((NN_DIGIT *, unsigned int));
        !            18: static int SmallFactor PROTO_LIST ((NN_DIGIT *, unsigned int));
        !            19: static int FermatTest PROTO_LIST ((NN_DIGIT *, unsigned int));
        !            20: 
        !            21: /* Generates a probable prime a between b and c such that a-1 is
        !            22:    divisible by d.
        !            23: 
        !            24:    Lengths: a[digits], b[digits], c[digits], d[digits].
        !            25:    Assumes b < c, digits < MAX_NN_DIGITS.
        !            26:    
        !            27:    Returns RE_NEED_RANDOM if randomStruct not seeded, RE_DATA if
        !            28:    unsuccessful.
        !            29:  */
        !            30: int GeneratePrime (a, b, c, d, digits, randomStruct)
        !            31: NN_DIGIT *a, *b, *c, *d;
        !            32: unsigned int digits;
        !            33: R_RANDOM_STRUCT *randomStruct;
        !            34: {
        !            35:   int status;
        !            36:   unsigned char block[MAX_NN_DIGITS * NN_DIGIT_LEN];
        !            37:   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
        !            38: 
        !            39:   /* Generate random number between b and c.
        !            40:    */
        !            41:   if (status = R_GenerateBytes (block, digits * NN_DIGIT_LEN, randomStruct))
        !            42:     return (status);
        !            43:   NN_Decode (a, digits, block, digits * NN_DIGIT_LEN);
        !            44:   NN_Sub (t, c, b, digits);
        !            45:   NN_ASSIGN_DIGIT (u, 1, digits);
        !            46:   NN_Add (t, t, u, digits);
        !            47:   NN_Mod (a, a, digits, t, digits);
        !            48:   NN_Add (a, a, b, digits);
        !            49: 
        !            50:   /* Adjust so that a-1 is divisible by d.
        !            51:    */
        !            52:   NN_Mod (t, a, digits, d, digits);
        !            53:   NN_Sub (a, a, t, digits);
        !            54:   NN_Add (a, a, u, digits);
        !            55:   if (NN_Cmp (a, b, digits) < 0)
        !            56:     NN_Add (a, a, d, digits);
        !            57:   if (NN_Cmp (a, c, digits) > 0)
        !            58:     NN_Sub (a, a, d, digits);
        !            59: 
        !            60:   /* Search to c in steps of d.
        !            61:    */
        !            62:   NN_Assign (t, c, digits);
        !            63:   NN_Sub (t, t, d, digits);
        !            64: 
        !            65:   while (! ProbablePrime (a, digits)) {
        !            66:     if (NN_Cmp (a, t, digits) > 0)
        !            67:       return (RE_DATA);
        !            68:     NN_Add (a, a, d, digits);
        !            69:   }
        !            70: 
        !            71:   return (0);
        !            72: }
        !            73: 
        !            74: /* Returns nonzero iff a is a probable prime.
        !            75: 
        !            76:    Lengths: a[aDigits].
        !            77:    Assumes aDigits < MAX_NN_DIGITS.
        !            78:  */
        !            79: static int ProbablePrime (a, aDigits)
        !            80: NN_DIGIT *a;
        !            81: unsigned int aDigits;
        !            82: {
        !            83:   return (! SmallFactor (a, aDigits) && FermatTest (a, aDigits));
        !            84: }
        !            85: 
        !            86: /* Returns nonzero iff a has a prime factor in SMALL_PRIMES.
        !            87: 
        !            88:    Lengths: a[aDigits].
        !            89:    Assumes aDigits < MAX_NN_DIGITS.
        !            90:  */
        !            91: static int SmallFactor (a, aDigits)
        !            92: NN_DIGIT *a;
        !            93: unsigned int aDigits;
        !            94: {
        !            95:   int status;
        !            96:   NN_DIGIT t[1];
        !            97:   unsigned int i;
        !            98:   
        !            99:   status = 0;
        !           100:   
        !           101:   for (i = 0; i < SMALL_PRIME_COUNT; i++) {
        !           102:     NN_ASSIGN_DIGIT (t, SMALL_PRIMES[i], 1);
        !           103:     if ((aDigits == 1) && ! NN_Cmp (a, t, 1))
        !           104:       break;
        !           105:     NN_Mod (t, a, aDigits, t, 1);
        !           106:     if (NN_Zero (t, 1)) {
        !           107:       status = 1;
        !           108:       break;
        !           109:     }
        !           110:   }
        !           111:   
        !           112:   /* Zeroize sensitive information.
        !           113:    */
        !           114:   i = 0;
        !           115:   R_memset ((POINTER)t, 0, sizeof (t));
        !           116: 
        !           117:   return (status);
        !           118: }
        !           119: 
        !           120: /* Returns nonzero iff a passes Fermat's test for witness 2.
        !           121:    (All primes pass the test, and nearly all composites fail.)
        !           122:      
        !           123:    Lengths: a[aDigits].
        !           124:    Assumes aDigits < MAX_NN_DIGITS.
        !           125:  */
        !           126: static int FermatTest (a, aDigits)
        !           127: NN_DIGIT *a;
        !           128: unsigned int aDigits;
        !           129: {
        !           130:   int status;
        !           131:   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
        !           132:   
        !           133:   NN_ASSIGN_DIGIT (t, 2, aDigits);
        !           134:   NN_ModExp (u, t, a, aDigits, a, aDigits);
        !           135:   
        !           136:   status = NN_EQUAL (t, u, aDigits);
        !           137:   
        !           138:   /* Zeroize sensitive information.
        !           139:    */
        !           140:   R_memset ((POINTER)u, 0, sizeof (u));
        !           141:   
        !           142:   return (status);
        !           143: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.