RSA: не генерится открытый ключ :(

Тема в разделе "WASM.A&O", создана пользователем _DEN_, 29 мар 2005.

  1. _DEN_

    _DEN_ DEN

    Публикаций:
    0
    Регистрация:
    8 окт 2003
    Сообщения:
    5.383
    Адрес:
    Йобастан
    Генерю модуль и закрытый ключ. А открытый не могу получить по закрытому. Прога уходит в бесконечный цикл... Может я в формулах что-то напутал? Уточните пожалуста.



    1. Берем простые p и q

    2. Считаем модуль: n = p*q

    3. Считаем закрытый ключ d. Это произвольное число, взаимно простое с (p-1)*(q-1)

    4. Считаем открытый ключ e. Это число, для которого справедливо: (e*d) mod ((p-1)*(q-1)) = 1



    Так вот я, имея p, q и d просто гоню циклом e от двойки и вперед. И прога виснет. Все ли правильно в формулах и где может быть косяк?
     
  2. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    По математике не скажу, но e это экспонента, её вроде бы выбирают, а n = p*q это есть открытый ключ, вместе с экспонентой, я бы проверил на RSA Tool, а ещё лучше в CrypTool. Там есть демонстрация RSA криптосистемы с формулами, картинками и на примере реальных чисел, например:



    Choose two prime numbers p and q. The number N = pq is the public RSA modulus and phi(N) = (p-1)(q-1) is the Euler number. Public key e is coprime to phi(N). The private key d = e^(-1) (mod phi(N)) is calculated from this.
    Код (Text):
    1. Prime number        p = 211
    2. Prime number        q = 227
    3. RSA modulus         N = 47897 (public)
    4. phi(N) = (p-1)(q-1)   = 47460 (secret)
    5. Public key          e = 2^16+1
    6. private key         d = 45953




    Ещё в MSDN можно посмотреть

    http://msdn.microsoft.com/library/default.asp?url=/library/en-us/seccr ypto/security/private_key_blobs.asp

    http://msdn.microsoft.com/library/default.asp?url=/library/en-us/seccr ypto/security/public_key_blobs.asp
     
  3. _DEN_

    _DEN_ DEN

    Публикаций:
    0
    Регистрация:
    8 окт 2003
    Сообщения:
    5.383
    Адрес:
    Йобастан
    bogrus



    Крипт тул качнул, посмотрю... Получается открытый ключ считается через закрытый... Я думал наоборот.
     
  4. RElf

    RElf New Member

    Публикаций:
    0
    Регистрация:
    25 дек 2004
    Сообщения:
    159


    Так не делают. Для больших p,q этот цикл будет практически неосуществим. Закрытый ключ d вычисляют, обращая открытый ключ e по модулю (p-1)*(q-1), используя расширенный алгоритм Евклида.





    И правильно думал. Обычной закрытый ключ вычисляют по открытому. Более того, открытый ключ e часто полагают равным маленькому простому числу с небольшим количеством единиц в двоичной записи, например, 2^4+1=17 или 2^16+1=65537.
     
  5. _DEN_

    _DEN_ DEN

    Публикаций:
    0
    Регистрация:
    8 окт 2003
    Сообщения:
    5.383
    Адрес:
    Йобастан
    RElf

    Так, стоп, что-то я сам уже запутался...



    Я думал что:

    1. Сначала вычесляется закрытый ключ.

    2. Потом зная закрытый ключ, вычисляется открытый.



    Получается что:

    1. Берем открытый ключ, для простоты 2^k+1.

    2. И уже по нему вычисляем закрытый по Евклиду.



    Все правильно?
     
  6. bogrus

    bogrus Active Member

    Публикаций:
    0
    Регистрация:
    24 окт 2003
    Сообщения:
    1.338
    Адрес:
    ukraine
    Выдираю из доки, по-моему тут хорошо понятен порядок действий:



    Алгоритм RSA работает следующим образом: берутся два достаточно больших простых числа p и q и вычисляется их произведение n = p*q; n называется модулем. Затем выбирается число e, удовлетворяющее условию 1< e < (p - 1)*(q - 1) и не имеющее общих делителей кроме 1 (взаимно простое) с числом (p - 1)*(q - 1). Затем вычисляется число d таким образом, что (e*d - 1) делится на (p - 1)*(q - 1).
    Код (Text):
    1. e - открытый (public) показатель
    2. d - частный (private) показатель
    3. (n:e) - открытый (public) ключ
    4. (n:d) - частный (private) ключ
    Делители (факторы) p и q можно либо уничтожить либо сохранить вместе с частным (private) ключом.



    Ещё у Z0MBiE ищи, статья + исходники (часть в аттаче)

    [​IMG] 258036027__zombie_rsa.zip
     
  7. Sergey_R

    Sergey_R Member

    Публикаций:
    0
    Регистрация:
    9 янв 2005
    Сообщения:
    138
    _DEN_



    Напрасно! :о) _Математически_ нет никакой разницы между _закрытым_ и _открытым_ ключами. Это определяется лишь тем, какое из чисел распространяется открыто, а какое остается у пользователя. Ведь сами числа e и d _взаимно_обратны по выбранному модулю, следовательно абсолютно равноправны в отношении "закрытости/открытости" ;о)

    Единственно, как уже сказал RElf, как правило "
    ", но и это не является обязательным требованием.