Реализация RSA класса на PHP

По ходу работы, я часто сталкиваюсь с интересными и неординарными задачами, в очередной раз такая задача была направленна на применение криптоалгоритма RSA (буквенная аббревиатура от фамилий Rivest, Shamir и Adleman). Описание RSA было опубликовано в августе 1977 года в журнале Scientific American.

Криптографические системы с открытым ключом используют однонаправленные функции, они обладают следующим свойством:
Если X известно, то функцию от X вычислить относительно просто
Если известно, что Y = функция от X, то для X нет простого пути вычисления
Под однонаправленностью понимается не теоретическая однонаправленость, а практическая невозможность вычислить обратное значение, применяя современные средства, за обозримый интервал времени.
В основу криптографической системы RSA положена задача умножения и разложения простых чисел на множители, которая является вычислительно однонаправленной задачей.
В криптографической системе с открытым ключом каждый располагает как открытым ключом (public key), так и секретным\приватным ключом (secret\private key). Каждый ключ — это часть информации. В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и секретный ключ самостоятельно. Секретный ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и секретный ключи каждого участника обмена сообщениями образуют «согласованную пару» в том смысле, что они являются взаимно обратными.

На 2009 год система шифрования на основе RSA считается надёжной, начиная с размера N в 1024 бита.

Зная разложение модуля на произведение двух простых чисел, противник может легко найти секретную экспоненту d и тем самым взломать RSA. Однако на сегодняшний день самый быстрый алгоритм факторизации — решето обобщённого числового поля (General Number Field Sieve), скорость которого для k-битного целого числа не позволяет разложить большое целое за приемлемое время.

И теперь перейдем от теории к практике. Я не стал изобретать велосипед и взял уже готовый класс от Khaled Al-Sham’aa. Какие у него плюсы? Плюс один и очень большой – его класс легко читаем, и прост для изучения. В добавок прилагается пример и краткое описание принципа открытых ключей и теория RSA.

качаем тут -> Khaled Al-Sham’aa RSA Class PHP

Расмотрим пример:

тут мы подключаем класс и создаем его экземпляр

include('rsa.class.php');
$RSA = new RSA();

далее мы создаем пару ключей из исходных простых чисел (как их генерировать на лету я расскажу позже)

$keys = $RSA->generate_keys ('9990454949', '9990450271', 1);

тут мы видим пример шифрования и дешифрования фразы

$message="هذا نص عربي بتنسيق مجموعة المحارف العالمية";
$encoded = $RSA->encrypt ($message, $keys[1], $keys[0], 5);
$decoded = $RSA->decrypt ($encoded, $keys[2], $keys[0]);

также чуть ниже мы видим вывод сигнатуры закриптованного сообщения (с его помощью мы можем проверить правильно ли все работает)

$signature = $RSA->sign($message, $keys[1], $keys[0]);

собственно вот тут мы и проверяем подлинность (предварительно мы опредилили переменную $fake_msg которая отличается от переменной $message, но $signature осталась прежняя)

echo "Success: ".(($RSA->prove($fake_msg, $signature, $keys[2], $keys[0])) ? "True" : "False")."\n";

данный код выведет False

Если смотреть пример далее то мы можем увидеть, что в этом классе существует возможность шифровать и проверять файлы используя функции signFile и proveFile.

В принципе алгоритм рабочий. Однако я сделал небольшое усовершенствование зашифровав оба ключа base64_encode для лучшего восприятия, но это не все.

Для генерации простых чисел я использовал небольшой и стабильный код. Конечно это не лучший вариант, но необходимости в оптимальном исполнении небыло.

private function prime($n,$s=2) {
for ($i=$s;$i<=$n;$i++) {
$flag=true;
for ($k=2;$k*$k<=$i;$k++) {
if ($i%$k == 0) {
$flag=false;
break;
}
}
if ($flag==true) {
$ret[]=$i;
}
}
return $ret;
}

естественно это находится внутри класса

а при генерации ключей включил вот такой код

public function generate_keys ($show_debug=0){

do {
$sta=rand(1000,9999);
$ret=$this->prime(intval($sta.'22500'),intval($sta.'22000'));
$k=rand(0,count($ret));
$p=$ret[$k];
$k=rand(0,count($ret));
$q=$ret[$k];
} while (($p=='') OR ($q=='') OR ($p==$q));

что дает нам генерацию ключей с псевдослучайной рандомизацией.

Естественно этот класс и данный пример не подходят, когда нам нужно устойчивое шифрование, но ни что не мешает нам оптимизировать его.
Спасибо, что дочиталю до конца =) Был бы рад инвайту.