Вот и новая эра, почитачей!

[AndyM 0]

RSA, по-крайней мере малобитный, который все используют, давно не орешек

 

Я видел очень мало людей, использующих RSA 512. 2048, который рекомендуется использовать, взломать пока unreal.

[Alexandro 0]

Я видел очень мало людей, использующих RSA 512. 2048, который рекомендуется использовать, взломать пока unreal.

 

Да... задача разложения на множители для 2048-битных чисел пока требует пару десятков тысяч лет...

Учитывая, что этими множителями являются два 1024-битных простых числа...

[KOTRPA 0]

Кстати, девайс-то (тот который квантовый), если вы заметили, был смонтирован можно сказать по-соседству со мной -- в Burnaby.

[DigitalDreamer 0]

Да... задача разложения на множители для 2048-битных чисел пока требует пару десятков тысяч лет...

Это смотря на чем считать... Скорее всего потребуется намноооого больше времени (на современном уровне развития).

Учитывая, что этими множителями являются два 1024-битных простых числа...

Поправьте меня, если я ошибаюсь, но по-моему, это совсем не обязательно.

[Alexandro 0]

Это смотря на чем считать... Скорее всего потребуется намноооого больше времени (на современном уровне развития).

Разумеется, подразумевается, что считать будет не один компьютер, а на несколько порядков большее число, путем распределения вычислительных мощностей...

 

Поправьте меня, если я ошибаюсь, но по-моему, это совсем не обязательно.

Что не обязательно ? Чтобы два числа были простыми, или чтобы они были 1024-битными, или для взлома RSA не нужно разложение на множители ?

 

Алгоритм RSA стоит у истоков асимметричной криптографии. Он был предложен тремя исседователями-математиками Рональдом Ривестом (R.Rivest) , Ади Шамиром (A.Shamir) и Леонардом Адльманом (L.Adleman) в 1977-78 годах.

 

Первым этапом любого асимметричного алгоритма является создание пары ключей : открытого и закрытого и распространение открытого ключа "по всему миру". Для алгоритма RSA этап создания ключей состоит из следующих операций :

 

1. Выбираются два простых (!) числа p и q

2. Вычисляется их произведение n(=p*q)

3. Выбирается произвольное число e (e<n), такое, что НОД(e,(p-1)(q-1))=1, то есть e должно быть взаимно простым с числом (p-1)(q-1).

4. Методом Евклида решается в целых числах (!) уравнение e*d+(p-1)(q-1)*y=1. Здесь неизвестными являются переменные d и y – метод Евклида как раз и находит множество пар (d,y), каждая из которых является решением уравнения в целых числах.

5. Два числа (e,n) – публикуются как открытый ключ.

6. Число d хранится в строжайшем секрете – это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары чисел (e,n).

 

 

Число n - известно. Задачка смешная - разложить это число на множители. и все.

Только вот... как уже упомянуто выше, на данный момент это невозможно для 2048-битных чисел и крайне проблематично для 1024-битных чисел.

Т.к. слабых мест у алгоритма нет. Чистая математика... А с ростом вычислительных возможностей, будет расти и длина ключа... вот и все...

 

Как пример, число 324 000 000 010 512 000 000 075 463

Оно простое или составное, и если составное, то из каких простых сомножителей состоит ? А это очень "маленькое" число... тем не менее, несколько секунд на определение сомножителей вы потратите...

[younghacker 7]

Чего вы копья ломаете?

Собственно времена сейчас такие, что память стала копеечной. Тоесть сейчас реально можно криптовать данные ключем размер которого совпадает с размером данных либо даже превышает их. Не имея ключа восстановить данные не даст возможности никакой квантовый процессор. Или перефразируя изменяя ключ из зашифрованных одних и тех же данных можно получить, как исходники винды так и музыкальный архив любой группы. А работает это ну просто фантастически быстро при помощи самой криптующей процессорной операции XOR.

[AndyM 0]

younghacker - ты только что открыл одноразовый блокнот Да, безусловно это самый надежный способ шифрования, но вот задачу безопасной передачи ключа никто не отменял. Как впрочем и задачу генерации ключа. И вообще это совсем из разных областей - симметричные и асимметричные алгоритмы. И память тут вообще не при чем - одноразовые блокноты использовали еще когда не было компьютеров

[younghacker 7]

Ничего я не открывал. Я о том, что если квантовый комп будет ломать длинные ключи, как орешки, имеется простейший лом, против которого кванты не помогут. Разве, что только квантовый утюг

[AndyM 0]

Простейший лом увы практически невозможно использовать. Как ты себе представляешь реализацию одноразового блокнота в современных условиях ? Быстродействие компьютеров это не такая большая угроза как ее малюют. Ну еще длиннее сделают ключ - это совершенно не проблема. Гораздо хуже если найдут аналитическое решение задачи разложения на простые множители. Вот по этому поводу как раз и ходят слухи что типа в NSA уже давно ее решили Или что у ФСБ есть backdoor к ГОСТ-у

[Yevgen35 0]

b]аналитическое[/b] решение задачи разложения на простые множители.

Вот по этому поводу как раз и ходят слухи что типа в NSA уже давно ее решили Или что у ФСБ есть backdoor к ГОСТ-у

Похоже на правду.

Особенно если вспомнить как в свое время были гонения на автора PGP, а потом все затихло.

А так же как долго были экспортные ограничения на длину ключа в IE.

Вероятно таки решение у них есть.

[AndyM 0]

Экспортные ограничения это на длину симметричного ключа в основном. Были времена когда за пределы Штатов нельзя было поставлять продукты с ключем шифрования больше 56 бит (реально обычно делали 40, ломается вообще без проблем). С Филом (автором PGP) я как-то встречался на одной из конференций. Он всем рассказывал что в текущей версии (тогда была кажется 6.0 и уже от Network Associates) все нормально и лично им проверено По поводу гонений есть предположение что это он так пиарился. Как его купили - "гонения" волшебным образом прекратились

[DigitalDreamer 0]

Что не обязательно ? Чтобы два числа были простыми, или чтобы они были 1024-битными, или для взлома RSA не нужно разложение на множители ?

 

Как работает RSA я вполне предятавляю. Но я совсем не уверен, что множетели по своей длине должны быть равны по длине 1/2 длины ключа. Т.е., их можно представить как 1024-битные (в нашем примере), но в одном или в обоих будут нули в старших разрядах.

 

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

 

Ну, строго говоря, задача взлом подразумевает под собой хотя бы примерное представление о том, что должно быть получено в результате. А вообще, действительно, не стоит мешать в одну кучу криптографию с открытым и закрытым ключем.

[Alexandro 0]

Как работает RSA я вполне предятавляю. Но я совсем не уверен, что множетели по своей длине должны быть равны по длине 1/2 длины ключа. Т.е., их можно представить как 1024-битные (в нашем примере), но в одном или в обоих будут нули в старших разрядах.

Хорошо. И это число будет "простым" ? И произведение двух таких чисел даст в итоге 2048-битное число ? или тоже будем добивать нулями ? в таком случае, мы создаем потенциальную уязвимость...

У нас задача сгенерировать два достоверно простых числа p и q, которые, после проверки различными методами, будут "с большой долей вероятности" простыми (как пример - http://www.cryptomathic.com/labs/rabinprimalitytest.html ). Множители, ИХМО, должны быть равны 1/2 длины ключа, т.к. произведение двух 1024-битных чисел дает 2048-битное число. По известным догмам математики, 1024-битных чисел в природе огромное количество. Упрощенно, примерно 8% из них - простые... При длине 4096 бита (2048х2048) - получаем еще большее количество гипотетических множителей...

[DigitalDreamer 0]

Хорошо. И это число будет "простым" ?

 

А что удивительно в том, что 1024-битное число с одним или несколькими старшими нулями может быть простым? Или вы предлагаете в данном случае понимать под 1024-битными числами только такие из них, которые имеют единицу в старшем разряде? Вот в этом то как-раз и будет уязвимость - злоумышленник будет наверняка знать старший бит, и область поиска ключа (а с ней, в общем-то, и время) сократятся в два раза. А что плохого в том, что бы брать множетели разной длины? Ведь что бы получить 2048-битный ключ, вполне можно использовать такие множетели. Ведь это несложная арифметика (я не про разложение на множетели).

[Yevgen35 0]

Экспортные ограничения это на длину симметричного ключа в основном.

Именно их я и имел ввиду.

 

все нормально и лично им проверено

В смысле согласовано с кем надо?

 

 

Американцам на слово верить нельзя.

"У них все несерьезно кроме денег" Брат-2.