Перейти к содержимому

Рекомендуемые сообщения

Хотел сегодня провести сногсшибательное обновление с полной оптимизацией всего и вся. Не вышло.

Собственно, появилась оптимизация теста ферма, при первом непрохождении числа возвращает false. Это ускоряет тест для составных чисел (не всех) в 8 раз, но оставляет точность теста нетронутой.

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

 

Из нереализованного, но закомментированного: расширенный алгоритм евклида :C

Прошу помочь с оптимизацией и фиксом уже его (xD), ибо например 64-битный ключ мне так и не удалось на нем сделать - постоянно отбраковывает ключ (с 8ю битами с раза 2-3 делает). Хотя ускоряет создание ключа реально сильно.

https://github.com/HeroBrine1st/RSA/blob/master/RSA/RSAB.lua

 

UPD: я почти разобрался с этим алгоритмом евклида и понял, что какого-то хрена алгоритм обрезает число до семи знаков)) Вот и вся проблема

UPD2: Выход за пределы натуральных чисел - вычитание большего из меньшего. Передлываю алгоритм под натуральные числа.

Изменено пользователем HeroBrine1st
UPD

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Основное время занимает генерация простых чисел, что неудивительно - с увеличением диапазона их количество в нем все падает и падает. Тест ферма берет некое число a в степень p-1 (p - проверяемое число), а вычисление степени, тем более на таких огромных числах - это невероятно сложное вычисление. Даже по модулю. Поиграюсь с тестами простоты, найду самый быстрый и выпущу еще одно обновление.

А дальше - только избавляться от костылей вроде subNum - я решил не ждать Zer0Galaxy и не нагружать его работой, а накостылить целые числа на основе натуральных (и не переделывать алгоритм под натуральные - я не нашел даже описания алгоритма на натуральных числах), тем более, что нужно всего 3 операции - умножение, сложение и вычитание.

Обновление уже на гитхабе, можно скачивать.

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
--вычисление закрытой экспотенты с помощью расширенного алгоритма евклида и моих авторских костылей
  while true do --нахрен он нужен, но мало ли
    rsa_d = modular_inversion(rsa_e,rsa_phi)
    local keyTest = keypairTest({rsa_d,rsa_n},{rsa_e,rsa_n},rsa_phi)
    --print(rsa_d,rsa_e,rsa_n,rsa_phi,keyTest)
    if keyTest then
      break
    end
    RSA_init()
    RSA_E_select()
  end

Я конечно могу ошибаться, но мне всегда казалось, что закрытая экспонента легко вычисляется через открытую экспоненту и функцию Эйлера как

rsa_d=rsa_e:pow( rsa_phi-1, rsa_phi )

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
7 часов назад, Zer0Galaxy сказал:

закрытая экспонента легко вычисляется через открытую экспоненту и функцию Эйлера

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

Нужно тестирование и бенчмаркинг.

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

 

А возможно, просто на больших phi он очень долго возводит. Те же 64 бита - там числа порядка 10^30

Изменено пользователем HeroBrine1st

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
11.03.2019 в 10:09, Zer0Galaxy сказал:

легко вычисляется через открытую экспоненту и функцию Эйлера

Шарил по форумам (в поисках эффективной организации поиска простых чисел), внезапно обнаружил:

Цитата

Итого получаем: ограничение пространства ключей и замену расширенного алгоритма Евклида на более тяжелую операцию - возведение в степень по модулю. Так все же, в чем профит?

Так что моя реализация полностью оправдана, хоть и немного костыльна.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Залил крупное обновление.

Одно из изменений, которое может сломать ваши программы:

  • В функции textEncrypt требуется не сама соль, а длина ее. По умолчанию 4, как и у функции textDecrypt, т.е. от второго аргумента смело избавляйтесь

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

  • Сменил тяжелый тест простоты Ферма на +- быстрый алгоритм Тест Миллера — Рабина. Даже если оптимизации не добавило (субьективно добавило), этот алгоритм используется в настоящей криптографии, а значит переход сделан точно не зря).
  • Для дешифровки и подписи используется китайская теорема об остатках. Это повышает скорость в 4 раза. (В 8 раз, на самом деле, но возведение в степень по модулю дорого обходится:C)
  • Так же 128-битный (например) ключ будет реально 128-битным. Ранее генерировалось 2 числа по 128 бит, итого ключ 256 бит, сейчас делю на 2 длину и получаются ключи в 128 бит. По этой причине минимальный размер ключа теперь 32 бита. Если у вас ключ 16-ти битный, не беспокойтесь: из-за бага он был 32-битным :), лучше беспокойтесь о безопасности))

Сейчас обновлю документацию, но особых изменений в методах нет.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Выпустил Hotfix.

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

Медленнее, зато работает :)

Так же при проверке подписи через textVerify отсекаются нули из подписанного сообщения.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Алгоритм Монтгомери вроде бы должен помочь ускорить возведение в степень по модулю. Но мне не удалось понять эту магию. Кто-нибудь здесь может на пальцах объяснить, как это применить?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
В 23.08.2019 в 21:08, monkey сказал:

Алгоритм Монтгомери вроде бы должен помочь ускорить возведение в степень по модулю. Но мне не удалось понять эту магию. Кто-нибудь здесь может на пальцах объяснить, как это применить?

На пальцах не объясню, но дам намёки.

На Википедии есть статья про умножение Монтгомери. Но она носит справочный характер, а не обучающий. При её чтении надо обратить внимание на следующие моменты:

 

В статье введено понятие n-остатка. И умножение Монтгомери работает не с исходными числами, и с их n-остатками. То есть, сначала числа преобразуются в их n-остатки, которые затем перемножаются по алгоритму Монтгомери. На выходе процедуры умножения также получается n-остаток. И для последующей работы его требуется преобразовать в исходную форму.

 

Преобразования чисел требуют дополнительных вычислений, и на отдельно взятом умножении они лишь ухудшат производительность. Но приятная особенность в том, что самые тяжёлые вычисления выполняются на этапе преобразования чисел в n-остатки. Само умножение и обратное преобразование выполняются заметно быстрее за счёт замены операций деления сдвигами (битовыми в случае двоичной системы). Поэтому существенная экономия достигается при возведении числа в степень, где достаточно один раз выполнить преобразование в n-остатки, выполнить серию умножений n-остатков, а к результату применить обратное преобразование.

 

Обратное преобразование уже присутствует в самой процедуре умножения Монтгомери, и её можно применить для этой цели без изменений, передав в качестве аргументов n-остаток числа и единицу. Результатом умножения будет искомое число.

 

Самая большая магия (которую я сейчас пояснить не могу) происходит в этой стоке: u = (t+(t*n' % r)*n)/r. После её выполнения, возможно, потребуется выполнить u=u-n. Выглядит сложновато, и в выражении даже присутствуют два деления, но за счёт правильного выбора r операция деления легко заменяется сдвигом разрядов числа.

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
22 минуты назад, Doob сказал:

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

Это да. По крайней мере, в Lua от OpenComputers нет заметной разницы во времени выполнения операций сложения, умножения, деления или сдвига для числовых типов. И задействование именно битовых операций вряд ли будет существенным.

 

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

 

Умножение Монтгомери заменяет операцию взятия остатка от деления последовательностью более быстрых операций:

  • одно сравнение
  • одно или два сложения
  • два умножения
  • одно отсечение младших разрядов
  • одно отсечение старших разрядов

В этом весь смысл добавления новых сущностей в старую задачу.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
2 часа назад, Doob сказал:

Как бы это примитив на уровне средней школы.

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Для этого, надо предварительно объяснить существование функций и циклов. В школе у меня такого не было, там тригонометрические функции, корни, да и все итеративные алгоритмы объяснялись магией.

Лучше всего познавать мир на практике - материал на порядки быстрее усваивается.

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
6 часов назад, Doob сказал:

Лучше всего познавать мир на практике - материал на порядки быстрее усваивается.

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

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Теперь стало понятнее. Магия какая-то, но работает. Еще вопросик. Как считается длина ключа RSA? Он состоит из экспоненты и модуля. Сколько бит под что занято?

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
14 часа назад, monkey сказал:

Как считается длина ключа RSA? Он состоит из экспоненты и модуля. Сколько бит под что занято?

В Linux это проверяется так:

 

создать ключ длиной 1024 бита:

$ ssh-keygen -t rsa -b 1024 -N '' -f tmp-rsa-1024b

вывести содержимое ключа в читаемом виде (длинные строки я обрезал для удобства):

$ openssl asn1parse -in tmp-rsa-1024b
    0:d=0  hl=4 l= 605 cons: SEQUENCE
    4:d=1  hl=2 l=   1 prim: INTEGER           :00
    7:d=1  hl=3 l= 129 prim: INTEGER           :B266CDD0ACA7CDB61DA3852B8E831690DFC36C8425E32C449B79D85AF6...
  139:d=1  hl=2 l=   3 prim: INTEGER           :010001
  144:d=1  hl=3 l= 128 prim: INTEGER           :6901C7DD2EF32A4B2A90E83EA60894CCBB58BCD3DFB5228653795996D9...
  275:d=1  hl=2 l=  65 prim: INTEGER           :E518DC47E852FE31DDDA8DB6A3B4D1D5BE1E7A65D55AFDC1E8D7BDDF98...
  342:d=1  hl=2 l=  65 prim: INTEGER           :C759EDF190F560FA22A4F590888F2FB6077091C18C9EAB6CE3B04D3916...
  409:d=1  hl=2 l=  64 prim: INTEGER           :68D3463FB4C2FCC28E73A9322F97D6078A156205E468DD0173EBFB5A2A...
  475:d=1  hl=2 l=  65 prim: INTEGER           :942F591C943092A1DD56D9E3525F7D8BC603FB94F03E921723394E6DFD...
  542:d=1  hl=2 l=  65 prim: INTEGER           :D8ED49BDBF7135BEC25E68E3762AEEAE997406C8CD91715B44C9A43274...

Сопоставить вывод предыдущей команды с этим документом:

https://tls.mbed.org/kb/cryptography/asn1-key-structures-in-der-and-pem

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

Как видно, готовый 1024-битный ключ содержит:

  •   модуль длиной длиной 128 байт (1024 бита);
  •   открытую экспоненту со стандартным значением, специально выбранным для упрощения вычислений на всякого рода умных кофеварках;
  •   закрытую экспоненту длиной 128 байт (1024 бита);

Где-то вместо 128 указано 129 байт и 65 вместо 64. Это связано с тем, что стандарт подразумевает использование целых чисел со знаком, в которых старший бит числа интерпретируется как знак. Чтобы избежать этого, числа с единичным старшим битом расширяются на один байт.

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
7 часов назад, eu_tomat сказал:

Если исходное число превышает N, то после шифрования и дешифрования сообщение превращается в кашу.

Это следствие того, что там используется a^e%N. Т.е. если a >= N, то при возведении числа в степень по модулю число a обрежется до a < N.
Такой изьян системы, тем не менее, в современных реалиях используются ключи в 3072 бит (такой размер дает криптостойкость до 2030 года), а размер блоков гораздо меньше данного.

Потому и существует требование к шифрованию текста - ключ минимум 32 байта. Пока библиотека может вычислять ключи до 128 (~30 секунд на сервере) и 256 бит (~3 минуты на моем компьютере в эмуляторе Lua) - этого хватает с головой. Больший размер мне сгенерировать не удалось(
Нужно оптимизировать поиск простых чисел, а оно упирается в умножение. Тут выше обсуждали, я тоже заинтересовался

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
33 минуты назад, HeroBrine1st сказал:

Пока библиотека может вычислять ключи до 128 (~30 секунд на сервере) и 256 бит (~3 минуты на моем компьютере в эмуляторе Lua) - этого хватает с головой. Больший размер мне сгенерировать не удалось(

У меня результат заметно хуже, даже на CPU Core i7-4770K. 128-битный ключ генерируется в диапазоне 423-130 секунд. А 256-битный -- 377-895 секунд. Нижняя граница: запущен лишь Майнкрафт. Верхняя: во время активной работы в редакторе и браузере. Генерация 512-битного ключа обрывается по TLWY. Я подсунул ключи от openssl, сообщение было даже успешно зашифровано, но дешифрация также оборвалась по TLWY. Генерацию ключей я не смотрел, но шифрование точно имеет хороший потенциал для оптимизации.

 

57 минут назад, HeroBrine1st сказал:

Такой изьян системы, тем не менее, в современных реалиях используются ключи в 3072 бит (такой размер дает криптостойкость до 2030 года), а размер блоков гораздо меньше данного.

Мне вот, что непонятно. При шифровании с солью в выходной таблице появляется не одно число, а два. Это разделение на два независимых блока? И если так, то что мешает разделять любое сообщение даже без соли, если его размер превышает N? А если моя догадка неверна, то какую роль играет второе число при шифровании с солью?

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах
42 минуты назад, eu_tomat сказал:

то какую роль играет второе число при шифровании с солью?

При шифровании:
1. В начало строки добавляется 4 случайных символа - соль
2. Строка делится на блоки по 4 символа, недостающие символы заполняются нулями

3. Для каждого блока используется функция F(P + C mod N), где P - результат предыдущего преобразования (для второго блока - предыдущий блок, для первого - не используется), C - текущий блок. а N - модуль RSA.

4. Результат подается в шифрующую функцию

Соль здесь играет прямую роль в запутывании второго блока (а он - в последующем, и так далее): Если соль изменится хоть на один бит, то после шифрования значение изменится кардинально, причем у всего зашифрованного сообщения.
А является она обычным блоком. Таким же, как и остальные блоки. Просто этот блок нестатичен и предугадать его становится очень тяжело, от чего повышается криптостойкость системы.

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на других сайтах

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в тему...

×   Вы вставили отформатированное содержимое.   Удалить форматирование

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отобразить как ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.


×
×
  • Создать...