# 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?
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
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)
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.
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.
160.     if type(a) == "number" then
162.     elseif type(b) == "number" then
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
187.     elseif type(a) == "number" then
188.         a = bigint(a)
189.     end
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
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
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)
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)
448. end
449.
450. bigintmt = {
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]: ")
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