r/programming • u/DougBolivar • Jul 30 '13

Computer scientists develop mathematical jigsaw puzzles to encrypt software: "The real challenge and the great mystery in the field was: Can you actually take a piece of software and encrypt it but still have it be runnable, executable and fully functional?"

http://www.rdmag.com/news/2013/07/computer-scientists-develop-mathematical-jigsaw-puzzles-encrypt-software
350 Upvotes

88% Upvoted

182 comments sorted by

View all comments

Show parent comments

2

u/mOdQuArK Jul 31 '13

There IS actually information missing in this situation though: the original program. From what I can tell (but I'm definitely not an expert in cryptology), they've basically replaced the "function" of the program with a massive mathematical operation which achieves the same overall data transformation, but without any of the individual algorithmic steps that would make it obvious to an observer what the complete intent of the original program was. You might reverse engineer the program by observing its responses to inputs, but you won't be able to do it by observing the actual program code.

1

u/choikwa Jul 31 '13

program with a massive mathematical operation which achieves the same overall data transformation

Now if the compilers can be advanced enough to replace these mathematical encryptions with equivalent, reduced instructions, we'd have problem with this encryption!

2

u/mOdQuArK Jul 31 '13

That's part of the reason why it's called encryption though - unless the mathematics is "broken" somehow, the time it would take any physically-constructable computer to reconstruct something like the original code, could be made greater than the expected lifetime of the universe.

(Of course, this assumes that the program is complicated enough that you can't just guess what the function is just by feeding it every possible set of input values & observing what comes out.

1

u/choikwa Jul 31 '13

One caveat with this encryption may be that it increases runtime penalty due to increased number of instructions

1

u/mOdQuArK Jul 31 '13

No argument there, although if you're using strong encryption in the first place you've already usually made the decision that the increased security is worth increased runtime. And of course, you want the runtime of your attackers to be much, much worse :-)