Здравствуйте. Помогите, пожалуйста, с RSA. Согласно описанию RSA, большое число x (причем x < m) зашифровывается в y так: y = (x ^ e) % n, а расшифровывается обратно так: x = (y ^ d) % n Мне известен открытый ключ (e,n). e небольшое, 16 бит. n большое, 1024 бит. Как можно подобрать для e свои d и n? Т.е. НЕ факторизовать n, чтобы узнать секретный ключ (d,n), а НАЙТИ ДРУГОЙ, который будет работать с таким же e ? Возможно ли это, и если да - то как? Спасибо.
Что значит найти другой? Что значит работает? Советую прочесть что-нибудь по конечным полям. А ответ - нет! Только Факторизовать для дешифрования.
А при чем тут алгоритм создания ключей? Автор топика хочет найти "другое n", которое как бы должно выдавать такой же результат.
извиняюсь, если не ясно выражаюсь. вопрос "подобрать/сгенерить свои d и n для известного e" мне не нужно вскрывать чужие сообщения. не нужно, чтобы результат шифрования и дешифрования "был такой же". мне нужно сгенерить ключ, но чтобы e было то, которе нужно. т.е. никаких чужих сообщений нет. ключ нужен любой, только заданной длинны и с заданным числом e. e небольшое, 16 бит. а в алгоритме генерации ключей e получается из p и q.
а теперь давайте рассуждать: что такое е? e - случайное простое число. нужно решить сравнение d*e = 1 ( (p-1)(q-1)) т.е. необходимо найти обратный к e по некоторому модулю (неизвестного). Т.е. нужно найти d - секретную экспоненту и модуль, но еще вспомнить нужно что n - должно состоять из pq. теперь вопрос что значит создать новый ключ: если вспомнить условия, налагаемые на правила выбора p,q. Т.е. получается что надо найти такое поле у которого функция Эйлера должна давать необходимы нам модуль. (для вычисления n) в итоге по мимо факторизации (p-1)(q-1) нужно перебирать кучу вариантов. Т.е. перебора еще больше чем при факторизации.
еще раз долго подумал... да, Ezrah, вы правы. как и говорит h0t: e - случайное простое число, т.е. его просто случайно выбирают. у меня задано - т.е. я его уже выбрал, и нужно просто подставить его в алгоритм генерации ключей. оно же там не вычисляется, а просто выбирается любое, как я понял из википедии. лишь бы оно было ".. взаимно простое со значением функции φ(n)...". у меня оно простое, а значит и взаимнопростое с другим числом.
как вы собираетесь находить d по неизвестнову модулю? оно взаимно простое и что, это ничего не дает. при неизвестном разложении Вы не найдете функцию Эйлера от n, как результат в каком кольце искать обратный Вы не знаете.
ну, как я понял из описания генерации ключей в русской википедии , я 1 - возьму любые простые числа 1024 бит p и q; 2 - вычислю модуль: n=pq; 3 - найду функцию Эйлера от числа n: φ(n) = (p − 1)(q − 1); 4 - "выбирается целое число e (1 < e < φ(n)), взаимно простое..." - а оно у меня уже есть, и причем простое - значит и взаимнопростое. мне нужно его и использовать; 5 - вычисляю d ... и т.д. далее по алгоритму если я запутался - поправьте, пожалуйста
Да верно, но как Вы вычислять d будите на шаге 5? У вас не известна функция Эйлера т.е. φ(n). Без нее вы не знаете в каком поле находить d!
