Перейти к публикации

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

Вроде понял в чем дело. 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.

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

 

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


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

Это прекрасно!

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

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


Ссылка на сообщение
Поделиться на других сайтах
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 символа в число преобразовывалась.

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


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

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

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

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

 

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

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

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

 

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

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

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

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


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

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

Основное время занимает генерация простых чисел, что неудивительно - с увеличением диапазона их количество в нем все падает и падает. Тест ферма берет некое число 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 сказал:

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

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

Цитата

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

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

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


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

Создайте аккаунт или войдите в него для комментирования

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

Создать аккаунт

Зарегистрируйтесь для получения аккаунта. Это просто!

Зарегистрировать аккаунт

Войти

Уже зарегистрированы? Войдите здесь.

Войти сейчас

×