RSA

[HeroBrine1st 88]

В сотрудничестве с @Zer0Galaxy мы доработали целочисленную библиотеку metaint.

Итак, встречайте:

RSA

Криптосистема с открытым ключом

• Теперь на "отечественной" библиотеке metaint
• Для поиска простых чисел используется Тест Миллера — Рабина
• Поддерживаются ключи с кастомным количеством бит
• А так же полная оптимизация генерации ключей. Осталось лишь оптимизировать поиск простых чисел и ключи в 2048 бит в ваших руках.

Установка

1. pastebin run 1xudmTa7 - выберите RSA и установите.
2. С hpm проблемы(

 

Использование

Библиотека возвращает класс. Для получения инстанса - просто require("RSA")(<params>): RSA_instance

Аргументом (он один) конструктора класса может быть:

• строка - путь к файлу собственной структуры. В нем обязательно должен быть публичный ключ.
• число (битовая длина ключа, не менее 16 - иначе будет недоступно шифрование текста. Да и не выйдет меньше 16)
• таблица. В ней нужно 3 поля - private_key, public_key и metadata, структура как у файла ключа библиотеки. Так же должен быть публичный ключ. Приватный ключ и метадата необязательны - они хранятся у создателя ключа.

Методы инстанса RSA

• RSA:save(filepath: string) - сохранить ключ в файл
• RSA:encrypt(number:number) - зашифровать число
• RSA:decrypt(cryptedNum: number) - расшифровать число. Кинет ошибку, если нет приватного ключа.
• RSA:sign(number: number) - подписать число. Кинет ошибку, если нет приватного ключа.
• RSA:verify(number:number, signedNumber: number): boolean - проверить подпись. Вернет true, если подпись верна.
• Работа с текстом. Очень медленно, битовая длина ключа - минимум 32 бит.
  • RSA:textEncrypt(text: string[,saltLen=4: number]):table[metaint] - шифрует текст поблочно, перемешивая блоки - защита от DPI. Блок равен 32 бит.
  • RSA:textDecrypt(cryptedText: table[, saltLen=4: number]): string - расшифровывает текст с учетом соли. Применяет обратное преобразование текста для расшифровки - защита от DPI, все дела.
  • RSA:textSign(text:string): table[metaint] - поблочно подписывает текст, перемешивая блоки.
  • RSA:textVerify(text:string, signedBlocks: table[metaint]): boolean, string - проверяет подпись текста. Второе значение - полученная строка.

 

Более полная документация с описанием алгоритмов.

Готовится оптимизация библиотеки, прогресс можно посмотреть в ветке beta репозитория. Спойлер: стоит на месте, ищу способ выполнения длинных битовых операций

 

Изменено 24 сентября, 2019 пользователем HeroBrine1st

[Zer0Galaxy 2 187]

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

[HeroBrine1st Автор темы 88]

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

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

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

Изменено 25 апреля, 2018 пользователем HeroBrine1st

[Zer0Galaxy 2 187]

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

[HeroBrine1st Автор темы 88]

 

 

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

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

[HeroBrine1st Автор темы 88]

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

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

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

Изменено 25 апреля, 2018 пользователем HeroBrine1st

[eu_tomat 2 154]

Попробовал от 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

 

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

[HeroBrine1st Автор темы 88]

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

 

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

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

 

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

Изменено 25 апреля, 2018 пользователем HeroBrine1st

[eu_tomat 2 154]

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

 

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

 

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

[Totoro 3 563]

 

 

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

 

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

[NEO 541]

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

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

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

Изменено 27 апреля, 2018 пользователем NEO

[RccHD 136]

Раз уж ты взялся писать алгоритм 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
 

[qwertyMAN 1 722]

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

[ECS 1 903]

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

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

Изменено 5 мая, 2018 пользователем ECS

[HeroBrine1st Автор темы 88]

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

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

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

[HeroBrine1st Автор темы 88]

Использовав третий метод в сравнении 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 все становится нормально.

Изменено 5 мая, 2018 пользователем HeroBrine1st

[eu_tomat 2 154]

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

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

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

 

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

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

 

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

 

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

 

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

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

[HeroBrine1st Автор темы 88]

Длинную арифметику написать не смог. 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

 

 

Изменено 14 мая, 2018 пользователем HeroBrine1st

[Zer0Galaxy 2 187]

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

[HeroBrine1st Автор темы 88]

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

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