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

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

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

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

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

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

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



Реально мы можем складывать небольшой объем только в Memory (это те самые бюджетные 30Гб).
Чтоб не разорится. По времени доступа к произвольной ячейке. Точных цифр я не помню но по моему для
памяти класса DDR4 это составляет 10-16 наносекунд.

Время доступа к диску. Обычно меряют чтение случайного сектора. И там это время на много порядков
хуже. Будет порядка милисекунд. Точно не помню но в процессе топика мы уточним.

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

(избавимся от множителя)

10 ms = 0.010 mks = 0.000010 ms

10 ms : 10 ns = 100 000 : 1

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

По поводу дисков (Hard Disk). Я возьму за основу WD (Western Digital) Purple 10TB 256MB 5400rpm WD100PURZ 3.5 SATA III.
Это наиболее толстый диск (10 терабайт) который я нашел в розничной торговле. Он - типичный медленнячок.
Для бэкапов и архивов. Скорость шпинделя 5400 - оборотов какраз говорит об этом. Это не для игр и операционок
а для долгого хранения информации.

Его цена в данный момент времени - $339.99 на сайте производителя.
Под спойлером. Если вы врдуг решили что выбор плохой и вы знаете другой диск получше - я не буду
против. Мы просто пересчитаем цифры. Но в целом перерасчет не сильно повлияет на результат. Вангую не более
десятка процентов.


Его мощность составляет 6.2 Вт.
Габариты 26.1 x 147 x 101.6 мм, 0.65 кг
Прошу запомнить эти цифры. Мы к ним еще вернемся. Мы посчитаем массу и кубатуру дискового
хранилища для любого диапазона простых чисел.

Кроме того мы посчитает удельную стоимость хранения 1 простого числа в долларах или центах как будет угодно.

SSD мы пока тоже брать не будем. Т.к. по сути SSD это энергонезависимая
память имеющая интерфейс диска. Как класс хранения она мне в топике неинтересна и кроме того в пирамиде
памяти она слишком дорога для нашей задачи. Но как кеш ее можно рассмотреть.


Что еще осталось за кадром. Как хранить? В каком формате? Надо ответить на следующие вопросы.
- (1) нужен-ли нам произвольный доступ к любому числу? Или хватит последовательного?
- (2) нужно-ли сжатие? (zip/gzip)
- нужен-ли поиск в диапазоне?
- гибридные варианты пунктов (1) (2) можно бить на блоки и использовать псевдо-последовательный и псевдо-произвольный
- API/форматы. Определяются (1) (2). Базы данных. CSV-файлы. Raw-store. Key-value. Key-value (hash/b+tree). Bitmap.

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

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

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

Поэтому я отвечу. Не проблема обработать 1 триллион чисел. Проблема - сделать это быстро.
Тоесть придумать совокупность тех-средств (конфигурация) и алгоритмов чтобы наши запросы
(я еще не знаю какие) создали мягкую нагрузку на железо и выдали результат. И в разумное
время. До того как погаснет солнце.
...
Рейтинг: 0 / 0
Послепятничная задачка. Криптография и случайное число
    #39787421
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вадяGennadiy UsovА если я хочу в одной программе обрабатывать 1 000 000 000 000 чисел, то что делать?это тоже не много. SSD в RAID5...
Это очень малое требование. Надо простое число порядка 2^1024 или примерно 10^307.
В диапазоне 2^1023 ... 2^1024 примерно 2^1013 или 10^304 простых чисел.
...
Рейтинг: 0 / 0
25 сообщений из 166, страница 1 из 7
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Послепятничная задачка. Криптография и случайное число
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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