diff options
author | Lucas Kanashiro <kanashiro@debian.org> | 2017-06-25 00:00:40 -0300 |
---|---|---|
committer | Lucas Kanashiro <kanashiro@debian.org> | 2017-06-25 00:00:40 -0300 |
commit | ea35d105ec8dbf421ad1803bcb72e097d2295a18 (patch) | |
tree | 2aa3f333938fb6886d020d7deb5bc7b4d010afca /src/ltc/pk/ecc |
Import original source of CryptX 0.048
Diffstat (limited to 'src/ltc/pk/ecc')
38 files changed, 4471 insertions, 0 deletions
diff --git a/src/ltc/pk/ecc/ecc.c b/src/ltc/pk/ecc/ecc.c new file mode 100644 index 00000000..b48b3f54 --- /dev/null +++ b/src/ltc/pk/ecc/ecc.c @@ -0,0 +1,426 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ecc.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/* This array holds the curve parameters: + * - it ***MUST*** be organized by size from smallest to largest + * - due to curve lookup by keysize the ordering is very important + * - be careful when adding/removing items to/from this list + * Curves (prime field only) are taken from: + * - http://www.secg.org/collateral/sec2_final.pdf (named: SECP*) + * - http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf (named: NISTP*) + * - ANS X9.62 (named: PRIMEP*) + * - http://www.ecc-brainpool.org/download/Domain-parameters.pdf (named: BRAINPOOLP*) + */ +const ltc_ecc_set_type ltc_ecc_sets[] = { +#if defined(LTC_ECC_SECP112R1) || defined(LTC_ECC112) +{ /* this curve ***MUST*** be the first from all with size 14 (backward compatibility reasons) */ + /* size/bytes */ 14, + /* curve name */ "SECP112R1", + /* prime */ "DB7C2ABF62E35E668076BEAD208B", + /* A */ "DB7C2ABF62E35E668076BEAD2088", + /* B */ "659EF8BA043916EEDE8911702B22", + /* order */ "DB7C2ABF62E35E7628DFAC6561C5", + /* Gx */ "09487239995A5EE76B55F9C2F098", + /* Gy */ "A89CE5AF8724C0A23E0E0FF77500", + /* cofactor */ 1, + /* OID struct */ { {1,3,132,0,6}, 5 } +}, +#endif +#ifdef LTC_ECC_SECP112R2 +{ + /* size/bytes */ 14, + /* curve name */ "SECP112R2", + /* prime */ "DB7C2ABF62E35E668076BEAD208B", + /* A */ "6127C24C05F38A0AAAF65C0EF02C", + /* B */ "51DEF1815DB5ED74FCC34C85D709", + /* order */ "36DF0AAFD8B8D7597CA10520D04B", + /* Gx */ "4BA30AB5E892B4E1649DD0928643", + /* Gy */ "ADCD46F5882E3747DEF36E956E97", + /* cofactor */ 4, + /* OID struct */ { {1,3,132,0,7}, 5 } +}, +#endif +#if defined(LTC_ECC_SECP128R1) || defined(LTC_ECC128) +{ /* this curve ***MUST*** be the first from all with size 16 (backward compatibility reasons) */ + /* size/bytes */ 16, + /* curve name */ "SECP128R1", + /* prime */ "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF", + /* A */ "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFC", + /* B */ "E87579C11079F43DD824993C2CEE5ED3", + /* order */ "FFFFFFFE0000000075A30D1B9038A115", + /* Gx */ "161FF7528B899B2D0C28607CA52C5B86", + /* Gy */ "CF5AC8395BAFEB13C02DA292DDED7A83", + /* cofactor */ 1, + /* OID struct */ { {1,3,132,0,28}, 5 } +}, +#endif +#ifdef LTC_ECC_SECP128R2 +{ + /* size/bytes */ 16, + /* curve name */ "SECP128R2", + /* prime */ "FFFFFFFDFFFFFFFFFFFFFFFFFFFFFFFF", + /* A */ "D6031998D1B3BBFEBF59CC9BBFF9AEE1", + /* B */ "5EEEFCA380D02919DC2C6558BB6D8A5D", + /* order */ "3FFFFFFF7FFFFFFFBE0024720613B5A3", + /* Gx */ "7B6AA5D85E572983E6FB32A7CDEBC140", + /* Gy */ "27B6916A894D3AEE7106FE805FC34B44", + /* cofactor */ 4, + /* OID struct */ { {1,3,132,0,29}, 5 } +}, +#endif +#if defined(LTC_ECC_SECP160R1) || defined(LTC_ECC160) +{ /* this curve ***MUST*** be the first from all with size 20 (backward compatibility reasons) */ + /* size/bytes */ 20, + /* curve name */ "SECP160R1", + /* prime */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFF", + /* A */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF7FFFFFFC", + /* B */ "1C97BEFC54BD7A8B65ACF89F81D4D4ADC565FA45", + /* order */ "0100000000000000000001F4C8F927AED3CA752257", + /* Gx */ "4A96B5688EF573284664698968C38BB913CBFC82", + /* Gy */ "23A628553168947D59DCC912042351377AC5FB32", + /* cofactor */ 1, + /* OID struct */ { {1,3,132,0,8}, 5 } +}, +#endif +#ifdef LTC_ECC_SECP160R2 +{ + /* size/bytes */ 20, + /* curve name */ "SECP160R2", + /* prime */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC73", + /* A */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC70", + /* B */ "B4E134D3FB59EB8BAB57274904664D5AF50388BA", + /* order */ "0100000000000000000000351EE786A818F3A1A16B", + /* Gx */ "52DCB034293A117E1F4FF11B30F7199D3144CE6D", + /* Gy */ "FEAFFEF2E331F296E071FA0DF9982CFEA7D43F2E", + /* cofactor */ 1, + /* OID struct */ { {1,3,132,0,30}, 5 } +}, +#endif +#ifdef LTC_ECC_SECP160K1 +{ + /* size/bytes */ 20, + /* curve name */ "SECP160K1", + /* prime */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFAC73", + /* A */ "0000000000000000000000000000000000000000", + /* B */ "0000000000000000000000000000000000000007", + /* order */ "0100000000000000000001B8FA16DFAB9ACA16B6B3", + /* Gx */ "3B4C382CE37AA192A4019E763036F4F5DD4D7EBB", + /* Gy */ "938CF935318FDCED6BC28286531733C3F03C4FEE", + /* cofactor */ 1, + /* OID struct */ { {1,3,132,0,9}, 5 } +}, +#endif +#ifdef LTC_ECC_BRAINPOOLP160R1 +{ + /* size/bytes */ 20, + /* curve name */ "BRAINPOOLP160R1", + /* prime */ "E95E4A5F737059DC60DFC7AD95B3D8139515620F", + /* A */ "340E7BE2A280EB74E2BE61BADA745D97E8F7C300", + /* B */ "1E589A8595423412134FAA2DBDEC95C8D8675E58", + /* order */ "E95E4A5F737059DC60DF5991D45029409E60FC09", + /* Gx */ "BED5AF16EA3F6A4F62938C4631EB5AF7BDBCDBC3", + /* Gy */ "1667CB477A1A8EC338F94741669C976316DA6321", + /* cofactor */ 1, + /* OID struct */ { {1,3,36,3,3,2,8,1,1,1}, 10 } +}, +#endif +#if defined(LTC_ECC_SECP192R1) || defined(LTC_ECC192) +{ /* this curve ***MUST*** be the first from all with size 24 (backward compatibility reasons) */ + /* size/bytes */ 24, + /* curve name */ "SECP192R1", /* same as: NISTP192 PRIME192V1, old libtomcrypt name: ECC-192 */ + /* prime */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF", + /* A */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC", + /* B */ "64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1", + /* order */ "FFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831", + /* Gx */ "188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012", + /* Gy */ "07192B95FFC8DA78631011ED6B24CDD573F977A11E794811", + /* cofactor */ 1, + /* OID struct */ { {1,2,840,10045,3,1,1}, 7 } +}, +#endif +#ifdef LTC_ECC_PRIME192V2 +{ + /* size/bytes */ 24, + /* curve name */ "PRIME192V2", + /* prime */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF", + /* A */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC", + /* B */ "CC22D6DFB95C6B25E49C0D6364A4E5980C393AA21668D953", + /* order */ "FFFFFFFFFFFFFFFFFFFFFFFE5FB1A724DC80418648D8DD31", + /* Gx */ "EEA2BAE7E1497842F2DE7769CFE9C989C072AD696F48034A", + /* Gy */ "6574D11D69B6EC7A672BB82A083DF2F2B0847DE970B2DE15", + /* cofactor */ 1, + /* OID struct */ { {1,2,840,10045,3,1,2}, 7 } +}, +#endif +#ifdef LTC_ECC_PRIME192V3 +{ + /* size/bytes */ 24, + /* curve name */ "PRIME192V3", + /* prime */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF", + /* A */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC", + /* B */ "22123DC2395A05CAA7423DAECCC94760A7D462256BD56916", + /* order */ "FFFFFFFFFFFFFFFFFFFFFFFF7A62D031C83F4294F640EC13", + /* Gx */ "7D29778100C65A1DA1783716588DCE2B8B4AEE8E228F1896", + /* Gy */ "38A90F22637337334B49DCB66A6DC8F9978ACA7648A943B0", + /* cofactor */ 1, + /* OID struct */ { {1,2,840,10045,3,1,3}, 7 } +}, +#endif +#ifdef LTC_ECC_SECP192K1 +{ + /* size/bytes */ 24, + /* curve name */ "SECP192K1", + /* prime */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFEE37", + /* A */ "000000000000000000000000000000000000000000000000", + /* B */ "000000000000000000000000000000000000000000000003", + /* order */ "FFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D", + /* Gx */ "DB4FF10EC057E9AE26B07D0280B7F4341DA5D1B1EAE06C7D", + /* Gy */ "9B2F2F6D9C5628A7844163D015BE86344082AA88D95E2F9D", + /* cofactor */ 1, + /* OID struct */ { {1,3,132,0,31}, 5 } +}, +#endif +#ifdef LTC_ECC_BRAINPOOLP192R1 +{ + /* size/bytes */ 24, + /* curve name */ "BRAINPOOLP192R1", + /* prime */ "C302F41D932A36CDA7A3463093D18DB78FCE476DE1A86297", + /* A */ "6A91174076B1E0E19C39C031FE8685C1CAE040E5C69A28EF", + /* B */ "469A28EF7C28CCA3DC721D044F4496BCCA7EF4146FBF25C9", + /* order */ "C302F41D932A36CDA7A3462F9E9E916B5BE8F1029AC4ACC1", + /* Gx */ "C0A0647EAAB6A48753B033C56CB0F0900A2F5C4853375FD6", + /* Gy */ "14B690866ABD5BB88B5F4828C1490002E6773FA2FA299B8F", + /* cofactor */ 1, + /* OID struct */ { {1,3,36,3,3,2,8,1,1,3}, 10 } +}, +#endif +#if defined(LTC_ECC_SECP224R1) || defined(LTC_ECC224) +{ /* this curve ***MUST*** be the first from all with size 28 (backward compatibility reasons) */ + /* size/bytes */ 28, + /* curve name */ "SECP224R1", /* same as: NISTP224, old libtomcrypt name: ECC-224 */ + /* prime */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001", + /* A */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFE", + /* B */ "B4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4", + /* order */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D", + /* Gx */ "B70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21", + /* Gy */ "BD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34", + /* cofactor */ 1, + /* OID struct */ { {1,3,132,0,33}, 5 } +}, +#endif +#ifdef LTC_ECC_SECP224K1 +{ + /* size/bytes */ 28, + /* curve name */ "SECP224K1", + /* prime */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFE56D", + /* A */ "00000000000000000000000000000000000000000000000000000000", + /* B */ "00000000000000000000000000000000000000000000000000000005", + /* order */ "010000000000000000000000000001DCE8D2EC6184CAF0A971769FB1F7", + /* Gx */ "A1455B334DF099DF30FC28A169A467E9E47075A90F7E650EB6B7A45C", + /* Gy */ "7E089FED7FBA344282CAFBD6F7E319F7C0B0BD59E2CA4BDB556D61A5", + /* cofactor */ 1, + /* OID struct */ { {1,3,132,0,32}, 5 } +}, +#endif +#ifdef LTC_ECC_BRAINPOOLP224R1 +{ + /* size/bytes */ 28, + /* curve name */ "BRAINPOOLP224R1", + /* prime */ "D7C134AA264366862A18302575D1D787B09F075797DA89F57EC8C0FF", + /* A */ "68A5E62CA9CE6C1C299803A6C1530B514E182AD8B0042A59CAD29F43", + /* B */ "2580F63CCFE44138870713B1A92369E33E2135D266DBB372386C400B", + /* order */ "D7C134AA264366862A18302575D0FB98D116BC4B6DDEBCA3A5A7939F", + /* Gx */ "0D9029AD2C7E5CF4340823B2A87DC68C9E4CE3174C1E6EFDEE12C07D", + /* Gy */ "58AA56F772C0726F24C6B89E4ECDAC24354B9E99CAA3F6D3761402CD", + /* cofactor */ 1, + /* OID struct */ { {1,3,36,3,3,2,8,1,1,5}, 10 } +}, +#endif +#ifdef LTC_ECC_PRIME239V1 +{ + /* size/bytes */ 30, + /* curve name */ "PRIME239V1", + /* prime */ "7FFFFFFFFFFFFFFFFFFFFFFF7FFFFFFFFFFF8000000000007FFFFFFFFFFF", + /* A */ "7FFFFFFFFFFFFFFFFFFFFFFF7FFFFFFFFFFF8000000000007FFFFFFFFFFC", + /* B */ "6B016C3BDCF18941D0D654921475CA71A9DB2FB27D1D37796185C2942C0A", + /* order */ "7FFFFFFFFFFFFFFFFFFFFFFF7FFFFF9E5E9A9F5D9071FBD1522688909D0B", + /* Gx */ "0FFA963CDCA8816CCC33B8642BEDF905C3D358573D3F27FBBD3B3CB9AAAF", + /* Gy */ "7DEBE8E4E90A5DAE6E4054CA530BA04654B36818CE226B39FCCB7B02F1AE", + /* cofactor */ 1, + /* OID struct */ { {1,2,840,10045,3,1,4}, 7 } +}, +#endif +#ifdef LTC_ECC_PRIME239V2 +{ + /* size/bytes */ 30, + /* curve name */ "PRIME239V2", + /* prime */ "7FFFFFFFFFFFFFFFFFFFFFFF7FFFFFFFFFFF8000000000007FFFFFFFFFFF", + /* A */ "7FFFFFFFFFFFFFFFFFFFFFFF7FFFFFFFFFFF8000000000007FFFFFFFFFFC", + /* B */ "617FAB6832576CBBFED50D99F0249C3FEE58B94BA0038C7AE84C8C832F2C", + /* order */ "7FFFFFFFFFFFFFFFFFFFFFFF800000CFA7E8594377D414C03821BC582063", + /* Gx */ "38AF09D98727705120C921BB5E9E26296A3CDCF2F35757A0EAFD87B830E7", + /* Gy */ "5B0125E4DBEA0EC7206DA0FC01D9B081329FB555DE6EF460237DFF8BE4BA", + /* cofactor */ 1, + /* OID struct */ { {1,2,840,10045,3,1,5}, 7 } +}, +#endif +#ifdef LTC_ECC_PRIME239V3 +{ + /* size/bytes */ 30, + /* curve name */ "PRIME239V3", + /* prime */ "7FFFFFFFFFFFFFFFFFFFFFFF7FFFFFFFFFFF8000000000007FFFFFFFFFFF", + /* A */ "7FFFFFFFFFFFFFFFFFFFFFFF7FFFFFFFFFFF8000000000007FFFFFFFFFFC", + /* B */ "255705FA2A306654B1F4CB03D6A750A30C250102D4988717D9BA15AB6D3E", + /* order */ "7FFFFFFFFFFFFFFFFFFFFFFF7FFFFF975DEB41B3A6057C3C432146526551", + /* Gx */ "6768AE8E18BB92CFCF005C949AA2C6D94853D0E660BBF854B1C9505FE95A", + /* Gy */ "1607E6898F390C06BC1D552BAD226F3B6FCFE48B6E818499AF18E3ED6CF3", + /* cofactor */ 1, + /* OID struct */ { {1,2,840,10045,3,1,6}, 7 } +}, +#endif +#if defined(LTC_ECC_SECP256R1) || defined(LTC_ECC256) +{ /* this curve ***MUST*** be the first from all with size 32 (backward compatibility reasons) */ + /* size/bytes */ 32, + /* curve name */ "SECP256R1", /* same as: NISTP256 PRIME256V1, old libtomcrypt name: ECC-256 */ + /* prime */ "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF", + /* A */ "FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC", + /* B */ "5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B", + /* order */ "FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551", + /* Gx */ "6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296", + /* Gy */ "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5", + /* cofactor */ 1, + /* OID struct */ { {1,2,840,10045,3,1,7}, 7 } +}, +#endif +#ifdef LTC_ECC_SECP256K1 +{ + /* size/bytes */ 32, + /* curve name */ "SECP256K1", + /* prime */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", + /* A */ "0000000000000000000000000000000000000000000000000000000000000000", + /* B */ "0000000000000000000000000000000000000000000000000000000000000007", + /* order */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", + /* Gx */ "79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", + /* Gy */ "483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", + /* cofactor */ 1, + /* OID struct */ { {1,3,132,0,10}, 5 } +}, +#endif +#ifdef LTC_ECC_BRAINPOOLP256R1 +{ + /* size/bytes */ 32, + /* curve name */ "BRAINPOOLP256R1", + /* prime */ "A9FB57DBA1EEA9BC3E660A909D838D726E3BF623D52620282013481D1F6E5377", + /* A */ "7D5A0975FC2C3057EEF67530417AFFE7FB8055C126DC5C6CE94A4B44F330B5D9", + /* B */ "26DC5C6CE94A4B44F330B5D9BBD77CBF958416295CF7E1CE6BCCDC18FF8C07B6", + /* order */ "A9FB57DBA1EEA9BC3E660A909D838D718C397AA3B561A6F7901E0E82974856A7", + /* Gx */ "8BD2AEB9CB7E57CB2C4B482FFC81B7AFB9DE27E1E3BD23C23A4453BD9ACE3262", + /* Gy */ "547EF835C3DAC4FD97F8461A14611DC9C27745132DED8E545C1D54C72F046997", + /* cofactor */ 1, + /* OID struct */ { {1,3,36,3,3,2,8,1,1,7}, 10 } +}, +#endif +#ifdef LTC_ECC_BRAINPOOLP320R1 +{ + /* size/bytes */ 40, + /* curve name */ "BRAINPOOLP320R1", + /* prime */ "D35E472036BC4FB7E13C785ED201E065F98FCFA6F6F40DEF4F92B9EC7893EC28FCD412B1F1B32E27", + /* A */ "3EE30B568FBAB0F883CCEBD46D3F3BB8A2A73513F5EB79DA66190EB085FFA9F492F375A97D860EB4", + /* B */ "520883949DFDBC42D3AD198640688A6FE13F41349554B49ACC31DCCD884539816F5EB4AC8FB1F1A6", + /* order */ "D35E472036BC4FB7E13C785ED201E065F98FCFA5B68F12A32D482EC7EE8658E98691555B44C59311", + /* Gx */ "43BD7E9AFB53D8B85289BCC48EE5BFE6F20137D10A087EB6E7871E2A10A599C710AF8D0D39E20611", + /* Gy */ "14FDD05545EC1CC8AB4093247F77275E0743FFED117182EAA9C77877AAAC6AC7D35245D1692E8EE1", + /* cofactor */ 1, + /* OID struct */ { {1,3,36,3,3,2,8,1,1,9}, 10 } +}, +#endif +#if defined(LTC_ECC_SECP384R1) || defined(LTC_ECC384) +{ /* this curve ***MUST*** be the first from all with size 48 (backward compatibility reasons) */ + /* size/bytes */ 48, + /* curve name */ "SECP384R1", /* same as: NISTP384, old libtomcrypt name: ECC-384 */ + /* prime */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF", + /* A */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFC", + /* B */ "B3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF", + /* order */ "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973", + /* Gx */ "AA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7", + /* Gy */ "3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F", + /* cofactor */ 1, + /* OID struct */ { {1,3,132,0,34}, 5 } +}, +#endif +#ifdef LTC_ECC_BRAINPOOLP384R1 +{ + /* size/bytes */ 48, + /* curve name */ "BRAINPOOLP384R1", + /* prime */ "8CB91E82A3386D280F5D6F7E50E641DF152F7109ED5456B412B1DA197FB71123ACD3A729901D1A71874700133107EC53", + /* A */ "7BC382C63D8C150C3C72080ACE05AFA0C2BEA28E4FB22787139165EFBA91F90F8AA5814A503AD4EB04A8C7DD22CE2826", + /* B */ "04A8C7DD22CE28268B39B55416F0447C2FB77DE107DCD2A62E880EA53EEB62D57CB4390295DBC9943AB78696FA504C11", + /* order */ "8CB91E82A3386D280F5D6F7E50E641DF152F7109ED5456B31F166E6CAC0425A7CF3AB6AF6B7FC3103B883202E9046565", + /* Gx */ "1D1C64F068CF45FFA2A63A81B7C13F6B8847A3E77EF14FE3DB7FCAFE0CBD10E8E826E03436D646AAEF87B2E247D4AF1E", + /* Gy */ "8ABE1D7520F9C2A45CB1EB8E95CFD55262B70B29FEEC5864E19C054FF99129280E4646217791811142820341263C5315", + /* cofactor */ 1, + /* OID struct */ { {1,3,36,3,3,2,8,1,1,11}, 10 } +}, +#endif +#ifdef LTC_ECC_BRAINPOOLP512R1 +{ + /* size/bytes */ 64, + /* curve name */ "BRAINPOOLP512R1", + /* prime */ "AADD9DB8DBE9C48B3FD4E6AE33C9FC07CB308DB3B3C9D20ED6639CCA703308717D4D9B009BC66842AECDA12AE6A380E62881FF2F2D82C68528AA6056583A48F3", + /* A */ "7830A3318B603B89E2327145AC234CC594CBDD8D3DF91610A83441CAEA9863BC2DED5D5AA8253AA10A2EF1C98B9AC8B57F1117A72BF2C7B9E7C1AC4D77FC94CA", + /* B */ "3DF91610A83441CAEA9863BC2DED5D5AA8253AA10A2EF1C98B9AC8B57F1117A72BF2C7B9E7C1AC4D77FC94CADC083E67984050B75EBAE5DD2809BD638016F723", + /* order */ "AADD9DB8DBE9C48B3FD4E6AE33C9FC07CB308DB3B3C9D20ED6639CCA70330870553E5C414CA92619418661197FAC10471DB1D381085DDADDB58796829CA90069", + /* Gx */ "81AEE4BDD82ED9645A21322E9C4C6A9385ED9F70B5D916C1B43B62EEF4D0098EFF3B1F78E2D0D48D50D1687B93B97D5F7C6D5047406A5E688B352209BCB9F822", + /* Gy */ "7DDE385D566332ECC0EABFA9CF7822FDF209F70024A57B1AA000C55B881F8111B2DCDE494A5F485E5BCA4BD88A2763AED1CA2B2FA8F0540678CD1E0F3AD80892", + /* cofactor */ 1, + /* OID struct */ { {1,3,36,3,3,2,8,1,1,13}, 10 } +}, +#endif +#if defined(LTC_ECC_SECP521R1) || defined(LTC_ECC521) +{ /* this curve ***MUST*** be the first from all with size 66 (backward compatibility reasons) */ + /* size/bytes */ 66, + /* curve name */ "SECP521R1", /* same as: NISTP521, old libtomcrypt name: ECC-521 */ + /* prime */ "01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", + /* A */ "01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC", + /* B */ "0051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00", + /* order */ "01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409", + /* Gx */ "00C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66", + /* Gy */ "011839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650", + /* cofactor */ 1, + /* OID struct */ { {1,3,132,0,35}, 5 } +}, +#endif +{ + 0, + NULL, NULL, NULL, NULL, NULL, NULL, NULL, + 0, + { { 0 }, 0 } +} +}; + +#endif + +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ecc_ansi_x963_export.c b/src/ltc/pk/ecc/ecc_ansi_x963_export.c new file mode 100644 index 00000000..fec560bb --- /dev/null +++ b/src/ltc/pk/ecc/ecc_ansi_x963_export.c @@ -0,0 +1,76 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ecc_ansi_x963_export.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** ECC X9.63 (Sec. 4.3.6) uncompressed export + @param key Key to export + @param out [out] destination of export + @param outlen [in/out] Length of destination and final output size + Return CRYPT_OK on success +*/ +int ecc_ansi_x963_export(ecc_key *key, unsigned char *out, unsigned long *outlen) +{ + unsigned char buf[ECC_BUF_SIZE]; + unsigned long numlen, xlen, ylen; + + LTC_ARGCHK(key != NULL); + LTC_ARGCHK(out != NULL); + LTC_ARGCHK(outlen != NULL); + + if (ltc_ecc_is_valid_idx(key->idx) == 0) { + return CRYPT_INVALID_ARG; + } + numlen = key->dp->size; + xlen = mp_unsigned_bin_size(key->pubkey.x); + ylen = mp_unsigned_bin_size(key->pubkey.y); + + if (xlen > numlen || ylen > numlen || sizeof(buf) < numlen) { + return CRYPT_BUFFER_OVERFLOW; + } + + if (*outlen < (1 + 2*numlen)) { + *outlen = 1 + 2*numlen; + return CRYPT_BUFFER_OVERFLOW; + } + + /* store byte 0x04 */ + out[0] = 0x04; + + /* pad and store x */ + zeromem(buf, sizeof(buf)); + mp_to_unsigned_bin(key->pubkey.x, buf + (numlen - xlen)); + XMEMCPY(out+1, buf, numlen); + + /* pad and store y */ + zeromem(buf, sizeof(buf)); + mp_to_unsigned_bin(key->pubkey.y, buf + (numlen - ylen)); + XMEMCPY(out+1+numlen, buf, numlen); + + *outlen = 1 + 2*numlen; + return CRYPT_OK; +} + +#endif + +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ diff --git a/src/ltc/pk/ecc/ecc_ansi_x963_import.c b/src/ltc/pk/ecc/ecc_ansi_x963_import.c new file mode 100644 index 00000000..081cf641 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_ansi_x963_import.c @@ -0,0 +1,106 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ecc_ansi_x963_import.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** Import an ANSI X9.63 format public key + @param in The input data to read + @param inlen The length of the input data + @param key [out] destination to store imported key \ +*/ +int ecc_ansi_x963_import(const unsigned char *in, unsigned long inlen, ecc_key *key) +{ + return ecc_ansi_x963_import_ex(in, inlen, key, NULL); +} + +int ecc_ansi_x963_import_ex(const unsigned char *in, unsigned long inlen, ecc_key *key, ltc_ecc_set_type *dp) +{ + int x, err; + + LTC_ARGCHK(in != NULL); + LTC_ARGCHK(key != NULL); + + /* must be odd */ + if ((inlen & 1) == 0) { + return CRYPT_INVALID_ARG; + } + + /* init key */ + if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, NULL) != CRYPT_OK) { + return CRYPT_MEM; + } + + /* check for 4, 6 or 7 */ + if (in[0] != 4 && in[0] != 6 && in[0] != 7) { + err = CRYPT_INVALID_PACKET; + goto error; + } + + /* read data */ + if ((err = mp_read_unsigned_bin(key->pubkey.x, (unsigned char *)in+1, (inlen-1)>>1)) != CRYPT_OK) { + goto error; + } + + if ((err = mp_read_unsigned_bin(key->pubkey.y, (unsigned char *)in+1+((inlen-1)>>1), (inlen-1)>>1)) != CRYPT_OK) { + goto error; + } + if ((err = mp_set(key->pubkey.z, 1)) != CRYPT_OK) { goto error; } + + if (dp == NULL) { + /* BEWARE: Here we are looking up the curve params by keysize (neither curve name nor curve oid), + * which might be ambiguous (there can more than one curve for given keysize). + * Thus the chosen curve depends on order of items in ltc_ecc_sets[] - see ecc.c file. + */ + /* determine the idx */ + for (x = 0; ltc_ecc_sets[x].size != 0; x++) { + if ((unsigned)ltc_ecc_sets[x].size >= ((inlen-1)>>1)) { + break; + } + } + if (ltc_ecc_sets[x].size == 0) { + err = CRYPT_INVALID_PACKET; + goto error; + } + /* set the idx */ + key->idx = x; + key->dp = <c_ecc_sets[x]; + } else { + if (((inlen-1)>>1) != (unsigned long) dp->size) { + err = CRYPT_INVALID_PACKET; + goto error; + } + key->idx = -1; + key->dp = dp; + } + key->type = PK_PUBLIC; + + /* we're done */ + return CRYPT_OK; +error: + mp_clear_multi(key->pubkey.x, key->pubkey.y, key->pubkey.z, key->k, NULL); + return err; +} + +#endif + +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ diff --git a/src/ltc/pk/ecc/ecc_decrypt_key.c b/src/ltc/pk/ecc/ecc_decrypt_key.c new file mode 100644 index 00000000..6e1d34d7 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_decrypt_key.c @@ -0,0 +1,148 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ecc_decrypt_key.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** + Decrypt an ECC encrypted key + @param in The ciphertext + @param inlen The length of the ciphertext (octets) + @param out [out] The plaintext + @param outlen [in/out] The max size and resulting size of the plaintext + @param key The corresponding private ECC key + @return CRYPT_OK if successful +*/ +int ecc_decrypt_key(const unsigned char *in, unsigned long inlen, + unsigned char *out, unsigned long *outlen, + ecc_key *key) +{ + unsigned char *ecc_shared, *skey, *pub_expt; + unsigned long x, y, hashOID[32]; + int hash, err; + ecc_key pubkey; + ltc_asn1_list decode[3]; + + LTC_ARGCHK(in != NULL); + LTC_ARGCHK(out != NULL); + LTC_ARGCHK(outlen != NULL); + LTC_ARGCHK(key != NULL); + + /* right key type? */ + if (key->type != PK_PRIVATE) { + return CRYPT_PK_NOT_PRIVATE; + } + + /* decode to find out hash */ + LTC_SET_ASN1(decode, 0, LTC_ASN1_OBJECT_IDENTIFIER, hashOID, sizeof(hashOID)/sizeof(hashOID[0])); + + if ((err = der_decode_sequence(in, inlen, decode, 1)) != CRYPT_OK) { + return err; + } + + hash = find_hash_oid(hashOID, decode[0].size); + if (hash_is_valid(hash) != CRYPT_OK) { + return CRYPT_INVALID_PACKET; + } + + /* we now have the hash! */ + + /* allocate memory */ + pub_expt = XMALLOC(ECC_BUF_SIZE); + ecc_shared = XMALLOC(ECC_BUF_SIZE); + skey = XMALLOC(MAXBLOCKSIZE); + if (pub_expt == NULL || ecc_shared == NULL || skey == NULL) { + if (pub_expt != NULL) { + XFREE(pub_expt); + } + if (ecc_shared != NULL) { + XFREE(ecc_shared); + } + if (skey != NULL) { + XFREE(skey); + } + return CRYPT_MEM; + } + LTC_SET_ASN1(decode, 1, LTC_ASN1_OCTET_STRING, pub_expt, ECC_BUF_SIZE); + LTC_SET_ASN1(decode, 2, LTC_ASN1_OCTET_STRING, skey, MAXBLOCKSIZE); + + /* read the structure in now */ + if ((err = der_decode_sequence(in, inlen, decode, 3)) != CRYPT_OK) { + goto LBL_ERR; + } + + /* import ECC key from packet */ + if ((err = ecc_import_raw(decode[1].data, decode[1].size, &pubkey, (ltc_ecc_set_type *)key->dp)) != CRYPT_OK) { + goto LBL_ERR; + } + + /* make shared key */ + x = ECC_BUF_SIZE; + if ((err = ecc_shared_secret(key, &pubkey, ecc_shared, &x)) != CRYPT_OK) { + ecc_free(&pubkey); + goto LBL_ERR; + } + ecc_free(&pubkey); + + y = MIN(ECC_BUF_SIZE, MAXBLOCKSIZE); + if ((err = hash_memory(hash, ecc_shared, x, ecc_shared, &y)) != CRYPT_OK) { + goto LBL_ERR; + } + + /* ensure the hash of the shared secret is at least as big as the encrypt itself */ + if (decode[2].size > y) { + err = CRYPT_INVALID_PACKET; + goto LBL_ERR; + } + + /* avoid buffer overflow */ + if (*outlen < decode[2].size) { + *outlen = decode[2].size; + err = CRYPT_BUFFER_OVERFLOW; + goto LBL_ERR; + } + + /* Decrypt the key */ + for (x = 0; x < decode[2].size; x++) { + out[x] = skey[x] ^ ecc_shared[x]; + } + *outlen = x; + + err = CRYPT_OK; +LBL_ERR: +#ifdef LTC_CLEAN_STACK + zeromem(pub_expt, ECC_BUF_SIZE); + zeromem(ecc_shared, ECC_BUF_SIZE); + zeromem(skey, MAXBLOCKSIZE); +#endif + + XFREE(pub_expt); + XFREE(ecc_shared); + XFREE(skey); + + return err; +} + +#endif + +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ecc_dp_clear.c b/src/ltc/pk/ecc/ecc_dp_clear.c new file mode 100644 index 00000000..76fa375e --- /dev/null +++ b/src/ltc/pk/ecc/ecc_dp_clear.c @@ -0,0 +1,36 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +int ecc_dp_clear(ltc_ecc_set_type *dp) +{ + if (dp == NULL) return CRYPT_INVALID_ARG; + + if (dp->name != NULL) { XFREE(dp->name ); dp->name = NULL; } + if (dp->prime != NULL) { XFREE(dp->prime); dp->prime = NULL; } + if (dp->A != NULL) { XFREE(dp->A ); dp->A = NULL; } + if (dp->B != NULL) { XFREE(dp->B ); dp->B = NULL; } + if (dp->order != NULL) { XFREE(dp->order); dp->order = NULL; } + if (dp->Gx != NULL) { XFREE(dp->Gx ); dp->Gx = NULL; } + if (dp->Gy != NULL) { XFREE(dp->Gy ); dp->Gy = NULL; } + dp->cofactor = 0; + dp->oid.OIDlen = 0; + + return CRYPT_OK; +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_dp_fill_from_sets.c b/src/ltc/pk/ecc/ecc_dp_fill_from_sets.c new file mode 100644 index 00000000..06c66be4 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_dp_fill_from_sets.c @@ -0,0 +1,76 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +static int hexstrcmp(const char *hexa, const char *hexb) +{ + #define MY_TOLOWER(a) ((((a)>='A')&&((a)<='Z')) ? ((a)|0x60) : (a)) + /* ignore leading zeroes */ + while(*hexa == '0') hexa++; + while(*hexb == '0') hexb++; + /* compare: case insensitive, hexadecimal chars only */ + while (*hexa && *hexb) { + if ( (*hexa < '0' || *hexa > '9') && + (*hexa < 'a' || *hexa > 'f') && + (*hexa < 'A' || *hexa > 'F') ) return 1; + if ( (*hexb < '0' || *hexb > '9') && + (*hexb < 'a' || *hexb > 'f') && + (*hexb < 'A' || *hexb > 'F') ) return 1; + if (MY_TOLOWER(*hexa) != MY_TOLOWER(*hexb)) return 1; + hexa++; + hexb++; + } + if (*hexa == '\0' && *hexb == '\0') return 0; /* success - match */ + return 1; +} + +/* search known curve by curve parameters and fill in missing parameters into dp + * we assume every parameter has the same case (usually uppercase) and no leading zeros + */ +int ecc_dp_fill_from_sets(ltc_ecc_set_type *dp) +{ + ltc_ecc_set_type params; + int x; + + if (!dp) return CRYPT_INVALID_ARG; + if (dp->oid.OIDlen > 0) return CRYPT_OK; + if (!dp->prime || !dp->A || !dp->B || !dp->order || !dp->Gx || !dp->Gy || dp->cofactor == 0) return CRYPT_INVALID_ARG; + + for (x = 0; ltc_ecc_sets[x].size != 0; x++) { + if (hexstrcmp(ltc_ecc_sets[x].prime, dp->prime) == 0 && + hexstrcmp(ltc_ecc_sets[x].A, dp->A) == 0 && + hexstrcmp(ltc_ecc_sets[x].B, dp->B) == 0 && + hexstrcmp(ltc_ecc_sets[x].order, dp->order) == 0 && + hexstrcmp(ltc_ecc_sets[x].Gx, dp->Gx) == 0 && + hexstrcmp(ltc_ecc_sets[x].Gy, dp->Gy) == 0 && + ltc_ecc_sets[x].cofactor == dp->cofactor) { + + params = ltc_ecc_sets[x]; + + /* copy oid */ + dp->oid.OIDlen = params.oid.OIDlen; + XMEMCPY(dp->oid.OID, params.oid.OID, dp->oid.OIDlen * sizeof(dp->oid.OID[0])); + + /* copy name */ + if (dp->name != NULL) XFREE(dp->name); + if ((dp->name = XMALLOC(1+strlen(params.name))) == NULL) return CRYPT_MEM; + strcpy(dp->name, params.name); + + return CRYPT_OK; + } + } + + return CRYPT_INVALID_ARG; +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_dp_from_oid.c b/src/ltc/pk/ecc/ecc_dp_from_oid.c new file mode 100644 index 00000000..2b9d40e6 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_dp_from_oid.c @@ -0,0 +1,86 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +int ecc_dp_set_by_oid(ltc_ecc_set_type *dp, unsigned long *oid, unsigned long oidsize) +{ + int i; + unsigned long len; + + for(i=0; ltc_ecc_sets[i].size != 0; i++) { + if ((oidsize == ltc_ecc_sets[i].oid.OIDlen) && + (XMEM_NEQ(oid, ltc_ecc_sets[i].oid.OID, sizeof(unsigned long) * ltc_ecc_sets[i].oid.OIDlen) == 0)) { + break; + } + } + if (ltc_ecc_sets[i].size == 0) return CRYPT_INVALID_ARG; /* not found */ + + /* a */ + len = (unsigned long)strlen(ltc_ecc_sets[i].A); + if ((dp->A = XMALLOC(1+len)) == NULL) goto cleanup1; + strncpy(dp->A, ltc_ecc_sets[i].A, 1+len); + /* b */ + len = (unsigned long)strlen(ltc_ecc_sets[i].B); + if ((dp->B = XMALLOC(1+len)) == NULL) goto cleanup2; + strncpy(dp->B, ltc_ecc_sets[i].B, 1+len); + /* order */ + len = (unsigned long)strlen(ltc_ecc_sets[i].order); + if ((dp->order = XMALLOC(1+len)) == NULL) goto cleanup3; + strncpy(dp->order, ltc_ecc_sets[i].order, 1+len); + /* prime */ + len = (unsigned long)strlen(ltc_ecc_sets[i].prime); + if ((dp->prime = XMALLOC(1+len)) == NULL) goto cleanup4; + strncpy(dp->prime, ltc_ecc_sets[i].prime, 1+len); + /* gx */ + len = (unsigned long)strlen(ltc_ecc_sets[i].Gx); + if ((dp->Gx = XMALLOC(1+len)) == NULL) goto cleanup5; + strncpy(dp->Gx, ltc_ecc_sets[i].Gx, 1+len); + /* gy */ + len = (unsigned long)strlen(ltc_ecc_sets[i].Gy); + if ((dp->Gy = XMALLOC(1+len)) == NULL) goto cleanup6; + strncpy(dp->Gy, ltc_ecc_sets[i].Gy, 1+len); + /* cofactor & size */ + dp->cofactor = ltc_ecc_sets[i].cofactor; + dp->size = ltc_ecc_sets[i].size; + /* name */ + len = (unsigned long)strlen(ltc_ecc_sets[i].name); + if ((dp->name = XMALLOC(1+len)) == NULL) goto cleanup7; + strncpy(dp->name, ltc_ecc_sets[i].name, 1+len); + /* oid */ + dp->oid.OIDlen = ltc_ecc_sets[i].oid.OIDlen; + XMEMCPY(dp->oid.OID, ltc_ecc_sets[i].oid.OID, dp->oid.OIDlen * sizeof(dp->oid.OID[0])); + /* done - success */ + return CRYPT_OK; + +cleanup7: + XFREE(dp->Gy); +cleanup6: + XFREE(dp->Gx); +cleanup5: + XFREE(dp->prime); +cleanup4: + XFREE(dp->order); +cleanup3: + XFREE(dp->B); +cleanup2: + XFREE(dp->A); +cleanup1: + return CRYPT_MEM; +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_dp_from_params.c b/src/ltc/pk/ecc/ecc_dp_from_params.c new file mode 100644 index 00000000..fe38613a --- /dev/null +++ b/src/ltc/pk/ecc/ecc_dp_from_params.c @@ -0,0 +1,86 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +int ecc_dp_set_bn(ltc_ecc_set_type *dp, void *a, void *b, void *prime, void *order, void *gx, void *gy, unsigned long cofactor) +{ + unsigned char buf[ECC_BUF_SIZE]; + unsigned long len; + + /* a */ + mp_tohex(a, (char *)buf); + len = (unsigned long)strlen((char *)buf); + if ((dp->A = XMALLOC(1+len)) == NULL) goto cleanup1; + strncpy(dp->A, (char*)buf, 1+len); + /* b */ + mp_tohex(b, (char *)buf); + len = (unsigned long)strlen((char *)buf); + if ((dp->B = XMALLOC(1+len)) == NULL) goto cleanup2; + strncpy(dp->B, (char*)buf, 1+len); + /* order */ + mp_tohex(order, (char *)buf); + len = (unsigned long)strlen((char *)buf); + if ((dp->order = XMALLOC(1+len)) == NULL) goto cleanup3; + strncpy(dp->order, (char*)buf, 1+len); + /* prime */ + mp_tohex(prime, (char *)buf); + len = (unsigned long)strlen((char *)buf); + if ((dp->prime = XMALLOC(1+len)) == NULL) goto cleanup4; + strncpy(dp->prime, (char*)buf, 1+len); + /* gx */ + mp_tohex(gx, (char *)buf); + len = (unsigned long)strlen((char *)buf); + if ((dp->Gx = XMALLOC(1+len)) == NULL) goto cleanup5; + strncpy(dp->Gx, (char*)buf, 1+len); + /* gy */ + mp_tohex(gy, (char *)buf); + len = (unsigned long)strlen((char *)buf); + if ((dp->Gy = XMALLOC(1+len)) == NULL) goto cleanup6; + strncpy(dp->Gy, (char*)buf, 1+len); + /* cofactor & size */ + dp->cofactor = cofactor; + dp->size = mp_unsigned_bin_size(prime); + /* see if we can fill in the missing parameters from known curves */ + if ((ecc_dp_fill_from_sets(dp)) != CRYPT_OK) { + /* custom name */ + if ((dp->name = XMALLOC(7)) == NULL) goto cleanup7; + strcpy(dp->name, "custom"); /* XXX-TODO check this */ + /* no oid */ + dp->oid.OIDlen = 0; + } + /* done - success */ + return CRYPT_OK; + + /* XFREE(dp->name); **** warning: statement not reached *** */ +cleanup7: + XFREE(dp->Gy); +cleanup6: + XFREE(dp->Gx); +cleanup5: + XFREE(dp->prime); +cleanup4: + XFREE(dp->order); +cleanup3: + XFREE(dp->B); +cleanup2: + XFREE(dp->A); +cleanup1: + return CRYPT_MEM; +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_dp_init.c b/src/ltc/pk/ecc/ecc_dp_init.c new file mode 100644 index 00000000..36c8f5c6 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_dp_init.c @@ -0,0 +1,36 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +int ecc_dp_init(ltc_ecc_set_type *dp) +{ + if (dp == NULL) return CRYPT_INVALID_ARG; + + dp->name = NULL; + dp->prime = NULL; + dp->A = NULL; + dp->B = NULL; + dp->order = NULL; + dp->Gx = NULL; + dp->Gy = NULL; + dp->oid.OIDlen = 0; + dp->cofactor = 0; + + return CRYPT_OK; +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_dp_set.c b/src/ltc/pk/ecc/ecc_dp_set.c new file mode 100644 index 00000000..33c72816 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_dp_set.c @@ -0,0 +1,100 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" +#include <errno.h> + +#ifdef LTC_MECC + +int ecc_dp_set(ltc_ecc_set_type *dp, char *ch_prime, char *ch_A, char *ch_B, char *ch_order, char *ch_Gx, char *ch_Gy, unsigned long cofactor, char *ch_name, char *oid) +{ + unsigned long l_name, l_prime, l_A, l_B, l_order, l_Gx, l_Gy; + + if (!dp || !ch_prime || !ch_A || !ch_B || !ch_order || !ch_Gx || !ch_Gy || cofactor==0) return CRYPT_INVALID_ARG; + + l_prime = (unsigned long)strlen(ch_prime); + l_A = (unsigned long)strlen(ch_A); + l_B = (unsigned long)strlen(ch_B); + l_order = (unsigned long)strlen(ch_order); + l_Gx = (unsigned long)strlen(ch_Gx); + l_Gy = (unsigned long)strlen(ch_Gy); + + dp->cofactor = cofactor; + + { /* calculate size */ + void *p_num; + mp_init(&p_num); + mp_read_radix(p_num, ch_prime, 16); + dp->size = mp_unsigned_bin_size(p_num); + mp_clear(p_num); + } + + if (dp->name != NULL) { XFREE(dp->name ); dp->name = NULL; } + if (dp->prime != NULL) { XFREE(dp->prime); dp->prime = NULL; } + if (dp->A != NULL) { XFREE(dp->A ); dp->A = NULL; } + if (dp->B != NULL) { XFREE(dp->B ); dp->B = NULL; } + if (dp->order != NULL) { XFREE(dp->order); dp->order = NULL; } + if (dp->Gx != NULL) { XFREE(dp->Gx ); dp->Gx = NULL; } + if (dp->Gy != NULL) { XFREE(dp->Gy ); dp->Gy = NULL; } + + dp->prime = XMALLOC(1+l_prime); strncpy(dp->prime, ch_prime, 1+l_prime); + dp->A = XMALLOC(1+l_A); strncpy(dp->A, ch_A, 1+l_A); + dp->B = XMALLOC(1+l_B); strncpy(dp->B, ch_B, 1+l_B); + dp->order = XMALLOC(1+l_order); strncpy(dp->order, ch_order, 1+l_order); + dp->Gx = XMALLOC(1+l_Gx); strncpy(dp->Gx, ch_Gx, 1+l_Gx); + dp->Gy = XMALLOC(1+l_Gy); strncpy(dp->Gy, ch_Gy, 1+l_Gy); + + /* optional parameters */ + if (ch_name == NULL && oid == NULL) { + (void)ecc_dp_fill_from_sets(dp); + } + else { + if (ch_name != NULL) { + l_name = (unsigned long)strlen(ch_name); + dp->name = XMALLOC(1+l_name); + strncpy(dp->name, ch_name, 1+l_name); + } + + if (oid != NULL) { + char *end_ptr; + unsigned int i = 0; + unsigned long val; + + end_ptr = oid; + while (i < sizeof(dp->oid.OID)/sizeof(dp->oid.OID[0]) && *oid != '\0') { + errno = 0; + val = strtoul(oid, &end_ptr, 10); + if (errno != 0 || oid == end_ptr) break; /* parsing failed */ + if (val > 0xFFFFFFFF) break; /* x64 check */ + dp->oid.OID[i++] = val; + oid = end_ptr; + if (*oid != '.') break; + oid++; + } + if (i == 0 || *end_ptr != '\0') return CRYPT_INVALID_ARG; + dp->oid.OIDlen = i; + } + } + + /* in case the parameters are really custom (unlikely) */ + if (dp->name == NULL) { + dp->name = XMALLOC(7); + strcpy(dp->name, "custom"); + dp->oid.OIDlen = 0; + } + + return CRYPT_OK; +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_encrypt_key.c b/src/ltc/pk/ecc/ecc_encrypt_key.c new file mode 100644 index 00000000..2b94401c --- /dev/null +++ b/src/ltc/pk/ecc/ecc_encrypt_key.c @@ -0,0 +1,134 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ecc_encrypt_key.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** + Encrypt a symmetric key with ECC + @param in The symmetric key you want to encrypt + @param inlen The length of the key to encrypt (octets) + @param out [out] The destination for the ciphertext + @param outlen [in/out] The max size and resulting size of the ciphertext + @param prng An active PRNG state + @param wprng The index of the PRNG you wish to use + @param hash The index of the hash you want to use + @param key The ECC key you want to encrypt to + @return CRYPT_OK if successful +*/ +int ecc_encrypt_key(const unsigned char *in, unsigned long inlen, + unsigned char *out, unsigned long *outlen, + prng_state *prng, int wprng, int hash, + ecc_key *key) +{ + unsigned char *pub_expt, *ecc_shared, *skey; + ecc_key pubkey; + unsigned long x, y, pubkeysize; + int err; + + LTC_ARGCHK(in != NULL); + LTC_ARGCHK(out != NULL); + LTC_ARGCHK(outlen != NULL); + LTC_ARGCHK(key != NULL); + + /* check that wprng/cipher/hash are not invalid */ + if ((err = prng_is_valid(wprng)) != CRYPT_OK) { + return err; + } + + if ((err = hash_is_valid(hash)) != CRYPT_OK) { + return err; + } + + if (inlen > hash_descriptor[hash].hashsize) { + return CRYPT_INVALID_HASH; + } + + /* make a random key and export the public copy */ + if ((err = ecc_make_key_ex(prng, wprng, &pubkey, key->dp)) != CRYPT_OK) { + return err; + } + + pub_expt = XMALLOC(ECC_BUF_SIZE); + ecc_shared = XMALLOC(ECC_BUF_SIZE); + skey = XMALLOC(MAXBLOCKSIZE); + if (pub_expt == NULL || ecc_shared == NULL || skey == NULL) { + if (pub_expt != NULL) { + XFREE(pub_expt); + } + if (ecc_shared != NULL) { + XFREE(ecc_shared); + } + if (skey != NULL) { + XFREE(skey); + } + ecc_free(&pubkey); + return CRYPT_MEM; + } + + pubkeysize = ECC_BUF_SIZE; + if ((err = ecc_export_raw(pub_expt, &pubkeysize, PK_PUBLIC_COMPRESSED, &pubkey)) != CRYPT_OK) { + ecc_free(&pubkey); + goto LBL_ERR; + } + + /* make random key */ + x = ECC_BUF_SIZE; + if ((err = ecc_shared_secret(&pubkey, key, ecc_shared, &x)) != CRYPT_OK) { + ecc_free(&pubkey); + goto LBL_ERR; + } + ecc_free(&pubkey); + y = MAXBLOCKSIZE; + if ((err = hash_memory(hash, ecc_shared, x, skey, &y)) != CRYPT_OK) { + goto LBL_ERR; + } + + /* Encrypt key */ + for (x = 0; x < inlen; x++) { + skey[x] ^= in[x]; + } + + err = der_encode_sequence_multi(out, outlen, + LTC_ASN1_OBJECT_IDENTIFIER, hash_descriptor[hash].OIDlen, hash_descriptor[hash].OID, + LTC_ASN1_OCTET_STRING, pubkeysize, pub_expt, + LTC_ASN1_OCTET_STRING, inlen, skey, + LTC_ASN1_EOL, 0UL, NULL); + +LBL_ERR: +#ifdef LTC_CLEAN_STACK + /* clean up */ + zeromem(pub_expt, ECC_BUF_SIZE); + zeromem(ecc_shared, ECC_BUF_SIZE); + zeromem(skey, MAXBLOCKSIZE); +#endif + + XFREE(skey); + XFREE(ecc_shared); + XFREE(pub_expt); + + return err; +} + +#endif +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ecc_export.c b/src/ltc/pk/ecc/ecc_export.c new file mode 100644 index 00000000..49bb583d --- /dev/null +++ b/src/ltc/pk/ecc/ecc_export.c @@ -0,0 +1,80 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ecc_export.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** + Export an ECC key as a binary packet + @param out [out] Destination for the key + @param outlen [in/out] Max size and resulting size of the exported key + @param type The type of key you want to export (PK_PRIVATE or PK_PUBLIC) + @param key The key to export + @return CRYPT_OK if successful +*/ +int ecc_export(unsigned char *out, unsigned long *outlen, int type, ecc_key *key) +{ + int err; + unsigned char flags[1]; + unsigned long key_size; + + LTC_ARGCHK(out != NULL); + LTC_ARGCHK(outlen != NULL); + LTC_ARGCHK(key != NULL); + + /* type valid? */ + if (key->type != PK_PRIVATE && type == PK_PRIVATE) { + return CRYPT_PK_TYPE_MISMATCH; + } + + if (ltc_ecc_is_valid_idx(key->idx) == 0) { + return CRYPT_INVALID_ARG; + } + + /* we store the NIST byte size */ + key_size = key->dp->size; + + if (type == PK_PRIVATE) { + flags[0] = 1; + err = der_encode_sequence_multi(out, outlen, + LTC_ASN1_BIT_STRING, 1UL, flags, + LTC_ASN1_SHORT_INTEGER, 1UL, &key_size, + LTC_ASN1_INTEGER, 1UL, key->pubkey.x, + LTC_ASN1_INTEGER, 1UL, key->pubkey.y, + LTC_ASN1_INTEGER, 1UL, key->k, + LTC_ASN1_EOL, 0UL, NULL); + } else { + flags[0] = 0; + err = der_encode_sequence_multi(out, outlen, + LTC_ASN1_BIT_STRING, 1UL, flags, + LTC_ASN1_SHORT_INTEGER, 1UL, &key_size, + LTC_ASN1_INTEGER, 1UL, key->pubkey.x, + LTC_ASN1_INTEGER, 1UL, key->pubkey.y, + LTC_ASN1_EOL, 0UL, NULL); + } + + return err; +} + +#endif +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ecc_export_full.c b/src/ltc/pk/ecc/ecc_export_full.c new file mode 100644 index 00000000..6a9fe434 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_export_full.c @@ -0,0 +1,182 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +/** + Export an ECC key as a binary packet + @param out [out] Destination for the key + @param outlen [in/out] Max size and resulting size of the exported key + @param type The type of key you want to export (PK_PRIVATE or PK_PUBLIC) + @param key The key to export + @return CRYPT_OK if successful +*/ + +int ecc_export_full(unsigned char *out, unsigned long *outlen, int type, ecc_key *key) +{ + int err; + void *prime, *order, *a, *b, *gx, *gy; + unsigned char bin_a[256], bin_b[256], bin_k[256], bin_g[512], bin_xy[512]; + unsigned long len_a, len_b, len_k, len_g, len_xy; + unsigned long cofactor, one = 1; + oid_st oid; + ltc_asn1_list seq_fieldid[2], seq_curve[2], seq_ecparams[6], seq_priv[4], asn_ecparams[1]; + + LTC_ARGCHK(out != NULL); + LTC_ARGCHK(outlen != NULL); + LTC_ARGCHK(key != NULL); + + if (key->type != PK_PRIVATE && type == PK_PRIVATE) return CRYPT_PK_TYPE_MISMATCH; + if (ltc_ecc_is_valid_idx(key->idx) == 0) return CRYPT_INVALID_ARG; + if (key->dp == NULL) return CRYPT_INVALID_ARG; + + if ((err = mp_init_multi(&prime, &order, &a, &b, &gx, &gy, NULL)) != CRYPT_OK) return err; + + if ((err = mp_read_radix(prime, key->dp->prime, 16)) != CRYPT_OK) goto error; + if ((err = mp_read_radix(order, key->dp->order, 16)) != CRYPT_OK) goto error; + if ((err = mp_read_radix(b, key->dp->B, 16)) != CRYPT_OK) goto error; + if ((err = mp_read_radix(a, key->dp->A, 16)) != CRYPT_OK) goto error; + if ((err = mp_read_radix(gx, key->dp->Gx, 16)) != CRYPT_OK) goto error; + if ((err = mp_read_radix(gy, key->dp->Gy, 16)) != CRYPT_OK) goto error; + + /* curve param a */ + len_a = mp_unsigned_bin_size(a); + if (len_a > sizeof(bin_a)) { err = CRYPT_BUFFER_OVERFLOW; goto error; } + if ((err = mp_to_unsigned_bin(a, bin_a)) != CRYPT_OK) goto error; + if (len_a == 0) { len_a = 1; bin_a[0] = 0; } /* XXX-TODO hack to handle case a == 0 */ + + /* curve param b */ + len_b = mp_unsigned_bin_size(b); + if (len_b > sizeof(bin_b)) { err = CRYPT_BUFFER_OVERFLOW; goto error; } + if ((err = mp_to_unsigned_bin(b, bin_b)) != CRYPT_OK) goto error; + if (len_b == 0) { len_b = 1; bin_b[0] = 0; } /* XXX-TODO hack to handle case b == 0 */ + + /* base point - we export uncompressed form */ + len_g = sizeof(bin_g); + if ((err = ltc_ecc_export_point(bin_g, &len_g, gx, gy, key->dp->size, 0)) != CRYPT_OK) goto error; + + /* public key */ + len_xy = sizeof(bin_xy); + if ((err = ltc_ecc_export_point(bin_xy, &len_xy, key->pubkey.x, key->pubkey.y, key->dp->size, 0)) != CRYPT_OK) goto error; + + /* co-factor */ + cofactor = key->dp->cofactor; + + /* we support only prime-field EC */ + if ((err = pk_get_oid(EC_PRIME_FIELD, &oid)) != CRYPT_OK) goto error; + + if (type & PK_CURVEOID) { + /* from http://tools.ietf.org/html/rfc5912 + + ECParameters ::= CHOICE { + namedCurve CURVE.&id({NamedCurve}) # OBJECT + } + */ + + /* BEWARE: exporting PK_CURVEOID with custom OID means we're unable to read the curve again */ + if (key->dp->oid.OIDlen == 0) { err = CRYPT_INVALID_ARG; goto error; } + + /* ECParameters used by ECPrivateKey or SubjectPublicKeyInfo below */ + LTC_SET_ASN1(asn_ecparams, 0, LTC_ASN1_OBJECT_IDENTIFIER, key->dp->oid.OID, key->dp->oid.OIDlen); + type &= ~PK_CURVEOID; + } + else { + /* from http://tools.ietf.org/html/rfc3279 + + ECParameters ::= SEQUENCE { # SEQUENCE + version INTEGER { ecpVer1(1) } (ecpVer1), # INTEGER :01 + FieldID ::= SEQUENCE { # SEQUENCE + fieldType FIELD-ID.&id({IOSet}), # OBJECT :prime-field + parameters FIELD-ID.&Type({IOSet}{@fieldType}) # INTEGER + } + Curve ::= SEQUENCE { # SEQUENCE + a FieldElement ::= OCTET STRING # OCTET STRING + b FieldElement ::= OCTET STRING # OCTET STRING + seed BIT STRING OPTIONAL + } + base ECPoint ::= OCTET STRING # OCTET STRING + order INTEGER, # INTEGER + cofactor INTEGER OPTIONAL # INTEGER + } + */ + + /* FieldID SEQUENCE */ + LTC_SET_ASN1(seq_fieldid, 0, LTC_ASN1_OBJECT_IDENTIFIER, oid.OID, oid.OIDlen); + LTC_SET_ASN1(seq_fieldid, 1, LTC_ASN1_INTEGER, prime, 1UL); + + /* Curve SEQUENCE */ + LTC_SET_ASN1(seq_curve, 0, LTC_ASN1_OCTET_STRING, bin_a, len_a); + LTC_SET_ASN1(seq_curve, 1, LTC_ASN1_OCTET_STRING, bin_b, len_b); + + /* ECParameters SEQUENCE */ + LTC_SET_ASN1(seq_ecparams, 0, LTC_ASN1_SHORT_INTEGER, &one, 1UL); + LTC_SET_ASN1(seq_ecparams, 1, LTC_ASN1_SEQUENCE, seq_fieldid, 2UL); + LTC_SET_ASN1(seq_ecparams, 2, LTC_ASN1_SEQUENCE, seq_curve, 2UL); + LTC_SET_ASN1(seq_ecparams, 3, LTC_ASN1_OCTET_STRING, bin_g, len_g); + LTC_SET_ASN1(seq_ecparams, 4, LTC_ASN1_INTEGER, order, 1UL); + LTC_SET_ASN1(seq_ecparams, 5, LTC_ASN1_SHORT_INTEGER, &cofactor, 1UL); + + /* ECParameters used by ECPrivateKey or SubjectPublicKeyInfo below */ + LTC_SET_ASN1(asn_ecparams, 0, LTC_ASN1_SEQUENCE, seq_ecparams, 6UL); + } + + if (type == PK_PRIVATE) { + /* private key format: http://tools.ietf.org/html/rfc5915 + + ECPrivateKey ::= SEQUENCE { # SEQUENCE + version INTEGER { ecPrivkeyVer1(1) } (ecPrivkeyVer1), # INTEGER :01 + privateKey OCTET STRING, # OCTET STRING + [0] ECParameters # see above + [1] publicKey # BIT STRING + } + */ + + /* private key */ + len_k = mp_unsigned_bin_size(key->k); + if (len_k > sizeof(bin_k)) { err = CRYPT_BUFFER_OVERFLOW; goto error; } + if ((err = mp_to_unsigned_bin(key->k, bin_k)) != CRYPT_OK) goto error; + + LTC_SET_ASN1(seq_priv, 0, LTC_ASN1_SHORT_INTEGER, &one, 1UL); + LTC_SET_ASN1(seq_priv, 1, LTC_ASN1_OCTET_STRING, bin_k, len_k); + LTC_SET_ASN1(seq_priv, 2, asn_ecparams[0].type, asn_ecparams[0].data, asn_ecparams[0].size); + LTC_SET_ASN1(seq_priv, 3, LTC_ASN1_RAW_BIT_STRING, bin_xy, 8*len_xy); + seq_priv[2].tag = 0xA0; + seq_priv[3].tag = 0xA1; + + err = der_encode_sequence(seq_priv, 4, out, outlen); + } + else { + /* public key format: http://tools.ietf.org/html/rfc5480 + + SubjectPublicKeyInfo ::= SEQUENCE { # SEQUENCE + AlgorithmIdentifier ::= SEQUENCE { # SEQUENCE + algorithm OBJECT IDENTIFIER # OBJECT :id-ecPublicKey + ECParameters # see above + } + subjectPublicKey BIT STRING # BIT STRING + } + */ + err = der_encode_subject_public_key_info( out, outlen, + PKA_EC, bin_xy, len_xy, + asn_ecparams[0].type, asn_ecparams[0].data, asn_ecparams[0].size ); + } + +error: + mp_clear_multi(prime, order, a, b, gx, gy, NULL); + return err; +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_export_raw.c b/src/ltc/pk/ecc/ecc_export_raw.c new file mode 100644 index 00000000..52062900 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_export_raw.c @@ -0,0 +1,63 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +/** Export raw public or private key (public keys = ANS X9.63 compressed or uncompressed; private keys = raw bytes) + @param out [out] destination of export + @param outlen [in/out] Length of destination and final output size + @param type PK_PRIVATE, PK_PUBLIC or PK_PUBLIC_COMPRESSED + @param key Key to export + Return CRYPT_OK on success +*/ + +int ecc_export_raw(unsigned char *out, unsigned long *outlen, int type, ecc_key *key) +{ + unsigned long size, ksize; + int err; + + LTC_ARGCHK(key != NULL); + LTC_ARGCHK(out != NULL); + LTC_ARGCHK(outlen != NULL); + + if (ltc_ecc_is_valid_idx(key->idx) == 0) { + return CRYPT_INVALID_ARG; + } + size = key->dp->size; + + if (type == PK_PUBLIC_COMPRESSED) { + if ((err = ltc_ecc_export_point(out, outlen, key->pubkey.x, key->pubkey.y, size, 1)) != CRYPT_OK) return err; + } + else if (type == PK_PUBLIC) { + if ((err = ltc_ecc_export_point(out, outlen, key->pubkey.x, key->pubkey.y, size, 0)) != CRYPT_OK) return err; + } + else if (type == PK_PRIVATE) { + if (key->type != PK_PRIVATE) return CRYPT_PK_TYPE_MISMATCH; + *outlen = size; + if (size > *outlen) return CRYPT_BUFFER_OVERFLOW; + if ((ksize = mp_unsigned_bin_size(key->k)) > size) return CRYPT_BUFFER_OVERFLOW; + /* pad and store k */ + if ((err = mp_to_unsigned_bin(key->k, out + (size - ksize))) != CRYPT_OK) return err; + zeromem(out, size - ksize); + } + else { + return CRYPT_INVALID_ARG; + } + + return CRYPT_OK; +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_free.c b/src/ltc/pk/ecc/ecc_free.c new file mode 100644 index 00000000..358c7fe2 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_free.c @@ -0,0 +1,38 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ecc_free.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** + Free an ECC key from memory + @param key The key you wish to free +*/ +void ecc_free(ecc_key *key) +{ + LTC_ARGCHKVD(key != NULL); + mp_clear_multi(key->pubkey.x, key->pubkey.y, key->pubkey.z, key->k, NULL); +} + +#endif +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ecc_get_size.c b/src/ltc/pk/ecc/ecc_get_size.c new file mode 100644 index 00000000..6f24c4e6 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_get_size.c @@ -0,0 +1,42 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ecc_get_size.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** + Get the size of an ECC key + @param key The key to get the size of + @return The size (octets) of the key or INT_MAX on error +*/ +int ecc_get_size(ecc_key *key) +{ + LTC_ARGCHK(key != NULL); + if (ltc_ecc_is_valid_idx(key->idx)) + return key->dp->size; + else + return INT_MAX; /* large value known to cause it to fail when passed to ecc_make_key() */ +} + +#endif +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ecc_import.c b/src/ltc/pk/ecc/ecc_import.c new file mode 100644 index 00000000..95cb7e28 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_import.c @@ -0,0 +1,126 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ecc_import.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** + Import an ECC key from a binary packet + @param in The packet to import + @param inlen The length of the packet + @param key [out] The destination of the import + @return CRYPT_OK if successful, upon error all allocated memory will be freed +*/ +int ecc_import(const unsigned char *in, unsigned long inlen, ecc_key *key) +{ + return ecc_import_ex(in, inlen, key, NULL); +} + +/** + Import an ECC key from a binary packet, using user supplied domain params rather than one of the NIST ones + @param in The packet to import + @param inlen The length of the packet + @param key [out] The destination of the import + @param dp pointer to user supplied params; must be the same as the params used when exporting + @return CRYPT_OK if successful, upon error all allocated memory will be freed +*/ +int ecc_import_ex(const unsigned char *in, unsigned long inlen, ecc_key *key, const ltc_ecc_set_type *dp) +{ + unsigned long key_size; + unsigned char flags[1]; + int err; + + LTC_ARGCHK(in != NULL); + LTC_ARGCHK(key != NULL); + LTC_ARGCHK(ltc_mp.name != NULL); + + /* init key */ + if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, NULL) != CRYPT_OK) { + return CRYPT_MEM; + } + + /* find out what type of key it is */ + if ((err = der_decode_sequence_multi(in, inlen, + LTC_ASN1_BIT_STRING, 1UL, &flags, + LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) { + goto done; + } + + + if (flags[0] == 1) { + /* private key */ + key->type = PK_PRIVATE; + if ((err = der_decode_sequence_multi(in, inlen, + LTC_ASN1_BIT_STRING, 1UL, flags, + LTC_ASN1_SHORT_INTEGER, 1UL, &key_size, + LTC_ASN1_INTEGER, 1UL, key->pubkey.x, + LTC_ASN1_INTEGER, 1UL, key->pubkey.y, + LTC_ASN1_INTEGER, 1UL, key->k, + LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) { + goto done; + } + } else { + /* public key */ + key->type = PK_PUBLIC; + if ((err = der_decode_sequence_multi(in, inlen, + LTC_ASN1_BIT_STRING, 1UL, flags, + LTC_ASN1_SHORT_INTEGER, 1UL, &key_size, + LTC_ASN1_INTEGER, 1UL, key->pubkey.x, + LTC_ASN1_INTEGER, 1UL, key->pubkey.y, + LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) { + goto done; + } + } + + if (dp == NULL) { + /* BEWARE: Here we are looking up the curve params by keysize (neither curve name nor curve oid), + * which might be ambiguous (there can more than one curve for given keysize). + * Thus the chosen curve depends on order of items in ltc_ecc_sets[] - see ecc.c file. + */ + /* find the idx */ + for (key->idx = 0; ltc_ecc_sets[key->idx].size && (unsigned long)ltc_ecc_sets[key->idx].size != key_size; ++key->idx); + if (ltc_ecc_sets[key->idx].size == 0) { + err = CRYPT_INVALID_PACKET; + goto done; + } + key->dp = <c_ecc_sets[key->idx]; + } else { + key->idx = -1; + key->dp = dp; + } + /* set z */ + if ((err = mp_set(key->pubkey.z, 1)) != CRYPT_OK) { goto done; } + + /* is it a point on the curve? */ + if ((err = ltc_ecc_is_point(key->dp, key->pubkey.x, key->pubkey.y)) != CRYPT_OK) { + goto done; + } + + /* we're good */ + return CRYPT_OK; +done: + mp_clear_multi(key->pubkey.x, key->pubkey.y, key->pubkey.z, key->k, NULL); + return err; +} +#endif +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ecc_import_full.c b/src/ltc/pk/ecc/ecc_import_full.c new file mode 100644 index 00000000..9c18f7a8 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_import_full.c @@ -0,0 +1,154 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +int ecc_import_full(const unsigned char *in, unsigned long inlen, ecc_key *key, ltc_ecc_set_type *dp) +{ + void *prime, *order, *a, *b, *gx, *gy; + ltc_asn1_list seq_fieldid[2], seq_curve[3], seq_ecparams[6], seq_priv[4]; + unsigned char bin_a[ECC_MAXSIZE], bin_b[ECC_MAXSIZE], bin_k[ECC_MAXSIZE], bin_g[2*ECC_MAXSIZE+1], bin_xy[2*ECC_MAXSIZE+2], bin_seed[128]; + unsigned long len_a, len_b, len_k, len_g, len_xy, len_oid; + unsigned long cofactor = 0, ecver = 0, pkver = 0, tmpoid[16], curveoid[16]; + int err; + + if ((err = mp_init_multi(&prime, &order, &a, &b, &gx, &gy, NULL)) != CRYPT_OK) return err; + + /* ### 1. try to load public key - no curve parameters just curve OID */ + + len_xy = sizeof(bin_xy); + err = der_decode_subject_public_key_info_ex(in, inlen, PKA_EC, bin_xy, &len_xy, LTC_ASN1_OBJECT_IDENTIFIER, curveoid, 16UL, &len_oid); + if (err == CRYPT_OK) { + /* load curve parameters for given curve OID */ + if ((err = ecc_dp_set_by_oid(dp, curveoid, len_oid)) != CRYPT_OK) { goto error; } + /* load public key */ + if ((err = ecc_import_raw(bin_xy, len_xy, key, dp)) != CRYPT_OK) { goto error; } + goto success; + } + + /* ### 2. try to load public key - curve parameters included */ + + /* ECParameters SEQUENCE */ + LTC_SET_ASN1(seq_ecparams, 0, LTC_ASN1_SHORT_INTEGER, &ecver, 1UL); + LTC_SET_ASN1(seq_ecparams, 1, LTC_ASN1_SEQUENCE, seq_fieldid, 2UL); + LTC_SET_ASN1(seq_ecparams, 2, LTC_ASN1_SEQUENCE, seq_curve, 3UL); + LTC_SET_ASN1(seq_ecparams, 3, LTC_ASN1_OCTET_STRING, bin_g, (unsigned long)2*ECC_MAXSIZE+1); + LTC_SET_ASN1(seq_ecparams, 4, LTC_ASN1_INTEGER, order, 1UL); + LTC_SET_ASN1(seq_ecparams, 5, LTC_ASN1_SHORT_INTEGER, &cofactor, 1UL); + seq_ecparams[5].optional = 1; + /* FieldID SEQUENCE */ + LTC_SET_ASN1(seq_fieldid, 0, LTC_ASN1_OBJECT_IDENTIFIER, tmpoid, 16UL); + LTC_SET_ASN1(seq_fieldid, 1, LTC_ASN1_INTEGER, prime, 1UL); + /* Curve SEQUENCE */ + LTC_SET_ASN1(seq_curve, 0, LTC_ASN1_OCTET_STRING, bin_a, (unsigned long)ECC_MAXSIZE); + LTC_SET_ASN1(seq_curve, 1, LTC_ASN1_OCTET_STRING, bin_b, (unsigned long)ECC_MAXSIZE); + LTC_SET_ASN1(seq_curve, 2, LTC_ASN1_RAW_BIT_STRING, bin_seed, (unsigned long)8*128); + seq_curve[2].optional = 1; + /* try to load public key */ + len_xy = sizeof(bin_xy); + err = der_decode_subject_public_key_info(in, inlen, PKA_EC, bin_xy, &len_xy, LTC_ASN1_SEQUENCE, seq_ecparams, 6); + + if (err == CRYPT_OK) { + len_a = seq_curve[0].size; + len_b = seq_curve[1].size; + len_g = seq_ecparams[3].size; + /* create bignums */ + if ((err = mp_read_unsigned_bin(a, bin_a, len_a)) != CRYPT_OK) { goto error; } + if ((err = mp_read_unsigned_bin(b, bin_b, len_b)) != CRYPT_OK) { goto error; } + if ((err = ltc_ecc_import_point(bin_g, len_g, prime, a, b, gx, gy)) != CRYPT_OK) { goto error; } + /* load curve parameters */ + if ((err = ecc_dp_set_bn(dp, a, b, prime, order, gx, gy, cofactor)) != CRYPT_OK) { goto error; } + /* load public key */ + if ((err = ecc_import_raw(bin_xy, len_xy, key, dp)) != CRYPT_OK) { goto error; } + goto success; + } + + /* ### 3. try to load private key - no curve parameters just curve OID */ + + /* ECPrivateKey SEQUENCE */ + LTC_SET_ASN1(seq_priv, 0, LTC_ASN1_SHORT_INTEGER, &pkver, 1UL); + LTC_SET_ASN1(seq_priv, 1, LTC_ASN1_OCTET_STRING, bin_k, (unsigned long)ECC_MAXSIZE); + LTC_SET_ASN1(seq_priv, 2, LTC_ASN1_OBJECT_IDENTIFIER, curveoid, 16UL); + LTC_SET_ASN1(seq_priv, 3, LTC_ASN1_RAW_BIT_STRING, bin_xy, (unsigned long)8*(2*ECC_MAXSIZE+2)); + seq_priv[2].tag = 0xA0; /* context specific 0 */ + seq_priv[3].tag = 0xA1; /* context specific 1 */ + /* try to load private key */ + err = der_decode_sequence(in, inlen, seq_priv, 4); + + if (err == CRYPT_OK) { + /* load curve parameters for given curve OID */ + if ((err = ecc_dp_set_by_oid(dp, curveoid, seq_priv[2].size)) != CRYPT_OK) { goto error; } + /* load private+public key */ + if ((err = ecc_import_raw(bin_k, seq_priv[1].size, key, dp)) != CRYPT_OK) { goto error; } + goto success; + } + + /* ### 4. try to load private key - curve parameters included */ + + /* ECPrivateKey SEQUENCE */ + LTC_SET_ASN1(seq_priv, 0, LTC_ASN1_SHORT_INTEGER, &pkver, 1UL); + LTC_SET_ASN1(seq_priv, 1, LTC_ASN1_OCTET_STRING, bin_k, (unsigned long)ECC_MAXSIZE); + LTC_SET_ASN1(seq_priv, 2, LTC_ASN1_SEQUENCE, seq_ecparams, 6UL); + LTC_SET_ASN1(seq_priv, 3, LTC_ASN1_RAW_BIT_STRING, bin_xy, (unsigned long)8*(2*ECC_MAXSIZE+2)); + seq_priv[2].tag = 0xA0; /* context specific 0 */ + seq_priv[3].tag = 0xA1; /* context specific 1 */ + /* ECParameters SEQUENCE */ + LTC_SET_ASN1(seq_ecparams, 0, LTC_ASN1_SHORT_INTEGER, &ecver, 1UL); + LTC_SET_ASN1(seq_ecparams, 1, LTC_ASN1_SEQUENCE, seq_fieldid, 2UL); + LTC_SET_ASN1(seq_ecparams, 2, LTC_ASN1_SEQUENCE, seq_curve, 3UL); + LTC_SET_ASN1(seq_ecparams, 3, LTC_ASN1_OCTET_STRING, bin_g, (unsigned long)2*ECC_MAXSIZE+1); + LTC_SET_ASN1(seq_ecparams, 4, LTC_ASN1_INTEGER, order, 1UL); + LTC_SET_ASN1(seq_ecparams, 5, LTC_ASN1_SHORT_INTEGER, &cofactor, 1UL); + seq_ecparams[5].optional = 1; + /* FieldID SEQUENCE */ + LTC_SET_ASN1(seq_fieldid, 0, LTC_ASN1_OBJECT_IDENTIFIER, tmpoid, 16UL); + LTC_SET_ASN1(seq_fieldid, 1, LTC_ASN1_INTEGER, prime, 1UL); + /* Curve SEQUENCE */ + LTC_SET_ASN1(seq_curve, 0, LTC_ASN1_OCTET_STRING, bin_a, (unsigned long)ECC_MAXSIZE); + LTC_SET_ASN1(seq_curve, 1, LTC_ASN1_OCTET_STRING, bin_b, (unsigned long)ECC_MAXSIZE); + LTC_SET_ASN1(seq_curve, 2, LTC_ASN1_RAW_BIT_STRING, bin_seed, (unsigned long)8*128); + seq_curve[2].optional = 1; + /* try to load private key */ + err = der_decode_sequence(in, inlen, seq_priv, 4); + if (err == CRYPT_OK) { + len_k = seq_priv[1].size; + len_xy = seq_priv[3].size; + len_a = seq_curve[0].size; + len_b = seq_curve[1].size; + len_g = seq_ecparams[3].size; + /* create bignums */ + if ((err = mp_read_unsigned_bin(a, bin_a, len_a)) != CRYPT_OK) { goto error; } + if ((err = mp_read_unsigned_bin(b, bin_b, len_b)) != CRYPT_OK) { goto error; } + if ((err = ltc_ecc_import_point(bin_g, len_g, prime, a, b, gx, gy)) != CRYPT_OK) { goto error; } + /* load curve parameters */ + if ((err = ecc_dp_set_bn(dp, a, b, prime, order, gx, gy, cofactor)) != CRYPT_OK) { goto error; } + /* load private+public key */ + if ((err = ecc_import_raw(bin_k, len_k, key, dp)) != CRYPT_OK) { goto error; } + goto success; + } + + /* ### 5. backward compatibility - try to load old-DER format */ + if ((err = ecc_import(in, inlen, key)) != CRYPT_OK) { goto error; } + +success: + err = CRYPT_OK; +error: + mp_clear_multi(prime, order, a, b, gx, gy, NULL); + return err; +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_import_pkcs8.c b/src/ltc/pk/ecc/ecc_import_pkcs8.c new file mode 100644 index 00000000..83228597 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_import_pkcs8.c @@ -0,0 +1,161 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +int ecc_import_pkcs8(const unsigned char *in, unsigned long inlen, + const void *pwd, unsigned long pwdlen, + ecc_key *key, ltc_ecc_set_type *dp) +{ + int err; + void *zero, *one, *iter; + unsigned char *buf1=NULL, *buf2=NULL; + unsigned long buf1len, buf2len; + unsigned long oid[16]; + oid_st ecoid; + ltc_asn1_list alg_seq[2], top_seq[3]; + ltc_asn1_list alg_seq_e[2], key_seq_e[2], top_seq_e[2]; + unsigned char *decrypted=NULL; + unsigned long decryptedlen; + void *prime, *order, *a, *b, *gx, *gy; + ltc_asn1_list seq_fieldid[2], seq_curve[3], seq_ecparams[6], seq_priv[4]; + unsigned char bin_a[ECC_MAXSIZE], bin_b[ECC_MAXSIZE], bin_k[ECC_MAXSIZE], bin_g[2*ECC_MAXSIZE+1], bin_xy[2*ECC_MAXSIZE+2], bin_seed[128]; + unsigned long len_a, len_b, len_g; + unsigned long cofactor = 0, ecver = 0, tmpoid[16], curveoid[16]; + + LTC_ARGCHK(in != NULL); + LTC_ARGCHK(key != NULL); + LTC_ARGCHK(ltc_mp.name != NULL); + + /* get EC alg oid */ + err = pk_get_oid(PKA_EC, &ecoid); + if (err != CRYPT_OK) { goto LBL_NOFREE; } + + /* alloc buffers */ + buf1len = inlen; /* approx. guess */ + buf1 = XMALLOC(buf1len); + if (buf1 == NULL) { err = CRYPT_MEM; goto LBL_NOFREE; } + buf2len = inlen; /* approx. guess */ + buf2 = XMALLOC(buf2len); + if (buf2 == NULL) { err = CRYPT_MEM; goto LBL_FREE; } + + /* init key */ + err = mp_init_multi(&prime, &order, &a, &b, &gx, &gy, &zero, &one, &iter, NULL); + if (err != CRYPT_OK) { goto LBL_NOCLEAR; } + + /* try to decode encrypted priv key */ + LTC_SET_ASN1(key_seq_e, 0, LTC_ASN1_OCTET_STRING, buf1, buf1len); + LTC_SET_ASN1(key_seq_e, 1, LTC_ASN1_INTEGER, iter, 1UL); + LTC_SET_ASN1(alg_seq_e, 0, LTC_ASN1_OBJECT_IDENTIFIER, oid, 16UL); + LTC_SET_ASN1(alg_seq_e, 1, LTC_ASN1_SEQUENCE, key_seq_e, 2UL); + LTC_SET_ASN1(top_seq_e, 0, LTC_ASN1_SEQUENCE, alg_seq_e, 2UL); + LTC_SET_ASN1(top_seq_e, 1, LTC_ASN1_OCTET_STRING, buf2, buf2len); + err=der_decode_sequence(in, inlen, top_seq_e, 2UL); + if (err == CRYPT_OK) { + LTC_UNUSED_PARAM(pwd); + LTC_UNUSED_PARAM(pwdlen); + /* unsigned long icount = mp_get_int(iter); */ + /* XXX: TODO decrypt buf1 with a key derived form password + salt + iter */ + /* fprintf(stderr, "XXX-DEBUG: gonna decrypt: iter=%ld salt.len=%ld encdata.len=%ld\n", icount, key_seq_e[0].size, top_seq_e[1].size); */ + err = CRYPT_PK_INVALID_TYPE; + goto LBL_ERR; + } + else { + decrypted = (unsigned char*)in; + decryptedlen = inlen; + } + + /* try to decode unencrypted priv key - curve defined by OID */ + LTC_SET_ASN1(alg_seq, 0, LTC_ASN1_OBJECT_IDENTIFIER, oid, 16UL); + LTC_SET_ASN1(alg_seq, 1, LTC_ASN1_OBJECT_IDENTIFIER, curveoid, 16UL); + LTC_SET_ASN1(top_seq, 0, LTC_ASN1_INTEGER, zero, 1UL); + LTC_SET_ASN1(top_seq, 1, LTC_ASN1_SEQUENCE, alg_seq, 2UL); + LTC_SET_ASN1(top_seq, 2, LTC_ASN1_OCTET_STRING, buf1, buf1len); + err=der_decode_sequence(decrypted, decryptedlen, top_seq, 3UL); + if (err == CRYPT_OK) { + /* load curve parameters for given curve OID */ + err = ecc_dp_set_by_oid(dp, curveoid, alg_seq[1].size); + if (err != CRYPT_OK) { goto LBL_ERR; } + } + else { + /* try to decode unencrypted priv key - curve defined by params */ + /* ECParameters SEQUENCE */ + LTC_SET_ASN1(seq_ecparams, 0, LTC_ASN1_SHORT_INTEGER, &ecver, 1UL); + LTC_SET_ASN1(seq_ecparams, 1, LTC_ASN1_SEQUENCE, seq_fieldid, 2UL); + LTC_SET_ASN1(seq_ecparams, 2, LTC_ASN1_SEQUENCE, seq_curve, 3UL); + LTC_SET_ASN1(seq_ecparams, 3, LTC_ASN1_OCTET_STRING, bin_g, (unsigned long)2*ECC_MAXSIZE+1); + LTC_SET_ASN1(seq_ecparams, 4, LTC_ASN1_INTEGER, order, 1UL); + LTC_SET_ASN1(seq_ecparams, 5, LTC_ASN1_SHORT_INTEGER, &cofactor, 1UL); + seq_ecparams[5].optional = 1; + /* FieldID SEQUENCE */ + LTC_SET_ASN1(seq_fieldid, 0, LTC_ASN1_OBJECT_IDENTIFIER, tmpoid, 16UL); + LTC_SET_ASN1(seq_fieldid, 1, LTC_ASN1_INTEGER, prime, 1UL); + /* Curve SEQUENCE */ + LTC_SET_ASN1(seq_curve, 0, LTC_ASN1_OCTET_STRING, bin_a, (unsigned long)ECC_MAXSIZE); + LTC_SET_ASN1(seq_curve, 1, LTC_ASN1_OCTET_STRING, bin_b, (unsigned long)ECC_MAXSIZE); + LTC_SET_ASN1(seq_curve, 2, LTC_ASN1_RAW_BIT_STRING, bin_seed, (unsigned long)8*128); + /* */ + LTC_SET_ASN1(alg_seq, 0, LTC_ASN1_OBJECT_IDENTIFIER, oid, 16UL); + LTC_SET_ASN1(alg_seq, 1, LTC_ASN1_SEQUENCE, seq_ecparams, 6UL); + LTC_SET_ASN1(top_seq, 0, LTC_ASN1_INTEGER, zero, 1UL); + LTC_SET_ASN1(top_seq, 1, LTC_ASN1_SEQUENCE, alg_seq, 2UL); + LTC_SET_ASN1(top_seq, 2, LTC_ASN1_OCTET_STRING, buf1, buf1len); + seq_curve[2].optional = 1; + err=der_decode_sequence(decrypted, decryptedlen, top_seq, 3UL); + if (err != CRYPT_OK) { goto LBL_ERR; } + len_a = seq_curve[0].size; + len_b = seq_curve[1].size; + len_g = seq_ecparams[3].size; + /* create bignums */ + if ((err = mp_read_unsigned_bin(a, bin_a, len_a)) != CRYPT_OK) { goto LBL_ERR; } + if ((err = mp_read_unsigned_bin(b, bin_b, len_b)) != CRYPT_OK) { goto LBL_ERR; } + if ((err = ltc_ecc_import_point(bin_g, len_g, prime, a, b, gx, gy)) != CRYPT_OK) { goto LBL_ERR; } + /* load curve parameters */ + if ((err = ecc_dp_set_bn(dp, a, b, prime, order, gx, gy, cofactor)) != CRYPT_OK) { goto LBL_ERR; } + } + + /* check alg oid */ + if ((alg_seq[0].size != ecoid.OIDlen) || + XMEMCMP(ecoid.OID, alg_seq[0].data, ecoid.OIDlen * sizeof(ecoid.OID[0]))) { + err = CRYPT_PK_INVALID_TYPE; + goto LBL_ERR; + } + + /* ECPrivateKey SEQUENCE */ + LTC_SET_ASN1(seq_priv, 0, LTC_ASN1_SHORT_INTEGER, &one, 1UL); + LTC_SET_ASN1(seq_priv, 1, LTC_ASN1_OCTET_STRING, bin_k, (unsigned long)ECC_MAXSIZE); + LTC_SET_ASN1(seq_priv, 2, LTC_ASN1_RAW_BIT_STRING, bin_xy, (unsigned long)8*(2*ECC_MAXSIZE+2)); + seq_priv[2].tag = 0xA1; /* context specific 1 */ + /* try to load private key */ + err = der_decode_sequence(buf1, top_seq[2].size, seq_priv, 3); + if (err != CRYPT_OK) { goto LBL_ERR; } + /* load private+public key */ + if ((err = ecc_import_raw(bin_k, seq_priv[1].size, key, dp)) != CRYPT_OK) { goto LBL_ERR; } + /* success */ + return err; + +LBL_ERR: + mp_clear_multi(prime, order, a, b, gx, gy, NULL); +LBL_NOCLEAR: + XFREE(buf2); +LBL_FREE: + XFREE(buf1); +LBL_NOFREE: + return err; +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_import_raw.c b/src/ltc/pk/ecc/ecc_import_raw.c new file mode 100644 index 00000000..1ea4bb1e --- /dev/null +++ b/src/ltc/pk/ecc/ecc_import_raw.c @@ -0,0 +1,100 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +/** Import raw public or private key (public keys = ANSI X9.63 compressed or uncompressed; private keys = raw bytes) + @param in The input data to read + @param inlen The length of the input data + @param key [out] destination to store imported key + @param dp Curve parameters + Return CRYPT_OK on success +*/ + +int ecc_import_raw(const unsigned char *in, unsigned long inlen, ecc_key *key, ltc_ecc_set_type *dp) +{ + int err, type = -1; + unsigned long size = 0; + void *prime, *a, *b; + ecc_point *base; + + LTC_ARGCHK(in != NULL); + LTC_ARGCHK(key != NULL); + LTC_ARGCHK(dp != NULL); + + /* init key + temporary numbers */ + if (mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, &prime, &a, &b, NULL) != CRYPT_OK) { + return CRYPT_MEM; + } + + if (inlen <= (unsigned long)dp->size) { + /* read PRIVATE key */ + type = PK_PRIVATE; + size = inlen; + /* load private k */ + if ((err = mp_read_unsigned_bin(key->k, (unsigned char *)in, size)) != CRYPT_OK) { + goto cleanup; + } + if (mp_iszero(key->k)) { + err = CRYPT_INVALID_PACKET; + goto cleanup; + } + /* init base point */ + if ((base = ltc_ecc_new_point()) == NULL) { + err = CRYPT_MEM; + goto cleanup; + } + /* load prime + base point */ + if ((err = mp_read_radix(prime, dp->prime, 16)) != CRYPT_OK) { goto cleanup; } + if ((err = mp_read_radix(base->x, dp->Gx, 16)) != CRYPT_OK) { goto cleanup; } + if ((err = mp_read_radix(base->y, dp->Gy, 16)) != CRYPT_OK) { goto cleanup; } + if ((err = mp_set(base->z, 1)) != CRYPT_OK) { goto cleanup; } + /* make the public key */ + if ((err = mp_read_radix(a, dp->A, 16)) != CRYPT_OK) { goto cleanup; } + if ((err = ltc_mp.ecc_ptmul(key->k, base, &key->pubkey, a, prime, 1)) != CRYPT_OK) { goto cleanup; } + /* cleanup */ + ltc_ecc_del_point(base); + } + else { + /* read PUBLIC key */ + type = PK_PUBLIC; + /* load prime + A + B */ + if ((err = mp_read_radix(prime, dp->prime, 16)) != CRYPT_OK) { goto cleanup; } + if ((err = mp_read_radix(b, dp->B, 16)) != CRYPT_OK) { goto cleanup; } + if ((err = mp_read_radix(a, dp->A, 16)) != CRYPT_OK) { goto cleanup; } + err = ltc_ecc_import_point(in, inlen, prime, a, b, key->pubkey.x, key->pubkey.y); + if (err != CRYPT_OK) { goto cleanup; } + if ((err = mp_set(key->pubkey.z, 1)) != CRYPT_OK) { goto cleanup; } + } + + if ((err = ltc_ecc_is_point(dp, key->pubkey.x, key->pubkey.y)) != CRYPT_OK) { + err = CRYPT_INVALID_PACKET; + goto cleanup; + } + + key->type = type; + key->idx = -1; + key->dp = dp; + + /* we're done */ + mp_clear_multi(prime, a, b, NULL); + return CRYPT_OK; +cleanup: + mp_clear_multi(key->pubkey.x, key->pubkey.y, key->pubkey.z, key->k, prime, a, b, NULL); + return err; +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_make_key.c b/src/ltc/pk/ecc/ecc_make_key.c new file mode 100644 index 00000000..1568b102 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_make_key.c @@ -0,0 +1,141 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ecc_make_key.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** + Make a new ECC key + @param prng An active PRNG state + @param wprng The index of the PRNG you wish to use + @param keysize The keysize for the new key (in octets from 20 to 65 bytes) + @param key [out] Destination of the newly created key + @return CRYPT_OK if successful, upon error all allocated memory will be freed +*/ +int ecc_make_key(prng_state *prng, int wprng, int keysize, ecc_key *key) +{ + /* BEWARE: Here we are looking up the curve params by keysize (neither curve name nor curve oid), + * which might be ambiguous (there can more than one curve for given keysize). + * Thus the chosen curve depends on order of items in ltc_ecc_sets[] - see ecc.c file. + */ + int x, err; + + /* find key size */ + for (x = 0; (keysize > ltc_ecc_sets[x].size) && (ltc_ecc_sets[x].size != 0); x++); + keysize = ltc_ecc_sets[x].size; + + if (keysize > ECC_MAXSIZE || ltc_ecc_sets[x].size == 0) { + return CRYPT_INVALID_KEYSIZE; + } + err = ecc_make_key_ex(prng, wprng, key, <c_ecc_sets[x]); + key->idx = x; + return err; +} + +int ecc_make_key_ex(prng_state *prng, int wprng, ecc_key *key, const ltc_ecc_set_type *dp) +{ + int err; + ecc_point *base; + void *prime, *order, *a; + unsigned char *buf; + int keysize, orderbits; + + LTC_ARGCHK(key != NULL); + LTC_ARGCHK(ltc_mp.name != NULL); + LTC_ARGCHK(dp != NULL); + + /* good prng? */ + if ((err = prng_is_valid(wprng)) != CRYPT_OK) { + return err; + } + + key->idx = -1; + key->dp = dp; + keysize = dp->size; + + /* allocate ram */ + base = NULL; + buf = XMALLOC(ECC_MAXSIZE); + if (buf == NULL) { + return CRYPT_MEM; + } + + /* make up random string */ + if (prng_descriptor[wprng].read(buf, (unsigned long)keysize, prng) != (unsigned long)keysize) { + err = CRYPT_ERROR_READPRNG; + goto ERR_BUF; + } + + /* setup the key variables */ + if ((err = mp_init_multi(&key->pubkey.x, &key->pubkey.y, &key->pubkey.z, &key->k, &prime, &order, &a, NULL)) != CRYPT_OK) { + goto ERR_BUF; + } + base = ltc_ecc_new_point(); + if (base == NULL) { + err = CRYPT_MEM; + goto errkey; + } + + /* read in the specs for this key */ + if ((err = mp_read_radix(prime, (char *)key->dp->prime, 16)) != CRYPT_OK) { goto errkey; } + if ((err = mp_read_radix(order, (char *)key->dp->order, 16)) != CRYPT_OK) { goto errkey; } + if ((err = mp_read_radix(base->x, (char *)key->dp->Gx, 16)) != CRYPT_OK) { goto errkey; } + if ((err = mp_read_radix(base->y, (char *)key->dp->Gy, 16)) != CRYPT_OK) { goto errkey; } + if ((err = mp_set(base->z, 1)) != CRYPT_OK) { goto errkey; } + if ((err = mp_read_unsigned_bin(key->k, (unsigned char *)buf, keysize)) != CRYPT_OK) { goto errkey; } + + /* ECC key pair generation according to FIPS-186-4 (B.4.2 Key Pair Generation by Testing Candidates): + * the generated private key k should be the range [1, order-1] + * a/ N = bitlen(order) + * b/ generate N random bits and convert them into big integer k + * c/ if k not in [1, order-1] go to b/ + * e/ Q = k*G + */ + orderbits = mp_count_bits(order); + do { + if ((err = rand_bn_bits(key->k, orderbits, prng, wprng)) != CRYPT_OK) { goto errkey; } + } while (mp_iszero(key->k) || mp_cmp(key->k, order) != LTC_MP_LT); + + /* make the public key */ + if ((err = mp_read_radix(a, (char *)key->dp->A, 16)) != CRYPT_OK) { goto errkey; } + if ((err = ltc_mp.ecc_ptmul(key->k, base, &key->pubkey, a, prime, 1)) != CRYPT_OK) { goto errkey; } + key->type = PK_PRIVATE; + + /* free up ram */ + err = CRYPT_OK; + goto cleanup; +errkey: + mp_clear_multi(key->pubkey.x, key->pubkey.y, key->pubkey.z, key->k, NULL); +cleanup: + ltc_ecc_del_point(base); + mp_clear_multi(prime, order, a, NULL); +ERR_BUF: +#ifdef LTC_CLEAN_STACK + zeromem(buf, ECC_MAXSIZE); +#endif + XFREE(buf); + return err; +} + +#endif +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ecc_shared_secret.c b/src/ltc/pk/ecc/ecc_shared_secret.c new file mode 100644 index 00000000..df22f5c3 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_shared_secret.c @@ -0,0 +1,95 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ecc_shared_secret.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** + Create an ECC shared secret between two keys + @param private_key The private ECC key + @param public_key The public key + @param out [out] Destination of the shared secret (Conforms to EC-DH from ANSI X9.63) + @param outlen [in/out] The max size and resulting size of the shared secret + @return CRYPT_OK if successful +*/ +int ecc_shared_secret(ecc_key *private_key, ecc_key *public_key, + unsigned char *out, unsigned long *outlen) +{ + unsigned long x; + ecc_point *result; + void *prime, *a; + int err; + + LTC_ARGCHK(private_key != NULL); + LTC_ARGCHK(public_key != NULL); + LTC_ARGCHK(out != NULL); + LTC_ARGCHK(outlen != NULL); + + /* type valid? */ + if (private_key->type != PK_PRIVATE) { + return CRYPT_PK_NOT_PRIVATE; + } + + if (ltc_ecc_is_valid_idx(private_key->idx) == 0 || ltc_ecc_is_valid_idx(public_key->idx) == 0) { + return CRYPT_INVALID_ARG; + } + +/* XXX FIXME names can be different in some situations + if (XSTRCMP(private_key->dp->name, public_key->dp->name) != 0) { + return CRYPT_PK_TYPE_MISMATCH; + } +*/ + /* make new point */ + result = ltc_ecc_new_point(); + if (result == NULL) { + return CRYPT_MEM; + } + + if ((err = mp_init_multi(&prime, &a, NULL)) != CRYPT_OK) { + ltc_ecc_del_point(result); + return err; + } + + if ((err = mp_read_radix(prime, (char *)private_key->dp->prime, 16)) != CRYPT_OK) { goto done; } + if ((err = mp_read_radix(a, (char *)private_key->dp->A, 16)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.ecc_ptmul(private_key->k, &public_key->pubkey, result, a, prime, 1)) != CRYPT_OK) { goto done; } + + x = (unsigned long)mp_unsigned_bin_size(prime); + if (*outlen < x) { + *outlen = x; + err = CRYPT_BUFFER_OVERFLOW; + goto done; + } + zeromem(out, x); + if ((err = mp_to_unsigned_bin(result->x, out + (x - mp_unsigned_bin_size(result->x)))) != CRYPT_OK) { goto done; } + + err = CRYPT_OK; + *outlen = x; +done: + mp_clear_multi(prime, a, NULL); + ltc_ecc_del_point(result); + return err; +} + +#endif +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ecc_sign_hash.c b/src/ltc/pk/ecc/ecc_sign_hash.c new file mode 100644 index 00000000..7f1859c6 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_sign_hash.c @@ -0,0 +1,165 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +/** + @file ecc_sign_hash.c + ECC Crypto, Tom St Denis +*/ + +static int ecc_sign_hash_ex(const unsigned char *in, unsigned long inlen, + unsigned char *out, unsigned long *outlen, + prng_state *prng, int wprng, ecc_key *key, int sigformat) +{ + ecc_key pubkey; + void *r, *s, *e, *p; + int err; + unsigned long pbits, pbytes, i, shift_right; + unsigned char ch, buf[MAXBLOCKSIZE]; + + LTC_ARGCHK(in != NULL); + LTC_ARGCHK(out != NULL); + LTC_ARGCHK(outlen != NULL); + LTC_ARGCHK(key != NULL); + + /* is this a private key? */ + if (key->type != PK_PRIVATE) { + return CRYPT_PK_NOT_PRIVATE; + } + + /* is the IDX valid ? */ + if (ltc_ecc_is_valid_idx(key->idx) != 1) { + return CRYPT_PK_INVALID_TYPE; + } + + if ((err = prng_is_valid(wprng)) != CRYPT_OK) { + return err; + } + + /* init the bignums */ + if ((err = mp_init_multi(&r, &s, &p, &e, NULL)) != CRYPT_OK) { + return err; + } + if ((err = mp_read_radix(p, (char *)key->dp->order, 16)) != CRYPT_OK) { goto errnokey; } + + /* get the hash and load it as a bignum into 'e' */ + pbits = mp_count_bits(p); + pbytes = (pbits+7) >> 3; + if (pbits > inlen*8) { + if ((err = mp_read_unsigned_bin(e, (unsigned char *)in, inlen)) != CRYPT_OK) { goto errnokey; } + } + else if (pbits % 8 == 0) { + if ((err = mp_read_unsigned_bin(e, (unsigned char *)in, pbytes)) != CRYPT_OK) { goto errnokey; } + } + else { + shift_right = 8 - pbits % 8; + for (i=0, ch=0; i<pbytes; i++) { + buf[i] = ch; + ch = (in[i] << (8-shift_right)); + buf[i] = buf[i] ^ (in[i] >> shift_right); + } + if ((err = mp_read_unsigned_bin(e, (unsigned char *)buf, pbytes)) != CRYPT_OK) { goto errnokey; } + } + + /* make up a key and export the public copy */ + for (;;) { + if ((err = ecc_make_key_ex(prng, wprng, &pubkey, key->dp)) != CRYPT_OK) { goto errnokey; } + + /* find r = x1 mod n */ + if ((err = mp_mod(pubkey.pubkey.x, p, r)) != CRYPT_OK) { goto error; } + + if (mp_iszero(r) == LTC_MP_YES) { + ecc_free(&pubkey); + } + else { + /* find s = (e + xr)/k */ + if ((err = mp_invmod(pubkey.k, p, pubkey.k)) != CRYPT_OK) { goto error; } /* k = 1/k */ + if ((err = mp_mulmod(key->k, r, p, s)) != CRYPT_OK) { goto error; } /* s = xr */ + if ((err = mp_add(e, s, s)) != CRYPT_OK) { goto error; } /* s = e + xr */ + if ((err = mp_mod(s, p, s)) != CRYPT_OK) { goto error; } /* s = e + xr */ + if ((err = mp_mulmod(s, pubkey.k, p, s)) != CRYPT_OK) { goto error; } /* s = (e + xr)/k */ + ecc_free(&pubkey); + if (mp_iszero(s) == LTC_MP_NO) { + break; + } + } + } + + if (sigformat == 1) { + /* RFC7518 format */ + if (*outlen < 2*pbytes) { err = CRYPT_MEM; goto errnokey; } + zeromem(out, 2*pbytes); + i = mp_unsigned_bin_size(r); + if ((err = mp_to_unsigned_bin(r, out + (pbytes - i))) != CRYPT_OK) { goto errnokey; } + i = mp_unsigned_bin_size(s); + if ((err = mp_to_unsigned_bin(s, out + (2*pbytes - i))) != CRYPT_OK) { goto errnokey; } + *outlen = 2*pbytes; + err = CRYPT_OK; + } + else { + /* store as ASN.1 SEQUENCE { r, s -- integer } */ + err = der_encode_sequence_multi(out, outlen, + LTC_ASN1_INTEGER, 1UL, r, + LTC_ASN1_INTEGER, 1UL, s, + LTC_ASN1_EOL, 0UL, NULL); + } + goto errnokey; +error: + ecc_free(&pubkey); +errnokey: + mp_clear_multi(r, s, p, e, NULL); + return err; +} + +/** + Sign a message digest + @param in The message digest to sign + @param inlen The length of the digest + @param out [out] The destination for the signature + @param outlen [in/out] The max size and resulting size of the signature + @param prng An active PRNG state + @param wprng The index of the PRNG you wish to use + @param key A private ECC key + @return CRYPT_OK if successful +*/ +int ecc_sign_hash(const unsigned char *in, unsigned long inlen, + unsigned char *out, unsigned long *outlen, + prng_state *prng, int wprng, ecc_key *key) +{ + return ecc_sign_hash_ex(in, inlen, out, outlen, prng, wprng, key, 0); +} + +/** + Sign a message digest in RFC7518 format + @param in The message digest to sign + @param inlen The length of the digest + @param out [out] The destination for the signature + @param outlen [in/out] The max size and resulting size of the signature + @param prng An active PRNG state + @param wprng The index of the PRNG you wish to use + @param key A private ECC key + @return CRYPT_OK if successful +*/ +int ecc_sign_hash_rfc7518(const unsigned char *in, unsigned long inlen, + unsigned char *out, unsigned long *outlen, + prng_state *prng, int wprng, ecc_key *key) +{ + return ecc_sign_hash_ex(in, inlen, out, outlen, prng, wprng, key, 1); +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_sizes.c b/src/ltc/pk/ecc/ecc_sizes.c new file mode 100644 index 00000000..3dbe37a5 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_sizes.c @@ -0,0 +1,46 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ecc_sizes.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +void ecc_sizes(int *low, int *high) +{ + int i; + LTC_ARGCHKVD(low != NULL); + LTC_ARGCHKVD(high != NULL); + + *low = INT_MAX; + *high = 0; + for (i = 0; ltc_ecc_sets[i].size != 0; i++) { + if (ltc_ecc_sets[i].size < *low) { + *low = ltc_ecc_sets[i].size; + } + if (ltc_ecc_sets[i].size > *high) { + *high = ltc_ecc_sets[i].size; + } + } +} + +#endif +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ecc_verify_hash.c b/src/ltc/pk/ecc/ecc_verify_hash.c new file mode 100644 index 00000000..c4d14c33 --- /dev/null +++ b/src/ltc/pk/ecc/ecc_verify_hash.c @@ -0,0 +1,207 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +/** + @file ecc_verify_hash.c + ECC Crypto, Tom St Denis +*/ + +static int ecc_verify_hash_ex(const unsigned char *sig, unsigned long siglen, + const unsigned char *hash, unsigned long hashlen, + int *stat, ecc_key *key, int sigformat) +{ + ecc_point *mG, *mQ; + void *r, *s, *v, *w, *u1, *u2, *e, *p, *m, *a, *mu, *ma; + void *mp; + int err; + unsigned long pbits, pbytes, i, shift_right; + unsigned char ch, buf[MAXBLOCKSIZE]; + + LTC_ARGCHK(sig != NULL); + LTC_ARGCHK(hash != NULL); + LTC_ARGCHK(stat != NULL); + LTC_ARGCHK(key != NULL); + + /* default to invalid signature */ + *stat = 0; + mp = NULL; + + /* is the IDX valid ? */ + if (ltc_ecc_is_valid_idx(key->idx) != 1) { + return CRYPT_PK_INVALID_TYPE; + } + + /* allocate ints */ + if ((err = mp_init_multi(&r, &s, &v, &w, &u1, &u2, &p, &e, &m, &a, &mu, &ma, NULL)) != CRYPT_OK) { + return CRYPT_MEM; + } + + /* allocate points */ + mG = ltc_ecc_new_point(); + mQ = ltc_ecc_new_point(); + if (mQ == NULL || mG == NULL) { + err = CRYPT_MEM; + goto error; + } + + if (sigformat == 1) { + /* RFC7518 format */ + if ((siglen % 2) == 1) { + err = CRYPT_INVALID_PACKET; + goto error; + } + i = siglen / 2; + if ((err = mp_read_unsigned_bin(r, (unsigned char *)sig, i)) != CRYPT_OK) { goto error; } + if ((err = mp_read_unsigned_bin(s, (unsigned char *)sig+i, i)) != CRYPT_OK) { goto error; } + } + else { + /* ASN.1 format */ + if ((err = der_decode_sequence_multi(sig, siglen, + LTC_ASN1_INTEGER, 1UL, r, + LTC_ASN1_INTEGER, 1UL, s, + LTC_ASN1_EOL, 0UL, NULL)) != CRYPT_OK) { goto error; } + } + + /* get the order */ + if ((err = mp_read_radix(p, (char *)key->dp->order, 16)) != CRYPT_OK) { goto error; } + + /* get the modulus */ + if ((err = mp_read_radix(m, (char *)key->dp->prime, 16)) != CRYPT_OK) { goto error; } + + /* get the a */ + if ((err = mp_read_radix(a, (char *)key->dp->A, 16)) != CRYPT_OK) { goto error; } + + /* check for zero */ + if (mp_iszero(r) || mp_iszero(s) || mp_cmp(r, p) != LTC_MP_LT || mp_cmp(s, p) != LTC_MP_LT) { + err = CRYPT_INVALID_PACKET; + goto error; + } + + /* read hash - truncate if needed */ + pbits = mp_count_bits(p); + pbytes = (pbits+7) >> 3; + if (pbits > hashlen*8) { + if ((err = mp_read_unsigned_bin(e, (unsigned char *)hash, hashlen)) != CRYPT_OK) { goto error; } + } + else if (pbits % 8 == 0) { + if ((err = mp_read_unsigned_bin(e, (unsigned char *)hash, pbytes)) != CRYPT_OK) { goto error; } + } + else { + shift_right = 8 - pbits % 8; + for (i=0, ch=0; i<pbytes; i++) { + buf[i] = ch; + ch = (hash[i] << (8-shift_right)); + buf[i] = buf[i] ^ (hash[i] >> shift_right); + } + if ((err = mp_read_unsigned_bin(e, (unsigned char *)buf, pbytes)) != CRYPT_OK) { goto error; } + } + + /* w = s^-1 mod n */ + if ((err = mp_invmod(s, p, w)) != CRYPT_OK) { goto error; } + + /* u1 = ew */ + if ((err = mp_mulmod(e, w, p, u1)) != CRYPT_OK) { goto error; } + + /* u2 = rw */ + if ((err = mp_mulmod(r, w, p, u2)) != CRYPT_OK) { goto error; } + + /* find mG and mQ */ + if ((err = mp_read_radix(mG->x, (char *)key->dp->Gx, 16)) != CRYPT_OK) { goto error; } + if ((err = mp_read_radix(mG->y, (char *)key->dp->Gy, 16)) != CRYPT_OK) { goto error; } + if ((err = mp_set(mG->z, 1)) != CRYPT_OK) { goto error; } + + if ((err = mp_copy(key->pubkey.x, mQ->x)) != CRYPT_OK) { goto error; } + if ((err = mp_copy(key->pubkey.y, mQ->y)) != CRYPT_OK) { goto error; } + if ((err = mp_copy(key->pubkey.z, mQ->z)) != CRYPT_OK) { goto error; } + + /* compute u1*mG + u2*mQ = mG */ + if (ltc_mp.ecc_mul2add == NULL) { + if ((err = ltc_mp.ecc_ptmul(u1, mG, mG, a, m, 0)) != CRYPT_OK) { goto error; } + if ((err = ltc_mp.ecc_ptmul(u2, mQ, mQ, a, m, 0)) != CRYPT_OK) { goto error; } + + /* find the montgomery mp */ + if ((err = mp_montgomery_setup(m, &mp)) != CRYPT_OK) { goto error; } + if ((err = mp_montgomery_normalization(mu, m)) != CRYPT_OK) { goto error; } + if ((err = mp_mulmod(a, mu, m, ma)) != CRYPT_OK) { goto error; } + + /* add them */ + if ((err = ltc_mp.ecc_ptadd(mQ, mG, mG, ma, m, mp)) != CRYPT_OK) { goto error; } + + /* reduce */ + if ((err = ltc_mp.ecc_map(mG, m, mp)) != CRYPT_OK) { goto error; } + } else { + /* use Shamir's trick to compute u1*mG + u2*mQ using half of the doubles */ + if ((err = ltc_mp.ecc_mul2add(mG, u1, mQ, u2, mG, a, m)) != CRYPT_OK) { goto error; } + } + + /* v = X_x1 mod n */ + if ((err = mp_mod(mG->x, p, v)) != CRYPT_OK) { goto error; } + + /* does v == r */ + if (mp_cmp(v, r) == LTC_MP_EQ) { + *stat = 1; + } + + /* clear up and return */ + err = CRYPT_OK; +error: + ltc_ecc_del_point(mG); + ltc_ecc_del_point(mQ); + mp_clear_multi(r, s, v, w, u1, u2, p, e, m, a, mu, ma, NULL); + if (mp != NULL) { + mp_montgomery_free(mp); + } + return err; +} + +/** + Verify an ECC signature + @param sig The signature to verify + @param siglen The length of the signature (octets) + @param hash The hash (message digest) that was signed + @param hashlen The length of the hash (octets) + @param stat Result of signature, 1==valid, 0==invalid + @param key The corresponding public ECC key + @return CRYPT_OK if successful (even if the signature is not valid) +*/ +int ecc_verify_hash(const unsigned char *sig, unsigned long siglen, + const unsigned char *hash, unsigned long hashlen, + int *stat, ecc_key *key) +{ + return ecc_verify_hash_ex(sig, siglen, hash, hashlen, stat, key, 0); +} + +/** + Verify an ECC signature in RFC7518 format + @param sig The signature to verify + @param siglen The length of the signature (octets) + @param hash The hash (message digest) that was signed + @param hashlen The length of the hash (octets) + @param stat Result of signature, 1==valid, 0==invalid + @param key The corresponding public ECC key + @return CRYPT_OK if successful (even if the signature is not valid) +*/ +int ecc_verify_hash_rfc7518(const unsigned char *sig, unsigned long siglen, + const unsigned char *hash, unsigned long hashlen, + int *stat, ecc_key *key) +{ + return ecc_verify_hash_ex(sig, siglen, hash, hashlen, stat, key, 1); +} + +#endif diff --git a/src/ltc/pk/ecc/ecc_verify_key.c b/src/ltc/pk/ecc/ecc_verify_key.c new file mode 100644 index 00000000..0ca1914f --- /dev/null +++ b/src/ltc/pk/ecc/ecc_verify_key.c @@ -0,0 +1,77 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +/* origin of this code - OLPC */ + +#ifdef LTC_MECC + +/** + Verify a key according to ANSI spec + @param key The key to validate + @return CRYPT_OK if successful +*/ + +int ecc_verify_key(ecc_key *key) +{ + int err; + void *prime = NULL; + void *order = NULL; + void *a = NULL; + ecc_point *point; + + if (mp_init_multi(&order, &prime, NULL) != CRYPT_OK) { + return CRYPT_MEM; + } + + /* Test 1: Are the x amd y points of the public key in the field? */ + if ((err = ltc_mp.read_radix(prime, key->dp->prime, 16)) != CRYPT_OK) { goto done2; } + + if (ltc_mp.compare_d(key->pubkey.z, 1) == LTC_MP_EQ) { + if ((ltc_mp.compare(key->pubkey.x, prime) != LTC_MP_LT) || + (ltc_mp.compare(key->pubkey.y, prime) != LTC_MP_LT) || + (ltc_mp.compare_d(key->pubkey.x, 0) != LTC_MP_GT) || + (ltc_mp.compare_d(key->pubkey.y, 0) != LTC_MP_GT) + ) + { + err = CRYPT_INVALID_PACKET; + goto done2; + } + } + + /* Test 2: is the public key on the curve? */ + if ((err = ltc_ecc_is_point(key->dp, key->pubkey.x, key->pubkey.y)) != CRYPT_OK) { goto done2; } + + /* Test 3: does nG = O? (n = order, O = point at infinity, G = public key) */ + point = ltc_ecc_new_point(); + if ((err = ltc_mp.read_radix(order, key->dp->order, 16)) != CRYPT_OK) { goto done1; } + if ((err = ltc_mp.read_radix(a, key->dp->A, 16)) != CRYPT_OK) { goto done1; } + if ((err = ltc_ecc_mulmod(order, &(key->pubkey), point, a, prime, 1)) != CRYPT_OK) { goto done1; } + + if (ltc_ecc_is_point_at_infinity(point, prime)) { + err = CRYPT_ERROR; + } + else { + err = CRYPT_OK; + } + +done1: + ltc_ecc_del_point(point); +done2: + mp_clear_multi(prime, order, NULL); + return err; +} + +#endif diff --git a/src/ltc/pk/ecc/ltc_ecc_export_point.c b/src/ltc/pk/ecc/ltc_ecc_export_point.c new file mode 100644 index 00000000..086e4c2e --- /dev/null +++ b/src/ltc/pk/ecc/ltc_ecc_export_point.c @@ -0,0 +1,64 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +int ltc_ecc_export_point(unsigned char *out, unsigned long *outlen, void *x, void *y, unsigned long size, int compressed) +{ + int err; + unsigned char buf[ECC_BUF_SIZE]; + unsigned long xsize, ysize; + + if (size > sizeof(buf)) return CRYPT_BUFFER_OVERFLOW; + if ((xsize = mp_unsigned_bin_size(x)) > size) return CRYPT_BUFFER_OVERFLOW; + if ((ysize = mp_unsigned_bin_size(y)) > size) return CRYPT_BUFFER_OVERFLOW; + + if(compressed) { + if (*outlen < (1 + size)) { + *outlen = 1 + size; + return CRYPT_BUFFER_OVERFLOW; + } + /* store first byte */ + out[0] = mp_isodd(y) ? 0x03 : 0x02; + /* pad and store x */ + zeromem(buf, sizeof(buf)); + if ((err = mp_to_unsigned_bin(x, buf + (size - xsize))) != CRYPT_OK) return err; + XMEMCPY(out+1, buf, size); + /* adjust outlen */ + *outlen = 1 + size; + } + else { + if (*outlen < (1 + 2*size)) { + *outlen = 1 + 2*size; + return CRYPT_BUFFER_OVERFLOW; + } + /* store byte 0x04 */ + out[0] = 0x04; + /* pad and store x */ + zeromem(buf, sizeof(buf)); + if ((err = mp_to_unsigned_bin(x, buf + (size - xsize))) != CRYPT_OK) return err; + XMEMCPY(out+1, buf, size); + /* pad and store y */ + zeromem(buf, sizeof(buf)); + if ((err = mp_to_unsigned_bin(y, buf + (size - ysize))) != CRYPT_OK) return err; + XMEMCPY(out+1+size, buf, size); + /* adjust outlen */ + *outlen = 1 + 2*size; + } + return CRYPT_OK; +} + +#endif diff --git a/src/ltc/pk/ecc/ltc_ecc_import_point.c b/src/ltc/pk/ecc/ltc_ecc_import_point.c new file mode 100644 index 00000000..d4d028d5 --- /dev/null +++ b/src/ltc/pk/ecc/ltc_ecc_import_point.c @@ -0,0 +1,72 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +int ltc_ecc_import_point(const unsigned char *in, unsigned long inlen, void *prime, void *a, void *b, void *x, void *y) +{ + int err; + unsigned long size; + void *t1, *t2; + + /* init key + temporary numbers */ + if (mp_init_multi(&t1, &t2, NULL) != CRYPT_OK) { + return CRYPT_MEM; + } + + size = mp_unsigned_bin_size(prime); + + if (in[0] == 0x04 && (inlen&1) && ((inlen-1)>>1) == size) { + /* read uncompressed point */ + /* load x */ + if ((err = mp_read_unsigned_bin(x, (unsigned char *)in+1, size)) != CRYPT_OK) { goto cleanup; } + /* load y */ + if ((err = mp_read_unsigned_bin(y, (unsigned char *)in+1+size, size)) != CRYPT_OK) { goto cleanup; } + } + else if ((in[0] == 0x02 || in[0] == 0x03) && (inlen-1) == size) { + /* read compressed point */ + /* load x */ + if ((err = mp_read_unsigned_bin(x, (unsigned char *)in+1, size)) != CRYPT_OK) { goto cleanup; } + /* compute x^3 */ + if ((err = mp_sqr(x, t1)) != CRYPT_OK) { goto cleanup; } + if ((err = mp_mulmod(t1, x, prime, t1)) != CRYPT_OK) { goto cleanup; } + /* compute x^3 + a*x */ + if ((err = mp_mulmod(a, x, prime, t2)) != CRYPT_OK) { goto cleanup; } + if ((err = mp_add(t1, t2, t1)) != CRYPT_OK) { goto cleanup; } + /* compute x^3 + a*x + b */ + if ((err = mp_add(t1, b, t1)) != CRYPT_OK) { goto cleanup; } + /* compute sqrt(x^3 + a*x + b) */ + if ((err = mp_sqrtmod_prime(t1, prime, t2)) != CRYPT_OK) { goto cleanup; } + /* adjust y */ + if ((mp_isodd(t2) && in[0] == 0x03) || (!mp_isodd(t2) && in[0] == 0x02)) { + if ((err = mp_mod(t2, prime, y)) != CRYPT_OK) { goto cleanup; } + } + else { + if ((err = mp_submod(prime, t2, prime, y)) != CRYPT_OK) { goto cleanup; } + } + } + else { + err = CRYPT_INVALID_PACKET; + goto cleanup; + } + + err = CRYPT_OK; +cleanup: + mp_clear_multi(t1, t2, NULL); + return err; +} + +#endif diff --git a/src/ltc/pk/ecc/ltc_ecc_is_point.c b/src/ltc/pk/ecc/ltc_ecc_is_point.c new file mode 100644 index 00000000..9ea963c5 --- /dev/null +++ b/src/ltc/pk/ecc/ltc_ecc_is_point.c @@ -0,0 +1,75 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +/** Returns whether [x,y] is a point on curve defined by dp + @param dp curve parameters + @param x x point coordinate + @param y y point coordinate + @return CRYPT_OK if valid +*/ + +int ltc_ecc_is_point(const ltc_ecc_set_type *dp, void *x, void *y) +{ + void *prime, *a, *b, *t1, *t2; + int err; + + if ((err = mp_init_multi(&prime, &a, &b, &t1, &t2, NULL)) != CRYPT_OK) { + return err; + } + + /* load prime, a and b */ + if ((err = mp_read_radix(prime, dp->prime, 16)) != CRYPT_OK) goto cleanup; + if ((err = mp_read_radix(b, dp->B, 16)) != CRYPT_OK) goto cleanup; + if ((err = mp_read_radix(a, dp->A, 16)) != CRYPT_OK) goto cleanup; + + /* compute y^2 */ + if ((err = mp_sqr(y, t1)) != CRYPT_OK) goto cleanup; + + /* compute x^3 */ + if ((err = mp_sqr(x, t2)) != CRYPT_OK) goto cleanup; + if ((err = mp_mod(t2, prime, t2)) != CRYPT_OK) goto cleanup; + if ((err = mp_mul(x, t2, t2)) != CRYPT_OK) goto cleanup; + + /* compute y^2 - x^3 */ + if ((err = mp_sub(t1, t2, t1)) != CRYPT_OK) goto cleanup; + + /* compute y^2 - x^3 - a*x */ + if ((err = mp_submod(prime, a, prime, t2)) != CRYPT_OK) goto cleanup; + if ((err = mp_mulmod(t2, x, prime, t2)) != CRYPT_OK) goto cleanup; + if ((err = mp_addmod(t1, t2, prime, t1)) != CRYPT_OK) goto cleanup; + + /* adjust range (0, prime) */ + while (mp_cmp_d(t1, 0) == LTC_MP_LT) { + if ((err = mp_add(t1, prime, t1)) != CRYPT_OK) goto cleanup; + } + while (mp_cmp(t1, prime) != LTC_MP_LT) { + if ((err = mp_sub(t1, prime, t1)) != CRYPT_OK) goto cleanup; + } + + /* compare to b */ + if (mp_cmp(t1, b) != LTC_MP_EQ) { + err = CRYPT_INVALID_PACKET; + } else { + err = CRYPT_OK; + } + +cleanup: + mp_clear_multi(prime, a, b, t1, t2, NULL); + return err; +} + +#endif diff --git a/src/ltc/pk/ecc/ltc_ecc_is_point_at_infinity.c b/src/ltc/pk/ecc/ltc_ecc_is_point_at_infinity.c new file mode 100644 index 00000000..1b946187 --- /dev/null +++ b/src/ltc/pk/ecc/ltc_ecc_is_point_at_infinity.c @@ -0,0 +1,50 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +#include "tomcrypt.h" + +#ifdef LTC_MECC + +/* http://crypto.stackexchange.com/questions/41468/point-at-infinity-for-jacobian-coordinates + * a point at infinity is any point (x,y,0) such that y^2 == x^3, except (0,0,0) + */ + +int ltc_ecc_is_point_at_infinity(ecc_point *P, void *modulus) +{ + int err, retval = 0; + void *x3, *y2; + + /* trivial case */ + if (!mp_iszero(P->z)) goto done; + + /* point (0,0,0) is not at infinity */ + if (mp_iszero(P->x) && mp_iszero(P->y)) goto done; + + /* initialize */ + if ((err = mp_init_multi(&x3, &y2, NULL)) != CRYPT_OK) goto done; + + /* compute y^2 */ + if ((err = mp_mulmod(P->y, P->y, modulus, y2)) != CRYPT_OK) goto cleanup; + + /* compute x^3 */ + if ((err = mp_mulmod(P->x, P->x, modulus, x3)) != CRYPT_OK) goto cleanup; + if ((err = mp_mulmod(P->x, x3, modulus, x3)) != CRYPT_OK) goto cleanup; + + /* test y^2 == x^3 */ + if ((mp_cmp(x3, y2) == LTC_MP_EQ) && !mp_iszero(y2)) retval = 1; + +cleanup: + mp_clear_multi(x3, y2, NULL); +done: + return retval; +} + +#endif diff --git a/src/ltc/pk/ecc/ltc_ecc_is_valid_idx.c b/src/ltc/pk/ecc/ltc_ecc_is_valid_idx.c new file mode 100644 index 00000000..b53eaca7 --- /dev/null +++ b/src/ltc/pk/ecc/ltc_ecc_is_valid_idx.c @@ -0,0 +1,44 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ltc_ecc_is_valid_idx.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** Returns whether an ECC idx is valid or not + @param n The idx number to check + @return 1 if valid, 0 if not +*/ +int ltc_ecc_is_valid_idx(int n) +{ + int x; + + for (x = 0; ltc_ecc_sets[x].size != 0; x++); + /* -1 is a valid index --- indicating that the domain params were supplied by the user */ + if ((n >= -1) && (n < x)) { + return 1; + } + return 0; +} + +#endif +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ltc_ecc_map.c b/src/ltc/pk/ecc/ltc_ecc_map.c new file mode 100644 index 00000000..75ea562a --- /dev/null +++ b/src/ltc/pk/ecc/ltc_ecc_map.c @@ -0,0 +1,81 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ltc_ecc_map.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** + Map a projective jacbobian point back to affine space + @param P [in/out] The point to map + @param modulus The modulus of the field the ECC curve is in + @param mp The "b" value from montgomery_setup() + @return CRYPT_OK on success +*/ +int ltc_ecc_map(ecc_point *P, void *modulus, void *mp) +{ + void *t1, *t2; + int err; + + LTC_ARGCHK(P != NULL); + LTC_ARGCHK(modulus != NULL); + LTC_ARGCHK(mp != NULL); + + if (mp_iszero(P->z)) { + if ((err = mp_set(P->x, 0)) != CRYPT_OK) { return err; } + if ((err = mp_set(P->y, 0)) != CRYPT_OK) { return err; } + if ((err = mp_set(P->z, 1)) != CRYPT_OK) { return err; } + return CRYPT_OK; + } + + if ((err = mp_init_multi(&t1, &t2, NULL)) != CRYPT_OK) { + return CRYPT_MEM; + } + + /* first map z back to normal */ + if ((err = mp_montgomery_reduce(P->z, modulus, mp)) != CRYPT_OK) { goto done; } + + /* get 1/z */ + if ((err = mp_invmod(P->z, modulus, t1)) != CRYPT_OK) { goto done; } + + /* get 1/z^2 and 1/z^3 */ + if ((err = mp_sqr(t1, t2)) != CRYPT_OK) { goto done; } + if ((err = mp_mod(t2, modulus, t2)) != CRYPT_OK) { goto done; } + if ((err = mp_mul(t1, t2, t1)) != CRYPT_OK) { goto done; } + if ((err = mp_mod(t1, modulus, t1)) != CRYPT_OK) { goto done; } + + /* multiply against x/y */ + if ((err = mp_mul(P->x, t2, P->x)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(P->x, modulus, mp)) != CRYPT_OK) { goto done; } + if ((err = mp_mul(P->y, t1, P->y)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(P->y, modulus, mp)) != CRYPT_OK) { goto done; } + if ((err = mp_set(P->z, 1)) != CRYPT_OK) { goto done; } + + err = CRYPT_OK; +done: + mp_clear_multi(t1, t2, NULL); + return err; +} + +#endif + +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ltc_ecc_mul2add.c b/src/ltc/pk/ecc/ltc_ecc_mul2add.c new file mode 100644 index 00000000..76febdcb --- /dev/null +++ b/src/ltc/pk/ecc/ltc_ecc_mul2add.c @@ -0,0 +1,211 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ltc_ecc_mul2add.c + ECC Crypto, Shamir's Trick, Tom St Denis +*/ + +#ifdef LTC_MECC + +#ifdef LTC_ECC_SHAMIR + +/** Computes kA*A + kB*B = C using Shamir's Trick + @param A First point to multiply + @param kA What to multiple A by + @param B Second point to multiply + @param kB What to multiple B by + @param C [out] Destination point (can overlap with A or B + @param modulus Modulus for curve + @return CRYPT_OK on success +*/ +int ltc_ecc_mul2add(ecc_point *A, void *kA, + ecc_point *B, void *kB, + ecc_point *C, + void *a, + void *modulus) +{ + ecc_point *precomp[16]; + unsigned bitbufA, bitbufB, lenA, lenB, len, nA, nB, nibble; + unsigned x, y; + unsigned char *tA, *tB; + int err, first; + void *mp, *mu, *ma; + + /* argchks */ + LTC_ARGCHK(A != NULL); + LTC_ARGCHK(B != NULL); + LTC_ARGCHK(C != NULL); + LTC_ARGCHK(kA != NULL); + LTC_ARGCHK(kB != NULL); + LTC_ARGCHK(modulus != NULL); + + /* allocate memory */ + tA = XCALLOC(1, ECC_BUF_SIZE); + if (tA == NULL) { + return CRYPT_MEM; + } + tB = XCALLOC(1, ECC_BUF_SIZE); + if (tB == NULL) { + XFREE(tA); + return CRYPT_MEM; + } + + /* get sizes */ + lenA = mp_unsigned_bin_size(kA); + lenB = mp_unsigned_bin_size(kB); + len = MAX(lenA, lenB); + + /* sanity check */ + if ((lenA > ECC_BUF_SIZE) || (lenB > ECC_BUF_SIZE)) { + err = CRYPT_INVALID_ARG; + goto ERR_T; + } + + /* extract and justify kA */ + mp_to_unsigned_bin(kA, (len - lenA) + tA); + + /* extract and justify kB */ + mp_to_unsigned_bin(kB, (len - lenB) + tB); + + /* allocate the table */ + for (x = 0; x < 16; x++) { + precomp[x] = ltc_ecc_new_point(); + if (precomp[x] == NULL) { + for (y = 0; y < x; ++y) { + ltc_ecc_del_point(precomp[y]); + } + err = CRYPT_MEM; + goto ERR_T; + } + } + + /* init montgomery reduction */ + if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) { + goto ERR_P; + } + if ((err = mp_init_multi(&mu, &ma, NULL)) != CRYPT_OK) { + goto ERR_MP; + } + if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) { + goto ERR_MU; + } + if ((err = mp_mulmod(a, mu, modulus, ma)) != CRYPT_OK) { + goto ERR_MU; + } + + /* copy ones ... */ + if ((err = mp_mulmod(A->x, mu, modulus, precomp[1]->x)) != CRYPT_OK) { goto ERR_MU; } + if ((err = mp_mulmod(A->y, mu, modulus, precomp[1]->y)) != CRYPT_OK) { goto ERR_MU; } + if ((err = mp_mulmod(A->z, mu, modulus, precomp[1]->z)) != CRYPT_OK) { goto ERR_MU; } + + if ((err = mp_mulmod(B->x, mu, modulus, precomp[1<<2]->x)) != CRYPT_OK) { goto ERR_MU; } + if ((err = mp_mulmod(B->y, mu, modulus, precomp[1<<2]->y)) != CRYPT_OK) { goto ERR_MU; } + if ((err = mp_mulmod(B->z, mu, modulus, precomp[1<<2]->z)) != CRYPT_OK) { goto ERR_MU; } + + /* precomp [i,0](A + B) table */ + if ((err = ltc_mp.ecc_ptdbl(precomp[1], precomp[2], ma, modulus, mp)) != CRYPT_OK) { goto ERR_MU; } + if ((err = ltc_mp.ecc_ptadd(precomp[1], precomp[2], precomp[3], ma, modulus, mp)) != CRYPT_OK) { goto ERR_MU; } + + /* precomp [0,i](A + B) table */ + if ((err = ltc_mp.ecc_ptdbl(precomp[1<<2], precomp[2<<2], ma, modulus, mp)) != CRYPT_OK) { goto ERR_MU; } + if ((err = ltc_mp.ecc_ptadd(precomp[1<<2], precomp[2<<2], precomp[3<<2], ma, modulus, mp)) != CRYPT_OK) { goto ERR_MU; } + + /* precomp [i,j](A + B) table (i != 0, j != 0) */ + for (x = 1; x < 4; x++) { + for (y = 1; y < 4; y++) { + if ((err = ltc_mp.ecc_ptadd(precomp[x], precomp[(y<<2)], precomp[x+(y<<2)], ma, modulus, mp)) != CRYPT_OK) { goto ERR_MU; } + } + } + + nibble = 3; + first = 1; + bitbufA = tA[0]; + bitbufB = tB[0]; + + /* for every byte of the multiplicands */ + for (x = 0;; ) { + /* grab a nibble */ + if (++nibble == 4) { + if (x == len) break; + bitbufA = tA[x]; + bitbufB = tB[x]; + nibble = 0; + ++x; + } + + /* extract two bits from both, shift/update */ + nA = (bitbufA >> 6) & 0x03; + nB = (bitbufB >> 6) & 0x03; + bitbufA = (bitbufA << 2) & 0xFF; + bitbufB = (bitbufB << 2) & 0xFF; + + /* if both zero, if first, continue */ + if ((nA == 0) && (nB == 0) && (first == 1)) { + continue; + } + + /* double twice, only if this isn't the first */ + if (first == 0) { + /* double twice */ + if ((err = ltc_mp.ecc_ptdbl(C, C, ma, modulus, mp)) != CRYPT_OK) { goto ERR_MU; } + if ((err = ltc_mp.ecc_ptdbl(C, C, ma, modulus, mp)) != CRYPT_OK) { goto ERR_MU; } + } + + /* if not both zero */ + if ((nA != 0) || (nB != 0)) { + if (first == 1) { + /* if first, copy from table */ + first = 0; + if ((err = mp_copy(precomp[nA + (nB<<2)]->x, C->x)) != CRYPT_OK) { goto ERR_MU; } + if ((err = mp_copy(precomp[nA + (nB<<2)]->y, C->y)) != CRYPT_OK) { goto ERR_MU; } + if ((err = mp_copy(precomp[nA + (nB<<2)]->z, C->z)) != CRYPT_OK) { goto ERR_MU; } + } else { + /* if not first, add from table */ + if ((err = ltc_mp.ecc_ptadd(C, precomp[nA + (nB<<2)], C, ma, modulus, mp)) != CRYPT_OK) { goto ERR_MU; } + } + } + } + + /* reduce to affine */ + err = ltc_ecc_map(C, modulus, mp); + + /* clean up */ +ERR_MU: + mp_clear_multi(mu, ma, NULL); +ERR_MP: + mp_montgomery_free(mp); +ERR_P: + for (x = 0; x < 16; x++) { + ltc_ecc_del_point(precomp[x]); + } +ERR_T: +#ifdef LTC_CLEAN_STACK + zeromem(tA, ECC_BUF_SIZE); + zeromem(tB, ECC_BUF_SIZE); +#endif + XFREE(tA); + XFREE(tB); + + return err; +} + +#endif +#endif + +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ diff --git a/src/ltc/pk/ecc/ltc_ecc_mulmod.c b/src/ltc/pk/ecc/ltc_ecc_mulmod.c new file mode 100644 index 00000000..ec2bf8f9 --- /dev/null +++ b/src/ltc/pk/ecc/ltc_ecc_mulmod.c @@ -0,0 +1,234 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ltc_ecc_mulmod.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC +#ifndef LTC_ECC_TIMING_RESISTANT + +/* size of sliding window, don't change this! */ +#define WINSIZE 4 + +/** + Perform a point multiplication + @param k The scalar to multiply by + @param G The base point + @param R [out] Destination for kG + @param modulus The modulus of the field the ECC curve is in + @param map Boolean whether to map back to affine or not (1==map, 0 == leave in projective) + @return CRYPT_OK on success +*/ +int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *a, void *modulus, int map) +{ + ecc_point *tG, *M[8]; + int i, j, err; + void *mu, *mp, *ma; + ltc_mp_digit buf; + int first, bitbuf, bitcpy, bitcnt, mode, digidx; + + LTC_ARGCHK(k != NULL); + LTC_ARGCHK(G != NULL); + LTC_ARGCHK(R != NULL); + LTC_ARGCHK(modulus != NULL); + + if (ltc_ecc_is_point_at_infinity(G, modulus)) { + /* return the point at infinity */ + if ((err = mp_set(R->x, 1)) != CRYPT_OK) { return err; } + if ((err = mp_set(R->y, 1)) != CRYPT_OK) { return err; } + if ((err = mp_set(R->z, 0)) != CRYPT_OK) { return err; } + return CRYPT_OK; + } + + /* init montgomery reduction */ + if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) { + return err; + } + if ((err = mp_init_multi(&mu, &ma, NULL)) != CRYPT_OK) { + mp_montgomery_free(mp); + return err; + } + if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) { + mp_montgomery_free(mp); + mp_clear_multi(mu, ma, NULL); + return err; + } + if ((err = mp_mulmod(a, mu, modulus, ma)) != CRYPT_OK) { + mp_montgomery_free(mp); + mp_clear_multi(mu, ma, NULL); + return err; + } + + /* alloc ram for window temps */ + for (i = 0; i < 8; i++) { + M[i] = ltc_ecc_new_point(); + if (M[i] == NULL) { + for (j = 0; j < i; j++) { + ltc_ecc_del_point(M[j]); + } + mp_montgomery_free(mp); + mp_clear_multi(mu, ma, NULL); + return CRYPT_MEM; + } + } + + /* make a copy of G incase R==G */ + tG = ltc_ecc_new_point(); + if (tG == NULL) { err = CRYPT_MEM; goto done; } + + /* tG = G and convert to montgomery */ + if (mp_cmp_d(mu, 1) == LTC_MP_EQ) { + if ((err = mp_copy(G->x, tG->x)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(G->y, tG->y)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(G->z, tG->z)) != CRYPT_OK) { goto done; } + } else { + if ((err = mp_mulmod(G->x, mu, modulus, tG->x)) != CRYPT_OK) { goto done; } + if ((err = mp_mulmod(G->y, mu, modulus, tG->y)) != CRYPT_OK) { goto done; } + if ((err = mp_mulmod(G->z, mu, modulus, tG->z)) != CRYPT_OK) { goto done; } + } + mp_clear(mu); + mu = NULL; + + /* calc the M tab, which holds kG for k==8..15 */ + /* M[0] == 8G */ + if ((err = ltc_mp.ecc_ptdbl(tG, M[0], ma, modulus, mp)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], ma, modulus, mp)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.ecc_ptdbl(M[0], M[0], ma, modulus, mp)) != CRYPT_OK) { goto done; } + + /* now find (8+k)G for k=1..7 */ + for (j = 9; j < 16; j++) { + if ((err = ltc_mp.ecc_ptadd(M[j-9], tG, M[j-8], ma, modulus, mp)) != CRYPT_OK) { goto done; } + } + + /* setup sliding window */ + mode = 0; + bitcnt = 1; + buf = 0; + digidx = mp_get_digit_count(k) - 1; + bitcpy = bitbuf = 0; + first = 1; + + /* perform ops */ + for (;;) { + /* grab next digit as required */ + if (--bitcnt == 0) { + if (digidx == -1) { + break; + } + buf = mp_get_digit(k, digidx); + bitcnt = (int) ltc_mp.bits_per_digit; + --digidx; + } + + /* grab the next msb from the ltiplicand */ + i = (buf >> (ltc_mp.bits_per_digit - 1)) & 1; + buf <<= 1; + + /* skip leading zero bits */ + if (mode == 0 && i == 0) { + continue; + } + + /* if the bit is zero and mode == 1 then we double */ + if (mode == 1 && i == 0) { + if ((err = ltc_mp.ecc_ptdbl(R, R, ma, modulus, mp)) != CRYPT_OK) { goto done; } + continue; + } + + /* else we add it to the window */ + bitbuf |= (i << (WINSIZE - ++bitcpy)); + mode = 2; + + if (bitcpy == WINSIZE) { + /* if this is the first window we do a simple copy */ + if (first == 1) { + /* R = kG [k = first window] */ + if ((err = mp_copy(M[bitbuf-8]->x, R->x)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(M[bitbuf-8]->y, R->y)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(M[bitbuf-8]->z, R->z)) != CRYPT_OK) { goto done; } + first = 0; + } else { + /* normal window */ + /* ok window is filled so double as required and add */ + /* double first */ + for (j = 0; j < WINSIZE; j++) { + if ((err = ltc_mp.ecc_ptdbl(R, R, ma, modulus, mp)) != CRYPT_OK) { goto done; } + } + + /* then add, bitbuf will be 8..15 [8..2^WINSIZE] guaranteed */ + if ((err = ltc_mp.ecc_ptadd(R, M[bitbuf-8], R, ma, modulus, mp)) != CRYPT_OK) { goto done; } + } + /* empty window and reset */ + bitcpy = bitbuf = 0; + mode = 1; + } + } + + /* if bits remain then double/add */ + if (mode == 2 && bitcpy > 0) { + /* double then add */ + for (j = 0; j < bitcpy; j++) { + /* only double if we have had at least one add first */ + if (first == 0) { + if ((err = ltc_mp.ecc_ptdbl(R, R, ma, modulus, mp)) != CRYPT_OK) { goto done; } + } + + bitbuf <<= 1; + if ((bitbuf & (1 << WINSIZE)) != 0) { + if (first == 1){ + /* first add, so copy */ + if ((err = mp_copy(tG->x, R->x)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(tG->y, R->y)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(tG->z, R->z)) != CRYPT_OK) { goto done; } + first = 0; + } else { + /* then add */ + if ((err = ltc_mp.ecc_ptadd(R, tG, R, ma, modulus, mp)) != CRYPT_OK) { goto done; } + } + } + } + } + + /* map R back from projective space */ + if (map) { + err = ltc_ecc_map(R, modulus, mp); + } else { + err = CRYPT_OK; + } +done: + if (mu != NULL) { + mp_clear(mu); + } + mp_clear(ma); + mp_montgomery_free(mp); + ltc_ecc_del_point(tG); + for (i = 0; i < 8; i++) { + ltc_ecc_del_point(M[i]); + } + return err; +} + +#endif + +#undef WINSIZE + +#endif + +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ diff --git a/src/ltc/pk/ecc/ltc_ecc_mulmod_timing.c b/src/ltc/pk/ecc/ltc_ecc_mulmod_timing.c new file mode 100644 index 00000000..73145e71 --- /dev/null +++ b/src/ltc/pk/ecc/ltc_ecc_mulmod_timing.c @@ -0,0 +1,178 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ltc_ecc_mulmod_timing.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +#ifdef LTC_ECC_TIMING_RESISTANT + +/** + Perform a point multiplication (timing resistant) + @param k The scalar to multiply by + @param G The base point + @param R [out] Destination for kG + @param a ECC curve parameter a + @param modulus The modulus of the field the ECC curve is in + @param map Boolean whether to map back to affine or not (1==map, 0 == leave in projective) + @return CRYPT_OK on success +*/ +int ltc_ecc_mulmod(void *k, ecc_point *G, ecc_point *R, void *a, void *modulus, int map) +{ + ecc_point *tG, *M[3]; + int i, j, err; + void *mu, *mp, *ma; + ltc_mp_digit buf; + int bitcnt, mode, digidx; + + LTC_ARGCHK(k != NULL); + LTC_ARGCHK(G != NULL); + LTC_ARGCHK(R != NULL); + LTC_ARGCHK(modulus != NULL); + + if (ltc_ecc_is_point_at_infinity(G, modulus)) { + /* return the point at infinity */ + if ((err = mp_set(R->x, 1)) != CRYPT_OK) { return err; } + if ((err = mp_set(R->y, 1)) != CRYPT_OK) { return err; } + if ((err = mp_set(R->z, 0)) != CRYPT_OK) { return err; } + return CRYPT_OK; + } + + /* init montgomery reduction */ + if ((err = mp_montgomery_setup(modulus, &mp)) != CRYPT_OK) { + return err; + } + if ((err = mp_init_multi(&mu, &ma, NULL)) != CRYPT_OK) { + mp_montgomery_free(mp); + return err; + } + if ((err = mp_montgomery_normalization(mu, modulus)) != CRYPT_OK) { + mp_clear(mu); + mp_montgomery_free(mp); + return err; + } + if ((err = mp_mulmod(a, mu, modulus, ma)) != CRYPT_OK) { + mp_montgomery_free(mp); + mp_clear_multi(mu, ma, NULL); + return err; + } + + /* alloc ram for window temps */ + for (i = 0; i < 3; i++) { + M[i] = ltc_ecc_new_point(); + if (M[i] == NULL) { + for (j = 0; j < i; j++) { + ltc_ecc_del_point(M[j]); + } + mp_clear(mu); + mp_montgomery_free(mp); + return CRYPT_MEM; + } + } + + /* make a copy of G incase R==G */ + tG = ltc_ecc_new_point(); + if (tG == NULL) { err = CRYPT_MEM; goto done; } + + /* tG = G and convert to montgomery */ + if ((err = mp_mulmod(G->x, mu, modulus, tG->x)) != CRYPT_OK) { goto done; } + if ((err = mp_mulmod(G->y, mu, modulus, tG->y)) != CRYPT_OK) { goto done; } + if ((err = mp_mulmod(G->z, mu, modulus, tG->z)) != CRYPT_OK) { goto done; } + mp_clear(mu); + mu = NULL; + + /* calc the M tab */ + /* M[0] == G */ + if ((err = mp_copy(tG->x, M[0]->x)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(tG->y, M[0]->y)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(tG->z, M[0]->z)) != CRYPT_OK) { goto done; } + /* M[1] == 2G */ + if ((err = ltc_mp.ecc_ptdbl(tG, M[1], ma, modulus, mp)) != CRYPT_OK) { goto done; } + + /* setup sliding window */ + mode = 0; + bitcnt = 1; + buf = 0; + digidx = mp_get_digit_count(k) - 1; + + /* perform ops */ + for (;;) { + /* grab next digit as required */ + if (--bitcnt == 0) { + if (digidx == -1) { + break; + } + buf = mp_get_digit(k, digidx); + bitcnt = (int) MP_DIGIT_BIT; + --digidx; + } + + /* grab the next msb from the ltiplicand */ + i = (int)((buf >> (MP_DIGIT_BIT - 1)) & 1); + buf <<= 1; + + if (mode == 0 && i == 0) { + /* dummy operations */ + if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[2], ma, modulus, mp)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.ecc_ptdbl(M[1], M[2], ma, modulus, mp)) != CRYPT_OK) { goto done; } + continue; + } + + if (mode == 0 && i == 1) { + mode = 1; + /* dummy operations */ + if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[2], ma, modulus, mp)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.ecc_ptdbl(M[1], M[2], ma, modulus, mp)) != CRYPT_OK) { goto done; } + continue; + } + + if ((err = ltc_mp.ecc_ptadd(M[0], M[1], M[i^1], ma, modulus, mp)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.ecc_ptdbl(M[i], M[i], ma, modulus, mp)) != CRYPT_OK) { goto done; } + } + + /* copy result out */ + if ((err = mp_copy(M[0]->x, R->x)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(M[0]->y, R->y)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(M[0]->z, R->z)) != CRYPT_OK) { goto done; } + + /* map R back from projective space */ + if (map) { + err = ltc_ecc_map(R, modulus, mp); + } else { + err = CRYPT_OK; + } +done: + if (mu != NULL) { + mp_clear(mu); + } + mp_clear(ma); + mp_montgomery_free(mp); + ltc_ecc_del_point(tG); + for (i = 0; i < 3; i++) { + ltc_ecc_del_point(M[i]); + } + return err; +} + +#endif +#endif +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ltc_ecc_points.c b/src/ltc/pk/ecc/ltc_ecc_points.c new file mode 100644 index 00000000..2b45c726 --- /dev/null +++ b/src/ltc/pk/ecc/ltc_ecc_points.c @@ -0,0 +1,58 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ltc_ecc_points.c + ECC Crypto, Tom St Denis +*/ + +#ifdef LTC_MECC + +/** + Allocate a new ECC point + @return A newly allocated point or NULL on error +*/ +ecc_point *ltc_ecc_new_point(void) +{ + ecc_point *p; + p = XCALLOC(1, sizeof(*p)); + if (p == NULL) { + return NULL; + } + if (mp_init_multi(&p->x, &p->y, &p->z, NULL) != CRYPT_OK) { + XFREE(p); + return NULL; + } + return p; +} + +/** Free an ECC point from memory + @param p The point to free +*/ +void ltc_ecc_del_point(ecc_point *p) +{ + /* prevents free'ing null arguments */ + if (p != NULL) { + mp_clear_multi(p->x, p->y, p->z, NULL); /* note: p->z may be NULL but that's ok with this function anyways */ + XFREE(p); + } +} + +#endif +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ltc_ecc_projective_add_point.c b/src/ltc/pk/ecc/ltc_ecc_projective_add_point.c new file mode 100644 index 00000000..d3d31dc0 --- /dev/null +++ b/src/ltc/pk/ecc/ltc_ecc_projective_add_point.c @@ -0,0 +1,217 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/** + @file ltc_ecc_projective_add_point.c + ECC Crypto, Tom St Denis +*/ + +#if defined(LTC_MECC) && (!defined(LTC_MECC_ACCEL) || defined(LTM_DESC)) + +/** + Add two ECC points + @param P The point to add + @param Q The point to add + @param R [out] The destination of the double + @param ma ECC curve parameter a in montgomery form (if NULL we assume a == -3) + @param modulus The modulus of the field the ECC curve is in + @param mp The "b" value from montgomery_setup() + @return CRYPT_OK on success +*/ +int ltc_ecc_projective_add_point(ecc_point *P, ecc_point *Q, ecc_point *R, void *ma, void *modulus, void *mp) +{ + void *t1, *t2, *x, *y, *z; + int err; + + LTC_ARGCHK(P != NULL); + LTC_ARGCHK(Q != NULL); + LTC_ARGCHK(R != NULL); + LTC_ARGCHK(modulus != NULL); + LTC_ARGCHK(mp != NULL); + + if ((err = mp_init_multi(&t1, &t2, &x, &y, &z, NULL)) != CRYPT_OK) { + return err; + } + + if (ltc_ecc_is_point_at_infinity(P, modulus)) { + /* P is point at infinity >> Result = Q */ + if ((err = ltc_mp.copy(Q->x, R->x)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.copy(Q->y, R->y)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.copy(Q->z, R->z)) != CRYPT_OK) { goto done; } + goto done; /* CRYPT_OK */ + } + + if (ltc_ecc_is_point_at_infinity(Q, modulus)) { + /* Q is point at infinity >> Result = P */ + if ((err = ltc_mp.copy(P->x, R->x)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.copy(P->y, R->y)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.copy(P->z, R->z)) != CRYPT_OK) { goto done; } + goto done; /* CRYPT_OK */ + } + + if ((mp_cmp(P->x, Q->x) == LTC_MP_EQ) && (mp_cmp(P->z, Q->z) == LTC_MP_EQ)) { + if (mp_cmp(P->y, Q->y) == LTC_MP_EQ) { + /* here P = Q >> Result = 2 * P (use doubling) */ + mp_clear_multi(t1, t2, x, y, z, NULL); + return ltc_ecc_projective_dbl_point(P, R, ma, modulus, mp); + } + if ((err = mp_sub(modulus, Q->y, t1)) != CRYPT_OK) { goto done; } + if (mp_cmp(P->y, t1) == LTC_MP_EQ) { + /* here Q = -P >>> Result = the point at infinity */ + if ((err = ltc_mp.set_int(R->x, 1)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.set_int(R->y, 1)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.set_int(R->z, 0)) != CRYPT_OK) { goto done; } + goto done; /* CRYPT_OK */ + } + } + + if ((err = mp_copy(P->x, x)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(P->y, y)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(P->z, z)) != CRYPT_OK) { goto done; } + + /* if Z is one then these are no-operations */ + if (Q->z != NULL) { + /* T1 = Z' * Z' */ + if ((err = mp_sqr(Q->z, t1)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; } + /* X = X * T1 */ + if ((err = mp_mul(t1, x, x)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(x, modulus, mp)) != CRYPT_OK) { goto done; } + /* T1 = Z' * T1 */ + if ((err = mp_mul(Q->z, t1, t1)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; } + /* Y = Y * T1 */ + if ((err = mp_mul(t1, y, y)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(y, modulus, mp)) != CRYPT_OK) { goto done; } + } + + /* T1 = Z*Z */ + if ((err = mp_sqr(z, t1)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; } + /* T2 = X' * T1 */ + if ((err = mp_mul(Q->x, t1, t2)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t2, modulus, mp)) != CRYPT_OK) { goto done; } + /* T1 = Z * T1 */ + if ((err = mp_mul(z, t1, t1)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; } + /* T1 = Y' * T1 */ + if ((err = mp_mul(Q->y, t1, t1)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; } + + /* Y = Y - T1 */ + if ((err = mp_sub(y, t1, y)) != CRYPT_OK) { goto done; } + if (mp_cmp_d(y, 0) == LTC_MP_LT) { + if ((err = mp_add(y, modulus, y)) != CRYPT_OK) { goto done; } + } + /* T1 = 2T1 */ + if ((err = mp_add(t1, t1, t1)) != CRYPT_OK) { goto done; } + if (mp_cmp(t1, modulus) != LTC_MP_LT) { + if ((err = mp_sub(t1, modulus, t1)) != CRYPT_OK) { goto done; } + } + /* T1 = Y + T1 */ + if ((err = mp_add(t1, y, t1)) != CRYPT_OK) { goto done; } + if (mp_cmp(t1, modulus) != LTC_MP_LT) { + if ((err = mp_sub(t1, modulus, t1)) != CRYPT_OK) { goto done; } + } + /* X = X - T2 */ + if ((err = mp_sub(x, t2, x)) != CRYPT_OK) { goto done; } + if (mp_cmp_d(x, 0) == LTC_MP_LT) { + if ((err = mp_add(x, modulus, x)) != CRYPT_OK) { goto done; } + } + /* T2 = 2T2 */ + if ((err = mp_add(t2, t2, t2)) != CRYPT_OK) { goto done; } + if (mp_cmp(t2, modulus) != LTC_MP_LT) { + if ((err = mp_sub(t2, modulus, t2)) != CRYPT_OK) { goto done; } + } + /* T2 = X + T2 */ + if ((err = mp_add(t2, x, t2)) != CRYPT_OK) { goto done; } + if (mp_cmp(t2, modulus) != LTC_MP_LT) { + if ((err = mp_sub(t2, modulus, t2)) != CRYPT_OK) { goto done; } + } + + /* if Z' != 1 */ + if (Q->z != NULL) { + /* Z = Z * Z' */ + if ((err = mp_mul(z, Q->z, z)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(z, modulus, mp)) != CRYPT_OK) { goto done; } + } + + /* Z = Z * X */ + if ((err = mp_mul(z, x, z)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(z, modulus, mp)) != CRYPT_OK) { goto done; } + + /* T1 = T1 * X */ + if ((err = mp_mul(t1, x, t1)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; } + /* X = X * X */ + if ((err = mp_sqr(x, x)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(x, modulus, mp)) != CRYPT_OK) { goto done; } + /* T2 = T2 * x */ + if ((err = mp_mul(t2, x, t2)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t2, modulus, mp)) != CRYPT_OK) { goto done; } + /* T1 = T1 * X */ + if ((err = mp_mul(t1, x, t1)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; } + + /* X = Y*Y */ + if ((err = mp_sqr(y, x)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(x, modulus, mp)) != CRYPT_OK) { goto done; } + /* X = X - T2 */ + if ((err = mp_sub(x, t2, x)) != CRYPT_OK) { goto done; } + if (mp_cmp_d(x, 0) == LTC_MP_LT) { + if ((err = mp_add(x, modulus, x)) != CRYPT_OK) { goto done; } + } + + /* T2 = T2 - X */ + if ((err = mp_sub(t2, x, t2)) != CRYPT_OK) { goto done; } + if (mp_cmp_d(t2, 0) == LTC_MP_LT) { + if ((err = mp_add(t2, modulus, t2)) != CRYPT_OK) { goto done; } + } + /* T2 = T2 - X */ + if ((err = mp_sub(t2, x, t2)) != CRYPT_OK) { goto done; } + if (mp_cmp_d(t2, 0) == LTC_MP_LT) { + if ((err = mp_add(t2, modulus, t2)) != CRYPT_OK) { goto done; } + } + /* T2 = T2 * Y */ + if ((err = mp_mul(t2, y, t2)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t2, modulus, mp)) != CRYPT_OK) { goto done; } + /* Y = T2 - T1 */ + if ((err = mp_sub(t2, t1, y)) != CRYPT_OK) { goto done; } + if (mp_cmp_d(y, 0) == LTC_MP_LT) { + if ((err = mp_add(y, modulus, y)) != CRYPT_OK) { goto done; } + } + /* Y = Y/2 */ + if (mp_isodd(y)) { + if ((err = mp_add(y, modulus, y)) != CRYPT_OK) { goto done; } + } + if ((err = mp_div_2(y, y)) != CRYPT_OK) { goto done; } + + if ((err = mp_copy(x, R->x)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(y, R->y)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(z, R->z)) != CRYPT_OK) { goto done; } + + err = CRYPT_OK; +done: + mp_clear_multi(t1, t2, x, y, z, NULL); + return err; +} + +#endif + +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + diff --git a/src/ltc/pk/ecc/ltc_ecc_projective_dbl_point.c b/src/ltc/pk/ecc/ltc_ecc_projective_dbl_point.c new file mode 100644 index 00000000..f954a597 --- /dev/null +++ b/src/ltc/pk/ecc/ltc_ecc_projective_dbl_point.c @@ -0,0 +1,200 @@ +/* LibTomCrypt, modular cryptographic library -- Tom St Denis + * + * LibTomCrypt is a library that provides various cryptographic + * algorithms in a highly modular and flexible manner. + * + * The library is free for all purposes without any express + * guarantee it works. + * + * Tom St Denis, tomstdenis@gmail.com, http://libtom.org + */ + +/* Implements ECC over Z/pZ for curve y^2 = x^3 + a*x + b + * + */ +#include "tomcrypt.h" + +/* ### Point doubling in Jacobian coordinate system ### + * + * let us have a curve: y^2 = x^3 + a*x + b + * in Jacobian coordinates it becomes: y^2 = x^3 + a*x*z^4 + b*z^6 + * + * The doubling of P = (Xp, Yp, Zp) is given by R = (Xr, Yr, Zr) where: + * Xr = M^2 - 2*S + * Yr = M * (S - Xr) - 8*T + * Zr = 2 * Yp * Zp + * + * M = 3 * Xp^2 + a*Zp^4 + * T = Yp^4 + * S = 4 * Xp * Yp^2 + * + * SPECIAL CASE: when a == -3 we can compute M as + * M = 3 * (Xp^2 - Zp^4) = 3 * (Xp + Zp^2) * (Xp - Zp^2) + */ + +/** + @file ltc_ecc_projective_dbl_point.c + ECC Crypto, Tom St Denis +*/ + +#if defined(LTC_MECC) && (!defined(LTC_MECC_ACCEL) || defined(LTM_DESC)) + +/** + Double an ECC point + @param P The point to double + @param R [out] The destination of the double + @param ma ECC curve parameter a in montgomery form (if NULL we assume a == -3) + @param modulus The modulus of the field the ECC curve is in + @param mp The "b" value from montgomery_setup() + @return CRYPT_OK on success +*/ +int ltc_ecc_projective_dbl_point(ecc_point *P, ecc_point *R, void *ma, void *modulus, void *mp) +{ + void *t1, *t2; + int err; + + LTC_ARGCHK(P != NULL); + LTC_ARGCHK(R != NULL); + LTC_ARGCHK(modulus != NULL); + LTC_ARGCHK(mp != NULL); + + if ((err = mp_init_multi(&t1, &t2, NULL)) != CRYPT_OK) { + return err; + } + + if (P != R) { + if ((err = mp_copy(P->x, R->x)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(P->y, R->y)) != CRYPT_OK) { goto done; } + if ((err = mp_copy(P->z, R->z)) != CRYPT_OK) { goto done; } + } + + if (ltc_ecc_is_point_at_infinity(P, modulus)) { + /* if P is point at infinity >> Result = point at infinity */ + if ((err = ltc_mp.set_int(R->x, 1)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.set_int(R->y, 1)) != CRYPT_OK) { goto done; } + if ((err = ltc_mp.set_int(R->z, 0)) != CRYPT_OK) { goto done; } + goto done; /* CRYPT_OK */ + } + + /* t1 = Z * Z */ + if ((err = mp_sqr(R->z, t1)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; } + /* Z = Y * Z */ + if ((err = mp_mul(R->z, R->y, R->z)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(R->z, modulus, mp)) != CRYPT_OK) { goto done; } + /* Z = 2Z */ + if ((err = mp_add(R->z, R->z, R->z)) != CRYPT_OK) { goto done; } + if (mp_cmp(R->z, modulus) != LTC_MP_LT) { + if ((err = mp_sub(R->z, modulus, R->z)) != CRYPT_OK) { goto done; } + } + + if (ma == NULL) { /* special case for ma == -3 (slightly faster than general case) */ + /* T2 = X - T1 */ + if ((err = mp_sub(R->x, t1, t2)) != CRYPT_OK) { goto done; } + if (mp_cmp_d(t2, 0) == LTC_MP_LT) { + if ((err = mp_add(t2, modulus, t2)) != CRYPT_OK) { goto done; } + } + /* T1 = X + T1 */ + if ((err = mp_add(t1, R->x, t1)) != CRYPT_OK) { goto done; } + if (mp_cmp(t1, modulus) != LTC_MP_LT) { + if ((err = mp_sub(t1, modulus, t1)) != CRYPT_OK) { goto done; } + } + /* T2 = T1 * T2 */ + if ((err = mp_mul(t1, t2, t2)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t2, modulus, mp)) != CRYPT_OK) { goto done; } + /* T1 = 2T2 */ + if ((err = mp_add(t2, t2, t1)) != CRYPT_OK) { goto done; } + if (mp_cmp(t1, modulus) != LTC_MP_LT) { + if ((err = mp_sub(t1, modulus, t1)) != CRYPT_OK) { goto done; } + } + /* T1 = T1 + T2 */ + if ((err = mp_add(t1, t2, t1)) != CRYPT_OK) { goto done; } + if (mp_cmp(t1, modulus) != LTC_MP_LT) { + if ((err = mp_sub(t1, modulus, t1)) != CRYPT_OK) { goto done; } + } + } + else { + /* T2 = T1 * T1 */ + if ((err = mp_sqr(t1, t2)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t2, modulus, mp)) != CRYPT_OK) { goto done; } + /* T1 = T2 * a */ + if ((err = mp_mul(t2, ma, t1)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t1, modulus, mp)) != CRYPT_OK) { goto done; } + /* T2 = X * X */ + if ((err = mp_sqr(R->x, t2)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t2, modulus, mp)) != CRYPT_OK) { goto done; } + /* T1 = T2 + T1 */ + if ((err = mp_add(t1, t2, t1)) != CRYPT_OK) { goto done; } + if (mp_cmp(t1, modulus) != LTC_MP_LT) { + if ((err = mp_sub(t1, modulus, t1)) != CRYPT_OK) { goto done; } + } + /* T1 = T2 + T1 */ + if ((err = mp_add(t1, t2, t1)) != CRYPT_OK) { goto done; } + if (mp_cmp(t1, modulus) != LTC_MP_LT) { + if ((err = mp_sub(t1, modulus, t1)) != CRYPT_OK) { goto done; } + } + /* T1 = T2 + T1 */ + if ((err = mp_add(t1, t2, t1)) != CRYPT_OK) { goto done; } + if (mp_cmp(t1, modulus) != LTC_MP_LT) { + if ((err = mp_sub(t1, modulus, t1)) != CRYPT_OK) { goto done; } + } + } + + /* Y = 2Y */ + if ((err = mp_add(R->y, R->y, R->y)) != CRYPT_OK) { goto done; } + if (mp_cmp(R->y, modulus) != LTC_MP_LT) { + if ((err = mp_sub(R->y, modulus, R->y)) != CRYPT_OK) { goto done; } + } + /* Y = Y * Y */ + if ((err = mp_sqr(R->y, R->y)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(R->y, modulus, mp)) != CRYPT_OK) { goto done; } + /* T2 = Y * Y */ + if ((err = mp_sqr(R->y, t2)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(t2, modulus, mp)) != CRYPT_OK) { goto done; } + /* T2 = T2/2 */ + if (mp_isodd(t2)) { + if ((err = mp_add(t2, modulus, t2)) != CRYPT_OK) { goto done; } + } + if ((err = mp_div_2(t2, t2)) != CRYPT_OK) { goto done; } + /* Y = Y * X */ + if ((err = mp_mul(R->y, R->x, R->y)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(R->y, modulus, mp)) != CRYPT_OK) { goto done; } + + /* X = T1 * T1 */ + if ((err = mp_sqr(t1, R->x)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(R->x, modulus, mp)) != CRYPT_OK) { goto done; } + /* X = X - Y */ + if ((err = mp_sub(R->x, R->y, R->x)) != CRYPT_OK) { goto done; } + if (mp_cmp_d(R->x, 0) == LTC_MP_LT) { + if ((err = mp_add(R->x, modulus, R->x)) != CRYPT_OK) { goto done; } + } + /* X = X - Y */ + if ((err = mp_sub(R->x, R->y, R->x)) != CRYPT_OK) { goto done; } + if (mp_cmp_d(R->x, 0) == LTC_MP_LT) { + if ((err = mp_add(R->x, modulus, R->x)) != CRYPT_OK) { goto done; } + } + + /* Y = Y - X */ + if ((err = mp_sub(R->y, R->x, R->y)) != CRYPT_OK) { goto done; } + if (mp_cmp_d(R->y, 0) == LTC_MP_LT) { + if ((err = mp_add(R->y, modulus, R->y)) != CRYPT_OK) { goto done; } + } + /* Y = Y * T1 */ + if ((err = mp_mul(R->y, t1, R->y)) != CRYPT_OK) { goto done; } + if ((err = mp_montgomery_reduce(R->y, modulus, mp)) != CRYPT_OK) { goto done; } + /* Y = Y - T2 */ + if ((err = mp_sub(R->y, t2, R->y)) != CRYPT_OK) { goto done; } + if (mp_cmp_d(R->y, 0) == LTC_MP_LT) { + if ((err = mp_add(R->y, modulus, R->y)) != CRYPT_OK) { goto done; } + } + + err = CRYPT_OK; +done: + mp_clear_multi(t1, t2, NULL); + return err; +} +#endif +/* $Source$ */ +/* $Revision$ */ +/* $Date$ */ + |