1lann

rsa-keygen

Jul 31st, 2015
1,009
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. --
  2. -- RSA Key Generator
  3. -- By 1lann
  4. --
  5. -- Refer to license: http://pastebin.com/9gWSyqQt
  6. --
  7.  
  8. --
  9. -- Start of third-party libraries/helpers
  10. --
  11.  
  12. -- two functions to help make Lua act more like C
  13. local function fl(x)
  14.     if x < 0 then
  15.         return math.ceil(x) + 0 -- make -0 go away
  16.     else
  17.         return math.floor(x)
  18.     end
  19. end
  20.  
  21. local function cmod(a, b)
  22.     local x = a % b
  23.     if a < 0 and x > 0 then
  24.         x = x - b
  25.     end
  26.     return x
  27. end
  28.  
  29.  
  30. local radix = 2^24 -- maybe up to 2^26 is safe?
  31. local radix_sqrt = fl(math.sqrt(radix))
  32.  
  33. local bigintmt -- forward decl
  34.  
  35. local function alloc()
  36.     local bi = {}
  37.     setmetatable(bi, bigintmt)
  38.     bi.comps = {}
  39.     bi.sign = 1;
  40.     return bi
  41. end
  42.  
  43. local function clone(a)
  44.     local bi = alloc()
  45.     bi.sign = a.sign
  46.     local c = bi.comps
  47.     local ac = a.comps
  48.     for i = 1, #ac do
  49.         c[i] = ac[i]
  50.     end
  51.     return bi
  52. end
  53.  
  54. local function normalize(bi, notrunc)
  55.     local c = bi.comps
  56.     local v
  57.     -- borrow for negative components
  58.     for i = 1, #c - 1 do
  59.         v = c[i]
  60.         if v < 0 then
  61.             c[i+1] = c[i+1] + fl(v / radix) - 1
  62.             v = cmod(v, radix)
  63.             if v ~= 0 then
  64.                 c[i] = v + radix
  65.             else
  66.                 c[i] = v
  67.                 c[i+1] = c[i+1] + 1
  68.             end
  69.         end
  70.     end
  71.     -- is top component negative?
  72.     if c[#c] < 0 then
  73.         -- switch the sign and fix components
  74.         bi.sign = -bi.sign
  75.         for i = 1, #c - 1 do
  76.             v = c[i]
  77.             c[i] = radix - v
  78.             c[i+1] = c[i+1] + 1
  79.         end
  80.         c[#c] = -c[#c]
  81.     end
  82.     -- carry for components larger than radix
  83.     for i = 1, #c do
  84.         v = c[i]
  85.         if v > radix then
  86.             c[i+1] = (c[i+1] or 0) + fl(v / radix)
  87.             c[i] = cmod(v, radix)
  88.         end
  89.     end
  90.     -- trim off leading zeros
  91.     if not notrunc then
  92.         for i = #c, 2, -1 do
  93.             if c[i] == 0 then
  94.                 c[i] = nil
  95.             else
  96.                 break
  97.             end
  98.         end
  99.     end
  100.     -- check for -0
  101.     if #c == 1 and c[1] == 0 and bi.sign == -1 then
  102.         bi.sign = 1
  103.     end
  104. end
  105.  
  106. local function negate(a)
  107.     local bi = clone(a)
  108.     bi.sign = -bi.sign
  109.     return bi
  110. end
  111.  
  112. local function compare(a, b)
  113.     local ac, bc = a.comps, b.comps
  114.     local as, bs = a.sign, b.sign
  115.     if ac == bc then
  116.         return 0
  117.     elseif as > bs then
  118.         return 1
  119.     elseif as < bs then
  120.         return -1
  121.     elseif #ac > #bc then
  122.         return as
  123.     elseif #ac < #bc then
  124.         return -as
  125.     end
  126.     for i = #ac, 1, -1 do
  127.         if ac[i] > bc[i] then
  128.             return as
  129.         elseif ac[i] < bc[i] then
  130.             return -as
  131.         end
  132.     end
  133.     return 0
  134. end
  135.  
  136. local function lt(a, b)
  137.     return compare(a, b) < 0
  138. end
  139.  
  140. local function eq(a, b)
  141.     return compare(a, b) == 0
  142. end
  143.  
  144. local function le(a, b)
  145.     return compare(a, b) <= 0
  146. end
  147.  
  148. local function addint(a, n)
  149.     local bi = clone(a)
  150.     if bi.sign == 1 then
  151.         bi.comps[1] = bi.comps[1] + n
  152.     else
  153.         bi.comps[1] = bi.comps[1] - n
  154.     end
  155.     normalize(bi)
  156.     return bi
  157. end
  158.  
  159. local function add(a, b)
  160.     if type(a) == "number" then
  161.         return addint(b, a)
  162.     elseif type(b) == "number" then
  163.         return addint(a, b)
  164.     end
  165.     local bi = clone(a)
  166.     local sign = bi.sign == b.sign
  167.     local c = bi.comps
  168.     for i = #c + 1, #b.comps do
  169.         c[i] = 0
  170.     end
  171.     local bc = b.comps
  172.     for i = 1, #bc do
  173.         local v = bc[i]
  174.         if sign then
  175.             c[i] = c[i] + v
  176.         else
  177.             c[i] = c[i] - v
  178.         end
  179.     end
  180.     normalize(bi)
  181.     return bi
  182. end
  183.  
  184. local function sub(a, b)
  185.     if type(b) == "number" then
  186.         return addint(a, -b)
  187.     elseif type(a) == "number" then
  188.         a = bigint(a)
  189.     end
  190.     return add(a, negate(b))
  191. end
  192.  
  193. local function mulint(a, b)
  194.     local bi = clone(a)
  195.     if b < 0 then
  196.         b = -b
  197.         bi.sign = -bi.sign
  198.     end
  199.     local bc = bi.comps
  200.     for i = 1, #bc do
  201.         bc[i] = bc[i] * b
  202.     end
  203.     normalize(bi)
  204.     return bi
  205. end
  206.  
  207. local function multiply(a, b)
  208.     local bi = alloc()
  209.     local c = bi.comps
  210.     local ac, bc = a.comps, b.comps
  211.     for i = 1, #ac + #bc do
  212.         c[i] = 0
  213.     end
  214.     for i = 1, #ac do
  215.         for j = 1, #bc do
  216.             c[i+j-1] = c[i+j-1] + ac[i] * bc[j]
  217.         end
  218.         -- keep the zeroes
  219.         normalize(bi, true)
  220.     end
  221.     normalize(bi)
  222.     if bi ~= bigint(0) then
  223.         bi.sign = a.sign * b.sign
  224.     end
  225.     return bi
  226. end
  227.  
  228. local function kmul(a, b)
  229.     local ac, bc = a.comps, b.comps
  230.     local an, bn = #a.comps, #b.comps
  231.     local bi, bj, bk, bl = alloc(), alloc(), alloc(), alloc()
  232.     local ic, jc, kc, lc = bi.comps, bj.comps, bk.comps, bl.comps
  233.  
  234.     local n = fl((math.max(an, bn) + 1) / 2)
  235.     for i = 1, n do
  236.         ic[i] = (i + n <= an) and ac[i+n] or 0
  237.         jc[i] = (i <= an) and ac[i] or 0
  238.         kc[i] = (i + n <= bn) and bc[i+n] or 0
  239.         lc[i] = (i <= bn) and bc[i] or 0
  240.     end
  241.     normalize(bi)
  242.     normalize(bj)
  243.     normalize(bk)
  244.     normalize(bl)
  245.     local ik = bi * bk
  246.     local jl = bj * bl
  247.     local mid = (bi + bj) * (bk + bl) - ik - jl
  248.     local mc = mid.comps
  249.     local ikc = ik.comps
  250.     local jlc = jl.comps
  251.     for i = 1, #ikc + n*2 do -- fill it up
  252.         jlc[i] = jlc[i] or 0
  253.     end
  254.     for i = 1, #mc do
  255.         jlc[i+n] = jlc[i+n] + mc[i]
  256.     end
  257.     for i = 1, #ikc do
  258.         jlc[i+n*2] = jlc[i+n*2] + ikc[i]
  259.     end
  260.     jl.sign = a.sign * b.sign
  261.     normalize(jl)
  262.     return jl
  263. end
  264.  
  265. local kthresh = 12
  266.  
  267. local function mul(a, b)
  268.     if type(a) == "number" then
  269.         return mulint(b, a)
  270.     elseif type(b) == "number" then
  271.         return mulint(a, b)
  272.     end
  273.     if #a.comps < kthresh or #b.comps < kthresh then
  274.         return multiply(a, b)
  275.     end
  276.     return kmul(a, b)
  277. end
  278.  
  279. local function divint(numer, denom)
  280.     local bi = clone(numer)
  281.     if denom < 0 then
  282.         denom = -denom
  283.         bi.sign = -bi.sign
  284.     end
  285.     local r = 0
  286.     local c = bi.comps
  287.     for i = #c, 1, -1 do
  288.         r = r * radix + c[i]
  289.         c[i] = fl(r / denom)
  290.         r = cmod(r, denom)
  291.     end
  292.     normalize(bi)
  293.     return bi
  294. end
  295.  
  296. local function multi_divide(numer, denom)
  297.     local n = #denom.comps
  298.     local approx = divint(numer, denom.comps[n])
  299.     for i = n, #approx.comps do
  300.         approx.comps[i - n + 1] = approx.comps[i]
  301.     end
  302.     for i = #approx.comps, #approx.comps - n + 2, -1 do
  303.         approx.comps[i] = nil
  304.     end
  305.     local rem = approx * denom - numer
  306.     if rem < denom then
  307.         quotient = approx
  308.     else
  309.         quotient = approx - multi_divide(rem, denom)
  310.     end
  311.     return quotient
  312. end
  313.  
  314. local function multi_divide_wrap(numer, denom)
  315.     -- we use a successive approximation method, but it doesn't work
  316.     -- if the high order component is too small.  adjust if needed.
  317.     if denom.comps[#denom.comps] < radix_sqrt then
  318.         numer = mulint(numer, radix_sqrt)
  319.         denom = mulint(denom, radix_sqrt)
  320.     end
  321.     return multi_divide(numer, denom)
  322. end
  323.  
  324. local function div(numer, denom)
  325.     if type(denom) == "number" then
  326.         if denom == 0 then
  327.             error("divide by 0", 2)
  328.         end
  329.         return divint(numer, denom)
  330.     elseif type(numer) == "number" then
  331.         numer = bigint(numer)
  332.     end
  333.     -- check signs and trivial cases
  334.     local sign = 1
  335.     local cmp = compare(denom, bigint(0))
  336.     if cmp == 0 then
  337.         error("divide by 0", 2)
  338.     elseif cmp == -1 then
  339.         sign = -sign
  340.         denom = negate(denom)
  341.     end
  342.     cmp = compare(numer, bigint(0))
  343.     if cmp == 0 then
  344.         return bigint(0)
  345.     elseif cmp == -1 then
  346.         sign = -sign
  347.         numer = negate(numer)
  348.     end
  349.     cmp = compare(numer, denom)
  350.     if cmp == -1 then
  351.         return bigint(0)
  352.     elseif cmp == 0 then
  353.         return bigint(sign)
  354.     end
  355.     local bi
  356.     -- if small enough, do it the easy way
  357.     if #denom.comps == 1 then
  358.         bi = divint(numer, denom.comps[1])
  359.     else
  360.         bi = multi_divide_wrap(numer, denom)
  361.     end
  362.     if sign == -1 then
  363.         bi = negate(bi)
  364.     end
  365.     return bi
  366. end
  367.  
  368. local counter = 0
  369.  
  370. local function activityDot()
  371.     counter = counter + 1
  372.  
  373.     if counter >= 1000 then
  374.         counter = 0
  375.         write(".")
  376.         sleep(0.01)
  377.     end
  378. end
  379.  
  380. local function intrem(bi, m)
  381.     if m < 0 then
  382.         m = -m
  383.     end
  384.     local rad_r = 1
  385.     local r = 0
  386.     local bc = bi.comps
  387.     for i = 1, #bc do
  388.         activityDot()
  389.         local v = bc[i]
  390.         r = cmod(r + v * rad_r, m)
  391.         rad_r = cmod(rad_r * radix, m)
  392.     end
  393.     if bi.sign < 1 then
  394.         r = -r
  395.     end
  396.     return r
  397. end
  398.  
  399. local function intmod(bi, m)
  400.     local r = intrem(bi, m)
  401.     if r < 0 then
  402.         r = r + m
  403.     end
  404.     return r
  405. end
  406.  
  407. local function rem(bi, m)
  408.     if type(m) == "number" then
  409.         return bigint(intrem(bi, m))
  410.     elseif type(bi) == "number" then
  411.         bi = bigint(bi)
  412.     end
  413.  
  414.     return bi - ((bi / m) * m)
  415. end
  416.  
  417. local function mod(a, m)
  418.     local bi = rem(a, m)
  419.     if bi.sign == -1 then
  420.         bi = bi + m
  421.     end
  422.     return bi
  423. end
  424.  
  425. local printscale = 10000000
  426. local printscalefmt = string.format("%%.%dd", math.log10(printscale))
  427. local function makestr(bi, s)
  428.     if bi >= bigint(printscale) then
  429.         makestr(divint(bi, printscale), s)
  430.     end
  431.     table.insert(s, string.format(printscalefmt, intmod(bi, printscale)))
  432. end
  433.  
  434. local function biginttostring(bi)
  435.     local s = {}
  436.     if bi < bigint(0) then
  437.         bi = negate(bi)
  438.         table.insert(s, "-")
  439.     end
  440.     makestr(bi, s)
  441.     s = table.concat(s):gsub("^0*", "")
  442.     if s == "" then s = "0" end
  443.     return s
  444. end
  445.  
  446. local function biginttonumber(bi)
  447.     return tonumber(biginttostring(bi))
  448. end
  449.  
  450. bigintmt = {
  451.     __add = add,
  452.     __sub = sub,
  453.     __mul = mul,
  454.     __div = div,
  455.     __mod = mod,
  456.     __unm = negate,
  457.     __eq = eq,
  458.     __lt = lt,
  459.     __le = le,
  460.     __tostring = biginttostring,
  461. }
  462.  
  463. local cache = {}
  464. local ncache = 0
  465.  
  466. function bigint(n)
  467.     if cache[n] then
  468.         return cache[n]
  469.     end
  470.     local bi
  471.     if type(n) == "string" then
  472.         local digits = { n:byte(1, -1) }
  473.         for i = 1, #digits do
  474.             digits[i] = string.char(digits[i])
  475.         end
  476.         local start = 1
  477.         local sign = 1
  478.         if digits[i] == '-' then
  479.             sign = -1
  480.             start = 2
  481.         end
  482.         bi = bigint(0)
  483.         for i = start, #digits do
  484.             bi = addint(mulint(bi, 10), tonumber(digits[i]))
  485.         end
  486.         bi = mulint(bi, sign)
  487.     else
  488.         bi = alloc()
  489.         bi.comps[1] = n
  490.         normalize(bi)
  491.     end
  492.     if ncache > 100 then
  493.         cache = {}
  494.         ncache = 0
  495.     end
  496.     cache[n] = bi
  497.     ncache = ncache + 1
  498.     return bi
  499. end
  500.  
  501. --
  502. -- Start of my code
  503. --
  504.  
  505. local bigZero = bigint(0)
  506. local bigOne = bigint(1)
  507.  
  508. local function gcd(a, b)
  509.     if b ~= bigZero then
  510.         return gcd(b, a % b)
  511.     else
  512.         return a
  513.     end
  514. end
  515.  
  516. local function modexp(base, exponent, modulus)
  517.     local r = 1
  518.  
  519.     while true do
  520.         if exponent % 2 == bigOne then
  521.             r = r * base % modulus
  522.         end
  523.         exponent = exponent / 2
  524.  
  525.         if exponent == bigZero then
  526.             break
  527.         end
  528.         base = base * base % modulus
  529.     end
  530.  
  531.     return r
  532. end
  533.  
  534. local function bigRandomWithLength(length, cap)
  535.     if not cap then
  536.         cap = 999999999
  537.     end
  538.  
  539.     local randomString = tostring(math.random(100000000, cap))
  540.  
  541.     while true do
  542.         randomString = randomString ..
  543.             tostring(math.random(100000000, cap))
  544.         if #randomString >= length then
  545.             local finalRandom = randomString:sub(1, length)
  546.             if finalRandom:sub(-1, -1) == "2" then
  547.                 return bigint(finalRandom:sub(1, -2) .. "3")
  548.             elseif finalRandom:sub(-1, -1) == "4" then
  549.                 return bigint(finalRandom:sub(1, -2) .. "5")
  550.             elseif finalRandom:sub(-1, -1) == "6" then
  551.                 return bigint(finalRandom:sub(1, -2) .. "7")
  552.             elseif finalRandom:sub(-1, -1) == "8" then
  553.                 return bigint(finalRandom:sub(1, -2) .. "9")
  554.             elseif finalRandom:sub(-1, -1) == "0" then
  555.                 return bigint(finalRandom:sub(1, -2) .. "1")
  556.             else
  557.                 return bigint(finalRandom)
  558.             end
  559.         end
  560.     end
  561. end
  562.  
  563. local function bigRandom(minNum, maxNum)
  564.     if maxNum < bigint(1000000000) then
  565.         return bigint(math.random(biginttonumber(minNum),
  566.             biginttonumber(maxNum)))
  567.     end
  568.  
  569.     local maxString = tostring(maxNum)
  570.     local cap = tonumber(tostring(maxNum):sub(1, 9))
  571.     local range = #maxString - #tostring(minNum)
  572.  
  573.     if range == 0 then
  574.         return bigRandomWithLength(#maxString, cap)
  575.     end
  576.  
  577.     if #maxString > 30 then
  578.         return bigRandomWithLength(#maxString - 1)
  579.     end
  580.  
  581.     local randomLength = math.random(1, 2^(#maxString - 1))
  582.     for i = 1, #maxString - 1 do
  583.         if randomLength <= (2^i) then
  584.             return bigRandomWithLength(i)
  585.         end
  586.     end
  587. end
  588.  
  589. local function isPrime(n)
  590.     if type(n) == "number" then
  591.         n = bigint(n)
  592.     end
  593.  
  594.     if n % 2 == bigZero then
  595.         return false
  596.     end
  597.  
  598.     local s, d = 0, n - bigOne
  599.     while d % 2 == bigZero do
  600.         s, d = s + 1, d / 2
  601.     end
  602.  
  603.     for i = 1, 3 do
  604.         local a = bigRandom(bigint(2), n - 2)
  605.         local x = modexp(a, d, n)
  606.         if x ~= bigOne and x + 1 ~= n then
  607.             for j = 1, s do
  608.                 x = modexp(x, bigint(2), n)
  609.                 if x == bigOne then
  610.                     return false
  611.                 elseif x == n - 1 then
  612.                     a = bigZero
  613.                     break
  614.                 end
  615.             end
  616.             if a ~= bigZero then
  617.                 return false
  618.             end
  619.         end
  620.     end
  621.  
  622.     return true
  623. end
  624.  
  625. local function generateLargePrime()
  626.     local i = 0
  627.     while true do
  628.         local randomNumber = bigRandomWithLength(39)
  629.  
  630.         if isPrime(randomNumber) then
  631.             return randomNumber
  632.         end
  633.     end
  634. end
  635.  
  636. local function generatePQ(e)
  637.     local randomPrime
  638.     while true do
  639.         randomPrime = generateLargePrime()
  640.         if gcd(e, randomPrime - 1) == bigOne then
  641.             return randomPrime
  642.         end
  643.     end
  644. end
  645.  
  646. local function euclidean(a, b)
  647.     local x, y, u, v = bigZero, bigOne, bigOne, bigZero
  648.     while a ~= bigZero do
  649.         local q, r = b / a, b % a
  650.         local m, n = x - u * q, y - v * q
  651.         b, a, x, y, u, v = a, r, u, v, m, n
  652.     end
  653.     return b, x, y
  654. end
  655.  
  656. local function modinv(a, m)
  657.     local gcdnum, x, y = euclidean(a, m)
  658.     if gcdnum ~= bigOne then
  659.         return nil
  660.     else
  661.         return x % m
  662.     end
  663. end
  664.  
  665. local function generateKeyPair()
  666.     while true do
  667.         local e = generateLargePrime()
  668.         write("-")
  669.         sleep(0.1)
  670.         local p = generatePQ(e)
  671.         write("-")
  672.         sleep(0.1)
  673.         local q = generatePQ(e)
  674.         write("-")
  675.         sleep(0.1)
  676.  
  677.         local n = p * q
  678.         local phi = (p - 1) * (q - 1)
  679.         local d = modinv(e, phi)
  680.  
  681.         -- 104328 is just a magic number (can be any semi-unique number)
  682.         local encrypted = modexp(bigint(104328), e, n)
  683.         local decrypted = modexp(encrypted, d, n)
  684.  
  685.         write("+")
  686.         sleep(0.1)
  687.         counter = 0
  688.  
  689.         if decrypted == bigint(104328) then
  690.             counter = 0
  691.             return {
  692.                 shared = tostring(n),
  693.                 public = tostring(e),
  694.             }, {
  695.                 shared = tostring(n),
  696.                 private = tostring(d),
  697.             }
  698.         end
  699.     end
  700. end
  701.  
  702. if fs.exists("/public.key") or fs.exists("/private.key") then
  703.     print("Generating new RSA keys will overwrite")
  704.     write("your current ones. Continue? [y/N]: ")
  705.     if not read():lower():find("y") then
  706.         return
  707.     end
  708. end
  709.  
  710. print("Generating RSA key pair...")
  711. print("This can take up to a few minutes.")
  712. local start = os.clock()
  713.  
  714. local publicKey, privateKey = generateKeyPair()
  715.  
  716. local f = io.open("/public.key", "w")
  717. f:write(textutils.serialize(publicKey))
  718. f:close()
  719. f = io.open("/private.key", "w")
  720. f:write(textutils.serialize(privateKey))
  721. f:close()
  722.  
  723. print("")
  724. print("Finished! Took " .. math.ceil(os.clock() - start) .. " seconds.")
  725. print("Keys saved to /private.key and /public.key")
RAW Paste Data