В RSA как бы я выбрал e, чтобы в нем было почти 400 цифр? - PullRequest
Новая
       5

В RSA как бы я выбрал e, чтобы в нем было почти 400 цифр?

0 голосов
/ 08 ноября 2018

Да, это по общему признанию для назначения. Я уже сгенерировал phi(n), используя p и q, используя Миллера-Рабина, и теперь мне нужно сгенерировать e. Насколько я понимаю, стандартно использовать 3 или 65537 как e, но я специально должен «найти e - 398-значное число, относительно простое с phi (n)» *

У меня вопрос как? Похоже, что попытка найти факторы огромных чисел - это та самая проблема, которая делает RSA безопасным, а циклический просмотр каждого 400-значного числа и проверка на относительную простоту кажутся явно неправильными, поэтому я чувствую, что что-то неправильно понимаю.

Спасибо за любую помощь

Редактировать:

Код, с которым я сейчас работаю 

def generate_e(r):
    # r is phi(n)
    e = long_string()  # uses a string as a seed
    e = base_10(e)  # converts string to base-10
    e = e % pow(10, 398)  # make len(e) == 398

    # make e odd
    if e % 2 == 0:
        e -= 1

    # iterate over increasing odd numbers until relative prime with phi(n) is found
    while extended_euclid(e, r) != 1:
        e += 2

    return e
...