Изучаю шифрование. Занялся созданием класса для работы с большими числами. Сделал сложение и вычитание.
Узнал, что есть быстрое умножение.
Нашел Метод умножения Шёнхаге — Штрассена и Fürer's algorithm.

Я так понимаю Fürer's algorithm более новый и работает быстрее. Где о нем почитать по русски?
Еще маленькая проблема в том, что я не дружу с высшей математикой, а она похоже там используется.

Хотелось бы понять принцип работы, чтобы хватило для написания кода.

Здравствуйте, MikelSV, Вы писали:

MSV>Занялся созданием класса для работы с большими числами. Сделал сложение и вычитание.
Создание велосипеда принципиально? Почему не использовать gmp? или mpfr (если вам не подойдёт gmp)

Здравствуйте, MikelSV, Вы писали:

MSV>Изучаю шифрование. Занялся созданием класса для работы с большими числами. Сделал сложение и вычитание.
MSV>Узнал, что есть быстрое умножение.
MSV>Нашел Метод умножения Шёнхаге — Штрассена и Fürer's algorithm.

MSV>Я так понимаю Fürer's algorithm более новый и работает быстрее. Где о нем почитать по русски?
MSV>Еще маленькая проблема в том, что я не дружу с высшей математикой, а она похоже там используется.

MSV>Хотелось бы понять принцип работы, чтобы хватило для написания кода.

Применение Шёнхаге — Штрассена оправдано для ОЧЕНЬ больших чисел
(конкретные оценки сложности есть напр в википедии).
Для практической работы (напр. для криптографии) испольуют методы Тоома-Кука (в частности метод Карацубы).
Для умножения по модулю используется метод Монтгомери.

Здравствуйте, MikelSV, Вы писали:

MSV>Изучаю шифрование. Занялся созданием класса для работы с большими числами. Сделал сложение и вычитание.

MSV>Узнал, что есть быстрое умножение.
MSV>Нашел Метод умножения Шёнхаге — Штрассена и Furer's algorithm.

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

Здравствуйте, potapov.d, Вы писали:

MSV>>Занялся созданием класса для работы с большими числами. Сделал сложение и вычитание.
PD>Создание велосипеда принципиально? Почему не использовать gmp? или mpfr (если вам не подойдёт gmp)

Чтобы научиться плавать — нужно плавать.

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, potapov.d, Вы писали:

MSV>>>Занялся созданием класса для работы с большими числами. Сделал сложение и вычитание.
PD>>Создание велосипеда принципиально? Почему не использовать gmp? или mpfr (если вам не подойдёт gmp)

CC>Чтобы научиться плавать — нужно плавать.

Угу. Например не смотреть на известных пловцов и использовать Стиль Топора.

Здравствуйте, potapov.d, Вы писали:

PD>Угу. Например не смотреть на известных пловцов и использовать Стиль Топора.

выже не знаете задачи топикпастера, может ему там даже crt языка нельзя тащить, нето-что gmp.

Здравствуйте, Sni4ok, Вы писали:

S>Здравствуйте, potapov.d, Вы писали:

PD>>Угу. Например не смотреть на известных пловцов и использовать Стиль Топора.

S>выже не знаете задачи топикпастера, может ему там даже crt языка нельзя тащить, нето-что gmp.

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

Я бы хотел сам узнать, как это делается. И совершенно нет желания копаться в готовых библиотеках, а уж тем более использовать их ибо время позволяет.

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

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

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

Здравствуйте, MikelSV, Вы писали:

MSV>Честно говоря, я смотрю вариантов быстрого умножения много и какой мне использовать ну совершенно не понятно.
Если пишешь для себя, чтоб разобраться в "кухне" то начни с простых и двигай к сложным.

MSV>Да и само шифрование, а точнее использование открытых и закрытых ключей, с возведением в безумные степени не очень позволяет понять с насколько большими числами придется работать.
Для RSA в последнее время норма: 2048 бит, strong считается 4096.
Но это всё модульное возведение. Т.е. в правильной реализации (montgomery exponentiation) больше чем модуль чисел не будет.

MSV>Наверно для начала хотел бы попросить вас дать информации по методам быстрого умножения. Тех, кто с этим работал и может рассказать.
Тебе модульное или обычное умножение надо?

MSV>А для продолжения, хотелось бы наверное простое описание нужного метода. В виде формул я не пойму, в виде кода,... возможно это будет слишком просто, хотя в любом случае буду переписывать заново, для встраивания в свой код.
Ну вот например http://en.wikipedia.org/wiki/Karatsuba_algorithm там в общем то всё просто.

Здравствуйте, CreatorCray, Вы писали:

CC>Здравствуйте, MikelSV, Вы писали:

MSV>>Честно говоря, я смотрю вариантов быстрого умножения много и какой мне использовать ну совершенно не понятно.
CC>Если пишешь для себя, чтоб разобраться в "кухне" то начни с простых и двигай к сложным.
Я пока не понял, какой из методов проще.

MSV>>Да и само шифрование, а точнее использование открытых и закрытых ключей, с возведением в безумные степени не очень позволяет понять с насколько большими числами придется работать.
CC>Для RSA в последнее время норма: 2048 бит, strong считается 4096.
CC>Но это всё модульное возведение. Т.е. в правильной реализации (montgomery exponentiation) больше чем модуль чисел не будет.
Про модульное возведение пока не слышал, почитаю.

MSV>>Наверно для начала хотел бы попросить вас дать информации по методам быстрого умножения. Тех, кто с этим работал и может рассказать.
CC>Тебе модульное или обычное умножение надо?
В принципе, было бы неплохо сделать обычное умножение. для создания полноценного класса работы с большими числами.
Для ключей лучше модульное. Я нашел алгоритм быстрого возведения в степень, думаю, делить по ходу возведения в степень было бы лучше. Хотя, если разберусь с модульным возведением, то он нафик не нужен.

MSV>>А для продолжения, хотелось бы наверное простое описание нужного метода. В виде формул я не пойму, в виде кода,... возможно это будет слишком просто, хотя в любом случае буду переписывать заново, для встраивания в свой код.
CC>Ну вот например http://en.wikipedia.org/wiki/Karatsuba_algorithm там в общем то всё просто.
Там формулы, значения которых я не понимаю

Здравствуйте, MikelSV, Вы писали:

MSV>Я пока не понял, какой из методов проще.
Карацуба — самый простой.

MSV>Про модульное возведение пока не слышал, почитаю.
Ну, правильно оно называется возведение в степень по модулю.
Быстрый алгоритм называется Montgomery Exponentiation.

MSV>>>А для продолжения, хотелось бы наверное простое описание нужного метода. В виде формул я не пойму, в виде кода,... возможно это будет слишком просто, хотя в любом случае буду переписывать заново, для встраивания в свой код.
CC>>Ну вот например http://en.wikipedia.org/wiki/Karatsuba_algorithm там в общем то всё просто.
MSV>Там формулы, значения которых я не понимаю
Мда. А ведь этот алгоритм в общем то элементарен.
Ну можешь ещё у Кнута почитать, там основные алгоритмы для длинных чисел есть в достаточно понятной форме объяснены.
Если не будет получаться попробую тут объяснить на пальцах.

Нашел книжку "Криптография на Си и С++ в действии — Вельшенбах М", читаю.
Правда я не понимаю, чего он там нахимичил с большими числами. Сдается мне, нужно создать отдельную тему по работе с большими числами, чтобы прояснить идеи. Для чего там используется модуль, особенно в сложении больших чисел.

Сделаю пожалуй обычное умножение. И почитаю, о модульном возведении в степень.

Отрывок из книжки проясняет ситуацию по алгоритму Шёнхаге — Штрассена:
"На сегодняшний день в литературе опубликовано множество методов умножения больших и очень больших чисел, среди которых есть и весьма трудные. Одним из самых трудных является алгоритм, предложенный А. Шёнхаге и В. Штрассеном, в основе которого лежит быстрое преобразование Фурье над конечными полями. Время работы этого алгоритма оценивается величиной 0(n log» log log n), где n — число разрядов аргументов (см. [KnuT, п. 4.3.3). Недостаток этого и подобных алгоритмов заключается в том, что выигрыш по скорости по сравнению с классическими методами сложности 0(п2) достигается лишь когда длина сомножителей составляет порядка 8000-10000 двоичных разрядов. До использования таких чисел к криптографии пока еще очень далеко."

Хм, двоичный разряд — 2 бита. это 2000-2500 байт? Сейчас же ключи таких размеров. книжка писалась году в 2000.

Здравствуйте, MikelSV, Вы писали:

MSV>Недостаток этого и подобных алгоритмов заключается в том, что выигрыш по скорости по сравнению с классическими методами сложности 0(п2) достигается лишь когда длина сомножителей составляет порядка 8000-10000 двоичных разрядов. До использования таких чисел к криптографии пока еще очень далеко."
MSV>Хм, двоичный разряд — 2 бита. это 2000-2500 байт? Сейчас же ключи таких размеров. книжка писалась году в 2000.

8000-10000 двоичных разрядов это 8000-10000 бит или 1000-1250 байт.

Здравствуйте, MikelSV, Вы писали:

MSV>Я бы хотел сам узнать, как это делается. И совершенно нет желания копаться в готовых библиотеках, а уж тем более использовать их ибо время позволяет.

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

MSV>Наверно для начала хотел бы попросить вас дать информации по методам быстрого умножения. Тех, кто с этим работал и может рассказать.

MSV>А для продолжения, хотелось бы наверное простое описание нужного метода. В виде формул я не пойму, в виде кода,... возможно это будет слишком просто, хотя в любом случае буду переписывать заново, для встраивания в свой код.

Знание тонкостей работы с большими числами необязательно для работы с асимметричной криптографией.
Это как знание ассемблера для бухгалтерской опердени.
Начинать нужно с хорошего учебника по криптографии, плюс нужно понимать теорию чисел (особенно арифметику по модулю,
теорему Эйлера и т.д.).
Потом взять готовую криптографическую библиотеку. Если нет подходящих готовых схем шифрования, то реализовать свою схему.
Знания быстрого умножения понадобятся, если возникнет необходимость кардинально отрефакторить криптографическую библиотеку,
например из-за ограничений архитектуры.
Из готовых библиотек можно порекомендовать openssl, подкаталог crypto\bn. Но это чистый С.

Здравствуйте, MikelSV, Вы писали:

MSV>Правда я не понимаю, чего он там нахимичил с большими числами. Сдается мне, нужно создать отдельную тему по работе с большими числами, чтобы прояснить идеи. Для чего там используется модуль, особенно в сложении больших чисел.
Скорее всего он там модульную математику рассматривает.

MSV>Хм, двоичный разряд — 2 бита. это 2000-2500 байт? Сейчас же ключи таких размеров. книжка писалась году в 2000.
Ключи в криптографии в байтах никто не меряет
Strong RSA ключом сегодня считается ключ с модулем в 4096 бит.

Подтяни пока math background. Бо у тебя пока замечаются изрядные пробелы в теории.

Здравствуйте, MikelSV, Вы писали:

MSV>Наверно для начала хотел бы попросить вас дать информации по методам быстрого умножения. Тех, кто с этим работал и может рассказать.

Лучше почитай умные книжки:
— High Speed RSA implementation (гуглим) Курить всю — она небольшая.
— Handbook of Applied Cryptography (гуглим) Главы 2,3,14 — курить до просветления.

MSV>А для продолжения, хотелось бы наверное простое описание нужного метода.
В книгах, которые я привел — имено это и есть. Простое и доходчивое описание алгоритмов "длинной арифметики"
Увы — на английском. На русском ничего сравнимого по качеству я не видел.

Здравствуйте, R.O. Prokopiev, Вы писали:

ROP>Знание тонкостей работы с большими числами необязательно для работы с асимметричной криптографией.
Думаю, стоит заметить, что оно хоть и не обязательно но не помешает.
Да и в целом там есть много мест для "разминки мозга" и получения достаточно ценного опыта.

ROP>Начинать нужно с хорошего учебника по криптографии, плюс нужно понимать теорию чисел (особенно арифметику по модулю, теорему Эйлера и т.д.).
+100

ROP>Знания быстрого умножения понадобятся, если возникнет необходимость кардинально отрефакторить криптографическую библиотеку,
Не только.
У меня в результате тестов совершенно неожиданно выяснилось, что моя велосипедная реализация существенно обгоняет OpenSSL bignum по скорости.
В результате для своих проектов у меня в жизнь вместо "одной из готовых криптобиблиотек" пошёл этот "велосипед", только уже приведённый в более менее промышленный вид.

Здравствуйте, CreatorCray, Вы писали:

ROP>>Знание тонкостей работы с большими числами необязательно для работы с асимметричной криптографией.
CC>Думаю, стоит заметить, что оно хоть и не обязательно но не помешает.
CC>Да и в целом там есть много мест для "разминки мозга" и получения достаточно ценного опыта.
Согласен. Но для новичка (который боится каждой формулы как огня) это может затянуть реализацию на приличный срок.
Оптимизировать бигнумы лучше после решения основной задачи. Если такая оптимизация будет оправдана.

Если бы не было проблем в теории, я бы здесь не сидел.

Кстати, почему ключи меряются в битах? так длиннее получается? :]

— High Speed RSA implementation и Handbook of Applied Cryptography нашел, однако понимаю лишь то, что уже знаю.

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


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