Перейти к публикации
Форум - ComputerCraft

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

Оптимизировал возведение в степень по модулю. Работает с большими числами очень быстро и хорошо, вероятность получения inf как результат степени и остатка от деления 0 минимальна.

От метачисел избавился, теперь - чистая Lua.

(Генератор ключей я взял с одного форума разработчиков, сам 2 часа бился над алгоритмом).

Код библиотеки:

local RSA = {}
local primes = { --таблица простых чисел до 1013
    2,      3,      5,      7,      11,     13,     17,     19,     23,     29,
    31,     37,     41,     43,     47,     53,     59,     61,     67,     71,
    73,     79,     83,     89,     97,     101,    103,    107,    109,    113,
    127,    131,    137,    139,    149,    151,    157,    163,    167,    173,
    179,    181,    191,    193,    197,    199,    211,    223,    227,    229,
    233,    239,    241,    251,    257,    263,    269,    271,    277,    281,
    283,    293,    307,    311,    313,    317,    331,    337,    347,    349,
    353,    359,    367,    373,    379,    383,    389,    397,    401,    409,
    419,    421,    431,    433,    439,    443,    449,    457,    461,    463,
    467,    479,    487,    491,    499,    503,    509,    521,    523,    541,
    547,    557,    563,    569,    571,    577,    587,    593,    599,    601,
    607,    613,    617,    619,    631,    641,    643,    647,    653,    659,
    661,    673,    677,    683,    691,    701,    709,    719,    727,    733,
    739,    743,    751,    757,    761,    769,    773,    787,    797,    809,
    811,    821,    823,    827,    829,    839,    853,    857,    859,    863,
    877,    881,    883,    887,    907,    911,    919,    929,    937,    941,
    947,    953,    967,    971,    977,    983,    991,    997,    1009,   1013,
}
local primes_start = 30 -- начальный индекс рандомизации rsa_p и rsa_q
local function modulePow(n1,n2,m) --возведение в степень по модулю
    local c = 1
    for i = 1, n2 do
        c = (c*n1)%m
    end
    return c
end

function RSA.getkey()
  rsa_e = 0

  rsa_p = primes[math.random(primes_start,#primes)]
  rsa_q = rsa_p

  while rsa_q == rsa_p do
      rsa_q = primes[math.random(primes_start,#primes)]
  end

  rsa_n = rsa_p*rsa_q
  rsa_phi = (rsa_p-1)*(rsa_q-1)

  while rsa_e == 0 do
      local prime = primes[math.random(1,#primes)]
      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

return RSA

Методы:

 

RSA.getkey(): table,table - возвращает 2 таблицы с приватным (секретным) и публичным ключами.

Каждая таблица имеет 2 числа, в последующих функциях можно просто использовать table.unpack и вставлять нужную таблицу

 

RSA.encrypt(number:number, public_E, public_N): number - возвращает зашифрованное число, которое можно расшифровать только закрытым ключом

RSA.decrypt(cryptedNumber:number,secret_E,secret_N): number - возвращает дешифрованное число, которое можно использовать, например, как сеансовый ключ (для этого идеально подходит кодирование степени какого-либо числа) и шифровать с помощью, например, более производительной сети Фейстеля, выложенной ранее.

 

Кто-то скажет, что есть дата-карта, но в планшетах нет лишних слотов для нее.

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

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


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

Когда-то давным-давно, когда в майне были только компьютеркрафтовые компы, а метанума и в помине не было, реализовывал я RSA-подобный алгоритм похожим образом. Тогда помню была проблема не с TLWY, а с банальным переполнением, тем не менее ее как то удалось решить. Если в руинах старого хлама найду тот жесткий диск, выложу.

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


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

Оптимизировал алгоритм. Работает моментально, кодирует большие числа без намека на провисание.

Избавился от метачисел, теперь библиотека работает на чистом Lua.

Дополнил таблицу простых чисел.

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

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


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

Я понимаю, что предложенный алгоритм учебно-тренировочный, но всё же хочу заметить: криптостойкость RSA-алгоритма основана на вычислительной сложности факторизации больших чисел. Другими словами, если взломщику удастся найти делитель числа rsa_n, которое входит в открытый ключ, то и секретный ключ вычислить не составит большого труда. В предложенном варианте реализации используются лишь первые несколько простых чисел, а значит и факторизация выполняется на раз-два. Рассмотри возможность нахождения очень больших простых чисел. Эту задачу мне в свое время не удалось решить.

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


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

 

 

Рассмотри возможность нахождения очень больших простых чисел.

Попытался решетом Эратосфена. Получил ошибку заполнения ОЗУ для n = 10 000 000.

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


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

Попробовал от 990000 до 1000000 использовать простые числа. Шифровка - нормально, дешифровка - too long without yielding.

Поставил os.sleep(0) - получил зависнувший сервер (из опенкомпов, а не хост)

UPD: от 50000 до 100000 - все так же

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

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


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

Попробовал от 990000 до 1000000 использовать простые числа. Шифровка - нормально, дешифровка - too long without yielding.

Что и неудивительно с такой реализацией:

 

local function modulePow(n1,n2,m) --возведение в степень по модулю
    local c = 1
    for i = 1, n2 do
        c = (c*n1)%m
    end
    return c
end

 

На помощь придут Алгоритмы быстрого возведения в степень

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


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

Немного погуглив, я заметил, что существуют онлайн-сервисы разложения числа на множители. Вставив туда число вида 42894984343598, разложило примерно за полминуты.

 

То есть можно просто записать сниффером все, включая обмен ключами (я для чего и пишу библиотеку - для коммуникации внутри сети Zn, отсеивая атаку man in-the-middle), а затем в таком сервисе разложить число, получить нужный множитель и найти секретный ключ.

И тут встает вопрос: потянет ли OC числа, которые не потянут такие сервисы? Нет.

 

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

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

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


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

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

 

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

 

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

  • Like 2

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


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

 

 

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

 

Справедливости ради, спамом можно обрушить любую сеть в Майнкрафте.

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


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

Справедливости ради, спамом можно обрушить любую сеть в Майнкрафте.

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

Zn слишком дырявая и не проработанная

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

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


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

Раз уж ты взялся писать алгоритм RSA, то неплохо было бы сначала изучить другие более простые алгоритмы.

Я имею в виду алгоритм возведения в степень

 

Оптимизировал возведение в степень по модулю. Работает с большими числами очень быстро и хорошо


Твоя реализация работает очень медленно (за линейное время), что в итоге будет причиной зависаний компа на целые минуты, а то и часы.
Вот, смотри сам: https://ideone.com/v48E18

Считаю нужным предложить правильную реализацию, которая работает за логарифмическое время (в миллионы или даже в миллиарды раз быстрее)
Вот: https://ideone.com/RyGdbH


P.S. сравни время работы двух реализаций на ideone. (У меня показывает 0.71s VS 0.00s)

P.S.S. подробнее об алгоритме возведения в степень тут: http://e-maxx.ru/algo/binary_pow
 
  • Like 4

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


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

@@HeroBrine1st а зачем тебе статичная таблица простых чисел, если можно легко написать генератор этих чисел? И будет у тебя сколько хочешь таких чисел. Генерация не займёт много времени.

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


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

Считаю нужным предложить правильную реализацию, которая работает за логарифмическое время (в миллионы или даже в миллиарды раз быстрее)

Вставлю свои пять копеек, чтобы правильность была еще более правильной. Ох уж эта правильность... В общем, так как время, затрачиваемое на вызов функций в Lua значительно превышает время осуществления иных операций, следует использовать итеративный метод расчетов вместо рекурсивного. Кроме того, как вполне грамотно заметил товарищ с e-maxx.ru, для определения четности числа имеет смысл заменить "n % 2 == 0" на "n & 1 == 0". В итоге времечко сократится еще втрое. Собсна, пруф: https://ideone.com/t9Yv5F

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

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


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

@@HeroBrine1st а зачем тебе статичная таблица простых чисел, если можно легко написать генератор этих чисел? И будет у тебя сколько хочешь таких чисел. Генерация не займёт много времени.

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

На крайняк можно в /boot/ записать require("RSA") конечно, но это уже вмешательство в openos

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


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

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

 

Вот код:

 

 

local RSA = {}
local primes = {
  11995003,11995019,11995031,11995057,11995079,11995091,11995129,11995147,11995157,11995187,11995201,
  11995229,11995261,11995279,11995303,11995337,11995339,11995343,11995367,11995369,11995381,11995391,
  11995427,11995447,11995453,11995457,11995469,11995499,11995507,11995513,11995537,11995547,11995567,
  11995573,11995619,11995639,11995651,11995661,11995691,11995717,11995721,11995751,11995757,11995759,
  11995769,11995787,11995799,11995813,11995817,11995831,11995843,11995847,11995849,11995873,11995883,
  11995889,11995891,11995909,11995927,11995957,11995961,11995981,11996003,11996009,11996021,11996069,
  11996081,11996099,11996107,11996113,11996119,11996123,11996143,11996147,11996161,11996167,11996191,
  11996197,11996207,11996209,11996249,11996261,11996267,11996279,11996291,11996297,11996323,11996329,
  11996359,11996377,11996381,11996393,11996447,11996449,11996507,11996531,11996533,11996539,11996557,
  11996573,11996591,11996599,11996617,11996627,11996629,11996651,11996681,11996689,11996693,11996701,
  11996711,11996729,11996741,11996753,11996767,11996773,11996791,11996821,11996833,11996837,11996851,
  11996857,11996909,11996911,11996927,11996939,11996987,11996993,11997049,11997059,11997061,11997071,
  11997107,11997109,11997137,11997157,11997179,11997199,11997233,11997247,11997269,11997277,11997299,
  11997311,11997319,11997343,11997347,11997383,11997397,11997409,11997437,11997443,11997449,11997463,
  11997481,11997523,11997533,11997547,11997551,11997553,11997577,11997593,11997599,11997611,11997613,
  11997617,11997637,11997647,11997649,11997659,11997679,11997691,11997751,11997787,11997829,11997841,
  11997847,11997863,11997877,11997893,11997901,11997913,11997917,11997919,11997929,11997943,11997959,
  11997977,11997991,11998009,11998013,11998031,11998033,11998043,11998067,11998121,11998123,11998127,
  11998153,11998171,11998183,11998187,11998201,11998213,11998223,11998297,11998303,11998369,11998381,
  11998391,11998439,11998487,11998501,11998507,11998513,11998529,11998541,11998577,11998589,11998601,
  11998607,11998621,11998661,11998673,11998681,11998697,11998711,11998717,11998733,11998739,11998741,
  11998751,11998759,11998769,11998807,11998813,11998817,11998843,11998859,11998927,11998933,11998949,
  11998951,11998967,11998979,11999027,11999111,11999129,11999153,11999159,11999171,11999173,11999177,
  11999179,11999233,11999257,11999291,11999293,11999303,11999311,11999321,11999329,11999333,11999381,
  11999423,11999443,11999461,11999489,11999513,11999527,11999531,11999551,11999563,11999653,11999657,
  11999681,11999683,11999699,11999719,11999723,11999747,11999749,11999761,11999777,11999789,11999791,
  11999797,11999831,11999837,11999843,11999857,11999879,11999903,11999927,11999929,11999941,11999987,
}

local primes_start = 1 -- начальный индекс рандомизации rsa_p и rsa_q
local function modulePow(b, e, m)
  local result = 1
  b = b % m
 
  while e > 0 do
    if e % 2 == 1 then
      e, result = e - 1, (result * b) % m
    else
      e, b = e / 2, (b * b) % m
    end
  end
 
  return result
end

 
function RSA.getkey()
  rsa_e = 0
 
  rsa_p = primes[math.random(primes_start,#primes)]
  rsa_q = rsa_p
 
  while rsa_q == rsa_p do
      rsa_q = primes[math.random(primes_start,#primes)]
  end
 
  rsa_n = rsa_p*rsa_q
  rsa_phi = (rsa_p-1)*(rsa_q-1)
 
  while rsa_e == 0 do
      local prime = primes[math.random(1,#primes)]
      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()
local num = RSA.encrypt(65536,public[1],public[2])
print(num)
print(RSA.decrypt(num,private[1],private[2]))

return RSA

 

 

 

И выход в opencomputers (lua 5.2) - http://prntscr.com/je2nnp

(после вызова команды первое число - зашифрованное число, второе - расшифрованное)

Шифровал я число 65536. А получил совершенно другие числа.

Попробую второй метод, если тоже не получится - надо будет уменьшать числа в таблице.

UPD: с вторым методом так же

UPD2: с простыми числами 3855000-3859999 все так же. При уменьшении до 1-1000 все становится нормально.

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

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


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

Вставлю свои пять копеек, чтобы правильность была еще более правильной. Ох уж эта правильность... В общем, так как время, затрачиваемое на вызов функций в Lua значительно превышает время осуществления иных операций, следует использовать итеративный метод расчетов вместо рекурсивного. Кроме того, как вполне грамотно заметил товарищ с e-maxx.ru, для определения четности числа имеет смысл заменить "n % 2 == 0" на "n & 1 == 0". В итоге времечко сократится еще втрое. Собсна, пруф: https://ideone.com/t9Yv5F

А я вставлю ещё копейку. Не знаю, как в текущей версии OpenComputers, но около года назад я проводил замеры, и не обнаружил разницы во времени исполнения разной арифметики типа + - * / % & | >> <<

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

 

@@HeroBrine1st а зачем тебе статичная таблица простых чисел, если можно легко написать генератор этих чисел? И будет у тебя сколько хочешь таких чисел. Генерация не займёт много времени.

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

 

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

 

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

 

я нашел странную вещь - при больших числах выходное значение дешифрования отлично от входного значения шифрования.

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

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


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

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

Зато есть генератор простого числа на тесте Ферма. И у него сильно ограничен диапазон из-за отсутствия длинной арифметики.

Раскомментировав последние строки, получите код для проверки алгоритма.

 

 

local RSA = {}

function method2(b, e, m)
  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(4096,table.unpack(public))
-- print(num1)
-- print(RSA.decrypt(num1,table.unpack(private)))
return RSA

 

 

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

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


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

Так может тебе помочь написать длинную арифметику? На подобии метачисел, только на основе таблиц, а не строк?

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


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

Так может тебе помочь написать длинную арифметику? На подобии метачисел, только на основе таблиц, а не строк?

Я бы не отказался

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


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

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

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


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

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

 

 

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

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

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


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

Не уверен, насколько эффективно и верно предлагаемое, но оно весьма просто. Ну и я на практике не проверял, это просто на ходу придуманный вариант.
Сначала надо выяснить, какое максимальное целое число можно хранить в переменной в луа без потери точности, пусть это будет 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)

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


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

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

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

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

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

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

Войти

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

Войти сейчас

×