GenerateKey.h

#pragma once

#include <vector>
#include <cmath>

// Ãåíåðàòîð ïàðû îòêðûòîãî è çàêðûòîãî êëþ÷åé
class GenerateKey
{
   // Äâà ïðîñòûõ ÷èñëà 
   // äëÿ ãåíåðàöèè êëþ÷åé
   struct PairPrime
   {
      uint64_t p, q;
   };

   // Ðåçóëüòàò ðàñøèðåííîãî àëãîðèòìà 
   // Åâêëèäà
   struct ResultGSDAdv
   {
      uint64_t a;
      int64_t adXi, adYi;
   };
   //------------------------------------------------------
public:
   struct Key
   {
      uint64_t exp, mod;
   };

   struct PairKeys
   {
      Key publicKey, primaryKey;
   };
   //------------------------------------------------------

   GenerateKey()
   {
      primes = sieveSundarama(500);
   }
   //------------------------------------------------------

   ~GenerateKey()
   {
      primes.clear();
   }
   //------------------------------------------------------

   /*Ãåíåðèðóåò îòêðûòûé è çàêðûòûé êëþ÷è
   *
   * Íè÷åãî íå ïðèíèìàåò
   *
   * Âîçâðàùàåò ïàðó: îòêðûòûé è çàêðûòûé êëþ÷è*/
   PairKeys Generate()
   {
      PairPrime pairPrime = generatePairPrime();
      uint64_t n = pairPrime.p * pairPrime.q;
      uint64_t funcEuler = (pairPrime.p - 1) *
         (pairPrime.q - 1);

      uint64_t publicExp = selectPublicExp(funcEuler);
      uint64_t primaryExp = calcInvNum(publicExp,
         funcEuler);
      PairKeys pair =
      {
         { publicExp, n },
         { primaryExp, n }
      };
      return pair;
   }
   //------------------------------------------------------

private:
   std::vector<uint64_t> primes;

   /*Âû÷èñëÿåò îáðàòíûé ýëåìåíò ÷èñëà ïî ìîäóëþ
   *
   * Ïðèíèìàåò ÷èñëà num è ìîäóëü mod
   *
   * Âîçâðàùàåò âû÷èñëåííîå çíà÷åíèå îáðàòíîãî ÷èñëà */
   uint64_t calcInvNum(uint64_t num, uint64_t mod)
   {
      ResultGSDAdv result;
      result = gsdAdvance(mod, num);
      while (result.adYi < 0)
         result.adYi += mod;
      return result.adYi;

      /*if (mod >= num)
      {
         result = gsdAdvance(mod, num);
      while (result.adYi < 0)
         result.adYi += mod;
      return result.adYi;
      }
      else
      {
         result = gsdAdvance(num, mod);
         while (result.adXi < 0)
            result.adXi += mod;
         return result.adXi;
      }*/
   }
   //------------------------------------------------------

   /*Âûáîð îòêðûòîé ýêñïîíåíòû
   *
   * Ïðèíèìàåò çíà÷åíèå ôóíêöèè ýéëåðà
   *
   * Âîçâðàùàåò îòêðûòóþ ýêñïîíåíòó*/
   uint64_t selectPublicExp(uint64_t funcEuler)
   {
      size_t bound = 30;
      uint64_t exp = 0;
      while (true)
      {
         exp = primes[rand() % bound];
         if (funcEuler > exp && checkMutuallyPrime(funcEuler, exp))
            break;
      }
      return exp;
   }
   //------------------------------------------------------

   //Âû÷èñëÿåò çíà÷åíèÿ ïî ðàñøèðåííîìó àëãîðèòìó åâêëèäà
   ResultGSDAdv gsdAdvance(uint64_t a, uint64_t b,
      int64_t x1 = 0, int64_t x2 = 1, int64_t y1 = 1, 
      int64_t y2 = 0)
   {
      if (b == 0) {
         return { a, x2, y2 };
      }
      else {
         uint64_t tmp = a % b;
         uint64_t addiv = a / b;
         a = b;
         b = tmp;

         int64_t adXi = x2 - addiv * x1;
         int64_t adYi = y2 - addiv * y1;

         return gsdAdvance(a, b, adXi, x1, adYi, y1);
      }
   }
   //------------------------------------------------------

   /*Ïðîâåðêà íà âçàèìíóþ ïðîñòîòó ÷èñåë
   *
   * Ïðèíèìàåò äâà ÷èñëà a è b
   * 
   * Âîçâðàùàåò true åñëè ÷èñëà âçàèìíî ïðîñòûå è 
   * false â ïðîòèâíîì ñëó÷àå*/
   bool checkMutuallyPrime(uint64_t a, uint64_t b)
   {
      uint64_t res = a > b ?
         gsdAdvance(a, b, 0, 1, 1, 0).a :
         gsdAdvance(b, a, 0, 1, 1, 0).a;
      return res == 1 ? true : false;
   }
   //------------------------------------------------------

   //Ãåíåðèðóåò ïàðó ïðîñòûõ ÷èñåë
   PairPrime generatePairPrime()
   {
      size_t size = primes.size();
      size_t firstQuarter = size / 4;
      size_t indp = firstQuarter + (rand() % (size - firstQuarter)),
         indq = firstQuarter + (rand() % (size - firstQuarter));
      return { primes[indp], primes[indq] };
   }
   //------------------------------------------------------

   /*Âûñ÷èòûâàåò ïðîñòûå ÷èñëà äî maxNum*2 
   *
   * Ïðèíèìàåò ìàêñèìàëüíîå çíà÷åíèå maxNum
   * 
   * Âîçâðàùàåò âåêòîð ïðîñòûõ ÷èñåë*/
   std::vector<uint64_t> sieveSundarama(uint64_t maxNum)
   {
      const uint64_t len = maxNum + 1;
      std::vector<uint64_t> primes(len + 1);

      // Çàïèñûâàåì âñå ÷èñëà â âåêòîð
      for (uint64_t i = 0; i <= len; ++i)
      {
         primes[i] = i;
      }

      // Âû÷åðêèâàåì òå, ÷òî ñîîòâåòñòâóþò êðèòåðèþ 
      uint64_t bound = ((uint64_t)sqrt(2 * maxNum + 1) - 1) / 2;
      for (uint64_t i = 1; i <= bound; i++)
      {
         for (uint64_t j = i; j <= (maxNum - i) / (2 * i + 1); j++)
         {
            if (i + j + 2 * i * j <= maxNum)
            {
               primes[i + j + 2 * i * j] = 0;
            }
         }
      }

      std::vector<uint64_t> result;
      result.push_back(2);

      // Îñòàâøèåñÿ ÷èñëà óìíîæàåì íà 2 è ñêëàäûâàåì ñ 1
      // è çàïèñûâàåì â ðåçóëüòàò
      for (size_t i = 0; i < primes.size(); i++)
      {
         if (primes[i] != 0)
            result.push_back(primes[i] * 2 + 1);
      }

      return result;
   }
};