Обсуждение:RSA

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Пожалуйста, добавляйте новые темы снизу


Источники[править код]

Товарищ, Goga312, ваше массовое расставленные шаблона {{источник?}} мне кажется очень близким к нарушению ВП:НДА, так как многие вещи являются очевидными (например, поскольку RSA был первым алгоритмом цифровой подписи и стал стандартом во многих системах, то очевидно его массовое распространение). Не могли бы Вы по каждому случаю указать источник Ваших сомнений? --A.I. 07:12, 29 ноября 2008 (UTC)[ответить]

Малые значения открытой экспоненты[править код]

Очевидно взаимно просты, так как в противном случае хотя бы один из них был составным, что невозможно в системе RSA.

все числа составные, т.к. являются умножением 2ух простых. Данная атака невозможна, если больше, чем — Эта реплика добавлена с IP 77.125.93.19 (о) 18:55, 16 декабря 2008 (UTC)[ответить]

Рецензия с 28 по 30 ноября 2008 года[править код]

Здесь находятся завершившиеся обсуждения. Просьба не вносить изменений.

В статье описан алгоритм шифрования с открытым ключом RSA. Хочу довести эту статью до статуса хорошей. Интересует любая критика, советы и пожелания.Заранее благодарен. Иванов Сергей 00:01, 28 ноября 2008 (UTC)[ответить]

  • "Опубликованная в ноябре 1976 года статья Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» перевернула представление о криптографических системах и заложила основы криптографии с открытом ключом. Однако разработанный впоследствии алгоритм Диффи-Хеллмана-Меркле, обеспечивая надёжную передачу секретного ключа по незащищенному каналу связи, не давал возможности адресату проверить подлинность сообщения." Немного не удачная формулировка противопоставление двух предложений, перечитал 3 раза пока дошло что имелось ввиду, надо как то переформулировать. goga312 06:31, 29 ноября 2008 (UTC)[ответить]
  • Впринципе статья не плохая, но нигде нет примечаний, я раставлю теги [источник?] где мне кажется надо ссылку на АИ goga312 06:31, 29 ноября 2008 (UTC)[ответить]
  • По поводу первого замечания. Думаю, так будет понятнее:
  • "Опубликованная в ноябре 1976 года статья Уитфилда Диффи и Мартина Хеллмана «Новые направления в криптографии» перевернула представление о криптографических системах, заложив основы криптографии с открытым ключом. Разработанный впоследствии алгоритм Диффи-Хеллмана-Меркле позволял двум сторонам получить общий секретный ключ, используя незащищенный канал связи. Однако этот алгоритм не решал проблему аутентификации. Без дополнительных сpедств, один из пользователей не мог быть увеpен, что он обменялся ключами именно с тем пользователем, котоpый ему был нужен." Иванов Сергей 00:56, 30 ноября 2008 (UTC)[ответить]

Американская компания RSA[править код]

По названию алгоритма в USA была названа компания см. en:RSA (security firm), network security provider, a division of EMC Corporation. Считаю этот факт так же желательно отметить в статье или дать ссылку на другое значение слова.

V lentin 10:39, 21 февраля 2012 (UTC)[ответить]

Скорость работы алгоритма RSA[править код]

Сдается мне, что скорость возведения в степень по модулю пропорциональна количеству бит (логарифму) в степени, и более слабо зависит от количества ненулевых бит. Т.е зависимость такая: O(log2(n) + k*nbits), где nbits - количество ненулевых битов в степени n, 0 <k < 1.

Каждый ноль — возведение в квадрат, каждая единица — умножение. Умножение выполняется в два раза медленнее возведения в квадрат, поэтому в открытой экспоненте должно быть их как можно меньше. Но и от количества нулей тоже скорость зависит. Vlsergey 10:41, 15 марта 2012 (UTC)[ответить]
Фразу про линейную зависимость скорости от числа единиц убрал как неверную. Vlsergey 06:51, 16 марта 2012 (UTC)[ответить]

А разве не так? Для xn:

t = x
for bit in bits(n) from high to low:
   t = t * t
   if bit == 1:
       t += x

Пример:

11 = 1011

x11 = ((x2)2+x)2+x

Итого: имеем возведения в квадрат по количеству битов (логарифму) степени и сложения по количеству единичных битов в нем. Сложение больших чисел гораздо быстрее умножения - вспомним столбик: для сложения 2 чисел из n разрядов надо n операций, а для умножения - n2.

И вот еще. Если мы выбрали e, взаимно простое с phi(n), а потом вычислили из него d, по идее надо d тоже проверить на взаимную простоту с phi(n). — Эта реплика добавлена с IP 178.27.144.11 (о) 03:12, 15 марта 2012 (UTC)[ответить]

Не надо. Из того, что d имеет обратный (равный e) по модулю phi(n), следует, что он взаимно прост с модулем. Maxal 04:39, 15 марта 2012 (UTC)[ответить]
Почему из ed = 1 mod phi(pq), и НОД(е, phi(pq)) = 1 следует НОД(d, phi(pq)) = 1?
Хорошо бы еще написать в статье, зачем нужна простота e и d с phi(n). — Эта реплика добавлена с IP 178.27.144.110 (о)
Иначе бы e и d не были бы обратными друг другу. Обратное по модулю существует только у чисел взаимно простым с модулем. Элементарная теорема: Пусть ab = 1 (mod m), т.е. ab = 1 + mk для некоторого k. Допустим у a или b есть общий c m делитель d > 1. Возьмем обе части равенства по модулю d. Слева нуль, справа 1, противоречие, QED. -- X7q 02:04, 16 марта 2012 (UTC)[ответить]
Ну тогда стоит указать в статье, что если одно число взаимно простое, то мультипликативно обратное к нему тоже взаимно простое и его можно не проверять.
Зачем вообще усложнять алгоритм генерации ключей такими подробностями? Это можно описать в доказательстве корректности, если какие-нибудь АИ обращают внимание на подобные детали. Vlsergey 08:39, 16 марта 2012 (UTC)[ответить]
Ну я не знаю, куда именно, но написать это однозначно стоит. — Эта реплика добавлена с IP 178.27.144.110 (о)
Там написано, что e должно быть взаимно простое с модулем phi(n) - хорошо бы обьяснить, почему и почему не надо проверять это для d. — Эта реплика добавлена с IP 178.27.144.110 (о)
Я не понимаю, почему это "должно быть написано" или почему "написать это однозначно стоит". В соответствии с ВП:ВЕС статья должна отражать то, что изложено во вторичных источниках. В каком источнике отражён тот факт, что d должно быть взаимно просто с e phi(n)? Vlsergey 10:42, 16 марта 2012 (UTC)[ответить]
Я где-то говорил, что d должно быть взаимно простым с e? Оно будет взаимно простым с phi(n). Доказательство парой строчек выше :) — Эта реплика добавлена с IP 178.27.144.110 (о)
Замечательно, спасибо за замеченную описку. А теперь, пожалуйста, найдите всё-таки вторичные авторитетные источники. Vlsergey 10:57, 16 марта 2012 (UTC)[ответить]
Прошу прощения за крамольный вопрос, Вы понимаете вообще предмет обсуждения? Почему e должно быть взаимно простым, а d нет? Это можно доказать и без АИ, просто влом искать - я в дискретке не настолько силен, чтобы помнить это наизусть. Думаю, его найдет любой, кто знает ее лучше.
Я прекрасно понимаю предмет обсуждения. Более того, я его преподаю в ВУЗе. Но это не имеет отношения к дискуссии (см. также ВП:ВСЕ). Я согласен с тем фактом, что d должно быть взаимно простым. Но я не согласен с тем фактом, что об этом нужно писать в статье и забивать читателю мозги. Точно также как не нужно указывать такие факты, что e выбирается меньше n, а p, q и n должны быть нечётными (хотя всё это несложно доказать). Правило, которое регулирует необходимость указания тех или иных фактов в статье -- ВП:ВЕС -- требует, чтобы эти факты освещались в авторитетных источниках. Vlsergey 11:13, 16 марта 2012 (UTC)[ответить]
Так если у Вас это не вызывает сомнений, зачем вы в меня тычете необходимостью AИ? Это уже похоже на придирки. — Эта реплика добавлена с IP 178.27.144.110 (о)
phi(x) < x следует из определения функции Эйлера. Неделимость на 2 следует из простоты, это может понять и среднеклассник. А вот у читателя вполне может возникнуть вопрос, почему e должно быть взаимно простым с phi(n), а d на взаимную простоту не проверяется? — Эта реплика добавлена с IP 178.27.144.110 (о)
Ещё раз для тех, кто не прочитал - не всё, что истинно, должно быть в статье. Википедия на F.A.Q., Википедия не собрание всех возможных фактов и мнений. В статье должно быть не то, что может быть интересно кому-то, а то, что описано во вторичных авторитетных источниках. Ищите такие источники, приводите в обсуждении. Потом уже вставляете в статью. Vlsergey 11:30, 16 марта 2012 (UTC)[ответить]
А кто, простите, решает, что должно быть, а что нет? Насколько я знаю, АИ нужны для подтверждения правильности. Она у Вас сомнений не вызывает? — Эта реплика добавлена с IP 178.27.144.110 (о)
Как я уже написал ниже, АИ нужны не только для подтверждения. См. ВП:ЗФ, ВП:ВЕС. Vlsergey 11:36, 16 марта 2012 (UTC)[ответить]

P.S.: А в формуле быстрого возведения в степень плюсов нет. Вместо сложения там умножение. Vlsergey 11:13, 16 марта 2012 (UTC)[ответить]

Получается, мой алгоритм лучше? :) — Эта реплика добавлена с IP 178.27.144.110 (о)
Нет, он с ошибкой. Vlsergey 11:35, 16 марта 2012 (UTC)[ответить]
Да, действительно. А почему умножение занимает больше возведения в квадрат? — Эта реплика добавлена с IP 178.27.144.110 (о)

По поводу выбора d или e[править код]

Нельзя выбирать d и вычислять e на основании выбранного d, так как выбор подразумевает ограничение вариантов (если, конечно, речь опять не идёт о случайной генерации). Ограничение вариантов приводит к уменьшению криптостойкости. Vlsergey 06:50, 16 марта 2012 (UTC)[ответить]

Под выбором имеется случайное число, т.к. способ выбора не указывается. e можно выбирать и неслучайно. — Эта реплика добавлена с IP 178.27.144.110 (о)
Лишний вызов подряд генератора случайных чисел уменьшает криптостойкость алгоритма. Возникает (хотя и не тривиальная) зависимость между случайно выбранными p, q и d. Чем меньше вызовов генератора, тем лучше. Vlsergey 08:42, 16 марта 2012 (UTC)[ответить]
Это уже кагбе детали реализации. И нет, необязательно.
Если говорить о возможности замены выбора e на случайную генерацию d, то об этом можно написать, если какой-нибудь авторитетный источник упоминает подобный вариант. Vlsergey 08:43, 16 марта 2012 (UTC)[ответить]
А самому предположить такое нельзя? Что-то говорит, что криптостойкость будет хуже, если взять случайное и генерировать из него , а не наоборот? Имхо выбирают чисто по практическим соображениям. — Эта реплика добавлена с IP 178.27.144.110 (о)
Самому предположить такое нельзя - Википедия не место для публикации результатов самостоятельных исследований.
При подписывании и меняются местами - шифруется закрытым ключом, расшифровывается открытым. Стойкость от этого же не падает? — Эта реплика добавлена с IP 178.27.144.110 (о)
Давайте прекратим спорить о формулах и начнём с более простого -- найдите авторитетный источник, в котором упоминается подобный вариант замены выбора e на генерацию d. Vlsergey 10:40, 16 марта 2012 (UTC)[ответить]
Источник искать влом, но судя по операции подписания, стойкость от этого не падает. Если для вас это так принципиально важно, моэет быть когда-нибудь найду, может кто-то другой найдет. Пока их у меня нет. — Эта реплика добавлена с IP 178.27.144.110 (о)
Значит, пока источника нет, в статье этого не будет. Vlsergey 11:32, 16 марта 2012 (UTC)[ответить]

Может, хватит отменять мои правки? Чем это не угодило? Я расписал, почему phi(n) такое. Такое впечатление, что вы хотите закрыть страницу от изменений, но то ли прав не хватает, то ли еще что-то. — Эта реплика добавлена с IP 178.27.144.110 (о)

  • Потому что верно в частности, но неверно в общем случае. По Вашей формуле создаётся ощущение, что достаточно расписать множители, после чего перемножить их значения формулы Эйлера, что неверно. Подобная форма записи "объяснения" не используется в тех источниках, что у меня под рукой. У Вас другие источники? Приведите их тут. Vlsergey 10:40, 16 марта 2012 (UTC)[ответить]
    • Ээ что? Вторая формула сверху. Для простых p и q формула верна всегда. — Эта реплика добавлена с IP 178.27.144.110 (о)
      • Для простых верна, для остальных нет. Давая подобную запись вместо ссылки на статью мы вводим читателя в заблуждение. Повторяю свою просьбу по приведению источников, в которых формула Эйлера в процедуре генерации ключа для RSA записывается в данном виде. Vlsergey 11:16, 16 марта 2012 (UTC)[ответить]
        • О е. Это не статья про функию Эйлера, здесь она применяется для конкретного случая. И для него эта запись верна.
        • Правильность сомнений не вызывает? АИ найдете сами, или они нужны для чего-то еще, кроме подтверждение правильности? — Эта реплика добавлена с IP 178.27.144.110 (о)
          • АИ также нужны для того, чтобы показать необходимость наличия того или иного факта в статье. См. ВП:ЗФ, ВП:ВЕС. Vlsergey 11:32, 16 марта 2012 (UTC)[ответить]
            • Слуште, ну так до маразма можно докатиться, искать АИ, что 2*2 = 4. И кстати, где АИ на то, что написано в статье? Требую их показать :) — Эта реплика добавлена с IP 178.27.144.110 (о)
              • Насколько я знаю, в обсуждаемой статье не приведено факта, что "2*2 = 4". Поэтому АИ на него искать не нужно. В статьях об умножении таким АИ может выступить, например, учебник. Vlsergey 11:40, 16 марта 2012 (UTC)[ответить]
                • То есть, нужно копипастить учебник, но только не полностью, иначе нарушите лицензионное соглашение? И я все еще хочу увидеть АИ на все написанное в статье. — Эта реплика добавлена с IP 178.27.144.110 (о)
                  • 1. Не копипастить, но пересказывать, и не только учебник, но и ещё 10-20-100 источников. 2. И какие факты, по вашему мнению, приведены в статье, но отсутствуют в тех АИ, что в ней перечислены? Vlsergey 12:07, 16 марта 2012 (UTC)[ответить]
                    • Нет, если Вам нужны АИ на все, что я пытаюсь добавить в статью, то Вы приведите АИ на все, что в ней написано. — Эта реплика добавлена с IP 178.27.144.110 (о)
                      • 1. С моей точки зрения, большая часть того, что в статье описано, в АИ присутствует. Если Вы считаете, что это не так, и что что-то не описано в АИ, укажите конкретно. То есть я считаю Ваше требование («приведите АИ на все, что в ней написано») с моей стороны выполненным в той мере, в которой мне известно. 2. Принцип редактирования Википедии не подразумевает какие-либо «торги» по содержимому статьи, но обсуждение новых изменений. Подробнее см. ВП:Консенсус. Vlsergey 12:15, 16 марта 2012 (UTC)[ответить]
                        • А к старым записям эти требования применялись, или хватило того, что Вам показалось, что они не нужны? А теперь перестало казаться? По-моему, у Вас двойные стандарты. — Эта реплика добавлена с IP 178.27.144.110 (о)

RSA скомпрометирован[править код]

Думаю, стоит добавить описание этого в статью 93.116.216.145 12:06, 23 декабря 2013 (UTC)[ответить]

В Примере при расшифровке вычисляют d по mod n, а не по mod phi(n). Исправьте, если я прав.[править код]

Знак равенства.[править код]

В примере в поле "вычислить секретную экспоненту" употреблен знак равенства. Это неверно, создается впечатление, что d - это остаток от деления 1/e на модуль. На самом деле, там речь идет о другом отношении, вот в англо-вики об этом. Если я не прав, поправьте. Иначе, замените изображение. У меня сейчас нет технической возможности, пишу с кофемолки) Mortelmischung 20:22, 19 июля 2015 (UTC)[ответить]

Рандеву, конспиративная встреча, сверим часы[править код]

Есть 3 разных простых числа. Первый участник рандеву на котором нужно узнать участника, знает 1 своё простое число. Второй участник знает своё 1. Оба знают произведение этих чисел, всех 3-ех. Первый называет своё число. Второй делит произведение на это число и если произошло деление без остатка то проверка дала положительный ответ. Второй называет своё число и т.д. Известная задача, мне попалась без ответа.95.78.40.36 04:42, 2 марта 2018 (UTC) Виктор Минеев[ответить]

Аддитивная (не шифрующая) цифровая подпись[править код]

Выбираем e и d следующие из уравнения e + d = phi(n) + 1. Первый участник вычисляет и посылает подпись s = (m ^ e) mod n. Второму доступно m и он вычисляет s' = (s * ((m ^ d) mod n)) mod n. Сравнив m и s' если равно то подпись верна. Зашифровать что-нибудь при помощи чисел {d,n} не представляю возможным.95.78.24.29 21:22, 27 января 2018 (UTC) Виктор Минеев 95.78.52.58 08:19, 28 января 2018 (UTC) Виктор Минеев[ответить]

А как выбирать числа?[править код]

Просто выбрать два случайных больших числа не проблема. 2048 раз подбрось монетку, или 616 раз дайс D10, или 416 раз прокрути рулетку и готово. Но вероятность простоты результата мала. Так надо ещё проверить число на простоту. Длительность проверки «в лоб» многократно превышает не только время существования вселенной, но даже некоторые оценки времени жизни протона, исключая возможность доверять результатам такой примитивной проверки. А после проверки придётся ещё и перебросить дайсы. И сколько времени будете бросать дайсы, пока получите даже одно большое простое число? Выбирать по случайному индексу из таблицы? Если бы такая таблица обозримых размеров существовала, то противник мог бы её перебрать. 31.135.41.175 10:58, 3 сентября 2019 (UTC)[ответить]

  • Существует простой алгоритм генерации заведомо простых очень больших чисел, названия сейчас не вспомню. Возможно, это связано с числами Мерсенна. MBH 12:48, 4 июня 2020 (UTC)[ответить]
    • Вы математик? Выйдя из горящего номера и увидев огнетушитель, просто скажите: «Решение существует» и спокойно вернётесь в номер? Как генерировать? Вот в чём вопрос. А не существует ли алгоритм. 31.135.43.252 14:05, 4 июня 2020 (UTC)[ответить]

Чем удостоверяется подлинность?[править код]

Предположим, некто третий сочинит полный бред b, расшифрует его открытым ключом Алисы, получив столь же бредовое pb, а потом передаст Бобу pb как прообраз, а b – как подпись. Боб расшифрует b ещё раз, сравнит с «прообразом» и убедится, что Алиса сошла с ума. Если Алиса и Боб заведомо разумны, то может и можно полагаться на читабельность сообщения. А если подпись юзается для аутентификации в программе, например, в сервере удалённой оболочки? 31.135.41.175 11:31, 3 сентября 2019 (UTC)[ответить]

Вычисление секретной экспоненты d[править код]

Стесняюсь спросить, откуда взялась данная формула?

Её будто вывели из этой:

Но разве можно вот так переносить переменные при сравнении по модулю?)
Проверка:
(6111579 - (3^-1)) % 9167368 = ~6111578.67

(6111579 * 3 - 1) % 9167368 = 0
31.131.65.147 22:44, 10 сентября 2021 (UTC)[ответить]

  • Тут означает обратный элемент в группе по модулю , а не обычное деление . Я переписал текст, чтобы таких вопросов не возникало. — Алексей Копылов 23:29, 10 сентября 2021 (UTC)[ответить]