Вопрос по RSA

Тема в разделе "WASM.CRYPTO", создана пользователем novice2, 22 янв 2012.

  1. novice2

    novice2 New Member

    Публикаций:
    0
    Регистрация:
    27 дек 2005
    Сообщения:
    14
    Здравствуйте.
    Помогите, пожалуйста, с 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 ?

    Возможно ли это, и если да - то как?

    Спасибо.
     
  2. h0t

    h0t Member

    Публикаций:
    0
    Регистрация:
    3 апр 2011
    Сообщения:
    735
    Что значит найти другой? Что значит работает? Советую прочесть что-нибудь по конечным полям.

    А ответ - нет! Только Факторизовать для дешифрования.
     
  3. Ezrah

    Ezrah Member

    Публикаций:
    0
    Регистрация:
    22 мар 2011
    Сообщения:
    413
    На той же википедии описан алгоритм создания ключей.
     
  4. h0t

    h0t Member

    Публикаций:
    0
    Регистрация:
    3 апр 2011
    Сообщения:
    735
    А при чем тут алгоритм создания ключей? Автор топика хочет найти "другое n", которое как бы должно выдавать такой же результат.
     
  5. TrashGen

    TrashGen ТрещГен

    Публикаций:
    0
    Регистрация:
    15 мар 2011
    Сообщения:
    422
    Адрес:
    подполье
    Найдите другую тройку, которая при вычитании из пятерки даст в результате двойку.
     
  6. Ezrah

    Ezrah Member

    Публикаций:
    0
    Регистрация:
    22 мар 2011
    Сообщения:
    413
    h0t
    Как я понял, он хочет
    , а не n для e и d.
     
  7. novice2

    novice2 New Member

    Публикаций:
    0
    Регистрация:
    27 дек 2005
    Сообщения:
    14
    извиняюсь, если не ясно выражаюсь.
    вопрос "подобрать/сгенерить свои d и n для известного e"

    мне не нужно вскрывать чужие сообщения.
    не нужно, чтобы результат шифрования и дешифрования "был такой же".

    мне нужно сгенерить ключ, но чтобы e было то, которе нужно.

    т.е. никаких чужих сообщений нет. ключ нужен любой, только заданной длинны и с заданным числом e.
    e небольшое, 16 бит.

    а в алгоритме генерации ключей e получается из p и q.
     
  8. h0t

    h0t Member

    Публикаций:
    0
    Регистрация:
    3 апр 2011
    Сообщения:
    735
    а теперь давайте рассуждать:
    что такое е?
    e - случайное простое число.
    нужно решить сравнение
    d*e = 1 ( (p-1)(q-1))
    т.е. необходимо найти обратный к e по некоторому модулю (неизвестного).
    Т.е. нужно найти d - секретную экспоненту и модуль, но еще вспомнить нужно что n - должно состоять из pq.
    теперь вопрос что значит создать новый ключ: если вспомнить условия, налагаемые на правила выбора p,q.

    Т.е. получается что надо найти такое поле у которого функция Эйлера должна давать необходимы нам модуль. (для вычисления n) в итоге по мимо факторизации (p-1)(q-1) нужно перебирать кучу вариантов. Т.е. перебора еще больше чем при факторизации.
     
  9. kejcerfcrv

    kejcerfcrv New Member

    Публикаций:
    0
    Регистрация:
    16 дек 2011
    Сообщения:
    320
    Упс.. не в ту тему написал.)
     
  10. novice2

    novice2 New Member

    Публикаций:
    0
    Регистрация:
    27 дек 2005
    Сообщения:
    14
    еще раз долго подумал...
    да, Ezrah, вы правы.
    как и говорит h0t: e - случайное простое число,
    т.е. его просто случайно выбирают.
    у меня задано - т.е. я его уже выбрал, и нужно просто подставить его в алгоритм генерации ключей.

    оно же там не вычисляется, а просто выбирается любое, как я понял из википедии.
    лишь бы оно было ".. взаимно простое со значением функции φ(n)...".
    у меня оно простое, а значит и взаимнопростое с другим числом.
     
  11. h0t

    h0t Member

    Публикаций:
    0
    Регистрация:
    3 апр 2011
    Сообщения:
    735
    как вы собираетесь находить d по неизвестнову модулю? оно взаимно простое и что, это ничего не дает. при неизвестном разложении Вы не найдете функцию Эйлера от n, как результат в каком кольце искать обратный Вы не знаете.
     
  12. novice2

    novice2 New Member

    Публикаций:
    0
    Регистрация:
    27 дек 2005
    Сообщения:
    14
    ну, как я понял из описания генерации ключей в русской википедии , я
    1 - возьму любые простые числа 1024 бит p и q;
    2 - вычислю модуль: n=pq;
    3 - найду функцию Эйлера от числа n: φ(n) = (p − 1)(q − 1);
    4 - "выбирается целое число e (1 < e < φ(n)), взаимно простое..." - а оно у меня уже есть, и причем простое - значит и взаимнопростое. мне нужно его и использовать;
    5 - вычисляю d ... и т.д. далее по алгоритму

    если я запутался - поправьте, пожалуйста
     
  13. h0t

    h0t Member

    Публикаций:
    0
    Регистрация:
    3 апр 2011
    Сообщения:
    735
    Да верно, но как Вы вычислять d будите на шаге 5? У вас не известна функция Эйлера т.е. φ(n).
    Без нее вы не знаете в каком поле находить d!