powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Послепятничная задачка. Криптография и случайное число
166 сообщений из 166, показаны все 7 страниц
Послепятничная задачка. Криптография и случайное число
    #39787257
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Если рассматривать алгоритм создания открытого и секретного ключей, то здесь выбираются два случайных простых числа.
https://ru.wikipedia.org/wiki/RSA
И здесь сразу противоречие: случайное и простое.
Это два разных числа, и вероятность того, что случайное число будет простым равно вероятности простого числа на некотором диапазоне.
Далее смотрим, а какое оно случайное простое число.
https://ru.wikipedia.org/wiki/Случайное_простое_число
И там читаем:
«Ввиду того, что тестирование простоты больших чисел требует существенных временных затрат, требование простоты получаемого числа часто ослабляют до сильной псевдопростоты по нескольким различным случайным основаниям.»
А далее:
делится это случайное число на 54 начальных простых чисел (отсекается 80% нечётных чисел) и выполняется тест Миллера-Рабина к раз по количеству к битов в числе (ещё надо понять, а сколько это операций вычислений).
Если находим, то вероятность к, что число простое.
И если нет, то ищется следующее число.

И сколько времени нужно искать это число?

По-видимому,
лучше решать обратную задачу:
найти критерии возможных псевдослучайных чисел, чтобы с помощью их выбирать нужные «случайные числа» для криптографии.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787264
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov,
взять базу простых чисел и случайным образом выбрать . Вот и будет случайное простое число
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787265
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
вадяGennadiy Usov,
взять базу простых чисел и случайным образом выбрать . Вот и будет случайное простое числоА на каком простом числе эта база заканчивается?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787271
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovА на каком простом числе эта база заканчивается?один из вариантов https://primes.utm.edu/lists/small/millions/
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787288
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
вадяGennadiy UsovА на каком простом числе эта база заканчивается?один из вариантов https://primes.utm.edu/lists/small/millions/ Сразу вопрос:
будет 100-ый миллион, миллиард, 10 миллиардов... Когда-то это закончится.
Когда?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787304
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usovбудет 100-ый миллион, миллиард, 10 миллиардов... Когда-то это закончится.
Когда?теория говорит о том, что числовой ряд бесконечен - значит ни когда.
на любое самое хитрое шифрование - всегда есть не нулевая возможность взлома - вопрос только во времени.
выбор за тобой
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787321
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
вадяGennadiy Usovбудет 100-ый миллион, миллиард, 10 миллиардов... Когда-то это закончится.
Когда?теория говорит о том, что числовой ряд бесконечен - значит ни когда.
на любое самое хитрое шифрование - всегда есть не нулевая возможность взлома - вопрос только во времени.
выбор за тобойПро шифрование ещё рано говорить. Мы говорим о базе простых чисел.

Так жду ответа - насколько велика в компьютере база простых чисел?
Где её предел?
То есть, количество простых чисел, начиная с 2.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787323
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovИ сколько времени нужно искать это число?
Долго. Именно поэтому генерация RSA ключа может длиться несколько секунд.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787328
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovТак жду ответа - насколько велика в компьютере база простых чисел?вопрос а сколько тебе надо? можешь запустить поиск и добавлять в базу, пока диск не заполнишь.
к примеру для mysql поле BIGINT может иметь значение 18 446 744 073 709 551 615, сколько до этого значения простых чисел - хз.
если исходить из моей ссылки со списком найденных
Код: plaintext
1.
2.
18 446 744 073 709 551 615
               982 451 653
то ещё дофига
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787336
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вадя,

не хз, а порядка N/ln(N)
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787338
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вадяGennadiy UsovТак жду ответа - насколько велика в компьютере база простых чисел?вопрос а сколько тебе надо? можешь запустить поиск и добавлять в базу, пока диск не заполнишь.
к примеру для mysql поле BIGINT может иметь значение 18 446 744 073 709 551 615, сколько до этого значения простых чисел - хз.
если исходить из моей ссылки со списком найденных
Код: plaintext
1.
2.
18 446 744 073 709 551 615
               982 451 653
то ещё дофигаЭто очень маленькое число, для криптографии нужно число в несколько сотен десятичных знаков.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787339
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
вадяGennadiy UsovТак жду ответа - насколько велика в компьютере база простых чисел?вопрос а сколько тебе надо? можешь запустить поиск и добавлять в базу, пока диск не заполнишь.
к примеру для mysql поле BIGINT может иметь значение 18 446 744 073 709 551 615, сколько до этого значения простых чисел - хз.
если исходить из моей ссылки со списком найденных
Код: plaintext
18 446 744 073 709 551 615 982 451 653
то ещё дофигаА дофига - это больше 1.0Е+40 или меньше?

И ещё вопрос - а сколько чисел "влезает" на компьютер?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787353
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я считал уже дисковые расходы на хранение
Всех 64 битных простых.

Могу найти ссылку.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787356
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Изопропилне хз, а порядка N/ln(N)это величины одного порядка
Gennadiy UsovИ ещё вопрос - а сколько чисел "влезает" на компьютер?смотря как хранить..
100 000 000 записей для субд это не много.
BarloneЭто очень маленькое число, для криптографии нужно число в несколько сотен десятичных знаков.ТС спрашивал от цифры 2....
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787387
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По оперативной памяти я приводил сравнительные расчеты здесь 21823126
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787395
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПо оперативной памятитак что такое 30гиг памяти по сравнению терабайтами дисков?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787407
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
вадяGennadiy UsovИ ещё вопрос - а сколько чисел "влезает" на компьютер?смотря как хранить..
100 000 000 записей для субд это не много.А если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787411
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovА если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать?это тоже не много. SSD в RAID5...
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787413
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По всем типам памяти я приведу картинку. Такое-себе напоминание. Не для программистов а для физиков-математиков и прочих
сочувствующих.



Реально мы можем складывать небольшой объем только в 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.

Поскольку драйвером этого топика является господин Усов. То я предлагаю сначала ответить ему.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787414
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вадяmaytonПо оперативной памятитак что такое 30гиг памяти по сравнению терабайтами дисков?
Читайте внимательно линк. Я там ответил на этот вопрос.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787415
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

mayton- (1) нужен-ли нам произвольный доступ к любому числу?

Gennadiy Usovвыбираются два случайных простых числа.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787417
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЧитайте внимательно линк. Я там ответил на этот вопрос.я внимательно прочитал...
я к тому что для ТС
Gennadiy UsovА если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787418
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вы хоть раз пробовали из базы данных выбрать случайную строку?
Это не так просто уверяю вас! У нас нет первичного ключа. У нас само число является
ключом к самому себе.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787420
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вадяmaytonЧитайте внимательно линк. Я там ответил на этот вопрос.я внимательно прочитал...
я к тому что для ТС
Gennadiy UsovА если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать?
Он - не программист. Он не знает многих вещей из программно аппаратной архитектуры.

Поэтому я отвечу. Не проблема обработать 1 триллион чисел. Проблема - сделать это быстро.
Тоесть придумать совокупность тех-средств (конфигурация) и алгоритмов чтобы наши запросы
(я еще не знаю какие) создали мягкую нагрузку на железо и выдали результат. И в разумное
время. До того как погаснет солнце.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787421
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вадяGennadiy UsovА если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать?это тоже не много. SSD в RAID5...
Это очень малое требование. Надо простое число порядка 2^1024 или примерно 10^307.
В диапазоне 2^1023 ... 2^1024 примерно 2^1013 или 10^304 простых чисел.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787424
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonВы хоть раз пробовали из базы данных выбрать случайную строку?
Это не так просто уверяю вас! У нас нет первичного ключа. У нас само число является
ключом к самому себе.можно и поле последовательного ключа поиметь. пожертвовав местом хранения. вопрос что выгоднее.
maytonПроблема - сделать это быстро.поэтому я и предложил RAID из SSD.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787425
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вадяmaytonВы хоть раз пробовали из базы данных выбрать случайную строку?
Это не так просто уверяю вас! У нас нет первичного ключа. У нас само число является
ключом к самому себе.можно и поле последовательного ключа поиметь. пожертвовав местом хранения. вопрос что выгоднее.
maytonПроблема - сделать это быстро.поэтому я и предложил RAID из SSD.
Да ты подожди предлагать. Это топик растет ногами из другого топика где
обсуждали факторизацию 2^2048.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787427
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Формула количества простых в диапазоне 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.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787530
Фотография Elic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonдля …математиковmayton10 ms : 10 ns = 100 000 : 1
Порядка сто тысяч к одному.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787768
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Мы ушли от темы топика.

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

О чём идёт речь.

В процессе нахождения больших случайных чисел выполняется тест Миллера-Рабина к раз по количеству к битов в числе.
(или любого другого теста)
При этом в какой-то момент случайное число, по версии теста, не имеет признаков составных чисел, и это число "назначается" простым числом.

Вопрос один:
а кто-нибудь пробовал на небольших числах (но на предельных значениях по количеству обнаруженных простых чисел) применить тест простоты, а потом сравнить это применение с обычным алгоритмом Эратосфена?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787776
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovВопрос один:
а кто-нибудь пробовал на небольших числах (но на предельных значениях по количеству обнаруженных простых чисел) применить тест простоты, а потом сравнить это применение с обычным алгоритмом Эратосфена?
Сравнить на предмет чего?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787783
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dima TGennadiy UsovВопрос один:
а кто-нибудь пробовал на небольших числах (но на предельных значениях по количеству обнаруженных простых чисел) применить тест простоты, а потом сравнить это применение с обычным алгоритмом Эратосфена?Сравнить на предмет чего?Например:
Тест показал, что число можно считать простым, а алгоритм Эратосфена (или любой перебор известных простых чисел) показал, что у этого случайного числа есть множители.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787785
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovDima Tпропущено...
Сравнить на предмет чего?Например:
Тест показал, что число можно считать простым, а алгоритм Эратосфена (или любой перебор известных простых чисел) показал, что у этого случайного числа есть множители.
Такое возможно, это в википедии написано.
Алгоритм Миллера-Рабина позволяет выполнять проверку за малое время и давать при этом достаточно малую вероятность того, что число на самом деле является составным
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787798
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dima TGennadiy UsovНапример:
Тест показал, что число можно считать простым, а алгоритм Эратосфена (или любой перебор известных простых чисел) показал, что у этого случайного числа есть множители.Такое возможно, это в википедии написано.
Алгоритм Миллера-Рабина позволяет выполнять проверку за малое время и давать при этом достаточно малую вероятность того, что число на самом деле является составнымЕсли это возможно, то сразу следующий вопрос:

а на каких порядках простых чисел может появиться такая ситуация ("простое число" не является простым числом)?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787804
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovDima Tпропущено...
Такое возможно, это в википедии написано.
пропущено...
Если это возможно, то сразу следующий вопрос:

а на каких порядках простых чисел может появиться такая ситуация ("простое число" не является простым числом)?
На маленьких. Псевдопростое число
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787805
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мы можем генерировать произвольные произведения известных нам простых.
И подавать их на вход Миллеру. И если где-то он даст сообщение о том-что число
простое - то мы засчитываем ошибку.

Далее - дело статистики. Только Миллер-Рабин имеет настроечные параметры.
С этим надо определится. В какой конфигурации настроек мы его будем тестить.
Тогда матрица отчота получистя многомерная.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787820
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dima TGennadiy UsovЕсли это возможно, то сразу следующий вопрос:
а на каких порядках простых чисел может появиться такая ситуация ("простое число" не является простым числом)?
На маленьких. Псевдопростое число Мало того, что наука изучает простые числа, но она ещё изучает и псевдопростые числа.

А где можно применить псевдопростые числа?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787864
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonМы можем генерировать произвольные произведения известных нам простых.
И подавать их на вход Миллеру. И если где-то он даст сообщение о том-что число
простое - то мы засчитываем ошибку.

Далее - дело статистики. Только Миллер-Рабин имеет настроечные параметры.
С этим надо определится. В какой конфигурации настроек мы его будем тестить.
Тогда матрица отчота получистя многомерная.Проверяли уже. Вот например https://oeis.org/A074773 в диапазоне до 5,5 триллионов есть целых 21 составное число, проходящее тест Миллера-Рабина по основаниям 2, 3, 5 и 7.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787877
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А еще говорят есть тест на псевдопростоту , для которого пока не нашли ни одного контрпримера
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787880
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarlonemaytonМы можем генерировать произвольные произведения известных нам простых.
И подавать их на вход Миллеру. И если где-то он даст сообщение о том-что число
простое - то мы засчитываем ошибку.
Далее - дело статистики. Только Миллер-Рабин имеет настроечные параметры.
С этим надо определится. В какой конфигурации настроек мы его будем тестить.
Тогда матрица отчота получистя многомерная.Проверяли уже. Вот например https://oeis.org/A074773 в диапазоне до 5,5 триллионов есть целых 21 составное число, проходящее тест Миллера-Рабина по основаниям 2, 3, 5 и 7.Интересная информация.

Я посмотрел на эти числа, и в них, кроме первого, 2 множителя, причем каждый из них "в районе" корня квадратного из этого числа.

Почему-то эти числа заканчиваются на 5537838510751 (13-й порядок).
А что далее?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787884
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneА еще говорят есть тест на псевдопростоту , для которого пока не нашли ни одного контрпримераА Вы задумывались о том, почему много тестов на простоту ?
Мне известно около 10 тестов.

Или так много простоты, что тесты со всеми не справляются?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787890
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneПроверяли уже. Вот например https://oeis.org/A074773 в диапазоне до 5,5 триллионов есть целых 21 составное число, проходящее тест Миллера-Рабина по основаниям 2, 3, 5 и 7.Посмотрел это сообщение подробно, и там оказалась ссылка на таблицу всех таких чисел до 2^64.

А их очень много...
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787891
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovПочему-то эти числа заканчиваются на 5537838510751 (13-й порядок).
А что далее?Немножко дальше заканчиваются https://oeis.org/A074773/a074773.txt
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787897
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneПроверяли уже. Вот например https://oeis.org/A074773 в диапазоне до 5,5 триллионов есть целых 21 составное число, проходящее тест Миллера-Рабина по основаниям 2, 3, 5 и 7.Посмотрел это сообщение подробно, и там оказалась ссылка на таблицу всех таких чисел до 2^64.

А их очень много...Ага, очень много... На примерно 4*10^17 простых приходится 16757 составных, проходящих 4 раунда теста. То есть у нас вероятность приблизительно одна двадцатипятитриллионная, что мы ошибочно примем составное число за простое.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787901
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
И сразу имеет место очередной вопрос:

Есть псевдопростые числа, которые подходят для криптографии.
Они являются составными числами, в которых 2 множителя, которые почти равны друг другу.

И есть другие составные числа, которые почти равны этим псевдопростым числам (один порядок).
И тоже состоят из двух множителей, которые почти равны друг другу.

Так почему эти составные числа нельзя использовать в криптографии?
Из-за ограничителя - теста простоты (очередного)?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787905
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneНа примерно 4*10^17 простых приходится 16757 составных, проходящих 4 раунда теста. То есть у нас вероятность приблизительно одна двадцатипятитриллионная, что мы ошибочно примем составное число за простое.А чем составное число плохо для криптографии?

Допустим, приняли составное число за простое ...

Что произойдет с шифрованием и дешифрованием?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787913
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovА чем составное число плохо для криптографии?

Допустим, приняли составное число за простое ...

Что произойдет с шифрованием и дешифрованием?
21820624
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787916
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovА чем составное число плохо для криптографии?
Допустим, приняли составное число за простое ...
Что произойдет с шифрованием и дешифрованием? 21820624 Допустим...

Но клиент не знает.
Система пропустила псевдослучайное число.
И что - облом,
и что делать клиенту, если не получилась расшифровка?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787924
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Что-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787933
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovПочему-то эти числа заканчиваются на 5537838510751 (13-й порядок).
А что далее?Немножко дальше заканчиваются https://oeis.org/A074773/a074773.txt Немного поизучал эту таблицу.

1 число – 10 знаков. Произведение первых двух множителей равно почти 4-м величинам третьего множителя.

8 чисел – 12 знаков. Первый множитель в четыре раза меньше второго множителя ( с точностью до 3)

15 чисел – 14 знаков. Первый множитель в два раза меньше второго множителя (с точностью до 1).

Далее много чисел – 15 знаков. Первый множитель в четыре раза меньше второго множителя ( с точностью до 3).

Далее - мала ячейка
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787935
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneЧто-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа.На каком этапе программы?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787942
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneЧто-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа.На каком этапе программы?
Я-бы по другому спросил. Алгорим ЭЦП будет нарушен если множителей будет не 2 а 3 ?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787950
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovНа каком этапе программы?Я-бы по другому спросил. Алгорим ЭЦП будет нарушен если множителей будет не 2 а 3 ?Зачем мелочиться.

А что если множителей для чисел, порядка 2^1024, будет 10, 20?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787952
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovА что если множителей для чисел, порядка 2^1024, будет 10, 20?
Видимо систему будет проще взломать.

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

Вы, Геннадий, конечно же про RSA не захотели почитать? А вдруг там есть ответ?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787984
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alex55555Gennadiy UsovА что если множителей для чисел, порядка 2^1024, будет 10, 20?
Видимо систему будет проще взломать.

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

Вы, Геннадий, конечно же про RSA не захотели почитать? А вдруг там есть ответ?
Если это так то всё равно нет чёткого осознания слабости ключа. Ключ создан.
Слабый он или нет - хз. Беря во внимание редкость этих лже-primes я-бы
сказал что мы зря беспокоимся.

Усов! Не беспокойтесь. Ребе и Миллер уверены в своей победе!
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787989
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonУсов! Не беспокойтесь. Ребе и Миллер уверены в своей победе!Я не понял:
Ребе и Миллер
или
Ребе Миллер?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787993
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Рабин == Рабинович == Раввин. Фамилия происходящая от духовного сана.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788006
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
alex55555Gennadiy UsovА что если множителей для чисел, порядка 2^1024, будет 10, 20?
Видимо систему будет проще взломать.

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

Вы, Геннадий, конечно же про RSA не захотели почитать? А вдруг там есть ответ?В вики записано:
"В основу криптографической системы с открытым ключом RSA положена сложность задачи факторизации произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования (обратной операции) за разумное время необходимо уметь вычислять функцию Эйлера от данного большого числа, для чего необходимо знать разложение числа на простые множители."

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

То есть, если множители небольшие ( по меркам 2^ 1024), то достаточно поработать с небольшими простыми числами.

Если число простое, то компьютер должен иметь массив простых чисел до, например корень.кв.(2^ 1024).
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788009
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я думаю что алгоритм генерации пары RSA имеет защиту от дурака и не позволяет генерить
тривиальные факторизации.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788021
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneЧто-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа.
21776823
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788034
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima TBarloneЧто-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа.
21776823
Он же параметризованный. Нужно сказать какие были значения случайного числа a.
Сколько было итераций.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788045
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да здесь я ошибся

10 ms = 0.010 mks = 0.000010 ms

Вот так правильно.

10 ns = 0.010 mks = 0.000010 ms

Десять наносекунд это одна десятитысячная милисекунды.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788083
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я тут под катом скопирую кусок промышленного кода. С любезного разрешения 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.
    /**
     * Returns {@code true} if this BigInteger is probably prime,
     * {@code false} if it's definitely composite.  If
     * {@code certainty} is ≤ 0, {@code true} is
     * returned.
     *
     * @param  certainty a measure of the uncertainty that the caller is
     *         willing to tolerate: if the call returns {@code true}
     *         the probability that this BigInteger is prime exceeds
     *         (1 - 1/2<sup>{@code certainty}</sup>).  The execution time of
     *         this method is proportional to the value of this parameter.
     * @return {@code true} if this BigInteger is probably prime,
     *         {@code false} if it's definitely composite.
     */
    public boolean isProbablePrime(int certainty) {
        if (certainty <= 0)
            return true;
        BigInteger w = this.abs();
        if (w.equals(TWO))
            return true;
        if (!w.testBit(0) || w.equals(ONE))
            return false;

        return w.primeToCertainty(certainty, null);
    }



Следующи уровень в стеке - расчет раундов. В конце Миллер-Рабин работает в паре с Люка-Лемером. В коньюнкции.
Они как-бы друг друга проверяют. Забавно что Миллер параметризуется случайным числом. А Люка не параметризуется.
Код: 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.
    /**
     * Returns {@code true} if this BigInteger is probably prime,
     * {@code false} if it's definitely composite.
     *
     * This method assumes bitLength > 2.
     *
     * @param  certainty a measure of the uncertainty that the caller is
     *         willing to tolerate: if the call returns {@code true}
     *         the probability that this BigInteger is prime exceeds
     *         {@code (1 - 1/2<sup>certainty</sup>)}.  The execution time of
     *         this method is proportional to the value of this parameter.
     * @return {@code true} if this BigInteger is probably prime,
     *         {@code false} if it's definitely composite.
     */
    boolean primeToCertainty(int certainty, Random random) {
        int rounds = 0;
        int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;

        // The relationship between the certainty and the number of rounds
        // we perform is given in the draft standard ANSI X9.80, "PRIME
        // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
        int sizeInBits = this.bitLength();
        if (sizeInBits < 100) {
            rounds = 50;
            rounds = n < rounds ? n : rounds;
            return passesMillerRabin(rounds, random);
        }

        if (sizeInBits < 256) {
            rounds = 27;
        } else if (sizeInBits < 512) {
            rounds = 15;
        } else if (sizeInBits < 768) {
            rounds = 8;
        } else if (sizeInBits < 1024) {
            rounds = 4;
        } else {
            rounds = 2;
        }
        rounds = n < rounds ? n : rounds;

        return passesMillerRabin(rounds, random) && passesLucasLehmer();
    }



Само туловище Миллера я копировать не буду. Вроде-бы есть уже пища для размышлений.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788089
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonGennadiy Usovпропущено...
На каком этапе программы?
Я-бы по другому спросил. Алгорим ЭЦП будет нарушен если множителей будет не 2 а 3 ?Нам нужно знать функцию Эйлера для произведения. Если известно разложение на простые множители m=p*q, то
φ(m) = φ(p)*φ(q) = (p-1)*(q-1)

А если разложение на простые множители неизвестно, то найти значение этой функции сложно.

RSA основывается на теореме Эйлера :
Код: plaintext
  a φ(m)  = 1 (mod m)

Ну а дальше из свойств степени: нашли i,j такие что
Код: plaintext
i*j = k*φ(m)+1

Пара i,m - открытый ключ, пара j,m - секретный. Шифрование - возведение в степень i по модулю m, расшифровка - возведение результата шифрования в степень j по модулю m.

Код: plaintext
(a i ) j  (mod m) = a i*j  (mod m) = a k*φ(m)+1  (mod m) = a k*φ(m)  * a (mod m) = (a φ(m) ) k  * a (mod m) = 1 k  * a (mod m) = a
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788147
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Теорема Эйлера в теории чисел гласит:
Если a и m взаимно просты, то ....

Это не означает, что a и m - простые числа.

Может быть здесь посмотреть?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788153
Фотография Elic
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonВот так правильно.

10 ns = 0.010 mks = 0.000010 ms

Десять наносекунд это одна десятитысячная милисекунды.Я так понимаю, здесь всем начхать, какую вежливую божью росу несут другие?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788157
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonДесять наносекунд это одна десятитысячная милисекунды.Теперь я позанудствую: 9 - 1- 3 = 5.
Одна стотысячная", Карл!"
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788179
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну и ладно. Спасибо за фикс.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788181
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonDima Tпропущено...

21776823
Он же параметризованный. Нужно сказать какие были значения случайного числа a.
Сколько было итераций.
Глубоко не вникал, в инете нашел исходник. Похоже студенческая поделка попалась.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788185
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovТеорема Эйлера в теории чисел гласит:
Если a и m взаимно просты, то ....

Это не означает, что a и m - простые числа.

Может быть здесь посмотреть?Что посмотреть?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788206
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovЕсли число простое, то компьютер должен иметь массив простых чисел до, например корень.кв.(2^ 1024).
сколько простых чисел в этом интервале?
авторДля сравнения — количество атомов в наблюдаемой Вселенной составляет по разным оценкам от 4*10^79 до 10^81
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788261
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovТеорема Эйлера в теории чисел гласит:
Если a и m взаимно просты, то ....

Это не означает, что a и m - простые числа.

Может быть здесь посмотреть?
У меня тоже был некоторый лингвистический ступор. Представил себе сумму или разность двух рациональных чисел.
Если знаменатели просто перемножаются - то взаимнопростые.

Чуть позже написал такое.

Код: sql
1.
def mutuallySimple(a: Int, b: Int): Boolean = gcd(a,b) == 1
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788348
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovТеорема Эйлера в теории чисел гласит:
Если a и m взаимно просты, то ....
Это не означает, что a и m - простые числа.
Может быть здесь посмотреть?Что посмотреть?Использование в методе двух взаимно простых чисел вместо двух простых чисел
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788362
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По аналогии со скатертью Улама. Я думаю неплохо-бы нарисовать на 2д плоскости
пары взаимно-простых чисел. И туда--же докидать еще каких-то чисел-редких-исключений.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788369
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonПо аналогии со скатертью Улама. Я думаю неплохо-бы нарисовать на 2д плоскости
пары взаимно-простых чисел. И туда--же докидать еще каких-то чисел-редких-исключений.Таких чисел (взаимно простых) можно наделать очень много
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788370
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneпропущено...
Что посмотреть?Использование в методе двух взаимно простых чисел вместо двух простых чиселВ каком методе? Если вы взяли большое случайное число, и оно оказалось составным, то вы для него функцию Эйлера не знаете.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788375
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
На этом и строится RSA - владелец секретного ключа знает функцию Эйлера для произведения двух больших простых чисел, потому что он эти множители сгенерировал, а никто другой, зная произведение, но не зная сомножителей, вычислить ее не может.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788397
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovИспользование в методе двух взаимно простых чисел вместо двух простых чиселВ каком методе? Если вы взяли большое случайное число, и оно оказалось составным, то вы для него функцию Эйлера не знаете.Почему не знаю?

Если я сам составлял составное (псевдопростое) число, то я и знаю, сколько в этом числе множителей
(Функция Эйлера — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним).
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788402
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovЕсли я сам составлял составное (псевдопростое) число, то я и знаю, сколько в этом числе множителей
(Функция Эйлера — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним).
Вы уж как-то определитесь...
Gennadiy UsovА чем составное число плохо для криптографии?

Допустим, приняли составное число за простое ...

Что произойдет с шифрованием и дешифрованием?То ли приняли составное число за простое, то ли специально взяли больше множителей.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788408
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovЕсли я сам составлял составное (псевдопростое) число, то я и знаю, сколько в этом числе множителей
(Функция Эйлера — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним).Вы уж как-то определитесь...
Gennadiy UsovА чем составное число плохо для криптографии?
Допустим, приняли составное число за простое ...
Что произойдет с шифрованием и дешифрованием?То ли приняли составное число за простое, то ли специально взяли больше множителей.А здесь приведены две выборки по одному и тому же вопросу: применение псевдопростых (составных) чисел в вопросах криптографии.
Так что и не надо определяться.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788409
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneпропущено...
В каком методе? Если вы взяли большое случайное число, и оно оказалось составным, то вы для него функцию Эйлера не знаете.Почему не знаю?

Если я сам составлял составное (псевдопростое) число, то я и знаю, сколько в этом числе множителей
(Функция Эйлера — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним).
Барлон имеет в виду что в протоколе секретной переписки между Алисой и Бобом каждый владеет своим секретным
ключом и никому его не передает. Публичная часть - публикуется для осуществления переписки.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788415
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonБарлон имеет в виду что в протоколе секретной переписки между Алисой и Бобом каждый владеет своим секретным
ключом и никому его не передает. Публичная часть - публикуется для осуществления переписки.У каждого будет свой секретный ключ.
Только он будет формироваться несколько по иному.

Главное - это возможность использования составных (взаимно простых) чисел.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788416
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneпропущено...
Вы уж как-то определитесь...
пропущено...
То ли приняли составное число за простое, то ли специально взяли больше множителей.А здесь приведены две выборки по одному и тому же вопросу: применение псевдопростых (составных) чисел в вопросах криптографии.
Так что и не надо определяться.Составное число, для которого мы знаем разложение на простые, и составное число, для которого не знаем разложение на простые - это два разных вопроса, на которые есть два разных ответа.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788419
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneСоставное число, для которого мы знаем разложение на простые, и составное число, для которого не знаем разложение на простые - это два разных вопроса, на которые есть два разных ответа.Пока я не вижу в этом разницы. Нужен пример.

А перечень общеизвестных псевдопростых чисел, который был опубликован на данном топике, имеет по 2 множителя, и вроде эти числа применяют.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788431
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonБарлон имеет в виду что в протоколе секретной переписки между Алисой и Бобом каждый владеет своим секретным
ключом и никому его не передает. Публичная часть - публикуется для осуществления переписки.Ну в принципе для шифрования достаточно одного секретного ключа. Боб генерирует случайный сессионный ключ, шифрует на открытом ключе Алисы, и передает зашифрованным по открытому каналу. Алиса расшифровывает его своим секретным ключом. Теперь у обоих есть сессионный ключ, которым они шифруют дальнейший обмен обычным симметричным алгоритмом.
Секретный ключ Боба нужен только для проверки Алисой, что к ней обращается действительно Боб.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788439
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovПока я не вижу в этом разницы. Нужен пример.
Какой? Вот такой пойдет?
124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099

составное число, что можно проверить тестом Миллера-Рабина. Попробуйте найти для него функцию Эйлера.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788460
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПо аналогии со скатертью Улама. Я думаю неплохо-бы нарисовать на 2д плоскости
пары взаимно-простых чисел. И туда--же докидать еще каких-то чисел-редких-исключений.
Нарисовал.

Красный - пара координат - взаимно-простые.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788472
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Barlone,

я думаю пойдёт, но для осознания масштаба помогают цифры в баксах которые выплачивались за это дело
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788535
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovПока я не вижу в этом разницы. Нужен пример.
Какой? Вот такой пойдет?
124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099
составное число, что можно проверить тестом Миллера-Рабина. Попробуйте найти для него функцию Эйлера.Нужен пример не числа, а того, что именно составное число не подошло для криптографики.

Что помешало именно этому составному числу быть "полезным" криптографии?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788537
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonmaytonПо аналогии со скатертью Улама. Я думаю неплохо-бы нарисовать на 2д плоскости пары взаимно-простых чисел. И туда--же докидать еще каких-то чисел-редких-исключений.Нарисовал.
Красный - пара координат - взаимно-простые.Красивая картинка.
Неплохо бы её применить в народном хозяйстве.

Но взаимно-простые числа могут иметь несколько пересечений:
для одного числа имеется множество взаимно-простых.

Ведь и число 2 есть взаимно-простое число со всеми нечетными числами.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788538
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovЧто помешало именно этому составному числу быть "полезным" криптографии?
Если ключами на основе составного числа зашифровать, а потом расшифровать, то в итоге получится не то что зашифровали.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788541
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovНужен пример не числа, а того, что именно составное число не подошло для криптографики.

Что помешало именно этому составному числу быть "полезным" криптографии?Так именно незнание φ и мешает
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788548
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovНужен пример не числа, а того, что именно составное число не подошло для криптографики.
Что помешало именно этому составному числу быть "полезным" криптографии?Так именно незнание φ и мешаетВ той талице псевдослучайных чисел два множителя для большинства чисел.
Следовательно, если это число р, то φ для одного числа р будет равно (р-3).
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788550
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovВ той талице псевдослучайных чисел два множителя для большинства чисел.
Следовательно, если это число р, то φ для одного числа р будет равно (р-3).Нет конечно, никак не p-3
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788601
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovВ той талице псевдослучайных чисел два множителя для большинства чисел.
Следовательно, если это число р, то φ дляоднφого числа р будет равно (р-3).Нет конечно, никак не p-3Обычно в таких случаях говорят - чему равно это значение.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788621
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneпропущено...
Нет конечно, никак не p-3Обычно в таких случаях говорят - чему равно это значение.Так было уже 21836602
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788631
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneТак было уже 21836602 Следовательно, если формула для двух составных чисел p и q, каждое из которых состоит из двух множителей, то имеем (p-3)*(q-3)
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788634
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneТак было уже 21836602 Следовательно, если формула для двух составных чисел p и q, каждое из которых состоит из двух множителей, то имеем (p-3)*(q-3)Нет конечно. (p-1)*(q-1) никак не равно p*q-3
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788636
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Там еще ссылка в википедию была, сходите почитайте. φ от произведения четырех сомножителей равно произведению четырех φ (от каждого из сомножителей).
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788661
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneТам еще ссылка в википедию была, сходите почитайте. φ от произведения четырех сомножителей равно произведению четырех φ (от каждого из сомножителей).У меня не 4 сомножителя, а 2 сомножителя, каждый из которых имеет только два множителя.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788667
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneТам еще ссылка в википедию была, сходите почитайте. φ от произведения четырех сомножителей равно произведению четырех φ (от каждого из сомножителей).У меня не 4 сомножителя, а 2 сомножителя, каждый из которых имеет только два множителя.
Мне кажется ты на основе свойств функции Эйлера "продавливаешь" свою гипотезу.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788670
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovУ меня не 4 сомножителя, а 2 сомножителя, каждый из которых имеет только два множителя.Что? И где разница между четыре и два раза по два?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788823
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonМне кажется ты на основе свойств функции Эйлера "продавливаешь" свою гипотезу.Да, несколько дней назад это было гипотезой.
А сейчас – это уже более серьёзное утверждение.

Неужели вы не замечаете кучу нестыковок в теории шифрования с помощью простых чисел?

1.Все говорят, 2^1024, простые числа, простые числа, бла, бла, бла, а это число около 1,0Е+300.
В то же время платят большие деньги, чтобы найти множители для чисел в районе 130 десятичных знаков и более.kealon(Ruslan)Barlone,я думаю пойдёт, но для осознания масштаба помогают цифры в баксах которые выплачивались за это делоТак какие числа находят тесты простоты?

Я пока не говорю про 2^2048.

2.Много тестов простоты, и ни один из них не повторяет другого.
Это говорит о том, что каждый тест «охватывает» (или находит) определённое количество составных чисел.
Но составных чисел очень и очень много, следовательно, и тестов простоты должно быть тоже много.
Если следовать этой теории, то существующие тесты простоты «охватывают» небольшую часть составных чисел.
Оставшиеся составные числа охватывают ещё не найденные тесты простоты.

Поэтому можно сформулировать следующий вывод:

большое количество составных чисел после «пропускания» через тесты простоты «становятся» простыми числами.

И данные «простые» числа (псевдопростые числа) в большом количестве используются в криптографии!


Защитники простых чисел в криптографии – защищайтесь!
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788844
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovУ меня не 4 сомножителя, а 2 сомножителя, каждый из которых имеет только два множителя.Что? И где разница между четыре и два раза по два?Хотите сказать, что если есть два числа p и q, каждый из которых состоит из 2-х множителей:
p = a*b
q = c*d
то функция Эйлера будет равна:
f=(a-1)*(b-1)*(c-1)*(d-1)?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788918
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov,

если a,b,c,d не равны между собой и являются простыми числами то ДА
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788919
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneпропущено...
Что? И где разница между четыре и два раза по два?Хотите сказать, что если есть два числа p и q, каждый из которых состоит из 2-х множителей:
p = a*b
q = c*d
то функция Эйлера будет равна:
f=(a-1)*(b-1)*(c-1)*(d-1)?Да, если a,b,c,d - простые, причем разные.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788937
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonМне кажется ты на основе свойств функции Эйлера "продавливаешь" свою гипотезу.Да, несколько дней назад это было гипотезой.
А сейчас – это уже более серьёзное утверждение.

Неужели вы не замечаете кучу нестыковок в теории шифрования с помощью простых чисел?

Я не вижу никаких нестыковок. Я пока вижу в криптографии запас прочности еще на 10 лет.

Денежные премии за нахождение новых простых - это просто популяризация науки. Как с большой
теоремой Ферма.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788938
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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 - владелец секретного ключа знает функцию Эйлера для произведения двух больших простых чисел, потому что он эти множители сгенерировал, а никто другой, зная произведение, но не зная сомножителей, вычислить ее не может.Теперь можно сказать, что нам известна функция Эйлера?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788940
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovДа, несколько дней назад это было гипотезой.
А сейчас – это уже более серьёзное утверждение.
Неужели вы не замечаете кучу нестыковок в теории шифрования с помощью простых чисел?
Я не вижу никаких нестыковок. Я пока вижу в криптографии запас прочности еще на 10 лет.
Денежные премии за нахождение новых простых - это просто популяризация науки. Как с большой
теоремой Ферма.Как в том анекдоте: и ты говори..

Говорить можно что угодно,
и про запас, и про прочность, и про популяризацию, и про Ферма (очень сильный аргумент!), и про ....

А где ответы на два моих вопроса?

И конечно, Вы составных чисел не видите?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788951
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov1.Все говорят, 2^1024, простые числа, простые числа, бла, бла, бла, а это число около 1,0Е+300.
В то же время платят большие деньги, чтобы найти множители для чисел в районе 130 десятичных знаков и более.kealon(Ruslan)Barlone,я думаю пойдёт, но для осознания масштаба помогают цифры в баксах которые выплачивались за это делоТак какие числа находят тесты простоты?
Нет, не так. Эти числа сгенерированы как произведение двух "вероятно простых" (прошедших тесты) чисел. Призы выплачивались RSA Laboratories, разработчиком криптосистемы RSA, как доказательство надежности такого метода шифрования.


Gennadiy Usov2.Много тестов простоты, и ни один из них не повторяет другого.
Это говорит о том, что каждый тест «охватывает» (или находит) определённое количество составных чисел.
Ну не так много. Во-первых, есть тесты детерминированные (точно доказывающие простоту) и вероятностные (отсеивающие составные с какой-то вероятностью). Во-вторых, среди детерминированных есть медленные тесты для чисел специального вида (типа чисел Мерсенна) и очень медленные для произвольных чисел. Не те, не другие для криптографии не подходят - числа специального вида использовать нельзя, так как их мало, а для произвольных чисел скорость совершенно неприемлема - кому надо сутки генерировать секретный ключ? Поэтому используют вероятностные тесты. В основном Миллера-Рабина. Иногда в комбинации с Люка - 21836586 и 21836159 на самом деле это оно.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788952
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usovmaytonпропущено...
Я не вижу никаких нестыковок. Я пока вижу в криптографии запас прочности еще на 10 лет.
Денежные премии за нахождение новых простых - это просто популяризация науки. Как с большой
теоремой Ферма.Как в том анекдоте: и ты говори..

Говорить можно что угодно,
и про запас, и про прочность, и про популяризацию, и про Ферма (очень сильный аргумент!), и про ....

А где ответы на два моих вопроса?

И конечно, Вы составных чисел не видите?
Поэтому когда ты что-то критикуешь неконкретно - говори. Я Усов критикую Миллера-Рабина за нестрогость
и неправдоподобность.

Но реализация которую я приводил в качестве примера находится вне твоей критики поскольку она использует
совокупность НЕСКОЛЬКИХ алгоритмов которые ты еще пока не исследовал и незнаешь их вероятности ложно
позитивного срабатывания.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788962
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonПоэтому когда ты что-то критикуешь неконкретно - говори. Я Усов критикую Миллера-Рабина за нестрогость
и неправдоподобность.
Но реализация которую я приводил в качестве примера находится вне твоей критики поскольку она использует
совокупность НЕСКОЛЬКИХ алгоритмов которые ты еще пока не исследовал и незнаешь их вероятности ложно
позитивного срабатывания.Снова не то...

Я не критикую Миллера-Рабина, там всё прекрасно, проверено.
Но это тест только на составные числа. А дальше, допущение, что ...
Как Вы это не понимаете?

Мы же говорим о простых числах для криптографии.

А это, как известно, две разные вещи.

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

А дальше, ещё интересно.

Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные).
Вот интересно!

Почему молчит об этом Barlone?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788963
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy Usov1.Все говорят, 2^1024, простые числа, простые числа, бла, бла, бла, а это число около 1,0Е+300.
В то же время платят большие деньги, чтобы найти множители для чисел в районе 130 десятичных знаков и более.
Так какие числа находят тесты простоты?
Нет, не так. Эти числа сгенерированы как произведение двух "вероятно простых" (прошедших тесты) чисел. Призы выплачивались RSA Laboratories, разработчиком криптосистемы RSA, как доказательство надежности такого метода шифрования.Как тяжело просто сказать, что число может быть составным.
А так вероятно простое. И добавляется - прошедшее тест.

А почему бы не заплатить?
Это реклама надежности, тут деньги не считают.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788965
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovmaytonПоэтому когда ты что-то критикуешь неконкретно - говори. Я Усов критикую Миллера-Рабина за нестрогость
и неправдоподобность.
Но реализация которую я приводил в качестве примера находится вне твоей критики поскольку она использует
совокупность НЕСКОЛЬКИХ алгоритмов которые ты еще пока не исследовал и незнаешь их вероятности ложно
позитивного срабатывания.Снова не то...

Я не критикую Миллера-Рабина, там всё прекрасно, проверено.
Но это тест только на составные числа. А дальше, допущение, что ...
Как Вы это не понимаете?

Мы же говорим о простых числах для криптографии.

А это, как известно, две разные вещи.

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

А дальше, ещё интересно.

Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные).
Вот интересно!

Почему молчит об этом Barlone?
Мне сложно перечитывать взад все-все ваши гипотезы. Вы можете подытожить и изложить ваши сомнения
в виде пунктов?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788967
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovТогда надо честно сказать, что могут быть составные числа для криптографии.

А дальше, ещё интересно.

Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные).
Вот интересно!

Почему молчит об этом Barlone?Ну с практической точки зрения, это маловероятно. Но если допустим кто-то даже выпустит ssl сертификат с таким косяком, при попытке установить защищенное соединение будет случаться облом. И просто сделают новый сертификат, с другим ключом. Может даже не станут разбираться, из-за бага в программе получился кривой сертификат или случайно составное число проскочило.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788973
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Есть еще к примеру вероятность, что какой-нибудь мюон из космических лучей прилетит и испортит значение в ячейке памяти. А память с ECC далеко не везде стоит.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788978
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy Usov2.Много тестов простоты, и ни один из них не повторяет другого.
Это говорит о том, что каждый тест «охватывает» (или находит) определённое количество составных чисел.
Ну не так много. Во-первых, есть тесты детерминированные (точно доказывающие простоту) и вероятностные (отсеивающие составные с какой-то вероятностью). Во-вторых, среди детерминированных есть медленные тесты для чисел специального вида (типа чисел Мерсенна) и очень медленные для произвольных чисел. Не те, не другие для криптографии не подходят - числа специального вида использовать нельзя, так как их мало, а для произвольных чисел скорость совершенно неприемлема - кому надо сутки генерировать секретный ключ? Поэтому используют вероятностные тесты. В основном Миллера-Рабина. Иногда в комбинации с Люка - 21836586 и 21836159 на самом деле это оно.А Вы задумывались, почему их много (по Вашему - немного)?

Эти тесты друг друга не повторяют!
Разная математика, и следовательно, рассматриваются разные последовательности чисел (так мне кажется!).

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

Кстати, а почему до сих пор нет сравнения на небольших числах для теста Миллера-Рабина для нахождения известных простых чисел?
(может быть и есть, но я не видел)
Разработчикам криптографики не хочется это показывать?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788982
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovТогда надо честно сказать, что могут быть составные числа для криптографии.
А дальше, ещё интересно.
Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные).
Вот интересно!Ну с практической точки зрения, это маловероятно. Но если допустим кто-то даже выпустит ssl сертификат с таким косяком, при попытке установить защищенное соединение будет случаться облом. И просто сделают новый сертификат, с другим ключом. Может даже не станут разбираться, из-за бага в программе получился кривой сертификат или случайно составное число проскочило.А вот здесь самое интересное.
Из-за составного числа, оказывается, может случиться облом (говорят, в расшифровке).
Но разработчики криптографики об этом не предупреждают.
Просто сказали, что только простое число.
А почему - промолчали.

И я не видел (может быть и есть) результов анализа применения (по ошибке) составных чисел.

А ведь если есть ограниченния, то сразу появляется куча статей. Сомневающихся хватает (на себя не указываю)
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788995
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovКстати, а почему до сих пор нет сравнения на небольших числах для теста Миллера-Рабина для нахождения известных простых чисел?
(может быть и есть, но я не видел)
Разработчикам криптографики не хочется это показывать?
На диапазоне до 4х миллиардов мы пожалуй можем это проверить.

Делайте ставки Усов. Сколько промахов даст Ребе Миллер с Люкой?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788996
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovА вот здесь самое интересное.
Из-за составного числа, оказывается, может случиться облом (говорят, в расшифровке).
Но разработчики криптографики об этом не предупреждают.
Просто сказали, что только простое число.
А почему - промолчали.Вообще-то, это известная особенность. Если вы об этом не знали - ну это ваши проблемы.
Если пользователь, не являющийся спецом, с таким столкнется - он не отличит результат от бага в программе. Ну пошлет он багрепорт разработчику - тот добавит пару раундов Рабина-Миллера, или прикрутит Люка, чтоб в ближайшие сто лет такое не повторялось.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39788999
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНа диапазоне до 4х миллиардов мы пожалуй можем это проверить.

Делайте ставки Усов. Сколько промахов даст Ребе Миллер с Люкой?Да проверяли же: до 2^64 ноль ошибок.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789001
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovКстати, а почему до сих пор нет сравнения на небольших числах для теста Миллера-Рабина для нахождения известных простых чисел?
(может быть и есть, но я не видел)
Разработчикам криптографики не хочется это показывать?На диапазоне до 4х миллиардов мы пожалуй можем это проверить.
Делайте ставки Усов. Сколько промахов даст Ребе Миллер с Люкой?Если такой тест будет, то интересно рассмотреть интервал между двумя последовательными простыми числами (нечётные числа).

Я бы поставил на 10%.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789004
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarlonemaytonНа диапазоне до 4х миллиардов мы пожалуй можем это проверить.
Делайте ставки Усов. Сколько промахов даст Ребе Миллер с Люкой?Да проверяли же: до 2^64 ноль ошибок.Есть ссылка?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789017
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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 я местами потыкался - все попадают произведения двух (хотя у меня поначалу было подозрение, что там должно быть еще некоторое количество чисел Кармайкла кроме первого).
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789020
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneпропущено...
Да проверяли же: до 2^64 ноль ошибок.Есть ссылка?Да давал уже - https://ru.wikipedia.org/wiki/Тест_Бейли_—_Померанца_—_Селфриджа_—_Уогстаффа
Кстати, о "много тестов простоты". Взяли комбинацию Миллера-Рабина и Люка, и дали новое название...
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789028
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovЭти тесты друг друга не повторяют!
Разная математика, и следовательно, рассматриваются разные последовательности чисел (так мне кажется!).
Да одинаковая там математика, везде считают порядок группы.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789084
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovНо разработчики криптографики об этом не предупреждают.
О чём предупреждать-то? В системах генерации RSA ключей есть финальная проверка на корректность их работы. Если шифрование-дешифрование с их помощью не прошло корректно, ключи выкидывается на помойку и генерируются новые.
И, главное, кого предупреждать-то? Разработчики это и так знают, а для пользователей - см. выше.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789124
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovТогда надо честно сказать, что могут быть составные числа для криптографии.
А дальше, ещё интересно.
Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные).Вот интересно!Ну с практической точки зрения, это маловероятно. Но если допустим кто-то даже выпустит ssl сертификат с таким косяком, при попытке установить защищенное соединение будет случаться облом. И просто сделают новый сертификат, с другим ключом. Может даже не станут разбираться, из-за бага в программе получился кривой сертификат или случайно составное число проскочило.Теперь у меня ещё одна идея.

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

Это займёт немного времени.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789127
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonGennadiy UsovЯ не критикую Миллера-Рабина, там всё прекрасно, проверено.
Но это тест только на составные числа. А дальше, допущение, что ...
Мы же говорим о простых числах для криптографии.
А это, как известно, две разные вещи.
Тогда надо честно сказать, что могут быть составные числа для криптографии.
А дальше, ещё интересно.
Используем составные числа в криптографии с ошибочным значением функции Эйлера (сомножители не простые, а составные).Мне сложно перечитывать взад все-все ваши гипотезы. Вы можете подытожить и изложить ваши сомнения
в виде пунктов?На самом деле гипотеза у меня пока одна:

имеет место большое количество составных чисел, которые после «пропускания» через тесты простоты «становятся» простыми числами.

Всё остальное - это следствие данной гипотезы.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789130
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Gennadiy UsovТеперь у меня ещё одна идея.
Если из-за числа, которое оказалось составным, происходит облом при расшифровании,
то почему нельзя проверять это число, одновременно с тестом простоты, в режиме шифрование-расшифрование.
Проверка будет проходить на небольшом тесте.
Это займёт немного времени.Пропустил предыдущее сообщение, а там есть ссылка на такую проверку, которая уже имеет место.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789148
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneпропущено...
Ну с практической точки зрения, это маловероятно. Но если допустим кто-то даже выпустит ssl сертификат с таким косяком, при попытке установить защищенное соединение будет случаться облом. И просто сделают новый сертификат, с другим ключом. Может даже не станут разбираться, из-за бага в программе получился кривой сертификат или случайно составное число проскочило.Теперь у меня ещё одна идея.

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

Это займёт немного времени.Ну тут ровно так же, как с тестом простоты. На каком-то значении шифрование-дешифрование может пройти, а на другом нет. Шифруется в RSA некоторое большое число, обычно сессионный ключ. Если тест Ферма на этом числе пройдет, то и дешифрование сработает. Конечно, тесты обычно прогоняют на маленьких значениях, но нет никаких причин, чтобы вероятность провала теста на большом значении отличалась от такой же вероятности на маленьком.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789214
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovЕсли из-за числа, которое оказалось составным, происходит облом при расшифровании,
то почему нельзя проверять это число, одновременно с тестом простоты, в режиме шифрование-расшифрование.
Проверка будет проходить на небольшом тесте.
Это займёт немного времени.Ну тут ровно так же, как с тестом простоты. На каком-то значении шифрование-дешифрование может пройти, а на другом нет. Шифруется в RSA некоторое большое число, обычно сессионный ключ. Если тест Ферма на этом числе пройдет, то и дешифрование сработает. Конечно, тесты обычно прогоняют на маленьких значениях, но нет никаких причин, чтобы вероятность провала теста на большом значении отличалась от такой же вероятности на маленьком.Тут ещё одна идея.

Если всё равно каждое число проверяется на шифровании-дешифровании, то зачем нужен тест простоты?

На что больше тратится время: на тест или на Ш-Д?

Вот такие мысли
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789215
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneпропущено...
Ну тут ровно так же, как с тестом простоты. На каком-то значении шифрование-дешифрование может пройти, а на другом нет. Шифруется в RSA некоторое большое число, обычно сессионный ключ. Если тест Ферма на этом числе пройдет, то и дешифрование сработает. Конечно, тесты обычно прогоняют на маленьких значениях, но нет никаких причин, чтобы вероятность провала теста на большом значении отличалась от такой же вероятности на маленьком.Тут ещё одна идея.

Если всё равно каждое число проверяется на шифровании-дешифровании, то зачем нужен тест простоты?

На что больше тратится время: на тест или на Ш-Д?

Вот такие мыслиТест быстрее.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789216
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Потому-что простых чисел меньше чем составных.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789223
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Но если поверка на Ш-ДШ отвергает какие-то числа, то есть приходится к нему подключаться, значит, тест простоты "пропускает"?

И проверка на Ш-ДШ является свого рода зачисткой огрехов теста простоты.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789224
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usovзначит, тест простоты "пропускает"?
Да, и это обсуждали уже 21835979
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789225
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Так ещё одна идея:

пусть различные шифры "выплёвывают" очередные простые числа.

Если эти шифры "поставить" на диапазон, то сразу все простые числа найдем в этом диапозоне.

Только непонятно, для чего это нужно, если уже случайное число в этом диапазоне для криптографии "нашли полчаса назад".
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789227
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovТак ещё одна идея:

пусть различные шифры "выплёвывают" очередные простые числа.

Если эти шифры "поставить" на диапазон, то сразу все простые числа найдем в этом диапозоне.
Геннадий мы все время крутимся вокруг "найти".

Вот вы нашли. И что дальше? Куда вы его положите? Мы уже считали что числа больше чем 64х бит
хранить физически негде. У нас нет носителей информации для этого.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789233
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovТолько непонятно, для чего это нужно, если уже случайное число в этом диапазоне для криптографии "нашли полчаса назад".
Нашли два числа, перемножили, результат всем показали, а числа тут же забыли. Числа нигде не сохраняются, никому не показываются, только произведение. Понятно?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789241
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Dima TGennadiy UsovТолько непонятно, для чего это нужно, если уже случайное число в этом диапазоне для криптографии "нашли полчаса назад".Нашли два числа, перемножили, результат всем показали, а числа тут же забыли. Числа нигде не сохраняются, никому не показываются, только произведение. Понятно?Понятно.

Была идея, что возможны составные числа, раз тест простоты "пропускает".
Однако выяснили, что шифр за тестом простоты всё "подчищает".

Была идея, формировать составные числа, раз тест простоты их "пропускает".
Однако то, из чего их формировать, надо где-то хранить.

Так что беседа была интересной
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789243
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
С другой стороны, в районе 2^1024 или 2^2048 количество простых чисел на "километр", то есть на диапазон, очень мало.

Как же так, что произвольно выбранное случайное число точно попадает на простое число?

Фантастика!
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789252
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovС другой стороны, в районе 2^1024 или 2^2048 количество простых чисел на "километр", то есть на диапазон, очень мало.

Как же так, что произвольно выбранное случайное число точно попадает на простое число?

Фантастика!Не попадает. Приводили же куски кода, идет перебор до ближайшего простого. Да, из 1024 бит младшие ~10 в результате оказываются не случайными.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789255
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovС другой стороны, в районе 2^1024 или 2^2048 количество простых чисел на "километр", то есть на диапазон, очень мало.
Как же так, что произвольно выбранное случайное число точно попадает на простое число?
Фантастика!Не попадает. Приводили же куски кода, идет перебор до ближайшего простого. Да, из 1024 бит младшие ~10 в результате оказываются не случайными.Так сколько чисел в результате перебирают "до ближайшего простого"?

10 младших бит, это 1024 числа (вместе с чётными), это очень мало для 2^1024.

Если уже в районе 1.0Е+15 диапазоны под 500 чисел.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789260
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Формула плотности простых на квадратный километр у нас есть. Можем примерно прикинуть сколько простых
в диапазоне 2^4096
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789261
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonФормула плотности простых на квадратный километр у нас есть. Можем примерно прикинуть сколько простых
в диапазоне 2^4096По этой формуле 10-ти младших бит не хватит.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789263
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovBarloneпропущено...
Не попадает. Приводили же куски кода, идет перебор до ближайшего простого. Да, из 1024 бит младшие ~10 в результате оказываются не случайными.Так сколько чисел в результате перебирают "до ближайшего простого"?

10 младших бит, это 1024 числа (вместе с чётными), это очень мало для 2^1024.

Если уже в районе 1.0Е+15 диапазоны под 500 чисел.Ну если не повезло, то можно попасть в большой интервал. Но в среднем в районе 2^1024 одно простое на 710 чисел. В районе 2^4096 соответственно одно на 2840.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789266
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneGennadiy Usovпропущено...
Так сколько чисел в результате перебирают "до ближайшего простого"?

10 младших бит, это 1024 числа (вместе с чётными), это очень мало для 2^1024.

Если уже в районе 1.0Е+15 диапазоны под 500 чисел.Ну если не повезло, то можно попасть в большой интервал. Но в среднем в районе 2^1024 одно простое на 710 чисел. В районе 2^4096 соответственно одно на 2840.
Субъективно генерация RSA ключей занимает несколько секунд. Не минут это точно.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789268
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovБыла идея, что возможны составные числа, раз тест простоты "пропускает".
Однако выяснили, что шифр за тестом простоты всё "подчищает".
И что непонятно? Надо найти два простых числа и перемножить, тогда шифрование работает. Если одно из найденных окажется непростое, то шифрование не работает.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789283
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну... я так понимаю что мифы разрушены. Все точки над i поставлены. И топик вобщем не нужен.

P.S. Cartago delenda est
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789314
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
maytonНу... я так понимаю что мифы разрушены. Все точки над i поставлены. И топик вобщем не нужен.
P.S. Cartago delenda est Наверное есть смысл подвести некоторые итоги...

1.Шифр RSA - это "тест простоты", который является более сильным по сравнению с общеизвестными тестами простоты.
Я говорю про шифры, которые применяют два простых числа.

Говорить, что он является "формулой" для поиска простых чисел на диапазоне, пока, наверное, рано.
Но всё равно, в дальнейшем, будем считать, что шифр определяет простые числа.

2.При этом, шифр определяет одновременно не одно простое число, а два простых числа.

3.Шифр ищет простое число в некотором диапазоне от случайного числа в три этапа.

4.На первом этапе "отбрасываются" составные числа
либо с помощью деления на небольшой перечень младших простых чисел
либо с помощью деления на числа 6хК+-1

5.На втором этапе "отбрасываются" составные числа с помощью определёного теста простоты (например, Миллера-Рабина).

6.На третьем этапе "отбрасывается" уже пара чисел, выбранных на первом и втором этапах,
с помощью тестового шифрования-дешифрования.

Получается, что шифр ищет одновременно два простых числа на двух разных диапазонах.

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

Как то так. Может быть я где-то не прав?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789347
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Кажется, ошибка в логике:

Скорее всего, ищется одно простое число.

А вторым для него будет заранее записанное проверенное простое число.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789368
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovКажется, ошибка в логике:

Скорее всего, ищется одно простое число.

А вторым для него будет заранее записанное проверенное простое число.Хреновый тест. Я уже говорил, берете вместо простого числа число Кармайкла - и дешифрование работает.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789515
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
BarloneGennadiy UsovКажется, ошибка в логике:
Скорее всего, ищется одно простое число.
А вторым для него будет заранее записанное проверенное простое число.Хреновый тест. Я уже говорил, берете вместо простого числа число Кармайкла - и дешифрование работает.Но число Кармайкла - составное число.
Как его можно использовать в качестве простого числа в тесте Ш-ДШ?
Ведь в шифре должны участвовать два простых числа.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789521
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если нарисовать блок-схему работы алгоритма RSA мне кажется многие вопросы отпадут.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789527
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Чтобы RSA шифрование-дешифрование работало, нужны два таких числа p, q, чтобы для любого a выполнялось тождество:
Код: plaintext
a (p-1)*(q-1)+1  mod (p*q) = a 
А для этого надо чтобы
Код: plaintext
a p  mod p = a и a q  mod q = a
А для чисел Кармайкла тождество выполняется
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789528
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Числа Кармайкла не нужны не потому, что шифрование не работает, а потому, что маленькие сомножители проще найти.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789574
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovБыла идея, что возможны составные числа, раз тест простоты "пропускает".
Однако выяснили, что шифр за тестом простоты всё "подчищает".

Была идея, формировать составные числа, раз тест простоты их "пропускает".
Однако то, из чего их формировать, надо где-то хранить.
Про эти "идеи" уже недели две назад всё разжёвывалось. Но Геннадий же писатель, а не читатель.
Gennadiy UsovС другой стороны, в районе 2^1024 или 2^2048 количество простых чисел на "километр", то есть на диапазон, очень мало.

Как же так, что произвольно выбранное случайное число точно попадает на простое число?

А ещё Геннадий очень торопится. Или ленится. То есть если бы не ленился (ну и тему читал, а не только писал), то давно бы сам всё посчитал и не выглядел бы ленивым торопыгой.
Gennadiy UsovНо разработчики криптографики об этом не предупреждают.
Просто сказали, что только простое число.
А почему - промолчали.
А здесь Геннадий выдаёт свою торопливость и лень за ошибку разработчиков криптографических решений. Это примерно как ковыряясь в носу заявлять, что кто-то пальцы мне толстыми сделал, глубоко не пролазят, враги во всём виноваты!

В общем неконструктивно себя Геннадий ведёт.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789580
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneМожно еще пытаться сконструировать что-то из больше чем двух сомножителей, там все еще сложнее
А какая разница - сколько простых в произведении, если факторизацию искать миллион лет?

В смысле и числа Кармайклаи другие их виды, которые проходят тест на шифрование-дешифрование, представляют всё ту же сложность, но, возможно, делённую на 2,3,4 и т.д. При порядках в сотни и более деление на 2,3,4 не даст никакого приближения к реальным возможностям, как было больше миллиона лет, так и останется.

Вот разве что есть какие-то закономерности, позволяющие быстрее проводить факторизацию чисел именно из 3,4,5 и т.д. простых.

ЗЫ. Малые простые можно отбросить, ибо факторизацию на них можно простым перебором проверить ещё на стадии выбора секретного числа.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789581
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneДа проверяли же: до 2^64 ноль ошибок.
Интересно. Проверка всех чисел до 2 64 будет длиться, видимо, не менее месяца, а скорее всего даже года, на кластере из 1000 ядер.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789587
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вот интересно, а можно ли найти a и b исходя из такого соотношения


q^2 - k1* ab = 1 + k2 *f

где k1, k2, q, f известны, также известно разложение f на множители
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789638
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy UsovШифр RSA - это "тест простоты", который является более сильным по сравнению с общеизвестными тестами простоты.
Не "более сильным", а "целевым". Он, в принципе, может давать false positive, но для последующего применения ключа это уже неважно.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789639
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
alex55555BarloneМожно еще пытаться сконструировать что-то из больше чем двух сомножителей, там все еще сложнее
А какая разница - сколько простых в произведении, если факторизацию искать миллион лет?

В смысле и числа Кармайклаи другие их виды, которые проходят тест на шифрование-дешифрование, представляют всё ту же сложность, но, возможно, делённую на 2,3,4 и т.д. При порядках в сотни и более деление на 2,3,4 не даст никакого приближения к реальным возможностям, как было больше миллиона лет, так и останется.

Вот разве что есть какие-то закономерности, позволяющие быстрее проводить факторизацию чисел именно из 3,4,5 и т.д. простых.

ЗЫ. Малые простые можно отбросить, ибо факторизацию на них можно простым перебором проверить ещё на стадии выбора секретного числа.Нет, не деление на 2-3-4. Сразу квадратный - кубический корень.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789664
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
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 - было целое число.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789694
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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, или ещё что.

А зачем это надо?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789697
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneНет, не деление на 2-3-4. Сразу квадратный - кубический корень.
А почему? Какая закономерность это обеспечивает?
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39789701
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
alex55555А зачем это надо?alex55555А почему? Какая закономерность это обеспечивает?Вы много вопросов задаёте, пора и подумать, а также почитать ...
...
Рейтинг: 0 / 0
166 сообщений из 166, показаны все 7 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Послепятничная задачка. Криптография и случайное число
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]