Великолепная мини лекция. Просто офигительная. Комментарии в процессе - то, что надо. Для начинающих - то, что нужно. небольшая ремарка: 9:50 симметричное -> асимметричное: Именно асимметричное шифрование и было придумано для безопасного распределения ключей как надо.
Народ, вопрос ко всем. Кто нибудь слышал о числах типа 1000...0001, то есть по краям единицы а в середине только нули, что среди них нет простых кроме 101? Или есть там простые? Кто что слышал?
Вопрос: Есть ли такие составные числа с которыми алгоритм RSA работает корректно? Или нужны только простые? Меня не парит безопасность, в принципе можно ли зашифровать алгоритмом RSA, а затем правильно расшифровать если p и q составные или хоть одно составное? Если нет таких чисел и для корректной работы RSA нужны только простые p и q то возникает другой вопрос: А нафига тогда все эти тесты на простоту? Не проще ли взять два числа и если на них работает RSA то значит они простые? А если есть такие составные p и q на которых алгоритм работает корректно то дайте пример таких чисел 🙂
На первый взгляд можно взять любой пример с игрушечной реализацией RSA и поменять p и q, например, с 3 и 7 на 2 и 8, иногда даже получится что-то правдоподобное: www.askpython.com/python/examples/rsa-algorithm-in-python Но что RSA, что Диффи-Хеллман основаны на функции Эйлера, а fi(p) = p-1 справедливо только для простых чисел, как и fi(p*q) = fi(p)*fi(q) только для взаимно простых p и q. Иначе использование (p-1)*(q-1) на третьем шаге теряет всякий смысл. Так что нет, RSA не будет корректно работать с составными числами. Ну а использование RSA для проверки простоты гораздо дороже любого из традиционных методов.
RSA будет работать корректно с любыми числами. Но нужно будет знать их разложение на простые множители, чтобы вычислить φ(n). Например, если p и q составные и каждое из них раскладывается в произведение двух простых: p1·p2 и q1·q2, то φ(n)= (p1-1)(p2-1)(q1-1)(q2-1). Единственное ограничение, это если в разложении n какой-то простой множитель будет в степени выше 1. Тогда нельзя будет шифровать числа кратные этому множителю.
Великолепная мини лекция. Просто офигительная.
Комментарии в процессе - то, что надо.
Для начинающих - то, что нужно.
небольшая ремарка:
9:50 симметричное -> асимметричное: Именно асимметричное шифрование и было придумано для безопасного распределения ключей как надо.
7:29 про "гигантскую" награду улыбнули )
Это, кстати, отличный пример того, на что способен голый энтузиазм.
Вопрос: Что такое большие числа с точки зрения асимметричного шифрования?
Рекомендованная с 2015 года минимальная длина ключа RSA - 2048 бита, 2^2048 - 617-значное десятичное число.
Народ, вопрос ко всем. Кто нибудь слышал о числах типа 1000...0001, то есть по краям единицы а в середине только нули, что среди них нет простых кроме 101? Или есть там простые? Кто что слышал?
Вопрос: Есть ли такие составные числа с которыми алгоритм RSA работает корректно? Или нужны только простые? Меня не парит безопасность, в принципе можно ли зашифровать алгоритмом RSA, а затем правильно расшифровать если p и q составные или хоть одно составное? Если нет таких чисел и для корректной работы RSA нужны только простые p и q то возникает другой вопрос: А нафига тогда все эти тесты на простоту? Не проще ли взять два числа и если на них работает RSA то значит они простые? А если есть такие составные p и q на которых алгоритм работает корректно то дайте пример таких чисел 🙂
На первый взгляд можно взять любой пример с игрушечной реализацией RSA и поменять p и q, например, с 3 и 7 на 2 и 8, иногда даже получится что-то правдоподобное:
www.askpython.com/python/examples/rsa-algorithm-in-python
Но что RSA, что Диффи-Хеллман основаны на функции Эйлера, а fi(p) = p-1 справедливо только для простых чисел, как и fi(p*q) = fi(p)*fi(q) только для взаимно простых p и q. Иначе использование (p-1)*(q-1) на третьем шаге теряет всякий смысл. Так что нет, RSA не будет корректно работать с составными числами.
Ну а использование RSA для проверки простоты гораздо дороже любого из традиционных методов.
RSA будет работать корректно с любыми числами. Но нужно будет знать их разложение на простые множители, чтобы вычислить φ(n). Например, если p и q составные и каждое из них раскладывается в произведение двух простых: p1·p2 и q1·q2, то φ(n)= (p1-1)(p2-1)(q1-1)(q2-1). Единственное ограничение, это если в разложении n какой-то простой множитель будет в степени выше 1. Тогда нельзя будет шифровать числа кратные этому множителю.