Реализация алгоритма 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)