Return to prime.c CVS log

Up to [rsaref] / rsaref / source

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

1.1     ! root        1: /* PRIME.C - primality-testing routines
        !             2:  */
        !             3: 
        !             4: /* Copyright (C) 1991-2 RSA Laboratories, a division of RSA Data
        !             5:    Security, Inc. All rights reserved.
        !             6:  */
        !             7: 
        !             8: #include "global.h"
        !             9: #include "rsaref.h"
        !            10: #include "nn.h"
        !            11: #include "prime.h"
        !            12: 
        !            13: static unsigned int SMALL_PRIMES[] = { 3, 5, 7, 11 };
        !            14: #define SMALL_PRIME_COUNT 4
        !            15: 
        !            16: static int RSAPrime PROTO_LIST
        !            17:   ((NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int));
        !            18: static int ProbablePrime PROTO_LIST ((NN_DIGIT *, unsigned int));
        !            19: static int SmallFactor PROTO_LIST ((NN_DIGIT *, unsigned int));
        !            20: static int FermatTest PROTO_LIST ((NN_DIGIT *, unsigned int));
        !            21: static int RelativelyPrime PROTO_LIST
        !            22:   ((NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int));
        !            23: 
        !            24: /* Find a probable prime a between 3*2^(b-2) and 2^b-1, starting at
        !            25:    3*2^(b-2) + (c mod 2^(b-2)), such that gcd (a-1, d) = 1.
        !            26: 
        !            27:    Lengths: a[cDigits], c[cDigits], d[dDigits].
        !            28:    Assumes b > 2, b < cDigits * NN_DIGIT_BITS, d is odd,
        !            29:            cDigits < MAX_NN_DIGITS, dDigits < MAX_NN_DIGITS, and a
        !            30:            probable prime can be found.
        !            31:  */
        !            32: void FindRSAPrime (a, b, c, cDigits, d, dDigits)
        !            33: NN_DIGIT *a, *c, *d;
        !            34: unsigned int b, cDigits, dDigits;
        !            35: {
        !            36:   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS], v[MAX_NN_DIGITS],
        !            37:     w[MAX_NN_DIGITS];
        !            38:   
        !            39:   /* Compute t = 2^(b-2), u = 3*2^(b-2).
        !            40:    */
        !            41:   NN_Assign2Exp (t, b-2, cDigits);
        !            42:   NN_Assign2Exp (u, b-1, cDigits);
        !            43:   NN_Add (u, u, t, cDigits);
        !            44:   
        !            45:   /* Compute v = 3*2^(b-2) + (c mod 2^(b-2)); add one if even.
        !            46:    */
        !            47:   NN_Mod (v, c, cDigits, t, cDigits);
        !            48:   NN_Add (v, v, u, cDigits);
        !            49:   if (NN_EVEN (v, cDigits)) {
        !            50:     NN_ASSIGN_DIGIT (w, 1, cDigits);
        !            51:     NN_Add (v, v, w, cDigits);
        !            52:   }
        !            53:   
        !            54:   /* Compute w = 2, u = 2^b - 2.
        !            55:    */
        !            56:   NN_ASSIGN_DIGIT (w, 2, cDigits);
        !            57:   NN_Sub (u, u, w, cDigits);
        !            58:   NN_Add (u, u, t, cDigits);
        !            59: 
        !            60:   /* Search to 2^b-1 from starting point, then from 3*2^(b-2)+1.
        !            61:    */
        !            62:   while (! RSAPrime (v, cDigits, d, dDigits)) {
        !            63:     if (NN_Cmp (v, u, cDigits) > 0)
        !            64:       NN_Sub (v, v, t, cDigits);
        !            65:     NN_Add (v, v, w, cDigits);
        !            66:   }
        !            67:   
        !            68:   NN_Assign (a, v, cDigits);
        !            69:   
        !            70:   /* Zeroize sensitive information.
        !            71:    */
        !            72:   R_memset ((POINTER)v, 0, sizeof (v));
        !            73: }
        !            74: 
        !            75: /* Returns nonzero iff a is a probable prime and GCD (a-1, b) = 1.
        !            76: 
        !            77:    Lengths: a[aDigits], b[bDigits].
        !            78:    Assumes aDigits < MAX_NN_DIGITS, bDigits < MAX_NN_DIGITS.
        !            79:  */
        !            80: static int RSAPrime (a, aDigits, b, bDigits)
        !            81: NN_DIGIT *a, *b;
        !            82: unsigned int aDigits, bDigits;
        !            83: {
        !            84:   int status;
        !            85:   NN_DIGIT aMinus1[MAX_NN_DIGITS], t[MAX_NN_DIGITS];
        !            86:   
        !            87:   NN_ASSIGN_DIGIT (t, 1, aDigits);
        !            88:   NN_Sub (aMinus1, a, t, aDigits);
        !            89:   
        !            90:   status = ProbablePrime (a, aDigits) &&
        !            91:     RelativelyPrime (aMinus1, aDigits, b, bDigits);
        !            92: 
        !            93:   /* Zeroize sensitive information.
        !            94:    */
        !            95:   R_memset ((POINTER)aMinus1, 0, sizeof (aMinus1));
        !            96:   
        !            97:   return (status);
        !            98: }
        !            99: 
        !           100: /* Returns nonzero iff a is a probable prime.
        !           101: 
        !           102:    Lengths: a[aDigits].
        !           103:    Assumes aDigits < MAX_NN_DIGITS.
        !           104:  */
        !           105: static int ProbablePrime (a, aDigits)
        !           106: NN_DIGIT *a;
        !           107: unsigned int aDigits;
        !           108: {
        !           109:   return (! SmallFactor (a, aDigits) && FermatTest (a, aDigits));
        !           110: }
        !           111: 
        !           112: /* Returns nonzero iff a has a prime factor in SMALL_PRIMES.
        !           113: 
        !           114:    Lengths: a[aDigits].
        !           115:    Assumes aDigits < MAX_NN_DIGITS.
        !           116:  */
        !           117: static int SmallFactor (a, aDigits)
        !           118: NN_DIGIT *a;
        !           119: unsigned int aDigits;
        !           120: {
        !           121:   int status;
        !           122:   NN_DIGIT t[1];
        !           123:   unsigned int i;
        !           124:   
        !           125:   status = 0;
        !           126:   
        !           127:   for (i = 0; i < SMALL_PRIME_COUNT; i++) {
        !           128:     NN_ASSIGN_DIGIT (t, SMALL_PRIMES[i], 1);
        !           129:     NN_Mod (t, a, aDigits, t, 1);
        !           130:     if (NN_Zero (t, 1)) {
        !           131:       status = 1;
        !           132:       break;
        !           133:     }
        !           134:   }
        !           135:   
        !           136:   /* Zeroize sensitive information.
        !           137:    */
        !           138:   i = 0;
        !           139:   R_memset ((POINTER)t, 0, sizeof (t));
        !           140: 
        !           141:   return (status);
        !           142: }
        !           143: 
        !           144: /* Returns nonzero iff a passes Fermat's test for witness 2.
        !           145:    (All primes pass the test, and nearly all composites fail.)
        !           146:      
        !           147:    Lengths: a[aDigits].
        !           148:    Assumes aDigits < MAX_NN_DIGITS.
        !           149:  */
        !           150: static int FermatTest (a, aDigits)
        !           151: NN_DIGIT *a;
        !           152: unsigned int aDigits;
        !           153: {
        !           154:   int status;
        !           155:   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
        !           156:   
        !           157:   NN_ASSIGN_DIGIT (t, 2, aDigits);
        !           158:   NN_ModExp (u, t, a, aDigits, a, aDigits);
        !           159:   
        !           160:   status = NN_EQUAL (t, u, aDigits);
        !           161:   
        !           162:   /* Zeroize sensitive information.
        !           163:    */
        !           164:   R_memset ((POINTER)u, 0, sizeof (u));
        !           165:   
        !           166:   return (status);
        !           167: }
        !           168: 
        !           169: /* Returns nonzero iff a and b are relatively prime.
        !           170: 
        !           171:    Lengths: a[aDigits], b[bDigits].
        !           172:    Assumes aDigits >= bDigits, aDigits < MAX_NN_DIGITS.
        !           173:  */
        !           174: static int RelativelyPrime (a, aDigits, b, bDigits)
        !           175: NN_DIGIT *a, *b;
        !           176: unsigned int aDigits, bDigits;
        !           177: {
        !           178:   int status;
        !           179:   NN_DIGIT t[MAX_NN_DIGITS], u[MAX_NN_DIGITS];
        !           180:   
        !           181:   NN_AssignZero (t, aDigits);
        !           182:   NN_Assign (t, b, bDigits);
        !           183:   NN_Gcd (t, a, t, aDigits);
        !           184:   NN_ASSIGN_DIGIT (u, 1, aDigits);
        !           185: 
        !           186:   status = NN_EQUAL (t, u, aDigits);
        !           187:   
        !           188:   /* Zeroize sensitive information.
        !           189:    */
        !           190:   R_memset ((POINTER)t, 0, sizeof (t));
        !           191:   
        !           192:   return (status);
        !           193: }

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