· last year · May 26, 2024, 09:20 PM
1RSA_Encrypt = {}
2--used for encoding strings to prepare them for encryption
3-- the mathematical max is 25, higher numbers will cause an overflow
4-- and lead to invalid results.
5RSA_Encrypt.max_chars_per_bignum = 25
6BigNumAPIPath = "api/BigNum"
7BigNum = require(BigNumAPIPath)
8
9
10--Usage Information:
11--
12-- Tested with 256 bit keys, I wouldn't recommend using keys of 512 or 1024 bit length
13--
14-- important: You must download the BigNum api from:
15-- https://github.com/ennorehling/euler/blob/master/BigNum.lua
16-- you can set the path to the BigNum api at the top
17
18
19
20-- !!!!!!! VERY IMPORTANT: !!!!!!!
21-- after downloading the BigNum api, you must open the file and write:
22-- return BigNum
23-- at the end of the file.
24
25
26
27-- To use this api, you will first need your key pairs generated by a different program.
28--
29-- Load public keys using the loadPublicKeyFrom functions
30-- Load private keys using the loadPrivateKeyFrom functions
31
32
33-- To encrypt a string refer to the encryptStringWith.. functions
34-- To decrypt a string refer to the decryptStringWith.. functions
35
36-- Important:
37-- use the prepareNumber(msg) function to convert your number
38-- to the format used in the encrypt/decrypt functions
39--
40-- To encrypt a number, refer to the encryptWith.. functions
41-- To decrypt a number, refer to the decryptWith.. functions
42--
43
44
45
46--############ Begin Functions ############--
47
48--
49-- Description:
50-- encrypts a string using the public key
51--
52-- Parameters:
53-- msg => String: the msg to be encrypted
54-- pub_key => PubKey: the public key
55--
56-- Returns:
57-- String: encrypted message ready for broadcasting
58--
59function RSA_Encrypt.encryptStringWithPublicKey(msg,pub_key)
60 if msg == nil then
61 error("Invalid Parameter #1: msg")
62 end
63 if pub_key == nil then
64 error("Invalid Parameter #2: pub_key")
65 end
66 local result = ""
67 local words = {}
68 local bignums = {}
69 --split msg into [max_chars_per_bignum]-char strings
70 while #msg > RSA_Encrypt.max_chars_per_bignum do
71 table.insert(words,msg:sub(1,25))
72 msg = msg:sub(26,#msg)
73 end
74 if #msg > 0 then
75 table.insert(words,msg)
76 end
77
78 local char_size = BigNum.new(256)
79
80 --encode each word into BigNums (bitshift encoding)
81 for i=1, #words do
82 --for each char in words[i]
83 local bignum = BigNum.new()
84 for c=1, #words[i] do
85 local byte = BigNum.new( string.byte(words[i]:sub(c,c)) )
86 bignum = bignum*char_size + byte
87 end
88 bignum = RSA_Encrypt.encryptWithPublicKey(bignum,pub_key)
89 table.insert(bignums, bignum)
90 result = result..tostring(bignum).." "
91 end
92
93 return result
94end
95
96--
97-- Description:
98-- encrypts a string using the private key
99--
100-- Parameters:
101-- msg => String: the msg to be encrypted
102-- pub_key => PubKey: the public key
103--
104-- Returns:
105-- String: encrypted message ready for broadcasting
106--
107function RSA_Encrypt.encryptStringWithPrivateKey(msg,priv_key,pub_key)
108 if msg == nil then
109 error("Invalid Parameter #1: msg")
110 end
111 if priv_key == nil then
112 error("Invalid Parameter #2: priv_key")
113 end
114 if pub_key == nil then
115 error("Invalid Parameter #3: pub_key")
116 end
117
118 local result = ""
119 local words = {}
120 local bignums = {}
121 --split msg into [max_chars_per_bignum]-char strings
122 while #msg > RSA_Encrypt.max_chars_per_bignum do
123 table.insert(words,msg:sub(1,25))
124 msg = msg:sub(26,#msg)
125 end
126 if #msg > 0 then
127 table.insert(words,msg)
128 end
129
130 local char_size = BigNum.new(256)
131
132 --encode each word into BigNums (bitshift encoding)
133 for i=1, #words do
134 --for each char in words[i]
135 local bignum = BigNum.new()
136 for c=1, #words[i] do
137 local byte = BigNum.new( string.byte(words[i]:sub(c,c)) )
138 bignum = bignum*char_size + byte
139 end
140 bignum = RSA_Encrypt.encryptWithPrivateKey(bignum,priv_key,pub_key)
141 table.insert(bignums, bignum)
142 result = result..tostring(bignum).." "
143 os.sleep(0.001)
144 end
145
146 return result
147end
148
149
150-- Description:
151-- Decrypts a string (encrypted with a private key) using a public key
152-- useful for verifying the message came from a particular sender.
153-- because a message encrypted with someone's private key can be decrypted with
154-- their public key. Very cool!
155--
156-- Paramters:
157-- msg => String: the encrypted message
158-- pub_key => BigNum: the public key n component
159-- pub_e => BigNum: the public key e component
160--
161-- Returns:
162-- String: the decrypted message
163--
164function RSA_Encrypt.decryptStringWithPublicKey(msg,pub_key)
165 if msg == nil then
166 error("Invalid Parameter #1: msg")
167 end
168 if pub_key == nil then
169 error("Invalid Parameter #2: pub_key")
170 end
171
172 --decode bignum into string
173 msg = RSA_Encrypt.splitWords(msg)
174 local result = ""
175 local bignums = {}
176
177 for i=1, #msg do
178 local bignum = BigNum.new(msg[i])
179 bignum = RSA_Encrypt.decryptWithPublicKey(bignum,pub_key)
180 table.insert(bignums, bignum)
181 end
182
183 local char_size = BigNum.new(256)
184 local _0 = BigNum.new(0)
185
186 --decode the decrypted bignums into strings (bitshift encoded)
187 for i=1, #bignums do
188 local word = ""
189 while bignums[i] > _0 do
190 local tmp = BigNum.new()
191 local char = BigNum.new()
192 BigNum.div(bignums[i],char_size,tmp,char)
193 word = string.char( tonumber(tostring(char)) )..word
194 BigNum.copy(tmp,bignums[i])
195 end
196 result = result..word
197 os.sleep(0.001)
198 end
199 return result
200end
201
202
203-- Description:
204-- Decrypts a string (encrypted with a public key) using a private key
205--
206-- Paramters:
207-- msg => String: the encrypted message
208-- priv_key => BigNum: the private key.
209-- pub_key => PubKey: the public key
210--
211-- Returns:
212-- String: the decrypted message
213--
214function RSA_Encrypt.decryptStringWithPrivateKey(msg,priv_key,pub_key)
215 if msg == nil then
216 error("Invalid Parameter #1: msg")
217 end
218 if priv_key == nil then
219 error("Invalid Parameter #2: priv_key")
220 end
221 if pub_key == nil then
222 error("Invalid Parameter #3: pub_key")
223 end
224 --decode bignum into string
225 msg = RSA_Encrypt.splitWords(msg)
226 local result = ""
227 local bignums = {}
228
229 for i=1, #msg do
230 local bignum = BigNum.new(msg[i])
231 bignum = RSA_Encrypt.decryptWithPrivateKey(bignum,priv_key,pub_key)
232 table.insert(bignums, bignum)
233 os.sleep(0.001)
234 end
235
236 local char_size = BigNum.new(256)
237 local _0 = BigNum.new(0)
238
239 --decode the decrypted bignums into strings (bitshift encoded)
240 for i=1, #bignums do
241 local word = ""
242 while bignums[i] > _0 do
243 local tmp = BigNum.new()
244 local char = BigNum.new()
245 BigNum.div(bignums[i],char_size,tmp,char)
246 word = string.char( tonumber(tostring(char)) )..word
247 BigNum.copy(tmp,bignums[i])
248 end
249 result = result..word
250 end
251 return result
252end
253
254
255--
256-- Description:
257-- convert public key to a one line string for sending over modems
258--
259-- Parameters:
260-- pub_key => PubKey: the public key
261--
262-- Returns:
263-- String: the public key for broadcasting
264--
265function RSA_Encrypt.publicKeyToString(_pub_key)
266 if _pub_key == nil then
267 error("Invalid Parameter #1: _pub_key")
268 end
269 local pub_key = _pub_key[1]
270 local pub_e = _pub_key[2]
271 local result = tostring(pub_key).." "..tostring(pub_e)
272 return result
273end
274
275
276--
277-- Description:
278-- Load public key from path
279-- File @ path should contain:
280-- RSA n component on first line
281-- RSA e component on second line
282--
283-- Parameter:
284-- path => path to file containing RSA public key data
285--
286-- Returns:
287-- pub_key ==> a BigNum RSA n component
288-- pub_e ==> a BigNum RSA e component
289--
290function RSA_Encrypt.loadPublicKeyFromFile(path)
291 if path == nil then
292 error("Invalid Parameter #1: path")
293 end
294 if fs.exists(path) then
295 local pub_key_file = fs.open(path,"r")
296 local pub_key = pub_key_file.readLine()
297 local pub_e = pub_key_file.readLine()
298 pub_key = BigNum.new(pub_key)
299 pub_e = BigNum.new(pub_e)
300 return {pub_key, pub_e}
301 else
302 error("pubkey file not found")
303 end
304end
305
306
307--
308-- Description:
309-- creates and returns the e and n component of an RSA Public Key from a string.
310-- the format of the string should be:
311-- pub_key.." "..pub_e
312-- where pub_key is the n component and pub_e is the e component of an RSA Public Key
313--
314-- Parameters:
315-- str ==> a string containing the public key data
316--
317-- Returns:
318-- pub_key ==> a BigNum, the n component of an RSA Public Key
319-- pub_e ==> a BigNum, the e component of an RSA Public Key
320--
321function RSA_Encrypt.loadPublicKeyFromString(str)
322 if str == nil then
323 error("Invalid Parameter #1: str")
324 end
325 local words = RSA_Encrypt.splitWords(str)
326 local pub_key = BigNum.new(words[1])
327 local pub_e = BigNum.new(words[2])
328 return {pub_key, pub_e}
329end
330
331
332--
333-- Description:
334-- Load private key from path
335-- File @ path should contain:
336-- RSA d component
337--
338-- Parameter:
339-- path => path to file containing RSA private key
340--
341-- Returns:
342-- priv_key => a BigNum containing the RSA private key found in path
343--
344function RSA_Encrypt.loadPrivateKeyFromFile(path)
345 if path == nil then
346 error("Invalid Parameter #1: path")
347 end
348 if fs.exists(path) then
349 priv_key_file = fs.open(path,"r")
350 priv_key = priv_key_file.readLine()
351 priv_key = BigNum.new(priv_key)
352 return priv_key
353 else
354 error("privkey file not found")
355 end
356end
357
358--
359-- Description:
360-- Load private key from str
361--
362-- Parameter:
363-- str => a string containing an RSA Private Key (base 10)
364--
365-- Returns:
366-- priv_key => a BigNum containing the RSA private key found in path
367--
368function RSA_Encrypt.loadPrivateKeyFromString(str)
369 if str == nil then
370 error("Invalid Parameter #1: str")
371 end
372 priv_key = BigNum.new(str)
373 return priv_key
374end
375
376--
377-- Description:
378-- Encrypt msg with a given public key
379--
380-- Parameters:
381-- msg ==> a BigNum to be encrypted
382-- pub_key ==> a BigNum, the n component of RSA pub key
383-- pub_e ==> a BigNum, the e component of RSA pub key
384--
385-- Returns:
386-- a BigNum: msg encrypted with the pub key
387--
388function RSA_Encrypt.encryptWithPublicKey(msg, _pub_key)
389 if msg == nil then
390 error("Invalid Parameter #1: msg")
391 end
392 if _pub_key == nil then
393 error("Invalid Parameter #2: _pub_key")
394 end
395 local pub_key = _pub_key[1]
396 local pub_e = _pub_key[2]
397 local result = RSA_Encrypt.BigNumModPow(msg, pub_e, pub_key)
398 return result
399end
400
401
402--
403-- Description:
404-- Encrypt msg with a given private key
405--
406-- Parameters:
407-- msg ==> a BigNum to be encrypted
408-- priv_key ==> a BigNum, the RSA private key
409-- pub_key ==> a BigNum, the n component of RSA public key
410--
411-- Returns:
412-- a BigNum: msg encrypted with the pub key
413--
414function RSA_Encrypt.encryptWithPrivateKey(msg, priv_key, _pub_key)
415 if msg == nil then
416 error("Invalid Parameter #1: msg")
417 end
418 if priv_key == nil then
419 error("Invalid Parameter #2: priv_key")
420 end
421 if _pub_key == nil then
422 error("Invalid Parameter #3: _pub_key")
423 end
424 local pub_key = _pub_key[1]
425 local result = RSA_Encrypt.BigNumModPow(msg, priv_key, pub_key)
426 return result
427end
428
429
430--
431-- Description:
432-- decrypt msg (encrypted with a public key) using the private key
433--
434-- Parameters:
435-- msg ==> a BigNum, the msg to be decrypted
436-- priv_key ==> a BigNum, the RSA private key
437-- pub_key ==> PubKey: the public key
438--
439-- Returns:
440-- a BigNum, the decrypted msg
441--
442function RSA_Encrypt.decryptWithPrivateKey(msg, priv_key, _pub_key)
443 if msg == nil then
444 error("Invalid Parameter #1: msg")
445 end
446 if priv_key == nil then
447 error("Invalid Parameter #2: priv_key")
448 end
449 if _pub_key == nil then
450 error("Invalid Parameter #3: _pub_key")
451 end
452 local pub_key = _pub_key[1]
453 local result = RSA_Encrypt.BigNumModPow(msg, priv_key, pub_key)
454 return result
455end
456
457
458--
459-- Description:
460-- decrypt msg (encrypted with a private key) using the public key
461--
462-- Parameters:
463-- msg ==> a BigNum, the msg to be decrypted
464-- _pub_key ==> a BigNum, the n component of an RSA Public Key
465--
466-- Returns:
467-- the decrypted message in msg.
468function RSA_Encrypt.decryptWithPublicKey(msg, _pub_key)
469 if msg == nil then
470 error("Invalid Parameter #1: msg")
471 end
472 if _pub_key == nil then
473 error("Invalid Parameter #2: _pub_key")
474 end
475 local pub_key = _pub_key[1]
476 local pub_e = _pub_key[2]
477 local result = RSA_Encrypt.BigNumModPow(msg, pub_e, pub_key)
478 return result
479end
480
481
482--
483-- Description:
484-- creates and returns a BigNum from msg
485--
486-- Parameter:
487-- msg ==> a string containing an integer (base 10) OR an int
488--
489-- Returns:
490-- a BigNum, the integer contained in msg
491--
492function RSA_Encrypt.prepareNumber(num)
493 if num == nil then
494 error("Invalid Parameter #1: num")
495 end
496 local result = BigNum.new(num)
497 return result
498end
499
500
501--
502-- Description:
503-- returns num^exponent % modulo
504--
505-- Parameters:
506-- b = a BigNum to be modpow-ed
507-- e = a BigNum exponent
508-- m = a BigNum modulo
509--
510-- Returns:
511-- a BigNum == (base^exponent) % modulo
512--
513function RSA_Encrypt.BigNumModPow(b, e, m)
514 if b == nil then
515 error("Invalid Parameter #1: b")
516 end
517 if e == nil then
518 error("Invalid Parameter #2: e")
519 end
520 if m == nil then
521 error("Invalid Parameter #3: m")
522 end
523 base = BigNum.new()
524 exponent = BigNum.new()
525 modulo = BigNum.new()
526 BigNum.copy(b, base)
527 BigNum.copy(e, exponent)
528 BigNum.copy(m, modulo)
529 --represent 0, 1, and 2 as BigNums
530 local _2 = BigNum.new("2")
531 local _1 = BigNum.new("1")
532 local _0 = BigNum.new("0")
533
534 --if base == 1
535 if BigNum.eq(base,_1) then
536 return 0
537 end
538 local r = BigNum.new("1")
539
540 --base = base % modulo
541 local tmp = BigNum.new()
542 local tmp_res = BigNum.new()
543 local tmp_res_2 = BigNum.new()
544
545 --base = base % modulo
546 BigNum.div(base, modulo, tmp, tmp_res)
547 BigNum.copy(tmp_res,base)
548
549 --while exponent > 0
550 while (BigNum.compare(exponent, _0) == 1) do
551
552 --if exponent % 2 == 1 then
553 BigNum.div(exponent, _2, tmp, tmp_res)
554 if (BigNum.compare(tmp_res, _1) == 0) then
555
556 --r = (r*base) % modulo
557 BigNum.mul(r,base,tmp_res)
558 BigNum.div(tmp_res,modulo,tmp,tmp_res_2)
559 BigNum.copy(tmp_res_2,r)
560 end
561
562 -- base = (base*base) % m
563 BigNum.mul(base,base,tmp_res)
564 BigNum.div(tmp_res,modulo,tmp,tmp_res_2)
565 BigNum.copy(tmp_res_2,base)
566
567 -- e = math.floor(e/2)
568 BigNum.div(exponent,_2,tmp_res,tmp)
569 BigNum.copy(tmp_res,exponent)
570 end
571 return r
572end
573
574
575--
576-- a helper function used by RSA_Encrypt.loadPublicKeyFromString(str)
577--
578function RSA_Encrypt.splitWords(s)
579 if s == nil then
580 error("Invalid Parameter #1: s")
581 end
582 local words = {}
583 local j = 1
584 local btoi = {[true]=1,[false]=0}
585 for i = 1, #s do
586 b = i ~= #s
587 if string.sub(s,i,i) == " " or not b then
588 words[#words+1] = string.sub(s,j,i-1*btoi[b])
589 j=i+1
590 end
591 end
592 return words
593end
594
595--
596-- Run a benchmark of the encryStringWith and decryptStringWith functions
597--
598-- Paramter: str => (Optional) the string to run the benchmark on
599--
600function RSA_Encrypt.benchmark(str)
601 print("\nRunning Benchmark using:")
602 if str == nil then
603 str = "Hello world! This is the default benchmark string. You can run the benchmark with a custom string by adding it to the call parameters"
604 end
605 print(str.."\n")
606
607 local priv_key = BigNum.new("30718027764395347858436300176794542038442961471507061849584361239819342178987")
608 local pub_key = RSA_Encrypt.loadPublicKeyFromString("18430816658637208715061780106076725223340967021069964147042057987714753676151 3")
609
610 --
611 print("Encrypting with public key:")
612 local start = os.epoch("utc")
613 local cipher = RSA_Encrypt.encryptStringWithPublicKey(str,pub_key)
614 local endd = os.epoch("utc")
615 local dist = endd-start
616 print(" took",dist,"ms")
617
618 print("Decrypting with private key:")
619 local start = os.epoch("utc")
620 local decipher = RSA_Encrypt.decryptStringWithPrivateKey(cipher,priv_key,pub_key)
621 if decipher == str then
622 print(" success!")
623 else
624 print(" failed!!")
625 print(" got:"..decipher)
626 end
627 local endd = os.epoch("utc")
628 local dist = endd-start
629 print(" took",dist,"ms")
630
631 print("\nEncrypting with private key:")
632 local start = os.epoch("utc")
633 local cipher = RSA_Encrypt.encryptStringWithPrivateKey(str,priv_key,pub_key)
634 local endd = os.epoch("utc")
635 local dist = endd-start
636 print(" took",dist,"ms")
637
638 print("Decrypting with public key:")
639 local start = os.epoch("utc")
640 local decipher = RSA_Encrypt.decryptStringWithPublicKey(cipher,pub_key)
641 if decipher == str then
642 print(" success!")
643 else
644 print(" failed!!")
645 print(" got:"..decipher)
646 end
647 local endd = os.epoch("utc")
648 local dist = endd-start
649 print(" took",dist,"ms")
650
651 -- print("\nencrypting:")
652 -- print(str)
653 -- local cipher = RSA_Encrypt.encryptStringWithPublicKey(str,pub_key)
654 -- print(cipher)
655 -- print("\ndeciphering")
656 -- local decipher = RSA_Encrypt.decryptStringWithPrivateKey(cipher,priv_key,pub_key)
657 -- print(decipher)
658
659 -- print("\nencrypting:")
660 -- print(str)
661 -- local cipher = RSA_Encrypt.encryptStringWithPrivateKey(str,priv_key,pub_key)
662 -- print(cipher)
663 -- print("\ndeciphering")
664 -- local decipher = RSA_Encrypt.decryptStringWithPublicKey(cipher,pub_key)
665 -- print(decipher)
666end
667
668return RSA_Encrypt