взломщикам RSA на заметку

Solo

+1 ))

 

ссылочку можно на рабочие образцы массового производства? П.С.: а кто мешает точно так же симметрики ломать? Вобщем, полностью солидарен с Solo

 

MSoft

раскатал губу) когда запустят те же квантовые тачки - ох, как я сомневаюсь, что они будут в продаже. да, и вообще, мало кто будет знать о рабочих образцах)

в корень зришь, товарищ) но между симметриком и асинхронкой есть принципиальная разница: задачу слома симметрика сложней формализировать а асинхронка может ломаться без знания плейнтекста вообще.

 

UbIvItS
если ты тут еще и про эльбрус скажешь, тогда я точно буду знать твой настоящий ник

 

MSoft

какой Эльбрус, товарищ, - эта гора стоит и будет стоять, когда нас не будет, так что я в ней не сомневаюсь))))))
-------------------------------
а про рса скажу ещё вот что не верь моим сомнениям, ибо истина в том, что рса сломать нельзя))

у меня много имён и все хорошие)

 

UbIvItS

Ну, ты нас совсем запутал! А нельзя эту истину сформулировать математически, в виде теоремки там какой-нибудь?

 

Конечно надувательство! Ведь скажем похожая задача извлечения квадратного корня решается элементарно и быстро, так почему разложение должно быть сложней?

Извлечь корень можно так - ставим старший бит, возводим в квадрат, если перебор, сбрасываем старший бит, а если нет - оставляем. Ставим следущий бит числа, если перебор - сбрасываем - и т.д. N битный корень квадратный за N шагов можно получить.

Предлагаю обобщить данный алгос для факторизации самостоятельно в качестве разминки =))).

 

Даже если они смогут исполнять нормальные программы и тем более ломать шифры. Есть ли уверенность что
это поможет ломать RSA?
Допустип прототип параллельно исполнял 65536 команд - RSA ключу в 2048 бит от этого явно ни холодно ни жарко. 2032 бит ломаются так же долго. Сколько таких камней придётся сделать чтобы ломать ключ?

 

>Ведь скажем похожая задача извлечения квадратного корня решается элементарно и быстро, так почему >разложение должно быть сложней?

При извлечении корня ищем семетричный результат (x*x тут только одно решение) а для нахождения делителя они разные (x*y могут быть много решений).

>Сколько таких камней придётся сделать чтобы ломать ключ?
Если специализированые то немного (с текущей возможностями минимизации).
Один риск ядро для управления и 10000 спец вычислителей (с большой разрядностью) в одной микрухе.

 

в квантовой факторизации немного другой принцип

 

Такая квантовая машинка сусществует и уже продается, ее память - 16 (ку)бит.
А мощща таких квантовых тачек не n, а 2^n. стало быть это 16 бит дают парралелизьм в 65536, а вот 64К квантовой памяти это уже не 65536, а 2^65536, ясно теперь? Квантовый Коммандор Амига на 64К пямяти расколет ключ с числом комбинаций 2^2048 как семечки моментом.

При факторизации тоже только одно (не считая единицы). Например, реши систему уравнений
a b = n
sin(pi a)^2 + sin(pi b)^2 = 0
и получищь искомые a и b.

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

 

to persicum
Все, что есть, это обычная маркетенговая чушь.
1) Кубит незя перевести в эквивалент битов. (тока если очень грубо квантовать но это не квантовый комп будет).
2)Причем сдесь память < 64К пямяти расколет ключ >
3)<квантовая машинка> это уже оналоговое устройство, а не цифровое. И вычисления там преближенные.

>sin(pi a)^2 + sin(pi b)^2 = 0
Синус штука переодичная такчто решений дохера, а не a и b

 

crypto

вот видишь - ты начал говорить как я), я тоже был бы непротив увидеть вразумительное обоснование надёжности рса. впрочем, флуд маздай) если меня катком жизни не закатает в асфальт - будем обсуждать ряд моих будущих поделок
persicum
твой путь взлома рса тупиковый: N=X^2*cos(alpha)*sin(alpha) - X не обязан быть целым числом и даже просто рациональным правда, можно попробовать вот что: пошаговый перебор альфы, тоесть мы получаем серию значений: T0.....Ti и выбираем ближайшие Th>N>Tl (Ti == X^2*cos(ai)*sin(ai)). ну, конечно, не вооружённым глазом видно, что с иксом у нас опять же проблемус, ибо мы его, паршивца, не ведаем. тогда берём некий X_hypotheses для краткости Xh - в итоге Xh( > or < )X, тоесть в расшаговке у нас получается смещённый результ - вот можно и поискать наиболее эффективные средства борьбы со смещением. хотя здесь можно обойтись без углов вообще. но путь, честно говоря, малоперспективный, если у тебя нет каких - то доп. метод.

 

SWR

!= плохо - всё зависит только от скорости сходимости результа и ресурсоёмкости применяемой методы.

 

persicum

Предпосылка неверная. Зная все квадратные корни из какого числа (кв.вычета) по модулю составного N, легко можно получить факторизацию N.
В частности, факторизацию легко получить, например, если найти квадратный корень из 1 по модулю N, отличный от 1 и -1.
Поэтому извлечение квадратного корня по модулю числа N в общем случае ничуть не проще факторизации этого числа.

 

UbIvItS
SWR
Бррр... Народ, вы хоть график синуса из школы помните?
идея была использовать мощщь плавучих действительных чисел для факторизации.
Иба ничего перебирать не нужно, нужно просто искать последовательные приближения.

Например, корень квадратный из N можно извлечь выполняя реккурентно преобразование
x=(x+N/x)/2. При этом количество верных цифр удваивается с каждым проходом, и методу пофиг что
из 5 извлечь или из 25 (целый ответ).

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

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

RElf

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

 

persicum
Корень тебе поможет только при факторизации произведения чисел, которые мало друг от друга отличаются. См. Weger attack.

 

мда....., забавно - наша милая беседа обо всём, кроме работы товарища, который аж шесть страниц исписал - непорядок: сейчас почитаю его)

 

Для меня лично чтение статей почти бесполезно... Вот если бы кто накатал рабочий пример на алголоподобном языке хотябы для чисел одинарной точности и продемонстрировал бы мне это мажоритарное голосование бит или что там еще - тогда бы поверил. А так - это очередная туфта - нету кода - значит определенно лажа.

 

persicum

мне это знакомо (, впрочем, в меру возможности стараюсь преодолеть в себе эту слабость - уважаю тех, кто быстро въезжает в чужие задумки, ибо это талант.

полностью разделяю твоё желание)

не могу разделить твоей категоричности. к тому же, каждому взломщику любой системы защиты желаю удачи))