Как известно, задача разложения числа на простые множители является вычислительно сложной, по крайней мере на настоящий момент — значит её можно взять за основу.
Кроме того любое число несёт в себе информацию. Исходя из этих двух идей, довольно легко придумать алгоритм шифрования:
1) Исходные данные представляются в виде двоичного кода (например, если это русский текст, то можно закодировать его по ГОСТу (iso8859-5), что бы занимал меньше места.
2) Текст разбивается N примерно равных частей по M бит. M должно быть достаточно большим, например, не менее 4096 (т.е. 512 байт). Для небольших текстов желательно взять две части. Это можно делать например командой split
3) Части интерпретируются просто как числа:
echo -n "какая-то фраза" | xxd -p -u # шестнадцатеричный вид
echo -n "какая-то фраза" | xxd -p -u | tr -dc 0-9A-F | dc -e16i?p # десятичный вид
Как пример: есть abc — в ASCII это \x61\x62\x63
А значит число будет 0x616263 или 6382179.
3.5) Шаг опциональный — для простого текста его можно не делать — каждый кусок текста оформляется таким образом, что бы к нему добавился номер и, например, маркер конца строки.
4) Теперь у нас есть N чисел. Далее, надо каждое из них превратить в простое. Для этого я предлагаю приписывать к ним от 0 до d цифр, где 0 цифр нужно, если случайно окажется, что число уже простое. А конкретные цифры, которые нужно приписать к числу находятся перебором. Цифры к числу приписываются обязательно слева: Bn=An*b^d+D — где D подбирается так, что бы число Bn было простым, а b — основание системы счисления (например 10, 16 или 256). При этом, подбирать придётся, скорей всего, не так уж и долго.
5) Все полученные числа перемножаются.
6) Полученный результат для удобства следует представить в виде печатных знаков, например с помощью base64:
$ echo 1254542325621 | dc -e ?P | base64
ASQYjLd1
Шифротекст готов. Кстати, я тут попробовал этот алгоритм применить вручную. Попробуйте расшифровать:
F2by3fRqZDAzNocxFDcKvU9wRhELEcrP/HMmN/KPhmwh6x43OpW3p55W+UjxZybvCki1sQhMUfmbDiL9fhVygQ==
Кроме того, хотелось бы узнать ваше мнение о криптостойкости данного шифра.
Кстати, о применении:
1) Классическое шифрование — в качестве ключа случайное число, которое просто умножается на открытый текст.
2) Хеширование — взять последние несколько байт полученного составного числа
3) Например, вы не хотите светить свои личные данные, но хотите иметь возможность доказать, что это вы в случае чего (например восстановление пароля на сайте).
Для этого нужные данные (например email-адрес) дополняются мусором и шифруются моим алгоритмом. Полученный результат отправляется на сайт. Далее, если вам понадобится восстановить аккаунт, можно отправить админу сообщение с нужного e-mail, содержащее один из простых множителей — админ делит шифротекст на него, получает результат и убеждается, что он совпадает с адресом, откуда отправлено письмо — тогда он высылает на этот адрес новый пароль.
Можно использовать для этого и что-то другое, например md5 от e-mail-адреса с солью, но это менее надёжно, так как в принципе возможны коллизии. Мой алгоритм по сравнению с алгоритмами хеширования всегда гарантирует принципиальную возможность получить исходный текст полностью. (по крайней мере, если добавить способ отличить кусок текста от D)
Правда, этот алгоритм имеет некоторую уязвимость — если знать часть исходного текста и шифротекст — восстановить остальное становится проще (А если знать (N-1)/N теста — можно восстановить 1/N вообще без усилий).
