1 Тема от im2002 (изменено: im2002, 2013-04-20 21:18:55)

  • im2002
  • Участник
  • Неактивен

Тема: JS: Алгоритм RSA

никак не получается написать написать функцию для определения d по известным e и f(n). в инете также не могу найти на js. т.е. что-то типа:

function define_D(e, f)              // объявление ф-ии
   {
   .........
   алгоритм вычисления
   .........
   return d;
    }

define_D(7927, 215836540);     // вызов функции
WScript.Echo(d);                        //  отображение результата

Здесь произведение d*7927 при делении на 215836540 даёт такой же остаток, что и 1 при делении на 215836540.
т.е. d*7927 = 1 mod(215836540).

Можно также переформулировать задачу таким образом:
d*7927 = k*215836540 + 1.
Надо решить это уравнение найдя такое НАТУРАЛЬНОЕ значение d < 215836540, что для некоторого НАТУРАЛЬНОГО k  вышеприведённое равенство справедливо.

2 Ответ от im2002

  • im2002
  • Участник
  • Неактивен

Re: JS: Алгоритм RSA

function input_Z(x, y)
    {
    i = 0, d1 = 0, d = 0; 
    Zel = new Array();                    // массив неопределённой длины для целых
    Ost = new Array();                    // массив неопределённой длины для остатков от деления
    k = new Array();
    en = y;                            // запоминаем начальные значения d и f(n)
    fn = x;
    define_D(x, y);
    return WScript.Echo(d);
    }
                    

function define_D(f, e)                        // ОБЪЯВЛЕНИЕ Ф-ЦИИ
    {        
    
    ost = f - parseInt(f/e)*e;                // остаток от деления
    Ost[i] = ost;
    Zel[i] = parseInt(f/e);
    
    
    if((ost == 1) && (parseFloat(i/2) != parseInt(i/2)) && i != 0)
        {
        for(j = (Zel.length - 1), k[j+1] = 1 ; j > 0; j--) 
            {
            k[j] = Zel[j]*k[j+1] + (Ost[j]*k[j+1] + Math.pow(-1, j))/Ost[j-1];
            d1 = Zel[0]*k[1] + (Ost[0]*k[1]+1)/en;
            ost_1 = (parseFloat(d1*en/fn) - parseInt(d1*en/fn)).toFixed(11);            // для проверки
            ost_2 = (1/fn).toFixed(11);
            }
        }
    else
        {
        if((ost == 1) && (parseFloat(i/2) == parseInt(i/2)) && i != 0)
            {
            for(j = (Zel.length - 1), k[j+1] = Ost[j-1] - 1 ; j > 0; j--) 
                {
                k[j] = Zel[j]*k[j+1] + (Ost[j]*k[j+1] + Math.pow(-1, j))/Ost[j-1];
                d1 = Zel[0]*k[1] + (Ost[0]*k[1]+1)/en;
                ost_1 = (parseFloat(d1*en/fn) - parseInt(d1*en/fn)).toFixed(11);        // для проверки
                ost_2 = (1/fn).toFixed(11);
                }
            }
        else
            {
            if((ost == 1) && (parseFloat(i/2) == parseInt(i/2)) && i == 0)
                {
                d1 = (e - 1)*parseInt(f/e) + 1;
                ost_1 = (parseFloat(d1*en/fn) - parseInt(d1*en/fn)).toFixed(11);        // для проверки
                ost_2 = (1/fn).toFixed(11);
                }
            else
                {
                f = e;
                e = Ost[i];
                i++;
                define_D(f, e)
                }
            }    
        }

    d = d1 + "\n" + ost_1 + "\n" + ost_2;
    return d;
    }

input_Z(215836540, 7927);

input_Z(62869032, 7993);

input_Z(9167368, 3);

input_Z(96, 5);

Вроде работает, но наверное можно "подсократить" его.

3 Ответ от Rumata

  • Rumata
  • Разработчик
  • Неактивен

Re: JS: Алгоритм RSA

Замечания общего характера
1. объявление переменных обязательно оператором var


// переменная объявлена, но неинициализирована
var a;
// переменная объявлена и инициализирована
var b = 10;

2. не используйте конструктор для инициализации массива. Массивы инициализируйте так


// пустой массив
var arr = [];
// массив из трех эдементов
var arr2 = [1, 2, 3];

3. parseInt это функция для перевода СТРОКИ в ЧИСЛО. В Вашем случае она используется не по назначению.
4. получите остаток от деления


var a = 7;
var b = 3;
var c = a % b; // с == 1

5. Если комментируете код, то давайте осмысленные комментарии. В данном случае совершенно не ясно, что является чем. В идеале хорошо составленный алгоритм не требует комментариев. 


    en = y;                            // запоминаем начальные значения d и f(n)
    fn = x;

И напоследок.

d*7927 = k*215836540 + 1.
Надо решить это уравнение найдя такое НАТУРАЛЬНОЕ значение d < 215836540, что для некоторого НАТУРАЛЬНОГО k  вышеприведённое равенство справедливо.

Это не является решением?

d = (k * 215836540  + 1) / 7927
( 2 * b ) || ! ( 2 * b )

4 Ответ от im2002

  • im2002
  • Участник
  • Неактивен

Re: JS: Алгоритм RSA

Rumata пишет:

Замечания общего характера

И напоследок.

d*7927 = k*215836540 + 1.
Надо решить это уравнение найдя такое НАТУРАЛЬНОЕ значение d < 215836540, что для некоторого НАТУРАЛЬНОГО k  вышеприведённое равенство справедливо.

Это не является решением?

d = (k * 215836540  + 1) / 7927

Само собой является, если знать натуральное k, которое даст в приведённой выше формуле натуральное d. Как k найти-то?! Подбором? при k = 1  d = (1* 215836540  + 1) / 7927 -> НЕ Целое, и так можно "до бесконечности" подбирать... а если числа скажем порядка 1024 бит? В остальном согласен с замечаниями.

5 Ответ от Rumata

  • Rumata
  • Разработчик
  • Неактивен

Re: JS: Алгоритм RSA

До бесконечности не получится. Ряд натуральных чисел ограничен 32 битами. Максимальное доступное число 0xFFFFFFFF, или 4294967295. Дальше - вещественные числа.

( 2 * b ) || ! ( 2 * b )

6 Ответ от im2002

  • im2002
  • Участник
  • Неактивен

Re: JS: Алгоритм RSA

Rumata пишет:

До бесконечности не получится. Ряд натуральных чисел ограничен 32 битами. Максимальное доступное число 0xFFFFFFFF, или 4294967295. Дальше - вещественные числа.

Не знал про такое! Тогда пусть будет целые и положительные, сути это не меняет. решение таких уравнений это только малая часть задачи в алгоритме RSA, если читаешь какой-либо материал по теме, там даже непонятно как они находят эти "приватные" ключи, поэтому вопрос заинтересовал, научился находить "руками", потом попытался на JS, доведу "до ума" потом попробую экспериментировать непосредственно с шифрованием...

7 Ответ от JSmаn

  • JSmаn
  • Разработчик
  • Неактивен

Re: JS: Алгоритм RSA

Вот пример реализации RSA на JS.

8 Ответ от im2002

  • im2002
  • Участник
  • Неактивен

Re: JS: Алгоритм RSA

JSman пишет:

Вот пример реализации RSA на JS.

Спасибо