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

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

Это будет целочисленная арифметика. Какие нужны операции и нужны ли отрицательные числа?

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


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

Это будет целочисленная арифметика. Какие нужны операции и нужны ли отрицательные числа?

 

 

Нужны три операции: умножение, возведение в квадрат и взятие остатка от деления

Отрицательные числа не нужны.

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


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

Не уверен, насколько эффективно и верно предлагаемое, но оно весьма просто. Ну и я на практике не проверял, это просто на ходу придуманный вариант.
Сначала надо выяснить, какое максимальное целое число можно хранить в переменной в луа без потери точности, пусть это будет N, тогда n=sqrt(N) (округленное вниз).
Длинное число реализуем как индексированную таблицу произвольной длины, в которой в каждой ячейке хранится число от 0 до n, сие есть запись числа в позиционной системе счисления по основанию n+1. Тогда операции можно реализовать по аналогии с сложением/вычитанием/делением/умножением столбиком (с учетом того, что система счисления уже не десятичная, конечно же), при этом операции над разрядами - просто арифметические операторы луа. Выбор основания гарантирует, что при сложении, вычитании и умножении разрядов переполнения или потери точности не будет. Взятие остатка от деления можно реализовать через деление, умножение и вычитание (ессно целочисленное) (a%b = a-(a/b)*b).

 

P.S. Основание у системы счисления выбрано согласно двум соображениям: 1. оно должно быть как можно больше, чтобы кол-во разрядов, а следовательно - кол-во операций при умножении и делении, было как можно меньше; 2. оно должно быть таким, чтобы при самой "опасной" операции - умножении - не происходило потери точности (ну или переполнения, будь в луа целочисленная арифметика).
Ну и "какое максимальное целое число можно хранить в переменной в луа без потери точности" сформулировано немного некорректно, я имел ввиду такое число N, что все числа от 0 до N представимы в переменной. Скорее всего с этой оценкой я переосторожничал, но лучше недооценить, чем переоценить.

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

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


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

...

Опытным путем установил, что основание системы счисления должно быть порядка 10^7

В результате получилась вот такая либа. По сути она аналогична метачислам, только целочисленна.

Но есть одна проблемка: меня одолела лень и деление (а вместе с ним остаток от деления и возведение в степень по модулю) осталось нереализованным.

Метачисла по прежнему можно складывать, вычитать, умножать и сравнивать как между собой, так и с обычными числами.

Пример вычисления факториала:

QKhFiwd.png

Кто не верит, может проверить на калькуляторе  :)

 

PS: вот думаю, нужна ли функция генерации случайного метачисла?

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

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


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

Длинную арифметику написать не смог. https://github.com/OpenPrograms/Fingercomp-Programs/blob/master/libbigint/bigint.lua не слушается.

А что не так с bigint? По тестировал. Вроде всё нормально

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


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

А что не так с bigint? По тестировал. Вроде всё нормально

Жалуется на то, что получило значение, отличное от числа. Не знаю, как это фиксить, ибо я передаю число.

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

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


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

Пример кода можно?

Кажется, я понял, в чем ошибка. Рекурсивный метод вызывает сам себя, а с ним вызывается и преобразование числа(уже таблицы) в bigint-таблицу. Вот тут и происходит ошибка.

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


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

Однако ошибка все равно происходит. Причем там, где обычная арифметика справляется на ура.

 

 

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

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

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


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

Так это банальный TLWY. Ясно, что длинная арифметика медленнее обычной, вот и не укладываешься в отведенные три секунды. Натыкай где можно sleep(0)

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


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

Вроде понял в чем дело. Bigint некорректно выполняет сравнение длинного целого с обычным числом. Например, если сделать так:

bi=require("bigint")
a=bi(1)
=a==1

в результате получим false.

Вот твоя прога и зацикливается на строке №31, поскольку в строке №26 всегда имеем false.

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

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


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

Натыкал. жду ответа третью минуту.

а, ща исправим (не хочу плодить сообщения)

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

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


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

Ответ - 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

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

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


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

Пришло большое обновление. В сотрудничестве с Zer0Galaxy (не буду тегать второй раз) мы доделали библиотеку metaint и RSA.

Добавлена поддержка кастомной длины ключа.

 

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


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

Пожалуйста добавьте репку в  hpm

Я пока не готов это сделать. Я переведу эту библиотеку на ООП, тогда выложу на hpm.

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

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


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

Собственно, поддержка ООП. Когда 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")

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

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


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

Еще одно большое обновление. Добавлено то, что сказал выше + работа с текстом.

С hpm одна большая проблема - пекейдж просто не добавляется.

 

Опять же, требуется помощь с оптимизацией. Подробности мелким шрифтом в шапке внизу.

(вкратце - нужно оптимизировать поиск экспонент).

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


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

Добавлено то, что сказал выше + работа с текстом.

Это чё, теперь шифровать не только числа но и текст можно? 

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


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

Это чё, теперь шифровать не только числа но и текст можно?  

Да) Я использовал твои наработки с сети фейстеля, когда там строка в 4 символа в число преобразовывалась.

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


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

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

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

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

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

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

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

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

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


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