Добрый день!

Данный алгоритм представлен следующей схемой:
На вход подается 128 байтное число, для расшифровки используются 2 числа одно
128 байт, другое 4 байта = 0x00010001,при этом проверяется чтобы входящее число
было меньше 128 байтового числа используемого для расшифровки.
Все операции проводятся с большими числами.
Определение входных параметров :
Crypt — 128 байт шифра
Key1 — 128 байт
Key2 — 4 байта = 0x00010001

Шаг 1: Определяется количество циклов Count, и преобразуется Key2 по схеме
Key2=0x00010001
Count=0;
while ((Key2>>30) & 3 ==0)
{
Count=Count+2;
Key2=Key2<<2;
}
Шаг 2: One=1 /* Большое число */
for(i=0;i<Count;i=i+2)
{
Tmp=BigMul(One,One) /* Результат произведение One*One */
One=BigMod(Tmp,Key1) /* Результат остаток от деления Tmp на Key1 */
Tmp=BigMul(One,One)
One=BigMod(Tmp,Key1)
if (Key2>>30)&3!=0
{
Tmp=BigMul(Crypt,One)
One=BigMod(Tmp,Key1)
}
Key2=Key2<<2;
}
Результат расшифровки в переменной One
Вопрос:
Как можно зашифровать изменненое значение One обратно в 128 байтную последовательность.

G>для расшифровки используются 2 числа одно
G>128 байт, другое 4 байта = 0x00010001

В детали не вдавался, но второе число (17) очень часто применяется как экспонента в открытом ключе RSA, соответственно, первое число — это 1024-битный модуль. Обычно с помощью такой расшифровки проверяют цифровую подпись.
Подробнее про RSA можно почитать тут:
http://en.wikipedia.org/wiki/RSA

Goldy wrote:
>
> Данный алгоритм представлен следующей схемой:

Странная картина. Приведенный код просто возводит Crypt в 4096 степень
по модулю Key1. Соответственно, обратной операций будет нахождения корня
4096 степени, что делается легко, если Key1 простое, или известно
разложение Key1 на множители (так ли это в вашем случае?). Странность в
том, что если это — расшифрование, то зашифрование будет гораздо
сложнее, чем расшифрование.
Вторая проблема заключается в очень большой степени. Дело в том, что в
модульной арифметике у числа может быть до четырех значений квадратного
корня. Соответственно, находя корень четвертой степени, возможно 16
значений, и т.д. То есть для 4096 — будет жуткое количество корней.
Хотя, если рассматривать извлечение корня, как зашифровывание, то
выбрать можно любой из них, первый попавшийся. Но тогда это мало похоже
на шифрование.

На сходных принципах основана криптосистема Рабина
(http://en.wikipedia.org/wiki/Rabin_cryptosystem) — но там зашифрование
осуществляется возведением в квадрат, а расшифрование — поиском
квадратных корней и выбором одного из них используя дополнительные признаки.

Спасибо всем.
Уже выяснил что алгоритм RSA.
Соответственно формула получается X^Key2 mod Key1.
Key2=0x10001=65537 степень.
Теперь вопрос какие есть наиболее быстрые и хорошо распаралеливаемые
программы для факторизации Key1=P*Q?

G>Key2=0x10001=65537 степень.

А, действительно, не 17 а 65537 — я hex с bin перепутал. Кстати, это ещё более распространённая экспонента в RSA-сертификатах.


G>Теперь вопрос какие есть наиболее быстрые и хорошо распаралеливаемые
G>программы для факторизации Key1=P*Q?

ИМХО для 1024 бит это нереально. Вот, к примеру, ссылочка:
http://en.wikipedia.org/wiki/Prime_factorization_algorithm
Пишут, что даже модули порядка 640 бит раскладываются несколько месяцев на кластере машин.
Впрочем, всегда есть шанс угадать

Goldy wrote:
>
> Спасибо всем.
> Уже выяснил что алгоритм RSA.
Так все-таки, это было зашифровывание.

> Соответственно формула получается X^Key2 mod Key1.
> Key2=0x10001=65537 степень.
Со степенью непонятно, или в приведенном алгоритме есть ошибки. С
указанным значением Key2, после первого цикла Count равен 14. Затем, на
первой итерации второго цикла One присваивается значение Crypt, а затем
One двенадцать раз возводится в квадрат. Итого получается 4096 степень.

> Теперь вопрос какие есть наиболее быстрые и хорошо распаралеливаемые
> программы для факторизации Key1=P*Q?

Сложная штука.
http://en.wikipedia.org/wiki/Integer_factorization
http://en.wikipedia.org/wiki/Category:Integer_factorization_algorithms

Алгоритм правильный.
После первой итерации Count=18.
После чего Key1 16 раз возводится в квадрат и в конце умножается на самого себя,
что и дает 65537 итераций.
Посмотрел программы по ссылкам, все они работают с числами не более 100 десятичных знаков,
а тут около 300 будет.
Похоже дело труба или есть еще варианты?

Здравствуйте, Goldy, Вы писали:

G>Алгоритм правильный.
G>После первой итерации Count=18.
G>После чего Key1 16 раз возводится в квадрат и в конце умножается на самого себя,
G>что и дает 65537 итераций.
G>Посмотрел программы по ссылкам, все они работают с числами не более 100 десятичных знаков,
G>а тут около 300 будет.
G>Похоже дело труба или есть еще варианты?
Ну, на wasm ты уже постил...
Модуль я твой на простые атаки попробовал — не поддается, генерен видимо с учетом стандарта, т.е. на халяву расчитывать не приходится.
Факторизаторы, что у меня есть 1024бита не хавают. Для такой битности алгоритмам NFS (MPQS, GNFS) в дефолтном исполнении требуется дофига оперативки, да и времени тоже.
Так что ищи реализации этих алгоритмов, которые могут работать с ограниченной оперативкой, а также в распределенной сети...
Ну или жди и надейся что заявленный новый метод брута RSA на wasm окажется чем то на самом деле работающим. Впрочем я на это не особо полагался бы, потому как заявленные 20 часов на взлом 4096битного ключа это пока из области фантастики.

Goldy wrote:
>
> Алгоритм правильный.
> После первой итерации Count=18.
> После чего Key1 16 раз возводится в квадрат и в конце умножается на
> самого себя,
> что и дает 65537 итераций.

int main()
{
    unsigned long Key2=0x00010001;
    int Count=0;

    while (((Key2>>30) & 3) ==0)
    {
        Count=Count+2;
        Key2=Key2<<2;
    }

    printf("%d\n", Count);
}

Видимо, я чего-то не понимаю. Может он и правильный, но, после
расстановки скобок (без них результат очевидно равен нулю), MSVC 6.0,
2005 и gcc3.4 печатают 14. Причем это понятно — цикл останавливается,
когда Key2 == 0x40004000, что равно 0x00010001 сдвинутому влево на 14
бит. Откуда 18?

> Посмотрел программы по ссылкам, все они работают с числами не более 100
> десятичных знаков,
> а тут около 300 будет.
> Похоже дело труба или есть еще варианты?

ИМХО, труба — даже 1024 бита все еще пока теория, а 640 бит — достаточно
дорогое удовольствие.

Извеняюсь, это моя ошибка при наборе.
Перед вторым циклом должен быть оператор Count=32-Count

Goldy wrote:
>
> Извеняюсь, это моя ошибка при наборе.
> Перед вторым циклом должен быть оператор Count=32-Count

Тогда совсем другое дело. В RSA значение Key2, должно быть взаимно
простым с (p-1)(q-1), где p и q — простые числа, и Key1 = p*q; А
произведение (p-1)(q-1) — всегда четно.
К сожалению, это совсем не облегчает задачи факторизации.