RSA vs Elliptic Curve

Берём большое рандомное число

dd if=/dev/urandom status=none |tr -dc 0-9 |dd bs=1b count=1000 status=none

Пока парное дописываем в конец ещё одну цифру:

dd if=/dev/urandom status=none |tr -dc 0-9 |dd bs=1b count=1 status=none

Получаем число для старта: N.

На 32 ядра делаем из него 32 числа:

n: 0..31
Nn=N+2*n

В 32 потока запускаем перебор множителей «в лоб» учитывая https://ru.onlinemschool.com/math/library/divisibility_rule/#h8 нам не надо проверять числа у которых есть множитель который мы уже проверяли: парные, делящиеся на 3, 5, 7, 11, …

Пока ни одно из 32 чисел не будет простым то находим следующие число для старта:

N=N+64

Ищем снова.

Мне кажется, что я на баше за полчаса простое число найду…

Надо ещё проверять признак делимости на 7: https://umath.ru/theory/priznak-delimosti-na-7/

Достаточно начинать проверку с делимости на 3, 5, 7, 11.

Проверять делимость на 2, 4, 6, 8, 10, парные, делящиеся на уже проверенные - не надо.

Заканчивать проверку можно на N/12

Кто прикинет примерно сколько времени займет поиск простого числа? А то меня здесь криптографы целой вечностью пугают.

https://ru.m.wikipedia.org/wiki/%D0%9F%D1%80%D0%B8%D0%B7%D0%BD%D0%B0%D0%BA%D0%B8_%D0%B4%D0%B5%D0%BB%D0%B8%D0%BC%D0%BE%D1%81%D1%82%D0%B8

Добавляем признаки делимости на все известные простые числа:

3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 59, 79, 101, 1091

При первом прохождении создать список исключений, чисел состоящих из множителей, которые мы уже проверяли:

2, 4, 6, 8, 10, 12, 14, 15, … и использовать его для исключения проверки.

Что крыптоаналитики скажут? Найду на баше простое число с >1000 знаками за полчаса? Или надо вечность?

Ты это серьёзно или троллишь так?

Признаки делимости тебе не нужны, можно и просто деление сделать, комп быстрый. Проблема в том, что делимость на 3 5 7 11 это мизерная часть от того, что нужно, тебе надо будет (для rsa2048) перебирать делимость на примерно 253273727608007581871986532250783302243764796682120428669739789708733093230509302541409994109156253999019942913911591794163939406099549062088994837290916334341298113033824300020250644434126570088113974406171028720954425077854904247630648406210179217729294733250969195173046588462124915563362164452833152840 разных простых чисел. Даже если ты будешь проверять по триллиону делимостей в секунду, на этот перебор тебе потребуется примерно 8031257217402574260273545543213575033097564582766375845691900992793413661545830242941717215536410895453448215179844996009764694511020708462994509046515611819549026922685955733772534387180573632931062100652303041633511703382004827740697881982818975701715332738805466615076312419524508991 лет.

Это всё для того, чтобы проверить на простоту одно единственное число. Простые числа проверяют другими способами. Деление в лоб тоже делают, но только для вот этого короткого списка простых чисел примерно до 17 тысяч, а дальше другая математика. Можешь там же рядом посмотреть код.

https://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D1%86%D0%B5%D0%BB%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB

Но проверить является ли большое число простым за конечное время можно: Василенко О. Н. Теоретико-числовые алгоритмы в криптографии — М.: МЦНМО, 2003. — 328 с. — ISBN 978-5-94057-103-2 с.48

Тогда алгоритм поиска простого числа следующий:

Берём большое непарное число N как сказал выше.

Проверяем делится ли оно на список простых чисел, для которых существуют признаки деления, или без них (как быстрее).

Если не делится проверяем на простоту.

Пока не простое добавляем 2.

Можно помнить деление на 3 и каждый третий раз вместо 2 добавлять 4.

Можно помнить деление на 5 и каждый пятый раз вместо 2 добавлять 4.

Можно помнить деление на 7 и каждый седьмой раз вместо 2 добавлять 4.

По аналогии можно помнить деление для 11, 13, 17, 19, 23, 29, 31, 37, 41

Большие простые числа не сильно редко расположены? Мы найдем по этому алгоритму простое число за конечное время?

Глянул https://ru.m.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D1%81%D1%82%D0%BE%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%BE#%D0%91%D0%BE%D0%BB%D1%8C%D1%88%D0%B8%D0%B5_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0

В принципе они так и делают.

Зная «маленькое» простое число строят по некой формуле большое простое число.

Проверяют его на отсутствие малых простых делителей.

Потом несколько раз проверяю вероятностным тестом простоты типа Рабина.

В конце проверяют истинным тестом простоты.

Пока на любом из этапов тест не проходит строят новое большое число.

То есть между проверкой на маленькие простые делители и истинной проверкой простоты ещё пару раз запускают вероятностную проверку простоты.

Они не сплошным перебором перебирают числа, как предлагал я. А ищут вероятностно тыкая в диапазон N<P<2*N.

Или щупая по формуле P=2Sn+1 где S известное простое число, а n < 2*S+1. Пропуская много простых чисел.

Коню уже понятно, что закладки есть всюду

Какие ваши доказательства?

Кажется бегло с RSA разобрались. Готов доказать наличие «упрощения» в алгоритме создание ключа RSA отрицательно влияющую на его криптостойкость.

Для работы RSA с заданной крыптостойкостью нам надо найти два оооченьбольших простых числа для приватного и публичного ключа. И как оказалось это большая проблема. ;)

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

1. Вероятностно с диапазона, или по некой формуле выбираем кандидата: N.

2. Проверяем N на делимость известным рядом простых чисел.

3. Некоторое количество раз проверяем N на простоту с помощью вероятностных тестов простоты.

4. Запускаем истинный тест простоты.

5. Пока на любом из тестов 2-4 не проходит выбираем нового кандидата: N.

На практике истинный тест простоты не используется!

Из приватного и публичного ключей можно извлечь кандидатов в простые числа и проверить самостоятельно тесты 2-4.

Кто знает генерялку ключей RSA которая выбирает случайное число из диапазона и проводит проверку на истинность простоты? Сколько занимает времени генерация пары RSA4096 ?

Да, этот RSA держится всего на одной тоненькой сопле под названием ВЕРА в то, что в 1977 году уважаемые Рональд Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института не занесли кому полагается эффективный алгоритм факторизации целого числа.

НЕТ доказательства того, что не существует решения задачи факторизации целого числа за полиномиальное время.

По этому RSA с самого начала использовать не стоило. Здесь нет даже предмета для верификации!

Так то у нас кроме вернама и его модификаций гарантий нет вообще. Что говорить P!=NP никто доказать пока так и не смог. А если принять P!=NP за истину на ВЕРУ то пробовали делать на задаче о рюкзаке крипту, вот только вышло, что даже если P!=NP и строгого работающего оптимально в 100% случаев решения задачи нет, то оказывается что у нас есть алгоритмы которые успешно решат задачу оптимально в 90% случаев. Классный алгоритм выходит для криптографии, который в 10% случаев не ломается никак, а в 90% ломается за 5 минут.

А мне кажется, что тепловая смерть вселенной наступит раньше.

Замечательно, тогда из каких источников вы берёте свои знания? Тайные чёрные книги, житейская мудрость, Коран, Упанишады? Откуда бы вы не черпали своё представление о реальности, ваш источник не более надежен, чем СМИ, в которые вы не верите.

Тайные чёрные книги

А эти:

https://upload.wikimedia.org/wikipedia/commons/3/39/Tetragrammaton_Sefardi.jpg

Танах, кабала, - достоверные источники?

Для кого-то вполне, но для меня нет, я не семитских кровей.

Для кого-то вполне

Беда этого мира, что депутаты с президентами их принимают за истину и национальные законы разных стран основывают на всяких талмудах. От сюда и геноциды с войнами.

Возможно, возможно… Они просто именно семитских кровей. Без негатива товарищ майор.

Они просто именно семитских кровей.

Учитывая, что сын Адама: Сиф,- родился не от Евы, а от овцы, доля негатива в сказаном имеется.

Генетика конечно влияет на решения.

Но я имел ввиду религиозные учения основанные на торе, танахе, …: иудаизм, христианство, мусульманство. Влияние аврамистических религий на: законы разных стран мира, торговлю, внешнеполитические отношения, проводимые геноциду, войны, …

Есть ли смысл перекатываться на elliptic curve ключи? Для меня, пока, RSA простой, надёжный, работает даже на говне мамонта. В отличии от новомодных кривых.

Как раз наоборот. В реализации rsa есть примерно миллион мест где можно ошибиться и допустить тайминг атаку или чего похуже. А вот ed25519 прост как топор - фигачь код по очевидной спеке и все будет тип-топ, Бернштейн все предусмотрел. И никаких непонятно откуда взятых параметров там нет, в отличие от NIST-овых ECDSA.

Но я имел ввиду религиозные учения основанные на торе, танахе, …: иудаизм, христианство, мусульманство

Я думаю, что всё же не соглашусь. Тора или Ветхий Завет, другая авраамическая литература – это не просто сборник семитских мифов, многое там является копией и вдохновением из мифов и легенд их соседей завоевателей (Египет, Вавилон, Греки, потом даже Римляне), куски их многих мифов это копии мифов их завоевателей. Так что с самого начала в авраамических религиях уже были западные нарративы, а западное христианство (тот же католицизм) буквально переосмыслил всё, через античную греческую философию. Поэтому на мой взгляд, не авраамические религии повлияли на западное общество (или любое другое), а западное общество и культура сделала авраамические религии такими. Та же история с исламом, я считаю, что мусульмане живут, как живут, не потому что на них так повлиял ислам, а нооборт, их ислам такой из-за обычаев этих обществ (ислам Индонезии не похож на ислам в Афганистане).

На иудаизм сатанинские религии древнего Вавилона и Египта имели самое непосредственное влияние.

Авраам вышел из Ура Халдейского в весьма зрелом возрасте и знал религии и науки древней Месопотамии.

Моисей был воспитан дочерью египетского фараона и обучен религии и наукам древнего Египта.

Влияние на тору сатанизма с Вавилона или Египта самое непосредственное. Да аврамистические религии подцепили сатану в Вавилоне или Египте. Мое мнение, что в Египте (~400 лет рабства).

На оригинал торы, написанный (а на каком языке?!!) 1700 лет до н.э. влияние западной цивилизации 100% отсутствовало. Влияние Египта было самым непосредственным. Кажется самые древние, известные версии торы записаны на производном от финикийского(Европа) письма - самаритянском.

Сам танах был записан 450 лет до н.э. цензурщиком торы и поздних семитских писаний книжником Эздрой. Он отцензурил и записал часть древних книг и устных еврейских сказаний оформив в один канонический свиток. Религия Вавилона имела самое непосредственное влияние (~400 лет плена) на записанную Эздрой раннюю версию танаха. Влияние западной цивилизации на ранние версии танаха (450-300 лет до н.э.) отсутствовало. Ранний Танах был записан на древнеарамейском языке, не производном от финикийского, не европейском. На отцензуренную часть танаха имели непосредственное влияние книги закона окружающих семитов племен, с которыми семиты вступали в брак и принимали их закон и традиции как дополнение к своим.

300-200 лет до н.э танах был переведен на древнегреческий. И эта версия танаха живет по сей день своей западной отдельной жизнью. Перевод был сделан не точный, не сохранил первоначальный смысл текстов, иногда даже им противоречил. Сделавшие этот перевод не знали и не соблюдали древние семитские традиции.

Примерно 500-1000 годах иудейская секта масоретов окончательно доцензурела танах. Все древние свитки торы и танаха масореты варварски сжигали.

На все евангельские тексты имеет самое непосредственное влияние западная цивилизация. Они были созданы ею в 100-200 годах, как защита от наступавшего иудаизма. Написаны на древнегреческом. В последующих веках евангельские тексты поддавались цензуре (сокрытию частей) и разным дополнениям…

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

Ситуация с дезинформацией и ложью ярко подтверждается с разделением иудаизма на две ветки по признанию существования «устной торы». Танах - письменный закон, типа только маленькая часть, а основная часть записана в талмуде. Мое мнение, что «устная тора» и талмуд были выдуманы частью семитского общества, как защита от иудаизма, примерно во времена написания евангелии западной цивилизацией, 100-200 годы. Талмуд бороться с иудаизмом как евангелия у западной цивилизации и коран в арабской.

У славянская цивилизация очень поздно начала защищаться против иудаизма, примерно в 1500 годах. Тогда это называлось защитой «от жидовствующих». Защищалась просвещением сограждан издавая корректный перевод доступных ей слабо отцензуренных текстов библии. Ярчайшим примером славянской истории в борьбе против «жидовствующих» есть:

• библия Новгородского метрополита Геннадия Гонзова 1499 года.
• 1519 год библия Франциска Скорины.
• Острожская библия Ивана Федорова нередактированный оригинал первого издания 1980 года, где в конце пирамида с глазом, а под пирамидой дата. Вы их полные сканы сегодня не найдете, запрещены властью…

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