Не совсем понятно как генерировать секретную компоненту (d) в RSA ! Берем пример из википедии Выбираем простые числа p = 3557 q = 2579 n = p*q = 3557*2579 = 9173503 Вычисляем функцию Эйлера. El = (p-1)*(q-1) = (3557-1)*(2579-1) = 3556*2578 = 9167368 Выбираем открытую экспоненту e=3 И теперь самая мякотка ...нам нужно сгенерить секретный ключ d. Пишут про мульпликативно обратное к числу e по модулю El (ранее полученного Эйлера) и алгоритм Евклида. Для меня это вообще магические заклинания. Смотрим что пишет Вики. d = (k*El+1)/e = (2*9167368+1)/3 = 6111579 Непонятно что такое k и откуда она взялась ? Почему она равна 2.
По-моему реализацию на языке программирования изучать проще, чем закорючки математиков. Код (Text): // Find the Greatest Common Divisor between two numbers int gcd(int num1, int num2){ int temp; while(num2 > 0){ temp = num1 % num2; num1 = num2; num2 = temp; } return num1; } // d = (1/e) mod n int mod_inverse(int u, int v) { int inv, u1, u3, v1, v3, t1, t3, q; int iter; /* Step X1. Initialise */ u1 = 1; u3 = u; v1 = 0; v3 = v; /* Remember odd/even iterations */ iter = 1; /* Step X2. Loop while v3 != 0 */ while (v3 != 0) { /* Step X3. Divide and "Subtract" */ q = u3 / v3; t3 = u3 % v3; t1 = u1 + q * v1; /* Swap */ u1 = v1; v1 = t1; u3 = v3; v3 = t3; iter = -iter; } /* Make sure u3 = gcd(u,v) == 1 */ if (u3 != 1) return 0; /* Error: No inverse exists */ /* Ensure a positive result */ if (iter < 0) inv = v - u1; else inv = u1; return inv; }
