API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jul 22nd, 2017
50
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 28.25 KB | None | 0 0
raw download clone embed print report
  1. # HG changeset patch
  2. # Parent c8a83ff13320911abb1e77a9149959f28c4c4e9d
  3. Add COMB method
  4.  
  5. diff -r c8a83ff13320 Makefile
  6. --- a/Makefile  Mon Feb 14 14:13:04 2011 +0200
  7. +++ b/Makefile  Thu Feb 17 14:03:07 2011 +0200
  8. @@ -13,7 +13,7 @@
  9.  AFFINE_ZZ_P := utils.o ec.o ec_defaults.o ec_compress.o
  10.  AFFINE_GF2X := utils.o ec.o ec_defaults.o ec_compress.o
  11.  
  12. -PROJ_GF2X   := ec.o
  13. +PROJ_GF2X   := ec.o ec_comb.o
  14.  
  15.  HASHES := rmd160.o sha512.o sha1.o
  16.  GENERIC := octet.o hash.o mgf.o convhex.o
  17. diff -r c8a83ff13320 include/ec/GF2X/projective/ec.hpp
  18. --- a/include/ec/GF2X/projective/ec.hpp Mon Feb 14 14:13:04 2011 +0200
  19. +++ b/include/ec/GF2X/projective/ec.hpp Thu Feb 17 14:03:07 2011 +0200
  20. @@ -8,6 +8,9 @@
  21.  #include <memory>
  22.  
  23.  #include "ec/GF2X/affine/ec.hpp"
  24. +#include "ec/GF2X/projective/ec_precomputations.hpp"
  25. +#include "ec/GF2X/projective/ec_comb.hpp"
  26. +
  27.  
  28.  namespace ECGF2X
  29.  {
  30. @@ -27,20 +30,16 @@
  31.              GF2X Z;
  32.  
  33.              const EC & __EC;
  34. -
  35. +            
  36.              bool __isZeroPoint;
  37. -            bool __isPrecomputed;
  38. -
  39. -            /* ------ FIXED POINT PRECOMPUTATION DATA ------- */
  40. -            /* TODO: Make precomputations duplications in copy constructor */
  41. -            EC_Point ** __precomputations;
  42. -            int __precomputations_window;
  43. -            const unsigned char * __point_as_byte[2048];
  44. -            unsigned int __point_byte_size;
  45. -            /* ---------------------------------------------- */
  46. +            
  47. +            EC_Point_Precomputations * __precomputations;
  48.              
  49.          public:
  50. -            
  51. +
  52. +            /* Create point from point and it's precomputations */
  53. +            EC_Point(const EC_Point & Point,
  54. +                     EC_Point_Precomputations_Logic * Precomputations);
  55.              
  56.              EC_Point(const GF2X &X, const GF2X &Y, const GF2X &Z, const EC & __EC); // Projective
  57.              EC_Point(const EC_Point & Point); // Same point in same field
  58. @@ -53,13 +52,17 @@
  59.          public:
  60.              bool precompute(void);
  61.              
  62. +            inline bool isPrecomputed() const
  63. +                { if (__precomputations)
  64. +                        return __precomputations->isReady();
  65. +                    else
  66. +                        return false; }
  67.              
  68. -            inline bool isPrecomputed() const
  69. -                { return __isPrecomputed; }
  70. -            
  71. -
  72.              inline bool isZero() const
  73.                  { return __isZeroPoint; }
  74. +
  75. +            inline void setZero()
  76. +                { __isZeroPoint = true; }
  77.      
  78.              EC_Point & operator=  (const EC_Point & Y);
  79.              EC_Point   operator+  (const EC_Point & Y) const;
  80. @@ -110,11 +113,16 @@
  81.  
  82.          class EC : public Affine::EC
  83.          {
  84. -            const EC_Point G; // Base point in GF2X/Projective
  85. -
  86. +            EC_Point G; // Base point in GF2X/Projective
  87. +                        // Can be precomputed
  88. +            
  89. +            const Affine::EC_Point G_a;
  90. +            
  91.          public:
  92.              inline const EC_Point & getBasePoint() const
  93.                  { return G; }
  94. +            inline const Affine::EC_Point & getAffineBasePoint() const
  95. +                { return G_a; }
  96.  
  97.          public:
  98.              /* This EC curve class exists only for precomputations.
  99. diff -r c8a83ff13320 include/ec/GF2X/projective/ec_comb.hpp
  100. --- /dev/null   Thu Jan 01 00:00:00 1970 +0000
  101. +++ b/include/ec/GF2X/projective/ec_comb.hpp    Thu Feb 17 14:03:07 2011 +0200
  102. @@ -0,0 +1,52 @@
  103. +#pragma once
  104. +
  105. +#include <NTL/GF2X.h>
  106. +#include <NTL/ZZ.h>
  107. +#include <NTL/ZZ_p.h>
  108. +
  109. +#include <ostream>
  110. +#include <memory>
  111. +
  112. +#include "ec/GF2X/affine/ec.hpp"
  113. +
  114. +namespace ECGF2X
  115. +{
  116. +    namespace Projective
  117. +    {
  118. +        using NTL::GF2X;
  119. +        using NTL::GF2XModulus;
  120. +        using NTL::ZZ;
  121. +
  122. +        class EC_Point_Precomputations_Comb : public EC_Point_Precomputations_Logic
  123. +        {
  124. +            const long __precomputations_window;
  125. +            const long __precomputations_elements;
  126. +            
  127. +            Affine::EC_Point ** __precomputations;
  128. +            
  129. +            const long __precomputations_max_size;
  130. +            const long __precomputations_portion;
  131. +
  132. +        private:
  133. +            EC_Point_Precomputations_Comb(EC_Point_Precomputations_Comb & Source);
  134. +            
  135. +        public:
  136. +            EC_Point_Precomputations_Comb(); /* Empty precomputations. Totaly useless */
  137. +            EC_Point_Precomputations_Comb(const EC_Point & Source);
  138. +            ~EC_Point_Precomputations_Comb();
  139. +
  140. +        public:
  141. +            void Multiply(EC_Point & P,
  142. +                          const ZZ & Y) const;
  143. +            inline bool isReady(void)
  144. +                { return true; }
  145. +            
  146. +            
  147. +        private:
  148. +            long getMulPortions(void) const;
  149. +            const Affine::EC_Point & getPrecomputedForMul(const ZZ & scalar,
  150. +                                                          const long portion) const;
  151. +        };
  152. +    }
  153. +}
  154. +
  155. diff -r c8a83ff13320 include/ec/GF2X/projective/ec_comb_index.hpp
  156. --- /dev/null   Thu Jan 01 00:00:00 1970 +0000
  157. +++ b/include/ec/GF2X/projective/ec_comb_index.hpp  Thu Feb 17 14:03:07 2011 +0200
  158. @@ -0,0 +1,254 @@
  159. +#pragma once
  160. +
  161. +static const long comb_window = 8;
  162. +static const long comb_idx[] =
  163. +{
  164. +    3, 2, 1,
  165. +    5, 4, 1,
  166. +    6, 4, 2,
  167. +    7, 4, 3,
  168. +    9, 8, 1,
  169. +    10, 8, 2,
  170. +    11, 8, 3,
  171. +    12, 8, 4,
  172. +    13, 8, 5,
  173. +    14, 8, 6,
  174. +    15, 8, 7,
  175. +    17, 16, 1,
  176. +    18, 16, 2,
  177. +    19, 16, 3,
  178. +    20, 16, 4,
  179. +    21, 16, 5,
  180. +    22, 16, 6,
  181. +    23, 16, 7,
  182. +    24, 16, 8,
  183. +    25, 16, 9,
  184. +    26, 16, 10,
  185. +    27, 16, 11,
  186. +    28, 16, 12,
  187. +    29, 16, 13,
  188. +    30, 16, 14,
  189. +    31, 16, 15,
  190. +    33, 32, 1,
  191. +    34, 32, 2,
  192. +    35, 32, 3,
  193. +    36, 32, 4,
  194. +    37, 32, 5,
  195. +    38, 32, 6,
  196. +    39, 32, 7,
  197. +    40, 32, 8,
  198. +    41, 32, 9,
  199. +    42, 32, 10,
  200. +    43, 32, 11,
  201. +    44, 32, 12,
  202. +    45, 32, 13,
  203. +    46, 32, 14,
  204. +    47, 32, 15,
  205. +    48, 32, 16,
  206. +    49, 32, 17,
  207. +    50, 32, 18,
  208. +    51, 32, 19,
  209. +    52, 32, 20,
  210. +    53, 32, 21,
  211. +    54, 32, 22,
  212. +    55, 32, 23,
  213. +    56, 32, 24,
  214. +    57, 32, 25,
  215. +    58, 32, 26,
  216. +    59, 32, 27,
  217. +    60, 32, 28,
  218. +    61, 32, 29,
  219. +    62, 32, 30,
  220. +    63, 32, 31,
  221. +    65, 64, 1,
  222. +    66, 64, 2,
  223. +    67, 64, 3,
  224. +    68, 64, 4,
  225. +    69, 64, 5,
  226. +    70, 64, 6,
  227. +    71, 64, 7,
  228. +    72, 64, 8,
  229. +    73, 64, 9,
  230. +    74, 64, 10,
  231. +    75, 64, 11,
  232. +    76, 64, 12,
  233. +    77, 64, 13,
  234. +    78, 64, 14,
  235. +    79, 64, 15,
  236. +    80, 64, 16,
  237. +    81, 64, 17,
  238. +    82, 64, 18,
  239. +    83, 64, 19,
  240. +    84, 64, 20,
  241. +    85, 64, 21,
  242. +    86, 64, 22,
  243. +    87, 64, 23,
  244. +    88, 64, 24,
  245. +    89, 64, 25,
  246. +    90, 64, 26,
  247. +    91, 64, 27,
  248. +    92, 64, 28,
  249. +    93, 64, 29,
  250. +    94, 64, 30,
  251. +    95, 64, 31,
  252. +    96, 64, 32,
  253. +    97, 64, 33,
  254. +    98, 64, 34,
  255. +    99, 64, 35,
  256. +    100, 64, 36,
  257. +    101, 64, 37,
  258. +    102, 64, 38,
  259. +    103, 64, 39,
  260. +    104, 64, 40,
  261. +    105, 64, 41,
  262. +    106, 64, 42,
  263. +    107, 64, 43,
  264. +    108, 64, 44,
  265. +    109, 64, 45,
  266. +    110, 64, 46,
  267. +    111, 64, 47,
  268. +    112, 64, 48,
  269. +    113, 64, 49,
  270. +    114, 64, 50,
  271. +    115, 64, 51,
  272. +    116, 64, 52,
  273. +    117, 64, 53,
  274. +    118, 64, 54,
  275. +    119, 64, 55,
  276. +    120, 64, 56,
  277. +    121, 64, 57,
  278. +    122, 64, 58,
  279. +    123, 64, 59,
  280. +    124, 64, 60,
  281. +    125, 64, 61,
  282. +    126, 64, 62,
  283. +    127, 64, 63,
  284. +    129, 128, 1,
  285. +    130, 128, 2,
  286. +    131, 128, 3,
  287. +    132, 128, 4,
  288. +    133, 128, 5,
  289. +    134, 128, 6,
  290. +    135, 128, 7,
  291. +    136, 128, 8,
  292. +    137, 128, 9,
  293. +    138, 128, 10,
  294. +    139, 128, 11,
  295. +    140, 128, 12,
  296. +    141, 128, 13,
  297. +    142, 128, 14,
  298. +    143, 128, 15,
  299. +    144, 128, 16,
  300. +    145, 128, 17,
  301. +    146, 128, 18,
  302. +    147, 128, 19,
  303. +    148, 128, 20,
  304. +    149, 128, 21,
  305. +    150, 128, 22,
  306. +    151, 128, 23,
  307. +    152, 128, 24,
  308. +    153, 128, 25,
  309. +    154, 128, 26,
  310. +    155, 128, 27,
  311. +    156, 128, 28,
  312. +    157, 128, 29,
  313. +    158, 128, 30,
  314. +    159, 128, 31,
  315. +    160, 128, 32,
  316. +    161, 128, 33,
  317. +    162, 128, 34,
  318. +    163, 128, 35,
  319. +    164, 128, 36,
  320. +    165, 128, 37,
  321. +    166, 128, 38,
  322. +    167, 128, 39,
  323. +    168, 128, 40,
  324. +    169, 128, 41,
  325. +    170, 128, 42,
  326. +    171, 128, 43,
  327. +    172, 128, 44,
  328. +    173, 128, 45,
  329. +    174, 128, 46,
  330. +    175, 128, 47,
  331. +    176, 128, 48,
  332. +    177, 128, 49,
  333. +    178, 128, 50,
  334. +    179, 128, 51,
  335. +    180, 128, 52,
  336. +    181, 128, 53,
  337. +    182, 128, 54,
  338. +    183, 128, 55,
  339. +    184, 128, 56,
  340. +    185, 128, 57,
  341. +    186, 128, 58,
  342. +    187, 128, 59,
  343. +    188, 128, 60,
  344. +    189, 128, 61,
  345. +    190, 128, 62,
  346. +    191, 128, 63,
  347. +    192, 128, 64,
  348. +    193, 128, 65,
  349. +    194, 128, 66,
  350. +    195, 128, 67,
  351. +    196, 128, 68,
  352. +    197, 128, 69,
  353. +    198, 128, 70,
  354. +    199, 128, 71,
  355. +    200, 128, 72,
  356. +    201, 128, 73,
  357. +    202, 128, 74,
  358. +    203, 128, 75,
  359. +    204, 128, 76,
  360. +    205, 128, 77,
  361. +    206, 128, 78,
  362. +    207, 128, 79,
  363. +    208, 128, 80,
  364. +    209, 128, 81,
  365. +    210, 128, 82,
  366. +    211, 128, 83,
  367. +    212, 128, 84,
  368. +    213, 128, 85,
  369. +    214, 128, 86,
  370. +    215, 128, 87,
  371. +    216, 128, 88,
  372. +    217, 128, 89,
  373. +    218, 128, 90,
  374. +    219, 128, 91,
  375. +    220, 128, 92,
  376. +    221, 128, 93,
  377. +    222, 128, 94,
  378. +    223, 128, 95,
  379. +    224, 128, 96,
  380. +    225, 128, 97,
  381. +    226, 128, 98,
  382. +    227, 128, 99,
  383. +    228, 128, 100,
  384. +    229, 128, 101,
  385. +    230, 128, 102,
  386. +    231, 128, 103,
  387. +    232, 128, 104,
  388. +    233, 128, 105,
  389. +    234, 128, 106,
  390. +    235, 128, 107,
  391. +    236, 128, 108,
  392. +    237, 128, 109,
  393. +    238, 128, 110,
  394. +    239, 128, 111,
  395. +    240, 128, 112,
  396. +    241, 128, 113,
  397. +    242, 128, 114,
  398. +    243, 128, 115,
  399. +    244, 128, 116,
  400. +    245, 128, 117,
  401. +    246, 128, 118,
  402. +    247, 128, 119,
  403. +    248, 128, 120,
  404. +    249, 128, 121,
  405. +    250, 128, 122,
  406. +    251, 128, 123,
  407. +    252, 128, 124,
  408. +    253, 128, 125,
  409. +    254, 128, 126,
  410. +    255, 128, 127,
  411. +    257, 256, 1
  412. +};
  413. diff -r c8a83ff13320 include/ec/GF2X/projective/ec_precomputations.hpp
  414. --- /dev/null   Thu Jan 01 00:00:00 1970 +0000
  415. +++ b/include/ec/GF2X/projective/ec_precomputations.hpp Thu Feb 17 14:03:07 2011 +0200
  416. @@ -0,0 +1,88 @@
  417. +#pragma once
  418. +
  419. +#include <NTL/GF2X.h>
  420. +#include <NTL/ZZ.h>
  421. +#include <NTL/ZZ_p.h>
  422. +
  423. +#include <ostream>
  424. +#include <memory>
  425. +
  426. +#include "ec/GF2X/affine/ec.hpp"
  427. +
  428. +namespace ECGF2X
  429. +{
  430. +    namespace Projective
  431. +    {
  432. +        using NTL::GF2X;
  433. +        using NTL::GF2XModulus;
  434. +        using NTL::ZZ;
  435. +
  436. +        class EC;
  437. +        class EC_Point;
  438. +        
  439. +        class EC_Point_Precomputations_Logic
  440. +        {
  441. +        public:
  442. +            EC_Point_Precomputations_Logic() {};
  443. +            virtual ~EC_Point_Precomputations_Logic() {};
  444. +            virtual bool isReady(void) = 0;
  445. +            virtual void Multiply(EC_Point & P,
  446. +                                  const ZZ & Y) const = 0;
  447. +        };
  448. +        
  449. +        class EC_Point_Precomputations
  450. +        {
  451. +        private:
  452. +            long * __ref_counter;
  453. +            const bool __can_be_used;
  454. +
  455. +            EC_Point_Precomputations_Logic * __logic;
  456. +            
  457. +        protected:
  458. +            inline long * get(void)
  459. +                { std::cout << "GET" << std::endl; (* __ref_counter) ++ ; return __ref_counter; }
  460. +            
  461. +            inline long * drop (void)
  462. +                { std::cout << "DROP" << std::endl; (* __ref_counter) -- ; return __ref_counter; }
  463. +
  464. +            inline bool isLastUser (void)
  465. +                { return ( * __ref_counter) == 1; }
  466. +            
  467. +        public:
  468. +            EC_Point_Precomputations * operator= (EC_Point_Precomputations * Source)
  469. +                {
  470. +                    std::cout << "operator= on precomputations" << std::endl;
  471. +                    Source->get(); return Source; }
  472. +            
  473. +        public:
  474. +            bool isReady(void) const
  475. +                { return __can_be_used; }
  476. +
  477. +        private:
  478. +            EC_Point_Precomputations();
  479. +
  480. +        public:
  481. +            EC_Point_Precomputations(EC_Point_Precomputations_Logic * Logic)
  482. +                : __ref_counter(new long(0)),
  483. +                  __can_be_used(true),
  484. +                  __logic(Logic) {}
  485. +            
  486. +            EC_Point_Precomputations(EC_Point_Precomputations & Source)
  487. +                : __ref_counter(Source.get()),
  488. +                  __can_be_used(true),
  489. +                  __logic(Source.__logic) {}
  490. +            
  491. +            ~EC_Point_Precomputations() { drop(); if (isLastUser()) delete __logic; }
  492. +
  493. +        public:
  494. +            void Multiply(EC_Point & P,
  495. +                          const ZZ & Y) const
  496. +                {
  497. +                    if (__logic)
  498. +                        __logic->Multiply(P, Y);
  499. +                    else throw;
  500. +                }
  501. +            
  502. +        };
  503. +    }
  504. +}
  505. diff -r c8a83ff13320 src/ec/GF2X/projective/ec.cpp
  506. --- a/src/ec/GF2X/projective/ec.cpp Mon Feb 14 14:13:04 2011 +0200
  507. +++ b/src/ec/GF2X/projective/ec.cpp Thu Feb 17 14:03:07 2011 +0200
  508. @@ -1,4 +1,5 @@
  509.  #include "ec/GF2X/projective/ec.hpp"
  510. +#include "ec/GF2X/projective/ec_comb_index.hpp"
  511.  
  512.  #include "ec/GF2X/affine/ec.hpp"
  513.  #include "ec/GF2X/affine/utils.hpp"
  514. @@ -46,36 +47,72 @@
  515.          Lopez_Dahab_Mixed_Addition(EC_Point & P1,
  516.                                     const Affine::EC_Point & P2)
  517.          {
  518. +            std::cout << "MIXED ADDITION" << std::endl;
  519. +
  520. +            const GF2X & a = P1.getEC().getA();
  521. +            const GF2X & b = P1.getEC().getB();
  522.              const GF2XModulus & P = P1.getEC().getModulus();
  523. -            const GF2X & a = P1.getEC().getA();
  524. -            /* -------------------------------------- */
  525. -            const GF2X Z2  = SqrMod(P1.Z, P);
  526. -            const GF2X aZ2 = MulMod(a, Z2, P);
  527. -            /* -------------------------------------- */
  528. -            const GF2X A = MulMod(P2.getY(), Z2, P) + P1.Y;
  529. -            const GF2X B = MulMod(P2.getX(), P1.Z, P) + P1.X;
  530. -            const GF2X C = MulMod(P1.Z, B, P);
  531. +            const GF2X Z2 = SqrMod(P1.Z, P);
  532. +            const GF2X aZ2 = IsOne(a) ? Z2 : MulMod(a, Z2, P);
  533. +
  534. +            /* ------------------------------------- */
  535. +            
  536. +            const GF2X & X_2 = P2.getX();
  537. +            const GF2X & Y_2 = P2.getY();
  538. +            const GF2X & Z_1 = P1.getZ();
  539. +            const GF2X & X_1 = P1.getX();
  540. +            const GF2X & Y_1 = P1.getY();
  541. +            
  542. +            /* ------------------------------------- */
  543. +
  544. +            const GF2X A = MulMod(Y_2, Z2, P) + Y_1;
  545. +            const GF2X B = MulMod(X_2, Z_1, P) + X_1;
  546. +
  547. +            if (IsZero(B))
  548. +            {
  549. +                std::cout << "Try to double point" << std::endl;
  550. +
  551. +                P1.X = X_2;
  552. +                P1.Y = Y_2;
  553. +                P1.Z = GF2X(0, 1);
  554. +                
  555. +                Lopez_Dahab_Double(P1.X,
  556. +                                   P1.Y,
  557. +                                   P1.Z,
  558. +                                   a,
  559. +                                   b,
  560. +                                   P);
  561. +
  562. +                // std::cout << "X3: " << P1.X << std::endl;
  563. +                // std::cout << "Y3: " << P1.Y << std::endl;
  564. +                // std::cout << "Z3: " << P1.Z << std::endl;
  565. +
  566. +                return;
  567. +            }
  568. +            
  569. +            const GF2X C = MulMod(Z_1, B, P);
  570.              const GF2X D = MulMod(SqrMod(B, P),
  571. -                                  C + aZ2,
  572. +                                  (C + aZ2),
  573.                                    P);
  574. -            const GF2X E = MulMod(A, C, P);
  575. -    
  576. -            SqrMod(P1.Z, C, P);
  577. -            /* P1.Z == Z_3 */
  578. -            add(P1.X, SqrMod(A, P), D);
  579. -            P1.X += E;
  580. -            /* P1.X == X_3 */
  581. +            const GF2X Z_3 = SqrMod(C, P);
  582. +            const GF2X E   = MulMod(A, C, P);
  583. +            const GF2X X_3 = SqrMod(A, P) + D + E;
  584. +            const GF2X F   = MulMod(X_2, Z_3, P) + X_3;
  585. +            const GF2X G   = MulMod(X_2 + Y_2,
  586. +                                    SqrMod(Z_3, P),
  587. +                                    P);
  588. +            const GF2X Y_3 = MulMod(E+Z_3, F, P) + G;
  589.  
  590. -            const GF2X F = MulMod(P2.getX(), P1.Z, P) + P1.X;
  591. -            const GF2X G = MulMod(SqrMod(P1.Z, P),
  592. -                                  (P2.getX() + P2.getY()),
  593. -                                  P);
  594. -    
  595. -            P1.Y = MulMod(E + P1.Z, F, P) + G;
  596. +            // std::cout << "X3: " << X_3 << std::endl;
  597. +            // std::cout << "Y3: " << Y_3 << std::endl;
  598. +            // std::cout << "Z3: " << Z_3 << std::endl;
  599.  
  600. -            /* P1 == P3 */
  601. +            P1.X = X_3;
  602. +            P1.Y = Y_3;
  603. +            P1.Z = Z_3;
  604.          }
  605.  
  606. +
  607.          /* LNCS. 2000 / 1977, 10.1.1.75.402 */
  608.          inline void
  609.          Lopez_Dahab_Addition(EC_Point & P1,
  610. @@ -120,32 +157,38 @@
  611.                  {
  612.                      R += S;
  613.                  }
  614. -
  615. +                
  616.                  S += S;
  617.              }
  618.      
  619.              P = R;
  620.          }
  621. +        
  622.      }
  623.  
  624.      Projective::EC_Point
  625.      toProjective(const Affine::EC_Point & Point,
  626.                   const Projective::EC & EC)
  627.      {
  628. -        
  629. -        return EC.create(Point.getX(), Point.getY(),
  630. -                         GF2X(0, 1));
  631. +        if (Point.isZero())
  632. +            return EC.create();
  633. +        else
  634. +            return EC.create(Point.getX(), Point.getY(),
  635. +                             GF2X(0, 1));
  636.      }
  637. -
  638. +    
  639.  
  640.  
  641.      Affine::EC_Point
  642.      toAffine(const Projective::EC_Point & Point,
  643.               const Affine::EC & EC)
  644.      {
  645. +
  646. +        std::cout << "toAffine" << std::endl;
  647. +        std::cout << "Z: " << Point.getZ() << std::endl;
  648. +        
  649.          const GF2X & P = EC.getModulus();
  650.          const GF2X iZ = InvMod(Point.getZ(), P);
  651. -
  652.          return EC.create(MulMod(Point.getX(), iZ, P),
  653.                           MulMod(Point.getY(), SqrMod(iZ, P), P));
  654.      }
  655. @@ -160,32 +203,65 @@
  656.        Y(Point.Y),
  657.        Z(Point.Z),
  658.        __EC(Point.__EC),
  659. -      __isZeroPoint(Point.__isZeroPoint),
  660. -      __isPrecomputed(false),
  661. -      __precomputations(NULL),
  662. -      __precomputations_window(0)
  663. -{}
  664. +      __isZeroPoint(Point.__isZeroPoint)
  665. +{
  666. +    __precomputations = Point.__precomputations ?
  667. +        ( Point.__precomputations->isReady() ?
  668. +          Point.__precomputations : NULL) : NULL;
  669. +    
  670. +    std::cout << "Just Copy" << std::endl;
  671. +}
  672.  
  673.  EC_Point::EC_Point(const EC_Point & Point, bool isZero)
  674.      : X(isZero ? GF2X() : Point.X),
  675.        Y(isZero ? GF2X() : Point.Y),
  676.        Z(isZero ? GF2X() : Point.Z),
  677.        __EC(Point.__EC),
  678. -      __isZeroPoint(isZero),
  679. -      __isPrecomputed(false)
  680. +      __isZeroPoint(isZero)
  681. +{
  682. +    if (! isZero && Point.__precomputations)
  683. +    {
  684. +        __precomputations = Point.__precomputations->isReady() ?
  685. +            Point.__precomputations : NULL;
  686. +    }
  687. +    
  688. +}
  689.  
  690. -{}
  691. -
  692. +EC_Point::EC_Point(const EC_Point & Point, EC_Point_Precomputations_Logic * comp)
  693. +    : X(Point.X),
  694. +      Y(Point.Y),
  695. +      Z(Point.Z),
  696. +      __EC(Point.__EC),
  697. +      __isZeroPoint(Point.__isZeroPoint)
  698. +{
  699. +    if (comp->isReady())
  700. +    {
  701. +        __precomputations = new EC_Point_Precomputations(comp);
  702. +    }
  703. +    
  704. +    
  705. +    std::cout << "Copy + Attach precomputations" << std::endl;
  706. +    std::cout << "__precomputations = " << __precomputations << std::endl;
  707. +}
  708.  
  709.  EC_Point::EC_Point(const GF2X &X,
  710.                     const GF2X &Y,
  711.                     const GF2X &Z, const EC & __EC)
  712.      : X(X), Y(Y), Z(Z), __EC(__EC),
  713.        __isZeroPoint(false),
  714. -      __isPrecomputed(false)
  715. +      __precomputations(NULL)
  716.  {
  717. +
  718. +    std::cout << X << std::endl;
  719. +    std::cout << Y << std::endl;
  720. +    std::cout << Z << std::endl;
  721. +    std::cout << "IS ON CURVE? " << std::endl;
  722. +
  723.      if (! _IsOnCurve())
  724. +    {
  725.          throw;
  726. +    }
  727. +    
  728.  }
  729.  
  730.  EC_Point::EC_Point(const EC & __EC)
  731. @@ -194,11 +270,18 @@
  732.        Z(GF2X()),
  733.        __EC(__EC),
  734.        __isZeroPoint(true),
  735. -      __isPrecomputed(false)
  736. +      __precomputations(NULL)
  737.  {}
  738.  
  739.  EC_Point::~EC_Point()
  740. -{}
  741. +{
  742. +    if (__precomputations)
  743. +    {
  744. +        std::cout << "__precomputations at: " << __precomputations << std::endl;
  745. +        delete __precomputations;
  746. +    }
  747. +    
  748. +}
  749.  
  750.  /* Lopez - Dahab */
  751.  
  752. @@ -246,6 +329,11 @@
  753.          this->Y = Y.getY();
  754.          this->Z = Y.getZ();
  755.          this->__isZeroPoint = false;
  756. +        this->__precomputations = Y.__precomputations ?
  757. +            ( Y.__precomputations->isReady() ?
  758. +              Y.__precomputations : NULL)
  759. +            : NULL;
  760. +        
  761.      }
  762.      
  763.      return *this;
  764. @@ -294,6 +382,8 @@
  765.  
  766.      __retval+= _Y;
  767.      
  768. +    delete __retval.__precomputations;
  769. +    
  770.      return __retval;
  771.  }
  772.  
  773. @@ -311,7 +401,15 @@
  774.      }
  775.  
  776.      /* Doubling couldn't be */
  777. -    Lopez_Dahab_Mixed_Addition(*this, _Y);
  778. +    if ((IsOne(__EC.getA())) || (IsZero(__EC.getA())))
  779. +        Lopez_Dahab_Mixed_Addition(*this, _Y);
  780. +    else
  781. +    {
  782. +        /* FIXME ADD GENERIC ADDITIONS */
  783. +        abort();
  784. +        
  785. +    }
  786. +    
  787.      
  788.      return;
  789.  }
  790. @@ -320,42 +418,36 @@
  791.  {
  792.      if (isPrecomputed())
  793.      {
  794. +        std::cout << "PRECOMPUTATIONS VERSION" << std::endl;
  795. +        __precomputations->Multiply(*this, Y);
  796.      }
  797.      else
  798. +    {
  799. +        std::cout << "STANDARD VERSION" << std::endl;
  800.          Right_To_Left_Multiplication(*this, Y);
  801. +    }
  802. +    
  803.      return;
  804.  }
  805.  
  806.  EC_Point EC_Point::operator* (const ZZ & Y) const
  807.  {
  808.      EC_Point __retval(*this);
  809. +    
  810. +    __retval*= Y;
  811.  
  812. -    __retval*= Y;
  813. +    delete __retval.__precomputations;
  814.  
  815.      return __retval;
  816.  }
  817.  
  818. -bool EC_Point::precompute(void)
  819. -{
  820. -    __precomputations_window = 1 * sizeof(char) * 8;
  821. -    
  822. -    __precomputations = new EC_Point *[1 << __precomputations_window];
  823. -
  824. -    for (unsigned int i = 0; i < (1 << __precomputations_window); i++)
  825. -    {
  826. -        char bytes[4096]; // FIXME
  827. -    }
  828. -    
  829. -    
  830. -    return true;
  831. -}
  832. -
  833. -
  834.  
  835.  /* ----------------------- EC ---------------------------------- */
  836.  
  837.  EC::EC(const Affine::EC & EC)
  838. -    : Affine::EC(EC), G(toProjective(EC.getBasePoint(), *this))
  839. +    : Affine::EC(EC),
  840. +      G(toProjective(EC.getBasePoint(), *this)),
  841. +      G_a(EC.getBasePoint())
  842.  {}
  843.  
  844.  EC::~EC()
  845. diff -r c8a83ff13320 src/ec/GF2X/projective/ec_comb.cpp
  846. --- /dev/null   Thu Jan 01 00:00:00 1970 +0000
  847. +++ b/src/ec/GF2X/projective/ec_comb.cpp    Thu Feb 17 14:03:07 2011 +0200
  848. @@ -0,0 +1,154 @@
  849. +#include "ec/GF2X/projective/ec.hpp"
  850. +#include "ec/GF2X/projective/ec_comb_index.hpp"
  851. +
  852. +#include "ec/GF2X/affine/ec.hpp"
  853. +#include "ec/GF2X/affine/utils.hpp"
  854. +
  855. +using namespace ECGF2X;
  856. +using namespace ECGF2X::Projective;
  857. +
  858. +static inline Affine::EC_Point wdouble(const Affine::EC_Point & input,
  859. +                                       long window)
  860. +{
  861. +    Affine::EC_Point r(input);
  862. +    std::cout << "wdouble(" << window << ")" << std::endl;
  863. +    
  864. +    for (long i=0; i<window; i++)
  865. +    {
  866. +        r += r;
  867. +    }
  868. +
  869. +    return r;
  870. +}
  871. +
  872. +EC_Point_Precomputations_Comb::EC_Point_Precomputations_Comb()
  873. +    : __precomputations_window(0),
  874. +      __precomputations_elements(0),
  875. +      __precomputations(NULL),
  876. +      __precomputations_max_size(0),
  877. +      __precomputations_portion(0)
  878. +{}
  879. +
  880. +EC_Point_Precomputations_Comb::EC_Point_Precomputations_Comb(const EC_Point & Source)
  881. +    : __precomputations_window(comb_window),
  882. +      __precomputations_elements(1 << __precomputations_window),
  883. +      __precomputations(new Affine::EC_Point * [ __precomputations_elements ]),
  884. +      __precomputations_max_size(((NumBits(Source.getEC().getModulus()) +
  885. +                                   comb_window - 1) / comb_window) *
  886. +                                 comb_window),
  887. +      __precomputations_portion(__precomputations_max_size / __precomputations_window)
  888. +{
  889. +    Affine::EC_Point asAffine(toAffine(Source, Source.getEC()));
  890. +        
  891. +    /* Fill 0, 1, 2 */
  892. +    /* -------------------------------------------------------- */
  893. +    __precomputations[0] = new Affine::EC_Point(asAffine.getEC()); // Zero
  894. +    __precomputations[1] = new Affine::EC_Point(asAffine);         // This point
  895. +    /* ----------L----------------------------------------- */
  896. +
  897. +    Affine::EC_Point * prev = __precomputations[1];
  898. +    
  899. +    for (long i = 1; i<__precomputations_window; i++)
  900. +    {
  901. +        __precomputations[1<<i] =
  902. +            new Affine::EC_Point(
  903. +                wdouble(*prev,
  904. +                        __precomputations_portion));
  905. +        
  906. +        prev = __precomputations[1<<i];
  907. +    }
  908. +    
  909. +   for (long i = 0; i<__precomputations_elements - __precomputations_window - 1; i++)
  910. +    {
  911. +        long t_idx = comb_idx[i*3];
  912. +        long f_idx = comb_idx[i*3 + 1];
  913. +        long s_idx = comb_idx[i*3 + 2];
  914. +        // std::cout << "B: " << t_idx << " = " << f_idx << " + " << s_idx << std::endl;
  915. +
  916. +        __precomputations[t_idx] = new Affine::EC_Point(*__precomputations[f_idx] +
  917. +                                                        *__precomputations[s_idx]);
  918. +        
  919. +        // std::cout << "P: " << t_idx << " :: " << *__precomputations_own[t_idx] << std::endl;
  920. +        
  921. +    }
  922. +}
  923. +
  924. +EC_Point_Precomputations_Comb::~EC_Point_Precomputations_Comb()
  925. +{
  926. +
  927. +    std::cout << "DELETE PRECOMPUTATIONS" << std::endl;
  928. +    
  929. +    for (long i = 0; i< __precomputations_elements; i++)
  930. +    {
  931. +        delete __precomputations[i];
  932. +        
  933. +        __precomputations[i] = NULL;
  934. +    }
  935. +
  936. +    delete [] __precomputations;
  937. +}
  938. +
  939. +long EC_Point_Precomputations_Comb::getMulPortions(void) const
  940. +{
  941. +    return __precomputations_portion;
  942. +}
  943. +
  944. +
  945. +/* Buffer -- NTL -- Big endian */
  946. +static inline long comb_build_index(const ZZ & Y,
  947. +                                    const long window,
  948. +                                    const long portions,
  949. +                                    const long iteration)
  950. +{
  951. +    long index = 0x0;
  952. +
  953. +    for (long i = 0; i<window; i++)
  954. +    {
  955. +        index |=
  956. +            bit(Y, i*portions + iteration) << i;
  957. +        // std::cout << "Get bit: " << ( i*portions + iteration ) << std::endl;
  958. +    }
  959. +            
  960. +    // std::cout << "idx: " << index << std::endl;
  961. +    return index;
  962. +}
  963. +
  964. +
  965. +const Affine::EC_Point &
  966. +EC_Point_Precomputations_Comb::getPrecomputedForMul(const ZZ & scalar,
  967. +                                               const long portion) const
  968. +{
  969. +    if (NumBits(scalar) > __precomputations_max_size)
  970. +    {
  971. +        std::cout << "Couldn't use precomputations!" << std::endl;
  972. +
  973. +        throw;
  974. +    }
  975. +
  976. +    return * __precomputations[ comb_build_index(scalar,
  977. +                                                 __precomputations_window,
  978. +                                                 __precomputations_portion,
  979. +                                                 __precomputations_portion - portion - 1) ];
  980. +}
  981. +
  982. +
  983. +/* TODO: Check, that Multiply compatible with point ? */
  984. +void
  985. +EC_Point_Precomputations_Comb::Multiply(EC_Point & P,
  986. +                                   const ZZ & Y) const
  987. +{
  988. +    std::cout << "USING MIXED COMBO" << std::endl;
  989. +            
  990. +    P.setZero();
  991. +            
  992. +    for (long i = 0;
  993. +         i < getMulPortions();
  994. +         i++)
  995. +    {
  996. +        P += P;
  997. +        P += getPrecomputedForMul(Y, i);
  998. +    }
  999. +            
  1000. +    std::cout << "Is P On curve? " << P._IsOnCurve() << std::endl;
  1001. +}
  1002. +
  1003. diff -r c8a83ff13320 src/examples/basis.cpp
  1004. --- a/src/examples/basis.cpp    Mon Feb 14 14:13:04 2011 +0200
  1005. +++ b/src/examples/basis.cpp    Thu Feb 17 14:03:07 2011 +0200
  1006. @@ -23,8 +23,12 @@
  1007.      const EC_Point G = EC.getBasePoint();
  1008.      const Projective::EC_Point G_p = EC_p.getBasePoint();
  1009.  
  1010. +    ZZ seed;
  1011. +    seed += time(NULL);
  1012. +    SetSeed(seed);
  1013. +
  1014. +    
  1015.      ZZ k;
  1016. -
  1017.      EC.generate_random(k);
  1018.  
  1019.      cout << "Original: " << G << endl;
  1020. @@ -32,5 +36,19 @@
  1021.      cout << "O*k: " << G * k << endl;
  1022.      cout << "P*k => O: " << toAffine( G_p * k, EC ) << endl;
  1023.  
  1024. +    cout << "Try to precompute" << endl;
  1025. +
  1026. +    Projective::EC_Point_Precomputations_Comb comb(G_p);
  1027. +
  1028. +    Projective::EC_Point G_pp(G_p, & comb);
  1029. +    
  1030. +    cout << "Try to multiply" << endl;
  1031. +
  1032. +    cout << "Is computations ready? " << comb.isReady() << endl;
  1033. +    
  1034. +    cout << "Is basepoint powered with precomputations? " << G_pp.isPrecomputed() << endl;
  1035. +
  1036. +    cout << "PP*k => O:" << toAffine(G_pp * k, EC) << endl;
  1037. +
  1038.      return 0;
  1039.  }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!