Криптосистема Рабина на языке Python

Криптосистема Рабина

Криптосистема Рабина - криптографическая система с открытым ключом, безопасность которой обеспечивается сложностью поиска квадратных корней составного числа. Безопасность системы, как и безопасность метода RSA, обусловлена сложностью разложения на множители больших чисел.

Зашифрованное сообщение можно расшифровать 4 способами.

Недостатком системы является необходимость выбора истинного сообщения из 4-х возможных.

История

В январе 1979 года Майкл О. Рабин опубликовал описание своей системы. Было доказано, что восстановление исходного текста из зашифрованного столь же трудно, как факторизация больших чисел. Система Рабина стала первой асимметричной криптосистемой, для которой было выполнено такое доказательство. Сложность восстановления связана с трудностью извлечения квадратного корня по модулю составного числа N = р · q. Задача факторизации и задача по извлечению квадратного корня эквивалентны, то есть:

• зная простые делители числа N можно извлекать квадратные корни по модулю N;
• умея извлекать квадратные корни по модулю N, можно разложить N на простые множители.

Генерация ключа

Система Рабина, как и любая асимметричная криптосистема, использует открытый и закрытый ключи. Открытый ключ используется для шифрования сообщений и может быть опубликован для всеобщего обозрения. Закрытый ключ необходим для расшифровки и должен быть известен только получателям зашифрованных сообщений.

Процесс генерации ключей следующий:

выбираются два случайных числа p и q с учётом следующих требований:

• числа должны быть большими;
• числа должны быть простыми;
• должно выполняться условие: p ≡ q ≡ 3 mod 4.

Выполнение этих требований сильно ускоряет процедуру извлечения корней по модулю р и q;

• вычисляется число n = p · q;
• число n — открытый ключ; числа p и q — закрытый.

Шифрование

Исходное сообщение m (текст) шифруется с помощью открытого ключа - числа n по следующей формуле: c = m² mod n.

Благодаря использованию умножения по модулю скорость шифрования системы Рабина больше, чем скорость шифрования по методу RSA, даже если в последнем случае выбрать небольшое значение экспоненты.

Расшифровка

Для расшифровки сообщения необходим закрытый ключ — числа p и q. Процесс расшифровки выглядит следующим образом:

• сначала, используя алгоритм Эвклида, из уравнения ypp+yqq=1 находят числа yp и yq;
• далее, используя китайскую теорему об остатках, вычисляют четыре числа:

...

...