OLD | NEW |
1 /* This Source Code Form is subject to the terms of the Mozilla Public | 1 /* This Source Code Form is subject to the terms of the Mozilla Public |
2 * License, v. 2.0. If a copy of the MPL was not distributed with this | 2 * License, v. 2.0. If a copy of the MPL was not distributed with this |
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ |
4 | 4 |
5 /* | 5 /* |
6 * PQG parameter generation/verification. Based on FIPS 186-3. | 6 * PQG parameter generation/verification. Based on FIPS 186-3. |
7 */ | 7 */ |
8 #ifdef FREEBL_NO_DEPEND | 8 #ifdef FREEBL_NO_DEPEND |
9 #include "stubs.h" | 9 #include "stubs.h" |
10 #endif | 10 #endif |
(...skipping 476 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
487 */ | 487 */ |
488 #define MAX_ST_SEED_BITS (HASH_LENGTH_MAX*PR_BITS_PER_BYTE) | 488 #define MAX_ST_SEED_BITS (HASH_LENGTH_MAX*PR_BITS_PER_BYTE) |
489 SECStatus | 489 SECStatus |
490 makePrimefromPrimesShaweTaylor( | 490 makePrimefromPrimesShaweTaylor( |
491 HASH_HashType hashtype, /* selected Hashing algorithm */ | 491 HASH_HashType hashtype, /* selected Hashing algorithm */ |
492 unsigned int length, /* input. Length of prime in bits. */ | 492 unsigned int length, /* input. Length of prime in bits. */ |
493 mp_int * c0, /* seed prime */ | 493 mp_int * c0, /* seed prime */ |
494 mp_int * q, /* sub prime, can be 1 */ | 494 mp_int * q, /* sub prime, can be 1 */ |
495 mp_int * prime, /* output. */ | 495 mp_int * prime, /* output. */ |
496 SECItem * prime_seed, /* input/output. */ | 496 SECItem * prime_seed, /* input/output. */ |
497 int * prime_gen_counter) /* input/output. */ | 497 unsigned int *prime_gen_counter) /* input/output. */ |
498 { | 498 { |
499 mp_int c; | 499 mp_int c; |
500 mp_int c0_2; | 500 mp_int c0_2; |
501 mp_int t; | 501 mp_int t; |
502 mp_int a; | 502 mp_int a; |
503 mp_int z; | 503 mp_int z; |
504 mp_int two_length_minus_1; | 504 mp_int two_length_minus_1; |
505 SECStatus rv = SECFailure; | 505 SECStatus rv = SECFailure; |
506 int hashlen = HASH_ResultLen(hashtype); | 506 int hashlen = HASH_ResultLen(hashtype); |
507 int outlen = hashlen*PR_BITS_PER_BYTE; | 507 int outlen = hashlen*PR_BITS_PER_BYTE; |
(...skipping 212 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
720 ** | 720 ** |
721 ** This generates a provable prime from a seed | 721 ** This generates a provable prime from a seed |
722 */ | 722 */ |
723 SECStatus | 723 SECStatus |
724 makePrimefromSeedShaweTaylor( | 724 makePrimefromSeedShaweTaylor( |
725 HASH_HashType hashtype, /* selected Hashing algorithm */ | 725 HASH_HashType hashtype, /* selected Hashing algorithm */ |
726 unsigned int length, /* input. Length of prime in bits. */ | 726 unsigned int length, /* input. Length of prime in bits. */ |
727 const SECItem * input_seed, /* input. */ | 727 const SECItem * input_seed, /* input. */ |
728 mp_int * prime, /* output. */ | 728 mp_int * prime, /* output. */ |
729 SECItem * prime_seed, /* output. */ | 729 SECItem * prime_seed, /* output. */ |
730 int * prime_gen_counter) /* output. */ | 730 unsigned int *prime_gen_counter) /* output. */ |
731 { | 731 { |
732 mp_int c; | 732 mp_int c; |
733 mp_int c0; | 733 mp_int c0; |
734 mp_int one; | 734 mp_int one; |
735 SECStatus rv = SECFailure; | 735 SECStatus rv = SECFailure; |
736 int hashlen = HASH_ResultLen(hashtype); | 736 int hashlen = HASH_ResultLen(hashtype); |
737 int outlen = hashlen*PR_BITS_PER_BYTE; | 737 int outlen = hashlen*PR_BITS_PER_BYTE; |
738 int offset; | 738 int offset; |
739 unsigned char bit, mask; | 739 unsigned char bit, mask; |
740 unsigned char x[HASH_LENGTH_MAX*2]; | 740 unsigned char x[HASH_LENGTH_MAX*2]; |
(...skipping 134 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
875 * Find a Q and algorithm from Seed. | 875 * Find a Q and algorithm from Seed. |
876 */ | 876 */ |
877 static SECStatus | 877 static SECStatus |
878 findQfromSeed( | 878 findQfromSeed( |
879 unsigned int L, /* input. Length of p in bits. */ | 879 unsigned int L, /* input. Length of p in bits. */ |
880 unsigned int N, /* input. Length of q in bits. */ | 880 unsigned int N, /* input. Length of q in bits. */ |
881 unsigned int g, /* input. Length of seed in bits. */ | 881 unsigned int g, /* input. Length of seed in bits. */ |
882 const SECItem * seed, /* input. */ | 882 const SECItem * seed, /* input. */ |
883 mp_int * Q, /* input. */ | 883 mp_int * Q, /* input. */ |
884 mp_int * Q_, /* output. */ | 884 mp_int * Q_, /* output. */ |
885 int * qseed_len, /* output */ | 885 unsigned int *qseed_len, /* output */ |
886 HASH_HashType *hashtypePtr, /* output. Hash uses */ | 886 HASH_HashType *hashtypePtr, /* output. Hash uses */ |
887 pqgGenType *typePtr) /* output. Generation Type used */ | 887 pqgGenType *typePtr) /* output. Generation Type used */ |
888 { | 888 { |
889 HASH_HashType hashtype; | 889 HASH_HashType hashtype; |
890 SECItem firstseed = { 0, 0, 0 }; | 890 SECItem firstseed = { 0, 0, 0 }; |
891 SECItem qseed = { 0, 0, 0 }; | 891 SECItem qseed = { 0, 0, 0 }; |
892 SECStatus rv; | 892 SECStatus rv; |
893 | 893 |
894 *qseed_len = 0; /* only set if FIPS186_3_ST_TYPE */ | 894 *qseed_len = 0; /* only set if FIPS186_3_ST_TYPE */ |
895 | 895 |
(...skipping 34 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
930 return SECSuccess; | 930 return SECSuccess; |
931 } | 931 } |
932 } | 932 } |
933 /* | 933 /* |
934 * OK finally try FIPS186_3 Shawe-Taylor | 934 * OK finally try FIPS186_3 Shawe-Taylor |
935 */ | 935 */ |
936 firstseed = *seed; | 936 firstseed = *seed; |
937 firstseed.len = seed->len/3; | 937 firstseed.len = seed->len/3; |
938 for (hashtype = getFirstHash(L,N); hashtype != HASH_AlgTOTAL; | 938 for (hashtype = getFirstHash(L,N); hashtype != HASH_AlgTOTAL; |
939 hashtype=getNextHash(hashtype)) { | 939 hashtype=getNextHash(hashtype)) { |
940 » int count; | 940 » unsigned int count; |
941 | 941 |
942 rv = makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, Q_, | 942 rv = makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, Q_, |
943 &qseed, &count); | 943 &qseed, &count); |
944 if (rv != SECSuccess) { | 944 if (rv != SECSuccess) { |
945 continue; | 945 continue; |
946 } | 946 } |
947 if (mp_cmp(Q,Q_) == 0) { | 947 if (mp_cmp(Q,Q_) == 0) { |
948 /* check qseed as well... */ | 948 /* check qseed as well... */ |
949 int offset = seed->len - qseed.len; | 949 int offset = seed->len - qseed.len; |
950 if ((offset < 0) || | 950 if ((offset < 0) || |
(...skipping 185 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1136 const SECItem *seed, /* input. */ | 1136 const SECItem *seed, /* input. */ |
1137 unsigned char index, /* input. */ | 1137 unsigned char index, /* input. */ |
1138 mp_int *G) /* input/output */ | 1138 mp_int *G) /* input/output */ |
1139 { | 1139 { |
1140 mp_int e, pm1, W; | 1140 mp_int e, pm1, W; |
1141 unsigned int count; | 1141 unsigned int count; |
1142 unsigned char data[HASH_LENGTH_MAX]; | 1142 unsigned char data[HASH_LENGTH_MAX]; |
1143 unsigned int len; | 1143 unsigned int len; |
1144 mp_err err = MP_OKAY; | 1144 mp_err err = MP_OKAY; |
1145 SECStatus rv = SECSuccess; | 1145 SECStatus rv = SECSuccess; |
1146 const SECHashObject *hashobj; | 1146 const SECHashObject *hashobj = NULL; |
1147 void *hashcx = NULL; | 1147 void *hashcx = NULL; |
1148 | 1148 |
1149 MP_DIGITS(&e) = 0; | 1149 MP_DIGITS(&e) = 0; |
1150 MP_DIGITS(&pm1) = 0; | 1150 MP_DIGITS(&pm1) = 0; |
1151 MP_DIGITS(&W) = 0; | 1151 MP_DIGITS(&W) = 0; |
1152 CHECK_MPI_OK( mp_init(&e) ); | 1152 CHECK_MPI_OK( mp_init(&e) ); |
1153 CHECK_MPI_OK( mp_init(&pm1) ); | 1153 CHECK_MPI_OK( mp_init(&pm1) ); |
1154 CHECK_MPI_OK( mp_init(&W) ); | 1154 CHECK_MPI_OK( mp_init(&W) ); |
1155 | 1155 |
1156 /* initialize our hash stuff */ | 1156 /* initialize our hash stuff */ |
(...skipping 65 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1222 /* This code uses labels and gotos, so that it can follow the numbered | 1222 /* This code uses labels and gotos, so that it can follow the numbered |
1223 ** steps in the algorithms from FIPS 186-3 appendix A.1.1.2 very closely, | 1223 ** steps in the algorithms from FIPS 186-3 appendix A.1.1.2 very closely, |
1224 ** and so that the correctness of this code can be easily verified. | 1224 ** and so that the correctness of this code can be easily verified. |
1225 ** So, please forgive the ugly c code. | 1225 ** So, please forgive the ugly c code. |
1226 **/ | 1226 **/ |
1227 static SECStatus | 1227 static SECStatus |
1228 pqg_ParamGen(unsigned int L, unsigned int N, pqgGenType type, | 1228 pqg_ParamGen(unsigned int L, unsigned int N, pqgGenType type, |
1229 unsigned int seedBytes, PQGParams **pParams, PQGVerify **pVfy) | 1229 unsigned int seedBytes, PQGParams **pParams, PQGVerify **pVfy) |
1230 { | 1230 { |
1231 unsigned int n; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ | 1231 unsigned int n; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ |
1232 unsigned int b; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ | |
1233 unsigned int seedlen; /* Per FIPS 186-3 app A.1.1.2 (was 'g' 186-1)*/ | 1232 unsigned int seedlen; /* Per FIPS 186-3 app A.1.1.2 (was 'g' 186-1)*/ |
1234 unsigned int counter; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ | 1233 unsigned int counter; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ |
1235 unsigned int offset; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ | 1234 unsigned int offset; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ |
1236 unsigned int outlen; /* Per FIPS 186-3, appendix A.1.1.2. */ | 1235 unsigned int outlen; /* Per FIPS 186-3, appendix A.1.1.2. */ |
1237 unsigned int maxCount; | 1236 unsigned int maxCount; |
1238 HASH_HashType hashtype; | 1237 HASH_HashType hashtype; |
1239 SECItem *seed; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ | 1238 SECItem *seed; /* Per FIPS 186, app 2.2. 186-3 app A.1.1.2 */ |
1240 PLArenaPool *arena = NULL; | 1239 PLArenaPool *arena = NULL; |
1241 PQGParams *params = NULL; | 1240 PQGParams *params = NULL; |
1242 PQGVerify *verify = NULL; | 1241 PQGVerify *verify = NULL; |
(...skipping 59 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1302 CHECK_MPI_OK( mp_init(&p0) ); | 1301 CHECK_MPI_OK( mp_init(&p0) ); |
1303 | 1302 |
1304 /* Select Hash and Compute lengths. */ | 1303 /* Select Hash and Compute lengths. */ |
1305 /* getFirstHash gives us the smallest acceptable hash for this key | 1304 /* getFirstHash gives us the smallest acceptable hash for this key |
1306 * strength */ | 1305 * strength */ |
1307 hashtype = getFirstHash(L,N); | 1306 hashtype = getFirstHash(L,N); |
1308 outlen = HASH_ResultLen(hashtype)*PR_BITS_PER_BYTE; | 1307 outlen = HASH_ResultLen(hashtype)*PR_BITS_PER_BYTE; |
1309 | 1308 |
1310 /* Step 3: n = Ceil(L/outlen)-1; (same as n = Floor((L-1)/outlen)) */ | 1309 /* Step 3: n = Ceil(L/outlen)-1; (same as n = Floor((L-1)/outlen)) */ |
1311 n = (L - 1) / outlen; | 1310 n = (L - 1) / outlen; |
1312 /* Step 4: b = L -1 - (n*outlen); (same as n = (L-1) mod outlen) */ | 1311 /* Step 4: (skipped since we don't use b): b = L -1 - (n*outlen); */ |
1313 b = (L - 1) % outlen; | |
1314 seedlen = seedBytes * PR_BITS_PER_BYTE; /* bits in seed */ | 1312 seedlen = seedBytes * PR_BITS_PER_BYTE; /* bits in seed */ |
1315 step_5: | 1313 step_5: |
1316 /* ****************************************************************** | 1314 /* ****************************************************************** |
1317 ** Step 5. (Step 1 in 186-1) | 1315 ** Step 5. (Step 1 in 186-1) |
1318 ** "Choose an abitrary sequence of at least N bits and call it SEED. | 1316 ** "Choose an abitrary sequence of at least N bits and call it SEED. |
1319 ** Let g be the length of SEED in bits." | 1317 ** Let g be the length of SEED in bits." |
1320 */ | 1318 */ |
1321 if (++iterations > MAX_ITERATIONS) { /* give up after a while */ | 1319 if (++iterations > MAX_ITERATIONS) { /* give up after a while */ |
1322 PORT_SetError(SEC_ERROR_NEED_RANDOM); | 1320 PORT_SetError(SEC_ERROR_NEED_RANDOM); |
1323 goto cleanup; | 1321 goto cleanup; |
(...skipping 17 matching lines...) Expand all Loading... |
1341 ** | 1339 ** |
1342 ** If using Shawe-Taylor, We do the entire A.1.2.1.2 setps in the block | 1340 ** If using Shawe-Taylor, We do the entire A.1.2.1.2 setps in the block |
1343 ** FIPS186_3_ST_TYPE. | 1341 ** FIPS186_3_ST_TYPE. |
1344 */ | 1342 */ |
1345 if (type == FIPS186_1_TYPE) { | 1343 if (type == FIPS186_1_TYPE) { |
1346 CHECK_SEC_OK( makeQfromSeed(seedlen, seed, &Q) ); | 1344 CHECK_SEC_OK( makeQfromSeed(seedlen, seed, &Q) ); |
1347 } else if (type == FIPS186_3_TYPE) { | 1345 } else if (type == FIPS186_3_TYPE) { |
1348 CHECK_SEC_OK( makeQ2fromSeed(hashtype, N, seed, &Q) ); | 1346 CHECK_SEC_OK( makeQ2fromSeed(hashtype, N, seed, &Q) ); |
1349 } else { | 1347 } else { |
1350 /* FIPS186_3_ST_TYPE */ | 1348 /* FIPS186_3_ST_TYPE */ |
1351 » int qgen_counter, pgen_counter; | 1349 » unsigned int qgen_counter, pgen_counter; |
1352 | 1350 |
1353 /* Step 1 (L,N) already checked for acceptability */ | 1351 /* Step 1 (L,N) already checked for acceptability */ |
1354 | 1352 |
1355 firstseed = *seed; | 1353 firstseed = *seed; |
1356 qgen_counter = 0; | 1354 qgen_counter = 0; |
1357 /* Step 2. Use N and firstseed to generate random prime q | 1355 /* Step 2. Use N and firstseed to generate random prime q |
1358 * using Apendix C.6 */ | 1356 * using Apendix C.6 */ |
1359 CHECK_SEC_OK( makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, &Q, | 1357 CHECK_SEC_OK( makePrimefromSeedShaweTaylor(hashtype, N, &firstseed, &Q, |
1360 &qseed, &qgen_counter) ); | 1358 &qseed, &qgen_counter) ); |
1361 /* Step 3. Use floor(L/2+1) and qseed to generate random prime p0 | 1359 /* Step 3. Use floor(L/2+1) and qseed to generate random prime p0 |
(...skipping 220 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1582 SECStatus | 1580 SECStatus |
1583 PQG_VerifyParams(const PQGParams *params, | 1581 PQG_VerifyParams(const PQGParams *params, |
1584 const PQGVerify *vfy, SECStatus *result) | 1582 const PQGVerify *vfy, SECStatus *result) |
1585 { | 1583 { |
1586 SECStatus rv = SECSuccess; | 1584 SECStatus rv = SECSuccess; |
1587 unsigned int g, n, L, N, offset, outlen; | 1585 unsigned int g, n, L, N, offset, outlen; |
1588 mp_int p0, P, Q, G, P_, Q_, G_, r, h; | 1586 mp_int p0, P, Q, G, P_, Q_, G_, r, h; |
1589 mp_err err = MP_OKAY; | 1587 mp_err err = MP_OKAY; |
1590 int j; | 1588 int j; |
1591 unsigned int counter_max = 0; /* handle legacy L < 1024 */ | 1589 unsigned int counter_max = 0; /* handle legacy L < 1024 */ |
1592 int qseed_len; | 1590 unsigned int qseed_len; |
1593 SECItem pseed_ = {0, 0, 0}; | 1591 SECItem pseed_ = {0, 0, 0}; |
1594 HASH_HashType hashtype; | 1592 HASH_HashType hashtype; |
1595 pqgGenType type; | 1593 pqgGenType type; |
1596 | 1594 |
1597 #define CHECKPARAM(cond) \ | 1595 #define CHECKPARAM(cond) \ |
1598 if (!(cond)) { \ | 1596 if (!(cond)) { \ |
1599 *result = SECFailure; \ | 1597 *result = SECFailure; \ |
1600 goto cleanup; \ | 1598 goto cleanup; \ |
1601 } | 1599 } |
1602 if (!params || !vfy || !result) { | 1600 if (!params || !vfy || !result) { |
(...skipping 72 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1675 CHECKPARAM( g >= N && g < counter_max/2 ); | 1673 CHECKPARAM( g >= N && g < counter_max/2 ); |
1676 /* 9. Q generated from SEED matches Q in PQGParams. */ | 1674 /* 9. Q generated from SEED matches Q in PQGParams. */ |
1677 /* This function checks all possible hash and generation types to | 1675 /* This function checks all possible hash and generation types to |
1678 * find a Q_ which matches Q. */ | 1676 * find a Q_ which matches Q. */ |
1679 CHECKPARAM( findQfromSeed(L, N, g, &vfy->seed, &Q, &Q_, &qseed_len, | 1677 CHECKPARAM( findQfromSeed(L, N, g, &vfy->seed, &Q, &Q_, &qseed_len, |
1680 &hashtype, &type) == SECSuccess ); | 1678 &hashtype, &type) == SECSuccess ); |
1681 CHECKPARAM( mp_cmp(&Q, &Q_) == 0 ); | 1679 CHECKPARAM( mp_cmp(&Q, &Q_) == 0 ); |
1682 if (type == FIPS186_3_ST_TYPE) { | 1680 if (type == FIPS186_3_ST_TYPE) { |
1683 SECItem qseed = { 0, 0, 0 }; | 1681 SECItem qseed = { 0, 0, 0 }; |
1684 SECItem pseed = { 0, 0, 0 }; | 1682 SECItem pseed = { 0, 0, 0 }; |
1685 » int first_seed_len; | 1683 » unsigned int first_seed_len; |
1686 » int pgen_counter = 0; | 1684 » unsigned int pgen_counter = 0; |
1687 | 1685 |
1688 /* extract pseed and qseed from domain_parameter_seed, which is | 1686 /* extract pseed and qseed from domain_parameter_seed, which is |
1689 * first_seed || pseed || qseed. qseed is first_seed + small_integer | 1687 * first_seed || pseed || qseed. qseed is first_seed + small_integer |
1690 * pseed is qseed + small_integer. This means most of the time | 1688 * pseed is qseed + small_integer. This means most of the time |
1691 * first_seed.len == qseed.len == pseed.len. Rarely qseed.len and/or | 1689 * first_seed.len == qseed.len == pseed.len. Rarely qseed.len and/or |
1692 * pseed.len will be one greater than first_seed.len, so we can | 1690 * pseed.len will be one greater than first_seed.len, so we can |
1693 * depend on the fact that | 1691 * depend on the fact that |
1694 * first_seed.len = floor(domain_parameter_seed.len/3). | 1692 * first_seed.len = floor(domain_parameter_seed.len/3). |
1695 * findQfromSeed returned qseed.len, so we can calculate pseed.len as | 1693 * findQfromSeed returned qseed.len, so we can calculate pseed.len as |
1696 * pseed.len = domain_parameter_seed.len - first_seed.len - qseed.len | 1694 * pseed.len = domain_parameter_seed.len - first_seed.len - qseed.len |
(...skipping 141 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1838 if (vfy == NULL) | 1836 if (vfy == NULL) |
1839 return; | 1837 return; |
1840 if (vfy->arena != NULL) { | 1838 if (vfy->arena != NULL) { |
1841 PORT_FreeArena(vfy->arena, PR_FALSE); /* don't zero it */ | 1839 PORT_FreeArena(vfy->arena, PR_FALSE); /* don't zero it */ |
1842 } else { | 1840 } else { |
1843 SECITEM_FreeItem(&vfy->seed, PR_FALSE); /* don't free seed */ | 1841 SECITEM_FreeItem(&vfy->seed, PR_FALSE); /* don't free seed */ |
1844 SECITEM_FreeItem(&vfy->h, PR_FALSE); /* don't free h */ | 1842 SECITEM_FreeItem(&vfy->h, PR_FALSE); /* don't free h */ |
1845 PORT_Free(vfy); | 1843 PORT_Free(vfy); |
1846 } | 1844 } |
1847 } | 1845 } |
OLD | NEW |