Crypto++: serpent.cpp Source File

00001 // serpent.cpp - written and placed in the public domain by Wei Dai
00002 
00003 #include "pch.h"
00004 #include "serpent.h"
00005 #include "misc.h"
00006 
00007 NAMESPACE_BEGIN(CryptoPP)
00008 
00009 // linear transformation
00010 #define LT(i,a,b,c,d,e) {\
00011         a = rotlFixed(a, 13);   \
00012         c = rotlFixed(c, 3);    \
00013         d = rotlFixed(d ^ c ^ (a << 3), 7);     \
00014         b = rotlFixed(b ^ a ^ c, 1);    \
00015         a = rotlFixed(a ^ b ^ d, 5);            \
00016         c = rotlFixed(c ^ d ^ (b << 7), 22);}
00017 
00018 // inverse linear transformation
00019 #define ILT(i,a,b,c,d,e)        {\
00020         c = rotrFixed(c, 22);   \
00021         a = rotrFixed(a, 5);    \
00022         c ^= d ^ (b << 7);      \
00023         a ^= b ^ d;             \
00024         b = rotrFixed(b, 1);    \
00025         d = rotrFixed(d, 7) ^ c ^ (a << 3);     \
00026         b ^= a ^ c;             \
00027         c = rotrFixed(c, 3);    \
00028         a = rotrFixed(a, 13);}
00029 
00030 // order of output from S-box functions
00031 #define beforeS0(f) f(0,a,b,c,d,e)
00032 #define afterS0(f) f(1,b,e,c,a,d)
00033 #define afterS1(f) f(2,c,b,a,e,d)
00034 #define afterS2(f) f(3,a,e,b,d,c)
00035 #define afterS3(f) f(4,e,b,d,c,a)
00036 #define afterS4(f) f(5,b,a,e,c,d)
00037 #define afterS5(f) f(6,a,c,b,e,d)
00038 #define afterS6(f) f(7,a,c,d,b,e)
00039 #define afterS7(f) f(8,d,e,b,a,c)
00040 
00041 // order of output from inverse S-box functions
00042 #define beforeI7(f) f(8,a,b,c,d,e)
00043 #define afterI7(f) f(7,d,a,b,e,c)
00044 #define afterI6(f) f(6,a,b,c,e,d)
00045 #define afterI5(f) f(5,b,d,e,c,a)
00046 #define afterI4(f) f(4,b,c,e,a,d)
00047 #define afterI3(f) f(3,a,b,e,c,d)
00048 #define afterI2(f) f(2,b,d,e,c,a)
00049 #define afterI1(f) f(1,a,b,c,e,d)
00050 #define afterI0(f) f(0,a,d,b,e,c)
00051 
00052 // The instruction sequences for the S-box functions 
00053 // come from Dag Arne Osvik's paper "Speeding up Serpent".
00054 
00055 #define S0(i, r0, r1, r2, r3, r4) \
00056        {           \
00057     r3 ^= r0;   \
00058     r4 = r1;   \
00059     r1 &= r3;   \
00060     r4 ^= r2;   \
00061     r1 ^= r0;   \
00062     r0 |= r3;   \
00063     r0 ^= r4;   \
00064     r4 ^= r3;   \
00065     r3 ^= r2;   \
00066     r2 |= r1;   \
00067     r2 ^= r4;   \
00068     r4 = ~r4;      \
00069     r4 |= r1;   \
00070     r1 ^= r3;   \
00071     r1 ^= r4;   \
00072     r3 |= r0;   \
00073     r1 ^= r3;   \
00074     r4 ^= r3;   \
00075             }
00076 
00077 #define I0(i, r0, r1, r2, r3, r4) \
00078        {           \
00079     r2 = ~r2;      \
00080     r4 = r1;   \
00081     r1 |= r0;   \
00082     r4 = ~r4;      \
00083     r1 ^= r2;   \
00084     r2 |= r4;   \
00085     r1 ^= r3;   \
00086     r0 ^= r4;   \
00087     r2 ^= r0;   \
00088     r0 &= r3;   \
00089     r4 ^= r0;   \
00090     r0 |= r1;   \
00091     r0 ^= r2;   \
00092     r3 ^= r4;   \
00093     r2 ^= r1;   \
00094     r3 ^= r0;   \
00095     r3 ^= r1;   \
00096     r2 &= r3;   \
00097     r4 ^= r2;   \
00098             }
00099 
00100 #define S1(i, r0, r1, r2, r3, r4) \
00101        {           \
00102     r0 = ~r0;      \
00103     r2 = ~r2;      \
00104     r4 = r0;   \
00105     r0 &= r1;   \
00106     r2 ^= r0;   \
00107     r0 |= r3;   \
00108     r3 ^= r2;   \
00109     r1 ^= r0;   \
00110     r0 ^= r4;   \
00111     r4 |= r1;   \
00112     r1 ^= r3;   \
00113     r2 |= r0;   \
00114     r2 &= r4;   \
00115     r0 ^= r1;   \
00116     r1 &= r2;   \
00117     r1 ^= r0;   \
00118     r0 &= r2;   \
00119     r0 ^= r4;   \
00120             }
00121 
00122 #define I1(i, r0, r1, r2, r3, r4) \
00123        {           \
00124     r4 = r1;   \
00125     r1 ^= r3;   \
00126     r3 &= r1;   \
00127     r4 ^= r2;   \
00128     r3 ^= r0;   \
00129     r0 |= r1;   \
00130     r2 ^= r3;   \
00131     r0 ^= r4;   \
00132     r0 |= r2;   \
00133     r1 ^= r3;   \
00134     r0 ^= r1;   \
00135     r1 |= r3;   \
00136     r1 ^= r0;   \
00137     r4 = ~r4;      \
00138     r4 ^= r1;   \
00139     r1 |= r0;   \
00140     r1 ^= r0;   \
00141     r1 |= r4;   \
00142     r3 ^= r1;   \
00143             }
00144 
00145 #define S2(i, r0, r1, r2, r3, r4) \
00146        {           \
00147     r4 = r0;   \
00148     r0 &= r2;   \
00149     r0 ^= r3;   \
00150     r2 ^= r1;   \
00151     r2 ^= r0;   \
00152     r3 |= r4;   \
00153     r3 ^= r1;   \
00154     r4 ^= r2;   \
00155     r1 = r3;   \
00156     r3 |= r4;   \
00157     r3 ^= r0;   \
00158     r0 &= r1;   \
00159     r4 ^= r0;   \
00160     r1 ^= r3;   \
00161     r1 ^= r4;   \
00162     r4 = ~r4;      \
00163             }
00164 
00165 #define I2(i, r0, r1, r2, r3, r4) \
00166        {           \
00167     r2 ^= r3;   \
00168     r3 ^= r0;   \
00169     r4 = r3;   \
00170     r3 &= r2;   \
00171     r3 ^= r1;   \
00172     r1 |= r2;   \
00173     r1 ^= r4;   \
00174     r4 &= r3;   \
00175     r2 ^= r3;   \
00176     r4 &= r0;   \
00177     r4 ^= r2;   \
00178     r2 &= r1;   \
00179     r2 |= r0;   \
00180     r3 = ~r3;      \
00181     r2 ^= r3;   \
00182     r0 ^= r3;   \
00183     r0 &= r1;   \
00184     r3 ^= r4;   \
00185     r3 ^= r0;   \
00186             }
00187 
00188 #define S3(i, r0, r1, r2, r3, r4) \
00189        {           \
00190     r4 = r0;   \
00191     r0 |= r3;   \
00192     r3 ^= r1;   \
00193     r1 &= r4;   \
00194     r4 ^= r2;   \
00195     r2 ^= r3;   \
00196     r3 &= r0;   \
00197     r4 |= r1;   \
00198     r3 ^= r4;   \
00199     r0 ^= r1;   \
00200     r4 &= r0;   \
00201     r1 ^= r3;   \
00202     r4 ^= r2;   \
00203     r1 |= r0;   \
00204     r1 ^= r2;   \
00205     r0 ^= r3;   \
00206     r2 = r1;   \
00207     r1 |= r3;   \
00208     r1 ^= r0;   \
00209             }
00210 
00211 #define I3(i, r0, r1, r2, r3, r4) \
00212        {           \
00213     r4 = r2;   \
00214     r2 ^= r1;   \
00215     r1 &= r2;   \
00216     r1 ^= r0;   \
00217     r0 &= r4;   \
00218     r4 ^= r3;   \
00219     r3 |= r1;   \
00220     r3 ^= r2;   \
00221     r0 ^= r4;   \
00222     r2 ^= r0;   \
00223     r0 |= r3;   \
00224     r0 ^= r1;   \
00225     r4 ^= r2;   \
00226     r2 &= r3;   \
00227     r1 |= r3;   \
00228     r1 ^= r2;   \
00229     r4 ^= r0;   \
00230     r2 ^= r4;   \
00231             }
00232 
00233 #define S4(i, r0, r1, r2, r3, r4) \
00234        {           \
00235     r1 ^= r3;   \
00236     r3 = ~r3;      \
00237     r2 ^= r3;   \
00238     r3 ^= r0;   \
00239     r4 = r1;   \
00240     r1 &= r3;   \
00241     r1 ^= r2;   \
00242     r4 ^= r3;   \
00243     r0 ^= r4;   \
00244     r2 &= r4;   \
00245     r2 ^= r0;   \
00246     r0 &= r1;   \
00247     r3 ^= r0;   \
00248     r4 |= r1;   \
00249     r4 ^= r0;   \
00250     r0 |= r3;   \
00251     r0 ^= r2;   \
00252     r2 &= r3;   \
00253     r0 = ~r0;      \
00254     r4 ^= r2;   \
00255             }
00256 
00257 #define I4(i, r0, r1, r2, r3, r4) \
00258        {           \
00259     r4 = r2;   \
00260     r2 &= r3;   \
00261     r2 ^= r1;   \
00262     r1 |= r3;   \
00263     r1 &= r0;   \
00264     r4 ^= r2;   \
00265     r4 ^= r1;   \
00266     r1 &= r2;   \
00267     r0 = ~r0;      \
00268     r3 ^= r4;   \
00269     r1 ^= r3;   \
00270     r3 &= r0;   \
00271     r3 ^= r2;   \
00272     r0 ^= r1;   \
00273     r2 &= r0;   \
00274     r3 ^= r0;   \
00275     r2 ^= r4;   \
00276     r2 |= r3;   \
00277     r3 ^= r0;   \
00278     r2 ^= r1;   \
00279             }
00280 
00281 #define S5(i, r0, r1, r2, r3, r4) \
00282        {           \
00283     r0 ^= r1;   \
00284     r1 ^= r3;   \
00285     r3 = ~r3;      \
00286     r4 = r1;   \
00287     r1 &= r0;   \
00288     r2 ^= r3;   \
00289     r1 ^= r2;   \
00290     r2 |= r4;   \
00291     r4 ^= r3;   \
00292     r3 &= r1;   \
00293     r3 ^= r0;   \
00294     r4 ^= r1;   \
00295     r4 ^= r2;   \
00296     r2 ^= r0;   \
00297     r0 &= r3;   \
00298     r2 = ~r2;      \
00299     r0 ^= r4;   \
00300     r4 |= r3;   \
00301     r2 ^= r4;   \
00302             }
00303 
00304 #define I5(i, r0, r1, r2, r3, r4) \
00305        {           \
00306     r1 = ~r1;      \
00307     r4 = r3;   \
00308     r2 ^= r1;   \
00309     r3 |= r0;   \
00310     r3 ^= r2;   \
00311     r2 |= r1;   \
00312     r2 &= r0;   \
00313     r4 ^= r3;   \
00314     r2 ^= r4;   \
00315     r4 |= r0;   \
00316     r4 ^= r1;   \
00317     r1 &= r2;   \
00318     r1 ^= r3;   \
00319     r4 ^= r2;   \
00320     r3 &= r4;   \
00321     r4 ^= r1;   \
00322     r3 ^= r0;   \
00323     r3 ^= r4;   \
00324     r4 = ~r4;      \
00325             }
00326 
00327 #define S6(i, r0, r1, r2, r3, r4) \
00328        {           \
00329     r2 = ~r2;      \
00330     r4 = r3;   \
00331     r3 &= r0;   \
00332     r0 ^= r4;   \
00333     r3 ^= r2;   \
00334     r2 |= r4;   \
00335     r1 ^= r3;   \
00336     r2 ^= r0;   \
00337     r0 |= r1;   \
00338     r2 ^= r1;   \
00339     r4 ^= r0;   \
00340     r0 |= r3;   \
00341     r0 ^= r2;   \
00342     r4 ^= r3;   \
00343     r4 ^= r0;   \
00344     r3 = ~r3;      \
00345     r2 &= r4;   \
00346     r2 ^= r3;   \
00347             }
00348 
00349 #define I6(i, r0, r1, r2, r3, r4) \
00350        {           \
00351     r0 ^= r2;   \
00352     r4 = r2;   \
00353     r2 &= r0;   \
00354     r4 ^= r3;   \
00355     r2 = ~r2;      \
00356     r3 ^= r1;   \
00357     r2 ^= r3;   \
00358     r4 |= r0;   \
00359     r0 ^= r2;   \
00360     r3 ^= r4;   \
00361     r4 ^= r1;   \
00362     r1 &= r3;   \
00363     r1 ^= r0;   \
00364     r0 ^= r3;   \
00365     r0 |= r2;   \
00366     r3 ^= r1;   \
00367     r4 ^= r0;   \
00368             }
00369 
00370 #define S7(i, r0, r1, r2, r3, r4) \
00371        {           \
00372     r4 = r2;   \
00373     r2 &= r1;   \
00374     r2 ^= r3;   \
00375     r3 &= r1;   \
00376     r4 ^= r2;   \
00377     r2 ^= r1;   \
00378     r1 ^= r0;   \
00379     r0 |= r4;   \
00380     r0 ^= r2;   \
00381     r3 ^= r1;   \
00382     r2 ^= r3;   \
00383     r3 &= r0;   \
00384     r3 ^= r4;   \
00385     r4 ^= r2;   \
00386     r2 &= r0;   \
00387     r4 = ~r4;      \
00388     r2 ^= r4;   \
00389     r4 &= r0;   \
00390     r1 ^= r3;   \
00391     r4 ^= r1;   \
00392             }
00393 
00394 #define I7(i, r0, r1, r2, r3, r4) \
00395        {           \
00396     r4 = r2;   \
00397     r2 ^= r0;   \
00398     r0 &= r3;   \
00399     r2 = ~r2;      \
00400     r4 |= r3;   \
00401     r3 ^= r1;   \
00402     r1 |= r0;   \
00403     r0 ^= r2;   \
00404     r2 &= r4;   \
00405     r1 ^= r2;   \
00406     r2 ^= r0;   \
00407     r0 |= r2;   \
00408     r3 &= r4;   \
00409     r0 ^= r3;   \
00410     r4 ^= r1;   \
00411     r3 ^= r4;   \
00412     r4 |= r0;   \
00413     r3 ^= r2;   \
00414     r4 ^= r2;   \
00415             }
00416 
00417 // key xor
00418 #define KX(r, a, b, c, d, e)    {\
00419         a ^= k[4 * r + 0]; \
00420         b ^= k[4 * r + 1]; \
00421         c ^= k[4 * r + 2]; \
00422         d ^= k[4 * r + 3];}
00423 
00424 void Serpent::Base::UncheckedSetKey(const byte *userKey, unsigned int keylen, const NameValuePairs &)
00425 {
00426         AssertValidKeyLength(keylen);
00427 
00428         word32 *k = m_key;
00429         GetUserKey(LITTLE_ENDIAN_ORDER, k, 8, userKey, keylen);
00430 
00431         if (keylen < 32)
00432                 k[keylen/4] |= word32(1) << ((keylen%4)*8);
00433 
00434         k += 8;
00435         word32 t = k[-1];
00436         signed int i;
00437         for (i = 0; i < 132; ++i)
00438                 k[i] = t = rotlFixed(k[i-8] ^ k[i-5] ^ k[i-3] ^ t ^ 0x9e3779b9 ^ i, 11);
00439         k -= 20;
00440 
00441 #define LK(r, a, b, c, d, e)    {\
00442         a = k[(8-r)*4 + 0];             \
00443         b = k[(8-r)*4 + 1];             \
00444         c = k[(8-r)*4 + 2];             \
00445         d = k[(8-r)*4 + 3];}
00446 
00447 #define SK(r, a, b, c, d, e)    {\
00448         k[(8-r)*4 + 4] = a;             \
00449         k[(8-r)*4 + 5] = b;             \
00450         k[(8-r)*4 + 6] = c;             \
00451         k[(8-r)*4 + 7] = d;}    \
00452 
00453         word32 a,b,c,d,e;
00454         for (i=0; i<4; i++)
00455         {
00456                 afterS2(LK); afterS2(S3); afterS3(SK);
00457                 afterS1(LK); afterS1(S2); afterS2(SK);
00458                 afterS0(LK); afterS0(S1); afterS1(SK);
00459                 beforeS0(LK); beforeS0(S0); afterS0(SK);
00460                 k += 8*4;
00461                 afterS6(LK); afterS6(S7); afterS7(SK);
00462                 afterS5(LK); afterS5(S6); afterS6(SK);
00463                 afterS4(LK); afterS4(S5); afterS5(SK);
00464                 afterS3(LK); afterS3(S4); afterS4(SK);
00465         }
00466         afterS2(LK); afterS2(S3); afterS3(SK);
00467 }
00468 
00469 typedef BlockGetAndPut<word32, LittleEndian> Block;
00470 
00471 void Serpent::Enc::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
00472 {
00473         word32 a, b, c, d, e;
00474         
00475         Block::Get(inBlock)(a)(b)(c)(d);
00476 
00477         const word32 *k = m_key + 8;
00478         unsigned int i=1;
00479 
00480         do
00481         {
00482                 beforeS0(KX); beforeS0(S0); afterS0(LT);
00483                 afterS0(KX); afterS0(S1); afterS1(LT);
00484                 afterS1(KX); afterS1(S2); afterS2(LT);
00485                 afterS2(KX); afterS2(S3); afterS3(LT);
00486                 afterS3(KX); afterS3(S4); afterS4(LT);
00487                 afterS4(KX); afterS4(S5); afterS5(LT);
00488                 afterS5(KX); afterS5(S6); afterS6(LT);
00489                 afterS6(KX); afterS6(S7);
00490 
00491                 if (i == 4)
00492                         break;
00493 
00494                 ++i;
00495                 c = b;
00496                 b = e;
00497                 e = d;
00498                 d = a;
00499                 a = e;
00500                 k += 32;
00501                 beforeS0(LT);
00502         }
00503         while (true);
00504 
00505         afterS7(KX);
00506         
00507         Block::Put(xorBlock, outBlock)(d)(e)(b)(a);
00508 }
00509 
00510 void Serpent::Dec::ProcessAndXorBlock(const byte *inBlock, const byte *xorBlock, byte *outBlock) const
00511 {
00512         word32 a, b, c, d, e;
00513         
00514         Block::Get(inBlock)(a)(b)(c)(d);
00515 
00516         const word32 *k = m_key + 104;
00517         unsigned int i=4;
00518 
00519         beforeI7(KX);
00520         goto start;
00521 
00522         do
00523         {
00524                 c = b;
00525                 b = d;
00526                 d = e;
00527                 k -= 32;
00528                 beforeI7(ILT);
00529 start:
00530                             beforeI7(I7); afterI7(KX); 
00531                 afterI7(ILT); afterI7(I6); afterI6(KX); 
00532                 afterI6(ILT); afterI6(I5); afterI5(KX); 
00533                 afterI5(ILT); afterI5(I4); afterI4(KX); 
00534                 afterI4(ILT); afterI4(I3); afterI3(KX); 
00535                 afterI3(ILT); afterI3(I2); afterI2(KX); 
00536                 afterI2(ILT); afterI2(I1); afterI1(KX); 
00537                 afterI1(ILT); afterI1(I0); afterI0(KX);
00538         }
00539         while (--i != 0);
00540         
00541         Block::Put(xorBlock, outBlock)(a)(d)(b)(e);
00542 }
00543 
00544 NAMESPACE_END