|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Если рассматривать алгоритм создания открытого и секретного ключей, то здесь выбираются два случайных простых числа. https://ru.wikipedia.org/wiki/RSA И здесь сразу противоречие: случайное и простое. Это два разных числа, и вероятность того, что случайное число будет простым равно вероятности простого числа на некотором диапазоне. Далее смотрим, а какое оно случайное простое число. https://ru.wikipedia.org/wiki/Случайное_простое_число И там читаем: «Ввиду того, что тестирование простоты больших чисел требует существенных временных затрат, требование простоты получаемого числа часто ослабляют до сильной псевдопростоты по нескольким различным случайным основаниям.» А далее: делится это случайное число на 54 начальных простых чисел (отсекается 80% нечётных чисел) и выполняется тест Миллера-Рабина к раз по количеству к битов в числе (ещё надо понять, а сколько это операций вычислений). Если находим, то вероятность к, что число простое. И если нет, то ищется следующее число. И сколько времени нужно искать это число? По-видимому, лучше решать обратную задачу: найти критерии возможных псевдослучайных чисел, чтобы с помощью их выбирать нужные «случайные числа» для криптографии. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 07:16 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy Usov, взять базу простых чисел и случайным образом выбрать . Вот и будет случайное простое число ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 09:07 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
вадяGennadiy Usov, взять базу простых чисел и случайным образом выбрать . Вот и будет случайное простое числоА на каком простом числе эта база заканчивается? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 09:21 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovА на каком простом числе эта база заканчивается?один из вариантов https://primes.utm.edu/lists/small/millions/ ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 10:20 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
вадяGennadiy UsovА на каком простом числе эта база заканчивается?один из вариантов https://primes.utm.edu/lists/small/millions/ Сразу вопрос: будет 100-ый миллион, миллиард, 10 миллиардов... Когда-то это закончится. Когда? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 12:48 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy Usovбудет 100-ый миллион, миллиард, 10 миллиардов... Когда-то это закончится. Когда?теория говорит о том, что числовой ряд бесконечен - значит ни когда. на любое самое хитрое шифрование - всегда есть не нулевая возможность взлома - вопрос только во времени. выбор за тобой ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 14:12 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
вадяGennadiy Usovбудет 100-ый миллион, миллиард, 10 миллиардов... Когда-то это закончится. Когда?теория говорит о том, что числовой ряд бесконечен - значит ни когда. на любое самое хитрое шифрование - всегда есть не нулевая возможность взлома - вопрос только во времени. выбор за тобойПро шифрование ещё рано говорить. Мы говорим о базе простых чисел. Так жду ответа - насколько велика в компьютере база простых чисел? Где её предел? То есть, количество простых чисел, начиная с 2. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 14:57 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovИ сколько времени нужно искать это число? Долго. Именно поэтому генерация RSA ключа может длиться несколько секунд. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 15:06 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovТак жду ответа - насколько велика в компьютере база простых чисел?вопрос а сколько тебе надо? можешь запустить поиск и добавлять в базу, пока диск не заполнишь. к примеру для mysql поле BIGINT может иметь значение 18 446 744 073 709 551 615, сколько до этого значения простых чисел - хз. если исходить из моей ссылки со списком найденных Код: plaintext 1. 2.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 15:34 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
вадя, не хз, а порядка N/ln(N) ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 16:30 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
вадяGennadiy UsovТак жду ответа - насколько велика в компьютере база простых чисел?вопрос а сколько тебе надо? можешь запустить поиск и добавлять в базу, пока диск не заполнишь. к примеру для mysql поле BIGINT может иметь значение 18 446 744 073 709 551 615, сколько до этого значения простых чисел - хз. если исходить из моей ссылки со списком найденных Код: plaintext 1. 2.
... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 16:46 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
вадяGennadiy UsovТак жду ответа - насколько велика в компьютере база простых чисел?вопрос а сколько тебе надо? можешь запустить поиск и добавлять в базу, пока диск не заполнишь. к примеру для mysql поле BIGINT может иметь значение 18 446 744 073 709 551 615, сколько до этого значения простых чисел - хз. если исходить из моей ссылки со списком найденных Код: plaintext
И ещё вопрос - а сколько чисел "влезает" на компьютер? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 16:52 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Я считал уже дисковые расходы на хранение Всех 64 битных простых. Могу найти ссылку. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 17:54 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Изопропилне хз, а порядка N/ln(N)это величины одного порядка Gennadiy UsovИ ещё вопрос - а сколько чисел "влезает" на компьютер?смотря как хранить.. 100 000 000 записей для субд это не много. BarloneЭто очень маленькое число, для криптографии нужно число в несколько сотен десятичных знаков.ТС спрашивал от цифры 2.... ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 18:00 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
По оперативной памяти я приводил сравнительные расчеты здесь 21823126 ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 19:22 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonПо оперативной памятитак что такое 30гиг памяти по сравнению терабайтами дисков? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 19:46 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
вадяGennadiy UsovИ ещё вопрос - а сколько чисел "влезает" на компьютер?смотря как хранить.. 100 000 000 записей для субд это не много.А если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 19:58 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovА если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать?это тоже не много. SSD в RAID5... ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 20:14 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
По всем типам памяти я приведу картинку. Такое-себе напоминание. Не для программистов а для физиков-математиков и прочих сочувствующих. Реально мы можем складывать небольшой объем только в Memory (это те самые бюджетные 30Гб). Чтоб не разорится. По времени доступа к произвольной ячейке. Точных цифр я не помню но по моему для памяти класса DDR4 это составляет 10-16 наносекунд. Время доступа к диску. Обычно меряют чтение случайного сектора. И там это время на много порядков хуже. Будет порядка милисекунд. Точно не помню но в процессе топика мы уточним. Тоесть если вы в топике - инженеры то должны понимать что разница между милисекундой и десятком наносекунд составляет: (избавимся от множителя) 10 ms = 0.010 mks = 0.000010 ms 10 ms : 10 ns = 100 000 : 1 Порядка сто тысяч к одному. Тоесть диск в среднем в сто тысяч раз медленнее чем оперативная память. По поводу дисков (Hard Disk). Я возьму за основу WD (Western Digital) Purple 10TB 256MB 5400rpm WD100PURZ 3.5 SATA III. Это наиболее толстый диск (10 терабайт) который я нашел в розничной торговле. Он - типичный медленнячок. Для бэкапов и архивов. Скорость шпинделя 5400 - оборотов какраз говорит об этом. Это не для игр и операционок а для долгого хранения информации. Его цена в данный момент времени - $339.99 на сайте производителя. Под спойлером. Если вы врдуг решили что выбор плохой и вы знаете другой диск получше - я не буду против. Мы просто пересчитаем цифры. Но в целом перерасчет не сильно повлияет на результат. Вангую не более десятка процентов. Его мощность составляет 6.2 Вт. Габариты 26.1 x 147 x 101.6 мм, 0.65 кг Прошу запомнить эти цифры. Мы к ним еще вернемся. Мы посчитаем массу и кубатуру дискового хранилища для любого диапазона простых чисел. Кроме того мы посчитает удельную стоимость хранения 1 простого числа в долларах или центах как будет угодно. SSD мы пока тоже брать не будем. Т.к. по сути SSD это энергонезависимая память имеющая интерфейс диска. Как класс хранения она мне в топике неинтересна и кроме того в пирамиде памяти она слишком дорога для нашей задачи. Но как кеш ее можно рассмотреть. Что еще осталось за кадром. Как хранить? В каком формате? Надо ответить на следующие вопросы. - (1) нужен-ли нам произвольный доступ к любому числу? Или хватит последовательного? - (2) нужно-ли сжатие? (zip/gzip) - нужен-ли поиск в диапазоне? - гибридные варианты пунктов (1) (2) можно бить на блоки и использовать псевдо-последовательный и псевдо-произвольный - API/форматы. Определяются (1) (2). Базы данных. CSV-файлы. Raw-store. Key-value. Key-value (hash/b+tree). Bitmap. Поскольку драйвером этого топика является господин Усов. То я предлагаю сначала ответить ему. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 20:15 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
вадяmaytonПо оперативной памятитак что такое 30гиг памяти по сравнению терабайтами дисков? Читайте внимательно линк. Я там ответил на этот вопрос. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 20:18 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
mayton, mayton- (1) нужен-ли нам произвольный доступ к любому числу? Gennadiy Usovвыбираются два случайных простых числа. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 20:23 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonЧитайте внимательно линк. Я там ответил на этот вопрос.я внимательно прочитал... я к тому что для ТС Gennadiy UsovА если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать? ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 20:26 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Вы хоть раз пробовали из базы данных выбрать случайную строку? Это не так просто уверяю вас! У нас нет первичного ключа. У нас само число является ключом к самому себе. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 20:27 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
вадяmaytonЧитайте внимательно линк. Я там ответил на этот вопрос.я внимательно прочитал... я к тому что для ТС Gennadiy UsovА если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать? Он - не программист. Он не знает многих вещей из программно аппаратной архитектуры. Поэтому я отвечу. Не проблема обработать 1 триллион чисел. Проблема - сделать это быстро. Тоесть придумать совокупность тех-средств (конфигурация) и алгоритмов чтобы наши запросы (я еще не знаю какие) создали мягкую нагрузку на железо и выдали результат. И в разумное время. До того как погаснет солнце. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 20:30 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
вадяGennadiy UsovА если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать?это тоже не много. SSD в RAID5... Это очень малое требование. Надо простое число порядка 2^1024 или примерно 10^307. В диапазоне 2^1023 ... 2^1024 примерно 2^1013 или 10^304 простых чисел. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 20:34 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonВы хоть раз пробовали из базы данных выбрать случайную строку? Это не так просто уверяю вас! У нас нет первичного ключа. У нас само число является ключом к самому себе.можно и поле последовательного ключа поиметь. пожертвовав местом хранения. вопрос что выгоднее. maytonПроблема - сделать это быстро.поэтому я и предложил RAID из SSD. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 20:39 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
вадяmaytonВы хоть раз пробовали из базы данных выбрать случайную строку? Это не так просто уверяю вас! У нас нет первичного ключа. У нас само число является ключом к самому себе.можно и поле последовательного ключа поиметь. пожертвовав местом хранения. вопрос что выгоднее. maytonПроблема - сделать это быстро.поэтому я и предложил RAID из SSD. Да ты подожди предлагать. Это топик растет ногами из другого топика где обсуждали факторизацию 2^2048. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 20:44 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Формула количества простых в диапазоне 1 ... N это N / ln(N). В случае со степенями двойки 2^K / 0.69K. Даже для K=64 это уже 2^60 или 10^18 или 1 000 000 000 000 000 000. Это только для N = 2^64. А мы про 2^1024. ... |
|||
:
Нравится:
Не нравится:
|
|||
17.03.2019, 20:51 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonдля …математиковmayton10 ms : 10 ns = 100 000 : 1 Порядка сто тысяч к одному. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 08:22 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Мы ушли от темы топика. Тема топика звучит так: "лучше решать обратную задачу: найти критерии возможных псевдослучайных чисел, чтобы с помощью их выбирать нужные «случайные числа» для криптографии." О чём идёт речь. В процессе нахождения больших случайных чисел выполняется тест Миллера-Рабина к раз по количеству к битов в числе. (или любого другого теста) При этом в какой-то момент случайное число, по версии теста, не имеет признаков составных чисел, и это число "назначается" простым числом. Вопрос один: а кто-нибудь пробовал на небольших числах (но на предельных значениях по количеству обнаруженных простых чисел) применить тест простоты, а потом сравнить это применение с обычным алгоритмом Эратосфена? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 14:03 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovВопрос один: а кто-нибудь пробовал на небольших числах (но на предельных значениях по количеству обнаруженных простых чисел) применить тест простоты, а потом сравнить это применение с обычным алгоритмом Эратосфена? Сравнить на предмет чего? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 14:15 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Dima TGennadiy UsovВопрос один: а кто-нибудь пробовал на небольших числах (но на предельных значениях по количеству обнаруженных простых чисел) применить тест простоты, а потом сравнить это применение с обычным алгоритмом Эратосфена?Сравнить на предмет чего?Например: Тест показал, что число можно считать простым, а алгоритм Эратосфена (или любой перебор известных простых чисел) показал, что у этого случайного числа есть множители. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 14:22 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovDima Tпропущено... Сравнить на предмет чего?Например: Тест показал, что число можно считать простым, а алгоритм Эратосфена (или любой перебор известных простых чисел) показал, что у этого случайного числа есть множители. Такое возможно, это в википедии написано. Алгоритм Миллера-Рабина позволяет выполнять проверку за малое время и давать при этом достаточно малую вероятность того, что число на самом деле является составным ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 14:26 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Dima TGennadiy UsovНапример: Тест показал, что число можно считать простым, а алгоритм Эратосфена (или любой перебор известных простых чисел) показал, что у этого случайного числа есть множители.Такое возможно, это в википедии написано. Алгоритм Миллера-Рабина позволяет выполнять проверку за малое время и давать при этом достаточно малую вероятность того, что число на самом деле является составнымЕсли это возможно, то сразу следующий вопрос: а на каких порядках простых чисел может появиться такая ситуация ("простое число" не является простым числом)? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 14:34 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovDima Tпропущено... Такое возможно, это в википедии написано. пропущено... Если это возможно, то сразу следующий вопрос: а на каких порядках простых чисел может появиться такая ситуация ("простое число" не является простым числом)? На маленьких. Псевдопростое число ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 14:38 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Мы можем генерировать произвольные произведения известных нам простых. И подавать их на вход Миллеру. И если где-то он даст сообщение о том-что число простое - то мы засчитываем ошибку. Далее - дело статистики. Только Миллер-Рабин имеет настроечные параметры. С этим надо определится. В какой конфигурации настроек мы его будем тестить. Тогда матрица отчота получистя многомерная. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 14:39 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Dima TGennadiy UsovЕсли это возможно, то сразу следующий вопрос: а на каких порядках простых чисел может появиться такая ситуация ("простое число" не является простым числом)? На маленьких. Псевдопростое число Мало того, что наука изучает простые числа, но она ещё изучает и псевдопростые числа. А где можно применить псевдопростые числа? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 14:48 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonМы можем генерировать произвольные произведения известных нам простых. И подавать их на вход Миллеру. И если где-то он даст сообщение о том-что число простое - то мы засчитываем ошибку. Далее - дело статистики. Только Миллер-Рабин имеет настроечные параметры. С этим надо определится. В какой конфигурации настроек мы его будем тестить. Тогда матрица отчота получистя многомерная.Проверяли уже. Вот например https://oeis.org/A074773 в диапазоне до 5,5 триллионов есть целых 21 составное число, проходящее тест Миллера-Рабина по основаниям 2, 3, 5 и 7. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 15:45 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
А еще говорят есть тест на псевдопростоту , для которого пока не нашли ни одного контрпримера ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 15:58 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarlonemaytonМы можем генерировать произвольные произведения известных нам простых. И подавать их на вход Миллеру. И если где-то он даст сообщение о том-что число простое - то мы засчитываем ошибку. Далее - дело статистики. Только Миллер-Рабин имеет настроечные параметры. С этим надо определится. В какой конфигурации настроек мы его будем тестить. Тогда матрица отчота получистя многомерная.Проверяли уже. Вот например https://oeis.org/A074773 в диапазоне до 5,5 триллионов есть целых 21 составное число, проходящее тест Миллера-Рабина по основаниям 2, 3, 5 и 7.Интересная информация. Я посмотрел на эти числа, и в них, кроме первого, 2 множителя, причем каждый из них "в районе" корня квадратного из этого числа. Почему-то эти числа заканчиваются на 5537838510751 (13-й порядок). А что далее? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 16:00 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneА еще говорят есть тест на псевдопростоту , для которого пока не нашли ни одного контрпримераА Вы задумывались о том, почему много тестов на простоту ? Мне известно около 10 тестов. Или так много простоты, что тесты со всеми не справляются? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 16:03 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneПроверяли уже. Вот например https://oeis.org/A074773 в диапазоне до 5,5 триллионов есть целых 21 составное число, проходящее тест Миллера-Рабина по основаниям 2, 3, 5 и 7.Посмотрел это сообщение подробно, и там оказалась ссылка на таблицу всех таких чисел до 2^64. А их очень много... ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 16:15 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovПочему-то эти числа заканчиваются на 5537838510751 (13-й порядок). А что далее?Немножко дальше заканчиваются https://oeis.org/A074773/a074773.txt ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 16:16 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneПроверяли уже. Вот например https://oeis.org/A074773 в диапазоне до 5,5 триллионов есть целых 21 составное число, проходящее тест Миллера-Рабина по основаниям 2, 3, 5 и 7.Посмотрел это сообщение подробно, и там оказалась ссылка на таблицу всех таких чисел до 2^64. А их очень много...Ага, очень много... На примерно 4*10^17 простых приходится 16757 составных, проходящих 4 раунда теста. То есть у нас вероятность приблизительно одна двадцатипятитриллионная, что мы ошибочно примем составное число за простое. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 16:22 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
И сразу имеет место очередной вопрос: Есть псевдопростые числа, которые подходят для криптографии. Они являются составными числами, в которых 2 множителя, которые почти равны друг другу. И есть другие составные числа, которые почти равны этим псевдопростым числам (один порядок). И тоже состоят из двух множителей, которые почти равны друг другу. Так почему эти составные числа нельзя использовать в криптографии? Из-за ограничителя - теста простоты (очередного)? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 16:27 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneНа примерно 4*10^17 простых приходится 16757 составных, проходящих 4 раунда теста. То есть у нас вероятность приблизительно одна двадцатипятитриллионная, что мы ошибочно примем составное число за простое.А чем составное число плохо для криптографии? Допустим, приняли составное число за простое ... Что произойдет с шифрованием и дешифрованием? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 16:30 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovА чем составное число плохо для криптографии? Допустим, приняли составное число за простое ... Что произойдет с шифрованием и дешифрованием? 21820624 ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 16:37 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovА чем составное число плохо для криптографии? Допустим, приняли составное число за простое ... Что произойдет с шифрованием и дешифрованием? 21820624 Допустим... Но клиент не знает. Система пропустила псевдослучайное число. И что - облом, и что делать клиенту, если не получилась расшифровка? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 16:41 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Что-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 16:47 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovПочему-то эти числа заканчиваются на 5537838510751 (13-й порядок). А что далее?Немножко дальше заканчиваются https://oeis.org/A074773/a074773.txt Немного поизучал эту таблицу. 1 число – 10 знаков. Произведение первых двух множителей равно почти 4-м величинам третьего множителя. 8 чисел – 12 знаков. Первый множитель в четыре раза меньше второго множителя ( с точностью до 3) 15 чисел – 14 знаков. Первый множитель в два раза меньше второго множителя (с точностью до 1). Далее много чисел – 15 знаков. Первый множитель в четыре раза меньше второго множителя ( с точностью до 3). Далее - мала ячейка ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 16:53 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneЧто-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа.На каком этапе программы? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 16:54 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneЧто-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа.На каком этапе программы? Я-бы по другому спросил. Алгорим ЭЦП будет нарушен если множителей будет не 2 а 3 ? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 17:01 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonGennadiy UsovНа каком этапе программы?Я-бы по другому спросил. Алгорим ЭЦП будет нарушен если множителей будет не 2 а 3 ?Зачем мелочиться. А что если множителей для чисел, порядка 2^1024, будет 10, 20? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 17:09 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovА что если множителей для чисел, порядка 2^1024, будет 10, 20? Видимо систему будет проще взломать. Как писали ранее, числа Кармайкла позволяют шифровать/дешифровать корректно, хотя и не являются простыми. Далее нужно читать про алгоритм RSA, что бы понять, отсеивают ли их. Вы, Геннадий, конечно же про RSA не захотели почитать? А вдруг там есть ответ? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 17:13 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
alex55555Gennadiy UsovА что если множителей для чисел, порядка 2^1024, будет 10, 20? Видимо систему будет проще взломать. Как писали ранее, числа Кармайкла позволяют шифровать/дешифровать корректно, хотя и не являются простыми. Далее нужно читать про алгоритм RSA, что бы понять, отсеивают ли их. Вы, Геннадий, конечно же про RSA не захотели почитать? А вдруг там есть ответ? Если это так то всё равно нет чёткого осознания слабости ключа. Ключ создан. Слабый он или нет - хз. Беря во внимание редкость этих лже-primes я-бы сказал что мы зря беспокоимся. Усов! Не беспокойтесь. Ребе и Миллер уверены в своей победе! ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 17:49 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonУсов! Не беспокойтесь. Ребе и Миллер уверены в своей победе!Я не понял: Ребе и Миллер или Ребе Миллер? ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 17:58 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Рабин == Рабинович == Раввин. Фамилия происходящая от духовного сана. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 18:01 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
alex55555Gennadiy UsovА что если множителей для чисел, порядка 2^1024, будет 10, 20? Видимо систему будет проще взломать. Как писали ранее, числа Кармайкла позволяют шифровать/дешифровать корректно, хотя и не являются простыми. Далее нужно читать про алгоритм RSA, что бы понять, отсеивают ли их. Вы, Геннадий, конечно же про RSA не захотели почитать? А вдруг там есть ответ?В вики записано: "В основу криптографической системы с открытым ключом RSA положена сложность задачи факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования (обратной операции) за разумное время необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего необходимо знать разложение числа на простые множители." Если принять во внимание сообщение 21834523 , то решение задачи факторизации заключается в поиске первого множителя, делении числа на этот множитель и ищется следующий множитель. То есть, если множители небольшие ( по меркам 2^ 1024), то достаточно поработать с небольшими простыми числами. Если число простое, то компьютер должен иметь массив простых чисел до, например корень.кв.(2^ 1024). ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 18:13 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Я думаю что алгоритм генерации пары RSA имеет защиту от дурака и не позволяет генерить тривиальные факторизации. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 18:19 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneЧто-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа. 21776823 ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 18:37 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Dima TBarloneЧто-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа. 21776823 Он же параметризованный. Нужно сказать какие были значения случайного числа a. Сколько было итераций. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 19:37 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Да здесь я ошибся 10 ms = 0.010 mks = 0.000010 ms Вот так правильно. 10 ns = 0.010 mks = 0.000010 ms Десять наносекунд это одна десятитысячная милисекунды. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 20:09 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Я тут под катом скопирую кусок промышленного кода. С любезного разрешения Josh Bloh. Это стартовая точка алгоритма нечеткого определения простоты. Обратите внимание на параметр certainty. Это не проверяемое число. Это параметр. Чуть дальше по коду он влияет на количество раундов проверки. Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25.
Следующи уровень в стеке - расчет раундов. В конце Миллер-Рабин работает в паре с Люка-Лемером. В коньюнкции. Они как-бы друг друга проверяют. Забавно что Миллер параметризуется случайным числом. А Люка не параметризуется. Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43.
Само туловище Миллера я копировать не буду. Вроде-бы есть уже пища для размышлений. ... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 20:57 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonGennadiy Usovпропущено... На каком этапе программы? Я-бы по другому спросил. Алгорим ЭЦП будет нарушен если множителей будет не 2 а 3 ?Нам нужно знать функцию Эйлера для произведения. Если известно разложение на простые множители m=p*q, то φ(m) = φ(p)*φ(q) = (p-1)*(q-1) А если разложение на простые множители неизвестно, то найти значение этой функции сложно. RSA основывается на теореме Эйлера : Код: plaintext
Ну а дальше из свойств степени: нашли i,j такие что Код: plaintext
Пара i,m - открытый ключ, пара j,m - секретный. Шифрование - возведение в степень i по модулю m, расшифровка - возведение результата шифрования в степень j по модулю m. Код: plaintext
... |
|||
:
Нравится:
Не нравится:
|
|||
18.03.2019, 21:15 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Теорема Эйлера в теории чисел гласит: Если a и m взаимно просты, то .... Это не означает, что a и m - простые числа. Может быть здесь посмотреть? ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 07:20 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonВот так правильно. 10 ns = 0.010 mks = 0.000010 ms Десять наносекунд это одна десятитысячная милисекунды.Я так понимаю, здесь всем начхать, какую вежливую божью росу несут другие? ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 08:03 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonДесять наносекунд это одна десятитысячная милисекунды.Теперь я позанудствую: 9 - 1- 3 = 5. Одна стотысячная", Карл!" ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 08:31 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Ну и ладно. Спасибо за фикс. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 09:17 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonDima Tпропущено... 21776823 Он же параметризованный. Нужно сказать какие были значения случайного числа a. Сколько было итераций. Глубоко не вникал, в инете нашел исходник. Похоже студенческая поделка попалась. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 09:22 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovТеорема Эйлера в теории чисел гласит: Если a и m взаимно просты, то .... Это не означает, что a и m - простые числа. Может быть здесь посмотреть?Что посмотреть? ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 09:34 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovЕсли число простое, то компьютер должен иметь массив простых чисел до, например корень.кв.(2^ 1024). сколько простых чисел в этом интервале? авторДля сравнения — количество атомов в наблюдаемой Вселенной составляет по разным оценкам от 4*10^79 до 10^81 ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 10:12 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovТеорема Эйлера в теории чисел гласит: Если a и m взаимно просты, то .... Это не означает, что a и m - простые числа. Может быть здесь посмотреть? У меня тоже был некоторый лингвистический ступор. Представил себе сумму или разность двух рациональных чисел. Если знаменатели просто перемножаются - то взаимнопростые. Чуть позже написал такое. Код: sql 1.
... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 11:13 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovТеорема Эйлера в теории чисел гласит: Если a и m взаимно просты, то .... Это не означает, что a и m - простые числа. Может быть здесь посмотреть?Что посмотреть?Использование в методе двух взаимно простых чисел вместо двух простых чисел ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 12:48 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
По аналогии со скатертью Улама. Я думаю неплохо-бы нарисовать на 2д плоскости пары взаимно-простых чисел. И туда--же докидать еще каких-то чисел-редких-исключений. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 12:59 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonПо аналогии со скатертью Улама. Я думаю неплохо-бы нарисовать на 2д плоскости пары взаимно-простых чисел. И туда--же докидать еще каких-то чисел-редких-исключений.Таких чисел (взаимно простых) можно наделать очень много ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 13:07 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneпропущено... Что посмотреть?Использование в методе двух взаимно простых чисел вместо двух простых чиселВ каком методе? Если вы взяли большое случайное число, и оно оказалось составным, то вы для него функцию Эйлера не знаете. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 13:08 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
На этом и строится RSA - владелец секретного ключа знает функцию Эйлера для произведения двух больших простых чисел, потому что он эти множители сгенерировал, а никто другой, зная произведение, но не зная сомножителей, вычислить ее не может. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 13:12 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovИспользование в методе двух взаимно простых чисел вместо двух простых чиселВ каком методе? Если вы взяли большое случайное число, и оно оказалось составным, то вы для него функцию Эйлера не знаете.Почему не знаю? Если я сам составлял составное (псевдопростое) число, то я и знаю, сколько в этом числе множителей (Функция Эйлера — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним). ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 13:32 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovЕсли я сам составлял составное (псевдопростое) число, то я и знаю, сколько в этом числе множителей (Функция Эйлера — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним). Вы уж как-то определитесь... Gennadiy UsovА чем составное число плохо для криптографии? Допустим, приняли составное число за простое ... Что произойдет с шифрованием и дешифрованием?То ли приняли составное число за простое, то ли специально взяли больше множителей. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 13:42 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovЕсли я сам составлял составное (псевдопростое) число, то я и знаю, сколько в этом числе множителей (Функция Эйлера — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним).Вы уж как-то определитесь... Gennadiy UsovА чем составное число плохо для криптографии? Допустим, приняли составное число за простое ... Что произойдет с шифрованием и дешифрованием?То ли приняли составное число за простое, то ли специально взяли больше множителей.А здесь приведены две выборки по одному и тому же вопросу: применение псевдопростых (составных) чисел в вопросах криптографии. Так что и не надо определяться. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 13:47 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneпропущено... В каком методе? Если вы взяли большое случайное число, и оно оказалось составным, то вы для него функцию Эйлера не знаете.Почему не знаю? Если я сам составлял составное (псевдопростое) число, то я и знаю, сколько в этом числе множителей (Функция Эйлера — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним). Барлон имеет в виду что в протоколе секретной переписки между Алисой и Бобом каждый владеет своим секретным ключом и никому его не передает. Публичная часть - публикуется для осуществления переписки. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 13:47 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonБарлон имеет в виду что в протоколе секретной переписки между Алисой и Бобом каждый владеет своим секретным ключом и никому его не передает. Публичная часть - публикуется для осуществления переписки.У каждого будет свой секретный ключ. Только он будет формироваться несколько по иному. Главное - это возможность использования составных (взаимно простых) чисел. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 13:51 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneпропущено... Вы уж как-то определитесь... пропущено... То ли приняли составное число за простое, то ли специально взяли больше множителей.А здесь приведены две выборки по одному и тому же вопросу: применение псевдопростых (составных) чисел в вопросах криптографии. Так что и не надо определяться.Составное число, для которого мы знаем разложение на простые, и составное число, для которого не знаем разложение на простые - это два разных вопроса, на которые есть два разных ответа. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 13:51 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneСоставное число, для которого мы знаем разложение на простые, и составное число, для которого не знаем разложение на простые - это два разных вопроса, на которые есть два разных ответа.Пока я не вижу в этом разницы. Нужен пример. А перечень общеизвестных псевдопростых чисел, который был опубликован на данном топике, имеет по 2 множителя, и вроде эти числа применяют. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 13:54 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonБарлон имеет в виду что в протоколе секретной переписки между Алисой и Бобом каждый владеет своим секретным ключом и никому его не передает. Публичная часть - публикуется для осуществления переписки.Ну в принципе для шифрования достаточно одного секретного ключа. Боб генерирует случайный сессионный ключ, шифрует на открытом ключе Алисы, и передает зашифрованным по открытому каналу. Алиса расшифровывает его своим секретным ключом. Теперь у обоих есть сессионный ключ, которым они шифруют дальнейший обмен обычным симметричным алгоритмом. Секретный ключ Боба нужен только для проверки Алисой, что к ней обращается действительно Боб. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 14:02 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovПока я не вижу в этом разницы. Нужен пример. Какой? Вот такой пойдет? 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099 составное число, что можно проверить тестом Миллера-Рабина. Попробуйте найти для него функцию Эйлера. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 14:10 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonПо аналогии со скатертью Улама. Я думаю неплохо-бы нарисовать на 2д плоскости пары взаимно-простых чисел. И туда--же докидать еще каких-то чисел-редких-исключений. Нарисовал. Красный - пара координат - взаимно-простые. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 14:31 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Barlone, я думаю пойдёт, но для осознания масштаба помогают цифры в баксах которые выплачивались за это дело ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 14:44 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovПока я не вижу в этом разницы. Нужен пример. Какой? Вот такой пойдет? 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099 Что помешало именно этому составному числу быть "полезным" криптографии? ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 16:26 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonmaytonПо аналогии со скатертью Улама. Я думаю неплохо-бы нарисовать на 2д плоскости пары взаимно-простых чисел. И туда--же докидать еще каких-то чисел-редких-исключений.Нарисовал. Красный - пара координат - взаимно-простые.Красивая картинка. Неплохо бы её применить в народном хозяйстве. Но взаимно-простые числа могут иметь несколько пересечений: для одного числа имеется множество взаимно-простых. Ведь и число 2 есть взаимно-простое число со всеми нечетными числами. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 16:31 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovЧто помешало именно этому составному числу быть "полезным" криптографии? Если ключами на основе составного числа зашифровать, а потом расшифровать, то в итоге получится не то что зашифровали. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 16:31 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovНужен пример не числа, а того, что именно составное число не подошло для криптографики. Что помешало именно этому составному числу быть "полезным" криптографии?Так именно незнание φ и мешает ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 16:33 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovНужен пример не числа, а того, что именно составное число не подошло для криптографики. Что помешало именно этому составному числу быть "полезным" криптографии?Так именно незнание φ и мешаетВ той талице псевдослучайных чисел два множителя для большинства чисел. Следовательно, если это число р, то φ для одного числа р будет равно (р-3). ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 16:51 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovВ той талице псевдослучайных чисел два множителя для большинства чисел. Следовательно, если это число р, то φ для одного числа р будет равно (р-3).Нет конечно, никак не p-3 ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 16:56 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovВ той талице псевдослучайных чисел два множителя для большинства чисел. Следовательно, если это число р, то φ дляоднφого числа р будет равно (р-3).Нет конечно, никак не p-3Обычно в таких случаях говорят - чему равно это значение. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 18:45 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneпропущено... Нет конечно, никак не p-3Обычно в таких случаях говорят - чему равно это значение.Так было уже 21836602 ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 19:13 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneТак было уже 21836602 Следовательно, если формула для двух составных чисел p и q, каждое из которых состоит из двух множителей, то имеем (p-3)*(q-3) ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 19:32 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneТак было уже 21836602 Следовательно, если формула для двух составных чисел p и q, каждое из которых состоит из двух множителей, то имеем (p-3)*(q-3)Нет конечно. (p-1)*(q-1) никак не равно p*q-3 ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 19:40 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Там еще ссылка в википедию была, сходите почитайте. φ от произведения четырех сомножителей равно произведению четырех φ (от каждого из сомножителей). ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 19:46 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneТам еще ссылка в википедию была, сходите почитайте. φ от произведения четырех сомножителей равно произведению четырех φ (от каждого из сомножителей).У меня не 4 сомножителя, а 2 сомножителя, каждый из которых имеет только два множителя. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 21:04 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneТам еще ссылка в википедию была, сходите почитайте. φ от произведения четырех сомножителей равно произведению четырех φ (от каждого из сомножителей).У меня не 4 сомножителя, а 2 сомножителя, каждый из которых имеет только два множителя. Мне кажется ты на основе свойств функции Эйлера "продавливаешь" свою гипотезу. ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 21:16 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovУ меня не 4 сомножителя, а 2 сомножителя, каждый из которых имеет только два множителя.Что? И где разница между четыре и два раза по два? ... |
|||
:
Нравится:
Не нравится:
|
|||
19.03.2019, 21:31 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonМне кажется ты на основе свойств функции Эйлера "продавливаешь" свою гипотезу.Да, несколько дней назад это было гипотезой. А сейчас – это уже более серьёзное утверждение. Неужели вы не замечаете кучу нестыковок в теории шифрования с помощью простых чисел? 1.Все говорят, 2^1024, простые числа, простые числа, бла, бла, бла, а это число около 1,0Е+300. В то же время платят большие деньги, чтобы найти множители для чисел в районе 130 десятичных знаков и более.kealon(Ruslan)Barlone,я думаю пойдёт, но для осознания масштаба помогают цифры в баксах которые выплачивались за это делоТак какие числа находят тесты простоты? Я пока не говорю про 2^2048. 2.Много тестов простоты, и ни один из них не повторяет другого. Это говорит о том, что каждый тест «охватывает» (или находит) определённое количество составных чисел. Но составных чисел очень и очень много, следовательно, и тестов простоты должно быть тоже много. Если следовать этой теории, то существующие тесты простоты «охватывают» небольшую часть составных чисел. Оставшиеся составные числа охватывают ещё не найденные тесты простоты. Поэтому можно сформулировать следующий вывод: большое количество составных чисел после «пропускания» через тесты простоты «становятся» простыми числами. И данные «простые» числа (псевдопростые числа) в большом количестве используются в криптографии! Защитники простых чисел в криптографии – защищайтесь! ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 10:00 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovУ меня не 4 сомножителя, а 2 сомножителя, каждый из которых имеет только два множителя.Что? И где разница между четыре и два раза по два?Хотите сказать, что если есть два числа p и q, каждый из которых состоит из 2-х множителей: p = a*b q = c*d то функция Эйлера будет равна: f=(a-1)*(b-1)*(c-1)*(d-1)? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 10:21 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy Usov, если a,b,c,d не равны между собой и являются простыми числами то ДА ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 11:54 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneпропущено... Что? И где разница между четыре и два раза по два?Хотите сказать, что если есть два числа p и q, каждый из которых состоит из 2-х множителей: p = a*b q = c*d то функция Эйлера будет равна: f=(a-1)*(b-1)*(c-1)*(d-1)?Да, если a,b,c,d - простые, причем разные. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 11:55 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovmaytonМне кажется ты на основе свойств функции Эйлера "продавливаешь" свою гипотезу.Да, несколько дней назад это было гипотезой. А сейчас – это уже более серьёзное утверждение. Неужели вы не замечаете кучу нестыковок в теории шифрования с помощью простых чисел? Я не вижу никаких нестыковок. Я пока вижу в криптографии запас прочности еще на 10 лет. Денежные премии за нахождение новых простых - это просто популяризация науки. Как с большой теоремой Ферма. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 12:11 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovХотите сказать, что если есть два числа p и q, каждый из которых состоит из 2-х множителей: p = a*b q = c*d то функция Эйлера будет равна: f=(a-1)*(b-1)*(c-1)*(d-1)?Да, если a,b,c,d - простые, причем разные.Отлично! a,b,c,d - простые и разные. Были сомнения... BarloneGennadiy UsovИспользование в методе двух взаимно простых чисел вместо двух простых чиселВ каком методе? Если вы взяли большое случайное число, и оно оказалось составным, то вы для него функцию Эйлера не знаете. ... На этом и строится RSA - владелец секретного ключа знает функцию Эйлера для произведения двух больших простых чисел, потому что он эти множители сгенерировал, а никто другой, зная произведение, но не зная сомножителей, вычислить ее не может.Теперь можно сказать, что нам известна функция Эйлера? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 12:13 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonGennadiy UsovДа, несколько дней назад это было гипотезой. А сейчас – это уже более серьёзное утверждение. Неужели вы не замечаете кучу нестыковок в теории шифрования с помощью простых чисел? Я не вижу никаких нестыковок. Я пока вижу в криптографии запас прочности еще на 10 лет. Денежные премии за нахождение новых простых - это просто популяризация науки. Как с большой теоремой Ферма.Как в том анекдоте: и ты говори.. Говорить можно что угодно, и про запас, и про прочность, и про популяризацию, и про Ферма (очень сильный аргумент!), и про .... А где ответы на два моих вопроса? И конечно, Вы составных чисел не видите? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 12:18 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy Usov1.Все говорят, 2^1024, простые числа, простые числа, бла, бла, бла, а это число около 1,0Е+300. В то же время платят большие деньги, чтобы найти множители для чисел в районе 130 десятичных знаков и более.kealon(Ruslan)Barlone,я думаю пойдёт, но для осознания масштаба помогают цифры в баксах которые выплачивались за это делоТак какие числа находят тесты простоты? Нет, не так. Эти числа сгенерированы как произведение двух "вероятно простых" (прошедших тесты) чисел. Призы выплачивались RSA Laboratories, разработчиком криптосистемы RSA, как доказательство надежности такого метода шифрования. Gennadiy Usov2.Много тестов простоты, и ни один из них не повторяет другого. Это говорит о том, что каждый тест «охватывает» (или находит) определённое количество составных чисел. Ну не так много. Во-первых, есть тесты детерминированные (точно доказывающие простоту) и вероятностные (отсеивающие составные с какой-то вероятностью). Во-вторых, среди детерминированных есть медленные тесты для чисел специального вида (типа чисел Мерсенна) и очень медленные для произвольных чисел. Не те, не другие для криптографии не подходят - числа специального вида использовать нельзя, так как их мало, а для произвольных чисел скорость совершенно неприемлема - кому надо сутки генерировать секретный ключ? Поэтому используют вероятностные тесты. В основном Миллера-Рабина. Иногда в комбинации с Люка - 21836586 и 21836159 на самом деле это оно. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 12:26 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy Usovmaytonпропущено... Я не вижу никаких нестыковок. Я пока вижу в криптографии запас прочности еще на 10 лет. Денежные премии за нахождение новых простых - это просто популяризация науки. Как с большой теоремой Ферма.Как в том анекдоте: и ты говори.. Говорить можно что угодно, и про запас, и про прочность, и про популяризацию, и про Ферма (очень сильный аргумент!), и про .... А где ответы на два моих вопроса? И конечно, Вы составных чисел не видите? Поэтому когда ты что-то критикуешь неконкретно - говори. Я Усов критикую Миллера-Рабина за нестрогость и неправдоподобность. Но реализация которую я приводил в качестве примера находится вне твоей критики поскольку она использует совокупность НЕСКОЛЬКИХ алгоритмов которые ты еще пока не исследовал и незнаешь их вероятности ложно позитивного срабатывания. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 12:32 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonПоэтому когда ты что-то критикуешь неконкретно - говори. Я Усов критикую Миллера-Рабина за нестрогость и неправдоподобность. Но реализация которую я приводил в качестве примера находится вне твоей критики поскольку она использует совокупность НЕСКОЛЬКИХ алгоритмов которые ты еще пока не исследовал и незнаешь их вероятности ложно позитивного срабатывания.Снова не то... Я не критикую Миллера-Рабина, там всё прекрасно, проверено. Но это тест только на составные числа. А дальше, допущение, что ... Как Вы это не понимаете? Мы же говорим о простых числах для криптографии. А это, как известно, две разные вещи. Тогда надо честно сказать, что могут быть составные числа для криптографии. А дальше, ещё интересно. Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные). Вот интересно! Почему молчит об этом Barlone? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 12:42 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy Usov1.Все говорят, 2^1024, простые числа, простые числа, бла, бла, бла, а это число около 1,0Е+300. В то же время платят большие деньги, чтобы найти множители для чисел в районе 130 десятичных знаков и более. Так какие числа находят тесты простоты? Нет, не так. Эти числа сгенерированы как произведение двух "вероятно простых" (прошедших тесты) чисел. Призы выплачивались RSA Laboratories, разработчиком криптосистемы RSA, как доказательство надежности такого метода шифрования.Как тяжело просто сказать, что число может быть составным. А так вероятно простое. И добавляется - прошедшее тест. А почему бы не заплатить? Это реклама надежности, тут деньги не считают. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 12:46 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovmaytonПоэтому когда ты что-то критикуешь неконкретно - говори. Я Усов критикую Миллера-Рабина за нестрогость и неправдоподобность. Но реализация которую я приводил в качестве примера находится вне твоей критики поскольку она использует совокупность НЕСКОЛЬКИХ алгоритмов которые ты еще пока не исследовал и незнаешь их вероятности ложно позитивного срабатывания.Снова не то... Я не критикую Миллера-Рабина, там всё прекрасно, проверено. Но это тест только на составные числа. А дальше, допущение, что ... Как Вы это не понимаете? Мы же говорим о простых числах для криптографии. А это, как известно, две разные вещи. Тогда надо честно сказать, что могут быть составные числа для криптографии. А дальше, ещё интересно. Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные). Вот интересно! Почему молчит об этом Barlone? Мне сложно перечитывать взад все-все ваши гипотезы. Вы можете подытожить и изложить ваши сомнения в виде пунктов? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 12:48 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovТогда надо честно сказать, что могут быть составные числа для криптографии. А дальше, ещё интересно. Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные). Вот интересно! Почему молчит об этом Barlone?Ну с практической точки зрения, это маловероятно. Но если допустим кто-то даже выпустит ssl сертификат с таким косяком, при попытке установить защищенное соединение будет случаться облом. И просто сделают новый сертификат, с другим ключом. Может даже не станут разбираться, из-за бага в программе получился кривой сертификат или случайно составное число проскочило. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 12:49 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Есть еще к примеру вероятность, что какой-нибудь мюон из космических лучей прилетит и испортит значение в ячейке памяти. А память с ECC далеко не везде стоит. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 12:55 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy Usov2.Много тестов простоты, и ни один из них не повторяет другого. Это говорит о том, что каждый тест «охватывает» (или находит) определённое количество составных чисел. Ну не так много. Во-первых, есть тесты детерминированные (точно доказывающие простоту) и вероятностные (отсеивающие составные с какой-то вероятностью). Во-вторых, среди детерминированных есть медленные тесты для чисел специального вида (типа чисел Мерсенна) и очень медленные для произвольных чисел. Не те, не другие для криптографии не подходят - числа специального вида использовать нельзя, так как их мало, а для произвольных чисел скорость совершенно неприемлема - кому надо сутки генерировать секретный ключ? Поэтому используют вероятностные тесты. В основном Миллера-Рабина. Иногда в комбинации с Люка - 21836586 и 21836159 на самом деле это оно.А Вы задумывались, почему их много (по Вашему - немного)? Эти тесты друг друга не повторяют! Разная математика, и следовательно, рассматриваются разные последовательности чисел (так мне кажется!). Хорошо, нашли два теста для криптографии, быстрые, быстрее находят множители, значит, что-то пропускают (так мне кажется). Либо, рассматривают только "мелкие" множители (когда множителей много). Кстати, а почему до сих пор нет сравнения на небольших числах для теста Миллера-Рабина для нахождения известных простых чисел? (может быть и есть, но я не видел) Разработчикам криптографики не хочется это показывать? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 12:59 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovТогда надо честно сказать, что могут быть составные числа для криптографии. А дальше, ещё интересно. Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные). Вот интересно!Ну с практической точки зрения, это маловероятно. Но если допустим кто-то даже выпустит ssl сертификат с таким косяком, при попытке установить защищенное соединение будет случаться облом. И просто сделают новый сертификат, с другим ключом. Может даже не станут разбираться, из-за бага в программе получился кривой сертификат или случайно составное число проскочило.А вот здесь самое интересное. Из-за составного числа, оказывается, может случиться облом (говорят, в расшифровке). Но разработчики криптографики об этом не предупреждают. Просто сказали, что только простое число. А почему - промолчали. И я не видел (может быть и есть) результов анализа применения (по ошибке) составных чисел. А ведь если есть ограниченния, то сразу появляется куча статей. Сомневающихся хватает (на себя не указываю) ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 13:06 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovКстати, а почему до сих пор нет сравнения на небольших числах для теста Миллера-Рабина для нахождения известных простых чисел? (может быть и есть, но я не видел) Разработчикам криптографики не хочется это показывать? На диапазоне до 4х миллиардов мы пожалуй можем это проверить. Делайте ставки Усов. Сколько промахов даст Ребе Миллер с Люкой? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 13:22 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovА вот здесь самое интересное. Из-за составного числа, оказывается, может случиться облом (говорят, в расшифровке). Но разработчики криптографики об этом не предупреждают. Просто сказали, что только простое число. А почему - промолчали.Вообще-то, это известная особенность. Если вы об этом не знали - ну это ваши проблемы. Если пользователь, не являющийся спецом, с таким столкнется - он не отличит результат от бага в программе. Ну пошлет он багрепорт разработчику - тот добавит пару раундов Рабина-Миллера, или прикрутит Люка, чтоб в ближайшие сто лет такое не повторялось. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 13:23 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonНа диапазоне до 4х миллиардов мы пожалуй можем это проверить. Делайте ставки Усов. Сколько промахов даст Ребе Миллер с Люкой?Да проверяли же: до 2^64 ноль ошибок. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 13:24 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonGennadiy UsovКстати, а почему до сих пор нет сравнения на небольших числах для теста Миллера-Рабина для нахождения известных простых чисел? (может быть и есть, но я не видел) Разработчикам криптографики не хочется это показывать?На диапазоне до 4х миллиардов мы пожалуй можем это проверить. Делайте ставки Усов. Сколько промахов даст Ребе Миллер с Люкой?Если такой тест будет, то интересно рассмотреть интервал между двумя последовательными простыми числами (нечётные числа). Я бы поставил на 10%. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 13:26 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarlonemaytonНа диапазоне до 4х миллиардов мы пожалуй можем это проверить. Делайте ставки Усов. Сколько промахов даст Ребе Миллер с Люкой?Да проверяли же: до 2^64 ноль ошибок.Есть ссылка? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 13:28 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneпропущено... Немножко дальше заканчиваются https://oeis.org/A074773/a074773.txt Немного поизучал эту таблицу. 1 число – 10 знаков. Произведение первых двух множителей равно почти 4-м величинам третьего множителя. 8 чисел – 12 знаков. Первый множитель в четыре раза меньше второго множителя ( с точностью до 3) 15 чисел – 14 знаков. Первый множитель в два раза меньше второго множителя (с точностью до 1). Далее много чисел – 15 знаков. Первый множитель в четыре раза меньше второго множителя ( с точностью до 3). Далее - мала ячейкаВот это "с точностью до..." на самом деле надо конкретизировать. Ну первое там число Кармайкла, оставим его в покое. А для остальных: эти числа - произведение двух множителей p, q таких, что НОД(p-1, q-1) большой. Чем больше этот НОД, тем больше вероятность обломаться тесту Миллера-Рабина. А тест Люка обламывается на произведениях p, q таких что НОД(p-1, q+1) большой. (Для доказательства надо лезть в теорию групп, это тут вряд ли кто осилит). Теперь попробуйте придумать пару p, q чтобы и НОД(p-1, q-1) и НОД(p-1, q+1) одновременно были большими. Можно еще пытаться сконструировать что-то из больше чем двух сомножителей, там все еще сложнее, но что-то даже в https://oeis.org/A074773 я местами потыкался - все попадают произведения двух (хотя у меня поначалу было подозрение, что там должно быть еще некоторое количество чисел Кармайкла кроме первого). ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 13:45 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneпропущено... Да проверяли же: до 2^64 ноль ошибок.Есть ссылка?Да давал уже - https://ru.wikipedia.org/wiki/Тест_Бейли_—_Померанца_—_Селфриджа_—_Уогстаффа Кстати, о "много тестов простоты". Взяли комбинацию Миллера-Рабина и Люка, и дали новое название... ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 13:48 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovЭти тесты друг друга не повторяют! Разная математика, и следовательно, рассматриваются разные последовательности чисел (так мне кажется!). Да одинаковая там математика, везде считают порядок группы. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 13:54 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovНо разработчики криптографики об этом не предупреждают. О чём предупреждать-то? В системах генерации RSA ключей есть финальная проверка на корректность их работы. Если шифрование-дешифрование с их помощью не прошло корректно, ключи выкидывается на помойку и генерируются новые. И, главное, кого предупреждать-то? Разработчики это и так знают, а для пользователей - см. выше. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 14:50 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovТогда надо честно сказать, что могут быть составные числа для криптографии. А дальше, ещё интересно. Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные).Вот интересно!Ну с практической точки зрения, это маловероятно. Но если допустим кто-то даже выпустит ssl сертификат с таким косяком, при попытке установить защищенное соединение будет случаться облом. И просто сделают новый сертификат, с другим ключом. Может даже не станут разбираться, из-за бага в программе получился кривой сертификат или случайно составное число проскочило.Теперь у меня ещё одна идея. Если из-за числа, которое оказалось составным, происходит облом при расшифровании, то почему нельзя проверять это число, одновременно с тестом простоты, в режиме шифрование-расшифрование. Проверка будет проходить на небольшом тесте. Это займёт немного времени. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 15:48 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonGennadiy UsovЯ не критикую Миллера-Рабина, там всё прекрасно, проверено. Но это тест только на составные числа. А дальше, допущение, что ... Мы же говорим о простых числах для криптографии. А это, как известно, две разные вещи. Тогда надо честно сказать, что могут быть составные числа для криптографии. А дальше, ещё интересно. Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные).Мне сложно перечитывать взад все-все ваши гипотезы. Вы можете подытожить и изложить ваши сомнения в виде пунктов?На самом деле гипотеза у меня пока одна: имеет место большое количество составных чисел, которые после «пропускания» через тесты простоты «становятся» простыми числами. Всё остальное - это следствие данной гипотезы. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 15:52 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovТеперь у меня ещё одна идея. Если из-за числа, которое оказалось составным, происходит облом при расшифровании, то почему нельзя проверять это число, одновременно с тестом простоты, в режиме шифрование-расшифрование. Проверка будет проходить на небольшом тесте. Это займёт немного времени.Пропустил предыдущее сообщение, а там есть ссылка на такую проверку, которая уже имеет место. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 15:54 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneпропущено... Ну с практической точки зрения, это маловероятно. Но если допустим кто-то даже выпустит ssl сертификат с таким косяком, при попытке установить защищенное соединение будет случаться облом. И просто сделают новый сертификат, с другим ключом. Может даже не станут разбираться, из-за бага в программе получился кривой сертификат или случайно составное число проскочило.Теперь у меня ещё одна идея. Если из-за числа, которое оказалось составным, происходит облом при расшифровании, то почему нельзя проверять это число, одновременно с тестом простоты, в режиме шифрование-расшифрование. Проверка будет проходить на небольшом тесте. Это займёт немного времени.Ну тут ровно так же, как с тестом простоты. На каком-то значении шифрование-дешифрование может пройти, а на другом нет. Шифруется в RSA некоторое большое число, обычно сессионный ключ. Если тест Ферма на этом числе пройдет, то и дешифрование сработает. Конечно, тесты обычно прогоняют на маленьких значениях, но нет никаких причин, чтобы вероятность провала теста на большом значении отличалась от такой же вероятности на маленьком. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 16:13 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovЕсли из-за числа, которое оказалось составным, происходит облом при расшифровании, то почему нельзя проверять это число, одновременно с тестом простоты, в режиме шифрование-расшифрование. Проверка будет проходить на небольшом тесте. Это займёт немного времени.Ну тут ровно так же, как с тестом простоты. На каком-то значении шифрование-дешифрование может пройти, а на другом нет. Шифруется в RSA некоторое большое число, обычно сессионный ключ. Если тест Ферма на этом числе пройдет, то и дешифрование сработает. Конечно, тесты обычно прогоняют на маленьких значениях, но нет никаких причин, чтобы вероятность провала теста на большом значении отличалась от такой же вероятности на маленьком.Тут ещё одна идея. Если всё равно каждое число проверяется на шифровании-дешифровании, то зачем нужен тест простоты? На что больше тратится время: на тест или на Ш-Д? Вот такие мысли ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 18:44 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneпропущено... Ну тут ровно так же, как с тестом простоты. На каком-то значении шифрование-дешифрование может пройти, а на другом нет. Шифруется в RSA некоторое большое число, обычно сессионный ключ. Если тест Ферма на этом числе пройдет, то и дешифрование сработает. Конечно, тесты обычно прогоняют на маленьких значениях, но нет никаких причин, чтобы вероятность провала теста на большом значении отличалась от такой же вероятности на маленьком.Тут ещё одна идея. Если всё равно каждое число проверяется на шифровании-дешифровании, то зачем нужен тест простоты? На что больше тратится время: на тест или на Ш-Д? Вот такие мыслиТест быстрее. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 18:46 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Потому-что простых чисел меньше чем составных. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 18:46 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Но если поверка на Ш-ДШ отвергает какие-то числа, то есть приходится к нему подключаться, значит, тест простоты "пропускает"? И проверка на Ш-ДШ является свого рода зачисткой огрехов теста простоты. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 18:59 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy Usovзначит, тест простоты "пропускает"? Да, и это обсуждали уже 21835979 ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 19:02 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Так ещё одна идея: пусть различные шифры "выплёвывают" очередные простые числа. Если эти шифры "поставить" на диапазон, то сразу все простые числа найдем в этом диапозоне. Только непонятно, для чего это нужно, если уже случайное число в этом диапазоне для криптографии "нашли полчаса назад". ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 19:05 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovТак ещё одна идея: пусть различные шифры "выплёвывают" очередные простые числа. Если эти шифры "поставить" на диапазон, то сразу все простые числа найдем в этом диапозоне. Геннадий мы все время крутимся вокруг "найти". Вот вы нашли. И что дальше? Куда вы его положите? Мы уже считали что числа больше чем 64х бит хранить физически негде. У нас нет носителей информации для этого. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 19:16 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovТолько непонятно, для чего это нужно, если уже случайное число в этом диапазоне для криптографии "нашли полчаса назад". Нашли два числа, перемножили, результат всем показали, а числа тут же забыли. Числа нигде не сохраняются, никому не показываются, только произведение. Понятно? ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 19:29 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Dima TGennadiy UsovТолько непонятно, для чего это нужно, если уже случайное число в этом диапазоне для криптографии "нашли полчаса назад".Нашли два числа, перемножили, результат всем показали, а числа тут же забыли. Числа нигде не сохраняются, никому не показываются, только произведение. Понятно?Понятно. Была идея, что возможны составные числа, раз тест простоты "пропускает". Однако выяснили, что шифр за тестом простоты всё "подчищает". Была идея, формировать составные числа, раз тест простоты их "пропускает". Однако то, из чего их формировать, надо где-то хранить. Так что беседа была интересной ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 19:45 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
С другой стороны, в районе 2^1024 или 2^2048 количество простых чисел на "километр", то есть на диапазон, очень мало. Как же так, что произвольно выбранное случайное число точно попадает на простое число? Фантастика! ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 19:50 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovС другой стороны, в районе 2^1024 или 2^2048 количество простых чисел на "километр", то есть на диапазон, очень мало. Как же так, что произвольно выбранное случайное число точно попадает на простое число? Фантастика!Не попадает. Приводили же куски кода, идет перебор до ближайшего простого. Да, из 1024 бит младшие ~10 в результате оказываются не случайными. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 20:34 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovС другой стороны, в районе 2^1024 или 2^2048 количество простых чисел на "километр", то есть на диапазон, очень мало. Как же так, что произвольно выбранное случайное число точно попадает на простое число? Фантастика!Не попадает. Приводили же куски кода, идет перебор до ближайшего простого. Да, из 1024 бит младшие ~10 в результате оказываются не случайными.Так сколько чисел в результате перебирают "до ближайшего простого"? 10 младших бит, это 1024 числа (вместе с чётными), это очень мало для 2^1024. Если уже в районе 1.0Е+15 диапазоны под 500 чисел. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 20:43 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Формула плотности простых на квадратный километр у нас есть. Можем примерно прикинуть сколько простых в диапазоне 2^4096 ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 20:49 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonФормула плотности простых на квадратный километр у нас есть. Можем примерно прикинуть сколько простых в диапазоне 2^4096По этой формуле 10-ти младших бит не хватит. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 20:53 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovBarloneпропущено... Не попадает. Приводили же куски кода, идет перебор до ближайшего простого. Да, из 1024 бит младшие ~10 в результате оказываются не случайными.Так сколько чисел в результате перебирают "до ближайшего простого"? 10 младших бит, это 1024 числа (вместе с чётными), это очень мало для 2^1024. Если уже в районе 1.0Е+15 диапазоны под 500 чисел.Ну если не повезло, то можно попасть в большой интервал. Но в среднем в районе 2^1024 одно простое на 710 чисел. В районе 2^4096 соответственно одно на 2840. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 21:06 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy Usovпропущено... Так сколько чисел в результате перебирают "до ближайшего простого"? 10 младших бит, это 1024 числа (вместе с чётными), это очень мало для 2^1024. Если уже в районе 1.0Е+15 диапазоны под 500 чисел.Ну если не повезло, то можно попасть в большой интервал. Но в среднем в районе 2^1024 одно простое на 710 чисел. В районе 2^4096 соответственно одно на 2840. Субъективно генерация RSA ключей занимает несколько секунд. Не минут это точно. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 21:15 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovБыла идея, что возможны составные числа, раз тест простоты "пропускает". Однако выяснили, что шифр за тестом простоты всё "подчищает". И что непонятно? Надо найти два простых числа и перемножить, тогда шифрование работает. Если одно из найденных окажется непростое, то шифрование не работает. ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 21:29 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Ну... я так понимаю что мифы разрушены. Все точки над i поставлены. И топик вобщем не нужен. P.S. Cartago delenda est ... |
|||
:
Нравится:
Не нравится:
|
|||
20.03.2019, 22:36 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
maytonНу... я так понимаю что мифы разрушены. Все точки над i поставлены. И топик вобщем не нужен. P.S. Cartago delenda est Наверное есть смысл подвести некоторые итоги... 1.Шифр RSA - это "тест простоты", который является более сильным по сравнению с общеизвестными тестами простоты. Я говорю про шифры, которые применяют два простых числа. Говорить, что он является "формулой" для поиска простых чисел на диапазоне, пока, наверное, рано. Но всё равно, в дальнейшем, будем считать, что шифр определяет простые числа. 2.При этом, шифр определяет одновременно не одно простое число, а два простых числа. 3.Шифр ищет простое число в некотором диапазоне от случайного числа в три этапа. 4.На первом этапе "отбрасываются" составные числа либо с помощью деления на небольшой перечень младших простых чисел либо с помощью деления на числа 6хК+-1 5.На втором этапе "отбрасываются" составные числа с помощью определёного теста простоты (например, Миллера-Рабина). 6.На третьем этапе "отбрасывается" уже пара чисел, выбранных на первом и втором этапах, с помощью тестового шифрования-дешифрования. Получается, что шифр ищет одновременно два простых числа на двух разных диапазонах. Если ещё раз посмотреть на начальное сообщение топика: "лучше решать обратную задачу: найти критерии возможных псевдослучайных чисел, чтобы с помощью их выбирать нужные «случайные числа» для криптографии." то можно сказать, что данная гипотеза не имеет смысла. Как то так. Может быть я где-то не прав? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 07:11 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Кажется, ошибка в логике: Скорее всего, ищется одно простое число. А вторым для него будет заранее записанное проверенное простое число. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 09:10 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovКажется, ошибка в логике: Скорее всего, ищется одно простое число. А вторым для него будет заранее записанное проверенное простое число.Хреновый тест. Я уже говорил, берете вместо простого числа число Кармайкла - и дешифрование работает. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 09:41 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneGennadiy UsovКажется, ошибка в логике: Скорее всего, ищется одно простое число. А вторым для него будет заранее записанное проверенное простое число.Хреновый тест. Я уже говорил, берете вместо простого числа число Кармайкла - и дешифрование работает.Но число Кармайкла - составное число. Как его можно использовать в качестве простого числа в тесте Ш-ДШ? Ведь в шифре должны участвовать два простых числа. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 12:36 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Если нарисовать блок-схему работы алгоритма RSA мне кажется многие вопросы отпадут. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 12:44 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Чтобы RSA шифрование-дешифрование работало, нужны два таких числа p, q, чтобы для любого a выполнялось тождество: Код: plaintext
Код: plaintext
... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 12:52 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Числа Кармайкла не нужны не потому, что шифрование не работает, а потому, что маленькие сомножители проще найти. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 12:55 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovБыла идея, что возможны составные числа, раз тест простоты "пропускает". Однако выяснили, что шифр за тестом простоты всё "подчищает". Была идея, формировать составные числа, раз тест простоты их "пропускает". Однако то, из чего их формировать, надо где-то хранить. Про эти "идеи" уже недели две назад всё разжёвывалось. Но Геннадий же писатель, а не читатель. Gennadiy UsovС другой стороны, в районе 2^1024 или 2^2048 количество простых чисел на "километр", то есть на диапазон, очень мало. Как же так, что произвольно выбранное случайное число точно попадает на простое число? А ещё Геннадий очень торопится. Или ленится. То есть если бы не ленился (ну и тему читал, а не только писал), то давно бы сам всё посчитал и не выглядел бы ленивым торопыгой. Gennadiy UsovНо разработчики криптографики об этом не предупреждают. Просто сказали, что только простое число. А почему - промолчали. А здесь Геннадий выдаёт свою торопливость и лень за ошибку разработчиков криптографических решений. Это примерно как ковыряясь в носу заявлять, что кто-то пальцы мне толстыми сделал, глубоко не пролазят, враги во всём виноваты! В общем неконструктивно себя Геннадий ведёт. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 14:02 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneМожно еще пытаться сконструировать что-то из больше чем двух сомножителей, там все еще сложнее А какая разница - сколько простых в произведении, если факторизацию искать миллион лет? В смысле и числа Кармайклаи другие их виды, которые проходят тест на шифрование-дешифрование, представляют всё ту же сложность, но, возможно, делённую на 2,3,4 и т.д. При порядках в сотни и более деление на 2,3,4 не даст никакого приближения к реальным возможностям, как было больше миллиона лет, так и останется. Вот разве что есть какие-то закономерности, позволяющие быстрее проводить факторизацию чисел именно из 3,4,5 и т.д. простых. ЗЫ. Малые простые можно отбросить, ибо факторизацию на них можно простым перебором проверить ещё на стадии выбора секретного числа. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 14:08 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneДа проверяли же: до 2^64 ноль ошибок. Интересно. Проверка всех чисел до 2 64 будет длиться, видимо, не менее месяца, а скорее всего даже года, на кластере из 1000 ядер. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 14:10 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
вот интересно, а можно ли найти a и b исходя из такого соотношения q^2 - k1* ab = 1 + k2 *f где k1, k2, q, f известны, также известно разложение f на множители ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 14:21 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
Gennadiy UsovШифр RSA - это "тест простоты", который является более сильным по сравнению с общеизвестными тестами простоты. Не "более сильным", а "целевым". Он, в принципе, может давать false positive, но для последующего применения ключа это уже неважно. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 14:53 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
alex55555BarloneМожно еще пытаться сконструировать что-то из больше чем двух сомножителей, там все еще сложнее А какая разница - сколько простых в произведении, если факторизацию искать миллион лет? В смысле и числа Кармайклаи другие их виды, которые проходят тест на шифрование-дешифрование, представляют всё ту же сложность, но, возможно, делённую на 2,3,4 и т.д. При порядках в сотни и более деление на 2,3,4 не даст никакого приближения к реальным возможностям, как было больше миллиона лет, так и останется. Вот разве что есть какие-то закономерности, позволяющие быстрее проводить факторизацию чисел именно из 3,4,5 и т.д. простых. ЗЫ. Малые простые можно отбросить, ибо факторизацию на них можно простым перебором проверить ещё на стадии выбора секретного числа.Нет, не деление на 2-3-4. Сразу квадратный - кубический корень. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 14:56 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
kealon(Ruslan)вот интересно, а можно ли найти a и b исходя из такого соотношения q^2 - k1* ab = 1 + k2 *f где k1, k2, q, f известны, также известно разложение f на множителиПри чём тут разложение f на множители, если a*b (а не аb?) будет равно определённому числу при том, что k1, k2, q, f известны? Осталось перебирать а и "следить" за b, чтобы b - было целое число. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 15:17 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
kealon(Ruslan)вот интересно, а можно ли найти a и b исходя из такого соотношения q^2 - k1* ab = 1 + k2 *f где k1, k2, q, f известны, также известно разложение f на множители (q 2 -1-k2*f)/k1=ab k1 укладывается ab раз в q 2 -1-k2*f. Так же k1 укладывается a раз по b раз. Ну и далее исследуем какие-то преобразования над левой частью, типа если разделить на a или b, или ещё что. А зачем это надо? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 15:53 |
|
Послепятничная задачка. Криптография и случайное число
|
|||
---|---|---|---|
#18+
BarloneНет, не деление на 2-3-4. Сразу квадратный - кубический корень. А почему? Какая закономерность это обеспечивает? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.03.2019, 15:53 |
|
|
start [/forum/topic.php?all=1&fid=16&tid=1339973]: |
0ms |
get settings: |
10ms |
get forum list: |
15ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
42ms |
get topic data: |
12ms |
get forum data: |
3ms |
get page messages: |
150ms |
get tp. blocked users: |
2ms |
others: | 43ms |
total: | 285ms |
0 / 0 |