Zer0Galaxy 2 187 Опубликовано: 15 мая, 2018 Это будет целочисленная арифметика. Какие нужны операции и нужны ли отрицательные числа? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 16 мая, 2018 Это будет целочисленная арифметика. Какие нужны операции и нужны ли отрицательные числа? Нужны три операции: умножение, возведение в квадрат и взятие остатка от деления Отрицательные числа не нужны. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
jammer312 45 Опубликовано: 16 мая, 2018 (изменено) Не уверен, насколько эффективно и верно предлагаемое, но оно весьма просто. Ну и я на практике не проверял, это просто на ходу придуманный вариант.Сначала надо выяснить, какое максимальное целое число можно хранить в переменной в луа без потери точности, пусть это будет N, тогда n=sqrt(N) (округленное вниз).Длинное число реализуем как индексированную таблицу произвольной длины, в которой в каждой ячейке хранится число от 0 до n, сие есть запись числа в позиционной системе счисления по основанию n+1. Тогда операции можно реализовать по аналогии с сложением/вычитанием/делением/умножением столбиком (с учетом того, что система счисления уже не десятичная, конечно же), при этом операции над разрядами - просто арифметические операторы луа. Выбор основания гарантирует, что при сложении, вычитании и умножении разрядов переполнения или потери точности не будет. Взятие остатка от деления можно реализовать через деление, умножение и вычитание (ессно целочисленное) (a%b = a-(a/b)*b). P.S. Основание у системы счисления выбрано согласно двум соображениям: 1. оно должно быть как можно больше, чтобы кол-во разрядов, а следовательно - кол-во операций при умножении и делении, было как можно меньше; 2. оно должно быть таким, чтобы при самой "опасной" операции - умножении - не происходило потери точности (ну или переполнения, будь в луа целочисленная арифметика).Ну и "какое максимальное целое число можно хранить в переменной в луа без потери точности" сформулировано немного некорректно, я имел ввиду такое число N, что все числа от 0 до N представимы в переменной. Скорее всего с этой оценкой я переосторожничал, но лучше недооценить, чем переоценить. Изменено 16 мая, 2018 пользователем jammer312 Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Zer0Galaxy 2 187 Опубликовано: 17 мая, 2018 (изменено) ... Опытным путем установил, что основание системы счисления должно быть порядка 10^7 В результате получилась вот такая либа. По сути она аналогична метачислам, только целочисленна. Но есть одна проблемка: меня одолела лень и деление (а вместе с ним остаток от деления и возведение в степень по модулю) осталось нереализованным. Метачисла по прежнему можно складывать, вычитать, умножать и сравнивать как между собой, так и с обычными числами. Пример вычисления факториала: Кто не верит, может проверить на калькуляторе PS: вот думаю, нужна ли функция генерации случайного метачисла? Изменено 17 мая, 2018 пользователем Zer0Galaxy Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Zer0Galaxy 2 187 Опубликовано: 17 мая, 2018 Длинную арифметику написать не смог. https://github.com/OpenPrograms/Fingercomp-Programs/blob/master/libbigint/bigint.lua не слушается. А что не так с bigint? По тестировал. Вроде всё нормально Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 17 мая, 2018 (изменено) А что не так с bigint? По тестировал. Вроде всё нормально Жалуется на то, что получило значение, отличное от числа. Не знаю, как это фиксить, ибо я передаю число. Изменено 17 мая, 2018 пользователем HeroBrine1st Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Zer0Galaxy 2 187 Опубликовано: 17 мая, 2018 Пример кода можно? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 17 мая, 2018 Пример кода можно? Кажется, я понял, в чем ошибка. Рекурсивный метод вызывает сам себя, а с ним вызывается и преобразование числа(уже таблицы) в bigint-таблицу. Вот тут и происходит ошибка. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 17 мая, 2018 (изменено) Однако ошибка все равно происходит. Причем там, где обычная арифметика справляется на ура. local RSA = {} local bigint = require("libbigint") function method2(b, e, m) if type(b) == "number" then b = bigint(b) end if e == 0 then return 1 elseif e == 1 then return b elseif e % 2 == 1 then return (method2(b, e - 1, m) * b) % m else local x = method2(b, e / 2, m) return (x*x) % m end end local modulePow = method2 local function fermaTest(p) local a for i = 2, math.huge do if i%p ~= 0 then a = i break end end return modulePow(a,p-1,p)==1 end local function generatePrime() local prime = 4 while not fermaTest(prime) do prime = math.random(0xFF,0xFFF) end return prime end function RSA.getkey() rsa_e = 0 rsa_p = generatePrime() rsa_q = generatePrime() while rsa_q == rsa_p do rsa_q = generatePrime() end rsa_n = rsa_p*rsa_q rsa_phi = (rsa_p-1)*(rsa_q-1) while rsa_e == 0 do local prime = generatePrime() if rsa_phi%prime > 0 then rsa_e = prime end end for i = 2, rsa_phi/2 do if ((i*rsa_phi)+1)%rsa_e == 0 then rsa_d = ((i*rsa_phi)+1)/rsa_e break end end local public = {rsa_e,rsa_n} local private = {rsa_d,rsa_n} return private, public end function RSA.encrypt(number,pE,pN) return modulePow(number,pE,pN) end function RSA.decrypt(number,sD,sN) return modulePow(number,sD,sN) end local private, public = RSA.getkey() print(table.unpack(private)) print(table.unpack(public)) local num1 = RSA.encrypt(4,table.unpack(public)) print(num1) print(RSA.decrypt(num1,table.unpack(private))) return RSA И сама ошибка - http://prntscr.com/jj3jml 76 строка, затем 31 и ошибка происходит в рекурсивном методе method2. Вот же ответ обычной арифметики (Удалил строки с 5й по 7ю) за ~0.3 секунды - http://prntscr.com/jj3kme Изменено 17 мая, 2018 пользователем HeroBrine1st Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Zer0Galaxy 2 187 Опубликовано: 18 мая, 2018 Так это банальный TLWY. Ясно, что длинная арифметика медленнее обычной, вот и не укладываешься в отведенные три секунды. Натыкай где можно sleep(0) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Zer0Galaxy 2 187 Опубликовано: 18 мая, 2018 (изменено) Вроде понял в чем дело. Bigint некорректно выполняет сравнение длинного целого с обычным числом. Например, если сделать так: bi=require("bigint") a=bi(1) =a==1 в результате получим false. Вот твоя прога и зацикливается на строке №31, поскольку в строке №26 всегда имеем false. Изменено 18 мая, 2018 пользователем Zer0Galaxy Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 19 мая, 2018 (изменено) Натыкал. жду ответа третью минуту. а, ща исправим (не хочу плодить сообщения) Изменено 19 мая, 2018 пользователем HeroBrine1st Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 19 мая, 2018 (изменено) Ответ - http://prntscr.com/jjvx97 Код: local RSA = {} local bigint = require("libbigint") function method2(b, e, m) if type(b) == "number" then b = bigint(b) os.sleep(0) end if e == 0 then return 1 elseif e == 1 then os.sleep(0) return b elseif e % 2 == 1 then os.sleep(0) return (method2(b, e - 1, m) * b) % m else os.sleep(0) local x = method2(b, e / 2, m) return (x*x) % m end end local modulePow = method2 local function fermaTest(p) local a for i = 2, math.huge do if i%p ~= 0 then a = i break end end return modulePow(a,p-1,p)==bigint(1) end local function generatePrime() local prime = 4 while not fermaTest(prime) do prime = math.random(0xFFFFFF,0xFFFFFFFFFF) end return prime end function RSA.getkey() rsa_e = 0 rsa_p = generatePrime() rsa_q = generatePrime() while rsa_q == rsa_p do rsa_q = generatePrime() end rsa_n = rsa_p*rsa_q rsa_phi = (rsa_p-1)*(rsa_q-1) while rsa_e == 0 do local prime = generatePrime() if rsa_phi%prime > 0 then rsa_e = prime end end for i = 2, rsa_phi/2 do if ((i*rsa_phi)+1)%rsa_e == 0 then rsa_d = ((i*rsa_phi)+1)/rsa_e break end end local public = {rsa_e,rsa_n} local private = {rsa_d,rsa_n} return private, public end function RSA.encrypt(number,pE,pN) return modulePow(number,pE,pN) end function RSA.decrypt(number,sD,sN) return modulePow(number,sD,sN) end local private, public = RSA.getkey() print(table.unpack(private)) print(table.unpack(public)) local num1 = RSA.encrypt(4,table.unpack(public)) print(num1) print(RSA.decrypt(num1,table.unpack(private))) return RSA Все так же, как и без bigint - число получилось совсем другим. Лично я думаю, что дело в тесте на простоту, поскольку тест Ферма - вероятностный тест и он можешь только лишь подтвердить, составное ли ему дали число, но опровергнуть - нет. UPD. использовал третий метод + бинарник луа. результат тот же - http://prntscr.com/jjw0m9 Изменено 19 мая, 2018 пользователем HeroBrine1st Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 7 марта, 2019 Пришло большое обновление. В сотрудничестве с Zer0Galaxy (не буду тегать второй раз) мы доделали библиотеку metaint и RSA. Добавлена поддержка кастомной длины ключа. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
man_cubus 28 Опубликовано: 7 марта, 2019 Это прекрасно! Пожалуйста добавьте репку в hpm Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 7 марта, 2019 3 часа назад, man_cubus сказал: Пожалуйста добавьте репку в hpm Я пока не готов это сделать. Я переведу эту библиотеку на ООП, тогда выложу на hpm. Предложенный выше алгоритм еще имеет кучу недостатков и не готов к полноценному использованию. Но это уже огромный шаг вперед - библиотека адекватно работает с огромными ключами) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 7 марта, 2019 (изменено) Собственно, поддержка ООП. Когда Zer0Galaxy выложит metaint на npm,я это добавлю в npm и в шапку темы (просто не хочу у себя ее выкладывать, все же большую часть работы он сделал) https://github.com/HeroBrine1st/RSA/tree/master/RSA require("RSA") - все как обычно. RSA(filepath or bitlen) - импортирует или создает класс RSA. Методы класса - save - сохраняет, sign - подписывает число, verify(num:number, cryptedNumber: number) - проверяет подпись, encrypt - шифрует, decrypt - расшифровывает. Наличие публичного ключа в файле ключа обязательно. Для обратной совместимости - require("RSA/RSAB") Изменено 7 марта, 2019 пользователем HeroBrine1st Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 8 марта, 2019 Еще одно большое обновление. Добавлено то, что сказал выше + работа с текстом. С hpm одна большая проблема - пекейдж просто не добавляется. Опять же, требуется помощь с оптимизацией. Подробности мелким шрифтом в шапке внизу. (вкратце - нужно оптимизировать поиск экспонент). Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
Zer0Galaxy 2 187 Опубликовано: 8 марта, 2019 Только что, HeroBrine1st сказал: Добавлено то, что сказал выше + работа с текстом. Это чё, теперь шифровать не только числа но и текст можно? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах
HeroBrine1st Автор темы 88 Опубликовано: 8 марта, 2019 2 минуты назад, Zer0Galaxy сказал: Это чё, теперь шифровать не только числа но и текст можно? Да) Я использовал твои наработки с сети фейстеля, когда там строка в 4 символа в число преобразовывалась. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на других сайтах