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

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

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

Так жду ответа - насколько велика в компьютере база простых чисел?
Где её предел?
То есть, количество простых чисел, начиная с 2.
...
Рейтинг: 0 / 0
17.03.2019, 14:57
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787323
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Gennadiy UsovИ сколько времени нужно искать это число?
Долго. Именно поэтому генерация RSA ключа может длиться несколько секунд.
...
Рейтинг: 0 / 0
17.03.2019, 15:06
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #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
17.03.2019, 15:34
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787336
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
вадя,

не хз, а порядка N/ln(N)
...
Рейтинг: 0 / 0
17.03.2019, 16:30
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787338
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
17.03.2019, 16:46
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787339
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
17.03.2019, 16:52
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787353
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я считал уже дисковые расходы на хранение
Всех 64 битных простых.

Могу найти ссылку.
...
Рейтинг: 0 / 0
17.03.2019, 17:54
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787356
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
вадя
Участник
Изопропилне хз, а порядка N/ln(N)это величины одного порядка
Gennadiy UsovИ ещё вопрос - а сколько чисел "влезает" на компьютер?смотря как хранить..
100 000 000 записей для субд это не много.
BarloneЭто очень маленькое число, для криптографии нужно число в несколько сотен десятичных знаков.ТС спрашивал от цифры 2....
...
Рейтинг: 0 / 0
17.03.2019, 18:00
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787387
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
По оперативной памяти я приводил сравнительные расчеты здесь 21823126
...
Рейтинг: 0 / 0
17.03.2019, 19:22
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787395
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
вадя
Участник
maytonПо оперативной памятитак что такое 30гиг памяти по сравнению терабайтами дисков?
...
Рейтинг: 0 / 0
17.03.2019, 19:46
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787407
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
вадяGennadiy UsovИ ещё вопрос - а сколько чисел "влезает" на компьютер?смотря как хранить..
100 000 000 записей для субд это не много.А если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать?
...
Рейтинг: 0 / 0
17.03.2019, 19:58
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787411
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
вадя
Участник
Gennadiy UsovА если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать?это тоже не много. SSD в RAID5...
...
Рейтинг: 0 / 0
17.03.2019, 20:14
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787413
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
17.03.2019, 20:15
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787414
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
вадяmaytonПо оперативной памятитак что такое 30гиг памяти по сравнению терабайтами дисков?
Читайте внимательно линк. Я там ответил на этот вопрос.
...
Рейтинг: 0 / 0
17.03.2019, 20:18
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787415
вадя
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
вадя
Участник
mayton,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Но клиент не знает.
Система пропустила псевдослучайное число.
И что - облом,
и что делать клиенту, если не получилась расшифровка?
...
Рейтинг: 0 / 0
18.03.2019, 16:41
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787924
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Что-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа.
...
Рейтинг: 0 / 0
18.03.2019, 16:47
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787933
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
18.03.2019, 16:53
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787935
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
BarloneЧто-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа.На каком этапе программы?
...
Рейтинг: 0 / 0
18.03.2019, 16:54
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787942
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy UsovBarloneЧто-то мне кажется, гораздо больше шансов, что из-за бага в программе случится облом, чем из-за составного числа.На каком этапе программы?
Я-бы по другому спросил. Алгорим ЭЦП будет нарушен если множителей будет не 2 а 3 ?
...
Рейтинг: 0 / 0
18.03.2019, 17:01
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39787950
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
maytonGennadiy UsovНа каком этапе программы?Я-бы по другому спросил. Алгорим ЭЦП будет нарушен если множителей будет не 2 а 3 ?Зачем мелочиться.

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

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

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

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

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

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

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

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

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

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

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

10 ms = 0.010 mks = 0.000010 ms

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

10 ns = 0.010 mks = 0.000010 ms

Десять наносекунд это одна десятитысячная милисекунды.
...
Рейтинг: 0 / 0
18.03.2019, 20:09
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39788083
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
18.03.2019, 20:57
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39788089
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
18.03.2019, 21:15
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39788147
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
Теорема Эйлера в теории чисел гласит:
Если a и m взаимно просты, то ....

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

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

10 ns = 0.010 mks = 0.000010 ms

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Защитники простых чисел в криптографии – защищайтесь!
...
Рейтинг: 0 / 0
20.03.2019, 10:00
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39788844
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
20.03.2019, 10:21
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39788918
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
Gennadiy Usov,

если a,b,c,d не равны между собой и являются простыми числами то ДА
...
Рейтинг: 0 / 0
20.03.2019, 11:54
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39788919
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
20.03.2019, 11:55
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39788937
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Gennadiy UsovmaytonМне кажется ты на основе свойств функции Эйлера "продавливаешь" свою гипотезу.Да, несколько дней назад это было гипотезой.
А сейчас – это уже более серьёзное утверждение.

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А вторым для него будет заранее записанное проверенное простое число.Хреновый тест. Я уже говорил, берете вместо простого числа число Кармайкла - и дешифрование работает.
...
Рейтинг: 0 / 0
21.03.2019, 09:41
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39789515
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
BarloneGennadiy UsovКажется, ошибка в логике:
Скорее всего, ищется одно простое число.
А вторым для него будет заранее записанное проверенное простое число.Хреновый тест. Я уже говорил, берете вместо простого числа число Кармайкла - и дешифрование работает.Но число Кармайкла - составное число.
Как его можно использовать в качестве простого числа в тесте Ш-ДШ?
Ведь в шифре должны участвовать два простых числа.
...
Рейтинг: 0 / 0
21.03.2019, 12:36
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39789521
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Если нарисовать блок-схему работы алгоритма RSA мне кажется многие вопросы отпадут.
...
Рейтинг: 0 / 0
21.03.2019, 12:44
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39789527
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
21.03.2019, 12:52
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39789528
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Числа Кармайкла не нужны не потому, что шифрование не работает, а потому, что маленькие сомножители проще найти.
...
Рейтинг: 0 / 0
21.03.2019, 12:55
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39789574
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
Gennadiy UsovБыла идея, что возможны составные числа, раз тест простоты "пропускает".
Однако выяснили, что шифр за тестом простоты всё "подчищает".

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

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

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

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

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

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

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


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

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

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

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

ЗЫ. Малые простые можно отбросить, ибо факторизацию на них можно простым перебором проверить ещё на стадии выбора секретного числа.Нет, не деление на 2-3-4. Сразу квадратный - кубический корень.
...
Рейтинг: 0 / 0
21.03.2019, 14:56
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39789664
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
21.03.2019, 15:17
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39789694
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
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
21.03.2019, 15:53
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39789697
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
BarloneНет, не деление на 2-3-4. Сразу квадратный - кубический корень.
А почему? Какая закономерность это обеспечивает?
...
Рейтинг: 0 / 0
21.03.2019, 15:53
| Ответить | Цитировать | Написать  
Послепятничная задачка. Криптография и случайное число
    #39789701
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gennadiy Usov
Гость
alex55555А зачем это надо?alex55555А почему? Какая закономерность это обеспечивает?Вы много вопросов задаёте, пора и подумать, а также почитать ...
...
Рейтинг: 0 / 0
21.03.2019, 15:58
| Ответить | Цитировать | Написать  
166 сообщений из 166, показаны все 7 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Послепятничная задачка. Криптография и случайное число
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=16&tid=1339973]:
 0ms
get settings:
 11ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 147ms
get topic data:
 11ms
get forum data:
 3ms
get page messages:
 170ms
get tp. blocked users:
 2ms
others: 43ms
total:  409ms
созд. / загр.: 409ms
x
x
Закрыть


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