Botan  1.11.15
src/lib/math/ec_gfp/curve_nistp.cpp
Go to the documentation of this file.
00001 /*
00002 * NIST curve reduction
00003 * (C) 2014,2015 Jack Lloyd
00004 *
00005 * Botan is released under the Simplified BSD License (see license.txt)
00006 */
00007 
00008 #include <botan/internal/curve_nistp.h>
00009 #include <botan/internal/mp_core.h>
00010 
00011 namespace Botan {
00012 
00013 void CurveGFp_NIST::curve_mul(BigInt& z, const BigInt& x, const BigInt& y,
00014                               secure_vector<word>& ws) const
00015    {
00016    if(x.is_zero() || y.is_zero())
00017       {
00018       z = 0;
00019       return;
00020       }
00021 
00022    const size_t p_words = get_p_words();
00023    const size_t output_size = 2*p_words + 1;
00024    ws.resize(2*(p_words+2));
00025 
00026    z.grow_to(output_size);
00027    z.clear();
00028 
00029    bigint_mul(z.mutable_data(), output_size, &ws[0],
00030               x.data(), x.size(), x.sig_words(),
00031               y.data(), y.size(), y.sig_words());
00032 
00033    this->redc(z, ws);
00034    }
00035 
00036 void CurveGFp_NIST::curve_sqr(BigInt& z, const BigInt& x,
00037                               secure_vector<word>& ws) const
00038    {
00039    if(x.is_zero())
00040       {
00041       z = 0;
00042       return;
00043       }
00044 
00045    const size_t p_words = get_p_words();
00046    const size_t output_size = 2*p_words + 1;
00047 
00048    ws.resize(2*(p_words+2));
00049 
00050    z.grow_to(output_size);
00051    z.clear();
00052 
00053    bigint_sqr(z.mutable_data(), output_size, &ws[0],
00054               x.data(), x.size(), x.sig_words());
00055 
00056    this->redc(z, ws);
00057    }
00058 
00059 //static
00060 const BigInt& CurveGFp_P521::prime()
00061    {
00062    static const BigInt p521("0x1FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
00063                                "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF");
00064 
00065    return p521;
00066    }
00067 
00068 void CurveGFp_P521::redc(BigInt& x, secure_vector<word>& ws) const
00069    {
00070    const size_t p_words = get_p_words();
00071 
00072    const size_t shift_words = 521 / MP_WORD_BITS,
00073                 shift_bits  = 521 % MP_WORD_BITS;
00074 
00075    const size_t x_sw = x.sig_words();
00076 
00077    if(x_sw < p_words)
00078       return; // already smaller
00079 
00080    if(ws.size() < p_words + 1)
00081       ws.resize(p_words + 1);
00082 
00083    clear_mem(&ws[0], ws.size());
00084    bigint_shr2(&ws[0], x.data(), x_sw, shift_words, shift_bits);
00085 
00086    x.mask_bits(521);
00087 
00088    bigint_add3(x.mutable_data(), x.data(), p_words, &ws[0], p_words);
00089 
00090    normalize(x, ws, max_redc_subtractions());
00091    }
00092 
00093 #if defined(BOTAN_HAS_CURVEGFP_NISTP_M32)
00094 
00095 namespace {
00096 
00097 /**
00098 * Treating this MPI as a sequence of 32-bit words in big-endian
00099 * order, return word i (or 0 if out of range)
00100 */
00101 inline u32bit get_u32bit(const BigInt& x, size_t i)
00102    {
00103 #if (BOTAN_MP_WORD_BITS == 32)
00104    return x.word_at(i);
00105 #elif (BOTAN_MP_WORD_BITS == 64)
00106    return (x.word_at(i/2) >> ((i % 2)*32));
00107 #else
00108   #error "Not implemented"
00109 #endif
00110    }
00111 
00112 /**
00113 * Treating this MPI as a sequence of 32-bit words in big-endian
00114 * order, set word i to the value x
00115 */
00116 inline void set_u32bit(BigInt& x, size_t i, u32bit v)
00117    {
00118 #if (BOTAN_MP_WORD_BITS == 32)
00119    x.set_word_at(i, v);
00120 #elif (BOTAN_MP_WORD_BITS == 64)
00121    const word shift_32 = (i % 2) * 32;
00122    const word w = (x.word_at(i/2) & (static_cast<word>(0xFFFFFFFF) << (32-shift_32))) | (static_cast<word>(v) << shift_32);
00123    x.set_word_at(i/2, w);
00124 #else
00125   #error "Not implemented"
00126 #endif
00127    }
00128 
00129 }
00130 
00131 //static
00132 const BigInt& CurveGFp_P192::prime()
00133    {
00134    static const BigInt p192("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF");
00135    return p192;
00136    }
00137 
00138 void CurveGFp_P192::redc(BigInt& x, secure_vector<word>& ws) const
00139    {
00140    const u32bit X6 = get_u32bit(x, 6);
00141    const u32bit X7 = get_u32bit(x, 7);
00142    const u32bit X8 = get_u32bit(x, 8);
00143    const u32bit X9 = get_u32bit(x, 9);
00144    const u32bit X10 = get_u32bit(x, 10);
00145    const u32bit X11 = get_u32bit(x, 11);
00146 
00147    x.mask_bits(192);
00148 
00149    u64bit S = 0;
00150 
00151    S += get_u32bit(x, 0);
00152    S += X6;
00153    S += X10;
00154    set_u32bit(x, 0, S);
00155    S >>= 32;
00156 
00157    S += get_u32bit(x, 1);
00158    S += X7;
00159    S += X11;
00160    set_u32bit(x, 1, S);
00161    S >>= 32;
00162 
00163    S += get_u32bit(x, 2);
00164    S += X6;
00165    S += X8;
00166    S += X10;
00167    set_u32bit(x, 2, S);
00168    S >>= 32;
00169 
00170    S += get_u32bit(x, 3);
00171    S += X7;
00172    S += X9;
00173    S += X11;
00174    set_u32bit(x, 3, S);
00175    S >>= 32;
00176 
00177    S += get_u32bit(x, 4);
00178    S += X8;
00179    S += X10;
00180    set_u32bit(x, 4, S);
00181    S >>= 32;
00182 
00183    S += get_u32bit(x, 5);
00184    S += X9;
00185    S += X11;
00186    set_u32bit(x, 5, S);
00187    S >>= 32;
00188 
00189    set_u32bit(x, 6, S);
00190 
00191    // No underflow possible
00192 
00193    normalize(x, ws, max_redc_subtractions());
00194    }
00195 
00196 //static
00197 const BigInt& CurveGFp_P224::prime()
00198    {
00199    static const BigInt p224("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001");
00200    return p224;
00201    }
00202 
00203 void CurveGFp_P224::redc(BigInt& x, secure_vector<word>& ws) const
00204    {
00205    const u32bit X7 = get_u32bit(x, 7);
00206    const u32bit X8 = get_u32bit(x, 8);
00207    const u32bit X9 = get_u32bit(x, 9);
00208    const u32bit X10 = get_u32bit(x, 10);
00209    const u32bit X11 = get_u32bit(x, 11);
00210    const u32bit X12 = get_u32bit(x, 12);
00211    const u32bit X13 = get_u32bit(x, 13);
00212 
00213    x.mask_bits(224);
00214 
00215    // One full copy of P224 is added, so the result is always positive
00216 
00217    int64_t S = 0;
00218 
00219    S += get_u32bit(x, 0);
00220    S += 1;
00221    S -= X7;
00222    S -= X11;
00223    set_u32bit(x, 0, S);
00224    S >>= 32;
00225 
00226    S += get_u32bit(x, 1);
00227    S -= X8;
00228    S -= X12;
00229    set_u32bit(x, 1, S);
00230    S >>= 32;
00231 
00232    S += get_u32bit(x, 2);
00233    S -= X9;
00234    S -= X13;
00235    set_u32bit(x, 2, S);
00236    S >>= 32;
00237 
00238    S += get_u32bit(x, 3);
00239    S += 0xFFFFFFFF;
00240    S += X7;
00241    S += X11;
00242    S -= X10;
00243    set_u32bit(x, 3, S);
00244    S >>= 32;
00245 
00246    S += get_u32bit(x, 4);
00247    S += 0xFFFFFFFF;
00248    S += X8;
00249    S += X12;
00250    S -= X11;
00251    set_u32bit(x, 4, S);
00252    S >>= 32;
00253 
00254    S += get_u32bit(x, 5);
00255    S += 0xFFFFFFFF;
00256    S += X9;
00257    S += X13;
00258    S -= X12;
00259    set_u32bit(x, 5, S);
00260    S >>= 32;
00261 
00262    S += get_u32bit(x, 6);
00263    S += 0xFFFFFFFF;
00264    S += X10;
00265    S -= X13;
00266    set_u32bit(x, 6, S);
00267    S >>= 32;
00268    set_u32bit(x, 7, S);
00269 
00270    BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
00271 
00272    normalize(x, ws, max_redc_subtractions());
00273    }
00274 
00275 //static
00276 const BigInt& CurveGFp_P256::prime()
00277    {
00278    static const BigInt p256("0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF");
00279    return p256;
00280    }
00281 
00282 void CurveGFp_P256::redc(BigInt& x, secure_vector<word>& ws) const
00283    {
00284    const u32bit X8 = get_u32bit(x, 8);
00285    const u32bit X9 = get_u32bit(x, 9);
00286    const u32bit X10 = get_u32bit(x, 10);
00287    const u32bit X11 = get_u32bit(x, 11);
00288    const u32bit X12 = get_u32bit(x, 12);
00289    const u32bit X13 = get_u32bit(x, 13);
00290    const u32bit X14 = get_u32bit(x, 14);
00291    const u32bit X15 = get_u32bit(x, 15);
00292 
00293    x.mask_bits(256);
00294 
00295    int64_t S = 0;
00296 
00297    // Adds 6 * P-256 to prevent underflow
00298 
00299    S = get_u32bit(x, 0);
00300    S += 0xFFFFFFFA;
00301    S += X8;
00302    S += X9;
00303    S -= X11;
00304    S -= X12;
00305    S -= X13;
00306    S -= X14;
00307    set_u32bit(x, 0, S);
00308    S >>= 32;
00309 
00310    S += get_u32bit(x, 1);
00311    S += 0xFFFFFFFF;
00312    S += X9;
00313    S += X10;
00314    S -= X12;
00315    S -= X13;
00316    S -= X14;
00317    S -= X15;
00318    set_u32bit(x, 1, S);
00319    S >>= 32;
00320 
00321    S += get_u32bit(x, 2);
00322    S += 0xFFFFFFFF;
00323    S += X10;
00324    S += X11;
00325    S -= X13;
00326    S -= X14;
00327    S -= X15;
00328    set_u32bit(x, 2, S);
00329    S >>= 32;
00330 
00331    S += get_u32bit(x, 3);
00332    S += 5;
00333    S += X11;
00334    S += X11;
00335    S += X12;
00336    S += X12;
00337    S += X13;
00338    S -= X15;
00339    S -= X8;
00340    S -= X9;
00341    set_u32bit(x, 3, S);
00342    S >>= 32;
00343 
00344    S += get_u32bit(x, 4);
00345    S += X12;
00346    S += X12;
00347    S += X13;
00348    S += X13;
00349    S += X14;
00350    S -= X9;
00351    S -= X10;
00352    set_u32bit(x, 4, S);
00353    S >>= 32;
00354 
00355    S += get_u32bit(x, 5);
00356    S += X13;
00357    S += X13;
00358    S += X14;
00359    S += X14;
00360    S += X15;
00361    S -= X10;
00362    S -= X11;
00363    set_u32bit(x, 5, S);
00364    S >>= 32;
00365 
00366    S += get_u32bit(x, 6);
00367    S += 6;
00368    S += X14;
00369    S += X14;
00370    S += X15;
00371    S += X15;
00372    S += X14;
00373    S += X13;
00374    S -= X8;
00375    S -= X9;
00376    set_u32bit(x, 6, S);
00377    S >>= 32;
00378 
00379    S += get_u32bit(x, 7);
00380    S += 0xFFFFFFFA;
00381    S += X15;
00382    S += X15;
00383    S += X15;
00384    S += X8;
00385    S -= X10;
00386    S -= X11;
00387    S -= X12;
00388    S -= X13;
00389    set_u32bit(x, 7, S);
00390    S >>= 32;
00391 
00392    S += 5;
00393    set_u32bit(x, 8, S);
00394 
00395    BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
00396 
00397    if(S >= 2)
00398       {
00399       BOTAN_ASSERT(S <= 10, "Expected overflow");
00400       static const BigInt P256_mults[9] = {
00401          2*get_p(),
00402          3*get_p(),
00403          4*get_p(),
00404          5*get_p(),
00405          6*get_p(),
00406          7*get_p(),
00407          8*get_p(),
00408          9*get_p(),
00409          10*get_p()
00410       };
00411       x -= P256_mults[S - 2];
00412       }
00413 
00414    normalize(x, ws, max_redc_subtractions());
00415    }
00416 
00417 //static
00418 const BigInt& CurveGFp_P384::prime()
00419    {
00420    static const BigInt p384("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF");
00421    return p384;
00422    }
00423 
00424 void CurveGFp_P384::redc(BigInt& x, secure_vector<word>& ws) const
00425    {
00426    const u32bit X12 = get_u32bit(x, 12);
00427    const u32bit X13 = get_u32bit(x, 13);
00428    const u32bit X14 = get_u32bit(x, 14);
00429    const u32bit X15 = get_u32bit(x, 15);
00430    const u32bit X16 = get_u32bit(x, 16);
00431    const u32bit X17 = get_u32bit(x, 17);
00432    const u32bit X18 = get_u32bit(x, 18);
00433    const u32bit X19 = get_u32bit(x, 19);
00434    const u32bit X20 = get_u32bit(x, 20);
00435    const u32bit X21 = get_u32bit(x, 21);
00436    const u32bit X22 = get_u32bit(x, 22);
00437    const u32bit X23 = get_u32bit(x, 23);
00438 
00439    x.mask_bits(384);
00440 
00441    int64_t S = 0;
00442 
00443    // One copy of P-384 is added to prevent underflow
00444    S = get_u32bit(x, 0);
00445    S += 0xFFFFFFFF;
00446    S += X12;
00447    S += X21;
00448    S += X20;
00449    S -= X23;
00450    set_u32bit(x, 0, S);
00451    S >>= 32;
00452 
00453    S += get_u32bit(x, 1);
00454    S += X13;
00455    S += X22;
00456    S += X23;
00457    S -= X12;
00458    S -= X20;
00459    set_u32bit(x, 1, S);
00460    S >>= 32;
00461 
00462    S += get_u32bit(x, 2);
00463    S += X14;
00464    S += X23;
00465    S -= X13;
00466    S -= X21;
00467    set_u32bit(x, 2, S);
00468    S >>= 32;
00469 
00470    S += get_u32bit(x, 3);
00471    S += 0xFFFFFFFF;
00472    S += X15;
00473    S += X12;
00474    S += X20;
00475    S += X21;
00476    S -= X14;
00477    S -= X22;
00478    S -= X23;
00479    set_u32bit(x, 3, S);
00480    S >>= 32;
00481 
00482    S += get_u32bit(x, 4);
00483    S += 0xFFFFFFFE;
00484    S += X21;
00485    S += X21;
00486    S += X16;
00487    S += X13;
00488    S += X12;
00489    S += X20;
00490    S += X22;
00491    S -= X15;
00492    S -= X23;
00493    S -= X23;
00494    set_u32bit(x, 4, S);
00495    S >>= 32;
00496 
00497    S += get_u32bit(x, 5);
00498    S += 0xFFFFFFFF;
00499    S += X22;
00500    S += X22;
00501    S += X17;
00502    S += X14;
00503    S += X13;
00504    S += X21;
00505    S += X23;
00506    S -= X16;
00507    set_u32bit(x, 5, S);
00508    S >>= 32;
00509 
00510    S += get_u32bit(x, 6);
00511    S += 0xFFFFFFFF;
00512    S += X23;
00513    S += X23;
00514    S += X18;
00515    S += X15;
00516    S += X14;
00517    S += X22;
00518    S -= X17;
00519    set_u32bit(x, 6, S);
00520    S >>= 32;
00521 
00522    S += get_u32bit(x, 7);
00523    S += 0xFFFFFFFF;
00524    S += X19;
00525    S += X16;
00526    S += X15;
00527    S += X23;
00528    S -= X18;
00529    set_u32bit(x, 7, S);
00530    S >>= 32;
00531 
00532    S += get_u32bit(x, 8);
00533    S += 0xFFFFFFFF;
00534    S += X20;
00535    S += X17;
00536    S += X16;
00537    S -= X19;
00538    set_u32bit(x, 8, S);
00539    S >>= 32;
00540 
00541    S += get_u32bit(x, 9);
00542    S += 0xFFFFFFFF;
00543    S += X21;
00544    S += X18;
00545    S += X17;
00546    S -= X20;
00547    set_u32bit(x, 9, S);
00548    S >>= 32;
00549 
00550    S += get_u32bit(x, 10);
00551    S += 0xFFFFFFFF;
00552    S += X22;
00553    S += X19;
00554    S += X18;
00555    S -= X21;
00556    set_u32bit(x, 10, S);
00557    S >>= 32;
00558 
00559    S += get_u32bit(x, 11);
00560    S += 0xFFFFFFFF;
00561    S += X23;
00562    S += X20;
00563    S += X19;
00564    S -= X22;
00565    set_u32bit(x, 11, S);
00566    S >>= 32;
00567    BOTAN_ASSERT_EQUAL(S >> 32, 0, "No underflow");
00568    set_u32bit(x, 12, S);
00569 
00570    if(S >= 2)
00571       {
00572       BOTAN_ASSERT(S <= 4, "Expected overflow");
00573 
00574       static const BigInt P384_mults[3] = {
00575          2*get_p(),
00576          3*get_p(),
00577          4*get_p()
00578       };
00579 
00580       x -= P384_mults[S - 2];
00581       }
00582 
00583    normalize(x, ws, max_redc_subtractions());
00584    }
00585 
00586 #endif
00587 
00588 
00589 }