следующая тема »

[celeron]

Dia+ifXBs0WVwQUnh/WCUFJHuRRReeBAEABvEjf5S0lKlHGq5sQa01HDnAOYQjp274Dwc26uQZZ/PHFoVcTUdA==

Вот короткое сообщение, зашифрованное RSA с ключом 256 бит (использована библиотека криптокомпонентов для Delphi TPLockBox). Хотелось бы посмотреть, как уважаемый аффтар его расшифрует. Мне кажется это прежде всего в его интересах.
Я бы на месте Urixa сначала написал бы программу, потом бы уже обнародовал свои исследования. Истории о потерянных исходниках и злых желторотых "хацкеров", которые ждут-недождутся готовой программы доверия не прибавляют.

[Urix]

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

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

[BeeVee]

Urix, Вы нам скажите, какой длины число сможете реально за день разложить.
Мы же не знаем, какая у Вас система.

[quatro]

Зачем изобретать велосипед, когда все уже придумано до нас?!
Вот вам число:

Name:         RSA-640
Prize:        $20000
Digits:       193
Digit Sum:    806
31074182404900437213507500358885679300373460228427275457201619488
23206440518081504556346829671723286782437916272838033415471073108
501919548529007337724822783525742386454014691736602477652346609

Urix, когда факторизуете, результаты отправьте сюда - http://www.rsasecurity.com/rsalabs/node.asp?id=2095
Думаю что если вы правы и все так как вы говорите и пишете в своей статье, то вознаграждение в 20000 долларов США, покроет ваши затраты на факторизацию этого числа. Кстати судя по архивам этого форума, Вам уже предлагали принять участие в этом... Странно что имея на руках действующий алгоритм, вы до сих пор этого не сделали.


//Админ: [/b]"число" я разбил на три строки по техническим причинам и для удобства восприятия страницы.

[quatro]

2Admin:

Дмитрий! Я поправил статью и выслал её Антону Серго. Смотрите, что получается в результате на Вашем примере.

А на сайте сейчас последняя версия статьи висит или предыдущая?

[Антон Серго]

2Admin:

Дмитрий! Я поправил статью и выслал её Антону Серго. Смотрите, что получается в результате на Вашем примере.

А на сайте сейчас последняя версия статьи висит или предыдущая?

Вопрос к автору, но ИМХО, последняя из мной полученных.

[quatro]

однако автор молчит, и ничего не отвечает ни про текст статьи ни про числа. Никак не понять, или он факторизацией занят или с юристами спорит в сосдених ветках.
Urix Ау!!!

Вы бы нам сказали беретесь вы за факторизацию предложенного числа или нет? И последняя версия статьи висит на сайте или нет?

[Urix]

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

В любой из версий описания алгоритма приводятся все идеи алгоритма, поэтому не важно, какая версия сейчас висит на сайте. Основными идеями являются:
1. использование всех положительных действительных чисел, а не только целых или рациональных;
2. использование меры порядка на основе среднего геометрического;
3. использование различных позиционных систем счисления;
4. операция выравнивания чисел на интервал или ее аналог операция нормализации мантиссы;
5. использование муаровых решеток, период которых в логарифмических координатах задается основанием системы счисления;
6. вычисление сразу всех делителей числа за счет применения муаровых решеток.

Вот Вам реализация первой целочисленной части алгоритма. На выдачу выдаются те интервалы, где НЕ могут быть делители. Проверяйтесь. Все работает. Я брал более ста разных чисел.
В тексте первой части программы я оставил данные для 575-разрядного числа. Текст на экране разъезжается.

# cat qfact_step1.bc
#!/usr/bin/bc -q

define encl (n, a, m)
{
    auto a2,e0,e1,e2,n0,n1,m0,m1,l0,r0,l1,r1;

    a2 = a^2;
    e0 = 1; e2 = a2;
    while (e2 < n) { e0 = e2; e2 *= a2; }
    e1 = e0 * a;
    m0 = sqrt(n*e0^2);
    while (m0 > e2) { m0 /= a2; }
    if (m0 > e1) { m1 = m0;  m0 /= a; } else { m1 = m0*a; }
    if (n < e1) { n0 = n; n1 = n0 * a; } else { n1 = n; n0 = n1 / a; }
    if (m0 < n0) {
        l0 = n0; r0 = e1;
        l1 = n1; r1 = e2;
    } else {
        l0 = e0; r0 = n0;
        l1 = e1; r1 = n1;
    }
    print "\n===================================\n"
    while (l0 > 1) {
        if (l1 < m) {
            print l1,"-"
            if (r1 < m) { print r1,"\n" } else { print m,"\n"  }
        }
        if (l0 < m) {
            print l0,"-"
            if (r0 < m) { print r0,"\n" } else { print m,"\n" }
        }
        l0 /= a2; r0 /= a2;
        l1 /= a2; r1 /= a2;
    }
}

p = 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317
q = 472772146107435302536223071973048224632914695302097116459852171130520711256363590397527
n = p*q;
m = sqrt(n)

print "n  = ",n,"\n"
print "m  = ",m,"\n"
print "p  = ",p,"\n"
print "q  = ",q,"\n"

a = 2;
while (a < m) { a *= 2; }
for (a /= 2; a > 0; a /= 2) { ret = encl(n,a+1,m) }

quit

[Dmitry]

p = 398075086424064937397125500550386491199064362342526708406385189575946388957261768583317
q = 472772146107435302536223071973048224632914695302097116459852171130520711256363590397527
n = p*q;

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

P = 3.98075...*10⁸⁶
Q = 4.72772...*10⁸⁶
N = P*Q = 1.881987...*10¹⁷³

Напомню, что исходное число для факторизации было 3.1074...*10¹⁹²

А, смотрю, что пока писал у вас текст сообщения слегка поменялся. Я так понимаю, что вы все-таки другое число факторизовали, которое уже было факторизовано?

[Urix]

Вы внимательно читайте то, что пишут другие. А то у меня создается впечатление, что Вы слышите только то, что хотите слушать. Односторонняя такая система.

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

P.S. Я понял, как надо оптимизировать метод. И, естественно, сразу нашел нижнюю границу вычислительных затрат на факторизацию. Затраты не могут быть меньше, чем 2*int(log2(2*int(log2(N))+1))+1 операций "огораживания".
P.P.S. Я это число использовал лишь как тест. Факторизовывал, естественно, гораздо меньшие числа, но не такие маленькие, как 5 и 11.