Реализация алгоритма RSA (PHP)

    Во вчерашней публикации пользователи runcore и pixxxel попросили поделиться еще информацией о простых и надежных обратимых алгоритмах и конкретно RSA соответственно. Т.к. я в свое время интересовался этим вопросом и реализовывал подобные алгоритмы, то один из них, пример класса для осуществления шифрования методом RSA я вам предлагаю .

    Собственно теоретическую часть можно найти тут, в более менее доступной форме тут. Я же в свое время использовал книгу Брюса Шнайера «Прикладная криптография».

    Для приготовления кода на понадобятся:

    1. Расширеный алгоритм Эвклида
    2. Алгоритм поиска НОД.
    3. Адаптированый алгоритм быстрого возведения числа в степень

    Т.к. подготовительная часть более или менее пройдена можно перейти к реализации.
    Далее идет код реализации алгоритма, с моими комментариями:

    Copy Source | Copy HTML
    1. class CRSA
    2. {
    3.  
    4.     // Два простых числа p и q
    5.     private $p=0x0;
    6.     private $q=0x0;
    7.  
    8.  
    9.     // соответственно значение функции n(p,q), ph(p,q) этих простых чисел
    10.     private $ph=0x0;
    11.     private $n=0x0;
    12.  
    13.  
    14.     // Ключи шифрования и дешифровки
    15.     private $e=0x0;
    16.     private $d=0x0;
    17.  
    18.     // Расшифрованая строка и вектор с зашифрованными символами
    19.     private $decriptedData="";
    20.     private $encriptedData=array();
    21.  
    22.  
    23.  
    24.     function __construct($p=0x0, $q=0x0)
    25.     {
    26.         $this->initPQParams($p, $q);
    27.     }
    28.  
    29.     // Инициация функций n и ph
    30.     function initPQParams($p=0x0, $q=0x0)
    31.     {
    32.         $this->p=$p;
    33.         $this->q=$q;
    34.  
    35.         if ($this->p && $this->q && ($this->q!=$this->p))
    36.         {
    37.             $this->n=$this->p*$this->q;
    38.             $this->ph=($this->p-1)*($this->q-1);
    39.         }
    40.     }
    41.  
    42.     // Инициирование подходящего ключа шифрования
    43.     function initEncryptingKey($e=0x0)
    44.     {
    45.  
    46.         if (!$this->ph || !$e)
    47.             return false;
    48.  
    49.         $this->e=$e;
    50.  
    51.         while (!$this->isMutuallyDistinct($this->e, $this->ph))
    52.             $this->e+=2;
    53.  
    54.         return true;
    55.     }
    56.  
    57.  
    58.     // Проверка на чисел на взаимную простоту
    59.     private function isMutuallyDistinct($a, $b)
    60.     {
    61.         while(($a!=0x0) && ($b!=0x0))
    62.             if($a>=$b) $a=$a%$b;
    63.                 else $b=$b%$a;
    64.  
    65.         return (($a+$b)==1)?true:false;
    66.     }
    67.  
    68.     // Реализация расширеного алгоритма Эвклида для поиска
    69.     // ключа дешифрования
    70.     function generateDecripringKey()
    71.     {
    72.         $u1=1;
    73.         $u2=0x0;
    74.         $u3=$this->ph;
    75.         $r1=0x0;
    76.         $r2=1;
    77.         $r3=$this->e;
    78.  
    79.         while ($r3)
    80.         {
    81.             if(!$r3)
    82.              break;
    83.  
    84.             $q=(int)(((int)$u3)/((int)$r3));
    85.             $t1=($u1-$r1*$q);
    86.             $t2=($u2-$r2*$q);
    87.             $t3=($u3-$r3*$q);
    88.             $u1=$r1;
    89.             $u2=$r2;
    90.             $u3=$r3;
    91.             $r1=$t1;
    92.             $r2=$t2;
    93.             $r3=$t3;
    94.         }
    95.         $this->d=$u2;
    96.  
    97.     }
    98.  
    99.     // Ну тут даже пояснить ничего не надо
    100.     function getEncripringKey()
    101.     {
    102.         return $this->e;
    103.     }
    104.  
    105.     // Тут тоже
    106.     function getDecriptingKey($forced=false)
    107.     {
    108.         if ((!$this->d) || ($forced))
    109.         {
    110.             $this->d=0x0;
    111.             $this->generateDecripringKey();
    112.         }
    113.         return $this->d;
    114.     }
    115.  
    116.  
    117.     // Ф-я шифрования, может работать опираясь как на ранее 
    118.     // ининциированные свойства, так и напрямую от параметров -   
    119.     // ключа шифрации и занчения n(p,q);
    120.     function EncriptX($data, $e=0x0, $n=0x0)
    121.     {
    122.         if ($e>0x0 && $n>0x0)
    123.         {
    124.             $this->n=$n;
    125.             $this->e=$e;
    126.         }
    127.  
    128.         for ($j=0x0; $j<strlen($data); $j++)
    129.         {
    130.             $b=ord($data[$j]);
    131.             $result = 1;
    132.             for($i=0x0; $i<$this->e; $i++)
    133.             {
    134.                 $result = ($result*$b) % $this->n;
    135.             }
    136.             $this->encriptedData[$j]=$result;
    137.         }
    138.     }
    139.  
    140.     // Аналогично ф-ии шифрования
    141.     function DecriptX($d=0x0, $n=0x0)
    142.     {
    143.         if ($d>0x0 && $n>0x0)
    144.         {
    145.             $this->d=$d;
    146.             $this->n=$n;
    147.         }
    148.  
    149.         $result = 1;
    150.         for ($j=0x0; $j<count($this->encriptedData); $j++)
    151.         {
    152.             $b=($this->encriptedData[$j]);
    153.             $result = 1;
    154.             for($i=0x0; $i<$this->d; $i++)
    155.             {
    156.                 $result = ($result*$b) % $this->n;
    157.             }
    158.             $this->decriptedData .= chr($result);
    159.         }
    160.  
    161.         return $this->decriptedData;
    162.     }
    163. }


    Вот собственно релизация класса, применять можно двумя способами

    Способ номер раз:

    Copy Source | Copy HTML
    1. $rsa=new CRSA(47, 71);
    2. if ($rsa->initEncryptingKey(79))
    3. {
    4.      $rsa->EncriptX(«Блин, как все сложно»);
    5.      echo "\n";
    6.      $rsa->getDecriptingKey(true);
    7.      echo $rsa->DecriptX();
    8.      echo "\n";
    9. }


    Способ номер два:

    Copy Source | Copy HTML
    1. $rsa=new CRSA();
    2. $rsa->EncriptX("Блин, как все сложно", 79, 3337);
    3. echo "\n";
    4. echo $rsa->DecriptX(1019, 3337);
    5. echo "\n";


    Благодарности:
    Отдельное спасибо пользователям за предоставленную возможность опубликовать статью.

    Прочее:
    Еще одну реализацию данного алгоритма можно найти здесь.

    Нули записаны в шестнадцатиричной форме чтобы парсер не кушал.

    UPD:

    Как справедливо отмечено в комментариях, реализация болше ради академического интереса, т.к. существующие в PHP ограничения типов данных не позволяют шифровать сколь-либо серъезной длиной ключа.

    Но для шифрации краткосрочных сессионных данных вполне может подойти.

    UPD 2:

    Так же реализацию можно найти и здесь (спс. пользователю galaxy)
    Поделиться публикацией

    Похожие публикации

    Комментарии 11

      +2
      А что, вызвать openssl из PHP уже некошерно?
        +1
        В PHP (да и собственно в большинстве случаев в других языках) конечно кошернее вызывать встроеную ф-ю нежели самописную, это не предмет для дискусии. Вопрос в том доступно ли это расширение.
          +1
          Интересно а на какой системе может быть установлен PHP и не может быть установлен openssl?
        +1
        Практической значимости 0. Лишь теоретико-академическая. Да и писать это на интерпретируемом языке ИМХО не самый лучший вариант. Конечно может я и недооцениваю их скорость относительно тех же С/С++.
        Да и с ключами такой длины криптостойкость очень слаба.
          +1
          Все верно… Именно для этой цели и писалась статья… Академический интерес, транслировать на другой (более подходящий) язык труда не составит… Основные потенциально проблемные моменты выделены… Ну а длина ключей да, согласен… Пин код своей карточки шифровать именно средствами PHP я бы не стал…
          –3
          Красота! Можно мне использовать ваш код в своем проекте?
            0
            Ну если найдете ему практическое применение я буду только рад :)
              0
              Я долго искал его, спасибо!
              Просто мне нужно было асимметричное шифрование, работающее на любом хостинге
            0
            if ($rsa->initEncryptingKey(79))

            $rsa->getDecriptingKey(true);

            Вы уж определитесь…

            Алгоритма быстрого возведения в степень я как-то не увидел. Как было отмечено, практическая ценность стремится к нулю, хотя бы потому, что разрядность ключа ограничена 31 битом.

            PS: Еще одна реализация: pear.php.net/package/Crypt_RSA
              0
              А вот еще можно попробовать переписать это дело на bc_math и тогда можно будет попытаться использовать в проектах.
                0
                Вполне, в одной из приведенных в топике ссылок реализовано именно так :)

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое